2024級(jí)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書

161.運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)

【問題描述】

參與運(yùn)動(dòng)會(huì)的n個(gè)學(xué)校編號(hào)為1?必競賽分成/個(gè)男子項(xiàng)目和“個(gè)女子項(xiàng)目，

項(xiàng)目編號(hào)分別為1?麻II?1?研人由于各項(xiàng)目參與人數(shù)差別較大，有些項(xiàng)目取前

五名，得分依次為7,5,3,2,1；還有些項(xiàng)目只取前三名，得分依次為5,3,2o

寫一個(gè)統(tǒng)計(jì)程序產(chǎn)生各種成果單和得分報(bào)表。

【基本要求】

1）可以輸入各個(gè)項(xiàng)目的前三名或前五名的成果；

2）能統(tǒng)計(jì)各學(xué)?？偡?，

3）可以按學(xué)校編號(hào)或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出；

4）可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的狀況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们?/p>

三或前五名的學(xué)校。

5）數(shù)據(jù)存入文件并能隨時(shí)查詢

6）規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱

輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整型。

界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，依據(jù)提示，可以完成相

關(guān)的功能要求。

存儲(chǔ)結(jié)構(gòu)：學(xué)生自己依據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)

據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。

測試數(shù)據(jù)：

【測試數(shù)據(jù)】

要求運(yùn)用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程

序測試，以保證程序的穩(wěn)定。

例如，對(duì)于〃=4,〃-3,掖=2,編號(hào)為奇數(shù)的項(xiàng)目取前五名，編號(hào)為偶數(shù)的

項(xiàng)目取前三名，設(shè)計(jì)一組實(shí)例數(shù)據(jù)。

【實(shí)現(xiàn)提示】

可以假設(shè)〃W20,〃忘30,vv<20,姓名長度不超過20個(gè)字符。每個(gè)項(xiàng)目結(jié)

束時(shí)，將其編號(hào)、類型符（區(qū)分取前五名還是前三名）輸入，并按名次依次輸入

運(yùn)動(dòng)員姓名、校名（和成績）。

【選作內(nèi)容】

允許用戶指定某項(xiàng)目實(shí)行其他名次取法。

162.約瑟夫環(huán)

【問題描述】

約瑟夫（Joseph）問題的一種描述是：編號(hào)為I,2,...,n的〃個(gè)人按順

時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一起先任選一個(gè)正整數(shù)作為

報(bào)數(shù)上限值〃3從第一個(gè)人起先按順時(shí)針方向自I起先依次報(bào)數(shù)，報(bào)到小時(shí)停止

報(bào)數(shù)。報(bào)〃2的人出列，將他的密碼作為新的加值，從他在順時(shí)針方向上的下一個(gè)

人起先重新從1報(bào)數(shù)，如此下去，直至全部人全部出列為止。試設(shè)計(jì)一個(gè)程序求

出出列依次。

【基本要求】

利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，依據(jù)出列的依次印出各人的編號(hào)。

【測試數(shù)據(jù)】

m的初值為20；〃=7,7個(gè)人的密碼依次為：3,1,7,2,4,8,4,首

先m值為6(正確的出列依次應(yīng)為6,1,4,7.2,3,5)。

【實(shí)現(xiàn)提示】

程序運(yùn)行后，首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取各人的密碼?？?/p>

設(shè)〃W30。此題所用的循環(huán)鏈表中不須要“頭結(jié)點(diǎn)”，請(qǐng)留意空表和非空表的

界限。

【選作內(nèi)容】

向上述程序中添加在依次結(jié)構(gòu)上實(shí)現(xiàn)的部分。

164,長整數(shù)四則運(yùn)算

【問題描述】

設(shè)計(jì)一個(gè)實(shí)現(xiàn)隨意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。

【基本要求】

利用雙向循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型

變量的范圍是一(2凡|)?(2凡I)。輸入和輸出形式：按中國對(duì)于長整數(shù)的表示習(xí)

慣，每四位一組，組間用逗號(hào)隔開。

【測試數(shù)據(jù)】

(1)0；0；應(yīng)輸出“0"。

(2)-2345,6789；-7654,3211；應(yīng)輸出”一1,0000,()()()()”。

(3)-9999,9999；1,0000,0000,0000；應(yīng)輸出"9999,0000,0001”。

(4)1,0001,0001；-1,0001,0001；應(yīng)輸出。

(5)1,0001,0001；-1,0001,0000；應(yīng)輸出“1"o

(6)-9999,9999,9999；―9999,9999,9999；應(yīng)輸出"-1,9999,

9999,9998”。(7)1,000(),9999,9999；1；應(yīng)輸出”1,0001,

0000,0000°o

【實(shí)現(xiàn)提示】

(1)每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為2,5-1=32767,才能保證兩數(shù)相加不

會(huì)溢出。但若這樣存放，即相當(dāng)于按32768進(jìn)制數(shù)存放，在十進(jìn)制數(shù)與32768進(jìn)

制數(shù)之間的轉(zhuǎn)換特別不便利。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超

過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制數(shù)。

(7.)可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長整數(shù)的符號(hào).相加過程中不要破壞

兩個(gè)操作數(shù)鏈表。不能給長整數(shù)位數(shù)規(guī)定上限。

【選作內(nèi)容】

(1)實(shí)現(xiàn)長整數(shù)的四則運(yùn)算；

(2)實(shí)現(xiàn)長整數(shù)的乘方和階乘運(yùn)算；

(3)整型量范圍是一(2〃-1)~(2〃-1),其中，〃是由程序讀人的參量。輸

入數(shù)據(jù)的分

組方法可以另行規(guī)定。

165.一元稀疏多項(xiàng)式計(jì)算器

【問題描述】

設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡潔計(jì)算器。

【基本要求】

一元稀疏多項(xiàng)式簡潔計(jì)算器的基本功能是：

(1)輸入并建立多項(xiàng)式；

(2)輸出多項(xiàng)式,輸出形式為整數(shù)序列：力，ci,ei,C2,或，…,CM,其

中〃是多項(xiàng)式的項(xiàng)數(shù)，。和3分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降

序排列；

(3)多項(xiàng)式〃和〃相加，建立多項(xiàng)式

(4)多項(xiàng)式Q和〃相減，建立多項(xiàng)式。功o

【測試數(shù)據(jù)】

(1)(2X+5X8-3.IX,,)+(7-5X8+1IX9)=(-3.1XH+11X9+2X+7)

(2)(6X-3-X+4.4X2-1.2X9)-(-6X3+5.4X2-X2+7.8X15)

=(-7.8XI5-1.2X9+12X-3-X)

(3)(1+x+x2+x3+x4+x5)+(-x3—x4)=(1+x+x2+x5)

(4)(x+x3)+(-x—x3)=0

(5)(x+x,(w)4-(x,oo+x2oo)=(x4-2x,oo+x2o())

(6)(x+x2+x3)+0=x+x2+x3

(7)互換上述測試數(shù)據(jù)中的前后兩個(gè)多項(xiàng)式

【實(shí)現(xiàn)提示】

用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。

【選作內(nèi)容】

(1)計(jì)算多項(xiàng)式在x處的值。

(2)求多項(xiàng)式a的導(dǎo)函數(shù)，。

(3)多項(xiàng)式a和b相乘，建立乘積多項(xiàng)式

abo

(4)多項(xiàng)式的輸出形式為類數(shù)學(xué)表達(dá)式。例如，多項(xiàng)式-3x8+6x3—18的輸

出形式為

-3/8+6/3-18,xF(-8)x7-14的輸出形式為xA15-8xA7-140留意,數(shù)

值為1的非零次項(xiàng)的輸出形式中略去系數(shù)1,如項(xiàng)以8的輸出形式為x8,項(xiàng)一以3

的輸出形式為一x3。

(5)計(jì)算器的仿真界。

166.池塘夜降彩色雨

【問題描述】

設(shè)計(jì)一個(gè)程序，演示漂亮的“池塘夜雨”景色：色調(diào)繽紛的雨點(diǎn)飄飄灑灑地

從天而降，滴滴入水有聲，濺起圈圈微瀾。

【基本要求】

(I)雨點(diǎn)的空中出現(xiàn)位置、降范過程的可見程度、入水位置、顏色、最大水

圈等，都是隨機(jī)確定的；

(2)多個(gè)雨點(diǎn)依據(jù)各自的隨機(jī)參數(shù)和存在狀態(tài)，同時(shí)演示在屏幕上。

【測試數(shù)據(jù)】

適當(dāng)調(diào)整限制雨點(diǎn)密度、最大水圈和狀態(tài)變更的時(shí)間間隔等參數(shù)。

【實(shí)現(xiàn)提示】

(1)每個(gè)雨點(diǎn)的存在周期可分為三個(gè)階段：從天而降、入水有聲和圈圈微瀾,

須要一

個(gè)記錄存儲(chǔ)其相關(guān)參數(shù)、當(dāng)前狀態(tài)和下一狀態(tài)的更新時(shí)刻。

(2)在圖形態(tài)態(tài)編程。雨點(diǎn)下降的可見程度應(yīng)是斷斷續(xù)續(xù)、依稀可見；圈圈

水波應(yīng)是

由里至外漸漸擴(kuò)大和消逝。

(3)每個(gè)雨點(diǎn)發(fā)生時(shí)，生成其記錄，并預(yù)置下一個(gè)雨點(diǎn)的發(fā)生時(shí)間。

(4)用一個(gè)適當(dāng)?shù)慕Y(jié)構(gòu)管理當(dāng)前存在的雨點(diǎn)，使系統(tǒng)能利用它按時(shí)更新每個(gè)

雨點(diǎn)的狀態(tài)，一旦有雨點(diǎn)的水圈全部消逝，就從結(jié)構(gòu)中刪去。

【選作內(nèi)容】

(1)增加“電閃雷鳴”景象。

(2)增加風(fēng)的效果，呈現(xiàn)“風(fēng)雨飄搖”的情景。

(3)增加雨點(diǎn)密度的變更：時(shí)而“和風(fēng)細(xì)雨”，時(shí)而“暴風(fēng)驟雨”。

(4)將“池塘”改為“荷塘”，雨點(diǎn)滴在荷葉上的效果是濺起四散的水珠，響聲也不同

ch2棧和隊(duì)列及其應(yīng)用

僅僅相識(shí)到棧和隊(duì)列是兩種特別的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在

于使讀者深化了解錢和隊(duì)列的特性，以便在實(shí)際問題背景下敏捷運(yùn)用他們；同時(shí)

還將鞏固對(duì)這兩種結(jié)構(gòu)的構(gòu)造方法的理解。

編程技術(shù)訓(xùn)練要點(diǎn)有：基本的“任務(wù)書”觀點(diǎn)及其典型用法(見本實(shí)習(xí)202)；

問題求解的狀態(tài)表示及其遞歸算法(2.3,2.4和2.9)；利用棧實(shí)現(xiàn)表達(dá)式求值的技

術(shù)(2.5)；事務(wù)驅(qū)動(dòng)的模擬方法(2.63.8)；以及動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)(2.6,2.7和2.8)。

167.停車場管理

［問題描述］

設(shè)停車場內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車

在停車場內(nèi)按車輛到達(dá)時(shí)旬的先后依次，依次由北向南排列(大門在最南端，最先到達(dá)的第

一輛車停放在車場的最北端)，若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道

上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，

在它之后開入的車輛必需先退出車場為它讓路，待該輛主開出大門外，其它車輛再按原次序

進(jìn)入車場，每輛停放在車場的車在它離開停車場時(shí)必需按它停留的時(shí)間長短交納費(fèi)用。試為

停車場編制按上述要求進(jìn)行管理的模擬程序。

［測試數(shù)據(jù)］

設(shè)n=2,輸入數(shù)據(jù)為：(W,1,5),('A',2,10),('D',1,15),('A',

3,20),('A，,4,25),('A',5,30),(B,2,35),(D,4,40),

('E，,0,0)。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車

牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，'A'表示到達(dá)；'【）’表示離去，'E'表示輸入結(jié)

束。

［基本要求］

以棧模擬停車場，以隊(duì)列模擬車場外的便道，依據(jù)從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬

管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到

達(dá)或離去的時(shí)刻，對(duì)每一處輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車

在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納

的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以依次結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。

［實(shí)現(xiàn)提示］

需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車，也用依次存

儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)

據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場的時(shí)刻。

［選作內(nèi)容］

（1）兩個(gè)棧共享空訶，思索應(yīng)開拓?cái)?shù)組的空間是多少？

（2）汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和

1.5輛小汽車的占地面積相同，1輛十輪卡車占地面枳相當(dāng)于3輛小汽車的占地面積。

（3）汽車可以干脆從便道上開走，此時(shí)排在它前面的汽車要先開走讓路，然后再依次

排到隊(duì)尾。

（4）停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請(qǐng)思索如何修改

結(jié)構(gòu)以滿意這種要求。

168.魔王語言說明

【問題描述】

有一個(gè)魔王總是運(yùn)用自己的一種特別精練而抽象的語言講話，沒有人能昕得

懂，但他的語言是可以逐步說明成人能聽懂的語言，因?yàn)樗恼Z言是由以下兩種

形式的規(guī)則由人的語言逐步抽象上去的：

⑴一夕也…凡

（2）（一名…凡）t他仍一…朗坦

在這兩種形式中，從左到右均表示說明。試寫一個(gè)魔王語言的說明系統(tǒng)，把

他的話說明成人能聽得懂的話。

【基本要求】

用下述兩條具體規(guī)則和上述規(guī)則形式（2）實(shí)現(xiàn)。設(shè)大寫字母表示魔王語言的

詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代

換的變量。魔王語言兀含人的詞匯。

（1）BiiAdA

（2）Asae

【測試數(shù)據(jù)】

B(ehnxgz)B說明成tsaedsaeezegexenehetsaedsae

若將小寫字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說的話是“天上一只

鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。

tdSaCZgXnh

天地上一只鵝追趕下蛋恨

【實(shí)現(xiàn)提示】

將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ攲幏?。若是開括號(hào)，則逐一出棧,

將字母依次入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。

其他情形較簡潔，請(qǐng)讀者思索應(yīng)如何處理。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作。

【選作內(nèi)容】

(1)由于問題的特別性，可以實(shí)現(xiàn)棧和隊(duì)列的依次存儲(chǔ)空間共享。

(2)代換變量的數(shù)目不限，則在程序起先運(yùn)行時(shí)首先讀入一組第一種形式的

規(guī)則，而不是把規(guī)則固定在程序中(其次種形式的規(guī)則只能固定在程序中)。

169.馬踏棋盤

【問題描述】

設(shè)計(jì)一個(gè)國際象棋的馬踏遍棋盤的演示程序。

【基本要求】

將馬隨機(jī)放在國際象棋的8x8棋盤Board網(wǎng)兇的某個(gè)方格中，馬按走棋規(guī)則

進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制非遞歸

程序，求出馬的行走路途，并按求出的行走路途，將數(shù)字I,2,…，64依次填

入一個(gè)8x8的方陣，輸出之。

170.算術(shù)表達(dá)式求值演示

【問題描述】

表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型

例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。

［基本要求］

以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教

科書表3.1給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿

照教科書的例3?1演示在求值中運(yùn)算符械、運(yùn)算數(shù)校、輸入字符和主要操作的變

更過程。

171.銀行業(yè)務(wù)模擬

【問題描述】

客戶業(yè)務(wù)分為兩種。第一種是申請(qǐng)從銀行得到一筆資金，即取款或借款。其

次種是向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)地有兩

個(gè)隊(duì)列?？蛻舻竭_(dá)銀行后先排第一個(gè)隊(duì)。處理每個(gè)客戶業(yè)務(wù)時(shí)，假如屬于第一種,

且申請(qǐng)額超出銀行現(xiàn)存資金總額而得不到滿意，則馬上排入其次個(gè)隊(duì)等候，直至

滿意時(shí)才離開銀行；否則業(yè)務(wù)處理完后馬上離開銀行。每接待完一個(gè)其次種業(yè)務(wù)

的客戶，則依次檢查和處理（假如可能）其次個(gè)隊(duì)列中的客戶，對(duì)能滿意的申請(qǐng)者

予以滿意，不能滿意者重新排到其次個(gè)隊(duì)列的隊(duì)尾。留意，在此檢查過程中，

旦銀行資金總額少于或等于剛才第一個(gè)隊(duì)列中最終一個(gè)客戶（其次種業(yè)務(wù)）被接

待之前的數(shù)額，或者本次已將其次個(gè)隊(duì)列檢查或處理了一遍，就停止檢查（因?yàn)?/p>

此時(shí)己不行能還有能滿意者）轉(zhuǎn)而接著接待第一個(gè)隊(duì)列的客戶。任何時(shí)刻都只開

一個(gè)窗口。假設(shè)檢查不須要時(shí)間.營業(yè)時(shí)間結(jié)束時(shí)全部客戶馬上離開銀行。

寫一個(gè)上述銀行業(yè)務(wù)的事務(wù)驅(qū)動(dòng)模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留

的平均時(shí)間。

［基本要求］

利用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)模擬。

【測試數(shù)據(jù)】

一天營業(yè)起先時(shí)銀行擁有的款額為10000（元），營業(yè)時(shí)間為600（分鐘）。其他

模擬參

量自定，留意測定兩種極端的狀況：一是兩個(gè)到達(dá)事務(wù)之間的間隔時(shí)間很短，而

客戶的交易時(shí)間很長，另一個(gè)恰好相反，設(shè)置兩個(gè)到達(dá)事務(wù)的間隔時(shí)間很長，而

客戶的交易時(shí)間很短。

【實(shí)現(xiàn)提示】

事務(wù)有兩類：到達(dá)銀行和離開銀行。初始時(shí)銀行現(xiàn)存資金總額為total。起先

營業(yè)后的第一今事務(wù)是客戶到達(dá)，營業(yè)時(shí)間從。到closetime。到達(dá)事務(wù)發(fā)生時(shí)隨

機(jī)地設(shè)置此客戶的交易時(shí)間和距下一到達(dá)事務(wù)之間的時(shí)間間隔。每個(gè)客戶要辦理

的款額也是隨機(jī)確定的，用負(fù)值和正值分別表示第一類和其次類業(yè)務(wù)。變量total,

closetime以及上述兩個(gè)隨機(jī)量的上下界均交互地從終端讀入，作為模擬參數(shù)。

兩個(gè)隊(duì)列和一個(gè)事務(wù)表均要用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。留意弄清應(yīng)當(dāng)在什么條件下設(shè)

置離開事務(wù)，以及其次個(gè)隊(duì)列用怎樣的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)可以獲得較高的效率。留

意：事務(wù)表是按時(shí)間依次有序的。

【選作內(nèi)容】

自己實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)類型。例如對(duì)于客戶結(jié)點(diǎn)，定義pool為

CustNodepoolfMAX］；

//結(jié)構(gòu)類型CustNode含四個(gè)域：alTHIne,durtime,amount,next

或者定義四個(gè)同樣長的，以上述域名為名字的數(shù)組。初始時(shí)，將全部重量的next

域鏈接起來，形成一個(gè)靜態(tài)鏈找，設(shè)置一個(gè)樓頂元素下標(biāo)指示量top,top=0表

示找空。動(dòng)態(tài)存儲(chǔ)安排函數(shù)可以取名為myMalloc,其作用是出錢，將錢頂元素

的下標(biāo)返回。若返回的值為0,則表示尢空間可安排。歸還函數(shù)可取名為myFree,

其作用是把該重量入錢。用FOR-TRAN和BASIC等語言實(shí)現(xiàn)時(shí)只能如此地自行

組織。

172.航空客運(yùn)訂票系統(tǒng)

【問題描述】

航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計(jì)

一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。

【基本要求】

（1）每條航線所涉及的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛行周日（星期

兒）、乘員定額、余票量、已訂票的客戶名單（包括姓名、訂票量、艙位等級(jí)1,2

或3）以及等候替補(bǔ)的客戶名單（包括姓名、所需票量）；

（2）系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：

①錄入：可以錄入航班狀況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲(chǔ)在文件

中；

②查詢航線：依據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星

期幾飛行，最近一天航班的日期和余票額；

③承辦訂票業(yè)務(wù)：依據(jù)客戶提出的要求（航班號(hào)、訂票數(shù)額）查詢?cè)摵桨嗥鳖~

狀況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號(hào)；若已滿員或余票額少

于訂票額，則需重新詢問客戶要求。若須要，可登記排隊(duì)候補(bǔ)；

④承辦退票業(yè)務(wù)：依據(jù)客戶供應(yīng)的狀況（日期、航班），為客戶辦理退票手續(xù),

然后查詢?cè)摵桨嗍欠裼腥伺抨?duì)候補(bǔ)，首先詢問排在第一的客戶，若所退票額能滿

意他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊(duì)候補(bǔ)的客戶。

【測試數(shù)據(jù)】

由讀者自行指定。

【實(shí)現(xiàn)提示】

兩個(gè)客戶名單可分別由線性表和隊(duì)列實(shí)現(xiàn)。為查找便利，已訂票客戶的線性

表應(yīng)按客戶姓名有序，并且，為插入和刪除便利，應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。由于預(yù)

約人數(shù)無法預(yù)料，隊(duì)列也應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線的狀況

登錄在一張線性表上，由于航線基本不變，可采納依次存儲(chǔ)結(jié)構(gòu)，并按航班有序

或按終點(diǎn)站名有序。每條航線是這張表上的一個(gè)記錄，包含上述8個(gè)域、其中乘

員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，等候替補(bǔ)的客戶名單域?yàn)榉謩e指向隊(duì)頭

和隊(duì)尾的指針。

【選作內(nèi)容】

當(dāng)客戶訂票要求不能滿意時(shí)，系統(tǒng)可向客戶供應(yīng)到達(dá)同一目的地的其他航線

狀況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。

173.電梯模擬

【問題描述】

設(shè)計(jì)一個(gè)電梯模擬系統(tǒng)。這是一個(gè)離散的模擬程序，因?yàn)殡娞菹到y(tǒng)是乘客和

電梯等“活動(dòng)體”構(gòu)成的集合，雖然他們彼此交互作用，但他們的行為是基本獨(dú)立

的。在離散的模擬中，以模擬時(shí)鐘確定每個(gè)活動(dòng)體的動(dòng)作發(fā)生的時(shí)刻和依次，系

統(tǒng)在某個(gè)模擬瞬間處理有待完成的各種事情，然后把模擬時(shí)鐘推動(dòng)到某個(gè)動(dòng)作預(yù)

定要發(fā)生的下一個(gè)時(shí)刻。

［基本要求］

（D模擬某校五層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停留。

五個(gè)樓層由下至上依次稱為地下層、第一層、其次層、第三層和第四層，其中第

一層是大樓的迸出層，即是電梯的“本壘層“，電梯”空閑”時(shí)，將來到該層候命。

（2）乘客可隨機(jī)地進(jìn)出于任何層。對(duì)每個(gè)人來說，他有一個(gè)能容忍的最長等

待時(shí)間，一旦等候電梯時(shí)間過長，他將放棄。

（3）模擬時(shí)鐘從0起先，時(shí)間單位為0.1秒。人和電梯的各種動(dòng)作均要耗費(fèi)

肯定的時(shí)間單位（簡記為t）,比如：

有人進(jìn)出時(shí)，電梯每隔401測試一次，若無人進(jìn)出，則關(guān)門；

關(guān)門和開門各須要20tg

每個(gè)人進(jìn)出電梯均須要25h

假如電梯在某層靜止時(shí)間超過3（）（）t,則駛回1層候命。

（4）按時(shí)序顯示系統(tǒng)狀態(tài)的變更過程：發(fā)生的全部人和電梯的動(dòng)作序列。

【測試數(shù)據(jù)】

模擬時(shí)鐘Time的初值為0,終值可在500-10000范圍內(nèi)逐步增加。

【實(shí)現(xiàn)提示】

（1）樓層由下至上依次編號(hào)為（），1,2,3,4o每層有要求Up（上）和Down（下）

的兩個(gè)按鈕，對(duì)應(yīng)10個(gè)變量CaliUp［0..4］和CallDOWEl［0..4］o電梯內(nèi)5個(gè)目標(biāo)

層按鈕對(duì)應(yīng)變量Caucar［0..4］。有人按下某個(gè)按鈕時(shí)，相應(yīng)的變量就置為1,一旦

要求滿意后，電梯就把該變量清為0。

（2）電梯處于三種狀態(tài)之-zGoingUp（上行）、GoingDown（下行）和Idle（停候）。

假如電梯處于Idle狀態(tài)且不在1層，則關(guān)門并駛回1層。在1層停候時(shí)，電梯是

閉門候命。一旦收到往另一層的吩咐，就轉(zhuǎn)入GoingUp或GoingDown狀態(tài)，執(zhí)

行相應(yīng)的操作。

（3）用變量Time表示模擬時(shí)鐘，初值為0,時(shí)間單位。）為0。1秒。其他重要

的變量有：

Floor——電梯的當(dāng)前位置（樓層）；

DI——值為0,除非人們正在進(jìn)入和離開電梯；

D2一一值為0,假如電梯己經(jīng)在某層停候30Ot以上；

D3——值為0,除非電梯門正開著又無人迸出電梯；

State——電梯的當(dāng)前狀態(tài)（GoingUp,GoingDOWEl,Idle）。

系統(tǒng)初始時(shí)，F(xiàn)loor=1,D1=D2=D3=0,State=Idle。

（4）每個(gè)人從進(jìn)入系統(tǒng)到離開稱為該人在系統(tǒng)中的存在周期。在此周期為，

他有6種可能發(fā)生的動(dòng)作：

ML［進(jìn)入系統(tǒng)，為下一人的出現(xiàn)作打算］產(chǎn)生以下數(shù)值：

InFloor該人進(jìn)入哪層樓；

OlltFloor他要去哪層樓；

GiveupTime也能容忍的等候時(shí)間；

Inter-Time——下一人出現(xiàn)的時(shí)間間隔，據(jù)此系統(tǒng)預(yù)置下一人進(jìn)入系統(tǒng)的時(shí)

刻。

M2.［按電鈕并等候］此時(shí)應(yīng)對(duì)以下不同狀況作不同的處理：

①Floor二InFloor且電梯的下一個(gè)活動(dòng)是E6（電梯在本層，但正在關(guān)門〉；

②Floor=InFloor且D3手0（電梯在本層，正有人進(jìn)出）；

③其他狀況，可能D2=0或電梯處于活動(dòng)E1（在1層停候）。

M3.［進(jìn)入排隊(duì)］在等候隊(duì)列Queu6［InFk）or］末尾插入該人，并預(yù)置在

GiveupTime個(gè)t之后，他若仍在隊(duì)列中將實(shí)施動(dòng)作M4。

M4.［放棄］假如Floor手InFloor或Dl=0,則從Quem［InFloor］和系統(tǒng)刪除

該人。假如Fk）or=InFloor且D1學(xué)0,他就接著等候（他知道立刻就可進(jìn)入電梯〉。

M5.［進(jìn)入電梯］從Qucuc［InFloor）刪除該人，并把他插入到lElevator（日梯）

校中。置CancarfOlltRoor］為1。

M6.［離去］從Elevator和系統(tǒng)刪除該人。

(5)電梯的活動(dòng)有9種：

EL［在1層停候］若有人按下一個(gè)按鈕，則調(diào)用Controler將電梯轉(zhuǎn)入活動(dòng)E3

或E60o

E2.［要變更狀態(tài)?］假如電梯處于GoingUp(或GoingDown〉狀態(tài)，但該方向

的樓層卻無人等待，則要看反方向樓層是否有人等候，而確定置State為

GoingDown(或GoingUp)還是Idle。

E3.［開門］置DI和D2為非0值，預(yù)置300個(gè)t后啟動(dòng)活動(dòng)E9和76個(gè)t后

啟動(dòng)E5,然后預(yù)置20個(gè)1后轉(zhuǎn)到目。

E4.［讓人出入］假如Elevator不空且有人的011lFloor=Floor,則按進(jìn)入的倒

序每隔25個(gè)t讓這類人馬上轉(zhuǎn)到他們的動(dòng)作M6oElevator中不再有要離開的人

時(shí)，假如Queue［Floor］不空，則以25個(gè)t的速度讓他們依次轉(zhuǎn)到MLQueue［Floor］

空時(shí)，置D1為()，D3手。，而且等候某個(gè)其他活動(dòng)的到來。

E5.［關(guān)門］每隔40個(gè)t檢查D1,直到是D1=O(若D1手個(gè)則仍有人出入〉。

置D3為0并預(yù)置電梯再20個(gè)t后啟動(dòng)活動(dòng)E6(再關(guān)門期間，若有人到來，則如

M2所述，門再次打開)。

E6.［打算移動(dòng)］置Caucar|Floor］為0,而且若State手GoingDown,則置CallUP

CFloor］%05若State手GoingUp,則置CaHDownCFloor］為0。調(diào)用Controler函

數(shù)。

假如State=Idle,則即使己經(jīng)執(zhí)行了Controler,也轉(zhuǎn)到El。否則，假如D2

手0,則取消電梯活動(dòng)E9。最終，假如State二GoingUp,則預(yù)置15個(gè)t后(電梯

加速〉轉(zhuǎn)到E7；假如State=GoingDown,則預(yù)置15個(gè)t后(電梯加速)轉(zhuǎn)到E8。

E7.［上升一層］置Floor加1并等候51個(gè)人假如現(xiàn)在CaucarfFloor)=1或

CanUp［Floor］=l,或者假如((Floor=l或CallDOWEl［Floor］=l)且

CalIUp［j］=CallDOWEl|j］=CallCar-0］=0對(duì)于全部j>Fk)or),則預(yù)置14個(gè)t后(減速)

轉(zhuǎn)到E2；否則重復(fù)E7。

E8.［下降一層］除了方向相反之外，與E7類似，但那里的51和14個(gè)3此

時(shí)分別改為61和23個(gè)t(電梯下降比上升慢)。

E9.［置不活動(dòng)指示器］置D2為0并調(diào)用Controler函數(shù)(E9是由E3預(yù)置的，

但幾乎總是被E6取消了訓(xùn)I。

(6)當(dāng)電梯須對(duì)下一個(gè)方向作出判定時(shí)，便在若干臨界時(shí)刻調(diào)用Controler函

數(shù)。該

函數(shù)有以下要點(diǎn)：

CL［須要推斷?］若State手Idle,則返回。

C2.［應(yīng)當(dāng)開門?］假如電梯處于E1且CallUpfl］,CallDown⑴或Caucar⑴非0,

則

預(yù)置20個(gè)t后啟動(dòng)E3,并返回。

C3.［有按鈕按下?］找最小的j手Floor,使得CallUplj］,CallDOWEl⑴或

Caucarfj］非0,并轉(zhuǎn)到C4。但假如不存在這樣的j,那么，假如Controler正為

E6所調(diào)用，則置j為1,否則返回。

C4.［置State］假如Floor>j,則置State為GoingDOWEl；假如Floorvj,則置

State為

GoingUpo

C5.［電梯靜止?］假如電梯處于El而且j手1,則預(yù)置20個(gè)t后啟動(dòng)E6,返

回。

(7)由上可見，關(guān)鍵是按時(shí)序管理系統(tǒng)中全部乘客和電梯的動(dòng)作設(shè)計(jì)合適的數(shù)

據(jù)結(jié)構(gòu)。

【選作內(nèi)容】

(1)增加電梯數(shù)量，模擬多梯系統(tǒng)。

(2)某高校的一座3()層住宅樓有三部自動(dòng)電梯，每梯最多載客15人。大樓

每層8戶，每戶平均3。5人，每天早晨平均每戶有3人必需在7時(shí)之前離開大

樓去上班或上學(xué)。模擬該電梯系統(tǒng)，并分析分別在一梯、二梯和三梯運(yùn)行狀況下,

下樓高峰期間各層的住戶應(yīng)提前多少時(shí)間候梯下樓?探討多梯運(yùn)行最佳策略。

174.迷宮問題

【問題描述】

以一個(gè)mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙，設(shè)

計(jì)一個(gè)程序，對(duì)隨意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通

路的結(jié)論。

【基本要求】

編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，

其中：(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對(duì)于下列

數(shù)據(jù)的迷宮,輸出的一條通路為z(l,1,1)，(1，2,2),(2,2,2),(3,2,3),

(3,1,2),-o

【測試數(shù)據(jù)】

迷宮的測試數(shù)據(jù)如下：左上角(1,1)為入口，右下角(8,9)為出口。

2345678

00100010

00100010

00001101

01110010

00010000

01000101

01111001

11000101

11000000

【實(shí)現(xiàn)提示】

計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從人口動(dòng)身，順著某一個(gè)方向

進(jìn)行探究，若能走通，則接著往前進(jìn)；否則沿著原路退回，換一個(gè)方向接著探究,

直至出口位置，求得一條通路。假如全部可能的通路都探究到而未能到達(dá)出口，

則所設(shè)定的迷宮沒有通路。

可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為(1,1),出口點(diǎn)的下

標(biāo)為(n,n)。為處理便利起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位

置，均可約定有東、南、西、北四個(gè)方向可通。

【選作內(nèi)容】

(1)編寫遞歸形式的算法，求得迷宮中全部可能的通路；

(2)以方陣形式輸出迷宮及其通路。

ch3串及其應(yīng)用

本實(shí)習(xí)單元的目的是熟識(shí)串類型的實(shí)現(xiàn)方法和文本模式匹配方法，熟識(shí)一般

文字處理軟件的設(shè)計(jì)方法,較困難問題的分解求精方法。本實(shí)習(xí)單元的難度較大,

在教學(xué)支配上可以敏捷駕馭完成此單元實(shí)習(xí)的時(shí)間。

編程技術(shù)訓(xùn)練要點(diǎn):并行的模式匹配技術(shù)⑶1)；字符填充技術(shù)(3.2,3.4);邏

輯/物理概念隔離技術(shù)(GetAWord,3.2);活區(qū)操作技術(shù)⑶3);不定長對(duì)象的成塊

存儲(chǔ)安排技術(shù)(3.3);吩咐識(shí)別與分析技術(shù)(3.3,3.4);串的動(dòng)態(tài)組織技術(shù)(3.4);

合理有效的錯(cuò)誤處理方法(3.4);程序語法結(jié)構(gòu)基本分析技術(shù)(3.5).

175.文學(xué)探討助手

【問題描述】

文學(xué)探討人員須要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試

寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱為〃文學(xué)探討助手〃。

【基本要求】

英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯合合要一次輸入完畢,即統(tǒng)計(jì)

工作必需在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)

次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。

【測試數(shù)據(jù)】

以你的c源程序模擬英文小說,c語言的保留字集作為待統(tǒng)計(jì)的詞匯合。

【實(shí)現(xiàn)提示】

約定小說中的詞匯一律不跨行。這樣,每讀入一行,就統(tǒng)計(jì)每個(gè)詞在這行中的

出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次,

不必存多個(gè)相同的行號(hào)。

假如讀者希望達(dá)到選做部分⑴和⑵所提出的要求,則首先應(yīng)把KMP算法改

寫成如下的等價(jià)形式,再將它推廣到多個(gè)模式的情形.

i=l;j=l;

while(i!=s.curlen+l&&j!=t.curlerl+1)

(

while(j!=0&&s.ch[i]!=t.ch[j])

j=next[j];//j==0或s.ch[i]==t.ch[j]

j++；i++；〃每次進(jìn)入循環(huán)體，i只增加一次

)

【選作內(nèi)容】

⑴模式匹配要基于KMP克法。

(2)整個(gè)統(tǒng)計(jì)過程中只對(duì)小說文字掃描一遍以提高效率。

(3)假設(shè)小說中的每個(gè)單詞或者從行首起先,或者前置一個(gè)空格符。利用單詞

匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。

(4)推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行(提示:定義

操作GetAChar)。

176.文本格式化

【問題描述】

輸入文件中含有待格式化(或稱為待排版》的文本，它由多行的文字組成，

例如一篇英文文章。每一行由一系列被一個(gè)或多個(gè)空格符所隔開的字①組成，

任何完整的字都沒有被分割在兩行(每行最終一個(gè)字與下一行的第一個(gè)字之間

在邏輯上應(yīng)當(dāng)由空格分開)，每行字符數(shù)不超過80。除了上述文本類字符之外，

還存在著起限制作用的字符:符號(hào)〃礦指示它后面的正文在格式化時(shí)應(yīng)另起一段

排放，即空一行,并在段首縮入8個(gè)字符位置。〃/自成一個(gè)字。

一個(gè)文本格式化程序可以處理上述輸入文件,依據(jù)用戶指定的版面規(guī)格重

排版而z實(shí)現(xiàn)頁內(nèi)調(diào)整、分段、分頁等文本處理功能，排版結(jié)果存入輸出文本文

件中。

試寫一個(gè)這樣的程序。

【基本要求】

(1)輸出文件中字與字之間只留一個(gè)空格符,即實(shí)現(xiàn)多余空格符的壓縮。

⑵在輸出文件中，任何完整的字仍不能分割在兩行,行尾不齊沒關(guān)系，但行

首要對(duì)齊(即左對(duì)齊)。

(3)假如所要求的每頁頁底所空行數(shù)不少于3,則將頁號(hào)印在頁底空行中第

2行的中間位置上，否則不印。

(4)版面要求的參數(shù)要包含：

頁長(PageLength)一一每頁內(nèi)文字(不計(jì)頁號(hào))的行數(shù)。

頁寬(PageWedth)每行內(nèi)文字所占最大字符數(shù)。

左空白(LeftMargin)每行文字前的固定空格數(shù)。

頭長(HeadingLength)每頁頁頂所空行數(shù)。

腳長(FootingLength)一—每頁頁底所空行數(shù)(含頁號(hào)行)。

起始頁號(hào)(StartingPageNumber)首頁的頁號(hào)。

【測試數(shù)據(jù)】

略。留意在標(biāo)點(diǎn)之后加上空格符。

【實(shí)現(xiàn)提示】

可以設(shè):左空白數(shù)X2+頁寬＜=160,即行印機(jī)最大行寬,從而只要設(shè)置這樣大

的一個(gè)行緩沖區(qū)就足夠了，每加工完一行,就輸出一行。

假如輸入文件和輸出文件不是由程序規(guī)定死,而是可由用戶指定,則有兩種

做法:一是像其他參量一樣，將文件名交互地讀入字符串變量中;更好的方式是

讓用戶通過吩咐行指定,具體做法依機(jī)器的操作系統(tǒng)而定。

應(yīng)當(dāng)首先實(shí)現(xiàn)GetAWord(w)這一操作，把諸如行尾處理、文件尾處理、多余

空格符壓縮等一系列〃低級(jí)〃事務(wù)留給它處理，使系統(tǒng)的核心部分集中應(yīng)付排版

要求。

每個(gè)參數(shù)都可以實(shí)現(xiàn)缺省值②設(shè)置。上述排版參數(shù)的缺省值可以分別取

56,60,10,5,5和1。

【選作內(nèi)容】

(1)輸入文件名和輸出文件名要由用戶指定。

(2)允許用戶指定是否右對(duì)齊,即增加一個(gè)參量〃右對(duì)齊否

(Rightjustifying),缺省值可設(shè)為〃y〃(yes)。右對(duì)齊指每行最終一個(gè)字的字尾

要對(duì)齊，多余的空格要?jiǎng)蚍Q分布在本行中各字之間。

(3)實(shí)現(xiàn)字符填充Icharacterstuffing)技術(shù)?！ˊ〃作為分段限制符之后，限

制了原文中不能有這樣的字?，F(xiàn)在去掉這一限制:假如原文中有這樣的字，改用

兩個(gè)〃@〃并列起來表示一個(gè)〃@〃字。當(dāng)然，假如原文中此符號(hào)夾在字中,就不必

特別處理了。

(4)允許用戶自動(dòng)按多欄印出一頁。

177.簡潔行編輯程序

【問題描述】

文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文

件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行

編輯程序。

被編輯的文本文件可能很大,全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法

既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文

件的一段放在內(nèi)存，稱為活區(qū)。試依據(jù)這種方法實(shí)現(xiàn)一個(gè)簡潔的行編輯程序。設(shè)

文件每行不超過320個(gè)字符,很少超過80個(gè)字符。

【基本要求】

實(shí)現(xiàn)以下4條基本編輯吩咐：

(1)行插入。格式:i〈行號(hào)＞＜回車〉＜文本〉.〈回車)

將〈文本)插入活區(qū)中第〈行號(hào)＞行之后。

(2)行刪除。格式:水行號(hào)1＞[＜空格X行號(hào)2＞"回車》

刪除活區(qū)中第〈行號(hào)1＞行(到第〈行號(hào)2》行)。例如：〃diO〃和〃dl014〃。

(3)活區(qū)切換。格式水回車》

將活區(qū)寫入輸出文件,并從輸入文件中讀入下一段，作為新的活區(qū)。

(4)活區(qū)顯示。格式:p＜回車＞

逐頁地(每頁20行)顯示活區(qū)內(nèi)容，每顯示一頁之后請(qǐng)用戶確定是否

接著顯示以后備頁(假如存在)。印出的每一行要前置行號(hào)和一個(gè)空格符，

行號(hào)固定占4位,增量為1。

各條吩咐中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入吩咐

的行號(hào)可以等于活區(qū)第一行行號(hào)減1,表示插入當(dāng)前屏幕中第一行之前，

否則吩咐參數(shù)非法。

【測試數(shù)據(jù)】

自行設(shè)定，留意測試將活區(qū)刪空等特別狀況。

【實(shí)現(xiàn)提示】

(1)設(shè)活區(qū)的大小用行數(shù)ActivcMULcn(可設(shè)為100)來描述?？紤]到文本文件

行長通常為正態(tài)分布，且峰值在60到70之間，用320XActiveMULen大小的字符數(shù)

組實(shí)現(xiàn)存儲(chǔ)將造成大量奢侈。可以以標(biāo)準(zhǔn)行塊為單位為各行安排存儲(chǔ),每個(gè)標(biāo)準(zhǔn)

行塊可含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài)鏈表連接起

來。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特別的ASCII字符(如(012)8)標(biāo)

識(shí)。此外，還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的依次下推。

(2)初始化函數(shù)包括:請(qǐng)用戶供應(yīng)輸入文件名(空串表示無輸入文件)和輸出

文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過

ActiveMULen-LX的值可以自定，例如20。

(3)在執(zhí)行行插入吩咐的過程中，每接收到一行時(shí)都要檢查活區(qū)大小是否已

達(dá)ActiveMaxLen。假如是，則為了在插入這一行之后仍保持活區(qū)大小不超過

ActiveMaxLen應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一夕亍輸出到輸出文件中；若插入

點(diǎn)為第一行之前,則只得將新插入的這一行輸出。

(4)若輸入文件尚天讀完，活區(qū)切換吩咐可將原活區(qū)中最終幾行留在活區(qū)頂

部，以保持閱讀連續(xù)性:否則，它意味著結(jié)束編輯或起先編輯另一個(gè)文件。

(5)可令前三條吩咐執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。

【選作內(nèi)容】

(1)對(duì)于吩咐格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。

(2)加入更困難的編輯操作,如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配

等，格式可以為S＜行號(hào)〉@＜串1〉@＜串2》＜回車＞和水串〉＜回車＞。

178,串基本操作的演示

【問題描述】

假如語言沒有把串作為一個(gè)預(yù)先定義好的基本類型對(duì)待，又須要用該語言

寫一個(gè)涉及串操作的軟件系統(tǒng)時(shí)，用戶必需自己實(shí)現(xiàn)串類型。試實(shí)現(xiàn)串類型,并

寫一個(gè)串的基本操作的演示系統(tǒng)。

【基本要求】

在教科書節(jié)用堆安排存儲(chǔ)表示實(shí)現(xiàn)HString串類型的最小操作子集的基礎(chǔ)

上，實(shí)現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不運(yùn)用C語言本身供應(yīng)的串函數(shù))。參

數(shù)合法性檢查必需嚴(yán)格。

利用上述基本操作函數(shù)構(gòu)造以下系統(tǒng):它是一個(gè)吩咐說明程序，循環(huán)往復(fù)地

處理用戶鍵入的每一條吩咐,直至終止程序的吩咐為止。吩咐定義如下：

(D賦值。格式：A＜串標(biāo)識(shí)〉〈回車)

用〈串標(biāo)識(shí)》所表示的串的值建立新串，并顯示新串的內(nèi)部名和串值。例:A

‘Hi!'

(2)判相等。格式：E＜串標(biāo)識(shí)1＞〈串標(biāo)識(shí)2＞〈回車)

若兩串相等，則顯示“EQUAL”,否則顯示〃UNEQUAL”。

(3)聯(lián)接。格式:C〈串標(biāo)識(shí)1＞〈串標(biāo)識(shí)2＞〈回車)

將兩串拼接產(chǎn)生結(jié)果串，它的內(nèi)部名和串值都顯示出來。

(4)求長度。格式:L〈串標(biāo)識(shí)〉〈回車》

顯示串的長度。

(5)求子串。格式:S＜串標(biāo)識(shí)》+＜數(shù)1＞+＜數(shù)2)＜回車》

假如參數(shù)合法,則顯示子串的內(nèi)部名和串值?！磾?shù))不帶正負(fù)號(hào)。

(6)子串定位。格式:1〈串標(biāo)識(shí)1》〈串標(biāo)識(shí)2)〈回車＞

顯示其次個(gè)串在第一個(gè)串中首次出現(xiàn)時(shí)的起始位置。

(7)串替換。格式：R＜串標(biāo)識(shí)1＞〈串標(biāo)識(shí)2》〈串標(biāo)識(shí)3＞〈回車》

將第一個(gè)串中全部出現(xiàn)的其次個(gè)串用第三個(gè)串替換,顯示結(jié)果串的內(nèi)部名

和串值，原串不變。

(8)顯示。格式:P〈回車)

顯示全部在系統(tǒng)中被保持的串的內(nèi)部名和串值的比照表。

(9)刪除v格式:D＜內(nèi)部名〉＜回車)

刪除該內(nèi)部名對(duì)應(yīng)的串，即賦值的逆操作。

(10)退出。格式:Q〈回車》

結(jié)束程序的運(yùn)行。

在上述吩咐中，假如一個(gè)自變量是串，則應(yīng)首先建立它?；静僮骱瘮?shù)的結(jié)

果(即函數(shù)值)假如是一個(gè)串，則應(yīng)在尚未安排的區(qū)域內(nèi)新辟空間存放。

【測試數(shù)據(jù)】

自定。但要包括以下幾組：

(1)E…y回車〉，應(yīng)顯示“EQUAL”。

(2)E'abc'匕bcd'c回車)，應(yīng)顯示“UNEQUAL”。

(3)C一一＜回車〉，應(yīng)顯示"。

(4)1〈回車＞，應(yīng)報(bào)告:參數(shù)非法。

(5)R匕aa-aa'b〈回車＞，應(yīng)顯示‘ba'

(6)R'aaabc…a''aab'＜回車)，應(yīng)顯示'aabaabaabbc'。

(7)RtFaaaaaaaa,4aaaa5'ab',〈回車＞，應(yīng)顯示‘a(chǎn)bab'。

【實(shí)現(xiàn)提示】

【選作內(nèi)容】

(1)串頭表改用單鏈表實(shí)現(xiàn)。

(2)對(duì)吩咐的格式(即語法)作嚴(yán)格檢查，使系統(tǒng)既能處理正確的吩咐,也能

處理錯(cuò)誤的吩咐。留意，語義檢查(如某內(nèi)部名對(duì)應(yīng)的串已被刪除而無定義等)

和基本操作參數(shù)合法性檢查仍應(yīng)留給基本操作去做。

(3)支持串名。將串名(可設(shè)不超過6個(gè)字符)存于串頭表中。吩咐(1)(3)(5)

要增加吩咐參數(shù)〈結(jié)果串名〉;吩咐(7)中的〈串標(biāo)識(shí)1》改為〈串名)，并用此名作

為結(jié)果串名，刪除原被替串標(biāo)識(shí)，用〈串名＞代替〈串標(biāo)識(shí)＞定義和吩咐說明中的內(nèi)

部名。每個(gè)吩咐執(zhí)行完畢時(shí)馬上自動(dòng)刪除無名串，

179.程序分析

【問題描述】

讀入一個(gè)c程序,統(tǒng)計(jì)程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個(gè)數(shù)和平

均行數(shù),并利用統(tǒng)計(jì)信息分析評(píng)價(jià)該程序的風(fēng)格。

【基本要求】

(1)把c程序文件按字符依次讀入源程序；

(2)邊讀入程序,邊識(shí)別統(tǒng)計(jì)代碼行、注釋行和空行，同時(shí)還要識(shí)別函數(shù)的

起先和結(jié)束，以便統(tǒng)計(jì)其個(gè)數(shù)和平均行數(shù)。

(3)程序的風(fēng)格評(píng)價(jià)分為代碼、注釋和空行三個(gè)方面。每個(gè)方面分為A,B,C

和D四個(gè)等級(jí)，等級(jí)的劃分標(biāo)準(zhǔn)是：

A級(jí)B級(jí)C級(jí)D級(jí)

代碼(函數(shù)平均長度)10~15行8~9或16~2。行5~7或或~24行<5或>24行

注群(占總行數(shù)比率)15~25%10~14或26~30%5~9或31~35%<5%或>35%

空行(占總行數(shù)比率)15^25%10~。或26~30%5"9或3廣35%<5%或>35$

【測試數(shù)據(jù)】

先對(duì)較小的程序進(jìn)行分析b當(dāng)你的程序能正確運(yùn)行時(shí),對(duì)你的程序本身進(jìn)行

分析。

【實(shí)現(xiàn)提示】

為了實(shí)現(xiàn)的便利，可作以下約定：

(1)頭兩個(gè)字符是FFF的行稱為注釋行(該行不含語句)。除了空行和注釋

行外,其余均為代碼行:包括類型定義、變量定義和函數(shù)頭)。

(2)每個(gè)函數(shù)代碼行數(shù)(除去空行和注釋行)禰為該函數(shù)的長度。

(3)每行最多只有一個(gè)〃{〃、〃}〃、“switch”和〃struct〃(便于識(shí)別函數(shù)的

結(jié)束行)。

【選作內(nèi)容】

(1)報(bào)告函數(shù)的平均長度。

(2)找出最長函數(shù)及其在程序中的位置。

(3)允許函數(shù)的俄套定義，報(bào)告最大的函數(shù)俄套深度。

ch4數(shù)組和廣義表

本實(shí)習(xí)單元是作為從線性結(jié)構(gòu)到非線性結(jié)構(gòu)的過渡來支配的。數(shù)組和廣義表

可以看成其元素本身也是自身結(jié)構(gòu)(遞歸結(jié)構(gòu))的線性表。廣義表本質(zhì)上是一

種層次結(jié)構(gòu)，自頂向下識(shí)別并建立一個(gè)廣義表的操作，可視為某種樹的遍歷操

作:遍歷邏輯的〈或符號(hào)形式的)結(jié)構(gòu),訪問動(dòng)作是建立一個(gè)結(jié)點(diǎn)。稀疏矩陣的十

字鏈表存儲(chǔ)結(jié)構(gòu)也是圖的一種存儲(chǔ)結(jié)構(gòu)。由此可見，這個(gè)實(shí)習(xí)單元的訓(xùn)練具有承

上啟下的作用。希望讀者能深化探討數(shù)組的存儲(chǔ)表示和實(shí)現(xiàn)技術(shù),熟識(shí)廣義表的

存儲(chǔ)結(jié)構(gòu)的特性。

編程技術(shù)訓(xùn)練要點(diǎn):稀疏矩陣的表示方法及其運(yùn)算的實(shí)現(xiàn)(4.1〉；共享數(shù)據(jù)的

存儲(chǔ)表示方法(4.2);形式系統(tǒng)的自底向上和自頂向下識(shí)別技術(shù)(4.3〉；遞歸算

法的設(shè)計(jì)方法(4.3);表達(dá)式求值技術(shù)(4.4)。

180.稀疏矩陣運(yùn)算器

【問題描述】

稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用〃稀疏〃特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)

算可以大大節(jié)約存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算

的運(yùn)算器。

【基本要求】

以〃帶行邏輯鏈接信息〃的三元組依次表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、

相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采納三元組表示，而運(yùn)算結(jié)果的矩陣

則以通常的陣列形式列出。

【測試數(shù)據(jù)】

【實(shí)現(xiàn)提示】

1.首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要

求作

的運(yùn)算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20o

2.程序可以對(duì)三元組的輸入依次加以限制，例如，按行優(yōu)先。留意探討教科

書

節(jié)中的算法，以便提高計(jì)算效率。

3.在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)當(dāng)另生成，乘積

矩陣也可用二維數(shù)組存放。

【選作內(nèi)容】

1.按教科書節(jié)中的描述方法，以十字鏈表表示稀疏矩陣。

2.增加矩陣求逆的運(yùn)算，包括不行求逆的狀況。在求逆之前，先將稀疏

矩陣的內(nèi)部表示改為十字鏈表。

181.多維數(shù)組

【問題描述】

設(shè)計(jì)并模擬實(shí)現(xiàn)整型多維數(shù)組類型。

[基本要求】

盡管c等程序設(shè)計(jì)語言已經(jīng)供應(yīng)了多維數(shù)組，但在某些狀況下，定義用

戶所需的多維數(shù)組很有用的。通過設(shè)計(jì)并模擬實(shí)現(xiàn)多維數(shù)組類型，可以深刻理

解和駕馭多維數(shù)組。整型多維數(shù)組應(yīng)具有以下基本功能：

(1)定義整型多維數(shù)組類型，各維的下標(biāo)是隨意整數(shù)起先的連續(xù)整數(shù)；

(2)下標(biāo)變量賦值，執(zhí)行下標(biāo)范圍檢查；

(3〉同類型數(shù)組賦值；

(4)子數(shù)組賦值,例如,a[l..n]=a

[2..n+l];a[2..4][3..5]=b[l..3][2..4];

(5)確定數(shù)組的大小。

【測試數(shù)據(jù)】

由讀者指定。

【實(shí)現(xiàn)提示】

各基本功能可以分別用函數(shù)模擬實(shí)現(xiàn)，應(yīng)細(xì)致考慮函數(shù)參數(shù)的形式和設(shè)

置。定義整型多維數(shù)組類型時(shí)，其類型信息可以存儲(chǔ)在如下定義的類型的記

錄中：

#defineMaxDim5

Typedefstruct

intdim,

BoundPtrlower,

Upper;

ConstPtrconstants;

)NArray,*NarrayPtr;

整型多維數(shù)組變量的存儲(chǔ)結(jié)構(gòu)類型可定義為：

Typedefstruct(

ElemType*elem;

Intnum;

NArrayTypeTypeRecord;

}NArrayType;

【選作內(nèi)容】

(1)各維的下標(biāo)是隨意字符起先的連續(xù)字符。

(2)數(shù)組初始化。

(3)可修改數(shù)組的下標(biāo)范圍。

182,識(shí)別廣義表的頭或尾

【問題描述】

寫一個(gè)程序,建立廣義表的存儲(chǔ)結(jié)構(gòu),演示在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的廣義表求

頭/求尾操作序列的結(jié)果。

【基本要求】

(1)設(shè)一個(gè)廣義表允許分多行輸入,其中可以隨意地輸入空格符,原子是不

限長的僅由字母或數(shù)字組成的串。

(2)廣義表采納加教科書中圖5.8所示結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)，試按表頭和表尾的

分解方法編寫建立廣義表存儲(chǔ)結(jié)構(gòu)的算法。

(3)對(duì)已建立存儲(chǔ)結(jié)構(gòu)的廣義表施行操作，操作序列為一個(gè)僅由〃t〃或〃h〃組

成的串，它可以是空串(此時(shí)印出整個(gè)廣義表)，自左至右施行各操作,再以符號(hào)形

式顯示結(jié)果。

【測試數(shù)據(jù)】

【實(shí)現(xiàn)提示】

(1)廣義表串可以利用C語言中的串類型或者利用實(shí)習(xí)三中已實(shí)現(xiàn)的串類

型表示。

(2)輸入廣義表時(shí)靠括號(hào)匹配推斷結(jié)束,濾掉空格符之后，存于一個(gè)串變量

中。

(3)為了實(shí)現(xiàn)指定的算法，應(yīng)在上述廣義表串結(jié)構(gòu)上定義以下4個(gè)操作：

Test(s):當(dāng)S分別為空串、原子串和其他形式串時(shí),分別返回'N',E

和'0'(代表Null,Element和Other)。

hsub(s,h):s表示一個(gè)由逗號(hào)隔開的廣義表和原子的混合序列，h為變量參

數(shù),返回時(shí)為表示序列第一項(xiàng)的字符串。假如s為空串，則h也賦為空串。

tsub(s,t):s的定義同hsub操作；t為變量參數(shù)，返回時(shí)取從S中除去第一項(xiàng)

(及其之后的逗號(hào)，假如存在的話)之后的子串。

strip(s,r)：s的定義同hsub操作；r為變量參數(shù)。假如串S以〃(〃開頭和

以〃)〃結(jié)束，則返回時(shí)取除去這對(duì)括號(hào)后的子串，否則取空串。

(4)在廣義表的輸出形式中，可以適當(dāng)添加空格符，使得結(jié)果更美觀。

【選作內(nèi)容】

(1)將hsub和tsub這兩個(gè)操作合為一個(gè)(用變量參數(shù)h和t分別返回各自的結(jié)

果)，以便提高執(zhí)行效率。

(2)設(shè)原了為單個(gè)字地廣義表的建立算法改用邊讀入邊建立的白底向上識(shí)

別策略實(shí)現(xiàn)，廣義表符號(hào)串不整體地緩沖。

183.簡潔LISP算術(shù)表達(dá)式計(jì)算器

【問題描述】

設(shè)計(jì)一個(gè)簡潔的LISP算術(shù)表達(dá)式計(jì)算器。

簡潔LISP算術(shù)表達(dá)式(以下簡稱表式)定義如下：

(1)一個(gè)0..9的整數(shù);或者

(2)(運(yùn)算符表達(dá)式表達(dá)式)

例如,6,(+45),(+(+25)8)都是表達(dá)式，其值分別為6,9和15。

【基本要求】

實(shí)現(xiàn)LISP加法表達(dá)式的求值。

【測試數(shù)據(jù)】

6,(+45),(+(+25)8),(+2(+58)),(+(+(+12)(-34))(+(+56)(+78)))

【實(shí)現(xiàn)提示】

寫一個(gè)遞歸函數(shù)：

intEvaluate(FILE*CharFile)

字符文件CharFile的每行是一個(gè)如上定義的表達(dá)式。每讀入CharFile的一行,

求出并返回表達(dá)式的值。

可以設(shè)計(jì)以下協(xié)助函數(shù)

statusisNumber(charReadlnChar);//視ReadTnchar是否是數(shù)字而返回

TRUE或FALSE<>

intTurnToTnteger(charTntChar);//將字符'O'..0轉(zhuǎn)換為整數(shù)

0..9

【選做內(nèi)容】

(1)標(biāo)準(zhǔn)整數(shù)類型的LISP加法表達(dá)式的求值。

(2)標(biāo)準(zhǔn)整數(shù)類型的LISP四則運(yùn)算表達(dá)式的求值。

(3)LISP算術(shù)表達(dá)式的語法檢查。

ch5樹、圖及其應(yīng)用

184.重言式判別

【問題描述】

一個(gè)邏輯表達(dá)式假如對(duì)于其變?cè)娜我环N取值都為真，則稱為重言式;反之,

假如對(duì)于其變?cè)娜我环N取值都為假，則稱為沖突式；然而，更多的狀況下，既

非重言式，也非沖突式。試寫一個(gè)程序，通過真值表判別一個(gè)邏輯表達(dá)式屬于上

述哪一類。

［基本要求］

(I)邏輯表達(dá)式從終端輸入，長度不超過一行。邏輯運(yùn)算符包括T，和

分別表示或、與利非，運(yùn)算優(yōu)先程度遞增，但可由括號(hào)變更，即括號(hào)內(nèi)的

運(yùn)算優(yōu)先。邏輯變?cè)獮榇髮懽帜?。表達(dá)式中任何地方都可以含有多個(gè)空格符。

(2)若是重言式或沖突式，可以只顯示"Trueforever",或"Falseforever",否

則顯示''Satisfactible'1以及變量名序列，與用戶交互。若用戶對(duì)表達(dá)式中變?cè)?/p>

定一組值，程序就求出并顯示邏輯表達(dá)式的值。

【測試數(shù)據(jù)】

⑴(A|?A)&(BbB)

⑵(A&~A)&C

(3)A|B|C|D舊卜A

(4)A&B&C&?B

(5)(A|B)&(AHB)

(6)A&-