數據結構與算法——C語言版

內容簡介

本書以C語言為基礎講解數據結構與算法。全書共11章，全面介紹了開發中常用的數據結構，包括線性表（順序表、單鍊表、雙鍊表、循環鍊表）、棧和佇列、串、數組和廣義表、樹、圖，詳細講解了各種愉跨厚數據結構的實現及常用操作，以及多種查找算法、內部排序算法的原理和實現，簡要介紹了檔案的相關知識，最後通過一個綜合項目對書中介紹的知主多主識進行整合套用，幫助讀者了解實際項目開發的流程。

本書對每種數據結構和算法的剖析都遵循由淺入深的原則，並配以實用的案例和圖示，適合具有C語言基礎的數據結構初學者，實用性強。本書可作為高等院校計算機相關專業數據結構課程的教學參考用書，也可作為培訓教材和自學者的學習用書。

圖書目錄

第1章數據結構與算法概述1

1.1數據結構1

1.1.1什麼是數據結構1

1.1.2數據結構的分類2

1.2抽象數據類型6

1.3算法7

1.3.1什麼是算法7

1.3.2算法的特性9

1.3.3算法的複雜度10

1.3.4算法與數據結構12

1.4小結12

【思考題】12

第2章線性表13

2.1什麼是線性表13

2.2線性表的順序臘良局存儲（順序表）14

2.2.1順序存儲的原理14

2.2.2順序存儲的實現15

2.3線性表的鏈式存儲（鍊表）23

2.3.1鏈式存儲的原理23

2.3.2鏈式存儲的實現24

2.4雙鍊表31

2.4.1什麼是雙鍊表32

2.4.2雙鍊表的實現32

2.5循環鍊表39

2.5.1什麼是循環鍊表39

2.5.2循環鍊表的實現40

2.5.3約瑟夫環43

2.6本章小結48

【思考題】49數據結構與算法——C語言版第3章棧和佇列50

3.1什麼是棧50

3.2棧的實現51

3.2.1棧的順序存儲實現51

3.2.2棧的鏈式存儲實現56

3.3棧的套用60

3.3.1用棧實現四則運算60

3.3.2棧的遞歸套用72

3.4什麼是佇列75

3.5佇列的實現75

3.5.1順序佇列的實現76

3.5.2鏈式佇列的實現80

3.5.3循環佇列84

3.6本章小結86

【思考題】87

第4章串88

4.1什麼是串88

4.2串的存儲結構89

4.2.1串的順序存儲89

4.2.2串的鏈式存儲97

4.3串的模式匹配算法98

4.3.1樸素的模式匹配98

4.3.2KMP算法（無回溯的模式匹配）101

4.4本章小結105

【思考題】105

第5章數組和廣義表106

5.1數組106

5.2矩陣的壓縮存儲109

5.2.1特殊矩陣109

5.2.2稀疏矩陣的定義110

5.2.3稀疏矩陣的創建112

5.2.4稀疏矩陣的轉置114

5.2.5稀疏矩陣的十字鍊表表示118

5.3廣義表123

5.3.1廣義表的定義123

5.3.2廣義表的存儲結構124

5.3.3廣義表的遞歸運算125

5.4本章小結132

【思考題】132

第6章紙拒狼熱樹133

6.1樹133

6.1.1什麼是樹133

6.1.2樹的表示法135

6.2二叉樹138

6.2.1什麼是二叉樹戒符境承138

6.2.2二叉樹的分類138

6.2.3二多淚棕叉樹的性質139

6.3二叉樹的存儲結構141

6.3.1二叉樹的順序存儲141

6.3.2二叉樹的鏈式存儲143

6.4二叉樹的淋雄遍歷147

6.4.1二叉樹的遍歷147

6.4.2遞歸思想的套用151

6.5二叉樹的非遞歸遍歷154

6.6二叉樹與樹、森林之間的轉換162

6.6.1二叉樹與樹之間的轉換162

6.6.2二叉樹與森林之間的轉換162

6.7二叉樹的創建164

6.7.1中序和先序創建二叉樹164

6.7.2#號法創建樹166

6.8線索二叉樹169

6.8.1什麼是線索二叉樹169

6.8.2二叉樹的線索化171

6.8.3線索化二叉樹的遍歷175

6.9赫夫曼樹177

6.9.1什麼是赫夫曼樹177

6.9.2赫夫曼樹的構造178

6.9.3赫夫曼編碼179

6.10本章小結180

【思考題】181

第7章圖182

7.1圖的基本概念182

7.1.1圖的定義與基本術語182

7.1.2圖的基本操作185

7.2圖的存儲結構186

7.2.1圖的鄰接矩陣存儲187

7.2.2圖的鄰接表存儲189

7.2.3圖的十字鍊表存儲192

7.2.4圖的鄰接多重表存儲194

7.3圖的遍歷196

7.3.1深度優先遍歷196

7.3.2廣度優先遍歷198

7.4最小生成樹201

7.4.1什麼是最小生成樹201

7.4.2Prim算法203

7.4.3Kruskal算法207

7.5最短路徑210

7.5.1從源點到其他頂點的最短路徑211

7.5.2每對頂點的最短路徑216

7.6拓撲排序219

7.7關鍵路徑224

7.8本章小結229

【思考題】230

第8章查找231

8.1查找概述231

8.2順序表的查找232

8.3有序表的查找233

8.3.1折半查找233

8.3.2插值查找235

8.3.3斐波納契查找235

8.4索引順序查找239

8.5二叉排序樹241

8.6平衡二叉樹246

8.6.1平衡二叉樹的概念246

8.6.2平衡二叉樹的插入247

8.6.3平衡二叉樹的刪除252

8.7B樹254

8.7.1B樹的概念254

8.7.2B樹的插入256

8.7.3B樹的刪除258

8.8鍵樹261

8.9哈希表265

8.9.1什麼是哈希表265

8.9.2哈希函式的構造方法267

8.9.3處理哈希衝突269

8.9.4哈希表的查找實現273

8.10本章小結275

【思考題】275

第9章內部排序276

9.1排序的概念與分類276

9.2交換排序278

9.2.1冒泡排序279

9.2.2快速排序283

9.3插入排序286

9.3.1直接插入排序286

9.3.2折半插入排序289

9.3.3希爾排序290

9.4選擇排序294

9.4.1簡單選擇排序294

9.4.2樹形選擇排序296

9.4.3堆排序298

9.5歸併排序303

9.6基數排序307

9.6.1基數排序基礎307

9.6.2鏈式基數排序310

9.7內部排序方法比較314

9.8磁碟排序315

9.8.1外部存儲設備315

9.8.2磁碟排序分析317

9.8.3置換選擇排序319

9.8.4多路平衡歸併321

9.8.5最佳歸併樹324

9.9本章小結325

【思考題】326

第10章檔案327

10.1檔案概述327

10.2順序檔案和索引檔案328

10.2.1順序檔案328

10.2.2索引檔案329

10.3ISAM檔案和VSAM檔案331

10.3.1ISAM檔案331

10.3.2VSAM檔案334

10.4哈希檔案336

10.5多關鍵字檔案337

10.5.1多重表檔案337

10.5.2倒排檔案338

10.6本章小結339

【思考題】339

第11章綜合項目——貪吃蛇340

11.1項目分析340

11.1.1模組設計340

11.1.2模組描述342

11.1.3項目分析345

11.2項目實現346

11.2.1創建項目346

11.2.2項目設計346

11.2.3項目實現349

11.2.4主函式實現360

11.2.5效果展示364

11.3項目心得365

【思考題】366

數據結構與算法——C語言版

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條