MindMap Gallery Estrutura do curso de estrutura de dados
Revisei o mapa criado pela estrutura de dados e espero que possa ajudar a todos. Ele resume em detalhes o conteúdo de conhecimento da pesquisa da estrutura de dados, gráfico, árvore, classificação e pontos de teste da tabela linear.
Edited at 2021-12-10 20:35:35Revisão da estrutura de dados
mesa linear
Armazenamento linear
mesclar
Preste atenção ao julgamento final sobre se as duas mesas estão vazias ou não.
Encontrar
complexidade de tempo:
inserir
complexidade de tempo:
excluir
complexidade de tempo:
Aplicação de tabelas lineares – inversão in-loco
Troque continuamente os primeiros e últimos elementos de uma lista linear
armazenamento em cadeia
Inserção em lista vinculada individualmente
Preste atenção na ordem do código
Exclusão de lista vinculada individualmente
Preste atenção na ordem do código
Inversão no local de lista vinculada individualmente
Constantemente fazendo exclusão de cabeça, inserção de cabeça
Lista vinculada circular única
Lista duplamente vinculada
pilhas e filas
pilha
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.
fila
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
A solução é construir uma fila circular (front=(front 1)%MAX), rear=(rear 1)%MAX
Julgamento de filas cheias e vazias: front=rear
Solução 1: defina um sinalizador para determinar se a última operação foi enviada por push ou retirada da pilha
Solução 2: Defina um número para registrar o número de elementos na fila
Solução 3: Sacrifique um espaço de armazenamento (traseiro 1)%MAX==frontal
Estrutura de armazenamento da cadeia de filas
variedade
Várias matrizes especiais
matriz triangular superior e inferior
Matriz simétrica
matriz tridiagonal
matriz esparsa
armazenamento de mesa triplo
armazenamento em cadeia
Árvore
Definição de árvore binária
Uma árvore binária é uma árvore vazia ou um nó raiz mais duas árvores binárias disjuntas que se tornam a subárvore esquerda e a subárvore direita, respectivamente.
árvore binária especial
árvore binária completa
árvore binária completa
Propriedades de árvores binárias
O i-ésimo nível da árvore binária tem no máximo
Uma árvore binária de nível k tem no máximo
Para qualquer árvore binária, assumindo que o número de nós folha é n0 e o número de nós secundários é n2, então n0=n2 1
Numere a árvore binária em ordem hierárquica. O nó filho esquerdo do nó numerado i é 2i e o nó filho direito é 2i 1.
Armazenamento sequencial de árvores binárias
Armazene apenas árvores binárias completas, deixando o espaço 0 livre, consulte Propriedade 4
Armazenamento vinculado de árvores binárias - lista vinculada binária
Lista vinculada de três vias (cada nó armazena seu nó pai)
Travessia de árvore binária
Travessia de pré-ordem, travessia de ordem, travessia de pós-ordem
passagem de ordem de nível
Usando uma fila, cada vez que um nó é visitado, seus filhos esquerdo e direito são enfileirados.
travessia não recursiva
Aplicações de árvores binárias
Encontre a profundidade de uma árvore binária
Encontre o número de folhas de uma árvore binária
árvores e floresta
Representação do irmão dos filhos da árvore
árvore binária especial
pista de árvore binária
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.
Árvore de classificação binária
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
A pesquisa BST é um processo de comparação e ramificação constante
estrutura
A construção do BST é um processo de localização e adição contínua de nós folha.
excluir
Exclua nós folha, exclua-os diretamente
Exclua o nó com grau 1 e substitua-o por seu nó filho não vazio
Exclua o nó com grau 2 e substitua-o pelo seu antecessor.
Encontre análise de desempenho
O conceito de comprimento médio de pesquisa
árvore binária balanceada
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
árvore binária ideal
A árvore com o menor comprimento de caminho ponderado
Algoritmo ganancioso para construir a árvore de Huffman
Quatro etapas para transmitir mensagens
1. Conte a frequência de ocorrências de caracteres
2. Construa a árvore Huffman
3. Formule a tabela de códigos de Huffman
4. Traduza caracteres
Pilha
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
foto
conceito de diagrama
gráfico direcionado
Gráfico completo direcionado (um gráfico direcionado com n (n-1) arestas)
Links são chamados de arcos
Gráfico não direcionado
Gráfico completo não direcionado (o número de arestas é metade do gráfico completo direcionado)
links se tornam bordas
certo
líquido
grau de vértice
O conceito de gráfico conectado
componentes conectados
O subgrafo conectado máximo em um gráfico não direcionado é chamado de componente conectado
Um subgrafo fortemente conectado máximo em um gráfico direcionado é chamado de componente fortemente conectado
subtrama
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.
árvore geradora
Para um grafo com n vértices, sua árvore geradora é um subgrafo conectado com n vértices e n-1 arestas.
adjacências de vértices em um gráfico
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
Armazenamento gráfico
matriz de adjacência
lista de adjacências
É 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
É mais fácil encontrar o grau de entrada e saída
Percurso gráfico
primeira pesquisa em profundidade
amplitude primeira pesquisa
algoritmo gráfico
Encontre a árvore geradora mínima para um gráfico não direcionado
Algoritmo de Prim
Principalmente conectado, selecione a borda conectada com o menor peso de cada vez
Complexidade algorítmica
Algoritmo de Kruskal
Focando no custo mínimo, selecione a aresta com o menor peso de cada vez para ver se ela pode ser adicionada à árvore geradora mínima.
Complexidade algorítmica
Verificando Anéis – Classificação Topológica
Exclua vértices continuamente com indegree 0
A classificação topológica não pode prosseguir, indicando que o gráfico contém ciclos.
Rede de gráfico acíclico direcionado (AOV) - algoritmo de caminho crítico
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 de caminho mais curto
Algoritmo da Unidade Dijikstra
programaçao dinamica
Algoritmo Floyd de todas as fontes
Multiplicação da matriz
Encontrar
Encontre categorias
pesquisa estática
pesquisa dinâmica
Palavras-chave
Se uma palavra-chave puder representar um elemento único, ela será chamada de palavra-chave primária.
Se puder representar apenas alguns elementos, é chamada de palavra-chave secundária.
Pesquisar na tabela linear
pesquisa sequencial
Comparação média necessária ao verificar ocorrências
Se a verificação falhar, ela precisará ser comparada n vezes.
meia pesquisa
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.
Pesquisa de índice
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 é
Pesquisa na tabela hash (pesquisa de hash)
Método de construção de função hash
método de função hash direta
Pegue a própria palavra-chave ou uma função linear da palavra-chave como o endereço hash
análise digital
H(chave)=s dígitos distribuídos uniformemente na chave
Método Quadrado-Médio
H (chave) = os dígitos do meio da chave2
método de dobramento
Divida a palavra-chave em várias partes e use a soma das várias partes como um endereço hash
Método de dividir e deixar resto
Pegue um certo número primo que não seja maior que o comprimento e remova o restante do número primo como endereço hash.
método de número aleatório
H(chave)=aleatório(chave)
métodos de resolução de conflitos
lei de endereço aberto
sondagem quadrada e hash
Sondagem linear e depois hash
Sondagem aleatória e depois hash
refazer
Hash novamente com uma função hash diferente
método de endereço de cadeia
Armazene todos os valores com o mesmo endereço hash em uma lista vinculada
método de estouro de área pública
Crie uma tabela de estouro
Comprimento médio de pesquisa de tabelas hash
O ASL de uma tabela hash é uma função do fator de preenchimento e não de n
organizar
Inserir classe
classificação por inserção direta
classificação de meia inserção
Meia pesquisa em sequência ordenada
Tipo de colina
A complexidade do tempo está entre
Selecione a turma
Ordenação por seleção simples
Selecione o menor dos dados não ordenados e adicione-o à sequência ordenada a cada vez
Classificação de pilha
Use um grande heap superior, exclua continuamente os elementos superiores e filtre-os
aula de intercâmbio
Tipo de bolha
Ordenação rápida
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
Mesclar classe
Classificação de mesclagem bidirecional
Comparação de estabilidade
Compare a complexidade do tempo e a complexidade do espaço com n ao quadrado (a classificação por seleção simples é um caso especial)
Classificação instável
Classificação por heap, classificação rápida, classificação por colina, classificação por seleção simples
classificação estável
Classificação por bolha, classificação por inserção direta, classificação por meia inserção, classificação por mesclagem bidirecional