数据结构.车厢调度ppt课件.ppt

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