數據結構與算法：理論與實踐

《數據結構與算法：理論與實踐》是2015年1月電子工業出版社出版的圖書，作者是唐培和、徐奕奕。

基本介紹

• 書名：數據結構與算法：理論與實踐
• 作者：唐培和、徐奕奕
• ISBN：9787121244674
• 類別：數據與算法基本理論
• 頁數：416
• 定價：52.00
• 出版社：電子工業出版社
• 出版時間：2015-01
• 開本：16開
• 千字數：700

內容簡介

本書以數據的邏輯結構為線索，介紹數據結構及其建立在數據結構之上的操作和算法，內容涉及數據結構與算法的基本概念、順序存儲結構的線性表、鏈式存儲結構的線性表、串、數組、特殊矩陣與廣義表、樹與二叉樹、圖及其套用、查找與搜尋引擎、排序等。 本書既強調“算法”與“數據結構”之間緊密的依賴關係，也注重算法描述的簡潔與幹練；既有完整的理論體系，也有很好的套用案例。為了增強可理解性，本書案例與生活實踐相聯繫。 本書以知識單元為基本構件，既可拆卸也可重組，內容豐富，表述詳盡，可讀性強，適合不同類型的本科院校按照不同的培養規格組織教學。

目錄

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

1.1 引言 1

1.1.1 《數據結構與算法》課程到底研究什麼 1

1.1.2 《數據結構與算法》課程介紹 1

1.1.3 為什麼要學習《數據結構與算法》課程 2

1.2 基本概念和術語 3

1.2.1 數據 3

1.2.2 數據項 3

1.2.3 數據元素 4

1.2.4 數據對象 4

1.2.5 數據結構 4

1.2.6 數據結構的形式化描述 6

1.2.7 數據的邏輯結構、存儲結構與物理結構 7

1.2.8 數據結構實例 7

1.3 算法 9

1.3.1 什麼是算法 9

1.3.2 算法的性質 11

1.3.3 算法和程式 12

1.4 算法的表示（描述） 14

1.4.1 自然語言 14

1.4.2 計算機語言 15

1.4.3 圖形化工具 16

1.4.4 偽代碼 17

1.5 算法設計的準則 19

1.5.1 正確性 19

1.5.2 可讀性 20

1.5.3 健壯性 20

1.5.4 效率 21

1.6 算法效率分析 24

1.6.1 事後統計的方法 25

1.6.2 事前分析估算的方法 25

1.6.3 算法的空間複雜度 28

1.7 抽象數據類型 30

閱讀材料 32

習題1 35

第2章 順序存儲結構的線性表 39

2.1 基本概念和操作 39

2.1.1 什麼是線性表 39

2.1.2 線性表的邏輯結構 40

2.1.3 線性表的基本操作 40

2.1.4 線性表的順序存儲結構 41

2.1.5 線性表的插入與刪除操作（算法） 42

2.1.6 順序表套用舉例 45

2.2 堆疊 47

2.2.1 堆疊的定義 47

2.2.2 棧的順序存儲結構與操作（算法） 48

2.2.3 堆疊在算法設計中的套用 51

2.3 佇列 63

2.3.1 佇列的定義 64

2.3.2 佇列的順序存儲結構與操作（算法） 64

2.3.3 循環佇列 66

2.3.4 佇列套用舉例 68

2.4 集合及其運算 71

2.4.1 集合的定義 71

2.4.2 集合運算 72

2.4.3 集合的順序存儲結構和操作實現 72

小結 75

習題2 75

第3章 鏈式存儲結構的線性表 79

3.1 什麼是鏈式存儲結構的線性表 79

3.2 線性鍊表的操作（算法） 82

3.2.1 線性鍊表的構造 83

3.2.2 求表長 86

3.2.3 查找操作 86

3.2.4 線性鍊表的插入 87

3.2.5 線性鍊表的刪除 89

3.3 棧的鏈式存儲結構 90

3.4 佇列的鏈式存儲結構 92

3.5 循環鍊表 93

3.6 雙向鍊表 94

3.7 靜態鍊表 95

3.8 鍊表套用 97

3.9 一元多項式的存儲和相加 100

3.10 集合的鏈式存儲結構與操作 103

3.11 順序表和鍊表的比較 106

習題3 107

第4章 串 110

4.1 基本概念 111

4.2 串的存儲結構 112

4.2.1 順序存儲結構 112

4.2.2 鏈式存儲結構 113

4.3 串的基本操作 113

4.3.1 串複製 114

4.3.2 求字元串的長度 115

4.3.3 字元串連線 115

4.3.4 取子串 115

4.3.5 判斷兩個字元串是否相等 116

4.3.6 插入字元串 117

4.3.7 刪除子串 117

4.3.8 字元串清空 118

4.3.9 判斷字元串是否為空 118

4.3.10 字元串比較 118

4.4 串的模式匹配算法 119

4.4.1 模式匹配及其BF算法 119

4.4.2 模式匹配的一種改進算法——KMP算法 120

4.4.3 其他模式匹配算法 124

4.5 串操作套用舉例 132

習題4 133

第5章 數組、特殊矩陣與廣義表 136

5.1 數組的定義和運算 136

5.1.1 數組的基本概念 136

5.1.2 數組的特點 137

5.2 數組的順序存儲結構 137

5.2.1 一維數組 137

5.2.2 二維數組 138

5.2.3 三維數組 138

5.2.4 n維數組 139

5.3 特殊矩陣的壓縮存儲與處理 141

5.3.1 基本原則 141

5.3.2 對稱矩陣的壓縮存儲 141

5.3.3 三角矩陣的壓縮存儲 142

5.3.4 對角矩陣（帶狀矩陣）的壓縮存儲 143

5.4 稀疏矩陣 144

5.4.1 稀疏矩陣的三元組表存儲 145

5.4.2 稀疏矩陣的轉置 145

5.4.3 稀疏矩陣的快速轉置算法 147

5.5.4 稀疏矩陣的乘積 148

5.4.5 稀疏矩陣的十字鍊表存儲 151

5.5 廣義表 155

5.5.1 廣義表的定義 155

5.5.2 廣義表的特性 156

5.5.3 廣義表的基本操作 156

5.5.4 廣義表的存儲 157

5.5.5 廣義表的基本操作 159

習題5 162

第6章 樹與二叉樹 166

6.1 基本概念 166

6.1.1 什麼是樹 166

6.1.2 基本概念和術語 167

6.1.3 樹的表示方法 167

6.1.4 樹的基本操作 168

6.1.5 樹的存儲結構 168

6.2 二叉樹 173

6.2.1 二叉樹的定義 173

6.2.2 二叉樹的基本形態 173

6.2.3 兩種特殊的二叉樹 174

6.2.4 二叉樹具有的重要性質 175

6.2.5 二叉樹的存儲結構 176

6.2.6 二叉樹的基本操作 179

6.3 二叉樹的遍歷 179

6.3.1 二叉樹的遍歷 179

6.3.2 先序遍歷算法 180

6.3.3 中序遍歷 181

6.3.4 後序遍歷 182

6.3.5 按層次順序遍歷二叉樹 183

6.3.6 遍歷算法的套用 184

6.4 二叉樹其他運算 185

6.4.1 建造二叉樹算法 185

6.4.2 求二叉樹高度（深度） 186

6.4.3 求二叉樹寬度 186

6.4.4 二叉樹查找 187

6.4.5 輸出一棵二叉樹 188

6.4.6 清除一棵二叉樹 188

6.5 線索二叉樹 189

6.5.1 建立線索樹 189

6.5.2 檢索結點 191

6.5.3 線上索二叉樹上插入一個結點 192

6.6 樹與森林 193

6.6.1 樹與二叉樹的轉換 193

6.6.2 森林與二叉樹的轉換 194

6.6.3 樹和森林的遍歷 194

6.7 樹的套用 197

6.7.1 判定樹 197

6.7.2 集合的表示 198

6.7.3 關係等價求等價類問題 199

6.8 二叉排序樹 200

6.8.1 二叉排序樹的定義 200

6.8.2 二叉排序樹的構造 201

6.8.3 二叉排序樹的查找 203

6.8.4 二叉排序樹的更新 205

6.8.5 二叉排序樹的刪除 205

6.9 哈夫曼樹及其套用 207

6.9.1 基本概念 207

6.9.2 哈夫曼樹的構造 208

6.9.3 哈夫曼編碼 210

6.9.4 最佳判定過程 211

6.10 平衡二叉樹 212

6.10.1 平衡二叉樹的引入 212

6.10.2 平衡二叉樹的定義 212

6.10.3 最小不平衡二叉樹 213

6.10.4 不平衡二叉樹的調整方法 214

6.10.5 建立平衡二叉樹舉例 218

6.10.6 平衡二叉樹與二叉排序樹比較 219

習題6 220

第7章 圖及其套用 223

7.1 基本概念和術語 225

7.1.1 圖的定義 225

7.1.2 完全圖、稠密圖、稀疏圖 226

7.1.3 頂點的度 227

7.1.4 子圖 227

7.1.5 路徑和迴路 227

7.1.6 連通和連通分量 227

7.1.7 強連通圖和強連通分量 227

7.1.8 權和網 228

7.2 圖的存儲結構 229

7.2.1 鄰接矩陣 229

7.2.2 鄰接表 231

7.2.3 十字鍊表 234

7.2.4 鄰接多重表 236

7.2.5 圖的邊集數組 237

7.3 圖的遍歷 237

7.3.1 深度優先搜尋 237

7.3.2 廣度優先搜尋 239

7.3.3 搜尋算法在搜尋引擎中的套用 242

7.4 圖的連通性 243

7.4.1 無向圖的連通性 243

7.4.2 有向圖的連通性 244

7.4.3 生成樹和生成森林 245

7.4.4 關結點和重連通分量 245

7.5 最小生成樹 248

7.5.1 什麼是生成樹 248

7.5.2 構造最小生成樹的普里姆（Prim）算法 248

7.5.3 構造最小生成樹的Kruskal算法 252

7.6 最短路徑 255

7.6.1 求某一個源點到其他頂點的最短路徑 256

7.6.2 Bellman-Ford算法 259

7.6.3 每對頂點之間的最短路徑 262

7.7 有向無環圖及其套用 267

7.7.1 有向無環圖的概念 267

7.7.2 AOV網與拓撲排序 268

7.7.3 AOE網與關鍵路徑 272

習題7 277

第8章 查找與搜尋引擎 281

8.1 基本概念與術語 281

8.2 順序查找 283

8.3 二分查找（折半查找） 285

8.3.1 二分查找的定義 285

8.3.2 二分查找算法 286

8.3.3 二分查找判定樹 287

8.3.4 二分查找性能分析 287

8.4 有序表的插值查找和斐波那契查找 288

8.4.1 插值查找 288

8.4.2 斐波那契查找 288

8.5 分塊查找 289

8.6 B-樹和B+樹上的查找 291

8.6.1 B-樹及其查找 291

8.6.2 B+樹 293

8.7 哈希表與散列查找 294

8.7.1 散列的概念 295

8.7.2 哈希函式 295

8.7.3 散列存儲的衝突 298

8.7.4 裝填因子 298

8.7.5 衝突解決方法 298

8.7.6 散列存儲的平均查找長度 302

8.7.7 散列存儲的優缺點 303

8.8 搜尋引擎及其相關技術 303

8.8.1 網頁的自動下載與存儲 304

8.8.2 網頁索引技術 306

8.8.3 網頁排名技術 310

習題8 323

第9章 排序 326

9.1 基本概念 327

9.2 插入排序 327

9.2.1 直接插入排序 327

9.2.2 折半插入排序 329

9.2.3 表插入排序 330

9.2.4 希爾排序 332

9.3 交換排序 336

9.3.1 冒泡排序 336

9.3.2 快速排序 337

9.4 選擇排序 343

9.4.1 簡單選擇排序 343

9.4.2 樹形選擇排序 346

9.4.3 堆排序 350

9.5 歸併排序 356

9.6 分配排序 359

9.6.1 箱排序 359

9.6.2 基數排序 360

9.6.3 多關鍵字排序 363

9.7 外排序 364

9.7.1 外部排序的方法 364

9.7.2 多路歸併的實現 365

9.8 排序方法之比較 368

習題9 369