哈希表的操作.docx

《哈希表的操作.docx》由会员分享，可在线阅读，更多相关《哈希表的操作.docx（18页珍藏版）》请在三一办公上搜索。

1、哈希表操作一目的1. 巩固和加深对哈希表的创建、查找、插入等方法理论知识的理解。2. 掌握建立哈希表的办法，本实验是采用的是除留余数法创建。3. 掌握哈希表解决冲突的办法，本实验用的是线性探测再散列的方法。4. 巩固对程序模块化设计的要求。二需求分析1. 对于哈希表的基本操作首先是要创建一个哈希表，哈希表的创建思想是由哈希函 数得到，本实验就采用了除留余数法创建哈希表。2. 创建好哈希表就需要在哈希表中插入元素，本实验是需要插入单词，所以需要调 用string函数库，通过每个单词的地址数来进行下一步的查找计划。当插入单词地址 已经存在时，就产生了冲突，因此需要采用线性探测再散列的方式来解决冲突

2、。3. 当哈希表插入单词完成之后便可以显示哈希表的存储情况，因此需要输出整个哈 孝士d希表04. 要想计算平均查找长度首先要对哈希表中的元素进行查找，当所有单词查找结 束，查找长度也得出。5. 要实现上诉需求，程序需要采用模块化进行设计。三概要设计1. 基本操作：void Initwordlist(int n) 初始化哈希表操作结果：以字符形式插入单词，将字符串的各个字符所对应的ASCII码相加， 所得的整数做为哈希表的关键字。void Createhashlist(int n) 创建哈希表，并插入单词操作结果：(1) 用除留余数法构建哈希函数；(2) 用线性探测再散列处理冲突。void fi

3、nd()查找哈希表中的单词操作结果：在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找 成功的平均查找长度。void printhash()显示哈希表操作结果：显示哈希表的存储情况：位置dtt关键字%-6dtt单词sn。float average()操作结果：计算出平均查找长度。void menu()菜单函数设计操作结果：显示格式：1向哈希表中插入单词(15)；2查找哈希表中的单词；3显示哈希表的存储情况；4计算哈希表的平均查找长度；5退出程序。int main()主程序设计操作结果：通过调用各个函数操作得到结果。四详细设计1.全局变量:#define HASH_LEN 15/ HA

4、SH_LEN长度定义为15#define M 13/取模质数M为132 .存储结构设计：WORD wordlistHASH_LEN;/全 局变量typedef struct char word15;/输入的单词int number;/单词所对应的整数WORD;typedef struct char *word;/存储输入的单词int number;/单词所对应的整数int numofseek;/查找的次数HASH;HASH hashlistHASH_LEN;/全 局变量3 .哈希表初始化void Initwordlist(int n)int i,j;char *w; /设立一个指针，指向单词的

5、地址for(i=0;in;i+) int sum=0; /存放单词地址printf(请输入第1%个单词(按回车结束)：，i+1);gets(wordlisti.word); /输入单词w=wordlisti.word; /取地址for(j=0;*(w+j)!=0;j+)/字符串的各个字符所对应的ASCII码 相加，所得的整数做为哈希表的关键字sum=sum+*(w+j);wordlisti.number=sum; /存入每个单词的存放地址，即关键字4.哈希表的创建void Createhashlist(int n)/创建哈希表，并插入单词 int i;for(i=0;iHASH_LEN;i+)

6、hashlisti.word=”;/输入单词hashlisti.number=0; /关键字hashlisti.numofseek=0; /查找次数for(i=0;in;i+) int address,sum=0;address=wordlisti.number%M; /除留余数法，将单词插入到 哈希表中if(hashlistaddress.numofseek=0)hashlistaddress.word=wordlisti.word;hashlistaddress.number=wordlisti.number;hashlistaddress.numofseek=1;else int d;

7、/d为冲突次数d=1;doaddress=(wordlisti.number+d)%M; /线性探测解决冲突 d+;sum+;while(hashlistaddress.numofseek!=0);hashlistaddress.word=wordlisti.word;hashlistaddress.number=wordlisti.number;hashlistaddress.numofseek=sum+1;5 .哈希表的查找void find()/查找哈希表中的单词char seek15,*p; /设置查找长度不超过表长int m=0,i=0,j=0,d=1;printf(-请输入你想查找

8、的单词(输入回车结束)：)；gets(seek);p=seek;for(i;*(p+i)!=0;i+)/依 次查找j+=*(p+i); 得到待查找单词的关键字j=j%M; /显示在哈希表中的位置while(!strcmp(hashlistj.word,seek)=0) / 用 strcmp 函数来比较字 符串j=(j+d)%M; /有冲突情况下的地址m+;d+;if(m=HASH_LEN)break; /超过表长if(m=HASH_LEN)printf(哈希表中没有这个单词n);elseprintf(单词s存在，他的关键字 是%dn,hashlistj.word,hashlistj.numbe

9、r);6 .哈希表的显示void printhash() int i=0;for(i=0;iHASH_LEN;i+)printf(位置%dtt 关键字%-6dtt 单 %sn,i,hashlisti.number,hashlisti.word);7.菜单界面设计void menu()printf(tt*n);printf(tt*1向哈希表中插入单词(15)*n)printf(tt*2查找哈希表中的单词*n)printf(tt*3显示哈希表的存储情况*n)printf(tt*4计算哈希表的平均查找长度*n)printf(tt*5退出程序*n)printf(tt*n);8.主程序设计int mai

10、n()int n,choose,done;float ave;menu();while(done)printf(请输入你的选择:)；scanf(%d”,&choose);switch(choose)case 1:printf(请输入你想输入的单词数:);scanf(%d”,&n);getchar();Initwordlist(n);Createhashlist(n);break;case 2:getchar();find();break;case 3:printhash();break;case 4:ave=average()/n; /计算平均查找长度 printf(平均查找长度为fn”,av

11、e);break;case 5:done=0;break;default:break;return 0;五调试分析1. 在编写程序之前首先要确定该程序的功能，是涉及到对哈希表的基本操 作，因此首先要了解哈希表的工作原理。2 .哈希表的创建要采用除留余数法，即取关键地址对不大于表长的数取模， 该数的取定要非常留心，通常取质数或者不包含小于20的质因数的合数，这是除留 余数法实现的关键。3 .哈希表的作用是不用比较就能直接查找出想要的数据，因此解决冲突是哈 希表的特长。解决冲突的方法有很多种，书上介绍了线性探测法，二次探测法，伪随 机探测法，链地址等，因此也需要选用解决冲突的办法，本实验就采用了线

12、性探测这 种最常用的方法来解决冲突。4.在主程序段采用了 switch语句，方便客户端进行选择性操作。5 .模块的调用要合理，只有模块起到相应的作用才能实现程序的功能。六测试结果1、输出菜单界面F:vcMicrosoft Visual StudioMyProjert5机器DebugWl器6己二 二 二 二 二 二 二 二 二 二 二词词喜一 i单单售 X的存平 =插中的的 一一星表表 =W希甫 一一普哈、 一一真示算出 一一向杳豆蓄 二 1 2 3 4 5哈程二 二 二 二 二 二 二 二 二二 二 二 二 二 二 二 二 二 二 二 二 二 二 二 二二 二 二 二 二 二 二 二 二请输入

13、你的选择:魅鹳瞄单词：10n回度长1 = hello 结灵,:9itl 结艮）:girl 结灵：boy 4qR = hello 结5日_- lang 结屹:short inM: hello2. 插入单词必集项要词II*入集理个善词按回车结束:hi卷入称的蛊择=3 .查找单词store回1O1 i回y Oj.B- .B- .-Tn - .-Tn - .fn - .-Tn - .-Tn - .-Tn - .5-. nATTTTTTTTT I S3 Jr- 123456789 1 第第第第第第第 AAAAAAAAAAAAAASA .-sfr-s?-sfr-sfr- 41414141414141414

14、14141414141 H.-T4-.*s =A&词词问词词词问词饲-eh s h : -y. -!- 豆豆谏。束束束束灵束束束灵士 :1结结结结结结结结结择 伺回回回回回回回回回矿. -.-V-.-V1 的 度 15长 F;-Llr-.F;-F;-FF;-Llr-.F;-F;-FF;-F- . T-? T-lr-lr-T-T-T-T-lr-T-T-T-T-束结车束结车:rm : :UJ.iJ:- _l.-lLn.4J- - 4LTJ- UJ- .选查京查在选 选必 的想静想的斗 F-Hrl你 你 -l- l- l- i 0 12 3 41234567891111 1./ 御词曾w-置置w-w

15、wlw-w(置置W-W-W-W-输5 .输出平均查找长度I F:vcMicrosoft Visual StudioMyProjects机器De.exehello girl girl hello lang hoy short hello hihello词词词词词词词词词词词词词词词 .自-.自 一 .m 一 .-Tn 一 .-Tn 一 .自一.自-.自 一 .m 一 一 .-Tn 一 .自一.自-.自 一 .m 一词词WWWWWWHH驾b-e.-h-e.-h-e.- 41= - fl -h-j-b-e.-h-e.-h-e.- - fl -H-J-B-E.- rhE.-h-e.-键键键键键键键键键

16、键键键键键键0 12 301234567891111单单的个找送查京查在选 选度选昌 想想的斗 你-Hpl你 篡你 AAA.A0 123456789 A_ A置置置WI置置置最请请壬辅.主后StudioMyP roj erts 机器 巳机器.exe6-退出程序 F:vcIMi crosoft Vi sua Ihello.-Tn 一 .自 一 .-Tn 一.自-,-m 一 .-Tn 一0 0 0 5 0 0WWWrH= - rH= - rH = - rH = - rh = - rH -键键键键键键,F;-F_.F_.F;-Llr-.F- T.-T.-.T.-.T-;刁._-lT-0 12 380

17、0000continue:3 : t 辛为辛J 4LTJ.- .iltj- 选度选ke 瓮你an 14入查入s 置鲁输esEIQ七用户使用说明1 .本程序在VC和TC环境下都可以运行。2. 程序运行后自动生成菜单界面，用户可以根据菜单提示进行操作。3. 程序结束也有相应的提示，用户不必担心无法结束程序。八课程设计总结该程序主要涉及到哈希表的初始化，创建，插入，查找等过程，要实现这些过程 需要用到除留余数法和线性探测再散列的方法，其中除留余数法主要是用来创建哈希 表，即取关键字被不大于表长的数除后得到余数为哈希地址。线性探测再散列是解决 哈希表冲突的常用方法之一。在编程过程中主要遇到以下几个问题

18、：1. 忘记定义变量，导致执行时无法被识别，如warning C4101: j: unreferenced local variable， error C2065: find : undeclared identifier。2. 在编写程序模块时功能不完全，导致程序无法运行，如error C2447: missing function header (old-style formal list?)。3 . 程序功能不完整，无法达到实验要求，如error C2601: InitHashTable local function definitions are illegal。4. 低级错误也经常出

19、现，如*/ found outside of comment 0数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本阶段学完理 论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后 的美观的用户界面以及另人兴奋的可用程序，都是一个很好的学习和锻炼的过程。使 我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分 析、解决实际问题的能力。使我们体会到自身知识和能力能在实际中的应用和发挥。 不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设 计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工 具操作经验，更加深了对C+语言的了解，熟悉了其环境，更增强了哈希表等对多种 算法的使用技巧。另外，数据结构课程设计指导老师细心、耐心的指导，鼓励我对程序进行合理改 进，培养了创新意识和创新能力。总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力 学习知识。