工作类型：数据结构与算法的 C++ 实现PDF电子书下载

PART ONE INTRODUCTION 3

1 PRELIMINARIES 3

1.1 ADTs:ABSTRACTION AND ENCAPSULATION 4

Abstraction 5

Reuse and Encapsulation 7

ADTs,OOP,and Things to Come 7

1.2 ADT:INTEGERARRAY 8

1.3 IMPLEMENTATION 13

Defining Integer Arrays 13

1.4 COMPUTER SCIENCE INTERLUDE:ASSERTIONS AND VERIFICATION 18

Assertions 18

Verification 19

1.5 APPLICATION:MULTIPRECISION ARITHMETIC 23

Declaring the Number Class 25

Defining the Number Class 27

1.6 SUMMARY 36

1.7 EXERCISES 36

1.8 EXPLORATIONS 44

Representation of Integers 44

Bit Vectors 45

PART TWO LINEAR STRUCTURES 45

2 LISTS 49

2.1 ADT:LIST 50

Parametrized Classes 53

2.2 IMPLEMENTATIONS 55

Arrays 55

Linked Lists 63

2.3 COMPARING IMPLEMENTATIONS 75

Space 75

Time 76

Comprehensibility 77

Trade-Offs 78

2.4 COMPUTER SCIENCE INTERLUDE:MEASURES OF EFFICIENCY 78

Algorithms 79

Big-O 81

Order Arichmetic 83

Timing Functions 85

2.5 APPLICATION:MEMORY MANAGEMENT 89

Allocation 92

Deallocation 94

Compaction 98

2.6 SUMMARY 100

2.7 EXERCISES 100

2.8 EXPLORATIONS 111

Sorted Lists 111

Self-Organizing Lists 115

3 STRINGS 117

3.1 ADT:STRING 117

(S)trings,(s)trings,and Arrays 118

Lexicographic Order 121

Declaring Strings 122

3.2 IMPLEMENTATION 124

Efficiency 130

3.3 APPLICATION:STRING MATCHING 132

3.4 SUMMARY 139

3.5 EXERCISES 140

3.6 EXPLORATIONS 144

Advanced Pattern Matching 144

4 OTHER LINEAR STRUCTURES 146

4.1 ADT:STACK 146

4.2 IMPLEMENTATIONS OF STACK 151

Efficiency Issues 151

Sacks as a Derived Class 152

Sacks from Scratch 153

4.3 APPLICATION:POSTFIX ARITHMETIC 154

4.4 ADT:QUEUE 157

4.5 IMPLEMENTATIONS OF QUEUE 158

Queues as Linked Lists 159

Circular Arrays and Queues 160

4.6 APPLICATION(CONTINUED):INFIX TO POSTFIX CONVERSION 163

Verification 166

4.7 SUMMARY 166

4.8 EXERCISES 167

4.9 EXPLORATIONS 173

The Electronic Labyrintn 173

Operating System Simulation 178

PART THREE NONLINEAR STRUCTURES 178

5 RECURSION 183

5.1 RECURSIVE ALGORITHMS 183

Induction and Recursion 190

5.2 TIMING RECURSIVE ALGORITHMS 191

5.3 COMPUTER SCIENCE INTERLUDE:DESIGN OF ALGORITHMS 196

5.4 RECURSIVE DATA STRUCTURES 202

General Lists and LISP 204

5.5 SUMMARY 211

5.6 EXERCISES 212

5.7 EXPLORATIONS 219

Quicksort 219

6 TREES 223

6.1 THE STRUCTURE OF TREES 224

6.2 ADT:BINARYTREE 228

6.3 BINARY TREE TRAVERSALS 231

6.4 IMPLEMENTATION OF BINARYTREE 236

6.5 COMPUTER SCIENCE INTERLUDE:PARSE TREES 240

6.6 DATA-ORDERED BINARY TREES 242

Binary Search Trees 244

Application:Treesort 251

6.7 SUMMARY 252

6.8 EXERCISES 253

6.9 EXPLORATIONS 257

Threaded Trees 257

Preamble:Tree Applications 259

Huffman Codes 261

Tries 265

7 SPECIALIZED TREES 268

7.1 BALANCED TREES 269

AVL Trees 270

Efficiency and Verification 277

7.2 B-TREES 277

k-ary Trees,Again 278

B-Trees Explained 279

Application:External Storage 289

7.3 SUMMARY 293

7.4 EXERCISES 294

8 GRAPHS AND DIGRAPHS 297

8.1 ADT:GRAPH 298

8.2 IMPLEMENTATIONS OF GRAPH 302

Adjacency Matrices 302

Adjacency Lists and Edge Lists 305

8.3 GRAPH TRAVERSALS 311

Depth-First Traversals 311

Breadth-First Traversals 312

Spanning Trees 314

8.4 APPLICATION:MINIMUM SPANNING TREES 317

8.5 DIRECTED GRAPHS 319

Application:Cheapest Paths 320

8.6 COMPUTER SCIENCE INTERLUDE:COMPUTATIONAL COMPLEXITY 326

8.7 SUMMARY 330

8.8 EXERCISES 331

8.9 EXPLORATIONS 336

Topological Sorting 336

Counting Paths 338

9 UNORDERED COLLECTION 342

9.1 ADT:SET 342

9.2 IMPLEMENTATIONS OF SET 345

Bit Vectors 345

Sets Represented by Lists 348

9.3 ADT:DICTIONARY 352

Associations 352

9.4 HASHING 356

Open Hashing 362

Time and Space Estimates 363

9.5 APPLICATION:A PROBABILISTIC SPELLING CHECKER 366

9.6 ADT:PRIORITYQUEUE 369

Application:Heapsort 375

9.7 SUMMARY 376

9.8 EXERCISES 377

9.9 EXPLORATIONS 380

Hashing,Coninued 380

The Disjoint Set ADT 383

Tree Representations of Disjoint Set 384

Application:Minimum Spanning Trees,Revisited 389

10 TRAVESTY:PUTTING IT ALL TOGETHER 391

10.1 THE PROBLEM 391

10.2 THE SOLUTIONS 396

Arrays 397

Hashing 401

Tries 408

A Guest Author 416

10.3 APPLICATIONS 416

Reactive Keyboards 417

Coding,Once Again 418

10.4 SUMMARY 419

10.5 EXERCISES 420

10.6 EXPLORATIONS 422

Long Strings 422

APPENDIX A:A Pascal-C++ Dictionary 425

A.1 Information 426

A.2 Program Structure 428

A.3 Statements 430

A.4 Compound Data Types 434

A.5 Pointers and References 435

A.6 Two Sample Programs 437

APPENDIX B:Topics in Mathematics 444

B.1 Exponential and Logarithmic Functions 444

B.2 Induction 449

B.3 Counting Techniques 451

B.4 Exercises 455

APPENDIX C:Random Numbers and Simulation 459

C.1 RandomNumbers 460

C.2 Probability Distributions 462

C.3 Selection Algorithms 469

C.4 Exercises 473

APPENDIX D:Specifications of the ADTs Used in the Text 475

Index 487