Lista Linear

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Algoritmo e Estruturas de dados
Engenharia Elétrica
Lista Linear: Definição
Dentre as estruturas de dados não primitivas, as listas lineares são as de manipulação mais simples.
Em sentido geral, uma lista é uma relação (ou rol) de elementos.
Uma lista de compras, por exemplo é uma enumeração de elementos a serem adquiridos.
Note-se que essa lista poderia conter apenas o nome do item, mas poderia também especificar a quantidade a ser comprada....
nesse caso, a lista possuiria pares como elementos, cada um contendo um nome de item e a quantidade correspondente.
Listas lineares, portanto são estruturas que permitem representar uma coleção de dados de forma a preservar a relação de ordem entre eles.
É uma coleção L:[a1, a2, ..., an], n≥0, cuja propriedade estrutural baseia-se apenas na posição relativa dos elementos, que são dispostos linearmente.
 Se n = 0, a lista L é vazia.
 Caso contrário:
a1 é o primeiro elemento de L;
an é o último elemento de L;
ak, 1<k<n, é precedido pelo elemento ak-1 e seguido por ak+1 em L
Lista Linear: Definição
Estrutura interna é abstraída
x1
...
x2
xn
Último - 1 = n
MaxTam
Xn - 1
São os itens de minha TAD
Lista Linear: Definição
Lista Linear: Operações
Criar uma lista vazia 
 Verificar se uma lista está vazia 
 Obter o tamanho da lista 
Obter/modificar o valor do elemento de uma determinada posição na lista 
 Obter a posição de elemento cujo valor é dado 
Inserir um novo elemento após (ou antes) de uma determinada posição na lista 
Remover um elemento de uma determinada posição na lista 
Exibir os elementos de uma lista 
Lista Linear: Classificação
Listas lineares gerais:
 – A inclusão e remoção de elementos pode ser realizada em qualquer posição da lista. Essas listas não apresentam nenhuma restrição de acesso 
Casos particulares de listas:
 – Pilha: lista linear onde todas as inserções e remoções são realizadas em um único extremo da lista. Conhecidas também como listas LIFO (Last-In/First-Out)
 
 – Fila: lista linear onde todas as inserções são realizadas num determinado extremo da lista e as
remoções, no outro extremo. Conhecidas também como FIFO (First-In/First-Out)
Lista Linear: Implementação
Várias estruturas de dados podem ser usadas para representar listas lineares, cada uma com vantagens e desvantagens particulares.
As duas representações mais utilizadas são as implementações por meio de arranjos/vetor e de apontadores.
0
1
2
3
4
5
Vetores possuem um espaço 
limitado para armazenamento de dados.
Necessitamos definir um espaço grande o suficiente para a lista.
Necessitamos de um indicador de qual elemento do vetor é o atual último elemento da lista.
Lista
cheia
Lista
vazia
55
4
12
89
24
Lista Linear: Implementação por vetor
Lista Linear: Implementação por vetor
Ex. 1: Considere uma lista L de n elementos.
Lista Linear: Modelagem da Lista
Aspecto Estrutural:
Necessitamos de um vetor para armazenar as informações.
Necessitamos de um indicador da posição atual do último elemento da lista.
Necessitamos de uma constante que nos diga quando a lista está cheia e duas outras para codificar erros.
Pseudo-código:
	
tipo Lista = registro
	dados:vetor de [1..100] de inteiro
	ultimo:inteiro
fimregistro
Lista Linear: Modelagem da Lista
Aspecto Funcional:
Colocar e retirar dados da lista.
Testar se a lista está vazia ou cheia e outros testes.
Inicializa-la e garantir a ordem dos elementos.
Lista Linear: Algoritmo InicializaLista
procedimento inicializaLista()
inicio
		alista.ultimo  0
fimprocedimento
	Observação: Este e os próximos algoritmos pressupõem que foi definida uma variável global tipo Lista denominada aLista.
Lista Linear: Algoritmo ListaCheia
FUNCAO listaCheia():logico
	inicio
		SE (aLista.ultimo = 100) ENTAO
				RETORNE(Verdadeiro)
		SENAO
				RETORNE(Falso)
		fimse
	fimfuncao
Lista Linear: Algoritmo ListaVazia
FUNCAO listaVazia():logico
	inicio
		SE (aLista.ultimo = 0) ENTAO
				RETORNE(Verdadeiro)
		SENAO
				RETORNE(Falso)
		FIMSE
	fimFUNCAO
Lista Linear: Algoritmo Adiciona
Procedimento:
Testamos se há espaço.
Incrementamos o último.
Adicionamos o novo dado.
Parâmetros:
O dado a ser inserido.
Lista (global).
4
5
20
55
4
12
89
24
Lista Linear: Algoritmo Adiciona
Constantes
			ErroListaCheia 	= -1;
		 	ErroListaVazia 	= -2;
		 	ErroPosição	 	= -3;
FUNCAO adiciona(dado:inteiro):inteiro
	inicio
		SE (listaCheia()) ENTAO
				RETORNE(-1)
		SENAO
				aLista.ultimo  aLista.ultimo + 1
				aLista.dados[aLista.ultimo]  dado
				RETORNE(1)
		FIMSE
	fimfuncao
Lista Linear: Algoritmo Retira
Procedimento:
Testamos se há elementos.
Decrementamos o último.
Devolvemos o último elemento.
Parâmetros:
Lista (global).
Lista Linear: Algoritmo Retira
FUNCAO retira():INTEIRO
	inicio
		SE (listaVazia()) ENTAO
				RETORNE(-2)
		SENAO
				aLista.ultimo  aLista.ultimo - 1
				RETORNE(aLista.dados[aLista.ultimo + 1])
		FIMSE
	fimFUNCAO
	
Lista Linear: Algoritmo AdicionaNaPosicao
Procedimento:
Testamos se há espaço e se a posição existe.
Incrementamos o último.
Empurramos tudo para trás a partir da posição.
Adicionamos o novo dado na posição dada.
Parâmetros:
O dado a ser inserido.
A posição onde inserir.
Lista (global).
Lista Linear: Algoritmo AdicionaNaPosicao
FUNCAO adicionaNaPosicao(dado, destino:INTEIRO):INTEIRO
	var
	 posicao:inteiro
	inicio
	 SE (listaCheia()) ENTAO
	 RETORNE(-1)
	 SENAO
		SE (destino > aLista.ultimo + 1) ENTAO
		 RETORNE(-3)
		SENAO
	 	 aLista.ultimo  aLista.ultimo + 1
	 	 posicao  aLista.ultimo
	 	 ENQUANTO (posicao > destino) FACA 
	 aLista.dados[posicao]  aLista.dados[posicao - 1]
		 posicao  posicao - 1
		 FIMENQUANTO
	 	 aLista.dados[destino]  dado
	 RETORNE(1)
 	 	FIMSE
	 FIMSE
	FIMFUNCAO
Lista Linear: Algoritmo RetiraDaPosicao
Procedimento:
Testamos se há elementos e se a posição existe.
Decrementamos o último.
Salvamos elemento na posição.
Empurramos tudo para frente até posição.
Parâmetros:
O dado a ser inserido.
A posição onde inserir.
Lista (global).
Lista Linear: Algoritmo RetiraDaPosicao
FUNCAO retiraDaPosição(fonte:inteiro):inteiro
var
posicao, valor:inteiro
inicio
SE (fonte > aLista.ultimo) ENTAO
 RETORNE(-3)
SENAO
 SE (listaVazia()) ENTAO
 RETORNE(-2)
 SENAO
 aLista.ultimo  aLista.ultimo - 1
 valor  aLista.dados[fonte]
 posição  fonte
 ENQUANTO (posicao <= aLista.ultimo) FACA
 aLista.dados[posicao]  aLista.dados[posicao + 1]
 posicao  posicao + 1
 FIMENQUANTO
 RETORNE(1)
 FIMSE
FIMSE
fimfuncao