C++數(shù)據(jù)結(jié)構(gòu)火車緩沖軌問(wèn)題

《C++數(shù)據(jù)結(jié)構(gòu)火車緩沖軌問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1．實(shí)驗(yàn)要求i.實(shí)驗(yàn)?zāi)康?（1）通過(guò)上機(jī)編程，學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的使用。（2）熟悉C++語(yǔ)言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法，熟練改錯(cuò)方法。（3）熟悉設(shè)計(jì)算法的過(guò)程（4）進(jìn)一步掌握指針、模板類、異常處理的使用（5）掌握棧的操作的實(shí)現(xiàn)方法（6）掌握隊(duì)列的操作的實(shí)現(xiàn)方法（7）學(xué)習(xí)使用棧解決實(shí)際問(wèn)題的能力（8）學(xué)習(xí)使用隊(duì)列解決實(shí)際問(wèn)題的能力ii.實(shí)驗(yàn)內(nèi)容：利用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)車廂重排問(wèn)題。車廂重排問(wèn)題如下：一列貨車共有n節(jié)車廂，每個(gè)車廂都有自己的編號(hào)，編號(hào)范圍從1~n。給定任意次序的車廂，通過(guò)轉(zhuǎn)軌站將車廂

2、編號(hào)按順序重新排成1~n。轉(zhuǎn)軌站共有k個(gè)緩沖軌，緩沖軌位于入軌和出軌之間。開(kāi)始時(shí)，車廂從入軌進(jìn)入緩沖軌，經(jīng)過(guò)緩沖軌的重排后，按1~n的順序進(jìn)入出軌。緩沖軌按照先進(jìn)先出方式，編寫(xiě)一個(gè)算法，將任意次序的車廂進(jìn)行重排，輸出每個(gè)緩沖軌中的車廂編號(hào)。提示：一列火車的每個(gè)車廂按順序從入軌進(jìn)入不同緩沖軌，緩沖軌重排后的進(jìn)入出軌，重新編排成一列貨車。比如：編號(hào)為3的車廂進(jìn)入緩沖軌1，則下一個(gè)編號(hào)小于3的車廂則必須進(jìn)入下一個(gè)緩沖軌2，而編號(hào)大于3的車廂則進(jìn)入緩沖軌1，排在3號(hào)車廂的后面，這樣，出軌的時(shí)候才可以按照從小到大的順序重新編排。iii.代碼要求：1、必須要有異常處

3、理，比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識(shí)符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說(shuō)明該函數(shù)的功能關(guān)鍵代碼應(yīng)說(shuō)明其功能3、遞歸程序注意調(diào)用的過(guò)程，防止棧溢出2.程序分析火車緩沖問(wèn)題描述的是一列亂序的火車，經(jīng)過(guò)K個(gè)緩沖軌之后實(shí)現(xiàn)順序排列。在這個(gè)程第9頁(yè)北京郵電大學(xué)信息與通信工程學(xué)院序中，我首先聯(lián)想到了隊(duì)列具有先入先出的特點(diǎn)，可以將K個(gè)緩沖軌道設(shè)計(jì)為K條鏈隊(duì)列或者循環(huán)隊(duì)列。當(dāng)前的軌道若為空，則火車的一節(jié)車廂可按目前的順序進(jìn)入一個(gè)，若當(dāng)前車廂的序號(hào)大于后面一節(jié)的，若兩節(jié)車廂在同一緩沖軌則依隊(duì)列的特點(diǎn)出

4、列是將不能實(shí)現(xiàn)從大到小排列，故下一列車應(yīng)該進(jìn)入下一個(gè)緩沖軌。每節(jié)車廂都按照上述進(jìn)行判斷再安排進(jìn)入緩沖軌。緩沖軌數(shù)量k是一個(gè)確定數(shù)，當(dāng)算法中所需要的緩沖軌數(shù)大于k時(shí)將無(wú)法實(shí)現(xiàn)重新排列，故需要提醒設(shè)計(jì)者多安排幾條緩沖軌道。若實(shí)際所需軌道數(shù)小于k則會(huì)有空的緩沖軌道。出軌的時(shí)候應(yīng)按照由小至大的順序依次出軌，需要在各條緩沖軌道之間查找相應(yīng)的列車節(jié)數(shù)。（但是其實(shí)可以邊入軌，當(dāng)該車廂在緩沖軌中的后一節(jié)車廂入軌后可以直接出軌，不一定要等到全部都入軌再出軌。）2.1存儲(chǔ)結(jié)構(gòu)鏈隊(duì)列的存儲(chǔ)示意圖：緩沖軌道1:……緩沖軌道2……``````緩沖軌道k：……2.2關(guān)鍵算法分析：a

5、)設(shè)定并初始化計(jì)數(shù)器j=0，have=1（這是一個(gè)bool型變量，用來(lái)判斷當(dāng)初循環(huán)是否還具有緩沖軌可用。）b)?用while判斷是否入軌，用i

6、實(shí)現(xiàn)一次，j++；可以實(shí)現(xiàn)入軌，令have=1.跳出for循環(huán)并進(jìn)入while循環(huán).（3）判斷是否還能繼續(xù)排軌。①?have=0無(wú)法實(shí)現(xiàn)重新排列，故需要提醒設(shè)計(jì)者多安排幾條緩沖軌道。②have=1有合適的緩沖軌，則遍歷緩沖軌，排列完畢后由小至大輸出。時(shí)間復(fù)雜度的計(jì)算：o（n2）第9頁(yè)北京郵電大學(xué)信息與通信工程學(xué)院代碼如下：voidchange(intq[],LinkQueued[],intn,intk){intj=0;//已經(jīng)重排車廂的數(shù)目boolhave=1;//還有緩沖軌道可以使用while((j

7、{have=0;//在后面的程序中改變have的值，若不變則說(shuō)明沒(méi)有排這節(jié)車廂for(inti=0;i

8、-1].read();cout<