哈希表的设计

第1页共20页数据结构课程设计（哈希表的设计）院系信息科学与工程学院专业班级学生姓名学号课程设计日期：2011年6月26日至2011年7月7日第2页共20页目录一、问题描述......................................................3二、需求分析1、基本要求2、测试数据.......................................................3三、概要设计......................................................3四、详细设计......................................................4五、测试分析.....................................................11六、课程设计总结.............................................13七、附录（源代码）.........................................13第3页共20页一、问题描述针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。二、需求分析基本要求：假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。测试数据：输入30个人的姓名拼音，即30个字符串，然后用除留余数法构建哈希表并用链表法处理冲突，最后将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。三、概要设计Ht[i].key=NULLKEYHt[i].next=NULLi++Ni=0i++开始i=0,keyiMaxY第4页共20页四、详细设计头文件#includestdio.h#includestring.hp-next!=NULLi8输入em-kry_codekey=em-key_code%pht[key].key=keyht[key].key=NULLKEYNULLKEYNULLKEYNULLKEYYNem-next=NULLYht[key].next=emNht[key].key==keyYp=ht[key].nextp=p-nextp-next=emYNN结束第5页共20页#includestdlib.h#includeconio.h#defineP30/*除数余留法中的除数*/#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;第6页共20页}}intCharToInt(charstr[]){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;}第7页共20页Node*Hash_Search(HashTableht,intkey)/*查找函数*/{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个姓名*/第8页共20页for(i=0;i30;i++){node=(Node*)malloc(sizeof(Node));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++;第9页共20页count2+=j;}printf(\n);}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(查找不成功！);}第10页共20页voidhash_create(inth[],intstatus[],intdata){intaddress;intdi;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页六、课程设计总结这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。这次课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。在本次课程设计中，不得不提的还有合作。虽说课题不是太难，但有时自己想不明白，通过大家的讨论可以更快和更有效率的解决问题，而且印象还很深刻。所以以后要多多和同学讨论，毕竟自己的不可能想得很全。通过这次课程设计，让我学到了很多，让我知道了认真上好专业实验课的重要性，以后多在实践中锻炼自己，毕竟说和做还是有很大差距的，而且写程序的过程中要考虑周到，严密。在做设计的时候要有信心，有耐心，切勿浮躁。认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。七、附录（程序源代码):第14页共20页#includestdio.h#includestring.h#includestdlib.h#includeconio.h#defineP30#defineNULLKEY0#defineMAX30#definehashlen30intsum=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;}第15页共20页}intCharToInt(charstr[]){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;}第16页共20页Node*Hash_Search(HashTableht,intkey){intp0=Hash(key);if(ht[p0].key==NULLKEY){sum++;returnNULL;}elseif(ht[p0].key==p