《數(shù)據(jù)結構》課程教學大綱

1、數(shù)據(jù)結構課程教學大綱課程編號：課程名稱：數(shù)據(jù)結構英文名稱：Data Structure課程類型：專業(yè)基礎必修課總 學 時：72 講課學時：56 上機學時：16 學時：72學分：4.5適用對象：計算機科學與技術專業(yè)本科生先修課程：計算機導論、C/C+程序設計I、C/C+程序設計II、離散數(shù)學一、課程性質(zhì)、目的和任務數(shù)據(jù)結構是計算機學科各專業(yè)本科學生必修的一門專業(yè)基礎課，是計算機程序設計的重要理論和實踐基礎，是培養(yǎng)學生軟件設計能力的一門重要課程，在計算機學科的本科教學中，起著非常重要的作用。本課程研究計算機系統(tǒng)中常用的線性表、二叉樹、圖等典型數(shù)據(jù)結構的設計方法，研究各種典型排序和查找算法的設計方法

2、和性能指標，并介紹這些數(shù)據(jù)結構和算法在實際工程中的應用。通過學習本課程，使學生深入理解軟件設計的基本要素和基本結構，培養(yǎng)邏輯思維能力，提高程序設計能力。數(shù)據(jù)結構課程是一門理論和實踐相結合的課程，上機實驗、課程設計等實踐性環(huán)節(jié)必不可少。二、教學基本要求本課程是理論與實踐并重的課程，要求學生既要掌握數(shù)據(jù)結構的基礎理論知識，又要掌握操作計算機和運行、調(diào)試程序的基本技能；能夠熟練運用C/C+語言或其它計算機語言編制具有中等難度的應用程序，在實踐中培養(yǎng)獨立分析問題和解決問題的作風和能力。本課程的基本要求如下。理解線性表、棧、隊列、串、數(shù)組、樹、二叉樹、圖等基本的數(shù)據(jù)邏輯結構，掌握描述這些數(shù)據(jù)結構、選擇合

3、適的存儲結構和實現(xiàn)各種操作的方法。熟練運用C/C+語言或其它計算機語言表達鏈式存儲結構；熟練運用遞歸函數(shù)表達遞歸定義、遞歸算法和遞歸結構。理解插入、交換、選擇、歸并等多種典型排序算法的思想，掌握在線性表、樹等各種不同數(shù)據(jù)結構中的查找算法。掌握在計算機語言環(huán)境中編輯、編譯、運行程序的方法，以及單步運行、設置斷點、查看變量運行時值等調(diào)試程序的方法。三、教學內(nèi)容及要求1緒論 了解數(shù)據(jù)結構的基本概念，了解數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和對數(shù)據(jù)的操作，了解抽象數(shù)據(jù)類型與數(shù)據(jù)結構的關系。 了解算法的概念、算法描述的方法、算法設計目標和算法分析方法，掌握算法的時間復雜度分析方法。2線性表 理解線性表的邏輯結

4、構和基本操作。 掌握線性表的順序存儲結構和實現(xiàn)方法。 掌握線性表的鏈式存儲結構和實現(xiàn)方法；比較兩種存儲結構的特點和性能。 掌握單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的概念和基本設計方法。3串 理解串的概念和串的基本操作，理解串的靜態(tài)存儲結構、動態(tài)存儲結構和鏈式存儲結構。 掌握串的定義和基本操作的實現(xiàn)方法。 掌握串的模式匹配方法。4棧和隊列 理解棧的概念和作用，掌握順序棧和鏈式棧的設計方法，掌握使用棧的算法設計方法。理解棧在遞歸等算法中的應用。 理解隊列的概念和作用，掌握順序循環(huán)隊列和鏈式隊列的設計方法，掌握使用隊列的算法設計方法。5數(shù)組和廣義表 理解數(shù)組的概念，理解一維數(shù)組和二維數(shù)組的

5、存儲結構。 了解特殊矩陣的壓縮存儲方法。 了解稀疏矩陣的基本壓縮存儲方法。 了解廣義表的概念和存儲結構。6樹和二叉樹 了解樹的定義、樹的術語、樹的表示方法和樹的幾種典型存儲結構。 理解二叉樹的定義、二叉樹的性質(zhì)、二叉樹的存儲結構和二叉樹的多種遍歷算法的基本概念。 掌握二叉樹結點類、二叉樹類的設計與實現(xiàn)；掌握多種二叉樹遍歷算法實現(xiàn)，比較二叉樹遍歷遞歸算法與非遞歸算法的實現(xiàn)和特點。 理解線索二叉樹的概念，掌握線索二叉樹結點類、中序線索二叉樹類的設計與實現(xiàn)，掌握中序線索化二叉樹的遞歸算法。 掌握哈夫曼樹的概念、算法實現(xiàn)，理解哈夫曼樹在信息論編碼中的應用。 理解樹與二叉樹的轉換方法；理解樹的遍歷方法。

6、7圖 了解圖的基本概念和術語。 掌握圖的鄰接矩陣和鄰接表存儲結構。 理解并實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。 理解最小生成樹的概念，掌握兩種構造圖的最小生成樹算法：普里姆算法和克魯斯卡爾算法。 了解最短路徑問題的基本概念，了解單源最短路徑算法。 8查找 理解查找的基本概念和查找方法的評判標準。 掌握線性表的順序查找、折半查找、分塊查找的算法設計方法，理解索引查找的基本結構。 掌握二叉排序樹的建立及其查找算法。 理解哈希表、哈希函數(shù)、解決沖突方法等哈希查找技術的概念，掌握拉鏈法哈希表的構造方法、動態(tài)插入、刪除元素、查找算法等。9排序 理解排序的基本概念和排序算法的評判標準。 掌握順序存儲結

7、構的直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、二路歸并排序的算法思想和算法設計方法；比較各種排序方法的特點和性能。 了解鏈式存儲結構的直接插入排序和直接選擇排序的算法設計方法。四、實踐環(huán)節(jié)數(shù)據(jù)結構課程是一門理論和實踐相結合的課程，不僅僅要注重理解基本知識，更要注重培養(yǎng)軟件設計的基本技能。實踐性環(huán)節(jié)是鞏固所學理論知識、使理論與實際相結合、提高程序設計能力和計算機操作能力的一項必不可少的重要環(huán)節(jié)。因此，課后習題、上機實驗和課程設計等都是加強程序設計訓練所必需的。本課程安排的上機實驗學時為16學時，課內(nèi)開設的8個實驗說明如下。實驗1 線性表的順序存儲結構和鏈式存儲結構（設計型

8、） 2學時實驗2 順序串類及串的模式匹配算法 2學時實驗3 棧和隊列及其應用 2學時實驗4 建立及遍歷二叉樹（設計型） 2學時實驗5 線索二叉樹，哈夫曼算法 2學時實驗6 順序查找，折半查找，二叉排序樹（設計型） 2學時實驗7 排序算法比較及性能評價 2學時實驗8 圖的建立與遍歷，最小代價生成樹 2學時每次實驗后均要求學生寫出實驗報告，實驗報告內(nèi)容包括：題目、題意解釋、題意分析、設計方案、流程描述、源程序清單、程序運行結果、程序存在問題和改進意見等。五、課外習題及課程討論本課程通過課堂講授例題、課堂練習、課后習題、上機實驗以及課程設計等各個實踐環(huán)節(jié)，對學生進行系統(tǒng)的程序設計訓練。所有例題、課堂

9、練習題、課后習題、上機實驗題都是精心挑選的，由淺入深，環(huán)環(huán)相扣，步步推進，調(diào)動學生的主動性和自覺性并培養(yǎng)學生寫程序的興趣。除了課內(nèi)安排的習題課、課堂討論、期中測驗、復習課以外，每次課后都要求學生做至少2個完整的程序，并定期檢查學生做作業(yè)的情況，作業(yè)的數(shù)量和質(zhì)量占平時成績的一部分。六、教學方法與手段本課程的課堂教學采用板書與多媒體相結合的方式進行，以板書教學為主，多媒體教學為輔。其中，課程主要內(nèi)容采用板書教學，計算機語言環(huán)境的使用和程序運行需要采用多媒體的方式進行演示。七、各教學環(huán)節(jié)學時分配章節(jié)（或內(nèi)容）講課習題課討論課實驗其它合計緒論44線性表8210串426棧和隊列628數(shù)組和廣義表44樹和

10、二叉樹8412圖628查找628排序8210復習22合 計5421672八、考核方式本課程為考試課程，期末考試為閉卷筆試。學生的課程總評成績由平時成績（占30%）和期末考試成績兩部分構成，平時成績中實驗成績占20%，出勤、作業(yè)、課堂測驗、學習主動性等占10%。實驗成績根據(jù)實驗報告質(zhì)量評定，作業(yè)成績根據(jù)習題的數(shù)量和質(zhì)量評定。九、推薦教材和教學參考書教 材：數(shù)據(jù)結構（C+版），葉核亞編著，機械工業(yè)出版社，2004年。參考書：數(shù)據(jù)結構及應用算法教程，嚴蔚敏等編著，清華大學出版社，2001年。數(shù)據(jù)結構（用面向?qū)ο蠓椒ㄅcC+描述），殷人昆等編著，清華大學出版社，1999年。十、說明另設一周課程設計。大綱

11、制訂人：葉核亞大綱審定人：黃緯制訂日期：2010年5月數(shù)據(jù)結構課程實驗教學大綱一、實驗教學目標與基本要求數(shù)據(jù)結構是計算機學科各專業(yè)本科學生必修的一門專業(yè)基礎課。數(shù)據(jù)結構課程是一門理論和實踐相結合的課程，不僅僅要注重理解基本知識，更要注重培養(yǎng)軟件設計的基本技能。實踐性環(huán)節(jié)是鞏固所學理論知識、使理論與實際相結合、提高程序設計能力和計算機操作能力的一項必不可少的重要環(huán)節(jié)。其中，上機實驗是加強程序設計訓練所必需的一個重要環(huán)節(jié)。實驗基本要求如下：驗證教材中已設計好的算法，給出多種運行結果并分析比較，進一步理解和鞏固數(shù)據(jù)結構基本原理和算法設計原則，積累軟件設計經(jīng)驗。熟練運用C/C+語言或其它計算機語言，綜

12、合數(shù)據(jù)結構基本原理和算法設計原則，獨立設計出具有中等難度的應用程序，編譯、運行程序，獲得正確的結果；分析算法性能并給出總結，進一步提高算法性能并降低算法復雜度。掌握在計算機語言環(huán)境中編輯、編譯、運行程序的方法，以及單步運行、設置斷點、查看變量運行時值等調(diào)試程序的方法。具備操作計算機和運行、調(diào)試程序的基本技能。二、本實驗課程的基本理論與實驗技術知識數(shù)據(jù)結構的基本理論，根據(jù)數(shù)據(jù)的邏輯結構，選擇合適的數(shù)據(jù)存儲結構，設計對數(shù)據(jù)進行各種操作的算法。算法的基本設計原則，算法必須達到正確性、可讀性、健壯性、高時間效率、高空間效率等基本目標。熟悉在計算機語言環(huán)境中編輯、編譯、運行和調(diào)試程序的方法。三、實驗方法

13、、特點與基本要求掌握計算機系統(tǒng)的基本操作，掌握在計算機語言環(huán)境中編輯、編譯、運行和調(diào)試程序的多種方法，具備運行和調(diào)試程序的基本技能，發(fā)現(xiàn)程序有錯時，能夠找到錯誤所在并改正錯誤。四、實驗主要儀器設備計算機。五、實驗項目的設置與內(nèi)容提要總實驗學時為 16 學時。序號實驗項目內(nèi) 容 提 要實驗學時實驗類型每組人數(shù)實驗要求1線性表掌握線性表的概念，實現(xiàn)線性表的順序存儲結構和鏈式存儲結構下的基本操作，實現(xiàn)單鏈表復制等操作。2設計1必做3串順序串類的算法實現(xiàn)及串的模式匹配算法。2驗證1必做4棧和隊列使用棧和隊列結構實現(xiàn)表達式計算等算法。2驗證1必做5二叉樹驗證建立及遍歷二叉樹算法，設計復制二叉樹的算法。2設計1必做6線索二叉樹及哈夫曼算法建立并線索化中序線索二叉樹；驗證哈夫曼算法。2驗證1必做8圖驗證圖的建立與遍歷算法，最小代價生成樹算法2驗證1必做7查找順序查找，折半查找，二叉排序樹2設計1必做2排序多個排序算法比較及性能評價。2驗證1必做六、實驗報告要求每次實驗后均要求學生寫出實驗報告，實驗報告內(nèi)容包括：題目、題意解釋、題意分析、設計方案、流程描述、源程序清單