k_search.java

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

/* =============== Program Description =============== */
/* 程序名称： k_search.c                               */
/* 程序目的： 运用余数法做为散列函数及链表解决法解 */
/*            决散列碰撞解决法设计散列表。             */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#include <stdlib.h>
#define Max	6
#define HashMax 5
int Data[Max] = { 1, 13, 20, 5, 12, 33};    /* 数据阵列 */
struct List				/* 宣告串列结构 */
{
	int		Key;		/* 键值 */
	struct  List	*Next;		/* 下一个节点 */
};
typedef struct List Node;
typedef Node *Link;

Node	HashTab[HashMax];	/* 散列表 */
int 	Counter = 1;	/* 计数器 */

/* --------------------------------------------------- */
/* 散列函数之余数法                                    */
/* --------------------------------------------------- */
int Hash_Mod(int Key)
{

	return Key % HashMax ;	/* 返回 键值除以散列表大小取余数 */

}

/* --------------------------------------------------- */
/* 建立散列表                                          */
/* --------------------------------------------------- */
void Create_Hash(int Key)
{
	Link	Pointer;	/* 链表指针 */
	Link	New;		/* 新链表指针 */
	int	Index;		/* 散列索引 */

	New = ( Link ) malloc(sizeof(Node));	/* 存储空间配置 */
	New->Key = Key;				/* 键值	*/
	New->Next = NULL;			/* 指向结束指针 */

	Index = Hash_Mod(Key);			/* 取得数据位置 */
	Pointer = HashTab[Index].Next;		/* 散列表起始指针 */
	if ( Pointer != NULL )			/* 指针没指向结束指针时 */
	{
		New->Next = Pointer;		/* 指向上一个指针 */
		HashTab[Index].Next = New;	/* 散列表指针指向此新指针 */
	}
	else
		HashTab[Index].Next = New;	/* 散列表指针指向此新指针 */
}

/* --------------------------------------------------- */
/* 散列查找法                                          */
/* --------------------------------------------------- */
int Hash_Search(int Key)
{
	Link	Pointer;	/* 链表指针 */
	int	Index;		/* 散列索引 */

	Counter = 0;
	Index = Hash_Mod(Key);			/* 取得数据位置 */
	Pointer = HashTab[Index].Next;		/* 散列表起始指针 */
	printf("Data[%d] : ",Index);

	while ( Pointer != NULL )		/* 指针指向结束指针时终止循环 */
	{
		Counter++;
		printf("[%d]",Pointer->Key);
		if ( Pointer->Key == Key )	/* 查找到数据 */
			return 1;
		else				/* 往下一个指针查找 */
			Pointer = Pointer->Next;	/* 指向下一个指针 */
	}
	return 0;
}

/* --------------------------------------------------- */
/* 主程序                                              */
/* --------------------------------------------------- */
void main ()
{
	int		KeyValue;	/* 欲查找数据变量 */
	int		Index;		/* 输入数据索引 */
	Link    Pointer;
	int i;

	Index = 0;

	printf("Input Data : ");	/* 输出输入数据 */
	for ( i=0;i<Max;i++ )
		printf("[%d]",Data[i]);
	printf("\n");

	while ( Index < Max )		/* 建立散列表 */
	{
		Create_Hash(Data[Index]);
		Index++;
	}

	for ( i=0;i<HashMax;i++ )	/* 输出散列表数据 */
	{
		printf("HashTab[%d] : ",i);
		Pointer = HashTab[i].Next;
		while ( Pointer != NULL )
		{
			if ( Pointer->Key > 0 )
				printf("[%d]",Pointer->Key);
			Pointer = Pointer->Next;
		}
		printf("\n");
	}

	while ( KeyValue != -1 )	/* 输入-1结束程序 */
	{
	printf("Please enter your key value : ");
	scanf("%d",&KeyValue);

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