Table of contents for Data abstraction and problem solving with C++ : walls and mirrors / Frank M. Carrano.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
vii
Contents
Preface xiii
Chapter Dependency Chart xv
PART ONE
Problem-Solving Techniques 1
1
Principles of Programming
and Software Engineering 3
1.1
Problem Solving and Software Engineering
4
An Examination of Problem Solving 4
Aspects of an Object-Oriented Solution 4
Abstraction and Information Hiding 5
Principles of Object-Oriented Programming 7
Object-Oriented Analysis and Design 8
Applying the UML to OOA/D 9
The Software Life Cycle 18
Iterative and Evolutionary Development 19
Rational Unified Process Development Phases 20
What about the Waterfall Method of Development? 22
1.2
Achieving a Better Solution
24
Evaluation of Designs and Solutions 24
Operation Contracts 27
Verification 29
What Is a Good Solution? 32
1.3
Key Issues in Programming
34
Modularity 35
Style 37
Modifiability 45
Ease of Use 47
Fail-Safe Programming 48
Debugging 53
Testing 56
Carrano_5e.book Page vii Monday, May 8, 2006 7:57 PM
viii
Contents
2
Recursion: The Mirrors 67
2.1
Recursive Solutions
68
A Recursive Valued Function: The Factorial of
n
71
A Recursive
void
Function: Writing a String Backward 78
2.2
Counting Things
83
Multiplying Rabbits (The Fibonacci Sequence) 87
Organizing a Parade 89
Mr. Spock's Dilemma (Choosing
k
Out of
n
Things) 92
2.3
Searching an Array
95
Finding the Largest Item in an Array 95
Binary Search 96
Finding the
k
th
Smallest Item of an Array 100
2.4
Organizing Data
104
The Towers of Hanoi 104
2.5
Recursion and Efficiency
108
3
Data Abstraction: The Walls 123
3.1
Abstract Data Types
124
3.2
Specifying ADTs
129
The ADT List 130
The ADT Sorted List 135
Designing an ADT 136
Axioms (Optional) 141
3.3
Implementing ADTs
143
C++ Classes 145
C++ Namespaces 154
An Array-Based Implementation of the ADT List 156
C++ Exceptions 162
An Implementation of the ADT List Using Exceptions 164
4
Linked Lists 173
4.1
Preliminaries
174
Pointers 175
Dynamic Allocation of Arrays 182
Pointer-Based Linked Lists 184
4.2
Programming with Linked Lists
186
Displaying the Contents of a Linked List 186
Deleting a Specified Node from a Linked List 188
Inserting a Node into a Specified Position of a Linked List 191
A Pointer-Based Implementation of the ADT List 196
Comparing Array-Based and Pointer-Based Implementations 204
Saving and Restoring a Linked List by Using a File 207
Passing a Linked List to a Method 210
Processing Linked Lists Recursively 212
Objects as Linked List Data 216
Carrano_5e.book Page viii Monday, May 8, 2006 7:57 PM
Contents
ix
4.3
Variations of the Linked List
217
Circular Linked Lists 218
Dummy Head Nodes 219
Doubly Linked Lists 220
4.4
Application: Maintaining an Inventory
223
4.5
The C++ Standard Template Library
229
Containers 230
Iterators 231
The Standard Template Library Class
list
232
5
Recursion as a Problem-Solving Technique 249
5.1
Backtracking
250
The Eight Queens Problem 250
Implementing Eight Queens Using the STL Class
vector
252
5.2
Defining Languages
257
The Basics of Grammars 258
Two Simple Languages 260
Algebraic Expressions 262
5.3
The Relationship Between Recursion
and Mathematical Induction
272
The Correctness of the Recursive Factorial Function 272
The Cost of Towers of Hanoi 273
PART TWO
Problem Solving with Abstract
Data Types 285
6
Stacks 287
6.1 The Abstract Data Type Stack 288
Developing an ADT During the Design of a Solution 288
6.2 Simple Applications of the ADT Stack 294
Checking for Balanced Braces 294
Recognizing Strings in a Language 296
6.3 Implementations of the ADT Stack 298
An Array-Based Implementation of the ADT Stack 299
A Pointer-Based Implementation of the ADT Stack 303
An Implementation That Uses the ADT List 307
Comparing Implementations 311
The Standard Template Library Class stack 311
6.4 Application: Algebraic Expressions 313
Evaluating Postfix Expressions 314
Converting Infix Expressions to Equivalent
Postfix Expressions 315
6.5 Application: A Search Problem 319
A Nonrecursive Solution That Uses a Stack 320
A Recursive Solution 329
Carrano_5e.book Page ix Monday, May 8, 2006 7:57 PM
x Contents
6.6 The Relationship Between Stacks and Recursion 331
7 Queues 345
7.1 The Abstract Data Type Queue 346
7.2 Simple Applications of the ADT Queue 348
Reading a String of Characters 348
Recognizing Palindromes 349
7.3 Implementations of the ADT Queue 350
A Pointer-Based Implementation 351
An Array-Based Implementation 356
An Implementation That Uses the ADT List 363
The Standard Template Library Class queue 366
Comparing Implementations 369
7.4 A Summary of Position-Oriented ADTs 370
7.5 Application: Simulation 371
8 Advanced C++ Topics 391
8.1 Inheritance Revisited 392
Public, Private, and Protected Inheritance 399
Is-a, Has-a, and As-a Relationships 399
8.2 Virtual Methods and Late Binding 402
Abstract Base Classes 408
8.3 Friends 412
8.4 The ADTs List and Sorted List Revisited 415
Implementations of the ADT Sorted List That Use the ADT List 417
8.5 Class Templates 422
8.6 Overloaded Operators 430
8.7 Iterators 434
Implementing the ADT List Using Iterators 436
9 Algorithm Efficiency and Sorting 449
9.1 Measuring the Efficiency of Algorithms 450
The Execution Time of Algorithms 451
Algorithm Growth Rates 452
Order-of-Magnitude Analysis and Big O Notation 454
Keeping Your Perspective 458
The Efficiency of Searching Algorithms 460
9.2 Sorting Algorithms and Their Efficiency 462
Selection Sort 463
Bubble Sort 466
Insertion Sort 468
Mergesort 470
Quicksort 476
Radix Sort 488
A Comparison of Sorting Algorithms 490
The Standard Template LibrarySorting Algorithms 491
Carrano_5e.book Page x Monday, May 8, 2006 7:57 PM
Contents xi
10 Trees 503
10.1 Terminology 505
10.2 The ADT Binary Tree 512
Traversals of a Binary Tree 516
Possible Representations of a Binary Tree 519
A Pointer-Based Implementation of the ADT Binary Tree 523
10.3 The ADT Binary Search Tree 539
Algorithms for the ADT Binary Search Tree Operations 543
A Pointer-Based Implementation of the ADT Binary Search Tree 559
The Efficiency of Binary Search Tree Operations 567
Treesort 572
Saving a Binary Search Tree in a File 573
The STL Search Algorithms 576
10.4 General Trees 579
11 Tables and Priority Queues 593
11.1 The ADT Table 594
Selecting an Implementation 599
A Sorted Array-Based Implementation of the ADT Table 606
A Binary Search Tree Implementation of the ADT Table 611
11.2 The ADT Priority Queue:
A Variation of the ADT Table 614
Heaps 618
A Heap Implementation of the ADT Priority Queue 627
Heapsort 630
11.3 Tables and Priority Queues in the STL 634
The STL Associative Containers 634
The STL priority_queue Class and Heap Algorithms 642
12 Advanced Implementations of Tables 653
12.1 Balanced Search Trees 654
2-3 Trees 655
2-3-4 Trees 674
Red-Black Trees 682
AVL Trees 685
12.2 Hashing 690
Hash Functions 694
Resolving Collisions 697
The Efficiency of Hashing 705
What Constitutes a Good Hash Function? 708
Table Traversal: An Inefficient Operation Under Hashing 710
Implementing a HashMap Class Using the STL 711
12.3 Data with Multiple Organizations 714
Carrano_5e.book Page xi Monday, May 8, 2006 7:57 PM
xii Contents
13 Graphs 725
13.1 Terminology 726
13.2 Graphs as ADTs 729
Implementing Graphs 730
Implementing a Graph Class Using the STL 733
13.3 Graph Traversals 736
Depth-First Search 737
Breadth-First Search 740
Implementing a BFS Class Using the STL 741
13.4 Applications of Graphs 744
Topological Sorting 744
Spanning Trees 747
Minimum Spanning Trees 751
Shortest Paths 753
Circuits 758
Some Difficult Problems 760
14 Processing Data in External Storage 769
14.1 A Look at External Storage 770
14.2 Sorting Data in an External File 773
14.3 External Tables 780
Indexing an External File 783
External Hashing 787
B-Trees 791
Traversals 801
Multiple Indexing 803
A Review of C++ Fundamentals 811
B ASCII Character Codes 882
C C++ Header Files and Standard Functions 885
D Mathematical Induction 891
E Standard Template Library 897
F C++ Documentation Systems 909
Glossary 938
Answers to Self-Test Questions 939
Index 957
Carrano_5e.book Page xii Monday, May 8, 2006 7:57 PM

Library of Congress Subject Headings for this publication:

C++ (Computer program language).
Abstract data types (Computer science).
Problem solving -- Data processing.