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

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

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

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

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

5、問(wèn)題描述已知 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è)計(jì)存儲(chǔ)結(jié)構(gòu)表示一元多項(xiàng)式；(2)設(shè)計(jì)算法實(shí)現(xiàn)一元多項(xiàng)式乘法；(3)分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2、 迷宮問(wèn)題迷宮問(wèn)題1)問(wèn)題描述問(wèn)題描述迷宮求解是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問(wèn)題，心理學(xué)家把一只老鼠從一個(gè)無(wú)頂蓋的大盒子的入口處趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。例如，圖 2 所示為一個(gè)迷宮

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20 以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xià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ù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫(xiě)方法等相關(guān)內(nèi)容在 c 語(yǔ)言程序設(shè)計(jì)的書(shū)上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫(xiě)明；

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

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

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

26、留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。2)2)基本要求基本要求以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。3)3)測(cè)試數(shù)據(jù)測(cè)試數(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ù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。4)4)實(shí)現(xiàn)提示實(shí)現(xiàn)提示需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來(lái)的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。5)5)選作內(nèi)容選作內(nèi)容（1） 兩個(gè)棧共享空間，思考應(yīng)開(kāi)辟數(shù)組的空間是多少？（2） 汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如 1 輛客車和1

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

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