2022年数据结构实验四实现Fibonacci检索算法参考 .pdf

《2022年数据结构实验四实现Fibonacci检索算法参考 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验四实现Fibonacci检索算法参考 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、福建农林大学金山学院实验报告系：专业：计算机科学与技术年级：08 级姓名：曾钦选学号：082231032 实验室号计算机号实验时间：指导教师签字：成绩：实验四 实现 Fibonacci检索算法 (验证性、 4 学时一、 实验目的和要求掌握不同的检索方法，并能用高级语言实现检索算法；熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法和检索算法，理解静态检索树的折半检索方法；熟练掌握二叉排序树的构造和检索方法；熟悉各种存储结构的特征以及如何应用树结构解决具体问题；二、 实验内容和原理实验内容：编程实现Fibonacci检索算法实验原理：Fibonacci数的定义为f0=0,f1=1,fi=

2、f(i-1)+f(i-2)(i2) 。由此得Fibonacci 数列为 0，1，1，2，3，5， 8，13， 21，34，55， 89，144，设数组 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

3、设 F 是顺序存储的线性表且满足F1 ，keyF2 ，key Fn 。key,k 是已知的关键字值，在F中检索关键字值为k 的记录。若找到返回其下标值，否则返回0. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 三、 实验环境硬件：（1）学生用微机（2）多媒体实验教室软件：（1）Windows XP 中文操作系统（2）TC3.0 或 VC6.0 四、 算法描述及实验步骤1、描述通过二分法的思路在有序表中取得中间项（通过费波拉数

4、列进行定位）作为比较对象，若给定值与中间记录的关键字相等，则检索成功； 若小于记录着在表左侧进行检索；若大于中间记录着在右侧检索；就这样通过一次次的缩小检索范围，在每一个检索区间重新定位中间项作为比较对象，不断的检索下去直至检索成功，或区间无记录而检索失败。2、流程图3、代码 (注释) #include stdio.h #define max 100 typedef struct /定义数据存放为结构体类型 int key; /仅含一个整型数据成员sglist; /该数据类型标识符low=hight int low ，mid，hight，i；low=1;hight=n-1; Y k=Rmid.

5、key N return mid; Y kRmid.key N hight=mid-1; low=mid+1; return 0; i=fibinx(hight-low+2); mid=low+fibonacci(i-1)-1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - int fibonacci(int n) /费波拉数列构造函数 if(n=0) /首项为 0 return 0; else if(n=1) /第二项为1

6、return 1; else return (fibonacci(n-1)+fibonacci(n-2); /递归实现第三项及之后各项计算 int fibinx(int m) /数据转化为费波拉数列相应项下标 int i=1; while(fibonacci(i)!=m & i100) /循环控制第2 项起比较直至第100 项上限i+; return i; /返回下标 int fibonsearch(sglist R,int k,int n) /费波拉数列定位二分位置查询数据 int low,mid,hight,i; /定义下标指针low=1; /指向数列第一项hight=n-1; /指向数列

7、末尾项while(low=hight) /循环控制子目录数据列 i=fibinx(hight-low+2); /定位费波拉数列下标mid=low+fibonacci(i-1)-1; /由费波拉数列下标进行运算指向新的数列二分中间项if(k=Rmid.key) /查询值与数列二分中间项相等return mid; /返回下标else if(kRmid.key) /查询值小于数列二分中间项hight=mid-1; /在数列二分中间项的左侧进行比较else low=mid+1; /在数列二分中间项的右侧进行比较 return 0; int main() /主函数 int m,i=1; /定义两数作为所

8、定位的费波拉数列返回下标和输入数据的下标(个数) int k; /所要查找的数据名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - sglist Rmax; /输入数据存放位置printf( 请输入第 %d 个数据 :,i); scanf(%d,&Ri.key); while(Ri.key!=-2) /控制输入结束 i+; printf( 请输入第 %d 个数据 :,i); scanf(%d,&Ri.key); /printf(%d

9、n,fibinx(i); printf( 请输入要查找数据:); scanf(%d,&k); m=fibonsearch(R,k,i); /调用查询函数if(m=0) printf( 找不到数据 %dn,k); else printf( 数据 %d 位于 %dn,k,m); return 0; 五、 调试过程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 比较两图猜想当给定值位于数列后半部时程序成功实现了检索而当给定值位于数列前

10、半部时程序无法实现检索而进入后台死循环；通过多组数据检验确实如此；所以可以断定在定位二分区间时出错了通过检查得知由于数组时从下标1 开始的i=fibinx(hight-low+1); int fibinx(int m) int i=1; while(fibonacci(i)!=m & i100) i+; return i; 并不能使得n=Fi-1 因 此 修 改i=fibinx(hight-low+1);为i=fibinx(hight-low+2);或while(fibonacci(i)-1)!=m & i100) 可经过修改无论在哪个区间均不能实现检索了；仔细检查了代码调试发现错误在于将输入

11、数据时将末尾结束项-2 作为了数列的一项，而数列要求是有序的。-2 不仅使得定位费波拉下标出错而且打乱了数据顺序。由此只需将hight指向 n-1 即可消除结束项的影响；最终结果如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 六、 总结该实验让我掌握了顺序表和有序表的二分检索方法，及静态检索树的构造，加深了我对静态检索树的折半检索方法的理解，一个简单的二分检索法通过费波拉数列实现了费波拉检索使我清楚的认识到理解并熟练掌握基础算法的重要性，只有在此基础上才可能灵活运用各种算法最大程度上衍生出为我所用的更好的算法。附录：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -