C++ Plus Data Structures, Third Edition

by Nell Dale ISBN:0763704814
Jones and Bartlett Publishers © 2003 (816 pages)
This book focuses on abstract data types as viewed from three different perspectives: their specification, their application, and their implementation.





Table of Contents
C++ Plus Data Structures, Third Edition
Preface
Chapter 1 - Software Engineering Principles
Chapter 2 - Data Design and Implementation
Chapter 3 - ADTs Unsorted List and Sorted List
Chapter 4 - ADTs Stack and Queue
Chapter 5 - Linked Structures
Chapter 6 - Lists Plus
Chapter 7 - Programming with Recursion
Chapter 8 - Binary Search Trees
Chapter 9 - Priority Queues, Heaps, Graphs, and Sets
Chapter 10 - Sorting and Searching Algorithms
Answers to Selected Exercises
Appendix A - Reserved Words
Appendix B - Operator Precedence
Appendix C - A Selection of Standard Library Routines
Appendix D - Character Sets
Appendix E - The Standard Template Library
Glossary
Index


Content and Organization
Chapter 1 outlines the basic goals of high-quality software, and the basic principles of software engineering for designing and implementing programs to meet these goals. Abstraction, functional decomposition, and object-oriented design are discussed. This chapter also addresses what we see as a critical need in software education: the ability to design and implement correct programs and to verify that they are actually correct. Topics covered include the concept of "life-cycle" verification; designing for correctness using preconditions and postconditions; the use of deskchecking and design/code walkthroughs and inspections to identify errors before testing; debugging techniques, data coverage (black-box), and code coverage (clear- or white-box) approaches; test plans, unit testing, and structured integration testing using stubs and drivers. The concept of a generalized test driver is presented and executed in a Case Study that develops the ADT Fraction.

Chapter 2 presents data abstraction and encapsulation, the software engineering concepts that relate to the design of the data structures used in programs. Three perspectives of data are discussed: abstraction, implementation, and application. These perspectives are illustrated using a real-world example, and then are applied to built-in data structures that C++ supports: structs and arrays. The C++ class type is presented as the way to represent the abstract data types we examine in subsequent chapters. The principles of object-oriented programming-encapsulation, inheritance, and polymorphism-are introduced here along with the accompanying C++ implementation constructs. The Case Study at the end of this chapter reinforces the ideas of data abstraction and encapsulation in designing and implementing a user-defined data type for generalized string input and output. This class is tested using a version of the generalized test driver.

Chapter 2 ends with a discussion of two C++ constructs that help users write better software: namespace and exception handling using the try/catch statement. Various approaches to error handling are demonstrated in subsequent chapters.

We would like to think that the material in Chapters 1 and 2 is a review for most students. The concepts in these two chapters, however, are so crucial to the future of any and all students that we feel that we cannot rely on the assumption that they have seen the material before.

Chapter 3 introduces the most fundamental abstract data type of all: the list. The chapter begins with a general discussion of operations on abstract data types and then presents the framework with which all of the other data types are examined: a presentation and discussion of the specification, a brief application using the operations, and the design and coding of the operations. Both the unsorted and the sorted lists are presented with an array-based implementation. Overloading the relational operators is presented as a way to make the implementations more generic. The binary search is introduced as a way to improve the performance of the search operation in the sorted list. Because there is more than one way to solve a problem, we discuss how competing solutions can be compared through the analysis of algorithms, using Big-O notation. This notation is then used to compare the operations in the unsorted list and the sorted list. The four-phase object-oriented methodology is presented and demonstrated in the Case Study by using a simple real estate database.

Chapter 4 introduces the stack and the queue data types. Each data type is first considered from its abstract perspective, and the idea of recording the logical abstraction in an ADT specification is stressed. Then the set of operations is implemented in C++ using an array-based implementation. The concept of dynamic allocation is introduced, along with the syntax for using C++ pointer variables, and then used to demonstrate how arrays can be dynamically allocated to give the user more flexibility. With the introduction of dynamic storage, the destructor must be introduced. Templates are introduced as a way of implementing generic classes. A Case Study using stacks (postfix expression evaluator) and one using queues (simulation) are presented.

Chapter 5 reimplements the ADTs from Chapters 3 and 4 as linked structures. The technique used to link the elements in dynamically allocated storage is described in detail and illustrated with figures. The array-based implementations and the linked implementations are then compared using Big-O notation.

Chapter 6 is a collection of advanced concepts and techniques. Circular linked lists and doubly linked lists are discussed. The insertion, deletion, and list traversal algorithms are developed and implemented for each variation. An alternative representation of a linked structure, using static allocation (an array of structs), is designed. Class copy constructors, assignment overloading, and dynamic binding are covered in detail. The Case Study uses doubly linked lists to implement large integers.

Chapter 7 discusses recursion, giving the student an intuitive understanding of the concept, and then shows how recursion can be used to solve programming problems. Guidelines for writing recursive functions are illustrated with many examples. After demonstrating that a by-hand simulation of a recursive routine can be very tedious, a simple three-question technique is introduced for verifying the correctness of recursive functions. Because many students are wary of recursion, the introduction to this material is deliberately intuitive and nonmathematical. A more detailed discussion of how recursion works leads to an understanding of how recursion can be replaced with iteration and stacks. The Case Study develops and implements the Quick-Sort algorithm.

Chapter 8 introduces binary search trees as a way to arrange data, giving the flexibility of a linked structure with O(log2N) insertion and deletion time. In order to build on the previous chapter and exploit the inherent recursive nature of binary trees, the algorithms first are presented recursively. After all the operations have been implemented recursively, we code the insertion and deletion operations iteratively to show the flexibility of binary search trees. A nonlinked array-based binary tree implementation is described. The Case Study discusses the process of building an index for a manuscript and implements the first phase.

Chapter 9 presents a collection of other branching structures: priority queues (implemented with both lists and heaps), graphs, and sets. The graph algorithms make use of stacks, queues, and priority queues, thus both reinforcing earlier material and demonstrating how general these structures are. Two set implementations are discussed: the bit-vector representation, in which each item in the base set is assigned a present/absent flag and the operations are the built-in logic operations, and a list-based representation, in which each item in a set is represented in a list of set items. If the item is not in the list, it is not in the set.

Chapter 10 presents a number of sorting and searching algorithms and asks the question: Which are better? The sorting algorithms that are illustrated, implemented, and compared include straight selection sort, two versions of bubble sort, quick sort, heap sort, and merge sort. The sorting algorithms are compared using Big-O notation. The discussion of algorithm analysis continues in the context of searching. Previously presented searching algorithms are reviewed and new ones are described. Hashing techniques are discussed in some detail. Finally, radix sort is presented and analyzed.


Another C++ Books
Another Core of CS Books
Another Programming Language Books
Download CHM and or Download PDF