基数排序.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵
typedef RecType DataType;		//将队列中结点数据类型改为与文件中记录类型一致

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

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

void InitQueue(LinkQueue *Q)
{
	Q->front=Q->rear=NULL;
}

int QueueEmpty(LinkQueue *Q)
{
	return Q->front==NULL&&Q->rear==NULL;
	//实际上只须判队头指针是否为空即可
}

void EnQueue(LinkQueue *Q,DataType x)
{	//将元素x插入链队列尾部
	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
	p->data=x;
	p->next=NULL;
	if (QueueEmpty(Q))
		Q->front=Q->rear=p;			//将x插入空队列
	else							//x插入非空队列的尾
	{
		Q->rear->next=p;			//*p链到原队尾结点后
		Q->rear=p;					//队尾指针指向新的尾
	}
}

DataType DeQueue(LinkQueue *Q)
{	DataType x;
	QueueNode *p;
	if (QueueEmpty(Q))
	{	printf("Queue underflow");
		exit(0);					//下溢
	}
	p=Q->front;						//指向队头结点
	x=p->data;						//保存队头结点的数据
	Q->front=p->next;				//将队头结点从链上摘下
	if (Q->rear==p)
	//原队中只有一个结点，删去后队列变空，此时队头指针已为空
		Q->rear=NULL;
	free(p);						//释放被删队头结点
	return x;						//返回原队头数据
}

DataType QueueFront(LinkQueue *Q)
{
	if(QueueEmpty(Q))
	{	printf("Queue is empty");
		exit(0);
	}
	return Q->front->data;
}

void Distribute(SeqList R,LinkQueue B[],int j);
void Collect(SeqList R,LinkQueue B[]);

void main()
{
	void RadixSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=0;i<n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=0;i<n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	RadixSort(R);
	printf("排序后：");
	for (i=0;i<n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

#define KeySize 4				//不妨设关键字位数d=4
#define Radix 10				//基数rd为10

void RadixSort(SeqList R)
{	//对R[0..n-1]进行基数排序，R[i].key为非负整数，且位数不超过KeySize
	LinkQueue B[Radix];			//10个箱子，每个都是一个链队列
	int i;

	for(i=0;i<Radix;i++)		//初始化
		InitQueue(&B[i]);		//箱子置空
	for(i=KeySize-1;i>=0;i--){	//从低位到高位做d趟箱排序
		Distribute(R,B,i);		//第KeySize-i趟分配
		Collect(R,B);			//第KeySize-i趟收集
	}
}

void Distribute(SeqList R,LinkQueue B[],int j)
{	//按关键字的第j个分量进行分配，进入此过程时各箱子一定为空
	int i,k,t;
	j=KeySize-j;				//确定关键字从个位起是第几位
	for(i=0;i<n;i++){			//依次扫描R[i]，将其装箱
		k=R[i].key;
		for(t=1;t<j;t++) k=k/10;
		k=k%10;					//取关键的第j位（从低位开始）数字k
		EnQueue(&B[k],R[i]);	//将R[i]装入箱子B[k]
	}
}

void Collect(SeqList R,LinkQueue B[])
{	//依次将各非空箱子中的记录收集起来，本过程结束时各箱子均变空
	int i=0,j;
	for(j=0;j<Radix;j++)			//注意：各箱子中记录数之和必为n
		while(!QueueEmpty(&B[j]))
			R[i++]=DeQueue(&B[j]);	//将出队记录依次输出到R[i]中
}