《數據結構》是由管致錦、徐慧、陳德裕編著,2010年清華大學出版社出版的普通高校本科計算機專業特色精選教材。該教材可作為計算機類及其相關專業的教材,也可供從事計算機工程與套用的科技工作者參考。
全書共9章,主要內容包括:緒論,線性表,特殊線性表,串及其模式匹配,廣義線性表,樹和二叉樹,圖,查找,排序。
基本介紹
- 書名:數據結構
- 作者:管致錦、徐慧、陳德裕
- ISBN:9787302214755
- 類別:普通高校本科計算機專業特色精選教材
- 頁數:288頁
- 出版社:清華大學出版社
- 出版時間:2010年3月1日
- 裝幀:平裝
- 開本:16開
- 字數:471千字
- CIP核字號:2010026130
成書過程
修訂過程
出版工作
責任編輯 | 責任校對 | 責任印製 |
---|---|---|
袁勤勇、李瑋琪 | 李健壯 | 李紅英 |
內容簡介
教材目錄
第1章 緒論11.1 數據結構的概念1 1.1.1 引言1 1.1.2 數據結構的發展及其在計算機科學中所處的地位2 1.1.3 什麼是數據結構3 1.1.4 有關概念和術語3 1.2 數據類型和抽象數據類型6 1.2.1 數據類型6 1.2.2 抽象數據類型6 1.3 算法和算法分析6 1.3.1 算法特性7 1.3.2 算法描述7 1.3.3 算法性能分析與度量8 第2章 線性表11 2.1 線性表的類型定義11 2.2 線性表的順序存儲結構及實現13 2.2.1 線性表的順序存儲13 2.2.2 順序表的實現14 2.3 線性表的鏈式存儲結構及實現18 2.3.1 線性表的鏈式存儲18 2.3.2 單鍊表的實現18 2.3.3 其他形式的鍊表25 2.4 線性表的其他存儲方法27 2.4.1 順序存儲與鏈式存儲的比較27 2.4.2 靜態鍊表28 2.4.3 間接定址29 2.5 線性表套用舉例29 第3章 特殊線性表35 3.1 棧35 3.1.1 棧的邏輯結構35 3.1.2 棧的順序存儲結構及實現37 3.1.3 棧的鏈式存儲及實現40 3.1.4 順序棧和鏈棧的比較42 3.1.5 棧的套用舉例42 3.2 佇列48 3.2.1 佇列的邏輯結構49 3.2.2 佇列的順序存儲結構及實現50 3.2.3 佇列的鏈式存儲及實現54 3.2.4 佇列的套用57 第4章 串及其模式匹配59 4.1 串的定義59 4.1.1 串的相關概念59 4.1.2 串的抽象數據類型定義60 4.2 串的存儲結構61 4.2.1 串的順序存儲結構62 4.2.2 串的鏈式存儲結構62 4.2.3 串的索引存儲結構63 4.2.4 串的堆存儲64 4.3 順序串的實現64 4.3.1 常用C++字元串函式64 4.3.2 串類65 4.4 串操作舉例71 4.5 模式匹配72 第5章 廣義線性表79 5.1 數組79 5.1.1 數組的定義79 5.1.2 數組的順序存儲81 5.2 矩陣的壓縮存儲83 5.2.1 特殊矩陣的壓縮存儲83 5.2.2 稀疏矩陣的壓縮存儲85 5.2.3 稀疏矩陣的運算87 5.3 廣義表97 5.3.1 廣義表的邏輯結構97 5.3.2 廣義表的存儲100 5.3.3 廣義表的實現102 第6章 樹和二叉樹107 6.1 樹的定義和基本術語107 6.2 二叉樹109 6.2.1 二叉樹的基本概念109 6.2.2 二叉樹的主要性質114 6.3 二叉樹的存儲結構與實現116 6.3.1 二叉樹的存儲116 6.3.2 二叉樹的基本操作及實現118 6.4 二叉樹的遍歷126 6.4.1 二叉樹的遍歷方法及遞歸實現126 6.4.2 二叉樹遍歷的非遞歸實現131 6.4.3 由遍歷序列恢復二叉樹134 6.4.4 不用棧的二叉樹遍歷的非遞歸方法136 6.5 線索二叉樹137 6.5.1 線索二叉樹及其結構137 6.5.2 線索二叉樹的基本操作實現138 | 6.6 二叉樹的套用143 6.6.1 二叉樹遍歷的套用143 6.6.2 最優二叉樹--哈夫曼樹145 6.7 樹151 6.7.1 樹的基本操作151 6.7.2 樹的存儲結構153 6.8 樹、森林與二叉樹的轉換157 6.8.1 樹轉換為二叉樹157 6.8.2 森林轉換為二叉樹158 6.8.3 二叉樹轉換為樹和森林159 6.9 樹和森林的遍歷159 6.9.1 樹的遍歷159 6.9.2 森林的遍歷160 6.10 樹的套用160 6.10.1 判定樹161 6.10.2 集合的表示162 6.10.3 求關係等價類問題164 第7章 圖167 7.1 圖的基本概念167 7.2 圖的存儲結構及實現172 7.2.1 鄰接矩陣172 7.2.2 鄰接表174 7.2.3 十字鍊表178 7.2.4 鄰接多重表181 7.3 圖的遍歷182 7.3.1 深度優先搜尋183 7.3.2 廣度優先搜尋185 7.4 圖的連通性186 7.4.1 無向圖的連通性186 7.4.2 有向圖的連通性187 7.4.3 生成樹和生成森林187 7.4.4 關節點和重連通分量190 7.5 最小生成樹193 7.5.1 最小生成樹的基本概念193 7.5.2 構造最小生成樹的Prim算法194 7.5.3 構造最小生成樹的Kruskal算法196 7.6 最短路徑199 7.6.1 從一個源點到其他各點的最短路徑199 7.6.2 每一對頂點之間的最短路徑202 7.7 有向無環圖及其套用204 7.7.1 有向無環圖的概念204 7.7.2 AOV網與拓撲排序205 7.7.3 AOE圖與關鍵路徑210 第8章 查找217 8.1 基本概念與術語217 8.2 靜態查找表219 8.2.1 靜態查找表結構219 8.2.2 順序查找220 8.2.3 有序表的折半查找222 8.2.4 有序表的其他查找方法225 8.2.5 分塊查找226 8.3 動態查找表227 8.3.1 二叉排序樹227 8.3.2 平衡二叉樹(AVL樹)234 8.3.3 B-樹和B+樹240 8.4 哈希表查找(雜湊法、散列法)245 8.4.1 哈希表與哈希方法245 8.4.2 常用的哈希函式246 8.4.3 處理衝突的方法248 8.4.4 哈希表的查找分析250 第9章 排序257 9.1 基本概念257 9.2 插入排序258 9.2.1 直接插入排序258 9.2.2 折半插入排序260 9.2.3 表插入排序261 9.2.4 希爾排序264 9.3 交換排序266 9.3.1 冒泡排序267 9.3.2 快速排序268 9.4 選擇排序271 9.4.1 簡單選擇排序272 9.4.2 樹形選擇排序273 9.4.3 堆排序276 9.5 歸併排序279 9.6 基數排序281 9.6.1 多關鍵字排序281 9.6.2 鏈式基數排序282 9.7 各種內部排序方法的比較286 參考文獻288 |
教學資源
- 配套教材
書名 | 書號 | 出版社 | 出版時間 | 作者 |
---|---|---|---|---|
《數據結構學習指導與習題集》 | 9787302214779 | 清華大學出版社 | 2010.03.01 | 陳德裕 |
- 課程資源