查找算法

浏览量:222    修改时间:2017-07-05 11:30:48
/** * Created on: 2016年09月18日 18:29:35 * Author: Guest * Copyright (c) 2016, tool.usta.wiki , All Rights Reserved. */ #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ int F[100]; /* 斐波那契数列 */ /* 无哨兵顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字 */ int Sequential_Search(int *a,int n,int key) { int i; for(i=1; i<=n; i++) { if (a[i]==key) return i; } return 0; } /* 有哨兵顺序查找 */ int Sequential_Search2(int *a,int n,int key) { int i; a[0]=key; i=n; while(a[i]!=key) { i--; } return i; } /* 折半查找 */ int Binary_Search(int *a,int n,int key) { int low,high,mid; low=1; /* 定义最低下标为记录首位 */ high=n; /* 定义最高下标为记录末位 */ while(low<=high) { mid=(low+high)/2; /* 折半 */ if (key<a[mid]) /* 若查找值比中值小 */ high=mid-1; /* 最高下标调整到中位下标小一位 */ else if (key>a[mid])/* 若查找值比中值大 */ low=mid+1; /* 最低下标调整到中位下标大一位 */ else { return mid; /* 若相等则说明mid即为查找到的位置 */ } } return 0; } /* 插值查找 */ int Interpolation_Search(int *a,int n,int key) { int low,high,mid; low=1; /* 定义最低下标为记录首位 */ high=n; /* 定义最高下标为记录末位 */ while(low<=high) { mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */ if (key<a[mid]) /* 若查找值比插值小 */ high=mid-1; /* 最高下标调整到插值下标小一位 */ else if (key>a[mid])/* 若查找值比插值大 */ low=mid+1; /* 最低下标调整到插值下标大一位 */ else return mid; /* 若相等则说明mid即为查找到的位置 */ } return 0; } /* 斐波那契查找 */ int Fibonacci_Search(int *a,int n,int key) { int low,high,mid,i,k=0; low=1; /* 定义最低下标为记录首位 */ high=n; /* 定义最高下标为记录末位 */ while(n>F[k]-1) k++; for (i=n; i<F[k]-1; i++) a[i]=a[n]; while(low<=high) { mid=low+F[k-1]-1; if (key<a[mid]) { high=mid-1; k=k-1; } else if (key>a[mid]) { low=mid+1; k=k-2; } else { if (mid<=n) return mid; /* 若相等则说明mid即为查找到的位置 */ else return n; } } return 0; } int main(void) { int a[MAXSIZE+1],i,result; int arr[MAXSIZE]= {0,1,16,24,35,47,59,62,73,88,99}; for(i=0; i<=MAXSIZE; i++) { a[i]=i; } result=Sequential_Search(a,MAXSIZE,MAXSIZE); printf("Sequential_Search:%d \n",result); result=Sequential_Search2(a,MAXSIZE,1); printf("Sequential_Search2:%d \n",result); result=Binary_Search(arr,10,62); printf("Binary_Search:%d \n",result); result=Interpolation_Search(arr,10,62); printf("Interpolation_Search:%d \n",result); F[0]=0; F[1]=1; for(i = 2; i < 100; i++) { F[i] = F[i-1] + F[i-2]; } result=Fibonacci_Search(arr,10,62); printf("Fibonacci_Search:%d \n",result); return 0; }