車廂調(diào)度問題


任務：
假設停在鐵路調(diào)度站(如教科書中圖3.1(b)所示)入口處的車廂系列的編號依次為1，2，3，…n。設計一個程序,求出所有可能由此輸出的長度為n 的車廂系列。
要求：
1設計一個程序，求出由一個編號依次為1，2，、、、，n的車廂序列可能產(chǎn)生的所有出棧系列。
2利用雙向棧存儲結(jié)構(gòu)實現(xiàn)調(diào)度站和輸出序列這兩個棧的空間共享。
3對于每個輸出序列演示出所有操作序列的變化過程 。

1、目的
在TC環(huán)境下，通過輸入車廂系列的編號n，求出所有可能由此輸出的長度為n的車廂系列，用入棧出棧的方法，實現(xiàn)車廂調(diào)度，并演示每一種出棧序列的過程。
2、結(jié)構(gòu)設計
⑴為了使車廂能夠調(diào)度，即改變原來的順序，需要定義一個棧，即利用棧先進后出的性質(zhì)，改變車廂的順序；因為輸出的序列有很多種，而且序列的產(chǎn)生是用遞歸產(chǎn)生的，因此需要定義一個結(jié)構(gòu)體，它可以保存所有的輸出序列，供演示時調(diào)用。
⑵初始化數(shù)據(jù)：主要是輸入車廂的長度，對輸出序列的結(jié)構(gòu)體的長度和它的內(nèi)嵌結(jié)構(gòu)體的長度初始化為0，并將棧初始化為空。
⑶顯示所有的序列：因為序列有很多種情況，為了得到它們，采用遞歸和回溯的算法，即利用編號出棧遞歸和編號入棧遞歸，當滿足條件的序列就輸出，在輸出的同時將題目復制給輸出序列的結(jié)構(gòu)體，供演示時調(diào)用。
⑷演示一種序列：演示時，采用的是向逆推的方法，因為我們已經(jīng)知道了一種輸出序列的結(jié)果和它的最出狀態(tài)，就可以利用棧將中間過程顯示出來；即當序列中當前的數(shù)據(jù)大于入口處的數(shù)據(jù)時, 入口處的數(shù)據(jù)要一直壓棧,直到大于出口處的數(shù)據(jù) 并顯示每一步結(jié)果 ；當序列中當前的數(shù)據(jù)小于入口處的數(shù)據(jù)時,彈出棧頂,重新顯示結(jié)果 ；一直到輸出序列全部輸出。