C++ Plus Data Structures, Third Edition

by Nell Dale, Dale

Overview

C++ Plus Data Structures is designed for a course in Data Structures where C++ is the programming language. The book focuses on abstract data types as viewed from three different perspectives: their specification, their application, and their implementation. The authors stress computer science theory and software engineering principles, including modularization, data encapsulation, information hiding, data abstraction, object-oriented decomposition, functional decomposition, the analysis of algorithms, and life-cycle software verification methods. Finally, through classic Dale pedagogy students are offered a clear, easy-to-understand discussion of important theoretical constructs and their implementation in C++.

Product Details

ISBN-13:	9780763704810
Publisher:	Jones & Bartlett Learning
Publication date:	11/13/2003
Series:	Cs2 - C++ Series
Edition description:	Third Edition
Pages:	832
Product dimensions:	8.12(w) x 9.48(h) x 1.41(d)

Table of Contents

Software Design Process

Verification of Software Correctness

Summary

Exercises

2. Data Design and Implementation

Different Views of Data

Abstractions and Built-in Types

Higher Level Abstraction and the C++ Class Type

Summary

Exercises

3. ADTs Unordered List and Sorted List

Abstract Data Type Unsorted List

Abstract Data Type Sorted List

Comparison of Algorithms

Summary

Exercises

4. ADTs Stack and Queue

Stacks

More about Generics: C++ Templates

Pointer Types

Dynamically Allocated Arrays

Queues

Summary

Exercises

5. Linked Structures

Implementing a Stack as a Linked Structure

Implementing a Queue as a Linked Structure

Implementing the Unsorted List as a Linked Structure

Implementing the Sorted List as a Linked Structure

Summary

Exercises

6. Lists Plus

Circular Linked Lists

Doubly Linked Lists

Linked Lists with Headers and Trailers

Copy Structures

A Specialized List ADT

A Linked List as an Array of Records

Object-Oriented Design: Composition and Inheritance

Summary

Exercises

7. Programming with Recursion

What is Recursion?

The Classic Example of Recursion

Programming Recursively

Verifying Recursive Functions

Writing Recursive Functions

Using Recursion to Simplify Solutions

Recursive Linked List Processing

A Recursive Version of Binary Search

Recursive Versions of InsertItem and DeleteItem

How Recursion Works

Tracing the Execution of Recursive Function Insert

Debugging Recursive Routines

Removing Recursion

Deciding Whether to Use a Recursive Solution

Summary

Exercises

8. Binary Search Trees

The Logical Level

Binary Search Tree ADT

Application Level

Implementation Level

Recursive Binary Search Tree Operations

Iterative Insertion and Deletion

Comparing Binary Search Trees to Linear Lists

Summary

Exercises

9. Trees Plus

Binary Expression Trees

A Nonlinked Representation of Binary Trees

Heaps

ADT Priority Queue

Graphs

Summary

Exercises

10. Sorting and Searching Algorithms

Sorting

Searching

Radix Sort

Summary

Exercises

Appendixes

Appendix A. Reserved Words

Appendix B. Operator Precedence

Appendix C. Description of Selected Operators

Appendix D. C++ Library Routines and Constants

Appendix E. The Character Sets

Answers to Selected Exercises

Programming Assignments

Glossary

Index

Editorial Reviews

Written as a second-semester text which focuses on abstract data types from three perspectives: specification, application, and implementation. Within this focus, the author stresses computer science theory and software engineering principles using chapter exercises, case studies, and programming assignments. Annotation c. by Book News, Inc., Portland, Or.

Booknews