i_search.java

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

/* =============== Program Description =============== */
/* 程序名称： i_search.c                               */
/* 程序目的： 设计插补查找法的程序。                   */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#define Max	20
int	Data[Max] = {  12,  16,  19,  22,  25,
				  32,  39,  48,  55,  57,
				  58,  63,  68,  69,  70,
				  78,  84,  88,  90,  97};	/* 数据数组 */
int Counter = 1;	/* 计数器 */

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

	Low = 0;
	High = Max - 1;
	Middle = Low + ( Key - Data[Low] ) * ( High - Low )
			 / ( Data[High] - Data[Low] );

	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 = Low + ( Key - Data[Low] ) * ( High - Low )
				 / ( Data[High] - Data[Low] );
		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");	/* 输出没有找到数据 */
}