C语言数据结构之语言数据结构之 折半查找实例详解折半查找实例详解
数据结构数据结构 折半查找折半查找
实例代码：实例代码：
/*
名称：折半查找
语言：数据结构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;
资源评论
