數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)優(yōu)化版

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、課程設(shè)計的目的1. 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)課程所學(xué)知識的理解，了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法 的設(shè)計方法；2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基木方 法和技能；3. 提高綜合運用所學(xué)的理論知識和方法，獨立分析和解決問題的能力；4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所 應(yīng)具備的科學(xué)的工作方法和作風(fēng)；二、課程設(shè)計的要求（應(yīng)完成的工作）完成并上交的成果的內(nèi)容必須由以下兩個部分組成，缺一不可（該部分以電 子文件形式上交）：1上交源程序：學(xué)生按照課程設(shè)計的具體要求所開發(fā)的所有源程序（以“學(xué) 號姓名.cpp或.c”來命名）；2.

2、課程設(shè)計報告：（保存為word文檔中，文件名要求按照“學(xué)號姓名.docn 命名,即文件名為1706803*張三".doc）,中間不含其他任何符號。按照課程設(shè)計的具體要求建立相應(yīng)的功能模塊，每個模塊要求按照如下幾個 內(nèi)容認(rèn)真完成： 需求分析：在該部分中敘述模塊的劃分和各個模塊的功能要求； 概要設(shè)計:在此說明每個部分的算法設(shè)計說明（使用專業(yè)流程圖描述算法, 流程圖繪制工具指定為office_visio_pro_20（）7）,每個程序中使用的存儲結(jié)構(gòu)設(shè) 計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義）。 詳細(xì)設(shè)計及代碼實現(xiàn)：各個模塊實現(xiàn)的源程序，對每個題目要有相應(yīng)的源 程序（可以是一組源程

3、序，每個功能模塊采用不同的函數(shù)實現(xiàn)），源程序要按照 代碼書寫規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上 清晰的程序注釋。 測試分析：測試數(shù)據(jù)，測試輸出的結(jié)果（截圖說明），時間復(fù)雜度分析， 和每個模塊設(shè)計和調(diào)試時存在問題及解決方法，并提出相應(yīng)的算法的改進設(shè)想。課程總結(jié)：總結(jié)可以包括課程設(shè)計過程的收獲、遇到問題、遇到問題解決問 題過程的思考、程序調(diào)試的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計過程 中對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識等內(nèi)容。另外，報告還必須打印成紙質(zhì)文檔，正文用字體小四，行距1.25倍；代碼 用五號字體，行距用單倍行距；“核心代碼”部分添加“核心”的代碼，不允許 全部加入。

4、三、題目參考見附2。四、時間安排19周，五個半天的時間必須到教室完成設(shè)計。五、設(shè)計地點、信息樓208教室六、考核評分。根據(jù)提交的設(shè)計文檔（包括程序主要完成的功能、數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計 及專業(yè)流程圖、主耍代碼、程序中有何創(chuàng)新、有何收獲和所存在的不足以及需耍 改進的地方）和代碼（程序的功能實現(xiàn)）進行考核。要求:1 設(shè)計：思路清晰，設(shè)計可行。2文檔：文檔排版正確，思路清晰流暢，流程圖符合規(guī)范并構(gòu)圖效果好。3代碼：結(jié)構(gòu)清晰，注釋得當(dāng)，運行成功。4界面要求：每個功能應(yīng)該設(shè)立菜單，有合理的提示，根據(jù)提示，可以完成相關(guān)的功能要求。5封面使用統(tǒng)一格式，要求封面布局合理美觀。參考文獻1 嚴(yán)蔚敏、李冬梅、吳偉民

5、主編數(shù)據(jù)結(jié)構(gòu)（c語言版/第二版）人民郵電 出版社 20152 嚴(yán)蔚敏、吳偉民數(shù)據(jù)結(jié)構(gòu)習(xí)題集（c語言版） 清華大學(xué)出版社3 譚浩強編著面向?qū)ο蟪绦蛟O(shè)計（c+）清華大學(xué)出版社附：課程設(shè)計說明書內(nèi)容要求（示例）附1:課程設(shè)計說明書（示例）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書1706* * x x x一、設(shè)計時間2018 年 6 月 20 口 -2018 年 x 月 x 口二、設(shè)計地點湖南城市學(xué)院信息樓208教室三、設(shè)計目的1. 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)課程所學(xué)知識的理解，了解并掌握數(shù)據(jù)結(jié)構(gòu)與算 法的設(shè)計方法；2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本 方法和技能；3. 提高綜合運用所學(xué)的理論

6、知識和方法，獨立分析和解決問題的能力；4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者 所應(yīng)具備的科學(xué)的工作方法和作風(fēng)；5培養(yǎng)查閱資料，獨立思考問題的能力。四設(shè)計小組成員五.指導(dǎo)老師六設(shè)計課題七. 基本思路及關(guān)鍵問題的解決方法（需求分析和概要設(shè)計）八. 算法及流程圖（詳細(xì)設(shè)計）九. 調(diào)試過程中出現(xiàn)的問題及相應(yīng)解決辦法（調(diào)試分析）十課程設(shè)計心得體會（課程總結(jié)）十一源程序（核心代碼部分加上清晰的程序注釋）；參考文獻1 嚴(yán)蔚敏、李冬梅、吳偉民主編數(shù)據(jù)結(jié)構(gòu)（c語言版）清華大學(xué)岀版社20022 嚴(yán)蔚敏、吳偉民數(shù)據(jù)結(jié)構(gòu)習(xí)題集（c語言版） 清華大學(xué)出版社3 譚浩強編著面向?qū)ο蟪绦蛟O(shè)計（c

7、+）清華大學(xué)出版社附2：課程設(shè)計題目1. 運動會分?jǐn)?shù)統(tǒng)計【問題描述】參加運動會的n個學(xué)校編號為1刃。比賽分成/個男子項目和介女子項目， 項目編號分別為1/和加4卅由于各項目參加人數(shù)差別較大，有些項目取前 五名，得分順序為7, 5, 3, 2, 1；還有些項目只取前三名，得分順序為5, 3, 2。 寫一個統(tǒng)計程序產(chǎn)生各種成績單和得分報表?！净疽蟆?）可以輸入各個項目的前三名或前五名的成績；2）能統(tǒng)計各學(xué)?？偡郑?）可以按學(xué)校編號或名稱、學(xué)校總分、男女團體總分排序輸出；4）可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们?三或前五名的學(xué)校。5）數(shù)據(jù)存入文件并能隨時查詢6）規(guī)定：輸

8、入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運動項目的名稱輸出形式：有屮文提示，各學(xué)校分?jǐn)?shù)為整型。界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相 關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(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)定。例如，對于71=4, 777=3, w =2,編號為奇數(shù)的項目取前五名，編號為偶數(shù)的 項目取前三名，設(shè)計一組實例數(shù)據(jù)?！緦崿F(xiàn)提示】可以假設(shè)w20,加w30, ww20,姓名長度不超過20個字符。每個項目結(jié) 束時，將其編

9、號、類型符(區(qū)分取前五名述是前三名)輸入，并按名次順序輸入 運動員姓名、校名(和成績)?！具x作內(nèi)容】允許用戶指定某項目采取其他名次取法。2. 集合的并、交和差運算【問題描述】編制一個能演示執(zhí)行集合的并、交和差運算的程序?！净疽蟆?1) 集合的元素限定為小寫字母字符4a . o(2) 演示程序以用戶和計算機的對話方式執(zhí)行?！緶y試數(shù)據(jù)】(1 )setl 二”magazine”，set2="paper",setl u set2=uaegimnprz", setl nset2=haeh, set 1 -set2=ngimnzn o(2) setl= n 012oper

10、4a6tion89", set2="error data",setl uset2=madeinoprt", setl aset2="aeort", setl-set2=ninp"?！緦崿F(xiàn)提示】以有序鏈表表示集合。【選作內(nèi)容】(1) 集合的元素判定和子集判定運算。(2) 求集合的補集。(3) 集合的混合運算表達式求值。(4) 集合的元素類型推廣到其他類型，其至任意類型。3. 一元稀疏多項式計算器【問題描述】設(shè)計一個一元稀疏多項式簡單計算器?！净疽蟆恳辉∈瓒囗検胶唵斡嬎闫鞯幕竟δ苁牵?1) 輸入并建立多項式；輸出多項式，

11、輸出形式為整數(shù)序列：n, c” ei，c2，e?,，c”，e,?,其 中斤是多項式的項數(shù)，5和”分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降 序排列；(3) 多項式a和b相加，建立多項式a+b；(4) 多項式a和b相減，建立多項式a"?！緶y試數(shù)據(jù)】(1) (2x+5x8-3x") + (7 5x8+1 収9)=(一3.1宀+1 lx°+2x+7)(2) (6x 3-x+4.4x2一 1.2x°) 一(.6x-3+5 4x2一x2+7.8x15)=(-7.8x15-1.2x9+12x'3-x)(3) (1 +x + x2+x3+x4+x5)+(-x3x4

12、)=( 1 +x+x2+x5)(4) (x+x')+(xx3)=0(5) (x4-x1>(x100 4-x20v(x4-2xkw00)(6) (x+x2+x3)+0=x+x2+x3(7) 互換上述測試數(shù)據(jù)屮的前后兩個多項式【實現(xiàn)提示】用帶表頭結(jié)點的單鏈表存儲多項式?！具x作內(nèi)容】(1) 計算多項式在x處的值。(2) 求多項式a的導(dǎo)函數(shù)n o(3) 多項式a和b相乘，建立乘積多項式ab o多項式的輸出形式為類數(shù)學(xué)表達式。例如,多項式-3x8+6x3-18的輸 出形式為-3xa8 + 6xa3-18, x,5+(-8)x7-14的輸出形式為xa15-8xa7-14o 注意，數(shù) 值為1的

13、非零次項的輸出形式中略去系數(shù)1,如項1/的輸出形式為項一1f 的輸岀形式為一x3 o(5) 計算器的仿真界。4. 池塘夜降彩色雨【問題描述】設(shè)計一個程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點飄飄灑灑地 從天而降，滴滴入水有聲，濺起圈圈微瀾?！净疽蟆?1) 雨點的空中出現(xiàn)位置、降范過程的可見程度、入水位置、顏色、最大水 圈等，都是隨機確定的;(2) 多個雨點按照各自的隨機參數(shù)和存在狀態(tài)，同時演示在屏幕上?！緶y試數(shù)據(jù)】適當(dāng)調(diào)整控制雨點密度、最大水圈和狀態(tài)變化的吋間間隔等參數(shù)?！緦崿F(xiàn)提示】(1) 每個雨點的存在周期可分為三個階段：從天而降、入水有聲和圈圈微瀾, 需要一個記錄存儲其相關(guān)參數(shù)、

14、當(dāng)前狀態(tài)和下一狀態(tài)的更新時刻。(2) 在圖形狀態(tài)編程。雨點下降的可見程度應(yīng)是斷斷續(xù)續(xù)、依稀可見；圈圈 水波應(yīng)是由里至外逐漸擴大和消失。(3) 每個雨點發(fā)生時，生成其記錄，并預(yù)置下一個雨點的發(fā)生時間。(4) 用一個適當(dāng)?shù)慕Y(jié)構(gòu)管理當(dāng)前存在的雨點，使系統(tǒng)能利用它按時更新每個 雨點的狀態(tài)，一旦有雨點的水圈全部消失，就從結(jié)構(gòu)中刪去?！具x作內(nèi)容】(1) 增加“電閃雷鳴”景象。(2) 增加風(fēng)的效果，展現(xiàn)“風(fēng)雨飄搖”的情景。(3) 增加雨點密度的變化：時而“和風(fēng)細(xì)雨”，時而“暴風(fēng)驟雨”。（4）將“池塘”改為“荷塘”，雨點滴在荷葉上的效果是濺起四散的水珠， 響聲也不同。5. 銀行業(yè)務(wù)模擬【問題描述】客戶業(yè)務(wù)分為

15、兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第 二種是向銀行投入一筆資金，即存款或還款。銀行有兩個服務(wù)窗口，相應(yīng)地有兩 個隊列?？蛻舻竭_銀行后先排第一個隊。處理每個客戶業(yè)務(wù)時，如果屬于第一種, 且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個隊等候，直至 滿足時才離開銀行；否則業(yè)務(wù)處理完后立刻離開銀行。每接待完一個第二種業(yè)務(wù) 的客戶，貝ij順序檢查和處理（如果可能）第二個隊列中的客戶，對能滿足的申請者 予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一 旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶（第二種業(yè)務(wù)）被接 待之前的數(shù)額，或者本次已將第二個

16、隊列檢查或處理了一遍，就停止檢查（因為 此時已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個隊列的客戶。任何時刻都只開 一個窗口。假設(shè)檢查不需要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務(wù)的事件驅(qū)動模擬系統(tǒng)，通過模擬方法求岀客戶在銀行內(nèi)逗留 的平均時間?！净疽蟆坷脛討B(tài)存儲結(jié)構(gòu)實現(xiàn)模擬?！緶y試數(shù)據(jù)】一天營業(yè)開始吋銀行擁有的款額為10000（元），營業(yè)吋間為600（分鐘）。其他 模擬參量自定，注意測定兩種極端的情況：一是兩個到達事件之間的間隔時間很短，而 客戶的交易時間很長，另一個恰好相反，設(shè)置兩個到達事件的間隔時間很長，而 客戶的交易時間很短。【實現(xiàn)提示】事件有兩類：到達銀行和離開

17、銀行。初始時銀行現(xiàn)存資金總額為total。開始 營業(yè)后的第一今事件是客戶到達，營業(yè)時間從0到closetimeo到達事件發(fā)生時隨 機地設(shè)置此客戶的交易時間和距下一到達事件之間的時間間隔。毎個客戶要辦理 的款額也是隨機確定的，用負(fù)值和正值分別表示第一類和第二類業(yè)務(wù)。變量total, closetime以及上述兩個隨機量的上下界均交互地從終端讀入，作為模擬參數(shù)。兩個隊列和一個事件表均要用動態(tài)存儲結(jié)構(gòu)實現(xiàn)。注意弄清應(yīng)該在什么條件下設(shè) 置離開事件，以及第二個隊列用怎樣的存儲結(jié)構(gòu)實現(xiàn)時可以獲得較高的效率。注 意：事件表是按時間順序有序的?！具x作內(nèi)容】自己實現(xiàn)動態(tài)數(shù)據(jù)類型。例如對于客戶結(jié)點，定義pool為

18、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ù)可取名為my free, 其作用是把該分量入錢。用for-tran和basic等語言實現(xiàn)時只能如此地自行 組織?！締栴}描述】設(shè)計一個國際象棋的馬踏遍棋盤的演示程序。【基本要求

19、】將馬隨機放在國際象棋的8x8棋盤board的某個方格中，馬按走棋規(guī)則 進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。編制非遞歸 程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1, 2,，64依次填 入一個8x8的方陣，輸出z。7.魔王語言解釋【問題描述】有一個魔王總是使用a己的一種非常精練而抽象的語言講話，沒有人能昕得 懂，但他的語言是可以逐步解釋成人能聽懂的語言，因為他的語言是由以下兩種 形式的規(guī)則由人的語言逐步抽象上去的：(1) qt002 尤(2) (州為戈)t如住t陽&在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統(tǒng)，把 他的話解釋成人能聽得懂

20、的話。【基本要求】用下述兩條具體規(guī)則和上述規(guī)則形式(2)實現(xiàn)。設(shè)大寫字母表示魔王語言的 詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代 換的變量。魔王語言可含人的詞匯。(1) b »ada(2) a t sae【測試數(shù)據(jù)】b(ehnxgz)b 解釋成 tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是“天上一只 鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕下蛋恨【實現(xiàn)提示】將魔王的語言自右至左進棧，總是處理棧頂字符。若是開括號，則逐一出棧, 將字母順序

21、入隊列，直至閉括號出棧，并按規(guī)則要求逐一出隊列再處理后入棧。 其他情形較簡單，請讀者思考應(yīng)如何處理。應(yīng)首先實現(xiàn)棧和隊列的基本操作。【選作內(nèi)容】(1) 由于問題的特殊性，可以實現(xiàn)棧和隊列的順序存儲空間共享。(2) 代換變量的數(shù)目不限，則在程序開始運行時首先讀入一組第一種形式的 規(guī)則，而不是把規(guī)則固定在程序屮(第二種形式的規(guī)則只能固定在程序屮)。.航空客運訂票系統(tǒng)【問題描述】航空客運訂票的業(yè)務(wù)活動包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計 一個航空客運訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計算機來完成?！净疽蟆浚?）每條航線所涉及的信息有：終點站名、航班號、飛機號、飛行周日（星期 幾）、乘員定額、余

22、票量、已訂票的客戶名單（包括姓名、訂票量、艙位等級1, 2 或3）以及等候替補的客戶名單（包括姓名、所需票量）；（2）系統(tǒng)能實現(xiàn)的操作和功能如下： 錄入：可以錄入航班情況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲在文件 中； 查詢航線：根據(jù)旅客提出的終點站名輸出下列信息：航班號、飛機號、星 期兒飛行，最近一天航班的日期和余票額； 承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額 情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少 于訂票額，則需重新詢問客戶要求。若需要，可登記排隊候補； 承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況（日期、航班），為客戶辦理退票手續(xù), 然后查

23、詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿 足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊候補的客戶?！緶y試數(shù)據(jù)】由讀者自行指定?！緦崿F(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個域、其中乘 員名單域為指向乘員名單鏈表的頭指針，等候替補的客戶名單域為分別指向隊頭 和

24、隊尾的指針?！具x作內(nèi)容】當(dāng)客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達同一目的地的其他航線 情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項目。9. 藥店的藥品銷售統(tǒng)計系統(tǒng)【問題描述】設(shè)計一系統(tǒng),實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、 單價、銷售量或銷售額做出排名?！净疽蟆吭诒驹O(shè)計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥 品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4 位，采用字母和數(shù)字混合編號，女山a125,前一位為大寫字母，后三位為數(shù)字， 按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量

25、或銷售額 進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直 接選擇排序等方法。在本設(shè)計中，對單價的排序采用冒泡排序法，對銷售量的排 序采用快速排序法，對銷售額的排序采用堆排序法。10. 文學(xué)研究助手【問題描述】文學(xué)研究人員需要統(tǒng)計某篇英文小說屮某些形容詞的出現(xiàn)次數(shù)和位置。試 寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)，稱為文學(xué)研究助手?！净疽蟆坑⑽男≌f存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計 工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn) 次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計?！緶y試數(shù)據(jù)】以你的c源程序模擬英文小說,c語言的保留字集作

26、為待統(tǒng)計的詞匯集。【實現(xiàn)提示】約定小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的 出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次, 不必存多個相同的行號。如果讀者希望達到選做部分(1)和(2)所提出的要求，則首先應(yīng)把kmp算法改 寫成如下的等價形式，再將它推廣到多個模式的情形。i=l；j=l；while(i!=s curlen+1&&j!=t curlerl十1)while(j!=0&&s. chi !=t. chj)j=nextj;/j=0或s. chi=t. chjj+；i+；/每次進入循環(huán)體，i只增加一次i【選作內(nèi)容

27、】(1) 模式匹配要基于kmp算法。(2) 整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。(3) 假設(shè)小說中的每個單詞或者從行首開始,或者前置一個空格符。利用單詞 匹配特點另寫一個高效的統(tǒng)計程序，與kmp算法統(tǒng)計程序進行效率比較。(4) 推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行(提示:定義 操作gctachar)。11.文本格式化【問題描述】輸入文件中含有待格式化或稱為待排版的文本，它由多行的文字組成， 例如一篇英文文章。每一行由一系列被一個或多個空格符所隔開的字組成， 任何完整的字都沒有被分割在兩行(毎行最后一個字與下一行的第一個字之間 在邏輯上應(yīng)該由空格分開)，每行字符數(shù)不超過

28、80。除了上述文本類字符之外， 還存在著起控制作用的字符:符號解指示它后面的正文在格式化時應(yīng)另起一段 排放，即空一行,并在段首縮入8個字符位置。解自成一個字。一個文木格式化程序可以處理上述輸入文件,按照用戶指定的版面規(guī)格重 排版面z實現(xiàn)頁內(nèi)調(diào)整、分段、分頁等文本處理功能，排版結(jié)果存入輸岀文本文件中。試寫一個這樣的程序。【基本要求】(1) 輸岀文件中字與字之間只留一個空格符,即實現(xiàn)多余空格符的壓縮。(2) 在輸出文件中，任何完整的字仍不能分割在兩行，行尾不齊沒關(guān)系，但行 首要對齊(即左對齊)。(3) 如果所要求的每頁頁底所空行數(shù)不少于3,則將頁號印在頁底空行中第 2行的屮間位置上，否則不印。(4

29、) 版面要求的參數(shù)要包含：頁長(pagelength) 一一每頁內(nèi)文字(不計頁號)的行數(shù)。 頁寬(pagewedth)每行內(nèi)文字所占最大字符數(shù)。左空白(lcftmargin)-每行文字前的固定空格數(shù)。頭長(lleadinglength)每頁頁頂所空行數(shù)。腳長(footinglength)每頁頁底所空行數(shù)(含頁號行)。起始頁號(start ingpagenumber)首頁的頁號?！緶y試數(shù)據(jù)】略。注意在標(biāo)點之后加上空格符?！緦崿F(xiàn)提示】可以設(shè):左空h數(shù)x2+頁寬=160,即行印機最大行寬,從而只要設(shè)置這樣大 的一個行緩沖區(qū)就足夠了，每加工完一行,就輸出一行。如果輸入文件和輸出文件不是由程序規(guī)定死，而

30、是可由用戶指定，則有兩種 做法:一是像其他參量一樣，將文件名交互地讀入字符串變量屮；更好的方式是 讓用戶通過命令行指定,具體做法依機器的操作系統(tǒng)而定。應(yīng)該首先實現(xiàn)getaword(w)這一操作，把諸如行尾處理、文件尾處理、多余 空格符壓縮等一系列低級事務(wù)留給它處理，使系統(tǒng)的核心部分集中對付排版 要求。每個參數(shù)都可以實現(xiàn)缺省值設(shè)置。上述排版參數(shù)的缺省值可以分別取 56, 60, 10, 5, 5和 1?！具x作內(nèi)容】(1) 輸入文件名和輸出文件名要由用戶指定。(2) 允許用戶指定是否右對齊，即增加一個參量右對齊否 (rightjustifying),缺省值可設(shè)為"y(yes)。右對齊指每

31、行最后一個字的字尾要對齊，多余的空格要均勻分布在本行中各字之間。(3) 實現(xiàn)字符填充(characterstuffing)技術(shù)。作為分段控制符之后，限 制了原文中不能有這樣的字?，F(xiàn)在去掉這一限制：如果原文中有這樣的字，改用 兩個飛并列起來 表示一個飛字。當(dāng)然，如果原文中此符號夾在字中,就不必 特殊處理了。(4) 允許用戶自動按多欄印岀一頁。12. 簡單行編輯程序【問題描述】文木編輯程序是利用計算機進行文字加工的基木軟件工具,實現(xiàn)對文木文 件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行 編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法 既不經(jīng)濟，

32、也不總能實現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文 件的一段放在內(nèi)存，稱為活區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程序。設(shè) 文件毎行不超過320個字符，很少超過80個字符?！净疽蟆繉崿F(xiàn)以下4條基本編輯命令：(1) 行插入。格式：i行號冋車文本冋車 將文木插入活區(qū)中第行號 行之后。(2) 行刪除。格式:d行號1空格行號2回車刪除活區(qū)中第行號1行(到第行號2行)。例如:dl0和dl014。(3) 活區(qū)切換。格式*回車將活區(qū)寫入輸岀文件，并從輸入文件中讀入下一段，作為新的活區(qū)。(4) 活區(qū)顯示。格式:p回車逐頁地(每頁20行)顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是否 繼續(xù)顯示以后備頁

33、(如果存在)。印出的每一行要前置行號和一個空格符， 行號固定占4位,增量為1。各條命令屮的行號均須在活區(qū)屮各行行號范圍z內(nèi)，只有插入命令 的行號可以等于活區(qū)第一行行號減1,表示插入當(dāng)前屏幕中第一行之前， 否則命令參數(shù)非法?！緶y試數(shù)據(jù)】自行設(shè)定,注意測試將活區(qū)刪空等特殊情況。【實現(xiàn)提示】(1) 設(shè)活區(qū)的大小用行數(shù)activemulen(可設(shè)為100)來描述?？紤]到文本文件 行長通常為正態(tài)分布，且峰值在60到70之間，用320xactivemulen大小的字符數(shù) 組實現(xiàn)存儲將造成大量浪費?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲，毎個標(biāo)準(zhǔn) 行塊可含81個字符。這些行塊可以組成一個數(shù)組，也可以利用動態(tài)鏈表

34、連接起 來。一行文字可能占多個行塊。行尾可用一個特殊的asch字符(如(012) 8)標(biāo) 識。此外，還應(yīng)記住活區(qū)起始行號。行插入將引起隨后各行行號的順序下推。(2) 初始化函數(shù)包括:請用戶提供輸入文件名(空串表示無輸入文件)和輸出 文件名，兩者不能相同。然后盡可能多地從輸入文件中讀入各行，但不超過 activcmulcn-lx的值可以自定，例如20。(3) 在執(zhí)行行插入命令的過程中，每接收到一行吋都要檢查活區(qū)大小是否已 達activemaxleno如果是，則為了在插入這一行之后仍保持活區(qū)大小不超過 ac t i vemaxlen應(yīng)將插入點之前的活區(qū)部分中第一行輸岀到輸岀文件中；若插入 點為第一

35、行之前，則只得將新插入的這一行輸出。(4) 若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)屮最后幾行留在活區(qū)頂 部，以保持閱讀連續(xù)性;否則，它意味著結(jié)束編輯或開始編輯另一個文件。(5) 可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示?！具x作內(nèi)容】(1) 對于命令格式非法等一切錯誤作嚴(yán)格檢查和適當(dāng)處理。(2) 加入更復(fù)雜的編輯操作，如對某行進行串替換；在活區(qū)內(nèi)進行模式匹配 等，格式可以為s行號串1敗串2冋車和m串x冋車。13. 串基本操作的演示【問題描述】如果語言沒有把串作為一個預(yù)先定義好的基本類型對待，又需要用該語言 寫一個涉及串操作的軟件系統(tǒng)時，用戶必須自己實現(xiàn)串類型。試實現(xiàn)串類型，并 寫一個串的基本操作

36、的演示系統(tǒng)。【基本要求】在教科書42. 2節(jié)用堆分配存儲表示實現(xiàn)hstring串類型的最小操作子集的 基礎(chǔ)上，實現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不使用c語言本身提供的串函 數(shù))。參數(shù)合法性檢查必須嚴(yán)格。利用上述基木操作函數(shù)構(gòu)造以下系統(tǒng):它是一個命令解釋程序，循環(huán)往復(fù)地 處理用戶鍵入的每一條命令，直至終止程序的命令為止。命令定義如下：賦值。 格式：a串標(biāo)識回車用串標(biāo)識所表示的串的值建立新串，并顯示新串的內(nèi)部名和串值。例:ahi!'(2) 判相等。格式：e串標(biāo)識1 串標(biāo)識2 回車若兩串相等,則顯示"equal",否則顯示"unequal"。(3) 聯(lián)

37、接。格式:c串標(biāo)識1串標(biāo)識2回車將兩串拼接產(chǎn)生結(jié)果串，它的內(nèi)部名和串值都顯示出來。(4) 求長度。格式:l串標(biāo)識冋車顯不串的長度。(5) 求子串。格式:s串標(biāo)識+數(shù)1+數(shù)2回車如果參數(shù)合法，則顯示子串的內(nèi)部名和串值。數(shù)不帶正負(fù)號。(6) 子串定位。格式:1串標(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)的串，即賦

38、值的逆操作。(10) 退出。格式:q回車結(jié)束程序的運行。在上述命令中，如果一個自變量是串，則應(yīng)首先建立它?；静僮骱瘮?shù)的結(jié) 果(即函數(shù)值)如果是一個串，則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放?！緶y試數(shù)據(jù)】自定。但要包括以下兒組：(1) e “ c'v回車，應(yīng)顯示”equal”。(2) e wbc' 4abedv回車，應(yīng)顯示“unequal”。(3) c6 6v回車，應(yīng)顯示”。(4) 1 w "回車,應(yīng)報告:參數(shù)非法。(5) r 6aaa?，aa'回車,應(yīng)顯示'ba，(6) r aaabc,匕''aabx回車，應(yīng)顯示'aabaabaa

39、bbe'。(7) r taaaaaaaa9 'aaaa, 4ab 回車，應(yīng)顯示'abeib'?！緦崿F(xiàn)提示】【選作內(nèi)容】(1) 串頭表改用單鏈表實現(xiàn)。(2) 對命令的格式(即語法)作嚴(yán)格檢查,使系統(tǒng)既能處理正確的命令，也能 處理錯誤的命令。注意，語義檢查(如某內(nèi)部名對應(yīng)的串已被刪除而無定義等) 和基木操作參數(shù)合法性檢查仍應(yīng)留給基木操作去做。(3) 支持串名。將串名(可設(shè)不超過6個字符)存于串頭表中。命令(1) (3) (5) 要增加命令參數(shù)結(jié)果串名;命令(7)中的串標(biāo)識1改為串名，并用此名作 為結(jié)果串名，刪除原被替串標(biāo)識，用串名代替串標(biāo)識定義和命令解釋屮的內(nèi) 部名

40、。每個命令執(zhí)行完畢時立即自動刪除無名串。14.程序分析【問題描述】讀入一個c程序，統(tǒng)計程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個數(shù)和平 均行數(shù)，并利用統(tǒng)計信息分析評價該程序的風(fēng)格。【基本要求】（1）把c程序文件按字符順序讀入源程序；（2）邊讀入程序,邊識別統(tǒng)計代碼行、注釋行和空行，同時還要識別函數(shù)的 開始和結(jié)束，以便統(tǒng)計其個數(shù)和平均行數(shù)。（3）程序的風(fēng)格評價分為代碼、注釋和空行三個方面。每個方面分為a, b,c 和d四個等級，等級的劃分標(biāo)準(zhǔn)是：a級b級c級d級代碼（幣數(shù)平均長度）1015彳亍89或 1620 行57或2廣24行5或24行注釋（占總行數(shù)比率）忙25%1014或2630%5為或3廣3

41、5%5%或35%空行（占總行數(shù)比率）15 25%1014或2630%59或 3135%5%或35%【測試數(shù)據(jù)】先對較小的程序進行分析。當(dāng)你的程序能止確運行時，對你的程序本身進行分析?！緦崿F(xiàn)提示】為了實現(xiàn)的方便，可作以下約定：（1）頭兩個字符是fff的行稱為注釋行（該行不含語句）。除了空行和注釋 行外，其余均為代碼行（包括類型定義、變量定義和函數(shù)頭）。（2）每個函數(shù)代碼行數(shù)（除去空行和注釋行）稱為該函數(shù)的長度。（3）每行最多只有一個、switch和stmet（便于識別函數(shù)的 結(jié)束行）?！具x作內(nèi)容】仃）報告函數(shù)的平均長度。(2) 找出最長函數(shù)及其在程序中的位置。(3) 允許函數(shù)的嵌套定義，報告最大

42、的函數(shù)嵌套深度。15.稀疏矩陣運算器【問題描述】稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用稀疏特點進行存儲和計 算可以大大節(jié)省存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算 的運算器?！净疽蟆恳詭羞壿嬫溄有畔⒌娜M順序表表示稀疏矩陣,實現(xiàn)兩個矩陣相加、相減 和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)果的矩陣則以 通常的陣列形式列出?！緦崿F(xiàn)提示】1. 首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要 求作的運算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20 o2. 程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科 書 5. 3.2節(jié)中的

43、算法，以便提高計算效率。3. 在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積 矩陣也 可用二維數(shù)組存放?！具x作內(nèi)容】1. 按教科書5. 3.2節(jié)中的描述方法，以十字鏈表表示稀疏矩陣。2. 增添矩陣求逆的運算，包括不可求逆的情況。在求逆之前，先將稀疏 矩陣的內(nèi)部表示改為十字鏈表。16.多維數(shù)組【問題描述】設(shè)計并模擬實現(xiàn)整型多維數(shù)組類型?！净疽蟆勘M管c等程序設(shè)計語言已經(jīng)提供了多維數(shù)組，但在某些情況下，定義用 戶所需的多維數(shù)組很有用的。通過設(shè)計并模擬實現(xiàn)多維數(shù)組類型，可以深刻理 解和掌握多維數(shù)組。整型多維數(shù)組應(yīng)具有以下基木功能：(1) 定義整型多維數(shù)組類型，各維的下標(biāo)是任意整數(shù)

44、開始的連續(xù)整數(shù)；(2) 下標(biāo)變量賦值，執(zhí)行下標(biāo)范圍檢查；(3同類型數(shù)組賦值；(4) 子數(shù)組賦值，例如，eil.nf2. n+l;a2. 4 3. 5二bl. 3 2. 4;(5) 確定數(shù)組的大小?！緶y試數(shù)據(jù)】由讀者指定?！緦崿F(xiàn)提示】各基木功能可以分別用函數(shù)模擬實現(xiàn)，應(yīng)仔細(xì)考慮函數(shù)參數(shù)的形式和設(shè) 置。定義整型多維數(shù)組類型時，其類型信息可以存儲在如下定義的類型的記 錄中：#define maxdim 5typedef struetint dim ,boundptr lower ,upper;constptr constants;)narray, *narrayptr;整型多維數(shù)組變量的存儲結(jié)構(gòu)類型

45、可定義為:typedef struetelemtype *elem;int num;narraytype typerecord;narraytype;【選作內(nèi)容】(1) 各維的下標(biāo)是任意字符開始的連續(xù)字符。(2) 數(shù)組初始化。(3) 可修改數(shù)組的下標(biāo)范圍。17.簡單lisp算術(shù)表達式計算器【問題描述】設(shè)計一個簡單的lisp算術(shù)表達式計算器。簡單lisp算術(shù)表達式(以下簡稱表達式)定義如下：(1) 定義一個自然數(shù)(2) (運算符表達式表達式)例如,6, (+45), (+(+25)8)都是表達式，其值分別為6, 9和15。【基木要求】實現(xiàn)lisp加法表達式的求值?！緶y試數(shù)據(jù)】6, (+45),

46、(+(+25)8), (+2(+58), (+(+(+12) (+34) (+(+56) (+78)【實現(xiàn)提示】寫一個遞歸函數(shù)：int evaluate(file * charfile)字符文件charfile的每行是一個如上定義的表達式。每讀入charfile的一行, 求出并返回表達式的值?？梢栽O(shè)計以下輔助函數(shù)status isnumber (char readlnchar) ;/視readinchar 是否是數(shù)字而返回true 或 false 。int turntolnteger(char intchar) ;/ 將字符'o'. 9 轉(zhuǎn)換為整數(shù)0. .9【選做內(nèi)容】(1)

47、標(biāo)準(zhǔn)整數(shù)類型的ltsp加法表達式的求值。(2) 標(biāo)準(zhǔn)整數(shù)類型的lisp四則運算表達式的求值。(3) lisp算術(shù)表達式的語法檢查。18.重言式判別【問題描述】一個邏輯表達式如果對于其變元的任一種取值都為真，則稱為重言式;反之, 如果對于其變元的任一種取值都為假，則稱為叩盾式；然而，更多的情況下，既 非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達式屬于上 述哪一類?！净疽蟆?1) 邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括t，”&“和 ”，分別表示或、與和非，運算優(yōu)先程度遞增，但可由括號改變，即括號內(nèi)的 運算優(yōu)先。邏輯變元 為大寫字母。表達式屮任何地方都可以

48、含有多個空格符。(2) 若是重言式或矛盾式，可以只顯"true forever",或'false forever",否 則顯示"satisfactible"以及變量名序列，與用戶交互。若用戶對表達式中變元取 定一組值，程序就求出并顯示邏輯表達式的值。【測試數(shù)據(jù)】(1) (a|-a)&(bab)(2) (a&a)&c(3) a|b|c|d|e 卜 a(4) a&b&c&b(5) (a|b)&(a卜b)(6) a&b 卜 a&b;0,0;0,1;1,0;1,1。19.哈

49、夫曼編/譯碼器【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降 低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼， 在接收端將傳來的數(shù)據(jù)進行譯碼(復(fù)原)。對于雙工信道(即可以雙向傳輸信息的信 道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€完整的系統(tǒng)應(yīng)具有以下功能：(1) 1：初始化(initialization)o從終端讀入字符集大小n ,以及n個字符和n 個權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree中。(2) e：編碼(encoding)o利用已建好的哈夫曼樹(如不在內(nèi)存，則從文

50、件 hfmtree中讀人)，對文件tobetran中的正文進行編碼，然后將結(jié)果存入文件 codefile 中。(3) d:譯碼(decoding)。利用已建好的哈夫曼樹將文件codefile中的代碼進 行譯碼，結(jié)果存入文件textfile中。(4) p：打印代碼文件(print)o將文件codefile以緊湊格式顯示在終端上，每 行50個代碼。同時將此字符形式的編碼文件寫入文件codeprin中。(5) t：打印哈夫曼w(tree printing)o將已在內(nèi)存中的哈夫曼樹以直觀的方式 (樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 treeprint 中?！緶y試數(shù)據(jù)】(1

51、) 利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。(2) 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼this program is my favorite%字符abcdefghijklm頻度1866413223210321154757153220字符nopqrstuvwxyz頻度5763151485180238181161【選作內(nèi)容】上述文件codefile中的每個”0”或t”實際上占用了一個字節(jié)的空間，只起 到示意或模擬的作用。為最大限度地利用編碼存儲能力，試改寫你的系統(tǒng)，將編 碼結(jié)果以二進制形式存放在文件codefile中。(2)修改你的系統(tǒng)，實現(xiàn)對你的系統(tǒng)的原程

52、序的編碼和譯碼(主要是將行尾符編/譯碼問題)。(3) 實現(xiàn)各個轉(zhuǎn)換操作的源/目文件，均由用戶在選擇此操作時指定。20.圖遍歷的演示ll-【問題描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演 示在連通的無向圖上訪問全部結(jié)點的操作?！净疽蟆恳脏徑佣嘀乇頌榇鎯Y(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以 用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊 集?！緶y試數(shù)據(jù)】任選國內(nèi)城市，起點為合肥，暫時忽略里程?！緦崿F(xiàn)提示】設(shè)圖的結(jié)點20-30個，每個結(jié)點用一個編號表示(如果一個圖有n個結(jié)點， 則它們的編號分別為1, 2,，n)。通過輸入圖的全部邊

53、(存于數(shù)據(jù)文件中，從 文件讀寫)輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。 注意，牛成樹的邊是有向邊，端點順序不能顛倒。(1)借助于棧類型(自己定義和實現(xiàn))，用非遞歸算法實現(xiàn)深度優(yōu)先遍歷。(2) 以鄰接表為存儲結(jié)構(gòu)，建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹 入表或樹形打印生成樹。(3) 兩個城市最短的路徑輸出路徑及長度。21. 教學(xué)計劃編制問題【問題描述】大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每 學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都 是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修 課程是確

54、定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這 樣的前提下設(shè)計一個教學(xué)計劃編制程序。【基本要求】(1) 輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(固定占 3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號。(2) 允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù) 擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。(3) 若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔ⅲ駝t將教學(xué)計劃輸出 到用戶指定的文件中。計劃的表格格式自行設(shè)計。【測試數(shù)據(jù)】學(xué)期總數(shù)：65；學(xué)分上限:103；該專業(yè)共開設(shè)12門課，課程號從co1到 c12,學(xué)分順序為2, 3, 4, 3, 2

55、, 3, 4, 4, 7, 5, 2, 3。先修關(guān)系見教科書圖 7.26o22. 校園導(dǎo)游咨詢【問題描述】設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。【基木要求】(1) 設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于io個。以圖中頂點表示 校內(nèi)各景點，存放景點名稱、代號、簡介等信息;以邊表示路徑，存放路徑長度等相 關(guān)信息。(2) 為來訪客人提供圖中任意景點相關(guān)信息的查詢。(3) 為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一 條最短的簡單路徑?！緶y試數(shù)據(jù)】以合肥學(xué)院南艷湖校區(qū)為例?！緦崿F(xiàn)提示】一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點和邊 均含有相關(guān)信息?！具x作內(nèi)容】(1) 求校園圖的關(guān)節(jié)點。(2) 提供圖屮任意景點問路查詢，即求任意兩個景點z間的所有路徑。(3) 提供校園圖中多個景點的最佳訪問路線查詢，即求途經(jīng)這多個景點的最佳 (短)路徑。(4) 校園導(dǎo)游圖的景點和道路的修改擴充功能。(5) 擴充道路信息，如道路類別(車道、人行道等)、沿途景色等級，以至可 按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等。(6) 擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡的 導(dǎo)向信息。(7) 實現(xiàn)校園導(dǎo)游圖的仿真界面。2