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

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

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

3、)LinkListq,p=(*L)->next;/p指向頭結(jié)點while(p!=*L)/沒到表尾，*L為表尾q=p->next;free(p);p=q;)free(*L);* L=NULL;return1;)/將L重置為空表intClearList_CL(LinkList*L)(LinkListp,q;* L=(*L)->next;/L指向頭結(jié)點p=(*L)->next;/p指向第一個結(jié)點while(p!=*L)/沒到表尾(q=p->next;free(p);p=q;)(*L)->next=*L;/頭結(jié)點指針域指向自身return1;)/若L為空表，則返回1

4、,否則返回0intListEmpty_CL(LinkListL)(if(L->next=L)/空return1;elsereturn0;)/返回L中數(shù)據(jù)元素個數(shù)intListLength_CL(LinkListL)(inti=0;LinkListp=L->next;/p指向頭結(jié)點while(p!=L)/沒到表尾(i+;p=p->next;)returni;/當(dāng)?shù)趇個元素存在時，其值賦給e并返回1,否則返回0intGetElem_CL(LinkListL,inti,ElemType*e)(intj=1;/初始化，j為計數(shù)器LinkListp=L->next->nex

5、t;/p指向第一個結(jié)點if(i<=0|i>ListLength_CL(L)第i個元素不存在return0;while(j<i)(/順指針向后查找，直到p指向第i個元素p=p->next;j+;*e=p->data;/取第i個元素return1;/返回L中第1個與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。/若這樣的數(shù)據(jù)元素不存在，則返回值為0intLocateElem_CL(LinkListL,ElemTypee,int(*compare)(ElemType,ElemType)(inti=0;LinkListp=L->next->next;/p指向第一

6、個結(jié)點while(p!=L->next)(i+;if(compare(p->data,e)/滿足關(guān)系returni;p=p->next;return0;/若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)intPriorElem_CL(LinkListL,ElemTypecur_e,ElemType*pre_e)(LinkListq,p=L->next->next;/p指向第一個結(jié)點q=p->next;while(q!=L->next)/p沒到表尾(if(q->data=cur_e)(*pre_e=p->data;retu

7、rn1;)p=q;q=q->next;)return0;)/若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼intNextElem_CL(LinkListL,ElemTypecur_e,ElemType*next_e)(LinkListp=L->next->next;/p指向第一個結(jié)點while(p!=L)/p沒到表尾(if(p->data=cur_e)(*next_e=p->next->data;return1;)p=p->next;)return0;)/在L的第i個位置之前才f入元素eintListInsert_CL(Lin

8、kList*L,inti,ElemTypee)(LinkListp=(*L)->next,s;/p指向頭結(jié)點intj=0;if(i<=0|i>ListLength_CL(*L)+1)/無法在第i個元素之前插入return0;while(j<i-1)/尋找第i-1個結(jié)點(p=p->next;j+;)s=(LinkList)malloc(sizeof(structLNode);/生成新結(jié)點s->data=e;/插入L中s->next=p->next;p->next=s;if(p=*L)/改變尾結(jié)點*L=s;return1;/刪除L的第i個元素，

9、并由e返回其值intListDelete_CL(LinkList*L,inti,ElemType*e)(LinkListp=(*L)->next,q;/p指向頭結(jié)點intj=0;if(i<=0|i>ListLength_CL(*L)/第i個元素不存在return0;while(j<i-1)/尋找第i-1個結(jié)點(p=p->next;j+;q=p->next;/q指向待刪除結(jié)點p->next=q->next;*e=q->data;if(*L=q)/刪除的是表尾元素*L=p;free(q);/釋放待刪除結(jié)點return1;/依次對L的每個數(shù)據(jù)元素

10、調(diào)用函數(shù)vi()intListTraverse_CL(LinkListL,void(*vi)(ElemType)(LinkListp=L->next->next;/p指向第一個結(jié)點while(p!=L->next)(vi(p->data);p=p->next;printf("n");return1;/兩個僅設(shè)表尾指針的循環(huán)鏈表的合并(教科書P35圖2.13)voidMergeList_CL(LinkList*La,LinkListLb)(LinkListp=Lb->next;Lb->next=(*La)->next;(*La)

11、->next=p->next;free(p);*La=Lb;intcompare(ElemTypec1,ElemTypec2)(if(c1=c2)return1;elsereturn0;voidvisit(ElemTypec)(printf("%d",c);intmain()(LinkListL,La,Lb;ElemTypee;inti,j,n;i=InitList_CL(&L);/初始化單循環(huán)鏈表Lprintf("初始化單循環(huán)鏈表Li=%d(1:初始化成功)n",i);i=ListEmpty_CL(L);printf("L

12、是否空i=%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ù)元素個數(shù)=%d第1個元素的值為dn",j,e);printf("L中的數(shù)據(jù)元素依次為：");ListTraverse_CL(L,visit);PriorElem_CL(L,5,&e);求元素5的前驅(qū)printf("5前面的元素的值為%dn",e);Nex

13、tElem_CL(L,3,&e);求元素3的后繼printf("3后面的元素的值為%dn",e);printf("L是否空%d(1:空0:否)n",ListEmpty_CL(L);j=LocateElem_CL(L,5,compare);if(j)printf("L的第dj元素為5。n",j);elseprintf("不存在值為5的元素n");i=ListDelete_CL(&L,2,&e);printf("刪除L的第2個元素：n");if(i)printf("

14、刪除的元素值為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)鏈表InitList_CL(&La);for(i=1;i&

15、lt;=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");return0;)/