數(shù)據(jù)結(jié)構(gòu)主要學(xué)習(xí)內(nèi)容ppt課件

1、數(shù)據(jù)結(jié)構(gòu)與算法n主講人：陳安龍主講人：陳安龍n電子科技大學(xué)信息與軟件工程學(xué)院電子科技大學(xué)信息與軟件工程學(xué)院n第第1章章 緒論緒論n第第2章章 線性表線性表n第第3章章 樹樹n第第4章章 圖圖n第第6章章 查找查找n第第7章章 排序排序主要內(nèi)容主要內(nèi)容第第1章章 緒論緒論本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容 什么是數(shù)據(jù)什么是數(shù)據(jù) 數(shù)據(jù)元素?cái)?shù)據(jù)元素 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)類型、抽象數(shù)據(jù)類型數(shù)據(jù)類型、抽象數(shù)據(jù)類型 算法的定義、算法的特性、算法的時(shí)空代價(jià)算法的定義、算法的特性、算法的時(shí)空代價(jià)本章要求本章要求n掌握數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容n掌握數(shù)據(jù)結(jié)構(gòu)的含

2、義n對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)有一個(gè)初步的認(rèn)識(shí)n理解算法的時(shí)間復(fù)雜度和空間復(fù)雜度n理解數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的關(guān)系n掌握算法的特性和度量算法優(yōu)劣的標(biāo)準(zhǔn)。 本章重點(diǎn)內(nèi)容本章重點(diǎn)內(nèi)容n數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義n數(shù)據(jù)結(jié)構(gòu)的含義n順序存儲(chǔ)n鏈?zhǔn)酱鎯?chǔ)n線性結(jié)構(gòu)n非線性結(jié)構(gòu)本章難點(diǎn)本章難點(diǎn)n抽象數(shù)據(jù)類型n算法的時(shí)間復(fù)雜度n空間復(fù)雜度第第2章章 線性表線性表本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容線性表的特點(diǎn)、基本運(yùn)算、線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)骄€性表的特點(diǎn)、基本運(yùn)算、線性表的順序存儲(chǔ)、線性表的鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)順序表的靜態(tài)分配和動(dòng)態(tài)分配；順序表的靜態(tài)分配和動(dòng)態(tài)分配；鏈?zhǔn)酱鎯?chǔ)的單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)

3、鏈鏈?zhǔn)酱鎯?chǔ)的單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表表受限的線性表?xiàng)：完?duì)列定義受限的線性表?xiàng)：完?duì)列定義棧的入棧，出棧，取棧頂元素操作，棧的兩種存儲(chǔ)結(jié)構(gòu)：順序棧的入棧，出棧，取棧頂元素操作，棧的兩種存儲(chǔ)結(jié)構(gòu)：順序棧和鏈棧。棧和鏈棧。隊(duì)列的入隊(duì)，出隊(duì)等基本操作，循環(huán)隊(duì)列，鏈隊(duì)列的表示，實(shí)隊(duì)列的入隊(duì)，出隊(duì)等基本操作，循環(huán)隊(duì)列，鏈隊(duì)列的表示，實(shí)現(xiàn)及特點(diǎn)?，F(xiàn)及特點(diǎn)。遞歸的概念，特點(diǎn)及遞歸算法的設(shè)計(jì)遞歸的概念，特點(diǎn)及遞歸算法的設(shè)計(jì)數(shù)組的按行和按列的存儲(chǔ)方式，兩種存儲(chǔ)方式下數(shù)組元素存儲(chǔ)數(shù)組的按行和按列的存儲(chǔ)方式，兩種存儲(chǔ)方式下數(shù)組元素存儲(chǔ)地址的計(jì)算方法，稀疏矩陣的概念及三元組及十字鏈表的壓地址的計(jì)算方

4、法，稀疏矩陣的概念及三元組及十字鏈表的壓縮存儲(chǔ)方式，稀疏矩陣的轉(zhuǎn)置，相乘等基本操作?？s存儲(chǔ)方式，稀疏矩陣的轉(zhuǎn)置，相乘等基本操作。本章要求本章要求n理解線形表的4類基本操作類型n掌握線性表的兩種存儲(chǔ)表示及其實(shí)現(xiàn)n掌握順序表和鏈表的一些常見操作n理解順序表和鏈表在存儲(chǔ)及實(shí)現(xiàn)上的異同n理解雙向鏈表，循環(huán)鏈表，雙向循環(huán)鏈表和靜態(tài)鏈表的存儲(chǔ)特征及用途。n掌握棧和隊(duì)列定義，特征及基本操作，掌握這兩種線性結(jié)構(gòu)的應(yīng)用場(chǎng)合，理解假溢出的概念，n掌握循環(huán)隊(duì)列的入隊(duì)，出隊(duì)，判滿，判空等基本操作，n理解遞歸的含義及遞歸算法設(shè)計(jì)的思想。n掌握數(shù)組的地址計(jì)算方法n掌握稀疏矩陣的概念及稀疏矩陣的兩種存儲(chǔ)方法n理解稀疏矩陣的

5、相關(guān)計(jì)算方法。 本章重點(diǎn)本章重點(diǎn)n順序表和鏈表的C語言表示的數(shù)據(jù)結(jié)構(gòu)，以及對(duì)應(yīng)結(jié)構(gòu)插入，刪除，查詢等常見操作。n棧和隊(duì)列的定義，棧的入棧，出棧操作，隊(duì)列及鏈隊(duì)列的的入隊(duì)，出隊(duì)操作，循環(huán)隊(duì)列的判空，判滿。n數(shù)組的兩種存儲(chǔ)方式，稀疏矩陣的概念及表示方法。本章難點(diǎn)本章難點(diǎn)n順序表和鏈表的存儲(chǔ)和在此兩種存儲(chǔ)映像上的基本操作n雙向循環(huán)鏈表和靜態(tài)鏈表的插入與刪除n一元多項(xiàng)式的加法和乘法運(yùn)算。n棧和隊(duì)列的基本操作，遞歸算法的設(shè)計(jì)。n稀疏矩陣的三元組和十字鏈表的表示方式及實(shí)現(xiàn)算法，如快速矩陣轉(zhuǎn)置。第第3章章 樹樹本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容樹的定義和基本術(shù)語樹的定義和基本術(shù)語二叉樹的定義及性質(zhì)，滿二叉樹和

6、完全二叉樹的概念二叉樹的定義及性質(zhì)，滿二叉樹和完全二叉樹的概念及特征，二叉樹的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)及特征，二叉樹的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)二叉樹的前序，中序和后序遍歷方法，線索二叉樹的二叉樹的前序，中序和后序遍歷方法，線索二叉樹的構(gòu)建，線索二叉樹中的節(jié)點(diǎn)插入與刪除構(gòu)建，線索二叉樹中的節(jié)點(diǎn)插入與刪除樹和森林的三種存儲(chǔ)表示方法及其遍歷操作，二叉樹，樹和森林的三種存儲(chǔ)表示方法及其遍歷操作，二叉樹，樹及森林間的相互轉(zhuǎn)換樹及森林間的相互轉(zhuǎn)換二叉排序樹，二叉平衡樹，二叉排序樹，二叉平衡樹，B-樹，鍵樹，四叉樹，樹，鍵樹，四叉樹，2-3樹的基本概念及相應(yīng)的查找方法，節(jié)點(diǎn)增刪方法樹的基本概念及相應(yīng)的查找方法，節(jié)點(diǎn)增刪

7、方法二叉樹及樹的典型應(yīng)用二叉樹及樹的典型應(yīng)用表達(dá)式求值，哈夫曼樹的表達(dá)式求值，哈夫曼樹的構(gòu)建和哈夫曼編碼構(gòu)建和哈夫曼編碼堆的構(gòu)建和堆排序方法堆的構(gòu)建和堆排序方法 本章要求本章要求n掌握二叉樹，樹，森林的基本概念n理解滿二叉樹和完全二叉樹的概念和特征。 n掌握樹的遍歷以及之間的相互轉(zhuǎn)換n掌握二叉樹的基本性質(zhì)n掌握線索二叉樹的構(gòu)建以及在線索二叉樹上的基本操作n掌握二叉排序樹，二叉平衡樹，B-樹，2-3樹的基本操作n掌握哈夫曼樹的構(gòu)建，哈夫曼編碼，堆排序方法本章重點(diǎn)本章重點(diǎn)n二叉樹，樹，森林的基本概念和遍歷操作n二叉樹，樹及森林相互間的轉(zhuǎn)換n線索二叉樹的構(gòu)建，線索二叉樹中節(jié)點(diǎn)的刪除，n二叉排序樹，二

8、叉平衡樹，B-樹，2-3樹的基本操作，哈夫曼樹的定義和建立本章難點(diǎn)本章難點(diǎn)n二叉樹，樹，森林的各種遍歷n線索二叉樹的構(gòu)建n線索二叉樹中節(jié)點(diǎn)的刪除n含左子樹和右子樹的二叉排序樹節(jié)點(diǎn)刪除方法n二叉平衡樹的4種調(diào)整方法n堆的調(diào)整n哈夫曼編碼 第第4章章 圖圖本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容圖的基本概念和基本術(shù)語圖的基本概念和基本術(shù)語圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷圖的基本操作和存儲(chǔ)方法圖的基本操作和存儲(chǔ)方法鄰接矩陣、關(guān)聯(lián)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、逆鄰接表、十字鏈表鄰接表、逆鄰接表、十字鏈表圖的遍歷方法圖的遍歷方法深度優(yōu)先和寬度優(yōu)先，深度優(yōu)先和寬度優(yōu)先，圖的生成樹和最小生成樹圖的生

9、成樹和最小生成樹最小生成樹的兩種構(gòu)建方法最小生成樹的兩種構(gòu)建方法普里姆和克魯斯卡爾。普里姆和克魯斯卡爾。最短路徑、關(guān)鍵路徑最短路徑、關(guān)鍵路徑最短路徑的求取方法最短路徑的求取方法迪杰斯特拉和弗洛伊德方法，迪杰斯特拉和弗洛伊德方法，有向無環(huán)圖的拓?fù)渑判蚝完P(guān)鍵路徑求取。有向無環(huán)圖的拓?fù)渑判蚝完P(guān)鍵路徑求取。本章要求本章要求n掌握?qǐng)D的基本概念和術(shù)語n圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣和鄰接表n圖基本操作深度優(yōu)先和廣度優(yōu)先遍歷n最小生成樹、結(jié)點(diǎn)間的最短路徑n圖的拓?fù)渑判蛞约瓣P(guān)鍵路徑。n理解圖的層次遍歷，圖的連通分支及圖的基本應(yīng)用。 本章重點(diǎn)本章重點(diǎn)n圖的鄰接矩陣和鄰接表的存儲(chǔ)表示n圖的深度優(yōu)先和廣度優(yōu)先遍歷n圖的最小生

10、成樹及其求取方法n圖中兩結(jié)點(diǎn)間及所有結(jié)點(diǎn)間的最短路徑求取n有向無環(huán)圖的拓?fù)渑判騨關(guān)鍵路徑的求取方法。 本章難點(diǎn)本章難點(diǎn)n圖的基本操作和存儲(chǔ)方法鄰接矩陣、關(guān)聯(lián)矩陣、鄰接表、逆鄰接表、十字鏈表n圖的生成樹和最小生成樹n最小生成樹的兩種構(gòu)建方法普里姆和克魯斯卡爾。n最短路徑、關(guān)鍵路徑n最短路徑的求取方法迪杰斯特拉和弗洛伊德方法第第6章章 查找查找本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容查找的基本概念和術(shù)語查找的基本概念和術(shù)語順序查找順序查找折半查找折半查找索引查找的方法。索引查找的方法。哈希表的基本概念哈希表的基本概念哈希函數(shù)構(gòu)造方法及沖突處理策略哈希函數(shù)構(gòu)造方法及沖突處理策略哈希表的查找，刪除等操作方法。

11、哈希表的查找，刪除等操作方法。本章要求本章要求n掌握順序查找，折半查找，索引查找以及哈希表的查找方法n掌握哈希函數(shù)的基本構(gòu)造方法n掌握解決地址沖突的基本策略。n理解各查找算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 本章重點(diǎn)本章重點(diǎn)n順序表的順序查找n有序表的折半查找n哈希表的查找n哈希函數(shù)的構(gòu)造和地址沖突解決辦法。本章難點(diǎn)本章難點(diǎn)n折半查找n哈希查找第第7章章 排序排序本章主要學(xué)習(xí)內(nèi)容本章主要學(xué)習(xí)內(nèi)容排序的基本概念排序的基本概念排序算法及復(fù)雜度分析排序算法及復(fù)雜度分析插入排序，快速排序，選擇排序，堆排序插入排序，快速排序，選擇排序，堆排序歸并排序和基數(shù)排序歸并排序和基數(shù)排序本章要求本章要求n掌握直接插入排序n