數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編：用C/C++描述

第一部分 理論基礎(chǔ).  
緒言——致成長(zhǎng)中的程序員們  
一. 為什么要使用C++?  
二. 為什么要使用STL?  
三. 編程的一些規(guī)范  
四. 應(yīng)當(dāng)使用什么開(kāi)發(fā)環(huán)境?  
第1章 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論  
1. 1 數(shù)據(jù)結(jié)構(gòu)與算法  
1. 1. 1 數(shù)據(jù)結(jié)構(gòu)  
1. 1. 2 算法  
1. 2 數(shù)據(jù)結(jié)構(gòu)的抽象形式——抽象數(shù)據(jù)類(lèi)型  
1. 2. 1 抽象數(shù)據(jù)類(lèi)型  
1. 2. 2 應(yīng)用程序編程接口(API)  
1. 2. 3 維護(hù)程序和文檔  
1. 3 C++類(lèi)和抽象數(shù)據(jù)類(lèi)型  
1. 3. 1 C++類(lèi)  
1. 3. 2 繼承性  
1. 3. 3 多態(tài)性  
1. 3. 4 泛型設(shè)計(jì)和模板  
1. 4 運(yùn)算與算法  
1. 4. 1 運(yùn)算  
1. 4. 2 算法  
1. 5 算法分析  
1. 5. 1 時(shí)空性能  
1. 5. 2 時(shí)間復(fù)雜度分析  
1. 5. 3 空間復(fù)雜度分析  
1. 5. 4 算法分析與代碼優(yōu)化調(diào)整  
第2章 C++語(yǔ)言概述  
2. 1 C++語(yǔ)言的演化和標(biāo)準(zhǔn)化歷程  
2. 2 C++支持的程序設(shè)計(jì)風(fēng)格  
2. 2. 1 基于過(guò)程的程序設(shè)計(jì)  
2. 2. 2 基于對(duì)象的程序設(shè)計(jì)  
2. 2. 3 面向?qū)ο蟮某绦蛟O(shè)計(jì)  
2. 2. 4 泛型程序設(shè)計(jì)  
2. 3 模塊化程序設(shè)計(jì)  
2. 3. 1 函數(shù)  
2. 3. 2 類(lèi)和封裝機(jī)制  
2. 4 類(lèi)的構(gòu)造. 析構(gòu)和賦值  
2. 4. 1 構(gòu)造函數(shù)和析構(gòu)函數(shù)  
2. 4. 2 類(lèi)的賦值  
2. 5 類(lèi)層次結(jié)構(gòu)——繼承和多態(tài)  
2. 5. 1 訪問(wèn)控制：public.cprivate和protected繼承  
2. 5. 2 虛函數(shù)與多態(tài)  
2. 6 異常處理  
2. 6. 1 異常處理的應(yīng)用情況  
2. 6. 2 異常處理基礎(chǔ)知識(shí)  
2. 6. 3 其他錯(cuò)誤處理技術(shù)  
2. 7 推薦的編程習(xí). 慣和風(fēng)格  
第3章 C++模板編程入門(mén)  
3. 1 類(lèi)模板  
3. 1. 1 如何定義類(lèi)模板  
3. 1. 2 如何實(shí)現(xiàn)類(lèi)模板的成員函數(shù)  
3. 1. 3 如何使用類(lèi)模板  
3. 2 函數(shù)模板  
3. 2. 1 如何定義函數(shù)模板  
3. 2. 2 如何使用函數(shù)模板  
3. 3 模板實(shí)例化  
3. 4 模板的特化  
3. 4. 1 類(lèi)模板的特化  
3. 4. 2 函數(shù)模板的特化  
3. 5 模板參數(shù)  
3. 6 靜態(tài)成員和變量  
3. 7 模板和friend  
3. 8 函數(shù)對(duì)象(仿函數(shù))  
3. 8. 1 如何定義函數(shù)對(duì)象  
3. 8. 2 函數(shù)對(duì)象的使用  
3. 8. 3模板函數(shù)對(duì)象  
3. 8. 4 標(biāo)準(zhǔn)庫(kù)中的函數(shù)對(duì)象  
第4章 泛型設(shè)計(jì). STL庫(kù)與數(shù)據(jù)結(jié)構(gòu)  
4. 1 標(biāo)準(zhǔn)C++與STL  
4. 1. 1 模板——現(xiàn)代C++風(fēng)格的基礎(chǔ)  
4. 1. 2 STL的發(fā)展歷程  
4. 1. 3 STL與C++標(biāo)準(zhǔn)程序庫(kù)  
4. 1. 4 STL的實(shí)現(xiàn)版本  
4. 1. 5 準(zhǔn)標(biāo)準(zhǔn)程序庫(kù)：Boost庫(kù)  
4. 1. 6 泛型算法與STL的應(yīng)用展示  
4. 2 泛型程序設(shè)計(jì)與多態(tài)  
4. 2. 1 面向?qū)ο蟪绦蛟O(shè)計(jì)中的多態(tài)  
4. 2. 2 泛型程序設(shè)計(jì)中的多態(tài)  
4. 2. 3 GP與OOP的對(duì)比  
4. 3 泛型程序設(shè)計(jì)與STL  
4. 3. 1 STL庫(kù)的設(shè)計(jì)：容器. 算法與迭代器  
4. 3. 2 A umulate函數(shù)示例  
4. 4 概念與模型  
4. 4. 1 必要條件集合  
4. 4. 2 示例：迭代器  
4. 5 關(guān)聯(lián)類(lèi)型與特性類(lèi)  
4. 5. 1 函數(shù)模板中需要的關(guān)聯(lián)類(lèi)型  
4. 5. 2 類(lèi)中的typedef嵌套  
4. 5. 3 特性類(lèi)的定義  
4. 5. 4 部分特化  
4. 5. 5 標(biāo)簽分派,92  
4. 6 STL中的核心concept：迭代器剖析  
4. 6. 1 迭代器概述  
4. 6. 2 迭代器與索引的比較  
4. 6. 3 STL的迭代器分類(lèi)  
4. 6. 4 STL中迭代器種類(lèi)的選擇  
4. 7 STL的其他組件  
4. 7. 1 STL的數(shù)據(jù)結(jié)構(gòu)：容器  
4. 7. 2 STL算法  
4. 7. 3 函數(shù)對(duì)象  
4. 7. 4 適配器  
4. 7. 5 分配器  
第二部分 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)  
第5章 線性表  
5. 1 線性表概述  
5. 1. 1 線性表基礎(chǔ)知識(shí)  
5. 1. 2 線性表類(lèi)ADT  
5. 2 順序存儲(chǔ)結(jié)構(gòu)——順序表  
5. 2. 1 順序表的定義及特點(diǎn)  
5. 2. 2 順序表的遍歷與查找  
5. 2. 3 順序表的其他操作  
5. 2. 4 順序表類(lèi)ADT以及類(lèi)定義  
5. 3 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表  
5. 3. 1 單鏈表  
5. 3. 2 雙向鏈表  
5. 3. 3 循環(huán)鏈表  
5. 3. 4 鏈表類(lèi)ADT以及類(lèi)定義  
5. 4 vector的基本操作及應(yīng)用  
5. 4. 1 vector迭代器  
5. 4. 2 vector的基本操作  
5. 5 list的基本操作及應(yīng)用  
5. 5. 1 list迭代器  
5. 5. 2 list的基本操作  
5. 6 slist的基本操作及應(yīng)用  
5. 6. 1 slist的迭代器  
5. 6. 2 slist的基本操作  
5. 7 線性表的應(yīng)用案例  
5. 7. 1 稀疏多項(xiàng)式的加法和乘法  
5. 7. 2 大整數(shù)加法..  
第6章 棧與隊(duì)列  
6. 1 雙端隊(duì)列  
6. 1. 1 deque概況  
6. 1. 2 操作與應(yīng)用  
6. 2 堆棧基礎(chǔ)  
6. 2. 1 堆棧的定義  
6. 2. 2 堆棧ADT  
6. 3 棧的使用  
6. 3. 1 進(jìn)制轉(zhuǎn)換  
6. 3. 2 列車(chē)調(diào)度  
6. 4 表達(dá)式計(jì)算  
6. 4. 1 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式  
6. 4. 2 后綴表達(dá)式的計(jì)算  
6. 4. 3 測(cè)試  
6. 5 隊(duì)列和優(yōu)先隊(duì)列  
6. 5. 1 隊(duì)列的定義  
6. 5. 2 隊(duì)列ADT  
6. 5. 3 隊(duì)列的實(shí)現(xiàn)  
6. 5. 4 優(yōu)先隊(duì)列  
6. 6 使用隊(duì)列  
6. 6. 1 時(shí)間驅(qū)動(dòng)的模擬  
6. 6. 2 基數(shù)排序法  
6. 7 棧與隊(duì)列的綜合實(shí)例  
6. 7. 1 農(nóng)夫過(guò)河問(wèn)題  
6. 7. 2 深度優(yōu)先搜索算法  
6. 7. 3 廣度優(yōu)先搜索算法  
第7章 遞歸  
7. 1 遞歸基礎(chǔ)  
7. 1. 1 遞歸的概念  
7. 1. 2 使用遞歸的情況  
7. 2 漢諾塔問(wèn)題  
7. 2. 1 問(wèn)題的提出  
7. 2. 2 問(wèn)題的遞歸求解  
7. 2. 3 Hanoi類(lèi)  
7. 3 迷宮問(wèn)題  
7. 3. 1 問(wèn)題的提出  
7. 3. 2 迷宮的回溯分析  
7. 3. 3 Maze類(lèi)  
7. 4 八皇后問(wèn)題  
7. 4. 1 問(wèn)題的描述  
7. 4. 2 八皇后問(wèn)題的回溯分析  
7. 4. 3 QueenChess類(lèi)的設(shè)計(jì)  
7. 5 遞歸算法的評(píng)價(jià)  
7. 5. 1 遞歸工作棧  
7. 5. 2 遞歸算法的復(fù)雜度  
7. 5. 3 遞歸與迭代的比較  
第8章 樹(shù)和二叉樹(shù)  
8. 1 樹(shù)和二叉樹(shù)基礎(chǔ)知識(shí)  
8. 1. 1 序列容器與有序關(guān)聯(lián)容器  
8. 1. 2 廣義樹(shù)結(jié)構(gòu)  
8. 1. 3 二叉樹(shù)的定義與性質(zhì)  
8. 1. 4 二叉樹(shù)遍歷算法  
8. 1. 5 二叉樹(shù)遍歷算法的應(yīng)用  
8. 2 二叉搜索樹(shù)基礎(chǔ)知識(shí)  
8. 2. 1 二叉搜索樹(shù)的定義  
8. 2. 2 二叉搜索樹(shù)的操作  
8. 2. 3 二叉搜索樹(shù)類(lèi)ADT  
8. 2. 4 二叉搜索樹(shù)的結(jié)構(gòu)  
8. 2. 5 二叉搜索樹(shù)的實(shí)現(xiàn)要點(diǎn)  
8. 2. 6 二叉搜索樹(shù)的迭代器  
8. 3  二叉樹(shù)類(lèi)算法的實(shí)現(xiàn)代碼分析  
8. 3. 1 二叉樹(shù)類(lèi)的聲明與接口  
8. 3. 2 二叉樹(shù)的遍歷操作實(shí)現(xiàn)  
8. 3. 3 樹(shù)遍歷算法的應(yīng)用  
8. 3. 4 二叉樹(shù)相關(guān)算法的測(cè)試程序  
8. 4 二叉搜索樹(shù)類(lèi)的實(shí)現(xiàn)代碼分析  
8. 4. 1 二叉搜索樹(shù)節(jié)點(diǎn)和樹(shù)類(lèi)的聲明  
8. 4. 2 構(gòu)造函數(shù). 析構(gòu)函數(shù)和賦值運(yùn)算符  
8. 4. 3 二叉搜索樹(shù)的查找與更新操作  
8. 4. 4 二叉搜索樹(shù)的測(cè)試程序  
8. 5 二叉搜索樹(shù)應(yīng)用案例  
8. 5. 1 消除重復(fù)項(xiàng)  
8. 5. 2 音像商店事務(wù)管理系統(tǒng)  
第9章 圖  
9. 1 圖的抽象  
9. 1. 1 圖的描述  
9. 1. 2 圖的數(shù)據(jù)結(jié)構(gòu)  
9. 2 圖的算法  
9. 2. 1 圖搜索算法  
9. 2. 2 拓?fù)渑判?nbsp; 
9. 2. 3 連通分量算法  
9. 2. 4 最短路徑問(wèn)題  
9. 2. 5 最小生成樹(shù)問(wèn)題  
9. 3 Boost圖庫(kù)介紹  
9. 3. 1 STL中的泛型  
9. 3. 2 BGL中的泛型  
9. 3. 3 BGL中的圖算法  
9. 3. 4 BGL實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)  
9. 3. 5 BGL的歷史  
9. 4 圖類(lèi)的實(shí)現(xiàn)與應(yīng)用  
9. 4. 1 圖的概念(Concepts)  
9. 4. 2 圖類(lèi)的實(shí)現(xiàn)  
9. 4. 3 圖類(lèi)應(yīng)用示例  
9. 5 圖算法的實(shí)現(xiàn)和應(yīng)用  
9. 5. 1 訪問(wèn)器  
9. 5. 2 圖遍歷算法的應(yīng)用  
9. 5. 3 拓?fù)渑判虻膽?yīng)用  
9. 5. 4 最短路徑算法的應(yīng)用  
9. 5. 5 最小生成樹(shù)算法的應(yīng)用  
9. 6 圖的建模與可視化——Graphviz軟件與DOT語(yǔ)言  
9. 6. 1 核心繪圖引擎  
9. 6. 2 圖文件描述語(yǔ)言——DOT語(yǔ)言  
9. 6. 3 Graphviz應(yīng)用示例  
第三部分 綜合應(yīng)用  
第10章 綜合應(yīng)用案例  
10. 1 數(shù)據(jù)壓縮——霍夫曼編碼解碼器的實(shí)現(xiàn)  
10. 1. 1 數(shù)據(jù)壓縮理論簡(jiǎn)介  
10. 1. 2 Huffman樹(shù)  
10. 1. 3 需求分析  
10. 1. 4 Huffman壓縮類(lèi)的接口與應(yīng)用  
10. 1. 5 Huffman壓縮類(lèi)的實(shí)現(xiàn)  
10. 1. 6 Huffman解壓縮  
10. 2 算法時(shí)間復(fù)雜度測(cè)度——算法計(jì)時(shí)器的實(shí)現(xiàn)  
10. 2. 1 精確測(cè)定算法時(shí)間的困難  
10. 2. 2 應(yīng)用統(tǒng)計(jì)方法解決困難  
10. 2. 3 完成自動(dòng)分析的Timer類(lèi)  
10. 2. 4 應(yīng)用Timer類(lèi)測(cè)試STL sort算法時(shí)間性能  
10. 3 理論計(jì)算機(jī)科學(xué)家族譜的文檔／視圖模式——STL組件的綜合應(yīng)用  
10. 3. 1 系統(tǒng)設(shè)計(jì)：“模型—視圖—控制器”模式  
10. 3. 2 數(shù)據(jù)關(guān)系建模與數(shù)據(jù)結(jié)構(gòu)選擇  
10. 3. 3 從源數(shù)據(jù)文檔到視圖  
10. 3. 4 完整的族譜視圖程序以及運(yùn)行示例  
10. 4 詞典檢索系統(tǒng)——數(shù)據(jù)結(jié)構(gòu)選擇對(duì)系統(tǒng)性能影響的示例  
10. 4. 1 解決方案1：應(yīng)用全排列的方法查找變位詞  
10. 4. 2 解決方案2：應(yīng)用pair向量改進(jìn)時(shí)間效率  
10. 4. 3 解決方案3：使用映射改進(jìn)空間效率  
附錄A Boost安裝指南  
附錄B 隨書(shū)所附光盤(pán)內(nèi)容清單  
附錄C STL庫(kù)容器類(lèi)速查手冊(cè)...