數據結構課程設計指導

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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