實驗2用堆棧解決火車車廂重排問題的編程.doc

實驗2用堆棧解決火車車廂重排問題的編程一、 目的通過對本次實驗，我們應(yīng)：1、 加深對線性表、堆棧的認識；2、 加深接口、類、索引器的認識；3、 掌握堆棧數(shù)據(jù)結(jié)構(gòu)，并應(yīng)用堆棧編程解決實際問題。二、 實驗準(zhǔn)備1、軟件準(zhǔn)備：C#.net。2、參考數(shù)據(jù)（示例）：文件夾“實驗2示例”中的數(shù)據(jù)。三、 實驗背景描述1、問題描述一列貨運列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1 -n，貨運列車按照第n站至第1站的次序經(jīng)過這些車站。車廂的編號與它們的目的地相同。為了便于從列車上卸掉相應(yīng)的車廂，必須重新排列車廂，使各車廂從前至后按編號1到n的次序排列。當(dāng)所有的車廂都按照這種次序排列時，在每個車站只需卸掉最后一節(jié)車廂即可。我們在一個轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個入軌、一個出軌和k個緩沖鐵軌（位于入軌和出軌之間）。圖3.1a 給出了一個轉(zhuǎn)軌站，其中有k= 3個緩沖鐵軌H1，H2和H3。開始時，n節(jié)車廂的貨車從入軌處進入轉(zhuǎn)軌站，轉(zhuǎn)軌結(jié)束時各車廂從右到左按照編號1至編號n的次序離開轉(zhuǎn)軌站（通過出軌處）。在圖3.1a 中，n= 9，車廂從后至前的初始次序為5，8，1，7，4，2，9，6，3。圖3.1b 給出了按所要求的次序重新排列后的結(jié)果。圖2.1根據(jù)上面的描述，編寫程序?qū)崿F(xiàn)下面的功能： 編寫一算法實現(xiàn)火車車箱的重排； 編寫程序模擬圖2.1所示的具有9節(jié)車廂的火車入軌和出軌的過程。 程序主界面設(shè)計如圖2.2所示。圖2.22、問題分析為了重排車廂，需從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動到緩沖鐵軌上，直到按輸出次序要求輪到它時才將它放到出軌上。緩沖鐵軌上車廂的進和出只能在緩沖鐵軌的尾部進行。當(dāng)緩沖鐵軌上的車廂編號不是按照從頂?shù)降椎倪f增次序排列時，重排任務(wù)將無法完成。 新的車廂u應(yīng)送入這樣的緩沖鐵軌：其底部的車廂編號v滿足vu,且v是所有滿足這種條件的緩沖鐵軌頂部車廂編號中最小的一個編號。只有這樣才能使后續(xù)的車廂重排所受到的限制最小。3、堆棧的基本操作 初始化棧：也就是產(chǎn)生一個新的空棧； 入棧操作Push(T x):將指定類型元素x進到棧中； 出棧操作Pop(): 將棧中的棧頂元素取出來，并在棧中刪除棧頂元素； 取棧頂元素GetTop():將棧中的棧頂元素取出來，棧中元素不變； 判斷?？誌sEmpty():若棧為空，返回true，否則返回false； 清空操作Clear ( )：從棧中清除所有的數(shù)據(jù)元素。四、