數(shù)據(jù)結(jié)構(gòu)與算法：C++語言描述

第一部分基礎(chǔ)知識
第1章概論
1.1算法與數(shù)據(jù)結(jié)構(gòu)
1.1.1算法
1.1.2數(shù)據(jù)結(jié)構(gòu)
1.1.3數(shù)據(jù)的邏輯結(jié)構(gòu)
1.1.4數(shù)據(jù)的存儲表示
1.1.5數(shù)據(jù)結(jié)構(gòu)的運算
1.2數(shù)據(jù)抽象和抽象數(shù)據(jù)類型
1.2.1抽象、數(shù)據(jù)抽象和過程抽象
1.2.2封裝與信息隱蔽
1.2.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.2.4數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型
1.3面向?qū)ο蠓椒?br />1.3.1面向?qū)ο蠓椒ǖ挠蓙?br />1.3.2面向?qū)ο蠓椒ǖ幕舅枷?br />1.3.3面向?qū)ο蠓椒ǖ囊?br />1.3.4面向?qū)ο蠓椒ê统橄髷?shù)據(jù)
類型
1.4描述數(shù)據(jù)結(jié)構(gòu)和算法
1.4.1數(shù)據(jù)結(jié)構(gòu)的規(guī)范
1.4.2實現(xiàn)數(shù)據(jù)結(jié)構(gòu)
本章小結(jié)
習(xí)題
第2章算法基礎(chǔ)
2.1算法復(fù)雜度
2.1.1什么是好的算法
2.1.2影響程序運行時間的因素
2.1.3算法的時間復(fù)雜度
2.1.4使用程序步分析算法
2.1.5算法的空間復(fù)雜度
2.2漸近表示法
2.2.1大O記號
2.2.2Ω記號
2.2.3Θ記號
2.2.4小o記號
2.2.5算法按時間復(fù)雜度分類
2.3遞歸、歸納和遞推
2.3.1遞歸
2.3.2遞歸算法示例
2.3.3證明方法
2.3.4遞推關(guān)系
本章小結(jié)
習(xí)題
第二部分數(shù)據(jù)結(jié)構(gòu)
第3章數(shù)組和鏈表
3.1結(jié)構(gòu)和類
3.1.1結(jié)構(gòu)
3.1.2結(jié)構(gòu)表示元素
3.2數(shù)組
3.2.1一維數(shù)組
3.2.2二維數(shù)組
3.2.3多維數(shù)組
3.3鏈表
3.3.1指針
3.3.2單鏈表
3.3.3帶表頭結(jié)點的單鏈表
3.3.4單循環(huán)鏈表
3.3.5雙向鏈表
3.4采用模擬指針的鏈表
3.4.1結(jié)點結(jié)構(gòu)
3.4.2可用空間表
3.5異常處理
本章小結(jié)
習(xí)題
第4章堆棧和隊列
4.1堆棧
4.1.1堆棧ADT
4.1.2堆棧的順序表示
4.1.3堆棧的鏈接表示
4.2隊列
4.2.1隊列ADT
4.2.2隊列的順序表示
4.2.3隊列的鏈接表示
4.3表達式計算
4.3.1表達式
4.3.2中綴表達式轉(zhuǎn)換為后綴表
達式
4.3.3計算后綴表達式的值
4.4實現(xiàn)遞歸
4.4.1子程序調(diào)用和系統(tǒng)棧
4.4.2遞歸函數(shù)的性能
4.4.3尾遞歸
4.5演示與測試
本章小結(jié)
習(xí)題
第5章線性表和數(shù)組ADT
5.1線性表
5.1.1線性表ADT
5.1.2線性表的順序表示
5.1.3線性表的鏈接表示
5.1.4兩種存儲表示的比較
5.2多項式的算術(shù)運算
5.2.1多項式ADT
5.2.2多項式的鏈接表示
5.2.3項結(jié)點類
5.2.4多項式類
5.2.5多項式的輸入和輸出
5.2.6多項式相加
5.2.7重載運算符函數(shù)
5.3數(shù)組作為抽象數(shù)據(jù)類型
5.3.1數(shù)組ADT
5.3.2一維數(shù)組的C++類
5.4特殊矩陣
5.4.1對稱矩陣
5.4.2帶狀矩陣
5.5稀疏矩陣
5.5.1稀疏矩陣ADT
5.5.2稀疏矩陣的順序表示
5.5.3稀疏矩陣轉(zhuǎn)置
5.5.4稀疏矩陣的正交鏈表表示
5.5.5建立正交鏈表
5.5.6打印正交鏈表
本章小結(jié)
習(xí)題
第6章字符串和廣義表
6.1字符串
6.1.1字符串ADT
6.1.2字符串的存儲表示
6.1.3串運算的實現(xiàn)
6.1.4簡單模式匹配算法
6.1.5模式匹配的KMP算法
6.2廣義表
6.2.1廣義表的概念
6.2.2廣義表ADT
6.2.3廣義表的存儲表示
6.2.4廣義表算法
本章小結(jié)
習(xí)題
第7章樹
7.1樹的基本概念
7.1.1樹的定義
7.1.2基本術(shù)語
7.2二叉樹
7.2.1二叉樹的定義
7.2.2二叉樹的性質(zhì)
7.2.3二叉樹ADT
7.2.4二叉樹的存儲表示
7.2.5二叉樹類
7.2.6二叉樹基本運算
7.3二叉樹的遍歷
7.3.1二叉樹遍歷算法
7.3.2二叉樹遍歷的遞歸算法
7.3.3二叉樹遍歷的應(yīng)用實例
7.4二叉樹遍歷的非遞歸算法
7.4.1遍歷器類
7.4.2中序遍歷器類
7.5二叉線索樹
7.5.1二叉線索樹的定義
7.5.2構(gòu)造中序線索樹
7.5.3遍歷二叉線索樹
7.6樹和森林
7.6.1森林與二叉樹的轉(zhuǎn)換
7.6.2樹和森林的存儲表示
7.6.3樹和森林的遍歷
7.7堆和優(yōu)先權(quán)隊列
7.7.1堆
7.7.2優(yōu)先權(quán)隊列ADT
7.7.3優(yōu)先權(quán)隊列類
7.7.4實現(xiàn)優(yōu)先權(quán)隊列
7.8哈夫曼樹和哈夫曼編碼
7.8.1樹的路徑長度
7.8.2哈夫曼樹和哈夫曼算法
7.8.3哈夫曼樹類
7.8.4構(gòu)造哈夫曼樹
7.8.5哈夫曼編碼
7.9并查集和等價關(guān)系
7.9.1并查集ADT
7.9.2并查集的存儲表示
7.9.3并查集類
7.9.4函數(shù)Union和Find
7.9.5改進的函數(shù)Union和Find
7.9.6按等價關(guān)系分組
本章小結(jié)
習(xí)題
第8章集合和搜索
8.1集合和搜索
8.1.1集合和搜索的概念
8.1.2動態(tài)集ADT
8.1.3集合的表示
8.2順序搜索
8.2.1無序表的順序搜索
8.2.2有序表的順序搜索
8.2.3平均搜索長度
8.2.4自組織表
8.3二分搜索
8.3.1分治法和二分搜索
8.3.2對半搜索
8.3.3二叉判定樹
8.3.4斐波那契搜索
8.4搜索算法的時間下界
本章小結(jié)
習(xí)題
第9章動態(tài)集和搜索樹
9.1二叉搜索樹
9.1.1二叉搜索樹的定義
9.1.2二叉搜索樹的搜索
9.1.3二叉搜索樹的插入
9.1.4二叉搜索樹的刪除
9.1.5平均情況時間分析
9.2二叉平衡樹
9.2.1二叉平衡樹的定義
9.2.2二叉平衡樹類
9.2.3二叉平衡樹的平衡旋轉(zhuǎn)
9.2.4二叉平衡樹的插入
9.2.5二叉平衡樹的刪除
9.2.6二叉平衡樹的高度
9.3B-樹
9.3.1m叉搜索樹
9.3.2B-樹的定義
9.3.3B-樹的高度
9.3.4B-樹的搜索
9.3.5B-樹的插入
9.3.6B-樹的刪除
9.4鍵樹
9.4.1鍵樹的定義
9.4.2雙鏈樹
9.4.3Trie樹
9.5伸展樹
9.5.1伸展樹的伸展操作
9.5.2性能分析
本章小結(jié)
習(xí)題
第10章跳表和散列表
10.1字典
10.2跳表
10.2.1什么是跳表
10.2.2跳表類
10.2.3跳表的搜索
10.2.4跳表的插入
10.2.5跳表的刪除
10.3散列表
10.3.1散列技術(shù)
10.3.2散列函數(shù)
10.3.3拉鏈法
10.3.4開地址法
10.3.5線性探查法
10.3.6其他開地址法
10.3.7性能分析
本章小結(jié)
習(xí)題
第11章圖
11.1圖的基本概念
11.1.1圖的定義與術(shù)語
11.1.2圖ADT
11.2圖的存儲結(jié)構(gòu)
11.2.1圖的矩陣表示法
11.2.2圖的鄰接矩陣實現(xiàn)
11.2.3圖的鄰接表表示法
11.2.4圖的鄰接表實現(xiàn)
11.3圖的遍歷
11.3.1擴充的圖類
11.3.2深度優(yōu)先遍歷
11.3.3寬度優(yōu)先遍歷
11.3.4基本遍歷方法
11.4拓撲排序
11.4.1用頂點代表活動的AOV網(wǎng)
11.4.2拓撲排序算法
11.4.3拓撲排序C++程序
11.5關(guān)鍵路徑
11.5.1用邊代表活動的AOE網(wǎng)
11.5.2關(guān)鍵路徑算法
11.5.3關(guān)鍵路徑C++程序
11.6最小代價生成樹
11.6.1基本概念
11.6.2普里姆算法
11.6.3克魯斯卡爾算法
11.6.4最優(yōu)化問題和貪心法
11.6.5貪心法求解最小代價
生成樹
11.7最短路徑
11.7.1貪心法和單源最短路徑
11.7.2迪杰斯特拉算法
11.7.3所有頂點之間的最短路徑
本章小結(jié)
習(xí)題
第12章內(nèi)排序
12.1基本概念
12.2簡單排序算法
12.2.1直接插入排序
12.2.2簡單選擇排序
12.2.3冒泡排序
12.3快速排序
12.3.1分治法與快速排序
12.3.2快速排序算法
12.3.3性能分析
12.4兩路合并排序
12.4.1合并兩個有序序列
12.4.2分治法和兩路合并排序
12.4.3合并排序算法
12.4.4性能分析
12.5堆排序
12.5.1堆排序算法
12.5.2實現(xiàn)堆排序
12.5.3性能分析
12.6排序算法的時間下界
12.7基數(shù)排序
12.7.1分配排序
12.7.2基數(shù)排序算法
12.7.3實現(xiàn)基數(shù)排序
本章小結(jié)
習(xí)題
第13章文件和外排序
13.1輔助存儲器簡介
13.1.1主存儲器和輔助存儲器
13.1.2磁盤存儲器
13.2文件
13.2.1文件的基本概念
13.2.2文件的組織方式
13.3文件的索引結(jié)構(gòu)
13.3.1靜態(tài)索引結(jié)構(gòu)
13.3.2動態(tài)索引結(jié)構(gòu)
13.4外排序
13.4.1外排序的基本過程
13.4.2初始游程的生成
13.4.3多路合并
13.4.4最佳合并樹
本章小結(jié)
習(xí)題
第三部分算法設(shè)計與分析
第14章問題求解和算法設(shè)計
14.1問題求解方法
14.1.1問題和問題求解
14.1.2問題求解過程
14.1.3系統(tǒng)生命周期
14.1.4問題求解策略
14.2分治法
14.2.1一般方法
14.2.2遞推關(guān)系
14.2.3求最大、最小元
14.2.4選擇問題
14.2.5斯特拉森矩陣相乘
14.3貪心法
14.3.1一般方法
14.3.2最佳合并模式
14.3.3背包問題
14.3.4貪心法的基本要素
14.4動態(tài)規(guī)劃法
14.4.1動態(tài)規(guī)劃法的基本要素
14.4.2最優(yōu)二叉搜索樹
14.5回溯法
14.5.1一般方法
14.5.2n-皇后問題
14.5.3子集和數(shù)問題
14.6分支限界法
14.6.1一般方法
14.6.2基于上下界的分支限界法
14.6.30/1背包問題
14.6.4旅行商問題
14.7隨機算法
14.7.1基本概念
14.7.2拉斯維加斯算法
14.7.3蒙特卡羅算法
14.7.4舍伍德算法
本章小結(jié)
習(xí)題
第15章NP難度和NP完全問題
15.1基本概念
15.1.1不確定算法和可滿足性
問題
15.1.2P類和NP類問題
15.1.3NP難度和NP完全問題
15.1.4Cook定理
15.2一些典型的NP完全問題
15.2.1最大集團判定問題
15.2.2頂點覆蓋判定問題
15.2.33元CNF-可滿足性
15.2.4圖著色數(shù)判定問題
本章小結(jié)
習(xí)題
附錄
附錄A實習(xí)要求和實習(xí)題
A.1面向?qū)ο蠓椒ǜ攀?br />A.2實習(xí)目的
A.3實習(xí)要求
A.4實習(xí)步驟
A.5實習(xí)報告
A.6實習(xí)題
附錄BC++程序設(shè)計概要
B.1函數(shù)與參數(shù)傳遞
B.2動態(tài)存儲分配
B.3類與對象
B.4函數(shù)和操作符重載
B.5繼承性和派生類
B.6多態(tài)性、虛函數(shù)和動態(tài)聯(lián)編
B.7純虛函數(shù)和抽象類
B.8模板函數(shù)和模板類
B.9友元函數(shù)和友元類
附錄C專有名詞中英文對照表
參考文獻