ds.cpp

一个数据结构课程设计源码

#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>
#include <windows.h>


void copyshuzu (int *d,int *s,long n)
{
	long i;
	for (i=0;i<n;i++)
		d[i+1]=s[i];
}

void paixu1 (int *key,long n) //第一种排序 插入排序
{
	long i,j;
	for (i=1;i<=n;++i)
		if (key[i]<key[i-1])
		{key[0]=key[i];
			for (j=i-1;key[0]<key[j];--j)
				key[j+1]=key[j];
			key[j+1]=key[0];
		}
}

long partition(int *L,long low,long high)
{   
	int pivotkey;
	L[0]=L[low];
	pivotkey=L[low];
	while (low<high){
		while (low<high&&L[high]>=pivotkey) --high;
		L[low]=L[high];
		while (low<high&&L[low]<=pivotkey) ++low;
		L[high]=L[low];
	}
	L[low]=L[0];
	return low;
}

void qsort(int *L,long low,long high)
{
	long pivotloc;
	if(low<high){
		pivotloc=partition(L,low,high);
		qsort(L,low,pivotloc-1);
		qsort(L,pivotloc+1,high);
	}
}

void paixu2(int *key,long n)  //第二种排序 快速排序
{
	qsort(key,1,n);
}

void heapadjust (int *H,long s,long m)
{	
	long j;
	int rc;
	rc=H[s];
	for(j=2*s;j<=m;j*=2){
		if(j<m&&(H[j]<H[j+1]))  ++j;
		if(!(rc<H[j]))	break;
		H[s]=H[j];
		s=j;
	}
	H[s]=rc;
}

void paixu3(int *L,long n)	//第三种排序 堆排序
{
	long i;
	int t;
	for(i=n/2;i>0;--i)
		heapadjust(L,i,n);
	for(i=n;i>1;--i){
		t=L[1];
		L[1]=L[i];
		L[i]=t;
		heapadjust(L,1,i-1);
	}
}

void paixu4(int *x, long n)  //第四种排序 选择排序
{
	int i, j, min, t;
	for (i=1; i<n; i++)
		{
		min = i; 
		for (j=i+1; j<=n; j++)
			{
			if (x[j] < x[min]) {
				min = j;
			}
		}  
		if (min != i) 
		{
			t = x[i];
			x[i] = x[min];
			x[min] = t;
		}
	}
}

void nixu(int *key,long n)
{
	long i;
	int t;
	for (i=0;i<n/2;i++) {
		t=key[i];
		key[i]=key[n-i-1];
		key[n-i-1]=t;
	}
}

void paixu5(int *x, long n)   //第四种排序 希尔择排序
{
	long h, j, k;
	int t;
	for (h=n/2; h>0; h=h/2) {
		for (j=h; j<n; j++) {
			t = *(x+j);
				for (k=j-h; (k>=0 && t<*(x+k)); k-=h) {
					*(x+k+h) = *(x+k);
				}
				*(x+k+h) = t;
		}
	}
}

void main (void)
{
	long i,n;
	LARGE_INTEGER t,a,b,feq;
	int *key;
	int *L;
	int j,leixing;
	double shijian[3][5];
	srand((unsigned)time(NULL));
	QueryPerformanceFrequency(&feq);
l1:	printf("请输入n(1≤n≤100000):");
	scanf("%ld",&n);
	if (n<1 || n>100000) {
		printf("范围错误！，请重新输入！\n");
		goto l1;
	}
	key=(int *)malloc(sizeof(int)*n);
	L=(int *)malloc(sizeof(int)*(n+1));
	if (key==NULL) {
		printf("内存不足！\n");
		exit(-1);
	}
	printf("自动生成随机数据中。。。\n");
	for (i=0;i<n;i++) {
		key[i]=rand();
		//printf("%d\t",key[i]);
	}
	printf("数据成功生成完毕！\n开始对随机数据进行排序。。。\n");
	for (leixing=0;leixing<3;leixing++) {
		copyshuzu(L,key,n);
		printf("开始执行第一种排序：插入排序。。。\n");
		QueryPerformanceCounter(&a); 
		paixu1(L,n);
		QueryPerformanceCounter(&b); 
		shijian[leixing][0]=((double)b.QuadPart-(double)a.QuadPart)/((double)feq.QuadPart);
		printf("执行成功！\n");
		copyshuzu(L,key,n);
		printf("开始执行第二种排序：快速排序。。。\n");
		QueryPerformanceCounter(&b);
		if(n<=10000) paixu2(L,n);
		QueryPerformanceCounter(&a); 
		shijian[leixing][1]=((double)a.QuadPart-(double)b.QuadPart)/((double)feq.QuadPart);
		printf("执行成功！\n");
		copyshuzu(L,key,n);
		printf("开始执行第三种排序：堆排序。。。\n");
		QueryPerformanceCounter(&a); 
		paixu3(L,n);
		QueryPerformanceCounter(&b); 
		shijian[leixing][2]=((double)b.QuadPart-(double)a.QuadPart)/((double)feq.QuadPart);
		printf("执行成功！\n");
		copyshuzu(L,key,n);
		printf("开始执行第四种排序：选择排序。。。\n");
		QueryPerformanceCounter(&b); 
		paixu4(L,n);
		QueryPerformanceCounter(&a); 
		shijian[leixing][3]=((double)a.QuadPart-(double)b.QuadPart)/((double)feq.QuadPart);
		printf("执行成功！\n");
		printf("开始执行第五种排序：希尔排序。。。\n");
		QueryPerformanceCounter(&a); 
		paixu5(key,n);
		QueryPerformanceCounter(&b); 
		shijian[leixing][4]=((double)b.QuadPart-(double)a.QuadPart)/((double)feq.QuadPart);
		printf("执行成功！\n");
		switch (leixing) {
			case 0:
				printf("自动生成正序数据中。。。\n");
				printf("数据成功生成完毕！\n开始对正序数据进行排序。。。\n");
				break;
			case 1:
				printf("自动生成逆序数据中。。。\n");
				nixu(key,n);
				printf("数据成功生成完毕！\n开始对随机数据进行排序。。。\n");
				break;
		}
	}
	printf("\n数据\t插入排序\t快速排序\t堆排序\t\t选择排序\t希尔排序");
	for(i=0;i<3;i++) {
		switch (i) {
			case 0:	printf("随机");
				break;
			case 1:	printf("正序");
				break;
			case 2:	printf("逆序");
				break;
		}
		for (j=0;j<5;j++) printf("\t%lg\t",shijian[i][j]*1000000);
		//printf("\n");
	}
	printf("\npress enter to continue....");
	getchar();
	getchar();
	

}