数据结构课程设计-哈希表设计.doc
12页
哈希表设计一． 需求分析1.1 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过 R，完成相应的建立和查表程序.1.2 人名为汉语拼音形式，最长不超过 19 个字符(如：庄双双 zhuangshuangshuang).1.3 假设待填入哈希表的人名有 30 个，平均查找长度为 2哈希表用除留余数法构造，用伪随机探测在散列法处理冲突1.4 测试数据:1)输入数据:zengqinhui,mayuelong,chenzhicheng,sunpeng,wanghui,liqingbo,liujunpeng,jiangquanlei,xingzhengchuan,luzhaoqian,gaowenhu,zhuhaoyin,chenlili,wuyunyun,huangjuanxia,wangyan,zhoutao,jiangzhenyu,liuxiaolong,wangziming,fengjunbo,lilei,wangjia,zhangjianguo,zhuqingqing,huangmin,haoyuhan,zhoutao,zhujiang,lixiaojun.2)D. 显示哈希表地址 关键字 搜索长度 H（key） 姓名0 0 1 0 （null）1 1505 1 1 xingzhengchuan2 1083 1 2 wangziming3 755 1 3 wanghui4 991 1 4 zhuhaoyin5 757 1 5 wangyan6 1272 2 3 jiangquanlei7 853 1 7 liqingbo8 1089 1 8 liujunpeng9 855 1 9 huangmin10 527 1 10 lilei11 0 12 0 (null)12 979 3 39 lixiaojun13 1084 3 3 luzhaoqian14 1283 1 14 huangjuanxia15 861 1 15 haoyuhan16 768 1 16 sunpeng17 0 0 0 18 1193 1 18 zengqinghui19 862 2 16 gaowenhu20 1195 1 20 liuxiaolong21 1196 1 21 jiangzhenhu22 1285 2 16 zhangjianguo23 864 2 18 zhujiang24 0 0 025 0 0 0数据结构课程设计（哈希表设计）126 778 1 26 zhuotao27 958 2 18 fengjunbo28 0 0 029 0 0 030 1205 1 30 zhuqingqing31 0 0 032 737 1 32 wangjia33 0 0 034 0 0 035 778 2 26 zhuotao36 0 0 037 977 1 37 mayuelong38 0 0 039 932 1 39 wuyunyun40 1262 1 40 chenzhicheng41 840 1 41 chenlili42 0 0 043 0 0 044 0 0 045 0 0 046 0 0 047 0 0 048 0 0 049 0 0 0平均查找长度：ASL（30）= 1.F. 查找请输入姓名的拼音：wangjia结果：姓名：wangjia 关键字：737 查找长度为：1请输入姓名的拼音：luzhaoqian结果：姓名：luzhaoqian 关键字：1084 查找长度为：3请输入姓名的拼音：luzhao结果：无此记录Q. 退出 y结果：Press ang key to continue二. 概要设计2.1 基本操作void InitNameList() 姓名（结构体数组）初始化操作结果：名字以拼音的形式够成字符串，将字符串的各个字符所对应的 ASCII 码相加，所得的整数做为哈希表的关键字。
void CreateHashList() 建立哈希表 操作结果：（1） 用除留余数法构建哈希函数数据结构课程设计（哈希表设计）2（2） 用伪随机探测再散列法处理冲突void FindList() 查找哈希表操作结果：在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度void Display() 操作结果：显示哈希表的的格式：\n 地址\t 关键字\t\t 搜索长度\tH(key)\t 姓名\nvoid main() 主函数设计 操作结果：主函数显示格式：D. 显示哈希表\nF. 查找\nQ. 退出\n 请选择：2.2 主程序Void main(){初始化；While（命令！=退出）{接受命令；处理命令；}}2.3 模块调用关系三． 详细设计3.1 存储结构设计typedef struct { char *py; //名字的拼音int k; //拼音所对应的整数}NAME;typedef struct //哈希表{ char *py; //名字的拼音主函数模块初始化模块 哈希表模块 查找模块 显示模块数据结构课程设计（哈希表设计）3int k; //拼音所对应的整数int si; //查找长度}HASH;3.2 姓名（结构体数组）初始化名字以拼音的形式够成字符串，将字符串的各个字符所对应的 ASCII 码相加，所得的整数做为哈希表的关键字。
void InitNameList() { char *f;int r,s0,i;NameList[0].py="zengqinghui";NameList[1].py="mayuelong";NameList[2].py="chenzhicheng";NameList[3].py="sunpeng";NameList[4].py="wanghui";NameList[5].py="liqingbo";NameList[6].py="liujunpeng";NameList[7].py="jiangquanlei";NameList[8].py="xingzhengchuan";NameList[9].py="luzhaoqian";NameList[10].py="gaowenhu";NameList[11].py="zhuhaoyin";NameList[12].py="chenlili";NameList[13].py="wuyunyun";NameList[14].py="huangjuanxia";NameList[15].py="wangyan";NameList[16].py="zhoutao";NameList[17].py="jiangzheny。
