國脈信息學院（程序設計類課程）實驗報告課程名稱：算法與數據構造姓名：張三系：計算機科學與技術專業(yè)：年級：學號：指導教師：李小林職稱：副教授2012年11月日實驗項目列表序號實驗項目名稱成績指導教師1第七章檢索及基本算法23456789101112福建農林大學計算機與信息學院實驗報告系：計算機科學與技術專業(yè)：年級：姓名：張三學號：實驗室號____計算機號93實驗時間：指導教師簽字：成績：實驗七檢索一、實驗目的和要求掌握檢索的不一樣方法，并能用高級語言實現檢索算法。熟練掌握序次表和有序表的檢索方法，以及靜態(tài)檢索樹的構造方法和檢索算法，理解靜態(tài)檢索樹的折半檢索方法。熟練掌握二叉排序樹的構造和檢索方法。熟習各種儲存構造的特色以及如何應用樹構造解決詳盡問題。二、實驗內容和原理實驗內容：編程實此刻二叉檢索樹中刪除一個結點的算法。編程實現Fibonacci檢索算法。實驗原理：1）構造排序樹，每輸入一個數就進行排序，選擇插入的結點，刪除結點，沒刪除一個節(jié)點就返回到構造排序樹的方法。2）Fibonacci數的定義為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，設數組Fibonacci

F

中元素按要點字值從小到大序次擺列，并假定元素個數樹fi小1，即n=fi-1。第一次用待查要點字k與F[f（i-1

n比某個）]，Key比較，其算法描述

以下：①若k=F[f(i-1)],Key，則檢索成功，F[f(i-1)]為k所在記錄。②若k<F[f(i-1)],Key，則下一次的檢索范圍為下標1到f(i-1)，序列長度為f(i-1)。③若k>F[f(i-1)],Key，則下一次的檢索范圍為下標度為（fi-1）-（f(i-1)+1）+1=fi-f(i-1)-1=f(i-2)-1

f(i+1)+1

到

fi-1

，序列長設F是序次儲存的線性表且滿足F[1]，key≤F[2]，key≤≤F[n]。key,k是已知的要點字值，在F中檢索要點字值為k的記錄。若找到返回其下標值，不然返回0.三、實驗環(huán)境WindowsXP系統(tǒng)visualc++6.0四、算法描述及實驗步驟實驗習題一：#include"stdio.h"#include"malloc.h"structBTnode{intdata;structBTnode*lchild,*rchild;}*root;typedefstructBTnodeNode,*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;}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=1;i<=space-3;i++)printf("");if(space-3>=0)printf("---->");if(proot==root)printf("%d\n",proot->data);else{if(m->data>proot->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);}}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);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!=0)q->lchild=p->rchild;elseq->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;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))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:"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:"

);}return0;}實驗習題二：#include"stdio.h"typedefintkeytype;typedefintdatatype;typedefstructnode{intkey;}rectype;intfibonacci(intn){if(n==0)return0;elseif(n==1)return1;elsereturnfibonacci(n-1)+fibonacci(n-2);}voidprintData(rectypeR[],intn){inti;for(i=1;i<=n;i++){printf("%5d",R[i].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(m-1);p=fibonacci(m-2);q=fibonacci(m-3);while(i>=0&&i<=n){if(K==R[i].key){returni;}elseif(K<R[i].key){i=i-q;t=p;p=q;q=t-q;}elseif(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();}五、調試過程1)成立二叉排序樹：刪除二叉樹的節(jié)點：2)在創(chuàng)立構造體時不決義key.六、實驗結果1）成