Packt.Cplusplus.Data.Structures.and.Algorithm.Design.Principles.....pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：10.58M 资料格式：pdf 举报版权申诉

cqiao0-11954109-4744302543298409367.pdf-第1页.png

第1页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第2页.png

第2页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第3页.png

第3页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第4页.png

第4页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第5页.png

第5页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第6页.png

第6页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第7页.png

第7页 / 共626页

cqiao0-11954109-4744302543298409367.pdf-第8页.png

第8页 / 共626页

Cover

Table of Contents

Preface

Chapter 1: Lists, Stacks, and Queues

Introduction

Contiguous Versus Linked Data Structures

Contiguous Data Structures

Linked Data Structures

Comparison

Limitations of C-style Arrays

std::array

Exercise 1: Implementing a Dynamic Sized Array

Exercise 2: A General-Purpose and Fast Data Storage Container Builder

std::vector

std::vector – Variable Length Array

Allocators for std::vector

std::forward_list

Inserting and Deleting Elements in forward_list

Other Operations on forward_list

Exercise 3: Conditional Removal of Elements from a Linked List Using remove_if

Iterators

Exercise 4: Exploring Different Types of Iterators

Exercise 5: Building a Basic Custom Container

Activity 1: Implementing a Song Playlist

std::list

Common Functions for std::list

Exercise 6: Insertion and Deletion Functions for std::list

Bidirectional Iterators

Iterator Invalidation for Different Containers

Activity 2: Simulating a Card Game

std::deque – Special Version of std::vector

The Structure of Deque

Container Adaptors

std::stack

std::queue

std::priority_queue

Iterators for Adaptors

Benchmarking

Activity 3: Simulating a Queue for a Shared Printer in an Office

Summary

Chapter 2: Trees, Heaps, and Graphs

Introduction

Non-Linear Problems

Hierarchical Problems

Cyclic Dependencies

Tree – It's Upside Down!

Exercise 7: Creating an Organizational Structure

Traversing Trees

Exercise 8: Demonstrating Level Order Traversal

Variants of Trees

Binary Search Tree

Time Complexities of Operations on a Tree

Exercise 9: Implementing a Binary Search Tree

Balanced Tree

N-ary Tree

Activity 4: Create a Data Structure for a Filesystem

Heaps

Heap Operations

Exercise 10: Streaming Median

Activity 5: K-Way Merge Using Heaps

Graphs

Representing a Graph as an Adjacency Matrix

Exercise 11: Implementing a Graph and Representing it as an Adjacency Matrix

Representing a Graph as an Adjacency List

Exercise 12: Implementing a Graph and Representing it as an Adjacency List

Summary

Chapter 3: Hash Tables and Bloom Filters

Introduction

Hash Tables

Hashing

Exercise 13: Basic Dictionary for Integers

Collisions in Hash Tables

Close Addressing – Chaining

Exercise 14: Hash Table with Chaining

Open Addressing

Perfect Hashing – Cuckoo Hashing

Exercise 15: Cuckoo Hashing

C++ Hash Tables

Exercise 16: Hash Tables Provided by STL

Activity 6: Mapping Long URLs to Short URLs

Bloom Filters

Exercise 17: Creating Bloom Filters

Activity 7: Email Address Validator

Summary

Chapter 4: Divide and Conquer

Introduction

Binary Search

Exercise 18: Binary Search Benchmarks

Activity 8: Vaccinations

Understanding the Divide-and-Conquer Approach

Sorting Using Divide and Conquer

Merge Sort

Exercise 19: Merge Sort

Quicksort

Exercise 20: Quicksort

Activity 9: Partial Sorting

Linear Time Selection

Exercise 21: Linear Time Selection

C++ Standard Library Tools for Divide and Conquer

Dividing and Conquering at a Higher Abstraction Level – MapReduce

The Map and Reduce Abstractions

Exercise 22: Map and Reduce in the C++ Standard Library

Integrating the Parts – Using a MapReduce Framework

Exercise 23: Checking Primes Using MapReduce

Activity 10: Implementing WordCount in MapReduce

Summary

Chapter 5: Greedy Algorithms

Introduction

Basic Greedy Algorithms

Shortest-Job-First Scheduling

Exercise 24: Shortest-Job-First Scheduling

The Knapsack Problem(s)

The Knapsack Problem

The Fractional Knapsack Problem

Exercise 25: Fractional Knapsack Problem

Activity 11: The Interval Scheduling Problem

Requirements for Greedy Algorithms

The Minimum Spanning Tree (MST) Problem

Disjoint-Set (or Union-Find) Data Structures

Exercise 26: Kruskal's MST Algorithm

The Vertex Coloring Problem

Exercise 27: Greedy Graph Coloring

Activity 12: The Welsh-Powell Algorithm

Summary

Chapter 6: Graph Algorithms I

Introduction

The Graph Traversal Problem

Breadth-First Search

Exercise 28: Implementing BFS

Depth-First Search

Exercise 29: Implementing DFS

Activity 13: Finding out Whether a Graph is Bipartite Using DFS

Prim's MST Algorithm

Exercise 30: Prim's Algorithm

Dijkstra's Shortest Path Algorithm

Exercise 31: Implementing Dijkstra's Algorithm

Activity 14: Shortest Path in New York

Summary

Chapter 7: Graph Algorithms II

Introduction

Revisiting the Shortest Path Problem

The Bellman-Ford Algorithm

Exercise 32: Implementing the Bellman-Ford Algorithm (Part I)

The Bellman-Ford Algorithm (Part II) – Negative Weight Cycles

Exercise 33: Implementing the Bellman-Ford Algorithm (Part II)

Activity 15: Greedy Robot

Johnson's Algorithm

Exercise 34: Implementing Johnson's Algorithm

Activity 16: Randomized Graph Statistics

Strongly Connected Components

Connectivity in Directed and Undirected Graphs

Kosaraju's Algorithm

Exercise 35: Implementing Kosaraju's Algorithm

Activity 17: Maze-Teleportation Game

Choosing the Right Approach

Summary

Chapter 8: Dynamic Programming I

Introduction

What Is Dynamic Programming?

Memoization – The Top-Down Approach

Tabulation – the Bottom-Up Approach

Subset Sum Problem

Solving the Subset Sum Problem – Step 1: Evaluating the Need for DP

Step 2 – Defining the States and the Base Cases

Step 2.a: Brute Force

Exercise 36: Solving the Subset Sum Problem by Using the Brute-Force Approach

Step 2.b: Optimizing Our Approach – Backtracking

Exercise 37: Solving the Subset Sum Problem by Using Backtracking

Step 3: Memoization

Devising a Caching Scheme

Exercise 38: Solving the Subset Sum Problem by Using Memoization

Step 4: Tabulation

Exercise 39: Solving the Subset Sum Problem by Using Tabulation

Activity 18: Travel Itinerary

Dynamic Programming on Strings and Sequences

The Longest Common Subsequence Problem

Exercise 40: Finding the Longest Common Subsequence by Using the Brute-Force Approach

First Steps Toward Optimization – Finding the Optimal Substructure

Activity 19: Finding the Longest Common Subsequence by Using Memoization

From Top-Down to Bottom-Up – Converting the Memoized Approach into a Tabulated Approach

Activity 20: Finding the Longest Common Subsequence Using Tabulation

Activity 21: Melodic Permutations

Summary

Chapter 9: Dynamic Programming II

Introduction

An Overview of P versus NP

Reconsidering the Subset Sum Problem

The Knapsack Problem

0-1 Knapsack – Extending the Subset Sum Algorithm

Exercise 41: 0-1 Knapsack Problem

Unbounded Knapsack

State Space Reduction

Exercise 42: Unbounded Knapsack

Activity 22: Maximizing Profit

Graphs and Dynamic Programming

Reconsidering the Bellman-Ford Algorithm

Approaching the Shortest Path Problem as a DP Problem

Exercise 43: Single-Source Shortest Paths (Memoization)

All-Pairs Shortest Path

The Floyd-Warshall Algorithm

Exercise 44: Implementing the Floyd-Warshall Algorithm

Activity 23: Residential Roads

Summary

Appendix

Index

C++ Data Structures and Algorithm Design Principles Leverage the power of modern C++ to build robust and scalable applications John Carey Shreyans Doshi Payas Rajan

C++ Data Structures and Algorithm Design Principles Copyright © 2019 Packt Publishing All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews. Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the authors, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book. Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information. Authors: John Carey, Shreyans Doshi, and Payas Rajan Technical Reviewer: Shubham Srivastava Managing Editor: Aniket Shedge Acquisitions Editors: Kunal Sawant and Sneha Shinde Production Editor: Shantanu Zagade Editorial Board: Shubhopriya Banerjee, Bharat Botle, Ewan Buckingham, Mahesh Dhyani, Manasa Kumar, Alex Mazonowicz, Bridget Neale, Dominic Pereira, Shiny Poojary, Abhisekh Rane, Erol Staveley, Ankita Thakur, Nitesh Thakur, and Jonathan Wray. First Published: October 2019 Production Reference: 1311019 ISBN: 978-1-83882-884-4 Published by Packt Publishing Ltd. Livery Place, 35 Livery Street Birmingham B3 2PB, UK

Table of Contents Preface Chapter 1: Lists, Stacks, and Queues i 1 Introduction .................................................................................................... 2 Contiguous Versus Linked Data Structures ................................................ 2 Contiguous Data Structures ............................................................................... 3 Linked Data Structures ....................................................................................... 4 Comparison .......................................................................................................... 6 Limitations of C-style Arrays .............................................................................. 7 std::array ......................................................................................................... 7 Exercise 1: Implementing a Dynamic Sized Array .......................................... 12 Exercise 2: A General-Purpose and Fast Data Storage Container Builder ............................................................................................... 17 std::vector ..................................................................................................... 19 std::vector – Variable Length Array ................................................................. 19 Allocators for std::vector ................................................................................... 23 std::forward_list ........................................................................................... 24 Inserting and Deleting Elements in forward_list ............................................ 24 Other Operations on forward_list .................................................................... 26 Exercise 3: Conditional Removal of Elements from a Linked List Using remove_if ................................................................ 27 Iterators ........................................................................................................ 31 Exercise 4: Exploring Different Types of Iterators ......................................... 32 Exercise 5: Building a Basic Custom Container .............................................. 34 Activity 1: Implementing a Song Playlist ......................................................... 39

std::list ........................................................................................................... 40 Common Functions for std::list ........................................................................ 40 Exercise 6: Insertion and Deletion Functions for std::list ............................. 41 Bidirectional Iterators ....................................................................................... 43 Iterator Invalidation for Different Containers ............................................... 43 Activity 2: Simulating a Card Game ................................................................. 44 std::deque – Special Version of std::vector ............................................... 45 The Structure of Deque ..................................................................................... 45 Container Adaptors ..................................................................................... 48 std::stack ............................................................................................................. 49 std::queue ........................................................................................................... 50 std::priority_queue ............................................................................................ 51 Iterators for Adaptors ....................................................................................... 51 Benchmarking .............................................................................................. 51 Activity 3: Simulating a Queue for a Shared Printer in an Office ................. 52 Summary ....................................................................................................... 53 Chapter 2: Trees, Heaps, and Graphs 55 Introduction .................................................................................................. 56 Non-Linear Problems .................................................................................. 56 Hierarchical Problems ....................................................................................... 57 Cyclic Dependencies .......................................................................................... 58 Tree – It's Upside Down! .............................................................................. 59 Exercise 7: Creating an Organizational Structure .......................................... 59 Traversing Trees ................................................................................................. 63 Exercise 8: Demonstrating Level Order Traversal ......................................... 65 Variants of Trees .......................................................................................... 66 Binary Search Tree ............................................................................................. 67

Time Complexities of Operations on a Tree ................................................... 71 Exercise 9: Implementing a Binary Search Tree ............................................. 71 Balanced Tree ..................................................................................................... 76 N-ary Tree ........................................................................................................... 79 Activity 4: Create a Data Structure for a Filesystem ...................................... 80 Heaps ............................................................................................................. 81 Heap Operations ................................................................................................ 82 Exercise 10: Streaming Median ........................................................................ 85 Activity 5: K-Way Merge Using Heaps .............................................................. 88 Graphs ........................................................................................................... 89 Representing a Graph as an Adjacency Matrix .............................................. 90 Exercise 11: Implementing a Graph and Representing it as an Adjacency Matrix .................................................................................. 91 Representing a Graph as an Adjacency List ................................................... 94 Exercise 12: Implementing a Graph and Representing it as an Adjacency List ....................................................................................... 94 Summary ....................................................................................................... 98 Chapter 3: Hash Tables and Bloom Filters 101 Introduction ................................................................................................ 102 Hash Tables ................................................................................................ 102 Hashing ............................................................................................................ 103 Exercise 13: Basic Dictionary for Integers .................................................... 104 Collisions in Hash Tables ........................................................................... 108 Close Addressing – Chaining .......................................................................... 108 Exercise 14: Hash Table with Chaining ......................................................... 109 Open Addressing ............................................................................................. 114 Perfect Hashing – Cuckoo Hashing ............................................................... 116 Exercise 15: Cuckoo Hashing ......................................................................... 118

C++ Hash Tables ......................................................................................... 126 Exercise 16: Hash Tables Provided by STL ................................................... 128 Activity 6: Mapping Long URLs to Short URLs ............................................. 133 Bloom Filters .............................................................................................. 134 Exercise 17: Creating Bloom Filters .............................................................. 136 Activity 7: Email Address Validator ............................................................... 140 Summary ..................................................................................................... 140 Chapter 4: Divide and Conquer 143 Introduction ................................................................................................ 144 Binary Search ............................................................................................. 146 Exercise 18: Binary Search Benchmarks ...................................................... 148 Activity 8: Vaccinations ................................................................................... 152 Understanding the Divide-and-Conquer Approach ............................... 154 Sorting Using Divide and Conquer ........................................................... 155 Merge Sort ....................................................................................................... 156 Exercise 19: Merge Sort .................................................................................. 157 Quicksort .......................................................................................................... 160 Exercise 20: Quicksort .................................................................................... 162 Activity 9: Partial Sorting ................................................................................ 166 Linear Time Selection ..................................................................................... 168 Exercise 21: Linear Time Selection ................................................................ 170 C++ Standard Library Tools for Divide and Conquer ............................. 176 Dividing and Conquering at a Higher Abstraction Level – MapReduce .................................................................................... 178 The Map and Reduce Abstractions ............................................................... 179 Exercise 22: Map and Reduce in the C++ Standard Library ....................... 180 Integrating the Parts – Using a MapReduce Framework ........................... 183

Exercise 23: Checking Primes Using MapReduce ........................................ 184 Activity 10: Implementing WordCount in MapReduce .............................. 189 Summary ..................................................................................................... 193 Chapter 5: Greedy Algorithms 195 Introduction ................................................................................................ 196 Basic Greedy Algorithms ........................................................................... 197 Shortest-Job-First Scheduling ........................................................................ 197 Exercise 24: Shortest-Job-First Scheduling ................................................... 198 The Knapsack Problem(s) .......................................................................... 201 The Knapsack Problem ................................................................................... 201 The Fractional Knapsack Problem ................................................................ 202 Exercise 25: Fractional Knapsack Problem .................................................. 203 Activity 11: The Interval Scheduling Problem .............................................. 207 Requirements for Greedy Algorithms .......................................................... 210 The Minimum Spanning Tree (MST) Problem .............................................. 210 Disjoint-Set (or Union-Find) Data Structures ............................................... 214 Exercise 26: Kruskal's MST Algorithm ........................................................... 220 The Vertex Coloring Problem ................................................................... 228 Exercise 27: Greedy Graph Coloring ............................................................. 229 Activity 12: The Welsh-Powell Algorithm ..................................................... 236 Summary ..................................................................................................... 240 Chapter 6: Graph Algorithms I 243 Introduction ................................................................................................ 244 The Graph Traversal Problem .................................................................. 246 Breadth-First Search ....................................................................................... 247 Exercise 28: Implementing BFS ..................................................................... 249

分享到：

赞收藏

资料库

Packt.Cplusplus.Data.Structures.and.Algorithm.Design.Principles.....pdf

相关推荐

开发技术

热门标签

最新资料