关于单循环链表的写法
#include<iostream>using namespace std;
#include"time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}Node,*LinkList;
Status visit(ElemType c);
Status InitList(LinkList* L);
Status ListEmpty(LinkList L);
Status ClearList(LinkList* L);
Status DestroyList(LinkList* L);
Status visit(ElemType c)
{
cout << c << " ";
return 0;
}
Status InitList(LinkList *L)
{
*L = new Node;
if (!(*L))
{
return ERROR;
}
(*L)->next = *L;
}
Status ListEmpty(LinkList L)
{
if (L->next=L)
{
return TRUE;
}
else
{
return FALSE;
}
}
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;
while (p!=*L)
{
q = p->next;
delete p;
p = q;
}
(*L)->next = *L;
return OK;
}
Status DestroyList(LinkList* L)
{
LinkList p;
p = (*L);
while (*L!=(*L)->next)
{
p = (*L);
(*L) = (*L)->next;
delete p;
}
delete *L;
return OK;
}
int main()
{
return 0;
}
如果判断了*L=*L->next,就是一个空表,循环结束再删除(*L),有点繁琐,有没有更好解决的办法 好方法?之前不是给你写了吗?你都不看吗?
Status DestroyList(LinkList *L) {
ClearList(L);
delete *L;
*L = NULL;
return OK;
}
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=220216&pid=6036030 我不能理解,我给你写了那么多东西,你都不看,伤心的说
我还以为你都看了,都弄懂了
人造人 发表于 2022-11-8 21:02
我还以为你都看了,都弄懂了
过一遍单链表以后,想手写一次循环单链表,思维卡主了,在循环链表上,设置头指针和尾指针上思路有些不够清晰{:5_100:} 1094570635 发表于 2022-11-8 21:30
过一遍单链表以后,想手写一次循环单链表,思维卡主了,在循环链表上,设置头指针和尾指针上思路有些不够 ...
都一样,销毁链表就是把链表清空了,然后删除头结点
1094570635 发表于 2022-11-8 21:30
过一遍单链表以后,想手写一次循环单链表,思维卡主了,在循环链表上,设置头指针和尾指针上思路有些不够 ...
清空链表等于什么呢?
等于一直删除第0个结点,直到链表为空
删除结点就没办法了,得老老实实的操作底层结构
人造人 发表于 2022-11-8 21:34
清空链表等于什么呢?
等于一直删除第0个结点,直到链表为空
有没有设置尾节点操作的办法,感觉循环链表用头结点操作比较麻烦orz,还有就是设置了尾节点操作链表插入,删除和单链表对比,需要做些什么修改么 1094570635 发表于 2022-11-8 21:53
有没有设置尾节点操作的办法,感觉循环链表用头结点操作比较麻烦orz,还有就是设置了尾节点操作链表插入, ...
把思维逆转过来,为什么头结点指向的就必须是第0个元素?
为什么头结点不能是指向最后一个元素?
下面这个代码把头结点指向的元素看成是最后一个元素
也就是那个所谓的 尾节点
#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList;
Status InitList(LinkList *L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList *L);
Status ListInsert(LinkList *L, int i, ElemType e);
Status ListDelete(LinkList *L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);
Status InitList(LinkList *L) {
*L = new Node;
if(!*L) return ERROR;
(*L)->next = *L;
return OK;
}
Status DestroyList(LinkList *L) {
ClearList(L);
delete *L;
return OK;
}
Status ClearList(LinkList *L) {
ElemType e;
while(!ListEmpty(*L)) ListDelete(L, 0, &e);
return OK;
}
Status ListInsert(LinkList *L, int i, ElemType e) {
int length = ListLength(*L);
if(i > length) return FALSE;
LinkList p = *L;
for(int x = 0; x < length - i; ++x) p = p->next;
LinkList q = new Node;
if(!q) return FALSE;
q->data = e;
q->next = p->next;
p->next = q;
return TRUE;
}
Status ListDelete(LinkList *L, int i, ElemType *e) {
int length = ListLength(*L);
if(i >= length) return FALSE;
LinkList p = *L;
for(int x = 0; x < length - i - 1; ++x) p = p->next;
LinkList q = p->next;
p->next = q->next;
delete q;
return TRUE;
}
Status GetElem(LinkList L, int i, ElemType *e) {
int length = ListLength(L);
if(i >= length) return FALSE;
LinkList p = L;
for(int x = 0; x < length - i; ++x) p = p->next;
*e = p->data;
return TRUE;
}
Status SetElem(LinkList L, int i, const ElemType *e) {
ElemType temp;
Status s = ListDelete(&L, i, &temp);
return s ? ListInsert(&L, i, *e) : s;
}
int ListLength(LinkList L) {
int i = 0;
LinkList p = L;
while(p->next != L) {
i++;
p = p->next;
}
return i;
}
Status ListEmpty(LinkList L) {
if(ListLength(L) == 0) return TRUE;
return FALSE;
}
Status visit(ElemType c) {
cout << c << " ";
return OK;
}
Status ListTraverse(LinkList L) {
for(int i = 0; i < ListLength(L); ++i) {
ElemType e;
GetElem(L, i, &e);
visit(e);
}
cout << endl;
return OK;
}
Status ListAppend(LinkList L, const ElemType *e) {
return ListInsert(&L, ListLength(L), *e);
}
int main() {
LinkList L;
InitList(&L);
for(ElemType i = 0; i < 10; ++i) {
ListAppend(L, &i);
}
ListTraverse(L);
ElemType e = 100; SetElem(L, 3, &e);
ListTraverse(L);
GetElem(L, 5, &e);
cout << e << endl;
DestroyList(&L);
return 0;
}
或者把next换成prev更好理解一些?
#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef struct Node {
ElemType data;
//struct Node *next;
struct Node *prev;
} Node;
typedef struct Node *LinkList;
Status InitList(LinkList *L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList *L);
Status ListInsert(LinkList *L, int i, ElemType e);
Status ListDelete(LinkList *L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);
Status InitList(LinkList *L) {
*L = new Node;
if(!*L) return ERROR;
(*L)->prev = *L;
return OK;
}
Status DestroyList(LinkList *L) {
ClearList(L);
delete *L;
return OK;
}
Status ClearList(LinkList *L) {
ElemType e;
while(!ListEmpty(*L)) ListDelete(L, 0, &e);
return OK;
}
Status ListInsert(LinkList *L, int i, ElemType e) {
int length = ListLength(*L);
if(i > length) return FALSE;
LinkList p = *L;
for(int x = 0; x < length - i; ++x) p = p->prev;
LinkList q = new Node;
if(!q) return FALSE;
q->data = e;
q->prev = p->prev;
p->prev = q;
return TRUE;
}
Status ListDelete(LinkList *L, int i, ElemType *e) {
int length = ListLength(*L);
if(i >= length) return FALSE;
LinkList p = *L;
for(int x = 0; x < length - i - 1; ++x) p = p->prev;
LinkList q = p->prev;
p->prev = q->prev;
delete q;
return TRUE;
}
Status GetElem(LinkList L, int i, ElemType *e) {
int length = ListLength(L);
if(i >= length) return FALSE;
LinkList p = L;
for(int x = 0; x < length - i; ++x) p = p->prev;
*e = p->data;
return TRUE;
}
Status SetElem(LinkList L, int i, const ElemType *e) {
ElemType temp;
Status s = ListDelete(&L, i, &temp);
return s ? ListInsert(&L, i, *e) : s;
}
int ListLength(LinkList L) {
int i = 0;
LinkList p = L;
while(p->prev != L) {
i++;
p = p->prev;
}
return i;
}
Status ListEmpty(LinkList L) {
if(ListLength(L) == 0) return TRUE;
return FALSE;
}
Status visit(ElemType c) {
cout << c << " ";
return OK;
}
Status ListTraverse(LinkList L) {
for(int i = 0; i < ListLength(L); ++i) {
ElemType e;
GetElem(L, i, &e);
visit(e);
}
cout << endl;
return OK;
}
Status ListAppend(LinkList L, const ElemType *e) {
return ListInsert(&L, ListLength(L), *e);
}
int main() {
LinkList L;
InitList(&L);
for(ElemType i = 0; i < 10; ++i) {
ListAppend(L, &i);
}
ListTraverse(L);
ElemType e = 100; SetElem(L, 3, &e);
ListTraverse(L);
GetElem(L, 5, &e);
cout << e << endl;
DestroyList(&L);
return 0;
}
人造人 发表于 2022-11-8 22:53
或者把next换成prev更好理解一些?
Status DestroyList(LinkList *L) {
ClearList(L);
delete *L;
*L = NULL;
return OK;
}
感谢,另外我能问一下,ClearList(L)函数中,即是函数调用函数的时候,形参L=LinkList L,对么?即是可以直接写L,不用&L接收 1094570635 发表于 2022-11-8 23:30
Status DestroyList(LinkList *L) {
ClearList(L);
delete *L;
就初始化的时候需要取地址,其他的都不需要
#include <iostream>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef struct Node {
ElemType data;
//struct Node *next;
struct Node *prev;
} Node;
typedef struct Node *LinkList;
Status InitList(LinkList *L);
Status DestroyList(LinkList L);
Status ClearList(LinkList L);
Status ListInsert(LinkList L, int i, ElemType e);
Status ListDelete(LinkList L, int i, ElemType *e);
Status GetElem(LinkList L, int i, ElemType *e);
Status SetElem(LinkList L, int i, const ElemType *e);
int ListLength(LinkList L);
Status ListEmpty(LinkList L);
Status ListTraverse(LinkList L);
Status InitList(LinkList *L) {
*L = new Node;
if(!*L) return ERROR;
(*L)->prev = *L;
return OK;
}
Status DestroyList(LinkList L) {
ClearList(L);
delete L;
return OK;
}
Status ClearList(LinkList L) {
ElemType e;
while(!ListEmpty(L)) ListDelete(L, 0, &e);
return OK;
}
Status ListInsert(LinkList L, int i, ElemType e) {
int length = ListLength(L);
if(i > length) return FALSE;
LinkList p = L;
for(int x = 0; x < length - i; ++x) p = p->prev;
LinkList q = new Node;
if(!q) return FALSE;
q->data = e;
q->prev = p->prev;
p->prev = q;
return TRUE;
}
Status ListDelete(LinkList L, int i, ElemType *e) {
int length = ListLength(L);
if(i >= length) return FALSE;
LinkList p = L;
for(int x = 0; x < length - i - 1; ++x) p = p->prev;
LinkList q = p->prev;
p->prev = q->prev;
delete q;
return TRUE;
}
Status GetElem(LinkList L, int i, ElemType *e) {
int length = ListLength(L);
if(i >= length) return FALSE;
LinkList p = L;
for(int x = 0; x < length - i; ++x) p = p->prev;
*e = p->data;
return TRUE;
}
Status SetElem(LinkList L, int i, const ElemType *e) {
ElemType temp;
Status s = ListDelete(L, i, &temp);
return s ? ListInsert(L, i, *e) : s;
}
int ListLength(LinkList L) {
int i = 0;
LinkList p = L;
while(p->prev != L) {
i++;
p = p->prev;
}
return i;
}
Status ListEmpty(LinkList L) {
if(ListLength(L) == 0) return TRUE;
return FALSE;
}
Status visit(ElemType c) {
cout << c << " ";
return OK;
}
Status ListTraverse(LinkList L) {
for(int i = 0; i < ListLength(L); ++i) {
ElemType e;
GetElem(L, i, &e);
visit(e);
}
cout << endl;
return OK;
}
Status ListAppend(LinkList L, const ElemType *e) {
return ListInsert(L, ListLength(L), *e);
}
int main() {
LinkList L;
InitList(&L);
for(ElemType i = 0; i < 10; ++i) {
ListAppend(L, &i);
}
ListTraverse(L);
ElemType e = 100; SetElem(L, 3, &e);
ListTraverse(L);
GetElem(L, 5, &e);
cout << e << endl;
DestroyList(L);
return 0;
}
人造人 发表于 2022-11-8 23:55
就初始化的时候需要取地址,其他的都不需要
在循环链表中,插入位置的合理性不能用p!=NULL,能否用p!=L来判断?,还是只能通过表长的长度来判断元素的插入位置是否合理? 1094570635 发表于 2022-11-9 19:33
在循环链表中,插入位置的合理性不能用p!=NULL,能否用p!=L来判断?,还是只能通过表长的长度来判断元素 ...
整那么复杂干嘛
通过表长的长度来判断 获取链表长度的函数已经写了,写了函数为什么不用呢,直接用链表长度判断不是更好?
人造人 发表于 2022-11-9 19:40
获取链表长度的函数已经写了,写了函数为什么不用呢,直接用链表长度判断不是更好?
稍微自己写了下,加了点功能
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedefint ElemType;
typedef struct Node
{
ElemTypedata;
/*struct Node* next;*/
struct Node* last;
}Node,*LinkList;
Status visit(ElemType c);
Status InitList(LinkList* L);
Status EmptyList(LinkList L);
Status DestroyList(LinkList* L);
Status ClearList(LinkList* L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType* e);
int LocateElem(LinkList L, ElemType e);
Node* LocateElem2(LinkList L, ElemType e);
Status ListInsert(LinkList* L, int i, ElemType e);
Status ListDelete(LinkList* L, int i, ElemType* e);
void CreatListHead(LinkList* L, int n);
void CreatListTail(LinkList* L, int n);
Status ListTraverse(LinkList L);
Status visit(ElemType c)
{
cout << c << " ";
return OK;
}
Status InitList(LinkList *L)
{
*L = new Node;
if(!(*L))
{
return ERROR;
}
(*L)->last = *L;
return OK;
}
Status EmptyList(LinkList L)
{
if (L->last!=L)
{
return FALSE;
}
else
{
return TRUE;
}
}
Status DestroyList(LinkList *L)
{
LinkList p = (*L);
while ((*L)->last!=(*L))
{
p = (*L);
(*L) = (*L)->last;
delete p;
}
return OK;
}
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->last;
while (p!=(*L))
{
q = p->last;
delete p;
p = q;
}
(*L)->last =(*L);
return OK;
}
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->last;
while (p!=L)
{
i++;
p = p->last;
}
return i;
}
Status GetElem(LinkList L,int i, ElemType *e)
{
int j = 1;
LinkList p = L->last;
while (p != L&&j<i )
{
p = p->last;
j++;
}
if (p==L||j>i)
{
return ERROR;
}
*e = p->data;
return OK;
}
int LocateElem(LinkList L, ElemType e)
{
LinkList p = L->last;
int i = 0;
while (p!=L)
{
++i;
if (p->data==e)
{
return i;
}
p = p->last;
}
return i;
}
Node* LocateElem2(LinkList L, ElemType e)
{
LinkList p = L->last;
while (p!=L)
{
if (p->data==e)
{
return p;
}
}
return p;
}
Status ListInsert(LinkList* L, int i, ElemType e)
{
int length = ListLength(*L)+1;
if (i > length||i<1)
{
return ERROR;
}
LinkList p, s;
p = (*L);
int j = 0;
while (j<i-1)
{
++j;
p = p->last;
}
/*if (j>i-1)
{
return ERROR;
}*/
s = new Node;
s->data=e;
s->last = p->last;
p->last = s;
return OK;
}
Status ListDelete(LinkList* L, int i, ElemType* e)
{
int length = ListLength(*L);
if (i>length||i<1)
{
return ERROR;
}
int j=0;
LinkList p, q;
p = *L;
while (p->last!=*L &&j<i-1)
{
p = p->last;
++j;
}
/*if (j > i - 1)
{
return ERROR;
}*/
q = p->last;
p->last = q->last;
*e = q->data;
delete q;
return OK;
}
Status ListTraverse(LinkList L)
{
LinkList p = L->last;
while (p!=L)
{
visit(p->data);
p = p->last;
}
cout << endl;
return OK;
}
void CreatListHead(LinkList* L, int n)
{
*L = new Node;
(*L)->last = *L;
LinkList p;
for (int i=0;i<n;i++)
{
p = new Node;
cin >> p->data;
p->last = (*L)->last;
(*L)->last = p;
}
}
void CreatListTail(LinkList* L, int n)
{
LinkList p, r;
*L = new Node;
(*L)->last = (*L);
r = (*L);
for (int i=0;i<n;i++)
{
p = new Node;
cin >> p->data;
r->last = p;
r = p;
}
r->last = *L;
}
Node* FindLast(Node* L)
{
Node* p = L->last;
while (p->last != L)
{
p = p->last;
}
return p;
}
LinkList Connect(LinkList*La,LinkList*Lb)
{
LinkList La_last, Lb_Last;
LinkList p;
La_last = FindLast(*La);
Lb_Last = FindLast(*Lb);
p = La_last->last;
La_last->last = Lb_Last->last->last;
delete Lb_Last->last;
Lb_Last->last = p;
return Lb_Last;
}
int main()
{
int i;
int j;
int k;
ElemType e;
LinkList L;
LinkList p;
LinkList La, Lb;
i = InitList(&L);
cout << "初始化链表(1.成功 0.失败)"<<i<< endl;
for (j=1;j<=5;j++)
{
ListInsert(&L, 1, j);
}
cout << "表头插入5个元素后,L.data=";
ListTraverse(L);
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
i = ClearList(&L);
cout << "清空L后ListLength(L)=" << ListLength(L) << endl;
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
for (j = 1; j <= 10; j++)
{
ListInsert(&L, j, j);
}
cout << "表尾插入10个元素后,L.data=";
ListTraverse(L);
GetElem(L, 5, &e);
cout << "第5个元素的值为" << e << endl;
e = 9;
i=LocateElem(L, e);
if (i == 0)
{
cout << "没有找到值为" << e << "的元素" << endl;
}
else
{
cout << "值为" << e << "的元素的位序为" << i << endl;
}
/*p=LocateElem2(L, e);
cout << "值为" << e << "元素的地址为" << p<< endl;*/
for (i = 1; i <= 2; i++)
{
ListDelete(&L, 1, &e);
}
cout << "删除第一和第二个元素以后,L.date=";
ListTraverse(L);
k = ListLength(L);
int T = 0;
for (int j=1;j<=k+1;j++)
{
T++;
i = ListDelete(&L, 1, &e);
if(i==ERROR)
{
cout << "删除第" << T << "个元素失败" << endl;
}
else
{
cout << "删除第" << T << "个元素的值为" << e << endl;
}
}
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
cout << "插入元素(头插法)" << endl;
CreatListHead(&La, 5);
cout << "整体创建L的元素(头插法)" << endl;
ListTraverse(La);
cout << "插入元素(尾插法)" << endl;
CreatListTail(&Lb, 5);
cout << "整体创建L的元素(尾插法)" << endl;
ListTraverse(Lb);
L = Connect(&La, &Lb);//Lb合并到La之后
cout << "合并La,Lb后,L=";
ListTraverse(L);
return 0;
}
发现合并La,Lb以后L的元素出错,还有就是p指针接收不了locateElem2()函数的地址. 1094570635 发表于 2022-11-9 22:15
稍微自己写了下,加了点功能
#include
using namespace std;
问题不大
4个问题
1. DestroyList 函数漏了个 delete *L; 为什么会这样呢?
2. 不释放内存,也就是没有调用 DestroyList 函数,为什么会这样呢?
3. date ? or data ?
4. Connect 函数最后返回的结点错了,这里你应该是大意了吧,上面4个步骤都没问题,说明你应该是理解了这个合并的过程了,就是最后返回错结点了
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *last;
} Node, *LinkList;
Status visit(ElemType c);
Status InitList(LinkList *L);
Status EmptyList(LinkList L);
Status DestroyList(LinkList *L);
Status ClearList(LinkList *L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int i, ElemType *e);
int LocateElem(LinkList L, ElemType e);
Node *LocateElem2(LinkList L, ElemType e);
Status ListInsert(LinkList *L, int i, ElemType e);
Status ListDelete(LinkList *L, int i, ElemType *e);
void CreatListHead(LinkList *L, int n);
void CreatListTail(LinkList *L, int n);
Status ListTraverse(LinkList L);
Status visit(ElemType c) {
cout << c << " ";
return OK;
}
Status InitList(LinkList *L) {
*L = new Node;
if(!(*L)) {
return ERROR;
}
(*L)->last = *L;
return OK;
}
Status EmptyList(LinkList L) {
if(L->last != L) {
return FALSE;
} else {
return TRUE;
}
}
Status DestroyList(LinkList *L) {
#if 0
LinkList p = (*L);
while((*L)->last != (*L)) {
p = (*L);
(*L) = (*L)->last;
delete p;
}
// 这里是不是少了这一句?
// 我不知道你为什么就是坚持要这么写,你看出错了吧
// 早跟你说过了,尽量避免直接操作底层结构
// 因为这样很容易出错,代码也不好理解,出了问题调试的时候也很麻烦
// 你就是不听
// 你看这里你就少写了这一句,这样就内存泄露了
delete *L;
#endif
// 你看下面就两行代码,而且逻辑也非常清晰
// 这样写代码怎么可能会出问题呢?
ClearList(L); // 清空链表
delete *L; // 删除头结点
return OK;
}
Status ClearList(LinkList *L) {
LinkList p, q;
p = (*L)->last;
while(p != (*L)) {
q = p->last;
delete p;
p = q;
}
(*L)->last = (*L);
return OK;
}
int ListLength(LinkList L) {
int i = 0;
LinkList p = L->last;
while(p != L) {
i++;
p = p->last;
}
return i;
}
Status GetElem(LinkList L, int i, ElemType *e) {
int j = 1;
LinkList p = L->last;
while(p != L && j < i) {
p = p->last;
j++;
}
if(p == L || j > i) {
return ERROR;
}
*e = p->data;
return OK;
}
int LocateElem(LinkList L, ElemType e) {
LinkList p = L->last;
int i = 0;
while(p != L) {
++i;
if(p->data == e) {
return i;
}
p = p->last;
}
return i;
}
Node *LocateElem2(LinkList L, ElemType e) {
LinkList p = L->last;
while(p != L) {
if(p->data == e) {
return p;
}
}
return p;
}
Status ListInsert(LinkList *L, int i, ElemType e) {
int length = ListLength(*L) + 1;
if(i > length || i < 1) {
return ERROR;
}
LinkList p, s;
p = (*L);
int j = 0;
while(j < i - 1) {
++j;
p = p->last;
}
/*if (j>i-1)
{
return ERROR;
}*/
s = new Node;
s->data = e;
s->last = p->last;
p->last = s;
return OK;
}
Status ListDelete(LinkList *L, int i, ElemType *e) {
int length = ListLength(*L);
if(i > length || i < 1) {
return ERROR;
}
int j = 0;
LinkList p, q;
p = *L;
while(p->last != *L && j < i - 1) {
p = p->last;
++j;
}
/*if (j > i - 1)
{
return ERROR;
}*/
q = p->last;
p->last = q->last;
*e = q->data;
delete q;
return OK;
}
Status ListTraverse(LinkList L) {
LinkList p = L->last;
while(p != L) {
visit(p->data);
p = p->last;
}
cout << endl;
return OK;
}
void CreatListHead(LinkList *L, int n) {
*L = new Node;
(*L)->last = *L;
LinkList p;
for(int i = 0; i < n; i++) {
p = new Node;
cin >> p->data;
p->last = (*L)->last;
(*L)->last = p;
}
}
void CreatListTail(LinkList *L, int n) {
LinkList p, r;
*L = new Node;
(*L)->last = (*L);
r = (*L);
for(int i = 0; i < n; i++) {
p = new Node;
cin >> p->data;
r->last = p;
r = p;
}
r->last = *L;
}
Node *FindLast(Node *L) {
Node *p = L->last;
while(p->last != L) {
p = p->last;
}
return p;
}
LinkList Connect(LinkList *La, LinkList *Lb) {
LinkList La_last, Lb_Last;
LinkList p;
La_last = FindLast(*La);
Lb_Last = FindLast(*Lb);
p = La_last->last;
La_last->last = Lb_Last->last->last;
delete Lb_Last->last;
Lb_Last->last = p;
//return Lb_Last;
return Lb_Last->last;
}
int main() {
int i;
int j;
int k;
ElemType e;
LinkList L;
LinkList La, Lb;
i = InitList(&L);
cout << "初始化链表(1.成功 0.失败)" << i << endl;
for(j = 1; j <= 5; j++) {
ListInsert(&L, 1, j);
}
cout << "表头插入5个元素后,L.data=";
ListTraverse(L);
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
i = ClearList(&L);
cout << "清空L后ListLength(L)=" << ListLength(L) << endl;
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
for(j = 1; j <= 10; j++) {
ListInsert(&L, j, j);
}
cout << "表尾插入10个元素后,L.data=";
ListTraverse(L);
GetElem(L, 5, &e);
cout << "第5个元素的值为" << e << endl;
e = 9;
i = LocateElem(L, e);
if(i == 0) {
cout << "没有找到值为" << e << "的元素" << endl;
} else {
cout << "值为" << e << "的元素的位序为" << i << endl;
}
/*p=LocateElem2(L, e);
cout << "值为" << e << "元素的地址为" << p<< endl;*/
for(i = 1; i <= 2; i++) {
ListDelete(&L, 1, &e);
}
//cout << "删除第一和第二个元素以后,L.date="; // date ?
cout << "删除第一和第二个元素以后,L.date="; // data ?
// date ? or data ?
ListTraverse(L);
k = ListLength(L);
int T = 0;
for(int j = 1; j <= k + 1; j++) {
T++;
i = ListDelete(&L, 1, &e);
if(i == ERROR) {
cout << "删除第" << T << "个元素失败" << endl;
} else {
cout << "删除第" << T << "个元素的值为" << e << endl;
}
}
i = EmptyList(L);
cout << "L是否为空(1.是 0.否)" << i << endl;
cout << "插入元素(头插法)" << endl;
CreatListHead(&La, 5);
cout << "整体创建L的元素(头插法)" << endl;
ListTraverse(La);
cout << "插入元素(尾插法)" << endl;
CreatListTail(&Lb, 5);
cout << "整体创建L的元素(尾插法)" << endl;
ListTraverse(Lb);
DestroyList(&L); // ******************************** 要释放内存的说 **********************
L = Connect(&La, &Lb); // Lb合并到La之后
cout << "合并La,Lb后,L=";
ListTraverse(L);
DestroyList(&L); // ******************************** 要释放内存的说 **********************
return 0;
}
人造人 发表于 2022-11-9 23:39
问题不大
4个问题
1. DestroyList 函数漏了个 delete *L; 为什么会这样呢?
LinkList Connect(LinkList* La, LinkList* Lb) {
LinkList La_last, Lb_Last;
LinkList p;
La_last = FindLast(*La);
Lb_Last = FindLast(*Lb);
p = La_last->last;
La_last->last = Lb_Last->last->last;
delete Lb_Last->last;
Lb_Last->last = p;
return Lb_Last->last;
}最后这个return 是否可以返回*La,或者*Lb?我发现返回*La程序似乎可以运行,*Lb则会引发 异常“ p 是 0xFFFFFFFFFFFFFFF7“
关于这个
p=LocateElem2(L, e);
cout << "值为" << e << "元素的地址为" << p<< endl;,我无法获取e的地址,并且输出cout以后往后的命令也不会显示
1094570635 发表于 2022-11-10 00:33
LinkList Connect(LinkList* La, LinkList* Lb) {
LinkList La_last, Lb_Last;
LinkList p;
你是没有理解了这个合并的过程吗?你上面那4行代码怎么写出来的?
delete Lb_Last->last;
这都把Lb的头结点删除了
多画图,不理解的地方画画图就理解了
‘‘‘
关于这个
p=LocateElem2(L, e);
cout << "值为" << e << "元素的地址为" << p<< endl;,我无法获取e的地址,并且输出cout以后往后的命令也不会显示
’’’
什么?
页:
[1]
2