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

1、/*數(shù)據(jù)結(jié)構(gòu)C語言版 雙向鏈表表示和實現(xiàn)P36-P37 編譯環(huán)境：Dev-C+ 4.9.9.2日期： 2011年2月10日 */#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef int ElemType;/ 線性表的雙向鏈表存儲結(jié)構(gòu) typedef struct DuLNodeElemType data;/數(shù)據(jù)域struct DuLNode *prior,*next;/前驅(qū)后繼指針DuLNode,*DuLinkList;/ 產(chǎn)生空的雙向循環(huán)鏈表Lint InitList(DuLin

2、kList *L) *L=(DuLinkList)malloc(sizeof(DuLNode);/ *L指向頭結(jié)點(diǎn)if(*L)/ 將頭結(jié)點(diǎn)的前驅(qū)后繼都指向頭結(jié)點(diǎn)，這樣構(gòu)成了一個空表(*L)->next=(*L)->prior=*L;return 1;elsereturn 0;/ 銷毀雙向循環(huán)鏈表Lint DestroyList(DuLinkList *L)DuLinkList q,p=(*L)->next; / p指向第一個結(jié)點(diǎn) while(p!=*L) / p沒到表頭 q=p->next;free(p);p=q;free(*L);*L=NULL;return 1;/

3、將L重置為空表int ClearList(DuLinkList L)DuLinkList q,p=L->next; / p指向第一個結(jié)點(diǎn) while(p!=L) / p沒到表頭 q=p->next;free(p);p=q;L->next=L->prior=L; / 頭結(jié)點(diǎn)的兩個指針域均指向自身，構(gòu)成空表 return 1;/ 若L為空表（空表就是頭結(jié)點(diǎn)的前驅(qū)后繼都指向頭結(jié)點(diǎn)），則返回1，否則返回0 int ListEmpty(DuLinkList L)if(L->next=L&&L->prior=L)return 1;elsereturn 0

4、;/ 返回L中數(shù)據(jù)元素個數(shù)int ListLength(DuLinkList L)int i=0;DuLinkList p=L->next; / p指向第一個結(jié)點(diǎn) while(p!=L) / p沒到表頭 i+;p=p->next;return i;/ 當(dāng)?shù)趇個元素存在時,其值賦給e并返回1,否則返回0int GetElem(DuLinkList L,int i,ElemType *e)int j=1; / j為計數(shù)器 DuLinkList p=L->next; / p指向第一個結(jié)點(diǎn) while(p!=L&&j<i) / 順指針向后查找,直到p指向第i個元

5、素或p指向頭結(jié)點(diǎn) p=p->next;j+;if(p=L|j>i) / 第i個元素不存在 return 0;*e=p->data; / 取第i個元素 return 1;/ 返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 / 若這樣的數(shù)據(jù)元素不存在，則返回值為0 int LocateElem(DuLinkList L,ElemType e,int(*compare)(ElemType,ElemType)int i=0;DuLinkList p=L->next; / p指向第1個元素 while(p!=L)i+;if(compare(p->data,e

6、) / 找到這樣的數(shù)據(jù)元素 return i;p=p->next;return 0;/ 若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)int PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)DuLinkList p=L->next->next; / p指向第2個元素 while(p!=L) / p沒到表頭 if(p->data=cur_e)*pre_e=p->prior->data;return 1;p=p->next;return 0;/ 若cur_e是L的數(shù)據(jù)元素，且

7、不是最后一個，則用next_e返回它的后繼int NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)DuLinkList p=L->next->next; / p指向第2個元素 while(p!=L) / p沒到表頭 if(p->prior->data=cur_e)*next_e=p->data;return 1;p=p->next;return 0;/ 在雙向鏈表L中返回第i個元素的位置指針(算法2.18、2.19要調(diào)用的函數(shù)) DuLinkList GetElemP(DuLinkList L,in

8、t i)int j;DuLinkList p=L;for(j=1;j<=i;j+)p=p->next;return p;/ 改進(jìn)算法2.18 P36/ 在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個位置之前插入元素e，/ i的合法值為1i表長+1 int ListInsert(DuLinkList L,int i,ElemType e)DuLinkList p,s;if(i<1|i>ListLength(L)+1) / i值不合法 return 0;p=GetElemP(L,i-1); / 在L中確定第i-1個元素的位置指針p if(!p) / p=NULL,即第i-1個元素不存

9、在 return 0;s=(DuLinkList)malloc(sizeof(DuLNode);if(!s)return 0;s->data=e; / 在第i-1個元素之后插入 s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;return 1;/ 算法2.19 P37 / 刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個元素,i的合法值為1i表長+1 int ListDelete(DuLinkList L,int i,ElemType *e) DuLinkList p;if(i<1|i>Li

10、stLength(L) / i值不合法 return 0;p=GetElemP(L,i); / 在L中確定第i個元素的位置指針p if(!p) / p=NULL,即第i個元素不存在 return 0;*e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return 1;/ 由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā),正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit() void ListTraverse(DuLinkList L,void(*visit)(ElemType)DuLinkList p

11、=L->next; / p指向頭結(jié)點(diǎn) while(p!=L)visit(p->data);p=p->next;printf("n");/ 由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā),逆序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit()void ListTraverseBack(DuLinkList L,void(*visit)(ElemType)DuLinkList p=L->prior; / p指向尾結(jié)點(diǎn) while(p!=L)visit(p->data);p=p->prior;printf("n");/ 數(shù)據(jù)元素判定函數(shù)(判定相等)int

12、 compare(ElemType c1,ElemType c2) if(c1=c2)return 1;elsereturn 0;void vd(ElemType c) / ListTraverse()調(diào)用的函數(shù)(類型一致) printf("%d ",c);int main()DuLinkList L;int i,n;int j;ElemType e;InitList(&L);for(i=1;i<=5;i+)ListInsert(L,i,i); / 在第i個結(jié)點(diǎn)之前插入i printf("正序輸出鏈表：");ListTraverse(L,v

13、d); / 正序輸出 printf("逆序輸出鏈表：");ListTraverseBack(L,vd); / 逆序輸出 n=2;ListDelete(L,n,&e); / 刪除并釋放第n個結(jié)點(diǎn) printf("刪除第%d個結(jié)點(diǎn)，值為%d，其余結(jié)點(diǎn)為：",n,e);ListTraverse(L,vd); / 正序輸出 printf("鏈表的元素個數(shù)為%dn",ListLength(L);printf("鏈表是否空：%d(1:是 0:否)n",ListEmpty(L);ClearList(L); / 清空鏈表

14、printf("清空后，鏈表是否空：%d(1:是 0:否)n",ListEmpty(L);for(i=1;i<=5;i+)ListInsert(L,i,i); / 重新插入5個結(jié)點(diǎn) ListTraverse(L,vd); / 正序輸出 n=3;j=GetElem(L,n,&e); / 將鏈表的第n個元素賦值給e if(j)printf("鏈表的第%d個元素值為%dn",n,e);elseprintf("不存在第%d個元素n",n);n=4;i=LocateElem(L,n,compare);if(i)printf("等于%d的元素是第%d個n",n,i);elseprintf("沒有等于%d的元素n",n);j=PriorElem(L,n,&e);if(j)printf("%d的前驅(qū)是%dn",n,e);elseprintf("不存在%d的前驅(qū)n",n);j=NextElem(L,n,&e);if(j)printf("%d的后繼是%dn",n,e);elseprintf("不存在%d的