第一篇學輔導篇

第1章緒論2

1.1由根及脈，本章導學2

1.1.1數據結構2

1.1.2算法3

1.2撥雲見日，謎點解析3

1.2.素3

1.2.2數據結構、邏輯結構與物理結構3

1.2.3順序存儲與鏈式存儲4

1.2.4數據結構的設計與選擇4

1.2.5程序與算法4

1.2.6偽碼與類語言算法描述5

1.2.7數據結構與抽像數據類型5

1.2.8數據結構與程序設計5

1.2.9算法的時間復雜度分析6

1.3積微成著，要點集錦6

1.4啟智明理，題解答7

1.4.1主教材題解答7

1.4.2自測題及解答14第2章線性表20

2.1由根及脈，本章導學20

2.1.1線性表的定義20

2.1.2順序表21

2.1.3單鏈表22數據結構原理與應用學及實驗指導目錄

2.1.4線性表的其他存儲形式24

2.2撥雲見日，謎點解析25

2.2.1線性表、順序表、單鏈表25

2.2.2一維數組與順序表25

2.2.3順序表的性25

2.2.4單鏈表的性26

2.2.5頭結點的作用26

2.2.6單鏈表遍歷中的計數28

2.2.7順序表遍歷結束條件29

2.2.8單鏈表遍歷結束條件30

2.2.9存儲結構的選擇32

2.2.10存儲結構與算法32

2.3積微成著，要點集錦33

2.4啟智明理，題解答34

2.4.1主教材題解答34

2.4.2自測題及解答42第3章棧和隊列49

3.1由根及脈，本章導學49

3.1.1棧49

3.1.2隊列51

3.2撥雲見日，謎點解析53

3.2.1線性表與棧53

3.2.2線性表與隊列53

3.2.3棧、順序棧和鏈棧53

3.2.4棧指針53

3.2.5隊列、順序隊列、鏈隊54

3.2.6隊頭、隊尾指針54

3.2.7“假溢出”及其相關問題55

3.2.8遞歸與非遞歸57

3.3積微成著，要點集錦58

3.4啟智明理，題解答59

3.4.1主教材題解答59

3.4.2自測題及解答66第4章數組和矩陣74

4.1由根及脈，本章導學74

4.1.1數組的順序存儲74

4.1.2殊矩陣的壓縮存儲74

4.1.3稀疏矩陣的壓縮存儲75

4.2撥雲見日，謎點解析75

4.2.1數組與線性表75

4.2.2數組與矩陣75

4.2.3多維數組存儲到一維數組中的位序計算75

4.2.4存儲位序與存儲地址76

4.2.5殊矩陣壓縮存儲與訪問77

4.2.6稀疏矩陣壓縮存儲與訪問78

4.3積微成著，要點集錦78

4.4啟智明理，題解答80

4.4.1主教材題解答80

4.4.2自測題及解答83第5章樹和二樹87

5.1脈絡梳理，本章導學87

5.1.1樹87

5.1.2森林88

5.1.3二樹88

5.1.4樹/森林與二樹的相互轉換90

5.2撥雲見日，謎點解析90

5.2.1樹與二樹90

5.2.2遍歷過程91

5.2.3二樹的先序、中序、後序遍歷遞歸作92

5.2.4二樹創建93

5.2.5二樹問題的遞歸分析94

5.2.6二樹的先序、中序、後序遍歷中結點訪問次序96

5.2.7先序、中序和後序遍歷非遞歸作中的入棧結點96

5.2.8線索的作用97

5.2.9哈夫曼樹的多樣性99

5.2.10二樹與前綴碼100

5.3積微成著，要點集錦101

5.4啟智明理，題解答103

5.4.1主教材題解答103

5.4.2自測題及解答113第6章圖123

6.1脈絡梳理，本章導學123

6.1.1基本概念123

6.1.2圖的實現124

6.1.3圖的應用126

6.2撥雲見日，謎點解析126

6.2.1圖的存儲設計126

6.2.2鄰接矩陣的秘密127

6.2.3鄰接表的秘密128

6.2.4深度先遍歷129

6.2.5廣度先遍歷130

6.2.6Prim算法與Kruskal算法131

6.2.7Dijkstra算法、Floyd算法中求解問題域131

6.2.8Prim算法、Dijkstra算法、Floyd算法中的距離數組132

6.2.9Dijkstra算法、Floyd算法中的路徑矩陣132

6.3積微成著，要點集錦133

6.4啟智明理，題解答135

6.4.1主教材題解答135

6.4.2自測題及解答147第7章查找157

7.1由根及脈，本章導學157

7.1.1基本概念157

7.1.2線性表查找158

7.1.3樹表查找158

7.1.4散列查找159

7.2撥雲見日，謎點解析159

7.2.1查找表與查找方法159

7.2.2折半查找判定樹159

7.2.3折半查找判定樹、二排序樹與平衡二樹161

7.2.4KMP算法對BF算法的改進161

7.2.5KMP的next［j］計算162

7.2.6衝突處理方法164

7.2.7衝突處理與散列查找方法165

7.2.8各種查找方法性能比較166

7.3登高望遠，要點集錦166

7.4啟智明理，題解答168

7.4.1主教材題解答168

7.4.2自測題及解答177第8章排序187

8.1由根及脈，本章導學187

8.1.1排序的基本概念187

8.1.2內排序技術188

8.1.3排序方法比較188

8.2撥雲見日，謎點解析188

8.2.1關於188

8.2.2排序算法的進189

8.2.3排序算法穩定性的可變性190

8.2.4二排序樹與堆191

8.2.5存儲結構與排序方法191

8.2.6鏈表上的排序191

8.3積微成著，要點集錦194

8.4啟智明理，題解答195

8.4.1主教材題解答195

8.4.2自測題及解答201

第二篇實踐指導篇

第1章緒論212

1.1上機練題212

1.1.1常見函數的增長趨勢212

1.1.2高效計算層和213

1.1.3溢出及函數出方式213第2章線性表216

2.1上機練題216

2.1.1用順序表基本作求解A=A∩B216

2.1.2用鏈表基本作求解A=A∩B217

2.1.3有序表問題218

2.2實驗源碼220

2.2.1集合運算220

2.2多項式求導223

2.2.3有序表合並225

2.2.4循環單鏈表225

2.2.5約瑟夫問題229第3章棧和隊列231

3.1上機練題231

3.1.1共用存儲區的兩個棧231

3.1.2單指針鏈隊233

3.2實驗源碼233

3.2.1數制轉換233

3.2.2算術表達式正確性判斷234

3.2.3棧的逆置236

3.2.4求任意長兩個大整數的和237

3.2.5單指針鏈隊問題239

3.2.6楊輝三角形問題242第4章數組和矩陣244

4.1上機練題244

4.1.1求馬鞍點244

4.1.2“蛇形”矩陣245

4.2實驗源碼246

4.2.1兩個對稱矩陣的和與積246

4.2.2“蛇形”矩陣248

4.2.3魔方問題248第5章樹和二樹250

5.1上機練題250

5.1.1二樹的若干基本作250

5.1.2二樹的遍歷250

5.2實驗源碼250

5.2.1二樹的葉結點計數251

5.2.2復制二樹252

5.2.3求二樹的寬度252

5.2.4求先/中/後序遍歷序列的、素254

5.2.5葉結點路徑問題256第6章圖258

6.1上機練題258

6.1.1鄰接矩陣上的遍歷作258

6.1.2鄰接表上的遍歷作261

6.2實驗源碼264

6.2.1存儲結構轉換問題264

6.2.2有向圖的路徑問題266

6.2.3無向圖的路徑問題268

6.2.4俱樂選址問題271

6.2.5物流短路徑問題272第7章查找275

7.1上機練題275

7.1.1稀疏矩陣的散列存儲275

7.1.2二排序樹結點刪除278

7.2實驗源碼279

7.2.1順序查找與折半查找279

7.2.2用二排序樹實現字符統計280

7.2.3拉鏈法處理衝突的散列表282

7.2.4開放定址法處理衝突的散列表285第8章排序289

8.1上機練題289

8.1.1序列重排289

8.1.2排序方法性能比較290

8.2實驗源碼291

8.2.1單鏈表上的直接入排序291

8.2.2單鏈表上的簡單選擇排序292

8.2.3雙向冒泡排序293

8.2.4序列重排293

8.2.5堆判斷293