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

2、熟練掌握二叉排序樹的構造和檢索方法。4) 熟悉各種存儲結構的特征以及如何應用樹結構解決具體問題。二、實驗內容和原理實驗內容：1) 編程實現在二叉檢索樹中刪除一個結點的算法。2) 編程實現Fibonacci檢索算法。實驗原理：1)構造排序樹，每輸入一個數就進行排序，選擇插入的結點，刪除結點, 沒刪除一個節點就返回到構造排序樹的方法。2) Fibonacci 數的定義為 fO=O,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,設數組F中元素按關鍵字值從小到大順

3、序排列，并假定元素個數n比某個Fibonacci樹fi小1,即n=fi-1。第一次用待查關鍵字k與Ff (i-1 ), 若 k=Ff(i-1),Key 若 k<Ff(i-1),Key 長度為f(i-1)。 若 k>Ff(i-1),KeyKey比較，其算法描述如下:，貝葉僉索成功，Ff(i-1) 為k所在記錄。，則下一次的檢索范圍為下標1到f(i-1)，序列，則下一次的檢索范圍為下標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<

4、;-< Fnkey,k是已知的關鍵字值，在F中檢索關鍵字值為k的記錄。若找到返回 其下標值，否則返回0.三、實驗環境Win dows XP 系統visual C+6.0四、算法描述及實驗步驟實驗習題一：#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;實驗習題二：#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();五、調試過程1)構建二叉排序樹：刪除二叉樹的節點：已直動生咸-頃目：數搦結構試驗配畫.De lug

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

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