数据结构的C++伪码实现 英文版PDF电子书下载

1 Introduction 1

1-1 Pseudocode 2

Algorithm Header 2

Purpose,Conditions,and Return 3

Statement Numbers 4

Variables 4

Algorithm Analysis 5

Statement Constructs 5

Pseudocode Example 6

1-2 The Abstract Data Type 7

Data Structure 8

Atomic and Composite Data 8

Abstract Data Type 9

1-3 A Model for an Abstract Data Type 10

ADT Operations 11

ADT Data Structure 11

ADT Class Templates 13

1-4 Algorithm Efficiency 13

Linear Loops 14

Logarithmic Loops 14

Nested Loops 15

Big-O Notation 17

Standard Measures of Efficiency 19

Big-O Analysis Examples 20

1-5 Summary 22

1-6 Practice Sets 23

Exercises 23

Problems 25

Projects 25

2 Searching 27

2-1 List Searches 28

Sequential Search 28

Variations on Sequential Searches 30

Binary Search 33

Binary Search Algorithm 36

Analyzing Search Algorithms 37

2-2 C++ Search Algorithms 38

Sequential Search in C++ 38

Binary Search in C++ 40

Search Example 41

2-3 Hashed List Searches 44

Basic Concepts 44

Hashing Methods 46

Hashing Algorithm 50

2-4 Collision Resolution 51

Open Addressing 53

Bucket Hashing 57

Linked List Resolution 57

Hash List Example 58

Combination Approaches 58

2-5 Summary 62

2-6 Practice Sets 64

Exercises 64

Problems 65

Projects 65

3 Linked Lists 67

3-1 Linear List Concepts 68

Insertion 68

Deletion 69

3-2 Linked List Concepts 70

Retrieval 70

Traversal 70

Nodes 71

Linked List Data Structure 71

Pointers to Linked Lists 73

3-3 Linked List Algorithms 73

Create List 73

Insert Node 74

Delete Node 78

Search List 80

Retrleve Node 83

Unordered List Search 83

Full List 84

Empty List 84

List Count 85

Traverse List 85

Destroy List 87

3-4 Processing a Linked List 88

Add Node 90

Remove Node 90

Print List 91

Testing Insert and Delete Logic 92

Append Lists 93

3-5 List Applications 93

Array of Lists 95

3-6 Complex Linked List Structures 97

Circularly Linked Lists 97

Doubly Linked Lists 98

Multilinked Lists 103

Multilinked List Insert 104

Multilinked List Delete 105

3-7 Building a Linked List-C++Implementation 105

Data Structure 105

Application Functions 106

3-8 List Abstract Data Type-Linked List Implementation 112

List ADT Declaration 113

3-9 Summary 124

3-10 Practice Sets 125

Exercises 125

Problems 127

Projects 128

4 Stacks 135

4-1 Basic Stack Operations 136

Push 136

Pop 136

Data Structure 137

4-2 Stack Linked List Implementation 137

Stack Top 137

Stack Algorithms 139

4-3 Stack Applications 146

Reversing Data 146

Reverse a List 146

Convert Decimal to Binary 147

Parsing 148

Postponement 149

Backtracking 157

4-4 Eight Queens Problem-C++Implementation 163

Get Board Size 164

Main Line Logic 164

4-5 Stack Abstract Data Type Implementation 169

Data Structure 169

Stack ADT Implementation 170

4-6 Stack ADT-Array Implementation 175

Array Data Structure 176

Create Stack Array 177

Push Stack Array 178

Pop Stack Array 178

Stack Top Array 179

Stack Count Array 180

Full Stack Array 180

Empty Stack Array 180

Destory Stack Array 181

4-7 Summary 181

4-8 Practice Sets 182

Exercises 182

Problems 183

Projects 185

5 Queues 189

5-1 Queue Operations 190

Enqueue 190

Dequeue 190

Queue Rear 191

Queue Front 191

Queue Example 192

5-2 Queue Linked List Design 192

Data Structure 192

Queue Algorithms 194

Create Queue 194

Enqueue 196

Dequeue 197

Retrieving Queue Data 198

Full Queue 199

Empty Queue 199

Queue Count 200

Destroy Queue 200

5-3 Queuing Theory 200

5-4 Queue Applications 202

Queue Simulation 202

Categorizing Data 209

5-5 Categorizing Data-C++Implementation 211

Main Line Logic 211

Fill Queues 212

Print Queues 213

Print One Queue 214

Queue Structure 215

5-6 Queue ADT-Linked List Implementation 215

Queue ADT Implementation 216

5-7 Queue ADT-Array Implementation 221

Array Queues Implementation 222

5-8 Summary 228

5-9 Practice Sets 229

Exercises 229

Problems 231

Projects 232

6 Recursion 237

6-1 Factorial-A Case Study 238

Recursion Defined 238

Recursive Solution 239

Iterative Solution 239

6-2 How Recursion Works 240

6-3 Designing Recursive Algorithms 242

The Design Methodology 243

Limitations of Recursion 243

Design Implementation-Reverse a Linked List 244

6-4 Another Case Study-Fibonacci Numbers 246

6-5 The Towers of Hanoi 249

Recursive Towers Of Hanoi 250

6-6 C++Implementations of Recursion 253

Fibonacci Numbers 253

Prefix to Postfix Conversion 254

Towers of Hanoi 259

6-7 Summary 260

6-8 Practice Sets 261

Exercises 261

Problems 263

Projects 264

7 Introduction to Trees 265

7-1 Basic Tree Concepts 266

Terminology 266

Tree Representation 268

7-2 Binary Trees 270

Properties 271

Depth-First Traversals 273

7-3 Binary Tree Traversals 273

Breadth-First Traversals 278

7-4 Expression Trees 280

Infix Traversal 280

Postfix Traversal 281

Prefix Traversal 282

7-5 General Trees 282

Changing General Tree to Binary Tree 282

Insertions into General Trees 283

General Tree Deletions 285

7-6 Huffman Code 285

7-7 Summary 288

7-8 Practice Sets 290

Exercises 290

Problems 293

Projects 293

8 Search Trees 294

8-1 Binary Search Trees 295

Definition 295

Operations on Binary Search Trees 296

Binary Search Tree Search Algorithms 297

8-2 AVL Trees 306

Balancing Trees 309

AVL Balance Factor 309

AVL Node Structure 314

AVL Delete Algorithm 319

Adjusting the Balance Factors 323

8-3 AVL Tree Implementation 324

Data Structure 324

Program Design 325

Count Words Summary 328

8-4 AVL Abstract Data Type 329

AVL Tree Data Structures 330

AVL Tree Functions 331

AVL Tree Data Processing 342

AVL Tree Utility Functions 344

8-5 Summary 347

8-6 Practice Sets 348

Exercises 348

Problems 350

Projects 351

9 Heaps 354

9-1 Heap Definition 355

9-2 Heap Structure 355

9-3 Basic Heap Algorithms 356

ReheapUp 356

ReheapDown 358

9-4 Heap Data Structure 360

9-5 Heap Algorithms 361

ReheapUp 361

ReheapDown 362

BuildHeap 363

InsertHeap 364

DeleteHeap 365

9-6 Heap Applications 367

Selection Algorithms 367

Priority Queues 368

9-7 A Heap Program 370

Heap Program Design 370

Heap Functions 375

9-8 Summary 377

9-9 Practice Sets 378

Exercises 378

Problems 380

Projects 380

10 Multiway Trees 383

10-1 m-Way Search Trees 384

10-2 B-Trees 385

B-Tree Insertion 387

B-Tree Insert Design 388

B-Tree Insert Node 389

B-Tree Deletion 396

Traverse B-Tree 407

B-Tree Search 410

10-3 Simplified B-Trees 411

2-3 Tree 411

2-3-4 Tree 411

10-4 B-Tree Variations 412

B*Tree 412

B+Tree 413

10-5 Lexical Search Tree 413

Tries 414

Utility Functions 415

Header File 415

Trie Structure 415

10-6 B-Tree Abstract Data Type 415

Insert Algorithms 428

Delete Algorithms 428

10-7 Summary 434

10-8 Practice Sets 435

Exercises 435

Problems 436

Projects 436

11 Advanced Sorting Concepts 438

Sort Order 439

11-1 General Sort Concepts 439

Sort Stability 440

Sort Efficiency 440

Passes 440

11-2 Insertion Sorts 441

Straight Insertion Sort 441

Shell Sort 443

Insertion Sort Algorithms 447

Insertion Sort Implementation 449

11-3 Selection Sorts 451

Straight Selection Sort 451

Selection Sort Algorithms 456

Selection Sort Implementation 457

11-4 Exchange Sorts 459

Bubble Sort 459

Bubble Sort Algorithm 461

Quick Sort 462

Exchange Sort Algorithms 468

11-5 Summary 470

Exchange Sort Implementation 470

11-6 External Sorts 474

Merging Ordered Files 474

Merging Unordered Files 475

The Sorting Process 476

Sort Phase Revisited 482

11-7 Summary 484

11-8 Practice Sets 485

Exercises 485

Problems 486

Projects 486

12 Graphs 490

12-1 Terminology 491

12-2 Operations 492

Add Vertex 492

Find Vertex 493

Delete Edge 493

Add Edge 493

Delete Vertex 493

Traverse Graph 494

12-3 Graph Storage Structures 497

Adjacency Matrix 497

Adjacency List 498

12-4 Graph Algorithms 499

Create Graph 500

Insert Vertex 500

Delete Vertex 502

Insert Arc 503

Delete Arc 505

Retrieve Vertex 506

First Arc 507

Depth-First Traversal 508

Breadth-First Traversal 510

12-5 Networks 512

Minimum Spanning Tree 512

Shortest Path Algorithm 517

12-6 Abstract Data Type 521

Insert Vertex 523

Delete Vertex 524

Insert Arc 525

Delete Arc 526

Depth-First Traversal 528

Breadth-First Traversal 529

12-7 Summary 531

12-8 Practice Sets 532

Exercises 532

Problems 533

Projects 534

Appendixes 537

A ASCII Tables 537

B Structure Charts 542

C Program Standards and Styles 549

D Random Numbers 554

E Standard C++Libraries 559

F C++Function Prototypes 561

G Classes Related to Input and Output 569

H The String Class 574

I Pointers to Functions 584

J Inheritance 587

K C++Templates 601

L Standard Template Library 608

Solutions to Selected Exercises 626

Glossary 647

Index 657