C++ Plus Data Structures

by Dale, Nell B.

• ISBN13: 9780763704810
• ISBN10: 0763704814
• Edition: 3rd
• Format: Hardcover
• Copyright: 2003-01-01
• Publisher: Jones & Bartlett

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	(62)
The Software Process	2	(7)
Program Design	9	(10)
Verification of Software Correctness	19	(44)
Case Study: Fraction Class	50	(8)
Summary	58	(2)
Exercises	60	(3)
Data Design and Implementation	63	(60)
Different Views of Data	64	(8)
Abstraction and Built in Types	72	(13)
Higher Level Abstraction and the C++ Class Type	85	(6)
Object Oriented Programming	91	(4)
Construct for Program Verification	95	(28)
Case Study: User Defined String 1/0 Class	100	(16)
Summary	116	(1)
Exercises	117	(6)
ADTs Unsorted List and Sorted List	123	(72)
Lists	124	(1)
Abstract Data Type Unsorted List	125	(21)
Abstract Data Type Sorted List	146	(11)
Comparison of Algorithms	157	(7)
Comparison of Unsorted and Sorted List ADT Algorithms	164	(3)
Overloading Operators	167	(3)
Object-Oriented Design Methodology	170	(25)
Case Study: Real Estate Listing: An Object-Oriented Design	173	(15)
Summary	188	(1)
Exercises	189	(6)
ADTs Stack and Queue	195	(84)
Stacks	196	(14)
More about Generics: C++ Templates	210	(4)
Pointer Types	214	(8)
Dynamically Allocated Arrays	222	(57)
Case Study: Simulation	245	(16)
Summary	261	(1)
Exercises	262	(17)
Linked Structures	279	(54)
Implementing a Stack as a Linked Structure	280	(16)
Implementing a Queue as a Linked Structure	296	(11)
Implementing the Unsorted List as a Linked Structure	307	(11)
Implementing the Sorted List as a Linked Structure	318	(15)
Summary	327	(1)
Exercises	327	(6)
Lists Plus	333	(66)
Circular Linked Lists	334	(10)
Doubly Linked Lists	344	(4)
Linked Lists with Headers and Trailers	348	(2)
Copy Structures	350	(8)
A Linked List as an Array of Records	358	(10)
Polymorphism with Virtual Functions	368	(5)
A Specialized List ADT	373	(26)
Case Study: Implementing a Large Integer ADT	379	(13)
Summary	392	(1)
Exercises	392	(7)
Programming with Recursion	399	(56)
What is Recursion?	400	(1)
The Classic Example of Recursion	401	(3)
Programming Recursively	404	(3)
Verifying Recursive Functions	407	(1)
Writing Recursive Functions	408	(3)
Using Recursion to Simplify Solutions	411	(1)
Recursive Linked List Processing	412	(4)
A Recursive Version of Binary Search	416	(2)
Recursive Versions of InsertItem and DeleteItem	418	(2)
How Recursion Works	420	(9)
Tracing the Execution of Recursive Function Insert	429	(3)
Debugging Recursive Routines	432	(1)
Removing Recursion	432	(4)
Deciding Whether to Use a Recursive Solution	436	(19)
Case Study: QuickSort	438	(8)
Summary	446	(1)
Exercises	447	(8)
Binary Search Trees	455	(74)
Trees	456	(4)
Logical Level	460	(3)
Application Level	463	(1)
Implementation Level	463	(1)
Recursive Binary Search Tree Operations	464	(32)
Iterative Insertion and Deletion	496	(8)
Comparing Binary Search Trees and Linear Lists	504	(2)
A Nonlinked Representation of Binary Trees	506	(23)
Case Study: Building an Index	510	(7)
Summary	517	(1)
Exercises	517	(12)
Priority Queues, Heaps, Graphs, and Sets	529	(59)
ADT Priority Queue	530	(3)
Heaps	533	(13)
Graphs	546	(25)
Sets	571	(17)
Summary	579	(1)
Exercises	579	(9)
Sorting and Searching Algorithms	588	(65)
Sorting	588	(31)
Searching	619	(3)
Hashing	622	(15)
Radix Sort	637	(16)
Summary	642	(2)
Exercises	644	(9)
Answer to Selected Exercises	653	(60)
Appendix A Reserved Words	713	(1)
Appendix B Operator Precedents	713	(2)
Appendix C A Selection of Standard Library Routines	715	(9)
Appendix D Character Sets	724	(2)
Appendix E The Standard Template Library	726	(45)
Glossary	771	(18)
Index	789