CHAPTER l
Classes in C++ 1
1. 1 Classes 2
CHAPTER 2
Storage Structures for Container
Classes 3s
2. 1 Pointers 36
2. 2 Arrays 41
2. 3 Container Classes 42
CHAPIER 3
Introduction to Software
Engineering 63
3. 1 The Software Developmental Life Cycle 64
3. 2 Problem Analysis 64
3. 3 Program Design 67
3. 4 Program Implementation 71
3 .5 Program Maintenance 87
CHAPTER 4
4. 1 Introduction 94
4. 2 Factorials 94
4. 3 Decimal-to-Binary 99
4. 4 Towers of Hanoi 103
4. 5 Backtracking 112
4. 6 Binary Search 125
4. 7 Generating Permutations 135
4. 8 Indirect Recursion 144
4. 9 The Cost of Recursion 145
Summary 146
Exercises 147
Programming Project 4.1 : An Iterative Version of
Towers of Hanoi 154
Programming Project 4.2: The Eight-Queens
Problem 156
Programming Project 4.3: A Knight's Tour 158
CHAPTER 5
5. 1 The Standard Template Library 164
5. 2 Vectors 165
5. 3 A Vector Application: High-Precision
Arithmetic 184
5. 4 Deques 190
5. 5 A Deque Application: Very Long
Integers 198
Summary 199
Exercises 199
Programming Project 5.1 : Extending the
very_long_int Class 203
Programming Project 5.2: An Alternative
Implementation of the deque Class 204
CHAPTER 6
Lists 205
6. 1 Lists 206
6. 2 List Application: A Line Editor 228
Summary 240
Exercises 241
Programming Project 6.1: Extending the Editor
Class 244
Programming Project 6.2: An Alternate Design and
Implementation of the list Class 251
CHAPTER 7
Queues and Staeks 253
7. 1 Queues 254
7. 2 Computer Simulation 261
7. 3 A Queue Application: A Simulated Car
Wash 264
7. 4 Stacks 274
7. 5 Stack Application 1: How Recursion Is
Implemented 277
7. 6 Stack Application 2: Conveting Infix to
Postfix 285
Summary 295
Exercises 295
Programming Project 7.1: Extending the Car Wash
Application 298
Programming Project 7.2: Evaluating a
Condition 300
Programming Project 7.3: An Iterative Maze
Search 304
Programming Project 7.4: An Alternate Design of
the queue Class 305
CHAPTER 8
Binary Trees and Binary Search
8. 1 Definition and Properties 308
8. 2 Binary Search Trees 324
Summary 345
Exercises 346
Programming Project 8. 1 : Alternative
Implementation of the BinSearch Tree
Class 350
CHAPTERg 9
AVL Ttees 353
9. 1 Balanced Binary Search Trees 354
9. 2 Rotations 354
9. 3 AVL Trees 358
9. 4 AVL Tree Application: A Simple Spell-
Checker 380
Summary 383
Exercises 384
Programming Project 9.1: The erase Method in the
AVLTree Class 388
Programming Project 9.2: Enhancing the
SpeIIChecker Project 389
CHAPTER 10
Red-Black Trees 391
10. 1 Red-Black Trees 392
10. 2 The Standard Template Library's Associative
Containers 422
10. 3 Set Application: Spell-Checker,
Revisited 425
Summary 432
Exercises 432
Programming Project 10.1: A Simple
Thesauras 436
Programming Project 10.2: Building a
Concordance 437
CHAPTER 11
Priority Queues
11.1 Introduction 440
11.2 Application of Priority Queues: Huffman
Codes 456
Summary 469
Exercises 469
Programming Project 11.1: Decoding a
Message 473
CHAPTER 12
Sorting 477
12.1 Introduction 478
12.2 How Fast Can We son? 481
12.3 Fast Sorts 483
Summary 501
Exercises 501
Programming Project 12.1: Sorting a File 509
CHPTER 13
Searehing and the Hash
Classe
13.1 A Framework to Analyze Searching 514
13.2 Review of Searching 514
13.3 The hash_map Class 517
13.4 The hash set Class 540
13.5 Open-Address Hashing 540
Summary 557
Exercises 558
Programming Project 13.1: A Run-Time
Comparison of Chaining and Double Hashing
in Building a Symbol Table 561
CHAPTER 14
14. 1 Undirected Graphs 564
14. 2 Directed Graphs 567
14. 3 Trees 568
14. 4 Networks 569
14. 5 Oraph Algorithms 571
14. 6 Developing a Network Class 588
14. 7 The network Class 589
14.8 Backtracking through a Network 607
Summary 610
Exercises 610
Programming Project 14.1 : Completing the
Adjacency-Matrix Implementation 614
Programming Project 14.2: Backtracking through
a Network 615
APPENDIX 1
A1. 1 Introduction 619
A1. 2 Functions and Sequences 619
A1. 3 Sums and Products 620
A1. 4 Logarithms 621
A1. 5 Mathematical Induction 623
A1. 6 Induction and Recursion 630
APPENDIX 2
The string
A2. 1 Introduction 633
A2. 2 Declaration of the string Class 633
A2. 3 Fields and Implementation of the string Class
644
APPENDIX 3
Polymorphism 647
A3. 1 Introduction 647
A3. 2 The Importance of Polymorphism 648
A3. 3 Dynamic Binding 649
References 651
Index 653
鄂公网安备 42010302001612号 