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
Data Structure 8
Atomic and Composite Data 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
Bucket Hashing 57
Linked List Resolution 57
Hash List Example 58
Combination Approaches 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
3-2 Linked List Concepts 70
Retrieval 70
Traversal 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
Retrleve Node 83
Unordered List Search 83
Full List 84
Empty 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
Append Lists 93
3-5 List Applications 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
Data Structure 137
4-2 Stack Linked List Implementation 137
Stack Top 137
Stack Algorithms 139
4-3 Stack Applications 146
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
Get Board Size 164
Main Line Logic 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
Stack Count Array 180
Full Stack Array 180
Empty Stack Array 180
Destory 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 Rear 191
Queue Front 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
Full Queue 199
Empty 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
Queue Structure 215
5-6 Queue ADT-Linked List Implementation 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
Recursive Solution 239
Iterative 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
Depth-First Traversals 273
7-3 Binary Tree 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 290
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
Balancing Trees 309
AVL Balance Factor 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
Utility Functions 415
Header File 415
Trie Structure 415
10-6 B-Tree Abstract Data Type 415
Insert Algorithms 428
Delete Algorithms 428
10-7 Summary 434
10-8 Practice Sets 435
Exercises 435
Problems 436
Projects 436
11 Advanced Sorting Concepts 438
Sort Order 439
11-1 General Sort Concepts 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
Find Vertex 493
Delete Edge 493
Add Edge 493
Delete 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 537
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