數據結構(2016年科學出版社出版的圖書)

數據結構(2016年科學出版社出版的圖書)

本詞條是多義詞,共76個義項
更多義項 ▼ 收起列表 ▲

《數據結構》是2016年科學出版社出版的圖書,作者是吳陳。

基本介紹

  • 書名:數據結構
  • 作者:吳陳
  • 出版社:科學出版社
  • 出版時間:2016年11月
  • ISBN:9787030505903 
內容簡介,圖書目錄,

內容簡介

本書系統地介紹了線性表、棧、佇列、串、數組、廣義表、樹、二叉樹、圖等常用數據結構以及查找、排序、索引等算法設計技術,給出了較多的數據結構套用實例及其算法在計算機中的存儲和實現,分析了複雜度。書中各種算法採用C++語言描述,既適合在MS VC下使用,也適合在MS VC++.NET中使用。全書注重程式設計風格,可讀性和實用性強。

圖書目錄

前言
第1章 緒論 1
1.1 引言 1
1.2 數據結構中的基本概念和術語 4
1.3 算法和算法描述 12
1.3.1 算法的概念 12
1.3.2 算法的描述方法 13
1.4 算法的評價方法 16
1.4.1 評價算法的一般原則 16
1.4.2 算法的複雜度 17
1.5 C++中的typedef、模板與異常處理 24
本章小結和學習要點 33
習題1 34
思考題1 36
上機題1 36
第2章 線性表 37
2.1 線性表及其基本操作 37
2.1.1 線性表的邏輯結構定義 37
2.1.2 線性表的抽象數據類型定義 38
2.2 線性表的順序存儲結構——順序表 40
2.2.1 順序表的基本表示 40
2.2.2 順序表模板類表示下的基本操作 44
2.2.3 順序表表示線性表下的其他操作 49
2.2.4 間接定址方式及其他方式實現的順序表 56
2.3 線性表的鏈式存儲結構 56
2.3.1 單鍊表 56
2.3.2 循環單鍊表 67
2.3.3 雙鍊表及循環雙鍊表 68
2.3.4 靜態鍊表 71
2.3.5 間接定址方式實現的單鍊表 73
2.4 線性表的套用 73
2.4.1 一元多項式的表示及相加 73
2.4.2 算法舉例 77
2.5 順序表和單鍊表的比較 82
2.5.1 時間性能比較 82
2.5.2 空間性能比較 82
本章內容小結和學習要點 83
習題2 84
思考題2 88
上機題2 88
第3章 棧和佇列 89
3.1 棧 89
3.1.1 棧的邏輯結構 89
3.1.2 棧的順序存儲結構——順序棧 91
3.1.3 棧的鏈式存儲結構 96
3.2 佇列 99
3.2.1 佇列的邏輯結構 99
3.2.2 佇列的鏈式存儲結構 102
3.2.3 佇列的順序存儲結構 106
3.3 棧和佇列的綜合套用 115
3.3.1 算術表達式求值 115
3.3.2 用順序棧作輔助存儲結構求迷宮的一條路徑解 124
本章內容小結和學習要點 126
習題3 126
思考題3 128
上機題3 129
第4章 字元串 130
4.1 串及其運算 130
4.2 串的順序存儲結構 134
4.3 串的鏈式存儲結構 137
4.4 串的模式匹配算法 138
4.5 串的套用 149
4.5.1 大整數加法 149
4.5.2 名字特徵數 152
本章小結和學習要點 153
習題4 153
思考題4 154
上機題4 154
第5章 數組和廣義表 155
5.1 數組的定址和運算 155
5.2 矩陣的壓縮存儲 159
5.2.1 特殊矩陣 160
5.2.2 稀疏矩陣 163
5.3 廣義表 170
5.3.1 廣義表的概念 170
5.3.2 廣義表的存儲結構 172
5.3.3 廣義表的操作 174
本章小結和學習要點 178
習題5 178
思考題5 180
上機題5 180
第6章 樹和二叉樹 182
6.1 樹的基本定義 182
6.2 二叉樹 186
6.2.1 二叉樹的定義和基本運算 187
6.2.2 二叉樹的性質 189
6.2.3 二叉樹的存儲結構 192
6.3 二叉樹的建立和遍歷 197
6.3.1 遍歷二叉樹 197
6.3.2 建立和釋放一棵二叉樹的二叉鍊表 202
6.3.3 二叉鍊表其他函式和主函式 204
6.3.4 二叉樹的三種遍歷的非遞歸算法 206
6.3.5 二叉樹的其他算法例 210
6.4 線索二叉樹 213
6.5 樹和森林 219
6.6 哈夫曼樹及其套用 228
本章小結和學習要點 237
習題6 237
思考題6 242
上機題6 242
第7章 圖的數據結構 243
7.1 圖的定義、基本術語和操作 243
7.2 圖的存儲結構 248
7.2.1 鄰接矩陣 248
7.2.2 邊數組 252
7.2.3 鄰接表 252
7.2.4 圖的十字鍊表表示 258
7.2.5 鄰接多重表 260
7.3 圖的遍歷 262
7.3.1 深度優先搜尋遍歷圖 262
7.3.2 廣度優先搜尋遍歷圖 266
7.3.3 圖的遍歷 268
7.4 圖的連通性和生成樹 270
7.4.1 圖的連通性和連通分量 270
7.4.2 生成樹和生成森林 272
7.4.3 最小生成樹 274
7.5 最短路徑問題 283
7.5.1 求某個源點到其餘各頂點的最短路徑 283
7.5.2 求帶權圖中每一對頂點之間的最短路徑 288
7.6 拓撲排序 291
7.7 求關鍵路徑 298
7.8 圖的遍歷算法的套用 305
7.8.1 求過給定點v長度大於或等於k的簡單有向迴路 305
7.8.2 地圖四色問題 306
本章小結和學習要點 308
習題7 308
思考題7 313
上機題7 313
第8章 排序 315
8.1 排序的基本概念和術語 315
8.2 插入排序 318
8.2.1 直接插入排序 318
8.2.2 謝爾排序 322
8.3 選擇排序 324
8.3.1 簡單選擇排序 325
8.3.2 改進的簡單選擇排序 326
8.3.3 堆排序 327
8.4 交換排序 333
8.4.1 冒泡排序 333
8.4.2 快速排序 335
8.5 歸併排序 340
8.6 基數排序 342
8.7 各種內部排序算法的比較 346
本章小結和學習要點 349
習題8 350
思考題8 355
上機題8 355
第9章 查找 356
9.1 查找的基本概念和術語 356
9.2 以順序表為基礎的查找 358
9.2.1 順序表的順序查找 358
9.2.2 有序表的二分法查找 361
9.2.3 靜態樹表的查找 366
9.2.4 分塊查找 370
9.3 樹形結構的查找 373
9.3.1 二叉排序樹 373
9.3.2 平衡二叉樹 383
9.4 散列表的查找 391
9.4.1 散列技術中的主要概念 391
9.4.2 散列函式的構造方法 392
9.4.3 衝突的處理方法 396
9.4.4 散列表上的查找算法 400
9.4.5 散列表查找的時間複雜度分析 400
本章小結和學習要點 405
習題9 405
思考題9 408
上機題9 408
第10章 索引技術 409
10.1 索引的基本概念 409
10.2 線性索引 410
10.2.1 稠密索引 410
10.2.2 稀疏索引 411
10.2.3 多重表 413
10.2.4 倒排表 413
10.3 樹形索引 415
10.3.1 B-樹 415
10.3.2 B+樹 424
10.3.3 鍵樹 425
本章內容小結和學習要點 432
習題10 432
思考題10 434
上機題10 434
主要參考文獻 435
附錄上機實驗報告格式 437
索引 439

相關詞條

熱門詞條

聯絡我們