Wondershare EdrawMind
MindMap Gallery Data structure knowledge map
- 9
- 1
Data structure knowledge map
A data structure refers to a collection of data elements that have one or more specific relationships with each other. It is a way for computers to store and organize data. The following summarizes the basic concepts and terms of data structures, linear structures, arrays and generalized tables, tree structures, internal sorting, search, graph or network structures.
Edited at 2021-08-01 04:44:15
- 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 knowledge 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
Basic concepts and terminology
data
basic unit
data element
consists of data items
indivisible smallest unit
data item
structure
logical structure
Logical relationships between data elements
physical structure
Store structures in computers
algorithm
ordered sequence of instructions
Finiteness, certainty, feasibility
linear structure
linear table
accomplish
Sequence table
Try it for operations such as random access
Insertion/deletion: O(n)
Number of insertion moves: n/2
Delete moves
(n-1)/2
Find the length of the table/get the i-th data element: O(1)
linked list
Linear linked list/singly linked list
Non-random access storage structure
Insertion: s->next=p->next;p->next=s; deletion: p->next=p->next->next; complexity O(n)
static linked list
It is represented by a one-dimensional array, using the cursor cur instead of the pointer, and the 0th component is regarded as the head node.
Doubly linked list
The node has two pointer fields
Delete/Insert: O(n)
circular linked list
The pointer field of the last node in the table points to the head node
application
Representation and addition of polynomials of one variable
stacks and queues
stack
Last in, last out (only insert and delete operations at the end of the table)
accomplish
Sequential stack (Page46, 47)
The top pointer in a non-empty stack is always at the next position of the top element.
Insert/delete: top -1;
chain stack
shared stack
application
Numeric conversion
bracket matching test
line compiler
Maze solving
Expression evaluation
Operands, operators, delimiters
Implement recursion
queue
First in, first out (insertions at one end of the table and deletions at the other end)
accomplish
chain queue
Head pointer and tail pointer
The queue is empty: both the head pointer and the tail pointer point to the head node
circular queue
front\rear, in a non-empty queue, the head pointer always points to the head element of the queue, and the tail pointer always points to the next position of the tail element of the queue.
Determine full/empty
null
Q.fornt==Q.rear
Full
Q. front==(Q.rear 1)%MAXSize
deque
string
a finite sequence of characters
Empty string or space string
substring
A subsequence consisting of any consecutive characters in the string
Number S=(1 n)n/2 1
accomplish
Fixed-length sequential storage
Heap allocated storage representation
Block chain storage representation of string
pattern matching algorithm
Main string S, pattern string T
Naive pattern matching algorithm
O((n-m 1)*n)
KMP algorithm
Calculation of next[] array
three conditions
Note that there is some misalignment with the original string array subscript because next[0]=0
Calculation of nextval[] array
When next[j]=k;pj=pk, next[j]=next[k];
Algorithm time complexity
O(n*m), close to O(n m)
Features
The pointer indicating the main string does not need to backtrace
String operation application
Arrays and generalized tables
array
There are only operations for accessing elements and modifying element values, generally no insertion/deletion operations are performed.
accomplish
sequential storage
Compressed storage of matrices
special matrix
nth order symmetric matrix
Store lower triangle/upper triangle (Page95-96)
lower triangle
i>=j:i(i-1)/2 j-1
diagonal matrix
sparse matrix
triple sequence table
Transpose operation
Swap the rows and columns of a matrix
Swap i and j in each triple
Reorder the triples
Row logically linked sequence table
cross linked list
generalized table
definition
Header: first element
Atom a and subtable A
Table tail: the table composed of the remaining elements
Distinguish between: () and (())
Any non-empty list, its head may be an atom/list, and its tail must be a list
Find the depth of a generalized table
multiplicity of brackets
accomplish
chain storage structure
table node
Flag field, pointer field indicating table header/footer
Atomic node
Flag and value fields
tree structure
Tree
Node
terminal node/leaf
branch node
basic terminology
degree of node
The number of subtrees owned by the node
children, parents, brothers, cousins
depth
Ordered tree, unordered tree
storage structure
parent representation
child representation
Child brother representation/binary linked list representation
Right pointer points to brother
Tree and forest traversal
Tree
Root traversal first
back root traversal
When a binary linked list is used as the storage structure of the tree, root-first traversal and root-posterior traversal can be implemented by borrowing the pre-order traversal and in-order traversal of the binary tree.
forest
Preface to the forest
Corresponding to pre-order traversal of a binary tree
The middle sequence of the forest
Inorder traversal of binary tree
Binary tree
definition
Each node has at most two subtrees (there is no node with degree greater than 2), and the order of the subtrees cannot be reversed. There are left and right
5 basic forms
nature
There are at most 2^(i-1) nodes on the i-th level of the binary tree
A binary tree with depth k has at most 2^k-1 nodes.
For any binary tree, the number of leaf nodes is n0 and the number of nodes with degree 2 is n2, then n0=n2 1
complete binary tree
The depth of a complete binary tree with n nodes is ëlognû 1
Features
for any node
full binary tree
Depth is k and there are 2^k-1 nodes
storage structure
sequential storage structure
chain storage structure
There are n 1 empty link fields in a binary linked list containing n nodes.
subtopic
application
Traverse a binary tree
Preorder traversal
VLR
inorder traversal
LVR
Postorder traversal
LRV
Given preorder traversal and inorder traversal, find postorder traversal
The first node of pre-order traversal is the root node, and in-order traversal can disconnect the left and right segments.
Given post-order traversal and in-order traversal, find pre-order traversal
In post-order traversal, the last node is the root node.
In the pre-order, in-order, and post-order traversal of binary tree nodes, the order of all leaf nodes is the same.
Preorder traversal and inorder traversal to obtain the only binary tree
clue binary tree
effect
Speed up finding the predecessor or successor of a node
After the pre-order and post-order clues are transformed, the empty link field is 1; After the mid-sequence clueing, the empty link domain is 2
Optimal Binary Tree/Huffman Tree
path length
Number of branches on the path
The weighted path length of the tree
WPL=åwl
structure
page145
Huffman coding
prefix encoding
Binary tree
The number of nodes in a Huffman tree must be an odd number
Forest to Binary Tree Conversion
subtopic
A tree can be converted into the only binary tree without a right subtree
tree count
There are - one dissimilar binary tree with n nodes. Page 154
The number of trees with n nodes that have different shapes is the same as the number of binary trees with n-1 nodes that are dissimilar to each other.
Internal sorting
Determine whether the sorting method is stable
The records to be sorted are stored in the computer's random access memory for sorting
insertion sort
direct insertion sort
In forward order, the number of comparisons reaches n-1, and in reverse order, the number of comparisons is 1/2n(n-1).
Time complexity O(n*n)
is a stable sorting
half insertion sort
The time complexity is O(n*n)
2-way insertion sort
Requires auxiliary space for n records
table insertion sort
Modify pointer instead of moving record
rearrange the results
Swap first, then modify the pointer field
The time complexity is still O(n*n)
Hill sort
First, divide the entire record sequence to be sorted into several sub-sequences and perform direct insertion sorting respectively. When the records in the entire sequence are "basically in order", perform direct insertion sorting on all records.
Combine records separated by a certain "increment" into a subsequence
The time complexity is lower than direct insertion
The values in the increment sequence should have no common factors other than 1, and the last increment value must be equal to 1
is an unstable sorting algorithm
Quick sort
bubble sort
One pass sorting: compare the first record with the second record, and then compare the second record with the third record
If the initial sequence is a positive sequence, then only one sorting pass is required. If the initial sequence is a reverse sequence, n-1 sorting passes are required.
Time complexity O(n*n)
is a stable sorting algorithm
Quick sort
pivot
O(nlogn)
If the initial records are ordered by keyword or basically ordered, quick sort will degenerate into bubble sort, and the time complexity is O(n*n)
space complexity
A stack is needed to implement recursion, and the maximum depth can be reduced to O(logn)
is an unstable sorting algorithm
selection sort
Simple selection sort
The number of comparisons of keywords is n(n-1)/2
Unaffected by the initial arrangement of records
Time complexity O(n*n)
is an unstable sorting
tree selection sort
First, compare the keywords of n records in pairs, and then compare the smaller ones among them, until the smallest/largest one is selected.
It can be represented by a complete binary tree with n leaf nodes.
O(nlogn)
Heap sort
heap
If viewed as a complete binary tree, the values of all non-terminal nodes of a complete binary tree are not greater/less than the values of its left and right child nodes.
Small top pile, big top pile
A record size of auxiliary space for exchange, each record to be sorted only occupies one storage space
More effective for files with larger n
In the worst case, the time complexity is O(nlogn)
Space complexity O(1)
is an unstable sorting method
merge sort
Time complexity O(nlogn)
Space complexity O(n)
is a stable sorting method
Radix sort
MSD and LSD
Multiple keyword sorting
Find
lookup table
Keywords
Primary keyword, sub-keyword
Performance analysis
Average lookup length ASL
static lookup table
Find element existence, retrieve attributes
Sequence table search
Sequential search (sentinels can be set)
In the case of equal probability ASL=(n 1)/2
Search in ordered list
half search
Suitable for ordered lists using sequential storage structures (linear linked lists cannot be searched effectively
Performance analysis
Approximate ASL=log(n 1)-1
Index sequence table search
direction chart
Table ordered or block ordered
The search for a certain block can be done sequentially/in half, and the block can only be searched sequentially.
Performance analysis
The table length is n, and the number of records in each block is s, then ASL=log(n/s 1) s/2
It is related to both n and s, and may not be as efficient as half search.
dynamic lookup table
Insert/delete operations during search
Binary sorting tree
nature
If the left subtree is not empty, the values of all nodes on the left subtree are less than the value of its root node.
If the right subtree is not empty, the values of all nodes on the right subtree are greater than the value of its root node.
Its left and right subtrees are also binary sorting trees respectively.
In-order traversal of a binary sorting tree can obtain an ordered sequence of keywords
insert
The newly inserted node must be a newly added leaf node
delete
three conditions
Find
subtopic
Balanced Binary Tree AVL
nature
Both the left subtree and the right subtree are balanced binary trees, and the absolute value of the difference in depth between the left and right subtrees does not exceed 1.
balancing factor
Left subtree depth - right subtree depth
AVL tree can only be 1, 0, -1
Generation of balanced trees (adjustment rules)
One-way right-hand balance processing
One-way left-hand balancing treatment
Two-way rotation (first left, then right) balance processing
Right first then left balance processing
Find performance analysis
Time complexity O(logn)
B-trees and B-trees
B-tree
m-order B-tree properties
Each node in the tree has at most m subtrees
If the root node is not a leaf node, there are at least two subtrees
All non-terminal nodes except the root have at least ém/2ù subtrees
All non-terminal nodes contain information data
(n,A0,K1,A1,....Kn,An)
Ki keyword, Ki<K(i 1)
Number range
Ai is a pointer to the root node of the subtree. The keys of all nodes in the subtree pointed to by A(i-1) are less than Ki. The keys of all nodes in the subtree pointed to by An are greater than Kn.
All leaf nodes appear at the same level and carry no information.
Find analysis
Page240-241
insert
overflow
split, move upward
delete
underflow
merge
B-tree
characteristic
A node with n subtrees contains n keywords
other
When searching, if the keyword on the non-terminal node is equal to the given value, it does not stop, but continues downward to the leaf node. That is, no matter whether the search is successful or not, each search takes a path from the root to the leaf node.
Insertions and deletions are only performed at leaf nodes
key tree
A tree of degree ³2. Each node in the tree contains only the symbols that make up the keyword.
Hash table
Correspondence: Hash function
definition
Hash table, hash, hash/hash address Page253
Construction method
direct addressing method
Linear function value of keyword/keyword
digital analytics
Take several digits of the keyword to form a hash address
Square-Medium Method
Take the middle digits of the square of the keyword as the hash address
folding method
Divide and overlay
divisor remainder method
p selects a prime number or a composite number that does not contain a prime factor less than 20
random number method
How to handle conflicts
open addressing method
di increment sequence
di=1,2,3,...
Linear probing and then hashing
prone to secondary aggregation
S»1/2(1 1/(1-a))
di=1*1,2*2,...
Second detection and then hashing
di = pseudo-random number sequence
Pseudo-random probing and then hashing
rehash
chain address method
Create a public overflow area
Find
loading factor
a=number of records filled in the table/length of the hash table
The average search length depends on the fill factor
See Page261
Graphic/Network Structure
basic terminology
vertex
Arc (directed graph)
arc tail
initial point of arc
arc head
arc terminal point
Edge (undirected graph)
Undirected graph
eÎ[1,1/2*n(n-1)]
directed graph
eÎ[0,n(n-1)]
Complete graph, directed complete graph
e respectively takes the maximum value above
sparse graph
subplot
adjacencies, dependencies, associations
Spend
The number of edges associated with vertex v TD(v)
out degree
degree
loop or ring
simple path
Paths with non-repeating vertices
connected
connected graph
Any two vertices in the graph are connected
connected components
Maximum connected subgraph in undirected graph
Strongly connected graph
In a directed graph, every two points can reach each other.
Strongly connected component
Maximum connected subgraph of directed graph
The spanning tree of a connected graph is a minimal connected subgraph
net
Picture with authority
storage structure
array notation
For an undirected graph, the degree of a vertex Vi is the sum of the elements of the i-th row/column in the adjacency matrix
For a directed graph, the sum of the elements in the i-th row is the out-degree OD(Vi) of the vertex Vi, and the sum of the elements in the j-th column is the in-degree ID(Vj) of the vertex Vj.
adjacency list
Create a singly linked list for each vertex
If the undirected graph has n vertices and e edges, the adjacency list requires n head nodes and 2e table nodes.
In order to facilitate the calculation of the in-degree of the vertices in the directed graph, an inverse adjacency list of the directed graph can be established.
cross linked list
adjacency multiple list
Graph traversal
Depth First Search (DFS)
Similar to tree root traversal
time complexity
When using adjacency lists to store graphs, O(n e)
Implemented using recursion/stack
Breadth First Search (BFS)
Similar to tree traversal by level
Utilize queues
time complexity
Same as DFS
Graph connectivity problem
Undirected graph
When traversing an undirected connected graph, you only need to start from any point in the graph and perform DFS/BFS to access all vertices. For non-connected graphs, it is necessary to search from multiple vertices.
spanning tree
Depth/breadth first spanning tree
directed graph
Use DFS to find the strongly connected components of a directed graph
minimum spanning tree
Prim's algorithm
Time complexity O(n*n)
Try to find edge-dense nets
Kruskal algorithm
Time complexity O(eloge)
Try to find the network with sparse edges
Joint points and reconnected components
joint point
If the vertex and its associated edges are deleted, a connected component is divided into two or more connected components.
Characteristics of two types of joint points
reconnected graph
Connected graph without joints
Depth-first search can be used to find joint points and determine whether the graph is reconnected.
Connectivity k
Connectivity can only be destroyed by deleting at least k vertices from the connected graph.
directed acyclic graph
topological sort
From a partial order on a set to a total order on the set
AOV network
A directed graph in which vertices represent activities and arcs represent priority relationships between activities.
How to perform topological sorting
Select a vertex in the directed graph without a predecessor and output
Remove the vertex and all arcs ending with it from the graph
Repeat the above two steps until all vertices have been output, or there are currently no vertices without predecessors. The latter case indicates that there is a cycle in the directed graph.
DFS can also be used. The vertex sequence recorded in the order of exiting the DFS function is the reverse topological ordered sequence.
AOE network
Vertices represent events, arcs represent activities (activity on edge), and weights represent the duration of activity.
Can be used to estimate project completion time
source point, sink point
Critical Path
The path with the longest path length is the shortest time to complete the project.
e(i)
The earliest start time of activity ai
l(i)
The latest time the activity ai must start
key activities
e(i)=l(i)
Activities on the critical path are critical activities (completing non-critical activities ahead of schedule will not speed up the progress of the project)
ve(i)
The earliest occurrence time of the event
When calculating, you should recurse forward from ve(0)
vl(i)
The latest occurrence time of the event
When calculating, recurse forward and backward from vl(n-1)=ve(n-1)
Algorithm for finding critical path
shortest path
The shortest path from a source point to all other vertices
Dijkstra's algorithm
ContentPage187-189
Time complexity O(n*n)
The shortest path between each pair of vertices
Relationship: e=1/2åTD(v)