数据结构习题与解答 C++语言描述 英文版PDF电子书下载

Chapter 1 Review of C++ 1

1.1 THE STANDARD C++PROGRAMMING LANGUAGE 1

1.2 CONDITIONALS 3

1.3 OPERATORS 5

1.4 ITERATION 6

1.5 FUNCTIONS 8

1.6 STRINGS 10

1.7 FILES 12

2.1 POINTERS 25

Chapter 2 Pointers and Arrays 25

2.2 DERIVED TYPES 26

2.3 REFERENCES 27

2.4 PASSING BY REFERENCE 27

2.5 NULL POINTER EXCEPTIONS 29

2.6 THE new AND delete OPERATORS 29

2.7 ARRAYS 31

2.8 DYNAMIC ARRAYS 32

2.9 PASSING AN ARRAY TO A FUNCTION 32

2.10 MULTIDIMENSIONAL ARRAYS 33

3.1 A Point CLASS 47

Chapter 3 Classes 47

3.2 INSTANCESIMPLICIT ARGUMENTS,AND THE this POINTER 49

3.3 COMPILING CLASSES AND THEIR CLIENT PROGRAMS 50

3.4 FRIEND FUNCTIONS 53

3.5 A Line CLASS 54

3.6 A CLASS FOR RANDOM NUMBERS 56

3.7 STATIC MEMBERS 57

3.8 COMPOSITION 59

3.9 INHERITANCE 61

4.1 THE FACTORIAL FUNCTION 76

Chapter 4 Recursion 76

4.2 TRACING A RECURSIVE CALL 77

4.3 THE FIBONACCI SEQUENCE 77

4.4 BINOMIAL COEFFICIENTS 78

4.5 THE EUCLIDEAN ALGORITHM 79

4.6 INDUCTIVE PROOF OF CORRECTNESS 80

4.7 COMPLEXITY ANALYSIS OF RECURSIVE ALGORIHMS 81

4.8 DYNAMIC PROGRAMMING 82

4.9 THE TOWERS OF HANOI 82

4.10 MUTUAL RECURSION 84

5.2 USING stack OBJECTS 92

Chapter 5 Stacks 92

5.1 THE stack INTERFACE 92

5.3 APPLICATIONS OF STACKS 93

5.4 REMOVING RECURSION 96

5.5 CONTIGUOUS IMPLEMENTATION 97

5.6 LINKED IMPLEMENTATION 100

Chapter 6 Queues 110

6.1 THE queue INTERFACE 110

6.2 USING queue OBJECTS 110

6.3 APPLICATIONS OF QUEUES 112

6.4 CONTIGUOUS IMPLEMENTATION 115

6.5 LINKED IMPLEMENTATION 118

Chapter 7 Lists 127

7.1 THE list INTERFACE 127

7.2 USING list OBJECTS 128

7.3 ITERATORS 129

7.4 APPLICATIONS 130

7.5 CIRCULAR LISTS 134

7.6 ORDERED LISTS 136

7.7 AN UNBOUNDED Integer CLASS 137

7.8 IMPLEMENTION OF THE List CLASS 142

Chapter 8 Tables 155

8.1 THE STANDARD pair TYPE 155

8.2 APPLICATIONSUSINGTHE map CLASSTEMPLATE 157

8.3 HASH TABLES 161

8.4 HASH FUNCTIONS 165

8.5 SEPARATE CHAINING 167

Chapter 9 Trees 174

9.1 TREE TERMINOLOGY 174

9.2 DECISION TREES AND TRANSITION DIAGRAMS 176

9.3 TREE TRAVERSAL ALGORITHMS 178

9.4 A Tree CLASS INTERFACE 180

9.5 IMPLEMENTATION OF THE Tree CLASS 182

Chapter 10 Binary Trees 200

10.1 DEFINITIONS 200

10.2 COUNTING BINARY TREES 201

10.3 FULL BINARY TREES 202

10.4 IDENTITY,EQUALITY,AND ISOMORPHISM 203

10.5 COMPLETE BINARY TREES 204

10.6 TREE TRAVERSALS 206

10.7 EXPRESSION TREES 208

10.9 A BinaryTree CLASS INTERFACE 210

10.8 FORESTS 210

10.10 IMPLEMENTATION OF THE BinaryTree CLASS 213

Chapter 11 Search Trees 224

11.1 BINARY SEARCH TREES 224

11.2 IMPLEMENTATION OF BINARY SEARCH TREES 225

11.3 PERFORMANCE CHARACTERISTICS OF BINARY SEARCH TREES 228

11.4 AVL TREES 228

12.2 THE NATURAL MAPPING 235

Chapter 12 Heaps and Priority Queues 235

12.1 HEAPS 235

12.3 INSERTION INTO A HEAP 236

12.4 REMOVAL FROM A HEAP 237

12.5 PRIORITY QUEUES 238

12.6 USING priority_queue OBJECTS 238

12.7 USING A HEAP TO IMPLEMENT A PriorityQueue CLASS TEMPLATE 239

12.8 APPLICATIONS OF PRIORITY QUEUES 241

13.1 PRELIMINARIES 248

13.2 THE BUBBLE SORT 248

Chapter 13 Sorting 248

13 3 THE SELECTION SORT 250

13.4 THE INSERTION SORT 251

13.5 THE MERGE SORT 252

13.6 THE QUICK SORT 255

13.7 HEAPS 256

13.8 THE HEAP SORT 257

13.9 THE SHELL SORT 261

13.10 THE SPEED LIMIT FOR EXCHANGE SORTS 262

Appendix A References 268

B.2 LOGARITHMS 275

Appendix B Essential Mathematics 275

B.1 THE FLOOR AND CEILING FUNCTIONS 275

B.3 THE FIRST PRINCIPLE OF MATHEMATICAL INDUCTION 276

B.4 THE SECOND PRINCIPLE OF MATHEMATICAL INDUCTION 277

B.5 GEOMETRIC SERIES 278

B.6 SUMMATION FORMULAS 278

B.7 ASYMPTOTIC COMPLEXITY CLASSES 279

B.8 HARMONIC NUMBERS 279

B.9 STIRLING'S FORMULA 281

B.10 FIBONACCI NUMBERS 281

B.11 THE GOLDEN MEAN 282

B.12 THE EUCLIDEAN ALGORITHM 283

Appendix C Standard Container Classes 285

C.1 THE vector CLASS TEMPLATE 285

C.2 THE deque CLASS TEMPLATE 290

C.3 THE stack CLASS TEMPLATE 290

C.4 THE queue CLASS TEMPLATE 291

C.5 THE priority_queue CLASS TEMPLATE 291

C.6 THE list CLASS TEMPLATE 292

C.7 THE map CLASS TEMPLATE 294

C.8 THE set CLASS TEMPLATE 296

Appendix D Generic Algorithms 299

Appendix E Example Classes 328

E.1 A BinaryTree CLASS 328

E.2 A BinarySearchTree CLASS 335

E.3 A Card CLASS 336

E.4 A Concordance CLASS 339

E.5 A Date CLASS 340

E.6 A Deck CLASS 347

E.7 A Hand CLASS 348

E.9 A HashTable CLASS TEMPLATE 349

E.8 A Hash FUNCTION STRUCTURE TEMPLATE 349

E.10 A Line CLASS 351

E.11 A List CLASS TEMPLATE 353

E.12 A Matrix CLASS TEMPLATE 358

E.13 AN OrderedList CLASS 360

E.14 A Peraon CLASS 361

E.15 A Point CLASS 363

E.16 A Polynomial CLASS 367

E.17 A PriorityQueue CLASS TEMPLATE 372

E.18 A Purse CLASS 374

E.19 A Queue CLASS 376

E.20 A Random CLASS 377

E.21 A RandomLine CLASS 378

E.22 A RandomPoint CLASS 378

E.23 A Ratio CLASS 379

E.24 A Rational CLASS 381

E.25 A SelforganizingList CLASS 384

E.26 A StackCLASS TEMPLATE 384

E.27 A Tree CLASS 386

Index 399