Artigo ED-02: Listas Lineares Sequenciais (Parte I)

Por Brunno Augusto
No artigo anterior introduzimos o estudo das estruturas de dados, dando algumas definições básicas. A partir de agora estudaremos uma a uma as estruturas citadas. Iniciemos o nosso estudo com as listas lineares sequenciais.
Uma lista linear é sequencial se, para cada nó da lista, seu sucessor está armazenado na posição seguinte da memória. A principal forma de se implementar uma lista linear sequencial é por meio da utilização de arrays (vetores). Um vetor é uma estrutura de armazenamento caracterizada por um nome, um tipo de dado que é capaz de armazenar e um tamanho, número de dados do mesmo tipo que pode armazenar. Antes de prosseguirmos neste artigo, duas observações devem ser feitas: Primeiro - A partir de agora far-se-á necessário implementarmos os algoritmos para mostrarmos o uso das estruturas de dados. Para tornar as soluções o mais genéricas possíveis, os algoritmos serão implementados em português estruturado e não em uma linguagem qualquer em particular. Segundo - Assumirei aqui que você leitor domina as noções mais elementares sobre algoritmos tais como declaração e uso de variáveis, estruturas de decisão e de repetição, entre outras. Feitas as considerações necessárias, prossigamos. A sintaxe de declaração de um vetor é dada como segue: declare nome_vetor : vetor [1..n] de tipo_vetor. Usaremos como padrão que palavras reservadas serão escritas em negrito. Vejamos agora os algoritmos que nos permitem realizar as operações mais básicas em uma lista linear sequencial. Nesse artigo implementaremos algoritmos de busca e nos demais os de inserção e exclusão.
Consideremos antes de mais nada que as listas podem se encontrar ordenadas ou desordenadas. É importante considerar isso, já que teremos mais de um algoritmo de busca e o emprego de um ou de outro, dependerá do fato de a lista está ou não ordenada.
Para qualquer tipo de lista temos o algoritmo de busca sequencial. Esse algoritmo atua da seguinte forma: ele sai em busca de um elemento vasculhando a lista do inicio até o final. Se chegar ao final e o último elemento não for o procurado, então ele não existe na lista. Percebemos que no pior caso, ou seja, quando o elemento a ser procurado é o último faremos n comparações, sendo n o número de elementos da lista. Por isso, dizemos que o algoritmo de busca sequencial é de ordem n O(n). Implementemos então o algoritmo de busca sequencial:

algoritmo busca_seq
declare
lista : vetor [1..n] de literal
chave : literal
i : numerico
achou : logico
inicio
leia chave
i <- 1 achou <- falso
enquanto (não achou) e (i<=n) faça
se lista[i] = chave então
escreva i
achou <- verdadeiro
senão
i <- i+1
fim se
fim enquanto
se não achou então
escreva "não encontrado"
fim se
fim algoritmo



Façamos uma breve análise do algoritmo acima. Nós definimos duas condições de parada, ou quando ele encontrar o elemento que busca, ou quando chegar ao fim da lista. Caso ele chegue ao final da lista e não tenha encontrado o elemento que busca, é exibida uma mensagem, se pelo contrário, for encontrado o elemento, então é exibida a sua posição na lista. É um algoritmo simples de se entender e de se implementar, podendo ser utilizado em qualquer tipo de lista. Quando porém a lista se apresenta ordenada, e nós queremos executar uma busca mais eficiente, nós podemos utilizar o algoritmo de busca binária. Vejamos no que consiste a busca binária: Estando a lista ordenada, temos que o primeiro elemento é o menor e que o último é o maior (considerando uma ordenação crescente que é a mais comum), desse modo, quando buscamos por um elemento podemos executar os seguintes passos. Procuramos o elemento médio da lista; Comparamos o valor procurado com esse e três situações podem ocorrer. O elemento procurado ser ele, desse modo encerra-se a execução do programa, o elemento procurado ser maior que ele, desse modo só no interessa procurar na metade do meio para o final da lista, ou o elemento ser menor que ele, desse modo, só nos interessa procurarmos na metade do meio para o inicio da lista. Uma vez em alguma dessas metades, repetimos os procedimentos anteriores, achando o meio da lista, comparando o elemento procurado com esse, e buscando em alguma das metades desse pedaço de lista. Para mostrarmos o que descrevemos acima de modo mais concreto, implementemos o algoritmo de busca binária, útil apenas quando a lista se encontra ordenada.



algoritmo buca_bin
declare
lista : vetor [1..n] de literal
chave : literal
ini, meio, fin : numerico
achou : lógico
inicio
leia chave
ini <- 1 fin <- n achou <- falso
enquanto (não achou) e (ini<=fin) faça
meio <- (ini+fin)/2 se chave = lista[meio]então
escreva meio
achou <- verdadeiro
senão
se chave < lista[meio] então
fin <- (meio-1)
senão
ini <- (meio+1) fim se
fim se
fim enquanto
se não achou então
escreva "elemento não encontrado"
fim se
fim algoritmo

Com base no algoritmo de busca binária, temos que a sua ordem é de log2N com N = tamanho da lista, ou seja, a busca binária no pior caso realizará log2N buscas. Para mais claramente vermos a eficiência da busca binária, consideremos uma lista com 10000 registros. A busca binária realizaria no pior caso 14 comparações enquanto que a busca sequencial realizaria em média 5000 comparações.
Bom, por hora ficamos aqui, até o próximo artigo então.