1. Data structure concept
data 、 data elements 、 Data item 、 Data objects 、 data structure 、 Logical structure 【 aggregate 、 Linear structure 、 Tree structure 、 The graph structure 】、 Physical structure 【 Sequential storage structure 、 Chain storage structure 】
(1) data structure
A collection of data elements that have one or more specific relationships with each other .
(2) Logical structure
The relationship between data elements .【 aggregate -- There's no relationship between the elements 、 Linear structure -- One-to-one correspondence 、 A tree structure -- One to many and hierarchical 、 The graph structure -- Many to many 】
There is no relationship between elements except that they belong to the same set .
2) Linear structure
There is a one-to-one correspondence between the elements . Apart from the first element , Every element has a precursor . Except for the last element , Every element has a successor .
3) A tree structure
A one to many relationship .
4) The graph structure
There is a many to many relationship between elements .
(3) Store results
The storage of logical structures in a computer .
1) Linear storage
The most common is arrays .
2) Chain store
Algorithm 、 Algorithm characteristics 、 Algorithm efficiency measurement method 、 Time complexity .
A description of the steps to solve the problem , A finite sequence of instructions in a computer . And each instruction set is one or more operations .
(2) Algorithm characteristics
1． Input （0 Or multiple inputs ）、
2． Output （ One or more outputs ）、
3． There is poverty （ There are limited steps 、 Each step is completed within the accepted time ）、
4． determine （ The meaning is certain , No ambiguity ）、
5． feasible （ Each step is executed a limited number of times ）.
(3) Time complexity
1． Constant order [ Operation steps and data size n No problem ]、
2． Linear order [a*n+b]、
3． Logarithmic order [longN]、
4． Exponential order [n²]
3. The linear table
The linear table 、 Linear sequential storage 、 Insertion and deletion of sequential storage 、 Linear watch chain storage 、 Read the linked list - Insert - Delete 、 Single linked list creation - Delete entire table 、 Insertion of static linked list - Delete 、 Circular linked list 、 Double linked list .
A finite sequence of zero or more data elements .
(1) Sequential storage of linear tables
Use a continuous storage unit to store the data elements of the linear table in turn .【 The logical relationship is consistent with the physical storage relationship 】
- Properties of the order table
- The storage address of the linear table
- The maximum capacity MaxSize
- The current length of the linear table ：Length
- Reading sequence table
Elements can be obtained directly from data and subscripts .Array[i]
- Sequence table storage insert
The element after the insertion position is moved backward as a whole
from length To the storage location i, Move the whole back one position . Then insert the new data into the subscript i Location .
- Deletion of sequential table storage
After deleting the element, the whole element will be migrated
Delete the subscript as i Location data . from i+1 To length The order of traversal , The whole element moves forward one bit .
(2) Chain storage of linear table
Node data structure 【 Data fields and pointer fields . The number field holds the data , The pointer field points to the location of logically adjacent successor elements 】、
1． Linked list traversal read
From the beginning , Get node , Then read the next node according to the pointer field , repeat , Up to the end of the list . No round reading , Insert and delete , All need the above traversal way .
Start at the head of the list , Get node data , Then get the node specified by the pointer field . So circular , Until the pointer field is null Location
2． Insert the elements of the linked list
Loop the list to the specified location 、 Suppose you need to insert a node P And the nodes q Between , Where nodes p->next Point to q. Then the new node will be e Insert p,q Between .S->next = p->next,p->next=s
3． Delete the elements of the linked list
Loop the list to the specified location 、 Suppose you need to delete a node q, node q The precursor of p, Delete q, Need to put q The pointer to the precursor element of the q Successor element ,p->next = p->next-next, If you need to release memory actively , Need to be right q Manual memory release
4． Single linked list creation
- The first interpolation
The newly created node , Always insert after the head node , The pointer field of the new element points to the previous first element .
- The tail interpolation
Tips , Use reservation PreNode. Every time a knot occurs . take PreNode The pointer field of is pointing to the new node .
During the cycle , Always record the node of the last loop preNode【 Execute at the end of the loop preNode= node】, The new node links to preNode after 、 Always add new nodes at the end
(3) Static list
It's a little complicated.
Definition 【 Use arrays to describe linked lists 】、 Node structure 【 Data fields data And pointer fields cur】、
1． Spare linked list
A linked list of unused nodes in an array . Provide new data for static linked list .
2． First and last nodes
The data fields of the first node and the last node do not store values , Use only pointer fields , The pointer field of the first node stores The subscript address of the first unused node in the alternate list , The pointer field of the last node stores The subscript address of the first node where the data is stored .
3． Insertion of static linked list
Suppose you insert an element at position i A place ,
- Find the insertion position and adjust the spare list
Get the first spatial subscript of the alternate linked list j【 meanwhile , The location of the second node in the original spare list cur Store in space A pointer to the domain cur】, Values are stored in nodes arr[j].data in ,
- Static list insertion
The pointer field of the new element points to the original i Elements , It turns out that No i-1 The pointer field of the element of points to the new element
find The first i The antecedents of elements ( That is the first. i-1 Elements ) Below is K, And then the original section i Elements arr[k].cur String after the new element arr[j].cur = arr[k].cur, Then assign the position of the new element to i-1 Pointers to elements arr[k].cur =j】
- The deletion of static linked list
Linked list node delete 、 Adjust the spare list
- The following subsequent pointer of a node is assigned to a subsequent pointer
- Spare list adjustment
It's special in static linked list , The deleted node needs to be recycled , Rewriting is added to the alternate list , And add the head position of the spare list . namely s->cur= space.cur;space.cur=s
(4) Circular linked list
The pointer field of the terminal chain node of a single linked list is from null Change to pointer to head . It's called a circular list .
(5) Double linked list
The node data structure is designed as a data domain data And two pointer fields prior and next, Point to the forerunner and the successor respectively . For the insertion and deletion of bi-directional linked list, we only need to consider the operation of the preceding and subsequent two directions of the linked list . It is essentially the same as the one-way linked list operation .
4. Stacks and queues
Stack definition 、 Sequential storage of stacks 、 Two stacks of shared space 、 Chain storage of stacks 、 The application of the stack - recursive 、 The application of the stack - Four expressions are evaluated 、 Queue definition 、 Circular queue （ Sequential storage ）、 Queue chain storage structure and its implementation .
(1) Stack definition
Inserts and deletions are only allowed at one end .
1． The top and bottom of the stack
Insert and delete the top of the stack top、 The other end is the bottom of the stack
(2) Sequential storage of stacks
1． Sequential stacks Top attribute
top： The location of the top element of the stack , Empty stack top=-1,stackSize For the size of the stack .Top The maximum value of is stackSize-1
2． The operation of a sequential stack
Out of the stack pop【stack[top];top--】
3． Special sequential stacks -- Two stacks of shared space
- Use scenarios 【 The data element types of the two stacks are the same , There is a strict trade-off between data 】
- Nature and operation
The two ends of a linear queue are stack low ,top1、top2 Two stacks of top, The first stack logic is stack1[++top1]=e, The second stack logic is stack2[--top2]=e, The condition for the stack to be full is top1+1=top2.
(3) Chain storage of stacks
The data structure of the node is data field and pointer field .
1． Chain stack properties
The data structure of the stack is top and count.S For chain stacks .e Represents the new element node .
Top Pointer to the top of the stack 、
count Represents the number of elements in the stack .
2． Chain stack operation
Push 【e->next = S->top; S->top = e】
Out of the stack 【S->top->data; S->top = S.top.next】
(4) The application of the stack
1． Recursive function
java In the virtual machine, each stack frame in the stack represents a method , The call between methods uses a stack to represent the relationship between them
2． Four expression operations
java Each stack frame in the virtual machine has a stack of operands , The operation used to calculate four expressions . Change infix expression into suffix expression
3． Suffix operation rules
Traverse each number and symbol of each expression from left to right , When it comes to numbers, go to the stack 、 Encounter symbols , Just pop two data out of the stack , Calculate , Put the results on the stack . To the end
Definition 【 Insertion is only allowed at one end 、 A linear table that is deleted at the other end , features ：FIFO】
(6) Queue sequential storage （ Circular linked list ）
Sequential storage queue , It's usually a circular list , No need to move .
1． Circular queue data element data structure
data For a linear table ,
front： Team head element position
rear： The next position at the end of the team
2． Queue attribute judgment
Empty queue ：front=rear
Full of lines ：(rear+1)%MaxSize =front
3． Queue operation
- Out of the team
- Judge not empty team
- Get elements ：Q-> data[front];
- adjustment front Location ：Q->front = (Q-> front + 1 ) %MaxSize
- The team
- Judge that the team is not full
- New elements in the team ：Q->data [rear]= e
- adjustment rear Location ：Q->rear= (Q->rear+1)%MaxSize
(7) Queue chain storage
1． Team structure
Team head pointer and tail pointer . The chain team goes out of the stack to look for the leader's pointer , Join the team and find the tail pointer .
front Team head pointer
rear Pointer to a party
Q On behalf of the queue
2． Data element structure
Data fields data and Pointer to the domain next
3． Chain operation
- The team
You don't have to judge if it's empty . New node elements are concatenated in the queue . take The pointer field of the original tail node points to the new node . meanwhile Update queue's rear For new elements .
- The pointer field of the original tail node points to the new node Q->rear->next =s;
- Update queue's rear For new elements Q->rear = s;
- Out of the team
- Judge not empty team ：Q->front =!= Q->rear;
- Get team leader data Q-> front->data ;
- Adjust the team head pointer Q->front = Q->front->next;
The definition of a tree （ Node classification 、 The relationship between nodes 、 level 、 depth 、 Ordered trees 、 Disordered trees 、 The forest ）、 The storage structure of the tree （ Parenting 、 Child representation 、 Child brother notation ）、 Binary tree （ Definition 、 characteristic 、 Special binary tree （ Oblique tree 、 Full binary tree 、 Perfect binary tree ）、 The characteristics of binary trees ）、 Binary tree storage （ Sequential storage 、 Binary list ）、 Traversal of binary tree （ The former sequence traversal 、 Middle order traversal and post order traversal 、 Level traversal ）、 The establishment of binary tree 、 Clue binary tree （ Node data structure 、 Clue binary tree implementation 、 After traversing the binary tree ）、 Trees - The forest - Transformation of binary trees 、 Huffman tree （ Definition 、 Principles of coding and coding ）
(1) Strengthen your knowledge
Tree knowledge points are divided into Trees 、 Binary tree 、 Clue binary tree 、 Huffman tree
(1) Tree definition
n A finite set of nodes .N=0 Time is called empty tree . In any non-empty tree ,（1） Having and having only one specific node is called the root node .（2） When N>1 It's me , Except for the root node n-1 Nodes can be divided into multiple finite sets that are not mutually intersecting , And each finite set is also a tree . Recursion is used in the definition .
(2) Tree storage
1． Parenting （ Sequential storage ）
An array of said ： Node data element structure 【 Data fields data, Pointer to the domain parent】 Each node records the subscript of its own parent node , To express the relationship between tree node elements
2． Child representation （ Chain store ）
The data structure of the node is data With the kids Express . The better structure of children's set representation is linked list representation . Then the structure is 【data、first_child、second_child ...】 and The structure of multiple linked lists is similar to , among first_child Point to the head of the child's linked list , It's the first child's node
3． Child brother notation （ Chain store ）
The data structure of the node is 【data、first_child、right_sib】
The advantages of this representation ： It can turn any tree into a binary tree
(3) Binary tree definition
The tree is either an empty binary tree , It's either a root node and two other binary trees
The nonexistence degree is greater than 2 The node of 、 The left and right subtrees are ordered , You can't change it at will 、 And it's a subtree , We should also distinguish between left subtree and subtree
(4) Binary tree storage
- Sequential storage
Compared with the sequential storage of trees 、 Binary tree order storage has children left and right . The storage of the tree only specifies the parent node , There's no right or left child .
Number according to a complete binary tree , Store the data in a numbered array
- Binary list
The data structure of the node 【data、l_child、r_child】, Each data node stores data , Store the node location of the left and right subtrees
(5) Traversal of binary tree
among , Before the order 、 In the middle order and after order , They all use recursion . And before 、 in 、 The root node and left subtree 、 The access order of the right subtree .
- The former sequence traversal
For non empty binary trees , So let's go to the root 、 The preorder then traverses the left subtree , Finally, preorder traverses the right subtree
- In the sequence traversal
ditto ： The left subtree -> Root node -> Right subtree
- Subsequent traversal
ditto ： The left subtree -> Right subtree -> Root node
- Sequence traversal
Start at the root of the tree , Traverse from top to bottom . In the same layer, nodes are accessed one by one from left to right
The results of preorder and postorder traversal are known , We can't determine the structure of a binary tree .
(6) Clue binary tree
Corresponding to the case of cross linked list storage .
A pointer to a precursor or successor is called a clue , A binary linked list with a leading pointer and a subsequent pointer is called a clue list , The corresponding binary tree is called the clue binary tree
2． Clue binary tree of Node data structure
data【 Data fields 】
l_child【 Left child or precursor node 】
l_tag【0： On behalf of the left child 1 Represents the precursor 】
r_child【 Right child or successor 】
r_tag【0 For the right child 1 On behalf of successors 】
3． The clue process
Tips ： Keep the antecedent node of order traversal in the precursor .
Clues The core processes , Middle order ergodic binary tree ,
If p->lchild It's empty be l_tag assignment 1 meanwhile ,l_child assignment Precursor node pre.
If pre->child It's empty , be pre->r_tag The assignment is 1, pre->r_child The assignment is The current node p,
The subtleties , according to p And the precursor pre, At the same time, judge p Whether the left subtree of is empty and pre Whether the right subtree of is empty
4． Traversal of the threaded binary tree
(7) Huffman tree
The length of the path 【 A branch from one node of a tree to another constitutes a path between two nodes . The number of branches on a path is called The length of the path , The length of a leaf node is the number of branches from the root node to the leaf node , The degree of weighted leaf node is the product of leaf node length and weight 】 The length of the tree path is the sum of the number of nodes from the root to each leaf .
The path between the two points ： The branches from one node of a cluster tree to another form a path between two nodes .
The length of the path ： The number of branches on a path is called the length of the path .
The length of the tree ： It is the sum of the paths from the root node to each node .
Weighted path length WPL Calculation method ： The weight of each leaf node * The path of the leaf node The sum of the .
1． Huffman tree
Weighted path length WPL The smallest binary tree is called the Huffman tree .
2． Algorithm of Huffman tree
Two subtrees of the minimum weight A、B Merge into a binary tree C,C The weight of is weight A+ power B, take C Put in the set red , Delete A、B, repeat , Until there's only one tree left in all the collections , The Huffman tree
3． Huffman code
Huffman tree from root node to leaf node , The left child in the branch represents 0, The right child represents 1, such , The Huffman coding of each leaf node is the corresponding character from the root node to the leaf node
chart （ Definition 、 The vertices 、 edge 、 Ordered pair 、 Disordered couple 、 arc 、 degree 、 The degree of 、 The degree of 、 Simple picture 、 Undirected complete graph 、 Directed complete graph 、 Sparse graph 、 A dense picture 、 power 、 network 、 Subgraphs 、 Adjacency point 、 Attachment 、 route 、 The length of the path 、 loop （ Ring ）、 Simple path 、 Simple circuit 、 connected 、 Connected subgraphs 、 Connected component 、 Strong connected components ）、 The storage structure of the graph （ Adjacency matrix 、 Adjacency list 、 Cross linked list 、 Adjacent multiple linked lists 、 Edge set array ）、 Graph traversal （ Depth-first traversal 、 Breadth first traversal ）、 Minimum spanning tree （ Definition 、 Prim algorithm 、 Kruskal algorithm ）、 Shortest path （ Definition ）、 A topological sort （ Algorithm ）、 critical path （ Algorithm 、 principle 、 Realization ）
(1) Strengthen your knowledge
(1) Figure defined
【 from A finite nonempty set of vertices and The set of edges between vertices form 】、 The length of the path 【 The number of edges or arcs on the path 】、 Ring 【 The first vertex is the same as the last vertex -- Ring 】、 Simple path 【 A path that does not appear in a simple way is called a repeated path 】、 connected 【 If there is a path between two points , Then two points are connected 】、 Connected graph 【 If any two points are connected , It is called a connected graph 】
(2) Figure of the storage
1． Adjacency matrix
Vertices are stored in one-dimensional arrays 、 Edges or arcs are stored in two-dimensional arrays . This kind of storage is called Adjacency matrix , Two dimensional arrays are very similar to matrices in discrete mathematics .
Matrix representation ： Suppose the vertex is in a one-dimensional array A The subscript of is i, The vertices B The subscript of is j. And in a two-dimensional array i Line represents from A For the starting edge / arc .Arr[i][j] == 0 Express AB There is no edge between .Arr[i][j] == 1 Express AB There's an edge between . The matrix of an undirected graph is a symmetric matrix .
Use scenarios ： It is suitable for statistics of graphs , However, it is not suitable for deleting and modifying the elements of the diagram .
2． Adjacency list
Vertices are represented by a one-dimensional array , Edges are represented by linked lists . The linked list is saved ： The current vertex is the starting point, and the end points of all edges correspond to the subscript of vertex in one-dimensional array .
Vertex data structure 【 Data fields data, Pointer to the domain ：first_edge The edge that goes out of the current vertex 】
The data structure of the node in the side chain list 【 The position of the node at the end of the edge ：adjvex、next】. It is equivalent to a one-dimensional array representing the vertices of a graph , The linked list can represent the point where the degree is at the current node , It can also represent the edge of the current vertex . The disadvantage is that we can't give consideration to the expression of in degree and out degree .
Adjacency list can only represent graph according to out degree or in degree . You can't take both .
3． Cross linked list （ Directed graph ）
Adjacency table is an optimized storage for directed graph . The purpose of cross linked list is to find the degree of vertex in graph （ Out and in ） And it comes up with . It is a kind of chain storage structure which combines adjacency list and inverse adjacency list .
Each vertex corresponds to two linked lists , One is a list of arcs starting from that vertex 、 The other is a list of arcs ending at the vertex .
- Vertex data structure of digraph
Data fields data, Vertex specific data information
first_in： Points to the first arc node with the vertex as the arc head .
first_out： Point to the first arc node with the vertex as the tail of the arc .
- The data structure of the node of the linked list
tailvex Indicates that the tail vertex of the arc is in the vertex array xList Position in
headvex Represents the position of the arc head vertex in the vertex array
headlink Indicates the next arc pointing to the same arc head
taillink Indicates the next arc with the same tail
- Use scenarios
It is convenient to count the in and out degrees of vertices . Optimized storage of digraphs . understand ： One edge corresponds to two vertices , They will be counted at the starting vertex in turn , It will also be counted once at the end point . The disadvantage is to delete an edge , Two things need to be changed
4． Adjacency multiple tables （ Undirected graph ）
- Design objectives
For undirected graph design
For undirected graphs , Use adjacency table to store , If you delete an edge, you need to modify the representation of the two vertices of the edge in the linked list . It is equivalent to two changes . Adjacency multiple table modifies adjacency list by imitating cross linked list . In the case of changes , You can modify one place .
One dimensional arrays represent vertices , A linked list represents an edge （ The table of true meaning -- Two vertices ）
- Storage ideas
One dimensional array holds vertices , A linked list represents an edge / arc .
- data structure
- Vertex data structure
Data： Vertex specific data information
- Linked list data structure
A node really means an edge .
ivex 、Jvex： The position of two vertices of an edge in a one-dimensional array of vertices .
Ilink： Attached to the apex ivex The next side of .
Jlink： Attached to the apex Jvex The next side of .
5． Edge set array
It consists of two one-dimensional arrays . Vertices have a one bit array . Just save the vertex itself .
The other one bit data represents the edge .
- The data structure of the edge is
Begin： The position of the start of the edge in the vertex array
End： The position of the end of the edge in the vertex array
Weight： The weight of the edge
(3) Graph traversal
Starting from a vertex of a graph , Traverse the rest of the vertices in the graph , Each vertex is accessed only once . This process is called graph traversal .
1． Depth-first traversal
Deep First Search Also known as depth first search , abbreviation DFS
Original definition ： It comes from a vertex of the graph V set out , Access this vertex , And then from V The next point that has not been visited starts , Depth first traversal graph . All the way to the sum V All vertices with paths in common are accessed . If there is still a vertex not visited , Select another vertex that is not visited as the starting point , Repeat the process . Until all the vertices in the graph are accessed .
Here is a simplified definition , The recursive call is implemented exactly according to the following definition .
（1） Visit vertex v;
（2） from v Select a vertex from the inaccessible adjacency points of w, from w Set out for depth first traversal ;
（3） Repeat the above two steps , All the way to the sum v All vertices with paths in common are accessed .
Personal understanding ： The access number is i The vertex of the is called recursively ( It is equivalent to the preorder traversal of a tree ==》 The root node - The left subtree - Right subtree ) The node next to him , In order to achieve the effect of depth first call .
There are recursive implementations and non recursive implementations , Non recursive can use the stack to assist in depth first traversal .
- Recursive implementation
（1） Visit vertex v;visited[v]=1;// Before the algorithm is executed visited[n]=0
（2）w= The vertices v The first adjacent point of ;
（3）while（w There is ）
if（w Not visited ）
From the top w The algorithm is executed recursively ;
w= The vertices v Next adjacent point of ;
- Non recursive implementation
（1） Stack S initialization ;visited[n]=0;
（2） Visit vertex v;visited[v]=1; The vertices v Push S
（3）while( Stack S Non empty )
x= Stack S The top element of ( Don't stack );
if( Exist and find that which has not been accessed x The adjacency point w)
w Into the stack ;
x Out of the stack ;
2． Breadth first traversal
Breadth First Search abbreviation BFS
（1） From some vertex in the graph v set out , visit v.
（2） Sequential access v Which has not been accessed .
（3） Start from these adjacent points and visit their adjacency points in turn , And make “ The adjacent point of the vertex accessed first ” Precede “ The adjacent point of the vertex to be accessed later ” To be accessed . Repeat step 3, Until the adjacent points of all the vertices in the graph that have been accessed are accessed .
From the definition of breadth first traversal , The first is hierarchical traversal , Reflect the breadth of . also , such as V The adjacency point A And the adjacency point B.A Precede B To be accessed , be A The lower adjacency of also takes precedence over B The lower adjacency point of is accessed . Because of this relationship , You can use the FIFO feature of queues , To assist in breadth first .
Pseudo code for breadth first code
（1） The vertices v Queue entry .
（2） When the queue is not empty, the execution continues , Otherwise the algorithm ends .
（3） Get out of the queue and get the top of the queue v; Visit vertex v And mark the vertices v Has been interviewed .
（4） Find vertices v The first adjacent vertex of col.
（5） if v The adjacency vertex of col Not visited , be col Queue entry .
（6） Continue searching for vertices v Another new adjacency vertex of col, Go to step （5）.
To the top v All the previously visited adjacency points are processed . Go to step （2）.
(4) Minimum spanning tree
For graphs with weights , Net structure . Choose to connect all vertices from it , And the sum of the weights of the edges is the smallest . This is the minimum spanning tree .
A more common application .N Villages need to be connected by internet cable , How to make the network cable shortest . This is a practical example of finding the minimum spanning tree .
1． The prim algorithm
hypothesis N=｛V,｛E｝｝ It's a connected network ,TE yes N The set of edges in the minimal spanning tree on . Algorithm from U=｛U0｝（U0 yes V The elements of ）,TE=｛｝ Start . Repeat the following ： Satisfy a vertex on all edges U in , The other vertex is at V-U In the middle , Select an edge with the smallest weight . As TE The elements of . meanwhile ,TE Put all the vertices in U in . Then continue with the above operation , until U=V. be T Namely N The minimum spanning tree of .
Make sure that one vertex of each edge is at U One of the top points in V-U And the weight is the smallest . Put the extracted edge in TE in . until V=U Location . Then the minimum spanning tree is obtained .
2． Kruskal algorithm
(5) Shortest path
Between two vertices , The path with the smallest sum of weights passed . The first vertex on the path is the source point , The last vertex is the end .
1． Dijkstra algorithm
An algorithm that produces the shortest path in the order of increasing path length . First, find the shortest path with the shortest length , Then we can find the shortest path with the shortest length , By analogy , Until from the apex v Until all the shortest paths of other vertices are found .
Description of solution steps ：
1. Set auxiliary array dist. Every component of it dist[i] Represents the currently found source point v0 To the end point vi The length of the shortest path ;
2. The initial state ：
2.1. If from the source v0 To the top vi Have edge ：dist[i] Is the weight on the edge ;
2.2. If from the source v0 To the top vi boundless ：dist[i] by ∞.
2． Freudian algorithm
(6) A topological sort
Topological sorting is actually the process of constructing topological sequence . And topological sequence , Generally speaking , It's a sort of ordering of vertices .
Topological sequence is a kind of order in which tasks are successfully completed .
- AOV network ： Use vertices to represent activities （ Work that takes a while to complete ）, Use the arc to represent the order . The event at the beginning of the arc needs to occur before the event at the end of the arc . therefore ,AOV The process of net sorting is a process that strictly follows the sequence of events .
- Topological sorting algorithm ： from AOV Select an entry in the network as 0 Node output of . Then delete the arc whose vertex is tail . Then repeat the above operation , Until all the vertices are output or do not exist 0 The vertex position of .（ It's very simple to understand ）
Graph based storage has the difference of adjacency table or adjacency matrix , In terms of concrete implementation, there are some difference .
If it's an adjacency list , Stack can be used in the implementation process . The purpose is ： Avoid traversing the vertex every time to find whether there is a degree of 0 The summit of . The application of stack in this algorithm needs to be further understood .
(7) critical path
The critical path is to solve the problem of the shortest time to complete the task in the project .
The vertex represents the event ( A moment , A landmark event happened , It's a description of a point in time ), Arc table activity （ Work over a period of time ）, The weight on the arc represents the time required for the activity .
2． Key activities
The sum of the duration of the activity on the path is called the path length . The path with the maximum length from the source point to the sink point is called the critical path . Activities on the critical path are called critical activities .
3． Critical path algorithm
Find definition （ lookup 、 Lookup table 、 keyword 、 Key words 、 Secondary key words ）、 Static lookup table （ features ）、 Dynamic lookup table （ features ）、 Sequence table lookup 、 Search in order （ Half （ Two points ） lookup 、 The interpolation to find 、 Fibonacci （qi） lookup ）、 Index lookup （ Dense index 、 Block index 、 Flashback index ）、 Binary sort tree （ Definition 、 Search operation 、 The insert 、 Delete operation ）、 Balanced binary trees AVL（ Definition 、 Realization principle 、 Code implementation 、）、 Multiple search trees （B Trees ）（2-3 Trees 、2-3-4 Trees 、B Trees 、B+ Trees ）、 hash （ Definition 、 Construction method 、 Conflict resolution 、 lookup ）
According to a given value , Identify a data element or record in a lookup table that has a key value equal to a given value .
2) Static search
1． Query whether a particular element is in a lookup table
2． Retrieve the attributes of a particular data element
3) Dynamic search
1． Insert data when searching
2． Delete data when searching
(2) In order to find
1) Order search definition
Also known as Linear search . Start with the first or last one , Compare the keywords and the given values one by one . If the match is successful , Then the search is successful . If it doesn't match until the last element , The search is unsuccessful . Personal understanding , By traversing , Match them one by one , Until the last element
2) Optimization of sequential search
Traversal of a linear table , If it's thread storage , We need to traverse the subscript , Determine if the subscript is out of bounds , Then get the elements and compare them . The process of matching and comparison cannot be less , But cross boundary judgment can be optimized . You can use a given element as a sentry . Cycle to sentinel position . If you jump out of the way , Indicates that the match was successful , If you don't jump out until the sentinel position , Description matching failed .
(3) Search in order
1) Binary search
Also called binary search . The premise is that linear tables are stored sequentially . And the key of the element is in order .
In an ordered list , Take the element in the middle as the comparison object . If the given value is equal to the middle record key . Then the search is successful . If the keyword of the intermediate record is larger than the size of the given value . Continue with the left half . If the keyword of the intermediate record is less than the size of the given value . Then continue the binary search in half . Keep repeating the process . Until successful or query all regions , To find the failure .
A binary search is a recursive call . Every time I look for the location is low and high Of 1/2. namely mid = (1/2) *(low+high)= low+(1/2)*(high-low)
2) The interpolation to find
The difference between interpolation search and binary search is only the ratio , No 1/2. It is (Key-a[low])/ (a[high]-a[low]).
namely mid = low = low + ((key-a[low])/(a[high]-a[low])) *(high-low)
3) Fibonacci looks for
(4) Linear index search
Indexing is the process of associating keywords with their records .
Indexes are divided into linear indexes 、 Tree index and multi-level index . So-called Linear index It is to organize the index item set into a linear structure . A linear index contains Dense index 、 Block index and Inverted index .
1) Dense index
In a linear index , Each record corresponds to an index entry .
For dense indexes , The index entries are ordered by key .
2) Block index
Divide the data set into blocks , And these blocks satisfy two conditions .
1． Features of partitioned data sets
Disorder within the block , The blocks are in order .
2． Index item data structure
Maximum key ： Store the largest key in each block .
Block length ： The number of records in the storage block . In order to use in circulation .
Block head pointer ： Pointer to the first element of the block . In order to start traversing this record .
3． Block index table lookup
- Find the block where the key is in the block index table .【 Find by half 】
- Find the corresponding block according to the first block pointer . Determine the range of the order table according to the block length ( size ). Then look up the key in the sequence table .【 Because the blocks are stored in order and out of order 】
3) Inverted index
(5) Binary sort tree
If the ordered data needs to be searched dynamically . That is, in the process of searching, it is necessary to insert or delete the data elements that are not found , Sequential storage of arrays is not a good solution to the need for . You need to use a data structure called a binary sort tree .
Binary tree search and sequential search have similar parts .
(1) Design purpose
Binary sort tree is mainly used to solve Ordered dynamic search . Storage is in the form of a binary tree .
(2) Binary sort tree operation
Dynamic search , The basic operation is to build 、 lookup 、 Insert 、 Delete
Key and binary tree root node value range comparison , If equal, the query is successful . If the keyword is less than the value of the root node , Find the left child of the root node recursively . If the keyword is greater than the value of the root node . Find the left child of the root node recursively . The lookup function returns the parent node . For insertion or deletion .
Basic algorithm ： Based on the search function , If returned to false, It means that no node has been found . New node created s, The node value field is assigned as the key word key. And find the location of the parent node P Comparison of node values of . If key< Parents data, Then the new node s do P The left subtree . If key> Parents node p Of data, Then the new node s do P The right subtree .
If the lookup function returns false, Then the parent node must be a leaf node .
The implementation is divided into two layers ：
first floor ： Judge key Whether the value is equal to the root node of the tree . If they are equal Delete the current node and adjust the left and right subtrees , And rejoin the left and right subtrees . If key< The value of the root node , Then the binary tree deletion method is called recursively , Delete left subtree . If key> The value of the root node , Then the binary tree deletion method is called recursively , Delete the right subtree .
The second floor ： Delete root , And the method of reconnecting left and right subtrees Realization .
There are three possibilities for deleting a node .
（1） leaf node 【 Delete directly 】
（2） There are only left or right nodes 【 If there are only left trees , After deletion, the left subtree is added to the deleted position , If only the right subtree , Add the right subtree to the deleted node 】
（3） Both the left and right subtrees have nodes
Find the whole tree Traversal of the precursor node s Replace the deleted node p The data of . And then according to s Small scale adjustment for subtree condition of 【s There are only two forms ： One is the leaf node 、 The other is that there are only left subtrees 】.
- s It's just leaf nodes
There is no adjustment .
- hypothesis s And Zuozi tree s->lchild, And s The original parent node is q If p!=q
Will s The left branch of the tree receives q The right child .
- hypothesis s And Zuozi tree s->lchild, And s The original parent node is q If p==q
be s The left branch of the tree receives q The left child ,q->lchild=s->lchild.
The deletion is a little more complicated . Replace the deleted node with the direct precursor node . Then adjust the predecessor's left sub tree , Re access to the binary tree .
(6) Balanced binary trees
1) Basic concepts
Balanced binary trees ： Defined as recursion , Every subtree with a root node is a balanced binary tree . The depth of the left and right subtrees is no more than 1.
Minimum unbalanced subtree ： Closest to the insertion point , And the absolute value of equilibrium factor is greater than 1 The node of is the subtree of the root node , We become the smallest unbalanced subtree .（ For the imbalance caused by inserting new nodes into the original balanced binary tree ）
The goal of balanced binary tree is to keep the element nodes unchanged . Keep the depth as low as possible . So in the case of an ordered search , Operate as little as possible .
2) AVL Tree implementation principle
The basic idea of building a balanced binary tree is ： In the build process , Whenever a node is inserted , Check if the balance of the tree is broken , if , Then find out the minimum unbalanced tree , Adjust accordingly .
3) Balanced binary tree node data structure
1． Data fields （ data ）
2． Left subtree pointer
3． Right subtree pointer
4． Data item of balance factor bf（ More nodes than a binary tree ）.
4) Balanced binary tree implementation algorithm
The essence is ： Adjust the operation of the minimum unbalanced tree
1． Basic operation - left-handed 、 Right hand
- Right hand
As shown in the figure below, the minimum unbalanced binary tree on the left , You can turn it into a balanced binary tree on the right .
Need to be right , The depth of the left subtree is high , The original left tree L It needs to be used as a follower . therefore ,P Need to be L The right subtree .L The right subtree of is p The forerunner of node's middle order traversal . therefore ,L The right subtree of is called P The left subtree . After the P As L The right subtree .
Divide the whole tree into three parts .（1） The original root node has a right subtree 【P and PR】（2） The right subtree of the left subtree LR （3） Remove the right part of the subtree 【L- LR】
Steps are as follows ：
（1） The left subtree L The right subtree LR As P The left subtree ;
（2） And then P As L The right subtree
As mentioned above , Figure and code of left rotation operation , As shown below
Left rotation means that the depth on the right side is high . Divide the original tree into three parts ,（1） The root node P With the left tree L（P - R）, be called p （2） Right subtree R The left subtree RL, Become q （3） Right subtree R Remove its left subtree RL part （R - RL）, be called w
The specific left shift operation is as follows
（1） take q As P Right subtree , Become r
（2） take r As w The left subtree
2． Left / Right balance rotation
- Left balance rotation
Left balanced rotation indicates that new nodes are added to the left subtree . Minimum unbalanced subtree T Of BF It must be 2. The whole has to turn right . according to
- If T The left child's BF and T Of BF The symbols are the same , Then the minimum unbalanced subtree T You need to turn right .
- If T The left child's BF and T Of BF The symbols are different , It shows that the new node is in T On the right tree of the left child . That means double spin is needed .（1）T The left hand of the child （2） To the whole T To carry on the right hand .
- Right balance rotation
It is necessary to rotate the right subtree of the minimum unbalanced subtree . The new node is added to the right subtree .
Right balanced rotation indicates that new nodes are added to the right subtree . Minimum unbalanced subtree T Of BF It must be -2. The whole thing has to turn left .
- If T Of the right child BF and T Of BF The symbols are the same , It shows that the new node is in T On the right tree of the right child , Then the minimum unbalanced subtree T Just turn left .
- If T Of the right child BF and T Of BF The symbols are different , It shows that the new node is in T On the left tree of the right child . That means double spin is needed .（1） Yes T The right hand of the child ,（2） To the whole T To carry on the left-hand .
(7) Multiple search trees (B Trees )
B Tree is a balanced multi-path search tree . The maximum number of children in a node is called B The steps of the tree .
1) B The design goal of the tree
2) m rank B The properties of trees
1． If the root node is not a leaf node , There are at least two subtrees .
2． Every non root branching node has k-1 Elements and K A child ; Its [m/2] <=K <=m. Every leaf node n There are k-1 Elements .
3． All leaf nodes are at the same level .
4． The data structure of all branch nodes is .K A child pointer and k-1 A cross arrangement of elements .
stay B The process of searching in the tree is a process of finding nodes by pointer and searching keywords in nodes .
3) 2-3 Trees
- 2-3 Tree definition
2-3 The tree is of order 3 Of B Trees . It's a multiway tree . Every node has 2 A child （ be called 2 node ） Or three kids （ be called 3 node ）. among 2 The node contains an element and two children or no children .3 The node contains two elements and three children or no children . All the leaves of the tree are at the same level .
- 2-3 Tree insertion
The insertion is divided into 3 Medium condition
（1） For empty trees , Insert a 2 The node can be .
（2） Insert a node into a 2 On the leaf node of a node , It's an element in itself , take 2 The node is raised to 3 The node can be .
（3） forget 3 Node inserts an element . because 3 The node is originally 2-3 The maximum capacity of the tree The node of ( There are already two elements ). So it needs to be split , Put two in the tree Choose one of the three elements or inserted elements （ The middle value of the three elements ） Move up one level , The other two elements are called two 2 node .
The nature of splitting ： If the position to be inserted is three nodes, then decompose it , Throw up （3 The middle value of elements ）, If it's also three nodes , Dismantling is still needed , Throw up ,… Wait until you drop it to the head node , If the head node is also three nodes, then , This tree is not high enough to hold this structure , We need to decompose the head node termination operation to increase the height of the tree . Because there are no nodes up there that can perform operations .
Suppose the data we record is 1,2,3,4,5,6,7,8,9 No loss of generality , From 1 Start inserting the emulator in sequence .
- 2-3 Tree delete
（1） Delete non leaf nodes
Using the middle order traversal under the direct successor node key To cover the current node key, After deleting the successor node used to overlay key.
（2） Delete leaf node
- Delete 3 The leaf node of a node
Delete directly , take 3 The node turns into 2 The leaf node of a node
- Delete 2 The leaf node of a node
4) 2-3-4 Trees
5) B Trees
6) B+ Trees
(8) Hash lookup
Hash is both a storage method , It's another way to look up .
1． Hash technology
stay Storage location of records and Its key words Establish a definite relationship between f, Make each keyword key Corresponding to a storage location f(key).f Called hash function , Also known as hash function .
Use hashing to store records in a linked storage space , This contiguous storage space is called a hash table or hash table .
2) Hash construction method
1． direct addressing
F(key) = a * key +b
2． Square with the middle method
Take the middle three
3． Division and remainder
f(key) =key mod p (p<=m)
4． Random number method
3) How to handle hash conflicts
1． Chain address
identical f(key) The values of are placed in the same linked list .F（key） To store the header of the linked list . If conflict , You need to match... In the linked list , Until the last node . Match elements .
2． Public spill area law
For the overflow part , Put into overflow table without sorting （ An array of sequential storage ） in . Find conflict , You need to traverse the overflow table as a whole , In order to find .
Sort （ Definition 、 Stable / Unstable sequencing 、 Internal order / External sorting ）、 Bubble sort （3 Kind of ）、 Simple exchange sort 、 Direct insert sort 、 Shell Sort 、 Heap sort 、 Merge sort and Quick sort .
1． Stable / Unstable sequencing
Pre sort sequence , If two elements a、b equal , And a stay b front , After sorting algorithm ,a、b There is no change in the relative position of , The sorting algorithm is called a stable sort . conversely , It's called unstable sequencing .
2． Inside row / Efflux
In the process of sorting , All the records to be sorted are in memory . It's called internal discharge .
3． Sort performance
Judging sorting performance is compared from the following aspects
- Time performance
- Auxiliary space
- Algorithm complexity
4． Sort and sort
The inner row is divided into 4 class
- Exchange sort
- Bubble sort
- Quick sort
- Selection sort
- Simple choice
- Heap sort
- Insertion sort
- Direct insert sort
- Shell Sort
- Merge sort
- Merge sort
There are two categories of complexity
- Simple algorithm
- Bubble sort
- Simple selection sort
- Direct insert sort
- Complex algorithms
- Bubble sort
- Heap sort
- Shell Sort
- Merge sort
(2) Bubble sort
1． Bubble sort （ Pseudo bubble ）
Two layers of circulation , The first layer identifies the smallest remaining element at a time , And then in exchange , Put the smallest element in the first position of the remaining position .
Because the standard of bubble sort is defined as adjacent pairwise comparison . The algorithm compares all the remaining elements with the sentry's position , And then put the smallest data in the first place . It's similar to sorting by choice . therefore , It's called pseudo bubble .
2． Standard bubble
Two layers of circulation , The first level of sorting controls each round to find the smallest element of the current round . The second control moves from the tail of the linear table to the head , Comparing the two , If the reverse order , Swap places .
3． Bubble optimization
Bubble sort species , If it is found that the linear table has been ordered in the process , You can break the sort . therefore , The essence of optimization is to discover , Interrupt invalid comparison .
(3) Simple exchange sort
Simple exchange sort , It's a sort of bubble optimization . Its core idea is multiple comparisons , The location of the exchange needs to be recorded , A swap .
(4) Direct insert sort
Divide the sequence to be sorted into two sequences , They are ordered sets and disordered sequences . Traversing the first element in an unordered set a[i], Put it in the sentry position a,（1） If a[i] Greater than the last element of an ordered sequence , be a[i] Position the same ,a[i] As the last element of an ordered sequence .（2） If a[i]< The last element of an ordered sequence . be a[i] From the tail of the ordered sequence to the head , Find a place j, Satisfy a[j]<=a[i]<=a[j+1], Will j To i Between the elements move back one bit . take a Data assigned to a[j]. Cycle the above operations , Until the unordered sequence is empty .
(5) Shell Sort
Hill sort is an improvement of direct insertion sort , It's also called narrowing incremental sort .
1． design idea
Hill sort is an optimization of direct insertion , And the direct order is The basic order and The number of records is small Under the circumstances , Efficient .
therefore , Make the sequence The basic order , Fewer , also Compare once , Take a big step . That's the starting point of Hill's sort .
First, the whole sequence of records to be sorted is divided into Several subsequences , separately Direct insert sort , To be recorded throughout the sequence “ The basic order ” when , Do a direct insertion sort for all records again .
notes ： Dividing a sequence of records into subsequences , This will ：（1） The number of elements in each sequence decreases （2） To divide into subsequences , So you can move a big step forward when you do the swap （3） Insert directly after sorting each time , The whole sequence becomes more ordered 【 The first element is the minimum in the first sequence , The second element is the minimum in the second sequence . By analogy , The basic order 】.
The characteristics of Hill sort algorithm ：
1） Reduce the increment
2） Multiple insert sort
2． Realization principle
Yes n A sequence to be sorted , Take one less than n The integer of gap( step ), The queue to be sorted is divided into several subsequences . All distances are gap Multiple of records in the same group . Then the elements of each group are sorted by direct insertion . Come down here , Every element is an ordered group . Then decrease the step size , Repeat the above grouping and sorting . Until the step size is 1. The real sequence is in order .
3 Methods ：
1. Take prime numbers , Every time you let gap- -, until gap =1;
2.gap = The number of elements to be sorted , Every time you let gap /2;
3.gap= The number of elements to be sorted , Every time you let gap /3 +1;
After being tested one by one by the great gods , The third method is more efficient .