Wondershare EdrawMind
MindMap Gallery data structure
- 31
data structure
Data structure mind map, such as a data type is a collection of values and a set of operations defined on this collection. I haven’t finished memorizing it at the beginning, so let’s take a look.
Edited at 2023-07-20 22:03:53
- Recommended to you
- Outline
data structure
introduction
data structure
basic concept
data
data element, data item
data objects, data structures
Data types, abstract data types
type of data
A collection of values and a set of operations defined on this collection.
Atomic type
Its value cannot be further divided: bool, int, etc.
structure type
A data type whose value can be decomposed into components: struct
Abstract data type (ADT)
Abstract data organization and operations related to it
Three elements
logical structure
linear structure
One to one
nonlinear structure
Set structure
tree structure
one to many
graph structure
many to many
Data operations
Define basic operations based on logical structure and actual needs
Add, delete, modify, check
Define a data structure (define an ADT)
Physical structure (storage structure)
sequential storage
chain storage
Index storage
Hash storage (hash storage)
Non-sequential storage (discrete storage)
Implement a data structure (determine the storage structure of ADT)
algorithm
Algorithm definition
A description (a finite sequence of instructions) of the steps to solve a particular problem
Important features
Finiteness
The algorithm must be finite, but the program can be infinite
certainty
The same input can only produce the same output
feasibility
Implemented through a finite number of basic operations
enter
Zero or more inputs
output
one or more outputs
Characteristics of a “good” algorithm
correctness
readability
Comment
Robustness
React to illegal data
High efficiency and low storage requirements
Time complexity and space complexity
measure of efficiency
time complexity
Analyze the time complexity of a program
Addition rule
When adding multiple terms, only the highest order term is retained, and the coefficient becomes 1
T(n)=T₁(n)+T₂(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
multiplication rule
Multiple multiplications are retained
T(n)=T₁(n)×T₂(n)=O(f(n))×O(g(n))=O(f(n)×g(n))
Common time complexity orders of magnitude
(often refers to the order of power)
Solution: Only consider the relationship between the number of loops in the deepest loop and n
Worst time complexity
average time complexity
When evaluating algorithms, only consider these two
best time complexity
space complexity
It is defined as the storage space consumed by this algorithm, which is a function of problem size n, S(n)=O(g(n))
Algorithms work in place
The memory space required by the algorithm is constant, S(n)=O(1)
calculate
Ordinary program
Find variables related to the size of the space occupied and the size of the problem
Analyze the relationship between the occupied space x and the problem size n: x=f(n)
The order of magnitude O(x) of x is the algorithm space complexity S(n)
recursive program
Find the relationship between the depth of the recursive call x and the problem size n: x=f(n)
The order of magnitude O(x) of x is the algorithm space complexity S(n)
Note: The storage space required for functions at each layer of the algorithm is different. If the above rules are not met, additional analysis is required.
linear data structure
linear table
logical structure
Definition of linear table
Same data type, finite sequence
Table length, empty table
Table header, table footer
precursor, successor
order
Bit order starts from 1, array subscript starts from 0
Basic operations of linear tables
initialization table
InitList(&L)
destroy operation
&DestroyList(&L)
insert operation
ListInsert(&L,i,e)
Delete operation
ListDelete(&L,i,&e)
Find by value
LocateElem(&L,e)
Bitwise search
GetElem(&L,i)
Other common operations
Ask for table length
Length(L)
Output operations
PrintList(L)
short operation
Empty(L)
Notice: ①Operation of data (memory mode) -> creation, destruction, addition, deletion, modification and search; ②The naming must be readable; ③The modification results of the parameters need to be "brought back", and the reference "&" of the parameters must be passed in
Implementation of linear table
Storage structure (physical structure)
Sequence table (sequential storage)
definition
Adjacent logically and physically
sizeof(ElemType): Get the size of a data element
accomplish
static allocation
There is "dirty data" left in the memory; when initializing the sequence table, length must be assigned to 0
dynamic allocation
C language dynamically applies for and releases memory space
The header file where the malloc and free functions are located: #include<stdlib.h>
malloc function
L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
The data pointer points to the starting address of an entire allocated continuous storage space.
free function
free(ElemType *p)
C dynamically apply for and release memory space
new
L.data=new ElemType(InitSize);
delete
Features
① Random access
Can find the i-th element in O(1) time
②High storage density
Each node stores only data elements
③It is inconvenient to expand the capacity
④ Insertion and deletion operations are inconvenient
Need to move a lot of elements
Basic operations
Pay attention to the relationship between bit order and array subscripts
insert
time complexity
Best case: insert to the end of the table
Best time complexity = O(1)
Worst case scenario: plug into the header
Worst time complexity = O(n)
average situation
delete
[Gallery: Insert operation]
time complexity
Find
Bitwise search
[Gallery: Search by bit]
Time complexity: O(1)
Find by value
In C language, structure comparison cannot use "==" directly.
[Gallery: Search by value]
time complexity
Linked list (linked storage)
nonlinear data structures