清華嚴蔚敏《數據結構》的全部代碼實現C語言#include<string.h>#include<ctype.h>#include<malloc.h>/*malloc()等*/#include<limits.h>/*INT_MAX等*/#include<stdio.h>/*EOF(=>或F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),cei1(),abs()*/#include<process.h>/*exit()*//*函數結果狀態代碼*/ttdefineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因為在math,h中已定義OVERFLOW的值為3,故去掉此行*/typedefintStatus;/*Status是函數的類型，其值是函數結果狀態代碼，如0K等*/typedefintBoolean;/*Boolean是布爾類型，其值是TRUE或FALSE*//*algo2-l.c實現算法2.1的程序*/#include*cl.h”typedefintElemType;#include”c2T?h”c2-l.h線性表的動態分配順序存儲結構*/#defineLIST_INIT_SIZE10/*線性表存儲空間的初始分配量*/#defineLISTINCREMENT2/*線性表存儲空間的分配增量*/typedefstruct(ElemType*elem;/*存儲空間基址*/intlength;/*當前長度*/intlistsize;/*當前分配的存儲容量(以sizeof(ElemType)為單位)*/}SqList;#include"bo2T?c”/*bo2-l.c順序表示的線性表(存儲結構由c2T.h定義)的基本操作(12個)*/StatusInitList(SqList*L)/*算法2.3*/{/*操作結果：構造一個空的順序線性表*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*L).elem)exit(OVERFLOW);/*存儲分配失敗*/(*L).length=0;/*空表長度為0*/1(*L).listsize=LIST_INIT_SIZE;/*初始存儲容量*/returnOK;}StatusDestroyList(SqList*L){/*初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L*/free((*L).elem);(*L).elem二NULL;(*L).length=O;(*L).listsize=O;returnOK;}StatusClearList(SqList*L){/*初始條件：順序線性表L已存在。操作結果：將L重置為空表*/(*L).length=0;returnOK;}StatusListEmpty(SqListL){/*初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE,否則返回FALSE*/if(L.length==0)returnTRUE;elsereturnFALSE;}intListLength(SqListL){/*初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數*/returnL.length;)StatusGetElem(SqListL,inti,ElemType*e){/*初始條件：順序線性表L已存在，IWiWListLength(L)*//*操作結果：用e返回L中第i個數據元素的值*/if(i<l||i>L.length)exit(ERROR);?e=*(L.elem+i-1);returnOK;)intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始條件：順序線性表L已存在，compare。是數據元素判定函數(滿足為1,否則為0)*/2/*操作結果：返回L中第1個與e滿足關系compare。的數據元素的位序。*//*若這樣的數據元素不存在，則返回值為0。算法2.6*/ElemType*p;inti=l;/*i的初值為第1個元素的位序*/P=L.elem;/*p的初值為第1個元素的存儲位置*/whi1e(i<=L.1ength&&!compare(*p++,e))++i；if(i<=L.length)returni;elsereturn0;}StatusPriorE1em(SqListL,ElemTypecur_e,ElemType*pre_e){/*初始條件：順序線性表L已存在*//*操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，*//*否則操作失敗，prje無定義*/inti=2;ElemType*p=L.elem+1;while(i<=L.length&&*p!=cur_e)(p++；i++;}if(i>L.length)returnINFEASIBLE;else(*pre_e=*-p;returnOK;))StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e){/*初始條件：順序線性表L已存在*//*操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回它的后繼，*//*否則操作失敗，next_e無定義*/inti=l;ElemType*p=L.elem;while(i<L.length&￡*p!=cur_e)i++；p++；3}if(i==L.length)returnINFEASIBLE;else(*next_e=*++p;returnOK;}}StatusListinsert(SqList*L,inti,ElemTypee)/*算法2.4*/{/*初始條件：順序線性表L已存在，lWiWListLength(L)+l*//*操作結果：在L中第i個位置之前插入新的數據元素e,L的長度加1*/ElemType*newbase,*q,*p;if(i<l||i>(*L).length+1)/*i值不合法*/returnERROR;if((*L).length>=(*L).listsize)/*當前存儲空間已滿，增加分配*/(newbase=(ElemType*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));if(Inewbase)exit(OVERFLOW);/*存儲分配失敗*/(*L).elem=newbase;/*新基址*/(*L).listsize+=LISTINCREMENT;/*增加存儲容量*/}q=(*L).elem+i-1;/*q為插入位置*/for(p=(*L).elem+(禮).lengthT;p>=q;--p)/*插入位置及之后的元素右移*/*(p+l)=*p;*q=e;/*插入e*/++(*L).length;/*表長增1*/returnOK;}StatusListDelete(SqList*L,inti,ElemType*e)/*算法2.5*/{/*初始條件：順序線性表L已存在，iWi這ListLength(L)*//*操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1*/ElemType*P,*q；if(i<l||i>(*L).length)/*i值不合法?/returnERROR;p=(*L).elem+i-1;/*p為被刪除元素的位置*/*e=*p；/*被刪除元素的值賦給e*/q=(*L).elem+(*L).length-1;/*表尾元素的位置*/for(++p;p<=q;++p)/*被刪除元素之后的元素左移*/*(pT)=*p;4(*L).length-;/*表長減1*/returnOK;StatusListTraverse(SqListL,void(*vi)(ElemType*)){/*初始條件：順序線性表L已存在*//*操作結果：依次對L的每個數據元素調用函數vi()。一旦vi()失敗，則操作失敗*//*vi()的形參加表明可通過調用vi()改變元素的值*/ElemType*p;inti;p=L.elem;for(i=l;i<=L.length;i++)vi(p++);printf('\n");returnOK;}Statusequal(ElemTypecl,ElemTypec2){/*判斷是否相等的函數,Union。用到*/if(cl==c2)returnTRUE;elsereturnFALSE;}voidUnion(SqList*La,SqListLb)/*算法2.1*/{/*將所有在線性表Lb中但不在La中的數據元素插入到La中*/ElemTypee;intLa_len,Lb_len;inti;La_len=ListLength(*La);/*求線性表的長度*/Lblen=ListLength(Lb);for(i=l;i<=Lb_len;i++)(GetElem(Lb,i,&e);/*取Lb中第i個數據元素賦給e*/if(!LocateElem(*La,e,equal))/*La中不存在和e相同的元素,則插入之*/Listinsert(La,++La_len,e);)}voidprint(ElemType*c)(printf(z，%d",*c);)5voidmain()(SqListLa,Lb;Statusi;intj;i=InitList(&La);if(i-l)/*創建空表La成功*/for(j=l;j<=5;j++)/*在表La中插入5個元素*/i=ListInsert(&La,j,j);printf(Z/La=");/*輸出表La的內容*/ListTraverse(La,print);InitList(&Lb);/*也可不判斷是否創建成功*/for(j=l;j<=5;j++)/*在表Lb中插入5個元素*/i=ListInsert(&Lb,j,2*j);printf(*Lb=");/*輸出表Lb的內容*/ListTraverse(Lb,print);Union(&La,Lb);printf(*newLa=");/*輸出新表La的內容*/ListTraverse(La,print);}6/*algo2-2.c實現算法2.2的程序*/ttinclude^cl.h”typedefintElemType;#include”c2T.h”#include"bo2T?c”voidMergeList(SqListLa,SqListLb,SqList*Lc)/*算法2.2*/{/*已知線性表La和Lb中的數據元素按值非遞減排列。*//*歸并La和Lb得到新的線性表Lc,Lc的數據元素也按值非遞減排列*/inti=l,j=l,k=O;intLa_len,Lb_len;ElemTypeai,bj;InitList(Lc);/*創建空表Lc*/La_len=ListLength(1^);Lb_len=ListLength(Lb);while(i<=Lalen&&j<=Lb_len)/*表La和表Lb均非空*/GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai<=bj)[Listinsert(Lc,++k,ai);++i;)else[Listinsert(Lc,++k,bj);++j；))while(i<=La_len)/*表La非空且表Lb空*/IGetElem(La,i++,&ai);Listinsert(Lc,++k,ai);)while(j<=Lb_len)/*表Lb非空且表La空*/{GetElem(Lb,j++,&bj);Listinsert(Lc,++k,bj);voidprint(ElemType*c){7printfC%d”,*c);}voidmain()(SqListLa,Lb,Lc;intj,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20):InitList(ftLa);/*創建空表La*/for(j=l;j<=4;j++)/*在表La中插入4個元素*/Listinsert(&La,j,a[j-l]);printfC"La=");/*輸出表La的內容*/ListTraverse(La,print);InitList(&Lb);/*創建空表Lb*/for(j=l;j<=7;j++)/*在表Lb中插入7個元素*/Listinsert(&Lb,j,b[j-l]);printfCLb=");/*輸出表Lb的內容*/ListTraverse(Lb,print);MergeList(La,Lb,&Lc);printf(*Lc=");/*輸出表Lc的內容*/ListTraverse(Lc,print);/*algo2-3.c實現算法2.7的程序*/#include*cl.h”typedefintElemType;#include*c2-l.h*#includez，bo2-l.c*voidMergeList(SqListLa,SqListLb,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).listsize=(*Lc).length二La.length+Lb.length;/*不用InitList()創建空表Lc*/pc=(*Lc).elem=(ElemType*)malloc((*Lc).listsize*sizeof(ElemType));if(!(*Lc).elem)/*存儲分配失敗*/exit(OVERFLOW);pa_last=La.elem+La.length-1;pblast=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pblast)/*表La和表Lb均非空*/{/*歸并*/8if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;while(pa<=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;/*插入La的剩余元素*/while(pb<=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;/*插入Lb的剩余元素*/)voidprint(ElemType*c)(printf(*%d”,*c);)voidmain()(SqListLa,Lb,Lc;intj;InitList(&La);/*創建空表La*/for(j=l;j<=5;j++)/*在表La中插入5個元素*/Listinsert(&La,j,j);printf(*La=");/*輸出表La的內容*/ListTraverse(La,print);InitList(&Lb);/*創建空表Lb*/for(j=l;j<=5;j++)/*在表Lb中插入5個元素*/Listinsert(&Lb,j,2*j);printf(*Lb=");/*輸出表Lb的內容*/ListTraverse(Lb,print);MergeList(La,Lb,&Lc);printfCLc=〃)；/*輸出表Lc的內容*/ListTraverse(Lc,print);}/*algo2-4.c修改算法2.7的第一個循環語句中的條件語句為開關語句，且當*//**pa=*pb時,只將兩者中之一插入Lc。此操作的結果和算法2.1相同*/#include*cl.h*typedefintElemType;#include”c2T'h”#include”bo2T.c”intcomp(ElemTypecl,ElemTypec2)9{inti;if(cl<c2)i=l；elseif(cl==c2)i=0;elsei=-l；returni;)voidMergeList(SqListLa,SqListLb,SqList*Lc){/*另一種合并線性表的方法(根據算法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).listsize*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<=pblast)/*表La和表Lb均非空*/switch(comp(*pa,*pb))/*此句與算法2.7不同*/{case0:pb++;case1:*pc++=*pa++;break;case-1:*pc++=*pb++;}while(pa<=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;while(pb<=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;(*Lc).length=pc-(*Lc).elem;/*加此句*/}voidprint(ElemType*c)printf("%d",*c);voidmainO{*/10SqListLa,Lb,Lc;intj;InitList(&La);/*創建空表La*/for(j=l;j<=5;j++)/*在表La中插入5個元素?/Listinsert(&La,j,j);printf(*La=");/*輸出表La的內容*/ListTraverse(La,print);InitList(&Lb);/*創建空表Lb*/for(j=l;j<=5;j++)/*在表Lb中插入5個元素*/Listinsert(&Lb,j,2*j)；printf(*Lb=");/*輸出表Lb的內容*/ListTraverse(Lb,print);MergeList(La,Lb,&Lc);printf(*Lc=");/*輸出表Lc的內容*/ListTraverse(Lc,print);)11/*algo2-5.c實現算法2.11、2.12的程序*/#include*cl.h”typedefintElemType;#include*c2-2.h*/*c2-2.h線性表的單鏈表存儲結構*/structLNodeiElemTypedata;structLNode*next;typedefstructLNode禮inkList;/*另一種定義LinkList的方法*/ttinclude*bo2-2.c〃/*bo2-2.c單鏈表線性表(存儲結構由c2-2.h定義)的基本操作(12個)*/StatusInitList(LinkList*L){/*操作結果：構造一個空的線性表L*/*L=(LinkList)malloc(sizeof(structLNode));/*產生頭結點，并使L指向此頭結點*/if(!*D/*存儲分配失敗*/exit(OVERFLOW);(*L)->next=NULL;/*指針域為空*/returnOK;)StatusDestroyList(LinkList*L){/*初始條件：線性表L已存在。操作結果：銷毀線性表L*/LinkListq;while(*L){q=(*L)->next;free(*L);*L=q;}returnOK;StatusClearList(LinkListL)/*不改變L*/{/*初始條件：線性表L已存在。操作結果：將L重置為空表*/LinkListp,q;p=L->next;/*p指向第一個結點*/while(p)/*沒到表尾*/Iq=p->next;free(p);12PF；)L->next=NULL;/*頭結點指針域為空*/returnOK;)StatusListEmpty(LinkListL){/*初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE,否則返回FALSE*/if(L->next)/*非空*/returnFALSE;elsereturnTRUE;}intListLength(LinkListL){/*初始條件：線性表L已存在。操作結果：返回L中數據元素個數*/inti=0;LinkListp=L->next;/*p指向第一個結點*/while(p)/*沒到表尾*/[i++;p=p->next;)returni;)StatusGetElem(LinkListL,inti,ElemType*e)/*算法2.8*/{/*L為帶頭結點的單鏈表的頭指針。當第i個元素存在時,其值賦給e并返回0K,否則返回ERROR*/intj=l;/*j為計數器*/LinkListp=L->next;/*p指向第一個結點*/while(p&&j<i)/*順指針向后查找,直到p指向第i個元素或p為空*/Ip=p->next;j++；}if(!p|Ij>i)/*第i個元素不存在*/returnERROR;*e=p->data;/*取第i個元素*/returnOK;intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType))13{/*初始條件：線性表L已存在,compare。是數據元素判定函數(滿足為1,否則為0)*//*操作結果：返回L中第1個與e滿足關系compare。的數據元素的位序。*//*若這樣的數據元素不存在,則返回值為0*/inti=0;LinkListp=L->next;while(p)(i++；if(compare(p->data,e))/*找到這樣的數據元素*/returni;p=p->next;)return0;}StatusPriorElem(LinkListL,ElemTypecure,ElemType*pre_e){/*初始條件：線性表L已存在*//*操作結果：若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅，*//*返回0K;否則操作失敗,pre_e無定義,返回INFEASIBLE*/LinkListq,p=L->next;/*p指向第一個結點*/while(p->next)/*p所指結點有后繼*/!q=p->next;/*q為p的后繼*/if(q->data==cur_e)*pre_e=p->data;returnOK;)P=q；/*p向后移*/)returnINFEASIBLE;)StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e){/*初始條件：線性表L已存在*//*操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回它的后繼，*//*返回0K;否則操作失敗,next_e無定義，返回INFEASIBLE*/LinkListp=L->next;/*P指向第一個結點*/while(p->next)/*p所指結點有后繼*/!if(p->data==cur_e)(*next_e=p->next->data;14returnOK;}p=p->next;returnINFEASIBLE;StatusListinsert(LinkListL,inti,ElemTypee)/*算法2.9。不改變L*/{/*在帶頭結點的單鏈線性表L中第i個位置之前插入元素e*/intj=0;LinkListp=L,s;while(p&&j<i-l)/*尋找第i-1個結點*/!p=p->next;j++；}if(!p|Ij>i-l)/*i小于1或者大于表長*/returnERROR;s=(LinkList)malloc(sizeof(structLNode));/*生成新結點*/s->data=e;/*插入L中*/s->next=p->next;p->next=s;returnOK;}StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改變L*/{/*在帶頭結點的單鏈線性表L中，刪除第i個元素，并由e返回其值*/intj=0;LinkListp=L,q;while(p->next&&j<i-l)/*尋找第i個結點，并令p指向其前趨*/{p=p->next;j++；if(!p->next|Ij>i-l)/*刪除位置不合理*/returnERROR;q=p->next;/*刪除并釋放結點*/p->next=q->next;*e=q->data;free(q);returnOK;}StatusListTraverse(LinkListL,void(*vi)(ElemType))15/*vi的形參類型為ElemType,與bo2T.e中相應函數的形參類型ElemType&不同*/{/*初始條件：線性表L已存在*//*操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗，則操作失敗*/LinkListp=L->next;while(p){vi(p->data);p=p->next;}printf('\n");returnOK;}voidCreateList(LinkList*L,intn)/*算法2.11*/{I*逆位序(插在表頭)輸入n個元素的值，建立帶表頭結構的單鏈線性表L*/inti;LinkListp;*L=(LinkList)malloc(sizeof(structLNode));(*L)->next=NULL;/*先建立一個帶頭結點的單鏈表*/printf("請輸入%d個數據\n”,n);for(i=n;i>0;-i)(p=(LinkList)malloc(sizeof(structLNode));/*生成新結點*/scanf("%d”,&p->data);/*輸入元素值*/p->next=(*L)->next;/*插入到表頭*/(*L)->next=p;}}voidCreateList2(LinkList*L,intn){/*正位序(插在表尾)輸入n個元素的值，建立帶表頭結構的單鏈線性表*/inti;LinkListp,q;*L=(LinkList)malloc(sizeof(structLNode));/*生成頭結點*/(*L)->next=NULL;q=*L;printf("請輸入%d個數據\n”,n);for(i=l;i<=n;i++)ip=(LinkList)malloc(sizeof(structLNode));scanf("%d”,&p->data);q->next=p;q=q->next;)16p->next=NULL;}voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)/*算法2.12*/{/*已知單鏈線性表La和Lb的元素按值非遞減排列。*//*歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列*/LinkListpa=La->next,pb=(*Lb)->next,pc;*Lc=pc=La;/*用La的頭結點作為Lc的頭結點*/while(pa&&pb)if(pa->data<=pb->data)!pc->next=pa;pc=pa;pa=pa->next;}else(pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;/*插入剩余段*/free(*Lb);/*釋放Lb的頭結點*/Lb=NULL;}voidvisit(ElemTypec)/*ListTraverseO調用的函數(類型要一致)*/(printf("%d",c);}voidmainO!intn=5;LinkListLa,Lb,Lc;printf(〃按非遞減順序，〃)；CreateList2(&La,n);/*正位序輸入n個元素的值*/printfCLa=*);/*輸出鏈表La的內容*/ListTraverse(La,visit);printf(〃按非遞增順序，〃)；CreateList(&Lb,n);/*逆位序輸入n個元素的值*/printf("Lb=");/*輸出鏈表Lb的內容*/ListTraverse(Lb,visit);MergeList(La,&Lb,&Lc);/*按非遞減順序歸并La和Lb,得到新表Lc*/17printf(*Lc=9;/*輸出鏈表Lc的內容*/ListTraverse(Lc,visit);/*algo2-6.c利用單鏈表結構處理教科書圖2.1(學生健康登記表)*/Sinclude^cl.h〃ttdefineNAMELEN8/*姓名最大長度*/^defineCLASSLEN4/*班級名最大長度*/structstud/*記錄的結構*/(charname[NAMELEN+l];longnum;charsex;intage;charClass[CLASSLEN+1];inthealth;}；typedefstructstudElemType;/*鏈表結點元素類型為結構體*/#include"c2-2.h”charsta[3][9]={〃健康，般”「神經衰弱”};/*健康狀況(3類)?/FILE*fp;StatusInitList(LinkList*L)/*拷自bo2-2.c*/{/*操作結果：構造一個空的線性表L*/*L=(LinkList)malloc(sizeof(structLNode));/*產生頭結點，并使L指向此頭結點*/if(!*L)/*存儲分配失敗*/exit(OVERFLOW);(禮)-)next=NULL;/*指針域為空*/returnOK;StatusListTraverse(LinkListL,void(*vi)(ElemType))/*拷自bo2-2.c*/{/*初始條件：線性表L已存在*//*操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗，則操作失敗*/LinkListp=L->next;while(p)(vi(p->data);p=p->next;)printf('\n");returnOK;)18voidInsertAscend(LinkListL,ElemTypee)/*此函數是由bo2-9.c中的同名函數改寫*/{/*按學號非降序插入*/LinkListq=L,p=L->next;while(p&&e.num>p->data.num)iq=P；p=p->next;}q->next=(LinkList)malloc(sizeof(structLNode));/*插在q后*/q->next->data=e;q->next->next=p;voidPrint(structstude){/*顯示記錄e的內容*/printf(*%-8s%61d”,,e.num);if(e.sex==，m，)printf(*男");elseprintf(*女”)；printf("%5d e.age,e.Class);printf("%9s\n”,state,health]);}voidReadin(structstud*e){/*由鍵盤輸入結點信息*/printf("請輸入姓名?=%d個字符)：”,NAMELEN);scanfe->name);printf("請輸入學號：”)；scanf&e->num);printf("請輸入性別(m:男f:女)：〃)；scanf(*%*c%c*,&e->sex);printf(”請輸入年齡：”)；scanf("%d”,&e->age);printf（”請輸入班級?=%d個字符）：”,CLASSLEN）;scanfe->Class);printf("請輸入健康狀況(0:%s1:%s2:%s):sta[O],sta[l],sta[2]);scanf&e->health);}voidWriteToFile(structstude){/*將結點信息寫入fp指定的文件*/fwrite(&e,sizeof(structstud),1,fp);19}StatusReadFromFi1e(struetstud*e){/*由fp指定的文件讀取結點信息到e*/inti;i=fread(e,sizeof(structstud),1,fp);if(i==l)/*讀取文件成功*/returnOK;elsereturnERROR;}StatusFindFromNum(LinkListL,longnum,LinkList*p,LinkList*q){/*查找表中學號為num的結點,如找到,q指向此結點,p指向q的前驅，*//*并返回TRUE;如無此元素，則返回FALSE*/*p=L;while(*p)*q=(*p)->next;if(*q&&(*q)->data.num>num)/*因為是按學號非降序排列*/break;if(*q&&(*q)->data.num==num)/*找到該學號*/returnTRUE;*p=*q;)returnFALSE;}StatusFindFromName(LinkListL,charname[],LinkList*p,LinkList*q){/*查找表中姓名為name的結點，如找到,q指向此結點,p指向q的前驅，*//*并返回TRUE;如無此元素，則返回FALSE*/*p=L;while(*p){*q=(*p)->next;if(*q&&!strcmp((*q)->,name))/*找到該姓名*/returnTRUE;*p=*q;}returnFALSE;StatusDeleteElemNum(LinkListL,longnum){/*刪除表中學號為num的元素，并返回TRUE；如無此元素，則返回FALSE*/20LinkListp,q;if(FindFromNum(L,num,&p,&q))/*找到此結點，且q指向其,p指向其前驅*/{p->next=q->next;free(q);returnTRUE;)returnFALSE;)StatusDeleteElemName(LinkListL,charname口){/*刪除表中姓名為name的元素，并返回TRUE；如無此元素，則返回FALSE*/LinkListp,q;if(FindFromName(L,name,&p,&q))/*找到此結點，且q指向其,p指向其前驅*/{p->next=q->next;free(q);returnTRUE;}returnFALSE;}voidModify(ElemType*e){/*修改結點內容*/chars[80];Print(*e);/*顯示原內容*/printf（〃請輸入待修改項的內容，不修改的項按回車鍵保持原值:\n〃）;printf("請輸入姓名?=%d個字符)：^NAMELEN);gets(s);if(strlen(s))strcpy(e->name,s);printf(“請輸入學號：〃)；gets(s);if(strlen(s))e->num=atol(s);printf("請輸入性別(m:男f:女)：〃)；gets(s);if(strlen(s))e->sex=s[O];printf(”請輸入年齡：”)；gets(s);if(strlen(s))e->age-atoi(s);printf("請輸入班級?=%d個字符)：",CLASSLEN);21gets(s);if(strlen(s))strcpy(e->Class,s);printf("請輸入健康狀況(0:%sl:%s2:%s)sta[O],sta[lLsta[2]);gets(s);if(strlen(s))e->health=atoi（s）;/*修改完畢*/#defineN4/*student記錄的個數*/voidmainOIstructstudstudent[N]={{"王小林"，790631,'m',18,"計91”,0},{"陳紅"，790632,*f',20,"計91”,1},{"劉建平"，790633,'m',21,"計91”,0）,{"張立立”,790634,'m',17,"計91”,2}};/*表的初始記錄*/inti,j,flag=l;longnum;charfilename[13],name[NAMELEN+1];ElemTypee;LinkListT,p,q;InitList（&T）；/*初始化鏈表*/while（flag）[printf（"1:將結構體數組student中的記錄按學號非降序插入鏈表\n"）;printf（"2:將文件中的記錄按學號非降序插入鏈表\n"）;printf（"3:鍵盤輸入新記錄，并將其按學號非降序插入鏈表\n"）;printf（"4:刪除鏈表中第一個有給定學號的記錄\n"）;printf（"5:刪除鏈表中第一個有給定姓名的記錄\n"）;printf（"6:修改鏈表中第一個有給定學號的記錄\n"）;printf（"7:修改鏈表中第一個有給定姓名的記錄\n"）;printf(〃8:查找鏈表中第一個有給定學號的記錄\n〃)；printf(〃9:查找鏈表中第一個有給定姓名的記錄\n");printf(〃10:顯示所有記錄11:將鏈表中的所有記錄存入文件12:結束\n");printf("請選擇操作命令：〃)；scanf&i);switch(i)(for(j=0;j<N;j++)InsertAscend(T,student[j]);break;printf(”請輸入文件名：”)；scanffilename);if((fp=fopen(fi1ename,"rb"))==NULL)22printf("打開文件失敗!\n");else(while(ReadFromFi1e(&e))InsertAscend(T,e);fclose(fp);)break;Readin(&e);InsertAscend(T,e);break;printf("請輸入待刪除記錄的學號：〃)；scanf&num);if(!De1eteE1emNum(T,num))printf("沒有學號為％1(1的記錄\n”,num);break;printf("請輸入待刪除記錄的姓名：”)；scanfname);if(!DeleteElemName(T,name))printf("沒有姓名為%s的記錄\n”,name);break;printf("請輸入待修改記錄的學號：");scanf(*%ld%*c*,&num);/*%*c吃掉回車符*/if(!FindFromNum(T,num,&p,&q))printf("沒有學號為%Id的記錄\n”,num);else(Modify(&q->data);if(q->data.num!=num)/*學號被修改*/ip->next=q->next;/*把q所指的結點從L中刪除*/InsertAscend(T,q->data);/*把元素插入L*/free(q);/*刪除q*/break;printf(“請輸入待修改記錄的姓名：")；scanf(*%s%*c*,name);/*%*c吃掉回車符*/if(!FindFromName(T,name,&p,&q))printf("沒有姓名為％5的記錄\\,name);else(num=q->data.num;/*學號存入num*/Modify(&q->data);23if(q->data.num!=num)/*學號被修改*/(p->next=q->next;/*把q所指的結點從L中刪除*/InsertAscend(T,q->data);/*把元素插入L*/free(q);/*刪除q*/}}break;printf("請輸入待查找記錄的學號：”)；scanf&num);if(!FindFromNum(T,num,&p,&q))printf("沒有學號為％1€1的記錄\n〃,num);elsePrint(q->data);break;printf("請輸入待查找記錄的姓名：〃)；scanfname);if(!FindFromName(T,name,&p,&q))printf("沒有姓名為%s的記錄\n”,name);elsePrint(q->data);break;case10:printf("姓名學號性別年齡班級健康狀況\n");ListTraverse(T,Print);break;casell:printf("請輸入文件名：”)；scanffilename);if((fp=fopen(filename,，zwb*))==NULL)printf("打開文件失敗!\n");elseListTraverse(T,WriteToFile);fclose(fp);break;case12:flag=0;/*algo2-7.c教科書中圖2.10靜態鏈表示例*//*第一個結點的位置在[0].cur中，成員cur的值為0,則到鏈表尾*/ttinclude*cl.h”ttdefineN6/*字符串長度*/24typedefcharElemType[N];#include"c2-3.h”/*c2-3.h線性表的靜態單鏈表存儲結構*/ttdefineMAXSIZE100/*鏈表的最大長度*/typedefstruct{ElemTypedata;intcur;}component,SLinkList[MAXSIZE];voidmain(){SLinkLists={{",1},{"ZHA0”,2},{〃QIAN〃,3},{〃SUN”,4},{"LI”,5},{〃ZH0U〃,6},{"WlT,7},{"ZHENG〃,8},{〃WANG〃,0}};inti;i=s[0].cur;while(i)/*輸出教科書中圖2.10(a)的狀態*/{printf(*%s s[i].data);/*輸出鏈表的當前值*/i=s[i].cur;/*找到下一個*/printf('\n");s[4].cur=9;/*按教科書中圖2.10(b)修改*/s[6].cur=8;s[9].cur=5;strcpy(s[9].data,"SHI");i=s[0].cur;while(i)/*輸出教科書中圖2.10(b)的狀態*/(printf(z，%s",s[i].data);/*輸出鏈表的當前值*/cur;/*找到下一個*/}printf;)/*algo2-8.c實現算法2.17的程序*/Sinclude*cl.h"fldefineN2typedefcharElemType;#include"c2-3.h”#include/zbo2-3.c"25/*bo2-3.c實現算法2.15、2.16的程序(數據結構由c2-3.h定義)(3個)*/intMalloc(SLinkListspace)/*算法2.15*/{/*若備用鏈表非空，則返回分配的結點下標(備用鏈表的第一個結點)，否則返回0*/inti=space[O].cur;if(i)/*備用鏈表非空*/spacetO].cur=space[i].cur;/*備用鏈表的頭結點指向原備用鏈表的第二個結點*/returni;/*返回新開辟結點的坐標*/)voidFree(SLinkListspace,intk)/*算法2.16*/{/*將下標為k的空閑結點回收到備用鏈表(成為備用鏈表的第一個結點)*/space[k].cur=space[0].cur;/*回收結點的"游標"指向備用鏈表的第一個結點*/space[0].cur=k;/*備用鏈表的頭結點指向新回收的結點*/)voidDestroyList(){/*靜態數組不能被銷毀*/)#include"bo2-32.c”/*bo2-32.c一個數組可生成若干靜態鏈表(數據結構由c2-3.h定義)的基本操作(12個)*/voidInitSpace(SLinkListL)/*算法2.14。另加*/{/*將一維數組L中各分量鏈成一個備用鏈表，L[0].cur為頭指針。“0”表示空指針*/inti;for(i=0;i<MAXSIZE-l;i++)L[i].cur=i+l;L[MAXSIZE-l].cur=O;}intInitList(SLinkListL){/*構造-個空鏈表，返回值為空表在數組中的位序*/inti;i=Malloc(L);/*調用MallocO,簡化程序*/L[i].cur=0;/*空鏈表的表頭指針為空(0)*/returni;)StatusClearList(SLinkListL,intn){/*初始條件：L中表頭位序為n的靜態鏈表已存在。操作結果：將此表重置為空表*/intj,k,i=L[n].cur;/*鏈表第一個結點的位置*/L[n].cur=0;/*鏈表空*/k=L[0].cur;/*備用鏈表第一個結點的位置*/L[0].cur=i;/*把鏈表的結點連到備用鏈表的表頭*/while(i)/*沒到鏈表尾*/{26j=i；i=L[i].cur;/*指向下一個元素*/)L[j].cur=k;/*備用鏈表的第一個結點接到鏈表的尾部*/return0K;)StatusListEmpty(SLinkListL,intn){/*判斷L中表頭位序為n的鏈表是否空,若是空表返回TRUE;否則返回FALSE*/if(L[n].cur==0)/*空表*/returnTRUE;elsereturnFALSE;intListLength(SLinkListL,intn){/*返回L中表頭位序為n的鏈表的數據元素個數*/intj=0,i=L[n].cur;/*i指向第一個元素*/while(i)/*沒到靜態鏈表尾*/{i=L[i].cur;/*指向下一個元素*/j++；)returnj;)StatusGetElem(SLinkListL,intn,inti,ElemType*e){/*用e返回L中表頭位序為n的鏈表的第i個元素的值*/int1,k=n;/*k指向表頭序號*/if(i<lI|i>ListLength(L,n))/*i值不合理*/returnERROR;for(l=l;K=i;l++)/*移動i-l個元素*/k=L[k].cur;*e=L[k].data;returnOK;intLocateElem(SLinkListL,intn,ElemTypee){/*在L中表頭位序為n的靜態單鏈表中查找第1個值為e的元素。/*若找到，則返回它在L中的位序，否則返回0*/inti=L[n].cur;/*i指示表中第一個結點*/while(i&&L[i].data!=e)/*在表中順鏈查找(e不能是字符串)*/i=L[i].cur;returni;*/27}StatusPriorElem(SLinkListL,intn,ElemTypecur_e,ElemType*pre_e){/*初始條件：在L中表頭位序為n的靜態單鏈表已存在*//*操作結果：若cur_e是此單鏈表的數據元素，且不是第一個，*//*則用pre_e返回它的前驅，否則操作失敗,pre_e無定義*/intj,i=L[n].cur;/*i為鏈表第一個結點的位置*/do{/*向后移動結點*/j=i；i=L[i].cur;}while(i&&cur_e!=L[i].data);if(i)/*找到該元素*/(*pre_e=L[j].data;returnOK;returnERROR;StatusNextElem(SLinkListL,intn,ElemTypecur_e,ElemType*next_e){/*初始條件：在L中表頭位序為n的靜態單鏈表已存在*//*操作結果：若cur_e是此單鏈表的數據元素，且不是最后一個，*//*則用next_e返回它的后繼，否則操作失敗，next_e無定義*/inti;i=LocateElem(L,n,cur_e);/*在鏈表中查找第一個值為cure的元素的位置*/if(i)/*在靜態單鏈表中存在元素cur_e*/{i=L[i].cur;/*cur_e的后繼的位置*/if(i)/*cur_e有后繼*/(*next_e=L[i].data;returnOK;/*cur_e元素有后繼*/}}returnERROR;/*L不存在cur_e元素,cur_e元素無后繼*/}StatusListinsert(SLinkListL,intn,inti,ElemTypee){/*在L中表頭位序為n的鏈表的第i個元素之前插入新的數據元素e*/int1,j,k=n;/*k指向表頭*/if(i<l||i>ListLength(L,n)+l)returnERROR;j=Malloc(L);/*申請新單元*/28if(j)/*申請成功*/L[j].data=e;/*賦值給新單元*/for(l=l;Ki;l++)/*移動i-1個元素*/k=L[k].cur;L[j].cur=L[kLcur;L[k].cur=j;returnOK;}returnERROR;}StatusListDelete(SLinkListL,intn,inti,ElemType*e){/*刪除在L中表頭位序為n的鏈表的第i個數據元素e,并返回其值*/intj,k=n;/*k指向表頭*/if(i<l||i>ListLength(L,n))returnERROR;for(j=l;j<i;j++)/*移動iT個元素*/k=L[k].cur;j=L[k].cur;L[k].cur=L[j].cur;*e=L[j].data;Free(L,j)；StatusListTraverse(SLinkListL,intn,void(*vi)(ElemType)){/*依次對L中表頭位序為n的鏈表的每個數據元素，調用函數vi()。一旦vi()失敗，則操作失敗*/inti=L[n].cur：/*指向第一個元素*/while(i)/*沒到靜態鏈表尾*/(vi(L[i].data);/*調用vi()*/i=L[i].cur：/*指向下一個元素*/)printf("\n");returnOK;)voiddifference(SLinkListspace,int*S)/*算法2.17*/{/*依次輸入集合A和B的元素，在一維數組space中建立表示集合(A-B)U(B-A)*//*的靜態鏈表，S為其頭指針。假設備用空間足夠大，space[O].cur為備用空間的頭指針*/intr,p,m,n,i,j,k;29ElemTypeb;InitSpace(space);/*初始化備用空間*/*S=Malloc(space);/*生成S的頭結點*/r=*S;/*r指向S的當前最后結點*/printf("請輸入集合A和B的元素個數m,n:")：scanf("%d,%d%*c",&m,&n);/*%*c吃掉回車符*/printf("請輸入集合A的元素(共%d個)：”,m);for(j=l;j<=m;j++)/*建立集合A的鏈表?/{i=Malloc(space);/*分配結點*/scanf(*%c*,&space[i].data);/*輸入A的元素值*/space[r].cur=i;/*插入到表尾*/r=i;}scanf("%*c");/*%*c吃掉回車符*/space[r].cur=O;/*尾結點的指針為空*/printf("請輸入集合B的元素(共%d個)：”,n);for(j=l;j<=n;j++){/*依次輸入B的元素，若不在當前表中，則插入，否則刪除*/scanf("%c",&b);P=*S;k=space[*S].cur;/*k指向集合A中的第一個結點*/while(k!=space[r].cur&&space[k].data!=b){/*在當前表中查找*/p=k;k=space[k].cur;if(k==space[r].cur){/*當前表中不存在該元素，插入在r所指結點之后，且r的位置不變*/i=Malloc(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i;}else/*該元素已在表中，刪除之*/(space[p].cur=space[k].cur;Free(space,k);if(r==k)r=p;/*若刪除的是尾元素，則需修改尾指針*/}})30voidvisit(ElemTypec)(printf(*%c",c);}voidmain()(intk;SLinkLists;difference(s,&k);ListTraverse(s,k,visit);}/*algo2-9.c盡量采用bo2-32.c中的基本操作實現算法2.17的功能*/#include*cl.h”ttdefineN2typedefcharElemType;#include"c2-3.h”#includez，bo2-3.c*#include"bo2-32.c"voidvisit(ElemTypec)(printf(*%c",c);}intdifference(SLinkListspace)/*改進算法2.17(盡量利用基本操作實現)*/{/*依次輸入集合A和B的元素，在一維數組space中建立表示集合(A-B)U(B-A)*//*的靜態鏈表，并返回其頭指針。假設備用空間足夠大，space[O].cur為備用空間的頭指針?*/intm,n,i,j,k,S;ElemTypeb,c;InitSpace(space);/*初始化備用空間*/S=InitList(space);/*生成鏈表S的頭結點*/printf（"請輸入集合A和B的元素個數m,n:'）;scanf(*%d,%d%*c*,&m,&n);/*%*c吃掉回車符*/printf("請輸入集合A的元素(共%d個):",m);for(j=l;j<=m;j++)/*建立集合A的鏈表*/(scanfC%c",&b);/*輸入A的元素值*/Listinsert(space,S,j,b);/*插入到表尾*/}scanf("%*c");/*吃掉回車符*/31printf("請輸入集合B的元素(共%d個)：”,n);for(j=l;j<=n;j++){/*依次輸入B的元素，若不在當前表中，則插入，否則刪除*/scanf&b);k=LocateElem(space,S,b);/*k為b的位序*/if(k)/*b在當前表中*/(PriorElem(space,S,b,&c);/*b的前驅為c*/i=LocateElem(space,S,c);/*i為c的位序*/spaceti].cur=space[k].cur;/*將k的指針賦給i的指針*/Free(space,k);/*將下標為k的空閑結點回收到備用鏈表*/)elseListinsert(space,S,ListLength(space,S)+l,b);/*在表尾插入b*/returnS;voidmain()(intk;SLinkLists;k=difference(s);ListTraverse(s,k,visit);}/*algo2-10.c兩個僅設表尾指針的循環鏈表的合并(教科書圖2.13)*/#include*cl.h〃typedefintElemType;#include'c2-2.h"/*c2-4.h線性表的雙向鏈表存儲結構*/typedefstructDuLNode(ElemTypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;#include，zbo2-4.c”/*bo2-4.c設立尾指針的單循環鏈表(存儲結構由c2-2.h定義)的12個基本操作*/StatusInitList_CL(LinkList*L){/*操作結果：構造一個空的線性表L*/*L=(LinkList)malloc(sizeof(structLNode));/*產生頭結點，并使L指向此頭結點*/if(!*L)/*存儲分配失敗*/32exit(OVERFLOW);(*L)->next=*L;/*指針域指向頭結點*/returnOK;}StatusDestroyList_CL(LinkList*L){/*操作結果：銷毀線性表L*/LinkListq,p=(*L)->next;/*p指向頭結點*/while(p!=*L)/*沒到表尾*/iq=p->next;free(p);P=q；}free(禮)；禮二NULL;returnOK;}StatusClearList_CL(LinkList*L)/*改變L*/{/*初始條件：線性表L已存在。操作結果：將L重置為空表*/LinkListp,q;?L=(*L)->next;/*L指向頭結點*/p=(*L)->next;/*p指向第一個結點*/while(p!=*L)/*沒到表尾*/{q=p->next;free(p);PF；}(*L)->next=*L;/*頭結點指針域指向自身*/returnOK;}StatusListEmpty_CL(LinkListL){/*初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE,否則返回FALSE*/if(L->next==L)/*空*/returnTRUE;elsereturnFALSE;)intListLength_CL(LinkListL)33{/*初始條件：L已存在。操作結果：返回L中數據元素個數*/inti=0;LinkListp=L->next;/*p指向頭結點*/while(p!=L)/*沒到表尾*/i++；p=p_>next;)returni;)StatusGetElemCL(LinkListL,inti,ElemType*e){/*當第i個元素存在時,其值賦給e并返回OK,否則返回ERROR*/intj=l;/*初始化,j為計數器*/LinkListp=L->next->next;/*p指向第一個結點*/if(i<=0||i>ListLength_CL(L))/*第i個元素不存在*/returnERROR;while(j<i){/*順指針向后查找,直到p指向第i個元素*/p=p->next;j++：)*e=p->data;/*取第i個元素*/returnOK;)intLocateElem_CL(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/*初始條件：逅性表L已存在，compare。是數據元素判定函數*//*操作結果：返回L中第1個與e滿足關系compare。的數據元素的位序。*//*若這樣的數據元素不存在