数据结构课程设计--哈希表设计

《数据结构课程设计--哈希表设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计学院计算机学院专业班级09网络工程学号E30914020学生姓名陈嘉奇【实验一】一．问题描述1问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。2.基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。二.需求分析（1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双

2、zhuangshuangshuang)。（3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4）在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三．程序设计1.存储结构设计typedefstruct{char*py;//名字的拼音intk;//拼音所对应的整数}NAME;typedefstruct//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长

3、度}HASH;2.主要算法设计（1）姓名（结构体数组）初始化名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。voidInitNameList(){char*f;intr,s0,i;NameList[0].py="chenliang";NameList[1].py="chenyuanhao";NameList[2].py="chengwenliang";NameList[3].py="dinglei";NameList[4].py="fenghanzao";NameList[5].py="fuzo

4、ngkai";NameList[6].py="hujingbin";NameList[7].py="huangjianwu";NameList[8].py="lailaifa";NameList[9].py="lijiahao";NameList[10].py="liangxiaocong";NameList[11].py="linchunhua";NameList[12].py="liujianhui";NameList[13].py="luzhijian";NameList[14].py="luonan";NameList[15].py="qu

5、egaoxiang";NameList[16].py="sugan";NameList[17].py="suzhiqiang";NameList[18].py="taojiayang";NameList[19].py="wujiawen";NameList[20].py="xiaozhuoming";NameList[21].py="xujinfeng";NameList[22].py="yanghaichun";NameList[23].py="yeweixiong";NameList[24].py="zengwei";NameList[25].

6、py="zhengyongbin";NameList[26].py="zhongminghua";NameList[27].py="chenliyan";NameList[28].py="liuxiaohui";NameList[29].py="panjinmei";for(i=0;i

7、2)建立哈希表（1）用除留余数法构建哈希函数（2）用伪随机探测再散列法处理冲突voidCreateHashList(){inti;for(i=0;i

8、].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else/