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