C语言中怎么实现折半查找

这篇文章将为大家详细讲解有关C语言中怎么实现折半查找，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

数据结构 折半查找

实例代码：

  #include <stdio.h>  #include <malloc.h>  #include <windows.h>      #define N 11 // 数据元素个数     typedef int KeyType; // 设关键字域为整型     typedef struct // 数据元素类型   {    KeyType key;  // 关键字域     int others;   // 其它部分    }ElemType;      // Search_Seq.h 静态查找表的顺序存储结构   typedef struct  {    // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空    ElemType *elem;    int length; // 表长度   }SSTable;    ElemType r[N]={    {05,1},{13,2},{19,3},{21,4},    {37,5},{56,6},{64,7},{75,8},    {80,9},{88,10},{92,11}  }; // 数据元素(以教科书P219的数据为例),全局变量       // 静态查找表(顺序表和有序表)的基本操作(7个)     // 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r)   int Creat_Seq(SSTable *ST,int n)  {     int i;    (*ST).elem = (ElemType *)calloc(n+1, sizeof(ElemType));     // 动态生成n+1个数据元素空间(0号单元不用)     if(!(*ST).elem)      return 0;    for( i = 1; i <= n; i++)      *((*ST).elem+i) = r[i-1]; // 将全局数组r的值依次赋给ST     (*ST).length = n;    return 1;  }    // 重建静态查找表为按关键字非降序排序   void Ascend(SSTable *ST)  {      int i, j, k;    for(i = 1; i < (*ST).length; i++)    {      k = i;      (*ST).elem[0] = (*ST).elem[i]; // 待比较值存[0]单元       for(j = i+1; j <= (*ST).length; j++) //从中找到第i小的值        if ((*ST).elem[j].key < (*ST).elem[0].key)        {          k=j;          (*ST).elem[0]=(*ST).elem[j];        }      if(k != i) // 有更小的值则交换       {        (*ST).elem[k]=(*ST).elem[i];        (*ST).elem[i]=(*ST).elem[0];      }    }  }    // 构造一个含n个数据元素的静态按关键字非降序查找表ST,  // 数据来自全局数组r   int Creat_Ord(SSTable *ST,int n)  {    int f;    f = Creat_Seq(ST,n);  //构建一个静态表    if( f ) //静态表存在，则对其进行重建      Ascend(ST);    return f;  }    // 销毁表ST   int Destroy(SSTable *ST)  {     free((*ST).elem);    (*ST).elem = NULL;    (*ST).length = 0;      return 1;  }    // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数  // 值为该元素在表中的位置，否则为0。   int Search_Bin(SSTable ST,KeyType key)  {      int low, high, mid;    low = 1; // 置区间初值     high = ST.length;    while(low <= high)    {      mid = (low + high) / 2;      if(key == ST.elem[mid].key) // 找到待查元素         return mid;      else if(key < ST.elem[mid].key)        high = mid - 1;   // 继续在前半区间进行查找       else        low = mid + 1;   // 继续在后半区间进行查找     }    return 0; // 顺序表中不存在待查元素   }    // 按顺序对ST的每个元素调用函数Visit()一次且仅一次。  int Traverse(SSTable ST,void(*Visit)(ElemType))  {      ElemType *p;    int i;        p = ++ST.elem; // p指向第一个元素,第0个元素没有用     for(i = 1; i <= ST.length; i++)      Visit( *p++ );        return 1;  }    void print(ElemType c) // Traverse()调用的函数   {    printf("(%d %d) ", c.key, c.others);  }    int main()  {    SSTable st;    int i;    KeyType s;        Creat_Ord(&st, N); // 由全局数组产生非降序静态查找表st     Traverse(st,print); // 顺序输出非降序静态查找表st       printf("\n请输入待查找值的关键字: ");    scanf("%d", &s);    i = Search_Bin(st, s); // 折半查找有序表     if( i )      print(st.elem[i]);    else      printf("没找到.\n");      Destroy(&st);    system("pause");    return 0;  }    /*  输出效果：    (5 1) (13 2) (19 3) (21 4) (37 5) (56 6) (64 7) (75 8) (80 9) (88 10) (92 11)  请输入待查找值的关键字: 75  (75 8) 请按任意键继续. . .     */

运行结果如下：

关于C语言中怎么实现折半查找就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。