本書是根據教育部高等學校計算機科學與技術專業教指委公布的《高等學校計算機科學與技術專業公共核心知識體繫與課程》和教育部考試中心公布的《全國碩士研究生入學考試計算機科學 與技術專業基礎綜合考試聯考考試大綱》編寫的學習數據結構算法的輔導教材和計算機專業考研輔導教材

●第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.6Huffman樹486
5.6.1Huffman樹及其結構定義486
5.6.2Huffman樹相關的算法487
5.6.3Huffman編碼相關的算法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.1AOV網與拓撲排序613
6.6.2AOE網與關鍵路徑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.3AVL樹680
7.3.1AVL樹的概念680
7.3.2AVL樹相關算法680
7.4B樹與B+樹690
7.4.1分塊查找與索引表690
7.4.2B樹696
7.4.3B+樹703
7.5其他查找樹711
7.5.1紅黑樹711
7.5.2伸展樹722
7.5.3雙鏈樹727
7.5.4Trie樹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.2MSD桶排序813
8.6.3LSD桶排序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

本書是根據教育部高等學校計算機科學與技術專業教指委公布的《高等學校計算機科學與技術專業公共核心知識體繫與課程》和教育部考試中心公布的《全國碩士研究生入學考試計算機科學與技術專業基礎綜合考試聯考考試大綱》編寫的學習數據結構算法的輔導教材。全書共分8章，第1章介紹數據結構的基本算法設計和簡單的算法分析方法；第2~6章給出大量算法題，覆蓋了基本數據結構和算法的全部知識點，包括線性表、棧、隊列、數組、字符串、廣義表、樹與二叉樹、圖等；第7~8章給出了相當多的算法，覆蓋了査找和排序方面的所有知識點。
本書融入了作者30多年數據結構教學的經驗，考慮了不同層次學生學習的需要，精選了1140多道算法題，覆蓋了相關知識點的方方面面，既可以作為大學計算機專業學習數據結構課程的輔助教材，也可以作為計算機專業考研的輔導教材。

殷人昆 編