文档介绍：数据结构课程设计 车厢调度
假设停在铁路调度口的车厢序列的编号依次1,2,3,…,n,设计一个程序,求出所有可能由此输出的长度为n的车厢序列。
问题描述:
为使车厢能够调度,常把站台设计成栈式结构。利用先进后出的性质,改变车厢的顺序。
从而,问题可以转化为: 1,2,3,…,n依次全部进栈且全部出栈,求所有的出栈序列。
…
问题分析:
从具体问题入手:
第一步:假如有1,2,3准备进栈,此时具体的过程如下
第二步:对上述过程的进一步分析,一个数进栈以后,有两种处理方式:要么下一个元素进栈(如果有的话),要么立刻出栈;一个数出栈以后,要么继续出栈(如果栈不为空),要么下一个元素进栈(如果有的话)
第三步:继续分析,由此得出一个结论,在操作过程中的任何状态下都有两种可能的操作:“入”和“出”。每个状态下处理问题的方法都是相同的,这说明问题本身具有天然的递归特性,可以考虑用递归算法实现。
本程序的主要算法分析:
调度函数的伪码算法如下:
void Scheduling(int pos, int path[],int i)
{
if(pos<n) {
一个数进栈后,有两种处理方式:要么下一个数的进栈,要么立刻出栈}
if(!IsEmpty()==true){
一个数出栈后,有两种处理方式:要么继续出栈,要么下一个数的进栈}
if(pos==n&&IsEmpty()){
一种可能输出序列产生,输出}
}
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,1
S(2,path,1)停止
停止
输出 path[i