Estruturas de Dados_ Teoria e Prática

Prévia do material em texto

Estruturas de Dados: Teoria e Prática
Uma Apostila Completa para Dominar os Conceitos
Fundamentais
Sobre esta Apostila
Este material foi desenvolvido para proporcionar uma compreensão profunda das estruturas
de dados, desde os conceitos básicos até implementações avançadas. Cada seção inclui:
Explicações detalhadas com analogias do mundo real
Exemplos práticos de código
Exercícios resolvidos e propostos
Dicas para resolução de questões
Análise de complexidade
Sumário
 Fundamentos de Estruturas de Dados
 Listas e suas Variações
 Pilhas e Filas
 Algoritmos de Ordenação
 Árvores
 Padrões de Projeto e Sub-rotinas
 Exercícios Resolvidos
 Exercícios Propostos
1. Fundamentos de Estruturas de Dados
1.1 Conceitos Básicos
O que são Estruturas de Dados?
Imagine que você está organizando uma biblioteca. Você pode empilhar todos os livros
aleatoriamente (uma estrutura caótica) ou organizá-los por autor, gênero e ordem alfabética
(uma estrutura eficiente). Estruturas de dados são exatamente isso: formas organizadas de
armazenar e gerenciar dados no computador.
Por que são importantes?
Um programa eficiente não depende apenas de bons algoritmos, mas também da escolha
correta das estruturas de dados. A estrutura errada pode fazer um programa simples
parecer lento, enquanto a estrutura certa pode fazer um programa complexo rodar
rapidamente.
1.2 Tipos de Alocação de Memória
Alocação Sequencial
Imagine um prédio onde todos os apartamentos estão um ao lado do outro no mesmo andar.
Características:
Elementos em memória contígua
Acesso direto e rápido (como encontrar o apartamento 305 diretamente)
Tamanho fixo (precisa definir previamente quantos elementos cabem)
Inserção/remoção no meio é custosa (como demolir um apartamento no meio do prédio)
Exemplo em C:
int vetor[100]; // Aloca 100 inteiros sequencialmente
Alocação Encadeada
Como um condomínio com casas espalhadas, conectadas por caminhos.
Características:
Elementos dispersos na memória
Ligados por ponteiros (como placas indicando o caminho para a próxima casa)
Tamanho dinâmico (pode crescer conforme necessário)
Inserção/remoção flexível, mas acesso sequencial
Exemplo em C:
struct Node {
 int data;
 struct Node* next;
};
2. Listas e suas Variações
2.1 Lista Sequencial
Conceito
Uma lista sequencial é como uma rua com casas numeradas sequencialmente. Cada
elemento ocupa um espaço fixo e consecutivo na memória.
Implementação Detalhada
typedef struct {
 int* elementos;
 int tamanho;
 int capacidade;
} ListaSequencial;
ListaSequencial* criarLista(int capacidade) {
 ListaSequencial* lista = malloc(sizeof(ListaSequencial));
 lista->elementos = malloc(capacidade * sizeof(int));
 lista->tamanho = 0;
 lista->capacidade = capacidade;
 return lista;
}
// Inserção no final - O(1) quando há espaço
int inserirFinal(ListaSequencial* lista, int elemento) {
 if (lista->tamanho >= lista->capacidade) {
 return 0; // Lista cheia
 }
 lista->elementos[lista->tamanho++] = elemento;
 return 1;
}
// Inserção no meio - O(n)
int inserirMeio(ListaSequencial* lista, int elemento, int posicao) {
 if (lista->tamanho >= lista->capacidade || posicao > lista->tamanho) {
 return 0;
 }
 // Desloca elementos para abrir espaço
 for (int i = lista->tamanho; i > posicao; i--) {
 lista->elementos[i] = lista->elementos[i-1];
 }
 lista->elementos[posicao] = elemento;
 lista->tamanho++;
 return 1;
}
Análise de Complexidade
Acesso direto: O(1)
Inserção/remoção no início/meio: O(n)
Inserção no final: O(1)
Busca: O(n) sequencial, O(log n) se ordenada
2.2 Lista Encadeada
Conceito
Uma lista encadeada é como uma caça ao tesouro, onde cada pista leva à próxima
localização. Cada elemento (nó) contém o dado e uma referência ao próximo elemento.
Implementação Detalhada
typedef struct Node {
 int data;
 struct Node* next;
} Node;
typedef struct {
 Node* head;
 int tamanho;
} ListaEncadeada;
ListaEncadeada* criarListaEncadeada() {
 ListaEncadeada* lista = malloc(sizeof(ListaEncadeada));
 lista->head = NULL;
 lista->tamanho = 0;
 return lista;
}
// Inserção no início - O(1)
void inserirInicio(ListaEncadeada* lista, int valor) {
 Node* novoNo = malloc(sizeof(Node));
 novoNo->data = valor;
 novoNo->next = lista->head;
 lista->head = novoNo;
 lista->tamanho++;
}
// Inserção no meio - O(1) após encontrar a posição
void inserirApos(Node* no, int valor) {
 if (no == NULL) return;
 Node* novoNo = malloc(sizeof(Node));
 novoNo->data = valor;
 novoNo->next = no->next;
 no->next = novoNo;
}
Análise de Complexidade
Acesso: O(n)
Inserção no início: O(1)
Inserção no meio: O(1) após encontrar posição
Busca: O(n)
2.3 Lista Circular
Conceito
Uma lista circular é como um carrossel: o último elemento sempre aponta para o primeiro,
formando um ciclo contínuo.
Implementação
typedef struct NodeCircular {
 int data;
 struct NodeCircular* next;
} NodeCircular;
typedef struct {
 NodeCircular* head;
} ListaCircular;
// Inserção em lista vazia
void inserirEmListaVazia(ListaCircular* lista, int valor) {
 NodeCircular* novoNo = malloc(sizeof(NodeCircular));
 novoNo->data = valor;
 lista->head = novoNo;
 novoNo->next = novoNo; // Aponta para si mesmo
}
// Inserção após um nó
void inserirApos(ListaCircular* lista, NodeCircular* no, int valor) {
 if (lista->head == NULL) {
 inserirEmListaVazia(lista, valor);
 return;
 }
 NodeCircular* novoNo = malloc(sizeof(NodeCircular));
 novoNo->data = valor;
 novoNo->next = no->next;
 no->next = novoNo;
}
3. Pilhas e Filas
3.1 Pilhas (LIFO)
Conceito
Uma pilha é como uma pilha de pratos: só podemos adicionar ou remover pratos do topo. O
último a entrar é o primeiro a sair (LIFO - Last In, First Out).
Implementação
typedef struct {
 int* elementos;
 int topo;
 int capacidade;
} Pilha;
Pilha* criarPilha(int capacidade) {
 Pilha* pilha = malloc(sizeof(Pilha));
 pilha->elementos = malloc(capacidade * sizeof(int));
 pilha->topo = -1;
 pilha->capacidade = capacidade;
 return pilha;
}
// Push - O(1)
int push(Pilha* pilha, int elemento) {
 if (pilha->topo >= pilha->capacidade - 1) {
 return 0; // Pilha cheia
 }
 pilha->elementos[++pilha->topo] = elemento;
 return 1;
}
// Pop - O(1)
int pop(Pilha* pilha) {
 if (pilha->topo elementos[pilha->topo--];
}
3.2 Filas (FIFO)
Conceito
Uma fila é como uma fila de banco: o primeiro a chegar é o primeiro a ser atendido (FIFO -
First In, First Out).
Implementação
typedef struct {
 int* elementos;
 int frente;
 int tras;
 int capacidade;
 int tamanho;
} Fila;
Fila* criarFila(int capacidade) {
 Fila* fila = malloc(sizeof(Fila));
 fila->elementos = malloc(capacidade * sizeof(int));
 fila->frente = 0;
 fila->tras = -1;
 fila->capacidade = capacidade;
 fila->tamanho = 0;
 return fila;
}
// Enfileirar - O(1)
int enfileirar(Fila* fila, int elemento) {
 if (fila->tamanho >= fila->capacidade) {
 return 0; // Fila cheia
 }
 fila->tras = (fila->tras + 1) % fila->capacidade;
 fila->elementos[fila->tras] = elemento;
 fila->tamanho++;
 return 1;
}
// Desenfileirar - O(1)
int desenfileirar(Fila* fila) {
 if (fila->tamanho == 0) {
 return -1; // Fila vazia
 }
 int elemento = fila->elementos[fila->frente];
 fila->frente = (fila->frente + 1) % fila->capacidade;
 fila->tamanho--;
 return elemento;
}
4. Algoritmos de Ordenação
4.1 Bubble Sort
Conceito
O Bubble Sort é como organizar cartas de baralho: comparamos pares adjacentes e
trocamos se estiverem fora de ordem, repetindo até que tudo esteja ordenado.
Implementação Detalhada
void bubbleSort(intarr[], int n) {
 int trocas = 0;
 int comparacoes = 0;
 
 for (int i = 0; i arr[j+1]) {
 // Troca
 int temp = arr[j];
 arr[j] = arr[j+1];
 arr[j+1] = temp;
 trocas++;
 }
 }
 }
 printf("Comparações: %d\nTrocas: %d\n", comparacoes, trocas);
}
Análise de Complexidade
Melhor caso: O(n) - array já ordenado
Pior caso: O(n²) - array em ordem inversa
Caso médio: O(n²)
5. Árvores
5.1 Árvore Binária
Conceito
Uma árvore é como uma árvore genealógica invertida: começa com um nó raiz que pode ter
até dois filhos, e cada filho pode ter seus próprios filhos.
Implementação
typedef struct NodeArvore {
 int data;
 struct NodeArvore* esquerda;
 struct NodeArvore* direita;
} NodeArvore;
NodeArvore* criarNo(int valor) {
 NodeArvore* no = malloc(sizeof(NodeArvore));
 no->data = valor;
 no->esquerda = NULL;
 no->direita = NULL;
 return no;
}
void inserir(NodeArvore** raiz, int valor) {
 if (*raiz == NULL) {
 *raiz = criarNo(valor);
 return;
 }
 if (valor data) {
 inserir(&((*raiz)->esquerda), valor);
 } else {
 inserir(&((*raiz)->direita), valor);
 }
}
6. Padrões de Projeto e Sub-rotinas
6.1 Template Method
Conceito
O Template Method é como uma receita de bolo: define os passos básicos (método
template) mas permite que diferentes tipos de bolo (subclasses) modifiquem alguns passos
específicos.
Implementação em C++
class Grafico {
protected:
 virtual void desenharEixos() = 0;
 virtual void plotarDados() = 0;
 
 void desenharTitulo() {
 // Implementação comum
 cout 51: Troca (1)
[51, 77, 11, 37, 29, 13, 21] → Comparação 77>11: Troca (2)
[51, 11, 77, 37, 29, 13, 21] → Comparação 77>37: Troca (3)
[51, 11, 37, 77, 29, 13, 21] → Comparação 77>29: Troca (4)
[51, 11, 37, 29, 77, 13, 21] → Comparação 77>13: Troca (5)
[51, 11, 37, 29, 13, 77, 21] → Comparação 77>21: Troca (6)
[51, 11, 37, 29, 13, 21, 77]
Segunda passada:
Comparações e trocas continuam…
Total de trocas: 16 trocas
Explicação: Para resolver este tipo de questão, é fundamental fazer o acompanhamento
passo a passo, marcando cada troca realizada. O número total de trocas é 16, que
corresponde à alternativa correta.
Exemplo 3: Análise de Código com Ponteiros
Questão: Analise o seguinte trecho de código:
ptr = malloc(sizeof(ptr));
if(ptr == NULL) {
 printf("Falha na alocação de memória!\n");
 return(1);
}
memset(ptr, 0x0, sizeof(*ptr));
strcpy(ptr->name, "Aluno");
ptr->idade=20;
Análise passo a passo:
 malloc(sizeof(ptr)) : Aloca memória do tamanho do ponteiro, não da estrutura
 memset(ptr, 0x0, sizeof(*ptr)) : Zera a memória alocada
 strcpy(ptr->name, "Aluno") : Copia a string para o campo name
 ptr->idade=20 : Atribui valor ao campo idade
Explicação: Este código contém um erro comum na alocação de memória. O correto seria
 malloc(sizeof(struct entrada_cadastro)) para alocar o tamanho correto da estrutura.
8. Exercícios Propostos
8.1 Lista de Exercícios - Conceitos Básicos
 Estruturas de Dados Básicas
Explique a diferença entre alocação sequencial e encadeada, citando vantagens e
desvantagens de cada uma.
 Listas
Implemente uma função que receba uma lista encadeada e retorne true se ela contiver
um ciclo, e false caso contrário.
 Pilhas
Desenvolva um programa que utilize uma pilha para verificar se uma expressão
matemática está com os parênteses balanceados.
 Filas
Implemente uma fila circular usando um array. A implementação deve evitar o
desperdício de espaço quando elementos são removidos.
 Ordenação
Implemente o Bubble Sort e conte o número de trocas necessárias para ordenar o vetor
[45, 23, 11, 89, 77, 98, 4, 28, 65, 43].
8.2 Exercícios de Implementação
 Lista Encadeada
// Implemente as seguintes funções para uma lista encadeada:
struct Node {
 int data;
 struct Node* next;
};
// TODO: Implementar inserção no início
void insertAtBeginning(struct Node** head, int value);
// TODO: Implementar remoção de um valor específico
void removeValue(struct Node** head, int value);
// TODO: Implementar inversão da lista
void reverseList(struct Node** head);
 Pilha com Tamanho Mínimo
Implemente uma pilha que, além das operações básicas push e pop, tenha uma função
que retorne o menor elemento presente na pilha em O(1).
 Fila com Duas Pilhas
Implemente uma fila usando duas pilhas. As operações de enfileirar e desenfileirar
devem ter complexidade amortizada O(1).
8.3 Exercícios de Análise de Complexidade
 Qual é a complexidade de tempo e espaço das seguintes operações em uma lista
duplamente encadeada:
Inserção no início
Remoção do final
Busca por um elemento
Reversão da lista
 Compare a complexidade do Bubble Sort com outros algoritmos de ordenação em
diferentes cenários:
Melhor caso
Pior caso
Caso médio
9. Dicas para Resolução de Provas
 Leia o Enunciado com Atenção
Destaque as palavras-chave
Identifique exatamente o que está sendo pedido
Verifique se há informações implícitas
 Faça Diagramas
Desenhe as estruturas de dados
Represente visualmente os algoritmos
Acompanhe passo a passo as operações
 Análise de Complexidade
Sempre considere o melhor e pior caso
Pense no tamanho da entrada
Identifique loops aninhados
 Implementação
Comece com casos simples
Verifique casos limite (empty, null, etc.)
Teste seu código mentalmente
10. Bibliografia Recomendada
 Cormen, Thomas H. et al. "Introduction to Algorithms"
 Sedgewick, Robert. "Algorithms in C"
 Drozdek, Adam. "Data Structures and Algorithms in C++"
 Tenenbaum, Aaron M. "Data Structures Using C"
Conclusão
Esta apostila fornece uma base sólida para o entendimento e implementação das principais
estruturas de dados. É importante praticar os exercícios propostos e implementar as
estruturas em código para solidificar o aprendizado. Lembre-se que a escolha da estrutura
de dados adequada pode fazer toda a diferença na eficiência de um programa.
Para dúvidasou esclarecimentos adicionais, consulte as referências bibliográficas ou
procure o professor. Bons estudos!