没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
广州大学学生实验报告
开课实验室:计算机科学与工程实验(电子楼 517)
学院
计 算 机 科 学
与 网 络 工 程
学院
年级、
专业、
班
姓名 学号
实验课程 数据结构实验 成绩
实验项目 实验四 查找和排序算法实现
指导
老师
一、 实验目的:
1、各种排序算法的实现
2、各种查找算法实现
二、 使用仪器、器材
微机一台
操作系统:WIN10
编程软件:C++
三、 实验内容及原理
1、各种排序算法的实现
用随机函数生成 16 个 2 位正整数(10~99),实现插入排序、选择排序、冒泡排序、
双向冒泡、快速排序、二路归并排序等多种排序算法,输出排序中间过程、统计关键字
的比较次数和记录的移动次数。
插入排序:
在有序序列中插入一个元素,保持序列有序,有序长度不断增加:起初 a[0]是长
度为 1 的子序列;然后,逐一将 a[1]至 a[n-1]插入到有序子序列中;在插入 a[i]之
前,数组 a 的前半段(a[0]~a[i-1])是有序段,后半段(a[i]~a[n-1])是停留于输入
次 序 的 “无序段 ” ; 插 入 a[i] 使 a[0]~a[i-1] 有 序 , 也 就 是 要 为 a[i] 找 到 有 序 位 置
j(0<=j<=i),将 a[i]插入在 a[j]的位置上。
使用直接插入排序的方法,采用顺序查找法查找插入位置,在未完成排序的序列
中,选择第一个元素,插入到有序序列当中,需要查找它的插入位置,将该位置后的元
素往后移,腾出一个控件给插入的元素。若直接往后移,会产生元素被覆盖的问题,需
要建立一个临时的空间复制保留这个插入的元素,即使用“哨兵”:数组的第一个空间不
存放数据,用来临时存放插入的元素;
选择排序:
在待排序的数据中选出最大(小)的元素放在其最终的位置:首先通过 n-1 次关键
字比较,从 n 个记录中找出关键字最小的记录,将它与第一个记录交换;再通过 n-2 此
比较,从剩余的 n-1 个记录中找出关键字次小的记录,将它与第二个记录交换;重复上
述操作,共进行 n-1 趟排序后,排序结束;
冒泡排序:
每趟不断将记录两两比较,并按“小在前大在后”的规则交换:首先将第一个记录的
关键字与第二个关键字比较,若为逆序,即“大在前小在后”,则交换这两个记录,继续
比较第二个记录和第三个记录,依次类推,直至第 n-1 个记录和第 n 个记录为止,完成
第一趟排序,使得最大的记录被安置在最后一个记录的位置上;然后进行第二趟冒泡排
序,对前 n-1 个数据进行相同的操作,其结果使关键字次大的记录被安置到第 n-1 个记
录的位置上;重复上述的过程,直到整个序列都已达到排序的要求,不再存在交换记录
的操作,且 n 个数据,需要 n-1 趟的冒泡排序;
另外可以再设置一个 ag 进行辅助判断,若 ag 为 ase 时说明本趟排序并未发
生交换,则不会再执行下一趟排序;
双向冒泡排序:
双向冒泡排序的原则和方法与普通冒泡排序的相似,而普通冒泡是单向进行的。
双向冒泡则首先让气泡排序由左向右进行扫描,不断将记录两两比较,并按“小在
前大在后”的规则交换,将第一个记录的关键字与第二个关键字比较,若为逆序,即“大
在前小在后”,则交换这两个记录,继续比较第二个记录和第三个记录,依次类推,直
至第 n-1 个记录和第 n 个记录为止,使得最大的记录被安置在最后一个记录的位置上,
用序列的长度作为该次排序的记录,完成一次排序后减 1;再来让气泡排序由右往左进
行扫描,将未完成排序的序列的最后一个记录的关键字与其前一个关键字比较,并按
“小在前大在后”的规则交换,若为逆序,则交换这两个记录,继续往前进行比较,依次
类推,直至第 1 个记录和第 2 个记录为止,使得最小的记录被安置在第一个记录的位置
上,用 1 作为该次排序的记录,完成一次排序后加 1。分别完成由左向右和由右向左的
排序即完成第一趟排序。重复上述的过程,直到整个序列都已达到排序的要求,即由左
向右的排序记录小于或等于由右向左的排序记录;
快速排序:
在需要排序的数据中任取一个元素(例如:第一个)作为中心,即枢轴或支点,将
所有比它小的元素一律放在其前方,其余的放在其后方,形成左右两个子表;再使用递
归的思想,对各个子表重新选择中心元素并依此规则调整,直至每一个子表的元素只剩
一个,作为递归结束的条件,最后使得整个序列有序。
将中心点放入“哨兵”空间,即第 0 号空间的位置,作为一个分界点,分别用 low 和
high 表示要排序的区间,初始时 low 指向第一个位置,high 指向最后一个位置,由于
将中心点(第一个元素)搬入了“哨兵”空间,前面空了一个空间,所以从 high 指向的
位置开始进行排序,若 high 指向的值比中心点的值小则搬入前面空的空间,否则继续
往前进行寻找;当 high 指向的位置搬走后则为空,则重新回到 low 指向的位置,若
low 指向的值比中心点小,则继续往后寻找,当 low 指向的值比中心点的大时将其搬入
high 指向的位置,即后方空的空间,再回到 high 指向的位置。重复上述操作,直至
high 和 low 指向的位置相同时,即找到了中心点的存放位置,将中心点的值放入该空
间中,通过上述操作将原来的表划分成了两个子表,再重复上述步骤对各个子表重新选
择中心元素并依此规则调整,直至每一个子表的元素只剩一个,完成序列的排序。
二路归并排序:
用递归地方法,将序列划分成左右两个序列,将两个位置相邻的有序子序列“归并”为
一个有序序列,若两个有序序列是放在同一数组中相邻的位置上:R[low,…,mid]和
R[mid+1,…,high]中,分别用 i,j 指向 R[low]位置和 R[mid+1]位置,分别将这两个
位置的元素进行比较,较小值放入 t[low,…,high]中,然后再寻找该值所在序列剩余的
值与另一序列进行比较,重复此过程,直至其中一个表为空,最后将另一非空表中余下
的部分直接复制到 t 中;
2、各种查找算法实现
( 1 ) 顺 序 查 找 : 使 用 数 组 或 链 表 结 构 。 用 随 机 函 数 生 成 16 个 不 重 复 的 字 母
(’a’~’z’),键盘输入待查找的字母,返回查找成功与否,若成功则返回该字母所在的
位置(序号),并计算比较次数。
使用数组结构:将这 16 个不重复的字母生成的数组放在一个有 17 个元素的存储空间
中,将第 0 号存储位置空出,这 16 个字母放在第 1 号到第 16 号的位置的位置上;第 0
号存储空间设计为“哨兵”,即监视哨,免去查找过程中每一步都要检测整个数组是否查
找完毕,即是否发生越界问题;进行从后往前进行查上找,即从后往前依次进行判断输
入待查找的字母与数组上的字母是否相等,若找到则放回该字母所在的位置的序号,若
无,则说明该字母不在该数组中,查找失败;
(2)折半查找:用数组实现,查找前元素先排序。计算比较次数。分别用查找成功、
不成功进行测试。
首先将随机生成的 16 个字母组成的数组进行冒泡排序,构成一个从左往右依次递增
的有序数组;最低端 low 的下标为 1,最高端 high 的下标为 16,通过(low+high)/2 得
到 mid 的下标为 8,将要查找的值与 mid 的下标对应的值进行比较,若相等,则查找成
功;若大于 mid 对应的值,则只需在 mid 之后的半区进行查找,即 low=mid+1;若小于
则只需在 mid 之前的半区进行查找,即 high=mid-1。重复上述过程,知道 low>high,若
仍查找不到该值,则说明查找失败。
(3)二叉查找树:手工输入 10 个字母,生成一棵二叉查找树,用递归算法打印树结构
或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母,计算比较次
数。分别用查找成功、不成功进行测试。
二叉查找树的定义:若左子树不空,则左子树上所有结点的值均小于它的根结点的
值;若右子树不空,则右子树上所有结点的值均大于或等于它的根节点的值;且它的
左、右子树也分别为二叉查找树;
输入待查找的字母后,从二叉查找树的根结点开始查找,若根节点不是要查找的值
剩余17页未读,继续阅读
资源评论
李阿伯
- 粉丝: 9
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功