1、數據結構課程設計任務書（本科 ）遼寧工程技術大學軟件學院軟件工程系一、課程設計目的和任務數據結構是計算機專業的核心課程， 是計算機科學的算法理論基礎和軟件設 計的技術基礎。 數據結構是實踐性很強的課程。 課程設計是加強學生實踐能力的 一個強有力手段。要求學生掌握數據結構的應用、算法的編寫、類 C 語言的算 法轉換成 C 程序并上機調試的基本方法。課程設計要求學生在完成程序設計的 同時能夠寫出比較規范的設計報告。 嚴格實施課程設計這一環節， 對于學生基本 程序設計素養的培養和軟件工作者工作作風的訓練，將起到顯著的促進作用。二、課程設計基本要求1、通過這次設計，要求在數據結構的邏輯結構和存儲結構、

2、數據結構的選 擇應用、算法的設計及其實現等方面加深對課程基本內容的理解。 同時，在程序 設計方法以及上機操作等基本技能方面受到比較系統的訓練。2、學生必須按照課程設計要求，以學生為主、指導教師指導為輔，認真、 獨立地完成課程設計的任務，有問題及時主動與指導教師溝通。3、本次課程設計按照教學要求需要在一周時間內獨立完成，學生要發揮自 主學習的能力，充分利用時間，按時完成設計內容。三、課程設計內容( 注：題目號與學生學號尾數對應 )1、題目：地鐵建設問題 設計任務：某城市要在各個轄區之間修建地鐵， 由于地鐵建設費用昂貴， 因此需要合理安排 地鐵建設線路，使市民可以沿地鐵到達各個轄區，并使總費用最小

3、。設計要求：(1) 輸入各個轄區名稱和各轄區間直接距離(地鐵鋪設費用與距離成正比) 。(2) 根據轄區距離信息，計算出應該在哪些轄區建立地鐵線路。(3) 輸出應該建設的地鐵線路及所需建設總里程。實現提示：(1) 根據輸入的轄區信息，建立圖模型，使用的數據結構是無向圖，采用鄰接 矩陣存儲。(2) 根據普利姆算法計算最小生成樹，參加教材7-4。2、題目：教學計劃編制問題設計任務： 大學的每個專業都要制定教學計劃。假設任何專業都有固定的學習年限，每 學年含兩學期， 每學期的時間長度和學分上限值均相等。 每個專業開設的課程都 是確定的， 而且課程在開設時間的安排必須滿足先修關系。 每門課程有哪些先修

4、課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這 樣的前提下設計一個教學計劃編制程序。設計要求：(1) 輸入參數包括：學期總數，一學期的學分上限，每門課的課程號(固定占3位的字母數字串)、學分和直接先修課的課程號。(2) 允許用戶指定下列兩種編排策略之一： 一是使學生在各學期中的學習負擔 盡量均勻；二是使課程盡量可能地集中在前幾個學期中。(3) 若根據給定的條件問題無解， 則報告適當的信息； 否則將教學計劃輸出到 屏幕。計劃的表格格式自行設定。實現提示：(1) 數據結構使用有向圖和棧。(2) 課程先修關系參照教材 P181 頁圖 7.26(3) 如果輸入的先修課程號不在該

5、專業開設的課程序列內，則作為錯誤處理。3、題目：運動會分數統計 設計任務：參加運動會有n個院系，院系編號為1n。比賽分成m個男子項目，和 w個女子項目。項目編號為男子1m,女子m+1m+w。不同的項目取前五名 或前三名積分；取前五名的積分分別為： 7、5、3、2、1 ，前三名的積分分別為： 5、3、2；哪些項目取前五名或前三名由學生自己設定。 (m=20,n=20) 設計要求：(1) 產生各院系的成績單， 內容包括各院系取得的每項成績的項目號、 名次(成 績)、姓名和得分；(2) 產生團體總分報表，內容包括院系編號、男子團體總分、女子團體總分和團體總分。實現提示：可以假設姓名長度不超過 20

6、個字符。每個項目結束時，將其編號、類型符 (區分取前五名還是取前三名) 輸入，并按名次順序輸入運動員姓名、 院系編號 和成績。4、題目：算術表達式求值演示程序設計任務：設計一個程序，演示用算符優先法對算術表達式求值的過程。設計要求：(1) 以字符序列的形式從終端輸入語法正確的、不含變量的整數表達式。(2) 利用教材P53頁表3.1給出的算符優先關系，實現對算術四則混合運算表 達式的求值；(3) 仿照教材例 3-1 演示在求值過程中運算符棧、運算數棧、輸入字符和主要 操作的變化過程。實現提示：(1) 設置運算符棧和運算數棧輔助分析算符優先關系；(2) 在讀入表達式的字符序列的同時， 完成運算符和

7、運算數的識別處理， 以及 相應的運算；(3) 在識別出運算數的同時，要將其字符序列形式轉換成整數形式；(4) 在程序的適當位置輸出運算符棧、 運算數棧、輸入字符和主要操作的內容。5、題目：停車場管理設計任務：設停車場是一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進出。 汽車在停車場內按車輛到達時間的先后順序， 依次由北向南排列(大門在最南端， 最先到達的第一輛車停放在車場的最北端) ，若車場內已停滿 n 輛汽車，則后來 的汽車只能在門外的便道上等候， 一旦有車開走， 則排在便道上的第一輛車即可 開入；當停車場內某輛車要離開時， 在它之后進入的車輛必須先退出車場為它讓 路，待該輛車開

8、出大門外， 其他車輛再按原次序進入停車場， 每輛停放在車場的 車在它離開停車場時必須按它停留的時間長短繳納費用。 試為停車場編制按上述 要求進行管理的模擬程序。 設計要求：以棧模擬停車場， 以隊列模擬停車場外的便道， 按照從終端讀入的輸入數據 序列進行模擬管理。(1) 每一組輸入數據包括三個數據項：汽車“到達”或者“離開”信息、汽 車牌照號碼以及汽車到達或離開的時刻。(2) 對每一組輸入數據進行操作后的輸出信息為：a若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；b、若是車輛離開，則輸出汽車在停車場內停留的時間和應繳的費用(在便 道上停留的時間不收費) 。(3) 棧以順序結構實現，隊列以

9、鏈表結構實現。 實現提示：需另設一個棧，臨時停放為給要離開的汽車讓路而從停車場退出來的汽車， 也用順序存儲結構實現。 輸入數據按到達或離開的時刻有序。 棧中每一個元素表 示一輛汽車，包含 2 個數據項：汽車的牌照號碼和進入停車場的時刻。6、題目：表達式類型的實現 設計任務：一個表達式與一棵二叉樹之間， 存在著自然的對應關系。 寫一個程序， 實現 基于二叉樹表示的算術表達式 Expression的操作。設計要求：假設算術表達式Expression內可以含有變量(az)、常量(09)和二元運 算符(+，-，*，/，A)o實現以下操作：ReadExpr (E)以字符序列的形式輸入語法正確的前綴表示式

10、并構造 表達式 E。(2) WriteExpr(E) 用帶括號的中綴表示式輸出表達式 E。(3) Assign(V， c)實現對變量V的賦值(V=c)，變量的初值為0。(4) Value ( E)對算術表達式 E求值。(1) 在讀入表達式的字符序列的同時，完成運算符和運算數的識別處理以及 相應的運算。(2) 在識別出運算數的同時，要將其字符形式轉換成整數形式。(3) 用后根遍歷的次序對表達式求值。(4) 用中綴表示輸出表達式 E 時，適當添加括號，以正確反映運算的優先次 序。7、題目：一元稀疏多項式計算器 設計任務：設計一個一元稀疏多項式簡單計算器。設計要求：一元稀疏多項式簡單計算器的基本功能

11、是：(1) 輸入并建立多項式 creatpolyn()；(2) 輸出多項式，輸出形式為整數序列： n,c1,e1,c2,e2；,cn,en其中n是多項 式的項數， ci 和 ei 分別是第 i 項的系數和指數，序列按指數升序排列 printpolyn()；(3) 多項式a和b相加，建立多項式a+b,輸出相加的多項式一一addpolyn()；(4) 多項式a和b相減，建立多項式a-b，輸出相減的多項式一一subpolyn()。 實現提示：(1) 用帶頭結點的單鏈表存儲多項式。(2) 參照教材 2.4節內容。8、題目：哈夫曼編碼系統 設計任務：從鍵盤輸入一串電文字符能輸出對應的哈夫曼編碼。同時，能

12、翻譯由哈夫曼 編碼生成的代碼串，輸出相應的電文字符串。設計要求：(1) 從終端讀入字符集大小n,以及n個字符和n個權值，建立哈夫曼樹及哈 夫曼編碼。(2) 利用已經建好的哈夫曼樹，對輸入的字符串進行編碼，輸出編碼序列。(3) 利用已建好的哈夫曼樹對輸入的二進制編碼進行譯碼，并輸出結果。參見教材 6.6 節內容9、題目：校園導航系統 設計任務：給出校園各主要建筑的名稱信息及有線路聯通的建筑之間的距離， 利用校園 導航系統計算出給定的起點到終點之間的最近距離及線路。設計要求：1、輸入各建筑信息及線路信息，構建圖。2、計算給定起點到終點之間最近距離的進行線路。3、輸出線路及總距離。實現提示：1、本設

13、計數據結構為有向網，采用鄰接矩陣為存儲結構。2、參照迪杰斯特拉算法計算給定兩點之間的最短路徑。 參照書上 7-6 內容。10、題目：通訊錄的制作設計任務：針對你所在班集體中的“人名” ，設計一個哈希表，使得平均查找長度不超過R,完成相應的建表和查找過程。設計要求：(1) 每個人的信息至少包括姓名,電話,地址。至少包括對通訊錄的創建, 添加和按姓名查找等功能。(2) 假設人名為漢語拼音全拼形式, 待插入哈希表的長度為你所在班級的人數。哈希函數用除留余數法構造,采用鏈地址法或二次探測再散列法解決沖突。(3) 完成菜單設計。操作有必要的提示。實現提示：假設人名最大長度不超過 20,取碼可以采用折疊處

14、理,將每個字符對應的ASCII 碼求和。四、課程設計安排時間：2014.1.132014.1.17指導教師：教師班級驗收 教師孫寧軟件12-1邱云飛唐曉亮軟件12-2王永貴劉臘梅唐曉亮軟件12-3劉萬車姜文濤軟件12-4郭偉王珊珊劉憲國軟件12-5史慶偉孫寧軟件12-6劉亮常戩郭鵬飛網絡12-1張海濤郭鵬飛網絡12-2陳虹徐嬌月徐嬌月網絡12-3肖振久李紅霞劉佳旭嵌軟12-1曲長波肖成龍嵌軟12-2齊向明劉佳旭姜彥吉嵌軟12-3于美娜姜彥吉嵌軟12-4劉憲國劉麗上機安排:412機房416機房420機房419機房星期一上午軟件12 12數據結構下午軟件12 34數據結 構晚上軟件12 56 數據

15、結 構上午網絡12 -3數據結 構下午晚上 上午下午 晚上星期二網絡12 1-2數據結軟件12 56數據結構星期三星期四網絡12 1-2數據結網絡12 - 3數據結 構軟件12 12數據結 構軟件12 34 數據結 構網絡121-2數據結軟件1234數據結 構網絡12 - 3數據結構軟件軟件12 561212數據結數據構結構上午下午 晚上數據 結構五、考核與成績評定考核內容與標準：1 課程設計階段的表現10%上機時間禁止玩游戲等與設計無關的事，一經發現按缺勤處理 違紀并情節嚴重者，成績按不合格處理。2 課程設計報告30%項目比例備注報告格式規范程度30%圖表質量10%報告內容全面、清晰程度45

16、%總結深刻程度10%參考文獻5%3 程序上機檢查40%項目比例備注程序運行情況25%功能實現情況40%算法清晰程度15%人機交互、界面及菜單10%獨立元成情況10%4. 課程設計答辯20%5. 發現以下情況，成績判為不合格：(1) 上機程序未通過或無設計報告，成績為不合格(2) 程序、報告雷同，成績為不合格。(3) 缺勤2次及以上，成績為不及格。成績評定：二級分制六、課程設計報告要求參見附錄A:數據結構課程設計報告模板七、參考文獻1. 嚴蔚敏等 數據結構（ C 語言版）清華大學出版社2. 嚴蔚敏等 數據結構習題集（ C 語言版） 清華大學出版社3. 其他有關 C 教材或資料附錄A軟件學院課程設

17、計報告書課程名稱數據結構設計題目 專業班級 學 號姓 名指導教師 目錄說明： 目錄：“目錄”用小 2 號黑體字、居中；目錄內容最少列出第一級標題（章）和 第二級標題（節）；前者用 4號黑體字，后者用 4 號宋體字，第三級標題用 4 號 楷體字，居左頂格、單獨占行，每一級標題后應標明起始頁碼。1設計時間2設計目的3設計任務（針對設計題目）4設計內容（一級標題，黑體，三號，1.5倍行距）4.1需求分析（二級標題，黑體，小三，1.5倍行距）（三級標題，黑體，四號，1.5倍行距）格式要求：1）上面各級標題均左頂格2）正文：小四，中文宋體，西文 Times New Roman3）行間距1.5,首行縮進2

18、字符4）圖表中文字：五號，宋體有圖名和表名，圖名在圖下面標注，表名在表上面標注以無歧義的陳述說明課程設計的任務，強調的是程序要做什么？明確規定：1. 程序所能達到的功能；2. 輸入的形式和輸入值的范圍；3. 輸出的形式；4. 測試數據：包括在正確的輸入及輸出結果和含有錯誤的輸入及輸出結果4.2總體設計內容包括：1. 本程序中用到的所有抽象數據類型的定義；2. 主程序的流程；3. 各程序模塊之間的層次（調用）關系。4.3詳細設計內容包括：1. 實現概要設計中定義的所有數據類型，對每個操作只需要寫出偽碼算法；2. 對主程序和其它主要函數偽碼算法（偽碼算法達到的詳細程度建議為：按照偽碼算 法可以在計算機鍵盤直接輸入高級程序設計語言程序）；3. 函數的調用關系圖。4.4測試與分析4.4.1測試給出測試數據，輸出測試的結果，測