Wondershare EdrawMind
MindMap Gallery Data structure mind map
- 35
Data structure mind map
Data structure mind map to help understand the outline of data structure, including introduction, linear list, stack and queue, string, array and generalized table super detailed introduction and code. In addition, there are trees, graphs, and general search contents. Do not miss passing through.
Edited at 2022-06-15 17:11:43
- 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
Arrays and generalized tables
array
Basic concepts of arrays
From the logical structure point of view, the one-dimensional array A is a finite sequence composed of n (n>1) data elements of the same type a1, a2,..., an. Its logical expression is: A=(a1,a2,…,an) Among them, ai (1≤i≤n) represents the i-th element of array A. A two-dimensional array A with m rows and n columns can be regarded as a one-dimensional array in which each data element is a one-dimensional array of the same type. It can be seen that multi-dimensional arrays are a generalization of linear tables.
Taking the C/C language as an example, the array data type has the following properties:
One-dimensional array storage structure
Storage structure of two-dimensional array
Compressed storage of special matrices
The main forms of special matrices are: (1) Symmetric matrix (2) Upper triangular matrix/lower triangular matrix (3) Diagonal matrix They are both square matrices, that is, they have the same number of rows and columns.
subtopic
subtopic
sparse matrix
subtopic
The difference between sparse matrices and special matrices
triple representation of sparse matrices
Convention: The non-zero elements represented in the data field are usually arranged in row-major order. It is a storage structure in which subscripts are ordered in rows. This ordered storage structure simplifies most matrix operations algorithms.
subtopic
Cross linked list representation of sparse matrix
subtopic
generalized table
Definition of generalized table
Important concepts of generalized tables:
The length of a generalized table is defined as the number of elements contained in the outermost layer. The depth of a generalized table is defined as the multiplicity of contained parentheses. Among them, the depth of atoms is 0, and the depth of empty tables is 1. The head of the generalized table GL is the first element a1, and the remaining parts (a2,...,an) are the tail of GL. The tail of a generalized table is always a generalized table. An empty table has no header or footer. The length of a generalized table is defined as the number of top elements in the table. The depth of a generalized table is defined as the maximum number of levels of brackets it contains. Among them, the depth of atoms is 0, and the depth of empty tables is 1.
Storage structure of generalized table
subtopic
picture
Basic concepts of graphs
The storage structure and basic operation algorithms of graphs
Graph traversal
Spanning tree and minimum spanning tree
shortest path
topological sort
AOE network and critical path
Find
Basic concepts of search
Linear table search
Search in number table
Hash table lookup
Trees and Binary Trees
Basic concepts of trees
tree definition
subtopic
Basic terminology for trees
subtopic
subtopic
subtopic
subtopic
tree nature
Basic operations on trees
subtopic
subtopic
tree storage structure
Parent storage structure
Child chain storage structure
Child sibling chain storage structure
Storage structure of generalized table
Concept and properties of binary trees
Binary tree storage structure
Basic operations of binary trees and their implementation
Binary tree traversal
Construction of binary tree
clue binary tree
Huffman tree
Solving Equivalent Problems Using Union-Find Sets
string
Basic concept of string
A string (or character string) is a finite sequence of zero or more characters. string contained in linear list
The number of characters contained in a string is called the length of the string (or string length). A string containing zero characters is called an empty string and is represented by Ф.
String equality: When the lengths of the two strings are equal and the characters at each corresponding position are the same. All empty strings are equal.
Substring: A subsequence consisting of any consecutive characters in a string (including empty strings) is called a substring of the string. A true substring is any substring that does not contain itself.
Basic operations on strings
StrAssign(&s, cstr): Assign the string constant cstr to the string s, that is, generate a string s whose value is equal to cstr. StrCopy(&s,t): string copy. Assign string t to string s. StrEqual(s,t): Determine whether strings are equal. Returns true if the two strings s and t are equal; otherwise returns false. StrLength(s): Find the string length. Returns the number of characters in string s. Concat(s,t): String concatenation: Returns a new string formed by concatenating two strings s and t. SubStr(s,i,j): Find substring. Returns a substring consisting of j consecutive characters starting from the i-th (1≤i≤n) character in string s.
storage structure
The logical relationship between elements in a string is the same as that in a linear table, and a string can use the same storage structure as a linear table.
String sequence storage structure
Each unit (such as 4 bytes) only stores one character, which is called a non-compressed format (its storage density is small).
Each unit stores multiple characters, which is called a compressed format (its storage density is high).
String chain storage structure
When the chain node size is 1, the node type of the chain string is declared as follows:
pattern matching
BF algorithm analysis
Brute-Force is referred to as BF algorithm, also known as simple matching algorithm. Use an exhaustive approach. BF means violence!
For example, s="aaaabcd", t="abc". BF algorithm idea: starting from each character of s, match the characters of t in sequence.
i, j scan strings s and t respectively i loops from 0 to s.length-t.length. For each s[i], k=i,j=0 starts comparison If t scan is completed, return i If all comparisons of s are completed without return, then -1 is returned.
KMP algorithm
KMP is to quickly find the substring you want from the main string. Only moves the pattern string backward, the comparison pointer does not move back
Based on the BF algorithm, the space-for-time method is used to extract and save information that is beneficial to matching. Extract information from s or t? Match different characters starting from s each time, and t always starts matching from t0 -> Extract the information in t What information is in t? -> Partial matching information.
stacks and queues
stack
stack definition
Several concepts of stack
The sequential storage structure of the stack and its basic operation implementation
The chain storage structure of the stack and its implementation of basic operations
queue
queue definition
Basic operations
Queue’s sequential storage structure and its basic operation implementation
Queue chain storage structure and its implementation of basic operations
linear table
Linear table and its logical structure
Definition of linear table
A linear list is a finite sequence of data elements with the same characteristics.
Finiteness: The number of data elements is limited. Consistency: All elements have the same nature, that is, they belong to the same data type. Seriality: Data elements are uniquely determined by logical sequence numbers. A linear list can have elements with the same value. Logical relationship: There is a 1-to-1 relationship between elements.
The number of elements contained in the linear table is called the length of the linear table, represented by n, n≥0. When n=0, it means that the linear list is an empty list, that is, the list does not contain any elements.
Abstract data type description of linear table
1 Initialize the linear list InitList(&L): Construct an empty linear list L. 2 Destroy the linear list DestroyList(&L): Release the memory space occupied by the linear list L. 3 Determine whether the linear list is an empty list ListEmpty(L): If L is an empty list, return true, otherwise return false. 4 Find the length of the linear list ListLength(L): return the number n of elements in L. 5 Output linear list DispList(L): When linear list L is not empty, the value range of each node in L is displayed sequentially. 6 Find a data element at the specified position 8 in the linear table L. GetElem(L, i, & e): Use e to return the value of the i-th (1≤i≤n) element in L. 7 Locate and search LocateElem(L, e): Return the logical bit sequence in which the first value range in L is equal to e. If such an element does not exist, the return value is 0. 8 Insert a data element ListInsert(&L, i, e): Insert a new element e before the i-th (1≤i≤n) element of L, and the length of L is increased by 1. Delete data elements ListDelete(&L, i, &e): Delete the i-th (1≤i≤n) element of L, and use e to return its value, and the length of L is reduced by 1.
Basic operations: InitList, DestroyList Reference operation: the result of the operation does not change the structure Processing operations: the result of the operation changes the structure
Abstract data types for linear tables:
Sequential storage of linear tables—sequential tables
Linear table sequential storage structure: all elements in the linear table are stored according to the sequential storage method. That is, they are stored in a continuous storage space in the memory in logical order.
Implementation of basic operations in sequence tables
Algorithm parameter description
Delete all elements with value x in the sequence list
subtopic
Linked storage of linear lists—linked lists
Overview of linked lists
Each element in a linear list has a unique predecessor element and successor element.
When designing a chain storage structure, each logical element is stored separately with a node. In order to express the logical relationship, a pointer field is added.
Each physical node adds a pointer field pointing to the subsequent node Single linked list. Each physical node adds a pointer field pointing to the successor node and a pointer field pointing to the predecessor node Double linked list.
. Comparison of linked lists and sequential lists
storage density
Single list
Advantages of adding a head node to a singly linked list
Characteristics of singly linked list
subtopic
Implementation of basic operations of linear tables on singly linked lists
Double linked list
In the linked storage structure of a linear list, each physical node adds a pointer field pointing to the successor node and a pointer field pointing to the predecessor node Double linked list.
Advantages of doubly linked list:
circular linked list
application
Natural join problem between two tables
Design basic computing algorithms
Why is it different from the general tail insertion method for table creation?
ordered list
The concept of ordered list
Storage structure of ordered list and its basic operation algorithm
Ordered list merging algorithm
introduction
What is data structure
Data structure definition
Data is a collection of numbers and characters that describe objective things
A data item is the smallest unit of data with independent meaning, also called a field or domain.
Data object refers to a collection of data elements with the same nature, which is a subset of data
Data structure refers to all data elements and the relationship between data elements. It can be regarded as a collection of data elements that have a certain relationship with each other.
Data structures usually include
logical structure of data
Composed of logical relationships between data elements
Data storage structure
The stored representation of data elements and their relationships in computer memory, also known as the physical structure of the data
Operations on data structures
operations applied to the data
logical structure
Representation of logical structure
Graphic representation
Use tables or graphics to directly describe the logical relationship of data
Two-tuple representation
Data logical structure representation, such as: B=(D, R). <x.y>, x is the predecessor element of y, and y is the successor element of x. If an element has no predecessor element, the element is called the beginning element; if there is no successor element, the element is called the terminal element. For symmetric pairs, round brackets can be used instead of angle brackets.
Type of logical structure
gather
linear structure
There is a one-to-one relationship between data elements. Its characteristic is that both the start element and the terminal element are unique.
tree structure
One-to-many relationship.
Graphical structure
many-to-many relationship
storage structure
sequential storage structure
The sequential storage structure uses a set of consecutive storage units to store all data elements. Advantages: high storage efficiency, random access to elements Disadvantages: Inconvenient to modify data
chain storage structure
Advantages: Easy to modify data Disadvantages: low storage space utilization, unable to perform random access to elements
Index storage structure
Advantages: High search efficiency. Disadvantages: Need to create index tables, thus increasing space overhead
Hash (or hash) storage structure
Advantages: fast search speed Features: It only stores data but not logical relationships. It is generally only suitable for occasions that require fast search and insertion of data.
Data types and abstract data types
Data type (c/c)
int type
The int type can have three modifiers, namely short (short whole sentence), long (long whole sentence) and unsigned (unsigned integer).
Boolean Boolean value type
float type
double type
char type
abstract data type ADT
It refers to the logical data structure and operations on the logical data structure that are abstracted from the mathematical model of the problem when the user designs the software system, without considering the specific storage structure of the computer and the specific implementation algorithm of the operation.
Algorithm and description
characteristic
Finiteness
certainty
feasibility
There is input
The quantity that is the object of algorithm processing is usually embodied as a set of variables in the algorithm. An algorithm has zero or more inputs
There is output
A set of quantities that have a definite correspondence with the "input". An algorithm has one or more outputs
Design goals
correctness
The algorithm is required to correctly perform pre-specified functional and performance requirements. This is the most important and basic standard
usability
The algorithm is required to be easy to use, also called user-friendliness.
readability
The algorithm is required to be easy to understand, and the logic of the algorithm must be clear, simple and structured
Robustness
The algorithm is required to have good fault tolerance, that is, to provide exception handling, to be able to check unreasonable data, and to avoid frequent abnormal interruptions or crashes.
Efficiency and storage requirements
Usually the efficiency of an algorithm mainly refers to the execution time of the algorithm; the amount of algorithm storage refers to the maximum storage space required during the execution of the algorithm.
Analysis of Algorithms
Time performance analysis of the algorithm (CPU time)
Frequency of algorithm T(n)
Suppose the size of the algorithm is n. If 10 integers are sorted, the problem size n is 10. Algorithm time analysis is to find the number of executions of all original operations of the algorithm (also called frequency), which is a function of the problem size and is represented by T(n). The execution time of the algorithm is roughly equal to the time required for the original operation*T(n)
Time complexity, T(n) is represented by "O"
Since algorithm analysis is not a comparison of absolute time, after calculating T(n), it is usually further expressed by time complexity. Time complexity: expressed in the order of magnitude of T(n), recorded as T(n)=O(f(n)) Also called asymptotic time complexity, it means that as the problem size n increases, the growth rate of the algorithm execution time is the same as the growth rate of f(n). Therefore, algorithm time complexity analysis is actually a time growth trend analysis.
The execution time of an algorithm without loops is independent of the problem size n and is denoted as O(1), also called constant order. The execution time of an algorithm with only one loop increases linearly with the growth of the problem size n, which is recorded as O(n), also called linear order. The time complexity of other commonly used algorithms includes square order O(n2), cubic order O(n3), logarithmic order O(log2n), exponential order O(2n), etc.
Time complexity analysis of recursive algorithms
Algorithm time performance comparison:
Suppose there are two algorithms for solving the same problem: A and B. If the average time complexity of algorithm A is O(n), and the average time complexity of algorithm B is O(n2). Generally speaking, the time performance of algorithm A is considered to be better than algorithm B.
Simplified algorithm time complexity analysis
Spatial performance analysis of algorithms (memory time)
Briefly analyze
Space complexity analysis of recursive algorithms
The purpose of algorithm analysis:
Analyze the spatiotemporal efficiency of the algorithm in order to improve the algorithm performance
Solving problems from a data structure perspective