This text is intended for use in the second programming course
Programming is a matter of learning by doing. Eric Roberts’ Programming Abstractions in C++ gives students opportunities to practice and learn with engaging graphical assignments. A client-first approach to data structures helps students absorb, and then apply the material.
Teaching and Learning Experience
This program presents a better teaching and learning experience—for you and your students. It will help:
Improve Student Comprehension with a Client-first Approach to Data Structures: To aid in student understanding, this book presents the full set of collection classes early.
Defer the Presentation of C++ Features that Require a Detailed Understanding of the Underlying Machine: Introducing collection classes early enables students to master other equally important topics without having to struggle with low-level details at the same time.
Engage Students with Exciting Graphical Assignments: An open-source library supports graphics and interactivity in a simple, pedagogically appropriate way.
Author(s): Eric S. Roberts
Publisher: Pearson
Year: 2014
Language: English
Pages: 959
Cover
Title Page
Copyright Page
To the Student
To the Instructor
Supplemental Resources
Acknowledgments
Contents
1 Overview of C++
1.1 Your first C++ program
1.2 The history of C++
1.3 The compilation process
1.4 The structure of a C++ program
1.5 Variables
1.6 Data types
1.7 Expressions
1.8 Statements
Summary
Review questions
Exercises
2 Functions and Libraries
2.1 The idea of a function
2.2 Libraries
2.3 Defining functions in C++
2.4 The mechanics of function calls
2.5 Reference parameters
2.6 Interfaces and implementations
2.7 Principles of interface design
2.8 Designing a random number library
2.9 Introduction to the Stanford libraries
Summary
Review questions
Exercises
3 Strings
3.1 Using strings as abstract values
3.2 String operations
3.3 The library
3.4 Modifying the contents of a string
3.5 The legacy of C-style strings
3.6 Writing string applications
3.7 The strlib.h library
Summary
Review questions
Exercises
4 Streams
4.1 Formatted output
4.2 Formatted input
4.3 Data files
4.4 Class hierarchies
4.5 The simpio.h and filelib.h libraries
Summary
Review questions
Exercises
5 Collections
5.1 The Vector class
5.2 The Stack class
5.3 The Queue class
5.4 The Map class
5.5 The Set class
5.6 Iterating over a collection
Summary
Review questions
Exercises
6 Designing Classes
6.1 Representing points
6.2 Operator overloading
6.3 Rational numbers
6.4 Designing a token scanner class
6.5 Encapsulating programs as classes
Summary
Review questions
Exercises
7 Introduction to Recursion
7.1 A simple example of recursion
7.2 The factorial function
7.3 The Fibonacci function
7.4 Checking palindromes
7.5 The binary search algorithm
7.6 Mutual recursion
7.7 Thinking recursively
Summary
Review questions
Exercises
8 Recursive Strategies
8.1 The Towers of Hanoi
8.2 The subset-sum problem
8.3 Generating permutations
8.4 Graphical recursion
Summary
Review questions
Exercises
9 Backtracking Algorithms
9.1 Recursive backtracking in a maze
9.2 Backtracking and games
9.3 The minimax algorithm
Summary
Review questions
Exercises
10 Algorithmic Analysis
10.1 The sorting problem
10.2 Computational complexity
10.3 Recursion to the rescue
10.4 Standard complexity classes
10.5 The Quicksort algorithm
10.6 Mathematical induction
Summary
Review questions
Exercises
11 Pointers and Arrays
11.1 The structure of memory
11.2 Pointers
11.3 Arrays
11.4 Pointer arithmetic
Summary
Review questions
Exercises
12 Dynamic Memory Management
12.1 Dynamic allocation and the heap
12.2 Linked lists
12.3 Freeing memory
12.4 Defining a CharStack class
12.5 Heap-stack diagrams
12.6 Unit testing
12.7 Copying objects
12.8 The uses of const
12.9 Efficiency of the CharStack class
Summary
Review questions
Exercises
13 Efficiency and Representation
13.1 Software patterns for editing text
13.2 Designing a simple text editor
13.3 An array-based implementation
13.4 A stack-based implementation
13.5 A list-based implementation
Summary
Review questions
Exercises
14 Linear Structures
14.1 Templates
14.2 Implementing stacks
14.3 Implementing queues
14.4 Implementing vectors
14.5 Integrating prototypes and code
Summary
Review questions
Exercises
15 Maps
15.1 Implementing maps using vectors
15.2 Lookup tables
15.3 Hashing
15.4 Implementing the HashMap class
Summary
Review questions
Exercises
16 Trees
16.1 Family trees
16.2 Binary search trees
16.3 Balanced trees
16.4 Implementing maps using BSTs
16.5 Partially ordered trees
Summary
Review questions
Exercises
17 Sets
17.1 Sets as a mathematical abstraction
17.2 Expanding the set interface
17.3 Implementation strategies for sets
17.4 Optimizing sets of small integers
Summary
Review questions
Exercises
18 Graphs
18.1 The structure of a graph
18.2 Representation strategies
18.3 A low-level graph abstraction
18.4 Graph traversals
18.5 Defining a Graph class
18.6 Finding shortest paths
18.7 Algorithms for searching the web
Summary
Review questions
Exercises
19 Inheritance
19.1 Simple inheritance
19.2 A hierarchy of graphical shapes
19.3 A class hierarchy for expressions
19.4 Parsing an expression
19.5 Multiple inheritance
Summary
Review questions
Exercises
20 Strategies for iteration
20.1 Using iterators
20.2 Using functions as data values
20.3 Encapsulating data with functions
20.4 The STL algorithms library
20.5 Functional programming in C++
20.6 Implementing iterators
Summary
Review questions
Exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
