![点击分享此内容可以赚币 分享](/master/images/share_but.png)
数据结构课程设计哈希表设计问题.doc
《数据结构课程设计哈希表设计问题.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计哈希表设计问题.doc(19页珍藏版)》请在咨信网上搜索。
目 录 1 前言 1 2 需求分析 1 2.1 任务和规定 1 2.2 运营环境 1 2.3 开发工具 2 3 分析和设计 2 3.1 系统分析及设计思绪 2 3.2 重要数据结构及算法 2 3.3 函数流程图 3 4 具体代码实现 6 5 课程设计总结 15 5.1 程序运营结果或预期运营结果 15 5.2 设计结论 17 参考文献 17 致 谢 17 1 前言 从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 <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> #define P 30 /*除数余留法中的除数*/ #define NULLKEY 0 #define MAX 30 /*人名个数*/ #define hashlen 30 /*哈希表长度*/ int sum=0,k=0; typedef struct Node /*哈希表结构体*/ { char key_code[10]; /*哈希表地址*/ struct Node *next; }Node; typedef struct hashtable /*创建哈希表*/ { int key; struct Node *next; }HashTable[MAX]; int Hash(int key) { int mode = key % P; /*除留余数法得到的余数*/ return mode; } void Hash_Init(HashTable ht) /*哈希表初始化*/ { int i; for(i = 0; i < MAX; i++) { ht[i].key = NULLKEY; ht[i].next = NULL; } } int CharToInt(char str[]){ return str[0]+str[1]+str[2]; } int Hash_Insert(HashTable ht, Node *node) /*为哈希表分派地址*/ { int key = Hash(CharToInt(node->key_code)); Node *p; p=(Node*)malloc(sizeof(Node)); if(ht[key].key == NULLKEY) { ht[key].key = key; ht[key].next = node; k++; } else if(ht[key].key == key) { p = ht[key].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(ht[p0].key == NULLKEY) {sum++;return NULL;} else if(ht[p0].key == p0) { Node *p = ht[p0].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(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",i); printf("%4d",h[i].key); if(h[i].next!=0) count2++; j=1; a=h[i].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("count=%d\n",k); /*查找总长度*/ printf("ASL=%d/8\n",k); /*平均查找长度*/ printf("请输入要查找的数据:"); /*输入查找的姓名*/ scanf("%s",&key); node = Hash_Search(ht, key); printf("查找次数:%d\n",sum); if(node != NULL) printf("查找成功!"); else printf("查找不成功!"); } void hash_create(int h[],int status[],int data) { int address; int di; address=data%P; if(status[address]==0) { h[address]=data; status[address]=1; } else { for(di=1;di<=hashlen-1;di++) { address=((data%P)+di)%hashlen; if(status[address]==0) { h[address]=data; status[address]=1; break; } } } return ; } int hash_search(int h[],int key) { int address, di; address=key % P; if(h[address]==key) /*哈希表中元素与查找元素是否相等*/ return 1; else { for(di=1;di<=hashlen-1;di++)/*哈希表中元素与查找元素不相等,查找下一元素*/ { address=((key%P)+di)%hashlen; if(h[address]==key) { return di+1; break; } } } if(di>=hashlen) return 0; } int main() /*主函数*/ { printf("\t\t\t************************\n"); printf("\t\t\t 哈希表设计\n"); printf("\n"); printf("\t\t\t************************\n"); printf("\n"); Hash_Link(); } 5 课程设计总结 5.1 程序运营结果或预期运营结果 图5.1程序运营结果1 图5.2程序运营结果2 说明:输入的数为30个姓的拼音,查找的为“pan”,输出的如上图所示。 5.2 设计结论 通过这次课程设计,我了解到了许多自身的局限性,有很多学习过的知识,在学过之后并没有反复的操作和复习,认为课堂上听懂就行了,在这课程设计中,这些局限性就显现了出来,导致经常要翻书,查找一些认为弄懂的问题,这次我了解到了,学习不仅仅是课堂上听讲,还要课后复习和操作。 课程设计是对我们这学期的学习成果的试金石,对我们来说是一个不小的考验,它是我们专业课程知识综合应用的实践训练。“自己动手,丰衣足食”,通过这次课程设计,我深深体会到这句千古名言的真正含义,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才干真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。 实验过程中,也对团队精神的进行了考察,让我们在合作起来更加默契,在成功后一起体会喜悦的心情。果然是团结就是力量,只有互相之间默契融洽的配合才干换来最终完美的结果。 参考文献 [1]张福祥. C语言程序设计[M]. 辽宁大学出版社,2023.1 [2] 张福祥,王萌.C语言程序设计习题解答与实验实训[M].沈阳:辽宁大学出版社,2023. [3] 牛莉,刘远军等.计算机等级考试辅导教程[M].北京:中国铁道出版社,2023. 致 谢 本次课程设计在选题及进行过程中得到陈智老师的悉心指导,陈老师严谨求实的治学态度,热情洋溢的工作激情,将使我终生受益,在老师的影响下我学到了很多在书本上学不到的东西,我非常感谢她。谨再一次向陈老师致以真挚的谢意和崇高的敬意。此外我还要感谢组内的成员们,由于他们也帮我解决了不少难题,正是在大家的共同努力下,本次课程设计将随着论文的完毕划上圆满的句号!- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 哈希表 设计 问题
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文