《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-實(shí)驗(yàn)指導(dǎo)

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

/學(xué)年第一學(xué)期

姓名：________________

學(xué)號(hào)：______________

班級(jí)：______________

指導(dǎo)教師：______________

數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2011

預(yù)備實(shí)驗(yàn)C語(yǔ)言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識(shí)

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

1、復(fù)習(xí)C語(yǔ)言中函數(shù)、數(shù)組、指針、結(jié)構(gòu)體與共用體等的概念。

2、熟悉利用C語(yǔ)言進(jìn)行程序設(shè)計(jì)的一般方法。

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下C語(yǔ)言中的概念

1、函數(shù)：

2、數(shù)組：

3、指針：

4、結(jié)構(gòu)體

5、共用體

三、實(shí)驗(yàn)內(nèi)容和要求

1、調(diào)試程序：輸出100以內(nèi)所有的素?cái)?shù)(用函數(shù)實(shí)現(xiàn))。

#include<>

intisprime(intn){/*判斷一個(gè)數(shù)是否為素?cái)?shù)*/

intm;

for(m=2;01*01<=0;m++)

if(n%m=0)return0;

return1;

}

intmain(){/*輸出100以內(nèi)所有素?cái)?shù)*/

inti;printf("\nH)；

for(i=2;i<100;i++)

if(isprime(i)==1)printf("%4d",i);

return0;

1

運(yùn)行結(jié)果：

2、調(diào)試程序：對(duì)一維數(shù)組中的元素進(jìn)行逆序排列。

#include<>

#defineN10

intmain(){

inta[N]={0,1,2,3,4,5,6,7,8,9],i.temp;

printf(H\ntheoriginalArrayis:\n");

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

printf("%4d",a[i]);

for(匚0;i<N/2;i++){/*交換數(shù)組元素使之逆序*/

temp=a[i];

a[i]=a[N-i-1];

a[N-i-1]=temp;

)

printf("\nthechangedArrayis:\n");

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

printf("%4d",a[i]);

return0;

運(yùn)行結(jié)果:

3、調(diào)試程序：在二維數(shù)組中，若某一位置上的元素在該行中最大，而在該列中最小，則該

元素即為該二維數(shù)組的一個(gè)鞍點(diǎn)。要求從鍵盤(pán)上輸入一個(gè)二維數(shù)組，當(dāng)鞍點(diǎn)存在時(shí)，把鞍點(diǎn)

找出來(lái)。

#incIude<>

#defineM3

#defineN4

intmain(){

inta[M][N],i,j,k;

printf("\n請(qǐng)輸入二維數(shù)組的數(shù)據(jù)：\n”)；

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

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

scanf("%d",&a[i][j]);

for(i=0;i<M;i++){/*輸出矩陣*/

for(j=0：j<N;j++)

printf("%4d",a[i][j]);

printf("\n")；

)

for(i=0;i<M;i++){

k=0;

for(j=1;j<N;j++)/*找出第i行的最大值*/

if(a[i][j]>a[i][k])

k=j；

for(j=0;j<M;j++)/*判斷第i行的最大值是否為該列的最小值*/

if(a[j][k]<a[i][k])

break;

if(j==M)/*在第i行找到鞍點(diǎn)*/

printf("%d,%d,%d\n",a[i][k],i,k);

)

return0;

)

運(yùn)行結(jié)果：

4、調(diào)試程序：利用指針輸出二維數(shù)組的元素。

#incIude<>

intmain(){

inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};

int*p;

for(p=a[0];p<a[0]+12;p++){

if((p_a[0])%4==0)printf("\n")；

printf("%4d",*p);

)

return0;

)

運(yùn)行結(jié)果：

5、調(diào)試程序：設(shè)有一個(gè)教師與學(xué)生通用的表格，教師的數(shù)據(jù)有姓名、年齡、職業(yè)、教研室

四項(xiàng)，學(xué)生有姓名、年齡、專(zhuān)業(yè)、班級(jí)四項(xiàng)，編程輸入人員的數(shù)據(jù)，再以表格輸出。

#incIude<>

#defineN10

structstudent{

charname[8];/*姓名*/

intage;/*年齡*/

charjob;/*職業(yè)或?qū)I(yè)，用s或t表示學(xué)生或教師*/

union{

intcIass;/*班級(jí)*/

charoffice[10];/*教研室*/

Jdepa;

}stu[N];

intmain(){

inti;intn;

printf("\n請(qǐng)輸入人員數(shù)?10):\n");

scanf("%d"，&n);

for(i=0;i<n;i++){/*輸入n個(gè)人員的信息*/

printf("\n請(qǐng)輸入第%(1人員的信息：(nameagejobclass/office)\nH,i+1);

scanf("%s,%d,%c",stu[i].name,&stu[i].age,&stu[i].job);

if(stu[i].job==,s')

scanf("%d",&stu[i].;

eIse

scanf("%sH,stu[i].;

)

printf("nameagejobcIass/officeM);

for(i=0;i<n;i++){/*輸出*/

if(stu[i].job=,s')

printf("%s%3d%3c%d\n",stu[i].name,stu[i].age,stu[i].job,stu[i].;

else

printf("%s%3d%3c%s\n",stu[i].name,stu[i].age,stu[i].job,stu[i].;

)

輸入的數(shù)據(jù)：2

Wang19s99061

Li36tcomputer

運(yùn)行結(jié)果：

四、實(shí)驗(yàn)小結(jié)

五、教師評(píng)語(yǔ)

實(shí)驗(yàn)一順序表與鏈表

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

1、掌握線性表中元素的前驅(qū)、后續(xù)的概念。

2、掌握順序表與鏈表的建立、插入元素、刪除表中某元素的算法。

3、對(duì)線性表相應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行分析。

4、理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)（優(yōu)缺點(diǎn)）。

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下概念

1、線性表：

2、順序表：

3、鏈表：

三、實(shí)驗(yàn)內(nèi)容和要求

1、閱讀下面程序，在橫線處填寫(xiě)函數(shù)的基本功能。并運(yùn)行程序，寫(xiě)出結(jié)果。

#include<>

#incIude<>

#defineERROR0

#defineOK1

#defineINIT_SIZE5/*初始分配的順序表長(zhǎng)度*/

#defineINCREM5/*溢出時(shí)，順序表長(zhǎng)度的增量*/

typedefintElemType;/*定義表元素的類(lèi)型*/

typedefstructSqIist{

ElemType*sIist;/*存儲(chǔ)空間的基地址*/

intlength;/*順序表的當(dāng)前長(zhǎng)度*/

intIistsize;/*當(dāng)前分配的存儲(chǔ)空間*/

1SqIist;

intInitList_sq(SqIist*L);/**/

intCreateList_sq(SqIist*L,intn);/**/

intListInsert_sq(SqIist*L,intiFElemTypee);/**/

intPrintList_sq(Sqlist*L);/*輸出順序表的元素*/

intListDeIete_sq(SqIist*L,inti);/*刪除第i個(gè)元素*/

intListLocate(SqIist*LtEIemTypee);/*查找值為e的元素*/

intInitList_sq(SqIist*L){

L->sIist=(EIemType*)maIIoc(INIT_SIZE*sizeof(EIemType));

if(!L->sIist)returnERROR;

L->Iength=0;

L->listsize=INIT_SIZE;

returnOK;

}/"InitList*/

intCreateList_sq(SqIist*L,intn){

ElemTypee;

inti;

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

printf("inputdata%d",i+1);

scanf("%d",&e);

if(!Listlnsert_sq(L,i+1,e))

returnERROR;

returnOK;

}/*CreateList*/

/*輸出順序表中的元素*/

intPrintList_sq(SqIist*L){

inti;

for(i=1;i<=L->length;i++)

printf("%5d"FL->sIist;

returnOK;

}/*PrintList*/

intListInsert_sq(SqIist*L,inti,EIemTypee){

intk;

if(i<1||i>L->Iength+1)

returnERROR;

if(L->Iength>=L->Iistsize){

L->sIist=(EIemType*)reaIIoc(L->sIist,

(INIT_SIZE+INCREM)*sizeof(ElemType));

if(!L->sIist)

returnERROR;

L->listsize+=INCREM;

)

for(k=L->Iength-1;k>=i-1;k—){

L->slist[k+1]=L->slist[k];

)

L->sIist[i-1]=e;

L->length++;

returnOK;

}/*ListInsert*/

/*在順序表中刪除第i個(gè)元素*/

intListDeIete_sq(SqIist*L,inti){

1

/*在順序表中查找指定值元素，返回其序號(hào)*/

intListLocate(SqIist*L,EIemTypee){

}

intmain(){

SqIistsI;

intn,m,k;

printf("pleaseinputn:'*);/*輸入順序表的元素個(gè)數(shù)*/

scanf("%d",&n);

if(n>0){

printf("\n1-CreateSqIist:\n");

InitList_sq(&sI);

CreateList_sq(&sI,n);

printf("\n2-PrintSqlist:\n");

PrintList_sq(&sI);

printf("\npIeaseinputinsertlocationanddata:(Iocation,data)\n");

scanf("%d,%d",&m,&k);

Listlnsert_sq(&sI,m,k);

printf("\n3-PrintSqlist:\n");

PrintList_sq(&sI);

printf("\n")；

)

eIse

printf("ERROR");

return0;

)

運(yùn)行結(jié)果

算法分析

2、為第1題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。

刪除算法代碼：

運(yùn)行結(jié)果

算法分析

查找算法代碼:

運(yùn)行結(jié)果

算法分析

3、閱讀下面程序，在橫線處填寫(xiě)函數(shù)的基本功能。并運(yùn)行程序，寫(xiě)出結(jié)果。

#include<>

#include<>

#defineERROR0

#defineOK1

typedefintElemType;/*定義表元素的類(lèi)型*/

typedefstructLNode{/*線性表的單鏈表存儲(chǔ)*/

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

LinkListCreateList(intn);/**/

voidPrintList(LinkListL);/*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/

intGetElem(LinkListL,inti,EIemType*e);/**/

LinkListCreateList(intn){

LNode*p,*q,*head;

inti;

head二(LinkList)maIIoc(sizeof(LNode));head->next=NULL;

p=head;

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

q=(LinkList)maIIoc(sizeof(LNode));printf("inputdata%i:",i+1);

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

q->next=NULL;/*結(jié)點(diǎn)指針域置空*/

p->next=q;/*新結(jié)點(diǎn)連在表末尾*/

p=q;

)

returnhead;

}/*CreateList*/

voidPrintList(LinkListL){

LNode*p;

p=L->next;/*p指向單鏈表的第1個(gè)元素*/

while(p!=NULL){

printf("%5d",p->data);

p=p->next;

}/*PrintList*/

intGetElem(LinkListL,inti,EIemType*e){

LNode*p;intj=1;

p=L->next;

while(p&&j<i){

p=p->next;j++;

)

if(!p||j>i)

returnERROR;

*e=p->data;

returnOK;

}/*GetElem*/

intmain(){

intn,i;ElemTypee;

LinkListL二NULL;/*定義指向單鏈表的指針*/

printf(,rpleaseinputn:;/*輸入單鏈表的元素個(gè)數(shù)*/

scanf&n);

if(n>0){

printf("\n1-CreateLinkList:\nn);

L=CreateList(n);

printf("\n2-PrintLinkList:\n");

PrintList(L);

printf("\n3-GetEIemfromLinkList:\n");

printf("inputi=");

scanf("%d",&i);

if(GetElem(L,i,&e))

printf("No%iis%d",i,e);

eIse

printf("notexists");

}eIse

printf("ERROR");

return0;

)

運(yùn)行結(jié)果

算法分析

4、為第3題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。

插入算法代碼：

運(yùn)行結(jié)果

算法分析

刪除算法代碼:

運(yùn)行結(jié)果

算法分析

以下為選做實(shí)驗(yàn)：

5、循環(huán)鏈表的應(yīng)用（約瑟夫回環(huán)問(wèn)題）

n個(gè)數(shù)據(jù)元素構(gòu)成一個(gè)環(huán)，從環(huán)中任意位置開(kāi)始計(jì)數(shù)，計(jì)到m將該元素從表中取出，重復(fù)上

述過(guò)程，直至表中只剩下一個(gè)元素。

提示：用一個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)單鏈表來(lái)實(shí)現(xiàn)n個(gè)元素的存儲(chǔ)。

算法代碼

6、設(shè)一帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)算法將表中值相同的元素僅保留一個(gè)結(jié)點(diǎn)。

提示：指針P從鏈表的第一個(gè)元素開(kāi)始，利用指針q從指針P位置開(kāi)始向后搜索整個(gè)鏈表,

刪除與之值相同的元素；指針P繼續(xù)指向下一個(gè)元素，開(kāi)始下一輪的刪除，直至p==null

為至，既完成了對(duì)整個(gè)鏈表元素的刪除相同值。

算法代碼

四、實(shí)驗(yàn)小結(jié)

五、教師評(píng)語(yǔ)

實(shí)驗(yàn)二棧和隊(duì)列

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

1、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；

2、掌握隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作，掌握循環(huán)隊(duì)列的特點(diǎn)及其操作。

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下概念

1、順序棧：

2、鏈棧：

3、循環(huán)隊(duì)列：

4、鏈隊(duì)

三、實(shí)驗(yàn)內(nèi)容和要求

1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補(bǔ)充完整。要求輸入元素序列12345e,運(yùn)

行結(jié)果如下所示。

#include<>

#incIude<>

#defineERROR0

#defineOK1

#defineSTACK,INT_SIZE10/*存儲(chǔ)空間初始分配量*/

#defineSTACKINCREMENT5/*存儲(chǔ)空間分配增量*/

typedefintElemType;/*定義元素的類(lèi)型*/

typedefstruct{

ElemType*base;

ElemType*top;

intstacksize;/*當(dāng)前已分配的存儲(chǔ)空間*/

}SqStack;

intInitStack(SqStack*S);/*構(gòu)造空棧*/

intpush(SqStack*S,ElemTypee);/*入棧*/

intPop(SqStack*S,EIemType*e);/*出棧*/

intCreateStack(SqStack*S);/*創(chuàng)建棧*/

voidPrintStack(SqStack*S);/*出棧并輸出棧中元素*/

intInitStack(SqStack*S){

S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));

if(!S->base)returnERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE;

returnOK;

}/*lnitStack*/

intPush(SqStack*S,ElemTypee){

}/*Push*/

intPop(SqStack*S,ElemType*e){

}/*Pop*/

intCreateStack(SqStack*S){

inte;

if(InitStack(S))

printf("InitSuccess!\n");

else{

printf("InitFail!\nH);

returnERROR;

)

printf(ninputdata:(Terminatedbyinputingacharacter)\n");

n

while(scanf("%df&e))

Push(S,e);

returnOK;

}/*CreateStack*/

voidPrintStack(SqStack*S){

ElemTypee;

while(Pop(S,&e))

printf("%3d",e);

}/*Pop_and_Print*/

intmain(){

SqStackss;

printf("\n1"createStack\n");

CreateStack(&ss);

printf("\n2-Pop&Print\n");

PrintStack(&ss);

return0;

1

算法分析：輸入元素序列12345,為什么輸出序列為54321體現(xiàn)了棧的什么特

性

2、在第1題的程序中，編寫(xiě)一個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的數(shù)制轉(zhuǎn)換算法函數(shù)(要求利用棧來(lái)

實(shí)現(xiàn))，并驗(yàn)證其正確性。

實(shí)現(xiàn)代碼

驗(yàn)證

3、閱讀并運(yùn)行程序，并分析程序功能。

#include<>

#incIude<>

#incIude<>

#defineM20

#defineeIemtypechar

typedefstruct

elemtypestack[M];

inttop;

)

stacknode;

voidinit(stacknode*st);

voidpush(stacknode*st,eIemtypex);

voidpop(stacknode*st);

voidinit(stacknode*st)

(

st->top=0;

)

voidpush(stacknode*stteIemtypex)

(

if(st->top=M)

printf("thestackisoverfIow!\n");

else

(

st->top=st->top+1;

st->stack[st->top]=x;

)

)

voidpop(stacknode*st)

(

if(st->top>0)st->top-;

eIseprintf("StackisEmpty!\n,5);

)

intmain0

chars[M];

inti;

stacknode*sp;

printf("createaemptystack!\n");

sp=maIIoc(sizeof(stacknode));

init(sp);

printf(ninputaexpression:\n");

gets(s);

for(i=0;i<strlen(s);i++)

(

if(s[i]=*(1)

push(sp,s[i]);

if(s[i]==')')

pop(sp);

)

if(sp->top-0)

printf("'('match')'!\n");

eIse

printf("'(*notmatch')'!\n");

return0;

輸入：2+((c-d)*6-(f-7)*a)/6

運(yùn)行結(jié)果：

輸入：a-((c-d)*6-(s/3-x)/2

運(yùn)行結(jié)果：

程序的基本功能:

以下為選做實(shí)驗(yàn):

4、設(shè)計(jì)算法，將一個(gè)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并按照后綴表達(dá)式進(jìn)行計(jì)算，得出表達(dá)式

得結(jié)果。

實(shí)現(xiàn)代碼

5、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)（不設(shè)隊(duì)頭指針）,

試編寫(xiě)相應(yīng)的置空隊(duì)列、入隊(duì)列、出隊(duì)列的算法。

實(shí)現(xiàn)代碼：

四、實(shí)驗(yàn)小結(jié)

五、教師評(píng)語(yǔ)

實(shí)驗(yàn)三串的模式匹配

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

1、了解串的基本概念

2、掌握串的模式匹配算法的實(shí)現(xiàn)

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下概念

1、模式匹配:

2、BF算法:

3、KMP算法：

三、實(shí)驗(yàn)內(nèi)容和要求

1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫(xiě)出運(yùn)行結(jié)果。

#include<>

#incIude<>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

JSqString;

intstrCompare(SqString*s1,SqString*s2);/*串的比較*/

voidshow_strCompare();

voidstrSub(SqString*s,intstart,intsubIen,SqString*sub);

/*求子串*/

voidshow_subString();

intstrCompare(SqString*s1,SqString*s2){

inti;

for(i=0;i<s1->length&&i<s2->Iength;i++)

if(s1->data[i]!=s2->data[i])

returns1->data[i]-s2->data[i];

returns1->Iength-s2->Iength;

)

voidshow_strCompare(){

SqStrings1,s2;

intk;

printf("\n***showCompare***\n");

printf("inputstrings1:");

gets;

=strlen;

printf('*inputstrings2:");

gets;

=strlen;

if((k=strCompare(&s1,&s2))==0)

printf("s1=s2\n");

eIseif(k<0)

printf("s1<s2\n");

else

printf("s1>s2\n");

printf("\n***showover***\n");

voidstrSub(SqString*s,intstart,intsubIen,SqString*sub){

inti;

if(start<1||start>s->Iength||subIen>s->Iength-start+1){

sub->length=0;

}

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

sub->data[i]=s->data[start+i-1];

sub->Iength=subIen;

)

voidshow_subString(){

SqStrings,sub;

intstart,subIen,i;

printf("\n***showsubString***\n");

printf(ninputstrings:;

gets;

二strlen;

printf("inputstart:");

scanf(n%d",&start);

printf("inputsubIen:");

scanf(u%d",&sublen);

strSub(&s,start,subIen,&sub);

if=0)

printf("ERROR!\n");

eIse{

printf("subStringis:");

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

printf("%c",[i]);

)

printf(M\n***showover***\n");

)

intmain(){

intn;

do{

printf("\n---String---\n");

printf("1.strCompare\n");

printf("2.subString\n");

printf("0.EXIT\n,r);

printf(u\ninputchoice:");

scanf("%dH,&n);

getchar();

switch(n){

case1:show_strCompare();break;

case2:show_subString();break;

defauIt:n=0;break;

)

}while(n);

return0;

)

運(yùn)行程序

輸入：

1

student

students

2

ComputerDataStuctures

10

4

運(yùn)行結(jié)果：

2、實(shí)現(xiàn)串的模式匹配算法。補(bǔ)充下面程序，實(shí)現(xiàn)串的BF和KMP算法。

#include<>

#incIude<>

#defineMAXSIZE100

typedefstruct{

chardata[MAXSIZE];

intlength;

ISqString;

intindex_bf(SqString*s,SqString*t,intstart);

voidgetNext(SqString*t,intnext[]);

intindex_kmp(SqString*s,SqString*t,intstart,intnext[]);

voidshow_index();

intindex_bf(SqString*s,SqString*t,intstart){

補(bǔ)充代碼一.一

)

voidgetNext(SqString*t,intnext[]){

inti=0,j=-1;

next[0]=-1;

whiIe(i<t->Iength){

if((j=-1)||(t->data[i]==t->data[j])){

i++;j++；next[i]=j;

)eIse

j=next[j];

)

)

intindex_kmp(SqString*s,SqString*ttintstart,intnext[]){

補(bǔ)充代碼.????

voidshow_index(){

SqStrings,t;

intk,next[MAXSIZE]={0},i;

printf("\n***showindex***\n");

printf("inputstrings:");

gets;

=strlen;

printf("inputstringt:n);

gets;

=strlen;

printf("inputstartposition:");

scanf(H%d",&k);

printf("BF:\ntheresultofBFis%d\nu,index_bf(&s,&t,k));

getNext(&t,next);

printf("KMP:\n");

printf(Hnext[]:");

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

printf("%3d"fnext[i]);

printf("\nn)；

n

printf(theresultofKMPis%d\n",index_kmp(&s,&trk,next));

printf("\n***showover***\n");

)

intmain(){

show_index();

return0;

)

輸入：

abcaabbabcabaacbacba

abcabaa

1

運(yùn)行結(jié)果:

四、實(shí)驗(yàn)小結(jié)

五、教師評(píng)語(yǔ)

實(shí)驗(yàn)四二叉樹(shù)

一'實(shí)驗(yàn)?zāi)康?/p>

1、掌握二叉樹(shù)的基本特性

2、掌握二叉樹(shù)的先序、中序、后序的遞歸遍歷算法

3、理解二叉樹(shù)的先序、中序、后序的非遞歸遍歷算法

4、通過(guò)求二叉樹(shù)的深度、葉子結(jié)點(diǎn)數(shù)和層序遍歷等算法，理解二叉樹(shù)的基本特性

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下概念

1、二叉樹(shù)：

2、遞歸遍歷：

3、非遞歸遍歷：

4、層序遍歷：

三、實(shí)驗(yàn)內(nèi)容和要求

1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫(xiě)出運(yùn)行結(jié)果，并畫(huà)出二叉樹(shù)的形態(tài)。

#include<>

#incIude<>

#defineMAX20

typedefstructBTNode{/*節(jié)點(diǎn)結(jié)構(gòu)聲明*/

chardata;/*節(jié)點(diǎn)數(shù)據(jù)*/

structBTNode*lchiId;

structBTNode*rchiId;/*指針*/

}*BiTree;

voidcreateBiTree(BiTree*t){/*先序遍歷創(chuàng)建二叉樹(shù)*/

chars;

BiTreeq;

printf("\npIeaseinputdata:(exitfor#)");

s二getche();

if(s='#'){*t=NULL;return;)

q=(BiTree)maIIoc(sizeof(structBTNode));

if(q==NULL)(printf("MemoryallocfaiIure!");exit(0);}

q->data=s;

*t=q；

createBiTree(&q->IchiId);/*遞歸建立左子樹(shù)*/

createBiTree(&q->rchiId);/*遞歸建立右子樹(shù)*/

)

voidPreOrder(BiTreep){/*先序遍歷二叉樹(shù)*/

if(p!=NULL){

printf("%cn,p->data);

PreOrder(p->lchiId);

PreOrder(p->rchiId);

)

)

voidInOrder(BiTreep){/*中序遍歷二叉樹(shù)*/

if(p!=NULL){

InOrder(p->IchiId);

printf("%c",p->data);

InOrder(p->rchiId)

voidPostOrder(BiTreep){/*后序遍歷二叉樹(shù)*/

if(p!=NULL){

PostOrder(p->lchiId);

PostOrder(p->rchiId);

printf("%c",p->data);

)

)

voidPreorder_n(BiTreep){/*先序遍歷的非遞歸算法*/

BiTreestack[MAX],q;

inttop=0,i;

for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化棧*/

q=P；

while(q!=NULL){

printfq->data);

if(q->rchiId!二NULL)stack[top++]=q->rchiId;

if(q->IchiId!=NULL)q=q->lchiId;

eIse

if(top>0)q=stack[—top];

elseq=NULL;

)

)

voidrelease(BiTreet){/*釋放二叉樹(shù)空間*/

if(t!二NULL){

reIease(t->IchiId);

reIease(t->rchiId);

free(t);

}

)

intmain(){

BiTreet=NULL;

createBiTree(&t);

printf("\n\nPreOrderthetreeis:");

PreOrder(t);

printf("\n\nInOrderthetreeis:");

InOrder(t);

printf("\n\nPostOrderthetreeis:");

PostOrder(t);

printf("\n\n先序遍歷序列(非遞歸)：”)；

Preorder_n(t);

reIease(t);

return0;

)

運(yùn)行程序

輸入：

ABC##DE#G##F###

運(yùn)行結(jié)果:

2、在上題中補(bǔ)充求二叉樹(shù)中求結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過(guò)程中統(tǒng)計(jì)遍歷的結(jié)點(diǎn)

數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。

算法代碼：

3、在上題中補(bǔ)充求二叉樹(shù)中求葉子結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過(guò)程中統(tǒng)計(jì)遍歷的

葉子結(jié)點(diǎn)數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。

算法代碼：

4、在上題中補(bǔ)充求二叉樹(shù)深度算法，并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。

算法代碼:

選做實(shí)驗(yàn)：（代碼可另附紙）

4、補(bǔ)充二叉樹(shù)層次遍歷算法。（提示：利用隊(duì)列實(shí)現(xiàn)）

5、補(bǔ)充二叉樹(shù)中序、后序非遞歸算法。

四、實(shí)驗(yàn)小結(jié)

五、教師評(píng)語(yǔ)

實(shí)驗(yàn)五圖的表示與遍歷

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

1、掌握?qǐng)D的鄰接矩陣和鄰接表表示

2、掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法

3、理解圖的應(yīng)用方法

二、實(shí)驗(yàn)預(yù)習(xí)

說(shuō)明以下概念

1、深度優(yōu)先搜索遍歷：

2、廣度優(yōu)先搜索遍歷：

3、拓?fù)渑判颍?/p>

4、最小生成樹(shù)：

5、最短路徑：

三、實(shí)驗(yàn)內(nèi)容和要求

1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫(xiě)出運(yùn)行結(jié)果。

#incIude<>

#defineN20

#defineTRUE1

#defineFALSE0

intvisited[N];

typedefstruct/*隊(duì)列的定義*/

intdata[N];

intfront,rear;

1queue;

typedefstruct/*圖的鄰接矩陣*/

intvexnum,arcnum;

charvexs[N];

intarcs[N][N];

)

graph;

voidcreateGraph(graph*g);/*建立一個(gè)無(wú)向圖的鄰接矩陣*/

voiddfs(inti,graph*g);/*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/

voidtdfs(graph*g);/*深度優(yōu)先搜索整個(gè)圖*/

voidbfs(intk,graph*g);/*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/

voidtbfs(graph*g);/*廣度優(yōu)先搜索整個(gè)圖*/

voidinit_visit();/*初始化訪問(wèn)標(biāo)識(shí)數(shù)組*/

voidcreateGraph(graph*g)/*建立一個(gè)無(wú)向圖的鄰接矩陣*/

{inti,j;

charv;

g->vexnum=0;

g->arcnum=0;

i=0;

printf("輸入頂點(diǎn)序列(以#結(jié)束)：\n");

while((v=getchar())!='#')

g->vexs[i]=v;/*讀入頂點(diǎn)信息*/

i++；

)

g->vexnum=i;/*頂點(diǎn)數(shù)目*/

for(i=0;i<g->vexnum;i++)/*鄰接矩陣初始化*/

for(j=0;j<g->vexnum;j++)

g->arcs[i][j]=0;

printf("輸入邊的信息：\n");

scanf(',%d,%d,\&i,&j);/*讀入邊i,j*/

while(i!=-1)/*讀入i,j為一1時(shí)結(jié)束*/

(

g->arcs[i][j]=1;

g->arcs[j][i]=1;

scanf("%d,%d",&i,&j);

voiddfs(inti,graph*g)/*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/

(

intj;

printfg->vexs[i]);

visited[i]=TRUE;

for(j=0;j<g->vexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j]))

dfs(j.g);

voidtdfs(graph*g)/*深度優(yōu)先搜索整個(gè)圖*/

inti;

printf(”\n從頂點(diǎn)%0開(kāi)始深度優(yōu)先搜索序列g(shù)->vexs[0]);

for(i=0;i<g->vexnum;i++)

if(visited[i]!=TRUE)

dfs(i,g);

)

voidbfs(intk,graph*g)/*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/

(

inti,j;

queueqIist,*q;

q二&qlist;

q->rear=0;

q->front=0;

printfg->vexs[k]);

visited[k]=TRUE;

q->data[q->rear]=k;

q->rear=(q->rear+1)%N;

while(q->rear!=q->front)

{

i=q->data[q->front];

q->front=(q->front+1)%N;

for(j=0;j<g->vexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j]))

printf("%c”,g->vexs[j]);

visited[j]=TRUE;

q->data[q->rear]=j;

q->rear=(q->rear+1)%N;

)

voidtbfs(graph*g)/*廣度優(yōu)先搜索整個(gè)圖*/

(

inti;

printf(“\n從頂點(diǎn)%C開(kāi)始廣度優(yōu)先搜索序列：“，g->vexs[0]);

for(i=0;i<g->vexnum;i++)

if(visited[i]!=TRUE)

bfs(i,g);

)

voidinit_visit()/*初始化訪問(wèn)標(biāo)識(shí)數(shù)組*/

(

inti;

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

visited[i]=FALSE;

}

intmain()

(

graphga;

inti,j;

createGraph(&ga);

printf("無(wú)向圖的鄰接矩陣：\n");

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

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

printf("%3d",[i][j]);

printf("\n")；

init_visit();

tdfs(&ga);

init_visit();

tbfs(&ga);

return0;

)

根據(jù)右圖的結(jié)構(gòu)驗(yàn)證實(shí)驗(yàn)，輸入：

ABCDEFGH#

0.1

0,2

0.5

1,3

1,4

2.5

2,6

3.7

4,7

-1,-1

運(yùn)行結(jié)果:

2、閱讀并運(yùn)行下面程序，補(bǔ)充拓?fù)渑判蛩惴ā?/p>

#incIude<>

#incIude<>

#defineN20

typedefstructedgenode{/*圖的鄰接表：鄰接鏈表結(jié)點(diǎn)*/

intadjvex;/*頂點(diǎn)序號(hào)*/

structedgenode*next;/*下一個(gè)結(jié)點(diǎn)的指針*/

}edgenode;

typedefstructvnode{/*圖的鄰接表:鄰接表*/

chardata;/*頂點(diǎn)信息*/

intind;/*頂點(diǎn)入度*/

structedgenode*1ink;/*指向鄰接鏈表指針*/

}vnode;

voidcreateGraph_list(vnodeadjIist[],int*p)；/*建立有向圖的鄰接表*/

voidtopSort(vnodeg[],intn)；/*拓?fù)渑判?/

voidcreateGraph_list(vnodeadjIist[],int*p){/*建立有向圖的鄰接表*/

inti,j,n,e;

charv;

edgenode*s;

i二0;n=0;e=0;

printf(”輸入頂點(diǎn)序列(以#結(jié)束)：\n");

whiIe((v=getchar())!='#')

adjIist[i].data=v;/*讀入頂點(diǎn)信息*/

adjlist[i].Iink=NULL;

adjIind=O;

i++；

)

n=i;

*P=n;

/*建立鄰接鏈表*/

printf("\n請(qǐng)輸入弧的信息(i=T結(jié)束):i,j：\n");

scanf(n%d,%d",&i,&j);

while(i!=-1){

s二(structedgenode*)maIIoc(sizeof(edgenode));

s->adjvex=j;

s->next=adjIist[i].link;

adjIist[i].Iink=s;

adjIist[j].ind++;/*頂點(diǎn)j的入度加1*/

e++;

scanf("%d,%d",&i,&j);

)

printf(“鄰接表：”)；

for(i=0;i<n;i++){/*輸出鄰接表*/

printf("\n%c,%d:",adjIist[i].data,adjIist[i].ind);

s=adjIist[i].link;

whiIe(s!二NULL){

printf("->%d",s->adjvex);

s=s->next;

)

)

)

voidtopSort(vnodeg[],intn){/*拓?fù)渑判?/

intmain(){

vnodeadjIist[N];

intn,*p;

p二&n;

createGraph_list(adjIist,p);

return0;

)

根據(jù)輸入，輸出有向圖的拓?fù)渑判蛐蛄?。并?huà)出有向圖。輸入:

ABCDEF#

0.1

1,2

2,3

4.1

4.5

運(yùn)行結(jié)果:

3、閱讀并運(yùn)行下面程序。

#include<>

#defineN20

#defineTRUE1

#defineINF32766/*鄰接矩陣中的無(wú)窮大元素*/

#defineINFIN32767/*比無(wú)窮大元素大的數(shù)*/

typedefstruct

{/*圖的鄰接矩陣*/

intvexnum,arcnum;

charvexs[N];

intarcs[N][N];

)

graph;

voidcreateGraph_w(graph*g,intfIag);

voidprim(graph*g,intu);

voiddijkstra(graphg,intv);

voidshowprim();

voidshowdij();

/*建帶權(quán)圖的鄰接矩陣,若flag為1則為無(wú)向圖，flag為0為有向圖*/

voidcreateGraph_w(graph*g,intfIag)

inti,j,w;

charv;

g->vexnum=0;

g->arcnum=0;

i=0;

printf("輸入頂點(diǎn)序列(以#結(jié)束)：\n");

while((v=getchar())!='#')

(

g->vexs[i]=v;/*讀入頂點(diǎn)信息*/

i++；

)

g->vexnum=i;

for(i=0;i<6;i++)/*鄰接矩陣初始化*/

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

g->arcs[i][j]=INF;

prin"("輸入邊的信息：\n");

scanf("%d,%d,%d",&i,&j,&w);/*讀入邊(i,j,w)*/

while(i!=-1)/*讀入i為一1時(shí)結(jié)束*/

(

g->arcs[i][j]=w;

if(flag=1)

g->arcs[j][i]=w;

scanf("%df%df%d",&i,&j,&w);

}

1

voidprim(graph*g,intu)/*出發(fā)頂點(diǎn)u*/

intIowcost[N],cIosest[N],i,j,k,min;

for(i=0;i<g->vexnum;i++)/*求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的權(quán)*/

(

Iowcost[i]=g->arcs[u][i];

closest[il=u;

)

Iowcost[u]=0;

for(i=1;i<g->vexnum;i++)/*循環(huán)求最小生成樹(shù)中的各條邊*/

{min=INFIN;

for(j=0;j<g->vexnum;j++)/*選擇得到一條代價(jià)最小的邊*/

if(Iowcost[j]!=0&&Iowcost[j]<min)

(

min=Iowcost[j];

k二j；

)

printf("(%c,%c)-%d\n",g->vexs[cIosest[k]],g->vexs[k],Iowcost[k]);

/*輸出該邊*/

lowcost[k]=0;/*頂點(diǎn)k納入最小生成樹(shù)*/

for(j=0;j<g->vexnum;j++)/*求其他頂點(diǎn)到頂點(diǎn)k的權(quán)*/

if(g->arcs[k][j]!=0&&g->arcs[k][j]<Iowcost[j])

(

Iowcost[j]=g->arcs[k][j];

cIosest[j]=k;

voidprintPath(graphg,intstartVex,intEndVex)

intstack[N],top=0;/*堆棧*/

inti,k,j;

intflag[N];/*輸出路徑頂點(diǎn)標(biāo)志*/

k二EndVex;

for(i=0;i<;i++)flag[i]=0;

j=startVex;

n

printf(%c"f[j]);

flag[j]=1;

stack[top++]=k;

while(top>0)/*找j到k的路徑*/

(

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

(

if(path[k][i]==1&&flag[i]==0)/*J到k的路徑含有i頂點(diǎn)*/

(