




已阅读5页,还剩15页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构课程设计数据结构课程设计 课程名称 查 找 院 系 信息工程学院 年级专业 学 号 学生姓名 指导教师 开题时间 2010 年 12 月 11 日 完成时间 2010 年 12 月 19 日 信 息 工 程 学 院 安徽新华学院课程设计成绩评定表 数据结构 课程设计 查找 第 1 页 共 20 页 课题名称查 找 院 系信息工程学院年级专业计算机科学与技术 学 号10062151016姓 名 课题设计 目的与 设计意义 本课程设计的主要目的是 使学生学会利用在课堂中学过的 理论知识 解决相应的实际问题 深入理解和灵活掌握所学的内 容 培养学生理论和实践相结合的能力 培养学生分析问题解决 问题的能力 同时 在实验步骤规范化 程序设计方法等方面受 到比较系统和规范化的训练 通过实践设计使学生进一步加深程 序设计的规范化及对复杂程序设计步骤的理解 成 绩 指导教师 年 月 日 数据结构 课程设计 查找 第 2 页 共 20 页 摘要 在日常生活中 人们几乎每天都要进行查找工作 例如 在通讯 簿中查阅某人的通信地址 或在字典中查阅某字的读音等 查找是一种在生活 中大量使用的数据结构 查找表是由同一类型的数据元素构成的集合 在各种 系统软件和应用软件中 查找表也是一种最常见的结构之一 如编译程序中的 符号表 信息处理系统中的信息表均是查找表 查找表是一种非常灵便的数据 结构 采用何种查找方法 首先取决于使用那种数据结构来表示 表 为了 提高查找速度 我们常常用某些特殊的数据结构来组织表 因此 在研究各种 查找方法时 首先必须弄清楚这些方法所需的数据结构 特别是存储结构 下 面分别就线性表 树表和哈希表三种数据结构的查找来讨论查找表的表示和操 作实现的方法 数据结构 课程设计 查找 第 3 页 共 20 页 目目 录录 一一 实践目的与要求实践目的与要求 4 1 1 实践目的 4 1 2 实践要求 4 二二 顺序查找的分析 程序 及运行结果顺序查找的分析 程序 及运行结果 4 2 1 系统简介 4 2 2 设计思路 4 2 3 顺序查找算法描述 5 2 4 运行结果 6 三三 折半查找的分析 程序 及运行结果折半查找的分析 程序 及运行结果 6 3 1 系统简介 6 3 2 设计思路 6 3 3 折半查找算法描述 7 3 4 运行结果 8 四四 二叉排序树查找的分析 程序 及运行结果二叉排序树查找的分析 程序 及运行结果 8 4 1 系统简介 8 4 2 设计思路 8 4 3 二叉排序树算法描述 9 4 4 运行结果 11 五五 哈希查找的分析 程序 及运行结果哈希查找的分析 程序 及运行结果 12 5 1 系统简介 12 5 2 设计思路 12 5 3 哈希查找算法描述 13 5 4 运行结果 15 六六 致谢致谢 15 七七 附录 附录 16 八八 参考文献参考文献 19 数据结构 课程设计 查找 第 4 页 共 20 页 一一 实践目的与要求实践目的与要求 1 11 1 实践目的实践目的 1 掌握各种查找算法的思想及其使用条件 2 掌握上机实现各种查找算法的基本思想 3 熟练掌握二叉排序树的构造和查找方法 4 掌握散列表存储结构的思想 能选择合适的散列表函数 实现不 同冲突处理方法的散列表的查找与建立 1 21 2 实践要求实践要求 1 掌握实践是算法 2 上机运行程序 保存和打印运行结果 并结合程序进行分析 3 注意理解折半查找的适用条件 4 建立二叉排序树 散列表是相同元素的处理 5 比较各种查找算法的各自特点 能够结合实际情况选择合适的查 找方式 二二 顺序查找顺序查找的分析 程序 及运行结果的分析 程序 及运行结果 2 12 1 系统简介系统简介 一次输入顺序表中的各个元素 然后进行关键字查找 如果存在则返回待 查元素的位置 2 22 2 设计思路设计思路 1 顺序查找的思想 数据结构 课程设计 查找 第 5 页 共 20 页 对于给定的关键字 K 从表中的一端开始 逐个进行数据元素的关键字和 给定值的比较 若当前扫描到的关键字与 K 相等则查找成功 若扫描结束后 仍未找到关键字等于 K 的节点 则查找失败 建立一个顺序表 数据元素从下标为 1 的单元开始放入 下标为 0 的元素 起哨兵作用 将待查的关键字存入下标为 0 的单元 顺序表从后向前查找 若 直到下标为 0 时才找到关键字则说明查找失败 若不到下标为 0 时就找到关键 字 则查找成功 2 32 3 顺序查找算法描述顺序查找算法描述 顺序表结构体定义 typedef struct keytype key maxsize int len stable 建立线性表 stable create s stable r int i j 0 k 1 printf 请输入顺序表元素 要为整形 用空格分开 99 为结束标志 n scanf d while i 99 j r key k i k scanf d r len j return r 顺序表查找 int search s keytype k stable r int j 数据结构 课程设计 查找 第 6 页 共 20 页 j r len r key 0 k while r key j k j return j 2 42 4 运行结果运行结果 三三 折半查找折半查找的分析 程序 及运行结果的分析 程序 及运行结果 3 13 1 系统简介系统简介 一次输入顺序表中的各个元素 然后进行关键字查找 如果存在则返回 待查元素的位置 否则显示不存在 数据结构 课程设计 查找 第 7 页 共 20 页 3 23 2 设计思路设计思路 1 折半查找的基本思想 设查找表中的元素存放在数组 r 中 数据元素的下标范围为 low high 查找 的关键字值为 key 中间元素的下标为 mid low high 2 向下取整 令 key 与 r mid 的关键字比较 若 key r mid key 查找成功 下标为 m 的记录即为所求 返回 mid 若 keyr mid key 所要找的记录只能在右半部分记录中 在对右半部分记 录中 再对右半部分使用折半查找法继续进行查找 搜索区间缩小一半 重复上述过程 直到找到查找表中某个数据元素的关键字的值等于给定的 值 key 说明查找成功 若出现 low 的值大于 high 的情况 说明查找不成功 建立一个有序表 数据元素从下标为 1 的单元开始放入 实现查找算法时 首先将 low 赋值为 1 high 等于最后一个数据元素的下标 然后将给定的关键 字与查找区间 low high 中间的数据元素的关键字比较 实现查找过程 3 33 3 折半查找算法描述折半查找算法描述 顺序表结构体定义 typedef struct keytype key maxsize int len stable 折半查找 int search bin keytype k stable r int low high mid low 1 high r len 数据结构 课程设计 查找 第 8 页 共 20 页 while lowkey mid return mid else if kkey mid high mid 1 else low mid 1 return 0 3 43 4 运行结果运行结果 四四 二叉排序树查找的分析 程序 及运行结果二叉排序树查找的分析 程序 及运行结果 4 14 1 系统简介系统简介 依次输入关键字并建立二叉排序树 实现二叉排序树的插入和查找功能 数据结构 课程设计 查找 第 9 页 共 20 页 4 24 2 设计思路设计思路 1 二叉排序树的基本思想 二叉排序树就是将原来的数据根据大小构成一棵二叉树 二叉树中的所有 节点数据满足一定的大小关系 所有的左自述中的节点均比根节点小 所有的 右子树的节点均比根结点大 二叉排序树查找是指按照二叉排序树中结点的关系进行查找 查找的关键 字首先同根结点比较 如果相等则查找成功 如果比根结点小 则在左子树中 查找 如果比根结点大 则在右子树中查找 这种查找方法可以快速缩小查找 范围 大大减小查找关键字的比较次数 从而提高查找效率 2 算法分析 算法的关键过程实际上就是二叉排序树的创建和查找两个步骤 首先创建 一个根结点 第二步就是将其他结点不断插入到二叉树中的合适位置 二叉排 序树进行结点插入时 首先要为结点寻找合适的位置插入 这个过程实际上就 是关键字不断比较的过程 如果比根结点小 则在左子树中插入 如果比根结 点大 则在右子树中插入 然后在二叉排序树中查找关键字的结点存在 4 34 3 二叉排序树算法描述二叉排序树算法描述 二叉排序树结构体定义 typedef struct bsnode keytype data struct bsnode lchild struct bsnode rchild bnode bnode bsp bnode bst 为关键字 key 建立一个二叉排序树结点 数据结构 课程设计 查找 第 10 页 共 20 页 bnode createbst keytype key bnode s s bnode malloc sizeof bst s data key s lchild s rchild NULL return s 将 s 指向的结点插入到 t 指向的二叉树中 bnode bstinsert bnode t bnode s bnode q p if t NULL return s else p t q NULL while p q p if s data p data printf 这个数 d 已存在 s data return t if s datadata p p lchild else p p rchild if s datadata q lchild s else q rchild s return t 输出二叉排序树 void bstprint bnode t if t 数据结构 课程设计 查找 第 11 页 共 20 页 bstprint t lchild printf d t data bstprint t rchild 在二叉排序树中查找关键字 void search bnode t keytype x bnode p if t NULL printf error n return else p t while p if p data x printf search success n return else if xdata p p lchild else p p rchild if p printf d not exist n x 4 44 4 运行结果运行结果 数据结构 课程设计 查找 第 12 页 共 20 页 五五 哈希查找的分析 程序 及运行结果哈希查找的分析 程序 及运行结果 5 15 1 系统简介系统简介 依次输入关键字并建立哈希表 进行关键字查找 如果存在则返回待查元 素的位置 否则显示不存在 5 25 2 设计思路设计思路 1 哈希表查找基本思想 它是通过记录中的关键字值 key 为自变量 通过 某一个特定的函数 h 计 算出函数值 h key 作为存储地址 而查找时也用这个函数 h 进行计算 获得所 要查找关键字所在记录的存储位置 除留余数法是用关键字 key 除以某个正整数 M 所得余数作为哈希地址的 方法 哈希函数 h key key M 一般 M 的取值为不大于表长的质数 数据结构 课程设计 查找 第 13 页 共 20 页 用开放地址法解决冲突 形成下一个地址的形式时 Hi h key di M i 1 2 k k k m 1 H key 为哈希函数 M 为正整数 di 为增量序列 m 为表长 线性探测再散列是将开放地址法中的增量序列 di 设定为从 1 开始一直到表 长减 1 的整数序列 1 2 3 m 1 2 算法分析 算法的关键过程实际上就是 Hash 表的创建和查找两个步骤 其中查找时利用除留余数法构造哈希函数 h 计算出函数值获得所要查找 的关键字的存储位置 若存储位置对应的数据元素的值和查找关键字相等 则 查找成功 否则 采用线性探测法从关键字的哈希地址开始向后扫描 直到找 到与关键字相等的数据元素 查找成功 若查找到最后还没找到关键字 则查 找失败 不存在与关键字相等的数据元素 5 35 3 哈希查找算法描述哈希查找算法描述 哈希表结构体定义 typedef struct keytype key int cn hashtable 哈希函数 int h keytype key return key m 哈希表查找函数 int hashsearch hashtable ht keytype key int d i i 0 数据结构 课程设计 查找 第 14 页 共 20 页 d h key ht d cn 0 while ht d key key return unsucess return d 插入函数 查找不成功就将 key 插入哈希表 int hashinsert hashtable ht keytype key int d d hashsearch ht key if ht d key 0 ht d key key return sucess else printf unsuccess n return unsucess 建立哈希表函数 void hashcreate hashtable ht int i n keytype key1 printf 请输入元素个数要小于表长 d n hm scanf d printf 请输入元素关键字 n for i 0 i n i scanf d hashinsert ht key1 数据结构 课程设计 查找 第 15 页 共 20 页 5 45 4 运行结果运行结果 六六 致谢致谢 从接受课题到现在完成课程设计报告 衷心的感谢我们的指导余云老师给予 了精心的指导和热情的帮助 从老师那里学到了很多知识 尤其在课题设计的前 期准备阶段和我们在编写程序中遇到的问题 余老师给予了纠正和提出了许多 宝贵的设计意见 使我们对整个课程设计的流程比较清楚做起来也方便多了 老 师在百忙之中抽出时间为我们提供了很多很及时的帮助 这样使得我得以顺利的 完成本次课程设计 老师渊博的知识 敏锐的思路和实事求是的工作作风给我们 留下了深刻的印象 这将使我终身受益 谨此向老师表示衷心的感谢和崇高的敬 意 同时还感谢那些在各个方面给过我帮助的人 谢谢大家 数据结构 课程设计 查找 第 16 页 共 20 页 七七 附录 附录 include include define keytype int define maxsize 100 define hm 20 define m 19 define free 0 define sucess 1 define unsucess 0 void main stable a bnode t s hashtable ht hm int i 0 k n keytype key int flag 1 t NULL while flag printf 请输入查找方式 n printf 1 顺序查找 n printf 2 折半查找 n printf 3 在二叉排序树中查找 n printf 4 哈希查找 n printf 5 退出 n scanf d switch n case 1 a create s a while i 1 printf n 输入待查关键字 scanf d k search s i if i 1 break if k 0 数据结构 课程设计 查找 第 17 页 共 20 页 printf 顺序表中待查元素不存在 n else printf 顺序表中待查元素位置是 d k printf n break case 2 a create s a while i 1 printf n 输入待查关键字 scanf d k search bin i if i 1 break if k 0 printf 顺序表中待查元素不存在 n else printf 顺序表中待查元素位置是 d
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大专财经考试题及答案大全
- 大数据导论考试题及答案
- 剪辑考试试题及答案网盘
- 暑假班安全协议书
- 传播理论考试题目及答案
- 2025年中国氯铂酸铵项目商业计划书
- 环卫安全考试试题及答案
- 2月LA技师上岗证练习习题(含参考答案)
- 中国煤制丙烯项目投资计划书
- 2025年仓储安全管理实务冲刺押题试卷
- 膀胱中医学课件
- 入团考试试题及答案大全
- 2024全员安全生产“大学习、大培训、大考试”考试题库(含答案)
- 电焊作业高空作业危险点及控制措施
- 内审员培训资料
- 2025至2030中国直链烷基苯行业投资风险及供需态势趋势预测报告
- 固碳增汇策略-洞察及研究
- 新生儿臀部护理与纸尿裤使用指南
- 余料使用管理制度
- 解三角形中四边形周长(边长)和面积问题(中上难度)
- 回收电池仓库管理制度
评论
0/150
提交评论