中圖網小程序
一鍵登錄
更方便
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫內科學·全國中醫藥行業高等教育“十四五”規劃教材
數據結構與算法分析:C++版 版權信息
- ISBN：9787121393549
- 條形碼：9787121393549 ; 978-7-121-39354-9
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
數據結構與算法分析:C++版 本書特色
適讀人群 ：本書適合作為大專院校計算機軟件專業與計算機應用專業學生的教材和參考書，也適合計算機工程技術人員參考。本書采用程序員偏愛的面向對象C++語言來描述數據結構和算法，并把數據結構原理和算法分析技術有機地結合在一起，系統介紹了各種類型的數據結構和排序、檢索的各種方法。作者非常注意對每一種數據結構的不同存儲方法及有關算法進行分析比較。書中還引入了一些比較高級的數據結構與先進的算法分析技術，并介紹了可計算性理論的一般知識。
數據結構與算法分析:C++版 內容簡介
本書采用程序員偏愛的面向對象C++語言來描述數據結構和算法，并把數據結構原理和算法分析技術有機地結合在一起，系統介紹了各種類型的數據結構和排序、檢索的各種方法。作者非常注意對每一種數據結構的不同存儲方法及有關算法進行分析比較。書中還引入了一些比較高級的數據結構與先進的算法分析技術，并介紹了可計算性理論的一般知識。書中分別給出了C++實現方法和偽碼實現方法，便于讀者根據情況選擇。在作者維護的網站可下載相關代碼、編程項目和輔助練習資料。本書已根據作者在網站提供的勘誤表進行過內容更正。
數據結構與算法分析:C++版 目錄
Contents
Part I Preliminaries 預備知識
Chapter 1 Data Structures and Algorithms 數據結構和算法 3
1．1 A Philosophy of Data Structures 數據結構的原則 4
1．1．1 The Need for Data Structures 學習數據結構的必要性 4
1．1．2 Costs and Benefits 代價與效益 6
1．2 Abstract Data Types and Data Structures 抽象數據類型和數據結構 8
1．3 Design Patterns 設計模式 12
1．3．1 Flyweight 享元模式 13
1．3．2 Visitor 訪問者模式 13
1．3．3 Composite 組合模式 14
1．3．4 Strategy 策略模式 15
1．4 Problems， Algorithms， and Programs 問題、算法和程序 16
1．5 Further Reading 深入學習導讀 18
1．6 Exercises 習題 20
Chapter 2 Mathematical Preliminaries 數學預備知識 25
2．1 Sets and Relations 集合和關系 25
2．2 Miscellaneous Notation 常用數學術語 29
2．3 Logarithms 對數 31
2．4 Summations and Recurrences 級數求和與遞歸 32
2．5 Recursion 遞歸 36
2．6 Mathematical Proof Techniques 數學證明方法 38
2．6．1 Direct Proof 直接證明法 39
2．6．2 Proof by Contradiction 反證法 39
2．6．3 Proof by Mathematical Induction 數學歸納法 40
2．7 Estimation 估計 46
2．8 Further Reading 深入學習導讀 47
2．9 Exercises 習題 48
Chapter 3 Algorithm Analysis 算法分析 55
3．1 Introduction 概述 55
3．2 Best， Worst， and Average Cases *佳、*差和平均情況 61
3．3 A Faster Computer， or a Faster Algorithm 換一臺更快的計算機，還是換一種更快的算法 62
3．4 Asymptotic Analysis 漸近分析 65
3．4．1 Upper Bounds 上限 65
3．4．2 Lower Bounds 下限 67
3．4．3 Θ Notation Θ表示法 68
3．4．4 Simplifying Rules 化簡法則 69
3．4．5 Classifying Functions 函數分類 70
3．5 Calculating the Running Time for a Program 程序運行時間的計算 71
3．6 Analyzing Problems 問題的分析 76
3．7 Common Misunderstandings 容易混淆的概念 77
3．8 Multiple Parameters 多參數問題 79
3．9 Space Bounds 空間代價 80
3．10 Speeding Up Your Programs 加速你的程序 82
3．11 Empirical Analysis 實證分析 85
3．12 Further Reading 深入學習導讀 86
3．13 Exercises 習題 86
3．14 Projects 項目設計 90
Part II Fundamental Data Structures 基本數據結構
Chapter 4 Lists， Stacks， and Queues 線性表、棧和隊列 95
4．1 Lists 線性表 96
4．1．1 Array-Based List Implementation 順序表的實現 100
4．1．2 Linked Lists 鏈表 103
4．1．3 Comparison of List Implementations 線性表實現方法的比較 112
4．1．4 Element Implementations 元素的表示 114
4．1．5 Doubly Linked Lists 雙鏈表 115
4．2 Stacks 棧 120
4．2．1 Array-Based Stacks 順序棧 121
4．2．2 Linked Stacks 鏈式棧 123
4．2．3 Comparison of Array-Based and Linked Stacks 順序棧與鏈式棧的比較 123
4．2．4 Implementing Recursion 遞歸的實現 125
4．3 Queues 隊列 127
4．3．1 Array-Based Queues 順序隊列 128
4．3．2 Linked Queues 鏈式隊列 133
4．3．3 Comparison of Array-Based and Linked Queues 順序隊列與鏈式隊列的比較 133
4．4 Dictionaries 字典 133
4．5 Further Reading 深入學習導讀 145
4．6 Exercises 習題 145
4．7 Projects 項目設計 148
Chapter 5 Binary Trees 二叉樹 151
5．1 Definitions and Properties 定義及主要特性 151
5．1．1 The Full Binary Tree Theorem 滿二叉樹定理 153
5．1．2 A Binary Tree Node ADT 二叉樹的抽象數據類型 155
5．2 Binary Tree Traversals 遍歷二叉樹 155
5．3 Binary Tree Node Implementations 二叉樹的實現 160
5．3．1 Pointer-Based Node Implementations 使用指針實現二叉樹 160
5．3．2 Space Requirements 空間代價 166
5．3．3 Array Implementation for Complete Binary Trees 使用數組實現完全二叉樹 168
5．4 Binary Search Trees 二叉檢索樹 168
5．5 Heaps and Priority Queues 堆與優先隊列 178
5．6 Huffman Coding Trees Huffman編碼樹 185
5．6．1 Building Huffman Coding Trees 建立Huffman編碼樹 186
5．6．2 Assigning and Using Huffman Codes Huffman編碼及其用法 192
5．6．3 Search in Huffman Trees 在Huffman樹中搜索 195
5．7 Further Reading 深入學習導讀 196
5．8 Exercises 習題 196
5．9 Projects 項目設計 200
Chapter 6 Non-Binary Trees 樹 203
6．1 General Tree Definitions and Terminology 樹的定義與術語 203
6．1．1 An ADT for General Tree Nodes 樹結點的ADT 204
6．1．2 General Tree Traversals 樹的遍歷 205
6．2 The Parent Pointer Implementation 父指針表示法 207
6．3 General Tree Implementations 樹的實現 213
6．3．1 List of Children 子結點表表示法 214
6．3．2 The Left-Child/Right-Sibling Implementation 左子結點/右兄弟結點表示法 215
6．3．3 Dynamic Node Implementations 動態結點表示法 215
6．3．4 Dynamic “Left-Child/Right-Sibling” Implementation 動態左子結點/右兄弟結點表示法 218
6．4 K-ary Trees K叉樹 218
6．5 Sequential Tree Implementations 樹的順序表示法 219
6．6 Further Reading 深入學習導讀 223
6．7 Exercises 習題 223
6．8 Projects 項目設計 226
Part III Sorting and Searching 排序與檢索
Chapter 7 Internal Sorting 內排序 231
7．1 Sorting Terminology and Notation 排序術語 232
7．2 Three Θ(n2) Sorting Algorithms 三種代價為Θ(n2)的排序算法 233
7．2．1 Insertion Sort 插入排序 233
7．2．2 Bubble Sort 冒泡排序 235
7．2．3 Selection Sort 選擇排序 237
7．2．4 The Cost of Exchange Sorting 交換排序算法的時間代價 238
7．3 Shellsort Shell排序 239
7．4 Mergesort 歸并排序 241
7．5 Quicksort 快速排序 244
7．6 Heapsort 堆排序 251
7．7 Binsort and Radix Sort 分配排序和基數排序 252
7．8 An Empirical Comparison of Sorting Algorithms 對各種排序算法的實驗比較 259
7．9 Lower Bounds for Sorting 排序問題的下限 261
7．10 Further Reading 深入學習導讀 265
7．11 Exercises 習題 265
7．12 Projects 項目設計 269
Chapter 8 File Processing and External Sorting 文件管理和外排序 273
8．1 Primary versus Secondary Storage 主存儲器和輔助存儲器 273
8．2 Disk Drives 磁盤 276
8．2．1 Disk Drive Architecture 磁盤結構 276
8．2．2 Disk Access Costs 磁盤訪問代價 280
8．3 Buffers and Buffer Pools 緩沖區和緩沖池 282
8．4 The Programmer’s View of Files 程序員的文件視圖 290
8．5 External Sorting 外排序 291
8．5．1 Simple Approaches to External Sorting 外排序的簡單方法 294
8．5．2 Replacement Selection 置換選擇排序 296
8．5．3 Multiway Merging 多路歸并 300
8．6 Further Reading 深入學習導讀 303
8．7 Exercises 習題 304
8．8 Projects 項目設計 307
Chapter 9 Searching 檢索 311
9．1 Searching Unsorted and Sorted Arrays 檢索未排序和已排序的數組 312
9．2 Self-Organizing Lists 自組織線性表 317
9．3 Bit Vectors for Representing Sets 集合檢索 323
9．4 Hashing 散列方法 324
9．4．1 Hash Functions 散列函數 325
9．4．2 Open Hashing 開散列方法 330
9．4．3 Closed Hashing 閉散列方法 331
9．4．4 Analysis of Closed Hashing 閉散列方法分析 339
9．4．5 Deletion 刪除 344
9．5 Further Reading 深入學習導讀 345
9．6 Exercises 習題 345
9．7 Projects 項目設計 348
Chapter 10 Indexing 索引技術 351
10．1 Linear Indexing 線性索引 353
10．2 ISAM 索引順序訪問方法 356
10．3 Tree-based Indexing 基于樹的索引 358
10．4 2-3 Trees 2-3樹 360
10．5 B-Trees B樹 364
10．5．1 B+-Trees B+樹 368
10．5．2 B-Tree Analysis B樹分析 374
10．6 Further Reading 深入學習導讀 375
10．7 Exercises 習題 375
10．8 Projects 項目設計 377
Part IV Advanced Data Structures 高級數據結構
Chapter 11 Graphs 圖 381
11．1 Terminology and Representations 術語和表示法 382
11．2 Graph Implementations 圖的實現 386
11．3 Graph Traversals 圖的遍歷 390
11．3．1 Depth-First Search 深度優先搜索 393
11．3．2 Breadth-First Search 廣度優先搜索 394
11．3．3 Topological Sort 拓撲排序 394
11．4 Shortest-Paths Problems *短路徑問題 399
11．4．1 Single-Source Shortest Paths 單源*短路徑 400
11．5 Minimum-Cost Spanning Trees *小支撐樹 402
11．5．1 Prim’s Algorithm Prim算法 404
11．5．2 Kruskal’s Algorithm Kruskal算法 407
11．6 Further Reading 深入學習導讀 408
11．7 Exercises 習題 408
11．8 Projects 項目設計 412
Chapter 12 Lists and Arrays Revisited 線性表和數組高級技術 415
12．1 Multilists 廣義表 415
12．2 Matrix Representations 矩陣的表示方法 418
12．3 Memory Management 存儲管理 422
12．3．1 Dynamic Storage Allocation 動態存儲分配 424
12．3．2 Failure Policies and Garbage Collection 失敗處理策略和無用單元收集 431
12．4 Further Reading 深入學習導讀 435
12．5 Exercises 習題 436
12．6 Projects 項目設計 437
Chapter 13 Advanced Tree Structures 高級樹結構 439
13．1 Tries Tries結構 439
13．2 Balanced Trees 平衡樹 444
13．2．1 The AVL Tree AVL樹 445
13．2．2 The Splay Tree 伸展樹 447
13．3 Spatial Data Structures 空間數據結構 450
13．3．1 The k-d Tree k-d樹 452
13．3．2 The PR quadtree PR四分樹 457
13．3．3 Other Point Data Structures 其他點狀數據結構 461
13．3．4 Other Spatial Data Structures 其他空間數據結構 463
13．4 Further Reading 深入學習導讀 463
13．5 Exercises 習題 464
13．6 Projects 項目設計 465
Part V Theory of Algorithms 算法理論
Chapter 14 Analysis Techniques 分析技術 471
14．1 Summation Techniques 求和技術 472
14．2 Recurrence Relations 遞歸關系 477
14．2．1 Estimating Upper and Lower Bounds 估算上下限 477
14．2．2 Expanding Recurrences 擴展遞歸 480
14．2．3 Divide and Conquer Recurrences 分治法遞歸 482
14．2．4 Average-Case Analysis of Quicksort 快速排序平均情況分析 484
14．3 Amortized Analysis 均攤分析 486
14．4 Further Reading 深入學習導讀 489
14．5 Exercises 習題 489
14．6 Projects 項目設計 493
Chapter 15 Lower Bounds 下限 495
15．1 Introduction to Lower Bounds Proofs 下限證明簡介 496
15．2 Lower Bounds on Searching Lists 線性表檢索的下限 498
15．2．1 Searching in Unsorted Lists 無序線性表檢索 498
15．2．2 Searching in Sorted Lists 有序線性表檢索 500
15．3 Finding the Maximum Value 查找*大值 501
15．4 Adversarial Lower Bounds Proofs 對抗性下限證明 503
15．5 State Space Lower Bounds Proofs 狀態空間下限證明 506
15．6 Finding the ith Best Element 查找第i大元素 509
15．7 Optimal Sorting 優化排序 511
15．8 Further Reading 深入學習導讀 514
15．9 Exercises 習題 514
15．10 Projects 項目設計 517
Chapter 16 Patterns of Algorithms 算法模式 519
16．1 Dynamic Programming 動態規劃 519
16．1．1 The Knapsack Problem 背包問題 521
16．1．2 All-Pairs Shortest Paths 全局*短路徑 523
16．2 Randomized Algorithms 隨機算法 525
16．2．1 Randomized algorithms for finding large values 查找*大值的隨機算法 525
16．2．2 Skip Lists 跳躍表 526
16．3 Numerical Algorithms 數值算法 532
16．3．1 Exponentiation 冪運算 533
16．3．2 Largest Common Factor *大公約數 533
16．3．3 Matrix Multiplication 矩陣相乘 534
16．3．4 Random Numbers 隨機數 536
16．3．5 The Fast Fourier Transform 快速傅里葉變換 537
16．4 Further Reading 深入學習導讀 542
16．5 Exercises 習題 542
16．6 Projects 項目設計 543
Chapter 17 Limits to Computation 計算的限制 545
17．1 Reductions 歸約 546
17．2 Hard Problems 難解問題 551
17．2．1 The Theory of NP-Completeness NP完全性理論 553
17．2．2 NP-Completeness Proofs NP完全性證明 557
17．2．3 Coping with NP-Complete Problems 處理NP完全性問題 562
17．3 Impossible Problems 不可解問題 565
17．3．1 Uncountability 不可數性 566
17．3．2 The Halting Problem Is Unsolvable 停機問題的不可解性 569
17．4 Further Reading 深入學習導讀 571
17．5 Exercises 習題 572
17．6 Projects 項目設計 574
Part VI Appendix 附錄
Appendix A Utility Functions 實用函數 579
Bibliography 參考文獻 581
Part I Preliminaries 預備知識
Chapter 1 Data Structures and Algorithms 數據結構和算法 3
1．1 A Philosophy of Data Structures 數據結構的原則 4
1．1．1 The Need for Data Structures 學習數據結構的必要性 4
1．1．2 Costs and Benefits 代價與效益 6
1．2 Abstract Data Types and Data Structures 抽象數據類型和數據結構 8
1．3 Design Patterns 設計模式 12
1．3．1 Flyweight 享元模式 13
1．3．2 Visitor 訪問者模式 13
1．3．3 Composite 組合模式 14
1．3．4 Strategy 策略模式 15
1．4 Problems， Algorithms， and Programs 問題、算法和程序 16
1．5 Further Reading 深入學習導讀 18
1．6 Exercises 習題 20
Chapter 2 Mathematical Preliminaries 數學預備知識 25
2．1 Sets and Relations 集合和關系 25
2．2 Miscellaneous Notation 常用數學術語 29
2．3 Logarithms 對數 31
2．4 Summations and Recurrences 級數求和與遞歸 32
2．5 Recursion 遞歸 36
2．6 Mathematical Proof Techniques 數學證明方法 38
2．6．1 Direct Proof 直接證明法 39
2．6．2 Proof by Contradiction 反證法 39
2．6．3 Proof by Mathematical Induction 數學歸納法 40
2．7 Estimation 估計 46
2．8 Further Reading 深入學習導讀 47
2．9 Exercises 習題 48
Chapter 3 Algorithm Analysis 算法分析 55
3．1 Introduction 概述 55
3．2 Best， Worst， and Average Cases *佳、*差和平均情況 61
3．3 A Faster Computer， or a Faster Algorithm 換一臺更快的計算機，還是換一種更快的算法 62
3．4 Asymptotic Analysis 漸近分析 65
3．4．1 Upper Bounds 上限 65
3．4．2 Lower Bounds 下限 67
3．4．3 Θ Notation Θ表示法 68
3．4．4 Simplifying Rules 化簡法則 69
3．4．5 Classifying Functions 函數分類 70
3．5 Calculating the Running Time for a Program 程序運行時間的計算 71
3．6 Analyzing Problems 問題的分析 76
3．7 Common Misunderstandings 容易混淆的概念 77
3．8 Multiple Parameters 多參數問題 79
3．9 Space Bounds 空間代價 80
3．10 Speeding Up Your Programs 加速你的程序 82
3．11 Empirical Analysis 實證分析 85
3．12 Further Reading 深入學習導讀 86
3．13 Exercises 習題 86
3．14 Projects 項目設計 90
Part II Fundamental Data Structures 基本數據結構
Chapter 4 Lists， Stacks， and Queues 線性表、棧和隊列 95
4．1 Lists 線性表 96
4．1．1 Array-Based List Implementation 順序表的實現 100
4．1．2 Linked Lists 鏈表 103
4．1．3 Comparison of List Implementations 線性表實現方法的比較 112
4．1．4 Element Implementations 元素的表示 114
4．1．5 Doubly Linked Lists 雙鏈表 115
4．2 Stacks 棧 120
4．2．1 Array-Based Stacks 順序棧 121
4．2．2 Linked Stacks 鏈式棧 123
4．2．3 Comparison of Array-Based and Linked Stacks 順序棧與鏈式棧的比較 123
4．2．4 Implementing Recursion 遞歸的實現 125
4．3 Queues 隊列 127
4．3．1 Array-Based Queues 順序隊列 128
4．3．2 Linked Queues 鏈式隊列 133
4．3．3 Comparison of Array-Based and Linked Queues 順序隊列與鏈式隊列的比較 133
4．4 Dictionaries 字典 133
4．5 Further Reading 深入學習導讀 145
4．6 Exercises 習題 145
4．7 Projects 項目設計 148
Chapter 5 Binary Trees 二叉樹 151
5．1 Definitions and Properties 定義及主要特性 151
5．1．1 The Full Binary Tree Theorem 滿二叉樹定理 153
5．1．2 A Binary Tree Node ADT 二叉樹的抽象數據類型 155
5．2 Binary Tree Traversals 遍歷二叉樹 155
5．3 Binary Tree Node Implementations 二叉樹的實現 160
5．3．1 Pointer-Based Node Implementations 使用指針實現二叉樹 160
5．3．2 Space Requirements 空間代價 166
5．3．3 Array Implementation for Complete Binary Trees 使用數組實現完全二叉樹 168
5．4 Binary Search Trees 二叉檢索樹 168
5．5 Heaps and Priority Queues 堆與優先隊列 178
5．6 Huffman Coding Trees Huffman編碼樹 185
5．6．1 Building Huffman Coding Trees 建立Huffman編碼樹 186
5．6．2 Assigning and Using Huffman Codes Huffman編碼及其用法 192
5．6．3 Search in Huffman Trees 在Huffman樹中搜索 195
5．7 Further Reading 深入學習導讀 196
5．8 Exercises 習題 196
5．9 Projects 項目設計 200
Chapter 6 Non-Binary Trees 樹 203
6．1 General Tree Definitions and Terminology 樹的定義與術語 203
6．1．1 An ADT for General Tree Nodes 樹結點的ADT 204
6．1．2 General Tree Traversals 樹的遍歷 205
6．2 The Parent Pointer Implementation 父指針表示法 207
6．3 General Tree Implementations 樹的實現 213
6．3．1 List of Children 子結點表表示法 214
6．3．2 The Left-Child/Right-Sibling Implementation 左子結點/右兄弟結點表示法 215
6．3．3 Dynamic Node Implementations 動態結點表示法 215
6．3．4 Dynamic “Left-Child/Right-Sibling” Implementation 動態左子結點/右兄弟結點表示法 218
6．4 K-ary Trees K叉樹 218
6．5 Sequential Tree Implementations 樹的順序表示法 219
6．6 Further Reading 深入學習導讀 223
6．7 Exercises 習題 223
6．8 Projects 項目設計 226
Part III Sorting and Searching 排序與檢索
Chapter 7 Internal Sorting 內排序 231
7．1 Sorting Terminology and Notation 排序術語 232
7．2 Three Θ(n2) Sorting Algorithms 三種代價為Θ(n2)的排序算法 233
7．2．1 Insertion Sort 插入排序 233
7．2．2 Bubble Sort 冒泡排序 235
7．2．3 Selection Sort 選擇排序 237
7．2．4 The Cost of Exchange Sorting 交換排序算法的時間代價 238
7．3 Shellsort Shell排序 239
7．4 Mergesort 歸并排序 241
7．5 Quicksort 快速排序 244
7．6 Heapsort 堆排序 251
7．7 Binsort and Radix Sort 分配排序和基數排序 252
7．8 An Empirical Comparison of Sorting Algorithms 對各種排序算法的實驗比較 259
7．9 Lower Bounds for Sorting 排序問題的下限 261
7．10 Further Reading 深入學習導讀 265
7．11 Exercises 習題 265
7．12 Projects 項目設計 269
Chapter 8 File Processing and External Sorting 文件管理和外排序 273
8．1 Primary versus Secondary Storage 主存儲器和輔助存儲器 273
8．2 Disk Drives 磁盤 276
8．2．1 Disk Drive Architecture 磁盤結構 276
8．2．2 Disk Access Costs 磁盤訪問代價 280
8．3 Buffers and Buffer Pools 緩沖區和緩沖池 282
8．4 The Programmer’s View of Files 程序員的文件視圖 290
8．5 External Sorting 外排序 291
8．5．1 Simple Approaches to External Sorting 外排序的簡單方法 294
8．5．2 Replacement Selection 置換選擇排序 296
8．5．3 Multiway Merging 多路歸并 300
8．6 Further Reading 深入學習導讀 303
8．7 Exercises 習題 304
8．8 Projects 項目設計 307
Chapter 9 Searching 檢索 311
9．1 Searching Unsorted and Sorted Arrays 檢索未排序和已排序的數組 312
9．2 Self-Organizing Lists 自組織線性表 317
9．3 Bit Vectors for Representing Sets 集合檢索 323
9．4 Hashing 散列方法 324
9．4．1 Hash Functions 散列函數 325
9．4．2 Open Hashing 開散列方法 330
9．4．3 Closed Hashing 閉散列方法 331
9．4．4 Analysis of Closed Hashing 閉散列方法分析 339
9．4．5 Deletion 刪除 344
9．5 Further Reading 深入學習導讀 345
9．6 Exercises 習題 345
9．7 Projects 項目設計 348
Chapter 10 Indexing 索引技術 351
10．1 Linear Indexing 線性索引 353
10．2 ISAM 索引順序訪問方法 356
10．3 Tree-based Indexing 基于樹的索引 358
10．4 2-3 Trees 2-3樹 360
10．5 B-Trees B樹 364
10．5．1 B+-Trees B+樹 368
10．5．2 B-Tree Analysis B樹分析 374
10．6 Further Reading 深入學習導讀 375
10．7 Exercises 習題 375
10．8 Projects 項目設計 377
Part IV Advanced Data Structures 高級數據結構
Chapter 11 Graphs 圖 381
11．1 Terminology and Representations 術語和表示法 382
11．2 Graph Implementations 圖的實現 386
11．3 Graph Traversals 圖的遍歷 390
11．3．1 Depth-First Search 深度優先搜索 393
11．3．2 Breadth-First Search 廣度優先搜索 394
11．3．3 Topological Sort 拓撲排序 394
11．4 Shortest-Paths Problems *短路徑問題 399
11．4．1 Single-Source Shortest Paths 單源*短路徑 400
11．5 Minimum-Cost Spanning Trees *小支撐樹 402
11．5．1 Prim’s Algorithm Prim算法 404
11．5．2 Kruskal’s Algorithm Kruskal算法 407
11．6 Further Reading 深入學習導讀 408
11．7 Exercises 習題 408
11．8 Projects 項目設計 412
Chapter 12 Lists and Arrays Revisited 線性表和數組高級技術 415
12．1 Multilists 廣義表 415
12．2 Matrix Representations 矩陣的表示方法 418
12．3 Memory Management 存儲管理 422
12．3．1 Dynamic Storage Allocation 動態存儲分配 424
12．3．2 Failure Policies and Garbage Collection 失敗處理策略和無用單元收集 431
12．4 Further Reading 深入學習導讀 435
12．5 Exercises 習題 436
12．6 Projects 項目設計 437
Chapter 13 Advanced Tree Structures 高級樹結構 439
13．1 Tries Tries結構 439
13．2 Balanced Trees 平衡樹 444
13．2．1 The AVL Tree AVL樹 445
13．2．2 The Splay Tree 伸展樹 447
13．3 Spatial Data Structures 空間數據結構 450
13．3．1 The k-d Tree k-d樹 452
13．3．2 The PR quadtree PR四分樹 457
13．3．3 Other Point Data Structures 其他點狀數據結構 461
13．3．4 Other Spatial Data Structures 其他空間數據結構 463
13．4 Further Reading 深入學習導讀 463
13．5 Exercises 習題 464
13．6 Projects 項目設計 465
Part V Theory of Algorithms 算法理論
Chapter 14 Analysis Techniques 分析技術 471
14．1 Summation Techniques 求和技術 472
14．2 Recurrence Relations 遞歸關系 477
14．2．1 Estimating Upper and Lower Bounds 估算上下限 477
14．2．2 Expanding Recurrences 擴展遞歸 480
14．2．3 Divide and Conquer Recurrences 分治法遞歸 482
14．2．4 Average-Case Analysis of Quicksort 快速排序平均情況分析 484
14．3 Amortized Analysis 均攤分析 486
14．4 Further Reading 深入學習導讀 489
14．5 Exercises 習題 489
14．6 Projects 項目設計 493
Chapter 15 Lower Bounds 下限 495
15．1 Introduction to Lower Bounds Proofs 下限證明簡介 496
15．2 Lower Bounds on Searching Lists 線性表檢索的下限 498
15．2．1 Searching in Unsorted Lists 無序線性表檢索 498
15．2．2 Searching in Sorted Lists 有序線性表檢索 500
15．3 Finding the Maximum Value 查找*大值 501
15．4 Adversarial Lower Bounds Proofs 對抗性下限證明 503
15．5 State Space Lower Bounds Proofs 狀態空間下限證明 506
15．6 Finding the ith Best Element 查找第i大元素 509
15．7 Optimal Sorting 優化排序 511
15．8 Further Reading 深入學習導讀 514
15．9 Exercises 習題 514
15．10 Projects 項目設計 517
Chapter 16 Patterns of Algorithms 算法模式 519
16．1 Dynamic Programming 動態規劃 519
16．1．1 The Knapsack Problem 背包問題 521
16．1．2 All-Pairs Shortest Paths 全局*短路徑 523
16．2 Randomized Algorithms 隨機算法 525
16．2．1 Randomized algorithms for finding large values 查找*大值的隨機算法 525
16．2．2 Skip Lists 跳躍表 526
16．3 Numerical Algorithms 數值算法 532
16．3．1 Exponentiation 冪運算 533
16．3．2 Largest Common Factor *大公約數 533
16．3．3 Matrix Multiplication 矩陣相乘 534
16．3．4 Random Numbers 隨機數 536
16．3．5 The Fast Fourier Transform 快速傅里葉變換 537
16．4 Further Reading 深入學習導讀 542
16．5 Exercises 習題 542
16．6 Projects 項目設計 543
Chapter 17 Limits to Computation 計算的限制 545
17．1 Reductions 歸約 546
17．2 Hard Problems 難解問題 551
17．2．1 The Theory of NP-Completeness NP完全性理論 553
17．2．2 NP-Completeness Proofs NP完全性證明 557
17．2．3 Coping with NP-Complete Problems 處理NP完全性問題 562
17．3 Impossible Problems 不可解問題 565
17．3．1 Uncountability 不可數性 566
17．3．2 The Halting Problem Is Unsolvable 停機問題的不可解性 569
17．4 Further Reading 深入學習導讀 571
17．5 Exercises 習題 572
17．6 Projects 項目設計 574
Part VI Appendix 附錄
Appendix A Utility Functions 實用函數 579
Bibliography 參考文獻 581
展開全部
數據結構與算法分析:C++版 作者簡介
Clifford A. Shaffer教授于美國馬里蘭大學獲得計算機科學博士學位，在弗吉尼亞理工大學計算機科學系任教超過30年，具有豐富的教學經驗，并參與遺傳學、生物信息學和計算生物學等交叉項目。著有多本數據結構和算法分析的教材。Clifford A. Shaffer教授于美國馬里蘭大學獲得計算機科學博士學位，在弗吉尼亞理工大學計算機科學系任教超過30年，具有豐富的教學經驗，并參與遺傳學、生物信息學和計算生物學等交叉項目。著有多本數據結構和算法分析的教材。
書友推薦
- >
中國歷史的瞬間
- >
隨園食單
- >
中國人在烏蘇里邊疆區:歷史與人類學概述
- >
月亮虎
- >
唐代進士錄
- >
有舍有得是人生
- >
二體千字文
- >
伊索寓言-世界文學名著典藏-全譯本
本類暢銷
