Listas lineares II

Prévia do material em texto

Departamento de Informática
Curso de Ciência da Computação
ESTRUTURAS
DE DADOS
Professora: Alessandra Dahmer
Santa Cruz do Sul, março de 2000.
2
1 INTRODUÇÃO
O objetivo desta disciplina é introduzir as principais Estruturas de Dados e seus
algoritmos.
Mas antes de mais nada, deve-se responder a uma questão: Qual o papel das
Estruturas de Dados no processo de desenvolvimento de software?
Em um projeto de software, existem dois aspectos que devem ser estudados: os
procedimentos que devem ser previstos pelo software e sobre que dados estes procedimentos
irão atuar.
Nas técnicas estruturadas de projeto de software era dada ênfase aos procedimentos,
com a identificação dos aspectos funcionais na primeira etapa de desenvolvimento do software.
Com as técnicas para especificação dos dados a nível conceitual, a importância dos
procedimentos e dados tornou-se equilibrada. Atualmente, já existem técnicas de programação
com ênfase nos dados (programação baseada em objetos).
Mas, independentemente das técnicas de análise e programação utilizadas, programas
precisam manipular dados e é extremamente importante o conhecimento de conceitos e
detalhes da implementação das diversas estruturas de dados que manipulam estes dados.
Neste texto, inicialmente, alguns conceitos básicos são apresentados. À seguir, são
descritas as principais Estruturas de Dados, com seus respectivos algoritmos.
2 CONCEITOS BÁSICOS
Neste capítulo, serão apresentados conceitos essenciais para o desenvolvimento desta
disciplina: Tipos de Dados, Tipos Abstratos de Dados e Estruturas de Dados.
2.1 TIPOS DE DADOS
Em computação precisamos identificar os tipos de dados que o computador, a
linguagem de programação ou mesmo um algoritmo são capazes de entender. De uma forma
geral, os Tipos de Dados são diferenciados pelos valores que podem assumir e pelo conjunto
de operações que podemos efetuar com eles.
Em linguagens de programação o Tipo de Dados de uma variável define o conjunto de
valores que esta variável pode assumir. Uma variável do tipo lógico, por exemplo, pode
assumir dois valores: verdadeiro ou falso. As possibilidades do hardware são previstas pela
linguagem.
3
Os tipos de dados são divididos em: Tipos Primitivos de Dados e Tipos Estruturados
de Dados.
Os Tipos Primitivos de Dados são os tipos básicos, a partir dos quais podemos definir
os demais tipos e estruturas de dados. Estes tipos de dados são os mais freqüentes nas
linguagens de programação e tem um conjunto de valores e operações restrito. São
considerados Tipos Primitivos de Dados:
· Inteiro - representa uma quantidade “que pode ser contada”.
· Real - Representa um valor que pode ser fracionado.
· Lógico - Pode representar dois estados (verdadeiro ou falso).
· Caracter - Pode representar dígitos, letras ou sinais.
· Ponteiro - Representa o endereço de um dado na memória.
Os Tipos Estruturados de Dados são construídos a partir dos tipos primitivos. Estes
tipos são previstos por muitas linguagens de programação e devem ser definidos pelo
programador. Exemplos de tipos estruturados: array e registro. Estes dois tipos são formados
por tipos básicos como inteiros, caracteres, reais, etc.
Uma declaração de variável em uma linguagem de programação como Pascal
especifica duas coisas:
· Quantos bytes devem ser reservados para armazenar esta variável (Ex: no caso de
uma variável inteira, deve ser reservado um espaço que garanta que o maior inteiro
permitido poderá ser representado)
· Como estes bytes devem ser interpretados (Ex: uma cadeia de bits pode ser
interpretada como um inteiro ou um real).
Assim, Tipos de Dados podem ser vistos como métodos para interpretar o conteúdo
da memória do computador.
2.2 TIPOS ABSTRATOS DE DADOS
O conceito de tipo de dados pode ser visto de uma outra perspectiva: levando em
conta, não o que um computador pode fazer, mas o que os usuários desejam fazer. Este
conceito de Tipo de Dados independente do hardware é chamado de Tipo Abstrato de
Dados - TAD.
Um Tipo Abstrato de Dados é composto por um modelo matemático acompanhado de
um conjunto de operações definidas sobre este modelo.
Uma vez que um TAD é definido e as operações associadas a este tipo são
especificadas, pode-se implementar este tipo de dado.
4
A característica essencial de um TAD é a separação entre conceito e implementação.
A descrição dos valores e o conjunto de operações do TAD são fornecidos ao usuário, mas a
implementação é invisível e inacessível. A separação da definição do TAD da sua
implementação permite que uma mudança de implementação não altere o programa que usa o
TAD.
Exemplos de TAD:
· Listas
· Pilhas
· Filas
· Árvores
2.3 ESTRUTURAS DE DADOS
Um algoritmo é projetado em termos de tipos abstratos de dados. Para implementá-los
numa linguagem de programação é necessário encontrar uma forma de representá-los nessa
linguagem, utilizando tipos e operações suportadas pelo computador. Para representar o
modelo matemático do TAD, em uma linguagem de programação, emprega-se uma Estrutura
de Dados.
As Estruturas de Dados diferem umas das outras pela disposição ou manipulação de
seus dados. A disposição dos dados em uma estrutura obedece a condições preestabelecidas e
caracteriza a estrutura.
Assim, Estrutura de Dados é um método particular de se implementar um TAD. A
implementação de um TAD escolhe uma estrutura de dados(ED) para representá-lo. Cada ED
pode ser construída a partir de tipos básicos (inteiro, real, caracter) ou estruturados (array,
registro) de uma determinada linguagem de programação.
O estudo de Estruturas de Dados não pode ser desvinculado de seus aspectos
algorítmicos. A escolha correta da estrutura adequada a cada caso depende diretamente do
conhecimento de algoritmos para manipular a estrutura de maneira eficiente.
Por muito tempo os projetos de software consideraram importante identificar as
estruturas de dados e os algoritmos bem cedo no ciclo de vida de um software. Com o
surgimento de linguagens como ADA, tornou-se possível deixar as decisões sobre as ED para
bem mais tarde no projeto de desenvolvimento de software.
Nos próximos capítulos serão apresentados as principais Estruturas de Dados utilizadas
para representar listas, pilhas, filas e árvores. Além disso, serão apresentados os algoritmos que
devem ser utilizados para manipular estas estruturas.
5
3 LISTAS LINEARES
Definição: Dizemos que um conjunto de registros R={ R1, R2, R3, ..., Rn }, onde n >
0, tem uma estrutura de lista linear para uma determinada relação de precedência, quando:
· R1 é o 1° elemento;
· Rn é o último elemento;
· Rk precede Rk+1 para 1 £ k < n;
As listas lineares são estruturas de tamanho variável e podem ter seus elementos
ordenados ou não. Cada elemento de uma lista linear pode também ser chamado de nodo ou
nó.
As operações mais frequentes em listas lineares são as seguintes::
1) Acessar o k-ésimo elemento (Exemplo: Acessar o segundo elemento - k=2 )
 
2) Inserir nodo antes/depois do k-ésimo elemento
 
3) Retirar o k-ésimo elemento (Exemplo: Acessar o terceiro elemento - k=3 )
 
4) Contar o número de nodos (A contagem do número de nodos define o tamanho, ou
comprimento, da lista)
 
5) Pesquisar por um valor (A pesquisa por um valor busca encontrar a posição do
nodo que contém a informação que está sendo procurada)
 
6) Combinar (Combinar duas listas lineares é colocar os elementos das duas listas em
uma só, de forma ordenada ou não)
 
7) Dividir (Listas lineares podem ser divididas em duas ou mais listas, de acordo com
algum critério pré-definido. Exemplo: Dividir a lista ao meio)
 
8) Classificar (Os elementos de uma lista linear podem ser classificados. Exemplo:
Elementos em ordem alfabética)
Casos particulares de listas, definidos basicamente com restrições para inclusões e
remoções nas listas, serão detalhados nos próximos capítulos. São eles: pilhas, filas e deques.
As listas lineares são classificadas de acordo com o tipo de armazenamento em: listas
lineares sequenciais e as listas lineares encadeadas. A seguirserão apresentados estes dois
tipos de listas e os respectivos algoritmos para implementar as principais operações.
6
3.1 LISTAS SEQUENCIAIS
As listas lineares sequenciais utilizam alocação sequencial, neste tipo de alocação deve-
se estabelecer previamente o tamanho definitivo da lista. Nas linguagens de programação a
maneira mais utilizada para implementar este tipo de lista é o vetor.
Os espaços da lista são ocupados sequencialmente na memória. A identificação dos
registros ocupados é gerenciada pela linguagem ou pelo próprio programador. Geralmente
utiliza-se um ponteiro para indicar a última posição “ocupada” ( na figura abaixo é
representado por f).
 
A seguir serão apresentados os algoritmos para implementar as principais operações
com listas lineares sequencias, como a representada pela figura acima.
1) Acessar o k-ésimo elemento:
if k > f or k < 1
then “Elemento não existe”
else VALOR ¬ INFOk
2) Inserir Nodo depois do k-ésimo elemento:
if k > f or k < 1
then “K-ÉSIMO ELEMENTO NÃO EXISTE”
else if f = n
then “LISTA CHEIA”
else i ¬ f
while i > k INFOi+1 ¬ INFOi
i ¬ i - 1
INFOk+1 ¬ VALOR
f ¬ f + 1
7
3) Inserir Nodo antes do k-ésimo elemento:
if k > f or k < 1
then “K-ÉSIMO ELEMENTO NÃO EXISTE”
else if f = n
then “LISTA CHEIA”
else i ¬ f
while i ³ k INFOi+1 ¬ INFOi
i ¬ i - 1
INFOk ¬ VALOR
f ¬ f + 1
4) Retirar o k-ésimo elemento:
if k > f or k < 1
then “K-ÉSIMO ELEMENTO NÃO EXISTE”
else VALOR ¬ INFOk
while k < f INFOk ¬ INFOk+1
k ¬ k+1
f ¬ f - 1
5) Contar o Número de Nodos:
CONTA ¬ 0
if f ¹ ^ then CONTA ¬ f
6) Pesquisar por um valor:
k ¬ 1
while k £ f and INFOk ¹ VALOR
k ¬ k + 1
if k £ f
 then “ACHEI NA POSIÇÃO k”
 else “NÃO ACHEI”
8
7) Inserir Nodo na posição correta em uma lista sequencial ordenada, sem repetições de
elementos:
if f = n
 then “LISTA CHEIA”
 else
if f = ^
 then
f ¬ f + 1
INFOf ¬ VALOR
 else
k ¬ f
while k ¹ ^ and INFOk > VALOR
k ¬ k - 1
if k = ^ or INFOk < VALOR
 then
i ¬ f
while i > k
INFOi+1 ¬ INFOi
i ¬ i - 1
INFOi+1 ¬ VALOR
f ¬ f + 1
 else “VALOR JÁ ESTÁ NA LISTA”
3.2 LISTAS ENCADEADAS
As listas encadeadas utilizam alocação dinâmica. Este tipo de alocação é ideal quando
não pode-se definir previamente o tamanho da lista. Assim, não é possível definir o tamanho de
memória necessário para armazenar toda a lista.
Neste caso, são utilizados registros distribuídos aleatoriamente na memória e
interligados através de ponteiros para o endereço de memória para o próximo elemento. Uma
lista encadeada pode ser representada pela figura abaixo:
Cada elemento da lista é formado por um campo de informação (INFO) e por um
ponteiro para o próximo elemento (PROX).
Existem uma rotina para alocar espaço na memória para armazenar cada novo
elemento da lista e outra para liberar a memória de um elemento retirado da lista. Nos
9
algoritmos apresentados a seguir estas rotinas serão representadas por: ALOQUE e
DESALOQUE, respectivamente.
3.2.1 Listas Simplesmente Encadeadas
1) Acessar o k-ésimo elemento:
if i = ^or k < 1
then “Elemento não existe”
else j ¬ i
CONTA ¬ 1
while CONTA < k and j ¹ ^
j ¬ PROXj
CONTA ¬ CONTA + 1
if j = ^
 then “NÃO EXISTE ELEMENTO K”
 else VALOR ¬ INFOj
2) Inserir Nodo depois do nodo apontado por k:
ALOQUE(t)
INFOt ¬ VALOR
PROXt ¬ PROXk
PROXk ¬ t
3) Inserir Nodo antes do nodo apontado por k:
ALOQUE(t)
INFOt ¬ VALOR
PROXt ¬ k
if i = k
 then i ¬ t
 else a ¬ i
while PROXa ¹ k
a ¬ PROXa
PROXa ¬ t
INICIAL:
i ¬ ^
10
4) Retirar o nodo apontado por k:
if i = k
 then i ¬ PROXi
 else a ¬ i
while PROXa ¹ k
a ¬ PROXa
PROXa ¬ PROXk
DESALOQUE(k)
5) Contar o Número de Nodos:
CONTA ¬ 0
p ¬ i
while p ¹ ^
CONTA ¬ CONTA + 1
p ¬ PROXp
6) Pesquisar por um valor:
p ¬ i
while p ¹ ^ and INFOp ¹ VALOR
p ¬ PROXp
if p ¹ ^
 then “ACHEI”
 else “NÃO ACHEI”
7) Combinar duas listas:
PROXf ¬ p
f ¬ j
p ¬ ^
j ¬ ^
11
4 PILHAS
Uma pilha é uma lista linear na qual todas as inserções e remoções são efetuadas no
mesmo extremo da lista, no final da lista linear. Ou seja:
· A inserção de um elemento torna-o o último da lista linear
· O elemento retirado na remoção é sempre o último elemento da lista (topo).
Devido às características das operações da pilha, o último elemento a ser inserido será
o primeiro a ser retirado. Estruturas deste tipo são conhecidas como LIFO (“Last In, First
Out”).
Notação:
· Topo da Pilha: elemento ao qual se tem acesso imediato
· Empilhar: colocar um elemento no topo da pilha
· Desempilhar: retirar o elemento do topo
Exemplo: Em Pascal, as pilhas são utilizadas para implementar a recursividade em um
programa.
4.1 PILHAS SEQUENCIAIS
INICIAL:
t ¬ ^
(TOPO DA PILHA)
12
EMPILHAR (PUSH)
if t = n
then “OVERFLOW”
else t ¬ t + 1
INFOt ¬ VALOR
DESEMPILHAR (POP)
if t = ^
then “UNDERFLOW”
else VALOR ¬ INFOt
t ¬ t - 1
4.2 PILHAS ENCADEADAS
EMPILHAR (PUSH)
ALOQUE(p)
INFOp ¬ VALOR
PROXp ¬ t
t ¬ p
DESEMPILHAR (POP)
if t = ^
then “UNDERFLOW”
else VALOR ¬ INFOt
p ¬ t
t ¬ PROXt
DESALOQUE(p)
Obs: A rotina ALOQUE já prevê o OVERFLOW.
INICIAL:
t ¬ ^
(TOPO DA PILHA)
13
5 FILAS
Uma fila é uma lista linear onde todas as operações de inserção são efetuadas apenas
no final e remoções apenas no início da lista linear. Ou seja:
· A inserção de um elemento torna-o o último da lista linear
· O elemento retirado na remoção é sempre o primeiro
Devido às características das operações da fila, o primeiro elemento a ser inserido será
o primeiro a ser retirado. Estruturas deste tipo são conhecidas como FIFO (“First In, First
Out”).
Exemplo: Fila de uma impressora, onde as primeiras solicitações que chegam são as
primeiras a serem impressas.
5.1 FILAS SEQUENCIAIS
INSERÇÃO
 if SUC(f) = 1
then “OVERFLOW”
else f ¬ SUC(f)
INFOf ¬ VALOR
REMOÇÃO
 if i = f
then “UNDERFLOW”
else i ¬ SUC(i)
VALOR ¬ INFOi
14
SUC(p)
 if p = n
then SUC ¬ 1
else SUC ¬ p + 1 ÞÞ
Obs : A Rotina SUC implementa a lista sequencial de maneira circular, permitindo que
todos os espaços livres da lista possam ser ocupados.
5.2 FILAS ENCADEADAS
5.2.1 Filas Simplesmente Encadeadas
INSERÇÃO
 ALOQUE(p)
 INFOp ¬ VALOR
 PROXp ¬ ^
 if i = ^
then i ¬ p
else PROXf ¬ p
 f ¬ p
REMOÇÃO
 if i = ^
then “UNDERFLOW”
else p ¬ i
i ¬ PROXi
VALOR ¬ INFOp
DESALOQUE(p)
5.2.2 Filas Encadeadas com Header
INICIAL:
i ¬ ^
f ¬ ^
15
INSERÇÃO
 ALOQUE(p)
 INFOp ¬ VALOR
 PROXp ¬ ^
 PROXf ¬ p
 f ¬ p
REMOÇÃO
 if PROXi = ^
then “UNDERFLOW”
else p ¬ PROXi
VALOR ¬ INFOp
PROXi ¬ PROXp
if p = f then f ¬ i
DESALOQUE(p)
5.2.3 Filas Encadeadas Circulares com Header
INSERÇÃO
 ALOQUE(p)
 INFOp ¬ VALOR
 PROXp ¬ i
 PROXf ¬ p
 f ¬ p
REMOÇÃO
 if PROXi = i
then “UNDERFLOW”
else p ¬ PROXi
VALOR ¬ INFOp
PROXi ¬ PROXp
if p = f then f ¬ i
DESALOQUE(p)
INICIAL:
ALOQUE(i)
PROXi ¬ ^
f ¬ ^
INICIAL:
ALOQUE(i)
PROXi ¬ i
f ¬ ^
16
6 DEQUES
Um deque (“Double-Ended QUEue”) é uma lista linear onde as operações de
inserção e remoção podem ser efetuadas tanto no início quanto no final da lista linear. Ou seja:
· A inserção de um elemento pode torná-lo o primeiro ou o último da lista linear
· O elemento retirado na remoção é o primeiro ou o último elemento da lista
Existem variações de deque, restrições nos deques faz com que uma das operações só
possa ser efetuada em uma das extremidades do deque:
· deque de entrada restrita:
onde as inserções só podem ser
efetuadas ou no início ou no final
da lista linear
 
 
 
· deque de saída restrita: onde
as remoções só podem ser
efetuadas ou no início ou no final
da lista linear
Podemos perceber que pilhas e filas são casos particulares de deque, dependendo das
restrições que forem feitas quanto à inserção e retirada.
17
6.1 DEQUES SEQUENCIAIS
INSERÇÃO - EXT.A
 if PRED(i) = f
then “OVERFLOW”
else i ¬ PRED(i)
INFOi ¬ VALOR
REMOÇÃO - EXT.A
 if i = f
then “UNDERFLOW”
else VALOR ¬ INFOi
i ¬ SUC(i)
INSERÇÃO - EXT.Bif SUC(f) = 1
then “OVERFLOW”
else INFOf ¬ VALOR
f ¬ SUC(f)
REMOÇÃO - EXT.B
 if i = f
then “UNDERFLOW”
else f ¬ PRED(f)
VALOR ¬ INFOf
SUC(p)
 if p = n
then SUC ¬ 1
else SUC ¬ p + 1
PRED(p)
 if p = 1
then PRED ¬ n
else PRED ¬ p - 1
Obs : As rotinas SUC(sucessor) e PRED(predecessor) implementam o deque
sequencial de forma circular, permitindo que todos os espaços livres da lista possam ser
ocupados.
18
6.2 DEQUES ENCADEADOS
INSERÇÃO - INÍCIO
ALOQUE(p)
INFO(p) ¬ VALOR
PROXp ¬ PROXi
ANTp ¬ i
ANTPROXp ¬ p
PROXi ¬ p
REMOÇÃO - INÍCIO
 if PROXi = i
then “UNDERFLOW”
else p ¬ PROXi
PROXANTp ¬ PROXp
ANTPROXp ¬ ANTp
DESALOQUE(p)
INSERÇÃO - FINAL
ALOQUE(p)
INFO(p) ¬ VALOR
f ¬ ANTi
PROXp ¬ PROXf
ANTp ¬ f
ANTPROXp ¬ p
PROXf ¬ p
REMOÇÃO - FINAL
 if PROXi = i
then “UNDERFLOW”
else p ¬ ANTi
PROXANTp ¬ PROXp
ANTPROXp ¬ ANTp
DESALOQUE(p)