Estrutura de Dados

Em palavras simples

Um vetor, uma fila e uma pilha podem guardar números, mas não servem para o mesmo trabalho. A estrutura é a combinação de como os dados ficam organizados e do que se pode fazer com eles. Escolher bem evita código confuso e trabalho desnecessário.

Tecnicamente

Um Tipo Abstrato de Dados (TAD) descreve um conjunto de valores e operações sem obrigar uma implementação. Por exemplo, uma pilha define empilhar, desempilhar e consultar o topo; ela pode ser implementada por vetor ou por nós encadeados. A disciplina compara custos de tempo e memória para escolher a implementação adequada.

Principais conceitos

Estrutura de dados

Organização de dados junto às operações que permitem acessá-los e modificá-los.

TAD

Contrato de comportamento de uma estrutura, independente de como ela é guardada na memória.

Implementação

Representação concreta do TAD, como um vetor, uma lista encadeada ou uma tabela hash.

Exemplos

empilhar(A)
empilhar(B)
desempilhar() -> B
topo() -> A

Onde isso aparece na prática

• Pilhas sustentam desfazer/refazer e a validação de parênteses.
• Filas aparecem no escalonamento de processos, em buffers e em filas de impressão.
• Árvores e grafos modelam índices, sistemas de arquivos, rotas e redes.

Curiosidades

• Lista, fila e pilha são TADs; vetor e lista encadeada são possíveis representações concretas.
• A mesma operação pode ter custo diferente conforme a estrutura escolhida.

Em palavras simples

Antes de guardar dados em estruturas maiores, é preciso dominar o básico: onde o vetor começa e termina, como percorrer uma matriz e como uma função recebe dados sem copiar tudo desnecessariamente.

Tecnicamente

Vetores em C são blocos contíguos indexados de 0 a n - 1. Matrizes bidimensionais são vetores de vetores em ordem de linhas. Ao passá-los para funções, o tamanho relevante deve acompanhar os dados; nunca se deve acessar índice fora do intervalo válido.

Principais conceitos

Índice

Posição de um elemento no vetor; para n elementos válidos, vai de 0 a n - 1.

Limite

Tamanho lógico que impede ler ou escrever fora da região reservada.

Onde isso aparece na prática

• Buscar o maior valor de uma coleção.
• Representar tabelas de notas e matrizes numéricas.
• Preparar a passagem de vetores para funções de busca e ordenação.

Curiosidades

• Em C, o nome de um vetor normalmente decai para um ponteiro ao primeiro elemento quando passado a uma função.

Em palavras simples

Um arquivo é como um caderno fora da memória do programa. Para usá-lo, o programa abre o caderno, lê ou escreve e o fecha ao terminar. Se não conseguir abrir, não deve fingir que o caderno existe.

Tecnicamente

`fopen` devolve um `FILE *` ou `NULL`. Os modos mais comuns são `r` para leitura, `w` para reescrita e `a` para anexar ao final. `fgets` lê uma linha com limite de tamanho; o seu retorno deve controlar o laço. `fclose` libera o recurso e descarrega buffers pendentes.

Principais conceitos

FILE *

Ponteiro que representa o fluxo aberto pelo programa.

Modo de abertura

Regra que define se o arquivo será lido, reescrito ou complementado.

EOF

Sinal de fim de arquivo; deve ser tratado a partir do resultado de uma leitura.

Exemplos

#include <stdio.h>

int main(void) {
  FILE *arquivo = fopen("notas.txt", "r");
  char linha[256];

  if (arquivo == NULL) {
    perror("notas.txt");
    return 1;
  }

  while (fgets(linha, sizeof linha, arquivo) != NULL) {
    fputs(linha, stdout);
  }

  fclose(arquivo);
  return 0;
}

Onde isso aparece na prática

• Importar dados CSV simples.
• Ler configurações e arquivos de log.
• Gerar relatórios que pessoas podem abrir em um editor de texto.

Curiosidades

• O padrão seguro é testar o retorno da operação de leitura, não usar `feof` como condição de laço: o fim só é detectado depois de uma tentativa de leitura.

Em palavras simples

Texto guarda os símbolos que uma pessoa lê. Binário guarda os bytes que o programa usa. Isso costuma economizar espaço e permite pular diretamente para um registro, mas exige que quem lê conheça o formato.

Tecnicamente

`fwrite(ptr, tamanho, quantidade, arquivo)` grava elementos e devolve quantos foram escritos; `fread` faz o inverso. Um formato simples deve registrar metadados necessários, como a quantidade de elementos. `fseek` desloca em bytes a partir de `SEEK_SET`, `SEEK_CUR` ou `SEEK_END`; se há cabeçalho, ele precisa entrar no deslocamento.

Principais conceitos

Registro

Conjunto de bytes que representa uma entidade armazenada no arquivo.

Cabeçalho

Dados iniciais que explicam o formato, como quantidade de itens ou versão.

Acesso direto

Leitura de uma posição específica sem percorrer todos os registros anteriores.

Exemplos

#include <stdio.h>

int main(void) {
  int valores[] = { 8, 13, 21, 34 };
  size_t total = sizeof valores / sizeof valores[0];
  FILE *arquivo = fopen("valores.bin", "wb");

  if (arquivo == NULL) return 1;
  if (fwrite(&total, sizeof total, 1, arquivo) != 1 ||
      fwrite(valores, sizeof valores[0], total, arquivo) != total) {
    fclose(arquivo);
    return 1;
  }

  fclose(arquivo);
  return 0;
}

Onde isso aparece na prática

• Persistir vetores numéricos compactos.
• Guardar registros de tamanho fixo para acesso direto.
• Ler matrizes e structs quando escritor e leitor controlam o mesmo formato.

Curiosidades

• Um arquivo binário com `int` e `struct` não é automaticamente portátil entre arquiteturas: tamanho, alinhamento e ordem de bytes podem variar.

Em palavras simples

Não basta um programa funcionar para dez valores. É preciso prever o que ocorre com dez mil ou dez milhões. Complexidade é a lente que compara esse crescimento antes de executar o programa em toda escala.

Tecnicamente

A análise assintótica classifica o crescimento do número de operações ou do espaço usado para uma entrada de tamanho n. No pior caso da busca linear, até n elementos são comparados: O(n). Dois laços que percorrem uma matriz n x n executam n² vezes: O(n²). Em Big-O, constantes e termos menores não mudam a classe de crescimento.

Principais conceitos

Pior caso

Maior custo possível para uma entrada de tamanho n.

Caso médio

Custo esperado sob uma distribuição assumida de entradas.

Espaço auxiliar

Memória adicional usada além dos dados de entrada.

Big-O

Notação que limita superiormente o crescimento assintótico de um custo.

Exemplos

for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    matriz[i][j] = 0;

Onde isso aparece na prática

• Escolher busca binária para grandes coleções ordenadas.
• Estimar o impacto de laços aninhados antes de processar muitos dados.
• Comparar tempo de execução e espaço auxiliar de duas soluções corretas.

Curiosidades

• Um algoritmo assintoticamente melhor pode perder em entradas pequenas se sua constante oculta for muito alta; isso é a ideia por trás dos chamados algoritmos galáticos.

Em palavras simples

Para achar uma palavra numa lista sem ordem, você olha uma por uma. Num dicionário ordenado, abre no meio e escolhe a metade certa. A busca binária faz exatamente essa segunda estratégia.

Tecnicamente

A busca linear tem pior e caso médio O(n), melhor caso O(1). A busca binária reduz o intervalo pela metade a cada passo e tem pior caso O(log n), mas só é correta se os elementos estiverem ordenados. Busca por interpolação estima uma posição proporcional ao valor; pode ter caso médio O(log log n) para distribuição aproximadamente uniforme, mas degrada a O(n) em distribuições desfavoráveis.

Principais conceitos

Pré-condição

Condição que deve ser verdadeira antes de executar um algoritmo; na busca binária, o vetor precisa estar ordenado.

Sentinela

Valor adicional usado para reduzir uma verificação no laço, sem alterar a ordem de complexidade.

Intervalo de busca

Faixa de índices ainda candidata a conter o valor procurado.

Exemplos

int busca_binaria(const int vetor[], size_t tamanho, int valor) {
  size_t esquerda = 0;
  size_t direita = tamanho;

  while (esquerda < direita) {
    size_t meio = esquerda + (direita - esquerda) / 2;

    if (vetor[meio] == valor) return (int)meio;
    if (vetor[meio] < valor) esquerda = meio + 1;
    else direita = meio;
  }

  return -1;
}

Onde isso aparece na prática

• Localizar um id em coleção pequena ou não ordenada com busca linear.
• Consultar tabelas ordenadas e índices com busca binária.
• Estimar posições em dados numéricos distribuídos de maneira uniforme.

Curiosidades

• A busca binária é simples em ideia, mas implementações ingênuas podem errar nos limites ou causar overflow ao calcular `(esq + dir) / 2`.

Em palavras simples

Para multiplicar A por B, cada linha de A conversa com cada coluna de B. O resultado só existe quando o número de colunas de A é igual ao número de linhas de B.

Tecnicamente

Se A tem L1 x C1 e B tem L2 x C2, A x B existe somente se C1 = L2 e produz matriz L1 x C2. Cada resultado `[i][j]` é a soma de `A[i][k] * B[k][j]` para k de 0 a C1 - 1. Para matrizes quadradas n x n, os três laços executam O(n³) operações.

Principais conceitos

Compatibilidade

Condição C1 = L2 que permite multiplicar A(L1 x C1) por B(L2 x C2).

Produto escalar

Soma dos produtos entre uma linha de A e uma coluna de B.

Exemplos

#include <stdio.h>

int main(void) {
  int linhasA, colunasA, linhasB, colunasB;
  float a[50][50], b[50][50], resultado[50][50] = {0};

  scanf("%d %d", &linhasA, &colunasA);
  for (int i = 0; i < linhasA; i++)
    for (int j = 0; j < colunasA; j++) scanf("%f", &a[i][j]);

  scanf("%d %d", &linhasB, &colunasB);
  for (int i = 0; i < linhasB; i++)
    for (int j = 0; j < colunasB; j++) scanf("%f", &b[i][j]);

  if (colunasA != linhasB) {
    puts("ERRO");
    return 0;
  }

  for (int i = 0; i < linhasA; i++)
    for (int j = 0; j < colunasB; j++)
      for (int k = 0; k < colunasA; k++)
        resultado[i][j] += a[i][k] * b[k][j];

  for (int i = 0; i < linhasA; i++) {
    for (int j = 0; j < colunasB; j++) printf("%.0f ", resultado[i][j]);
    puts("");
  }
}

Onde isso aparece na prática

• Transformações gráficas e computação científica.
• Composição de relações e caminhos em grafos por matriz de adjacência.
• Exercício de leitura de entrada e validação antes do processamento.

Curiosidades

• O enunciado do VPL pede encerrar com `ERRO` quando C1 for diferente de L2; essa validação deve acontecer antes dos três laços.

Em palavras simples

Ordenar uma lista é colocar os itens numa ordem combinada, como notas da menor para a maior.

Tecnicamente

Algoritmos de ordenação podem comparar e trocar elementos, como bubble sort e selection sort. A análise deve considerar custo temporal, uso de memória, estabilidade e se o algoritmo altera o vetor original.

Principais conceitos

Estabilidade

Propriedade de preservar a ordem relativa de elementos com a mesma chave.

In-place

Algoritmo que usa pouca memória adicional e altera a própria coleção.

Onde isso aparece na prática

• Preparar dados para busca binária e relatórios ordenados.

Em palavras simples

Primeiro coloque em ordem; depois use a ordem para encontrar mais rápido.

Tecnicamente

A escolha entre ordenar e buscar linearmente depende da quantidade de buscas esperada, do custo de atualização e da necessidade de preservar a ordem de entrada.

Principais conceitos

Custo amortizado

Custo médio de uma sequência de operações, incluindo um preparo inicial como a ordenação.

Onde isso aparece na prática

• Catálogos que recebem dados em lote e são consultados muitas vezes.

Em palavras simples

A prova cobra escolher a ferramenta certa e explicar por quê, não só decorar nomes.

Tecnicamente

Revise pré-condições de algoritmos, validação de retornos de funções de arquivo, limites de vetores e classes O(1), O(log n), O(n), O(n²) e O(n³).

Principais conceitos

Pré-condição

Condição necessária antes de executar um algoritmo.

Onde isso aparece na prática

• Elaborar um roteiro de revisão com exemplos pequenos executados à mão.

Em palavras simples

Uma lista guarda itens em sequência. Quando ela usa vetor por baixo, achar uma posição é rápido, mas abrir espaço no meio exige deslocar itens.

Tecnicamente

Em vetor dinâmico, acesso por índice é O(1). Inserção ou remoção no meio pode exigir deslocar O(n) elementos. Redimensionar costuma copiar o bloco, mas pode ter custo amortizado constante em inserções no final.

Principais conceitos

Array list

Lista baseada em vetor redimensionável.

Capacidade

Quantidade de posições alocadas, que pode ser maior que o tamanho lógico.

Onde isso aparece na prática

• Coleções com muitas leituras por posição e inserções principalmente no final.

Em palavras simples

Em vez de uma fila de caixas lado a lado, cada caixa aponta para a próxima. Para chegar à caixa 20 é preciso seguir as anteriores; para encaixar uma caixa depois da atual basta trocar ligações.

Tecnicamente

Um nó normalmente contém dado e ponteiro `proximo`. Acesso por índice exige percorrer nós, O(n). Inserção após um nó conhecido e remoção do próximo podem ser O(1), desde que os ponteiros sejam atualizados sem perder referências.

Principais conceitos

Nó

Unidade que contém um valor e referências para outros nós.

Cabeça

Referência ao primeiro nó da lista.

Onde isso aparece na prática

• Filas, pilhas e coleções com inserções frequentes em posições já localizadas.

Em palavras simples

Pense numa pilha de pratos: só é possível colocar ou retirar o prato do topo.

Tecnicamente

As operações principais são `push`, `pop` e `peek`. Em implementação por vetor com topo controlado ou por lista encadeada na cabeça, essas operações podem ser O(1).

Principais conceitos

LIFO

Last In, First Out: último a entrar, primeiro a sair.

Topo

Única extremidade acessível para inserção e remoção.

Onde isso aparece na prática

• Desfazer/refazer, chamada de funções e validação de delimitadores.

Em palavras simples

A pilha ajuda quando a ordem de volta é o contrário da ordem de chegada.

Tecnicamente

Na verificação de parênteses, abre-se um delimitador com push e fecha-se com pop compatível. A pilha vazia antes do fim ou não vazia ao final indica expressão inválida.

Principais conceitos

Invariável

Propriedade que deve permanecer verdadeira durante a execução do algoritmo.

Onde isso aparece na prática

• Analisadores de expressões e editores com desfazer/refazer.

Em palavras simples

Numa fila normal, quem chega primeiro é atendido primeiro. No deque, as duas pontas ficam disponíveis.

Tecnicamente

Fila opera com inserção no fim e remoção no início. Deque generaliza a estrutura com operações em ambas as extremidades. Uma implementação circular em vetor reaproveita posições liberadas sem deslocar elementos.

Principais conceitos

FIFO

First In, First Out: primeiro a entrar, primeiro a sair.

Deque

Double-ended queue, fila com operações nas duas pontas.

Onde isso aparece na prática

• Fila de impressão, escalonamento e janelas deslizantes.

Em palavras simples

Uma árvore parece a estrutura de pastas: há uma origem e cada pasta pode levar a outras.

Tecnicamente

Em árvore enraizada, cada nó, exceto a raiz, tem um pai. Árvores binárias limitam cada nó a até dois filhos. Percursos pré-ordem, em ordem e pós-ordem visitam nós com regras diferentes.

Principais conceitos

Raiz

Nó sem pai, ponto inicial da árvore.

Folha

Nó sem filhos.

Onde isso aparece na prática

• Sistemas de arquivos, árvores de expressão e índices de banco de dados.

Em palavras simples

Um grafo é um mapa de pontos e conexões: cidades e estradas, pessoas e amizades, páginas e links.

Tecnicamente

Um grafo G = (V, E) possui conjunto de vértices V e arestas E. Pode ser direcionado ou não direcionado, ponderado ou não. Lista de adjacência economiza espaço em grafos esparsos; matriz de adjacência favorece consulta direta de ligação.

Principais conceitos

Vértice

Entidade ou ponto do grafo.

Aresta

Ligação entre dois vértices.

Onde isso aparece na prática

• Rotas, redes sociais, dependências de tarefas e redes de computadores.

Em palavras simples

Não basta mostrar que funcionou: explique qual problema o programa resolve e por que a estrutura escolhida combina com ele.

Tecnicamente

Uma apresentação técnica deve declarar requisitos, representação de dados, invariantes, casos de borda, complexidades principais e evidências de teste. Isso conecta implementação a decisão de projeto.

Principais conceitos

Caso de borda

Entrada válida extrema ou especial que frequentemente revela falhas de implementação.

Onde isso aparece na prática

• Documentar e defender escolhas técnicas em equipe.

Em palavras simples

Revise qual estrutura atende cada regra de acesso: topo, frente, índice, hierarquia ou conexão.

Tecnicamente

Compare contratos e complexidades: acesso em vetor, percurso em lista encadeada, push/pop, enqueue/dequeue, percursos de árvore e representações de grafo.

Principais conceitos

Contrato de acesso

Regra que limita quais elementos podem ser lidos ou removidos em uma estrutura.

Onde isso aparece na prática

• Selecionar estrutura a partir das operações requeridas pelo problema.

Em palavras simples

Use os erros anteriores como roteiro: descubra onde a regra foi confundida e pratique um exemplo pequeno até conseguir explicá-lo.

Tecnicamente

Uma revisão eficaz alterna recuperação ativa, execução manual de algoritmos, comparação de complexidades e leitura crítica de código, especialmente validações, limites e retornos de funções.

Principais conceitos

Recuperação ativa

Técnica de tentar lembrar e resolver antes de consultar a resposta.

Onde isso aparece na prática

• Planejar estudo final por lacunas reais em vez de apenas reler resumos.