数据结构-火车车厢重排问题(队列实现)

问题描述

 转轨站示意图如下：

 重排过程如下：

 伪代码

1. 分别对k个队列初始化；
2. 初始化下一个要输出的车厢编号nowOut = 1; 
3. 依次取入轨中的每一个车厢的编号；
3.1 如果入轨中的车厢编号等于nowOut，则
    3.1.1 输出该车厢；
    3.1.2  nowOut++；
3.2 否则，考察每一个缓冲轨队列
    for (j=1; j<=k; j++)
 3.2.1 取队列 j 的队头元素c；
 3.2.2 如果c=nowOut，则
    3.2.2.1 将队列 j 的队头元素出队并输出；
    3.2.2.2  nowOut++； 
3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则
    3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;
3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；

晦涩的伪代码简直难啃，我们直接先分析一波这个实现过程 

        就算火车车厢的顺序打乱了之后，其编号也是连续的，可以利用这个点，所以我们定义三个队列：H1、H2、H3，将打乱的序列入队进H3，同时定义一个nowOut=1，让其自增，遍历序列H3，如当前遍历元素等于nowOut，那就将该元素出队，nowOut自增，否则就去H1和H2队列的对头去找有无等于nowOut的元素，若H1、H2、H3都没有nowOut，那么就将当前遍历的元素放进H1或H2条件是该元素必须大于H1或H2的队尾元素，如此循环完毕，最终可输出排列好的序列。

 代码实现

#include #define MAXSIZE 100
#define ERROR 0
#define OK 1
typedef int SElemType;
typedef int Status;
typedef struct Queue {
	SElemType data[MAXSIZE];
	int front;
	int rear;
} Queue;
//初始化队列 
void InitQueue(Queue *q) {
	q->data[0] = 0;
	q->front = 0;
	q->rear = 0;
}
//入队
Status EnQueue(Queue *q, SElemType num) {
	if(q->rear >= MAXSIZE - 1) {
		return ERROR;
	}
	q->data[q->rear] = num;
	q->rear++;
	return OK;
}
//出队
Status DeQueue(Queue *q, SElemType* num) {
	if(q->front >= q->rear) {
		return ERROR;
	}
	*num = q->data[q->front];
	q->front++;
	return OK;
}
//获取头元素 
Status GetHead(Queue *q, SElemType* num) {
	if(q->front >= q->rear) {
		return ERROR;
	}
	*num = q->data[q->front];
	return OK;
}
//获取尾元素 
Status GetRear(Queue *q, SElemType* num) {
	if(q->front >= q->rear) {
		return ERROR;
	}
	*num = q->data[q->rear-1];
	return OK;
}
int main() {
	Queue H1;
	InitQueue(&H1);
	Queue H2;
	InitQueue(&H2);
	Queue H3;
	InitQueue(&H3);
	Queue* QArray[] = {&H1, &H2, &H3};//指向结构体的指针数组,将H1,H2,H3放入数组 
	printf("请输入火车车厢,输入0停止输入\n");
	while(true) {//元素全部入队进H3 
		int num;
		scanf("%d", &num);
		if(num == 0) {
			break;
		}
		EnQueue(&H3, num);
	}
//	int num;
//	GetRear(&H3, &num);
//	printf("%d\n", num);
	int nowOut = 1;//火车车厢排序的关键 
	printf("\n出队序列为:");
	//遍历H3队列 
	while(H3.front < H3.rear || H1.front < H1.rear || H2.front < H2.rear) {
		int flag = 0;
		int num;
		GetHead(&H3, &num);
		//如果当前遍历元素等于nowOut就H3对头元素出队 
		if(num == nowOut) {
			DeQueue(&H3, &num);
			printf("%d", num);
			nowOut++;
			flag = 1;
		} else {
			//否则去寻找H1和H2对头元素是否等于nowOut,等于就出队 
			for(int i = 0; i < 2; i++) {
				GetHead(QArray[i], &num);
				if(num == nowOut){
					DeQueue(QArray[i], &num);
					printf("%d", num);
					nowOut++;
					flag = 1;
				}
			}
		}
		/*
		如果H1,H2,H3的对头都没有等于nowOut的元素,
		那么就将该元素入队至H1或H2,条件是小于队尾元素 
		*/
		if(flag == 0){
			int container;
			for(int i = 0; i < 2; i++){
				GetHead(&H3, &num);
				GetRear(QArray[i], &container);
				if(num > container || QArray[i]->rear == 0){
					DeQueue(&H3, &num);
					EnQueue(QArray[i], num);
					break;
				}
			}
		}
		
	}
	printf("\n\n2062011002-吴奇\n"); 
	return 0;
}

 测试用例

输入：369247185 0为结束符

输出：123456789

最后总结几个可以优化的点，感兴趣的小伙伴可以尝试实现以下

1. 该算法中用到的是队列的顺序存储结构，想要改为环形只需将出队入队操作的索引稍做修改，就可实现环形队列。
2. 输入方式比较不雅，可以进一步优化。
3. 如想实现任意乱序的排列，我认为应再加一个队列，用2个队列作为缓冲轨某些情况下运行不是想象中的结果。