火车车厢重排问题,队列,c语言

计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼
学生姓名肖宇博试验时间2012-4-21
试验项目算法与数据结构
试验类别基础性（）设计性（）综合性（√）其它（）试
验目的及要求（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。

成绩评定表
类别评分标准分值得分合计
上机表现积极出勤、遵守纪律
主动完成设计任务
30分
程序与报告程序代码规范、功能正确
报告详实完整、体现收获
70分
goto label2;
}
else if(r!=0)
{
printf("重排前的序列为\n");
for(i=1;i<=k;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
printf("排列后的车厢号为：\n");
reset(q,w1,w2,k);
}
else
{
printf("我也不知道错哪了？'");
}
}
四、测试用例（尽量覆盖所有分支）
1.输入正确的序列后得到结果如图：
2.倒输这几个数如图：
3.顺序输这个序列
4.如果输入的车厢数有误的时候（为负数或零）
5.如果输入的序列不是连续自然数。

火车车厢重排问题1.1火车车厢重排问题一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1~n,货运列车按照第n站至第1站的顺序经过这些车站。

车厢编号与他们的目的地一样。

为了便于从列车上卸掉相应的车厢，必须重排车厢顺序，使得各车厢从前往后按编号1到n的次序排列。

当所有车厢按照这种次序排列时，在每个车站只需卸掉最后一个车厢即可。

1.2想法一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。

比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排我们在一个转轨站里完成重拍的工作，在转轨站有一个入轨，一个出轨和k个缓冲轨（位于入轨和出轨之间）。

下面的图示就是一个转轨站，其中有3个缓冲轨，H1,H2,H3。

（PPT中有动态演示）1.3算法描述：那么缓冲轨就不是FILO 而是FIFO了那么就要用队列来实现车厢重排了，算法的描述和栈实现的基本一样的，只是OutPut和Hold 函数改了一下，将一截车厢移动到缓冲轨时，车厢c应该移动到这样的缓冲轨中：该缓冲轨中现有各车厢的编号均小于c，如果有多个缓冲轨都满足这一条件，那么选择其中左端车厢编号最大的那个缓冲轨，否则选择一个空的缓冲轨(如果存在的话)1.4代码：#include<iostream>#include<stack>usingnamespace std;template<class T>void PrintfNum(T a[], constint& n);// move cars from holding track to output trackvoid OutPut(stack<int> t[],int n, int totalStack,int& min){//move car from holding trackfor(int x = 0;x <totalStack; ++x){if(!t[x].empty() && t[x].top() == min){cout<<"Move car "<< t[x].top() <<" from holding track "<< x <<" to output"<<endl;t[x].pop();++min;x = -1; // find next car from the first holding track 0}}}// move cars from input track to holding trackbool Hold(stack<int> t[],int n , int totalStack){for(int i = 0;i <totalStack; ++i){if(t[i].empty() || (!t[i].empty() && t[i].top() > n)){cout<<"holding track "<<i<<" hold car "<< n <<endl;t[i].push(n);returntrue; // we already find a holding track, so break the loop. }}returnfalse;}int main(int argc, char* argv[]){constint NUM = 9;constint STACKNUM = 3;stack<int> t[STACKNUM];int min = 1;int a[NUM] = {5,8,1,7,4,2,9,6,3};PrintfNum(a,NUM);for(int i = NUM - 1; i>= 0; --i){if(a[i] == min){// try to move cars from input track or holding track cout<<"Move car "<< a[i] <<" from input to output"<<endl;++min;OutPut(t,a[i],STACKNUM,min);}else{// move cars from input track to holding trackif(!Hold(t,a[i],STACKNUM)){cout<<"Not enough holding track"<<endl;break;}}} getchar();return 0;}template<class T>void PrintfNum(T a[], constint& n){for(int i = 0; i< n; ++i){cout<< a[i] <<",";}cout<<endl;}1.5火车车厢重排问题决策过程H1H2H31.5.1初始数组H1 H2 H31.5.2H1H2H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3 1．6程序运行截图。

实验2用堆栈解决火车车厢重排问题的编程一、目的通过对本次实验，我们应：1、加深对线性表、堆栈的认识；2、加深接口、类、索引器的认识；3、掌握堆栈数据结构，并应用堆栈编程解决实际问题。

二、实验准备1、软件准备：C#.net。

2、参考数据（示例）：文件夹“…\实验2\示例”中的数据。

三、实验背景描述1、问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。

车厢的编号与它们的目的地相同。

为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。

当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。

图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。

开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。

在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。

图3.1b 给出了按所要求的次序重新排列后的结果。

图2.1根据上面的描述，编写程序实现下面的功能：编写一算法实现火车车箱的重排；编写程序模拟图2.1所示的具有9节车厢的火车入轨和出轨的过程。

程序主界面设计如图2.2所示。

图2.22、问题分析为了重排车厢，需从前至后依次检查入轨上的所有车厢。

如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。

如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。

缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。

当缓冲铁轨上的车厢编号不是按照从顶到底的递增次序排列时，重排任务将无法完成。

新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v>u,且v是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。

火车车厢重排问题栈c语言以下是一个用C语言实现火车车厢重排问题的代码：```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int val;struct Node* next;} Node;typedef struct {Node* top;} Stack;Stack* createStack() {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->top = NULL;return stack;}int isEmpty(Stack* stack) {return (stack->top == NULL);}void push(Stack* stack, int val) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = val;newNode->next = stack->top;stack->top = newNode;}int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}int val = stack->top->val;Node* temp = stack->top;stack->top = stack->top->next;free(temp);return val;}int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}return stack->top->val;}int canReorder(int numCars, int cars[]) { Stack* stationStack = createStack(); Stack* branchStack = createStack(); int nextCar = 1;for (int i = 0; i < numCars; i++) {// 如果当前车厢和需要出站的车厢一致，直接出站if (cars[i] == nextCar) {nextCar++;continue;}// 将从站台出来的车厢压入分支轨道while (!isEmpty(stationStack) && peek(stationStack) == nextCar) {push(branchStack, pop(stationStack));nextCar++;}// 当前车厢进站push(stationStack, cars[i]);}// 如果分支轨道中的车厢可以按顺序出站，则返回1，否则返回0while (!isEmpty(branchStack)) {if (pop(branchStack) != nextCar) {return 0;}nextCar++;}return 1;}int main() {int numCars;int cars[MAX_SIZE];printf("Enter the number of train cars: ");scanf("%d", &numCars);printf("Enter the train car numbers: ");for (int i = 0; i < numCars; i++) {scanf("%d", &cars[i]);}int result = canReorder(numCars, cars);if (result) {printf("Yes, it is possible to reorder the train cars.\n"); } else {printf("No, it is not possible to reorder the train cars.\n"); }return 0;}```输入示例：```Enter the number of train cars: 5Enter the train car numbers: 3 1 2 4 5```输出示例：```Yes, it is possible to reorder the train cars. ```。

车厢调度问题解析（经典递归）博客分类：zhanghonglun算法算法题目假设停在铁路调度站入口处的车厢系列的编号依次为1，2，3，…n。

设计一个程序,求出所有可能由此输出的长度为n 的车厢系列。

解析:一个数的进栈以后,有两种处理方式：要么立刻出栈，或者下一个数的进栈(如果还有下一个元素)其出栈以后，也有两种处理方式：要么继续出栈（栈不为空），或者下一个数的入栈。

该问题有天然的递归性质算法设计:两重递归，下一个元素处理完后返回，再处理出栈的递归,有点像嵌套循环，但比它复杂...进栈的递归跳出条件为最后一个元素进栈出栈的递归跳出条件为栈空附上经典实现代码C代码1.#include<stdafx.h>2.#include<stdio.h>3.#define MaxLen 1004.struct snode{5. int data[MaxLen];6. int top;7.}s;//定义一个栈指针8.int n;//定义输入序列总个数9.void Initstack()10.{11. s.top=-1;12.}13.void push(int q)//元素n进栈14.{15. s.top++;16. s.data[s.top]=q;17.}18.int pop()//出栈19.{20. int temp;21. temp=s.data[s.top];22. s.top--;23. return temp;24.}25.int Emptys()//判断栈空26.{27. if(s.top==-1)28. return 1;29. else30. return 0;31.}32./*33.每次调用求值阶段包含两重递归，只有全部返回，才表示本pos 处理完，可以对上一个元素求值，process 就是找出当前元素进栈后所有可能的操作，即在当前元素进栈后各种情况下，34.包括不出栈，立即出栈，出栈后继续出栈情况(出栈递归)下，继续处理下一个元素(入栈递归)35.36.*/37.void process(int pos,int path[],int curp)//当前处理位置pos的元素38.{39. int m,i;40. if(pos<n)//编号进栈递归41. {42. push(pos+1);//当前元素进栈后下一个元素继续进栈43. process(pos+1,path,curp); //处理下一个元素，返回表明下一个元素进栈的情况处理完了44. pop(); //下一个元素处理完后，pop 掉，准备处理直接出栈45. }46.47. if(!Emptys())//递归处理出栈48. {49. m=pop();50. path[curp]=m;51. curp++;52. process(pos,path,curp);//出栈后处理下一个素继续进栈53. push(m);54. }55. if(pos==n&&Emptys())//输出一种可能的方案56. {57. for(i=0;i<curp;i++)58. printf("%2d",path[i]);59. printf("\n");60. }61.}62.void main()63.{64. int path[MaxLen];65. printf("输入要调度车厢总数:");66. scanf("%d",&n);67. Initstack();68. push(1);69. printf("所有输出序列:\n");70. process(1,path,0); //从1 开始，递归处理所有元素71.}。

一、实验目的队列的应用二、实验内容利用队列结构实现车厢重排问题。

三、算法描述利用一个队列组中的多个队列充当缓冲轨，根据需要动态对其分配空间。

进入缓冲轨前，要求与已有的缓冲轨的队尾元素进行比较，当队尾元素小时入队，否则进入一个新的缓冲轨；当入轨为空时，进行出队操作，每次出队之前，比较每个缓冲轨队头元素的值大小，小的先出队。

四、算法实现int EnQueue(LinkQueue &Q,int e)//排列{QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;}int DeQueue(LinkQueue &Q,int &e){QueuePtr p;if(Q.front==Q.rear)return(0);p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return 1;}int RanQueue(LinkQueue &Q,LinkQueue &D,int n){int p=0,q=0,i=0,j=0,k=0;LinkQueue T[10];InitQueue(T[0]);DeQueue(Q,p);EnQueue(T[0],p);loop1: while(Q.front!=Q.rear){DeQueue(Q,p);for(i=0;i<=j;i++){if(p>T[i].rear->data){EnQueue(T[i],p);goto loop1;}}j++;InitQueue(T[j]);EnQueue(T[j],p);}do{for(i=0;i<=j;i++){if(T[i].front!=T[i].rear){p=T[i].front->next->data;q=i;}}for(i=0;i<=j;i++){if(T[i].front!=T[i].rear&&p>T[i].front->next->data){p=T[i].front->next->data;q=i;}}DeQueue(T[q],p);EnQueue(D,p);k++;}while(k!=n);return 1;}五、实验结果五、心得体会为达到动态创建队列的目的，使用队列数组，根据需要动态对其分配空间，但是还是受到定义数组初始队列数的限制，当列车节数足够大时依然会导致内存空间不足。

火车车厢重排问题栈c语言火车车厢重排问题是一个经典的问题，考验了数据结构和算法的运用。

这个问题可以很好地帮助我们了解如何使用栈这种数据结构来解决实际问题，并且可以通过编写C语言程序对其进行求解。

在本文中，我们将深入探讨火车车厢重排问题，并编写C语言程序实现问题的求解。

首先，让我们来了解一下火车车厢重排问题的具体描述。

假设有一列火车车厢按照编号从1到n的顺序排列在轨道上。

现在我们需要将这些车厢按照特定的顺序重新排列，给定一个目标排列，我们需要找出一种排列车厢的方法，使得最终的排列符合目标排列。

具体而言，对于每一个车厢，我们可以将其从原来的位置移动到一个临时的缓冲轨道中，然后再将其移动到目标位置。

这个问题的关键在于如何确定每个车厢应该如何移动才能满足最终的目标排列。

为了解决这个问题，我们可以使用栈这种数据结构来辅助实现。

栈是一种先进后出的数据结构，这样的特性非常适合用来模拟火车车厢的重排过程。

具体而言，我们可以将原始轨道上的车厢编号序列作为输入，然后使用栈来模拟车辆的移动过程，最终得到目标排列。

下面我们将通过C语言程序来实现这个过程。

首先，我们需要定义一个栈的数据结构，来模拟车厢的移动过程。

我们可以使用数组来实现这个栈，同时需要定义一个栈顶指针来表示当前栈顶元素的位置。

另外，我们还需要定义一个函数来模拟入栈和出栈的过程。

接下来，让我们来具体实现这个栈的数据结构和相关的函数。

```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} Stack;void init(Stack *s) {s->top = -1;}void push(Stack *s, int value) { if (s->top < MAX_SIZE - 1) {s->top++;s->data[s->top] = value;} else {printf("Stack overflow\n");}}int pop(Stack *s) {if (s->top >= 0) {int value = s->data[s->top];s->top--;return value;} else {printf("Stack underflow\n"); return -1;}}int main() {Stack s;init(&s);//对栈进行入栈和出栈操作push(&s, 1);push(&s, 2);push(&s, 3);printf("%d\n", pop(&s)); //输出3printf("%d\n", pop(&s)); //输出2printf("%d\n", pop(&s)); //输出1printf("%d\n", pop(&s)); //输出Stack underflow，表示栈已空return 0;}```在这段代码中，我们定义了一个栈的数据结构，并实现了栈的初始化、入栈和出栈操作。

火车车厢重排问题c++解决方法（队列实现）//Queue.h#ifndef QUEUE_H#define QUEUE_H#include<iostream>using namespace std;template<typename T>class Queue{public:virtual void MakeEmpty()=0;virtual void Enqueue(T x)=0;virtual T Dequeue()=0;virtual bool IsEmpty()const=0;virtual bool IsFull()const=0;virtual T GetFirstItem()=0;};class EmptyQueue{};class FullQueue{};#endif//LinkQueue.h //链表队列#ifndef LINKQUEUE_H#define LINKQUEUE_H#include<iostream>#include"Queue.h"using namespace std;template<typename T>struct Node{T date;Node<T> *next;};template<typename T>class LinkQueue:public Queue<T>{template<typename T>friend ostream & operator<<(ostream &s,const LinkQueue<T> &lq);public:LinkQueue();~LinkQueue();void MakeEmpty();void Enqueue(T x);T Dequeue();bool IsEmpty()const;bool IsFull()const;T GetFirstItem();T GetlastItem();private:Node<T> *front;Node<T> *rear;};template<typename T>LinkQueue<T>::LinkQueue(){front=new Node<T>;front->next=NULL;rear=front;}template<typename T>LinkQueue<T>::~LinkQueue(){MakeEmpty();delete front;}template<typename T>void LinkQueue<T>::Enqueue(T x) {Node<T> *newnode;newnode=new Node<T>;newnode->date=x;newnode->next=NULL;rear->next=newnode;rear=newnode;}template<typename T>T LinkQueue<T>::Dequeue(){if(IsEmpty())throw EmptyQueue();Node<T> *p;p=front->next;T x=p->date;front->next=p->next;if(p->next==NULL)rear=front;delete p;return x;}template<typename T>bool LinkQueue<T>::IsFull()const {return false;}template<typename T>bool LinkQueue<T>::IsEmpty()const {return front==rear;}template<typename T>T LinkQueue<T>::GetFirstItem() {if(IsEmpty())throw EmptyQueue();Node<T> *p;p=front->next;return p->date;}template<typename T>T LinkQueue<T>::GetlastItem() {if(IsEmpty())throw EmptyQueue();return rear->date;}template<typename T>void LinkQueue<T>::MakeEmpty() {Node<T> *p;while(front->next!=NULL){p=front->next;front->next=p->next;delete p;}}template <typename T>ostream & operator<<(ostream &s,const LinkQueue<T> &lq){Node<T> *p;p=lq.front->next;while(p!=NULL){s<<p->date<<" ";p=p->next;}return s;}#endif//TrainResort.h//火车车厢重排代码核心部分#ifndef TRAINRESORT#define TRAINRESORT#include<iostream>#include"LinkQueue.h"using namespace std;class TrainResort{friend ostream & operator <<(ostream &s,TrainResort &tr); public:TrainResort(LinkQueue<int> *or,int m=3);~TrainResort();private:int buf;LinkQueue<int> orbit;LinkQueue<int> *buffer;};TrainResort::TrainResort(LinkQueue<int> *or,int m){buf=m;while(!or->IsEmpty())orbit.Enqueue(or->Dequeue());buffer=new LinkQueue<int>[buf];}TrainResort::~TrainResort(){delete []buffer;}ostream & operator <<(ostream &s,TrainResort &tr){int nowOut=1;int temp;int x,y;int z;while(!tr.orbit.IsEmpty()){x=0,y=0;z=0;temp=tr.orbit.Dequeue();if(temp==nowOut){tr.buffer[0].Enqueue(nowOut);nowOut++;for(int j=1;j<tr.buf;j++){int k=0;while(!tr.buffer[j].IsEmpty()&&tr.buffer[j].GetFirstItem()==nowOu t){tr.buffer[0].Enqueue(nowOut);nowOut++;tr.buffer[j].Dequeue();k++;}if(k!=0){if(temp==nowOut){tr.buffer[0].Enqueue(nowOut);nowOut++;}j=0;}}}else{for(int j=1;j<tr.buf;j++){if(!tr.buffer[j].IsEmpty()){if(temp-tr.buffer[j].GetlastItem()>0){y=(x>temp-tr.buffer[j].GetlastItem()?y:j);x=(y==j?temp-tr.buffer[j].GetlastItem():x);}}else{z=j;}}if(y!=0){tr.buffer[y].Enqueue(temp);}else if(z!=0){tr.buffer[z].Enqueue(temp);}else{s<<"Don't resort!";break;}}}s<<tr.buffer[0];return s;}#endif（注：可编辑下载，若有不当之处，请指正，谢谢!）。

数据结构实验报告实验名称：实验四队列的应用学生姓名：班级：班内序号：15学号：日期：2016.12.211．实验要求题目二：队列的应用利用队列结构实现车厢重排问题。

车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。

给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。

转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。

开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。

缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。

提示：1、一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。

比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。

2. 程序分析2.1 存储结构我使用了线性表的链式存储结构，通过建立单链表进行顺序存取初始车厢编号。

每个节点分为data、next。

data域称为数据域，数据通过node结构存储车厢编号；next为指针域，用来储存直接后继的地址。

struct node{int data;node*next;};2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)class LinkQueue{private:node*front;node*rear;public:LinkQueue() //无参构造函数{front = rear = new node;front->next = NULL;}void EnQueue(int x); //入队void show(int num); //输出缓冲轨~LinkQueue(); //析构函数};void line(int*zzj, LinkQueue*jay, int n) //建立缓冲轨队列2.3 关键算法分析入队函数：通过尾插法进行链表队列的入队操作。

目录一、功能描述 (2)1、输入火车厢信息 (2)2、入轨 (2)3、出轨 (2)4、退出 (2)二、总体概要设计 (2)1、系统设计框图: (2)2、系统设计流程图 (3)三、详细设计 (3)1 功能一：输入火车厢信息 (3)1）概要设计： (3)2）算法描述： (3)3)算法分析 (4)2 功能二：入轨 (4)1）概要设计： (4)2）算法描述： (4)3)算法分析： (7)3 功能三：出轨 (8)1）概要设计 (8)2）算法描述： (8)3）算法分析: (11)4 功能四：退出 (11)四、效果及存在问题 (11)1、效果显示: (11)1）输入火车厢信息 (12)2）入轨 (12)3）出轨： (12)4）显示重排完成车厢排列 (13)2、存在问题 (13)五、心得及体会 (14)六、参考文献 (14)七、评分表（见尾页）.............................. 错误！未定义书签。

附录：源代码. (14)一、功能描述1、输入火车厢信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。

2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。

3、出轨给出每节火车厢出轨提示。

4、退出如果不需要操作就退出系统。

二、总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。

1、系统设计框图:2、系统设计流程图三、详细设计1 功能一：输入火车厢信息1）概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排列信息，并在屏幕上显示火车原始排列。

2）算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：int i,M,A[100],N=0;printf("\n\n");printf("************************************************************\n\n"); printf("===============您好,欢迎光临火车转轨系统！===============\n\n");printf("请输入您要进行转轨的火车车厢总长：");scanf("%d",&M);printf("\n请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢号\n\n");for(i=0;i<M;i++){scanf("%d",&A[i]);}printf("未转轨前的火车厢排列如下，请核对：\n");for(i=0;i<M;i++)printf("A[%d]=%d\n",i,A[i]);3)算法分析：此功能模块简单明了没有深度算法，在此不做分析。

一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。

二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。

为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。

所以，给定任意次序的车厢，必须重新排列它们。

车厢的重排工作可以通过国转轨站完成。

在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。

假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。

(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：2222(a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨 (d) 将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：四、源程序代码#include<iostream>using namespace std;const MS=100;template <class T>struct QNode{T data;QNode<T> *next;};template <class T>class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template <class T>LiQueue<T>::LiQueue( ){QNode <T> *s;s=new QNode<T>;s->next=NULL;front=rear=s;}template <class T>LiQueue<T>::~LiQueue( ){QNode <T> *p;while(front){p=front;front=front->next;delete p;}}template <class T>void LiQueue<T>::EnQueue(T x){QNode<T> *s;s=new QNode<T>;s->data=x; //申请一个数据域为x的结点ss->next=NULL;rear->next=s; //将结点s插入到队尾 rear=s;}template <class T>T LiQueue<T>::DeQueue(){QNode <T> *p; int x;if (rear==front) throw "下溢";p=front->next;x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p;return x;}template <class T>T LiQueue<T>::GetFront(){if (rear!=front)return front->next->data;}template <class T>T LiQueue<T>::GetRear(){if(rear!=front)return rear->data;}template <class T>bool LiQueue<T>::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout<<"请输入火车(货运列车）的车厢个数为："<<endl;cin>>n;cout<<"请输入转轨站的缓冲轨个数为："<<endl;cin>>k;}void Train::ChongPai(){int a[MS];LiQueue<int>*b;b=new LiQueue<int>[k+2];cout<<"请输入车厢入轨编号次序："<<endl;for(int i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<<endl;th=1;while(b[k].Empty()){int xx=b[k].DeQueue();if(xx==th){cout<<th<<"号车厢直接移至出轨"<<endl;b[k+1].EnQueue(th);th++;int j=0;while(b[j].Empty()){int x=b[j].GetFront();if(x==th){cout<<x<<"号车厢从"<<j+1<<"号缓冲轨出轨"<<endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{int j=0,u=5;while(b[j].Empty()&&j<k){if(xx<b[j].GetRear())j++;else{cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&j<k){cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);}if(j==k-1){cout<<"\n缓冲轨不够，重排车厢失败\n";return;}}}cout<<"车厢依次出轨的编号为：";while(b[k+1].Empty())cout<<b[k+1].DeQueue()<<" ";cout<<endl;}void main(){Train a;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。

#include <iostream>class Node{protected:int data;Node *next;Node(int n=0,Node*m=NULL):data(n),next(m){}//初始化节点对象friend class Queue;};class Queue//队列类{protected:Node *front,*rear;public:Queue();~Queue(){}//析构函数void EnQueue(int x);int DeQueue();int GetFront();int GetRear();bool IsEmpty();};Queue::Queue()//构造函数{Node *p;p=new Node;p->next=NULL;front=rear=p;}void Queue::EnQueue(int x)//进队{Node *p;p=new Node;p->data=x;p->next=NULL;rear->next=p;rear=p;}int Queue::DeQueue()//出队{Node*k;if(front==rear)return NULL;else{k=front->next;front->next=k->next;if(k->next==NULL)front=rear;int m=k->data;delete k;return m;}}int Queue::GetFront()//取队头元素{if(front==rear)return NULL;elsereturn front->next->data;}int Queue::GetRear()//取队尾元素{if(front==rear)return NULL;elsereturn rear->data;}bool Queue::IsEmpty()//判断队列为空{return front==rear ;}int Find_MinH(Queue *H, int k)//求入轨到空缓冲轨中最优队列编号{int n=0;int minH=k+1;for(int i=1;i<k+1;i++){if(!H[i].IsEmpty())n++;elseminH=(minH>i)?i:minH;}if(n<k)return minH;else return 0;int Find_MaxH(Queue *H,int k,Queue p)//求入轨到非空缓冲轨队列最优编号{int maxHRear=0,maxH=0;for(int i=1;i<k+1;i++){int x=0;if(p.GetFront()>H[i].GetRear()&&H[i].GetRear()>=maxHRear){ maxHRear=H[i].GetRear();maxH=i;}}return maxH;}void Resort(Queue p,Queue *H,int k)//火车车厢重排{int nowOut=1;while(nowOut<=9){int flag=0;//车厢出轨标记初始化为0if(p.GetFront()==nowOut){int m=p.DeQueue();std::cout<<m<<"\t";nowOut++;flag=1;}elsefor(int j=1;j<k+1;j++){if(!H[j].IsEmpty()){int c=H[j].GetFront();if(c==nowOut){int n=H[j].DeQueue();std::cout<<n<<"\t";nowOut++;flag=1;}}}}if(flag==0)//入轨和缓冲轨均无出队车厢{int maxH=Find_MaxH(H,k,p);//求由入轨到非空缓冲轨的最优车厢编号if(maxH!=0){int h=p.DeQueue();H[maxH].EnQueue(h);}else{int minH=Find_MinH(H,k);//求由入轨到空缓冲轨的最优车厢编号if(minH>0)H[minH].EnQueue(p.DeQueue());else //无空缓冲轨，重排算法结束std::cout<<"无空缓冲轨，重排结束！"<<"\n"; }}}}void main(){Queue p;const int N=9;int a[N]={3,6,9,2,4,7,1,8,5};std::cout<<"车厢重排后顺序："<<"\n";for(int i=0;i<N;i++)std::cout<<a[i]<<"\t";std::cout<<std::endl;for(int i=0;i<N;i++)p.EnQueue(a[i]);std::cout<<"车厢重排后顺序："<<"\n";int k=2;/*Queue B;Queue C;Queue D;Queue E;Queue H[]={B,C,D,E};*/Queue *H=new Queue[k+1];Resort(p,H,k);}。

车厢调度车厢调度(train.cpp/c/pas)Description有⼀个⽕车站，铁路如图所⽰，每辆⽕车从 A 驶⼊，再从 B ⽅向驶出，同时它的车厢可以重新组合。

假设从 A ⽅向驶来的⽕车有 n 节（n<=1000），分别按照顺序编号为 1，2，3，…，n。

假定在进⼊车站前，每节车厢之间都不是连着的，并且它们可以⾃⾏移动到 B处的铁轨上。

另外假定车站 C 可以停放任意多节车厢。

但是⼀旦进⼊车站 C，它就不能再回到 A ⽅向的铁轨上了，并且⼀旦当它进⼊ B ⽅向的铁轨，它就不能再回到车站 C。

负责车厢调度的 xxy 需要知道能否使它以a1,a2,…,an 的顺序从 B ⽅向驶出，请来判断能否得到指定的车厢顺序。

Input输⼊⽂件的第⼀⾏为⼀个整数 n，其中 n<=1000，表⽰有 n 节车厢，第⼆⾏为 n 个数字，表⽰指定的车厢顺序。

Output如果可以得到指定的车厢顺序，则输出⼀个字符串”YES”，否则输出”NO”（注意要⼤写，不包含引号）。

还有，xxy 说了这题 AC 有糖吃。

Exampletrain.in train.out5 YES5 4 3 2 1YESHint对于 50%的数据，1<=N<=20。

对于 100%的数据，1<=N<=1000。

解题思路：解题思路：先记录下所有车的出站顺序；模拟n辆车厢进站的情况；若进站车厢号⽐出站车号⼩，将此车厢进栈；若是出站车厢号，则将此车厢不进栈，不出栈；若以上都不符合，则证明不符合规则，输出no；代码实现 :1 #include<iostream>2using namespace std;3 #include<cstdio>4int f[1010],head=0,z[1010];5int main()6 {7 freopen("train.in","r",stdin);8 freopen("train.out","w",stdout); 9int n;10 cin>>n;11for(int i=1;i<=n;++i)12 scanf("%d",&f[i]);13for(int h=1,k=1;h<=n;++h) 14 {15while(k<=f[h]) //进栈16 {17 z[++head]=k;++k;18 }19if(z[head]==f[h]) //出站20 {21 --head;22 }23else24 {25 cout<<"NO";26return0;27 }28 }29 cout<<"YES";30 fclose(stdin);fclose(stdout); 31return0;32 }。

车厢重组c语言车厢重组是一道经典的排序算法问题，它是计算机科学中的重要考题之一。

在这道问题中，给定一个长度为 N 的整数数组，能通过一系列的操作来将其排序，每个操作都是将一个子数组中的所有元素翻转。

现在的问题是，最少需要几次操作才能将整个数组变成升序排列。

我们可以通过编写 C 语言程序来解决这道问题。

在下面的代码中，我们使用了一个名为 solve 的函数来进行求解。

该函数接受一个整数数组作为参数，返回一个整数值，即最小的操作次数。

代码如下：```c#include <stdio.h>int solve(int a[], int n) {int ans = 0;for (int i = 0; i < n; i++) {int s = i, t = n - 1;while (s < t && a[s] <= a[s + 1]) s++;while (s < t && a[t] >= a[t - 1]) t--;if (s == t) break;int k = s;while (k <= t && a[k] >= a[k - 1]) k++; ans++;if (s == 0 && t == n - 1) ans++;if (s > 0) ans++;if (t < n - 1) ans++;for (int i = s, j = t; i < j; i++, j--) {int tmp = a[i];a[i] = a[j];a[j] = tmp;}}return ans;}int main() {int a[] = {3, 2, 1, 4, 5};int n = sizeof(a) / sizeof(a[0]);printf("%d\n", solve(a, n));return 0;}```在上述代码中，我们首先定义了一个名为 solve 的函数来解决车厢重组问题。