數(shù)據(jù)結(jié)構(gòu)》課程教案

1、數(shù)據(jù)結(jié)構(gòu)課程教案課程類別：專業(yè)基礎(chǔ)課適用專業(yè)：計算機應用技術(shù)授課學時：32學時課程學分：4學分一、課程性質(zhì)、任務(wù)課程性質(zhì)：數(shù)據(jù)結(jié)構(gòu)是計算機應用技術(shù)專業(yè)的必修課程，也是研究如何對數(shù)據(jù)進行組織和設(shè)計、如何編制高效率的處理程序的一門基礎(chǔ)學科。課程任務(wù)：1、學習計算機程序編寫中的數(shù)據(jù)組織和設(shè)計；2、數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)； 3、經(jīng)典算法的設(shè)計和算法效率的分析。二、課程培養(yǎng)目標：（一）知識目標通過理論學習和程序的編寫，使學生系統(tǒng)地掌握程序中數(shù)據(jù)的組織、數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)，在重要算法的實現(xiàn)上逐步提高編程能力。（二）技能目標通過課程的學習，讓學生掌握重要的數(shù)據(jù)結(jié)構(gòu)，對數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)有深入的

2、理解，同時能編寫出使用重要算法知識的程序，并運用所學知識編寫程序解決實際中的問題。（三）素質(zhì)目標通過課程的學習，讓學習學會自學，培養(yǎng)學生的自學能力、克服學習困難的能力，同時讓學生掌握計算機編程中數(shù)據(jù)結(jié)構(gòu)的學習方法，并養(yǎng)成嚴謹、認真、仔細、踏實、上進的好習慣。三、選用教材與參考資料教材版本信息數(shù)據(jù)結(jié)構(gòu)與算法簡明教程（Java語言版） 清華大學出版社葉小平 陳瑛 主編教材使用評價本教材經(jīng)過兩年的使用，得到了讀者一致認可，同時也在不斷改進，適合高職高專教學使用，內(nèi)容基礎(chǔ)、重難點突出，符合高職高專“理論夠用、注重實踐”的要求。選用的參考資料嚴蔚敏.吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社.2009年

3、版 殷人昆.數(shù)據(jù)結(jié)構(gòu).清華大學出版社.1999年版 C語言程序設(shè)計.石油大學出版社 C語言程序設(shè)計.中國石油大學出版社.2006年版四、本課程與其他課程的聯(lián)系與分工先修課程離散數(shù)學、程序設(shè)計基礎(chǔ)后續(xù)課程面向?qū)ο蠹夹g(shù)、操作系統(tǒng)與其他課程配合與取舍情況 數(shù)據(jù)結(jié)構(gòu)與離散數(shù)學知識點結(jié)合較多，離散數(shù)學講求邏輯思維能力的培養(yǎng)和訓練，數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)的學習也需要邏輯思維能力做鋪墊。同時程序設(shè)計基礎(chǔ)課程也為學習數(shù)據(jù)結(jié)構(gòu)打下了基礎(chǔ)，對于本課程的教材，我們采用C語言來描述數(shù)據(jù)結(jié)構(gòu)，因此程序設(shè)計基礎(chǔ)也是以C語言作為的對象。本課程也與算法設(shè)計與分析結(jié)合得很緊密，因此在學習中我們也會引入常見算法的學習，達到兩者共同促

4、進的目的。五、課程教學內(nèi)容與基本要求第一章 數(shù)據(jù)結(jié)構(gòu)導論（一）、教學內(nèi)容第一節(jié) 數(shù)據(jù)結(jié)構(gòu)的基本概念一、引言二、數(shù)據(jù)結(jié)構(gòu)有關(guān)概念及術(shù)語第二節(jié) 算法和算法描述一、什么是算法二、算法描述工具類C語言第三節(jié) 算法評價一、時間二、空間（二）、教學目的要求通過本章的學習讓學生了解數(shù)算法的基本概念，理解如何運用類C語言來描述算法，掌握據(jù)結(jié)構(gòu)的概念和相關(guān)術(shù)語、算法的描述方法，學會從程序中分析算法效率和用函數(shù)式表示該程序的算法效率。在學完本章后，要求學生對數(shù)據(jù)結(jié)構(gòu)的涉及領(lǐng)域有大體的認識，同時了解數(shù)據(jù)結(jié)構(gòu)的作用，明確數(shù)據(jù)結(jié)構(gòu)和程序開發(fā)的關(guān)系。通過對算法效率的分析，學會使用這一知識點來優(yōu)化自己所寫程序的執(zhí)行效率。重

5、難點分析：本章重點是據(jù)結(jié)構(gòu)的概念和相關(guān)術(shù)語，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的含義，順序存儲和鏈式存儲的含義，類C語言的表示。難點是學會從程序中分析算法效率和用函數(shù)式表示該程序的算法效率。第二章 線性表（一）、教學內(nèi)容第一節(jié) 線性表的邏輯結(jié)構(gòu)一、線性表的定義二、線性表的基本操作第二節(jié) 線性表的順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)二、基本操作的實現(xiàn)三、動態(tài)分配的順序存儲結(jié)構(gòu)介紹第三節(jié) 線性表的鏈式存儲結(jié)構(gòu)一、單鏈表二、單鏈表的基本操作第四節(jié) 循環(huán)鏈表和雙向鏈表一、循環(huán)鏈表二、雙向鏈表第五節(jié) 線性表的應用多項式相加問題（二）、教學目的要求通過本章的學習讓學生進一步了解線性表的定義、稀疏矩陣的三元組存儲，掌握

6、C語言中指針知識的運用和鏈表的實現(xiàn)方式，掌握線性表的基本操作和順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)的實現(xiàn)，同時進一步掌握數(shù)組、矩陣的操作，學會編寫程序?qū)崿F(xiàn)矩陣的兩種轉(zhuǎn)置算法。在學完本章后，要求學生能夠掌握編程實現(xiàn)線性表中元素的插入和刪除操作，對于雙向鏈表的插入和刪除操作要操作熟練，同時能編程實現(xiàn)運用線性表解決多項式相加問題、運用數(shù)組實現(xiàn)矩陣的轉(zhuǎn)置問題。重難點分析：本章重點是線性表的基本操作和順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)的實現(xiàn)，數(shù)組、矩陣的操作，編寫程序?qū)崿F(xiàn)多項式相加問題（應用線性表）、矩陣的兩種轉(zhuǎn)置算法。難點是鏈式存儲結(jié)構(gòu)的實現(xiàn)、編寫程序?qū)崿F(xiàn)矩陣的兩種轉(zhuǎn)置算法以及稀疏矩陣的十字鏈表算法。第三章 棧和隊列第

7、一節(jié) 棧一、棧的定義及其運算二、棧的順序存儲結(jié)構(gòu)三、棧的鏈式存儲四、棧的應用舉例第二節(jié) 隊列一、隊列的定義及運算二、隊列的順序存儲結(jié)構(gòu)三、隊列的鏈式存儲結(jié)構(gòu)第三節(jié) 棧和隊列的應用實例停車場管理（二）、教學目的要求通過本章的學習讓學生進一步了解線性棧和隊列的定義和常見用途，掌握棧和隊列的基本操作，掌握棧和隊列的順序存儲結(jié)構(gòu)及鏈式存儲結(jié)構(gòu)的實現(xiàn)。在學完本章后，要求學生能夠掌握編程實現(xiàn)棧和隊列中的元素插入和刪除操作，同時能夠運用棧和隊列的知識編寫程序?qū)崿F(xiàn)停車場管理、劃分子集問題、敢死隊問題等經(jīng)典算法。重難點分析：本章重點是棧和隊列的基本操作，掌握棧和隊列的順序存儲結(jié)構(gòu)及鏈式存儲結(jié)構(gòu)。難點是編寫程序?qū)?/p>

8、現(xiàn)棧和隊列的鏈式存儲結(jié)構(gòu)及插入和刪除操作。第四章 串和數(shù)組第一節(jié) 串的定義一、串的定義二、串的存儲結(jié)構(gòu)第二節(jié) 數(shù)組的基本概念一、數(shù)組的定義二、數(shù)組的順序存儲結(jié)構(gòu)第三節(jié) 特殊矩陣和稀疏矩陣壓縮存儲一、特殊矩陣壓縮存儲二、稀疏矩陣壓縮存儲（二）、教學目的要求通過本章的學習讓學生進一步了解線性表中數(shù)組的定義、稀疏矩陣的三元組存儲，同時進一步掌握數(shù)組、矩陣的操作，學會編寫程序?qū)崿F(xiàn)矩陣的兩種轉(zhuǎn)置算法。在學完本章后，要求學生能夠編程實現(xiàn)運用線性表解決多項式相加問題、運用數(shù)組實現(xiàn)矩陣的轉(zhuǎn)置問題。重難點分析：本章重點是數(shù)組的基本操作和順序存儲結(jié)構(gòu)，矩陣的兩種轉(zhuǎn)置算法。難點是編寫程序?qū)崿F(xiàn)矩陣的兩種轉(zhuǎn)置算法以及稀

9、疏矩陣的十字鏈表算法。第五章 樹第一節(jié) 樹的定義和基本術(shù)語一、樹的定義二、樹的基本術(shù)語第二節(jié) 二叉樹一、二叉樹的定義二、二叉樹的重要性質(zhì)三、二叉樹的存儲結(jié)構(gòu)四、建立二叉樹的二叉鏈表第三節(jié) 遍歷二叉樹一、先根遍歷二、中根遍歷三、后根遍歷第四節(jié) 線索二叉樹一、線索二叉樹的基本概念二、中根線索二叉樹第五節(jié) 二叉樹、樹和森林一、樹的存儲結(jié)構(gòu)二、樹與二叉樹之間的轉(zhuǎn)換三、森林與二叉樹的轉(zhuǎn)換四、樹和森林的遍歷第六節(jié) 哈夫曼樹及其應用第七節(jié) 二叉樹遍歷算法的簡單應用實例 （二）、教學目的要求通過本章的學習讓學生了解樹和森林的遍歷，樹在計算機編程中的應用，理解樹的性質(zhì)、線索二叉樹的含義，掌握數(shù)據(jù)結(jié)構(gòu)中樹的定義和

10、相關(guān)術(shù)語、二叉樹的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、二叉樹的先根遍歷、中根遍歷、后根遍歷和層次遍歷，二叉樹和非二叉樹的一般樹的轉(zhuǎn)換，二叉樹和森林的轉(zhuǎn)換，哈夫曼樹的含義和應用，二叉樹遍歷算法的簡單應用的程序?qū)崿F(xiàn)。在學完本章后，要求學生能夠運用樹的性質(zhì)解決常見的樹的求解問題，同時能夠編程實現(xiàn)樹的遍歷、樹的層數(shù)和葉子總數(shù)等等的計算。重難點分析：本章重點是掌握數(shù)據(jù)結(jié)構(gòu)中樹的定義和相關(guān)術(shù)語，樹的性質(zhì)，二叉樹的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、二叉樹的先根遍歷、中根遍歷、后根遍歷和層次遍歷，二叉樹和非二叉樹的一般樹的轉(zhuǎn)換，二叉樹和森林的轉(zhuǎn)換，哈夫曼樹的含義和應用。難點是理解并掌握如何編程實現(xiàn)二叉樹遍歷算法的簡單應用。第六章 圖第一節(jié)

11、 圖的基本概念一、圖的定義二、圖的基本術(shù)語第二節(jié) 圖的存儲結(jié)構(gòu)一、鄰接矩陣表示法二、鄰接表第三節(jié) 圖的遍歷一、連通圖的深度優(yōu)先搜索遍歷二、連通圖的廣度優(yōu)先搜索遍歷三、求圖的連通分量第四節(jié) 圖的最小生成樹一、生成樹的概念二、網(wǎng)絡(luò)的最小生成樹第五節(jié) 最短路徑一、從某源點到其余頂點之間的最短路徑二、求有向網(wǎng)中每一對頂點間的最短路徑第六節(jié) 有向無環(huán)圖及其應用一、拓撲序列二、關(guān)鍵路徑（二）、教學目的要求通過本章的學習讓學生了解圖在計算機中的常見用途、關(guān)鍵路徑的定義和求解，理解圖的連通分量的求法、拓撲序列，掌握圖的定義及基本術(shù)語、圖的存儲中鄰接矩陣和鄰接表的表示、最小生成樹的求解法、最短路徑的兩種實現(xiàn)方式

12、。在學完本章后，要求學生能夠掌握圖的存儲的編程實現(xiàn)，同時能夠編程實現(xiàn)求解圖的最小生成樹的算法。重難點分析：本章重點是圖的定義及基本術(shù)語、圖的存儲中鄰接矩陣和鄰接表的表示、最小生成樹的求解法、最短路徑的兩種實現(xiàn)方式。難點是關(guān)鍵路徑的求解原理和編程實現(xiàn)。第七章 排序第一節(jié) 排序的基本概念第二節(jié) 插入排序一、直接插入排序二、折半插入排序三、希爾排序第三節(jié) 交換排序一、冒泡排序二、快速排序第四節(jié) 選擇排序一、簡單選擇排序二、堆排序第五節(jié) 歸并排序第六節(jié) 基數(shù)排序第七節(jié) 內(nèi)部排序總結(jié)第八節(jié) 多路歸并用于外排序的簡介第九節(jié) 排序應用實例（二）、教學目的要求通過本章的學習讓學生了解排序的實質(zhì)含義、常見的幾種

13、排序方式的定義，理解常見的幾種排序方式的具體操作、聯(lián)系及區(qū)別，掌握插入排序、交換排序、選擇排序的算法效率和適用環(huán)境。在學完本章后，要求學生能夠掌握插入排序、交換排序、選擇排序的具體操作原理和效率，同時能夠編程實現(xiàn)關(guān)鍵字的排序。重難點分析：本章重點是常見的幾種排序方式的具體操作、聯(lián)系及區(qū)別，插入排序、交換排序、選擇排序的算法效率和適用環(huán)境。難點是插入排序、交換排序、選擇排序的算法效率和適用環(huán)境的確定。第七章 查找第一節(jié) 查找的基本概念第二節(jié) 靜態(tài)查找表一、 順序表的概念二、 順序查找三、 折半查找四、 索引順序查找第三節(jié) 動態(tài)查找表一、 二叉排序查找樹二、 平衡二叉樹與動態(tài)平衡技術(shù)三、 B-樹用

14、于外部查找第四節(jié) 哈希表及其查找一、 哈希表與哈希函數(shù)二、 構(gòu)造哈希函數(shù)的常用方法三、 解決沖突的主要方法四、 哈希查找效率的分析第五節(jié) 查找應用實例（二）、教學目的要求通過本章的學習讓學生了解查找的實質(zhì)含義、順序表的概念、B-樹用于外部查找，理解索引順序查找、平衡二叉樹、動態(tài)平衡技術(shù)、哈希表、哈希函數(shù)的常見構(gòu)造方法和解決沖突的方法，哈希查找效率的分析，掌握二叉查找排序樹的構(gòu)造，順序查找和折半查找的原理及操作步驟。在學完本章后，要求學生能夠掌握二叉查找排序樹的構(gòu)造方法，同時能夠編程實現(xiàn)查找操作。重難點分析：本章重點是常見的幾種排序方式的具體操作、聯(lián)系及區(qū)別，插入排序、交換排序、選擇排序的算法效

15、率和適用環(huán)境。難點是插入排序、交換排序、選擇排序的算法效率和適用環(huán)境的確定。第八章 排序第一節(jié) 了解排序的基本概念第二節(jié) 掌握插入排序方法第三節(jié) 掌握交換排序方法第四節(jié) 掌握選擇排序方法第五節(jié) 掌握歸并排序和基數(shù)排序方法（二）、教學目的要求通過本章的學習讓學生了解排序的基本概念和基本方法。在學完本章后，要求學生能夠掌握插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序，同時能夠編程實現(xiàn)簡單的排序算法。重難點分析：本章重點是幾種基本排序的方法，難點是編程實現(xiàn)排序的算法。六、教學學時分配（表格展示各章或各個模塊的學時分配） 章節(jié)序號課堂講授課時1第一章 數(shù)據(jù)結(jié)構(gòu)的基本概念； 22第二章 線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)循環(huán)鏈表，實現(xiàn)多項式相加問題 43第三章 棧的定義、運算和結(jié)構(gòu)、隊列，棧和隊列的應用實例24第四章 數(shù)組和矩陣的相關(guān)知識25第五章 樹的定義及