数据结构

根据给出的代码段，补充一个哈希查找的程序，在该段程序中冲突解决方法为：双散列函数探查法哈希函数关键字为：人名字母ASCII相加哈希函数为：关键字%M，从而映射到哈希表中的位置。**请注意看注释！！再补充完成查找的过程**。图中第1行为输入，第3行为输出（标点为半角符号）。

分数:

请勿频繁操作

#include<stdio.h>
#include<string.h>

#define HASH_LEN 50 //哈希表的长度
#define M 47 //随机数
#define NAME_NO 30 //人名的个数

typedef struct
{
	char *name_py; //名字的拼音
	int value; //拼音所对应的整数
} NAME;

NAME NameList[HASH_LEN]; //全局变量NAME

typedef struct //哈希表
{
	char *name_py; //名字的拼音
	int value; //拼音所对应的整数
	int SearchLength; //查找长度
} HASH;

HASH HashList[HASH_LEN]; //全局变量HASH

void InitNameList() //姓名（结构体数组）初始化
{
	char *ch_temp;
	int i, j;
	int sl_temp;

	NameList[0].name_py = "wanghui";
	NameList[1].name_py = "mayuelong";
	NameList[2].name_py = "chenzhicheng";
	NameList[3].name_py = "sunpeng";
	NameList[4].name_py = "zengqinghui";
	NameList[5].name_py = "liqingbo";
	NameList[6].name_py = "liujunpeng";
	NameList[7].name_py = "jiangquanlei";
	NameList[8].name_py = "xingzhengchuan";
	NameList[9].name_py = "luzhaoqian";
	NameList[10].name_py = "gaowenhu";
	NameList[11].name_py = "zhuhaoyin";
	NameList[12].name_py = "chenlili";
	NameList[13].name_py = "wuyunyun";
	NameList[14].name_py = "huangjuanxia";
	NameList[15].name_py = "wangyan";
	NameList[16].name_py = "zhoutao";
	NameList[17].name_py = "jiangzhenyu";
	NameList[18].name_py = "liuxiaolong";
	NameList[19].name_py = "wangziming";
	NameList[20].name_py = "fengjunbo";
	NameList[21].name_py = "lilei";
	NameList[22].name_py = "wangjia";
	NameList[23].name_py = "zhangjianguo";
	NameList[24].name_py = "zhuqingqing";
	NameList[25].name_py = "huangmin";
	NameList[26].name_py = "haoyuhan";
	NameList[27].name_py = "zhoutao";
	NameList[28].name_py = "zhujiang";
	NameList[29].name_py = "lixiaojun";

	for (i = 0; i < NAME_NO; i++)
	{
		sl_temp = 0;
		ch_temp = NameList[i].name_py;
		for (j = 0; *(ch_temp + j) != '\0'; j++)
		{
			sl_temp = sl_temp + *(ch_temp + j);
		}
		NameList[i].value = sl_temp;
	}
}

void CreateHashList() //建立哈希表
{
	int i, sum, address, readdress;

	for (i = 0; i < HASH_LEN; i++)
	{
		HashList[i].name_py = "";
		HashList[i].value = 0;
		HashList[i].SearchLength = 0;
	}

	for (i = 0; i < NAME_NO; i++)
	{
		sum = 0;
		address = (NameList[i].value) % M; //哈希函数
		readdress = address;
		if (HashList[address].SearchLength == 0) //如果不冲突
		{
			HashList[address].value = NameList[i].value;
			HashList[address].name_py=NameList[i].name_py;
			HashList[address].SearchLength=1;
		}
		else //冲突
		{
			do
			{
				readdress =(readdress + NameList[i].value % 10 + 1) % M; //伪随机探测再散列法处理冲突
				sum = sum + 1; 				//查找次数加1
			} while (HashList[readdress].value != 0);
			HashList[readdress].value = NameList[i].value;
			HashList[readdress].name_py = NameList[i].name_py;
			HashList[readdress].SearchLength = sum + 1;
		}
	}
}

void FindList() //查找
{
	char name[20] = {0};
	int i, value = 0, sum=1, address;

	printf("请输入姓名的拼音:");
	scanf("%s", name);
	printf("Output:\n");
	for (i = 0; name[i] != '\0'; i++) //求出姓名的拼音所对应的整数(关键字)
	{
		value += name[i];
	}
	/******start******/

	/******end******/
}

void Display() //显示哈希表
{
	int i;
	float average = 0;
	printf("\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n"); //显示的格式
	for (i = 0; i < HASH_LEN; i++)
	{
		printf("%d",i);
		printf("\t%d", HashList[i].value);
		printf("\t\t%d",HashList[i].SearchLength);
		printf("\t\t%d",HashList[i].value % M);
		printf("\t%s",HashList[i].name_py);
		printf("\n");
	}
	for (i = 0; i < HASH_LEN; i++)
	{
		average += HashList[i].SearchLength;
	}
	average /= NAME_NO;
	printf("\n平均查找长度：ASL(%d)=%f\n", NAME_NO, average);
}

int main()
{
	InitNameList();
	CreateHashList();

	FindList();
	
	return 0;
}

#include<stdio.h>
#include<string.h>

#define HASH_LEN 50 //哈希表的长度
#define M 47 //随机数
#define NAME_NO 30 //人名的个数

typedef struct
{
	char *name_py; //名字的拼音
	int value; //拼音所对应的整数
} NAME;

NAME NameList[HASH_LEN]; //全局变量NAME

typedef struct //哈希表
{
	char *name_py; //名字的拼音
	int value; //拼音所对应的整数
	int SearchLength; //查找长度
} HASH;

HASH HashList[HASH_LEN]; //全局变量HASH

void InitNameList() //姓名（结构体数组）初始化
{
	char *ch_temp;
	int i, j;
	int sl_temp;

	NameList[0].name_py = "wanghui";
	NameList[1].name_py = "mayuelong";
	NameList[2].name_py = "chenzhicheng";
	NameList[3].name_py = "sunpeng";
	NameList[4].name_py = "zengqinghui";
	NameList[5].name_py = "liqingbo";
	NameList[6].name_py = "liujunpeng";
	NameList[7].name_py = "jiangquanlei";
	NameList[8].name_py = "xingzhengchuan";
	NameList[9].name_py = "luzhaoqian";
	NameList[10].name_py = "gaowenhu";
	NameList[11].name_py = "zhuhaoyin";
	NameList[12].name_py = "chenlili";
	NameList[13].name_py = "wuyunyun";
	NameList[14].name_py = "huangjuanxia";
	NameList[15].name_py = "wangyan";
	NameList[16].name_py = "zhoutao";
	NameList[17].name_py = "jiangzhenyu";
	NameList[18].name_py = "liuxiaolong";
	NameList[19].name_py = "wangziming";
	NameList[20].name_py = "fengjunbo";
	NameList[21].name_py = "lilei";
	NameList[22].name_py = "wangjia";
	NameList[23].name_py = "zhangjianguo";
	NameList[24].name_py = "zhuqingqing";
	NameList[25].name_py = "huangmin";
	NameList[26].name_py = "haoyuhan";
	NameList[27].name_py = "zhoutao";
	NameList[28].name_py = "zhujiang";
	NameList[29].name_py = "lixiaojun";

	for (i = 0; i < NAME_NO; i++)
	{
		sl_temp = 0;
		ch_temp = NameList[i].name_py;
		for (j = 0; *(ch_temp + j) != '\0'; j++)
		{
			sl_temp = sl_temp + *(ch_temp + j);
		}
		NameList[i].value = sl_temp;
	}
}

void CreateHashList() //建立哈希表
{
	int i, sum, address, readdress;

	for (i = 0; i < HASH_LEN; i++)
	{
		HashList[i].name_py = "";
		HashList[i].value = 0;
		HashList[i].SearchLength = 0;
	}

	for (i = 0; i < NAME_NO; i++)
	{
		sum = 0;
		address = (NameList[i].value) % M; //哈希函数
		readdress = address;
		if (HashList[address].SearchLength == 0) //如果不冲突
		{
			HashList[address].value = NameList[i].value;
			HashList[address].name_py=NameList[i].name_py;
			HashList[address].SearchLength=1;
		}
		else //冲突
		{
			do
			{
				readdress =(readdress + NameList[i].value % 10 + 1) % M; //伪随机探测再散列法处理冲突
				sum = sum + 1; 				//查找次数加1
			} while (HashList[readdress].value != 0);
			HashList[readdress].value = NameList[i].value;
			HashList[readdress].name_py = NameList[i].name_py;
			HashList[readdress].SearchLength = sum + 1;
		}
	}
}

void FindList() //查找
{
	char name[20] = {0};
	int i, value = 0, sum=1, address;

	printf("请输入姓名的拼音:");
	scanf("%s", name);
	printf("Output:\n");
	for (i = 0; name[i] != '\0'; i++) //求出姓名的拼音所对应的整数(关键字)
	{
		value += name[i];
	}
	/******start******/

	/******end******/
}

void Display() //显示哈希表
{
	int i;
	float average = 0;
	printf("\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n"); //显示的格式
	for (i = 0; i < HASH_LEN; i++)
	{
		printf("%d",i);
		printf("\t%d", HashList[i].value);
		printf("\t\t%d",HashList[i].SearchLength);
		printf("\t\t%d",HashList[i].value % M);
		printf("\t%s",HashList[i].name_py);
		printf("\n");
	}
	for (i = 0; i < HASH_LEN; i++)
	{
		average += HashList[i].SearchLength;
	}
	average /= NAME_NO;
	printf("\n平均查找长度：ASL(%d)=%f\n", NAME_NO, average);
}

int main()
{
	InitNameList();
	CreateHashList();

	FindList();
	
	return 0;
}