《数据结构》课程设计说明书hash表的建立和查找

1、课程设计任务书学生姓名： xxx 专业班级： 计算机0502 指导教师： xxx 工作单位：计算机科学与技术学院 题 目: hash表的建立和查找初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）设计哈希函数和哈希表；（2）设计解决冲突的方法；（3）输入一组数据建立哈希表，并实现在哈希表中进行查找。2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；

2、（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、结果分析、设计体会等；（4）结束语；（5）参考文献。时间安排： 2007年7月2日7日 （第18周）7月2日 查阅资料7月3日 系统设计，数据结构设计，算法设计7月4日-5日 编程并上机调试7月6日 撰写报告7月7日 验收程序，提交设计报告书。指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日hash表的建立和查找摘要: 本人设计了一个hash表的建立和查找系统，其主要功能是，用户可以手工输入hash表元素个数和各个元素的数据内容，系统便相应地建立一个hash表，（输入错误时，系统会显示输入错

3、误，并提示重新输入）；可对已建立的hash表进行多次查找，系统打印查找到的信息，用户可以按提示信息退出系统。hash表采用结构体数组进行存储，hash函数由除留余数法建立，冲突的解决采用线性探测。关键字: hash表，结构体数组，除留余数法，线性探测0.引言随着时代的进步，科技的发展，信息时代已经来临，在这样的时代背景之下，人们迫切需要对信息进行存储和查找，而数据结构成为了信息技术中极为重要的一门学科，发挥着关键作用。信息资料之多之杂之广，使如何存储和高效查找信息成为了一个很严肃的问题。本次课程设计中，我设计了一个小程序对用户输入的数据利用hash表进行存储。存储完成后，用户可利用hash表查

4、找数据，速度十分快，可多次查找，也可按提示信息退出。1.需求分析本次课程设计需要实现hash表的建立和查找，具体内容如下：1.1 hash 表的建立建立hash函数，从而根据用户输入的数据元素个数和各元素的值建立hash 表，即数据的添加和存储。如果输入的元素个数超出规定范围，则打印出错信息，并提示重新输入信息。1.2 hash 表的查找hash表建立好之后，用户可以输入想要查找的值，屏幕显示相应信息。如果存在此值，屏幕显示该值信息；如果不存在，则显示该值不存在；如果想退出系统，则按提示输入命令。2.数据结构设计2.1定义结构体typedef structint key; /定义关键字int

5、cn; /定义查找次数cnhashtable; /定义哈希表类型2.2定义结构体数组hashtable hthm; /定义哈希表空间3.算法设计3.1 hash函数该函数利用除留余数法实现“hash 函数”#define m 19 /不大于表长的最大质数status h(keytype key)/哈希函数return(key%m); /除留余数法/h3.2信息查找函数 这个函数能查找信息，它既能用于查找所输入信息，又能在建立hash的时候被建立hash表的函数调用。用户可以输入想要查找的值，屏幕显示相应信息。如果存在此值，屏幕显示该值信息；如果不存在，则显示该值不存在；如果想退出系统，则按提示

6、输入命令。status hashsearch(hashtable ht,keytype key)/哈希表查找函数int d,i;i=0;d=h(key); /求哈希地址=0; /记录元素被查找的次数while(htd.key!=key)&(htd.key!=free)&(i=hm) /hash表已满，插入失败，返回unsuccessprintf(the hashtable is full!n);return(unsuccess);return(d); /若hd的关键字等于key说明查找成功/hashsearch3.3数据输入函数此函数能够对用户输入的数据进行处理，即将输入数据插入h

7、ash表中。它调用了hash函数。如果插入成功，显示插入成功信息；如果插入不成功，则显示插入不成功信息。status hashinsert(hashtable ht,keytype key)/哈希插入函数，插入成功返回success，插入不成功返回unsuccess/查找不成功的时候，将给定关键字key插入哈希表中int d;d=hashsearch(ht,key);if(htd.key=free) /插入成功htd.key=key;printf(insert success!n);return(success);else /插入不成功printf(uneuccess!n);return(un

8、success); /hashinseart3.4建立hash表函数此函数能够根据用户输入的数据建立hash表，并将所有数据存入表中。如果输入数据不和理（即输入的数据长度大于或等于表长，或小于0），屏幕会提示错误信息，并提示用户重新输入正确的数据值；如果输入数据合理（即输入的表长大于等于0，小于表长），用户就可以按提示信息输入表元素，哈希表就会被成功建立。hash表的建立也利用了除留余数法，所以该函数调用了哈希表插入运算函数。void hashcreat(hashtable ht)/根据用户输入的信息建立一个哈希表int n;int i;int key1;printf(input the nu

9、mber of the elements(less than the length of the list %d and no less than 0):n,hm); /提示输入规定范围内的长度scanf(%d,&n); /输入表长if(n=20) /输入不合理的表长度 printf(please input a length less than 20:n);/表长大于等于20else if(n0) printf(please input a length no less than 0:n);/表长小于0while(n=20) /输入表长度合理scanf(%d,&n);if(n=20) pri

10、ntf(please input a length less than 20:n); /表长大于等于20 else if(n0) printf(please input a length no less than 0:n); /表长小于0 for(i=0;in;i+) /依次插入用户输入的各个元素的数据printf(input the key word:n);scanf(%d,&key1); /输入元素数据hashinsert(ht,key1); /调用哈希表插入运算/hashcreat3.5主要界面的设计void jiemian()/主界面设计hashtable ht0hm; /分配hash

11、表的空间int key0=0; /初始化为0float key1=0; /初始化为0 int i;printf(build the hash list:n); /提示建立信息hashcreat(ht0); /建立hash表printf(now you can search in the hash list:n); /提示用户查找printf(input the key word of the element required to searchn(if you want to exit ,input a figure bigger than 0 and small than 1.):n);sc

12、anf(%f,&key1); /输入想要查找的数据key0=(int)key1;while(key1-(float)key0)=0)/多次查找输入的数据，系统显示相应结果/按提示退出系统 i=hashsearch(ht0,key0); if(ht0i.key=key0) /存在该元素时 printf(%d exists in the list.n ,key0); /打印存在信息 printf(its pose is num.%dnn,i); /打印元素位置 else printf(there is no %d in the list.nn,key0);printf(input the key

13、word of the element required to searchn(if you want to exit ,input a figure bigger than 0 and small than 1.):n); /提示用户退出 scanf(%f,&key1); /用户继续输入数据 key0=(int)key1; /key0是key1的整数部分/jiemian3.6其他有关技术讨论我这个程序选用结构体数组为存储结构，实现了hash表的数据存储。hash表查找给予一种尽可能不通过比较操作而直接得到记录的存储位置的想法而提出的一种特殊查找技术。它的基本思想是通过记录中关键字的值key为

14、自变量，通过某一种确定的函数h，计算出函数值h（key）作为存储地址，将相应的关键字的记录存储到对应的位置上。而在查找是仍需要用这个确定的函数h进行计算，获得所要查找的关键字所在的记录的存储位置。除留余数法（division method）是用关键字key除以某个正整数m，所得余数作为哈希地址的方法。对应hash函数h（key）为：h（key）=key % m，一般情况下m 的取值为不大于表长的质数。开放定址发解决冲突，形成下一个地址的形式是： hi=（h（key）+di）%m i=1，2，k（k=m）其中，h（key）为哈希函数，m为某个正整数，di为增量序列。线形探测再散列，是将开放定地址

15、发中的增量di设定为一系列从1开始一直到表长减1的整数序列：1，2，3，,m-1(m为表长)。本系统对用户在操作时可能进行的错误和违规操作，给出了基本的提示信息和解决方案，以便用户在非法操作后得到意想不到的结果，即在根据用户输入的数据建立hash表并将所有数据存入表中时。如果输入数据不和理（即输入的数据长度大于或等于表长，或小于0），屏幕会提示错误信息，并提示用户重新输入正确的数据值；如果输入数据合理（即输入的表长大于等于0，小于表长），用户就可以按提示信息输入表元素，哈希表就会被成功建立。本系统对用户在操作时可能进行的错误和违规操作，给出了基本的提示信息和解决方案，以便用户在非法操作后得到意

16、想不到的结果。4.程序的实现4.1所有的函数声明int h(int key)int hashsearch(hashtable ht,int key)int hashinsert(hashtable ht,int key)void hashcreat(hashtable ht)4.2主要方法的代码实现4.2.1哈希表查找函数int hashsearch(hashtable ht,int key)/*哈希表查找函数*/int d,i;i=0;d=h(key); /*求哈希地址*/=0;while(htd.key!=key)&(htd.key!=free)&(i=hm)printf(th

17、e hashtable is full!n);return(unsuccess);return(d); /*若hd的关键字等于key说明查找成功*/*hashsearch*/4.2.2哈希插入函数int hashinsert(hashtable ht,int key)/*哈希插入函数*/*查找不成功的时候，将给定关键字key插入哈希表中*/int d;d=hashsearch(ht,key);if(htd.key=free)htd.key=key;printf(insert success!n);return(success); /*插入成功*/elseprintf(uneuccess!n);

18、return(unsuccess); /*插入不成功*/*hashinseart*/4.2.3哈希表建立函数void hashcreat(hashtable ht)/*建立哈希表的函数*/int n;int i;int key1;printf(input the number of the elements(less than the length of the list %d and no less than 0):n,hm);scanf(%d,&n);if(n=20) /*输入不合理的表长度*/ printf(please input a length less than 20:n);el

19、se if(n0) printf(please input a length no less than 0:n);while(n=20) /*输入表长度合理*/scanf(%d,&n);if(n=20) printf(please input a length less than 20:n); else if(n0) printf(please input a length no less than 0:n); for(i=0;in;i+)printf(input the key word:n);scanf(%d,&key1);hashinsert(ht,key1); /*调用哈希表插入运算*

20、/*hashcreat*/4.3程序运行结果4.3.1运行界面4.3.2输入出错提示界面4.3.3输入元素超过hash表表长届面4.3.4输入正确建立hash表提示界面4.3.5根据提示建立hash表界面4.3.6输入查找数据得到显示数据界面4.3.7表中无输入数据时的界面4.3.8用户可按提示信息退出系统界面4.4结果分析用户手工输入数据并对输入数据建立hash表，具有提示错误功能；另外就是对已建立的hash表进行查找，具有多次查找功能，并打印信息，可以按提示信息退出系统。本系统采用了hash表存储,查找速度极其快,查找的时间复杂度为o(1)。本系统仍然存在一些不足之处值得改进，例如：在建立

21、hash表的过程中，如果用户想退出系统，也不得不在建立好hash表之后，才能实现。5.设计体会通过这次做课程设计，使我对数据结构这门课的认识更进一步，这门课确实是学好计算机程序设计的基础。与此同时，自己对程序设计中应该注意的一些问题也有了自己的一些想法。首先，一个程序要达到正确性，可读性，健壮性，高效率和低存储量的要求，这样用户在使用程序的时候才会更加满意，程序才能得到更多的关注。其次，要养成良好的编程习惯，在做一个程序之前，要对该程序的存储结构，抽象数据类型和应该具备的功能以及各模块之间的调用关系有一个总体的把握，画出必要的算法流程图或写出必要的伪码来表示各模块应该具备的功能。再次，在编写程序的过程中应该对一些难于理解的地方加上必要的注释，这样会使在之后的调试与维护阶段更加容易，在定义功能函数与变量时应该尽量采取有表征意义的名称，这样也可达到见名知意的效果。最后，在程序的调试阶段，应该针对程序中用户可能进行的错误操作给出解决的方法，要尽量选出几组具有毁灭性的数据