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

武汉理工大学数据结构课程设计说明书课程设计任务书学生姓名： XXX 专业班级： 计算机0502 指导教师： XXX 工作单位：计算机科学与技术学院 题 目: Hash表的建立和查找初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）设计哈希函数和哈希表；（2）设计解决冲突的方法；（3）输入一组数据建立哈希表，并实现在哈希表中进行查找。2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（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表，（输入错误时，系统会显示输入错误，并提示重新输入）；可对已建立的Hash表进行多次查找，系统打印查找到的信息，用户可以按提示信息退出系统。Hash表采用结构体数组进行存储，Hash函数由除留余数法建立，冲突的解决采用线性探测。关键字: Hash表，结构体数组，除留余数法，线性探测0.引言随着时代的进步，科技的发展，信息时代已经来临，在这样的时代背景之下，人们迫切需要对信息进行存储和查找，而数据结构成为了信息技术中极为重要的一门学科，发挥着关键作用。信息资料之多之杂之广，使如何存储和高效查找信息成为了一个很严肃的问题。本次课程设计中，我设计了一个小程序对用户输入的数据利用Hash表进行存储。存储完成后，用户可利用Hash表查找数据，速度十分快，可多次查找，也可按提示信息退出。1.需求分析本次课程设计需要实现Hash表的建立和查找，具体内容如下：1.1 Hash 表的建立建立Hash函数，从而根据用户输入的数据元素个数和各元素的值建立Hash 表，即数据的添加和存储。如果输入的元素个数超出规定范围，则打印出错信息，并提示重新输入信息。1.2 Hash 表的查找Hash表建立好之后，用户可以输入想要查找的值，屏幕显示相应信息。如果存在此值，屏幕显示该值信息；如果不存在，则显示该值不存在；如果想退出系统，则按提示输入命令。2.数据结构设计2.1定义结构体typedef structint 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表的函数调用。用户可以输入想要查找的值，屏幕显示相应信息。如果存在此值，屏幕显示该值信息；如果不存在，则显示该值不存在；如果想退出系统，则按提示输入命令。Status HashSearch(hashtable ht,keytype key)/哈希表查找函数int d,i;i=0;d=h(key); /求哈希地址htd.cn=0; /记录元素被查找的次数while(htd.key!=key)&&(htd.key!=free)&&(i<hm) /元素位置冲突时，进行线性探测i+; /寻找下一个单元htd.cn+; /寻找次数加1d=(d+i)%m; /线性探测记录的插入位置if(i>=hm) /Hash表已满，插入失败，返回unsuccessprintf("The hashtable is full!n");return(unsuccess);return(d); /若hd的关键字等于key说明查找成功/hashsearch3.3数据输入函数此函数能够对用户输入的数据进行处理，即将输入数据插入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");return(unsuccess); /HashInseart3.4建立Hash表函数此函数能够根据用户输入的数据建立Hash表，并将所有数据存入表中。如果输入数据不和理（即输入的数据长度大于或等于表长，或小于0），屏幕会提示错误信息，并提示用户重新输入正确的数据值；如果输入数据合理（即输入的表长大于等于0，小于表长），用户就可以按提示信息输入表元素，哈希表就会被成功建立。Hash表的建立也利用了除留余数法，所以该函数调用了哈希表插入运算函数。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");/表长大于等于20else if(n<0) printf("Please input a length no less than 0:n");/表长小于0while(n<0|n>=20) /输入表长度合理scanf("%d",&n);if(n>=20) printf("Please input a length less than 20:n"); /表长大于等于20 else if(n<0) printf("Please input a length no less than 0:n"); /表长小于0 for(i=0;i<n;i+) /依次插入用户输入的各个元素的数据printf("Input the key word:n");scanf("%d",&key1); /输入元素数据HashInsert(ht,key1); /调用哈希表插入运算/HashCreat3.5主要界面的设计void jiemian()/主界面设计hashtable ht0hm; /分配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 than 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"); /提示用户退出 scanf("%f",&key1); /用户继续输入数据 key0=(int)key1; /key0是key1的整数部分/jiemian3.6其他有关技术讨论我这个程序选用结构体数组为存储结构，实现了Hash表的数据存储。Hash表查找给予一种尽可能不通过比较操作而直接得到记录的存储位置的想法而提出的一种特殊查找技术。它的基本思想是通过记录中关键字的值key为自变量，通过某一种确定的函数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为增量序列。线形探测再散列，是将开放定地址发中的增量di设定为一系列从1开始一直到表长减1的整数序列：1，2，3，,m-1(m为表长)。本系统对用户在操作时可能进行的错误和违规操作，给出了基本的提示信息和解决方案，以便用户在非法操作后得到意想不到的结果，即在根据用户输入的数据建立Hash表并将所有数据存入表中时。如果输入数据不和理（即输入的数据长度大于或等于表长，或小于0），屏幕会提示错误信息，并提示用户重新输入正确的数据值；如果输入数据合理（即输入的表长大于等于0，小于表长），用户就可以按提示信息输入表元素，哈希表就会被成功建立。本系统对用户在操作时可能进行的错误和违规操作，给出了基本的提示信息和解决方案，以便用户在非法操作后得到意想不到的结果。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); /*求哈希地址*/htd.cn=0;while(htd.key!=key)&&(htd.key!=free)&&(i<hm)i+; /*寻找下一个单元*/htd.cn+; /*寻找次数加1*/d=(d+i)%m; /*线性探测记录的插入位置*/if(i>=hm)printf("The 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");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");else if(n<0) printf("Please input a length no less than 0:n");while(n<0|n>=20) /*输入表长度合理*/scanf("%d",&n);if(n>=20) printf("Please input a length less than 20:n"); else if(n<0) printf("Please input a length no less than 0:n"); for(i=0;i<n;i+)printf("Input the key word:n");scanf("%d",&key1);HashInsert(ht,key1); /*调用哈希表插入运算*/*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)。本系统仍然存在一些不足之处值得改进，例如：在建立Hash表的过程中，如果用户想退出系统，也不得不在建立好Hash表之后，才能实现。5.设计体会通过这次做课程设计，使我对数据结构这门课的认识更进一步，这门课确实是学好计算机程序设计的基础。与此同时，自己对程序设计中应该注意的一些问题也有了自己的一些想法。首先，一个程序要达到正确性，可读性，健壮性，高效率和低存储量的要求，这样用户在使用程序的时候才会更加满意，程序才能得到更多的关注。其次，要养成良好的编程习惯，在做一个程序之前，要对该程序的存储结构，抽象数据类型和应该具备的功能以及各模块之间的调用关系有一个总体的把握，画出必要的算法流程图或写出必要的伪码来表示各模块应该具备的功能。再次，在编写程序的过程中应该对一些难于理解的地方加上必要的注释，这样会使在之后的调试与维护阶段更加容易，在定义功能函数与变量时应该尽量采取有表征意义的名称，这样也可达到见名知意的效果。最后，在程序的调试阶段，应该针对程序中用户可能进行的错误操作给出解决的方法，要尽量选出几组具有毁灭性的数据来进行测试，在程序不能正常处理的情况下要采取一些方案使这样的问题得以解决。做程序是一个比较累的工作，特别是当遇到困难时，程序通不过时，真的很令人沮丧。但是改正一个错误时，那种喜悦心情也很令人期盼，这种心情堪比久旱见甘霖的喜悦。就是因为有这种令人身心愉悦的可能，我才得以能够整晚不睡来改程序中的不足之处。编程中有苦有乐，其中的苦乐只有亲身经历才能体会到。要想做出好的程序，必须做好忍受其间痛苦的准备。通过这个星期的课程设计，我的收获还是不少。我的c语言水平有了比较大的提高，其中c语言关于指针，链表的操作理解的比以前深刻不少。另外是数据结构方面的提高，对存储结构，及各种查找排序方面也有不少的提高。虽然我做的程序里还有写问题，做的不够深入，但独立完成一个比较大一点的程序的经历也是很宝贵的。6.结束语用户手工输入数据并对输入数据建立Hash表，具有提示错误功能；另外就是对已建立的Hash表进行查找，具有多次查找功能，并打印信息，可以按提示信息退出系统。程序用turboc实现. 通过本次课程设计，使我对数据结构这门课的认识更进一步，数据结构作为计算机专业的一门必修课，对如何编写好的算法进行了比较深入的阐述，为我们写出正确的，强壮的代码奠定了基础。在做课程设计的过程中，从查阅的相关资料和问题的解决中学到了不少的知识，因此对课本上的知识也有了更深入的了解。在此，深深的感谢任课教师和辅导老师对我的的热心帮助，也感谢广大同学们的关心和帮助参考文献1 严蔚敏，吴伟民.数据结构，清华大学出版社，2001年1月2 刘怀亮.数据结构习题解析与实验指导，冶金工业出版社 ，2005年2月3 谭浩强.数据结构，清华大学出版社，1999年12月ut2ApOdfXXc02GyBKsKCWw97MrqqWhoj5TL15Zt6jIPYytYCummtARp3v1N5luizi3xh3BhWYreKO8d9g7nmZQoWPJeTLDrw08gVS8DsDQQYGC3cE7moO2tLF0Jf1gK74IUXyBmtIVR97CkrfVqULT5fn2t6MpJR6rbzVPSortZvIj5NB5ndVvSr4iWr1TwLFKgLSPzuhRjQ3CmZU98eUOuijdLSZqPmvrw9zKupxf8WFUG9l2G9277g2rTipa1YpCZEuqxpKBhtVDCooQOzxUz3vJrZmOcijyM62zchmeooTYes8EBMm932tbz2Yo09RtsZEYS8Zrd2Yktj8l6jEAzVAjnfbtryLvsm6oFbfToXVRFFn7OwIYgJlamkUNXJYbz5Rrb7r4VsuR9zpfZFMfsjhcfCA37lNW2VVLRKN7R8psz1BN6oRic5hU5Z6HCxAYqyNPOG8duYbAwqSl20CSg06Dh2sM8HLtgPkIcSkrgOPDpuHBj1LmPk7lYdvC6NNMwL3fwhZFTFVYAARY7lHSSxJ10V3pH3Y19BxYR77Ib7CpZSu2tijqe3hKqkKAu9KSkCpHKXUIKvvyJZpg2YijRkqfbGgOvyqKuxNWI9oMnJtt6QilZxtyrF7d20FbmabcfiixrQKUsVNXBPPFUXyQ1fJSKFSUbkgs2DUVQC9sz4JkbgN4Qqv66pyoARjurNFJ3TxyfclZiEePtwFJthphEipDFNqnR2HjQKV2DzWtMPDJQkBcXmovdsjqCTJagjMdLsKPgaD2s0H0vmZGAHt36gyUEZ7UmANk1ndREuBeqdgrx0venqGnsyIB2ilq3SIQrNL4m56t7Z8Y8da5K0KUpn5Nzg4JvjdtfFHyt82AoGQkXo4VBLmLEiy2P7HtHBho07rCfttxodYDPPdtQsO7wxD0J6fKKlGm4woDzplhtRr2XgqN13hqy59zU1GegDyQniHNTaVSieueFQcYfUCJwd3vk5I7YKmhunDmIZ ut2ApOdfXXc02GyBKsKCWw97MrqqWhoj5TL15Zt6jIPYytYCummtARp3v1N5luizi3xh3BhWYreKO8d9g7nmZQoWPJeTLDrw08gVS8DsDQQYGC3cE7moO2tLF0Jf1gK74IUXyBmtIVR97CkrfVqULT5fn2t6MpJR6rbzVPSortZvIj5NB5ndVvSr4iWr1TwLFKgLSPzuhRjQ3CmZU98eUOuijdLSZqPmvrw9zKupxf8WFUG9l2G9277g2rTipa1YpCZEuqxpKBhtVDCooQOzxUz3vJrZmOcijyM62zchmeooTYes8EBMm932tbz2Yo09RtsZEYS8Zrd2Yktj8l6jEAzVAjnfbtryLvsm6oFbfToXVRFFn7OwIYgJlamkUNXJYbz5Rrb7r4VsuR9zpfZFMfsjhcfCA37lNW2VVLRKN7R8psz1BN6oRic5hU5Z6HCxAYqyNPOG8duYbAwqSl20CSg06Dh2sM8HLtgPkIcSkrgOPDpuHBj1LmPk7lYdvC6NNMwL3fwhZFTFVYAARY7lHSSxJ10V3pH3Y19BxYR77Ib7CpZSu2tijqe3hKqkKAu9KSkCpHKXUIKvvyJZpg2YijRkqfbGgOvyqKuxNWI9oMnJtt6QilZxtyrF7d20FbmabcfiixrQKUsVNXBPPFUXyQ1fJSKFSUbkgs2DUVQC9sz4JkbgN4Qqv66pyoARjurNFJ3TxyfclZiEePtwFJthphEipDFNqnR2HjQKV2DzWtMPDJQkBcXmovdsjqCTJagjMdLsKPgaD2s0H0vmZGAHt36gyUEZ7UmANk1ndREuBeqdgrx0venqGnsyIB2ilq3SIQrNL4m56t7Z8Y8da5K0KUpn5Nzg4JvjdtfFHyt82AoGQkXo4VBLmLEiy2P7HtHBho07rCfttxodYDPPdtQsO7wxD0J6fKKlGm4woDzplhtRr2XgqN13hqy59zU1GegDyQniHNTaVSieueFQcYfUCJwd3vk5I7YKmhunDmIZ17