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

数据结构.车厢调度[课件]数据结构全文共10页，当前为第1页。假设停在铁路调度口的车厢序列的编号依次1,2,3,…,n，设计一个程序，求出所有可能由此输出的长度为n的车厢序列。

问题描述：[课件]数据结构全文共10页，当前为第2页。为使车厢能够调度，常把站台设计成栈式结构。利用先进后出的性质，改变车厢的顺序。

从而，问题可以转化为：1,2,3,…,n依次全部进栈且全部出栈，求所有的出栈序列。…[课件]数据结构全文共10页，当前为第3页。问题分析：从具体问题入手：第一步：假如有1,2,3准备进栈，此时具体的过程如下第二步：对上述过程的进一步分析，一个数进栈以后，有两种处理方式：要么下一个元素进栈（如果有的话），要么立刻出栈；一个数出栈以后，要么继续出栈（如果栈不为空），要么下一个元素进栈（如果有的话）第三步：继续分析，由此得出一个结论，在操作过程中的任何状态下都有两种可能的操作：“入”和“出”。每个状态下处理问题的方法都是相同的，这说明问题本身具有天然的递归特性，可以考虑用递归算法实现。[课件]数据结构全文共10页，当前为第4页。本程序的主要算法分析：调度函数的伪码算法如下：voidScheduling(intpos,intpath[],inti){if(pos<n){一个数进栈后,有两种处理方式：要么下一个数的进栈，要么立刻出栈}if(!IsEmpty()==true){一个数出栈后,有两种处理方式：要么继续出栈,要么下一个数的进栈}if(pos==n&&IsEmpty()){一种可能输出序列产生，输出}}[课件]数据结构全文共10页，当前为第5页。具体的调度函数的程序代码：voidSeqStack::Scheduling(intpos,intpath[],inti){ inttemp; if(pos<maxSize){ 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;j<i;j++) cout<<path[j]<<''; cout<<'\t'; }}[课件]数据结构全文共10页，当前为第6页。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？[课件]数据结构全文共10页，当前为第7页。122112111初始状态：①：②：③：④：⑤：⑥：⑦：④：⑤：④：①：⑤：④：⑨：①：⑤：④：⑧：进出栈情况：[课件]数据结构全文共10页，当前为第8页。谢谢！看收！[课件]数据结构全文共10页，当前为第9页。3进3进无3出1出无2出无2出3进空3出无3进无3出无3出1出3进无1出2出无空空无3出无空无无空空无2进2进