课程设计报告-哈希表

1、. 数据结构课程设计 （哈希表的设计） 院 系 专 业 班 级 学 生 姓 名 学 号 课程设计日期：2011年 6月26日至 2011年 7 月 7 日目录1、 问题描述.32、 需求分析 1、基本要求3 2、测试数据.33、 概要设计.34、 详细设计.45、 测试分析.11六、课程设计总结.13七、附录（源代码）.141、 问题描述针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。2、 需求分析基本要求： 假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。测试数

2、据： 输入30个人的姓名拼音，即30个字符串，然后用除留余数法构建哈希表并用链表法处理冲突，最后将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。3、 概要设计 开始i=0,key i+ N i<Max YHti.key=NULLKEYHti.next=NULLi=0 i+ i<8 N Y输入em->kry_codeem->next=NULLkey=em->key_code%p Nhtkey.key= NULLKEY NULLKEY NULLKEY NULLKEY Nhtkey.key = key Y htkey.key =

3、key Y htkey.next = em p = htkey.next Np->next!= NULL p->next = em Y p = p->next 结束4、 详细设计头文件#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 30 /*除数余留法中的除数*/#define NULLKEY 0 #define MAX 30 /*人名个数*/#define hashlen 30 /*哈希表长度*/int su

4、m=0,k=0;typedef struct Node /*哈希表结构体*/ char key_code10; /*哈希表地址*/ struct Node *next;Node;typedef struct hashtable /*创建哈希表*/ int key; struct Node *next;HashTableMAX;int Hash(int key) int mode = key % P; /*除留余数法得到的余数*/ return mode;void Hash_Init(HashTable ht) /*哈希表初始化*/ int i; for(i = 0; i < MAX; i

5、+) hti.key = NULLKEY; hti.next = NULL; int CharToInt(char str) return str0+str1+str2;int Hash_Insert(HashTable ht, Node *node) /*为哈希表分配地址*/ int key = Hash(CharToInt(node->key_code); Node *p;p=(Node*)malloc(sizeof(Node); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = node;k+; else if(htkey.

6、key = key) p = htkey.next;k+; while(p->next!= NULL) p = p->next;k+; p->next = node;k+; return 1;Node* Hash_Search(HashTable ht, int key) /*查找函数*/ int p0 = Hash(key); if(htp0.key = NULLKEY) sum+;return NULL; else if(htp0.key = p0) Node *p = htp0.next; while(p != NULL) if(CharToInt(p->key_

7、code) = key) sum+; return p; p = p->next;sum+; return NULL;int Hash_Create(HashTable ht) /*哈希表长度*/ int i; Node *node; Hash_Init(ht); printf("请输入姓名："); /*输入30个姓名*/ for(i=0;i<30;i+) node = (Node *)malloc(sizeof(Node); scanf("%s",node->key_code); node->next = NULL; Hash_

8、Insert(ht, node); printf("nCreate Successfully!n"); return 1;int hash_output(HashTable h) /*哈希表的输出部分*/ Node *a;int i,j,count2=0;a=(Node*)malloc(sizeof(Node);j=0;for(i=0;i<hashlen;i+) printf("%4d",i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)pri

9、ntf("->%s",(*a).key_code);a=(*a).next;j+;count2+=j;printf("n");return count2;void Hash_Link() /*链表法构造函数*/int key;int i;Node *node; HashTable ht; Hash_Create(ht);hash_output( ht);printf("count=%dn",k); /*查找总长度*/printf("ASL=%d/8n",k); /*平均查找长度*/ printf("

10、请输入要查找的数据："); /*输入查找的姓名*/ scanf("%s",&key); node = Hash_Search(ht, key);printf("查找次数:%dn",sum); if(node != NULL) printf("查找成功！"); else printf("查找不成功！"); void hash_create(int h,int status,int data)int address;int di;address=data%P;if(statusaddress=0)ha

11、ddress=data;statusaddress=1;elsefor(di=1;di<=hashlen-1;di+)address=(data%P)+di)%hashlen;if(statusaddress=0)haddress=data;statusaddress=1;break;return ;int hash_search(int h,int key)int address, di; address=key % P; if(haddress=key) /*哈希表中元素与查找元素是否相等*/ return 1; else for(di=1;di<=hashlen-1;di+)

12、/*哈希表中元素与查找元素不相等，查找下一元素*/ address=(key%P)+di)%hashlen;if(haddress=key)return di+1;break; if(di>=hashlen)return 0;int main() /*主函数*/ printf("ttt*n"); printf("ttt 哈希表设计n"); printf("n"); printf("ttt*n"); printf("n");Hash_Link(); 5、 测试分析测试数据：随机输入的30个人

13、的姓名拼音测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作测试结果：主界面：哈希表：6、 课程设计总结 这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。 这次课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。在本次课程设计中，不得不提的还有合作。虽说课题不是太难，但有时自己想不明白，通过大家的讨论可以更快和更有效率的解决问题，而且映象还很深刻。所以以后要多多和同学讨论，毕竟自己的不可能想得很全。 通过这次课程设

14、计，让我学到了很多，让我知道了认真上好专业实验课的重要性，以后多在实践中锻炼自己，毕竟说和做还是有很大差距的，而且写程序的过程中要考虑周到，严密。在做设计的时候要有信心，有耐心，切勿浮躁。认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 7、 附录（程序源代码): #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 11#d

15、efine NULLKEY 0#define MAX 20#define hashlen 13int sum=0,k=0;typedef struct employee int key_code; struct employee *next;Employee;typedef struct hashtable int key; struct employee *next;HashTableMAX;int Hash(int key) int mode = key % P; return mode;void logo() printf("ttt*n"); printf("

16、;ttt 哈希表的基本操作n"); printf("n"); printf("ttt n"); printf("ttt*n"); printf("n");void Hash_Init(HashTable ht) int i; for(i = 0; i < MAX; i+) hti.key = NULLKEY; hti.next = NULL; int Hash_Insert(HashTable ht, Employee *em) int key = Hash(em->key_code); Em

17、ployee *p;p=(Employee*)malloc(sizeof(Employee); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = em;k+; else if(htkey.key = key) p = htkey.next;k+; while(p->next!= NULL) p = p->next;k+; p->next = em;k+; return 1;Employee* Hash_Search(HashTable ht, int key)int p0 = Hash(key); if(htp0.ke

18、y = NULLKEY)sum+;return NULL; else if(htp0.key = p0) Employee *p = htp0.next; while(p != NULL) if(p->key_code = key) sum+; return p; p = p->next;sum+; return NULL;int Hash_Create(HashTable ht)int i; Employee *em; Hash_Init(ht); printf("请输入数据："); for(i=0;i<30;i+) em = (Employee *)m

19、alloc(sizeof(Employee);scanf("%d",&em->key_code); em->next = NULL; Hash_Insert(ht, em); printf("nCreate Successfully!n"); return 1;void ConFun() printf("请按任意键继续."); getch();int hash_output(HashTable h)Employee *a;int i,j,count2=0;a=(Employee*)malloc(sizeof(Emp

20、loyee);j=0;for(i=0;i<hashlen;i+)printf("%4d",i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)printf("->%d",(*a).key_code);a=(*a).next;j+;count2+=j;printf("n");return count2;void Hash_Link()int key;Employee *em; HashTable ht; Hash_Crea

21、te(ht);hash_output( ht);printf("count=%dn",k);printf("ASL=%d/30n",k); printf("请输入要查找的数据："); scanf("%d",&key); em = Hash_Search(ht, key);printf("查找次数:%dn",sum); if(em != NULL) printf("查找成功！"); else printf("查找不成功！");ConFun();void hash_create(int h,int status,int data)int address;int di;address=data%P;if(statusaddress=0)haddress=data;statusaddress=1;elsefor(di=1;di<=hashlen-1;di+)address=(data%P)+di)%