了得網計算機/網絡_數據結構與算法分析 C++語言描述(英文版第4版)

編輯推薦

1. 用C 新標準C 11的代碼講數據結構和算法分析；

2. 作者所寫的數據結構和算法分析書籍銷量好，好評多，已被世界上很多大學用作教材。

內容簡介

本書是數據結構和算法分析領域的教材。全書以 C 作為具體的實現語言，介紹了表、棧、隊列、樹、哈希表、優先隊列、排序、不相交集算法、圖論算法、算法分析、算法設計、攤還分析、查找樹算法、後綴數組、後綴樹、k-d 樹、配對堆等內容。本書把算法分析和 C 程序的開發有機結合起來，深入剖析每種算法，內容縝密嚴謹，還詳細講解了精心構建程序的方法。

本書可作為高等院校計算機相關專業的教學用書或參考用書，也可供計算機領域的工程技術人員參考

作者簡介

Mark Allen Weiss，佛羅裡達國際大學計算與信息科學學院教授、副院長，本科教育主任和研究生教育主任。他於1987年獲得普林斯頓大學計算機科學博士學位，師從Bob Sedgewick。他曾經擔任全美AP(Advanced Placement)考試計算機學科委員會的主席(2000-2004)。Weiss教授在數據結構和算法分析方面卓有建樹，他的數據結構和算法分析的書籍，受到廣泛好評．已被世界500餘所大學用作教材。

Chapter 1Programming: A General Overview / 第 1章程序設計：概述1

1.1What’s This Book About / 本書討論的內容1

1.2Mathematics Review / 數學知識復習2

1.2.1Exponents / 指數3

1.2.2Logarithms / 對數3

1.2.3Series / 級數4

Chapter 1Programming: A General Overview / 第 1章程序設計：概述1

1.1What’s This Book About / 本書討論的內容1

1.2Mathematics Review / 數學知識復習2

1.2.1Exponents / 指數3

1.2.2Logarithms / 對數3

1.2.3Series / 級數4

1.2.4Modular Arithmetic / 模運算5

1.2.5The P Word / 證明方法6

1.3A Brief Introduction to Recursion / 遞歸簡論8

1.4C Classes / C類12

1.4.1Basic class Syntax / 基本的class語法12

1.4.2Extra Constructor Syntax and Accessors / 構造函數的附加語法和訪問函數13

1.4.3Separation of Interface and Implementation / 接口與實現的分離16

1.4.4vector and string / vector類和string類19

1.5C Details / C細節21

1.5.1Pointers / 指針21

1.5.2Lvalues, Rvalues, and References / 左值、右值和引用23

1.5.3Parameter Passing / 參數傳遞25

1.5.4Return Passing / 返回值傳遞27

1.5.5std::swap and std::move / std::swap和std::move29

1.5.6The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= / 五大函數：析構函數、拷貝構造函數、移動構造函數、拷貝賦值operator=和移動賦值operator=30

1.5.7C-style Arrays and Strings / C風格數組和字符串35

1.6Templates / 模板36

1.6.1Function Templates / 函數模板37

1.6.2Class Templates / 類模板38

1.6.3Object, Comparable, and an Example / Object、Comparable和一個例子39

1.6.4Function Objects / 函數對像41

1.6.5Separate Compilation of Class Templates / 類模板的分離式編譯 44

1.7Using Matrices / 使用矩陣44

1.7.1The Data Members, Constructor, and Basic Accessors / 數據成員、構造函數和基本訪問函數44

1.7.2operator[] / operator[]45

1.7.3Big-Five / 五大函數46

Summary / 小結46

Exercises / 練習46

References / 參考文獻48

Chapter 2 Algorithm Analysis / 第 2章算法分析51

2.1Mathematical Background / 數學基礎51

2.2Model / 模型54

2.3What to Analyze / 要分析的問題54

2.4Running-Time Calculations / 運行時間計算57

2.4.1A Simple Example / 一個簡單的例子58

2.4.2General Rules / 一般法則58

2.4.3Solutions for the Maximum Subsequence Sum Problem / 子序列和問題的求解60

2.4.4Logarithms in the Running Time / 運行時間中的對數66

2.4.5Limitations of Worst-Case Analysis / 壞情形分析的局限性 70

Summary / 小結70

Exercises / 練習71

References / 參考文獻

76

Chapter 3 Lists, Stacks, and Queues / 第3章表、棧和隊列77

3.1Abstract Data Types (ADTs) / 抽像數據類型77

3.2The List ADT / 表的抽像數據類型78

3.2.1Simple Array Implementation of Lists / 表的簡單數組實現78

3.2.2Simple Linked Lists / 簡單鏈表79

3.3vector and list in the STL / STL中的vector和list80

3.3.1Iterators / 迭代器82

3.3.2Example: Using erase on a List / 例子：對表使用erase83

3.3.3const_iterators / const_iterators84

3.4Implementation of vector / vector的實現86

3.5Implementation of list / list的實現91

3.6The Stack ADT / 棧的抽像數據類型103

3.6.1Stack Model / 棧模型103

3.6.2Implementation of Stacks / 棧的實現104

3.6.3Applications / 應用104

3.7The Queue ADT / 隊列的抽像數據類型112

3.7.1Queue Model / 隊列模型113

3.7.2Array Implementation of Queues / 隊列的數組實現113

3.7.3Applications of Queues / 隊列的應用115

Summary / 小結116

Exercises / 練習116

Chapter 4 Trees / 第4章樹121

4.1Preliminaries / 預備知識121

4.1.1Implementation of Trees / 樹的實現122

4.1.2Tree Traversals with an Application / 樹的遍歷及應用123

4.2Binary Trees / 二叉樹126

4.2.1Implementation / 實現128

4.2.2An Example: Expression Trees / 一個例子——表達式樹128

4.3The Search Tree ADT—Binary Search Trees / 查找樹的抽像數據類型——二叉查找樹132

4.3.1contains / contains134

4.3.2findMin and findMax / findMin和findMax135

4.3.3insert / insert136

4.3.4remove / remove139

4.3.5Destructor and Copy Constructor / 析構函數和拷貝構造函數141

4.3.6Average-Case Analysis / 平均情況分析141

4.4AVL Trees / AVL樹144

4.4.1Single Rotation / 單旋轉147

4.4.2Double Rotation / 雙旋轉149

4.5Splay Trees / 伸展樹158

4.5.1A Simple Idea (That Does Not Work) / 一個簡單的想法（不能直接使用）158

4.5.2Splaying / 展開160

4.6Tree Traversals (Revisited) / 樹的遍歷（再次討論）166

4.7B-Trees / B樹168

4.8Sets and Maps in the Standard Library / 標準庫中的集合與映射173

4.8.1Sets / 集合173

4.8.2Maps / 映射174

4.8.3Implementation of set and map / set和map的實現175

4.8.4An Example That Uses Several Maps / 使用多個映射的示例176

Summary / 小結181

Exercises / 練習182

References / 參考文獻189

Chapter 5 Hashing / 第5章哈希193

5.1General Idea / 一般想法193

5.2Hash Function / 哈希函數194

5.3Separate Chaining / 分離鏈接法196

5.4Hash Tables without Linked Lists / 不用鏈表的哈希表201

5.4.1Linear Probing / 線性探測法201

5.4.2Quadratic Probing / 平方探測法202

5.4.3Double Hashing / 雙哈希207

5.5Rehashing / 再哈希208

5.6Hash Tables in the Standard Library / 標準庫中的哈希表210

5.7Hash Tables with Worst-Case O(1) Access / 以壞情形O(1)訪問的哈希表212

5.7.1Perfect Hashing / 完美哈希213

5.7.2Cuckoo Hashing / 杜鵑哈希215

5.7.3Hopscotch Hashing / 跳房子哈希227

5.8Universal Hashing / 通用哈希230

5.9Extendible Hashing / 可擴哈希233

Summary / 小結236

Exercises / 練習237

References / 參考文獻241

Chapter 6 Priority Queues (Heaps) / 第6章優先隊列（堆）245

6.1Model / 模型245

6.2Simple Implementations / 一些簡單的實現246

6.3Binary Heap / 二叉堆247

6.3.1Structure Property / 結構性質247

6.3.2Heap-Order Property / 堆序性質248

6.3.3Basic Heap Operations / 基本的堆操作249

6.3.4Other Heap Operations / 其他的堆操作252

6.4Applications of Priority Queues / 優先隊列的應用257

6.4.1The Selection Problem / 選擇問題258

6.4.2Event Simulation / 事件模擬259

6.5d-Heaps / d堆260

6.6Leftist Heaps / 左式堆261

6.6.1Leftist Heap Property / 左式堆的性質261

6.6.2Leftist Heap Operations / 左式堆操作262

6.7Skew Heaps / 斜堆269

6.8Binomial Queues / 二項隊列271

6.8.1Binomial Queue Structure / 二項隊列構建271

6.8.2Binomial Queue Operations / 二項隊列操作271

6.8.3Implementation of Binomial Queues / 二項隊列的實現276

6.9Priority Queues in the Standard Library / 標準庫中的優先隊列282

Summary / 小結283

Exercises / 練習283

References / 參考文獻288

Chapter 7 Sorting / 第7章排序291

7.1Preliminaries / 預備知識291

7.2Insertion Sort / 插入排序292

7.2.1The Algorithm / 算法292

7.2.2STL Implementation of Insertion Sort / 插入排序的STL實現293

7.2.3Analysis of Insertion Sort / 插入排序的分析294

7.3A Lower Bound for Simple Sorting Algorithms / 一些簡單排序算法的下界295

7.4Shellsort / 希爾排序296

7.4.1Worst-Case Analysis of Shellsort / 希爾排序的壞情形分析297

7.5Heapsort / 堆排序300

7.5.1Analysis of Heapsort / 堆排序的分析301

7.6Mergesort / 歸並排序304

7.6.1Analysis of Mergesort / 歸並排序的分析306

7.7Quicksort / 快速排序309

7.7.1Picking the Pivot / 選311

7.7.2Partitioning Strategy / 分割策略313

7.7.3Small Arrays / 小數組315

7.7.4Actual Quicksort Routines / 實際的快速排序例程315

7.7.5Analysis of Quicksort / 快速排序的分析318

7.7.6A Linear-Expected-Time Algorithm for Selection / 選擇問題的線性期望時間算法321

7.8A General Lower Bound for Sorting / 排序算法的一般下界323

7.8.1Decision Trees / 決策樹323

7.9Decision-Tree Lower Bounds for Selection Problems / 選擇問題的決策樹下界325

7.10Adversary Lower Bounds / 對手下界328

7.11Linear-Time Sorts: Bucket Sort and Radix Sort / 線性時間排序：桶式排序和基數排序331

7.12External Sorting / 外部排序336

7.12.1Why We Need New Algorithms / 為什麼需要一些新的算法336

7.12.2Model for External Sorting / 外部排序模型336

7.12.3The Simple Algorithm / 簡單算法337

7.12.4Multiway Merge / 多路合並338

7.12.5Polyphase Merge / 多相合並339

7.12.6Replacement Selection / 替換選擇340

Summary / 小結341

Exercises / 練習341

References / 參考文獻347

Chapter 8 The Disjoint Sets Class / 第8章不相交集算法351

8.1Equivalence Relations / 等價關繫351

8.2The Dynamic Equivalence Problem / 動態等價性問題352

8.3Basic Data Structure / 基本數據結構353

8.4Smart Union Algorithms / 靈巧求並算法357

8.5Path Compression / 路徑壓縮360

8.6Worst Case for Union-by-Rank and Path Compression / 按秩求並和路徑壓縮的壞情形361

8.6.1Slowly Growing Functions / 緩慢增長的函數362

8.6.2An Analysis by Recursive Decomposition / 通過遞歸分解進行的分析362

8.6.3An O (M log*N) Bound / 一個O (M log*N)界369

8.6.4An O (Mα(M, N)) Bound / 一個O (Mα(M, N))界370

8.7An Application / 一個應用372

Summary / 小結374

Exercises / 練習375

References / 參考文獻376

Chapter 9 Graph Algorithms / 第9章圖論算法379

9.1Definitions / 若干定義379

9.1.1Representation of Graphs / 圖的表示380

9.2Topological Sort / 拓撲排序382

9.3Shortest-Path Algorithms / 短路徑算法386

9.3.1Unweighted Shortest Paths / 無權短路徑387

9.3.2Dijkstra’s Algorithm / Dijkstra算法391

9.3.3Graphs with Negative Edge Costs / 具有負邊值的圖400

9.3.4Acyclic Graphs / 無圈圖400

9.3.5All-Pairs Shortest Path / 所有頂點對間的短路徑404

9.3.6Shortest Path Example / 短路徑的例404

9.4Network Flow Problems / 網絡流問題406

9.4.1A Simple Maximum-Flow Algorithm / 一個簡單的流算法408

9.5Minimum Spanning Tree / 小生成樹413

9.5.1Prim’s Algorithm / Prim算法414

9.5.2Kruskal’s Algorithm / Kruskal算法417

9.6Applications of Depth-First Search / 深度優先搜索的應用419

9.6.1Undirected Graphs / 無向圖420

9.6.2Biconnectivity / 雙連通性421

9.6.3Euler Circuits / 歐拉回路425

9.6.4Directed Graphs / 有向圖429

9.6.5Finding Strong Components / 查找強分支431

9.7Introduction to NP-Completeness / NP完全性介紹432

9.7.1Easy vs. Hard / 難與易433

9.7.2The Class NP / NP類434

9.7.3NP-Complete Problems / NP完全問題434

Summary / 小結437

Exercises / 練習437

References / 參考文獻445

Chapter 10 Algorithm Design Techniques / 第 10章算法設計技巧449

10.1Greedy Algorithms / 貪婪算法449

10.1.1A Simple Scheduling Problem / 一個簡單的調度問題450

10.1.2Huffman Codes / 哈夫曼編碼453

10.1.3Approximate Bin Packing / 近似裝箱問題459

10.2Divide and Conquer / 分治算法467

10.2.1Running Time of Divide-and-Conquer Algorithms / 分治算法的運行時間468

10.2.2Closest-Points Problem / 近點問題470

10.2.3The Selection Problem / 選擇問題475

10.2.4Theoretical Improvements for Arithmetic Problems / 一些算術問題的理論改進478

10.3Dynamic Programming / 動態規劃482

10.3.1Using a Table Instead of Recursion / 用表代替遞歸483

10.3.2Ordering Matrix Multiplications / 矩陣乘法的順序安排485

10.3.3Optimal Binary Search Tree / 二叉查找樹487

10.3.4All-Pairs Shortest Path / 所有點對短路徑491

10.4Randomized Algorithms / 隨機化算法494

10.4.1Random-Number Generators / 隨機數發生器495

10.4.2Skip Lists / 跳躍表500

10.4.3Primality Testing / 素性測試503

10.5Backtracking Algorithms / 回溯算法506

10.5.1The Turnpike Reconstruction Problem / 收費公路重建問題506

10.5.2Games / 遊戲511

Summary / 小結518

Exercises / 練習518

References / 參考文獻527

Chapter 11 Amortized Analysis / 第 11章攤還分析533

11.1An Unrelated Puzzle / 一個無關的智力問題534

11.2Binomial Queues / 二項隊列534

11.3Skew Heaps / 斜堆539

11.4Fibonacci Heaps / 斐波那契堆541

11.4.1Cutting Nodes in Leftist Heaps / 切除左式堆中的節點542

11.4.2Lazy Merging for Binomial Queues / 二項隊列的懶惰合並544

11.4.3The Fibonacci Heap Operations / 斐波那契堆操作548

11.4.4Proof of the Time Bound / 時間界的證明549

11.5Splay Trees / 伸展樹551

Summary / 小結555

Exercises / 練習556

References / 參考文獻557

Chapter 12 Advanced Data Structures and Implementation / 第 12章高級數據結構及其實現559

12.1Top-Down Splay Trees / 自頂向下伸展樹559

12.2Red-Black Trees / 紅黑樹566

12.2.1Bottom-Up Insertion / 自底向上的插入567

12.2.2Top-Down Red-Black Trees / 自頂向下紅黑樹568

12.2.3Top-Down Deletion / 自頂向下刪除570

12.3Treaps / treap 樹576

12.4Suffix Arrays and Suffix Trees / 後綴數組和後綴樹579

12.4.1Suffix Arrays / 後綴數組580

12.4.2Suffix Trees / 後綴樹583

12.4.3Linear-Time Construction of Suffix Arrays and Suffix Trees / 後綴數組和後綴樹的線性586

12.5k -d Trees / k-d 樹596

12.6Pairing Heaps / 配對堆602

Summary / 小結606

Exercises / 練習608

References / 參考文獻612

Appendix A Separate Compilation of Class Templates / 附錄A類模板的分離式編譯615

A.1 Everything in the Header / 頭文件中的內容616

A.2 Explicit Instantiation / 顯示實例化616

商品搜索

商品分类

【醫學】

【各大出版社】