MindMap Gallery data structure
Mind map of the basic framework of data structure for postgraduate entrance examination professional courses, including linear tables, stacks and queues, trees and binary trees, graphs, search, sorting, etc. You can pick it up if you need it.
Edited at 2021-11-23 20:04:58One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
number according to Knot structure and Calculate Law
introduction
data
Data elements are the basic units of data A data item is the smallest unit of data A data object is a collection of data elements with the same properties
algorithm
Important features: finiteness, certainty, feasibility, input and output
Evaluation of pros and cons: correctness, readability, robustness, efficiency
time complexity
space complexity
linear table
sequential storage
Sequence table
Random storage, but insertion and deletion require moving a lot of data
chain storage
linked list
static linked list
circular linked list
Doubly linked list
Single list
Memory distribution can be discontinuous Easy to insert and delete The search needs to start from one end
special
stack
First in, last out, the input and output of elements are performed at the same end
queue
First in, first out, input at the end of the queue, output at the head of the queue
feature
Except for the first and last data elements, each data element has a unique predecessor and successor
String, array, generalized list
string
storage structure
Sequential storage and chained storage
pattern matching algorithm
BF algorithm
KMP algorithm
Need to find next array
array
Compressed storage of matrices
dense matrix
row precedence
Column first
sparse matrix
Triad
generalized table
Data elements can be atoms or generalized tables
picture
basic concept
subplot
Suppose there are two graphs. The vertices and edges of one graph are a subset of the vertices and edges of the other graph. This graph is said to be a subgraph of the other graph.
Directed and undirected complete graphs
An undirected graph has n(n-1)/2 edges, and a directed graph has n(n-1) arcs.
sparse graph
Very few edges or arcs
dense graph
There are many edges or arcs
right
Meaningful values on the sides. Personal understanding can be compared to the right of Huffman tree
adjacent point
Two points connected by an edge are adjacent points to each other. The edge is attached to the vertex and the edge is associated with the vertex.
Out (in) degree
For directed graphs, the point is the in-degree and the point is the out-degree.
path
loop
A path with the same start and end points
storage structure
adjacency matrix
A matrix representing the adjacency relationship between vertices
adjacency list
A linked storage structure of a graph, establishing a single linked list for each vertex in the graph, and placing adjacent vertices in the linked list
cross linked list
It is another chain storage structure of directed graph
tail domain
header field
chain domain
Points to the next arc hlink with the same arc head
Points to another arc tlink with the same arc tail
Related Information
adjacency multiple list
It is another chain storage structure of undirected graph
Traverse
depth first
Access from a vertex Find the first unvisited adjacent point of the just visited vertex and repeat the execution Returns the previously visited vertex that still has unvisited adjacent vertices and finds the next unvisited adjacent vertex.
breadth first
Access from a vertex Visit each unvisited adjacent vertex of this vertex in sequence Starting from these adjacent points respectively, visit their adjacent points in sequence
algorithm
minimum spanning tree
Prim's algorithm
Kruskal's algorithm
shortest path
Dijkstra's algorithm
Freud's algorithm
topological sort
In a directed graph, visit a vertex without a predecessor and output Delete this vertex. Repeat the above operations
Critical Path
The longest weighted path from a point with indegree 0 (source point) to the sink point
Tree
basic terminology
Node
an independent unit in the tree
degree of node
The number of subtrees a node has is called the degree of the node
leaf
Nodes with degree 0 are called leaves or terminal nodes
tree depth
The maximum level of nodes in the tree is called the depth or height of the tree
degree of tree
The degree of a tree is the maximum value of the degree of each node in the tree
Parents, children, brothers, ancestors, descendants, cousins
Binary tree
full binary tree
A binary tree of depth k and containing 2∧k-1 nodes
Features
The number of nodes on each layer is the maximum number of nodes
complete binary tree
Binary tree with depth k and n nodes A complete binary tree is called a complete binary tree if and only if each node corresponds to a node numbered from 1 to n in a full binary tree of depth k.
Features
Leaf nodes can only appear on the two largest levels.
For any node, the maximum level of its descendants under the right branch is L, then the maximum level of its descendants under the left branch must be L or L 1
General binary tree
clue binary tree
The binary linked list composed of this node structure is used as the storage structure of the binary tree and is called a clue linked list. The pointers pointing to the predecessor and successor of the node are called clues. The binary tree with clues added is called a clue binary tree.
typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; int LTag ,RTag; }BiThrNode,*BiThrTree;
Traverse
preorder traversal
inorder traversal
Postorder traversal
The so-called first, middle and last refer to the timing of accessing the root node. For traversing a binary tree, the left and right subtrees and root nodes must be accessed in a certain order. Different access orders are different traversal methods.
forest
is a set of m (m≥0) disjoint trees
Huffman tree
basic concept
path
The branches from one node to another in the tree constitute the path between the two nodes.
path length
Path length The number of branches on a path is called path length
tree path length
The sum of the path lengths from the root of the tree to each node
right
A quantity assigned to an entity is a numerical description of one or some attributes of the entity. My personal understanding is the degree of importance. The larger the value, the more important it is.
algorithm
The structure of Huffman tree
Given n weights, construct n binary trees with only root nodes to form a forest. Select the two trees with the smallest weights from the forest as the left and right subtrees to construct a new binary tree. The weight of the root node of the new binary tree is the sum of the weights of the two subtrees. Add the new binary tree to the forest and delete it as a subtree. two trees Repeat until there is only one tree left in the forest, this tree is the Huffman tree
My personal understanding is that constructing the two smallest trees into a new binary tree, and performing this operation cyclically, the smaller the weight, that is, the less important data, is stored at the bottom of the Huffman tree. The larger the weight, the more important it is. High-level data is stored in the upper level of the tree for easy use
Huffman coding
For a Huffman tree with n leaves, if each left branch in the tree is assigned 0 and the right branch is assigned 1, the binary string composed of the assignments of each branch on the path from the root to the leaves is Huffman coding.
Personal understanding: Huffman coding is like a navigation, 0 means go left, 1 means go right.
Calculation of WPL value
Find
basic concept
lookup table
A collection of data elements of the same type
Keywords
The value of a data item in a data element
Find
Based on a given value, determine a record or data element in the lookup table whose key is equal to the given value
Linear table search
sequential search
Starting from one end of the table, compare them sequentially
Half search (binary search)
Start the comparison from the middle of the table. If it is greater, perform a halved comparison on the half that is greater. If it is smaller, perform a halved comparison on the half that is smaller than the table until the search is successful or there is no result.
Block search
Create an index table and perform sequential searches in the blocks according to the blocks pointed to by the index table.
Tree table lookup
Binary sorting tree
If the left subtree is not empty, it must be smaller than its root node.
If the right subtree is not empty, it must be greater than its root node.
The left and right subtrees are both binary sorted trees.
balanced binary tree
On the basis of the binary sorting tree, there is an additional restriction, that is, the absolute value of the depth difference between the left and right subtrees does not exceed 1.
hash table
sort
basic concept
sort
Is the operation of reordering a set of records in non-decreasing or non-increasing order of keywords
sorting stability
When the sorting keys are different, the result obtained by sorting the unordered sequence of any record is unique, otherwise it is not unique.
Internal sorting and external sorting
Internal sorting
The sorting process in which all records to be sorted are stored in computer memory
external sort
The number of records to be sorted is very large, and the memory cannot accommodate them all at once. During the sorting process, external storage needs to be accessed for the sorting process.
insertion sort
direct insertion sort
When inserting the i-th (i >= 1), the previous V[0], V[1],..., V[i-1] have been sorted. At this time, use the sorting code of V[I] to compare the order of the sorting codes of V[i-1], V[i-2],..., find the insertion position and insert V[i], and the element at the original position will be inserted into Move backward
half insertion sort
Use low, mid, and high to divide it into two regions [low, mid-1] and [mid 1, high] If the key value is less than the middle value mid of the sequence, it means that the key value should be inserted into the left area [low, mid-1], and then divide the area repeatedly for [low, mid-1] until low>high, and the final insertion The position should be high 1. Move the data at the position after high back as a whole, and then assign the key to [mid 1]
Hill sort
It is essentially a group insertion method that sorts by continuously shortening the cloth length.
swap sort
Bubble Sort
Find small elements or large elements one by one by comparing and exchanging positions of adjacent elements.
Quick sort
It is an improvement on bubble sorting. Select the dividing value to divide it into two parts. The left side is less than the right side and the right side is greater. Repeat the execution.
selection sort
Simple selection sort
First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.
tree selection sort
Compare the n elements to be sorted in pairs, take out the smaller ones, and then compare the n/2 smaller ones in pairs, take out the smaller ones, and repeat the above steps until the ones are taken out. Minimal element.
Heap sort
Construct the sequence to be sorted into a big top heap. According to the properties of the big top heap, the root node of the current heap is the largest element in the sequence. Swap the top element of the heap with the last element, and then reconstruct the remaining nodes into a big top heap, and so on. Starting from the first time we build the big top heap, we can get the maximum value of a sequence every time we build it. , and then put it at the end of the big top pile. Finally, an ordered sequence is obtained.
merge sort
Divide n elements into two subsequences containing n/2 elements Use MS to recursively sort the two subsequences (finally the entire original sequence can be decomposed into n subsequences) Merge two sorted sequences
Radix sort
Multiple keyword sorting
highest priority method
lowest priority method
chained radix sort
external sort