清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言

《清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言》由會(huì)員分享，可在線閱讀，更多相關(guān)《清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言（51頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、/* cl.h （程序名）*/ #in elude #in elude #in elude #in elude vmalloc .h> /* malloc() 等 */ /* INT MAX等 */ #in clude /* EOF(=AZ 或 F6),NULL */ #in clude #in clude #in clude /* atoi() */ /* eof() */ /* floor(),ceil(),abs

2、() */ #in clude /* exit() */ /*函數(shù)結(jié)果狀態(tài)代碼*/ #defi ne TRUE 1 #defi ne FALSE 0 #defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1 /* #define OVERFLOW -2 因?yàn)樵?math.h中已定義 OVERFLO的值為3,故去掉此行*/ typedef int Status ; /* Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如 OK等*/ typedef int Boolean ; /* Boolea

3、n 是布爾類型，其值是 TRUE或 FALSE */ /* algo2-1.c 實(shí)現(xiàn)算法2.1的程序*/ #include "cl.h" typedef int ElemType; #include "c2-1.h" /*c2-1.h 線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu) */ #define LIST_INIT_SIZE 10 /*線性表存儲(chǔ)空間的初始分配量 */ #define LISTINCREMENT 2/* 線性表存儲(chǔ)空間的分配增量 */ typedef struct { ElemType *elem; /* 存儲(chǔ)空間基址 */ int length ; /* 當(dāng)前長(zhǎng)度

4、 */ int listsize ; /* 當(dāng)前分配的存儲(chǔ)容量 (以sizeof( ElemType)為單位)*/ } SqList ; #include "bo2-1.c" /* bo2-1.c 順序表示的線性表(存儲(chǔ)結(jié)構(gòu)由c2-1.h定義)的基本操作(12個(gè))*/ Status InitList (SqList *L) /* 算法 2.3 */ { /*操作結(jié)果：構(gòu)造一個(gè)空的順序線性表 */ (*L). elem=( ElemType*) malloc (LIST_INIT_SIZE *sizeof ( ElemType)); if (!( *L). elem) exit

5、(OVERFLOW);/* 存儲(chǔ)分配失敗 */ (*L). length =0; /* 空表長(zhǎng)度為 0 */ (*L). listsize =LIST_INIT_SIZE ; /* 初始存儲(chǔ)容量 */ return OK; } Status DestroyList (SqList *L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：銷毀順序線性表 L */ free(( *L). elem); (*L). elem=NULL; (*L). length =0; (*L). listsize =0; return OK; } Stat

6、us ClearList (SqList *L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：將 L重置為空表*/ (*L). length =0; return OK; } Status ListEmpty (SqList L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：若 L為空表，則返回 TRUE否則返回 FALSE */ if (L. length ==0) return TRUE; else return FALSE; } int List Length (SqList L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：返回 L中

7、數(shù)據(jù)元素個(gè)數(shù)*/ return L. length ; } Status Get Elem( SqList L, int i, ElemType *e) { /*初始條件：順序線性表 L已存在，1 < i w ListLength(L) */ /*操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值*/ if (i<1||i>L. length ) exit (ERROR); *e=*(L. elem+i-1); return OK; } int Locate Elem( SqList L, ElemType e, Status (*compare)( ElemType, ElemT

8、ype)) { /*初始條件：順序線性表 L已存在，compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為 0) */ /*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 */ /* 若這樣的數(shù)據(jù)元素不存在，則返回值為 0。算法2.6 */ ElemType *p; int i=1; /* i的初值為第1個(gè)元素的位序*/ p=L. elem; /* p的初值為第1個(gè)元素的存儲(chǔ)位置*/ while (i<=L. length &&!compare(*p++,e)) ++i; if (i<=L. length ) return i; else r

9、eturn 0; } Status Prior Elem( SqList L, ElemType cur_e, ElemType *pre_e) { /*初始條件：順序線性表 L已存在*/ /*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/ /* 否則操作失敗，pre_e無(wú)定義*/ int i=2; ElemType *p=L. elem+1; while (i<=L. length &&*p!=cur_e) { p++； i++； } if (i>L. length ) return INFEASIBLE; else {

10、*pre_e=*--p; return OK; } } Status Next Elem(SqList L, ElemType cur_e, ElemType *next_e) { /*初始條件：順序線性表 L已存在*/ /*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼, */ /* 否則操作失敗，next_e無(wú)定義*/ int i=1; ElemType *p=L. elem; while (i

11、NFEASIBLE; else { *n ext_e=*++p; return OK; } } Status List In sert( SqList *L, i nt i, ElemType e) /* 算法 2.4 */ { /*初始條件：順序線性表 L已存在，1 < i < ListLength(L)+1 */ /*操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素 e, L的長(zhǎng)度加1 */ ElemType *n ewbase,*q,*p; if (i<1||i>( *L). length +1) /* i 值不合法 */ return ERROR; if ((

12、*L). length >=(*L). listsize ) /*當(dāng)前存儲(chǔ)空間已滿，增加分配*/ { n ewbase=( ElemType *)realloc(( *L). elem,(( *L). listsize +LISTINCREMENT)Sizeof (ElemType)); if (!newbase) exit (OVERFLOW); /* 存儲(chǔ)分配失敗 */ ( *L). elem =newbase; /* 新基址 */ (*L). listsize +=LISTINCREMENT;/* 增加存儲(chǔ)容量 */ } q=( *L). elem+i-1; /* q

13、為插入位置 */ for (p=( *L). elem+(*L). length -1;p>=q;--p) /* 插入位置及之后的元素右移 */ *(p+1)=*p; *q=e; /* 插入 e */ ++( *L). length ; /* 表長(zhǎng)增 1 */ return OK; } Status ListDelete( SqList *L, int i, ElemType *e) /* 算法 2.5 */ { /*初始條件：順序線性表 L已存在，1 < i < ListLength(L) */ /*操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用 e返回其值，L的長(zhǎng)度減1 */

14、ElemType *p,*q; if (i<1||i>( *L). length ) /* i 值不合法 */ return ERROR; p=( *L). elem+i-1; /* p為被刪除元素的位置 */ *e=*p; /*被刪除元素的值賦給 e */ q=( *L). elem+(*L). length -1; /* 表尾元素的位置 */ for什+p;p<=q;++p) /*被刪除元素之后的元素左移 */ *(p-1)=*p; (*L). length --; /* 表長(zhǎng)減 1 */ return OK; } Status ListTraverse( SqLis

15、t L,void(*vi)( ElemType*)) { /*初始條件：順序線性表 L已存在*/ /*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/ /* vi() 的形參加& ,表明可通過(guò)調(diào)用 vi()改變?cè)氐闹?/ ElemType *p; int i; p=L. elem; for (i=1;i<=L. length ;i++) vi(p++); pr int f("\n"); return OK; } Status equal( ElemType c1, ElemType c2) { /*判斷是否相等的函數(shù)， Union

16、()用到*/ if (c1==c2) return TRUE; else return FALSE; } void Union( SqList *La, SqList Lb) /* 算法 2.1 */ { /*將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到 La中*/ ElemType e; int La_len,Lb_len; int i; La_len=List Length (*L a); /* 求線性表的長(zhǎng)度 */ Lb_len=List Length (Lb); for (i=1;i<=Lb_len;i++) { Get Elem(Lb,i,&e);

17、/*取Lb中第i個(gè)數(shù)據(jù)元素賦給 e */ if (!Locate Elem( *La,e,equal)) /* La 中不存在和e相同的元素，則插入之*/ ListI nsert(La,++La_le n, e); } } void pr int (ElemType *c) { pr int f("%d ",*c); } void mai n() { SqList La,Lb; Status i; int j; i= In itList (&La); if (i==1) /* 創(chuàng)建空表 La成功*/ for (j=1;j<=5;j++) /*在表La中插入5個(gè)元素

18、*/ i=List In sert(&La,j,j); pr int f("La= "); /* 輸出表 La 的內(nèi)容 */ ListTraverse(La,pr int ); InitList (&Lb); /*也可不判斷是否創(chuàng)建成功 */ for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/ i=ListI nsert(&Lb,j,2*j); pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */ ListTraverse(Lb,pr int ); Un io n(&La,Lb); pr int f("new La= "); /* 輸出新

19、表 La 的內(nèi)容 */ ListTraverse(La,pr int );} /* algo2-2.c 實(shí)現(xiàn)算法 22的程序*/ #include "cl.h" typedef int ElemType; #include "c2-1.h" #include "bo2-1.c" void MergeList( SqList La, SqList Lb, SqList *Lc) /* 算法 2.2 */ { /*已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。 */ /*歸并La和Lb得到新的線性表 Lc,Lc的數(shù)據(jù)元素也按值非遞減排列 */ int i=

20、1,j=1,k=O; int La_len,Lb_len; ElemType ai,bj; InitList (Lc); /* 創(chuàng)建空表 Lc */ La_len=List Length (La); Lb_len=List Length (Lb); while (i<=La_len&&j<=Lb_len) /* 表 La 和表 Lb 均非空 */ { Get Elem(La,i, &ai); Get Elem(Lb,j, &bj); if (ai<=bj) { List In sert(Lc,++k,ai); ++i; } else { ListI nsert

21、(Lc,++k,bj); ++j; } } while (i<=La_len) /* 表 La 非空且表 Lb 空 */ { Get Elem(La,i++, &ai); List In sert(Lc,++k,ai); } while (j<=Lb_len) /* 表 Lb 非空且表 La 空 */ { Get Elem(Lb,j++, &bj); ListI nsert(Lc,++k,bj); } } void pr int (ElemType *c) { pr int f("%d ",*c); } void mai n() { SqList La

22、,Lb,Lc; int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20}; In itList (&La); /* 創(chuàng)建空表 La */ for (j=1;j<=4;j++) /*在表La中插入 4個(gè)兀素*/ ListI nsert(&La,j,a[j-1]); pr int f("La="); /* 輸出表 La的內(nèi)容 */ ListTraverse(La,pr int ); In itList (&Lb); /* 創(chuàng)建空表 Lb */ for (j=1;j<=7;j++) /

23、* 在表Lb中插入7個(gè)元素*/ ListI nsert(&Lb,j,b[j-1]); pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */ ListTraverse(Lb,pr int ); MergeList(La,Lb,&Lc); pr int f("Lc= "); /* 輸出表 Lc 的內(nèi)容 */ ListTraverse(Lc,pr int ); } /* algo2-3.c 實(shí)現(xiàn)算法2.7的程序*/ #include "cl.h" typedef int ElemType; #include "c2-1.h" #include "bo2-1.c

24、" void MergeList( SqList La, SqList Lb, SqList *Lc) /* 算法 2.7 */ { /*已知順序線性表 La和Lb的元素按值非遞減排列。 */ /*歸并La和Lb得到新的順序線性表 Lc,Lc的元素也按值非遞減排列 */ ElemType *pa,*pa_last,*pb,*pb_last,*pc; pa=La. elem; pb=Lb. elem; Lc (*Lc). listsize =(*Lc). length =La. length +Lb. length ; /* 不用 InitList() 創(chuàng)建空表 */ pc=

25、( *Lc). elem =( ElemType *) malloc (( *Lc). listsize * sizeof (ElemType)); if (!( *Lc). elem) /* 存儲(chǔ)分配失敗 */ exit (OVERFLOW); pa_last=La. elem+La. length -1; pb_last=Lb. elem+Lb. length -1; while (pa<=pa_last&&pb<=pb_last) /* 表 La 和表 Lb 均非空 */ { /*歸并*/ if (*pa<=*pb) *pc++=*pa++; else *pc++=*

26、pb++; while (pa<=pa_last) *pc++=*pa++; /* while (pb<=pb_last) *pc++=*pb++; /* /*表La非空且表Lb空*/ 插入La的剩余元素*/ /* 表Lb非空且表 La空*/ 插入Lb的剩余元素*/ void pr int (ElemType *c) { pr int f("%d ",*c); } void mai n() { SqList La,Lb,Lc; int j; InitList (&La); /* 創(chuàng)建空表 La */ for (j=1;j<=5;j++) /* 在表La中插

27、入5個(gè)元素*/ ListI nsert (&La,j,j); pr int f("La= "); /* 輸出表 La 的內(nèi)容 */ ListTraverse(La,pr int ); InitList (&Lb); /* 創(chuàng)建空表 Lb */ for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/ ListI nsert(&Lb,j,2*j); pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */ ListTraverse(Lb,pr int ); MergeList(La,Lb,&Lc); pr int f("Lc= "); /* 輸出表

28、Lc 的內(nèi)容 */ ListTraverse(Lc,pr int ); } /* algo2-4.c 修改算法2.7的第一個(gè)循環(huán)語(yǔ)句中的條件語(yǔ)句為開(kāi)關(guān)語(yǔ)句，且當(dāng) */ /* *pa=*pb 時(shí)，只將兩者中之一插入 Lc。此操作的結(jié)果和算法 2.1相同*/ #include "c1.h" typedef int ElemType; #include "c2-1.h" #include "bo2-1.c" int comp( ElemType c1, ElemType c2) { int i; if (c1

29、lse i=-1; return i; } void MergeList( SqList La, SqList Lb, SqList *Lc) { /*另一種合并線性表的方法(根據(jù)算法 2.7下的要求修改算法 2.7 ) */ ElemType *pa,*pa_last,*pb,*pb_last,*pc; pa=La. elem; pb=Lb. elem; (*Lc). listsize =La. length +Lb. length ; /* 此句與算法 2.7 不同 */ pc=( *Lc). elem =( ElemType *) malloc (( *Lc). li

30、stsize * sizeof (ElemType)); if (!( *Lc). elem) exit (OVERFLOW); pa_last=La. elem+La. length -1; pb_last=Lb. elem+Lb. length -1; while (pa<=pa_last&&pb<=pb_last) /* 表 La 和表 Lb 均非空 */ switch(comp(*pa,*pb)) /* 此句與算法 2.7 不同 */ { case 0: pb++; case 1:*pc++=*pa++; break; case -1:*pc++=*pb++; }

31、 while (pa<=pa_last) /* 表 La 非空且表 Lb 空 */ *pc++=*pa++; while (pb<=pb_last) /* 表 Lb 非空且表 La 空 */ *pc++=*pb++; (*Lc). length =pc-( *Lc). elem; /* 加此句 */ } void pr int (ElemType *c) { pr int f("%d ",*c); } void mai n() { SqList La,Lb,Lc; int j; InitList (&La); /* 創(chuàng)建空表 La */ for (j=1；j<=5

32、;j++) /* 在表La中插入5個(gè)元素*/ ListI nsert (&La,j,j); pr int f("La= "); /* 輸出表 La 的內(nèi)容 */ ListTraverse(La,pr int ); InitList (&Lb); /* 創(chuàng)建空表 Lb */ for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/ ListI nsert(&Lb,j,2*j); pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */ ListTraverse(Lb,pr int ); MergeList(La,Lb,&Lc); pr int f("

33、Lc= "); /* 輸出表 Lc 的內(nèi)容 */ ListTraverse(Lc,pr int ); } /* algo2-5.c 實(shí)現(xiàn)算法 2.11、2.12 的程序 */ #include "cl.h" typedef int ElemType; #include "c2-2.h" /* c2-2.h 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) */ struct LNode { ElemType data; struct LNode *n ext; }； typedef struct LNode *L inkList; /* 另一種定義 LinkList 的方法 */ #inclu

34、de "bo2-2.c" /* bo2-2.c 單鏈表線性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè))*/ Status In itList (Lin kList *L) { /*操作結(jié)果：構(gòu)造一個(gè)空的線性表 L */ *L=(LinkList) malloc ( sizeof ( struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn)，并使 L 指向此頭結(jié)點(diǎn) */ if (! *L) /*存儲(chǔ)分配失敗*/ exit (OVERFLOW); (*L)->next=NULL; /* 指針域?yàn)榭?*/ return OK; } Status DestroyList (Li n

35、kList *L) { /*初始條件：線性表 L已存在。操作結(jié)果：銷毀線性表 L */ Lin kList q; while (*L) { q=( *L)-> next; free( *L); *L=q; } return OK; } Status ClearList (LinkList L) /* 不改變 L */ { /*初始條件：線性表 L已存在。操作結(jié)果：將 L重置為空表*/ Lin kList p,q; p=L-> next; /* p指向第一個(gè)結(jié)點(diǎn) */ while (p) /* 沒(méi)到表尾*/ { q=p->n ext; free(p); p=

36、q; } L-> next=NULL; /*頭結(jié)點(diǎn)指針域?yàn)榭?*/ return OK; } Status ListEmpty (LinkList L) { /*初始條件：線性表 L已存在。操作結(jié)果：若 L為空表，則返回TRUE否則返回FALSE */ if (L->next) /* 非空 */ return FALSE; else return TRUE; } int List Length (LinkList L) { /*初始條件：線性表 L已存在。操作結(jié)果：返回 L中數(shù)據(jù)元素個(gè)數(shù)*/ int i=0; Lin kList p=L-> next; /* p

37、 指向第一個(gè)結(jié)點(diǎn) */ while (p) /* 沒(méi)到表尾*/ { i++; p=p->n ext; } return i; } Status Get Elem(LinkList L, int i, ElemType *e) /* 算法 2.8 */ { /* L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)?i個(gè)元素存在時(shí)，其值賦給e并返回OK,否則 返回 ERROR */ int j=1; /* j 為計(jì)數(shù)器*/ Lin kList p=L-> next; /* p 指向第一個(gè)結(jié)點(diǎn) */ while (p&&j

38、 p=p->n ext; j++; } if (!p||j>i) /*第i個(gè)元素不存在*/ return ERROR; *e=p->data; /* 取第 i 個(gè)元素 */ return OK; } int Locate Elem(LinkList L, ElemType e, Status (*compare)( ElemType, ElemType)) { /*初始條件：線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) */ /*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。 */ /* 若這樣的數(shù)據(jù)元素不存在,則返回值

39、為0 */ int i=0; Lin kList p=L->n ext; while (p) { i++； if (compare(p->data,e)) /*找到這樣的數(shù)據(jù)元素 */ return i; p=p->n ext; } return 0; } Status Prior Elem(LinkList L, ElemType cur_e, ElemType *pre_e) { /*初始條件：線性表L已存在*/ /*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/ /* 返回OK;否則操作失敗,pre_e無(wú)定義，返回INF

40、EASIBLE */ Lin kList 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 OK; } p=q; /* p 向后移*/ } return INFEASIBLE; } Status Next Elem(LinkList L, ElemType cur_e, ElemType *next_e) { /*初始條件：線性表 L已存在*/

41、/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼, */ /* 返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE */ Lin kList p=L-> next; /* p 指向第一個(gè)結(jié)點(diǎn) */ while (p->next) /* p所指結(jié)點(diǎn)有后繼 */ { if (p->data==cur_e) { *n ext_e=p->n ext->data; return OK; } p=p->n ext; } return INFEASIBLE; } Status List In sert(Li nkList

42、L, int i, ElemType e) /* 算法 2.9。不改變 L */ { /*在帶頭結(jié)點(diǎn)的單鏈線性表 L中第i個(gè)位置之前插入元素 e */ int j=0; Lin kList p=L,s; while (p&&jn ext; j++; } if (!p||j>i-1) /* i 小于1或者大于表長(zhǎng)*/ return ERROR; s=(LinkList) malloc (sizeof (struct LNode)); /* 生成新結(jié)點(diǎn) */ s->data=e; /* 插入 L 中 */ s-

43、>n ext=p->n ext; p_>n ext=s; return OK; } Status ListDelete(LinkList L, int i, ElemType *e) /* 算法 2.10。不改變 L */ { /*在帶頭結(jié)點(diǎn)的單鏈線性表 L中，刪除第i個(gè)元素，并由e返回其值*/ int j=0; Lin kList p=L,q; while (p->next&&jn ext; j++; } if (!p->next||j>i-1) /* 刪除位置不合理 */ return ERRO

44、R; q=p->next; /*刪除并釋放結(jié)點(diǎn)*/ p_>n ext=q _>n ext; *e=q_>data; free(q); return OK; } Status ListTraverse(LinkList L,void(*vi)( ElemType)) /* vi 的形參類型為 ElemType，與bo2-1.c中相應(yīng)函數(shù)的形參類型 ElemType&不同*/ { /*初始條件：線性表 L已存在*/ /*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/ Lin kList p=L->n ext; while (p) {

45、 vi(p->data); p=p->n ext; } pr int f("\n"); return OK; } void CreateList(LinkList *L, int n) /* 算法 2.11 */ { /*逆位序(插在表頭)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 L */ int i; Lin kList p; *L=(LinkList) malloc (sizeof (struct LNode)); (*L)-> next=NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */ pr int f("請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n); for (i=n;

46、i>0;__i) { p=(LinkList) malloc (sizeof (struct LNode)); /* 生成新結(jié)點(diǎn) */ scanf("%d",&p->data); /* 輸入元素值 */ p->next=( *L )->next; /* 插入到表頭 */ ( *L)->n ext=p; } } void CreateList2(LinkList *L, int n) { /*正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 */ int i; Lin kList p,q; *L=(LinkList) malloc (sizeof (stru

47、ct LNode)); /* 生成頭結(jié)點(diǎn) */ (*L)-> next=NULL; q= *L; pr int f("請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n); for (i=1;i<=n;i++) { p=(LinkList) malloc (sizeof (struct LNode)); scan f("%d",&p->data); q_>n ext=p; q=q_>n ext; } p-> next=NULL; } void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法 2.12 */ { /*已知單鏈線性表

48、La和Lb的元素按值非遞減排列。 */ /*歸并La和Lb得到新的單鏈線性表 Lc，Lc的元素也按值非遞減排列 */ LinkList pa=La->next,pb=( *L b)->next,pc; *Lc=pc=La; /*用La的頭結(jié)點(diǎn)作為 Lc的頭結(jié)點(diǎn)*/ while (pa&&pb) if (pa->data<=pb->data) { pc- >n ext=pa; pc=pa; pa=pa->n ext; } else { pc- >n ext=pb; pc=pb; pb=pb->n ext; } pc->next=pa?pa:pb; /* 插入剩余

49、段 */ free( *Lb); /*釋放Lb的頭結(jié)點(diǎn)*/ Lb=NULL; } void visit( ElemType c) /* ListTraverse() 調(diào)用的函數(shù)(類型要一致)*/ { pr int f("%d ”,c); } void mai n() { int n=5; Lin kList La,Lb,Lc; pr int f("按非遞減順序，"); CreateList2(&La,n); /*正位序輸入 n個(gè)元素的值*/ pr int f("La="); /*輸出鏈表La的內(nèi)容*/ ListTraverse(La,visit); pr int

50、 f("按非遞增順序，"); CreateList(&Lb,n); /* 逆位序輸入 n個(gè)元素的值*/ pr int f("Lb="); /*輸出鏈表Lb的內(nèi)容*/ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并 La和Lb,得到新表Lc */ pr int f("Lc="); /*輸出鏈表Lc的內(nèi)容*/ ListTraverse(Lc,visit); } /* algo2-6.c 利用單鏈表結(jié)構(gòu)處理教科書(shū)圖 2.1(學(xué)生健康登記表)*/ #include "c1.h" #defi ne NAMELEN

51、8 /* 姓名最大長(zhǎng)度 */ #defi ne CLASSLEN 4 /* 班級(jí)名最大長(zhǎng)度 */ struct stud /* 記錄的結(jié)構(gòu)*/ { char name[NAMELEN+1]; long num; char sex; int age; char Class[CLASSLEN+1]; int health; }; typedef struct stud ElemType; /*鏈表結(jié)點(diǎn)元素類型為結(jié)構(gòu)體 */ #include "c2-2.h" char sta[3][9]={" 健康"，” 一般"，”神經(jīng)衰弱"}; /*健康狀況(3類)*/ FILE *

52、fp; Status InitList (LinkList *L) /* 拷自 bo2-2.c */ { /*操作結(jié)果：構(gòu)造一個(gè)空的線性表 L */ *L=(LinkList) malloc (sizeof (struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn)，并使 L 指向此頭結(jié)點(diǎn) */ if (! *L) /*存儲(chǔ)分配失敗*/ exit (OVERFLOW); (*L)->next=NULL; /* 指針域?yàn)榭?*/ return OK; } Status ListTraverse(LinkList L,void(*vi)( ElemType)) /* 拷自 bo2-2.

53、c */ { /*初始條件：線性表 L已存在*/ /*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/ Lin kList p=L->n ext; while (p) { vi(p->data); p=p->n ext; } pr int f("\n"); return OK; } void In sertAsce nd(Li nkList L, ElemType e) /* 此函數(shù)是由 bo2-9.c 中的同名函數(shù)改寫(xiě) */ { /*按學(xué)號(hào)非降序插入*/ Lin kList q=L,p=L->n ext; while (p&

54、&e.num>p->data.num) { q=p； p=p->n ext; } q->next=(LinkList) malloc (sizeof (struct LNode)); /* 插在 q 后 */ q->n ext->data=e; q_>n ext- >n ext=p; } void Print (struct stud e) { /*顯示記錄e的內(nèi)容*/ pr int f("%-8s %6ld",e.name,e.num); if (e.sex=='m') pr int f("男"); else pr int f("女"); pr int f("%

55、5d %-4s",e.age,e.Class); pr int f("%9s\n",sta[e.health]); } void Readln( struct stud *e) { /*由鍵盤(pán)輸入結(jié)點(diǎn)信息 */ pr int f("請(qǐng)輸入姓名(<=%d個(gè)字符):",NAMELEN); sca nf("%s",e->n ame); pr int f("請(qǐng)輸入學(xué)號(hào):"); sca nf("%ld", &e-> nu m); pr int f("請(qǐng)輸入性別(m:男f:女):"); sca nf("%*c%c", &e->sex); pr int f("請(qǐng)輸入年齡:"); sc

56、a nf("%d", &e->age); pr int f("請(qǐng)輸入班級(jí)(<=%d個(gè)字符):",CLASSLEN); sca nf("%s",e->Class); pr int f("請(qǐng)輸入健康狀況(0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); sca nf("%d", &e->health); } void WriteToFile( struct stud e) { /*將結(jié)點(diǎn)信息寫(xiě)入fp指定的文件*/ fwrite(&e, sizeof (struct stud),1,fp); } Status ReadFromFile( struct

57、 stud *e) { /*由fp指定的文件讀取結(jié)點(diǎn)信息到 e */ int i; i=fread(e, sizeof (struct stud),1,fp); if (i==1) /* 讀取文件成功*/ return OK; else return ERROR; } Status FindFromNum(LinkList L,long num,LinkList *p,LinkList *q) { /*查找表中學(xué)號(hào)為num的結(jié)點(diǎn)，如找到,q指向此結(jié)點(diǎn),p指向q的前驅(qū),*/ /*并返回TRUE如無(wú)此元素，則返回FALSE */ *p=L; while (*p) {

58、*q=(*p)-> next; if (*q&&(*q)->data.num>num) /*因?yàn)槭前磳W(xué)號(hào)非降序排列 */ break; if (*q&&(*q)->data.num==num) /* 找到該學(xué)號(hào) */ return TRUE; *p=*q; } return FALSE; } Status FindFromName(LinkList L,char name[],LinkList *p,LinkList *q) { /*查找表中姓名為name的結(jié)點(diǎn)，如找到,q指向此結(jié)點(diǎn),p指向q的前驅(qū)，*/ /*并返回TRUE如無(wú)此元素，則返回FALSE */ *p=L;

59、 while (*p) { *q=(*p)-> next; if (*q&&!strcmp((*q)->data.name,name)) /* 找到該姓名 */ return TRUE; *p=*q; FALSE; } return Status Delete ElemNum(LinkList L,long num) { /*刪除表中學(xué)號(hào)為num的元素，并返回TRUE如無(wú)此元素，則返回 FALSE */ Lin kList p,q; if (FindFromNum(L,num,&p,&q)) /*找到此結(jié)點(diǎn)，且q指向其,p指向其前驅(qū)*/ { p_>n ext=q _

60、>n ext; free(q); return TRUE; } return FALSE; } Status Delete ElemName(LinkList L,char name[]) { /*刪除表中姓名為name的元素，并返回 TRUE如無(wú)此元素，則返回 FALSE */ Lin kList p,q; if (FindFromName(L,name,&p,&q)) /* 找到此結(jié)點(diǎn)，且q指向其,p指向其前驅(qū)*/ { p_>n ext=q _>n ext; free(q); return TRUE; } return FALSE; } void Modf

61、 y( ElemType *e) { /*修改結(jié)點(diǎn)內(nèi)容*/ char s[80]; Pr int (*e); /* 顯示原內(nèi)容 */ pr int f("請(qǐng)輸入待修改項(xiàng)的內(nèi)容，不修改的項(xiàng)按回車(chē)鍵保持原值 :\n"); pr int f("請(qǐng)輸入姓名(<=%d個(gè)字符):",NAMELEN); gets(s); if (strlen(s)) strcpy(e->n ame,s); pr int f("請(qǐng)輸入學(xué)號(hào):"); gets(s); if (strlen(s)) e->num=atol(s); pr int f("請(qǐng)輸入性別(m:男f:女):"); gets(s);

62、 if (strlen(s)) e_>sex=s[0]; pr int f("請(qǐng)輸入年齡:"); gets(s); if (strlen(s)) e_>age=atoi(s); pr int f("請(qǐng)輸入班級(jí)(<=%d個(gè)字符):",CLASSLEN); gets(s); if (strlen(s)) strcpy(e->Class,s); pr int f("請(qǐng)輸入健康狀況(0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); gets(s); if (strlen(s)) e->health=atoi(s); /* 修改完畢 */ }

63、#define N 4 /* student 記錄的個(gè)數(shù) */ void mai n() { struct stud stude nt[N]={{" 王小林",790631,'m',18," 計(jì) 91",0}, {" 陳紅",790632,'f,20," 計(jì) 91",1}, {" 劉建平",790633,'m',21," 計(jì) 91",0}, {" */ 張立立",790634,'m',17," 計(jì)91",2}}; /*表的初始記錄 int i,j,flag=1; long num; char file name[13], name[NAMELEN+1];

64、 ElemType e; Lin kList T,p,q; InitList （&T）; /* 初始化鏈表 */ while （flag） { pr int f（"1:將結(jié)構(gòu)體數(shù)組student中的記錄按學(xué)號(hào)非降序插入鏈表 \n"）; pr int f（"2:將文件中的記錄按學(xué)號(hào)非降序插入鏈表 \n"）; pr int f（"3:鍵盤(pán)輸入新記錄，并將其按學(xué)號(hào)非降序插入鏈表 \n"）; pr int f（"4:刪除鏈表中第一個(gè)有給定學(xué)號(hào)的記錄 \n"）; pr int f（"5:刪除鏈表中第一個(gè)有給定姓名的記錄 \n”）； pr int f（"6:修改鏈表中第一個(gè)有給定學(xué)號(hào)

65、的記錄 \n”）； pr int f（"7:修改鏈表中第一個(gè)有給定姓名的記錄 \n"）; pr int f（"8:查找鏈表中第一個(gè)有給定學(xué)號(hào)的記錄 \n"）; pr int f（"9:查找鏈表中第一個(gè)有給定姓名的記錄 \n”）； pr int f（"10:顯示所有記錄11:將鏈表中的所有記錄存入文件 12:結(jié)束\n"）; pr int f（"請(qǐng)選擇操作命令:"）; scan f（"%d",&i）; switch（i） { case 1: for （j=0;j

66、int f("請(qǐng)輸入文件名：”)； sea nf("%s",file name); if ((fp=fopen(filename,"rb"))==NULL) pr int f("打開(kāi)文件失敗!\n"); else { while (ReadFromFile(&e)) In sertAsce nd(T,e); fclose(fp); } break; case 3: ReadI n(& e); In sertAsce nd(T,e); break; case 4: pr int f("請(qǐng)輸入待刪除記錄的學(xué)號(hào) :"); scan f("%ld", &nu m); if (!Delete ElemNum(T,num)) pr int f("沒(méi)有學(xué)號(hào)為 %ld的記錄\n",num); break; case 5: pr int f("請(qǐng)輸入待刪除記錄的姓名 :"); sca nf("%s", name); if (!Delete ElemName(T,name)) pr int f("沒(méi)有姓名為 %s的記錄\n”,name); break; ca