數(shù)據(jù)結(jié)構(gòu)課程研發(fā)設(shè)計(jì)任務(wù)書

1、161. 運(yùn)動會分?jǐn)?shù)統(tǒng)計(jì)【問題描述】參加運(yùn)動會的n個學(xué)校編號為1n。比賽分成m個男子項(xiàng)目和w個女子項(xiàng)目， 項(xiàng)目編號分別為1m和m+1m+wo由于各項(xiàng)目參加人數(shù)差別較大，有些項(xiàng)目取前 五名，得分順序?yàn)?，5，3，2，1；還有些項(xiàng)目只取前三名，得分順序?yàn)?，3，2。 寫一個統(tǒng)計(jì)程序產(chǎn)生各種成績單和得分報(bào)表。 矚慫潤厲釤瘞睞櫪廡賴?！净疽蟆?）可以輸入各個項(xiàng)目的前三名或前五名的成績；2）能統(tǒng)計(jì)各學(xué)?？偡郑?）可以按學(xué)校編號或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出；4）可以按學(xué)校編號查詢學(xué)校某個項(xiàng)目的情況；可以按項(xiàng)目編號查詢?nèi)〉们?三或前五名的學(xué)校。5）數(shù)據(jù)存入文件并能隨時查詢6）規(guī)定：輸入數(shù)據(jù)形式

2、和范圍：可以輸入學(xué)校的名稱，運(yùn)動項(xiàng)目的名稱 輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整型。界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相 關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動會的相關(guān)數(shù) 據(jù)要存儲在數(shù)據(jù)文件中。測試數(shù)據(jù)：【測試數(shù)據(jù)】要求使用 1、全部合法數(shù)據(jù)； 2、整體非法數(shù)據(jù)； 3、局部非法數(shù)據(jù)。進(jìn)行程 序測試，以保證程序的穩(wěn)定。例如，對于 n=4，m=3，w =2，編號為奇數(shù)的項(xiàng)目取前五名，編號為偶數(shù)的 項(xiàng)目取前三名，設(shè)計(jì)一組實(shí)例數(shù)據(jù)。 聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈。【實(shí)現(xiàn)提示】可以假設(shè)nw 20, m< 30, w< 20,姓名長度不超過

3、 20個字符。每個項(xiàng)目結(jié) 束時，將其編號、類型符 （區(qū)分取前五名還是前三名 ） 輸入，并按名次順序輸入 運(yùn)動員姓名、校名 （和成績）。殘騖樓諍錈瀨濟(jì)溆塹籟?！具x作內(nèi)容】 允許用戶指定某項(xiàng)目采取其他名次取法。162. 約瑟夫環(huán)【問題描述】約瑟夫（Joseph）問題的一種描述是：編號為 1, 2,，n的n個人按順 時針方向圍坐一 圈，每人持有一個密碼 （正整數(shù)）。一開始任選一個正整數(shù)作為 報(bào)數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報(bào)數(shù)，報(bào)到m時停止 報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個 人開始重新從 1報(bào)數(shù),如此下去,直至所有人全部出列為止。試設(shè)計(jì)一個程

4、序求 出出列順序。釅錒極額閉鎮(zhèn)檜豬訣錐?！净疽蟆?利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號?！緶y試數(shù)據(jù)】m 的初值為 20；n=7， 7 個人的密碼依次為： 3，1，7，2，4， 8， 4， 首 先 m 值為 6( 正確的出列順序應(yīng)為 6， 1，4，7，2，3，5) 。彈貿(mào)攝爾霽斃攬磚鹵廡?！緦?shí)現(xiàn)提示】程序運(yùn)行后， 首先要求用戶指定初始報(bào)數(shù)上限值， 然后讀取各人的密碼。 可 設(shè)n< 30。此題所用的循環(huán)鏈表中不需要“頭結(jié)點(diǎn)”，請注意空表和非空表的界限。 謀蕎摶篋飆鐸懟類蔣薔?！具x作內(nèi)容】 向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。164. 長整數(shù)四則運(yùn)算【問題描

5、述】 設(shè)計(jì)一個實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。【基本要求】 利用雙向循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲， 每個結(jié)點(diǎn)含一個整型變量。任何整型 變量的范 圍是 (215-l)(215-1) 。輸入和輸出形式：按中國對于長整數(shù)的表示習(xí) 慣，每四位一組，組間用逗號隔開。 廈礴懇蹣駢時盡繼價(jià)騷。【測試數(shù)據(jù)】(1) 0； 0； 應(yīng)輸出 "0" 。(2) 2345， 6789； 7654， 3211； 應(yīng)輸出 "1， 0000， 0000" 。(3) 9999， 9999；1， 0000， 0000， 0000； 應(yīng)輸出 "9999 ， 0000， 0001&

6、quot; 。 煢楨廣鰳鯡選塊網(wǎng)羈淚。(4) 1， 0001， 0001； 1， 0001， 0001； 應(yīng)輸出 "0" 。(5) 1， 0001， 0001； 1， 0001， 0000； 應(yīng)輸出 "1" 。(6) -9999， 9999， 9999； 9999， 9999， 9999；應(yīng)輸出 "1， 9999， 9999， 9998" 。 (7) 1， 0000， 9999， 9999；1； 應(yīng)輸出 "1 ， 0001， 0000， 0000 " 。鵝婭盡損鵪慘歷蘢鴛賴?！緦?shí)現(xiàn)提示】(1) 每個結(jié)點(diǎn)中可以存放的

7、最大整數(shù)為 215-1=32767， 才能保證兩數(shù)相加不會溢出。但若這樣存放，即相當(dāng)于按 32768進(jìn)制數(shù)存放，在十進(jìn)制數(shù)與 32768進(jìn) 制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制數(shù)。 籟叢媽羥為贍僨蟶練淨(jìng)。(2) 可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號代表長整數(shù)的符號。相加過程中不要破壞 兩個操作數(shù)鏈表。不能給長整數(shù)位數(shù)規(guī)定上限。 預(yù)頌圣鉉儐歲齦訝驊糴。 【選作內(nèi)容】(1) 實(shí)現(xiàn)長整數(shù)的四則運(yùn)算；(2) 實(shí)現(xiàn)長整數(shù)的乘方和階乘運(yùn)算；(3) 整型量范圍是一 (2 1) (2 1),其中，n是由程序讀人的參量。輸 入數(shù)據(jù)的分組方法可以另

8、行規(guī)定。165. 一兀稀疏多項(xiàng)式計(jì)算器【問題描述】設(shè)計(jì)一個一元稀疏多項(xiàng)式簡單計(jì)算器?！净疽蟆恳辉∈瓒囗?xiàng)式簡單計(jì)算器的基本功能是：(1) 輸入并建立多項(xiàng)式；(2) 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n,ci,e ,C2,e2,，cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù)，Ci和e,分別是第i項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降 序排列；滲釤嗆儼勻諤鱉調(diào)硯錦。(3) 多項(xiàng)式a和b相加，建立多項(xiàng)式a +b;(4) 多項(xiàng)式a和b相減，建立多項(xiàng)式a -b 。 【測試數(shù)據(jù)】8ii89119(1) (2x+5x - 3.1x ) + (7 - 5x+11x)=( 3.lx +11x+2x+7)鐃誅臥瀉噦圣騁貺頂廡。(2)

9、 (6x-3 x+4.4x2 1.2x9) (-6x-3+5.4x2 x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x)2345、/3425、(3) (1 +x + x +x +x +x )+(-x x )=(1+x+x +x )(x+x)+(-x x3)=0(5) (x+x100)+(x100 +x200)=(x+2x100+x200(6) (x+x 2+x3)+0=x+x 2+x3(7) 互換上述測試數(shù)據(jù)中的前后兩個多項(xiàng)式 【實(shí)現(xiàn)提示】用帶表頭結(jié)點(diǎn)的單鏈表存儲多項(xiàng)式。【選作內(nèi)容】(1) 計(jì)算多項(xiàng)式在x處的值。(2) 求多項(xiàng)式a的導(dǎo)函數(shù)a，。(3) 多項(xiàng)式a和b相乘，建立乘

10、積多項(xiàng)式ab。多項(xiàng)式的輸出形式為類數(shù)學(xué)表達(dá)式。例如，多項(xiàng)式-3x8+6x3 18的輸出形式為-3x 8 6x 3 -18，x15+( 8)x7 14的輸出形式為 x 15-8x 7-14。注意，數(shù) 值為1的非零次項(xiàng)的輸出形式中略去系數(shù)1,如項(xiàng)1x8的輸出形式為x8,項(xiàng)一1x3 的輸出形式為一X3。擁締鳳襪備訊顎輪爛薔。(5) 計(jì)算器的仿真界。166. 池塘夜降彩色雨【問題描述】設(shè)計(jì)一個程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點(diǎn)飄飄灑灑地 從天而降， 滴滴入水有聲，濺起圈圈微瀾。贓熱俁閫歲匱閶鄴鎵騷?！净疽蟆?1) 雨點(diǎn)的空中出現(xiàn)位置、降范過程的可見程度、入水位置、顏色、最大水 圈等，

11、都是隨機(jī)確定的；（2）多個雨點(diǎn)按照各自的隨機(jī)參數(shù)和存在狀態(tài)，同時演示在屏幕上?！緶y試數(shù)據(jù)】 適當(dāng)調(diào)整控制雨點(diǎn)密度、最大水圈和狀態(tài)變化的時間間隔等參數(shù)?！緦?shí)現(xiàn)提示】（1） 每個雨點(diǎn)的存在周期可分為三個階段： 從天而降、入水有聲和圈圈微瀾， 曲:*需要一 個記錄存儲其相關(guān)參數(shù)、當(dāng)前狀態(tài)和下一狀態(tài)的更新時刻。（2） 在圖形狀態(tài)編程。雨點(diǎn)下降的可見程度應(yīng)是斷斷續(xù)續(xù)、依稀可見；圈圈 水波應(yīng)是 由里至外逐漸擴(kuò)大和消失。（3）每個雨點(diǎn)發(fā)生時，生成其記錄，并預(yù)置下一個雨點(diǎn)的發(fā)生時間。（4）用一個適當(dāng)?shù)慕Y(jié)構(gòu)管理當(dāng)前存在的雨點(diǎn)，使系統(tǒng)能利用它按時更新每個 雨點(diǎn)的狀態(tài)，一旦有雨點(diǎn)的水圈全部消失，就從結(jié)構(gòu)中刪去。 壇

12、摶鄉(xiāng)囂懺蔞鍥鈴氈淚?！具x作內(nèi)容】（1） 增加“電閃雷鳴”景象。（2） 增加風(fēng)的效果，展現(xiàn)“風(fēng)雨飄搖”的情景。（3）增加雨點(diǎn)密度的變化：時而“和風(fēng)細(xì)雨”， 時而“暴風(fēng)驟雨”。（4） 將“池塘”改為“荷塘”，雨點(diǎn)滴在荷葉上的效果是濺起四散的水珠，響聲也不同 ch2 棧和隊(duì)列及其應(yīng)用僅僅認(rèn)識到棧和隊(duì)列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的， 本次實(shí)習(xí)的目的在 于使讀者深入了解錢和隊(duì)列的特性， 以便在實(shí)際問題背景下靈活運(yùn)用他們； 同時 還將鞏固對這兩種結(jié)構(gòu)的構(gòu)造方法的理解。 蠟變黲癟報(bào)倀鉉錨鈰贅。編程技術(shù)訓(xùn)練要點(diǎn)有：基本的 “任務(wù)書 “觀點(diǎn)及其典型用法 （見本實(shí)習(xí) 2。2）； 問題求解的狀態(tài)表示及其遞歸算法

13、（2.3，2.4和 2.9）；利用棧實(shí)現(xiàn)表達(dá)式求值的技 術(shù)（2.5）；事件驅(qū)動的模擬方法 （2.6 3.8）；以及動態(tài)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn) （2.6，2.7和 2.8）。 買鯛鴯譖曇膚遙閆擷凄。167. 停車場管理 問題描述 設(shè)停車場內(nèi)只有一個可停放 n 輛汽車的狹長通道， 且只有一個大門可供汽車進(jìn)出。 汽車 在停車場內(nèi)按車輛到達(dá)時間的先后順序， 依次由北向南排列 （大門在最南端， 最先到達(dá)的第 一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道 上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時， 在它之后開入的車輛必須先退出車場為它讓路，

14、 待該輛車開出大門外， 其它車輛再按原次序 進(jìn)入車場， 每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。 綾鏑鯛駕櫬鶘蹤韋轔糴。 測試數(shù)據(jù) 設(shè) n=2, 輸入數(shù)據(jù)為： （A'， 1， 5），（A'， 2， 10） ， （D'， 1， 15） ， （A'， 3， 20 ）， （A'， 4， 25），（ A'， 5， 30），（D'， 2， 35） ， （D'， 4， 40）， （ E'， 0， 0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車

15、牌照號碼及到達(dá)或離去的時刻，其中， A'表示到達(dá)；D'表示離去，E'表示輸入結(jié) 束。驅(qū)躓髏彥浹綏譎飴憂錦。基本要求以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬 管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。貓蠆驢繪燈鮒誅髏貺廡。實(shí)現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而

16、從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。 棧中每個元素表示一輛汽車， 包含兩個數(shù) 據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時刻。 鍬籟饗逕瑣筆襖鷗婭薔。選作內(nèi)容（1）兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和 1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于 3輛小汽車的占地面積。 構(gòu)氽頑 黌碩飩薺齦話騖。（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾。（4） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足

17、這種要求。168. 魔王語言解釋【問題描述】有一個魔王總是使用自己的一種非常精練而抽象的語言講話， 沒有人能昕得 懂，但他的語言是可以逐步解釋成人能聽懂的語言， 因?yàn)樗恼Z言是由以下兩種 形式的規(guī)則由人的語言逐步抽象上去的： 輒嶧陽檉籪癤網(wǎng)儂號澩。（2）（“2 八r在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統(tǒng)， 把 他的話解釋成人能聽得懂的話?！净疽蟆坑孟率鰞蓷l具體規(guī)則和上述規(guī)則形式（2）實(shí)現(xiàn)。設(shè)大寫字母表示魔王語言的 詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代 換的變量。魔王語言可含人的詞匯。 堯側(cè)閏繭絳闕絢勵蜆贅。 B；tAdA(2) A：

18、 sae【測試數(shù)據(jù)】B(ehnxgz)B 解釋成 tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是“天上一只 鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝” 。識饒鎂錕縊灩筧嚌儼 淒。tdsaezgxnh天地；上：一只鵝追趕下蛋恨【實(shí)現(xiàn)提示】將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。若是開括號，則逐一出棧， 將字母順序入隊(duì)列，直至閉括號出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。 其他情形較簡單，請讀者思考應(yīng)如何處理。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作。凍鈹鋨勞臘錯癇婦脛糴。【選作內(nèi)容】(1) 由于問題的特殊性，可以實(shí)現(xiàn)棧和隊(duì)列

19、的順序存儲空間共享。(2) 代換變量的數(shù)目不限，則在程序開始運(yùn)行時首先讀入一組第一種形式的 規(guī)則，而不是把規(guī)則固定在程序中(第二種形式的規(guī)則只能固定在程序中)。恥諤銪 滅縈歡煬鞏鶩錦。169. 馬踏棋盤【問題描述】設(shè)計(jì)一個國際象棋的馬踏遍棋盤的演示程序?！净疽蟆繉ⅠR隨機(jī)放在國際象棋的8$棋盤Board88的某個方格中，馬按走棋規(guī)則 進(jìn)行移動。要求每個方格只進(jìn)入一次，走遍棋盤上全部 64個方格。編制非遞歸 程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字 1, 2,，64依次填 入一個8>8的方陣，輸出之。鯊腎鑰詘漣鉀溈懼統(tǒng)庫。170. 算術(shù)表達(dá)式求值演示【問題描述】表達(dá)式計(jì)算是實(shí)現(xiàn)

20、程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個典型 例子。設(shè)計(jì)一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。碩癘鄴頏謅攆檸攜驤蘞?！净疽蟆恳宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教 科書表3.1給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿 照教科書的例3-1演示在求值中運(yùn)算符械、運(yùn)算數(shù)校、輸入字符和主要操作的變 化過程。閿擻輳嬪諫遷擇植秘騖。171. 銀行業(yè)務(wù)模擬【問題描述】客戶業(yè)務(wù)分為兩種。 第一種是申請從銀行得到一筆資金， 即取款或借款。 第 二種是向銀行投入一筆資金， 即存款或還款。 銀行有兩個服務(wù)窗口， 相應(yīng)地有兩 個隊(duì)列?？蛻舻竭_(dá)銀行后

21、先排第一個隊(duì)。 處理每個客戶業(yè)務(wù)時， 如果屬于第一種， 且申請額超出銀行現(xiàn)存資金總額而得不到滿足， 則立刻排入第二個隊(duì)等候， 直至 滿足時才離開銀行； 否則業(yè)務(wù)處理完后立刻離開銀行。 每接待完一個第二種業(yè)務(wù) 的客戶，則順序檢查和處理 （如果可能 ）第二個隊(duì)列中的客戶，對能滿足的申請者 予以滿足，不能滿足者重新排到第二個隊(duì)列的隊(duì)尾。注意，在此檢查過程中，一 旦銀行資金總額少于或等于剛才第一個隊(duì)列中最后一個客戶（第二種業(yè)務(wù) ）被接待之前的數(shù)額，或者本次已將第二個隊(duì)列檢查或處理了一遍，就停止檢查 （因?yàn)?此時已不可能還有能滿足者 ）轉(zhuǎn)而繼續(xù)接待第一個隊(duì)列的客戶。任何時刻都只開 一個窗口。假設(shè)檢查不需

22、要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。 氬嚕 躑竄貿(mào)懇彈瀘頷澩。寫一個上述銀行業(yè)務(wù)的事件驅(qū)動模擬系統(tǒng)， 通過模擬方法求出客戶在銀行內(nèi)逗留 的平均時間。【基本要求】利用動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)模擬。【測試數(shù)據(jù)】一天營業(yè)開始時銀行擁有的款額為 10000（元），營業(yè)時間為 600（分鐘 ）。其他 模擬參 量自定， 注意測定兩種極端的情況： 一是兩個到達(dá)事件之間的間隔時間很短， 而 客戶的交易時間很長， 另一個恰好相反， 設(shè)置兩個到達(dá)事件的間隔時間很長， 而 客戶的交易時間很短。 釷鵒資贏車贖孫滅獅贅?！緦?shí)現(xiàn)提示】事件有兩類：到達(dá)銀行和離開銀行。初始時銀行現(xiàn)存資金總額為total。開始 營業(yè)后的第一今

23、事件是客戶到達(dá)，營業(yè)時間從0到closetime。到達(dá)事件發(fā)生時隨 機(jī)地設(shè)置此客戶的交易時間和距下一到達(dá)事件之間的時間間隔。 每個客戶要辦理 的款額也是隨機(jī)確定的， 用負(fù)值和正值分別表示第一類和第二類業(yè)務(wù)。 變量 total， closetime以及上述兩個隨機(jī)量的上下界均交互地從終端讀入，作為模擬參數(shù)。慫闡譜鯪逕導(dǎo)嘯畫長涼。兩個隊(duì)列和一個事件表均要用動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)。 注意弄清應(yīng)該在什么條件下設(shè) 置離開事件， 以及第二個隊(duì)列用怎樣的存儲結(jié)構(gòu)實(shí)現(xiàn)時可以獲得較高的效率。 注 意：事件表是按時間順序有序的。 諺辭調(diào)擔(dān)鈧諂動禪瀉類?！具x作內(nèi)容】 自己實(shí)現(xiàn)動態(tài)數(shù)據(jù)類型。例如對于客戶結(jié)點(diǎn)，定義 pool

24、 為 CustNodepoolfMAX ；/ 結(jié)構(gòu)類型 CustNode含四個域：alTHIne，durtime，amount, next 或者定義四個同樣長的， 以上述域名為名字的數(shù)組。初始時，將所有分量的 next 域鏈接起來，形成一個靜態(tài)鏈找，設(shè)置一個樓頂元素下標(biāo)指示量top， top=0 表示找空。動態(tài)存儲分配函數(shù)可以取名為myMalloc，其作用是出錢，將錢頂元素的下標(biāo)返回。 若返回的值為 0，則表示無空間可分配。 歸還函數(shù)可取名為 myFree， 其作用是把該分量入錢。 用 FOR-TRAN 和 BASIC 等語言實(shí)現(xiàn)時只能如此地自行 組織。 嘰覲詿縲鐋囁偽純鉿錈。172. 航空客

25、運(yùn)訂票系統(tǒng)【問題描述】航空客運(yùn)訂票的業(yè)務(wù)活動包括： 查詢航線、 客票預(yù)訂和辦理退票等。 試設(shè)計(jì) 一個航空客運(yùn)訂票系統(tǒng)， 以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。 熒紿譏鉦鏌觶鷹緇機(jī)庫。【基本要求】（1）每條航線所涉及的信息有：終點(diǎn)站名、航班號、飛機(jī)號、飛行周日（星期幾 ）、乘員定額、余票量、已訂票的客戶名單 （包括姓名、訂票量、艙位等級 1，2 或 3）以及等候替補(bǔ)的客戶名單 （ 包括姓名、所需票量 ）；鶼漬螻偉閱劍鯫腎邏蘞。（2）系統(tǒng)能實(shí)現(xiàn)的操作和功能如下： 錄入：可以錄入航班情況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲在文件 中； 查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號、飛機(jī)號、星 期

26、幾飛行，最近一天航班的日期和余票額； 紂憂蔣氳頑薟驅(qū)藥憫騖。 承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額 情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少 于訂票額，則需重新詢問客戶要求。若需要，可登記排隊(duì)候補(bǔ)； 穎芻莖蛺餑億頓裊賠瀧。 承辦退票業(yè)務(wù)： 根據(jù)客戶提供的情況 （日期、航班），為客戶辦理退票手續(xù)， 然后查詢該航班是否有人排隊(duì)候補(bǔ)， 首先詢問排在第一的客戶， 若所退票額能滿 足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊(duì)候補(bǔ)的客戶。 濫驂膽閉 驟羥闈詔寢賻?！緶y試數(shù)據(jù)】由讀者自行指定?！緦?shí)現(xiàn)提示】兩個客戶名單可分別由線性表和隊(duì)列實(shí)現(xiàn)

27、。 為查找方便， 已訂票客戶的線性 表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲結(jié)構(gòu)。由于預(yù) 約人數(shù)無法預(yù)計(jì)， 隊(duì)列也應(yīng)以鏈表作存儲結(jié)構(gòu)。 整個系統(tǒng)需匯總各條航線的情況 登錄在一張線性表上， 由于航線基本不變， 可采用順序存儲結(jié)構(gòu)， 并按航班有序 或按終點(diǎn)站名有序。 每條航線是這張表上的一個記錄， 包含上述 8 個域、其中乘 員名單域?yàn)橹赶虺藛T名單鏈表的頭指針， 等候替補(bǔ)的客戶名單域?yàn)榉謩e指向隊(duì)頭 和隊(duì)尾的指針。 銚銻縵嚌鰻鴻鋟謎諏涼?！具x作內(nèi)容】當(dāng)客戶訂票要求不能滿足時， 系統(tǒng)可向客戶提供到達(dá)同一目的地的其他航線 情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)

28、項(xiàng)目。 擠貼綬電麥結(jié)鈺贖嘵類。173. 電梯模擬【問題描述】設(shè)計(jì)一個電梯模擬系統(tǒng)。 這是一個離散的模擬程序， 因?yàn)殡娞菹到y(tǒng)是乘客和 電梯等“活動體“構(gòu)成的集合， 雖然他們彼此交互作用， 但他們的行為是基本獨(dú)立 的。在離散的模擬中， 以模擬時鐘決定每個活動體的動作發(fā)生的時刻和順序， 系 統(tǒng)在某個模擬瞬間處理有待完成的各種事情， 然后把模擬時鐘推進(jìn)到某個動作預(yù) 定要發(fā)生的下一個時刻。 賠荊紳諮侖驟遼輩襪錈?！净疽蟆?1) 模擬某校五層教學(xué)樓的電梯系統(tǒng)。 該樓有一個自動電梯， 能在每層停留。 五個樓層由下至上依次稱為地下層、第 一層、第二層、第三層和第四層，其中第 一層是大樓的迸出層，即是電梯的

29、 “本壘層“，電梯“空閑“時，將來到該層候命。 塤礙籟饈決穩(wěn)賽釙冊庫。(2) 乘客可隨機(jī)地進(jìn)出于任何層。對每個人來說，他有一個能容忍的最長等 待時間，一旦等候電梯時間過長，他將放棄。 裊樣祕廬廂顫諺鍘羋藺。(3) 模擬時鐘從 0 開始，時間單位為 0.1 秒。人和電梯的各種動作均要耗費(fèi) 一定的時間單位(簡記為t)，比如：倉嫗盤紲囑瓏詁鍬齊驚。有人進(jìn)出時，電梯每隔 40t 測試一次，若無人進(jìn)出，則關(guān)門； 關(guān)門和開門各需要 20tg每個人進(jìn)出電梯均需要 25h如果電梯在某層靜止時間超過 300t，則駛回1層候命。(4) 按時序顯示系統(tǒng)狀態(tài)的變化過程：發(fā)生的全部人和電梯的動作序列。 【測試數(shù)據(jù)】模擬

30、時鐘Time的初值為0,終值可在50010000范圍內(nèi)逐步增加。【實(shí)現(xiàn)提示】(1) 樓層由下至上依次編號為0, 1, 2, 3, 4。每層有要求Up(上)和Down(下 的兩個按鈕，對應(yīng) 10 個變量 CaliUp0.4和 CallDOWEl0.4 。電梯內(nèi) 5個目標(biāo) 層按鈕對應(yīng)變量 Caucar0.4。有人按下某個按鈕時, 相應(yīng)的變量就置為 1,一旦 要求滿足后,電梯就把該變量清為 0。綻萬璉轆娛閬蟶鬮綰瀧。(2) 電梯處于三種狀態(tài)之-zGoingUp(上行)、GoingDown(下行)和ldle(停候)。 如果電梯處于 Idle 狀態(tài)且不在 1 層,則關(guān)門并駛回 1 層。在 1 層停候時,

31、 電梯是 閉門候命。一旦收到往另一層的命令,就轉(zhuǎn)入 GoingUp 或 GoingDown 狀態(tài),執(zhí) 行相應(yīng)的操作。 驍顧燁鶚巰瀆蕪領(lǐng)鱺賻。(3) 用變量 Time 表示模擬時鐘,初值為 0,時間單位。 )為 0。 l 秒。其他重要 的變量有：Floor 電梯的當(dāng)前位置 (樓層)；Dl 值為 0,除非人們正在進(jìn)入和離開電梯；D2 值為0,如果電梯已經(jīng)在某層停候 30Ot以上；D3 值為 0,除非電梯門正開著又無人迸出電梯；State 電梯的當(dāng)前狀態(tài) (GoingUp, GoingDOWEl, ldle)。 系統(tǒng)初始時, Floor=1 , Dl=D2=D3=0 , State=ldle。(4)

32、 每個人從進(jìn)入系統(tǒng)到離開稱為該人在系統(tǒng)中的存在周期。在此周期內(nèi), 他有 6 種可能發(fā)生的動作：M1. 進(jìn)入系統(tǒng),為下一人的出現(xiàn)作準(zhǔn)備 產(chǎn)生以下數(shù)值：lnFloor 該人進(jìn)入哪層樓；011tFloor 他要去哪層樓；GiveupTime 他能容忍的等候時間；lnter-Time 下一人出現(xiàn)的時間間隔, 據(jù)此系統(tǒng)預(yù)置下一人進(jìn)入系統(tǒng)的時刻。M2. 按電鈕并等候 此時應(yīng)對以下不同情況作不同的處理： Floor=lnFloor且電梯的下一個活動是 E6（電梯在本層，但正在關(guān)門; Floor=lnFloor且D3手0（電梯在本層，正有人迸出）； 其他情況，可能D2=0或電梯處于活動El（在1層停候）。M3

33、.進(jìn)入排隊(duì)在等候隊(duì)列QueuelnFloor末尾插入該人，并預(yù)置在 GiveupTime 個 t 之后，他若仍在隊(duì)列中將實(shí)施動作 M4。 瑣釙濺曖惲錕縞馭篩涼。M4.放棄如果Floor手InF loor或Dl=0，則從 Quem In Floor和系統(tǒng)刪除 該人。如果Floor=lnFloor且D1學(xué)0,他就繼續(xù)等候（他知道馬上就可進(jìn)入電梯。 鎦詩涇艷損樓紲鯗餳類。M5.進(jìn)入電梯從QueuelnFloor刪除該人，并把他插入到IEIevator（電梯） 校中。置Cancar011tFloor為1。櫛緶歐鋤棗鈕種鵑瑤錟。M6.離去從Elevator和系統(tǒng)刪除該人。（5）電梯的活動有 9 種：E1

34、.在1層停候若有人按下一個按鈕，貝U調(diào)用Controler將電梯轉(zhuǎn)入活動E3 或 E60。E2.要改變狀態(tài)？如果電梯處于 GoingUp（或GoingDown狀態(tài)，但該方向 的樓層卻無人等待，則要看反方向樓層是否有人等候，而決定置State 為GoingDown（或GoingUp還是Idle。轡燁棟剛殮攬瑤麗鬮應(yīng)。E3.開門置DI和D2為非0值，預(yù)置300個t后啟動活動E9和76個t后 啟動E5，然后預(yù)置20個t后轉(zhuǎn)到目。峴揚(yáng)爛滾澗輻灄興渙藺。E4.讓人出入如果Elevator不空且有人的011tFloor=Floor,則按進(jìn)入的倒 序每隔25個t讓這類人立即轉(zhuǎn)到他們的動作 M6。Elevat

35、or中不再有要離開的人 時，如果QueueFloor不空，則以25個t的速度讓他們依次轉(zhuǎn)到 MLQueueFloor 空時，置 Dl 為 0， D3 手 0，而且等候某個其他活動的到來。 詩叁撻訥燼憂毀厲鋨驁。E5.關(guān)門每隔40個t檢查D1，直到是D仁0（若D1手0,則仍有人出入。 置D3為0并預(yù)置電梯再20個t后啟動活動E6（再關(guān)門期間，若有人到來，則如 M2 所述，門再次打開 ）。 則鯤愜韋瘓賈暉園棟瀧。E6.準(zhǔn)備移動置 CaucarFloor為 0,而且若 State手 GoingDown，則置 CallUP 脹鏝彈奧秘孫戶孿釔賻。CFloor為 05 若 State手 GoingUp，

36、則置 CallDownCFIoor為 0。調(diào)用 Controler 函 數(shù)。 鰓躋峽禱紉誦幫廢掃減。如果State=ldle,則即使已經(jīng)執(zhí)行了 Controler，也轉(zhuǎn)到E1。否則，如果 D2 手0,則取消電梯活動E9。最后，如果State=GoingUp,則預(yù)置15個t后（電梯 加速轉(zhuǎn)到E7；如果State=GoingDown,則預(yù)置15個t后（電梯加速）轉(zhuǎn)到E8。稟 虛嬪賑維嚌妝擴(kuò)踴糶。E7. 上升一層 置 Floor 加 1 并等候 51 個人如果現(xiàn)在 CaucarFloor =1 或 CallUpFloor=1 ， 或 者 如 果 （Floor=1 或 CallD0WElFloor=1

37、） 且 CallUpj=CallDOWElj=CallCar-0=0 對于所有 j>Floor）,則預(yù)置 14 個 t 后（減速） 轉(zhuǎn)至U E2;否貝U重復(fù) E7。陽簍埡鮭罷規(guī)嗚舊巋錟。E8.下降一層除了方向相反之外，與E7類似，但那里的51和14個t,此 時分別改為61和23個t（電梯下降比上升慢）。溈氣嘮戇萇鑿鑿櫧諤應(yīng)。E9.置不活動指示器置D2為0并調(diào)用Controler函數(shù)（E9是由E3預(yù)置的， 但幾乎總是被 E6 取消了訓(xùn)。 鋇嵐縣緱虜榮產(chǎn)濤團(tuán)藺。當(dāng)電梯須對下一個方向作出判定時，便在若干臨界時刻調(diào)用Controler函數(shù)。該函數(shù)有以下要點(diǎn)：C1.需要判斷？若State手Idle

38、，則返回。C2.應(yīng)該開門？如果電梯處于 E1 且 CallUp1 ,CallDown1或 Caucar1非 0， 貝V懨俠劑鈍觸樂鷴燼觶騮。預(yù)置20個t后啟動E3,并返回。C3.有按鈕按下?找最小的j手Floor，使得CallUpj , CallDOWElj或 Caucarj非0,并轉(zhuǎn)到C4。但如果不存在這樣的j,那么，如果Controler正為 E6所調(diào)用，則置j為1,否則返回。 謾飽兗爭詣繚鮐癩別濾。C4.置 State如果 Floor>j，則置 State為 GoingDOWEl ;如果 Floorvj，則置 State為咼鉉們歟謙鴣餃競蕩賺。Goi ngUp。C5.電梯靜止?如果

39、電梯處于E1而且j手1,則預(yù)置20個t后啟動E6。返 回。(7)由上可見，關(guān)鍵是按時序管理系統(tǒng)中所有乘客和電梯的動作設(shè)計(jì)合適的數(shù) 據(jù)結(jié)構(gòu)?！具x作內(nèi)容】(1) 增加電梯數(shù)量，模擬多梯系統(tǒng)。(2) 某高校的一座30層住宅樓有三部自動電梯，每梯最多載客15人。大樓每層8戶，每戶平均3。5人，每天早晨平均每戶有3人必須在7時之前離開大 樓去上班或上學(xué)。模擬該電梯系統(tǒng)，并分析分別在一梯、二梯和三梯運(yùn)行情況下， 下樓高峰期間各層的住戶應(yīng)提前多少時間候梯下樓？研究多梯運(yùn)行最佳策略?，撝C齷蘄賞組靄縐嚴(yán)減。174. 迷宮問題【問題描述】以一個mx n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè) 計(jì)一個

40、程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路， 或得出沒有通 路的結(jié)論。 麩肅鵬鏇轎騍鐐縛縟糶?！净疽蟆烤帉懸粋€求解迷宮的非遞歸程序。求得的通路以三元組(i, j, d)的形式輸出， 其中：(i, j)指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列 數(shù)據(jù)的迷宮，輸出的一條通路為 z(1, 1, 1), (1, 2, 2), (2, 2, 2), (3, 2, 3), (3, 1, 2),-納疇鰻吶鄖禎銣膩鰲錟?！緶y試數(shù)據(jù)】迷宮的測試數(shù)據(jù)如下：左上角(1, 1)為入口，右下角(8, 9)為出口。123456780010001000100010000011010111001

41、00001000001000101011110011100010111000000【實(shí)現(xiàn)提示】計(jì)算機(jī)解迷宮通常用的是 窮舉求解 方法，即從人口出發(fā)，順著某一個方向 進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個方向繼續(xù)探索， 直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口， 則所設(shè)定的迷宮沒有通路。風(fēng)攆鮪貓鐵頻鈣薊糾廟?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為(1,1),出口點(diǎn)的下標(biāo)為(n, n)。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位 置，均可約定有東、南、西、北四個方向可通。滅曖駭諗鋅獵輛覯餿藹?！具x作內(nèi)容】(1) 編寫遞歸形式

42、的算法，求得迷宮中所有可能的通路；(2) 以方陣形式輸出迷宮及其通路。ch3 串及其應(yīng)用本實(shí)習(xí)單元的目的是熟悉串類型的實(shí)現(xiàn)方法和文本模式匹配方法，熟悉一般文字處理軟件的設(shè)計(jì)方法，較復(fù)雜問題的分解求精方法。本實(shí)習(xí)單元的難度較大 在教學(xué)安排上可以靈活掌握完成此單元實(shí)習(xí)的時間。鐒鸝餉飾鐔閌貲諢癱騮。編程技術(shù)訓(xùn)練要點(diǎn)：并行的模式匹配技術(shù)(3.1);字符填充技術(shù)(3.2,3.4);邏 輯/物理概念隔離技術(shù)(GetAWord,3.2);活區(qū)操作技術(shù)(3.3);不定長對象的成塊 存儲分配技術(shù)(3.3);命令識別與分析技術(shù)(3.3,3.4);串的動態(tài)組織技術(shù)(3.4); 合理有效的錯誤處理方法(3.4);程序

43、語法結(jié)構(gòu)基本分析技術(shù)(3.5).攙閿頻嶸陣澇諗 譴隴瀘。175. 文學(xué)研究助手【問題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試 寫一個實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱為"文學(xué)研究助手"。趕輾雛紈顆鋝討躍滿賺?！净疽蟆坑⑽男≌f存于一個文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì) 工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號 , 格式自行設(shè)計(jì)。 夾覡閭輇駁檔驀遷錟減。 【測試數(shù)據(jù)】以你的C源程序模擬英文小說,C語言的保留字集作為待統(tǒng)計(jì)的詞匯集?！緦?shí)現(xiàn)提示】約定小說中的詞匯一律不跨行 。這樣,每

44、讀入一行,就統(tǒng)計(jì)每個詞在這行中的 出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次 , 不必存多個相同的行號。 視絀鏝鴯鱭鐘腦鈞欖糲。如果讀者希望達(dá)到選做部分(1)和(2)所提出的要求,則首先應(yīng)把KM算法改 寫成如下的等價(jià)形式 , 再將它推廣到多個模式的情形。 偽澀錕攢鴛擋緬鐒鈞錠。i=1;j=1; while(i!=s.curlen+1&&j!=t.curlerl 十1) while(j!=0&&s.chi!=t.chj)j=nextj; /j=O 或 s.chi=t.chjj+;i+;/ 每次進(jìn)入循環(huán)體 ,i 只增加一次【選作內(nèi)容】(1)

45、 模式匹配要基于KM算法。(2) 整個統(tǒng)計(jì)過程中只對小說文字掃描一遍以提高效率。(3) 假設(shè)小說中的每個單詞或者從行首開始 , 或者前置一個空格符 。利用單詞 匹配特點(diǎn)另寫一個高效的統(tǒng)計(jì)程序，與KM算法統(tǒng)計(jì)程序進(jìn)行效率比較。緦徑銚膾齲 轎級鏜撟廟。(4) 推廣到更一般的模式集匹配問題 , 并設(shè)待查模式串可以跨行 (提示:定義 操作 GetAChar) 。176. 文本格式化【問題描述】 輸入文件中含有待格式化或稱為待排版的文本 , 它由多行的文字組成 ,例如一篇英文文章。每一行由一系列被一個或多個空格符所隔開的字組成，任何完整的字都沒有被分割在兩行 ( 每行最后一個字與下一行的第一個字之間 在

46、邏輯上應(yīng)該由空格分開 ), 每行字符數(shù)不超過 80。除了上述文本類字符之外 , 還存在著起控制作用的字符 : 符號""指示它后面的正文在格式化時應(yīng)另起一段 排放,即空一行,并在段首縮入8個字符位置。 ""自成一個字 。 騅憑鈳銘僥張礫陣軫藹。一個文本格式化程序可以處理上述輸入文件 , 按照用戶指定的版面規(guī)格重 排版面z實(shí)現(xiàn)頁內(nèi)調(diào)整、分段、分頁等文本處理功能，排版結(jié)果存入輸出文本文 件中。 癘騏鏨農(nóng)剎貯獄顥幗騮。試寫一個這樣的程序?！净疽蟆?1) 輸出文件中字與字之間只留一個空格符 , 即實(shí)現(xiàn)多余空格符的壓縮。(2) 在輸出文件中 , 任何完整的字仍不

47、能分割在兩行 , 行尾不齊沒關(guān)系 , 但行 首要對齊 (即左對齊) 。(3) 如果所要求的每頁頁底所空行數(shù)不少于 3, 則將頁號印在頁底空行中第2行的中間位置上 , 否則不印(4) 版面要求的參數(shù)要包含：頁長(PageLength) 一每頁內(nèi)文字(不計(jì)頁號)的行數(shù)。頁寬(PageWedth)一 一每行內(nèi)文字所占最大字符數(shù)。左空白 (LeftMargin)- 一一每行文字前的固定空格數(shù)。頭長 (HeadingLength) 一一每頁頁頂所空行數(shù)。腳長(FootingLength) 一每頁頁底所空行數(shù)(含頁號行)。起始頁號 (StartingPageNumber) 一一首頁的頁號?！緶y試數(shù)據(jù)】略。

48、注意在標(biāo)點(diǎn)之后加上空格符。【實(shí)現(xiàn)提示】可以設(shè)：左空白數(shù)x 2+頁寬=160,即行印機(jī)最大行寬,從而只要設(shè)置這樣大 的一個行緩沖區(qū)就足夠了 , 每加工完一行 , 就輸出一行。 鏃鋝過潤啟婭澗駱讕瀘。如果輸入文件和輸出文件不是由程序規(guī)定死 , 而是可由用戶指定 , 則有兩種 做法： 一是像其他參量一樣 , 將文件名交互地讀入字符串變量中 ; 更好的方式是 讓用戶通過命令行指定 , 具體做法依機(jī)器的操作系統(tǒng)而定。 榿貳軻謄壟該檻鯔塏賽。應(yīng)該首先實(shí)現(xiàn)GetAWord(w)這一操作，把諸如行尾處理、文件尾處理、多余 空格符壓縮等一系列 " 低級" 事務(wù)留給它處理 , 使系統(tǒng)的核心部分

49、集中對付排版 要求。 邁蔦賺陘賓唄擷鷦訟湊。每個參數(shù)都可以實(shí)現(xiàn)缺省值設(shè)置。上述排版參數(shù)的缺省值可以分別取56,60,10,5,5 和1?！具x作內(nèi)容】(1) 輸入文件名和輸出文件名要由用戶指定。(2) 允許用戶指定是否右對齊 , 即增加一個參量 " 右對齊否 "(RightJustifying), 缺省值可設(shè)為 "y"(yes) 。右對齊指每行最后一個字的字尾 要對齊 , 多余的空格要均勻分布在本行中各字之間。 嶁硤貪塒廩袞憫倉華糲。(3) 實(shí)現(xiàn)字符填充 (characterstuffing) 技術(shù)。 ""作為分段控制符之后 , 限 制

50、了原文中不能有這樣的字?，F(xiàn)在去掉這一限制 ： 如果原文中有這樣的字 , 改用 兩個""并列起來 表示一個 ""字。當(dāng)然, 如果原文中此符號夾在字中 , 就不必 特殊處理了。 該櫟諼碼戇沖巋鳧薩錠。(4) 允許用戶自動按多欄印出一頁。177. 簡單行編輯程序【問題描述】文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具 , 實(shí)現(xiàn)對文本文 件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行 編輯程序。 劇妝諢貰攖蘋塒呂侖廟。被編輯的文本文件可能很大 , 全部讀入編輯程序的數(shù)據(jù)空間 (內(nèi)存)的作法 既不經(jīng)濟(jì) , 也不總能實(shí)現(xiàn)。一種解決方法是逐

51、段地編輯。任何時刻只把待編輯文 件的一段放在內(nèi)存 ,稱為活區(qū)。試按照這種方法實(shí)現(xiàn)一個簡單的行編輯程序。設(shè) 文件每行不超過 320個字符 , 很少超過 80個字符。 臠龍訛驄椏業(yè)變墊羅蘄。 【基本要求】實(shí)現(xiàn)以下 4條基本編輯命令 :(1) 行插入。格式 :i 行號 回車文本.回車 將文本插入活區(qū)中第 行號 行之后。(2) 行刪除。格式:d行號1空格 亍號2回車刪除活區(qū)中第 行號1行(到第 行號2行)。例如:"d10"和"d1014"。(3) 活區(qū)切換。格式*回車將活區(qū)寫入輸出文件 , 并從輸入文件中讀入下一段 ,作為新的活區(qū)。(4) 活區(qū)顯示。格式:p回車

52、逐頁地(每頁20行)顯示活區(qū)內(nèi)容 ,每顯示一頁之后請用戶決定是否 繼續(xù)顯示以后備頁 (如果存在)。印出的每一行要前置行號和一個空格符 , 行號固定占 4位, 增量為 1 。鰻順褸悅漚縫囅屜鴨騫。各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi) , 只有插入命令 的行號可以等于活區(qū)第一行行號減 1,表示插入當(dāng)前屏幕中第一行之前 , 否則命令參數(shù)非法。 穡釓虛綹滟鰻絲懷紓濼?！緶y試數(shù)據(jù)】自行設(shè)定 , 注意測試將活區(qū)刪空等特殊情況?！緦?shí)現(xiàn)提示】(1) 設(shè)活區(qū)的大小用行數(shù)ActiveMULen(可設(shè)為100)來描述?？紤]到文本文件 行長通常為正態(tài)分布，且峰值在60到70之間，用320x ActiveMUL

53、en大小的字符數(shù) 組實(shí)現(xiàn)存儲將造成大量浪費(fèi) 。可以以標(biāo)準(zhǔn)行塊為單位為各行分配存儲 , 每個標(biāo)準(zhǔn) 行塊可含 81個字符。這些行塊可以組成一個數(shù)組 , 也可以利用動態(tài)鏈表連接起 來。一行文字可能占多個行塊。行尾可用一個特殊的 ASCII字符(如(012)8)標(biāo) 識。此外 , 還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。 隸 誆熒鑒獫綱鴣攣駘賽。(2) 初始化函數(shù)包括 : 請用戶提供輸入文件名 (空串表示無輸入文件 )和輸出 文件名, 兩者不能相同。然后盡可能多地從輸入文件中讀入各行 , 但不超過 ActiveMULen-LX的值可以自定,例如20。浹繢膩叢著駕驃構(gòu)碭湊。(3) 在執(zhí)行

54、行插入命令的過程中 , 每接收到一行時都要檢查活區(qū)大小是否已達(dá)ActiveMaxLen。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過 ActiveMaxLen應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前 , 則只得將新插入的這一行輸出。 鈀燭罰櫝箋礱颼畢韞糲。(4) 若輸入文件尚未讀完 , 活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂 部,以保持閱讀連續(xù)性 ；否則,它意味著結(jié)束編輯或開始編輯另一個文件。 愜執(zhí)緝蘿 紳頎陽灣熗鍵。(5) 可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示?！具x作內(nèi)容】(1) 對于命令格式非法等一切錯誤作嚴(yán)格檢查和適當(dāng)處理。(2) 加入更復(fù)雜的編輯

55、操作 ,如對某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配 等，格式可以為S亍號串1串2回車 和m 回車 。貞廈給鏌綞牽鎮(zhèn)獵鎦龐。178. 串基本操作的演示【問題描述】如果語言沒有把串作為一個預(yù)先定義好的基本類型對待, 又需要用該語言寫一個涉及串操作的軟件系統(tǒng)時 ,用戶必須自己實(shí)現(xiàn)串類型。試實(shí)現(xiàn)串類型 , 并 寫一個串的基本操作的演示系統(tǒng)。 嚌鯖級廚脹鑲銦礦毀蘄。【基本要求】在教科書 4.2.2 節(jié)用堆分配存儲表示實(shí)現(xiàn) HString 串類型的最小操作子集的 基礎(chǔ)上,實(shí)現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不使用C語言本身提供的串函 數(shù) ) 。參數(shù)合法性檢查必須嚴(yán)格。 薊鑌豎牘熒浹醬籬鈴騫。利用上述基本操作函

56、數(shù)構(gòu)造以下系統(tǒng) :它是一個命令解釋程序 ,循環(huán)往復(fù)地 處理用戶鍵入的每一條命令 , 直至終止程序的命令為止。命令定義如下 : 齡踐硯語蝸 鑄轉(zhuǎn)絹攤濼。(1) 賦值。 格式: A 串標(biāo)識 回車用 串標(biāo)識 所表示的串的值建立新串 , 并顯示新串的內(nèi)部名和串值。例 :A Hi! '(2) 判相等。格式 : E 串標(biāo)識1 串標(biāo)識2 回車 若兩串相等,則顯示"EQUAL",否則顯示"UNEQUAL。(3) 聯(lián)接。 格式:C 串標(biāo)識1 串標(biāo)識2 回車 將兩串拼接產(chǎn)生結(jié)果串 , 它的內(nèi)部名和串值都顯示出來。求長度。格式：L串標(biāo)識回車 顯示串的長度。(5) 求子串。格式 ：S 串標(biāo)識 +數(shù)1+數(shù)2回車 如果參數(shù)合法 , 則顯示子串的內(nèi)部名和串值。 數(shù)不帶正負(fù)號。(6) 子串定位。格式 ：I 串標(biāo)識 1 串標(biāo)識 2 回車 顯示第二個串在第一個串中首次出現(xiàn)時的起始位置。(7) 串替換。格式 ： R 串標(biāo)識1 串標(biāo)識2 串標(biāo)識3 回車 將第一個串中所有出現(xiàn)的第二個串用第三個串替換 ,顯示結(jié)果串的內(nèi)部名和串值, 原串不變。(8) 顯示。格式 ：P 回車 顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對照表。(9) 刪除。格式:D 內(nèi)部名 回車 刪除該內(nèi)部名對應(yīng)的串 ,即賦值的