数据结构课程设计哈希表设计问题.docx
- 文档编号:8884968
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:15
- 大小:144.77KB
数据结构课程设计哈希表设计问题.docx
《数据结构课程设计哈希表设计问题.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计哈希表设计问题.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构课程设计哈希表设计问题
1前言
从C语言产生到现在,它已经成为最重要和最流行的编程语言之一。
在各种流行编程语言中,都能看到C语言的影子,如Java的语法与C语言基本相同。
学习、掌握C语言是每一个计算机技术人员的基本功之一。
根据本次课程设计的要求,我设计小组将编写一个C语言程序来处理哈希表问题,通过这个程序,将针对自己的班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
2需求分析
2.1任务和要求
针对自己的班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
要求:
假设人名为中国姓名的汉语拼音形式。
待填入哈希表的人名共有30个,取平均查找长度的上限为2。
哈希函数用除留余数法构造,用链表法处理冲突。
2.2运行环境
(1)WINDOWS2000/XP系统
(2)VisualC++6.0编译环境或TC编译环境
2.3开发工具
C语言
3分析和设计
3.1系统分析及设计思路
(1)创建哈希表
(2)姓名(结构体数组)初始化
(1)用除留余数法构建哈希函数
(2)用链表法处理冲突
(3)查找哈希表
在哈希表中进行查找,输出查找的结果和关键字,并计算和输出查找成功的平均查找长度
(4)显示哈希表
显示哈希表的的格式:
3.2主要数据结构及算法
定义结构体typedefstructhashtable创建哈希表
定义函数Hash_Init(HashTableht)来对哈希表初始化
定义函数Hash_Insert(HashTableht,Node*node)来为哈希表分配地址
定义函数Hash_Init(ht)输入30个名字
定义函数Hash_Create(HashTableht)来求哈希表长度
定义函数hash_output(HashTableh)来输出哈希表
定义函数Hash_Link()构造链表函数
定义函数inthash_search(inth[],intkey)查找输入的名字
3.3函数流程图
(1)哈希表的创建及初始化流程图
图3.1哈希表的创造及初始化流程图
(2)创建哈希表链表的流程图
图3.2创造哈希表链表的流程图
(3)查找输入数据的流程图
图3.3查找输入数据的流程图
4具体代码实现
#include
#include
#include
#include
#defineP30/*除数余留法中的除数*/
#defineNULLKEY0
#defineMAX30/*人名个数*/
#definehashlen30/*哈希表长度*/
intsum=0,k=0;
typedefstructNode/*哈希表结构体*/
{
charkey_code[10];/*哈希表地址*/
structNode*next;
}Node;
typedefstructhashtable/*创建哈希表*/
{
intkey;
structNode*next;
}HashTable[MAX];
intHash(intkey)
{
intmode=key%P;/*除留余数法得到的余数*/
returnmode;
}
voidHash_Init(HashTableht)/*哈希表初始化*/
{
inti;
for(i=0;i { ht[i].key=NULLKEY; ht[i].next=NULL; } } intCharToInt(charstr[]){ returnstr[0]+str[1]+str[2]; } intHash_Insert(HashTableht,Node*node)/*为哈希表分配地址*/ { intkey=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++; } elseif(ht[key].key==key) { p=ht[key].next; k++; while(p->next! =NULL) { p=p->next; k++; } p->next=node; k++; } return1; } Node*Hash_Search(HashTableht,intkey)/*查找函数*/ { intp0=Hash(key); if(ht[p0].key==NULLKEY) {sum++;returnNULL;} elseif(ht[p0].key==p0) { Node*p=ht[p0].next; while(p! =NULL) { if(CharToInt(p->key_code)==key) {sum++; returnp; } p=p->next; sum++; } } returnNULL; } intHash_Create(HashTableht)/*哈希表长度*/ { inti; 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("\nCreateSuccessfully! \n"); return1; } inthash_output(HashTableh)/*哈希表的输出部分*/ { Node*a; inti,j,count2=0; a=(Node*)malloc(sizeof(Node)); j=0; for(i=0;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"); } returncount2; } voidHash_Link()/*链表法构造函数*/ { intkey; inti; Node*node; HashTableht; 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("查找不成功! "); } voidhash_create(inth[],intstatus[],intdata) { intaddress; intdi; 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; } inthash_search(inth[],intkey) {intaddress,di; address=key%P; if(h[address]==key)/*哈希表中元素与查找元素是否相等*/ return1; else { for(di=1;di<=hashlen-1;di++)/*哈希表中元素与查找元素不相等,查找下一元素*/ { address=((key%P)+di)%hashlen; if(h[address]==key) { returndi+1; break; } } } if(di>=hashlen) return0; } intmain()/*主函数*/ { 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].辽宁大学出版社,2008.1 [2]张福祥,王萌.C语言程序设计习题解答与实验实训[M].沈阳: 辽宁大学出版社,2008. [3]牛莉,刘远军等.计算机等级考试辅导教程[M].北京: 中国铁道出版社,2008. 致谢 本次课程设计在选题及进行过程中得到陈智老师的悉心指导,陈老师严谨求实的治学态度,热情洋溢的工作激情,将使我终生受益,在老师的影响下我学到了很多在书本上学不到的东西,我非常感谢她。 谨再一次向陈老师致以诚挚的谢意和崇高的敬意。 此外我还要感谢组内的成员们,因为他们也帮我解决了不少难题,正是在大家的共同努力下,本次课程设计将随着论文的完成划上圆满的句号!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 哈希表 设计 问题
![提示](https://static.bingdoc.com/images/bang_tan.gif)