Estruturas de Dados - Listas Lineares (União de Conjuntos, Listas Encadeadas, Quadrado Latino, Problema do Mágico, etc.)

Armazenamento Sequencial de Listas Lineares
Implementação de União de Conjuntos com Ordenação Bolha
Armazenamento Encadeado de Listas Lineares
Lista Simplesmente Encadeada
Lista Estática
Exercício: Obtenção Rápida do Nó Central
Lista Simplesmente Circular
Problema de Josephus - Versão Básica
Problema de Josephus - Versão Avançada
Mesclagem de Duas Listas Circulares
Detecção de Ciclos em Listas
Problema do Mágico e as Cartas★
Problema do Quadrado Latino
Lista Duplamente Circular

O armazenamento sequencial utiliza um array para guardar os elementos da lista, organizando-os em posições contíguas de memória. Esta abordagem permite acesso direto aos elementos através de índice, oferecendo complexidade O(1) para consultas por posição.

# include<stdio.h>
# include<stdlib.h>


# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0


typedef int status;


const int MaxSize = 20;
typedef int ElemType;
typedef struct
{
    ElemType dados[MaxSize];
    int tamanho;
} ListaSequencial;



status ObterElemento(ListaSequencial lista, int posicao, ElemType *elemento)
{
    if(lista.tamanho == 0 || lista.tamanho < posicao)   
    {
        return ERROR;
    } 
    *elemento = lista.dados[posicao - 1];
    return *elemento;
}


status InserirElemento(ListaSequencial *lista, int posicao, ElemType elemento)
{
    int k ;
    if (lista->tamanho == MaxSize)
    {
        return ERROR;
    }
    if ( posicao < 0 || posicao > lista->tamanho + 1)
    {
        return ERROR;
    }
    if ( posicao <= lista->tamanho)
    {
        for ( int k = lista->tamanho - 1; k >= posicao - 1; k --)
        {
            lista->dados[ k + 1 ] = lista->dados[k];
        }
    }
    lista->dados[posicao - 1] = elemento;
    lista->tamanho ++ ;
    return OK; 
}


status RemoverElemento(ListaSequencial *lista, int posicao, ElemType elemento)
{
    if(lista->tamanho == 0)
    {
        return ERROR;
    }
    else if (posicao <= 0 || posicao > lista->tamanho)
    {
        return ERROR;
    }
    elemento = lista->dados[posicao - 1]; 
    printf("Elemento removido: %d\n", elemento);
    for(int k = posicao - 1; k <= lista->tamanho - 1; k ++)
    {
        lista->dados[k] = lista->dados[k + 1];
    }
    lista->tamanho --;
    return OK;
}


status ImprimirLista(ListaSequencial *lista)
{
    printf("Lista: ");
    for(int i = 0; i < lista->tamanho; i ++)
    {
        printf("%d ", lista->dados[i]);
    }
    printf("\n");
    return OK;
}



int main()
{
    printf("Sistema de Gerenciamento de Lista Sequencial\n");
    printf("--------------------------------------------------\n");
    printf("|Menu de Opções:\n");
    printf("|1. Inserir elemento\n");
    printf("|2. Remover por posição\n");
    printf("--------------------------------------------------\n");
    printf("Digite uma opção:\n");

    ListaSequencial lista;
    lista.tamanho = 0;
    
    while(1)
    {
        int opcao;
        scanf("%d", &opcao);
        system("cls");
        if(opcao == 1)
        {
            int quantidade;
            printf("Quantos elementos deseja inserir?\n");
            scanf("%d", &quantidade);
            for(int i = 1; i <= quantidade; i ++)
            {
                int elemento;
                printf("Digite o valor do elemento:\n");
                scanf("%d", &elemento);
                InserirElemento(&lista, i, elemento);
                ImprimirLista(&lista);
            }
        }
        else if (opcao == 2)
        {
            system("cls");
            printf("Digite a posição do elemento a remover\n");
            int posicao;
            scanf("%d", &posicao);
            int elemento = 0;
            RemoverElemento(&lista, posicao, elemento);
            ImprimirLista(&lista);
        }
    }

    system("pause");
    return 0;
}

União de Conjuntos com Ordenação Bolha

Esta implementação demonstra a união de dois conjuntos utilizando lista sequencial, seguida de ordenação bolha para orgenizar os elementos em ordem crescente.

# include<stdlib.h>
# include<stdio.h>

# define OK 1
# define ERROR 0
# define MaxSize 100

typedef int ElemType;


typedef struct Colecao
{
    ElemType *elementos;
    int contador;
} Colecao;
typedef Colecao *PtrColecao;


int inicializarColecao(PtrColecao colecao)
{
    colecao->elementos = (ElemType *) malloc(MaxSize * sizeof(ElemType));
    colecao->contador = 0;
    return OK;
}

int adicionarElemento(PtrColecao colecao, ElemType elemento)
{
    colecao->elementos[colecao->contador ++] = elemento;
    return OK;
}

int removerDuplicado(PtrColecao colecao, ElemType elemento)
{
    int posicao = -1;
    for(int i = 0; i < colecao->contador; i ++)
    {
        if(colecao->elementos[i] == elemento)
        {
            posicao = i;
            break;
        }
    }
    while(posicao < colecao->contador && posicao != -1)
    {
        colecao->elementos[posicao] = colecao->elementos[posicao + 1];
        posicao ++;
    }
    colecao->contador --;
    return OK;
}

int unirColecoes(PtrColecao conjuntoA, PtrColecao conjuntoB)
{
    for(int i = 0; i < conjuntoB->contador; i ++)
    {
        for(int j = 0; j < conjuntoA->contador; j ++)
        {
            if(conjuntoB->elementos[i] == conjuntoA->elementos[j])
            {
                removerDuplicado(conjuntoB, conjuntoB->elementos[i]);
            }
            else continue;
        }
    }

    int indiceA = conjuntoA->contador;
    for(int i = 0; i < conjuntoB->contador; i ++)
    {
        conjuntoA->elementos[indiceA ++] = conjuntoB->elementos[i];
        conjuntoA->contador ++;
    }

    return OK;
}

void exibirColecao(PtrColecao colecao)
{
    for(int i = 0; i < colecao->contador; i ++)
    {
        printf("%d-", colecao->elementos[i]);
    }
    printf("\n");
}


void ordenarBolha(PtrColecao colecao)
{
    for(int iteracao = 0; iteracao < colecao->contador; iteracao ++)
    {
        for(int i = 0; i < colecao->contador - iteracao - 1; i ++)
        {
            if( colecao->elementos[i] > colecao->elementos[i + 1] )
            {
                int temp = colecao->elementos[i];
                colecao->elementos[i] = colecao->elementos[i + 1];
                colecao->elementos[i + 1] = temp;
            }
        }
    }
}


int main()
{
    int tamanhoA, tamanhoB, elemento;
    PtrColecao conjuntoA = (PtrColecao)malloc(sizeof(Colecao));
    PtrColecao conjuntoB = (PtrColecao)malloc(sizeof(Colecao));
    inicializarColecao(conjuntoA);
    inicializarColecao(conjuntoB);

    printf("Digite o número de elementos do conjunto A\n");
    scanf("%d", &tamanhoA);
    printf("Digite os elementos do conjunto A\n");
    while(tamanhoA --)
    {
        scanf("%d", &elemento);
        adicionarElemento(conjuntoA, elemento);
    }

    printf("Digite o número de elementos do conjunto B\n");
    scanf("%d", &tamanhoB);
    printf("Digite os elementos do conjunto B\n");
    while(tamanhoB --)
    {
        scanf("%d", &elemento);
        adicionarElemento(conjuntoB, elemento);
    }
    
    if(conjuntoA->contador > conjuntoB->contador) 
    {
        unirColecoes(conjuntoA, conjuntoB);
        printf("Conjunto ordenado resultante:");
        ordenarBolha(conjuntoA);
        exibirColecao(conjuntoA);
    }
    else 
    {
        unirColecoes(conjuntoB, conjuntoA);
        printf("Conjunto ordenado resultante:");
        ordenarBolha(conjuntoB);
        exibirColecao(conjuntoB);
    }
    
    system("pause");
    return 0;
}

Armazenamento Encadeado de Listas Lineares

O armazenamento encadeado utiliza ponteiros para conectar os nós da lista, permitindo alocação dinâmica de memória e inserção/remoção eficiente sem deslocar elementos.

Lista Simplesmente Encadeada

# include<stdio.h>
# include<stdlib.h>


# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0


typedef int status;


typedef int ElemType;

typedef struct No
{
    ElemType dados;
    struct No *proximo;
} No;

typedef struct No *ListaEncadeada;  


ListaEncadeada criarLista(void)
{
    ListaEncadeada cabeca = (ListaEncadeada)malloc(sizeof(No));
    ListaEncadeada lista = cabeca;
    
    cabeca->proximo = NULL; 
    cabeca->dados = 0;
    return lista;
}


status inserirElemento(ListaEncadeada lista, ElemType elemento, int posicao)
{
    ListaEncadeada ponteiro;
    ponteiro = lista;
    int indice = 0; 
    while(indice < posicao && ponteiro)
    {
        ponteiro = ponteiro->proximo;
        indice ++;
    }
    if (!ponteiro) 
    {
        printf("Ponteiro nulo\n");
        return ERROR;
    }

    ListaEncadeada novoNo = (ListaEncadeada)malloc(sizeof(No));
    novoNo->dados = elemento;
    novoNo->proximo = ponteiro->proximo;
    ponteiro->proximo = novoNo;
    lista->dados ++;
    printf("Tamanho atual da lista: %d\n", lista->dados);
    return OK;
}


status imprimirLista(ListaEncadeada lista)
{
    printf("Lista:\n");
    ListaEncadeada ponteiro = lista->proximo;
    while(ponteiro)
    {
        printf("%d-", ponteiro->dados);
        ponteiro = ponteiro->proximo;
    }
    printf("\n");
    return OK;
}


status buscarElemento(ListaEncadeada lista, int posicao, ElemType *elemento)
{
    ListaEncadeada ponteiro = lista->proximo;
    int indice = 1;
    while(ponteiro && indice < posicao)
    {
        ponteiro = ponteiro->proximo;
        indice ++;
    }
    if (!ponteiro)
    {
        return ERROR;
    }
    *elemento = ponteiro->dados;
    return OK;
}


status removerElemento(ListaEncadeada lista, int posicao)
{
    ListaEncadeada ponteiro;
    ponteiro = lista;
    int indice = 1;
    while( indice < posicao && ponteiro)
    {
        ponteiro = ponteiro->proximo;
        printf("Removendo - percorrendo até %d\n", ponteiro->dados);
        indice ++;
    }
    if( !ponteiro )
    {
        return ERROR;
    }
    int elemento;
    ListaEncadeada temporario = ponteiro->proximo;
    elemento = temporario->dados;
    printf("Elemento %d na posição %d foi removido!\n", elemento, posicao);
    ponteiro->proximo = ponteiro->proximo->proximo;
    lista->dados --;
    free(temporario);

    return OK;
}


int main()
{
    ListaEncadeada lista = criarLista();
    while(1)
    {
        printf("-------------------------Menu---------------------\n");
        printf("0. Limpar tela\n");
        printf("1. Inserir novo elemento na posição i\n");
        printf("2. Buscar elemento na posição i\n");
        printf("3. Remover elemento na posição i\n");
        printf("--------------------------------------------------\n");
        int opcao;
        scanf("%d", &opcao);
        if(opcao == 1)
        {
            int posicao, elemento;
            printf("Digite a posição e o valor (para inserir no início use 0 valor)\n");
            scanf("%d %d", &posicao, &elemento);
            inserirElemento(lista, elemento, posicao);
            printf("Inserção concluída!\n");
            imprimirLista(lista);
        }
        else if (opcao == 2)
        {
            int posicao;
            ElemType elemento;
            printf("Digite a posição\n");
            scanf("%d", &posicao);
            buscarElemento(lista, posicao, &elemento);
            printf("%d\n", elemento);
        }
        else if(opcao == 3)
        {
            int posicao;
            printf("Digite a posição\n");
            scanf("%d", &posicao);
            removerElemento(lista, posicao);
            imprimirLista(lista);
            printf("\n");
        }
        else if(opcao == 0)
        {
            system("cls");
        }
    }
    return 0;
}

Lista Estática

Implementação utilizando dois arrays para simular uma lista encadeada, útil em linguagens que não suportam ponteiros diretamente.

# include<stdio.h>
# include<stdlib.h>

# define OK 1
# define ERROR 0


const int TamanhoMaximo = 10000;
int cabeca, elementos[TamanhoMaximo], proximos[TamanhoMaximo], indice;


int inicializarLista(void)
{
    cabeca = -1;
    indice = 0;
    return OK;
}

int contarElementos(void)
{
    if(cabeca == -1) return 0;
    int ponteiro = cabeca;
    int contador = 0;
    while( ponteiro >= 0)
    {
        ponteiro = proximos[ponteiro];
        contador ++;
    }
    return contador;
}

int inserirNoInicio(int valor)
{
    elementos[indice] = valor;
    proximos[indice] = cabeca;
    cabeca = indice ++;
    return OK;
}

int inserirAposPosicao(int posicao, int valor)
{
    elementos[indice] = valor;
    proximos[indice] = proximos[posicao];
    proximos[posicao] = indice ++;
    return OK;
}

int removerPrimeiro(void)
{
    cabeca = proximos[cabeca];
    return OK;
}

int removerAposPosicao(int posicao)
{
    proximos[posicao] = proximos[proximos[posicao]];
    return OK;
}

void imprimirLista(void)
{
    int ponteiro = cabeca;
    printf("Lista:\n");
    while(ponteiro >= 0)
    {
        printf("%d-", elementos[ponteiro]);
        ponteiro = proximos[ponteiro];
    }
    printf("\n");
}

int main()
{
    inicializarLista();
    while (1)
    {
        printf("--------------------menu-----------------------\n");
        printf("1. Inserir no início\n");
        printf("2. Inserir após a posição k\n");
        printf("3. Remover após a posição k\n");
        printf("-----------------------------------------------------------------\n");
        int opcao;
        scanf("%d", &opcao);
        if(opcao == 1)
        {
            int valor;
            printf("Digite o valor:\n");
            scanf("%d", &valor);
            inserirNoInicio(valor);
            imprimirLista();
        }
        else if(opcao == 2)
        {
            int posicao, valor;
            printf("Nota: Este método não permite inserção no início ou fim!!!\n");
            printf("Digite a posição e o valor:\n");
            scanf("%d%d", &posicao, &valor);
            inserirAposPosicao(posicao, valor);
            imprimirLista();
        }
        else if(opcao == 3)
        {
            int posicao;
            printf("Digite a posição:\n");
            scanf("%d", &posicao);
            removerAposPosicao(posicao);
            imprimirLista();
        }
    }
    return 0;
}

Exercício: Obtenção Rápida do Nó Central

Utilizando a técnica de ponteiros rápido e lanto, podemos encontrar o elemento central de uma lista simplesmente encadeada em uma única travessia.

# include<stdio.h>
# include<stdlib.h>
# include<time.h>

int gerarNumeroAleatorio(void)
{
    srand((unsigned)time(0) + rand());
    return rand() % 100;
}


typedef struct NoIndividual 
{
    int valor;
    struct NoIndividual *proximo;
} NoIndividual;

typedef NoIndividual *ListaAleatoria;


ListaAleatoria gerarListaAleatoria(void)
{
    ListaAleatoria ponteiro = NULL;

    ListaAleatoria noCabeca = (ListaAleatoria)malloc(sizeof(NoIndividual));
    ponteiro = noCabeca;
    noCabeca->proximo = NULL;
    
    for(int i = 0; i < 20; i ++)
    {
        ListaAleatoria no = (ListaAleatoria)malloc(sizeof(NoIndividual));
        no->valor = gerarNumeroAleatorio();
        no->proximo = noCabeca->proximo;
        noCabeca->proximo = no;
        printf("%d-", no->valor);
    }
    printf("\n");
    return noCabeca;
}

int encontrarElementoCentral(ListaAleatoria lista)
{
    lista = lista->proximo;
    ListaAleatoria ptrRapido = lista;
    ListaAleatoria ptrLento = lista;

    while(ptrRapido)
    {
        ptrRapido = (ptrRapido->proximo)->proximo;
        ptrLento = ptrLento->proximo;
    }

    int central = ptrLento->valor;
    printf("Elemento central = %d\n", central);
    return central;
}

int main()
{
    ListaAleatoria listaGerada = gerarListaAleatoria();
    encontrarElementoCentral(listaGerada);
    system("pause");
    return 0;
}

Lista Simplesmente Circular

Na lista simplesmente circular, o último nó aponta de volta para o primeiro nó, formando um ciclo fechado. Esta estrutura é particularmente útil para problemas que envolvem repetição cíclica.

# include<stdlib.h>
# include<stdio.h>
# define OK 1
# define ERROR 0
typedef struct NoCircular
{
    int valor;
    struct NoCircular *proximo;
} NoCircular;

typedef NoCircular* ListaCircular;


ListaCircular inicializarListaCircular(void)
{
    ListaCircular lista;
    NoCircular *cabeca = (NoCircular*)malloc(sizeof(NoCircular));
    if(cabeca == NULL) exit(0);
    cabeca->proximo = cabeca;
    lista = cabeca;
    return lista;
}

int obterTamanho(ListaCircular lista)
{
    int tamanho = 0;
    for(NoCircular *noh = lista; noh->proximo != lista; )
    {
        noh = noh->proximo;
        tamanho ++;
    }
    return tamanho;
}

void inserirNoInicioCircular(ListaCircular lista, int elemento)
{
    NoCircular *novo = (NoCircular*)malloc(sizeof(NoCircular));
    novo->valor = elemento;
    novo->proximo = lista->proximo;
    lista->proximo = novo;
}

void imprimirListaCircular(ListaCircular lista)
{
    printf("Lista:\n");
    for(NoCircular *noh = lista; noh->proximo != lista;)
    {
        noh = noh->proximo;
        printf("%d-", noh->valor);
    }
    printf("\n");
}

void inserirNoFimCircular(ListaCircular lista, int elemento)
{
    NoCircular *novo = (NoCircular*)malloc(sizeof(NoCircular));
    novo->valor = elemento;
    NoCircular *ponteiro = lista;
    while(ponteiro->proximo != lista) ponteiro = ponteiro->proximo;
    ponteiro->proximo = novo;
    novo->proximo = lista;
}

int inserirNaPosicaoCircular(ListaCircular lista, int elemento, int posicao)
{
    if(posicao < 0 || posicao > obterTamanho(lista))
    {
        printf("Posição inválida!\n");
        return ERROR;
    }
    NoCircular *novo = (NoCircular*)malloc(sizeof(NoCircular));
    novo->valor = elemento;
    NoCircular *ponteiro = lista;
    for(int k = 0; k < posicao; k ++)
    {
        ponteiro = ponteiro->proximo;
    }
    novo->proximo = ponteiro->proximo;
    ponteiro->proximo = novo;
    return OK;
}

int removerDaPosicaoCircular(ListaCircular lista, int posicao)
{
    NoCircular *ponteiro = lista;
    for(int k = 0; k < posicao - 1; k ++)
    {
        ponteiro = ponteiro->proximo;
    }
    NoCircular *remover = ponteiro->proximo;
    ponteiro->proximo = ponteiro->proximo->proximo;
    free(remover);
    return OK;
}

int main()
{
    ListaCircular lista = inicializarListaCircular();
    while(1)
    {
        printf("=======================================================\n");
        printf("Digite a operação:\n");
        printf("1. Inserir elemento no início\n");
        printf("2. Mostrar tamanho da lista\n");
        printf("3. Inserir elemento no fim\n");
        printf("4. Inserir elemento após a posição i\n");
        printf("5. Remover nó na posição i\n");
        printf("...\n");
        printf("=======================================================\n");
        int opcao;
        scanf("%d", &opcao);

        if(opcao == 1)
        {
            int elemento;
            printf("Digite o valor do elemento:\n");
            scanf("%d", &elemento);
            inserirNoInicioCircular(lista, elemento);
            imprimirListaCircular(lista);
        }
        else if(opcao == 2)
        {
            int tamanho = obterTamanho(lista);
            printf("Tamanho da lista: %d\n", tamanho); 
        }
        else if(opcao == 3)
        {
            int elemento;
            printf("Digite o valor do elemento:\n");
            scanf("%d", &elemento);
            inserirNoFimCircular(lista, elemento);
            imprimirListaCircular(lista);
        }
        else if(opcao == 4)
        {
            int posicao, elemento;
            printf("Digite a posição e o valor:\n");
            scanf("%d%d", &posicao, &elemento);
            inserirNaPosicaoCircular(lista, elemento, posicao);
            imprimirListaCircular(lista);
        }
        else if(opcao == 5)
        {
            int posicao;
            printf("Digite a posição do nó a remover:\n");
            scanf("%d", &posicao);
            removerDaPosicaoCircular(lista, posicao);
            imprimirListaCircular(lista);
        }
    }

    system("pause");
    return 0;
}

Problema de Josephus - Versão Básica

O problema clássico de Josephus pode ser facilmente resolvido utilizando listas circulares, onde pessoas são representadas como nós e a eliminação ocorre através da manipulação de ponteiros.

# include<stdio.h>
# include<stdlib.h>

# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0

typedef struct NoPessoa
{
    int identificador;
    struct NoPessoa *proximo;
} NoPessoa;

typedef NoPessoa *ListaPessoas;

ListaPessoas listaCircular;

int configurarLista(void)
{
    NoPessoa *ultimo = (NoPessoa*)malloc(sizeof(NoPessoa));
    ultimo->identificador = 41;
    ultimo->proximo = ultimo;
    listaCircular = ultimo;
    for(int i = 40; i >= 1; i --)
    {
        NoPessoa *novo = (NoPessoa*)malloc(sizeof(NoPessoa));
        novo->identificador = i;
        novo->proximo = ultimo->proximo;
        ultimo->proximo = novo;
    }
    return OK;
}

void mostrarLista(void)
{
    NoPessoa *ponteiro = listaCircular->proximo;
    while(ponteiro->proximo != listaCircular->proximo)
    {
        printf("%d-", ponteiro->identificador);
        ponteiro = ponteiro->proximo;
    }
    printf("%d", ponteiro->identificador);
    printf("\n");
}

void executarEliminacoes(void)
{
    NoPessoa *ponteiro = listaCircular->proximo;
    int contador = 1, sequencia = 1;
    while(ponteiro != NULL)
    {
        if(contador == 2)
        {
            NoPessoa *eliminar = ponteiro->proximo;
            ponteiro->proximo = ponteiro->proximo->proximo;
            printf("%d: Pessoa %d eliminada\n", sequencia ++, eliminar->identificador);
            free(eliminar);
        }
        contador ++;
        if(contador == 3) contador = 1;
        ponteiro = ponteiro->proximo;
        if(ponteiro->proximo == ponteiro) 
        {
            printf("Última pessoa restante: %d\n", ponteiro->identificador);
            break;
        }
    }
}

int main()
{
    configurarLista();
    mostrarLista();
    executarEliminacoes();
    system("pause");
    return 0;
}

Problema de Josephus - Versão Avançada

Na versão avançada, cada pessoa possui uma senha (número secreto) que determina quando será eliminada. A senha da pessoa eliminada determina a próxima contagem.

# include<stdio.h>
# include<stdlib.h>

# define OK 1
# define ERROR 0
# define TRUE 1 
# define FALSE 0

typedef struct NoJogador
{
    int identificador;
    struct NoJogador *proximo;
    int senha;
} NoJogador;

typedef NoJogador *ListaJogadores;

ListaJogadores listaJogadores;

ListaJogadores criarListaJogadores(void)
{
    printf("Configuração da lista:\n");
    
    NoJogador *cabeca = (NoJogador*)malloc(sizeof(NoJogador));
    cabeca->identificador = 1;
    
    int senha;
    printf("Digite a senha do jogador 1:\n");
    scanf("%d", &senha);
    cabeca->senha = senha;
    cabeca->proximo = cabeca;

    listaJogadores = cabeca;
    return listaJogadores;
}

int configurarJogadores(int quantidade)
{
    for(int i = 1; i < quantidade; i ++)
    {
        int senhaJogador;
        printf("Digite a senha do jogador %d:\n", i + 1);
        scanf("%d", &senhaJogador);
        
        NoJogador *novo = (NoJogador*)malloc(sizeof(NoJogador));
        novo->identificador = i + 1;
        novo->senha = senhaJogador;
        novo->proximo = listaJogadores->proximo;
        listaJogadores->proximo = novo;
        listaJogadores = novo;
    }
    return OK;
}

int listarJogadores()
{
    NoJogador *ponteiro = listaJogadores ->proximo;
    while(ponteiro->proximo != listaJogadores)
    {
        printf("Jogador %d, senha: %d\n", ponteiro->identificador, ponteiro->senha);
        ponteiro = ponteiro->proximo;
    }
    printf("Jogador %d, senha: %d\n", ponteiro->identificador, ponteiro->senha);
    ponteiro = ponteiro->proximo;
    printf("Jogador %d, senha: %d\n", ponteiro->identificador, ponteiro->senha);
    return OK;
}

int executarJogo(void)
{
    NoJogador *ponteiro = listaJogadores->proximo;
    int contagem = 1;
    int eliminados = 1;
    int senhaAtual = ponteiro->senha;
    while(ponteiro->proximo != ponteiro)
    {
        if (senhaAtual == 1) 
        {
            NoJogador *anterior = listaJogadores;
            while(anterior->proximo != ponteiro)
            {
                anterior = anterior->proximo; 
            }
            NoJogador *remover = anterior->proximo;
            if(anterior->proximo->identificador == listaJogadores->identificador)
            {
                listaJogadores = anterior;
            }
            anterior->proximo = anterior->proximo->proximo;
            
            ponteiro = ponteiro->proximo;
            printf("Jogador %d eliminado, senha: %d\n", eliminados ++, remover->senha);
            senhaAtual = remover->senha;
            free(remover);
            contagem = 1;
        }
        else if(contagem == senhaAtual - 1)
        {
            NoJogador *remover = ponteiro->proximo; 
            if(ponteiro->proximo->identificador == listaJogadores->identificador)
            {
                listaJogadores = ponteiro;
            }
            ponteiro->proximo = ponteiro->proximo->proximo;
            printf("Jogador %d eliminado, senha: %d\n", eliminados ++, remover->senha);
            senhaAtual = remover->senha;
            free(remover);
            ponteiro = ponteiro->proximo;
            contagem = 1;
        }
        else 
        {
            contagem++;
            ponteiro = ponteiro->proximo;
        }
    }
    printf("Último jogador: %d, senha: %d\n", eliminados, ponteiro->senha);
    return OK;
}

int main()
{
    criarListaJogadores();
    printf("Digite o número de jogadores:\n");
    int quantidade;
    scanf("%d", &quantidade);
    configurarJogadores(quantidade);
    listarJogadores();
    executarJogo();
    system("pause");
    return 0;
}

Mesclagem de Duas Listas Circulares

# include<stdio.h>
# include<stdlib.h>

# define OK 1
# define ERROR 0
# define FALSE 0
# define TRUE 1

typedef struct No
{
    int valor;
    struct No *proximo;
} No;

typedef No *ListaCircularDupla;


ListaCircularDupla criarListaCircularDupla(ListaCircularDupla lista)
{
    No *ultimo = (ListaCircularDupla)malloc(sizeof(No));
    ultimo -> valor = 10;
    ultimo -> proximo = ultimo;
    for(int i = 9; i >= 1; i --)
    {
        No *no = (ListaCircularDupla)malloc(sizeof(No));
        no->valor = i;
        no->proximo = ultimo->proximo;
        ultimo->proximo = no;
        ultimo = no;
    }
    lista = ultimo;
    return lista;
}

int imprimirListaCircularDupla(ListaCircularDupla lista)
{
    int tamanho = 1;
    printf("Lista: ");
    No *ponteiro;
    for(ponteiro = lista->proximo; ponteiro != lista; ponteiro = ponteiro->proximo)
    {
        printf("%d-", ponteiro->valor);
        tamanho ++;
    }
    printf("%d-", ponteiro->valor);
    printf("\n");
    printf("Tamanho da lista: %d\n", tamanho);
    return OK;
}

ListaCircularDupla mesclarListas(ListaCircularDupla listaA, ListaCircularDupla listaB)
{
    NoCircularDupla *inicioA = listaA->proximo;
    listaA->proximo = listaB->proximo;
    listaB->proximo = inicioA;
    return listaB;
}

int main(void)
{
    ListaCircularDupla lista1 = criarListaCircularDupla(lista1);
    ListaCircularDupla lista2 = criarListaCircularDupla(lista2);

    imprimirListaCircularDupla(lista1);
    imprimirListaCircularDupla(lista2);

    ListaCircularDupla lista3 = mesclarListas(lista1, lista2);
    imprimirListaCircularDupla(lista3);
    
    system("pause");
    return 0;
}

Detecção de Ciclos em Listas

Utiliza-se o algoritmo de Floyd (tartaruga e lebre) com dois ponteiros: um avança uma posição e outro avança duas posições por iteração. Se houver ciclo, os ponteiros se encontrarão.

# include<stdio.h>
# include<stdlib.h>

# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0

typedef struct NoSimples
{
    int valor;
    struct NoSimples *proximo;
} NoSimples;

typedef NoSimples *ListaLinear;

ListaLinear criarListaLinear(ListaLinear lista)
{
    NoSimples *noCabeca = (ListaLinear)malloc(sizeof(NoSimples));
    noCabeca->valor = 10;
    noCabeca->proximo = NULL;
    for(int i = 9; i >= 1; i --)
    {
        NoSimples *no = (ListaLinear)malloc(sizeof(NoSimples));
        no->valor = i;
        no->proximo = noCabeca;
        noCabeca = no;
    }
    lista = noCabeca;
    return lista;
}

int imprimirListaLinear(ListaLinear lista)
{
    NoSimples *ponteiro = lista;
    printf("Lista linear: ");
    while(ponteiro != NULL)
    {
        printf("%d-", ponteiro->valor);
        ponteiro = ponteiro->proximo;
    }
    printf("\n");
    return OK;
}

ListaLinear criarListaCircular(ListaLinear lista)
{
    NoSimples *ultimo = (ListaLinear)malloc(sizeof(NoSimples));
    ultimo->valor = 10;
    ultimo->proximo = ultimo;
    lista = ultimo;
    for(int i = 9; i >= 1; i --)
    {
        NoSimples *novo = (ListaLinear)malloc(sizeof(NoSimples));
        novo->valor = i;
        novo->proximo = ultimo->proximo;
        ultimo->proximo = novo;
    }
    return lista;
}

int imprimirListaCircular(ListaLinear lista)
{
    NoSimples *ponteiro = lista->proximo;
    printf("Lista: ");
    while(ponteiro != lista)
    {
        printf("%d-", ponteiro->valor);
        ponteiro = ponteiro->proximo;
    }
    printf("%d-\n", ponteiro->valor);
    return OK;
}

int verificarCiclo(ListaLinear lista)
{
    int resultado = 0;
    NoSimples *ponteiroRapido = lista;
    NoSimples *ponteiroLento = lista;

    while(ponteiroLento != NULL )
    {
        ponteiroRapido = ponteiroRapido->proximo;
        if(ponteiroRapido == NULL) break;
        ponteiroRapido = ponteiroRapido->proximo;
        if(ponteiroRapido == NULL) break;
        ponteiroLento = ponteiroLento->proximo;
        if(ponteiroRapido == ponteiroLento)
        {
            resultado = 1;
            break;
        }
    }
    return resultado;
}

int main()
{
    ListaLinear listaLinear;
    listaLinear = criarListaLinear(listaLinear);
    imprimirListaLinear(listaLinear);

    ListaLinear listaCircular;
    listaCircular = criarListaCircular(listaCircular);
    imprimirListaCircular(listaCircular);
    
    int resultadoLinear = 0, resultadoCircular = 0;
    resultadoLinear = verificarCiclo(listaLinear);
    resultadoCircular = verificarCiclo(listaCircular);

    printf("Lista circular tem ciclo: %d\nLista linear tem ciclo: %d\n", resultadoCircular, resultadoLinear);

    system("pause");
    return 0;
}

Problema do Mágico e as Cartas★

Este problema clássico consiste em determinar a ordem original de um baralho de 13 cartas (Ás a Rei) após um processo específico de distribuição e revelação. A solução utiliza uma lista circular simulando o baralho.

# include<stdlib.h>
# include<stdio.h>

# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0

typedef struct NoCarta 
{
    int indice;
    int valor;
    struct NoCarta *proximo;
} NoCarta;

typedef NoCarta *ListaCartas;

ListaCartas inicializarBaralho(ListaCartas baralho)
{
    NoCarta *ultima = (ListaCartas)malloc(sizeof(NoCarta));
    ultima->valor = 0;
    ultima->indice = 13;
    ultima->proximo = ultima;
    baralho = ultima;

    for(int i = 1; i <= 12; i ++)
    {
        NoCarta *nova = (ListaCartas)malloc(sizeof(NoCarta));
        nova->valor = 0;
        nova->indice = i;
        NoCarta *ponteiro = ultima->proximo;
        while(ponteiro->proximo != ultima)
        {
            ponteiro = ponteiro->proximo;
        }
        ponteiro->proximo = nova;
        nova->proximo = ultima;
    }
    return baralho;
}

int contarCartas(ListaCartas baralho)
{
    NoCarta *ponteiro = baralho->proximo;
    int contador = 0;
    while(ponteiro != baralho)
    {
        contador ++;
        ponteiro = ponteiro->proximo;
    }
    return ++contador;
}

int revelarOrdemCartas(ListaCartas baralho)
{
    int contador = 1, cartaRevelar = 1;
    NoCarta *ponteiro = baralho->proximo;
    while(ponteiro)
    {
        for(contador = 1; contador < cartaRevelar; contador ++)
        {
            ponteiro = ponteiro->proximo;
        }
        ponteiro->valor = cartaRevelar ++;
        printf("Carta na posição %d deve ser %d\n", ponteiro->indice, ponteiro->valor);

        NoCarta *remover = ponteiro, *anterior = baralho->proximo;
        while(anterior->proximo != remover)
        {
            anterior = anterior->proximo;
        }
        anterior->proximo = anterior->proximo->proximo;

        if(contarCartas(baralho) == 1) break;
        ponteiro = anterior->proximo;
        free(remover);
    }
    ponteiro = ponteiro->proximo;
    ponteiro->valor = cartaRevelar ++;
    printf("Carta na posição %d deve ser %d\n", ponteiro->indice, ponteiro->valor);
    return OK;
}

int main()
{
    ListaCartas baralho;
    baralho = inicializarBaralho(baralho);
    contarCartas(baralho);
    revelarOrdemCartas(baralho);
    system("pause");
    return 0;
}

Problema do Quadrado Latino

Um quadrado latino é uma matriz n×n onde cada número de 1 a n aparece exatamente uma vez em cada linha e coluna. A implementação utiliza listas circulares para gerar o padrão automaticamente.

# include<stdio.h>
# include<stdlib.h>

typedef struct NoMatriz
{
    int valor;
    struct NoMatriz *proximo;
} NoMatriz;

typedef NoMatriz *ListaMatriz;

ListaMatriz criarListaMatriz(ListaMatriz lista)
{
    NoMatriz *ultimo = (ListaMatriz)malloc(sizeof(NoMatriz));
    lista = ultimo;

    ultimo->valor = 9;
    ultimo->proximo = ultimo;

    for(int i = 1; i <= 8; i ++)
    {
        NoMatriz *novo = (ListaMatriz)malloc(sizeof(NoMatriz));
        novo->valor = i;
        NoMatriz *ponteiro = ultimo;
        while(ponteiro->proximo != ultimo)
        {
            ponteiro = ponteiro->proximo;
        }
        novo->proximo = ultimo;
        ponteiro->proximo = novo;
    }
    return lista;
}

void imprimirQuadradoLatino(ListaMatriz lista)
{
    printf("Quadrado Latino:\n");
    int repeticoes = 9;
    while(repeticoes --)
    {
        NoMatriz *ponteiro = lista->proximo;
        while(ponteiro != lista)
        {
            printf("%d ", ponteiro->valor);
            ponteiro = ponteiro->proximo;
        }
        printf("%d\n", ponteiro->valor);
        lista = lista->proximo;
    }
}

int main()
{
    ListaMatriz lista;
    lista = criarListaMatriz(lista);
    imprimirQuadradoLatino(lista);
    system("pause");
    return 0;
}

Lista Duplamente Circular

A lista duplamente circular possui ponteiros tanto para o próximo quanto para o nó anteriro, permitindo navegação em ambas as direções. O nó inicial e final estão conectados, formando um ciclo fechado.

# include<stdio.h>
# include<stdlib.h>

typedef struct NoDuplo
{
    int valor;
    struct NoDuplo *anterior;
    struct NoDuplo *proximo;
} NoDuplo;

typedef NoDuplo *ListaDupla;

ListaDupla inicializarListaDupla(ListaDupla lista)
{
    NoDuplo *noCabeca = (ListaDupla)malloc(sizeof(NoDuplo));
    lista = noCabeca;
    NoDuplo *noFinal = (ListaDupla)malloc(sizeof(NoDuplo));
    noCabeca->valor = 0;
    noFinal->valor = 0;

    noCabeca->proximo = noFinal;
    noCabeca->anterior = noFinal;
    noFinal->proximo = noCabeca;
    noFinal->anterior = noCabeca;

    return lista;
}

int obterTamanhoListaDupla(ListaDupla lista)
{
    int tamanho = 0;
    for(NoDuplo *ponteiro = lista; ponteiro != lista->anterior; ponteiro = ponteiro->proximo)
    {
        tamanho ++;
    }
    tamanho ++;
    return tamanho;
}

ListaDupla inserirNaPosicaoDupla(ListaDupla lista, int posicao, int elemento)
{
    if(posicao <= obterTamanhoListaDupla(lista) - 2 && posicao >= obterTamanhoListaDupla(lista)) 
    {
        printf("Tamanho da lista não corresponde à posição informada!\n");
        exit(1);
    }
    NoDuplo *ponteiro = lista;
    for(int k = 1; k < posicao; k ++)
    {
        ponteiro = ponteiro->proximo;
    }
    NoDuplo *novo = (ListaDupla)malloc(sizeof(NoDuplo));
    novo->valor = elemento;

    novo->proximo = ponteiro->proximo;
    novo->anterior = ponteiro;
    ponteiro->proximo->anterior = novo;
    ponteiro->proximo = novo;
    
    return lista;
}

int removerDaPosicaoDupla(ListaDupla lista, int posicao)
{
    if(posicao >= obterTamanhoListaDupla(lista) && posicao <= 1)
    {
        printf("Tamanho da lista não corresponde à posição!\n");
        exit(1);
    }
    NoDuplo *ponteiro = lista;
    for(int k = 1; k < posicao - 1; k ++)
    {
        ponteiro = ponteiro->proximo;
    }
    NoDuplo *remover = ponteiro->proximo;
    ponteiro->proximo->anterior = ponteiro;
    ponteiro->proximo = ponteiro->proximo->proximo;

    int elemento = remover->valor;
    printf("Elemento removido: %d\n", elemento);
    free(remover);
    return elemento;
}

void imprimirListaDupla(ListaDupla lista)
{
    NoDuplo *ponteiro = lista;
    printf("Lista:");
    while(ponteiro != lista->anterior)
    {
        printf("%d-", ponteiro->valor);
        ponteiro = ponteiro->proximo;
    }
    printf("%d\n", ponteiro->valor);
}

int main()
{
    ListaDupla lista;
    lista = inicializarListaDupla(lista);
    int tamanhoLista = obterTamanhoListaDupla(lista);
    printf("%d\n", tamanhoLista);

    printf("Inserção: Quantos elementos deseja inserir?\n");
    int quantidade = 0;
    scanf("%d", &quantidade);
    while(quantidade --)
    {
        int posicao, elemento;
        printf("Digite a posição e o valor do elemento:\n");
        scanf("%d%d", &posicao, &elemento);
        inserirNaPosicaoDupla(lista, posicao, elemento);
        imprimirListaDupla(lista);
    }
    printf("Remoção: Quantos elementos deseja remover?\n");
    scanf("%d", &quantidade);
    while(quantidade --)
    {
        int posicao;
        printf("Digite a posição do elemento a remover:\n");
        scanf("%d", &posicao);
        removerDaPosicaoDupla(lista, posicao);
        imprimirListaDupla(lista);
    }

    system("pause");
    return 0;
}

Tags: estruturas-de-dados listas-lineares lista-encadeada lista-circular Algoritmos

Publicado em 7-4 19:12

Doido Dev