PART ONE
Preliminaries 1
An Overview of ANSI C 3
1.1 What is C? 4
1.2 The structure of a C program 5
Comments 7, Library inclusions 8, Program-level
definitions 8, Function prototypes 9, The main program 9,
Function definitions I0
1.3 Variables, values, and types 11
Variables 11, Naming conventions 12, Local and global
variables 13, The concept of a data type 13, Integer
types 14, Floating-point types 15, Text types 16, Boolean
type 18, Simple input and output 18
1.4 Expressions 20
Precedence and associativity 21, Mixing types in an
expression 22, Integer division and the remainder
operator 23, Type casts 24, The assignment operator 24,
Increment and decrement operators 26, Boolean operators 28
1.5 Statements 30
Simple statements 30, Blocks 30, The if statement 31, The
switch statement 32, The while statement 34, The for
statement 36
1.6 Functions 39
Returning results from functions 39, Function definitions and
prototypes 40, The mechanics of the function-calling
process 40, Stepwise refinement 41
Summary 42
Review questions 43
Programming exercises 45
2 Data Types in C 51
2.1 Enumeration types 52
Internal representation of enumeration types 53, Scalar
types 54, Understanding typedef 55
2.2 Data and memory 56
Bits, bytes, and words 56, Memory addresses 57
2.3 Pointers 59
Using addresses as data values 60, Declaring pointer
variables 60, The fundamental pointer operations 61, The
special pointer NULL 4, Passing parameters by reference 64
PART ONE
Preliminaries 1
An Overview of ANSI C 3
1.1 What is C? 4
1.2 The structure of a C program 5
Comments 7, Library inclusions 8, Program-level
definitions 8, Function prototypes 9, The main program 9,
Function definitions 10
1.3 Variables, values, and types 11
Variables 11, Naming conventions 12, Local and global
variables 13, The concept of a data type 13, Integer
types 14, Floating-point types 15, Text types 16, Boolean
type 18, Simple input andoutput 18
1.4 Expressions 20
Precedence and associativity 21, Mixing types in an
expression 22, Integer division and the remainder
operator 23, Type casts 24, The assignment operator 24,
Increment and decrement operators 26, Boolean operators 28
1.5 Statements 30
Simple statements 30, Blocks 30, The if statement 31, The
switch statement 32, The while statement 34, The for
statement 36
1.6 Functions 39
Returning results from functions 39, Function definitions and
prototypes 40, The mechanics of the function-calling
process 40, Stepwise refinement 41
Summary 42
Review questions 43
Programming exercises 45
2 Data Types in C 51
2.1 Enumeration lypes 52
Internal representation of enumeration types 53, Scalar
types 54, Understanding typedef 55
2.2 Data and memory 56
Bits, bytes, and words 56, Memory addresses 57
2.3 Pointers 59
Using addresses as data values 60, Declaring pointer
variables 60, The fundamental pointer operations 61, The
special pointer NULL, 64, Passing parameters by reference 64
2.4 Arrays 66
Array declaration 69, Array selection 70, Effective and
allocated sizes 71, Passing arrays as parameters 72,
Initialization of arrays 72, Multidimensional arrays 75
2.5 Pointers and arrays 77
Pointer arithmetic 78, Incrementing and decrementing
pointers 81, The relationship between pointers and arrays 82
2.6 Records 84
Defining a new structure type 85, Declaring structure
variables 85, Record selection 86, Initializing records 86,
Pointers to records 87
2.7 Dynamic allocation 88
THe type void ,, 89, Coping with memory limitations 90,
Dynamic arrays 91, Dynamic records 93
Summary 94
Review questions 95
Programming exercises 98
3 Libraries and Interfaces 107
3.1 The concept of an interface 108
Interfaces and implementations 108, Packages and
abstractions 109, Principles of good interface design 110
3.2 Random numbers 111
The structure of the random.h interface 111, Constructing a
client program 115, The ANSI functions for random
numbers 117, The random.c implementation 120
3.3 Strings 123
The underlying representation of a string 124, The data type
string 125, The ANSI string library 127, The strlib.h
interface 132
3.4 The standard I/O library 138
Data files 138, Using files in C 139, Standard files 141,
Character I/O 141, Rereading characters from an input
file 142, Updating a file 142, Line-oriented I/O 145,
Formatted I/O 146, The scanf functions 146
3.5 Other ANSI libraries 148
Summary 150
Review questions 151
Programming exercises 154
4 Introduction to Recursion
4.1 A simple example of recursion 164
4.2 The factorial function 166
The recursive formulation of Fact. 167, Tracing the recursive
process 167, The recursive leap of faith 171
4.3 The Fibanacci function 172
Computing terms in the Fibonacci sequence 173, Gaining
confidence in the recursive implementation 174, Efficiency of
the recursive implementation 176, Recursion is not to
blame 176
4.4 Other examples of recursion 178
Detecting palindromes 179, Binary search 180, Mutual
recursion 182
4.5 Thinking recursively 185
Maintaining a holistic perspective 185, Avoiding the common
pitfalls 186
Summary 187
Review questions 188
Programming exercises 190
5 Recursive Procedures
5.1 The Tower of Hanoi 196
Framing the problem 197, Finding a recursive strategy 198,
Validating the strategy 200, Coding the solution 201,
Tracing the recursive process 201
5.2 Generating permutations 206
The recursive insight 207
5.3 Graphical applications of recursion 208
The graphics library 209, An example from computer
art 212, Fractals 217
Summary 222
Review questions 223
Programming exercises 224
6 Backtracking Algorithms 235
6.1 Solving a maze by recursive backtracking 236
The right-hand rule 236, Finding a recursive approach 237
Identifying the simple cases 238, Coding the maze solution
algorithm 239, Convincing yourself that the solution
works 243
6.2 Backtracking and games 245
The game of nim 246, A generalized program for two-player
games 248, The minimax strategy 254, Implementing the
minimax algorithm 257, Using the general strategy to solve a
specific game 259
Summary 272
Review questions 272
Programming exercises 274
7 Algorithmic Analysis 283
7.1 The sorting problem 284
The selection sort algorithm 285, Empirical measurements of
performance 286, Analyzing the performance of selection
sort 287
7.2 Computational complexity 288
Big-O notation 289, Standard simplifications of big-O 290,
The computational complexity of selection sort 290,
Predicting computational complexity from code structure 291,
Worst-case versus average-case complexity 293, A formal
definition of big-O 294
7.3 Recursion to the rescue 296
The power of divide-and-conquer strategies 296, Merging two
arrays 297, The merge sort algorithm 298, The
computational complexity of merge sort 300, Comparing N2
and N log N performance 302
7.4 Standard complexily classes 303
7.5 The Quicksort algorithm 306
Partitioning the array 308, Analyzing the performance of
Quicksoft 311
7.6 Mathematical induction 312
Summary 315
Review questions 316
Programming exercises 318
PART THREE
Data Abstraction 325
8 Abstract Data Types 327
8.1 Stacks 328
The basic stack metaphor 329, Stacks and function
calls 329, Stacks and pocket calculators 330
8.2 Defining a stack ADT 331
Defining the types for the stack abstraction 331, Opaque
types 333, Defining the stack.h interface 334
8.3 Using stacks in an application 338
8.4 Implementing the stack abstraction 342
Defining the concrete type 342, Implementing the stack
operations 342, The advantages of opaque types 344
mproving the stack.c implementation 345
8.5 Defining a scanner ADT 347
The dangers of encapsulated state 347, Abstract data types as
an alternative to encapsulated state 348, Implementing the
scanner abstraction 353
Summary 358
Review questions 359
Programming exercises 360
9 Efficiency and ADTs 373
9.1 The concept of an editor buffer 374
9.2 Defining the buffer abstraction 375
Functions in the buffer.h interface 376, Coding the editor
application 379
9.3 Implementing the editor using arrays 380
Defining the concrete type 381, Implementing the buffer
operations 382, The computational complexity of the array
implementation 385
9.4 Implementing the editor using stacks 386
Defining the concrete structure far the stack-based buffer 387,
Implementing the buffer operations 387, Comparing
computational complexities 388
9.5 Implementing the editor using linked lists 391
The concept of a linked list 392, Designing a linked-list data
structure 393, Using a linked list to represent the
buffer 394, Insertion into a linked-list buffer 396, Deletion
in a linked-list buffer 398, Cursor motion in the linked-list
representation 399, Linked-list idioms 402 Completing the
buffer implementation 403, Computational complexity of the
linked-list buffer 404, Doubly linked lists 407, Time-space
tradeoffs 408
Summary 409
Review questions 410
Programming exercises 411
10 Linear Structures 419
10.1 Stacks revisited 420
10.2 Queues 424
The structure of the queue.h interface 427, Array-based
implementation of queues 427, Linked-list representation of
queues 433
10.3 Simulations involving queues 436
Simulations and models 439, The waiting-line model 440,
Discrete time 440, Events in simulated time 441,
Implementing the simulation 442
Summary 448
Review questions 449
Programming exercises 451
11 Symbol Tables 457
11.1 Defining a symbol table abstraction 458
Choosing types for values and keys 458, Representing an
undefined entry 460, A preliminary version of the symbol
table interface 461
11.2 Hashing 462
Implementing the hash table strategy 463, Choosing a hash
function 468, Determining the number of buckets 470
11.3 Limitations of the preliminary interface 471
11.4 Using functions as data 473
A general plotting function 473, Declaring pointers to
functions and function classes 474, Implementing
PlotFunction 475, The qsort function 476
11.5 Mapping functions 481
Mapping over entries in a symbol table 481, Implementing
MapsymbolTable 484, Passing client data to callback
functions 485
11.6 Iterators 486
Using iterators 487 Defining the iterator interface 488
Implementing the iterator abstraction for symbol tables 488
11.7 Command dispatch tables 492
Summary 496
Review questions 497
Programming exercises 499
12 Recursive Lists 507
12.1 The recursive formulation of a list 508
12.2 Defining an abstract list type 510
Immutable types 513 Functions that manipulate list
structure 514, Concatenating lists 517, Interna sharing in
immutable types 519
12.3 Using lists to represent large integers 520
The bigint.h interface 521, Representing the type
bigIntADT 521, Implementing the bigint package 524,
Using the bigint package 529
Summary 531
Review questions 532
Programming exercises 533
13 Trees 537
13.1 Family trees 538
Terminology used to describe trees 539, The recursive nature
of a tree 540, Representing family trees in C 540
13.2 Binary search trees 542
The underlying motivation for using binary search trees 543,
Finding nodes in a binary search tree 544, Inserting new
nodes in a binary search tree 545, Tree traversals 549
13.3 Balanced trees 551
Tree-balancing strategies 552, Illustrating the AVL
idea 553, Single rotations 555, Double rotations 557,
Implementing the AVL algorithm 558
13.4 Defining a general interface for binary search trees 561
Allowing the client to define the node structure 563,
Generalizing the types used for keys 570, Deleting
nodes 570, Implementing the binary search tree
package 572, Implementing the symtab.h interface using
binary trees 572
Summary 580
Review questions 581
Programming exercises 583
14 Expression Trees 593
14.1 Overview of the interpreter 594
14.2 The abstract structure of expressions 597
A recursive definition of expressions 597, Ambiguity 599,
Expression trees 600, Defining an abstract interface for
expressions 601
14.3 Defining the concrete expression type 606
Union types 606, Using tagged unions to represent
expressions 608, Visualizing the concrete
representation 610, Implementing the constructor and selector
functions 612
14.4 Parsing an expression 615
Parsing and grammars 615, Parsing without precedence 617,
Adding precedence to the parser 618
14.5 Evaluating an expression 621
Summary 623
Review questions 626
Programming exercises 627
15 Sets 641
15.1 Sets as a mathematical abstraction 642
Membership 643, Set operations 643, Identities on
sets 645
15.2 Designing a set interface 646
Defining the element type 647, Writing the set.h
interface 649, Character sets 649, Using pointer sets to
avoid duplication 654
15.3 Implementing the set package 654
15.4 Designing a polymorphic iterator 662
Generalizing the prototypes of the iterator functions 663,
Adding polymorphism to the iterator implementation 663,
Exporting a collection type 665, Coding the iterator
package 669, The foreach idiom 673
15.5 Enhancing the efficiency of integer sets 674
Characteristic vectors 674, Packed arrays 9f bits 675,
Bitwise operators 676, Implementing characteristic vectors
using the bib,vise operators 678, Implementing the high-level
set operations 680, Using a hybrid implementation 681
Summary 681
Review questions 683
Programming exercises 686
16 Graphs 693
16.1 The structure of a graph 694
Directed and undirected graphs 695, Paths and cycles 697,
Connectivity 697
16.2 Implementation strategies for graphs 698
Representing connections using an adjacency list 700,
Representing connections using an adjacency matrix 700
16.3 Extending the graph abstraction 703
Associating data with nodes and graphs 706, Making arcs
explicit 706, Iteration and graphs 708, Layered
abstractions 708, A set-based interface for graphs 709
16.4 Graph traversals 718
Depth-first search 719, Breadth-first search 721
16.5 Finding minimum paths 724.
An efficient implementation of priority queues 728
Summary 732
Review questions 733
Programming exercises 735
17 Looking Ahead to Java 745
17.1 The object-oriented paradigm 746
The history of object-oriented programming 747, Objects,
classes, and methods 748, Class hierarchies and inheritance 749
17.2 An introduction to Java 751
The structure of the Web 752, Applets 753, Executing a Java applet 757
17.3 The structure of Java 758
The syntax of Java 760, Atomic types in Java 761,
Defining a new class 762, Constructor methods 763, The keyword this 764, Defining methods 765, Defining subclasses 767
17.4 Predefined classes in Java 774
The string class 775, The Hashtable class 776,
Ob ect wrappers for the atomic types 779, The veer:or c ass 779, The stack class 781
17.5 Tools for creating interactive applets 782
Components and containers 783, The act:ion method 784,
A sample applet for drawing shapes 785, Moving ahead 793
Summary 794
Review questions 794
Programming exercises 796
Index 809
鄂公网安备 42010302001612号 