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

《數(shù)據(jù)結(jié)構(gòu)與算法》

試驗(yàn)指導(dǎo)書(shū)

2022年8月

目錄

試驗(yàn)一C語(yǔ)言編程復(fù)習(xí)1

試驗(yàn)二線形表基本操作的實(shí)現(xiàn)5

試驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用14

試驗(yàn)四二叉樹(shù)算法的實(shí)現(xiàn)24

試驗(yàn)五圖的算法的實(shí)現(xiàn)36

試驗(yàn)六查找算法的實(shí)現(xiàn)52

試驗(yàn)七排序算法的實(shí)現(xiàn)62

試驗(yàn)一C語(yǔ)言編程復(fù)習(xí)

一、試驗(yàn)?zāi)康?/p>

1.熟識(shí)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)潔排序方法。

二、試驗(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è)紀(jì)錄，每個(gè)紀(jì)錄包

括學(xué)號(hào)、姓名、三門(mén)課程的成果和三門(mén)課程平均成果。從鍵盤(pán)輸入

同學(xué)的學(xué)號(hào)、姓名及三門(mén)課的成果。要求打印三門(mén)課程平均成果最

高分的同學(xué)紀(jì)錄。

三、試驗(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)、姓名、成果等成員。

四、實(shí)現(xiàn)提示

structstudent

{charnum[6];

stringname;

floatscore[3];

floataver;

);

五、思索與提高

思索為何voidSwap1(Student,Student)這個(gè)函數(shù)無(wú)法實(shí)現(xiàn)兩個(gè)同學(xué)的交

換？

六、完整參考程序

1、

#include<iostream>

#include<string>

usingnamespacestd;

voidmainO

(

cout?！ㄝ斎雗個(gè)單詞，單詞之間用空格隔開(kāi)〃<lndl;

stringstr;

getline(cin,str);

intnum=0;

intlen=str.size();

if(len!=0)num=l;

for(inti=0;i<len;i++)

if(str[i]=='')

(

num++;

)

)

cout<<〃單詞個(gè)數(shù)為：〃〈<num〈〈6ndl;

)

也可使用數(shù)組實(shí)現(xiàn)：

^include<iostream>

usingnamespacestd;

voidmainO

(

cout<<〃輸入n個(gè)單詞，單詞之間用空格隔開(kāi)〃Gendl;

charstr[100];

cin>>str;

intnum=0;

for(inti=0;str[i]!='\0';i++)

(

if(str[i]=,f)

(

num++;

)

}

cout<〈〃單詞個(gè)數(shù)為：〃《num<<endl;

)

2、

#include<iostream>

usingnamespacestd;

structcomplex

{

floatreal;

floatimag;

};一

complexadd(complexxl,complexx2)

(

complexsum;

sum.real=xl.real+x2.real;

sum.imag=xl.imag+x2.imag;

returnsum;

voidmain()

(

complexx1={2,3},x2={4,5},sum;

complexadd(complexxl,complexx2);

sum=add(xl,x2);

cout?ux1="?xl.real?"+,,?xl.imag?nin?n

n?nx2=n?x2.real?',+',?x2.imag?,,i',?endl;

cout?nx1+x2=',?sum.real?n4-,,?sum.imag?',i,,?endl;

)

3、

#include<iostream>

#include<string>

#include<iomanip>

usingnamespacestd;

constintn=3;

structstudent

{charnum[6];

stringname;

floatscore[3];

floataver;

);

intmain()

{intij,maxi,max,sum;

floataverage;

studentstudfn];

for(i=0;i<n;i++)〃輸入同學(xué)和成果信息

{cout?"inputscoresofstudentn?i+l?endl;

cout?"number:H;

cin?stud[i].num;

cout?"name:";

cin?stud[i].name;

for(j=O；j<3;j++)

{cout?nscoren?j+l?n:n;

cin?stud[i].score[j];

)

cout?endl;

)〃輸入同學(xué)和成果信息

average=0;

max=0;

maxi=0;

for(i=0;i<n;i++)

{sum=0;

for(j=0;j<3;j++)〃計(jì)算每個(gè)同學(xué)總成果

sum+=stud[i].score[j];

studfi].aver=sum/3.0;//計(jì)算每個(gè)同學(xué)平均成果

if(sum>max)〃將某同學(xué)平均成果與目前的最高平均成果進(jìn)行比較

選擇高的那個(gè)為最新最高平均成果

{max=sum;

maxi=i;

cout?"score1score2score3average"?endl;

for(i=0;i<n;i++)〃輸出全部同學(xué)成果信息

{cout?setw(8)?stud[i].num?H"?setw(10)?stud[i].name?n”；

for(j=0;j<3;j++)

cout<vsetw(3)?stud[i].score[jkv"”；

cout?stud[i].aver?endl;}〃輸出全部同學(xué)成果信息

cout?nThehighestscoreis:n?stud[maxi].num?n,K?stud[maxi].name?n,

n?nTheaverageis:"?stud[maxi].aver;

cout?",threescores:n;〃輸出最高平均成果的同學(xué)信息

for(j=0;j<3;j++)

cout?stud[maxi].score[j]?nn;

cout?endl;

return0;

試驗(yàn)二線形表基本操作的實(shí)現(xiàn)

一、試驗(yàn)?zāi)康?/p>

1.熟識(shí)C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步把握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。

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)——單鏈表中的各種基本操作。

二、試驗(yàn)內(nèi)容

1.挨次線性表的建立、插入及刪除。

2.鏈?zhǔn)骄€性表的建立、插入及刪除。

三、試驗(yàn)步驟

1.建立含n個(gè)數(shù)據(jù)元素的挨次表并輸出該表中各元素的值及挨次表的長(zhǎng)

度。

2.采用前面的試驗(yàn)先建立一個(gè)挨次表L=[21,23,14,5,56,17,31},

然后在第i個(gè)位置插入元素68o

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)型定義挨次表：

#defineMAXSIZE1024

typedefintelemtype;/*線性表中存放整型元素*/

typedefstruct

{elemtypevecfMAXSIZE];

intlen;/*挨次表的長(zhǎng)度*/

}sequenlist;

將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避開(kāi)在后面的參考程序中代

碼重復(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(siz60f(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)。

五、思索與提高

1.假如按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立挨次表。

2.在main函數(shù)里假如去掉L二&a語(yǔ)句，會(huì)消失什么結(jié)果？

六、完整參考程序

#include<stdio.h>

#include<conio.h>

#defineMAX30〃定義線性表的最大長(zhǎng)度

enumBOOL{False,True);〃定義BOOL型

typedefstruct{

charelem[MAX];〃線性表

intlast;//last指示當(dāng)前線性表的長(zhǎng)度

Jsqlist;

voidinitial(sqlist&);〃初始化線性表

BOOLinsert(sqlist&,int,char);〃在線性表中插入元素

BOOLdel(sqlist&Jnt,char&);//在線性表中刪除元素

intlocate(sqlist,char);〃在線性表中定位元素

voidprint(sqlist);〃顯示線性表中全部元素

voidmain()

{sqlistS;//S為一線性表

intloc,flag=l;

charj,ch;

BOOLtemp;

printff本程序用來(lái)實(shí)現(xiàn)挨次結(jié)構(gòu)的線性表。\nn);

printf("可以實(shí)現(xiàn)查找、插入、刪除等操作。\n")；

initial(S);〃初始化線性表

while(flag)

{printf("請(qǐng)選擇:\n");

printf("1.顯示全部元素5”)；

printf(”2.插入一個(gè)元素\n")；

printf("3.刪除一個(gè)元素\n")；

printf("4.查找一個(gè)元素曲”)；

printf("5.退出程序\nn);

scanf(M%c'\&j);

switch(j)

{case*r：print(S);break;//顯示全部元素

case2:{printf(”請(qǐng)輸入要插入的元素(一個(gè)字符)和插入位置:\n")；

printf(”格式:字符，位置;例如:a,2\n");

scanf("%c,%dH,&ch,&loc);〃輸入要插入的元素和插入的位置

temp=insert(S,loc,ch);〃插入

if(temp==False)printf("插入失敗八n")；〃插入失敗

else{printf("插入勝利!\n");print(S);}〃插入勝利

break;

)

case3:{printf("請(qǐng)輸入要?jiǎng)h除元素的位置蜜

scanf("%d",&loc);〃輸入要?jiǎng)h除的元素的位置

temp=del(S,loc,ch);〃刪J除

if(temp==True)printf(”刪除了一個(gè)元素:％c\n”,ch);//刪除勝利

elseprintf(“該元素不存在!\n")；〃刪除失敗

print(S);

break;

)

case'4':{printf("請(qǐng)輸入要查找的元素:")；

scanf("%c",&ch);〃輸入要查找的元素

loc=locate(S,ch);//定位

if(loc!=-l)printf("該元素所在位置:％d\n",loc+l);//顯示該元素位置

elseprintf("%c不存在!\n",ch);〃當(dāng)前元素不存在

break;

)

default:flag=O;printf("程序結(jié)束,按任意鍵退出!\n")；

)

)

getch();

voidinitial(sqlist&v)

{〃初始化線性表

inti;

printf(”請(qǐng)輸入初始線性表長(zhǎng)度：n=)〃輸入線性表初始化時(shí)的長(zhǎng)度

scanf(u%d",&v.last);

printf(”請(qǐng)輸入從1到％(1的各元素(字符)，例如:abcdefgW”,v.last);

getchar();

for(i=0;i<v.last;i++)scanf(H%cn,&v.elem[i]);//輸入線性表的各元素

}

BOOLinsert(sqlist&v,intloc,charch)

{//插入一個(gè)元素，勝利返回True,失敗返回False

inti;

if((loc<l)||(loc>v.last+1))

{printf("插入位置不合理!\n")；〃位置不合理

returnFalse;

)

elseif(v.last>=MAX)〃線性表已滿

{printf("線性表已滿!\n");

returnFalse;

)

else{for(i=v.last-l;i>=loc-l;i—)v.elem[i+1J=v.elem[iJ;〃其后元素依次后移

v.elem[loc-l]=ch;〃插入元素

v.last++;〃線性表長(zhǎng)度加一

returnTrue;

)

)

BOOLdel(sqlist&v,intloc,char&ch)

{//刪除一個(gè)元素，勝利返回True,并用ch返回該元素值，失敗返回False

intj;

if(loc<l||loc>v.last)〃刪除位置不合理

returnFalse;

else{ch=v.elem[loc-l];//ch取得該元素值

for(j=loc-1;j<v.last-l;j++)v.elem[jj=v.elem[j+1];〃其后元素依次前移

v.last—;〃線性表長(zhǎng)度減一

returnTrue;

)

)

intlocate(sqlistv,charch)

{〃在線性表中查找ch的位置，勝利返回其位置，失敗返回-I

inti=0;

while(i<v.last&&v.elem[i]!=ch)i++;〃當(dāng)前位置后移，直到找到為止

if(v.elem[i]==ch)//找到當(dāng)前元素

returni;

elsereturn(-l);

)

voidprint(sqlistv)〃顯示當(dāng)前線性表全部元素

{inti;

for(i=0;i<v.last;i++)printf(n%cn,v.elem[i]);

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=l;

charj,ch;

printf("本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的線性表的操作。\nn);

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("l.顯示全部元素\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.退出程序\n")；〃退出

scanf(n%c”,&j);

switch(j)

{case'r：ListPrint(L);break;

case2:{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;

)

case3:printf("請(qǐng)輸入要?jiǎng)h除的元素所在位置

scanf(n%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(n%c",&ch);〃輸入要查找的元素

temp=ListFind_keyword(L,ch,loc);//按關(guān)鍵字查找

if(temp==False)printf("沒(méi)有找到該元素!\n");〃查找失敗

elseprintf("該元素在鏈表的第％(1個(gè)位置。\n'\loc);

//勝利查找，顯示該元素位置

)

break;

case,5,:if(L->next==NULL)〃鏈表為空

primf("鏈表為空!\n”);

else{primf("請(qǐng)輸入要查找的位置

scanf("%d",&loc);〃輸入要查找的元素的位置

temp=ListFind_order(L,ch,loc);〃按序號(hào)查找

if(temp==False)printf("該位置不存在!\n");〃查找失敗

elseprintf("第％d個(gè)元素是：%c\nH,loc,ch);

//勝利查找，顯示該元素

break;

default:flag=O;printf("程序結(jié)束,按任意鍵退出!\n");

)

}

getch();

}

voidCreatList(LinkList&v,intn)

{〃生成一個(gè)帶頭結(jié)點(diǎn)的有n個(gè)元素的單鏈表

inti;

LinkListp;

v二(LinkLisl)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(n%cn,&p->data);

p->next=v->next;

v->next=p;

}

)

BOOLListInsert(LinkList&v,inti,chare)

{//在單鏈表的第i各位置插入元素e,勝利返回True,失敗返回False

LinkListp,s;

intj=O;

p=v;

while(p&&j<i-l){p=p->next;++j;)〃查找第i-1個(gè)元素的位置

if(!plU>i-l)returnFalse;〃沒(méi)有找到

s=(LinkList)malloc(LEN);〃生成一個(gè)新結(jié)點(diǎn)

s->data=e;

s->next=p->next;〃將新結(jié)點(diǎn)插入到單鏈表中

p->next=s;

returnTrue;

)

BOOLListDelete(LinkList&v,inti,char&e)

{〃在單鏈表中刪除第i個(gè)元素,勝利刪除返回True,并用e返回該元素值，失敗返回False

LinkListp,q;

intj=O;

p=v;

while(p->next&&j<i-1)//查找第i-1個(gè)元素位置

{p=p->next;++j;}

if(!(p->next)||j>i-l)returnFalse;〃查找失敗

q=p->next;p->next=q->next;〃刪除該元素

e=q->data;//e取得該元素值

free(q);〃釋放該元素空間

returnTrue;

)

BOOLListFind_keyword(LinkListv,chare,int&i)

{〃在單鏈表中查找關(guān)鍵字為e的元素，勝利返回True,并用i返回該元素位置,

〃失敗返回False

i=l；

LinkListp;

p=v->next;

while((p->data!=e)&&(p->next!=NULL))//p指針指向下一個(gè),直到

{p=p->next;i++;}〃找到或到鏈表尾為止

if(p->data!=e)〃該元素在鏈表中不存在

returnFalse;

elsereturnTrue;

)

BOOLListFind_order(LinkListv,char&e,inti)

{〃在單鏈表中查找第i個(gè)元素，勝利返回True,并用e返回該元素值，

〃失敗返回False

LinkListp;

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;〃查找勝利，用e取得該元素值

returnTrue;

}

)

voidListPrint(LinkListv)

{〃顯示鏈表全部元素

LinkListq;

q=v->next;

printf("鏈表全部元素

while(q!=NULL)

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

printf(n\n");

試驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用

一、試驗(yàn)?zāi)康?/p>

1.把握棧的挨次表示和實(shí)現(xiàn)

2.把握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

二、試驗(yàn)內(nèi)容

1.編寫(xiě)一個(gè)程序?qū)崿F(xiàn)挨次棧的各種基本運(yùn)算。

2.實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。

三、試驗(yàn)步驟

1.初始化挨次棧

2.插入元素

3.刪除棧頂元素

4.取棧頂元素

5.遍歷挨次棧

6.置空挨次棧

7.初始化并建立鏈隊(duì)列

8.入鏈隊(duì)列

9.出鏈隊(duì)列

10.遍歷鏈隊(duì)列

四、實(shí)現(xiàn)提示

1./*定義挨次棧的存儲(chǔ)結(jié)構(gòu)*/

typedefstruct{

ElemTypestack[MAXNUM];

inttop;

}SqStack;

/*初始化挨次棧函數(shù)列

voidInitStack(SqStack*p)

{q=(SqStack*)manoc(sizeof(SqStack)/*申請(qǐng)空間*/)

/*入棧函數(shù)號(hào)

voidPush(SqStack*p,ElemTypex)

{if(p->top<MAXNUM-l)

{p->top=p->top+1;/*棧頂+1*/

p->stackfp->top]=x;}/*數(shù)據(jù)入棧*/

)

/*出棧函數(shù)*/

ElemTypePop(SqStack*p)

{x=p->stack[p->top];/*將棧頂元素賦給x*/

p->top=p->top-l;}/*棧頂-1*/

/*獵取棧頂元素函數(shù)刃

ElemTypeGetTop(SqStack*p)

{x=p->stackfp->top];}

/*遍歷挨次棧函數(shù)刃

voidOutStack(SqStack*p)

{for(i=p->top;i>=0;i-)

printf("第％d個(gè)數(shù)據(jù)元素是：%6d\nn,i,p->stack[i]);}

/*置空挨次棧函數(shù)*/

voidsetEmpty(SqStack*p)

{p->top=-l;}

2./*定義鏈隊(duì)列*/

typedefstructQnode

{ElemTypedata;

structQnode*next;

JQnodetype;

typedefstruct

{Qnodetype*front;

Qnodetype*rear;

JLqueue;

/*初始化并建立鏈隊(duì)列函數(shù)*/

voidcreat(Lqueue*q)

{h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請(qǐng)空間*/

h->next=NULL;

q->front=h;

q->rear=h;

for(i=l;i<=n;i++)*采用循環(huán)快速輸入數(shù)據(jù)*/

{scanf("%dn,&x);

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(n%d—>",p->data);

p=p->next;

)

)

五、思索與提高

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>

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

typedefintStatus;

typedefintSElemType;

//---棧的挨次存儲(chǔ)表示—-

#defineSTACKJNIT.SIZE100

#defineSTACKINCREMENT10

typedefstruct{

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è)空棧S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);〃存儲(chǔ)安排失效

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack

StatusDestroyStack(SqStack&S){〃銷(xiāo)毀棧S

if(S.base)free(S.base);

S.top=S.base=NULL;

returnOK;

}//InitStack

StatusStackDisplay(SqStack&S){〃顯示棧S

SElemType*p=S.base;

inti=0;

if(S.base==S.top){

printf(”堆棧已空!\n")；

returnOK;

)

while(p<S.top)

printf("[%d:%d]",++i,*p++);

printf("\n”)；

returnOK;

}//StackDisplay

StatusGetTop(SqStackS,SElemType&e){

〃若棧不空，則用e返回S的棧頂元素，

〃并返回OK;否則返回ERROR

if(S.top==S.base)returnERROR;

e=*(S.top-l);

returnOK;

}//GetTop

StatusPush(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;

}//Push

StatusPop(SqStack&S,SElemType&e){

〃若棧不為空，則刪除S的棧頂元素，

〃用e返回其值，并返回OK;否則返回ERROR

if(S.top==S.base)returnERROR;

e=*—S.top;

returnOK;

}//Pop

StatusStackEmpty(SqStackS){

〃若S為空棧，則返回TRUE,否則返回FALSE。

if(S.top==S.base)returnTRUE;

elsereturnFALSE;

)//StackEmpty

voidmain(){

SqStackSt;

Statustemp;

intflag=I,ch;

inte;

printf("本程序?qū)崿F(xiàn)挨次結(jié)構(gòu)的堆棧的操作。\nu);

printf("可以進(jìn)行入棧，出棧，取棧頂元素等操作。\nn);

InitStack(St);〃初始化堆棧St

while(flag){

printf("請(qǐng)選擇:\n");

printf("l.顯示棧中全部元素W");

printf(”2.入棧\n");

printf("3.出棧

printf(”4.取棧頂元素W”)；

printf(”5.退出程序

scanf("％d”,&ch);

switch(ch){

case1:

StackDisplay(St);

break;

case2:

printf(”請(qǐng)輸入要入棧的元素(一個(gè)整數(shù)):")；

scanf(u%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("堆棧巳空!\nu);

else{

printf("勝利出棧一個(gè)元素:％d\n”,e);〃勝利出棧

StackDisplay(St);

}

break;

case4:

temp二GetTop(St,e);〃取得棧頂元素

if(temp==ERROR)printf(”堆棧已空!\nH);

elseprinlf("棧頂元素是:％d\n”,e);〃顯示棧頂元素

break;

default:

flag=O;

printf("程序結(jié)束，按任意鍵退出!\n");

getch();

DestroyStack(St);

2.隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#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)

QElemTypedata;〃數(shù)據(jù)域

structQNode*next;//指針域

}QNode,*QueuePlr;

typedefstructlinkqueue{〃定義隊(duì)列結(jié)構(gòu)

QueuePtrfront;〃隊(duì)頭指針

QueuePtrrear;〃隊(duì)尾指針

)LinkQueue;

StatusInitLinkQueue(LinkQueue&);〃初始化一個(gè)隊(duì)列

StatusDestroyLinkQueue(LinkQueue&);〃銷(xiāo)毀一個(gè)隊(duì)列

intLinkQueueLength(LinkQueue&Q);〃隊(duì)列的長(zhǎng)度

StatusEnLinkQueue(LinkQueue&,QElemType);〃將一個(gè)元素入隊(duì)列

StatusDeLinkQueue(LinkQueue&,QElemType&);〃將一個(gè)元素出隊(duì)列

StatusDisplayLinkQueue(LinkQueue);〃顯示隊(duì)列中全部元素

voidmain(){

LinkQueueLQ;

QElemTypee;

intflag=l,ch,len;

Statustemp;

printfC,本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列的操作。\nn);

printf("可以進(jìn)行入隊(duì)列、出隊(duì)列等操作。\nM);

InitLinkQueue(LQ);〃初始化隊(duì)列

while(flag){

printf("請(qǐng)選擇:\n");

printf(M1.顯示隊(duì)列全部元素\n”)；

printf(”2.入隊(duì)列\(zhòng)n");

printf(”3.出隊(duì)列\(zhòng)n");

printf(”4.求隊(duì)列的長(zhǎng)度\n”);

printf(”5.退出程序\n");

scanf("％d”,&ch);

switch(ch){

case1:DisplayLinkQueue(LQ);〃顯示隊(duì)列中全部元素

break;

case2:prinlf("請(qǐng)輸入要人隊(duì)的元素(一個(gè)整數(shù)):")；

scanf("%dn,&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\nn,len);

break;

default:flag=O;

printf("程序運(yùn)行結(jié)束，按任意鍵退出!\n)

getch();

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;

Q.rear->next=p;〃插入至隊(duì)列尾

Q.rear=p;〃修改隊(duì)尾指針

returnOK;

StatusDeLinkQueue(LinkQueue&Q,QElemType&e){〃出隊(duì)歹“

QueuePtrp;

if(Q.front==Q.rear)returnERROR;〃推斷隊(duì)列是否已空，已空返回ERROR

p=Q.front->next;〃p指向隊(duì)列中第一個(gè)元素

e=p->data;//取得該元素值

Q.front->next=p->next;〃修改隊(duì)首指針

if(Q.rear==p)Q.rear=Q.front;〃若隊(duì)列已空，把隊(duì)尾指針指向頭結(jié)點(diǎn)

returnOK;〃勝利出隊(duì)列，返回0K

StatusDisplayLinkQueue(LinkQueueQ){〃顯示隊(duì)列中全部元素

QueuePtrp;

inti=0;

p=Q.front->next;

if(p==NULL)printf("隊(duì)列為空隊(duì)列為空

else{

while(p){〃否則顯示隊(duì)列中全部元素

printf(,'[%d:%d]*',++i,p->data);

p=p->next;

)

printf(n\n");

)

returnOK;

)

試驗(yàn)四二叉樹(shù)算法的實(shí)現(xiàn)

一、試驗(yàn)?zāi)康?/p>

1.通過(guò)試驗(yàn)，把握二叉樹(shù)的建立與存儲(chǔ)

2.通過(guò)試驗(yàn)，把握二叉樹(shù)的遍歷方法

二、試驗(yàn)內(nèi)容

1.練習(xí)二叉樹(shù)的建立與存儲(chǔ)

2.練習(xí)二叉樹(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;

structnodel*s[30];

intj,i,x;

printf("建立二叉樹(shù),輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)

隔開(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=l,對(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;}/*q結(jié)點(diǎn)編號(hào)為奇數(shù)則掛在雙親結(jié)點(diǎn)j

的右邊*/

printf("i,x=");

scanf("%d,%c",&i,&x);}

returns[l];/*返回根結(jié)點(diǎn)地址*/

)

五、思索與提高

1.如何用孩子兄弟表示法存儲(chǔ)樹(shù)？

2.熟識(shí)及難赫夫曼樹(shù)。

六、完整參考程序

1.二叉樹(shù)的建立、存儲(chǔ)與遍歷

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<dos.h>

#include<conio.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#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{//定義二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;〃數(shù)據(jù)域

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)(BiTree。);〃后序遞歸遍歷二

叉樹(shù)

char*pstr;

StatusCreateBiTree(BiTree&T){〃生成一個(gè)二叉樹(shù)(可用兩種方法輸入)

inti,len,choice=0;

charstr[200];

printf("請(qǐng)選擇建立二叉樹(shù)的方法:\n");

printf("l.按先序遍歷的結(jié)果輸入二叉樹(shù)\n");

printf("2.按嵌套括號(hào)表示法輸入二叉樹(shù)\n");

do{

gets(str);

choice=atoi(str);

}while(choice<l||choice>2);

if(choice==l){

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");

printf("/\n");

printf("b\n");

printf("/\\\n");

printf("cd\n");

printf("/\\\n");

printf("ef\n");

printf("\\\n");

printf("g\n");

pstr=gets(str);

len=strlen(str);

for(i=len;i<180;++i)

str[i]='

strfi]=O;

CreateBiTreelnPreOrderResult(T);//初始化二叉樹(shù)

else{

printf("請(qǐng)輸入嵌套括號(hào)表示法表示的二叉樹(shù)，程序據(jù)此建立二叉樹(shù)。\nM);

printf("例如:(a(b(c,d(e(,g),f))))(回車(chē)),建立如下二叉樹(shù):\nn);

printf("a\n");

printf("/\n")；

printf("b\n");

printf("/\\\n");

printf("cd\n");

printf("/\\\n");

printf("ef\n");

printf("\\\n");

printf("g'n")；

pstr=gets(str);

CreateBiTreelnBracket(T);//初始化二叉樹(shù)

returnOK;

)

StatusCreateBiTreeInPreOrderResult(BiTree&T){

〃依據(jù)存放在字符串*str中的光序遍歷二叉樹(shù)的結(jié)果，生成鏈接存儲(chǔ)的二叉樹(shù)。

〃(若某結(jié)點(diǎn)無(wú)左孩子或右孩子，則以空格表示其“孩子

if(!(*pstr)||*pstr=-*){

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)))”

BiTreestackfl00],p;

inttop=0,k;//top為棧指針,k指定是左還是右孩子；

T=NULL;

while(*pstr){

switch(*pstr){

caseV:stack[top++]=p;k=