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

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