Wondershare EdrawMind
Galeria de mapas mentais 01Estrutura de dados
- 11
01Estrutura de dados
Este é um mapa mental sobre 01 estrutura de dados, incluindo estrutura lógica, número de Cattleya, estrutura física, Operações de dados, etc.
Editado em 2023-12-08 15:46:58
- moléculas que compõem as células
A segunda unidade do Curso Obrigatório de Biologia resumiu e organizou os pontos de conhecimento, abrangendo todos os conteúdos básicos, o que é muito conveniente para todos aprenderem. Adequado para revisão e visualização de exames para melhorar a eficiência do aprendizado. Apresse-se e colete-o para aprender juntos!
- Cambridge IGCS Chemistry Coursebook 2023 Capítulo 16 Resumo dos pontos de conhecimento
Este é um mapa mental sobre Extração e corrosão de mim. O conteúdo principal inclui: Corrosão de metais, Extração de metais e a série de reatividade.
- Cambridge IGCS Chemistry Coursebook 2023 Capítulo 15 Resumo dos pontos de conhecimento
Este é um mapa mental sobre Reatividade de metais. O conteúdo principal inclui: Reações de deslocamento de metais, A série de reatividade de metais.
01Estrutura de dados
- moléculas que compõem as células
A segunda unidade do Curso Obrigatório de Biologia resumiu e organizou os pontos de conhecimento, abrangendo todos os conteúdos básicos, o que é muito conveniente para todos aprenderem. Adequado para revisão e visualização de exames para melhorar a eficiência do aprendizado. Apresse-se e colete-o para aprender juntos!
- Cambridge IGCS Chemistry Coursebook 2023 Capítulo 16 Resumo dos pontos de conhecimento
Este é um mapa mental sobre Extração e corrosão de mim. O conteúdo principal inclui: Corrosão de metais, Extração de metais e a série de reatividade.
- Cambridge IGCS Chemistry Coursebook 2023 Capítulo 15 Resumo dos pontos de conhecimento
Este é um mapa mental sobre Reatividade de metais. O conteúdo principal inclui: Reações de deslocamento de metais, A série de reatividade de metais.
- Recomendado para você
- Descrição
estrutura de dados (uma coleção de elementos de dados que possuem um relacionamento)
estrutura lógica
estrutura linear
Tabela linear geral
representação sequencial
Tabela de sequência
Use unidades de armazenamento com endereços consecutivos para armazenar elementos na tabela
Características
A ordem lógica é consistente com a ordem física
Inserções e exclusões são extremamente caras
acesso aleatório
inserir
Melhor caso: inserção no final da tabela O(n) Pior cenário: inserção de cabeçalho, todos os elementos devem ser movidos de volta O(n)
for(int j=L. length; j>=i; j--)//Mover o primeiro elemento e os elementos subsequentes para trás L. dados[j]=L dados[j-1]; L. data[i-1]=e;//Coloque e na posição i L.length;//Adiciona 1 ao comprimento da tabela linear
excluir
Melhor caso, O(1) Pior caso, O(n)
e=L. data[i-1];//Atribuir o elemento excluído a e for(int j=i; j<L. length;j);//Move o elemento após a i-ésima posição para frente L. dados[j-1]=L dados[j]; L. length--;//O comprimento da tabela linear é reduzido em 1
Encontrar por valor
Melhor caso, O(1) Pior caso, O (n)
for(i=0; i<L. comprimento;i) if(L.dados[i]==e) return i 1;//Como o subscrito da tabela é armazenado a partir de 0, o valor do elemento com subscrito i é igual a e, retorna sua ordem de bits i 1 return 0; //Sai do loop, indicando que a busca falhou
representação em cadeia
Logicamente adjacente, não fisicamente adjacente, estabelecendo relações lógicas através de cadeias
vantagem
A inserção e exclusão não requerem movimentação de elementos, apenas modifique o ponteiro
deficiência
Não é possível acessar aleatoriamente
Categorias principais
Lista única
A unidade de armazenamento armazena informações do elemento e um ponteiro para o subseqüente
Método de definição
digite estrutura LNoed{ Dados ElemType; Estrutura LNoed *próximo; ｝LNode,*Llinklist;
inserir
Método de inserção de cabeça
S->dados=x; S->next=L->next; //L é o ponteiro principal L->próximo=S;
L é o ponteiro principal
método de inserção de cauda
S->dados=x; r->next=S;. //r é o ponteiro final da tabela r=S; //Move r para o novo nó final para se preparar para a próxima inserção final
excluir
p-q-x Excluir q
q=p->próximo; p->próximo=q->próximo; grátis(q);
Encontrar por valor
lnode *p=l->next; //Ponteiro p aponta para o próximo nó do nó principal while (p!=null&&p!=valor a ser verificado) p=p->próximo; retornar p;
Lista duplamente vinculada
Comparado com uma lista vinculada individualmente, há mais um pré-ponteiro apontando para o nó anterior.
Definição
digite estrutura LNoed{ Dados ElemType; Estrutura LNoed *pre,*next; ｝LNode,*Llinklist;
inserir
① s->próximo=p->próximo; ② p->próximo->pre=s; ③ s->pré=p; ④ p->próximo=s;
①② deve preceder ④
excluir
p→próximo=q→próximo; q→próximo→pré=p; grátis(q);
lista vinculada circular
Lista circular unida individualmente
Lista circular duplamente vinculada
lista vinculada estática
O ponteiro aqui se refere ao subscrito da matriz do próximo elemento
tabela generalizada
cabeça
Remova o elemento no topo da tabela ou subtabela
cauda
Remova os elementos do final da tabela
tabela linear restrita
pilha
Características
ultimo a entrar primeiro a sair
Somente inserção ou exclusão é permitida no topo da pilha
Você não pode ler um elemento do meio à vontade
Classificação
pilha de sequência
Operações básicas
A pilha está vazia bool StackEmpty(SqStack S){ if(S.top==-1) //A pilha está vazia retornar verdadeiro; senão //não está vazio retorna falso; ｝
empurrar para a pilha bool Push(SqStack &S,ElemType x){ if(S.top==MaxSize-1) //A pilha está cheia e um erro será relatado retorna falso; S. data[ S. top]=x; //O ponteiro é primeiro incrementado em 1 e depois colocado na pilha retornar verdadeiro; ｝
pop bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //A pilha está vazia e um erro é relatado retorna falso; x=S. data[S. top--]; //Puxa a pilha primeiro e depois diminui o ponteiro em 1 retornar verdadeiro; }
Leia o elemento superior da pilha bool GetTop(SqStack S,ElemType &x) { if(S.top==-1)//A pilha está vazia e um erro é relatado retorna falso; x=S.data[S.top]; //x registra o elemento superior da pilha retornar verdadeiro; ｝
pilha compartilhada
Duas pilhas sequenciais compartilham um espaço de pilha para economizar espaço de armazenamento.
O ponteiro topo0 da pilha A aponta para o topo da pilha e o ponteiro topo1 da pilha B aponta para o topo da pilha. O elemento é colocado na pilha A: top0 é adicionado primeiro e depois colocado na pilha O elemento é colocado na pilha B: top1 é primeiro decrementado em um e depois colocado na pilha A pilha está cheia quando top1-top0=1 a pilha A está vazia quando top0==-1 A pilha B está vazia quando top1==Maxsize
pilha de corrente
Sem nó principal Lhead aponta para o elemento superior da pilha A pilha de cadeia facilita a inserção e exclusão
aplicação de pilha
correspondência de colchetes
Avaliação de expressão
chamada recursiva
fila
Características
primeiro a entrar, primeiro a sair
Não permita a leitura arbitrária de um elemento no meio
Classificação
Armazenamento de pedidos em fila
fila sequencial
Junte-se à equipe
traseira 1 e atribua o valor
Retirar da fila
Deixe o time primeiro, depois na frente 1
fila circular
A equipe está vazia
dianteiro==traseiro
A equipe está cheia
(traseira 1)%Maxsize==frente
Número atual de elementos
(tamanho máximo traseiro dianteiro)% tamanho máximo
Junte-se à equipe
Junte-se à equipe bool EnQueue(SqQueue &Q, ElemType x){ if((Q. traseira 1)MaxSize==Q. frente) return false; //Se o time estiver cheio, um erro será reportado Q. data[Q. rear]=x; //Se não houver espaço, insira-o na parte traseira Q. rear=(Q. rear 1)MaxSize //Adiciona 1 ao módulo do ponteiro da cauda; retornar verdadeiro; ｝
Retirar da fila
Retirar da fila bool DeQueue(SqQueue &Q, ElemType &x){ if (Q. traseiro == Q. frontal) return false; //Se a fila estiver vazia, um erro será relatado x=Q.dados[Q.front]; Q. front=(Q. front 1)%MaxSize; //Adiciona 1 ao módulo do ponteiro do cabeçalho da equipe; retornar verdadeiro; }
Armazenamento em cadeia de filas
A essência é uma lista vinculada individualmente com um ponteiro inicial e um ponteiro final.
entrar e sair
A equipe está vazia bool IsEmpty(LinkQueue Q){ if(Q.front==Q.traseiro) retornar verdadeiro; caso contrário, retorne falso; ｝
Junte-se à equipe void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->dados=x; s->next=NULL; //Cria um novo nó e insere-o no final da cadeia Q. traseiro->próximo=s; Q. traseira = s; ｝
Retirar da fila bool DeQueue(LinkQueue &Q, ElemType &x){ if(Q.front==Q.traseiro) return false; //Equipe vazia LinkNode *p=Q.front->próximo; x=p->dados; Q.front->próximo=p->próximo; if(Q.traseiro==p) Q. rear=Q. front; //Se houver apenas um nó na fila original, ele ficará vazio após a exclusão. grátis(p); retornar verdadeiro; ｝
deque
Saída limitada
Apenas uma extremidade pode produzir
Entrada restrita
Apenas uma entrada é permitida
Enfileirar aplicativos
Passagem de nível
amortecedor
corda
correspondência de padrões
partida simples
algoritmo kmp
Método de cálculo do próximo valor
① Os dois primeiros próximos valores são 0 e 1
② O próximo valor subsequente é correspondido por prefixo e sufixo, e o comprimento de string mais longo correspondido com sucesso é considerado 1
Otimização do algoritmo kmp
método de cálculo do valor nextval
Pesquise de acordo com o próximo valor com o mesmo número. O próximo valor é o valor nextval a ser encontrado. Se já existir um valor nextval, atualize-o.
Generalização de tabelas lineares
variedade
Método de armazenamento
precedência de linha
Coluna primeiro
Armazenamento compactado de matrizes especiais
matriz triangular superior matriz triangular inferior
Matriz simétrica
matriz tridiagonal
precedência de linha
Armazenado em uma matriz unidimensional k=2i j-3
matriz esparsa
método de armazenamento triplo
(linha, coluna, dados)
Método de armazenamento de lista vinculada
estrutura não linear
juntar
Os elementos pertencem ao mesmo conjunto
estrutura de árvore
Árvore
natureza da árvore
é uma estrutura de dados recursiva
é uma estrutura hierárquica
① Número de nós da árvore = soma dos graus de todos os nós 1
② Uma árvore de grau m possui no máximo mⁱ⁻¹ nós no i-ésimo nível.
③ Uma árvore m-ária com altura h possui no máximo (mʰ -1) / (m-1) nós.
④ A altura mínima de uma árvore x com n nós ┍ logₓ (n(m-1) 1)┒
Árvore binária
natureza
n₀=n₂ 1
n=n₀ n₁ n₂
n = 1 n₁ 2n₂
Uma árvore binária com altura h possui no máximo 2ʰ-1 nós.
Classificação
Árvore binária vazia
árvore binária completa
árvore binária completa
Correspondência um-para-um entre nós e números
Só pode haver um ou nenhum nó com grau 1
Este nó determina a paridade do número total de nós na árvore binária completa
A altura da árvore de uma árvore binária completa com n nós
┍ log₂(n 1)┒ arredondar
┕ log₂n┙ 1 arredondamento para baixo
Árvore de classificação binária
Pequeno à esquerda e grande à direita
árvore binária balanceada
A diferença de altura entre as subárvores esquerda e direita não excede 1
Estrutura de armazenamento de árvore binária
armazenamento sequencial
árvore binária completa
árvore binária completa
armazenamento em cadeia
Lista vinculada binária com n nós Contém n 1 domínios de cadeia vazios
pista de árvore binária
Clue A árvore binária é uma estrutura física
O campo de link vazio é usado para armazenar pistas que apontam para a sequência anterior ou subsequente.
Classificação
Árvore binária de dicas em ordem
árvore binária de dicas de pré-encomenda
árvore binária de pista pós-ordem
Travessia de árvore binária
passagem de pré-encomenda
Ao redor da raiz
travessia em ordem
esquerda raiz direita
Travessia pós-ordem
raízes esquerda e direita
estrutura de armazenamento de árvore
representação dos pais
representação infantil
representação do irmão menor
representação de árvore binária
Nós fáceis de encontrar para crianças
Encontrar pais é mais difícil
digite estrutura csnode{ dados de tipo de elemento; struct csnode *liftchild, *rightbro; //Definir ponteiros filho e irmão direito ｝csnode, *cstree;
Árvore, floresta, conversão de árvore binária
Filho esquerdo, irmão direito
O nó filho esquerdo da raiz é usado como nó filho da raiz na nova árvore. O irmão certo da raiz torna-se filho da raiz na nova árvore
Aplicações de árvores e árvores binárias
Árvore Huffman/Árvore Huffman
Árvore binária com comprimento de caminho mínimo ponderado WPL
Características
① Pequeno à esquerda e grande à direita ou Grande à esquerda e pequeno à direita
② Selecione duas fusões com o menor peso de cada vez, e sua soma será usada como o peso da nova raiz.
③ A forma da árvore Ha não é única, mas o valor WPL é sempre o menor.
④ Não existe nenhum nó com grau 1 na árvore hash.
Porque a árvore ha é mesclada dois a dois.
Codificação de Huffman
comprimento variável
Variável de comprimento de caracteres binários
comprimento fixo
O comprimento dos caracteres binários é fixo
E pesquise a coleção
É um conjunto (estrutura lógica)
Árvore armazenada sequencialmente na representação pai
e
verificar
Aplicação de busca sindical
Determinar a conectividade de um gráfico
Percorra todas as arestas de um gráfico não direcionado, Cada vez que uma aresta é atravessada, seus dois vértices são mesclados em um conjunto. Desta forma, todos os vértices conectados estarão em um conjunto, e os vértices não conectados não estarão neste conjunto.
estrutura gráfica
Definição de gráfico
O conjunto de vértices V e o conjunto de arestas E constituem
Classificação de fotos
Gráfico não direcionado
A soma dos graus de todos os vértices de um gráfico não direcionado = número de arestas × 2
gráfico direcionado
cauda do arco → cabeça do arco
A soma dos graus de entrada de todos os vértices de um gráfico direcionado = a soma dos graus de saída
diagrama simples
Não há arestas duplicadas Não há aresta do vértice para si mesmo
gráfico completo
gráfico completo não direcionado
n(n-1)/2 arestas
Gráfico completo direcionado
Existem dois arcos em direções opostas entre dois vértices
subtrama
conectado
em gráfico não direcionado
Quaisquer dois vértices estão conectados
Subgrafos maximamente conectados são chamados de componentes conectados
Conectividade forte
no gráfico direcionado
Quaisquer dois pontos estão fortemente conectados
Caminhos simples e circuitos simples
Os vértices não aparecem repetidamente → caminho simples
Exceto o primeiro e o último ponto, outros pontos não aparecem repetidamente → circuito simples
árvore geradora
Subgrafo conectado mínimo contendo todos os vértices
O gráfico deve ser conectado e ter o número mínimo de arestas.
Perceber
O maior número de arestas no caso não conectado:
Um gráfico completo é composto por n vértices. Neste momento, adicionar outro ponto é um gráfico não conectado.
O gráfico direcionado tem o menor número de arestas quando está fortemente conectado:
Pelo menos n arestas formam um ciclo
Outras imagens
gráfico esparso
|E| = |V|*log|V|
gráfico denso
Armazenamento gráfico
método de matriz de adjacência
armazenar
Gráfico não direcionado
gráfico direcionado
Complexidade espacial O(n²) → n é o número de vértices
Mais adequado para armazenar gráficos densos
método de lista de adjacências
armazenar
Gráfico não direcionado
Complexidade espacial (V 2E)
Porque a borda aparecerá duas vezes
gráfico direcionado
Complexidade espacial (V E)
método de lista cruzada
Armazenamento encadeado de gráficos direcionados
método de múltiplas tabelas
Armazenamento encadeado de gráficos não direcionados
Percurso gráfico
largura primeiro
Semelhante à passagem de nível
profundidade primeiro
Continue cavando fundo em um ponto
Para gráficos não direcionados, o número de chamadas para DFS ou BFS = o número de componentes conectados deste gráfico
Aplicação de diagramas
① Árvore geradora mínima
① Contém todos os vértices
② Contenha o mínimo de arestas possível
③ Peso e exclusividade
④ Número de arestas = número de vértices-1
⑤ O formato da árvore não é único
② Algoritmo primário
processo de algoritmo
① Escolha qualquer um
② Encontre o menor peso
③ Conecte em sequência, incluindo todos os pontos, com o mínimo de arestas possível
Adequado para resolver árvores geradoras mínimas de gráficos com densidade de arestas
complexidade de tempo
O(V²)
③ Algoritmo de Kruskal
Encontre a menor aresta em todo o gráfico, selecione-a primeiro e exija que todos os vértices sejam incluídos
Use e pesquise
Adequado para gráficos com poucas arestas e muitos vértices
complexidade de tempo
Elog₂E
④ Problema do caminho mais curto
① Algoritmo Dijkstra
processo de algoritmo
Grave todas as rodadas
① O caminho de cada etapa e o peso total do caminho
② Conjunto de caminho mais curto
Resolva o problema do caminho de origem único
Imagens sem autoridade ou imagens com autoridade estão bem.
complexidade de tempo
matriz de adjacência
O(V²)
lista de adjacências
O(V²)
②Algoritmo Floyd
gráfico ponderado
processo de algoritmo
Atualize continuamente a matriz
Tais como: A, A², A³……
O subscrito de A representa o nó de retransmissão
complexidade de tempo
O(V³)
⑤ Problema de caminho crítico
processo de cálculo manual
① Encontre o primeiro horário de ocorrência do evento Vk
Conte diretamente de frente para trás
② Encontre o último horário de ocorrência do evento Vl
Calcule de trás para frente, subtraia o menor peso
③ Encontre o primeiro horário de ocorrência e da atividade
O horário de ocorrência mais antigo do evento no final do arco
④ Encontre o último horário de ocorrência l da atividade
O último horário de ocorrência do evento no início do arco - o peso desta atividade
⑤ Subtraia a atividade mais antiga e da atividade mais recente l. A atividade igual a 0 é a atividade chave e os vértices conectados a ela são os necessários.
Número de Cattleya
Aplica-se a:
pilha
N elementos são colocados na pilha e o número de sequências pop-up é encontrado.
Árvore binária
Quantas formas diferentes de árvores binárias podem ser formadas por n nós?
correspondência de colchetes
n pares de colchetes, quantas sequências correspondentes de colchetes existem?
Pré-requisitos para usar números Cattelan
Pilhas e árvores binárias não podem ter outras restrições
Por exemplo, o requisito é: o primeiro número que sai da pilha é 1. Neste momento, o número Cattelan não pode ser usado para calculá-lo.
Dois métodos principais
Encontrar
pesquisa sequencial
Aplicável a
Tabela de sequência
lista vinculada
meia pesquisa
Aplicável a
lista de sequência ordenada
método de comparação
Unilateral
É necessário que a tabela linear possa ser armazenada aleatoriamente Então só funciona com estruturas de armazenamento sequenciais
Complexidade de tempo O (log₂n)
Pesquise em pedaços
Não ordenado dentro de blocos, ordenado entre blocos
Uma tabela de comprimento n é dividida em b blocos, cada bloco possui s registros. s=√n, o comprimento médio da pesquisa assume o valor mínimo √n 1
Comprimento médio de pesquisa ASL = (S² 2S n)/2S
ordem
pesquisa de árvore
Árvore de classificação binária
Pequeno à esquerda e grande à direita
estrutura
inserir
excluir
árvore binária balanceada
A diferença de altura entre as subárvores esquerda e direita não excede 1 Ou uma árvore vazia
Ajustamento
Tipo LL
Vire à direita uma vez
Tipo RR
Vire à esquerda uma vez
Tipo LR
Primeiro vire à esquerda e depois vire à direita
Tipo de RL
Primeiro vire à direita e depois à esquerda
operar
inserir
excluir
Encontrar
árvore vermelha preta
definição
① Raiz esquerda direita
② Raízes e folhas pretas
③ Não é vermelho
④ Pinça da Estrada Negra
Ajuste primeiro e depois a cor
Encontre por muito tempo
Sucesso ASL = (ΣNúmero da camada×Número de nós)/Número total
Falha ASL = (ΣQual camada × número de domínios de link vazios de nó)/número total
Árvore B e Árvore B
Árvore B
árvore B m-ária
Suporta pesquisa aleatória
Características
① Cada nó possui no máximo m subárvores, No máximo palavras-chave m-1
③ Exceto o nó raiz, todos os nós não-folha têm pelo menos ┍ m/2 ┒ subárvores Existem pelo menos ┍ m/2 ┒-1 palavras-chave
④ Os nós folha estão na mesma camada, ou seja, a camada de domínio de link vazio
② Se o nó raiz não for uma folha, existem pelo menos 2 subárvores
altura da árvore
Encontrar
Use pesquisa sequencial e meia pesquisa dentro do nó.
inserir
excluir
① Excluir diretamente
② Os irmãos podem pedir emprestado o suficiente
① O irmão Zuo pode pegar emprestado
Substitua-se pelo nó mais à direita do seu irmão esquerdo e preencha você mesmo a lacuna.
② O irmão certo pode pegar emprestado
Substitua-se pelo nó mais à esquerda do seu irmão direito e preencha você mesmo a lacuna.
③ Não há irmãos suficientes para pedir emprestado
mesclar
Árvore B
características da árvore B do garfo m
① Cada palavra-chave corresponde a uma subárvore
② ┍ m/2 ┒≤ n ≤ m
③ Os nós folha contêm todas as palavras-chave e informações
④ Não-folha serve apenas como índice
⑤ Suporta pesquisa sequencial e pesquisa aleatória
tabela hash
A eficiência da pesquisa depende do número de comparações
função hash
①Método de endereçamento direto
②Divisão com método de resto
H (chave) = chave%P
P: o maior número primo não maior que o comprimento da tabela
③Método de análise digital
④Método médio dos quadrados
Pesquisa de hash
Fator de carga α = número de registros/comprimento da tabela
Como lidar com conflitos
método de endereçamento aberto
① Detecção linear
Volte e preencha
Detecção linear calculada manualmente
Falha ASL = numerador/denominador
Numerador: mova o número de série da tabela para trás até encontrar uma lacuna, registre o número de vezes que ele foi movido para trás e, em seguida, 1 Todos os registros dentro de P elementos (o número de retrocessos é 1) e o número de lacunas (se as lacunas estiverem dentro de P)
Denominador: P
② Detecção quadrada
resolver conflitos
(restante d¡)% comprimento da tabela
d¡ = 0², 1², -1², 2², -2²…
③Hash duplo
④Pseudo-aleatório
método de zíper
organizar
A maior parte da classificação funciona apenas em tabelas lineares armazenadas sequencialmente
Classificação interna
ordenação por inserção
classificação por inserção direta
Tabelas lineares adequadas para armazenamento sequencial e vinculado
Escolha um como sentinela
Os elementos grandes são colocados atrás da sentinela e os elementos pequenos são colocados na frente da sentinela.
Após a conclusão, selecione o elemento que você acabou de organizar como o novo sentinela.
complexidade de tempo
O(n²)
Estabilizar
classificação de meia inserção
Tabelas lineares adequadas para armazenamento sequencial
complexidade de tempo
O(n²)
Tipo de colina
Tabelas lineares adequadas para armazenamento sequencial
complexidade de tempo
O(n²)
instável
classificação de troca
Tipo de bolha
complexidade de tempo
O(n²)
Estabilizar
Ordenação rápida
Selecione o benchmark, ① compare com o benchmark de trás para frente, ② compare com o benchmark de frente para trás, ① e ② alternadamente
complexidade de tempo
Melhor O (nlog₂n)
Pior O (n²)
Média O(nlog₂n)
instável
ordenação por seleção
Ordenação por seleção simples
Complexidade de tempo O (n²)
instável
Classificação de pilha
Adequado para situações com muitas palavras-chave
Um heap pode ser visto como uma árvore binária completa
processo de configuração
Começando pelo último nó não folha, determine se ele atende aos requisitos do heap.
Complexidade de tempo O (nlog₂n)
instável
Classificação de raiz
A eficiência do tempo é independente da sequência inicial
O bit mais alto primeiro/o bit mais baixo primeiro
Classificar por ano, mês e dia
Complexidade de tempo O(d(n r))
Estabilizar
classificação por mesclagem
Complexidade de tempo O (nlog₂n)
Estabilizar
classificação externa
Tempo total de classificação externa = tempo de classificação interna, tempo de leitura e gravação de armazenamento externo, tempo de fusão interna
Para r segmentos de mesclagem iniciais, execute x mesclagens
Altura da árvore h - 1 = ┍ logₓr ┒= número de passagens de mesclagem
árvore perdedora
Pode ser considerada uma árvore binária completa
Em cada rodada de comparação, o vencedor continua subindo, até o nó raiz
A profundidade da árvore perdedora para fusão k-way é: ┍ log₂k ┒
Classificação de seleção de deslocamento
processo de algoritmo
①Selecione um certo número de elementos da sequência a ser classificada e coloque-os na área de trabalho
②Selecione o número mínimo na área de trabalho e coloque-o no segmento de mesclagem e altere miniMax para este número.
③ Certifique-se de que o número colocado no segmento de mesclagem na próxima vez seja maior que o valor miniMax.
④Quando não há número maior que miniMax na área de trabalho, o primeiro segmento de mesclagem é gerado
Melhor mesclagem
Operações de dados
Aritmética
adicionar
reduzir -
pegar *
remover /
Operação (a são dados)
XOR ^ O mesmo é 0, a diferença é 1
E && lógico O mesmo que 1 é 1, caso contrário é 0
OU lógico || Todos os 0 são 0, caso contrário 1
Primeiro incremente e depois atribua um
Atribua o valor primeiro e depois aumente um
Diminua primeiro e depois atribua --a
Atribua primeiro e depois diminua a--
Pegue o restante %a
Negar !a
Estrutura física
Armazenamento de índice
Não apenas armazena elementos, mas também constrói uma tabela de índice para eles. A tabela de índice contém várias entradas de índice. Ao modificar os dados, você também deve modificar a tabela de índice
armazenamento em cadeia
Os elementos são logicamente adjacentes, mas não necessariamente fisicamente adjacentes
armazenamento sequencial
Elementos logicamente adjacentes também são armazenados fisicamente adjacentes.
Armazenamento de hash (cerquilha)
Calcule o endereço de armazenamento diretamente com base em palavras-chave