數(shù)據(jù)結(jié)構(gòu)常用算法實(shí)現(xiàn)print

資料范本本資料為word版本，可以直接編輯和打印，感謝您的下載數(shù)據(jù)結(jié)構(gòu)常用算法實(shí)現(xiàn)print地點(diǎn)： 時(shí)間： 說明：本資料適用于約定雙方經(jīng)過談判，協(xié)商而共同承認(rèn)，共同遵守的責(zé)任與義務(wù)，僅供參考，文檔可直接下載或修改，不需要的部分可直接刪除，使用時(shí)請(qǐng)?jiān)敿?xì)閱讀內(nèi)容線性表的順序表示程序2_1.c提供了順序存儲(chǔ)結(jié)構(gòu)下線性表的實(shí)現(xiàn)。第1行定義了一個(gè)常數(shù)值MAXSIZE。它是一個(gè)常數(shù)，表示線性表的最大長(zhǎng)度。第2行把ELEMTYPE設(shè)置為int的一個(gè)別名。這樣，這個(gè)例子就可以使用一組整數(shù)了。第3行到第7行包含了線性表的說明。接下來從第8行到第46行線性表運(yùn)算函數(shù)的定義。第8到第11行將線性表置成空表，只需簡(jiǎn)單地將線性表元素個(gè)數(shù)置成0即可。由于線性表的長(zhǎng)度已經(jīng)記錄在結(jié)構(gòu)成員length中，因此求線性表的長(zhǎng)度（第35行到第38行）只是返回length的值。第20到第24行是追加函數(shù)，函數(shù)append在線性表的表尾插入一個(gè)元素。第12行到第19行是插入函數(shù)。在表中第i位置插入一個(gè)新元素item時(shí)，需將i，i+1，…，n-1位置上的元素向后移，變成編號(hào)為i+1，i+2，…，n，然后將item插入到第i個(gè)位置，且線性表的長(zhǎng)度加1。第25行到第34行是刪除元素。要?jiǎng)h去表中位置i上的元素，同樣需要移動(dòng)表中元素，使原編號(hào)為i+1，i+2，…，n-1的元素變成編號(hào)為i，i+1，…，n-2,并將表的長(zhǎng)度減1。第39行到第46行的函數(shù)find在線性表中查找第一個(gè)出現(xiàn)的值為item的元素。如果值item找到了，函數(shù)返回元素item所在位置1，否則返回-1。第54行到第67行是main函數(shù)的一個(gè)例子，說明了線性表的使用。57行調(diào)用clear函數(shù)將線性表清空，第58，59，60三行調(diào)用append函數(shù)追加三個(gè)元素，第62行在位置2插入一個(gè)元素15,第65行調(diào)用delete函數(shù)刪除位置3的元素。第47行到53行的print函數(shù)是為了顯示線性表中的數(shù)據(jù)而設(shè)置的。程序2_1.c#defineMAXSIZE999typedefintELEMTYPE;structlist（ELEMTYPElistarray[MAXSIZE];

8 void9 {1011121314151617181920212224252627282930intlength;};structlistl;clear()l.length=0;}voidinsert(intpos,ELEMTYPEitem)(inti;for(i=l.length;i>pos;i--)l.listarray[i]=l.listarray[i-1];l.listarray[pos]=item;l.length++;}voidappend(ELEMTYPEitem)(l.listarray[l.length++]=item;}ELEMTYPEdelete(intpos)(inti;ELEMTYPEtemp;temp=l.listarray[pos];for(i=pos;i<l.length-1;i++)

31323335(3739404243444547485051525455575859606162l.listarray[i]=l.listarray[i+1];l.length--;returntemp;}intlength()returnl.length;}intfind(ELEMTYPEitem)(inti;for(i=0;i<l.length;i++)if(l.listarray[i]==item)returni;return-1;}voidprint()(inti;for(i=0;i<l.length;i++)printf("%d〃，l.listarray[i]);printf("\n");}voidmain()(clrscr();clear();append(10);/*Lis10*/append(20);/*Lis(10,20)*/append(30);/*Lis(10,20,30)*/print();insert(2,15); /*Lis(10,20,15,30)*/

print();printf("\n%d",find(100));printf("\n%d\n",delete(3));/*Lis(10,20,15)*/print();}線性表的鏈?zhǔn)奖硎境绦?_2.c提供了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下線性表的實(shí)現(xiàn)。第3行到第8行包含了線性表中結(jié)點(diǎn)的說明，其中element表示數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息，next為指針域，指明該結(jié)點(diǎn)的唯一后繼結(jié)點(diǎn)在內(nèi)存中的存放地址，或是在該結(jié)點(diǎn)序列中所在的物理位置。線性鏈表由head和tail表示。接下來從第9行到第76行線性表運(yùn)算函數(shù)的定義。第9行到第14行初始化單鏈表。head指針與tail指針指向表頭結(jié)點(diǎn)。在單鏈表的最后一個(gè)結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)只要將單鏈表尾指針tail指向新插入結(jié)點(diǎn)，新插入結(jié)點(diǎn)成為最后一個(gè)結(jié)點(diǎn)即可。第15行到第20行函數(shù)append實(shí)現(xiàn)追加一個(gè)新結(jié)點(diǎn)到單鏈表的最后，新結(jié)點(diǎn)的元素值為item。malloc是C語言提供的標(biāo)準(zhǔn)函數(shù)，其功能是申請(qǐng)存儲(chǔ)空間。設(shè)p是指向單鏈表中一個(gè)結(jié)點(diǎn)的指針，在p指向的結(jié)點(diǎn)后面插入一個(gè)結(jié)點(diǎn)包括三個(gè)步驟。首先，要?jiǎng)?chuàng)建一個(gè)新的結(jié)點(diǎn)，并且賦給它一個(gè)新的值。其次，新結(jié)點(diǎn)的next指向指針p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)。第三，指針p指向的結(jié)點(diǎn)的next要指向新插入的結(jié)點(diǎn)。第21行到第38行函數(shù)insert實(shí)現(xiàn)在單鏈表的第i個(gè)結(jié)點(diǎn)前面插入一個(gè)新結(jié)點(diǎn)。新結(jié)點(diǎn)的元素值為item，s為指向新結(jié)點(diǎn)的指針。算法在實(shí)現(xiàn)時(shí)，首先查找新結(jié)點(diǎn)插入位置，然后根據(jù)上面所述修改相應(yīng)指針。從單鏈表刪去一個(gè)結(jié)點(diǎn)只需將被刪結(jié)點(diǎn)的前趨結(jié)點(diǎn)的next域指向被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)即可。但必須注意，被刪結(jié)點(diǎn)占據(jù)的內(nèi)存空間應(yīng)該返回給存儲(chǔ)器。因此可設(shè)一個(gè)臨時(shí)指針指向要?jiǎng)h去的結(jié)點(diǎn)，而后調(diào)用C語言提供的標(biāo)準(zhǔn)過程free將被刪去的結(jié)點(diǎn)占據(jù)的內(nèi)存空間返回給存儲(chǔ)器。第39行到第57行的函數(shù)delete實(shí)現(xiàn)刪除結(jié)點(diǎn)運(yùn)算。第58行到第65求單鏈表中所含結(jié)點(diǎn)的個(gè)數(shù)。為求單鏈表的結(jié)點(diǎn)個(gè)數(shù)，我們必須從單鏈表表頭開始，沿著每個(gè)結(jié)點(diǎn)的鏈指針，依次向后訪問并計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)位置。程序2_2.c#include<alloc.h>typedefintELEMTYPE;structlist(ELEMTYPEelement;structlist*next;TOC\o"1-5"\h\z);struct list *head;struct list *tail;voidinit()(head= malloc(sizeof(structlist));head->next= NULL;tail= head;}voidappend(ELEMTYPEitem)(tail二tail->next=(structlist *)malloc(sizeof(structlist));tail->element=item;tail->next=NULL;}

21222324252627282930313233343536373839404142434445intinsert(intpos,ELEMTYPEitem)(structlist*p,*s;intj;s=(structlist*)malloc(sizeof(structlist));s->element=item;p=head;j=1;while((p!=NULL)&&(j<pos))(p=p->next;j++;}if((!p)||(j>pos))return0;s->next=p->next;p->next=s;if(tail==p)tail=s;return1;}ELEMTYPEdelete(intpos)(structlist*p,*q;ELEMTYPEtemp;intj;q=p;p=head->next;j=1;

46474849505152535455565758596061626364656667686970while((p!=NULL)&&(j<pos))(q=p;p=p->next;j++;}if((!p)||(j>pos))return0q->next=p->next;temp=p->element;if(tail==p)tail=q;free(p);returntemp;}intlength()(structlist*p;intcnt=0;for(p=head->next;p!=NULL;p=p->next)cnt++;returncnt;}intfind(ELEMTYPEitem)(structlist*p=head->next;while(p!=NULL)(if(p->element==item)

717273747576777879808182838485868788899091929394(10,20,30,return1;elsep=p->next;}return0;}voidprint()(structlist*p;printf("\n");for(p=head->next;p!二NULL;p=p->next)printf("%d",p->element);}voidmain()(clrscr();init();append(10);/*listis(10)*/append(20);/*listis(10,20)*/append(30);/*listis(10,20,30)*/append(40);/*listis(10,20,30,40)*/insert(3,35); /*listis(10,20,30,35,40)*/print();printf("\n%d\n",delete(4));/*listis35)*/

95print();9596 }棧程序2_3.c是棧數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，第3行到第6行包含棧類型的說明，top被定義為表示棧中最上面那個(gè)元素的位置。push（第13行到第17行）和pop（第18行到第22行）只是從top指示的數(shù)組中的位置插入和刪去一個(gè)元素，因?yàn)閠op表示棧頂元素的位置，所以push首先把一個(gè)值插入到棧頂位置，然后把top加1。同樣，pop首先把top減1，然后刪去棧頂元素。函數(shù)topValue（第23行到27行）只是將棧頂元素返回。如果棧中沒有元素，函數(shù)isEmpty（第28行到第31行）返回1，否則返回0。程序2_3.c#include<assert.h>#include<stdio.h>#defineMAXSIZE100typedefintELEMTYPE;structstack（ELEMTYPElistarray[MAXSIZE];inttop;};structstacks;voidinit（）（s.top=0;}

voidpush(ELEMTYPEitem)(assert(s.top<MAXSIZE);s.listarray[s.top++]=item;}ELEMTYPEpop()(intisEmpty();assert(!isEmpty());returns.listarray[--s.top];}ELEMTYPEtopValue()(intisEmpty();assert(!isEmpty());returns.listarray[s.top-1];}intisEmpty()(returns.top==0;}voidmain()(init();push(10);/*sis(10)*/push(10);/*sis(10)*/push(20); /*sis(20,10)*/printf(〃％d〃，topValue());/*returntopelement20*/printf(〃\n〃)；printf("%d",pop());/*sis(10)*/}程序2_4.c給出了鏈?zhǔn)綏１硎竞透鞣N運(yùn)算的算法。其中top是指向鏈?zhǔn)綏５谝粋€(gè)結(jié)點(diǎn)(棧頂)的指針。進(jìn)棧操作(第13行到第21行)首先申請(qǐng)一個(gè)新結(jié)點(diǎn)，并初始化該結(jié)點(diǎn)，然后修改新產(chǎn)生的結(jié)點(diǎn)的next域指向棧頂，并設(shè)置top指向新的鏈表結(jié)點(diǎn)。第22行到第32行是出棧操作。變量temp用來存儲(chǔ)棧頂結(jié)點(diǎn)的值，ltemp用于在刪去棧頂結(jié)點(diǎn)時(shí)保持與棧的鏈接，它指向當(dāng)前棧頂鏈接到的結(jié)點(diǎn)。此時(shí)把原來的棧頂結(jié)點(diǎn)釋放回內(nèi)存，恢復(fù)top等于ltemp。也就是指向原來?xiàng)ｍ旀溄拥慕Y(jié)點(diǎn)，原來?xiàng)ｍ數(shù)闹祎emp作為pop函數(shù)的返回值。程序2_4.c#include<malloc.h>#include<stdio.h>#include<assert.h>typedefintELEMTYPE;structnode(ELEMTYPEelem;structnode*next;};structnode*top;voidinit()(top=NULL;}voidpush(ELEMTYPEitem)(structnode*p;if((p=(structnode*)malloc(sizeof(structnode)))!=NULL)(p->elem=item;p->next=top;top=p;}}ELEMTYPEpop()(intisEmpty();ELEMTYPEtemp;structnode*ltemp;assert(!isEmpty());temp=top->elem;ltemp=top->next;free(top);top=ltemp;returntemp;}ELEMTYPEtopValue()

intisEmpty();intisEmpty();assert(!isEmpty());returntop->elem;}intisEmpty()(returntop==NULL;}voidmain()(init();push(10); /*sis(10)*/push(20); /*sis(20,10)*/push(30); /*sis(30,20,10)*/printf("%d\n",topValue());printf("%d\n",pop());/*sis(20,10)*/}隊(duì)列在程序2_5.c中，q表示循環(huán)隊(duì)列(第3行到第9行)，其隊(duì)頭與隊(duì)尾指示變量分別為front和rear。隊(duì)列中的元素類型為int(第3行)。函數(shù)enqueue(第14行到第19行)執(zhí)行隊(duì)列的插入操作，參數(shù)item是插入隊(duì)列的元素。當(dāng)隊(duì)列不滿時(shí)，enqueue首先移動(dòng)隊(duì)尾指針，然后將item置入rear所指位置。函數(shù)dequeue(第20行到25行)執(zhí)行隊(duì)列的刪除操作，返回從隊(duì)列中取出的元素。函數(shù)firstValue(第26行到第30行)返回隊(duì)列頭元素。程序2_5.c#include<assert.h>#include<stdio.h>#defineMAXSIZE100typedefintELEMTYPE;structqueue(intfront;intrear;ELEMTYPEelem[MAXSIZE];};structqueueq;voidinit()(q.front=q.rear=0;}voidenqueue(ELEMTYPEitem)(assert(((q.rear+1)%MAXSIZE)!=q.front);q.rear=(q.rear+1)%MAXSIZE;/*incrementrear*/q.elem[q.rear]=item;}ELEMTYPEdequeue()/*dequeueelementfrofrontofqueue*/(intisEmpty();assert(!isEmpty());/*theremustbesomethingtodequeue*/q.front=(q.front+1)%MAXSIZE;/*incrementfront*/q.front=returnq.elem[q.front];/*returnvalue*/}ELEMTYPEfirstValue()/*getvalueoffrontelement*/(intisEmpty();assert(!isEmpty());returnq.elem[(q.front+1)%MAXSIZE];}intisEmpty()/*TRUEisqueueisempty*/(returnq.front==q.rear;}voidmain()(init();enqueue(10); /* q is (10)*/enqueue(20); /* q is (10,20)*/enqueue(30); /* q is (10,20,30)*/printf("%d\n",firstValue());/*willdisplay10*/printf("%d\n",dequeue());/*willdispla10*/}程序2_6.c給出了鏈?zhǔn)疥?duì)列的說明和函數(shù)的實(shí)現(xiàn)。front和rear分別是指向隊(duì)首和隊(duì)尾元素的指針。鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)不需要表頭結(jié)點(diǎn)，當(dāng)隊(duì)列為空時(shí)，指針front和rear的值均為空（NULL）。當(dāng)在隊(duì)列中插入一個(gè)結(jié)點(diǎn)時(shí)(第14行到27行)，新結(jié)點(diǎn)鏈入rear所指結(jié)點(diǎn)的next域，并使rear指向新的結(jié)點(diǎn)。如果在插入之前隊(duì)列為空，則指針front指向新插入的結(jié)點(diǎn)。當(dāng)從隊(duì)列中刪除一個(gè)結(jié)點(diǎn)時(shí)(第28行到37行)，要把front所指結(jié)點(diǎn)的next域的值賦給front，并且釋放這個(gè)結(jié)點(diǎn)。如果刪除之后隊(duì)列為空，則置指針rear為空(NULL)。程序2_6.c#include<malloc.h>#include<stdio.h>#include<assert.h>typedefintELEMTYPE;structnode(ELEMTYPEelem;structnode*next;};structnode*front;structnode*rear;voidinit()(rear=front=NULL;}voidenqueue(ELEMTYPEitem)(if(rear!=NULL)(rear->next=(structnode*)malloc(sizeof(structnode));rear->next->elem=item;rear->next->next=NULL;rear=rear->next;}else(front=rear=(structnode*)malloc(sizeof(structnode));front->elem=item;front->next=NULL;}}ELEMTYPEdequeue()(intisEmpty();ELEMTYPEtemp=front->elem;structnode*ltemp=front;assert(!isEmpty());front=front->next;free(ltemp);if(front==NULL)rear=NULL;returntemp;}ELEMTYPEfirstValue()(intisEmpty();assert(!isEmpty());returnfront->elem;}intisEmpty()(returnfront==NULL;}voidmain()(init();enqueue(10);enqueue(20);enqueue(30);printf("%d\n",firstValue());printf(〃％d\n〃，dequeue());}稀疏矩陣程序3_1.c是按照快速轉(zhuǎn)置算法求矩陣的轉(zhuǎn)置。程序第2行給出稀疏矩陣a的三元組表表示。函數(shù)FastTranspose按照快速轉(zhuǎn)置算法思想將稀疏矩陣a轉(zhuǎn)置為稀疏矩陣b，b也表示為三元組表形式。第11行到第13行計(jì)算矩陣a的每一列的非零元素個(gè)數(shù)。第15行計(jì)算a中每一列第一個(gè)非零元素在b中的起始位置。第16行第22行對(duì)a中的元素依此進(jìn)行轉(zhuǎn)置。程序3_1.c#defineMAXCOL100inta[][3]={{7,6,8},{0,0,5},{0,3,2},{0,5,8},{1,1,6},{1,2,9},{2,3,3},{4,0,9},{5,2,2}};intb[9][3];

5{678910111213141516171819202122232425262728FastTranspose(inta[][3],intb[][3])intm,n,tn,i,j;ints[MAXCOL],t[MAXCOL];m=a[0][0]; n=a[0][1]; tn=a[0][2];b[0][0]=n; b[0][1]=m; b[0][2]=tn;if(tn<=0)return;for(i=0;i<n;i++)s[i]=0;for(i=1;i<=tn;i++)s[a[i][1]]=s[a[i][1]]+1;t[0]=1;for(i=1;i<n;i++) t[i]=t[i-1]+s[i-1];for(i=1;i<=tn;i++)(j=a[i][1];b[t[j]][0]=a[i][1];b[t[j]][1]=a[i][0];b[t[j]][2]=a[i][2];t[j]=t[j]+1;}}main()(inti;clrscr();for(i=0;i<=8;i++)

29printf("%d%d%d\n”,a[i][0],a[i][1],a[i][2]);29FastTranspose(a,b);printf(〃\n〃)；for(i=0;i<=8;i++)printf("%d%d%d\n”,b[i][0],b[i][1],b[i][2]);}程序3_2.c是求矩陣的乘積。程序第1行給出稀疏矩陣a的行數(shù)，程序第2行給出稀疏矩陣a的列數(shù)(b的行數(shù))，程序第3行給出稀疏矩陣的列數(shù)。第4行和第5行給出矩陣a與b的三元組表。第6行定義存放a與b相乘的結(jié)果c(二維數(shù)組)。第7行到第27行的MatrixMultiply函數(shù)實(shí)現(xiàn)稀疏矩陣相乘。此算法中數(shù)組S和T的意義與矩陣轉(zhuǎn)置中相同，分別表示矩陣B中各行非零元素個(gè)數(shù)和各行第一個(gè)非零元素在數(shù)組b中的位置。在找B中某行的所有非零元素時(shí)，只要知道此行第一個(gè)非零元素在b中的位置和下一行第一個(gè)非零元素在b中的位置即可。例如，在B中行號(hào)為i所有非零元素，就是在b中從T[i]到T[i+1]-1的這些元素。對(duì)于在B中最后一行n，實(shí)際上它沒有“下一行”了，只是為了求T[n+1]，又虛設(shè)了第n+1行，且T[n+1]的值為t2+1。程序3_2.c#defineM3#defineP4#defineN2inta[][3]={{3,4,4},{0,0,3},{0,3,2},{1,1,1},{2,0,2}};intb[][3]={{4,2,3},{0,1,2},{2,0,2},{3,1,1}};intc[M][N];MatrixMultiply(){

9101112131415161718192021222324252627282930313233intm,n,t1,t2,i,j,p,k;ints[P],t[P];m=a[0][0];n=a[0][1];t1=a[0][2];if(n==b[0][0])(p=b[0][1];t2=b[0][2];}if(t1*t2==0)return;for(i=0;i<n;i++)s[i]=0;for(i=1;i<=t2;i++)s[b[i][0]]=s[b[i][0]]+1;t[0]=1;for(i=1;i<n+1;i++)t[i]=t[i-1]+s[i-1];for(i=1;i<=t1;i++)(k=a[i][1];for(j=t[k];j<=t[k+1]-1;j++)c[a[i][0]][b[j][1]]+=a[i][2]*b[j][2];}}main()(inti,j;clrscr();MatrixMultiply();}

二叉樹遍歷在程序4_1.c中，函數(shù)inorder實(shí)現(xiàn)中序周游二叉樹的遞歸算法，周游時(shí)輸出所訪問結(jié)點(diǎn)的值。程序中第2行定義二叉樹結(jié)點(diǎn)元素類型為字符型，第3行到第7行定義二叉樹結(jié)點(diǎn)類型，第8行定義root為二叉樹的根結(jié)點(diǎn)指針。第24行到第31行的inorder函數(shù)首先檢查樹是否為空(如果為空，則周游完成；并且函數(shù)直接返回)，否則對(duì)左子樹遞歸調(diào)用本函數(shù)，當(dāng)左子樹周游完成后，對(duì)根結(jié)點(diǎn)調(diào)用printf函數(shù)打印結(jié)點(diǎn)的值(或者按照需要完成某些運(yùn)算)。最后，對(duì)右子樹進(jìn)行同樣的操作。setup函數(shù)利用前序結(jié)果序列建立二叉樹。Setup掃描一個(gè)字符串，若當(dāng)前字符不為‘.’，則申請(qǐng)一個(gè)結(jié)點(diǎn)，存入當(dāng)前字符，并置該結(jié)點(diǎn)的左、右指針為空。然后用該結(jié)點(diǎn)的左鏈和右鏈存放子樹根結(jié)點(diǎn)的指針，遞歸調(diào)用函數(shù)setup，建立當(dāng)前結(jié)點(diǎn)的左子樹和右子樹。當(dāng)?shù)竭_(dá)字符串的末尾時(shí)，建立二叉樹的過程結(jié)束。第32行到第37行是main函數(shù)的一個(gè)例子，首先調(diào)用函數(shù)setup建立一棵二叉樹。然后調(diào)用inorder函數(shù)對(duì)二叉樹進(jìn)行中序周游。程序4_1.c#include<alloc.h>typedefcharELEMTYPE;structBinNode(ELEMTYPEelement;structBinNode*left;structBinNode*right;);structBinNode*root;voidsetup(structBinNode**t)(

11121314151617BinNode));1819202122232425262728293031323334ELEMTYPEch;structBinNode*p;scanf(〃％c〃,&ch);if(ch=='.')*t=NULL;else(p=(structBinNode*)malloc(sizeof(structp->element=ch;*t=p;setup(&(p->left));setup(&(p->right));}}voidinorder(structBinNode*t)(if(t!=NULL)(inorder(t->left);printf("%c",t->element);inorder(t->right);}}voidmain()(clrscr();

35setup(&root);35setup(&root);inorder(root);}程序4_2.c實(shí)現(xiàn)二叉樹周游的非遞歸算法。為了實(shí)現(xiàn)非遞歸算法，要在程序中設(shè)置一個(gè)棧結(jié)構(gòu)，用以保存指向結(jié)點(diǎn)的指針，以便能夠繼續(xù)周游。第16行到第33是第3章中順序棧的實(shí)現(xiàn)。第34行到第48行的函數(shù)setup與程序4_1.c功能相同。第49行到第63的inorder函數(shù)實(shí)現(xiàn)二叉樹中序周游。對(duì)于inorder函數(shù)來說，首先從二叉樹的根結(jié)點(diǎn)開始周游，令指針變量p指向當(dāng)前訪問結(jié)點(diǎn)，只是在訪問結(jié)點(diǎn)之前，若p所指結(jié)點(diǎn)的左鏈不空，則沿著其左鏈前進(jìn)，在前進(jìn)過程中，把經(jīng)過的結(jié)點(diǎn)指針值逐一壓棧。這個(gè)過程一直重復(fù)到p為空，從而實(shí)現(xiàn)周游左子樹。然后，如果棧不空，則從棧中彈出一個(gè)結(jié)點(diǎn)的指針值，訪問這個(gè)結(jié)點(diǎn)。接下來，p取其右鏈的值，實(shí)現(xiàn)周游右子樹。整個(gè)周游過程是在一個(gè)do-while循環(huán)中進(jìn)行。只有當(dāng)p為空，而且棧也為空時(shí)，do-while循環(huán)結(jié)束，周游結(jié)束。程序4_2.c#include<alloc.h>#include<assert.h>#defineMAXSIZE100typedefcharELEMTYPE;structBinNode(ELEMTYPEelement;struct BinNode *left;struct BinNode *right;};struct stack(

11121314151617181920212223242526272829303132333435structBinNode*listarray[MAXSIZE];inttop;};structBinNode*root;structstacks;voidinit()(s.top=0;}voidpush(structBinNode*item)(assert(s.top<MAXSIZE);s.listarray[s.top++]=item;}structBinNode*pop()(assert(!isEmpty());returns.listarray[--s.top];}intisEmpty()(returns.top==0;}voidsetup(structBinNode**t)(

36373839404142BinNode));4344454647484950515253545556575859ELEMTYPEch;structBinNode*p;scanf(〃％c〃,&ch);if(ch=='.')*t=NULL;else(p=(structBinNode*)malloc(sizeof(structp->element=ch;*t=p;setup(&(p->left));setup(&(p->right));}}voidinorder(structBinNode*t)(structBinNode*p=t;do(while(p!=NULL)(push(p);p=p->left;}if(!isEmpty())(p=pop();printf("%c",p->element);

60p=p->right;60TOC\o"1-5"\h\z}}while(!(p==NULL&&isEmpty()));}voidmain()(clrscr();init();setup(&root);inorder(root);}Huffman樹程序4_3.c按照Huffman算法由已知的權(quán)集構(gòu)造Huffman樹并求Huffman編碼。第2行定義權(quán)集元素個(gè)數(shù)。第3行定義Huffamn樹結(jié)點(diǎn)個(gè)數(shù)。第4行到第9行定義Huffamn樹結(jié)點(diǎn)類型，結(jié)點(diǎn)類型由權(quán)值、雙親、左子樹和右子樹組成。第10行到第13行定義Huffamn編碼結(jié)構(gòu)，由存放編碼的數(shù)組和編碼的開始位置組成。第14行的數(shù)組weight存放權(quán)值，第15行數(shù)組HT用來存放Huffman樹，第16行數(shù)組HC用于存放Huffman編碼。第17行到26行的init函數(shù)用于初始化Huffman樹。將由n個(gè)權(quán)值作為葉結(jié)點(diǎn)存放到數(shù)組HT的前n個(gè)分量中。第27行到38行函數(shù)minimum從數(shù)組weight中求出當(dāng)前最小的元素，并用一個(gè)大數(shù)HUGE把weight中的最小元素沖掉，返回最小元素所在位置。函數(shù)huffmantree按照huffman算法的基本思想，不斷將兩個(gè)子樹合并為一個(gè)較大的子樹，每次構(gòu)成的新子樹的根結(jié)點(diǎn)順序存放到數(shù)組HT中的前n個(gè)分量的后面。函數(shù)huffmancode求每個(gè)葉結(jié)點(diǎn)的huffman編碼。從該葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親域回退到根結(jié)點(diǎn)，每回退一步，就走過了huffman樹中的一個(gè)分支，從而得到一位huffman編碼值。對(duì)于第i個(gè)葉結(jié)點(diǎn)，其huffman編碼存放在HC[i].bit中從HT[i].start到n的分量上。程序4_3.c#defineHUGE999#defineN8#defineM2*N-1structHuffmanNode(intweight;intparent;intleft;intright;TOC\o"1-5"\h\z);struct HuffmanCode (intbit[10];intstart;);intweight：]={5,29,7,8,14,23,3,11,0,0,0,0,0,0,0};struct HuffmanNode HT[M];struct HuffmanCode HC[N];voidinit(){inti;for(i=0;i<M;i++){HT[i].parent=0;HT[i].weight=weight[i];

23242526272829303132333435363738394041424344454647HT[i].left=0;HT[i].right=0;}}intminimum()(inti,k;intmin=HUGE;for(i=0;i<M;i++)if(min>weight[i]&&weight[i]!=0)(min=weight[i];k=i;}weight[k]=HUGE;returnk;}voidhuffmantree()(inti,l,r;for(i=N;i<M;i++)(=minimum();r=minimum();HT[l].parent=i;HT[r].parent=i;HT[i].left=l;

48495051525354555657585960616263646566676869cd.bit[j];7071HT[i].right=r;HT[i].weight=HT[l].weight+HT[r].weight;weight[i]=HT[i].weight;}}voidhuffmancode()(inti,p,j,c;structHuffmanCodecd;for(i=0;i<N;i++)(cd.start=N-1;c=i;p=HT[c].parent;while(p!=0)(if(HT[p].left==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HT[c].parent;}for(j=cd.start+1;j<N;j++)HC[i].bit[j]=HC[i].start=cd.start;

}voidmain()(inti,j;clrscr();init();huffmantree();for(i=0;i<M;i++)80printf(〃％d%d%d%d\n〃，HT[i].weight,HT[i].parent,HT[i].left,HT[i].right);81printf(〃\n〃)；82huffmancode();83for(i=0;i<N;i++)(84printf("%5d:〃,HT[i].weight);85for(j=HC[i].start+1;j<N;j++)86printf("%d〃，HC[i].bit[j])87printf(〃\n〃)；88}89}深度優(yōu)先遍歷在程序5_1.c，我們用鄰接表表示圖。用一維數(shù)組visited[w]標(biāo)記頂點(diǎn)w是否被訪問過。程序第3行到第7行定義圖的鄰接表存儲(chǔ)結(jié)構(gòu)。函數(shù)setup建立n個(gè)頂點(diǎn)的鄰接表，該函數(shù)首先將鄰接表的頭結(jié)點(diǎn)初始化為空(第14行)，然后依次輸入相鄰頂點(diǎn)(vivj)，并將vj鏈入vi的鏈表中。輸入過程直到出現(xiàn)(vi=0vj=0)結(jié)束。第24行到第37行的函數(shù)print用于打印鄰接表的全部?jī)?nèi)容。在打印的結(jié)果中，第一列整數(shù)為圖中各頂點(diǎn)的序號(hào)，同一行的是該頂點(diǎn)的相鄰頂點(diǎn)。第38行到第52行的dfs函數(shù)實(shí)現(xiàn)以參數(shù)v為起點(diǎn)的深度優(yōu)先搜索。指針p指向頂點(diǎn)v的第一個(gè)相鄰頂點(diǎn)，在執(zhí)行函數(shù)dfs時(shí)沿著v的鄰接表前進(jìn)。程序5_1.c#include<alloc.h>#defineMAXVERTEX100structEdgeNode(intvertex;structEdgeNode*next;);structEdgeNode*a[MAXVERTEX];intvisited[MAXVERTEX];voidsetup(intn)10(11intvi,vj;12inti;13structEdgeNode*p;14for(i=0;i<n;i++)a[i]=NULL;15scanf(〃％d%d〃，&vi,&vj);16while(vi>=0)(

17EdgeNode))1819202122232425262728293031323334353637383940(structEdgeNode*)malloc(sizeof(structp->vertex=vj;p->next=a[vi];a[vi]=p;scanf(〃％d%d〃，&vi,&vj);}}voidprint(intn)(structEdgeNode*p;inti;for(i=0;i<n;i++)(printf("%d",i);p=a[i];while(p!=NULL)(printf("%d",p->vertex);p=p->next;}printf("\n");}}voidDFS(intv)(structEdgeNode*p;

414243444546474849505152535455565758596061626364inti;visited[v]=1;p=a[v];while(p!=NULL)(=p->vertex;if(!visited[i])(printf("(%d,%d)",v,i);DFS(i);}p=p->next;}}voidmain()(intn,i;clrscr();printf("Pleaseinputvertexnumberofgraph:");scanf(〃%d〃,&n);for(i=0;i<n;i++)visited[i]=0;setup(n);print(n);printf("Orderintraversbydfs...”);DFS(0);}最小生成樹

在程序5_2.c中，第1行定義常量HUGE為大于圖中邊的權(quán)最大值，第3行到第8行給出了加權(quán)圖的鄰接矩陣，其中N為圖的頂點(diǎn)個(gè)數(shù)。第9行到第36行的函數(shù)prim實(shí)現(xiàn)Prim算法，在這個(gè)函數(shù)里，matrix表示帶權(quán)圖的鄰接矩陣。為了便于選出權(quán)最小的邊，我們引入兩個(gè)數(shù)組CloseVertex和LowCost，CloseVertex[i]表示最小代價(jià)生成樹中的一個(gè)頂點(diǎn)，該頂點(diǎn)和不是最小代價(jià)生成樹中的一個(gè)頂點(diǎn)i構(gòu)成的邊（CloseVertex[i]，i）具有最小的權(quán)。LowCost[i]表示邊（CloseVertex[i]，i）的權(quán)。起初（第14行到第17行）我們將頂點(diǎn)0作為生成樹的頂點(diǎn)，所以，CloseVertex[i]的值為0，i=1，2，…，n-1。而LowCost[i]為邊（0，i）的權(quán)，i=1，2，…，n-1。由于n個(gè)頂點(diǎn)的連通圖共有n-1條邊，所以，選擇邊的過程共需要重復(fù)n-1次。每次掃描數(shù)組LowCost，找出當(dāng)前與生成樹中頂點(diǎn)最近的頂點(diǎn)，令其為w，得到生成樹的一條邊（w，CloseVertex[w]）（第23行到第27行）。然后，令LowCost[w]=0（表示頂點(diǎn)w已在最小生成樹中），由于頂點(diǎn)w加入最小生成樹中后，可能引起其它頂點(diǎn)的LowCost發(fā)生變化，因此第30行到第34行修改數(shù)組LowCost和CloseVertex。第37到第45行的PrintMatrix函數(shù)輸出加權(quán)圖的鄰接矩陣。程序5_2.c#defineHUGE999#defineN6intmatrix[N][N]={{0,60,10,50,HUGE,HUGE},{60,0,50,HUGE,30,HUGE},{10,50,0,50,60,40},{50,HUGE,50,0,HUGE,20},{HUGE,30,60,HUGE,0,60},{HUGE,HUGE,40,20,60,0}};intPrim（intmatrix[N][N],intn）

11121112131415161718192021222324LowCost[j]!=0)252627282930313233intLowCost[N];intCloseVertex[N];for(i=1;i<n;i++)(LowCost[i]=matrix[0][i];CloseVertex[i]=0;}LowCost[0]=0;CloseVertex[0]=0;for(i=1;i<n;i++)(MinCost=HUGE;k=i;for(j=1;j<n;j++)if(LowCost[j]<MinCost&&(MinCost=LowCost[j];k=j;}printf("(%d,%d)",k,CloseVertex[k]);LowCost[k]=0;for(j=1;j<n;j++)if(matrix[k][j]<LowCost[j])(LowCost[j]=matrix[k][j];CloseVertex[j]=k;

3536 }37 void38 (39404142434445 }46 void47 (48495051 }拓?fù)渑判騷PrintMatrix(intmatrix[N][N],intn)inti,j;for(i=0;i<n;i++)(for(j=0;j<n;j++)printf("%5d",matrix[i][j]);printf(〃\n〃)；}main()clrscr();PrintMatrix(matrix,N);Prim(matrix,N);程序5_3.c中第4行到第7行定義鄰接表頭結(jié)點(diǎn)類型，頭結(jié)點(diǎn)中有兩個(gè)字段count和link。Count字段存放該頂點(diǎn)的入度，link是一個(gè)指向該結(jié)點(diǎn)鄰接表的第一個(gè)表結(jié)點(diǎn)的指針。第8行到第11行定義表結(jié)點(diǎn)類型。每個(gè)表結(jié)點(diǎn)有兩個(gè)字段：vertex程序5_3.c中第13行到30行函數(shù)AdjList生成圖鄰接表。在該函數(shù)中利用頭結(jié)點(diǎn)的count記錄頂點(diǎn)的直接前驅(qū)數(shù)。

第45行到第71行函數(shù)TopOrder實(shí)現(xiàn)拓?fù)渑判?。首先將前?qū)為0的頂點(diǎn)入棧，棧通過count字段連接起來。第55行到第70行從棧中取出一個(gè)頂點(diǎn)并輸出，然后將該頂點(diǎn)的鄰接表上所有頂點(diǎn)的前驅(qū)計(jì)數(shù)遞減，如果前驅(qū)計(jì)數(shù)為0則入棧，這個(gè)過程重復(fù)n次。程序5_3.c#include<alloc.h>#defineMAXVERTEX100#defineN7structEdgeNode(intvertex;structEdgeNode*next;TOC\o"1-5"\h\z)；structVertexNode(intcount;structEdgeNode*link;);structVertexNode AdjList[N];voidAdjList(struct VertexNodea[],intn){int vi,vj,i;structEdgeNode *p;for (i=0;i<n;i++) (a[i].count=0;a[i].link=NULL;}

212223EdgeNode))242526272829303132333435363738394041424344scanf("%d%d”,&vi,&vj);while(vi>=0)(p=(structEdgeNode*)malloc(sizeof(structp->vertex=vj;p->next=a[vi].link;a[vi].link=p;a[vj].count=a[vj].count+1;scanf("%d%d",&vi,&vj);}}voidPrintAdjList(structVertexNodea[],intn)(inti;structEdgeNode*p;for(i=0;i<n;i++)(printf("%d%d〃，i,a[i].count);p=a[i].link;while(p!=NULL)(printf("%d",p->vertex);p=p->next;}printf("\n");

45464748495051525354555657585960616263646566676869voidTopOrder(structVertexNodea[],intn)(inti,j,k,top;structEdgeNode*ptr;top=-1;for(i=0;i<n;i++)if(a[i].count==0)(a[i].count=top;top=i;}for(i=0;i<n;i++)(if(top==-1)return;j=top;top=a[top].count;printf("%d",j);ptr=a[j].link;while(ptr!=NULL)(k=ptr->vertex;a[k].count=a[k].count-1;if(a[k].count==0)(a[k].count=top;top=k;}ptr=ptr->next;

TOC\o"1-5"\h\z}}voidmain()(AdjList(AdjList,N);PrintAdjList(AdjList,N);TopOrder(AdjList,N);}最短路徑Dijkstra算法的執(zhí)行過程是：首先從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)u，使distance[u]值最小，我們把u加入到集合S中(S[u]=1)，頂點(diǎn)u也成為S中的一員。這時(shí)v0出發(fā)，中間只經(jīng)過S中的頂點(diǎn)并以不在S中的一個(gè)頂點(diǎn)w為終點(diǎn)的最短路徑長(zhǎng)度可能會(huì)減小。就是說，distance*]的值可能發(fā)生變化。如果distance*]的值真的發(fā)生了變化(減小)，是因?yàn)橛幸粭l從v0到u，再到w的路徑，而且v0到u的路徑為最短的這種路徑，自u(píng)到w的路徑是邊＜u,w＞的緣故。這條路徑長(zhǎng)度是distance[u]+matrix[u][w]。因此接下來要調(diào)整distance中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的最短路徑長(zhǎng)度：從原來的distance[v]和distance[u]+matrix[u][v]中選擇較小值作為新的distance[v]，使distance[v]始終保持到目前為止最短的路徑長(zhǎng)度。重復(fù)上述過程，直到S中包含V中的全部頂點(diǎn)。結(jié)果數(shù)組distance記錄了從源點(diǎn)到圖中其余各頂點(diǎn)的最短路徑長(zhǎng)度。在程序5_4.c中，為了實(shí)現(xiàn)從“S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)u，使distance[u]值最小”的目的，我們建立函數(shù)MinCost，選擇當(dāng)s[u]為0時(shí)，使distance[u]最小的w,并返回w的值。函數(shù)ShortPath按上述說明實(shí)現(xiàn)Dijkstra算法。函數(shù)PrintMatrix輸出圖鄰接矩陣的值。程序5_4.c#defineHUGE9992#defineN53intmatrix[N][N]={{0,10,2,30,HUGE},4{HUGE,0,HUGE,15,HUGE},5{HUGE,3,0,HUGE,10},6{HUGE,HUGE,HUGE,0,6},7{HUGE,HUGE,HUGE,HUGE,0}};8intdistance[N];9voidShortPath(intmatrix[N][N],intv0,intn)10(11inti,u,dist,number;12ints[N];13for(i=0;i<n;i++)(14s[i]=0;15distance[i]=matrix[v0][i];16}17s[v0]=1;number=1;18while(number<n)(19u=MinCost(distance,s,n);20s[u]=1;21number++;22for(i=0;i<n;i++)(23if(s[i]==0)(2425dist=distance[u]+matrix[u][i]distance[i]=(distance[i]<dist)?distance[i]:dist;

26272829303132333435363738394041424344454647484950}}intMinCost(intdistance[],ints[],intn)(inti,k;intMinDistance=HUGE;for(i=0;i<n;i++)if(s[i]==0&&distance[i]<MinDistance)(MinDistance=distance[i];k=i;}returnk;}voidPrintMatrix(intmatrix[N][N],intn)(inti,j;for(i=0;i<n;i++)(for(j=0;j<n;j++)printf("%5d",matrix[i][j]);printf(〃\n〃)；}}voidmain()

51inti;clrscr();PrintMatrix(matrix,N);ShortPath(matrix,0,N);for(i=1;i<N;i++)printf("(0-%d):%d\n”,i,distance[i]);}順序查找程序6_1.c實(shí)現(xiàn)順序查找。第2行定義了一個(gè)常整數(shù)N表明查找表的大小。函數(shù)init隨機(jī)產(chǎn)生N個(gè)數(shù)并將其置入查找表a中。程序6_1.c#include<stdlib.h>#defineN8inta[N];voidinit(inta[],intn){inti;for(i=0;i<n;i++)a[i]=random(100);}voidprint(inta[],intn)inti;for(i=0;i<n;i++)

1415161718192021222324252627282930313233343536printf("%d",a[i]);printf(〃\n〃)；}intsearch(inta[],intk,intn)(inti=0;for(i=0;i<n&&a[i]!=k;i++);if(i<n)returni;elsereturn-1;}voidmain()(intk;clrscr();init(a,N);print(a,N);printf("PleaseinputKEY:〃)；scanf(〃％d〃,&k);printf("\n%d",search(a,k,N));printf("\nPressanykeytoRETURN...");getche();}折半查找

程序6_2.c實(shí)現(xiàn)折半查找。第3行對(duì)查找表中元素賦值，且值有序。在函數(shù)search中，如果查找下限小于上限，則計(jì)算中間位置。并根據(jù)中間位置的元素值與k進(jìn)行比較，根據(jù)比較結(jié)果決定下次查找的范圍。程序6_2.c#include<stdlib.h>#defineN8inta[N]={15,17,30,46,56,82,90,95};voidprint(inta[],intn)5{6inti;7for(i=0;i<n;i++)8printf("%d",a[i]);9printf(〃\n〃)；10}11intsearch(inta[],intk,intn)12{13intlow=0;14inthigh=n-1;15intmid;16while(low<=high){17mid=(low+high)/2;18if(a[mid]==k)returnmid;19elseif(a[mid]>k)high=mid-1;20elselow=mid+1;21}return-1;}voidmain()(intk;clrscr();print(a,N);printf("PleaseinputKEY: 〃)；scanf(〃％d〃,&k);printf("\n%d",search(a,k,N));printf("\nPressanykeyto RETURN...");getche();}二叉排序樹程序6_3.c實(shí)現(xiàn)二叉排序樹的有關(guān)操作。第4行到第8行定義二叉排序樹結(jié)點(diǎn)結(jié)構(gòu)。第9行一維數(shù)組a存放用于構(gòu)造二叉排序樹的元素。函數(shù)search按3.1所述思想查找與參數(shù)item匹配的結(jié)點(diǎn)，若找到這個(gè)結(jié)點(diǎn)，則返回該結(jié)點(diǎn)的地址，否則返回空。第11行到第44行函數(shù)insert功能是將元素item插入二叉排序樹中。若二叉排序樹為空，則item作為根結(jié)點(diǎn)。若二叉排序樹不空，則要根據(jù)item的值進(jìn)行查找。程序6_3.c#include<alloc.h>#defineN8typedefintEL