stanford 106X C++讲义.pdf

【实例截图】

【核心代码】

Programming Abstractions in C  
Chapter 1. An Overview of C   1
1.1 What is C  ? 2
The object-oriented paradigm; The compilation process
1.2 The structure of a C   program 5
Comments; Library inclusions; Program-level definitions; Function prototypes;
The main program; Function definitions
1.3 Variables, values, and types 9
Naming conventions; Local and global variables; The concept of a data type;
Integer types; Floating-point types; Text types; Boolean type; Simple input and
output
1.4 Expressions 16
Precedence and associativity; Mixing types in an expression; Integer division and
the remainder operator; Type casts; The assignment operator; Increment and
decrement operators; Boolean operators
1.5 Statements 24
Simple statements; Blocks; The if statement; The switch statement; The while
statement; The for statement
1.6 Functions 32
Returning results from functions; Function definitions and prototypes; The
mechanics of the function-calling process; Passing parameters by reference
Summary 38
Review questions 39
Programming exercises 41
Chapter 2. Data Types in C   45
2.1 Enumeration types 46
Internal representation of enumeration types; Scalar types
2.2 Data and memory 49
Bits; bytes; and words; Memory addresses
2.3 Pointers 51
Using addresses as data values; Declaring pointer variables; The fundamental
pointer operations
2.4 Arrays 56
Array declaration; Array selection; Effective and allocated sizes; Initialization of
arrays; Multidimensional arrays
2.5 Pointers and arrays 64
The relationship between pointers and arrays
2.6 Records 67
Defining a new structure type; Declaring structure variables; Record selection;
Initializing records; Pointers to records
2.7 Dynamic allocation 71
Coping with memory limitations; Dynamic arrays; Dynamic records
iii
Summary 74
Review questions 74
Programming exercises 77
Chapter 3. Libraries and Interfaces 85
3.1 The concept of an interface 86
Interfaces and implementations; Packages and abstractions; Principles of good
interface design
3.2 A random number interface 89
The structure of the random.h interface; Constructing a client program; The ANSI
functions for random numbers; The random.cpp implementation
3.3 Strings 98
The data type string; Operations on the string type ; The strutils.h
interface; An aside about C-style strings
3.4 Standard I/O and file streams 105
Data files; Using file streams in C  ; Standard streams; Formatted stream output;
Formatted stream input; Single character I/O; Rereading characters from an input
file; Line-oriented I/O
3.5 Other ANSI libraries 112
Summary 113
Review questions 113
Programming exercises 116
Chapter 4. Using Abstract Data Types 123
4.1 The Vector class 125
Specifying the base type of a Vector; Declaring a new Vector object; Operations
on the Vector class; Iterating through the elements of a Vector; Passing a Vector
as a parameter
4.2 The Grid class 131
4.3 The Stack class 133
The structure of the Stack class
4.4 The Queue class 136
Simulations and models; The waiting-line model; Discrete time; Events in
simulated time; Implementing the simulation
4.5 The Map class 146
The structure of the Map class; Using maps in an application; Maps as associative
arrays
4.6 The Lexicon class 151
The structure of the Lexicon class; A simple application of the Lexicon class;
Why are lexicons useful if maps already exist
4.7 The Scanner class 154
Setting scanner options
4.8 Iterators 156
The standard iterator pattern; Iteration order; A simple iterator example;
Computing word frequencies
iv
Summary 163
Review questions 164
Programming exercises 165
Chapter 5. Introduction to recursion 173
5.1 A simple example of recursion 174
5.2 The factorial function 176
The recursive formulation of Fact; Tracing the recursive process; The recursive
leap of faith
5.3 The Fibonacci function 181
Computing terms in the Fibonacci sequence; Gaining confidence in the recursive
implementation; Recursion is not to blame
5.4 Other examples of recursion 187
Detecting palindromes; Binary search; Mutual recursion
5.5 Thinking recursively 192
Maintaining a holistic perspective; Avoiding the common pitfalls
Summary 194
Review questions 195
Programming exercises 197
Chapter 6. Recursive procedures 201
6.1 The Tower of Hanoi 202
Framing the problem; Finding a recursive strategy; Validating the strategy;
Coding the solution; Tracing the recursive process
6.2 Generating permutations 211
The recursive insight
6.3 Graphical applications of recursion 213
The graphics library; An example from computer art; Fractals
Summary 224
Review questions 225
Programming exercises 226
Chapter 7. Backtracking algorithms 235
7.1 Solving a maze by recursive backtracking 236
The right-hand rule; Finding a recursive approach; Identifying the simple cases;
Coding the maze solution algorithm; Convincing yourself that the solution works
7.2 Backtracking and games 245
The game of nim; A generalized program for two-player games; The minimax
strategy; Implementing the minimax algorithm; Using the general strategy to
solve a specific game
Summary 269
Review questions 270
Programming exercises 271
v
Chapter 8. Algorithmic analysis 277
8.1 The sorting problem 278
The selection sort algorithm; Empirical measurements of performance; Analyzing
the performance of selection sort
8.2 Computational complexity and big-O notation 282
Big-O notation; Standard simplifications of big-O; Predicting computational
complexity from code structure; Worst-case versus average-case complexity; A
formal definition of big-O
8.3 Recursion to the rescue 288
The power of divide-and-conquer strategies; Merging two vectors; The merge sort
algorithm; The computational complexity of merge sort; Comparing N2 and N log
N performance
8.4 Standard complexity classes 294
8.5 The Quicksort algorithm 296
Partitioning the vector; Analyzing the performance of Quicksort
8.6 Mathematical induction 301
Summary 304
Review questions 305
Programming exercises 307
Chapter 9. Classes and objects 313
9.1 A simple example of a class definition 314
Defining a Point class; Implementing methods in a class; Constructors and
destructors; The keyword this
9.2 Implementing a specialized version of the Stack class 319
Defining the CharStack interface; Representing the stack data; The advantages of
object encapsulation; Removing the maximum size limitation; Object copying
9.3 Implementing the Scanner class 328
Summary 328
Review questions 334
Programming exercises 335
Chapter 10. Efficiency and Data Representation 339
10.1 The concept of an editor buffer 340
10.2 Defining the buffer abstraction 341
The public interface of the EditorBuffer class; Coding the editor application
10.3 Implementing the editor using arrays 345
Defining the private data representation; Implementing the buffer operations;
Assessing the computational complexity of the array implementation
10.4 Implementing the editor using stacks 352
Defining the private data representation for the stack-based buffer; Implementing
the buffer operations; Comparing computational complexities
vi
10.5 Implementing the editor using linked lists 357
The concept of a linked list; Designing a linked-list data structure; Using a linked
list to represent the buffer; Insertion into a linked-list buffer; Deletion in a linkedlist buffer; Cursor motion in the linked-list representation; Linked-list idioms;
Completing the buffer implementation; Computational complexity of the linkedlist buffer; Doubly linked lists; Time-space tradeoffs
Summary 371
Review questions 372
Programming exercises 373
Chapter 11. Linear Structures 381
11.1 Reimplementing stacks as a template class 382
The interface of a class template
11.2 Reimplementing stacks using linked lists 383
11.3 Implementing queues 391
An array-based implementation of queues; Linked-list representation of queues
11.4 Implementing vectors 404
Supporting insertion and deletion at arbitrary index positions; Implementing
selection brackets; Implementing iterators
Summary 414
Review questions 415
Programming exercises 416
Chapter 12. Implementing Maps 419
12.1 An array-based implementation of the map interface 420
12.2 The advantage of knowing where to look 427
12.3 Hashing 429
Implementing the hash table strategy; Choosing a hash function; Determining the
number of buckets; Using the typename keyword
12.4 Functions as data 438
A general plotting function; Declaring pointers to functions and function
typedefs; Implementing Plot; A generic sorting function
12.5 Mapping functions 444
Mapping over entries in a map; Implementing mapAll; Passing client information
to a callback function; A note on function types and methods
Summary 448
Review questions 449
Programming exercises 450
Chapter 13. Trees 455
13.1 Family trees 456
Terminology used to describe trees; The recursive nature of a tree; Representing
family trees in C  
vii
13.2 Binary search trees 459
The underlying motivation for using binary search trees; Finding nodes in a
binary search tree; Inserting new nodes in a binary search tree; Tree traversals
13.3 Balanced trees 466
Tree-balancing strategies; Illustrating the AVL idea; Single rotations; Double
rotations; Implementing the AVL algorithm
13.4 Defining a general interface for binary search trees 477
Allowing the client to define the node data; Generalizing the types used for keys;
Removing nodes; Implementing the binary search tree package; Implementing the
map.h interface using binary trees; Using the static keyword
Summary 488
Review questions 489
Programming exercises 492
Chapter 14. Expression Trees 499
14.1 Overview of the interpreter 500
14.2 Understanding the abstract structure of expressions 505
A recursive definition of expressions; Expression trees
14.3 Class hierarchies and inheritance 509
14.4 Defining an inheritance hierarchy for expressions 510
Defining the interface for the expression subclasses
14.5 Implementing the node classes 518
Implementing the methods
14.6 Parsing an expression 522
Parsing and grammars; Parsing without precedence; Adding precedence to the
parser
Summary 528
Review questions 528
Programming exercises 530
Chapter 15. Sets 535
15.1 Sets as a mathematical abstraction 536
Membership; Set operations; Identities on sets
15.2 Designing a set interface 539
Defining the element type; Writing the set interface; Character sets; Using sets to
avoid duplication
15.3 Implementing the set class 544
15.4 Enhancing the efficiency of integer sets 548
Characteristic vectors; Packed arrays of bits; Bitwise operators; Implementing
characteristic vectors using the bitwise operators; Implementing the high-level set
operations; Using a hybrid implementation
Summary 555
Review questions 556
Programming exercises 558
viii
Chapter 16. Graphs 563
16.1 The structure of a graph 564
Directed and undirected graphs; Paths and cycles; Connectivity
16.2 Implementation strategies for graphs 568
Representing connections using an adjacency list; Representing connections using
an adjacency matrix; Representing connections using a set of arcs
16.3 Designing a low-level graph abstraction 571
Using the low-level graph.h interface
16.4 Graph traversals 575
Depth-first search; Breadth-first search
16.5 Defining a Graph class 580
Using classes for graphs, nodes, and arcs; Adopting an intermediate strategy
16.6 Finding minimum paths 589
16.7 An efficient implementation of priority queues 593
Summary 596
Review questions 597
Programming exercises 599
Appendix A. Library Interfaces 607
bst.h 608
cmpfn.h 611
extgraph.h 612
genlib.h 622
graph.h 623
graphics.h 627
grid.h 630
lexicon.h 634
map.h 638
queue.h 642
random.h 644
scanner.h 646
set.h 652
simpio.h 656
sound.h 657
stack.h 658
strutils.h 660
vector.h 662
Index 657
Chapter 1
An Overview