《數據結構算法解析》是2021年清華大學出版社出版的圖書，作者是殷人昆。本書是根據教育部高等學校計算機科學與技術專業教指委公布的《高等學校計算機科學與技術專業公共核心知識體系與課程》和教育部考試中心公布的《全國碩士研究生入學考試計算機科學與技術專業基礎綜合考試聯考考試大綱》編寫而成，精選1130多個算法，是數據結構算法的輔導教材和計算機專業考研輔導教材。
基本介紹
- 中文名：數據結構算法解析
- 作者：殷人昆
- 出版社：清華大學出版社
- ISBN：9787302575122
內容簡介,圖書目錄,作者簡介,
內容簡介
本書共分8章。第1章是介紹數據結構和算法的基本概念和算法分析的簡單方法，以及C語言編程的要點。本書既可作為普通大學計算機科學與技術專業和軟體工程專業本科生學習數據結構與算法課程的教材，也可以作為計算機專業考研的輔導教材或其他計算機或軟體考試的複習教材，還可以作為供從事計算機或軟體系統開發的人員參考的學習資料。
圖書目錄
第1章 數據結構緒論 1
1.1 簡單的編程問題 1
1.2 簡單的算法設計 4
1.2.1 枚舉法編程 4
1.2.2 遞推法編程 8
1.2.3 遞歸法編程 11
1.2.4 疊代法編程 13
1.2.5 動態規劃法編程 16
1.3 簡單的算法分析 17
1.3.1 語句的執行頻度 17
1.3.2 時間複雜度度量 18
1.3.3 有關算法分析的選擇題 20
第2章 線性表 26
2.1 線性表的概念 26
2.1.1 線性表的定義 26
2.1.2 線性表的套用 26
2.2 順序表 28
2.2.1 順序表的結構 28
2.2.2 順序表的基本操作 28
2.2.3 順序表的相關算法 31
2.3 鍊表 42
2.3.1 單鍊表的結構 42
2.3.2 單鍊表的基本運算 42
2.3.3 單鍊表的相關算法 50
2.4 循環單鍊表 80
2.4.1 循環單鍊表的定義 80
2.4.2 循環單鍊表的基本運算 81
2.4.3 循環單鍊表的相關算法 86
2.5 雙向鍊表 90
2.5.1 雙向鍊表的定義與結構 90
2.5.2 雙向鍊表的基本運算 90
2.5.3 雙向鍊表的相關算法 93
2.5.4 異或雙向鍊表 99
2.6 靜態鍊表 105
2.6.1 靜態鍊表的結構定義 105
2.6.2 靜態鍊表的基本運算 105
2.7 線性表的套用實例 109
2.7.1 約瑟夫問題求解 109
2.7.2 用位向量表示集合 111
2.7.3 用有序鍊表表示集合 115
2.7.4 多項式的鍊表存儲表示 124
2.7.5 大整數運算 136
第3章 棧和佇列 146
3.1 棧 146
3.1.1 棧的概念 146
3.1.2 順序棧 148
3.1.3 鏈式棧 160
3.2 佇列 165
3.2.1 佇列的定義及基本運算 165
3.2.2 順序佇列 166
3.2.3 鏈式佇列 177
3.2.4 雙端佇列 182
3.2.5 優先佇列 188
3.3 棧和佇列的套用 191
3.3.1 棧在數制轉換和括弧配對中的套用 191
3.3.2 棧在表達式計算中的套用 193
3.3.3 棧和佇列的其他套用 199
3.3.4 優先佇列的套用 209
3.4 棧與遞歸 214
3.4.1 遞歸的概念 214
3.4.2 分治法與遞歸 215
3.4.3 減治法與遞歸 217
3.4.4 回溯法與遞歸 227
3.4.5 貪心法 234
3.4.6 動態規劃法 235
第4章 多維數組、字元串與廣義表 240
4.1 多維數組 240
4.1.1 一維數組 240
4.1.2 二維數組 263
4.2 特殊矩陣與稀疏矩陣 277
4.2.1 特殊矩陣與稀疏矩陣的概念 277
4.2.2 特殊矩陣相關的算法 281
4.2.3 稀疏矩陣相關的算法 287
4.3 字元串 301
4.3.1 字元串的概念 301
4.3.2 順序串相關的算法 304
4.3.3 堆分配串相關的算法 308
4.3.4 塊鏈存儲字元串相關的算法 323
4.3.5 模式匹配算法 327
4.4 廣義表 333
4.4.1 廣義表的概念 333
4.4.2 頭尾表示廣義表相關的算法 335
4.4.3 層次表示廣義表相關的算法 342
第5章 樹與二叉樹 348
5.1 樹的基本概念 348
5.1.1 樹的概念 348
5.1.2 樹的雙親存儲表示 349
5.1.3 樹的子女鍊表存儲表示 353
5.1.4 樹的子女-兄弟鍊表存儲表示 361
5.1.5 樹的標準鍊表表示 367
5.1.6 樹的廣義表存儲表示 367
5.2 二叉樹及其存儲表示 370
5.2.1 二叉樹的概念 370
5.2.2 二叉樹的順序存儲結構 372
5.2.3 二叉樹的鏈式存儲結構 376
5.3 二叉樹的遍歷 384
5.3.1 二叉樹遍歷的基本運算 384
5.3.2 創建二叉樹的算法 388
5.3.3 二叉樹遍歷的非遞歸算法 403
5.3.4 二叉樹遍歷相關的算法 417
5.3.5 表達式樹 445
5.4 線索二叉樹 453
5.4.1 線索二叉樹的結構定義 453
5.4.2 中序線索二叉樹 454
5.4.3 先序和後序線索二叉樹 461
5.5 樹與森林的遍歷 467
5.5.1 樹與森林遍歷的概要 467
5.5.2 基於樹的雙親表示的遍歷算法 468
5.5.3 基於子女鍊表表示的樹的遍歷算法 472
5.5.4 基於子女-兄弟鍊表表示的樹的遍歷算法 476
5.6 Huffman樹 486
5.6.1 Huffman樹及其結構定義 486
5.6.2 Huffman樹相關的算法 487
5.6.3 Huffman編碼相關的算法 489
5.6.4 判定樹相關的算法 493
5.7 堆 495
5.7.1 堆的結構定義 495
5.7.2 小根堆的基本運算 495
5.7.3 小根堆相關的算法 498
5.8 並查集 504
5.8.1 並查集的結構定義 504
5.8.2 並查集主要操作的實現 505
第6章 圖 509
6.1 圖的基本概念 509
6.1.1 圖的基本定義與特徵 509
6.1.2 圖算法實例 510
6.2 圖的存儲表示 511
6.2.1 圖的鄰接矩陣表示 511
6.2.2 圖的鄰接表表示 522
6.2.3 無向圖的鄰接多重表表示 534
6.2.4 有向圖的十字鍊表表示 538
6.2.5 關聯矩陣 541
6.3 圖的遍歷 544
6.3.1 深度優先搜尋 544
6.3.2 廣度優先搜尋 549
6.3.3 圖頂點間的路徑 550
6.3.4 圖的連通性與生成樹 565
6.3.5 雙連通圖的關節點 578
6.4 小生成樹 579
6.4.1 小生成樹的概念與定義 579
6.4.2 小生成樹相關的算法 580
6.5 短路徑 592
6.5.1 短路徑的概念 592
6.5.2 單源短路徑相關的算法 593
6.5.3 所有頂點間短路徑相關的算法 605
6.6 拓撲排序和關鍵路徑 613
6.6.1 AOV網與拓撲排序 613
6.6.2 AOE網與關鍵路徑 618
6.7 圖的其他套用 623
6.7.1 算術表達式的計算 623
6.7.2 二部圖 627
6.7.3 渡河問題 629
6.7.4 四色問題 633
第7章 查找 635
7.1 查找的概念與簡單查找方法 635
7.1.1 查找的概念 635
7.1.2 順序查找 635
7.1.3 折半查找 640
7.1.4 斐波那契查找與插值查找 644
7.1.5 靜態樹表查找 646
7.1.6 跳表 651
7.2 二叉查找樹 655
7.2.1 二叉查找樹的概念 655
7.2.2 二叉查找樹基本運算的實現 655
7.2.3 二叉查找樹相關的算法 659
7.2.4 中序線索二叉查找樹 677
7.3 AVL樹 680
7.3.1 AVL樹的概念 680
7.3.2 AVL樹相關算法 680
7.4 B樹與B 樹 690
7.4.1 分塊查找與索引表 690
7.4.2 B樹 696
7.4.3 B 樹 703
7.5 其他查找樹 711
7.5.1 紅黑樹 711
7.5.2 伸展樹 722
7.5.3 雙鏈樹 727
7.5.4 Trie樹 732
7.6 散列法 737
7.6.1 散列法的概念 737
7.6.2 散列法的套用 739
7.6.3 用開地址法解決衝突 743
7.6.4 用鏈地址法解決衝突 749
第8章 排序 753
8.1 排序的概念與算法 753
8.1.1 排序的概念 753
8.1.2 計數排序算法 753
8.2 插入排序 755
8.2.1 直接插入排序 755
8.2.2 折半插入排序 758
8.2.3 希爾排序 760
8.3 交換排序 761
8.3.1 逆序與交換 761
8.3.2 起泡排序 763
8.3.3 快速排序 769
8.4 選擇排序 783
8.4.1 簡單選擇排序 783
8.4.2 堆排序 789
8.4.3 錦標賽排序 793
8.5 歸併排序 797
8.5.1 兩路歸併 797
8.5.2 遞歸二路歸併排序 805
8.5.3 疊代的二路歸併排序 807
8.6 桶排序 813
8.6.1 多排序碼的概念 813
8.6.2 MSD桶排序 813
8.6.3 LSD桶排序 817
8.7 鍊表排序 819
8.7.1 鍊表排序方法 819
8.7.2 雙向鍊表排序 826
8.7.3 靜態鍊表排序 827
8.8 其他排序算法 834
8.8.1 選擇算法 834
8.8.2 地址排序 837
8.9 外排序 841
8.9.1 輸入輸出緩衝區 841
8.9.2 多路平衡歸併 843
8.9.3 初始歸併段的生成 845
8.9.4 磁帶歸併排序 853
8.9.5 歸併樹 855
參考文獻 859
作者簡介
殷人昆，清華大學計算機系教授，1985年赴日本國東京理科大學做訪問學者，研究方向為軟體工程過程的質量管理和軟體產品的質量評價。主要教學工作為計算機系大學本科“數據結構”、“軟體工程”和研究生“軟體工程設計與技術”、“軟體項目管理”課程負責人，主持教育部―微軟精品課程“數據結構”的建設。曾與人合作或單獨編寫和出版教材20餘部，其中，《數據結構》教材被評為教育部普通高等教育“十一五”規劃教材，並於2005年獲“北京市精品教材”。曾在核心刊物和專業會議發表論文多篇，並參加或主持多項科研項母。
