福建农林大学实验报告。
系（教研室）： 计算机专业年级实验课程。
姓名学号实验室号计算机号。
实验时间指导教师签字成绩。
实验四实现fibonacci检索算法(验证性、4学时)
一、 实验目的和要求。
掌握不同的检索方法，并能用高级语言实现检索算法；
熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法和检索算法，理解静态检索树的折半检索方法；
熟练掌握二叉排序树的构造和检索方法；
熟悉各种存储结构的特征以及如何应用树结构解决具体问题；
二、 实验内容和原理。
实验内容：
编程实现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比较，其算法描述如下：
1 若k=f[f(i-1)],key，则检索成功，f[f(i-1)]为k所在记录。
2 若k3 若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.
三、 实验环境。
硬件：1）学生用微机。
2）多**实验教室。
软件：1）windows xp中文操作系统
2）tc3.0或vc6.0
四、 算法描述及实验步骤。
1、算法描述。
已知的关键字key，在r中检索关键字为key的记录，若找到，则返回其下标，否则返回0。
从而可将算法描述为：首先定义一个函数求数列的函数，然后再给出数列的检索算法。例如：
由于n=20< f=21,所以首先应该让关键字key与这20个记录中的第13个记录进行比较。因为f＝f＝13,从而可得判断树如下：
2、算法流程图。
3、**(注释)
#include ""
typedef int keytype; /指定关键值类型为整型*/
typedef int datatype; /指定数据值类型为整型*/
typedef struct node /*定义结点结构体*/
int key;}rectype; /记录类型的标识符*/
int fibonacci(int n) /建立fibonacci数列*/
if(n==0) return 0;
else if(n==1) return 1;
else return fibonacci(n-1)+fibonacci(n-2);
*当n>1时，利用递归调用的实现fibonacci数列*/}
void printdata(rectype r,int n)
int i;
for(i=1; i<=n; i++)
printf("%5d",r[i].key);
if(i%8==0) printf("");
printf("");
int fibsearch(rectype r,keytype k,int n)
int m,i,p,q,t;
for(m=0;fibonacci(m)<=n+1);m循环扫描n+1次*/
m--;在最后一次循环时，满足条件时的fibonacci的数多加了一次，所以将其减1*/
i=fibonacci(m-1); m为fibonacci的数列序号， 得到第m-1个fibonacci数值*/
p=fibonacci(m-2);
q=fibonacci(m-3);
while(i>=0 &&i<=n) /当不小于0并不大于n时做*/
else if(k < r[i].key) /当待查数k小于关键值，检索1到k之间的数*/
else if(k > r[i].key) /当待查数k大于关键值，继续在之后的区间检索*/
i=i+q; /i为原来的i加上q的距离*/
p=p-q; q=q-p; /用于得到q的距离值*/}
return 0; }
main()
int m,i,k,n; /定义局部变量*/
rectype r[20];
printf("请输入k的数值：")
scanf("%d",&k); 输入待检索的关键字k的值*/
printf("输入 r[20]:"
for(i=1;i<=20;i++)循环扫描i次*/
printdata(r,20);
m=fibsearch(r,k,20);/在数组中检索待检索的数并把下标赋给m*/
if(m ==0)
else printf("key 在 r[%d]中被找到",m);}
五、 调试过程。
1.变量没有定义。2.主函数没有返回值。所以要删去“getch()”
六、 实验结果。
测试数据（1）：r[20]:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
实验结果（1）：key在r[5]中。
实验截图（1）：
测试数据（2）：r[20]:1,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38
实验结果（2）：key在r[6]中。
实验截图（2）：
七、 总结。
通过本次实验，掌握了不同的检索算法。初步掌握了顺序表和有序表的检索方法，以及fibonacci数的构造方法和检索算法。并在编程中学会了各种存储结构的特征以及如何应用树结构解决具体问题。
1]谭浩强、张基温等《c语言程序设计（第三版）》，北京：高等教育出版社， 2007；
2]宁正元、王秀娟《算法与数据结构》， 北京：清华大学出版社， 2006；
3]严蔚敏、佩娟等《数据结构》，北京：国防工业出版社， 1981；
算法与数据结构实验
实验1 adt list 线性表 6学时 问题描述 线性表是典型的线性结构，实现adt list，并在此基础上实现两个集合的交运算和并运算。实验目的 1 掌握线性表的链表存储结构。2 掌握在单链表上基本操作的实现。3 在掌握单链表的基本操作上进行综合题的实现。实验内容及要求 1 要求用带头结点的单链...
数据结构与算法实验
计算机科学与技术系。实验报告。专业名称网络系统管理 课程名称数据结构与算法 项目名称堆栈实验 班级 13网络系统管理 学号 1304052010 姓名汪康。同组人员。实验日期。一 实验目的与要求 1 掌握堆栈的两种不同的存储结构。2 掌握应用堆栈表示数据 并进行有关算法设计的方法。二 实验背景 堆栈...
数据结构与算法分析实验
教材 电子信息技术专业实验指导书的第2章 数据结构实验。本实验课学分 0.5 上课周次 10周 17周 各个班不同，13 成绩评定 随课实验，成绩不单独给，但会体现在数据结构与算法分析课程的成绩中，课程总3.5学分，理论课程3学分，实验0.教材 电子信息技术专业实验指导书的第2章 数据结构实验。本实...