数据结构之火车厢重排

基于、XML与Flash架构的火车车厢重排问题虚拟实验开发摘要：当前，XML（Extensible Makeup Language）是跨平台数据结构的最佳选择，应用广泛。

它是一种通用的、跨平台的数据描述方法，相比于一般的记事本文件，完全采用了Unicode 编码和条理清晰的分层标签。

介绍了和Flash之间通过XML文件传递信息解决火车重排堆栈问题。

Flash使抽象的数据结构问题转化为具象的动画呈现给学生，有助于学生理解问题、编写程序。

关键词：XML；；Flash；虚拟实验；火车车厢重排0引言当前，XML是跨平台数据结构的最佳选择。

XML全称为可扩展标记语言（Extensible Makeup Language）。

它是一种通用的、跨平台的数据描述方法，也是未来存储信息的方式，其应用无处不在。

XML是可扩展的、与平台无关的语言，相比于一般记事本文件，它完全采用Unicode 编码和条理清晰的分层标签并且支持国际化。

Flash是专业的动画创作工具，可以开发有吸引力、表现力的用户界面和丰富的应用程序。

它开发的文件数据量小，可以以插件方式工作、“流”形式文件播放以及实时交互。

因此，Flash成功地渗入到网络动画、音乐电视、广告、教学、游戏等多个领域。

是基于通用语言的编译运行程序，其强大的适应性，几乎可以使它运行在Web 应用软件开发者全部的平台上。

通用语言的基本库、消息机制、数据接口的处理都能无缝整合到的Web应用中。

也是languageindependent（语言独立化）的，支持C#（C++和Java的结合体）、VB、Jscript、C++、F++等语言。

与Flash之间传值在中对数据进行处理后，生成XML树，然后通过XML 文件在Flash端接收XML文件，解析XML树后，根据传入的参数进行操作。

^[1]其通信原理如图1所示。

端生成XML文件的代码如下：System.Xml.XmlTextWriter xmlWriter = new XmlTextWriter （Server.MapPath（"./1234.xml"），System.Text.Encoding.UTF8）；//声明一个xmlWriter变量用于编写XML文件xmlWriter.Formatting = Formatting.Indented；//用于生成良好的显示格式，增强可读性xmlWriter.WriteStartDocument（）；xmlWriter.WriteStartElement（"数据"）；//生成一个结点xmlWriter.WriteStartElement（"单次"）；xmlWriter.WriteAttributeString（"车厢"，firstNum.ToString（））；//写入节点的属性xmlWriter.WriteAttributeString（"铁轨"，secondNum.ToString（））；xmlWriter.WriteAttributeString（"出入"，thirdNum.ToString（））；xmlWriter.WriteEndElement（）；xmlWriter.WriteEndDocument（）；//写文档结束xmlWriter.Close（）；//关闭textWriterFlash端接收XML文件的代码如下：var myXML：XML= new XML；var XML_URL：String = "1234.xml"；var myXMLURL：URLRequest = new URLRequest（XML_URL）；public var myLoader：URLLoader = new URLLoader （myXMLURL）；public function Motion（）{myLoader.addEventListener（"complete"，xmlLoaded）；}2火车重排堆栈问题动画实现笔者在学习数据结构时发现授课内容比较抽象，需要具体的图解动态地描述问题。

Project1火车车厢重排调度年级：2014级学院：电子与信息工程学院班级：智能科学与技术、自动化姓名：*** 14350046 姓名：*** 14350045 姓名：*** 14350069【题目要求】1.问题：一列火车要将n节车厢分别送往n个车站，车站按照n,n-1,…,1的编号次序经过车站。

假设车厢的编号就是其目的地车站的编号。

2.要求：给定一个任意的车厢排列次序。

重新排列车厢，使其按照从1到n的次序排列。

规定重排调度时车厢只能从入轨到缓冲铁轨，或者从缓冲铁轨到出轨。

【数据结构与算法】本程序将栈的空间设为25（可以通过全局常量maxstack直接修改），栈的最大数量设为100（可以直接修改）。

可以处理任意少于100个任意次序车厢的火车重排调度问题。

流程图如图1：图1 总流程图【测试数据、结果及分析】实验1：顺序输入车厢节数：10车厢顺序：1 2 3 4 5 6 7 8 9 10测试结果如图2。

图2 实验1测试结果测试序列重排成功，使用0个栈，返回值正常，实验程序运行良好。

实验2：倒序输入车厢节数：10车厢顺序：10 9 8 7 6 5 4 3 2 1测试结果如图3。

图3实验2测试结果测试序列重排成功，使用1个栈，实验程序运行良好。

实验3：乱序输入车厢节数：10车厢顺序：3 2 4 5 7 8 9 6 1 10测试结果如图4。

图4实验3测试结果测试序列重排成功，使用7个栈，实验程序运行良好。

实验4：乱序输入车厢节数：25车厢顺序：25 2 6 4 5 3 7 23 9 19 11 12 16 14 15 13 17 18 10 22 21 20 8 24 1测试结果如图5。

图5 实验4测试结果测试序列重排成功，使用13个栈，实验程序运行良好。

实验五：乱序输入车厢节数：50车厢顺序：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48测试结果如下（由于太长无法完全截图，只能粘贴）：请输入火车车厢的个数：50请输入火车车厢次序（中间有间隔）：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48将第46车厢移动到缓冲轨道1将第47车厢移动到缓冲轨道2将第50车厢移动到缓冲轨道3将第38车厢移动到缓冲轨道1将第32车厢移动到缓冲轨道1将第29车厢移动到缓冲轨道1将第21车厢移动到缓冲轨道1将第39车厢移动到缓冲轨道2将第1车厢从入站轨道移动到出站轨道将第37车厢移动到缓冲轨道2将第12车厢移动到缓冲轨道1将第22车厢移动到缓冲轨道2将第2车厢从入站轨道移动到出站轨道将第30车厢移动到缓冲轨道3将第11车厢移动到缓冲轨道1将第31车厢移动到缓冲轨道4将第41车厢移动到缓冲轨道5将第3车厢从入站轨道移动到出站轨道将第20车厢移动到缓冲轨道2将第36车厢移动到缓冲轨道5将第19车厢移动到缓冲轨道2将第23车厢移动到缓冲轨道3将第5车厢移动到缓冲轨道1将第14车厢移动到缓冲轨道2将第44车厢移动到缓冲轨道6将第4车厢从入站轨道移动到出站轨道将第45车厢移动到缓冲轨道7将第5车厢从缓冲轨道1移动到出站轨道将第13车厢移动到缓冲轨道2将第35车厢移动到缓冲轨道5将第8车厢移动到缓冲轨道1将第24车厢移动到缓冲轨道4将第40车厢移动到缓冲轨道6将第7车厢移动到缓冲轨道1将第28车厢移动到缓冲轨道5将第43车厢移动到缓冲轨道7将第16车厢移动到缓冲轨道3将第27车厢移动到缓冲轨道5将第34车厢移动到缓冲轨道6将第6车厢从入站轨道移动到出站轨道将第42车厢移动到缓冲轨道7将第7车厢从缓冲轨道1移动到出站轨道将第15车厢移动到缓冲轨道3将第8车厢从缓冲轨道1移动到出站轨道将第26车厢移动到缓冲轨道5将第10车厢移动到缓冲轨道1将第17车厢移动到缓冲轨道4将第9车厢从入站轨道移动到出站轨道将第33车厢移动到缓冲轨道6将第10车厢从缓冲轨道1移动到出站轨道将第18车厢移动到缓冲轨道5将第11车厢从缓冲轨道1移动到出站轨道将第25车厢移动到缓冲轨道6将第12车厢从缓冲轨道1移动到出站轨道将第49车厢移动到缓冲轨道8将第13车厢从缓冲轨道2移动到出站轨道将第48车厢移动到缓冲轨道8将第14车厢从缓冲轨道2移动到出站轨道将第15车厢从缓冲轨道3移动到出站轨道将第16车厢从缓冲轨道3移动到出站轨道将第17车厢从缓冲轨道4移动到出站轨道将第18车厢从缓冲轨道5移动到出站轨道将第19车厢从缓冲轨道2移动到出站轨道将第20车厢从缓冲轨道2移动到出站轨道将第21车厢从缓冲轨道1移动到出站轨道将第22车厢从缓冲轨道2移动到出站轨道将第23车厢从缓冲轨道3移动到出站轨道将第24车厢从缓冲轨道4移动到出站轨道将第25车厢从缓冲轨道6移动到出站轨道将第26车厢从缓冲轨道5移动到出站轨道将第27车厢从缓冲轨道5移动到出站轨道将第28车厢从缓冲轨道5移动到出站轨道将第29车厢从缓冲轨道1移动到出站轨道将第30车厢从缓冲轨道3移动到出站轨道将第31车厢从缓冲轨道4移动到出站轨道将第32车厢从缓冲轨道1移动到出站轨道将第33车厢从缓冲轨道6移动到出站轨道将第34车厢从缓冲轨道6移动到出站轨道将第35车厢从缓冲轨道5移动到出站轨道将第36车厢从缓冲轨道5移动到出站轨道将第37车厢从缓冲轨道2移动到出站轨道将第38车厢从缓冲轨道1移动到出站轨道将第39车厢从缓冲轨道2移动到出站轨道将第40车厢从缓冲轨道6移动到出站轨道将第41车厢从缓冲轨道5移动到出站轨道将第42车厢从缓冲轨道7移动到出站轨道将第43车厢从缓冲轨道7移动到出站轨道将第44车厢从缓冲轨道6移动到出站轨道将第45车厢从缓冲轨道7移动到出站轨道将第46车厢从缓冲轨道1移动到出站轨道将第47车厢从缓冲轨道2移动到出站轨道将第48车厢从缓冲轨道8移动到出站轨道将第49车厢从缓冲轨道8移动到出站轨道将第50车厢从缓冲轨道3移动到出站轨道共用8个缓冲轨道结果分析：本程序可对少于100个任意次序车厢的火车进行调度。

火车车厢重排问题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（注：可编辑下载，若有不当之处，请指正，谢谢!）。

⽕车车厢重排问题2014-11-04主要数据结构：栈题⽬：⼀列⽕车要将n节车厢分别送往n个车站按1~n的次序编号，⽕车按照n,n-1,…1的编号次序经过车站。

假设车厢的编号就是其⽬的地车站的编号。

要求：给定⼀个任意的车厢排列次序。

重新排列车厢，使其按照从1到n的次序排列。

规定重排时，只能从⼊轨到缓冲铁轨，或者从缓冲铁轨到出轨。

总的思路：⾸先：将所需要重排的车厢编号从左到右依次输⼊数组carrage中；然后：对carrage中的元素进⾏从左往右逐个遍历，如果符合下⼀个输出，则直接将其输出，并且遍历所有的缓冲轨道，查找是否有符合下⼀个输出的车厢，有的话便将其输出，否则将其压⼊缓冲轨道未经优化的代码：1 #include <iostream>2 #include <stack>3using namespace std;45 stack<int> stack_final;678void Output(int& minH, int& minS, stack<int> H[], int k, int n) {9// put the car from the strack to the output line, and change the minH and minS10int index; // the index of the car11//delete the minist car number from the minS12 stack_final.push(H[minS].top());13 H[minS].pop();14 cout << "Move car " << minH << "from holding track " << minS << " to output line" << endl;15//serch all the track's top, find the new minH and minS16 minH = n+2;17for (int i= 0; i < k; i++) {18if (!H[i].empty() && (index = H[i].top()) < minH) {19 minH = index;20 minS = i;21 }22 }23 }2425bool Input(int c, int& minH, int& minS, stack<int> H[], int k, int n) {26// put the new car c into the track27// if there is no available track, then return false, else return true28// find the best track for the car c29// initial30int BestTrack = 0; //the best track now31int BestTop = n+1; //the best track's top car32int index; //the index for the car33// search the k track34for (int i= 0; i < k; i++) {35if (!H[i].empty()) {36 index = H[i].top();37if (c < index && index < BestTop) {38//the top car's number is the smallest39 BestTop = index;40 BestTrack = i;41 }42 } else { // the track is empty43if (!BestTrack) {44 BestTrack = i;45 }46 }47 }48if (!BestTrack) {49return false; //there is available track to use50 }51 H[BestTrack].push(c);52 cout << "Move car " << c << "from input to holding track " << BestTrack << endl;53//if it is essencial, then change the minH and minS54if (c < minH) {55 minH = c;56 minS = BestTrack;57 }58return true;59 }6061bool Railroad(int input[], int n, int k) {62//k63// if it resort succed, then return true, else return false64// create the stack according to the k65 stack<int> *H;66 H = new stack<int> [k];67int NowOut = 1; // the next number of car to putout68int minH = n+1; //the minist number car in the k69int minS; //the minist number's strack70// resort the car71for (int i = n-1; i >= 0; i--) {72int number = input[i];73if (number == NowOut) {74 cout << "Move car " << number << " from the input line to the output line\n";75 stack_final.push(number);76 NowOut++;77while (minH == NowOut) {78 Output (minH, minS, H, k, n);79 NowOut++;80 }81 } else {82int end = 0;83for (int j = i; j > 0; j--) {84if (input[j-1] < input[j]) {85 end = j;86break;87 }88 }89for (int j = end; j <= i; j++) {90if (!Input (input[j], minH, minS, H, k, n)) {91return false;92 }93 }94if (end) {95 i = end;96 }97 }98 }99return true;100 }101102int main() {103int n, *input;104 cin >> n;105 input = new int[n];106for (int i = 0; i < n; i++) {107 cin >> input[i];108 }109if (Railroad(input, n, n-1)) {110 cout << "resort succed!\n";111while (!stack_final.empty()) {112 cout << stack_final.top() << "";113 stack_final.pop();114 }115 } else {116 cout << "failed\n";117 }118 }View Code经过优化之后的代码：增加的条件：车厢可以从排在后⾯的缓冲轨道移到前⾯的缓冲轨道。

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

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

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

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

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

②基本要求●设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；●设计并实现车厢重排算法；●分析算法的时间性能。

③思考●如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？二、数据结构设计迷宫问题和火车重排问题可以通过栈与队列实现的。

迷宫的进出和车厢的出入轨和缓冲轨主要是对栈与队列的判断和操作。

int empty( STLink top[],int n) /*判断是否为空*/{return (top[n]==NULL);}int push(STLink top[],int A,int m) /*入栈*/{STLink p;if(!(p=(STLink)malloc(LEN)))return 0;else{p->data=A;p->link=top[m];top[m]=p;return 1;}}int pop(STLink top[],int m) /*出栈*/{int A;STLink p;p=top[m];A=p->data;top[m]=top[m]->link;free(p);return A;}struct Node{ /定义队列int data;Node* next;};三、算法设计1.迷宫问题：进入格子后，需要判断此时格子位置周围障碍物的位置，对其进行压栈，判断，然后看是否满足条件，满足就进栈，不满足就弹出，然后输出不能通过建立迷宫：typedef struct LStack{Element elem;struct LStack *next;}*PLStack;int InitStack(PLStack &S){S=NULL;return 1;}int StackEmpty(PLStack S){if(S==NULL)return 1;elsereturn 0;}int Push(PLStack &S, Element e){PLStack p;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return 1;}（2）.输出路径2.火车车厢排序六、实验收获与思考通过本次实验，进一步增强了对栈和队列的理解，明白的栈的先进后出和队列先进先出的方式，对压栈和出入栈与队列有了深刻认识。

火车车厢重排问题栈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. ```。

数据结构车厢调度第一篇：数据结构车厢调度#include #include#define STACK_INIT_SIZE 20 #define STACK_SIZEtypedef struct { int *base;int *top;int stacksize;} SqStack;bool InitStack(SqStack &S){ // 初始化栈S.base =(int *)malloc(STACK_INIT_SIZE*sizeof(SqStack));if(!S.base) exit(0);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return true;} // InitStackbool GetT op(SqStack S, int &e){ // if(S.top == S.base)return false;e = *(S.topS.base >= S.stacksize){S.base =(int *)realloc(S.base,(S.stacksize + STACK_SIZE)*sizeof(SqStack));if(!S.base)exit(0);S.top = S.base + S.stacksize;S.stacksize += STACK_SIZE;} *S.top++ = e;return true;} // Pushbool Pop(SqStack &S, int &e){ if(S.top == S.base)return false;e = *--S.top;return true;}/////////////////////////////////////////////////////////////////// ////////////////bool Judement(int *Array, int n){ int Count = 0;for(int i = 1;i <= 2*n;i++)if(Array[i] == 1)Count++;if(Count == n && Array[2*n] == 0)一个是出栈return true;elsereturn false;}void operation(SqStack S, int n){ // n代表获得数量，分别标记为1,2,3....n int *Array;int nCount = 0, e;Array =(int *)malloc((2 * n + 1)* sizeof(int));if(!Array)exit(0);// 将其初始化为1234..n的形式for(int i = 1;i <= 2*n;i++)if(i%2 == 1)Array[i] = 1;elseArray[i] = 0;while(1){if(Judement(Array, n)){nCount = 0;for(int i = 1;i <= 2*n;i++){if(Array[i] == 1)Push(S, ++nCount);// 必须保证最后//从1开始// 代表入栈// 代表出栈else{Pop(S, e);printf(“%d ”, e);}}printf(“n”);}Array[2*n] += 1;// 最后一个自增1，等于2时本为为0前一位加1for(int i = 2*n;i >= 1;i--){if(Array[i] == 2){Array[i-1] += 1;Array[i] = 0;}}nCount = 0;for(int i = 1;i <= n;i++){if(Array[i] == 1)nCount++;}if(nCount == n && Array[2*n] == 1)break;// 退出循环的条件为前n个为1同时最后一位也为1 } }void main(){ // 这个是在左边有1,2,3...n节车厢的情况，得出在右边所有的情况SqStack S;InitStack(S);int n;scanf_s(“%d”, &n);if(n <= 1){printf(“输入数字小于1”);return;} operation(S, n);第二篇：数据结构任务调度实验报告实验报告实验名称：表达式求值任务调度实验类型：综合性实验班级：学号：姓名：实验日期：2014.5.28表达式求值 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#语言版)

解决堆栈的编程问题
数据结构(C#语言版)
解决堆栈的编程问题
小结
在本章中，你已经学到：
堆栈(Stack)是一种特殊旳线性表,是一种只允许在表旳一端进行 插入或删除操作旳线性表。栈旳主要特点是“后进先出”； 堆栈旳插入操作也称为进栈或入栈，堆栈旳删除操作称为出栈 或退栈； 允许插入和删除旳一端称栈顶(Top)，不允许插入和删除旳一端 称栈底(Bottom)； 堆栈旳基本操作; 顺序栈用一片连续旳存储空间来存储栈中旳数据元素； 链栈是用链式存储构造存储旳栈。
使用堆栈处理编程问题
数据构造(C#语言版)
目的
在本章中,你将学到:
辨认堆栈旳特征 实施堆栈 利用堆栈来处理编程问题
数据结构(C#语言版)
解决堆栈的编程问题
学习情境——用堆栈处理火车车厢重排问题旳编 程
[问题描述]
一列货运列车共有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 给出了按所要求旳顺序重新排列后旳成果。

① 从左向后扫描数组，直到遇到第一个偶数 ② 从右向左扫描数组，直到遇到第一个奇数 ③ 如果i<j 交换a[i]、 a[j]的数据，，同时修改i，j的 值，继续进行2的工作
int n,*a; cin>>n; a=new int [n]; int i=0,j=n-1; for (i=0;i<n;i++) cin>>a[i]; i=0; while (i<j){
template <class T> void CycleList<T>::append(Node<T> *p) { p->next=rear->next; rear->next=p; rear=p; return; }
数据结构算法
数据结构
• 数据结构是一门研究非数值计算的程序设计问题中的操作 对象（结点）以及它们之间关系和操作等的学科。 • 1968 年克努思教授开创了数据结构的最初体系，他所著
的《计算机程序设计艺术》第一卷《基本算法》是第一本
较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 70 年代初，数据结构作为一门独立的课程开始进入大学
课堂。 • 下面介绍数据结构中常见的一些基本算法
• 关于算法 • 线性表上的常见算法 • 基于队列的常见算法 • 基于栈的常见算法
算法
• 多项式求的两种方法
– A(x)=anxn+an-1xn-1+…+a0
– A(x)=((anx+an-1)X+an-2)…+a0
template<typename T> T Poly1(T a[],int n,T x) { int i,j; T result=0; T xn,xx; for( i=0;i<n;i++) – A(x)=anxn+an-1xn-1+…+a0 { xn=1; xx=x; for(j=0;j<i;j++) xn=xn*xx; result=a[i]*xn+result; } return result; }

目录1．题目： (2)1-1.队列的应用——火车厢重排问题 (2)1-2.简单指导 (2)2.设计目的及内容 (3)2-1.目的 (3)2-2.内容 (3)设计内容 (3)3.概要设计 (4)3-1.函数调用的关系图 (4)3-2.流程图 (4)3-2-1. 总体程序设计流程图 (4)3-2-2 Output函数的流程图. (5)3-2-3. Hold函数的流程图 (6)4. 算法描述 (8)4-1. 模块一：LinkQueue() 构造函数 (8)初始化一个空的链队列 (8)4-2. 模块二：析构函数 (8)释放链队列中的各结点的存储空间 (8)4-3. 模块三：EnQueue函数 (9)将队头元素x入队 (9)4-4. 模块四：DeQueue函数 (9)将队头元素出队 (9)4-5.模块五：GetQueue函数 (9)取链队列的队头元素 (9)4-6. 模块六：Empty函数 (10)判断链队列是否为空 (10)4-7. 模块七：Outputput 函数 (10)该函数调用6个函数模板来实现火车厢重排问题，预设K个缓冲轨道，通过运用函数模板来比较各个缓冲轨道的队头元素，确定队列的出队、入队元素，最后通过输入和输出函数来实现火车厢由小到大的顺序出轨 (10)5.源程序 (11)6. 运行结果及性能分析 (15)6-1. 运行结果及性能分析 (15)6-1-1.开始后的界面 (15)6-1-2. 输入火车总数i=5和缓冲轨数j=3后的界面 (16)6-1-3.随机输入1.2.3.4.5的进入顺序后开始进入重排界面 (16)6-2. 性能分析 (16)7.心得体会 (17)1．题目：1-1.队列的应用——火车厢重排问题假设一列货运列车共有n节编号分别为1~n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1~n的次序排列，以便各车厢能够停靠在与其编号一致的站点。

{
a[m].EnterQueue(arr[i]);//入队
i++;//i加一实现了对下一个车厢的操作
p=1;//重新置为1
break; }
}
}
if(p==0) //表示上一节车厢没有被处理，程序结束
{
{ Node<T> *p=front->next;
while(p)
{
if(p==NULL)
break;
else
{
cout<<p->data<<' ';
p=p->next;
}
};
}
void main()
{ int n,k,t;
cin>>k;
if(k<=0) throw"必须存在缓冲轨道!";
cout<<"请依次输入火车车车厢号"<<endl;
for(int i=0;i<n;i++)
{
cin>>main[i];
}
cout<<endl;
LinkQueue<int> *huan;
huan=new LinkQueue<int>[k];
s->next=NULL;
rear->next=s;
rear=s;
}
template<class T>
T LinkQueue<T>::DeQueue()
{
if(rear==front) throw"发生下溢";

目录一、功能描述 (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)算法分析：此功能模块简单明了没有深度算法，在此不做分析。

数据结构实验报告实验名称：实验二——题目5学生姓名：班级：班内序号：学号：日期：2011年11月7日1．实验要求利用队列结构实现车厢重排问题。

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

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

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

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

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

2. 程序分析将每个轨道视为一个队列，每一个车厢视为一个结构体的结点，结点存储车厢编号以及下一节车厢的地址。

用尾插法建立队列，并根据队列队尾入队，队头出队的特点实现结点的出队以及入队。

由于车厢在重排过程中将会频繁进行入队以及出队的操作，如果采用顺序存储结构，则在结点出入队时是操作将会十分不方便，还会占用大量多余的空间和时间，故选用链式存储结构，可以直接调动结点，十分简洁。

重排过程比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面。

在把车厢c 移至缓冲轨是，车厢c应该移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择对位车厢编号最大的缓冲轨，否则选择一个空的缓冲轨。

这样，出轨的时候才可以按照从小到大的顺序重新编排。

2.1 存储结构2.2 关键算法分析1. 移动车厢算法（车厢要从a队列移至b队列）·自然语言描述（1）判断a队列是否为空，为空则输出“队列下溢”，提示出错。

（2） 否则，设置工作指针p 指向a 队列的队头元素，（3） 将b 的尾指针指向next 域指向p ；（4） b 队列的尾指针后移，指向p 指向的结点；（5） a 头结点指向p 后一个结点（6） p 的next 域置为空，完成一次车厢的移动（7） a 队列车厢数减1，b 队列车厢数加1·伪代码描述两个队列，车厢要从a 队列移至b 队列；（1）bus* p=a.front->next;（2）if(!p) cout<<"Underflow"<<endl;（3）b.rear->next=p;（4）b.rear=b.rear->next;（5）a.front->next=p->next;（6）p->next=NULL;（7）if(!(a.front->next))a.rear=a.front;（8）a.Number--;b.Number++;图示ab算法时间复杂度O(1)，空间复杂度S(1)。

int i=0;
bool flag=1;//标记
while(i<n&&flag){ //当入轨中有车厢时
flag=0;
for(int m=0;m<k;m++){ //判断缓冲轨的队尾元素与入轨的元素
if(a[m].GetRear()<arr[i]){
a[m].EnQueue(arr[i]);
}
friend void TrainPermute(int arr[],LinkQueue<T> a[],int n,int k);
};
template<typename T>
LinkQueue<T>::LinkQueue(){
Node<T> *s=new Node<T>;
s->next=NULL;
if(rear==front)
throw"下溢";
Node<T> *p=front->next;
int x=p->data;
front->next=p->next;
if(p->next==NULL)
rear=front;
delete p;
return x;
}
}
else
{
for(int m=0;m<k;m++){
cout<<"第"<<(m+1)<<"个缓冲轨的列车编号\t";
a[m].Trans();
cout<<endl;

cout<<endl; cout<<"请问是手动输入车厢号还是随机产生？ \n1 手动 2 随机 " <<endl;
cin>>h; switch(h) {case 1: cout<<endl; for(a=0;a<n;a++) cin>>array[a]; break; case 2: srand((unsigned)time(NULL)); int count=0; int *m; m=new int[n]; while(count!=n) { t=rand()%n; if(m[t]!=1) { array[t]=count+1; m[t]=1; count++; } } break;
}
cout<<endl; cout<<"火车车厢入轨顺序为:"<<endl; for(int i=0;i<n;i++) cout<<array[i]<<" "; cout<<endl; LinkQueue *buffer; buffer=new LinkQueue[k]; cout<<endl; TrainPermute(array,buffer,n,k); cout<<endl;} //缓冲轨
bool Empty() {if(front==NULL) return 1; else return 0;}
//判断队空
friend void TrainPermute(int arr[],LinkQueue a[],int n,int k); private: Node *front,*rear; };

⽕车车厢重排问题问题描写叙述：⼀列货运⽕车从出发站出发时⽕车上⼀共同拥有n节车厢，编号各⾃是1到n。

运货的各节车厢是在⼊轨上时是随机的顺序，⽕车头在出轨处，如今要将各节车厢按编号从⼤到⼩挂到车头上。

当中在⼊轨与出轨之间有k条缓冲铁轨，将通过缓冲铁轨完毕本次的⽕车车厢的重排。

详细规则：⼀、车厢从⼊轨的前部（即右端）仅仅能够移动到⼀个缓冲铁轨的顶端或出轨的右端。

⼆、缓冲铁轨的顶端的车厢仅仅能够移动到出轨的最左端三、车厢不能从⼀个缓冲铁轨移动到还有⼀个缓冲铁轨或者再移动到⼊轨四、车厢移动到出轨的最左端（即⽕车头端）后不能再移动解决步骤：⼀、从⼊轨端開始移除最右边的车厢假设该车厢正好能够挂在出轨端则直接移到⼊轨端。

然后再在缓冲铁轨中查找是否有接到出轨上的车厢如有则移出如⽆则開始步骤四。

否则先在每条缓冲铁轨中查找。

⼆、假设能找到⼀条缓冲铁轨顶端的车厢编号正好⽐它⼤并且和它最接近则移动到该条缓冲铁轨上三、假设每⼀条有车厢的缓冲铁轨的顶端车厢编号都⽐它⼩，则再查找有没有空的缓冲铁轨假设有则移动到缓冲铁轨上，否则返回false。

四、继续開始从⼊轨端移除最右端的车厢⽽且開始反复步骤⼀。

应⽤的数据结构：因为对于每个缓冲铁轨来说都是LIFO后进先出的特点所以能够考虑採⽤栈的数据结构。

详细实现代码及结果例如以下：#include<iostream>#include<vector>#include<stack>#include<deque>#include<iterator>#include<algorithm>using namespace std;//辅函数：更新缓冲铁轨上的min_buf、min_travoid updata(vector<stack<int>> & tracks_buf,int & min_buf,int & min_tra){for (int i = 0;i<tracks_buf.size();i++){if(!tracks_buf[i].empty() && min_buf>tracks_buf[i].top()){min_buf = tracks_buf[i].top();min_tra = i;}}}//辅函数：将车厢移到缓冲铁轨上bool trans(int n,int d,vector<stack<int>> & tracks_buf,int & min_buf,int & min_tra){//先查找最优缓冲铁轨int min_gap = n+1;//d与个缓冲铁轨顶端上⼤于的车厢与d之间的最⼩间隔int prefer_track = -1;//最优铁轨for (int i = 0;i<tracks_buf.size();i++){if (!tracks_buf[i].empty() && tracks_buf[i].top()>d && (tracks_buf[i].top()-d)<min_gap){min_gap = tracks_buf[i].top()-d;prefer_track = i;}}if(-1!=prefer_track)//找到最优缓冲铁轨{tracks_buf[prefer_track].push(d);updata(tracks_buf,min_buf,min_tra);return true;}else{//再查找是否存在空铁轨for (int i = 0;i<tracks_buf.size();i++){if(tracks_buf[i].empty()){tracks_buf[i].push(d);updata(tracks_buf,min_buf,min_tra);return true;}}//否则返回false;return false;}}/* ⽕车车厢重排问题* datas：⽕车车厢在⼊轨上时的序列* n : ⽕车车厢的总节数* k ：缓冲铁轨的条数*///主要函数bool fun(vector<int> &datas,deque<int> & results,int n,int k){int min_buf = n+1;//缓冲铁轨上最⼩的车厢号int min_tra = 0;//最⼩的车厢所在的缓冲铁轨编号vector<stack<int>> tracks_buf(k);//缓冲铁轨数组int need = 1;//出轨处须要挂上的车厢号while (!datas.empty()){int d = datas.back();datas.pop_back();if (d==need)//符合要求直接移到出轨{results.push_front(need);need++;//再到缓冲铁轨中查找是否有下⼀个符合的车厢while(min_buf == need)//找到{results.push_front(need);need++;//移除缓冲铁轨tracks_buf[min_tra].pop();//更新min_buf、min_tramin_buf = n+2;min_tra = 0;updata(tracks_buf,min_buf,min_tra);}}else//不符合要求移到缓冲铁轨上{if(!trans(n,d,tracks_buf,min_buf,min_tra)){return false;}}}return true;}int main(){int array[] = {5,8,1,7,4,2,9,6,3};deque<int> results;vector<int> vec(array,array+sizeof(array)/sizeof(array[0]));int n = vec.size();int k = 3;//3条缓冲铁轨if (fun(vec,results,n,k)){cout<<k<<"条缓冲铁轨能够将依照";copy(vec.begin(),vec.end(),ostream_iterator<int>(cout));cout<<"此序列的"<<n<<"节车厢⼜⼀次排好挂到⽕车头上。