数据结构课程设计-综合查找算法.doc

1 数据结构课程设计任务书数据结构课程设计任务书 学 院计算机与信息工程学院专 业 计算机科学与技术 专升本 课程名称 数据结构题 目综合查找算法 完成期限 2014 年 6 月 2 日至 2014 年 6 月 29 日共 4 周 内 容 及 任 务 一 项目的目的 1 巩固和加深学生对数据结构课程基本知识的理解 综合该 课程中所学的理论知识 独立或联合完成一个数据结构应用课题 的设计 2 根据选题需要 通过查阅手册和文献资料 培养分析和解 决实际问题的能力 3 熟练运用数据结构有关知识编写程序 二 项目任务的主要内容和要求 1 设计一个的菜单将可以实现的功能显示出来 并有选择提 示 2 分别实现顺序 二分法 二叉排序树 哈希表的查找 3 哈希表可选取其中任何一种方法实现 4 二叉排序树必须实现构建 查找 插入 删除四个基本操 作 5 输出各种排序的结果并进行比较 三 项目设计 本课题是要解决综合查找问题 四 具体成果形式和要求 程序和报告 起止日期工作内容 进 度 安 排 2014 年 6 月 2 号 至 2014 年 6 月 10 号 需求分析 按照课题要求 搜集查阅相关参考 资料 2 2014 年 6 月 11 号至 2014 年 6 月 24 号 概要设计和详细设计阶段 根据前期的需求分 析结果 定义系统实现所需的自定义数据类型 及完成各函数功能 2014 年 6 月 26 号至 2014 年 6 月 29 号 程序的进一步完善 调试与测试 撰写课程设 计报告 主 要 参 考 资 料 1 刘怀亮编著 数据结构 C 程序 北京 冶金工业出版社 2004 2 严蔚敏 吴伟民编著 数据结构 C 语言版 北京 清华大学 出版社 1997 3 杨路明等编著 C 语言程序设计教程 北京 北京邮电大学出 版社 2005 指导教师 意见 签字 年 月 日 系 教研室 主任意见 签字 年 月 日 数据结构设计说明书数据结构设计说明书 学院名称 计算机与信息工程学院 班级名称 计专 14 学生姓名 李振雷 学 号 2013220008 题 目 综合查找算法 指导教师 姓 名 杨传健 起止日期 2014 年 6 月 2 日 2014 年 6 月 29 日 2 目目 录录 1 背景 3 2 设计思路 3 2 1 课程设计思想 3 2 1 1 设计内容 3 2 1 2 设计要求 4 2 2 功能需求 4 2 3 软硬件运行环境及开发工具 4 3 过程论述 4 3 1 概要设计 4 3 1 1 自定义数据类型 4 3 1 2 系统流程图 5 3 2 详细设计 6 3 2 1 顺序查找子模块的实现 6 3 2 2 二分查找子模块的实现 7 3 2 3 二叉排序树子模块的实现 9 3 2 4 哈希查找子模块的实现 9 4 程序测试结果 11 5 总结 17 致谢 18 附录 20 3 1 背景背景 在现代计算机应用中 程序设计占据重要地位 如学生成绩管理 万年历 网上问卷调查等等 用 C 语言实现查找算法要求实现顺序查找 二分查找 二 叉排序树 哈希查找等多种查找方法 如何解决这些问题成为我研究的课题之 一 作为一名学计算机的学生 光有理论知识是远远不够的 更重要的是我们 的实际动手能力 学习计算机 理论能够指导我们的实践 能让我们在实践的 应用过程中得心应手 反过来说 实践也能使我们对理论知识有更深刻的理解 和体会 会促使我们更好的发现问题和解决问题 同时也使我在专业知识上的 视野得到了很好的扩展 因此 综上所述 学计算机 最好的方法就是需要理 论结合实际 而我们最缺乏的就是实践 因此 本次的课程设计给我们提供了 一个很好的实践的机会 程序设计实践课程设计是非常重要的综合性实践教学环节 通过该课程设 计 进一步熟悉了软件开发的基本理论知识 了解了软件设计的一般步骤 掌 握了软件开发的常用技巧 并且学会了更多的解决软件开发过程常见问题的方 法 运用所学的数据结构的基本原理 基本知识和基本技巧 解决某一具体的 实际问题 培养我们综合分析和解决问题的能力 为今后分析 设计 开发和 调试程序打下坚实的基础 2 设计思路设计思路 2 1 课程设计思想课程设计思想 2 1 1 设计内容设计内容 用 C 语言实现各种查找算法的想法来源于生活和工作中的需要 如今 随 着社会的飞速发展 信息时代改变着人们的各种生活方式 人们的联系信息 联系方式变得复杂而多样化 人们的日常生活中也要求各类查找 由于传统的 查找不方便 功能单一等缺陷已经无法胜任它的 时代使命 因而 用计算机 编程来实现各种查找方法已成为时代的迫切需要 此程序只是一个初步构想 可以将其应用到人们日常生活中的各种查找 很有现实意义 用 C 语言实现各类查找 它的内容对于电子产品来说是至关重要的 它能 够为电子产品的使用者提供充足的信息和快捷的查询手段 用 Visual C 6 0 构 建的各种查找方法 包括顺序查找 二分查找 二叉排序树 哈希查找等 本 程序设计合理 操作方便 运行稳定 功能完备 具有较高的实用价值 4 2 1 2 设计要求设计要求 查找同人们每天的生活和工作息息相关 例如从电话号码本中查找某个电 话号码 从成绩表中查找某个同学的成绩等 对于小规模的查找可以使用人力 对于大规模的查找活动使用计算机会更快 更准确 因此 理解并会应用各种 查找算法非常重要 本程序融合顺序查找 二分查找 二叉排序树 哈希算法 等多种查找方法 我们可以从中比较并依据不同数据的特点使用不同的查找方 法 具有较高的实用价值 本程序需要包括四大块包括 顺序查找 二分查找 二叉排序树 哈希查 找 本程序根据实际生活的需要 满足各方的要求 因此 运用空间还可进一 步提高 在课程设计中 程序的开发平台是 Windows XP 程序设计语言采用 C 语言 程序应用平台为 Windows 2000 XP 采用自定义函数 数组和结构体 来解决管理系统中的各种问题 2 2 功能需求功能需求 要求完成以下功能 1 顺序查找子模块的实现 2 二分查找法的实现 3 二叉顺序树的实现 4 哈希查找的实现 2 3 软硬件运行环境及开发工具软硬件运行环境及开发工具 VC 6 0 windows XP 操作系统 PC 3 过程论述过程论述 3 1 概要设计概要设计 3 1 1 自定义数据类型自定义数据类型 通过四个自定义函数 printSeq printBin printTree printHash 简化了主菜单 使其更加简洁明了 同时采用模块化的结果 是程序更加清 晰 增强了它的易读性 3 1 2 系统流程图系统流程图 系统需要实现顺序查找 二分查找 二叉排序树 哈希查找四个模块 其 5 中这四个模块又由其子程序实现 如图 3 1 所示 图 3 1 功能模块图 系统功能图如图 3 2 所示 图3 2 系统流程图 开始 选择按钮 顺序表 的查找 输 入 关 键 字 序 列 输 入 待 查 关 键 字 输 出 查 找 结 果 有序表 的查找 输 入 表 长 输 出 查 找 结 果 输 入 待 查 关 键 字 输 出 查 找 结 果 二叉排序树 的查找 输 入 结 点 个 数 输 入 关 键 字 序 列 输 入 待 查 关 键 字 输 入 关 键 字 序 列 哈希表开放地址 法的查找 输 入 关 键 字 个 数 输 入 关 键 字 序 列 输 出 创 建 哈 希 表 输 入 待 查 关 键 字 输 出 查 找 结 果 退出 退 出 程 序 输 入 表 长 6 3 2 详细设计详细设计 3 2 1 顺序查找子模块的实现顺序查找子模块的实现 顺序查找包括建立顺序表 输入表中数据 打印查找表 用哨兵查找法查 找等几个内容 通过自定义函数 最终实现顺序查找的目的 首先输入元素个数 然后输入这几个元素的值 用户再输入需要查询的数 字即可得出查找结果 如果查找成功则显示出关键字所在的位置 否则显 示 查找失败 表中无此数据 如图 3 3 所示 代码如下 typedef int ElemType 顺序存储结构 typedef struct ElemType elem 数据元素存储空间基址 建表时按实际长度分配 号 单元留空 输入 1 进入顺序查找功能 输入元素个数 判断是否在表中 输出 查找失败 表中无此数据 输出此元素在表中的位置 输入各个元素的值 输入要查找的关键字的值 7 int length 表的长度 SSTable void Create SSTable table int length void Destroy SSTable table int Search Seq SSTable table ElemType key void Traverse SSTable table void visit ElemType elem 构建顺序表 void Create SSTable table int length SSTable t SSTable malloc sizeof SSTable 分配空间 t elem ElemType malloc sizeof ElemType length 1 t length length table t 3 2 2 二分查找子模块的实现 二分查找子模块的实现 二分查找法又叫折半查找法 它需要把无序表变为有序表 用 Sort SSTable table 函数实现 之后再进行查找 设定 3 个变量 low mid 和 high 以实现二分查找法的功能 折半查找过程是以处于区间中间位置记录 的关键字和给定值比较 若相等 则查找成功 若不等 则缩小范围 直至新 的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时为止 通过主菜单按键选择 2 进入二分查找功能 根据提示输入元素个数 再输 入这几个值 然后输入要查找的关键字 系统排序后会显示该关键字在顺序表 中的位置 否则显示 查找失败 表中无此数据 如图 3 4 所示 8 图 3 4 代码如下 int Search Seq SSTable table ElemType key table elem 0 key 设置哨兵 int result 0 找不到时 返回 int i for i table length i 1 i Y N 输入 2 进入二分查找功能 判断是否在表中 输出 查找失败 表中无此数据 输出在顺序表中的位置 输入元素个数 输入各个元素的值 输入要查找的关键字的值 按从小到大的顺序排序 9 if table elem i key result i break return result 返回结果 3 2 3 二叉排序树子模块的实现 二叉排序树子模块的实现 从主菜单进入二叉排序树功能 用户可根据提示输入相应信息 包括二叉 排序树的建立 输出 插入 删除 查找等 可以充分利用二叉排序树的特点 实现查找的功能 可以提高查找效率 通过主菜单按键选择 3 进入二叉排序树功能 根据提示建立二叉排序树 然后进入二叉排序树的菜单 通过数字选择想要实现的功能 中序输出 插 入一个节点 删除一个结点 查找一个结点等 3 2 4 哈希查找子模块的实现 哈希查找子模块的实现 从主菜单进入哈希查找功能 根据除留余数法构建哈希表 用二次探测法 解决冲 用 SearHash HashTable H int key int p 函数进行查找 通过主菜单按键选择 4 进入哈希查找功能 根据提示输入元素个数 再输 入这几个值 然后输入要查找的关键字 如果查找成功则显示存在此元素 否 则显示 不存在此元素 如图 3 5 所示 10 图 3 5 代码如下 void InitHash HashTable H 创建哈希表 int i H elem Elemtype malloc MAX sizeof Elemtype H count 0 H sizeindex MAX for i 0 ielem i num 0 初始化 使 SearHash 函数能判断到底有没有元素 输入 4 进入顺序查找功能 输入元素个数 判断是否在表中 输出 不存在此 元素 输出 查找成功 输入各个元素的值 输入要查找的关键字的值 N Y 11 在里面 int SearHash HashTable H int key int p 查找函数 p Hash key while H elem p num key if H elem p num key return 1 else return 0 void InsertHash HashTable H Elemtype e 如果查找不到就插入元素 int p SearHash H e num 查找 H elem p e H count 4 程序测试结果程序测试结果 1首主菜单 首先出现主菜单 通过选择相应数字进行相应功能的实现 如 图4 1所示 12 图4 1 主菜单 2 通过主菜单按键选择1进入顺序查找功能 输入元素个数 然后输入这 几个元素的值 用户再输入需要查询的数字即可得出查找结果 如果查找成功 则显示出关键字所在的位置 否则显示 查找失败 表中无此数据 图4 2所 示 图4 2 顺序查找 13 3 通过主菜单按键选择2进入二分查找功能 根据提示输入元素个数 再 输入这几个值 然后输入要查找的关键字 系统排序后会显示该关键字在顺序 表中的位置 否则显示 查找失败 表中无此数据 如图4 3所示 图4 3 查询功能 4 a 通过主菜单按键选择3进入二叉排序树功能 首先输入结点个数及结 点的值建立二叉排序树 然后便进入一个菜单提示选择二叉排序树的某个功能 如图4 4所示 14 图4 4 二叉排序树功能菜单 b 中序遍历二叉排序树 如图4 5所示 图4 5 中序遍历二叉排序树 c 插入一个结点 如图4 6所示 15 图4 6 二叉排序树插入一个结点 d 删除一个结点 如图4 7所示 图4 7 二叉排序树删除一个结点 e 查找一个结点 如图4 8所示 16 图4 8 二叉排序树查找一个结点 5 通过主菜单按键选择4进入哈希查找功能 根据提示输入元素个数 再 输入这几个值 然后输入要查找的关键字 找到则显示 查找成功 否则显 示 不存在此元素 如图4 9所示 图4 9 哈希查找法 17 5 总结总结 做了一个月的课程设计 基本上已经完成 在这次程序设计的课程中 让 我获益匪浅 在我逐步完成课程设计的过程中 我对程序的编写逐渐加大了兴 趣 由于我是由经管系跨系升本过来的一员 对于 C 语言和数据结构都算不上 真正的懂 对树上稍微难的知识就不甚了解 对一些程序的理解 也不甚明白 但是我尝试改变老师所讲程序的一些变量 自己尽最大努力的去理解老师做程 序的思路 在课程设计刚开始时 面临一系列的问题 我感到束手无策 只能 向杨老师以及其他同学请教 在杨老师细心的指导和同学们的帮助下 基本上 完成了本次的课程设计内容 在这里 我要对杨老师以及同学们表示深深的感 谢 本课题基本实现了综合查找的基本功能 通过这次试验 我发现书本知识 是一个基础 但是我的基础掌握的很不牢固 在写程序的时候 返现自己的专 业知识很是匮乏 对很多基础知识都只是有一个模糊的概念 不能落实到程序 上 基本上是涉及到一个知识点 就要去翻书查找 这主要是因为我对于老师 上课讲到的内容掌握很不牢固 平时的联系又特别的少 不断的编写过程就是 我不断的学习的过程 当摆在自己面前的问题一个个被解决时 南中心里的满 足感 收获感 以及对于之前学习不认真的羞耻感是无以言表的 这次课程设计 让我对原有的知识从表面的了解深入到本质 从个体学习 跳跃到了本质 加深了对新知识的汲取 学会了把课本知识应用于实际 让我 更深一层次的了解了 书到用时方恨少 增加我学习的自信以及学习的动力 通过这次课程设计 我收获匪浅 由衷的感谢老师提供了这样的一个锻炼 自我的机会 让我深深的感受到不是所有的知识都是用来完成试卷的 这次课 程设计让一贯独立思考的我学会了积极的与同学 老师 朋友们交流 取长补 短 共同进步 再次拜谢指导老师和同学朋友们 参考文献参考文献 1 刘怀亮编著 数据结构 C 程序 北京 冶金工业出版社 2004 2 严蔚敏 吴伟民编著 数据结构 C 语言版 北京 清华大学出版社 1997 3 杨路明等编著 C 语言程序设计教程 北京 北京邮电大学出版社 2005 18 学生签名 填表日期 年 月 日 致谢 通过这一个月的忙碌和学习 本次课程设计基本圆满完成 作为一个 从经管学院跨专业的一名大学生 由于自身基础的不牢固以及经验的匮乏 课程设计期间有许多考虑不周全的地方 在这里我要衷心的感谢指导老师 杨传键的悉心指教 以及一起学习的同学们的支持 让我按时 保质保量 的完成了本次的课程设计 在课程设计期间 我遇到了许许多多的问题 我要感谢我的指导老师 杨传键老师给予的悉心帮助和细致的指导 我本身的弟子很薄弱 但是杨 老师仍然悉心的纠正期间我犯下的错误 杨老师专业的水平 治学的严谨 以及科学研究的精神将 永远是我学习的榜样 并将积极的影响我今后的 学习工作 感谢我大学期间传授我专业知识的所有老师 感谢老师们的谆 谆教诲 同时我还要感谢我所有的同窗好友 他们也给予了我无数的关心 与支持 让我在课程设计期间的生活充满了温暖和欢心 如果没有指导老 师杨老师的悉心指导以及同学们的帮助 此次的课程设计将变得无比困难 再次拜谢指导老师杨传健老师以及所有的同学们 19 指导教师评语指导教师评语 成绩评定成绩评定 20 指导教师签名 填表日期 年 月 日 附录附录 源代码源代码 include iostream include stdlib h include stdio h include malloc h define MAX 11 using namespace std typedef int ElemType 顺序存储结构 typedef struct ElemType elem 数据元素存储空间基址 建表时按实际长度分配 号 单元留空 int length 表的长度 SSTable void Create SSTable table int length void Destroy SSTable table int Search Seq SSTable table ElemType key void Traverse SSTable table void visit ElemType elem 构建顺序表 void Create SSTable table int length SSTable t SSTable malloc sizeof SSTable 分配空间 t elem ElemType malloc sizeof ElemType length 1 t length length table t 无序表的输入 void FillTable SSTable table 21 ElemType t table elem for 循环 输入各个元素 for int i 0 ilength i t scanf d t 输入元素 getchar 销毁表 void Destroy SSTable table free table elem 释放元素空间 free table 释放表的空间 打印查找表 void PrintTable SSTable table int i 定义变量 ElemType t table elem for i 0 ilength i 进入循环 依次打印表中元素 t printf d t 打印输出 printf n 哨兵查找算法 int Search Seq SSTable table ElemType key table elem 0 key 设置哨兵 int result 0 找不到时 返回 22 int i for i table length i 1 i if table elem i key result i break return result 返回结果 void printSeq 先设置几个变量 SSTable table int r int n ElemType key printf 请输入元素个数 scanf d 输入元素个数 Create 建立表 printf 请输入 cout 0 23 printf 关键字 d 在表中的位置是 d n key r 打印关键字在 表中的位置 printf n else 查找失败 printf 查找失败 表中无此数据 n n 排序算法 void Sort SSTable table int i j ElemType temp for i table length i 1 i 从前往后找 for j 1 jelem j table elem j 1 temp table elem j table elem j table elem j 1 table elem j 1 temp 二分法查找 非递归 int Search Bin SSTable table ElemType key int low 1 int high table length 24 int result 0 找不到时 返回 while low elem mid key 如果找到 result mid break else if keyelem mid 如果关键字小于 mid 对应的值 high mid 1 else 否则的话 low mid 1 return result 返回结果 void printBin 声明变量 SSTable table int r int n ElemType key printf 请输入元素个数 scanf d Create 建立表 25 printf 请输入 cout 0 printf 关键字 d 在表中的位置是 d n key r else printf 查找失败 表中无此数据 n n 二叉排序树 typedef struct BiTnode 定义二叉树节点 int data 节点的值 struct BiTnode lchild rchild 节点的左孩子 节点的右孩子 BiTnode BiTree 查找 根据节点的值查找 返回节点指针 BiTree search tree BiTree T int keyword BiTree father BiTree p 临时指针变量 father NULL 先设其父亲节点指向空 26 p T p 赋值为根节点 从根节点开始查找 while p 先将父亲指向自己 注意 这里传过来的 father 是二 级指针 if keyword data 如果要找的值小于自己的值 p p lchild 就向自己的左孩子开始找 else p p rchild 否则向自己的右孩子开始查找 return p 如果找到了则返回节点指针 BiTree creat tree int count BiTree T p 设置两个临时变量 T p int i 1 while i data 输入 p 指向节点的值 p lchild p rchild NULL p 的左孩子和右孩子都指向空 i else int temp 如果不是空树 27 scanf d 输入节点的值 search tree T temp 查找节点要插入的位置 T 是根节点 插入的节点的值 父亲节点的地址 if temp data 如果插入的值小于父亲节点的值 p lchild BiTnode malloc sizeof BiTnode 那么就 为父亲节点的左孩子分配一个节点空间 并指向这个空间 if p lchild return NULL p p lchild 分配成功 p 指向自己的左孩子 else 如果插入的值大于父亲节点的值 p rchild BiTnode malloc sizeof BiTnode if p rchild return NULL 分配不成功 退出 p p rchild p 指向自己的右孩子 p data temp 新分配的节点的值赋值为插入的值 p lchild p rchild NULL 使其左右节点均为 NULL i return T 返回根节点 void InOrder BiTree T if T InOrder T lchild printf d T data InOrder T rchild 28 int insert tree BiTree T int elem 插入 根节点 插入的值 返回 1 和 1 代表插入失败 代表成功 BiTree s p father s BiTnode malloc sizeof BiTnode s 指向新开辟一个节点 if s 为开辟成功 return 1 返回值 1 s data elem 新节点的值赋值为插入的值 s lchild s rchild NULL 其左右孩子为空 p search tree T elem p 赋值为要插入的节点 if p return 1 未开辟成功 返回 1 if father NULL 如果父亲节点指向空 说明是空树 T s 让根节点指向 s else if elem data 否则如果插入的值小于父亲的值 father lchild s 父亲的左孩子赋值为 s else father rchild s 否则父亲的右孩子赋值为 s return 0 返回 删除树结点的操作 int delete tree BiTree T int elem BiTree s p q father 声明变量 p search tree T elem 查找 if p return 1 if p lchild 如果 p 的左孩子为空 if father NULL 29 T p rchild T 指向左孩子 free p 释放 p return 0 if p father lchild 如果 p 和 father 的左孩子相等 father lchild p rchild 将 p 的左孩子的值赋给 father 的左孩子 else father rchild p rchild 将 p 的左孩子的值赋给 father 的 右孩子 free p 释放 p return 0 else if p rchild if father NULL 如果 father 为空 T p lchild 将 p 的左孩子赋给 T free p 释放 p return 0 if p father lchild 如果 p 等于 father 的左孩子的值 father lchild p lchild 将 p 的左孩子的值赋给 father 的左孩子 else father rchild p lchild 将 p 的左孩子的值赋给 father 的右孩子 free p return 0 else 30 q p s p lchild 将 p 的左孩子赋给 s while s rchild q s s s rchild p data s data 将 s 的值赋给 p if q p 如果 q 不等于 p q rchild s lchild 将 s 的左孩子值赋给 p 的右孩子 else q lchild s lchild 将 s 的左孩子值赋给 p 的右孩子 free s 释放 s return 0 定义 print1 以便调用 void print1 printf t n printf t1 输出中序遍历 n printf t2 插入一个结点 n printf t3 删除一个结点 n printf t4 查找一个结点 n printf t5 返回主菜单 n printf t n void printTree 声明变量 BiTree T p T NULL 31 int i n ElemType key printf 请输入结点个数 n scanf d 输入值 printf 请输入 cout n printf 个值 T creat tree n 建立树 print1 scanf d 输入各个值 while i 5 i 不等于 5 时 switch i case 1 printf 中序遍历二叉树结果如下 n InOrder T 中序遍历 break case 2 printf 请输入要插入的结点值 scanf d 输入要查找的关键字 if insert tree else printf 已存在此元素 break case 3 printf 请输入要删除的结点值 scanf d 输入要删除的关键字 if delete tree else printf 不存在此元素 break case 4 printf 请输入要查找的结点值 32 scanf d 输入要查找的关键字 if search tree T key else printf 不存在此元素 break default printf 按键错误 printf n print1 scanf d 哈希表 typedef struct int num Elemtype 定义查找的结点元素 typedef struct Elemtype elem 数据元素存储基址 int count 数据元素个数 int sizeindex HashT