实验四 查找和排序算法实现
广州大学学生实验报告开课实验室：计算机科学与工程实验（电子楼418A）学院计算机科学与网络工程学院实验课程数据结构实验实验项目实验四查找和排序算法实现一、实验目的：1、各种排序算法的实现2、各种查找算法实现二、使用仪器、器材微机一台操作系统：WinXP编程软件：C++三、实验内容及原理1、各种排序算法的实现用随机函数生成16个2位正整数（10~99），...
·
广州大学学生实验报告
开课实验室：计算机科学与工程实验（电子楼418A）
学院 计算机科学与网络工程学院
实验课程 数据结构实验
实验项目 实验四 查找和排序算法实现
- 一、实验目的：
1、各种排序算法的实现
2、各种查找算法实现 - 二、使用仪器、器材
微机一台
操作系统：WinXP
编程软件：C++ - 三、实验内容及原理
1、各种排序算法的实现 （返回目录🖱）
用随机函数生成16个2位正整数（10~99），实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种排序算法，输出排序中间过程、统计关键字的比较次数和记录的移动次数。
代码说明：各排序算法在同一个cpp文件中，老师要检查某个算法时可以把main函数中的相应排序算法的注释符号“//”去掉即可；
#include<iostream>
#include<ctime>
using namespace std;
const int maxnum = 1000;
//数组结构
typedef struct sqlist
{
int l[maxnum];
int length;
}sqlist;
//------插入排序-----（采用“从后向前比较”策略）
void InsertSort(sqlist list, int length)
{
int compare_count = 0; //关键字比较次数
int remove_count = 0; //关键字移动次数
int process = 1; //第n次中间过程
for (int i = 2; i <= list.length; i++) {
compare_count++; //关键字比较次数+1
if (list.l[i] < list.l[i - 1]) {
list.l[0] = list.l[i]; // list.l[0]: 人称“哨兵”
list.l[i] = list.l[i - 1]; //将list.[i]后移
int j = 0;
for (j = i - 2; list.l[0] < list.l[j]; j--) {
list.l[j + 1] = list.l[j]; //将记录逐个后移
}
list.l[j + 1] = list.l[0]; //将“哨兵”插入到正确的位置
remove_count++; //关键字移动次数+1
}
//中间过程输出
cout << "第" << process++ << "次中间过程输出:" << endl;
for (int i = 1; i <= list.length; i++) {
cout << list.l[i] << ' ';
}
cout << endl;
}
//输出关键字比较次数和关键字移动次数
cout << "关键字比较次数：" << compare_count << "\t"
<< "关键字移动次数：" << remove_count << endl;
}
//-----选择排序-----
void SelectSort(sqlist& list)
{
int k = 0;
int process = 1; //第n次中间过程
int compare_count = 0; //关键字比较次数
int remove_count = 0; //关键字移动次数
for (int i = 1; i < list.length; i++) {
k = i;
for (int j = i + 1; j <= list.length; j++) {
compare_count++; //关键字比较次数+1
if (list.l[j] < list.l[k]) k = j; //寻找数组剩余未排序元素中的值最小元素的下标
if (k != i) {
remove_count++; //关键字移动次数+1
int temp = list.l[i];
list.l[i] = list.l[k];
list.l[k] = temp;
}
}
//中间过程输出
cout << "第" << process++ << "次中间过程输出:" << endl;
for (int i = 1; i <= list.length; i++) {
cout << list.l[i] << ' ';
}
cout << endl;
}
//输出关键字比较次数和关键字移动次数
cout << "关键字比较次数：" << compare_count << "\t"
<< "关键字移动次数：" << remove_count << endl;
}
//-----冒泡排序-----
void BubbleSort(sqlist& list)
{
int n = list.length; //作为结束循环的条件之一
int flag = 1; //是否排序完成的标记
int process = 1; //第n次中间过程
int compare_count = 0; //关键字比较次数
int remove_count = 0; //关键字移动次数
//设置两重循环
while (n--&&flag) {
flag = 0;
for (int j = 1; j < list.length; j++) {
compare_count++; //关键字比较次数+1
if (list.l[j] > list.l[j + 1]) {
remove_count++; //关键字移动次数+1
flag = 1;
int temp = list.l[j];
list.l[j] = list.l[j + 1];
list.l[j + 1] = temp;
}
}
//中间过程输出
cout << "第" << process++ << "次中间过程输出:" << endl;
for (int i = 1; i <= list.length; i++) {
cout << list.l[i] << ' ';
}
cout << endl;
}
//输出关键字比较次数和关键字移动次数
cout << "关键字比较次数：" << compare_count << "\t"
<< "关键字移动次数：" << remove_count << endl;
}
//-----双向冒泡----
void TwowaybubbleSort(sqlist& list)
{
int n = list.length;
int flag = 1;
int process = 1; //第n次中间过程
int compare_count = 0; //关键字比较次数
int remove_count = 0; //关键字移动次数
int left= 1; //初始化待排序数组的最左端元素序号
int right= list.length; //初始化待排序数组的最右端元素序号
int temp_right = 0; //暂存待更新待排序数组的最右端元素序号
int temp_left = 0; //暂存待更新待排序数组的最左端元素序号
//设置两重循环
while (n--&&flag) {
flag = 0;
for ( int j = left; j < right; j++) {
compare_count++; //关键字比较次数+1
if (list.l[j] > list.l[j + 1]) {
flag = 1;
remove_count++; //关键字移动次数+1
int temp = list.l[j];
list.l[j] = list.l[j + 1];
list.l[j + 1] = temp;
temp_right = j;
}
}
right = temp_right; //更新待排序数组的最右端元素序号
for (int j = right; j >left; j--) {
compare_count++; //关键字比较次数+1
if (list.l[j] < list.l[j-1]) {
flag = 1;
remove_count++; //关键字移动次数+1
int temp = list.l[j];
list.l[j] = list.l[j - 1];
list.l[j - 1] = temp;
temp_left = j;
}
}
left = temp_left; //更新待排序数组的最左端元素序号
//中间过程输出
cout << "第" << process++ << "次中间过程输出:" << endl;
for (int i = 1; i <= list.length; i++) {
cout << list.l[i] << ' ';
}
cout << endl;
cout << "left,right：" << left << ' ' << right << endl;
}
//输出关键字比较次数和关键字移动次数
cout << "关键字比较次数：" << compare_count << "\t"
<< "关键字移动次数：" << remove_count << endl;
}
//-----快速排序-----
int QSort_process = 1; //第n次中间过程
int QSort_compare_count = 0; //关键字比较次数
int QSort_remove_count = 0; //关键字移动次数
void QSort(sqlist& list,int low, int high)
{
int i, j, pivotkey;
i = low;
j = high;
if (low < high){
pivotkey = list.l[low]; //设置枢轴
while (i != j){
while (j > i&& list.l[j] >= pivotkey){
--j;
QSort_compare_count++; //关键字比较次数+1
}
if (i < j){
list.l[i] = list.l[j]; //交换
++i;
QSort_remove_count++; //关键字移动次数+1
}
while (i < j && list.l[i] <= pivotkey){
++i;
QSort_compare_count++; //关键字比较次数+1
}
if (i < j){
list.l[j] = list.l[i]; //交换
--j;
QSort_remove_count++; //关键字移动次数+1
}
}
list.l[i] = pivotkey; //枢轴记录到位
//中间过程输出
cout << "第" << QSort_process++ << "次中间过程输出:" << endl;
for (int n = 1; n <= list.length; n++) {
cout << list.l[n] << ' ';
}
cout << endl;
//递归
QSort(list, low, i - 1);
QSort(list, i + 1, high);
}
}
//-----二路归并排序-----
int MSort_process = 1; //第n次中间过程
int MSort_compare_count = 0; //关键字比较次数
int MSort_remove_count = 0; //关键字移动次数
void Merge(sqlist &list, int low, int mid, int high)
{
int len = high - low + 1;
int* temp = new int[len];
int i = low; int j = mid + 1; //i,j分别为两个子序列的下标
int k = 0; //新合并的数组的下标
while (i <= mid && j <= high) {
if (list.l[i] <= list.l[j]) {
MSort_compare_count++; //关键字比较次数+1
MSort_remove_count++; //关键字移动次数+1
temp[k] = list.l[i];
i++;
k++;
}
else {
MSort_compare_count++; //关键字比较次数+1
MSort_remove_count++; //关键字移动次数+1
temp[k] = list.l[j];
j++;
k++;
}
}
while (i <= mid) {
temp[k] = list.l[i];
i++;
k++;
}
while (j <= high) {
temp[k] = list.l[j];
j++;
k++;
}
for (int i = 0; i < len; i++) {
list.l[low+i] = temp[i];
}
}
void MSort(sqlist &list,int low,int high)
{
if (low < high) {
int mid = (low + high) / 2;
//递归
MSort(list, low, mid);
MSort(list, mid + 1, high);
//合并左右序列（子树）
Merge(list, low, mid, high);
}
//中间过程输出
cout << "第" << MSort_process++ << "次中间过程输出:" << endl;
for (int n = 1; n <= list.length; n++) {
cout << list.l[n] << ' ';
}
cout << endl;
}
int main()
{
/*
-----------------------------------------
说明：
随机生成数组首元素下标为 1
-----------------------------------------
*/
// 生成随机数组
srand(unsigned(time));
sqlist list;
list.length = 0;
cout << "请输入生成数组的长度：";
cin >> list.length; //输入数组的长度
cout << "生成的数组为：";
for (int i = 1; i <=list.length; i++){
list.l[i] =(int) rand() % 90 + 10;
cout << list.l[i]<<' ';
}
cout << endl;
//-----插入排序-----
//InsertSort(list,list.length);
//-----选择排序-----
//SelectSort(list);
//-----冒泡排序-----
//BubbleSort(list);
//-----双向冒泡-----
//TwowaybubbleSort(list);
//-----快速排序-----
//QSort(list, 1, list.length);
//输出关键字比较次数和关键字移动次数
//cout << "关键字比较次数：" << QSort_compare_count << "\t"
// << "关键字移动次数：" << QSort_remove_count << endl;
//-----归并排序-----
//MSort(list, 1, list.length);
//输出关键字比较次数和关键字移动次数
//cout << "关键字比较次数：" << MSort_compare_count << "\t"
//<< "关键字移动次数：" << MSort_remove_count << endl;
}
2、各种查找算法实现（返回目录🖱）
（1） 顺序查找（返回目录🖱）：使用数组或链表结构。用随机函数生成16个不重复的字母（’a’~’z’），键盘输入待查找的字母，返回查找成功与否，若成功则返回该字母所在的位置（序号），并计算比较次数。
#include<iostream>
#include<ctime>
using namespace std;
//-----顺序查找-----
void Search_Seq(char* s)
{
cout << "请输入想寻找的字母：";
char x;
cin >> x; //输入想找的字母
int index = 0;
int count = 0; //比较次数,初始化为0
while (s[index] != '\0') {
++count;
if (s[index++] == x) {
cout << "已找到字母 " << x << " ,它的下标为：" << index - 1 << endl;
break;
}
}
if (count == 17) {
cout << "没有找到该字母,共比较了：" << count-1 << " 次"<< endl;
}
else cout << "共比较了：" << count << " 次";
}
int main()
{
/*
-----------------------------------------
说明：
随机生成数组首元素下标为 0
-----------------------------------------
*/
// 生成随机数组
srand(unsigned(time));
char* s=new char[17]; //字符数组
for (int i = 0; i < 16; i++) s[i] = '\0';
cout << "生成的数组为：";
int k = 0;
while (k != 16) {
int flag = 0; //用于检测是否有相同的字母出现
s[k] = 'a' + (rand() % 26);
for (int i = 0; i < 16; i++) {
if (k != i) {
if (s[k] == s[i]) flag = 1; //若flag=1，则重新加入一个字母
}
}
if (flag == 0) ++k; //若flag=0，往数组下一个位置添加字母
}
for (int i = 0; i < 16; i++)
cout << s[i] << " "; //打印随机生成的字符数组
s[16] = '\0'; //字符串的最后一位是'\0'
cout << endl;
//-----顺序查找-----
Search_Seq(s);
}
（2） 折半查找（返回目录🖱）：用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、不成功进行测试。
#include<iostream>
#include<ctime>
using namespace std;
//-----顺序查找-----
void TwowaybubbleSort(char* s)
{
int n = 16;
int flag = 1; //检测是否已排序完成
int left = 1; //初始化待排序数组的最左端元素序号
int right = 15; //初始化待排序数组的最右端元素序号
int temp_right = 0; //暂存待更新待排序数组的最右端元素序号
int temp_left = 0; //暂存待更新待排序数组的最左端元素序号
//设置两重循环
while (n-- && flag) {
flag = 0;
for (int j = left; j < right; j++) {
if (s[j] > s[j + 1]) {
flag = 1;
int temp = s[j];
s[j] =s[j + 1];
s[j + 1] = temp;
temp_right = j;
}
}
right = temp_right; //更新待排序数组的最右端元素序号
for (int j = right; j > left; j--) {
if (s[j] < s[j - 1]) {
flag = 1;
int temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;
temp_left = j;
}
}
}
}
void Search_Bin(char* s)
{
TwowaybubbleSort(s); //先使用双向冒泡进行排序
int compare_count = 0; //记录比较次数
cout << "请输入想寻找的字母：";
char x;
cin >> x; //输入待寻找的字母
int low = 0; int high = 15;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (x == s[mid]) {
compare_count++;
cout << "已找到字母 " << x << endl;
break;
}
else if (x < s[mid]) {
compare_count++;
high = mid - 1;
}
else {
compare_count++;
low = mid + 1;
}
}
if(low>high&&x!=s[low]) cout<< "未找到该字母，总共比较了 " << compare_count << " 次" << endl;
else cout << "总共比较了 " << compare_count << " 次" << endl;
}
int main()
{
/*
-----------------------------------------
说明：
随机生成数组首元素下标为 0
-----------------------------------------
*/
// 生成随机数组
srand(unsigned(time));
char* s = new char[17]; //字符数组
for (int i = 0; i < 16; i++) s[i] = '\0';
cout << "生成的数组为：";
int k = 0;
while (k != 16) {
int flag = 0; //用于检测是否有相同的字母出现
s[k] = 'a' + (rand() % 26);
for (int i = 0; i < 16; i++) {
if (k != i) {
if (s[k] == s[i]) flag = 1; //若flag=1，则重新加入一个字母
}
}
if (flag == 0) ++k; //若flag=0，往数组下一个位置添加字母
}
for (int i = 0; i < 16; i++)
cout << s[i] << " "; //打印随机生成的字符数组
s[17] = '\0'; //字符串的最后一位是'\0'
cout << endl;
//-----折半查找-----
Search_Bin(s);
}
（3）二叉查找树（返回目录🖱）：手工输入10个字母，生成一棵二叉查找树，用递归算法打印树结构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次数。分别用查找成功、不成功进行测试。
#include<iostream>
using namespace std;
//二叉查找树结构
typedef struct BSTNode
{
char data;
BSTNode* lchild, * rchild;
}BSTNode,*BSTree;
//二叉排序树的插入
void InsertBST(BSTree& T, char x)
{
if (!T) {
BSTNode* new_tree = new BSTNode; //生成新结点
new_tree->data = x;
new_tree->lchild = new_tree->rchild = NULL;
T = new_tree;
}
else if (x < T->data) InsertBST(T->lchild, x);
else if (x > T->data) InsertBST(T->rchild, x);
}
//二叉排序树的创建
void CreatBST(BSTree& T)
{
T = NULL;
char x;
cin >> x;
int i = 0; //用于提示已经输入了多少个字母
while (x != '#') {
InsertBST(T, x);
cout << "这是输入的第 " << ++i << " 个字母" << endl;
cin >> x;
}
}
//二叉树的先序遍历
void Preorder(BSTree T)//前序遍历（递归实现）
{
if (T != NULL)
{
cout << T->data << " ";
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//二叉树的中序遍历
void Mreorder(BSTree T)//前序遍历（递归实现）
{
if (T != NULL)
{
Mreorder(T->lchild);
cout << T->data << " ";
Mreorder(T->rchild);
}
}
//-----二叉查找树-----
int compare_count = 0; //全局变量。记录比较次数
BSTree SearchBST(BSTree T, char x)
{
compare_count++;
if (!T|| x == T->data) {
if (!T)
cout << "查询失败,共查找了 " << compare_count << " 次\n";
else
cout << "已找到字母 " << T->data << " ,共查找了 " << compare_count << " 次\n";
return T;
}
else if (x < T->data) return SearchBST(T->lchild, x);
else if (x >= T->data) return SearchBST(T->rchild, x);
}
int main()
{
//创建二叉查找树
BSTree T = new BSTNode;
cout << "请输入十个字母(输入#结束): " << endl;
CreatBST(T);
cout<<"输入完成\n";
//中序遍历二叉查找树
cout << "\n先序遍历输出：";
Preorder(T);
//中序遍历二叉查找树
cout << "\n中序遍历输出(按照各字母的ASCⅡ码大小)：";
Mreorder(T);
//输入待查找字母
cout << "\n请输入想查询的字母(如果想退出查找，请输入$) ";
char letter;
cin >> letter;
//查找字母
while (1 && letter != '$') {
SearchBST(T, letter);
cout << "\n请输入想查询的字母(如果想退出查找，请输入$) ";
cin >> letter;
}
}
四、实验过程原始数据记录
1、 各种排序算法的实现
1） 插入排序
2） 选择排序
3） 冒泡排序
4） 双向冒泡排序
5） 快速排序
6） 归并排序
2、各种查找算法实现
（1）顺序查找
1） 查找成功的情况
2）查找不成功的情况
（2）折半查找
1）查找成功的情况
2）查找不成功的情况
（3） 二叉查找树
五、实验结果及分析
（代码已写注释。）
插入排序、选择排序、冒泡排序等实现简单，并且在待排序的元素总量较小的时候与快速排序、归并排序等速度相差不大，但是当待排序元素总量较大时，快速排序和二路归并排序的优势就非常明显了（我尝试了对900个元素进行排序）。所以在元素总量较小时，各种排序方法的差距不会太大，但当元素总量大时，为了提高效率，还是应该选择实现过程较复杂的但效率高的算法。
查找算法：在顺序查找、折半查找、二叉查找树查找中算法中，顺序查找是效率最低的；对于折半查找、二叉查找树查找来说，这两种查找算法的时间复杂度在一般情况下是相同的，但二叉查找树是链式结构，插入和删除都只需要修改指针，这是非常方便的。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献2条内容
所有评论(0)