Embedded Files
A Estrutura de Dados Lista
Em uma estrutura de dados tipo lista, para cada novo elemento inserido na lista, alocamos um espaço de memória para armazená-lo. Dessa forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos armazenados na lista.
No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, pois a alocação é feita dinamicamente; portanto, não temos acesso direto aos elementos da lista, somente através do endereço de cada elemento.
Para percorrer todos os elementos da lista, devemos explicitamente guardar o seu encadeamento, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro com o endereço para o próximo elemento da lista. Por isso, os elementos da lista estão ligados uns aos outros, encadeados e por conta desta característica a lista é também conhecida como lista encadeada.
A Figura abaixo ilustra o arranjo da memória de uma estrutura de dados lista.
A estrutura de dados Lista consiste de uma sequência encadeada de elementos, em geral chamados de nós da lista. Um nó da lista é representado por uma estrutura que contém, conceitualmente, dois campos: a informação armazenada e o ponteiro para o próximo elemento da lista.
A lista inteira é representada por um ponteiro para o primeiro elemento (ou nó).
Do primeiro elemento, podemos alcançar o segundo, seguindo o encadeamento, e assim por diante. O último elemento da lista armazenada, não possui o ponteiro para o próximo elemento mas sim um ponteiro inválido, com valor NULL, e sinaliza, assim, que não existe próximo elemento na lista.
Características das Listas
As listas possuem características próprias que são as seguintes:
• As listas são implementadas através de variáveis dinâmicas que são criadas em tempo de execução usando portanto alocação dinâmica de memória;
• Os nós que compõem a lista devem ser agregados do tipo struct contendo, pelo menos, dois tipos de informação: um campo ou mais campos de tipo simples ou struct para abrigar as informações de cada elemento armazenado na lista e um outro campo do tipo ponteiro para abrigar o endereço do próximo elemento, ou nó, da lista;
• O acesso aos nós componentes da lista é sempre sequencial (para se acessar o 4o elemento, é necessário passar antes pelo 3o, para se acessar o 3o elemento, é necessário passar antes pelo 2o e assim sucessivamente);
• As estruturas de representação de Listas Ligadas devem obrigatoriamente suportar conceitos como ponteiros e alocação dinâmica;
• As Listas Ligadas podem ser simplesmente encadeadas (um único ponteiro por nó) ou duplamente encadeadas (dois ponteiros por nó).
As vantagens e desvantagens do uso das Listas
• Maior complexidade inerente à manipulação os elementos da lista devido ao uso de ponteiros; ( desvantagem )
• O fato de nem todas as linguagens de programação permitirem a construção de estruturas para a representação de Listas Ligadas (desvantagem);
• A flexibilidade de se trabalhar com listas de tamanhos indefinidos, que podem crescer e decrescer conforme a necessidade (vantagem);
• Maior facilidade para a realização de operações de inserção e remoção, que consistem basicamente no rearranjo de alguns ponteiros (vantagem).
Principais Operações das Listas
• Inserção de elementos em qualquer posição da lista (início ou final);
• Retirar elemento de qualquer posição lista;
• Impressão da lista;
• Busca de elementos na lista;
Exemplo de Implementação de uma Lista
Para exemplificar a implementação de listas encadeadas em C, segue abaixo um exemplo simples em que queremos armazenar valores inteiros em uma lista encadeada. O nó da lista pode então ser representado pela estrutura a seguir:
struct no {
int valor; // Valor inteiro
struct no* prox; // Ponteiro para o proximo elemento
};
typedef struct no lista;
Devemos notar que se trata de uma estrutura auto-referenciada, pois, além do campo para armazenar a informação (no caso, um número inteiro), há um campo que é um ponteiro para o próximo elemento da lista. Embora não seja essencial, é uma boa estratégia definir o tipo lista como sinônimo de struct lista. O tipo lista representa um nó da lista, e a estrutura da lista encadeada é representada pelo ponteiro para seu primeiro elemento (tipo lista*).
Função de criação
A função que cria uma lista vazia deve ter como valor de retorno uma lista sem nenhum elemento. Como a lista é representada pelo ponteiro para o primeiro elemento, uma lista vazia é representada pelo ponteiro NULL, pois não existem elementos na lista. A função tem como valor de retorno a lista vazia inicializada, isto é, o valor de retorno é NULL.
/* função de criação de lista: retorna lista vazia*/
lista* cria(void) {
return NULL;
}
Função de inserção
Uma vez criada a lista vazia, podemos inserir nela novos elementos. Para cada elemento inserido, devemos alocar dinamicamente a memória necessária para armazenar o elemento e encadeá-lo na lista existente. A função de inserção mais simples insere o novo elemento no início da lista, porém não existe obrigatoriedade na disciplina de acesso aos dados, isto é, a inserção pode ser realizada no início, no final, no meio da lista, etc.
Uma possível implementação dessa função é mostrada a seguir. Devemos notar que o ponteiro que representa a lista deve ter seu valor atualizado, pois a lista deve passar a ser representada pelo ponteiro para o novo primeiro elemento. Por essa razão, a função de inserção recebe como parâmetros de entrada a lista na qual será inserido o novo elemento e a informação do novo elemento e tem como valor de retorno a nova lista, representada pelo ponteiro para o novo elemento.
/* função que insere elemento no início da lista*/
lista* insere(lista* l, int i)
{
lista* novo = (lista*) malloc(sizeof(lista));
novo->valor = i;
novo->prox = l;
return novo;
}
Essa função aloca dinamicamente o espaço para armazenar o novo nó da lista, guarda informação no novo nó e faz ele apontar (isto é, tenha como próximo elemento) para o elemento que era o primeiro da lista. A função então tem como valor de retorno a nova lista, representada pelo ponteiro para o novo primeiro elemento.
A Figura abaixo ilustra a operação de inserção de um novo elemento no início da lista.
Função que verifica se a lista está vazia
Pode ser útil implementar uma função para verificar se uma lista está vazia ou não. A função recebe a lista e retorna 1 se estiver vazia ou 0 se não estiver vazia. Como sabemos, uma lista está vazia se seu valor é NULL. Uma implementação dessa função é mostrada a seguir:
/* função vazia: retorno 1 se vazia ou 0 se não vazia*/
int lista_vazia(lista* l) {
if(l == NULL)
return 1; // Retorna 1 que significa verdadeiro, a lista está vazia
else
return 0; // Retorna 0 que significa falso, a lista não está vazia
}
Função que percorre os elementos da lista
Para ilustrar a implementação de uma função que percorre todos os elementos da lista, vamos considerar a criação de uma função que imprime os valores dos elementos armazenados em uma lista. Uma possível implementação dessa função é mostrada a seguir.
/* função que imprime elementos da lista*/
lista* imprime(lista* l) {
if(!lista_vazia(l)) {
lista* aux;
for(aux=l; aux != NULL; aux=aux->prox)
printf("valor = %d\n",aux->valor);
}
else
printf("\nTentou imprimir uma lista vazia");
}
Função de busca
Uma outra função útil consiste em verificar se um determinado elemento está presente na lista. A função recebe a informação referente ao elemento que queremos buscar e fornece como valor de retorno o ponteiro do nó da lista que representa o elemento. Caso o elemento não seja encontrado na lista, o valor retornado é NULL.
/* função que busca um elemento na lista*/
lista* busca(lista* l, int busca) {
lista* aux;
if(!lista_vazia(l)) {
for(aux=l;aux!=NULL;aux=aux->prox) {
if(aux->valor == busca) {
printf("Valor encontrado.\n");
return aux;
}
}
return NULL;
}
else {
printf("\nTentou buscar de uma lista vazia");
return NULL;
}
Função que retira um elemento da lista
Devemos agora considerar a implementação de uma função que permita retirar um elemento da lista. A função tem como parâmetros de entrada a lista e o valor do elemento que desejamos retirar, e deve atualizar o valor da lista, pois, se o elemento removido for o primeiro da lista, o valor da lista deve ser atualizado.
A função para retirar um elemento da lista é mais complexa.
Se descobrirmos que o elemento a ser retirado é o primeiro da lista, devemos fazer o novo valor da lista passar a ser o ponteiro para o segundo elemento, e então podemos liberar o espaço alocado para o elemento que queremos retirar.
Se o elemento a ser removido estiver no meio da lista, devemos fazer o elemento anterior a ele passar a apontar para o seguinte, e então podemos liberar aquele que queremos retirar.
Se o elemento a ser removido for o ultimo elemento da lista, devemos fazer o elemento anterior a ele apontar para NULL, tornando-se assim o ultimo elemento da lista.
Devemos notar que, no segundo caso, precisamos do ponteiro para o elemento anterior a fim de acertar o encadeamento da lista. As Figuras abaixo ilustram as operações de remoção.
Uma possível implementação da função para retirar um elemento da lista é mostrada a seguir. Inicialmente busca-se o elemento que se deseja retirar, mas guarda-se uma referência para o elemento anterior. De modo análogo à função insere, optamos por implementar a função retira tendo como valor de retorno o eventual novo valor da lista.
lista* retira(lista* l, int valor) {
lista* ant = NULL; /* ponteiro para elemento anterior */
lista* aux = l; /* ponteiro para percorrer a lista */
if(!lista_vazia(l)) {
/* procura elemento na lista, guardando anterior */
while(aux!= NULL && aux->valor != valor) {
ant = aux;
aux = aux->prox;
}
/* se aux for NULL significa que chegou ao final da lista e nao encontrou o elemento. Logo retorna a lista inalterada. */
if(aux == NULL)
return l;
/* se chegou aqui é porque aux nao é NULL e contem o elemento a ser excluido da lista. */
if(ant == NULL)
/* O elemento anterior é null porque o elemento excluido é o primeiro e entao agora o primeiro elemento da lista é o elemento apontado por aux.
*/
l = aux->prox;
else
/* O elemento anterior nao é null porque o elemento aux a ser excluido nao é o primeiro. Portanto o elemento anterior deve
apontar para o elemento apontado por aux */
ant->prox = aux->prox;
/* libera a memoria utilizada pelo elemento aux que foi excluido */
free(aux);
/* Retorna a lista atualizada */
return l;
}
else {
printf("\nTentou remover de uma lista vazia");
/* Retorna a lista inalterada */
return l;
}
}
Implementação de Lista em C – Inserção pelo Final da Lista
A implementação de Listas Dinâmicas também pode ser realizada com a inserção pelo final da Lista. No programa abaixo, não é utilizado a função typedef.
São declarados três ponteiros: aux (responsável pela criação e alocação de novos nós), início (responsável por guardar o início do encadeamento) e final (responsável por guardar o último elemento encadeado do encadeamento).
Todas as funções são semelhantes as apresentadas anteriormente, com exceção da função de inserção ( insere final() ).
Segue abaixo o programa completo:
#include <stdio.h>
#include <conio.h>
#include <cstdlib>
struct Registro {
int valor;
struct Registro *prox;
};
struct Registro *aux, *inicio = NULL, *final = NULL;
/*função responsável por criar a lista*/
struct Registro* cria(void) {
return NULL;
}
/* função com tipo de retorno ponteiro para estrutura, realizando inserção pelo final*/
struct Registro* insere_final() {
int x;
printf("Entre com um numero inteiro: ");
scanf("%i",&x);
aux = (struct Registro*) malloc (sizeof(struct Registro));
aux->valor = x;
aux -> prox = (struct Registro *) NULL;
if(inicio == NULL)
inicio = final = aux; // Não existe elemento anterior e portanto há apenas um elemento na lista. Assim inicio e final são o mesmo elemento da lista.
else {
final -> prox = aux; // O elemento incluido se torna o ultimo elemento da lista. Assim o prox aponta para o elemento incluido.
final = aux;
}
return inicio;
}
/* função que verifica o estado da lista: retorno 1 se vazia ou 0 se não vazia*/
int lista_vazia(struct Registro *lista) {
if(lista == NULL)
return 1;
else
return 0;
}
/* função responsável por imprimir o conteúdo da lista */
void visualiza_lista_final(struct Registro *lista) {
/* verifica se a lista está vazia*/
if(!lista_vazia(lista)) {
aux = lista;
while(aux != (struct Registro *) NULL) { // Enquando o aux for diferente de NULL. Note que aux é atualizado com o ponteiro para o proximo elemento.
printf("Valor da Lista: %i\n", aux->valor);
aux = aux -> prox; // Atualiza aux com o ponteiro para o proximo elemento.
}
}
/* indica que a lista está vazia*/
else
printf("\nTentou imprimir uma lista vazia!");
getch();
}
/* função que busca um elemento na lista*/
struct Registro* busca(struct Registro* lista, int busca) {
bool achou = 0; // Assume que o elemento nao existe na lista, inicializando o flag com 0
if(!lista_vazia(lista)) { // Se a lista nao estiver vazia inicia a busca
for(aux=lista;aux!=NULL;aux=aux->prox) { // Percorre a lista a partir do primeiro elemento ate que o proximo elemento seja NULL
if(aux->valor == busca) { // Se o campo valor do elemento for igual a busca entao atualiza o flag para 1
achou = 1;
}
}
if(!achou) // Ao final da busca, verifica se achou e caso tenha encontrado imprime mensagem
printf("Valor nao encontrado.\n");
}
else {
printf("\nTentou buscar de uma lista vazia"); // Se a lista nao exister preenchida exibe mensagem informando lista vazia
}
getch();
return NULL;
}
/* função para excluir registros da lista*/
struct Registro* excluir(struct Registro *lista, int valor) {
/* ponteiro para elemento anterior */
struct Registro *ant = NULL;
/* ponteiro para percorrer a lista */
aux = lista;
if(!lista_vazia(lista)) {
/* procura elemento na lista, guardando anterior */
while(aux!= NULL && aux->valor != valor) {
ant = aux;
aux = aux->prox;
}
/* verifica se achou o elemento */
if(aux == NULL) {
printf("\nNao foi possivel a exclusao. Elemento nao encontrado!");
getche();
return lista;
}
/* retira elemento */
if(ant == NULL)
lista = aux->prox; // Se o elemento excluido for o primeiro elemento da lista entao o inicio da lista aponta para o elemento seguinte
else
ant->prox = aux->prox; // Se o elemento excluido nao for o primeiro, faz o elemento anterior apontar para o proximo elemento da lista
/* Libera a memoria alocada para o elemento excluido. Neste momento o elemento não faz mais parte da lista e pode ser exlcuido. */
free(aux);
printf("Elemento removido com sucesso!\n");
getche();
/* Retorna a lista atualizada, sem o elemento que foi excluido */
return lista;
}
else {
printf("\nTentou remover de uma lista vazia");
getche();
return lista;
}
}
/* Programa Principal - Funcao Main */
main() {
/* Variaveis para opcao do menu, para o elemento a ser excluido e para o elemento a ser localizado pela busca */
int op, vremover, vbuscar;
/* Variavel para apontar para o primeiro elemento da lista */
struct Registro *lista;
/* Cria a lista inicialmente vazia */
lista = cria();
/* Enquanto o usuario nao escolher a opcao 5 para sair do programa, as opções escolhidas sao executadas */
while(op != 5) {
/* Imprime o menu principal do programa */
system("cls");
printf("\nPrograma Para Manipulacao de Listas Ligadas");
printf("\n1 - Inserir no Final da Lista");
printf("\n2 - Visualizar Lista");
printf("\n3 - Buscar Elemento na Lista");
printf("\n4 - Excluir Elemento");
printf("\n5 - Sair do Programa");
/* Le a opcao do usuario */
printf("\nEntre com a Opcao Desejada: ");
scanf("%i",&op);
/* Conforme a opção escolhida execuca a funcao solicitada que pode ser para inserir, listar, buscar ou remover um elemento da lista */
switch(op) {
case 1:
lista = insere_final();
break;
case 2:
visualiza_lista_final(lista);
break;
case 3:
printf("Entre com o valor que se deseja buscar: ");
scanf("%d",&vbuscar);
busca(lista,vbuscar);
break;
case 4:
printf("Entre com o valor que deseja remover: ");
scanf("%i",&vremover);
lista = excluir(lista, vremover);
break;
case 5:
exit(1);
}
}
}
Page updated
Google Sites
Report abuse