数据结构实验八：折半查找

折半查找

1 实验目的

1. 通过编程实现折半查找算法，掌握顺序查找方法的理论原理和实现过程，从而加深对顺序查找方法的理解，提高这般查找方法的编程应用技巧。

2 实验内容

1. 编写一个程序，输出在顺序表（1,2,3,4,5,6,7,8,9,10）中采用这般查找方法查找关键字9的过程。

3 软件程序

main.cpp：

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#define MAXL 100		//最大长度
typedef int KeyType;	//定义关键字类型为int
typedef char InfoType;
typedef struct
{
	KeyType key;
	InfoType data;
}RecType;

void CreateList(RecType R[],KeyType keys[],int n)	//创建顺序表
{
	for (int i=0;i<n;i++)
	{
		R[i].key = keys[i];
	}
}
void DispList(RecType R[],int n)	//输出顺序表
{
	for(int i=0;i<n;i++)
	{
		printf("%d ",R[i]);
	}
}

int BinSearch(RecType R[],int n,KeyType k)
{
    int low = 0,high = n-1,mid;
	while (low<=high)
	{
		mid = (low+high)/2;
		if(k==R[mid].key)
			return mid+1;
		if(k<R[mid].key)
			high = mid - 1;
		else
			low = mid + 1;
	}
    return -1;
}

int main()
{
	RecType R[MAXL];
	KeyType k=9;
	int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;
	CreateList(R,a,n);			//建立顺序表
	printf("关键字序列:"); DispList(R,n);
	printf("查找%d的比较过程如下:\n",k);
	if ((i=BinSearch(R,n,k))!=-1)
		printf("元素%d的位置是%d\n",k,i);
	else
		printf("元素%d不在表中\n",k);
	return 1;
}

4 实验结果