数据结构课程设计哈希表设计问题

1、目 录1 前言12 需求分析12.1 任务和要求12.2 运行环境12.3 开发工具23 分析和设计23.1 系统分析及设计思路23.2 主要数据结构及算法23.3 函数流程图34 具体代码实现65 课程设计总结155.1 程序运行结果或预期运行结果155.2 设计结论17参考文献17致 谢171 前言从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体

2、中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。2 需求分析2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。2.2 运行环境（1）WINDOWS2000/XP系统（2）Visual C+ 6.0编译环境或TC编译环境2.3 开发工具C语言3 分析和设计3.1 系统分析及设计思路（1）创建哈希表（2）姓名（结构体数组）初始化 （1） 用除留余数法构建哈希函数

3、（2） 用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式：3.2 主要数据结构及算法定义结构体typedef struct hashtable创建哈希表定义函数Hash_Init(HashTable ht)来对哈希表初始化定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址定义函数Hash_Init(ht)输入30个名字定义函数Hash_Create(HashTable ht)来求哈希表长度定义函数hash_output(HashTable

4、h)来输出哈希表定义函数Hash_Link()构造链表函数定义函数int hash_search(int h,int key)查找输入的名字3.3 函数流程图 （1）哈希表的创建及初始化流程图 图3.1 哈希表的创造及初始化流程图（2）创建哈希表链表的流程图 图3.2 创造哈希表链表的流程图（3）查找输入数据的流程图 图3.3 查找输入数据的流程图4 具体代码实现 #include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define P 30 /*除数余

5、留法中的除数*/#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; /*除留余数法得到的余数*/

6、return mode;void Hash_Init(HashTable ht) /*哈希表初始化*/ int i; for(i = 0; i < MAX; i+) 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(N

7、ode); 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; e

8、lse 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;i<30;i+) node = (Node *)malloc

9、(sizeof(Node); scanf("%s",node->key_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<hashlen;i+) printf("%4d"

10、;,i);printf("%4d",hi.key);if(hi.next!=0)count2+;j=1;a=hi.next;while(a)printf("->%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("cou

11、nt=%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_creat

12、e(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;

13、 if(haddress=key) /*哈希表中元素与查找元素是否相等*/ return 1; else for(di=1;di<=hashlen-1;di+)/*哈希表中元素与查找元素不相等，查找下一元素*/ 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");

14、printf("ttt*n"); printf("n");Hash_Link();5 课程设计总结5.1 程序运行结果或预期运行结果 图5.1程序运行结果1 图5.2程序运行结果2说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。5.2 设计结论通过这次课程设计，我了解到了许多自身的不足，有很多学习过的知识，在学过之后并没有反复的操作和复习，以为课堂上听懂就行了，在这课程设计中，这些不足就显现了出来，导致经常要翻书，查找一些以为弄懂的问题，这次我了解到了，学习不仅仅是课堂上听讲，还要课后复习和操作。课程设计是对我们这学期的学习成果的试金石，对我们来说是一个不小的考验，它是我们专业课程知识综合应用的实践训练。“自己动手，丰衣足食”，通过这次课程设计，我深深体会到这句千古名言的真正含义，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。参考文献1张福祥. C语言程序设计M. 辽宁大学出版社，2008.12 张福祥，王萌C语言程序设计习题解