![《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)_第1頁(yè)](http://file4.renrendoc.com/view14/M03/10/15/wKhkGWZnr0SADFTqAAE4rts9M04704.jpg)
![《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)_第2頁(yè)](http://file4.renrendoc.com/view14/M03/10/15/wKhkGWZnr0SADFTqAAE4rts9M047042.jpg)
![《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)_第3頁(yè)](http://file4.renrendoc.com/view14/M03/10/15/wKhkGWZnr0SADFTqAAE4rts9M047043.jpg)
![《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)_第4頁(yè)](http://file4.renrendoc.com/view14/M03/10/15/wKhkGWZnr0SADFTqAAE4rts9M047044.jpg)
![《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏著-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)_第5頁(yè)](http://file4.renrendoc.com/view14/M03/10/15/wKhkGWZnr0SADFTqAAE4rts9M047045.jpg)
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
《數(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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度國(guó)際快遞運(yùn)輸與時(shí)效跟蹤服務(wù)合同
- 2025年度屋頂租賃合同附屋頂廣告權(quán)益共享協(xié)議
- 2025年度時(shí)尚女鞋品牌全國(guó)代理權(quán)購(gòu)買合同樣本
- 培養(yǎng)學(xué)生團(tuán)隊(duì)合作能力的美術(shù)教學(xué)計(jì)劃
- 激活團(tuán)隊(duì)潛力的成功經(jīng)驗(yàn)計(jì)劃
- 學(xué)校年度班級(jí)工作計(jì)劃表目
- 區(qū)域倉(cāng)庫(kù)布局的設(shè)計(jì)原則計(jì)劃
- 2025年港物運(yùn)輸項(xiàng)目合作計(jì)劃書(shū)
- 主管的職業(yè)素養(yǎng)與榜樣作用計(jì)劃
- 2025年激光轉(zhuǎn)速測(cè)量?jī)x項(xiàng)目建議書(shū)
- 2024-2025學(xué)年第二學(xué)期教學(xué)教研工作安排表 第二版
- 七年級(jí)地理下冊(cè) 9.2 巴西說(shuō)課稿 (新版)新人教版
- 二零二五年度電梯安裝工程監(jiān)理合同4篇
- 2025年中國(guó)儲(chǔ)備棉管理有限公司招聘筆試參考題庫(kù)含答案解析
- 2025年華能新能源股份有限公司招聘筆試參考題庫(kù)含答案解析
- 開(kāi)展課外讀物負(fù)面清單管理的具體實(shí)施舉措方案
- 初中教學(xué)常規(guī)培訓(xùn)
- 2025中國(guó)煙草/中煙工業(yè)招聘高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2024-2030年中國(guó)兒童室內(nèi)游樂(lè)園產(chǎn)業(yè)競(jìng)爭(zhēng)格局展望及投資策略分析報(bào)告
- 《建筑平面圖的繪制》課件
- 2025造價(jià)咨詢工作計(jì)劃范本
評(píng)論
0/150
提交評(píng)論