數據結構與經典算法

《數據結構與經典算法》是2015年5月15日出版的圖書，作者是李千目、殷新春、李濤。

基本介紹

• 書名：數據結構與經典算法
• 作者：李千目、殷新春、李濤
• ISBN：9787302400837
• 定價：49.00
• 出版社：清華大學出版社
• 出版時間：2015年5月15日
• 裝幀：平裝

圖書簡介

本書經過國內著名高校的培優班、精英班的實際教學檢驗，由淺入深，循序漸進，通過案例來講解理論，以淺顯易懂的文字與圖表對各種數據結構和算法的設計進行分析，對問題的解決方法做了詳盡的剖析。

本書注重原理和思想，儘量簡化模型，強調其背後的基本思想，以基礎理論實驗經典題庫為主線進行編寫，輔之以相應的類C語言代碼，從而增進讀者對數據結構的理解與掌握。

全書共分為12章，內容包括基礎知識、線性存儲結構、棧、佇列、串、數組與廣義表、樹型結構、圖狀結構、查找、內部排序、經典算法、數據分析與挖掘。其中，第11章是經典算法解析，第12章簡要地介紹了數據挖掘的知識，本書安排了大量的實驗和練習方便讀者學習和使用。

目錄

第1章基礎知識/1

1.1數據結構研究什麼/1

1.2基本概念和有關術語/3

1.3數據類型與抽象數據類型/4

1.3.1數據類型/4

1.3.2抽象數據類型/4

1.4算法描述與算法分析/6

1.4.1算法的描述/6

1.4.2算法的時間複雜度分析/7

1.4.3算法的空間複雜度分析/8

1.5小結/8

1.6經典題庫/9

1.6.1要點提醒/9

1.6.2經典剖析/9

1.7練習/11第2章線性存儲結構/13

2.1線性表的定義及基本操作/13

2.1.1線性表的基本概念/13

2.1.2線性表的抽象數據類型/14

2.2線性表順序存儲結構的定義/15

2.2.1線性表順序存儲結構的定義/15

2.2.2順序表的基本操作及實現/16

2.2.3順序表的套用/18

2.3線性表鏈式存儲結構與實現/20

2.3.1線性表鏈式存儲結構/21

2.3.2單鍊表及其基本操作/21

2.3.3循環鍊表的基本操作及實現/29

2.3.4雙鍊表的基本操作及實現/33

2.3.5循環雙鍊表/37

2.4實驗/38

實驗一：順序表的操作/38實驗二：單鍊表連線/40

實驗三：循環鍊表連線/43

實驗四：循環雙鍊表操作/47

2.5小結/52

2.6經典題庫/52

2.6.1要點提醒/52

2.6.2經典剖析/53

2.7練習/61第3章棧/65

3.1棧/65

3.1.1棧的基本概念/65

3.1.2棧的抽象數據類型/65

3.1.3棧的順序存儲結構及實現/66

3.1.4棧的鏈式存儲結構與實現/70

3.2棧的套用/74

3.2.1表達式求值/74

3.2.2數制轉換/76

3.2.3括弧匹配檢驗/77

3.2.4棧與遞歸的實現/78

3.3實驗/79

實驗：利用棧尋找迷宮路徑/79

3.4小結/82

3.5經典題庫/82

3.5.1要點提醒/82

3.5.2經典剖析/83

3.6練習/86第4章佇列/90

4.1佇列/90

4.1.1什麼是佇列/90

4.1.2佇列的抽象數據類型/90

4.1.3佇列的順序存儲結構與實現/91

4.1.4佇列的鏈式存儲結構與實現/97

4.2佇列的套用/101

4.3實驗/105

實驗：利用佇列模擬病人看病/105

4.4小結/109

4.5經典題庫/109

4.5.1要點提醒/109

4.5.2經典剖析/109

4.6練習/112第5章串/116

5.1串的定義/116

5.1.1串的定義/116

5.1.2串的抽象數據類型/116

5.2串的存儲結構與實現/118

5.2.1串的順序存儲結構與實現/118

5.2.2串的堆存儲結構與實現/121

5.2.3串的塊鏈存儲結構與實現/122

5.3串的模式匹配算法/123

5.3.1簡單的模式匹配算法——BF算法/123

5.3.2改進的模式匹配算法——KMP

算法/125

5.4串的套用/127

5.5實驗/128

實驗一：顯示多位數數字字元/128

實驗二：塊鏈的基本操作/130

實驗三：統計串中最長的重複子串/135

5.6小結/137

5.7經典題庫/138

5.7.1要點提醒/138

5.7.2經典剖析/138

5.8練習/140第6章數組與廣義表/142

6.1數組的定義/142

6.1.1數組的概念與性質/142

6.1.2抽象數據類型/143

6.2數組相關結構的實現/143

6.2.1數組的順序存儲/143

6.2.2數組的基本操作實現/144

6.3矩陣的壓縮存儲探究/147

6.3.1特殊矩陣/147

6.3.2稀疏矩陣/149

6.4廣義表/153

6.4.1廣義表相關概念/153

6.4.2抽象數據類型/154

6.4.3廣義表存儲結構詳解/155

6.4.4廣義表的相關套用/156

6.5實驗/157

實驗一：矩陣乘法/157

實驗二：三元組實現兩個矩陣的乘法/160

實驗三：廣義表的基本運算/163

6.6小結/168

6.7經典題庫/169

6.7.1要點提醒/169

6.7.2經典剖析/169

6.8練習/172第7章樹型結構/175

7.1樹的基本概念和術語/175

7.1.1樹的基本概念/175

7.1.2基本術語/175

7.2二叉樹/176

7.2.1二叉樹的基本概念/176

7.2.2二叉樹性質的探究/178

7.2.3抽象數據類型/179

7.2.4存儲結構/181

7.3遍歷二叉樹的方法/185

7.3.1遍歷的定義/185

7.3.2遍歷算法探究/186

7.4線索二叉樹/189

7.5樹和森林/192

7.5.1樹的存儲結構/192

7.5.2二叉樹與森林/194

7.5.3樹和森林的遍歷探究/195

7.6哈夫曼樹/196

7.6.1哈夫曼樹的基本概念/196

7.6.2哈夫曼樹的構造算法/197

7.6.3哈夫曼樹和哈夫曼編碼/199

7.7實驗/201

實驗一:運算二叉樹/201

實驗二:統計二叉樹結點的個數/203

實驗三:統計二叉樹的寬度/205

實驗四:按層遍歷二叉樹/207

7.8小結/210

7.9經典題庫/210

7.9.1要點提醒/210

7.9.2經典剖析/210

7.10練習/217第8章圖狀結構/220

8.1圖的相關定義和術語/220

8.1.1圖的基本概念/220

8.1.2圖的基本術語/220

8.1.3抽象數據類型/222

8.2圖的存儲結構探究/223

8.2.1鄰接矩陣/223

8.2.2鄰接表/225

8.2.3十字鍊表/227

8.2.4多重鄰接表/228

8.3圖的遍歷/229

8.3.1深度優先遍歷/229

8.3.2廣度優先遍歷/230

8.4最小生成樹/231

8.4.1生成樹的概念/231

8.4.2最小生成樹/231

8.4.3Prim算法/235

8.5最短路徑探究/238

8.5.1單源點最短路徑問題分析/238

8.5.2所有頂點對應最短路徑問題分析/240

8.6拓撲排序探究/241

8.7關鍵路徑/244

8.8實驗/244

實驗一:遍歷算法/244

實驗二:Prim算法/248

8.9小結/253

8.10經典題庫/253

8.10.1要點提醒/253

8.10.2經典剖析/253

8.11練習/264第9章查找/269

9.1查找的基本概念/269

9.2靜態查找表/269

9.2.1順序表的查找/269

9.2.2有序表的查找/270

9.2.3索引順序表的查找/271

9.2.4靜態樹表的查找/273

9.3動態查找表/274

9.3.1二叉排序樹/274

9.3.2平衡二叉樹/276

9.3.3B-和B+樹/280

9.3.4鍵樹/288

9.4哈希表/289

9.4.1哈希表的概念/289

9.4.2哈希表的構造方法/289

9.4.3處理衝突的方法/290

9.4.4哈希表的查找及分析/293

9.5實驗/294

實驗一:二叉排序樹的查找/294

實驗二:哈希查找/298

9.6小結/300

9.7經典題庫/301

9.7.1要點提醒/301

9.7.2經典剖析/301

9.8練習/308第10章內部排序/310

10.1插入排序/310

10.1.1直接插入排序/310

10.1.2希爾排序/311

10.2交換排序/313

10.2.1冒泡排序/313

10.2.2快速排序/315

10.3選擇排序/316

10.3.1簡單選擇排序/316

10.3.2堆排序/317

10.4歸併排序/320

10.5基數排序/321

10.6各種內排序方法的比較/324

10.7實驗/325

實驗一:雙向冒泡排序/325

實驗二:數組歸併排序/328

實驗三:計數排序/331

實驗四:字元串排序/332

實驗五:最高位關鍵字排序MSD/335

10.8小結/338

10.9經典題庫/338

10.9.1要點提醒/338

10.9.2經典剖析/339

10.10練習/343第11章經典算法/345

11.1基礎算法/345

11.1.1河內之塔/345

11.1.2八皇后/346

11.1.3背包問題/348

11.2數、運算/352

11.2.1篩選求質數/352

11.2.2最大公因數、最低公倍數、因式

分解/353

11.2.3最大訪客數/356

11.3關於博弈/358

11.3.1洗撲克牌(亂數排列)/358

11.3.2Craps賭博遊戲/360

11.4集合問題/362

11.4.1格雷碼(GrayCode)/362

11.4.2m元素集合的n元子集/364

11.5矩陣/365

11.5.1稀疏矩陣存儲/365

11.5.2上三角、下三角、對稱矩陣存儲/367

11.5.3奇數魔方陣/369第12章數據分析與挖掘/371

12.1大數據時代的挖掘/371

12.1.1數據挖掘/371

12.1.2從數據挖掘套用的角度看大

數據/372

12.2挖掘技術發展和歷史/373

12.3十大挖掘算法簡介/374參考文獻/378