快速排序与二分查找-实验四

电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 1 页 电电 子子 科科 技技 大大 学学 实实 验验 报报 告告 课程名称 课程名称 数据结构与算法数据结构与算法 学生姓名 学生姓名 陈陈 浩浩 学学 号 号 点名序号 点名序号 指导教师 指导教师 钱钱 实验地点 实验地点 基础实验大楼基础实验大楼 A508 实验时间 实验时间 2015 6 3 2014 2015 2 学期学期 信息与软件工程学院信息与软件工程学院 电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 2 页 实实 验验 报报 告告 四四 学生姓名 陈学生姓名 陈 浩浩 学学 号 号 导教师 钱导教师 钱 实验地点 基础实验大楼实验地点 基础实验大楼 A508 实验时间 实验时间 2015 6 3 一 一 实验室名称 实验室名称 软件实验室 二 二 实验项目名称 实验项目名称 数据结构与算法 快速排序与二分查找 三 三 实验学时 实验学时 4 四 实验原理 四 实验原理 快速排序的基本思想是 通过一躺排序将要排序的数据分割成独立的两部分 其中一部 分的所有数据都比另外一不部分的所有数据都要小 然后再按次方法对这两部分数据分别 进行快速排序 整个排序过程可以递归进行 以此达到整个数据变成有序序列 假设要排序的数组是 A 1 A N 首先任意选取一个数据 通常选用第一个数据 作为关键数据 然后将所有比它的数都放到它前面 所有比它大的数都放到它后面 这个 过程称为一躺快速排序 一躺快速排序的算法是 1 设置两个变量 I J 排序开始的时候 I 1 J N 2 以第一个数组元素作为关键数据 赋值给 X 即 X A 1 3 从 J 开始向前搜索 即 J J 1 找到第一个小于 X 的值 两者交换 4 从 I 开始向后搜索 即 I I 1 找到第一个大于 X 的值 两者交换 5 重复第 3 4 步 直到 I J 二分法查找 折半查找 的基本思想 1 确定该区间的中点位置 mid low high 2 min 代表区间中间的结点的位置 low 代表区间最左结点位置 high 代表区间最右结点位 置 2 将待查 a 值与结点 mid 的关键字 下面用 R mid key 比较 若相等 则查找成 功 否则确定新的查找区间 A 如果 R mid key a 则由表的有序性可知 R mid key 右侧的值都大于 a 所以等于 a 的关键字如果存在 必然在 R mid key 左边的表中 这时 high mid 1 B 如果 R mid key a 则等于 a 的关键字如果存在 必然在 R mid key 右边的表中 这 时 low mid C 如果 R mid key a 则查找成功 3 下一次查找针对新的查找区间 重复步骤 1 和 2 4 在查找过程中 low 逐步增加 high 逐步减少 如果 high low 则查找失败 五 实验目的 五 实验目的 本实验通过实现快速排序和折半查找算法 使学生理解如何实现快速查 找和排序的基本算法思想 通过练习 加强对算法的理解 提高编程能力 电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 3 页 六 实验内容 六 实验内容 1 实现数据序列的输入 2 实现快速排序算法 并对输入的序列排序后输出 3 实现折半查找算法 并在步骤 2 排序后的序列上 进行任意 地 查找 并输出查询结果 七 实验器材 设备 元器件 七 实验器材 设备 元器件 PC 机一台 装有 C C 语言集成开发环境 八 数据结构及程序八 数据结构及程序 快速查找与二分排序快速查找与二分排序 陈家浩陈家浩 2015 6 6 include define MAX 100 int Data MAX 1 0 int Quick Part int Data int i int j 一趟排序一趟排序 int Quick Sort int Data int s int t 递归排序递归排序 int Quick Find int Data int data int n 二分查找二分查找 int main void int choose 1 选择功能选择功能 int i k data int n 数据序列长度数据序列长度 while 1 printf 排序与查找排序与查找 n 1 输入数据序列输入数据序列 n 电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 4 页 2 序列排序序列排序 n 3 查找信息查找信息 n 0 退出退出 n n 请选择 请选择 scanf d switch choose case 1 printf 请输入序列数据个数 请输入序列数据个数 scanf d if n MAX printf 数据过多数据过多 n n break else printf 请输入数据序列 请输入数据序列 n for i 1 i n i scanf d printf 读取成功 读取成功 n n break case 2 Quick Sort Data 1 n 快速排序快速排序 printf 排序成功 序列如下 排序成功 序列如下 n for i 1 i n i printf d Data i printf n n break case 3 printf 请输入待查找的数据 请输入待查找的数据 scanf d k Quick Find Data data n 二分法查找二分法查找 if k printf 查找成功 数据查找成功 数据 d 位于序列第位于序列第 d 位 位 n n data k else printf 查找失败 没有你要查找的数据 查找失败 没有你要查找的数据 n n break default return 0 电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 5 页 int Quick Part int Data int i int j 快速排序快速排序 Data 0 Data i while i j while i j 右边目标元比划分元大 右边目标元比划分元大 j 往左移往左移 if i j Data i Data j 比划分元小的关键字交换到左边比划分元小的关键字交换到左边 i while i Data i i 左边目标元比划分元小 左边目标元比划分元小 i 往右移往右移 if i s Quick Sort Data s i 1 递归调用排序递归调用排序 if i t Quick Sort Data i 1 t 递归调用排序递归调用排序 return 0 int Quick Find int Data int data int n 二分查找二分查找 int low 1 int high n int mid while low Data mid low mid 1 else high mid 1 return 0 查找失败返回查找失败返回 0 九 程序运行结果 九 程序运行结果 电子科技大学信息与软件工程学院实验报告电子科技大学信息与软件工程学院实验报告 第 7 页 十 实验结论 十 实验结论 通过实现快速排序和折半查找算法 基本达到了实验目的 快速排序的基 本思想是每次确定一个划分元 将比划分元大的数据存储到划分元右边 比他 小的存储到他左边 通过递归排序实现整个顺序表的排序 然而 其中的递归 调用很难 需要思考其中参数的变化 这需要细心 十一 总结及心得体会 十一 总结及心得体会 1 对错误输入的解决方案还有待完善 2 快速排序递归调用结束的条件需要慎重考虑 否则极易