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

这篇具有很好参考价值的文章主要介绍了数据结构-火车车厢重排问题(队列实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

转轨站示意图如下：

火车车厢重拍问题,数据结构,C语言,数据结构,c语言

重排过程如下：

火车车厢重拍问题,数据结构,C语言,数据结构,c语言

伪代码

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 <stdio.h>
#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;
}