Big talk data structure  Summary
Read the book "Dahua data structure" and summarize some things; The summary is rough. Some ideas can't be understood for the time being. Put them aside first, and then go back to digest these knowledge points after learning other things
1. Data structure
A data structure is a collection of data elements that have one or more specific relationships with each other
Logical structure of data
1.Set structure Belonging to the same set, the elements are equal 2.linear structure Element one to one 3.Tree structure One to many hierarchical relationship of elements 4.Graphic structure Element many to many
Physical structure of data
1.Sequential storage Elements are stored in storage units with continuous addresses, and the logical relationship of data is consistent with the physical relationship 2.Chain structure Store the data in any storage unit of the task, and the address can be even discontinuous; Find the associated data location through the pointer
2. Time algorithm complexity
Derivation method
1.Replace all addition constants in time with constant 1 2.In the modified sub function, only the highest order is retained 3.If the highest order exists and is not 1, remove the constant multiplied by this term and the result is large O rank
 Constant order O(1)
int sum = 0,n=100; //Execute once sum = sum+n; //Execute once System.out.printf(sum); //Execute once O(1)
 Linear order O(n)
 Logarithmic order Ologn
 Square order O(n) ²)
3. Linear table
 Sequential storage structure
Continuous storage location, slow insertion and fast search(Subscript lookup)
 Linked Storage Structure
 Single linked list
 Static linked list
 Circular linked list
 Bidirectional circular linked list
Search is slow, insert and delete blocks; Space for time
4. Stack and queue
 Stack
A stack is a linear table that restricts insertion and deletion operations only at the end of the queue Function: recursion Application: evaluation of four operation expressions(Postfix Expression )
 queue
A queue is a linear table that only allows insertion at one end and deletion at the other
5. String
String is a finite sequence of 0 or more characters, also known as string
 KMP matching algorithm
6. Tree
 depth
The maximum level of nodes in a tree is called the depth or height of the tree
 Representation method
Parent representation, child representation, child brother representation
 Binary tree
1.Each node has at most two subtrees, and there are no nodes with a degree greater than 2 in the binary tree 2.The number of left and right words is in order and cannot be reversed 3.If there is only one subtree, you should also distinguish whether it is a left subtree or a right subtree Five basic forms 1.Empty binary tree 2.There is only one root node 3.The root node has only the left subtree 4.The root node has only the right subtree 5.The root node has both left and right subtrees
 Special binary tree
1.Oblique tree 2.Full binary tree(The number of left and right nodes is exactly the same) 3.Complete binary tree(On a certain layer, the number of left and right nodes is equal)
 Binary tree traversal method
1.Preamble Starting from the root node, traverse from left to right 2.Middle order Starting from the leftmost node, traverse the root node first, and then the right node 3.Post order Start from the leftmost node, first traverse the right node, and finally traverse the root node 4.level traversal Start from the root node and traverse layer by layer from left to right

Application of tree
huffman tree Weighted path length WPL The smallest binary tree is called Huffman tree Huffman codingcompress
7. Figure Graph
A graph is composed of a set of edges between vertices of a finite non empty set of vertices, which is usually expressed as: G(V,E), where G is a graph, V is the marriage of vertices in graph G, and E is the set of edges in graph G
Some definitions in the figure

The data elements in the graph are called vertices

No vertices are allowed in a graph structure

There may be a relationship between any two vertices in the graph. The logical relationship between vertices is represented by edges, and the edge set can be empty

Definition of edge
Undirected edge Directed edge
8. Search
Sequential table lookup
Ordered table lookup
 Half search
 Interpolation search
 fibonacci search
Linear index lookup

Dense index
Dense index means that in linear index, each record in the data set corresponds to an index item; Example: Notepad

Block index
Disorder within blocks and order between blocks; Ways of storing books in reference libraries and Archives

Inverted index
Common structure of index entries: Secondary key Record number table
Binary sort tree
Balanced binary tree (AVL tree)
Construction thought: Whenever a node is inserted, first check whether the balance of the tree is damaged due to the insertion. If so, find out the minimum unbalanced subtree. On the premise of maintaining the characteristics of binary sort tree, adjust the link relationship between the nodes of the minimum unbalanced subtree and rotate it accordingly to make it a new balanced subtree
Multiple lookup tree (Btree)
Hash table lookup
The most suitable solution of hash technology is to find records equal to the given value; However, the maximum value, minimum value and other results cannot be found Construction method of hash function: 1.direct addressing 2.Digital analysis 3.Square middle method 4.Folding method 5.Division method 6.Random number method How to handle hash conflicts: 1.Open addressing The open addressing method for conflict resolution is called linear detection method The situation that is not a synonym but needs to compete for the same address is called accumulation To prevent keywords from piling up in one area. Secondary detection method is adopted/Recalculate address by random detection method 2.Hashing function method 3.Chain address method 4.Public spillover area act
9. Sort
Sorting and classification
According to whether all the records to be sorted are placed in memory during sorting, sorting is divided into:Inner sort and outer sort Inner sorting: Internal sorting is that all records to be sorted are placed in memory in the whole process of sorting. External sorting: Because there are too many records to be sorted, they cannot be placed in memory at the same time. The whole sorting process always needs to exchange data between internal and external memory for many times Internal sorting performance impact points: 1.Time performance 2.Auxiliary space 3.Complexity of algorithm Internal sorting is divided into: Insert sort, swap sort, select sort and merge sort
Sort type
Bubble sort, simple selection sort, direct insertion sort, Hill sort, heap sort, merge sort, quick sort
 Quick sort!!!
 Random fast scheduling
 Two way fast platoon
 Three way fast platoon
Efficiency comparison of sorting methods
complimentary close
 Nothing is impossible. Don't be limited by rules
 If you have a dream, defend it. When others can't do it, they want to tell you, and you can't. If you want something. Just try to fight for it.