清華嚴蔚敏數(shù)據(jù)結(jié)構(gòu)的全部代碼實現(xiàn)C語言知識

s

cl?h(程序名)*/

#include<string.h>

#include<ctype.h>

#include<malloc.h>/*malloc。等*/

#include<limits.h>/*INT_MAX等*/

#include<stdio.h>/*EOF(=AZ或F6),NULL*/

#include<stdlib.h>/*atoi()*/

#include<io.h>/*eof()*/

#include<math.h>/*floor(),ceil(),abs()*/

#include<process.h>/*exit()*/

/*函數(shù)結(jié)果狀態(tài)代碼*/

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

/*#defineOVERFLOW-2因為在math.h中已定義OVERFLOW的值為3,故去掉此行*/

typedefintStatus;/*Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等*/

typedefintBoolean;/*Boolean是布爾類型,其值是TRUE或FALSE刃

/*algo2-l.c實現(xiàn)算法2.1的程序*/

#includencl.hM

typedefintElemType;

#includeMc2-l.hH

/*c2-l.h線性表的動態(tài)分配順序存儲結(jié)構(gòu)*/

#defineLIST_INIT_SIZE10/*線性表存儲空間的初始分配量*/

#defineLISTINCREMENT2/*線性表存儲空間的分配增量*/

typedefstruct

(

ElemTypeclem;/*存儲空間基址*/

intlength;/*當前長度*/

intlistsize;/*當前分配的存儲容量(以sizeof(ElemType)為單位)*/

JSqList;

#include"

/*bo2-l.c順序表示的線性表(存儲結(jié)構(gòu)由c2-l.h定義)的基本操作(12個)*/

StatusInitList(SqList*L)/*算法2.3*/

{/*操作結(jié)果：構(gòu)造一個空的順序線性表*/

(}:L).elem=(ElemType:(c}malloc(LIST_INlT_SlZE*sizeof(ElemType));

if(!(*L).elem)

exit(OVERFLOW);/*存儲分配失敗*/

(*L).length=0;/*空表長度為0*/

(^L).listsize=LIST_INIT_SIZE;/*初始存儲容量*/

returnOK;

StatusDestroyList(SqList:L)

{/*初始條件：順序線性表L已存在。操作結(jié)果：銷毀順序線性表L*/

free((::L).elem);

(*L).elem=NULL;

(：i：L).length=0;

(*L).listsize=O;

returnOK;

StatusClearList(SqList*L)

｛六初始條件：順序線性表L已存在。操作結(jié)果：將L重置為空表*/

(*L)』englh=0;

returnOK;

StatusListEmpty(SqListL)

{/*初始條件：順序線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE,否則返回

FALSE*/

if(L.length==O)

returnTRUE;

else

returnFALSE;

intListLength(SqListL)

{/*初始條件：順序線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)*/

returnL.length;

)

StatusGetElem(SqListL,inti,ElemType*e)

{/*初始條件：順序線性表L已存在，iWiWListLength(L)*/

/*操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值*/

if(i<l||i>L.length)

exil(ERROR);

*e=*(L.elem+i-l);

returnOK;

)

intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{/*初始條件：順序線性表L已存在，compare。是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0)*/

/*操作結(jié)果：返回L中第1個與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。*/

/*若這樣的數(shù)據(jù)元素不存在，則返回值為00算法2.6*/

ElemType*p;

inli=l;/*i的初值為第1個元素的位序*/

p=L.elem;/*p的初值為第1個元素的存儲位置*/

while(i<=L.length&&!compare(*p4-+,e))

++i；

if(i<=L.length)

returni;

else

return0;

)

StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)

{/*初始條件：順序線性表L已存在*/

/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，*/

否則操作失敗，pre_e無定義*/

inti=2;

ElemType*p=L.elem+1;

while(i<=L.lenglh&&:1:p!=cur_e)

p++;

i++；

)

if(i>L.length)

returnINFEASIBLE;

else

{

*pre_e=*—p;

returnOK;

)

)

StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e)

{/*初始條件：順序線性表L已存在*/

/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼,

7

/*否則操作失敗，next_e無定義*/

inti=l;

ElemType*p=L.elem;

while(i<L.length&&*p!=cur_e)

(

i++；

P++；

)

if(i==L.length)

returnINFEASIBLE;

else

(

*next_e=*++p;

returnOK;

StatusListInsert(SqList*L,inti,ElemTypee)/*算法2.4*/

{/*初始條件：順序線性表L已存在，l<i<ListLength(L)+l*/

/*操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加1*/

ElemType*newbase,*q,*p;

if(i<l||i>(*L).length+l)/*i值不合法*/

returnERROR;

if((：:：L).length>=(：!：L).listsize)/*當前存儲空間已滿，增加分配*/

{

newbase=(ElemType

*)reanoc((:::L),elem,(("L)Jistsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)

exit(OVERFLOW);/*存儲分配失敗*/

(::L).elem=newbase;/*新基址*/

(*L)Jislsize+二LISTINCREMENT;/*增加存儲容量*/

)

q=(*L).elem+i-l;/*q為插入位置*/

for(p=(1L).elem+(:'L).length-l;p>=q;-p)/*插入位置及之后的元素右移*/

*(p+l)=*p;

*q=e;/*插入e*/

++(：i：L),length;/*表長增1*/

returnOK;

StatusListDelete(SqList：KL,inti,ElemType*e)/*算法2.5*/

{/*初始條件：順序線性表L已存在，iWiWListLength(L)*/

/*操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1*/

ElemType*p,*q;

if(i<l||i>(*L).length)/*i值不合法*/

returnERROR;

p=(：i：L).elem+i-l;/*p為被刪除元素的位置*/

*e=*p;/*被刪除元素的值賦給e*/

q=(*L).ftlem+(*L).length-1;/*表尾元素的位置*/

for(++p;p<=q;++p)/*被刪除元素之后的元素左移*/

*(p-l)=*p;

(：1：L).length—;/*表長減1*/

returnOK;

StatusListTraverse(SqListL,void(*vi)(ElemType*))

{/*初始條件：順序線性表L已存在*/

/*操作結(jié)果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗，則操作失敗*/

/*vi()的形參加表明可通過調(diào)用vi()改變元素的值*/

ElemType*p;

inti;

p=L.elem;

for(i=l;i<=L.length;i++)

vi(p++);

printf(n\n");

returnOK;

Statusequal(ElemTypecl,ElemTypec2)

{/*判斷是否相等的函數(shù),Union。用到*/

if(cl==c2)

returnTRUE;

else

returnFALSE;

)

voidUnion(SqList"La,SqListLb)/*算法2.1*/

{將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中*/

ElemTypee;

intLa_len,Lb_len;

inti;

La_len=ListLength(La);/*求線性表的長度*/

Lb_len=ListLength(Lb);

for(i=l;i<=Lb_len;i++)

(

GetElem(Lb,i,&e);/*取Lb中第i個數(shù)據(jù)元素賦給e*/

if(!LocateElem(::La,e,equal))/*La中不存在和e相同的元索，則插入之*/

ListInsert(La,++La_len,e);

voidprint(ElemType*c)

(

printf(n%du,*c);

voidmain()

(

SqListLa,Lb;

Statusi;

intj；

i=InitList(&La);

if(i==l)/*創(chuàng)建空表La成功*/

for(j=l;j<=5;j++)/*在表La中插入5個元素*/

i=ListInsert(&La,jj);

prmtf(MLa=H);/*輸出表La的內(nèi)容*/

ListTraverse(La,print);

InitList(&Lb);/*也可不判斷是否創(chuàng)建成功*/

for(j=l；j<=5;j++)/*在表Lb中插入5個元素*/

i=ListInsert(&Lb,j,2*j);

prmtf(MLb=°);/*輸出表Lb的內(nèi)容*/

ListTraverse(Lb,print);

Union(&La,Lb);

printf(nnewLa=M);/*輸出新表La的內(nèi)容*/

ListTraverse(La,print);}

/*algo2-2.c實現(xiàn)算法2.2的程序*/

#includencl.h"

typedefintElemType;

#include"c2-l.hn

#

voidMergeList(SqListLa,SqListLb,SqListLc)/*算法2.2*/

{/*已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。*/

/*歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列號

inti=l,j=l,k=O;

intLa」en,Lb_len;

ElemTypeai,bj;

InitList(Lc);/*創(chuàng)建空表Lc*/

LaJen=ListLength(La);

Lb_len=ListLength(Lb);

while(i<=La_len&&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空次/

{

GetElem(La,i++,&ai);

ListInsert(Lc,++k,ai);

)

while(j<=Lb_len)/*表Lb非空且表La空*/

(

GetElem(Lb,j++,&bj);

ListInsert(Lc,++k,bj);

voidprint(ElemType*c)

printf(n%d",*c);

)

voidmain()

(

SqListLa,Lb,Lc;

intj,a[4]={3,5,8,ll},b[7]={2,6,8,9,11,15,20);

InitList(&La);/*創(chuàng)建空表La*/

for(j=l;j<=4;j++)/*在表La中插入4個元素*/

ListInsert(&La,j,a[j-1]);

printf(nLa=H);/*輸出表La的內(nèi)容*/

ListTraverse(La,print);

InitList(&Lb);/*創(chuàng)建空表Lb*/

for(j=l;j<=7;j++)/*在表Lb中插入7個元素*/

ListInsert(&Lb,j,b[j-l]);

printf(nLb=H);/*輸出表Lb的內(nèi)容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(MLc=H);/*輸出表Lc的內(nèi)容*/

ListTraverse(Lc,print);

/*algo2-3.c實現(xiàn)算法2.7的程序*/

#includencl.hn

typedefintElemType;

#includenc2-l.hM

#include,,

voidMergeList(SqListLa,SqListLb,SqList?Lc)/*算法2.7*/

{/*已知順序線性表La和Lb的元素按值非遞減排列。*/

/求歸并La和Lb得到新的順序線性表Lc,Lc的元素也按值非遞減排列*/

ElemType*pa,*pa」ast,*pb,*pb」ast,*pc;

pa=La.elem;

pb=Lb.elem;

(*Lc)[istsize=(*Lc).length=La.length+Lb.length;/*不用InitList。創(chuàng)建空表Lc*/

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+LbJength-l;

while(pa<=pa_last&&pb<=pb_last)/*表La和表Lb均非空*/

{/*歸并*/

if(*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(H%d”/c);

voidmain()

(

SqListLa,Lb,Lc;

intj;

InitList(&La);/*創(chuàng)建空表La*/

for(j=l；j<=5;j++)/*在表La中插入5個元素*/

ListInsert(&La,j,j);

printf(',La=");/*輸出表La的內(nèi)容*/

ListTraverse(La,print);

InitList(&Lb);/*創(chuàng)建空表Lb*/

for(j=l;j<=5;j++)/*在表Lb中插入5個元素*/

ListInsert(&Lb,j,2*j);

printf(HLb=M);/*輸出表Lb的內(nèi)容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(nLc=");/*輸出表Lc的內(nèi)容*/

ListTraverse(Lc,print);

)

/*algo2-4.c修改算法2.7的第一個循環(huán)語句中的條件語句為開關(guān)語句，且當*/

/**pa=*pb時，只將兩者中之一插入Lc。此操作的結(jié)果和算法2.1相同*/

#includencl.hH

lypedefintElemType;

#includeHc2-l.h"

#includeH

intcomp(ElemTypecl,ElemTypec2)

inti;

if(cl<c2)

i=l；

elseif(cl==c2)

i=0;

else

i=-l；

returni;

}

voidMergeList(SqListLa,SqListLb,SqListLc)

{/*另一種合并線性表的方法(根據(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=(Ix).elem=(ElemType*)malloc((:Lc).listsize*sizeof(ElemType));

if(!(Lc).elem)

exit(OVERFLOW);

pa_last=La.elem+La.length-1;

pb_last=Lb.eleiTi+LbJength-l;

while(pa<=pa_last&&pb<=pb_last)/*表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(M%dH,*c);

voidmain()

SqListLa,Lb,Lc;

intj;

InitList(&La);/*創(chuàng)建空表La*/

f0r(j=l;j<=5;j++)/*在表La中插入5個元素*/

ListInsert(&Laj,j);

printf(MLa=");/*輸出表La的內(nèi)容*/

ListTraverse(La,print);

InitList(&Lb);/*創(chuàng)建空表Lb*/

for(j=l;j<=5;j++)/*在表Lb中插入5個元素*/

ListInsert(&Lb,j,2*j);

printf(nLb=n);/*輸出表Lb的內(nèi)容*/

ListTraverse(Lb,print);

MergeList(La,Lb,&Lc);

printf(MLc=");/*輸出表Lc的內(nèi)容*/

ListTraverse(Lc,print);

/*algo2-5.c實現(xiàn)算法2.11、2.12的程序*/

#includencl.h"

typedefintElemType;

#includeHc2-2.hM

/*c22h線性表的單鏈表存儲結(jié)構(gòu)*/

structLNode

(

Elemiypedata;

structLNode*next;

)；

typedefstructLNode"LinkList;/*另一種定義LinkList的方法*/

#includenbo2-2.cM

/*bo2-2.c單鏈表線性表(存儲結(jié)構(gòu)由c2-2.h定義)的基本操作(12個)*/

StatusInitList(LinkList*L)

{/*操作結(jié)果：構(gòu)造一個空的線性表L*/

:：:I=(LinkList)malloc(sizeof(structLNode));/*產(chǎn)生頭結(jié)點，并使L指向此頭結(jié)點*/

if(!*L)/*存儲分配失敗*/

exit(OVERFLOW);

(*L)->next=NULL;/*指針域為空*/

returnOK;

)

StatusDestroyList(LinkList::L)

{/*初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L*/

LinkListq;

while(*L)

(

q=(=:L)->next;

free(::<L);

*L=q;

}

returnOK;

)

StatusClearList(LinkListL)/*不改變L*/

{/*初始條件：線性表L已存在。操作結(jié)果：將L重置為空表號

LinkListp,q;

p=L->next;/*p指向第一個結(jié)點*/

vvhile(p)/*沒到表尾*/

{

q=p->next;

free(p);

p=q;

)

L->next=NULL;/*頭結(jié)點指針域為空*/

returnOK;

)

StatusListEmpty(LinkListL)

{/*初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE,否則返回FALSE

/

if(L->next)/*非空*/

returnFALSE;

else

returnTRUE;

intListLength(LinkListL)

{/*初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)*/

inti=0;

LinkListp=L->next;/*p指向第一個結(jié)點*/

while(p)/*沒到表尾*/

{

i++；

p=p->next;

)

returni;

)

StatusGetElem(LinkLi$tL,inti,ElemType*e)/*算法2.8*/

{/*L為帶頭結(jié)點的單鏈表的頭指針。當?shù)趇個元素存在時，其值賦給e并返回OK,否則返

回ERROR*/

intj=l;/*j為計數(shù)器*/

LinkListp=L->next;/*p指向第一個結(jié)點*/

while(p&&j<i)/*順指針向后查找，直到p指向第i個元素或p為空*/

{

p=p->next;

j++；

)

if(!plU>i)/*第i個元素不存在*/

returnERROR;

*e=p->data;/*取第i個元素*/

returnOK;

intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType))

{/*初始條件：線性表L已存在,compare。是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0)*/

/*操作結(jié)果：返回L中第1個與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。東/

/*若這樣的數(shù)據(jù)元素不存在，則返回值為0*/

inti=0;

LinkListp=L->next;

vvhile(p)

(

i++；

if(compare(p->data,e))/*找到這樣的數(shù)據(jù)元素列

returni;

p=p->next;

)

return0;

StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)

{/*初始條件：線性表L已存在*/

/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素,且不是第一個，則用pre_e返回它的前驅(qū),*/

/*返回OK;否則操作失敗,pre_e無定義，返回INFEASIBLE*/

LinkListq,p=L->next;/*p指向第一個結(jié)點*/

while(p->next)/*p所指結(jié)點有后繼*/

{

q=p->next;/*q為p的后繼*/

if(q->data==cur_e)

(

*pre_e=p->data;

returnOK;

)

p=q；/*p向后移*/

)

returnINFEASIBLE;

StatusNextElem(LinkListL,ElemTypecur_e,Elemiype*next_e)

{/*初始條件：線性表L已存在*/

/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼,

/

/*返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE*/

LinkListp=L->next;/*p指向第一個結(jié)點*/

while(p->next)/*p所指結(jié)點有后繼*/

(

if(p->data==cur_e)

*next_e=p->next->data;

returnOK;

p=p->next;

)

returnINFEASIBLE;

StatusListInsert(LinkListL,inti,ElemTypee)/*算法2.9。不改變L*/

{/*在帶頭結(jié)點的單鏈線性表L中第i個位置之前插入元素e*/

intj=O;

LinkListp=L,s;

while(p&&j<i-l)/*尋找第i?l個結(jié)點

(

p=p->next;

j++；

)

if(!pllj>i-l)/*i小于1或者大于表長*/

returnERROR;

s=(LinkList)malloc(sizeof(structLNode));/*生成新結(jié)點*/

s->data=e;/*插入L中*/

s->next=p->next;

p->next=s;

returnOK;

)

StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改變L*/

{/*在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值*/

intj=O;

LinkListp=L,q;

while(p->next&&j<i-l)/*尋找第i個結(jié)點，并令p指向其前趨*/

(

p=p->next;

j++；

)

if(!p->next||j>i-l)/*刪除位置不合理*/

returnERROR;

q=p->next;/*刪除并釋放結(jié)點*/

p->next=q->next;

*e=q->data;

free(q);

returnOK;

StatusListTraverse(LinkListL,void(*vi)(ElemType))

/*vi的形參類型為ElemType，與bo2-l.c中相應(yīng)函數(shù)的形參類型Elem］，pe&不同*/

{/*初始條件：線性表L已存在*/

/*操作結(jié)果:依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗，則操作失敗*/

LinkListp=L->next;

while(p)

(

vi(p->data);

p=p->next;

)

prmtf(,,\nH);

returnOK;

)

voidCreateList(LinkList*L,intn)/*算法CU*/

{/*逆位序(插在表頭)輸入n個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L*/

inti;

LinkListp;

::L=(LinkList)malloc(sizeof(structLNode));

(*L)?>next=NULL;/*先建立一個帶頭結(jié)點的單鏈表為

printf("請輸入％d個數(shù)據(jù)\n”,n);

for(i=n;i>0;-i)

(

p=(LinkList)malloc(sizeof(structLNode));/*生成新結(jié)點*/

scanf(u%d",&p->data);/*輸入元素值*/

p->next=(：i：L)->next;/*插入到表頭*/

(L)->next=p;

)

)

voidCreateList2(LinkList*L,intn)

{/*正位序(插在表尾)輸入n個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表*/

inti;

LinkListp,q;

::L=(LinkList)malloc(sizeof(structLNode));/*生成頭結(jié)點*/

(L)->next=NULL;

q=*L;

printf("請輸入％d個數(shù)據(jù)\n”,n);

fdr(i=l;i<=n;i++)

(

p=(LinkList)malloc(sizeof(structLNode));

scanf(u%d",&p->data);

q->next=p;

q=q->next;

p->next=NULL;

)

voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)/*算法2.12*/

{/*己知單鏈線性表La和Lb的元素按值非遞減排列6*/

/*歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列*/

LinkListpa=La->next,pb=(:Lb)->next,pc;

：i：Lc=pc=La;/*用La的頭結(jié)點作為Lc的頭結(jié)點刃

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的頭結(jié)點*/

Lb=NULL;

)

voidvisit(ElemTypec)/*ListTraverse()調(diào)用的函數(shù)(類型要一致)*/

(

printf(H%d",c);

)

voidmain()

(

intn=5;

LinkListLa,Lb,Lc;

printf("按非遞減順序,

CreateList2(&La,n);/*正位序輸入n個元素的值*/

printf(MLa=u);/*輸出鏈表La的內(nèi)容*/

ListTraverse(La,visit);

printf("按非遞增順序,")；

CreateList(&Lb,n);/*逆位序輸入n個元素的值*/

printf("Lb=");/*輸出鏈表Lb的內(nèi)容*/

ListTraverse(Lb,visit);

MergeLisl(La,&Lb,&Lc);/*按非遞減順序歸并La和Lb,得到新表Lc*/

printf(nLc=u);/*輸出鏈表Lc的內(nèi)容*/

ListTraverse(Lc,visit);

/*algo2-6.c利用單鏈表結(jié)構(gòu)處理教科書圖2.1(學生健康登記表)*/

#includencl.hn

#defineNAMELEN8/*姓名最大長度*/

#defineCLASSLEN4/*班級名最大長度刃

structstud/*記錄的結(jié)構(gòu)*/

(

charname[NAMELEN+l];

longnum;

charsex;

intage;

charClass[CLASSLEN+l];

inthealth;

)；

typedefstructstudElemType;/*鏈表結(jié)點元素類型為結(jié)構(gòu)體*/

#include"c2-2.hn

charsta[3][9]={“健康一般神經(jīng)衰弱”};/*健康狀況(3類)*/

FILE*fp;

StatusInilLisl(LinkList*L)/*拷自bo2-2.c*/

{/*操作結(jié)果：構(gòu)造一個空的線性表L*/

?：:L=(LinkList)malloc(sizeof(structLNode));/*產(chǎn)生頭結(jié)點，并使L指向此頭結(jié)點*/

if(!*L)/*存儲分配失敗刃

exit(OVERFLOW);

(*L)->next=NULL;/*指針域為空*/

returnOK;

)

StatusListTraverse(LinkListL,void(*vi)(ElemType))/*拷自bo2-2.c*/

{/*初始條件：線性表L已存在*/

/*操作結(jié)果:依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗，則操作失敗為

LinkListp=L->next;

while(p)

(

vi(p->data);

p=p->next;

printf("\nn);

returnOK;

voidInsertAscend(LinkListL,ElemTypee)/*此函數(shù)是由bo2-9.c中的同名函數(shù)改寫*/

{/*按學號非降序插入*/

LinkListq=L,p=L->next;

while(p&&e.num>p->data.num)

(

q=p;

p=p->next;

)

q->next=(LinkList)malloc(sizeof(structLNode));/*插在q后*/

q->next->data=e;

q->next->next=p;

)

voidPrint(structstude)

{/*顯示記錄e的內(nèi)容*/

printf(n%-8s%61d",,e.num);

if(e.sex==,m')

printf(H男)

else

printf(H女)

printf(H%5d%-4s",e.age,e.Class);

printf(M%9s\nu,sta[e.health]);

)

voidReadln(structstud*e)

{/*由鍵盤輸入結(jié)點信息*/

prinlf(”請輸入姓名(v=%d個字符):[NAMELEN);

scanf("%sn,e->name);

printf("請輸入學號：");

scanf(,'%ld,',&e->num);

printf("請輸入性別(m:男f:女):");

scanf(,,%*c%c,\&e->sex);

printf(”請輸入年齡:");

scanf(n%d",&e->age);

printf(”請輸入班級(v=%d個字符):n,CLASSLEN);

scanf("％s”,e4class);

printf("請輸入健康狀況(0:%sl:%s2:%s):n,sta[0],sta[l],sta[2]);

scanf("%d",&e->health);

voidWriteToFile(struclstude)

{/*將結(jié)點信息寫入fp指定的文件*/

fwrite(&e,sizeof(struclstud),l,fp);

StatusReadFromFile(structstud*e)

{/*由fp指定的文件讀取結(jié)點信息到e*/

inti;

i=fread(e,sizeof(structstud),l,fp);

if(i==l)/*讀取文件成功*/

returnOK;

else

returnERROR;

StatusFindFromNum(LinkListL,longnum,LinkList*p,LinkList*q)

{/*查找表中學號為num的結(jié)點，如找到,q指向此結(jié)點,p指向q的前驅(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的結(jié)點，如找到,q指向此結(jié)點,p指向q的前驅(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*/

LinkListp,q;

if(FindFromNum(L,num,&p,&q))/*找到此結(jié)點，且q指向其,p指向其前驅(qū)*/

p->next=q->next;

free(q);

returnTRUE;

)

returnFALSE;

StatusDeleteElemName(LinkListL,charname[])

{/*刪除表中姓名為name的元素，并返回TRUE；如無此元素，則返回FALSE*/

LinkListp,q;

if(FindFromName(L,name,&p,&q))/*找到此結(jié)點，且q指向其,p指向其前驅(qū)*/

(

p->next=q->next;

free(q);

returnTRUE;

)

returnFALSE;

voidModify(ElemType*e)

{/*修改結(jié)點內(nèi)容*/

chars[80];

Print(*e);/*顯示原內(nèi)容*/

printf("請輸入待修改項的內(nèi)容，不修改的項按回車鍵保持原值:\n");

prinlf(”請輸入姓名(v=%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[0];

printff請輸入年齡:");

gets(s);

if(strlen(s))

e->age=atoi(s);

prinlf(”請輸入班級(<二%d個字符):",CLASSLEN);

gets(s);

if(strlen(s))

strcpy(e->Class,s);

printf("請輸入健康狀況(0:%sl:%s2:%s):",sta[0],sta[l],sta[2]);

gets(s);

if(strlen(s))

e->health=atoi⑸;/*修改完畢*/

}

#defineN4/*sludent記錄的個數(shù)*/

voidmain()

(

structstudstudent[N]={{"王小林”,790631,'m',18,"計91”,0},

{"陳紅”,790632,f,20,“計91",1),

{"劉建平”,790633；m',21，"計91",0),

{"張立立",790634,17,"計91”,2}};/*表的初始記錄*/

inti,j,flag=l;

longnum;

charfilename[13],name[NAMELEN+1];

ElemTypee;

LinkListT,p,q;

InitList(&T);/*初始化鏈表*/

while(flag)

(

printf(”l:將結(jié)構(gòu)體數(shù)組student中的記錄按學號非降序插入鏈表\n")；

prinlf("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:結(jié)束\n")；

printf("請選擇操作命令:");

scanf(H%d",&i);

switch(i)

(

case1:for(j=0;j<N;j++)

InsertAscend(T,student[j]);

break;

case2:printf(”請輸入文件名：");

scanf(,'%su,filename);

if((fp=fopen(filename,,'rb',))==NULL)

printf("打開文件失敗!\n”);

else

(

while(ReadFromFile(&e))

InsertAscend(T,e);

fclose(fp);

)

break;

case3:Readln(&e);

InsertAscend(T,e);

break;

case4:prinlf("請輸入待刪除記錄的學號:")；

scanf(,'%ld,,,&num);

if(!DeleteElemNum(T,num))

printf("沒有學號為％舊的記錄\n”,num);

break;

case5:printf("請輸入待刪除記錄的姓名：");

scanf("%su,name);

if(!DeleteElemName(T,name))

printf("沒有姓名為％s的記錄\n”,name);

break;

case6:primf("請輸入待修改記錄的學號：”)；

scanf(',%ld%*c,,,&num);/*%*c吃掉回車符

if(!FindFromNum(T,num,&p,&q))

printf("沒有學號為％舊的記錄\n\num);

else

(

Modify(&q->data);

if(q->data.num!=num)/*學號被修改*/

(

p->next=q->next;/*把q所指的結(jié)點從L中刪除*/

InsertAscend(T,q->data);/*把元素插入L*/

free(q);/*刪除q*/

)

)

break;

case7:printf("請輸入待修改記錄的姓名：”)；

scanf(n%s%*cn,name);/*%*c吃掉回車符*/

if(!FindFromName(T,name,&p,&q))

primf("沒有姓名為％$的記錄\n”,name);

else

(

num=q->data.num;/*學號存入num*/

Modify(&q->data);

if(q->data.num!=num)/*學號被修改*/

p->next=q->next;/*把q所指的結(jié)點從L中刪除*/

InsertAscend(T,q->data);/*把元素插入L*/

free(q);/*刪除q*/

)

)

break;

case8:printf("請輸入待查找記錄的學號：”)；

scanf("%ld",&num);

if(!FindFromNum(T,num,&p,&q))

printf("沒有學號為％出的記錄\n”,num);

else

Print(q->data);

break;

case9:prinlf("請輸入待查找記錄的姓名：”)；

scanf(',%s,',naine);

if(!FindFromName(T,name,&p,&q))

printf("沒有姓名為％§的記錄\n”,name);

else

Print(q->data);

break;

case10:printf(n姓名學號性別年齡班級健康狀況\n")；

ListTraverse(T,Print);

break;

casell:printf(”請輸入文件名:");

scanf("%su,filename);

if((fp=fopen(filename,"wb"))==NULL)

printf("打開文件失敗!\n)

else

ListTraverse(T,WriteToFile);

fclose(fp);

break;

case12:flag=0;

/*algo2-7.c教科書中圖2.10靜態(tài)鏈表示例*/

/*第一個結(jié)點的位置在[0].cur中，成員cur的值為0,則到鏈表尾*/

#include"cl.h"

#defineN6/*字符串長度*/

typedefcharElemType[N];

#includeMc2-3.hM

信c2-3.h線性表的靜態(tài)單鏈表存儲結(jié)構(gòu)*/

#defineMAXSIZE100/*鏈表的最大長度刃

typedefstruct

(

ElemTypedata;

intcur;

}component,SLinkList[MAXSIZE];

voidmain()

(

SLinkList

s={{"",1},{“ZHAO”,2},{“QIAN”,3},{“SUN”,4},{“LI”,5},{“ZHOU”,6},{“WU”,7},{“ZHENG”,8}

,{“WANG”,0}};

inti;

i=s[0].cur;

while(i)/*輸出教科書中圖2.10(a)的狀態(tài)*/

(

printf(H%s\s[i].data);/*輸出鏈表的當前值*/

i=s[i].cur;/*找到下一個*/

)

printf(,'\nn);

s[4].cur=9;/*按教科書中圖2.10(b)修改*/

s[6].cur=8;

s[9].cur=5;

strcpy(s[9].data；,SHIH);

i=s[0].cur;

while(i)/*輸出教科書中圖2.10(b)的狀態(tài)*/

(

printf(n%s\s[i].data);/*輸出鏈表的當前值*/

i=s[i].cur;/*找到下一個*/

}

printf(n\nn);

)

/*algo2-8.c實現(xiàn)算法2.17的程序*/

#includencl.hn

#defineN2

typedefcharElemType;

#includeMc2-3.hM

#indudenbo2-3.cM

/*bo2-3.c實現(xiàn)算法2.15、2.16的程序(數(shù)據(jù)結(jié)構(gòu)由c2-3.h定義)(3個)*/

intMalloc(SLinkListspace)/*算法2.15*/

{/*若備用鏈表非空，則返回分配的結(jié)點下標(備用鏈表的第一個結(jié)點)，否則返回0*/

inti=space[O].cur;

if(i)/*備用鏈表非空刃

space[O].cur=space[i].cur;/*備用鏈表的頭結(jié)點指向原備用鏈表的第二個結(jié)點*/

returni;/*返回新開辟結(jié)點的坐標*/

voidFree(SLinkListspace,intk)/*算法2.16*/

{譯將下標為k的空閑結(jié)點回收到備用鏈表(成為備用鏈表的第一個結(jié)點)*/

space[k].cur=space[O].cur;P回收結(jié)點的“游標”指向備用鏈表的第一個結(jié)點*/

space[O]