數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版線性表的單鏈表存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)

1、精品#include <stdio.h>#include <malloc.h>#include <stdlib.h>/*數(shù)據(jù)結(jié)構(gòu) C 語(yǔ)言版線性表的單鏈表存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)P28-31編譯環(huán)境： Dev-C+ 4.9.9.2日期：2011 年2月10日*/typedef int ElemType;/ 線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedef struct LNodeElemType data;/ 數(shù)據(jù)域struct LNode *next;/ 指針域LNode, *LinkList;/ typedef struct LNode *LinkList; /另一種定義

2、LinkList的方法感謝下載載精品/ 構(gòu)造一個(gè)空的線性表 L int InitList(LinkList *L)/*產(chǎn)生頭結(jié)點(diǎn)L,并使 L 指向此頭結(jié)點(diǎn)，頭節(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?，不放?shù)據(jù)的。void * malloc(size_t)這里對(duì)返回值進(jìn)行強(qiáng)制類型轉(zhuǎn)換了，返回值是指向空類型的指針類型。*/(*L) = (LinkList)malloc( sizeof(struct LNode) );if( !(*L) )exit(0);/存儲(chǔ)分配失敗(*L)->next = NULL;/指針域?yàn)榭誶eturn 1;/ 銷毀線性表 L，將包括頭結(jié)點(diǎn)在內(nèi)的所有元素釋放其存儲(chǔ)空間。int Destroy

3、List(LinkList *L)LinkList q;/ 由于單鏈表的每一個(gè)元素是單獨(dú)分配的，所以要一個(gè)一個(gè)的進(jìn)行釋放感謝下載載精品while( *L )q = (*L)->next;free( *L );/ 釋放*L = q;return 1;/*將 L 重置為空表，即將鏈表中除頭結(jié)點(diǎn)外的所有元素釋放其存儲(chǔ)空間，但是將頭結(jié)點(diǎn)指針域置空，這和銷毀有區(qū)別哦。不改變L，所以不需要用指針。*/int ClearList( LinkList L )LinkList p, q;p = L->next;/ p 指向第一個(gè)結(jié)點(diǎn)while( p )/沒到表尾則繼續(xù)循環(huán)感謝下載載精品q = p-&

4、gt;next;free( p ); / 釋放空間p = q;L->next = NULL; /頭結(jié)點(diǎn)指針域?yàn)榭眨湵沓闪艘粋€(gè)空表return 1;/若 L 為空表（根據(jù)頭結(jié)點(diǎn)L->next來(lái)判斷，為空則是空表），則返回1 ，/ 否則返回 0。int ListEmpty(LinkList L)if( L->next ) /非空return 0;elsereturn 1;/ 返回 L 中數(shù)據(jù)元素個(gè)數(shù)。int ListLength(LinkList L)感謝下載載精品int i = 0;LinkList p = L->next; / p指向第一個(gè)結(jié)點(diǎn)while(p) /沒到

5、表尾，則繼續(xù)循環(huán)i+;p=p->next;return i;/算法 2.8 P29/ L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇 個(gè)元素存在時(shí),其值賦給e 并/ 返回 1,否則返回 0 。int GetElem(LinkList L,int i,ElemType *e)int j = 1;/ j為計(jì)數(shù)器LinkList p=L->next;/ p指向第一個(gè)結(jié)點(diǎn)while(p&&j<i)/順指針向后查找,直到 p 指向第 i 個(gè)元素或p 為空p=p->next;j+;感謝下載載精品if(!p|j>i) /第 i 個(gè)元素不存在return 0;*e = p-

6、>data; /取第 i 個(gè)元素return 1;/返回 L 中第 1 個(gè)與 e 滿足關(guān)系compare()的數(shù)據(jù)元素的位序。/ 若這樣的數(shù)據(jù)元素不存在 ,則返回值為 0int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType)int i=0;LinkList p=L->next;while(p) /將鏈表的每一個(gè)元素進(jìn)行對(duì)比i+;if(compare(p->data,e) /找到這樣的數(shù)據(jù)元素return i;p=p->next;感謝下載載精品return 0;/若 cur_e 是 L 的

7、數(shù)據(jù)元素 ,且不是第一個(gè),則用 pre_e 返回它的前驅(qū),/ 返回 1;否則操作失敗 ,pre_e 無(wú)定義 ,返回 -1int PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)LinkList q,p=L->next;/ p指向第一個(gè)結(jié)點(diǎn)while(p->next)/ p所指結(jié)點(diǎn)有后繼q=p->next; / q為 p 的后繼if(q->data=cur_e)*pre_e=p->data;return 1;p=q; / p向后移return -1;感謝下載載精品/若 cur_e 是 L 的數(shù)據(jù)元素，且不是最后

8、一個(gè)，則用next_e 返回它的后繼，/ 返回 1;否則操作失敗， next_e 無(wú)定義，返回 -1int NextElem(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L->next; / p指向第一個(gè)結(jié)點(diǎn)while(p->next) / p所指結(jié)點(diǎn)有后繼if(p->data=cur_e)*next_e=p->next->data;return 1;p=p->next;return -1;/ 算法 2.9 P30/在帶頭結(jié)點(diǎn)的單鏈線性表L 中第 i 個(gè)位置之前插入元素eint ListInse

9、rt(LinkList *L,int i,ElemType e)int j=0;感謝下載載精品LinkList p=*L,s;while(p && j<i-1) /尋找第 i-1 個(gè)結(jié)點(diǎn)p=p->next;j+;if(!p | j>i-1) / i小于 1 或者大于表長(zhǎng)return 0;s=(LinkList)malloc(sizeof(struct LNode); /生成新結(jié)點(diǎn)s->data=e; /插入 L 中s->next=p->next;p->next=s;return 1;/ 算法 2.10 P30/ 在帶頭結(jié)點(diǎn)的單鏈線性表

10、L 中，刪除第 i 個(gè)元素 ,并由 e 返回其值int ListDelete(LinkList *L, int i,ElemType *e)int j = 0;LinkList p=*L,q;while(p->next&&j<i-1) /尋找第 i 個(gè)結(jié)點(diǎn) ,并令 p 指向其前趨感謝下載載精品p=p->next;j+;if(!p->next|j>i-1) /刪除位置不合理return 0;q=p->next; /刪除并釋放結(jié)點(diǎn)p->next=q->next;*e=q->data;free(q);return 1;/依次對(duì) L

11、 的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()int ListTraverse(LinkList L,void(*vi)(ElemType)LinkList p=L->next;/ 對(duì)所有元素調(diào)用函數(shù) vi while(p)vi(p->data);感謝下載載精品p=p->next;printf("n");return 1;/ 在按非降序排列的線性表 L 中按非降序插入新的數(shù)據(jù)元素 e void InsertAscend(LinkList L,ElemType e)LinkList q=L,p=L->next;while(p&&e>p->

12、data)q=p;p=p->next;q->next=(LinkList)malloc(sizeof(struct LNode); / e插在 q 后q->next->data=e;q->next->next=p;感謝下載載精品/按非升序排列的線性表L 中按非升序插入新的數(shù)據(jù)元素evoid InsertDescend(LinkList L,ElemType e)LinkList q=L,p=L->next;while(p&&e<p->data)q=p;p=p->next;q->next=(LinkList)mal

13、loc(sizeof(struct LNode); / e插在 q 后q->next->data=e;q->next->next=p;/ L 的頭部插入新的數(shù)據(jù)元素 e,作為鏈表的第一個(gè)元素int HeadInsert(LinkList L,ElemType e)LinkList s;s=(LinkList)malloc(sizeof(struct LNode); /生成新結(jié)點(diǎn)s->data=e; /給結(jié)點(diǎn)賦值s->next=L->next; /插在表頭感謝下載載精品L->next=s;return 1;/在 L 的尾部插入新的數(shù)據(jù)元素e,作為鏈

14、表的最后一個(gè)元素int EndInsert(LinkList L,ElemType e)LinkList p=L;while(p->next) /使 p 指向表尾元素p=p->next;p->next=(LinkList)malloc(sizeof(struct LNode); /在表尾生成新結(jié)點(diǎn)p->next->data=e; /給新結(jié)點(diǎn)賦值p->next->next=NULL; /表尾return 1;/刪除 L 的第一個(gè)數(shù)據(jù)元素，并由e 返回其值int DeleteFirst(LinkList L,ElemType *e)LinkList p=L

15、->next;if(p)感謝下載載精品*e=p->data;L->next=p->next;free(p);return 1;elsereturn 0;/刪除 L 的最后一個(gè)數(shù)據(jù)元素，并用e 返回其值int DeleteTail(LinkList L,ElemType *e)LinkList p=L,q;if(!p->next) /鏈表為空return 0;while(p->next)q=p;p=p->next;q->next=NULL; /新尾結(jié)點(diǎn)的next域設(shè)為 NULL*e=p->data;感謝下載載精品free(p);return

16、1;/ 刪除表中值為 e 的元素，并返回 1 ；如無(wú)此元素，則返回 0 int DeleteElem(LinkList L,ElemType e)LinkList p=L,q; while(p)q=p->next; if(q&&q->data=e)p->next=q->next; free(q);return 1;p=q;return 0;感謝下載載精品/ 用 e 取代表 L 中第 i 個(gè)元素的值int ReplaceElem(LinkList L,int i,ElemType e)LinkList p=L;int j=0;/ 找到第 i 個(gè)元素的位置給

17、 p while(p->next && j<i)j+; p=p->next;if(j=i)p->data=e; return 1;else / 表中不存在第 i 個(gè)元素 return 0;/ 按非降序建立 n 個(gè)元素的線性表int CreatAscend(LinkList *L,int n)感謝下載載精品int j;LinkList p,q,s;if(n<=0)return 0;InitList(L);printf("請(qǐng)輸入 %d 個(gè)元素 :（空格） n",n);s=(LinkList)malloc(sizeof(struct

18、LNode); /第一個(gè)結(jié)點(diǎn)scanf("%d",&s->data);s->next=NULL;(*L)->next=s;for( j=1;j<n;j+)s=(LinkList)malloc(sizeof(struct LNode); /其余結(jié)點(diǎn)scanf("%d",&s->data);q=*L;p=(*L)->next;while(p&&p->data<s->data) / p沒到表尾，且所指元素值小于新值q=p;p=p->next; /指針后移感謝下載載精品s

19、->next=q->next; /元素插在 q 的后面q->next=s;return 1;/ 按非升序建立 n 個(gè)元素的線性表int CreatDescend(LinkList *L,int n)int j;LinkList p,q,s;if(n<=0)return 0;InitList(L);printf("請(qǐng)輸入 %d 個(gè)元素 :（空格） n",n);s=(LinkList)malloc(sizeof(struct LNode); /第一個(gè)結(jié)點(diǎn)scanf("%d",&s->data);s->next=NU

20、LL;(*L)->next=s;for( j=1;j<n;j+)s=(LinkList)malloc(sizeof(struct LNode); /其余結(jié)點(diǎn)感謝下載載精品scanf("%d",&s->data);q=*L;p=(*L)->next;while(p&&p->data>s->data) / p沒到表尾，且所指元素值大于新值q=p;p=p->next; /指針后移s->next=q->next; /元素插在 q 的后面q->next=s;return 1;/ 返回表頭元素的值

21、int GetFirstElem(LinkList L,ElemType *e)LinkList p=L->next;/ 第一個(gè)結(jié)點(diǎn)給pif(!p)/空表return 0;else /非空表*e=p->data;感謝下載載精品return 1;/算法 2.11 P30/逆位序 ( 插在表頭 )輸入 n 個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表Lvoid CreateList(LinkList *L,int n)int i;LinkList p;/ 先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表，相當(dāng)于初始化單鏈表*L=(LinkList)malloc(sizeof(struct LNode);(*L)

22、->next=NULL;printf("請(qǐng)輸入 %d 個(gè)數(shù)據(jù) n",n);for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(struct LNode); /生成新結(jié)點(diǎn)scanf("%d",&p->data); /輸入元素值p->next=(*L)->next; /插入到表頭(*L)->next=p;感謝下載載精品/ 正位序 ( 插在表尾 )輸入 n 個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表void CreateList2(LinkList *L,int n)int i;LinkLi

23、st p,q;/ 先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表，相當(dāng)于初始化單鏈表*L=(LinkList)malloc(sizeof(struct LNode); /生成頭結(jié)點(diǎn)(*L)->next=NULL;q=*L;printf("請(qǐng)輸入 %d 個(gè)數(shù)據(jù) n",n);for(i=1;i<=n;i+)p=(LinkList)malloc(sizeof(struct LNode);scanf("%d",&p->data);q->next=p;q=q->next;感謝下載載精品p->next=NULL;/*用單鏈表重寫算法 2.2

24、 供參考已知線性表La 和 Lb 中的數(shù)據(jù)元素按值非遞減排列。歸并 La 和 Lb 得到新的線性表Lc,Lc 的數(shù)據(jù)元素也按值非遞減排列void MergeList(LinkList La,LinkList Lb,LinkList *Lc)int i=1,j=1,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while(i<=La_len&&j<=Lb_len) /表 La 和表 Lb 均非空GetElem(La,i,&

25、;ai);GetElem(Lb,j,&bj);感謝下載載精品if(ai<=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;while(i<=La_len) /表 La 非空且表Lb 空GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while( j<=Lb_len) /表 Lb 非空且表La 空GetElem(Lb,j+,&bj);ListInsert(Lc,+k,bj);感謝下載載精品*/ 算法 2.12 P31/ 已知單鏈線性表 La 和 Lb 的元素按值

26、非遞減排列。/歸并 La 和 Lb 得到新的單鏈線性表Lc， Lc 的元素也按值非遞減排列void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)LinkList pa=La->next,pb=(*Lb)->next,pc;*Lc=pc=La; /用 La 的頭結(jié)點(diǎn)作為L(zhǎng)c 的頭結(jié)點(diǎn)while(pa&&pb)if(pa->data <= pb->data)pc->next=pa;*Lc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->n

27、ext;感謝下載載精品pc->next=pa ? pa : pb; /插入剩余段free(*Lb); /釋放 Lb 的頭結(jié)點(diǎn)Lb=NULL;/ 判斷是否相等的函數(shù)， Union() 用到int equal(ElemType c1,ElemType c2)if(c1=c2)return 1;elsereturn 0;/算法 2.1/將所有在線性表Lb 中但不在La 中的數(shù)據(jù)元素插入到La 中void Union(LinkList La,LinkList Lb)ElemType e;感謝下載載精品int La_len,Lb_len;int i;La_len=ListLength(La); /

28、求線性表的長(zhǎng)度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i+)GetElem(Lb,i,&e); /取 Lb 中第 i 個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal) / La中不存在和e 相同的元素 ,則插入之ListInsert(&La,+La_len,e);/ 數(shù)據(jù)元素判定函數(shù) (相等為 1,否則為 0) int comp(ElemType c1,ElemType c2)if(c1=c2) return 1;elsereturn 0;感謝下載載精品void visit(ElemType c)printf(&

29、quot;%d ",c);int main()LinkList L, La, Lb, Lc;ElemType e, e0, d;int i, j, n, k;/ 初始化一個(gè)單鏈表i=InitList(&L);/ 通過(guò)插入操作創(chuàng)建一個(gè)單鏈表for( j=1;j<=5;j+)i=ListInsert(&L,1,j);/ 調(diào)用 visit 函數(shù)，對(duì)單鏈表進(jìn)行遍歷printf("在 L 的表頭依次插入1 5 后： L=");ListTraverse(L,visit); /依次對(duì)元素調(diào)用visit() ，輸出元素的值感謝下載載精品/ 判斷單鏈表是否為空

30、i=ListEmpty(L);printf("L是否空： i=%d(1: 是 0:否 )n",i);/ 清空單鏈表i=ClearList(L);printf("清空 L 后： L=");ListTraverse(L,visit);/ 判斷單鏈表是否為空i=ListEmpty(L);printf("L是否空： i=%d(1: 是 0:否 )n",i);/ 再次通過(guò)插入操作創(chuàng)建一個(gè)單鏈表for( j=1;j<=10;j+)ListInsert(&L,j,j);printf("在 L 的表尾依次插入1 10 后： L

31、=");ListTraverse(L,visit);/ 取得單鏈表的第 5 個(gè)元素GetElem(L,5,&e);感謝下載載精品printf("第 5 個(gè)元素的值為：%dn",e);/ 在單鏈表中找到和 j 滿足 comp 函數(shù)關(guān)系的元素for( j=0;j<=1;j+)k=LocateElem(L,j,comp);if(k)printf("第 %d 個(gè)元素的值為%dn",k,j);elseprintf("沒有值為 %d 的元素 n",j);/ 找到某個(gè)元素的前驅(qū)for( j=1;j<=2;j+) /測(cè)試

32、頭兩個(gè)數(shù)據(jù)GetElem(L,j,&e0); /把第 j 個(gè)數(shù)據(jù)賦給e0i=PriorElem(L,e0,&e); /求 e0 的前驅(qū)if(i=-1)printf("元素 %d 無(wú)前驅(qū) n",e0);elseprintf("元素 %d 的前驅(qū)為： %dn",e0,e);感謝下載載精品/ 找到某個(gè)元素的后繼for( j=ListLength(L)-1;j<=ListLength(L);j+)/測(cè)試最后兩個(gè)數(shù)據(jù)GetElem(L,j,&e0); /把第 j 個(gè)數(shù)據(jù)賦給e0i=NextElem(L,e0,&e); /求 e

33、0 的后繼if(i=-1)printf("元素 %d 無(wú)后繼 n",e0);elseprintf("元素 %d 的后繼為： %dn",e0,e);/ 求單鏈表的表長(zhǎng)k=ListLength(L); / k為表長(zhǎng)/ 刪除操作for( j=k+1;j>=k;j-)i=ListDelete(&L,j,&e); /刪除第 j 個(gè)數(shù)據(jù)if(i=0)printf("刪除第 %d 個(gè)數(shù)據(jù)失敗 n",j);else感謝下載載精品printf("刪除的元素為：%dn",e);printf("依次輸出L

34、 的元素： ");ListTraverse(L,visit);/ 銷毀單鏈表DestroyList(&L);printf("銷毀 L 后： L=%unn",L);printf("按非降序建立n 個(gè)元素的線性表L,請(qǐng)輸入元素個(gè)數(shù)n: ");scanf("%d",&n);CreatAscend(&L,n);printf("依次輸出L 的元素： ");ListTraverse(L,visit);/ 按非降序插入元素 10 InsertAscend(L,10);printf("按

35、非降序插入元素10 后，線性表L 為： ");ListTraverse(L,visit);/在 L 的頭部插入12感謝下載載精品HeadInsert(L,12);/ 在 L 的尾部插入 9 EndInsert(L,9);printf(" 在 L 的頭部插入 12 ，尾部插入 9 后，線性表 L 為： "); ListTraverse(L,visit);i=GetFirstElem(L,&e);printf("第 1 個(gè)元素是 : %dn",e);printf("請(qǐng)輸入要?jiǎng)h除的元素的值: ");scanf("

36、%d",&e);i=DeleteElem(L,e);if(i)printf("成功刪除 %d!n",e);elseprintf("不存在元素 %d!n",e);printf("線性表 L 為： ");ListTraverse(L,visit);printf("請(qǐng)輸入要取代的元素的序號(hào)元素的新值 : ");scanf("%d%d",&n,&e);ReplaceElem(L,n,e);感謝下載載精品printf("線性表 L 為： ");List

37、Traverse(L,visit);DestroyList(&L);printf("銷毀 L 后 ,按非升序重新建立n 個(gè)元素的線性表L,請(qǐng)輸入 ""元素個(gè)數(shù)n(>2): ");scanf("%d",&n);CreatDescend(&L,n);printf("依次輸出L 的元素： ");ListTraverse(L,visit);/ 按非升序插入元素 10InsertDescend(L,10);printf("按非升序插入元素10 后，線性表L 為： ");Lis

38、tTraverse(L,visit);printf("請(qǐng)輸入要?jiǎng)h除的元素的值: ");scanf("%d",&e);i=DeleteElem(L,e);if(i)printf("成功刪除 %d!n",e);感謝下載載精品elseprintf("不存在元素 %d!n",e);printf("線性表 L 為： ");ListTraverse(L,visit);DeleteFirst(L,&e);DeleteT ail(L,&d);printf("刪除表頭元素%d 和

39、表尾元素 %d 后 ,線性表 L 為： ",e,d);ListTraverse(L,visit);printf("n");/測(cè)試算法2.11n = 3;CreateList2(&La,n);/正位序輸入n 個(gè)元素的值printf("正位創(chuàng)建后La=");/輸出鏈表La 的內(nèi)容ListTraverse(La,visit);CreateList(&Lb,n);/逆位序輸入n 個(gè)元素的值printf("逆位創(chuàng)建后Lb=");/輸出鏈表Lb 的內(nèi)容ListTraverse(Lb,visit);DestroyList(&La);DestroyList(&Lb);感謝下載載精品/ 測(cè)試算法 2.12/ 初始化一個(gè)單鏈表 Lai=InitList(&La);/ 通過(guò)插入操作創(chuàng)建一個(gè)單鏈表for( j=2;j<=10;j+=2)i=ListInsert(&La,1,j);printf("La="); /輸出鏈表 La 的內(nèi)容ListTraverse(La,visit