character

sound

image

.......

Storage method

Relationship description method

collection of operations

Data logical structure

Data physical structure

Ability to program computers to achieve

The same input corresponds to the same output

Can be completed within a limited number of steps

Number of basic operations

space complexity

full binary tree

perfect binary tree

small root pile

dagendui

Main operations of the heap

For a small root heap, the top element of the heap must be the smallest element. If you first create a small root heap from the sequence to be sorted, Then remove the elements from the heap in turn, and the new sequence obtained must be ordered from small to large. This solution requires opening up two memory spaces, one to store the small root heap and the other to store the result sequence.

Concatenate the elements of the sequence into a large root heap. Replace the first element and the last element of the array, and reduce the number of array elements by 1. Resize the shrunken array into a large root heap. Repeat steps 2 and 3 until the data element in the array is 0.

Use a structure to store each node, and use two pointer fields to point to the two children respectively.

Algorithm 1: Access after dequeuing Create a queue and add the root node pointer to the queue. If the queue is not empty, delete a node pointer from the queue. Then access the node and store the left and right children of the node in the queue in sequence. Repeat step 2 until the queue is empty.

Algorithm 2: Access before queuing Create a queue, access the root node, and add the root node pointer to the queue. If the queue is not empty, delete a node pointer from the queue. If the node has a left child, access its left child node and add the left child node to the queue; if the node has a right child, access its right child node and add the right child node to the queue. Repeat step 2 until the queue is empty.

access root node Preorder traversal of left subtree Preorder traversal of right subtree

In-order traversal of left subtree access root node In-order traversal of right subtree

Postorder traversal of left subtree Postorder traversal of right subtree access root node

A tree is a collection of (≥0) nodes.

If =0, it is an empty tree.

If >0, there is a node called the root node (root). The remaining nodes are divided into multiple disjoint sub-sets.

These subsets are themselves trees, called subtrees of the root.

Enqueue the root node When the queue is not empty Dequeue and access the node Put the child nodes of this node into the queue in turn

Push the root node onto the stack When the queue is not empty Pop the stack and access the node Push the child nodes of this node onto the stack in turn

Each subtree of the node is visited in turn using post-root traversal. Visit the root node.

Definition of graph

Undirected graph

directed graph

The relationship between vertices and edges

right

Spend

path

connectivity

Strong connectivity and weak connectivity

adjacency matrix

adjacency list

breadth-first traversal

depth first traversal

Given a directed network and a vertex called a source, the shortest path from the source to each other vertex is called the single-source shortest path.

The most efficient shortest path algorithm so far

Can be solved for weighted undirected graphs or directed graphs

Restriction: There cannot be negative weight edges

For an undirected graph G, its spanning tree T is a connected subgraph of G, and T contains all vertices in G and has n-1 edges. (n is the number of vertices)

Select an edge with the smallest weight from the candidate edge set and add it to the selected subgraph

Update candidate edge set

Repeat step 2 until the selected subgraph contains all vertices of the original image

Vertices are used to represent activities, and directed edges are used to represent the sequence of activities. Such a directed graph is called activity on vertex network (AOV network activity on vertex network).

Arrange the vertices in the AOV network into a sequence such that for any two vertices vi and vj, if vi is the predecessor of vj, then vi must be in front of vj in the sequence. We call such a sequence a topological sequence

Create an integer array to record the in-degree of each vertex. Create a queue and put the vertices with indegree 0 into the queue.

If the queue is not empty, take a vertex from it as the vertex in the topological sequence.

Decrease the in-degree of the end point of the edge starting from this vertex by 1. If the in-degree is 0 after subtracting 1, then insert the point into the queue.

Repeat steps 2 and 3 until the queue is empty.

If the number of vertices in the resulting sequence is equal to the number of vertices in the graph, the algorithm is successful.

For a weighted directed graph, its edges represent an activity, the weight represents the duration of the activity, and the vertices represent events in which the incoming edge activities have been completed and the outgoing edge activities can start. This weighted directed graph is called edge activity network (AOE network)

The longest weighted path from the source to the sink is called the critical path

Activities on the critical path are called critical activities

Activities that are not on the critical path are called non-critical activities

For an event, its earliest occurrence time is the earliest start time of the activity starting from its vertex.

is the length of the longest weighted path from the source point to this vertex.

For an event, its latest occurrence time is the latest end time of all activities that end at its vertex.

It is the earliest occurrence time of the sink minus the length of the longest weighted path from the vertex to the sink.

For any activity (edge), the latest occurrence time of its end event minus the earliest occurrence time of its starting point is the longest time that this activity can last.

The maximum sustainable time of an activity minus the weight of the activity edge is the allowed delay of the activity.

The earliest and latest occurrence time of the source point event are the same, both are 0

The earliest and latest occurrence times of sink events are also the same, both are the length of the critical path

Find

lookup table

Keywords

Static search and dynamic search

Inner search and outer search

Search successful

Search failed

B-tree is a tree-like data structure that can self-adjust its balance state.

Supports fast search, traverse, insertion and deletion operations

B-trees are more suitable for large-scale data read and write operations in storage systems.

Commonly used in databases and file systems

Data object or data element: a record in a data table

Key code: attributes used to distinguish objects

Index item: The data object composed of the key code of an object and the address of the object in the data table is called an index item.

Index table: A data table composed of index items is called an index table

Collection std::set, std::unordered_set

Dictionary std::map, std::unordered_map