Random storage, but insertion and deletion require moving a lot of data

static linked list

circular linked list

Doubly linked list

Single list

Memory distribution can be discontinuous Easy to insert and delete The search needs to start from one end

First in, last out, the input and output of elements are performed at the same end

First in, first out, input at the end of the queue, output at the head of the queue

Sequential storage and chained storage

BF algorithm

KMP algorithm

row precedence

Column first

Triad

Suppose there are two graphs. The vertices and edges of one graph are a subset of the vertices and edges of the other graph. This graph is said to be a subgraph of the other graph.

An undirected graph has n(n-1)/2 edges, and a directed graph has n(n-1) arcs.

Very few edges or arcs

There are many edges or arcs

Meaningful values ​​on the sides. Personal understanding can be compared to the right of Huffman tree

Two points connected by an edge are adjacent points to each other. The edge is attached to the vertex and the edge is associated with the vertex.

For directed graphs, the point is the in-degree and the point is the out-degree.

A path with the same start and end points

A matrix representing the adjacency relationship between vertices

A linked storage structure of a graph, establishing a single linked list for each vertex in the graph, and placing adjacent vertices in the linked list

It is another chain storage structure of directed graph

It is another chain storage structure of undirected graph

Access from a vertex Find the first unvisited adjacent point of the just visited vertex and repeat the execution Returns the previously visited vertex that still has unvisited adjacent vertices and finds the next unvisited adjacent vertex.

Access from a vertex Visit each unvisited adjacent vertex of this vertex in sequence Starting from these adjacent points respectively, visit their adjacent points in sequence

Prim's algorithm

Kruskal's algorithm

Dijkstra's algorithm

Freud's algorithm

In a directed graph, visit a vertex without a predecessor and output Delete this vertex. Repeat the above operations

The longest weighted path from a point with indegree 0 (source point) to the sink point

an independent unit in the tree

The number of subtrees a node has is called the degree of the node

Nodes with degree 0 are called leaves or terminal nodes

The maximum level of nodes in the tree is called the depth or height of the tree

The degree of a tree is the maximum value of the degree of each node in the tree

A binary tree of depth k and containing 2∧k-1 nodes

Features

Binary tree with depth k and n nodes A complete binary tree is called a complete binary tree if and only if each node corresponds to a node numbered from 1 to n in a full binary tree of depth k.

Features

The binary linked list composed of this node structure is used as the storage structure of the binary tree and is called a clue linked list. The pointers pointing to the predecessor and successor of the node are called clues. The binary tree with clues added is called a clue binary tree.

preorder traversal

inorder traversal

Postorder traversal

The so-called first, middle and last refer to the timing of accessing the root node. For traversing a binary tree, the left and right subtrees and root nodes must be accessed in a certain order. Different access orders are different traversal methods.

path

path length

tree path length

right

The structure of Huffman tree

Huffman coding

Calculation of WPL value

A collection of data elements of the same type

The value of a data item in a data element

Based on a given value, determine a record or data element in the lookup table whose key is equal to the given value

Starting from one end of the table, compare them sequentially

Start the comparison from the middle of the table. If it is greater, perform a halved comparison on the half that is greater. If it is smaller, perform a halved comparison on the half that is smaller than the table until the search is successful or there is no result.

Create an index table and perform sequential searches in the blocks according to the blocks pointed to by the index table.

If the left subtree is not empty, it must be smaller than its root node.

If the right subtree is not empty, it must be greater than its root node.

The left and right subtrees are both binary sorted trees.

On the basis of the binary sorting tree, there is an additional restriction, that is, the absolute value of the depth difference between the left and right subtrees does not exceed 1.

Is the operation of reordering a set of records in non-decreasing or non-increasing order of keywords

When the sorting keys are different, the result obtained by sorting the unordered sequence of any record is unique, otherwise it is not unique.

Internal sorting

external sort

When inserting the i-th (i >= 1), the previous V[0], V[1],..., V[i-1] have been sorted. At this time, use the sorting code of V[I] to compare the order of the sorting codes of V[i-1], V[i-2],..., find the insertion position and insert V[i], and the element at the original position will be inserted into Move backward

Use low, mid, and high to divide it into two regions [low, mid-1] and [mid 1, high] If the key value is less than the middle value mid of the sequence, it means that the key value should be inserted into the left area [low, mid-1], and then divide the area repeatedly for [low, mid-1] until low>high, and the final insertion The position should be high 1. Move the data at the position after high back as a whole, and then assign the key to [mid 1]

It is essentially a group insertion method that sorts by continuously shortening the cloth length.

Find small elements or large elements one by one by comparing and exchanging positions of adjacent elements.

It is an improvement on bubble sorting. Select the dividing value to divide it into two parts. The left side is less than the right side and the right side is greater. Repeat the execution.

First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.

Compare the n elements to be sorted in pairs, take out the smaller ones, and then compare the n/2 smaller ones in pairs, take out the smaller ones, and repeat the above steps until the ones are taken out. Minimal element.

Construct the sequence to be sorted into a big top heap. According to the properties of the big top heap, the root node of the current heap is the largest element in the sequence. Swap the top element of the heap with the last element, and then reconstruct the remaining nodes into a big top heap, and so on. Starting from the first time we build the big top heap, we can get the maximum value of a sequence every time we build it. , and then put it at the end of the big top pile. Finally, an ordered sequence is obtained.

highest priority method

lowest priority method