Wondershare EdrawMind
MindMap Gallery Data structure mind map
- 31
Data structure mind map
Data structure mind map, including algorithm performance analysis, linear structure review, binary tree basics, binary tree chain storage, binary tree traversal, etc.
Edited at 2022-11-16 19:16:18
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Data structure mind map
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
- Recommended to you
- Outline
data structure
introduction
What is data?
character
sound
image
.......
Main content
Storage method
Relationship description method
collection of operations
Type of data structure
Data logical structure
linear structure
Sequence table
linked list
queue
stack
nonlinear structure
Binary tree
heap
Tree
picture
hash table
.......
Data physical structure
sequential storage structure
chain storage structure
Other complex structures
What is an algorithm?
Ability to program computers to achieve
The same input corresponds to the same output
Can be completed within a limited number of steps
Algorithm performance analysis
Measuring algorithm performance
Number of basic operations
Algorithm performance comparison
space complexity
Fixed part
changing part
Linear Structure Review
Sequence table
linked list
queue
stack
Binary tree basics
Binary tree definition
Basic terminology of binary trees
Five basic forms of binary trees
Properties of binary trees
Classification of binary trees
full binary tree
perfect binary tree
time complexity
Sequentially stored binary trees and heaps
Sequential storage structure of binary tree
heap
small root pile
The small root heap is a complete binary tree stored in hierarchical order. The key value of each node is no greater than the key value of its left and right children.
dagendui
The large root heap is a complete binary tree stored in hierarchical order. The key value of each node is no less than the key value of its left and right children.
Main operations of the heap
Query the top element of the heap
insert an element
Delete the top element of the heap
Heap sort
small root pile
For a small root heap, the top element of the heap must be the smallest element. If you first create a small root heap from the sequence to be sorted, Then remove the elements from the heap in turn, and the new sequence obtained must be ordered from small to large. This solution requires opening up two memory spaces, one to store the small root heap and the other to store the result sequence.
dagendui
Concatenate the elements of the sequence into a large root heap. Replace the first element and the last element of the array, and reduce the number of array elements by 1. Resize the shrunken array into a large root heap. Repeat steps 2 and 3 until the data element in the array is 0.
Binary tree chain storage
Binary tree chain storage structure
Use a structure to store each node, and use two pointer fields to point to the two children respectively.
Binary tree node structure definition
Binary tree level traversal output
Algorithm 1: Access after dequeuing Create a queue and add the root node pointer to the queue. If the queue is not empty, delete a node pointer from the queue. Then access the node and store the left and right children of the node in the queue in sequence. Repeat step 2 until the queue is empty.
Algorithm 2: Access before queuing Create a queue, access the root node, and add the root node pointer to the queue. If the queue is not empty, delete a node pointer from the queue. If the node has a left child, access its left child node and add the left child node to the queue; if the node has a right child, access its right child node and add the right child node to the queue. Repeat step 2 until the queue is empty.
Sequential storage to chain storage code
Vertical output binary tree
Example of printing a binary tree vertically
Binary tree traversal
Level traversal
Preorder traversal
access root node Preorder traversal of left subtree Preorder traversal of right subtree
inorder traversal
In-order traversal of left subtree access root node In-order traversal of right subtree
Postorder traversal
Postorder traversal of left subtree Postorder traversal of right subtree access root node
Application of binary tree traversal
Application of preorder traversal
Quick sort
Find power set
Application of in-order traversal
Tower of Hanoi
Application of postorder traversal
Find the depth of a binary tree
algorithm:
Find the depth of the left subtree
Find the depth of the right subtree
The depth of the binary tree is the larger of the left and right subtrees plus 1.
Huffman coding
Basic concepts and storage of trees
tree definition
A tree is a collection of (≥0) nodes.
If =0, it is an empty tree.
If >0, there is a node called the root node (root). The remaining nodes are divided into multiple disjoint sub-sets.
These subsets are themselves trees, called subtrees of the root.
tree traversal
Breadth first traversal of tree
Enqueue the root node When the queue is not empty Dequeue and access the node Put the child nodes of this node into the queue in turn
Depth first traversal algorithm idea
Push the root node onto the stack When the queue is not empty Pop the stack and access the node Push the child nodes of this node onto the stack in turn
Back root traversal of tree
Each subtree of the node is visited in turn using post-root traversal. Visit the root node.
Eight Queens
picture
Basic concepts of graphs
Definition of graph
A graph is a collection of n vertices, and each vertex can have multiple predecessors and successors.
Undirected graph
If there is no difference between the predecessor and successor relationships of vertices in a graph, the graph is called an undirected graph.
directed graph
If the relationship between the predecessor and successor of a vertex in a graph is different, the graph is called a directed graph. The predecessor-successor relationship formed by a pair of vertices in a directed graph is called an ordered pair, directed edge (edge) or arc (arc).
The relationship between vertices and edges
If two vertices form an edge, the two vertices are said to be adjacent to each other, and the edge is said to be associated with the two vertices. The predecessor and successor vertices that constitute a directed edge are called the starting point and end point of this directed edge respectively.
right
If each edge is assigned a meaningful value, this value is called a weight, and such a graph is called a weighted graph.
Spend
In an undirected graph, the number of edges associated with a vertex is called the degree of the vertex. In a directed graph, the number of edges ending at a vertex is called the in-degree of the vertex; the number of edges starting from a vertex is called the out-degree of the vertex.
path
For a sequence of vertices in a graph, if the two adjacent vertices in the sequence are the starting point and end point of the edge, the sequence is called a path. The first and last vertices of the sequence are called the starting point and end point of the path. The number of edges a sequence contains is called the length of the path. A path with no less than three vertices, if the starting point and end point are the same, is called a cycle or cycle. A path that has no identical vertices except the starting point and end point is called a simple path. A simple path with the same start and end points is called a simple circuit.
connectivity
If there is a path between two vertices, they are said to be connected. If any two vertices are connected, the graph is called a connected graph.
Strong connectivity and weak connectivity
in directed graph If there is a path starting from at least one vertex between any two points, the graph is called a weakly connected graph (week connected digraph). If there is a path between any two points starting from each vertex, the graph is called a strongly connected digraph.
Graph storage
adjacency matrix
Can quickly query whether two vertices are adjacent. Querying all neighbors of a vertex is relatively slow. When the graph is sparse, it takes up more space.
adjacency list
When the graph is a sparse graph, the space occupied is small. Querying all adjacent points of a vertex is fast. When the graph is a dense graph, it is slow to query whether two points are adjacent points.
Graph traversal
breadth-first traversal
Initialize the access flag array, all 0
Insert the starting point into the queue and mark "visited"
If the queue is not empty:
Remove a vertex access from the queue
If the neighbor is not "visited", insert it into the queue and mark it as "visited"
depth first traversal
access node
Starting from unvisited nodes, perform depth-first traversal.
shortest path
single source shortest path
Given a directed network and a vertex called a source, the shortest path from the source to each other vertex is called the single-source shortest path.
Dijkstra's algorithm
The most efficient shortest path algorithm so far
Can be solved for weighted undirected graphs or directed graphs
Restriction: There cannot be negative weight edges
minimum spanning tree
spanning tree
For an undirected graph G, its spanning tree T is a connected subgraph of G, and T contains all vertices in G and has n-1 edges. (n is the number of vertices)
Prim's algorithm Prim
Select an edge with the smallest weight from the candidate edge set and add it to the selected subgraph
Update candidate edge set
Repeat step 2 until the selected subgraph contains all vertices of the original image
Kruskal's algorithm
topological sequence
Apex Activity Network AOV
Vertices are used to represent activities, and directed edges are used to represent the sequence of activities. Such a directed graph is called activity on vertex network (AOV network activity on vertex network).
Arrange the vertices in the AOV network into a sequence such that for any two vertices vi and vj, if vi is the predecessor of vj, then vi must be in front of vj in the sequence. We call such a sequence a topological sequence
Algorithms for finding topological sequences
Create an integer array to record the in-degree of each vertex. Create a queue and put the vertices with indegree 0 into the queue.
If the queue is not empty, take a vertex from it as the vertex in the topological sequence.
Decrease the in-degree of the end point of the edge starting from this vertex by 1. If the in-degree is 0 after subtracting 1, then insert the point into the queue.
Repeat steps 2 and 3 until the queue is empty.
If the number of vertices in the resulting sequence is equal to the number of vertices in the graph, the algorithm is successful.
Critical Path
Side Activity Network AOE
For a weighted directed graph, its edges represent an activity, the weight represents the duration of the activity, and the vertices represent events in which the incoming edge activities have been completed and the outgoing edge activities can start. This weighted directed graph is called edge activity network (AOE network)
Critical Path
The longest weighted path from the source to the sink is called the critical path
Activities on the critical path are called critical activities
Activities that are not on the critical path are called non-critical activities
The earliest time the event occurred
For an event, its earliest occurrence time is the earliest start time of the activity starting from its vertex.
is the length of the longest weighted path from the source point to this vertex.
Latest occurrence time of the event
For an event, its latest occurrence time is the latest end time of all activities that end at its vertex.
It is the earliest occurrence time of the sink minus the length of the longest weighted path from the vertex to the sink.
Activity delay
For any activity (edge), the latest occurrence time of its end event minus the earliest occurrence time of its starting point is the longest time that this activity can last.
The maximum sustainable time of an activity minus the weight of the activity edge is the allowed delay of the activity.
The earliest and latest occurrence time of the source point event are the same, both are 0
The earliest and latest occurrence times of sink events are also the same, both are the length of the critical path
Maze solving
binary search tree
Find related concepts
Find
Suppose there are n data elements in the data set, and ki is the keyword of the data element Ri. Now given the keyword k, the process of finding the corresponding data element R is called search.
lookup table
Data objects mainly for search operations. Generally it is a linear table.
Keywords
A data item that uniquely identifies a data element.
Categories to find
Static search and dynamic search
Depending on whether the lookup table is modified during the search process, the search is divided into static search and dynamic search.
Inner search and outer search
According to whether there is interaction between internal and external memory during the search process, search is divided into internal search and external search.
Search results
Search successful
gives the entire data element, or gives the position of the data element
Search failed
Returns a null pointer or other predetermined value
Main search methods
Balanced binary search tree
If every node of a binary tree is in a balanced state, then the binary tree is called a balanced binary tree.
B-tree
B-tree B-tree
B-tree is a tree-like data structure that can self-adjust its balance state.
Supports fast search, traverse, insertion and deletion operations
B-trees are more suitable for large-scale data read and write operations in storage systems.
Commonly used in databases and file systems
Several important concepts
Data object or data element: a record in a data table
Key code: attributes used to distinguish objects
Index item: The data object composed of the key code of an object and the address of the object in the data table is called an index item.
Index table: A data table composed of index items is called an index table
hash
open address law
Linear detection method
square detection method
Double hash function detection method
SetMap
Collections and Dictionaries
Collection std::set, std::unordered_set
The elements in the set container always maintain a constant order based on itself, and the user cannot change this order.
Multiple elements with the same value cannot exist in the set container at the same time.
The set container manages memory usage by itself without user intervention.
Only const elements can be stored in the set container
Set containers are usually implemented using binary search trees
Dictionary std::map, std::unordered_map
The unordered_map container is similar to the unordered_set container, storing keywords and their corresponding values. That is, a tuple whose internal elements are (keyword, value)
Elements in a container can only be accessed by key, not storage location
The storage location of the elements in the map container is determined based on the hash function value of its key.
The value of an element can be different from its key
Multiple elements with the same key code cannot exist in the container at the same time.
Containers manage their own memory usage without user intervention.
Only const key codes can be stored in the container
Containers are usually implemented using hash tables
Same as unordered_set, when using a custom type key, you need to formulate the hash function and equivalence determination function of the custom type.