C++ Programming: Program Design Including Data Structures

Description

Publishing companies are scum, education should not have a paywall. Enjoy :) Cover Brief Contents Table of Contents Preface Features of the Book Supplemental Resources Acknowledgments Chapter 1: AN OVERVIEW OF COMPUTERS AND PROGRAMMING LANGUAGES Introduction A Brief Overview of the History of Computers Elements of a Computer System Hardware Central Processing Unit and Main Memory Input/Output Devices Software The Language of a Computer The Evolution of Programming Languages Processing a C11 Program Programming with the Problem Analysis–Coding–Execution Cycle Programming Methodologies Structured Programming Object-Oriented Programming ANSI/ISO Standard C11 Quick Review Exercises Chapter 2: BASIC ELEMENTS OF C++ A Quick Look at a C11 Program The Basics of a C11 Program Comments Special Symbols Reserved Words (Keywords) Identifiers Whitespaces Data Types Simple Data Types Floating-Point Data Types Data Types, Variables, and Assignment Statements Arithmetic Operators, Operator Precedence, and Expressions Order of Precedence Expressions Mixed Expressions Type Conversion (Casting) string Type Variables, Assignment Statements, and Input Statements Allocating Memory with Constants and Variables Putting Data into Variables Assignment Statement Saving and Using the Value of an Expression Declaring and Initializing Variables Input (Read) Statement Variable Initialization Increment and Decrement Operators Output Preprocessor Directives namespace and Using cin and cout in a Program Using the string Data Type in a Program Creating a C11 Program Debugging: Understanding and Fixing Syntax Errors Program Style and Form Syntax Use of Blanks Use of Semicolons, Brackets, and Commas Semantics Naming Identifiers Prompt Lines Documentation Form and Style More on Assignment Statements Programming Example: Convert Length Programming Example: Make Change Quick Review Exercises Programming Exercises Chapter 3: INPUT/OUTPUT I/O Streams and Standard I/O Devices cin and the Extraction Operator >> Using Predefined Functions in a Program cin and the get Function cin and the ignore Function The putback and peek Functions The Dot Notation between I/O Stream Variables and I/O Functions: A Precaution Input Failure The clear Function Output and Formatting Output setprecision Manipulator fixed Manipulator showpoint Manipulator C++14 Digit Separator setw Additional Output Formatting Tools setfill Manipulator left and right Manipulators Input/Output and the string Type Debugging: Understanding Logic Errors and Debugging with cout Statements File Input/Output Programming Example: Movie TicketsSale and Donation to Charity Programming Example: Student Grade Quick Review Exercises Programming Exercises Chapter 4: CONTROL STRUCTURES I (SELECTION) Control Structures SELECTION: if AND if . . . else Relational Operators and Simple Data Types Comparing Characters One-Way Selection Two-Way Selection int Data Type and Logical (Boolean) Expressions bool Data Type and Logical (Boolean) Expressions Logical (Boolean) Operators and Logical Expressions Order of Precedence Relational Operators and the string Type Compound (Block of) Statements Multiple Selections: Nested if Comparing if...else Statements with a Series of if Statements Short-Circuit Evaluation Comparing Floating-Point Numbers for Equality: A Precaution Associativity of Relational Operators: A Precaution Avoiding Bugs by Avoiding Partially Understood Concepts and Techniques Input Failure and the if Statement Confusion between the Equality Operator (==) and the Assignment Oper-ator (=) Conditional Operator (:) Program Style and Form (Revisited): Indentation Using Pseudocode to Develop, Test, and Debug a Program switch Structures Avoiding Bugs by Avoiding Partially Understood Concepts and Techniques (Revisited) Terminating a Program with the assert Function Programming Example: Cable Company Billing Quick Review Exercises Programming Exercises Chapter 5: CONTROL STRUCTURES II (REPETITION) Why Is Repetition Needed while Looping (Repetition) Structure Designing while Loops Case 1: Counter-Controlled while Loops Case 2: Sentinel-Controlled while Loops Case 3: Flag-Controlled while Loops Case 4: EOF-Controlled while Loops eof Function More on Expressions in while Statements Programming Example: Fibonacci Number for Looping (Repetition) Structure Programming Example: Classifying Numbers do...while Looping (Repetition) Structure Divisibility Test by 3 and 9 Choosing the Right Looping Structure break and continue Statements Nested Control Structures Avoiding Bugs by Avoiding Patches Debugging Loops Quick Review Exercises Programming Exercises Chapter 6: USER-DEFINED FUNCTIONS Predefined Functions User-Defined Functions Value-Returning Functions Syntax: Value-Returning Function Syntax: Formal Parameter List Function Call Syntax: Actual Parameter List return Statement Syntax: return Statement Function Prototype Syntax: Function Prototype Value-Returning Functions: Some Peculiarities More Examples of Value-Returning Functions Flow of Compilation and Execution Programming Example: Largest Number Void Functions Value Parameters Reference Variables as Parameters Calculate Grade Value and Reference Parameters and Memory Allocation Reference Parameters and Value-Returning Functions Scope of an Identifier Global Variables, Named Constants, and Side Effects Static and Automatic Variables Debugging: Using Drivers and Stubs Function Overloading: An Introduction Functions with Default Parameters Programming Example: Classify Numbers Programming Example: Data Comparison Quick Review Exercises Programming Exercises Chapter 7: USER-DEFINED SIMPLE DATA TYPES, NAMESPACES, AND THE STRING TYPE Enumeration Type Declaring Variables Assignment Operations on Enumeration Types Relational Operators Input /Output of Enumeration Types Functions and Enumeration Types Declaring Variables When Defining the Enumeration Type Anonymous Data Types typedef Statement Programming Example: The Game of Rock, Paper, and Scissors Namespaces string Type Additional string Operations Programming Example: Pig Latin Strings Quick Review Exercises Programming Exercises Chapter 8: ARRAYS AND STRINGS Arrays Accessing Array Components Processing One-Dimensional Arrays Array Index Out of Bounds Array Initialization during Declaration Partial Initialization of Arrays during Declaration Some Restrictions on Array Processing Arrays as Parameters to Functions Constant Arrays as Formal Parameters Base Address of an Array and Array in Computer Memory Functions Cannot Return a Value of the Type Array Integral Data Type and Array Indices Other Ways to Declare Arrays Searching an Array for a Specific Item Sorting Auto Declaration and Range-Based For Loops C-Strings (Character Arrays) String Comparison Reading and Writing Strings String Input String Output Specifying Input/Output Files at Execution Time string Type and Input/Output Files Parallel Arrays Two- and Multidimensional Arrays Accessing Array Components Two-Dimensional Array Initialization during Declaration Two-Dimensional Arrays and Enumeration Types Initialization Print Input Sum by Row Sum by Column Largest Element in Each Row and Each Column Passing Two-Dimensional Arrays as Parameters to Functions Arrays of Strings Arrays of Strings and the string Type Arrays of Strings and C-Strings (Character Arrays) Another Way to Declare a Two-Dimensional Array Multidimensional Arrays Programming Example: Code Detection Programming Example: Text Processing Quick Review Exercises Programming Exercises Chapter 9: RECORDS (STRUCTS) Records (structs) Accessing struct Members Assignment Comparison (Relational Operators) Input/Output struct Variables and Functions Arrays versus structs Arrays in structs structs in Arrays structs within a struct Programming Example: Sales Data Analysis Quick Review Exercises Programming Exercises Chapter 10: CLASSES AND DATA ABSTRACTION Classes Unified Modeling Language Class Diagrams Variable (Object) Declaration Accessing Class Members Built-in Operations on Classes Assignment Operator and Classes Class Scope Functions and Classes Reference Parameters and Class Objects (Variables) Implementation of Member Functions Accessor and Mutator Functions Order of public and private Members of a Class Constructors Invoking a Constructor Invoking the Default Constructor Invoking a Constructor with Parameters Constructors and Default Parameters Classes and Constructors: A Precaution In-line Initialization of Data Members and the Default Constructor Arrays of Class Objects (Variables) and Constructors Destructors Data Abstraction, Classes, and Abstract Data Types A struct versus a class Information Hiding Executable Code More Examples of Classes Inline Functions Static Members of a Class Programming Example: Juice Machine Quick Review Exercises Programming Exercises Chapter 11: INHERITANCE AND COMPOSITION Inheritance Redefining (Overriding) Member Functions of the Base Class Constructors of Derived and Base Classes Destructors in a Derived Class Multiple Inclusions of a Header File C11 Stream Classes Protected Members of a Class Inheritance as public, protected, or private (Accessing protected Members in the Derived Class) Composition (Aggregation) Object-Oriented Design (OOD) and Object-Oriented Programming (OOP) Identifying Classes, Objects, and Operations Programming Example: Grade Report Quick Review Exercises Programming Exercises Chapter 12: POINTERS, CLASSES, VIRTUAL FUNCTIONS, ABSTRACT CLASSES, AND LISTS Pointer Data Type and Pointer Variables Declaring Pointer Variables Address of Operator (&) Dereferencing Operator (*) Classes, Structs, and Pointer Variables Initializing Pointer Variables Initializing Pointer Variables Using nullptr Dynamic Variables Operator new Operator delete Operations on Pointer Variables Dynamic Arrays Arrays and Range-Based for Loops (Revisited) Functions and Pointers Pointers and Function Return Values Dynamic Two-Dimensional Arrays Shallow versus Deep Copy and Pointers Classes and Pointers: Some Peculiarities Destructor Assignment Operator Copy Constructor Inheritance, Pointers, and Virtual Functions Classes and Virtual Destructors Abstract Classes and Pure Virtual Functions Array-Based Lists Unordered Lists Ordered Lists Address of Operator and Classes Quick Review Exercises Programming Exercises Chapter 13: OVERLOADING AND TEMPLATES Why Operator Overloading Is Needed Operator Overloading Syntax for Operator Functions Overloading an Operator: Some Restrictions Pointer this Friend Functions of Classes Operator Functions as Member Functions and Nonmember Functions Overloading Binary Operators Overloading the Stream Insertion () Operators Overloading the Assignment Operator (=) Overloading Unary Operators Operator Overloading: Member versus Nonmember Classes and Pointer Member Variables (Revisited) Operator Overloading: One Final Word Programming Example: clockType Programming Example: Complex Numbers Overloading the Array Index (Subscript) Operator ([]) Programming Example: newString Function Overloading Templates Function Templates Class Templates Array-Based Lists (Revisited) C1111 Random Number Generator Quick Review Exercises Programming Exercises Chapter 14: EXCEPTION HANDLING Handling Exceptions within a Program C11 Mechanisms of Exception Handling try/catch Block Using C11 Exception Classes Creating Your Own Exception Classes Rethrowing and Throwing an Exception Exception-Handling Techniques Terminate the Program Fix the Error and Continue Log the Error and Continue Stack Unwinding Quick Review Exercises Programming Exercises Chapter 15: RECURSION Recursive Definitions Direct and Indirect Recursion Infinite Recursion Problem Solving Using Recursion Tower of Hanoi: Analysis Recursion or Iteration Programming Example: Converting a Number from Binary to Decimal Programming Example: Converting a Number from Decimal to Binary Quick Review Exercises Programming Exercises Chapter 16: LINKED LISTS Linked Lists Linked Lists: Some Properties Deletion Building a Linked List Linked List as an ADT Structure of Linked List Nodes Member Variables of the class linkedListType Linked List Iterators Print the List Length of a List Retrieve the Data of the First Node Retrieve the Data of the Last Node Begin and End Copy the List Destructor Copy Constructor Overloading the Assignment Operator Unordered Linked Lists Search the List Insert the First Node Insert the Last Node Header File of the Unordered Linked List Ordered Linked Lists Search the List Insert a Node Insert First and Insert Last Delete a Node Header File of the Ordered Linked List Print a Linked List in Reverse Order (Recursion Revisited) printListReverse Doubly Linked Lists Default Constructor isEmptyList Destroy the List Initialize the List Length of the List Print the List Reverse Print the List Search the List First and Last Elements Circular Linked Lists Programming Example: DVD Store Quick Review Exercises Programming Exercises Chapter 17: STACKS AND QUEUES Stacks Stack Operations Implementation of Stacks as Arrays Initialize Stack Empty Stack Full Stack Push Return the Top Element Pop Copy Stack Constructor and Destructor Copy Constructor Overloading the Assignment Operator (=) Stack Header File Programming Example: Highest GPA Linked Implementation of Stacks Default Constructor Empty Stack and Full Stack Initialize Stack Push Return the Top Element Pop Copy Stack Constructors and Destructors Overloading the Assignment Operator (=) Stack as Derived from the class unorderedLinkedList Application of Stacks: Postfix Expressions Calculator Main Algorithm Function evaluateExpression Function evaluateOpr Function discardExp Function printResult Removing Recursion: Nonrecursive Algorithm to Print a Linked List Backward Queues Queue Operations Implementation of Queues as Arrays Linked Implementation of Queues Queue Derived from the class unorderedLinkedListType Application of Queues: Simulation Designing a Queuing System Customer Server Server List Waiting Customers Queue Main Program Quick Review Exercises Programming Exercises Chapter18: SEARCHING AND SORTING ALGORITHMS Searching and Sorting Algorithms Search Algorithms Sequential Search Binary Search Performance of Binary Search Binary Search Algorithm and the class ordered ArrayListType Asymptotic Notation: Big-O Notation Lower Bound on Comparison-Based Search Algorithms Sorting Algorithms Sorting a List: Bubble Sort Analysis: Bubble Sort Bubble Sort Algorithm and the class unorderedArrayListType Selection Sort: Array-Based Lists Analysis: Selection Sort Insertion Sort: Array-Based Lists Analysis: Insertion Sort Lower Bound on Comparison-Based Sort Algorithms Quick Sort: Array-Based Lists Analysis: Quick Sort Merge Sort: Linked List–Based Lists Divide Merge Analysis: Merge Sort Programming Example: Election Results Quick Review Exercises Programming Exercises Chapter19: BINARY TREES Binary Trees Copy Tree Binary Tree Traversal Implementing Binary Trees Binary Search Trees Binary Search Tree: Analysis Nonrecursive Binary Tree Traversal Algorithms Nonrecursive Inorder Traversal Nonrecursive Preorder Traversal Nonrecursive Postorder Traversal Binary Tree Traversal Algorithms and Functions as Parameters Programming Example: DVD Store (Revisited) Quick Review Exercises Programming Exercises Chapter20: GRAPHS Introduction Graph Definitions and Notations Graph Representation Adjacency Matrix Adjacency Lists Operations on Graphs Graphs as ADTs Graph Traversals Depth First Traversal Breadth First Traversal Shortest Path Algorithm Shortest Path Minimal Spanning Tree Quick Review Exercises Programming Exercises Chapter 21: STANDARD TEMPLATE LIBRARY (STL) Components of the STL Container Types Sequence Containers Sequence Container: vector Member Functions Common to All Containers Member Functions Common to Sequence Containers The copy Algorithm Range-Based for Loops Initializing vector Objects during Declaration Sequence Container: deque Sequence Container: list Iterators Types of Iterators Stream Iterators istream_iterator ostream_iterator Associative Containers Associative Containers: set and multiset Declaring set or multiset Associative Containers Item Insertion and Deletion from set/multiset Container Adapters Stack Queue Containers, Associated Header Files, and Iterator Support Algorithms STL Algorithm Classification Function Objects Insert Iterator STL Algorithms The Functions fill and fill_n The Functions generate and generate_n The Functions find, find_if, find_end, and find_first_of The Functions remove, remove_if, remove_copy,and remove_copy_if The Functions replace, replace_if, replace_copy, and replace_copy_if The Functions swap, iter_swap, and swap_ranges The Functions search, search_n, sort, and binary_search The Functions adjacent_find, merge, and inplace_merge The Functions reverse, reverse_copy, rotate, and rotate_copy The Functions count, count_if, max, max_element, min, min_element, and random_shuffle The Functions for_each and transform The Functions includes, set_intersection, set_union, set_difference, and set_symmetric_difference The Functions accumulate, adjacent_difference, inner_product, and partial_sum Quick Review Exercises Programming Exercises APPENDIX A: Reserved Words APPENDIX B: Operator Precedence APPENDIX C: Character Sets ASCII (American Standard Code for Information Interchange) EBCDIC (Extended Binary Coded Decimal Interchange Code) APPENDIX D: OPERATOR OVERLOADING APPENDIX E: ADDITIONAL C++ TOPICS Binary (Base 2) Representation of a Nonnegative Integer Converting a Base 10 Number to a Binary Number (Base 2) Converting a Binary Number (Base 2) to Base 10 Converting a Binary Number (Base 2) to Octal (Base 8) and Hexadecimal (Base 16) More on File Input/Output Binary Files Random File Access Naming Conventions of Header Files in ANSI/ISO Standard C++ and Standard C++ APPENDIX F: HEADER FILES Header File cassert (assert.h) Header File cctype (ctype.h) Header File cfloat (float.h) Header File climits (limits.h) Header File cmath (math.h) Header File cstddef (stddef.h) Header File cstring (string.h) APPENDIX G: MEMORY SIZE ON A SYSTEM APPENDIX H: REFERENCES APPENDIX I: ANSWERS TO ODD-NUMBERED EXERCISES Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 INDEX