數(shù)據(jù)結(jié)構(gòu)與算法

前言
第1章算法及其復(fù)雜度.
1.1計算機(jī)與算法
1.1.1過指定垂足的直角邊
1.1.2三等分線段
1.1.3排序
1.1.4算法的定義
1.2算法性能的分析與評價
1.2.1三個層次
1.2.2時間復(fù)雜度及其度量
1.2.3空間復(fù)雜度
1.3算法復(fù)雜度及其分析
1.3.1O(1)——取非極端元素
1.3.2O(logn)——進(jìn)制轉(zhuǎn)換
1.3.3O(n)——數(shù)組求和
1.3.4O(n2)——起泡排序
1.3.5O(2r)——冪函數(shù)
1.4計算模型
1.4.1可解性
1.4.2有效町解
1.4.3下界
1.5遞歸
1.5.1線性遞歸
1.5.2遞歸算法的復(fù)雜度分析
1.5.3二分遞歸
1.5.4多分支遞歸
第2章棧與隊列
2.1棧
2.1.1棧ADT
2.1.2基于數(shù)組的簡單實(shí)現(xiàn)
2.1.3Java虛擬機(jī)中的棧
2.1.4棧應(yīng)用實(shí)例
2.2隊列
2.2.1隊列ADT
2.2.2基于數(shù)組的實(shí)現(xiàn)
2.2.3隊列應(yīng)用實(shí)例
2.3鏈表
2.3.1單鏈表
2.3.2基于單鏈表實(shí)現(xiàn)棧
2.3.3基于單鏈表實(shí)現(xiàn)隊列
2.4位置
2.4.1位置ADT
2.4.2位置接口
2.5雙端隊列
2.5.1雙端隊列ADT
2.5.2雙端隊列接口
2.5.3雙向鏈表
2.5.4基于雙向鏈表實(shí)現(xiàn)的雙端隊列
第3章向量.列表與序列
3.1向量與數(shù)組
3.1.1向量ADT
3.1.2基于數(shù)組的簡單實(shí)現(xiàn)
3.1.3基于可擴(kuò)充數(shù)組的實(shí)現(xiàn)
3.1.4java.util,ArrayList類和java.util.Vector類
3.2列表
3.2.1基于節(jié)點(diǎn)的操作
3.2.2由秩到位置
3.2.3列表ADT
3.2.4基于雙向鏈表實(shí)現(xiàn)的列表
3.3序列
3.3.1序列ADT
3.3.2基于雙向鏈表實(shí)現(xiàn)序列
3.3.3基于數(shù)組實(shí)現(xiàn)序列
3.4迭代器
3.4.1迭代器ADT
3.4.2迭代器接口
3.4.3迭代器的實(shí)現(xiàn)
3.4.4Java中的列表及迭代器
第4章樹
4.1術(shù)語及性質(zhì)
4.1.1節(jié)點(diǎn)的深度.樹的深度與高度
4.1.2節(jié)點(diǎn)的度與內(nèi)部節(jié)點(diǎn).外部節(jié)點(diǎn)
4.1.3路徑
4.1.4祖先.后代.子樹和節(jié)點(diǎn)的高度
4.1.5共同祖先及最低共同祖先
4.1.6有序樹.m叉樹
4.1.7二叉樹
4.1.8滿二叉樹與完全二叉樹
4.2樹ADT及其實(shí)現(xiàn)
4.2.1“父親-長子-弟弟”模型
4.2.2樹ADT
4.2.3樹的Java接口
4.2.4基于鏈表實(shí)現(xiàn)樹
4.3樹的基本算法
4.3.1getSize()——統(tǒng)計(子)樹的規(guī)模
4.3.2getHeight()——計算節(jié)點(diǎn)的高度
4.3.3getDepth()——計算節(jié)點(diǎn)的深度
4.3.4前序.后序遍歷
4.3.5層次遍歷
4.3.6樹迭代器
4.4二叉樹ADT及其實(shí)現(xiàn)
4.4.1二叉樹ADT
4.4.2二叉樹的Java接口
4.4.3二叉樹類的實(shí)現(xiàn)
4.5二叉樹的基本算法
4.5.1getSize().getHeiglit()和getDepth()
4.5.2updateSize()
4.5.3updateHeight()
4.5.4updateDepth()
4.5.5secede()
4.5.6attachL()和attachR()
4.5.7二叉樹的遍歷
4.5.8直接前驅(qū).直接后繼的定位算法
4.6完全二叉樹的Java買現(xiàn)
4.6.1完全二叉樹的Java接口
4.6.2基于向量的實(shí)現(xiàn)
第5章優(yōu)先隊列
5.1優(yōu)先級.關(guān)鍵碼.全序關(guān)系與優(yōu)先隊列
5.2條目與比較器
5.2.1條目
5.2.2比較器
5.2.3Comparator接口及其實(shí)現(xiàn)
5.3優(yōu)先隊列ADT及其Java接口
5.3.1優(yōu)先隊列的ADT描述
5.3.2優(yōu)先隊列的Java接口
5.3.3基于優(yōu)先隊列的排序器
5.4用向量實(shí)現(xiàn)優(yōu)先隊列
5.5用列表實(shí)現(xiàn)優(yōu)先隊列
5.5.1基于無序列表的實(shí)現(xiàn)及分析
5.5.2基于有序列表的實(shí)現(xiàn)及分析
5.6選擇排序與插入排序
5.6.1選擇排序
5.6.2插入排序
5.6.3效率比較
5.7堆的定義及性質(zhì)
5.7.1堆結(jié)構(gòu)
5.7.2完全性
5.8用堆實(shí)現(xiàn)優(yōu)先隊列
5.8.1基于堆的優(yōu)先隊列及其實(shí)現(xiàn)
5.8.2插入與上濾
5.8.3刪除與下濾
5.8.4改變?nèi)我夤?jié)點(diǎn)的關(guān)鍵碼
5.8.5建堆
5.9堆排序
5.9.1直接堆排序
5.9.2就地堆排序
5.10Huffman編碼樹
5.10.1二叉編碼樹
5.10.2最優(yōu)編碼樹
5.10.3Huffman編碼與Huffman編碼樹
5.10.4Huffman編碼樹的構(gòu)造算法
5.10.5基于優(yōu)先隊列的Huffman編碼樹構(gòu)造算法
第6章映射與詞典
6.1映射..
6.1.1映射的ADT描述
6.1.2映射的Java接口
6.1.3判等器
6.1.4java.util包中的映射類
6.1.5基于列表實(shí)現(xiàn)映射類
6.2散列表
6.2.1桶及桶數(shù)組
6.2.2散列函數(shù)
6.2.3散列碼
6.2.4壓縮函數(shù)
6.2.5沖突的普遍性
6.2.6解決沖突
6.2.?基于散列表實(shí)現(xiàn)映射類
6.2.8裝填因子與重散列
6.3無序詞典
6.3.1無序詞典的ADT描述
6.3.2無序詞典的Java接口
6.3.3列表式無序詞典及其實(shí)現(xiàn)
6.3.4散列表式無序詞典及其實(shí)現(xiàn)
6.4有序詞典
6.4.1全序關(guān)系與有序查找表
6.4.2二分查找
6.4.3有序詞典的ADT描述
6.4.4有序詞典的Java接口
6.4.5基于有序查找表實(shí)現(xiàn)有序
詞典
第7章查找樹
7.1二分查找樹
7.1.1定義
7.1.2查找算法
7.1.3完全查找算法
7.1.4插入算法
7.1.5刪除算法
7.1.6二分查找樹節(jié)點(diǎn)類的實(shí)現(xiàn)
7.1.?二分查找樹類的實(shí)現(xiàn)
7.1.8二分查找樹的平均性能
7.2AVL樹
7.2.1平衡二分查找樹
7.2.2等價二分查找樹
7.2.3等價變換
7.2.4AVL樹
7.2.5插入節(jié)點(diǎn)后的重平衡
7.2.6節(jié)點(diǎn)刪除后的重平衡
7.2.7AVL樹的Java實(shí)現(xiàn)
7.3伸展樹
7.3.1數(shù)據(jù)局部性
7.3.2逐層伸展
7.3.3雙層伸展
7.3.4分?jǐn)倧?fù)雜度
7.3.5伸展樹的Java實(shí)現(xiàn)
7.3.6插入
7.3.7刪除
7.4B-樹
7.4.1分級存儲
7.4.2B-樹的定義
7.4.3關(guān)鍵碼的查找
7.4.4性能分析
7.4.5上溢節(jié)點(diǎn)的處理
7.4.6關(guān)鍵碼的插入
7.4.7下溢節(jié)點(diǎn)的處理
7.4.8關(guān)鍵碼的刪除
第8章排序
8.1歸并排序
8.1.1分治策略
8.1.2時間復(fù)雜度
8.1.3歸并算法
8.1.4Mergesort的Java實(shí)現(xiàn)
8.2快速排序
8.2.1分治策略
8.2.2軸點(diǎn)
8.2.3劃分算法
8.2.4Quicksort的Java實(shí)現(xiàn)
8.2.5時間復(fù)雜度
8.3復(fù)雜度下界
8.3.1比較樹與基于比較的算法
8.3.2下界
第9章串
9.1串及其ADT描述
9.2串模式匹配
9.2.1概念與記號
9.2.2問題
9.2.3算法效率的測試與評價
9.3蠻力算法
9.3.1算法描述
9.3.2算法實(shí)現(xiàn)
9.3.3算法分析
9.4KMP算法
9.4.1蠻力算法的改進(jìn)
9.4.2next[]表的定義及含義
9.4.3KMP算法描述
9.4.4next[]表的特殊情況
9.4.5next[]表的構(gòu)造
9.4.6next[]表的改進(jìn)
9.4.7KMP算法的Java實(shí)現(xiàn)
9.4.8性能分析
9.5BM算法
9.5.1壞字符策略
9.5.2好后綴策略
9.5.3BM算法
9.5.4BM算法的Java實(shí)現(xiàn)
9.5.5性能
第10章圖
10.1概述
10.1.1無向圖.混合圖及有向圖
10.1.2度
10.1.3簡單圖
10.1.4圖的復(fù)雜度
10.1.5子圖.生成子圖與限制子圖
10.1.6通路.環(huán)路及可達(dá)分量
10.1.7連通性.等價類與連通分量
10.1.日森林.樹以及無向圖的生成樹
10.1.9有向圖的生成樹
10.1.10帶權(quán)網(wǎng)絡(luò)
10.2抽象數(shù)據(jù)類型
10.2.1圖
10.2.2頂點(diǎn)
10.2.3邊
10.3鄰接矩陣
10.3.1表示方法
10.3.2時間性能
10.3.3空間性能
10.4鄰接表
10.4.1頂點(diǎn)表和邊表
10.4.2頂點(diǎn)與鄰接邊表
10.4.3邊
lo.4.4基于鄰接表實(shí)現(xiàn)圖結(jié)構(gòu)
10.5圖遍歷及其算法模板
10.6深度優(yōu)先遍歷
10.6.1深度優(yōu)先遍歷算法
10.6.2邊分類
10.6.3可達(dá)分量與DFS樹
10.6.4深度優(yōu)先遍歷算法模板
10.6.5可達(dá)分量算法
10.6.6單強(qiáng)連通分量算法
10.6.7強(qiáng)連通分量分解算法
10.6.8濃縮圖與弱連通性
10.7廣度優(yōu)先遍歷
10.7.1廣度優(yōu)先遍歷算法
10.7.2邊分類
10.7.3可達(dá)分量與BFS樹
10.7.4廣度優(yōu)先遍歷算法模板
10.7.5最短距離算法
10.8最佳優(yōu)先遍歷
10.8.1最佳優(yōu)先遍歷算法
10.8.2最佳優(yōu)先遍歷算法模板
10.8.3最短路徑
10.8.4最短路徑序列
10.8.5Dijkstra算法
10.8.6最小生成樹
10.8.7Prim-Jarnik算法
DSA類關(guān)系圖...