C++: Introduction to Data Structures
by
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
Supplements
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:
-
To continue developing a disciplined
approach to the design, coding, and testing of programs written in a high-level
language.
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:
-
To teach the use of data abstraction using as examples data structures
other than those normally provided as basic types in current programming
languages; for example, linked lists, stacks, queues, and trees.
-
To provide an understanding of the different
implementations of these data structures.
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:
-
To introduce searching and sorting algorithms
and their analysis.
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.
|
LECTURE TRANSPARENCIES
(
Adobe Acrobat-PDF format)
These are transparency masters used in the CS-2 course taught
regularly by the author.
|
STUDENT SEMI-NOTES
(
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: