1 Introduction 1
1-1 Pseudocode 2
·Algorithm Header 2
·Purpose, Conditions, and Return 3
·Statement Numbers 4
·Variables 4
·Algorithm Analysis 5
·Statement Constructs 5
·Pseudocode Example 6
1-2 The Abstract Data Type 7
·Atomic and Composite Data 8
·Data Structure 8
·Abstract Data Type 9
1-3 A Model for an Abstract Data Type 10
·ADT Operations 11
·ADT Data Structure 11
·ADT Class Templates 13
1-4 Algorithm Efficiency 13
·Linear Loops 14
·Logarithmic Loops 14
·Nested Loops 15
·Big-O Notation 17
·Standard Measures of Efficiency 19
·Big-O Analysis Examples 20
1-5 Summary 22
1-6 Practice Sets 23
·Exercises 23
·Problems 25
·Projects 25
2 Searching 27
2-1 List Searches 28
·Sequential Search 28
·Variations on Sequential Searches 30
·Binary Search 33
·Binary Search Algorithm 36
·Analyzing Search Algorithms 37
2-2 C++ Search Algorithms 38
·Sequential Search in C++ 38
·Binary Search in C++ 40
·Search Example 41
2-3 Hashed List Searches 44
·Basic Concepts 44
·Hashing Methods 46
·Hashing Algorithm 50
2-4 Collision Resolution 51
·Open Addressing 53
·Linked List Resolution 57
·Bucket Hashing 57
·Combination Approaches 58
·Hash List Example 58
2-5 Summary 62
2-6 Practice Sets 64
·Exercises 64
·Problems 65
·Projects 65
3 Linked Lists 67
3-1 Linear List Concepts 68
·Insertion 68
·Deletion 69
·Retrieval 70
·Traversal 70
3-2 Linked List Concepts 70
·Nodes 71
·Linked List Data Structure 71
·Pointers to Linked Lists 73
3-3 Linked List Algorithms 73
·Create List 73
·Insert Node 74
·Delete Node 78
·Search List 80
·Unordered List Search 83
·Retrieve Node 83
·Empty List 84
·Full List 84
·List Count 85
·Traverse List 85
·Destroy List 87
3-4 Processing a Linked List 88
·Add Node 90
·Remove Node 90
·Print List 91
·Testing Insert and Delete Logic 92
3-5 List Applications 93
·Append Lists 93
·Array of Lists 95
3-6 Complex Linked List Structures 97
·Circularly Linked Lists 97
·Doubly Linked Lists 98
·Multilinked Lists 103
·Multilinked List Insert 104
·Multilinked List Delete 105
3-7 Building a Linked List——C++ Implementation 105
·Data Structure 105
·Application Functions 106
3-8 List Abstract Data Type——Linked List Implementation 112
·List ADT Declaration 113
3-9 Summary 124
3-10 Practice Sets 125
·Exercises 125
·Problems 127
·Projects 128
4 Stacks 135
4-1 Basic Stack Operations 136
·Push 136
·Pop 136
·Stack Top 137
4-2 Stack Linked List Implementation 137
·Data Structure 137
·Stack Algorithms 139
4-3 Stack Applications 148
·Reversing Data 146
·Reverse a List 146
·Convert Decimal to Binary 147
·Parsing 148
·Postponement 149
·Backtracking 157
4-4 Eight Queens Problem——C++ Implementation 163
·Main Line Logic 164
·Get Board Size 164
4-5 Stack Abstract Data Type Implementation 169
·Data Structure 169
·Stack ADT Implementation 170
4-6 Stack ADT—Array Implementation 175
·Array Data Structure 176
·Create Stack Array 177
·Push Stack Array 178
·Pop Stack Array 178
·Stack Top Array 179
·Empty Stack Array 180
·Full Stack Array 180
·Stack Count Array 180
·Destroy Stack Array 181
4-7 Summary 181
4-8 Practice Sets 182
·Exercises 182
·Problems 183
·Projects 185
5 Queues 189
5-1 Queue Operations 190
·Enqueue 190
·Dequeue 190
·Queue Front 191
·Queue Rear 191
·Queue Example 192
5-2 Queue Linked List Design 192
·Data Structure 192
·Queue Algorithms 194
·Create Queue 194
·Enqueue 196
·Dequeue 197
·Retrieving Queue Data 198
·Empty Queue 199
·Full Queue 199
·Queue Count 200
·Destroy Queue 200
5-3 Queuing Theory 200
5-4 Queue Applications 202
·Queue Simulation 202
·Categorizing Data 209
5-5 Categorizing Data——C++ Implementation 211
·Main Line Logic 211
·Fill Queues 212
·Print Queues 213
·Print One Queue 214
5-6 Queue ADT——Linked List Implementation 215
·Queue Structure 215
·Queue ADT Implementation 216
5-7 Queue ADT——Array Implementation 221
·Array Queues Implementation 222
5-8 Summary 228
5-9 Practice Sets 229
·Exercises 229
·Problems 231
·Projects 232
6 Recursion 237
6-1 Factorial——A Case Study 238
·Recursion Defined 238
·Iterative Solution 239
·Recursive Solution 239
6-2 How Recursion Works 240
6-3 Designing Recursive Algorithms 242
·The Design Methodology 243
·Limitations of Recursion 243
·Design Implementation——Reverse a Linked List 244
6-4 Another Case Study——Fibonacci Numbers 246
6-5 The Towers of Hanoi 249
·Recursive Towers Of Hanoi 250
6-6 C++ Implementations of Recursion 253
·Fibonacci Numbers 253
·Prefix to Postfix Conversion 254
·Towers of Hanoi 259
6-7 Summary 260
6-8 Practice Sets 261
·Exercises 261
·Problems 263
·Projects 264
7 Introduction to Trees 265
7-1 Basic Tree Concepts 266
·Terminology 266
·Tree Representation 268
7-2 Binary Trees 270
·Properties 271
7-3 Binary Tree Traversals 273
·Depth-First Traversals 273
·Breadth-First Traversals 278
7-4 Expression Trees 280
·Infix Traversal 280
·Postfix Traversal 281
·Prefix Traversal 282
7-5 General Trees 282
·Changing General Tree to Binary Tree 282
·Insertions into General Trees 283
·General Tree Deletions 285
7-6 Huffman Code 285
7-7 Summary 288
7-8 Practice Sets 290
·Exercises 293
·Problems 293
·Projects 293
8 Search Trees 294
8-1 Binary Search Trees 295
·Definition 295
·Operations on Binary Search Trees 296
·Binary Search Tree Search Algorithms 297
8-2 AVL Trees 306
·AVL Balance Factor 309
·Balancing Trees 309
·AVL Node Structure 314
·AVL Delete Algorithm 319
·Adjusting the Balance Factors 323
8-3 AVL Tree Implementation 324
·Data Structure 324
·Program Design 325
·Count Words Summary 328
8-4 AVL Abstract Data Type 329
·AVL Tree Data Structures 330
·AVL Tree Functions 331
·AVL Tree Data Processing 342
·AVL Tree Utility Functions 344
8-5 Summary 347
8-6 Practice Sets 348
·Exercises 348
·Problems 350
·Projects 351
9 Heaps 354
9-1 Heap Definition 355
9-2 Heap Structure 355
9-3 Basic Heap Algorithms 356
·ReheapUp 356
·ReheapDown 358
9-4 Heap Data Structure 360
9-5 Heap Algorithms 361
·ReheapUp 361
·ReheapDown 362
·BuildHeap 363
·InsertHeap 364
·DeleteHeap 365
9-6 Heap Applications 367
·Selection Algorithms 367
·Priority Queues 368
9-7 A Heap Program 370
·Heap Program Design 370
·Heap Functions 375
9-8 Summary 377
9-9 Practice Sets 378
·Exercises 378
·Problems 380
·Projects 380
10 Multiway Trees 383
10-1 m-Way Search Trees 384
10-2 B-Trees 385
·B-Tree Insertion 387
·B-Tree Insert Design 388
·B-Tree Insert Node 389
·B-Tree Deletion 396
·Traverse B-Tree 407
·B-Tree Search 410
10-3 Simplified B-Trees 411
·2-3 Tree 411
·2-3-4 Tree 411
10-4 B-Tree Variations 412
·B*Tree 412
·B+Tree 413
10-5 Lexical Search Tree 413
·Tries 414
·Trie Structure 415
10-6 B-Tree Abstract Data Type 415
·Header File 415
·Utility Functions 415
·Insert Algorithms 423
·Delete Algorithms 428
10-7 Summary 434
10-8 Practice Sets 435
·Exercises 435
·Problems 436
·Projects 436
11 Advanced Sorting Concepts 438
11-1 General Sort Concepts 439
·Sort Order 439
·Sort Stability 440
·Sort Efficiency 440
·Passes 440
11-2 Insertion Sorts 441
·Straight Insertion Sort 441
·Shell Sort 443
·Insertion Sort Algorithms 447
·Insertion Sort Implementation 449
11-3 Selection Sorts 451
·Straight Selection Sort 451
·Selection Sort Algorithms 456
·Selection Sort Implementation 457
11-4 Exchange Sorts 459
·Bubble Sort 459
·Bubble Sort Algorithm 461
·Quick Sort 462
·Exchange Sort Algorithms 468
11-5 Summary 470
·Exchange Sort Implementation 470
11-6 External Sorts 474
·Merging Ordered Files 474
·Merging Unordered Files 475
·The Sorting Process 476
·Sort Phase Revisited 482
11-7 Summary 484
11-8 Practice Sets 485
·Exercises 485
·Problems 486
·Projects 486
12 Graphs 490
12-1 Terminology 491
12-2 Operations 492
·Add Vertex 492
·Delete Vertex 493
·Add Edge 493
·Delete Edge 493
·Find Vertex 493
·Traverse Graph 494
12-3 Graph Storage Structures 497
·Adjacency Matrix 497
·Adjacency List 498
12-4 Graph Algorithms 499
·Create Graph 500
·Insert Vertex 500
·Delete Vertex 502
·Insert Arc 503
·Delete Arc 505
·Retrieve Vertex 506
·First Arc 507
·Depth-First Traversal 508
·Breadth-First Traversal 510
12-5 Networks 512
·Minimum Spanning Tree 512
·Shortest Path Algorithm 517
12-6 Abstract Data Type 521
·Insert Vertex 523
·Delete Vertex 524
·Insert Arc 525
·Delete Arc 526
·Depth-First Traversal 528
·Breadth-First Traversal 529
12-7 Summary 531
12-8 Practice Sets 532
·Exercises 532
·Problems 533
·Projects 534
Appendixes
A ASCII Tables 537
B Structure Charts 542
C Program Standards and Styles 549
D Random Numbers 554
E Standard C++ Libraries 559
F C++ Function Prototypes 561
G Classes Related to Input and Output 569
H The String Class 574
I Pointers to Functions 584
J Inheritance 587
K C++ Templates 601
L Standard Template Library 608
Solutions to Selected Exercises 626
Glossary 647
Index 657
【媒体评论】
鄂公网安备 42010302001612号 