數(shù)據(jù)結(jié)構(gòu)C++描述 目 錄 譯者序 前言 第一部分 預(yù)備知識(shí) 第1章 C++程序設(shè)計(jì) 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 動(dòng)態(tài)存儲(chǔ)分配 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 類(lèi) 13 1.4.1 類(lèi)Currency 13 1.4.2 使用不同的描述方法 18 1.4.3 操作符重載 20 1.4.4 引發(fā)異常 22 1.4.5 友元和保護(hù)類(lèi)成員 23 1.4.6 增加#ifndef, #define和#endif語(yǔ)句 24 1.5 測(cè)試與調(diào)試 24 1.5.1 什么是測(cè)試 24 1.5.2 設(shè)計(jì)測(cè)試數(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 時(shí)間復(fù)雜性 37 2.3.1 時(shí)間復(fù)雜性的組成 37 2.3.2 操作計(jì)數(shù) 37 2.3.3 執(zhí)行步數(shù) 44 2.4 漸進(jìn)符號(hào)（O、 健?、 o） 55 2.4.1 大寫(xiě)O符號(hào) 56 2.4.2 椒?58 2.4.3 符號(hào) 59 2.4.4 小寫(xiě)o符號(hào) 60 2.4.5 特性 60 2.4.6 復(fù)雜性分析舉例 61 2.5 實(shí)際復(fù)雜性 66 2.6 性能測(cè)量 68 2.6.1 選擇實(shí)例的大小 69 2.6.2 設(shè)計(jì)測(cè)試數(shù)據(jù) 69 2.6.3 進(jìn)行實(shí)驗(yà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 異常類(lèi)NoMem 79 3.3.3 操作 79 3.3.4 評(píng)價(jià) 83 3.4 鏈表描述 86 3.4.1 類(lèi)ChainNode 和Chain 86 3.4.2 操作 88 3.4.3 擴(kuò)充類(lèi)Chain 91 3.4.4 鏈表遍歷器類(lèi) 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 等價(jià)類(lèi) 117 3.8.4 凸包 122 3.9 參考及推薦讀物 127 第4章 數(shù)組和矩陣 128 4.1 數(shù)組 128 4.1.1 抽象數(shù)據(jù)類(lèi)型 128 4.1.2 C++數(shù)組 129 4.1.3 行主映射和列主映射 129 4.1.4 類(lèi)Array1D 131 4.1.5 類(lèi)Array2D 133 4.2 矩陣 137 4.2.1 定義和操作 137 4.2.2 類(lèi)Matrix 138 4.3 特殊矩陣 141 4.3.1 定義和應(yīng)用 141 4.3.2 對(duì)角矩陣 143 4.3.3 三對(duì)角矩陣 144 4.3.4 三角矩陣 145 4.3.5 對(duì)稱矩陣 146 4.4 稀疏矩陣 149 4.4.1 基本概念 149 4.4.2 數(shù)組描述 149 4.4.3 鏈表描述 154 第5章 堆棧 161 5.1 抽象數(shù)據(jù)類(lèi)型 161 5.2 派生類(lèi)和繼承 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 括號(hào)匹配 169 5.5.2 漢諾塔 170 5.5.3 火車(chē)車(chē)廂重排 172 5.5.4 開(kāi)關(guān)盒布線 176 5.5.5 離線等價(jià)類(lèi)問(wèn)題 178 5.5.6 迷宮老鼠 180 5.6 參考及推薦讀物 188 第6章 隊(duì)列 189 6.1 抽象