數據結構教程（C++語言描述）（第2版·微課視頻版）

本書系統地介紹了常用的數據結構以及查找和排序的算法，闡述了數據結構的邏輯結構、存儲表示及基本運算，並採用C++語言描述數據組織和基本運算算法的實現，所有算法程序均在Dev C++5.1中調試通過。 全書既註重原理又註重實踐，配有大量圖表和示例，內容豐富，概念講解清楚，表達嚴謹，邏輯性強，語言精練，可讀性好。書中提供了豐富的練習題、上機實驗題和在線編程題，配套的《數據結構教程（C++語言描述）（第2版）學習與上機實驗指導》輔助教材中詳細給出了本書所有練習題和實驗題的解題思路和參考答案，《數據結構在線編程實訓（C++語言）（全程視頻講解版）》輔助教材中詳細給出了所有實戰題和在線編程題的解題思路和參考答案（含全部題目的視頻講解）。 本書內容涉及的廣度和深度符合普通高等學校電腦及相關專業培養目標的要求，配套教學資源豐富，可作為“數據結構”課程的教材，也可作為從事電腦軟件開發和工程應用人員的參考書。

李春葆,計算機學院教授，計算機科學系副主任。
主要研究方向：數據庫系統、數據挖掘、人工智能和軟件工程。
發表論文20篇，主持和參加8項科研課題。著作教材11部。
從事近30年C/C++語言、數據結構和算法設計等課程的第一線本科教學工作，具備豐富的教學經驗，曾參與深圳名企的筆試和麵試題庫建設。

第1章 緒論
1.1 什麼是數據結構
1.1.1 數據結構的定義
1.1.2 數據的邏輯結構
1.1.3 數據的存儲結構
1.1.4 數據的運算
1.1.5 數據結構和數據類型
1.2 算法及其描述
1.2.1 什麼是算法
1.2.2 算法描述
1.2.3 C++語言描述算法的要點
1.3 算法分析
1.3.1 算法的設計目標
1.3.2 算法的時間性能分析
1.3.3 算法的存儲空間分析
1.4 數據結構的目標
1.5 練習題
1.5.1 問答題
1.5.2 算法設計題
1.6 上機實驗題
1.6.1 基礎實驗題
1.6.2 應用實驗題
1.7 在線編程題
第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.3.4 雙鍊錶
2.3.5 雙鍊錶的應用算法設計示例
2.3.6 循環鍊錶
2.4 順序表和鍊錶的比較
2.5 線性表的應用——兩個多項式相加
2.5.1 問題描述
2.5.2 問題求解
2.6 STL中的線性表
2.6.1 vector向量容器
2.6.2 list鍊錶容器
2.7 練習題
2.7.1 問答題
2.7.2 算法設計題
2.8 上機實驗題
2.8.1 基礎實驗題
2.8.2 應用實驗題
2.9 在線編程題
第3章 棧和隊列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的順序存儲結構及其基本運算算法的實現
3.1.3 順序棧的應用算法設計示例
3.1.4 棧的鍊式存儲結構及其基本運算算法的實現
3.1.5 鏈棧的應用算法設計示例
3.1.6 STL中的stack棧容器
3.1.7 棧的綜合應用
3.2 隊列
3.2.1 隊列的定義
3.2.2 隊列的順序存儲結構及其基本運算算法的實現
3.2.3 循環隊列的應用算法設計示例
3.2.4 隊列的鍊式存儲結構及其基本運算算法的實現
3.2.5 鏈隊的應用算法設計示例
3.2.6 STL中的queue隊列容器
3.2.7 隊列的綜合應用
3.2.8 STL中的雙端隊列和優先隊列
3.3 *棧和隊列的擴展——單調棧和單調隊列
3.3.1 單調棧
3.3.2 單調隊列
3.4 練習題
3.4.1 問答題
3.4.2 算法設計題
3.5 上機實驗題
3.5.1 基礎實驗題
3.5.2 應用實驗題
3.6 在線編程題
第4章 串
4.1 串的定義
4.2 串的存儲結構
4.2.1 串的順序存儲結構——順序串
4.2.2 串的鍊式存儲結構——鏈串
4.3 STL中的string
4.4 串的模式匹配
4.4.1 BF算法
4.4.2 KMP算法
4.5 練習題
4.5.1 問答題
4.5.2 算法設計題
4.6 上機實驗題
4.6.1 基礎實驗題
4.6.2 應用實驗題
4.7 在線編程題
第5章 數組和稀疏矩陣
5.1 數組
5.1.1 數組的基本概念
5.1.2 數組的存儲結構
5.1.3 數組的應用
5.2 特殊矩陣的壓縮存儲
5.2.1 對稱矩陣的壓縮存儲
5.2.2 三角矩陣的壓縮存儲
5.2.3 對角矩陣的壓縮存儲
5.3 稀疏矩陣
5.3.1 稀疏矩陣的三元組表示
5.3.2 稀疏矩陣的十字鍊錶表示
5.4 練習題
5.4.1 問答題
5.4.2 算法設計題
5.5 上機實驗題
5.5.1 基礎實驗題
5.5.2 應用實驗題
5.6 在線編程題
第6章 遞歸
6.1 什麼是遞歸
6.1.1 遞歸的定義
6.1.2 何時使用遞歸
6.1.3 遞歸模型
6.1.4 遞歸與數學歸納法
6.1.5 遞歸的執行過程
6.1.6 遞歸算法的時空分析
6.2 遞歸算法設計
6.2.1 遞歸算法設計的步驟
6.2.2 基於遞歸數據結構的遞歸算法設計
6.2.3 基於歸納方法的遞歸算法設計
6.3 遞歸算法轉換為非遞歸算法
6.3.1 迭代轉換法
6.3.2 用棧模擬轉換法
6.4 練習題
6.4.1 問答題
6.4.2 算法設計題
6.5 上機實驗題
6.5.1 基礎實驗題
6.5.2 應用實驗題
6.6 在線編程題
第7章 樹和二r/> 7.1 樹
7.1.1 樹的定義
7.1.2 樹的邏輯結構表示方法
7.1.3 樹的基本術語
7.1.4 樹的性質
7.1.5 樹的基本運算
7.1.6 樹的存儲結構
7.2 二r/> 7.2.1 二叉樹的概念
7.2.2 二叉樹的性質
7.2.3 二叉樹的存儲結構
7.2.4 二叉樹的遞歸算法設計
7.2.5 二叉樹的基本運算算法及其實現
7.3 二叉樹的先序、中序和後序遍歷
7.3.1 二叉樹遍歷的概念
7.3.2 先序、中序和後序遍歷遞歸算法
7.3.3 遞歸遍曆算法的應用
7.3.4 先序、中序和後序遍歷非遞歸算法
7.4 二叉樹的層次遍歷
7.4.1 層次遍歷的過程
7.4.2 層次遍曆算法的設計
7.4.3 層次遍曆算法的應用
7.5 二叉樹的構造
7.5.1 由先序/中序序列或後序/中序序列構造二r/> 7.5.2 *序列化和反序列化
7.6 線索二r/> 7.6.1 線索二叉樹的定義
7.6.2 線索化二r/> 7.6.3 遍歷線索化二r/> 7.7 哈夫曼樹
7.7.1 哈夫曼樹的定義
7.7.2 哈夫曼樹的構造算法
7.7.3 哈夫曼編碼
7.8 樹/森林與二叉樹之間的轉換及還原
7.8.1 一棵樹與二叉樹的轉換及還原
7.8.2 森林與二叉樹的轉換及還原
7.9 *並查集
7.9.1 並查集的定義
7.9.2 並查集的實現
7.10 練習題
7.10.1 問答題
7.10.2 算法設計題
7.11 上機實驗題
7.11.1 基礎實驗題
7.11.2 應用實驗題
7.12 在線編程題
第8章 圖
8.1 圖的基本概念
8.1.1 圖的定義
8.1.2 圖的基本術語
8.2 圖的存儲結構
8.2.1 鄰接矩陣
8.2.2 鄰接表
8.3 圖的遍歷
8.3.1 圖遍歷的概念
8.3.2 深度優先遍歷
8.3.3 廣度優先遍歷
8.3.4 非連通圖的遍歷
8.4 圖遍曆算法的應用
8.4.1 深度優先遍曆算法的應用
8.4.2 *回溯法及其應用
8.4.3 廣度優先遍曆算法的應用
8.5 生成樹和生成樹
8.5.1 生成樹和生成樹的概念
8.5.2 普里姆算法
8.5.3 克魯斯卡爾算法
8.6 短路徑
8.6.1 短路徑的概念
8.6.2 狄克斯特拉算法
8.6.3 弗洛伊德算法
8.7 拓撲排序
8.7.1 什麼是拓撲排序
8.7.2 拓撲排序算法的設計
8.8 AOE網和關鍵路徑
8.8.1 什麼是AOE網
8.8.2 求AOE網的關鍵路徑
8.9 練習題
8.9.1 問答題
8.9.2 算法設計題
8.10 上機實驗題
8.10.1 基礎實驗題
8.10.2 應用實驗題
8.11 在線編程題
第9章 查找
9.1 查找的基本概念
9.2 線性表的查找
9.2.1 順序查找
9.2.2 折半查找
9.2.3 索引存儲結構和分塊查找
9.3 樹表的查找
9.3.1 二叉排序樹
9.3.2 衡二r/> 9.3.3 *STL中的關聯容器
9.3.4 B樹
9.3.5 B+樹
9.4 哈希表的查找
9.4.1 哈希表的基本概念
9.4.2 哈希函數的構造方法
9.4.3 哈希衝突的解決方法
9.4.4 哈希表查找及性能分析
9.4.5 *STL中的哈希表
9.5 練習題
9.5.1 問答題
9.5.2 算法設計題
9.6 上機實驗題
9.6.1 基礎實驗題
9.6.2 應用實驗題
9.7 在線編程題
第10章 排序
10.1 排序的基本概念
10.2 插入排序
10.2.1 直接插入排序
10.2.2 折半插入排序
10.2.3 希爾排序
10.3 交換排序
10.3.1 冒泡排序
10.3.2 快速排序
10.4 選擇排序
10.4.1 簡單選擇排序
10.4.2 堆排序
10.4.3 堆數據結構
10.5 歸併排序
10.5.1 自底向上的二路歸併排序
10.5.2 自頂向下的二路歸併排序
10.6 基數排序
10.7 各種內排序方法的比較和選擇
10.8 外排序
10.8.1 生成初始歸併段的方法
10.8.2 多路歸併方法
10.9 練習題
10.9.1 問答題
10.9.2 算法設計題
10.10 上機實驗題
10.10.1 基礎實驗題
10.10.2 應用實驗題
10.11 在線編程題
參考文獻