The art and science of C : a library-based introduction to computer science = C语言的科学和艺术 /

i introduction

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, i/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 mo numbers 26

the input phase 28, the computalion phase 30, the output phase 30

.2.3 perspectives on the programming process 32

2.4 data types 33

floatingpoint data 34, string data 34

2.5 expressions 37

constants 38, variables 39, assignment statements 41, operators

and operands 43, combining integers and floating-point numbers 44,

integer division and the remainder operator 45 precedence 45

applying precedence rubs 48 type conversion 48

summary 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 repealntimes idiom 65, iteration and loops 67 index

variables 67, the importance of initialization 69, the read untijsentinel

idiom 69 building a more practical application 71, conditional

execution and the if statement 74

3.4 an exercise in debugging 76

3.5 formatted output 80

format codes for printf 82, controlling spacing, alignment,

and precision 83

3.6 crafting a program 86

programming style 86, designing for change 88,

the #define mechanism 89

summary 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, shortcircuit

evaluation 109, flags 110, avoiding redundancy in boolean

expressions 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 1 17

4.6 the while statement 119

using the while loop 120, infinite loops 122

solving the loopandahalf problem 123

4.7 the for statement 125

nested for loops 126, the relationship beiween for

and while 129, using for with floatingpoint data 129

summary 131

review questions 132

programming exercises 133

5 functions 137

5.1 using library functions 138

5.2 function declarations 140

5.3 writing your own functions 141

the return statement 142, putting functions together with main

programs 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 within

other functions 156

5.5 procedures 163

5.6 stepwise refinement 165

starting at the top 166, implementing printcalendar t67,

implementing printcalendarmonth 167, completing the final

pieces 171

summary 176

review questions 177

programming exercises 1 78

6 algorithms 185

6.1 testing for primality 186

a simple version of tsprime 187, verifying that a strategy represents

an algorithm 187, demonstrating the correctness of the isprime

algorithm 188, improving algorithmic efficiency 189, choosing

between alternative implementations 192

6.2 computing the greatest common divisor 193

brute-force algorithms 194, euclid's algorithm 195, defending the

correctness of euclid's algorithm 195, comparing the efficiency of the

gcd algorithms 197

6.3 numerical algorithms 197

successive approximation 198, reporting errors 200

6.4 series expansion 201

zeno's paradox 201, using a series expansion for the square

root function 203, the taylor series expansion for approximating

a 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 two

libraries 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 the

graphics.h interface 227, initializing the package 231, drawing

straight 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 drawhouse

procedure 242, looking for common patterns 243, finishing the

decomposition 245

summary 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 principle

of 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 versus

pseudorandom numbers 265, generating pseudo-random numbers

in 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 probabilistic

event 285, including header files in an interface 286, completing

the implementation of the randomnumber package 286

8.5 using the random-number package 286

summary 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, representing

enumeration types as integers 304, defining new enumeration

types 304, operations on enumeration types 307, scalar types 307

9.2 characters 308

the data type char 308, the ascii code 308, character conslonts 31 o,

important properties of the ascii coding scheme 31 o, special characters

311, character arithmetic 312, the ctype.h interface 3t4, control

statements involving characters 315, character input and output 316

9.3 strings as abstract data 316

layered abstractions 317, the concept of an abstract lype 319

9.4 the strlib.h interface 319

determining the length of a string 320, selecting characters from

a string 321, concatenation 321, converting characters to strings 322,

extracting parts of a string 323, comparing one string with another 324,

searching within a string 325, case conversion 327, numeric

conversion 329, efficiency and the strlib.h library 330

summary 331

review questions 332

programming exercises 334

10 modular development 339

10.1 pig latin---a case study in modular development 342

applying topdown design 342, using pseudocode 343,

implementing translateline 344, taking spaces and punctuation

into account 345, refining the definition of a word 347,

designing the token scanner 348, completing the translateline

implementation 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 global

variables 357, private functions 359

10.3 implementing the scanner abstraction 359

summary 366

review questions 366

programming exercises 367

part three

compound data types 373

11 arrays 375

11.1 introduction to arrays 376

array declaration 377, array selection 378, example of a

simple 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 memory to 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 array

parameter transmission 392, implementing printintegerarray and

getintegerarray 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 an

initialized array 409, initialized arrays and scalar types 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 sorting 425

12.1 searching 426

searching in an integer array 426, a more sophisticated example

of searching 429, linear search 431, binary search 433, relative

efficiency of the search algorithms 435

12.2 sorting 437

sorting on integer array 437, the selection sort algorithm 438,

evaluating the efficiency of selection sort 442, measuring the running

time 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 asdata values 455

13.2 pointer manipulation in c 457

declaring pointer variables in c 457, the fundamental

pointer operations 458, the special pointer null 461

13.3 passing parameters by reference 461

designing a swapinteger function 465, using call by reference to

return 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 relationship

between pointers and arrays 476

13.5 dynamic allocation 478

the type void * 478, dynamic arrays 480, detecting errors in

malloc 481, freeing memory 481

summary 482

review questions 483

programming exercises 486

14 strings revisited 491

14.1 conceptual representations of the type string 492

strings as arrays 491, strings as pointers 495, strings as an

abstract type 496, string parameters 497, string variables 497,

differences between pointer and array variables 499, deciding on

a strategy for string representation 502

14.2 the ansi string library 502

the strcpy function 504, the strncpy function 507,

the strcat and strncat functions 508, the strlen, strcmp,

and strncmp functions 509, the strchr, strrchr, ond

strstr functions 510, an application of the ansi string functions 510

14.3 implementing the strlib library 511

implementing the passthrough functions 511 implementing the

strlib allocation functions 514

qi

summary 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 o file 526, performing

i/o operations 527, closing files 528, standard files 528

'15.3 character i/0 529

updating a file 531, rereading characters in the input file 533

15.4 line-oriented i/0 536

15.5 formatted i/0 539

the three forms of printf 539, the scanf functions 539,

reading strings with scanf 541, an example of formatted i/0 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 for

record 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 the

problem 575, designing the internal representation 576,

designing the external structure 580, coding the program 581,

the value of a data-driven design 588

summary 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 queue

abstraction 616, the queue.h interface 618, implementing

the queue abstraction 620, alternative implementation of the

queue abstraction 622

17.3 analysis of algorithms 628

evaluating algorithmic efficiency 628, big-o notation 629, selection

sort revisited 630, divideandconquer strategies 631, merging two

arrays 632, the merge sort algorithm 633, the computational

complexity of merge sort 635, comparing quadratic and n log n

performance 636

summary 637

review questions 638

programming exercises 639

appendix a. summary of c syntax and structure 647

a.1 an overview 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