C++ Plus Data Structures

by DALE

• ISBN13: 9780763706210
• ISBN10: 0763706213
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-01-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

Software Engineering Principles	1	(54)
Software Design Process	2	(14)
Hardware	3	(1)
Software	3	(1)
Ideaware	4	(1)
Goals of Quality Software	4	(3)
Specification: Understanding the Problem	7	(1)
Writing Detailed Specifications	8	(2)
Program Design	10	(1)
Abstraction	10	(1)
Information Hiding	11	(1)
Functional Decomposition	12	(2)
Object-Oriented Design	14	(2)
Verification of Software Correctness	16	(34)
Origin of Bugs	17	(1)
Specifications and Design Errors	18	(3)
Compile-Time Errors	21	(1)
Run-Time Errors	22	(5)
Designing for Correctness	27	(1)
Assertions	28	(1)
Preconditions and Postconditions	28	(2)
Design Review Activities	30	(2)
Program Testing	32	(1)
Data Coverage	33	(2)
Code Coverage	35	(3)
Test Plans	38	(4)
Planning for Debugging	42	(2)
Integration Testing	44	(6)
Practical Considerations	50	(1)
Summary	50	(2)
Exercises	52	(3)
Data Design and Implementation	55	(52)
Different Views of Data	56	(9)
What Do We Mean by Data?	56	(1)
Data Abstraction	56	(3)
Data Structures	59	(5)
Abstract Data Type Operator Categories	64	(1)
Abstraction and Built-in Types	65	(14)
Records	66	(1)
Logical Level	66	(1)
Application Level	67	(1)
Implementation Level	67	(4)
One-Dimensional Arrays	71	(1)
Logical level	71	(3)
Application Level	74	(1)
Implementation Level	74	(3)
Two-Dimensional Arrays	77	(1)
Logical Level	77	(2)
Application Level	79	(1)
Implementation Level	79	(1)
Higher Level Abstraction and the C++ Class Type	79	(9)
Class Specification	80	(2)
Class Implementation	82	(2)
Member Functions with Object Parameters	84	(1)
Difference Between Classes and Structs	85	(1)
Object-Oriented Programming	86	(2)
Case Study: User-Defined String I/O Class	88	(13)
Summary	101	(2)
Exercises	103	(4)
ADTs Unsorted List and Sorted List	107	(70)
Lists	108	(1)
Abstract Data Type Unsorted List	109	(20)
Logical Level	109	(1)
Abstract Data Type Operations	109	(2)
Generic Data Types	111	(3)
Application Level	114	(2)
Implementation Level	116	(1)
List Design Terminology	116	(1)
Member Functions	117	(8)
Notes on the Array-Based List Implementation	125	(1)
Test Plan	126	(3)
Abstract Data Type Sorted List	129	(11)
Logical Level	129	(1)
Application Level	130	(1)
Implementation Level	130	(1)
InsertItem Operation	130	(2)
DeleteItem Operation	132	(1)
Improving the RetrieveItem Operation	133	(1)
Binary Search Algorithm	134	(5)
Test Plan	139	(1)
Comparison of Algorithms	140	(8)
Big-O	142	(2)
Common Orders of Magnitude	144	(4)
Comparison of Unsorted and Sorted List ADT Algorithms	148	(3)
Unsorted List ADT	148	(1)
Sorted List ADT	149	(2)
Class Constructors, Destructors, and Overloading Operators	151	(6)
Class Constructor	151	(4)
Class Destructor	155	(1)
Overloading an Operator	155	(2)
Case Study: Real Estate Listings, an Object-Oriented Design	157	(15)
Summary	172	(2)
Exercises	174	(3)
ADTs Stack and Queue	177	(88)
Stacks	177	(14)
Logical Level	177	(2)
Operations on Stacks	179	(2)
Application Level	181	(6)
Implementation Level	187	(1)
Definition of Stack Class	187	(1)
Definitions of Stack Operations	188	(2)
Test Plan	190	(1)
More about Generics: C++ Templates	191	(5)
Pointer Types	196	(8)
Logical Level	196	(7)
Application Level	203	(1)
Implementation Level	204	(1)
Dynamically Allocated Arrays	204	(4)
Case Study: Postfix Expression Evaluation	208	(10)
Queues	218	(16)
Logical Level	218	(2)
Operations on Queues	220	(1)
Application Level	221	(4)
Implementation Level	225	(1)
Definition of Queue Class	225	(1)
Implementations of Queue Operations	226	(2)
Another Queue Design	228	(5)
Test Plan	233	(1)
Comparing Array Implementations	234	(1)
Case Study: Simulation	234	(17)
Summary	251	(1)
Exercises	252	(13)
Linked Structures	265	(56)
Implementing a Stack as a Linked Structure	266	(18)
Function Push	266	(9)
Function Pop	275	(5)
Other Stack Functions	280	(2)
Comparing Stack Implementations	282	(2)
Implementing a Queue as a Linked Structure	284	(10)
Function Enqueue	284	(2)
Function Dequeue	286	(4)
A Circular Linked Queue Design	290	(1)
Comparing Queue Implementations	291	(3)
Implementing the Unsorted List as a Linked Structure	294	(11)
Function MakeEmpty	298	(1)
Function RetrieveItem	299	(2)
Function InsertItem	301	(1)
Function DeleteItem	301	(2)
Functions ResetList and GetNextItem	303	(1)
Comparing Unsorted List Implementations	304	(1)
Implementing the Sorted List as a Linked Structure	305	(10)
Function RetrieveItem	306	(1)
Function InsertItem	307	(6)
Function DeleteItem	313	(1)
Comparing Sorted List Implementations	314	(1)
Summary	315	(1)
Exercises	316	(5)
Lists Plus	321	(72)
Circular Linked Lists	322	(10)
Finding a List Item	324	(3)
Inserting into a Circular List	327	(3)
Deleting from a Circular List	330	(2)
Doubly Linked Lists	332	(5)
Finding an Item in a Doubly Linked List	334	(1)
Operations on a Doubly Linked List	334	(3)
Linked Lists with Headers and Trailers	337	(1)
Copy Structures	338	(10)
Shallow vs. Deep Copies	340	(1)
Class Copy Constructors	340	(4)
Copy Function	344	(1)
Overloading the Assignment Operator	345	(3)
A Specialized List ADT	348	(4)
A Linked List as an Array of Records	352	(9)
Why Use an Array?	353	(2)
How Is an Array Used?	355	(6)
Object-Oriented Design: Composition and Inheritance	361	(11)
Deriving One Class from Another	363	(1)
Implementation of the Derived Class	364	(2)
Application of the CountedQue Class	366	(1)
Inheritance and Accessibility	367	(1)
Virtual Functions	367	(5)
Case Study: Implementing a Large Integer ADT	372	(14)
Summary	386	(1)
Exercises	387	(6)
Programming with Recursion	393	(58)
What Is Recursion?	394	(1)
The Classic Example of Recursion	394	(3)
Programming Recursively	397	(3)
Coding the Factorial Function	398	(2)
Verifying Recursive Functions	400	(1)
The Three-Question Method	400	(1)
Writing Recursive Functions	401	(4)
Writing a Boolean Function	402	(3)
Using Recursion to Simplify Solutions	405	(2)
Recursive Linked List Processing	407	(3)
A Recursive Version of Binary Search	410	(1)
Recursive Versions of InsertItem and DeleteItem	411	(3)
The InsertItem Operation	411	(2)
The DeleteItem Operation	413	(1)
How Recursion Works	414	(10)
Static Storage Allocation	414	(3)
Dynamic Storage Allocation	417	(7)
Tracing the Execution of Recursive Function Insert	424	(2)
Debugging Recursive Routines	426	(1)
Removing Recursion	427	(4)
Iteration	427	(2)
Stacking	429	(2)
Deciding Whether to Use a Recursive Solution	431	(3)
Case Study: Quick Sort	434	(7)
Summary	441	(1)
Exercises	442	(9)
Binary Search Tree	451	(66)
The Logical Level	452	(5)
Binary Search Tree ADT	457	(2)
Application Level	459	(1)
Implementation Level	459	(1)
Recursive Binary Search Tree Operations	460	(34)
Function NumberOfNodes	461	(3)
Function RetrieveItem	464	(3)
Function InsertItem	467	(4)
Insertion Order and Tree Shape	471	(1)
Function DeleteItem	472	(6)
Function PrintTree	478	(4)
Class Constructor and Destructor	482	(1)
Copying a Tree	483	(7)
More about Traversals	490	(1)
ResetTree and GetNextItem	491	(3)
Iterative Insertion and Deletion	494	(9)
Searching a Binary Search Tree	494	(3)
Function InsertItem	497	(3)
Function DeleteItem	500	(1)
Recursion or Iteration?	501	(2)
Comparing Binary Search Trees to Linear Lists	503	(2)
Big-O Comparisons	503	(2)
Case Study: Building an Index	505	(4)
Summary	509	(1)
Exercises	510	(7)
Trees Plus	517	(68)
Binary Expression Trees	518	(12)
Expression Evaluation	519	(3)
Printing a Binary Expression Tree	522	(1)
Building a Binary Expression Tree	522	(8)
A Nonlinked Representation of Binary Trees	530	(3)
Heaps	533	(10)
Heap Implementation	538	(5)
Application level	543	(1)
ADT Priority Queue	543	(6)
Logical Level	543	(2)
Implementation Level	545	(2)
Heaps vs. Other Representations of Priority Queues	547	(2)
Graphs	549	(25)
Logical Level	549	(6)
Application Level	555
Depth-First Searching	553	(6)
Breadth-First Searching	559	(3)
The Single-Source Shortest-Paths Problem	562	(4)
Implementation Level	566	(1)
Array-Based Implementation	566	(5)
Linked Implementation	571	(3)
Summary	574	(1)
Exercises	575	(10)
Sorting and Searching Algorithms	585	(66)
Sorting	586	(31)
Straight Selection Sort	587	(3)
Analyzing Selection Sort	590	(2)
Bubble Sort	592	(2)
Analyzing Bubble Sort	594	(2)
Insertion Sort	596	(2)
Analyzing Insertion Sort	598	(1)
O(N log2 N) Sorts	599	(1)
Merge Sort	599	(2)
Merging the Sorted Halves	601	(3)
The MergeSort Function	604	(1)
Analyzing MergeSort	605	(1)
QuickSort	606	(1)
Heap Sort	607	(1)
Building a Heap	607	(3)
Sorting Using the Heap	610	(1)
Analyzing Heap Sort	611	(2)
Other Efficiency Considerations	613	(1)
When N Is Small	613	(1)
Eliminating Calls to Functions	613	(1)
Programmer Time	614	(1)
Space Considerations	614	(1)
More About Sorting in General	614	(1)
Keys	614	(4)
Sorting with Pointers	618
Searching	617	(21)
Linear Searching	617	(1)
High-Probability Ordering	618	(1)
Key Ordering	619	(1)
Binary Searching	620	(1)
Hashing	620	(3)
Collisions	623	(1)
Linear Probing	624	(4)
Clustering	628	(1)
Rehashing	628	(2)
Buckets and Chaining	630	(2)
Choosing a Good Hash Function	632	(2)
Division Method	634	(1)
Other Hash Methods	634	(3)
Analyzing Hashing	637	(1)
Radix Sort	638	(5)
Analyzing RadixSort	642	(1)
Summary	643	(1)
Exercises	644	(7)
Appendixes	651	(6)
Appendix A Reserved Words	651	(1)
Appendix B Operator Precedence	651	(1)
Appendix C Description of Selected Operators	652	(1)
Appendix D C++ Library Routines and Constants	653	(2)
Appendix E The Character Sets	655	(2)
Answers to Selected Exercises	657	(50)
Chapter 1	657	(1)
Chapter 2	658	(4)
Chapter 3	662	(5)
Chapter 4	667	(9)
Chapter 5	676	(3)
Chapter 6	679	(3)
Chapter 7	682	(4)
Chapter 8	686	(9)
Chapter 9	695	(7)
Chapter 10	702	(5)
Programming Assignments	707	(40)
Chapter 1	707	(4)
Chapter 2	711	(3)
Chapter 3	714	(5)
Chapter 4	719	(7)
Chapter 5	726	(2)
Chapter 6	728	(7)
Chapter 7	735	(3)
Chapter 8	738	(5)
Chapter 9	743	(2)
Chapter 10	745	(2)
Glossary	747	(18)
Index	765