哈希表的设计

《哈希表的设计》由会员分享，可在线阅读，更多相关《哈希表的设计（20页珍藏版）》请在金锄头文库上搜索。

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

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

3、p = htkey.next Np-next!= NULL p-next = em Y p = p-next 结束4、 详细设计头文件#include #include #include #include #define P 30 /*除数余留法中的除数*/#define NULLKEY 0 #define MAX 30 /*人名个数*/#define hashlen 30 /*哈希表长度*/int sum=0,k=0;typedef struct Node /*哈希表结构体*/ char key_code10; /*哈希表地址*/ struct Node *next;Node;typedef

4、 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 key_code); Node *p;p=(Node*)malloc(sizeof(Node); if(htkey.key = NULLKEY) htkey.key = key; htkey.next = node

5、;k+; else if(htkey.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-k

6、ey_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;ikey_code); node-next = NULL; Hash_Insert(ht, node); printf(nCreate Successfully!n); return 1;int hash_output(HashTable h) /*哈希表的

7、输出部分*/ Node *a;int i,j,count2=0;a=(Node*)malloc(sizeof(Node);j=0;for(i=0;i%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); /*平均查找长

8、度*/ printf(请输入要查找的数据：); /*输入查找的姓名*/ 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)haddress=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