哈希表的设计.docVIP

学号 2023-2023学年 第一 2023-2023学年 第一学期 《数据结构课程设计》 课程设计报告 题目： 哈希表的设计 专业： 数字媒体技术 班级： 13〔1〕班 姓名： 金春升 指导教师： 时慧琨 成绩： 计算机与信息工程系 2023年11 月28日 目 录 TOC \o "1-2" \h \u HYPERLINK 1 问题分析和任务定义 2 HYPERLINK 1.1问题描述 2 HYPERLINK 1.2问题分析 2 HYPERLINK 2 开发平台 2 HYPERLINK 3 数据类型和系统设计 2 HYPERLINK 3.1、流程图 2 HYPERLINK 3.2 存储结构设计 3 HYPERLINK 3.3主要算法设计 4 HYPERLINK 4 调试结果与运行情况分析 8 HYPERLINK 4.1程序运行结果 8 HYPERLINK 4.2运行情况分析 10 HYPERLINK 4.3算法的时间复杂度 10 HYPERLINK 5 自我评价与总结 11 HYPERLINK 参考文献 12 HYPERLINK 附：源代码 13 哈希表的设计 1 问题分析和任务定义 1.1问题描述 设计哈希表，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。 1.2问题分析 〔1〕待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。 〔2〕人名为汉语拼音形式，最长不超过20个字符。 〔3〕查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。 〔4〕可屡次查找，继续查找输入1，退出输入0。 2 开发平台 系统：Windows 7 开发工具：Visual studio 2023 语言：C++ 3 数据类型和系统设计 3.1、流程图 开始 开始 选 择 操 作 选 择 操 作 添加记录查找建立哈希表删除 添加记录 查找 建立哈希表 删除 关键字姓名平方线性 关键字 姓名 平方 线性 显 示 输 出 结 果 显 示 输 出 结 果 退出 3.2 存储结构设计 根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下： typedef struct { int key;//关键字 int hash;//初始地址 int reha;//再散列值 char *p;//名字 int l;//查找长度 }HASH; 3.3主要算法设计 3.3.1 NAME〔结构体数组〕初始化 结构体数组NAME a[]的实现〔以班级30人的人名作为初始值〕： NAME a[30]; a[0].p="cailulu"; a[1].p="chenhailin"; a[2].p="daiping"; a[3].p="shanyueming"; a[4].p="fanfangfang"; a[5].p="fengshuang"; a[6].p="gushenglei"; a[7].p="haozonghao"; a[8].p="hongwei"; a[9].p="jiangwangzhi"; a[10].p="jinchunsheng"; a[11].p="laiyan"; a[12].p="lilianxi"; a[13].p="liuhuilin"; a[14].p="liujing"; a[15].p="liupei"; a[16].p="liuyawei"; a[17].p="luoping"; a[18].p="panliangliang"; a[19].p="qiwentao"; a[20].p="shimin"; a[21].p="sunjie"; a[22].p="sunyanyan"; a[23].p="wanxiankai"; a[24].p="wangjiawei"; a[25].p="wangping"; a[26].p="wangwei"; a[27].p="wangyuchun"