دانلود کتاب C++ Programming: Program Design Including Data Structures

فهرست مطالب :

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 (<<) and Extraction (>>) 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