●章 緒論
1.1 數據結構的重要性
1.2 數據結構基本術語
1.3 數據的邏輯結構
1.4 數據的存儲結構
1.5 算法的基本概念
1.6 算法分析與度量
1.6.1 算法的評價標準
1.6.2 算法效率的度量
1.7 總結與提高
1.8 習題一
第2章 線性結構
2.1 線性表及邏輯結構
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.4 順序表與鏈表的比較
2.5 循環鏈表
2.6 雙向鏈表
2.7 應用舉例
2.7.1 順序表的應用:大整數求和
2.7.2 單鏈表的應多項式加法運算
2.8 總結與提高
2.9 習題二
第3章 枝和隊列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的順序存儲結構
3.1.3 棧的鏈式存儲結構
3.1.4 棧的特性分析
3.2 隊列
3.2.1 隊列的定義
3.2.2 循環隊列
3.2.3 鏈式隊列
3.2.4 雙端隊列
3.3 棧和隊列的應用
3.3.1 括號匹配
3.3.2 表達式求解
3.3.3 隊列在層次遍歷中的應用
3.4 遞歸
3.4.1 遞歸的概念
3.4.2 遞歸算法的設計
3.4.3 轉化遞歸算法為非遞歸算法
3.5 總結與提高
3.6 習題三
第4章 數組和字符串
4.1 數組的定義
4.2 數組的順序存儲結構
4.2.1 一維數組的順序存儲
4.2.2 多維數組的順序存儲
4.3 矩陣的壓縮存儲
4.3.1 特殊矩陣的壓縮存儲
4.3.2 三對角矩陣的壓縮存儲
4.3.3 稀疏矩陣的壓縮存儲
4.4 稀疏矩陣的運算
4.4.1 稀疏矩陣的轉置
4.4.2 稀疏矩陣的乘法
4.5 字符串
4.5.1 串的基本概念
4.5.2 串的存儲結構
4.5.3 串的模式匹配算法
4.6 總結與提高
4.7 習題四
第5章 樹
5.1 樹的定義及基本術語
5.2 N叉樹
5.2.1 N叉樹的概念
5.2.2 N叉樹的性質
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.5.3 二叉樹析構函數
5.5.4 遞歸遍歷算法的應用舉例
5.5.5 由遍歷序列恢復二叉樹
5.5.6 二叉樹遍歷的非遞歸算法
5.6 線索二叉樹
5.6.1 線索二叉樹的定義
5.6.2 中序線索二叉樹的建立和遍歷
5.6.3 中序線索二叉樹插入
5.6.4 中序線索二叉樹刪除
5.6.5 前序與後序線索二叉樹
5.6.6 線索二叉樹算法的應用舉例
5.7 二叉排序樹
5.7.1 二叉排序樹的基本概念
5.7.2 二叉排序樹的插入
5.7.3 二叉排序樹的刪除
5.7.4 二叉排序樹查找分析
5.7.5 二叉排序樹算法的應用舉例
5.8 平衡二叉樹
5.8.1 平衡二叉樹基本概念
5.8.2 平衡化旋轉
5.8.3 平衡二叉樹的插入
5.8.4 平衡二叉樹的刪除
5.8.5 平衡二又樹算法的應用舉例
5.9 樹、森林與二叉樹的關繫
5.9.1 樹的存儲結構
5.9.2 森林與二叉樹的轉換
5.9.3 樹與森林的遍歷
5.10 Huffman樹及其應用
5.10.1 帶權路徑長度的概念
5.10.2 Huffman樹的構造
5.10.3 Huffman樹結構定義及算法實現
5.10.4 Huffman編碼
5.11 總結與提高
5.12 習題五
第6章 圖
6.1 圖的基本概念
6.1.1 圖的基本概念與術語
6.1.2 圖的基本操作
6.2 圖的存儲結構
6.2.1 鄰接矩陣
6.2.2 鄰接表
6.2.3 有向圖的十字鏈表表示
6.2.4 無向圖的鄰接多重表表示
6.3 圖的遍歷
6.3.1 深度優先搜索
6.3.2 廣度優先搜索
6.4 生成樹
6.4.1 MST性質
6.4.2 Kruskal算法
6.4.3 Prim算法
6.5 路徑規劃
6.5.1 最短路徑
6.5.2 Dijkstra算法
6.5.3 Floyd算法
6.6 拓撲排序
6.7 關鍵路徑
6.8 總結與提高
6.9 習題六
第7章 查找
7.1 基本概念
7.2 線性表查找
7.2.1 順序查找
7.2.2 線性鏈表上的順序查找
7.3 折半查找法
7.3.1 一般的折半查找法
7.3.2 次優查找樹:折半查找的改進方法
7.4 索引查找
7.4.1 索引順序表與分塊查找
7.4.2 多級索引結構與m叉查找樹
7.4.3 B樹的概念
7.4.4 B樹上的查找
7.4.5 B樹上的插入
7.4.6 B樹上的刪除
7.4.7 B樹析構函數
7.4.8 B樹層序遍歷輸出
7.4.9 B樹操作應用舉例
7.4.10 B+樹
7.5 散列表及其查找
7.5.1 散列的概念
7.5.2 散列函數設計
7.5.3 處理衝突的方法
7.5.4 散列表查找性能分析
7.6 總結與提高
7.7 習題七
第8章 排序
8.1 基本概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希爾排序
8.3 交換排序
8.3.1 冒泡排序
8.3.2 快速排序
8.4 選擇排序
8.4.1 簡單選擇排序
8.4.2 堆排序
8.5 歸並排序
8.5.1 二路歸並
8.5.2 二路歸並遞歸排序算法
8.6 分配排序
8.6.1 桶排序
8.6.2 基數排序
8.6.3 關鍵字分解
8.6.4 鏈式基數排序
8.7 內部排序算法比較
8.7.1 排序方法的下界
8.7.2 各種內排序方法的比較
8.8 總結與提高
8.9 習題八
參考文獻
內容簡介
“數據結構”是計算機專業教學計劃中的核心課程,也是計算機專業考研和水平等級考試的必考科目。本書共8章,內容包括緒論、線性結構、棧和隊列、數組和字符串、樹、圖、查找和排序等。本書將數據結構知識點、實踐操作和可視化交互展示融為一體,不僅強調數據結構的基本概念和程序實現,而且將增強現實(Augmented Reality,AR)技術用於數據結構教學過程,突破了傳統教材的圖文講解方式,依托視覺、聽覺等多模態模式來獲取交互信息,彌補多媒體教學的不足,增強了學習效果。本書提供了涵蓋所有知識點的AR可視化展示,給出了許多經典算法和大量C++代碼,每章均附有小結和各類練習題,便於總結提高。
本書內容豐富,AR可視化效果逼真,知識點脈絡清晰,代碼實用性強,適合高等院校計算機專業和相關專業的本科牛和研究生使用。