齣版者的話
譯者序
前言
第1章算法基礎知識
1.1方法
1.2算法和數據結構
1.3僞代碼
1.4算法的特點
1.4.1大O符號
1.4.2常見的運行時間函數
1.4.3可視化函數
1.5實際因素
1.6總結
練習
第2章數值算法
2.1隨機化數據
2.1.1隨機數生成
2.1.2隨機化數組
2.1.3生成不均勻分布
2.2尋找最大公約數
2.3求冪運算
2.4有關素數的運算
2.4.1尋找素數因子
2.4.2尋找素數
2.4.3素性測試
2.5進行數值積分
2.5.1矩形規則
2.5.2梯形規則
2.5.3自適應求積
2.5.4濛特卡羅積分
2.6查找零
2.7總結
練習
第3章鏈錶
3.1基本概念
3.2單鏈錶
3.2.1遍曆鏈錶
3.2.2查找單元格
3.2.3使用哨兵
3.2.4在開頭添加單元格
3.2.5在結尾添加單元格
3.2.6在某個單元格後插入單元格
3.2.7刪除單元格
3.3雙嚮鏈錶
3.4有序鏈錶
3.5鏈錶算法
3.5.1復製鏈錶
3.5.2鏈錶的插入排序
3.6鏈錶的選擇排序
3.7多綫程鏈錶
3.8循環鏈錶
3.8.1標記單元格
3.8.2使用散列錶
3.8.3鏈錶迴溯
3.8.4反轉鏈錶
3.8.5烏龜和兔子
3.8.6雙嚮鏈錶中的循環問題
3.9總結
練習
第4章數組
4.1基本概念
4.2一維數組
4.2.1查找元素
4.2.2查找最大值、最小值、平均值
4.2.3插入元素
4.2.4移除元素
4.3非零下界
4.3.1二維數組
4.3.2多維數組
4.4三角形數組
4.5稀疏數組
4.5.1找到行或列
4.5.2獲取值
4.5.3設置值
4.5.4刪除值
4.6矩陣
4.7總結
練習
第5章棧和隊列
5.1棧
5.1.1棧的鏈錶實現
5.1.2棧的數組實現
5.1.3雙嚮棧
5.1.4棧的算法
5.2隊列
5.2.1隊列的鏈錶實現
5.2.2隊列的數組實現
5.2.3專用隊列
5.3總結
練習
第6章排序
6.1時間復雜度為O（N2）的算法
6.1.1數組中的插入排序
6.1.2數組中的選擇排序
6.1.3冒泡排序
6.2時間復雜度為O（N log N）的算法
6.2.1堆排序
6.2.2快速排序
6.2.3歸並排序
6.3時間復雜度為亞O（N log N）的算法
6.3.1計數排序
6.3.2桶排序
6.4總結
練習
第7章搜索
7.1綫性搜索
7.2二分搜索
7.3插值搜索
7.4總結
練習
第8章散列錶
8.1散列錶的基礎知識
8.2鏈
8.3開放尋址
8.3.1刪除記錄
8.3.2綫性探測
8.3.3二次探測
8.3.4僞隨機探測
8.3.5雙散列
8.3.6有序散列
8.4總結
練習
第9章遞歸
9.1基礎算法
9.1.1階乘
9.1.2斐波那契數
9.1.3漢諾塔
9.2圖算法
9.2.1科赫麯綫
9.2.2希爾伯特麯綫
9.2.3謝爾賓斯基麯綫
9.2.4墊片
9.3迴溯算法
9.3.1八皇後問題
9.3.2騎士巡遊
9.4選擇與排列
9.4.1循環選擇
9.4.2重復選擇
9.4.3不重復選擇
9.4.4元素可重復的排列
9.4.5元素不重復的排列
9.5消去遞歸
9.5.1尾遞歸的消除
9.5.2存儲中間值
9.5.3一般遞歸的消除
9.6總結
練習
第10章樹
10.1樹的術語
10.2二叉樹屬性
10.3樹的錶示
10.3.1建立樹的通用方法
10.3.2構造完全樹
10.4樹的遍曆
10.4.1前序遍曆
10.4.2中序遍曆
10.4.3後序遍曆
10.4.4深度優先遍曆
10.4.5遍曆的運行時間
10.5排序樹
10.5.1添加結點
10.5.2查找結點
10.5.3刪除結點
10.6綫索樹
10.6.1建立綫索樹
10.6.2使用綫索樹
10.7特化樹算法
10.7.1動物遊戲
10.7.2錶達式求值
10.7.3四叉樹
10.7.4Trie樹
10.8總結
練習
第11章平衡樹
11.1AVL樹
11.1.1添加值
11.1.2刪除值
11.22—3樹
11.2.1添加值
11.2.2刪除值
11.3B樹
11.3.1添加值
11.3.2刪除值
11.4平衡樹變體
11.4.1自上而下的B樹
11.4.2B+樹
11.5總結
練習
第12章決策樹
12.1遊戲搜索樹
12.1.1極小化極大值算法
12.1.2初始步驟和反應
12.1.3啓發式遊戲樹
12.2搜索通用決策樹
12.2.1優化問題
12.2.2窮舉搜索
12.2.3分支界限
12.2.4決策樹的啓發式搜索
12.2.5其他決策樹問題
12.3總結
練習
第13章基本網絡算法
13.1網絡術語
13.2網絡的錶示方法
13.3網絡的遍曆
13.3.1深度優先遍曆
13.3.2廣度優先遍曆
13.3.3連通性測試
13.3.4生成樹
13.3.5最小生成樹
13.4尋找路徑
13.4.1尋找任一路徑
13.4.2標簽設置最短路徑
13.4.3標簽校正最短路徑
13.4.4任意兩點間最短路徑
13.5總結
練習
第14章更多的網絡算法
14.1拓撲排序
14.2迴路檢測
14.3地圖著色
14.3.1兩色著色
14.3.2三色著色
14.3.3色著色
14.3.4五色著色
14.3.5其他地圖著色算法
14.4最大流
14.4.1工作分配
14.4.2最小割
14.5總結
練習
第15章字符串算法
15.1括號匹配
15.1.1求算術錶達式
15.1.2構建解析樹
15.2模式匹配
15.2.1DFA
15.2.2為正則錶達式建立DFA
15.2.3NFA
15.3字符串搜索
15.4計算編輯距離
15.5總結
練習
第16章密碼學
16.1術語
16.2換位密碼
16.2.1行／列換位
16.2.2列換位
16.2.3路由加密算法
16.3替換密碼
16.3.1凱撒替換
16.3.2維吉尼亞密碼
16.3.3簡單替換密碼
16.3.4一次性密碼本
16.4分組密碼
16.4.1代換—置換網絡
16.4.2Feistel密碼
16.5公鑰加密和RSA
16.5.1歐拉函數
16.5.2在取模運算下的乘法逆元素
16.5.3一個RSA的例子
16.5.4現實思考
16.6加密技術的其他用途
16.7總結
練習
第17章復雜性理論
17.1符號
17.2復雜性分類
17.3歸約
17.3.13SAT
17.3.2二分圖匹配
17.4NP難問題
17.5檢測、報告和優化問題
17.5.1檢測≤p報告
17.5.2報告≤p優化
17.5.3報告≤p檢測
17.5.4優化≤p報告
17.6NP完全問題
17.7總結
練習
……
第18章分布式程序設計
第19章麵試難題
附錄A算法概念綜述
附錄B練習解答
索引
· · · · · · (收起)