17_3_1.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 1000

/*
@ InsertSort
前置条件：	数组存在，比较次数cpr存在，语句运行次数run存在
输入：		待排序的数组a，长度，比较次数cpr，语句运行次数run
功能：		直接插入排序
输出：		无
后置条件：	数组被排序
*/
void InsertSort(int a[], int n, int &cpr, int &run)
{
	int i, j;
	for (i = 2; i <= n; i++)
	{
		a[0] = a[i];
		for (j = i - 1; a[0] < a[j]; j--)
		{
			a[j + 1] = a[j];
			run++;
		}
		a[j + 1] = a[0];
		run += 2;
	}
}

/*
@ ShellSort
前置条件：	数组存在，比较次数cpr存在，语句运行次数run存在
输入：		待排序的数组a，长度，比较次数cpr，语句运行次数run
功能：		希尔排序
输出：		无
后置条件：	数组被排序
*/
void ShellSort(int r[], int n, int &cpr, int &run)
{
	int d, i, j;
	for (d = n / 2; d >= 1; d = d / 2)
	{
		for (i = d + 1; i <= n; i++)
		{
			r[0] = r[i];
			for (j = i - d; j > 0 && r[0] < r[j]; j = j - d)
			{
				r[j + d] = r[j];
				run++;
			}
			r[j + d]	= r[0];
			run		+= 2;
		}
	}
}

/*
@ BubbleSort
前置条件：	数组存在，比较次数cpr存在，语句运行次数run存在
输入：		待排序的数组a，长度，比较次数cpr，语句运行次数run
功能：		气泡排序
输出：		无
后置条件：	数组被排序
*/
void BubbleSort(int a[], int n, int &cpr, int &run)
{
	int exchange = n - 1;
	run++;
	while (exchange)
	{
		int bound = exchange;
		exchange = 0;
		for (int i = 1; i < bound; i++)
		{
			if (a[i] > a[i + 1])
			{
				cpr++;
				int t		= a[i];
				a[i]		= a[i + 1];
				a[i + 1]	= t;
				exchange	= i;
				run		+= 4;
			}
		}
		run += 2;
	}
}

/*
@ SelectSort
前置条件：	数组存在，比较次数cpr存在，语句运行次数run存在
输入：		待排序的数组a，长度，比较次数cpr，语句运行次数run
功能：		选择排序
输出：		无
后置条件：	数组被排序
*/
void SelectSort(int a[], int n, int &cpr, int &run)
{
	int i, j, minId;
	for (i = 0; i <= n; i++)
	{
		minId = i;
		run++;
		for (j = i; j <= n; j++)
			if (a[minId] > a[j])
			{
				minId = j;
				cpr++;
				run++;
			}
		if (minId != i)
		{
			int t		= a[minId];
			a[minId]	= a[i];
			a[i]		= t;
			cpr++;
			run		+= 2;
		}
	}
}

/******************* 归并排序 ***********************/

/*
@ Merge
前置条件：	数组r存在，比较次数cpr存在，语句运行次数run存在，
			辅助数组r1存在
输入：		待排序的数组a，辅助数组r1，s、m、t，比较次数，语句运行条数
功能：		进行一次归并排序
输出：		无
后置条件：	数组r、r1被改变
*/
void Merge(int r[], int r1[], int s, int m, int t, int &cpr, int &run)
{
	int i = s;
	int j = m + 1;
	int k = s;
	run += 3;
	while (i <= m && j <= t)
	{
		if (r[i] < r[j])
			r1[k++] = r[i++];
		else
			r1[k++] = r[j++];
		cpr++;
		run++;
	}
	if (i <= m)
	{
		cpr++;
		while (i <= m)
		{
			r1[k++] = r[i++];
			run++;
		}
	}
	if (j <= t)
	{
		cpr++;
		while (j <= t)
		{
			r1[k++] = r[j++];
			run++;
		}
	}
}

/*
@ MergePass
前置条件：	数组a存在，比较次数cpr存在，语句运行次数run存在，
			辅助数组r1存在
输入：		数组a、辅助数组a1、数组长度、一次排序的长度h，
			比较次数cpr，语句运行条数run
功能：		做一趟归并排序
输出：		无
后置条件：	数组a, a1被改变
*/
void MergePass(int a[], int a1[], int n, int h, int &cpr, int &run)
{
	int i = 1;
	while (i <= n - 2 * h + 1)
	{
		Merge(a, a1, i, i + h - 1, i + 2 * h - 1, cpr, run);
		i = i + 2 * h;
		run++;
	}
	if (i < n - h + 1)
		Merge(a, a1, i, i + h - 1, n, cpr, run);
	else
		for (int j = i; j <= n; j++)
		{
			a1[j] = a[j];
			run++;
		}
	cpr++;
}

/*
@ MergeSort
前置条件：	数组r存在，比较次数cpr存在，语句运行次数run存在，
			辅助数组r1存在
输入：		数组a、辅助数组a1、数组长度、
			比较次数cpr，语句运行条数run
功能：		归并排序
输出：		无
后置条件：	数组被排序
*/
void MergeSort(int a[], int a1[], int n, int &cpr, int &run)
{
	int h = 1;
	while (h < n)
	{
		MergePass(a, a1, n, h, cpr, run);
		h = h * 2;
		MergePass(a1, a, n, h, cpr, run);
		h = h * 2;
		run += 2;
	}
}

/****************** 输出和生成函数等 ******************/

/*
@ Print
前置条件：	无
输入：		介绍词，数组，数组长度
功能：		打印数组内容（Debug用）
输出：		数组内容
后置条件：	无
*/
void Print(char *introduction, int a[], int n)
{
	cout << introduction << "：" << endl;
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
}

/*
@ Print
前置条件：	无
输入：		说明，比较次数，语句运行条数
功能：		打印内容
输出：		格式化地输出比较次数，语句运行条数
后置条件：	无
*/
void Print(char *i, int cpr, int run)
{
	cout << "\t" << i << endl;
	cout << "\t\t" << "比较次数为：\t" << cpr << endl;
	cout << "\t\t" << "语句运行次数：\t" << run << endl;
}

/*
@ GenerateArray
前置条件：	数组a存在，长度存在
输入：		数组a，长度n
功能：		生成长度为n的随机数组
输出：		无
后置条件：	数组a被生成
*/
void GenerateArray(int a[], int n)
{
	for (int i = 1; i <= n; i++)
		a[i] = rand() % MAX_SIZE;
}

/*
@ CopyArray
前置条件：	数组a、b存在
输入：		数组a、数组b，数组长度
功能：		复制数组，将数组b的内容复制到a
输出：		无
后置条件：	数组b的内容被复制到a
*/
void CopyArray(int a[], int b[], int n)
{
	for (int i = 1; i <= n; i++)
		a[i] = b[i];
}

/*
@ GenerateArrayASC
前置条件：	数组存在
输入：		数组和数组长度
功能：		生成长度为n的升序排列数组
输出：		无
后置条件：	数组被生成	
*/
void GenerateArrayASC(int a[], int n)
{
	for (int i = 1; i <= n; i++)
		a[i] = i;
}

/*
@ GenerateArrayDESC
前置条件：	数组存在
输入：		数组和数组长度
功能：		生成长度为n的降序排列数组
输出：		无
后置条件：	数组被生成
*/
void GenerateArrayDESC(int a[], int n)
{
	int j = 0;
	for (int i = MAX_SIZE; i >= MAX_SIZE - n + 1; i--)
	{
		a[j] = i;
		j++;
	}
}

/*
@ Reset
前置条件：	比较次数cpr，语句运行条数run存在
输入：		比较次数cpr，语句运行条数run
功能：		cpr、run归零
输出：		无
后置条件：	cpr、run归零
*/
void Reset(int &cpr, int &run)
{
	cpr = 0;
	run = 0;
}

/************************ 主函数 ***********************/

void main()
{
	srand(time(NULL));
	int a[MAX_SIZE];
	int a1[MAX_SIZE];
	int n;
	cout << "请输入数组的个数：（1~999）" << endl;
	cin >> n;
	if (n > 999 || n < 1)
	{
		cout << "【错误】数值范围不正确" << endl;
		exit(0);
	}
	cout << "----------------------------------------------" << endl;

	int cpr = 0;
	int run = 0;
	int tpl[MAX_SIZE];
	
	/************** 直接插入排序 ****************/

	cout << "一、直接插入排序。" << endl;

	GenerateArrayASC(a, n);
	InsertSort(a, n, cpr, run);
	Print("1、正序", cpr, run);

	GenerateArrayDESC(a, n);
	InsertSort(a, n, cpr, run);
	Print("2、反序", cpr, run);

	GenerateArray(a, n);

	InsertSort(a, n, cpr, run);
	Print("3、随机情况", cpr, run);
	
	Reset(cpr, run);

	/************** 起泡排序 ***************/

	cout << "二、起泡排序。" << endl;

	GenerateArrayASC(a, n);
	BubbleSort(a, n, cpr, run);
	Print("1、正序", cpr, run);

	GenerateArrayDESC(a, n);
	BubbleSort(a, n, cpr, run);
	Print("2、反序", cpr, run);

	GenerateArray(tpl, n);
	CopyArray(a, tpl, n);
	BubbleSort(a, n, cpr, run);
	Print("3、随机情况", cpr, run);

	Reset(cpr, run);

	/*************** 希尔排序 **************/

	cout << "三、希尔排序。" << endl;

	GenerateArrayASC(a, n);
	ShellSort(a, n, cpr, run);
	Print("1、正序", cpr, run);

	GenerateArrayDESC(a, n);
	ShellSort(a, n, cpr, run);
	Print("2、反序", cpr, run);

	CopyArray(a, tpl, n);
	ShellSort(a, n, cpr, run);
	Print("3、随机情况", cpr, run);

	Reset(cpr, run);

	/*************** 选择排序 **************/

	cout << "四、选择排序。" << endl;

	GenerateArrayASC(a, n);
	SelectSort(a, n, cpr, run);
	Print("1、正序", cpr, run);

	GenerateArrayDESC(a, n);
	SelectSort(a, n, cpr, run);
	Print("2、反序", cpr, run);

	CopyArray(a, tpl, n);
	SelectSort(a, n, cpr, run);
	Print("3、随机情况", cpr, run);

	Reset(cpr, run);

	/*************** 归并排序 **************/

	cout << "五、归并排序。" << endl;

	GenerateArrayASC(a, n);
	MergeSort(a, a1, n, cpr, run);
	Print("1、正序", cpr, run);

	GenerateArrayDESC(a, n);
	MergeSort(a, a1, n, cpr, run);
	Print("2、反序", cpr, run);

	CopyArray(a, tpl, n);
	MergeSort(a, a1, n, cpr, run);
	Print("3、随机情况", cpr, run);

	Reset(cpr, run);
}