1. Home
2. Computer Science & IT
4. Data Structures

# Data Structures and Algorithm Analysis in C++, 4th edition

• Mark A. Weiss

4th edition

Chosen format
View all

ISBN-13: 9780132871174

Includes:
• Instant Access
• eBook

This product is not available in your country

### What's included

• Instant Access

• eBook

A digital version of the text you can personalize and read online or offline.

## Overview

Chapter 1 Programming: A General Overview 1

1.1 What’s This Book About? 1

1.2 Mathematics Review 2

1.2.1 Exponents 3

1.2.2 Logarithms 3

1.2.3 Series 4

1.2.4 Modular Arithmetic 5

1.2.5 The P Word 6

1.3 A Brief Introduction to Recursion 8

1.4 C++ Classes 12

1.4.1 Basic class Syntax 12

1.4.2 Extra Constructor Syntax and Accessors 13

1.4.3 Separation of Interface and Implementation 16

1.4.4 vector and string 19

1.5 C++ Details 21

1.5.1 Pointers 21

1.5.2 Lvalues, Rvalues, and References 23

1.5.3 Parameter Passing 25

1.5.4 Return Passing 27

1.5.5 std::swap and std::move 29

1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 30

1.5.7 C-style Arrays and Strings 35

1.6 Templates 36

1.6.1 Function Templates 37

1.6.2 Class Templates 38

1.6.3 Object, Comparable, and an Example 39

1.6.4 Function Objects 41

1.6.5 Separate Compilation of Class Templates 44

1.7 Using Matrices 44

1.7.1 The Data Members, Constructor, and Basic Accessors 44

1.7.2 operator[] 45

1.7.3 Big-Five 46

Summary 46

Exercises 46

References 48

Chapter 2 Algorithm Analysis 51

2.1 Mathematical Background 51

2.2 Model 54

2.3 What to Analyze 54

2.4 Running-Time Calculations 57

2.4.1 A Simple Example 58

2.4.2 General Rules 58

2.4.3 Solutions for the Maximum Subsequence Sum Problem 60

2.4.4 Logarithms in the Running Time 66

2.4.5 Limitations of Worst Case Analysis 70

Summary 70

Exercises 71

References 76

Chapter 3 Lists, Stacks, and Queues 77

3.1 Abstract Data Types (ADTs) 77

3.2.1 Simple Array Implementation of Lists 78

3.3 vector and list in the STL 80

3.3.1 Iterators 82

3.3.2 Example: Using erase on a List 83

3.3.3 const_iterators 84

3.4 Implementation of vector 86

3.5 Implementation of list 91

3.6.1 Stack Model 103

3.6.2 Implementation of Stacks 104

3.6.3 Applications 104

3.7.1 Queue Model 113

3.7.2 Array Implementation of Queues 113

3.7.3 Applications of Queues 115

Summary 116

## For teachers

All the material you need to teach your courses.

Discover teaching material