數據結構 — C++語言描述

陳慧南，教授，南京郵電大學計算機學院，主持了多項信息產業部基金項目的研究工作，並負責了多項企業辦公自動化和信息管理網絡系統的研製開發。出版多本教材。曾獲江蘇省普通高校教學成果三等獎，其主持的《數據結構》課程獲江蘇省高校一類優秀課程。

 

第1章概論\t1

1.1問題求解方法\t1

1.1.1問題和問題求解\t1

1.1.2問題求解過程\t1

1.1.3計算機求解問題的過程\t2

1.2什麼是數據結構\t2

1.2.1算法與數據結構\t2

1.2.2數據結構基本概念\t3

1.2.3數據的邏輯結構\t4

1.2.4數據的存儲表示\t5

1.2.5數據結構的操作\t6

1.3數據抽象和抽像數據類型\t7

1.3.1數據抽象和過程抽象\t7

1.3.2模塊化、封裝與信息隱蔽\t7

1.3 .3數據類型和抽像數據類型\t8

1.4面向對象方法\t10

1.4.1面向對象方法的由來\t10

1.4.2面向對象方法的基本思想\t10

1.4.3面向對象方法的基本要素\t11

1.4. 4抽像數據類型和麵向對象方法\t12

1.4.5 C++語言對抽像數據類型的支持\t13

1.5描述數據結構和算法\t13

1.5.1數據結構的規範\t13

1.5.2實現數據結構\t14

1.6算法分析的基本方法\t15

1.6.1算法及其性能標準\t15

1.6.2算法的時間複雜度\t16

1.6.3漸近時間複雜度\t18

1.6.4最好、最壞和平均情況時間複雜度\t19

1.6.5算法按時間複雜度分類\t19

1.6.6算法的空間複雜度\t19

本章小結\t20

習題1\t20

 

第2章數組和鍊錶\t22

2.1兩種基本的存儲表示方式\t22

2.2結構和類\t22

2.2.1結構\t22

2.2.2結構表示元素\t23

2.3指針和動態存儲分配\t24

2.3.1指針\t24

2.3.2動態存儲分配\t25

2.3.3靜態變量和動態變量\t26

2.4數組\t26

2.4.1一維數組\t26

2.4.2二維數組\t27

2.4.3多維數組\t28

2.4.4數組和指針\t28

2.4.5固定長度數組和可變長度數組\t28

2.5鍊錶\t29

2.5.1指向結構的指針\t30

2.5.2單鍊錶\t30

2.5.3帶錶頭結點的單鍊錶\t33

2.5.4單循環鍊錶\ t33

2.5.5雙向鍊錶\t33

2.6採用模擬指針的鍊錶\t35

2.6.1結點結構\t35

2.6.2可用空間表\t35

2.7異常處理\t37

本章小結\t38

習題2\t38

 

第3章棧和隊列\t40

3.1棧\t40

3.1.1棧ADT\t40

3.1.2棧的順序表示\t41

3.1.3棧的鏈接表示\t44

3.2隊列\t47

3.2.1隊列ADT\t47

3.2.2隊列的順序表示\t48

3.2.3隊列的鏈接表示\t51

3.3表達式計算\t51

3.3.1表達式\t51

3.3.2中綴表達式轉換為後綴表達式\t52

3.3.3計算後綴表達式的值\t55

3.4演示與測試\t58

本章小結\t61

習題3\t61

 

第4章遞歸\t63

4.1遞歸和遞歸算法\t63

4.1.1遞歸的概念\t63

4.1.2遞歸算法示例\t64

4.2歸納證明\t66

4.3遞推關係\t67

4.4實現遞歸\ t67

4.4.1函數調用和系統棧\t68

4.4.2遞歸函數的性能\t69

4.4.3尾遞歸\t69

4.4.4消去遞歸\t70

本章小結\t70

習題4\t70

 

第5章線性表和串\ t72

5.1線性表\t72

5.1.1線性表ADT\t72

5.1.2線性表的順序表示\t73

5.1.3線性表的鏈接表示\t76

5.1.4兩種存儲表示的比較\t79

5.2一元多項式算術運算\t80

5.2.1多項式ADT\t80

5.2.2多項式的鏈接表示\t80

5.2.3項結點類\t81

5.2.4多項式類\t82

5.2.5多項式的輸入和輸出\t83

5.2.6多項式相加\t84

5.2.7多項式相乘\t85

5.2.8重載運算符\t86

5.3串\t86

5.3.1串ADT\t86

5.3.2串的存儲表示\t87

5.3.3串運算的實現\t88

5.3.4簡單模式匹配算法\ t89

5.3.5 KMP算法\t91

本章小結\t95

習題5\t95

 

第6章數組和廣義表\t97

6.1數組作為抽像數據類型\t97

6.1.1數組ADT\t97

6.1.2一維數組的C++類\ t98

6.2矩陣\t99

6.2.1矩陣的概念\t99

6.2.2矩陣ADT\t99

6.2.3矩陣的二維數組表示\t100

6.3特殊矩陣\t101

6.3.1對稱矩陣\t101

6.3.2帶狀矩陣\t102

6.4稀疏矩陣\t103

6.4.1稀疏矩陣的三元組表\t103

6.4.2稀疏矩陣轉置\t105

6.4.3稀疏矩陣相加\t107

6.4.4稀疏矩陣相乘\t108

6.5稀疏矩陣的正交鍊錶\t109

6.5.1正交鍊錶結構\t109

6.5.2正交鍊錶結點類\t110

6.5.3正交鍊錶類\t111

6.5.4建立正交鍊錶\t111

6.5.5輸出正交鍊錶\t113

6.6廣義表\t113

6.6.1廣義表的概念\t113

6.6.2廣義表ADT\t114

6.6.3廣義表的存儲表示\t115

6.6.4廣義表算法\t116

本章小結\t116

習題6\t117

 

第7章樹\t118

7.1樹的基本概念\t118

7.1 .1樹的定義\t118

7.1.2基本術語\t119

7.2二叉樹\t120

7.2.1二叉樹的定義\t120

7.2.2二叉樹的性質\t121

7.2.3二叉樹ADT\t122

7.2.4二叉樹的存儲表示\t123

7.2.5二叉樹類\t123

7.2.6實現二叉樹的基本操作\t124

7.3二叉樹的遍歷\t126

7.3.1二叉樹遍曆算法\t126

7.3.2二叉樹遍歷的遞歸算法\t128

7.3.3二叉樹遍歷的應用實例\t129

7.4二叉樹遍歷的非遞歸算法\t131

7.4.1遍歷器類\t131

7.4.2中序遍歷器類\t132

7.4.3後序遍歷器類\t134

7.5二叉線索樹\t136

7.5.1二叉線索樹的定義\t136

7.5.2構造中序線索樹\t137

7.5.3遍歷中序線索樹\t138

7.6樹和森林\t139

7.6.1森林與二叉樹的轉換\t139

7.6.2樹和森林的存儲表示\t141

7.6.3樹和森林的遍歷\t142

本章小結\t143

習題7\t143

 

第8章樹的應用\t145

8.1堆\t145

8.1.1堆的定義\t145

8.1.2堆的順序表示\t145

8.1.3向下調整和建堆操作\t145

8.2優先權隊列\t147

8.2.1優先權隊列ADT\t147

8.2. 2優先權隊列類\t148

8.2.3實現優先權隊列\t148

8.3哈夫曼樹和哈夫曼編碼\t150

8.3.1樹的路徑長度\t151

8.3.2哈夫曼算法\t152

8.3.3哈夫曼樹類\t152

8.3.4構造哈夫曼樹\t153

8.3.5哈夫曼編碼\t155

8.3.6哈夫曼編碼算法\t156

8.4並查集和等價關係\t156

8.4.1並查集ADT\t157

8.4.2並查集的存儲表示\t157

8.4.3並查集類\t158

8.4.4 Union和Find函數\t159

8.4.5改進的Union和Find函數\t159

8.4.6按等價關係分組\t160

本章小結\t161

習題8\t161

 

第9章字典和查找\t162

9.1字典及其表示\t162

9.1.1字典\t162

9.1.2字典查找\t163

9.1.3字典ADT\t163

9.1.4字典的存儲表示\t164

9.2順序查找\t165

9.2.1無序表的順序查找\t165

9.2.2有序表的順序查找\t165

9.2.3平均查找長度\t166

9.2.4自組織表\t166

9.3二分查找\t167

9.3.1二分查找算法\t167

9.3.2對半查找算法\t168

9.3.3二叉判定樹\t169

9.3.4斐波那契查找算法\t170

9.3.5插值查找\t172

9.4分塊查找\t172

9.5查找算法的時間複雜度下界\t173

本章小結\t174

習題9\t174

 

第10章二叉查找樹\t175

10.1二叉查找樹表示字典\t175

10.1.1二叉查找樹的定義\t175

10.1.2二叉查找樹的查找操作\t176

10.1.3二叉查找樹的插入操作\t177

10.1. 4二叉查找樹的刪除操作\t178

10.1.5二叉查找樹的高度\t179

10.2二叉平衡樹\t179

10.2.1二叉平衡樹的定義\t179

10.2.2二叉平衡樹類\t180

10.2.3二叉平衡樹的平衡旋轉\t181

10.2.4二叉平衡樹的插入操作\t185

10.2.5二叉平衡樹的刪除操作\t187

10.2.6二叉平衡樹的高度\t189

10.3伸展樹\t190

10.3.1自調節樹和伸展樹\t190

10.3.2伸展樹的伸展操作\ t191

10.3.3伸展樹類\t193

10.3.4旋轉的實現\t193

10.3.5伸展樹的插入操作\t194

10.3.6分攤時間分析\t195

10.4紅黑樹\t195

10.4.1紅黑樹的定義\ t195

10.4.2紅黑樹的查找操作\t196

10.4.3紅黑樹的插入操作\t196

10.4.4紅黑樹的刪除操作\t198

10.4.5紅黑樹的高度\t199

本章小結\t199

習題10 \t199

 

第11章多叉查找樹\t201

11.1 m叉查找樹\t201

11.2 B樹\t202

11.2.1 B樹的定義\t203

11.2.2 B樹的高度\t203

11.2.3 B樹的查找操作\t203

11.2.4 B樹的插入操作\t204

11.2.5 B樹的刪除操作\t206

11.2. 6 B樹類\t207

11.2.7 B樹的查找操作\t208

11.2.8 B樹的插入函數\t209

11.2.9 B樹的刪除函數\t210

11.3鍵樹\t212

11.3.1鍵樹的定義\t212

11.3.2雙鏈樹\t213

11.3.3 Trie樹\t214

11.3.4 Trie樹的查找操作\t216

11.3.5 Trie樹的插入操作\t216

11.3.6 Trie樹的刪除操作\t217

11.3.7 Trie樹性能分析\t217

本章小結\t218

習題11\t218

 

第12章跳表和散列表\t219

12.1跳表\t219

12.1.1跳表的概念\t219

12.1.2跳表類\t221

12.1.3跳表的查找函數\t222

12.1.4跳表的插入函數\t223

12.1.5跳表的刪除函數\t224

12.1.6性能分析\t224

12.2散列表\t224

12.2.1散列技術\t225

12.2.2散列函數\t226

12.2.3拉鍊法\t227

12.2.4開地址法\t228

12.2.5線性探查法\ t228

12.2.6其他開地址法\t231

12.2.7性能分析\t233

本章小結\t233

習題12\t234

 

第13章圖\t235

13.1圖的基本概念\t235

13.1.1圖的定義與術語\t235

13.1. 2圖的抽像數據類型\t237

13.2圖的存儲結構\t238

13.2.1圖的矩陣表示\t238

13.2.2圖的鄰接矩陣實現\t239

13.2.3圖的鄰接表表示\t241

13.2.4圖的鄰接表實現\t242

13.2.5有向圖的正交鍊錶表示\t245

13.2.6無向圖的鄰接多重表表示\t245

13.3圖的遍歷\t246

13.3.1擴充的圖類\t246