本書基于抽象數據類型的觀點講解數據結構,力圖讓讀者學會以“積木式”組件方案快速、便捷、高效地構建程序. 數據結構要為算法服務,因此本書以算法分析為導向,以算法效率為準繩,著墨于抽象數據類型的選擇、使用和組合,從而實現提升算法性能的終極目標. 全書采用 C++語言描述程序,并盡量與 C++11標準靠攏,力求緊跟程序設計語言的時代脈搏. 本書特色在于以標準模板庫(STL)高效地編寫C++程序代碼,并特別論及了各種容器的算法性能優劣,從而讓讀者能夠更好地使用 STL容器.
本書可作為高等院校計算機科學與技術等本科專業的數據結構課程教材,也可供相關專業的工程技術人員參考.
范文瀾曾云“板凳要坐十年冷”, Peter Norvig也寫過一篇異曲同工的Teach Yourself Programming in Ten Years妙文. 盡管一般人不可能用十年去培養非常專業的功底, 但我們希望在有限的課程時間內培養出學生的基本技能, 并為他們打開程序設計這扇神奇之窗.那么如何盡快學會搭建程序呢? 樂高積木為我們提供了一種很好的思路, 學生只需使用基本的“積木式”組件便可迅速完成程序設計. 抽象數據類型正是這樣的積木, 而C++的標準模板庫(STL)已為我們準備好了.在學會組建程序的基礎上, 我們要求從算法角度分析效率, 而抽象數據類型的簡約性更利于我們在宏觀上盡快給出優良的方案設計. 因此, 貫穿全書的主線是抽象數據類型的選擇、使用和組合.我們特別強調在抽象數據類型選用時必須以算法分析為導向, 以算法效率為準繩. 對于以不同抽象數據類型為要素的實現方案, 其選擇標準是完成整個方案所需的時空開銷.此外, 我們還會關注同一抽象數據類型在不同數據結構實現下的性能差異. 在上述思想指導下, 本書力求給出一種全新的模式, 讓學生盡快學會高效使用抽象數據類型, 最終為后續的算法設計課程打下堅實的基礎.
第1 章 章 算 法 法 1
11 概述 1
12 [實例] 二分查找 3
13 程序性能與算法分析 5
14 漸近記號 9
15 [技巧] 階的快速比較* 13
16 習題 18
第2 章 章 抽 象 數 據 類 型 型 19
21 概述 19
22 [實例] 在數據集中查找給定值 20
23 數據庫與數據集 25
24 功能與實現 27
25 [技巧] 組裝使用 36
26 STL容器一覽 38
27 設計模式 40
28 習題 43
第3 章 章 向 量 量 45
31 概述 45
32 [使用] vector 45
33 vector的簡要實現 48
34 加倍技術* 54
35 [技巧] 物理存儲與進制換算 56
36 [技巧] 自然數映射與下標 59
37 [實例] 矩陣的向量實現 61
38 習題 67
第4 章 章 遞 歸 歸 71
41 概述 71
42 [技巧] 遞歸設計與歸納證明 72
43 遞歸與進程模型 75
VI 目錄
44 遞歸算法性能分析 76
45 [實例] 排列生成器* 79
46 [實例] 樂高鋪磚 84
47 習題 89
第5 章 章 棧 棧 91
51 概述 91
52 [使用] stack 92
53 stack的簡要實現 94
54 [技巧] 邏輯表達式優化 97
55 [實例] 路徑搜索 104
56 習題108
第6 章 章 隊 列 列 109
61 概述109
62 [使用] queue 109
63 [技巧] 循環向量設計 111
64 queue的簡要實現114
65 [實例] 賈憲三角 121
66 [技巧] 排隊組織與內蘊次序123
67 習題124
第7 章 章 鏈 鏈 127
71 概述127
72 [使用] list 128
73 [技巧] 用于鏈接的指針 132
74 鏈的變種 137
75 list的簡要實現*138
76 [技巧] 基于歸納的初始條件選取149
77 [實例] 歸并排序 151
78 習題155
第8 章 章 二 叉 樹 樹 157
81 概述157
82 二叉樹與樹 158
83 [技巧] 二叉樹遍歷 161
84 [技巧] 遞歸處理二叉樹 165
目錄 VII
85 [實例] 二叉查找樹 168
86 習題173
第9 章 章 集 合 合 175
91 概述175
92 [使用] set與multiset175
93 [實例] 尋找寶藏 178
94 [技巧] 哨兵179
95 [技巧] 集合與序關系 182
96 [技巧] 不相交集 184
97 習題189
第10 章 章 優 先 級 隊 列 列 191
101 概述191
102 [使用] priority_queue 192
103 [技巧] 維護最大元 193
104 priority_queue的簡要實現196
105 [實例] 堆排序 200
106 [實例] Huffman編碼203
107 習題209
第11 章 章 圖 圖 211
111 概述211
112 圖的表示 213
113 圖類217
114 [技巧] 編號與反向映射 225
115 [技巧] DFS和BFS 227
116 [實例] 最短路徑* 232
117 [實例] 最小生成樹 239
118 習題246
第12 章 章 實 驗 驗 247
121 多維求和 247
122 幻方計數 249
123 隨機行走 251
124 紙牌游戲 255
125 迷宮生成 260
VIII 目錄
126 數據壓縮 261
127 會場安排 263
128 排序測試 264
附 錄A 頭 文 件 件 269
A1 計時類 269
A2 bookh270
附 錄B 中 文 參 考 書 目 目 275
B1 國內數據結構教材275
B2 數據結構教材(翻譯版)275
B3 算法教材(翻譯版) 276
英 文 參 考 文 獻 獻 277