📚 Documentação Completa - Estruturas de Dados

Autor: Matheus Herman Bernardim Andrade

📋 Sumário

Visão Geral do Projeto
Estruturas de Dados Implementadas
Algoritmos de Grafos
Como Executar
Estrutura do Projeto

🎯 Visão Geral do Projeto

Este repositório contém implementações educacionais de estruturas de dados fundamentais e algoritmos de grafos clássicos. O projeto foi desenvolvido com fins acadêmicos para demonstrar o funcionamento e aplicação prática de:

Estruturas de Dados Básicas: Hash Table, Árvores, Filas e Pilhas
Algoritmos de Busca em Grafos: A*, Bellman-Ford, Dijkstra e Suurballe
Análise de Desempenho: Comparações de tempo de execução e desvio padrão

As implementações estão em Java e C, com código comentado e exemplos práticos de uso.

🏗️ Estruturas de Dados Implementadas

1. Hash Table

Arquivo: HashTable.c

Linguagem: C

📖 Descrição

Hash Table (Tabela de Dispersão) é uma estrutura de dados que mapeia chaves a valores usando uma função de hash. Permite busca, inserção e remoção em tempo médio O(1).

🔑 Conceitos Principais

Função Hash: Transforma uma chave em um índice do array usando o operador módulo (chave % TAM)
Colisão: Tratada por sondagem linear (linear probing) - quando uma posição está ocupada, procura a próxima disponível
Tamanho: Tabela fixa de 20 posições (#define TAM 20)

🛠️ Estrutura de Dados

struct Dados {
   int dado;    // Valor armazenado
   int chave;   // Chave para indexação
};

⚙️ Funções Implementadas

Função	Descrição	Complexidade
`hashCode(int chave)`	Calcula o índice hash usando `chave % TAM`	O(1)
`adicionar(int chave, int dado)`	Insere um elemento na tabela	O(1) médio, O(n) pior caso
`buscar(int chave)`	Busca um elemento pela chave	O(1) médio, O(n) pior caso
`deletar(struct Dados* item)`	Remove um elemento e marca com ItemTemp	O(1) médio, O(n) pior caso
`printar()`	Exibe todos os elementos da tabela	O(n)

💡 Exemplo de Uso

O programa demonstra:

Inserção de 9 elementos com chaves e valores distintos
Busca do elemento com chave 37
Remoção do elemento encontrado
Verificação da remoção (elemento não é mais encontrado)

📊 Aplicações

Armazenamento seguro de senhas
Busca em bases de dados
Verificação de integridade de dados
Cache de informações

2. Árvores

Diretório: Arvore/src/

2.1 Árvore Binária

Arquivo: ArvoreBin.java

📖 Descrição

Árvore Binária simples implementada com uma lista sequencial. Os elementos são armazenados em níveis, onde o filho esquerdo do nó i está em 2*i+1 e o direito em 2*i+2.

🛠️ Estrutura

private List<No> arvore; // Lista que armazena os nós

⚙️ Métodos

Método	Descrição	Complexidade
`Adicionar(int novo)`	Adiciona elemento no final da lista	O(1)
`Busca(int busca)`	Busca linear por um valor	O(n)
`ObtemRaiz()`	Retorna o primeiro elemento	O(1)
`imprime()`	Exibe a árvore organizada por níveis	O(n)

2.2 Árvore de Busca Binária (BST)

Arquivo: ArvoreBusca.java

📖 Descrição

Árvore Binária de Busca (Binary Search Tree) onde cada nó segue a propriedade:

Valores menores ficam à esquerda
Valores maiores ficam à direita

Isso permite busca eficiente em O(log n) para árvores balanceadas.

🛠️ Estrutura de Nó

public class No {
    int valor;
    public No p_Esq;  // Ponteiro esquerda
    public No p_Dir;  // Ponteiro direita
}

⚙️ Métodos

Método	Descrição	Complexidade
`Adicionar(int novo)`	Insere mantendo a propriedade BST	O(log n) médio, O(n) pior
`Buscar(int busca)`	Busca binária eficiente	O(log n) médio, O(n) pior
`ImprimirCrescente(No raiz)`	Percurso in-ordem (crescente)	O(n)
`ImprimirDecrescente(No raiz)`	Percurso in-ordem reverso	O(n)

🔍 Algoritmo de Busca

1. Começa na raiz
2. Se valor < nó atual → vai para esquerda
3. Se valor > nó atual → vai para direita
4. Repete até encontrar ou chegar em null

2.3 Comparação de Desempenho

Arquivo: main.java

📖 Descrição

Programa de benchmark que compara o desempenho entre Árvore Binária e Árvore de Busca Binária.

🧪 Testes Realizados

Construção: Insere 10.000 valores aleatórios (1-100.000)
Busca: Realiza 100 buscas aleatórias
Métricas:
- Tempo total de construção
- Tempo total de busca
- Desvio padrão das buscas

📊 Resultados Esperados

Operação	Árvore Binária	Árvore de Busca
Inserção	O(1) - Rápido	O(log n) - Médio
Busca	O(n) - Lento	O(log n) - Rápido

A BST é significativamente mais rápida em buscas, mas pode ter overhead na inserção.

3. Fila (Queue)

Diretório: Fila/src/fila/

Arquivos: Fila.java, Main.java

📖 Descrição

Implementação de uma Fila FIFO (First In, First Out) usando ArrayList. O primeiro elemento inserido é o primeiro a ser removido.

🛠️ Estrutura

private ArrayList<String> fila;  // Capacidade máxima: 1000

⚙️ Métodos

Método	Descrição	Complexidade
`push(String s)`	Adiciona elemento no final	O(1)
`pop()`	Remove e retorna o primeiro elemento	O(n)
`isEmpty()`	Verifica se está vazia	O(1)
`isFull()`	Verifica se está cheia (1000 elementos)	O(1)

💻 Interface do Usuário (Main)

Menu interativo com opções:

Sair - Encerra o programa
Mostrar tamanho - Exibe se está vazia, cheia ou quantidade
Adicionar item - Insere uma string na fila
Remover item - Remove o primeiro da fila

📊 Aplicações

Gerenciamento de processos em sistemas operacionais
Buffer de impressão
Fila de atendimento
Processamento de mensagens

4. Pilha (Stack)

Diretório: Pilha/src/

Arquivos: Pilha.java, Main.java

📖 Descrição

Implementação de uma Pilha LIFO (Last In, First Out) usando ArrayList. O último elemento inserido é o primeiro a ser removido.

🛠️ Estrutura

private ArrayList<String> pilha;  // Capacidade máxima: 1000

⚙️ Métodos

Método	Descrição	Complexidade
`push(String s)`	Adiciona elemento no topo	O(1)
`pop()`	Remove e retorna o elemento do topo	O(1)
`isEmpty()`	Verifica se está vazia	O(1)
`isFull()`	Verifica se está cheia (1000 elementos)	O(1)

💻 Interface do Usuário (Main)

Menu interativo com opções:

Sair - Encerra o programa
Mostrar tamanho - Exibe se está vazia, cheia ou quantidade
Adicionar dado - Insere uma string na pilha
Remover dado - Remove o topo da pilha

📊 Aplicações

Avaliação de expressões matemáticas
Histórico de navegação (voltar/avançar)
Recursão em algoritmos
Desfazer/Refazer em editores

⚖️ Diferença entre Fila e Pilha

Característica	Fila (FIFO)	Pilha (LIFO)
Inserção	No final	No topo
Remoção	Do início	Do topo
Pop()	O(n)	O(1)
Analogia	Fila de banco	Pilha de pratos

🔀 Algoritmos de Grafos

5. Algoritmo A* (A-Star)

Diretório: A/

Arquivos: Main.java, No.java

📖 Descrição

O Algoritmo A* é um método de busca heurístico que encontra o caminho mais curto em um grafo. É amplamente usado em jogos, GPS e robótica.

🧠 Conceito Principal

A* avalia cada nó através da função:

f(n) = g(n) + h(n)

Onde:

g(n): Custo real do caminho do início até o nó n
h(n): Estimativa heurística do custo de n até o objetivo
f(n): Custo total estimado

🛠️ Estrutura de Nó

public class No implements Comparable<No> {
    public int id;                    // Identificador único
    public No raiz;                   // Nó pai no caminho
    public List<Aresta> vizinho;      // Lista de adjacência
    public double f;                  // f(n) = g(n) + h(n)
    public double g;                  // Custo do caminho
    public double h;                  // Heurística
}

⚙️ Algoritmo

Adiciona o nó inicial na lista aberta
Remove nó com menor f(n) da lista aberta
Se é o objetivo → reconstrói caminho
Senão, para cada vizinho:
- Calcula novo g(n)
- Se melhor caminho → atualiza f(n) e raiz
Move nó para lista fechada
Repete até encontrar objetivo

💡 Exemplo no Código

Grafo: 4 → n1(6) → n2(1) → objetivo
       4 → n2(4) → objetivo(4)
       4 → n3(1) → n4(3) → objetivo
       4 → n4(5)

Saída: 4 1 3 4 (caminho ótimo)

📊 Características

Completo: Sempre encontra solução se existir
Ótimo: Encontra o melhor caminho com heurística admissível
Eficiente: Melhor que busca em largura/profundidade
Complexidade: O(b^d) onde b=ramificação, d=profundidade

6. Algoritmo de Bellman-Ford

Arquivo: Shortest Path/Java/Bellman-Ford/src/Bellman.java

📖 Descrição

Algoritmo que encontra o caminho mais curto em grafos com pesos negativos. Detecta ciclos negativos que impossibilitam a solução.

🔑 Características Principais

✅ Aceita pesos negativos
✅ Detecta ciclos negativos
❌ Mais lento que Dijkstra: O(V·E)
✅ Garante caminho ótimo

⚙️ Algoritmo

1. Inicializa distâncias com infinito, exceto origem (0)
2. Para cada nó (n-1 vezes):
   - Para cada aresta (u, v):
     - Se dist[u] + peso(u,v) < dist[v]:
       - dist[v] = dist[u] + peso(u,v)
       - anterior[v] = u
3. Verifica ciclos negativos (mais uma iteração)
4. Reconstrói caminho do fim ao início

💻 Implementação

Grafo gerado:

30 nós (0-29)
Cada nó tem 0-4 conexões aleatórias
Pesos entre 1-20 (aleatórios)
Infinito (9999) para sem conexão

Saída:

Caminho do nó 1 ao nó 30
Lista de todas as arestas e custos

📊 Complexidade

Operação	Complexidade
Tempo	O(V · E)
Espaço	O(V)

Onde V = vértices, E = arestas

🆚 Quando usar Bellman-Ford vs Dijkstra?

Bellman-Ford	Dijkstra
Pesos negativos	Apenas positivos
O(V·E)	O((V+E)log V)
Detecta ciclos	Não detecta

7. Algoritmo de Dijkstra

Arquivo: Shortest Path/Java/Djikstra/src/Dijkstra.java

📖 Descrição

Algoritmo clássico para encontrar o caminho mais curto em grafos com pesos não-negativos. Mais eficiente que Bellman-Ford quando não há pesos negativos.

🔑 Características Principais

❌ Não aceita pesos negativos
✅ Mais rápido: O((V+E)log V)
✅ Algoritmo guloso (greedy)
✅ Garante caminho ótimo

⚙️ Algoritmo

1. Inicializa:
   - Distância da origem = 0
   - Demais distâncias = infinito
   - Todos nós não visitados
   
2. Enquanto houver nós não visitados:
   - Seleciona nó não visitado com menor distância
   - Marca como visitado
   - Para cada vizinho não visitado:
     - Calcula dist_tentativa = dist[atual] + peso(atual, vizinho)
     - Se dist_tentativa < dist[vizinho]:
       - Atualiza dist[vizinho]
       - Atualiza anterior[vizinho]
       
3. Reconstrói caminho seguindo os anteriores

💻 Implementação

Estruturas usadas:

visitedNode: Lista de nós já processados
unvisitedNode: Lista de nós pendentes
distance[]: Menor distância conhecida até cada nó
previous[]: Nó anterior no caminho ótimo

Grafo gerado:

30 nós (0-29)
Conexões aleatórias (0-4 por nó)
Pesos entre 1-20
Verifica ausência de pesos negativos antes de executar

Saída:

Caminho do nó 1 ao nó 30
Lista de todas as conexões e custos

📊 Complexidade

Implementação	Complexidade
Array simples	O(V²)
Min-heap	O((V+E)log V)
Fibonacci heap	O(E + V log V)

Nota: Este código usa array simples (O(V²))

🎯 Passo a Passo Exemplo

Grafo: 1 --5--> 2
       1 --2--> 3
       2 --1--> 4
       3 --6--> 4

1. Início: dist[1]=0, demais=∞
2. Visita 1: dist[2]=5, dist[3]=2
3. Visita 3: dist[4]=8 (2+6)
4. Visita 2: dist[4]=6 (5+1) ✓ melhor!
5. Caminho: 1 → 3 → 2 → 4 (custo 6)

8. Algoritmo de Suurballe

Arquivo: Shortest Path/Java/Suurballe/src/Suurballe.java

📖 Descrição

Algoritmo avançado que encontra dois caminhos disjuntos de menor custo em um grafo. Usado para redundância de rede e tolerância a falhas.

🎯 Objetivo

Encontrar dois caminhos do nó origem ao destino que:

Sejam os mais curtos possíveis
Não compartilhem arestas (disjuntos)
Garantam comunicação mesmo se uma aresta falhar

🔑 Etapas do Algoritmo

1ª Etapa: Encontra o primeiro caminho mais curto

firstShortestPath = Dijkstra(graph, startNode, endNode);

2ª Etapa: Modifica os pesos das arestas

modGraph[i][j] = graph[i][j] - distance[j] + distance[i];

Inverte a direção das arestas no primeiro caminho
Ajusta pesos para buscar caminhos alternativos

3ª Etapa: Encontra segundo caminho no grafo modificado

secondShortestPath = Dijkstra(modGraph, startNode, endNode);

4ª Etapa: Remove arestas comuns (em direções opostas)

// Se s1→d1 e s2→d2 são a mesma aresta invertida
if (s1 == d2 && d1 == s2)
    graph[s1][d1] = inf; // Remove do grafo

5ª Etapa: Encontra os dois caminhos disjuntos finais

firstDisjointPath = Dijkstra(graph, startNode, endNode);
// Remove arestas do primeiro caminho
secondDisjointPath = Dijkstra(graph, startNode, endNode);

🛠️ Estrutura

static final int inf = 9999;        // Infinito
static int[] distance;               // Distâncias globais
int[][] graph = new int[30][30];     // Matriz de adjacência

💻 Implementação

Grafo:

30 nós (0-29)
Grafo não-direcionado (conexões bidirecionais)
Pesos entre 0-20 (aleatórios)

Saída:

1st Path: 
1 3 7 15 30 

2nd Path: 
1 5 11 22 30

📊 Complexidade

Etapa	Operação	Complexidade
1	Dijkstra #1	O((V+E)log V)
2	Modificar pesos	O(E)
3	Dijkstra #2	O((V+E)log V)
4	Remover arestas comuns	O(V²)
5	Dijkstra #3 e #4	2 × O((V+E)log V)
Total		O(V·E log V)

🌐 Aplicações Práticas

Redes de Comunicação:
- Caminho principal e backup
- Tolerância a falhas em roteadores
Sistemas Críticos:
- Aeronaves (sistema de controle duplo)
- Usinas nucleares (redundância de segurança)
Redes de Transporte:
- Rotas alternativas em GPS
- Logística com contingência

🔍 Exemplo Visual

       2
    A ----> B
    |       |
  1 |       | 3
    |       |
    C ----> D
       4

Caminhos disjuntos:
1º: A → C → D (custo 5)
2º: A → B → D (custo 5)

💡 Por que é importante?

Confiabilidade: Se um caminho falhar, o outro continua
Balanceamento: Distribui tráfego entre rotas
Segurança: Caminhos independentes para redundância

🚀 Como Executar

Hash Table (C)

# Compilar
gcc HashTable.c -o hashtable

# Executar
./hashtable

Árvores (Java)

# Compilar
cd Arvore/src
javac *.java

# Executar
java main

Fila (Java)

# Compilar
cd Fila/src/fila
javac *.java

# Executar
java Main

Pilha (Java)

# Compilar
cd Pilha/src
javac *.java

# Executar
java Main

Algoritmo A* (Java)

# Compilar
cd A
javac *.java

# Executar
java Main

Bellman-Ford (Java)

# Compilar
cd "Shortest Path/Java/Bellman-Ford/src"
javac Bellman.java

# Executar
java Bellman

Dijkstra (Java)

# Compilar
cd "Shortest Path/Java/Djikstra/src"
javac Dijkstra.java

# Executar
java Dijkstra

Suurballe (Java)

# Compilar
cd "Shortest Path/Java/Suurballe/src"
javac Suurballe.java

# Executar
java Suurballe

📁 Estrutura do Projeto

Estrutura-De-dados/
│
├── HashTable.c                    # Hash Table em C
│
├── A/                             # Algoritmo A*
│   ├── Main.java
│   └── No.java
│
├── Arvore/                        # Árvores Binárias
│   ├── Arvore.iml
│   └── src/
│       ├── ArvoreBin.java         # Árvore Binária simples
│       ├── ArvoreBusca.java       # Árvore de Busca Binária
│       ├── main.java              # Comparação de desempenho
│       └── No.java                # Estrutura de nó
│
├── Fila/                          # Fila (Queue)
│   ├── build.xml
│   ├── manifest.mf
│   ├── build/
│   ├── nbproject/
│   └── src/
│       └── fila/
│           ├── Fila.java          # Implementação da fila
│           └── Main.java          # Interface do usuário
│
├── Grafos/                        # Grafos (binário)
│   ├── Grafos.iml
│   └── src/
│       └── Grafos.java
│
├── Pilha/                         # Pilha (Stack)
│   ├── Pilha.iml
│   └── src/
│       ├── Main.java              # Interface do usuário
│       └── Pilha.java             # Implementação da pilha
│
└── Shortest Path/                 # Algoritmos de Caminho Mínimo
    └── Java/
        ├── Description            # Descrição geral
        ├── Bellman-Ford/
        │   ├── Bellman-Ford.iml
        │   └── src/
        │       └── Bellman.java   # Algoritmo Bellman-Ford
        ├── Djikstra/
        │   ├── Djikstra.iml
        │   └── src/
        │       └── Dijkstra.java  # Algoritmo Dijkstra
        └── Suurballe/
            ├── Suubarlle.iml
            └── src/
                └── Suurballe.java # Algoritmo Suurballe

📚 Conceitos Teóricos

Complexidade de Tempo

Notação	Descrição	Exemplo
O(1)	Constante	Acesso direto por índice
O(log n)	Logarítmica	Busca binária
O(n)	Linear	Busca sequencial
O(n log n)	Linearítmica	Merge sort
O(n²)	Quadrática	Bubble sort

Estruturas de Dados - Comparação

Estrutura	Inserção	Busca	Remoção	Uso Principal
Hash Table	O(1)	O(1)	O(1)	Chave-valor rápido
Árvore BST	O(log n)	O(log n)	O(log n)	Dados ordenados
Fila	O(1)	-	O(n)	FIFO
Pilha	O(1)	-	O(1)	LIFO

Algoritmos de Grafos - Comparação

Algoritmo	Pesos Negativos	Complexidade	Melhor Uso
A*	Sim (heurística)	O(b^d)	Busca com objetivo
Bellman-Ford	✅ Sim	O(V·E)	Grafos com negativos
Dijkstra	❌ Não	O((V+E)log V)	Grafos só positivos
Suurballe	❌ Não	O(V·E log V)	Caminhos disjuntos

🎓 Objetivos Educacionais

Este projeto visa:

✅ Implementar estruturas de dados fundamentais
✅ Comparar desempenho de diferentes abordagens
✅ Aplicar algoritmos clássicos de grafos
✅ Analisar complexidade computacional
✅ Demonstrar casos de uso práticos

📝 Notas Importantes

⚠️ Hash Table: Usa sondagem linear - pode haver clustering
⚠️ Árvores: BST não balanceada - pode degenerar para O(n)
⚠️ Fila: pop() é O(n) devido a remove(0) - ineficiente
⚠️ Grafos gerados: Valores aleatórios - resultados variam
⚠️ Dijkstra: Verifica pesos negativos antes de executar

🔧 Possíveis Melhorias

Hash Table

Implementar re-hashing dinâmico
Usar encadeamento para colisões

Árvores

Implementar AVL ou Red-Black para balanceamento
Adicionar operação de remoção na BST

Fila

Usar índices ao invés de remove(0) (O(1) ao invés de O(n))
Implementar fila circular

Algoritmos

Adicionar visualização gráfica dos caminhos
Implementar A* bidirecional
Paralelizar Bellman-Ford

📖 Referências

Cormen, T. et al. Introduction to Algorithms (CLRS)
Sedgewick, R. Algorithms (4th Edition)
Hart, P. E. et al. A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968)
Dijkstra, E. W. A Note on Two Problems in Connexion with Graphs (1959)
Bellman, R. On a Routing Problem (1958)
Suurballe, J. W. Disjoint Paths in a Network (1974)

👨‍💻 Autor

Matheus Herman Bernardim Andrade

📜 Licença

Este projeto foi desenvolvido para fins educacionais.

Última atualização: Janeiro 2026

Name		Name	Last commit message	Last commit date
A*		A*
Arvore		Arvore
Fila		Fila
Grafos		Grafos
Pilha		Pilha
Shortest Path/Java		Shortest Path/Java
HashTable.c		HashTable.c
README.md		README.md

Latest commit

History

Folders and files

Repository files navigation

📚 Documentação Completa - Estruturas de Dados

📋 Sumário

🎯 Visão Geral do Projeto

🏗️ Estruturas de Dados Implementadas

1. Hash Table

📖 Descrição

🔑 Conceitos Principais

🛠️ Estrutura de Dados

⚙️ Funções Implementadas

💡 Exemplo de Uso

📊 Aplicações

2. Árvores

2.1 Árvore Binária

📖 Descrição

🛠️ Estrutura

⚙️ Métodos

2.2 Árvore de Busca Binária (BST)

📖 Descrição

🛠️ Estrutura de Nó

⚙️ Métodos

🔍 Algoritmo de Busca

2.3 Comparação de Desempenho

📖 Descrição

🧪 Testes Realizados

📊 Resultados Esperados

3. Fila (Queue)

📖 Descrição

🛠️ Estrutura

⚙️ Métodos

💻 Interface do Usuário (Main)

📊 Aplicações

4. Pilha (Stack)

📖 Descrição

🛠️ Estrutura

⚙️ Métodos

💻 Interface do Usuário (Main)

📊 Aplicações

⚖️ Diferença entre Fila e Pilha

🔀 Algoritmos de Grafos

5. Algoritmo A* (A-Star)

📖 Descrição

🧠 Conceito Principal

🛠️ Estrutura de Nó

⚙️ Algoritmo

💡 Exemplo no Código

📊 Características

6. Algoritmo de Bellman-Ford

📖 Descrição

🔑 Características Principais

⚙️ Algoritmo

💻 Implementação

📊 Complexidade

🆚 Quando usar Bellman-Ford vs Dijkstra?

7. Algoritmo de Dijkstra

📖 Descrição

🔑 Características Principais

⚙️ Algoritmo

💻 Implementação

📊 Complexidade

🎯 Passo a Passo Exemplo

8. Algoritmo de Suurballe

📖 Descrição

🎯 Objetivo

🔑 Etapas do Algoritmo

🛠️ Estrutura

💻 Implementação

📊 Complexidade

🌐 Aplicações Práticas

🔍 Exemplo Visual

💡 Por que é importante?

🚀 Como Executar

Hash Table (C)

Árvores (Java)

Fila (Java)

Pilha (Java)

Algoritmo A* (Java)