Cart

Data Structures & Algorithms in Python, 1st edition

BRAND: PEARSON

Publisher: Pearson (March 8, 2023) © 2023
John Canning,Alan Broder,Robert Lafore | eBook ISBN: 9780137916191
eBook edition. 1 Month Subscription. Dành cho Cá nhân  |  Trường ĐH, Nhóm, Thư Viện: Gọi 0915920514 để báo giá Pearson, Vital Source eBook hoặc mua Sách In  

ISBN: 9780134855684
Giá bán lẻ: 349,000₫
Số lượng:
Tổng tiền:
Giá có thể thay đổi bất kỳ khi nào.
Thời hạn giao hàng: 03 ngày làm việc với sách digital và 30 ngày với sách in. Gọi để được Tư vấn Giáo Trình.

Mô tả sản phẩm


TÌM HIỂU CÁCH SỬ DỤNG CẤU TRÚC DỮ LIỆU KHI VIẾT CHƯƠNG TRÌNH VÀ Thuật toán PYTHON HIỆU SUẤT CAO

Phần giới thiệu thực tế về cấu trúc dữ liệu và thuật toán này có thể giúp mọi lập trình viên muốn viết phần mềm hiệu quả hơn. Dựa trên hướng dẫn dựa trên Java huyền thoại của Robert Lafore, cuốn sách này giúp sinh viên hiểu chính xác cách thức hoạt động của các cấu trúc dữ liệu và thuật toán. Bạn sẽ tìm hiểu cách áp dụng chúng một cách hiệu quả bằng ngôn ngữ Python cực kỳ phổ biến và mở rộng quy mô mã của bạn để xử lý các thách thức về dữ liệu lớn ngày nay.

Xuyên suốt, các tác giả tập trung vào các ví dụ thực tế, truyền đạt các ý tưởng chính bằng hình ảnh trực quan, tương tác, đồng thời giới hạn độ phức tạp và toán học ở những gì bạn cần để cải thiện hiệu suất. Từng bước, họ giới thiệu mảng, sắp xếp, ngăn xếp, hàng đợi, danh sách liên kết, đệ quy, cây nhị phân, cây 2-3-4, bảng băm, cấu trúc dữ liệu không gian, đồ thị, v.v. Các ví dụ về mã và hình minh họa của chúng rất rõ ràng, bạn có thể hiểu chúng ngay cả khi bạn là người mới bắt đầu hoặc bạn đã có kinh nghiệm với các ngôn ngữ hướng đối tượng hoặc thủ tục khác.

Xây dựng các kỹ năng khoa học máy tính cốt lõi giúp bạn vượt ra ngoài phạm vi “viết mã” đơn thuần
Tìm hiểu cách cấu trúc dữ liệu làm cho chương trình (và lập trình viên) hiệu quả hơn
Xem cách tổ chức dữ liệu và thuật toán ảnh hưởng đến mức độ bạn có thể làm với tài nguyên máy tính của ngày hôm nay và ngày mai
Phát triển kỹ năng triển khai cấu trúc dữ liệu mà bạn có thể sử dụng bằng bất kỳ ngôn ngữ nào
Chọn (các) cấu trúc dữ liệu và thuật toán tốt nhất cho từng vấn đề lập trình—và nhận ra những vấn đề nào cần tránh
Cấu trúc dữ liệu & thuật toán trong Python chứa đầy các ví dụ, câu hỏi ôn tập, bài tập cá nhân và nhóm, thử nghiệm suy nghĩ và các dự án lập trình dài hơn. Đây là cuốn sách lý tưởng cho cả môi trường tự học và lớp học, đồng thời có thể dùng làm văn bản chính hoặc phần bổ sung cho bài thuyết trình trang trọng hơn.

Tài nguyên dành cho Giảng viên: Các slide bài giảng và giải pháp dự án cho một số chương đầu tiên có sẵn trên Trung tâm Nguồn lực dành cho Giảng viên của Pearson. Đối với các câu hỏi và thông tin phụ trợ bổ sung, chẳng hạn như các slide bài giảng hoàn chỉnh và các giải pháp dự án lập trình, vui lòng liên hệ với các tác giả tại trang web của họ, https://datastructures.live.


1 Overview  . . . 1

What Are Data Structures and Algorithms?. . . . . . . . . . . . . . . . . . . . . . . 1

Overview of Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Overview of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Some Definitions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Programming in Python.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Object-Oriented Programming.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 Arrays  . . . 29

The Array Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Using Python Lists to Implement the Array Class.. . . . . . . . . . . . . . . . . 37

The OrderedArray Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . 47

Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Python Code for an OrderedArray Class.. . . . . . . . . . . . . . . . . . . . . . . . 52

Logarithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Storing Objects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Big O Notation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Why Not Use Arrays for Everything?.. . . . . . . . . . . . . . . . . . . . . . . . . . 69

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3 Simple Sorting  . . . 75

How Would You Do It?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Selection Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Insertion Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Comparing the Simple Sorts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4 Stacks and Queues  . . . 103

Different Structures for Different Use Cases.. . . . . . . . . . . . . . . . . . . . . 103

Stacks.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Priority Queues.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Parsing Arithmetic Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

5 Linked Lists . . .  157

Links.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

The LinkedList Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

A Simple Linked List.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Double-Ended Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Linked List Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Abstract Data Types and Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Ordered Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

Doubly Linked Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

Insertion and Deletion at the Ends.. . . . . . . . . . . . . . . . . . . . . . . 201

Insertion and Deletion in the Middle.. . . . . . . . . . . . . . . . . . . . . 204

Doubly Linked List as Basis for Deques.. . . . . . . . . . . . . . . . . . . . 208

Circular Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Iterators.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

6 Recursion  . . . 229

Triangular Numbers.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Factorials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

Anagrams.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

A Recursive Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

The Tower of Hanoi.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

Sorting with mergesort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

Eliminating Recursion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

Some Interesting Recursive Applications.. . . . . . . . . . . . . . . . . . . . . . . 275

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

7 Advanced Sorting  . . . 285

Shellsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

Partitioning.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

Quicksort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

Radix Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Timsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

8 Binary Trees . . .  335

Why Use Binary Trees?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

Tree Terminology.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

An Analogy.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

How Do Binary Search Trees Work?.. . . . . . . . . . . . . . . . . . . . . . . . . . 341

Finding a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Inserting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350

Traversing the Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

Finding Minimum and Maximum Key Values. . . . . . . . . . . . . . . . . . . 365

Deleting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

The Efficiency of Binary Search Trees.. . . . . . . . . . . . . . . . . . . . . . . . . 375

Trees Represented as Arrays.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

Printing Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

Duplicate Keys.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

The BinarySearchTreeTester.py Program. . . . . . . . . . . . . . . . . . . . . . . . 382

The Huffman Code.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

9 2-3-4 Trees and External Storage  . . . 401

Introduction to 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

The Tree234 Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Python Code for a 2-3-4 Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

Efficiency of 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

2-3 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432

External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

10 AVL and Red-Black Trees 463 Our Approach to the Discussion.. . . 463

Balanced and Unbalanced Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

The Efficiency of AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

Using the Red-Black Tree Visualization Tool.. . . . . . . . . . . . . . . . . . . . 489

Experimenting with the Visualization Tool.. . . . . . . . . . . . . . . . . . . . . 492

Rotations in Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497

Inserting a New Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498

Deletion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

The Efficiency of Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

2-3-4 Trees and Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

Red-Black Tree Implementation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521

11 Hash Tables 525 Introduction to Hashing.. . . . . . . . . . . . . . . . . 526

Open Addressing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536

Separate Chaining.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565

Hash Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575

Hashing Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

Hashing and External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595

12 Spatial Data Structures 597 Spatial Data.. . . . . .. . . . . .  . . . . . . 597

Computing Distances Between Points.. . . . . . . . . . . . . . . . . . . . . . . . . 599

Circles and Bounding Boxes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601

Searching Spatial Data.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611

Lists of Points.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

Grids.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617

Quadtrees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633

Theoretical Performance and Optimizations.. . . . . . . . . . . . . . . . . . . . 656

Practical Considerations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656

Further Extensions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663

13 Heaps 665 Introduction to Heaps.. . . . . . . . . . . . . . . . . . . .. . . . . 666

The Heap Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Python Code for Heaps.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677

A Tree-Based Heap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684

Heapsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686

Order Statistics.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703

14 Graphs 705 Introduction to Graphs.. . . . . . .  . . . . . . . . . . . . . . . . 705

Traversal and Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718

Minimum Spanning Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734

Topological Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740

Connectivity in Directed Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 753

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763

15 Weighted Graphs  . . . 767

Minimum Spanning Tree with Weighted Graphs.. . . . . . . . . . . . . . . . . 767

The All-Pairs Shortest-Path Problem.. . . . . . . . . . . . . . . . . . . . . . . . . . 797

Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Intractable Problems.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809

16 What to Use and Why 813 Analyzing the Problem.. . . . . .  . . . . . 814

Foundational Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818

Special-Ordering Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 824

Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826

Specialty Data Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828

External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829

Onward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831

A Running the Visualizations  . . . 833

B Further Reading . . .  841

C Answers to Questions  . . . 845

9780134855684, TOC, 8/3/2022

TỔNG QUAN SÁCH

TÌM HIỂU CÁCH SỬ DỤNG CẤU TRÚC DỮ LIỆU KHI VIẾT CHƯƠNG TRÌNH VÀ Thuật toán PYTHON HIỆU SUẤT CAO

Phần giới thiệu thực tế về cấu trúc dữ liệu và thuật toán này có thể giúp mọi lập trình viên muốn viết phần mềm hiệu quả hơn. Dựa trên hướng dẫn dựa trên Java huyền thoại của Robert Lafore, cuốn sách này giúp sinh viên hiểu chính xác cách thức hoạt động của các cấu trúc dữ liệu và thuật toán. Bạn sẽ tìm hiểu cách áp dụng chúng một cách hiệu quả bằng ngôn ngữ Python cực kỳ phổ biến và mở rộng quy mô mã của bạn để xử lý các thách thức về dữ liệu lớn ngày nay.

Xuyên suốt, các tác giả tập trung vào các ví dụ thực tế, truyền đạt các ý tưởng chính bằng hình ảnh trực quan, tương tác, đồng thời giới hạn độ phức tạp và toán học ở những gì bạn cần để cải thiện hiệu suất. Từng bước, họ giới thiệu mảng, sắp xếp, ngăn xếp, hàng đợi, danh sách liên kết, đệ quy, cây nhị phân, cây 2-3-4, bảng băm, cấu trúc dữ liệu không gian, đồ thị, v.v. Các ví dụ về mã và hình minh họa của chúng rất rõ ràng, bạn có thể hiểu chúng ngay cả khi bạn là người mới bắt đầu hoặc bạn đã có kinh nghiệm với các ngôn ngữ hướng đối tượng hoặc thủ tục khác.

Xây dựng các kỹ năng khoa học máy tính cốt lõi giúp bạn vượt ra ngoài phạm vi “viết mã” đơn thuần
Tìm hiểu cách cấu trúc dữ liệu làm cho chương trình (và lập trình viên) hiệu quả hơn
Xem cách tổ chức dữ liệu và thuật toán ảnh hưởng đến mức độ bạn có thể làm với tài nguyên máy tính của ngày hôm nay và ngày mai
Phát triển kỹ năng triển khai cấu trúc dữ liệu mà bạn có thể sử dụng bằng bất kỳ ngôn ngữ nào
Chọn (các) cấu trúc dữ liệu và thuật toán tốt nhất cho từng vấn đề lập trình—và nhận ra những vấn đề nào cần tránh
Cấu trúc dữ liệu & thuật toán trong Python chứa đầy các ví dụ, câu hỏi ôn tập, bài tập cá nhân và nhóm, thử nghiệm suy nghĩ và các dự án lập trình dài hơn. Đây là cuốn sách lý tưởng cho cả môi trường tự học và lớp học, đồng thời có thể dùng làm văn bản chính hoặc phần bổ sung cho bài thuyết trình trang trọng hơn.

Tài nguyên dành cho Giảng viên: Các slide bài giảng và giải pháp dự án cho một số chương đầu tiên có sẵn trên Trung tâm Nguồn lực dành cho Giảng viên của Pearson. Đối với các câu hỏi và thông tin phụ trợ bổ sung, chẳng hạn như các slide bài giảng hoàn chỉnh và các giải pháp dự án lập trình, vui lòng liên hệ với các tác giả tại trang web của họ, https://datastructures.live.

MỤC LỤC

1 Overview  . . . 1

What Are Data Structures and Algorithms?. . . . . . . . . . . . . . . . . . . . . . . 1

Overview of Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Overview of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Some Definitions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Programming in Python.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Object-Oriented Programming.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 Arrays  . . . 29

The Array Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Using Python Lists to Implement the Array Class.. . . . . . . . . . . . . . . . . 37

The OrderedArray Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . 47

Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Python Code for an OrderedArray Class.. . . . . . . . . . . . . . . . . . . . . . . . 52

Logarithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Storing Objects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Big O Notation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Why Not Use Arrays for Everything?.. . . . . . . . . . . . . . . . . . . . . . . . . . 69

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3 Simple Sorting  . . . 75

How Would You Do It?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Selection Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Insertion Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Comparing the Simple Sorts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4 Stacks and Queues  . . . 103

Different Structures for Different Use Cases.. . . . . . . . . . . . . . . . . . . . . 103

Stacks.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Priority Queues.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Parsing Arithmetic Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

5 Linked Lists . . .  157

Links.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

The LinkedList Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

A Simple Linked List.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Double-Ended Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Linked List Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Abstract Data Types and Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

Ordered Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

Doubly Linked Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

Insertion and Deletion at the Ends.. . . . . . . . . . . . . . . . . . . . . . . 201

Insertion and Deletion in the Middle.. . . . . . . . . . . . . . . . . . . . . 204

Doubly Linked List as Basis for Deques.. . . . . . . . . . . . . . . . . . . . 208

Circular Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Iterators.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

6 Recursion  . . . 229

Triangular Numbers.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Factorials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

Anagrams.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

A Recursive Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

The Tower of Hanoi.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

Sorting with mergesort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

Eliminating Recursion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

Some Interesting Recursive Applications.. . . . . . . . . . . . . . . . . . . . . . . 275

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

7 Advanced Sorting  . . . 285

Shellsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

Partitioning.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

Quicksort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

Radix Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Timsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

8 Binary Trees . . .  335

Why Use Binary Trees?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

Tree Terminology.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

An Analogy.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

How Do Binary Search Trees Work?.. . . . . . . . . . . . . . . . . . . . . . . . . . 341

Finding a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

Inserting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350

Traversing the Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

Finding Minimum and Maximum Key Values. . . . . . . . . . . . . . . . . . . 365

Deleting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

The Efficiency of Binary Search Trees.. . . . . . . . . . . . . . . . . . . . . . . . . 375

Trees Represented as Arrays.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

Printing Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

Duplicate Keys.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

The BinarySearchTreeTester.py Program. . . . . . . . . . . . . . . . . . . . . . . . 382

The Huffman Code.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

9 2-3-4 Trees and External Storage  . . . 401

Introduction to 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

The Tree234 Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Python Code for a 2-3-4 Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

Efficiency of 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

2-3 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432

External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

10 AVL and Red-Black Trees 463 Our Approach to the Discussion.. . . 463

Balanced and Unbalanced Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

The Efficiency of AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

Using the Red-Black Tree Visualization Tool.. . . . . . . . . . . . . . . . . . . . 489

Experimenting with the Visualization Tool.. . . . . . . . . . . . . . . . . . . . . 492

Rotations in Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497

Inserting a New Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498

Deletion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

The Efficiency of Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

2-3-4 Trees and Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

Red-Black Tree Implementation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521

11 Hash Tables 525 Introduction to Hashing.. . . . . . . . . . . . . . . . . 526

Open Addressing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536

Separate Chaining.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565

Hash Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575

Hashing Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

Hashing and External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595

12 Spatial Data Structures 597 Spatial Data.. . . . . .. . . . . .  . . . . . . 597

Computing Distances Between Points.. . . . . . . . . . . . . . . . . . . . . . . . . 599

Circles and Bounding Boxes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601

Searching Spatial Data.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611

Lists of Points.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

Grids.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617

Quadtrees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633

Theoretical Performance and Optimizations.. . . . . . . . . . . . . . . . . . . . 656

Practical Considerations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656

Further Extensions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663

13 Heaps 665 Introduction to Heaps.. . . . . . . . . . . . . . . . . . . .. . . . . 666

The Heap Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Python Code for Heaps.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677

A Tree-Based Heap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684

Heapsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686

Order Statistics.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703

14 Graphs 705 Introduction to Graphs.. . . . . . .  . . . . . . . . . . . . . . . . 705

Traversal and Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718

Minimum Spanning Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734

Topological Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740

Connectivity in Directed Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 753

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763

15 Weighted Graphs  . . . 767

Minimum Spanning Tree with Weighted Graphs.. . . . . . . . . . . . . . . . . 767

The All-Pairs Shortest-Path Problem.. . . . . . . . . . . . . . . . . . . . . . . . . . 797

Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Intractable Problems.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801

Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805

Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806

Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808

Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809

16 What to Use and Why 813 Analyzing the Problem.. . . . . .  . . . . . 814

Foundational Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818

Special-Ordering Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 824

Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826

Specialty Data Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828

External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829

Onward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831

A Running the Visualizations  . . . 833

B Further Reading . . .  841

C Answers to Questions  . . . 845

9780134855684, TOC, 8/3/2022

-%
0₫ 0₫
0915920514
0915920514