数据结构和编程设计 应用C语言 英文PDF|Epub|txt|kindle电子书版本网盘下载

数据结构和编程设计 应用C语言 英文PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

CHAPTER 1 Programming Principles1

1.1 Introduction2

1.2 The Game of Life4

1.2.1 Rules for the Game of Life4

1.2.2 Examples5

1.2.3 The Solution6

1.2.4 Life:The Main Program7

1.3 Programming Style10

1.3.1 Names10

1.3.2 Documentation and Format12

1.3.3 Refinement and Modularity14

1.4 Coding,Testing,and Further Refinement19

1.4.1 Stubs19

1.4.2 Counting Neighbors20

1.4.3 Input and Output21

1.4.4 Drivers24

1.4.5 Program Tracing25

1.4.6 Principles of Program Testing26

Pointers and Pitfalls30

Review Questions32

References for Further Study32

C32

Programming Principles33

The Game of Life33

CHAPTER 2 Introduction to Software Engineering34

2.1 Program Maintenance35

2.1.1 Review of the Life Program35

2.1.2 A Fresh Start and a New Method for Life37

2.2 Algorithm Development:A Second Version of Life40

2.2.1 Lists:Specifications for a Data Structure40

2.2.2 The Main Program45

2.2.3 Information Hiding47

2.2.4 Refinement:Development of the Subprograms48

2.2.5 Verification of Algorithms50

2.3 Coding55

2.3.1 The List Functions55

2.3.2 Error Processing56

2.3.3 Demonstration and Testing57

2.4 Coding the Life Functions62

2.5 Program Analysis and Comparison66

2.6 Conclusions and Preview68

2.6.1 The Game of Life68

2.6.2 Program Design70

2.6.3 C73

Pointers and Pitfalls75

Review Questions75

References for Further Study76

CHAPTER 3 Stacks and Recursion77

3.1 Stacks78

3.1.1 Introduction78

3.1.2 First Example:Reversing a Line79

3.1.3 Information Hiding80

3.1.4 Specifications for a Stack81

3.1.5 Implementation of Stacks83

3.1.6 Linked Stacks85

3.2 Introduction to Recursion91

3.2.1 Stack Frames for Subprograms91

3.2.2 Tree of Subprogram Calls91

3.2.3 Factorials:A Recursive Definition93

3.2.4 Divide and Conquer:The Towers of Hanoi95

3.3 Backtracking:Postponing the Work101

3.3.1 Solving the Eight-Queens Puzzle102

3.3.2 Example:Four Queens102

3.3.3 Backtracking103

3.3.4 Refinement:Choosing the Data Structures104

3.3.5 Analysis of Backtracking107

3.4 Principles of Recursion110

3.4.1 Designing Recursive Algorithms110

3.4.2 How Recursion Works111

3.4.3 Tail Recursion115

3.4.4 When Not to Use Recursion116

3.4.5 Guidelines and Conclusions120

Pointers and Pitfalls122

Review Questions124

References for Further Study124

CHAPTER 4 Queues and Linked Lists126

4.1 Definitions127

4.2 Implementations of Queues131

4.3 Circular Queues in C135

4.4 Application of Queues:Simulation139

4.4.1 Introduction139

4.4.2 Simulation of an Airport140

4.4.3 The Main Program142

4.4.4 Steps of the Simulation144

4.4.5 Pseudo-Random Numbers147

4.4.6 Sample Results149

4.5 Pointers and Linked Lists152

4.5.1 Introduction and Survey152

4.5.2 Pointers and Dynamic Memory in C155

4.5.3 The Basics of Linked Lists159

4.6 Linked Queues161

4.7 Application:Polynomial Arithmetic166

4.7.1 Purpose of the Project166

4.7.2 The Main Program166

4.7.3 Data Structures and Their Implementation171

4.7.4 Reading and Writing Polynomials172

4.7.5 Addition of Polynomials174

4.7.6 Completing the Project176

4.8 Abstract Data Types and Their Implementations179

4.8.1 Introduction179

4.8.2 General Definitions180

4.8.3 Refinement of Data Specification183

Pointers and Pitfalls185

Review Questions185

References for Further Study186

CHAPTER 5 General Lists187

5.1 List Specifications188

5.2 Implementation of Lists190

5.2.1 Contiguous Implementation190

5.2.2 Simply Linked Implementation191

5.2.3 Variation:Keeping the Current Position195

5.2.4 Doubly Linked Lists197

5.2.5 Comparison of Implementations200

5.3 Strings202

5.4 Application:A Text Editor205

5.4.1 Specifications205

5.4.2 Implementation207

5.5 Linked Lists in Arrays214

5.6 Generating Permutations223

Pointers and Pitfalls228

Review Questions229

References for Further Study230

CHAPTER 6 Searching231

6.1 Searching:Introduction and Notation232

6.2 Sequential Search235

6.3 Coatrooms:A Project241

6.3.1 Introduction and Specification241

6.3.2 Demonstration and Testing Programs244

6.4 Binary Search248

6.4.1 Algorithm Development249

6.4.2 The Forgetful Version249

6.4.3 Recognizing Equality252

6.5 Comparison Trees254

6.5.1 Analysis for n=10255

6.5.2 Generalization258

6.5.3 Comparison of Methods261

6.5.4 A General Relationship263

6.6 Lower Bounds264

6.7 Asymptotics269

6.7.1 Introduction269

6.7.2 The Big-O Notation270

6.7.3 Imprecision of the Big-O Notation273

6.7.4 Ordering of Common Functions274

Pointers and Pitfalls275

Review Questions276

References for Further Study276

CHAPTER 7 Sorting278

7.1 Introduction and Notation279

7.2 Insertion Sort280

7.2.1 Ordered Lists280

7.2.2 Sorting by Insertion281

7.2.3 Linked Version283

7.2.4 Analysis285

7.3 Selection Sort288

7.3.1 The Algorithm289

7.3.2 Contiguous Implementation290

7.3.3 Analysis291

7.3.4 Comparisons291

7.4 Shell Sort293

7.5 Lower Bounds295

7.6 Divide-and-Conquer Sorting298

7.6.1 The Main Ideas298

7.6.2 An Example299

7.7 Mergesort for Linked Lists304

7.7.1 The Functions304

7.7.2 Analysis of Mergesort306

7.8 Quicksort for Contiguous Lists311

7.8.1 The Main Function311

7.8.2 Partitioning the List312

7.8.3 Analysis of Quicksoft314

7.8.4 Average-Case Analysis of Quicksort316

7.8.5 Comparison with Mergesort318

7.9 Heaps and Heapsort321

7.9.1 Two-Way Trees as Lists322

7.9.2 Heapsort323

7.9.3 Analysis of Heapsort327

7.9.4 Priority Queues328

7.10 Review:Comparison of Methods330

Pointers and Pitfalls333

Review Questions334

References for Further Study334

CHAPTER 8 Tables and Information Retrieval336

8.1 Introduction:Breaking the lg n Barrier337

8.2 Rectangular Arrays337

8.3 Tables of Various Shapes340

8.3.1 Triangular Tables340

8.3.2 Jagged Tables342

8.3.3 Inverted Tables342

8.4 Tables:A New Abstract Data Type345

8.5 Application:Radix Sort348

8.5.1 The Idea348

8.5.2 Implementation349

8.5.3 Analysis352

8.6 Hashing353

8.6.1 Sparse Tables353

8.6.2 Choosing a Hash Function355

8.6.3 Collision Resolution with Open Addressing357

8.6.4 Collision Resolution by Chaining362

8.7 Analysis of Hashing367

8.8 Conclusions:Comparison of Methods373

8.9 Application:The Life Game Revisited374

8.9.1 Choice of Algorithm374

8.9.2 Specification of Data Structures374

8.9.3 The Main Program376

8.9.4 Functions377

Pointers and Pitfalls380

Review Questions381

References for Further Study382

CHAPTER 9 Binary Trees383

9.1 Introduction to Binary Trees384

9.1.1 Definitions384

9.1.2 Traversal of Binary Trees386

9.1.3 Linked Implementation of Binary Trees391

9.2 Binary Search Trees396

9.2.1 Ordered Lists and Implementations397

9.2.2 Treesearch398

9.2.3 Insertion into a Binary Search Tree401

9.2.4 Treesort404

9.2.5 Deletion from a Binary Search Tree406

9.3 Building a Binary Search Tree414

9.3.1 Getting Started415

9.3.2 Declarations and the Main Function416

9.3.3 Inserting a Node417

9.3.4 Finishing the Task418

9.3.5 Evaluation419

9.3.6 Random Search Trees and Optimality419

9.4 Height Balance:AVL Trees422

9.4.1 Definition423

9.4.2 Insertion of a Node424

9.4.3 Deletion of a Node431

9.4.4 The Height of an AVL Tree433

9.5 Splay Trees:A Self-Adjusting Data Structure438

9.5.1 Introduction438

9.5.2 Splaying Steps439

9.5.3 Splaying Algorithm442

9.5.4 Amortized Algorithm Analysis:Introduction446

9.5.5 Amortized Analysis of Splaying449

Pointers and Pitfalls455

Review Questions456

References for Further Study458

CHAPTER 10 Multiway Trees459

10.1 Orchards,Trees,and Binary Trees460

10.1.1 On the Classification of Species460

10.1.2 Ordered Trees461

10.1.3 Forests and Orchards463

10.1.4 The Formal Correspondence464

10.1.5 Rotations465

10.1.6 Summary466

10.2 Lexicographic Search Trees:Tries468

10.2.1 Tries468

10.2.2 Searching for a Key468

10.2.3 C Algorithm470

10.2.4 Insertion into a Trie470

10.2.5 Deletion from a Trie472

10.2.6 Assessment of Tries472

10.3 External Searching:B-Trees473

10.3.1 Access Time473

10.3.2 Multiway Search Trees474

10.3.3 Balanced Multiway Trees474

10.3.4 Insertion into a B-tree475

10.3.5 C Algorithms:Searching and Insertion477

10.3.6 Deletion from a B-tree483

10.4 Red-Black Trees492

10.4.1 Introduction492

10.4.2 Definition and Analysis493

10.4.3 Insertion495

10.4.4 C Insertion496

10.5 Tree-Structured Programs:Look-Ahead in Games501

10.5.1 Game Trees501

10.5.2 The Minimax Method502

10.5.3 Algorithm Development503

10.5.4 Refinement504

Pointers and Pitfalls507

Review Questions507

References for Further Study508

CHAPTER 11 Graphs510

11.1 Mathematical Background511

11.1.1 Definitions and Examples511

11.1.2 Undirected Graphs512

11.1.3 Directed Graphs512

11.2 Computer Representation513

11.3 Graph Traversal517

11.3.1 Methods517

11.3.2 Depth-First Algorithm518

11.3.3 Breadth-First Algorithm519

11.4 Topological Sorting520

11.4.1 The Problem520

11.4.2 Depth-First Algorithm522

11.4.3 Breadth-First Algorithm523

11.5 A Greedy Algorithm:Shortest Paths525

11.6 Graphs as Data Structures529

Pointers and Pitfalls531

Review Questions532

References for Further Study532

CHAPTER 12 Case Study:The Polish Notation533

12.1 The Problem534

12.1.1 The Quadratic Formula534

12.2 The Idea536

12.2.1 Expression Trees536

12.2.2 Polish Notation538

12.2.3 C Method539

12.3 Evaluation of Polish Expressions540

12.3.1 Evaluation of an Expression in Prefix Form540

12.3.2 C Conventions541

12.3.3 C Function for Prefix Evaluation542

12.3.4 Evaluation of Postfix Expressions542

12.3.5 Proof of the Program:Counting Stack Entries544

12.3.6 Recursive Evaluation of Postfix Expressions547

12.4 Translation from Infix Form to Polish Form551

12.5 An Interactive Expression Evaluator558

12.5.1 Overall Structure558

12.5.2 Representation of the Data560

12.5.3 Initialization and Auxiliary Tasks562

12.5.4 Translation of the Expression566

12.5.5 Evaluating the Expression574

12.5.6 Graphing the Expression576

References for Further Study578

APPENDIX A Mathematical Methods579

A.1 Sums of Powers of Integers580

A.2 Logarithms582

A.2.1 Definition of Logarithms583

A.2.2 Simple Properties583

A.2.3 Choice of Base584

A.2.4 Natural Logarithms584

A.2.5 Notation585

A.2.6 Change of Base586

A.2.7 Logarithmic Graphs586

A.2.8 Harmonic Numbers588

A.3 Permutations,Combinations,Factorials589

A.3.1 Permutations589

A.3.2 Combinations589

A.3.3 Factorials590

A.4 Fibonacci Numbers592

A.5 Catalan Numbers594

A.5.1 The Main Result594

A.5.2 The Proof by One-to-One Correspondences594

A.5.3 History596

A.5.4 Numerical Results597

References for Further Study598

APPENDIX B Removal of Recursion600

B.1 General Methods for Removing Recursion601

B.1.1 Preliminary Assumptions601

B.1.2 General Rules602

B.1.3 Indirect Recursion603

B.1.4 Towers of Hanoi603

B.1.5 Further Simplifications605

B.2 Recursion Removal by Folding606

B.2.1 Program Schemata606

B.2.2 Proof of the Transformation607

B.2.3 Towers of Hanoi:The Final Version609

B.3 Nonrecursive Quicksort611

B.4 Stackless Recursion Removal:Mergesort613

B.5 Threaded Binary Trees617

B.5.1 Introduction617

B.5.2 Threads619

B.5.3 Inorder and Preorder Traversal620

B.5.4 Insertion in a Threaded Tree621

B.5.5 Postorder Traversal623

References for Further Study627

APPENDIX C An Introduction to C628

C.1 Introduction629

C.1.1 Overview of a C Program629

C.2 C Elements629

C.2.1 Reserved Words629

C.2.2 Constants629

C.3 Types and Declarations631

C.3.1 Basic Types631

C.3.2 Arrays631

C.3.3 Enumerations631

C.3.4 Structures632

C.3.5 Unions632

C.3.6 Type Definitions with typedef634

C.4 Operators635

C.5 Control Flow Statements636

C.5.1 If-Else636

C.5.2 Switch636

C.5.3 Loops637

C.5.4 Break and Continue637

C.5.5 Goto637

C.6 Pointers638

C.6.1 Pointer to a Simple Variable638

C.6.2 Pointer to an Array639

C.6.3 Array of Pointers640

C.6.4 Pointer to Structures641

C.7 Functions642

C.7.1 Arguments to Functions:Call by Value642

C.7.2 Arguments to Functions:Call by Reference643

C.7.3 Function Prototypes and Include Files644

C.8 Pointers and Functions644

C.8.1 Pointer to a Function644

C.8.2 Functions that Return a Pointer645

C.8.3 Pointer to a Pointer as an Argument646

References for Further Study647

INDEX649