数据结构(C语言版)——有序表查找(斐波那契查找)(代码版)

一、代码

#include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 #define MAXSIZE 20 typedef int Status; Status fbi(int number); Status fbiSearch(int fbiArr[],int fbiArrLenght,int dataArr[],int dataArrLenght,int wantSearchElement); int main(int argc, char *argv[]) { int i,fbiSize,dataArr[MAXSIZE],size,wantSearch,result; //创建斐波那契数组 printf("请输你要创建的斐波那契数组大小:"); if(scanf("%d",&fbiSize)==0) { printf("输入错误!\n"); fflush(stdin); return ERROR; } int fbiArr[fbiSize]; for(i=0;i<fbiSize;i++) fbiArr[i]=fbi(i); //创建数组 printf("请输入初始化数组大小(1-%d):",MAXSIZE-2); scanf("%d",&size); printf("请输入数组元素(空格隔开):"); for(i=1;i<=size;i++) { if(scanf("%d",&dataArr[i])==0) { printf("输入错误\n"); fflush(stdin); return ERROR; } } //输入要寻找的元素 printf("请输入你要查找的内容:"); if(scanf("%d",&wantSearch)==0) { printf("输入错误\n"); fflush(stdin); return ERROR; } if((result= fbiSearch(fbiArr,fbiSize,dataArr,size,wantSearch))==ERROR) { printf("你要查找的元素不在数组中\n"); return ERROR; } printf("元素在数组中%d位置\n",result); return 0; } //斐波那契函数 Status fbi(int number) { if(number<2) return number==0?0:1; return fbi(number-1)+fbi(number-2); } //斐波那契查找 Status fbiSearch(int fbiArr[],int fbiArrLenght,int dataArr[],int dataArrLenght,int wantSearchElement) { int low=1,high=dataArrLenght,k=0,mid,i;//初始化 while(dataArrLenght>fbiArr[k]-1) k++;//寻找斐波那契中dataArrLenght的位置 for(i=dataArrLenght;i<fbiArr[k]-1;i++) dataArr[i]=dataArr[dataArrLenght]; while(low<=high) { mid=low+fbiArr[k-1]-1; if(wantSearchElement<dataArr[mid]) {//新范围在low~mid-1之间，这之间的个数为fbiArr[k-1]-1个 high=mid-1; k=k-1; }else if(wantSearchElement>dataArr[mid]) { low=mid+1; k=k-2; }else{ if(mid<=dataArrLenght) return mid; else return dataArrLenght; } } return ERROR; }

二、代码中重要的函数或语句

(一)、

printf("请输你要创建的斐波那契数组大小:"); if(scanf("%d",&fbiSize)==0) { printf("输入错误!\n"); fflush(stdin); return ERROR; } int fbiArr[fbiSize];

这里我用了边长数组 (二)、斐波那契函数

//斐波那契函数 Status fbi(int number) { if(number<2) return number==0?0:1; return fbi(number-1)+fbi(number-2); }

用递归生成斐波那契数列，注意数列的特性，因为在查找中会用到这个特性 特性就是Fib(5)=Fib(4)+Fib(3); 在下面的代码中用得到

if(wantSearchElement<dataArr[mid]) {//新范围在low~mid-1之间，这之间的个数为fbiArr[k-1]-1个 high=mid-1; k=k-1; }else if(wantSearchElement>dataArr[mid]) { low=mid+1; k=k-2; }else{ if(mid<=dataArrLenght) return mid; else return dataArrLenght; }

在这里当wantSearchElement<dataArr[mid]就k=k-1，当wantSearchElement>dataArr[mid]就k=k-2；解释如下 F[k]-1=F[k-1]-1+F[k-2]-1;(fib(5)=fib(4)+fib(3));

三、运行截图