哈希表的设计与实现数据结构与算法课程设计报告Word文件下载.docx
- 文档编号:1143257
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:26
- 大小:157.18KB
哈希表的设计与实现数据结构与算法课程设计报告Word文件下载.docx
《哈希表的设计与实现数据结构与算法课程设计报告Word文件下载.docx》由会员分享,可在线阅读,更多相关《哈希表的设计与实现数据结构与算法课程设计报告Word文件下载.docx(26页珍藏版)》请在冰点文库上搜索。
所以采用链地址法散列算法。
采用链地址法,当出现同义词冲突时,可以使用链表结构把同义词链接在一起,即同义词的存储地址不是散列表中其他的空地址。
根据问题分析,我们可以定义有3个域的节点,这三个域分别为电话号码charnum[30],姓名charname[30],地址charaddress[30]。
这种类型的每个节点对应链表中的每个节点,其中电话号码和姓名可分别作关键字实现哈希表的创建。
二、数据结构的选择和概要设计
1、数据结构的选择
数据结构:
散列结构。
散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系,并提供多种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。
散列结构基本思想,是以所需存储的结点中的关键词作为自变量,通过某种确定的函
数H(称作散列函数或者哈希函数)进行计算,把求出的函数值作为该结点的存储地址,并将该结点或结点地址的关键字存储在这个地址中。
散列结构法(简称散列法)通过在结点的存储地址和关键字之间建立某种确定的函数
关系H,使得每个结点(或关键字)都有一个唯一的存储地址相对应。
当需要查找某一指定关键词的结点时,可以很方便地根据待查关键字K计算出对应的“映
像”H(K),即结点的存储地址。
从而一次存取便能得到待查结点,不再需要进行若干次的比较运算,而可以通过关键词直接计算出该结点的所在位置。
2、概要设计
(1)、哈希表的定义
结点的数据类型:
structnodeII定义姓名地址电话号码
{
charname[30];
charaddress[30];
charnum[30];
node*next;
};
ElemNode;
(2、、哈希地址的计算
以姓名为关键字的哈希地址计算:
从取得的姓名第二个字母开始,取ASCII码累加,
对30求余得所求哈希地址
以电话号码为关键字的哈希地址计算:
从号码第二位开始,将所有号码累加之后对30
求模得哈希地址
(3)、拉链法
链地址法:
在散表结构存放在指针指向的单元中。
链地址法在解决冲突时,使用链表结构把同义词链接在一起,即同义词的存储地址不是散列表中其他的空地址。
采用C语言定义如下:
#defineMax_length100Typedefstruct{
intkey;
ElemTypedata;
ElemNode*next;
}ElemNode;
Typedefstruct{
ElemNode*first;
}ElemHeader,HashTable[Max_length];
所有的同义词构成一个单链表,再由一个表头节点指向这个单链表的第一个节点。
这
些镖头节点组成一个一维数组,即散列表。
数组元素的下标对应由散列函数求出的散列地址。
拉链法处理冲突的散列表结构
(4)链地址法查找结点的算法思想
a、根据查找节点的关键字算出哈希地址b、在散列地址所指向的单链表中依次寻找节点
c、如果找到,输出节点的信息;
否则提示没有找到
三、详细设计和编码主流程图。
初始化散列链表2并为其
动态分配内存空间
Menu()主
菜单
输入选择
选择
2
添加记录apend()
>进行号码散列list()
3
*清空creat();
creat2()
4
选择1
选择5
选9
选8
进行姓名散列Iist2()
查找用户
find2name)
>退出系统return0
查找号码find_num()mm()
输出结果
空
号码散列
结果
列表已清
姓名散
列结果
输出
num[i]!
=O
始
开
Key=key+(int)num[i]
取整型num[2]赋给key
i从3开始取
i++
以姓名为关键字的Hash()函数流程图
结束
添加结点信息流程图
按姓名查找流程图
按号码查找流程图
编码
1、建立节点
structnode//定义姓名地址电话号码
charname[30];
node*next;
typedefnode*pnode;
//声明了已有数据类型的两个指针变量
typedefnode*mingzi;
node**phone;
node**nam;
2、定义哈希函数这里我们需要定义两个哈希函数,一个以电话号码为关键字,另一个以姓名ASCII之和求模之后的值为关键字。
主要方法为将电话号码从第二位开始逐一累加并将所得结果对30求模
得哈希地址;
第二种则是将姓名字符进行强制类型转换之后得ASCII码相加对30求模得哈希地址。
=============================求哈希地址源代码==========================
voidhash(charnum[30])//
//
哈希函数
将运算的结果所得的余数作为节点的存储地址
{inti=1;
key=(int)num[0];
while(num[i]!
=NULL)
key+=(int)num[i];
i++;
}
key=key%30;
voidhash2(charname[30])////
inti=1;
key2=(int)name[0];
while(name[i]!
key2+=(int)name[i];
i++;
key2=key2%30;
(3)、添加节点接下来就是每个节点的建立,添加结点,利用链地址法解决冲突。
建立结点应包括动态申请内存空间。
向结点中输入信息。
同时将结点中的next指针等于NULL。
添加结点,首先需要利用哈希函数计算出地址即关键字,然后将所得数据插入到链表中。
===========================动态申请内存空间============================voidcreate_phone()//新建节点
inti;
phone=newpnode[30];
for(i=0;
i<
30;
i++){
phone[i]=newnode;
phone[i]->
next=NULL;
voidcreate2_num()//新建节点
{inti;
nam=newmingzi[30];
for(i=0;
i++)
{nam[i]=newnode;
nam[i]->
添加节点===============================
intapend()//添加节点{
node*newphone;
node*newname;
newphone=input();
newname=newphone;
newphone->
newname->
hash(newphone->
num);
//先计算号码的keyhash2(newname->
name);
//姓名的key2
next=phone[key]->
next;
//把该key的号码链接到原来的号码的后一节点上
phone[key]->
next=newphone;
next=nam[key2]->
//把该key的姓名链接到原来的号码的后一节点
上
nam[key2]->
next=newname;
return0;
(4)、查找节点
voidfind_num(charnum[30])//按号码查找用户信息
hash(num);
node*q=phone[key]->
while(q!
=NULL)
if(strcmp(num,q->
num)==0)
break;
q=q->
if(q)
cout<
<
q->
name<
"
_"
<
address<
num<
endl;
elsecout<
无此记录"
voidfind2_nam(charname[30])//按姓名查找用户信息
hash2(name);
node*q=nam[key2]->
if(strcmp(name,q->
name)==0)
elsecout<
5)输出哈希表
voidlist_num()//以号码为关键字显示列表
node*p;
p=phone[i]->
while(p)
{cout<
p->
'
_'
p=p->
voidlist2_nam()//以姓名为关键字显示列表
p=nam[i]->
6)主函数
main()四、上机调试
1在调试的时候,出现了无法查找姓名或者电话号码相同的用户的信息当查找姓名相同或者号码相同的用户时,就会出现死循环原先代码如下
==================================部分代码===================================while(q!
if(strcmp(num,q_>
num)==O)
q=q_>
next;
q_>
name<
q_>
num<
endl;
无此记录"
}
这个子函数只能查找一个符合条件的节点,查找到一个之后就跳出循环了,后经指导老师指
出,改为
==================================部分代码===================================intflag;
hash(num);
node*q=phone[key]->
{cout<
flag=1;
if(flag==0)cout<
无此记录"
先前出现问题是因为break语句结束语句指能查找一个节点,改进之后可以实现功能
2、文件的操作在这个程序中没有能成功实现,故在最后阶段,删除了这一功能。
如i,j混淆少括号少分号等小问
3、程序中经常会出现程序调试过程中常会出现一些小错误,题都可以按照提示找到,然后改正。
五、测试结果及分析
(1)主界面:
c*C:
\Docu>
entsandSettings\Ad>
inistrator\桌面'
课程设计\Debug\Debug\哈希
(3)查找记录
a、通过姓名查找姓名不重复的结点
b、通过姓名查找姓名重复的结点
c、通过电话号码查找结点
d、结点不存在
结点不存在时,输出的数据为空
(4)姓名散列
以姓名为关键字查找结点,输出数据
(5)、号码散列
(6)清空记录
(7)退出系统
六、用户使用说明
添加数据不能大于30个数,电话号码为字符型。
进入后按照程序界面提示可以进行对数据的添加、查找以及按姓名和按电话号码两种不同方式的散列。
本程序在运行时有辅助信息提示,可以十分容易的上手,关键信息均通过键盘录入。
七、参考文献
[1]王昆仑,李红•数据结构与算法•北京:
中国铁道出版社,2007.
[2]谭浩强,张基温•C语言程序设计教程•3版•北京:
高等教育出版社,2007.
八、附录
#include<
iostream>
#include"
string.h"
usingnamespacestd;
#defineNULL0
unsignedintkey;
//所需存储的节点中的无符号关键字作为自变量unsignedintkey2;
//声明了已有数据类型的两个指针变量typedefnode*mingzi;
voidhash(charnum[30])//哈希函数//将运算的结果所得的余数作为节点的存储地址
key=(int)num[0];
voidhash2(charname[30])//哈希函数
//将运算的结果所得的余数作为节点的存储地址{inti=1;
node*input()//输入节点
node*one;
one=newnode;
one->
输入姓名:
"
cin>
>
name;
输入地址:
cin>
address;
输入电话:
num;
returnone;
intapend()//添加节点
node*newname;
newphone=input();
newname=newphone;
//先计算号码的key
hash2(newname->
//把该key的号码链接到原来的号码的后一节点上phone[key]->
//把该key的姓名链接到原来的号码的后一节点上nam[key2]->
voidcreate_phone()//新建节点
phone[i]->
nam=newmingzi[30];
nam[i]=newnode;
intflag;
hash(num);
node*q=phone[key]->
while(q!
{if(strcmp(num,q->
num)==0){cout<
}q=q->
{intflag=0;
voidmenu()//菜单
//cout<
\t\t欢迎来到哈希电话簿系统cout<
\t\t*************************************************
intmain()
system("
colorfc"
);
//界面美化charnum[30];
create_phone();
//按号码创建
create2_num();
//按姓名创建
intsel;
//定义变量选择你所要进行的操作
while
(1)
menu();
\n\t\t\t请输入你要进行的操作:
;
sel;
if(sel==1)
9号码查询,8姓名查询"
intb;
//选择号码查询还是姓名查询
b;
if(b==9)
请输入电话号码:
cin>
输出查找的信息:
find_num(num);
else
请输入姓名:
find2_nam(name);
if(sel==2)
姓名散列结果:
list2_nam();
if(sel==0)
\n请输入要添加的内容:
apend();
if(sel==3)
号码散列结果:
list_num();
if(sel==4)
列表已清空:
if(sel==5)return0;
*****2.姓名散歹J*****
KMKKK3_号~码議^列XXXKX
KMKKK4.清空记录*****
mc£
”退出系统*****
请输入你要进行的操作:
(2)添加记录
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈希表 设计 实现 数据结构 算法 课程设计 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)