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

前言
第1章算法及其復(fù)雜度.
1.1計算機與算法
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ù)組的簡單實現(xiàn)
2.1.3Java虛擬機中的棧
2.1.4棧應(yīng)用實例
2.2隊列
2.2.1隊列ADT
2.2.2基于數(shù)組的實現(xiàn)
2.2.3隊列應(yīng)用實例
2.3鏈表
2.3.1單鏈表
2.3.2基于單鏈表實現(xiàn)棧
2.3.3基于單鏈表實現(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基于雙向鏈表實現(xiàn)的雙端隊列
第3章向量.列表與序列
3.1向量與數(shù)組
3.1.1向量ADT
3.1.2基于數(shù)組的簡單實現(xiàn)
3.1.3基于可擴充數(shù)組的實現(xiàn)
3.1.4java.util,ArrayList類和java.util.Vector類
3.2列表
3.2.1基于節(jié)點的操作
3.2.2由秩到位置
3.2.3列表ADT
3.2.4基于雙向鏈表實現(xiàn)的列表
3.3序列
3.3.1序列ADT
3.3.2基于雙向鏈表實現(xiàn)序列
3.3.3基于數(shù)組實現(xiàn)序列
3.4迭代器
3.4.1迭代器ADT
3.4.2迭代器接口
3.4.3迭代器的實現(xiàn)
3.4.4Java中的列表及迭代器
第4章樹
4.1術(shù)語及性質(zhì)
4.1.1節(jié)點的深度.樹的深度與高度
4.1.2節(jié)點的度與內(nèi)部節(jié)點.外部節(jié)點
4.1.3路徑
4.1.4祖先.后代.子樹和節(jié)點的高度
4.1.5共同祖先及最低共同祖先
4.1.6有序樹.m叉樹
4.1.7二叉樹
4.1.8滿二叉樹與完全二叉樹
4.2樹ADT及其實現(xiàn)
4.2.1“父親-長子-弟弟”模型
4.2.2樹ADT
4.2.3樹的Java接口
4.2.4基于鏈表實現(xiàn)樹
4.3樹的基本算法
4.3.1getSize()——統(tǒng)計(子)樹的規(guī)模
4.3.2getHeight()——計算節(jié)點的高度
4.3.3getDepth()——計算節(jié)點的深度
4.3.4前序.后序遍歷
4.3.5層次遍歷
4.3.6樹迭代器
4.4二叉樹ADT及其實現(xiàn)
4.4.1二叉樹ADT
4.4.2二叉樹的Java接口
4.4.3二叉樹類的實現(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基于向量的實現(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接口及其實現(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用向量實現(xiàn)優(yōu)先隊列
5.5用列表實現(xiàn)優(yōu)先隊列
5.5.1基于無序列表的實現(xiàn)及分析
5.5.2基于有序列表的實現(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用堆實現(xiàn)優(yōu)先隊列
5.8.1基于堆的優(yōu)先隊列及其實現(xiàn)
5.8.2插入與上濾
5.8.3刪除與下濾
5.8.4改變?nèi)我夤?jié)點的關(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基于列表實現(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.?基于散列表實現(xiàn)映射類
6.2.8裝填因子與重散列
6.3無序詞典
6.3.1無序詞典的ADT描述
6.3.2無序詞典的Java接口
6.3.3列表式無序詞典及其實現(xiàn)
6.3.4散列表式無序詞典及其實現(xiàn)
6.4有序詞典
6.4.1全序關(guān)系與有序查找表
6.4.2二分查找
6.4.3有序詞典的ADT描述
6.4.4有序詞典的Java接口
6.4.5基于有序查找表實現(xiàn)有序
詞典
第7章查找樹
7.1二分查找樹
7.1.1定義
7.1.2查找算法
7.1.3完全查找算法
7.1.4插入算法
7.1.5刪除算法
7.1.6二分查找樹節(jié)點類的實現(xiàn)
7.1.?二分查找樹類的實現(xiàn)
7.1.8二分查找樹的平均性能
7.2AVL樹
7.2.1平衡二分查找樹
7.2.2等價二分查找樹
7.2.3等價變換
7.2.4AVL樹
7.2.5插入節(jié)點后的重平衡
7.2.6節(jié)點刪除后的重平衡
7.2.7AVL樹的Java實現(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實現(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é)點的處理
7.4.6關(guān)鍵碼的插入
7.4.7下溢節(jié)點的處理
7.4.8關(guān)鍵碼的刪除
第8章排序
8.1歸并排序
8.1.1分治策略
8.1.2時間復(fù)雜度
8.1.3歸并算法
8.1.4Mergesort的Java實現(xiàn)
8.2快速排序
8.2.1分治策略
8.2.2軸點
8.2.3劃分算法
8.2.4Quicksort的Java實現(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算法實現(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實現(xiàn)
9.4.8性能分析
9.5BM算法
9.5.1壞字符策略
9.5.2好后綴策略
9.5.3BM算法
9.5.4BM算法的Java實現(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頂點
10.2.3邊
10.3鄰接矩陣
10.3.1表示方法
10.3.2時間性能
10.3.3空間性能
10.4鄰接表
10.4.1頂點表和邊表
10.4.2頂點與鄰接邊表
10.4.3邊
lo.4.4基于鄰接表實現(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單強連通分量算法
10.6.7強連通分量分解算法
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)系圖...