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

課程類別：專業(yè)基礎(chǔ)課適用專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)授課學(xué)時(shí)：32學(xué)時(shí)課程學(xué)分：4學(xué)分一、課程性質(zhì)、任務(wù)對(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)物理結(jié)構(gòu)和邏輯結(jié)構(gòu)，在重要算法的實(shí)現(xiàn)上逐步提高編程能力。（二）技能目標(biāo)程序解決實(shí)際中的問題。（三）素質(zhì)目標(biāo)能力，同時(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葉小平陳瑛主編教材使用評(píng)價(jià)清華大學(xué)出版社本教材經(jīng)過兩年的使用，得到了讀者一致認(rèn)可，同時(shí)也在不斷改進(jìn)，適合高的要求。1選用的參考資料嚴(yán)蔚敏.吳偉民《數(shù)據(jù)結(jié)構(gòu)（C年版殷人昆.《數(shù)據(jù)結(jié)構(gòu)》.清華大學(xué)出版社.1999年版《C語(yǔ)言程序設(shè)計(jì)》.石油大學(xué)出版社《C語(yǔ)言程序設(shè)計(jì)》.中國(guó)石油大學(xué)出版社.2006年版四、本課程與其他課程的聯(lián)系與分工先修課程后續(xù)課程與其他課程配合與取舍情況鋪墊。同時(shí)《程序設(shè)計(jì)基礎(chǔ)》課程也為學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》打下了基礎(chǔ)，對(duì)于本課CC語(yǔ)言作為的對(duì)象。本課程也與《算法設(shè)計(jì)與分析》結(jié)合得很緊密，因此在學(xué)習(xí)中我們也會(huì)引入常見算法的學(xué)習(xí)，達(dá)到兩者共同促進(jìn)的目的。五、課程教學(xué)內(nèi)容與基本要求第一章數(shù)據(jù)結(jié)構(gòu)導(dǎo)論第一節(jié)數(shù)據(jù)結(jié)構(gòu)的基本概念一、引言二、數(shù)據(jù)結(jié)構(gòu)有關(guān)概念及術(shù)語(yǔ)第二節(jié)算法和算法描述一、什么是算法二、算法描述工具——類C語(yǔ)言第三節(jié)算法評(píng)價(jià)一、時(shí)間二、空間C語(yǔ)言來描法效率和用函數(shù)式表示該程序的算法效率。使用這一知識(shí)點(diǎn)來優(yōu)化自己所寫程序的執(zhí)行效率。2C從程序中分析算法效率和用函數(shù)式表示該程序的算法效率。第二章線性表第一節(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é)習(xí)讓學(xué)生進(jìn)一步了解線性表的定義、稀疏矩陣的三元組存儲(chǔ)，掌握C存儲(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)線性表中元素的插入和刪除操?zèng)Q多項(xiàng)式相加問題、運(yùn)用數(shù)組實(shí)現(xiàn)矩陣的轉(zhuǎn)置問題。算法以及稀疏矩陣的十字鏈表算法。第三章棧和隊(duì)列第一節(jié)棧一、棧的定義及其運(yùn)算二、棧的順序存儲(chǔ)結(jié)構(gòu)三、棧的鏈?zhǔn)酱鎯?chǔ)四、棧的應(yīng)用舉例第二節(jié)隊(duì)列3一、隊(duì)列的定義及運(yùn)算二、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)三、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第三節(jié)棧和隊(duì)列的應(yīng)用實(shí)例——停車場(chǎng)管理和隊(duì)列的基本操作，掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。敢死隊(duì)問題等經(jīng)典算法。操作。第四章串和數(shù)組第一節(jié)串的定義一、串的定義二、串的存儲(chǔ)結(jié)構(gòu)第二節(jié)數(shù)組的基本概念一、數(shù)組的定義二、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)第三節(jié)特殊矩陣和稀疏矩陣壓縮存儲(chǔ)一、特殊矩陣壓縮存儲(chǔ)二、稀疏矩陣壓縮存儲(chǔ)法。用數(shù)組實(shí)現(xiàn)矩陣的轉(zhuǎn)置問題。算法。難點(diǎn)是編寫程序?qū)崿F(xiàn)矩陣的兩種轉(zhuǎn)置算法以及稀疏矩陣的十字鏈表算法。第五章樹第一節(jié)樹的定義和基本術(shù)語(yǔ)一、樹的定義二、樹的基本術(shù)語(yǔ)第二節(jié)二叉樹4一、二叉樹的定義二、二叉樹的重要性質(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í)例的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、二叉樹的先根遍歷、中根遍歷、后根遍歷和層次遍歷，用，二叉樹遍歷算法的簡(jiǎn)單應(yīng)用的程序?qū)崿F(xiàn)。能夠編程實(shí)現(xiàn)樹的遍歷、樹的層數(shù)和葉子總數(shù)等等的計(jì)算。重難點(diǎn)分析：本章重點(diǎn)是掌握數(shù)據(jù)結(jié)構(gòu)中樹的定義和相關(guān)術(shù)語(yǔ)，樹的性質(zhì)，義和應(yīng)用。難點(diǎn)是理解并掌握如何編程實(shí)現(xiàn)二叉樹遍歷算法的簡(jiǎn)單應(yīng)用。第六章圖第一節(jié)圖的基本概念一、圖的定義二、圖的基本術(shù)語(yǔ)第二節(jié)圖的存儲(chǔ)結(jié)構(gòu)一、鄰接矩陣表示法二、鄰接表5第三節(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)鍵路徑解，理解圖的連通分量的求法、拓?fù)湫蛄?，掌握?qǐng)D的定義及基本術(shù)語(yǔ)、圖的存儲(chǔ)中鄰接矩陣和鄰接表的表示、最小生成樹的求解法、最短路徑的兩種實(shí)現(xiàn)方式。求解圖的最小生成樹的算法。求解原理和編程實(shí)現(xiàn)。第七章排序第一節(jié)排序的基本概念第二節(jié)插入排序一、直接插入排序二、折半插入排序三、希爾排序第三節(jié)交換排序一、冒泡排序二、快速排序第四節(jié)選擇排序一、簡(jiǎn)單選擇排序二、堆排序第五節(jié)歸并排序第六節(jié)基數(shù)排序第七節(jié)內(nèi)部排序總結(jié)6第八節(jié)多路歸并用于外排序的簡(jiǎn)介第九節(jié)排序應(yīng)用實(shí)例通過本章的學(xué)習(xí)讓學(xué)生了解排序的實(shí)質(zhì)含義、常見的幾種排序方式的定義，理解常見的幾種排序方式的具體操作、聯(lián)系及區(qū)別，掌握插入排序、交換排序、選擇排序的算法效率和適用環(huán)境。作原理和效率，同時(shí)能夠編程實(shí)現(xiàn)關(guān)鍵字的排序。入排序、交換排序、選擇排序的算法效率和適用環(huán)境。難點(diǎn)是插入排序、交換排序、選擇排序的算法效率和適用環(huán)境的確定。第七章查找第一節(jié)查找的基本概念第二節(jié)靜態(tài)查找表一、順序表的概念二、順序查找三、折半查找四、索引順序查找第三節(jié)動(dòng)態(tài)查找表一、二叉排序查找樹二、平衡二叉樹與動(dòng)態(tài)平衡技術(shù)三、B-樹用于外部查找第四節(jié)哈希表及其查找一、哈希表與哈希函數(shù)二、構(gòu)造哈希函數(shù)的常用方法三、解決沖突的主要方法四、哈希查找效率的分析第五節(jié)查找應(yīng)用實(shí)例查找，理解索引順序查找、平衡二叉樹、動(dòng)態(tài)平衡技術(shù)、哈希表、哈希函數(shù)的常造，順序查找和折半查找的原理及操作步驟。程實(shí)現(xiàn)查找操作。入排序、交換排序、選擇排序的算法效率和適用環(huán)境。難點(diǎn)是插入排序、交換排7序、選擇排序的算法效率和適用環(huán)境的確定。第八章排序第一節(jié)了解排序的基本概念第二節(jié)掌握插入排序方法第三節(jié)掌握交換排序方法第四節(jié)掌握選擇排序方法第五節(jié)掌握歸并排序和基數(shù)排序方法通過本章的學(xué)習(xí)讓學(xué)生了解排序的基本概念和基本方法。在學(xué)完本章后，要求學(xué)生能夠掌握插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序，同時(shí)能夠編程實(shí)現(xiàn)簡(jiǎn)單的排序算法。六、教學(xué)學(xué)時(shí)分配（表格展示各章或各個(gè)模塊的學(xué)時(shí)分配）課時(shí)2第二章線性表的邏輯結(jié)422第五章樹及其應(yīng)用，二叉樹遍歷算法的簡(jiǎn)單應(yīng)