quinta-feira, novembro 08, 2007

Lista Ligadas - Parte 4

Neste post vamos examinar as Listas Lineares, com destaque para as Pilhas e Filas.
Listas Lineares

Definição

Listas Lineares são listas que apresentam somente uma relação de adjacência. Em uma lista linear existe um primeiro elemento e um último elemento, todos os demais elementos possuem um elemento anterior e um elemento seguinte.

Operações Básicas

As operações básicas que vamos examinar são:
  • Inserir um elemento em uma lista
  • Remover um elemento de uma lista
  • Percorrer os elementos de uma lista
Listas Lineares Especializadas

Existem dois tipos especializados de listas lineares que são encontrados com freqüência:
  • Uma pilha é uma lista onde todas as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido é sempre o que foi inserido mais recentemente. Por isso, as pilhas são à vezes chamadas de LIFO (last in first out, último a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma pilha de caixas:

  • Uma fila é uma lista onde todas as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra ponta. Desta forma, o item removido é sempre o que foi inserido a mais tempo. Por isso, as filas são à vezes chamadas de FIFO (first in first out, primeiro a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma fila de pessoas:

Alocação Seqüencial

A maneira mais simples e óbvia de implementar uma lista é mantendo os elementos seqüencialmente na memória. Podemos fazer isto tanto usando um vetor alocado estaticamente como uma área alocada dinamicamente.

Um exemplo de alocação sequencial estática para uma lista genérica:
int lista [10];  // área para guardar a lista
// lista pode ter até 10 elementos
int tamlista; // número de elementos atualmente na lista

// inicia lista
void IniciaLista ()
{
tamlista = 0; // lista está vazia
}

// Insere um elemento na lista na posição pos
// (as posições são numeradas de 0 a tamlista-1)
int Insere (int pos, int elemento)
{
int i;

if (tamlista == (sizeof(lista)/sizeof(int)))
return FALSE; // lista cheia
if ((pos <> tamlista))
return FALSE; // posicao invalida
if (pos == tamlista)
{
// inserir no final
lista[tamlista++] = elemento;
}
else
{
// inserção no meio, mover os elementos seguintes
for (i = tamlista; i > pos; i--)
lista [i] = lista [i-1];
lista[pos] = elemento;
tamlista++;
}
return TRUE;
}
A rotina de inserção acima mostra uma desvantagem da alocação sequencial: é preciso mover os elementos na memória quando é feita uma inserção ou remoção.

Obs: no caso de filas e pilhas, onde as inserções e remoções são feitas nos extremos, é possível evitar a movimentação dos elementos.

Por outro lado, o acesso aleatório as elementos é muito simples. A rotina abaixo calcula a soma de todos os elementos da lista:
int Soma ()
{
int i, total;
for (i = total = 0; i < tamlista; i++)
total += lista[i];
return total;
}

No próximo post vamos examinar as Listas Ligadas Simples.

2 comentários:

breno augusto disse...

Olá Daniel, no código:
...
if ((pos <> tamlista))
return FALSE; // posicao invalida
...
O sinal de "diferente" na linguagem C não seria "!=" não?

Se bem que o diferente não poderia entrar ali visto que deve testar um intervalo...

Se eu estiver enganado, me desculpe...

No mais, os seus artigos são excelentes...

Grande abraço

Daniel Quadros disse...

Bruno,

Devia ser (pos > tamlista). Ainda não achei uma forma fácil de colocar código no blog, às vezes o editor do blogger se atrapalha com < e >, pensando que são marcas de tags HTML.