哈希表

数据结构课程设计报告

题目: 哈希表设计

院 系： 班 级：

姓 名： 学 号：

指导教师：

一、需求分析

1.针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。

2.人名为汉语拼音形式，最长不超过19个字符 (如：庄双双Zhang Shuangshuang)。 3.设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用

伪随机探测在散列法处理冲突。

4.查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。 二、概要设计

1.哈希表的抽象数据类型定义: ADT HashList{

数据对象：D是相同类型元素构成的结合。 数据关系：R={集合内的元素之间是松散关系} 基本操作： InitNameTable()

操作结果：初始姓名表 CreateHashTable() 操作结果：创建哈希表 DisplayHashTable() 操作结果：显示哈希表 FindName()

操作结果：查找元素 DisplayNameTable() 操作结果：显示姓名表 } ADT HashList 2.本程序包含两个模块 1）主程序模块： void main ( ) { 初始化； Swith （ ） {

接受命令； 处理命令；

} }

2）哈希表单元模块——实现哈希表的抽象数据类型；

各模块的关系如下： 主程序模块

哈希表单元模块

三、详细设计

1. 元素类型，结点类型 typedef struct //姓名表

{

char *py; //名字的拼音 int m; //拼音所对应的整数

} NAME;

typedef struct //哈希表 {

char *py; //名字的拼音

int m; //拼音所对应的ASCII总和 int si; //查找长度

} HASH; 2. 姓名表的初始化

void InitNameTable() {

NameTable[0].py=\"louyuhong\"; NameTable[1].py=\"shenyinghong\"; NameTable[2].py=\"wangqi\"; NameTable[3].py=\"zhuxiaotong\"; NameTable[4].py=\"zhataotao\"; NameTable[5].py=\"chenbinjie\"; NameTable[6].py=\"chenchaoqun\"; NameTable[7].py=\"chencheng\"; NameTable[8].py=\"chenjie\"; NameTable[9].py=\"chenweida\";

NameTable[10].py=\"shanjianfeng\"; NameTable[11].py=\"fangyixin\"; NameTable[12].py=\"houfeng\"; NameTable[13].py=\"hujiaming\"; NameTable[14].py=\"huangjiaju\"; NameTable[15].py=\"huanqingsong\"; NameTable[16].py=\"jianghe\"; NameTable[17].py=\"jinleicheng\"; NameTable[18].py=\"libiao\"; NameTable[19].py=\"liqi\"; NameTable[20].py=\"lirenhua\"; NameTable[21].py=\"liukai\"; NameTable[22].py=\"louhanglin\"; NameTable[23].py=\"luchaoming\"; NameTable[24].py=\"luqiuwei\"; NameTable[25].py=\"panhaijian\"; NameTable[26].py=\"shuxiang\"; NameTable[27].py=\"suxiaolei\"; NameTable[28].py=\"sunyubo\"; NameTable[29].py=\"wangwei\";

for (i=0;i的整数做为哈希表的关键字

{

int s=0;

char *p=NameTable[i].py;

for (j=0;*(p+j)!='\\0';j++) s+=toascii(*(p+j)); NameTable[i].m=s; } }

3. 建立哈希表

void CreateHashTable() {

for(i=0;iHashTable[i].py=\"\\0\"; HashTable[i].m =0; HashTable[i].si=0; }

for(i=0;iint sum=1,j=0;

int adr=(NameTable[i].m)%P; //除留余数法 H(key)=key MOD p,p<=m if(HashTable[adr].si==0) //如果不冲突，将姓名表赋值给哈希表 {

HashTable[adr].m =NameTable[i].m; HashTable[adr].py=NameTable[i].py; HashTable[adr].si=1; }

else //如果冲突 {

while(HashTable[adr].si!=0) {

adr=(adr+d[j++])%HASH_LEN;

//伪随机探测再散列法处理冲突

sum=sum+1; //查找次数加1 }

HashTable[adr].m =NameTable[i].m; //将姓名表复制给哈希表对应

的位置上

HashTable[adr].py=NameTable[i].py;

HashTable[adr].si=sum; } } }

4. 显示姓名表与哈希表 void DisplayNameTable() {

printf(\"\\n地址 \\ 姓名 \\ 关键字\\n\"); for (i=0;iprintf(\"%2d %18s \\ %d \\n\}

void DisplayHashTable() {

float asl=0.0;

printf(\"\\n\\n 地址 \\ 姓名 \\ 关键字 \ 搜索长度\\n\"); //显示的格式 for (i=0;iprintf(\"%2d

%18s

\\

\\ %d\\n\ asl+=HashTable[i].si; }

asl/=NAME_LEN; //求得ASL printf(\"\\n\\n平均查找长度：ASL(%d)=%f \\n\}

5. 姓名查找 void FindName() {

char name[20]={0}; int s=0,sum=1,adr;

printf(\"\\n请输入想要查找的姓名的拼音:\");

%d

scanf(\"%s\

for (j=0;j<20;j++) //求出姓名的拼音所对应的ASCII作为关键字 s+=toascii(name[j]);

adr=s%P; //除留余数法 j=0;

if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)) //分3种情况进行判

断，并输出超找结果

printf(\"\\n姓名:%s 关键字:%d 查找长度为: 1\\n\ else if (HashTable[adr].m==0)

printf(\"没有想要查找的人!\\n\"); else {

while(1) {

adr=(adr+d[j++])%HASH_LEN; //伪随机探测再散列法处理冲突 sum=sum+1; //查找次数加1 if(HashTable[adr].m==0) {

printf(\"没有想要查找的人!\\n\"); break; }

if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py,name)) {

printf(\"\\n

姓

名

:%s

关

键

字

:%d

查

找

长度

为:%d\\n\

break; } } } }

四、调试分析

1．开始的时候在创建哈希表的时候总是得不到相应的结果，最后发现原来是在InitNameTable函数中的i重复利用，使得结果混乱了，为解决这个问题将该函数中的for语句的i改为j，避免与外for的i发生混乱使用。1

2.本次实验采取数据抽象的处理方法，将程序分为两个模块，设计时思路清晰，使得调试时也比较顺利。 五、用户手册

1.本程序的运行环境为DOS操作系统，执行文件为5.exe：。

2.进入演示程序后，即显示文本方式的用户界面。有4种操作可选择。 3.选择操作1：程序根据当前的姓名表将姓名输出，同时输出相应的关键字。 4.选择操作2：将程序建好的哈希表显示出来。

5.选择操作3：查找学生姓名。若查找成功，则输出此学生的姓名以及查找长度。 6.选择操作4：程序结束。 六、测试结果