DATA STRUCTURES WITH C++USING STL （第二版）2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Introduction to Data Structures1

1-1 WHAT IS THIS BOOK ABOUT？2

Data Structures and Algorithms5

1-2 ABSTRACT VIEW OF DATA STRUCTURES5

The time24 ADT6

1-3 AN ADT AS A CLASS8

The C++ Class8

Private and Public Sections9

Encapsulation and Information Hiding9

The time24 Class9

1-4 IMPLEMENTING C++ CLASSES13

Implementation of the time24 Class14

1-5 DECLARING AND USING OBJECTS18

Running a Program18

1-6 IMPLEMENTING A CLASS WITH INLINE CODE21

Compiler Use of Inline Code22

1-7 APPLICATION PROGRAMMING INTERFACE（API）23

Random Numbers24

The randomNumberAPI24

Application： The Game of Craps26

1-8 STRINGS28

The string Class30

Additional String Functions and Operations31

CHAPTER SUMMARY36

CLASSES AND LIBRARIES IN THE CHAPTER37

REVIEW EXERCISES38

Answers to Review Exercises40

WRITTEN EXERCISES42

PROGRAMMING EXERCISES48

PROGRAMMING PROJECTS51

2 Object Design Techniques53

2-1 SOFTWARE DESIGN55

Request and Problem Analysis56

Program Design57

Designing the Calendar Class58

Program Implementation62

Implementing the Calendar Class62

Program Testing and Debugging64

Program Maintenance68

2-2 HANDLING RUNTIME ERRORS68

Terminate Program69

Set a Flag69

C++ Exceptions70

2-3 OBJECT COMPOSITION74

The timeCard Class75

Implementing the timeCard Class77

2-4 OPERATOR OVERLOADING82

Operator Functions85

Operator Overloading with Free Functions86

Operator Overloading with Friend Functions87

Overloading Stream I/O Operators89

Member Function Overloading94

CHAPTER SUMMARY97

CLASSES AND LIBRARIES IN THE CHAPTER98

REVIEW EXERCISES99

Answers to Review Exercises100

WRITTEN EXERCISES102

PROGRAMMING EXERCISES107

PROGRAMMING PROJECTS108

3 Introduction to Algorithms113

3-1 SELECTION SORT115

Selection Sort Algorithm116

3-2 SIMPLE SEARCH ALGORITHMS120

Sequential Search120

Binary Search122

3-3 ANALYSIS OF ALGORITHMS127

System/Memory Performance Criteria128

Algorithm Performance Criteria： Running Time Analysis128

Big-O Notation131

Common Orders of Magnitude133

3-4 ANALYZING THE SEARCH ALGORITHMS135

Binary Search Running Time135

Comparing Search Algorithms136

3-5 MAKING ALGORITHMS GENERIC139

Template Syntax140

Runtime Template Expansion142

Template-Based Searching Functions144

3-6 THE CONCEPT OF RECURSION146

Implementing Recursive Functions148

How Recursion Works149

Application： Multibase Output152

3-7 PROBLEM SOLVING WITH RECURSION155

Tower of Hanoi155

Number Theory： The Greatest Common Divisor159

Application of gcd - Rational Numbers161

Evaluating Recursion164

CHAPTER SUMMARY168

CLASSES AND LIBRARIES IN THE CHAPTER169

REVIEW EXERCISES169

Answers to Review Exercises172

WRITTEN EXERCISES173

PROGRAMMING EXERCISES179

PROGRAMMING PROJECT182

4 The Vector Container183

4-1 OVERVIEW OF STL CONTAINER CLASSES184

4-2 TEMPLATE CLASSES188

Constructing a Template Class188

Declaring Template Class Objects191

4-3 THE VECTOR CLASS192

Introducing the Vector Container195

The Vector API200

4-4 VECTOR APPLICATIONS202

Joining Vectors203

The Insertion Sort203

CHAPTER SUMMARY208

CLASSES AND LIBRARIES IN THE CHAPTER209

REVIEW EXERCISES209

Answers to Review Exercises211

WRITTEN EXERCISES211

PROGRAMMING EXERCISES216

PROGRAMMING PROJECT217

5 Pointers and Dynamic Memory219

5-1 C+ + POINTERS221

Declaring Pointer Variables222

Assigning Values to Pointers222

Accessing Data with Pointers224

Arrays And Pointers225

Pointers and Class Types227

5-2 DYNAMIC MEMORY229

The Memory Allocation Operator new229

Dynamic Array Allocation231

The Memory Deallocation Operator delete232

5-3 CLASSES USING DYNAMIC MEMORY234

The Class dynamicClass234

The Destructor236

5-4 ASSIGNMENT AND INITIALIZATION240

Assignment Issues240

Overloading the Assignment Operator242

The Pointer this243

Initialization Issues243

Creating a Copy Constructor244

5-5 THE MINIVECTOR CLASS247

Design of the miniVector Class248

Reserving More Capacity251

The miNiVector Constructor， Destructor， and Assignment253

Adding and Removing Elements from a miNIVector Object254

Overloading the Index Operator258

5-6 THE MATRIX CLASS260

Describing the Matrix Container261

Implementing Matrix Functions265

CHAPTER SUMMARY266

CLASSES AND LIBRARIES IN THE CHAPTER267

REVIEW EXERCISES268

Answers to Review Exercises270

WRITTEN EXERCISES271

PROGRAMMING EXERCISES277

PROGRAMMING PROJECT279

6 The List Container and Iterators281

6-1 THE LIST CONTAINER282

The listADT284

The listAPI286

Application： A List Palindrome288

6-2 ITERATORS290

The Iterator Concept290

Constant Iterators294

The Sequential Search of a List296

Application： Word Frequencies298

6-3 GENERAL LIST INSERT AND ERASE OPERATIONS302

Ordered Lists305

Removing Duplicates307

Splicing Two Lists309

6-4 CASE STUDY：GRADUATION LISTS310

Problem Analysis310

Program Design310

Program Implementation312

CHAPTER SUMMARY315

CLASSES AND LIBRARIES IN THE CHAPTER316

REVIEW EXERCISES316

Answers to Review Exercises318

WRITTEN EXERCISES319

PROGRAMMING EXERCISES322

PROGRAMMING PROJECT325

7 Stacks327

7-1 THE STACK ADT328

Multibase Output332

Uncoupling Stack Elements336

7-2 RECURSIVE CODE AND THE RUNTIME STACK339

7-3 STACK IMPLEMENTATION342

miniStack Class Implementation345

Implementation of the STL stack Class （Optional）346

7-4 POSTFIX EXPRESSIONS347

Postfix Evaluation349

The postfixEval Class350

7-5 CASE STUDY： INFIX EXPRESSION EVALUATION357

Infix Expression Attributes358

Infix to Postfix Conversion： Algorithm Design359

Infix to Postfix Conversion： Object Design364

infix2Postftx Class Implementation366

CHAPTER SUMMARY372

CLASSES IN THE CHAPTER373

REVIEW EXERCISES373

Answers to Review Exercises375

WRITTEN EXERCISES377

PROGRAMMING EXERCISES381

PROGRAMMING PROJECTS382

8 Queues and Priority Queues384

8-1 THE QUEUE ADT386

Application： Scheduling Queue388

8-2 THE RADIX SORT390

Radix Sort Algorithm391

8-3 IMPLEMENTING THE MINIQUEUE CLASS395

Implementation of the STL queue Class （Optional）398

8-4 CASE STUDY： TIME-DRIVEN SIMULATION399

Simulation Design400

Simulation Implementation401

8-5 ARRAY BASED QUEUE IMPLEMENTATION406

Designing the Bounded Queue409

Implementing the Bounded Queue411

8-6 PRIORITY QUEUES412

Priority Queue ADT413

Sorting with a Priority Queue415

Company Support Services417

CHAPTER SUMMARY421

CLASSES AND LIBRARIES IN THE CHAPTER422

REVIEW EXERCISES423

Answers to Review Exercises425

WRITTEN EXERCISES426

PROGRAMMING EXERCISES430

PROGRAMMING PROJECT432

9 Linked Lists436

9-1 LINKED LIST NODES438

The node Class439

Adding and Removing Nodes442

9-2 BUILDING LINKED LISTS443

Defining a Singly Linked List443

Inserting at the Front of a Linked List445

Erasing at the Front of a Linked List447

Removing a Target Node448

9-3 HANDLING THE BACK OF THE LIST452

Designing a New Linked List Structure453

9-4 IMPLEMENTING A LINKED QUEUE455

The linkedQueue Class456

Implementing the linkedQueue Class457

9-5 DOUBLY LINKED LISTS462

dnode Objects463

Circular Doubly Linked Lists466

9-6 UPDATING A DOUBLY LINKED LIST468

The insert（） Function468

The erase（） Function470

9-7 THE JOSEPHUS PROBLEM474

9-8 THE MINILIST CLASS477

miniList Class Private Members478

miniList Class Constructors and Destructor479

Functions Dealing with the Ends of a List480

miniList Iterators481

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

The General List Insert Function485

9-9 SELECTING A SEQUENCE CONTAINER486

CHAPTER SUMMARY487

CLASSES AND LIBRARIES IN THE CHAPTER489

REVIEW EXERCISES489

Answers to Review Exercises493

WRITTEN EXERCISES495

PROGRAMMING EXERCISES498

PROGRAMMING PROJECT500

10 Binary Trees502

10-1 TREE STRUCTURES504

Tree Terminology505

Binary Trees506

10-2 BINARY TREE NODES510

Building a Binary Tree511

10-3 BINARY TREE SCAN ALGORITHMS514

Recursive Tree Traversals514

Iterative Level-Order Scan518

10-4 USING TREE SCAN ALGORITHMS522

Computing the Leaf Count522

Computing the Depths of a Tree523

Copying a Binary Tree526

Deleting Tree Nodes529

Displaying a Binary Tree530

10-5 BINARY SEARCH TREES532

Introducing Binary Search Trees533

Building a Binary Search Tree534

Locating Data in a Binary Search Tree535

Removing a Binary Search Tree Node536

A Binary Search Tree Class537

Access and Update Operations538

10-6 USING BINARY SEARCH TREES543

Application： Removing Duplicates543

Application： The Video Store545

10-7 IMPLEMENTING THE stree CLASS551

The stree Class Data Members553

Constructor， Destructor， and Assignment554

Update Operations554

Complexity of Binary Search Tree Operations563

10-8 THE STREE ITERATOR （Optional）563

Implementing the stree Iterator565

CHAPTER SUMMARY569

CLASSES AND LIBRARIES IN THE CHAPTER571

REVIEW EXERCISES571

Answers to Review Exercises574

WRITTEN EXERCISES576

PROGRAMMING EXERCISES579

PROGRAMMING PROJECTS581

11 Associative Containers586

11-1 OVERVIEW OF ASSOCIATIVE CONTAINERS587

Associative Container Categories587

STL Associative Containers590

Implementing Associative Containers590

11-2 SETS591

Displaying a Container Using Iterators592

Set Access and Update Functions593

A Simple Spelling Checker596

Application： Sieve of Eratosthenes600

Set Operations603

Application： Updating Computer Accounts606

11-3 MAPS610

The Map Class Interface610

Map Operations613

Map Index Operator614

Case Study： Concordance618

11-4 MULTISETS623

Application： Computer Software Products625

11-5 IMPLEMENTING SETS AND MAPS628

Implementing miniSet Operations629

The miniMap Class630

Implementing the miniMap Class632

The miniMap Index Operator633

CHAPTER SUMMARY634

CLASSES AND LIBRARIES IN THE CHAPTER635

REVIEW EXERCISES635

Answers to Review Exercises637

WRITTEN EXERCISES638

PROGRAMMING EXERCISES641

PROGRAMMING PROJECTS643

12 Advanced Associative Structures646

12-1 HASHING649

Using a Hash Function650

12-2 DESIGNING HASH FUNCTIONS651

Function Objects652

Illustrating Function Objects653

Integer Hash Functions656

String Hash Functions658

A Custom Hash Function659

12-3 DESIGNING HASH TABLES659

Linear Probe Open Addressing660

Chaining with Separate Lists662

12-4 THE HASH CLASS663

Application： Using a Hash Table666

Hash Class Implementation669

Implementing the Hash Iterators672

Unordered Associative Containers676

12-5 HASH TABLE PERFORMANCE678

Comparing Search Algorithms680

12-6 2-3-4 TREES683

Inserting into a 2-3-4 Tree686

Running Time for 2-3-4 Tree Operations689

12-7 RED-BLACK TREES690

Properties of a Red-Black Tree692

Inserting Nodes in a Red-Black Tree694

Building a Red-Black Tree699

Search Running Time （Optional）701

Erasing a Node in a Red-Black Tree702

12-8 THE RBTREE CLASS703

rbtree Class Private Section707

Splitting a 4-node707

The insert（） Operation709

CHAPTER SUMMARY710

CLASSES AND LIBRARIES IN THE CHAPTER711

REVIEW EXERCISES712

Answers to Review Exercises714

WRITTEN EXERCISES716

PROGRAMMING EXERCISES723

PROGRAMMING PROJECTS725

13 Inheritance and Abstract Classes727

13-1 INHERITANCE IN C++730

Declaring the Employee Hierarchy731

Derived Class Constructor734

Implementing Member Functions736

13-2 THE GRAPHICS HIERARCHY739

The circleShape Class742

The Other Figure and Text Classes744

Implementing the Polyshape Class747

13-3 THE GRAPHICS SYSTEM750

13-4 SAFE VECTORS754

13-5 ORDERED LISTS756

OrderedList Class Implementation758

13-6 POLYMORPHISM AND VIRTUAL FUNCTIONS759

Dynamic Binding761

Application： Paying Employees with Polymorphism763

Implementing Polymorphism in C++766

Virtual Functions And The Destructor768

13-7 ABSTRACT CLASSES771

An Abstract Class as an Interface772

The Stack Interface772

CHAPTER SUMMARY773

CLASSES AND LIBRARIES IN THE CHAPTER774

REVIEW EXERCISES775

Answers to Review Exercises778

WRITTEN EXERCISES780

PROGRAMMING EXERCISES786

PROGRAMMING PROJECT789

14 Heaps Binary Files and Bit Sets790

14-1 ARRAY BASED BINARY TREES792

14-2 HEAPS793

Inserting into a Heap794

Deleting from a Heap797

The Heap Sort801

Heapifying a Vector805

14-3 IMPLEMENTING A PRIORITY QUEUE808

Implementing the miniPQ Class809

14-4 BINARY FILES811

File Structure811

Direct File Access812

Input and Output for Binary Files813

Application： Bank Account Records814

14-5 BITSETS818

The bitVector Class820

Implementing the bitVector Class823

14-6 CASE STUDY： HUFFMAN COMPRESSION826

Building the Huffinan Tree830

Implementation of Huffman Compression831

Huffman Decompression840

CHAPTER SUMMARY843

CLASSES AND LIBRARIES IN THE CHAPTER844

REVIEW EXERCISES845

Answers to Review Exercises847

WRITTEN EXERCISES849

PROGRAMMING EXERCISES856

PROGRAMMING PROJECT859

15 Recursive Algorithms861

15-1 DIVIDE AND CONQUER ALGORITHMS862

Building a Ruler863

Mergesort866

Quicksort874

Comparison of Sorting Algorithms884

Application： Finding Kth Largest Element886

15-2 COMBINATORICS889

Finding All Subsets889

Listing Permutations893

15-4 DYNAMIC PROGRAMMING897

Top-Down Dynamic Programming898

Application： Combinations901

Bottom-Up Dynamic Programming903

Knapsack Problem904

15-4 BACKTRACKING： THE Eight-QUEENS PROBLEM912

Problem Analysis914

Program Design915

Displaying a Chessboard918

Illustrating the Eight-Queens Problem920

CHAPTER SUMMARY921

CLASSES AND LIBRARIES IN THE CHAPTER923

REVIEW EXERCISES923

Answers to Review Exercises925

WRITTEN EXERCISES929

PROGRAMMING EXERCISES932

PROGRAMMING PROJECT936

16 Graphs939

16-1 GRAPH TERMINOLOGY941

Directed Graphs942

Weighted Graphs943

16-2 THE GRAPH CLASS944

Listing the Graph API944

16-3 GRAPH CLASS DESIGN951

Representing Vertex Information951

The Vertex Map and Vlnfo List953

Graph Class Declaration957

Graph Class Implementation958

16-4 GRAPH TRAVERSAL ALGORITHMS962

Breadth-First Search964

Depth-First Visit Algorithms968

Depth-First Search973

16-5 GRAPH TRAVERSAL APPLICATIONS974

Acyclic Graphs974

Topological Sort977

Strong Components981

16-6 GRAPH MINIMIZATION ALGORITHMS985

Shortest Path Algorithm986

Dijkstra’s Minimum Path Algorithm991

Minimum Spanning Tree998

CHAPTER SUMMARY1006

CLASSES AND LIBRARIES IN THE CHAPTER1007

REVIEW EXERCISES1007

Answers to Review Exercises1009

WRITTEN EXERCISES1010

PROGRAMMING EXERCISES1018

PROGRAMMING PROJECT1019

Index1021