Wondershare EdrawMind
MindMap Gallery Data Structures and Algorithms
- 22
Data Structures and Algorithms
Data Structures and Algorithms Data structures are the way data is stored and organized in computers. A data structure is a collection of data elements that has certain logical relationships, applies a certain storage structure in the computer, and encapsulates corresponding operations.
Edited at 2022-06-01 17:11:27
- Recommended to you
- Outline
Algorithms and Data Structures
linear table
Linked linear list has head node (pacesetter)
The first node is phead->next or head.next
stack
Non-recursive implementation of recursive programs does not necessarily require a stack
You can use the idea of DP
picture
The vertex set of the graph is not empty, so there is no empty graph
connected components
Maximally connected subgraph
A circuit is a ring
The cycle must not be a simple path
Except for the endpoints, the intermediate nodes of a simple loop do not repeat.
The vertices of a simple path are not repeated
adjacency matrix
Generally, the elements on the main diagonal are 0
Not connected is infinity
Critical Path
Earliest start time ve()
Latest start time vl()
The earliest start time of the activity e()
The earliest start time of the origin point
The latest start time of the activity l()
The latest start time of the meeting point minus the activity time
Activity time margin d()
Indicates the time margin of the activity. An activity with a margin of 0 is on the critical path.
Shortening the common edges of all critical paths can shorten the construction period
Extending any critical edge will extend the construction period
KMP
partial match table
A table consisting of the common prefix and suffix lengths of all prefixes of the substring
next[]
nextval[]
sort
Hill sort
an insertion sort
Gradually reduce the increment and use direct insertion sort within the group
external sort
multi-way balanced merging
The number of segments after each pass of processing becomes celing(m/k), where k is the number of passes.
Find
average search length
binary search
Draw search tree
Also known as binary decision tree
The average height of the failed node's parent node
Success is calculated as average depth
Hash table lookup
Tree
B-tree and B-tree
B-tree
Definition of m-order B-tree
Each node has at most m subtrees and m-1 keywords
The non-empty B-tree root node has at least 2 subtrees
The non-root node has at least ceiling(m/2) subtrees
3,4-2
5-3
The leaf node is the node where the search failed (actually does not exist)
The terminal node refers to the lowest node
Also called B-tree
Each element appears only once
Data is inside the B-tree node
Any node keyword always has left and right children
The predecessor/successor of any keyword is always at the lowest level
Split on insertion
Middle elements are raised, recursively split
After splitting, the node on the left is always full.
The 4th order B-tree node is split into 2,1,1
merge on delete
always translates into a merger from the bottom
If you have enough, borrow it from your brothers
If the borrowing is not enough, the parent keyword will be dropped and the terminal point will be merged.
If there is not enough money to borrow, it will definitely be merged.
The order is odd, and there are m-1 keywords after merging.
The order is even, and there are m-2 keywords after merging.
Note that the nodes after merging even-order B-trees are not full.
Merge towards the root
B-tree
m-order B-tree definition
Similarly, there are at most m subtrees and at least ceiling(m/2) subtrees.
But the keyword is the largest keyword corresponding to the child node
Therefore there are also m
Leaf nodes have pointers to records
Leaf nodes are linked horizontally to facilitate traversal search
Pay attention to the difference between the leaf nodes of the B tree and the leaf nodes of the B tree.
minimum spanning tree
When the weights of each edge are different from each other, the minimum spanning tree is unique
The spanning trees constructed using Prim's algorithm from different vertices are not necessarily the same.
The minimum spanning tree edge weight sequence of the same picture is the same
heap
Build a pile
Array traversal from back to front
AVL tree
Delete and insert
If the deleted node is a non-leaf node, the tree may be the same after reinsertion