二、实验任务1. 掌握常见排序算法的策略、适用条件和程序实现。
2.掌握折半查找算法的思想及程序实现。
3.掌握 BST 的建立、查找、插入、删除算法策略及其程序实现。
4.选择合适的散列函数,实现不同冲突处理方法的散列表建立与查找。
三、源代码 源文件1. 实现选择排序、插入排序和冒泡排序。
2. 实现快速排序的非递归算法(可借助栈实现)。
3. 实现堆排序算法。
4. 实现折半插入排序。
5. 采用链式存储结构实现:选择排序、插入排序和冒泡排序。
6. 在主函数中设计一个简单菜单,调用上述算法。
1 建立有序表,采用折半查找实现某一已知关键字的查找。
2.随机产生一组关键字,利用插入算法建立 BST,然后删除某一指定关键字的元素。
3.建立散列表:散列函数 H(key)=key%p(p 为自定常数),冲突处理分别采用线性探 测法、拉链法。
/*
实验4:集合应用
实验名称:排序算法
实验目的:掌握常见排序算法的策略、适用条件和程序实现。
实验内容:
1. 实现选择排序、插入排序和冒泡排序。
2. 实现快速排序的非递归算法(可借助栈实现)。
3. 实现堆排序算法。
4. 实现折半插入排序。
5. 采用链式存储结构实现:选择排序、插入排序和冒泡排序。
6. 在主函数中设计一个简单菜单,调用上述算法。
实验日期:2021/1/5
开发者:每天八杯水
*/
#include"Sort.h"
SortArr* SSortArr();
void ShowSortArr(SortArr*);
SortArr* InsertSort(SortArr*);
SortArr* BinSort(SortArr*);
SortArr* SelectSort(SortArr*);
void HeapAdjust(SortArr* ,int, int);
void HeapSort(SortArr*, int);
SortArr* BubbleSort(SortArr*);
int main()
{
//设置一组待排序数组
SortArr* sortArr = SSortArr();//sortArr为该待排序数组的指针
cout << "你创建的待排序数组为:";
ShowSortArr(sortArr);//打印出设置的待排序数组
bool opt = true; //是否循环的一个标志
while (opt == true) {
//主菜单列表
cout << "\n\t\t********************************\n";
cout << "\t\t* WELCOM TO MY WORLD *\n";
cout << "\t\t* 1. 插入排序 *\n";
cout << "\t\t* 2. 选择排序 *\n";
cout << "\t\t* 3. 交换排序 *\n";
cout << "\t\t* 4. 退出程序 *\n";
cout << "\t\t********************************\n";
//接收输入选择
cout << "\t\t请选择:";
int x;
cin >> x;
//判断用户的选择
switch (x) {
case 1:
{//设置插入排序循环,有两个算法:直接插入排序 二分插入排序
bool opt1 = true;
while (opt1==true)
{
//插入排序列表
cout << "\n\t\t*****************************\n";
cout << "\t\t* 插入排序 *\n";
cout << "\t\t* 1. 直接插入排序 *\n";
cout << "\t\t* 2. 二分插入排序 *\n";
cout << "\t\t* 3. Shell排序 *\n";
cout << "\t\t* 4. 释放资源 *\n";
cout << "\t\t* 5. 返回主菜单 *\n";
cout << "\t\t*****************************\n";
//接收输入选择
cout << "\t\t请选择:";
int x;
cin >> x;
//判断用户的选择
switch (x) {
case 1://直接插入排序
cout << "直接插入排序后的顺序:";
ShowSortArr(InsertSort(sortArr));//排序并打印排序后的数据
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;//第二层循环退出时,令第一层循环为真继续循环
break;
case 2:
cout << "二分插入排序后的顺序:";
ShowSortArr(BinSort(sortArr));//排序并打印排序后的数据
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 3:
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 4:
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 5:
opt = true;
opt1 = false; //子菜单目录
if (opt1 == false)opt = true;
break;
default:
cout << "\n\t\t输入非法,请重新选择!\n";
break;
}
}
}
break;
case 2:
{//设置选择排序循环,有两个算法:直接选择排序 堆排序
bool opt1 = true;
while (opt1 == true)
{
//选择排序列表
cout << "\n\t\t*****************************\n";
cout << "\t\t* 选择排序 *\n";
cout << "\t\t* 1. 直接选择排序 *\n";
cout << "\t\t* 2. 堆排序 *\n";
cout << "\t\t* 3. 释放资源 *\n";
cout << "\t\t* 4. 返回主菜单 *\n";
cout << "\t\t*****************************\n";
//接收输入选择
cout << "\t\t请选择:";
int x;
cin >> x;
//判断用户的选择
switch (x) {
case 1:
cout << "直接选择排序后的顺序:";
ShowSortArr(SelectSort(sortArr));//排序并打印排序后的数据
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;//第二层循环退出时,令第一层循环为真继续循环
break;
case 2:
//堆排序
cout << "堆排序后的顺序:";
HeapSort(sortArr, sortArr->cnt);
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 3:
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 4:
opt = true;
opt1 = false; //子菜单目录
if (opt1 == false)opt = true;
break;
default:
cout << "\n\t\t输入非法,请重新选择!\n";
break;
}
}
}
break;
case 3:
{//设置交换排序循环,有两个算法:冒泡排序 快速排序
bool opt1 = true;
while (opt1 == true)
{
//交换排序列表
cout << "\n\t\t*****************************\n";
cout << "\t\t* 交换排序 *\n";
cout << "\t\t* 1. 冒泡排序 *\n";
cout << "\t\t* 2. 快速排序 *\n";
cout << "\t\t* 3. 释放资源 *\n";
cout << "\t\t* 4. 返回主菜单 *\n";
cout << "\t\t*****************************\n";
//接收输入选择
cout << "\t\t请选择:";
int x;
cin >> x;
//判断用户的选择
switch (x) {
case 1:
cout << "冒泡排序后的顺序:";
ShowSortArr(BubbleSort(sortArr));//排序并打印排序后的数据
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;//第二层循环退出时,令第一层循环为真继续循环
break;
case 2:
cout << "快速排序后的顺序:";
ShowSortArr(QuickSort(sortArr,0,sortArr->cnt-1));//排序并打印排序后的数据
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 3:
opt1 = Out(); //子菜单目录
if (opt1 == false)opt = true;
break;
case 4:
opt = true;
opt1 = false; //子菜单目录
if (opt1 == false)opt = true;
break;
default:
cout << "\n\t\t输入非法,请重新选择!\n";
break;
}
}
}
break;
break;
case 4:
opt = false; //把标志位为假,就退出了循环
break;
default:
cout << "\n\t\t输入非法,请重新选择!\n";
break;
}
}
cout << "\n\t\t菜单已退出!\n";
}
头文件
/*
头文件
*/
#pragma once
#include
#include
#include
#include
using namespace std;
/*
定义小目录-进入算法后如何退出的实现
*/
int Out() {
cout << "\n";
cout << "\t\t****************\n";
cout << "\t\t*算法结束请选择*\n";
cout << "\t\t* 1.返回子菜单 *\n";
cout << "\t\t* 2.返回主菜单 *\n";//主菜单界面
cout << "\t\t****************\n";
cout << "\t\t选择:";
char y;
cin >> y; //接受输入
switch (y) {
case '1':
return true;
case '2':
return false;
default:
cout << "\t\t非法输入,已返回主目录!\n";//输入其他数字无效
return true;
break;
}
}
typedef int KeyType;
typedef int InfoType;
typedef struct RECORDTYPE_STRU//数组每一个下标存放的是这个结构体的地址
{
KeyType key;
InfoType otherInfo;
}RecordType;
typedef struct SORTARRAY_STRU
{
int cnt;//排序数组中的元素个数
RecordType* recordArr;//指向排序数组的指针
}SortArr;
/*
交换i 和 j 两个元素关键字的位置
*/
void Swap(SortArr* sortArr, int i, int j)
{
KeyType temp;
temp = sortArr->recordArr[i].key;//排序数组中第i个元素的关键字赋值给temp,
sortArr->recordArr[i].key = sortArr->recordArr[j].key;
sortArr->recordArr[j].key = temp;
}
/*
待排序数组
*/
SortArr* SSortArr()
{
SortArr* sortArr;//待排序数据指针地址
sortArr = (SortArr*)malloc(sizeof(SortArr*));//申请排序数组指针空间
//随机函数创建一组乱序数据
cout << "正在随机创建一组乱序数据,请等待......" << endl;
cout << "请输入该待排序元素个数:";
int cnt;
cin >> cnt;
sortArr->cnt = cnt;
sortArr->recordArr = (RecordType*)malloc(sizeof(RecordType) * sortArr->cnt);//申请数组的大小空间
srand((unsigned)time(NULL));//rand函数的不同时间种子
for (int i = 0; i < cnt; i++)
{
sortArr->recordArr[i].key = rand()%100;//除以100表示随机数在0到100的范围
}
return sortArr;
}
void ShowSortArr(SortArr* sortArr)
{
for (int i = 0; i < sortArr->cnt; i++)
{
cout << sortArr->recordArr[i].key << " ";
}
}
/*
直接插入排序算法
*/
SortArr* InsertSort(SortArr* sortArr)
{
int i, j;
RecordType temp;
for (i = 1; i < sortArr->cnt; i++)
{
j = i - 1;
temp = sortArr->recordArr[i];
while (temp.key < sortArr->recordArr[j].key && j>=0)
{
sortArr->recordArr[j + 1] = sortArr->recordArr[j];
j--;
}
if (j + 1 != i) {
sortArr->recordArr[j+1] = temp;
}
}
return sortArr;
}
/*
二分插入
*/
SortArr* BinSort(SortArr* sortArr)
{
int i, j;
int low, mid, high;
RecordType temp;
for (i = 1; i < sortArr->cnt; i++)
{
temp = sortArr->recordArr[i];
low = 0;
high = i - 1;
while (low<=high)
{
mid = (low + high) / 2;
if (temp.key < sortArr->recordArr[mid].key)
high = mid - 1;
else
low = mid + 1;
}
if (low != 1)
{
for (j = i - 1; j > low; j--)
sortArr->recordArr[j + 1] = sortArr->recordArr[j];
sortArr->recordArr[low] = temp;
}
}
return sortArr;
}
/*
直接选择
*/
SortArr* SelectSort(SortArr* sortArr)
{
int i, j;
int minPos;
for (i = 0; i < sortArr->cnt-1; i++)
{
minPos = i;
for (j = i + 1; j < sortArr->cnt; j++)
{
if (sortArr->recordArr[j].key < sortArr->recordArr[minPos].key)
minPos = j;
}
if (minPos != i)
Swap(sortArr, minPos, i);
}
return sortArr;
}
/*
堆排序
*/
void HeapAdjust(SortArr* sortArr, int father, int size)
{
int lchild;
int rchild;
int max;
while (father= size)
{
break;//???
}
//大根堆要父结点大于左右孩子
max = lchild;
if(rchildrecordArr[rchild].key>sortArr->recordArr[lchild].key)
{
max = rchild;
}
if (sortArr->recordArr[father].key < sortArr->recordArr[max].key)
{
Swap(sortArr, father, max);
father = max;
}
else
{
break;
}
}
}
void HeapSort(SortArr* sortArr, int size)
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
{
HeapAdjust(sortArr, i, size);
}
for (i = size - 1; i >= 1; i--)
{
cout<recordArr[0].key<<" ";
Swap(sortArr, 0, i);
HeapAdjust(sortArr, 0, i);
}
}
/*
冒泡排序
*/
SortArr* BubbleSort(SortArr* sortArr)
{
int i, j;
int hasSwap = 0;
for (i = 1; i < sortArr->cnt; i++)
{
hasSwap = 0;
for (j = 1; j < sortArr->cnt - i + 1; j++)
{
if (sortArr->recordArr[j - 1].key > sortArr->recordArr[j].key)
{
Swap(sortArr, j, j - 1);
hasSwap = 1;
}
}
if (!hasSwap)
break;
}
return sortArr;
}
/*
快速排序
*/
SortArr* QuickSort(SortArr* sortArr, int left, int right)
{
int i, j;
KeyType temp;
if (left >= right)
return sortArr;
i = left;
j = right;
temp = sortArr->recordArr[i].key;
while (i!=j)
{
while (sortArr->recordArr[j].key >= temp && j > i)
{
j--;
}
if(irecordArr[i].key = sortArr->recordArr[j].key;
i++;
}
else
{
break;
}
while (sortArr->recordArr[i].key<=temp && j>1)
{
i++;
}
if (i < j)
{
sortArr->recordArr[j].key = sortArr->recordArr[i].key;
j--;
}
else
{
break;
}
}
sortArr->recordArr[i].key = temp;
QuickSort(sortArr, left, i - 1);
QuickSort(sortArr, i + 1, right);
return sortArr;
}
四、运行结果
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)