Algorithm Learning Notes (1)
There are two ideas, like jewelers' gems on velvet, one is calculus, the other is algorithms. Calculus and the mathematical analysis system established on the basis of calculus created modern science, while algorithms created the modern world. -- "the emergence of algorithms"
Basic data structure
1. Linear data structure
(1) Array: "string" (such as: data string, binary string)
(2) linked list: single linked list: data + address pointer of the next element
Double linked list: address pointer of the previous element + data + address pointer of the next element
Note: the difference between array and linked list: access mode is different, array is direct single access, linked list is linked access.
(3) Linear list:
Stack: "last in, first out" (LIFO)-> "stack of plates"
Insert and delete operations are at the end-> top of the stack
Queue: first-in, first-out (FIFO)-> customer queue
Delete-> team leader-> get out
Insert-> end of line-> join the team
Priority queue: (task)-> find or the largest element, insert a new element-> heap
2. Figure
Undirected graph
Directed graph
Difference: whether the vertex pair (u.j.v) is the same as the vertex pair (v..u)
Definition: figure G =
V is a finite set whose elements are vertices.
E is a finite set whose elements are a pair of vertices and edges.
Note: whether the circle is prohibited or not, 0 depends on whether there is a connected component.
Acyclic graphs: without loops
3. Tree (connected acyclic graph)
Forest (no loop but not necessarily connected, whose connected components are trees)
Rooted tree: (application) describes the hierarchical relationship
State space trees: backtracking and branch bounds
Distinguish / distinguish: ancestors, true ancestors, parents, children, brothers, leaf nodes, father nodes, descendants, child trees.
Depth of vertex
The height of the tree
4. Ordered tree
Binary tree, binary search tree, multipath search tree.
Note: the expression of children before brothers
5. Sets and dictionaries
The method of representing a set: bit vector, linear list structure
Abstract data types: a collection of abstract objects of data items and a series of operations on these objects
Set merging problem
