C++ Plus Data Structures

by Dale, Nell B.; Teague, David

• ISBN13: 9780763714703
• ISBN10: 0763714704
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Jones & Bartlett Learning

Summary

Updated and reorganized, C++ Plus Data Structures, Fourth Edition explores the specifications, applications, and implementations of abstract data types with unmatched accessibility. Written by renowned author and educator Nell Dale, this text provides intuitive explanations that clarify abstract concepts, and approaches the study of data structures with emphasis on computer science theory and software engineering principles. Topics such as modularization, data encapsulation, information hiding, object-oriented decomposition, algorithm analysis, life-cycle software verification models, and data abstraction are carefully presented to foster good software engineering techniques in students from the beginning of their careers. In addition to the meaningful exercises and case studies that define Nell Dalea (TM)s teaching philosophy, this fourth edition provides an increased emphasis on object-oriented design and an early introduction of object-oriented concepts.

Table of Contents

Preface	v
Software Engineering Principles	1	(50)
Software Design Process	2	(12)
Verification of Software Correctness	14	(37)
Summary	46	(2)
Exercises	48	(3)
Data Design and Implementation	51	(52)
Different Views of Data	52	(7)
Abstraction and Built-in Types	59	(13)
Higher-Level Abstraction and the C++ Class Type	72	(7)
C++ Constructs for Program Verification	79	(24)
Case Study: User-Defined String I/O Class	84	(12)
Summary	96	(1)
Exercises	97	(6)
ADTs Unsorted List and Sorted List	103	(72)
Lists	104	(1)
Abstract Data Type Unsorted List	105	(20)
Abstract Data Type Sorted List	125	(11)
Comparison of Algorithms	136	(8)
Comparison of Unsorted and Sorted List ADT Algorithms	144	(3)
Class Constructors, Class Destructors, and Overloading Operators	147	(28)
Case Study: Real Estate Listings, and Object-Oriented Design	154	(15)
Summary	169	(1)
Exercises	170	(5)
ADTs Stack and Queue	175	(90)
Stacks	176	(17)
More about Generics: C++ Templates	193	(4)
Pointer Types	197	(9)
Dynamically Allocated Arrays	206	(13)
Case Study: Postfix Expression Evaluation	209	(10)
Queues	219	(46)
Case Study: Simulation	234	(15)
Summary	249	(1)
Exercises	250	(15)
Linked Structures	265	(56)
Implementing a Stack as a Linked Structure	266	(18)
Implementing a Queue as a Linked Structure	284	(10)
Implementing the Unsorted List as a Linked Structure	294	(11)
Implementing the Sorted List as a Linked Structure	305	(16)
Summary	315	(1)
Exercises	315	(6)
Lists Plus	321	(70)
Circular Linked Lists	322	(10)
Doubly Linked Lists	332	(4)
Linked Lists with Headers and Trailers	336	(1)
Copy Structures	337	(9)
A Specialized List ADT	346	(5)
A Linked List as an Array of Records	351	(10)
Object-Oriented Design: Composition and Inheritance	361	(30)
Case Study: Implementing a Large Integer ADT	371	(12)
Summary	383	(1)
Exercises	384	(7)
Programming with Recursion	391	(54)
What Is Recursion?	392	(1)
The Classic Example of Recursion	392	(3)
Programming Recursively	395	(3)
Verifying Recursive Functions	398	(1)
Writing Recursive Functions	399	(3)
Using Recursion to Simplify Solutions	402	(2)
Recursive Linked-List Processing	404	(3)
A Recursive Version of Binary Search	407	(2)
Recursive Versions of InsertItem and DeleteItem	409	(2)
How Recursion Works	411	(9)
Tracing the Execution of Recursive Function Insert	420	(2)
Debugging Recursive Routines	422	(1)
Removing Recursion	423	(3)
Deciding Whether to Use a Recursive Solution	426	(19)
Case Study: Quick Sort	429	(7)
Summary	436	(1)
Exercises	437	(8)
Binary Search Trees	445	(62)
The Logical Level	446	(4)
Binary Search Tree ADT	450	(2)
Application Level	452	(1)
Implementation Level	452	(2)
Recursive Binary Search Tree Operations	454	(31)
Iterative Insertion and Deletion	485	(8)
Comparing Binary Search Trees to Linear Lists	493	(14)
Case Study: Building an Index	495	(5)
Summary	500	(1)
Exercises	500	(7)
Trees Plus	507	(66)
Binary Expression Trees	508	(11)
A Nonlinked Representation of Binary Trees	519	(3)
Heaps	522	(10)
ADT Priority Queue	532	(5)
Graphs	537	(36)
Summary	561	(1)
Exercises	561	(12)
Sorting and Searching Algorithms	573	(64)
Sorting	574	(30)
Searching	604	(18)
Radix Sort	622	(15)
Summary	627	(1)
Exercises	628	(9)
Programming Assignments	637	(42)
Answers to Selected Exercises	679	(46)
Appendix A Reserved Words	725	(1)
Appendix B Operator Precedents	725	(2)
Appendix C A Selection of Standard Library Routines	727	(9)
Appendix D Character Sets	736	(2)
Appendix E The Standard Template Library	738	(45)
Glossary	783	(10)
Index	793