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

1、1課程簡(jiǎn)介人們?cè)谶\(yùn)用程序設(shè)計(jì)語(yǔ)言編寫程序的過(guò)程中發(fā)現(xiàn)所有的數(shù)據(jù)都可以抽象為三種結(jié)構(gòu)，而對(duì)這些數(shù)據(jù)的所有操作都可以轉(zhuǎn)化為對(duì)這三種數(shù)據(jù)的幾種基本操作，而大多數(shù)的程序設(shè)計(jì)技巧都可以抽象為一些最基本的算法。于是人們逐步發(fā)展了一門稱為數(shù)據(jù)結(jié)構(gòu)（或數(shù)據(jù)結(jié)構(gòu)與算法）的計(jì)算機(jī)科學(xué)，它廣泛應(yīng)用于計(jì)算機(jī)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)是信息與計(jì)算專業(yè)的核心基礎(chǔ)課程之一。數(shù)據(jù)是計(jì)算機(jī)處理的對(duì)象，本課程研究的數(shù)據(jù)是非數(shù)值性、結(jié)構(gòu)性的數(shù)據(jù)。學(xué)習(xí)本課程要求掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)

2、、計(jì)算機(jī)內(nèi)的表示方法，以及處理數(shù)據(jù)的算法，對(duì)于算法所花費(fèi)的時(shí)間和空間代價(jià)的分析也要求有一定程度的了解和掌握。通過(guò)本課程的學(xué)習(xí)，使學(xué)生透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)基本的良好的程序設(shè)計(jì)能力。本課程主要包括如下三個(gè)方面的內(nèi)容：1基本數(shù)據(jù)結(jié)構(gòu)：線性表、棧、隊(duì)列、串、數(shù)組和廣義表，掌握它們的特點(diǎn)、表示和實(shí)現(xiàn)，對(duì)靜態(tài)結(jié)構(gòu)要求非常熟練的編程上機(jī)實(shí)現(xiàn)，對(duì)動(dòng)態(tài)結(jié)構(gòu)要求逐步熟悉鏈表的表示，通過(guò)模仿實(shí)驗(yàn)教程中的例子

3、，掌握編程技巧。強(qiáng)調(diào)類C語(yǔ)言的書(shū)寫規(guī)范，特別注意參數(shù)的區(qū)別，輸入輸出的方式和錯(cuò)誤處理方式，以及抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。能熟練完成以下的應(yīng)用：多項(xiàng)式的計(jì)算、語(yǔ)法檢查、回朔算法、遞歸算法、表達(dá)式求值、離散事件模擬、文字的編輯和稀疏矩陣進(jìn)行矩陣運(yùn)算采用的處理方法。2復(fù)雜數(shù)據(jù)結(jié)構(gòu)：樹(shù)、二叉樹(shù)、圖。掌握它們的定義和特點(diǎn)、表示和實(shí)現(xiàn)，特別注意與基本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹(shù)、Huffman編碼、拓

4、撲排序、關(guān)鍵路徑和最短路徑問(wèn)題。3數(shù)據(jù)結(jié)構(gòu)的應(yīng)用：查找和內(nèi)部排序。熟練掌握靜態(tài)查找表的查找方法和實(shí)現(xiàn)，了解哈希表的構(gòu)造和查找方法。掌握各種內(nèi)部排序方法的基本思想、算法特點(diǎn)、排序過(guò)程以及它們的時(shí)間復(fù)雜度分析。33.2棧的應(yīng)有和舉例3.2.1數(shù)制轉(zhuǎn)換3.3.4迷宮求解3.3棧與遞歸的實(shí)現(xiàn)3.4隊(duì)列教學(xué)要求：理解棧和隊(duì)列的定義、特點(diǎn)，學(xué)習(xí)它們的各種組織方式及算法；掌握它們的空和滿的判斷條件；并學(xué)會(huì)它們的簡(jiǎn)單應(yīng)用。第四章：串第四章：串4.1串類

5、型的定義4.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示4.2.3串的塊鏈存儲(chǔ)表示4.3串的模式匹配算法4.3.1求字串位置的定位函數(shù)教學(xué)要求：了解串的概念，掌握串的基本運(yùn)算，學(xué)習(xí)串運(yùn)算在不同存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)過(guò)程。第五章：多維數(shù)組和廣義表第五章：多維數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表現(xiàn)和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)教學(xué)要求：領(lǐng)會(huì)數(shù)組的定義，數(shù)組的兩種順序存儲(chǔ)結(jié)構(gòu)，并領(lǐng)會(huì)幾種特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法。第六章：樹(shù)第六章：樹(shù)6.

6、1樹(shù)的定義和基本術(shù)語(yǔ)6.2二叉樹(shù)6.2.1二叉樹(shù)的定義6.2.2二叉樹(shù)的性質(zhì)6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.3.1遍歷二叉樹(shù)6.4樹(shù)和森林6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4.2森林與二叉樹(shù)的轉(zhuǎn)換6.4.3樹(shù)和森林的遍歷6.6赫夫曼樹(shù)及其應(yīng)用6.6.1最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）6.6.2赫夫曼編碼教學(xué)要求：理解樹(shù)型結(jié)構(gòu)的概念和術(shù)語(yǔ)，領(lǐng)會(huì)二叉樹(shù)的定義、形態(tài)、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，掌握二叉樹(shù)的各種遍歷算法極其實(shí)現(xiàn)過(guò)程，了解樹(shù)和森林及