Data Abstraction and Problem Solving with C++

by Carrano, Frank M.

• ISBN13: 9780321433329
• ISBN10: 0321433327
• Edition: 5th
• Format: Paperback
• Copyright: 2006-07-14
• Publisher: Prentice Hall

Summary

Data Structures/C++ Data Abstraction and Problem Solving with C++: Walls and Mirrors Frank M. Carrano, University of Rhode Island This fifth edition of the classic, best-selling book Data Abstraction and Problem Solving with C++: Walls and Mirrors continues to offer students a superior foundation in data abstraction, object-oriented programming, and problem-solving techniques. The focus is on core abstract data types with the consistent use of data abstraction emphasizing the distinction between specification and implementation. Fifth Edition highlights: bull; Completely revised software engineering concepts to conform with modern practice bull; NEW! Introduces techniques for testing software bull; NEW! Presents ADT (abstract data type) behaviors as operation contracts bull; Includes extensive coverage of object-oriented programming techniques bull; NEW! Includes an introduction to Doxygen, a documentation generator for C++ that is similar to Javadoc bull; Contains major applications of ADTs, such as searching a flight map, event-driven simulation, and the eight queens problem bull; Covers the use of the Standard Template Library (STL), with examples included in most chapters bull; Updated all C++ code to ensure compliance with the latest ANSI standards bull; Includes "Review of C++ Fundamentals" appendix for students who are making the transition to C++ from another language Addison-Wesley Computing Leading Authors bull; Quality Products Visit aw.com/computing for more information about Addison-Wesley computing books. ISBN 0-321-43332-7

Author Biography

Frank M. Carrano is a professor emeritus of computer science at the University of Rhode Island. He received the Ph.D. degree in computer science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates.

Frank’s Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science.

Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano

Find him on Facebook: https://www.facebook.com/makingitreal

Table of Contents

Preface	ix
Chapter Dependency Chart	xi
PART ONE Problem-Solving Techniques	1	(282)
Principles of Programming and Software Engineering	3	(62)
Software Engineering and Object-Oriented Design	4	(20)
An Examination of Problem Solving	4	(1)
Aspects of an Object-Oriented Solution	4	(1)
Abstraction and Information Hiding	5	(2)
Principles of Object-Oriented Programming	7	(1)
Object-Oriented Analysis and Design	8	(1)
Applying the UML to OOA/D	9	(10)
The Software Life Cycle	19	(1)
Iterative and Evolutionary Development	19	(1)
Rational Unified Process Development Phases	20	(3)
What About the Waterfall Method of Development?	23	(1)
Achieving a Better Solution	24	(10)
Evaluation of Designs and Solutions	24	(3)
Operation Contracts	27	(2)
Verification	29	(3)
What Is a Good Solution?	32	(2)
Key Issues in Programming	34	(31)
Modularity	35	(1)
Style	36	(9)
Modifiability	45	(2)
Ease of Use	47	(1)
Fail-Safe Programming	48	(5)
Debugging	53	(2)
Testing	55	(10)
Recursion: The Mirrors	65	(56)
Recursive Solutions	66	(19)
A Recursive Valued Function: The Factorial of n	69	(7)
A Recursive void Function: Writing a String Backward	76	(9)
Counting Things	85	(8)
Multiplying Rabbits (The Fibonacci Sequence)	85	(2)
Organizing a Parade	87	(3)
Mr. Spock's Dilemma (Choosing k Out of n Things)	90	(3)
Searching an Array	93	(9)
Finding the Largest Item in an Array	93	(1)
Binary Search	94	(4)
Finding the kth Smallest Item of an Array	98	(4)
Organizing Data	102	(4)
The Towers of Hanoi	102	(4)
Recursion and Efficiency	106	(15)
Data Abstraction: The Walls	121	(50)
Abstract Data Types	122	(5)
Specifying ADTs	127	(14)
The ADT List	128	(5)
The ADT Sorted List	133	(1)
Designing an ADT	134	(5)
Axioms (Optional)	139	(2)
Implementing ADTs	141	(30)
C++ Classes	143	(9)
C++ Namespaces	152	(2)
An Array-Based Implementation of the ADT List	154	(6)
C++ Exceptions	160	(2)
An Implementation of the ADT List Using Exceptions	162	(9)
Linked Lists	171	(76)
Preliminaries	172	(12)
Pointers	173	(7)
Dynamic Allocation of Arrays	180	(2)
Pointer-Based Linked Lists	182	(2)
Programming with Linked Lists	184	(31)
Displaying the Contents of a Linked List	184	(2)
Deleting a Specified Node from a Linked List	186	(3)
Inserting a Node into a Specified Position of a Linked List	189	(5)
A Pointer-Based Implementation of the ADT List	194	(8)
Comparing Array-Based and Pointer-Based Implementations	202	(3)
Saving and Restoring a Linked List by Using a File	205	(3)
Passing a Linked List to a Method	208	(1)
Processing Linked Lists Recursively	209	(5)
Objects as Linked List Data	214	(1)
Variations of the Linked List	215	(6)
Circular Linked Lists	216	(1)
Dummy Head Nodes	217	(1)
Doubly Linked Lists	218	(3)
Application: Maintaining an Inventory	221	(6)
The C++ Standard Template Library	227	(20)
Containers	228	(1)
Iterators	229	(1)
The Standard Template Library Class list	230	(17)
Recursion as a Problem-Solving Technique	247	(36)
Backtracking	248	(8)
The Eight Queens Problem	248	(2)
Implementing Eight Queens Using the STL Class vector	250	(6)
Defining Languages	256	(14)
The Basics of Grammars	256	(2)
Two Simple Languages	258	(2)
Algebraic Expressions	260	(10)
The Relationship Between Recursion and Mathematical Induction	270	(13)
The Correctness of the Recursive Factorial Function	270	(1)
The Cost of Towers of Hanoi	271	(12)
PART TWO Problem Solving with Abstract Data Types	283	(524)
Stacks	285	(58)
The Abstract Data Type Stack	286	(6)
Developing an ADT During the Design of a Solution	286	(6)
Simple Applications of the ADT Stack	292	(4)
Checking for Balanced Braces	292	(2)
Recognizing Strings in a Language	294	(2)
Implementations of the ADT Stack	296	(15)
An Array-Based Implementation of the ADT Stack	297	(4)
A Pointer-Based Implementation of the ADT Stack	301	(4)
An Implementation That Uses the ADT List	305	(3)
Comparing Implementations	308	(1)
The Standard Template Library Class stack	309	(2)
Application: Algebraic Expressions	311	(5)
Evaluating Postfix Expressions	311	(2)
Converting Infix Expressions to Equivalent Postfix Expressions	313	(3)
Application: A Search Problem	316	(13)
A Nonrecursive Solution That Uses a Stack	317	(10)
A Recursive Solution	327	(2)
The Relationship Between Stacks and Recursion	329	(14)
Queues	343	(44)
The Abstract Data Type Queue	344	(2)
Simple Applications of the ADT Queue	346	(2)
Reading a String of Characters	346	(1)
Recognizing Palindromes	347	(1)
Implementations of the ADT Queue	348	(20)
A Pointer-Based Implementation	349	(5)
An Array-Based Implementation	354	(7)
An Implementation That Uses the ADT List	361	(3)
The Standard Template Library Class queue	364	(3)
Comparing Implementations	367	(1)
A Summary of Position-Oriented ADTs	368	(1)
Application: Simulation	369	(18)
Advanced C++ Topics	387	(58)
Inheritance Revisited	388	(10)
Public, Private, and Protected Inheritance	395	(1)
Is-a, Has-a, and As-a Relationships	395	(3)
Virtual Methods and Late Binding	398	(10)
Abstract Base Classes	404	(4)
Friends	408	(3)
The ADTs List and Sorted List Revisited	411	(8)
Implementations of the ADT Sorted List That Use the ADT List	413	(6)
Class Templates	419	(7)
Overloaded Operators	426	(5)
Iterators	431	(14)
Implementing the ADT List Using Iterators	433	(12)
Algorithm Efficiency and Sorting	445	(54)
Measuring the Efficiency of Algorithms	446	(12)
The Execution Time of Algorithms	447	(1)
Algorithm Growth Rates	448	(2)
Order-of-Magnitude Analysis and Big O Notation	450	(4)
Keeping Your Perspective	454	(2)
The Efficiency of Searching Algorithms	456	(2)
Sorting Algorithms and Their Efficiency	458	(41)
Selection Sort	459	(3)
Bubble Sort	462	(2)
Insertion Sort	464	(2)
Mergesort	466	(6)
Quicksort	472	(12)
Radix Sort	484	(2)
A Comparison of Sorting Algorithms	486	(1)
The Standard Template LibrarySorting Algorithms	487	(12)
Trees	499	(90)
Terminology	500	(8)
The ADT Binary Tree	508	(28)
Traversals of a Binary Tree	512	(3)
Possible Representations of a Binary Tree	515	(4)
A Pointer-Based Implementation of the ADT Binary Tree	519	(17)
The ADT Binary Search Tree	536	(39)
Algorithms for the ADT Binary Search Tree Operations	539	(16)
A Pointer-Based Implementation of the ADT Binary Search Tree	555	(9)
The Efficiency of Binary Search Tree Operations	564	(4)
Treesort	568	(1)
Saving a Binary Search Tree in a File	569	(3)
The STL Search Algorithms	572	(3)
General Trees	575	(14)
Tables and Priority Queues	589	(60)
The ADT Table	590	(20)
Selecting an Implementation	595	(7)
A Sorted Array-Based Implementation of the ADT Table	602	(5)
A Binary Search Tree Implementation of the ADT Table	607	(3)
The ADT Priority Queue: A Variation of the ADT Table	610	(20)
Heaps	614	(9)
A Heap Implementation of the ADT Priority Queue	623	(3)
Heapsort	626	(4)
Tables and Priority Queues in the STL	630	(19)
The STL Associative Containers	630	(8)
The STL priority_queue Class and Heap Algorithms	638	(11)
Advanced Implementations of Tables	649	(72)
Balanced Search Trees	650	(36)
2-3 Trees	651	(19)
2-3-4 Trees	670	(8)
Red-Black Trees	678	(3)
AVL Trees	681	(5)
Hashing	686	(24)
Hash Functions	690	(3)
Resolving Collisions	693	(8)
The Efficiency of Hashing	701	(3)
What Constitutes a Good Hash Function?	704	(2)
Table Traversal: An Inefficient Operation Under Hashing	706	(1)
Implementing a HashMap Class Using the STL	707	(3)
Data with Multiple Organizations	710	(11)
Graphs	721	(44)
Terminology	722	(3)
Graphs as ADTs	725	(7)
Implementing Graphs	726	(3)
Implementing a Graph Class Using the STL	729	(3)
Graph Traversals	732	(8)
Depth-First Search	733	(3)
Breadth-First Search	736	(1)
Implementing a BFS Class Using the STL	737	(3)
Applications of Graphs	740	(25)
Topological Sorting	740	(3)
Spanning Trees	743	(4)
Minimum Spanning Trees	747	(2)
Shortest Paths	749	(5)
Circuits	754	(2)
Some Difficult Problems	756	(9)
Processing Data in External Storage	765	(42)
A Look at External Storage	766	(3)
Sorting Data in an External File	769	(7)
External Tables	776	(31)
Indexing an External File	779	(4)
External Hashing	783	(4)
B-Trees	787	(10)
Traversals	797	(2)
Multiple Indexing	799	(8)
Review of C++ Fundamentals	807	(73)
ASCII Character Codes	880	(1)
C++ Header Files and Standard Functions	881	(6)
Mathematical Induction	887	(6)
Standard Template Library	893	(12)
C++ Documentation Systems	905	(4)
Glossary	909	(26)
Answers to Self-Test Exercises	935	(18)
Index	953