Referente e objetivo de aprendizagem
Referente: estruturas de dados em memória e suas abstrações. Problema: escolher uma organização que suporte operações e restrições de desempenho. Resultado esperado: identificar, simular e justificar uma estrutura para um caso de uso.
Como usar esta página
Explore o 5W4H, selecione um nó no knowgrama e execute operações no laboratório. O painel de estado mostra o resultado; a tabela compara custos assintóticos. As simulações são didáticas e não medem tempo real de execução.
Conhecimentos prévios
Variáveis, tipos de dados, memória, referências, funções, algoritmos, laços, condições e noções de crescimento de funções.
1 · Análise 5W4H
2 · Knowgrama de classificação
Clique em um tipo para abrir sua simulação. As categorias são perspectivas didáticas e podem se sobrepor.
organização + operações + custos
Uma tabela hash também pode ser implementada com arranjos e listas.
Distinção importante: pilha, fila, mapa e conjunto podem ser especificados como tipos abstratos de dados; vetores, listas e árvores são organizações usadas para implementá-los.
3 · Laboratório de operações executáveis
Modelo didático: o vetor insere ao final e remove pelo valor; a lista é simplesmente encadeada; a BST não se autobalanceia; o grafo é não direcionado; a tabela hash usa encadeamento separado com cinco compartimentos. A complexidade depende da operação e da implementação.
4 · Comparação de complexidade
Notação Big-O: n = elementos; V = vértices; E = arestas; h = altura da árvore. Os valores são custos assintóticos, não tempos medidos.
| Estrutura | Buscar | Inserir | Remover | Percorrer |
|---|
* Vetor: inserção ao final com capacidade amortizada; lista: inserção no início; pilha/fila: busca não é operação central; BST: custos O(h); hash: custos esperados com distribuição adequada, pior caso O(n). Percorrer a hash visita compartimentos e elementos: O(n + m), com m compartimentos.
5 · Exemplos de aplicação e critérios de escolha
Como escolher?
Defina as operações dominantes, volume de dados, ordem necessária, mutabilidade, uso de memória, requisitos de concorrência e limites de latência. Em seguida compare alternativas e teste com cargas representativas.
Exemplo LAC: representar e navegar um knowgrama
Grafo: conceitos são vértices e relações semânticas são arestas. Tabela hash: localizar rapidamente um conceito pelo identificador. Pilha: permitir retorno ao percurso anterior. Fila: processar eventos editoriais. Árvore: apresentar uma classificação hierárquica quando essa visão for pertinente.
Um grafo de conhecimento não se reduz à estrutura de dados: exige semântica das relações, proveniência, regras de interpretação e governança.
6 · Glossário e referências
Glossário A–Z
ADT/TAD: tipo abstrato de dados, definido por operações e comportamento. Aresta: relação entre vértices. Big-O: limite superior assintótico. BFS: busca em largura. BST: árvore binária de busca. DFS: busca em profundidade. Hash: função que transforma chave em índice. LIFO: último a entrar, primeiro a sair. FIFO: primeiro a entrar, primeiro a sair. Nó: elemento de uma estrutura ligada. Referência: ligação lógica para outro objeto.
Referências para aprofundamento: Cormen et al., Introduction to Algorithms; Sedgewick e Wayne, Algorithms; Goodrich, Tamassia e Goldwasser, Data Structures and Algorithms; Open Data Structures (Pat Morin, acesso aberto).