C++: Introduction to Data Structures
Larry Nyhoff of Calvin College

Upper Saddle River, New Jersey: Prentice-Hall, 1999


NOTE: A new edition of this text has been published (summer 2004). Any corrections not on the errata page as well as suggestions for improving it are welcome.


Table of Contents


Errata List

This text is designed for the CS2 course as described in the curriculum recommendations of the ACM (Association of Computing Machinery). It assumes that the reader has completed a first course in programming and knows the basic syntax, fundamental data types, and operations of C++ as well as how to write and use functions. A knowledge of arrays and/or vector s and classes is helpful, but these are covered in detail in early chapters. The sections dealing with these may be omitted or treated lightly if desired

The text aims to meet the major objectives of this course as spelled out in the ACM curriculum recommendations. One of these objectives is:

This text continues the Object-Centered-Design paradigm developed in the C++ text of which I am one of the authors — C++: An Introduction to Computing 2e —and culminates in true OOP (Object-Oriented Programming), which has become the modus operandi in programming and system development. It also continues the coverage of C++, including more advanced topics not usually covered in a first course and which students need to learn them such as recursion, function and class templates, inheritance, and polymorphism. Standard C++ as spelled out in the final November, 1997 ANSI/ISO draft is used throughout. The text also presents some of the C-style topics appropriate in a data structures course, because many students will get jobs as C programmers, many libraries use C, and C-style data structures are usually implemented very efficiently and are often used to implement some of the more modern standard data types.

Two other objectives of CS2 are:

This text emphasizes abstract data types (ADTs) throughout, presenting them in the spirit of OOP. It covers all of the usual data structures as recommended. It also treats the containers and algorithms from the Standard Template Library, which are up-to-date and powerful standard data types and tools in C++.

Another objective of the CS2 course is:

One chapter of the text is devoted to searching and another chapter to sorting. The text also covers algorithm development, analysis, and verification in general, thus providing a first look at important tools for later courses in computer science.

The curriculum recommendations also include the following objective for the CS2 course:

  • To provide an introduction to the various areas of computer science and thereby provide a foundation for further studies in computer science.
  • This text continues the portrayal of the discipline of computer science begun in C++: An Introduction to Computing 2e & 3e by including examples and exercises from different areas of computer science in an attempt to provide a foundation for further study in theoretical and/or applied computer science. The topics include: a description of the software development process; data representation; Reverse Polish notation and generation of machine code; simple systems concepts such as input/output buffers, parameter-passing mechanisms, address translation, and memory management; computational complexity of algorithms, illustrated by the analysis of standard searching and sorting algorithms; an introduction to correctness proofs of algorithms; abstract data types; object-oriented programming; data encryption; data compression; pattern matching; Internet addresses; hash tables; doubly-linked lists and large integer arithmetic; numerical methods; random number generation and simulation.

    TABLE OF CONTENTS SOURCE PROGRAMS: Source code for all of the example programs and classes used in the text.
    ONLINE STUDY GUIDE POWERPOINT SLIDES: These are organized chapter by chapter and are based on lectures in the CS-2 course taught regularly by the author.
    Note: These have undergone several revisions by the author; also, coordinated student seminotes are available.
    ( Adobe Acrobat-PDF format) These are transparency masters used in the CS-2 course taught regularly by the author.
    ( Adobe Acrobat-PDF format) These are copies of the Lecture Transparencies but with various items left out -- examples, key code segments, etc. -- for students to fill in from the class lectures.
    A LAB MANUAL coordinated with the text has been published separately by Prentice-Hall (ISBN 013-084691-0). A set of revised and corrected SOLUTIONS FOR EXERCISE SETS is available to instructors who adopt the text for use in their courses. Contact the author for instructions on how to access these -- include your name, college/university, course number and name, and class size.
    Changes and corrections Reviews and User Comments

      This page maintained by Larry Nyhoff Last modified: