Programming Abstractions in C++

<p>Contents<br><strong>1 Overview of C++ 1</strong><br>1.1 Your first C++ program 2<br>1.2 The history of C++ 3<br>1.3 The structure of a C++ program 6<br>1.4 Variables 14<br>1.5 Data types 19<br>1.6 Expressions 26<br>1.7 Statements 36<br>Summary 47<br>Review questions 48<br>Exercises 50<br><strong>2 Functions and Libraries 55</strong><br>2.1 The idea of a function 56<br>2.2 Libraries 59<br>2.3 Defining functions in C++ 61<br>2.4 The mechanics of function calls 65<br>2.5 Reference parameters 73<br>2.6 Interfaces and implementations 78<br>2.7 Principles of interface design 85<br>2.8 Designing a random number library 90<br>2.9 Introduction to the Stanford libraries 107<br>Summary 112<br>Review questions 114<br>Exercises 115<br><strong>3 Strings 125</strong><br>3.1 Using strings as abstract values 126<br>3.2 String operations 129<br>3.3 The &lt;cctype&gt; library 137<br>3.4 Modifying the contents of a string 138<br>3.5 The legacy of C-style strings 139<br>3.6 Writing string applications 140<br>3.7 The strlib.h library 146<br>Summary 147<br>Review questions 148<br>Exercises 149<br><strong>4 Streams 159</strong><br>4.1 Using strings as abstract values 160<br>4.2 Formatted input 165<br>4.3 Data files 167<br>4.4 Class hierarchies 181<br>4.5 The simpio.h and filelib.h libraries 186<br>Summary 188<br>Review questions 189<br>Exercises 190<br><strong>5 Collections 195</strong><br>5.1 The Vector class 197<br>5.2 The Stack class 211<br>5.3 The Queue class 217<br>5.4 The Map class 226<br>5.5 The Set class 232<br>5.6 Iterating over a collection 236<br>Summary 243<br>Review questions 245<br>Exercises 246<br><strong>6 Designing Classes 261</strong><br>6.1 Representing points 262<br>6.2 Operator overloading 268<br>6.3 Rational numbers 281<br>6.4 Designing a token scanner class 292<br>6.5 Encapsulating programs as classes 301<br>Summary 303<br>Review questions 305<br>Exercises 306<br><strong>7 Introduction to Recursion 315</strong><br>7.1 A simple example of recursion 316<br>7.2 The factorial function 318<br>7.3 The Fibonacci function 325<br>7.4 Checking palindromes 332<br>7.5 The binary search algorithm 335<br>7.6 Mutual recursion 336<br>7.7 Thinking recursively 338<br>Summary 340<br>Review questions 342<br>Exercises 344<br><strong>8 Recursive Strategies 349</strong><br>8.1 The Towers of Hanoi 350<br>8.2 The subset-sum problem 361<br>8.3 Generating permutations 364<br>8.4 Graphical recursion 368<br>Summary 375<br>Review questions 375<br>Exercises 376<br><strong>9 Backtracking Algorithms 389</strong><br>9.1 Recursive backtracking in a maze 390<br>9.2 Backtracking and games 400<br>9.3 The minimax algorithm 409<br>Summary 415<br>Review questions 416<br>Exercises 417<br><strong>10 Algorithmic Analysis 429</strong><br>10.1 The sorting problem 430<br>10.2 Computational complexity 435<br>10.3 Recursion to the rescue 443<br>10.4 Standard complexity classes 449<br>10.5 The Quicksort algorithm 452<br>10.6 Mathematical induction 458<br>Summary 462<br>Review questions 463<br>Exercises 466<br><strong>11 Pointers and Arrays 473</strong><br>11.1 The structure of memory 474<br>11.2 Pointers 484<br>11.3 Arrays 494<br>11.4 Pointer arithmetic 500<br>Summary 506<br>Review questions 508<br>Exercises 510<br><strong>12 Dynamic Memory Management 515</strong><br>12.1 Dynamic allocation and the heap 516<br>12.2 Linked lists 519<br>12.3 Freeing memory 523<br>12.4 Defining a CharStack class 527<br>12.5 Heap-stack diagrams 536<br>12.6 Unit testing 543<br>12.7 Copying objects 546<br>12.8 The uses of const 550<br>12.9 Efficiency of the CharStack class 558<br>Summary 560<br>Review questions 562<br>Exercises 564<br><strong>13 Efficiency and Representation 569</strong><br>13.1 Software patterns for editing text 570<br>13.2 Designing a simple text editor 572<br>13.3 An array-based implementation 579<br>13.4 A stack-based implementation 586<br>13.5 A list-based implementation 591<br>Summary 607<br>Review questions 608<br>Exercises 610<br><strong>14 Linear Structures 615</strong><br>14.1 Templates 616<br>14.2 Implementing stacks 619<br>14.3 Implementing queues 634<br>14.4 Implementing vectors 649<br>14.5 Integrating prototypes and code 656<br>Summary 657<br>Review questions 658<br>Exercises 659<br><strong>15 Maps 663</strong><br>15.1 Implementing maps using vectors 664<br>15.2 Lookup tables 668<br>15.3 Hashing 671<br>15.4 Implementing the HashMap class 682<br>Summary 683<br>Review questions 684<br>Exercises 685<br><strong>16 Trees 689</strong><br>16.1 Family trees 691<br>16.2 Binary search trees 693<br>16.3 Balanced trees 706<br>16.4 Implementing maps using BSTs 717<br>16.5 Partially ordered trees 719<br>Summary 722<br>Review questions 724<br>Exercises 727<br><strong>17 Sets 737</strong><br>17.1 Sets as a mathematical abstraction 738<br>17.2 Expanding the set interface 742<br>17.3 Implementation strategies for sets 747<br>17.4 Optimizing sets of small integers 753<br>Summary 761<br>Review questions 762<br>Exercises 764<br><strong>18 Graphs 767</strong><br>18.1 The structure of a graph 768<br>18.2 Representation strategies 772<br>18.3 A low-level graph abstraction 776<br>18.4 Graph traversals 783<br>18.5 Defining a Graph class 789<br>18.6 Finding shortest paths 804<br>18.7 Algorithms for searching the web 808<br>Summary 812<br>Review questions 813<br>Exercises 815<br><strong>19 Inheritance 823</strong><br>19.1 Simple inheritance 824<br>19.2 A hierarchy of graphical shapes 832<br>19.3 A class hierarchy for expressions 841<br>19.4 Parsing an expression 861<br>19.5 Multiple inheritance 870<br>Summary 873<br>Review questions 875<br>Exercises 877<br><strong>20 Strategies for iteration 885</strong><br>20.1 Using iterators 886<br>20.2 Using functions as data values 890<br>20.3 Encapsulating data with functions 899<br>20.4 The STL algorithms library 904<br>20.5 Functional programming in C++ 907<br>20.6 Implementing iterators 911<br>Summary 918<br>Review questions 920<br>Exercises 921<br><strong>A Stanford library interfaces 927<br>Index 1025</strong></p>