《哈希表的设计与实现.doc》由会员分享，可在线阅读，更多相关《哈希表的设计与实现.doc（38页珍藏版）》请在金锄头文库上搜索。
1、令胆 嗲 院计算机科 嗲 b 练 水 系课程设计报告20232023 学年第2学期课程数据结构与算法课 程 设 计 名 称哈希表的设计与实现学生姓名学号专业班级06 计科（1)指导教师2023年9月课程设计题目：（哈希表的设计与实现的问题 设计哈希表实现电话号码查询系统。设计程序完毕以下 规定 ：(1） 设每个记录有下列数据项：电话号码、用户名、地址：（2） 从键盘输入各记录 ， 分别以电话号码和用户名为关键字建立晗希表 ；(3） 采用再哈希法解决冲突；（4） 查找并 显示给定电话号码的记录 ：（5） 查找并显示给定用户的记录。一、 问题分析和任务定义1、问题分析要完毕如下规定 ：设计晗希表实
2、现电话号码查询系统。 实现本程序需要解决以下几个问题：(1)如何设计一个结点使该结点涉及电话号码、用户名、地址。(2)如何分别以 电话号码和用户名为关键字建立哈希表 。(3)如何运用再晗希法解决冲突。(4)如何实现用晗希法查找并显示给定电话号码的记录 。(5)如何查找并显示给定用户的记录 。2、任务定义由问题分析知，本设计重要规定分别以电话号码和用户名为关键字建立晗希表 ，并实现 查找功能 。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由 于结点的个数无法确认，并且假如采用线性探测法散列算法 ，删除结点会引起 “信息丢失” 的问题。所以采用链地址法散列算法 。采用链地址
3、法 ，当出现同义词冲突时，使用链表结构 把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址 。一方面，解决的是定义链表结点，在链地址法中，每个结点相应一个链表结点，它由三个 域组成，而由于该程序需要分别用电话号码和用户名为关键字建立晗希表 ，所以该链表结点 它是由四个域组成.name8 、num ll 和 address20 都是 char 浮点型，输入输出都只能 是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表 的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标相应由散列函 数求出的散列地址。拉链法解决冲突 的散列表结构：
4、 3、主程序分析本题目最重要的规定是设计散列 函数，本程序需要设计两个散列函数才干解决问题，程序需 要分别为以 电话号码和用户名为关键字建立哈希表 。所以要分别以用户名、号码为关键字建 立两个散列画数，具体思绪为 ：对于以号码为关键字的散列函数，是将十一个数字所有相加，然后对 20 求余。得到的 数作为地址 。对于以用户名为关键字的散列函 数，是将所有字母的ASCLL 码值相加 ，然后对 20 求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须涉及一个输 入结点信息、添加结点的函数：要实现查找函数 ，则必须涉及一个查找结点的函数； 此外尚有一个必不可少的就是运 行之后要有
5、一个主菜单 ，即要设计一个主函数(main（） ）。4、测试数据的选择最后，程序完毕后要对程序进行 编译调试，执行后要选择数据进行测试，这里选择的测试数 据为：l、姓名：张三 电话号码： 地址：合肥2、姓名：Jack 电话号码： 地址：Shanghai三、概要设计和数据结构选择本设计涉及到的数据结构为 ：哈希表。规定输入电话号码、用户名、地址三个信息，并 规定分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个晗希函数，进行哈 希查找。在链地址法中，每个结点相应一个链表结点，它由三个域组成，而由于该程序需要分别 用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是由 四个域组成
6、，链地址法结 点结构如图： 阳e8 I 川口J l a抽出s 20 I next其中 name8和 numll 是分别为以电话号码和用户名为关键字域 ，存放关键字 （key ) ; address20(data）为结点的数据域，用来存储用户的地址。Next 指针是用来指 向下一个结点 的地址。重要算法的流程 图如下：以号码为关键字的 Hash（）函数流程图开始取整型 num2赋给 keyi从 3 开始取 Key=key+(int) numii+Key=key%20结束以姓名为关键字的 HashO函数流程图开始取整型nameO赋给 key2i从 0 开始取Key2+=nameii+Key2:ke
7、y%20结束添加结点信息流程图：开始申请新的结点 newphone,newname 即新的号码和名字Newphone=input()Newname 指向 newphone调用 hash（）函数调用 hash（）函数拉链法解决冲突运用用户名为关键字插入结束按姓名查找流程图：开始调用 hash（）函数中新结点 q 指向phonekey-nextq=q-next输 出无 记 录q 不为 空输 出相 应记录结束按号码查找流程图：开始 调用 bash2（）函数中新结点 q 指向pbonekey-nextq=q-next输 出无 记 录q 不为空输 出相 应 记录结束初始化散列链表 (1） 并为其动态分派
8、内存空 间初始化散列链表 （ 2） 并为其动态分派内存空 间主程序流程图Menu （） 主 菜单进行姓名散1 list2()添加记录 apend()进行号码散列 list()号码散列结果清空 creat();creat2()列表己清空退出系统 return O结束四、具体设计和编码一方面定义结点结构体类型，在链地址法 中，每个结点相应一个链表结点，它由三个域组 成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是 由四个域组成 ，链地址法结点结构如图：I n棚e s I 川其中 name8和 num ll是分别为以电话号码和用户名为关键 字域 （key） ，存放关
9、键字： address20为结点的数据域（data），用来存储用户的地址信息。next 指针是用来指向下一个结 点的地址。unsigned int key 和 unsigned int key2 分别被定义为电话号码和用户名关键字。程序的重要模 块如下：串程序部分源代码中串串串串串丰1、建立节点struct node H建节点char name8,address20矿节点中要包含用户名，用户地址，电话号码以及指向下一个结点的指针char num(ll; node * next;typedef node* pnode; /typedef 可认为一个己有的数据类型声明多个别名，这里为该类型声明了两
10、 个指针typedef node* mingzi; node *phone ;node 肺nam; node *a;2、对哈希函数的定义本程序要设计两个 hash O 函数，分别相应电话号码和用户名。本设计中对散列函数 选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或 结点 的存储地址，即 H (key) =key mod p，本设计中p 取 20，然后将计算出来的数作为该结 点的地 址赋给 key。具体方法如下：以电话号码为关键字建立哈希函数 hash(char num11） 。以用户 名为关键字建立哈希 函数bash2(char name8） 。运用强制类型转换
11、，将用户名的每一个字母 的ASCLL 码值相加并且除以20 后的余数。将计算出来的数作为该结 点的地址赋给 key2 。程序部分源代码牢牢牢牢牢牢牢牢牢牢串串串串串串串 串本本中a),oid hash(char numll) II以电话号码为关键字建立哈希函数key=(int)num 2;while(numi!=NULL)key+=(int)numi;1+;key=key %20;b)void bash2(char name8) II以用户名为关键字建立晗希函数int i = 1; key2=(int)nameO;while(namei!=NULL)key2+=(int)namei;；key2
12、=key2%20;然后，建立结点 ，并添加结点 ，运用链地址法解决冲突 。建立结点应涉及动态申请内 存空间。向结点中输入信息。同时将结点中的 next 指针等于 null 。添加结点，一方面需要运用 晗希函数计算出地址即关键字，另一方面将该结点插入以关键字为地址的链表后 ，当然由于分别 以用户名和电话号码为关键字 ，所以分两种情况 ，假如以用户名为关键字则调用 void hash2(char name8）函数，并且将结点插入相应的散列链表中，假如以电话号码为关键字则 调用 void hash(char numll）函数，并且将结点插入相应的散列链表中 。并且，需要两个建立散列链表的函数 ，分别动态申请一定的空间 ，用于动态申请散列 链表。void creat（）用来动态创建以电话号码为关键字的链表数组，void create2（）用来动态创 建以用户名为关键字的链表数组。串串程序部分源代码串串丰void create() II新建号码节点phonei=new node; phonei-next=NULL;int i;phone=new pnode20; fl动态创建对象数组for(i=O;inext=NULL ;nam=new mingzi20; for(i=O;i2
