《《数据结构》课程设计说明书hash表的建立和查找》由会员分享,可在线阅读,更多相关《《数据结构》课程设计说明书hash表的建立和查找(17页珍藏版)》请在金锄头文库上搜索。
1、武汉理工大学数据结构课程设计说明书课程设计任务书学生姓名: XXX 专业班级: 计算机0502 指导教师: XXX 工作单位:计算机科学与技术学院 题 目: Hash表的建立和查找初始条件:理论:学习了数据结构课程,掌握了基本的数据结构和常用的算法;实践:计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)1、系统应具备的功能:(1)设计哈希函数和哈希表;(2)设计解决冲突的方法;(3)输入一组数据建立哈希表,并实现在哈希表中进行查找。2、数据结构设计;3、主要算法设计;4、编程及上机实现;5、撰写课程设计报告,包括:(
2、1)设计题目;(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表进行存储。
4、存储完成后,用户可利用Hash表查找数据,速度十分快,可多次查找,也可按提示信息退出。1.需求分析本次课程设计需要实现Hash表的建立和查找,具体内容如下:1.1 Hash 表的建立建立Hash函数,从而根据用户输入的数据元素个数和各元素的值建立Hash 表,即数据的添加和存储。如果输入的元素个数超出规定范围,则打印出错信息,并提示重新输入信息。1.2 Hash 表的查找Hash表建立好之后,用户可以输入想要查找的值,屏幕显示相应信息。如果存在此值,屏幕显示该值信息;如果不存在,则显示该值不存在;如果想退出系统,则按提示输入命令。2.数据结构设计2.1定义结构体typedef structin
5、t key; /定义关键字int 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数据输入函数此函数能够对用户输入的数据进行处
7、理,即将输入数据插入Hash表中。它调用了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
8、);return(unsuccess); /HashInseart3.4建立Hash表函数此函数能够根据用户输入的数据建立Hash表,并将所有数据存入表中。如果输入数据不和理(即输入的数据长度大于或等于表长,或小于0),屏幕会提示错误信息,并提示用户重新输入正确的数据值;如果输入数据合理(即输入的表长大于等于0,小于表长),用户就可以按提示信息输入表元素,哈希表就会被成功建立。Hash表的建立也利用了除留余数法,所以该函数调用了哈希表插入运算函数。void HashCreat(hashtable ht)/根据用户输入的信息建立一个哈希表int n;int i;int key1;printf(I
9、nput 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);/表长大于等于20else if(n0) printf(Please input a length no less than 0:n);/表长小于0while(n=20) /输入表长度合理scanf(%d,&n);i
10、f(n=20) printf(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 ht0
11、hm; /分配Hash表的空间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 tha
12、n 1.):n);scanf(%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 word of the element required to searchn(If you want to exit ,input a figure bigger than 0 and small than 1.):n); /提示用户退出