Armazenamento aleatório, mas a inserção e a exclusão exigem a movimentação de muitos dados

lista vinculada estática

lista vinculada circular

Lista duplamente vinculada

Lista única

A distribuição de memória pode ser descontínua Fácil de inserir e excluir A busca precisa começar de um lado

Primeiro a entrar, último a sair, a entrada e a saída dos elementos são realizadas na mesma extremidade

Primeiro a entrar, primeiro a sair, entrada no final da fila, saída no início da fila

Armazenamento sequencial e armazenamento encadeado

Algoritmo BF

Algoritmo KMP

precedência de linha

Coluna primeiro

Tríade

Suponha que haja dois gráficos. Os vértices e arestas de um gráfico são um subconjunto dos vértices e arestas do outro gráfico.

Um gráfico não direcionado possui n(n-1)/2 arestas e um gráfico direcionado possui n(n-1) arcos.

Muito poucas arestas ou arcos

Existem muitas arestas ou arcos

Valores significativos nas laterais. A compreensão pessoal pode ser comparada à direita da árvore de Huffman

Dois pontos conectados por uma aresta são pontos adjacentes entre si. A aresta está anexada ao vértice e a aresta está associada ao vértice.

Para gráficos direcionados, o ponto é o grau de entrada e o ponto é o grau de saída.

Um caminho com os mesmos pontos inicial e final

Uma matriz que representa a relação de adjacência entre vértices

Uma estrutura de armazenamento vinculada de um gráfico, estabelecendo uma única lista vinculada para cada vértice do gráfico e colocando vértices adjacentes na lista vinculada

É outra estrutura de armazenamento em cadeia de gráfico direcionado

É outra estrutura de armazenamento em cadeia de gráfico não direcionado

Acesso de um vértice Encontre o primeiro ponto adjacente não visitado do vértice recém-visitado e repita a execução Retorna o vértice visitado anteriormente que ainda possui vértices adjacentes não visitados e encontra o próximo vértice adjacente não visitado.

Acesso de um vértice Visite cada vértice adjacente não visitado deste vértice em sequência A partir desses pontos adjacentes, visite seus pontos adjacentes em sequência.

Algoritmo de Prim

Algoritmo de Kruskal

Algoritmo de Dijkstra

Algoritmo de Freud

Em um gráfico direcionado, visite um vértice sem antecessor e produza Exclua este vértice. Repita as operações acima

O caminho ponderado mais longo de um ponto com grau 0 (ponto de origem) até o ponto de destino

uma unidade independente na árvore

O número de subárvores que um nó possui é chamado de grau do nó

Nós com grau 0 são chamados de folhas ou nós terminais

O nível máximo de nós na árvore é chamado de profundidade ou altura da árvore

O grau de uma árvore é o valor máximo do grau de cada nó da árvore

Uma árvore binária de profundidade k e contendo 2∧k-1 nós

Características

Árvore binária com profundidade k e n nós Uma árvore binária completa é chamada de árvore binária completa se e somente se cada nó corresponde a um nó numerado de 1 a n em uma árvore binária completa de profundidade k.

Características

A lista vinculada binária composta por esta estrutura de nó é usada como estrutura de armazenamento da árvore binária e é chamada de lista vinculada de pistas. Os ponteiros que apontam para o predecessor e o sucessor do nó são chamados de pistas. uma pista de árvore binária.

passagem de pré-encomenda

travessia em ordem

Travessia pós-ordem

Os chamados primeiro, meio e último referem-se ao tempo de acesso ao nó raiz. Para percorrer uma árvore binária, as subárvores esquerda e direita e os nós raiz devem ser acessados ​​em uma determinada ordem.

caminho

comprimento do percurso

comprimento do caminho da árvore

certo

A estrutura da árvore de Huffman

Codificação de Huffman

Cálculo do valor WPL

Uma coleção de elementos de dados do mesmo tipo

O valor de um item de dados em um elemento de dados

Com base em um determinado valor, determine um registro ou elemento de dados na tabela de pesquisa cuja chave seja igual ao valor fornecido

Começando em uma extremidade da tabela, compare-os sequencialmente

Inicie a comparação a partir do meio da tabela. Se for maior, faça uma comparação pela metade na metade que for maior. Se for menor, faça uma comparação pela metade na metade que for menor que a tabela até que a busca seja bem-sucedida. não há resultado.

Crie uma tabela de índices e realize buscas sequenciais nos blocos de acordo com os blocos apontados pela tabela de índices.

Se a subárvore esquerda não estiver vazia, ela deverá ser menor que seu nó raiz.

Se a subárvore direita não estiver vazia, ela deverá ser maior que seu nó raiz.

As subárvores esquerda e direita são árvores classificadas binariamente.

Com base na árvore de classificação binária, existe uma restrição adicional, ou seja, o valor absoluto da diferença de profundidade entre as subárvores esquerda e direita não excede 1.

É a operação de reordenar um conjunto de registros em ordem não decrescente ou não crescente de palavras-chave

Quando as chaves de ordenação são diferentes, o resultado obtido pela ordenação da sequência não ordenada de qualquer registro é único, caso contrário não é único.

Classificação interna

classificação externa

Ao inserir o i-ésimo (i >= 1), os V[0], V[1],..., V[i-1] anteriores foram ordenados. Neste momento, use o código de classificação de V[I] para comparar a ordem dos códigos de classificação de V[i-1], V[i-2],..., encontre a posição de inserção e insira V[i] , e o elemento na posição original será inserido em Mover para trás

Use baixo, médio e alto para dividi-lo em duas regiões [baixo, médio-1] e [médio 1, alto] Se o valor da chave for menor que o valor do meio da sequência, significa que o valor da chave deve ser inserido na área esquerda [baixo, médio-1] e então dividir a área repetidamente para [baixo, médio-1] até baixo> alto e a inserção final A posição deve ser alta 1. Mova os dados na posição após alta para trás como um todo e, em seguida, atribua a chave para [mid 1]

É essencialmente um método de inserção de grupo que classifica encurtando continuamente o comprimento do tecido.

Encontre elementos pequenos ou grandes, um por um, comparando e trocando posições de elementos adjacentes.

É uma melhoria na classificação de bolhas. Selecione o valor de divisão para dividi-lo em duas partes. O lado esquerdo é menor que o lado direito e o lado direito é maior.

Primeiro, encontre o menor (grande) elemento na sequência não classificada e armazene-o no início da sequência classificada. Em seguida, continue a encontrar o menor (grande) elemento dos elementos não classificados restantes e, em seguida, coloque-o no final da sequência. sequência ordenada. E assim por diante até que todos os elementos estejam classificados.

Compare os n elementos a serem classificados em pares, retire os menores e, em seguida, compare os n/2 menores em pares, retire os menores e repita as etapas acima até que os elementos mínimos sejam retirados.

Construa a sequência a ser classificada em um heap grande. De acordo com as propriedades do heap grande, o nó raiz do heap atual é o maior elemento da sequência. Troque o elemento superior do heap pelo último elemento e, em seguida, reconstrua os nós restantes em um grande heap superior e assim por diante. A partir da primeira vez que construímos o grande heap superior, podemos obter o valor máximo de uma sequência a cada. vez que construímos e depois colocamos no final da grande pilha superior. Finalmente, uma sequência ordenada é obtida.

método de maior prioridade

método de prioridade mais baixa