2021版天勤計(jì)算機(jī)考研高分筆記系列 數(shù)據(jù)結(jié)構(gòu)高分筆記（第9版）

序

輔導(dǎo)專(zhuān)欄簡(jiǎn)介

前言

第1章  緒論 1

本章概略 1

1.1  針對(duì)考研數(shù)據(jù)結(jié)構(gòu)的代碼書(shū)寫(xiě)規(guī)范以及C與C++語(yǔ)言基礎(chǔ) 1

1.1.1  考研綜合應(yīng)用題中算法設(shè)計(jì)部分的代碼書(shū)寫(xiě)規(guī)范 1

1.1.2  考研中的C與C++語(yǔ)言基礎(chǔ) 3

1.2  算法的時(shí)間復(fù)雜度與空間復(fù)雜度分析基礎(chǔ) 12

1.2.1  考研中的算法時(shí)間復(fù)雜度分析 12

1.2.2  例題選講 12

1.2.3  考研中的算法空間復(fù)雜度分析 14

1.3  數(shù)據(jù)結(jié)構(gòu)和算法的基本概念 14

1.3.1  數(shù)據(jù)結(jié)構(gòu)的基本概念 14

1.3.2  算法的基本概念 15

習(xí)題 16

習(xí)題答案 17

第2章  線(xiàn)性表 20

大綱要求 20

考點(diǎn)與要點(diǎn)分析 20

核心考點(diǎn) 20

基礎(chǔ)要點(diǎn) 20

知識(shí)點(diǎn)講解 20

2.1  線(xiàn)性表的基本概念與實(shí)現(xiàn) 20

2.2  線(xiàn)性表的結(jié)構(gòu)體定義和基本操作 24

2.2.1  線(xiàn)性表的結(jié)構(gòu)體定義 24

2.2.2  順序表的操作 26

2.2.3  單鏈表的操作 29

2.2.4  雙鏈表的操作 33

2.2.5  循環(huán)鏈表的操作 35

▲真題仿造 35

真題仿造答案與解析 36

習(xí)題+真題精選 37

習(xí)題答案+真題精選答案 41

第3章  棧和隊(duì)列 55

大綱要求 55

考點(diǎn)與要點(diǎn)分析 55

核心考點(diǎn) 55

基礎(chǔ)要點(diǎn) 55

知識(shí)點(diǎn)講解 55

3.1  棧和隊(duì)列的基本概念 55

3.1.1  棧的基本概念 55

3.1.2  隊(duì)列的基本概念 56

3.2  棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)、算法與應(yīng)用 56

3.2.1  本章所涉及的結(jié)構(gòu)體定義 56

3.2.2  順序棧 57

3.2.3  鏈棧 59

3.2.4  棧的應(yīng)用 60

3.2.5  順序隊(duì) 64

3.2.6  鏈隊(duì) 66

3.3  抽象數(shù)據(jù)類(lèi)型 69

▲真題仿造 71

真題仿造答案與解析 71

習(xí)題+真題精選 74

習(xí)題答案+真題精選答案 79

第4章  串 91

知識(shí)點(diǎn)講解 91

4.1  串?dāng)?shù)據(jù)類(lèi)型的定義 91

4.1.1  串的定義 91

4.1.2  串的存儲(chǔ)結(jié)構(gòu) 91

4.1.3  串的基本操作 92

4.2  串的模式匹配算法 95

4.2.1  簡(jiǎn)單模式匹配算法 95

4.2.2  KMP算法 96

4.2.3  KMP算法的改進(jìn) 99

習(xí)題 102

習(xí)題答案 103

第5章  數(shù)組、矩陣與廣義表 113

知識(shí)點(diǎn)講解 113

5.1  數(shù)組 113

5.2  矩陣的壓縮存儲(chǔ) 114

5.2.1  矩陣 114

5.2.2  特殊矩陣和稀疏矩陣 115

5.3  廣義表 121

習(xí)題 122

習(xí)題答案 123

第6章  樹(shù)與二叉樹(shù) 132

大綱要求 132

考點(diǎn)與要點(diǎn)分析 132

核心考點(diǎn) 132

基礎(chǔ)要點(diǎn) 132

知識(shí)點(diǎn)講解 132

6.1  樹(shù)的基本概念 132

6.1.1  樹(shù)的定義 132

6.1.2  樹(shù)的基本術(shù)語(yǔ) 132

6.1.3  樹(shù)的存儲(chǔ)結(jié)構(gòu) 133

6.2  二叉樹(shù) 134

6.2.1  二叉樹(shù)的定義 134

6.2.2  二叉樹(shù)的主要性質(zhì) 135

6.2.3  二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 137

6.2.4  二叉樹(shù)的遍歷算法 137

6.2.5  二叉樹(shù)遍歷算法的改進(jìn) 146

6.3  樹(shù)和森林與二叉樹(shù)的互相轉(zhuǎn)換 155

6.3.1  樹(shù)轉(zhuǎn)換為二叉樹(shù) 155

6.3.2  二叉樹(shù)轉(zhuǎn)換為樹(shù) 156

6.3.3  森林轉(zhuǎn)換為二叉樹(shù) 156

6.3.4  二叉樹(shù)轉(zhuǎn)換為森林 157

6.3.5  樹(shù)和森林的遍歷 157

6.4  樹(shù)與二叉樹(shù)的應(yīng)用 158

6.4.1  二叉排序樹(shù)與平衡二叉樹(shù) 158

6.4.2  赫夫曼樹(shù)和赫夫曼編碼 159

▲真題仿造 162

真題仿造答案與解析 162

習(xí)題+真題精選 163

習(xí)題答案+真題精選答案 168

第7章  圖 183

大綱要求 183

考點(diǎn)與要點(diǎn)分析 183

核心考點(diǎn) 183

基礎(chǔ)要點(diǎn) 183

知識(shí)點(diǎn)講解 183

7.1  圖的基本概念 183

7.2  圖的存儲(chǔ)結(jié)構(gòu) 184

7.2.1  鄰接矩陣 185

7.2.2  鄰接表 186

7.2.3  鄰接多重表 187

7.3  圖的遍歷算法操作 188

7.3.1  深度優(yōu)先搜索遍歷 188

7.3.2  廣度優(yōu)先搜索遍歷 189

7.3.3  例題選講 190

7.4  最?。ù鷥r(jià)）生成樹(shù) 193

7.4.1  普里姆算法和克魯斯卡爾算法 193

7.4.2  例題選講 197

7.5  最短路徑 198

7.5.1  迪杰斯特拉算法 198

7.5.2  弗洛伊德算法 204

7.6  拓?fù)渑判?207

7.6.1  AOV網(wǎng) 207

7.6.2  拓?fù)渑判蚝诵乃惴?207

7.6.3  例題選講 209

7.7  關(guān)鍵路徑 209

7.7.1  AOE網(wǎng) 209

7.7.2  關(guān)鍵路徑核心算法 210

▲真題仿造 213

真題仿造答案與解析 213

習(xí)題+真題精選 215

習(xí)題答案+真題精選答案 221

第8章  排序 234

大綱要求 234

考點(diǎn)與要點(diǎn)分析 234

核心考點(diǎn) 234

基礎(chǔ)要點(diǎn) 234

知識(shí)點(diǎn)講解 235

8.1  排序的基本概念 235

......