taxis.cpp

一个DOS下的学生信息管理系统,使用了多中数值算法,有HASH查找,归并排序,快速排序,对排序

// Compositor.cpp: implementation of the CTaxis class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Taxis.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTaxis::CTaxis(STUDINFO pStudInfo[],UINT uiTaxisSort)
{
	this->pStudInfo=pStudInfo;

	//根据排序类别选择排序方法
	switch(uiTaxisSort)
	{
	case TAXISBY_STUDNUM:
		QuickTaxis();
		break;

	case TAXISBY_AGE:
		HeapTaxis();
		break;

	case TAXISBY_ALLMARK:
		MergeTaxis();
		break;

	default:
		break;
	}
}

CTaxis::~CTaxis()
{

}

void CTaxis::MergeTaxis()
{
	MergeSort(pStudInfo,pStudInfo,0,9);
}

void CTaxis::HeapTaxis()
{
	int i;
	STUDINFO siTemp;

	//把L[1...10]建成大顶堆
	for(i=4;i>=0;i--)
		HeapAdjust(pStudInfo,i,9);

	for(i=9;i>0;--i)
	{
		siTemp=pStudInfo[0];
		pStudInfo[0]=pStudInfo[i];
		pStudInfo[i]=siTemp;

		HeapAdjust(pStudInfo,0,i-1);
	}
}

void CTaxis::QuickTaxis()
{
	QuickSort(pStudInfo,0,9);
}

UINT CTaxis::Partition(STUDINFO L[],UINT uiLow,UINT uiHigh)
{
	UINT uiPivotKey;//枢轴关键字
	STUDINFO siBkUp=L[uiLow];

	uiPivotKey=L[uiLow].uiStudNum;
	while(uiLow<uiHigh)
	{
		while(uiLow<uiHigh && L[uiHigh].uiStudNum>=uiPivotKey)
			uiHigh--;
		L[uiLow]=L[uiHigh];

		while(uiLow<uiHigh && L[uiLow].uiStudNum<=uiPivotKey)
			uiLow++;
		L[uiHigh]=L[uiLow];
	}
	L[uiLow]=siBkUp;

	return uiLow;
}

void CTaxis::QuickSort(STUDINFO L[],int nLow,int nHigh)
{
	UINT uiPivotLoc;

	if(nLow<nHigh)
	{
		uiPivotLoc=Partition(L,nLow,nHigh);
		QuickSort(L,nLow,uiPivotLoc-1); //对低子表递归排序
		QuickSort(L,uiPivotLoc+1,nHigh);//对高子表递归排序
	}
}

void CTaxis::Merge(STUDINFO SourceL[], STUDINFO DestL[], int i, int m, int n)
{
	UINT j,k;
	UINT l;

	//将SourceL中记录由小到大的并入DestL
	for(j=m+1,k=i;i<=m && j<=n;++k)
		if((SourceL[i].pCourseInfo->uiMark+SourceL[i].pCourseInfo->pNext->uiMark)>
			(SourceL[j].pCourseInfo->uiMark+SourceL[j].pCourseInfo->pNext->uiMark))
			DestL[k]=SourceL[i++];
		else
			DestL[k]=SourceL[j++];

	if(i<=m)
		for(l=k;l<=n;l++)
			DestL[l]=SourceL[i+l-k];

	if(j<=n)
		for(l=k;l<=n;l++)
			DestL[l]=SourceL[j+l-k];
}

void CTaxis::MergeSort(STUDINFO SourceL[], STUDINFO DestL[], int s, int t)
{
	UINT uiMid;
	STUDINFO DestL2[10];

	if(s==t)
		DestL[s]=SourceL[s];
	else
	{
		uiMid=(s+t)/2;                      //将SourceL[s..t]平分为SourceL[s..uiMid]和SourceL[uiMid+1..t]
		MergeSort(SourceL,DestL2,s,uiMid);  //递归的将SourceL[s..uiMid]归并为有序的DestL2[s..uiMid]
		MergeSort(SourceL,DestL2,uiMid+1,t);//递归的将SourceL[uiMid+1..t]归并为有序的DestL2[uiMid+1..t]
		Merge(DestL2,DestL,s,uiMid,t);      //将DestL2[s..uiMid]和DestL2[uiMid+1..t]归并到DestL[s..t]
	}
}

void CTaxis::HeapAdjust(STUDINFO L[], int s, int m)
{
	//已知L[s...m]中的记录除L[s]之外均满足堆的定义，本函数调整H[s],使L[s...m]成为一个大顶堆
	STUDINFO rc=L[s];
	UINT j;

	for(j=2*s+1;j<=m;j=2*j+1)
	{
		//沿较大值的孩子节点向下筛选
		if(j<m && L[j].uiAge<L[j+1].uiAge)
			j++;

		if(rc.uiAge>=L[j].uiAge)
			break;

		L[s]=L[j];
		s=j;
	}
	L[s]=rc;
}

void CTaxis::StudInfoJ2I(UINT i,UINT j)
{
	if(i==j)
		return;

	//pStudInfo[i]=pStudInfo[j]
	strcpy(pStudInfo[i].pName,pStudInfo[j].pName);
	pStudInfo[i].uiStudNum=pStudInfo[j].uiStudNum;
	pStudInfo[i].uiAge=pStudInfo[j].uiAge;
	strcpy(pStudInfo[i].pSex,pStudInfo[j].pSex);

	strcpy(pStudInfo[i].pCourseInfo->pCourse,pStudInfo[j].pCourseInfo->pCourse);
	pStudInfo[i].pCourseInfo->uiMark=pStudInfo[j].pCourseInfo->uiMark;
	strcpy(pStudInfo[i].pCourseInfo->pTeacher,pStudInfo[j].pCourseInfo->pTeacher);

	strcpy(pStudInfo[i].pCourseInfo->pNext->pCourse,pStudInfo[j].pCourseInfo->pNext->pCourse);
	pStudInfo[i].pCourseInfo->pNext->uiMark=pStudInfo[j].pCourseInfo->pNext->uiMark;
	strcpy(pStudInfo[i].pCourseInfo->pNext->pTeacher,pStudInfo[j].pCourseInfo->pNext->pTeacher);
}