數(shù)據(jù)結(jié)構(gòu)C++描述 目 錄 譯者序 前言 第一部分 預(yù)備知識 第1章 C++程序設(shè)計 1 1.1 引言 1 1.2 函數(shù)與參數(shù) 2 1.2.1 傳值參數(shù) 2 1.2.2 模板函數(shù) 3 1.2.3 引用參數(shù) 3 1.2.4 常量引用參數(shù) 4 1.2.5 返回值 4 1.2.6 遞歸函數(shù) 5 1.3 動態(tài)存儲分配 9 1.3.1 操作符new 9 1.3.2 一維數(shù)組 9 1.3.3 異常處理 10 1.3.4 操作符delete 10 1.3.5 二維數(shù)組 10 1.4 類 13 1.4.1 類Currency 13 1.4.2 使用不同的描述方法 18 1.4.3 操作符重載 20 1.4.4 引發(fā)異常 22 1.4.5 友元和保護(hù)類成員 23 1.4.6 增加#ifndef, #define和#endif語句 24 1.5 測試與調(diào)試 24 1.5.1 什么是測試 24 1.5.2 設(shè)計測試數(shù)據(jù) 26 1.5.3 調(diào)試 28 1.6 參考及推薦讀物 29 第2章 程序性能 30 2.1 引言 30 2.2 空間復(fù)雜性 31 2.2.1 空間復(fù)雜性的組成 31 2.2.2 舉例 35 2.3 時間復(fù)雜性 37 2.3.1 時間復(fù)雜性的組成 37 2.3.2 操作計數(shù) 37 2.3.3 執(zhí)行步數(shù) 44 2.4 漸進(jìn)符號（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 復(fù)雜性分析舉例 61 2.5 實際復(fù)雜性 66 2.6 性能測量 68 2.6.1 選擇實例的大小 69 2.6.2 設(shè)計測試數(shù)據(jù) 69 2.6.3 進(jìn)行實驗 69 2.7 參考及推薦讀物 74 第二部分 數(shù)據(jù)結(jié)構(gòu) 第3章 數(shù)據(jù)描述 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 擴(kuò)充類Chain 91 3.4.4 鏈表遍歷器類 92 3.4.5 循環(huán)鏈表 93 3.4.6 與公式化描述方法的比較 94 3.4.7 雙向鏈表 95 3.4.8 小結(jié) 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 應(yīng)用 111 3.8.1 箱子排序 111 3.8.2 基數(shù)排序 116 3.8.3 等價類 117 3.8.4 凸包 122 3.9 參考及推薦讀物 127 第4章 數(shù)組和矩陣 128 4.1 數(shù)組 128 4.1.1 抽象數(shù)據(jù)類型 128 4.1.2 C++數(shù)組 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 定義和應(yīng)用 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 數(shù)組描述 149 4.4.3 鏈表描述 154 第5章 堆棧 161 5.1 抽象數(shù)據(jù)類型 161 5.2 派生類和繼承 162 5.3 公式化描述 163 5.3.1 Stack的效率 164 5.3.2 自定義Stack 164 5.4 鏈表描述 166 5.5 應(yīng)用 169 5.5.1 括號匹配 169 5.5.2 漢諾塔 170 5.5.3 火車車廂重排 172 5.5.4 開關(guān)盒布線 176 5.5.5 離線等價類問題 178 5.5.6 迷宮老鼠 180 5.6 參考及推薦讀物 188 第6章 隊列 189 6.1 抽象