o_search.java

已经编写好的数据结构课本程序可以减轻您的负担

/* =============== Program Description =============== */
/* 程序名称： o_search.c                               */
/* 程序目的： 设计插补查找法的程序。                   */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#define Max	20
int Data[Max] = {   12,   160,  219,    522,   725,
		   732,   739,  748,    755,   757,
		   958,   963,  1068,  1169,  1570,
		  2278,  5384,  8888,  9000,  9997};    /* 数据数组 */
int Counter = 1;	/* 计数器 */

/* --------------------------------------------------- */
/* 找出加强型插补查找的中间值                        */
/* --------------------------------------------------- */
int	FindRobust(int Low,int High,int Key)
{
	int	Gap;
	int	Num1;
	int	Num2;
	int	Num3;

	Gap = ceil ( sqrt( (float) High - (float) Low + 1.0 ) );
	Num1 = Low + Gap;
	Num2 = High - Gap;
	Num3 = Low + ( Key - Data[Low] ) * ( High - Low )
			/ ( Data[High] - Data[Low] );

	if ( Num1 >= Num2 )
		if ( Num2 >= Num3 )
			return Num2;	/* Num1 >= Num2 >= Num3 */
		else if ( Num1 >= Num3)
			return Num3;	/* Num1 >= Num3 >= Num2 */
		else
			return Num1;	/* Num3 >= Num1 >= Num2 */
	else if ( Num2 >= Num1 )
		if (  Num1 >= Num3 )	
			return Num1;	/* Num2 >= Num1 >= Num3 */
		else if ( Num3 >= Num1 )
			return Num3;	/* Num2 >= Num3 >= Num1 */
		else
			return Num2;	/* Num3 >= Num2 >= Num1 */
	return 0;
}

/* --------------------------------------------------- */
/* 插补查找法                                          */
/* --------------------------------------------------- */
int Interpolation_Search(int Key)
{
	int	Low;	/* 插补查找法左边界变量 */
	int	High;	/* 插补查找法右边界变量 */
	int	Middle;	/* 插补查找法中间数 */

	Low = 0;
	High = Max - 1;
	Middle = FindRobust(Low,High,Key);

	if ( Middle < Low )
		Middle = Low;
	if ( Middle > High )
		Middle = High;

	while ( Low <= High )
	{
		if ( Key < Data[Middle] )	/* 欲查找值较小 */
			High = Middle - 1;		/* 查找前半段	*/
		else if ( Key > Data[Middle] )	/* 欲查找值较大 */
			Low = Middle + 1;		/* 查找后半段	*/

		else if ( Key == Data[Middle] )	/* 查找到数据	*/
		{
			printf ("Data[%d] = %d\n",Middle,Data[Middle]);
			return 1;
		}
		if ( Low < High )
			Middle = FindRobust(Low,High,Key);
		if ( Middle < Low )
			Middle = Low;
		if ( Middle > High )
			Middle = High;
		Counter++;
	}
	return 0;
}

/* --------------------------------------------------- */
/* 主程序                                              */
/* --------------------------------------------------- */
void main ()
{
	int	KeyValue;	/* 欲查找数据变量 */

	printf("Please enter your key value : ");
	scanf("%d",&KeyValue);

	if ( Interpolation_Search(KeyValue) )
		printf("Search Time = %d\n",Counter);	/* 输出查找次数 */
	else
		printf("No Found!!\n");	/* 输出没有找到数据 */
}