數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)4946

《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)指導(dǎo)書(shū)2013年8月

目錄實(shí)驗(yàn)一C語(yǔ)言編程復(fù)習(xí).....................................................................3實(shí)驗(yàn)二線形表基本操作的實(shí)現(xiàn)........................................................7實(shí)驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用......................................18實(shí)驗(yàn)四二叉樹(shù)算法的實(shí)現(xiàn)..............................................................33實(shí)驗(yàn)五圖的算法的實(shí)現(xiàn)..................................................................49實(shí)驗(yàn)六查找算法的實(shí)現(xiàn)..................................................................69實(shí)驗(yàn)七排序算法的實(shí)現(xiàn)................................................................812

實(shí)驗(yàn)一C語(yǔ)言編程復(fù)習(xí)一、實(shí)驗(yàn)?zāi)康?.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.理解指針與應(yīng)用的區(qū)別。3.掌握結(jié)構(gòu)體的使用。4.掌握簡(jiǎn)單排序方法。二、實(shí)驗(yàn)內(nèi)容(1)輸入一行字符，計(jì)算該行字符中包含多少個(gè)單詞，單詞之間用空格分隔開(kāi)。(2)利用add函數(shù)求兩個(gè)復(fù)數(shù)2+3i和4+5i的和。（要求用結(jié)構(gòu)體來(lái)定義復(fù)數(shù)）(3)一個(gè)班上有30名學(xué)生，每個(gè)學(xué)生的數(shù)據(jù)作為一個(gè)記錄，每個(gè)記錄包括學(xué)號(hào)、姓名、三門(mén)課程的成績(jī)和三門(mén)課程平均成績(jī)。從鍵盤(pán)輸入學(xué)生的學(xué)號(hào)、姓名及三門(mén)課的成績(jī)。要求打印三門(mén)課程平均成績(jī)最高分的學(xué)生記錄。三、實(shí)驗(yàn)步驟(1)用數(shù)組或字符串獲取字符，碰到空格即表示新單詞的開(kāi)始。(2)要求用結(jié)構(gòu)體來(lái)定義復(fù)數(shù)，包括實(shí)部和虛部。(3)定義一個(gè)Student的結(jié)構(gòu)體類(lèi)型，包含學(xué)號(hào)、姓名、成績(jī)等成員。四、實(shí)現(xiàn)提示structstudent3

{charnum[6];stringname;floatscore[3];floataver;};五、思考與提高思考為何voidSwap1(Student,Student)這個(gè)函數(shù)無(wú)法實(shí)現(xiàn)兩個(gè)學(xué)生的交換？六、完整參考程序1、#include<iostream>#include<string>usingnamespacestd;voidmain(){cout<<"輸入n個(gè)單詞，單詞之間用空格隔開(kāi)"<<endl;stringstr;getline(cin,str);intnum=0;intlen=str.size();if(len!=0)num=1;for(inti=0;i<len;i++){if(str[i]==''){num++;}}cout<<"單詞個(gè)數(shù)為："<<num<<endl;}也可使用數(shù)組實(shí)現(xiàn)：#include<iostream>4

usingnamespacestd;voidmain(){cout<<"輸入n個(gè)單詞，單詞之間用空格隔開(kāi)"<<endl;charstr[100];cin>>str;intnum=0;for(inti=0;str[i]!='\0';i++){if(str[i]=''){num++;}}cout<<"單詞個(gè)數(shù)為："<<num<<endl;}2、#include<iostream>usingnamespacestd;structcomplex{floatreal;floatimag;};complexadd(complexx1,complexx2){complexsum;sum.real=x1.real+x2.real;sum.imag=x1.imag+x2.imag;returnsum;};voidmain(){complexx1={2,3},x2={4,5},sum;complexadd(complexx1,complexx2);sum=add(x1,x2);cout<<"x1="<<x1.real<<"+"<<x1.imag<<"i"<<""<<"x2="<<x2.real<<"+"<<x2.imag<<"i"<<endl;5

cout<<"x1+x2="<<sum.real<<"+"<<sum.imag<<"i"<<endl;}3、#include<iostream>#include<string>#include<iomanip>usingnamespacestd;constintn=3;structstudent{charnum[6];stringname;floatscore[3];floataver;};intmain(){inti,j,maxi,max,sum;floataverage;studentstud[n];for(i=0;i<n;i++)//輸入學(xué)生和成績(jī)信息{cout<<"inputscoresofstudent"<<i+1<<endl;cout<<"number:";cin>>stud[i].num;cout<<"name:";cin>>stud[i].name;for(j=0;j<3;j++){cout<<"score"<<j+1<<":";cin>>stud[i].score[j];}cout<<endl;}//輸入學(xué)生和成績(jī)信息average=0;max=0;maxi=0;for(i=0;i<n;i++){sum=0;6

for(j=0;j<3;j++)//計(jì)算每個(gè)同學(xué)總成績(jī)sum+=stud[i].score[j];stud[i].aver=sum/3.0;//計(jì)算每個(gè)同學(xué)平均成績(jī)if(sum>max)//將某同學(xué)平均成績(jī)與目前的最高平均成績(jī)進(jìn)行比較選擇高的那個(gè)為最新最高平均成績(jī){max=sum;maxi=i;}}cout<<"score1score2score3average"<<endl;for(i=0;i<n;i++)//輸出所有同學(xué)成績(jī)信息{cout<<setw(8)<<stud[i].num<<""<<setw(10)<<stud[i].name<<"";for(j=0;j<3;j++)cout<<setw(3)<<stud[i].score[j]<<"";cout<<stud[i].aver<<endl;}//輸出所有同學(xué)成績(jī)信息cout<<"Thehighestscoreis:"<<stud[maxi].num<<","<<stud[maxi].name<<","<<"Theaverageis:"<<stud[maxi].aver;cout<<",threescores:";//輸出最高平均成績(jī)的同學(xué)信息for(j=0;j<3;j++)cout<<stud[maxi].score[j]<<"";cout<<endl;return0;}實(shí)驗(yàn)二線形表基本操作的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。7

2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。二、實(shí)驗(yàn)內(nèi)容1.順序線性表的建立、插入及刪除。2.鏈?zhǔn)骄€性表的建立、插入及刪除。三、實(shí)驗(yàn)步驟1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。四、實(shí)現(xiàn)提示1.由于C語(yǔ)言的數(shù)組類(lèi)型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類(lèi)型定義順序表：#defineMAXSIZE1024typedefintelemtype;/*線性表中存放整型元素*/8

typedefstruct{elemtypevec[MAXSIZE];intlen;/*順序表的長(zhǎng)度*/}sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。2.注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：typedefintelemtype;typedefstructnode{elemtypedata;//數(shù)據(jù)域structnode*next;//指針域}linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：p=(linklist*)malloc(sizeof(linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類(lèi)型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。五、思考與提高9

1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？六、完整參考程序#include<stdio.h>#include<conio.h>#defineMAX30//定義線性表的最大長(zhǎng)度enumBOOL{False,True};//定義BOOL型typedefstruct{charelem[MAX];intlast;//線性表//last指示當(dāng)前線性表的長(zhǎng)度}sqlist;voidinitial(sqlist&);//初始化線性表BOOLinsert(sqlist&,int,char);//在線性表中插入元素BOOLdel(sqlist&,int,char&);//在線性表中刪除元素intlocate(sqlist,char);voidprint(sqlist);voidmain()//在線性表中定位元素//顯示線性表中所有元素{sqlistS;//S為一線性表intloc,flag=1;charj,ch;BOOLtemp;printf("本程序用來(lái)實(shí)現(xiàn)順序結(jié)構(gòu)的線性表。\n");printf("可以實(shí)現(xiàn)查找等操作。\n");//初始化線性表、插入、刪除initial(S);while(flag){printf("請(qǐng)選擇:\n");printf("1.顯示所有元素\n");printf("2.插入一個(gè)元素\n");printf("3.刪除一個(gè)元素\n");printf("4.查找一個(gè)元素\n");printf("5.退出程序\n");scanf("%c",&j);switch(j){case'1':print(S);break;//顯示所有元素case'2':{printf("請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:\n");10

printf("格式：字符，位置；例如:a,2\n");scanf("%c,%d",&ch,&loc);//輸入要插入的元素和插入的位置temp=insert(S,loc,ch);//插入if(temp==False)printf("插入失敗!\n");//插入失敗else{printf("插入成功!\n");print(S);}//插入成功break;}case'3':{printf("請(qǐng)輸入要?jiǎng)h除元素的位置:");scanf("%d",&loc);//輸入要?jiǎng)h除的元素的位置temp=del(S,loc,ch);//刪除if(temp==True)printf("刪除了一個(gè)元素:%c\n",ch);//刪除成功elseprintf("該元素不存在!\n");//刪除失敗print(S);break;}case'4':{printf("請(qǐng)輸入要//輸入要//定位if(loc!=-1)printf("該元素:%d\n",loc+1);//顯示該元素位置printf("%c不存在!\n",ch);//當(dāng)前元素不存在查找的元素:");scanf("%c",&ch);查找的元素loc=locate(S,ch);所在位置elsebreak;}default:flag=0;printf("程序結(jié)束，按任意鍵退出!\n");}}getch();}voidinitial(sqlist&v){//初始化線性表inti;printf("請(qǐng)輸入初始線性表長(zhǎng)度：n=");//輸入線性表初始化時(shí)的長(zhǎng)度scanf("%d",&v.last);printf("請(qǐng)輸入從1到%d的各元素(字符)，例如:abcdefg\n",v.last);getchar();for(i=0;i<v.last;i++)scanf("%c",&v.elem[i]);//輸入線性表的各元素}BOOLinsert(sqlist&v,intloc,charch){//插入一個(gè)元素，成功返回True，失敗返回False11

inti;if((loc<1)||(loc>v.last+1)){printf("插入位置不合理!\n");//位置不合理returnFalse;}elseif(v.last>=MAX){printf("線性表已滿!\n");returnFalse;//線性表已滿}else{for(i=v.last-1;i>=loc-1;i--)v.elem[i+1]=v.elem[i];//其后元素依次后移v.elem[loc-1]=ch;v.last++;//插入元素//線性表長(zhǎng)度加一returnTrue;}}BOOLdel(sqlist&v,intloc,char&ch){//刪除一個(gè)元素，成功返回True，并用ch返回該元素值，失敗返回Falseintj;if(loc<1||loc>v.last)returnFalse;//刪除位置不合理else{ch=v.elem[loc-1];//ch取得該元素值for(j=loc-1;j<v.last-1;j++)v.elem[j]=v.elem[j+1];//其后元素依次前移v.last--;//線性表長(zhǎng)度減一returnTrue;}}intlocate(sqlistv,charch){//在線性表中查找ch的位置，成功返回其位置，失敗返回-1inti=0;while(i<v.last&&v.elem[i]!=ch)i++;//當(dāng)前位置后移，直到找到為止if(v.elem[i]==ch)returni;//找到當(dāng)前元素elsereturn(-1);}voidprint(sqlistv){inti;//顯示當(dāng)前線性表所有元素for(i=0;i<v.last;i++)printf("%c",v.elem[i]);12

printf("\n");}2.鏈?zhǔn)骄€性表的建立、插入及刪除。#include<conio.h>#include<stdio.h>#include<stdlib.h>#defineLENsizeof(LNode)//定義LEN為一個(gè)節(jié)點(diǎn)的長(zhǎng)度enumBOOL{False,True};//定義BOOL型typedefstructnode{chardata;//數(shù)據(jù)域structnode*next;//指向下一個(gè)節(jié)點(diǎn)的指針}LNode,*LinkList;voidCreatList(LinkList&,int);//生成一個(gè)單鏈表BOOLListInsert(LinkList&,int,char);//在單鏈表中插入一個(gè)元素BOOLListDelete(LinkList&,int,char&);//在單鏈表中刪除一個(gè)元素BOOLListFind_keyword(LinkList,char,int&);//按關(guān)鍵字查找一個(gè)元素BOOLListFind_order(LinkList,char&,int);//按序號(hào)查找一個(gè)元素voidListPrint(LinkList);voidmain()//顯示單鏈表所有元素{LinkListL;BOOLtemp;intnum,loc,flag=1;charj,ch;printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的線性表的操作。\n");printf("可以進(jìn)行插入，刪除，定位，查找等操作。\n");printf("請(qǐng)輸入初始時(shí)鏈表長(zhǎng)度:");//輸入生成單鏈表時(shí)的元素個(gè)數(shù)scanf("%d",&num);CreatList(L,num);ListPrint(L);//生成單鏈表while(flag){printf("請(qǐng)選擇:\n");printf("1.顯示所有元素\n");//顯示鏈表元素printf("2.插入一個(gè)元素\n");//插入鏈表元素printf("3.刪除一個(gè)元素\n");//刪除鏈表元素printf("4.按關(guān)鍵字查找元素\n");//按關(guān)鍵字查找printf("5.按序號(hào)查找元素\n");//按序號(hào)查找printf("6.退出程序scanf("%c",&j);switch(j)\n");//退出13

{case'1':ListPrint(L);break;case'2':{printf("請(qǐng)輸入元素(一個(gè)字符)和要插入的位置:\n");printf("格式:字符，位置；例如:a,3\n");scanf("%c,%d",&ch,&loc);temp=ListInsert(L,loc,ch);//輸入要插入的元素和要插入的位置//插入if(temp==False)printf("插入失敗!\n");//插入失敗elseprintf("插入成功!\n");//成功插入ListPrint(L);break;}case'3':printf("請(qǐng)輸入要?jiǎng)h除的元素所在位置:");scanf("%d",&loc);//輸入要?jiǎng)h除的節(jié)點(diǎn)的位置//刪除temp=ListDelete(L,loc,ch);if(temp==False)printf("刪除失敗!\n");//刪除失敗elseprintf("成功刪除了一個(gè)元素:%c\n",ch);//刪除成功，顯示該元素ListPrint(L);break;case'4':if(L->next==NULL)printf("鏈表為空!\n");//鏈表為空else{printf("請(qǐng)輸入要查找的元素(一個(gè)字符):");scanf("%c",&ch);//輸入要查找的元素temp=ListFind_keyword(L,ch,loc);//按關(guān)鍵字查找if(temp==False)printf("沒(méi)有找到該元素!\n");//查找失敗elseprintf("該元素在鏈表的第%d個(gè)位置。\n",loc);//成功查找，顯示該元素位置}break;case'5':if(L->next==NULL)printf("鏈表為空!\n");else{printf("請(qǐng)輸入要查找的位置:");//鏈表為空scanf("%d",&loc);//輸入要查找的元素的位置temp=ListFind_order(L,ch,loc);//按序號(hào)查找if(temp==False)printf("該位置不存在!\n");//查找失敗elseprintf("第%d個(gè)元素是：%c\n",loc,ch);//成功查找，顯示該元素}break;default:flag=0;printf("程序結(jié)束，按任意鍵退出!\n");}14

}getch();}voidCreatList(LinkList&v,intn){//生成一個(gè)帶頭結(jié)點(diǎn)的有n個(gè)元素的單鏈表inti;LinkListp;v=(LinkList)malloc(LEN);//生成頭結(jié)點(diǎn)v->next=NULL;printf("請(qǐng)輸入%d個(gè)字符：例如：abcdefg\n",n);getchar();for(i=n;i>0;--i){p=(LinkList)malloc(LEN);//生成新結(jié)點(diǎn)scanf("%c",&p->data);p->next=v->next;v->next=p;}}BOOLListInsert(LinkList&v,inti,chare){//在單鏈表的第i各位置插入元素e，成功返回True，失敗返回FalseLinkListp,s;intj=0;p=v;while(p&&j<i-1){p=p->next;++j;}//查找第i-1個(gè)元素的位置if(!p||j>i-1)returnFalse;//沒(méi)有找到s=(LinkList)malloc(LEN);s->data=e;//生成一個(gè)新結(jié)點(diǎn)s->next=p->next;p->next=s;//將新結(jié)點(diǎn)插入到單鏈表中returnTrue;}BOOLListDelete(LinkList&v,inti,char&e){//在單鏈表中刪除第i個(gè)元素，成功刪除返回True，并用e返回該元素值，失敗返回FalseLinkListp,q;intj=0;p=v;while(p->next&&j<i-1)//查找第i-1個(gè)元素位置{p=p->next;++j;}15

if(!(p->next)||j>i-1)returnFalse;//查找失敗q=p->next;p->next=q->next;//刪除該元素e=q->data;free(q);//e取得該元素值//釋放該元素空間returnTrue;}BOOLListFind_keyword(LinkListv,chare,int&i){//在單鏈表中查找關(guān)鍵字為e的元素，成功返回True,并用i返回該元素位置，//失敗返回Falsei=1;LinkListp;p=v->next;while((p->data!=e)&&(p->next!=NULL))//p指針指向下{p=p->next;i++;}//找到或到鏈表//該元素在鏈表中一個(gè)，直到尾為止if(p->data!=e)不存在returnFalse;elsereturnTrue;}BOOLListFind_order(LinkListv,char&e,inti){//在單鏈表中查找//失敗返回FalseLinkListp;第i個(gè)元素，成功返回True，并用e返回該元素值，intj=0;p=v;while(p->next&&j<i)//移動(dòng)指針，直到找到第i個(gè)元素{p=p->next;++j;}if(j!=i)returnFalse;//查找失敗else{e=p->data;returnTrue;}//查找成功，用e取得該元素值}voidListPrint(LinkListv){//顯示鏈表所有元素LinkListq;q=v->next;printf("鏈表所有元素:");while(q!=NULL)16

{printf("%c",q->data);q=q->next;}printf("\n");}17

實(shí)驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)康?.掌握棧的順序表示和實(shí)現(xiàn)2.掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1.編寫(xiě)一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2.實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。三、實(shí)驗(yàn)步驟1.初始化順序棧2.插入元素3.刪除棧頂元素4.取棧頂元素5.遍歷順序棧6.置空順序棧7.初始化并建立鏈隊(duì)列8.入鏈隊(duì)列9.出鏈隊(duì)列10.遍歷鏈隊(duì)列18

四、實(shí)現(xiàn)提示1./*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedefstruct{ElemTypestack[MAXNUM];inttop;}SqStack;/*初始化順序棧函數(shù)*/voidInitStack(SqStack*p){q=(SqStack*)malloc(sizeof(SqStack)/*申請(qǐng)空間*/)/*入棧函數(shù)*/voidPush(SqStack*p,ElemTypex){if(p->top<MAXNUM-1){p->top=p->top+1;/*棧頂+1*/p->stack[p->top]=x;}/*數(shù)據(jù)入棧*/}/*出棧函數(shù)*/ElemTypePop(SqStack*p){x=p->stack[p->top];/*將棧頂元素賦給x*/p->top=p->top-1;}/*棧頂-1*//*獲取棧頂元素函數(shù)*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}19

/*遍歷順序棧函數(shù)*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)printf("第%d個(gè)數(shù)據(jù)元素是：%6d\n",i,p->stack[i]);}/*置空順序棧函數(shù)*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定義鏈隊(duì)列*/typedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;}Lqueue;/*初始化并建立鏈隊(duì)列函數(shù)*/voidcreat(Lqueue*q){h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請(qǐng)空間*/h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環(huán)快速輸入數(shù)據(jù)*/{scanf("%d",&x);20

Lappend(q,x);}/*利用入鏈隊(duì)列函數(shù)快速輸入數(shù)據(jù)*/}/*入鏈隊(duì)列函數(shù)*/voidLappend(Lqueue*q,intx){s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出鏈隊(duì)列函數(shù)*/ElemTypeLdelete(Lqueue*q){p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);}/*釋放空間*//*遍歷鏈隊(duì)列函數(shù)*/voiddisplay(Lqueue*q){while(p!=NULL)/*利用條件判斷是否到隊(duì)尾*/{printf("%d-->",p->data);p=p->next;}}五、思考與提高21

1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？2.如果一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分配過(guò)大的存儲(chǔ)空間，勢(shì)必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問(wèn)題？（1）鏈棧只有一個(gè)top指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？（2）一個(gè)程序中如果要用到兩個(gè)棧時(shí)，可通過(guò)兩個(gè)棧共享一維數(shù)組來(lái)實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？六、完整參考程序1.棧的順序表示和實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>#include<conio.h>#defineTRUE#defineFALSE#defineOK101#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintSElemType;//-----棧的順序存儲(chǔ)表示-----#defineSTACK_INIT_SIZE10022

#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S);StatusDestroyStack(SqStack&S);StatusStackDisplay(SqStack&S);StatusGetTop(SqStackS,SElemType&e);StatusPush(SqStack&S,SElemTypee);StatusPop(SqStack&S,SElemType&e);StatusStackEmpty(SqStackS);StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失效S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusDestroyStack(SqStack&S){//銷(xiāo)毀棧Sif(S.base)free(S.base);S.top=S.base=NULL;returnOK;}//InitStackStatusStackDisplay(SqStack&S){//顯示棧SSElemType*p=S.base;inti=0;if(S.base==S.top){23

printf("堆棧已空!\n");returnOK;}while(p<S.top)printf("[%d:%d]",++i,*p++);printf("\n");returnOK;}//StackDisplayStatusGetTop(SqStackS,SElemType&e){//若棧不空，則用e返回S的棧頂元素，//并返回OK；否則返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTopStatusPush(SqStack&S,SElemTypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize){//棧滿，追加存儲(chǔ)空間S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PushStatusPop(SqStack&S,SElemType&e){//若棧不為空，則刪除S的棧頂元素，24

//用e返回其值，并返回OK；否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusStackEmpty(SqStackS){//若S為空棧，則返回TRUE，否則返回FALSE。if(S.top==S.base)returnTRUE;elsereturnFALSE;}//StackEmptyvoidmain(){SqStackSt;Statustemp;intflag=1,ch;inte;printf("本程序?qū)崿F(xiàn)順序結(jié)構(gòu)的堆棧的操作。\n");printf("可以進(jìn)行入棧，出棧，取棧頂元素等操作。\n");InitStack(St);while(flag){//初始化堆棧Stprintf("請(qǐng)選擇:\n");printf("1.顯示棧中所有元素printf("2.入棧\n");\n");\n");\n");\n");printf("3.出棧printf("4.取棧頂元素printf("5.退出程序scanf("%d",&ch);25

switch(ch){case1:StackDisplay(St);break;case2:printf("請(qǐng)輸入要入棧的元素(一個(gè)整數(shù)):");scanf("%d",&e);temp=Push(St,e);//輸入要入棧的元素//入棧if(temp!=OK)printf("堆棧已滿!入棧失敗!\n");else{printf("成功入棧!\n");//成功入棧StackDisplay(St);}break;case3:temp=Pop(St,e);//出棧if(temp==ERROR)printf("堆棧已空!\n");else{printf("成功出棧一個(gè)元素:%d\n",e);//成功出棧StackDisplay(St);}break;case4:temp=GetTop(St,e);//取得棧頂元素if(temp==ERROR)printf("堆棧已空!\n");elseprintf("棧頂元素是:%d\n",e);//顯示棧頂元素break;default:26

flag=0;printf("程序結(jié)束，按任意鍵退出!\n");getch();}}DestroyStack(St);}2.隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)#include<conio.h>#include<stdio.h>#include<stdlib.h>#defineTRUE#defineFALSE#defineOK101#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;//ElemType是順序表數(shù)據(jù)元素類(lèi)型,此程序定義為int型typedefintQElemType;//-----單鏈隊(duì)列--隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-----typedefstructQNode{//定義結(jié)點(diǎn)結(jié)構(gòu)//數(shù)據(jù)域QElemTypedata;structQNode*next;}QNode,*QueuePtr;//指針域typedefstructlinkqueue{//定義隊(duì)列結(jié)構(gòu)27

QueuePtrfront;QueuePtrrear;//隊(duì)頭指針//隊(duì)尾指針}LinkQueue;StatusInitLinkQueue(LinkQueue&);StatusDestroyLinkQueue(LinkQueue&);intLinkQueueLength(LinkQueue&Q);//初始化一個(gè)隊(duì)列//銷(xiāo)毀一個(gè)隊(duì)列//隊(duì)列的長(zhǎng)度StatusEnLinkQueue(LinkQueue&,QElemType);//將一個(gè)元素入隊(duì)列StatusDeLinkQueue(LinkQueue&,QElemType&);//將一個(gè)元素出隊(duì)列StatusDisplayLinkQueue(LinkQueue);//顯示隊(duì)列中所有元素voidmain(){LinkQueueLQ;QElemTypee;intflag=1,ch,len;Statustemp;printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列的操作。\n");printf("可以進(jìn)行入隊(duì)列、出隊(duì)列等操作。\n");InitLinkQueue(LQ);while(flag){//初始化隊(duì)列printf("請(qǐng)選擇:\n");printf("1.顯示隊(duì)列所有元素\n");printf("2.入隊(duì)列\(zhòng)n");printf("3.出隊(duì)列\(zhòng)n");28

printf("4.求隊(duì)列的長(zhǎng)度\n");printf("5.退出程序\n");scanf("%d",&ch);switch(ch){case1:DisplayLinkQueue(LQ);//顯示隊(duì)列中所有元素break;case2:printf("請(qǐng)輸入要人隊(duì)的元素(一個(gè)整數(shù)):");scanf("%d",&e);//輸入要入隊(duì)列的字符EnLinkQueue(LQ,e);//入隊(duì)列DisplayLinkQueue(LQ);break;case3:temp=DeLinkQueue(LQ,e);//出隊(duì)列if(temp==OK){printf("出隊(duì)一個(gè)元素:%d\n",e);DisplayLinkQueue(LQ);}elseprintf("隊(duì)列為空!\n");break;case4:len=LinkQueueLength(LQ);printf("隊(duì)列的長(zhǎng)度為:%d\n",len);break;default:flag=0;printf("程序運(yùn)行結(jié)束，按任意鍵退出!\n");getch();}}}29

StatusInitLinkQueue(LinkQueue&Q){//隊(duì)列初始化Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//生成一個(gè)頭結(jié)點(diǎn)，并把首尾指針指向頭結(jié)點(diǎn)Q.front->next=NULL;returnOK;}StatusDestroyLinkQueue(LinkQueue&Q){//銷(xiāo)毀一個(gè)隊(duì)列QueuePtrp;QElemTypee;while(Q.front!=Q.rear)DeLinkQueue(Q,e);free(Q.front);Q.front=Q.rear=NULL;returnOK;}intLinkQueueLength(LinkQueue&Q){//隊(duì)列的長(zhǎng)度inti=0;QueuePtrp=Q.front;while(p!=Q.rear){++i;p=p->next;}returni;}StatusEnLinkQueue(LinkQueue&Q,QElemTypee){//入隊(duì)列QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));//生成一個(gè)新結(jié)點(diǎn)p->data=e;//賦值p->next=NULL;30

Q.rear->next=p;//插入至隊(duì)列尾//修改隊(duì)尾指針Q.rear=p;returnOK;}StatusDeLinkQueue(LinkQueue&Q,QElemType&e){//出隊(duì)列QueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front->next;//判斷隊(duì)列是否已空，已空返回ERROR//p指向隊(duì)列中第一個(gè)元素//取得該元素值e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;returnOK;//修改隊(duì)首指針//若隊(duì)列已空，把隊(duì)尾指針指向頭結(jié)點(diǎn)//成功出隊(duì)列，返回OK}StatusDisplayLinkQueue(LinkQueueQ){//顯示隊(duì)列中所有元素QueuePtrp;inti=0;p=Q.front->next;if(p==NULL)printf("隊(duì)列為空!\n");//隊(duì)列為空else{while(p){//否則顯示隊(duì)列中所有元素printf("[%d:%d]",++i,p->data);p=p->next;}printf("\n");}31

returnOK;}32

實(shí)驗(yàn)四二叉樹(shù)算法的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的建立與存儲(chǔ)2.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的遍歷方法二、實(shí)驗(yàn)內(nèi)容1.練習(xí)二叉樹(shù)的建立與存儲(chǔ)2.練習(xí)二叉樹(shù)的遍歷三、實(shí)驗(yàn)步驟1.建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。2.建立二叉樹(shù),并通過(guò)調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。四、實(shí)現(xiàn)提示建立二叉樹(shù)的代碼如下：BTCHINALR*createbt(){BTCHINALR*q;structnode1*s[30];intj,i,x;printf("建立二叉樹(shù)，輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)33

隔開(kāi)\n\n");printf("i,x=");scanf("%d,%c",&i,&x);while(i!=0&&x!='$'){q=(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個(gè)新結(jié)點(diǎn)q*/q->data=x;q->lchild=NULL;q->rchild=NULL;s[i]=q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/if(i!=1)/*i=1，對(duì)應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/{j=i/2;/*求雙親結(jié)點(diǎn)的編號(hào)j*/if(i%2==0)s[j]->lchild=q;/*q結(jié)點(diǎn)編號(hào)為偶數(shù)則掛在雙親結(jié)點(diǎn)j的左邊*/elses[j]->rchild=q;}的右邊*/printf("i,x=");/*q結(jié)點(diǎn)編號(hào)為奇數(shù)則掛在雙親結(jié)點(diǎn)jscanf("%d,%c",&i,&x);}returns[1];/*返回根結(jié)點(diǎn)地址*/}五、思考與提高1.如何用孩子兄弟表示法存儲(chǔ)樹(shù)？2.熟悉及難赫夫曼樹(shù)。34

六、完整參考程序1.二叉樹(shù)的建立、存儲(chǔ)與遍歷#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>#include<conio.h>#defineTRUE#defineFALSE#defineOK101#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;//TElemType是二叉樹(shù)數(shù)據(jù)元素類(lèi)型,此程序定義為char型typedefcharTElemType;//-----二叉樹(shù)的二叉鏈表存儲(chǔ)表示-----typedefstructBiTNode{TElemTypedata;//定義二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)//數(shù)據(jù)域35

structBiTNode*lchild,*rchild;//左右孩子指針域}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T);//生成一個(gè)二叉樹(shù)(可用兩種方法輸入)StatusCreateBiTreeInPreOrderResult(BiTree&T);//生成一個(gè)二叉樹(shù)(先序遍歷結(jié)果輸入)StatusCreateBiTreeInBracket(BiTree&T);//生成一個(gè)二叉樹(shù)(嵌套括號(hào)法輸入)StatusPrintElement(BiTreet);StatusPreOrderTraverse(BiTreeT,Status(*Visit)(BiTreet));//先序遞歸遍歷二叉樹(shù)StatusInOrderTraverse(BiTreeT,Status(*Visit)(BiTreet));//中序遞歸遍歷二叉樹(shù)StatusPostOrderTraverse(BiTreeT,Status(*Visit)(BiTreet));//后序遞歸遍歷二叉樹(shù)char*pstr;StatusCreateBiTree(BiTree&T){//生成一個(gè)二叉樹(shù)(可用兩種方法輸入)inti,len,choice=0;charstr[200];printf("請(qǐng)選擇建立二叉樹(shù)的方法:\n");36

printf("1.按先序遍歷的結(jié)果輸入二叉樹(shù)\n");printf("2.按嵌套括號(hào)表示法輸入二叉樹(shù)\n");do{gets(str);choice=atoi(str);}while(choice<1||choice>2);if(choice==1){printf("請(qǐng)輸入先序遍歷二叉樹(shù)的結(jié)果,程序據(jù)此建立二叉樹(shù)。\n");printf("對(duì)于葉子結(jié)點(diǎn)以空格表示。\n");printf("例如:abc__de_g__f___(回車(chē))，建立如下二叉樹(shù)：\n");printf("a\n");\n");\n");\n");\n");\n");\n");\n");\n");printf("/printf("bprintf("/\\printf("cd/\\printf("printf("efprintf("\\printf("gpstr=gets(str);len=strlen(str);for(i=len;i<180;++i)str[i]='';str[i]=0;37

CreateBiTreeInPreOrderResult(T);//初始化二叉樹(shù)}else{printf("請(qǐng)輸入嵌套括號(hào)表示法表示的二叉樹(shù),程序據(jù)此建立二叉樹(shù)。\n");printf("例如:(a(b(c,d(e(,g),f))))(回車(chē))，建立如下二叉樹(shù)：\n");printf("printf("printf("printf("printf("printf("printf("printf("printf("pstr=gets(str);a\n");\n");\n");\n");\n");\n");\n");\n");\n");/b/\\cd/\\ef\\gCreateBiTreeInBracket(T);//初始化二叉樹(shù)}returnOK;}StatusCreateBiTreeInPreOrderResult(BiTree&T){//根據(jù)存放在字符串*str中的先序遍歷二叉樹(shù)的結(jié)果,生成鏈接存儲(chǔ)的二叉樹(shù)。//(若某結(jié)點(diǎn)無(wú)左孩子或右孩子,則以空格表示其"孩子")。if(!(*pstr)||*pstr==''){38

T=NULL;pstr++;}else{T=(BiTNode*)malloc(sizeof(BiTNode));//生成一個(gè)新結(jié)點(diǎn)if(!T)exit(OVERFLOW);T->data=*(pstr++);CreateBiTreeInPreOrderResult(T->lchild);//生成左子樹(shù)CreateBiTreeInPreOrderResult(T->rchild);//生成右子樹(shù)}returnOK;}StatusCreateBiTreeInBracket(BiTree&T){//根據(jù)嵌套括號(hào)表示法的字符串*str生成鏈接存儲(chǔ)的二叉樹(shù)//例如:*pstr="(a(b(c),d(e(,f),g)))"BiTreestack[100],p;inttop=0,k;//top為棧指針,k指定是左還是右孩子;T=NULL;while(*pstr){switch(*pstr){case'(':stack[top++]=p;k=1;break;//左結(jié)點(diǎn),其父結(jié)點(diǎn)為*pcase')':top--;break;39

case',':k=2;break;//右結(jié)點(diǎn),其父結(jié)點(diǎn)為*pcase'':break;default:p=(BiTree)malloc(sizeof(BiTNode));p->data=*pstr;p->lchild=p->rchild=NULL;if(!T)T=p;//根結(jié)點(diǎn)else{switch(k){case1:stack[top-1]->lchild=p;break;case2:stack[top-1]->rchild=p;break;}}}pstr++;}returnOK;}StatusDestroyBiTree(BiTree&T){if(T){if(T->lchild)DestroyBiTree(T->lchild);//銷(xiāo)毀左子樹(shù)if(T->rchild)DestroyBiTree(T->rchild);//銷(xiāo)毀右子樹(shù)free(T);//銷(xiāo)毀根結(jié)點(diǎn)40

T=NULL;returnOK;}elsereturnOK;}StatusPrintElement(BiTreet){printf("%c",t->data);//顯示結(jié)點(diǎn)數(shù)據(jù)域returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(BiTreet)){//先序if(T){if((*Visit)(T))//訪問(wèn)結(jié)點(diǎn)if(PreOrderTraverse(T->lchild,Visit))//遍歷左子樹(shù)if(PreOrderTraverse(T->rchild,Visit))//遍歷右子樹(shù)returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(BiTreet)){//中序41

if(T){if(InOrderTraverse(T->lchild,Visit))//遍歷左子樹(shù)//訪問(wèn)結(jié)點(diǎn)if(InOrderTraverse(T->rchild,Visit))//遍歷右子樹(shù)if((*Visit)(T))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(BiTreee)){//后序if(T){if(PostOrderTraverse(T->lchild,PrintElement))//遍歷左子樹(shù)if(PostOrderTraverse(T->rchild,PrintElement))//遍歷右子樹(shù)if((*Visit)(T))//訪問(wèn)結(jié)點(diǎn)returnOK;returnERROR;}elsereturnOK;}StatusDisplayBiTreeInConcave(BiTreeT){//以凹入表示法輸出一棵二叉樹(shù)BiTreestack[100],p;42

intlevel[100][2],top,n,i,width=4;charchildtype[3]={'L','R','D'};constintMaxWidth=30;if(T){top=0;stack[top]=T;//根結(jié)點(diǎn)入棧level[top][0]=width;level[top][1]=2;while(top>=0){p=stack[top];//2表示是根//退棧并凹入顯示該結(jié)點(diǎn)值n=level[top][0];for(i=1;i<=n;i++)printf("");//其中n為顯示場(chǎng)寬,字符以右對(duì)齊顯示printf("%c(%c)",p->data,childtype[level[top][1]]);for(i=n+1;i<=MaxWidth;i+=2)printf("━");printf("\n");top--;if(p->rchild){//將右子樹(shù)根結(jié)點(diǎn)入棧top++;stack[top]=p->rchild;level[top][0]=n+width;//顯示場(chǎng)寬增widthlevel[top][1]=1;}//1表示是右子樹(shù)if(p->lchild){//將左子樹(shù)根結(jié)點(diǎn)入棧43

top++;stack[top]=p->lchild;level[top][0]=n+width;//顯示場(chǎng)寬增widthlevel[top][1]=0;//0表示是左子樹(shù)}}}elseprintf("該二叉樹(shù)是一棵空二叉樹(shù)!\n");returnOK;}StatusDisplayBiTreeInBracket(BiTreeT){//以嵌套括號(hào)表示法輸出一棵二叉樹(shù)if(T){printf("%c",T->data);if(T->lchild||T->rchild){printf("(");if(T->lchild)DisplayBiTreeInBracket(T->lchild);//遞歸處理左子樹(shù)if(T->rchild)printf(",");if(T->rchild)DisplayBiTreeInBracket(T->rchild);//遞歸處理右子樹(shù)printf(")");}44

}elseprintf("該二叉樹(shù)是一棵空二叉樹(shù)!");returnOK;}voidmain(){BiTreeT;charch,j;charstr[200];intchoice,flag=1,len,i;Statustemp;printf("本程序?qū)崿F(xiàn)二叉樹(shù)的操作:\n");printf("可以進(jìn)行建立二叉樹(shù),遞歸先序、中序、后序遍歷等操作。\n");CreateBiTree(T);while(flag){printf("請(qǐng)選擇:\n");printf("1.遞歸先序遍歷\n");printf("2.遞歸中序遍歷\n");printf("3.遞歸后序遍歷\n");printf("4.凹入表示法輸出二叉樹(shù)\n");printf("5.嵌套括號(hào)表示法輸出二叉樹(shù)\n");printf("6.重新構(gòu)建二叉樹(shù)\n");45

printf("7.退出程序\n");scanf("%d",&choice);switch(choice){case1:if(T){printf("先序遍歷二叉樹(shù):");PreOrderTraverse(T,PrintElement);//先序遞歸遍歷二叉樹(shù)printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;case2:if(T){printf("中序遍歷二叉樹(shù):");InOrderTraverse(T,PrintElement);//中序遞歸遍歷二叉樹(shù)printf("\n");}elseprintf("二叉樹(shù)為空!\n");break;c