數據結構教程

本書是為全國高等院校計算機及相關專業開設數據結構課程而精心組織和編著的一本實用教材，內容覆蓋了教育部計算機科學與技術專業碩士研究生入學統一考試的大綱要求。本書採用C++描述，強調原理闡述與應用結合，避免大段冗長代碼，並在每章 最後增加進階和最新研究成果的介紹，引導學有餘力的學生進一步自學與本章 內容相關的數據結構知識。

第1章 基礎

1.1 什麼是數據結構

1.2 程序性能分析

1.2.1 程序性能的衡量標準

1.2.2 程序的事後測試

1.2.3 時間複雜性的計算方法

1.2.4 空間複雜性的計算方法

1.2.5 計算複雜性的表示方法

1.2.6 兩種代價計算方法的比較

1.3 從抽象數據類型到C++語言描述

1.4 C++基礎知識

1.4.1 C++中的類和對象

1.4.2 C++的輸入和輸出

1.4.3 C++中的變數和常量

1.4.4 C++中的函數

1.4.5 C++中的動態存儲分配

1.4.6 C++中的繼承

1.4.7 C++中的多態性

1.4.8 其他

1.5 進階導讀

習題

第2章 線性表

2.1 線性表及其基本運算

2.1.1 線性表的定義與特點

2.1.2 線性表的基本運算

2.2 數組

2.2.1 數組的定義和特點

2.2.2 數組的類定義

2.2.3 數組的順序存儲方式

2.2.4 稀疏矩陣

2.3 線性表的順序表示——順序表

2.3.1 順序表的定義和特點

2.3.2 順序表類定義

2.3.3 順序表的插入

2.3.4 順序表的刪除

2.3.5 順序表的應用實例——用順序存儲的線性表表示多項式

2.4 線性表的鏈式表示——鏈表

2.4.1 線性鏈表的邏輯結構與建立

2.4.2 線性鏈表的類定義

2.4.3 線性鏈表的插入與刪除

2.4.4 線性鏈表的應用實例——用線性鏈表表示多項式

2.4.5 幾種變形的線性鏈表

2.4.6 雙向鏈表

2.5 進階導讀

習題

第3章 串

3.1 串的定義

3.2 串的邏輯結構和基本操作

3.3 串的存儲結構

3.3.1 串的數組存儲表示

3.3.2 串的塊鏈存儲表示

3.4 串的實現

3.4.1 串的自定義類

3.4.2 串的實現

3.5 串的模式匹配演演算法

3.5.1 BF演演算法

3.5.2 KR演演算法

3.5.3 KMP演演算法

3.5.4 BM演演算法

3.6 進階導讀

習題

第4章 棧和隊列

4.1 棧

4.1.1 棧的基本操作

4.1.2 用數組實現棧

4.1.3 用鏈表實現棧

4.1.4 棧的應用實例

4.2 隊列

4.2.1 用數組實現隊列

4.2.2 循環隊列

4.2.3 雙向隊列

4.2.4 用鏈表實現隊列

4.2.5 隊列的應用舉例

4.3 進階導讀

習題

第5章 遞歸和廣義表

5.1 遞歸的概念

5.2 遞歸轉化為非遞歸

5.3 廣義表

5.3.1 廣義表的概念與存儲結構

5.3.2 廣義表遞歸演演算法的實現

5.4 進階導讀

習題

第6章 樹、二叉樹和森林

6.1 基本概念

6.2 樹的存儲結構

6.3 樹的線性表示

6.4 樹的遍歷

6.5 二叉樹

6.6 二叉樹的存儲表示

6.7 二叉樹的各種遍歷

6.8 線索化二叉樹

6.9 堆

6.10 計算二叉樹的數目

6.11 二叉樹的應用：霍夫曼樹和霍夫曼編碼

6.12 進階導讀

習題

第7章 查找與索引

7.1 查找與索引的概念

7.2 基於順序表的查找

7.2.1 順序表

7.2.2 順序查找

7.2.3 有序順序表上的查找操作

7.3 二叉查找樹

7.3.1 二叉查找樹的結構

7.3.2 二叉查找樹上的查找

7.3.3 基於二叉查找樹的遍歷

7.3.4 最優二叉查找樹

7.3.5 動態二叉查找樹

7.4 B－樹和B+樹

7.4.1 B－樹的結構

7.4.2 B－樹的查詢

7.4.3 B－樹的插入

7.4.4 B－樹的刪除

7.4.5 B+樹

7.5 Trie樹

7.5.1 Trie樹的定義

7.5.2 Trie樹的查找

7.5.3 Trie樹的插入和刪除

7.6 Hash查找

7.6.1 Hash函數

7.6.2 解決衝突的方法

7.6.3 Hash查找的討論

7.7 進階導讀

習題

第8章 圖

8.1 圖的基本概念

8.2 圖的存儲結構

8.2.1 鄰接矩陣

8.2.2 鄰接表

8.3 圖的遍歷與求圖的連通分量

8.3.1 深度優先查找法

8.3.2 廣度優先查找法

8.3.3 求圖的連通分量

8.4 生成樹與最小（代價）生成樹

8.4.1 普里姆（Prim）演演算法

8.4.2 克魯斯卡爾（Kruskal）演演算法

8.5 最短路徑

8.5.1 求某個頂點到其他頂點的最短路徑

8.5.2 求一對頂點之間的最短路徑

8.5.3 傳遞閉包

8.6 拓撲排序

8.7 關鍵路徑

8.8 進階導讀

習題

第9章 排序

9.1 問題定義

9.2 基本排序方法

9.2.1 插入排序

9.2.2 冒泡排序

9.2.3 選擇排序

9.3 歸併排序

9.4 快速排序

9.4.1 基本演演算法

9.4.2 性能

9.4.3 快速排序的一些改進策略

9.4.4 重複值

9.5 堆排序

9.5.1 堆及其基本操作

9.5.2 堆排序

9.6 希爾排序

9.7 基數排序

9.8 內部排序方法的比較

9.9 進階導讀——中的sort()函數

習題

第10章 外部排序

10.1 外部存儲設備

10.1.1 磁帶存儲設備

10.1.2 磁碟存儲設備

10.2 外排序的基本過程

10.3 磁碟文件的外排序方法

10.4 磁帶文件的外排序方法

10.4.1 平衡合併排序

10.4.2 多階段合併排序

10.5 進階導讀

習題