实例介绍
【实例简介】Data Structures the Fun Way（有趣的数据结构）
这本易读且有趣的书通过数据结构的镜头提供了对计算思维的深入介绍——数据结构是任何编程努力的关键组成部分。通过图表、伪代码和幽默的类比，您将了解数据结构如何驱动算法操作，不仅了解如何构建数据结构，而且了解如何以及何时使用数据结构。
本书将为您提供实现和使用超过15个关键数据结构的强大背景知识，从堆栈、队列和缓存到开花过滤器、跳过列表和图表。通过在咖啡馆排队来掌握链表，通过编目夏季奥运会的历史来掌握哈希表，通过整齐地整理厨房的橱柜来掌握四叉树。随着基本的计算机科学概念，如递归和迭代，您将学习:
指针的复杂性和功能
基于树的数据结构的分支逻辑
不同的数据结构如何在内存中插入和删除数据
为什么数学映射和随机化是有用的
如何在速度、灵活性和内存使用之间进行权衡
《有趣的数据结构》展示了如何有效地将这些想法应用到现实世界的问题中——其中有惊人数量的问题是关于买一杯像样的咖啡。在任何级别上，完全理解数据结构将教会您应用于多种编程语言的核心技能，将您的职业生涯带到下一个层次。
【实例截图】
【核心代码】
CONTENTS IN DETAIL
ACKNOWLEDGMENTS
xvii
INTRODUCTION
xix
Intended Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
Language-Agnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
On Analogies and Brewing Coffee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
How to Use This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii
1
INFORMATION IN MEMORY
1
Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Composite Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2
BINARY SEARCH
13
The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Linear Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Binary Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Absent Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Implementing Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Adapting Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3
DYNAMIC DATA STRUCTURES
25
The Limitations of Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Pointers and References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Operations on Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Inserting into a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Deleting from a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Arrays and Linked Lists of Items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40xii Contents in Detail
4
STACKS AND QUEUES
43
Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Stacks as Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Stacks as Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Queues as Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Queues as Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
The Importance of Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5
BINARY SEARCH TREES
55
Binary Search Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Searching Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Iterative and Recursive Searches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Searching Trees vs. Searching Sorted Arrays . . . . . . . . . . . . . . . . . . . . . . . . 62
Modifying Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Adding Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Removing Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
The Danger of Unbalanced Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Bulk Construction of Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6
TRIES AND ADAPTING DATA STRUCTURES
75
Binary Search Trees of Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Strings in Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
The Cost of String Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Searching Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Adding and Removing Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7
PRIORITY QUEUES AND HEAPS
93
Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Max Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Adding Elements to a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Removing the Highest-Priority Elements from Heaps . . . . . . . . . . . . . . . . . . . 101
Storing Auxiliary Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Updating Priorities................................................ 105
Min Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Contents in Detail xiii
8
GRIDS
113
Introducing Nearest-Neighbor Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Nearest-Neighbor Search with Linear Scan . . . . . . . . . . . . . . . . . . . . . . . . 114
Searching Spatial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Grid Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Building Grids and Inserting Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Deleting Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Searches Over Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Pruning Bins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Linear Scan Over Bins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Ideal Expanding Search over Bins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Simplified Expanding Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
The Importance of Grid Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
Beyond Two Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Beyond Spatial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9
SPATIAL TREES
139
Quadtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Building Uniform Quadtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Adding Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Removing Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Searching Uniform QuadTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Nearest-Neighbor Search Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
k-d Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
k-d Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Tighter Spatial Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Building k-d Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
k-d Tree Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10
HASH TABLES
171
Storage and Search with Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Handling Non-numeric Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
An Example Use Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185xiv Contents in Detail
11
CACHES
187
Introducing Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
LRU Eviction and Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Building an LRU Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
Updating an Element’s Recency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Other Eviction Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
12
B-TREES
199
B-tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Searching B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Adding Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
The Addition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Examples of Adding Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Removing Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Fixing Under-full Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Finding the Minimum Value Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
The Removal Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Examples of Removing Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
13
BLOOM FILTERS
225
Introducing Bloom Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Hash Tables of Indicators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
The Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Bloom Filter Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Tuning Bloom Filter Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Bloom Filters vs. Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
14
SKIP LISTS
235
Randomized vs. Deterministic Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Introducing Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Searching Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Adding Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Deleting Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Runtimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
15
GRAPHS
247
Introducing Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Representing Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
Searching Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Finding Shortest Paths with Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252Contents in Detail xv
Finding Minimum Spanning Trees with Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 256
Topological Sort with Kahn’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
CONCLUSION
265
What Is the Impact of the Data’s Structure? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
Do We Need Dynamic Data Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
What Is the Amortized Cost? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
How Can We Adapt Data Structures to a Specific Problem? . . . . . . . . . . . . . . . . . . . 267
What Are the Memory vs. Runtime Tradeoffs?............................. 268
How Can We Tune Our Data Structure? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
How Does Randomization Impact Expected Behavior? . . . . . . . . . . . . . . . . . . . . . . . 269
Why This Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
INDEX
271
好例子网口号：伸出你的我的手 — 分享！
相关软件
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论