Preste atenção ao julgamento final sobre se as duas mesas estão vazias ou não.

complexidade de tempo:

complexidade de tempo:

complexidade de tempo:

Troque continuamente os primeiros e últimos elementos de uma lista linear

Preste atenção na ordem do código

Preste atenção na ordem do código

Constantemente fazendo exclusão de cabeça, inserção de cabeça

A pilha é uma lista linear especial (primeiro a entrar, último a sair, último a entrar, primeiro a sair)

Uma pilha vazia não pode ser retirada e uma pilha cheia não pode ser inserida.

A pilha é implementada com uma tabela linear. O ponteiro superior (na verdade, um número) da pilha é -1, o que significa uma pilha vazia, e top=MAX-1, o que significa uma pilha cheia.

Quando a pilha está cheia, torna-se um estouro; quando a pilha está vazia, torna-se um estouro negativo.

A fila só pode ser excluída na frente da fila (front) e só pode ser inserida no final da fila (rear).

Frente inicial=traseira=-1

Falso estouro de fila

Julgamento de filas cheias e vazias: front=rear

Estrutura de armazenamento da cadeia de filas

matriz triangular superior e inferior

Matriz simétrica

matriz tridiagonal

armazenamento de mesa triplo

armazenamento em cadeia

Usando uma fila, cada vez que um nó é visitado, seus filhos esquerdo e direito são enfileirados.

Regulamento: Se houver uma subárvore esquerda, então lchild aponta para sua subárvore esquerda, caso contrário, aponta para seu antecessor. Se houver uma subárvore direita, então rchild aponta para sua subárvore direita, caso contrário, aponta para seu sucessor.

Uma árvore de classificação binária é uma árvore vazia ou possui as seguintes propriedades. Se sua subárvore esquerda não estiver vazia, todos os valores dos nós na subárvore esquerda serão menores que o valor do nó raiz. , então a subárvore direita Os valores de todos os nós na subárvore são maiores que o valor do nó raiz. As subárvores esquerda e direita são árvores binárias classificadas.

Encontrar

estrutura

excluir

Encontre análise de desempenho

Uma árvore binária balanceada é antes de tudo uma árvore binária ordenada. Suas subárvores esquerda e direita são árvores binárias balanceadas e a diferença de profundidade entre as subárvores esquerda e direita não excede 1.

Árvores binárias balanceadas são construídas usando técnicas de rotação balanceada

A árvore com o menor comprimento de caminho ponderado

Algoritmo ganancioso para construir a árvore de Huffman

Quatro etapas para transmitir mensagens

Uma árvore empilhada é uma árvore binária completa. O valor do nó pai de um heap superior grande é maior que seu nó filho, e o valor do nó pai de um heap superior pequeno é menor que seu nó filho.

penteando a pilha

Classificação de pilha

Problema TopK de elementos massivos

Gráfico completo direcionado (um gráfico direcionado com n (n-1) arestas)

Links são chamados de arcos

Gráfico completo não direcionado (o número de arestas é metade do gráfico completo direcionado)

links se tornam bordas

componentes conectados

Um gráfico cujo conjunto de vértices é um subconjunto do gráfico pai e cujo conjunto de arestas também é um subconjunto do gráfico pai torna-se um subgrafo do gráfico pai.

Para um grafo com n vértices, sua árvore geradora é um subgrafo conectado com n vértices e n-1 arestas.

Se houver uma aresta conectando dois vértices em um grafo não direcionado, então os dois vértices serão adjacentes um ao outro.

Se houver um arco no gráfico direcionado, o receptor é adjacente ao remetente

É fácil encontrar o grau de saída, mas é difícil encontrar o grau de entrada.

É fácil encontrar o grau de entrada da lista de adjacência inversa, mas é difícil encontrar o grau.

lista vinculada

Algoritmo de Prim

Algoritmo de Kruskal

Exclua vértices continuamente com indegree 0

A classificação topológica não pode prosseguir, indicando que o gráfico contém ciclos.

Método de rotulagem, a soma máxima na direção direta, a diferença mínima na direção reversa, o nó com direções direta e reversa iguais é o nó chave

Algoritmo da Unidade Dijikstra

Algoritmo Floyd de todas as fontes

Comparação média necessária ao verificar ocorrências

Se a verificação falhar, ela precisará ser comparada n vezes.

Quando a pesquisa falha, alto e baixo são intercalados.

O número máximo de verificações bem-sucedidas é logn e o número mínimo é 1.

Se a verificação falhar, será necessário comparar os tempos de logn.

O processo de busca é dividido em duas partes – busca sequencial entre blocos e busca sequencial dentro de blocos.

Assumindo que n é o comprimento da tabela e cada bloco contém s dados, o comprimento médio da pesquisa é

método de função hash direta

análise digital

Método Quadrado-Médio

método de dobramento

Método de dividir e deixar resto

método de número aleatório

lei de endereço aberto

refazer

método de endereço de cadeia

método de estouro de área pública

O ASL de uma tabela hash é uma função do fator de preenchimento e não de n

Meia pesquisa em sequência ordenada

A complexidade do tempo está entre

Selecione o menor dos dados não ordenados e adicione-o à sequência ordenada a cada vez

Use um grande heap superior, exclua continuamente os elementos superiores e filtre-os

Divisão única de classificação rápida: encontre um registro como pivô, mova tudo menor que ele para a frente e mova tudo que for maior que ele para trás

Quicksort é um programa recursivo

Melhoria da classificação rápida, selecione o do meio entre o primeiro elemento, o último elemento e o elemento do meio como pivô para evitar deterioração do desempenho

A complexidade do espaço se reflete principalmente na recursão

Classificação por heap, classificação rápida, classificação por colina, classificação por seleção simples

Classificação por bolha, classificação por inserção direta, classificação por meia inserção, classificação por mesclagem bidirecional