《工作类型：数据结构与算法的 C++ 实现》

PART ONEINTRODUCTION3

1PRELIMINARIES3

1.1ADTs:ABSTRACTION AND ENCAPSULATION4

Abstraction5

Reuse and Encapsulation7

ADTs,OOP,and Things to Come7

1.2 ADT:INTEGERARRAY8

1.3IMPLEMENTATION13

Defining Integer Arrays13

1.4COMPUTER SCIENCE INTERLUDE:ASSERTIONS AND VERIFICATION18

Assertions18

Verification19

1.5APPLICATION:MULTIPRECISION ARITHMETIC23

Declaring the Number Class25

Defining the Number Class27

1.6 SUMMARY36

1.7 EXERCISES36

1.8EXPLORATIONS44

Representation of Integers44

Bit Vectors45

PART TWOLINEAR STRUCTURES45

2LISTS49

2.1ADT:LIST50

Parametrized Classes53

2.2IMPLEMENTATIONS55

Arrays55

Linked Lists63

2.3COMPARING IMPLEMENTATIONS75

Space75

Time76

Comprehensibility77

Trade-Offs78

2.4COMPUTER SCIENCE INTERLUDE:MEASURES OF EFFICIENCY78

Algorithms79

Big-O81

Order Arichmetic83

Timing Functions85

2.5APPLICATION:MEMORY MANAGEMENT89

Allocation92

Deallocation94

Compaction98

2.6 SUMMARY100

2.7 EXERCISES100

2.8EXPLORATIONS111

Sorted Lists111

Self-Organizing Lists115

3STRINGS117

3.1ADT:STRING117

(S)trings,(s)trings,and Arrays118

Lexicographic Order121

Declaring Strings122

3.2IMPLEMENTATION124

Efficiency130

3.3 APPLICATION:STRING MATCHING132

3.4 SUMMARY139

3.5 EXERCISES140

3.6EXPLORATIONS144

Advanced Pattern Matching144

4OTHER LINEAR STRUCTURES146

4.1 ADT:STACK146

4.2IMPLEMENTATIONS OF STACK151

Efficiency Issues151

Sacks as a Derived Class152

Sacks from Scratch153

4.3 APPLICATION:POSTFIX ARITHMETIC154

4.4 ADT:QUEUE157

4.5IMPLEMENTATIONS OF QUEUE158

Queues as Linked Lists159

Circular Arrays and Queues160

4.6APPLICATION(CONTINUED):INFIX TO POSTFIX CONVERSION163

Verification166

4.7 SUMMARY166

4.8 EXERCISES167

4.9EXPLORATIONS173

The Electronic Labyrintn173

Operating System Simulation178

PART THREE NONLINEAR STRUCTURES178

5RECURSION183

5.1RECURSIVE ALGORITHMS183

Induction and Recursion190

5.2 TIMING RECURSIVE ALGORITHMS191

5.3 COMPUTER SCIENCE INTERLUDE:DESIGN OF ALGORITHMS196

5.4RECURSIVE DATA STRUCTURES202

General Lists and LISP204

5.5 SUMMARY211

5.6 EXERCISES212

5.7EXPLORATIONS219

Quicksort219

6TREES223

6.1 THE STRUCTURE OF TREES224

6.2 ADT:BINARYTREE228

6.3 BINARY TREE TRAVERSALS231

6.4 IMPLEMENTATION OF BINARYTREE236

6.5 COMPUTER SCIENCE INTERLUDE:PARSE TREES240

6.6DATA-ORDERED BINARY TREES242

Binary Search Trees244

Application:Treesort251

6.7 SUMMARY252

6.8 EXERCISES253

6.9EXPLORATIONS257

Threaded Trees257

Preamble:Tree Applications259

Huffman Codes261

Tries265

7SPECIALIZED TREES268

7.1BALANCED TREES269

AVL Trees270

Efficiency and Verification277

7.2B-TREES277

k-ary Trees,Again278

B-Trees Explained279

Application:External Storage289

7.3 SUMMARY293

7.4 EXERCISES294

8GRAPHS AND DIGRAPHS297

8.1 ADT:GRAPH298

8.2IMPLEMENTATIONS OF GRAPH302

Adjacency Matrices302

Adjacency Lists and Edge Lists305

8.3GRAPH TRAVERSALS311

Depth-First Traversals311

Breadth-First Traversals312

Spanning Trees314

8.4 APPLICATION:MINIMUM SPANNING TREES317

8.5DIRECTED GRAPHS319

Application:Cheapest Paths320

8.6 COMPUTER SCIENCE INTERLUDE:COMPUTATIONAL COMPLEXITY326

8.7 SUMMARY330

8.8 EXERCISES331

8.9EXPLORATIONS336

Topological Sorting336

Counting Paths338

9UNORDERED COLLECTION342

9.1 ADT:SET342

9.2IMPLEMENTATIONS OF SET345

Bit Vectors345

Sets Represented by Lists348

9.3ADT:DICTIONARY352

Associations352

9.4HASHING356

Open Hashing362

Time and Space Estimates363

9.5 APPLICATION:A PROBABILISTIC SPELLING CHECKER366

9.6ADT:PRIORITYQUEUE369

Application:Heapsort375

9.7 SUMMARY376

9.8 EXERCISES377

9.9EXPLORATIONS380

Hashing,Coninued380

The Disjoint Set ADT383

Tree Representations of Disjoint Set384

Application:Minimum Spanning Trees,Revisited389

10TRAVESTY:PUTTING IT ALL TOGETHER391

10.1 THE PROBLEM391

10.2THE SOLUTIONS396

Arrays397

Hashing401

Tries408

A Guest Author416

10.3APPLICATIONS416

Reactive Keyboards417

Coding,Once Again418

10.4 SUMMARY419

10.5 EXERCISES420

10.6EXPLORATIONS422

Long Strings422

APPENDIX A:A Pascal-C++ Dictionary425

A.1Information426

A.2 Program Structure428

A.3 Statements430

A.4 Compound Data Types434

A.5 Pointers and References435

A.6 Two Sample Programs437

APPENDIX B:Topics in Mathematics444

B.1Exponential and Logarithmic Functions444

B.2 Induction449

B.3 Counting Techniques451

B.4 Exercises455

APPENDIX C:Random Numbers and Simulation459

C.1RandomNumbers460

C.2 Probability Distributions462

C.3 Selection Algorithms469

C.4 Exercises473

APPENDIX D:Specifications of the ADTs Used in the Text475

Index487