Programming Abstractions in C++

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. 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 This is the eBook of the printed book and may not include any media, website access codes, or print supplements that may come packaged with the bound book. 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. Support Instructors and Students: The companion website provides source code, sample run PDFs, answers to review questions, and more.