數據結構與算法（第3版）(2024年清華大學出版社出版的圖書)

《數據結構與算法（第3版）》是2024年清華大學出版社出版的圖書，作者是熊岳山。

基本介紹

• 中文名：數據結構與算法（第3版）
• 作者：熊岳山
• 出版時間：2024年1月1日
• 出版社：清華大學出版社
• ISBN：9787302643463 
• 定價：59 元

內容簡介

“數據結構與算法”是計算機科學與技術、軟體工程等相關專業的重要基礎課，是這些專業的核心課程之一，是一門集技術性、理論性和實踐性於一體的課程。本書內容包括基本數據類型、抽象數據類型、線性表、鍊表、串、樹和二叉樹、圖、遞歸與分治算法、貪心算法、分支限界法和動態規劃法等內容；並重點介紹抽象數據類型、基本數據結構、C語言數據結構描述、數據結構的套用、算法設計與分析以及算法性能評價等內容，目的是讓讀者理解數據抽象與編程實現的關係，提高用計算機解決實際問題的能力。

圖書目錄

目錄

第1章數據結構概述1

1.1基本概念1

1.1.1數據、數據元素、數據對象1

1.1.2數據結構2

1.2數據結構的分類3

1.3數據類型5

1.3.1基本類型和組合類型5

1.3.2抽象數據類型5

1.4算法和算法分析8

1.4.1算法概念8

1.4.2算法分析9

習題11

第2章向量、棧和佇列13

2.1線性表13

2.1.1線性表的抽象數據類型13

2.1.2線性表的結構表示15

2.2向量18

2.2.1向量的抽象數據類型18

2.2.2向量的插入和刪除20

2.2.3向量的套用22

2.3棧25

2.3.1棧的抽象數據類型及其實現25

2.3.2棧的套用27

2.4遞歸效率分析34

2.4.1遞歸方程求解34

2.4.2生成函式求解遞歸方程35

2.4.3特徵方程求解遞歸方程36

2.4.4遞歸樹方法37

2.5佇列38

2.5.1佇列的抽象數據類型及其實現39

2.5.2佇列的套用——模擬銀行活動44

習題51

第3章鍊表53

3.1單鍊表53

3.1.1基本概念53

3.1.2單鍊表結點結構54

3.1.3單鍊表結構56

3.1.4棧的單鍊表實現65

3.1.5佇列的單鍊表實現66

3.1.6單鍊表的套用舉例70

3.2循環鍊表74

3.3雙鍊表76

習題78

第4章串81

4.1基本概念81

4.2串的存儲82

4.3串結構和串的運算83

4.4模式匹配85

4.4.1樸素的模式匹配算法85

4.4.2KMP匹配算法86

4.4.3BM匹配算法89

習題91

第5章排序93

5.1基本概念93

5.2插入排序94

5.2.1直接插入排序94

5.2.2折半插入排序95

5.2.3Shell排序97

5.3選擇排序99

5.3.1直接選擇排序99

5.3.2樹形選擇排序100

5.4交換排序101

5.4.1起泡排序101

5.4.2快速排序103

5.5分配排序106

5.5.1基本思想106

5.5.2基數排序107

5.6歸併排序110

5.7外部排序113

5.7.1二路合併排序113

5.7.2多路替代選擇合併排序114

5.7.3最佳合併排序114

習題116

第6章查找117

6.1基本概念117

6.2順序查找117

6.3折半查找119

6.4分塊查找121

6.5散列查找123

6.5.1概述123

6.5.2散列函式124

6.5.3衝突的處理126

6.5.4散列查找的效率129

習題130

第7章樹和二叉樹132

7.1樹的概念132

7.2二叉樹133

7.2.1二叉樹的概念133

7.2.2二叉樹的性質133

7.2.3二叉樹的存儲方式136

7.2.4樹(樹林)與二叉樹的相互轉換138

7.3樹(樹林)、二叉樹的遍歷139

7.3.1樹(樹林)的遍歷139

7.3.2二叉樹的遍歷139

7.4抽象數據類型BinaryTree以及BinaryTree結構140

7.4.1抽象數據類型BinaryTree140

7.4.2一個完整的包含構建二叉樹與遍歷實現的例子142

7.5二叉樹的遍歷算法143

7.5.1非遞歸(使用棧)的遍歷算法143

7.5.2線索化二叉樹的遍歷145

習題148

第8章樹結構的套用150

8.1二叉排序樹150

8.1.1二叉排序樹與BinarySTree結構150

8.1.2二叉排序樹的檢索、插入、刪除運算151

8.1.3等機率查找對應的最佳二叉排序樹154

8.2平衡的二叉排序樹157

8.2.1平衡二叉排序樹的定義157

8.2.2平衡二叉排序樹的插入、刪除157

8.2.3AVL樹高度161

8.3B樹、B+樹161

8.4鍵樹和23樹165

8.4.1鍵樹165

8.4.223樹167

8.5Huffman最優樹與樹編碼168

8.5.1Huffman最優樹168

8.5.2樹編碼171

8.6堆排序173

8.7判定樹178

8.8等價類和並查集179

8.8.1等價類179

8.8.2並查集180

8.9紅黑樹182

8.10跳表186

8.10.1跳表時間複雜度分析187

8.10.2跳表的空間複雜度分析187

8.10.3高效的動態插入和刪除188

8.10.4小結189

習題189

第9章圖191

9.1基本概念191

9.2圖的存儲表示193

9.2.1相鄰矩陣表示圖193

9.2.2圖的鄰接表表示194

9.2.3鄰接多重表195

9.3基於鄰接表表示的Graph結構197

9.4圖的遍歷197

9.4.1深度優先遍歷198

9.4.2廣度優先遍歷200

9.5最小代價生成樹201

9.6單源最短路徑問題205

9.7每一對頂點間的最短路徑問題208

9.8有向無迴路圖209

9.8.1DAG圖和AOV、AOE網209

9.8.2AOV網的拓撲排序211

9.8.3AOE網的關鍵路徑213

習題215

第10章算法設計與分析217

10.1遞歸與分治217

10.1.1遞歸方法設計217

10.1.2分治法218

10.2回溯法220

10.3分支限界法225

10.4貪心算法231

10.5動態規劃法232

10.6數據結構中的Catalan數235

10.6.1問題描述235

10.6.2問題解析235

10.6.3遞歸方程求解236

習題237

關鍵字索引239

參考文獻242