火车调度问题PROJECT.

1、Project1火车车厢重排调度年级：2014级 学院：电子与信息工程学院 班级：智能科学与技术、自动化姓名：王金顶 14350046 姓名：王帆 14350045 姓名：张宇航 14350069 【题目要求】1.问题：一列火车要将n节车厢分别送往n个车站，车站按照n,n-1,1的编号次序经过车站。假设车厢的编号就是其目的地车站的编号。2.要求：给定一个任意的车厢排列次序。重新排列车厢，使其按照从1到n的次序排列。规定重排调度时车厢只能从入轨到缓冲铁轨，或者从缓冲铁轨到出轨。【数据结构与算法】本程序将栈的空间设为25（可以通过全局常量maxstack直接修改），栈的最大数量设为100（可以直接

2、修改）。可以处理任意少于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个栈，实

3、验程序运行良好。实验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测试结果如

4、下（由于太长无法完全截图，只能粘贴）：请输入火车车厢的个数：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

5、将第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车

6、厢移动到缓冲轨道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车厢移动到缓冲轨道

7、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移动到

8、出站轨道将第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车厢从缓冲轨道

9、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个任意次序车厢的火车进行调度。进行多次乱序重排，实验程序均成功运行，且结果全部与人

10、工计算相符合，实验程序满足实验要求。【分工、贡献%、自我评分】王金顶：算法设计，主程序，调试，实验报告 34% 100分王帆：算法设计，栈程序，测试，实验报告 33% 100分张宇航：算法设计，流程图设计，实验报告 33% 100分【项目总结】本次题目较为简单，考察了我们对栈的学习与理解情况，同时也让我们复习了类的相关知识。大家都为终于能够解决实际问题而感到开心。在算法设计中也遇到了很多问题，如我们发现标准库中的栈占用内存过大，因此导致程序在处理车厢数很大时经常崩溃。因此我们自己写了一个简单的栈，节省了大量内存，因此能够处理更加复杂的问题。我们也增加了好几处错误处理代码，增加了程序的容错性。如

11、栈满、栈空现象等。但是该程序在处理不连续序列时会出现问题，这也是我们一直在改进的地方，但是输出一直不稳定，有时正确有时错误，因此在程序清单中删除了这一部分。总体而言，本次的实验让我们对自己有了更大的信心。【程序清单】1.stack.h/*文件名：stack.h作用：栈的类定义*/#ifndef STACK_H#define STACK_Hconst int maxstack=25;class Stackpublic:Stack();bool empty() const;bool full() const;int top() const;void push(int item);void pop(

12、);private:int count;int entrymaxstack;#endif2.stack.cpp/*文件名：stack.cpp作用：栈的类成员函数的实现 */#include<iostream>#include"stack.h"using namespace std;void Stack:push(int item)if (count<maxstack)entrycount+=item;void Stack:pop()if (count>0)-count;int Stack:top() constif (count>0)retur

13、n entrycount-1;else return 0;bool Stack:empty() constif(count>0) return false;return true;bool Stack:full() constif(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

14、n, now_out=1;int stack_count=0;cout<<"请输入火车车厢的个数：" <<endl; /输入数据并储存cin>>n;int arrayn;cout<<"请输入火车车厢次序（中间有间隔）："<<endl;for (int i=0; i<n; i+)cin>>arrayi;/输入部分Stack stack_array100;for (int i=0; i<n; i+)if (arrayi=now_out) /判断当前车厢数是否恰好满足输出条件c

15、out<<"将第"<<now_out<<"车厢从入站轨道移动到出站轨道"<<endl; /如果满足直接输出now_out+;continue;else /不满足则将数压入合适的栈 for (int j=0; j<stack_count+1; j+)if (stack_arrayj.empty() cout<<"将第"<<arrayi<<"车厢移动到缓冲轨道"<<j+1<<endl; stack_arra

16、yj.push(arrayi); if (j=stack_count) stack_count+; break; else if (stack_arrayj.full() /栈满时另找新栈 continue; else if(arrayi<stack_arrayj.top() cout<<"将第"<<arrayi<<"车厢移动到缓冲轨道"<<j+1<<endl; stack_arrayj.push(arrayi); break; else ;for (int s=0; s<stack

17、_count; s+)/遍历各个栈顶是否有满足输出条件的数 if (stack_arrays.top()=now_out)cout<<"将第"<<now_out<<"车厢从缓冲轨道"<<s+1<<"移动到出站轨道"<<endl;stack_arrays.pop();now_out+;break;for (int m=now_out; now_out<=n; m+)for (int s=0; s<stack_count; s+)/遍历各个栈顶是否有满足输出条件的数 if (stack_arr