數據結構與算法分析（C++實現）

《數據結構與算法分析（C++實現）》是清華大學出版社2020年出版圖書，作者張千帆、莫嘉銘、王翀

基本介紹

• 中文名：數據結構與算法分析（C++實現）
• 作者：張千帆、莫嘉銘、王翀
• 出版社：清華大學出版社
• ISBN：9787302564379

內容簡介

本書按照循序漸進的原則介紹線性表、棧、佇列、串、樹、圖等數據結構的邏輯結構、存儲結構和數據運算，對於經典算法使用C++構造可執行的程式，幫助讀者利用最少的時間和空間資源編寫出最優秀最合理的程式。本書可以作為高等院校信息管理與信息系統專業、軟體專業、計算機專業的本科教材，也可以作為其他理工科專業的選修教材。教師可以根據本學校的專業特點、學生情況和教學學時，選講部分章節的內容。

作者簡介

張千帆，基金委A類期刊外審專家，中國建築第三工程局有限公司企業管理諮詢顧問。2017年獲得華中科技大學優秀教職工，2016年獲得湖北省大學生暑期社會實踐先進工作者、2011年獲得湖北省教育系統先進女教職工、2012年和2007年獲得華中科技大學教學質量一等獎、2007年獲得華中科技大學教學競賽一等獎。

目錄

第1章緒論1

1.1數據結構與程式設計1

1.1.1學習數據結構的意義1

1.1.2數據與數據結構2

1.1.3數據結構的類型4

1.2抽象數據類型5

1.2.1C++中的數據類型6

1.2.2抽象數據類型與C++特性6

1.3算法分析10

1.3.1問題、算法與程式10

1.3.2算法效率的度量10

本章小結14

第2章線性表15

2.1線性表的基本概念15

2.1.1線性表的定義與特點15

2.1.2線性表的存儲結構15

2.2順序表的算法實現17

2.2.1順序表的創建和插入19

2.2.2順序表內結點的查找23

2.2.3順序表內元素的刪除28

2.3單鍊表的算法實現30

2.3.1單鍊表的結點結構和一般形式30

2.3.2單鍊表的創建和插入32

2.3.3單鍊表內數據元素的查找37

2.3.4單鍊表內數據元素的刪除40

2.3.5單鍊表的合併43

2.4雙向鍊表的算法實現47

2.4.1雙向鍊表的結點結構和一般形式47

2.4.2雙向鍊表的創建和插入49

2.4.3雙向鍊表內元素的查找53

2.4.4雙向鍊表內元素的刪除55

2.5循環鍊表的算法實現57

2.5.1循環鍊表的結點結構和一般形式57

2.5.2循環鍊表的創建58

2.6線性表的套用——一元多項式的存儲和相加63

2.6.1一元多項式的存儲和相加的實現方式63

2.6.2一元多項式的存儲和相加的實現65

2.7STL的使用68

2.7.1STL簡介68

2.7.2STL套用實例68

本章小結69

第3章棧與佇列71

3.1棧的基本概念71

3.1.1棧的定義與特點71

3.1.2棧的兩類存儲結構71

3.2順序棧的算法實現72

3.2.1順序棧的建立和順序棧入棧72

3.2.2順序棧出棧74

3.3佇列的基本概念76

3.3.1佇列的定義與特點76

3.3.2佇列的存儲結構77

3.4順序佇列的算法實現78

3.4.1順序佇列的建立和順序佇列入隊79

3.4.2順序佇列出隊80

3.5循環佇列的算法實現83

3.5.1循環佇列的建立和循環佇列入隊83

3.5.2循環佇列出隊85

3.6鏈佇列的算法實現87

3.6.1鏈佇列的建立和鏈佇列入隊87

3.6.2鏈佇列出隊88

3.7棧和佇列的套用——算術表達式的轉化和求值89

本章小結96

第4章串97

4.1串的基本概念97

4.1.1串的定義與特點97

4.1.2串的存儲結構98

4.2串的算法實現100

4.2.1串賦值算法100

4.2.2求子串算法102

4.2.3串比較算法104

4.2.4串連線算法106

4.3串的模式匹配算法實現107

4.3.1串的樸素模式匹配算法107

4.3.2改進的模式匹配算法109

本章小結114

第5章數組和廣義表115

5.1數組的基本概念115

5.1.1數組的定義與特點115

5.1.2數組的存儲結構116

5.2特殊矩陣的壓縮存儲117

5.3矩陣的算法實現120

5.4廣義表的基本概念126

5.4.1廣義表的定義與圖形表示126

5.4.2廣義表的存儲結構127

5.5廣義表的算法實現128

本章小結134

第6章樹和二叉樹135

6.1樹的基本概念135

6.1.1樹的定義與基本術語135

6.1.2樹的表示形式和存儲結構136

6.2二叉樹的基本概念140

6.2.1二叉樹的定義與性質140

6.2.2二叉樹的存儲結構142

6.2.3樹、森林和二叉樹的轉換144

6.2.4二叉樹的遍歷146

6.3二叉樹算法實現147

6.3.1二叉樹的建立147

6.3.2遞歸的二叉樹前序遍歷、中序遍歷、後序遍歷150

6.3.3非遞歸的二叉樹前序遍歷153

6.3.4非遞歸的二叉樹中序遍歷155

6.3.5非遞歸的二叉樹後序遍歷157

6.4哈夫曼樹及其套用161

6.4.1哈夫曼樹與哈夫曼編碼161

6.4.2哈夫曼算法實現162

本章小結168

第7章圖169

7.1圖的基本概念169

7.1.1圖的定義和術語169

7.1.2圖的表示與存儲結構173

7.2圖的構造算法實現176

7.2.1圖的基本類定義176

7.2.2構造順序表存儲的圖179

7.2.3構造鄰接表存儲的無向圖與有向圖182

7.2.4構造十字鍊表存儲的有向圖188

7.2.5構造鄰接多重表存儲的無向圖193

7.3圖的遍歷算法實現197

7.3.1深度優先遍歷算法198

7.3.2廣度優先遍歷算法200

7.4最小生成樹算法實現204

7.4.1普里姆算法205

7.4.2克魯斯卡爾算法209

7.5圖的套用216

7.5.1拓撲排序216

7.5.2關鍵路徑220

7.5.3最短路徑——迪傑斯克拉算法225

7.5.4最短路徑——弗洛伊德算法229

本章小結234

第8章查找235

8.1查找的基本概念235

8.1.1查找的相關術語235

8.1.2查找表結構236

8.2順序表查找算法實現236

8.3有序順序表的折半查找算法實現240

8.4索引順序表的分塊查找算法實現245

8.4.1索引表245

8.4.2分塊查找算法實現246

8.5二叉排序樹及其算法實現250

8.5.1二叉排序樹及其查找過程250

8.5.2二叉排序樹建立及插入結點的過程251

8.5.3二叉排序樹刪除結點的過程251

8.5.4二叉排序樹的算法實現253

8.6平衡二叉樹及其算法實現258

8.6.1平衡二叉排序樹及其構造258

8.6.2平衡二叉排序樹算法實現261

8.7B樹及其算法實現268

8.7.1B樹268

8.7.2B樹的查找269

8.7.3B樹的插入269

8.7.4B樹的刪除271

8.7.5B樹的算法實現273

8.8哈希查找的算法實現282

8.8.1哈希表282

8.8.2哈希函式的構造方法282

8.8.3哈希衝突的處理方法283

8.8.4哈希表的算法實現285

本章小結289

第9章排序290

9.1排序的基本概念290

9.1.1排序相關術語介紹290

9.1.2常用的內部排序算法類型簡介291

9.2插入排序的算法實現292

9.2.1直接插入排序292

9.2.2希爾排序295

9.3交換排序的算法實現299

9.4選擇排序的算法實現303

9.4.1直接選擇排序303

9.4.2堆排序306

9.5歸併排序的算法實現313

9.6基數排序的算法實現316

9.7各種內部排序方法的比較321

9.7.1時間性能321

9.7.2空間性能321

9.7.3排序方法的穩定性322

9.8外部排序322

本章小結322

第10章綜合案例323

10.1背景介紹323

10.2問題分解323

10.2.1旅行商問題323

10.2.2動態規劃325

10.2.3帶酒店選擇的旅行商問題328

10.3總結與思考331

附錄A資料夾結構332

附錄BUML類圖334

B.1第2章線性表的相關類圖334

B.2第3章棧與佇列的相關類圖336

B.3第4章串的相關類圖337

B.4第5章數組和廣義表的相關類圖338

B.5第6章樹和二叉樹的相關類圖339

B.6第7章圖的相關類圖341

B.7第8章查找的相關類圖344

B.8第9章排序的相關類圖346

參考文獻347