第一章 緒論/l 1.1 問題求解/1 1.1.1問題/2 1.1.2問題的分析/2 1.1.3算法的選擇/3 1.1.4解的精化/4 1.2 數據結構/4 1.3 算法/6 l.3.1算法的設計/6 1.3.2算法的分析/7 1.4 抽象數據類型/9 1.5 程序設計方法和語言/11 小結/12 習題/12第二章 C++與麵嚮對象初步/13 2.1 C++語言對c的基本擴充/13 2.1.1注釋/13 2.1.2函數原型說明/14 2.1.3引用和引用參數/14 2.1.4重載/16 2.1.5缺省參數/16 2.1.6變量說明/17 2.1.7輸入和輸齣/17 2.1.8動態存儲分配/17 2.1.9類型定義/18 2.1.10強製類型轉換/18 2.2 對象和類/18 2.3 類的界麵描述和實現/22 2.3.1類的數據域/24 2.3.2對象的行為——成員函數/24 2.3.3運算符作為成員函數/25 2.3.4用構造函數進行實例的初始化/27 2.4 普通運算符和普通函數/31 2.4.1普通運算符/31 2.4.2普通函數/33 2.4.3輸入和輸齣/33 2.5 類的閤成、繼承和多態性/36 2.5.1閤成/36 2.5.2繼承/38 2.5.3多態性/39 小結/40 習題/42第三章 字符串二—數據封裝技術/44 3.1 C語言的字符和字符串/44 3.2 字符串數據抽象的描述和實現/46 3.2.1字符串類的定義/47 3.2.2構造函數的定義/49 3.2.3析構函數/52 3.2.4基本成員函數的實現/53 3.2.5比較運算符/57 3.2.6串連接/59 3.2.7輸入和輸齣/60 3.3子串/62 3.4 模式匹配/67 3.4.1簡單字符串匹配/69 3.4.2 Knuth-Mords-Pratt模式匹配算法/72 3.4.3 Bovermore符串匹配算法/76 小結/80 習題/80第四章 嚮量——類的重用技術/83 4.1 模闆類/84 4.2 嚮量的實現/86 4.3 定界嚮量和枚舉嚮量——繼承方式的重用/90 4.3.1定界嚮量/90 4.3.2枚舉嚮量/94 4.4 排序嚮量和矩陣——捨成方式的重用/96 4.4.1排序嚮量和二分法檢索/96 4.4.2矩陣/100 4.5 嚮量遍曆器/103 4.5.1遍曆器的抽象/103 4.5.2嚮量遍曆器/105 4.6 嚮量的排序一模闆函數/110 4.6.1插入排序/110 4.6.2起泡排序/112 4.6.3選擇排序/113 4.6.4快速排序算法/114 4.7 繼承和多態的若乾討論/l16 4.7.1父類與子類/116 4.7.2靜態類型和動態類型/117 4.7.3框架和框架類/118 4.7.4遮蔽和虛函數/118 4.7.5虛遮蔽和非虛遮蔽/119 4.7.6兩類繼承/120 4.7.7多態的主要形式/121 4.7.8參數多態性——歸約/121 4.7.9切割問題/123小結/125習題/125第五章 動態數據結構一鏈錶/128 5.1 單鏈錶的定義/128 5.1.1錶類/128 5.1.2鏈類/130 5.2 單鏈錶的實現/131 5.2.I鏈類的實現/131 5.2.2錶類的實現/133 5.3 錶遍曆器/136 5.3.1錶遍曆器類/136 5.3.2錶遍曆器類的實現/138 5.4 錶的應用：多項式處理/142 5.4.1項類/143 5.4.2多項式類/145 5.5 排序錶“/148 5.5.1排序錶類/148 5.5.2排序錶類的實現/148 5.5.3排序錶的應用——錶插入排序/149 5.6 其他鏈錶/150 5.6.1 自組織錶/150 5.6.2雙端錶/152 5.6-3循環錶/154 5.6.4雙鏈錶/155 5.7 可利用空間錶/155小結/157習題/159第六章 棧和隊列/161 6.1 抽象類棧和隊列161 6.2 棧的實現/162 6.2.1棧的嚮量實現/163 6.2.2棧的鏈錶實現/165 6.3棧的應用——錶達式計算/167 6.3.1、後綴錶達式的求值/167 6.3.2中綴錶達式到後綴錶達式 的轉換/170 6.4 隊列的實現/172 6.4.1隊列的嚮量實現/172 6.4.2隊列的鏈錶實現/174 6.5 隊列的應用——農夫過河問題/177小結/181習題/181第七章 樹和二叉樹/184 7.1 基本概念/185 7.1.1樹/185 7.1.2二叉樹/187 7.1.3樹與二叉樹的關係/190 7.2 二叉樹的實現/191 7.2.1二叉樹結點類/191 7.2.2基本二叉樹類/193 7.2.3可構造二叉樹類/195 7.3 二叉樹的周遊/197 7.3.1周遊的遞歸實現/197 7.3.2通過遍曆器實現周遊/199 7.3.3前序周遊器類/199 7.3.4中序周遊器類/202 7.3.5後序周遊器類/203 7.3.6層次周遊算法(按寬度方嚮周遊)/205 7.4 二叉樹的嚮量錶示/207 7.4.1二叉樹嚮量錶示的一種基本方法/207 7.4.2記錄結構信息的二叉樹嚮量錶示/208 7.5 二叉排序樹/209 7.6 平衡的二叉排序樹/214 7.6.1AVL樹上的操作/215 7.6.2AVL樹的設計與實現/218 7.7 二叉樹的應用——哈夫曼樹/225小、結/228習題/228第八章 優先隊列/23l 8.1 優先隊列的抽象/231 8.2 堆/234 8.3 堆排序/238 8.4 斜堆/240 8.5 離散事件模擬/244 8.5.1模擬類的結構/246 8.5.2冰淇淋店的模擬/248 8.5.3隨機數/251小結/253習題/253第九章 集閤與字典/256 9.1 集閤及其運算/256 9.1.1集閤運算/257 9.1.2集閤類/258 9.2 位嚮量集閤/259 9.2.1位嚮量/260 9.2.2位嚮量集閤/266 9.2.3字符集閤/269 9.2.4字符集類的應用——將字符串分解為單詞/270 9.3 集閤的錶實現/273 9.4 關聯與字典/275 9.5 字典的關聯錶實現/278 9.6 字典的應用/281 9.6.1稀疏矩陣/281 9.6.2排序字典/284 9.6.3索引的實現/285小結/287習題/289 第十章散列結構/291 10.1散列結構/291 10.2散列函數/295 10.3開地址散列嚮量/297 10.4桶散列——用桶解決碰撞/300 IO.4.桶散列的抽象模闆類/301 10.4.2用樹作為桶的實現/302 10.4.3桶散列結構操作時間的分析/304lO.5桶散列結構的遍曆器/30510.6用散列錶實現集閤/307 10.6.1應用——拼寫檢查器/30910.7用桶散列錶實現字典/311小結/313習題/314第十一章 圖/316 11.1 基本概念/316 11.2 圖的鄰接矩陣錶示和Warshall算法/318 11.2.1圖的鄰接矩陣錶示/318 Il.2.2圖結點的可達性問題/318 11.3 鄰接錶方式的圖錶示和深度優先搜索/320 11.3.1鄰接錶錶示中的結點類/321 11.3.2用深度優先方式求解可達性問題/322 11.4 帶權圖的矩陣錶示和Floyd算法/324 11.4.1帶權圖的鄰接矩陣/325 11.4.2帶權圖最短路徑問題Floyd算法/325 11.5 帶權圖的鄰接錶錶示與Dijkstra算法/327 11.5.1帶權圖的鄰接錶錶示/327 11.5.2從一個結點齣發的最短路徑和Dijkstra算法/328 11.6 連通性、帶權連通無嚮圖與最小生成樹/330 11.7有限自動機/333 11.8拓撲排序}/336小結/338習題/339第十二章 文件/342 12.1 外存、文件及其問題/342 12.1.1外存儲器的特點與信息組織/342 12.1.2文件基本結構和操作/344 12.1.3文件與字典/345 12.1.4文件組織/346 12.2 C++的字符流文件及其操作/347 12.3 歸並排序/352 12.4 文件的隨機訪問/356 12.5 文件索引結構/359 12.5.1索引嚮量/359 12.5.2樹形索引結構/360 12.5.3 B樹/361 12.5.4 B+樹/364 12.6 樹索引文件的實現/367小結/369習題/369附錄/371 附錄A 主要抽象數據類及其相互關係/371 附錄B Borland C++集成開發環境使用入門/375 附錄C“多叉路口的交通管理係統”上機報告/387
· · · · · · (收起)