數據結構與算法[瞿有甜主編書籍]

《數據結構與算法》是2015年清華大學出版社出版的圖書，作者是瞿有甜。

內容簡介

本書以數據結構基礎和算法設計方法為知識單元，系統地介紹了數據結構與算法的基本知識及套用，簡明扼要地闡釋了計算機算法的設計與分析方法。本書的主要內容包括線性表、樹、圖等基礎數據結構，同時也包括一些實用性較強的算法及高級數據結構，如並查集、伸展樹等。以經典問題算法為例，書中分類介紹了算法設計方法以及查找與排序算法等。編者結合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實戰練習

參考文獻