1、國脈信息學院（程序設計類課程）實驗報告課程名稱：算法與數據結構姓名：張三系：計算機科學與技術專業：年級：學號：指導教師：李小林職稱：副教授2012年11月日實驗項目列表序號實驗項目名稱成績指導教師1第七章檢索及基本算法23456789101112福建農林大學計算機與信息學院實驗報告系：計算機科學與技術專業：年級：姓名：_三學號：實驗室號計算機號93實驗時間：2012.6.1指導教師簽字：成績：實驗七檢索一、實驗目的和要求1) 掌握檢索的不同方法，并能用高級語言實現檢索算法。2) 熟練掌握順序表和有序表的檢索方法，以及靜態檢索樹的構造方法和檢索算法，理解靜態檢索樹的折半檢索方法。3) 熟練掌握二

2、叉排序樹的構造和檢索方法。4) 熟悉各種存儲結構的特征以及如何應用樹結構解決具體問題。二、實驗內容和原理實驗內容：1)編程實現在二叉檢索樹中刪除一個結點的算法。2)編程實現Fibonacci檢索算法。實驗原理：1)構造排序樹，每輸入一個數就進行排序，選擇插入的結點，刪除結點，沒刪除一個節點就返回到構造排序樹的方法。5) Fibonacci數的定義為f0=0,f1=1,fi=f(i-1)+f(i-2)(in2)。由此得Fibonacci數列為0,1,1,2,3,5,8,13,21,34,55,89,144,設數組F中元素按關鍵字值從小到大順序排列，并假定元素個數n比某個Fibonacci樹fi小

3、1,即n=fi-1。第一次用待查關鍵字k與Ff(i-1),Key比較，其算法描述如下： 若 k=Ff(i-1),Key,則檢索成功，Ff(i-1) 為k所在記錄。 若 k<Ff(i-1),Key,則下一次的檢索范圍為下標1到f(i-1),序列長度為f(i-1)。 若 k>Ff(i-1),Key,則下一次的檢索范圍為下標f(i+1)+1到fi-1,序列長度為(fi-1)-(f(i-1)+1)+1=fi-f(i-1)-1=f(i-2)-1設F是順序存儲的線性表且滿足F1,keyWF2,key<-<Fn。key,k是已知的關鍵字值，在F中檢索關鍵字值為k的記錄。若找到返回其下

4、標值，否則返回0.三、實驗環境WindowsXP系統visualc+6.0四、算法描述及實驗步驟實驗習題一：#include"stdio.h"#include"malloc.h"structBTnodeintdata;structBTnode*lchild,*rchild;*root;typedefstructBTnodeNode,*Nodep;voidcreatetree(intdata)Node*node,*p,*q;node=(Nodep)malloc(sizeof(Node);node->data=data;node->lchild=

5、0;node->rchild=0;if(root=0)root=node;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=node;elsebreak;voidshowtree(structBTnode*proot,structBTnode*m,intspace)inti;charb;if(proot!=0)for(i=

6、1;i<=space-3;i+)printf("");if(space-3>=0)printf("->");if(proot=root)printf("%dn",proot->data);elseb='L'elseb='R'printf("%d(%c)”,proot->data,b);printf("n");m=proot;showtree(proot->lchild,m,space+6);showtree(proot->rchil

7、d,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;elseq->rchild=0;p->lchild=t->lchild;p->rchild=t->rchild;free(t

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

9、lsefree(p)；return(0);NodepdeleteBTnode(intx)Node*p=root,*q;while(p!=0)q=p;if(p->data>x)p=p->lchild;elsebreak;elseif(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)

10、q->lchild=deletep(p);elseif(p=q->rchild)&&(p->data=x)q->rchild=deletep(p);elseif(p->data!=x)printf("cannotfoundthedatayouwanttodelete,pleasecheckit!n");return0;returnroot;intmain()charch;intdata;printf("Enter'c'createtree,Enter'd'deleteanode:&quo

11、t;);scanf("%c",&ch);getchar();root=0;while(ch='c'11ch='d')if(ch='c')printf("pleaseinputthekey:");scanf("%d”,&data);getchar();createtree(data);showtree(root,0,0);elseprintf("pleaseinputthekeyofthenodeyouwantdel:");scanf("%d”,&

12、;data);getchar();if(deleteBTnode(data)showtree(root,0,0);printf("Enter'c'createtree,Enter'd'deleteanode:");scanf("%c",&ch);return0;實驗習題二：#include"stdio.h"typedefintkeytype;typedefintdatatype;typedefstructnodeintkey;rectype;intfibonacci(intn)if(n=0)re

13、turn0;elseif(n=1)return1;elsereturnfibonacci(n-1)+fibonacci(n-2);voidprintData(rectypeR口，intn)inti;for(i=1;i<=n;i+)printf("%5d",Ri.key);if(i%8=0)printf("n");printf("n");intfibsearch(rectypeR口,keytypeK,intn)intm,i,P,q,t；for(m=0;fibonacci(m)<=(n+1);m+)m-;i=fibonacci

14、(m-l);p=fibonacci(m-2);q=fibonacci(m-3);while(i>=0&&i<=n)if(K=Ri.key)returni;elseif(K<Ri.key)i=i-q;t=p;p=q;q=t-q;elseif(K>Ri.key)i=i+q;p=p-q;q=q-p;return0;voidmain()intm,i,k,n;rectypeR20;printf("Enterknum:");scanf("%d",&k);printf("enterR20:");for

15、(i=1;i<=20;i+)scanf("%d”,&Ri.key);printData(R,20);m=fibsearch(R,k,20);if(m=0)printf("Notfound!n");elseprintf("TheKeyhasbeenfoundatR%dn",m);getchar();五、調試過程1)構建二叉排序樹:刪除二叉樹的節點:1：1.1：1；1：1：1.1.：11：1：1.11：11：已啟動生成：項目：麴捐結構試脂，前置.DebugWin32生成啟動時間為2011/5/9L6：£2.34o出垃七iix

16、eEui1dStatus;卜正在創建"D金口*教二居結構試蛉,HLSUtsCei£mEuILu；1d"，因為已指定“色相4yMe總&止"心OCflmyile：.數雌構i踴“PP.式迎儲"kt弓八數據結構試蛉'敷娓堵構試魄I敷娓結構試蛤pQ7）：mrw匚弱：'«¥"：不是“融。”的成員*=：如上”式帥儲點七11A額據結構試驗'數據結榜成蛉1勃據結構前煌.，回）.參見“皿品”的聲明加泰t罐、數據結構試蛉、激據結構試嗓曲據結構試驗5PC29上打/斯C幼3日'""

17、"：不是“口。瓶”的成員匚消gorChjAkdfpl額據結構向哈上數據結構試蛉，數據結構試臉.rpp:參見“蛇。產的聲明_,cAcerGmA業5ktQjA數據結構試臉圖據結構試蛉曲據結構試驗,cppGSl）；errm陽啟9；key"：不是"node"的成員，二八口w八hjAS&kS八數腦給林感'數福結構狀金嗑據結構試臉,泣丁）；善見,"a周"的聲明匕人04苴屈1船工地。仙數據結構試哈1新據籍構試IS（據箝憫試中pGB）;bSFC2C招；:不是n，d的成員W5片r八用"亂研七噸，凝據緒構試驗"教據結構跳蛉'數據結構近臉.斗尸怎）：參見，鼠。品”的聲明pgmVhptdckl摩I數據結構試哈I藪據結何試喊I藪據結初試鴕.qpEBj：。加的：叫"，不是樽養期/的成員卜士"g"八心、提a七匕八器I據第構i醯4數據結梅i臉I射據結胸試臉.用p（5：參見產的聲明.-生成失敗4-“已用時間00