數(shù)據(jù)結(jié)構(gòu)（C++語言版）

前言
第1章 數(shù)據(jù)結(jié)構(gòu)與算法概論
1.1 算法及其復(fù)雜性的概念
1.1.1 算法與程序
1.1.2 算法復(fù)雜性的概念
1.1.3 算法復(fù)雜性的漸近性態(tài)
1.2 數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型
1.3 用C++描述數(shù)據(jù)結(jié)構(gòu)與算法
1.3.1 指針和引用
1.3.2 函數(shù)與參數(shù)傳遞
1.3.3 C++的類
1.3.4 類的對象
1.3.5 模板
1.3.6 動(dòng)態(tài)存儲(chǔ)分配
1.4 遞歸
1.5 應(yīng)用舉例
習(xí)題1
實(shí)驗(yàn)1
實(shí)驗(yàn)題1.1 實(shí)系數(shù)復(fù)變多項(xiàng)式問題
實(shí)驗(yàn)題1.2 平面幾何問題
實(shí)驗(yàn)題1.3 m進(jìn)制數(shù)問題
第2章 線性表
2.1 表的基本概念
2.2 用數(shù)組實(shí)現(xiàn)表
2.3 用指針實(shí)現(xiàn)表
2.4 用間接尋址方法實(shí)現(xiàn)表
2.5 用游標(biāo)實(shí)現(xiàn)表
2.6 循環(huán)鏈表
2.7 雙鏈表
2.8 表的搜索游標(biāo)
2.9 應(yīng)用舉例
習(xí)題2
實(shí)驗(yàn)2
實(shí)驗(yàn)題2.1 實(shí)系數(shù)一元多項(xiàng)式問題
實(shí)驗(yàn)題2.2 Josephus排列問題1
實(shí)驗(yàn)題2.3 向量分類問題
實(shí)驗(yàn)題2.4 條形圖輪廓問題
實(shí)驗(yàn)題2.5 Josephus排列問題2
第3章 棧
3.1 棧的基本概念
3.2 用數(shù)組實(shí)現(xiàn)棧
3.3 用指針實(shí)現(xiàn)棧
3.4 應(yīng)用舉例
習(xí)題3
實(shí)驗(yàn)3
實(shí)驗(yàn)題3.1 車皮編序問題
實(shí)驗(yàn)題3.2 單柱Hanoi塔問題
實(shí)驗(yàn)題3.3 多棧模擬問題
實(shí)驗(yàn)題3.4 親兄弟問題
第4章 隊(duì)列
4.1 隊(duì)列的基本概念
4.2 用指針實(shí)現(xiàn)隊(duì)列
4.3 用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列
4.4 應(yīng)用舉例
習(xí)題4
實(shí)驗(yàn)4
實(shí)驗(yàn)題4.1 組隊(duì)列問題
實(shí)驗(yàn)題4.2 雙棧隊(duì)列問題
實(shí)驗(yàn)題4.3 猴子分桃問題
實(shí)驗(yàn)題4.4 逆序表問題
第5章 集合
5.1 集合的基本概念
5.2 抽象數(shù)據(jù)類型集合
5.3 用位向量實(shí)現(xiàn)集合
5.4 用鏈表實(shí)現(xiàn)集合
5.5 應(yīng)用舉例
習(xí)題5
實(shí)驗(yàn)5
實(shí)驗(yàn)題5.1 半數(shù)集問題
第6章 排序與選擇
6.1 簡單排序算法
6.1.1 冒泡排序算法
6.1.2 插入排序算法
6.1.3 選擇排序算法
6.1.4 簡單排序算法的計(jì)算復(fù)雜性
6.2 快速排序算法
6.2.1 算法基本思想及實(shí)現(xiàn)
6.2.2 算法性能分析
6.2.3 隨機(jī)快速排序算法
6.3 合并排序算法
6.3.1 算法基本思想及實(shí)現(xiàn)
6.3.2 消除遞歸
6.3.3 自然合并排序算法
6.4 線性時(shí)間排序算法
6.4.1 計(jì)數(shù)排序算法
6.4.2 桶排序算法
6.5 中位數(shù)與第k小元素
6.5.1 平均情況下的線性時(shí)間選擇算法
6.5.2 最壞情況下的線性時(shí)間選擇算法
6.6 應(yīng)用舉例
習(xí)題6
實(shí)驗(yàn)6
實(shí)驗(yàn)題6.1 交換排序問題
實(shí)驗(yàn)題6.2 DNA排序問題
實(shí)驗(yàn)題6.3 輸油管道問題
實(shí)驗(yàn)題6.4 最優(yōu)服務(wù)次序問題
第7章 樹
7.1 樹的定義
7.2 樹的遍歷
7.3 樹的表示法
7.3.1 父結(jié)點(diǎn)數(shù)組表示法
7.3.2 兒子鏈表表示法
7.3.3 左兒子右兄弟表示法
7.4 二叉樹的基本概念
7.5 二叉樹的運(yùn)算
7.6 二叉樹的實(shí)現(xiàn)
7.6.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu)
7.6.2 二叉樹的結(jié)點(diǎn)度表示法
7.6.3 用指針實(shí)現(xiàn)二叉樹
7.7 線索二叉樹
7.8 應(yīng)用舉例
習(xí)題7
實(shí)驗(yàn)7
實(shí)驗(yàn)題7.1 層序列表問題
實(shí)驗(yàn)題7.2 最近公共祖先問題
實(shí)驗(yàn)題7.3 子樹問題-
實(shí)驗(yàn)題7.4 同構(gòu)二叉樹問題
實(shí)驗(yàn)題7.5 后序中序遍歷問題
第8章 二叉搜索樹
8.1 有序集與二叉搜索樹
8.1.1 抽象數(shù)據(jù)類型字典
8.1.2 用數(shù)組實(shí)現(xiàn)字典
8.1.3 二叉搜索樹的基本概念
8.2 實(shí)現(xiàn)二叉搜索樹
8.3 平衡的二叉搜索樹AVL樹
8.3.1 AVL樹的定義和性質(zhì)
8.3.2 旋轉(zhuǎn)變換
8.3.3 AVL樹的插入與重平衡運(yùn)算
8.3.4 AVL樹的刪除與重平衡運(yùn)算
8.4 應(yīng)用舉例
習(xí)題8
實(shí)驗(yàn)8
實(shí)驗(yàn)題8.1 裝箱問題
實(shí)驗(yàn)題8.2 電路板連線問題
實(shí)驗(yàn)題8.3 辭典問題
第9章 堆與優(yōu)先隊(duì)列
9.1 優(yōu)先隊(duì)列的基本概念
9.2 用字典實(shí)現(xiàn)優(yōu)先隊(duì)列
9.3 優(yōu)先級樹和堆
9.4 用數(shù)組實(shí)現(xiàn)堆
9.5 可并優(yōu)先隊(duì)列
9.5.1 左偏樹的定義
9.5.2 用左偏樹實(shí)現(xiàn)可并優(yōu)先隊(duì)列
9.6 應(yīng)用舉例
習(xí)題9
實(shí)驗(yàn)9
實(shí)驗(yàn)題9.1 區(qū)間相交問題
實(shí)驗(yàn)題9.2 整數(shù)字典問題
實(shí)驗(yàn)題9.3 最小權(quán)語言問題
實(shí)驗(yàn)題9.4 二叉搜索堆問題
實(shí)驗(yàn)題9.5 區(qū)間覆蓋問題
第10章 散列
10.1 抽象數(shù)據(jù)類型符號表
10.2 開散列
10.3 閉散列
10.4 散列函數(shù)的效率
10.5 重新散列
10.6 應(yīng)用舉例
習(xí)題10
實(shí)驗(yàn)10
實(shí)驗(yàn)題10.1 偽隨機(jī)排列問題
實(shí)驗(yàn)題10.2 字符串散列問題
實(shí)驗(yàn)題10.3 英文文本分析問題
實(shí)驗(yàn)題10.4 最長模式串問題
第11章 并查集
11.1 并查集的基本概念
11.2 用父結(jié)點(diǎn)數(shù)組實(shí)現(xiàn)并查集
11.3 應(yīng)用舉例
習(xí)題11
實(shí)驗(yàn)11
實(shí)驗(yàn)題11.1 二進(jìn)制方程問題
實(shí)驗(yàn)題11.2 網(wǎng)絡(luò)連通問題
實(shí)驗(yàn)題11.3 朋友問題
實(shí)驗(yàn)題11.4 等價(jià)類劃分問題
第12章 圖
12.1 圖的基本概念
12.2 抽象數(shù)據(jù)類型圖
12.3 圖的表示法
12.3.1 鄰接矩陣表示法
12.3.2 鄰接表表示法
12.3.3 緊縮鄰接表
12.4 用鄰接矩陣實(shí)現(xiàn)圖
12.4.1 用鄰接矩陣實(shí)現(xiàn)賦權(quán)有向圖
12.4.2 用鄰接矩陣實(shí)現(xiàn)賦權(quán)無向圖
12.4.3 用鄰接矩陣實(shí)現(xiàn)有向圖
12.4.4 用鄰接矩陣實(shí)現(xiàn)無向圖
12.5 用鄰接表實(shí)現(xiàn)圖
12.5.1 鄰接表基類
12.5.2 用鄰接表實(shí)現(xiàn)有向圖
12.5.3 用鄰接表實(shí)現(xiàn)無向圖
12.5.4 用鄰接表實(shí)現(xiàn)賦權(quán)有向圖
12.5.5 用鄰接表實(shí)現(xiàn)賦權(quán)無向圖
12.6 圖的遍歷
12.6.1 圖的搜索游標(biāo)
12.6.2 廣度優(yōu)先搜索
12.6.3 深度優(yōu)先搜索
12.7 最短路徑算法
12.7.1 單源最短路徑算法
12.7.2 Bellman-Ford最短路徑算法
12.7.3 所有頂點(diǎn)對之間的最短路徑算法
12.8 最小支撐樹
12.8.1 最小支撐樹性質(zhì)
12.8.2 最小支撐樹的Prim算法
12.8.3 最小支撐樹的Kruskal算法
12.9 圖匹配算法
12.10 應(yīng)用舉例
習(xí)題12
實(shí)驗(yàn)12
實(shí)驗(yàn)題12.1 圖的二著色問題
實(shí)驗(yàn)題12.2 賦權(quán)有向圖中心問題
實(shí)驗(yàn)題12.3 最長簡單路徑問題
實(shí)驗(yàn)題12.4 計(jì)算機(jī)網(wǎng)絡(luò)問題
實(shí)驗(yàn)題12.5 差分約束問題
實(shí)驗(yàn)題12.6 有截止時(shí)間的工作排序問題
實(shí)驗(yàn)題12.7 無向圖的連通分支問題
參考文獻(xiàn)