數據結構與算法分析：C++語言描述（第4版）

目錄

 

第1章程序設計: 綜述1

1.1本書討論的內容1

1.2復習數學知識2

1.2.1指數2

1.2.2對數2

1.2.3級數3

1.2.4模運算4

1.2.5證明方法4

1.3遞歸簡論6

1.4C++類8

1.4.1類的基本語法8

1.4.2構造函數的其他語法和訪問函數9

1.4.3接口與實現分離11

1.4.4vector類和string類13

1.5C++細節15

1.5.1指針15

1.5.2左值、右值和引用16

1.5.3參數傳遞18

1.5.4傳遞返回值20

1.5.5std:swap和std::move21

1.5.6五大函數21

1.5.7C風格的數組和字符串25

1.6模板26

1.6.1函數模板26

1.6.2類模板27

1.6.3Object、Comparable和例子28

1.6.4函數對象29

1.6.5類模板的分離式編譯31

1.7使用矩陣32

1.7.1數據成員、構造函數和基本訪問函數33

1.7.2operator［ ］33

1.7.3五大函數33

小結33

練習34

參考文獻35

第2章算法分析36

2.1數學基礎36

2.2模型38

2.3要分析的問題38

2.4估算運行時間40

2.4.1簡單的例子40

2.4.2一般法則41

2.4.3求解最大子序列和問題42

2.4.4對數運行時間46

2.4.5分析最壞情況的局限性49

小結49

練習49

參考文獻53

第3章表、棧和隊列54

3.1抽象數據類型54

3.2表ADT54

3.2.1表的簡單數組實現55

3.2.2簡單鏈表55

3.3STL中的容器vector和list56

3.3.1疊代器57

3.3.2例子: 對表使用erase函數58

3.3.3const_iterators59

3.4vector的實現61

3.5list的實現64

3.6棧ADT72

3.6.1棧模型72

3.6.2棧的實現73

3.6.3棧的應用73

3.7隊列ADT79

3.7.1隊列模型79

3.7.2隊列的數組實現79

3.7.3隊列的應用80

小結81

練習81

第4章樹85

4.1預備知識85

4.1.1樹的實現86

4.1.2樹的遍歷與應用86

4.2二叉樹89

4.2.1實現89

4.2.2例子: 表達式樹89

4.3查找樹ADT——二叉查找樹91

4.3.1contains函數93

4.3.2findMin函數和findMax函數94

4.3.3insert函數95

4.3.4remove函數96

4.3.5析構函數和拷貝構造函數98

4.3.6平均情況分析98

4.4AVL樹100

4.4.1單旋轉102

4.4.2雙旋轉104

4.5伸展樹109

4.5.1一種簡單的想法（不可行）110

4.5.2伸展111

4.6樹的遍歷（回顧）116

4.7B樹117

4.8STL中的容器set和map121

4.8.1集合容器set121

4.8.2映射容器map122

4.8.3set和map的實現123

4.8.4例子: 使用多個map123

小結127

練習127

參考文獻132

第5章散列表133

5.1基本思想133

5.2散列函數134

5.3分離鏈接法135

5.4不用鏈表的散列表138

5.4.1線性探測法139

5.4.2平方探測法140

5.4.3雙散列143

5.5再散列144

5.6標準庫中的散列表146

5.7最壞情況下O(1)訪問時間的散列表146

5.7.1完美散列147

5.7.2杜鵑散列148

5.7.3跳房子散列155

5.8通用散列158

5.9可擴散列160

小結162

練習163

參考文獻166

第6章優先隊列（堆）168

6.1模型168

6.2幾種簡單的實現169

6.3二叉堆169

6.3.1結構性質169

6.3.2堆序性質170

6.3.3堆的基本操作171

6.3.4堆的其他操作174

6.4優先隊列的應用176

6.4.1選擇問題177

6.4.2事件模擬178

6.5d堆179

6.6左式堆179

6.6.1左式堆的性質179

6.6.2左式堆的操作180

6.7斜堆185

6.8二項隊列186

6.8.1二項隊列的結構186

6.8.2二項隊列的操作187

6.8.3二項隊列的實現189

6.9標準庫的優先隊列193

小結194

練習194

參考文獻198

第7章排序200

7.1預備知識200

7.2插入排序201

7.2.1算法201

7.2.2插入排序的STL實現201

7.2.3插入排序的分析202

7.3一些簡單排序算法的下界203

7.4希爾排序203

7.4.1算法204

7.4.2希爾排序的最壞情況分析204

7.5堆排序206

7.5.1算法206

7.5.2堆排序的分析207

7.6歸並排序209

7.6.1算法209

7.6.2歸並排序的分析211

7.7快速排序213

7.7.1選取軸值214

7.7.2劃分策略216

7.7.3小數組217

7.7.4實際的快速排序程序217

7.7.5快速排序的分析219

7.7.6選擇問題的期望線性時間算法221

7.8排序算法的一般下界222

7.9選擇問題的判定樹下界224

7.10對手下界225

7.11線性時間排序: 桶式排序和基數排序227

7.12外部排序231

7.12.1為什麼需要新算法231

7.12.2外部排序模型231

7.12.3簡單算法232

7.12.4多路合並232

7.12.5多相合並233

7.12.6替換選擇234

小結235

練習235

參考文獻240

第8章不相交集類241

8.1等價關系241

8.2動態等價問題241

8.3基本數據結構243

8.4靈活的union算法245

8.5路徑壓縮246

8.6按秩合並與路徑壓縮的最壞情況248

8.6.1緩慢增長的函數248

8.6.2通過遞歸分解進行分析248

8.6.3O(MlogN)界254

8.6.4O(Mα(M, N))界254

8.7應用255

小結257

練習257

參考文獻258

第9章圖論算法260

9.1相關定義260

9.2拓撲排序262

9.3最短路徑算法264

9.3.1無權最短路徑265

9.3.2Dijkstra算法268

9.3.3具有負值邊的圖272

9.3.4無環圖272

9.3.5所有頂點之間的最短路徑274

9.3.6最短路徑實例275

9.4網絡流問題276

9.5最小生成樹281

9.5.1Prim算法282

9.5.2Kruskal算法283

9.6深度優先搜索與應用284

9.6.1無向圖285

9.6.2雙連通性286

9.6.3歐拉回路288

9.6.4有向圖291

9.6.5查找強連通分量291

9.7NP完全性簡論293

9.7.1難解問題與易解問題293

9.7.2NP問題294

9.7.3NP完全問題294

小結296

練習296

參考文獻301

第10章算法設計技術303

10.1貪心算法303

10.1.1簡單的調度問題304

10.1.2哈夫曼編碼306

10.1.3近似裝箱問題309

10.2分治算法315

10.2.1分治算法的運行時間315

10.2.2最近點對問題317

10.2.3選擇問題319

10.2.4算術問題的理論改進321

10.3動態規劃324

10.3.1用表格代替遞歸324

10.3.2矩陣乘法的運算順序326

10.3.3最優二叉查找樹328

10.3.4所有頂點之間的最短路徑331

10.4隨機算法332

10.4.1隨機數生成器333

10.4.2跳躍表336

10.4.3素數測試339

10.5回溯算法341

10.5.1收費公路重建問題341

10.5.2博弈344

小結349

練習350

參考文獻356

第11章攤還分析358

11.1一個無關的智力問題358

11.2二項隊列359

11.3斜堆362

11.4Fibonacci堆364

11.4.1切斷左式堆中的節點364

11.4.2二項隊列的懶惰合並366

11.4.3Fibonacci堆的基本操作368

11.4.4時間界的證明369

11.5伸展樹370

小結373

練習373

參考文獻375

第12章高級數據結構與實現376

12.1自頂向下伸展樹376

12.2紅黑樹382

12.2.1自底向上插入382

12.2.2自頂向下紅黑樹383

12.2.3自頂向下刪除388

12.3treap樹389

12.4後綴數組和後綴樹391

12.4.1後綴數組392

12.4.2後綴樹394

12.4.3線性時間構建後綴數組和後綴樹395

12.5kd樹404

12.6配對堆406

小結411

練習411

參考文獻414

附錄A類模板的分離式編譯416

A.1全部放入頭文件417

A.2顯式實例化417

索引419