數(shù)據(jù)結(jié)構(gòu)與算法分析 Data Structure

1、數(shù)據(jù)結(jié)構(gòu)與算法分析 Data Structure 第一章、緒論 1、教學(xué)內(nèi)容 （1）數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、算法等； （2）抽象數(shù)據(jù)類(lèi)型； （3）描述算法所用的類(lèi)C語(yǔ)言中的一些有關(guān)問(wèn)題； （4）算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。 2、學(xué)習(xí)緒論的基本要求 了解本課程的性質(zhì)、任務(wù)和目的，掌握數(shù)據(jù)結(jié)構(gòu)的一些基本概念，掌握算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法，了解抽象數(shù)據(jù)類(lèi)型的定義和使用，了解算法的描述方法。 第二章、線性表 1、教學(xué)內(nèi)容 （1）線性表的基本概念和類(lèi)型定義； （2）線性表的順序存儲(chǔ)結(jié)構(gòu)； （3）線性表的鏈接存儲(chǔ)結(jié)構(gòu) A、單鏈表的查

2、找、插入和刪除； B、循環(huán)鏈表； C、雙向鏈表； D、一元多項(xiàng)式的表示及相加。 2、基本要求 掌握線性表的基本概念和類(lèi)型定義；熟練掌握對(duì)順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)；掌握循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法；掌握一元多項(xiàng)式的表示及相加運(yùn)算。 第三章、棧和隊(duì)列 1、教學(xué)內(nèi)容 （1）棧的類(lèi)型定義； （2）棧的順序存儲(chǔ)和鏈接存儲(chǔ)的表示； （3）在棧的順序存儲(chǔ)和鏈接存儲(chǔ)上進(jìn)行各種棧操作的算法； （4）棧的應(yīng)用舉例； （5）隊(duì)列的類(lèi)型定義； （6）隊(duì)列的順序存儲(chǔ)(循環(huán)隊(duì)列)和鏈接存儲(chǔ)表示及各種操作的實(shí)現(xiàn)算法。 2、基本要求 掌握棧和隊(duì)列的定義，熟練掌握順序和鏈接存儲(chǔ)的棧和隊(duì)列的

3、各種運(yùn)算的方法及其程序?qū)崿F(xiàn)，掌握表達(dá)式求值等方法并了解其算法。 第四章、串、數(shù)組和廣義表 1、教學(xué)內(nèi)容 （1）串的定義、存儲(chǔ)結(jié)構(gòu)和操作； （2）數(shù)組的定義、抽象數(shù)據(jù)類(lèi)型以及順序存儲(chǔ)結(jié)構(gòu)； （3）特殊矩陣和稀疏矩陣的定義、存儲(chǔ)和運(yùn)算； （4）廣義表的定義和存儲(chǔ)結(jié)構(gòu)。 2、 基本要求 掌握串的定義、存儲(chǔ)結(jié)構(gòu)和操作；掌握數(shù)組的定義、抽象數(shù)據(jù)類(lèi)型以及順序存儲(chǔ)結(jié)構(gòu)；掌握特殊矩陣和稀疏矩陣的定義以及各種存儲(chǔ)結(jié)構(gòu)，掌握稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；掌握廣義表的定義、存儲(chǔ)結(jié)構(gòu)的表示方法。第五章、樹(shù)和二叉樹(shù) 1、教學(xué)內(nèi)容 （1）樹(shù)的定義、術(shù)語(yǔ)、表示形式、基本操作和抽象數(shù)據(jù)類(lèi)型； （2）二叉樹(shù)的定義、性

4、質(zhì)、基本操作和抽象數(shù)據(jù)類(lèi)型以及存儲(chǔ)結(jié)構(gòu)； （3）遍歷二叉樹(shù)和線索二叉樹(shù)； （4）哈夫曼樹(shù)的定義、構(gòu)造哈夫曼樹(shù)的方法及哈夫曼編碼的方法； （5）樹(shù)和森林：樹(shù)的存儲(chǔ)結(jié)構(gòu)，樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換，樹(shù)的遍歷，森林的遍歷。 2、基本要求 掌握樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)以及樹(shù)和森林的遍歷算法，熟練掌握二叉樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、各種遍歷方法及其實(shí)現(xiàn)，掌握二叉樹(shù)的其他操作方法及實(shí)現(xiàn)，掌握樹(shù)和二叉樹(shù)的轉(zhuǎn)換方法，掌握哈夫曼樹(shù)應(yīng)用。 第六章、圖 1、教學(xué)內(nèi)容 （1）圖的定義、術(shù)語(yǔ)、基本操作和抽象數(shù)據(jù)類(lèi)型； （2）圖的各種存儲(chǔ)結(jié)構(gòu)； （3）圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷以及圖的連通分量； （4）圖的生成樹(shù)和最小生成

5、樹(shù)； （5）有向無(wú)環(huán)圖及其應(yīng)用； （6）最短路徑。 2、基本要求 掌握?qǐng)D的定義和術(shù)語(yǔ)；熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)；掌握?qǐng)D的生成樹(shù)的概念，掌握求圖的最小生成樹(shù)的普里姆法和克魯斯卡爾法并了解其實(shí)現(xiàn)算法；掌握拓?fù)渑判虻姆椒ú⒘私馄鋵?shí)現(xiàn)算法，了解AOE網(wǎng)絡(luò)。 第七章、查找 1、教學(xué)內(nèi)容 （1）查找的基本概念； （2）順序表的查找、有序表的折半查找以及索引順序表查找； （3）二叉排序樹(shù)定義、查找、插入、刪除以及查找性能的分析； （4）平衡二叉樹(shù)的定義、平衡旋轉(zhuǎn)以及B-樹(shù)； （5）散列表的基本概念、散列函數(shù)、處理溢出的閉散列方法和開(kāi)散列方法以及散列表分析。 2、基本要求 了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、二叉排序樹(shù)、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度，理解平衡二叉樹(shù)、了解B-樹(shù)。