8-2-3.txt

数据结构源程序

/*折半查找的基本运算与实现*/
#include <stdio.h>
#include <malloc.h>
typedef int keytype;
typedef struct
{
	keytype num;	
}datatype;
typedef struct
{
	datatype *data;
	int length;
}S_TBL;
int Binary_Search(S_TBL *tbl,keytype kx);
void main()
{
	int i,flag;
	keytype kx;
	S_TBL *tbl=(S_TBL *)malloc(sizeof(S_TBL));
	printf("please input table length:\n");
	scanf("%d",&(tbl->length));
	tbl->data=(datatype *)calloc( tbl->length, sizeof(datatype) );
	printf("\nplease input element:\n");
	for(i=1;i<=tbl->length;i++)
	{
		scanf("%d",&((tbl->data[i]).num));		
	}
	printf("\nplease input a value that you want to find:\n");
	scanf("%d",&kx);
	flag=Binary_Search(tbl,kx);
	if(flag==0)
	{
		printf("search failed!\n");
	}
	else
	{
		printf("place=%6d\n",flag);
	}
}
int Binary_Search(S_TBL *tbl,keytype kx)
{
	int low,high,mid,flag;
	flag=0;
	low=1;
	high=tbl->length;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(kx<tbl->data[mid].num)
		{
			high=mid-1;
		}
		else if(kx>tbl->data[mid].num)
		{
			low=mid+1;
		}
		else
		{
			flag=mid;
			break;
		}
	}
	return flag;
}