1 lntduction 1
1.1 A brief history of computing 2
1.2 What is computer science 4
1.3 A brief tour of computer hardware 6
The CPU 7
Memory 7
Secondary storage 8
l/O devices 8
1.4 Algorithms 9
1.5 Programming languages and compilation 10
1.6 Programming errors and debugging 12
1.7 Software maintenance 13
1.8 The importance of software engineering 14
1.9 Some thoughts on the C programming language 15
Summary 16
REVIEW QUESTIONS 17
PART ONE The Basics of C Programming 19
2 Learning by Example 21
2.1 The ”Hello world” program 22
Comments 22
library inclusions 23
The main program 24
2.2 A program to add two numbers 26
The input phase 28
The computation phase 30
The output phase 30
2.3 Perspectives on the programming process 32
2.4 Data types 33
Floating-point data 34
String data 34
2.5 Expressions 37
Constants 38
Variables 39
Assignment statements 41
Operatorsand operands 43
Combining integers and floating-point numbers 44
Integer division and the remainder operator 45
Precedence 45
Applying precedence rules 48
ype conversion 48
Summa 51
REVIEW QUESTIONS 52
PROGRAMMING EXERCISES 55
3 Problem Solving 59
3.1 Programming idioms and paradigms 60
Shorthand assignment idioms 61
Increment and decrement operators 62
3.2 Solving problems on a larger scale 63
3.3 Control statements 65
The repeat-N-times idiom 65
Iteration and loops 67
Indexvariables 67
The importance of initialization 69
The read-until-sentinelidiom 69
Building a more practical application 71
Conditionalexecution and the if statement 74
3.4 An exercise in debugging 76
3.5 Formatted output 80
Format codes for printf 82
Controlling spacing alignmentand precision 83
3.6 Craing a program 86
Programming style 86
Designing for change 88
The #define mechanism 89
Summa 89
REVIEW QUESTIONS 91
PROGRAMMING EXERCISES 93
4 Statement Forms 99
4.1 Simple statements 100
Embedded assignments 102
Multiple assignments 102
Blocks 103
4.2 Control statements 104
4.3 Boolean data 105
Relational operators 106
Logical operators 107
Short-circuitevaluation 109
Flags 110
Avoiding redundancy in Booleanexpressions 110
An example of Boolean calculation 111
4.4 The if statement 112
Singleline if statements 114
Multiline if statements 114
The if-else statement 114
Cascading if statements 115
The ?: operator 115
4.5 The switch statement 117
4.6 The while statement 119
Using the while loop 120
Infinite loops 122
Solving the loop-and-half problem 123
4.7 The for statement 125
Nested for loops 126
The relationship between forand while 129
Using for with floating-point data 129
Summary 131
REVIEW QUESTIONS 132
PROGRAMMING EXERCISES 133
5 Functions 137
5.1 Using libra functions 138
5.2 Function declarations 140
5.3 Writing your own functions 141
The return statement 142 Pu 143
ing functions together with mainprograms 143
Functions involving internal control structures 145
Functions that return nonnumeric values 146
Predicate functions 148
A predicate function to test for string equality 149
5.4 Mechanics of the function-calling process 150
Parameter passing 151
Calling functions from withinother functions 156
5.5 Procedures 163
5.6 Stepwise refinement 165
Starting at the top 166
Implementing Printcalendar 167
Implementing PrintCalendarmonth 167
Completing the finalpieces 171
Summa 176
REVIEW QUESTIONS 177
PROGRAMMING EXERCISES 178
6 Algorithms 185
6.1 Testing for primality 186
A simple version of IsPrime 187
Verifying that a strategy representsan algorithm 187
Demonstrating the correctness of the IsPrimealgorithm 188
Improving algorithmic efficiency 189
Choosingbetween alternative implementations 192
6.2 Computing the greatest common divisor 193
Brute-force algorithms 194
Euclids algorithm 195
Defending thecorrectness of Euclids algorithm 195
Comparing the efficiency of theGCD algorithms 197
6.3 Numerical algorithms 197
Successive approximation 198
Reporting errors 200
6.4 Series expansion 201
Zenos paradox 201
Using a series expansion for the squareroot function 203
The Taylor series expansion for approximatinga square root 204
Implementing the Taylor series approximation 205
Staying within the radius of convergence 207
6.5 Specifying the size of numeric types 210
Integer types 210
Unsigned types 211
Floating-point types 212
Summary 212
REVIEW QUESTIONS 213
PROGRAMMING EXERCISES 214
PART TWOLibraries and Modular Development 219
7 Libraries and Interfaces:A Simple Graphics Library 221
7.1 The concept of an interface 222
Interfaces and header files 224
7.2 An introduction to the graphics library 225
The underlying model for graphics.h 225
The functions in thegraphics. h interface 227
Initializing the package 231
Drawingstraight lines 231
Drawing circles and arcs 233
Obtaining informa-tion about the graphics window 235
7.3 Building your own tools 235
Defining DrawBox 236
Defining DrawCenteredcircle 237
Switching between absolute and relative coordinates 239
The advantages of defining procedures 240
7.4 Solving a larger problem 240
Using stepwise refinement 241
Implementing the DrawHouseprocedure 242
looking for common patterns 243
Finishing thedecomposition 245
Summa 250
REVIEW QUESTIONS 251
PROGRAMMING EXERCISES 252
8 Designing Interfaces: A Random Number Library 259
8.1 Interface design 260
The importance of a unifying theme 261
Simplicity and the principleof information hiding 261
Meeting the needs of your clients 263
The advantages of general tools 263
The value of stability 264
8.2 Generating random numbers by computer 265
Deterministic versus nondeterministic behavior 265
Random versuspseudrandom numbers 265
Generating pseudrandom numbersin ANSI C 266
Changing the range of random numbers 267
Generalizing the problem 272
8.3 Saving tools in libraries 274
The contents of an interface 275
Writing the random.h interface 276
The random.c implementation 277
Constructing a client program 278
Initializing the random number generator 280
8.4 Evaluating the design of the random.h interface 283
Generating random real numbers 284
Simulating a probabilisticevent 285
Including header files in an interface 286
Completingthe implementation of the random-number package 286
8.5 Using the random-number package 286
Summa 290
REVIEW QUESTIONS 291
PROGRAMMING EXERCISES 292
9 Strings and Characters 301
9.1 The principle of enumeration 302
Representing enumeration types inside the machine 303
Representingenumeration types as integers 304
Defining new enumerationtypes 304
Operations on enumeration types 307
Scalar types 307
9.2 Characters 308
The data type char 308
The ASCII code 308
Character constants 310
Important propeies of the ASCII coding scheme 310
Special characters 311
Character arithmetic 312
The ctype.h interface 314
Controlstatements involving characters 315
Character input and output 316
9.3 Strings as abstract data 316
layered abstractions 317
The concept of an abstract type 319
9.4 The strlib.h interface 319
Determining the length of a string 320
Selecting characters froma string 321
Concatenation 321
Conveing characters to strings 322
Extracting parts of a string 323
Comparing one string with another 324
Searching within a string 325
Case conversion 327
Numericconversion 329
Efficiency and the strlib.h library 330
Summa 331
REVIEW QUESTIONS 332
PROGRAMMING EXERCISES 334
10 Modular Development 339
10.1 Pig Latin—a case study in modular development 342
Applying topown design 342
Using pseudocode 343
Implementing TranslateLine 344
Taking spaces and punctuationinto account 345
Refining the definition of a word 347
Designing the token scanner 348
Completing the TranslateLineimplementation 349
Specifying the scanner module interface 352
10.2 Maintaining internal state within a module 352
Global variables 355
The dangers of using global variables 356
Keeping variables private to a module 356
Initializing globalvariables 357
Private functions 359
10.3 Implementing the scanner abstraction 359
Summa 366
REVIEW QUESTIONS 366
PROGRAMMING EXERCISES 367
PART THREE 373
Compound Data Types 373
11 Arrays 375
11.1 Introduction to arrays 376
Array declaration 377
Array selection 378
Example of asimple array 379
Changing the index range 381
11.2 internal representation of data 382
Bits bytes and words 382
Memory addresses 383
The sizeof operator 385
Allocation of memoto variables 385
References to elements outside the array bound 386
11.3 Passing arrays as parameters 388
Generalizing the number of elements 390
The mechanics of arrayparameter transmission 392
Implementing Print iritegerArray andGetIntegerArray 394
Implementing ReverseIntegerArray 396
Implementing SwapIntegerElements 397
11.4 Using arrays for tabulation 398
11.5 Static initialization of arrays 404
Automatic determination of array size 408
Determining the size of aniniioiized array 409
Initialized arrays and scalarpes 409
11.6 Multidimensional arrays 410
Passing multidimensional arrays to functions 411
Initializing multidimensional arrays 412
Summary 413
REVIEW QUESTIONS 414
PROGRAMMING EXERCISES 416
12 Searching and Sor 425
12.1 Searching 426
Searching in an integer array 426
A more sophisticated exampleof searching 429
linear search 431
Binasearch 433
Relativeefficiency of the search algorithms 435
12.2 Sorting 437
Sorting an integer array 437
The selection sort algorithm 438
Evaluating the efficiency of selection so 442
Measuring the runningtime of a program 442
Analyzing the selection sort algorithm 445
Summary 446
REVIEW QUESTIONS 446
PROGRAMMING EXERCISES 447
13 Pointers 453
13.1 Using addresses as data values 455
13.2 Pointer manipulation in C 457
Declaring pointer variables in C 457
The fundamentalpointer operations 458
The special pointer NULL 461
13.3 Passing parameters by reference 461
Designing a SaapInteger function 465
Using call by reference toreturn multiple results 466
The danger of overusing call by reference 467
13.4 Pointers and arrays 468
Pointer arithmetic 469
New capabilities of the ++ and -- operators 473
Incrementing and decrementing pointers 475
The relationshipbetween pointers and arrays 476
13.5 Dynamic allocation 478
The type void 478
Dynamic arrays 480
Detecting errors inmalloc 481
Freeing memory 481
Summary 482
REVIEW QUESTIONS 483
PROGRAMMING EXERCISES 486
14 Strings Revisited 491
14.1 Conceptual representations of the type string 491
Strings as arrays 491
Strings as pointers 495
Strings as anabstract type 496
String parameters 497
String variables 497
Differences between pointer and array variables 499
Deciding ona strategy for string representation 502
14.2 The ANSI string libra 502
The strcpy function 504
The strncpy function 507
The strcat and st 507
cat functions 508
The strien strcrrp 510
and st 510
ccnp functions 510
The strchr strrchr andstrstr functions 510
An application of the ANSI string functions 510
14.3 Implementing the strlib libra 511
Implementing the pass-through functions 511
Implementing thestrlib allocation functions 514
Summa 516
REVIEW QUESTIONS 517
PROGRAMMING EXERCISES 517
15 Files 523
15.1 Text files 524
15.2 Using files in C 525
Declaring a FILE variable 526
Opening a file 526
PerformingI/O operations 527
Closing files 528
Standard files 528
15.3 Character l/O 529
Updating a file 531
Rereading characters in the input file 533
15.4 line-oriented l/O 536
15.5 Formatted l/O 539
The three forms of printf 539
The scanf functions 539
Reading strings with scanf 541
An example of formatted l/O 543
limitations on the use of scanf 546
Summary 547
REVIEW QUESTIONS 548
PROGRAMMING EXERCISES 549
16 Records 557
16.1 The concept of the data record 558
16.2 Using records in C 559
Defining a new structure type 560
Declaring structure variables 560
Record selection 561
Initializing records 561
Simple records 562
16.3 Combining records and arrays 563
16.4 Pointers to records 566
Defining a pointer-to-record type 566
Allocating storage forrecord data 568
Manipulating pointers to records 569
16.5 Building a database of records 570
Creating the employee database 570
Using the database 573
16.6 Designing a record-based application 574
The importance of using a database 575
Framing theproblem 575
Designing the internal representation 576
Designing the external structure 580
Coding the program 581
The value of a data-driven design 588
Summa 589
REVIEW QUESTIONS 592
PROGRAMMING EXERCISES 593
17 looking Ahead 601
17.1 Recursion 602
A simple illustration of recursion 603
The Factorial function 604
The recursive leap of faith 609
The recursive paradigm 610
Generating permutations 611
Thinking recursively 614
17.2 Abstract data types 614
The queue abstraction 615
Representing types in the queueabstraction 616
The queue. h interface 618
Implementingthe queue abstraction 620
Alternative implementation of thequeue abstraction 622
17.3 Analysis of algorithms 628
Evaluating algorithmic efficiency 628
Bignotation 629
Selectionsort revisited 630
Divide-andonquer strategies 631
Merging twoarrays 632
The merge sort algorithm 633
The computationalcomplexity of merge sort 635
Comparing quadratic and N log Nperformance 636
Summa 637
REVIEW QUESTIONS 638
PROGRAMMING EXERCISES 639
Appendix A. Summary of G Syntax and Structure 647
A.1 An oveiew of the compilation process 648
A.2 The C preprocessor 648
A.3 The lexical structure of C programs 650
A.4 Expressions 652
A.5 Statements 653
A.6 Functions 657
A.7 Declarations 658
A.8 Data types 659
A.9 ANSI libraries 662
Appendix B. Library Sources 669
Index 696