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

2、解靜態檢索樹的折半檢索方法。3) 熟練掌握二叉排序樹的構造和檢索方法。4) 熟悉各種存儲結構的特征以及如何應用樹結構解決具體問題。二、實驗內容和原理實驗內容：1) 編程實現在二叉檢索樹中刪除一個結點的算法。2) 編程實現Fibonacci檢索算法。實驗原理：1)構造排序樹，每輸入一個數就進行排序，選擇插入的結點，刪除結點，沒刪 除一個節點就返回到構造排序樹的方法。2 ) Fib on acci 數的定義為 f0=0,f1=1,fi二f(i-1)+f(i-2)(i 2)。由此得Fibonacci 數列為 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,設

3、數組F中元素按關鍵字值從小到大順序排列，并假定元素個數n比某個Fibonacci 樹fi小1,即n二fi-1。第一次用待查關鍵字 k與Ff (i-1 ) , Key比較，其算法描述如下： 若k=Ff(i-1),Key ，則檢索成功，Ff(i-1) 為k所在記錄。 若kFf(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，key F2，key-data=data;no de-lchild=0;no de-rchild=0;if (root=0

4、)root=no de;return ;else p=root;while (p!=0)if (datadata)q=p；p=p-lchild;if (p=0)q-lchild=no de;elseif (datap-data)q=p; p=p-rchild;if (p=0) q-rchild=no de;elsebreak;void showtree( struct BTnode *proot, struct BTnode *m, int space) int i;char b;if (proot!=0)for (i=1;i=0) printf( -);if (proot=root)prin

5、tf( %dn ,proot-data);elseif (m-dataproot-data)b=L;elseb=R;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!=0)q=p;p=p-rchild;if (p=q)p-rchild=t-rchi

6、ld;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);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; free(t); return (p);if (p-rchild!=O) q-lchild=p-rchild; else q-lchild=0;p-rch

7、ild=t-rchild; p-lchild=t-lchild; free(t); return (p); else free(p);return (0);Nodep deleteBTnode( int x)Node *p=root,*q;while (p!=0) q=p;if (p-datax) if (p-lchild) p=p-lchild;elsebreak;elseif (p-datarchild) p=p-rchild;else break;if (p-data=x) break;if (p=root)&(p-data=x) root=deletep(p); elseif (p=q

8、-lchild)&(p-data=x) q-lchild=deletep(p);elseif (p=q-rchild)&(p-data=x) q-rchild=deletep(p);elseif (p-data!=x)printf( ca n not found the data you want to delete,please check 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);get

9、char();root=0;while (ch=c |ch= d)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,0);printf( En ter c create tree,E n

10、ter d delete a no de:);scanf( %c,&ch);return 0;實驗習題二：#i nclude stdio.htypedef int keytype;typedef int datatype;typedef struct nodeint key;rectype;int fibonacci( int n)if (n=0) return 0; elseif (n=1) return 1;elsereturn fibonacci(n-1)+fibonacci(n-2); void printData(rectype R, int n) int i;for (i=1; i

11、=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)=0 & i=n)if (K = Ri.key)return i; else if (K Ri.key) i=i+q; p=p-q; q=q-p; return 0; void main()int m,i,k,n;rectype R20;printf(En ter k nu m: );sca nf(%d,&k);prin

12、tf(enter R20:);for (i=1;i2Enter 7cJ createtFee,Enterdttlefceanode:cpleaseLinput thekey = 8D28Enter 1cJ createteej-Entei*deleteanode：cpleaseczlnpui: tliekey4D2噸BEnter JcJ createtree,EnterJdJde L&teanode = cpleaseinput tlie248 I nEnter 1 c1tieplGN訪& input 七he t?Entei* 1 c1 create please input the t?-i

13、 Enter J c1 create pie裁& Input the &7-l r CL Enter 1c1 create please input the 67E CL -2 CL 7 CR Enter J cf create please input the &7ti?eeiter J dJ key =ti*ee,Enter J7 CR ?0 CRde letc a rk o de - cdelcte a node-cde lete a node：cdelete a node：cde lete a node：c刪除二叉樹的節點:blease lni)ut the-l 90 Entei* J

14、 cJ create please input the&7tree . EntevJ dJ delete a node:c-2e90Enter JcJ createp2eseJie-2 8-9 Qtvce , Erttei* liy of tLeJdJ delete a node:d node t/ou wan le 1：1inter J cJ create leesG input thetreejEnter 畑y of ttieJ dJ deletc a node:d nods 5-2 9B Enter J cJ create半；tree M Enter? cn i J cJ cr-eate

15、 se input thetpee,Enter JdJ de letea. node: cyt715 Enter F c pleasecreate input thetree,Enter JdJ delete key：9a. node : c67CRCR9 CLEn te 1 c 1 creaite please input tlie cahEnttteeEnto J d J de lets a node - d key of tlie node you want del： 1 not Found the data /ou uant to de leteplease er f c1 creat

16、echeck it*please input thetree,Enterde lete 孔 node :dl key of the node you uant del：?6 CR9 CB15 CIO Entei* c createtifee.EMev* Jd j de lete a node:11.1；1：1：11：11.1：1 ；111.1.111：1已啟動生成：I頁目：埶將結梅誼驗lebut Nin3生成啟動時間為011/6/9 1氐田：3吒血11 i al i z1 dSt itKLw:” Efifi fieWO結構試驗 umehc cess fulluiId !因為己指定 M-wayz

17、Crate * HTlComjile k數據結構ii - uppP丘叱Ih譏址kt dr燭據鎗枸訊您歸據結枸iit髓城據結物iil瞌mp(lT)： ?0 CREnctp f c1 ci*feAtetiee,Entei*deleteanode：cplease input thekesj：2121 CL?0 CREnter J c1 createtree,. Enterdeleteanode-cples：e input thekey = 5 &t?21 ?0Enver f c1 cirete tree Enter 1 d* delete a node ；c input the kev：34&7L兀

18、& CR34 CLI90Eri 七亡 j* * cf create tree , Enter 1 d * de le te % node -c please Input the key；246721 956 W34 24 CL?-90 CR刪除結點成功:Encepci*eatepie else in pat the 6724 CL?56 34 CL99Ent ev J cf ci*eatet re e , En t e p d de le t e a. n o de : a ke of the node tou.叩de 1：21plea.se in put the6724 94 90 tFWE

19、.EbtEF J df de le a m o de ： d keF of the node you want de 1:5&Enter 1 c1 crea t 療 nle&se input the 6724 ?& t re e , Ente r 1 d1 de lete a. nqde ： d key qF the node yoit want deL：34刪除結點失敗:EnteF1create tFeeEnti fd* delete a node：dplease input tlie Icey of tJie node yoit uant de 1 - 34can not found the datat to deLet巳，卩Eunwg 耳iiuuk it;! Enter rcr create treeEnter delete a node:dpiease inp