數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)總結(jié)

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)總結(jié) 第一章緒論1 什么是數(shù)據(jù)結(jié)構(gòu)(1.1、1.2)(1) 基本概念：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型(2) 數(shù)據(jù)結(jié)構(gòu)的分類(兩類、四類)(3) 數(shù)據(jù)結(jié)構(gòu)的形式定義(二元組)(4) 數(shù)據(jù)結(jié)構(gòu)研究?jī)?nèi)容：三方面(邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)運(yùn)算的表示) 邏輯結(jié)構(gòu)的概念物理結(jié)構(gòu)的概念兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)(順序映像)、非順序存儲(chǔ)(鏈?zhǔn)酱鎯?chǔ)或非順序映像)2 算法和算法分析(1.3、1.5 )(1) 算法的概念(2) 算法的五個(gè)重要特性(3) 算法設(shè)計(jì)要求(四點(diǎn))(4) 算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系(5) 算法的描述(流程圖、自然語言、類c、實(shí)現(xiàn)用c(c+)等)，在設(shè)計(jì)算法 時(shí)，描述前最好有算法思想的描

2、述(6) 算法分析(主要側(cè)重在效率分析：時(shí)間復(fù)雜度、空間復(fù)雜度)時(shí)間復(fù)雜度：主要由重要語句的頻度得來，對(duì)問題規(guī)模的函數(shù)。第二章線性表1. 線性表結(jié)構(gòu)的定義(1) 線性的概念、特點(diǎn)(2) 抽象數(shù)據(jù)類型定義：數(shù)據(jù)結(jié)構(gòu)的抽象表示定義在其上的基本操作(3) 線性表的存儲(chǔ)結(jié)構(gòu)：兩種2 順序表及其基本操作(1) 順序表的定義、表示形式(數(shù)組)及特點(diǎn)(優(yōu)、缺點(diǎn))(2) 基本操作：插入、刪除、查找、合并(3) 插入、刪除的時(shí)間性能2. 鏈表及其基本操作(1) 鏈表的定義、表示及特點(diǎn)(注意頭結(jié)點(diǎn)和頭指針的概念的不同，帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的不同)(2) 幾種存儲(chǔ)結(jié)構(gòu)的定義、特點(diǎn)(3) 基本操作：插入、刪除、查找、

3、合并鏈表判空的條件，插入、刪除指針的改變(注意語句序列)、不同鏈表上插 入、刪除結(jié)點(diǎn)的操作語句a. 單鏈表b. 雙向鏈表c. 循環(huán)鏈表3順序表與鏈表的比較，各自的優(yōu)缺點(diǎn)不同鏈表之間的比較。第三章棧和隊(duì)列1棧(3.1)(1) 定義、特點(diǎn)、存儲(chǔ)形式(2) 基本操作空棧判斷(top=0，top=base)初始化、入棧、出棧、取棧頂元素(3) 棧的應(yīng)用舉例中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 表達(dá)式求值的算法。遞歸的實(shí)現(xiàn)。2 隊(duì)列(3.2 )(1) 定義、特點(diǎn)、存儲(chǔ)形式(2) 基本操作判空、判滿、插入(入隊(duì))、刪除(出隊(duì))(3) 鏈隊(duì)的表示、實(shí)現(xiàn)(3.2.2 1)(4) 循環(huán)隊(duì)列(3.2.2 2)循環(huán)隊(duì)列為解決

4、什么問題而引入的取模運(yùn)算構(gòu)成、判空、判滿條件、插入(入隊(duì))、刪除(出隊(duì))用帶尾指針的單循環(huán)鏈表表示循環(huán)隊(duì)列的優(yōu)點(diǎn)。第四章串1. 串的定義(4.1 )2. 串的表示和實(shí)現(xiàn)順序存儲(chǔ)(4.2.1)3. 串的基本操作(最小操作集)4. 串匹配(1) 匹配的含義(2) 串的匹配算法樸素算法 第五章數(shù)組和廣義表1. 數(shù)組的定義2. 順序表示和實(shí)現(xiàn)(5.2)數(shù)組元素的存儲(chǔ)位置確定(行優(yōu)先、列優(yōu)先)4. 矩陣(1) 特殊矩陣和稀疏矩陣的定義(2) 特殊矩陣的壓縮存儲(chǔ)三角矩陣對(duì)稱矩陣(2)稀疏矩陣的壓縮存儲(chǔ) 三元組和十字鏈表的特點(diǎn)、表示5. 廣義表(1) 定義、求表頭、表尾、深度(2) 存儲(chǔ)結(jié)構(gòu)由廣義表表示其存

5、儲(chǔ)結(jié)構(gòu)由存儲(chǔ)結(jié)構(gòu)得出廣義表 第六章樹和二叉樹1. 樹的定義和基本術(shù)語(6.1)2 .二叉樹的定義和性質(zhì)(6.2 )3. 存儲(chǔ)結(jié)構(gòu)(6.2.3 )重點(diǎn)掌握二叉鏈表的存儲(chǔ)方式。4. 二叉樹的遍歷(6.3(1) 遍歷的概念及方法(四種)(2) 遍歷的遞歸和非遞歸算法(3) 遍歷算法的應(yīng)用：求結(jié)點(diǎn)數(shù)、葉子結(jié)點(diǎn)數(shù)、深度、交換等(4) 線索二叉樹的概念(5) 線索二叉樹的存儲(chǔ)(6) 由遍歷確定二叉樹5. 樹和森林(1) 樹的存儲(chǔ)了解幾種存儲(chǔ)方式，掌握孩子兄弟表示法。(2) 樹及森林與二叉樹的轉(zhuǎn)換(3) 樹和森林的遍歷6. 哈夫曼樹及其應(yīng)用(6.5)(1) 哈夫曼樹的定義(2) 構(gòu)造哈夫曼樹方法(畫圖，算法

6、)(3) 哈夫曼編碼(由畫圖得出以及算法)(4) 求樹的帶權(quán)路徑長(zhǎng)度和哈夫曼編碼長(zhǎng)度第七章圖1. 圖的定義和術(shù)語(7.12. 圖的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣、鄰接表)(7.2 )3. 圖的遍歷(7.3)(1) 兩種遍歷的定義(2) 遍歷的算法4. 最小生成樹(7.4.1 )(1) 無向圖的連通分量、生成樹、最小生成樹的概念(2) 最小生成樹的生成掌握兩種算法的思想及構(gòu)成最小生成樹的過程5. 拓樸排序和關(guān)鍵路徑(7.4.2)(1) 有向無環(huán)圖的概念(2) 拓樸排序的概念：(3) aov網(wǎng)的定義(4) 理解拓樸排序算法思想，會(huì)求拓?fù)湫蛄?5) aoe網(wǎng)的定義(6) 關(guān)鍵路徑的概念、算法思想，會(huì)求關(guān)鍵路徑。

7、6. 最短路徑(7.4.3)(1) 最短路徑的概念(2) 理解最短路徑的算法(迪杰斯特拉算法、弗洛伊德算法)的思想(3) 能夠描術(shù)迪杰斯特拉算法的求解過程，從而求出最短路徑第九章 查找1. 查找的概念、平均查找長(zhǎng)度的概念2. 靜態(tài)查找(8.2 )(1) 順序查找、折半查找、索引順序表(分塊)查找的方法，重點(diǎn)掌握順序查 找和折半查找的算法。(2) 判定樹概念和性質(zhì)，會(huì)通過判定樹求得折半查找的平均查找長(zhǎng)度3. 動(dòng)態(tài)查找(8.3 )(1) 二叉排序樹的定義，性質(zhì)：中序遍歷有序(2) 二叉排序樹的查找(3) 二叉排序樹的插入、刪除(保持二叉排序樹的特點(diǎn))(4) 平衡二叉樹的概念、生成過程。(5) b-樹的概念和查找4. 哈希表(8.4)(1) 哈希表的概念(2) 哈希函數(shù)的構(gòu)造方法(直接定址法、除留取余法)(3) 解決沖突的方法(開放地址法、鏈地址法)(4) 會(huì)構(gòu)造哈希表，計(jì)算查找成功和查找不成功的平均查找長(zhǎng)度。5. 對(duì)于各種查找方法，要掌握其各自的特點(diǎn)、時(shí)間復(fù)雜度的分析(用平均查找 長(zhǎng)度asl來度量)。第十章排序1. 掌握如下排序方法的算法思想插入排序、希爾排序、冒泡排序、快速排序、堆排序、歸并排序和基數(shù)排序。2