Pay attention to the final judgment of whether the two tables are empty or not.

time complexity:

time complexity:

time complexity:

Continuously swap the front and last elements of a linear list

Pay attention to the order of the code

Pay attention to the code order

Constantly doing head deletion, head insertion

The stack is a special linear list (first in, last out, last in, first out)

An empty stack cannot be taken out, and a full stack cannot be entered.

The stack is implemented with a linear table. The top pointer (actually a number) of the stack is -1, which means an empty stack, and top=MAX-1, which means a full stack.

When the stack is full, it becomes an overflow; when the stack is empty, it becomes an underflow.

The queue can only be deleted at the front of the queue (front) and can only be inserted at the rear of the queue (rear).

Initial front=rear=-1

False overflow of queue

Judgment of full and empty queues: front=rear

Queue chain storage structure

upper and lower triangular matrix

Symmetric matrix

tridiagonal matrix

triple table storage

chain storage

Using a queue, each time a node is visited, its left and right children are queued.

Regulation: If there is a left subtree, then lchild points to its left subtree, otherwise it points to its predecessor. If there is a right subtree, then rchild points to its right subtree, otherwise it points to its successor.

A binary sorting tree is either an empty tree or has the following properties. If its left subtree is not empty, then all node values ​​on the left subtree are less than the value of the root node. If its right subtree is not empty, then the right subtree The values ​​of all nodes in the subtree are greater than the value of the root node. The left and right subtrees are both sorted binary trees.

Find

structure

delete

Find performance analysis

A balanced binary tree is first of all a sorted binary tree. Its left and right subtrees are both balanced binary trees, and the difference in depth between the left and right subtrees does not exceed 1.

Balanced binary trees are constructed using balanced rotation techniques

The tree with the shortest weighted path length

Greedy algorithm to construct Huffman tree

Four steps for transmitting messages

A stacked tree is a complete binary tree. The value of the parent node of a large top heap is greater than its child node, and the value of the parent node of a small top heap is smaller than its child node.

combing the pile

Heap sort

TopK problem of massive elements

Directed complete graph (a directed graph with n (n-1) edges)

Links are called arcs

Undirected complete graph (the number of edges is half that of directed complete graph)

links become edges

connected components

A graph whose vertex set is a subset of the parent graph and whose edge set is also a subset of the parent graph becomes a subgraph of the parent graph.

For a graph with n vertices, its spanning tree is a connected subgraph with n vertices and n-1 edges.

If there is an edge connecting two vertices in an undirected graph, then the two vertices are adjacent to each other.

If there is an arc in the directed graph, the receiver is adjacent to the sender

It is easy to find the degree of exit, but it is difficult to find the degree of entry.

It is easy to find the entry degree of the inverse adjacency list, but it is difficult to find the degree.

cross linked list

Prim's algorithm

Kruskal algorithm

Continuously delete vertices with indegree 0

Topological sorting cannot proceed, indicating that the graph contains cycles.

Labeling method, the maximum sum in the forward direction, the minimum difference in the reverse direction, the node with equal forward and reverse directions is the key node

Unit Dijikstra's Algorithm

All-source Floyd algorithm

Average comparison required when checking hits

If the check fails, it needs to be compared n times.

When the search fails, high and low are interleaved.

The maximum number of successful checks is logn and the minimum number is 1.

If the check fails, it needs to be compared logn times.

The search process is divided into two parts - sequential search between blocks and sequential search within blocks.

Assuming that n is the table length and each block contains s data, the average search length is

direct hash function method

digital analytics

Square-Medium Method

folding method

divide and leave remainder method

random number method

open address law

rehash

chain address method

public area overflow method

The ASL of a hash table is a function of the fill factor rather than a function of n

Half search in sorted sequence

The time complexity is between

Select the smallest one from the unordered data and add it to the ordered sequence each time

Use a large top heap, continuously delete the top elements and filter them

Quick sort and divide once: find a record as the pivot, move everything smaller than it to the front, and move everything larger than it to the back

Quicksort is a recursive program

Improvement of quick sorting, select the middle one among the first element, last element, and middle element as the pivot to avoid performance deterioration

Space complexity is mainly reflected in recursion

Heap sort, quick sort, Hill sort, simple selection sort

Bubble sort, direct insertion sort, half insertion sort, two-way merge sort