Galeria de mapas mentais Mapa mental de estrutura de dados
Este é um mapa mental sobre estrutura de dados, incluindo os conceitos básicos de estrutura de dados, tabelas lineares, pilhas e filas, etc. Espero que isto ajude!
Editado em 2023-11-07 11:40:27Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
estrutura de dados
Capítulo Um Introdução
1. Conceitos básicos de estrutura de dados
1. Conceitos básicos e terminologia
1.Dados
O portador da informação é uma coleção de números, caracteres e todos os símbolos que podem ser reconhecidos e processados por computadores que descrevem os atributos de coisas objetivas.
2. Elementos de dados
A unidade básica de dados, composta por itens de dados, a menor unidade indivisível
3. Objetos de dados
Uma coleção de elementos de dados com as mesmas propriedades, um subconjunto de dados
4.Tipo de dados
Uma coleção de valores e um conjunto de operações definidas na coleção.
Tipo atômico
O valor não pode ser dividido
tipo de estrutura
O valor pode ser dividido ainda mais
tipo de dados abstrato
5. Tipos de dados abstratos
1. Definição: Um modelo matemático e um conjunto de operações definidas no modelo
2. Características: A definição depende apenas do seu conjunto de características lógicas e nada tem a ver com a forma como é representado e implementado dentro do computador.
3. Representação: (objetos de dados, relacionamentos de dados, conjuntos de operações básicas)
6. Estrutura de dados
1. Estrutura: a relação entre os elementos de dados
2. Definição: Uma coleção de elementos de dados que possuem um ou mais relacionamentos específicos entre si.
3. Conteúdo: Estrutura lógica, estrutura de armazenamento, operações de dados
Estrutura lógica: o desenho de um algoritmo
Estrutura de armazenamento: implementação de um algoritmo
2. Três elementos da estrutura de dados
1. Estrutura lógica dos dados
1. Definição: A relação lógica entre os elementos de dados, que nada tem a ver com armazenamento e é independente do computador.
2. Classificação
estrutura linear
mesa linear
Um a um
estrutura não linear
juntar
Pertencem ao mesmo conjunto
Árvore
um para muitos
Figura/Rede
muitos para muitos
2. Estrutura de armazenamento de dados
1. Definição: Representação da estrutura de dados em computador (também chamada de imagem/estrutura física)
2. Incluindo: representação de elementos de dados e representação de relacionamentos
3. Classificação
armazenamento sequencial
Vantagens: Acesso aleatório, os elementos ocupam menos espaço de armazenamento
Desvantagens: Apenas um bloco adjacente de unidades de armazenamento pode ser usado, resultando em mais fragmentação externa
armazenamento em cadeia
Vantagens: Sem fragmentação
Desvantagens: Os ponteiros de armazenamento ocupam espaço de armazenamento adicional e só podem ser acessados sequencialmente;
Armazenamento de índice
Definição: Crie uma tabela de índice adicional, cada item é chamado de item de índice (palavra-chave, endereço)
Vantagens: Recuperação rápida
Desvantagens: ocupa mais espaço de armazenamento; adicionar e excluir dados requer modificação da tabela de índice, o que leva mais tempo.
Armazenamento de hash
Definição: calcule diretamente o endereço de armazenamento do elemento (armazenamento hash) com base na palavra-chave do elemento
Vantagens: Recuperação, adição e exclusão de nós são rápidas
Desvantagens: Se a função hash não for boa, ocorrerão conflitos de unidades de armazenamento de elementos, o que aumentará o custo de tempo e espaço.
3. Operações de dados
1. Definição de operação: Aponte a função da operação de acordo com a estrutura lógica
2. Implementação da operação: Aponte as etapas específicas da operação de acordo com a estrutura de armazenamento.
Resumo da pergunta
1. Sujeito a erros
1. Pertence a uma estrutura lógica
lista ordenada
2. Uma fila circular é uma fila representada por uma tabela de sequência. É uma estrutura de dados, não uma estrutura de dados abstrata.
3. Os espaços de armazenamento de diferentes nós podem ser descontínuos, mas os espaços de armazenamento dentro dos nós devem ser contínuos.
4. Duas estruturas de dados diferentes, a estrutura lógica e a estrutura física podem ser exatamente iguais, mas as operações de dados são diferentes.
Árvores binárias e árvores de classificação binária têm tempos diferentes para pesquisar nós.
2. Algoritmos e avaliação de algoritmos
1. Conceitos básicos de algoritmos
1. Definição: Uma descrição das etapas para resolver um problema específico, uma sequência finita de instruções
2.Características
1. Finitude
2.Certeza
3. Viabilidade
4. Entrada
5.Saída
3. Bom algoritmo
1. Correção
2. Legibilidade
3. Robustez
4. Eficiência e baixos requisitos de armazenamento
2. Medição da eficiência do algoritmo
1. Complexidade de tempo O(n)
Definição: Mede a rapidez com que o tempo de execução de um algoritmo aumenta à medida que o tamanho do problema aumenta.
2. Complexidade espacial S(n)
1. Definição: Mede a rapidez com que o espaço exigido pelo algoritmo aumenta à medida que o tamanho do problema aumenta.
2. O algoritmo funciona no local: o espaço auxiliar exigido pelo algoritmo é constante, ou seja, O(1)
Resumo da pergunta
1. Sujeito a erros
1. Mesclar duas listas vinculadas ascendentes de comprimento m, n em uma lista vinculada descendente de m n (pegue o elemento menor, método de interpolação principal)
1. Melhor caso: O(min(m,n))
Aquele que exige menos
2. Pior caso: O(max(m,n)) =O(m n)
Ambas as listas vinculadas foram percorridas uma vez
2. Cálculo da complexidade do tempo
1.soma = eu;
O (n ^ 1/2)
k-ésima vez: soma = 1 2 3 ... k ≥n
2.i=i*2
O(log₂n)
3. Algoritmo recursivo
1.T(n)=2T(n/2) n (n>1) (quando n=1: T(n)=1)
O(nlog₂n)
2. Suponha que n = 2 ^ k, primeiro encontre a fórmula geral de T (2 ^ k) de acordo com a condição de recursão e depois converta-a em n, ou seja, obtenha a complexidade do tempo
3. Para o mesmo algoritmo, quanto maior o nível da linguagem implementada, menor será a eficiência de execução.
Capítulo 2 Tabela Linear
1. Definição e operações básicas de tabelas lineares
1.Definição de tabela linear
1.Definição: Sequência finita do mesmo tipo de dados
2. Nota: Listas lineares são estruturas lógicas, listas sequenciais e listas vinculadas referem-se a estruturas de armazenamento.
2. Operações básicas de tabelas lineares
1. Nota: & representa uma referência em C. Se uma variável de ponteiro for passada e precisar ser alterada no corpo da função, uma referência à variável de ponteiro deve ser usada (ponteiros para ponteiros também podem ser usados em C)
2. Principais operações
2. Representação sequencial de tabelas lineares
1. Definição de tabela de sequência
1. A tabela de sequência requer três partes
A posição inicial do espaço de armazenamento
Espaço máximo de armazenamento da tabela de sequência
O comprimento atual da tabela de sequência
2. Alocação estática
3. Alocação dinâmica
4. Declaração de alocação dinâmica
Linguagem C: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C: L.data=new ElemType[InitSize];
5. Nota: A alocação dinâmica não é armazenamento em cadeia, é também uma estrutura de armazenamento sequencial e a estrutura física não muda: é um método de acesso aleatório, mas o tamanho do espaço alocado pode ser determinado em tempo de execução.
6. Recursos: acesso aleatório, alta densidade de armazenamento, inserção e exclusão exigem a movimentação de um grande número de elementos
2. Implementação de operações básicas na tabela de sequência
1. Operação de inserção O(n)
2. Excluir operação O(n)
3. Pesquisa por valor (pesquisa sequencial) O(n)
Resumo da pergunta
1. Sujeito a erros
1. A tabela linear deve ser uma sequência finita
2. Insira um número na i-ésima posição da tabela de sequência. O valor legal de i é: 1≤i≤n 1.
Inserir na posição n1 equivale a anexar ao final da tabela
2. Algoritmo
1. Inverta todos os elementos da lista de sequências
1. Digitalize a primeira metade e troque o i-ésimo elemento (0≤i<n/2) pelo elemento correspondente (ni-1) na segunda metade
Espaço O(1)
1.1 No array A[m n], existem duas tabelas de sequências com comprimentos m e n, e as posições são trocadas.
1. Pensamentos
1. Primeiro inverta a ordem de todos os elementos em A (n,n-1,...,m,m-1,...,1)
2. Em seguida, use o algoritmo de ordem inversa para os primeiros n elementos e os últimos m elementos, respectivamente.
2. Perceba
1. Defina a função Reverse() para implementar a ordem inversa de qualquer posição da esquerda para a direita
2. Defina a função Exchange() para realizar a troca de posição de duas tabelas de sequência com comprimentos m e n.
3.Reverse() possui três parâmetros. O primeiro é o array que precisa ser revertido. Troque o elemento esquerdo pelo elemento correspondente (direita-esquerda-1)
4.Exchange() tem três parâmetros, o primeiro é o array A e os comprimentos restantes são m e n.
5.Exchange() chama Reverse(), passando parâmetros (A,0,m n-1) pela primeira vez A segunda vez (A,0,n-1), a terceira vez (A,n,m n-1)
3. Descrições semelhantes
1. Mova os elementos em A para as posições p esquerdas
1. Trate os primeiros p elementos como array B
2. Trate os últimos elementos np como array C
3. Conclua a troca das posições B e C
Tempo O(n), espaço O(1)
2. Lista sequencial (não ordenada) exclui todos os elementos de dados com valor x
1. Utilize k para registrar a quantidade de elementos que não são iguais a x (valor inicial = 0), que é a posição atual que deve ser inserida.
2. Digitalize a tabela de sequências. Se não for x, coloque este elemento na k-ésima posição e k aumentará em 1.
3. O comprimento da última tabela modificada = k
Tempo O(n), espaço O(1)
2.1 Lista sequencial (não ordenada) exclui todos os elementos com valores entre s e t
1. Basta alterar k para registrar o número de elementos menor que s ou maior que t.
3. A lista de sequência ordenada exclui todos os elementos entre os valores fornecidos s e t
1. Primeiro encontre o primeiro elemento ≥ s (o primeiro elemento excluído)
2. Encontre o primeiro elemento > t (o próximo elemento após o último elemento excluído)
3. Mova diretamente os seguintes elementos para frente e, finalmente, modifique o comprimento da tabela
4. Remova todos os elementos com valores duplicados da lista ordenada
1. A ideia é semelhante à classificação por inserção direta. Inicialmente, o primeiro elemento é considerado uma lista ordenada não repetitiva.
2. Determine, por sua vez, se os seguintes elementos são iguais ao último elemento da lista ordenada não repetitiva anterior
3. Dois ponteiros: i sempre aponta para o último elemento da lista ordenada, j é o ponteiro de trabalho
4.1 Alterar lista ordenada para lista não ordenada
1. Usando uma tabela hash, o tempo é O(n)
5. Mesclar duas listas ordenadas em uma lista ordenada e retornar o resultado pela função
1. A função possui três parâmetros, o último é a lista vinculada de resultados, tipo de referência
2. Compare os elementos do cabeçalho das duas listas vinculadas em ordem e coloque o menor na nova lista.
3. Verifique qual tabela resta e adicione a parte restante ao final da nova tabela
6. Uma sequência ascendente S de comprimento L, a mediana é ┍L/2┑ Encontre a mediana de duas sequências ascendentes de comprimento igual A e B
1. Primeiro encontre as medianas aeb de A e B respectivamente e compare-as.
2. Se a=b, então a é a mediana necessária
3. Se a<b, descarte a metade menor de A e descarte a metade maior de B. Os comprimentos dos dois descartes devem ser iguais.
4. Se a>b, descarte a metade maior de A e descarte a metade menor de B. É necessário que os comprimentos dos dois descartes sejam iguais.
5. Repita as etapas 2, 3 e 4 até que ambas as sequências contenham apenas um elemento e o menor seja a mediana necessária.
Nota: Para garantir que os comprimentos descartados sejam sempre iguais
1. Quando a sequência é um número ímpar, o ponto médio é mantido
2. Quando a sequência é um número par, porque a posição do ponto médio é relativamente primeira, Portanto, ao descartar a parte menor, você deve descartar o ponto médio junto. Para garantir que o comprimento descartado seja igual à parte maior
3. Ambos os casos 3 e 4 precisam ser discutidos separadamente.
Tempo O(log₂n), espaço O(1)
7. Se o número de elementos com valor x > n/2, é chamado de elemento principal. Encontre o elemento principal de A.
1. Selecione os principais elementos candidatos
1. Coloque o primeiro número a em c como candidato a elemento principal e registre o número de ocorrências de a como 1
2. Se o próximo elemento = a, conte 1, caso contrário conte -1
3. Quando a contagem diminuir para 0, substitua o elemento principal candidato, coloque o próximo número em c e conte novamente = 1
4. Repita o processo até o final
2. Determine se o elemento em c é o verdadeiro elemento principal
1. Digitalize novamente para contar o número de ocorrências de c. Se >n/2, é o elemento principal.
Tempo O(n), espaço O(1)
Nota: Se você usar classificação por contagem: tempo O(n), espaço O(n)
8. Encontre o menor número inteiro positivo que não aparece na matriz, menos tempo
1. Troque espaço por tempo, aloque uma matriz B[n] para marcação, registre se um número inteiro positivo de 1-n aparece e o valor inicial é todo 0
2. Nenhuma ação é tomada para números menores ou iguais a 0 ou maiores que n.
3. Se 0<A[i]≤n, seja B[A[i]-1]=1, caso contrário nenhuma operação será executada
4. Percorra B, encontre o primeiro B[i]==0 e retorne i 1. Se nem todos forem 0, retorne i 1 (i=n ao sair do loop)
3. Representação vinculada de tabela linear
1. Definição de lista vinculada individualmente
1.Descrição do tipo de nó
2. Recursos: desperdício de espaço, acesso não aleatório
3. A diferença entre ponteiro principal e nó principal
1. Independentemente de haver ou não um nó principal, o ponteiro principal sempre aponta para o primeiro nó da lista vinculada.
2. O nó principal é o primeiro nó na lista vinculada com o nó principal e geralmente não armazena informações.
4. Vantagens de introduzir nós principais
1. A operação na primeira posição da lista vinculada é consistente com a operação nas demais posições.
2. Independentemente de a lista vinculada estar vazia ou não, o ponteiro principal aponta para o ponteiro não nulo do nó principal, e as listas vazias e as listas não vazias são tratadas da mesma forma
2. Implementação de operações básicas em listas vinculadas simples
1. Método de inserção de cabeçalho para criar uma lista vinculada
2. Crie uma lista vinculada usando o método de inserção final
3. Encontre o valor do nó por número de série
4. Encontre os nós da tabela por valor
5. Inserir operação de nó
Operação de inserção direta: Encontre primeiro o nó anterior, a complexidade de tempo é O (n)
Extensão: Converta a operação de inserção direta em uma operação de inserção reversa e, em seguida, troque os dados dos dois nós. A complexidade de tempo é O (1).
6. Operação de exclusão de nó
Encontre primeiro o nó predecessor e, em seguida, exclua o nó, O(n)
Extensão: primeiro troque dados com o nó sucessor e, em seguida, exclua o nó sucessor, O(1)
7. Encontre a operação de comprimento da tabela
Conte o número de nós de dados
3. Lista duplamente vinculada
1. Descrição dos tipos de nós em listas duplamente vinculadas
2. Operação de inserção
3. Excluir operação
4. Lista vinculada circular
1. Lista circular vinculada individualmente
1. Condição nula: se o ponteiro do nó principal aponta para o ponteiro principal
2. Ao operar no início e no final de uma lista vinculada individualmente: não defina o ponteiro principal e apenas defina o ponteiro final, que é mais eficiente.
3. Você pode percorrer toda a lista vinculada começando em qualquer nó
2. Lista circular duplamente vinculada
Condição nula: o campo anterior e o próximo campo do nó principal apontam para o ponteiro principal.
5. Lista vinculada estática
1. Definição: Use um array para descrever uma estrutura de armazenamento encadeada, que também possui um campo de dados e um campo de ponteiro. O ponteiro é o endereço relativo do nó (subscrito do array), também chamado de cursor.
2.Formulário
3. Sinalizador de fim: próximo==-1
4.Atenção
1. Assim como a tabela de sequência, um espaço de memória contínua deve ser alocado antecipadamente
2. A inserção e exclusão requerem apenas a modificação do ponteiro e não requerem movimentação de elementos.
3. Muito inteligente em linguagens de alto nível (Básica) que não suportam ponteiros
6. Comparação entre lista de sequências e lista vinculada
1. Método de acesso
A lista de sequência pode ser acessada sequencialmente ou aleatoriamente. A lista vinculada só pode ser acessada sequencialmente a partir do cabeçalho.
2. Estrutura lógica e estrutura física
3. Encontre, insira e exclua
1. Pesquise por valor
Quando fora de ordem, é O(n)
Quando ordenada, a tabela de sequência pode ser pesquisada pela metade, O(log₂n)
2. Pesquise por número de série
A lista de sequências é O(1), a lista vinculada é O(n)
4. Alocação de espaço
5. Como escolher a estrutura de armazenamento
1. Considerações sobre armazenamento
As listas vinculadas são usadas quando é difícil estimar o comprimento e o tamanho do armazenamento, mas a densidade de armazenamento das listas vinculadas é baixa.
2. Considerações baseadas nas operações
Acesse frequentemente elementos de dados por número de série usando uma tabela de sequência
3. Considerações ambientais
Listas sequenciais são fáceis de implementar, listas vinculadas são baseadas em ponteiros
Se for mais estável, escolha a lista sequencial; se for mais dinâmica, escolha a lista encadeada.
Resumo da pergunta
1. Sujeito a erros
1. A estrutura de armazenamento em cadeia é mais conveniente do que a estrutura de armazenamento sequencial para representar várias estruturas lógicas.
2. O armazenamento sequencial não pode ser usado apenas para armazenar estruturas lineares, mas também estruturas de gráficos e árvores (árvores binárias completas)
3. As listas vinculadas estáticas precisam alocar um grande espaço contínuo e a inserção e exclusão não requerem elementos móveis.
4. Se uma lista vinculada individualmente for usada para representar a fila, uma lista vinculada circular com um ponteiro final deverá ser usada.
5. Dada uma matriz unidimensional, o tempo mínimo para construir uma lista ordenada unida individualmente é O (nlog₂n)
Primeiro classifique a matriz e depois construa uma lista vinculada individualmente
6. As operações comumente usadas em listas vinculadas são inserir após o último elemento e excluir o primeiro elemento. A operação que economiza mais tempo é.
1. Lista vinculada circular única sem nó principal e ponteiro final
2. Mesmo que seja uma lista duplamente vinculada, desde que não haja ponteiro final, o nó final deve ser encontrado e o tempo é O (n)
tome cuidado
1. Ao inserir um nó: primeiro opere no nó sucessor do nó inserido e, em seguida, opere no nó original
Capítulo 3 Pilha e Fila
1. Pilha
1. Conceito básico de pilha
1. Definição de pilha: uma lista linear com inserção e exclusão em uma extremidade
2.Características da pilha: último a entrar, primeiro a sair
3. Operações básicas da pilha: sem restrições, podem ser usadas diretamente
2. A estrutura de armazenamento sequencial da pilha
1. Implementação de pilha sequencial
1. Ponteiro superior da pilha: S.top Elemento superior da pilha: S.data[S.top]
2. Empurre para a pilha: O ponteiro é primeiro incrementado em 1 e, em seguida, o valor é enviado para o elemento superior da pilha.
3. Abrir a pilha: primeiro pegue o valor do elemento no topo da pilha e, em seguida, diminua o ponteiro no topo da pilha em 1
4. Condições para julgamento vazio e julgamento completo: variam devido às diferentes condições reais.
2. Operações básicas de pilha sequencial
3. Pilha compartilhada
1. Definição: Coloque os fundos das duas pilhas em ambas as extremidades do espaço compartilhado e os topos das duas pilhas se estendam em direção ao meio.
2. Julgamento em branco: top0=-1 top1=MaxSize
3. Frase completa: top1-top0=1
Esta fórmula é válida apenas nas condições acima para julgamento nulo. Se as condições forem diferentes, a fórmula também será diferente.
4. Empurre para dentro da pilha: top0 primeiro adiciona 1 e depois atribui um valor, top1 primeiro decrementa 1 e depois atribui um valor, e o oposto é verdadeiro ao sair da pilha.
Nota: O ponteiro superior da pilha aponta para as diferentes operações do elemento superior da pilha e do elemento próximo ao elemento superior da pilha (S.top=0)
1. Elemento superior da pilha
Empurrar para a pilha:S.data[S.top]=x Retirar da pilha:x=S.data[S.top--]
2. O próximo elemento do elemento superior da pilha
Empurre para a pilha:S.data[S.top]=x Retire da pilha:x=S.data[--S.top]
3. As condições de julgamento para pilha vazia e pilha cheia também serão alteradas.
3. Estrutura de armazenamento em cadeia de pilha
1. Vantagens: Facilita o compartilhamento de espaço de armazenamento em várias pilhas, melhora sua eficiência e evita o estouro de pilha.
2. Recursos: Todas as operações são executadas no topo da tabela. Geralmente, não há nó principal. O ponteiro principal é usado como o ponteiro superior da pilha para facilitar a inserção/exclusão do nó.
4. Sequência pop de pilha
1. Após cada elemento da sequência pop, todos os elementos menores que ele formam uma série decrescente.
Para aumentar sequências
2.f(n)=
f(2)=2, f(3)=5, f(4)=14
Resumo da pergunta
1. Sujeito a erros
1. A pilha e a fila têm a mesma estrutura lógica, não uma estrutura de armazenamento
Listas lineares, pilhas e filas são estruturas lineares.
2. A lista vinculada não possui um nó principal e todas as operações são realizadas no início da lista. É a pilha de links mais inadequada.
1. Uma lista vinculada circular unidirecional com apenas ponteiros de nó principal e nenhum ponteiro de nó final
2. Motivo: após inserir o nó, ele ainda precisa ser transformado em uma lista circular unida individualmente, e o nó final precisa ser encontrado, o que leva tempo O(n).
3.Solução
1. Se o nó principal for usado: o topo da pilha ocupa o primeiro nó e o ponteiro da pilha ocupa o nó principal
2. Se não houver nenhum nó inicial: o topo da pilha ocupa o segundo nó e o ponteiro da pilha ocupa o primeiro nó.
3. Ambos mantêm o primeiro nó inalterado e não precisam encontrar o elemento final da tabela.
3. Insira um nó x em uma pilha de cadeia (sem o nó principal) cujo ponteiro superior está no topo
x->próximo=topo;
4. A sequência push é 1,2,...,n, e a sequência pop é P1, P2,...,Pn Se P2=3, o número de valores possíveis de P3 é n-1.
1. Obviamente, 4, 5,..., n após 3 podem ser obtidos
2.P1 pode ser 1 e P3 pode ser 2.
3.P1 pode ser 2 e P3 pode ser 1
4.P1 pode ser 4 e P3 pode ser qualquer número, exceto 1, 3 e 4.
5. Ao reescrever um programa recursivo de forma não recursiva, a pilha pode não ser aplicável
1. O cálculo da iteração da sequência de Fibonacci requer apenas um loop
6. As definições dos ponteiros no topo da pilha, no início da fila e no final da fila não são exclusivas. Certifique-se de revisar a questão com cuidado.
2. Algoritmo
1. Determine se uma lista vinculada é centralmente simétrica
1. Empurre a primeira metade dos elementos para a pilha em sequência Ao processar a segunda metade, ao acessar um elemento da lista vinculada, retire um elemento da pilha para determinar se eles são iguais.
2. Observe que não há anormalidade quando o número é par. Quando o número é ímpar, o nó central deve ser ignorado primeiro.
3. Não há necessidade de uma pilha real, basta usar o array como pilha e usar o ponteiro de trabalho i como o ponteiro superior da pilha.
2.Fila
1. Conceito básico de fila
1. Definição: Uma tabela linear que permite apenas a inserção em uma extremidade da tabela e a exclusão na outra extremidade.
2. Operações básicas
2. Estrutura de armazenamento sequencial da fila
1. Fila de armazenamento sequencial
1. Dois ponteiros: front aponta para o elemento principal da fila e traseiro aponta para a próxima posição do elemento final da fila.
2. Estado inicial (equipe vazia): Q.front==Q.rear==0
3. Entre na fila: primeiro envie o valor para o último elemento da fila e depois adicione 1 ao último ponteiro da fila.
4. Desenfileirar: primeiro pegue o valor do elemento principal e, em seguida, adicione 1 ao ponteiro principal
5. Existe um falso estouro
6. Digite a descrição
2. Fila circular
1. Estado inicial (equipe vazia): Q.front==Q.rear==0
2. Avance o ponteiro frontal: Q.front=(Q.front 1)%MaxSize
3. Avance o ponteiro final da fila: Q.rear=(Q.rear 1)%MaxSize
4. Comprimento da fila: (Q.rear MaxSize-Q.front)%MaxSize
5. Distinguir entre equipes vazias e completas
1. Sacrifique uma unidade e junte-se à equipe para usar uma unidade a menos (comumente usado)
Fila completa: (Q.rear 1)%MaxSize==Q.front
Equipe vazia: Q.front==Q.rear
Número de elementos na fila: (Q.rear MaxSize-Q.front)%MaxSize
2. Adicione um membro de dados indicando o número de elementos: Q.size
3. Adicionar membros de dados de tag: tag = 0 operação de exclusão: a fila está vazia, tag = 1 operação de inserção: a fila está cheia
3. Operação de fila circular
3. Estrutura de armazenamento da cadeia de filas
1. Armazenamento em cadeia de filas
1. Digite a descrição
2. Lista vinculada única com nó principal: operações unificadas de inserção e exclusão
3. Adequado para situações em que os elementos de dados mudam muito. Não há estouro de fila ou alocação de armazenamento irracional em múltiplas filas.
2. Operações básicas de fila em cadeia
4. Fila dupla
1. Definição: Uma fila que permite que ambas as extremidades (front-end e back-end) entrem e saiam da fila.
2. Estrutura lógica: estrutura linear
3. Deque restrito de entrada
4. Deque restrito de saída
Resumo da pergunta
1. Sujeito a erros
1. Ao usar uma fila de armazenamento encadeada para executar uma operação de exclusão, os ponteiros inicial e final podem ser modificados.
Geralmente, apenas o ponteiro inicial da fila precisa ser modificado. Se houver apenas um elemento, o ponteiro final precisa ser modificado.
2. Na fila em cadeia, quando o elemento apontado por x entra na fila, execute a operação
1.rear->next=x,x->next=null,rear=x;
2. Como x é inserido no final da fila, ele deve ser definido como vazio (frase do meio), o que é mais estrito
2. Tipo de pergunta
1. Determine o status inicial e completo da fila circular
1. Matriz A[0...n-1], a frente aponta para a cabeça da equipe, a retaguarda aponta para o final da equipe O primeiro é armazenado em A[0], perguntando sobre a situação inicial
1. Ao entrar na fila, a frente não se move e a retaguarda 1 eventualmente aponta para A[0]. Então frente inicial = 0, traseira = n-1
Nota: Ao lidar com problemas específicos, você pode usar algumas situações especiais (desenhar esboços simples) para julgar as situações vazias e cheias, o que é mais rápido do que pensar diretamente.
2. Determine a sequência que não pode ser obtida pela fila dupla restrita de entrada/saída
1. Entre diretamente de acordo com as 4 opções uma por uma, utilizando o método de eliminação
2. Situação de erro geral: O último número da fila não pode ser imprensado entre dois números mais avançados que ele (2,3,1)
3. Aplicação de pilha e fila
1. Aplicação de correspondência de pilha entre colchetes
1. Pensamentos
1. Configure uma pilha vazia e leia os parênteses sequencialmente
2. Se for ), ele será retirado da pilha se estiver emparelhado com o topo da pilha (ou é ilegal).
3. Se for ( , coloque-o na pilha como uma nova expectativa mais urgente
4. O algoritmo termina e a pilha fica vazia, caso contrário, a sequência de colchetes não corresponde
2. Aplicação de pilha na avaliação de expressões
1. Expressão pós-fixada: O operador vem depois do operando, sem parênteses
2. O processo de conversão de infixo em sufixo
1. Adicione parênteses a todos os operadores e seus operandos de acordo com a precedência do operador (não há necessidade de adicionar parênteses se eles existirem originalmente)
2. Mova o operador após os parênteses correspondentes
3. Remova os colchetes
Nota: A expressão de prefixo coloca o operador na frente dos parênteses e os demais são iguais.
3. Idéia de algoritmo de infixo para sufixo
1. Números: adicionados diretamente à expressão do sufixo
2. Se for (: empurrar para empilhar
3. Se for): Adicione os operadores da pilha à expressão pós-fixada em sequência até (e exclua o (na pilha
4.Se - */
1. A pilha está vazia e colocada na pilha
2. O topo da pilha é ( , colocado na pilha
3. Maior que a prioridade do elemento no topo da pilha, coloque-o na pilha [se for do mesmo nível, execute 4 também]
4. Caso contrário [menor ou igual à prioridade do topo da pilha], coloque os operadores em sequência até que o operador seja inferior a ele ou (ou a pilha esteja vazia), empurre-o para a pilha
5. A travessia é concluída Se a pilha não estiver vazia, abra todos os elementos em sequência.
4. Processo de expressão de cálculo de sufixo
1. Digitalize cada termo da expressão sequencialmente
2. Operando: Empurre para a pilha
3. Operador <op>: Sai continuamente de dois operandos x e y da pilha para formar uma instrução de operação x<op>y e coloca o resultado do cálculo de volta na pilha
3. Aplicação de pilha em recursão
1. Duas condições
1. Expressão recursiva (corpo recursivo)
2. Condições de limite (saída recursiva)
2. A essência da recursão: O problema original pode ser transformado em um problema menor com as mesmas propriedades, mas em menor escala?
3. Desvantagens: Existem muitas recursões, que podem facilmente causar estouro de pilha; contém muitos cálculos repetidos e não é eficiente;
4. Vantagens: O código é simples e fácil de entender
5. Conversão: precisa ser alcançada com a ajuda da pilha
4. Aplicação de fila em travessia hierárquica
5. Aplicação de filas em sistemas informáticos
1. Resolva o problema de incompatibilidade de velocidade entre o host e os dispositivos externos
1. Configure um buffer de dados de impressão, pause a saída quando estiver cheio, faça outras coisas e aguarde a impressora enviar uma solicitação
2. Resolver problemas de competição de recursos causados por múltiplos usuários
1. Organize cada solicitação em uma fila de acordo com a ordem de tempo e aloque a CPU para o primeiro usuário da fila a cada vez.
Resumo da pergunta
sub tópico
4. Armazenamento compactado de matrizes especiais
1. Definição de array (estrutura lógica)
2. Estrutura de armazenamento do array (armazenamento sequencial)
1. Dois métodos de mapeamento: primeiro linha, primeiro coluna
3. Armazenamento compactado de matrizes
1. Armazenamento compactado: vários elementos com o mesmo valor alocam apenas um espaço, 0 não aloca espaço
2. Matrizes especiais: muitos elementos de matriz idênticos ou zero elementos, distribuídos regularmente
1. Matriz simétrica
2. Matriz triangular
1. Matriz triangular inferior
2. Matriz triangular superior
3. Matriz tridiagonal
4. Matriz esparsa
1. Armazenamento: configure elementos diferentes de zero e linhas e colunas correspondentes em um trio (rótulo de linha, rótulo de coluna, valor)
2. Desvantagens: Perda das características de acesso aleatório
Capítulo 4 Árvores e Árvores Binárias
1. Conceito básico de árvore
1. Definição de árvore
2. Terminologia básica
1. Grau do nó
O número de nós filhos de um nó
2. Grau da árvore
O grau máximo de um nó em uma árvore
3. Profundidade do nó
Começando no nó raiz e acumulando camada por camada, de cima para baixo.
4.Altura do nó
Começando pelos nós folha e acumulando camada por camada, de baixo para cima.
5. Altura da árvore (profundidade)
O número máximo de níveis de nós na árvore
6. O caminho entre dois nós
A sequência de nós passando entre dois nós
7. Comprimento do caminho
O número de arestas passadas no caminho
8.Atenção
Os galhos da árvore são direcionados (os pais apontam para os filhos), o caminho é de cima para baixo e não há caminho entre dois filhos.
3. Natureza das árvores
1. Número de nós = grau de todos os nós 1
2. O i-ésimo nível de uma árvore com grau m possui no máximo m^(i-1) nós.
3. Uma árvore m-ária com altura h tem no máximo (m^h-1)/(m-1) nós.
Soma das séries geométricas
2. Conceito de árvore binária
1. A definição de árvore binária e suas principais características
1. Definição de árvore binária
1. As subárvores podem ser divididas em esquerda e direita e a ordem não pode ser invertida arbitrariamente.
2. A diferença entre uma árvore binária e uma árvore ordenada de grau 2
1. Uma árvore com grau 2 possui pelo menos 3 nós e uma árvore binária pode estar vazia.
2. A ordem esquerda e direita dos filhos de uma árvore ordenada com grau 2 é relativa a outro filho. Uma criança não precisa distinguir entre esquerda e direita. A ordem esquerda e direita de uma árvore binária é determinada
2. Várias árvores binárias especiais
1. Árvore binária completa
Cada nível da árvore contém o maior número de nós
2. Árvore binária completa
1. Definição: Cada nó corresponde a uma árvore binária completa, não necessariamente o máximo em cada nível.
2. Natureza
1. Os nós folha estão apenas nas duas camadas maiores
2. Se houver apenas um nó com grau 1, o nó deixou apenas o filho
3. Árvore de classificação binária
1. As chaves de todos os nós na subárvore esquerda são menores que o nó raiz
2. As palavras-chave de todos os nós na subárvore direita são maiores que o nó raiz
3. As subárvores esquerda e direita são, cada uma, uma árvore de classificação binária.
4. Árvore binária balanceada
A diferença de profundidade entre as subárvores esquerda e direita de qualquer nó não excede 1
3. Propriedades das árvores binárias
1.n0=n₂ 1
Número de nós folha = número de nós com grau 2 1 (n=n0 n₁ n₂=n₁ 2n₂ 1)
2. A enésima camada tem no máximo 2 ^ (n-1) nós
3. Uma árvore binária com altura h possui no máximo 2 ^ h-1 nós.
4. Para árvores binárias completas
1. O nó pai i/2 do nó i (aceite o limite)
2. O filho esquerdo do nó i é 2i e o filho direito é 2i 1
3. O nível onde o nó i está localizado é ㏒₂i (siga o limite) 1
5. A altura de uma árvore binária completa com n nós é ㏒₂n (retirado do limite) 1
2. Estrutura de armazenamento da árvore binária
1. Armazenamento sequencial
1. Adequado para árvores binárias completas e árvores binárias completas
2. Geralmente, alguns nós vazios que não existem são adicionados à árvore binária.
3. Nota: Somente iniciando o armazenamento a partir do subscrito 1 da matriz as propriedades acima podem ser satisfeitas.
É fácil ignorar ao escrever um programa
4. Distinguir entre armazenamento sequencial de árvores e árvores binárias
1. Na árvore: o subscrito da matriz é o número do nó e o conteúdo acima do subscrito indica o relacionamento entre os nós.
2. Em uma árvore binária: o subscrito representa tanto o número do nó quanto o relacionamento entre os nós.
2. Armazenamento em cadeia
1. A lista vinculada binária possui três campos: dados, lchild, rchild
2. Uma lista vinculada binária com n nós possui n 1 campos de link vazios (o nó raiz não usa um ponteiro) para formar uma lista vinculada de dicas.
3. Travessia de árvore binária e árvore binária de dicas
1. Travessia de árvore binária
1. Passagem de pré-encomenda
2. Percurso em ordem
3. Travessia pós-pedido
Ordem refere-se a quando o nó raiz é visitado
4. Conversão de algoritmos recursivos e algoritmos não recursivos (ordem intermediária)
1. Pensamentos
1. Primeiro, verifique todos os nós esquerdos do nó raiz (não visitado) e coloque-os na pilha, um por um.
2. Retire um nó da pilha (sem filho restante ou já visitado) e acesse-o
3. Digitalize seu filho direito e coloque-o na pilha
4. Em seguida, verifique todos os nós esquerdos do filho direito e coloque-os na pilha, um por um.
5. Continue assim até que a pilha esteja vazia
2. Implementação de algoritmo
3. A eficiência de execução de algoritmos não recursivos é maior do que a de algoritmos recursivos
5. Passagem de nível (fila)
1. Pensamentos
1. Primeiro coloque o nó raiz na fila, depois retire-o da fila e acesse o nó.
2. Se houver uma subárvore esquerda, adicione o nó raiz da subárvore esquerda à fila
3. Se houver uma subárvore direita, adicione o nó raiz da subárvore direita à fila.
4. Em seguida, retire da fila e visite o nó de retirada da fila
5. Repita até que a fila esteja vazia
2. Implementação de algoritmo
6. Construa uma árvore binária a partir da sequência de travessia
1. Pré-encomenda e pedido intermediário
1. Em pré-encomenda: o primeiro é o nó raiz
2. Em ordem: o nó raiz é dividido em duas subsequências, a subárvore frontal esquerda e a subárvore posterior direita.
3. Na pré-ordem: Encontre duas subsequências, e o primeiro nó de cada uma também é o nó raiz.
2. Pós-pedido e pedido intermediário
O último nó na pós-ordem é equivalente ao primeiro nó na pré-ordem
3. O primeiro pedido e o último pedido não são permitidos
2. Clue árvore binária
1. Conceitos básicos
1. Objetivo: Agilizar a busca por predecessores e sucessores de nós
2. Regulamentos
1. Se não houver subárvore esquerda, deixe lchild apontar para o nó predecessor; se não houver subárvore direita, deixe rchild apontar para o nó sucessor;
O antecessor e o sucessor são determinados pelo método de travessia específico.
2. Adicione dois campos de sinalização para indicar se o ponteiro atual se refere ao predecessor (1) ou ao filho esquerdo (0)
3.Pista: Indicadores para antecessores e sucessores
4. Threading: O processo de percorrer uma árvore binária em uma determinada ordem para transformá-la em uma árvore binária encadeada.
2.Construção
1. A essência da pista
1. Percorra a árvore binária uma vez e verifique se os campos de ponteiro esquerdo e direito do nó estão vazios. Se estiverem vazios, altere-os para apontar para as pistas predecessoras e sucessoras.
2. Na sequência de travessia em ordem: o primeiro nó é o nó mais à esquerda e o último nó é o nó mais à direita.
3. Nó precursor
1. O ponteiro esquerdo é a pista e o nó apontado é o nó predecessor.
2. O ponteiro esquerdo é o filho esquerdo e o nó mais à direita de sua subárvore esquerda é o nó predecessor.
4. Nó sucessor
1. O ponteiro direito é a pista e o nó apontado é o nó sucessor.
2. O ponteiro direito é o filho direito e o nó mais à esquerda de sua subárvore direita é o nó sucessor.
2. Implementação de travessia em ordem encadeada
3. Às vezes, um nó principal também é adicionado à lista vinculada de dicas para formar uma lista vinculada de dicas bidirecional.
1.lchild aponta para o nó raiz, rchild aponta para o último nó da travessia em ordem
2. Travessia em ordem, o primeiro nó lchild e o último nó rchild apontam para o nó principal
3. Atravessar
1. Um algoritmo não recursivo para travessia de árvores binárias pode ser implementado usando árvores binárias de pistas.
1. Primeiro nó Firstnode (nó mais à esquerda) na ordem intermediária
2. O nó sucessor Nextnode na ordem intermediária
2. Implementação de algoritmo
4.Árvore, floresta
1. Estrutura de armazenamento de árvores
1. Expressão dos pais
1. Definição: armazenamento em espaço contínuo, cada nó adiciona um pseudoponteiro para indicar a posição dos pais na matriz, o subscrito do nó raiz é 0 e seu pseudoponteiro é -1
2. Características: Os pais podem ser obtidos rapidamente, mas a criança deve percorrer toda a estrutura.
2. Representação infantil
1. Definição: Conecte os filhos de cada nó em uma estrutura linear usando uma única lista vinculada
2. Características: É conveniente perguntar pelos filhos, mas inconveniente perguntar pelos pais.
3. Notação dos irmãos dos filhos (filho esquerdo, irmão direito)
1. Definição: O ponteiro esquerdo aponta para o primeiro filho, o ponteiro direito aponta para o primeiro irmão e a lista vinculada binária é usada como estrutura de armazenamento
2. Vantagens: Conveniente para converter árvore em árvore binária, fácil de encontrar filhos
3. Desvantagens: É difícil encontrar os pais. Será conveniente adicionar os pais para apontar para os pais.
2. Conversão de árvores, florestas e árvores binárias
1. Converta a árvore em uma árvore binária
O ponteiro esquerdo aponta para o primeiro filho, o ponteiro direito aponta para o primeiro irmão, a raiz não tem irmãos e a árvore binária não tem subárvore direita.
2. Converta floresta em árvore binária
A raiz de cada árvore binária serve como subárvore direita da árvore binária anterior.
3. Converta árvore binária em floresta (único)
1. A raiz e a subárvore esquerda da árvore binária são usadas como a forma de árvore binária da primeira árvore e depois convertidas em uma árvore (o filho direito se torna um irmão)
2. A subárvore direita da raiz e seu filho esquerdo servem como a segunda árvore, e o filho direito serve como a terceira árvore, e assim por diante.
3. Travessia de árvores e florestas
1. Primeiro percurso pela raiz da árvore
Visite a raiz primeiro e, em seguida, percorra cada subárvore da esquerda para a direita, o que é o mesmo que percorrer a raiz da árvore binária correspondente.
2. Travessia da raiz posterior da árvore
Percorra cada subárvore da esquerda para a direita e, em seguida, visite a raiz, que é igual à travessia da raiz intermediária da árvore binária correspondente.
3. Pré-encomenda de travessia da floresta
O mesmo que a travessia pela raiz de uma árvore binária
4. Travessia ordenada da floresta
Igual ao percurso raiz na árvore binária
4. Aplicação de árvores – busca de união
1.3 operações
1.Union(S,Root1,Root2): Mesclar duas subcoleções e conectar root Root2 a root Root1
S[Raiz2]=Raiz1
2.Find(S,x): Encontre a raiz da árvore que contém x até que um número negativo seja encontrado
enquanto(s[x]>=0) x=S[x]; retornar x;
3.Inital(s): Cada elemento do conjunto S é inicializado como um subconjunto com apenas um único elemento (todos os elementos recebem um valor de -1)
2. Estrutura de armazenamento: representação pai da árvore, o subscrito do nó raiz é o nome do subconjunto, o nó pai do nó raiz é um número negativo e o tamanho é o número de nós do subconjunto
5. Aplicação de árvores e árvores binárias
1. Árvore de classificação binária (árvore de pesquisa binária BST)
1.Definição
1. As chaves de todos os nós na subárvore esquerda são menores que o nó raiz
2. As palavras-chave de todos os nós na subárvore direita são maiores que o nó raiz
3. As subárvores esquerda e direita são, cada uma, uma árvore de classificação binária.
A travessia em ordem pode obter sequência ordenada crescente
2. Encontre
1. Implementação não recursiva, a recursão é simples, mas ineficiente
3.Inserir
1. O novo nó inserido deve ser um nó folha (só será inserido quando a árvore estiver vazia)
4.Construção
1. Mesmo que os elementos inseridos sejam iguais, mas em ordens diferentes, o BST construído será diferente.
5.Excluir
1. Nó folha: exclua diretamente
2.i tem apenas uma subárvore esquerda/direita: deixe a subárvore de i se tornar a subárvore do nó pai de i, substituindo a posição de i
3.i tem duas subárvores à esquerda e à direita: substitua i pelo sucessor/predecessor direto de i, em seguida, exclua o sucessor/predecessor direto e converta para o caso 1,2
6. Análise de eficiência de pesquisa
1. Comprimento médio de pesquisa ASL = (número de cada camada * número de camadas correspondentes) / número total
2. Pior caso: semelhante à lista vinculada simples ordenada O (n)
3. Melhor caso: árvore binária balanceada O(㏒₂n)
4. Processo de pesquisa: semelhante à pesquisa binária, mas a árvore de decisão da pesquisa binária é única
2. Árvore binária balanceada (árvore AVL)
1.Definição
1. Árvore binária balanceada: O valor absoluto da diferença de altura entre as subárvores esquerda e direita de qualquer nó não excede 1
2. Fator de equilíbrio: A diferença de altura entre as subárvores esquerda e direita do nó -1,0,1
2. Insira (insira primeiro e depois ajuste)
1. O objeto de cada ajuste é a subárvore desbalanceada mínima
2. rotação balanceada LL (rotação única direita)
0.A é o nó raiz da subárvore desbalanceada mínima. Certifique-se de encontrar A claramente.
1. Motivo: Um novo nó (pode ser esquerdo ou direito) é inserido na subárvore esquerda L de B, o filho esquerdo de A, e a subárvore com A como raiz está desequilibrada.
2. Método
1. Gire o filho esquerdo B de A para cima, para a direita e substitua A como o nó raiz.
2.A gira para baixo para a direita e se torna o nó raiz da subárvore direita de B.
3. A subárvore direita original de B é usada como a subárvore esquerda de A
3.RR rotação equilibrada (rotação única esquerda)
4.Rotação balanceada LR (rotação dupla primeiro para a esquerda e depois para a direita)
1. Motivo: um novo nó (pode ser esquerdo ou direito) é inserido na subárvore direita c do filho esquerdo B de A, e a subárvore com A como raiz está desequilibrada.
2. Método
1. Gire o nó raiz c da subárvore direita do filho esquerdo B de A para a esquerda e para cima até a posição do nó B.
2. Em seguida, gire o nó c para cima, para a direita, e eleve-o até a posição do nó A.
5.RL rotação equilibrada (rotação dupla direita e depois esquerda)
3. Encontre
1. A profundidade máxima de uma árvore binária balanceada contendo n nós é O(㏒₂n), e o comprimento da pesquisa balanceada é O(㏒₂n)
3. Árvore de Huffman e codificação de Huffman
1.Definição
1. O comprimento do caminho ponderado (WPL) do nó
O produto do comprimento do caminho (número de arestas) do nó raiz a qualquer nó e o peso do nó
2. Comprimento ponderado do caminho da árvore
A soma dos comprimentos de caminho ponderados de todos os nós folha
3. Árvore Huffman (árvore binária ideal)
Árvore binária com comprimento mínimo de caminho ponderado
2.Construção
1. Processo de construção
1. Selecione os dois nós com os menores pesos para construir um novo nó. O peso é a soma dos dois nós.
2. Em seguida, selecione o nó restante com o menor peso, construa-o com o novo nó e repita o processo
2.Recursos
1. Os nós iniciais são todos nós folha. Quanto menor o peso, maior o comprimento do caminho até o nó raiz.
2. Crie n-1 novos nós, um total de 2n-1 nós
3. Não existe nó com grau 1
3. Codificação de Huffman
1. Codificação de comprimento fixo
Use uma representação binária do mesmo comprimento para cada caractere
2. Codificação de comprimento variável
Use bits binários de comprimento desigual para representar caracteres diferentes
3. Codificação de prefixo
Nenhuma codificação é um prefixo de outra codificação
4. Processo de codificação Huffman
A sequência marcada no caminho do nó raiz até o personagem, 0 vai para o filho esquerdo, 1 vai para o filho direito
Imagem do Capítulo 5
1. Conceitos básicos de gráficos
1. Definição de gráfico
0.G=(V,E),V(G): Conjunto finito não vazio de vértices E(G): Conjunto de arestas |V|: Número de vértices (ordem do gráfico) |E|: Número de arestas
0.1 Nota: A tabela linear pode ser uma tabela vazia e a árvore pode ser uma árvore vazia, mas o gráfico não pode ser um gráfico vazio: o conjunto de vértices deve ser não vazio e o conjunto de arestas pode ser vazio.
1. Gráfico direcionado
<v,w>: arco de v a w (v é adjacente a w/w é adjacente a v) v: cauda do arco w: cabeça do arco
2. Gráfico não direcionado
(v,c)=(c,v)
3. Diagrama simples
Não há arestas duplicadas e não há arestas do vértice para ele mesmo.
4. Vários gráficos
Existem arestas duplicadas e existem arestas do vértice até ele mesmo.
5. Gráfico completo (gráfico completo simples)
1. Grafo completo não direcionado: Existem n(n-1)/2 arestas entre quaisquer dois vértices.
2. Grafo completo direcionado: quaisquer dois vértices possuem dois arcos em direções opostas, n(n-1)
6. Subimagem
Gerar subgrafo: subgrafo com o mesmo conjunto de vértices
7. Gráfico conectado, conectado, componentes conectados (gráfico não direcionado)
1. Subgrafo maximamente conectado (componente conectado): Um subgrafo conectado contém todas as arestas, não necessariamente todos os vértices (não necessariamente um gráfico conectado)
2. Subgrafo minimamente conectado: um subgrafo que mantém a conectividade do gráfico enquanto minimiza o número de arestas (pode ser um único vértice)
Mínimo, máximo em relação ao lado
8. Gráfico fortemente conectado, componente fortemente conectado (gráfico direcionado)
9. Abrangendo árvore, abrangendo floresta
1. Árvore geradora de um grafo conectado; um subgrafo conectado mínimo contendo todos os vértices (n vértices têm n-1 arestas)
2. Em um grafo não conectado, a árvore geradora de componentes conectados constitui a floresta geradora do grafo não conectado.
10. Grau de vértice, grau de entrada, grau de saída
1. Grau de um vértice: o número de arestas com o vértice como ponto final
1. Grau do nó
O número de nós filhos de um nó
2. Em um gráfico não direcionado: a soma dos graus de todos os vértices = número de arestas * 2
3. Em um gráfico direcionado: o grau de um vértice = grau de entrada e grau de saída, a soma dos graus de entrada de todos os vértices = a soma dos graus de saída = o número de arestas
11. Lado direito, rede
1. Imagem ponderada (líquida): uma imagem com pesos nas laterais
12. Gráfico denso, gráfico esparso
13. Caminho, comprimento do caminho, loop
1. Loop/Loop: O caminho onde o primeiro vértice e o último vértice são iguais
14. Caminho simples, loop simples
1. Caminho simples: um caminho no qual os vértices não aparecem repetidamente
2. Loop simples: Exceto o primeiro vértice e o último vértice, os outros vértices não aparecem repetidamente.
15. Distância
1. Se o caminho mais curto de v a w existir, é uma distância. Se não existir, é registrado como infinito.
16. Árvore direcionada
1. Um gráfico direcionado no qual o grau de entrada de um vértice é 0 e o grau de entrada dos outros vértices é 1.
2. Armazenamento de imagens e operações básicas
1. Método da matriz de adjacência (sequencial)
1.Definição
1. Uma matriz unidimensional armazena informações de vértice e uma matriz bidimensional armazena informações de borda.
2.Recursos
1. Gráfico não direcionado/gráfico direcionado: O número de elementos diferentes de zero na i-ésima linha é o grau/grau externo do i-ésimo vértice
2. É fácil determinar se existem arestas, mas é difícil determinar quantas arestas existem.
3. Gráficos densos são adequados para usar matrizes de adjacência
4.Aⁿ[i][j]: O número de caminhos de comprimento n do vértice i ao vértice j
2. Método de lista de adjacências (link)
1.Definição
1. Combine armazenamento sequencial e vinculado para criar uma lista vinculada individualmente para cada vértice i
2. Tabela de vértices: ponteiro do campo de vértice (dados) para a primeira lista de adjacências (primeiro arco)
3. Tabela de borda: Campo de ponto de adjacência (adjvex) Campo de ponteiro apontando para a próxima lista de adjacência (nextarc)
2.Recursos
1. Gráfico não direcionado: espaço de armazenamento O(|V| 2|E|) gráfico direcionado: O(|V| |E|)
2. Use o método de lista de adjacências para economizar espaço em gráficos esparsos
3. Lista vinculada cruzada (gráfico direcionado)
1.Definição: Um armazenamento em cadeia de gráfico direcionado
2. Estrutura
1. ArcNode: 5 domínios
1. Domínio da cauda (tailvex), domínio da cabeça (headvex): indica a cauda do arco e a cabeça do arco
2. Domínio da cadeia hlink, tlink: indica o próximo arco com a mesma cabeça/cauda do arco
<v,w>: arco de v a w (v é adjacente a w/w é adjacente a v) v: cauda do arco w: cabeça do arco
Campo 3.info: informações relacionadas ao arco
2. Ponteiro de vértice (VNode): 3 campos
1. campo de dados: informações de dados do vértice (nome do vértice)
2. Domínio firstin, domínio firstout: considere este vértice como o primeiro nó da cabeça/cauda do arco
3. Nota: os nós do vértice são armazenados sequencialmente
3.Recursos
1. É fácil encontrar o arco com vi como cauda e o arco com vi como cabeça. É fácil encontrar o grau de saída/entrada do vértice.
2. Significa que não é único, mas determina um gráfico.
4. Lista múltipla de adjacência (gráfico não direcionado)
1.Definição: Outro armazenamento em cadeia de gráfico não direcionado
2. Estrutura
1. Cada aresta é representada por um nó
1. campo de sinalização de marca: se esta borda foi pesquisada
2.ivex,jvex: as posições dos dois vértices anexados à aresta no gráfico
3.ilink,jlink: aponta para a próxima aresta anexada ao vértice ivex/jvex
4.info: campo ponteiro para diversas informações
2. O vértice é representado por um nó
1.campo de dados: informações relacionadas de vértices
2.domínio firstedge: a primeira aresta anexada ao vértice
3.Recursos
1. As arestas anexadas ao mesmo vértice são conectadas na mesma lista vinculada e cada nó da aresta é vinculado em duas listas vinculadas ao mesmo tempo.
2. Cada aresta possui apenas um nó
5. Operações básicas de gráficos
1. Independentemente da estrutura de armazenamento do gráfico, diferentes métodos de armazenamento têm desempenho diferente
2. Operações específicas
3. Percurso gráfico
1. Primeira pesquisa ampla (BFS)
1.Definição
Um algoritmo de passagem hierárquica semelhante a uma árvore binária, dando prioridade ao primeiro nó descoberto.
2. Pensamentos
1. Primeiro visite o vértice inicial v
2. Visite todos os vértices adjacentes não visitados de v em sequência
3. Em seguida, comece a partir desses vértices e visite todos os seus nós não visitados.
3. Descrição do algoritmo
1. Pesquisa hierárquica, acessando um lote de nós para frente, ao contrário da busca em profundidade, onde há uma situação inversa, não é recursiva
2. Use a matriz de marcas auxiliares da fila (se o vértice é visitado)
3. Implementação de algoritmo
4.Análise de desempenho
1. Complexidade do espaço: O(|V|)
Com a ajuda da fila auxiliar, os vértices são enfileirados uma vez
2. Complexidade de tempo
1. Lista de adjacências: O(|V| |E|)
2. Matriz de adjacência: O(|V|²)
A essência da travessia de um gráfico: o processo de encontrar seus pontos adjacentes para cada vértice
5.BFS resolve o problema do caminho mais curto de fonte única
5. Árvore abrangente em largura
1. Definição: Uma árvore transversal obtida durante a travessia em largura
2. Características: Único na matriz de adjacência, não único na lista de adjacência
O mesmo vale para DFS
2. Primeira pesquisa em profundidade (DFS)
1.Definição
Semelhante à travessia de pré-ordem de uma árvore, o último nó descoberto recebe prioridade.
2. Pensamentos
1. Primeiro visite o vértice inicial v
2. Visite qualquer vértice adjacente não visitado w de v
3. Em seguida, visite qualquer vértice adjacente não visitado w2 de w
4. Repita até que você não consiga mais acessar para baixo e retornar ao vértice visitado mais recentemente.
3. Descrição do algoritmo
1. Partindo de um vértice, usando forma recursiva
2. Implementação de algoritmo
4.Análise de desempenho
1. Complexidade do espaço: O(|V|)
Usando uma pilha de trabalho recursiva
2. Complexidade de tempo
1. Lista de adjacências: O(|V| |E|)
2. Matriz de adjacência: O(|V|²)
5. Árvore/floresta abrangente em profundidade (gráfico não conectado)
3. Travessia de gráfico e conectividade de gráfico
1. Gráfico não direcionado
1. Conectado: visite todos os vértices em uma travessia
2. Não conectado: visite todos os vértices de componentes conectados em uma travessia
2. Gráfico direcionado
1. Se houver um caminho do vértice inicial para cada vértice, todos os vértices poderão ser acessados, caso contrário não será possível
3. Um segundo loop for é adicionado ao algoritmo e então o ponto inicial é selecionado.
O primeiro loop for inicializa os vértices para FLASE
4. Gráfico não direcionado: O número de chamadas para BFS ou DFS = o número de componentes conectados do gráfico
4. Aplicação de diagramas
1. Árvore geradora mínima (MST)
1.Definição
A árvore geradora com a menor soma de pesos de aresta
2.Recursos
1. A forma da árvore não é única, a soma dos pesos das arestas é única
2. Número de arestas = número de vértices - 1
3. Considerações Gerais
Quando T não forma uma árvore geradora, encontre uma aresta de custo mínimo e nenhum loop será gerado após adicionar T
4. Dois algoritmos
1.Algoritmo Prim (Prim)
1. Pensamento (expandindo-se do vértice)
1. Inicialização: primeiro selecione qualquer vértice como vértice inicial
2. Loop (até que todos os vértices sejam incluídos): Em seguida selecione a aresta com menor peso entre as arestas adjacentes deste vértice e não formará um ciclo.
3. Em seguida, selecione a aresta com menor peso entre as arestas adjacentes dos dois vértices que não forma um loop.
2.Recursos
1. Complexidade de tempo: O(|V|²), não depende de |E|, adequado para gráficos com arestas densas
2.Algoritmo Kruskal (Kruskal)
1. Pensamento (aumento de peso)
1. Inicialização: primeiro inclua todos os vértices, sem arestas
2. Loop (até virar uma árvore): Selecione as arestas em ordem crescente de peso sem formar um ciclo até que n-1 arestas sejam incluídas
2.Recursos
1. Use um heap para armazenar conjuntos de arestas, com uma complexidade de tempo de O(|E|log|E|), que é adequado para gráficos com arestas esparsas e muitos vértices.
2. Caminho mais curto
1. Algoritmo Dijkstra para encontrar o caminho mais curto de uma única fonte
1. Variáveis auxiliares
1. Conjunto S: registra os vértices do caminho mais curto encontrado e o valor inicial é 0
2.dist[]: Registre o comprimento do caminho mais curto atual (atualizado continuamente) do ponto de origem v0 para outros vértices. O valor inicial é arcs[v0][i].
3.path[]: path[i] é o nó predecessor do caminho mais curto do ponto de origem até i, e seu valor pode ser rastreado até o caminho mais curto de v0 a vi.
2. Pensamentos
1. Inicialização: O conjunto S é {0}, dist[] é a distância do vértice inicial 0 a cada vértice e não há infinito. O vértice inicial 0 em path[] é -1 (sempre inalterado), a distância de 0 a outros pontos é 0 e a distância de 0 a outros pontos é infinita.
2. Selecione o ponto j com o menor valor restante em dist[]. Se dist[j] arcs[j][k]<dist[k], atualize dist[k] Adicione este ponto ao conjunto S. Se dist[k] for atualizado, deixe path[k]=j
3. Repita a operação nos pontos restantes do conjunto S até que S contenha todos os pontos
3.Recursos
1. A complexidade de tempo de uma única fonte é O(|V|²), e a de todos os pares de nós é O(|V|³)
2. O algoritmo não se aplica quando há pesos negativos nas arestas.
2. O algoritmo de Floyd encontra o caminho mais curto entre os vértices
1. Pensamentos
1. Gere recursivamente uma sequência de matriz quadrada de ordem n, começando de A﹣¹ a Aⁿ﹣¹
Sobrescrito de matriz mais parênteses
2.Inicialmente: Se houver uma aresta entre quaisquer dois vértices, o peso é considerado o caminho mais curto. Se não houver aresta, é infinito.
3. Posteriormente, adicione gradualmente o vértice k (k de 0 a n-1) ao caminho original como um vértice intermediário. Se o caminho diminuir, substitua o caminho original.
4.A(k)[i][j]: Do vértice i ao vértice j, o comprimento do caminho mais curto cujo número de nó intermediário não é maior que k
2.Recursos
1. Complexidade de tempo: O(|V|³)
2. Arestas com pesos negativos são permitidas e arestas contendo pesos negativos não podem formar um loop.
3. Aplicável a gráficos não direcionados ponderados, considerados gráficos direcionados com arestas duplas de ida e volta
3. Classificação topológica
1. Gráfico acíclico direcionado (gráfico DAG)
Não há ciclos em gráficos direcionados
2. O vértice representa a rede ativa (rede AOV)
O gráfico DAG representa um projeto, os vértices representam atividades e as arestas direcionadas <vi, vj> representam que a atividade i deve preceder a atividade j
3. Classificação topológica (no gráfico DAG)
1.Definição
1. Cada vértice aparece apenas uma vez
2. Se A estiver na frente de B, não há caminho de B para A.
2. Método de implementação
1. Selecione um vértice sem antecessor no gráfico DAG e produza-o
2. Exclua o vértice e todas as arestas direcionadas a partir dele
3. Repita os passos 1 e 2 até que o gráfico esteja vazio/não haja nenhum nó sem antecessor (deve haver um ciclo no gráfico)
3.Recursos
1. Complexidade de tempo O(|V| |E|)
Saída de vértices ao remover arestas
4.Atenção
1. O projeto pode começar a partir de um vértice com indegree 0
2. Um vértice possui múltiplos sucessores diretos e o resultado geralmente não é único.
3. A matriz de adjacência é uma matriz triangular e há classificação topológica, mas não necessariamente vice-versa. Os números dos vértices podem ser reorganizados de acordo com os resultados da classificação, e a matriz de adjacência é uma matriz triangular.
4. Caminho crítico
1. Use arestas para representar redes ativas (rede AOE)
1.Definição
Os vértices representam eventos, as arestas direcionadas representam atividades e os pesos representam custos (tempo)
2. Duas propriedades
1. Após a ocorrência do evento representado pelo vértice, as atividades representadas pelas arestas direcionadas a partir do vértice podem começar.
2. Somente quando todas as atividades representadas por arestas direcionadas entrando em um determinado vértice terminam, o evento representado pelo vértice pode ocorrer.
2. Vários conceitos
1. Vértice inicial (ponto de origem): Existe apenas um vértice com grau 0, o início de todo o projeto
2. Vértice final (sink): Existe apenas um vértice com grau de saída 0, que é o final de todo o projeto.
3. Caminho crítico: o caminho com o comprimento máximo
4. Atividades Críticas: Atividades no caminho crítico
5. Tempo mínimo: comprimento do caminho crítico
3. Vários parâmetros
1. O primeiro tempo de ocorrência Ve(k) do evento vk
1. Definição: O maior comprimento do caminho do vértice V a Vk determina o horário de início mais precoce de todas as atividades começando em Vk
2. Método de localização: adicione pesos do ponto de origem para trás e obtenha o valor máximo de diferentes caminhos.
Todas as atividades devem ser concluídas antes do início do evento. Obtenha o valor máximo.
2. O último horário de ocorrência Vl(k) do evento vk
1. Definição: O último horário em que esse horário ocorrerá sem atrasar a conclusão de todo o projeto
2. Como encontrá-lo: Vl (ponto de afundamento) = Ve (ponto de afundamento), subtraia os pesos do ponto de afundamento para frente e tome o valor mínimo de diferentes caminhos
Pegue o valor mínimo para garantir que todo o projeto não sofrerá atrasos.
3. O primeiro momento de ocorrência e(i) da atividade ai
1. Definição: O primeiro horário de ocorrência do evento representado pelo ponto inicial da atividade
2. Como encontrar: <Vk, Vj> representa a atividade ai, então e(i)=Ve(k)
4. O último horário de ocorrência l(i) da atividade ai
1. Definição: A diferença entre o último horário de ocorrência do evento representado pelo ponto final da atividade e o tempo necessário para a atividade
2. Como encontrar: <Vk,Vj> representa a atividade ai,l(i)=Vl(j)-Peso(Vk,Vj)
5. A diferença nas atividades d(i)=l(i)-e(i)
4. Caminho crítico
As atividades com diferença d()=0 entre todas as atividades constituem o caminho crítico
Capítulo 6 Pesquisa
1. Conceitos básicos de pesquisa
1. Tabela de pesquisa (estrutura de pesquisa): coleta de dados usada para pesquisa
2. Adequado para tabelas de pesquisa estáticas: pesquisa sequencial, meia pesquisa, pesquisa de hash
3. Adequado para tabelas de pesquisa dinâmicas: árvores de classificação binária, pesquisa de hash, árvores binárias balanceadas e árvores B são melhorias nas árvores de classificação binária.
4. Comprimento médio de pesquisa (ASL)
2. Pesquisa sequencial e pesquisa binária
1. Pesquisa sequencial (pesquisa linear)
1. Pesquisa sequencial de tabelas lineares gerais
1. Características do algoritmo
1. Introduza a sentinela (o primeiro elemento da matriz) e pesquise de trás para frente. Não há necessidade de julgar se a matriz cruzará o limite, o que melhora a eficiência do programa.
2. Vantagens e Desvantagens
1. Desvantagens: Quando n é grande, a eficiência é baixa
2. Vantagens: Não há requisitos para o armazenamento de elementos de dados e nem requisitos de ordem.
3.Desempenho
1.Sucesso ASL=(n 1)/2
2.ASL falhou=n 1
adicione uma sentinela
2. Pesquisa sequencial em lista ordenada
1. Árvore de decisão: nós circulares são nós de existência, nós retangulares são nós de falha (intervalo), n sucessos devem ter n 1 nós de falha
2. O comprimento da pesquisa para alcançar o nó com falha = o número de camadas de um nó circular acima dele
3. Apenas a falha ASL é diferente = (1 2 ... n n)/n 1
Os dois últimos nós com falha estão no mesmo nível, ambos são n
2. Meia pesquisa (pesquisa binária)
1. Características do algoritmo
1. Condição do loop: baixo≤alto garante que todos apontem para o mesmo valor no final, caso contrário, haverá um número a menos para pesquisar.
2.mid=(low high)/2 é equivalente a remover os limites
2.Desempenho
1. Complexidade de tempo: O(log₂n)
2.ASL: Número de camadas por camada * número de nós por camada / número de pontos de resumo, n camada tem 2ⁿ﹣¹ nós
3. Pesquisa de bloco (pesquisa de ordem de índice)
1. Características do algoritmo
1. Absorvem as respectivas vantagens da pesquisa sequencial e da pesquisa binária, possuem uma estrutura dinâmica e são adequadas para pesquisa rápida.
2. Pensamentos
1. Divididos em vários subblocos, os blocos podem ser desordenados e os blocos podem ser ordenados.
2. A maior palavra-chave no primeiro bloco <todos os registros no segundo bloco e assim por diante
3. Crie uma tabela de índice contendo a maior palavra-chave de cada bloco e o endereço do primeiro elemento de cada bloco, organizados em ordem por palavra-chave
3. Processo de pesquisa
1. Determine o bloco na tabela de índices e pesquise sequencialmente/pela metade
2. Pesquise sequencialmente dentro do bloco
4.Desempenho
ASL = tabela de índice ASL intra-bloco ASL
Resumo da pergunta
1. Sujeito a erros
1. A velocidade da meia pesquisa agora é geralmente mais rápida. Em casos especiais, a pesquisa sequencial pode ser mais rápida.
2. Desempenho temporal da pesquisa binária e da árvore de classificação binária
1. Metade da pesquisa é medida por uma árvore de decisão binária e ASL é sempre O (log₂n)
2. A árvore de classificação binária está relacionada à ordem de entrada dos dados, e o pior caso é O(n)
3. Ao pesquisar pela metade, o valor do meio é limitado
2.Fórmula
1. A altura da árvore de decisão binária: ┎log₂(n 1)┒ ou ┕log₂n┙ 1
1. É uma árvore binária balanceada, com diferenças de altura de no máximo 1, ou uma árvore de classificação binária?
2. O número de comparações de nós malsucedidos (a diferença não excede 1)/o número máximo de comparações
3. Número total de nós n=2^h-1
2. O comprimento ideal do bloco da tabela de sequência de índice de n registros:
Todos são pesquisados sequencialmente, o comprimento do bloco é b, a tabela de índice ASL=(n/b 1)/2, o intra-bloco ASL=(b 1)/2, e a desigualdade básica é usada para adição
3. Pesquisa sequencial ASL=(n 1)/2, pesquisa de índice ASL=tabela de índice ASL intra-bloco ASL
3. Tipo de pergunta
1. Determine se uma árvore é uma árvore de decisão de pesquisa binária
Pegue o último nó a ser comparado (a posição intermediária da árvore) e determine se os limites superior e inferior são consistentes (você também pode determinar primeiro os limites superior e inferior do nó raiz)
2. Use uma ideia semelhante para bloquear a pesquisa diretamente na lista ordenada: W252
O comprimento da pesquisa dentro de um bloco é diferente para cada segmento
4.Pontos de conhecimento
Método de pesquisa de 1.k pontos: A complexidade de tempo de sucesso e falha é O (logk (n))
A profundidade de uma árvore k-ária com n nós é ┕logk(n)┙ 1
2. Quando as probabilidades de pesquisa são diferentes, a forma mais eficaz é usar a pesquisa sequencial
Classifique em ordem decrescente de probabilidade de pesquisa
3. Árvore B e árvore B
1.Árvore B e suas operações básicas
1.Definição
0.B-tree (uma árvore de pesquisa balanceada de múltiplos caminhos com um fator de equilíbrio de 0 para todos os nós), o número máximo de nós filhos é a ordem da árvore B (m)
1. Cada nó possui no máximo m subárvores (no máximo m-1 palavras-chave)
2. Se o nó raiz não for um nó terminal, existem pelo menos duas subárvores e 1 palavra-chave
3. Todos os nós não-folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores e pelo menos ┎m/2┒-1 palavras-chave.
4. Todas as estruturas de nós não-folha
1. As palavras-chave são organizadas em ordem crescente
2. Todos os números na subárvore esquerda <correspondem à palavra-chave, todos os números na subárvore direita> correspondem à palavra-chave
5. Todos os nós folha estão no mesmo nível, sem informações (nós externos/nós com falha)
2.A altura da árvore B
1. Altura mínima
Cada nó possui no máximo m subárvores e m-1 palavras-chave
h≥logm(n 1) n≤(m-1)(1 m m² ... m^(h-1))=m^h-1
2. Altura máxima
A primeira camada tem pelo menos um nó, a segunda camada tem pelo menos 2 nós, a terceira camada tem pelo menos 2┎m/2┒,..., e a h 1ª camada tem pelo menos 2┎m/2┒^ (h-1) nós.
A h1ª camada é um nó folha (nó de falha), o número é n 1 (número de intervalos) e existem n-1 nós de falha para n palavras-chave.
n 1≥2┎m/2┒^(h-1)
Pesquisa em árvore 3.B
Semelhante a uma árvore de pesquisa binária
4.Inserção na árvore B
1. Posicionamento: deve ser inserido em um nó não folha no nível mais baixo
2.Inserir
1. O número de palavras-chave para cada nó sem falha está dentro de [┎m/2┒-1,m-1]
2. Se o número de palavras-chave após a inserção for <m, insira diretamente >m-1, divida o nó;
3. Método de divisão
1. Divida o nó original após inserir a chave em duas partes a partir da posição intermediária ┎m/2┒
2. O nó na posição intermediária ┎m/2┒ é inserido no nó pai e as partes esquerda e direita são usadas como subárvores esquerda e direita.
3. Se o nó pai também exceder o limite superior, continue a dividir até atingir o nó raiz. A altura da árvore B é 1.
5. Exclusão da árvore B
1. No nó terminal
1. Exclua palavras-chave diretamente
Número de palavras-chave>┎m/2┒-1
2. Irmãos bastam
1. O número de palavras-chave = ┎m/2┒-1, e as palavras-chave dos nós irmãos adjacentes à direita (esquerda) são >┎m/2┒
2. Método de transposição pai-filho: um dos nós pais entra no nó excluído e um dos nós irmãos entra no nó pai.
3. Não há irmãos suficientes para emprestar (método de fusão)
1. O número de palavras-chave = ┎m/2┒-1, e as palavras-chave dos nós irmãos adjacentes à direita (esquerda) = ┎m/2┒-1
2. Método de mesclagem: mescla um dos nós pai com um dos nós irmãos para substituir o nó excluído. O nó pai tem uma palavra-chave a menos.
3. Se o nó pai for o nó raiz e for reduzido a 0, exclua o nó raiz diretamente e o novo nó após a fusão se tornará a raiz.
4. O nó pai não é o nó raiz e é reduzido a ┎m/2┒-2 e então ajustado ou mesclado com seus irmãos (pegue emprestado primeiro quando houver disponibilidade suficiente)
2. Não no nó terminal
1. Se o número de palavras-chave na subárvore esquerda >┎m/2┒-1, substitua k pelo nó predecessor de k (o nó mais à direita da subárvore esquerda) e, em seguida, exclua k recursivamente
2. Se o número de palavras-chave na subárvore direita >┎m/2┒-1, substitua k pelo nó sucessor de k (o nó mais à esquerda da subárvore direita) e, em seguida, exclua k recursivamente
3. Se o número de palavras-chave nas subárvores esquerda e direita = ┎m/2┒-1, mescle diretamente as duas subárvores e exclua k diretamente
2. Conceito básico de árvore B
1.Definição
1. Cada nó de ramificação possui no máximo m subárvores (nós filhos)
2. O nó raiz não folha tem pelo menos duas subárvores, e todos os nós não folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores
3. O número de subárvores de um nó = o número de palavras-chave
Na árvore B: o número de subárvores de um nó = o número de palavras-chave 1
4. Todos os nós folha contêm todas as palavras-chave (organizadas em ordem) e ponteiros para os registros correspondentes, e os nós folha adjacentes são vinculados entre si de acordo com o tamanho.
5. Todos os nós de ramificação (índices que podem ser considerados índices) contêm apenas o valor máximo das palavras-chave em cada um de seus nós filhos e ponteiros para os nós filhos.
2.Recursos
1. Dois ponteiros principais: um aponta para o nó raiz e o outro aponta para o nó folha com a menor palavra-chave
2. Duas operações de pesquisa: pesquisa a partir da ordem mínima de palavras-chave/pesquisa multidirecional a partir do nó raiz
3. Nota: Ao pesquisar, a pesquisa não termina quando o nó não folha é igual ao valor fornecido. A pesquisa continua descendente até o nó folha. Independentemente de a pesquisa ser bem-sucedida ou não, é um caminho do nó raiz até o nó folha.
Resumo da pergunta
1. Sujeito a erros
1. Quando o número de palavras-chave em um nó ≠ o número de subárvores, não deve ser uma árvore B
2. Todos os nós não-folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores e pelo menos ┎m/2┒-1 palavras-chave.
Preste atenção especial ao nó raiz: existem pelo menos duas subárvores e 1 palavra-chave
3. Quando a árvore B é dividida após a inserção, desde que o nó raiz não seja dividido, a altura não será 1
2.Fórmula
1. Altura mínima: h≥logm(n 1)
2. Altura máxima: n 1≥2┎m/2┒^(h-1)
3.Pontos de conhecimento
1. Para uma árvore B de terceira ordem: quando o número de nós é menor, é semelhante a uma árvore binária completa; quando o número de nós é maior, é semelhante a uma árvore ternária completa;
Pontos de resumo=m^h-1
A árvore 2.B é usada para índice de arquivo/índice de banco de dados
4. Tabela hash
1. Conceitos básicos de tabelas hash
1. Função hash
A função que mapeia palavras-chave para endereços correspondentes é registrada como Hash(key)=addr (pode ser subscrito/índice/endereço de memória da matriz)
2.Conflito
Duas ou mais palavras-chave diferentes são mapeadas para o mesmo endereço
3.Sinônimos
Colisão de palavras-chave diferentes
4. Tabela hash
Uma estrutura de dados que é acessada diretamente com base em palavras-chave, de preferência O(1)
2. Método de construção da função hash
0. Pontos de atenção
1. O domínio de definição deve conter todas as palavras-chave e o intervalo de valores depende do tamanho/intervalo de endereços da tabela hash
2. Os endereços devem ser igualmente prováveis e distribuídos uniformemente.
3. Torne a função o mais simples possível e calcule-a em pouco tempo
1. Método de endereçamento direto
1. Função: H(chave)=a*chave b
2. Recursos: Sem conflito, adequado para distribuição basicamente contínua de palavras-chave
2. Método de divisão com resto
1. Função: H(chave)=chave%p
2. Seleção de P: O número primo p que não é maior que m (comprimento da tabela hash), mas mais próximo ou igual a m
3. Método de análise digital
1. Selecione um número de bits com uma distribuição digital relativamente uniforme como endereço hash
2. Recursos: Adequado para coleções de palavras-chave conhecidas
4.Método para encontrar o meio do quadrado
1. Os dígitos do meio do valor quadrado são usados como endereço hash
2. Aplicável a situações em que os valores de cada bit não são suficientemente uniformes/são inferiores ao número de bits necessários para o endereço hash.
5. Método de dobramento
1. Divida a palavra-chave em várias partes com o mesmo número de dígitos e tome a soma da superposição como endereço hash.
2. Adequado para um grande número de dígitos e os dígitos em cada bit são distribuídos de maneira aproximadamente uniforme.
3. Maneiras de lidar com conflitos
1. Lei de endereço aberto
0.Definição
1. Endereços gratuitos estão abertos a sinônimos e não sinônimos
2. Fórmula de recursão: Hi=[H(key) di]%m, di: sequência incremental
1. Método de detecção linear
1.Definição: di=0,1,2,...,m-1
2. Recursos: Faz com que um grande número de elementos se reúna em endereços hash adjacentes, reduzindo a eficiência da pesquisa.
2. Método de detecção quadrada (método de detecção secundário)
1. Definição: di=0²,1²,-1²,2²,-2²,...,k²,-k²
2.Recursos
1. Vantagens: Pode evitar problemas de acumulação
2. Desvantagem: Apenas metade das células pode ser detectada
3. Método de rehashing (método de hash duplo)
1. Definição: di=Hash₂(chave), Hi=[H(chave) i*Hash₂(chave)]%m
eu é o número de conflitos
2.Recursos
1. Use a segunda função hash para calcular o incremento de endereço
2. Todas as posições podem ser detectadas até m-1 vezes
4. Método de sequência pseudo-aleatória
1.Definição: di=sequência pseudoaleatória
5.Atenção
1. Você não pode excluir fisicamente os elementos existentes à vontade, pois isso truncará os endereços de pesquisa de outros elementos com o mesmo endereço hash.
2. Pode ser marcado para exclusão e exclusão lógica
3. Efeitos colaterais: Após múltiplas exclusões, a tabela hash parece estar muito cheia, mas na verdade ainda existem muitos locais não utilizados e requerem manutenção regular.
2. Método Zipper (método link)
1. Definição: Todos os sinônimos são armazenados em uma lista linear vinculada, identificada exclusivamente por um endereço hash
2. Adequado para situações frequentes de inserção e exclusão e pode ser excluído fisicamente diretamente
4. Pesquisa de hash e análise de desempenho
1. Processo de pesquisa
0.Inicialização: Addr=Hash(chave)
1. Verifique se existe um registro no Addr
1. Sem registro, falha na pesquisa
2. Há um registro e a busca igual foi bem-sucedida, aguarde a execução 2;
2. Calcule o "próximo endereço hash" usando o método de tratamento de conflitos fornecido, defina Addr para este endereço e transfira para 1
2. Eficiência de pesquisa
1. Depende de: função hash, método de tratamento de colisões, fator de carga
2. Fator de preenchimento (α): Define o quão cheia uma tabela está
α = número de registros na tabela n/comprimento da tabela hash m
3. O comprimento médio da pesquisa depende de α e não depende diretamente de n ou m.
Resumo da pergunta
1. Sujeito a erros
1. K sinônimos são preenchidos na tabela hash usando detecção linear, que requer K (K 1)/2 vezes de detecção.
1 2...K
2. A probabilidade de conflito é proporcional ao tamanho do fator de carga
Quanto mais cheio estiver, maior será a probabilidade de conflito.
3. A função hash não pode ser construída usando uma função de número aleatório e pesquisas normais não podem ser realizadas.
2. Pontos de conhecimento
1. Causas de acumulação
Sequências de sondagem para conflitos de sinônimos e diferentes sequências de sondagem para não-sinônimos estão interligadas
2. Número médio de detecções = duração média da pesquisa
3. Tipo de pergunta
1.Sucesso ASL
Número de pesquisas = número de conflitos 1
2.ASL falhou
Determine o total de posições de pesquisa necessárias com base na função hash e pesquise cada posição até que esteja vazia, use o método de tratamento de conflito correspondente para pesquisar novamente.
5. espetos
1. Definição de string
1. String de espaço: composta por um ou mais espaços, não uma string vazia
2. As tabelas lineares usam um único elemento como objeto de operação e as strings usam substrings como objeto de operação.
2. Estrutura de armazenamento de strings
1. Representação de armazenamento sequencial de comprimento fixo
1. Semelhante ao armazenamento sequencial de tabela linear, aloque matrizes de comprimento fixo
2. Truncamento: Valores de string que excedam o comprimento predefinido serão descartados.
2. Representação de armazenamento de alocação de heap
1. Use malloc() e free() para alocar e excluir dinamicamente
3. Representação de armazenamento Blockchain
1. Armazenamento vinculado semelhante a uma lista linear, cada nó pode conter um ou mais caracteres
3. Operações básicas de strings
1. Subconjunto mínimo de operações (5): não pode ser implementado usando outras operações de string
1. Atribuição de string: StrAssigh
2. Comparação de strings: StrCompare
3. Conexão de string: Concat
4. Encontre o comprimento da string: StrLength
5. Encontre substring: SubString
4. Padrão de correspondência de strings
1.Definição: Operação de posicionamento de substring
2. Pensamentos
1. Começando pelo caractere pos da string principal, compare-o com o primeiro caractere da string padrão
2. Se forem iguais, continue a comparar os caracteres subsequentes um por um.
3. Se não for igual, inicie a comparação novamente a partir do próximo caractere da string principal.
3. Eficiência
Pior complexidade de tempo: O(mn)
5. Algoritmo de correspondência de padrões aprimorado - algoritmo KMP
1. Prefixos de string e valores correspondentes parciais
1. Prefixo: todas as substrings do cabeçalho, exceto o último caractere (só pode começar na primeira posição)
2. Sufixo: todas as substrings finais, exceto o primeiro caractere (só pode começar na última posição)
3. Valor de correspondência parcial: os comprimentos mais longos do prefixo e do sufixo são iguais
2.Eficiência
1. Complexidade de tempo: O(m n)
3. Resolva o próximo array (manual)
1.próximo valor da matriz = mesmo comprimento de prefixo e sufixo mais longo 1
2. A string em si não pode ser usada como prefixo ou sufixo.
3. Geralmente next[1]=0 (depende da questão específica, se for -1, ainda use 0 para cálculo e, finalmente, todos os números são -1)
4. Quando o i-ésimo elemento em next[i] não corresponde, o comprimento da string é i-1, excluindo o i-ésimo elemento.
5. Quando a sequência for longa, você só poderá contar as primeiras para obter a resposta.
Resumo da pergunta
1. Pontos de conhecimento
1.A maior vantagem do algoritmo KMP
A string principal não retrocede, o ponteiro i não se move, j=next[j]
2. Tipo de pergunta
1. Uma maneira rápida de resolver next[], assumindo que next[n] esteja sendo resolvido no momento, next[n-1]=m
0.Padrão próximo[1]=0, próximo[2]=1
O subscrito também pode começar em 0 e o valor numérico também pode começar em -1.
1. A string tem n-1 caracteres Se os primeiros m caracteres forem iguais aos últimos m caracteres, então next[n]=m 1, vá para 3.
2. Quando os primeiros m números são diferentes dos últimos m números, se m=1, então próximo[n]=1, vá para 3. Caso contrário, seja m=m-1, então compare o primeiro m-1 e o último m-1, se forem iguais, vá para 1, se forem diferentes, continue para 2.
3. Finalize a operação
2. Processo de correspondência KMP
Quando o valor de next[] começa em 0, o número subscrito começa em 1. Quando não há correspondência, o ponteiro i não se move, j=next[j]
3. Sujeito a erros
1. Durante o exame, você deve distinguir se o valor next[] começa em 0 ou 1
Capítulo 7 Classificação
1. Conceitos básicos de classificação
1. Definição de classificação
1. A estabilidade de um algoritmo não pode medir a qualidade de um algoritmo.
2. Classificação interna: todos os elementos são colocados na memória
3. Classificação externa: movimentação constante entre memória e memória externa
Resumo da pergunta
1. Sujeito a erros
1. O algoritmo de classificação implementado na lista de sequências não pode ser implementado na lista vinculada.
2. Se você usar métodos de classificação diferentes para classificar a mesma tabela linear, os resultados de classificação obtidos poderão ser diferentes.
2.Fórmula
1. O número mínimo de comparações para classificar quaisquer n palavras-chave é ┍log₂(n!)┑
2. Classificação por inserção
1. Classificação por inserção direta
1. Pensamentos
1. Suponha que o primeiro elemento foi classificado
2. A partir do segundo elemento, compare-o com o anterior em sequência. Se a troca imediata não for satisfeita, classifique no lugar e mova repetidamente os itens já organizados para trás.
2.Recursos
1. Copie A[0] como sentinela para evitar subscritos fora dos limites, facilitar a atribuição e eliminar a necessidade de aplicar variáveis temporárias.
2. Compare e mova-se ao mesmo tempo
3.Análise de desempenho
1. Eficiência de tempo
1. Melhor caso: O(n)
Só precisa ser comparado uma vez de cada vez, não há necessidade de se mover
2. Pior caso: O(n²)
2. Aplicabilidade
Tanto a sequência quanto a cadeia são adequadas. A maioria dos algoritmos é adequada apenas para sequência.
4. Implementação de algoritmo
2. Classificação de inserção intermediária
1. Pensamentos
1. Primeiro dobre ao meio para encontrar a posição onde o elemento será inserido.
2. Mova todos os elementos após a posição a ser inserida uniformemente
2.Recursos
1. Apenas o número de elementos de comparação foi reduzido, o número de movimentos não mudou
2. O número de comparações não tem nada a ver com o estado inicial, apenas n
3.Análise de desempenho
1. Complexidade de tempo: O(n²)
Está relacionado apenas ao número de movimentos (loop for de dois níveis) e não tem nada a ver com o número de comparações. A comparação é apenas uma operação concluída no loop for.
2. Estável
4. Implementação de algoritmo
3. Classificação de colinas (reduzindo a classificação incremental)
1. Pensamentos
1. Primeiro considere o tamanho do passo como n/2, divida-o em vários grupos e use a classificação por inserção direta em cada grupo.
2. Reduza o tamanho do passo pela metade e continue até que o tamanho do passo seja 1
2.Recursos
1. A melhor sequência incremental ainda não foi encontrada e a complexidade do tempo não pode ser calculada.
3.Análise de desempenho
1. Eficiência de tempo
Pior caso: O(n²)
2. Instável
As mesmas palavras-chave podem ser divididas em diferentes subtabelas
4. Implementação de algoritmo
Resumo da pergunta
1. Sujeito a erros
1. A complexidade de tempo da classificação de meia inserção é O (n²)
3. Classificação de troca
1. Classificação por bolha
1. Pensamentos
1. A partir do último elemento, compare os dois elementos adjacentes. Se estiverem na ordem inversa, troque-os.
2. Uma operação de bolha resultará na troca do menor elemento para a primeira posição.
3. Na próxima rodada de borbulhamento, o menor elemento determinado na rodada anterior não participará mais e a coluna a ser ordenada será reduzida em um elemento.
4. O resultado de cada bolha é que o menor elemento da sequência é colocado na posição final e até n-1 é concluído.
2.Recursos
1. A subsequência ordenada gerada pela classificação por bolha deve ser ordenada globalmente, o que é diferente da classificação por inserção direta.
3.Análise de desempenho
1. Eficiência de tempo
1. Melhor caso: O(n)
Após o borbulhamento, o sinalizador ainda é falso, não há troca de elementos e o loop é saltado diretamente.
4. Implementação de algoritmo
2. Classificação rápida (método de dividir e conquistar)
1. Pensamentos
1. Cada vez, o primeiro elemento da tabela atual é considerado o pivô base (valor do pivô) para dividir a tabela.
2.i aponta para o primeiro elemento (base), j aponta para o último elemento
3. Comece com j e encontre o primeiro elemento menor que a linha de base de trás para frente j aponta para a posição deste elemento e substitua o elemento apontado por i por este elemento.
4. A partir de i, encontre o primeiro elemento maior que a linha de base da frente para trás i aponta para a posição deste elemento e substitua o elemento apontado por j por este elemento.
5. Comece de j novamente e repita até que o contato entre i e j pare. Coloque o valor de referência na posição de contato e divida a sequência em duas partes. A frente é menor que o valor de referência e a última é maior que o valor de referência. .
6. Tome o primeiro elemento das duas subsequências como valor de referência e repita a operação.
2.Recursos
1. Nenhuma subsequência ordenada é gerada, mas um elemento será colocado na posição final após cada passagem de classificação
2. Quanto mais ordenado for o algoritmo, menor será a eficiência, e quanto mais desordenado for o algoritmo, maior será a eficiência.
3.Análise de desempenho
1. Eficiência de espaço
Caso médio: O(㏒₂n)
O algoritmo é recursivo e requer uma pilha de trabalho recursiva, cujo tamanho é igual à profundidade da árvore recursiva.
Pior caso: O (n)
2. Eficiência de tempo
1. Pior caso: O(n²)
A sequência é basicamente em ordem ou ordem inversa
2. Melhor caso (caso médio): O(n㏒₂n)
4. Instável
A palavra-chave Exchange existe
4. Maneiras de melhorar a eficiência
1. Quando a subsequência obtida pela divisão recursiva é pequena, a recursão não é mais necessária e a classificação por inserção direta é usada para o trabalho subsequente.
2. Tente escolher um benchmark que possa dividir os dados.
1. Selecione três elementos da cabeça, cauda e meio e, em seguida, escolha o valor do meio
2. Selecione benchmarks aleatoriamente para garantir que o pior cenário não ocorra
5. Implementação de algoritmo
Resumo da pergunta
1. Sujeito a erros
1. A situação mais rápida quando um grupo de números é classificado usando classificação rápida
Cada benchmark selecionado divide a tabela em duas subtabelas de comprimento semelhante.
2. Ao procurar sequências possíveis, ambas as ordens devem ser consideradas (do grande para o pequeno, do pequeno para o grande)
2. Pontos de conhecimento
1. A classificação rápida é mais adequada para armazenamento sequencial.
3. Pensamento algorítmico
1. Algoritmo para mover todos os números ímpares na frente de todos os números pares (menos tempo/espaço)
1. Primeiro encontre um número par L(i) de frente para trás, depois encontre um número ímpar L(j) de trás para frente, troque os dois e repita até i>j
2. Com base na classificação rápida, uma travessia, tempo O(n), espaço O(1)
2. Problema da bandeira holandesa: uma sequência de blocos consistindo apenas de vermelho, branco e azul, de modo que os blocos sejam organizados na ordem de vermelho, branco e azul, e o tempo seja O(n)
1. Digitalize sequencialmente, troque o vermelho para a frente e o azul para trás
2. Três ponteiros, um ponteiro de trabalho, um apontando para a cabeça, um apontando para a cauda, instrução switch
Nota: Números positivos, números negativos e 0 são classificados da mesma maneira.
3. Encontre o k-ésimo menor elemento na matriz L[1...n]
0. Você pode usar classificação direta para obter k elementos ou mais O(nlog₂n)/usar um pequeno heap superior O(n klog₂n)
1. Mais emocionante, com base na classificação rápida, o tempo é O(n)
2. Selecione um benchmark e execute a mesma operação de divisão da classificação rápida, dividida em L[1...m-1] e L[m 1...n], L(m) é o benchmark
3. Discuta a relação entre m e k
1.m=k, o benchmark é o elemento que você procura
2.m<k, o elemento que você está procurando está na segunda metade, continue a encontrar recursivamente o k-ésimo menor elemento na segunda metade
3.m>k, o elemento que você está procurando está na primeira metade, continue a encontrar recursivamente o k-ésimo menor elemento na primeira metade
4. N números constituem um conjunto A, que é dividido em dois subconjuntos disjuntos A1 e A2. Os números são n1 e n2, e a soma dos elementos é s1 e s2. Satisfaça |n1-n2| mínimo e |s1-s2|
1. Coloque os menores n/2 elementos em A1 e o restante em A2, imite a classificação rápida e processe a posição de referência i separadamente após a divisão
2. Se i=n/2, o agrupamento está concluído
3. Se i<n/2, coloque a base e todos os elementos anteriores em A1 e continue a dividir os elementos após i
4. Se i>n/2, coloque a base e todos os elementos subsequentes em A2 e continue a dividir os elementos antes de i
5. Não há necessidade de classificar todos os elementos, tempo médio O(n), espaço O(1)
4.Selecione a classificação
1. Classificação de seleção simples
1. Pensamentos
1. Encontre o menor elemento na primeira passagem e troque este elemento pelo primeiro elemento
1. Encontre o menor elemento na segunda passagem, troque este elemento pelo segundo elemento e repita n-1 vezes
2.Recursos
1. Cada passagem de classificação pode determinar a posição final de um elemento.
3.Análise de desempenho
1. A complexidade do tempo é sempre O(n²)
O número de movimentos do elemento raramente é O(n), mas o número de comparações não tem nada a ver com o estado inicial e é sempre n(n-1)/2
2. Instável
A troca direta após encontrar o menor elemento destruirá a ordem original.
4. Implementação de algoritmo
2. Classificação de pilha
1. Pensamentos
1. Definição de pilha
Heap raiz grande (árvore binária completa): o maior elemento é o nó raiz e o valor de qualquer nó não raiz é menor ou igual ao valor de seu nó pai
1.1 Operações de heap
1. Exclua o elemento superior do heap
Primeiro troque o último elemento pelo elemento superior do heap. Depois de excluí-lo, ajuste o elemento superior do heap para baixo para se tornar um heap.
2. Operação de inserção
Primeiro coloque o novo nó no final do heap e, em seguida, ajuste-o para cima no heap
2. Construa o heap inicial (heap raiz grande)
1. Faça julgamentos do último nó da penúltima camada em diante.
2. Observe apenas a subárvore do nó (não o nó pai). Se houver um nó na subárvore que seja maior que o nó raiz, encontre o maior e troque-o com o nó raiz.
3. Se o heap do próximo nível for destruído após a troca, continue usando o método acima para ajustar o heap do próximo nível até o nó raiz.
3. Produza o elemento superior (valor máximo) do heap, coloque o último elemento no topo do heap e ajuste o topo do heap para baixo para se tornar um grande heap superior.
4. Repita a operação até que reste apenas um elemento na pilha
2.Análise de desempenho
1. A complexidade do tempo é sempre O(n㏒₂n)
O tempo de construção do heap é O(n), e então há n-1 ajustes para baixo, cada vez O(h)
2. Instável
Ao construir um heap, a ordem original será interrompida.
3. Complexidade do espaço: O(1)
Use apenas um número constante de unidades auxiliares
3. Implementação de algoritmo
A classificação da seleção é instável
Resumo da pergunta
1. Perguntas clássicas
1. Cada elemento possui dois itens de dados k1 e k2. Classificar: olhe primeiro para k1, com o menor primeiro tendo o mesmo valor, depois olhe para k2, com o menor primeiro;
1. Primeiro determine a ordem de classificação que deve ser classificada primeiro, seguida por k1.
2. Não há requisitos de estabilidade para classificação k2. Tente escolher um algoritmo com alta eficiência.
3. Um algoritmo estável deve ser usado para classificar k1, caso contrário, pode interromper a classificação de k2
2. Tipo de pergunta
1. Número de comparações ao inserir/excluir elementos do heap
2. Só quero obter a sequência ordenada parcial antes do k-ésimo (k≥5) menor elemento
1. Seleção por bolha/simples/classificação de heap disponível
2. As duas primeiras vezes são conhecidas
3. Classificação de heap, o heap inicial a ser construído não excede 4n, o tempo para obter k elementos é klog₂n, um total de 4n klog₂n, ideal quando k≥5
3. Determine se uma sequência de dados é um pequeno heap raiz
1. Duas situações precisam ser divididas, a sequência é um número ímpar e um número par
2. Quando é um número ímpar: não há um único nó de ramificação, você pode comparar diretamente o nó pai com os dois nós filhos
3. Quando é um número par: existe um único nó de ramificação, que pode ser julgado separadamente, e outros nós são normais.
5. Mesclar classificação e classificação radix
1. Mesclar classificação
1. Pensamentos
1. Primeiro divida em n subtabelas com comprimento 1 e mescle-as em pares.
2. Obtenha as sublistas com comprimento 2 e mescle-as duas a duas novamente e repita
2.Análise de desempenho
1. Complexidade do espaço: O(n)
Os dados mesclados precisam ser copiados para a matriz auxiliar, o comprimento é n
2. Complexidade de tempo: O(n㏒₂n)
Cada mesclagem é O(n) e um total de n vezes é executada. A subsequência dividida não tem nada a ver com o estado inicial.
3. Implementação de algoritmo
2. Classificação de raiz
1. Pensamentos
1. Menos Significativo Primeiro (LSD)
1. Primeiro coloque a sequência em 10 filas (0 ~ 9, de cima para baixo e de baixo para fora) de acordo com o tamanho dos dígitos únicos.
2. Retire todos os elementos da primeira fila em sequência até a 10ª fila
3. Em seguida, repita a operação de entrada e saída da fila de acordo com o dígito das dezenas, e a mesma operação é feita para o dígito das centenas.
4. Quando o bit mais alto também é retirado da fila, a sequência está em ordem.
2. Primeiro o bit mais significativo (MSD)
1. Primeiro coloque a sequência em 10 filas (0 ~ 9, de cima para baixo e de baixo para fora) de acordo com o tamanho do bit mais alto.
2. Classifique as filas cujo número não seja 1 recursivamente e coloque-as novamente em 10 filas de acordo com o tamanho do próximo dígito mais alto.
3. Até que haja apenas 1 número em todas as filas, a recursão termina, colete cada fila e retorne à camada anterior
2.Recursos
1. Não baseado em comparação, adote a ideia de classificação multi-palavras-chave
3. Análise de Desempenho (LSD)
1. Complexidade espacial: O(r)
r é a base do número (qual sistema de base)
2. Complexidade de tempo: O(d(n r))
Execute d tempos de alocação e coleta. Uma alocação é O(n) e uma coleção é O(r).
3. Estável
Tanto a alocação quanto a coleta são feitas sequencialmente
Resumo da pergunta
1. Sujeito a erros
1. Qual método deve ser usado para classificar arquivos de dados de 10 TB?
Classificação por mesclagem, o arquivo é muito grande, a classificação interna não pode ser usada, apenas a classificação externa pode ser usada, geralmente a classificação por mesclagem é usada
2. Pontos de conhecimento
1. Mesclar duas listas ordenadas com n elementos cada em uma lista ordenada
1. O número mínimo de comparações é: n
2. O número máximo de comparações é: 2n-1
3. Tipo de pergunta
1. Quantas comparações de código de classificação são realizadas na classificação radix?
Fiz diversas alocações e arrecadações
6. Comparação e aplicação de vários algoritmos de classificação interna
1. Comparação de algoritmos de classificação interna
2. Aplicação do algoritmo de classificação interna (resumo)
1. Seleção de algoritmo
1.n é menor
1. O registro em si é pequeno
Inserção direta (menos comparações)/seleção simples (menos trocas)
2. O registro em si é grande
Escolha simples
1.1 Média escala (n<1000)
A classificação Hill é uma boa escolha
2. n é muito grande (escolha aquele com menos tempo)
1. Instável
1. Classificação rápida: o melhor método, com o menor tempo médio quando distribuído aleatoriamente
2. Classificação de heap: requer menos espaço auxiliar do que classificação rápida
2. Estável
Classificação por mesclagem: mas tem a maior complexidade de espaço
3.n é muito grande, o número de palavras-chave é pequeno e pode ser decomposto
A classificação Radix é melhor
4. A sequência está basicamente em ordem
Classificação por inserção direta (maior eficiência/menor número de comparações)/classificação por bolha
O melhor caso de complexidade de tempo é O (n)
5.O resultado após várias classificações
1. Coloque um elemento de cada vez na posição final
Seleção simples/classificação de heap, classificação por bolha/classificação rápida (troca)
Apenas o elemento classificado rapidamente não é o elemento mais valioso, os outros 3 são todos os mais valiosos (primeiro/último)
2. Os primeiros elementos estão em ordem, mas não a posição final
inserir diretamente
3. Talvez todos os elementos não estejam em sua posição final antes do início da última viagem.
inserir diretamente
4. Não há garantia de que haverá um elemento na posição final
Inserção direta/classificação em colina/classificação por mesclagem
6. Vários dos mais
1. Atualmente o melhor algoritmo de classificação interna em termos de desempenho médio
Ordenação rápida
2. Algoritmos que ocupam mais espaço
Mesclar classificação O (n)
Quicksort é O(n) no pior caso
3. Qual é o mais rápido quando está basicamente em ordem?
classificação por inserção direta
4. Na melhor das hipóteses, o tempo linear pode ser alcançado
Inserção direta/classificação por bolha
7.0 O tempo do algoritmo é independente da sequência inicial
Classificação por seleção (seleção simples/classificação por heap)/classificação por mesclagem/classificação por base
7.1 O número de passagens de classificação não tem nada a ver com a sequência inicial
A inserção direta/seleção simples ocorre n-1 vezes e a classificação radix é fixada em d vezes.
7.2 O número de movimentos não tem nada a ver com a sequência inicial
Classificação de raiz
A classificação Radix não tem nada a ver com a sequência inicial
8. Encontre a estrutura de dados menos eficiente
Heap: projetado principalmente para classificação e não é ordenado durante a pesquisa.
9. Se o armazenamento sequencial for substituído pelo armazenamento em cadeia, a eficiência do tempo será reduzida.
Classificação de colina/classificação de heap (aproveitando as características de acesso aleatório de tabelas sequenciais)
2. Melhorias na classificação por mesclagem
Combinado com classificação por inserção direta: primeiro use a inserção direta para obter subsequências ordenadas mais longas e depois mescle-as em pares, ainda estáveis
3. Algoritmo baseado em comparação
O processo de decisão de comparação pode ser descrito por uma árvore binária, portanto leva pelo menos O(n㏒₂n) tempo
4. O próprio registro contém uma grande quantidade de informações
Usar listas vinculadas como estruturas de armazenamento pode evitar gastar muito tempo movendo registros
7. Classificação externa
1. Conceitos básicos de classificação externa
1. Reduza o número de leituras e gravações na memória externa
Aumentar o número de caminhos de mesclagem/reduzir o número de segmentos de mesclagem
2. Aumente o número de caminhos de mesclagem (m)
árvore perdedora
Após o uso, o número de comparações não tem nada a ver com m. Você pode aumentar m para reduzir a altura da árvore de mesclagem.
3. Reduza o número de segmentos mesclados
classificação de seleção de permutação
Aumente o comprimento dos segmentos de mesclagem para reduzir o número de segmentos de mesclagem
4. Organize a sequência de fusão de segmentos mesclados com comprimentos diferentes
melhor árvore de mesclagem
Árvore de Huffman generalizada para árvore m-ária
2. Método de classificação externa (classificação por mesclagem)
1. Duas etapas relativamente independentes
1. Obtenha o segmento/string serial mesclado
De acordo com o tamanho do buffer de memória, os n registros são divididos em vários registros, que são lidos sequencialmente na memória e classificados usando classificação interna e, em seguida, gravados de volta na memória externa.
2. Mescle os segmentos mesclados um por um, de modo que os segmentos mesclados aumentem de pequeno para grande até serem concluídos.
2. Número de passagens de mesclagem S = altura da árvore = ┌㏒mⁿ┐
n-o número de segmentos iniciais de fusão m-o número de caminhos de fusão ┌┐-arredondado
3. Fusão balanceada multidirecional e árvore perdedora
1. O tempo de fusão interna aumenta com o crescimento de m
1. Compensa os benefícios obtidos com a redução do número de acessos à memória externa devido ao aumento de m.
2. A classificação por mesclagem interna comum não pode ser usada
2. Árvore perdedora (árvore binária completa)
1. Nó folha
Registros atualmente participando da comparação
2. Nós internos
Memorize o número de sequência do perdedor nas subárvores esquerda e direita e deixe o vencedor continuar a comparar para cima até o nó raiz
3. Nó raiz
O número de série do número mínimo/máximo atual, não o valor em si (vencedor)
3. Depois de usar a árvore perdedora para obter o número de sequência do valor mínimo, retire o número do valor mínimo, adicione a próxima palavra-chave em sua posição, continue a comparação e construa a árvore perdedora.
4. Depois de usar a árvore perdedora, o número de comparações não tem nada a ver com m. Você pode aumentar m para reduzir a altura da árvore de mesclagem.
5.m não é tão maior, melhor
À medida que m aumenta, o buffer de entrada aumenta, sua capacidade diminui e o número de trocas de dados entre a memória interna e externa aumenta.
4. Classificação por seleção de substituição (gera o segmento de mesclagem inicial mais longo)
1. Pensamentos
1. Primeiro pegue o menor número a na área de trabalho
2. Em seguida, pegue o menor número entre os números maiores que a e coloque-o nesta seção de mesclagem, e o número menor que a é colocado na próxima seção de mesclagem.
5. Melhor árvore de mesclagem
1. Definição (árvore m-ária generalizada de Huffman)
1. Nó folha
Um segmento de mesclagem inicial que participa da mesclagem
2. Peso do nó folha
O número de registros no segmento de mesclagem inicial
3. Comprimento do caminho do nó folha ao nó raiz
Número de passagens de mesclagem
4. Nós não-folha
Novos segmentos mesclados gerados pela fusão
5. Comprimento do caminho ponderado da árvore de mesclagem
Número total de registros lidos
Número de arestas passadas por todos os nós folha * peso
2. Pensamentos
Deixe que os segmentos de mesclagem com menos registros sejam mesclados primeiro e aqueles com mais registros sejam mesclados por último.
3. A árvore de mesclagem ideal é uma árvore m-ária estrita
1. Se o último item faltante não for suficiente para formar uma árvore m-ária estrita, adicione um "segmento virtual" com comprimento 0 e mescle-o primeiro.
2. Número de segmentos de mesclagem vazios = m-u-1
você=(n0-1)%(m-1)
n0 - o número de nós com grau 0 (o número de segmentos iniciais mesclados) árvore m-m
Resumo da pergunta
1. Tipo de pergunta
1. Há n registros no total, o espaço de trabalho pode acomodar registros e a mesclagem balanceada de m vias é executada.
1. O número inicial de segmentos de fusão r=n/a, o número de passagens de fusão s=┌㏒m(r)┐
2,5 segmentos de mesclagem iniciais, cada um com 20 registros, usando mesclagem balanceada de 5 vias, Número de comparações sem árvore perdedora e com árvore perdedora
1. Nenhuma árvore perdedora é usada: 5 registros precisam ser comparados 4 vezes para selecionar o menor. Existem 100 registros no total, 99 operações são necessárias para selecionar o menor, 4*99=396.
2. Use a árvore perdedora: A altura da árvore perdedora é h = 3, selecione a menor de cada vez e o número de comparações não exceda h, um total de 100 vezes, não mais que 300 vezes
3. Faça a fusão balanceada m-way, o número de buffers de entrada e saída
1. Situação normal (operação serial): m buffers de entrada e 1 buffer de saída são necessários
2. Operação paralela de entrada/saída: buffers de entrada de 2m, 2 buffers de saída
4. O número total de arquivos de entrada/saída disponíveis ao mesmo tempo não excede 15
Até 14 maneiras de mesclar podem ser feitas