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个任意次序车厢的火车进行调度。
进行多次乱序重排，实验程序均成功运行，且结果全部与人工计算相符合，实验程序满足实验要求。
【分工、贡献%、自我评分】王金顶：算法设计，主程序，调试，实验报告 34% 100分王帆：算法设计，栈程序，测试，实验报告 33% 100分张宇航：算法设计，流程图设计，实验报告 33% 100分【项目总结】本次题目较为简单，考察了我们对栈的学习与理解情况，同时也让我们复习了类的相关知识。
大家都为终于能够解决实际问题而感到开心。
在算法设计中也遇到了很多问题，如我们发现标准库中的栈占用内存过大，因此导致程序在处理车厢数很大时经常崩溃。
因此我们自己写了一个简单的栈，节省了大量内存，因此能够处理更加复杂的问题。
我们也增加了好几处错误处理代码，增加了程序的容错性。
如栈满、栈空现象等。
但是该程序在处理不连续序列时会出现问题，这也是我们一直在改进的地方，但是输出一直不稳定，有时正确有时错误，因此在程序清单中删除了这一部分。
总体而言，本次的实验让我们对自己有了更大的信心。
【程序清单】1.stack.h/*文件名：stack.h作用：栈的类定义*/#ifndef STACK_H#define STACK_Hconst int maxstack=25;class Stack{public:Stack();bool empty() const;bool full() const;int top() const;void push(int item);void pop();private:int count;int entry[maxstack];};#endif2.stack.cpp/*文件名：stack.cpp作用：栈的类成员函数的实现*/ #include<iostream>#include"stack.h"using namespace std;void Stack::push(int item){if (count<maxstack){entry[count++]=item;}}void Stack::pop(){if (count>0){--count;}}int Stack::top() const{if (count>0){return entry[count-1];}elsereturn 0;}bool Stack::empty() const{if(count>0) return false;return true;}bool Stack::full() const{if(count==maxstack) return true;return false;}Stack::Stack(){count=0;3.train.cpp/*文件名：train.cpp作用：主程序*/#include<iostream>#include"stack.h"using namespace std;int main(){int n, now_out=1;int stack_count=0;cout<<"请输入火车车厢的个数：" <<endl; //输入数据并储存cin>>n;int array[n];cout<<"请输入火车车厢次序（中间有间隔）："<<endl;for (int i=0; i<n; i++){cin>>array[i];}//输入部分Stack stack_array[100];for (int i=0; i<n; i++){if (array[i]==now_out) //判断当前车厢数是否恰好满足输出条件{cout<<"将第"<<now_out<<"车厢从入站轨道移动到出站轨道"<<endl; //如果满足直接输出now_out++;continue;}else //不满足则将数压入合适的栈{for (int j=0; j<stack_count+1; j++){if (stack_array[j].empty()){cout<<"将第"<<array[i]<<"车厢移动到缓冲轨道"<<j+1<<endl;stack_array[j].push(array[i]);if (j==stack_count){stack_count++;}break;}else if (stack_array[j].full()) //栈满时另找新栈{continue;}else if(array[i]<stack_array[j].top()){cout<<"将第"<<array[i]<<"车厢移动到缓冲轨道"<<j+1<<endl;stack_array[j].push(array[i]);break;}else;}}for (int s=0; s<stack_count; s++)//遍历各个栈顶是否有满足输出条件的数{if (stack_array[s].top()==now_out){cout<<"将第"<<now_out<<"车厢从缓冲轨道"<<s+1<<"移动到出站轨道"<<endl;stack_array[s].pop();now_out++;break;}}}for (int m=now_out; now_out<=n; m++){for (int s=0; s<stack_count; s++)//遍历各个栈顶是否有满足输出条件的数{if (stack_array[s].top()==now_out){cout<<"将第"<<now_out<<"车厢从缓冲轨道"<<s+1<<"移动到出站轨道"<<endl;stack_array[s].pop();now_out++;break;}}}cout<<"共用"<<stack_count<<"个缓冲轨道"<<endl;return 0;}。