《數(shù)據(jù)結(jié)構(gòu)》課程教學大綱

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

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

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

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

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

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

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

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

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

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

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

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

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