目錄
第1章 Collections類、泛型類和Timing類概述 1
1.1 群集的定義 1
1.2 群集的描述 1
1.2.1 直接存取群集 2
1.2.2 順序存取群集 4
1.2.3 層次群集 6
1.2.4 組群集 7
1.3 CollectionBase類 8
1.3.1 用ArrayList實現Collection類 8
1.3.2 定義Collection類 8
1.3.3 實現Collection類 8
1.4 泛型編程 10
1.5 時間測試 12
1.5.1 一個簡單化的時間測試 12
1.5.2 用於.Net環境的時間測試 13
1.5.3 Timing Test類 14
小結 16
練習 17
第2章 數組和ArrayList 18
2.1 數組基本概念 18
2.1.1 數組的聲明和初始化 18
2.1.2 數組元素的設置和存取訪問 19
2.1.3 檢索數組元數據的方法和屬性 19
2.1.4 多維數組 20
2.1.5 參數數組 21
2.1.6 鋸齒狀數組 22
2.2 ArrayList類 23
2.2.1 ArrayList類的成員 23
2.2.2 應用ArrayList類 24
小結 27
練習 27
第3章 基礎排序算法 29
3.1 排序算法 29
3.1.1 數組類測試環境 29
3.1.2 冒泡排序 31
3.1.3 檢驗排序過程 32
3.1.4 選擇排序 33
3.1.5 插入排序 35
3.2 基礎排序算法的時間比較 36
小結 37
練習 38
第4章 基礎查找算法 39
4.1 順序查找 39
4.1.1 查找最小值和最大值 41
4.1.2 自組織數據加快順序查找速度 42
4.2 二叉查找算法 43
4.3 遞歸二叉查找算法 45
小結 47
練習 47
第5章 棧和隊列 48
5.1 棧、棧的實現以及Stack類 48
5.1.1 棧的操作 48
5.1.2 Stack類的實現 49
5.2 Stack類 51
5.2.1 Stack構造器方法 51
5.2.2 主要的棧操作 52
5.2.3 Peek方法 54
5.2.4 Clear方法 54
5.2.5 Contains方法 54
5.2.6 CopyTo方法和ToArray方法 54
5.2.7 Stack類的實例：十進制向多種進制的轉換 55
5.3 隊列、Queue類以及Queue類的實現 56
5.3.1 隊列的操作 56
5.3.2 Queue的實現 57
5.3.3 Queue類：實例應用 58
5.3.4 用隊列排序數據 61
5.3.5 源自Queue類的優先隊列 64
小結 65
練習 66
第6章 BitArray類 67
6.1 激發的問題 67
6.2 位和位操作 68
6.2.1 二進制數制系統 68
6.2.2 處理二進制數：按位運算符和移位運算符 69
6.3 按位運算符的應用 70
6.4 整數轉換成二進制形式的應用程序 74
6.5 移位的示例應用程序 76
6.6 BitArray類 78
6.6.1 使用BitArray類 78
6.6.2 更多BitArray類的方法和屬性 81
6.7 用BitArray來編寫埃拉托斯特尼篩法 81
6.8 BitArray與數組在埃拉托斯特尼篩法上的比較 83
小結 83
練習 84
第7章 字符串、String類和StringBuilder類 85
7.1 String類的應用 85
7.1.1 創建String對象 85
7.1.2 常用的String類方法 86
7.1.3 Split方法和Join方法 88
7.1.4 比較字符串的方法 90
.
7.1.5 處理字符串的方法 92
7.2 StringBuilder類 98
7.2.1 構造StringBuilder對象 98
7.2.2 獲取並且設置關於StringBuilder對象的信息 98
7.2.3 修改StringBuilder對象 99
7.3 String類與StringBuilder的性能比較 101
小結 103
練習 103
第8章 模式匹配和文本處理 105
8.1 正則表達式概述 105
8.2 數量詞 107
8.3 使用字符類 109
8.4 用斷言修改正則表達式 111
8.5 使用分組構造 112
8.5.1 匿名組 112
8.5.2 命名組 112
8.5.3 零寬度正向預搜索斷言和零寬度反向預搜索斷言 113
8.6 CapturesCollection類 114
8.7 正則表達式的選項 115
小結 116
練習 116
第9章 構建字典：DictionaryBase類和SortedList類 117
9.1 DictionaryBase類 117
9.1.1 DictionaryBase類的基礎方法和屬性 117
9.1.2 其他的DictionaryBase方法 119
9.2 泛型KeyValuePair類 121
9.3 SortedList類 122
小結 123
練習 123
第10章 散列和Hashtable類 125
10.1 散列概述 125
10.2 選擇散列函數 125
10.3 查找散列表中數據 127
10.4 解決沖突 128
10.4.1 桶式散列法 128
10.4.2 開放定址法 129
10.4.3 雙重散列法 130
10.5 Hashtable類 130
10.5.1 實例化Hashtable對象並且給其添加數據 130
10.5.2 從散列表中分別檢索鍵和數值 131
10.5.3 檢索基於鍵的數值 132
10.5.4 Hashtable類的實用方法 133
10.6 Hashtable的應用：計算機術語表 133
小結 136
練習 136
第11章 鏈表 137
11.1 數組存在的問題 137
11.2 鏈表的定義 137
11.3 面向對象鏈表的設計 138
11.3.1 Node類 138
11.3.2 LinkedList類 139
11.4 鏈表設計的改進方案 141
11.4.1 雙向鏈表 141
11.4.2 循環鏈表 143
11.5 使用Iterator類 146
11.5.1 新的LinkedList類 148
11.5.2 實例化Iterator類 148
11.6 泛型Linked List類和泛型Node類 152
小結 154
練習 154
第12章 二叉樹和二叉查找樹 155
12.1 樹的定義 155
12.2 二叉樹 156
12.2.1 構造二叉查找樹 157
12.2.2 遍歷二叉查找樹 159
12.2.3 在二叉查找樹中查找節點和最大/最小值 161
12.2.4 從二叉查找樹中移除葉子節點 162
12.2.5 刪除帶有一個子節點的節點 163
12.2.6 刪除帶有兩個子節點的節點 164
小結 167
練習 167
第13章 集合 169
13.1 集合的基礎定義、操作及屬性 169
13.1.1 集合的定義 169
13.1.2 集合的操作 169
13.1.3 集合的屬性 169
13.2 第一個用散列表的Set類的實現 170
13.2.1 類數據成員和構造器方法 170
13.2.2 Add方法 170
13.2.3 Remove方法和Size方法 171
13.2.4 Union方法 171
13.2.5 Intersection方法 172
13.2.6 Subset方法 172
13.2.7 Difference方法 172
13.2.8 測試CSet實現的程序 173
13.3 CSet類的BitArray實現 174
13.3.1 使用BitArray實現的概述 174
13.3.2 BitArray集合的實現 175
小結 177
練習 177
第14章 高級排序算法 178
14.1 希爾排序算法 178
14.2 歸並排序算法 179
14.3 堆排序算法 182
14.4 快速排序算法 185
14.4.1 快速排序算法的描述 186
14.4.2 快速排序算法的代碼 187
14.4.3 快速排序算法的改進 188
小結 188
練習 188
第15章 用於查找的高級數據結構和算法 189
15.1 AVL樹 189
15.1.1 AVL樹的基本原理 189
15.1.2 AVL樹的實現 190
15.2 紅黑樹 192
15.2.1 紅黑樹規則 192
15.2.2 紅黑樹的插入 193
15.2.3 紅黑樹實現代碼 194
15.3 跳躍表 198
15.3.1 跳躍表的基本原理 198
15.3.2 跳躍表的實現 199
小結 203
練習 203
第16章 圖和圖的算法 204
16.1 圖的定義 204
16.2 由圖模擬真實世界系統 205
16.3 圖類 205
16.3.1 頂點的表示 205
16.3.2 邊的表示 206
16.3.3 圖的構造 206
16.3.4 圖的第一個應用：拓撲排序 208
16.3.5 拓撲排序算法 208
16.3.6 拓撲排序算法的實現 208
16.4 圖的搜索 211
16.4.1 深度優先搜索 211
16.4.2 廣度優先搜索 213
16.5 最小生成樹 215
16.6 查找最短路徑 218
16.6.1 加權圖 218
16.6.2 確定最短路徑的Dijkstra算法 218
16.6.3 Dijkstra算法的代碼 220
小結 226
練習 226
第17章 高級算法 227
17.1 動態規劃 227
17.1.1 動態規劃實例：計算斐波納契數列 227
17.1.2 尋找最長公共子串 230
17.1.3 背包問題 232
17.2 貪心算法 234
17.2.2 采用哈夫曼編碼的數據壓縮 236
17.2.3 用貪心算法解決背包問題 243
小結 245
練習 246
參考文獻 247
索引 248
