#01
Composição de Permutação1-RespExerc1.c
Dado v[0..98] inicializado com 98,97,…,0, demonstra a composição de permutação: calcula v[i] = v[v[i]] usando vetor auxiliar para preservar os valores originais durante o processo.
VetorIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define TAM 99
int main(void){
int i, v[TAM], aux[TAM];
printf("Primeiro vetor:\n");
for (i = 0; i < TAM; ++i){
v[i] = 98 - i;
printf("v[%d] = %d\n", i, v[i]);
}
// Copia para auxiliar
for (i = 0; i < TAM; ++i){
aux[i] = v[i];
}
printf("\nSegundo vetor:\n");
for (i = 0; i < TAM; ++i){
v[i] = aux[ aux[i] ];
printf("v[%d] = %d\n", i, v[i]);
}
return 0;
}
#02a
Busca Linear Simples em Vetor2-ExercicioBuscaVetor.c
Exercício introdutório de busca linear: preenche 100 posições com números aleatórios e retorna 1 (encontrado) ou 0 (não encontrado).
VetorIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
/*
Escreva uma função que receba x, v e n e devolva 1 se x está em v[0..n-1]
e 0 em caso contrário.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TAM 100
// Função de busca linear
int busca(int n, const int v[], int x){
for (int i = 0; i < n; i++) {
if (v[i] == x) {
return 1; // encontrado
}
}
return 0; // não encontrado
}
int main(void){
int v[TAM];
int num, retorno;
// Inicializa gerador aleatório
srand(time(NULL));
printf("Vetor:\n");
for (int i = 0; i < TAM; i++){
v[i] = rand() % 100; // números mais legíveis
printf("v[%d] = %d\n", i, v[i]);
}
printf("\nInforme o número a ser buscado: ");
scanf("%d", &num);
retorno = busca(TAM, v, num);
if (retorno)
printf("Elemento %d encontrado no vetor!\n", num);
else
printf("Elemento %d NÃO encontrado no vetor!\n", num);
return 0;
}
#02b
Inversão de Permutação (com validação)2-RespExerc2.c
Constrói o vetor inverso tal que inv[v[i]] = i, com validação via ehPermutacao(). Permite consulta O(1) pelo valor desejado.
PermutaçãoIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
/*
Inversão de permutação:
Dado um vetor v[0..n-1] contendo uma permutação de 0..n-1,
construir o vetor inverso inv tal que:
v[i] = j => inv[j] = i
*/
#include <stdio.h>
#include <stdlib.h>
#define N 10
// Função que gera a inversa da permutação
void inverterPermutacao(int n, const int v[], int inv[]) {
for (int i = 0; i < n; i++) {
inv[v[i]] = i;
}
}
// Verifica se é uma permutação válida de 0..n-1
int ehPermutacao(int n, const int v[]) {
int freq[N] = {0};
for (int i = 0; i < n; i++) {
if (v[i] < 0 || v[i] >= n) return 0;
freq[v[i]]++;
}
for (int i = 0; i < n; i++) {
if (freq[i] != 1) return 0;
}
return 1;
}
int main(void) {
int v[N] = {8,3,4,7,6,5,1,2,9,0}; // permutação de 0..9
int inv[N];
printf("Vetor original:\n");
for (int i = 0; i < N; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
// Verificação
if (!ehPermutacao(N, v)) {
printf("\nErro: o vetor não é uma permutação válida!\n");
return 1;
}
// Inversão
inverterPermutacao(N, v, inv);
printf("\nVetor inverso:\n");
for (int i = 0; i < N; i++) {
printf("inv[%d] = %d\n", i, inv[i]);
}
// Consulta direta usando a inversa
int x;
printf("\nInforme o valor (j) para descobrir quem aponta para ele (v[i] = j): ");
scanf("%d", &x);
if (x >= 0 && x < N)
printf("Existe i tal que v[i] = %d -> i = %d\n", x, inv[x]);
else
printf("Valor fora do intervalo!\n");
return 0;
}
#03
Busca Linear Instrumentada (conta comparações)3-buscaVetor.c
Busca da direita para a esquerda com contagem de comparações — recurso para análise de desempenho de algoritmos de busca sequencial.
VetorIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
/*
Busca linear:
Retorna o índice onde x aparece no vetor v[0..n-1]
ou -1 caso não exista.
Versão instrumentada: conta comparações.
*/
#include <stdio.h>
#include <stdlib.h>
// Busca linear da direita para a esquerda
int busca(int n, const int v[], int x, int *comparacoes){
*comparacoes = 0;
for (int i = n - 1; i >= 0; i--) {
(*comparacoes)++;
if (v[i] == x) {
return i;
}
}
return -1;
}
int main(void){
int v[] = {8,3,4,7,6,5,1,2,9,0};
int n = sizeof(v) / sizeof(v[0]);
int valor, posicao, comparacoes;
printf("Vetor:\n");
for (int i = 0; i < n; i++){
printf("v[%d] = %d\n", i, v[i]);
}
printf("\nInforme o valor a ser buscado: ");
if (scanf("%d", &valor) != 1) {
printf("Entrada inválida!\n");
return 1;
}
posicao = busca(n, v, valor, &comparacoes);
if (posicao != -1) {
printf("\n✔ Valor %d encontrado na posição %d\n", valor, posicao);
} else {
printf("\n✖ Valor %d NÃO encontrado\n", valor);
}
printf("Comparações realizadas: %d\n", comparacoes);
return 0;
}
#04
Busca com Inversão de Permutação4-buscaInversaoVetor.c
Combina inversão de permutação e busca linear iterativa para busca simultânea no vetor original e no invertido.
PermutaçãoVetorIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
/*
Inversão de permutação:
Dado um vetor v[0..n-1] contendo uma permutação de 0..n-1,
queremos gerar um vetor inv tal que:
se v[i] = j ⇒ inv[j] = i
*/
#include <stdio.h>
#include <stdlib.h>
#define N 10
// Função que inverte a permutação
void inverterPermutacao(int n, const int v[], int inv[]) {
for (int i = 0; i < n; i++) {
inv[v[i]] = i;
}
}
// Função de busca (opcional, apenas para demonstração)
int busca(int x, int n, const int v[]) {
for (int i = 0; i < n; i++) {
if (v[i] == x) {
return i;
}
}
return -1;
}
int main(void) {
int v[N] = {8,3,4,7,6,5,1,2,9,0}; // permutação de 0..9
int inv[N];
printf("Vetor original:\n");
for (int i = 0; i < N; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
// Inverte a permutação
inverterPermutacao(N, v, inv);
printf("\nVetor inverso (permutação invertida):\n");
for (int i = 0; i < N; i++) {
printf("inv[%d] = %d\n", i, inv[i]);
}
// Demonstração de busca
int valor;
printf("\nInforme um valor para buscar: ");
scanf("%d", &valor);
int posOriginal = busca(valor, N, v);
int posInvertido = busca(valor, N, inv);
if (posOriginal != -1)
printf("Valor %d está na posição %d no vetor original\n", valor, posOriginal);
else
printf("Valor %d não encontrado no vetor original\n", valor);
if (posInvertido != -1)
printf("Valor %d está na posição %d no vetor invertido\n", valor, posInvertido);
else
printf("Valor %d não encontrado no vetor invertido\n", valor);
return 0;
}
#05
Busca Recursiva + Inversão de Permutação5-buscaRecursivaVetor.c
Versão recursiva da busca linear da direita para a esquerda combinada com inversão de permutação. A função reduz o tamanho lógico a cada chamada recursiva.
RecursivoPermutaçãoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define N 10
// Busca recursiva (da direita para a esquerda)
int busca_r(int x, int n, const int v[]) {
if (n == 0)
return -1;
if (x == v[n - 1])
return n - 1;
return busca_r(x, n - 1, v);
}
// Inversão da permutação: inv[v[i]] = i
void inverterPermutacao(int n, const int v[], int inv[]) {
for (int i = 0; i < n; i++) {
inv[v[i]] = i;
}
}
int main(void) {
int v[N] = {8,3,4,7,6,5,1,2,9,0}; // permutação de 0..9
int inv[N];
int valor;
printf("=== Vetor original ===\n");
for (int i = 0; i < N; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
// Inverte a permutação
inverterPermutacao(N, v, inv);
printf("\n=== Vetor invertido ===\n");
for (int i = 0; i < N; i++) {
printf("inv[%d] = %d\n", i, inv[i]);
}
// Entrada do usuário
printf("\nInforme um valor para busca: ");
if (scanf("%d", &valor) != 1) {
printf("Entrada inválida!\n");
return 1;
}
// Busca no vetor original
int pos = busca_r(valor, N, v);
if (pos != -1)
printf("Valor %d encontrado no vetor original na posição %d\n", valor, pos);
else
printf("Valor %d NÃO encontrado no vetor original\n", valor);
// Busca no vetor invertido
pos = busca_r(valor, N, inv);
if (pos != -1)
printf("Valor %d encontrado no vetor invertido na posição %d\n", valor, pos);
else
printf("Valor %d NÃO encontrado no vetor invertido\n", valor);
return 0;
}
#06
Maior Elemento do Vetor (Recursivo)6-maiorRecursivoVetor.c
Estratégia reduz-e-conquista: o maior de n elementos é o maior entre o último e o maior dos n−1 anteriores. Entrada encerrada com -1.
RecursivoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Função recursiva para encontrar o maior elemento
int maior_r(int tam, const int v[]) {
if (tam == 1)
return v[0];
int maior = maior_r(tam - 1, v);
return (v[tam - 1] > maior) ? v[tam - 1] : maior;
}
int main(void) {
int v[MAX];
int tam = 0;
int valor;
printf("Digite os elementos do vetor (-1 para encerrar):\n");
// Leitura segura dos dados
while (tam < MAX) {
printf("v[%d]: ", tam);
if (scanf("%d", &valor) != 1) {
printf("Entrada inválida!\n");
return 1;
}
if (valor == -1)
break;
v[tam++] = valor;
}
// Verifica se o vetor está vazio
if (tam == 0) {
printf("Vetor vazio! Não é possível calcular o maior elemento.\n");
return 0;
}
int maior = maior_r(tam, v);
printf("\nMaior elemento do vetor = %d\n", maior);
return 0;
}
#07
Fatorial Iterativo e Recursivo7-fatorialRecursivo.c
Calcula o fatorial nas duas abordagens: iterativa (laço, O(1) espaço) e recursiva (n! = n × (n−1)!). Usa unsigned long long para valores maiores.
IterativoRecursivoFatorial
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//-------------------------------
// Fatorial iterativo
//-------------------------------
unsigned long long fat_iterativo(int n) {
unsigned long long resultado = 1;
for (int i = 2; i <= n; i++) {
resultado *= i;
}
return resultado;
}
//-------------------------------
// Fatorial recursivo
//-------------------------------
unsigned long long fat_recursivo(int n) {
if (n == 0 || n == 1)
return 1;
return n * fat_recursivo(n - 1);
}
//-------------------------------
// MAIN
//-------------------------------
int main() {
int n;
printf("Informe um número inteiro não negativo: ");
scanf("%d", &n);
if (n < 0) {
printf("Erro: fatorial não é definido para números negativos.\n");
return 1;
}
printf("\nFatorial de %d (iterativo) = %llu\n", n, fat_iterativo(n));
printf("Fatorial de %d (recursivo) = %llu\n", n, fat_recursivo(n));
return 0;
}
#08
Fibonacci Iterativo8-fibonacciIterativa.c
Versão iterativa com dois acumuladores — O(n) em tempo e O(1) em espaço. Exibe a sequência completa separada por vírgulas.
IterativoFibonacci
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Fibonacci:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), para n > 1
*/
// ----------- VERSÃO ITERATIVA -----------
void fib_iter(int n) {
if (n <= 0) {
printf("Sequência vazia\n");
return;
}
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
printf("%d", a);
if (i < n - 1) printf(", ");
int prox = a + b;
a = b;
b = prox;
}
printf("\n");
}
// ----------- MAIN -----------
int main(void) {
int n;
printf("Informe a quantidade de termos da sequência de Fibonacci: ");
if (scanf("%d", &n) != 1 || n < 0) {
printf("Entrada inválida!\n");
return 1;
}
// Versão iterativa (sequência completa)
printf("\nSequência de Fibonacci (iterativa):\n");
fib_iter(n);
return 0;
}
#10
Remoção Recursiva em Vetor10-remocaoRecursivaVetor.c
Remove elemento na posição k e desloca os subsequentes recursivamente. A cadeia propaga o valor removido de volta ao chamador.
RecursivoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define N 10
// Remove elemento na posição k e desloca os demais (recursivo)
// Retorna o valor removido
int remove_r(int k, int n, int v[]) {
int removido = v[k];
if (k < n - 1) {
v[k] = remove_r(k + 1, n, v);
}
return removido;
}
// Função auxiliar para imprimir vetor
void imprimirVetor(int n, int v[]) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[N] = {8,3,4,7,6,5,1,2,9,0};
int tamanho = N;
int pos;
printf("=== Vetor original ===\n");
imprimirVetor(tamanho, v);
printf("\nInforme a posição a remover (0 a %d): ", tamanho - 1);
if (scanf("%d", &pos) != 1 || pos < 0 || pos >= tamanho) {
printf("Posição inválida!\n");
return 1;
}
int removido = remove_r(pos, tamanho, v);
tamanho--; // atualiza tamanho lógico
printf("\nItem removido: %d\n", removido);
printf("\n=== Vetor após remoção ===\n");
imprimirVetor(tamanho, v);
return 0;
}
#11
Remoção Iterativa em Vetor11-remocaoIterativaVetor.c
Remove o elemento de posição k e desloca todos os posteriores à esquerda via laço iterativo, atualizando o tamanho lógico.
IterativoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define N 10
// Remove elemento da posição k
// Atualiza o tamanho lógico do vetor
int remover(int k, int *n, int v[]) {
if (k < 0 || k >= *n) {
printf("Erro: posição inválida!\n");
return -1;
}
int removido = v[k];
// desloca elementos para a esquerda
for (int j = k + 1; j < *n; j++) {
v[j - 1] = v[j];
}
(*n)--; // atualiza tamanho lógico
return removido;
}
// Imprime vetor
void imprimir(int n, int v[]) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[N] = {8,3,4,7,6,5,1,2,9,0};
int n = N;
int pos;
printf("=== Vetor original ===\n");
imprimir(n, v);
printf("\nInforme a posição a remover (0 a %d): ", n - 1);
if (scanf("%d", &pos) != 1) {
printf("Entrada inválida!\n");
return 1;
}
int removido = remover(pos, &n, v);
if (removido != -1) {
printf("\nItem removido: %d\n", removido);
printf("\n=== Vetor após remoção ===\n");
imprimir(n, v);
}
return 0;
}
#12
Inserção Recursiva em Vetor12-insercaoRecursivaVetor.c
Insere elemento em posição k deslocando os posteriores à direita recursivamente. Abre espaço no final até alcançar a posição-alvo.
RecursivoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
// Inserção recursiva com controle de tamanho
int inserir_r(int k, int x, int *n, int v[], int capacidade) {
// validações
if (*n >= capacidade) {
printf("Erro: vetor cheio!\n");
return 0;
}
if (k < 0 || k > *n) {
printf("Erro: posição inválida!\n");
return 0;
}
// caso base
if (k == *n) {
v[*n] = x;
} else {
v[*n] = v[*n - 1]; // abre espaço no final
inserir_r(k, x, n - 1, v, capacidade);
}
return 1;
}
// impressão
void imprimir(int n, int v[]) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[MAX] = {8,3,4,7,6,5,1,2,9,0};
int n = 10;
int valor, pos;
printf("=== Vetor original ===\n");
imprimir(n, v);
printf("\nInforme o valor a inserir: ");
if (scanf("%d", &valor) != 1) {
printf("Entrada inválida!\n");
return 1;
}
printf("Informe a posição (0 a %d): ", n);
if (scanf("%d", &pos) != 1) {
printf("Entrada inválida!\n");
return 1;
}
if (inserir_r(pos, valor, &n, v, MAX)) {
n++; // atualiza tamanho lógico
printf("\n=== Vetor após inserção ===\n");
imprimir(n, v);
}
return 0;
}
#13a
Remoção de Todas as Ocorrências de um Valor (Iterativo)13-buscaRetiraIterativoVetor.c
Compactação in-place O(n): remove todas as ocorrências de um valor com dois índices. Apenas os elementos diferentes do valor removido são mantidos.
IterativoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define VALOR_REMOVER 2
/*
Remove todas as ocorrências de VALOR_REMOVER do vetor v[0..n-1].
Retorna o novo tamanho do vetor.
*/
int removerValor(int n, int v[], int valor) {
int i = 0;
for (int j = 0; j < n; ++j) {
if (v[j] != valor) {
v[i++] = v[j];
}
}
return i; // novo tamanho
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; ++i) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {2,8,0,3,4,7,2,2,6,5,1,0,2,9,2};
int tam = sizeof(v) / sizeof(v[0]);
printf("Vetor original:\n");
imprimirVetor(v, tam);
int novoTam = removerValor(tam, v, VALOR_REMOVER);
printf("\nVetor sem o valor %d:\n", VALOR_REMOVER);
imprimirVetor(v, novoTam);
printf("\nTamanho original: %d\n", tam);
printf("Novo tamanho: %d\n", novoTam);
return 0;
}
#13b
Remoção de Zeros do Vetor13-tiraZerosVetor.c
Compactação in-place: remove todos os zeros, copiando não-zeros para as primeiras posições e retornando o novo tamanho lógico.
IterativoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Remove todos os zeros do vetor v[0..n-1].
Retorna o novo tamanho do vetor.
*/
int removerZeros(int n, int v[]) {
int i = 0;
for (int j = 0; j < n; ++j) {
if (v[j] != 0) {
v[i++] = v[j];
}
}
return i;
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; ++i) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {0,8,0,3,4,7,0,6,5,1,0,2,9,0};
int tam = sizeof(v) / sizeof(v[0]);
printf("Vetor original (com zeros):\n");
imprimirVetor(v, tam);
tam = removerZeros(tam, v);
printf("\nVetor sem zeros:\n");
imprimirVetor(v, tam);
printf("\nNovo tamanho do vetor: %d\n", tam);
return 0;
}
#14
Remoção Recursiva de Todas as Ocorrências14-buscaRetiraRecursivoVetor.c
Remove todas as ocorrências de um valor via recursão: resolve o subproblema de tamanho n−1 e decide se inclui v[n-1] — compactação sem laços explícitos.
RecursivoVetor
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Remove recursivamente todas as ocorrências de 'valor' do vetor v[0..n-1].
Retorna o novo tamanho do vetor.
*/
int removerValorRec(int n, int v[], int valor) {
if (n == 0) return 0;
int m = removerValorRec(n - 1, v, valor);
if (v[n - 1] == valor)
return m;
v[m] = v[n - 1];
return m + 1;
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; ++i) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {2,8,2,3,4,7,2,6,5,1,0,2,9,7,0};
int tam = sizeof(v) / sizeof(v[0]);
int valor = 2;
printf("Vetor original:\n");
imprimirVetor(v, tam);
tam = removerValorRec(tam, v, valor);
printf("\nVetor sem o valor %d:\n", valor);
imprimirVetor(v, tam);
printf("\nNovo tamanho: %d\n", tam);
return 0;
}
#15
Insertion Sort15-InsertionSort.c
Ordenação por inserção: desloca elementos maiores à direita e insere na posição correta. Melhor caso O(n); pior O(n²). Abordagem de deslocamento (sem trocas duplas) é mais eficiente na prática.
IterativoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Ordenação por Insertion Sort
Melhor abordagem: deslocamento em vez de várias trocas
*/
void insertionSort(int n, int v[]) {
for (int i = 1; i < n; i++) {
int chave = v[i];
int j = i - 1;
// desloca elementos maiores para a direita
while (j >= 0 && v[j] > chave) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = chave;
}
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {2,8,0,3,4,7,2,2,6,5,1,0,2,9,2};
int tam = sizeof(v) / sizeof(v[0]);
printf("Vetor Original:\n");
imprimirVetor(v, tam);
insertionSort(tam, v);
printf("\nVetor Ordenado:\n");
imprimirVetor(v, tam);
return 0;
}
#16
Bubble Sort (otimizado)16-BubbleSort.c
Bubble Sort otimizado com flag trocou para encerramento antecipado — melhor caso O(n).
IterativoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Bubble Sort otimizado:
- Reduz o tamanho da varredura a cada iteração
- Usa flag para parar se já estiver ordenado
*/
void bubbleSort(int n, int v[]) {
int trocou;
for (int j = 0; j < n - 1; j++) {
trocou = 0;
for (int i = 0; i < n - 1 - j; i++) {
if (v[i] > v[i + 1]) {
int aux = v[i];
v[i] = v[i + 1];
v[i + 1] = aux;
trocou = 1;
}
}
// Se não houve troca, já está ordenado
if (!trocou) break;
}
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {16,8,0,3,4,7,13,22,6,5,1,24,12,9,77,34,120,56};
int tam = sizeof(v) / sizeof(v[0]);
printf("Vetor Original:\n");
imprimirVetor(v, tam);
bubbleSort(tam, v);
printf("\nVetor Ordenado:\n");
imprimirVetor(v, tam);
return 0;
}
#17
Selection Sort17-SelectionSort.c
Selection Sort: encontra o menor do trecho não ordenado e coloca na posição correta. Máximo n−1 trocas. O(n²) em todos os casos.
IterativoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Selection Sort:
- Seleciona o menor elemento e coloca na posição correta
- Faz no máximo (n-1) trocas
*/
void selectionSort(int n, int v[]) {
for (int i = 0; i < n - 1; i++) {
int menor = i;
for (int j = i + 1; j < n; j++) {
if (v[j] < v[menor]) {
menor = j;
}
}
// Troca apenas se necessário
if (menor != i) {
int aux = v[i];
v[i] = v[menor];
v[menor] = aux;
}
}
}
// Função para imprimir vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; i++) {
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(void) {
int v[] = {16,8,0,3,4,7,13,22,6,5,1,24,12,9,77,34};
int tam = sizeof(v) / sizeof(v[0]);
printf("Vetor Original:\n");
imprimirVetor(v, tam);
selectionSort(tam, v);
printf("\nVetor Ordenado:\n");
imprimirVetor(v, tam);
return 0;
}
#18
Merge Sort (Divisão e Conquista)18-MergeSort.c
Merge Sort: divide recursivamente ao meio e intercala pares ordenados. O(n log n) garantido. Usa malloc para vetores auxiliares.
RecursivoOrdenaçãoDivisão-Conquista
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
/*
Função merge:
Junta dois subvetores ordenados v[l..m] e v[m+1..r]
*/
void merge(int v[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Alocação dinâmica (mais segura que VLA)
int *L = (int *) malloc(n1 * sizeof(int));
int *R = (int *) malloc(n2 * sizeof(int));
if (L == NULL || R == NULL) {
printf("Erro de memória!\n");
exit(1);
}
// Copia dados
for (i = 0; i < n1; i++)
L[i] = v[l + i];
for (j = 0; j < n2; j++)
R[j] = v[m + 1 + j];
i = 0;
j = 0;
k = l;
// Intercala os vetores
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
v[k++] = L[i++];
} else {
v[k++] = R[j++];
}
}
// Copia restantes
while (i < n1)
v[k++] = L[i++];
while (j < n2)
v[k++] = R[j++];
// Libera memória
free(L);
free(R);
}
/*
Merge Sort (divisão e conquista)
*/
void mergeSort(int v[], int l, int r) {
if (l < r) {
// Evita overflow
int m = l + (r - l) / 2;
mergeSort(v, l, m);
mergeSort(v, m + 1, r);
merge(v, l, m, r);
}
}
// Impressão do vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", v[i]);
printf("\n");
}
int main(void) {
int v[] = {70, 11, 34, 23, 4, 5, 87, 2, 50, 30, 10, 89, 45, 20, 40, 60, 110, 1, 3};
int n = sizeof(v) / sizeof(v[0]);
printf("Vetor original:\n");
imprimirVetor(v, n);
mergeSort(v, 0, n - 1);
printf("\nVetor ordenado:\n");
imprimirVetor(v, n);
return 0;
}
#19
Quick Sort (Partição de Hoare)19-Quick-sort.c
Quick Sort com partição de Hoare: dois ponteiros opostos trocam elementos fora de lugar. Pivô central. Média O(n log n); pior O(n²).
RecursivoOrdenaçãoDivisão-Conquista
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
// Função de troca
void trocar(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/*
Partição (Hoare)
*/
int particionar(int v[], int esq, int dir) {
int pivo = v[(esq + dir) / 2];
int i = esq - 1;
int j = dir + 1;
while (1) {
do { i++; } while (v[i] < pivo);
do { j--; } while (v[j] > pivo);
if (i >= j)
return j;
trocar(&v[i], &v[j]);
}
}
/*
Quick Sort
*/
void quickSort(int v[], int esq, int dir) {
if (esq < dir) {
int p = particionar(v, esq, dir);
quickSort(v, esq, p);
quickSort(v, p + 1, dir);
}
}
// Impressão do vetor
void imprimirVetor(int v[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", v[i]);
printf("\n");
}
int main(void) {
int v[] = {25,4,6,7,9,0,1,2,5,8,40,55,20,44,35,38,99,10,65,50};
int n = sizeof(v) / sizeof(v[0]);
printf("Vetor original:\n");
imprimirVetor(v, n);
quickSort(v, 0, n - 1);
printf("\nVetor ordenado:\n");
imprimirVetor(v, n);
return 0;
}
#20
Quick Sort Modularizado (Pivô Aleatório)20-QuickSortModularizado.c
Quick Sort modularizado com pivô aleatório para evitar pior caso. Demonstra boas práticas de modularização em C.
RecursivoOrdenaçãoDivisão-Conquista
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Troca dois elementos do vetor
void troca(int v[], int i, int j){
int aux = v[i];
v[i] = v[j];
v[j] = aux;
}
// Particiona usando o último elemento como pivô
int particiona(int v[], int inicio, int fim){
int pivo = v[fim];
int i = inicio - 1;
for(int j = inicio; j < fim; j++){
if(v[j] <= pivo){
i++;
troca(v, i, j);
}
}
troca(v, i + 1, fim);
return i + 1;
}
// Particiona com pivô aleatório (evita pior caso)
int particionaRandom(int v[], int inicio, int fim){
int indicePivo = inicio + rand() % (fim - inicio + 1);
troca(v, indicePivo, fim);
return particiona(v, inicio, fim);
}
// Algoritmo QuickSort
void quickSort(int v[], int inicio, int fim){
if(inicio < fim){
int pivo = particionaRandom(v, inicio, fim);
quickSort(v, inicio, pivo - 1);
quickSort(v, pivo + 1, fim);
}
}
// Impressão do vetor
void imprimirVetor(const int v[], int tamanho){
for(int i = 0; i < tamanho; i++){
printf("%d ", v[i]);
}
printf("\n");
}
int main(){
int vet[] = {25,4,6,7,9,0,1,2,5,8,40,55,20,44,35,38,99,10,65,50};
int tamanho = sizeof(vet) / sizeof(vet[0]);
// Inicializa a semente do random
srand(time(NULL));
printf("Vetor Original:\n");
imprimirVetor(vet, tamanho);
quickSort(vet, 0, tamanho - 1);
printf("\nVetor Ordenado:\n");
imprimirVetor(vet, tamanho);
return 0;
}
#21
Shell Sort (sequência de Knuth)21-ShellSort.c
Shell Sort com gaps de Knuth (1,4,13,40,…): generalização do Insertion Sort. Complexidade ≈ O(n1.5).
IterativoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
// Função para imprimir vetor
void imprimirVetor(const int v[], int n){
for(int i = 0; i < n; i++){
printf("%d ", v[i]);
}
printf("\n");
}
// Algoritmo Shell Sort (sequência de Knuth)
void shellSort(int v[], int n) {
int gap = 1;
// Define o maior gap da sequência de Knuth: 1, 4, 13, 40, ...
while (gap < n) {
gap = 3 * gap + 1;
}
// Reduz o gap até chegar a 1
while (gap > 1) {
gap /= 3;
// Inserção com distância "gap"
for (int i = gap; i < n; i++) {
int valor = v[i];
int j = i - gap;
while (j >= 0 && valor < v[j]) {
v[j + gap] = v[j];
j -= gap;
}
v[j + gap] = valor;
}
}
}
int main(){
int vet[] = {25,4,6,7,9,0,1,2,5,8,40,55,20,44,35,38,99,10,65,50,100,120,11,13};
int tamanho = sizeof(vet) / sizeof(vet[0]);
printf("Vetor original:\n");
imprimirVetor(vet, tamanho);
shellSort(vet, tamanho);
printf("\nVetor ordenado:\n");
imprimirVetor(vet, tamanho);
return 0;
}
#22a
Heap Sort v1 (vetor fixo)22-HeapSort.c
Heap Sort: constrói heap máximo e extrai o maior repetidamente. O(n log n) garantido sem memória extra.
IterativoRecursivoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
// Função de troca
void troca(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
// Função "peneira" (heapify - ajusta o heap)
void heapify(int v[], int n, int raiz){
int maior = raiz;
int esq = 2 * raiz + 1;
int dir = 2 * raiz + 2;
// Verifica filho esquerdo
if (esq < n && v[esq] > v[maior])
maior = esq;
// Verifica filho direito
if (dir < n && v[dir] > v[maior])
maior = dir;
// Se a raiz não é o maior elemento
if (maior != raiz){
troca(&v[raiz], &v[maior]);
heapify(v, n, maior);
}
}
// HeapSort
void heapSort(int v[], int n){
// Construção do heap (heap máximo)
for (int i = n/2 - 1; i >= 0; i--){
heapify(v, n, i);
}
// Extração dos elementos do heap
for (int i = n - 1; i > 0; i--){
troca(&v[0], &v[i]); // Move o maior para o final
heapify(v, i, 0); // Reorganiza o heap reduzido
}
}
// Impressão do vetor
void imprimir(int v[], int n){
for (int i = 0; i < n; i++){
printf("v[%d] = %d\n", i, v[i]);
}
}
int main(){
int vetor[] = {16,8,0,3,4,7,13,22,123,675,111,576,97,15,6,5,1,24,14,9,77,11,12,87,33,59,89,56,32,90,34};
int tamanho = sizeof(vetor) / sizeof(vetor[0]);
printf("Vetor Original:\n");
imprimir(vetor, tamanho);
heapSort(vetor, tamanho);
printf("\nVetor Ordenado:\n");
imprimir(vetor, tamanho);
return 0;
}
#22b
Heap Sort v2 (entrada interativa)22-HeapSort_-_SegundaVersao.c
Segunda versão do Heap Sort com entrada interativa via scanf — ideal para testes manuais em aula.
IterativoRecursivoOrdenação
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#define MAX 10
// Função para trocar dois elementos
void troca(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
// Função que "desce" o elemento (heapify)
void heapify(int v[], int n, int i){
int maior = i; // raiz
int esq = 2*i + 1; // filho esquerdo
int dir = 2*i + 2; // filho direito
// Se filho esquerdo é maior que a raiz
if(esq < n && v[esq] > v[maior])
maior = esq;
// Se filho direito é maior que o maior até agora
if(dir < n && v[dir] > v[maior])
maior = dir;
// Se o maior não é a raiz
if(maior != i){
troca(&v[i], &v[maior]);
heapify(v, n, maior);
}
}
// Função principal do HeapSort
void heapSort(int v[], int n){
// Construir heap (reorganiza vetor)
for(int i = n/2 - 1; i >= 0; i--){
heapify(v, n, i);
}
// Extrair elementos do heap
for(int i = n - 1; i > 0; i--){
troca(&v[0], &v[i]); // move raiz para o final
heapify(v, i, 0); // reorganiza heap reduzido
}
}
// Impressão do vetor
void imprimir(int v[], int n){
for(int i = 0; i < n; i++){
printf("%d ", v[i]);
}
printf("\n");
}
int main(){
int vetor[MAX];
for(int i = 0; i < MAX; i++){
printf("Digite o %dº elemento: ", i + 1);
scanf("%d", &vetor[i]);
}
printf("\nVetor original:\n");
imprimir(vetor, MAX);
heapSort(vetor, MAX);
printf("\nVetor ordenado:\n");
imprimir(vetor, MAX);
return 0;
}
#23
Lista Simplesmente Encadeada23-ListaEncadeada.c
Lista simplesmente encadeada: cada nó aponta apenas para o próximo. Inserção no início O(1) e no final O(n), busca iterativa e recursiva, remoção por valor com ponteiro anterior, impressão e liberação de memória — tudo via menu interativo.
ListaIterativoRecursivo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
// Definição do nó
typedef struct nodo{
int valor;
struct nodo *prox;
} Celula;
//-------------------------------
// Criação de nó (função auxiliar)
//-------------------------------
Celula *criarNo(int valor){
Celula *novo = (Celula*) malloc(sizeof(Celula));
if (novo == NULL){
printf("Erro de alocação de memória!\n");
exit(EXIT_FAILURE);
}
novo->valor = valor;
novo->prox = NULL;
return novo;
}
//-------------------------------
// Inserir no início
//-------------------------------
Celula *inserirInicio(int valor, Celula *lista){
Celula *novo = criarNo(valor);
novo->prox = lista;
return novo;
}
//-------------------------------
// Inserir no final
//-------------------------------
Celula *inserirFinal(int valor, Celula *lista){
Celula *novo = criarNo(valor);
if (lista == NULL){
return novo;
}
Celula *p = lista;
while (p->prox != NULL){
p = p->prox;
}
p->prox = novo;
return lista;
}
//-------------------------------
// Buscar (iterativo)
//-------------------------------
Celula *buscar(int valor, Celula *lista){
while (lista != NULL){
if (lista->valor == valor)
return lista;
lista = lista->prox;
}
return NULL;
}
//-------------------------------
// Buscar (recursivo)
//-------------------------------
Celula *buscarRecursivo(int valor, Celula *lista){
if (lista == NULL) return NULL;
if (lista->valor == valor) return lista;
return buscarRecursivo(valor, lista->prox);
}
//-------------------------------
// Remover por valor
//-------------------------------
Celula *remover(int valor, Celula *lista){
Celula *atual = lista;
Celula *anterior = NULL;
while (atual != NULL && atual->valor != valor){
anterior = atual;
atual = atual->prox;
}
if (atual == NULL){
printf("Elemento não encontrado!\n");
return lista;
}
if (anterior == NULL){ // remove primeiro
lista = atual->prox;
} else {
anterior->prox = atual->prox;
}
free(atual);
printf("Elemento removido com sucesso!\n");
return lista;
}
//-------------------------------
// Imprimir lista
//-------------------------------
void imprimir(Celula *lista){
printf("Lista: ");
while (lista != NULL){
printf("%d -> ", lista->valor);
lista = lista->prox;
}
printf("NULL\n");
}
//-------------------------------
// Liberar memória
//-------------------------------
void liberarLista(Celula *lista){
Celula *temp;
while (lista != NULL){
temp = lista;
lista = lista->prox;
free(temp);
}
}
//-------------------------------
// Programa principal
//-------------------------------
int main(){
Celula *lista = NULL;
int opcao, valor;
do {
printf("\n===== MENU =====\n");
printf("1 - Inserir no início\n");
printf("2 - Inserir no final\n");
printf("3 - Buscar elemento\n");
printf("4 - Remover elemento\n");
printf("5 - Imprimir lista\n");
printf("0 - Sair\n");
printf("Escolha: ");
if (scanf("%d", &opcao) != 1){
printf("Entrada inválida!\n");
break;
}
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirInicio(valor, lista);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirFinal(valor, lista);
break;
case 3:
printf("Valor: ");
scanf("%d", &valor);
if (buscar(valor, lista))
printf("Elemento encontrado!\n");
else
printf("Elemento não encontrado!\n");
break;
case 4:
printf("Valor: ");
scanf("%d", &valor);
lista = remover(valor, lista);
break;
case 5:
imprimir(lista);
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opção inválida!\n");
}
} while(opcao != 0);
liberarLista(lista);
return 0;
}
#24
Lista Encadeada Circular24-ListaEncadeadaCircular.c
Lista circular: o último nó aponta de volta ao primeiro. Inserção no final, remoção por valor, busca e impressão percorrendo o ciclo com condição p != topo.
ListaIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
// Estrutura do nó
typedef struct reg{
int valor;
struct reg *prox;
} Celula;
//-------------------------------
// Criação de nó
//-------------------------------
Celula *criarNo(int valor){
Celula *novo = (Celula*) malloc(sizeof(Celula));
if (novo == NULL){
printf("Erro de alocação!\n");
exit(EXIT_FAILURE);
}
novo->valor = valor;
novo->prox = NULL;
return novo;
}
//-------------------------------
// Imprimir lista circular
//-------------------------------
void imprimir(Celula *topo){
if (topo == NULL){
printf("Lista vazia\n");
return;
}
Celula *p = topo;
printf("Lista: ");
do {
printf("%d -> ", p->valor);
p = p->prox;
} while (p != topo);
printf("(retorna ao início)\n");
}
//-------------------------------
// Buscar elemento
//-------------------------------
Celula *buscar(int valor, Celula *topo){
if (topo == NULL) return NULL;
Celula *p = topo;
do {
if (p->valor == valor)
return p;
p = p->prox;
} while (p != topo);
return NULL;
}
//-------------------------------
// Inserir no final (mantém topo)
//-------------------------------
Celula *inserir(int valor, Celula *topo){
Celula *novo = criarNo(valor);
// Lista vazia
if (topo == NULL){
novo->prox = novo;
return novo;
}
Celula *ultimo = topo;
while (ultimo->prox != topo){
ultimo = ultimo->prox;
}
ultimo->prox = novo;
novo->prox = topo;
return topo; // topo permanece o mesmo
}
//-------------------------------
// Remover elemento
//-------------------------------
Celula *remover(int valor, Celula *topo){
if (topo == NULL){
printf("Lista vazia!\n");
return NULL;
}
Celula *atual = topo;
Celula *anterior = NULL;
do {
if (atual->valor == valor)
break;
anterior = atual;
atual = atual->prox;
} while (atual != topo);
// Não encontrou
if (atual->valor != valor){
printf("Elemento não encontrado!\n");
return topo;
}
// Caso: único elemento
if (atual == topo && atual->prox == topo){
free(atual);
return NULL;
}
// Caso: remover topo
if (atual == topo){
Celula *ultimo = topo;
while (ultimo->prox != topo){
ultimo = ultimo->prox;
}
topo = topo->prox;
ultimo->prox = topo;
free(atual);
return topo;
}
// Caso geral
anterior->prox = atual->prox;
free(atual);
printf("Elemento removido com sucesso!\n");
return topo;
}
//-------------------------------
// Liberar memória
//-------------------------------
void liberarLista(Celula *topo){
if (topo == NULL) return;
Celula *p = topo->prox;
while (p != topo){
Celula *temp = p;
p = p->prox;
free(temp);
}
free(topo);
}
//-------------------------------
// MAIN
//-------------------------------
int main(){
Celula *topo = NULL;
int valor, opcao;
do {
printf("\n===== LISTA CIRCULAR =====\n");
printf("1 - Inserir elemento\n");
printf("2 - Remover elemento\n");
printf("3 - Buscar elemento\n");
printf("4 - Imprimir lista\n");
printf("0 - Sair\n");
printf("Escolha: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
topo = inserir(valor, topo);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
topo = remover(valor, topo);
break;
case 3:
printf("Valor: ");
scanf("%d", &valor);
if (buscar(valor, topo))
printf("Elemento encontrado!\n");
else
printf("Elemento não encontrado!\n");
break;
case 4:
imprimir(topo);
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opção inválida!\n");
}
} while(opcao != 0);
liberarLista(topo);
return 0;
}
#25
Lista Duplamente Encadeada25-ListaDuplamenteEncadeada.c
Lista com prox e ant em cada nó. Inserção no início, final e após referência, além de remoção e busca.
ListaIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//-------------------------------
// Definição da estrutura
//-------------------------------
typedef struct reg{
int conteudo;
struct reg *prox;
struct reg *ant;
} celula;
//-------------------------------
// Alocação segura
//-------------------------------
celula* criarNo(int valor){
celula *nova = (celula*) malloc(sizeof(celula));
if (nova == NULL){
printf("Erro de memória!\n");
exit(1);
}
nova->conteudo = valor;
nova->prox = NULL;
nova->ant = NULL;
return nova;
}
//-------------------------------
// Imprimir lista
//-------------------------------
void imprimir(celula *lista){
printf("Lista: ");
for (celula *p = lista; p != NULL; p = p->prox){
printf("%d <-> ", p->conteudo);
}
printf("NULL\n");
}
//-------------------------------
// Buscar elemento
//-------------------------------
celula *buscar(int x, celula *lista){
for (; lista != NULL; lista = lista->prox){
if (lista->conteudo == x)
return lista;
}
return NULL;
}
//-------------------------------
// Inserir no início
//-------------------------------
celula *inserirInicio(int x, celula *topo){
celula *nova = criarNo(x);
nova->prox = topo;
if (topo != NULL)
topo->ant = nova;
return nova;
}
//-------------------------------
// Inserir no final
//-------------------------------
celula *inserirFinal(int x, celula *topo){
celula *nova = criarNo(x);
if (topo == NULL)
return nova;
celula *p = topo;
while (p->prox != NULL)
p = p->prox;
p->prox = nova;
nova->ant = p;
return topo;
}
//-------------------------------
// Remover nó específico
//-------------------------------
celula *remover(celula *topo, celula *p){
if (p == NULL) return topo;
if (p->ant == NULL){ // primeiro elemento
topo = p->prox;
if (topo != NULL)
topo->ant = NULL;
} else {
p->ant->prox = p->prox;
if (p->prox != NULL)
p->prox->ant = p->ant;
}
free(p);
return topo;
}
//-------------------------------
// Buscar e remover
//-------------------------------
celula *buscarRemover(int x, celula *lista){
celula *p = buscar(x, lista);
if (p == NULL){
printf("Elemento %d não encontrado!\n", x);
return lista;
}
return remover(lista, p);
}
//-------------------------------
// Inserir após valor Y
//-------------------------------
celula *inserirApos(int x, int y, celula *lista){
celula *p = buscar(y, lista);
if (p == NULL){
printf("Elemento %d não encontrado!\n", y);
return lista;
}
celula *nova = criarNo(x);
nova->prox = p->prox;
nova->ant = p;
if (p->prox != NULL)
p->prox->ant = nova;
p->prox = nova;
return lista;
}
//-------------------------------
// Liberar memória
//-------------------------------
void liberar(celula *lista){
while (lista != NULL){
celula *tmp = lista;
lista = lista->prox;
free(tmp);
}
}
//-------------------------------
// MAIN (menu interativo)
//-------------------------------
int main(){
celula *lista = NULL;
int opcao, valor, ref;
do {
printf("\n===== MENU =====\n");
printf("1 - Inserir no início\n");
printf("2 - Inserir no final\n");
printf("3 - Inserir após um valor\n");
printf("4 - Remover valor\n");
printf("5 - Buscar valor\n");
printf("6 - Imprimir lista\n");
printf("0 - Sair\n");
printf("Escolha: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirInicio(valor, lista);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirFinal(valor, lista);
break;
case 3:
printf("Novo valor: ");
scanf("%d", &valor);
printf("Inserir após qual valor? ");
scanf("%d", &ref);
lista = inserirApos(valor, ref, lista);
break;
case 4:
printf("Valor a remover: ");
scanf("%d", &valor);
lista = buscarRemover(valor, lista);
break;
case 5:
printf("Valor a buscar: ");
scanf("%d", &valor);
if (buscar(valor, lista))
printf("Elemento encontrado!\n");
else
printf("Elemento não encontrado!\n");
break;
case 6:
imprimir(lista);
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opção inválida!\n");
}
} while(opcao != 0);
liberar(lista);
return 0;
}
#25b
Troca de Células entre Duas Listas Duplas (Exercício 4)RespExerc4-TrocaCelulas.c
Resolução do Exercício 4: lê duas listas duplamente encadeadas, exibe-as e troca uma célula de cada lista por manipulação de ponteiros — sem copiar conteúdo. trocarElementos() religa ant/prox dos nós vizinhos e atualiza o topo da lista quando a célula trocada é a primeira.
ListaIterativo
/*---------------------------------------------------------------------
Exercício 4. Faça um algoritmo que leia duas listas duplamente encadeadas
informadas pelo usuário, depois mostre-as na tela e deixe o usuário escolher
um elemento de cada lista e troque-os. Não pode trocar apenas o conteúdo da
célula; deve-se realizar a troca por meio da manipulação de ponteiros, trocando
as células de posição.
//---------------------------------------------------------------------*/
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//-------------------------------
// Definição da estrutura
//-------------------------------
typedef struct reg{
int conteudo;
struct reg *prox;
struct reg *ant;
} celula;
//-------------------------------
// Alocação segura
//-------------------------------
celula* criarNo(int valor){
celula *nova = (celula*) malloc(sizeof(celula));
if (nova == NULL){
printf("Erro de memória!\n");
exit(1);
}
nova->conteudo = valor;
nova->prox = NULL;
nova->ant = NULL;
return nova;
}
//-------------------------------
// Imprimir lista
//-------------------------------
void imprimir(celula *lista){
printf("Lista: ");
for (celula *p = lista; p != NULL; p = p->prox){
printf("%d <-> ", p->conteudo);
}
printf("NULL\n");
}
//-------------------------------
// Buscar elemento
//-------------------------------
celula *buscar(int x, celula *lista){
for (; lista != NULL; lista = lista->prox){
if (lista->conteudo == x)
return lista;
}
return NULL;
}
//-------------------------------
// Inserir no início
//-------------------------------
celula *inserirInicio(int x, celula *topo){
celula *nova = criarNo(x);
nova->prox = topo;
if (topo != NULL)
topo->ant = nova;
return nova;
}
//-------------------------------
// Inserir no final
//-------------------------------
celula *inserirFinal(int x, celula *topo){
celula *nova = criarNo(x);
if (topo == NULL)
return nova;
celula *p = topo;
while (p->prox != NULL)
p = p->prox;
p->prox = nova;
nova->ant = p;
return topo;
}
//-------------------------------
// Remover nó específico
//-------------------------------
celula *remover(celula *topo, celula *p){
if (p == NULL) return topo;
if (p->ant == NULL){ // primeiro elemento
topo = p->prox;
if (topo != NULL)
topo->ant = NULL;
} else {
p->ant->prox = p->prox;
if (p->prox != NULL)
p->prox->ant = p->ant;
}
free(p);
return topo;
}
//-------------------------------
// Buscar e remover
//-------------------------------
celula *buscarRemover(int x, celula *lista){
celula *p = buscar(x, lista);
if (p == NULL){
printf("Elemento %d não encontrado!\n", x);
return lista;
}
return remover(lista, p);
}
//-------------------------------
// Inserir após valor Y
//-------------------------------
celula *inserirApos(int x, int y, celula *lista){
celula *p = buscar(y, lista);
if (p == NULL){
printf("Elemento %d não encontrado!\n", y);
return lista;
}
celula *nova = criarNo(x);
nova->prox = p->prox;
nova->ant = p;
if (p->prox != NULL)
p->prox->ant = nova;
p->prox = nova;
return lista;
}
//-------------------------------
// Liberar memória
//-------------------------------
void liberar(celula *lista){
while (lista != NULL){
celula *tmp = lista;
lista = lista->prox;
free(tmp);
}
}
//-------------------------------
// Trocar elementos de duas listas
//-------------------------------
void trocarElementos(celula **lista1, celula **lista2, celula *x, celula *y){
celula *xAnt = x->ant;
celula *xProx = x->prox;
celula *yAnt = y->ant;
celula *yProx = y->prox;
//trocando os elementos
y->ant = xAnt;
y->prox = xProx;
if (xAnt != NULL)
xAnt->prox = y;
else
*lista1 = y; // 'x' era o primeiro da lista 1
if (xProx != NULL)
xProx->ant = y;
x->ant = yAnt;
x->prox = yProx;
if (yAnt != NULL)
yAnt->prox = x;
else
*lista2 = x; // 'y' era o primeiro da lista 2
if (yProx != NULL)
yProx->ant = x;
}
//-------------------------------
// MAIN (menu interativo)
//-------------------------------
int main(){
celula *lista = NULL,*lista1 = NULL,*lista2 = NULL;
celula *x, *y;
int opcao, valor, ref;
do {
printf("\n===== MENU =====\n");
printf("1 - Inserir no início\n");
printf("2 - Inserir no final\n");
printf("3 - Inserir após um valor\n");
printf("4 - Remover valor\n");
printf("5 - Buscar valor\n");
printf("6 - Imprimir lista\n");
printf("7 - Trocar elementos de duas listas\n");
printf("8 - Sair\n");
printf("Escolha: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirInicio(valor, lista);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirFinal(valor, lista);
break;
case 3:
printf("Novo valor: ");
scanf("%d", &valor);
printf("Inserir após qual valor? ");
scanf("%d", &ref);
lista = inserirApos(valor, ref, lista);
break;
case 4:
printf("Valor a remover: ");
scanf("%d", &valor);
lista = buscarRemover(valor, lista);
break;
case 5:
printf("Valor a buscar: ");
scanf("%d", &valor);
if (buscar(valor, lista))
printf("Elemento encontrado!\n");
else
printf("Elemento não encontrado!\n");
break;
case 6:
imprimir(lista);
break;
case 7:
do{
printf("Informe os elementos da lista 1, digite -1 para encerrar:\n");
printf("Valor: ");
scanf("%d", &valor);
if(valor>=0)
lista1 = inserirInicio(valor, lista1);
}while(valor>=0);
do{
printf("Informe os elementos da lista 2, digite -1 para encerrar:\n");
printf("Valor: ");
scanf("%d", &valor);
if(valor>=0)
lista2 = inserirInicio(valor, lista2);
}while(valor>=0);
printf("Listas 1 e 2:\n");
imprimir(lista1);
imprimir(lista2);
printf("Informe os elementos para troca:\n");
do{
printf("Informe o elemento da lista 1 a ser trocado: ");
scanf("%d", &valor);
x=buscar(valor,lista1);
if(x==NULL) printf("Elemento não encontrado! Informe novamente:\n");
}while(x==NULL);
do{
printf("Informe o elemento da lista 2 a ser trocado: ");
scanf("%d", &valor);
y=buscar(valor,lista2);
if(y==NULL) printf("Elemento não encontrado! Informe novamente:\n");
}while(y==NULL);
trocarElementos(&lista1,&lista2,x,y);
printf("Listas 1 e 2:\n");
imprimir(lista1);
imprimir(lista2);
break;
case 8:
printf("Encerrando...\n");
break;
default:
printf("Opcao inválida!\n");
}
} while(opcao != 8);
liberar(lista);
liberar(lista1);
liberar(lista2);
return 0;
}
#26
Lista Duplamente Encadeada Circular26-ListaDuplamenteEncadeadaCircular.c
Lista dupla + circular: navegação bidirecional e acesso O(1) ao último via topo->ant.
ListaIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//--------------------------------
// Estrutura do nó
//--------------------------------
typedef struct registro{
int conteudo;
struct registro *ant;
struct registro *prox;
} celula;
//--------------------------------
// Criação de nó (alocação segura)
//--------------------------------
celula* criarNo(int valor){
celula *novo = (celula*) malloc(sizeof(celula));
if (novo == NULL){
printf("Erro de memória!\n");
exit(1);
}
novo->conteudo = valor;
novo->ant = novo;
novo->prox = novo;
return novo;
}
//--------------------------------
// Inserir no início
//--------------------------------
celula *inserirInicio(int x, celula *topo){
celula *novo = criarNo(x);
if (topo == NULL)
return novo;
celula *ultimo = topo->ant;
novo->prox = topo;
novo->ant = ultimo;
topo->ant = novo;
ultimo->prox = novo;
return novo; // novo topo
}
//--------------------------------
// Buscar elemento
//--------------------------------
celula *buscar(int x, celula *topo){
if (topo == NULL) return NULL;
celula *p = topo;
do{
if (p->conteudo == x)
return p;
p = p->prox;
} while (p != topo);
return NULL;
}
//--------------------------------
// Remover nó
//--------------------------------
celula *remover(celula *topo, celula *no){
if (topo == NULL || no == NULL) return topo;
// Caso: único elemento
if (no->prox == no){
free(no);
return NULL;
}
// Ajusta encadeamento
no->ant->prox = no->prox;
no->prox->ant = no->ant;
// Atualiza topo se necessário
if (no == topo)
topo = no->prox;
free(no);
return topo;
}
//--------------------------------
// Imprimir lista
//--------------------------------
void imprimir(celula *topo){
if (topo == NULL){
printf("Lista vazia\n");
return;
}
printf("Lista: ");
celula *p = topo;
do{
printf("%d <-> ", p->conteudo);
p = p->prox;
} while (p != topo);
printf("(circular)\n");
}
//--------------------------------
// Liberar memória
//--------------------------------
void liberar(celula *topo){
if (topo == NULL) return;
celula *p = topo->prox;
while (p != topo){
celula *tmp = p;
p = p->prox;
free(tmp);
}
free(topo);
}
//--------------------------------
// Programa principal
//--------------------------------
int main(){
celula *lista = NULL, *aux = NULL;
int opcao, valor;
do{
printf("\n===== MENU =====\n");
printf("1 - Inserir no início\n");
printf("2 - Buscar\n");
printf("3 - Mostrar\n");
printf("4 - Remover\n");
printf("5 - Sair\n");
printf("Opcao: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
lista = inserirInicio(valor, lista);
imprimir(lista);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
aux = buscar(valor, lista);
printf(aux ? "Encontrado!\n" : "Nao encontrado.\n");
break;
case 3:
imprimir(lista);
break;
case 4:
printf("Valor: ");
scanf("%d", &valor);
aux = buscar(valor, lista);
if (aux == NULL){
printf("Elemento nao encontrado.\n");
} else {
lista = remover(lista, aux);
printf("Elemento removido.\n");
}
imprimir(lista);
break;
case 5:
printf("Encerrando...\n");
break;
default:
printf("Opcao invalida!\n");
}
} while(opcao != 5);
liberar(lista);
return 0;
}
#27
Fila (FIFO) com Lista Encadeada27-Fila.c
Fila FIFO com dois ponteiros. enfileirar() e desenfileirar() em O(1).
FilaIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//--------------------------------
// Estrutura do nó
//--------------------------------
typedef struct reg{
int conteudo;
struct reg *prox;
} celula;
//--------------------------------
// Estrutura da fila
//--------------------------------
typedef struct {
celula *inicio;
celula *fim;
} Fila;
//--------------------------------
// Criar nó
//--------------------------------
celula* criarNo(int valor){
celula *novo = (celula*) malloc(sizeof(celula));
if (novo == NULL){
printf("Erro de memória!\n");
exit(1);
}
novo->conteudo = valor;
novo->prox = NULL;
return novo;
}
//--------------------------------
// Inicializar fila
//--------------------------------
void inicializar(Fila *f){
f->inicio = NULL;
f->fim = NULL;
}
//--------------------------------
// Enfileirar (O(1))
//--------------------------------
void enfileirar(Fila *f, int x){
celula *novo = criarNo(x);
if (f->fim == NULL){
f->inicio = f->fim = novo;
} else {
f->fim->prox = novo;
f->fim = novo;
}
}
//--------------------------------
// Desenfileirar (O(1))
//--------------------------------
int desenfileirar(Fila *f){
if (f->inicio == NULL){
printf("Fila vazia!\n");
return -1;
}
celula *tmp = f->inicio;
int valor = tmp->conteudo;
f->inicio = tmp->prox;
if (f->inicio == NULL)
f->fim = NULL;
free(tmp);
return valor;
}
//--------------------------------
// Imprimir fila
//--------------------------------
void imprimir(Fila *f){
printf("Fila: ");
for (celula *p = f->inicio; p != NULL; p = p->prox){
printf("%d <- ", p->conteudo);
}
printf("NULL\n");
}
//--------------------------------
// Buscar
//--------------------------------
celula *buscar(Fila *f, int x){
for (celula *p = f->inicio; p != NULL; p = p->prox){
if (p->conteudo == x)
return p;
}
return NULL;
}
//--------------------------------
// Liberar memória
//--------------------------------
void liberar(Fila *f){
while (f->inicio != NULL){
desenfileirar(f);
}
}
//--------------------------------
// MAIN
//--------------------------------
int main(){
Fila fila;
inicializar(&fila);
int opcao, valor;
do{
printf("\n===== FILA =====\n");
printf("1 - Enfileirar\n");
printf("2 - Desenfileirar\n");
printf("3 - Buscar\n");
printf("4 - Imprimir\n");
printf("0 - Sair\n");
printf("Opcao: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
enfileirar(&fila, valor);
break;
case 2:
valor = desenfileirar(&fila);
if (valor != -1)
printf("Removido: %d\n", valor);
break;
case 3:
printf("Valor: ");
scanf("%d", &valor);
if (buscar(&fila, valor))
printf("Encontrado!\n");
else
printf("Nao encontrado.\n");
break;
case 4:
imprimir(&fila);
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opcao invalida!\n");
}
} while(opcao != 0);
liberar(&fila);
return 0;
}
#28
Pilha (LIFO) com Lista Encadeada28-Pilha.c
Pilha LIFO: empilhar e desempilhar em O(1). Busca linear, impressão do topo à base e liberação segura.
PilhaIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// na disciplina de Estruturas de Dados no IFBA Campus Feira de Santana
//
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//--------------------------------
// Estrutura do nó
//--------------------------------
typedef struct reg{
int conteudo;
struct reg *prox;
} celula;
//--------------------------------
// Criar nó (alocação segura)
//--------------------------------
celula* criarNo(int valor){
celula *novo = (celula*) malloc(sizeof(celula));
if (novo == NULL){
printf("Erro de memória!\n");
exit(1);
}
novo->conteudo = valor;
novo->prox = NULL;
return novo;
}
//--------------------------------
// Empilhar (push)
//--------------------------------
celula *empilhar(celula *topo, int x){
celula *novo = criarNo(x);
novo->prox = topo;
return novo;
}
//--------------------------------
// Desempilhar (pop)
//--------------------------------
int desempilhar(celula **topo){
if (*topo == NULL){
printf("Pilha vazia!\n");
return -1;
}
celula *tmp = *topo;
int valor = tmp->conteudo;
*topo = tmp->prox;
free(tmp);
return valor;
}
//--------------------------------
// Buscar
//--------------------------------
celula *buscar(celula *topo, int x){
for (; topo != NULL; topo = topo->prox){
if (topo->conteudo == x)
return topo;
}
return NULL;
}
//--------------------------------
// Imprimir pilha
//--------------------------------
void imprimir(celula *topo){
printf("\nPilha (topo -> base):\n");
for (celula *p = topo; p != NULL; p = p->prox){
printf("%d\n", p->conteudo);
}
}
//--------------------------------
// Liberar memória
//--------------------------------
void liberar(celula *topo){
while (topo != NULL){
celula *tmp = topo;
topo = topo->prox;
free(tmp);
}
}
//--------------------------------
// MAIN (menu)
//--------------------------------
int main(){
celula *pilha = NULL;
int opcao, valor;
do{
printf("\n===== PILHA =====\n");
printf("1 - Empilhar\n");
printf("2 - Desempilhar\n");
printf("3 - Buscar\n");
printf("4 - Mostrar\n");
printf("0 - Sair\n");
printf("Opcao: ");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("Valor: ");
scanf("%d", &valor);
pilha = empilhar(pilha, valor);
break;
case 2:
valor = desempilhar(&pilha);
if (valor != -1)
printf("Removido: %d\n", valor);
break;
case 3:
printf("Valor: ");
scanf("%d", &valor);
if (buscar(pilha, valor))
printf("Encontrado!\n");
else
printf("Nao encontrado.\n");
break;
case 4:
imprimir(pilha);
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opcao invalida!\n");
}
} while(opcao != 0);
liberar(pilha);
return 0;
}
#29
Árvore Binária de Busca (ABB / BST)29-ArvoreBinariaBuscaOrdenada.c
ABB: menores à esquerda, maiores à direita. Inserção recursiva, busca iterativa, remoção com sucessor in-order e percursos pré/em/pós-ordem.
ÁrvoreRecursivo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// Disciplina: Estruturas de Dados - IFBA Campus Feira de Santana
//
// Árvore Binária de Busca (ABB / BST)
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//-------------------------------
// Estrutura do nó
//-------------------------------
typedef struct No {
int valor;
struct No *esq;
struct No *dir;
} No;
//-------------------------------
// Criação de nó
//-------------------------------
No* criarNo(int valor) {
No* novo = (No*) malloc(sizeof(No));
if (novo == NULL) {
printf("Erro de alocação de memória!\n");
exit(EXIT_FAILURE);
}
novo->valor = valor;
novo->esq = NULL;
novo->dir = NULL;
return novo;
}
//-------------------------------
// Inserção (recursiva)
//-------------------------------
No* inserir(No* raiz, int valor) {
if (raiz == NULL)
return criarNo(valor);
if (valor < raiz->valor)
raiz->esq = inserir(raiz->esq, valor);
else if (valor > raiz->valor)
raiz->dir = inserir(raiz->dir, valor);
else
printf("Valor %d já existe na árvore.\n", valor);
return raiz;
}
//-------------------------------
// Buscar (iterativa)
//-------------------------------
No* buscar(No* raiz, int valor) {
while (raiz != NULL) {
if (valor == raiz->valor)
return raiz;
else if (valor < raiz->valor)
raiz = raiz->esq;
else
raiz = raiz->dir;
}
return NULL;
}
//-------------------------------
// Menor elemento da subárvore
//-------------------------------
No* minimo(No* raiz) {
while (raiz && raiz->esq != NULL)
raiz = raiz->esq;
return raiz;
}
//-------------------------------
// Remoção
//-------------------------------
No* remover(No* raiz, int valor) {
if (raiz == NULL) {
printf("Valor %d não encontrado!\n", valor);
return NULL;
}
if (valor < raiz->valor) {
raiz->esq = remover(raiz->esq, valor);
}
else if (valor > raiz->valor) {
raiz->dir = remover(raiz->dir, valor);
}
else {
// Caso 1: folha
if (raiz->esq == NULL && raiz->dir == NULL) {
free(raiz);
return NULL;
}
// Caso 2: um filho
else if (raiz->esq == NULL) {
No* temp = raiz->dir;
free(raiz);
return temp;
}
else if (raiz->dir == NULL) {
No* temp = raiz->esq;
free(raiz);
return temp;
}
// Caso 3: dois filhos
else {
No* temp = minimo(raiz->dir);
raiz->valor = temp->valor;
raiz->dir = remover(raiz->dir, temp->valor);
}
}
return raiz;
}
//-------------------------------
// Percursos
//-------------------------------
void preOrdem(No* raiz) {
if (raiz) {
printf("%d ", raiz->valor);
preOrdem(raiz->esq);
preOrdem(raiz->dir);
}
}
void emOrdem(No* raiz) {
if (raiz) {
emOrdem(raiz->esq);
printf("%d ", raiz->valor);
emOrdem(raiz->dir);
}
}
void posOrdem(No* raiz) {
if (raiz) {
posOrdem(raiz->esq);
posOrdem(raiz->dir);
printf("%d ", raiz->valor);
}
}
//-------------------------------
// Impressão lateral da árvore
//-------------------------------
void imprimirArvore(No* raiz, int nivel) {
if (raiz) {
imprimirArvore(raiz->dir, nivel + 1);
for (int i = 0; i < nivel; i++)
printf(" ");
printf("%d\n", raiz->valor);
imprimirArvore(raiz->esq, nivel + 1);
}
}
//-------------------------------
// Liberação de memória
//-------------------------------
void liberarArvore(No* raiz) {
if (raiz) {
liberarArvore(raiz->esq);
liberarArvore(raiz->dir);
free(raiz);
}
}
//-------------------------------
// Menu
//-------------------------------
void menu() {
printf("\n===== Árvore Binária de Busca =====\n");
printf("1 - Inserir valor\n");
printf("2 - Remover valor\n");
printf("3 - Buscar valor\n");
printf("4 - Mostrar árvore\n");
printf("5 - Pré-ordem\n");
printf("6 - Em-ordem\n");
printf("7 - Pós-ordem\n");
printf("0 - Sair\n");
printf("Opção: ");
}
//-------------------------------
// MAIN
//-------------------------------
int main() {
No* raiz = NULL;
int opcao, valor;
do {
menu();
scanf("%d", &opcao);
switch(opcao) {
case 1:
printf("Valor: ");
scanf("%d", &valor);
raiz = inserir(raiz, valor);
break;
case 2:
printf("Valor: ");
scanf("%d", &valor);
raiz = remover(raiz, valor);
break;
case 3:
printf("Valor: ");
scanf("%d", &valor);
if (buscar(raiz, valor))
printf("Valor encontrado!\n");
else
printf("Valor NÃO encontrado!\n");
break;
case 4:
printf("\nÁrvore:\n");
imprimirArvore(raiz, 0);
break;
case 5:
printf("Pré-ordem: ");
preOrdem(raiz);
printf("\n");
break;
case 6:
printf("Em-ordem: ");
emOrdem(raiz);
printf("\n");
break;
case 7:
printf("Pós-ordem: ");
posOrdem(raiz);
printf("\n");
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opção inválida!\n");
}
} while (opcao != 0);
liberarArvore(raiz);
return 0;
}
#30
Árvore AVL (Autobalanceada)30-ArvoreAVL.c
AVL: mantém fator de balanceamento entre −1 e +1 com quatro rotações (LL,LR,RR,RL). O(log n) garantido em todos os casos.
AVLÁrvoreRecursivo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// Disciplina: Estruturas de Dados - IFBA Campus Feira de Santana
//
// Árvore AVL (Balanceada)
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//-------------------------------
// Estrutura do nó
//-------------------------------
typedef struct no {
int id;
int altura;
struct no *esq;
struct no *dir;
} No;
//-------------------------------
// Funções utilitárias
//-------------------------------
int max(int a, int b) {
return (a > b) ? a : b;
}
int altura(No *n) {
return (n == NULL) ? -1 : n->altura;
}
No *novoNo(int id) {
No *n = (No*) malloc(sizeof(No));
if (n == NULL) {
printf("Erro de memória!\n");
exit(EXIT_FAILURE);
}
n->id = id;
n->esq = n->dir = NULL;
n->altura = 0;
return n;
}
//-------------------------------
// Fator de balanceamento
//-------------------------------
int fb(No *n) {
return (n == NULL) ? 0 : altura(n->esq) - altura(n->dir);
}
//-------------------------------
// Rotações
//-------------------------------
No *rotDir(No *y) {
No *x = y->esq;
No *t2 = x->dir;
x->dir = y;
y->esq = t2;
y->altura = 1 + max(altura(y->esq), altura(y->dir));
x->altura = 1 + max(altura(x->esq), altura(x->dir));
return x;
}
No *rotEsq(No *x) {
No *y = x->dir;
No *t2 = y->esq;
y->esq = x;
x->dir = t2;
x->altura = 1 + max(altura(x->esq), altura(x->dir));
y->altura = 1 + max(altura(y->esq), altura(y->dir));
return y;
}
//-------------------------------
// Balanceamento
//-------------------------------
No *balancear(No *n) {
int fator = fb(n);
// LL
if (fator > 1 && fb(n->esq) >= 0)
return rotDir(n);
// LR
if (fator > 1 && fb(n->esq) < 0) {
n->esq = rotEsq(n->esq);
return rotDir(n);
}
// RR
if (fator < -1 && fb(n->dir) <= 0)
return rotEsq(n);
// RL
if (fator < -1 && fb(n->dir) > 0) {
n->dir = rotDir(n->dir);
return rotEsq(n);
}
return n;
}
//-------------------------------
// Inserção
//-------------------------------
No *inserir(No *raiz, int id) {
if (raiz == NULL)
return novoNo(id);
if (id < raiz->id)
raiz->esq = inserir(raiz->esq, id);
else if (id > raiz->id)
raiz->dir = inserir(raiz->dir, id);
else {
printf("Valor %d já existe!\n", id);
return raiz;
}
raiz->altura = 1 + max(altura(raiz->esq), altura(raiz->dir));
return balancear(raiz);
}
//-------------------------------
// Menor elemento
//-------------------------------
No *minimo(No *n) {
while (n->esq != NULL)
n = n->esq;
return n;
}
//-------------------------------
// Remoção
//-------------------------------
No *remover(No *raiz, int id) {
if (raiz == NULL)
return NULL;
if (id < raiz->id)
raiz->esq = remover(raiz->esq, id);
else if (id > raiz->id)
raiz->dir = remover(raiz->dir, id);
else {
// 0 ou 1 filho
if (raiz->esq == NULL || raiz->dir == NULL) {
No *temp = raiz->esq ? raiz->esq : raiz->dir;
free(raiz);
return temp;
}
// 2 filhos
No *temp = minimo(raiz->dir);
raiz->id = temp->id;
raiz->dir = remover(raiz->dir, temp->id);
}
raiz->altura = 1 + max(altura(raiz->esq), altura(raiz->dir));
return balancear(raiz);
}
//-------------------------------
// Busca (SEM print)
//-------------------------------
No *buscar(No *raiz, int id) {
if (raiz == NULL || raiz->id == id)
return raiz;
if (id < raiz->id)
return buscar(raiz->esq, id);
return buscar(raiz->dir, id);
}
//-------------------------------
// Impressões
//-------------------------------
void emOrdem(No *raiz) {
if (raiz) {
emOrdem(raiz->esq);
printf("%d ", raiz->id);
emOrdem(raiz->dir);
}
}
void desenhar(No *raiz, int nivel) {
if (raiz) {
desenhar(raiz->dir, nivel + 1);
for (int i = 0; i < nivel; i++)
printf(" ");
printf("%d\n", raiz->id);
desenhar(raiz->esq, nivel + 1);
}
}
//-------------------------------
// Menu
//-------------------------------
void menu() {
printf("\n======= AVL =======\n");
printf("1 - Inserir\n");
printf("2 - Remover\n");
printf("3 - Buscar\n");
printf("4 - Desenhar árvore\n");
printf("5 - Em ordem\n");
printf("0 - Sair\n");
printf("Opção: ");
}
//-------------------------------
// MAIN
//-------------------------------
int main() {
No *raiz = NULL;
int op, id;
do {
menu();
scanf("%d", &op);
switch(op) {
case 1:
printf("Valor: ");
scanf("%d", &id);
raiz = inserir(raiz, id);
break;
case 2:
printf("Valor: ");
scanf("%d", &id);
raiz = remover(raiz, id);
break;
case 3:
printf("Valor: ");
scanf("%d", &id);
if (buscar(raiz, id))
printf("Encontrado!\n");
else
printf("Não encontrado.\n");
break;
case 4:
printf("\nÁrvore:\n");
desenhar(raiz, 0);
break;
case 5:
printf("Em ordem: ");
emOrdem(raiz);
printf("\n");
break;
case 0:
printf("Encerrando...\n");
break;
default:
printf("Opção inválida!\n");
}
} while (op != 0);
return 0;
}
#31
Árvore B (ordem MAX=3)31-ArvoreB.c
Árvore B de ordem 3: estrutura multiway balanceada. Quando uma página fica cheia a chave do meio é promovida ao nível superior, mantendo a árvore balanceada em altura.
Árvore BRecursivo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// Disciplina: Estruturas de Dados - IFBA Campus Feira de Santana
//
// Árvore B (ordem definida por MAX)
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
//-------------------------------
// Estrutura da página
//-------------------------------
typedef struct pagina {
int chaves[2 * MAX];
int n; // quantidade de chaves
struct pagina *filhos[2 * MAX + 1];
} Pagina;
//-------------------------------
// Criação de página
//-------------------------------
Pagina *criarPagina(int chave, Pagina *filhoDir, Pagina *raiz) {
Pagina *p = (Pagina*) malloc(sizeof(Pagina));
if (!p) {
printf("Erro de memória!\n");
exit(EXIT_FAILURE);
}
p->n = 1;
p->chaves[1] = chave;
for (int i = 0; i < 2 * MAX + 1; i++)
p->filhos[i] = NULL;
p->filhos[0] = raiz;
p->filhos[1] = filhoDir;
return p;
}
//-------------------------------
// Inserção em página
//-------------------------------
void inserirNaPagina(Pagina *p, int chave, Pagina *filhoDir, int pos) {
int i = p->n;
while (i > pos) {
p->chaves[i + 1] = p->chaves[i];
p->filhos[i + 1] = p->filhos[i];
i--;
}
p->chaves[pos + 1] = chave;
p->filhos[pos + 1] = filhoDir;
p->n++;
}
//-------------------------------
// Divisão de página
//-------------------------------
void dividirPagina(Pagina *p, int chave, int *promo, Pagina *filhoDir,
int pos, Pagina **nova) {
int meio = (pos > MIN) ? MIN + 1 : MIN;
*nova = (Pagina*) malloc(sizeof(Pagina));
if (!(*nova)) {
printf("Erro de memória!\n");
exit(EXIT_FAILURE);
}
// copiar metade superior
int j = meio + 1;
while (j <= MAX) {
(*nova)->chaves[j - meio] = p->chaves[j];
(*nova)->filhos[j - meio] = p->filhos[j];
j++;
}
(*nova)->n = MAX - meio;
p->n = meio;
// inserir nova chave
if (pos <= MIN)
inserirNaPagina(p, chave, filhoDir, pos);
else
inserirNaPagina(*nova, chave, filhoDir, pos - meio);
*promo = p->chaves[p->n];
(*nova)->filhos[0] = p->filhos[p->n];
p->n--;
}
//-------------------------------
// Inserção recursiva
//-------------------------------
int inserirRec(Pagina *p, int chave, int *promo, Pagina **filhoDir) {
if (p == NULL) {
*promo = chave;
*filhoDir = NULL;
return 1;
}
int pos;
if (chave < p->chaves[1]) {
pos = 0;
} else {
for (pos = p->n; (chave < p->chaves[pos] && pos > 1); pos--);
if (chave == p->chaves[pos]) {
printf("Chave duplicada!\n");
return 0;
}
}
if (inserirRec(p->filhos[pos], chave, promo, filhoDir)) {
if (p->n < MAX) {
inserirNaPagina(p, *promo, *filhoDir, pos);
return 0;
} else {
dividirPagina(p, *promo, promo, *filhoDir, pos, filhoDir);
return 1;
}
}
return 0;
}
//-------------------------------
// Interface de inserção
//-------------------------------
Pagina *inserir(int chave, Pagina *raiz) {
int promo;
Pagina *filhoDir;
if (inserirRec(raiz, chave, &promo, &filhoDir))
raiz = criarPagina(promo, filhoDir, raiz);
return raiz;
}
//-------------------------------
// Busca (retorna 1 se encontrou)
//-------------------------------
int buscar(Pagina *p, int chave) {
if (!p) return 0;
int pos;
if (chave < p->chaves[1]) {
pos = 0;
} else {
for (pos = p->n; (chave < p->chaves[pos] && pos > 1); pos--);
if (chave == p->chaves[pos])
return 1;
}
return buscar(p->filhos[pos], chave);
}
//-------------------------------
// Impressão em ordem
//-------------------------------
void imprimir(Pagina *p) {
if (p) {
for (int i = 0; i < p->n; i++) {
imprimir(p->filhos[i]);
printf("%d ", p->chaves[i + 1]);
}
imprimir(p->filhos[p->n]);
}
}
//-------------------------------
// MAIN
//-------------------------------
int main() {
Pagina *raiz = NULL;
int x;
// Inserção
while (1) {
printf("Digite chave (>=0 insere, -1 sai): ");
scanf("%d", &x);
if (x < 0) break;
raiz = inserir(x, raiz);
printf("Árvore (em ordem): ");
imprimir(raiz);
printf("\n");
}
// Busca
printf("\nDigite valor para buscar: ");
scanf("%d", &x);
if (buscar(raiz, x))
printf("Elemento %d encontrado!\n", x);
else
printf("Elemento %d NÃO encontrado!\n", x);
return 0;
}
#32
Árvore B+ (chaves string)32-ArvoreBPlus.c
Árvore B+: todos os dados nas folhas ligadas em lista para varredura sequencial eficiente. Nós internos guardam apenas cópias para roteamento. Chaves do tipo string.
Árvore BRecursivo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// Disciplina: Estruturas de Dados - IFBA Campus Feira de Santana
//
// Árvore B (ordem definida por MAX)
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ORDEM 3
#define MAX (2*ORDEM)
#define MIN ORDEM
#define TAM 50
typedef struct No {
int n;
char chaves[MAX][TAM];
struct No *filhos[MAX+1];
int folha;
struct No *prox;
} No;
/* ============================= */
/* CRIAÇÃO */
/* ============================= */
No* criarNo(int folha){
No* n = malloc(sizeof(No));
n->n = 0;
n->folha = folha;
n->prox = NULL;
for(int i=0;i<MAX+1;i++)
n->filhos[i]=NULL;
return n;
}
/* ============================= */
/* BUSCA */
/* ============================= */
No* buscarFolha(No* raiz, char* chave){
while(raiz && !raiz->folha){
int i=0;
while(i<raiz->n && strcmp(chave, raiz->chaves[i])>0)
i++;
raiz = raiz->filhos[i];
}
return raiz;
}
int buscar(No* raiz, char* chave){
No* folha = buscarFolha(raiz,chave);
if(!folha) return 0;
for(int i=0;i<folha->n;i++)
if(strcmp(folha->chaves[i],chave)==0)
return 1;
return 0;
}
/* ============================= */
/* INSERÇÃO EM FOLHA */
/* ============================= */
void inserirFolha(No* folha, char* chave){
int i=folha->n-1;
while(i>=0 && strcmp(chave, folha->chaves[i])<0){
strcpy(folha->chaves[i+1], folha->chaves[i]);
i--;
}
strcpy(folha->chaves[i+1], chave);
folha->n++;
}
/* ============================= */
/* DIVISÃO */
/* ============================= */
void dividirFolha(No* folha, char* chave, char* sobe, No** nova){
char temp[MAX+1][TAM];
for(int i=0;i<MAX;i++)
strcpy(temp[i], folha->chaves[i]);
inserirFolha(folha,chave);
int meio = (MAX+1)/2;
*nova = criarNo(1);
folha->n=0;
for(int i=0;i<meio;i++){
strcpy(folha->chaves[i], temp[i]);
folha->n++;
}
for(int i=meio,j=0;i<MAX+1;i++,j++){
strcpy((*nova)->chaves[j], temp[i]);
(*nova)->n++;
}
(*nova)->prox = folha->prox;
folha->prox = *nova;
strcpy(sobe, (*nova)->chaves[0]);
}
void dividirInterno(No* no, char* chave, No* filho, char* sobe, No** novo){
int i,j;
char tempChaves[MAX+1][TAM];
No* tempFilhos[MAX+2];
for(i=0;i<no->n;i++)
strcpy(tempChaves[i], no->chaves[i]);
for(i=0;i<=no->n;i++)
tempFilhos[i]=no->filhos[i];
i=no->n-1;
while(i>=0 && strcmp(chave,tempChaves[i])<0){
strcpy(tempChaves[i+1],tempChaves[i]);
tempFilhos[i+2]=tempFilhos[i+1];
i--;
}
strcpy(tempChaves[i+1],chave);
tempFilhos[i+2]=filho;
int meio = (MAX)/2;
*novo = criarNo(0);
no->n=0;
for(i=0;i<meio;i++){
strcpy(no->chaves[i],tempChaves[i]);
no->filhos[i]=tempFilhos[i];
no->n++;
}
no->filhos[i]=tempFilhos[i];
strcpy(sobe,tempChaves[meio]);
for(i=meio+1,j=0;i<MAX+1;i++,j++){
strcpy((*novo)->chaves[j],tempChaves[i]);
(*novo)->filhos[j]=tempFilhos[i];
(*novo)->n++;
}
(*novo)->filhos[j]=tempFilhos[MAX+1];
}
/* ============================= */
/* INSERÇÃO RECURSIVA */
/* ============================= */
int inserirRec(No* no, char* chave, char* sobe, No** novoFilho){
if(no->folha){
if(no->n<MAX){
inserirFolha(no,chave);
return 0;
}
dividirFolha(no,chave,sobe,novoFilho);
return 1;
}
int i=0;
while(i<no->n && strcmp(chave,no->chaves[i])>0)
i++;
char novaChave[TAM];
No* novo;
if(inserirRec(no->filhos[i],chave,novaChave,&novo)){
if(no->n<MAX){
int j=no->n-1;
while(j>=i){
strcpy(no->chaves[j+1],no->chaves[j]);
no->filhos[j+2]=no->filhos[j+1];
j--;
}
strcpy(no->chaves[i],novaChave);
no->filhos[i+1]=novo;
no->n++;
return 0;
}
dividirInterno(no,novaChave,novo,sobe,novoFilho);
return 1;
}
return 0;
}
No* inserir(No* raiz, char* chave){
if(!raiz){
raiz=criarNo(1);
strcpy(raiz->chaves[0],chave);
raiz->n=1;
return raiz;
}
char sobe[TAM];
No* novo;
if(inserirRec(raiz,chave,sobe,&novo)){
No* novaRaiz = criarNo(0);
strcpy(novaRaiz->chaves[0],sobe);
novaRaiz->filhos[0]=raiz;
novaRaiz->filhos[1]=novo;
novaRaiz->n=1;
return novaRaiz;
}
return raiz;
}
/* ============================= */
/* REMOÇÃO (simplificada completa)*/
/* ============================= */
void removerFolha(No* folha, char* chave){
int i;
for(i=0;i<folha->n;i++)
if(strcmp(folha->chaves[i],chave)==0)
break;
for(;i<folha->n-1;i++)
strcpy(folha->chaves[i],folha->chaves[i+1]);
folha->n--;
}
/* (Obs: implementação completa de rebalanceamento é extensa,
aqui mantemos versão funcional simplificada didática) */
/* ============================= */
/* IMPRESSÃO */
/* ============================= */
void imprimirFolhas(No* raiz){
if(!raiz) return;
while(!raiz->folha)
raiz = raiz->filhos[0];
while(raiz){
for(int i=0;i<raiz->n;i++)
printf("%s ",raiz->chaves[i]);
raiz = raiz->prox;
}
printf("\n");
}
/* ============================= */
/* MAIN */
/* ============================= */
int main(){
No* raiz=NULL;
int op;
char palavra[TAM];
do{
printf("\n1 Inserir\n2 Buscar\n3 Mostrar\n0 Sair\n");
scanf("%d",&op);
switch(op){
case 1:
scanf("%s",palavra);
raiz = inserir(raiz,palavra);
break;
case 2:
scanf("%s",palavra);
printf(buscar(raiz,palavra) ? "Encontrado\n":"Nao encontrado\n");
break;
case 3:
imprimirFolhas(raiz);
break;
}
}while(op!=0);
return 0;
}
#33
Tabela Hash com Encadeamento33-TabelaHASH.c
Tabela Hash tamanho 10 com encadeamento para colisões. Função hash: chave % TAM. Suporta inserção, busca, remoção e impressão com pares (int, string).
HashIterativo
//---------------------------------------------------------------------
//
// Algoritmo desenvolvido pela professora Ana Carolina Sokolonski Anton
// Disciplina: Estruturas de Dados - IFBA Campus Feira de Santana
//
// Árvore B (ordem definida por MAX)
//---------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAM 10 7
//===============================
// Estrutura do nó (lista ligada)
//===============================
typedef struct No {
int chave;
char valor[50];
struct No *prox;
} No;
//===============================
// Tabela Hash
//===============================
No* tabela[TAM];
//===============================
// Função Hash
//===============================
// Método simples: resto da divisão
int funcaoHash(int chave) {
return chave % TAM;
}
//===============================
// Inicializar tabela
//===============================
void inicializar() {
for (int i = 0; i < TAM; i++)
tabela[i] = NULL;
}
//===============================
// Inserir elemento
//===============================
void inserir(int chave, char valor[]) {
int indice = funcaoHash(chave);
No* novo = (No*) malloc(sizeof(No));
if (!novo) {
printf("Erro de memória!\n");
exit(1);
}
novo->chave = chave;
strcpy(novo->valor, valor);
// Inserção no início da lista (mais simples)
novo->prox = tabela[indice];
tabela[indice] = novo;
}
//===============================
// Buscar elemento
//===============================
No* buscar(int chave) {
int indice = funcaoHash(chave);
No* p = tabela[indice];
while (p != NULL) {
if (p->chave == chave)
return p;
p = p->prox;
}
return NULL;
}
//===============================
// Remover elemento
//===============================
void remover(int chave) {
int indice = funcaoHash(chave);
No* p = tabela[indice];
No* ant = NULL;
while (p != NULL && p->chave != chave) {
ant = p;
p = p->prox;
}
if (p == NULL) {
printf("Elemento não encontrado!\n");
return;
}
if (ant == NULL) {
// remover primeiro da lista
tabela[indice] = p->prox;
} else {
ant->prox = p->prox;
}
free(p);
printf("Elemento removido com sucesso!\n");
}
//===============================
// Imprimir tabela
//===============================
void imprimir() {
printf("\n===== TABELA HASH =====\n");
for (int i = 0; i < TAM; i++) {
printf("[%d] -> ", i);
No* p = tabela[i];
while (p != NULL) {
printf("(%d,%s) -> ", p->chave, p->valor);
p = p->prox;
}
printf("NULL\n");
}
}
//===============================
// MAIN
//===============================
int main() {
int opcao, chave;
char valor[50];
inicializar();
do {
printf("\n--- MENU HASH ---\n");
printf("1 - Inserir\n");
printf("2 - Buscar\n");
printf("3 - Remover\n");
printf("4 - Imprimir\n");
printf("0 - Sair\n");
printf("Opcao: ");
scanf("%d", &opcao);
switch (opcao) {
case 1:
printf("Chave (int): ");
scanf("%d", &chave);
printf("Valor (string): ");
scanf("%s", valor);
inserir(chave, valor);
break;
case 2:
printf("Chave: ");
scanf("%d", &chave);
No* encontrado = buscar(chave);
if (encontrado)
printf("Encontrado: %s\n", encontrado->valor);
else
printf("Nao encontrado!\n");
break;
case 3:
printf("Chave: ");
scanf("%d", &chave);
remover(chave);
break;
case 4:
imprimir();
break;
}
} while (opcao != 0);
return 0;
}