Mota (2009) discute que uma lista é uma estrutura de dados linear. Uma lista ligada, também chamada de encadeada, é linear e dinâmica, é composta por nós que apontam para o próximo elemento da lista, com exceção do último, que não aponta para ninguém. Para compor uma lista encadeada, basta guardar seu primeiro elemento.
É importante que o programador saiba que a lista é uma implementação da uma estrutura de dados, em vez de um tipo de dado, ou seja, a lista é uma estrutura lógica com operações e comandos bem definidos e não é um tipo de dado. (TENENBAUM; LANGSAM; AUGENSTEIN; 1995)
A lista por vetores possui elementos que são organizados de forma linear em que esses elementos possuem um antecessor com a exceção do primeiro valor e o um sucessor com exceção do último valor. (SUAVÉ, 2007).
As listas utilizam o conceito de ponteiros e parâmetros, pois utilizam os endereços da memória para a organização das informações e também para incluí-los ou apagá-los.
Uma lista realiza uma alocação de memória na execução do programa visto que a lista organiza as informações na mesma hora em que o programa está em pleno funcionamento.
Essa alocação é conhecida como alocação dinâmica em que é muito utilizada para solucionar os problemas das estruturas de dados, como em listas, pilhas e filas. Para realizar uma alocação dinâmica é necessário utilizar ponteiros e as funções estão contidas na biblioteca “
p = (int * ) calloc (1, sizeof (int));
O ponteiro “p” que é do tipo int, aloca a memória do computador de tamanho “1” vezes a quantidade de bytes de int.
free(p);
O comando “free” libera a memória que foi alocada pelo ponteiro “p”.
A alocação dinâmica é necessária para começar o desenvolvimento das listas e dos próximos conceitos como listas encadeadas e duplamente encadeadas.
Para entender uma lista é possível que o programador realize uma abstração de como essa estrutura deverá funcionar. Esse tipo de visualização da lista pode ser feita em rascunhos, e com as anotações feitas elas poderão ser úteis em todo o processo de desenvolvimento.
Segundo Tenenbaum; Langsam; Augenstein; (1995, p.224) discutem que a lista pode ser entendida de forma que cada item na lista é chamado de nó e contem dois campos, um campo de informação e um campo de endereço seguinte. O campo de informação armazena o real elemento da lista e o campo do endereço está logo em seguida e possui o endereço do próximo nó na lista. Esse endereço, que é usado pra acessar determinado nó, é conhecido como ponteiro. A lista ligada inteira é acessada a partir de um ponteiro externo que aponta para o endereço que o está o primeiro nó na lista. O campo do próximo endereço do último nó na lista contém um valor especial, conhecido como null, que não é um endereço válido. Esse ponteiro nulo (ou null) é usado para indicar o final de uma lista.
#define
#define
struct no
{
int info;
struct no *prox;
}; typedef struct no lista;
A implementação de um nó (figura ao lado) de uma lista pode ser entendida como uma estrutura em que o campo “info” é reservado para o valor a ser manipulado e logo em seguida o campo “*prox” do tipo struct “no” em que sua posição aponta para o próximo nó da lista possui um ponteiro que pode apontar para outros nós da lista.
Uma lista que não possui nós é chamada de lista vazia ou lista nula com isso os seus ponteiros externos dessa lista serão nulos, a lista pode ser iniciada com valores null. (TENENBAUM; LANGSAM; AUGENSTEIN; 1995).
Lista * cria ( )
{
return NULL;
}
void main( )
{
lista *L;
L = cria( );
}
A implementação de criar uma lista começa com os valores NULL em que o ponteiro “L” do tipo da estrutura “lista” indica o ponteiro de início da lista.
O ponteiro “L” aponta para o ponteiro do tipo lista, em que esse ponteiro passa a ser um valor nulo. Essa implementação é necessária tendo como conceito que a lista para ser iniciada precisa da passagem de ponteiros com isso a função “cria” realiza a operação de iniciar a lista de valor nulo e com passagem de parâmetros
Com a declaração da lista e de suas instruções básicas a lista pode agora armazenar informações.
void inserir_inicio (lista * * L, int v)
{
lista *p = (lista * ) calloc (1, sizeof(lista));
p->info = v;
p->prox = * L;
*L = p;
}
A função de inserção recebe como parâmetros o ponteiro “L” que indica o início da lista e “v” a informação, a ser inserida.
A memória é alocada com o auxílio do ponteiro “p” que indica o novo nó a ser inserido. A informação recebida pelo parâmetro “v” é então atribuído ao campo do novo nó, este novo nó por sua vez tem seu ponteiro “prox” apontando para o início da lista. Para finalizar, o ponteiro “*L” é atualizado junto ao ponteiro auxiliar “p”.
Existe a possibilidade de inserir variáveis no fim da lista para auxiliar o programador na implementação de uma lista.
void inserir_fim (lista * *L, int v)
{
lista *p, *q;
p = (lista *) calloc (1,sizeof (lista));
p->info = v;
p->prox = NULL;
if ( * L == NULL)
*L = p;
else
{
q = *L;
while( q->prox != NULL)
q = q-> prox;
q-> prox = p;
}
}
A função “inserir_fim” possui dois parâmetros que ajudam na manipulação dos nós da lista, o primeiro parâmetro “L” aloca a memória, recebe a informação desejada e aponta para “NULL” que já caracteriza como o fim da lista.
A condição “if” dentro do método é necessária para verificar se a lista possui algum nó, caso o ponteiro “* L” estiver com o valor “NULL” então é interpretado que a lista não possui nenhum nó e com isso pode ser inserida normalmente.
Se a lista possui algum nó será necessário utilizar outra variável “*q” que auxiliará na busca dentro da lista para que o nó possa ser inserido no final. O ponteiro “*q” vai para o início da lista e em seguida um comando de repetição que vai realizar a busca entre os nós da lista, enquanto o próximo nó não for “NULL” ele irá passar de nó em nó até alcançar o último nó da lista. Se a lista possuir um nó ele colocará o próximo nó no final da lista normalmente.
Após a inserção dos elementos na lista, ela pode ser visualizada no compilador em que o programador e o usuário podem analisar as informações inseridas.
void imprime ( lista * L )
{
lista * p;
p = L;
while (p ! = NULL)
{
printf(“%d->”, p->info);
p = p-> prox;
}
Printf(“Null \n”);
getch( );
}
A função que visualiza os dados “imprime”, possui um parâmetro auxiliar em que esse parâmetro enquanto não encontrar o valor “NULL” na lista ele irá para cada nó da lista dentro do comando de repetição e mostrará nó que foi encontrado.
As listas simples lineares são um dos conceitos básicos sobre listas das estruturas de dados, as listas podem servir de grande auxilio para o programador em que podem ser implementadas para organizar diversas informações utilizando o mesmo método para inserir ou manipular dados aos programas ou algoritmos.
Nenhum comentário:
Postar um comentário