The art and science of C a library-based introduction to computer science = C语言的科学和艺术 （英文版）PDF电子书下载

1 Introduction 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

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

Operators and operands 43

Combining integers and floating-point numbers 44

Integer division and the remainder operator 45

Precedence 45

Applying precedence rules 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 repeat-N-times idiom 65

Iteration and loops 67

Index variables 67

The importance of initialization 69

The read-until-sentinel 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

Shortircuit evaluation 109

Flags 110

Avoiding redundancy in Boolean expressions 110

An example of Boolean calculation 111

4.4 The if statement 112

Single-line 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 loopand-a-half problem 123

4.7 The for statement 125

Nested for loops 126

The relationship between for and while 129

Using for with floating-point 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 167

Implementing PrintCalendarMonth 167

Completing the final pieces 171

Summary 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 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 pseudo-random 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 random-number 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 constants 310

Important properties of the ASCII coding scheme 310

Special characters 311

Character arithmetic 312

The ctype.h interface 314

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 type 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 top-down 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 Print IntegerArray and GetIntegerArray 394

Implementing Reverse IntegerArray 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 an 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 as data 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，and strstr functions 510

An application of the ANSI string functions 510

14.3 Implementing the strlib library 511

Implementing the pass-through functions 511

Implementing the strlib allocation functions 514

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 a file 526

Performing I/O operations 527

Closing files 528

Standard files 528

15.3 Character I/O 529

Updating a file 531

Rereading characters in the input file 533

15.4 Line-oriented I/O 536

15.5 Formatted I/O 539

The three forms of printf 539

The scanf functions 539

Reading strings with scanf 541

An example of formatted I/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 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

Divide-and-conquer 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