搜索
数据结构课程设计车厢调度假设停在铁路调度口的车厢序列的编号依次1,2,3,…,n，设计一个程序，求出所有可能由此输出的长度为n的车厢序列。问题描述：为使车厢能够调度，常把站台设计成栈式结构。利用先进后出的性质，改变车厢的顺序。从而，问题可以转化为：1,2,3,…,n依次全部进栈且全部出栈，求所有的出栈序列。…问题分析：从具体问题入手：第一步：假如有1,2,3准备进栈，此时具体的过程如下第二步：对上述过程的进一步分析，一个数进栈以后，有两种处理方式：要么下一个元素进栈（如果有的话），要么立刻出栈；一个数出栈以后，要么继续出栈（如果栈不为空），要么下一个元素进栈（如果有的话）第三步：继续分析，由此得出一个结论，在操作过程中的任何状态下都有两种可能的操作：“入”和“出”。每个状态下处理问题的方法都是相同的，这说明问题本身具有天然的递归特性，可以考虑用递归算法实现。本程序的主要算法分析：调度函数的伪码算法如下：voidScheduling(intpos,intpath[],inti){if(posn){一个数进栈后,有两种处理方式：要么下一个数的进栈，要么立刻出栈}if(!IsEmpty()==true){一个数出栈后,有两种处理方式：要么继续出栈,要么下一个数的进栈}if(pos==n&&IsEmpty()){一种可能输出序列产生，输出}}具体的调度函数的程序代码：voidSeqStack::Scheduling(intpos,intpath[],inti){inttemp;if(posmaxSize){Push(pos+1);Scheduling(pos+1,path,i);Pop();}if(IsEmpty()==false){temp=Pop();path[i++]=temp;Scheduling(pos,path,i);Push(temp);}if(pos==maxSize&&IsEmpty()==true){count++;for(intj=0;ji;j++)coutpath[j]'';cout'\t';}}S(1,path,0)push(2)S(2,path,0)pop()t=path[0]=pop()S(1,path,1)push(t)S(2,path,0)停止t=path[0]=pop()S(1,path,1)push(t)S(1,path,1)停止t=path[0]=pop()S(1,path,2)push(t)S(1,path,1)push(2)S(2,path,1)pop()停止S(1,path,2)停止停止输出path[i]:2,1S(2,path,1)停止停止输出path[i]:1,2主函数调用Scheduling函数后后究竟怎么执行的呢现考虑只有两个车厢1,2？122112111初始状态：①：②：③：④：⑤：⑥：⑦：④：⑤：④：①：⑤：④：⑨：①：⑤：④：⑧：进出栈情况：谢谢！看收！3进3进无3出1出无2出无2出3进空3出无3进无3出无3出1出3进无1出2出无空空无3出无空无无空空无2进2进1出1进空2出输出3,2,1输出3,2,1输出3,2,1输出3,2,1输出3,2,1无空车厢调度的状态图