●章計算問題
1.1計算問題及其算法
1.1.1計算問題及其描述
1.1.2算法及其描述
1.1.3偽代碼的使用約定
1.1.4算法分析
1.1.5算法運行時間的漸近表示
1.2數據結構
1.2.1什麼是數據結構
1.2.2數據結構對算法效率的影響
1.2.3字典與字典操作
1.3程序設計
1.3.1算法與程序
1.3.2數據類型的抽像與代碼通用性
1.4數據的輸入輸出
1.4.1應用問題
1.4.2標準輸入輸出
1.4.3文件輸入輸出
1.5計數問題
1。5.1簡單模擬
1.5.2加法原理和乘法原理
1.5.3計算四邊形個數
第2章數據結構基礎
2.1線性表
2.1.1線性表的鏈表表示
2.1.2對鏈表的操作
2.1.3鏈表的程序實現
2.1.4鏈表應用
2.2棧
2.2.1棧的概念及其鏈表實現
2.2.2棧的程序實現
2.2.3棧的應用
2.3隊列
2.3.1隊列的概念及其鏈表實現
2.3.2隊列的程序實現
2.3.3隊列的應用
2.4ZY.搜索樹
2.4.1二樹及其在計算機中的表示
2.4.2二搜索樹
2.4.3二搜索樹的查詢操作
2.4.4二搜素的增刪
2.4.5紅一黑樹及其性質
2.4.6紅一黑樹的操作
2.4.7紅一黑樹的程序實現
2.4.8二搜索樹的應用
2.5散列表
2.5.1直接尋址表與散列表
2.5.2用拉鏈法解決衝突
2.5.3散列表的程序實現
2.5.4散列表的應用
第3章基本算策略
3.1漸增型算法
3.1.1有序序列的合並問題
3.1.2序列的劃分問題
3.2分治算法
3.2.1歸並排序算法
3.2.2快速排序算法
3.2.3序統計與選擇問題
3.3排序問題的討論
3.3.1排序的性質
3.3.2比較型排序算法的時間復雜度
3.3.3應用
3.4堆與基於堆的優先隊列
3.4.1堆的概念及其創建
3.4.2基於二堆的優先隊列
3.4.3應用
第4章代數計算
4.1矩陣及其計算
4.1.1矩陣與向量
4.1.2矩陣的運算
4.1.3矩陣的性質
4.1.4矩陣的程序實現
4.2矩陣的LUP分解
4.2.1LUP分解法概述
4.2.2LU分解
4.2.3計算LUP分解
4.2.4程序實現
4.3解線性方程組
4.3.1前代法和回代法
4.3.2用LUP分解計算矩陣的逆
4.3.3程序實現
4.4多項式及其計算
4.4.1多項式及其表示
4.4.2多項式的運算
4.4.3FFT
4.4.4程序實現
4.5應用
4.5.1多項式的泰勒展開式
4.5.2完善序列
4.5.3函數的有理式逼近
第5章計算幾何
5.1線段的性質
5.1.1積及其應用
5.1.2向量的極角
5.1.3程序實現
5.2判斷是否存在線段相交
5.2.1算法描述與分析
5.2.2程序實現
5.3求凸殼
5.3.1Graham掃描
5.3.2程序實現
5.4求鄰近點對
5.4.1算法描述與分析
5.4.2程序實現
5.5應用
5.5.1光導管
5.5.2小邊界矩形
5.5.3德克薩斯一日遊
第6章數論算法
6.1整數的表示
6.1.1整數的表示
6.1.2整數的算術運算
6.1.3程序實現
6.1.4應用
6.2初等數論的概念
6.3大公約數
6.3.1Euclid算法
6.3.2EUCLID算法的運行時間
6.3.3Euclid算法的迭代版本
6.3.4程序實現
6.3.5應用
模運算
.1模加法和乘法
.2解模線性方程
.4應用
6.5素數檢測
6.5.1偽素數檢測
6.5.2Miller-Rabin的隨機素數檢測
6.5.3Miller-Rabin素數檢測的錯誤率
6.5.4程序實現
6.6整數分解
6.6.1Pollard的探索法
6.6.2程序實現
6.6.3應用
第7章回溯策略
7.1組合問題
7.1.1組合問題的例子
7.1.2組合問題的形式化描述
7.2組合問題的回溯算法
7.2.1解空間的樹狀結構
7.2.2解決組合問題的回溯算法
7.2.3回溯算法的框架
7.3子集樹和排列樹
7.3.1子集樹問題
7.3.2排列樹問題
7.3.3應用
7.4用回溯算法解決組合優化問題
7.4.1組合優化問題
7.4.2用回溯策略解決組合優化問題
7.4.3應用
第8章動態規劃策略
8.1組裝線調度問題
8.1.1問題描述
8.1.2算法設計與分析
8.1.3應用——牛牛玩牌
8.2長公共子序列
8.2.1問題描述
8.2.2算法設計與分析
8.2.3程序實現
8.2.4應用
8.30—1背包問題
8.3.1問題描述
8.3.2算法設計與分析
8.3.3程序實現
8.3.4應用
8.4帶權有向圖中任意兩點間的短路徑
8.4.1問題描述
8.4.2算法設計與分析
8.4.3程序實現
8.4.4應用——牛牛聚會
第9章貪婪策略
9.1活動選擇問題
9.1.1算法描述與分析
9.1.2程序實現
9.1.3貪婪算法與動態規劃
9.1.4應用——海岸雷達
9.2Huffman編碼
9.2.1算法描述與分析
9.2.2應用——RHuffman樹
……
0章圖的搜索算法
1章文本搜索
2章代碼實驗
參考文獻
本書章討論算法設計、分析的基本概念。第2章討論算法設計中常用的幾個數據結構,包括鏈表、棧、隊列、二搜索樹、散列表等。第3章討論了算法設計的基本策略:漸增策略與分支策略。~3章的內容,為讀者閱讀本書以後的內容奠定了基礎。第4章討論幾個代數計算的基本問題及其算法,包括矩陣運算、解線性方程組、多項式運算等。第5章討論幾個關於計算幾何的基本問題及其算法,包括線段的相交判斷、平面點集的凸包計算、鄰近點對問題等。第6章討論了關於整數運算的基本問題,包括大整數的表示與運算、大公約數計算、模運算、素數判定及整數因數分解等。第4~6章的內容為讀者深入學習解決各種復雜問題奠定了解決數學計算問題的基礎。第7~9章分別用回溯策略、動態規劃策略及貪婪策略研究、解決計算機應用面臨的普遍、典型的組合優化問題。0章討論圖的搜索算法及其應用,包括深度優先搜索、拓撲排序、有向圖的強連通分支計算、關節點等