开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
9_7.C
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：3k
源码类别：

数据结构

开发平台：

C/C++

9_7.C：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 9_7.c                       */
  3. /*    插补搜索                              */
  4. /* ======================================== */
  5. #include <stdlib.h>
  6. #define MAX  20                   /* 最大阵列容量         */
  8. struct element                    /* 记录结构宣告         */
  9. {
  10.    int key;                       /* 搜索键值             */
  11. };
  12. typedef struct element record;    /* 结构新型态           */
  13. record data[MAX] = {              /* 结构阵列宣告         */
  14.        2,   5,   7,   9,  17,  21,  25,
  15.       33,  46,  48,  51,  52,  63,  69,
  16.       77,  78,  80,  89,  94,  99 };
  18. /* ---------------------------------------- */
  19. /*  插补搜索                                */
  20. /* ---------------------------------------- */
  21. int intersearch(int n,int key)
  22. {
  23.    if ( key < data[0].key || key > data[n-1].key )
  24.       return -1;                  /* 没有找到             */
  25.    else
  26.       return interfind(key,0,n-1);  /* 递回呼叫         */
  27. }
  29. /* ---------------------------------------- */
  30. /*  插补搜索递回处理                        */
  31. /* ---------------------------------------- */
  32. int interfind(int key,int left,int right)
  33. {
  34.    int next_guess;                /* 下一个可能索引       */
  35.    int offset;                    /* 索引位移             */
  36.    int range;                     /* 键值范围             */
  37.    int index_range;               /* 索引范围             */
  38.    int temp;
  40.    if ( data[left].key == key )   /* 找到了               */
  41.       return left;
  42.    else
  43.       /* 没有找到 */
  44.       if ( left == right ||
  45.            data[left].key == data[right].key )
  46.          return -1;
  47.       else
  48.       {
  49.          index_range = right - left;  /* 计算索引范围     */
  50.          /* 计算键值范围 */
  51.          range = data[right].key - data[left].key;
  52.          offset = key - data[left].key;   /* 计算键值位移 */
  53.          temp = ( offset * index_range )  / range;
  54.          next_guess = left + temp;      /* 下一个可能索引 */
  55.          if ( next_guess == left )      /* 己试过         */
  56.             next_guess++;
  57.          if ( key < data[next_guess].key )
  58.             /* 左边部分递回呼叫插补搜索 */
  59.             return interfind(key,left,next_guess - 1);
  60.          else
  61.             /* 右边部分递回呼叫插补搜索 */
  62.             return interfind(key,next_guess,right);
  63.       }
  64. }
  66. /* ---------------------------------------- */
  67. /*  主程式: 在一个已排序的阵列, 接着输入    */
  68. /*  值用插补搜索来找值.                     */
  69. /* ---------------------------------------- */
  70. void main()
  71. {
  72.    int found;                     /* 是否找到变数         */
  73.    int value;                     /* 搜索值的内容         */
  75.    while ( 1 )                    /* 主回路开始           */
  76.    {
  77.       printf("n请输入搜索值(0-100) ==> ");
  78.       scanf("%d",&value);         /* 读入搜索值           */
  79.       if ( value != -1 )
  80.       {
  81.          found = intersearch(MAX,value);  /* 呼叫插补搜索 */
  82.          if ( found != -1 )
  83.             printf("找到搜索值:%d[%d]n",value,found);
  84.          else
  85.             printf("没有找到搜索值:%dn",value);
  86.       }
  87.       else
  88.          exit(1);                 /* 结束程式             */
  89.    }
  90. }