车厢调度问题.rar

车厢调度问题


任务：
假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n 的车厢系列。
要求：
1设计一个程序，求出由一个编号依次为1，2，、、、，n的车厢序列可能产生的所有出栈系列。
2利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。
3对于每个输出序列演示出所有操作序列的变化过程 。

1、目的
在TC环境下，通过输入车厢系列的编号n，求出所有可能由此输出的长度为n的车厢系列，用入栈出栈的方法，实现车厢调度，并演示每一种出栈序列的过程。
2、结构设计
⑴为了使车厢能够调度，即改变原来的顺序，需要定义一个栈，即利用栈先进后出的性质，改变车厢的顺序；因为输出的序列有很多种，而且序列的产生是用递归产生的，因此需要定义一个结构体，它可以保存所有的输出序列，供演示时调用。
⑵初始化数据：主要是输入车厢的长度，对输出序列的结构体的长度和它的内嵌结构体的长度初始化为0，并将栈初始化为空。
⑶显示所有的序列：因为序列有很多种情况，为了得到它们，采用递归和回溯的算法，即利用编号出栈递归和编号入栈递归，当满足条件的序列就输出，在输出的同时将题目复制给输出序列的结构体，供演示时调用。
⑷演示一种序列：演示时，采用的是向逆推的方法，因为我们已经知道了一种输出序列的结果和它的最出状态，就可以利用栈将中间过程显示出来；即当序列中当前的数据大于入口处的数据时, 入口处的数据要一直压栈,直到大于出口处的数据 并显示每一步结果 ；当序列中当前的数据小于入口处的数据时,弹出栈顶,重新显示结果 ；一直到输出序列全部输出。