#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;
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-11-8 20:45:09
置顶卡
千斤顶
显身卡
发表于 2022-11-8 20:58:43
楼主
