数据结构 查找 课程设计最新.doc

数据结构课程设计数据结构课程设计 课程名称 查 找 院 系 信息工程学院 年级专业 学 号 学生姓名 指导教师 开题时间 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