Estruturas de Dados: Conceito de Lista

Prévia do material em texto

Conceito de Lista [SCE182] Página 1 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
ESTRUTURAS DE DADOS I
PROFESSOR: MARCO AURÉLIO SPOHN 
1. Lista
Uma lista, como array, pode conter uma sequência ordenada de registros (records) com elementos disponíveis de 
forma consecutiva -Lista Estática Sequencial- ou não consecutiva -Lista Estática Encadeada. 
O Pascal permite construir estruturas de dados avançadas -Listas Dinâmicas-, mais versáteis utilizando ponteiros e 
variáveis dinâmicas. 
Um ponteiro é uma variável que contém o endereço de memória de uma outra variável ou estrutura de dados. Uma 
variável declarada como ponteiro é alocado durante a execução real de um programa. 
Uma variável dinâmica é a única estrutura de dados do Turbo Pascal que tem de estar identificada numa declaração 
Var antes de ser utilizada num programa. O Turbo Pascal armazena as variáveis dinâmicas numa área especial da 
memória chamada Heap (um tipo de pilha, não confundir com stack). Um programa pode criar qualquer número 
de variáveis dinâmicas, enquanto existir espaço disponível no Heap. 
 
1.1 Lista Estática Sequencial
Uma lista estática sequencial é um arranjo de registros onde estão estabelecidos regras de precedência entre seus 
elementos ou é uma coleção ordenada de componentes do mesmo tipo. O sucessor de um elemento ocupa posição 
física subsequente. 
Ex: lista telefônica, lista de alunos 
A implementação de operações pode ser feita utilizando array (vetor) e record(registro), onde o vetor associa o 
elemento a(i) com o índice i (mapeamento sequencial). 
 
1.1.1 Características de Lista Estática Sequencial 
� elementos na lista estão ordenados; 
� 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; 
Mas, absolutamente, uma lista estática sequencial ou é vazia ou pode ser escrita como ( a(1), a(2), a(3), ... a(n) ) onde 
a(i) são átomos de um mesmo conjunto S. 
Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento. 
 
 
 
Conceito de Lista [SCE182] Página 2 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Assim as propriedades estruturadas da lista permitem responder a questões como: 
� qual é o primeiro elemento da lista 
� qual é o último elemento da lista 
� quais elementos sucedem um determinado elemento 
� quantos elementos existem na lista 
� inserir um elemento na lista 
� eliminar um elemento da lista 
Consequência: As quatros primeiras operações são feitas em tempo constante. Mas, as operações de inserção e 
remoção requererão mais cuidados. 
Vantagem: 
� acesso direto indexado a qualquer elemento da lista 
� tempo constante para acessar o elemento i - dependerá somente do índice. 
Desvantagem: 
� movimentação quando eliminado/inserido elemento 
� tamanho máximo pré-estimado 
Quando usar: 
� listas pequenas 
� inserção/remoção no fim da lista 
� tamanho máximo bem definido 
1.1.2 Definição da ED (Estrutura de Dados)
Const MAX=100;
Type lista=record
A:array[1..MAX] of integer;
n:0..MAX;
End;
Var L: lista;
 
1) Acesso a um elemento 
Writeln (L.A[i]);
2) Atualização 
L.A[i]:= 'Valor'
3) Tamanho da Lista 
Conceito de Lista [SCE182] Página 3 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Begin
tamanho:=L.n;
End;
4) Inserção de um elemento na posição i 
Requer o deslocamento à direita dos elementos a(i+1)...a(n) 
 
{ considerando que a posição foi obtida em um procedimento de consulta executado 
préviamente }
{ também é necessário verificar se a lista não está cheia }
Begin
For j:=L.n+1 downto i+1 do
lista.A[j]:=L.A[j-1];
L.A[i]:='novo valor';
L.n:=L.n+1;
End;
5) Remoção do i-ésimo elemento 
Requer o deslocamento à esquerda dos elementos a(i+1)...a(n) 
Begin
For j:=i to L.n-1 do
L.A[j]:=L.A[j+1];
L.n:=L.n-1;
End;
 
 
1.1.3 Exercícios
Dada uma lista sequecial ordenada L1, escreva procedimentos Pascal que: 
� verifique se L1 está ordenada ou não (a ordem pode ser crescente ou decrescente) 
� faça uma cópia da lista L1 em uma outra lista L2; 
� faça uma cópia da Lista L1 em L2, eliminando elementos repetidos; 
� inverta L1 colocando o resultado em L2; 
� inverta L1 colocando o resultado na própria L1; 
� intercale L1 com a lista L2, gerando a lista L3. considere que L1, L2 e L3 são ordenadas. 
� gere uma lista L2 onde cada registro contém dois campos de informação: elem contém um elemento de L1, e 
count contém quantas vezes este elemento apareceu em L1. 
� elimine de L1 todas as ocorrências de um elemento dado, L1 ordenada. 
� assumindo que os elementos da lista L1 são inteiros positivos, forneça os elementos que aparecem o maior e o 
menor número de vezes (forneça os elementos e o número de vezes correspondente) 
1.2 Lista Estática Encadeada
Os elementos da lista são registros com um dos componentes destinado a guardar o endereço do registro sucessor. 
Ex: L = anta, cabra, macaco, pato, rato 
Conceito de Lista [SCE182] Página 4 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Cada registro é: 
 
ou 
 
Há duas alternativas para implementação de operações de listas encadeadas: utilizando arrays ou variáveis 
dinâmicas. 
Encadeamento em arrays
 
Eliminando o elemento "cobra" teremos: 
 
O registro 2 tornou-se disponível para as próximas inserções... 
Implementação utilizando array
Após sucessivas inserções e eliminações como descobrir quais registros estão disponíveis? 
Juntá-los numa lista DISPO. Assim, os registros 6, 7, ... m estariam inicialmente na lista DISPO. 
Como deverá ser Dispo ? Sequencial? 
Ela deve ser capaz de anexar os registros eliminados da lista principal L. Suponha que queremos inserir algum 
elemento. 
Isso implica que : 
� a eliminação de um elemento da lista principal causa a inserção de um registro na lista Dispo 
� a inserção de um elemento na lista principal causa a utilização de um dos registros da Dispo 
 
No exemplo dado, ao eliminar "cobra" anexamos esse registro à dispo. 
Conceito de Lista [SCE182] Página 5 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
A princípio podemos utilizar qualquer posição (todos são vazios mesmos!!). A posição mais conveniente é a do 
primeiro elemento do Dispo - uma vez que requer o acesso a poucos ponteiros. 
 
Se a próxima operação é a inserção do elemento ovelha temos: 
 
Com várias inserções e eliminações, os registros da lista principal ficariam espalhados pelo vetor, intermediados por 
registros disponíveis. 
Vantagens: 
� não requer mais a movimentação de elementos na inserção e eliminação (como na lista sequencial); 
� apenas os ponteiros são alterados (lembre que cada registro pode conter elementos muito complexos); 
Desvantagens: 
� necessário prever espaco máximo da lista; 
� necessário gerenciar a Dispo. 
� o acesso é não indexado, para acessar a(i) temos que percorrer a(1) ... a(i -1) pois o endereço de a(i) está 
disponível apenas em a(i-1); 
� aumento do tempo de execução, o qual é gasto obtenção de espaço de memória; 
� reserva de espaço para a Dispo; 
� tamanho máximo pré-definido. 
Quando usar: 
� quando for possível fazer uma boa previsão do espaço utilizado (lista principal + Dispo) e quando o ganho dos 
movimentos sobre a perda do acesso direto a cada elemento for compensador. 
 
1.2.1 Implementação de Operações
Supondo apenas um campo de informação do tipo T: 
 
Const N=_____; {número máximo de elementos}
Conceito de Lista [SCE182] Página 6 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html15/8/2001
Type endereço= 0..N; { elementos armazenados nas posições de
1 a N do array; o valor 0 indica fim
da lista }
Type Rec = record
info: T
lig: endereço;
End;
Lista = record
A: array[1..N] of Rec;
Prim, Dispo: endereco;
End;
Var L: lista;
1) Qual é o primeiro elemento da lista ? 
Function Primeiro (L: lista): T;
Begin
If L.Prim <> 0 Then
Primeiro := L.A[L.Prim].info;
End;
2) Qual é o último ? 
Function Ultimo(L: Lista): T;
Var p: endereco;
Begin
If L.Prim = 0 Then
{Retorna lista vazia }
Else
Begin
p := L.Prim;
While L.A[p].lig <> 0 do
p := L.A[p].lig; {L.A[p].info é o último elemento}
End;
Ultimo := L.A[p].info;
End;
3) Quantos elementos tem a lista ? 
Function No_elementos(L: Lista): integer;
Var Nelem: integer;
p: endereco;
Begin
If L.Prim = 0 Then
Nelem := 0 {lista vazia}
Else
Begin
p := L.Prim;
Nelem := 1;
While L.A[p].lig <> 0 do
Begin
Nelem := Nelem + 1; {Nelem contém o Número de elementos}
p := L.A[p].lig;
End;
End;
No_elementos := Nelem;
End;
Algoritmos para inserção e eliminação de elementos 
Os algoritmos requerem a mudança de vários ponteiros: do antecessor do registro na lista, do ponteiro da lista Dispo, 
e do registro a ser inserido/eliminado. 
Conceito de Lista [SCE182] Página 7 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Temos ObterNo(j) e DevolverNo(j), as quais permitem obter um registro de índice j da Dispo, ou devolver o registro 
de indice j, respectivamente. 
Na inserção podemos contar com o registro j como sendo disponível, e na eliminação podemos contar com o registro 
j como a ser deixado disponível. 
Para inserir ou eliminar um elemento da lista, temos que saber do endereço do predecessor (lembre que a busca é 
guiada pelo conteúdo do registro, no caso de listas ordenadas). Este predecessor é quem contém o endereço daquele 
que será o sucessor do elemento inserido/eliminado. 
inserção 
 
eliminação 
 
1) Inserção após o registro de endereço k 
Procedure Insere(var L: Lista; k: endereco, valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then {se a Dispo está vazia, nao pode inserir!}
Begin
ObterNo(j);
L.A[j].info := valor;
L.A[j].lig := L.A[k].lig;
L.A[k].lig := j;
End
Else {não pode inserir registro}
...
End;
2) Eliminação do registro de endereço j precedido por k 
Procedure Remover(var L: Lista; k,j: endereco);
Begin
L.A[k].lig := L.A[j].lig;
DevolverNo(j);
End;
3) Casos especiais 
Inserção antes do primeiro elemento 
Conceito de Lista [SCE182] Página 8 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Procedure Insere_prim(var L: Lista; valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then
Begin
ObterNo(j);
L.A[j].info:= valor;
L.A[j].lig := L.Prim;
L.Prim := j;
End
Else
{ não pode inserir }
End;
OBS: No caso da lista estar vazia, Prim passa a apontar o único elemento da lista. 
Inserção em lista vazia 
Procedure Insere_ListaVazia(var L: Lista; valor: T);
Var j: endereco;
Begin
If L.Dispo <> 0 Then { lista vazia ou prim = 0 }
Begin
Obter_No(j);
L.A[j].info:=valor;
L.A[j].lig:=0; {null}
L.Prim:=j;
End;
End;
Eliminação do primeiro elemento 
 
Procedure Remove_Primeiro(var L: Lista);
Var j: endereco;
Begin
j := L.Prim;
L.Prim := L.A[L.Prim].lig;
DevolverNo(j);
End;
4) Acesso ao i-ésimo elemento A[i].info 
Function Acessa_iesimo(L: Lista; Var dado: T): boolean;
Var p,j: endereço;
Begin
p := L.Prim; { começa do primeiro elemento }
j := 1;
While (j < i) and (p <> 0) do
Begin
Conceito de Lista [SCE182] Página 9 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
p := L.A[p].lig; { fim := (p=0) }
j := j + 1; { achou := (j=i) }
End;
If p = 0 Then
Begin
Acessa_iesimo:=false;{ lista não possui i elementos }
dado:=0;
End
Else
Begin
Acessa_iesimo:=true;
dado:=L.A[p].info; { A[p] é o elemento procurado}
End;
End;
5) Eliminar o registro de conteúdo dado pela variável valor 
Procedure Remove_elem(var L: lista; valor: T);
Var pa, p, endereco;
acabou: boolean;
Begin
pa := 0; { ponteiro anterior }
p := L.Prim; { busca a partir do primeiro }
acabou := (p=0); { termina quando fim da lista ]
While not (acabou) do
Begin
If L.A[p].info <> valor Then
Begin
pa := p;
p := L.A[p].lig;
acabou := (p=0);
End
Else
acabou := true;
End;
If p=0 Then
{ não existe o conteúdo `valor' na lista }
Else
Begin
If pa = 0 Then
L.Prim := L.A[L.Prim]lig; { eliminar o primeiro elemento }
Else
L.A[pa].lig := L.A[p].lig;
DevolverNo(p);
End;
End;
 
1.2.2 Alocação de Nó em Lista Estática Encadeada
Inicialização da Lista 
Inicialmente todas as posições do vetor A estão disponíveis, portanto fazem parte de "Dispo". 
 
Procedure Init(L: Lista);
Begin
L.Dispo:=1; {primeiro elemento}
Conceito de Lista [SCE182] Página 10 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
L.Prim:=0; {lista principal está vazia}
For i:=1 to n-1 do
L.A[i].lig:=i+1;
L.A[n].lig:=0; {receber 0 corresponde ao nil}
End;
Obter_No(j): obtém um registro de índice j da Dispo. Dispo contém pelo menos nil. 
Procedure Obter_No(var j: endereco);
Begin
j:= L.Dispo; { A dispo passa a apontar para quem ela apontava }
L.Dispo:= L.A[L.Dispo].lig;
End;
OBS: A procedure Obter_No oferece uma "posição vazia", devemos portanto, determinar os campos do 
registro. 
Devolver_No(j): devolve um registro de índice j à Dispo. 
Procedure Devolver_No(j:endereco);
Begin
L.A[j].lig := L.Dispo;
L.Dispo := j;
End;
OBS: 
� Dispo está vazia quando a lista está cheia 
� Dispo está cheia quando a lista está vazia 
 
 
1.2.3 Exercícios
1) Dada uma lista encadeada ordenada L1, escreva procedimentos Pascal que: 
� verifique se L1 está ordenada ou não (a ordem pode ser crescente ou decrescente) 
� faça uma cópia da lista L1 em uma outra lista L2; 
� faça uma cópia da Lista L1 em L2, eliminando elementos repetidos; 
� inverta L1 colocando o resultado em L2; 
� inverta L1 colocando o resultado na própria L1; 
� intercale L1 com a lista L2, gerando a lista L3. considere que L1, L2 e L3 são ordenadas. 
� gere uma lista L2 onde cada registro contém dois campos de informação: elem contém um elemento de L1, e 
count contém quantas vezes este elemento apareceu em L1. 
� elimine de L1 todas as ocorrências de um elemento dado, L1 ordenada. 
� assumindo que os elementos da lista L1 são inteiros positivos, forneça os elementos que aparecem o maior e o 
menor número de vezes (forneça os elementos e o número de vezes correspondente) 
2) Escreva os seguintes algoritmos que implementem Listas Encadeadas Estáticas (em array) com sentinela: 
� criação de lista; 
� busca em lista ordenada e não ordenada 
� inserção e eliminação de elementos 
 
Conceito de Lista [SCE182] Página 11 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
 
1.3 Lista Dinâmica
As linguagens de programação modernas tornaram possível explicitar não apenas o acesso aos dados, mas também 
aos endereços desses dados. 
Isso significa que ficou possível a utilização de ponteiros explicitamente implicando que uma distinção notacional 
deve existir entre os dados e as referências (endereços) desses dados. 
A notação introduzida por Wirth, com a introdução de Pascal, é: 
Type Tp = ^T
Essa declaração expressa que valores do tipo Tp são ponteiros para dados do tipo T. 
Portanto, lemos o simbolo ^ como sendo ponteiro para... e na declaração acima lemos Tp é um ponteiro para 
variáveis do tipo T. 
O fato de que o tipo dos elementos apontados ser evidente na declaração do ponteiro tem importância fundamental. 
Isso distingue ponteiros de linguagens de alto nível de endereços em Assembly. 
Valores para ponteiros são gerados quando dados correspondentes a seus tipos são alocados/desalocadosdinamicamente. Em Pascal, os procedimentos new e dispose existem com esse propósito. 
Portanto, deixa-se a cargo do programa (via linguagem de programação), e não do programador, prover e devolver 
espaço para inserções e eliminações em tempo de execução. 
Custo: Tempo de execução comprometido. 
Idéia: O programador declara apenas o tipo de registro que contém um elemento da lista, e avisa que a alocação será 
dinâmica. Sempre que requisitar um registro novo para a inserção, ou liberar um registro a ser eliminado, o 
programador lança mão de duas rotinas pré-definidas para este fim. 
1) Registros com ponteiros
Dizemos que uma variável do tipo prec aponta para, ou é um ponteiro para um registro do tipo rec . Ponteiro é o 
único tipo que pré-referencia outro em Pascal. 
Type prec = ^rec;
Lista = prec;
rec = record
info: T; {seu tipo preferido}
lig: Lista;
End;
Var p, L: Lista; {nossos ponteiros }
Um ponteiro do tipo Lista pode assumir o conjunto de valores que correspondem a endereços reais de memória. Por 
exemplo, sendo var p: Lista podemos ter: 
onde o conteúdo de p corresponderia ao endereço do objeto. Esses endereços serão as ligações das listas encadeadas 
Conceito de Lista [SCE182] Página 12 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
dinâmicas. 
Sendo o registro: 
O acesso ao registro depende do tipo da alocação. Se compararmos alocação em array com alocação dinâmica com 
ponteiros, temos que para acessar o conteúdo de uma variável fazemos: 
alocação alocação
array L.A[p] dinâmica p^
Para designar ponteiro, objeto e campos, a notação utilizada é: 
ponteiro: p
objeto: p^
campos: p^.info
p^.lig
2) Endereço nulo (terra)
Pascal provê uma constante pré-definida para denotar o endereço nulo nil. Podemos utilizá-la para atribuições e 
testes, como nos exemplos abaixo: 
1: L := nil;
2: If (p = nil) Then ...
Ponteiro x Objeto Apontado 
Nos exemplos abaixo, é ilustrada a diferença entre as operações de atribuição entre ponteiros (por exemplo, p : = q ) 
e a atribuição entre o conteúdo dos registros apontados pelos ponteiros (isto é: p^ : = q^). 
var p,q: Lista;
Dada a situação abaixo, chamada de (a): 
Dada a situação (a), após a atribuição p : = q temos a representação abaixo (b). Esta atribuição só é válida para 
ponteiros do mesmo tipo e é a única operação entre ponteiros. 
Dada a situação (a), após a atribuição p^ : = q^ temos a representação abaixo (c), onde o conteúdo é atribuido (lembre 
que p^ equivale a L.A[p]). 
Conceito de Lista [SCE182] Página 13 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
 
1.3.1 Manipulação de Registros
1) Declaração de Variável 
Registro do tipo rec 
var p: ^rec;
2) Criação de um registro
Substitui o procedimento ObterNo(j) dada uma variável ponteiro do tipo ^rec. 
new(p);
 
a) efetivamente aloca uma variável do tipo rec 
b) gera um ponteiro do ^rec apontando para aquela variável 
c) atribui o ponteiro à variável p 
A partir daí: 
a) o ponteiro pode ser referenciado como p 
b) variável referenciada por p é denotada por p^ 
 
3) Atribuição de conteúdo ao registro:
p^.info := valor;
4) Liberação de um registro
Substitui o DevolverNo(j) - dispose(p) 
a) operação libera o espaço apontado por p 
b) p passa a ter valor indefinido 
 
Conceito de Lista [SCE182] Página 14 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 1.3.2 Definição da ED
Type prec = ^rec;
Lista = prec;
rec = record
info: T; {seu tipo preferido}
lig: Lista
End;
Var p: Lista; {ponteiro para qualquer elemento da lista}
L: Lista; {ponteiro para o primeiro elemento da lista }
� Operações sobre Listas Dinâmicas 
1.3.3 Implementação das Operações
1) Criação da lista vazia 
 
Procedure Create (Var L : Lista);
Begin
L:= nil;
End;
2) Inserção do primeiro elemento 
 
Procedure Insere_Prim(Var L: Lista; valor: T);
Var p: Lista;
Begin
new(p);
p^.info := valor;
p^.lig := nil;
L := p;
End;
3) Inserção no início de uma lista 
Procedure Insere_Inic(Var L: Lista; valor: T);
Conceito de Lista [SCE182] Página 15 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Var p: Lista;
Begin
new(p);
p^.info := valor;
p^.lig := L;
L := p;
End;
4) Acesso ao primeiro elemento da lista 
Function Prim(L: Lista): T;
Begin
Prim:= L^.info;
End;
5) Acesso ao último elemento da lista 
Function Ultimo(L: Lista): T;
Begin
If L = nil Then
{ lista vazia}
Else
Begin
p := L;
While p^.lig <> nil do
p := p^.lig;
Ultimo := p^.info; {p^.info é último elemento}
End; {p^ é o último registro}
End;
6) Qual o número de elementos da lista ? 
Function Nelem(L: Lista): integer;
Begin
If L = nil Then
Nelem := 0
Else
Begin
p := L;
Nelem := 1;
While p^.lig <> nil do
Begin
Nelem := Nelem + 1;
p := p^.lig;
End;
End;
End;
7) Inserção do valor v depois do elemento apontado por k 
 
Procedure Insere_depois(Var L: Lista; v: T; k: Lista);
Var j: Lista;
Begin
new(j);
j^.info := v;
Conceito de Lista [SCE182] Página 16 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
j^.lig := k^.lig;
k^.lig := j;
End;
OBS: Funciona para inserção após último elemento. 
8) Remoção do elemento apontado por j, que segue k 
 
Procedure Elimina_depois(Var L: Lista; k, j: Lista);
Begin
k^.lig := j^.lig;
dispose(j);
End;
9) Remoção do primeiro elemento 
Procedure Remove_Prim(Var L: Lista);
Begin
p := L;
L:= L^.lig;
dispose(p)
End;
OBS: funciona no caso de remocao em lista com um único elemento. 
10) Eliminar um valor v de uma lista ordenada L 
 
Procedure Elimina(v: T; Var L: Lista);
Var
p, pa: Lista;
acabou: boolean;
Begin
pa := nil;
p := L;
acabou := (p = nil);
While (not acabou) do
If p^.info < v Then
Begin
pa := p;
p := p^.lig;
acabou := (p = nil);
End
Else acabou := true;
{While acaba aqui!}
{ p = nil ou p^.info = v ou p^.info > v }
If (p = nil) Then
"lista não contém v"
Else
If p^.info > v Then
Conceito de Lista [SCE182] Página 17 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
"lista não contém v"
Else
Begin
If pa = nil Then
L := p^.lig
Else pa^.lig := p^.lig;
dispose(p);
End;
End;
11) Inserção do valor v antes do elemento apontado por p 
Uma alternativa para evitarmos percorrer a lista para encontrar o antecessor de p é inserirmos o valor dado, de fato, 
após o elemento apontado por p, após realizar uma cópia de conteúdo entre ponteiros.... 
Procedure Insere_antes(Var L: Lista; v: T; p: Lista);
Var q: Lista;
Begin
new(q);
q^ := p^;
p^.info := v;
p^.lig := q;
End;
12) Criação de uma lista L com registros numerados de 1 .. n 
Procedure Cria_Lista_num(Var L: Lista);
Var L, q: Lista;
Begin
L := nil; { começa com lista vazia }
While n > 0 do
Begin
new(q);
q^.lig := L;
q^.info := n;
L := q;
n := n-1;
End;
End;
13) Remoção do registro sucessor de p e inserção do mesmo como cabeça em uma lista apontada por q 
Procedure Remove_Insere(Var q: Lista; p: Lista);
Begin
r := p^.next; {r aponta o sucessor de p^}
p^.lig := r^.lig; {r^ sai da lista}
r^.lig := q; {r^ passa a apontar q^ }
q := r; {r^ passa a ser o primeiro elemento da lista
End; apontada por q}
14) Impressão recursiva de uma lista 
Procedure Printlist(p: Lista);
Begin
If (p <> nil) Then
Begin
write(p^.info);
Printlist(p^.lig);
End;
End;
1.3.4 Exemplo de Uso de Ponteiros
Conceito de Lista [SCE182] Página 18 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Este programa cria uma lista de N elementos cujo conteúdo é o quadrado da sua posição e a impressão inclui o sinal 
negativo. 
Program Listas;
Uses Crt;
Type
prec = ^fred;
lista= prec;
fred = record
info: integer;
lig: prec;
End;
Var
L, p,q,r: lista;
N,i: 0..10;
Begin
ClrScr;
write('Dê o número de elementos da lista [1..10]:');
readln(N);
L := nil;
new(p);
p^.info := 1;
L := p;
For i := 2 to N do
Begin
new(p^.lig);
p := p^.lig;
p^.info := i*i;
End;
p^.lig := nil;
writeln('*** Impressão de sua lista ***');
p := L;
While (p <> nil) do
Begin
write(' - ',p^.info);
p := p^.lig;
End;
writeln;
writeln('*** Fim ***');
readln;
End.
1.3.5 Busca em Lista Dinâmica
1) Problema com nil ?
Se estivermos buscando um elemento x em uma lista encadeada, podemos ter algo similar a: 
while (p <> nil) and (p^.info <> x) do
p := p^.lig;
Que problema temos no comando acima ? 
No caso de p = nil o comando pode ser inválido pois p^.info não existe! 
OBS.: Se o compilador não realiza o segundo teste no caso do primeiro falhar, não haveria problema. Em nível de 
algoritmo, é melhor resolver o problema evitando a possibilidade desse tipo de erro ocorrer, ao inv és de usar soluções 
que dependem do compilador. 
Conceito de Lista [SCE182] Página 19 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
O que fizemos nos nossos algoritmos foi algo similar a: 
acabou := false;
While (p <> nil) and (not acabou) do
If p^. info = x Then
acabou := true
Else p := p^.lig;
2) Uso de sentinela na busca em lista encadeada
Um elemento sentinela pode ser utilizado na busca em lista linear encadeada: usamos para isso um registro no final 
da lista. 
Supondo que inicializamos uma lista apontada por L com a lista vazia, faremos: 
Procedure Create(var L: Lista);
Var sentinela: Lista;
Begin
new(sentinela);
L := sentinela;
End;
O algoritmo seguinte implementa uma busca por um elemento x na lista apontada por L não ordenada. Retorna p = 
nil se o elemento não for encontrado; caso contrário p aponta o registro que contém o elemento. 
Procedure busca(x: T; var L, p: Lista);
Begin
p := L;
sentinela^.info := x;
While p^.info <> x do
p := p^.lig;
If (p = sentinela) Then
p := nil; {elemento não encontrado}
End;
3) Busca com sentinela e inserção na cabeça da lista não ordenada
Caso o elemento não seja encontrado e quisermos inseri-lo no início da lista, teremos o procedimento abaixo: 
Procedure busca_insere(x: T; Var L, p: Lista);
var p: Lista;
Begin
p := L;
sentinela^.info := x;
While p^.info <> x do
p := p^.lig;
If (p = sentinela) Then
Begin
{ inserção no começo da lista}
p := L; {aponta primeiro}
new(L); {novo registro é primeiro}
L^.info := x;
L^.lig := p;
End;
End;
4) Sentinela em busca com lista encadeada ordenada
No algoritmo acima, ao realizar uma busca sequencial numa lista encadeada anulamos a vantagem de utilizar listas 
Conceito de Lista [SCE182] Página 20 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
encadeadas. Neste caso, esta implementação só pode ser considerada para listas com um número pequeno de 
elementos. 
No caso da lista estar ordenada, a busca termina assim que encontrarmos um elemento maior que aquele que 
buscamos. A ordenação é obtida ao inserirmos cada novo elemento na sua posição correta, ao invés de na cabeça da 
lista. 
Essa "ordenação" na realidade não tem custo algum, porque fazemos uso das características da lista encadeada. Isso 
não ocorre com estruturas estáticas como o array e os arquivos sequenciais. 
O procedimento abaixo elimina um registro que contém o elemento v de uma lista apontada por L. 
O bloco de busca pelo elemento realiza dois testes para cada elemento da lista. Esse esforço pode ser reduzido 
introduzindo o recurso de sentinela. 
Depois da busca, testes devem ser efetuados para verificar se: 
� o elemento foi encontrado ou não 
� se encontrado, se ele era o primeiro da lista ou não 
Procedure elimina(v: integer; Var Prim: Lista);
Var
p, pa: Lista;
acabou: boolean;
Begin
pa := nil;
p := L;
acabou := (p = nil);
While (not acabou) do
If p^.info < v Then
Begin
pa := p;
p := p^.lig;
acabou := (p = nil);
End
Else acabou := true;
{ p = nil ou p^.info = v ou p^.info > v }
If (p = nil) Then
"lista não contém v"
Else
If p^.info > v Then
"lista não contém v"
Else
Begin
If pa = nil Then
L := p^.lig
Else
pa^.lig := p^.lig;
dispose(p);
End;
End;
Dada a seguinte inicialização: 
new(root);
new(sentinel);
root^.lig := sentinel;
Temos acima um lista com dois elementos: o elemento apontado por root vai ser sempre um dummy (elemento sem 
Conceito de Lista [SCE182] Página 21 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
conteúdo), e o sentinela sempre marca o final da lista. 
O algoritmo abaixo realiza a busca de um elemento e o insere na posição correta caso ele não seja encontrado. 
Procedure busca_insere(x: T; Var root: Lista);
Var w1, w2, w3: Lista;
Begin
w2 := root;
w1 := w2^.lig;
sentinel^.info := x;
While w1^.info < x do
Begin
w2 := w1;
w1 := w1^.lig;
End;
If (w1^.info = x) and (w1 <> sentinel) Then
{elemento já existe}
Else
Begin
new(w3); {insere w3 entre w1 e w2}
w3^.info := x;
w3^.lig := w1;
w2^.lig := w3;
End;
End;
 1.3.6 Exercício 
Reescreva os algoritmos de inserção e eliminação de um elemento em uma lista duplamente encadeada de forma a 
incluir uma 
chamada à Função Busca_Dup_Ord(x). 
 
1.4 Lista Duplamente Encadeada
Características 
� Listas foram percorridas do início ao final. 
� Ponteiro "anterior" necessário para muitas operações. 
� Em alguns casos pode-se desejar percorrer uma lista nos dois sentidos indiferentemente. 
� Nestes casos, o gasto de memória imposto por um novo campo de ponteiro pode ser justificado pela economia 
em não reprocessar a lista toda. 
 
Type tpont = ^ trec;
trec = record
info:Tipoelem;
esq, dir: tpont;
End;
Lista = tpont;
Var pont: Lista;
� Como consequência, podemos realizar as operações de inserção e eliminação à esquerda ou à direita de um 
campo no interior de uma lista sem a necessidade de ponteiros "anteriores". 
Conceito de Lista [SCE182] Página 22 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Implementação de lista duplamente encadeada com alocação dinâmica 
1) Inserção à direita de pont 
Procedure ins_dir (Var pont: lista; x: Tipoelem);
Var j: Lista;
Begin
new(j);
j^.info:=x;
j^.dir:=pont^.dir;
j^.dir^.esq:=j;
j^.esq:=pont;
pont^.dir:=j;
End;
2) Inserção à esquerda de pont 
Procedure ins_esq (Var ptlista: Lista; x: Tipoelem);
Var j: Lista;
Begin
new(j);
j^.info:=x;
j^.dir:=pont;
j^.esq:=pont^.esq;
j^.esq^.dir:=j;
pont^.esq:=j;
End;
3) Eliminação à direita de pont 
Procedure elim_dir (Var pont: Lista);
Var j: Lista;
Begin
j:=pont^.dir;
pont^.dir:=j^.dir;
j^.dir^.esq:=pont;
dispose(j);
End;
4) Eliminação do próprio pont 
Procedure elim (Var pont: Lista);
Begin
pont^.dir^.esq:=pont^.esq;
pont^.esq^.dir:=pont^.dir;
dispose(pont);
End;
5) Busca em uma lista circular 
 
Conceito de Lista [SCE182] Página 23 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Funtion Busca_Dup_Ord(Var ptlista: Lista; x: Tipoelem):Lista;
{ Lista Duplamente Encadeada Ordenada com sentinela apontado por ptlista }
Var pont, ultimo: Lista;
Begin
ultimo:=ptlista^.esq;
If x<=ultimo^.info then
Begin
pont:=ptlista^.dir;
While pont^.info < x do
pont:=pont^.dir;
Busca_Dup_Ord:=pont;
End
Else
Busca_Dup_Ord:=ptlista;
End;
 
1.4.1 Exercício 
Reescreva os algoritmos de inserção e eliminação de um elemento em uma lista duplamente encadeada de forma a 
incluir uma 
chamada à Função Busca_Dup_Ord(x). 
 
 
1.5 Listas Encadeadas Circulares
A implementação de listas circulares significaram uma melhoria na utilização do espaço liberado pelos elementos que 
são retirados da fila. 
O conceito de anel (circular)pode ser aplicado também às listas comuns, como por exemplo, listas encadeadas. 
Nestas listas, um procedimento comum que devemos fazer é o de busca. Veremos a seguir como realizar buscas em 
listas circulares encadeadas. O conceito de sentinela é também utilizado. 
O trecho do algoritmo abaixo é o de busca e inserção em lista encadeada ordenada que utiliza dois registros 
auxiliares: o sentinela e o "dummy". 
Procedure busc_enc (Var root: Lista; Var sentinela: Lista; x: T);
{w2 - anterior; w1 - elemento se existir}
Var w1, w2: Lista;
Begin
w2:= root; {dummy}
w1:= w2^.lig; { primeiro elemento }
sentinela^.chave:= x;
While w1^.chave < x do
Begin
w2:=w1;
w1:=w1^.lig;
End;
If (w1^.chave = x) and (w1 <> sentinela) then
{elemento já existe}
Else
{inserir entre w1 e w2}
End;
Conceito de Lista [SCE182] Página 24 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Quando consideramos uma lista circular encadeada, podemos utilizar apenas um registro auxiliar, como indicado no 
algoritmo de busca abaixo: 
 
{ Busca em uma lista circular encadeada ordenada com sentinela.
O sentinela é o primeiro elemento da lista circular apontado por ptlista }
Procedure busc_circ (Var ptlista: Lista; x: T);
Var ant, pont: Lista;
Begin
ant:=ptlista; {sentinela}
ptlista^.chave = x;
pont:=ptlista^.lig; {primeiro elemento}
While pont^.chave < x do
Begin
ant:=pont;
pont:=pont^.lig;
End;
If pont^.chave = x and (pont<>ptlista) then
{elemento já existe}
Else
{inserir entre ant e pont}
End;
 1.5.1 Exercícios 
1) Como a lista seria inicializada nesse caso ? 
2) Como seriam os algoritmos de inserção e eliminação ? 
3) Qual alteração devemos fazer no caso das listas não serem ordenadas ? 
 
 
1.6 Listas Generalizadas 
Uma lista generalizada é aquela que pode ter como elemento ou um átomo ou uma outra lista (sub-lista). 
Toda lista pode ser representada usando-se a estrutura de nó onde: 
 
� CABEÇA (CAR) é um atomo ou um ponteiro para uma outra lista 
� CAUDA (CDR) ligação para a cauda da lista ('próximo elemento') 
� TAG é 0 (CABEÇA é atomo) ou é 1 (CABEÇA é ponteiro) 
Conceito de Lista [SCE182] Página 25 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Exemplo: 
L1 = (a, (b, c) ) 
 
L2 = (a, b, c) 
 
L3 = ( (a, b), (c, d), e) 
 
1.6.1 Implementação de Listas Generalizadas 
Utilizam o Recurso do Pascal (record variante) 
Type
pont_no = ^no;
no = record
cauda: pont_no;
case tag: boolean of
true: (pont: pont_no);
false: (atomo: tipo_elem);
End;
Lista = pont_no;
 
 
1.6.2 Variações de Listas Generalizadas
Listas Compartilhadas 
Exemplo: 
L4 = (L3, L3, ( ) ) onde: 
� L3 é a lista do exemplo anterior 
� ( ) é lista vazia 
Conceito de Lista [SCE182] Página 26 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Listas Recursivas 
Exemplo: 
L5 = (a, L5) 
 
 
 
1.6.3 Exercícios
1) Sobre Listas Generalizadas 
� Quais suas vantagens 
� Quais suas desvantagens 
� Dê exemplos de uso 
� Dê um exemplo de uma lista generalizada a qual contém, no total, pelo menos 25 átomos e 10 cabeças (em 
vários níveis). Escreva sua lista em notação de parênteses (LISP). 
� Reescreva a sua lista do item acima para incluir listas compartilhadas. Escreva sua lista em notação de 
parênteses (LISP). 
� Reescreva a sua lista do item acima para incluir listas recursivas. Escreva sua lista em notação de parênteses 
(LISP). 
2) Implemente a função abaixo, a qual determina se duas listas são iguais, assumindo que listas são não recursivas e 
compartilhadas. 
Teste o programa incluindo para as listas: 
A = B = ( ( a, b), (c, d) ) 
A = (a, (b, c) ) e B = (a, b, (c)) 
Function Igual (S,T: Lista) : boolean
Var resp:boolean;
Begin
resp:=false;
If (S=nil ) and (T=nil) Then
resp:=true;
Else
If (S<>nil) and (T<>nil) Then
If ((S^.tag = T^.tag)
Begin
If (S^.tag=false) Then
resp:=(S^.atomo, T^.atomo)
Else
resp:= igual(S^.pont, T^.pont);
If resp
Conceito de Lista [SCE182] Página 27 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Then resp:=igual(S^.cauda, T^.cauda);
End;
igual:=resp;
End;
 
1.7 Matriz Esparsa
Problema: Representação de matrizes contendo grande parte de seus elementos nulos. 
Por exemplo seja a matriz abaixo, a qual contém 5 linhas e 6 colunas. Apenas 5 de seus 30 elementos são não nulos. 
Precisamos buscar uma representação que evite o armazenamento de tantas posicões nulas. 
Veremos uma solução que utiliza, as listas cruzadas como estruturas de dados. 
Estrutura de Dados de Listas Cruzadas
Numa matriz genérica, para cada elemento temos as informacões de: 
� Linha, 
� Coluna e 
� Valor 
Para não representarmos os valores nulos, fazemos listas de linhas e listas de colunas tais que o elemento a(ij) 
diferente de 0 pertence: 
� à lista dos elementos da linha i 
� à lista dos elementos da coluna j 
Então se a matriz tem nl linhas e nl colunas, temos nl listas de linhas e nc listas de colunas. Graficamente podemos ter 
algo como: 
Conceito de Lista [SCE182] Página 28 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Para o exemplo anterior, temos: 
 
 
 
1.7.1 ED e Operações
Definição da ED 
Type
Preg = ^Reg;
Lista = Preg;
Reg = record
linha: 1..nl;
coluna: 1..nc;
valor: TipoElemento;
PL,PC: Preg; { pont p/ prox registro }
end;
var
L: array[1..nl] of Lista;
C: array[1..nc] of Lista;
1) Acesso ao primeiro elemento não nulo da linha i:
� L[i] ^ 
Conceito de Lista [SCE182] Página 29 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
2) Acesso ao elemento i,j:
� percorrer a lista L[i] até encontrar registro com campo de coluna = j ou 
� percorrer a lista C[j] até encontrar registro com campo de linha = i 
Operações com matrizes esparsas 
Além de armazenar matrizes esparsas, as aplicações normalmente exigem a realização de operações sobre essas 
matrizes, como por exemplo: 
� multiplicar uma dada linha ou coluna por uma constante 
� somar uma constante a todos os elementos de uma linha ou coluna 
� somar duas matrizes esparsas de igual dimensão 
Como consequência dessas operacões, alguns elementos podem deixar de ser nulos, enquanto que outros podem se 
tornar nulos. 
Por exemplo, ao se somar -4 a coluna 5 do exemplo temos: 
Esse exemplo ilustra que, quando um elemento a(i,j) deve ser eliminado, ele deve ser eliminado, de fato, de duas 
listas: L[i] e L[j]. 
Algoritmo: Somar k aos elementos da coluna j
 Procedure Soma (k: TipoElemento); 
 Var p: Lista; 
 begin 
 p := C[j]; 
 for i := 1 to nl do 
 if p = nil then insere(i,j,k) 
 else 
 begin 
Conceito de Lista [SCE182] Página 30 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 if p^.linha <> i then { valor era nulo} 
 inserir(i,j,k) {insere antes de p} 
 else 
 begin 
 p^.valor := p^.valor + k; 
 if p^.valor = 0 then 
 begin 
 p := p^.pc; 
 eliminar(i,j); 
 end 
 else p := p^.pc; 
 end; 
 end; 
 end; 
 
1.7.2 Usabilidade
Quando a representação de listas cruzadas é vantajosa em relação à representação convencional 
(bidimensional) ? 
Fator Espaço
Suponhamos o caso de: 
� uma matriz esparsa que armazena inteiros 
� um ponteiro que ocupa o mesmo espaço que um inteiro 
Matriz Esparsa 
Espaço ocupado por uma matriz esparsa de nl linhas, nl colunas e n valores não-nulos: 
� 5 * n espaços para ponteiros para os registros (um para cada campo do registro: linha,coluna, valor, PL, PC) 
� nl espaços para ponteiros para o vetor L 
� nc espaços para ponteiros para o vetor C 
� espaço total de 5n + nl + nc 
Representação bidimensional 
� o espaço ocupado seria nl * nc 
Conclusão: 
Em termos de espaço ocupado, há vantagem em utilizar-se a representação de listas cruzadas quando: 
5n + nl + nc < nl * nc
ou seja, quando: 
n < [(nl - 1) * (nc - 1) -1] / 5
Como (nl - 1) * (nc - 1) é aproximadamente o tamanho da matriz, pode-se dizer, de uma maneira geral que, há ganho 
em termos de espaço, quando um número inferior a 1/5 dos elementos da matriz forem não nulos. 
Conceito de Lista [SCE182] Página 31 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Fator Tempo
As operações sobre listas cruzadas podem ser mais lentas e complicadas que para o caso bidimensional. 
Portanto, para algumas aplicacões, deve ser feita uma reavaliação de tempo-espaço. 
 
1.7.3 Exercícios
1) Sobre Matrizes Esparsas (ME) 
� Quais suas vantagens 
� Quais suas desvantagens 
� Dê exemplos de uso 
� Defina vetor esparso, de tanto sua declaração como sua funcionalidade 
� Quando usar uma ME 
2) Faça algorítmos que: 
1. leia e imprima um matriz esparsa 
2. some os elementos da linha i a uma constante k 
3. some duas matrizes esparsas 
4. verifique se uma matriz esparsa é a identidade 
5. multiplique um vetor esparso por uma ME 
6. multiplique duas matrizes esparsas 
7. calcule a inversa de uma matriz esparsa 
 
2. Pilhas 
2.1 Conceito de Pilhas
Pilhas são listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única 
extremidade, no topo. 
Pilha vazia 
Insere(A) 
Insere(B) 
Retira(B) 
Conceito de Lista [SCE182] Página 32 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Insre(C) 
Retira(C) 
Retira(A) 
Definição
Dada uma pilha P=( a(1), a(2), ..., a(n) ), dizemos que a(1) é o elemento da base da pilha; a(n) é o elemento topo da 
pilha; e a(i+1) está acima de a(i). 
Pilhas são também conhecidas como listas LIFO (last in first out). 
Operações Associadas:
1. criar (P) - criar uma pilha P vazia 
2. inserir (x, P) - insere x no topo de P (empilha): push(x,P) 
3. vazia (P) - testa se P está vazia 
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar) 
5. elimina (P) - elimina o elemento do topo de P (desempilha): pop(P) 
2.2 Implementação de Pilhas
Como lista Sequencial ou Encadeada ? 
No caso geral de listas ordenadas, a maior vantagem da alocação encadeada sobre a sequencial - se a memória não for 
problema - é a eliminação de deslocamentos na inserção ou eliminação dos elementos. No caso das pilhas, essas 
operações de deslocamento não ocorrem. 
Portanto, podemos dizer que a alocação sequencial é mais vantajosa na maioria das vezes. 
Um outro modo de se implementar pode ser feito utilizando pilhas múltiplas. 
 
 
2.3 Exemplo do Uso de Pilhas
Chamadas de procedimentos
Suponha a seguinte situação: 
Conceito de Lista [SCE182] Página 33 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Quando o procedimento A1 é executado, ele efetua uma chamada a A2, que deve carregar consigo o endereço de 
retorno e1. Ao término de A2, o processamento deve retornar ao A1, no devido endereço. 
Situação idêntica ocorre em A2 e A3. 
Assim, quando um procedimento termina, é o seu endereço de retorno que deve ser consultado. Portanto, há uma lista 
implícita de endereços (e0, e1, e2, e3) que deve ser manipulada como uma pilha pelo sistema, onde e0 é o endereço 
de retorno de A1. 
No caso de processamento recursivo - por exemplo uma chamada a A2 dentro de A4 - o gerenciamento da lista como 
uma pilha resolve automaticamente a obtenção dos endereços de retorno na ordem apropriada (e0, e1, e2, e3, e4). 
 
 
2.4 Alocação Sequencial de Pilhas
Definição da Estrutura de Dados 
Type
pilha = array [1..maxp] of TipoElem;
indice = 0 .. maxp;
Var
P: pilha;
topo: indice;
 
Operações 
1. criar (P) - criar uma pilha P vazia 
procedure criar (Var topo:indice);
begin
topo := 0;
end;
2. inserir (x, P) - insere x no topo de P(empilha): push (x, P). 
procedure push (x:TipoElem; var P: pilha; Var topo: indice);
begin
Conceito de Lista [SCE182] Página 34 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
if topo = maxp then
"PILHA CHEIA"
else
begin
topo := topo + 1;
P[topo] := x;
end
end;
3. vazia (P) - testa se P está vazia 
function vazia (topo: indice): boolean;
begin
vazia := (topo = 0);
end;
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar) 
procedure top (Var topo_p: TipoElem; P:pilha; topo:indice);
begin
if topo = 0 then
"PILHA VAZIA"
else topo_p := P[topo];
end;
5. elimina (P) - elimina o elemento do topo de P (desempilha): pop (P) 
procedure pop (var P:pilha; Var topo:indice);
begin
if topo = 0 then
"PILHA VAZIA"
else topo := topo-1;
end;
Devolve elemento eliminado 
procedure pop_up (var topo_p:TipoElem; var P:pilha; 
 var topo:indice); 
 begin 
 if topo = 0 then 
 "PILHA VAZIA" 
 else 
 begin 
 topo_p := P[topo]; {no caso de acesso ao elemento} 
 topo := topo-1; 
 end; 
 end; 
 
 
2.5 Alocação Encadeada de Pilhas
Definição da Estrutura de Dados 
Type
tpont = ^reg_pilha;
pilha = tpont;
reg_pilha = record
info: TipoElem;
lig: tpont;
Conceito de Lista [SCE182] Página 35 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
End;
Var p: pilha;
 
Operações 
1. criar (P) - criar uma pilha P vazia 
procedure criar (var p: pilha);
begin
p := nil;
end;
2. inserir (x, P) - insere x no topo de P (empilha): push(x,P) 
procedure push (x:TipoElem; var p: pilha);
var pont: pilha;
begin
new(pont);
pont^.info := x;
pont^.lig := p;
p := pont;
end;
3. vazia (P) - testa se P está vazia 
function vazia (var p: pilha): boolean;
begin
vazia := (p = nil);
end;
4. topo (P) - acessa o elemento do topo da pilha (sem eliminar) 
function top (var p: pilha): TipoElem;
begin
if (p <> nil) then
top := p^.info
end;
5. elimina (P) - elimina o elemento do topo de P (desempilha) : pop(P) 
procedure pop (var p: pilha);
var aux:pilha;
begin
if (p <> nil) then
begin
Conceito de Lista [SCE182] Página 36 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
aux := p; 
p:= p^.lig;
dispose (aux);
end
end. 
2.6 Aplicação de Pilha: Notação Polonesa 
Uma representação para expressões aritméticas que seja conveniente do ponto de vista computacional é assunto de 
interesse, por exemplo, na área de compiladores. 
A notação tradicional é ambígua e, portanto, obriga o pré-estabelecimento de regras de prioridade. 
Isso torna a tarefa computacional menos simples. Outras notacões são apresentadas a seguir, considerendo-se apenas 
operações binárias (com dois operandos): 
 Notação completamente Parentizada: acrescenta-se sempre um parênteses a cada par de operandos e seu 
 operador. 
 Exemplo: 
 tradicional: A * B - C / D 
 parentizada: ((A*B)-(C/D)) 
 Notação Polonesa: os operadores aparecem imediatamente antes dos operandos. Esta notação especifica quais 
 operadores, e em que ordem, devem ser calculados. Por esse motivo dispensa o uso de parênteses, sem 
ambiguidades. 
 Exemplo: 
 tradicional: A * B - C / D 
 polonesa: - * A B / C D 
 Notação Polonesa Reversa (ou posfix): é como a polonesa na qual os operandos aparecem após os operadores. 
 Exemplo: 
 tradicional: A * B - C / D 
 polonesa reversa: A B * C D / - 
Avaliação de expressões aritméticas 
 programa fonte - notação infix: x := A / B + D * E - Aobjetivo- notação posfix: x := A B / D E * + A - 
Um algoritmo para a avaliação de Expressões PosFix: 
 empilha operandos até encontrar um operador 
 retira o número de operandos; calcula e empilha o valor resultante 
 até que chegue ao final da expressão 
Exemplo: A B / D E * + A - 
Conceito de Lista [SCE182] Página 37 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
 
 function valor ( E: expressão): TipoValor; 
 var x : TipoOperador; 
 begin 
 topo := 0; 
 while not acabou(E) do 
 begin 
 x := proxsimb(E); 
 if x é operando then push(x,pilha) 
 else 
 begin 
 remove o número de operandos (dois) para o operador x da pilha; 
 calcule o resultado da operação; 
 empilhe resultado; 
 end; 
 valor := P[topo]; 
 end; 
 
 
2.7 Exercícios 
1) Seja a função esvazie( ) tal que, recebendo uma pilha como entrada, esvazie a pilha descartando todos os seus 
elementos. 
Escreva a função esvazie( ) 
2) Escreva um programa que verifique que expressões aritméticas estão com a parentização correta. Guarde o 
resultado numa 
pilha também. Seu programa deve checar expressões para ver se cada "abre parênteses" tem um "fecha parênteses" 
correspondente. 
3) Escreva um algoritmo que converta uma expressão escrita na notação parentizada no seu equivalente na notação 
polonesa 
Conceito de Lista [SCE182] Página 38 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
reversa. 
4) Uma palavra é uma palíndrome se a seqüência de letras que a forma é a mesma seja ela lida da esquerda para a 
direita ou 
vice-versa. Exemplos: arara, rairar, hanah. Escreva a função palíndrome que, dada uma palavra, retorne true caso a 
palavra 
seja uma palíndrome, e false caso contrário. 
3 Fila 
3.1 Conceito 
É uma lista linear em que a inserção é feita numa extremidade e a eliminação na outra. (FIFO: 
first in, first out). 
 ( a1, a2 , ..., an) 
 eliminações no inserções 
 início no final 
Exemplo 
Escalonamento de "Jobs": fila de processos aguardando os recursos do sistema operacional. 
Operações associadas: 
 1.Criar (F) - criar uma fila F vazia 
 2.Inserir (x, F) - insere x no fim de F 
 3.Vazia (F) - testa se F está vazia 
 4.Primeiro (F) - acessa o elemento do início da fila 
 5.Elimina (F) - elimina o elemento do início da fila 
Implementação de filas como lista 
 Sequencial ou 
 Encadeada ? Dinâmica ou Estática ? 
Só tem sentido falarmos em fila sequencial ou encadeada dinâmica, uma vez que não existe 
movimentação de elementos. As filas encadeadas são usadas quando não há previsão do 
tamanho máximo da fila. 
 
3.2 Implementação Sequencial de Fila 
Definição da Estrutura de Dados 
 
Conceito de Lista [SCE182] Página 39 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 Type índice = 0..maxfila; 
 fila = array[1..maxfila] of TipoElem; 
 Var 
 F: fila; 
 Começo, {posição anterior ao primeiro elemento} 
 Fim: índice; {posição do último elemento} 
 
Operações com Filas 
1. Criar (F) - criar uma fila F vazia 
 Procedure CriaFila (Var Começo, Fim: indice); 
 Begin 
 Começo := 0; 
 Fim := 0; 
 End; 
2. Inserir (x, F) - insere x no fim de F 
 Procedure Inserir (x: TipoElem; Var F: fila; Var Fim: indice); 
 Begin 
 If Fim < maxfila Then 
 Begin 
 Fim := Fim + 1; 
 F[Fim] := x; 
 End 
 Else 
 { OVERFLOW } 
 End; 
3. Vazia (F) - testa se F está vazia 
 Function Vazia (Começo, Fim: indice): Boolean; 
 Begin 
 If Começo = Fim Then 
 {FILA VAZIA} 
 End; 
4. Primeiro (F) - acessa o elemento do início da fila 
 Function Primeiro (F: fila; Começo: indice): TipoElem; 
 Begin 
 x := F[Começo + 1]; 
 End; 
5. Elimina (F) - elimina o elemento do início da fila 
 Procedure Eliminar (Var Começo: indice, Fim: indice); 
 Begin 
 If (Começo = Fim) Then 
 {FILA VAZIA} 
Conceito de Lista [SCE182] Página 40 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 Else 
 Começo := Começo + 1; 
 End; 
 
3.3 Implementação Encadeada de Fila 
Definição da Estrutura de Dados 
 Type tpont = ^reg_fila; 
 fila = tpont; 
 reg_fila = record 
 info: TipoElem; 
 lig: tpont; 
 End; 
 Var Começo, Fim: fila; 
 
Operações com Filas 
1. Criar (F) - criar uma fila F vazia 
 Procedure CriaFila (Var Começo, Fim: fila); 
 Begin 
 Começo := nil; 
 Fim := nil; 
 End; 
2. Inserir (x, F) - insere x no fim de F 
 {só se lista não vazia} 
 Procedure Inserir (x: TipoElem; Var Fim: fila); 
 Begin 
 new(Fim^.lig); 
 Fim := Fim^.lig; 
 Fim^.info := x; 
 Fim^.lig := nil; 
 End; 
3. Vazia (F) - testa se F está vazia 
 Function Vazia (Começo, Fim: fila): boolean; 
 Begin 
 Vazia := ( Começo = nil) and (Fim = nil); 
 End; 
Conceito de Lista [SCE182] Página 41 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
4. Primeiro (F) - acessa o elemento do início da fila 
 Function Primeiro (Var Começo: fila): TipoElem; 
 Begin 
 Primeiro := Começo^.info; 
 End; 
5. Elimina (F) - elimina o elemento do início da fila 
 Procedure Elimina (Var Começo, Fim: fila;); 
 Var p: fila; 
 Begin 
if (começo <> nil) then
begin
 p := Começo; 
 Começo := Começo^.lig; {válido se lista não vazia} 
 If ( Começo = Fim) Then 
 Begin 
 Começo := nil; 
 Fim := nil; 
 End; 
 dispose(p);
end 
 End; 
 
 
3.4 Problema na Implementação com Fila 
O que acontece com a fila considerando a seguinte sequência de operações sobre um 
fila IEIEIEIEIE. (I - inserção e E - eliminação) 
A fila terá sempre 1 ou 0 elementos, no entanto num certo instante: 
 
Ou seja, apenas um elemento na fila, o qual ocupa a última posição do array! 
Na próxima inserção, teremos uma condição de overflow e a fila está vazia ! 
Alternativa: no algoritmo de eliminação após a atualização de Começo, verificar se a fila ficou 
vazia, i.e, Começo = Fim; se este for o caso, reinicializar Começo = Fim := 0; 
Conceito de Lista [SCE182] Página 42 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Portanto, ficaria: 
 Procedure Eliminar (Var Começo, Fim: indice); 
 Begin 
 If ( Começo = Fim) Then 
 {FILA VAZIA} 
 Else 
 Begin 
 Começo := Começo + 1; 
 If Começo = Fim Then 
 Begin 
 Começo := 0; 
 Fim := 0; 
 End; 
 End; 
 End; 
O que aconteceria se a sequência fosse IIEIEIEIEI... 
A lista estaria com no máximo dois elementos, mas ainda ocorreria overflow com a lista quase 
vazia. 
Alternativa:Forçar Fim a usar o espaço liberado por Começo (Fila Circular) 
 
 
 
 
 
 
 
 
 
 
3.5 Fila Circular 
Fila Circular Implementada como Anel 
Conceito de Lista [SCE182] Página 43 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 1.Índices do array: 0 .. m-1 
 2.Ponteiros de controle: Começo e Fim 
 3.Inicialmente Começo = Fim = 0 
 4.Quando Fim = m-1, o próximo elemento será inserido na posição 0 (se essa posição 
 estiver vazia!) 
 5.Condição de fila vazia Começo = Fim 
 6.Para inserir: 
 Procedure Inserir (Var Fim: indice); 
 Begin 
 If Fim = m-1 Then 
 Fim := 0 
 Else 
 Fim := Fim + 1; {ou Fim := ( Fim + 1 ) mod m} 
 End; 
 7.Para eliminar um elemento 
 ProcedureEliminar (Var Começo: indice); 
 Begin 
 Começo := (Começo + 1) mod m; 
 End; 
Problema: Nesta representação, como teremos fila cheia ??? 
 Começo = Fim 
 
Para resolver esse problema, utilizaremos apenas m-1 posições do anel. Deste modo, existe 
sempre um elemento vazio e, portanto, Fim não coincide com Começo. 
O algoritmo para inserção em anel fica: 
 Procedure Inserir (Var Fim: indice; Começo: indice; F: fila); 
 Begin 
 If (Fim + 1) mod m = Começo Then 
 {FILA CHEIA} 
 Else 
 Begin 
 Fim := (Fim + 1) mod m; {um registro fica vazio} 
 F[Fim] := x; 
 End; 
 End; 
O algoritmo para eliminação em anel fica: 
 Procedure Eliminar (Var Comeco: indice; Fim: indice); 
 Begin 
 If Começo = Fim Then 
 {FILA VAZIA} 
Conceito de Lista [SCE182] Página 44 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 Else 
 Começo := (Começo + 1) mod m; 
 End; 
3.6 Exercício 
1. Escreva a função esvazie( ) recebendo uma fila como entrada, esvazie a fila descartando 
todos os seus elementos. 
 
4 Árvores 
4.1 Conceito de Árvores 
Representação gráfica 
As três formas de representação gráfica são: 
Representação por parênteses aninhados 
( A (B) ( C (D (G) (H)) (E) (F (I)) ) ) 
 
Diagrama de inclusão 
 
Representação hierárquica 
Conceito de Lista [SCE182] Página 45 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Motivação 
 diversas aplicações necessitam de estruturas mais complexas que as listas estudadas até 
 agora 
 inúmeros problemas podem ser modelados através de árvores 
 árvores admitem tratamento computacional eficiente quando comparadas às estruturas 
 mais genéricas como os grafos (os quais, por sua vez são mais flexíveis e complexos) 
Definição 
Uma árvore enraizada T, ou simplesmente uma árvore, é um conjunto finito de elementos 
denominados nós ou vértices tais que: 
 T = 0 é a árvore dita vazia ou 
 existe um nó especial r, chamado raiz de T; os restantes constituem um único conjunto 
 vazio ou são divididos em m (deve ser maior ou igual a 1) conjuntos distintos não vazios 
 que são as subárvores de r, cada subárvore a qual é, por sua vez, uma árvore. 
Notação: Tv, se v é um nó de T então a notação Tv indica a subárvore de T com raiz em v. 
Subárvore 
Seja a árvore acima T = {A, B, ...} 
A árvore T possui duas subárvores: 
Tb e Tc onde 
Tb = { B } e Tc = {C, D, ...} 
A subárvore Tc possui 3 subárvores: 
Td, Tf e Te onde 
Td = {D, G, H} 
Tf = {F, I} 
Te = {E} 
As subárvores Tb, Te, Tg, Th, Ti possuem apenas o nó raiz e nenhuma subárvore. 
Exemplo: representação da expressão aritmética: (a + (b * (c / d) - e)) 
Conceito de Lista [SCE182] Página 46 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
Nós filhos, pais, tios, irmãos e avô 
Seja v o nó raiz da subárvore Tv de T. 
Os nós raízes w1, w2, ... wj das subárvores de Tv são chamados filhos de v. 
v é chamado pai de w1, w2, ... wj. 
Os nós w1, w2, ...wj são irmãos. 
Se z é filho de w1 então w2 é tio de z e v é avô de z. 
Grau de saída, descendente e ancestral 
O número de filhos de um nó é chamado grau de saída desse nó. 
Se x pertence à subárvore Tv, então, x é descendente de v e v é ancestral, ou antecessor, de x. 
Se neste caso x é diferente de v então x é descendente próprio de v e v é ancestral próprio de 
x. 
Nó folha e nó interior 
Um nó que não possui descendentes próprios é chamado de nó folha, ou seja, um nó folha é 
aquele com grau de saída nulo. 
Um nó que não é folha (isto é, possui grau de saída diferente de zero) é chamado nó interior ou 
nó interno. 
Grau de uma árvore 
O grau de uma árvore é o máximo entre os graus de seus nós. 
Floresta 
Uma floresta é um conjunto de zero ou mais árvores. 
Conceito de Lista [SCE182] Página 47 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Caminho, comprimento do caminho 
Uma sequência de nós distintos v1, v2, ..., vk, tal que existe sempre entre nós consecutivos ( 
isto é, entre v1 e v2, entre v2 e v3, ... , v(k-1) e vk) a relação "é filho de"ou "é pai de" é 
denominada um caminho na árvore. 
Diz-se que v1 alcança vk e que vk é alcançado por v1. 
Um caminho de vk vértices é obtido pela sequência de k-1 pares. O valor k-1 é o 
comprimento do caminho. 
Nível (ou profundidade) e altura de um nó 
O nível ou profundidade, de um nó é o número de nós do caminho da raiz até o nó. 
O nível da raiz, é portanto, 1. 
A altura de um nó v é o número de nós no maior caminho de v até um de seus descendentes. 
As folhas têm altura 1. 
Nível da raiz (profundidade) e altura de uma árvore 
O nível da raiz é 1 (acima). A altura de uma árvore T é igual ao máximo nivel de seus nós. 
Representa-se a altura de T por h(T) e a altura da subárvore de raiz v por h(v). 
Árvore Ordenada 
 
Uma árvore ordenada é aquela na qual os filhos de cada nó estão ordenados. Assume-se 
ordenação da esquerda para a direita. Desse modo a árvore do primeiro exemplo é ordenada, 
mas, a árvore abaixo não. 
Árvore Cheia 
Árvore com número máximo de nós 
Uma árvore de grau d tem número máximo de nós se cada nó, com exceção das folhas tem 
grau d. 
Conceito de Lista [SCE182] Página 48 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Árvore cheia de grau 2: implementação sequencial. 
 
Array com 7 posições: 
 
 
Armazenamento por nível: 
 posição do nó posição dos filhos do nó 
 1 2,3 
 2 4,5 
 3 6,7 
 i (2i,2i+1) 
 
Dentre as árvores, as binárias são, sem dúvida, as mais comumente utilizadas nas aplicações em 
computação. 
 
 
 4.2 Exercícios
1. Para a árvore abaixo: 
Conceito de Lista [SCE182] Página 49 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
� Quantas subárvores ela contém? 
� Quais os nós folhas? 
� Qual o grau de cada nó? 
� Qual o grau da árvore? 
� Liste os ancestrais dos nós B, G e I. 
� Identifique todas as relações de parentesco entre os nós 
� Justifique: podemos dizer que uma árvore é um dígrafo conexo onde existe um único nó sem predecessor e 
todos os demais têm um único predecessor. 
2. Dada uma árvore cujo grau da raiz é d, como transformá-la em uma floresta com d árvores? 
3. Dada uma floresta com d árvores como transformá-la em uma árvore cujo nó raiz tem grau d ? 
4. Para a árvore do exercício 1: 
� Liste os vértices de quem C é ancestral próprio 
� Liste os vértices de quem D é descendente próprio 
� Dê o nível e altura do vértice F. 
� Dê o nível e a altura do vértice A. 
� Qual a altura da árvore ? 
5. Explique porque a árvore do primeiro exercício e a árvore abaixo são isomórfas. 
6. Para uma árvore de grau d com número máximo de nós, diga: 
� Qual o grau dos nós internos da árvore? 
� Qual o grau dos nós folhas? 
� Quantos nós tem a árvore se o grau d e a altura é h? 
� Qual a altura da árvore se o grau é d e o número de nós é n? 
7. Para uma árvore cheia de grau d: 
� Se um nó estiver armazenado na posição i de um array, em que posições estarão seus d filhos? 
Considerando esta alocação sequencial, quais as consequências de inserções e eliminações na árvore?
 
 
Conceito de Lista [SCE182] Página 50 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
4.3 Árvore Binária
Uma Árvore Binária T é um conjunto finito de elementos denominados nós ou vértices, tal que: 
� T = 0 e a árvore é dita vazia ou 
� existe um nó especial r, chamado raiz de T, os restantes podem ser divididos em dois subconjuntos disjuntos, 
Tre e Trd, que são as subárvores esquerda e direitade r, respectivamente e as quais, por sua vez, também são 
árvores binárias. 
4.3.1 Definição da Estrutura de Dados
Type
PNo = ^no;
no = record
info: Telem;
esq, dir: PNo;
End;
Type tree: PNo;
4.3.2 Operações associadas ao TAD árvore binária padrão:
� Definir uma árvore vazia 
� Criar um nó raiz 
� Verificar se árvore vazia ou não 
� Criar um filho à direita de um dado nó 
� Criar um filho à esquerda de um dado nó 
� Verificar qual o nível de um dado nó 
� Retornar o pai de um dado nó 
1. Define uma árvore vazia 
Conceito de Lista [SCE182] Página 51 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Define uma árvore vazia e deve ser utilizado antes de qualquer outro. 
Procedure Define(var t: tree);
Begin
t:=nil;
End;
2. Cria um nó raiz 
Retorna o nó raiz da árvore em t 
Procedure Cria_Raiz(var t: tree; item: Telem);
Var no: tree;
Begin
new(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
t:=no;
End;
3. Verifica se árvore vazia ou não 
Retorna true se árvore vazia, false c.c. 
Function Vazia (t:tree):boolean;
Begin
vazia:=(t=nil);
End;
4. Criar um filho à direita de um dado nó 
� Busca elemento contendo Item_Pai 
� Se Item_Pai ainda não possui filho à direita, então cria um filho à sua direita com o conteúdo de item. 
Procedure Adicionar_Dir(t: tree; item_pai, item: Telem)
Var pai,
no: tree;
Begin
pai:=Localiza(t,item_pai);
If(pai<>nil) Then
If (pai^.dir<>nil) Then
erro("item já possui subárvore direita")
Else
Begin
New(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
pai^.dir:=nó;
End;
End;
5. Criar um filho à esquerda de um dado nó 
Procedure Adicionar_Esq(t: tree; item_pai, item: Telem)
Var pai,
no: tree;
Begin
pai:=Localiza(t,item_pai);
If(pai<>nil) Then
If (pai^.esq<>nil) Then
erro("item já possui subárvore direita")
Conceito de Lista [SCE182] Página 52 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Else
Begin
New(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
pai^.esq:=nó;
End;
End;
6. Verificar qual o nível de um dado nó 
� Retorna o nível onde está um nó com item pesquisado 
� Se item não existe retorna zero 
Function Nível (t: tree; item: Telem): integer;
Var p: integer;
Procedure Travessia (ptr: tree; niv: integer);
Begin
If ptr<>nil Then
Begin
niv:=niv+1;
If Igual(ptr^.info, item) Then
p:=niv;
Else
Begin
Travessia(ptr^.esq, niv);
If p=0 Then
Travessia(ptr^.dir, niv);
End;
End;
End;
Begin {nivel}
p:=0;
Travessia(t,p);
nivel:=p;
End;
7. Retornar o pai de um dado nó 
� Dado um item, procura se item existe na árvore 
� Caso positivo retorna o conteúdo do pai do nó 
 Function Pai(t: tree; item:Telem):Telem; 
 Var achou: boolean; 
 it : Telem; 
 Procedure Travessia(t: tree; var it: Telem); 
 Begin 
 If not Vazia(t) Then 
 Begin 
 If t^.esq<>nil Then 
 If Igual(item, t^.esq^.info) Then 
 Begin 
 achou:=true; 
 it:=t^.info; 
 End; 
 If not achou Then 
Conceito de Lista [SCE182] Página 53 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 If t^.dir<>nil Then 
 If Igual(item, t^.dir^.info) Then 
 Begin 
 achou:=true; 
 it:=t^.info; 
 End; 
 If not achou Then 
 Travessia(t^.esq, it); 
 If not achou Then 
 Travessia(t^.dir, it); 
 End; 
 End; {Travessia} 
 Begin {pai} 
 If t<>nil Then 
 Begin 
 achou:=false; 
 If Igual(item, t^.info) Then 
 pai:=t^.info; {pai do raiz é ele próprio} 
 Else 
 Begin 
 Travessia(t,it); 
 pai:=it; 
 End; 
 End; 
 End; 
 
 
4.3.3 Percurso em Árvores Binárias
Percorrer uma árvore visitando cada nó uma única vez gera uma sequência linear de nós, e então passa a ter sentido 
falar em sucessor e predecessor de um nó segundo um determinado percurso. Há três maneiras recursivas de se 
percorrer árvores binárias. 
Travessia em Pré-Ordem
1. se árvore vazia; fim 
2. visitar o nó raiz 
3. percorrer em pré-ordem a subárvore esquerda 
4. percorrer em pré-ordem a subárvore direita 
Conceito de Lista [SCE182] Página 54 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Pré-ordem: 
� ABDCEGFHI 
� visita o nó quando passar a sua esquerda 
� notação pré-fix 
� Exercício: aplique para a expressão aritmética ilustrada anteriormente 
Travessia em In-Ordem
1. se árvore vazia, fim 
2. percorrer em in-ordem a subárvore esquerda 
3. visitar o nó raiz 
4. percorrer em in-ordem a subárvore direita 
In-ordem: 
� DBAEGCHFI 
� visita o nó quando passar embaixo do nó 
� notação in-fix 
� Exercício: aplique para a expressão aritmética ilustrada anteriormente 
Travessia em Pós-Ordem
1. se árvore vazia, fim 
2. percorrer em Pós-Ordem a subárvore esquerda 
3. percorrer em Pós-Ordem a subárvore direita 
4. visitar o nó raiz 
Pós-Ordem 
Conceito de Lista [SCE182] Página 55 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
� DBGEHIFCA 
� visita o nó quando passar a sua direita 
� notação pós-fix 
� Exercício: aplique para a expressão aritmética ilustrada anteriormente 
Algoritmos de Percurso - versão recursiva
Procedure PreOrdem(N:Pno);
Begin
If N <> nil Then
Begin
Processa(N); {p. ex. imprime}
PreOrdem(N^.esq);
PreOrdem(N^.dir);
End;
End;
Procedure InOrdem(N:Pno);
Begin
If N <> nil Then
Begin
InOrdem(N^.esq);
Processa(N); {p. ex: imprime}
InOrdem(N^.dir);
End;
End;
Procedure PosOrdem(N:Pno)
Begin
If N <> nil Then
Begin
PosOrdem(N^.esq);
PosOrdem(N^.dir);
Processa(N); {p.ex.: imprime}
End;
End;
Operações Facilitadas pelos Algoritmos de Percurso:
Pesquisa se um elemento existe 
Conceito de Lista [SCE182] Página 56 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
� retorna true se elemento está na árvore 
� árvore binária comum (não é ABBusca) 
� sem sentinela 
Function Esta_Presente(t: tree; item: Telem): boolean;
Begin
Esta_Presente:= busca(t, item) <> nil;
End;
� Busca declarada apenas na implementation: Esta_Presente é disponível na interface 
� Retorna nil se elemento não encontrado 
� Usa Pós-Ordem para percorrer a árvore - visita equivale à verificar se elemento é encontrado 
Function Busca(t:tree; item: Telem): tree;
Var
achou: boolean;
ptr: tree;
Procedure Pós_Ordem(t:tree);
Begin
If (t<>nil) and (not achou) then
Begin
Pós_Ordem(t^.esq);
Pós_Ordem(t^.dir);
If Igual(item, t^.info) Then
Begin
achou:=true;
ptr:=t;
End;
End;
End; {Pós_Ordem}
Begin {busca}
achou:=false;
ptr:=nil;
Pós_Ordem(t);
busca:=ptr;
End; {busca}
Outra versão para busca 
� Utiliza implicitamente percurso em Pré-Ordem 
Function Busca1(t: tree; item: Telem): tree;
Var p: tree;
Function local(t: tree; item: Telem):tree;
Begin
p:=nil;
If t<> nil then
If t^.info=item then p:=t;
Else
Begin
local:=local(t^.esq, item);
If (p=nil) Then
local:=local(t^.dir, item);
End;
local:=p;
End; {local}
Begin {busca1}
busca1:=local(t, item);
End;
Conceito de Lista [SCE182] Página 57 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Tornar uma árvore vazia 
� Desaloca todo o espaço de memória da árvore e retorna a árvore ao estado equivalente ao define, isto é, nula. 
� Utiliza o algoritmo de Pós-Ordem para percurso 
Procedure Tornar_Vazia(var t: tree);
Begin
If not Vazia(t) Then
Begin
Tornar_Vazia(t^.esq);
Tornar_Vazia(t^.dir);
Dispose(t);
End;
t:=nil;
End;
Treinar o rastreamento dos Algoritmos de Travessia em Árvore Binária. 
4.3.4 Exercícios - Percursoem Árvore Binária 
1) Escrever o algoritmo de visita em Pré-Ordem utilizando alocação dinâmica mas sem utilizar 
procedimentos recursivos. Utilizar pilha para saber o endereço da subárvore que resta à 
direita. 
 processar raiz A 
 guardar A para poder acessar C depois 
 passa à B e processa essa subárvore 
 idem para D 
 retorna B (topo da pilha) para acessar D que é a subárvore esquerda 
2) Escrever uma função recursiva que calcule a altura de uma árvore binária dada. A altura de 
uma árvore é igual ao máximo nível de seus nós. 
 
 
4.3.5 Árvore Binária de Busca
Uma Árvore Binária de Busca T (ABB) ou Árvore Binária de Pesquisa é tal que T = 0 e a árvore é dita vazia ou 
seu nó raiz contém uma chave e: 
1. Todas as chaves da subárvore esquerda são menores que a chave da raiz. 
2. Todas as chaves da subárvore direita são maiores que a chave raiz. 
3. As subárvores direita e esquerda são também Árvores Binárias de Busca. 
Tabelas de Palavras reservadas de um compilador Pascal 
Conceito de Lista [SCE182] Página 58 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Em algoritmo de busca a medida de eficiência é dada pelo número de comparações necessárias para se localizar uma 
chave, ou descobrir que ela não existe. 
Numa lista linear com n chaves, temos que, no pior caso, faremos n comparações. O número de comparações cresce 
linearmente em função do número de chaves. 
Busca binária 
Pesquisa realizada se informação está armazenada de forma ordenada e em sequência (em um array). 
Qual a eficiência do Algoritmo de busca binária ? 
� Para n = 8 posições, o pior caso é quando precisando chegar na posição 1 ou 8. 
� A cada divisão, desprezamos toda a porção maior ou menor que a chave. 
 
Com busca binária obtemos a melhor eficiência possível em array, mas, ficamos limitados à representação sequencial 
(deslocamentos, previsão de memória, etc). 
Podemos utilizar a Árvore Binária de Busca e obteremos o mesmo desempenho anterior - desde que a altura seja 
mínima. É a característica de altura mínima que garante que estamos tomando a chave do meio da porção 
Conceito de Lista [SCE182] Página 59 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
pesquisada !! 
Com Árvore Binária de Busca Perfeitamente Balanceadas temos altura mínima. 
O número de comparações será igual a : 
 
Para garantir a performance ótima temos que garantir que a árvore seja balanceada durante a construção e que o 
balanceamento seja mantido em inserções e eliminações ! 
Definição da Estrutura de Dados e Algoritmos: 
Type Pno=^No;
Tree = Pno;
No=record
chave: Tchave;
esq, dir: Pno;
End;
Var raiz: Tree;
Algoritmo de Busca 
Function Busca (x: Tchave; raiz: Tree;):Tree;
Var achou: boolean;
p: Tree;
Begin
p:=raiz;
achou:=false;
While (not achou) and (p<>nil) do
If p^.chave = x Then
achou:=true
Else
If p^.chave > x Then
p:=p^.esq
Else p:=p^.dir;
Busca:=p;
End;
Algoritmo de Busca Recursivo 
Function Busca (x: Tchave; raiz: Tree;):Tree;
Begin
If raiz=nil Then
Busca = nil
Else
If raiz^.chave = x Then
busca:=raiz
Else
If raiz^.chave < x Then
Busca:=Busca(x, raiz^.dir)
Else
Busca:=Busca(x,raiz^.esq);
End;
Algoritmo de Busca: versão com sentinela - para eliminar teste duplo durante a busca. 
Conceito de Lista [SCE182] Página 60 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
Function Busca (x: Tchave; raiz: Tree):Tree;
Var sentinela,
p: Tree;
Begin
p:=raiz;
sentinela^.chave:=x;
While p^.chave <> x do
If p^.chave x Then
p:=p^.dir
Else p:=p^.esq;
Busca:=p;
End;
Como fica a configuração VAZIA da ABB com sentinela?? 
 
4.3.6 Árvore Balanceada e Perfeitamente Balanceada
Árvore Binária Balanceada 
Uma árvore binária é dita balanceada se, para cada nó, as alturas de suas subárvores diferem de, no máximo 1. 
Árvore Binária Perfeitamente Balanceada 
Uma árvore binária é dita perfeitamente balanceada se, para cada nó, o número de nós de suas subárvores diferem de 
no máximo, 1. 
 
 
 
Conceito de Lista [SCE182] Página 61 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
 
 
Altura de Árvore Perfeitamente Balanceada
 
Árvore Perfeitamente Balanceada é a árvore com menor altura para o seu número de nós. 
Procedimento recursivo para geração balanceada de nós:
1. Use um nó para a raiz. 
2. Gere a subárvore esquerda com nl = n div 2 nós, usando este mesmo procedimento. 
3. Gere a subárvore direita com nr = n - nl - 1 nós, usando este mesmo procedimento. 
Program Buildtree(input, output);
Type ref = ^ node;
node = record
key:integer;
left, right: ref;
End;
Var n: integer;
root: ref;
Function tree(n: integer): ref;
Var newnode: ref;
x, nl, nr: integer;
Begin
If n=0 Then
tree:=nil;
Else
Begin
Conceito de Lista [SCE182] Página 62 de 62
http://www.unicruz.tche.br/prof/maspohn/apostila/edados.html 15/8/2001
nl:=n div 2;
nr:=n - nl -1;
read(x); { conteúdo do nó }
new (newnode);
with newnode^ do
Begin
key:=x;
left:=tree(nl);
right:=tree(nr);
End;
tree:=newnode;
End;
End; {tree}
Procedure Printtree(t: ref; h: integer);
Var i: integer;
Begin {imprime tree t com indentação h}
If t<>nil Then
with t^ do
Begin
printtree(left, h+1);
for i:=1 to h do
write(' ');
writeln(key);
printtree(right, h+1);
End;
End; {printtree);
Begin {buildtree: programa principal}
read(n); { primeiro inteiro especIfica número de nós }
root:=tree(n);
printtree(root, 0);
End; { buildtree}