f_search.java

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

/* =============== Program Description =============== */
/* 程序名称： f_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 Fib(int N)
{
	if (N <= 1)				/* 递归结束条件 */
		return N;
	else
		return Fib(N-1) + Fib(N-2);	/* 递归执行部分 */
}

/* --------------------------------------------------- */
/* 费氏查找法                                          */
/* --------------------------------------------------- */
int Fibonacci_Search(int n,int Key)
{
	int	Root;		/* 左边界变量 */
	int	Distance_1;	/* 上一个费氏数 */
	int	Distance_2;	/* 上二个费氏数（差值） */
	int	Temp;

	Root = Fib(n-1);
	Distance_1 = Fib(n-2);
	Distance_2 = Fib(n-3);

	do
	{
		if ( Key < Data[Root-1] )	/* 欲查找值较小 */
		{				/* 查找前半段	*/
			Root = Root - Distance_2;
			Temp = Distance_1;
			Distance_1 = Distance_2;
			Distance_2 = Temp - Distance_2;
		}
		else if ( Key > Data[Root-1] )	/* 欲查找值较大 */
		{				/* 查找后半段	*/
			Root = Root + Distance_2;
			Distance_1 = Distance_1 - Distance_2;
			Distance_2 = Distance_2 - Distance_1;
		}
		else if ( Key == Data[Root-1] )	/* 查找到数据	*/
		{
			printf ("Data[%d] = %d\n",Root-1,Data[Root-1]);
			return 1;
		}
		Counter++;
	}	while ( Distance_2 >= 0 );
	return 0;
}

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

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

	FinA = 1;
	while ( Fib(FinA) <= Max )
		FinA++;

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