1、國脈信息學(xué)院（程序設(shè)計(jì)類課程） 實(shí)驗(yàn)報(bào)告課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)姓名：系：張三計(jì)算機(jī)科學(xué)與技術(shù)專 業(yè):年 級:學(xué) 號:指導(dǎo)教師：李小林職稱：副教授2012年11 月日實(shí)驗(yàn)項(xiàng)目列表序號實(shí)驗(yàn)項(xiàng)目名稱成績指導(dǎo)教師1第七章檢索及基本算法23456789101112福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院實(shí)驗(yàn)報(bào)告系：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)：年級：姓名：_三學(xué)號：實(shí)驗(yàn)室號計(jì)算機(jī)號93實(shí)驗(yàn)時(shí)間：201261指導(dǎo)教師簽字： 成績：實(shí)驗(yàn)七檢索一、實(shí)驗(yàn)?zāi)康暮鸵?) 掌握檢索的不同方法，并能用高級語言實(shí)現(xiàn)檢索算法。2) 熟練掌握順序表和有序表的檢索方法，以及靜態(tài)檢索樹的構(gòu)造方法 和檢索算法，理解靜態(tài)檢索樹的折半檢索方法。3)

2、熟練掌握二叉排序樹的構(gòu)造和檢索方法。4) 熟悉各種存儲結(jié)構(gòu)的特征以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。二、實(shí)驗(yàn)內(nèi)容和原理實(shí)驗(yàn)內(nèi)容：1) 編程實(shí)現(xiàn)在二叉檢索樹中刪除一個(gè)結(jié)點(diǎn)的算法。2) 編程實(shí)現(xiàn)Fibonacci檢索算法。實(shí)驗(yàn)原理：1)構(gòu)造排序樹，每輸入一個(gè)數(shù)就進(jìn)行排序，選擇插入的結(jié)點(diǎn)，刪除結(jié)點(diǎn), 沒刪除一個(gè)節(jié)點(diǎn)就返回到構(gòu)造排序樹的方法。2) Fibonacci 數(shù)的定義為 fO=O,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)鍵字值從小到大順

3、序排列，并假定元素個(gè)數(shù)n比某個(gè)Fibonacci樹fi小1,即n=fi-1。第一次用待查關(guān)鍵字k與Ff (i-1 ), 若 k=Ff(i-1),Key 若 k<Ff(i-1),Key 長度為f(i-1)。 若 k>Ff(i-1),KeyKey比較，其算法描述如下:，貝葉僉索成功，F(xiàn)f(i-1) 為k所在記錄。，則下一次的檢索范圍為下標(biāo)1到f(i-1)，序列，則下一次的檢索范圍為下標(biāo)f(i+1)+1到fi-1 :序列長度為(fi-1 ) - (f(i-1)+1)+1= fi-f(i-1)- 1=f(i-2)-1設(shè)F是順序存儲的線性表且滿足F1 , key<F2 , key<

4、;-< Fnkey,k是已知的關(guān)鍵字值，在F中檢索關(guān)鍵字值為k的記錄。若找到返回 其下標(biāo)值，否則返回0.三、實(shí)驗(yàn)環(huán)境Win dows XP 系統(tǒng)visual C+6.0四、算法描述及實(shí)驗(yàn)步驟實(shí)驗(yàn)習(xí)題一：#include "stdio.h"#include "malloc.h"struct BTnodeint data;struct BT node *lchild,*rchild;*root;typedef struct BTnode Node,*Nodep;void createtree( int data)Node *no de,*p,*q;no

5、de=(Nodep)malloc( sizeof (Node);no de->data=data;no de->lchild=0;no de->rchild=0;if (root=0)root=no de;return ;elsep=root;while (p!=0)if (data<p->data)q=p;p=p->lchild;if (p=0)q->lchild=node;elseif (data>p->data)q=p； p=p->rchild;if (p=0) q->rchild=no de;elsebreak;void

6、 showtree( struct BTnode *proot, struct BTnode *m, int space) int i;char b;if (proot!=0)for (i=1;i<=space-3;i+)printf("");if (space-3>=0)printf( "->");if (proot=root)printf( "%dn" ,proot->data);elseif (m->data>proot->data)b='L'elseb='R&#

7、39;printf( "%d (%c)" ,proot->data,b);printf( "n");m=proot;showtree(proot->lchild,m,space+6);showtree(proot->rchild,m,space+6);Nodep deletep(Node *p)Node *q,*t;t=p;if (p->lchild!=O)p=p->lchild;q=p； while (p->rchild!=O) q=p； p=p->rchild;if (p=q) p->rchild=t-

8、>rchild; free(t); return (p);if (p->lchild!=O) q->rchild=p->lchild; elseq->rchild=O;p->lchild=t->lchild; p->rchild=t->rchild; free(t); return (p);elseif (p->rchild!=O)p=p->rchild;q=p;while (p->lchild!=O) q=p;p=p->lchild;if (p=q) p->lchild=t->lchild; free(

9、t);return (p);if (p->rchild!=O) q->lchild=p->rchild; elseq->lchild=O;p->rchild=t->rchild;p->lchild=t->lchild;free(t);return (p);elsefree(p);return (0);Nodep deleteBTnode( int x)Node *p=root,*q;while (p!=0)q=p;if (p->data>x)if (p->lchild)p=p->lchild;elsebreak;elsei

10、f (p->data<x)if (p->rchild)p=p->rchild;elsebreak;if (p->data=x)break;if (p=root)&&(p->data=x)root=deletep(p);elseif (p=q->lchild)&&(p->data=x)q->lchild=deletep(p);elseif (p=q->rchild)&&(p->data=x)q->rchild=deletep(p);elseif (p->data!=x)p

11、ri ntf("ca n not found the data you want to delete,pleasecheck it!n");return 0;return root;int main()char ch;int data;printf( "En ter 'c' create tree,E nter 'd' delete a no de:");scanf( "%c",&ch);getchar();root=0;while (ch= 'c' |ch= 'd

12、9;)if (ch='c')pri ntf("please in put the key:" );scanf( "%d",&data);getchar();createtree(data); showtree(root,0,0);elsepri ntf("please in put the key of the node you want del:");scanf( "%d",&data);getchar();if (deleteBTnode(data)showtree(root,0

13、,0);printf( "En ter 'c' create tree,E nter 'd' delete a no de:");scanf( "%c",&ch);return 0;實(shí)驗(yàn)習(xí)題二：#i nclude "stdio.h"typedef int keytype;typedef int datatype;typedef struct nodeint key;rectype;int fibonacci(int n)if (n=0) return 0;elseif (n=1) return

14、1;elsereturn fibonacci(n-1)+fibonacci(n-2); void printData(rectype R, int n)int i;for (i=1; i<=n; i+)printf( "%5d",Ri.key);if (i%8=0) printf("n" ); printf( "n");int fibsearch(rectype R,keytype K, int n)int m,i,p,q,t;for (m=0;fibonacci(m)<=(n+1);m+) m-;i = fibon ac

15、ci(m-1);p = fibon acci(m-2);q = fibon acci(m-3);while (i>=0 && i<=n)if (K = Ri.key)return i; else if (K < Ri.key)i = i-q;t = p;p = q;q = t-q; else if (K > Ri.key) i=i+q; p=p-q; q=q-p;return 0;void mai n()int m,i,k,n;rectype R20;printf( "En ter k nu m:");scanf("%d&q

16、uot;,&k);printf("en ter R20:");for (i=1;i<=20;i+)scanf( "%d",&Ri.key);prin tData(R,20);m=fibsearch(R,k,20);if (m = 0)printf( "Not fou nd!n");elseprintf( "The Key has bee n found at R%dn",m);getchar();五、調(diào)試過程1)構(gòu)建二叉排序樹：刪除二叉樹的節(jié)點(diǎn)：已直動生咸-頃目：數(shù)搦結(jié)構(gòu)試驗(yàn)配畫.De lug

17、 liriSZ匕成啟動時(shí)間対2011/8l&：22：34cIni 11 Oi z.eBuildSt 自t口s :正在創(chuàng)律 b4£ ®el-ag數(shù)據(jù)結(jié)構(gòu)|克鯊一 un£ w" s; wfullmii 1 d ",因?yàn)橐艳蠥lwayECTeaiLeoICornjile；靱據(jù)詰掏試驗(yàn).CPP皿紐MVhpl仏瞅麻期s結(jié)構(gòu)試聆城據(jù)結(jié)構(gòu)試驗(yàn)邇據(jù)結(jié)構(gòu)試騎.叱代C20C39 "鹼汕：不昱f 皿"的爾員 c：結(jié)枸試噓I勤掘結(jié)枸試噓I數(shù)捐結(jié)枸試髓.占“陌：參見H 的聲他:皿叱如仏kt環(huán)頻辭構(gòu)數(shù)堆結(jié)構(gòu)i溜數(shù)堀結(jié)構(gòu)i謹(jǐn)® 住廠：e

18、rror C2K39: -key11 :不曇f 皿"的成員 二狂址to訕救拐結(jié)枸試驗(yàn)燉協(xié)結(jié)枸試驗(yàn)燉瞬枸試騷一 TPCS)：參見的聲明_;也曲11班仏15伽1數(shù)據(jù)結(jié)構(gòu)1沆驗(yàn)1數(shù)據(jù)結(jié)構(gòu)I丑驗(yàn)燼I據(jù)結(jié)構(gòu)加：error C2Q39: "key"不是的感員 =；usershpdeskt&p數(shù)損結(jié)枸試盛5數(shù)捐括枸試誡'數(shù)1S結(jié)枸試驗(yàn)山丹；善見*4寸'的聲朋八11 wNhp也Ekt °F、數(shù)據(jù)結(jié)構(gòu)試怒數(shù)據(jù)唐堿罐燼塘結(jié)暢i罐Cfp(36)- *rror 02030: kay"不是、皿砂的咸員 c Aus*rshpUftiktopSffi®W試胚燼捐括枸試唸'數(shù)揭站枸試驗(yàn)"PP：參見"朕”的聲明:皿叱血也皿低曦?fù)?jù)結(jié)構(gòu)試血哦據(jù)結(jié)稱亦I數(shù)垢結(jié)爾試驗(yàn)注：wrwr C2tX3g：叫甲不是皿利的粛員 c! user3hpdesktoptiti£tlE結(jié)箱i式婭I教吉慚式猛” cpp國：參閃0捷"的靑明，用時(shí)間 00:00