實(shí)驗(yàn)2用堆棧解決火車車廂重排問題的編程.doc

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