數據結構與演演算法

本書以數據結構基礎和演演算法設計方法為知識單元，系統地介紹了數據結構與演演算法的基本知識及應用，簡明扼要地闡釋了計算機演演算法的設計與分析方法。本書的主要內容包括線性表、樹、圖等基礎數據結構，同時也包括一些實用性較強的演演算法及高級數據結構，如並查集、伸展樹等。以經典問題演演算法為例，書中分類介紹了演演算法設計方法以及查找與排序演演算法等。編者結合ACM國際大學生程序設計競賽的需求，對各章節知識的靈活應用進行了詳細的分析，用豐富的實例幫助讀者由淺入深、快速地掌握演演算法設計的技巧，提升演演算法設計能力。本書的演演算法全部採用C語言描述，且在DevC++中測試通過，習題安排上注重能力培養和實戰訓練的需求。

第1章緒論

1.1數據結構簡介

1.1.1數據結構課程的內容

1.1.2數據結構的基本概念和術語

1.2抽象數據類型

1.3演演算法的執行效率及其度量

1.3.1演演算法

1.3.2演演算法設計的要求

1.3.3演演算法效率的度量

1.3.4演演算法的存儲空間需求

1.4演演算法分析

1.4.1演演算法設計與分析的重要性

1.4.2一個簡單的演演算法分析設計實例

習題

ACM/ICPC實戰練習

第2章線性結構

2.1線性表

2.1.1線性表的定義

2.1.2線性表的抽象數據類型

2.1.3線性表的存儲結構

2.2線性表的順序存儲及運算實現

2.2.1順序表

2.2.2順序表上基本運算的實現

2.2.3順序表應用舉例

2.3線性表的鏈式存儲和運算實現

2.3.1單鏈表

2.3.2單鏈表上基本運算的實現

2.3.3循環鏈表

2.3.4雙向鏈表

2.3.5靜態鏈表

2.3.6單鏈表應用舉例

2.3.7線性表實現方法比較

2.4棧

2.4.1順序棧

2.4.2鏈式棧

2.4.3棧的應用舉例

2.4.4棧與遞歸

2.5隊列

2.5.1順序隊列

2.5.2鏈式隊列

2.5.3基於隊列的演演算法設計實例

2.6數組

2.6.1數組的定義

2.6.2數組的順序表示和實現

2.6.3特殊矩陣的壓縮存儲

習題

ACM/ICPC實戰練習

第3章字元串

3.1串類型定義

3.2串的表示和實現

3.2.1串的定長順序存儲結構及其基本運算實現

3.2.2串的堆存儲結構及其基本運算實現

3.2.3串的鏈式存儲結構及其基本運算實現

3.3串的模式匹配演演算法

3.3.1樸素匹配演演算法

3.3.2KMP演演算法

3.3.3基於KMP演演算法的應用舉例

習題

ACM/ICPC實戰練習

第4章樹和二叉樹

4.1樹

4.1.1樹的定義和基本術語

4.1.2樹的抽象數據類型

4.1.3樹的存儲結構

4.1.4樹的遍歷

4.1.5樹的應用

4.2二叉樹

4.2.1二叉樹的定義

4.2.2二叉樹的性質

4.2.3二叉樹的存儲結構

4.2.4表達式樹

4.2.5二叉樹的基本操作及實現

4.3遍歷二叉樹和線索二叉樹

4.3.1遍歷二叉樹

4.3.2二叉樹遍歷的非遞歸實現

4.3.3線索二叉樹

4.4樹、森林和二叉樹的轉換

4.4.1樹轉換為二叉樹

4.4.2森林轉換為二叉樹

4.4.3二叉樹轉換為樹和森林

4.5Huffman編碼樹

4.5.1最優二叉樹(Huffman樹)

4.5.2Huffman編碼

4.6二叉搜索樹

4.6.1二叉搜索樹的基本操作

4.6.2平衡二叉樹(AVL樹)

4.7伸展樹

4.7.1伸展樹的基本操作

4.7.2伸展樹的參考常式

4.8堆與優先隊列

4.8.1堆的邏輯定義

4.8.2堆的性質

4.8.3堆的基本操作

4.8.4堆的實現常式

4.9B樹和B+樹

4.9.1B樹及其查找

4.9.2B樹的插入和刪除

4.9.3B+樹

4.10樹型結構搜索演演算法應用案例

4.10.1基於二叉樹遍歷的應用

4.10.2ACM/ICPC競賽題例分析

習題

ACM/ICPC實戰練習

第5章圖論演演算法

5.1圖

5.1.1圖的定義和術語

5.1.2圖的抽象數據類型

5.1.3圖的存儲結構

5.2圖的遍歷演演算法

5.2.1深度優先搜索

5.2.2廣度優先搜索

5.2.3深度與廣度優先搜索應用

5.3圖的連通性

5.3.1無向圖的連通性

5.3.2有向圖的連通性

5.3.3生成樹和生成森林

5.3.4關節點和重連通分量

5.3.5有向圖的強連通分量

5.4有向無環圖及其應用

5.4.1有向無環圖的概念

5.4.2AOV網與拓撲排序

5.4.3AOE網與關鍵路徑

5.5最短路徑演演算法

5.5.1無權最短路徑

5.5.2Dijkstra演演算法

5.5.3具有負邊值的圖

5.5.4所有點對的最短路徑

5.6最小支撐樹

5.6.1Prim演演算法

5.6.2Kruskal演演算法

5.6.3最小生成樹演演算法應用

5.7網路流問題

5.7.1網路流的最大流問題

5.7.2網路流應用

習題

ACM/ICPC實戰練習

第6章內部排序

6.1概述

6.2基於順序比較的簡單排序演演算法

6.2.1插入排序(InsertionSort)

6.2.2冒泡排序(BubbleSort)

6.2.3直接選擇排序(DirectlySelectionSort)

6.2.4簡單排序演演算法的時間代價對比

6.3縮小增量排序方法——Shell排序(ShellSort)

6.4基於分治策略的排序

6.4.1快速排序(QuickSort)

6.4.2歸併排序(MergeSort)

6.5樹形排序方法

6.5.1堆排序(HeapSort)

6.5.2樹形選擇排序(TreeSelectSort)

6.6分配排序和基數排序

6.6.1桶式排序(BucketSort)

6.6.2基數排序(RadixSort)

6.7內部排序問題討論與分析

6.7.1常用排序演演算法性能簡要分析

6.7.2排序問題的下限

6.8排序應用舉例

習題

ACM/ICPC實戰練習

第7章文件管理和外排序

7.1外存儲器

7.1.1磁碟

7.1.2磁碟訪問時間估算

7.2外存文件的組織

7.2.1文件組織

7.2.2文件上的操作

7.2.3C語言中的文件流操作

7.3緩衝區和緩衝池

7.4外排序(ExternalSort)

7.4.1二路外排序

7.4.2多路平衡歸併的實現

7.5置換選擇排序

7.6最佳歸併樹

習題

第8章檢索與散列表

8.1檢索的基本概念

8.2基於線性表的檢索

8.2.1順序檢索

8.2.2有序表的二分檢索

8.2.3有序表的插值查找和斐波那契查找

8.2.4分塊檢索

8.3集合的檢索

8.3.1集合的數學特性

8.3.2計算機中的集合

8.4鍵樹

8.4.1基本概念

8.4.2鍵樹的存儲表示

8.4.3鍵樹相關演演算法實現

8.5散列方法及其檢索

8.5.1散列函數

8.5.2開散列方法（分離鏈接法）

8.5.3開放定址法

8.5.4散列方法的效率分析

8.6散列表及檢索的應用

習題

ACM/ICPC實戰練習

第9章演演算法設計方法

9.1演演算法設計方法概論

9.1.1常用的演演算法設計方法

9.1.2演演算法設計中的最優化問題

9.2分治法

9.2.1分治策略的思想

9.2.2高精度計算

9.2.3矩陣相乘的Strassen演演算法

9.2.4選擇問題的分治演演算法

9.2.5分治法求最近點對問題

9.2.6分治法的應用

9.3貪心法

9.3.1貪心演演算法的思想

9.3.2活動安排問題

9.3.3背包問題

9.3.4多機調度問題的近似演演算法

9.3.5任務調度問題

9.3.6貪心演演算法的應用

9.4回溯與分支限界

9.4.1回溯與分支限界簡介

9.4.2八皇后問題

9.4.301背包問題的回溯演演算法

9.4.4分支限界演演算法

9.4.5回溯與分支限界應用

9.5動態規劃法

9.5.1Fibonacci數的計算

9.5.2矩陣連乘的順序問題

9.5.3適合動態規劃演演算法的兩個條件

9.5.4最長不降子序列問題

9.5.5最長公共子序列問題

9.5.6石子合併問題

9.5.7凸多邊形最優三角剖分

習題

ACM/ICPC實戰練習

參考文獻