Sistemas Operacional

LISTAS ENCADEADAS

Listas são estruturas de dados que contém um conjunto de blocos de memória que armazenam dados. Esses blocos são encadeados (ligados) por ponteiros, formando uma espécie de “corrente”, onde as peças dessa corrente estão ligadas umas as outras. O encadeamento de listas pode ser de dois tipos: simplesmente encadeada e duplamente encadeada.

LISTAS SIMPLISMENTE ENCADEADAS

Listas simplesmente encadeadas possuem um único ponteiro, que apontará para o próximo elemento da lista.

Código:

struct lista {

int info;

struct lista* prox;

}

typedef struct lista Lista;

A função que cria uma lista simplesmente encadeada retornará um NULL do tipo da lista, ou seja, uma lista totalmente vazia:

Código:

Lista* lst_cria (void)

{

return NULL;

}

A função de inserção insere novos elementos no início da lista encadeada, pois esta é a maneira mais simples de se inserir elementos numa lista, seja ela simplesmente ou duplamente encadeada. É importante lembrar que uma lista é representada pelo ponteiro para o primeiro elemento dela todos os demais elementos estão encadeados um a um sucessivamente, a partir do primeiro. Ou seja, para se acessar qualquer elemento da lista, basta fornecer o ponteiro para o primeiro elemento e ir percorrendo elemento a elemento até se chegar no elemento desejado.

Código:

Lista* lst_insere (Lista* l, int i)

{

Lista* novo = (Lista*) malloc (sizeof(Lista));

novo->info = i;

novo->prox = l;

return novo;

}

Observe que o novo elemento é encadeado aos demais já existentes na lista (caso ela já tenha outros elementos) e a nova lista é representada pelo novo elemento inserido, que passa a ser o 1º da lista.

Função que imprime na tela os elementos da lista:

Código:

void lst_imprime (Lista* l)

{

Lista*p;

for (p = l; p != NULL; p = p->prox)

{

printf (“info = %d\n”, p->info);

}

}

Função para verificar se a lista está vazia:

Código:

int lst_vazia (Lista* l)

{

return (l == NULL);

}

Para criarmos uma função que busque um determinado elemento, vamos implementá-la de forma a retornar um ponteiro para o elemento buscado. Como sempre, você pode alterar a maneira de retorno de quaisquer das funções aqui mostradas, de forma a se enquadrar melhor ao seu caso.

Código:

Lista* lst_retira (Lista* l, int v)

{

Lista* ant = NULL;

Lista* p = l;

while (p != NULL && p->info != v)

{

ant = p;

p = p->prox;

}

if (p == NULL)

return l;

if (ant == NULL)

{

l = p->prox;

}

else

{

ant->prox = p->prox;

}

free (p);

return l;

}

Função para liberar os elementos da lista:

Código:

void lst_libera (Libera* l)

{

Lista* p= l;