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

数据结构课程设计 学 院 计算机学院 专业班级 09网络工程 学 号 学生姓名 陈嘉奇 【实验一】 一．问题描述 1问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2.基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。 二. 需求分析 （1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。 （2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。 （3） 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 （4） 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。 （5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度 三．程序设计 1 .存储结构设计 typedef struct { char *py; //名字的拼音 int k; //拼音所对应的整数 }NAME; typedef struct //哈希表 { char *py; //名字的拼音 int k; //拼音所对应的整数 int si; //查找长度 }HASH; ） 名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 void InitNameList() { char *f; int r,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=fuzongkai; 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=quegaoxiang; 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].py=zhengyongbin; NameList[26].py=zhongminghua; NameList[27].py=chenliyan; NameList[28].py=liuxiaohui; NameList[29].py=panjinmei; for(i=0;iNAME_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) 建立哈希表 （1） 用除留余数