算法大視界

魏振鋼，男，教授，1984年6月畢業於山東大學計算機專業，1980.7―1986.6，山東大學講師，1986.6―至今，中國海洋大學教授，兼任信息化教學中心主任。
任全國高校計算機教育研究會理事，中國體育學會信息分會常務理事，青島計算機學會常務理事。
曾獲得中國海洋大學教學名師，青島市教學名師，教育部-英特爾精品課程、山東精品課程《數據結構》負責人，教育部-IBM精品課程《軟件工程》負責人。
先後主持國家自然科學基金1項，省級自然科學基金1項，主編教材1部，出版教材名稱：《數據結構》，出版社：高等教育出版社，出版時間：2011年2月。

― 目 錄 ―

第1章 緒論 / 1
1．1 何為算法 / 1
1．2 算法的特性 / 3
1．3 “敲7”遊戲 / 4
1．3．1 數據元素 / 4
1．3．2 數據的邏輯結構 / 5
1．3．3 數據的存儲結構 / 6
1．3．4 線性表的刪除 / 7
1．3．5 “敲7”遊戲的算法設計 / 9
1．4 計算機求解問題的基本步驟 / 10
1．5 總結與思考 / 11

第2章 《三體》在哪裡 / 12
2．1 怎樣找到《三體》這本書 / 12
2．2 線性表的定義及表示 / 14
2．2．1 類型定義 / 14
2．2．2 線性表的順序表示和實現 / 17
2．2．3 線性鍊錶 / 20
2．2．4 循環鍊錶 / 27
2．3 查找的定義 / 28
2．3．1 概念與術語 / 28
2．3．2 順序表的查找 / 29
2．3．3 有序表的查找 / 33
2．4 如何查找《三體》這本書 / 37
2．4．1 問題分析 / 37
2．4．2 算法設計 / 37
2．5 如何找到“小明” / 38
2．5．1 問題描述 / 38
2．5．2 問題分析 / 39
2．6 總結與思考 / 39

第3章 獎學金爭先 / 41
3．1 誰能拿到獎學金 / 41
3．2 常用排序方法介紹 / 42
3．2．1 概述 / 42
3．2．2 直接插入排序 / 43
3．2．3 起泡排序 / 46
3．2．4 快速排序 / 49
3．2．5 簡單選擇排序 / 51
3．3 獎學金競爭問題的求解 / 53
3．3．1 問題分析 / 53
3．3．2 算法分析 / 53
3．3．3 算法設計 / 54
3．4 應用 / 55
3．4．1 荷蘭國旗問題 / 55
3．4．2 貨箱移動問題 / 57
3．5 總結與思考 / 58

第4章 網上沖浪 / 59
4．1 “Web導航”問題 / 59
4．1．1 問題描述 / 59
4．1．2 問題分析 / 61
4．2 什麼是“棧” / 62
4．2．1 棧的定義 / 62
4．2．2 棧的順序表示和實現 / 64
4．2．3 棧的應用舉例 / 64
4．2．4 生活中的棧 / 67
4．3 如何實現“Web導航” / 69
4．3．1 問題分析 / 69
4．3．2 算法設計 / 71
4．4 列車調度問題 / 73
4．4．1 問題描述 / 73
4．4．2 問題分析 / 73
4．4．3 算法設計 / 74
4．5 總結與思考 / 75

第5章 “漢諾塔”的智慧 / 77
5．1 “漢諾塔”問題 / 77
5．1．1 問題描述 / 77
5．1．2 問題分析 / 78
5．2 遞歸的基本概念與應用 / 81
5．2．1 遞歸 / 81
5．2．2 遞歸函數 / 82
5．3 “漢諾塔”問題求解 / 83
5．3．1 問題分析 / 83
5．3．2 算法設計 / 84
5．4 應用 / 85
5．4．1 八皇后問題 / 85
5．4．2 快速排序 / 88
5．4．3 分蘋果問題 / 88
5．5 總結與思考 / 89

第6章 舞伴的選擇 / 91
6．1 舞伴組合 / 91
6．1．1 問題描述 / 91
6．1．2 問題分析 / 91
6．2 隊列 / 92
6．2．1 隊列的抽像數據類型定義 / 92
6．2．2 隊列的基本操作 / 93
6．2．3 生活中的隊列 / 94
6．3 舞伴組合問題求解 / 95
6．3．1 算法分析 / 95
6．3．2 算法設計 / 95
6．3．3 算法設計 / 97
6．4 消息的加密和解密 / 98
6．4．1 問題描述 / 98
6．4．2 問題分析 / 98
6．4．3 算法設計 / 99
6．5 總結與思考 / 99

第7章 愛的密碼 / 101
7．1 如何傳輸“I LOVEYOU” / 101
7．1．1 問題描述 / 101
7．1．2 問題分析 / 101
7．2 樹及二叉樹 / 102
7．2．1 樹的定義 / 102
7．2．2 二叉樹 / 104
7．3 哈夫曼樹及其哈夫曼編碼 / 110
7．3．1 哈夫曼樹 / 110
7．3．2 哈夫曼編碼 / 113
7．3．3 傳輸“I LOVE YOU”的解決方案 / 114
7．4 農夫鋸木板問題 / 117
7．4．1 問題描述 / 117
7．4．2 算法分析 / 117
7．4．3 算法設計 / 117
7．5 總結與思考 / 118

第8章 眾裡尋他千百度 / 120
8．1 微信通訊錄 / 120
8．2 動態查找表 / 121
8．2．1 二叉排序樹 / 121
8．2．2 平衡二叉樹 / 127
8．2．3 B-樹和B+樹 / 129
8．3 哈希表 / 132
8．3．1 哈希表的定義 / 132
8．3．2 哈希表的查找 / 134
8．3．3 哈希表的應用 / 134
8．4 電話通訊錄的實現 / 134
8．4．1 問題描述 / 134
8．4．2 問題分析 / 135
8．5 總結與思考 / 139

第9章 城市互連 / 140
9．1 城市公路連接問題 / 140
9．1．1 問題描述 / 140
9．1．2 問題分析 / 141
9．2 圖的基本知識 / 141
9．2．1 圖的定義和術語 / 141
9．2．2 圖的存儲結構 / 144
9．3 最小生成樹的求解 / 148
9．3．1 普里姆算法 / 148
9．3．2 克魯斯卡爾算法 / 152
9．4 城市公路連接問題的求解 / 153
9．5 應城市之間的通信線路網建設問題 / 154
9．5．1 問題描述 / 154
9．5．2 問題分析 / 154
9．6 總結與思考 / 154

第10章 地圖導航 / 155
10．1 如何去羅馬 / 156
10．1．1 問題描述 / 156
10．1．2 問題分析 / 156
10．2 如何求解最短路徑 / 157
10．2．1 從某個源點到其餘各頂點的最短路徑 / 157
10．2．2 每對頂點之間的最短路徑 / 160
10．3 如何實現去羅馬 / 163
10．4 校園導航 / 163
10．4．1 問題描述 / 163
10．4．2 問題分析 / 164
10．4．3 算法設計 / 164
10．5 總結與思考 / 167
參考文獻 / 169