程序設(shè)計(jì)類課程實(shí)驗(yàn)報(bào)告

文檔編碼:CQ2Z1N8L1M3——HO5P5P7K10X4——ZM4Q6X9Z6V1國(guó)脈信息學(xué)院

（程序設(shè)計(jì)類課程）

試驗(yàn)報(bào)告課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)日姓名：張三系：運(yùn)算機(jī)科學(xué)與技術(shù)專業(yè)：李小林年級(jí)：學(xué)號(hào)：指導(dǎo)老師：職稱：副教授2022年11月試驗(yàn)項(xiàng)目列表序號(hào)試驗(yàn)項(xiàng)目名稱成果指導(dǎo)老師1第七章檢索及基本算法2

34

56

7 8

9

10

11

12

福建農(nóng)林高校運(yùn)算機(jī)與信息學(xué)院試驗(yàn)報(bào)告系：運(yùn)算機(jī)科學(xué)與技術(shù)專業(yè)：年級(jí)：成果：姓名：張三學(xué)號(hào)：試驗(yàn)室號(hào)____運(yùn)算機(jī)號(hào)93試驗(yàn)時(shí)間：2022.6.1指導(dǎo)老師簽字：試驗(yàn)七檢索一、試驗(yàn)?zāi)康暮鸵?/p>

1〕 把握檢索的不同方法,并能用高級(jí)語(yǔ)言實(shí)現(xiàn)檢索算法；2〕 嫻熟把握次序表和有序表的檢索方法,以及靜態(tài)檢索樹的構(gòu)造方法和檢索算法,懂得靜態(tài)檢索樹的折半檢索方法；3〕 嫻熟把握二叉排序樹的構(gòu)造和檢索方法；4〕 熟識(shí)各種儲(chǔ)備結(jié)構(gòu)的特點(diǎn)以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題；二、試驗(yàn)內(nèi)容和原理試驗(yàn)內(nèi)容：1〕編程實(shí)現(xiàn)在二叉檢索樹中刪除一個(gè)結(jié)點(diǎn)的算法；2〕編程實(shí)現(xiàn)Fibonacci 檢索算法；試驗(yàn)原理：1）構(gòu)造排序樹,每輸入一個(gè)數(shù)就進(jìn)行排序,選擇插入的結(jié)點(diǎn),刪除結(jié)點(diǎn),沒刪除一個(gè)節(jié)點(diǎn)就返回到構(gòu)造排序樹的方法；2）Fibonacci 數(shù)的定義為 f0=0,f1=1,fi=f〔i-1〕+f〔i-2〕〔i ≥2〕；由此得Fibonacci 數(shù)列為0,1,1,2,3,5,8,13,21,34,55,89,144,??設(shè)數(shù)組F中元素按關(guān)鍵字值從小到大次序排列,并假定元素個(gè)數(shù) n比某個(gè)Fibonacci 樹fi 小1,即n=fi-1；第一次用待查關(guān)鍵字 k與F[f（i-1）],Key比較,其算法描述 如下：①如k=F[f〔i-1〕],Key ,就檢索成功,F[f〔i-1〕] 為k所在記錄；②如k<F[f〔i-1〕],Key ,就下一次的檢索范疇為下標(biāo) 1到f〔i-1〕 ,序列長(zhǎng)度為f〔i-1〕 ；③如k>F[f〔i-1〕],Key ,就下一次的檢索范疇為下標(biāo) f〔i+1〕+1 到fi-1 ,序列長(zhǎng)度為（fi-1）-（f〔i-1〕+1）+1=fi-f〔i-1〕-1=f〔i-2〕-1設(shè)F是次序儲(chǔ)備的線性表且中意 F[1],key≤F[2],key≤?≤F[n]；key,k是已知的關(guān)鍵字值,在 F中檢索關(guān)鍵字值為 k的記錄；如找到返回其下標(biāo)值,否就返回0.三、試驗(yàn)環(huán)境WindowsXP系統(tǒng)visualc++6.0四、算法描述及試驗(yàn)步驟試驗(yàn)習(xí)題一：#include"stdio.h"

#include"malloc.h"

structBTnode

{

intdata;

structBTnode*lchild,*rchild;

}*root;

typedef

structBTnodeNode,*Nodep;voidcreatetree〔 intdata〕

{

Node*node,*p,*q;

node=〔Nodep〕malloc〔sizeof〔Node〕〕;

node->data=data;

node->lchild=0;

node->rchild=0;

if〔root==0〕

{

root=node;

return;

}

else

{

p=root;

while〔p.=0〕

{

if〔data<p->data〕

{

q=p;

p=p->lchild;

if〔p==0〕

q->lchild=node;

}

else

if〔data>p->data〕{q=p; p=p->rchild;

if〔p==0〕

q->rchild=node;

}

else}break;}}

voidshowtree〔structBTnode*proot,{

inti;

charb;

if〔proot.=0〕

{for〔i=1;i<=space-3;i++〕 printf〔 ""〕;

if〔space-3>=0〕printf〔 "---->" 〕;

if〔proot==root〕structBTnode*m,intspace〕 printf〔 "%d\n",proot->data〕;

else

{

if〔m->data>proot->data〕

b='L';

else

b='R';

printf〔 "%d〔%c〕",proot->data,b〕; printf〔 "\n"〕;

}

m=proot;

showtree〔proot->lchild,m,space+6〕; showtree〔proot->rchild,m,space+6〕; }

}

Nodepdeletep〔Node*p〕

{

Node*q,*t;

t=p;

if〔p->lchild.=0〕

{

p=p->lchild; q=p;

while〔p->rchild.=0〕

{

q=p;

p=p->rchild;

}

if〔p==q〕{p->rchild=t->rchild;free〔t〕;}return〔p〕; if〔p->lchild.=0〕

q->rchild=p->lchild;

else

q->rchild=0;

p->lchild=t->lchild;

p->rchild=t->rchild;

free〔t〕;

return〔p〕;

}

else

if〔p->rchild.=0〕

{

p=p->rchild;

q=p;

while〔p->lchild.=0〕

{

q=p;

p=p->lchild;

}

if〔p==q〕

{

p->lchild=t->lchild;

free〔t〕;

return〔p〕;

}

if〔p->rchild.=0〕

q->lchild=p->rchild;

else

q->lchild=0;

p->rchild=t->rchild;

p->lchild=t->lchild;

free〔t〕;}return〔p〕;else{free〔p〕; return〔0〕;

}

}

NodepdeleteBTnode〔intx〕

{

Node*p=root,*q;

while〔p.=0〕

{

q=p;

if〔p->data>x〕

if〔p->lchild〕

p=p->lchild;

else

break;

else

if〔p->data<x〕

if〔p->rchild〕

p=p->rchild;

else

break;

if〔p->data==x〕

break;

}

if〔〔p==root〕&&〔p->data==x〕〕

root=deletep〔p〕;

else

if〔〔p==q->lchild〕&&〔p->data==x〕〕

q->lchild=deletep〔p〕;

else

if〔〔p==q->rchild〕&&〔p->data==x〕〕

q->rchild=deletep〔p〕;

else

if〔p->data.=x〕

{printf〔 "cannotfoundthedatayouwanttodelete,pleasecheck it.\n" 〕;

return0;

}

returnroot;

}intmain〔〕

{charch;

intdata;printf〔"Enter'c'createtree,Enter'd'deleteanode:"〕;scanf〔"%c",&ch〕;getchar〔〕;

root=0;

while〔ch=='c'||ch=='d'〕

{if〔ch=='c'〕{printf〔"pleaseinputthekey:"〕; scanf〔"%d",&data〕;

getchar〔〕;

createtree〔data〕;

showtree〔root,0,0〕;

}

else{printf〔"pleaseinputthekeyofthenodeyouwantdel:"〕;scanf〔"%d",&data〕;

getchar〔〕;

if〔deleteBTnode〔data〕〕}showtree〔root,0,0〕;〕;printf〔"Enter'c'createtree,Enter'd'deleteanode:" scanf〔"%c",&ch〕;

}

return0;

}試驗(yàn)習(xí)題二：#include "stdio.h"

typedef intkeytype;

typedef intdatatype;

typedef structnode

{

intkey;

}rectype;

intfibonacci〔 intn〕

{

if〔n==0〕return0;

else

if〔n==1〕return1;

else

returnfibonacci〔n-1〕+fibonacci〔n-2〕;}voidprintData〔rectypeR[], intn〕{inti;for〔i=1;i<=n;i++〕{intn〕printf〔"%5d",R[i].key〕;if〔i%8==0〕printf〔"\n"〕;}printf〔"\n"〕;}

intfibsearch〔rectypeR[],keytypeK,{

intm,i,p,q,t;

for〔m=0;fibonacci〔m〕<=〔n+1〕;m++〕{}

m--;

i=fibonacci〔m-1〕;

p=fibonacci〔m-2〕;

q=fibonacci〔m-3〕;

while〔i>=0&&i<=n〕{if〔K==R[i].key〕{elsereturni;}

if〔K<R[i].key〕{

i=i-q;

t=p;

p=q;

q=t-q;}else{if〔K>R[i].key〕 i=i+q;

p=p-q;

q=q-p;

}

}

return0;

}

voidmain〔〕{intm,i,k,n;rectypeR[20];printf〔"Enterknum:"〕;scanf〔"%d",&k〕;〕;printf〔"enterR[20]:"for〔i=1;i<=20;i++〕{scanf〔"%d",&R[i].key〕; }

printData〔R,20〕;

m=fibsearch〔R,k,20〕;

if〔m==0〕

{}printf〔"Notfound.\n"〕;elseprintf〔"TheKeyhasbeenfoundatR[%d]\n",m〕;getchar〔〕;}五、調(diào)試過(guò)程1〕構(gòu)建二叉排序