數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版循環(huán)鏈表表示和實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu) C 語(yǔ)言版 循環(huán)鏈表表示和實(shí)現(xiàn) .txt37 真誠(chéng)是美酒，年份越久越醇香濃烈；真誠(chéng)是 焰火，在高處綻放才愈顯美麗；真誠(chéng)是鮮花，送之于人，手有余香。 /*數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版循環(huán)鏈表表示和實(shí)現(xiàn)P35 編譯環(huán)境： Dev-C+ 4.9.9.2 日期： 2011年 2月 10日*/#include <stdio.h>#include <malloc.h> #include <stdlib.h> typedef int ElemType;/ 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) typedef struct LNodeElemType data;struct LNode *

2、next;LNode, *LinkList;/ 要好好區(qū)分什么是頭結(jié)點(diǎn) (*L)->next) ，尾結(jié)點(diǎn) (*L) ，以及第一個(gè)結(jié)/點(diǎn)(*L)-> next-next,設(shè)立尾指針的單循環(huán)鏈表(頭尾相接，即頭結(jié)點(diǎn)/ 與尾結(jié)點(diǎn)是一樣的，它們都沒(méi)數(shù)據(jù)域 ./ 構(gòu)造一個(gè)空的循環(huán)鏈表 Lint InitList_CL(LinkList *L)/ 產(chǎn)生頭結(jié)點(diǎn) , 并使 L 指向此頭結(jié)點(diǎn)*L = (LinkList)malloc(sizeof(struct LNode);if(!*L) exit(0);/ 指針域指向頭結(jié)點(diǎn)，這樣就構(gòu)成了一個(gè)循環(huán)，空表循環(huán)，*L 為表尾(*L)->next

3、= *L;return 1;/ 銷毀循環(huán)鏈表 Lint DestroyList_CL(LinkList *L)LinkList q, p = (*L)->next; / p 指向頭結(jié)點(diǎn)while(p != *L)/ 沒(méi)到表尾， *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 指向頭結(jié)點(diǎn)p=(*L)->next;/ p 指向第一個(gè)結(jié)點(diǎn)while(p!=*L

4、)/ 沒(méi)到表尾 q=p->next; free(p); p=q;(*L)->next=*L; / 頭結(jié)點(diǎn)指針域指向自身 return 1;/ 若 L 為空表，則返回 1，否則返回 0 int ListEmpty_CL(LinkList L)if(L->next=L) / 空 return 1;else return 0;/ 返回 L 中數(shù)據(jù)元素個(gè)數(shù)int ListLength_CL(LinkList L)int i=0;LinkList p=L->next; / p 指向頭結(jié)點(diǎn) while(p!=L) / 沒(méi)到表尾i+; p=p->next;return i;/當(dāng)

5、第i個(gè)元素存在時(shí)，其值賦給e并返回1,否則返回0int GetElem_CL(LinkList L,int i,ElemType *e)int j=1; / 初始化 ,j 為計(jì)數(shù)器LinkList p=L->next->next; / p指向第一個(gè)結(jié)點(diǎn)if(i<=0|i>ListLength_CL(L) /第 i 個(gè)元素不存在return 0;while(j<i)/ 順指針向后查找 , 直到 p 指向第 i 個(gè)元素 p=p->next;j+;*e=p->data; / 取第 i 個(gè)元素 return 1;/ 返回 L 中第 1 個(gè)與 e 滿足關(guān)系 co

6、mpare() 的數(shù)據(jù)元素的位序。/ 若這樣的數(shù)據(jù)元素不存在，則返回值為 0int LocateElem_CL(LinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0;LinkList p=L->next->next; / p指向第一個(gè)結(jié)點(diǎn)while(p!=L->next)i+; if(compare(p->data,e) /滿足關(guān)系return i;p=p->next;return 0;/ 若 cur_e 是 L 的數(shù)據(jù)元素，且不是第一個(gè)，則用 pre_e 返回它的前驅(qū) int PriorEl

7、em_CL(LinkList L,ElemType cur_e,ElemType *pre_e)LinkList q,p=L->next->next; / p指向第一個(gè)結(jié)點(diǎn)q=p->next;while(q!=L->next) / p 沒(méi)到表尾 if(q->data=cur_e) *pre_e=p->data;return 1;p=q; q=q->next;return 0;/ 若 cur_e 是 L 的數(shù)據(jù)元素 , 且不是最后一個(gè) , 則用 next_e 返回它的后繼 int NextElem_CL(LinkList L,ElemType cur_e

8、,ElemType *next_e)LinkList p=L->next->next; / p 指向第一個(gè)結(jié)點(diǎn) while(p!=L) / p 沒(méi)到表尾if(p->data=cur_e)*next_e=p->next->data; return 1; p=p->next;return 0;/ 在 L 的第 i 個(gè)位置之前插入元素 eint ListInsert_CL(LinkList *L,int i,ElemType e)LinkList p=(*L)->next,s; / p指向頭結(jié)點(diǎn)int j=0;if(i<=0|i>ListLeng

9、th_CL(*L)+1) / 無(wú)法在第 i 個(gè)元素之前插入 return 0;while(j<i-1) / 尋找第 i-1 個(gè)結(jié)點(diǎn)p=p->next; j+; s=(LinkList)malloc(sizeof(struct LNode); /生成新結(jié)點(diǎn)s->data=e; /插入 L 中s->next=p->next;p->next=s;if(p=*L) / 改變尾結(jié)點(diǎn)*L=s;return 1;/刪除L的第i個(gè)元素，并由e返回其值int ListDelete_CL(LinkList *L,int i,ElemType *e)LinkList p=(*L)

10、->next，q; / p指向頭結(jié)點(diǎn)int j=0;if(i<=0|i>ListLength_CL(*L) /第 i 個(gè)元素不存在return 0;while(j<i-1) / 尋找第 i-1 個(gè)結(jié)點(diǎn) p=p->next;j+;q=p->next; / q 指向待刪除結(jié)點(diǎn) p->next=q->next;*e=q->data;if(*L=q) / 刪除的是表尾元素*L=p;free(q); / 釋放待刪除結(jié)點(diǎn) return 1;/ 依次對(duì) L 的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()int ListTraverse_CL(LinkList L，vo

11、id(*vi)(ElemType)LinkList p=L->next->next;/ p指向第一個(gè)結(jié)點(diǎn)while(p!=L->next) vi(p->data); p=p->next;printf("n");return 1;/兩個(gè)僅設(shè)表尾指針的循環(huán)鏈表的合并(教科書(shū)P35圖2.13 )void MergeList_CL(LinkList *La，LinkList Lb)LinkList p=Lb->next; Lb->next=(*La)->next; (*La)->next=p->next;free(p);*

12、La=Lb;int compare(ElemType c1,ElemType c2)if(c1=c2)return 1;elsereturn 0;void visit(ElemType c)printf("%d ",c);int main()LinkList L, La, Lb;ElemType e;int i, j, n;i=InitList_CL(&L); / 初始化單循環(huán)鏈表 L printf(" 初始化單循環(huán)鏈表 L i=%d (1: 初始化成功 )n",i); i=ListEmpty_CL(L);printf("L 是否空 i

13、=%d(1: 空 0: 否 )n",i);ListInsert_CL(&L,1,3); / 在 L 中依次插入 3,5ListInsert_CL(&L,2,5);i=GetElem_CL(L,1,&e);j=ListLength_CL(L);printf("L中數(shù)據(jù)元素個(gè)數(shù)=%d，第1個(gè)元素的值為%d n",j,e);printf("L中的數(shù)據(jù)元素依次為： ");ListTraverse_CL(L,visit);PriorElem_CL(L,5,&e); / 求元素 5 的前驅(qū)printf("5前面的元

14、素的值為%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(" 不存在值為 5 的元素 n");i=ListDelete_CL(&L,2,&e);printf(”刪除L的第2

15、個(gè)元素：n");if(i)printf(”刪除的元素值為d,現(xiàn)在L中的數(shù)據(jù)元素依次為：”,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;/ 創(chuàng)建單循環(huán)鏈表In

16、itList_CL(&La);for(i=1;i<=n;i+)ListInsert_CL(&La,i,i);printf("La="); /輸出鏈表 La 的內(nèi)容ListTraverse_CL(La,visit);/ 創(chuàng)建單循環(huán)鏈表InitList_CL(&Lb);for(i=1;i<=n;i+)ListInsert_CL(&Lb,1,i*2);printf("Lb="); /輸出鏈表 Lb 的內(nèi)容ListTraverse_CL(Lb,visit);MergeList_CL(&La,Lb);printf("La+Lb="); /輸出合并后的鏈表的內(nèi)容ListTraverse_CL(La,visit);system("pause");return 0;/*輸出效果： 初始化單循環(huán)鏈表 L i=1 （1: 初始化成功 ）L 是否空 i=1（1: 空 0: 否