前言
目錄
44 種演算法
22 個經典問題
第 1 章 從資料到演算法
1.1 資料與資料結構
1.1.1 資料及其類型
1.1.2 資料結構簡介
1.2 演算法
1.2.1 演算法的概念
1.2.2 演算法的分析
1.2.3 演算法的設計
1.3 C++中的STL
1.3.1 STL 簡介
1.3.2 STL 的組成
1.3.3 STL 的不同版本
參考文獻
第 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.2.4 陣列的抽象資料類型
2.3 陣列應用舉例
2.3.1 Z 字形編排問題
2.3.2 大整數乘法問題
2.3.3 九宮格問題
2.4 動態記憶體管理
2.4.1 關鍵字new 和delete
2.4.2 避免記憶體錯誤
參考文獻
第 3 章 字串與模式比對——夢裡尋她千百度
3.1 基本概念與定義
3.1.1 C++中的字串
3.1.2 字串抽象資料類型
3.2 文字的精確比對
3.2.1 BF 演算法
3.2.2 MP 演算法
3.2.3 KMP 演算法
3.2.4 BM 演算法
3.2.5 BMH 演算法
3.3 文字的模糊比對
3.3.1 全域編輯距離
3.3.2 局部最佳對準
3.3.3 N 元距離模型
3.3.4 語音編碼模型
參考文獻
第 4 章 連結串列——老鷹捉小雞
4.1 連結串列的概念
4.2 單向連結串列
4.2.1 單向連結串列的結構
4.2.2 單向連結串列的操作演算法
4.2.3 有序連結串列的合併演算法
4.3 單向迴圈連結串列
4.3.1 單向迴圈連結串列的結構
4.3.2 單向迴圈連結串列的實現
4.3.3 約瑟夫環的問題
4.3.4 魔術師發牌問題
4.3.5 拉丁方陣問題
4.4 雙向迴圈連結串列
4.4.1 雙向迴圈連結串列的結構
4.4.2 雙向迴圈連結串列的實現
4.4.3 維吉尼亞加密法問題
4.5 游標類別的設計與實現
4.5.1 游標類別的結構
4.5.2 游標類別的實現
4.6 STL 與連結串列
4.6.1 STL 中連結串列類別的介面
4.6.2 巡訪
4.6.3 元素的插入與刪除
參考文獻
第 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.2.4 楊輝三角問題
5.2.5 遊程編碼問題
5.3 優先佇列——兼談頁面置換演算法
5.3.1 優先佇列的結構
5.3.2 優先佇列的實現
5.4 STL 的堆疊與佇列
5.4.1 STL 的stack
5.4.2 STL 的queue
5.4.3 STL 的priority_queue
參考文獻
第 6 章 遞迴——老和尚講故事
6.1 遞迴的概念
6.1.1 定義
6.1.2 應用遞迴的原則
6.1.3 遞迴和非遞迴的轉換
6.2 分治法
6.2.1 分治法簡述
6.2.2 河內塔問題
6.2.3 傳染病問題
6.3 回溯法
6.3.1 回溯法簡述
6.3.2 迷宮問題
6.3.3 八皇后問題
參考文獻
第 7 章 樹——從紅樓夢說起
7.1 認識樹狀結構
7.1.1 基本定義
7.1.2 術語解釋
7.1.3 樹的抽象
7.2 花開二枝分外香——二元樹及相關演算法
7.2.1 二元樹的定義
7.2.2 二元樹的性質
7.2.3 二元樹的實現
7.2.4 二元樹的巡訪演算法
7.2.5 二元樹線索化演算法
7.3 合抱之木，生於毫末——從樹到森林
7.3.1 樹的儲存表示
7.3.2 樹的實現
7.3.3 樹與森林的巡訪演算法
7.3.4 森林與二元樹的轉換
7.4 霍夫曼樹——最佳二元樹編碼演算法
7.4.1 霍夫曼編碼
7.4.2 建構霍夫曼樹
7.4.3 霍夫曼編碼的實現
7.5 堆積
7.5.1 堆積的概念
7.5.2 堆積的建立
7.5.3 堆積的操作
7.6 基於STL 實現樹結構
7.6.1 STL 中的vector
7.6.2 STL 的map
參考文獻
第 8 章 圖——始於柯尼斯堡的七橋問題
8.1 圖的基本概念
8.1.1 圖的定義
8.1.2 圖的術語
8.1.3 圖的運算
8.1.4 圖的抽象資料類型
8.2 圖的儲存與表示
8.2.1 圖的鄰接矩陣
8.2.2 圖的鄰接表
8.2.3 兩種標記法的比較
8.3 圖的巡訪
8.3.1 歐拉路徑與歐拉迴路
8.3.2 哈密頓路徑與哈密頓迴路
8.3.3 廣度優先巡訪演算法
8.3.4 深度優先巡訪演算法
8.4 最短路徑問題
8.4.1 固定起點最短路徑問題
8.4.2 非固定起點最短路徑問題
8.5 最小生成樹
8.5.1 最小生成樹的定義
8.5.2 克魯斯克爾演算法
8.5.3 普林演算法
參考文獻
第 9 章 樹狀搜索結構——做一名出色的園藝師
9.1 二元搜尋樹
9.1.1 二元搜尋樹的概念
9.1.2 二元搜尋樹的操作
9.1.3 二元搜尋樹的實現
9.1.4 二元搜尋樹的分析
9.2 自平衡的二元搜尋樹——AVL 樹
9.2.1 AVL 樹的概念
9.2.2 AVL 樹的旋轉
9.2.3 AVL 樹的實現
9.3 樹中亦有「紅與黑」
9.3.1 紅黑樹的概念
9.3.2 紅黑樹的操作
9.3.3 紅黑樹的實現
9.4 基於Trie 樹的單字檢索
9.4.1 Trie 樹的概念
9.4.2 Trie 樹的表示
9.4.3 Trie 樹的實現
參考文獻
第 10 章 集合與字典——再論搜索之話題
10.1 集合論基礎
10.1.1 集合的概念
10.1.2 集合的運算
10.2 集合的實現
10.2.1 位置向量集合
10.2.2 單向連結串列集合
10.3 字典
10.3.1 字典的概念
10.3.2 搜索運算
10.4 雜湊
10.4.1 雜湊的概念
10.4.2 雜湊函數
10.4.3 字串雜湊
10.4.4 處理雜湊衝突
10.5 拼寫檢查問題
10.6 不交集
10.6.1 不交集的概念
10.6.2 不交集的實現
10.6.3 犯罪團伙的問題
10.6.4 路徑壓縮的實現
10.7 STL 中的set
參考文獻
第 11 章 排序——有序讓世界更美好
11.1 排序問題概述
11.1.1 基本概念和定義
11.1.2 排序演算法的分類
11.1.3 排序演算法的分析
11.2 插入排序
11.2.1 直接插入排序
11.2.2 二分插入排序
11.2.3 希爾排序
11.3 選擇排序
11.3.1 直接選擇排序
11.3.2 堆排序
11.4 交換排序
11.4.1 氣泡排序
11.4.2 雞尾酒排序
11.4.3 快速排序
11.5 合併排序
11.6 計數排序
參考文獻
附錄A 經典求職面試題目
?
