1.Dados

2. Elementos de dados

3. Objetos de dados

4.Tipo de dados

estrutura de dados

Três elementos

complexidade de tempo

complexidade do espaço

inserir

excluir

Pesquise por valor (pesquise sequencialmente)

Crie uma lista vinculada individualmente

Encontre nós por número de série

Encontre o nó da tabela de nós por valor

Inserir nó

Excluir nó

Pergunte o comprimento da mesa

Inserir nó

Excluir nó

Lista circular unida individualmente

Lista circular duplamente vinculada

inicialização voidInitStack(SqStack &S){ topo = -1; }

A pilha está vazia bool StackEmpty(SqStack S){ if(S.top == -1) retornar verdadeiro; caso contrário, retorne falso; }

empurrar para a pilha bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) retorna falso; S.data[ S.top] = x; //top é inicializado como -1 retornar verdadeiro; }

pop bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) retornar falso; x = S.dados[S.top- -]; retornar verdadeiro; }

Leia o elemento superior da pilha bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) retornar falso; x = S.dados[S.top]; retornar verdadeiro; }

Inicial: top0 = -1 top1 = MaxSize pilha cheia: somente quando dois ponteiros de pilha são adjacentes top1 - top0 = 1;

fila sequencial

fila circular As operações de desenfileiramento, junção e completa da fila circular devem ter%; a condição vazia é apenas Q.rear == Q.front;

inicialização void InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkQueue)); //Crie o nó principal Q.front ->próximo = NULL; }

A equipe está vazia bool IsEmpty(LinkQueue&Q){ if(Q.front == Q.rear) return true;//Com nó principal caso contrário, retorne falso; }

Junte-se à equipe void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL;//Cria um novo nó e insere-o no final da cadeia Q.rear->próximo = s; Q.traseira = s; }

Retirar da fila bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.rear == Q.front) retorna falso; LinkNode *p = Q.front->próximo; x = p->dados; Q.front->próximo = p->próximo; if(Q.rear == p) Q.rear = Q.front;//A fila original possui apenas um nó grátis(p); retornar verdadeiro; }

Deque restrito de entrada

Deque restrito de saída

[]()([][]()) é o formato correto; (] [) é o formato errado;

Expressões infixas: dependem da precedência do operador, mas também lidam com parênteses Expressões postfix: precedência do operador já considerada, sem parênteses (travessia pós-ordem da árvore de expressões) Converter expressão infixa em expressão pós-fixada

O nó raiz entra na fila; se a fila estiver vazia (todos os nós foram processados), a travessia termina, caso contrário, o primeiro nó raiz na fila é retirado da fila e acessado. o O filho da esquerda entra na equipe se tiver um filho da direita, adiciona o filho da direita à equipe e volta para a etapa anterior;

1. Resolva o problema de incompatibilidade de velocidade entre o host e os dispositivos externos; 2. Resolver problemas de competição de recursos causados ​​por múltiplos usuários

Estrutura de armazenamento de matriz linha principal; coluna principal

Matriz simétrica

matriz triangular

matriz tridiagonal

Use o método tripleto (rótulo de linha, rótulo de coluna, valor) ou lista vinculada

Armazenamento sequencial de comprimento fixo #define MaxLen 255 estrutura typedef{ char ch[MaxLen]; comprimento interno; }SString; Você também não pode registrar o comprimento e usar ‘\0’, que não está incluído no comprimento da string, para indicar o comprimento da string.

Representação de armazenamento alocado em heap (alocação dinâmica) estrutura typedef{ char*ch; comprimento interno; }HString; Na linguagem C, o espaço alocado dinamicamente é armazenado no heap e gerenciado por malloc() free().

Representação de armazenamento em cadeia de blocos: cada nó é chamado de bloco, e um bloco pode armazenar um ou vários caracteres, toda a lista vinculada é chamada de estrutura de cadeia de blocos; Quando o último nó ocupa menos de um bloco, geralmente é preenchido com "#"

Atribuição de string StrAssign(&T,chars) atribui o valor de T a chars

Comparação de strings StrCompare(S,T) if S>T,return>0;S=T,return 0;S<T,return<0

Encontre o comprimento da string StrLength(S) retorna o número de elementos S

Concatenação de série Concat(&T,S1,S2) usa T para retornar uma nova string formada pela concatenação de S1 e S2.

Encontre a substring SubString(&Sub,S,pos,len) Use Sub para retornar a substring começando no caractere pos da string S e continuando com o comprimento de len

índice interno(SString S,SString T){ int i=1,j=1; enquanto(i<=S.comprimento && j<=T.comprimento){ if(S.ch[i] == T.ch[j]){ eu j ; } outro{ eu = i-j 1 1;j = 1; } if(j > T.comprimento) return i - T.comprimento; caso contrário, retorne 0; } Pior complexidade de tempo O(mn)

Conceitos relacionados: Prefixo: Todas as substrings de cabeçalho da string, exceto o último caractere; Sufixo: todas as substrings finais da string, exceto o primeiro caractere; Correspondência parcial (PM): o comprimento igual mais longo do prefixo e do sufixo da string. Exemplo: 'ababa' Atenção! ! A partir do primeiro caractere da string principal, divida todas as substrings e, em seguida, analise o comprimento do prefixo e do sufixo e o sufixo e sufixo iguais mais longos, respectivamente. O prefixo e sufixo 'a' é um conjunto vazio e o maior comprimento igual de prefixo e sufixo é 0 'ab' prefixo 'a' sufixo 'b' O maior comprimento de correspondência igual é 0 'aba' prefixo 'a' 'ab' sufixo 'a' 'ba' {'a' 'ab'} ^ {'a' 'ba'} = 'a', o maior comprimento igual do sufixo é 1 Prefixo ‘abab’ ‘a’ ‘ab’ ‘aba’ sufixo ‘b’ ‘ab’ ‘bab’, o prefixo igual mais longo e o comprimento do sufixo são 2 'ababa' prefixo 'a' 'ab' 'aba' 'abab' sufixo 'a' 'ba' 'aba' 'baba' ,{ } ^ { } = {'a' 'aba'}, o maior comprimento igual do sufixo 3 Portanto, o valor de correspondência parcial da string final é 00123

Ao usar o algoritmo KMP, primeiro escreva a tabela PM da string padrão (substring). Quando a substring não corresponder à string principal, encontre o valor PM do último elemento correspondente da substring na tabela PM e, em seguida, deixe o valor PM. substring A distância retrocedida (número de caracteres correspondentes - valor PM do último caractere correspondente); quando ocorre uma incompatibilidade em uma determinada viagem, se o valor de correspondência parcial da parte correspondente for 0, significa que não há sufixos iguais e sufixos na sequência correspondente. O número de dígitos movidos é o maior (comprimento correspondente - 0) e é movido diretamente para a posição apontada pela string principal neste momento para a próxima comparação. Mover = (j-1) - PM[j-1];

Geração e modificação do próximo array: Para facilitar a incompatibilidade, em vez de esperar por um caractere, verifique diretamente o valor PM da posição atual do caractere incompatível, de modo que todos os elementos no PM sejam movidos 1 posição para a direita, a primeira posição seja preenchida com -1 , e a última posição é ignorada; Chamado de next array, Move = (j-1)-next[j] Neste momento, j retorna para j = j-Move = next[j] 1; Em seguida, adicione 1 a todos os próximos e atualize o próximo array para que j = next[j] (neste momento, a primeira posição do próximo array seja 0) O significado da próxima matriz final: Quando o j-ésimo caractere da substring não corresponder, pule para a próxima posição [j] da substring para a próxima rodada de correspondência! ! !

Uma árvore é um conjunto finito de n (n>0) nós. Quando n=0, é chamada de árvore vazia, pois possui apenas um nó raiz, e os nós restantes podem ser divididos em conjuntos finitos disjuntos, chamados de subárvores; 1. O nó raiz da árvore não tem antecessor, e os outros nós além do nó raiz têm um e apenas um predecessor 2. Todos os nós na árvore podem ter zero ou mais sucessores, a árvore é adequada para representar dados com um; estrutura hierárquica; 3. Terminologia: 1. Antepassado-descendente (pode abranger vários níveis, desde que exista uma relação descendente-filho-pai-irmão (com o mesmo nó pai); 2. O número de filhos de um nó na árvore é chamado de grau do nó; o grau máximo de um nó na árvore é o grau da árvore; 3. Nós com grau > 0 são chamados de nós ramificados (nós não terminais); nós com grau 0 são chamados de nós folhas (nós terminais); o número de ramificações de um nó ramificado é o grau do nó ramificado; 4. O nível dos nós é definido a partir da raiz da árvore, sendo o nó raiz os nós de primeiro nível cujos nós pais estão no mesmo nível são primos um do outro; A profundidade de um nó é acumulada camada por camada, começando no nó raiz e de cima para baixo (imagine a raiz da árvore ficando mais profunda para baixo) A altura do nó é acumulada camada por camada começando no nó folha e de baixo para cima (parece muito alta de baixo para cima) A altura ou profundidade de uma árvore é o número máximo de níveis de nós na árvore; 4. Árvores ordenadas e árvores não ordenadas, árvores ordenadas não são intercambiáveis 5. Caminho e comprimento do caminho: O caminho é composto pela sequência de nós passados ​​entre os dois nós, e o comprimento do caminho é o número de arestas passadas! 6. Floresta: um conjunto de árvores separadas. Enquanto o nó raiz for excluído, a árvore se tornará uma floresta; inversamente, enquanto um nó raiz for adicionado a m árvores, a floresta se tornará uma árvore;

natureza: 1. O número de nós da árvore é igual à soma dos graus de todos os nós (número total de ramos) 1 (nó raiz) 2. O i-ésimo nível de uma árvore de grau m tem no máximo m^i-1 nós (i>1) 3. Uma árvore m-ária com altura h tem no máximo (m^i - 1)/(m-1) nós. 4. A altura mínima de uma árvore m-ária com n nós é

1. Armazenamento sequencial: Notação parental: uma estrutura grande define uma estrutura pequena, e a estrutura pequena são os dados e os ponteiros pais; #define Max_Tree_SIze 100 estrutura typedef{ Dados ElemType; pai interno; }PTNode; estrutura typedef{ Nós PTNode[Max_Tree_Size]; intn; }PTree; Essa estrutura aproveita o fato de que cada nó (exceto o nó raiz) possui apenas um pai e pode obter rapidamente o nó pai de cada nó, mas requer percorrer toda a árvore para encontrar os filhos do nó.

2. Na representação filho: conecte os nós filhos de cada nó com uma única lista vinculada para formar uma estrutura linear. Existem n listas vinculadas para n nós (a lista vinculada filho de um nó folha é uma lista vinculada vazia); Este método é muito simples para encontrar filhos, mas encontrar pais requer percorrer as n listas vinculadas de filhos apontadas pelos ponteiros da lista vinculada de filhos em n nós; Semelhante à tabela crítica

3. Representação de irmão filho: também conhecida como representação de árvore binária. typedef estrutura CSNode{ Dados ElemType; struct CSNode *primeirofilho,*próximo; }CSNode,*CSTree; Implemente convenientemente a operação de conversão de uma árvore em uma árvore binária A criança da esquerda tem um irmão

A conversão entre árvores e árvores binárias; tanto as árvores quanto as árvores binárias podem ser representadas por listas vinculadas binárias. A estrutura física é a mesma, mas as regras para converter uma árvore em uma árvore binária: filho esquerdo e irmão direito. Como o nó raiz não tem irmãos, o nó raiz não tem subárvore direita. Etapas de conversão de caligrafia: 1. Conecte uma linha entre os nós irmãos 2. Mantenha apenas a conexão entre cada nó e seu primeiro filho e use outro Apague todas as conexões dos filhos; 3. Tome a raiz da árvore como eixo e gire 45 graus no sentido horário

Conversão de floresta em árvore binária 1. Primeiro converta cada árvore da floresta em uma árvore binária 2. A raiz de cada árvore é considerada um relacionamento entre irmãos e as árvores subsequentes são sequencialmente consideradas como o nó direito da árvore anterior. 3. Gire a raiz da primeira árvore 45 graus no sentido horário

Converta uma árvore binária em uma floresta: 1. Desconecte a subárvore direita do nó raiz, por sua vez, até que haja apenas um nó raiz sem uma subárvore direita. 2. Converta todas as árvores binárias desconectadas em árvores para obter a floresta original Converter uma árvore binária em uma árvore ou floresta é único

Converter árvore binária em árvore 1. Remova todos os nós direitos, nós direitos e nós direitos da subárvore esquerda do nó raiz. . . todos como filhos da raiz 2. Ajuste por sua vez

travessia de árvore

Viajando pela floresta

Union-find é uma representação de conjunto simples que suporta 3 operações A definição da estrutura do conjunto de pesquisa sindical: #define TAMANHO 100 int UFSets[TAMANHO]; Um conjunto na busca de união é uma árvore e vários conjuntos formam uma floresta.

Clue árvore binária (desconhecida, especialmente expandida) typedef estrutura TreadNode{ Dados ElemType; struct TreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; Uma lista vinculada binária composta por uma estrutura de nó como a estrutura de armazenamento da árvore binária é chamada de lista vinculada de pistas; os ponteiros que apontam para o predecessor e o sucessor do nó são chamados de pistas; Uma árvore binária com pistas é chamada de árvore binária de pistas

Atravessar

Árvore de classificação binária BST (árvore de pesquisa binária)

árvore binária balanceada

árvore vermelha preta

Árvores de Huffman e codificação de Huffman

gráfico direcionado, gráfico não direcionado Gráfico direcionado: E é uma aresta direcionada (arco) e um arco é um par ordenado de vértices, denotado como <v,w> Gráfico não direcionado: E é uma aresta não direcionada (aresta) e uma aresta é um par não ordenado de vértices, registrado como (v, w)

Gráfico simples, gráfico múltiplo Diagrama simples: 1. Não há arestas duplicadas (arestas apontando uma para a outra entre dois nós adjacentes em um gráfico direcionado não são contadas como arestas duplicadas) 2. Não há aresta do vértice para ele mesmo. Parcelas múltiplas: 1. O número de arestas entre dois vértices é maior que 1 2. Permitir que os vértices sejam relacionados entre si através de uma aresta As definições de gráficos múltiplos e gráficos simples são relativas e apenas gráficos simples são discutidos na estrutura de dados.

Gráfico completo (gráfico completo simples) Para gráficos não direcionados, o intervalo de valores de |E| é 0-n(n-1)/2, Um grafo não direcionado com n(n-1)/2 arestas é chamado de grafo completo e há uma aresta entre quaisquer dois vértices; Para gráficos direcionados, o intervalo de valores de |E| é 0-n(n-1), Um grafo direcionado com n(n-1) arcos é chamado de grafo completo direcionado e existe um arco oposto entre quaisquer dois vértices.

subtrama G=(V,E),G'=(V',E'); Se V' é um subconjunto de V e E' é um subconjunto de E, então G' é chamado de subgrafo de G. Se V(G')=V(G) for satisfeito, então G' é chamado de subgrafo gerado de G; Nenhum subconjunto de V e E pode formar um subgrafo G, porque os vértices associados a algumas arestas no subconjunto de E podem não estar neste subconjunto de V.

Conectividade, gráficos conectados e componentes conectados Se existe um caminho do vértice v ao vértice w, então v e w são considerados conectados. Se quaisquer dois vértices em G estiverem conectados, ele se tornará um grafo conectado, caso contrário, será um grafo desconectado. O subgrafo conectado máximo em um gráfico não direcionado é chamado de componente conectado. Um gráfico conectado tem pelo menos n-1 arestas. Se o número de arestas for menor que n-1, deve ser um grafo não conectado; Quantas arestas um gráfico desconectado pode ter no máximo? : O estado crítico de n-1 vértices formando um gráfico completo (adicionando qualquer aresta para formar um gráfico conectado)

Gráfico fortemente conectado, componentes fortemente conectados Em um grafo direcionado, se um par de vértices v para w e w para v têm caminhos, então os dois vértices são fortemente conectados. Se qualquer par de vértices no grafo estiver fortemente conectado, o grafo será chamado de grafo fortemente conectado. O subgrafo fortemente conectado máximo em um gráfico direcionado é chamado de componente fortemente conectado do gráfico direcionado; A situação com o menor número de arestas quando um grafo direcionado é fortemente conectado: pelo menos n arestas são necessárias para formar um ciclo

abrangendo árvore, abrangendo floresta A árvore geradora de um grafo conectado é um subgrafo conectado mínimo que contém todos os vértices do grafo. Se o número de vértices fixos for n, então a árvore geradora terá n-1 arestas. Se uma aresta for cortada da árvore geradora, ela se tornará um subgrafo não conectado; se uma aresta for adicionada, um ciclo será formado; Em um gráfico desconectado, a árvore geradora de componentes conectados constitui a floresta abrangente do gráfico desconectado.

Grau de vértice, grau de entrada e grau de saída Gráfico não direcionado: TD(v), a soma dos graus de todos os vértices de um gráfico não direcionado é igual a 2 vezes o número de arestas Gráfico direcionado: O grau do vértice v é dividido em grau de entrada ID (v) e grau de saída OD (v). O grau do vértice v é igual à soma do grau de entrada e do grau de saída: TD (v). =ID(v) OD(v) , o grau de entrada de todos os vértices de um gráfico direcionado é igual ao grau de saída igual ao número de arestas

Bian's Quanhe.com Cada aresta pode ser marcada com um valor numérico que possui um determinado significado, que é chamado de peso da aresta. O grafo com arestas ponderadas é chamado de grafo ponderado, também conhecido como rede.

Gráfico denso, gráfico esparso Um grafo com poucas arestas é chamado de grafo esparso e o oposto é chamado de grafo denso. Geralmente, quando G satisfaz |E|<|V|log|V|, G é considerado um grafo esparso.

Caminhos, comprimentos de caminho e loops Caminho: um caminho do vértice vp para vq refere-se à sequência de vértices vp,vi1...vim,vq, O número de arestas em um caminho é chamado de comprimento do caminho Um caminho cujo primeiro e último vértices são iguais é chamado de ciclo ou ciclo Se um grafo tiver n vértices e mais de n-1 arestas, então o grafo deve ter um ciclo.

Caminho simples, loop simples Em uma sequência de caminhos, um caminho cujos vértices não aparecem repetidamente é chamado de caminho simples; Exceto o primeiro vértice e o último vértice, o ciclo no qual os vértices restantes não param nesse gráfico é chamado de ciclo simples.

distância Se o caminho mais curto do vértice u ao vértice v existir, então o comprimento desse caminho é a distância de u a v; Não há caminho de u para v, então a distância é registrada como ∞

árvore direcionada Um gráfico direcionado no qual o grau de entrada de um vértice é 0 e o grau de saída dos vértices restantes é 1 é chamado de árvore direcionada.

Refere-se ao uso de uma matriz unidimensional para armazenar o relacionamento entre os vértices no gráfico e ao uso de uma matriz bidimensional para armazenar as informações de borda no gráfico (o relacionamento de adjacência entre os vértices. A matriz bidimensional que armazena o). A relação de adjacência entre vértices é chamada de matriz de adjacência. A estrutura de armazenamento de todo o gráfico G: #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; estrutura typedef{ VertexType Vex[MaxVertexNum]; //Tabela de vértices EdgeType Edge[MaxVertexNum][MaxVertexNum];//matriz de adjacência, tabela de arestas int vexnum,arcnum; }MGráfico;

Quando um gráfico é esparso, o uso do método de lista de adjacências economiza muito espaço. O método de lista de adjacência de gráfico combina métodos de armazenamento sequencial e de armazenamento em cadeia; Crie uma lista vinculada individualmente para cada vértice no gráfico. O nó na i-ésima lista vinculada individualmente é anexado à aresta vi do vértice. Esta lista vinculada individualmente é a lista de arestas do vértice vi (um gráfico direcionado é chamado de. lista de arestas de saída) (a lista de arestas é "Edge" é realmente incrível) Cada nó na tabela de arestas representa uma aresta, mas armazena um número de vértice e omite outro número de vértice (na tabela de vértices) O ponteiro principal da tabela de arestas e as informações de dados de vértice do gráfico G são armazenados sequencialmente (chamadas de tabela de vértices); #define MaxVertexNum 100 typedef struct ArcNode{//nó da tabela de borda int adjvex;//A posição do vértice apontado pelo arco estrutura ArcNode *próximo; //Info Typeinfo; //O peso da borda da rede }ArcNode; typedef estrutura VNode{ Dados VertexType; // informações do vértice struct VNode *first;//Ponteiro para o primeiro arco anexado ao vértice }VNode,AdjList[MaxVertexNum]; estrutura typedef{ AdjList vértices; // lista de adjacências int vexnum,arcnum;//O número de vértices e arcos do gráfico }ALGráfico

Uma lista reticulada é uma estrutura de armazenamento vinculada de um gráfico direcionado. Cada arco no gráfico possui um nó. O nó do arco possui 5 campos: (tailvex, headvex, hlink, tlink, info) tailvex e headvex são respectivamente os vértices de origem e inserção da aresta hlink e tlink conectam respectivamente os nós de aresta dos mesmos vértices de origem e inserção; O nó vértice possui 3 campos: (dados, primeiro a entrar, primeiro a sair) A lista reticulada não é única, mas uma lista reticulada representa um determinado gráfico Na lista reticulada, é fácil encontrar o grau de entrada de V e o grau de saída de V.

Lista múltipla de adjacência é uma estrutura de armazenamento em cadeia de gráfico não direcionado Nós de borda (mark,ivex,ilink,jvex,jlink,info) mark é um campo de sinalização, que pode marcar se esta aresta foi pesquisada; ivex e jvex são as posições dos dois vértices anexados à aresta no gráfico; anexado ao vértice jvex edge info está um campo de ponteiro apontando para várias informações relacionadas à borda; vértice (dados, primeira aresta)

BFS resolve o problema do caminho mais curto de fonte única void BFS_MIN_Distance(Gráfico G,int u){ para(i=0;i<G.vexnum;i) //d[i] representa o caminho mais curto de você até i d[i]=∞;//inicializar comprimento do caminho visitado[u]=TRUE; d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){ DeQueue(Q,u); for(w=PrimeiroVizinho(G,u);w>=0;w=PróximoN oitavo(G,u,w)) if(visitado[w]){ visitado[w]=TRUE; d[w]=d[u] 1;//comprimento do caminho 1 EnQueue(Q,w); } } }

árvore geradora de largura A matriz de adjacência é armazenada de forma única – sua árvore geradora em largura é única O armazenamento da lista de adjacências não é único – sua árvore geradora de largura não é única

Semelhante ao percurso de pré-encomenda de uma árvore bool visitado[MAX_VERTEX_NUM]; void DFSTraverse(Gráfico G){ para(v=0;v<G.vexnum;v) visitado[v] = FALSO; para (v=0,v<G.vexnum;v) if(!visitado[v]) DFS(G,v); } void DFS(Gráfico G,int v){ visitar(v); visitado[v] = VERDADEIRO; for(w=PrimeiroVizinho(G,v);w>=0;w=PróximoVizinho(G,v,w)) if(!visitou[w]){ DFS(G,w); } }

Algoritmos de travessia de gráfico podem ser usados ​​para determinar a conectividade do gráfico. Se um grafo não direcionado for conectado, começando em qualquer vértice, todos os vértices do grafo podem ser visitados com apenas uma travessia; Se um grafo direcionado estiver conectado e houver um caminho do ponto inicial para cada vértice do grafo, então todos os vértices do grafo poderão ser acessados.

Algoritmo Prim (BFS) Semelhante a Dijkstra, inicialmente escolha um vértice do gráfico e adicione-o à árvore T, depois selecione um vértice mais próximo do conjunto atual de vértices em T e adicione o vértice e a aresta à árvore T; após cada operação e o número de arestas é aumentado em 1 até que todos os vértices do gráfico sejam adicionados à árvore T, T é a árvore geradora mínima. Deve haver n-1 arestas em T voidPrim(G,T){ T=conjunto vazio; você={W}; while((V-U)!=empty set){//Se a árvore não contém todos os vértices Seja (u, v) a aresta que forma u∈U e v∈(V-U) e tem o menor peso; T=T∪{(u,v)};//As arestas são classificadas em árvores U=U∪{v};//Os vértices são classificados em árvores } } A complexidade de tempo do algoritmo de Prim é O(|V^2|) e não depende de |E|, portanto é adequado para resolver a árvore geradora mínima de grafos com arestas densas.

Algoritmo de Kruskal Diferente do algoritmo de Prim, que se expande a partir dos vértices para gerar uma árvore geradora mínima, o algoritmo de Kruskal seleciona arestas apropriadas em ordem crescente de pesos para construir uma árvore geradora mínima. Inicialmente, cada vértice forma um componente conectado. Então, na ordem dos pesos das arestas, de pequeno para grande, a aresta que ainda não foi selecionada e tem o menor peso é selecionada continuamente se o vértice anexado à aresta cair em um conectado diferente. componente do componente T, adicione esta aresta a T, caso contrário, descarte esta aresta até que todos os vértices em T estejam em um componente conectado; nulo Kruskal(V,T){ T=V; //Inicializa T, apenas vértices numS=n;//Número de componentes conectados while(numS>1){//Se o número de componentes conectados for maior que 1 Pegue a aresta (v, u) com o menor peso de E se (v e u pertencem a diferentes componentes conectados em T) T=T∪{(v,você)}; numS--; } } } O algoritmo de Kruskal usa um heap para armazenar o conjunto de arestas, portanto, leva apenas O(log|E|) tempo para selecionar a aresta com o menor peso cada vez que adicionar uma nova aresta é semelhante ao processo de resolver uma equivalência; classe, e o método de pesquisa de união pode ser usado Estrutura de dados para descrever T, a complexidade do tempo é O(|E|log|E|), então Kruskal é adequado para gráficos com arestas esparsas e muitos vértices.

Algoritmo de Dijkstra (BFS) Caminho mais curto de origem única; O algoritmo de Dijkstra define um conjunto S para registrar os vértices do caminho mais curto obtido. Inicialmente, o ponto fonte v0 é colocado em S. Cada vez que um novo vértice vi é incorporado ao conjunto S, o ponto fonte v0 deve ser modificado. para o vértice mais curto atual no valor de comprimento V-S definido não são permitidos; Configure duas matrizes auxiliares: dist[]: Registre o comprimento do caminho mais curto atual do ponto de origem v0 para outros vértices. Estado inicial: Se houver um arco de v0 a vi, então dist[i] é o peso do arco, caso contrário, defina dist[i; ] para ∞. (dist[] só volta um passo de cada vez - ideia BFS) path[]: path[i] representa o nó predecessor do caminho mais curto do ponto de origem ao vértice i. Ao final do algoritmo, o caminho mais curto do ponto fonte v0 até o vértice vi pode ser traçado. Ao resolver manualmente, desenhe uma matriz de dict. O mais importante é adicionar o vértice ao conjunto S toda vez que você selecioná-lo, atualizar a distância do caminho de cada ponto e então dar o próximo passo começando no último vértice do conjunto. S. Complexidade de tempo O(|V|^2)

Algoritmo Floyd O caminho mais curto entre cada par de vértices A recursão produz uma sequência de matriz quadrada de ordem n: A^-1,A^0,..A^N; onde A^k[i][j] representa o comprimento do vértice i a j, e o k-ésimo vértice é usado; como relaxe os vértices do meio A complexidade do tempo é O(|V|^3) (equivalente a executar o algoritmo de Dijkstra uma vez para cada vértice O(|V^2|)*|V|), Arestas com pesos negativos não são permitidas e podem atuar em gráficos direcionados\gráficos não direcionados (convertidos em gráficos direcionados com os mesmos lados bilaterais)

Rede AOV (atividade na rede vértice) Se um DAG for usado para representar um projeto, seus vértices representam atividades, e a aresta direcionada <Vi, Vj> representa um relacionamento que Vi deve preceder Vj, então esse tipo de grafo é chamado de rede com vértices representando atividades. Existem muitos algoritmos para classificação topológica de redes AOV, um dos algoritmos comumente usados ​​é: 1. Selecione um vértice sem predecessor da rede AOV e produza-o 2. Exclua o vértice e todas as arestas direcionadas a partir dele da rede 3. Repita o passo 1.2 até que a rede AOV esteja vazia ou não haja vértices sem predecessor na rede atual (indicando que deve haver um ciclo no gráfico) Como a saída de cada vértice requer a exclusão de sua aresta inicial, a complexidade de tempo da classificação topológica é O(|V| |E|) Além disso, a classificação topológica também pode ser implementada usando DFS (começando nos vértices com um grau de entrada 0 e um grau de saída diferente de 0, um por um, e falhará enquanto o retrocesso ocorrer até que um traço seja concluído ) classificação topológica reversa Comece no vértice com grau externo 0 A rede AOV utiliza armazenamento de matriz de adjacência. Se for uma matriz triangular, deve haver uma sequência topológica e vice-versa.

Rede AOE (atividade na rede de ponta) Os eventos são representados por vértices, as atividades são representadas por arestas direcionadas e o custo de conclusão da atividade é representado pelo peso na aresta (como o tempo necessário para concluir a atividade) Duas propriedades da rede AOE: 1. Somente após a ocorrência do evento representado por um vértice, as atividades representadas pelas arestas direcionadas a partir do vértice podem começar. 2. O evento em um vértice só pode ocorrer após a conclusão das atividades representadas pelas arestas de entrada de um vértice. Existe apenas um vértice com grau de entrada 0 na rede AOE, denominado vértice inicial (ponto de origem), que representa o início de todo o projeto. A rede AOE também possui apenas um vértice com grau de saída 0; , chamado de vértice final (sink). Representa o final de todo o projeto. Algumas atividades na rede AOE podem ser realizadas em paralelo, mas todas as atividades em todos os caminhos não podem terminar até que sejam concluídas. Portanto, entre todos os caminhos da origem ao destino, o caminho com o maior comprimento é chamado de caminho crítico. . As atividades no caminho são chamadas de atividades críticas (encontrar as atividades críticas equivale a encontrar o caminho crítico). O menor tempo para concluir todo o projeto é a extensão do caminho crítico.

Pratique ASL ao buscar sucesso e fracasso

Pesquisa sequencial de tabelas lineares gerais typedef struct{//estrutura de dados da tabela de pesquisa ElemType *elem; //Endereço base do espaço de armazenamento do elemento int TableLen; //O comprimento da tabela }SSTable; int Search_Seq(SSTable ST, chave ElemType){ ST.elem[0] = chave;//Sentinela for(i=ST.TableLen;ST.elem[i]!=key;--i);//Olha de trás para frente retornar eu; } No algoritmo acima, ST.elem[0] é chamado de sentinela, de modo que o loop interno de Search_Seq não precisa julgar se a matriz sairá dos limites, porque o loop definitivamente saltará quando i==0 for satisfeito. A introdução de sentinelas pode evitar muitas declarações de julgamento desnecessárias, melhorando assim a eficiência do programa.

Pesquisa sequencial em lista ordenada Se for conhecido antes da pesquisa que as palavras-chave na tabela estão em ordem, então, após a falha da comparação, não há necessidade de comparar com a outra extremidade da tabela para retornar a falha da pesquisa, reduzindo assim o comprimento médio da pesquisa do falha na pesquisa. Uma árvore de decisão pode ser usada para descrever o processo de busca de uma lista linear ordenada. Os nós circulares representam os elementos que existem na lista linear ordenada; , então, correspondentemente, existem n 1 nós onde a pesquisa falhou. O comprimento médio da pesquisa (ASL) da pesquisa com falha é (1 2 .. n n)/(n 1); a probabilidade de encontrar cada 'nó com falha' é 1/n 1);

Sucesso em ASL=(n 1)/2

int Binary_Search(SeqList L, chave ElemType){ int baixo = 0, alto = L.TableLen-1, médio; enquanto(baixo<=alto){ médio = (baixo alto)/2; if(L.elem[mid]==key) return mid; senão if(L.elem[mid]<chave){ baixo = médio 1; // médio = (baixo alto)/2; } outro{ alto = médio-1; // médio = (baixo alto)/2; } } retornar -1; }

Altura da árvore B O número de acessos ao disco necessários para a maioria das operações em uma árvore B é proporcional à altura da árvore B. Cada nó na árvore possui no máximo m subárvores e m-1 palavras-chave, e o número de palavras-chave deve satisfazer n≤m^h-1; A h1ª camada tem pelo menos 2(m/2 limite superior)^(h-1) nós, e a h1ª camada é um nó folha que não contém nenhuma informação; Para uma árvore B com n palavras-chave, o nó onde a pesquisa do nó folha falha é n 1, então n 1>=2 (m/2 assume o limite superior)^(h-1), ou seja, h≤log ( m/2 assume o limite superior)((n 1)/2 1)

Pesquisa de árvore B 1. Encontre nós na árvore B 2. Encontre palavras-chave dentro do nó A operação de pesquisa de 1. é executada no disco e a operação de pesquisa de 2. é executada na memória; Depois de encontrar o nó de destino, leia-o na memória e, em seguida, use o método de pesquisa sequencial ou o método de pesquisa binária dentro do nó.

Inserção na árvore B Inserir diretamente após não conseguir encontrar o local destruirá os requisitos na definição da árvore B. 1. Posicionamento: Encontre o nó não folha na camada mais baixa (encontre o nó folha, pegue o nó não folha da camada anterior) 2. Inserção: O número de palavras-chave em cada nó sem falha está dentro do intervalo [m/2 leva o limite superior -1, m-1] e pode ser inserido diretamente; Quando o número de palavras-chave de nó inseridas é maior que m-1, o nó é dividido. Método de divisão: pegue o limite superior da posição intermediária m/2 e divida a palavra-chave em duas partes. A parte esquerda é incluída no nó original e a parte direita é colocada no novo nó na posição intermediária (; m/2 assume o limite superior) para inserir o nó pai do nó original e assim por diante;

Exclusão da árvore B Quando a palavra-chave excluída k não está no nó terminal (o nó não folha mais baixo), k pode ser substituído pelo antecessor (sucessor) de k k', e então k' é excluído no nó correspondente e convertido em uma palavra-chave A situação no nó terminal; Quando a palavra-chave excluída está no nó terminal (o nó não folha mais baixo), há três situações: 1. Exclua palavras-chave diretamente: o número de palavras-chave ≥ m/2 assume o limite superior -1 2. Irmãos são suficientes: o número de palavras-chave = m/2, considere o limite superior -1, e o número de palavras-chave irmãs esquerda e direita (adjacentes) é maior ou igual a m/2, considere o limite superior, então seus irmãos, pais e ele próprio usam o método de transposição pai-filho para alcançar o equilíbrio 3. Não há irmãos suficientes: o número de palavras-chave excluídas = m/2 e o limite superior é -1. Neste momento, os nós de seus irmãos esquerdo e direito (adjacentes) também são = m/2 e o limite superior. é 1. Depois da exclusão, as palavras-chave serão mescladas com as palavras-chave no nó irmão esquerdo (direito) e no nó pai. O número de palavras-chave no nó pai será reduzido em um. o nó raiz pode ser reduzido diretamente para 0 (exclua o nó raiz).

Propriedades relacionadas à árvore B É necessário compreender a relação entre o número de palavras-chave e o número de subárvores: o número de palavras-chave é 1 a menos que o número de subárvores. Todos os nós não terminais, exceto o nó raiz, têm pelo menos m/2 subárvores de limite superior (m/2 limite superior - 1 palavra-chave) As palavras-chave nos nós são ordenadas em ordem crescente, da esquerda para a direita. Ou seja, m/2 assume o limite superior -1≤n≤m-1, ou seja, [m/2 assume o limite superior -1, m-1]

A árvore B é uma árvore deformada da árvore B que aparece em resposta às necessidades do banco de dados. Uma árvore B de ordem m satisfaz as seguintes condições: 1. Cada nó de ramificação possui no máximo m subárvores 2. O nó raiz não folha tem pelo menos duas subárvores 3. O número de subárvores de um nó é igual ao número de palavras-chave 4. Todos os nós folha contêm todas as palavras-chave e ponteiros para os registros correspondentes. As palavras-chave são organizadas em ordem de tamanho nos nós folha, e os nós folha adjacentes são conectados uns aos outros em ordem de tamanho.

Principais diferenças das árvores B: 1. Um nó com n palavras-chave na árvore B possui n subárvores, e cada palavra-chave corresponde a uma subárvore que n nós de palavras-chave na árvore B contêm n-1 subárvores; 2. O intervalo do número n de palavras-chave para cada nó na árvore B é [m/2 leva o limite superior, m] (em relação aos limites superior e inferior do número n de palavras-chave do nó na árvore B mais 1 ); nó raiz B: [1,m],B:[1,m-1] 3. Na árvore B, os nós folha contêm informações (todas as palavras-chave) e os nós não folha servem apenas como índices. 4. Cada pesquisa na árvore B, bem-sucedida ou não, é um caminho do nó raiz ao nó folha.

Devido à tabela linear anterior e à pesquisa em árvore, não existe uma relação definida entre a posição do registro na tabela e a chave do registro. Portanto, ao buscar registros nessas tabelas, é necessário comparar uma série de palavras-chave. Esse método de busca é baseado na comparação, e a eficiência da busca depende do número de comparações. Função hash: A função Hash(key)=Addr que mapeia as palavras-chave da tabela de consulta para o endereço correspondente à palavra-chave, ou seja, utilizando as características da própria palavra-chave e utilizando o mínimo possível de busca de "comparação". A função hash pode mapear várias palavras-chave diferentes para o mesmo endereço, o que é chamado de 'colisão'. Essas diferentes palavras-chave que colidem são chamadas de sinônimos. Por um lado, uma função hash bem projetada minimizará os conflitos; por outro lado, os conflitos são inevitáveis ​​e devem ser projetados métodos para lidar com eles; Tabela hash: Uma estrutura de dados que é acessada diretamente com base em palavras-chave. Em outras palavras, a tabela hash estabelece uma relação de mapeamento direto entre palavras-chave e endereços de armazenamento. Idealmente, a complexidade de tempo de pesquisa em uma tabela hash é O(1), o que significa que não tem nada a ver com o número de elementos.

1. O domínio de definição da função hash deve incluir todas as chaves de armazenamento, e o intervalo de valores depende do tamanho ou intervalo de endereços da tabela hash, 2. Os endereços calculados pela função hash devem ser distribuídos uniformemente em todo o espaço de endereçamento com igual probabilidade, reduzindo assim a ocorrência de conflitos. 3. A função hash deve ser o mais simples possível e pode calcular o hash correspondente a qualquer palavra-chave em um curto espaço de tempo.

Sequência ordenada L[1..i-1]L(i) Sequência não ordenada L[i 1…n] void InsertSort(ELemType A[],int n){ int eu,j; for(i=2;i<=n;i){//Insira os seguintes números n-1 na frente if(A[i]<A[i-1]){ A[0] = A[i];//Copia como sentinela, A[0] não armazena nenhum elemento for(j=i-1;A[0]<A[j];j--){//Encontre a posição de inserção de trás para frente A[j 1] = A[j]; A[j 1] = A[0]; } } Complexidade espacial O(1), complexidade espacial O(n^2) Melhor caso: os elementos da tabela já estão classificados, tempo O(n) Pior caso: a ordem dos elementos na tabela é invertida, tempo O(n^2) Como cada comparação é de trás para frente, ela é estável. Adequado para listas sequenciais e listas vinculadas (você pode encontrar a posição do elemento especificada da frente para trás) Adequado para tabelas de classificação basicamente ordenadas com pequena quantidade de dados

void InsertSort(ElemType A[],int n){ int i,j,baixo,alto,médio; para(i=2;i<=n;i ){ A[0] =A[i]; baixo=1; alto=i-1; enquanto(baixo<=alto){ médio = (baixo alto)/2; if(A[meio]>A[0])alto=meio-1; senão baixo = médio 1; } para (j=i-1;j>=alto 1;j--) A[j 1] = A[j]; A[alto 1]=A[0]; } } Complexidade de tempo O (n ^ 2) O número de comparações não tem nada a ver com o estado inicial da lista a ser ordenada e depende apenas do número n de elementos da lista; O número de movimentos está relacionado ao estado inicial da lista a ser ordenada

Primeiro divida a tabela de classificação em várias subtabelas (registros com o mesmo incremento separados formam uma subtabela di 1 = di/2, e o último incremento é igual a 1), execute a classificação por inserção direta em cada subtabela, quando a tabela inteira Quando os elementos estão basicamente em ordem, uma classificação por inserção direta é executada em todos os registros. void ShellSort(ELemType A[],int n){ //A[0] é uma unidade de armazenamento temporário, não uma sentinela. Quando j<=0, a posição de inserção é alcançada. for(dk=n/2;dk>=1;dk/=2)//alteração do tamanho do passo para(i=di 1;i<=n;i) if(A[i]<A[i-dk]){//A[i] precisa ser inserido na subtabela incremental ordenada A[0]=A[j];//armazenado temporariamente em A[0] para(j=i-dk;j>0&&A[0]<A[j];j-=dk) A[j dk]=A[j]; } } Não há uma conclusão definitiva sobre a complexidade do tempo, mas acredita-se que seja O(n^2) Classificando instabilidade Adequado para tabela de sequência

Compare os valores dos elementos adjacentes de trás para frente (de frente para trás) e troque-os se estiverem na ordem inversa. Palavras-chave flutuam gradualmente na superfície como bolhas void BubbleSort(ELemType A[],int n){ for(int i=0;i<n-1;i){//n-1 vezes bandeira = falso; para(j=n-1;j>i;j--) if(A[j-1]>A[j]){//Se for ordem inversa trocar(A[j-1],A[j]); bandeira = verdadeiro; } if(flag==false)//O sinalizador do fim da classificação por bolha: nem uma única troca retornar; } } Espaço O(1), tempo O(n^2) Estabilidade: os elementos não serão trocados quando forem iguais, estáveis A sequência produzida pela classificação por bolha é ordenada globalmente, o que não é equivalente à ordenação local da classificação por inserção.

Escolha qualquer elemento na lista para ser classificado como pivô (geralmente o primeiro elemento) e divida a sequência classificada em duas partes independentes L[1..k-1] L(k) L[k 1, ...n] , de modo que a primeira metade seja menor que o pivô e a segunda metade seja maior que o pivô, e o pivô seja colocado na posição final L (k). Este processo é chamado de classificação rápida de uma passagem (divisão de uma passagem). void QuickSort(ELemType A[],int baixo,int alto){ if(low<high){//Condição para salto recursivo int pivotpos = Partição(A,baixa,alta);//Partição QuickSort(A,baixo,pivotpos-1); QuickSort(A,pivotpos 1,alto); } } O desempenho e a chave do algoritmo de classificação rápida vêm da operação de partição. Aqui, o primeiro elemento é usado como pivô para particionamento. int Partition(ElemType A[],int baixo,int alto){ ElemType pivô=A[baixo]; while(low<high){//Condição de saída do loop while(baixo<alto && A[alto]>=pivô) --alto; A[baixo]=A[alto]; whilie(baixo<alto && A[baixo]<=pivô) baixo; A[alto] = A[baixo]; } A[baixo] = pivô; retornar baixo; } Espaço: requer pilha de trabalho recursiva, de preferência O(log2n), média O(log2n) (dividida ao meio tanto quanto possível, como uma árvore binária completa), Pior caso O(n) (o número de elementos nas duas áreas divididas é n-1 e 0, são necessárias n-1 chamadas recursivas e a profundidade da pilha é O(n)). Tempo: O tempo de execução da classificação rápida está relacionado ao fato de a divisão ser simétrica. O pior caso é metade n-1 e metade 0. A assimetria máxima ocorre em cada nível de recursão, que corresponde à sequência ordenada inicial (sequencial ou reversa). ordem), é O (n ^ 2) Estabilidade: Instável, os mesmos elementos serão transferidos para partes diferentes e as posições relativas serão alteradas. Nota: A classificação rápida não produz uma subsequência ordenada, mas o elemento pivô é colocado na posição final em cada passagem. Melhore a eficiência: 1. Selecione elementos pivôs que possam dividir a sequência tanto quanto possível 2. Selecione aleatoriamente elementos pivôs A divisão mais ideal: ambos os problemas de palavras são menores que n/2, o tempo é O(nlog2n) e o tempo de execução da classificação rápida é muito próximo do melhor caso, em média. Quicksort é o algoritmo de classificação com melhor desempenho médio entre todos os algoritmos de classificação interna.

void SelectSort(ElemType A[],int n){ for(i=0;i<n-1;i)//Um total de n-1 vezes min=i;//Registra a posição mínima do elemento para(j=i 1;j<n;j) if(A[j]<A[min]) min = j; if(min!=i) troca(A[i],A[min]); } } Espaço O(1), tempo O(n^2) Estabilidade: pode fazer com que a posição relativa das palavras-chave contendo os mesmos elementos mude, o que é instável.

O heap é um objeto array de uma árvore. Um array unidimensional pode ser considerado como uma árvore binária completa, que satisfaz as propriedades. 1.L(i)>=L(2i) e L(i)>=L(2i 1) ou 2.L(i)<=L(2i) e L(i)<=L(2i 1) ( 1<=i<=n/2 (tomar o limite); Aqueles que satisfazem 1. são considerados como grandes pilhas de raiz (grandes pilhas superiores), e aqueles que satisfazem 2. são considerados como pequenas pilhas de raiz (pequenas pilhas superiores). Classificação de heap: primeiro, n elementos na matriz são construídos em um heap inicial após a saída do elemento superior do heap, o elemento inferior do heap é enviado para o topo do heap. atende às propriedades de uma grande pilha raiz e a pilha é destruída. O elemento superior da pilha é movido para o topo da pilha, ajustando-o para baixo para que possa continuar a manter a natureza de uma grande pilha superior. Em seguida, produza o elemento superior da torre e repita até que reste apenas um elemento na pilha. Algoritmo de classificação de heap: void HeapSort(ElemType A[],int len){ BuildMaxHeap(A,len); for(i=len;i>1;i--){ Swap(A[i],A[1]);//Sai do elemento superior do heap e o troca com o elemento inferior do heap HeadAdjust(A,1,i-1);//Organiza os elementos i-1 restantes em uma pilha } } A classificação de heap é adequada para situações onde existem muitas palavras-chave (na ordem de centenas de milhões) Exemplo: para selecionar os 100 valores máximos principais entre 100 milhões de números, primeiro use uma matriz de 100, leia os primeiros 100 números e construa um pequeno heap superior e, em seguida, leia os números restantes em sequência, se forem menores que. o topo da pilha, descarte-os. Caso contrário, substitua o topo da pilha por este número e redimensione a pilha. Após a leitura dos dados, os 100 números na pilha são os necessários. Eficiência espacial O(1), eficiência temporal O(nlog2n) instável

Supondo que a tabela a ser classificada contém n registros, ela pode ser considerada como n subtabelas ordenadas, cada uma com comprimento 1, e então mescladas em pares para obter n/2 registros com limite superior com comprimento 2 ou 1. Lista de sequências; continue mesclando dois por dois até mesclar em uma lista ordenada de comprimento n. Este método é chamado de classificação por mesclagem bidirecional. ElemType *B=(ElemType*)malloc((n 1)*sizeof(ElemType));//matriz auxiliar B void Merge(ElemType A[],int baixo,int médio,int alto){ //Tabela A[low..mid]A[mid 1..high] estão ordenadas, mescle-as em uma lista ordenada for(int k=baixo;k<=alto;k) B[k]=A[k]; for(i=low;j=mid 1;k=i,i<=mid&&j<=high;k ){ if(B[i]<=B[j]) A[k]=B[i ]; senão A[k]=B[j]; } enquanto(i<=meio) A[k ]=B[i ]; enquanto(j<=alto) A[k ]=B[j ]; } void MergeSort(ELemType A[],int baixo,int alto){ if(baixo<alto){ int médio=(baixo alto)/2; MergeSort(A, baixo, médio); MergeSort(A,médio 1,alto); Mesclar(A,baixo,médio,alto); } } Eficiência espacial: n unidades de espaço auxiliar, complexidade espacial O(n) Eficiência de tempo: cada mesclagem é O(n) e as mesclagens de limite superior log2n são necessárias. A complexidade de tempo do algoritmo é O(nlog2n). Estabilidade: A operação Merge() não alterará a ordem relativa dos registros com as mesmas palavras-chave, estável

Classifique com base no tamanho da palavra-chave. A palavra-chave de cada nó aj consiste em d tuplas, kd-1j é a palavra-chave primária e kj0 é a palavra-chave secundária. Para obter a classificação de várias palavras-chave, geralmente existem dois métodos: 1. Primeiro o bit mais significativo (MSD), divida várias subsequências menores, camada por camada, de acordo com o peso decrescente das palavras-chave e, finalmente, todas as subsequências são conectadas em uma sequência ordenada. 2. O dígito mais baixo primeiro (LSD), classificado em ordem crescente pelo peso da palavra-chave para formar uma sequência ordenada. operar: 1. Distribuição: Deixe a fila Q0...Qr-1 vazia e, em seguida, adicione-a à fila correspondente de acordo com o bit correspondente de cada nó. 2. Coleta: Conecte os nós da fila de Q0..Qr-1 de ponta a ponta para obter uma nova sequência de nós para formar uma nova tabela linear. Exemplo: para classificar sequências abaixo de 1000, primeiro determine a base r (pode ser considerada como r base). A base de 1000 é 10, portanto, 10 filas de cadeia são necessárias durante o processo de classificação. Números abaixo de 1000 têm três dígitos, portanto são necessárias três operações de "distribuição" e "coleta"; todos os registros com a mesma palavra-chave mais baixa (dígito de unidades) são atribuídos a uma fila e, em seguida, a operação de "coleta" é executada. Eficiência de espaço: O espaço de armazenamento auxiliar necessário para uma viagem de classificação é r (r filas: r ponteiros de cabeça de fila, r ponteiros de cauda de fila), O (r) Eficiência de tempo: d passagens de alocação e coleta, uma passagem de alocação requer O(n), uma passagem de coleta requer O(r), a complexidade de tempo é O(d(n r)), independentemente do estado inicial da sequência . Estabilidade: a classificação Radix em si exige que a classificação bit a bit seja estável, portanto, é estável!

1. Se n for pequeno, a classificação por inserção direta ou a classificação por seleção simples podem ser usadas. Como a classificação por inserção direta requer mais movimentos de registro do que a classificação por seleção simples, quando o próprio registro contém uma grande quantidade de informações, a classificação por seleção simples é melhor. 2. Se o estado inicial do arquivo for basicamente ordenado por palavras-chave, é apropriado usar inserção direta ou classificação por bolha. 3. Se n for grande, use o método de classificação O (nlog2n): classificação rápida, classificação por heap ou classificação por mesclagem. A classificação rápida é considerada o melhor método de classificação interna baseada em comparação no momento. Quando as palavras-chave a serem classificadas são distribuídas aleatoriamente, a classificação rápida tem o tempo médio mais curto e requer menos espaço auxiliar do que a classificação rápida, e a classificação rápida irá. não ocorrer. Mas ambas as classificações são instáveis. Se um algoritmo O(nlog2n) estável for necessário, a classificação por mesclagem será usada, mas a mesclagem de pares de um único registro não é recomendada. Eles geralmente podem ser usados ​​em combinação com a classificação por inserção direta: primeiro use a classificação por inserção direta para obter subdivisões ordenadas mais longas. arquivos e, em seguida, mescle-os dois por dois. A classificação por inserção direta é estável e a classificação por mesclagem aprimorada também é estável. 4. No método de classificação baseado em comparação, após cada comparação de dois tamanhos de palavras-chave, ocorrem apenas duas transferências possíveis. Portanto, uma árvore binária pode ser usada para descrever o processo de decisão de comparação. Quando as palavras-chave são distribuídas aleatoriamente, qualquer algoritmo de classificação que dependa de "comparação" requer pelo menos tempo O(nlog2n). 5. Se n for muito grande e o número de palavras-chave registradas for pequeno e puder ser decomposto, é melhor usar a classificação radix. 6. Quando o próprio registro contém uma grande quantidade de informações, para evitar gastar muito tempo movimentando o registro, uma lista vinculada pode ser usada como estrutura de armazenamento

A classificação realizada na memória é chamada de classificação interna. Em muitos aplicativos, arquivos grandes precisam ser classificados e o arquivo inteiro não pode ser copiado para a memória para classificação. Portanto, os registros a serem classificados precisam ser armazenados na memória externa. Durante a classificação, os dados são transferidos para a memória parte por parte para classificação. Durante o processo de classificação, são necessárias múltiplas trocas entre a memória e o armazenamento externo. Essa classificação é chamada de classificação externa

O tempo gasto durante o processo de classificação externa considera principalmente o número de acessos ao disco, ou seja, o número de IOs A classificação externa geralmente usa classificação por mesclagem: 1. De acordo com o tamanho do buffer de memória, divida os arquivos no armazenamento externo em subarquivos de comprimento l, leia-os na memória em sequência e use o método de classificação interna para classificá-los e grave os subarquivos ordenados obtidos após a classificação de volta para o armazenamento externo, esses subarquivos ordenados são chamados de segmentos mesclados ou sequências sequenciais; 2. Mescle esses segmentos mesclados um por um para que os segmentos mesclados aumentem gradualmente de pequeno para grande até que todo o arquivo ordenado seja obtido. A fusão de uma passagem refere-se à fusão de todos os segmentos do mesmo nível atual em um Tempo total de classificação externa = tempo necessário para classificação interna, tempo de leitura e gravação de informações externas, tempo necessário para fusão interna O tempo para leitura e gravação de informações de armazenamento externo é muito maior do que o tempo para classificação interna e fusão interna. A leitura e gravação de informações de armazenamento externo é baseada em "blocos de disco". bloco de disco a ser lido e gravado diversas vezes Portanto, o número total de leituras e gravações necessárias: 2*número total de registros/número de registros em um bloco de disco*n (número de vezes) número total de registros/número de registros. em um bloco de disco (a classificação interna também requer leitura e gravação completas) Para r segmentos de fusão iniciais, execute a fusão balanceada de k vias. A altura da árvore (árvore k-ária invertida) = logkr e o limite superior = o número de passagens de fusão S. Pode-se observar que aumentar o número de caminhos de mesclagem k ou reduzir o número de segmentos de mesclagem iniciais r pode reduzir o número de passagens de mesclagem S, reduzindo assim o número de E/Ss de disco e melhorando a velocidade da classificação externa.

Aumentar o número de caminhos de fusão k pode reduzir o número de passagens de fusão S, mas aumentará o tempo de fusão interno. Ao mesclar internamente, selecionar a menor palavra-chave entre k elementos requer comparações k-1, e palavras-chave n-1 precisam ser comparadas. Cada mesclagem de n elementos requer (n-1)(k-1) comparações, S vezes. o número de comparações necessárias para a fusão é S(n-1)(k-1)=log2r pega o limite superior (n-1)(k-1)/log2k pega o limite superior, onde (k-1)/log2k pega o limite superior e cresce com o crescimento de k. Portanto, o algoritmo de classificação por mesclagem interna comum não pode ser usado.

Para reduzir r, r=n/l assume um limite superior, então precisamos encontrar uma maneira de gerar um segmento de mesclagem inicial mais longo l. Suponha que o arquivo inicial a ser classificado seja FI, o arquivo de saída do segmento de mesclagem inicial seja FO, a área de trabalho da memória seja WA, FO e WA estejam inicialmente vazios e WA possa acomodar w registros. As etapas do algoritmo de seleção de substituição são as seguintes: 1. Insira w registros do FI para o espaço de trabalho WA 2. Selecione o registro com o valor mínimo da palavra-chave de WA e registre-o como MINIMAX 3. Grave MINIMAX em FO 4. Se FI não estiver vazio, envie o próximo registro de FI para WA 5. Selecione o menor registro de palavra-chave de todos os registros em WA com palavras-chave maiores que as palavras-chave do registro MINIMAX como o novo registro MINIMAX. 6. Repita as etapas 3 a 5 até que nenhum novo MINIMAX possa ser selecionado em WA, obtenha um segmento de mesclagem inicial e envie um sinalizador final do segmento de mesclagem para FO. 7. Repita as etapas 2 a 6 até que WA esteja vazio e todos os segmentos mesclados iniciais sejam obtidos. O processo de seleção da gravação MINIMAX no WA requer o uso de árvores perdedoras.

Depois que o arquivo é classificado por seleção de substituição, são obtidos segmentos iniciais mesclados de diferentes comprimentos. Como organizar a ordem de fusão dos segmentos iniciais de fusão com comprimentos diferentes para minimizar o número de IOs? Desenhe a árvore de mesclagem correspondente. O comprimento do caminho ponderado WPL da árvore é o número total de registros lidos durante o processo recursivo. Estenda a ideia da árvore de Huffman para o caso da árvore k-ária. Na árvore de mesclagem, deixe o segmento de mesclagem inicial com um pequeno número de registros ser mesclado primeiro e o segmento de mesclagem inicial com um grande número de registros. mesclado por último. O IO total pode ser estabelecido A melhor árvore de mesclagem com o menor número de vezes. Método para construir a melhor árvore de mesclagem: Se o segmento de mesclagem inicial não for suficiente para formar uma árvore k-ária estrita, um "segmento virtual" com comprimento 0 precisa ser adicionado. Como determinar o número de segmentos virtuais a serem adicionados? Uma árvore k-ária estrita tem n0=(k-1)nk 1. Se (n0-1)%(k-1)=0, então o livro de mesclagem k-fork pode ser construído com nk nós internos. Se (n0-1)%(k-1)=u!=0, então ku-1 segmentos de mesclagem vazios podem ser adicionados para criar uma árvore de mesclagem