9 de jun de 2012

Lista com alocação estática e acesso sequencial em C.

Vamos dar uma estudada em estruturas de dados!?
Então vamos começar pelas Lista com alocação Estática/Sequencial...


A estrutura de uma lista desse tipo contem um vetor cujo tamanho deve ser escolhido por você, e um inteiro que conterá a posição do primeiro elemento vazio da lista no vetor.
Desse jeito:

struct lista{

    int vet[MAX];

    int fim;

};

O valor de "MAX" deverá ser definido da forma "#define MAX número".
E podemos renomear essa estrutura:

typedef struct lista *Lista;

Para iniciar essa lista devemos alocar posição em memória para a estrutura e declarar que o primeiro elemento vazio da lista está na posição 0:


Lista inicializa_lista()

{

    Lista l;

    l = (Lista)malloc(sizeof(struct lista));

    if(l == NULL)
        return 0;

    l->fim = 0;

    return l;

}

Para verificar se a lista está vazia basta observar o primeiro elemento vazio da lista, se ele estiver na posição 0 ela está vazia caso não ela não está vazia, e da mesma forma verifica se ela esta cheia mais nesse caso verifica se o primeiro elemento vazio esta na posição "MAX" caso sim a lista está cheia, caso não ela está cheia.

int lista_vazia(Lista l)

{

    if(l->fim == 0)

        return 1;

    return 0;

}



int lista_cheia(Lista l)

{

    if(l->fim == MAX)

        return 1;

    return 0;

}

A melhor forma de inserir um elemento nesta lista é inseri-lo no fim, o que não o impede de tentar inserir um elemento no inicio ou em outra posição qualquer, mas lembre-se nestes casos você devera abrir espaço para o novo elemento movendo todos seus posteriores uma casa para a frente.

Inserindo no fim temos que verificar se lista foi inicializada ou se ela está cheia pois nestes casos não poderá ocorrer a inserção, então caso não entre em nenhum destes casos colocamos o elemento na primeira posição vazia da lista e incrementaremos a posição deste.


int insere_elemento_fim(Lista *l, int elem)

{

    if(*l == NULL || lista_cheia(*l))

        return 0;

    (*l)->vet[(*l)->fim] = elem;

    (*l)->fim++;

    return 1;

}

A melhor forma de se remover um elemento nesta lista também seria remover no fim pelo mesmo motivo da inserção, o deslocamento de elementos, mais vamos fazer uma remoção de um elemento em qualquer que seja sua posição para entendermos esse deslocamento.

Nessa remoção devemos observar se a lista foi inicializada ou se ela está vazia pois nestes casos não existem elementos para serem removidos, então caso não entre nos casos anteriores percorremos a lista procurando um elemento igual ao que queremos remover, assim que o encontrarmos devemos percorrer a lista a partir do elemento a ser removido movendo cada elemento uma posição para traz e no fim decrementamos a posição do primeiro elemento vazio da lista.


int remove_elemento(Lista *l, int elem)

{

   int i,j;

    if((*l) == NULL || (*l)->fim == 0)

        return 0;

    for(i=0; i<(*l)->fim; i++)

    {

        if((*l)->vet[i] == elem)

        {

            for(j=i; j < ((*l)->fim); j++)

                (*l)->vet[j] = (*l)->vet[j+1];

            (*l)->fl--;

            return 1;

        }

    }

    return 0;

}

Então é isso, qualquer duvida, dica ou critica construtiva pode ser colocada ai nos comentários, e fique de olho nos próximos posts onde abordaremos novos tipos de dados e novos tipos de estruturas também...

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

Nenhum comentário:

Postar um comentário