《數據結構課程設計A》教學大綱

1、數據結構課程設計A教學大綱 編寫日期：課程組組長簽名：審定人簽名：一、課程基本信息1課程代碼：419209012課程中文名稱：數據結構課程設計A 課程英文名稱：Course Design for Data structure A3面向對象：地理信息科學，軟件工程，信息工程及遙感科學與技術專業(yè)本科學生4開課學院（課部）、系（中心、室）：信息工程學院、軟件工程系5實習周數：2周6學分數：27授課語種：中文，考試語種：中文 8教材：參見實習指導書。二、課程內容簡介數據結構課程是軟件工程及計算機相關專業(yè)一門重要的專業(yè)必修課，它涉及的概念多、內容廣，具有較強的理論性和實踐性，在整個教學課程體系中處于承上

2、啟下的作用。數據結構課程實習，是在完成理論課程學習之后安排的綜合實踐訓練。通過兩周的課程實驗活動，加深學生對數據結構課程內容的理解，增加感性認識，掌握利用計算機解決問題的基本方法、步驟和技術，提高學生利用所學知識解決實際問題的能力。三、課程的地位、作用和教學目標學生通過該課程實習，應該達到的教學目標為：1、了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；3、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4、訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作

3、方法和作風。四、與本課程相聯(lián)系的其他課程 計算機高級語言（C+），計算機高級程序語言課程設計，數據結構。五、教學基本要求數據結構課程實習要求學生根據教師布置實習題目，獨立設計并編寫能正確運行的程序，并且能通過多種黑盒法測試用例進行健壯性驗證。實習結束后，學生還應按照指定文檔模板，撰寫并提交課程實驗報告。學生在課程實習過程中，應遵循以下步驟： 問題分析和任務定義。根據課程設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 邏輯設計。對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型。邏輯設計

4、的結果應寫出每個抽象數據類型的定義（包括數據結構的描述和每個基本操作的功能說明），各個主要模塊的算法，并畫出模塊之間的調用關系圖。 物理設計。定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設計的結果是對數據結構和基本操作實施進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架。 程序編碼。把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些必要的代碼注釋和斷言，使程序中邏輯概念清楚。 程序調試與測試。采用自底向上的模塊組裝模式，分模

5、塊進行，即先調試低層函數。能夠熟練掌握調試工具的各種功能，設計測試數據確定疑點，通過修改程序來證實或排除這些疑點。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。 結果分析。程序運行結果不僅包括正確的輸入及其輸出結果，還應含有錯誤的輸入及其輸出結果，采用黑盒測試的方法進行多方位用例測試；同時，通過對算法的時間、空間復雜性的分析，提供更為優(yōu)化的改進程序版本。同時，在課程實習報告的撰寫中，要求學生按照給定文檔模板格式，體現出對問題進行分析、軟件設計、程序編碼和調試、軟件測試等上述環(huán)節(jié)的實施細節(jié)。課程實習報告要求在實習結束后一周內上交。六、考核方式與評價結構比例1、考核方式

6、：課程實習的成績由三部分組成：上機考勤、課程設計報告和課堂檢查結果。其中，課堂檢查結果與學生完成的題數和質量相關。以3題為例，課堂檢查結果等級如下：優(yōu)秀：完成3題，且代碼質量高；良好：完成2題，且代碼質量高；中等：完成2題，且代碼質量一般；及格：完成1題；不及格：完成小于1題。如檢查結果發(fā)現有網上直接下載使用，或同學之間拷貝使用，成績將以不及格計。2、評價結構比例：上機考勤10%，課程設計報告30%，課堂檢查的軟件作品60%。指導老師按優(yōu)秀、良好、中等、及格、不及格五檔提交成績，成績等級如下：優(yōu)秀：90-100；良好：80-89；中等：70-79；及格：60-69；不及格：60，成績不合格者需

7、要重修。七、教學參考資料 1 軟件工程系, 數據結構課程設計大綱20112014版, 2011.12.2 Sartaj Sahni著, 數據結構算法與應用C+語言描述, 機械工業(yè)出版社.3 嚴蔚敏 吳偉民等編著, 數據結構, 清華大學出版社.4 殷人昆 陶永雷 等編著, 數據結構（用面向對象方法與C+描述）, 清華大學出版社.5 William Ford William Topp著, Data Structure with C+, 清華大學出版社.6 Donald E. Knuth著, 計算機程序設計藝術第1卷基本算法, 國防工業(yè)出版社.7 Thomas H.Cormen Charles E.

8、Leiserson Ronald L.Rivest Clifford Stein, Introduction to Algorithms(Second Edition)（美）,高等教育出版社.八、教學進度與內容安排序次教學基本內容、重點、難點1線性表的應用1）線性表的順序存儲結構：順序表上的插入、刪除等基本操作；利用順序表解決簡單的應用問題；2）線性表的鏈式存儲結構：單鏈表上的建表、查找、插入和刪除等基本操作；單鏈表、雙鏈表和循環(huán)鏈表的使用；利用鏈表解決簡單的應用問題。實習題目1）單鏈表的搜索；2）單鏈表的遞歸輸出；3）法雷序列的生成；4）大數運算系列。2棧與隊列的應用1）順序棧和鏈棧上的壓棧

9、、彈棧等基本操作；2）順序隊列和鏈隊列上的入隊、出隊等基本操作；循環(huán)隊列的使用；3）利用棧和隊列解決簡單的應用問題。實習題目1）表達式括號匹配問題；2）簡單數學計算器的實現；3）火燒連營問題；4）二值圖像的像元分組。3樹和二叉樹及其應用1）二叉樹的表示方法、存儲方式、三種遍歷方式；2）堆的插入、刪除、初始化等基本操作；堆排序；3）哈夫曼樹及其應用。實習題目二叉樹的前序創(chuàng)建、交換等操作練習；2）由遍歷結果確定一棵二叉樹；3）由字符串構建Huffman樹；4）軟件壓縮/解壓縮軟件的實現（Huffman算法及應用）；5）磁盤樹管理器的實現。4搜索樹的應用1）二叉搜索樹的基本操作及應用；2）平衡二叉樹的基本操作及應用；3）紅黑樹的基本操作及應用；4）B-樹的基本操作及應用。實習題目1）利用BST樹統(tǒng)計文獻中單詞出現的頻率；2）電話簿軟件的實現（動態(tài)查找表算法的應用）；3）英語四級電子辭典的實現（動態(tài)查找表算法的應用）。5圖及其應用1）圖的鄰接矩陣和鄰