哈希表的设计与实现

哈希表的设计与实现

课程设计任务书

学生姓名： 专业班级：

指导教师： 工作单位：

题 目: 哈希表的设计与实现

初始条件：

针对某个集体（比如你所在的班级）中的“人名”设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

（1）假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的

上限为2。

（2）哈希函数用除留余数法构造

（3）用伪随机探测再散列法处理冲突。

（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p166。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：

1. 问题描述

简述题目要解决的问题是什么。

2. 设计

存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；

3. 调试报告

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4. 经验和体会（包括对算法改进的设想）

5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这

些测试数据和运行输出。

说明：

1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。

时间安排：

1、第19周完成。

2、6月30日下午-7月1日在实验中心检查程序、交课程设计报告、源程序（U盘）。

指导教师签名： 2011年6月22日

哈希表的设计与实现

系主任（或责任教师）签名： 年 月 日

1问题描述

1.1问题描述

针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长

度不超过R，完成相应的建表和查表程序。

1.2基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查

找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。

2设计

2.1存储结构设计

typedef struct

{ char *py; //名字的拼音

int k; //拼音所对应的整数

}NAME;

typedef struct //哈希表

{ char *py; //名字的拼音

int k; //拼音所对应的整数

int si; //查找长度

}HASH;

2.2主要算法设计

2.2.1 姓名（结构体数组）初始化

名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的

整数做为哈希表的关键字。

void InitNameList()

{ char *f;

int r,s0,i;

NameList[0].py="zhouyulin";

NameList[1].py="chengjianfeng";

NameList[2].py="qinxudong";

哈希表的设计与实现

NameList[3].py="fangxin";

NameList[4].py="yangzongcheng";

NameList[5].py="tangxuewei";

NameList[6].py="sunjie";

NameList[7].py="chentao";

NameList[8].py="chendehui";

NameList[9].py="xubiao";

NameList[10].py="chenxiaokun";

NameList[11].py="xuyulin";

NameList[12].py="huwei";

NameList[13].py="yehanfan";

NameList[14].py="changzhen";

NameList[15].py="zhoupenghui";

NameList[16].py="liweipeng";

NameList[17].py="gengguangzhen";

NameList[18].py="weikaikai";

NameList[19].py="leiyutian";

NameList[20].py="wangwei";

NameList[21].py="liumingxi";

NameList[22].py="nvchunqiu";

NameList[23].py="congxiaofei";

NameList[24].py="weitaifei";

NameList[25].py="guijie";

NameList[26].py="huangliang";

NameList[27].py="mahuizhi";

NameList[28].py="huye";

NameList[29].py="shengxianqin";

for(i=0;i<NAME_NO;i++)

{ s0=0;

f=NameList[i].py;

for(r=0;*(f+r)!='\0';r++) */将字符串的各个字符所对应的ASCII码相加，所得的整数做

为哈希表的关键字*/

s0=*(f+r)+s0;

NameL

ist[i].k=s0;

}

}

2.2.2 建立哈希表

（1） 用除留余数法构建哈希函数

（2） 用伪随机探测再散列法处理冲突

void CreateHashList()

哈希表的设计与实现

{ int i;

for(i=0; i<HASH_LENGTH;i++)

{ HashList[i].py="";

HashList[i].k=0;

HashList[i].si=0;

}

for(i=0;i<HASH_LENGTH;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;

}

}

}

2.2.3查找哈希表

在哈希表中进行查找，输出查找的结果 …… 此处隐藏：6553字，全部文档内容请下载后查看。喜欢就下载吧 ……