h_search.java

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

/* =============== Program Description =============== */
/* 程序名称： h_search.c                               */
/* 程序目的： 运用余数法做为散列函数及差值解决法解决杂 */
/*            凑碰撞解决法、设计散列表。               */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#define Max	6
#define HashMax 5
int Data[Max] = {   12,   160,  219,    522,   725,  9997};    /* 数据数组 */
int HashTab[HashMax];
int Counter = 1;	/* 计数器 */

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

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

}

/* --------------------------------------------------- */
/* 差值散列碰撞解决法                                  */
/* --------------------------------------------------- */
int Collision_Offset(int Address)
{
	int	Offset = 3;	/* 设差值为3 */

	return ( Address + Offset ) % HashMax;	
	/* 返回 旧地址加差值除以散列表大小取余数*/

}

/* --------------------------------------------------- */
/* 建立散列表                                          */
/* --------------------------------------------------- */
int Create_Hash(int Key)
{
	int	HashTime;	/* 散列次数 */
	int	CollisionTime;	/* 碰撞次数 */
	int	Address;	/* 数据地址 */
	int	i;

	HashTime = 0;
	CollisionTime = 0;
	Address = Hash_Mod(Key);	/* 调用散列函数 */
	while ( HashTime < HashMax )
	{
		if ( HashTab[Address] == 0 )	/* 可储存数据 */
		{
			HashTab[Address] = Key;
			printf("Key : %d => Address %d\n",Key,Address);
			for ( i=0;i<HashMax;i++)
			{
				printf("[%d]",HashTab[i]);
			}
			printf("\n");
			return 1;
		}
		else
		{
			CollisionTime++;
			printf("Collision %d => Address %d\n",CollisionTime,Address);
			Address = Collision_Offset(Address); /* 调用碰撞解决法 */
		}
		HashTime++;
	}
	return 0;
}

/* --------------------------------------------------- */
/* 散列查找法                                          */
/* --------------------------------------------------- */
int Hash_Search(int Key)
{
	int	Address;	/* 数据地址 */

	Counter = 0;
	Address = Hash_Mod(Key);	/* 调用散列函数 */
	while ( Counter < HashMax )
	{
		Counter++;
		if ( HashTab[Address] == Key )
			return 1;
		else
			Address = Collision_Offset(Address);/* 调用碰撞解决法 */
	}
	return 0;
}

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

	Index = 0;

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

	for ( i=0;i<HashMax;i++)	/* 散列表初始化 */
		HashTab[i] = 0;

	while ( Index < Max )
	{
		if ( Create_Hash(Data[Index]) )
			printf("Hash Success!!\n");	/* 散列建立成功 */
		else
			printf("Hash Fulled!!\n");	/* 散列建立失败 */
		Index++;
	}

	for ( i=0;i<HashMax;i++)	/* 输出散列表数据 */
	{
		printf("[%d]",HashTab[i]);
	}
	printf("\n");

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

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