What Is a Vector Iterator?

The book uses object-oriented C ++ language as the description language, and uses the design concept of STL as the description and implementation framework. It is rich in content, concise in narration, and emphasizes both theory and practice. Each chapter is designed with application examples, data structures, and algorithm experiments. Teachers provide electronic courseware and course experiment data for free.

Data Structure (STL Framework)

Data structure (STL framework) ^[1]

Chapter 1 Introduction to Algorithms and Data Structures 1

1.1 Algorithms and their concepts of complexity 1

1.1.1 Algorithms and Programs 1

1.1.2 Concept of Algorithm Complexity 1

1.1.3 Asymptotic behavior of algorithm complexity 2

1.2 Data Structures and Abstract Data Types 3

1.3 Describe data structures and algorithms in C ++ 4

1.3.1 Pointers and References 4

1.3.2 Function and Parameter Passing 4

1.3.3 C ++ Classes 5

1.3.4 Class Objects 6

1.3.5 Template 6

1.3.6 Dynamic Storage Allocation 7

1.4 Recursion 8

1.5 Standard Template Library STL and Generic Algorithms 9

1.5.1 STL Overview 9

1.5.2 Container 10

1.5.3 Iterators

1.5.4 Generic Algorithms 11

1.5.5 Function Objects

1.6 Application Examples 19

1.6.1 Implementing Abstract Data Types with C ++ Classes

1.6.2 Design and Analysis of Sequential Search and Binary Search Algorithm 23

1.6.3 Design and Analysis of Recursive Algorithms 25

Problem 126

Data Structure and Algorithm Experiment 127

Data Structure and Algorithm Experiments 1.1 Real Coefficient Polynomial Problem 27

Data Structure and Algorithm Experiments 1.2 Plane Geometry Problems 28

Data Structure and Algorithm Experiments 1.3 m Number Problems 29

Chapter 2 Vectors 30

2.1 Basic Concepts of Vectors 30

2.2 Abstract Data Type Vectors

2.3 Iterators of Vectors

2.4 Vector Implementation Methods 31

2.5 Matrices and Multidimensional Vectors

2.6 High-precision integers 36

2.7 Application Examples 47

2.7.1 Searching for Common Elements Question 47

2.7.2 Same Color Block Recognition Problem 48

2.7.3 The Full Permutation Problem

Exercises 249

Data Structure and Algorithm Experiment 250

Data structure and algorithm experiment 2.1 Prefix and suffix and question 50 ^[1]

Data Structure and Algorithm Experiments 2.2 Voting Problems 50

Data Structure and Algorithm Experiments 2.3 Stable Marriage Problems 51

Data Structure and Algorithm Experiment 2.4 Triangulation of Convex Polygons 52

Directory Data Structure (STL Framework) Chapter 3 Deques 53

3.1 Basic Concepts of Double-Ended Queues

3.2 Abstract Data Type Double-Ended Queues 53

3.3 Implementation method of double-ended queue 54

3.4 Iterators for Double-Ended Queues

3.5 Application Examples 62

3.5.1 Simple Application of Double-Ended Queues

3.5.2 Convex Hull of Simple Polygons

Exercises 365

Data Structure and Algorithm Experiment 365

Data Structure and Algorithm Experiments 3.1 Queuing Tickets 65

Data Structure and Algorithm Experiments 3.2 Extreme Problems of Cyclic Vectors 66

Chapter 4 Linear Tables 68

4.1 Basic Concepts of Tables 68

4.2 Implementing Tables with Arrays

4.3 Implementing Tables with Pointers

4.3.1 A Method of Implementing a Single Linked List with a Pointer

4.3.2 Iterators for Single Linked Lists

4.4 Implementing Table 79 with Indirect Addressing

4.4.1 Basic Ideas of Indirect Addressing Method 79

4.4.2 Iterators for Indirect Addressing Tables

4.5 Implementing Tables with Cursors

4.5.1 Basic Ideas of Implementing Tables with Cursors

4.5.2 Iterators for Tables Implemented by Cursors

4.6 Circular Linked Lists

4.6.1 The basic idea of implementing a single-loop linked list

4.6.2 Iterators for single-loop linked lists

4.7 Double linked list

4.7.1 Basic Ideas of Implementing a Doubly Circular List

4.7.2 Iterators for doubly circular linked lists

4.8 Application Examples 101

4.8.1 Polynomial Functions

4.8.2 Josephus Arrangement Problem 106

Exercise 4107

Data Structure and Algorithm Experiment 4108

Data Structure and Algorithm Experiments 4.1 Real Coefficient Unary Polynomial Problem 108

Data Structure and Algorithm Experiments 4.2 Josephus Arrangement Problem 1109

Data Structure and Algorithm Experiments 4.3 Vector Classification Problems 110

Data Structure and Algorithm Experiments 4.4 Bar Graph Contour Problem 110

Data Structure and Algorithm Experiments 4.5 Josephus Arrangement Problem 2111

Chapter 5 Stacks 113

5.1 Basic Concepts of the Stack

5.2 Stack Implementation Methods

5.3 Application Examples

5.3.1 Division of Equivalence Classes 115

5.3.2 Simulating Recursive Problems

5.3.3 Circuit Board Wiring Problems

Exercise 5121

Data Structure and Algorithm Experiment 5121

Data Structure and Algorithm Experiment 5.1 Wagon Sequence Problem 121

Data Structure and Algorithm Experiment 5.2 One-Column Hanoi Tower Problem 122

Data Structure and Algorithm Experiment 5.3 Multi-stack Simulation Problem 123

Data Structure and Algorithm Experiments 5.4 Brother Problem 124

Chapter 6 Queues 125

6.1 Basic Concepts of Queues

6.2 Implementation methods of queues

6.3 Application Examples

6.3.1 Optimal Circuit Wiring Problems

6.3.2 Harmonious SMS Issues

Exercise 6130

Data Structure and Algorithm Experiment 6130

Data Structure and Algorithm Experiments 6.1 Group Queue Problems 130

Data Structure and Algorithm Experiment 6.2 Dual Stack Queue Problem 131

Data Structure and Algorithm Experiment 6.3 Monkey Peach Problem 132

Data Structure and Algorithm Experiments 6.4 Reverse Table Problem 132

Chapter 7 Sorting and Selection 134

7.1 Simple Sorting Algorithm

7.1.1 Bubble Sort Algorithm

7.1.2 Insert Sort Algorithm

7.1.3 Choosing a Sorting Algorithm

7.1.4 Computational Complexity of the Simple Sort Algorithm

7.2 Quick Sort Algorithms

7.2.1 Algorithmic Basic Ideas and Implementation

7.2.2 Algorithm Performance Analysis

7.2.3 Random Quick Sort Algorithm

7.3 Merge Sort Algorithm

7.3.1 Algorithm Basic Ideas and Implementations

7.3.2 Eliminating Recursion

7.3.3 Natural Merge Sort Algorithm

7.4 Linked List Sorting and Index Sorting Algorithms

7.4.1 Linked List Sorting Algorithm

7.4.2 Index Sort Algorithm

7.5 Linear Time Sorting Algorithms

7.5.1 Counting Sorting Algorithm 151 ^[3]

7.5.2 Bucket Sorting Algorithm

7.6 Median and k Small Element 152

7.6.1 Linear Time Selection Algorithm in the Average Case

7.6.2 Worst-Case Linear Time Selection Algorithms

7.7 Generic Sorting Algorithms

7.7.1 Generalization of Sorting Algorithms

7.7.2 Generic Merge Sort Algorithm

7.7.3 Generic Quick Sort Algorithm

7.7.4 Generic Selection Algorithms

7.8 Application Examples 161

7.8.1 Interval Coverage Problems

7.8.2 Oil Pipeline Problems

Exercise 7162

Data Structure and Algorithm Experiment 7163

Data Structure and Algorithm Experiments 7.1 Exchange and Sorting Problems 163

Data Structure and Algorithm Experiment 7.2 DNA Ranking Problem 163

Data Structure and Algorithm Experiment 7.3 Post Office Location Problem 164

Data Structure and Algorithm Experiment 7.4 Optimal Service Order Problem 165

Chapter 8 The Tree 166

8.1 Definition of Tree

8.2 Tree Traversal

8.3 Tree Representation

8.3.1 Parent Node Array Notation

8.3.2 Son List Representation

8.3.3 Left Son Right Brother Representation

8.4 Basic Concepts of Binary Trees

8.5 Binary Tree Operations

8.6 Binary Tree Implementation

8.6.1 Binary Tree Sequential Storage Structure

8.6.2 Node Degree Representation of Binary Trees

8.6.3 Implementing Binary Trees with Pointers

8.7 Trail Binary Tree 179

8.8 Application Examples-Signal Enhancement Device Layout Problems 181

Exercises 8184

Data Structure and Algorithm Experiment 8185

Data Structure and Algorithm Experiments 8.1 Layer Sequence List Problem 185

Data Structure and Algorithm Experiments 8.2 Recent Public Ancestry Problems 186

Data Structure and Algorithm Experiment 8.3 Subtree Problem 187

Data Structure and Algorithm Experiment 8.4 Isomorphic Binary Tree Problem 187

Data Structure and Algorithm Experiments

Chapter 9 Binary Search Tree 189

9.1 Ordered Sets and Binary Search Trees

9.1.1 Abstract Data Type Dictionary

9.1.2 Implementing dictionaries with arrays

9.1.3 Basic Concepts of Binary Search Trees

9.2 Implementing a Binary Search Tree

9.3 Iterators for Binary Search Trees

9.4 Efficiency of Binary Search Trees

9.5 Application Examples-Bar Graph Statistics Problem 207

Exercise 9209

Data Structure and Algorithm Experiment 9209

Data Structure and Algorithm Experiment 9.1 Boxing Problem 209

Data Structure and Algorithm Experiments 9.2 Circuit Board Connection Problems 210

Data Structure and Algorithm Experiments 9.3 Dictionary Problems 211

Chapter 10: Balanced Search Trees

10.1 Red and Black Trees

10.1.1 Definition and Properties of Red and Black Trees

10.1.2 Rotation Transformation

10.1.3 Red-Black Tree Insertion and Rebalancing

10.1.4 Red-Black Tree Deletion and Rebalancing

10.2 AVL Trees

10.2.1 Definition and Properties of AVL Trees

10.2.2 AVL Tree Insertion and Rebalancing

10.2.3 AVL Tree Deletion and Rebalancing

10.3 Application Examples

10.3.1 Bar Graph Statistics Problems

10.3.2 Dynamic Selection Problems

10.3.3 Josephus Arrangement Problem

Exercises 10233

Data Structure and Algorithm Experiment 10234

Data Structure and Algorithm Experiment 10.1 Reverse Count Problem 234

Data Structure and Algorithm Experiments 10.2k Successor Problem 234

Data Structure and Algorithm Experiment 10.3 Intersecting Strings in a Circle 235

Data Structure and Algorithm Experiments 10.4 Minimum Gap Problem 236

Data Structure and Algorithm Experiment 10.5 Graphic Perimeter Problem 237

Data Structure and Algorithm Experiment 10.6 Dynamic Selection Problem 237

Chapter 11 Collections 239

11.1 Basic Concepts of Collections

11.2 Implementing Sets with Bit Vectors

11.3 Implementing Sets with a Balanced Binary Search Tree

11.3.1 Applying Red and Black Trees Directly to Implement Collections

11.3.2 Generalization of Balanced Binary Search Trees

11.3.3 STL Compliant Collections

11.4 Multiple Sets

11.5 Generic Set Operations

11.6 Application Examples

11.6.1 Eratosthenes Sieve Method 259

11.6.2 Subsets and Problems

11.6.3 Spell Check Problems

11.6.4 Software Product Database Issues

Exercise 11262

Data Structure and Algorithm Experiment 11263

Data Structure and Algorithm Experiments 11.1 Half Set Problem 263

Data Structure and Algorithm Experiments 11.2 Bill Payment Problems 263

Data Structure and Algorithm Experiments 11.3 Poster Problems 264

Data Structure and Algorithm Experiments 11.4 Tricolor Game Problems 265

Chapter 12 Mapping 266

12.1 Basic Concepts of Mapping

12.2 Mapping with a balanced binary search tree

12.2.1 Further Generalization of Binary Search Trees

12.2.2 STL-Compliant Mapping

12.3 Multiple mappings

12.4 Application Examples

12.4.1 Population Distribution Statistics

12.4.2 Electronic Dictionary Problems

Problem 12278

Data Structure and Algorithm Experiment 12278

Data Structure and Algorithm Experiments 12.1 Work Salary Problem 278

Data Structure and Algorithm Experiments 12.2 Intelligent Analysis of Poker Games 279

Data Structure and Algorithm Experiment 12.3 Optimal Driving Route Problem 280

Data Structure and Algorithm Experiments 12.4 Inventory Adjustment Problem 281

Data Structure and Algorithm Experiments 12.5 Two-Character Word Frequency Analysis Problems 282

Data Structure and Algorithm Experiments 12.6 English Vocabulary Analysis Problems 283

Chapter 13 Hashing 285

13.1 Symbol Tables

13.2 Open Hashing

13.3 Closed Hashing

13.4 Efficiency of Hash Functions

13.5 Rehashing

13.6 Hash Sets

13.6.1 Implementing Collections with Hash Tables

13.6.2 Multiple Sets with Hash Tables

13.7 Hash Maps

13.7.1 Generalization of Open Lists

13.7.2 Mapping with Hash Tables

13.7.3 Implementing Multiple Maps with Hash Tables

13.8 Application Examples 309

13.8.1 String Frequency Statistics Problems

13.8.2 Spell Check Problems

13.8.3 Population Distribution Statistics

13.8.4 Electronic Dictionary Problems

Exercises 13313

Data Structure and Algorithm Experiment 13313

Data Structure and Algorithm Experiment 13.1 Pseudo-random Arrangement Problem 313

Data Structure and Algorithm Experiments 13.2 String Hashing Problem 314

Data Structure and Algorithm Experiments 13.3 English Text Analysis Problems 314

Data Structure and Algorithm Experiments 13.4 Longest Pattern String Problem 315

14. Heaps and Priority Queues

14.1 Basic Concepts of Priority Queues

14.2 Priority Trees and Heaps

14.3 Heap Sequential Storage

14.4 Heap-Related Algorithms

14.5 Heap Generic Algorithms

14.6 Implementing Priority Queues with the Heap

14.7 Parallelizable Priority 327

14.7.1 Definition of Left Partial Tree

14.7.2 Implementing Parallel Priority Queues Using Left Partial Trees

14.7.3 Generalizing Left Partial Trees

14.8 Application Examples

14.8.1 Comparison Modes for Priority Queues

14.8.2 Huffman Coding Problems

14.8.3 Event Scheduling

Exercises 14338

Data Structure and Algorithm Experiment 14338

Data Structure and Algorithm Experiment 14.1 Intersection Intersection Problems 338

Data Structure and Algorithm Experiments 14.2 Integer Dictionary Problems 338

Data Structure and Algorithm Experiments 14.3 Least Weight Language Problems 339

Data Structure and Algorithm Experiments 14.4 Binary Search Heap Problem 339

Data Structure and Algorithm Experiments 14.5 Interval Coverage Problem 340

Data Structure and Algorithm Experiments 14.6 Batch Job Scheduling Problems 341

Chapter 15 And Collection 342

15.1 Basic Concepts of Union Checks

15.2 Implementing and Checking Sets with Parent Node Vectors

15.3 Application Example-Offline Minimum Problem 346

Exercise 15347

Data Structure and Algorithm Experiment 15348

Data Structure and Algorithm Experiments 15.1 Binary Equation Problems 348

Data Structure and Algorithm Experiments 15.2 Network Connectivity Problems 349

Data Structure and Algorithm Experiments 15.3 Friends Questions 349

Data Structure and Algorithm Experiments 15.4 Equivalence Class Division Problem 350

Chapter 16 Picture 352

16.1 Basic Concepts of Graphs

16.2 Abstract Data Type Graphs

16.3 Representation of Graphs

16.3.1 Adjacency Matrix Representation

16.3.2 Adjacency List Notation

16.3.3 Compacting adjacency lists

16.4.Figure 357

16.4.1 Methods of Implementing Graphs with Adjacent Matrices

16.4.2 Vertex Iterators for Adjacent Matrix Graphs ^[3]