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

161.運動會分數(shù)統(tǒng)計

【問題描述】

參與運動會的n個學校編號為1?必競賽分成/個男子項目和“個女子項目，

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

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

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

【基本要求】

1）可以輸入各個項目的前三名或前五名的成果；

2）能統(tǒng)計各學?？偡郑?/p>

3）可以按學校編號或名稱、學?？偡帧⒛信畧F體總分排序輸出；

4）可以按學校編號查詢學校某個項目的狀況；可以按項目編號查詢?nèi)〉们?/p>

三或前五名的學校。

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

6）規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱

輸出形式：有中文提示，各學校分數(shù)為整型。

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

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

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

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

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

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

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

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

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

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

【實現(xiàn)提示】

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

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

運動員姓名、校名（和成績）。

【選作內(nèi)容】

允許用戶指定某項目實行其他名次取法。

162.約瑟夫環(huán)

【問題描述】

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

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

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

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

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

出出列依次。

【基本要求】

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

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

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

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

【實現(xiàn)提示】

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

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

界限。

【選作內(nèi)容】

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

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

【問題描述】

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

【基本要求】

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

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

慣，每四位一組，組間用逗號隔開。

【測試數(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

【實現(xiàn)提示】

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

會溢出。但若這樣存放，即相當于按32768進制數(shù)存放，在十進制數(shù)與32768進

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

過9999的非負整數(shù)，整個鏈表表示為萬進制數(shù)。

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

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

【選作內(nèi)容】

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

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

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

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

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

165.一元稀疏多項式計算器

【問題描述】

設(shè)計一個一元稀疏多項式簡潔計算器。

【基本要求】

一元稀疏多項式簡潔計算器的基本功能是：

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

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

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

序排列；

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

(4)多項式Q和〃相減，建立多項式。功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ù)中的前后兩個多項式

【實現(xiàn)提示】

用帶表頭結(jié)點的單鏈表存儲多項式。

【選作內(nèi)容】

(1)計算多項式在x處的值。

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

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

abo

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

出形式為

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

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

的輸出形式為一x3。

(5)計算器的仿真界。

166.池塘夜降彩色雨

【問題描述】

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

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

【基本要求】

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

圈等，都是隨機確定的；

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

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

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

【實現(xiàn)提示】

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

須要一

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

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

水波應(yīng)是

由里至外漸漸擴大和消逝。

(3)每個雨點發(fā)生時，生成其記錄，并預(yù)置下一個雨點的發(fā)生時間。

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

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

【選作內(nèi)容】

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

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

(3)增加雨點密度的變更：時而“和風細雨”，時而“暴風驟雨”。

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

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

僅僅相識到棧和隊列是兩種特別的線性表是遠遠不夠的，本次實習的目的在

于使讀者深化了解錢和隊列的特性，以便在實際問題背景下敏捷運用他們；同時

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

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

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

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

167.停車場管理

［問題描述］

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

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

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

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

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

進入車場，每輛停放在車場的車在它離開停車場時必需按它停留的時間長短交納費用。試為

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

［測試數(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ù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車

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

束。

［基本要求］

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

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

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

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

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

［實現(xiàn)提示］

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

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

據(jù)項：汽車的牌照號碼和進入停車場的時刻。

［選作內(nèi)容］

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

（2）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和

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

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

排到隊尾。

（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思索如何修改

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

168.魔王語言說明

【問題描述】

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

懂，但他的語言是可以逐步說明成人能聽懂的語言，因為他的語言是由以下兩種

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

⑴一夕也…凡

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

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

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

【基本要求】

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

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

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

（1）BiiAdA

（2）Asae

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

B(ehnxgz)B說明成tsaedsaeezegexenehetsaedsae

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

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

tdSaCZgXnh

天地上一只鵝追趕下蛋恨

【實現(xiàn)提示】

將魔王的語言自右至左進棧，總是處理棧頂寧符。若是開括號，則逐一出棧,

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

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

【選作內(nèi)容】

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

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

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

169.馬踏棋盤

【問題描述】

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

【基本要求】

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

進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。編制非遞歸

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

入一個8x8的方陣，輸出之。

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

【問題描述】

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

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

［基本要求］

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

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

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

更過程。

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

【問題描述】

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

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

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

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

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

的客戶，則依次檢查和處理（假如可能）其次個隊列中的客戶，對能滿意的申請者

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

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

待之前的數(shù)額，或者本次已將其次個隊列檢查或處理了一遍，就停止檢查（因為

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

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

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

的平均時間。

［基本要求］

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

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

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

模擬參

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

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

客戶的交易時間很短。

【實現(xiàn)提示】

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

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

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

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

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

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

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

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

【選作內(nèi)容】

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

CustNodepoolfMAX］；

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

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

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

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

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

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

組織。

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

【問題描述】

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

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

【基本要求】

（1）每條航線所涉及的信息有：終點站名、航班號、飛機號、飛行周日（星期

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

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

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

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

中；

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

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

③承辦訂票業(yè)務(wù)：依據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額

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

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

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

然后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿

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

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

由讀者自行指定。

【實現(xiàn)提示】

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

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

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

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

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

員名單域為指向乘員名單鏈表的頭指針，等候替補的客戶名單域為分別指向隊頭

和隊尾的指針。

【選作內(nèi)容】

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

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

173.電梯模擬

【問題描述】

設(shè)計一個電梯模擬系統(tǒng)。這是一個離散的模擬程序，因為電梯系統(tǒng)是乘客和

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

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

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

定要發(fā)生的下一個時刻。

［基本要求］

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

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

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

（2）乘客可隨機地進出于任何層。對每個人來說，他有一個能容忍的最長等

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

（3）模擬時鐘從0起先，時間單位為0.1秒。人和電梯的各種動作均要耗費

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

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

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

每個人進出電梯均須要25h

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

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

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

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

【實現(xiàn)提示】

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

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

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

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

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

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

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

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

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

的變量有：

Floor——電梯的當前位置（樓層）；

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

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

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

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

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

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

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

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

InFloor該人進入哪層樓；

OlltFloor他要去哪層樓；

GiveupTime也能容忍的等候時間；

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

刻。

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

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

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

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

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

GiveupTime個t之后，他若仍在隊列中將實施動作M4。

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

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

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

校中。置CancarfOlltRoor］為1。

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

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

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

或E60o

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

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

GoingDown(或GoingUp)還是Idle。

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

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

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

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

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

空時，置D1為()，D3手。，而且等候某個其他活動的到來。

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

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

M2所述，門再次打開)。

E6.［打算移動］置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,則取消電梯活動E9。最終，假如State二GoingUp,則預(yù)置15個t后(電梯

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

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

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

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

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

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

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

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

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

(6)當電梯須對下一個方向作出判定時，便在若干臨界時刻調(diào)用Controler函

數(shù)。該

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

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

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

則

預(yù)置20個t后啟動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個t后啟動E6,返

回。

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

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

【選作內(nèi)容】

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

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

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

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

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

174.迷宮問題

【問題描述】

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

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

路的結(jié)論。

【基本要求】

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

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

數(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

【實現(xiàn)提示】

計算機解迷宮通常用的是“窮舉求解”方法，即從人口動身，順著某一個方向

進行探究，若能走通，則接著往前進；否則沿著原路退回，換一個方向接著探究,

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

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

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

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

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

【選作內(nèi)容】

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

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

ch3串及其應(yīng)用

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

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

在教學支配上可以敏捷駕馭完成此單元實習的時間。

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

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

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

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

175.文學探討助手

【問題描述】

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

寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng),稱為〃文學探討助手〃。

【基本要求】

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

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

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

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

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

【實現(xiàn)提示】

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

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

不必存多個相同的行號。

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

寫成如下的等價形式,再將它推廣到多個模式的情形.

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++；〃每次進入循環(huán)體，i只增加一次

)

【選作內(nèi)容】

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

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

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

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

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

操作GetAChar)。

176.文本格式化

【問題描述】

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

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

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

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

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

排放，即空一行,并在段首縮入8個字符位置?！?自成一個字。

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

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

件中。

試寫一個這樣的程序。

【基本要求】

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

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

首要對齊(即左對齊)。

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

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

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

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

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

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

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

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

起始頁號(StartingPageNumber)首頁的頁號。

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

略。留意在標點之后加上空格符。

【實現(xiàn)提示】

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

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

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

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

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

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

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

要求。

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

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

【選作內(nèi)容】

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

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

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

要對齊，多余的空格要勻稱分布在本行中各字之間。

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

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

兩個〃@〃并列起來表示一個〃@〃字。當然，假如原文中此符號夾在字中,就不必

特別處理了。

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

177.簡潔行編輯程序

【問題描述】

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

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

編輯程序。

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

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

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

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

【基本要求】

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

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

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

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

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

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

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

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

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

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

行號固定占4位,增量為1。

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

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

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

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

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

【實現(xiàn)提示】

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

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

組實現(xiàn)存儲將造成大量奢侈?？梢砸詷藴市袎K為單位為各行安排存儲,每個標準

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

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

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

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

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

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

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

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

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

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

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

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

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

【選作內(nèi)容】

(1)對于吩咐格式非法等一切錯誤作嚴格檢查和適當處理。

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

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

178,串基本操作的演示

【問題描述】

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

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

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

【基本要求】

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

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

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

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

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

(D賦值。格式：A＜串標識〉〈回車)

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

‘Hi!'

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

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

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

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

(4)求長度。格式:L〈串標識〉〈回車》

顯示串的長度。

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

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

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

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

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

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

和串值，原串不變。

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

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

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

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

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

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

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

果(即函數(shù)值)假如是一個串，則應(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)報告:參數(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'。

【實現(xiàn)提示】

【選作內(nèi)容】

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

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

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

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

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

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

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

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

179.程序分析

【問題描述】

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

均行數(shù),并利用統(tǒng)計信息分析評價該程序的風格。

【基本要求】

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

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

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

(3)程序的風格評價分為代碼、注釋和空行三個方面。每個方面分為A,B,C

和D四個等級，等級的劃分標準是：

A級B級C級D級

代碼(函數(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~?；?6~30%5"9或3廣35%<5%或>35$

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

先對較小的程序進行分析b當你的程序能正確運行時,對你的程序本身進行

分析。

【實現(xiàn)提示】

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

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

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

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

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

結(jié)束行)。

【選作內(nèi)容】

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

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

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

ch4數(shù)組和廣義表

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

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

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

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

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

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

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

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

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

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

180.稀疏矩陣運算器

【問題描述】

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

算可以大大節(jié)約存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算

的運算器。

【基本要求】

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

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

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

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

【實現(xiàn)提示】

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

求作

的運算是否相匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過20o

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

書

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

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

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

【選作內(nèi)容】

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

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

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

181.多維數(shù)組

【問題描述】

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

[基本要求】

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

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

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

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

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

(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ù)】

由讀者指定。

【實現(xiàn)提示】

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

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

錄中：

#defineMaxDim5

Typedefstruct

intdim,

BoundPtrlower,

Upper;

ConstPtrconstants;

)NArray,*NarrayPtr;

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

Typedefstruct(

ElemType*elem;

Intnum;

NArrayTypeTypeRecord;

}NArrayType;

【選作內(nèi)容】

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

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

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

182,識別廣義表的頭或尾

【問題描述】

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

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

【基本要求】

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

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

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

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

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

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

式顯示結(jié)果。

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

【實現(xiàn)提示】

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

型表示。

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

中。

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

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

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

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

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

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

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

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

以〃)〃結(jié)束，則返回時取除去這對括號后的子串，否則取空串。

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

【選作內(nèi)容】

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

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

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

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

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

【問題描述】

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

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

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

(2)(運算符表達式表達式)

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

【基本要求】

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

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

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

【實現(xiàn)提示】

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

intEvaluate(FILE*CharFile)

字符文件CharFile的每行是一個如上定義的表達式。每讀入CharFile的一行,

求出并返回表達式的值。

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

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

TRUE或FALSE<>

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

0..9

【選做內(nèi)容】

(1)標準整數(shù)類型的LISP加法表達式的求值。

(2)標準整數(shù)類型的LISP四則運算表達式的求值。

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

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

184.重言式判別

【問題描述】

一個邏輯表達式假如對于其變元的任一種取值都為真，則稱為重言式;反之,

假如對于其變元的任一種取值都為假，則稱為沖突式；然而，更多的狀況下，既

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

述哪一類。

［基本要求］

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

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

運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以含有多個空格符。

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

則顯示''Satisfactible'1以及變量名序列，與用戶交互。若用戶對表達式中變元取

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

【測試數(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&-