DATA STRUCTURES WITH C++USING STL （第二版）PDF电子书下载

1 Introduction to Data Structures 1

1-1 WHAT IS THIS BOOK ABOUT？ 2

Data Structures and Algorithms 5

1-2 ABSTRACT VIEW OF DATA STRUCTURES 5

The time24 ADT 6

1-3 AN ADT AS A CLASS 8

The C++ Class 8

Private and Public Sections 9

Encapsulation and Information Hiding 9

The time24 Class 9

1-4 IMPLEMENTING C++ CLASSES 13

Implementation of the time24 Class 14

1-5 DECLARING AND USING OBJECTS 18

Running a Program 18

1-6 IMPLEMENTING A CLASS WITH INLINE CODE 21

Compiler Use of Inline Code 22

1-7 APPLICATION PROGRAMMING INTERFACE（API） 23

Random Numbers 24

The randomNumberAPI 24

Application： The Game of Craps 26

1-8 STRINGS 28

The string Class 30

Additional String Functions and Operations 31

CHAPTER SUMMARY 36

CLASSES AND LIBRARIES IN THE CHAPTER 37

REVIEW EXERCISES 38

Answers to Review Exercises 40

WRITTEN EXERCISES 42

PROGRAMMING EXERCISES 48

PROGRAMMING PROJECTS 51

2 Object Design Techniques 53

2-1 SOFTWARE DESIGN 55

Request and Problem Analysis 56

Program Design 57

Designing the Calendar Class 58

Program Implementation 62

Implementing the Calendar Class 62

Program Testing and Debugging 64

Program Maintenance 68

2-2 HANDLING RUNTIME ERRORS 68

Terminate Program 69

Set a Flag 69

C++ Exceptions 70

2-3 OBJECT COMPOSITION 74

The timeCard Class 75

Implementing the timeCard Class 77

2-4 OPERATOR OVERLOADING 82

Operator Functions 85

Operator Overloading with Free Functions 86

Operator Overloading with Friend Functions 87

Overloading Stream I/O Operators 89

Member Function Overloading 94

CHAPTER SUMMARY 97

CLASSES AND LIBRARIES IN THE CHAPTER 98

REVIEW EXERCISES 99

Answers to Review Exercises 100

WRITTEN EXERCISES 102

PROGRAMMING EXERCISES 107

PROGRAMMING PROJECTS 108

3 Introduction to Algorithms 113

3-1 SELECTION SORT 115

Selection Sort Algorithm 116

3-2 SIMPLE SEARCH ALGORITHMS 120

Sequential Search 120

Binary Search 122

3-3 ANALYSIS OF ALGORITHMS 127

System/Memory Performance Criteria 128

Algorithm Performance Criteria： Running Time Analysis 128

Big-O Notation 131

Common Orders of Magnitude 133

3-4 ANALYZING THE SEARCH ALGORITHMS 135

Binary Search Running Time 135

Comparing Search Algorithms 136

3-5 MAKING ALGORITHMS GENERIC 139

Template Syntax 140

Runtime Template Expansion 142

Template-Based Searching Functions 144

3-6 THE CONCEPT OF RECURSION 146

Implementing Recursive Functions 148

How Recursion Works 149

Application： Multibase Output 152

3-7 PROBLEM SOLVING WITH RECURSION 155

Tower of Hanoi 155

Number Theory： The Greatest Common Divisor 159

Application of gcd - Rational Numbers 161

Evaluating Recursion 164

CHAPTER SUMMARY 168

CLASSES AND LIBRARIES IN THE CHAPTER 169

REVIEW EXERCISES 169

Answers to Review Exercises 172

WRITTEN EXERCISES 173

PROGRAMMING EXERCISES 179

PROGRAMMING PROJECT 182

4 The Vector Container 183

4-1 OVERVIEW OF STL CONTAINER CLASSES 184

4-2 TEMPLATE CLASSES 188

Constructing a Template Class 188

Declaring Template Class Objects 191

4-3 THE VECTOR CLASS 192

Introducing the Vector Container 195

The Vector API 200

4-4 VECTOR APPLICATIONS 202

Joining Vectors 203

The Insertion Sort 203

CHAPTER SUMMARY 208

CLASSES AND LIBRARIES IN THE CHAPTER 209

REVIEW EXERCISES 209

Answers to Review Exercises 211

WRITTEN EXERCISES 211

PROGRAMMING EXERCISES 216

PROGRAMMING PROJECT 217

5 Pointers and Dynamic Memory 219

5-1 C+ + POINTERS 221

Declaring Pointer Variables 222

Assigning Values to Pointers 222

Accessing Data with Pointers 224

Arrays And Pointers 225

Pointers and Class Types 227

5-2 DYNAMIC MEMORY 229

The Memory Allocation Operator new 229

Dynamic Array Allocation 231

The Memory Deallocation Operator delete 232

5-3 CLASSES USING DYNAMIC MEMORY 234

The Class dynamicClass 234

The Destructor 236

5-4 ASSIGNMENT AND INITIALIZATION 240

Assignment Issues 240

Overloading the Assignment Operator 242

The Pointer this 243

Initialization Issues 243

Creating a Copy Constructor 244

5-5 THE MINIVECTOR CLASS 247

Design of the miniVector Class 248

Reserving More Capacity 251

The miNiVector Constructor， Destructor， and Assignment 253

Adding and Removing Elements from a miNIVector Object 254

Overloading the Index Operator 258

5-6 THE MATRIX CLASS 260

Describing the Matrix Container 261

Implementing Matrix Functions 265

CHAPTER SUMMARY 266

CLASSES AND LIBRARIES IN THE CHAPTER 267

REVIEW EXERCISES 268

Answers to Review Exercises 270

WRITTEN EXERCISES 271

PROGRAMMING EXERCISES 277

PROGRAMMING PROJECT 279

6 The List Container and Iterators 281

6-1 THE LIST CONTAINER 282

The listADT 284

The listAPI 286

Application： A List Palindrome 288

6-2 ITERATORS 290

The Iterator Concept 290

Constant Iterators 294

The Sequential Search of a List 296

Application： Word Frequencies 298

6-3 GENERAL LIST INSERT AND ERASE OPERATIONS 302

Ordered Lists 305

Removing Duplicates 307

Splicing Two Lists 309

6-4 CASE STUDY：GRADUATION LISTS 310

Problem Analysis 310

Program Design 310

Program Implementation 312

CHAPTER SUMMARY 315

CLASSES AND LIBRARIES IN THE CHAPTER 316

REVIEW EXERCISES 316

Answers to Review Exercises 318

WRITTEN EXERCISES 319

PROGRAMMING EXERCISES 322

PROGRAMMING PROJECT 325

7 Stacks 327

7-1 THE STACK ADT 328

Multibase Output 332

Uncoupling Stack Elements 336

7-2 RECURSIVE CODE AND THE RUNTIME STACK 339

7-3 STACK IMPLEMENTATION 342

miniStack Class Implementation 345

Implementation of the STL stack Class （Optional） 346

7-4 POSTFIX EXPRESSIONS 347

Postfix Evaluation 349

The postfixEval Class 350

7-5 CASE STUDY： INFIX EXPRESSION EVALUATION 357

Infix Expression Attributes 358

Infix to Postfix Conversion： Algorithm Design 359

Infix to Postfix Conversion： Object Design 364

infix2Postftx Class Implementation 366

CHAPTER SUMMARY 372

CLASSES IN THE CHAPTER 373

REVIEW EXERCISES 373

Answers to Review Exercises 375

WRITTEN EXERCISES 377

PROGRAMMING EXERCISES 381

PROGRAMMING PROJECTS 382

8 Queues and Priority Queues 384

8-1 THE QUEUE ADT 386

Application： Scheduling Queue 388

8-2 THE RADIX SORT 390

Radix Sort Algorithm 391

8-3 IMPLEMENTING THE MINIQUEUE CLASS 395

Implementation of the STL queue Class （Optional） 398

8-4 CASE STUDY： TIME-DRIVEN SIMULATION 399

Simulation Design 400

Simulation Implementation 401

8-5 ARRAY BASED QUEUE IMPLEMENTATION 406

Designing the Bounded Queue 409

Implementing the Bounded Queue 411

8-6 PRIORITY QUEUES 412

Priority Queue ADT 413

Sorting with a Priority Queue 415

Company Support Services 417

CHAPTER SUMMARY 421

CLASSES AND LIBRARIES IN THE CHAPTER 422

REVIEW EXERCISES 423

Answers to Review Exercises 425

WRITTEN EXERCISES 426

PROGRAMMING EXERCISES 430

PROGRAMMING PROJECT 432

9 Linked Lists 436

9-1 LINKED LIST NODES 438

The node Class 439

Adding and Removing Nodes 442

9-2 BUILDING LINKED LISTS 443

Defining a Singly Linked List 443

Inserting at the Front of a Linked List 445

Erasing at the Front of a Linked List 447

Removing a Target Node 448

9-3 HANDLING THE BACK OF THE LIST 452

Designing a New Linked List Structure 453

9-4 IMPLEMENTING A LINKED QUEUE 455

The linkedQueue Class 456

Implementing the linkedQueue Class 457

9-5 DOUBLY LINKED LISTS 462

dnode Objects 463

Circular Doubly Linked Lists 466

9-6 UPDATING A DOUBLY LINKED LIST 468

The insert（） Function 468

The erase（） Function 470

9-7 THE JOSEPHUS PROBLEM 474

9-8 THE MINILIST CLASS 477

miniList Class Private Members 478

miniList Class Constructors and Destructor 479

Functions Dealing with the Ends of a List 480

miniList Iterators 481

The miniList Member Functions begin（） and end（） 485

The General List Insert Function 485

9-9 SELECTING A SEQUENCE CONTAINER 486

CHAPTER SUMMARY 487

CLASSES AND LIBRARIES IN THE CHAPTER 489

REVIEW EXERCISES 489

Answers to Review Exercises 493

WRITTEN EXERCISES 495

PROGRAMMING EXERCISES 498

PROGRAMMING PROJECT 500

10 Binary Trees 502

10-1 TREE STRUCTURES 504

Tree Terminology 505

Binary Trees 506

10-2 BINARY TREE NODES 510

Building a Binary Tree 511

10-3 BINARY TREE SCAN ALGORITHMS 514

Recursive Tree Traversals 514

Iterative Level-Order Scan 518

10-4 USING TREE SCAN ALGORITHMS 522

Computing the Leaf Count 522

Computing the Depths of a Tree 523

Copying a Binary Tree 526

Deleting Tree Nodes 529

Displaying a Binary Tree 530

10-5 BINARY SEARCH TREES 532

Introducing Binary Search Trees 533

Building a Binary Search Tree 534

Locating Data in a Binary Search Tree 535

Removing a Binary Search Tree Node 536

A Binary Search Tree Class 537

Access and Update Operations 538

10-6 USING BINARY SEARCH TREES 543

Application： Removing Duplicates 543

Application： The Video Store 545

10-7 IMPLEMENTING THE stree CLASS 551

The stree Class Data Members 553

Constructor， Destructor， and Assignment 554

Update Operations 554

Complexity of Binary Search Tree Operations 563

10-8 THE STREE ITERATOR （Optional） 563

Implementing the stree Iterator 565

CHAPTER SUMMARY 569

CLASSES AND LIBRARIES IN THE CHAPTER 571

REVIEW EXERCISES 571

Answers to Review Exercises 574

WRITTEN EXERCISES 576

PROGRAMMING EXERCISES 579

PROGRAMMING PROJECTS 581

11 Associative Containers 586

11-1 OVERVIEW OF ASSOCIATIVE CONTAINERS 587

Associative Container Categories 587

STL Associative Containers 590

Implementing Associative Containers 590

11-2 SETS 591

Displaying a Container Using Iterators 592

Set Access and Update Functions 593

A Simple Spelling Checker 596

Application： Sieve of Eratosthenes 600

Set Operations 603

Application： Updating Computer Accounts 606

11-3 MAPS 610

The Map Class Interface 610

Map Operations 613

Map Index Operator 614

Case Study： Concordance 618

11-4 MULTISETS 623

Application： Computer Software Products 625

11-5 IMPLEMENTING SETS AND MAPS 628

Implementing miniSet Operations 629

The miniMap Class 630

Implementing the miniMap Class 632

The miniMap Index Operator 633

CHAPTER SUMMARY 634

CLASSES AND LIBRARIES IN THE CHAPTER 635

REVIEW EXERCISES 635

Answers to Review Exercises 637

WRITTEN EXERCISES 638

PROGRAMMING EXERCISES 641

PROGRAMMING PROJECTS 643

12 Advanced Associative Structures 646

12-1 HASHING 649

Using a Hash Function 650

12-2 DESIGNING HASH FUNCTIONS 651

Function Objects 652

Illustrating Function Objects 653

Integer Hash Functions 656

String Hash Functions 658

A Custom Hash Function 659

12-3 DESIGNING HASH TABLES 659

Linear Probe Open Addressing 660

Chaining with Separate Lists 662

12-4 THE HASH CLASS 663

Application： Using a Hash Table 666

Hash Class Implementation 669

Implementing the Hash Iterators 672

Unordered Associative Containers 676

12-5 HASH TABLE PERFORMANCE 678

Comparing Search Algorithms 680

12-6 2-3-4 TREES 683

Inserting into a 2-3-4 Tree 686

Running Time for 2-3-4 Tree Operations 689

12-7 RED-BLACK TREES 690

Properties of a Red-Black Tree 692

Inserting Nodes in a Red-Black Tree 694

Building a Red-Black Tree 699

Search Running Time （Optional） 701

Erasing a Node in a Red-Black Tree 702

12-8 THE RBTREE CLASS 703

rbtree Class Private Section 707

Splitting a 4-node 707

The insert（） Operation 709

CHAPTER SUMMARY 710

CLASSES AND LIBRARIES IN THE CHAPTER 711

REVIEW EXERCISES 712

Answers to Review Exercises 714

WRITTEN EXERCISES 716

PROGRAMMING EXERCISES 723

PROGRAMMING PROJECTS 725

13 Inheritance and Abstract Classes 727

13-1 INHERITANCE IN C++ 730

Declaring the Employee Hierarchy 731

Derived Class Constructor 734

Implementing Member Functions 736

13-2 THE GRAPHICS HIERARCHY 739

The circleShape Class 742

The Other Figure and Text Classes 744

Implementing the Polyshape Class 747

13-3 THE GRAPHICS SYSTEM 750

13-4 SAFE VECTORS 754

13-5 ORDERED LISTS 756

OrderedList Class Implementation 758

13-6 POLYMORPHISM AND VIRTUAL FUNCTIONS 759

Dynamic Binding 761

Application： Paying Employees with Polymorphism 763

Implementing Polymorphism in C++ 766

Virtual Functions And The Destructor 768

13-7 ABSTRACT CLASSES 771

An Abstract Class as an Interface 772

The Stack Interface 772

CHAPTER SUMMARY 773

CLASSES AND LIBRARIES IN THE CHAPTER 774

REVIEW EXERCISES 775

Answers to Review Exercises 778

WRITTEN EXERCISES 780

PROGRAMMING EXERCISES 786

PROGRAMMING PROJECT 789

14 Heaps Binary Files and Bit Sets 790

14-1 ARRAY BASED BINARY TREES 792

14-2 HEAPS 793

Inserting into a Heap 794

Deleting from a Heap 797

The Heap Sort 801

Heapifying a Vector 805

14-3 IMPLEMENTING A PRIORITY QUEUE 808

Implementing the miniPQ Class 809

14-4 BINARY FILES 811

File Structure 811

Direct File Access 812

Input and Output for Binary Files 813

Application： Bank Account Records 814

14-5 BITSETS 818

The bitVector Class 820

Implementing the bitVector Class 823

14-6 CASE STUDY： HUFFMAN COMPRESSION 826

Building the Huffinan Tree 830

Implementation of Huffman Compression 831

Huffman Decompression 840

CHAPTER SUMMARY 843

CLASSES AND LIBRARIES IN THE CHAPTER 844

REVIEW EXERCISES 845

Answers to Review Exercises 847

WRITTEN EXERCISES 849

PROGRAMMING EXERCISES 856

PROGRAMMING PROJECT 859

15 Recursive Algorithms 861

15-1 DIVIDE AND CONQUER ALGORITHMS 862

Building a Ruler 863

Mergesort 866

Quicksort 874

Comparison of Sorting Algorithms 884

Application： Finding Kth Largest Element 886

15-2 COMBINATORICS 889

Finding All Subsets 889

Listing Permutations 893

15-4 DYNAMIC PROGRAMMING 897

Top-Down Dynamic Programming 898

Application： Combinations 901

Bottom-Up Dynamic Programming 903

Knapsack Problem 904

15-4 BACKTRACKING： THE Eight-QUEENS PROBLEM 912

Problem Analysis 914

Program Design 915

Displaying a Chessboard 918

Illustrating the Eight-Queens Problem 920

CHAPTER SUMMARY 921

CLASSES AND LIBRARIES IN THE CHAPTER 923

REVIEW EXERCISES 923

Answers to Review Exercises 925

WRITTEN EXERCISES 929

PROGRAMMING EXERCISES 932

PROGRAMMING PROJECT 936

16 Graphs 939

16-1 GRAPH TERMINOLOGY 941

Directed Graphs 942

Weighted Graphs 943

16-2 THE GRAPH CLASS 944

Listing the Graph API 944

16-3 GRAPH CLASS DESIGN 951

Representing Vertex Information 951

The Vertex Map and Vlnfo List 953

Graph Class Declaration 957

Graph Class Implementation 958

16-4 GRAPH TRAVERSAL ALGORITHMS 962

Breadth-First Search 964

Depth-First Visit Algorithms 968

Depth-First Search 973

16-5 GRAPH TRAVERSAL APPLICATIONS 974

Acyclic Graphs 974

Topological Sort 977

Strong Components 981

16-6 GRAPH MINIMIZATION ALGORITHMS 985

Shortest Path Algorithm 986

Dijkstra’s Minimum Path Algorithm 991

Minimum Spanning Tree 998

CHAPTER SUMMARY 1006

CLASSES AND LIBRARIES IN THE CHAPTER 1007

REVIEW EXERCISES 1007

Answers to Review Exercises 1009

WRITTEN EXERCISES 1010

PROGRAMMING EXERCISES 1018

PROGRAMMING PROJECT 1019

Index 1021