25 de set de 2012

Lista com encadeamento circular em C.

O encadeamento circular em uma lista facilita as operações de inserção no fim e remoção no inicio, características de uma fila, sua implementação é parecida com Lista com alocação dinâmica encadeada, mais como o nome indica, agora a lista formará um ciclo de forma que o último elemento apontará para o primeiro.

A estrutura utilizada em uma lista circular é do mesmo tipo de uma lista dinâmica encadeada comum, então vamos usar um estrutura simples com dados em números inteiros:

struct no {
    int info;
    struct no * prox;
};

typedef struct no *Lista;

Quando um ponteiro deste tipo de lista está vazio ele deve valer "NULL", desta forma para podermos inicializar uma lista nova devemos fazer com que esta seja nula:

void inicializa_lista(Lista *l)
{
    *l = NULL;
}

Este tipo de lista facilita a inserção no fim da lista, e devemos lembrar também que o ponteiro da lista deve apontar para o último elemento da lista, desta forma a operação de inserção fica:

int insere_elemento_fim(Lista *l, int elem)
{
    Lista aux;

    aux = (Lista) malloc(sizeof(struct no));
    if (aux == NULL)
        return 0;

    aux->info = elem;
    if(lista_vazia(*l))
    {
        *l = aux;
        (*l)->prox = *l;
        return 1;
    }

    aux->prox = (*l)->prox;
    (*l)->prox = aux;
    *l = aux;
    return 1;
}

Veja que foi alocado espaço em memória para a o elemento que está sendo inserido, depois este novo elemento recebe seu valor, devemos verificar se a lista está vazia pois neste caso, como a lista contem um único elemento, ele deve apontar para si, e caso a lista não esteja vazia o elemento é inserido no fim, fazendo ele apontar para o primeiro da lista e fazendo o último da lista apontar para ele.
Lembre-se o ponteiro da lista deve sempre apontar para o último elemento então devemos mudar este ponteiro.

A operação de remoção no início da lista também fica facilitado por este tipo de lista:

int remove_elemento_inicio(Lista *l)
{
    Lista aux;

    if(lista_vazia(*l))
        return 0;

    aux = (*l)->prox;
    if(aux->prox == aux)
    {
        *l = NULL;
        free(aux);
        return 1;
    }

    (*l)->prox = aux->prox;
    free(aux);
    return 1;
}

Para remover um elemento devemos verificar se a lista está vazia, pois neste caso não será possível remover nenhum elemento, agora devemos verificar se a lista contém um único elemento, pois neste caso ao remove-lo a lista ficará vazia e deverá ser anulada, caso nenhum dos casos anteriores sejam verdadeiros devemos fazer com que o último elemento da lista aponte para o segundo elemento e liberar o espeço de memória ocupado por ele.

Estas são operações básicas deste tipo de lista, as operações de inserção no fim e remoção no início são facilitadas pelo tipo da lista, mas nada o impede de tentar inserir no inicio e remover no fim, qualquer dúvida,   dica ou critica construtiva serão muito bem vindas e respondidas, basta deixar ai nos comentários.

Até mais...

Veja também:
Lista com alocação estática e acesso sequencial em C.
Lista com alocação dinâmica encadeada em C.
Lista utilizando nó-cabeçalho em C.

Continua...
Lista Duplamente Encadeada em C.
Pilha em C.





Nenhum comentário:

Postar um comentário