Mastering Algorithms with C

Mastering Algorithms with C

Kyle Loudon  (Author)

Product Details

• Series: Mastering
• Paperback: 562 pages
• Publisher: O'Reilly Media; 1 edition (August 12, 1999)
• Language: English
• ISBN-10: 1565924533
• ISBN-13: 978-1565924536
• Product Dimensions: 7 x 1.2 x 9.2 inches
  
  

本帖隐藏的内容

Mastering Algorithms with C 3rd Edition.pdf (5.04 MB, 需要: 10 个论坛币)

2014-12-26 16:02:35 上传

需要: 10 个论坛币  [购买]

O'Reilly精品图书系列

算法精解：C语言描述 [Mastering Algorithms with C]

[美] Kyle Loudon 著； 肖翔，陈舸 译

本书是数据结构和算法领域的经典之作，十余年来，畅销不衰！全书共分为三部分：第一部分首先介绍了数据结构和算法的概念，以及使用它们的原因和意义，然后讲解了数据结构和算法中最常用的技术——指针和递归，最后还介绍了算法的分析方法，旨在为读者学习这本书打下坚实的基础；第二部分对链表、栈、队列、集合、哈希表、堆、图等常用数据结构进行了深入阐述；第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。 本书的众多特色使得它在同类书中独树一帜：具体实现都采用正式的C语言代码而不是伪代码，在很多数据结构和算法的实现过程中，有大量细节问题是伪代码不能解决的；每一章都有精心组织的主题和应用；全部示例来自真实的应用，不只是一般的练习；对每种数据结构、算法和示例都进行了详细分析；每一章的末尾都会有一系列问题和对应的回答，旨在强调这一章的重要思想…… 本书中的代码尤为值得强调：所有实现都采用C语言编写，所有代码都优先用于教学目的，所有代码都在4种平台上经过完整测试，头文件记录了所有公共的接口，命名规则适用于全书所有的代码，所有的代码都包含大量注释…… 本书内容包括： · 数据结构和算法的概念，以及使用它们的原因和意义 · 指针和递归 · 算法分析 · 常用数据结构：链表、栈、队列、集合、哈希表、树、堆、优先级队列以及图 · 排序和搜索 · 数值计算 · 数据压缩 · 数据加密 · 图算法 · 几何算法

Table of contents :
Table of Contents......Page 7
Organization......Page 13
Part III......Page 14
Key Features......Page 15
About the Code......Page 16
How to Contact Us......Page 17
Acknowledgments......Page 18
I......Page 21
Introduction......Page 23
An Introduction to Data Structures......Page 24
An Introduction to Algorithms......Page 25
Divide-and-conquer algorithms......Page 26
Greedy algorithms......Page 27
A Bit About Software Engineering......Page 28
How to Use This Book......Page 30
Pointer Manipulation......Page 31
Storage Allocation......Page 32
Structures......Page 35
Arrays......Page 36
Pointers as Parameters to Functions......Page 37
Call-by-Reference Parameter Passing......Page 38
Pointers to Pointers as Parameters......Page 40
Generic Pointers......Page 41
Function Pointers......Page 43
Questions and Answers......Page 44
Related Topics......Page 45
Recursion......Page 47
Basic Recursion......Page 48
Tail Recursion......Page 52
Questions and Answers......Page 54
Related Topics......Page 57
Analysis of Algorithms......Page 58
Reasons for Worst-Case Analysis......Page 59
Simple Rules for O-Notation......Page 60
O-Notation Example and Why It Works......Page 61
Computational Complexity......Page 62
Analysis Example: Insertion Sort......Page 65
Questions and Answers......Page 67
Related Topics......Page 68
II......Page 69
Linked Lists......Page 71
Description of Linked Lists......Page 72
list_init......Page 73
list_rem_next......Page 74
list_is_tail......Page 75
ImplementationandAnalysis ofLinkedLists......Page 76
list_ins_next......Page 78
list_rem_next......Page 79
list_size, list_head, list_tail, list_is_tail, list_data, and list_next......Page 80
LinkedListExample:Frame Management......Page 85
dlist_init......Page 88
dlist_ins_prev......Page 89
dlist_tail......Page 90
dlist_prev......Page 91
Implementation and Analysis ofDoublyLinked Lists......Page 92
dlist_destroy......Page 93
dlist_ins_next......Page 94
dlist_size, dlist_head, dlist_tail, dlist_is_head, dlist_is_tail, dlist_data, dlist_next, and dli.........Page 95
clist_init......Page 102
clist_rem_next......Page 103
Implementation and Analysis ofCircular Lists......Page 104
clist_ins_next......Page 106
clist_size, clist_head, clist_data, and clist_next......Page 107
Circular List Example: Second-Chance Page Replacement......Page 111
Questions and Answers......Page 114
Related Topics......Page 116
Stacks and Queues......Page 118
Description of Stacks......Page 119
stack_destroy......Page 120
stack_size......Page 121
Implementation and Analysis of Stacks......Page 122
stack_pop......Page 123
stack_peek, stack_size......Page 124
queue_init......Page 125
queue_dequeue......Page 126
Implementation and Analysis of Queues......Page 127
queue_dequeue......Page 128
queue_peek, queue_size......Page 129
Queue Example: Event Handling......Page 130
Questions and Answers......Page 133
Related Topics......Page 134
Sets......Page 135
Description of Sets......Page 136
Basic Operations......Page 137
Properties......Page 138
set_destroy......Page 139
set_union......Page 140
set_is_subset......Page 141
Implementation and Analysis of Sets......Page 142
set_init......Page 143
set_union......Page 144
set_is_subset......Page 145
set_size......Page 146
Set Example: Set Covering......Page 153
Questions and Answers......Page 158
Related Topics......Page 160
Hash Tables......Page 161
Collision Resolution......Page 163
Selecting a Hash Function......Page 164
Multiplication method......Page 165
chtbl_destroy......Page 167
chtbl_size......Page 168
ImplementationandAnalysis ofChainedHashTables......Page 169
chtbl_destroy......Page 170
chtbl_size......Page 171
ChainedHashTableExample: SymbolTables......Page 177
Collision Resolution......Page 181
Linear probing......Page 182
Double hashing......Page 183
ohtbl_init......Page 184
ohtbl_remove......Page 185
ImplementationandAnalysis of Open AddressedHashTables......Page 186
ohtbl_insert......Page 188
ohtbl_size......Page 189
Questions and Answers......Page 196
Related Topics......Page 197
Trees......Page 198
Traversal Methods......Page 200
Preorder traversal......Page 201
Tree Balancing......Page 202
bitree_init......Page 203
bitree_ins_right......Page 204
bitree_size......Page 205
bitree_left......Page 206
ImplementationandAnalysis ofBinaryTrees......Page 207
bitree_rem_left......Page 209
bitree_size, bitree_root, bitree_is_eob, bitree_is_leaf, bitree_data, bitree_left, bitree_right......Page 210
BinaryTreeExample: ExpressionProcessing......Page 219
Description of Binary Search Trees......Page 223
bistree_init......Page 224
bistree_remove......Page 225
ImplementationandAnalysis ofBinarySearchTrees......Page 226
LL rotation......Page 227
RR rotation......Page 228
RL rotation......Page 229
bistree_destroy......Page 232
bistree_insert......Page 233
bistree_remove......Page 234
bistree_size......Page 235
Questions and Answers......Page 250
Related Topics......Page 253
Heapsand PriorityQueues......Page 255
Description of Heaps......Page 256
heap_init......Page 257
heap_extract......Page 258
Implementation and Analysis of Heaps......Page 259
heap_insert......Page 260
heap_size......Page 262
Description of Priority Queues......Page 270
pqueue_insert......Page 271
ImplementationandAnalysis ofPriorityQueues......Page 272
Priority Queue Example: Parcel Sorting......Page 274
Questions and Answers......Page 276
Related Topics......Page 278
Graphs......Page 279
Description of Graphs......Page 281
Breadth-first search......Page 284
Depth-first search......Page 286
graph_init......Page 287
graph_ins_edge......Page 288
graph_adjlist......Page 289
Implementation and Analysis of Graphs......Page 290
graph_init......Page 292
graph_ins_edge......Page 293
graph_is_adjacent......Page 294
graph_adjlists, graph_vcount, graph_ecount......Page 295
Graph Example: Counting Network Hops......Page 304
Graph Example: Topological Sorting......Page 310
Questions and Answers......Page 315
Related Topics......Page 317
III......Page 319
Sorting and Searching......Page 321
issort......Page 323
Implementation and Analysis of Insertion Sort......Page 324
Description of Quicksort......Page 327
ImplementationandAnalysis ofQuicksort......Page 328
Quicksort Example: Directory Listings......Page 334
Description of Merge Sort......Page 337
ImplementationandAnalysis ofMergeSort......Page 338
Description of Counting Sort......Page 344
ImplementationandAnalysis ofCountingSort......Page 345
rxsort......Page 349
ImplementationandAnalysis ofRadixSort......Page 350
Description of Binary Search......Page 353
ImplementationandAnalysis ofBinarySearch......Page 354
Binary Search Example: Spell Checking......Page 357
Questions and Answers......Page 359
Related Topics......Page 361
Numerical Methods......Page 363
Description of Polynomial Interpolation......Page 364
Constructing an Interpolating Polynomial......Page 365
Evaluating an Interpolating Polynomial......Page 366
interpol......Page 368
ImplementationandAnalysis ofPolynomialInterpolation......Page 369
Description of Least-Squares Estimation......Page 372
lsqe......Page 373
Implementation and Analysis of Least-Squares Estimation......Page 374
Finding Roots with Newton’s Method......Page 375
Understanding the First and Second Derivative......Page 376
Selecting an Initial Point for Newton’s Method......Page 377
How Newton’s Method Works......Page 378
ImplementationandAnalysis oftheSolutionofEquations......Page 380
Questions and Answers......Page 382
Related Topics......Page 383
Data Compression......Page 385
bit_set......Page 389
bit_get......Page 390
bit_rot_left......Page 391
Entropy and Minimum Redundancy......Page 395
Building a Huffman Tree......Page 396
Compressing and Uncompressing Data......Page 397
Effectiveness of Huffman Coding......Page 398
huffman_uncompress......Page 399
huffman_compress......Page 400
huffman_uncompress......Page 401
HuffmanCodingExample: OptimizedNetworking......Page 416
Maintaining a Dictionary of Phrases......Page 419
Effectiveness of LZ77......Page 420
lz77_compress......Page 422
lz77_compress......Page 423
lz77_uncompress......Page 425
Questions and Answers......Page 438
Related Topics......Page 440
Data Encryption......Page 442
Description of DES......Page 445
Computing Subkeys......Page 446
Enciphering and Deciphering Data Blocks......Page 448
des_encipher......Page 452
des_encipher......Page 453
des_decipher......Page 455
DES Example: Block Cipher Modes......Page 465
Description of RSA......Page 468
Computing Public and Private Keys......Page 469
Enciphering and Deciphering Data Blocks......Page 471
Implementation and Analysis of RSA......Page 472
rsa_encipher......Page 473
rsa_decipher......Page 474
Questions and Answers......Page 476
Related Topics......Page 478
Graph Algorithms......Page 480
Description of Minimum Spanning Trees......Page 483
Prim’s Algorithm......Page 484
mst......Page 485
Implementation and Analysis ofMinimum Spanning Trees......Page 486
Description of Shortest Paths......Page 492
Dijkstra’s Algorithm......Page 493
shortest......Page 494
Implementation and Analysis ofShortestPaths......Page 495
Shortest Paths Example: Routing Tables......Page 501
Description of the Traveling-Salesman Problem......Page 505
Applying the Nearest-Neighbor Heuristic......Page 506
tsp......Page 507
Implementation and Analysis oftheTraveling-Salesman Problem......Page 508
Questions and Answers......Page 513
Related Topics......Page 515
Geometric Algorithms......Page 516
Description of Testing Whether Line Segments Intersect......Page 519
Standard Test for Intersecting Line Segments......Page 520
Computer Test for Intersecting Line Segments......Page 521
lint......Page 522
Implementation and Analysis of Testing Whether Line Segments Intersect......Page 523
Jarvis’s March......Page 525
ImplementationandAnalysis ofConvexHulls......Page 527
Description of Arc Length onSphericalSurfaces......Page 532
Converting Between Coordinate Systems......Page 533
Computing the Length of an Arc......Page 534
arclen......Page 535
Implementation and Analysis of Arc Length on Spherical Surfaces......Page 536
Arc Length Example: Approximating Distances on Earth......Page 537
Questions and Answers......Page 540
Related Topics......Page 543
Index......Page 545