MindMap Gallery Data structure mind map organization
The data structure organizes the overview of Song Dynasty literature, Song lyrics, Song poetry, Song Dynasty prose, C11 grammar, sorting, graphs, trees, and comparison of 935 exam syllabus. Everyone is welcome to study.
Edited at 2023-03-05 23:09:15Avatar 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.
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 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!
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.
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 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
introduction
algorithm
Algorithm definition
Description of problem solving steps
five characteristics
Finiteness
certainty
feasibility
enter
output
Complexity calculation
time complexity
Addition rule
Multiplication rules
Common asymptotic time complexities
Arithmetic formula
space complexity
Define the relationship between the size of the auxiliary space and the amount of original data
Work in place
solve problems
recursive algorithm
recursion formula
recursive call
recursive public exit
column equation method
data
data object
data element
(individual) basic unit
data item
(individual) attributes
type of data
Atomic type
structure type
Abstract data type (ADT)
data structure
Three elements
logical structure
linear structure
General linear table
restricted linear table
stack
queue
string
Linear table promotion
array
nonlinear structure
Tree
Binary tree
multi-tree
forest
Picture/Network
directed graph
Undirected graph
gather
storage structure
sequential storage
chain storage
Index storage
Hash storage/hash storage
Data operations (operations)
Linear ListLinear List
Definition/Concept
Limited number of data elements, same data type, and ordered
The storage space is the same size
Head element; tail element; bit order; predecessor; successor
operate
Create/destroy
static allocation
dynamic allocation
C/C malloc, new[]
Add, delete, modify and check
Property acquisition
storage structure
sequential mapping sequential storage
SqList sequence table
characteristic
Random access [physical and logical order are the same]
Deletion and insertion have high time complexity
Allocation
static
C language array allocation
dynamic
C language pointer mode allocation
operate
initialization
insert
Implement logic
Robustness Judgment
move
Property modification
Return function status
time complexity
Best O(1)
Worst O(n)
Average = Probability Number of moves = Expectation
delete
Implement logic
Robustness
move
Property modification
Return function status
time complexity
Best O(1)
Worst O(n)
Average
Find by value
Implement logic
Search in order
Return order
time complexity
Best O(1)
Worst O(n)
Average
merge
Real questions
2010] 408 integer array circular left shift
2011] 408 Find the median of two equal-length ascending sequences
2013] 408 Find the main element in the sequence. Main element: number > total number of sequence/2
2018】408 Find the smallest integer that does not appear
2020】408 Find the minimum distance of triples
chain storage
Single list
definition
operate
insert
Head insertion method
tail insertion method
Time complexity O(n)
delete
Find by value
Call it short
Double linked list
definition
operate
insert
Implement logic
time complexity
delete
circular linked list
One-way circular linked list
Two-way circular linked list
phalanx
static linked list
jump table
Related concepts
head node
head pointer
Linked list header
First node
tail pointer
Real questions
2009】408 Find the node value at the kth position from the bottom in a singly linked list containing only the head node
2012】408 Find the common suffix starting position of two linked lists
2015] 408 singly linked list retains the node with the first appearing position among all nodes with equal absolute values.
2019】408 rearrange singly linked list
Advantages and Disadvantages
order
Random access, chained can only be accessed sequentially
chain
Flexible allocation, no need to occupy continuous space, low insertion and deletion time complexity
logical structure
Stack
definition
top of stack
Bottom
Empty
Features LIFO last in first out
Mathematical properties [Cattleya number]n different elements are pushed onto the stack, and the number of different arrangements of elements popped out of the stack is
operate
&InitializeInit
&Destroy
Push(Push)Push(&S,&e)
Pop(&S,&e)
Read the top of the stack GetTop(S,&e)
Empty IsEmpty
storage structure
order
sequence stack
shared stack
chain
chain stack
operate
Attributes
header node
table tail node
Application question types
bracket matching
Expression evaluation
prefix/polish expression
infix
Suffix/reverse polish expression
Conversion method
Calculation method
expression tree
recursive call
time complexity calculation
dfs wide search
Pop sequence
impossible sequence
Number of sequence types
Cattleya number:
possible sequence
Numeric conversion
Minimum stack depth
Function local variable storage
Queue/Queue
Basic operations
FIFO
initialization
destroy
Call it short
Join the team
Dequeue
Read the header element
concept
Head of line pointer
tail pointer
head node
storage structure
order
circular queue
sequential storage
chain
deque
chain storage
definition
operate
logical structure
application
Binary tree level traversal
Dequeue sequence calculation
When doing the questions, you can mark the sequence of left and right entries
FIFO properties
OS buffer
CPU resource allocation
Page replacement algorithm
array matrix
array
definition
storage structure
row precedence
Column first
special matrix
Symmetric matrix
Subscript conversion formula
triangular matrix
Subscript conversion
tridiagonal matrix
Subscript conversion
sparse matrix
Triad
cross linked list
sparse matrix
adjacency matrix
Real questions
The following table of matrix elements and one-digit array subscript conversion
Please ask for the bank manager’s address
string
basic concept
substring
main string
Location
storage structure
Fixed-length sequential storage
Heap allocated storage
Blockchain storage
Related operations
pattern matching
Brute force matching
KMP algorithm
nextarray
nextManual algorithm
Equality judgment
Find substring
connect
length
Find
efficiency index
average search length
Search successful
Search failed
concept
Lookup table/lookup structure
operate
Find specific elements
Check the element attributes that meet the conditions
insert element
Delete element
static lookup table
order
Halve
hash
dynamic lookup table
Binary sorting tree
AVL balanced binary tree
B-tree
average search length
conflict/collision
conflict between synonyms
impossible to avoid
aggregation/accumulation
Synonyms conflict with non-synonyms
Mainly related to conflict detection methods
Hash structure
hash function
direct addressing method
division leaving remainder method
digital analytics
Square-Medium Method
Conflict handling
open addressing method
Linear probing and then hashing
Second detection and then hashing
Pseudo-random probing and then hashing
Chain address method/zipper method
Rehashing (hash) method
average search length
Search successful
Search failed
loading factor
a = number of records in the table/length of the hash table
linear structure
Sequential search (chain restriction)
General sequence table lookup
Ordered list search
Search by half (two points)
Suitable for ordered sequential storage structures
Half search decision tree
Type: Balanced Binary Tree
Tree height h when there are n elements
Determine whether the tree is a composite rule
Most searches
Minimum number of searches
Blocked (index order) search
ideal block length
sequential block search
optimal optimization
Index structure/tree table
B-tree
Attributes
Order of B-tree
non-leaf node structure
The balance factor of all nodes is 0 [height balance]
high
Highest
lowest
Number of keywords
most
least
nature
Number of non-root node keywords
Number of non-root node subtrees
When the root node is a non-terminal node, it must have at least two children.
Strictly balanced search tree, all node subtrees have the same height and leaves are at the same level and are represented by NULL
The structure of non-leaf nodes
operate
Find
insert
Split
delete
merge
Illustration
calculate
Given the order, number of layers, and number of keywords in a certain layer, find the maximum number of nodes
B-tree
Illustration
The difference between B and B trees
red black tree
definition
nature
application
Basic operations
Discoloration
rotate
insert
Insert adjustment
delete
Delete adjustment
Comparison of 935 exam syllabus
2022] 1. Linear table (1) Definition and basic operations of linear table (2) Implementation of linear table 1. Sequential storage structure 2. Linked storage structure 3. Application of linear table 2. Stack, queue and array (1) Basic concepts of stacks and queues (2) Sequential storage structures of stacks and queues (3) Chained storage structures of stacks and queues (4) Applications of stacks and queues (5) [Storage of multi-dimensional arrays] and compressed storage of special matrices 3. Trees and binary trees (1) Basic concepts of trees (2) Binary trees 1. Definition of binary trees and their main characteristics 2. Sequential storage structure and chain storage structure of binary trees 3. Traversal of binary trees 4. Basic concepts and clues of binary trees Construction (3) Trees and forests 1. Storage structure of trees 2. Conversion between forests and binary trees 3. Traversal of trees and forests (4) Applications of trees and binary trees 1. Binary search tree 2. Balanced binary tree 3. Huffman (Huffman) tree and Huffman coding 4. [Union search] 3. Graph (1) Concept of graph (2) Storage and basic operations of graph 1. Adjacency matrix method 2. Adjacency list method (3) Traversal of graph 1. Depth-first search 2. Breadth-first search (4) Basic applications of graphs 1. Minimum (cost) spanning tree 2. Shortest path 3. Topological sorting 4. Critical path 4. Search (1) Basic concepts of search (2) Sequential search method (3) [Block search method] (4) Half search method (5) B-tree and its basic operations, basic concepts of B-tree (6) Hash table (7) Analysis of search algorithm and application 5. Sorting (1) Basic concepts of sorting (2) Insertion sort 1. Direct insertion sort 2. Half insertion sort (3) Bubble sort (4) Simple selection sort (5) Hill sort ( shell sort) (6) Quick sort (7) Heap sort (8) Two-way merge sort (9) Radix sort (10) [External sort] (11) Comparison of various sorting algorithms (12) Application of sorting algorithms
2021] 1. Linear table (1) Definition and basic operations of linear table (2) Implementation of linear table 1. Sequential storage structure 2. Linked storage structure 3. Application of linear table 2. Stack, queue and array (1) Basic concepts of stacks and queues (2) Sequential storage structures of stacks and queues (3) Chained storage structures of stacks and queues (4) Applications of stacks and queues (5) Compressed storage of special matrices 3. Trees and binary trees (1 ) Basic concepts of trees (2) Binary trees 1. Definition and main characteristics of binary trees 2. Sequential storage structure and chain storage structure of binary trees 3. Traversal of binary trees 4. Clues Basic concepts and construction of binary trees (3) Tree, forest 1. Storage structure of tree 2. Conversion between forest and binary tree 3. Traversal of tree and forest (4) Application of tree and binary tree 1. Binary sorting tree 2. Balanced binary tree 3. Huffman tree and Huff Mann coding 3. Graph (1) Concept of graph (2) Storage and basic operations of graph 1. Adjacency matrix method 2. Adjacency list method (3) Graph traversal 1. Depth first search 2. Breadth first search (4) Figure Basic applications of 1. Minimum (cost) spanning tree 2. Shortest path 3. Topological sorting 4. Critical path 4. Search (1) Basic concept of search (2) Sequential search method (3) Half search method (4) B- Tree and its basic operations, basic concepts of B-tree (5) Hash table (6) Analysis and application of search algorithm 5. Internal sorting (1) Basic concept of sorting (2) Insertion sort 1. Direct insertion sort 2. Halved insertion sort (3) Bubble sort (4) Simple selection sort (5) Hill sort (shell sort) (6) Quick sort (7) Heap sort (8) Two-way merge sort (merge sort) (9) Radix sort (10) Comparison of various internal sorting algorithms (11) Application of internal sorting algorithms
Tree
basic concept
high
node height
tree height
Number of layers/depth
node depth
tree depth
Ancestor, descendant, brother, parent; cousin
Spend
degree of node
degree of tree
Node
branch node
leaf node
Ordered tree and unordered tree
Path and path length
path
path length
forest
nature
Nodes and degrees
Number of nodes (m) = number of non-leaf nodes number of leaf nodes
Number of nodes = Σ degree x number 1 [root]
Number of nodes
m-ary tree with height h up to (maximum) number of nodes
sp: The binary tree nodes with height h are at most
For a binary tree with an even number of nodes, the number of nodes with degree 1 must be an odd number.
minimum height
The height of an m-order tree/m-ary tree/complete m-ary tree with n nodes [must memorize]
maximum height
The maximum height of a tree with n nodes and degree m
type
Binary tree
definition
If a node has only one child node, it must be the left child
Number of nodes , ordered tree containing left and right subtrees
nature
Number related
Number of leaf nodes
Maximum number of nodes in layer k
The height is h at most the number of nodes
subscript related
control children
Left child number of node i = 2i
Right child number of node i = 2i 1
Depth related
The depth of the node
Complete Binary Tree] Depth
Maximum depth of a strict binary tree
(n 1)/2
Number of pointers
The number of null pointers in a binary chain with n nodes is n 1
Traversal access order
sequence legitimacy
The access order determines the shape of the binary tree
Left must be accessed before right
Access sequence in front, middle and back order, leaf node sequence remains unchanged
When the height is equal to the number of nodes, the preorder and postorder traversal sequences are opposite.
type
full binary tree
Definition
complete binary tree
definition
The layers are all full, and the nodes in layer are filled in order from left to right.
Each node corresponds one-to-one to the node position numbered in the full binary tree with height
nature
If a node has no left child, it must be a leaf node
The left brother of the parent of a leaf node (if it exists) must not be a leaf node.
A complete binary tree with height h, the minimum number of nodes is
The last branch (non-leaf) node number is
If a complete binary tree has nodes, then the number of leaf nodes is
calculate
There are k leaf nodes in layer x. Find the max/min number of nodes.
The minimum number of nodes is: The maximum number of nodes is:
storage structure
sequential storage
chain storage
Traverse
First/previous order (NLR)
Mid-order (LNR)
Postorder (LRN)
trees and forest
definition
Tree of degree m m-ary tree
forest
storage structure
parent representation
Sequential storage; storage address = logical address
child representation
Adjacency list storage; directed graph storage structure
Child Brothers/Binary Tree Notation
Number of forest nodes
Given the number of forest edges and nodes, find the number of trees contained in the forest.
Forest and binary tree relationship
The number of nodes whose right child pointer is empty
The number of nodes in the left subtree of the forest = the node tree of the first tree in the forest
Traversal and ordered trees
tree: first root
Forest: Preface
Binary tree: preorder
tree: back root
Forest: Afterword
Binary tree: in-order
Tree, forest and binary tree transformations
Traverse
BFS breadth first search
Complexity analysis
Spanning trees and spanning forests
DFS depth first search
Traversal and connectivity
Recursive and non-recursive conversions
recursion = stack
Level traversal
auxiliary queue
Traverse a sequence to construct a binary tree
Middle order (required) First order/Subsequent
Clue tree traversal requires stack
Postorder traversal
To find the path from ancestors to descendants, you can use first/inorder traversal
Find the heterogeneous number of binary trees in a known order
application
Huffman tree
weighted path length
definition
The binary tree with the smallest weighted path length (WPL); also called the optimal binary tree
A Huffman tree with degree m is a strict m-ary tree.
structure
Greedy, take the two nodes with the smallest weight each time as the left and right subtrees of the new node. The new node weight is the sum of the left and right subtrees, and put them into the selectable node set.
nature
The initial nodes are all leaf nodes
The smaller the weight, the longer the path to the root node.
n-1 new nodes are created, and the total number of nodes is 2n-1
In a Huffman tree with degree m, the leaf node is n, then the number of non-leaf nodes is
The number of leaf nodes is the number of codes of different symbols
Huffman coding
fixed length encoding
Each character is represented by equal length binary bits
prefix encoding
No encoding is a prefix of another encoding
clue binary tree
Physical/Storage Structure
Flag field meaning
concept
clue
cueing
Related questions
Number of empty links after clueing
The traversal that still requires stack support is the post-order clue tree
Not every node can find its predecessor and successor through clues
Given the post-order clue binary tree, finding the post-order successor still cannot be completely solved.
Binary Search Tree BST
definition
operate
insert
Find
Recursive implementation
Non-recursive implementation
delete
Leaf nodes are deleted directly
x has only one left/right subtree child node connected to its parent node
x has two subtrees on the left and right to supplement the predecessor and successor
structure
nature
If a node is deleted and then inserted, the sorted tree before and after may be different.
Question calculation
ASL (average search length)
Successfully found length
Failed to find length
Increasing sequence traversal = in-order traversal
Illegal search path sequence
Balanced Binary Tree AVL
balancing mechanism
balancing factor
Operating principle
Insert/Delete
rotate
Rotation points
Adjust the minimum imbalance subtree
LL, RR rotate once, LR, RL rotate twice (first inside and then outside)
The left heavy rotation reduces the left depth, the right counterrotation reduces the right depth.
Root to connect predecessor and successor [Compare connections based on numerical values]
Rotation method
LL (left child left subtree)
The left subtree is rotated and balanced by lowering one level
RR (right child right subtree)
LR (left child right subtree)
RL (right child left subtree)
calculate
The minimum number of nodes required to construct an AVL with height h
Given an AVL with n nodes in total, find its maximum depth
It is known that the height of AVL is n, and the balance factor of all non-leaf nodes is 1, find the total number of nodes
And search the collection
operate
Merge Union
Find ancestors Find(S,x)
Initialize Init(S)
picture
Related concepts
directed graph
Arc head (vertex)
Arc tail (vertex)
Undirected graph
Simple graph, multiple graph
Simple graph: no self-loops, no repeated edges
Multiple graphs: self-loops and repeated edges
complete graph
The number of edges in a simple graph reaches the upper limit
subplot
Edges and vertices are both subsets and can form a graph
Connectivity, connected graphs and connected components
Connectivity: There is a path between u and v
Connected graph: any two points in the graph are connected
Connected components: maximal connected subgraphs in undirected graphs
Strongly connected, strongly connected components
Strongly connected: u and v in the directed graph are reachable to each other
Strongly connected graph: Any two points in the directed graph are reachable to each other.
Strongly connected components: maximal wall-connected subgraphs in directed graphs
Spanning tree, spanning forest
Spanning tree: a minimal connected subgraph that contains all the vertices in the graph
Spanning forest: Spanning trees of connected components in a non-connected graph constitute a spanning forest.
Minimally connected subgraph: maintain the connectivity of the graph and keep the number of edges as small as possible
Vertex degree, in-degree and out-degree
Vertex degree: the number of edges connected to a vertex in an undirected graph
Bian's Quanhe.com
Net: Picture with authority
Dense graph, sparse graph
Paths, path lengths and loops
Path: Vertex sequence [sequence formed by edges composed of vertices and adjacent vertices]
Loop/Loop: The first and last vertices in the path are the same
Simple path, simple loop
distance
directed tree
undirected graph forest
The number of undirected graph forest trees with n vertices and e edges
storage structure
sparse matrix
cross linked list
adjacency list method
adjacency multiple list
dense matrix
adjacency matrix
directed graph
Undirected graph
nature
Traverse
Guangsou bfs
Deep search dfs
application
minimum spanning tree
Prim's algorithm
Kruskal algorithm
shortest path
Dijkstra
Floyd
directed acyclic graph expression
topological sort
AOV network
Number of ordered sequences
Critical Path
AOE network
The earliest time the event occurred
Latest occurrence time of the event
The earliest start event of the activity
The latest start time of the event
time margin
sort
basic concept
keyword ordered process
stability
The specific elements are unknown, at least the number of comparisons
trip
During the sorting process, all elements whose final positions have not yet been determined are processed once.
Internal sorting
Common types
insertion sort
insert directly
Time complexity
stable sorting
Features
After each sorting, the first i bits are in order, and there may be values after i bit that change the original i bits.
Insert in half
Use a half-search on the sorted sequence search part
sequential storage
Time complexity
stable sorting
Hill sort
Algorithm description: Select increment d, divide the original sequence into several parts, and then perform insertion sort on each part.
Time complexity
space complexity
Unstable sorting [reason for grouping]
swap sort
Bubble Sort
Algorithm description [Maximum bubble pops up] Each time sorting puts the smallest/largest element at the end of the sequence/the final position at the head of the queue through sequential traversal, comparison and exchange.
Time complexity
space complexity
stable sorting
Features
The first i digits or the last i digits (according to order or reverse order) are the final ordered order.
Quick sort
Based on the idea of divide and conquer [two points]
Time complexity [related to the depth of the recursive stack]
Space complexity [stack depth]
Features
The left side of a value is a value less than it, and the right side is a value greater than it.
When the sequence is basically in order or reverse order, the efficiency is lowest: affected by unbalanced partitioning
Real questions
2014) To perform quick sorting on 15 elements, the minimum number of times to compare elements is
selection sort
Simple choice
Algorithm description: Find the element with the smallest keyword among the next n-i elements in each pass, and exchange it with the i-th element.
Time complexity
space complexity
Unstable sorting [multiple minimums take the last traversed position]
Features
The first i digits or the last i digits (according to order or reverse order) are the final ordered order.
Heap sort
Algorithm description Binary heap: complete binary tree, both left and right subtrees are smaller than/larger than the root node [small/large top heap]
Time complexity
space complexity
Heap building time【Calculation supplement】
Features
The position of the last non-leaf node is len/2 [the root node subscript is 1]
Unstable sorting [the rear position may be adjusted to the root during adjustment]
merge sort
Algorithm description: two-way merge algorithm: initially the length of each sub-table is 1, and then continuously merges and sorts them in pairs, and finally merges and grows into an ordered sequence of n
Time complexity [independent of the initial state of the sequence]
space complexity
stable sorting
Features
When there are files that are large enough to fit in memory, a divide-and-conquer merge sort is used.
Radix sort
The algorithm description is sorted one by one based on the size of the numbers in the key positions.
Time complexity
space complexity
Common keyword sorting
Most significant endian MSD
Least Significant First LSD
stable sorting
sort comparison
time complexity
in order
Direct insertion, bubble sort
Quick sort
In the case of disorder [average]
Simple selection, direct insertion, bubble sort
Stack sort, quick sort, merge
space complexity
Simple selection, insertion, bubbling, Hill, stack sort
Quick sort
merge
Algorithm stability
stable sorting
Unstable sorting
Storage structure impact
sequential storage
chain storage
Algorithm process characteristics
[Each sorting operation can obtain at least one final ordered order]
Heap sort, quick sort, simple selection, bubble sort
[Comparison times and initial sequence]
Unrelated two-way merge sort, simple selection sort, radix sort
About quick sort, direct insertion sort, bubble sort, heap sort, Hill sort
[Number of sorting passes and initial sequence]
Independent direct insertion sort, halved insertion sort, Hill sort, simple selection sort, merge sort, radix sort
About bubble sort and quick sort
external sort
basic concept
General method merge sort method
Total external sorting time = memory sorting time, external storage information reading and writing time, internal merging time
Number of merged beds = tree height =
Total number of merge comparisons ==
Number of I/O operations read into the merged segment and written into the merged segment (in blocks)
Illustration
The initial sequence is 12 unordered data
Divide the memory data into multiple blocks, first sort the blocks to form an ordered string
Merge two sorted sub-blocks into a larger block [two-way merge]
Continue to merge small merged segments into larger merged segments
Multi-way balanced merging and loser tree
k-way balanced merge
At most k segments can be merged into one
In each pass, if m blocks are merged, then blocks will be obtained in one pass.
winner tree/loser tree
winner tree
loser tree
Use loser trees to speed up sorting
permutation-selection sort
principle
Initial segment creation diagram
Each group is divided into 6 elements, and the initial number of groups is divided into at least 4 groups.
CHOOSE YOUR FIRST MINIMAX 29
Choose a larger MINIMAX 38 than in the initial segment
Same reason
Until no MINIMAX is selected, the initial segment is considered completed.
Loser Tree Utilization
best merge tree
principle
The optimal merge tree with additional virtual short
Additional supplementary number of virtual breaks
C11 syntax
typedef keyword
struct structure
grammar
Without typedef tag
with typedef tag
Bad syntax
Structure nesting
self-reference
Cross-referencing
The difference between struct in C and C
Pointer T *t
address and value
& Get address/reference (alias)