数据结构第六次上机代码

---

报告

排序

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream>
#include<windows.h>
#include<time.h>
using namespace std;
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define LIST_INIT_SIZE 10 //线性表储存空间初始分配量
#define LISTINCREMRNT 10 //线性表储存空间的分配增量
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型
 //线性表动态分配顺序储存结构
typedef struct
{
	ElemType* elem;//储存空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;

//1初始化一个空的表
Status InitList(SqList* L)
{

	L->elem = (ElemType*)__vcrt_malloc_normal(LIST_INIT_SIZE * sizeof(ElemType));
	if (!(L->elem))
		exit(OVERFLOW);//分配失败
	L->length = 0;//长度
	L->listsize = LIST_INIT_SIZE;//容量

	return OK;
}

//2插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	if (i<1 || i>L->length + 1)
		return ERROR;

	ElemType* q = &(L->elem[i - 1]), *p = NULL;// q为插入位置
	for (p = &(L->elem[L->length - 1]); p >= q; --p)
		* (p + 1) = *p;// 插入位置及之后的元素后移
	*q = e;// 插入e
	++(L->length);// 表长增加1
	if (L->length == L->listsize) {
		ElemType*  newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMRNT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;// 新基址
		L->listsize += LISTINCREMRNT;// 增加存储容量
	}
	return OK;
}
//3获取长度
int getLength(SqList* L)
{
	return L->length;
}
//4是否为空
char* isEmtey(SqList* L)
{
	return L->length == 0 ? "空" : "不空";
}
//5清空
Status clearList(SqList* L)
{
	__vcrt_free_normal(L->elem);
	L->length = 0;
	return OK;
}
//6摧毁
Status destryList(SqList* L)
{

	__vcrt_free_normal(L);
	L = NULL;
	return OK;
}
//7通过索引取值
ElemType getElemByIndex(SqList* L, int i)
{
	return L->elem[i - 1];
}

//8通过值取索引
int getIndexByElem(SqList* L, ElemType e)
{
	for (int j = 0; j < L->length; ++j)
	{
		if ((L->elem[j]) == e)
			return j + 1;
	}
	return -1;
}
//9通过索引改值
ElemType changeElemByIndex(SqList* L, int i, ElemType e)
{
	return  L->elem[i - 1] = e;

}

//11遍历表
Status myPrintf(SqList* L)
{
	for (int i = 0; i < L->length; i++) {
		printf("%d ",(L->elem[i]));
	}
	return OK;
}
//验证增序
int verify(SqList* L)
{
	int length = getLength(L);

	for (int i = 0; i < length-1; i++)
	{
		if (L->elem[i]>L->elem[i+1])
		{
			return 0;
		}
	}
	return 1;
}
//建表
SqList* createSqByCin()
{
	SqList* L = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(L);
	int n = 0;
	cin >> n;
	cout << "输入数据：";
	ElemType elem = NULL;
	for (int i = 0; i < n; i++)
	{
		cin >> elem;
		ListInsert(L, i + 1, elem);
	}
	cout << "建表成功: ";
	myPrintf(L);
	cout << endl;
	return L;
}

SqList* createSqByRandom()
{
	SqList* L = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(L);
	int n = 0;
	cin >> n;
	ElemType elem = NULL;
	
	for (int i = 0; i < n; i++)
	{
		
		ListInsert(L, i + 1, rand()%100+1);
	}
	cout << "建表成功: ";
	myPrintf(L);
	cout << endl;
	return L;
}
//插入排序
void InsertSort(SqList* L)
{
	int j = 0;
	int length = getLength(L);
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	for (int i = 1; i < length; i++)
	{
		ElemType temp = L->elem[i];
		for (j= i-1; j >=0&&L->elem[j]>temp; j--)
		{
			L->elem[j + 1] = L->elem[j];
		}
		L->elem[j + 1] = temp;
	}
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000*(finish.QuadPart - start.QuadPart)/Freq <<" 微秒" <<endl;
	cout << endl;
	destryList(L);
}
//希尔排序
void ShellInsert(SqList* L,int dk)
{
	int j = 0;
	int length = getLength(L);
	for (int i = dk; i < length; i++)
	{
		j = i - dk;
		ElemType temp = L->elem[i];
		
		
			
			while ( j >= 0 && L->elem[j]>temp)
			{
				L->elem[j + dk] = L->elem[j];
				j -= dk;
			}
			if (j!=i-dk)
			{
				L->elem[j + dk] = temp;
			}
			
		
	}
}
void ShellSort(SqList* L)
{
	int dk = getLength(L)/2;
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	while ( dk>=1)
	{
		ShellInsert(L, dk);
		dk = dk / 2;
	}
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//冒泡排序
void BubbleSort(SqList* L)
{
	int length = getLength(L);
	int flag = 1;
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	for (int i = 0; i < length&&flag==1; i++)
	{
		flag = 0;
		for (int j = 0; j < length-i-1; j++)
		{
			if (L->elem[j]>L->elem[j+1])//不会异或相同数
			{
				flag = 1;
				L->elem[j + 1] = L->elem[j] ^ L->elem[j + 1];
				L->elem[j] = L->elem[j] ^ L->elem[j + 1];
				L->elem[j + 1] = L->elem[j] ^ L->elem[j + 1];
			}
		}
	}
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//快速排序
int Partition(SqList* L, int low, int high)
{
	ElemType pivotkey = L->elem[low];
	while (low<high)
	{
		while (low<high&&L->elem[high]>=pivotkey)
		{
			high--;
		}
		L->elem[low] = L->elem[high];
		while (low<high&&L->elem[low]<=pivotkey)
		{
			low++;
		}
		L->elem[high] = L->elem[low];
	}
	L->elem[low] = pivotkey;
	return low;
}
void QSort(SqList* L, int low, int high)
{
	if (low < high)
	{
		int pivotloc = Partition(L, low, high);
		QSort(L, low, pivotloc - 1);
		QSort(L, pivotloc + 1, high);
	}
}
void QuickSort(SqList* L)
{
	int length = getLength(L);
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	QSort(L, 0, length-1);
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//简单选择排序
void SelectSort(SqList* L)
{
	int length = getLength(L)-1;
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	for (int i = 0; i < length; i++)
	{
		int index = i;
		for (int  j = i+1; j <= length; j++)
		{
			if (L->elem[j] < L->elem[index])
			{
				index = j;
			}
		}
		if (L->elem[index]!= L->elem[i])//不会异或相同数 index !=i应该不需要了
		{
			L->elem[index] = L->elem[index] ^ L->elem[i];
			L->elem[i] = L->elem[index] ^ L->elem[i];
			L->elem[index] = L->elem[index] ^ L->elem[i];
		}
	}
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//堆排序
void heapify(ElemType elem[], int i/*第i个*/, int n/*共n个*/)
//提示：假设第i+1后面已经是堆，调整第i个
{	//递归出口隐含在if里所以可以不写
	/*if (n<=i)
	{
		return;
	}*/
	int c1 = 2 * i + 1;
	int c2 = 2 * i + 2;
	int max = i;
	if (c1<n&&elem[c1]>elem[max])
		max = c1;
	if (c2<n&&elem[c2]>elem[max])
		max = c2;
	if (max != i)
	{//三个if保证elem[i]!=elem[max]
		elem[i] = elem[i] ^ elem[max];
		elem[max] = elem[i] ^ elem[max];
		elem[i] = elem[i] ^ elem[max];
		heapify(elem, max, n);
	}
}
void CreatHeap(SqList* L,int n)
//提示：从最后非叶结点开始heapify建初堆
{
	int lost_node = (n - 1) ;
	for (int i = (lost_node-1)/2; i >= 0; --i)
	{
		heapify(L->elem, i, n);
	}
	cout << "创建的初堆：";
	myPrintf(L);
	cout << endl;
}
void HeapSort(SqList* L)
{
	int n = getLength(L);
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	CreatHeap(L,n);
	for(int i = n-1; i >= 0; --i)
	{
		if (L->elem[0]!=L->elem[i])
		{
			L->elem[i] = L->elem[i] ^ L->elem[0];
			L->elem[0] = L->elem[i] ^ L->elem[0];
			L->elem[i] = L->elem[i] ^ L->elem[0];
		}
		heapify(L->elem, 0, i);
	}
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//归并排序(从上往下)
void Merge(ElemType elem[], int start, int mid, int end)
{
	ElemType *tmp = (ElemType *)malloc((end - start + 1) * sizeof(ElemType));
	int i = start;// 第1个有序区的索引
	int j = mid + 1;// 第2个有序区的索引
	int k = 0;// 临时区域的索引
	while (i <= mid && j <= end)
	{
		if ( elem[i] <= elem[j])
			tmp[k++] = elem[i++];
		else
			tmp[k++] = elem[j++];
	}
	while (i <= mid)
		tmp[k++] = elem[i++];

	while (j <= end)
		tmp[k++] = elem[j++];
	for (i = 0; i < k; i++)
		 elem[start + i] = tmp[i];
	free(tmp);
}
void merge_sort_up2down(ElemType elem[], int start, int end)
{
	if (elem == NULL || start >= end)
		return;

	int mid = (end + start) / 2;
	merge_sort_up2down(elem, start, mid); // 递归排序 elem[start...mid]
	merge_sort_up2down(elem, mid + 1, end); // 递归排序 elem[mid+1...end]
	Merge(elem, start, mid, end);
}
void MergeSort(SqList* L)
{
	int end = getLength(L) - 1;
	_LARGE_INTEGER start, finish;
	double Freq;
	LARGE_INTEGER f;
	QueryPerformanceFrequency(&f);
	Freq = (double)f.QuadPart;
	QueryPerformanceCounter(&start);
	merge_sort_up2down(L->elem, 0, end);
	QueryPerformanceCounter(&finish);
	if (verify(L))
	{
		cout << "通过" << endl;
	}
	else
	{
		cout << "不通过" << endl;
	}
	cout << "排序后：";
	myPrintf(L);
	cout << " 共用时： " << 1000000 * (finish.QuadPart - start.QuadPart) / Freq << " 微秒" << endl;
	cout << endl;
	destryList(L);
}
//模式一
void Mode1()
{
	SqList* Sq = NULL;
	char ch = NULL;
	printf("进入模式一\n"
		"1.插入排序\n"
		"2.希尔排序\n"
		"3.冒泡排序\n"
		"4.快速排序\n"
		"5.选择排序\n"
		"6.堆排序\n"
		"7.归并排序\n");
	while (true)
	{
		cin >> ch;
		switch (ch)
		{
		case'1':cout << "1、输入个数："; Sq = createSqByCin(); InsertSort(Sq); break;
		case'2':cout << "2、输入个数："; Sq = createSqByCin(); ShellSort(Sq); break;
		case'3':cout << "3、输入个数："; Sq = createSqByCin(); BubbleSort(Sq); break;
		case'4':cout << "4、输入个数："; Sq = createSqByCin(); QuickSort(Sq); break;
		case'5':cout << "5、输入个数："; Sq = createSqByCin(); SelectSort(Sq); break;
		case'6':cout << "6、输入个数："; Sq = createSqByCin(); HeapSort(Sq); break;
		case'7':cout << "7、输入个数："; Sq = createSqByCin(); MergeSort(Sq); break;
		default:return;
			break;
		}
	}
}
//模式二
void Mode2()
{
	SqList* Sq = NULL;
	char ch = NULL;
	printf("进入模式二\n"
	"1.插入排序\n"
	"2.希尔排序\n"
	"3.冒泡排序\n"
	"4.快速排序\n"
	"5.选择排序\n"
	"6.堆排序\n"
	"7.归并排序\n");
	while (true)
	{
		cin >> ch;
		switch (ch)
		{
		case'1':cout << "1、输入个数："; Sq = createSqByRandom(); InsertSort(Sq); break;
		case'2':cout << "2、输入个数："; Sq = createSqByRandom(); ShellSort(Sq); break;
		case'3':cout << "3、输入个数："; Sq = createSqByRandom(); BubbleSort(Sq); break;
		case'4':cout << "4、输入个数："; Sq = createSqByRandom(); QuickSort(Sq); break;
		case'5':cout << "5、输入个数："; Sq = createSqByRandom(); SelectSort(Sq); break;
		case'6':cout << "6、输入个数："; Sq = createSqByRandom(); HeapSort(Sq); break;
		case'7':cout << "7、输入个数："; Sq = createSqByRandom(); MergeSort(Sq); break;
		default:return;
			break;
		}
	}
}
int main(void) {
	srand((unsigned int)time(NULL));
	SqList* Sq = NULL;
	char ch = NULL;
	printf("选择模式：\n1.：输入模式\n2.：随机模式\n");
	while (true)
	{
		cin >> ch;
		switch (ch)
		{
		case '1':Mode1(); break;
			
		case '2':Mode2(); break;
		default:system("pause"); return 0;
			break;
		}
	}
	system("pause");
	return 0;
}