用C++描述數(shù)據結構

第一章　基本概念
1.1　綜述：系統(tǒng)生命周期
1.2　面向對象程序
1.2.1　算法分解與面向對象分解
1.2.2　面向對象程序設計的基本定義和概念
1.2.3　程序設計語言的演變和C++的歷史
1.3　數(shù)據抽象和封裝
1.4　C++基礎
1.4.1　C++中的程序結構
1.4.2　C++中的作用域
1.4.3　C++中的表達式和操作符
1.4.4　C++中的數(shù)據聲明
1.4.5　C++中的注釋
1.4.6　C++中的輸入/輸出
1.4.7　C++中的函數(shù)
1.4.8　C++中的參數(shù)傳遞
1.4.9　C++中的函數(shù)名重載
1.4.10　內聯(lián)函數(shù)
1.4.11　C++中的支態(tài)存儲器分配
1.5　算法說述
1.5.1　引言
1.5.2　遞歸算法
1.6　　性能分析與測定
1.6.1性能分析
1.6.2　性能測定
1.6.3　　產生測試數(shù)據
第二章　數(shù)組
2.1　　抽象數(shù)據類型和C++類
2.1.1　C++類簡介
2.1.2　C++中的數(shù)據抽象與封裝
2.1.3　聲明類對象和調用成員函數(shù)
2.1.4　特殊的類操作
2.1.5　其他方面的概述
2.1.6　抽象數(shù)據類型(ADT)和C++的類
2.2　作為抽象數(shù)據的數(shù)組
2.3　多項式抽象數(shù)據類型
2.3.1　多項式表示
2.3.2　多項式相加
2.3.3　由數(shù)組表示多項式的缺點
2.4　稀疏矩陣
2.4.1　引言
2.4.2　稀疏矩陣的表示方式
2.4.3　矩陣的轉置
2.4.4　矩陣相乘
2.4.5　由數(shù)組表示稀疏矩陣的缺點
2.5　數(shù)組的表示
2.6　字符串抽象數(shù)據類型
2.6.1　字符串模式匹配:一種簡單算法
2.6.2　字符串模式匹配:K-M-P算法
2.7　附加練習
第三章　棧和隊列
3.1　C++中的模板
3.1.1　模板函數(shù)
3.1.2　采用模板表示包容類
3.2　棧抽象數(shù)據類型
3.3　隊列抽象數(shù)據類型
3.4　C++中的子類型和繼承
3.5　迷宮問題
3.6　表達式的計算
3.6.1　表達式
3.6.2　后綴表示法
3.6.3　中綴轉換為后綴
3.7　多棧和多隊列
3.8　附加練習
第四章　鏈表
4.1　單鏈表
4.2　用C++表示鏈表
4.2.1　用C++定義一個鏈表結點
4.2.2　用C++設計鏈表
4.2.3　C++中的指針使用
4.2.4　表處理操作
4.3　可重用的鏈表類
4.3.1　采用模板實現(xiàn)鏈表
4.3.2　鏈表重復體
4.3.3　鏈表操作
4.3.4　重用一個類
4.4　循環(huán)鏈表
4.5　鏈接棧和鏈接隊列
4.6　多項式
4.6.1　多項式表示
4.6.2　多項式相加
4.6.3　清除多項式
4.6.4　多項式的循環(huán)鏈表示
4.6.5　總結
4.7　等價類
4.8　稀疏矩陣
4.8.1　稀疏矩陣表示
4.8.2　稀疏矩陣的輸入
4.8.3　清除稀疏矩陣
4.9　雙向鏈表
4.10　廣義表
4.10.1　文義表的表示
4.10.2　鏈表的遞歸算法
4.10.3　共享鏈表\遞歸鏈表和引用數(shù)
4.11　C++中的虛函數(shù)和動態(tài)聯(lián)編
4.12　異質表
第五章　樹
5.1　引言
5.1.1　術語
5.1.2　樹的表示法
5.2　二叉樹
5.2.1　抽象數(shù)據類型
5.2.2　二叉樹的性質
5.2.3　二叉樹的表示法
5.3　二叉樹遍歷
5.3.1　引言
5.3.2　中序遍歷
5.3.3　先序遍歷
5.3.4　后序遍歷
5.3.5　選代中序遍歷
5.3.6　層序遍歷
5.3.7　不用找的遍歷
5.4　二叉樹的其他操作
5.4.1　復制二叉樹
5.4.2　測試等價性
5.4.3　可滿足性問題
5.5　線索二叉樹
5.5.1　線索
5.5.2　中序遍歷線索二叉樹
5.5.3　向線索二叉樹中插入結點
5.6　堆
5.6.1　優(yōu)先級隊列
5.6.2　最大堆的定義
5.6.3　向最大堆中插入元素
5.6.4　從最大堆中刪除元素
5.7　二叉查找樹
5.7.1　定義
5.7.2　檢索一棵二叉查找樹
5.7.3　向二叉查找樹中插入元素
5.7.4　從二叉查找樹中刪除元素
5.7.5　連接和分裂二叉樹
5.7.6　二叉查找樹的高度
5.8　選取撥樹
5.8.1　引言
5.8.2　優(yōu)勝者樹
5.8.3　失敗者樹
5.9　森林
5.9.1　把森林轉換成二叉樹
5.9.2　森林的遍歷
5.10　集合的表示方法
5.10.1　引言
5.10.2　歸并和查找操作
5.10.3　在等價類中的應用
5.11　樹數(shù)據結構的面向對象系統(tǒng)
5.12　二叉樹的計數(shù)
5.12.1　不相同的二叉樹
5.12.2　棧排列
5.12.3　矩陣乘法
5.12.4　不同二叉樹數(shù)
第六章　圖
6.1　圖抽象數(shù)據類型
6.1.1　引言
6.1.2　定義
6.1.3　圖的表示方法
6.2　圖的基本操作
6.2.1　深度優(yōu)先搜索
6.2.2　廣度優(yōu)先搜索
6.2.3　連通分量
6.2.4　生成樹
6.2.5　重連通分量
6.3　最小代價生成樹
6.3.1　克魯斯卡爾算法
6.3.2　普里姆算法
6.3.3　索林算法
6.4　最短路每項和傳遞閉包
6.4.1　邊帶非負權值時從一個源點到其余所有頂點最短路徑
6.4.2　邊帶任意權值時從一個源點到其余所有頂點的最短路徑
6.4.3　每一對頂點之間的最短路徑
6.4.4　傳遞閉包
6.5　活動網絡
6.5.1　頂點表示活動的網絡
6.5.2　邊表示活動的網絡
6.6　附加練習
第七章　排序
7.1　引言
7.2　插入排序
7.3　快速排序
7.4　排序的最小時間復雜度
7.5　歸并排序
7.5.1　歸并
7.5.2　迭代歸并排序
7.5.3　遞歸歸并排序
7.6　堆排序
7.7　對多個關鍵的排序
7.8　鏈表排序和列表排序
7.9　內部排序的總結
7.10　外部排序
7.10.1　引言
7.10.2　K-路歸并
7.10.3　對并行操作的緩沖區(qū)劃管理
7.10.4　歸并段產生
7.10.5　歸并段的最佳歸并
第八章　散列
8.1　符號表抽象數(shù)據類型
8.2　靜態(tài)散列
8.2.1　哈希表
8.2.2　哈希函數(shù)
8.2.3　溢出處理
8.2.4　溢出處理技術的理論評估
8.3　動態(tài)散列
8.3.1　引言
8.3.2　使用目錄的動態(tài)散列
8.3.3　基于目錄的動態(tài)散列方法的分析
8.3.4　無目錄的動態(tài)散列
第九章　堆結構
9.1　最?。畲蠖?br />9.1.1　定義
9.1.2　向最小－最大堆中插入元素
9.1.3　刪除最小元素
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.4.5　刪除最小元素
9.4.6　分析
9.5　斐波那契堆
9.5.1　定義
9.5.2　從F-堆中刪除結點
9.5.3　減-碼
9.5.4　級聯(lián)剪切
9.5.5　分析
9.5.6　在最短路徑問題中的應用
9.6　附加練習
第十章　查找結構
10.1　最優(yōu)二叉查找樹
10.2　AVL樹
10.3　　2-3樹
10.3.1　定義和性質
10.3.2　查找一棵2-3樹
10.3.3　向2-3樹中插入元素
10.3.4　從2-3樹中刪除元素
10.4　2-3-4樹
10.4.1　定義和性質
10.4.2　自頂向下插入
10.4.3　自頂向下刪除
10.5　　紅－黑樹
10.5.1　定義和性質
10.5.2　查找紅－黑樹
10.5.3　自頂向下插入
10.5.4　自底向上插入
10.5.5　從紅-黑樹中刪除元素
10.5.6　連接和分裂紅-黑樹
10.6　B-樹
10.6.1　m-路查找樹的定義
10.6.2　查找一棵m-路查找樹
10.6.3　B-樹的定義和性質
10.6.4　向B-樹中插入
10.6.5　從B-樹中刪除
10.6.6　可變大小的關鍵碼
10.7　扁樹
10.8　數(shù)字查找樹
10.8.1　定義
10.8.2　二叉trie樹
10.8.3　Patricia
10.9　trie樹
10.9.1　定義
10.9.2　查找一棵trie樹
10.6.3　采樣策略
10.9.4　向trie樹中插入關鍵碼
10.9.5　從trie樹中刪除關鍵碼
10.9.6　結點結構
10.10　差異文件
10.10.1　概念
10.10.2　布盧姆過濾程序