/*名称：折半查找 语言：数据结构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;
}// 在有序表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;		// 继续在前半区间进行查找 elselow = 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]);elseprintf("没找到.\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) 请按任意键继续. . . */ 

运行结果如下：