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

目 录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语言程序来解决哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完毕相应的建表和查表程序。2 需求分析2.1 任务和规定 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完毕相应的建表和查表程序。规定：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法解决冲突。2.2 运营环境（1）WINDOWS2023/XP系统（2）Visual C+ 6.0编译环境或TC编译环境2.3 开发工具C语言3 分析和设计3.1 系统分析及设计思绪（1）创建哈希表（2）姓名（结构体数组）初始化 （1） 用除留余数法构建哈希函数 （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 h)来输出哈希表定义函数Hash_Link()构造链表函数定义函数int hash_search(int h,int key)查找输入的名字3.3 函数流程图 （1）哈希表的创建及初始化流程图 图3.1 哈希表的发明及初始化流程图（2）创建哈希表链表的流程图 图3.2 发明哈希表链表的流程图（3）查找输入数据的流程图 图3.3 查找输入数据的流程图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 课程设计总结5.1 程序运营结果或预期运营结果 图5.1程序运营结果1 图5.2程序运营结果2说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。5.2 设计结论通过这次课程设计，我了解到了许多自身的局限性，有很多学习过的知识，在学过之后并没有反复的操作和复习，认为课堂上听懂就行了，在这课程设计中，这些局限性就显现了出来，导致经常要翻书，查找一些认为弄懂的问题，这次我了解到了，学习不仅仅是课堂上听讲，还要课后复习和操作。课程设计是对我们这学期的学习成果的试金石，对我们来说是一个不小的考验，它是我们专业课程知识综合应用的实践训练。“自己动手，丰衣足食”，通过这次课程设计，我深深体会到这句千古名言的真正含义，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才干真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才干换来最终完美的结果。参考文献1张福祥. C语言程序设计M. 辽宁大学出版社，2023.12 张福祥，王萌C语言程序设计习题解答与实验实训M沈阳：辽宁大学出版社，20233 牛莉，刘远军等计算机等级考试辅导教程M北京：中国铁道出版社，2023致 谢本次课程设计在选题及进行过程中得到陈智老师的悉心指导，陈老师严谨求实的治学态度，热情洋溢的工作激情，将使我终生受益，在老师的影响下我学到了很多在书本上学不到的东西，我非常感谢她。谨再一次向陈老师致以真挚的谢意和崇高的敬意。此外我还要感谢组内的成员们，由于他们也帮我解决了不少难题，正是在大家的共同努力下，本次课程设计将随着论文的完毕划上圆满的句号!