课程设计报告-哈希表

第1页共20页数据结构课程设计（哈希表的设计）院系专业班级学生姓名学号课程设计日期：2011年6月26日至2011年7月7日第2页共20页目录一、问题描述......................................................3二、需求分析1、基本要求……………………………………………32、测试数据.......................................................3三、概要设计......................................................3四、详细设计......................................................4五、测试分析.....................................................11六、课程设计总结.............................................13七、附录（源代码）.........................................14第3页共20页一、问题描述针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。二、需求分析基本要求：假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。测试数据：输入30个人的姓名拼音，即30个字符串，然后用除留余数法构建哈希表并用链表法处理冲突，最后将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。三、概要设计i8输入em-kry_codeNHt[i].key=NULLKEYHt[i].next=NULLYi++Ni=0i++开始i=0,keyiMaxY第4页共20页四、详细设计头文件#includestdio.h#includestring.h#includestdlib.h#includeconio.h#defineP30/*除数余留法中的除数*/p-next!=NULLkey=em-key_code%pht[key].key=keyht[key].key=NULLKEYNULLKEYNULLKEYNULLKEYYem-next=NULLht[key].next=emNht[key].key==keyYp=ht[key].nextp=p-nextp-next=emYNN结束第5页共20页#defineNULLKEY0#defineMAX30/*人名个数*/#definehashlen30/*哈希表长度*/intsum=0,k=0;typedefstructNode/*哈希表结构体*/{charkey_code[10];/*哈希表地址*/structNode*next;}Node;typedefstructhashtable/*创建哈希表*/{intkey;structNode*next;}HashTable[MAX];intHash(intkey){intmode=key%P;/*除留余数法得到的余数*/returnmode;}voidHash_Init(HashTableht)/*哈希表初始化*/{inti;for(i=0;iMAX;i++){ht[i].key=NULLKEY;ht[i].next=NULL;}}intCharToInt(charstr[]){第6页共20页returnstr[0]+str[1]+str[2];}intHash_Insert(HashTableht,Node*node)/*为哈希表分配地址*/{intkey=Hash(CharToInt(node-key_code));Node*p;p=(Node*)malloc(sizeof(Node));if(ht[key].key==NULLKEY){ht[key].key=key;ht[key].next=node;k++;}elseif(ht[key].key==key){p=ht[key].next;k++;while(p-next!=NULL){p=p-next;k++;}p-next=node;k++;}return1;}Node*Hash_Search(HashTableht,intkey)/*查找函数*/第7页共20页{intp0=Hash(key);if(ht[p0].key==NULLKEY){sum++;returnNULL;}elseif(ht[p0].key==p0){Node*p=ht[p0].next;while(p!=NULL){if(CharToInt(p-key_code)==key){sum++;returnp;}p=p-next;sum++;}}returnNULL;}intHash_Create(HashTableht)/*哈希表长度*/{inti;Node*node;Hash_Init(ht);printf(请输入姓名：);/*输入30个姓名*/for(i=0;i30;i++){node=(Node*)malloc(sizeof(Node));第8页共20页scanf(%s,node-key_code);node-next=NULL;Hash_Insert(ht,node);}printf(\nCreateSuccessfully!\n);return1;}inthash_output(HashTableh)/*哈希表的输出部分*/{Node*a;inti,j,count2=0;a=(Node*)malloc(sizeof(Node));j=0;for(i=0;ihashlen;i++){printf(%4d,i);printf(%4d,h[i].key);if(h[i].next!=0)count2++;j=1;a=h[i].next;while(a){printf(-%s,(*a).key_code);a=(*a).next;j++;count2+=j;}printf(\n);第9页共20页}returncount2;}voidHash_Link()/*链表法构造函数*/{intkey;inti;Node*node;HashTableht;Hash_Create(ht);hash_output(ht);printf(count=%d\n,k);/*查找总长度*/printf(ASL=%d/8\n,k);/*平均查找长度*/printf(请输入要查找的数据：);/*输入查找的姓名*/scanf(%s,&key);node=Hash_Search(ht,key);printf(查找次数:%d\n,sum);if(node!=NULL)printf(查找成功！);elseprintf(查找不成功！);}voidhash_create(inth[],intstatus[],intdata){intaddress;intdi;第10页共20页address=data%P;if(status[address]==0){h[address]=data;status[address]=1;}else{for(di=1;di=hashlen-1;di++){address=((data%P)+di)%hashlen;if(status[address]==0){h[address]=data;status[address]=1;break;}}}return;}inthash_search(inth[],intkey){intaddress,di;address=key%P;if(h[address]==key)/*哈希表中元素与查找元素是否相等*/return1;else{for(di=1;di=hashlen-1;di++)/*哈希表中元素与查找元素不相等，查找下一元素*/{第11页共20页address=((key%P)+di)%hashlen;if(h[address]==key){returndi+1;break;}}}if(di=hashlen)return0;}intmain()/*主函数*/{printf(\t\t\t************************\n);printf(\t\t\t哈希表设计\n);printf(\n);printf(\t\t\t************************\n);printf(\n);Hash_Link();}五、测试分析测试数据：随机输入的30个人的姓名拼音测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作测试结果：主界面：第12页共20页哈希表：六、课程设计总结这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。这次课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。在本次课程设计中，不得不提的还有合作。虽说课题不是太难，但有时自己想不明白，通过大家的讨论可以更快和更有效率的解决问题，而且映象还很深刻。所以以后要多多和同学讨论，毕竟自己的不可能想得很全。通过这次课程设计，让我学到了很多，让我知道了认真上好专业实验课的重要性，以后多在实践中锻炼自己，毕竟说和做还是有很大差距的，而且写程序的过程中要考虑周到，严密。在做设计的时候要有信心，有耐心，切勿浮躁。认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，第13页共20页以便能节省调试程序的时间。七、附录（程序源代码):#includestdio.h#includestring.h#includestdlib.h#includeconio.h#defineP11#defineNULLKEY0#defineMAX20#definehashlen13intsum=0,k=0;typedefstructemployee{intkey_code;structemployee*next;}Employee;typedefstructhashtable{intkey;structemployee*next;}HashTable[MAX];intHash(intkey){intmode=key%P;returnmode;}voidlogo()第14页共20页{printf(\t\t\t************************\n);printf(\t\t\t哈希表的基本操作\n);printf(\n);printf(\t\t\t\n);printf(\t\t\t************************\n);printf(\n);}voidHash_Init(HashTableht){inti;for(i=0;iMAX;i++){ht[i].key=NULLKEY;ht[i].next=NULL;}}intHash_Insert(HashTableht,Employee*em){intkey=Hash(em-key_code);Employee*p;p=(Employee*)malloc(sizeof(Employee));if(ht[key].key==NULLKEY){ht[key].key=key;ht[key].next=em;k++;}elseif(ht[key].key==key){p=ht[key].next;第15页共20页k++;while(p-next!=NULL){p=p-next;k++;}p-next=em;k++;}return1;}Emplo