1. #include "stdio.h"    
    2. #include "stdlib.h"   
    3. #include "io.h"  
    4. #include "math.h"  
    5. #include "time.h"
    7. #define OK 1
    8. #define ERROR 0
    9. #define TRUE 1
    10. #define FALSE 0
    11. #define MAXSIZE 100 /* 存储空间初始分配量 */
    13. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
    15. int F[100]; /* 斐波那契数列 */
    17. /* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
    18. int Sequential_Search(int *a,int n,int key)
    19. {
    20.     int i;
    21.     for(i=1;i<=n;i++)
    22.     {
    23.         if (a[i]==key)
    24.             return i;
    25.     }
    26.     return 0;
    27. }
    28. /* 有哨兵顺序查找 */
    29. int Sequential_Search2(int *a,int n,int key)
    30. {
    31.     int i;
    32.     a[0]=key;
    33.     i=n;
    34.     while(a[i]!=key)
    35.     {
    36.         i--;
    37.     }
    38.     return i;
    39. }
    41. /* 折半查找 */
    42. int Binary_Search(int *a,int n,int key)
    43. {
    44.     int low,high,mid;
    45.     low=1;    /* 定义最低下标为记录首位 */
    46.     high=n;    /* 定义最高下标为记录末位 */
    47.     while(low<=high)
    48.     {
    49.         mid=(low+high)/2;    /* 折半 */
    50.         if (key<a[mid])        /* 若查找值比中值小 */
    51.             high=mid-1;        /* 最高下标调整到中位下标小一位 */
    52.         else if (key>a[mid])/* 若查找值比中值大 */
    53.             low=mid+1;        /* 最低下标调整到中位下标大一位 */
    54.         else
    55.         {
    56.             return mid;        /* 若相等则说明mid即为查找到的位置 */
    57.         }
    59.     }
    60.     return 0;
    61. }
    63. /* 插值查找 */
    64. int Interpolation_Search(int *a,int n,int key)
    65. {
    66.     int low,high,mid;
    67.     low=1;    /* 定义最低下标为记录首位 */
    68.     high=n;    /* 定义最高下标为记录末位 */
    69.     while(low<=high)
    70.     {
    71.         mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
    72.         if (key<a[mid])        /* 若查找值比插值小 */
    73.             high=mid-1;        /* 最高下标调整到插值下标小一位 */
    74.         else if (key>a[mid])/* 若查找值比插值大 */
    75.             low=mid+1;        /* 最低下标调整到插值下标大一位 */
    76.         else
    77.             return mid;        /* 若相等则说明mid即为查找到的位置 */
    78.     }
    79.     return 0;
    80. }
    82. /* 斐波那契查找 */
    83. int Fibonacci_Search(int *a,int n,int key)
    84. {
    85.     int low,high,mid,i,k=0;
    86.     low=1;    /* 定义最低下标为记录首位 */
    87.     high=n;    /* 定义最高下标为记录末位 */
    88.     while(n>F[k]-1)
    89.         k++;
    90.     for (i=n;i<F[k]-1;i++)
    91.         a[i]=a[n];
    93.     while(low<=high)
    94.     {
    95.         mid=low+F[k-1]-1;
    96.         if (key<a[mid])
    97.         {
    98.             high=mid-1;        
    99.             k=k-1;
    100.         }
    101.         else if (key>a[mid])
    102.         {
    103.             low=mid+1;        
    104.             k=k-2;
    105.         }
    106.         else
    107.         {
    108.             if (mid<=n)
    109.                 return mid;        /* 若相等则说明mid即为查找到的位置 */
    110.             else 
    111.                 return n;
    112.         }
    114.     }
    115.     return 0;
    116. }
    123. int main(void)
    124. {    
    126.     int a[MAXSIZE+1],i,result;
    127.     int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    129.     for(i=0;i<=MAXSIZE;i++)
    130.     {
    131.         a[i]=i;
    132.     }
    133.     result=Sequential_Search(a,MAXSIZE,MAXSIZE);
    134.     printf("Sequential_Search:%d \n",result);
    135.     result=Sequential_Search2(a,MAXSIZE,1);
    136.     printf("Sequential_Search2:%d \n",result);
    138.     result=Binary_Search(arr,10,62);
    139.     printf("Binary_Search:%d \n",result);
    142.     result=Interpolation_Search(arr,10,62);
    143.     printf("Interpolation_Search:%d \n",result);
    146.     F[0]=0;
    147.     F[1]=1;
    148.     for(i = 2;i < 100;i++)  
    149.     { 
    150.         F[i] = F[i-1] + F[i-2];  
    151.     } 
    152.     result=Fibonacci_Search(arr,10,62);
    153.     printf("Fibonacci_Search:%d \n",result);
    155.     return 0;
    156. }