数据结构实验报告-检索及基本算法

福建农林大学计算机与信息学院实验报告检索及基本算法实验目的和要求掌握检索的不同方法，并能用高级语言实现检索算法。熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法和检索算法，理解静态检索树的折半检索方法。熟练掌握二叉排序树的构造和检索方法。熟悉各种存储结构的特征以及如何应用树结构解决具体问题。实验内容和原理实验内容：编程实现Fibonacci检索算法。实验原理：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，……设数组F中元素按关键字值从小到大顺序排列，并假定元素个数n比某个Fibonacci 树fi小1，即n=fi-1。第一次用待查关键字k与F[f（i-1）]，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，则下一次的检索范围为下标f(i+1)+1到fi-1，序列长度为（fi-1）-（f(i-1)+1）+1=fi-f(i-1)-1=f(i-2)-1设F是顺序存储的线性表且满足F[1]，key≤F[2]，key≤…≤F[n]。key,k是已知的关键字值，在F中检索关键字值为k的记录。若找到返回其下标值，否则返回0.实验环境WindowsXP系统visualc++6.0算法描述及实验步骤实验习题：#include"stdio.h"#definetrue1#definefalse0typedefintkeytype;typedefintdatatype;typedefstruct{keytypekey;datatypeother;}rectype;intfibonacci(intn){if(n==0)return(n);elseif(n==1)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2));}intfibosrch(rectypeR[],keytypek,intn){inti,p,q,s,t,flag1,flag2;i=fibonacci(n-1);q=fibonacci(n-2);s=fibonacci(n-3);s=n+1-(i+p);if(k>R[i].key)i=i+s;flag1=false;while((i)&&(!flag1)){if(R[i].key==k)flag2=1;elseif(R[i].key>k)flag2=3;switch(flag2){case1:flag1=true;break;case2:if(q==0)i=0; else{i=i-q;t=p;p=q;q=t-p;}break;case3:if(p==1)i=0;else{i=i+p;p=p-q;q=q-p;}break;default:;}}return(i);}main(){inta,i,k,n;rectypeR[15];scanf("%d",&k);for(i=1;i<=15;i++)scanf("%d",R[i]);a=fibosrch(R,k,15);printf("%d",a);}调试过程在创建结构体时未定义key.实验结果在Fibonacci数列没有找到关键字的情况：在Fibonacci数列找到关键字的情况：总结掌握了二叉排序树的构造和检索方法。删除二叉检索树的结点时