數據結構：C++語言描述（簡體書）

《重點大學計算機教材：數據結構·C++語言描述》將數據結構與算法設計有機地結合起來，向讀者系統地介紹數據結構的基本概念及主要的算法設計方法。
全書共分七章：第1章介紹了數據結構的基本概念及主要的數學方法；第2～5章分別介紹了線性表，棧、隊列和數組，樹，圖等重要的數據結構及基本操作的實現過程；第6～7章介紹了查找和排序等數據結構的相關知識。本書在內容講授過程中輔以大量的實例，旨在幫助讀者更好地理解概念，並使用這些概念去解決實際問題。書中主要算法都用C++語言寫出，並給出了必要的注釋。
《重點大學計算機教材：數據結構·C++語言描述》概念清楚，選材精練，敘述深入淺出，並借助例子和圖表來說明基本概念和方法，直觀易懂，同時涵蓋了研究生入學考試大綱“數據結構”課程的知識點。每章後面都附有習題，讀者可以通過練習來檢驗所學知識。本書可以作為高等院校計算機專業學生的教材，也可以作為廣大工程技術人員的參考書。·

《華章教育?重點大學計算機教材?數據結構:C++語言描述》的目的是要為師生提供一本涉及該課程教學主要內容的合適教材。《華章教育?重點大學計算機教材?數據結構:C++語言描述》各章的介紹中，既包含了數據結構的基本概念，也介紹了算法的設計與實現。實際上，數據結構與算法設計是程序設計的核心，二者是密不可分的。掌握了初步的程序設計方法之后，面對實際的應用問題，最重要的就是學習如何選擇和設計有效的數據結構和算法，解決問題才是編寫程序的目的。《華章教育?重點大學計算機教材?數據結構:C++語言描述》采用準C++語言作為全書的基本描述語言，書中對各段程序代碼都盡可能地給出了說明，相信即使沒有學習過C++的讀者，也能很快理解書中的內容。

前言
教學建議
第1章 緒論
1.1 數據結構的基本概念和術語
1.2 抽象數據類型及面向對象的概念
1.2.1 抽象數據類型
1.2.2 面向對象的概念
1.3 有關的預備知識
1.3.1 集合
1.3.2 遞歸
1.4 算法和算法分析
1.4.1 算法的基本概念
1.4.2 算法的評估和複雜度度量
1.4.3 算法設計的一個實例
本章小結
習題

第2章 線性表
2.1 線性表的定義和基本運算
2.1.1 線性表的定義
2.1.2 線性表的操作
2.2 線性表的實現
2.2.1 順序存儲結構
2.2.2 鏈式存儲結構
2.2.3 兩種基本存儲實現方式的比較
2.2.4 循環鏈表
2.2.5 雙向鏈表
2.3 線性表的應用
本章小結
習題

第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.3.3 特殊數組
3.3.4 數組的應用
本章小結
習題

第4章 樹與二叉樹
4.1 樹
4.1.1 樹的基本概念
4.1.2 樹的抽象數據類型
4.2 二叉樹
4.2.1 二叉樹的定義及其主要特性
4.2.2 二叉樹的實現
4.2.3 二叉樹的遍歷
4.3 樹與森林
4.3.1 樹的存儲結構
4.3.2 森林與二叉樹的轉換
4.3.3 樹和森林的遍歷
4.4 哈夫曼樹和哈夫曼編碼
本章小結
習題

第5章 圖結構
5.1 圖
5.1.1 圖的基本概念
5.1.2 圖的抽象數據類型
5.2 圖的存儲結構
5.2.1 鄰接矩陣
5.2.2 鄰接表
5.2.3 圖的實現
5.3 圖的遍歷及求圖的連通分量
5.3.1 深度優先搜索
5.3.2 廣度優先搜索
5.3.3 無向圖的連通分量
5.4 有向無環圖及拓撲排序
5.4.1 有向無環圖
5.4.2 拓撲排序
5.5 生成樹和最小代價生成樹
5.5.1 生成樹
5.5.2 最小代價生成樹
5.6 單源最短路徑
5.6.1 問題的提出
5.6.2 單源最短路徑的算法
本章小結
習題

第6章 查找
6.1 查找的基本概念
6.2 順序表的查找
6.2.1 順序查找方法
6.2.2 折半查找方法
6.3 樹形結構的查找
6.3.1 二叉排序樹
6.3.2 平衡二叉樹
6.3.3 B樹
6.4 哈希表及其查找
6.4.1 哈希的概念
6.4.2 哈希函數的構造方法
6.4.3 處理衝突的幾種方法
6.4.4 哈希表的查找及其效率分析
本章小結
習題

第7章 內部排序
7.1 排序的基本概念
7.2 插入排序
7.2.1 直接插入排序
7.2.2 折半插入排序
7.2.3 希爾排序
7.3 交換排序
7.4 基於分治法的排序
7.4.1 歸併排序
7.4.2 快速排序
7.5 選擇排序
7.5.1 簡單選擇排序
7.5.2 堆排序
7.6 分配排序和桶式排序
7.7 有關內部排序算法的比較
本章小結
習題

附錄
數據結構綜合測試題
數據結構期末模擬考試試卷一
數據結構期末模擬考試試卷二
數據結構期末模擬考試試卷三
參考文獻·

為了解決重復訪問及圖的不連通問題，遍歷圖的頂點時，對每個頂點增加一個訪問標志，標明該結點是否被訪問過。可以使用一維數組visited記錄圖頂點的訪問標志，數組元素的個數等于圖中頂點的個數。初始時，所有頂點的訪問標志置為UNVISITED或是0，當訪問過后，頂點的訪問標志置為VISITED或是1。遍歷時，檢查圖中所有的頂點，如果它的標志是UNVISITED，則輸出相關信息，進行相應的處理，同時將訪問標志置為VISITED。否則，跳過該頂點，繼續對下一頂點的操作。有了這個數組，既能防止對頂點的重復訪問，也不會漏掉哪個頂點。
與樹的遍歷類似，圖的遍歷也需要依據某種規律進行，這樣才不會漏掉某個頂點或是多次訪問一個頂點。遍歷的方式主要有兩種，分別是深度優先搜索（Depth First Search，DFS）及廣度優先搜索（Breadth First Search，BFS）。
5.3.1 深度優先搜索
深度優先搜索類似于樹的先序遍歷，遍歷過程如下：
1）選擇圖中指定的頂點為起始頂點v；
2）當前頂點=起始頂點；
3）訪問當前頂點，輸出它的相關信息；
4）將當前頂點的訪問標志置為VISITED；
5）如果當前頂點的鄰接點中存在未訪問的頂點w，則起始頂點=w，轉步驟2繼續；否則轉步驟6；
6）回退到最近訪問過的且仍有未被訪問的鄰接點的頂點，轉步驟5繼續；不能回退時，轉步驟7；
7）如果所有頂點均已訪問，則遍歷結束，否則，選擇未被訪問的另一個頂點作為起始頂點，轉步驟2繼續。
直觀地看，深度優先搜索就是從起始頂點起，沿著一條路徑盡可能地向前搜索，直到不能再向前時（這個頂點的所有鄰接點都已訪問過）就往回退，回退過程也稱為回溯。回溯時沿著與訪問順序相反的順序進行，當回溯到仍有未被訪問的鄰接點的一個頂點時，把這個點當成起始頂點，再找一條路徑繼續向前搜索，這個過程類似剛才的過程。因此，圖的深度優先搜索遍歷過程是個遞歸過程。