數據結構（AR版）

《數據結構（AR版）》是2019年10月清華大學出版社出版的圖書，作者是連遠鋒。

基本介紹

• 中文名：數據結構（AR版）
• 作者：連遠鋒
• 出版時間：2019年10月
• 出版社：清華大學出版社
• ISBN：9787302535249
• 定價：59 元

內容簡介

本書共8章，內容包括緒論、線性表、棧和佇列、數組、樹、圖、查找和排序等。書中給出了數據結構的增強現實案例。本書內容豐富、條理清晰，講解攝入淺出，特色鮮明，實用性強，適合高等院校計算機和相關專業的本科生及研究生使用。

圖書目錄

第1章緒論/1

1.1數據結構的重要性1

1.2數據結構基本術語2

1.3數據的邏輯結構4

1.4數據的存儲結構5

1.5算法的基本概念5

1.6算法分析與度量6

1.6.1算法的評價標準6

1.6.2算法效率的度量7

1.7總結與提高13

1.8習題一13

第2章線性結構/16

2.1線性表及邏輯結構16

2.2線性表的順序存儲18

2.2.1順序存儲18

2.2.2順序表的存儲結構描述19

2.2.3順序結構上的運算19

2.3線性表的鏈式存儲26

2.3.1線性鍊表26

2.3.2線性鍊表的存儲結構描述27

2.3.3線性鍊表的基本運算28

2.3.4線性鍊表操作的性能分析35

2.4順序表與鍊表的比較35

2.5循環鍊表36

2.6雙向鍊表37

2.7套用舉例42

2.7.1順序表的套用： 大整數求和42

2.7.2單鍊表的套用： 一元多項式加法運算44〖1〗數據結構(AR版)〖3〗〖3〗2.8總結與提高48

2.9習題二49

第3章棧和佇列/51

3.1棧51

3.1.1棧的定義51

3.1.2棧的順序存儲結構52

3.1.3棧的鏈式存儲結構57

3.1.4棧的特性分析63

3.2佇列65

3.2.1佇列的定義65

3.2.2循環佇列66

3.2.3鏈式佇列70

3.2.4雙端佇列74

3.3棧和佇列的套用76

3.3.1括弧匹配76

3.3.2表達式求解78

3.3.3佇列在層次遍歷中的套用86

3.4遞歸87

3.4.1遞歸的概念87

3.4.2遞歸算法的設計89

3.4.3轉化遞歸算法為非遞歸算法91

3.5總結與提高95

3.6習題三95

第4章數組和字元串/98

4.1數組的定義98

4.2數組的順序存儲結構99

4.2.1一維數組的順序存儲100

4.2.2多維數組的順序存儲100

4.3矩陣的壓縮存儲104

4.3.1特殊矩陣的壓縮存儲105

4.3.2三對角矩陣的壓縮存儲106

4.3.3稀疏矩陣的壓縮存儲107

4.4稀疏矩陣的運算116

4.4.1稀疏矩陣的轉置116

4.4.2稀疏矩陣的乘法119

4.5字元串124

4.5.1串的基本概念124

4.5.2串的存儲結構124

4.5.3串的模式匹配算法126

4.6總結與提高133

4.7習題四133

第5章樹/136

5.1樹的定義及基本術語136

5.2N叉樹138

5.2.1N叉樹的概念138

5.2.2N叉樹的性質139

5.3二叉樹140

5.3.1二叉樹的定義及性質140

5.3.2二叉樹的基本操作142

5.4二叉樹的存儲結構143

5.4.1順序存儲結構143

5.4.2鏈式存儲結構143

5.5二叉樹的操作146

5.5.1二叉樹的遞歸遍歷146

5.5.2二叉樹構造函式149

5.5.3二叉樹析構函式150

5.5.4遞歸遍歷算法的套用舉例150

5.5.5由遍歷序列恢復二叉樹153

5.5.6二叉樹遍歷的非遞歸算法154

5.6線索二叉樹158

5.6.1線索二叉樹的定義158

5.6.2中序線索二叉樹的建立和遍歷160

5.6.3中序線索二叉樹插入166

5.6.4中序線索二叉樹刪除170

5.6.5前序與後序線索二叉樹174

5.6.6線索二叉樹算法的套用舉例174

5.7二叉排序樹176

5.7.1二叉排序樹的基本概念176

5.7.2二叉排序樹的插入178

5.7.3二叉排序樹的刪除180

5.7.4二叉排序樹查找分析184

5.7.5二叉排序樹算法的套用舉例187

5.8平衡二叉樹188

5.8.1平衡二叉樹基本概念188

5.8.2平衡化旋轉188

5.8.3平衡二叉樹的插入191

5.8.4平衡二叉樹的刪除194

5.8.5平衡二叉樹算法的套用舉例198

5.9樹、森林與二叉樹的關係207

5.9.1樹的存儲結構207

5.9.2森林與二叉樹的轉換211

5.9.3樹與森林的遍歷213

5.10Huffman樹及其套用215

5.10.1帶權路徑長度的概念215

5.10.2Huffman樹的構造216

5.10.3Huffman樹結構定義及算法實現218

5.10.4Huffman編碼219

5.11總結與提高222

5.12習題五223

第6章圖/227

6.1圖的基本概念227

6.1.1圖的基本概念與術語227

6.1.2圖的基本操作230

6.2圖的存儲結構232

6.2.1鄰接矩陣232

6.2.2鄰接表236

6.2.3有向圖的十字鍊表表示240

6.2.4無向圖的鄰接多重表表示245

6.3圖的遍歷248

6.3.1深度優先搜尋249

6.3.2廣度優先搜尋251

6.4生成樹254

6.4.1MST性質254

6.4.2Kruskal算法255

6.4.3Prim算法261

6.5路徑規劃264

6.5.1最短路徑265

6.5.2Dijkstra算法265

6.5.3Floyd算法269

6.6拓撲排序272

6.7關鍵路徑278

6.8總結與提高288

6.9習題六288

第7章查找/292

7.1基本概念292

7.2線性表查找293

7.2.1順序查找293

7.2.2線性鍊表上的順序查找295

7.3折半查找法296

7.3.1一般的折半查找法296

7.3.2次優查找樹： 折半查找的改進方法299

7.4索引查找305

7.4.1索引順序表與分塊查找305

7.4.2多級索引結構與m叉查找樹307

7.4.3B樹的概念308

7.4.4B樹上的查找310

7.4.5B樹上的插入312

7.4.6B樹上的刪除316

7.4.7B樹析構函式322

7.4.8B樹層序遍歷輸出322

7.4.9B樹操作套用舉例324

7.4.10B+樹324

7.5散列表及其查找325

7.5.1散列的概念326

7.5.2散列函式設計326

7.5.3處理衝突的方法329

7.5.4散列表查找性能分析341

7.6總結與提高342

7.7習題七343

第8章排序/345

8.1基本概念345

8.2插入排序346

8.2.1直接插入排序347

8.2.2折半插入排序349

8.2.3希爾排序350

8.3交換排序352

8.3.1冒泡排序352

8.3.2快速排序354

8.4選擇排序359

8.4.1簡單選擇排序360

8.4.2堆排序361

8.5歸併排序366

8.5.1二路歸併366

8.5.2二路歸併遞歸排序算法368

8.6分配排序369

8.6.1桶排序369

8.6.2基數排序370

8.6.3關鍵字分解370

8.6.4鏈式基數排序371

8.7內部排序算法比較378

8.7.1排序方法的下界378

8.7.2各種內排序方法的比較379

8.8總結與提高382

8.9習題八382

參考文獻/384

第1章面向對象程式設計概述/1

1.1面向過程程式設計1

1.2面向對象程式設計5

1.2.1面向對象程式設計的思想5

1.2.2面向對象的基本概念6

1.2.3面向對象程式設計的優點9

1.3面向對象的軟體開發10

1.4圖書館圖書借閱管理系統的面向對象分析與設計12

1.4.1面向對象分析12

1.4.2面向對象設計15

本章小結16

習題17

第2章面向過程程式設計概述/18

2.1從C語言到C++18

2.2簡單C++程式19

2.3C++對C語言的擴充25

2.3.1C++的輸入輸出25

2.3.2C++對C語言數據類型的擴展26

2.3.3常變數26

2.3.4指針28

2.3.5引用38

2.3.6函式44

2.3.7名字空間53

2.3.8字元串變數56

2.3.9複數變數60

2.4C++程式的編寫和實現63

本章小結64

習題64第3章類與對象/66

3.1類的聲明和對象的定義66

3.1.1類和對象的概念及其關係66

3.1.2類的聲明67

3.1.3對象的定義68

3.2類的成員函式70

3.2.1成員函式的性質70

3.2.2在類外定義成員函式70

3.2.3inline成員函式71

3.2.4成員函式的存儲方式72

3.3對象成員的訪問74

3.3.1通過對象名和成員運算符來訪問對象的成員74

3.3.2通過指向對象的指針來訪問對象的成員74

3.3.3通過對象的引用來訪問對象的成員75

3.4構造函式與析構函式76

3.4.1構造函式76

3.4.2析構函式80

3.4.3構造函式和析構函式的調用次序81

3.5對象數組85

3.6對象指針88

3.6.1指向對象的指針88

3.6.2指向對象成員的指針88

3.6.3this指針90

3.7對象與const92

3.7.1常對象92

3.7.2常對象成員93

3.7.3指向對象的常指針94

3.7.4指向常對象的指針94

3.7.5對象的常引用96

3.8對象的動態創建與釋放97

3.9對象的賦值與複製98

3.9.1對象的賦值98

3.9.2對象的複製102

3.9.3對象的賦值與複製的比較105

3.10向函式傳遞對象105

3.11圖書館圖書借閱管理系統中類的聲明和對象的定義108

本章小結115

習題115

第4章繼承與派生/118

4.1繼承與派生的概念118

4.2派生類的聲明119

4.3派生類的構成120

4.4派生類中基類成員的訪問屬性121

4.4.1公用繼承121

4.4.2私有繼承123

4.4.3保護成員和保護繼承125

4.4.4成員同名問題127

4.5派生類的構造函式和析構函式129

4.5.1派生類構造函式129

4.5.2派生類析構函式132

4.6多重繼承134

4.6.1聲明多重繼承的方法134

4.6.2多重繼承派生類的構造函式與析構函式134

4.6.3多重繼承引起的二義性問題137

4.6.4虛基類139

4.7基類與派生類對象的關係143

4.8聚合與組合146

4.9圖書館圖書借閱管理系統中繼承與聚合的套用148

本章小結165

習題166

第5章多態性與虛函式/168

5.1什麼是多態性168

5.2向上類型轉換169

5.3功能早綁定和晚綁定171

5.4實現功能晚綁定——虛函式171

5.4.1虛函式的定義和作用172

5.4.2虛析構函式175

5.4.3虛函式與重載函式的比較177

5.5純虛函式和抽象類177

5.6圖書館圖書借閱管理系統中的多態性180

本章小結187

習題188

第6章友元與靜態成員/189

6.1封裝的破壞——友元189

6.1.1友元函式189

6.1.2友元類194

6.2對象機制的破壞——靜態成員195

6.2.1靜態數據成員196

6.2.2靜態成員函式198

6.3圖書館圖書借閱管理系統中友元與靜態成員的套用201

本章小結202

習題202

第7章運算符重載/205

7.1為什麼要進行運算符重載205

7.2運算符重載的方法207

7.3重載運算符的規則208

7.4運算符重載函式作為類的成員函式和友元函式210

7.4.1運算符重載函式作為類的成員函式210

7.4.2運算符重載函式作為類的友元函式214

7.5幾種常用運算符的重載217

7.5.1單目運算符“++”和“--”的重載217

7.5.2賦值運算符“=”的重載221

7.5.3流插入運算符“<<”和流提取運算符“>>”的重載223

7.6不同類型數據間的轉換227

7.6.1系統預定義類型間的轉換227

7.6.2轉換構造函式228

7.6.3類型轉換函式231

7.7圖書館圖書借閱管理系統中的運算符重載233

本章小結238

習題239

第8章泛型編程/240

8.1函式模板240

8.1.1函式模板的定義241

8.1.2函式模板的實例化243

8.1.3模板參數244

8.1.4函式模板重載248

8.2類模板251

8.2.1類模板的定義252

8.2.2類模板的實例化253

8.2.3類模板參數256

8.3STL簡介259

8.3.1容器 259

8.3.2疊代器269

8.3.3算法271

8.3.4函式對象273

8.4圖書館圖書借閱管理系統中的泛型編程276

本章小結282

習題282

第9章輸入輸出/285

9.1C++的輸入輸出概述285

9.1.1C++的輸入輸出285

9.1.2C++的輸入輸出流286

9.2C++的標準輸入輸出流288

9.2.1C++的標準輸出流288

9.2.2C++的標準輸入流291

9.3輸入輸出運算符297

9.3.1輸入運算符297

9.3.2輸出運算符298

9.3.3輸入與輸出運算符的重載298

9.4C++格式輸入輸出299

9.4.1用流對象的成員函式控制輸入輸出格式299

9.4.2用控制符控制輸入輸出格式302

9.5檔案操作與檔案流304

9.5.1檔案的概念304

9.5.2檔案流類及檔案流對象304

9.5.3檔案的打開與關閉305

9.5.4對文本檔案的操作306

9.5.5對二進制檔案的操作308

9.6圖書館圖書借閱管理系統中的檔案操作312

本章小結313

習題313

第10章異常處理/315

10.1C++異常處理概述315

10.2C++異常處理的實現316

10.3異常與函式322

10.3.1在函式中處理異常322

10.3.2在函式調用中完成異常處理323

10.3.3限制函式異常324

10.4異常與類324

10.4.1構造函式、析構函式與異常處理324

10.4.2異常類327

10.5圖書館圖書借閱管理系統中的異常處理330

本章小結332

習題333

第11章圖形界面設計/334

11.1基於對話框的圖形界面C++程式設計334

11.2基於單文檔的圖形界面C++程式設計345

11.3圖書館圖書借閱管理系統的圖形界面設計364

本章小結 364

習題365

參考文獻/366第1章C語言程式設計概述/1

1.1程式設計語言1

1.1.1“存儲程式”原理1

1.1.2程式設計語言的發展3

1.1.3語言處理程式4

1.2C語言的發展和特點5

1.3C語言的語法單位6

1.3.1C語言的基本符號6

1.3.2關鍵字6

1.3.3標識符6

1.3.4C語言語句8

1.4C語言程式的基本結構8

1.4.1簡單的C語言程式介紹8

1.4.2C程式的結構與書寫規則11

1.5程式設計與算法13

1.5.1程式設計13

1.5.2算法概述14

1.5.3算法的描述15

1.5.4結構化程式設計方法19

1.6C語言程式的上機調試20

1.6.1C語言的編譯環境與運行程式的步驟20

1.6.2Turbo C開發環境21

1.6.3WinTC系統上機操作方法26

1.6.4Visual C++ 6.0系統上機操作方法28

本章小結34

習題34

上機實訓36

實訓項目: C語言開發環境的使用與程式調試 37

第2章數據類型、運算符與表達式/39

2.1C語言數據類型與數據的存儲39〖1〗C語言程式設計實用教程〖3〗〖3〗2.1.1C語言的數據類型39

2.1.2數據在記憶體中的存儲形式41

2.2變數與常量43

2.2.1常量43

2.2.2變數47

2.3C語言的運算符和表達式53

2.3.1概述53

2.3.2算術運算符和算術表達式55

2.3.3關係運算符和關係表達式57

2.3.4邏輯運算符和邏輯表達式58

2.3.5賦值運算符和賦值表達式60

2.3.6條件運算符和條件表達式61

2.4不同類型數據間的混合運算63

2.5位運算64

2.5.1位邏輯運算64

2.5.2位移運算65

2.5.3位運算賦值運算符65

2.6常用數學庫函式的使用66

本章小結67

習題68

上機實訓70

第3章順序結構程式設計/72

3.1C語言簡單語句72

3.2數據的輸入與輸出73

3.3格式化輸入與輸出75

3.3.1格式化輸出函式printf75

3.3.2格式化輸入函式scanf80

3.4字元數據的輸入與輸出84

3.4.1字元輸出函式putchar84

3.4.2字元輸入函式getchar85

3.5順序結構程式設計舉例87

本章小結90

習題90

上機實訓93

第4章選擇結構程式設計/95

4.1if語句95

4.1.1單分支if語句95

4.1.2雙分支if語句96

4.1.3if語句的嵌套97

4.2switch語句100

4.3選擇結構程式設計舉例102

本章小結106

習題107

上機實訓110

第5章循環結構程式設計/112

5.1循環的概念112

5.2for語句113

5.3while語句117

5.4do…while語句119

5.5break與continue語句121

5.5.1break語句121

5.5.2continue語句123

5.6循環的嵌套124

5.7程式舉例126

本章小結128

習題128

上機實訓134

第6章數組/136

6.1概述136

6.2一維數組137

6.2.1一維數組的定義137

6.2.2一維數組的引用138

6.2.3一維數組的初始化139

6.2.4套用舉例141

6.3二維數組145

6.3.1二維數組的定義145

6.3.2二維數組的引用147

6.3.3二維數組的初始化147

6.3.4二維數組的套用舉例148

6.4字元數組與字元串150

6.4.1字元數組150

6.4.2字元串152

6.4.3字元串處理函式153

本章小結156

習題157

上機實訓160

第7章函式/162

7.1函式的定義與調用162

7.1.1函式的分類162

7.1.2函式定義的一般形式164

7.1.3函式的調用167

7.1.4函式的參數傳遞168

7.2函式的嵌套調用與遞歸調用172

7.2.1函式的嵌套調用172

7.2.2函式的遞歸調用173

7.3變數的作用域和存儲類別175

7.3.1變數的作用域175

7.3.2變數的存儲類別177

7.4內部函式與外部函式178

7.4.1內部函式179

7.4.2外部函式179

7.5程式的多檔案結構180

7.6程式舉例185

本章小結189

習題189

上機實訓192

第8章編譯預處理/194

8.1宏定義命令194

8.2檔案包含200

8.3條件編譯203

本章小結205

習題205

上機實訓209

第9章指針/210

9.1地址與指針類型210

9.1.1地址及取地址運算210

9.1.2指針類型與指針運算211

9.2指針變數213

9.2.1指針變數的定義213

9.2.2指針變數的運算214

9.3指針與數組217

9.3.1指向數組元素的指針217

9.3.2用指針法引用數組元素218

9.3.3多維數組與指針220

9.4指針與字元串224

9.5指針與函式227

9.5.1指針變數作函式的參數227

9.5.2指向函式的指針變數232

9.5.3指針型函式235

9.6指針型數組237

9.7多級指針240

本章小結241

習題242

上機實訓245

第10章結構體、共用體和枚舉類型/247

10.1結構體類型247

10.1.1結構體類型的定義247

10.1.2結構體變數的說明與引用249

10.1.3位段253

10.2結構體數組255

10.2.1結構體數組的定義與初始化255

10.2.2套用舉例257

10.3結構體與指針259

10.3.1結構體類型的指針變數259

10.3.2指向結構體數組的指針261

10.3.3結構體類型變數作函式的參數262

10.4動態數據結構與鍊表264

10.4.1鍊表的相關概念264

10.4.2動態記憶體分配函式265

10.4.3鍊表的建立與操作267

10.5共用體272

10.5.1共用體類型的定義與變數說明272

10.5.2共用體變數的引用273

10.6枚舉類型275

10.7用typedef說明一種新類型名277

本章小結280

習題280

上機實訓283

第11章檔案操作/285

11.1C語言檔案概述285

11.2檔案的打開與關閉288

11.3檔案的讀寫291

11.3.1字元的輸入和輸出291

11.3.2格式化輸入和輸出294

11.3.3字元串的輸入和輸出298

11.4隨機檔案的讀寫301

11.4.1檔案的定位301

11.4.2fread函式與fwrite函式302

11.5出錯檢測函式305

11.5.1ferror( )函式305

11.5.2clearerror( )函式305

本章小結306

習題307

上機實訓311

第12章課程設計/313

12.1課程設計的目的313

12.2課程設計的選題與實施過程314

12.2.1選題314

12.2.2實施過程314

12.3課程設計報告的內容315

12.4課程設計參考題目315

本章小結321

綜合項目實訓321

附錄AC常用庫函式/325

附錄B全國計算機等級考試二級C語言考試大綱/333

附錄C計算機二級C語言考試模擬題/336

模擬題參考答案350

附錄D習題參考答案/351第1章習題解答351

第2章習題解答353

第3章習題解答354

第4章習題解答356

第5章習題解答359

第6章習題解答364

第7章習題解答367

第8章習題解答371

第9章習題解答372

第10章習題解答375

第11章習題解答378

參考文獻/382