Estrutura de Dados I
Robson Godoi / Sandra Siebra
Conceitos de Estrutura de Dados
Estrutura da Informação
 O que é Informação ?
 Conhecimento adquirido sob qualquer forma: fatos, dados,
aprendizado, etc.
 Comunicação ou notícia trazida ao conhecimento de uma
pessoa ou público.
Estrutura da Informação
Informações
Fontes
Estrutura da Informação
 O que é Dado para o computador ?
 É a representação da informação, em forma de bytes,
permitindo acesso e mecanismos de manipulação sobre os
mesmos.
Estrutura da Informação
Informações
Nível Abstrato
Modelagem
Dado
Nível Físico
Estrutura da Informação
 Conclusão
 É de fundamental importância a forma e organização de
armazenamento da informação sob a forma de dado para
que possamos ter eficácia e eficiência nos processos de
manipulação da mesma.
Conceitos
Tipos de Dados
Representam um conjunto de valores e uma seqüência de
operações sobre estes valores.
 Tipos Primitivos:
 Tipos básicos fornecidos pelas linguagens
 Ex: Inteiro, Real, Booleano, etc.
 Tipos Construídos:
 Construídos a partir de uma combinação de tipos primitivos
 Ex: Array, Record, Class, etc
Conceitos
Tipos Abstratos de Dados (TAD)
Podemos olhar o conceito de Tipo de Dados com uma outra
perspectiva: não em termos do que um computador pode fazer
mas em termos do que os usuários desejam fazer.
Este conceito de Tipo de Dado dissociado do hardware é
chamado Tipo Abstrato de Dado (TAD).
Conceitos
Estruturas de Dados (ED)
Definem a forma utilizada para representar um Tipo Abstrato
de Dado.
Onde as informações são representadas por Tipos Primitivos
(Inteiro, Real, Booleano, etc) e/ou Tipos Construídos (Array,
Record, Class, etc) de uma linguagem de programação. E os
procedimentos e restrições sobre as mesmas são bem
definidos.
Podemos citar como exemplos de ED básicas: Listas, Pilhas,
Filas, Arvores e Grafos.
Listas
 Representam um conjunto de dados preservando a relação de
ordem entre eles.
 As listas mais simples são:
 Lista Estática Seqüencial (LES) ;
 Lista Estática Simplesmente Encadeada (LESE);
 Lista Dinâmica Simplesmente Encadeada (LDSE), ou
simplesmente, Lista Simplesmente Encadeada (LSE), a base
deste curso.
 Listas Estáticas são geralmente implementadas através de
arrays, uma vez que necessitam de uma definição prévia do seu
tamanho.
 Listas Dinâmicas são geralmente implementadas através de
ponteiros, não sendo necessária a definição prévia do seu
tamanho.
Lista Estática Seqüencial (LES)
 Uma LES é uma lista onde o sucessor de um elemento ocupa
posição física subseqüente.
 Utiliza-se array e record, onde cada elemento está associado a
um índice (mapeamento seqüencial – a(i)).
 Características:
 armazenados fisicamente em posições consecutivas;
 inserção de um elemento na posição a(i) causa o
deslocamento a direita do elemento de a(i) ao último;
 eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último.
Lista Estática Seqüencial (LES)
 Na LES o elemento a(1) é o primeiro elemento, a(i) precede
a(i+1), e a(n) é o último elemento.
 Desvantagens:
 Número máximo de elementos pré-definido
 Problemas de overflow
Lista Est. Simp. Encadeada (LESE)
 Em uma LESE a estrutura de cada elemento armazenado possui
um componente utilizado para guardar uma referência (índice)
para o próximo elemento na lista.
Início
1
2
3
4
 Vantagens:
 não requer mais a movimentação de elementos na inserção e
eliminação (como na lista seqüencial);
 Desvantagens:
 necessário gerenciar espaço disponível
 o acesso é não indexado
Lista Est. Simp. Encadeada (LESE)
A
Início
B
1
M
G
3
2
4
• Inserir o elemento E na lista entre o B e o G
Início
A
B
1
M
G
3
2
4
E
5
• Remover o elemento G da lista
Início
A
G
B
1
2
M
3
4
E
5
Lista Simplesmente Encadeada (LSE)
 Uma LSE possui o mesmo comportamento de uma LESE, no
entanto o armazenamento é feito através da alocação dinâmica
de memória no lugar de arrays. Desta forma, utilizam-se
ponteiros no lugar de índices.
 Vantagens:
 não necessita de gerenciar espaço disponível,
responsabilidade do S.O
 Neste curso utilizaremos LSE como base para as demais
estruturas de dados.
Lista Simplesmente Encadeada (LSE)
 Definição da Estrutura de Dados
type
apontador = ^celula;
registro = record
nome
idade
salario
end;
celula
= record
dado
prox
end;
TLista
= record
inicio
fim
end;
var
L : TLista;
: string [40];
: integer;
: real;
: registro;
: apontador;
: apontador;
: apontador;
Lista Simplesmente Encadeada (LSE)
 Operações sobre LSE
1.
2.
3.
4.
Criar lista vazia
Destruir a lista
Verificar se a lista está vazia
Inserir:
•
•
•
•
•
Inserir primeiro elemento
Inserir no início de uma lista
Inserir no final de uma lista
Inserir depois do elemento apontado por p
Inserir antes do elemento apontado por p
5. Excluir:
•
•
•
Excluir o primeiro elemento da lista
Excluir o último elemento da lista
Excluir o elemento com valor v da lista
6. Consultar:
•
•
•
Consultar o primeiro elemento da lista
Consultar o último elemento da lista
Consultar o elemento com valor v da lista
7. Imprimir os elementos da lista
8. Verificar o tamanho da lista
LSE - Operações
 Criar lista vazia
 Inserir o primeiro
elemento
LSE - Operações
 Inserir o elemento apontado por j depois do
elemento apontado por k
 Excluir elemento apontado por j, que segue k
LSE - Criar / Destruir
procedure Criar (var l:tlista);
begin
l.inicio := nil;
l.fim
:= nil;
end;
procedure Destruir (var l:tlista);
var aux : apontador;
begin
aux
:= l.inicio;
while (aux <> nil) do begin
l.inicio:= aux^.prox;
Dispose (Aux);
aux
:= l.inicio;
end;
l.inicio := nil;
l.fim
:= nil;
end;
LSE - Vazia
function Vazia (l:tlista):boolean;
begin
if (l.inicio=NIL) and (l.fim=NIL) then
Vazia := TRUE
else
Vazia := FALSE;
end;
OU
function Vazia (l:tlista):boolean;
begin
Vazia := (l.inicio = nil) and
(l.fim
= nil);
end;
LSE - Inserir
function Inserir (var l:tlista;
d:registro):boolean;
begin
Inserir := False;
if Vazia (l) then begin
New (l.inicio);
l.fim := l.inicio;
end
else begin
New (l.fim^.prox);
l.fim := l.fim^.prox;
end;
l.fim^.dado := d;
l.fim^.prox := nil;
Inserir
:= True;
end;
LSE - Consultar
function Consultar (
l:tlista;
var d:registro):boolean;
var
aux
: apontador;
achou : boolean;
begin
Consultar := False;
if not Vazia(l) then begin
achou
:= False;
aux
:= l.inicio;
while (aux <> nil)and (not achou) do begin
if (aux^.dado.nome = d.nome) then begin
achou
:= True;
d
:= aux^.dado;
Consultar := True;
end;
aux := aux^.prox;
end;
end;
end;
LSE - Imprimir
procedure Imprimir (l:tlista);
var
aux : apontador;
begin
if Vazia(l) then begin
writeln('Lista Vazia !!!');
end
else begin
aux := l.inicio;
while (aux <> nil) do begin
writeln ('NOME: ',
aux^.dado.nome);
writeln ('IDADE: ',
aux^.dado.idade);
writeln ('SALARIO: ', aux^.dado.salario:5:2);
writeln;
aux := aux^.prox;
end
end;
end;
LSE - Excluir
function Excluir (var l:tlista; d:registro):boolean;
var
aux
: apontador; {elemento a ser excluído}
ant
: apontador; {elemento anterior ao Aux}
achou : boolean;
begin
Excluir := False;
if not Vazia (l) then
begin
<< PROCURA O ELEMENTO – Próxima página >>
if achou then {Eliminar o elemento da memoria}
begin
Dispose(aux);
Excluir := True;
end;
end;
end;
LSE - Excluir
achou := False; ant := l.inicio;
aux := l.inicio;
while (aux <> nil) and (not achou) do begin
if aux^.dado.nome=d.nome then begin
achou := True;
if l.inicio^.prox=nil then begin {Só um elemento}
l.inicio := nil; l.fim := nil;
end
else if aux=l.inicio
then begin {Inicio da lista}
l.inicio := l.inicio^.prox;
end
else if aux=l.fim
then begin {Fim da lista}
l.fim
:= ant;
ant^.prox := nil;
end
else begin
{Meio da lista}
ant^.prox := aux^.prox;
end;
end
else begin
{Atualiza o Aux e o Ant}
ant := aux;
aux := aux^.prox;
end;
end;