XX年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及報(bào)告范例

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

2、學(xué)校的名稱(chēng)，運(yùn)動(dòng)項(xiàng)目的名稱(chē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ù)文件中。測(cè)試數(shù)據(jù)：【測(cè)試數(shù)據(jù)】要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程 序測(cè)試，以保證程序的穩(wěn)定。例如，對(duì)于n=4, m=3, w =2,編號(hào)為奇數(shù)的項(xiàng)目取前五名，編號(hào)為偶數(shù)的 項(xiàng)目取前三名，設(shè)計(jì)一組實(shí)例數(shù)據(jù)。【實(shí)現(xiàn)提示】可以假設(shè)nw 20, m< 30, w< 20,姓名長(zhǎng)度不超過(guò) 20個(gè)字符。每個(gè)項(xiàng)目結(jié)束時(shí)，將其編號(hào)、類(lèi)型符

3、（區(qū)分取前五名還是前三名）輸入，并按名次順序輸入運(yùn)動(dòng)員姓名、校名(和成績(jī))?！具x作內(nèi)容】允許用戶(hù)指定某項(xiàng)目采取其他名次取法。2. 集合的并、交和差運(yùn)算【問(wèn)題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序。【基本要求】(1) 集合的元素限定為小寫(xiě)字母字符a'''。(2) 演示程序以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式執(zhí)行?！緶y(cè)試數(shù)據(jù)】(1) Set仁"magazine", Set2="paper",Setlu Set2="aegimnprz", Setl n Set2="ae", Set1-Set2=&

4、quot;gimnz"。(2) Set1= " 012oper4a6tion89", Set2="error data",SetluSet2="adeinoprt", Setl n Set2="aeort", Set1-Set2="inp"?！緦?shí)現(xiàn)提示】以有序鏈表表示集合?！具x作內(nèi)容】(1) 集合的元素判定和子集判定運(yùn)算。(2) 求集合的補(bǔ)集。(3) 集合的混合運(yùn)算表達(dá)式求值。(4) 集合的元素類(lèi)型推廣到其他類(lèi)型，甚至任意類(lèi)型。3. 一兀稀疏多項(xiàng)式計(jì)算器【問(wèn)題描述】設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)

5、式簡(jiǎn)單計(jì)算器。【基本要求】一元稀疏多項(xiàng)式簡(jiǎn)單計(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ù)降 序排列；(3) 多項(xiàng)式a和b相加，建立多項(xiàng)式a +b；(4) 多項(xiàng)式a和b相減，建立多項(xiàng)式a -b ?！緶y(cè)試數(shù)據(jù)】(1) (2x+5x8 3.1x11) + (7 - 5x8+11x9)=( - 3.lx11+11x9+2x+7)(2) (6x-3 x+4.4x2- 1.2x9) - (-6x-3+5.4x2 x2+7.8x15)159-3、=(-7.8

6、x -1.2x +12x -x)(3) (1 +x + x 2 +x3+x 4+x 5)+(-x 3x4)=(1+x+x 2+x5)(x+x)+(-x x3)=0(5) (x+x100)+(x100 +x200)=(x+2x100+x200(6) (x+x2+x3)+0=x+x2+x3(7) 互換上述測(cè)試數(shù)據(jù)中的前后兩個(gè)多項(xiàng)式【實(shí)現(xiàn)提示】用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式?！具x作內(nèi)容】(1) 計(jì)算多項(xiàng)式在x處的值。(2) 求多項(xiàng)式a的導(dǎo)函數(shù)a o(3) 多項(xiàng)式a和b相乘，建立乘積多項(xiàng)式ab o多項(xiàng)式的輸出形式為類(lèi)數(shù)學(xué)表達(dá)式。例如，多項(xiàng)式-3x8+6x3 18的輸出形式為-3x 8 6x 3-18，

7、x15+( 8)x7 14的輸出形式為 x 15-8x 7-14。注意，數(shù) 值為1的非零次項(xiàng)的輸出形式中略去系數(shù)1,如項(xiàng)1x8的輸出形式為x8,項(xiàng)一1x3 的輸出形式為一x3o(5) 計(jì)算器的仿真界。4. 池塘夜降彩色雨【問(wèn)題描述】設(shè)計(jì)一個(gè)程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點(diǎn)飄飄灑灑地 從天而降， 滴滴入水有聲，濺起圈圈微瀾?！净疽蟆?1) 雨點(diǎn)的空中出現(xiàn)位置、降范過(guò)程的可見(jiàn)程度、入水位置、顏色、最大水 圈等，都是隨機(jī)確定的；(2) 多個(gè)雨點(diǎn)按照各自的隨機(jī)參數(shù)和存在狀態(tài)，同時(shí)演示在屏幕上。【測(cè)試數(shù)據(jù)】適當(dāng)調(diào)整控制雨點(diǎn)密度、最大水圈和狀態(tài)變化的時(shí)間間隔等參數(shù)?！緦?shí)現(xiàn)提示】(1)

8、每個(gè)雨點(diǎn)的存在周期可分為三個(gè)階段： 從天而降、入水有聲和圈圈微瀾,曲:*需要個(gè)記錄存儲(chǔ)其相關(guān)參數(shù)、當(dāng)前狀態(tài)和下一狀態(tài)的更新時(shí)刻。(2) 在圖形狀態(tài)編程。雨點(diǎn)下降的可見(jiàn)程度應(yīng)是斷斷續(xù)續(xù)、依稀可見(jiàn)；圈圈 水波應(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)中刪去?！具x作內(nèi)容】(1) 增加“電閃雷鳴”景象。 增加風(fēng)的效果，展現(xiàn)“風(fēng)雨飄搖”的情景。(3) 增加雨點(diǎn)密度的變化：時(shí)而“和風(fēng)細(xì)雨”，時(shí)而“暴風(fēng)驟雨”。(4) 將“池塘”改為“荷塘”，

9、雨點(diǎn)滴在荷葉上的效果是濺起四散的水珠， 響聲也不同。5. 銀行業(yè)務(wù)模擬【問(wèn)題描述】客戶(hù)業(yè)務(wù)分為兩種。第一種是申請(qǐng)從銀行得到一筆資金， 即取款或借款。第 二種是向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)地有兩 個(gè)隊(duì)列?？蛻?hù)到達(dá)銀行后先排第一個(gè)隊(duì)。處理每個(gè)客戶(hù)業(yè)務(wù)時(shí)，如果屬于第一種， 且申請(qǐng)額超出銀行現(xiàn)存資金總額而得不到滿(mǎn)足，則立刻排入第二個(gè)隊(duì)等候，直至滿(mǎn)足時(shí)才離開(kāi)銀行；否則業(yè)務(wù)處理完后立刻離開(kāi)銀行。每接待完一個(gè)第二種業(yè)務(wù) 的客戶(hù)，則順序檢查和處理（如果可能）第二個(gè)隊(duì)列中的客戶(hù)，對(duì)能滿(mǎn)足的申請(qǐng)者 予以滿(mǎn)足，不能滿(mǎn)足者重新排到第二個(gè)隊(duì)列的隊(duì)尾。注意，在此檢查過(guò)程中，一 旦銀行資金總額

10、少于或等于剛才第一個(gè)隊(duì)列中最后一個(gè)客戶(hù)（第二種業(yè)務(wù)）被接待之前的數(shù)額，或者本次已將第二個(gè)隊(duì)列檢查或處理了一遍，就停止檢查（因?yàn)榇藭r(shí)已不可能還有能滿(mǎn)足者）轉(zhuǎn)而繼續(xù)接待第一個(gè)隊(duì)列的客戶(hù)。任何時(shí)刻都只開(kāi) 一個(gè)窗口。假設(shè)檢查不需要時(shí)間。營(yíng)業(yè)時(shí)間結(jié)束時(shí)所有客戶(hù)立即離開(kāi)銀行。寫(xiě)一個(gè)上述銀行業(yè)務(wù)的事件驅(qū)動(dòng)模擬系統(tǒng)， 通過(guò)模擬方法求出客戶(hù)在銀行內(nèi)逗留 的平均時(shí)間?！净疽蟆坷脛?dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)模擬。【測(cè)試數(shù)據(jù)】一天營(yíng)業(yè)開(kāi)始時(shí)銀行擁有的款額為10000（元），營(yíng)業(yè)時(shí)間為600（分鐘）。其他 模擬參量自定，注意測(cè)定兩種極端的情況：一是兩個(gè)到達(dá)事件之間的間隔時(shí)間很短， 而 客戶(hù)的交易時(shí)間很長(zhǎng)，另一個(gè)恰好相反，設(shè)置

11、兩個(gè)到達(dá)事件的間隔時(shí)間很長(zhǎng)， 而 客戶(hù)的交易時(shí)間很短。【實(shí)現(xiàn)提示】事件有兩類(lèi)：到達(dá)銀行和離開(kāi)銀行。初始時(shí)銀行現(xiàn)存資金總額為total。開(kāi)始 營(yíng)業(yè)后的第一今事件是客戶(hù)到達(dá)，營(yíng)業(yè)時(shí)間從0到closetime。到達(dá)事件發(fā)生時(shí)隨 機(jī)地設(shè)置此客戶(hù)的交易時(shí)間和距下一到達(dá)事件之間的時(shí)間間隔。 每個(gè)客戶(hù)要辦理 的款額也是隨機(jī)確定的，用負(fù)值和正值分別表示第一類(lèi)和第二類(lèi)業(yè)務(wù)。 變量total， closetime以及上述兩個(gè)隨機(jī)量的上下界均交互地從終端讀入，作為模擬參數(shù)。兩個(gè)隊(duì)列和一個(gè)事件表均要用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。注意弄清應(yīng)該在什么條件下設(shè)置離開(kāi)事件，以及第二個(gè)隊(duì)列用怎樣的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)可以獲得較高的效率。注意：

12、事件表是按時(shí)間順序有序的。【選作內(nèi)容】自己實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)類(lèi)型。例如對(duì)于客戶(hù)結(jié)點(diǎn)，定義pool為CustNodepoolfMAX；/ 結(jié)構(gòu)類(lèi)型 CustNode含四個(gè)域：alTHIne，durtime，amount, next或者定義四個(gè)同樣長(zhǎng)的，以上述域名為名字的數(shù)組。初始時(shí)，將所有分量的next域鏈接起來(lái)，形成一個(gè)靜態(tài)鏈找，設(shè)置一個(gè)樓頂元素下標(biāo)指示量top，top=0表示找空。動(dòng)態(tài)存儲(chǔ)分配函數(shù)可以取名為myMalloc，其作用是出錢(qián)，將錢(qián)頂元素的下標(biāo)返回。若返回的值為0,則表示無(wú)空間可分配。歸還函數(shù)可取名為myFree, 其作用是把該分量入錢(qián)。用FOR-TRAN和BASIC等語(yǔ)言實(shí)現(xiàn)時(shí)只能如此

13、地自行 組織。6. 馬踏棋盤(pán)【問(wèn)題描述】設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏遍棋盤(pán)的演示程序。【基本要求】將馬隨機(jī)放在國(guó)際象棋的8$棋盤(pán)Board88的某個(gè)方格中，馬按走棋規(guī)則 進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部 64個(gè)方格。編制非遞歸 程序，求出馬的行走路線(xiàn)，并按求出的行走路線(xiàn)，將數(shù)字 1, 2,，64依次填 入一個(gè)8>8的方陣，輸出之。7. 魔王語(yǔ)言解釋【問(wèn)題描述】有一個(gè)魔王總是使用自己的一種非常精練而抽象的語(yǔ)言講話(huà)， 沒(méi)有人能昕得 懂，但他的語(yǔ)言是可以逐步解釋成人能聽(tīng)懂的語(yǔ)言， 因?yàn)樗恼Z(yǔ)言是由以下兩種 形式的規(guī)則由人的語(yǔ)言逐步抽象上去的：M Qm(2) (X.仆.2 、：n)X十

14、在這兩種形式中，從左到右均表示解釋。試寫(xiě)一個(gè)魔王語(yǔ)言的解釋系統(tǒng)， 把 他的話(huà)解釋成人能聽(tīng)得懂的話(huà)?！净疽蟆坑孟率鰞蓷l具體規(guī)則和上述規(guī)則形式(2)實(shí)現(xiàn)。設(shè)大寫(xiě)字母表示魔王語(yǔ)言的 詞匯；小寫(xiě)字母表示人的語(yǔ)言詞匯；希臘字母表示可以用大寫(xiě)字母或小寫(xiě)字母代 換的變量。魔王語(yǔ)言可含人的詞匯。(1) B > tAdA(2) A > sae【測(cè)試數(shù)據(jù)】B(ehnxgz)B 解釋成 tsaedsaeezegexenehetsaedsae若將小寫(xiě)字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說(shuō)的話(huà)是“天上一只 鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕

15、下蛋恨【實(shí)現(xiàn)提示】將魔王的語(yǔ)言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。若是開(kāi)括號(hào)，則逐一出棧, 將字母順序入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。 其他情形較簡(jiǎn)單，請(qǐng)讀者思考應(yīng)如何處理。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作?！具x作內(nèi)容】(1) 由于問(wèn)題的特殊性，可以實(shí)現(xiàn)棧和隊(duì)列的順序存儲(chǔ)空間共享。(2) 代換變量的數(shù)目不限，則在程序開(kāi)始運(yùn)行時(shí)首先讀入一組第一種形式的 規(guī)則，而不是把規(guī)則固定在程序中(第二種形式的規(guī)則只能固定在程序中)。8. 航空客運(yùn)訂票系統(tǒng)【問(wèn)題描述】航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢(xún)航線(xiàn)、客票預(yù)訂和辦理退票等。試設(shè)計(jì) 一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來(lái)完成。

16、【基本要求】每條航線(xiàn)所涉及的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛行周日 （星期 幾）、乘員定額、余票量、已訂票的客戶(hù)名單（包括姓名、訂票量、艙位等級(jí)1, 2 或3）以及等候替補(bǔ)的客戶(hù)名單（包括姓名、所需票量）；（2）系統(tǒng)能實(shí)現(xiàn)的操作和功能如下： 錄入：可以錄入航班情況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲(chǔ)在文件 中； 查詢(xún)航線(xiàn)：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星 期幾飛行，最近一天航班的日期和余票額； 承辦訂票業(yè)務(wù)：根據(jù)客戶(hù)提出的要求（航班號(hào)、訂票數(shù)額）查詢(xún)?cè)摵桨嗥鳖~ 情況，若尚有余票，則為客戶(hù)辦理訂票手續(xù)，輸出座位號(hào)；若已滿(mǎn)員或余票額少于訂票額，則需重新詢(xún)問(wèn)客戶(hù)要求。若需要

17、，可登記排隊(duì)候補(bǔ)； 承辦退票業(yè)務(wù)：根據(jù)客戶(hù)提供的情況（日期、航班），為客戶(hù)辦理退票手續(xù)， 然后查詢(xún)?cè)摵桨嗍欠裼腥伺抨?duì)候補(bǔ)，首先詢(xún)問(wèn)排在第一的客戶(hù)，若所退票額能滿(mǎn) 足他的要求，貝U為他辦理訂票手續(xù)，否則依次詢(xún)問(wèn)其他排隊(duì)候補(bǔ)的客戶(hù)。【測(cè)試數(shù)據(jù)】由讀者自行指定?！緦?shí)現(xiàn)提示】?jī)蓚€(gè)客戶(hù)名單可分別由線(xiàn)性表和隊(duì)列實(shí)現(xiàn)。 為查找方便，已訂票客戶(hù)的線(xiàn)性 表應(yīng)按客戶(hù)姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。由于預(yù) 約人數(shù)無(wú)法預(yù)計(jì)，隊(duì)列也應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線(xiàn)的情況 登錄在一張線(xiàn)性表上，由于航線(xiàn)基本不變，可采用順序存儲(chǔ)結(jié)構(gòu)，并按航班有序 或按終點(diǎn)站名有序。每條航線(xiàn)是這張表上的一個(gè)記錄

18、，包含上述8個(gè)域、其中乘 員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，等候替補(bǔ)的客戶(hù)名單域?yàn)榉謩e指向隊(duì)頭 和隊(duì)尾的指針?！具x作內(nèi)容】當(dāng)客戶(hù)訂票要求不能滿(mǎn)足時(shí)，系統(tǒng)可向客戶(hù)提供到達(dá)同一目的地的其他航線(xiàn)情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。9. 藥店的藥品銷(xiāo)售統(tǒng)計(jì)系統(tǒng)【問(wèn)題描述】設(shè)計(jì)一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷(xiāo)售各藥品的記錄進(jìn)行統(tǒng)計(jì)， 可按藥品的編號(hào)、 單價(jià)、銷(xiāo)售量或銷(xiāo)售額做出排名。【基本要求】在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄， 存儲(chǔ)在順序表中。各藥 品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷(xiāo)出數(shù)量、銷(xiāo)售額。藥品編號(hào)共4位，采用字母和數(shù)字混合編號(hào)，如：A12

19、5,前一位為大寫(xiě)字母，后三位為數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷(xiāo)售量或銷(xiāo)售額 進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直 接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷(xiāo)售量的排 序采用快速排序法，對(duì)銷(xiāo)售額的排序采用堆排序法。10. 文學(xué)研究助手【問(wèn)題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為"文學(xué)研究助手"。【基本要求】英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì) 工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出

20、結(jié)果是每個(gè)詞的出現(xiàn) 次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)?！緶y(cè)試數(shù)據(jù)】以你的C源程序模擬英文小說(shuō),C語(yǔ)言的保留字集作為待統(tǒng)計(jì)的詞匯集?！緦?shí)現(xiàn)提示】約定小說(shuō)中的詞匯一律不跨行。這樣,每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的 出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次 , 不必存多個(gè)相同的行號(hào)。如果讀者希望達(dá)到選做部分(1)和(2)所提出的要求,則首先應(yīng)把KM算法改 寫(xiě)成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。i=1;j=1;while(i!=s.curle n+1 &&j!=t.curlerl十 1)while(j!=0&&s.chi!

21、=t.chj)j=n extj; j=0或 s.chi=t.chjj+;i+; 每次進(jìn)入循環(huán)體,i只增加一次【選作內(nèi)容】(1) 模式匹配要基于KM算法。(2) 整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。(3) 假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始，或者前置一個(gè)空格符。利用單詞 匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序，與KM算法統(tǒng)計(jì)程序進(jìn)行效率比較。(4) 推廣到更一般的模式集匹配問(wèn)題，并設(shè)待查模式串可以跨行(提示：定義 操作 GetAChar)。11. 文本格式化【問(wèn)題描述】輸入文件中含有待格式化或稱(chēng)為待排版的文本，它由多行的文字組成，例如一篇英文文章。每一行由一系列被一個(gè)或多個(gè)空格符所隔開(kāi)的字組成

22、，任何完整的字都沒(méi)有被分割在兩行(每行最后一個(gè)字與下一行的第一個(gè)字之間 在邏輯上應(yīng)該由空格分開(kāi))，每行字符數(shù)不超過(guò)80。除了上述文本類(lèi)字符之外， 還存在著起控制作用的字符：符號(hào)"'指示它后面的正文在格式化時(shí)應(yīng)另起一段 排放,即空一行,并在段首縮入8個(gè)字符位置。""自成一個(gè)字。一個(gè)文本格式化程序可以處理上述輸入文件，按照用戶(hù)指定的版面規(guī)格重 排版面z實(shí)現(xiàn)頁(yè)內(nèi)調(diào)整、分段、分頁(yè)等文本處理功能，排版結(jié)果存入輸出文本文 件中。試寫(xiě)一個(gè)這樣的程序?！净疽蟆?1) 輸出文件中字與字之間只留一個(gè)空格符，即實(shí)現(xiàn)多余空格符的壓縮。在輸出文件中，任何完整的字仍不能分割在兩行

23、，行尾不齊沒(méi)關(guān)系，但行 首要對(duì)齊(即左對(duì)齊)。(3) 如果所要求的每頁(yè)頁(yè)底所空行數(shù)不少于3,則將頁(yè)號(hào)印在頁(yè)底空行中第2行的中間位置上，否則不印。(4) 版面要求的參數(shù)要包含：頁(yè)長(zhǎng)(PageLength) 一每頁(yè)內(nèi)文字(不計(jì)頁(yè)號(hào))的行數(shù)。頁(yè)寬(PageWedth)一 一每行內(nèi)文字所占最大字符數(shù)。左空白(LeftMargin)- 一每行文字前的固定空格數(shù)。頭長(zhǎng)(Headi ngLe ngth) 一每頁(yè)頁(yè)頂所空行數(shù)。腳長(zhǎng)(FootingLength) 一每頁(yè)頁(yè)底所空行數(shù)(含頁(yè)號(hào)行)。起始頁(yè)號(hào)(StartingPageNumber) 一首頁(yè)的頁(yè)號(hào)。【測(cè)試數(shù)據(jù)】略。注意在標(biāo)點(diǎn)之后加上空格符?！緦?shí)現(xiàn)提示】

24、可以設(shè)：左空白數(shù)X 2+頁(yè)寬=160,即行印機(jī)最大行寬,從而只要設(shè)置這樣大 的一個(gè)行緩沖區(qū)就足夠了，每加工完一行，就輸出一行。如果輸入文件和輸出文件不是由程序規(guī)定死，而是可由用戶(hù)指定，則有兩種 做法:一是像其他參量一樣，將文件名交互地讀入字符串變量中；更好的方式是 讓用戶(hù)通過(guò)命令行指定，具體做法依機(jī)器的操作系統(tǒng)而定。應(yīng)該首先實(shí)現(xiàn)GetAWord(w)這一操作，把諸如行尾處理、文件尾處理、多余 空格符壓縮等一系列"低級(jí)"事務(wù)留給它處理，使系統(tǒng)的核心部分集中對(duì)付排版 要求。每個(gè)參數(shù)都可以實(shí)現(xiàn)缺省值設(shè)置。上述排版參數(shù)的缺省值可以分別取56,60,10,5,5 和 1?！具x作內(nèi)容】

25、(1) 輸入文件名和輸出文件名要由用戶(hù)指定。(2) 允許用戶(hù)指定是否右對(duì)齊，即增加一個(gè)參量"右對(duì)齊否"(RightJustifying), 缺省值可設(shè)為"y"(yes)。右對(duì)齊指每行最后一個(gè)字的字尾 要對(duì)齊,多余的空格要均勻分布在本行中各字之間。(3) 實(shí)現(xiàn)字符填充(characterstuffing)技術(shù)。""作為分段控制符之后，限制了原文中不能有這樣的字。現(xiàn)在去掉這一限制：如果原文中有這樣的字，改用 兩個(gè)""并列起來(lái) 表示一個(gè)""字。當(dāng)然,如果原文中此符號(hào)夾在字中，就不必 特殊處理了。(4)

26、 允許用戶(hù)自動(dòng)按多欄印出一頁(yè)。12. 簡(jiǎn)單行編輯程序【問(wèn)題描述】文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對(duì)文本文 件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱(chēng)為行 編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法 既不經(jīng)濟(jì),也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文 件的一段放在內(nèi)存，稱(chēng)為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè) 文件每行不超過(guò)320個(gè)字符,很少超過(guò)80個(gè)字符。【基本要求】實(shí)現(xiàn)以下4條基本編輯命令:(1) 行插入。格式:i行號(hào) 回車(chē)v文本 . 回車(chē)將 文本插入活區(qū)中第 行號(hào)行之后。(2)

27、行刪除。格式:d行號(hào)1空格 行號(hào)2回車(chē)刪除活區(qū)中第 行號(hào)1行(到第 行號(hào)2行)。例如:"d10"和"d1014"。(3) 活區(qū)切換。格式*回車(chē)將活區(qū)寫(xiě)入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。(4) 活區(qū)顯示。格式:p回車(chē)逐頁(yè)地(每頁(yè)20行)顯示活區(qū)內(nèi)容，每顯示一頁(yè)之后請(qǐng)用戶(hù)決定是否 繼續(xù)顯示以后備頁(yè)(如果存在)。印出的每一行要前置行號(hào)和一個(gè)空格符， 行號(hào)固定占4位,增量為1。各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令 的行號(hào)可以等于活區(qū)第一行行號(hào)減1,表示插入當(dāng)前屏幕中第一行之前， 否則命令參數(shù)非法。【測(cè)試數(shù)據(jù)】自行設(shè)定,注意

28、測(cè)試將活區(qū)刪空等特殊情況?！緦?shí)現(xiàn)提示】(1) 設(shè)活區(qū)的大小用行數(shù)ActiveMULen(可設(shè)為100)來(lái)描述?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布,且峰值在60到70之間,用320x ActiveMULen大小的字符數(shù) 組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)。可以以標(biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ)，每個(gè)標(biāo)準(zhǔn) 行塊可含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài)鏈表連接起 來(lái)。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ASCII字符(如(012)8)標(biāo)識(shí)。此外,還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。(2) 初始化函數(shù)包括：請(qǐng)用戶(hù)提供輸入文件名(空串表示無(wú)輸入文件)和輸出文件名,兩者不能相同

29、。然后盡可能多地從輸入文件中讀入各行，但不超過(guò)ActiveMULen-LX的值可以自定,例如20。(3) 在執(zhí)行行插入命令的過(guò)程中，每接收到一行時(shí)都要檢查活區(qū)大小是否已達(dá)ActiveMaxLen。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過(guò) ActiveMaxLen應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中；若插入點(diǎn)為第一行之前，則只得將新插入的這一行輸出。(4) 若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部,以保持閱讀連續(xù)性；否則,它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。(5) 可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示?！具x作內(nèi)容】(1) 對(duì)于命令格式非法等一切錯(cuò)誤

30、作嚴(yán)格檢查和適當(dāng)處理。(2) 加入更復(fù)雜的編輯操作，如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配 等，格式可以為S行號(hào)串1串2回車(chē)和口串x回車(chē)。13. 串基本操作的演示【問(wèn)題描述】如果語(yǔ)言沒(méi)有把串作為一個(gè)預(yù)先定義好的基本類(lèi)型對(duì)待，又需要用該語(yǔ)言 寫(xiě)一個(gè)涉及串操作的軟件系統(tǒng)時(shí)，用戶(hù)必須自己實(shí)現(xiàn)串類(lèi)型。試實(shí)現(xiàn)串類(lèi)型，并 寫(xiě)一個(gè)串的基本操作的演示系統(tǒng)?！净疽蟆吭诮炭茣?shū)422節(jié)用堆分配存儲(chǔ)表示實(shí)現(xiàn)HString串類(lèi)型的最小操作子集的 基礎(chǔ)上,實(shí)現(xiàn)串抽象數(shù)據(jù)類(lèi)型的其余基本操作(不使用C語(yǔ)言本身提供的串函 數(shù))。參數(shù)合法性檢查必須嚴(yán)格。利用上述基本操作函數(shù)構(gòu)造以下系統(tǒng)：它是一個(gè)命令解釋程序，循環(huán)往復(fù)地 處

31、理用戶(hù)鍵入的每一條命令,直至終止程序的命令為止。命令定義如下：(1) 賦值。格式：A 串標(biāo)識(shí) 回車(chē)用串標(biāo)識(shí) 所表示的串的值建立新串,并顯示新串的內(nèi)部名和串值。例:AHi!'(2) 判相等。格式：E 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē)若兩串相等,則顯示"EQUAL",否則顯示"UNEQUAL"(3) 聯(lián)接。 格式:C 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē)將兩串拼接產(chǎn)生結(jié)果串，它的內(nèi)部名和串值都顯示出來(lái)。求長(zhǎng)度。格式：L串標(biāo)識(shí)回車(chē)顯示串的長(zhǎng)度。(5) 求子串。格式:S 串標(biāo)識(shí) +數(shù)1+數(shù)2回車(chē)如果參數(shù)合法，則顯示子串的內(nèi)部名和串值。 數(shù)不帶正負(fù)號(hào)。(6) 子串定位。格式:

32、I 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē) 顯示第二個(gè)串在第一個(gè)串中首次出現(xiàn)時(shí)的起始位置。(7) 串替換。格式：R 串標(biāo)識(shí)1 串標(biāo)識(shí)2 串標(biāo)識(shí)3 回車(chē)將第一個(gè)串中所有出現(xiàn)的第二個(gè)串用第三個(gè)串替換 ，顯示結(jié)果串的內(nèi)部名 和串值,原串不變。(8) 顯示。格式:P 回車(chē)精選范本，供參考！顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對(duì)照表。(9) 刪除。格式:D 內(nèi)部名 回車(chē)刪除該內(nèi)部名對(duì)應(yīng)的串，即賦值的逆操作。(10) 退出。格式：Q 回車(chē)結(jié)束程序的運(yùn)行。在上述命令中，如果一個(gè)自變量是串，則應(yīng)首先建立它?；静僮骱瘮?shù)的結(jié) 果(即函數(shù)值)如果是一個(gè)串，則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放。【測(cè)試數(shù)據(jù)】自定。但要包括以下

33、幾組：E回車(chē)，應(yīng)顯示"EQUAL"。(2) E abc' abcd'v 回車(chē)，應(yīng)顯示"UNEQUAL"。(3) C '' 回車(chē)，應(yīng)顯示"。(4) 1a' 回車(chē),應(yīng)報(bào)告:參數(shù)非法。(5) R aaa' aa' b'v回車(chē),應(yīng)顯示'ba '(6) R aaabc' a' aab'回車(chē),應(yīng)顯示'aabaabaabbc'。(7) R Faaaaaaaa aaaa'ab', 回車(chē) ,應(yīng)顯示'abab'。【

34、實(shí)現(xiàn)提示】【選作內(nèi)容】(1) 串頭表改用單鏈表實(shí)現(xiàn)。(2) 對(duì)命令的格式(即語(yǔ)法)作嚴(yán)格檢查,使系統(tǒng)既能處理正確的命令,也能 處理錯(cuò)誤的命令。注意，語(yǔ)義檢查(如某內(nèi)部名對(duì)應(yīng)的串已被刪除而無(wú)定義等) 和基本操作參數(shù)合法性檢查仍應(yīng)留給基本操作去做。(3) 支持串名。將串名(可設(shè)不超過(guò)6個(gè)字符)存于串頭表中。命令(1)(3)(5) 要增加命令參數(shù) 結(jié)果串名 ;命令中的 串標(biāo)識(shí)1改為串名,并用此名作 為結(jié)果串名，刪除原被替串標(biāo)識(shí)，用串名代替 串標(biāo)識(shí) 定義和命令解釋中的內(nèi) 部名。每個(gè)命令執(zhí)行完畢時(shí)立即自動(dòng)刪除無(wú)名串。14. 程序分析【問(wèn)題描述】讀入一個(gè)C程序,統(tǒng)計(jì)程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個(gè)

35、數(shù)和平 均行數(shù),并利用統(tǒng)計(jì)信息分析評(píng)價(jià)該程序的風(fēng)格?！净疽蟆?1) 把C程序文件按字符順序讀入源程序；(2) 邊讀入程序，邊識(shí)別統(tǒng)計(jì)代碼行、注釋行和空行，同時(shí)還要識(shí)別函數(shù)的 開(kāi)始和結(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í)級(jí)代碼(函數(shù)平均長(zhǎng)度)1015行89或1620行57或2124行<5或>24行注釋(占總行數(shù)比率)1525%1014或2630%59或 3135%<5滅 >35%空行(占總行數(shù)比率)1525%1014或2630%59或 3135%<5

36、滅 >35%【測(cè)試數(shù)據(jù)】先對(duì)較小的程序進(jìn)行分析。當(dāng)你的程序能正確運(yùn)行時(shí)，對(duì)你的程序本身進(jìn)行 分析。【實(shí)現(xiàn)提示】為了實(shí)現(xiàn)的方便，可作以下約定：(1) 頭兩個(gè)字符是FFF的行稱(chēng)為注釋行(該行不含語(yǔ)句)。除了空行和注釋 行外,其余均為代碼行(包括類(lèi)型定義、變量定義和函數(shù)頭)。(2) 每個(gè)函數(shù)代碼行數(shù)(除去空行和注釋行)稱(chēng)為該函數(shù)的長(zhǎng)度。(3) 每行最多只有一個(gè)"" 、""、"switch" 和"struet"( 便于識(shí)別函數(shù)的 結(jié)束行)。【選作內(nèi)容】(1) 報(bào)告函數(shù)的平均長(zhǎng)度(2) 找出最長(zhǎng)函數(shù)及其在程序中的位置。

37、(3) 允許函數(shù)的嵌套定義,報(bào)告最大的函數(shù)嵌套深度。15. 稀疏矩陣運(yùn)算器【問(wèn)題描述】稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用"稀疏"特點(diǎn)進(jìn)行存儲(chǔ)和計(jì) 算可以大大 節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算 的運(yùn)算器?！净疽蟆恳?quot;帶行邏輯鏈接信息"的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減 和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以 通常的陣列形式列出?！緦?shí)現(xiàn)提示】1. 首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要 求作的運(yùn)算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。2. 程

38、序可以對(duì)三元組的輸入順序加以限制 ，例如，按行優(yōu)先。注意研究教科 書(shū) 節(jié)中的算法，以便提高計(jì)算效率。3. 在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積 矩陣也 可用二維數(shù)組存放?！具x作內(nèi)容】1. 按教科書(shū)節(jié)中的描述方法，以十字鏈表表示稀疏矩陣。2. 增添矩陣求逆的運(yùn)算，包括不可求逆的情況。在求逆之前，先將稀疏 矩陣的內(nèi)部表示改為十字鏈表。16. 多維數(shù)組【問(wèn)題描述】設(shè)計(jì)并模擬實(shí)現(xiàn)整型多維數(shù)組類(lèi)型。【基本要求】盡管C等程序設(shè)計(jì)語(yǔ)言已經(jīng)提供了多維數(shù)組，但在某些情況下，定義用 戶(hù)所需的多維數(shù)組很有用的。通過(guò)設(shè)計(jì)并模擬實(shí)現(xiàn)多維數(shù)組類(lèi)型，可以深刻理解和掌握多維數(shù)組。整型多維數(shù)組應(yīng)具有

39、以下基本功能 ：(1) 定義整型多維數(shù)組類(lèi)型，各維的下標(biāo)是任意整數(shù)開(kāi)始的連續(xù)整數(shù)；(2) 下標(biāo)變量賦值，執(zhí)行下標(biāo)范圍檢查；(3同類(lèi)型數(shù)組賦值；(4) 子數(shù)組賦值，例如，a1.n=a2. n+1;a2.43.5=b1.32.4;(5) 確定數(shù)組的大小?！緶y(cè)試數(shù)據(jù)】由讀者指定?！緦?shí)現(xiàn)提示】各基本功能可以分別用函數(shù)模擬實(shí)現(xiàn)，應(yīng)仔細(xì)考慮函數(shù)參數(shù)的形式和設(shè) 置。定義整型多維數(shù)組類(lèi)型時(shí)，其類(lèi)型信息可以存儲(chǔ)在如下定義的類(lèi)型的記 錄中：# define MaxDim 5Typedef structint dim ,Boun dPtr lower ,Upper;Con stPtr con sta nts;)NA

40、rray,*NarrayPtr;整型多維數(shù)組變量的存儲(chǔ)結(jié)構(gòu)類(lèi)型可定義為T(mén)ypedef structElemType *elem;Int num;NArrayType TypeRecord;NArrayType;【選作內(nèi)容】(1) 各維的下標(biāo)是任意字符開(kāi)始的連續(xù)字符。(2) 數(shù)組初始化。(3) 可修改數(shù)組的下標(biāo)范圍。17. 簡(jiǎn)單LISP算術(shù)表達(dá)式計(jì)算器【問(wèn)題描述】設(shè)計(jì)一個(gè)簡(jiǎn)單的LISP算術(shù)表達(dá)式計(jì)算器。簡(jiǎn)單LISP算術(shù)表達(dá)式(以下簡(jiǎn)稱(chēng)表達(dá)式)定義如下：(1) 定義一個(gè)自然數(shù)(2) (運(yùn)算符表達(dá)式表達(dá)式)例如,6,(+45),(+(+25)8)都是表達(dá)式,其值分別為6,9和15?！净疽蟆繉?shí)現(xiàn)L

41、ISP加法表達(dá)式的求值。【測(cè)試數(shù)據(jù)】6,(+45),(+(+25)8),(+2(+58),(+(+(+12)(+34)(+(+56)(+78)【實(shí)現(xiàn)提示】寫(xiě)一個(gè)遞歸函數(shù)：int Evaluate(FILE * CharFile)字符文件CharFile的每行是一個(gè)如上定義的表達(dá)式。每讀入CharFile的一行,求出并返回表達(dá)式的值?？梢栽O(shè)計(jì)以下輔助函數(shù)status isNumber(char ReadInChar); / 視ReadInchar 是否是數(shù)字而返回TRUE或 FALSE。int TurnTol nteger(char In tChar);/將字符''9轉(zhuǎn)換為整數(shù)0

42、.9【選做內(nèi)容】(1) 標(biāo)準(zhǔn)整數(shù)類(lèi)型的LISP加法表達(dá)式的求值。(2) 標(biāo)準(zhǔn)整數(shù)類(lèi)型的LISP四則運(yùn)算表達(dá)式的求值。(3) LISP 算術(shù)表達(dá)式的語(yǔ)法檢查。18.重言式判別【問(wèn)題描述】一個(gè)邏輯表達(dá)式如果對(duì)于其變?cè)娜我环N取值都為真，則稱(chēng)為重言式；反之,如果對(duì)于其變?cè)娜我环N取值都為假，則稱(chēng)為矛盾式；然而，更多的情況下，既 非重言式，也非矛盾式。試寫(xiě)一個(gè)程序，通過(guò)真值表判別一個(gè)邏輯表達(dá)式屬于上 述哪一類(lèi)?！净疽蟆?1) 邏輯表達(dá)式從終端輸入，長(zhǎng)度不超過(guò)一行。邏輯運(yùn)算符包括"|"，"&"和""，分別表示或、與和非，運(yùn)算優(yōu)先程度

43、遞增，但可由括號(hào)改變，即括號(hào)內(nèi) 的運(yùn)算優(yōu)先。邏輯變?cè)?為大寫(xiě)字母。表達(dá)式中任何地方都可以含有多個(gè)空格符。(2) 若是重言式或矛盾式，可以只顯示 "True forever"，或"False forever"，否 則顯示"Satisfactible"以及變量名序列，與用戶(hù)交互。若用戶(hù)對(duì)表達(dá)式中變?cè)《ㄒ唤M值，程序就求出并顯示邏輯表達(dá)式的值?！緶y(cè)試數(shù)據(jù)】(1) (A|A)&(B卜B)(2) (A&A)&C(3) A|B|C|D|E|A(4) A&B&C&B(5) (A|B)&(AB)

44、(6) A&BA&B;0 ,0;0,1;1,0;1,1。19哈夫曼編/譯碼器【問(wèn)題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成 本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼， 在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信 道)，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。【基本要求】一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) 1:初始化(Initialization)。從終端讀入字符集大小 n ,以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。

45、(2) E :編碼(Encoding)。利用已建好的哈夫曼樹(shù) (如不在內(nèi)存，則從文件 hfmTree中讀人)，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。D:譯碼(Decoding)。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。(4) P:打印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrin中。(5) T:打印哈夫曼樹(shù)(Tree printing)。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式 (樹(shù)或凹入表形式)顯示在終端上，同時(shí)將

46、此字符形式的哈夫曼樹(shù)寫(xiě)入文件 TreePri nt 中?！緶y(cè)試數(shù)據(jù)】(1)利用教科書(shū)例6-2中的數(shù)據(jù)調(diào)試程序。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù),并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼："THIS PROGRAM IS MY FA VORITE"。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161【選作內(nèi)容】上述文件CodeFile中的每個(gè)"0"或"1"實(shí)際上占用了一個(gè)字節(jié)的空間，只起 到示意或模擬的作用。為

47、最大限度地利用編碼存儲(chǔ)能力， 試改寫(xiě)你的系統(tǒng)，將編 碼結(jié)果以二進(jìn)制形式存放在文件 CodeFile中。(2)修改你的系統(tǒng)，實(shí)現(xiàn)對(duì)你的系統(tǒng)的原程序的編碼和譯碼(主要是將行尾符編/譯碼冋題）0（3）實(shí)現(xiàn)各個(gè)轉(zhuǎn)換操作的源/目文件，均由用戶(hù)在選擇此操作時(shí)指定。20. 圖遍歷的演示【問(wèn)題描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫(xiě)一個(gè)程序，演示在連通的無(wú)向圖上訪問(wèn)全部結(jié)點(diǎn)的操作?！净疽蟆恳脏徑佣嘀乇頌榇鎯?chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。 以 用戶(hù)指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和相應(yīng)生成樹(shù)的邊 集?！緶y(cè)試數(shù)據(jù)】任選國(guó)內(nèi)城市，起點(diǎn)為合肥，暫時(shí)忽略里程?！?/p>

48、實(shí)現(xiàn)提示】設(shè)圖的結(jié)點(diǎn)20-30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)， 則它們的編號(hào)分別為1, 2,，n）。通過(guò)輸入圖的全部邊（存于數(shù)據(jù)文件中，從 文件讀寫(xiě)）輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。 注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒?！具x作內(nèi)容】（1）借助于棧類(lèi)型（自己定義和實(shí)現(xiàn)），用非遞歸算法實(shí)現(xiàn)深度優(yōu)先遍歷。（2）以鄰接表為存儲(chǔ)結(jié)構(gòu)，建立深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)，再按凹 入表或樹(shù)形打印生成樹(shù)。21. 教學(xué)計(jì)劃編制問(wèn)題【問(wèn)題描述】大學(xué)的每個(gè)專(zhuān)業(yè)都要制定教學(xué)計(jì)劃。 假設(shè)任何專(zhuān)業(yè)都有固定的學(xué)習(xí)年限，每 學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相

49、等。 每個(gè)專(zhuān)業(yè)開(kāi)設(shè)的課程都 是確定的，而且課程在開(kāi)設(shè)時(shí)間的安排必須滿(mǎn)足先修關(guān)系。每門(mén)課程有哪些先修 課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序?！净疽蟆?1) 輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門(mén)課的課程號(hào)(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號(hào)。(2) 允許用戶(hù)指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù) 擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。(3) 若根據(jù)給定的條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔?，否則將教學(xué)計(jì)劃輸出 到用戶(hù)指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)?！緶y(cè)試數(shù)據(jù)】學(xué)期總數(shù)：65

50、；學(xué)分上限：103；該專(zhuān)業(yè)共開(kāi)設(shè)12門(mén)課，課程號(hào)從CO1到 C12，學(xué)分順序?yàn)?, 3，4, 3, 2, 3, 4, 4, 7, 5, 2, 3。先修關(guān)系見(jiàn)教科書(shū)圖 7.26。22. 校園導(dǎo)游咨詢(xún)【問(wèn)題描述】設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢(xún)服務(wù)?！净疽蟆?1) 設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示 校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相 關(guān)信息。(2) 為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。(3) 為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的一 條最短的簡(jiǎn)單路徑?！緶y(cè)試數(shù)據(jù)】以合肥學(xué)院南

51、艷湖校區(qū)為例。【實(shí)現(xiàn)提示】一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊 均含有相關(guān)信息。【選作內(nèi)容】(1) 求校園圖的關(guān)節(jié)點(diǎn)。(2) 提供圖中任意景點(diǎn)問(wèn)路查詢(xún)，即求任意兩個(gè)景點(diǎn)之間的所有路徑。 提供校園圖中多個(gè)景點(diǎn)的最佳訪問(wèn)路線(xiàn)查詢(xún)，即求途經(jīng)這多個(gè)景點(diǎn)的最佳(短)路徑。(4) 校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。(5) 擴(kuò)充道路信息，如道路類(lèi)別(車(chē)道、人行道等)、沿途景色等級(jí)，以至可 按客人所需分別查詢(xún)?nèi)诵新窂交蜍?chē)行路徑或觀景路徑等。(6) 擴(kuò)充每個(gè)景點(diǎn)的鄰接景點(diǎn)的方向等信息，使得路徑查詢(xún)結(jié)果能提供詳盡的導(dǎo)向信息。(7) 實(shí)現(xiàn)校園導(dǎo)游圖的仿真界面。23. 圖書(shū)管理

52、【問(wèn)題描述】圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。【基本要求】1每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、著者、現(xiàn)存量和總庫(kù)存量等五項(xiàng)。2作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)(即關(guān)鍵字進(jìn)行的，所以要用B樹(shù)24樹(shù) 對(duì)書(shū)號(hào)建立索引，以獲得高效率。3系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及其功能定義如下： 采編入庫(kù)z新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)之后登記到圖書(shū)賬目中去。如果這種書(shū)在賬中已有，則只將總庫(kù)存量增加。 清除庫(kù)存:某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)賬目中注銷(xiāo)。 借閱:如果一

53、種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào) 和歸還期限。 歸還z注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。 顯示:以凹入表的形式顯示 B樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的?！緶y(cè)試數(shù)據(jù)】入庫(kù)書(shū)號(hào):35, 16,18,70,5,50, 22, 60,13,17,12, 45,25,氈，15,90, 30, 7然后清除:45, 90, 50, 22, 42其余數(shù)據(jù)自行設(shè)計(jì)。由空樹(shù)開(kāi)始，每插入刪除一個(gè)關(guān)鍵字后就顯示B樹(shù)的狀態(tài)?！緦?shí)現(xiàn)提示】(1) 24樹(shù)的查找算法是基礎(chǔ)，入庫(kù)和清除操作都要調(diào)用。難點(diǎn)在于刪除關(guān)鍵 字的算法，因而只要算法對(duì)2-3樹(shù)適用就可以了，暫時(shí)不必追求高階B樹(shù)也適用 的刪

54、除算法。(2) 每種書(shū)的記錄可以用動(dòng)(或靜)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。借閱登記信息可以鏈接在相應(yīng) 的那種書(shū)的記錄之后?！具x作內(nèi)容】(1) 將一次會(huì)話(huà)過(guò)程(即程序一次運(yùn)行)中的全部人機(jī)對(duì)話(huà)記入一個(gè)日志文件 "log"中去。(2) 增加列出某著者全部著作名的操作。思考如何提高這一操作的效率，參閱 教科書(shū)節(jié)。(3增加列出某種書(shū)狀態(tài)的操作。狀態(tài)信息除了包括這種書(shū)記錄的全部信息 外還包括最早到期(包括已逾期)的借閱者證號(hào)，日期可用整數(shù)實(shí)現(xiàn)，以求簡(jiǎn)化。(4) 增加預(yù)約借書(shū)功能。24. 多關(guān)鍵字排序【問(wèn)題描述】多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如：在進(jìn)行高考分?jǐn)?shù)處理時(shí)，除了 需對(duì)總分進(jìn)行排序外，不同

55、的專(zhuān)業(yè)對(duì)單科分?jǐn)?shù)的要求不同，因此尚需在總分相同 的情況下，按用戶(hù)提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序?！净疽蟆?1)假設(shè)待排序的記錄數(shù)不超過(guò)10000,表中記錄的關(guān)鍵字?jǐn)?shù)不超過(guò) 5,各個(gè) 關(guān)鍵字的范圍均為0至100。按用戶(hù)給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。(2)約定按LSD法進(jìn)行多關(guān)鍵字的排序。在對(duì)各個(gè)關(guān)鍵字進(jìn)行排序時(shí)采用兩 種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用"分配"和"收集"的方法。并綜 合比較這兩種策略?！緶y(cè)試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成?！緦?shí)現(xiàn)提示】用5至8組數(shù)據(jù)比較不同排序策略所需時(shí)間。由于是按LSD方法進(jìn)行排序，

56、 則對(duì)每個(gè)關(guān)鍵字均可進(jìn)行整個(gè)序列的排序， 但在利用通常的內(nèi)部排序方法進(jìn)行排 序時(shí)，必須選用穩(wěn)定的排序方法。借助"分配"和"收集"策略進(jìn)行的排序，如同一 趟"基數(shù)排序"，由于關(guān)鍵字的取值范圍為0至100，則分配時(shí)將得到104個(gè)鏈表?！具x作內(nèi)容】增添按MSD策略進(jìn)行排序，并和上述兩種排序策略進(jìn)行綜合比較。25手機(jī)通訊錄的制作設(shè)計(jì)目的：用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)。 編寫(xiě)一個(gè)手機(jī)通訊錄管理系統(tǒng)。 以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)應(yīng)用到實(shí)際軟件開(kāi)發(fā)中去。設(shè)計(jì)內(nèi)容:本系統(tǒng)應(yīng)完成一下幾方面的功能：（1）.添加信息（2）.顯示信息：它可以按按固定電話(huà)排列、按手機(jī)、聯(lián)系人名字的拼音順序排列。（3）.查找：可以不同的關(guān)鍵字作為查找的依據(jù)，進(jìn)行查找；（4）.編輯信息（5）.刪除信息（6）.保存到文件：將以上信息保存到文件，以便下次運(yùn)行程序時(shí)能載入此通信錄設(shè)計(jì)要求：（1） .每條信息至包含：姓名（NAME）,手機(jī)號(hào)，固定電話(huà)號(hào)，電子郵箱，QQ號(hào)碼，城市（CITY）郵編（EIP）幾項(xiàng)