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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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