2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
福建工程学院 课程设计 课程：算法与数据结构 题目：9.哈希表设计 专业：计算机科学与技术 班级： 0702 座号： 20 姓名：XXXX 2009年9月11日 1 实验题目：哈希表设计 一、要解决的问题 任务：针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为重点字设计哈希表，并达成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再 散列法或链地点法办理矛盾；在查找的过程中给出比较的次数。达成按姓名查问的操作。 二、算法基本思想描绘： 散列是一种存储策略，散列表也叫哈希表，是鉴于散列存储策略成立的查找表。基本思想是确定一个函数，求得每个重点码相应的函数值并以此作为存储地点，直接将该数据元素存入到相应的地点空间去，因此它的查找效率很高。 本次设计采用除留余数法建立哈希函数，用伪随机探测再散列法办理矛盾，达到建表查表查察学生通讯录信息。 三、设计 1.数据结构的设计 所用函数如下： voidchash( )/*建哈希表*/ voidfindhlist( )/*查找信息函数*/ voidinput( )/*输入信息表*/ voiddishash( )/*显示哈希表,哈希表的属性*/ intmain( )/*主函数*/ 1）基本表数据结构 基本表是存储同班级学生的全部通讯信息，是最原始的信息表。包含姓名拼音、学号、 电话号码等属性。 原始表结构定义如下： #defineL50/*哈希表长*/ structold { charpy[20]; intk; charnumber[20]; charphone[20]; }; structoldoldlist[L]; 2）哈希表数据结构：structhterm { charpy[20]; 2 intk; intsi; charnumber[20]; charphone[20]; }; structhtermhlist[L];/*哈希表*/ 算法的设计 （1）建立哈希函数 哈希函数用除留余数法结构，Hash（key）=key%p，其中，p是一个整数，即重点码除 以p的余数作为散列地点。使用这种方法建立哈希函数，选用合适的p很重要，本设计用L表示哈希表长，M来表示p值，那么M应小于等于L,且靠近L或许等于M。P一般选用为小于L的最大质数，也能够是不包含小于20质因子的合数。 memset(hlist,0,sizeof(hlist));/*将结构体全部置为0*/ for(i=0;iN;i++)/*哈希函数用除留余数法结构*/ {sum=0; adr=(oldlist[i].k)%M;/*定义一个p值,用m来表示,它应当=L*/ d=adr; if(hlist[adr].si==0) {hlist[adr].k=oldlist[i].k; strcpy(hlist[adr].py,oldlist[i].py); strcpy(hlist[adr].phone,oldlist[i].phone); strcpy(hlist[adr].number,oldlist[i].number); hlist[adr].si=1; } } 当不同的重点码映射到同一个散列地点上时，发生矛盾。此时用伪随机探测再散列法办理矛盾。 else { do { d=(d+(oldlist[i].k)%10+1)%M; sum=sum+1; }while(hlist[d].k!=0);hlist[d].k=oldlist[i].k;strcpy(hlist[d].py,oldlist[i].py);strcpy(hlist[d].phone,oldlist[i].phone);strcpy(hlist[d].number,oldlist[i].number); hlist[d].si=sum+1;/*计数*/ } （2）信息表插入数据 用一个二维数组py[30][20]寄存30名学生的姓名（用拼音的形式），因为是同班同学，所以学号必为连号，为了方便起见，将学生的电话号码也设为连号方便信息录入。 3 #defineN30//定义名单表长，即学生人数 charstrTemp[N]; for(i=0;iN;i++) { strcpy(oldlist[i].py,py[i]); sprintf(strTemp,226431%02d,i+1); strcpy(oldlist[i].phone,strTemp); sprintf(strTemp,0702%02d,i+1); strcpy(oldlist[i].number,strTemp); } （3）查找信息函数 用数组Z[]寄存用户输入的重点字----姓名拼音，经过累加各个字母的ASCII码值合
