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

前言
第1章算法及其復(fù)雜度.
1.1計(jì)算機(jī)與算法
1.1.1過(guò)指定垂足的直角邊
1.1.2三等分線(xiàn)段
1.1.3排序
1.1.4算法的定義
1.2算法性能的分析與評(píng)價(jià)
1.2.1三個(gè)層次
1.2.2時(shí)間復(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計(jì)算模型
1.4.1可解性
1.4.2有效町解
1.4.3下界
1.5遞歸
1.5.1線(xiàn)性遞歸
1.5.2遞歸算法的復(fù)雜度分析
1.5.3二分遞歸
1.5.4多分支遞歸
第2章棧與隊(duì)列
2.1棧
2.1.1棧ADT
2.1.2基于數(shù)組的簡(jiǎn)單實(shí)現(xiàn)
2.1.3Java虛擬機(jī)中的棧
2.1.4棧應(yīng)用實(shí)例
2.2隊(duì)列
2.2.1隊(duì)列ADT
2.2.2基于數(shù)組的實(shí)現(xiàn)
2.2.3隊(duì)列應(yīng)用實(shí)例
2.3鏈表
2.3.1單鏈表
2.3.2基于單鏈表實(shí)現(xiàn)棧
2.3.3基于單鏈表實(shí)現(xiàn)隊(duì)列
2.4位置
2.4.1位置ADT
2.4.2位置接口
2.5雙端隊(duì)列
2.5.1雙端隊(duì)列ADT
2.5.2雙端隊(duì)列接口
2.5.3雙向鏈表
2.5.4基于雙向鏈表實(shí)現(xiàn)的雙端隊(duì)列
第3章向量.列表與序列
3.1向量與數(shù)組
3.1.1向量ADT
3.1.2基于數(shù)組的簡(jiǎn)單實(shí)現(xiàn)
3.1.3基于可擴(kuò)充數(shù)組的實(shí)現(xiàn)
3.1.4java.util,ArrayList類(lèi)和java.util.Vector類(lèi)
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章樹(shù)
4.1術(shù)語(yǔ)及性質(zhì)
4.1.1節(jié)點(diǎn)的深度.樹(shù)的深度與高度
4.1.2節(jié)點(diǎn)的度與內(nèi)部節(jié)點(diǎn).外部節(jié)點(diǎn)
4.1.3路徑
4.1.4祖先.后代.子樹(shù)和節(jié)點(diǎn)的高度
4.1.5共同祖先及最低共同祖先
4.1.6有序樹(shù).m叉樹(shù)
4.1.7二叉樹(shù)
4.1.8滿(mǎn)二叉樹(shù)與完全二叉樹(shù)
4.2樹(shù)ADT及其實(shí)現(xiàn)
4.2.1“父親-長(zhǎng)子-弟弟”模型
4.2.2樹(shù)ADT
4.2.3樹(shù)的Java接口
4.2.4基于鏈表實(shí)現(xiàn)樹(shù)
4.3樹(shù)的基本算法
4.3.1getSize()——統(tǒng)計(jì)(子)樹(shù)的規(guī)模
4.3.2getHeight()——計(jì)算節(jié)點(diǎn)的高度
4.3.3getDepth()——計(jì)算節(jié)點(diǎn)的深度
4.3.4前序.后序遍歷
4.3.5層次遍歷
4.3.6樹(shù)迭代器
4.4二叉樹(shù)ADT及其實(shí)現(xiàn)
4.4.1二叉樹(shù)ADT
4.4.2二叉樹(shù)的Java接口
4.4.3二叉樹(shù)類(lèi)的實(shí)現(xiàn)
4.5二叉樹(shù)的基本算法
4.5.1getSize().getHeiglit()和getDepth()
4.5.2updateSize()
4.5.3updateHeight()
4.5.4updateDepth()
4.5.5secede()
4.5.6attachL()和attachR()
4.5.7二叉樹(shù)的遍歷
4.5.8直接前驅(qū).直接后繼的定位算法
4.6完全二叉樹(shù)的Java買(mǎi)現(xiàn)
4.6.1完全二叉樹(shù)的Java接口
4.6.2基于向量的實(shí)現(xiàn)
第5章優(yōu)先隊(duì)列
5.1優(yōu)先級(jí).關(guān)鍵碼.全序關(guān)系與優(yōu)先隊(duì)列
5.2條目與比較器
5.2.1條目
5.2.2比較器
5.2.3Comparator接口及其實(shí)現(xiàn)
5.3優(yōu)先隊(duì)列ADT及其Java接口
5.3.1優(yōu)先隊(duì)列的ADT描述
5.3.2優(yōu)先隊(duì)列的Java接口
5.3.3基于優(yōu)先隊(duì)列的排序器
5.4用向量實(shí)現(xiàn)優(yōu)先隊(duì)列
5.5用列表實(shí)現(xiàn)優(yōu)先隊(duì)列
5.5.1基于無(wú)序列表的實(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)先隊(duì)列
5.8.1基于堆的優(yōu)先隊(duì)列及其實(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編碼樹(shù)
5.10.1二叉編碼樹(shù)
5.10.2最優(yōu)編碼樹(shù)
5.10.3Huffman編碼與Huffman編碼樹(shù)
5.10.4Huffman編碼樹(shù)的構(gòu)造算法
5.10.5基于優(yōu)先隊(duì)列的Huffman編碼樹(shù)構(gòu)造算法
第6章映射與詞典
6.1映射..
6.1.1映射的ADT描述
6.1.2映射的Java接口
6.1.3判等器
6.1.4java.util包中的映射類(lèi)
6.1.5基于列表實(shí)現(xiàn)映射類(lèi)
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)映射類(lèi)
6.2.8裝填因子與重散列
6.3無(wú)序詞典
6.3.1無(wú)序詞典的ADT描述
6.3.2無(wú)序詞典的Java接口
6.3.3列表式無(wú)序詞典及其實(shí)現(xiàn)
6.3.4散列表式無(wú)序詞典及其實(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章查找樹(shù)
7.1二分查找樹(shù)
7.1.1定義
7.1.2查找算法
7.1.3完全查找算法
7.1.4插入算法
7.1.5刪除算法
7.1.6二分查找樹(shù)節(jié)點(diǎn)類(lèi)的實(shí)現(xiàn)
7.1.?二分查找樹(shù)類(lèi)的實(shí)現(xiàn)
7.1.8二分查找樹(shù)的平均性能
7.2AVL樹(shù)
7.2.1平衡二分查找樹(shù)
7.2.2等價(jià)二分查找樹(shù)
7.2.3等價(jià)變換
7.2.4AVL樹(shù)
7.2.5插入節(jié)點(diǎn)后的重平衡
7.2.6節(jié)點(diǎn)刪除后的重平衡
7.2.7AVL樹(shù)的Java實(shí)現(xiàn)
7.3伸展樹(shù)
7.3.1數(shù)據(jù)局部性
7.3.2逐層伸展
7.3.3雙層伸展
7.3.4分?jǐn)倧?fù)雜度
7.3.5伸展樹(shù)的Java實(shí)現(xiàn)
7.3.6插入
7.3.7刪除
7.4B-樹(shù)
7.4.1分級(jí)存儲(chǔ)
7.4.2B-樹(shù)的定義
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時(shí)間復(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時(shí)間復(fù)雜度
8.3復(fù)雜度下界
8.3.1比較樹(shù)與基于比較的算法
8.3.2下界
第9章串
9.1串及其ADT描述
9.2串模式匹配
9.2.1概念與記號(hào)
9.2.2問(wèn)題
9.2.3算法效率的測(cè)試與評(píng)價(jià)
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無(wú)向圖.混合圖及有向圖
10.1.2度
10.1.3簡(jiǎn)單圖
10.1.4圖的復(fù)雜度
10.1.5子圖.生成子圖與限制子圖
10.1.6通路.環(huán)路及可達(dá)分量
10.1.7連通性.等價(jià)類(lèi)與連通分量
10.1.日森林.樹(shù)以及無(wú)向圖的生成樹(shù)
10.1.9有向圖的生成樹(shù)
10.1.10帶權(quán)網(wǎng)絡(luò)
10.2抽象數(shù)據(jù)類(lèi)型
10.2.1圖
10.2.2頂點(diǎn)
10.2.3邊
10.3鄰接矩陣
10.3.1表示方法
10.3.2時(shí)間性能
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邊分類(lèi)
10.6.3可達(dá)分量與DFS樹(shù)
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邊分類(lèi)
10.7.3可達(dá)分量與BFS樹(shù)
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最小生成樹(shù)
10.8.7Prim-Jarnik算法
DSA類(lèi)關(guān)系圖...