sort.h

这是同一个数据结构的课程设计,由C++语言编写的

#ifndef _SORT_H_ 
#define _SORT_H_ 

#include <stdlib.h>
#include <iostream.h>

typedef struct queuenode{  //链队列中的结点类型
	int data;
	struct queuenode *next;
}QueueNode;

typedef struct linkqueue{
	QueueNode *front;  //队头指针
	QueueNode *rear;   //队尾指针
}LinkQueue;

#define KeySize  6    //设关键字位数 d=6;
#define RadixNum 10   //基数 rd 为 10;


template <class T>
class sort {
public:
	sort(int s)
	{
		if (s < 0)
		{
			cerr << "** An invalid array size was entered." << endl;
			exit(-1);
			return;
		}
		size = s;	
	};


	void Insertion(T R[]);	     // 直接插入	

	void Shell(T R[]);           // 希尔排序

	void Selection(T R[]);	     // 直接选择

	void Bubble(T R[]);		     // 冒泡排序
	
	void Quick(T R[], int, int); // 快速排序

	void Heap(T R[]);            // 堆排序
	
	void Merge(T R[]);           // 归并排序

	void Radix(T R[]);           // 基数排序

protected:
	void ShellPass(T R[], int d);    //希尔排序中的一趟排序 

	int Partition(T R[], int i, int j);  //快速排序的区间划分

	void BuildHeap(T R[]);                  //将初始文件R[1..n]构造为大根堆
	void Heapify(T R[], int low, int high); //将R[low..high]调整为大根堆 	
	
	void MergeEx(T R[], int low, int m, int high);  //将两个有序的子文件归并成一个有序的子文件
	void MergePass(T R[], int length);              //做一趟归并排序

	void Distribute(T R[], LinkQueue B[], int j);  //按关键字的第j个分量进行分配
	void Collect(T R[], LinkQueue B[]);            //依次将各非空看箱子中的记录连接起来

protected:
	void InitQueue(LinkQueue *Q) { Q->front = Q->rear = NULL; }
	int  QueueEmpty(LinkQueue *Q) { return Q->front == NULL && Q->rear == NULL; }
	void EnQueue(LinkQueue *Q, int x)
	{
		QueueNode *p = new QueueNode;
		p->data = x;
		p->next = NULL;
		if (QueueEmpty(Q))
			Q->front = Q->rear = p;
		else
		{
			Q->rear->next = p;
			Q->rear = p;
		}
	}
	int DeQueue(LinkQueue *Q)
	{
		int x;
		QueueNode *p;
		if (!QueueEmpty(Q))
		{
			p = Q->front;
			x = p->data;
			Q->front = p->next;
			if (Q->rear == p)
				Q->rear = NULL;
			delete p;
		}
		return x;
	}

private:
	int size;
};



#endif