《哈希表的设计》doc版.doc

哈尔滨理工大学课程设计（数据结构）题目： 哈希表设计班级： 姓名： 指导教师：系主任： 2013年03月08日目录1、 问题描述.32、 需求分析 1、基本要求 2、测试数据.33、 概要设计.34、 详细设计.45、 测试分析.11六、课程设计总结.13七、附录（源代码）.131、 问题描述针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。2、 需求分析基本要求： 假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有30个，取平均查找长度的上限为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 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 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;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-key_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) /*哈希表的输出部分*/ 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); /*平均查找长度*/ 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; address=key % P; if(haddress=key) /*哈希表中元素与查找元素是否相等*/ return 1; else for(di=1;di=hashlen)return 0;int main() /*主函数*/ printf(ttt*n); printf(ttt 哈希表设计n); printf(n); printf(ttt*n); printf(n);Hash_Link(); 5、 测试分析测试数据：随机输入的30个人的姓名拼音测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作测试结果：主界面：哈希表：查找界面：6、 课程设计总结 在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。 这段时间的课程设计，我也认识到数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。 7、 附录（程序源代码):#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 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;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-key_code) = key) sum+; return p; p = p-next;sum+; return NULL;int Hash_Create(HashTable ht) int i; Node *node; Hash_Init(ht);printf(请输入姓名：); for(i=0;ikey_code); node-next = NULL; Hash_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%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(请输入要查找的姓名：); 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;retu