问题描述
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
1.2基本要求
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
1.3需求分析
1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序.
2）人名为汉语拼音形式(如：庄双双 zhuangshuangshuang).
3）假设待填入哈希表的人名有30个，平均查找长度为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。
4）在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。
1.4详细设计
1）系统使用到的结构定义
/*————-线性表（1）数据结构定义————*/
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音对应的整数
}NAME;
NAME NAMELIST[NAMENUMBER];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
2）函数定义
/*———————–姓名（结构体数组）初始化———————————*/
void InitNameList()
{
NameList[0].py=”hanbiao”;
NameList[1].py=”dingjian”;
NameList[2].py=”linlukun”;
NameList[3].py=”wangshaowei”;
NameList[4].py=”taojun”;
NameList[5].py=”lijie”;
NameList[6].py=”shiyanqiang”;
NameList[7].py=”liuning”;
NameList[8].py=”modapeng”;
NameList[9].py=”guoqiang”;
NameList[10].py=”dudachhao”;
NameList[11].py=”zhangyingjie”;
NameList[12].py=”zhuhongbing”;
NameList[13].py=”ruanjiangyang”;
NameList[14].py=”dingyankun”;
NameList[15].py=”xiedajia”;
NameList[16].py=”zhengguolin”;
NameList[17].py=”chenwei”;
NameList[18].py=”yewei”;
NameList[19].py=”sundedong”;
NameList[20].py=”wanbinbin”;
NameList[21].py=”zhangliang”;
NameList[22].py=”gaopen”;
NameList[23].py=”xiaofan”;
NameList[24].py=”weijinchao”;
NameList[25].py=”weichunshui”;
NameList[26].py=”wangfei”;
NameList[27].py=”caojian”;
NameList[28].py=”zhushouyuan”;
NameList[29].py=”liwei”;
char *f;
int r,s0;
for (int i=0;i<NAME_NO;i++) //求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r) != ‘\0’;r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
/*———————–建立哈希表———————————*/
void CreateHashList()
{
for (int i=0; i<HASH_LEN;i++) //哈希表的初始化
{
HashList[i].py=””;
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; i<NAME_NO; i++)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //不冲突时
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突时
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪随机探测再散列法处理
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}
/*————————————-查找————————————*/
void FindList()
{
printf(“\n\n请输入姓名的拼音: “); //输入姓名
char name[20]={0};
scanf(“%s”,name);
int s0=0;
for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
int sum=1;
int adr=s0 % M; //使用哈希函数
int d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
printf(“\n姓名:%s 关键字:%d 查找长度为: 1”,HashList[d].py,s0);
else if (HashList[adr].k==0)
printf(“无该记录!”);
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪随机探测再散列法处理
sum=sum+1;
if (HashList[d].k==0)
{
printf(“无记录! “);
g=1;
}
if (HashList[d].k==s0)
{
printf(“\n姓名:%s 关键字:%d 查找长度为:%d”,HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
1.5测试分析
白盒：
查看代码完整性
黑盒：
测试是否可以正确的查找。
附 C语言实现源码
#include “stdafx.h”
#include <stdio.h>
#include<conio.h>
#include<string.h>
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*———————–姓名（结构体数组）初始化———————————*/
void InitNameList()
{
NameList[0].py=”hanbiao”;
NameList[1].py=”dingjian”;
NameList[2].py=”linlukun”;
NameList[3].py=”wangshaowei”;
NameList[4].py=”taojun”;
NameList[5].py=”lijie”;
NameList[6].py=”shiyanqiang”;
NameList[7].py=”liuning”;
NameList[8].py=”modapeng”;
NameList[9].py=”guoqiang”;
NameList[10].py=”dudachhao”;
NameList[11].py=”zhangyingjie”;
NameList[12].py=”zhuhongbing”;
NameList[13].py=”ruanjiangyang”;
NameList[14].py=”dingyankun”;
NameList[15].py=”xiedajia”;
NameList[16].py=”zhengguolin”;
NameList[17].py=”chenwei”;
NameList[18].py=”yewei”;
NameList[19].py=”sundedong”;
NameList[20].py=”wanbinbin”;
NameList[21].py=”zhangliang”;
NameList[22].py=”gaopen”;
NameList[23].py=”xiaofan”;
NameList[24].py=”weijinchao”;
NameList[25].py=”weichunshui”;
NameList[26].py=”wangfei”;
NameList[27].py=”caojian”;
NameList[28].py=”zhushouyuan”;
NameList[29].py=”liwei”;
char *f;
int r,s0;
for (int i=0;i<NAME_NO;i++) //求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r) != ‘\0’;r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
/*———————–建立哈希表———————————*/
void CreateHashList()
{
for (int i=0; i<HASH_LEN;i++) //哈希表的初始化
{
HashList[i].py=””;
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; i<NAME_NO; i++)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //不冲突时
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突时
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪随机探测再散列法处理
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}