2021版天勤計算機考研高分筆記系列 數據結構高分筆記（第9版）

序

輔導專欄簡介

前言

第1章  緒論 1

本章概略 1

1.1  針對考研數據結構的代碼書寫規(guī)范以及C與C++語言基礎 1

1.1.1  考研綜合應用題中算法設計部分的代碼書寫規(guī)范 1

1.1.2  考研中的C與C++語言基礎 3

1.2  算法的時間復雜度與空間復雜度分析基礎 12

1.2.1  考研中的算法時間復雜度分析 12

1.2.2  例題選講 12

1.2.3  考研中的算法空間復雜度分析 14

1.3  數據結構和算法的基本概念 14

1.3.1  數據結構的基本概念 14

1.3.2  算法的基本概念 15

習題 16

習題答案 17

第2章  線性表 20

大綱要求 20

考點與要點分析 20

核心考點 20

基礎要點 20

知識點講解 20

2.1  線性表的基本概念與實現 20

2.2  線性表的結構體定義和基本操作 24

2.2.1  線性表的結構體定義 24

2.2.2  順序表的操作 26

2.2.3  單鏈表的操作 29

2.2.4  雙鏈表的操作 33

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

▲真題仿造 35

真題仿造答案與解析 36

習題+真題精選 37

習題答案+真題精選答案 41

第3章  棧和隊列 55

大綱要求 55

考點與要點分析 55

核心考點 55

基礎要點 55

知識點講解 55

3.1  棧和隊列的基本概念 55

3.1.1  棧的基本概念 55

3.1.2  隊列的基本概念 56

3.2  棧和隊列的存儲結構、算法與應用 56

3.2.1  本章所涉及的結構體定義 56

3.2.2  順序棧 57

3.2.3  鏈棧 59

3.2.4  棧的應用 60

3.2.5  順序隊 64

3.2.6  鏈隊 66

3.3  抽象數據類型 69

▲真題仿造 71

真題仿造答案與解析 71

習題+真題精選 74

習題答案+真題精選答案 79

第4章  串 91

知識點講解 91

4.1  串數據類型的定義 91

4.1.1  串的定義 91

4.1.2  串的存儲結構 91

4.1.3  串的基本操作 92

4.2  串的模式匹配算法 95

4.2.1  簡單模式匹配算法 95

4.2.2  KMP算法 96

4.2.3  KMP算法的改進 99

習題 102

習題答案 103

第5章  數組、矩陣與廣義表 113

知識點講解 113

5.1  數組 113

5.2  矩陣的壓縮存儲 114

5.2.1  矩陣 114

5.2.2  特殊矩陣和稀疏矩陣 115

5.3  廣義表 121

習題 122

習題答案 123

第6章  樹與二叉樹 132

大綱要求 132

考點與要點分析 132

核心考點 132

基礎要點 132

知識點講解 132

6.1  樹的基本概念 132

6.1.1  樹的定義 132

6.1.2  樹的基本術語 132

6.1.3  樹的存儲結構 133

6.2  二叉樹 134

6.2.1  二叉樹的定義 134

6.2.2  二叉樹的主要性質 135

6.2.3  二叉樹的存儲結構 137

6.2.4  二叉樹的遍歷算法 137

6.2.5  二叉樹遍歷算法的改進 146

6.3  樹和森林與二叉樹的互相轉換 155

6.3.1  樹轉換為二叉樹 155

6.3.2  二叉樹轉換為樹 156

6.3.3  森林轉換為二叉樹 156

6.3.4  二叉樹轉換為森林 157

6.3.5  樹和森林的遍歷 157

6.4  樹與二叉樹的應用 158

6.4.1  二叉排序樹與平衡二叉樹 158

6.4.2  赫夫曼樹和赫夫曼編碼 159

▲真題仿造 162

真題仿造答案與解析 162

習題+真題精選 163

習題答案+真題精選答案 168

第7章  圖 183

大綱要求 183

考點與要點分析 183

核心考點 183

基礎要點 183

知識點講解 183

7.1  圖的基本概念 183

7.2  圖的存儲結構 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）生成樹 193

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

7.4.2  例題選講 197

7.5  最短路徑 198

7.5.1  迪杰斯特拉算法 198

7.5.2  弗洛伊德算法 204

7.6  拓撲排序 207

7.6.1  AOV網 207

7.6.2  拓撲排序核心算法 207

7.6.3  例題選講 209

7.7  關鍵路徑 209

7.7.1  AOE網 209

7.7.2  關鍵路徑核心算法 210

▲真題仿造 213

真題仿造答案與解析 213

習題+真題精選 215

習題答案+真題精選答案 221

第8章  排序 234

大綱要求 234

考點與要點分析 234

核心考點 234

基礎要點 234

知識點講解 235

8.1  排序的基本概念 235

......