數據結構與應用教程(C++版)（簡體書）

令書採用面向對象的觀點討論數據結構技術，並以c++類模板作為算法描述工具。
《21世紀高等學校計算機教育實用規劃教材：數據結構與應用教程（C++版）》在簡要回顧（++程序設計概念的基礎上，全面系統地介紹了線性表、棧和隊列、串、數組和廣義表、樹和二叉樹及圖等數據結構，討論了常用的查找和排序技術。對每一種數據結構，除了詳細闡述其邏輯結構、存儲結構和相關算法外，並對所有算法進行了c++語言實現和評價，最後通過實例來瞭解它的基本應用。對查找和排序算法，還著重在時間上作出了定量或定性的分析比較。《21世紀高等學校計算機教育實用規劃教材：數據結構與應用教程（C++版）》最後還精心設計了8個上機實驗。
全書條理清晰，語言通俗，圖文並茂，可操作性強，列舉實例豐富、典型。每章後面提供的練習題和附錄部分的實驗內容與教學要求一致，並提供全方位的教學資源。
《21世紀高等學校計算機教育實用規劃教材：數據結構與應用教程（C++版）》可作為高等院校計算機及相關專業的教材或參考書，也可供自學者使用。．

《21世紀高等學校計算機教育實用規劃教材:數據結構與應用教程(C++版)》條理清晰，語言通俗，圖文并茂，可操作性強，列舉實例豐富、典型。每章后面提供的練習題和附錄部分的實驗內容與教學要求一致，并提供全方位的教學資源。《21世紀高等學校計算機教育實用規劃教材:數據結構與應用教程(C++版)》可作為高等院校計算機及相關專業的教材或參考書，也可供自學者使用。

第0章 C十十程序設計語言預備知識
0.1 一個簡單C++語言程序
0.1.1 C++程序基本結構
0.1.2 C++程序基本組成
0.1.3 簡單的輸入／輸出
0.2 指針與引用
0.2.1 指針
0.2.2 引用
0.3 動態存儲分配
0.4 函數
0.4.1 函數的定義與調用
0.4.2 函數的參數傳遞
0.4.3 函數原型與帶默認參數的函數
0.4.4 重載函數
0.5 類與對象
0.5.1 類
0.5.2 對象
0.5.3 構造函數與析構函數
0.5.4 友元函數
0.6 運算符重載
0.6.1 用成員函數重載運算符
0.6.2 用友元函數重載運算符
0.7 模板
0.7.1 模板的概念
0.7.2 函數模板
0.7.3 類模板
第1章 緒論
1.1 數據結構的產生和發展
1.2 數據結構研究的內容
1.3 基本概念和術語
1.3.1 數據和數據元素
1.3.2 數據結構
1.4 算法
1.4.1 算法的定義及特性
1.4.2 算法的描述
1.4.3 算法設計的目標
1.4.4 算法的分析
1.5 習題
第2章 線性表
2.1 線性表的邏輯結構
2.1.1 線性表的定義
2.1.2 線性表的操作
2.2 線性表的順序存儲結構
2.2.1 順序表
2.2.2 順序表基本運算的實現
2.2.3 小結
2.3 線性表的鏈式存儲結構
2.3.1 單鏈表
2.3.2 單循環鏈表
2.3.3 雙鏈表
2.4 順序表和鏈表的比較
2.5 線性表的應用
2.5.1 一元多項式的表示
2.5.2 一元多項式的存儲結構
2.5.3 一元多項式加法的算法分析與實現
2.6 習題
第3章 棧和隊列
3.1 棧
3.1.1 棧的邏輯結構
3.1.2 順序棧
3.1.3 鏈棧
3.2 隊列
3.2.1 隊列的邏輯結構
3.2.2 順序隊列
3.2.3 鏈隊列
3.3 棧的應用
3.3.1 問題描述
3.3.2 算法的分析與實現
3.4 習題
第4章 串
4.1 串的邏輯結構
4.1.1 串的基本概念
4.1.2 串的基本操作
4.1.3 常用的C++字符串函數
4.2 串的順序存儲結構
4.2.1 順序串
4.2.2 順序串基本操作的實現
4.2.3 模式匹配
4.3 串的鏈式存儲結構
4.4 串的應用
4.4.1 問題描述
4.4.2 算法的設計與實現
4.5 習題
第5章 數組和廣義表
5.1 數組
5.1.1 數組的邏輯結構
5.1.2 數組的順序存儲結構
5.2 矩陣的壓縮存儲
5.2.1 特殊矩陣
5.2.2 稀疏矩陣
5.3 廣義表
5.3.1 廣義表的邏輯結構
5.3.2 廣義表的存儲結構
5.3.3 廣義表基本操作的實現
5.4 多維數組的應用
5.4.1 問題描述
5.4.2 設計要求
5.4.3 算法的分析與實現
5.5 習題
第6章 樹和二叉樹
6.1 樹的邏輯結構
6.1.1 樹的定義
6.1.2 樹的表示方法
6.1.3 樹的基本術語
6.1.4 樹的基本運算
6.2 樹的順序存儲結構
6.2.1 雙親表示法
6.2.2 孩子鏈表表示法
6.2.3 雙親孩子表示法
6.2.4 孩子兄弟表示法
6.3 二叉樹的邏輯結構
6.3.1 二叉樹的概念
6.3.2 二叉樹的基本性質
6.3.3 二叉樹的遍歷操作
6.3.4 由遍歷序列恢復二叉樹
6.4 二叉樹的存儲結構
6.4.1 二叉樹的順序存儲結構
6.4.2 二叉鏈表
6.4.3 三叉鏈表
6.5 線索二叉樹
6.5.1 線索二叉樹的定義及結構
6.5.2 線索二叉樹基本操作的實現
6.6 樹、森林與二叉樹的轉換
6.7 樹的應用
6.7.1 哈夫曼樹的基本概念
6.7.2 哈夫曼算法
6.7.3 哈夫曼編碼
6.8 習題
第7章 圖
7.1 圖的邏輯結構
7.1.1 圖的定義
7.1.2 圖的基本術語
7.1.3 圖的基本操作
7.2 圖的存儲結構
7.2.1 鄰接矩陣
7.2.2 鄰接表
7.2.3 鄰接矩陣和鄰接表的比較
7.3 圖的遍歷
7.3.1 深度優先搜索遍歷
7.3.2 廣度優先搜索遍歷
……
第8章 排序
第9章 查找
附錄 實驗內容
參考文獻

6.1.3 樹的基本術語
下面介紹樹的常用術語。
（1）結點的度與樹的度。樹中某個結點的子樹的個數稱為該結點的度（degree）。樹中各結點的度的最大值稱為樹的度，通常將度為m的樹稱為m次樹。例如，在圖6.1（b）中，結點A的度為3，結點B的度為2，結點M的度為0，樹的度為3，該樹是一棵3次樹。
（2）分支結點與葉子結點。度不為零的結點稱為非終端結點，又叫分支（branch）結點。度為零的結點稱為終端結點或葉子（leaf）結點。在分支結點中，每個結點的分支數就是該結點的度。如對于度為l的結點，其分支數為1，被稱為單分支結點；對于度為2的結點，其分支數為2，被稱為雙分支結點，其余類推。例如，圖6.1（b）所示的樹中，B、C、D、E和H等是分支結點，而F、G、I、J、K、L和M等是葉子結點。
（3）孩子結點、雙親結點和兄弟結點。在一棵樹中，每個結點的直接后繼被稱做該結點的孩子（children）結點（或子女結點）。相應地，該結點被稱做孩子結點的雙親（parent）結點（或父母結點）。具有同一雙親的孩子結點互為兄弟結點。例如，圖6.1（b）所示的樹中，結點B是結點A的孩子結點，結點A是結點B的雙親結點，結點B和C互為兄弟結點。
（4）路徑與路徑長度。若樹中存在一個結點序列k1，k2，….kn，使得結點ki是結點ki+1（1≤i
（5）祖先結點和子孫結點。把每個結點的所有子樹中的結點稱為該結點的子孫（descendant）結點，從樹根結點到達該結點的路徑上經過的所有結點（除自Nfib）被稱做該結點的祖先結點。例如，圖6.1（b）所示的樹中，結點D的子孫結點有H、I、J和M；結點I的祖先結點有A、D。
（6）結點的層次和樹的高度。樹中的每個結點都處在一定的層次上。結點的層次（level）從樹根開始定義，根結點為第一層，它的孩子結點為第二層，以此類推，一個結點所在的層次為其雙親結點所在的層次加1。樹中結點的最大層次稱為樹的高度（或樹的深度）。例如，圖6.1（b）所示的樹中，結點A位于第一層，結點K位于第四層，樹的高度是4。
（7）有序樹和無序樹。若樹中各結點的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有序樹（ordered tree），否則稱為無序樹（unordered tree）。在圖6.4所示的樹中，若為有序樹，則圖6.4（a）和圖6.4（b）是兩棵不同的樹；若為無序樹，則它們是兩棵相同的樹。以后若不特別指明，我們討論的樹都是有序樹。