24 de set de 2012

Lista utilizando nó-cabeçalho em C.

Continuando os estudos sobre Estruturas de Dados, vamos dar uma olhada na utilização de um nó como cabeçalho em uma lista.
Vamos lá!?

A utilização de um nó como cabeçalho nos trás alguns benefícios como, por exemplo, a possibilidade de "guardar" alguma informação importante e também facilita as operações de inserção e remoção em uma lista ordenada.

O tipo do nó-cabeçalho não precisa necessariamente ser do mesmo tipo da lista, pode se criar um tipo próprio para o nó, dessa forma poderíamos "guardar" informações que nos sejam mais convenientes.

Vamos desenvolver um exemplo usando uma lista ordenada de números inteiros, e tendo o nó com o mesmo tipo da lista e para não desperdiçar este nó vamos colocar o tamanho da lista em seu campo "info".

Desta forma teremos a seguinte estrutura:

struct no{

    int info;

    struct no *prox;

};

typedef struct no *Lista;


O nó-cabeçalho deverá ser criado durante a inicialização da lista, desta forma deveremos alocar espaço em memória para ele, atribuir o valor 0 "zero" ao seu campo "info" e "NULL" ao seu campo "prox", pois neste momento a lista está vazia.

void inicializa_lista(Lista *l)

{

    Lista aux;

    aux = (Lista)malloc(sizeof(struct no));

    aux->info = 0;

    aux->prox = NULL;

    *l = aux;

}

As operações de inserção e remoção serão muito parecidas com as que usamos quando não utilizamos o nó-cabeçalho, a grande mudança é que agora não será mais necessário verificar se a lista está vazia ou se o primeiro elemento é menor ao elemento em questão, pois o primeiro nó será o cabeçalho.

int insere_elemento_ord(Lista l, int elem)

{

    Lista inserindo, anterior;



    inserindo = (Lista) malloc(sizeof(struct no));

    if (inserindo == NULL)

        return 0;



    inserindo->info = elem;



    anterior = l;

    while (anterior->prox != NULL && (anterior->prox)->info < elem)

        anterior = anterior->prox;



    inserindo->prox = anterior->prox;

    anterior->prox = inserindo;

    l->info++;

    return 1;

}



int remove_elemento_ord(Lista l, int elem)

{

    Lista anterior, remover;



    anterior = l;

    while(anterior->prox != NULL && (anterior->prox)->info < elem)

        anterior = anterior->prox;



    if(anterior->prox == NULL || (anterior->prox)->info < elem)

        return 0;



    remover = anterior->prox;

    anterior->prox = remover->prox;

    free(remover);

    l->info--;

    return 1;

}

Agora já temos as operações básicas, o resto é com você! Qualquer duvida, comentário ou crítica construtiva pode ser deixado ai nos comentários!

Para quem ainda não viu:
Lista com alocação dinâmica encadeada em C.
Lista com alocação estática e acesso sequencial em C.
vale a pena dar uma olhada!

Até a próxima!

Continuação:
Lista com encadeamento circular em C.



Nenhum comentário:

Postar um comentário