數據結構：C++語言描述(2021年清華大學出版社出版的圖書)

《數據結構：C++語言描述》是2021年清華大學出版社出版的圖書，作者是張淑芬、劉麗。

基本介紹

• 中文名：數據結構：C++語言描述
• 作者：張淑芬、劉麗
• 出版社：清華大學出版社
• 出版時間：2021年3月1日
• 頁數：336 頁
• 開本：16 開
• 裝幀：平裝
• ISBN：9787302574941

內容簡介

主講《數據結構》等課程；主持主研科研課題二十餘項，獲河北省科技進步獎三等獎一項，發明專利一項；第一作者發表科研教改論文三十多篇

圖書目錄

目錄

第1章緒論1

1.1數據結構的研究內容1

1.2數據結構的基本概念3

1.2.1數據、數據元素、數據項和數據對象3

1.2.2數據結構4

1.3抽象數據類型及其實現6

1.3.1數據類型6

1.3.2抽象數據類型6

1.3.3C++的類和對象7

1.3.4C++的動態存儲分配11

1.3.5C++的模板11

1.4算法和算法分析15

1.4.1算法15

1.4.2算法分析16

本章小結20

習題121

第2章線性表23

2.1線性表的邏輯結構23

2.2線性表的順序表示和實現25

2.2.1線性表的順序存儲結構——順序表25

2.2.2順序表的實現26

2.3線性表的鏈式表示和實現33

2.3.1線性表的鏈式存儲結構——鍊表33

2.3.2單鍊表的定義和表示33

2.3.3單鍊表的實現34

2.3.4雙鍊表42

2.3.5循環鍊表44

2.4順序表和鍊表的比較45

2.5線性表的套用46

本章小結52

習題252第3章棧和佇列56

3.1棧56

3.1.1棧的定義56

3.1.2順序棧的表示和實現58

3.1.3鏈棧的表示和實現62

3.1.4棧的套用67

3.2佇列69

3.2.1佇列的定義69

3.2.2循環佇列——佇列的順序表示和實現71

3.2.3鏈隊——佇列的鏈式表示和實現75

3.2.4佇列的套用80

本章小結83

習題384

第4章串88

4.1串的定義88

4.2串的存儲結構90

4.3串的模式匹配91

本章小結96

習題496

第5章數組和廣義表98

5.1數組98

5.1.1數組的基本概念98

5.1.2數組的存儲結構99

5.2矩陣100

5.2.1特殊矩陣的壓縮存儲100

5.2.2稀疏矩陣的壓縮存儲104

5.3廣義表109

5.3.1廣義表的定義109

5.3.2廣義表的存儲結構111

本章小結112

習題5112

第6章樹和二叉樹116

6.1樹116

6.1.1樹的定義116

6.1.2樹的基本術語116

6.1.3樹的抽象數據類型定義118

6.2二叉樹119

6.2.1二叉樹的定義119

6.2.2二叉樹的抽象數據類型定義121

6.2.3二叉樹的性質123

6.2.4二叉樹的存儲結構124

6.2.5二叉鍊表的實現127

6.3二叉樹的遍歷133

6.3.1遍歷的概念133

6.3.2遍歷算法136

6.4線索二叉樹144

6.4.1線索二叉樹的概念144

6.4.2構造線索二叉樹145

6.4.3線索二叉樹的遍歷148

6.5樹和森林149

6.5.1樹的存儲結構149

6.5.2樹和森林與二叉樹的轉換151

6.5.3樹和森林的遍歷154

6.6哈夫曼樹及其套用155

6.6.1哈夫曼樹的基本概念155

6.6.2哈夫曼樹的構造算法156

6.6.3哈夫曼編碼158

本章小結160

習題6161

第7章圖165

7.1圖的基本概念165

7.1.1圖的定義165

7.1.2基本術語166

7.1.3圖的抽象類型定義168

7.2圖的存儲結構169

7.2.1鄰接矩陣169

7.2.2鄰接表176

7.2.3十字鍊表185

7.2.4鄰接多重表185

7.3圖的遍歷186

7.3.1深度優先遍歷187

7.3.2廣度優先遍歷188

7.4圖的套用191

7.4.1最小生成樹191

7.4.2最短路徑197

7.4.3拓撲排序204

7.4.4關鍵路徑208

本章小結213

習題7214

第8章查找219

8.1查找的基本概念219

8.1.1查找的定義219

8.1.2查找算法的性能分析220

8.2基於靜態表的查找221

8.2.1順序查找221

8.2.2折半查找221

8.3二叉排序樹223

8.3.1二叉排序樹的概念224

8.3.2二叉排序樹結點的定義224

8.3.3二叉排序樹類的定義和實現225

8.4二叉平衡樹231

8.4.1二叉平衡樹的概念231

8.4.2二叉平衡樹的平衡處理235

8.4.3二叉平衡樹的插入操作239

8.5B樹和B+樹240

8.5.1B樹241

8.5.2B+樹244

8.6散列表245

8.6.1散列表的概念245

8.6.2常見的散列函式246

8.6.3處理衝突的方法246

本章小結249

習題8249

第9章排序251

9.1排序的基本概念251

9.1.1排序的定義251

9.1.2內排序和外排序251

9.1.3排序用到的類定義251

9.2插入排序252

9.2.1直接插入排序252

9.2.2希爾排序253

9.3交換排序255

9.3.1冒泡排序255

9.3.2快速排序257

9.4選擇排序259

9.4.1簡單選擇排序259

9.4.2堆排序261

9.5歸併排序266

9.6各種內部排序算法的分析和比較268

本章小結269

習題9269

第10章實驗271

實驗1一元多項式求和271

實驗2求解約瑟夫問題277

實驗3表達式求值280

實驗4字元串的加解密285

實驗5利用二叉樹求解簡單算術表達式289

實驗6醫院選址問題294

附錄C++程式設計簡述299

A.1C++程式的基本結構299

A.2C++的數據類型300

A.3順序結構306

A.4選擇結構308

A.5循環結構309

A.6數組311

A.7指針和引用315

A.8函式317

A.9結構體319

參考文獻322