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

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

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

姓名：學(xué)號(hào)：班級(jí)：

指導(dǎo)教師：______________

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

2022

預(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ǔ)言中的概念I(lǐng)、函數(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

intiprime（intn）{/某判斷一個(gè)數(shù)是否為素?cái)?shù)某/intm;for（m=2;m某

m<=n;m++)

if(n%m==O)returnO;returnl;

)

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

inti;printf(\for(i=2;i<100;i++)

if(iprime(i)==1)printf(\returnO;

}

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

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

#include#defineNlOintmain(){

2

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

printf(\for(i=0;i

temp=a[i];a[i]=a[N-i-l];a[N-i-l]=temp;

printf(\for(i=0;i

returnO;}

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

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

而在該列中最小，則該元素即為該二維數(shù)組的一個(gè)鞍點(diǎn)。要求從鍵盤上輸

入一個(gè)二維數(shù)組，當(dāng)鞍點(diǎn)存在時(shí)，把鞍點(diǎn)找出來(lái)。ftinclude

#defineM3#defineN4intmain(){inta[M][N],i,j,k;printf(\請(qǐng)輸入

二維數(shù)組的數(shù)據(jù)：\\n\

for(i=0;i

for(j=0;j

for(j=0;j

for(i=0;i

/某找出第i行的最大值某/

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

for(j=0;j

if(a[j][k]

/某在第i行找到鞍點(diǎn)某/

break;if(j==M)

printf(\

3

)

returnO;}

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

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

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

；int某p;

for(p=a[O];p

printf(\

returnO;}

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

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

年齡、職業(yè)、教研室四項(xiàng)，學(xué)生有姓名、年齡、專業(yè)、班級(jí)四項(xiàng)，編程輸

入人員的數(shù)據(jù)，再以表格輸出。ttinclude

#defineNlOtructtudent{charname[8];/某姓名某/intage;/某年齡某

/cha門ob;/某職業(yè)或?qū)I(yè)，用或t表示學(xué)生或教師某/

union{

intcla;

/某班級(jí)某/

charoffice[10];/某教研室某/}depa;

}tu[N];intmain(){

inti;intn;

printf(u\\n請(qǐng)輸入人員數(shù)

(<10):\\n");canf("%d",&n);for(i=0;i

canf(\if(tu[i].job==,')canf(\

4

ele

canf(\}printf("nameagejobcla/office");for(i=0;i

ifjob==,')

printf(\

eleprintf(\

}

}

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

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

5

intmain(){

SqStack;

printf(\CreateStack(&);

printf(\PrintStack(&);returnO;

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

棧的什么

特性？

2、在第1題的程序中，編寫一個(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#include#include#defineM20

#defineelemtypechartypedeftruct{

elemtypetack[M];inttop;}

tacknode;

voidinit(tacknode某t);

voidpuh(tacknode某t,elemtype某);voidpop(tacknode某t);

16

voidinit(tacknode某

t){t->top=0;}

voidpuh(tacknode某t,elemtype

某){if(t->top==M)

printf(\ele{

t->top=t->top+l;;}}

voidpop(tacknode某t){

if(t->top>0)t->top一;

eleprintf("StackiEmpty!\\n");}

intmain(){

char[M];inti;

tacknode某p;

printf(\p=malloc(izeof(tacknode));init(p);

printf(\get();

for(i=0;i

if([i]=='(')

puh(p,[i]);if([i]==')’)pop(p);}

if(p->top==0)

printf(\ele

printf(\returnO;}

輸入：2+((c-d)某6-(f-7)某a)/6運(yùn)行結(jié)果:

輸入：a-((c-d)某6-(/3-某)/2運(yùn)行結(jié)果：程序的基本功能：

17

以下為選做實(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ì)頭指針)，試編寫相應(yīng)的置空隊(duì)列、入隊(duì)列、出隊(duì)列的算

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

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

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

18

實(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ù)輸入寫出運(yùn)行結(jié)果。

#include#include#defineMA某SIZElOOtypedeftruct{

chardata[MA某SIZE];intlength;}SqString;

voidtrSub(SqString某,inttart,intublen,SqString某ub);/某求

子串某/

voidhowubString();

printf(\

19

for(i=0;ilength&&ilength;i++)if(l->data[i]!=2->data[i])

returnl->data[i]-2->data[i];returnl->length-2->length;

printf(\get(1.data);

1.length=trlen(1.data)jprintf(\get(2.data);

2.length=trlen(2.data);

printf(\ele

printf(\

printf(\)

voidtrSub(SqString某,inttart,intublen,SqString某

ub){inti;

if(tart<l1|tart>->length||ublen>->length-tart+l){ub-

>length=0;}

for(i=0;i

ub->data[i]=~>data[tart+i-l];ub->length=ublen;}

voidhow_ubString(){SqString,ub;inttart,ublen,i;

printf(\printf(\get(.data);

.length=trlen(.data);printf(\canf(\

printf(\canf(\

trSub(&,tart,ublen,&ub);if(ub.length==0)printf(\ele{printf(\f

or(i=0;i

printf(\}

printf(\

20

)

intmain(){intn;do{printf(\printf(\printf(\printf(\printf(\can

f(\getchar();witch(n){

}while(n);returnO;}

運(yùn)行程序

輸入：1

tudenttudent

2

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

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

#include#include#defineMA某SIZElOOtypedeftruct{

chardata[MA某SIZE];intlength;

}SqString;

intinde某_bf(SqString某,SqString某t,inttart);

21

voidgetNe某t(SqString某t,intne某t[]);

intinde某_kmp(SqString某,SqString某t,inttart,intne某

t[]);voidhow_inde某()；

intinde某_bf(SqString某,SqString某

t,inttart){補(bǔ)充代碼}

voidgetNe某t(SqString某t,intne某t[]){inti=0,j=T;ne某

t[0]=T;

while(ilength){

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

>data[j])){i++;j++;ne某t[i]=j;}ele

j=ne某t[j];}}

intindeM_kmp(SqString某,SqString某t,inttart,intne某

t口){補(bǔ)充代碼)

voidhow_inde某(){SqString,t;

intk,ne某t[MA某SIZE]={0},i;

printf(\printf(\

22

get(.data);

.length=trlen(.data);printf(\get(t.data);

t.length=trlen(t.data);

printf(\canf(\

printf(\getNe某t(&t,ne某t);printf(\printf(\for(i=0;i

printf(\printf(\)

intmain(){

howinde某();returnO;

}

輸入：

abcaabbabcabaacbacbaabcabaal

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

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

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

23

實(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ù)輸入寫出運(yùn)行結(jié)果，并畫(huà)出二叉樹(shù)的

形態(tài)。#include#include#defineMA某20

typedeftructBTNode{/某節(jié)點(diǎn)結(jié)構(gòu)聲明某/chardata;/某節(jié)點(diǎn)數(shù)據(jù)某/

tructBTNode某Ichild;

tructBTNode某rchild;/某指針某/

}某BiTree;

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

BiTreeq;

printf(\=getche();

if(=='#'){某t=NULL;return;}

q=(BiTree)malloc(izeof(tructBTNode));

if(q==NULL){printf(\q->data=;

某t=q;

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

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

24

}

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

/if(p!=NULL){printf(\PreOrder(p->lchild);PreOrder(p-

>rchild);}}voidlnOrder(BiTreep){/某中序遍歷二叉樹(shù)某

/if(p!=NULL){InOrder(p->lchild);printf(\InOrder(p-

>rchild);}}voidPotOrder(BiTreep){/某后序遍歷二叉樹(shù)某

/if(p!=NULL){PotOrder(p->lchild);PotOrder(p-

>rchild);printf(\

}}

voidPreordern(BiTreep){/某先序遍歷的非遞歸算法某

/BiTreetack[MA某],q;inttop=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchi1d!=NULL)tack[top++]=q->rchiId;if(q-

>lchild!=NULL)q=q->lchild;ele

if(top>0)q=tack[-top];eleq=NULL;}}

voidreleae(BiTreet){/某釋放二叉樹(shù)空間某

/if(t!=NULL){releae(t->lchild);releae(t-

>rchild);free(t);

25

for(i=0;i

intmain(){

graphga;

inti,j;

createGraph(&ga);

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

for(i=0;i

for(j=0;j

printf(\printf(\)

init_viit();tdf(&ga);init_viit();tbf(&ga)jreturnO;

}

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

ABCDEFGH#O,10,20,51,31,42,52,63,74,7-1,-1

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

#include#include#defineN20

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

10B4E7HAC2F5G6

3D31

typedeftructedgenode{/某圖的鄰接表：鄰接鏈表結(jié)點(diǎn)某/intadjve

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

tructedgenode某ne某t;/某下一個(gè)結(jié)點(diǎn)的指針某/}edgenode;

typedeftructvnode{/某圖的鄰接表：鄰接表某/chardata;/某頂點(diǎn)信

息某/

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

tructedgenode某link;/某指向鄰接鏈表指針某/}vnode;

voidcreateGraphlit(vnodeadjlit[],int某p)；/某建立有向圖的

鄰接表某/voidtopSort(vnodeg口，intn)；/某拓?fù)渑判蚰?

voidcreateGraph1it(vnodeadj1it[],int某p){/某建立有向圖的鄰

接表某/inti,j,n,e;charv;

edgenode某;i=0;n=0;e=0;

printf(、輸入頂點(diǎn)序列(以#結(jié)束)：\\n\while((v=getchar())!='#')

(

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

/adjlit[i].link=NULL;adjlit[i].ind=0;i++;}

n=i;某p=n;

/某建立鄰接鏈表某/

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

while(i!=-1){

=(tructedgenodeM)malloc(izeof(edgenode));->adjve塞j;

->ne某t=adjlit[i].link;adjlit[i].link=;

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

canf(\}

printf(、鄰接表：\

for(i=0;i

printf(\

32

=adjlit[i].link;

while(!=NULL){printf

(\=->ne某t;}}}

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

intmain(){

vnodeadjlit[N];intn,某p;p=&n;

createGraph_lit(adjlit,p);returnO;

)

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

入:ABCDEF#0,11,22,34,14,5-1,-1

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

33

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

#include#defineN20#defineTRUEl

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

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

typedeftruct{/某圖的鄰接矩陣某/intve某num,arcnum;charve某

[N];intarc[N][N];}

graph;

voidcreateGraphw(graph某g,intflag);voidprim(graph某

g,intu);voiddijktra(gr^iig,intv);voidbovprimOjvoichjdijO;

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

S^/voidcreateGraphw(graph某g,intflag){

inti,j,w;charv;

g->ve某num=0;

g->arcnum=0;i=0;

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

\\n\while((v=getchar())!='#'){

g->ve某[i]=v;/某讀入頂點(diǎn)信息某/i++;}

g->ve某num=i;

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

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

printf('輸入邊的信息：\\n\

canf(、讀入邊(i,j,w)某/while(i!=-1)/某讀入i為一1時(shí)結(jié)束某

/{g->arc[i][j]=w;

34

if(flag==l)

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

canf(\}}

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

/{intlowcot[N],cloet[N],i,j,k,min;

for(i=0;ive某num;i++)/某求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的權(quán)某

/{lowcot[i]=g->arc[u][i];cloet[i]=u;}

lowcot[u]=0;

for(i=l;ive某num;i++)/某循環(huán)求最小生成樹(shù)中的各條邊某

/{min=INFIN;

for(j=0;jve某num;j++)/某選擇得到一條代價(jià)最小的邊某

/if(lowcot[j]!=0&&lowcot[j]

min=lowcot[j];

k=j;}

printf(\/某輸出該邊某/

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

for(j=0;jve某num;j++)/某求其他頂點(diǎn)到頂點(diǎn)k的權(quán)某/if(g-

>arc[k][j]!=0&&g->arc[k][j]

lowcot[j]=g->arc[k][j];cloet[j]=k;}}}

voidprintPath(graphg,inttartVe某,intEndVe

某){inttack[N],top=0;/某堆棧某/inti,k,j;

intflag[N];/某輸出路徑頂點(diǎn)標(biāo)志某/k=EndVe某；

for(i=0;i

35

printf(\

flag[j]=l;

tack[top++]=k;

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

/{for(i=0;i

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

/{]￡1@%口]"]!=1小)/某上到i的路徑含有中間頂點(diǎn)某

/{printf(\/某輸出j到k的路徑的頂點(diǎn)i某;j=i;

k=tack[-top];break;}ele

if(i!=k)tack[top++]=i;/某break;某/}}}}

voiddijktra(graphg,intv){/某dijktra算法求單源最短路徑某

/intpath[N][N],dit[N],[N];intmindi,i,j,u,k;

for(i=0;i

for(j=0;j

dit[v]=0;[v]=l;

for(i=0,u=l;i

for(j=0;j

36

if([j]==0)

if(dit[j]

mindi=dit[j];}

[u]=l;

for(j=0;j

if(([j]==0)&&dit[u]+g.arc[u][j]

printf('頂點(diǎn)%c-＞到各頂點(diǎn)的最短路徑\\n\for(i=0;i

printf(、頂點(diǎn)%c-＞頂點(diǎn)％c：\if(dit[i]==INF||dit[i]==0)printf(\

無(wú)路徑\

ele{

printf(\

printf(、經(jīng)過(guò)頂點(diǎn)：\

printPath(g,v,i);/某輸出v到i的路徑某/}}}

voidhowprim。/某最小生成樹(shù)prim算法演示某

/{graphga;

createGraph_w(&ga,1);prim(&ga,0);}

voidhowdij(){/某dijtra算法演示某/graphga;

createGraphw(&ga,0);dijktra(ga,0);}

intmain(){

howprimO;/某prim算法演示某/getchar();

howdij();/某dijtra算法演示某/

37

returnO;

}

下面的輸入分別驗(yàn)證prim算法和dijtra算法。輸入實(shí)例的第一部分

為無(wú)向圖，求

其最小生成樹(shù)；輸入的第二部分為有向圖，求其最短路徑。最小生成

樹(shù)最短路徑

ABCDEFftO,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-

運(yùn)行結(jié)果：（并畫(huà)出兩個(gè)圖）

最小生成樹(shù)

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

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

ABCDEF#O,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-

最短路徑

38

實(shí)驗(yàn)六查找

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

1、掌握查找表、動(dòng)態(tài)查找表、靜態(tài)查找表和平均查找長(zhǎng)度的概念。2、

掌握線性表中順序查找和折半查找的方法。

3、學(xué)會(huì)哈希函數(shù)的構(gòu)造方法，處理沖突的機(jī)制以及哈希表的查找。

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

說(shuō)明以下概念1、順序查找：

2、折半查找：

3、哈希函數(shù)：

4、沖突及處理：

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

1.靜態(tài)查找表技術(shù)

依據(jù)順序查找算法和折半查找算法的特點(diǎn)，對(duì)下面的兩個(gè)查找表選擇

一個(gè)合適的算法，設(shè)計(jì)出完整的c源程序。并完成問(wèn)題：

查找表1：{8,15,19,26,33,41,47,52,64,90},查找

key=41查找表2：{12,76,29,15,62,35,33,89,48,20),查找

key=35查找key=41的算法：比較次數(shù)：查找key=35的算法：比較次數(shù):

順序查找算法算法實(shí)現(xiàn)代碼

39

折半查找算法算法實(shí)現(xiàn)代碼

2、哈希表的構(gòu)造與查找

/某采用開(kāi)放地址法構(gòu)造哈希表某/#include#incIude#defineMA某

SIZE25#defineP13

#define0Kl#defineERR0R0

#defineDUPLICATE-1#defineTRUEI

ttdefineFALSEO

typedeftruct{/某哈希表元素結(jié)構(gòu)某/intkey;/某關(guān)鍵字值某/

intflag;/某是否存放元素某/}ElemType;

typedeftruct{ElemTypeda

ta[MA某SIZE];

intcount;/某元素個(gè)數(shù)某/intizeinde某;/某當(dāng)前哈希表容量某

/}HahTable;

intdl[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};/某線性探測(cè)序

列某/

intd2[15]={0,1,-1,2某2,-2某2,3某3,-3某3,4某4,-4某4,5

某5,-5某5,6某6,-6某6,7某7,-7某7};/某二次探測(cè)序列某/

voiddataet(intd[],int某len);

intlnertHah(HahTable某H,inte,intd[]);

intCreateHah(HahTableintd[],intlm,intd[])jintSeaidifahGblirable

某H,inte,intd[]);

40

voidmenu();

/某輸入查找表某/

voiddataet(intd[],int某len){intn,m;n=0;

printf(、查找表輸入：\

while(canf(、以輸入一個(gè)非整數(shù)作為結(jié)束某/d[n]=m;n++;}某len=n;}

/某計(jì)算哈希地址，插入哈希表某/

intlnertHah(HahTable某H,inte,intd[]){intk,i=l;k=e%P;

while(H->data[k].flag==TRUE||k<0){k=(e%P+d[i])%MA某

SIZE;i++;if(i>=15)

returnERROR;}

H->data[k].key=e;

H->data[k].flag=TRUE;H->count++;returnOK;}

/某構(gòu)造哈希表某/

intCreateHah(HahTable某H,intd[],intlen,intd[]){inti;

for(i=0;i

if(SearchHah(H,d[i],d)!=-

1)returnDUPLICATE;InertHah(H,d[i],d);if(H->count>=MA某

SIZE)returnERROR;}

returnOK;}

/某初始化哈希表某/

voidlnitHah(HahTable某H){inti;

for(i=0;idata[i].key=0;

H->data[i].flag=FALSE;

41

)

)

/某在哈希表中查找某/

intSearchHah(HahTable某H,inte,intd[]){intk,i=l;

k=e%P;

while(H->data[k].key!=e){k=(e%P+d[i])%MA某

SIZE;i++;if(i>=15)return-1;}

returnk;}

/某演示菜單某/

voidmenu(){intcho

ice;int某p;

HahTableh;

h.count=0;h.izeinde某=MA某SIZE;inta[MA某SIZE]={0};

inti,n,e;

dataet(a,&n);/某建立查找表某/

getchar();printf(\do{

printf(、哈希查找演示--\\n\printf(、線性探測(cè)構(gòu)造哈希表

\\n\printf('二分探測(cè)構(gòu)造哈希表\\n\printf(\退出\\n\printf(\輸入選

擇：\canf(\if(choice==l)p=dl;

eleif(choice==2)p=d2;ele

return;

InitHah(&h);/某初始化哈希表某/

if(!(i=CreateHah(&h,a,n,p)))/某構(gòu)造哈希表某/printf(、哈希表構(gòu)

造失?。\n\eleif(i==DUPLICATE)

printf('哈希表具有重復(fù)關(guān)鍵字！

\\n\ele{printf(、哈希表：\\n\for(i=0;i

42

printf(\

printf(、哈希查找\\n輸入要查找的key值：\getchar();

canf(\

if((i=SearchHah(&h,e,p))=-1)printf(、未找到\\n\ele

printf(\在哈希表中下標(biāo)為%d\\n\}

getchar();}while(1);}

intmain(){menu();returnO;

}

輸入查找表為：19142316820842755111079(注意以輸入一個(gè)非整數(shù)

結(jié)束)。運(yùn)行結(jié)果：1)線性探測(cè)散列：哈希表形態(tài)：

84在哈希表中的位置:2)二次探測(cè)散列：哈希表形態(tài)：

84在哈希表中的位置：

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

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

43

實(shí)驗(yàn)七排序

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

1、掌握內(nèi)部排序的基本算法；

2、分析比較內(nèi)部排序算法的效率。

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

說(shuō)明以下概念1、簡(jiǎn)單排序：

2、希爾排序：

3、快速排序：

4、堆排序：

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

1運(yùn)行下面程序：#include#include#defineMA某50

intlitEMA某];/某待排序序列某/

voidinertSort(intlit[],intn);voidcreateLit(intlit[],int某

n);voidprintLit(intlit[],intn);

voidheapAdjut(intlit[],intu,intv);voidheapSort(intlit[],intn

)；

/某直接插入排序某/

voidinertSort(intlit[],intn){

inti=l,j=0,node=0,count=l;printf('對(duì)序列進(jìn)行直接插入排序：

\\n\printf(\初始序列為:

\printLit(lit,n);for(i=2;i<=n;i++){node=lit[i];j=i-l;

while(j>=0&&node<lit[j])

44

lit[j+l]=lit[j]j;}

lit[j+l]=node;

printf(\第％d次排序結(jié)果：\printLit(lit,n);

/某堆排序某/

voidheapAdjut(intlit[],intu,intv){inti=u,

j,temp=lit[i];j=2某i;while(j<=v){}

if(j〈v&&lit[jklit[j+l])j++;/某若右孩子較大,則把j修改為右

孩子的下標(biāo)某/if