10 de jun de 2012

Lista com alocação dinâmica encadeada em C.

Continuando nosso estudo em Estrutura de Dados, vamos dar uma olhada em listas com alocação dinâmica encadeada, e vamos aproveitar para ver como podemos fazer uma inserção ordenada de elemento e só para dificultar um pouquinho mais as coisas vamos utilizar strings como tipo de dado.
Então vamos nessa...
Quando temos uma lista dinâmica encadeada não precisamos mais do vetor, pois agora alocaremos espaço para cada elemento da lista, que chamaremos de nó, e para que exista uma continuidade na lista precisaremos de um apontador para o próximo elemento da lista.

Nesse caso então nossa estrutura terá um vetor de caracteres que será nossa string e um ponteiro que terá o tipo do nó:

struct no{

    char info[20];

    struct no * prox;

};

e vamos renomear nossa estrutura:

typedef struct no *Lista;

Neste caso quando não existir nenhum elemento na lista a mesma terá o valor de "NULL" então para inicializarmos uma lista vamos atribuir a mesma este valor:

void inicializa_lista(Lista *l)

{

    *l = NULL;

}

Para verificarmos se a lista está vazia então, basta verificarmos se a mesma é nula e como alocaremos espaço para cada elemento nossa lista nunca ficara cheia então não é necessário verificar este estado :

int lista_vazia(Lista l)

{

    if(l == NULL)

        return 1;

    return 0;

}

Agora vamos partir para a inserção de elementos, neste caso o ideal seria uma inserção no inicio pois neste caso não seria necessário percorrer a lista, mais como coisa fácil é para os fracos vamos fazer uma  inserção ordenada...

No caso da inserção ordenada será necessário alocar memória para o novo elemento e então procurar a posição onde o elemento devera ser inserido e depois fazer como que o seu apontador aponte para o que deve ser seu próximo e também com que o apontador do elemento que deve ser seu anterior aponte para o elemento que está sendo inserido, nossa inserção então ficará assim:

int insere_elemento_ord(Lista *l, char elem[])

{

    Lista inserindo, anterior;



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

    if (inserindo == NULL)

        return 0;



    strcpy(inserindo->info, elem);



    if(lista_vazia(*l) || strcmp(elem, (*l)->info) <= 0)

    {

        inserindo->prox = *l;

        *l = inserindo;

        return 1;

    }



    anterior = *l;

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

        anterior = anterior->prox;



    inserindo->prox = anterior->prox;

    anterior->prox = inserindo;

    return 1;

}

Agora vamos remover um elemento, para remover o mais fácil também seria remover no inicio pelo mesmo motivo da inserção, mas vamos procurar um certo elemento para ser removido, assim é mais emocionante...

Para remover um elemento onde quer que ele esteja nós teremos que procura-lo na lista e quando o encontrarmos teremos que fazer o apontador de seu anterior apontar para o elemento apontado pelo que queremos remover e só então liberar a área de memória que estava alocada para aquele elemento, desta forma:

int remove_elemento_ord(Lista *l, char elem[])

{

    Lista anterior, remover;



    if(lista_vazia(*l))

        return 0;



    if(strcmp(elem, (*l)->info) == 0)

    {

        remover = *l;

        *l = remover->prox;

        free(remover);

        return 1;

    }



    anterior = *l;

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

        anterior = anterior->prox;



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

        return 0;



    remover = anterior->prox;

    anterior->prox = remover->prox;

    free(remover);

    return 1;

}

Por enquanto então é só e para quem ainda não viu a Lista com alocação estática e acesso sequencial em C. vale dar uma olhada! E não perca os próximos posts vamos aumentar o nosso nível... rs.

Como sempre dicas, duvidas e criticas construtivas são sempre bem vindas basta deixa-las ai nos comentários, até a próxima!

Continuação:
Lista utilizando nó-cabeçalho em C.
Lista com encadeamento circular em C.
Lista Duplamente Encadeada em C.
Pilha em C.

4 comentários:

  1. Minha função insere está similar a sua e nao esta ordenando ///

    int insere_ord(Lista *L, int x){

    Lista N, P; // Como se fosse um aux
    N = malloc(sizeof(Lista));

    if(N == NULL){
    return 0;
    }
    else{
    N->info= x; // Atribuir elemento ao compo INFO do novo no

    if(L == NULL || L < x){ // Casos em que a insercao e no inicio: o endereco da lista e atualizado

    N->prox = *L; // //Atribuir o endereco da lista ao compo PROX do novo no
    *L = N; // Atribuir o endereco do novo no ao endereco da lista ou seja apontar a lista para o novo no
    return 1;
    }
    else{ // Caminhar P ate o no que sera o anterior ao novo no

    P = *L; // Apontar o ponteiro aux P para o Primeiro da Lista

    while(P->prox != NULL && P->prox->info < x){ // Sucessor de P difenrete de NULL E campo info do sucessor de P < x

    P = P->prox; // P Apontar para o sucessor de P
    }
    N->prox = P->prox;
    P->prox = N;
    return 1;
    }
    }

    ResponderExcluir
  2. Me parece ser problema com ponteiros...
    tente implementar uma função "lista_vazia" igual à do post e no lugar de fazer
    "if(L == NULL || L < x)"
    faça:
    if(lista_vazia(*L) || (*L)->info < x)...

    ResponderExcluir
    Respostas
    1. Belezura cara! Só tive que mudar um detalhe do if que vc me mandou, tive que deixar assim:

      if(lista_vazia(*L) || x < (*L)->info)

      Agora está ordenando certinho! Muito Obrigado pela ajuda, mas queria que vc me ajudasse a entender porque na chamada da lista_vazia eu tive que passar o *L e não apenas o L como faço no main?
      Meu codigo está funcionando mas ainda estou com dificuldade de entendimento ...

      Excluir