數據結構C++描述 目 錄 譯者序 前言 第一部分 預備知識 第1章 C++程序設計 1 1.1 引言 1 1.2 函數與參數 2 1.2.1 傳值參數 2 1.2.2 模板函數 3 1.2.3 引用參數 3 1.2.4 常量引用參數 4 1.2.5 返回值 4 1.2.6 遞歸函數 5 1.3 動態存儲分配 9 1.3.1 操作符new 9 1.3.2 一維數組 9 1.3.3 異常處理 10 1.3.4 操作符delete 10 1.3.5 二維數組 10 1.4 類 13 1.4.1 類Currency 13 1.4.2 使用不同的描述方法 18 1.4.3 操作符重載 20 1.4.4 引發異常 22 1.4.5 友元和保護類成員 23 1.4.6 增加#ifndef, #define和#endif語句 24 1.5 測試與調試 24 1.5.1 什么是測試 24 1.5.2 設計測試數據 26 1.5.3 調試 28 1.6 參考及推薦讀物 29 第2章 程序性能 30 2.1 引言 30 2.2 空間復雜性 31 2.2.1 空間復雜性的組成 31 2.2.2 舉例 35 2.3 時間復雜性 37 2.3.1 時間復雜性的組成 37 2.3.2 操作計數 37 2.3.3 執行步數 44 2.4 漸進符號（O、 健?、 o） 55 2.4.1 大寫O符號 56 2.4.2 椒?58 2.4.3 符號 59 2.4.4 小寫o符號 60 2.4.5 特性 60 2.4.6 復雜性分析舉例 61 2.5 實際復雜性 66 2.6 性能測量 68 2.6.1 選擇實例的大小 69 2.6.2 設計測試數據 69 2.6.3 進行實驗 69 2.7 參考及推薦讀物 74 第二部分 數據結構 第3章 數據描述 75 3.1 引言 75 3.2 線性表 76 3.3 公式化描述 77 3.3.1 基本概念 77 3.3.2 異常類NoMem 79 3.3.3 操作 79 3.3.4 評價 83 3.4 鏈表描述 86 3.4.1 類ChainNode 和Chain 86 3.4.2 操作 88 3.4.3 擴充類Chain 91 3.4.4 鏈表遍歷器類 92 3.4.5 循環鏈表 93 3.4.6 與公式化描述方法的比較 94 3.4.7 雙向鏈表 95 3.4.8 小結 96 3.5 間接尋址 99 3.5.1 基本概念 99 3.5.2 操作 100 3.6 模擬指針 102 3.6.1 SimSpace的操作 103 3.6.2 采用模擬指針的鏈表 106 3.7 描述方法的比較 110 3.8 應用 111 3.8.1 箱子排序 111 3.8.2 基數排序 116 3.8.3 等價類 117 3.8.4 凸包 122 3.9 參考及推薦讀物 127 第4章 數組和矩陣 128 4.1 數組 128 4.1.1 抽象數據類型 128 4.1.2 C++數組 129 4.1.3 行主映射和列主映射 129 4.1.4 類Array1D 131 4.1.5 類Array2D 133 4.2 矩陣 137 4.2.1 定義和操作 137 4.2.2 類Matrix 138 4.3 特殊矩陣 141 4.3.1 定義和應用 141 4.3.2 對角矩陣 143 4.3.3 三對角矩陣 144 4.3.4 三角矩陣 145 4.3.5 對稱矩陣 146 4.4 稀疏矩陣 149 4.4.1 基本概念 149 4.4.2 數組描述 149 4.4.3 鏈表描述 154 第5章 堆棧 161 5.1 抽象數據類型 161 5.2 派生類和繼承 162 5.3 公式化描述 163 5.3.1 Stack的效率 164 5.3.2 自定義Stack 164 5.4 鏈表描述 166 5.5 應用 169 5.5.1 括號匹配 169 5.5.2 漢諾塔 170 5.5.3 火車車廂重排 172 5.5.4 開關盒布線 176 5.5.5 離線等價類問題 178 5.5.6 迷宮老鼠 180 5.6 參考及推薦讀物 188 第6章 隊列 189 6.1 抽象