Data Abstraction and Problem Solving with C++

by Carrano, Frank

• ISBN13: 9780321247254
• ISBN10: 0321247256
• Additional ISBN(s): 9780201741193, 9780321433329
• Edition: 4th
• Format: Paperback
• Copyright: 2007-01-01
• Publisher: Addison Wesley
• More Book Details
• Purchase Benefits

Summary

This classic book has been revised to further enhance its focus on data abstraction and data structures using C++. In this new edition, the clarity of the C++ language is enhanced, along with coverage of the latest C++ features, including stronger use of the Standard Template Library. This edition continues with Frank Carrano's lucid writing style, widespread use of examples, and flexible coverage of important topics.

Table of Contents

Preface	v
Chapter Dependency Chart	vii
PART I Problem-Solving Techniques	1	(278)
CHAPTER 1 Principles of Programming and Software Engineering	2	(51)
1.1 Problem Solving and Software Engineering	3	(12)
What Is Problem Solving?	3	(1)
The Life Cycle of Software	4	(9)
What Is a Good Solution?	13	(2)
1.2 Achieving a Modular Design	15	(11)
Abstraction and Information Hiding	15	(2)
Object-Oriented Design	17	(3)
Top-Down Design	20	(1)
General Design Guidelines	21	(1)
Modeling Object-Oriented Designs Using UML	21	(4)
Advantages of an Object-Oriented Approach	25	(1)
1.3 A Summary of Key Issues in Programming	26	(20)
Modularity	27	(1)
Modifiability	28	(2)
Ease of Use	30	(1)
Fail-Safe Programming	31	(6)
Style	37	(7)
Debugging	44	(2)
Summary	46	(1)
Cautions	47	(1)
Self-Test Exercises	48	(1)
Exercises	48	(2)
Programming Problems	50	(3)
CHAPTER 2 Recursion: The Mirrors	53	(60)
2.1 Recursive Solutions	54	(21)
A Recursive Valued Function: The Factorial of n	57	(6)
A Recursive void Function: Writing a String Backward	63	(12)
2.2 Counting Things	75	(8)
Multiplying Rabbits (The Fibonacci Sequence)	75	(3)
Organizing a Parade	78	(2)
Mr. Spock's Dilemma (Choosing k Out of n Things)	80	(3)
2.3 Searching an Array	83	(9)
Finding the Largest Item in an Array	83	(1)
Binary Search	84	(4)
Finding the k th Smallest Item of an Array	88	(4)
2.4 Organizing Data	92	(5)
The Towers of Hanoi	92	(5)
2.5 Recursion and Efficiency	97	(5)
Summary	102	(1)
Cautions	103	(1)
Self-Test Exercises	104	(1)
Exercises	104	(8)
Programming Problems	112	(1)
CHAPTER 3 Data Abstraction: The Walls	113	(51)
3.1 Abstract Data Types	114	(5)
3.2 Specifying ADTs	119	(14)
The ADT List	119	(5)
The ADT Sorted List	124	(2)
Designing an ADT	126	(5)
Axioms (Optional)	131	(2)
3.3 Implementing ADTs	133	(23)
C++ Classes	135	(9)
C++ Namespaces	144	(2)
An Array-Based Implementation of the ADT List	146	(6)
C++ Exceptions	152	(2)
An Implementation of the ADT List Using Exceptions	154	(2)
Summary	156	(1)
Cautions	157	(1)
Self-Test Exercises	158	(1)
Exercises	159	(3)
Programming Problems	162	(2)
CHAPTER 4 Linked Lists	164	(78)
4.1 Preliminaries	165	(12)
Pointers	166	(6)
Dynamic Allocation of Arrays	172	(3)
Pointer-Based Linked Lists	175	(2)
4.2 Programming with Linked Lists	177	(32)
Displaying the Contents of a Linked List	178	(1)
Deleting a Specified Node from a Linked List	179	(3)
Inserting a Node into a Specified Position of a Linked List	182	(6)
A Pointer-Based Implementation of the ADT List	188	(8)
Comparing Array-Based and Pointer-Based Implementations	196	(2)
Saving and Restoring a Linked List by Using a File	198	(4)
Passing a Linked List to a Function	202	(1)
Processing Linked Lists Recursively	203	(5)
Objects as Linked List Data	208	(1)
4.3 Variations of the Linked List	209	(6)
Circular Linked Lists	209	(2)
Dummy Head Nodes	211	(1)
Doubly Linked Lists	211	(4)
4.4 Application: Maintaining an Inventory	215	(6)
4.5 The C++ Standard Template Library	221	(7)
Containers	221	(1)
Iterators	222	(2)
The Standard Template Library Class list	224	(4)
Summary	228	(2)
Cautions	230	(2)
Self-Test Exercises	232	(3)
Exercises	235	(3)
Programming Problems	238	(4)
CHAPTER 5 Recursion as a Problem-Solving Technique	242	(37)
5.1 Backtracking	243	(7)
The Eight Queens Problem	243	(2)
Implementing Eight Queens Using the STL Class vector	245	(5)
5.2 Defining Languages	250	(15)
The Basics of Grammars	251	(1)
Two Simple Languages	252	(3)
Algebraic Expressions	255	(10)
5.3 The Relationship Between Recursion and Mathematical Induction	265	(3)
The Correctness of the Recursive Factorial Function	265	(1)
The Cost of Towers of Hanoi	266	(2)
Summary	268	(1)
Cautions	269	(1)
Self-Test Exercises	269	(1)
Exercises	269	(4)
Programming Problems	273	(6)
PART II Problem Solving with Abstract Data Types	279	(534)
CHAPTER 6 Stacks	280	(58)
6.1 The Abstract Data Type Stack	281	(6)
Developing an ADT During the Design of a Solution	281	(6)
6.2 Simple Applications of the ADT Stack	287	(4)
Checking for Balanced Braces	287	(3)
Recognizing Strings in a Language	290	(1)
6.3 Implementations of the ADT Stack	291	(14)
An Array-Based Implementation of the ADT Stack	292	(4)
A Pointer-Based Implementation of the ADT Stack	296	(3)
An Implementation That Uses the ADT List	299	(4)
Comparing Implementations	303	(1)
The STL Class stack	303	(2)
6.4 Application: Algebraic Expressions	305	(6)
Evaluating Postfix Expressions	306	(1)
Converting Infix Expressions to Equivalent Postfix Expressions	307	(4)
6.5 Application: A Search Problem	311	(12)
A Nonrecursive Solution That Uses a Stack	312	(8)
A Recursive Solution	320	(3)
6.6 The Relationship Between Stacks and Recursion	323	(2)
Summary	325	(1)
Cautions	326	(1)
Self-Test Exercises	326	(1)
Exercises	327	(4)
Programming Problems	331	(7)
CHAPTER 7 Queues	338	(46)
7.1 The Abstract Data Type Queue	339	(2)
7.2 Simple Applications of the ADT Queue	341	(3)
Reading a String of Characters	342	(1)
Recognizing Palindromes	343	(1)
7.3 Implementations of the ADT Queue	344	(19)
A Pointer-Based Implementation	344	(6)
An Array-Based Implementation	350	(6)
An Implementation That Uses the ADT List	356	(3)
The STL Class queue	359	(3)
Comparing Implementations	362	(1)
7.4 A Summary of Position-Oriented ADTs	363	(1)
7.5 Application: Simulation	364	(10)
Summary	374	(1)
Cautions	375	(1)
Self-Test Exercises	375	(1)
Exercises	376	(4)
Programming Problems	380	(4)
CHAPTER 8 Advanced C++ Topics	384	(59)
8.1 Inheritance Revisited	385	(11)
Public, Private, and Protected Inheritance	391	(2)
Is-a , Has-a , and As-a Relationships	393	(3)
8.2 Virtual Functions and Late Binding	396	(10)
Abstract Base Classes	401	(5)
8.3 Friends	406	(2)
8.4 The ADTs List and Sorted List Revisited	408	(8)
Implementations of the ADT Sorted List That Use the ADT List	411	(5)
8.5 Class Templates	416	(6)
8.6 Overloaded Operators	422	(5)
8.7 Iterators	427	(6)
Implementing the ADT List Using Iterators	429	(4)
Summary	433	(1)
Cautions	434	(1)
Self-Test Exercises	435	(1)
Exercises	436	(4)
Programming Problems	440	(3)
CHAPTER 9 Algorithm Efficiency and Sorting	443	(56)
9.1 Measuring the Efficiency of Algorithms	444	(12)
The Execution Time of Algorithms	445	(2)
Algorithm Growth Rates	447	(1)
Order-of-Magnitude Analysis and Big O Notation	448	(5)
Keeping Your Perspective	453	(2)
The Efficiency of Searching Algorithms	455	(1)
9.2 Sorting Algorithms and Their Efficiency	456	(34)
Selection Sort	457	(4)
Bubble Sort	461	(2)
Insertion Sort	463	(2)
Mergesort	465	(6)
Quicksort	471	(11)
Radix Sort	482	(3)
A Comparison of Sorting Algorithms	485	(1)
The STL Sorting Algorithms	485	(5)
Summary	490	(1)
Cautions	491	(1)
Self-Test Exercises	492	(1)
Exercises	493	(3)
Programming Problems	496	(3)
CHAPTER 10 Trees	499	(90)
10.1 Terminology	501	(6)
10.2 The ADT Binary Tree	507	(28)
Traversals of a Binary Tree	512	(4)
Possible Representations of a Binary Tree	516	(4)
A Pointer-Based Implementation of the ADT Binary Tree	520	(15)
10.3 The ADT Binary Search Tree	535	(40)
Algorithms for the ADT Binary Search Tree Operations	540	(15)
A Pointer-Based Implementation of the ADT Binary Search Tree	555	(8)
The Efficiency of Binary Search Tree Operations	563	(5)
Treesort	568	(1)
Saving a Binary Search Tree in a File	568	(3)
The STL Search Algorithms	571	(4)
10.4 General Trees	575	(1)
Summary	576	(1)
Cautions	577	(1)
Self-Test Exercises	577	(2)
Exercises	579	(7)
Programming Problems	586	(3)
CHAPTER 11 Tables and Priority Queues	589	(64)
11.1 The ADT Table	590	(21)
Selecting an Implementation	596	(8)
A Sorted Array-Based Implementation of the ADT Table	604	(4)
A Binary Search Tree Implementation of the ADT Table	608	(3)
11.2 The ADT Priority Queue: A Variation of the ADT Table	611	(20)
Heaps	615	(10)
A Heap Implementation of the ADT Priority Queue	625	(3)
Heapsort	628	(3)
11.3 Tables and Priority Queues in the Standard Template Library	631	(13)
The STL Associative Containers	631	(9)
The STL priority_queue Class and Heap Algorithms	640	(4)
Summary	644	(1)
Cautions	645	(1)
Self-Test Exercises	645	(1)
Exercises	646	(4)
Programming Problems	650	(3)
CHAPTER 12 Advanced Implementations of Tables	653	(74)
12.1 Balanced Search Trees	654	(37)
2-3 Trees	655	(20)
2-3-4 Trees	675	(7)
Red-Black Trees	682	(3)
AVL Trees	685	(6)
12.2 Hashing	691	(23)
Hash Functions	695	(2)
Resolving Collisions	697	(9)
The Efficiency of Hashing	706	(3)
What Constitutes a Good Hash Function?	709	(2)
Table Traversal: An Inefficient Operation Under Hashing	711	(1)
Implementing a HashMap Class Using the STL	712	(2)
12.3 Data with Multiple Organizations	714	(5)
Summary	719	(2)
Cautions	721	(1)
Self-Test Exercises	721	(1)
Exercises	722	(3)
Programming Problems	725	(2)
CHAPTER 13 Graphs	727	(44)
13.1 Terminology	728	(3)
13.2 Graphs as ADTs	731	(7)
Implementing Graphs	732	(3)
Implementing a Graph Class Using the STL	735	(3)
13.3 Graph Traversals	738	(7)
Depth-First Search	739	(3)
Breadth-First Search	742	(1)
Implementing a BFS Class Using the STL	743	(2)
13.4 Applications of Graphs	745	(19)
Topological Sorting	746	(3)
Spanning Trees	749	(4)
Minimum Spanning Trees	753	(2)
Shortest Paths	755	(5)
Circuits	760	(3)
Some Difficult Problems	763	(1)
Summary	764	(1)
Cautions	765	(1)
Self-Test Exercises	765	(1)
Exercises	766	(4)
Programming Problems	770	(1)
CHAPTER 14 External Methods	771	(42)
14.1 A Look at External Storage	772	(3)
14.2 Sorting Data in an External File	775	(8)
14.3 External Tables	783	(24)
Indexing an External File	785	(5)
External Hashing	790	(3)
B-Trees	793	(11)
Traversals	804	(1)
Multiple Indexing	805	(2)
Summary	807	(1)
Cautions	807	(1)
Self-Test Exercises	808	(1)
Exercises	808	(4)
Programming Problems	812	(1)
APPENDIX A Review of C++ Fundamentals	813	(76)
A.1 Language Basics	814	(10)
Comments	814	(1)
Identifiers and Keywords	815	(1)
Fundamental Data Types	815	(1)
Variables	816	(1)
Literal Constants	817	(1)
Named Constants	818	(1)
Enumerations	818	(1)
The typedef Statement	819	(1)
Assignments and Expressions	820	(4)
A.2 Input and Output Using iostream	824	(4)
Input	824	(2)
Output	826	(1)
Manipulators	827	(1)
A.3 Functions	828	(4)
Standard Functions	831	(1)
A.4 Selection Statements	832	(2)
The if Statement	832	(1)
The switch Statement	833	(1)
A.5 Iteration Statements	834	(4)
The while Statement	835	(1)
The for Statement	836	(2)
The do Statement	838	(1)
A.6 Arrays	838	(6)
One-Dimensional Arrays	839	(2)
Multidimensional Arrays	841	(2)
Arrays of Arrays	843	(1)
A.7 Strings	844	(6)
C++ Strings	845	(2)
C Strings	847	(3)
A.8 Structures	850	(3)
Structures Within Structures	852	(1)
Arrays of Structures	852	(1)
A.9 C++ Exceptions	853	(7)
Catching Exceptions	853	(5)
Throwing Exceptions	858	(2)
A.10 File Input and Output	860	(14)
Text Files	862	(11)
Binary Files	873	(1)
A.11 Libraries	874	(2)
Avoiding Duplicate Header Files	876	(1)
A.12 A Comparison to Java	876	(3)
Summary	879	(4)
Cautions	883	(1)
Self-Test Exercises	884	(2)
Exercises	886	(2)
Programming Problems	888	(1)
APPENDIX B ASCII Character Codes	889	(1)
APPENDIX C C++ Header Files and Standard Functions	890	(7)
APPENDIX D Mathematical Induction	897	(6)
APPENDIX E Standard Template Library	903	(12)
Glossary	915	(19)
Answers to Self-Test Exercises	934	(20)
Index	954