用C++描述數(shù)據(jù)結(jié)構(gòu)

第一章　基本概念
1.1　綜述：系統(tǒng)生命周期
1.2　面向?qū)ο蟪绦?br />1.2.1　算法分解與面向?qū)ο蠓纸?br />1.2.2　面向?qū)ο蟪绦蛟O(shè)計(jì)的基本定義和概念
1.2.3　程序設(shè)計(jì)語言的演變和C++的歷史
1.3　數(shù)據(jù)抽象和封裝
1.4　C++基礎(chǔ)
1.4.1　C++中的程序結(jié)構(gòu)
1.4.2　C++中的作用域
1.4.3　C++中的表達(dá)式和操作符
1.4.4　C++中的數(shù)據(jù)聲明
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　內(nèi)聯(lián)函數(shù)
1.4.11　C++中的支態(tài)存儲(chǔ)器分配
1.5　算法說述
1.5.1　引言
1.5.2　遞歸算法
1.6　　性能分析與測定
1.6.1性能分析
1.6.2　性能測定
1.6.3　　產(chǎn)生測試數(shù)據(jù)
第二章　數(shù)組
2.1　　抽象數(shù)據(jù)類型和C++類
2.1.1　C++類簡介
2.1.2　C++中的數(shù)據(jù)抽象與封裝
2.1.3　聲明類對象和調(diào)用成員函數(shù)
2.1.4　特殊的類操作
2.1.5　其他方面的概述
2.1.6　抽象數(shù)據(jù)類型(ADT)和C++的類
2.2　作為抽象數(shù)據(jù)的數(shù)組
2.3　多項(xiàng)式抽象數(shù)據(jù)類型
2.3.1　多項(xiàng)式表示
2.3.2　多項(xiàng)式相加
2.3.3　由數(shù)組表示多項(xiàng)式的缺點(diǎn)
2.4　稀疏矩陣
2.4.1　引言
2.4.2　稀疏矩陣的表示方式
2.4.3　矩陣的轉(zhuǎn)置
2.4.4　矩陣相乘
2.4.5　由數(shù)組表示稀疏矩陣的缺點(diǎn)
2.5　數(shù)組的表示
2.6　字符串抽象數(shù)據(jù)類型
2.6.1　字符串模式匹配:一種簡單算法
2.6.2　字符串模式匹配:K-M-P算法
2.7　附加練習(xí)
第三章　棧和隊(duì)列
3.1　C++中的模板
3.1.1　模板函數(shù)
3.1.2　采用模板表示包容類
3.2　棧抽象數(shù)據(jù)類型
3.3　隊(duì)列抽象數(shù)據(jù)類型
3.4　C++中的子類型和繼承
3.5　迷宮問題
3.6　表達(dá)式的計(jì)算
3.6.1　表達(dá)式
3.6.2　后綴表示法
3.6.3　中綴轉(zhuǎn)換為后綴
3.7　多棧和多隊(duì)列
3.8　附加練習(xí)
第四章　鏈表
4.1　單鏈表
4.2　用C++表示鏈表
4.2.1　用C++定義一個(gè)鏈表結(jié)點(diǎn)
4.2.2　用C++設(shè)計(jì)鏈表
4.2.3　C++中的指針使用
4.2.4　表處理操作
4.3　可重用的鏈表類
4.3.1　采用模板實(shí)現(xiàn)鏈表
4.3.2　鏈表重復(fù)體
4.3.3　鏈表操作
4.3.4　重用一個(gè)類
4.4　循環(huán)鏈表
4.5　鏈接棧和鏈接隊(duì)列
4.6　多項(xiàng)式
4.6.1　多項(xiàng)式表示
4.6.2　多項(xiàng)式相加
4.6.3　清除多項(xiàng)式
4.6.4　多項(xiàng)式的循環(huán)鏈表示
4.6.5　總結(jié)
4.7　等價(jià)類
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ù)和動(dòng)態(tài)聯(lián)編
4.12　異質(zhì)表
第五章　樹
5.1　引言
5.1.1　術(shù)語
5.1.2　樹的表示法
5.2　二叉樹
5.2.1　抽象數(shù)據(jù)類型
5.2.2　二叉樹的性質(zhì)
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　復(fù)制二叉樹
5.4.2　測試等價(jià)性
5.4.3　可滿足性問題
5.5　線索二叉樹
5.5.1　線索
5.5.2　中序遍歷線索二叉樹
5.5.3　向線索二叉樹中插入結(jié)點(diǎn)
5.6　堆
5.6.1　優(yōu)先級(jí)隊(duì)列
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　把森林轉(zhuǎn)換成二叉樹
5.9.2　森林的遍歷
5.10　集合的表示方法
5.10.1　引言
5.10.2　歸并和查找操作
5.10.3　在等價(jià)類中的應(yīng)用
5.11　樹數(shù)據(jù)結(jié)構(gòu)的面向?qū)ο笙到y(tǒng)
5.12　二叉樹的計(jì)數(shù)
5.12.1　不相同的二叉樹
5.12.2　棧排列
5.12.3　矩陣乘法
5.12.4　不同二叉樹數(shù)
第六章　圖
6.1　圖抽象數(shù)據(jù)類型
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　最小代價(jià)生成樹
6.3.1　克魯斯卡爾算法
6.3.2　普里姆算法
6.3.3　索林算法
6.4　最短路每項(xiàng)和傳遞閉包
6.4.1　邊帶非負(fù)權(quán)值時(shí)從一個(gè)源點(diǎn)到其余所有頂點(diǎn)最短路徑
6.4.2　邊帶任意權(quán)值時(shí)從一個(gè)源點(diǎn)到其余所有頂點(diǎn)的最短路徑
6.4.3　每一對頂點(diǎn)之間的最短路徑
6.4.4　傳遞閉包
6.5　活動(dòng)網(wǎng)絡(luò)
6.5.1　頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)
6.5.2　邊表示活動(dòng)的網(wǎng)絡(luò)
6.6　附加練習(xí)
第七章　排序
7.1　引言
7.2　插入排序
7.3　快速排序
7.4　排序的最小時(shí)間復(fù)雜度
7.5　歸并排序
7.5.1　歸并
7.5.2　迭代歸并排序
7.5.3　遞歸歸并排序
7.6　堆排序
7.7　對多個(gè)關(guān)鍵的排序
7.8　鏈表排序和列表排序
7.9　內(nèi)部排序的總結(jié)
7.10　外部排序
7.10.1　引言
7.10.2　K-路歸并
7.10.3　對并行操作的緩沖區(qū)劃管理
7.10.4　歸并段產(chǎn)生
7.10.5　歸并段的最佳歸并
第八章　散列
8.1　符號(hào)表抽象數(shù)據(jù)類型
8.2　靜態(tài)散列
8.2.1　哈希表
8.2.2　哈希函數(shù)
8.2.3　溢出處理
8.2.4　溢出處理技術(shù)的理論評估
8.3　動(dòng)態(tài)散列
8.3.1　引言
8.3.2　使用目錄的動(dòng)態(tài)散列
8.3.3　基于目錄的動(dòng)態(tài)散列方法的分析
8.3.4　無目錄的動(dòng)態(tài)散列
第九章　堆結(jié)構(gòu)
9.1　最?。畲蠖?br />9.1.1　定義
9.1.2　向最?。畲蠖阎胁迦朐?br />9.1.3　刪除最小元素
9.2　雙端堆
9.2.1　定義
9.2.2　向雙端堆中插入元素
9.2.3　刪除最小元素
9.3　左樹
9.4　二項(xiàng)堆
9.4.1　代價(jià)分?jǐn)?br />9.4.2　二項(xiàng)堆的定義
9.4.3　向二項(xiàng)堆中插入元素
9.4.4　結(jié)合兩個(gè)二項(xiàng)堆
9.4.5　刪除最小元素
9.4.6　分析
9.5　斐波那契堆
9.5.1　定義
9.5.2　從F-堆中刪除結(jié)點(diǎn)
9.5.3　減-碼
9.5.4　級(jí)聯(lián)剪切
9.5.5　分析
9.5.6　在最短路徑問題中的應(yīng)用
9.6　附加練習(xí)
第十章　查找結(jié)構(gòu)
10.1　最優(yōu)二叉查找樹
10.2　AVL樹
10.3　　2-3樹
10.3.1　定義和性質(zhì)
10.3.2　查找一棵2-3樹
10.3.3　向2-3樹中插入元素
10.3.4　從2-3樹中刪除元素
10.4　2-3-4樹
10.4.1　定義和性質(zhì)
10.4.2　自頂向下插入
10.4.3　自頂向下刪除
10.5　　紅－黑樹
10.5.1　定義和性質(zhì)
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-樹的定義和性質(zhì)
10.6.4　向B-樹中插入
10.6.5　從B-樹中刪除
10.6.6　可變大小的關(guān)鍵碼
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樹中插入關(guān)鍵碼
10.9.5　從trie樹中刪除關(guān)鍵碼
10.9.6　結(jié)點(diǎn)結(jié)構(gòu)
10.10　差異文件
10.10.1　概念
10.10.2　布盧姆過濾程序