哈希表设计.doc

:针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查表程序。基本要求:假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。(1)针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序。(2)人名为汉语拼音形式,最长不超过19个字符(如:庄双双zhuangshuangshuang)。(3)假设待填入哈希表的人名有30个,平均查找长度的上限为2。哈希表用除留余数法构造,用伪随机探测在散列法处理冲突。(4)在输入人名过程中能自动识别非法输入,并给与非法输入的反馈信息要求重新输入。(5)查找成功时,显示姓名及关键字,,需要顺序的抽象数据类型。ADTHash{数据对象D:D是具有相同特征的数据元素的集合。各数据元素均含有类型相同,可唯一标识的数据元素的关键字。数据关系:数据元素同属于一个集合。基本操作P:Creat(&ST,n);操作结果:构造一个含n个数据元素的静态查找表ST。Destroy(&ST)初始条件:静态查找表ST存在。操作结果::(ST,key)初始条件:静态查找表ST存在,key为和关键字类型相同的定值。操作结果:若ST中存在其关键字等于key的数据元素,则函数值为该数据元素的值或在表中的位置,否则为“空”。Insert(&h,key)初始条件:哈希表h存在。操作结果:若表中没有key,则在h中插入key。Hash(h,&k)初始条件:哈希表h存在。操作结果:通过除留余数法得到地址用k返回。:(1)主程序模块Main(){初始化;{接受命令;显示结果;}}(2)创建hash表的模块(3)查找hash表的模块(4)#include<>#include<>#include<>//#include #defineHASH_LEN50//哈希表的长度 #defineM47 #defineNAME_NO30//人名的个数 typedefstructNAME {char*py;//名字的拼音intk;//拼音所对应的整数}NAME;NAMENameList[HASH_LEN]; typedefstructhterm//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长度}HASH;HASHHashList[HASH_LEN]; /*-----------------------姓名(结构体数组)初始化---------------------------------*/voidInitNameList() {NameList[0].py="baojianbo";NameList[1].py="chenjiabin";NameList[2].py="chenxi";NameList[3].py="dinglin";NameList[4].py="fangzewei";NameList[5].py="fengpan";NameList[6].py="guidong";NameList[7].py="hanlijuan";NameList[8].py="haoxiaoju";NameList[9].py="heqing";NameList[10].py="jishaomei";NameList[11].py="jiyunfeng";NameList[12].py="jiangshanshan";NameList[13].py="lixuefei";NameList[14].py="lixueqin";NameList[15].py="liyuanxin";NameList[16].py="liangguannan";NameList[17].py="liuna";NameList[18].py="liupeiyu";NameList[19].py="nixiaodong";NameList[20].py="peixue";NameList[21].py="sunke";NameList[22].py="sunying";NameList[23].py="wanqishuai";NameList[24].py="wangna";NameList[25].py="linglei";NameList[26].py="xinnaping";NameList[27].py="xuyuanfei";NameList[28].py