車廂調(diào)度問題


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

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