實(shí)驗(yàn)4線性結(jié)構(gòu)綜合實(shí)驗(yàn)

1、實(shí)驗(yàn)4 線性結(jié)構(gòu)綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?. 熟練掌握順序表、鏈表及棧和隊(duì)列的概念、特點(diǎn)及實(shí)現(xiàn)2. 掌握各種線性結(jié)構(gòu)的基本運(yùn)算3. 加深線性結(jié)構(gòu)理解，逐步培養(yǎng)解決復(fù)雜實(shí)際問題的編程能力。二、實(shí)驗(yàn)內(nèi)容1. 刪除單鏈表中的重復(fù)結(jié)點(diǎn) 一帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)值為整型，其中元素按結(jié)點(diǎn)值從小到大排列，要求刪除此鏈表中結(jié)點(diǎn)值重復(fù)的結(jié)點(diǎn)，只保留一個(gè)結(jié)點(diǎn)。如：?jiǎn)捂湵碇械慕Y(jié)點(diǎn)元素依次為(1,3,3,3,5,5,7)，則完成此操作后單鏈表的結(jié)點(diǎn)為(1,3,5,7)。2. 約瑟夫環(huán) 約瑟夫（Joeph）問題的一種描述是：編號(hào)為1,2,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)

2、數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。測(cè)試數(shù)據(jù) m的初值為20=6；n=7，他們的密碼為3，1，7=0，2，4，8=2，4；則正確的結(jié)果應(yīng)為6，1，4，7，2，3，5。實(shí)現(xiàn)提示 程序運(yùn)行后首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼。設(shè)n30。算法分析 本題需循環(huán)計(jì)數(shù)，為此，可以使用一個(gè)一維數(shù)組存儲(chǔ)每個(gè)人的狀態(tài)，初為零，表示此人還未出列。 然后循環(huán)報(bào)數(shù)，這需要一個(gè)變量來(lái)存儲(chǔ)當(dāng)前用戶報(bào)的數(shù)，當(dāng)報(bào)的數(shù)達(dá)到密碼m時(shí)

3、，停止計(jì)數(shù)，并將當(dāng)前用戶出列。然后計(jì)數(shù)器置0，繼續(xù)報(bào)數(shù)，至所有用戶均出列為止。3. 停車場(chǎng)管理 設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來(lái)的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理

4、的模擬程序。算法思路 根據(jù)要求由此很容易聯(lián)想到棧，因此可首先設(shè)計(jì)一個(gè)堆棧，以堆棧來(lái)模擬停車場(chǎng)，可用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)停車場(chǎng)內(nèi)的車輛信息，并給車輛按進(jìn)棧順序編號(hào)，當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入停車場(chǎng)。這是個(gè)一退一進(jìn)的過程，而且讓道的汽車必須保持原有的先后順序，因此可再設(shè)計(jì)一個(gè)堆棧，以之來(lái)暫時(shí)存放為出站汽車暫時(shí)讓道的汽車。當(dāng)停車場(chǎng)滿后，繼續(xù)進(jìn)來(lái)的汽車需要停放在停車場(chǎng)旁邊的便道上等候，若停車場(chǎng)有汽車開走，則按排隊(duì)的先后順序依次進(jìn)站，最先進(jìn)入便道的汽車將會(huì)最先進(jìn)入停車場(chǎng)，這完全是一個(gè)先進(jìn)先出模型，因此可設(shè)計(jì)一個(gè)隊(duì)列來(lái)模擬便

5、道，隊(duì)列中的數(shù)據(jù)元素設(shè)計(jì)成汽車的車牌號(hào)。另外，停車場(chǎng)根據(jù)汽車在停車場(chǎng)內(nèi)停放的總時(shí)長(zhǎng)來(lái)收費(fèi)的，在便道上的時(shí)間不計(jì)費(fèi)，因此必須記錄車輛進(jìn)入停車場(chǎng)時(shí)的時(shí)間和車輛離開停車場(chǎng)時(shí)的時(shí)間，然后計(jì)算、顯示費(fèi)用情況。核心算法停車場(chǎng)使用棧存儲(chǔ)，便道使用隊(duì)列存儲(chǔ)到達(dá)：車a到達(dá)時(shí)如果棧未滿，則入棧否則，將其加入到便道車隊(duì)中記錄停車時(shí)間并顯示之。離開：當(dāng)車a離開時(shí)首先在停車場(chǎng)（棧）中查找車a，如果找到，則a以前的車均出棧并進(jìn)入臨時(shí)棧（先臨時(shí)退出停車場(chǎng)）。然后a出棧，并記錄其離開時(shí)間，計(jì)算費(fèi)用。并顯示之。臨時(shí)棧中所有車出棧并進(jìn)入停車場(chǎng)棧；從便道隊(duì)列中取一輛車進(jìn)入停車場(chǎng)。主函數(shù)：初始化棧和隊(duì)列從鍵盤輸入指令（停車或離開）調(diào)用到達(dá)、停車函數(shù)實(shí)現(xiàn)功能。三、實(shí)驗(yàn)報(bào)告要求1. 根據(jù)程序要求對(duì)運(yùn)行結(jié)果進(jìn)行分析。如果程序未能調(diào)試通過，分析其原因。2. 根據(jù)實(shí)驗(yàn)步驟，說明未能編譯通過的原因，并正確進(jìn)行