《数据结构C语言版 循环链表表示和实现》由会员分享，可在线阅读，更多相关《数据结构C语言版 循环链表表示和实现（8页珍藏版）》请在金锄头文库上搜索。
1、数据构造 C 语言版 循环链表表示和实现.txt37 真诚是美酒，年份越久越醇香浓烈；真诚是焰火，在高处绽放才愈显秀丽；真诚是鲜花，送之于人，手有余香。/*数据构造C 语言版 循环链表表示和实现P35编译环境：Dev-C+ 4.9.9.2日期：2021 年 2 月 10 日*/#include #include #include typedef int ElemType;/ 线性表的单链表存储构造typedef struct LNodeElemType data; struct LNode *next;LNode, *LinkList;/ 要好好区分什么是头结点(*L)-next)，尾结点(*
2、L)，以及第一个结/ 点(*L)-next-next,设立尾指针的单循环链表(头尾相接，即头结点/ 与尾结点是一样的，它们都没数据域./ 构造一个空的循环链表L int InitList_CL(LinkList *L)/ 产生头结点,并使L 指向此头结点*L = (LinkList)malloc(sizeof(struct LNode); if(!*L)exit(0);/ 指针域指向头结点，这样就构成了一个循环，空表循环，*L 为表尾(*L)-next = *L; return 1;/ 销毁循环链表Lint DestroyList_CL(LinkList *L)LinkList q,p = (
3、*L)-next; / p 指向头结点while(p != *L) / 没到表尾，*L 为表尾q = p-next; free(p);p = q;free(*L);*L = NULL;return 1;/ 将L 重置为空表int ClearList_CL(LinkList *L)LinkList p, q;*L=(*L)-next; / L 指向头结点p=(*L)-next;/ p 指向第一个结点while(p!=*L)/ 没到表尾q=p-next; free(p); p=q;(*L)-next=*L; / 头结点指针域指向自身return 1;/ 假设L 为空表，那么返回 1，否那么返回 0
4、 int ListEmpty_CL(LinkList L)if(L-next=L) / 空return 1; elsereturn 0;/ 返回L 中数据元素个数int ListLength_CL(LinkList L)int i=0;LinkList p=L-next; / p 指向头结点while(p!=L) / 没到表尾i+;p=p-next;return i;/ 当第i 个元素存在时,其值赋给e 并返回 1,否那么返回 0 int GetElem_CL(LinkList L,int i,ElemType *e)int j=1; / 初始化,j 为计数器LinkList p=L-next
5、-next; / p 指向第一个结点if(iListLength_CL(L) / 第 i 个元素不存在return 0; while(jnext;j+;*e=p-data; / 取第i 个元素return 1;/ 返回L 中第 1 个与e 满足关系compare()的数据元素的位序。/ 假设这样的数据元素不存在，那么返回值为0int LocateElem_CL(LinkList L,ElemType e,int(*compare)(ElemType,ElemType)int i=0;LinkList p=L-next-next; / p 指向第一个结点while(p!=L-next)i+;if
6、(compare(p-data,e) / 满足关系return i; p=p-next;return 0;/ 假设cur_e 是L 的数据元素，且不是第一个，那么用pre_e 返回它的前驱. int PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)LinkList q,p=L-next-next; / p 指向第一个结点q=p-next;while(q!=L-next) / p 没到表尾if(q-data=cur_e)*pre_e=p-data;return 1;p=q;q=q-next;return 0;/ 假设cur_e 是L
7、的数据元素,且不是最终一个,那么用next_e 返回它的后继. int NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L-next-next; / p 指向第一个结点while(p!=L) / p 没到表尾if(p-data=cur_e)*next_e=p-next-data; return 1;p=p-next;return 0;/ 在L 的第i 个位置之前插入元素eint ListInsert_CL(LinkList *L,int i,ElemType e)LinkList p=(*L)-next,s;
8、/ p 指向头结点int j=0;if(iListLength_CL(*L)+1) / 无法在第i 个元素之前插入return 0;while(jnext; j+;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点s-data=e; / 插入L 中s-next=p-next; p-next=s;if(p=*L) / 转变尾结点*L=s; return 1;/ 删除L 的第i 个元素,并由 e 返回其值int ListDelete_CL(LinkList *L,int i,ElemType *e)LinkList p=(*L)-next,q; / p
9、 指向头结点int j=0;if(iListLength_CL(*L) / 第 i 个元素不存在return 0;while(jnext; j+;q=p-next; / q 指向待删除结点p-next=q-next;*e=q-data;if(*L=q) / 删除的是表尾元素*L=p;free(q); / 释放待删除结点return 1;/ 依次对L 的每个数据元素调用函数vi()int ListTraverse_CL(LinkList L,void(*vi)(ElemType)LinkList p=L-next-next;/ p 指向第一个结点while(p!=L-next)vi(p-data
10、); p=p-next;printf(“n“); return 1;/ 两个仅设表尾指针的循环链表的合并教科书P35 图 2.13 void MergeList_CL(LinkList *La,LinkList Lb)LinkList p=Lb-next; Lb-next=(*La)-next; (*La)-next=p-next; free(p);*La=Lb;int compare(ElemType c1,ElemType c2)if(c1=c2)return 1; elsereturn 0;void visit(ElemType c)printf(“%d “,c);int main()L
11、inkList L, La, Lb;ElemType e;int i, j, n;i=InitList_CL(&L); / 初始化单循环链表Lprintf(“初始化单循环链表L i=%d (1:初始化成功)n“,i); i=ListEmpty_CL(L);printf(“L 是否空 i=%d(1:空 0:否)n“,i); ListInsert_CL(&L,1,3); / 在L 中依次插入 3,5 ListInsert_CL(&L,2,5); i=GetElem_CL(L,1,&e);j=ListLength_CL(L);printf(“L 中数据元素个数=%d,第 1 个元素的值为%d。n“,
12、j,e); printf(“L 中的数据元素依次为：“); ListTraverse_CL(L,visit);PriorElem_CL(L,5,&e); / 求元素 5 的前驱printf(“5 前面的元素的值为%d。n“,e); NextElem_CL(L,3,&e); / 求元素 3 的后继printf(“3 后面的元素的值为%d。n“,e);printf(“L 是否空 %d(1:空 0:否)n“,ListEmpty_CL(L); j=LocateElem_CL(L,5,compare);if(j)printf(“L 的第%d 个元素为 5。n“,j); elseprintf(“不存在值为
13、 5 的元素n“); i=ListDelete_CL(&L,2,&e);printf(“删除L 的第 2 个元素：n“); if(i)printf(“删除的元素值为%d,现在L 中的数据元素依次为：“,e); ListTraverse_CL(L,visit);elseprintf(“删除不成功！n“);printf(“清空L：%d(1: 成功)n“,ClearList_CL(&L);printf(“清空L 后，L 是否空：%d(1:空 0:否)n“,ListEmpty_CL(L); printf(“销毁L：%d(1: 成功)n“,DestroyList_CL(&L);n = 5;/创立单循环链表InitList_CL(&La); for(i=1;i=n;i+)ListInsert_CL(&La,i,i); printf(“La=“); / 输出链表La 的内容ListTraverse_CL(La,visit);/创立单循环链表InitList_CL(&Lb); for(i=1;i=n;i+)ListInsert_CL(&Lb,1,i*2); printf(“Lb=“); / 输出链表Lb 的内容ListTraverse_CL(Lb,visit);MergeList_CL(&La,Lb);printf(“La+Lb=“); / 输出合并后
