數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、設(shè)計目的一、設(shè)計目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、設(shè)計要求二、設(shè)計要求在本課程設(shè)計過程中要求學(xué)生：（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）按照課程設(shè)計的題目要求，獨立地完成各項任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績。（3）認(rèn)真編寫課程設(shè)計報告。課程設(shè)計報告的書寫格式及要求見附錄 2。三、設(shè)計步驟三、設(shè)計步驟1、 問題分析和任務(wù)定義；2、 數(shù)據(jù)類型和系統(tǒng)設(shè)計；3、

2、編碼實現(xiàn)和靜態(tài)檢查；4、 上機(jī)調(diào)試；5、總結(jié)和整理課程設(shè)計報告。四、考核方式和成績評定四、考核方式和成績評定考核分為兩個部分：程序運(yùn)行情況：按規(guī)定時間到機(jī)房運(yùn)行程序，由老師檢查運(yùn)行情況。學(xué)生能對自己的程序面對教師提問并能熟練地解釋清楚。課程設(shè)計報告：是否按規(guī)定書寫課程設(shè)計報告的各項內(nèi)容。課程設(shè)計成績采用五級分制。100%=上機(jī)檢查（50%）+課程設(shè)計報告（50%）五、上交相關(guān)內(nèi)容要求五、上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個部分組成，缺一不可1 上交源程序：學(xué)生按照課程設(shè)計的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個文件夾中） ；2 上交程序的說明文件：（保存在.doc 中）在說明文檔中

3、應(yīng)該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；3 課程設(shè)計報告：（保存在 word 文檔中，文件名要求 按照姓名-學(xué)號-課程設(shè)計報告起名，如文件名為張三-101-課程設(shè)計報告.doc ）按照課程設(shè)計的具體要求建立的功能模塊，每個模塊要求按照如下幾個內(nèi)容認(rèn)真完成；1、需求分析、需求分析1 程序的功能；2 輸入輸出的要求；3 測試數(shù)據(jù)。2、概要設(shè)計、概要設(shè)計包括程序設(shè)計組成框圖，程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義） 。3、詳細(xì)設(shè)計、詳細(xì)設(shè)計包括模塊功能說明（如函數(shù)功能、入口及出口參數(shù)說明，函數(shù)調(diào)用關(guān)系描述等） ，每個模塊

4、的算法設(shè)計說明（可以是描述算法的流程圖） 。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。4、調(diào)試分析、調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？） ，算法的改進(jìn)設(shè)想。5、核心源程序清單和執(zhí)行結(jié)果、核心源程序清單和執(zhí)行結(jié)果源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。附錄 1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的具體內(nèi)容本次課程設(shè)計完成如下模塊（共 36 個模塊，抽簽決定自己所做題目的序號）1、一元多項式乘法、一元多項式乘法1) 問題描述

5、問題描述已知 A(x)=a0+a1x+a2x2+anxn和 B(x)=b0+b1x+b2x2+bmxm，并且在 A(x)和 B(x)中指數(shù)相差很多，求 A(x)=A(x)*B(x)。2) 基本要求基本要求(1)設(shè)計存儲結(jié)構(gòu)表示一元多項式；(2)設(shè)計算法實現(xiàn)一元多項式乘法；(3)分析算法的時間復(fù)雜度和空間復(fù)雜度。2、 迷宮問題迷宮問題1)問題描述問題描述迷宮求解是實驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。例如，圖 2 所示為一個迷宮

6、示意圖，其中雙邊矩形表示迷宮，1 代表有障礙，0 代表無障礙。2) 基本要求基本要求(1) 設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲迷宮；(2) 設(shè)計存儲結(jié)構(gòu)保存從入口到出口的通路；(3) 設(shè)計算法完成迷宮問題的求解；(4) 分析算法的時間復(fù)雜度。3) 設(shè)計思想設(shè)計思想可以采用回溯法實現(xiàn)該問題的求解。回溯法是一種不斷試探及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的） ，即某處可以到達(dá)，則到達(dá)新點，否則試探下一方向；若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼0123456789011111111111101110111121101011111310100000114101

7、1101111511001100016101100110171111111111入口(1, 1)出口(6, 8) 圖 2 迷宮示意圖，其中 1 代表有障礙，0 代表無障礙前進(jìn)的方向有八個，分別是上、下、左、右、左上、左下、右上、右下續(xù)試探，直到所有可能的通路都搜索到，或找到一條通路，或無路可走又返回到入口點。在求解過程中，為了保證在任何位置上都能沿原路退回，需要一個后進(jìn)先出的棧來保存從入口到當(dāng)前位置的路徑?？梢詫⒚詫m定義成一個二維數(shù)組，則每個點有 8 個試探方向，如當(dāng)前點的坐標(biāo)是(x, y)，與其相鄰的 8 個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，規(guī)定試探順序為順時針方向，將這 8 個方向的

8、坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組 move8中，在 move 數(shù)組中，每個元素由兩個域組成：x 表示橫坐標(biāo)增量，y 表示縱坐標(biāo)增量。這樣會很方便地求出從某點(x，y)按某一方向 v (0v7) 到達(dá)新點（i，j）的坐標(biāo)：i=x+movev.x ； j=y+movev.y。算法用偽代碼描述如下：1. 棧初始化；2. 將入口點坐標(biāo)(x , y)及該點的方向 d（設(shè)為-1）入棧；3. 當(dāng)棧不空時循環(huán)執(zhí)行下述操作：3.1 (x , y , d)容忍值，則在 j 處放置放大器; 2.2 否則 D(i) = maxD(i)，D(j) +d(j) ;【思考題思考題】本題假設(shè)分布網(wǎng)絡(luò)是一棵二叉樹結(jié)構(gòu)，如果是樹結(jié)構(gòu)應(yīng)如

9、何設(shè)計算法？5、哈夫曼編碼、哈夫曼編碼1) 問題描述問題描述設(shè)某編碼系統(tǒng)共有 n 個字符，使用頻率分別為w1, w2, , wn，設(shè)計一個不等長的編碼方案，使得該編碼系統(tǒng)的空間效率最好。2) 基本要求基本要求(1) 設(shè)計數(shù)據(jù)結(jié)構(gòu)；(2) 設(shè)計編碼算法；(3) 分析時間復(fù)雜度和空間復(fù)雜度。3) 設(shè)計思想設(shè)計思想 利用 Huffman 編碼樹求得最佳的編碼方案。根據(jù)哈夫曼算法，建立哈夫曼樹時，可以將哈夫曼樹定義為一個結(jié)構(gòu)型的一維數(shù)組HuffTree，保存哈夫曼樹中各結(jié)點的信息，每個結(jié)點包括：權(quán)值、左孩子、右孩子、雙親，如圖 6 所示。由于哈夫曼樹中共有 2n-1 個結(jié)點，并且進(jìn)行 n-1 次合并操

10、作，所以該數(shù)組的長度為 2n-1。 構(gòu)造哈夫曼樹的偽代碼如下：1. 數(shù)組 huffTree 初始化，所有元素結(jié)點的雙親、左右孩子都置為-1； 2. 數(shù)組 huffTree 的前 n 個元素的權(quán)值置給定權(quán)值 wn； 3. 進(jìn)行 n-1 次合并 3.1 在二叉樹集合中選取兩個權(quán)值最小的根結(jié)點，其下標(biāo)分別為 i1, i2； 3.2 將二叉樹 i1、i2 合并為一棵新的二叉樹 k； 在哈夫曼樹中，設(shè)左分支為 0，右分支為 1，從根結(jié)點出發(fā)，遍歷整棵哈夫曼樹，求得各個葉子結(jié)點所表示字符的哈夫曼編碼。【思考題思考題】對于采用哈夫曼編碼樹進(jìn)行的編碼，如何設(shè)計解碼算法？6、TSP 問題問題1) 問題描述問題描

11、述所謂 TSP 問題是指旅行家要旅行 n 個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。2) 基本要求基本要求(1) 上網(wǎng)查找 TSP 問題的應(yīng)用實例；(2) 分析求 TSP 問題的全局最優(yōu)解的時間復(fù)雜度；(3) 設(shè)計一個求近似解的算法；(4) 分析算法的時間復(fù)雜度。3) 設(shè)計思想設(shè)計思想對于 TSP 問題，一種最容易想到的也肯定能得到最佳解的算法是窮舉法，即考慮所有可能的旅行路線，從中選擇最佳的一條。但是用窮舉法求解 TSP 問題的時間復(fù)雜度為(n!)，當(dāng) n 大到一定程度后是不可解的。本實驗只要求近似

12、解，可以采用貪心法求解：任意選擇某個城市作為出發(fā)點，然后前往最近的未訪問的城市，直到所有的城市都被訪問并且僅被訪問一次，最后返回到出發(fā)點。為便于查找離某頂點最近的鄰接點，可以采用鄰接矩陣存儲該圖。算法用偽代碼描述weight lchild rchild parent 圖 6 哈夫曼樹的結(jié)點結(jié)構(gòu)如下：1. 任意選擇某個頂點 v 作為出發(fā)點； 2. 執(zhí)行下述過程，直到所有頂點都被訪問： 2.1 v=最后一個被訪問的頂點； 2.2 在頂點 v 的鄰接點中查找距離頂點 v 最近的未被訪問的鄰接點 j； 2.2 訪問頂點 j； 3. 從最后一個訪問的頂點直接回到出發(fā)點 v；【思考題思考題】上網(wǎng)查找 TS

13、P 問題的應(yīng)用實例，寫一篇綜述報告。7、醫(yī)院選址問題、醫(yī)院選址問題1)問題描述問題描述n 個村莊之間的交通圖可以用有向網(wǎng)圖來表示，圖中邊上的權(quán)值表示從村莊 i 到村莊 j 的道路長度。現(xiàn)在要從這 n 個村莊中選擇一個村莊新建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使所有的村莊離醫(yī)院都比較近？2) 基本要求基本要求(1) 建立模型，設(shè)計存儲結(jié)構(gòu)；(2) 設(shè)計算法完成問題求解；(3) 分析算法的時間復(fù)雜度。3) 設(shè)計思想設(shè)計思想醫(yī)院選址問題實際是求有向圖中心點的問題。首先定義頂點的偏心度。設(shè)圖 G=（V，E） ，對任一頂點 k，稱 E(k)=maxd(i, k)（iV）為頂點 k 的偏心度。顯然，

14、偏心度最小的頂點即為圖 G 的中心點。如圖 7(a)所示是一個帶權(quán)有向圖，其各頂點的偏心度如圖(b)所示。醫(yī)院選址問題的算法用偽代碼描述如下：1對加權(quán)有向圖，調(diào)用 Floyd 算法，求每對頂點間最短路徑長度的矩陣；2對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度；3具有最小偏心度的頂點即為所求。abcde1253214頂點偏心度a b 6b 8d 5e 7 (a) (b) 圖 7 帶權(quán)有向圖及各頂點的偏心度【思考題思考題】圖的存儲結(jié)構(gòu)和算法的設(shè)計需要一定的靈活性和技巧。從醫(yī)院選址問題的求解過程，你有什么感想？8、簡單個人電話號碼查詢系統(tǒng)簡單個人電話號碼查詢系統(tǒng)1) 問題描述問題描述人們在

15、日常生活中經(jīng)常需要查找某個人或某個單位的電話號碼，本實驗將實現(xiàn)一個簡單的個人電話號碼查詢系統(tǒng)，根據(jù)用戶輸入的信息（例如姓名等）進(jìn)行快速查詢。2) 基本要求基本要求(1) 在外存上，用文件保存電話號碼信息；(2) 在內(nèi)存中，設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲電話號碼信息；(3) 提供查詢功能：根據(jù)姓名實現(xiàn)快速查詢；(4) 提供其他維護(hù)功能：例如插入、刪除、修改等；(5) 按電話號碼進(jìn)行排序。3) 設(shè)計思想設(shè)計思想 由于需要管理的電話號碼信息較多，而且要在程序運(yùn)行結(jié)束后仍然保存電話號碼信息，所以電話號碼信息采用文件的形式存放到外存中。在系統(tǒng)運(yùn)行時，需要將電話號碼信息從文件調(diào)入內(nèi)存來進(jìn)行查找等操作，為了接收文件中的內(nèi)

16、容，要有一個數(shù)據(jù)結(jié)構(gòu)與之對應(yīng)，可以設(shè)計如下結(jié)構(gòu)類型的數(shù)組來接收數(shù)據(jù)： const int max=10; struct TeleNumber string name; /姓名 string phoneNumber; /固定電話號碼 string mobileNumber; /移動電話號碼 string email; /電子郵箱 Telemax;為了實現(xiàn)對電話號碼的快速查詢，可以將上述結(jié)構(gòu)數(shù)組排序，以便應(yīng)用折半查找，但是，在數(shù)組中實現(xiàn)插入和刪除操作的代價較高。如果記錄需頻繁進(jìn)行插入或刪除操作，可以考慮采用二叉排序樹組織電話號碼信息，則查找和維護(hù)都能獲得較高的時間性能。更復(fù)雜地，需要考慮該二叉排序

17、樹是否平衡，如何使之達(dá)到平衡。9、機(jī)器調(diào)度問題、機(jī)器調(diào)度問題1)問題描述問題描述機(jī)器調(diào)度是指有 m 臺機(jī)器需要處理 n 個作業(yè)，設(shè)作業(yè) i 的處理時間為 ti，則對 n 個作業(yè)進(jìn)行機(jī)器分配，使得：(1) 一臺機(jī)器在同一時間內(nèi)只能處理一個作業(yè)；(2) 一個作業(yè)不能同時在兩臺機(jī)器上處理；(3) 作業(yè) i 一旦運(yùn)行，則需要 ti個連續(xù)時間單位。設(shè)計算法進(jìn)行合理調(diào)度，使得在 m 臺機(jī)器上處理 n 個作業(yè)所需要的處理時間最短。2) 基本要求基本要求(1) 建立問題模型，設(shè)計數(shù)據(jù)結(jié)構(gòu)；(2) 設(shè)計調(diào)度算法，為每個作業(yè)分配一臺可用機(jī)器；(3) 給出分配方案。3) 設(shè)計思想設(shè)計思想假設(shè)有七個作業(yè)，所需時間分別

18、為2, 14, 4, 16, 6, 5, 3，有三臺機(jī)器，編號分別為m1、m2和 m3。這七個作業(yè)在三臺機(jī)器上進(jìn)行調(diào)度的情形如圖 9 所示，陰影區(qū)代表作業(yè)的運(yùn)行區(qū)間。作業(yè) 4 在 0 到 16 時間被調(diào)度到機(jī)器 1 上運(yùn)行，在這 16 個時間單位中，機(jī)器 1完成了對作業(yè) 4 的處理；作業(yè) 2 在 0 到 14 時間被調(diào)度到機(jī)器 2 上處理，之后機(jī)器 2 在 14到 17 時間處理作業(yè) 7；在機(jī)器 3 上，作業(yè) 5 在 06 時間完成，作業(yè) 6 在 611 時間完成，作業(yè) 3 在 1115 時間完成，作業(yè) 1 在 1517 時間完成。注意到作業(yè) i 只能在一臺機(jī)器上從 si時刻到 si +ti時

19、間完成且任何機(jī)器在同一時刻僅能處理一個作業(yè)，因此最短調(diào)度長度為17。 在上述處理中，采用了最長時間優(yōu)先（LPT）的簡單調(diào)度策略。在 LPT 算法中，作業(yè)按其所需時間的遞減順序排列，在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機(jī)器。 下面設(shè)計完成下面設(shè)計完成 LPT 算法的存儲結(jié)構(gòu)。算法的存儲結(jié)構(gòu)。 為每個機(jī)器設(shè)計數(shù)據(jù)類型： struct MachineNode int ID; /機(jī)器號m1m2m3時間分配 作業(yè)作業(yè) 5作業(yè)作業(yè) 6 作業(yè)作業(yè) 3 作業(yè)作業(yè) 1作業(yè)作業(yè) 2 作業(yè)作業(yè) 7 作業(yè)作業(yè) 41716圖 9 三臺機(jī)器的調(diào)度示例654int avail; /機(jī)器可用時刻 ; 為每個作業(yè)設(shè)計數(shù)據(jù)

20、類型： struct JobNode int ID; /作業(yè)號int time; /處理時間 ;LPT 算法用偽代碼描述如下：1. 如果作業(yè)數(shù) n機(jī)器數(shù) m，則 1.1 將作業(yè) i 分配到機(jī)器 i 上； 1.2 最短調(diào)度長度等于 n 個作業(yè)中處理時間最大值；2. 否則，重復(fù)執(zhí)行以下操作，直到 n 個作業(yè)都被分配： 2.1 將 n 個作業(yè)按處理時間建成一個大根堆 H1； 2.2 將 m 個機(jī)器按可用時刻建立一個小根堆 H2； 2.3 將堆 H1 的堆頂作業(yè)分配給堆 H2 的堆頂機(jī)器； 2.4 將 H2 的堆頂機(jī)器加上 H1 的堆頂作業(yè)的處理時間重新插入 h2 中； 2.5 將堆 H1 的堆頂元素

21、刪除；3. 堆 H2 的堆頂元素就是最短調(diào)度時間；10、 運(yùn)動會分?jǐn)?shù)統(tǒng)計運(yùn)動會分?jǐn)?shù)統(tǒng)計1)問題描述問題描述參加運(yùn)動會有 n 個學(xué)校，學(xué)校編號為 1n。比賽分成 m 個男子項目，和 w 個女子項目。項目編號為男子 1m，女子 m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m=20,n=20）2)2) 基本要求基本要求(1)可以輸入各個項目的前三名或前五名的成績；(2)能統(tǒng)計各學(xué)?？偡?，(3)可以按學(xué)校編號、學(xué)校總分、男女團(tuán)體總分排序輸出；(4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以

22、按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20 以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動項目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整型界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運(yùn)動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在 c 語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；

23、11、 訂票系統(tǒng)訂票系統(tǒng)1)問題描述問題描述通過此系統(tǒng)可以實現(xiàn)如下功能：(1)錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）(2)查詢： 可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達(dá)城市，航班票價，票價折扣，確定航班是否滿倉） ；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；(3)訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；(4)退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。(5)修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件2) 基

24、本要求基本要求根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能。 12、 文章編輯文章編輯1)1)問題描述問題描述輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。2)2) 基本要求基本要求靜態(tài)存儲一頁文章，每行最多不超過 80 個字符，共 N 行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）

25、分 4 行輸出全部字母數(shù)、數(shù)字個數(shù)、空格個數(shù)、文章總字?jǐn)?shù)（3）輸出刪除某一字符串后的文章；13、停車場管理、停車場管理1)1)問題描述問題描述設(shè)停車場內(nèi)只有一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿 n 輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停

26、留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。2)2)基本要求基本要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。3)3)測試數(shù)據(jù)測試數(shù)據(jù)設(shè) n=2,輸入數(shù)據(jù)為：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （

27、A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。4)4)實現(xiàn)提示實現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。5)5)選作內(nèi)容選作內(nèi)容（1） 兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如 1 輛客車和1

28、.5 輛小汽車的占地面積相同，1 輛十輪卡車占地面積相當(dāng)于 3 輛小汽車的占地面積。（3） 汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。（4） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。14、統(tǒng)計成績、統(tǒng)計成績1)1)問題描述問題描述給出 n 個學(xué)生的 m 門考試的成績表，每個學(xué)生的信息由學(xué)號、姓名以及各科成績組成。對學(xué)生的考試成績進(jìn)行有關(guān)統(tǒng)計，并打印統(tǒng)計表。2)2)基本要求基本要求（1） 按總數(shù)高低次序，打印出名次表，分?jǐn)?shù)相同的為同一名次；（2） 按名次打印出每個學(xué)生的學(xué)號、姓名、總分以及各科成績。3)3)測

29、試數(shù)據(jù)測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。4)4)選作內(nèi)容選作內(nèi)容對各科成績設(shè)置不同的權(quán)值。15、校園導(dǎo)游程序、校園導(dǎo)游程序 1)1)問題描述問題描述用無向網(wǎng)表示你所在學(xué)校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。2)2)基本要求基本要求（1） 查詢各景點的相關(guān)信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 查詢圖中任意兩個景點間的所有路徑。（4） 增加、刪除、更新有關(guān)景點和道路的信息。3)3)選作內(nèi)容選作內(nèi)容（1） 求多個景點的最佳（最短）游覽路徑。（2） 區(qū)分機(jī)動車