散列表的设计与实现

1 散列表的设计与实现散列表的设计与实现 一 一 作业要求 作业要求 问题描述 设计散列表实现电话号码查找系统 基本要求 1 设每个记录有下列数据项 电话号码 用户名 地址 2 从键盘输入各记录 分别以电话号码和用户名为关键字建立散列 表 3 采用一定的方法解决冲突 4 查找并显示给定电话号码的记录 5 查找并显示给定用户名的记录 进一步完成内容 1 系统功能的完善 2 设计不同的散列函数 比较冲突率 3 在散列函数确定的前提下 尝试各种不同类型处理冲突的方法 考察平均查找长度的变化 二 二 设计分析 设计分析 用散列表实现电话号码查找系统 采用姓名和电话号码为关键 字 动态分配存储空间 根据姓名和电话号码分别进行哈希排序建 立不同的数组分别存放姓名和电话号码 能实现电话号码信息的插 入 删除 查找 保存等操作 采取线性探测法解决冲突 三 三 逻辑结构 逻辑结构 电话号码查找系统 逻辑上应当是每个结点含有一个人所有的 信息 在查找的时候可以通过不同的查找方式对不同的信息进行查 找 人和人之间的关系应当是独立的 添加结点的时候对每个人由 系统分配新的结点 但是不同人结点中所包含的信息则具有相同的 格式 比如每个结点中的姓名 地址 电话号码都具有相同的格式 在进行物理存储的时候可以建立相同的数组来放置同类信息 四 四 存储结构 存储结构 所设计的程序采用数组存放各类相同的信息 先建立数组进行 初始化 再把不同的结点通过哈希排序以及线性探测的结果存放入 对应的数组 建立的数组有两个 分别以姓名和电话号码建立哈希 表 对信息进行存储 以后的各种操作 比如查找 散列等都建立 在相应的哈希表的基础上 各个信息之间通过链表相连 在查找的 时候可以充分利用哈希表查找的快速性 形象化的存储结构如下图 2 五 五 算法设计 算法设计 六 六 实现代码 实现代码 include include include include include define NULL 0 unsigned int key unsigned int key1 unsigned int key2 int p struct node 建节点 char name 8 address 20 char num 11 node next typedef node pnode typedef node mingzi node phone node nam node a using namespace std 使用名称空间 hash char num 11 建表 以人的电话号码为关键字 建立相应的 散列表若哈希地址发生冲突 进行冲突处理 int i 3 j key1 int num 2 while num i NULL 3 key1 int num i i key1 key1 20 for j 0 jnum break return key hash2 char name 8 建表 以人的姓名为关键字 建立相应的散列 表 若哈希地址发生冲突 进行冲突处理 int i 1 j key2 int name 0 while name i NULL key2 int name i i key2 key2 20 for j 0 jname break return key node input 输入节点 node temp temp new node temp next NULL cout 输入姓名 temp name cout 输入地址 temp address 4 cout 输入电话 temp num return temp int apend 添加节点 node newphone node newname newphone input newname newphone newphone next NULL newname next NULL newphone next phone hash newphone num next phone hash newphone num next newphone newname next nam hash2 newname name next nam hash2 newname name next newname return 0 void create 新建电话号码数组 int i phone new pnode 20 for i 0 inext NULL void create2 新建姓名数组 int i nam new mingzi 20 for i 0 inext NULL void list 显示列表 号码散列 int i node p 5 for i 0 inext while p cout name address num next void list2 显示列表 姓名散列 int i node p for i 0 inext while p cout name address num next void find char num 11 查找用户信息 号码查找 int i j 0 node p for i 0 inext while p if strcmp num p num 0 cout name address num next if j 0 cout 无此记录 endl 6 void find2 char name 8 查找用户信息 姓名查找 int i j 0 node p for i 0 inext while p if strcmp name p name 0 cout name address num next if j 0 cout 无此记录 next phone key next p next void Delete1 char name 8 node p hash2 name p nam key next nam key next p next void save 保存用户信息 int i node p fstream iiout out txt ios out for i 0 inext while p iiout name address num next void menu 菜单 cout 0 添加记录 endl cout 1 查找记录 endl cout 2 姓名散列 endl cout 3 号码散列 endl cout 4 清空记录 endl cout 5 保存记录 endl cout 6 删除信息 endl cout 7 退出系统 endl int main cout 欢迎使用电话号码查找系统 endl cout 散列表的设计与实现 sel 输入选择项目操作 if sel 0 cout 请输入要添加的内容 endl apend else if sel 1 8 cout 9 号码查询 8 姓名查询 b if b 9 cout 请输入电话号码 num cout 输出查找的信息 endl find num else if b 8 cout 请输入姓名 name cout 输出查找的信息 endl find2 name else printf 不合法操作 n else if sel 2 cout 姓名散列结果 endl list2 else if sel 3 cout 号码散列结果 endl list else if sel 4 cout 列表已清空 endl create create2 else if sel 5 cout 通信录已保存 endl save else if sel 6 int c cout 删除信息 endl cout 9 按号码删除 8 按姓名删除 c