《數據結構——從概念到C實現》是2017年2月清華大學出版社出版的圖書，作者是王紅梅、皮德常。
基本介紹
內容簡介,圖書目錄,
內容簡介
數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹了數據結構、算法以及抽象數據類型的概念；介紹了線性表、棧和佇列、字元串和多維數組、樹和二叉樹、圖等常用數據結構；討論了基本的查找和排序技術。
本書合理規劃教學內容，梳理知識單元及其拓撲結構，兼顧概念層和實現層，既強調了數據結構的基本概念和原理方法，又注重了數據結構的程式實現和實際運用，在提煉基礎知識的同時，進行了適當的擴展和提高。
本書內容豐富，層次清晰，深入淺出，結合實例，可作為計算機及相關專業數據結構課程的教材，也可供從事計算機軟體開發和套用的工程技術人員參考和閱讀。
圖書目錄
第1章 緒論1
1.1 問題求解與程式設計 2
1.1.1 程式設計的一般過程 2
1.1.2 數據結構在程式設計中的作用 4
1.1.3 算法在程式設計中的作用 6
1.1.4 本書討論的主要內容 7
1.2 數據結構的基本概念 8
1.2.1 數據結構 8
1.2.2 抽象數據類型 11
1.3 算法的基本概念 12
1.3.1 算法及算法的特性 12
1.3.2 算法的描述方法 14
1.4 算法分析 15
1.4.1 算法的時間複雜度 16
1.4.2 算法的空間複雜度 17
1.4.3 算法分析舉例 18
1.5 擴展與提高 20
1.5.1 從數據到大數據 20
1.5.2 算法分析的其他漸進符號 22
習題123
第2章 線性表 25
2.1 引言 26
2.2 線性表的邏輯結構 27
2.2.1 線性表的定義 27
2.2.2 線性表的抽象數據類型定義 27
2.3 線性表的順序存儲結構及實現 29
2.3.1 順序表的存儲結構定義 29
2.3.2 順序表的實現 30
2.3.3 順序表的使用 34
2.4 線性表的連結存儲結構及實現 35
2.4.1 單鍊表的存儲結構定義 35
2.4.2 單鍊表的實現 37
2.4.3 單鍊表的使用 44
2.4.4 雙鍊表 45
2.4.5 循環鍊表 47
2.5 順序表和鍊表的比較 48
2.6 擴展與提高 48
2.6.1 線性表的靜態鍊表存儲 48
2.6.2 順序表的動態分配方式 51
2.7 套用實例 52
2.7.1 約瑟夫環問題 52
2.7.2 一元多項式求和 55
習題2 59
第3章 棧和佇列 63
3.1 引言 64
3.2 棧 65
3.2.1 棧的邏輯結構 65
3.2.2 棧的順序存儲結構及實現 66
3.2.3棧的連結存儲結構及實現 68
3.2.4順序棧和鏈棧的比較 71
3.3 佇列 72
3.3.1 佇列的邏輯結構 72
3.3.2 佇列的順序存儲結構及實現 73
3.3.3 佇列的連結存儲結構及實現 77
3.3.4 循環佇列和鏈佇列的比較 80
3.4 擴展與提高 81
3.4.1 兩棧共享空間 81
3.4.2 雙端佇列 82
3.5 套用舉例 83
3.5.1 括弧匹配問題 83
3.5.2 表達式求值 85
習題3 88
第4章 字元串和多維數組 91
4.1 引言 92
4.2 字元串 92
4.2.1 字元串的邏輯結構 92
4.2.2 字元串的存儲結構 94
4.2.3 模式匹配 94
4.3 多維數組 98
4.3.1 數組的邏輯結構 98
4.3.2 數組的存儲結構與定址 99
4.4 矩陣的壓縮存儲 100
4.4.1 特殊矩陣的壓縮存儲 100
4.4.2 稀疏矩陣的壓縮存儲 102
4.5 擴展與提高 105
4.5.1 稀疏矩陣的轉置運算 105
4.5.2 廣義表 107
4.6 套用實例 111
4.6.1 發紙牌 111
4.6.2 八皇后問題 112
習題4 115
第5章 樹和二叉樹 119
5.1 引言 120
5.2 樹的邏輯結構 121
5.2.1 樹的定義和基本術語 121
5.2.2 樹的抽象數據類型定義 123
5.2.3 樹的遍歷操作 123
5.3 樹的存儲結構 124
5.3.1 雙親表示法 124
5.3.2 孩子表示法 125
5.3.3 孩子兄弟表示法 126
5.4 二叉樹的邏輯結構 127
5.4.1 二叉樹的定義 127
5.4.2 二叉樹的基本性質 129
5.4.3 二叉樹的抽象數據類型定義 130
5.4.4 二叉樹的遍歷操作 131
5.5 二叉樹的存儲結構 133
5.5.1 順序存儲結構 133
5.5.2 二叉鍊表 134
5.5.3 三叉鍊表 138
5.6 森林 138
5.6.1 森林的邏輯結構 138
5.6.2 樹、森林與二叉樹的轉換 139
5.7 最優二叉樹 141
5.7.1 哈夫曼算法 141
5.7.2 哈夫曼編碼 143
5.8 擴展與提高 145
5.8.1 二叉樹遍歷的非遞歸算法 145
5.8.2 線索二叉樹 148
5.9 套用實例 151
5.9.1 堆與優先佇列 151
5.9.2 並查集 154
習題5 155
第6章 圖 159
6.1 引言 160
6.2 圖的邏輯結構 161
6.2.1 圖的定義和基本術語 161
6.2.2 圖的抽象數據類型定義 163
6.2.3 圖的遍歷操作 164
6.3 圖的存儲結構及實現 167
6.3.1 鄰接矩陣 167
6.3.2 鄰接表 170
6.3.3 鄰接矩陣和鄰接表的比較 174
6.4 最小生成樹 175
6.4.1 Prim算法 176
6.4.2 Kruskal算法 178
6.5 最短路徑 182
6.5.1 Dijkstra算法 183
6.5.2 Floyd算法 185
6.6 有向無環圖及其套用 187
6.6.1 AOV網與拓撲排序 187
6.6.2 AOE網與關鍵路徑 190
6.7 擴展與提高 193
6.7.1 圖的其他存儲方法193
6.7.2 圖的連通性 194
6.8 套用實例 196
6.8.1 七巧板塗色問題 196
6.8.2 醫院選址問題 198
習題6 200
第7章 查找技術 205
7.1 概述 206
7.1.1 查找的基本概念 206
7.1.2 查找算法的性能 207
7.2 線性表的查找技術 207
7.2.1 順序查找 207
7.2.2 折半查找 208
7.3 樹表的查找技術 211
7.3.1 二叉排序樹 211
7.3.2 平衡二叉樹 217
7.3.3 B樹 220
7.4 散列表的查找技術 225
7.4.1 散列查找的基本思想 225
7.4.2 散列函式的設計 226
7.4.3 處理衝突的方法 227
7.4.4 散列查找的性能分析 231
7.4.5 開散列表與閉散列表的比較 232
7.5 各種查找方法的比較 232
7.6 擴展與提高 233
7.6.1 順序查找的改進——分塊查找 233
7.6.2 折半查找的改進——插值查找 234
7.6.3 B樹的改進——B+樹 235
習題7 236
第8章 排序技術 239
8.1 概述 240
8.1.1 排序的基本概念 240
8.1.2 排序算法的性能 241
8.2 插入排序 241
8.2.1 直接插入排序 241
8.2.2 希爾排序 243
8.3 交換排序 245
8.3.1 起泡排序 245
8.3.2 快速排序 247
8.4 選擇排序 250
8.4.1 簡單選擇排序 250
8.4.2 堆排序 252
8.5 歸併排序 256
8.5.1 二路歸併排序的遞歸實現 256
8.5.2 二路歸併排序的非遞歸實現 257
8.6 各種排序方法的比較 259
8.7 擴展與提高 261
8.7.1 排序問題的時間下界 261
8.7.2 基數排序 262
習題8 264
附錄A 預備知識 269
A.1 數學術語 269
A.2 級數求和 269
A.3 集合 270
A.4 關係 271
附錄B C語言基本語法 273
B.1 程式結構 273
B.2 數據的基本表現形式——常量和變數 274
B.3 數據類型 275
B.4 控制語句 277
B.5 函式 278
B.6 動態存儲分配 281
附錄C 辭彙索引 283
參考文獻 287
