【数据结构】折半查找

数据结构 折半查找


[plain] view plaincopy
/*  
    名称：折半查找   
    语言：数据结构C语言版   
    编译环境：VC++ 6.0  
    日期： 2014-3-26   
*/  
  
#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;  
}  
  
// 算法9.2 P220   
// 在有序表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) 请按任意键继续. . .   
  

*/   

运行结果：