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

第1章 緒論
1.1 什么是數(shù)據(jù)結(jié)構(gòu)
1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義
1.1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)
1.1.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
1.1.4 數(shù)據(jù)的運(yùn)算
1.1.5 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型
1.2 算法及其描述
1.2.1 什么是算法
1.2.2 算法描述
1.3 算法分析
1.3.1 算法設(shè)計(jì)的目標(biāo)
1.3.2 算法的時(shí)間效率分析
1.3.3 算法的存儲(chǔ)空間分析
1.4 數(shù)據(jù)結(jié)構(gòu)的目標(biāo)
本章小結(jié)
練習(xí)題1
第2章 線性表
2.1 線性表的定義
2.1.1 什么是線性表
2.1.2 線性表的抽象數(shù)據(jù)類型描述
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)
2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表
2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn)
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表
2.3.2 單鏈表
2.3.3 雙鏈表
2.3.4 循環(huán)鏈表
2.4 線性表的應(yīng)用
2.4.1 求解兩個(gè)多項(xiàng)式相加問題
2.4.2 采用順序存儲(chǔ)結(jié)構(gòu)求解
2.4.3 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)求解
本章小結(jié)
練習(xí)題2
第3章 棧和隊(duì)列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)
3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)
3.1.4 棧的應(yīng)用示例
3.2 隊(duì)列
3.2.1 隊(duì)列的定義
3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)
3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)
3.2.4 隊(duì)列的應(yīng)用示例
本章小結(jié)
練習(xí)題3
第4章 串
4.1 串的基本概念
4.1.1 什么是串
4.1.2 串的抽象數(shù)據(jù)類型
4.2 串的存儲(chǔ)結(jié)構(gòu)
4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)——順序串
4.2.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈串
4.3 串的模式匹配
4.3.1 Brute-Force算法
4.3.2 KMP算法
本章小結(jié)
練習(xí)題4
第5章 數(shù)組和廣義表
5.1 數(shù)組
5.1.1 數(shù)組的基本概念
5.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)
5.1.3 特殊矩陣的壓縮存儲(chǔ)
5.2 稀疏矩陣
5.2.1 稀疏矩陣的三元組表示
5.2.2 稀疏矩陣的十字鏈表表示
5.3 遞歸
5.3.1 遞歸的定義
5.3.2 何時(shí)使用遞歸
5.3.3 遞歸模型
5.3.4 遞歸算法的設(shè)計(jì)步驟
5.3.5 遞歸算法轉(zhuǎn)換為非遞歸算法
5.4 廣義表
5.4.1 廣義表的定義
5.4.2 廣義表的存儲(chǔ)結(jié)構(gòu)
5.4.3 廣義表的運(yùn)算
本章小結(jié)
練習(xí)題5
第6章 樹和二叉樹
6.1 樹
6.1.1 樹的定義
6.1.2 樹的邏輯結(jié)構(gòu)表示方法
6.1.3 樹的基本術(shù)語
6.1.4 樹的性質(zhì)
6.1.5 樹的基本運(yùn)算
6.1.6 樹的存儲(chǔ)結(jié)構(gòu)
6.2 二叉樹
6.2.1 二叉樹的概念
6.2.2 二叉樹的性質(zhì)
6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)
6.2.4 二叉樹的遞歸算法設(shè)計(jì)
6.2.5 二叉樹的基本運(yùn)算及實(shí)現(xiàn)
6.2.6 二叉樹的遍歷
6.2.7 二叉樹的構(gòu)造
6.3 線索二叉樹
6.3.1 線索二叉樹的定義
6.3.2 線索化二叉樹
6.3.3 遍歷線索化二叉樹
6.4 哈夫曼樹
6.4.1 哈夫曼樹的定義
6.4.2 哈夫曼樹的構(gòu)造算法
6.4.3 哈夫曼編碼
6.5 二叉樹與樹、森林之間的轉(zhuǎn)換
6.5.1 樹和二叉樹的轉(zhuǎn)換
6.5.2 森林和二叉樹的轉(zhuǎn)換
本章小結(jié)
練習(xí)題6
第7章 圖
7.1 圖的基本概念
7.1.1 圖的定義
7.1.2 圖的基本術(shù)語
7.2 圖的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)
7.2.1 鄰接矩陣存儲(chǔ)方法
7.2.2 鄰接表存儲(chǔ)方法
7.3 圖的遍歷
7.3.1 什么是圖的遍歷
7.3.2 深度優(yōu)先遍歷
7.3.3 廣度優(yōu)先遍歷
7.3.4 非連通圖的遍歷
7.3.5 圖遍歷算法的應(yīng)用
7.4 生成樹和最小生成樹
7.4.1 生成樹和最小生成樹的概念
7.4.2 普里姆算法
7.4.3 克魯斯卡爾算法
7.5 最短路徑
7.5.1 路徑的概念
7.5.2 求一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑
7.5.3 求每對(duì)頂點(diǎn)之間的最短路徑
7.6 拓?fù)渑判?br />7.7 AOE網(wǎng)與關(guān)鍵路徑
本章小結(jié)
練習(xí)題7
第8章 查找
8.1 查找的基本概念
8.2 線性表的查找
8.2.1 順序查找
8.2.2 折半查找
8.2.3 索引存儲(chǔ)結(jié)構(gòu)和分塊查找
8.3 樹表的查找
8.3.1 二叉排序樹
8.3.2 平衡二叉樹
8.3.3 B-樹
8.3.4 B+樹
8.3.5 2-3-4樹
8.3.6 紅黑樹
8.4 哈希表的查找
8.4.1 哈希表的基本概念
8.4.2 哈希函數(shù)的構(gòu)造方法
8.4.3 哈希沖突的解決方法
8.4.4 哈希表的查找及性能分析
本章小結(jié)
練習(xí)題8
第9章 內(nèi)排序
9.1 排序的基本概念
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 希爾排序
9.3 交換排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 選擇排序
9.4.1 簡(jiǎn)單選擇排序
9.4.2 堆排序
9.5 歸并排序
9.6 基數(shù)排序
9.7 各種內(nèi)排序方法的比較和選擇
本章小結(jié)
練習(xí)題9
第10章 外排序
10.1 外排序概述
10.2 磁盤排序
10.2.1 磁盤排序過程
10.2.2 生成初始?xì)w并段
10.2.3 多路平衡歸并
10.2.4 最佳歸并樹
本章小結(jié)
練習(xí)題10
第11章 數(shù)據(jù)結(jié)構(gòu)和STL
11.1 STL概述
11.1.1 STL的發(fā)展和特點(diǎn)
11.1.2 C++標(biāo)準(zhǔn)庫和STL
11.1.3 什么是算法
11.1.4 什么是容器
11.1.5 什么是迭代器
11.1.6 STL和數(shù)據(jù)結(jié)構(gòu)的關(guān)系
11.2 使用STL
11.2.1 使用STL的名字空間
11.2.2 使用STL的示例
11.3 迭代器
11.3.1 自己設(shè)計(jì)迭代器
11.3.2 STL的迭代器及其使用
11.4 容器
11.4.1 順序容器
11.4.2 關(guān)聯(lián)容器
11.4.3 適配器容器
11.5 算法
11.5.1 非可變序列算法
11.5.2 可變序列算法
11.5.3 排序算法
11.5.4 通用數(shù)值算法
本章小結(jié)
練習(xí)題11
附錄A 書中部分算法清單
附錄B 部分練習(xí)題參考答案
參考文獻(xiàn)