Apostila Estruturas de Dados

Prévia do material em texto

ESTRUTURAS 
 
 
DE 
 
 
DADOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
ROGÉRIO FERREIRA SGOTI 
 
 
 
FACULDADE DE TECNOLOGIA DE BOTUCATU 
 
SUMÁRIO 
 
 
Apresentação da disciplina .................................................................................................. ..... 3 
1 Introdução ao estudo das estruturas de dados ..................................................................... 4 
2 Revisão de tópicos ........................................................................................................ ........ 4 
3 Registros ............................................................................................................................... 6 
4 Algoritmos de Ordenação ................................................................................................... ... 9 
5 Algoritmos de Pesquisa ......................................................................................................... 13 
6 Comparativo entre os algoritmos de pesquisa ...................................................................... 16 
7 Listas ............................................................................................................................. ........ 18 
8 Alocação Estática de Memória ...................................................................................... ........ 18 
 8.1 Lista Estática Sequencial ............................................................................................... . 18 
 8.2 Lista Estática Encadeada ............................................................................. ................... 22 
9 Alocação Dinâmica de Memória ............................................................................................ 28 
 9.1 Ponteiros ......................................................................................................................... 28 
 9.2 Listas Dinâmicas ........................................................................................................ ..... 29 
10 Pilhas ................................................................................................................................... 38 
 10.1 Operações sobre Pilhas ................................................................................................ 38 
 10.2 Aplicações de Pilhas ..................................................................................................... 39 
 10.3 Implementação de Pilhas .............................................................................................. 39 
 10.4 Alocação Sequencial de Pilhas ..................................................................................... 39 
 10.5 Alocação Dinâmica de Pilhas ........................................................................................ 42 
11 Filas ..................................................................................................................................... 44 
 11.1 Operações sobre Filas .................................................................................................. 44 
 11.2 Aplicações de Filas ........................................................................................................ 44 
 11.3 Implementação de Filas ................................................................................................ 44 
 11.4 Alocação Sequencial de Filas ....................................................................................... 45 
 11.5 Fila Circular .......................................................................................................... ......... 48 
 11.6 Alocação Dinâmica de Filas .......................................................................................... 50 
12 Espalhamento (Hashing) .............................................................................................. ....... 52 
 12.1 Fundamentos ............................................................................................................ ..... 52 
 12.2 Funções de Espalhamento ............................................................................................ 53 
 12.3 Tabelas de Espalhamento ............................................................................................. 55 
13 Recursividade ...................................................................................... ................................ 57 
 13.1 Implementação de Recursão ......................................................................................... 57 
 13.2 Recursão Degenerada .................................................................................................. 60 
 13.3 Eliminação de Recursão ................................................................................................ 62 
14 Árvores ................................................................................................................................ 64 
 14.1 Fundamentos ............................................................................................................ ..... 64 
 14.2 Árvores Binárias ............................................................................................................ 65 
 14.3 Percursos em Árvores Binárias ..................................................................................... 66 
 14.4 Algoritmos dos Percursos .............................................................................................. 68 
 14.5 Árvores de Busca Binária .............................................................................................. 70 
 14.6 Implementação de Árvores de Busca Binária ............................................................... 71 
Bibliografia ................................................................................................................ ................ 74 
ESTRUTURAS DE DADOS 
 
 
Instituição: Faculdade de Tecnologia de Botucatu 
Curso: Análise e Desenvolvimento de Sistemas 
Carga Horária: 04 h/a semanais – Total: 80 horas 
Professor Responsável: Rogério Ferreira Sgoti 
 
 
 
 
CONTEÚDO PROGRAMÁTICO 
 
Semana Tópicos 
1ª 
Apresentação da Disciplina: Objetivos, Ementa, Conteúdo 
Programático, Critério de Avaliação, Bibliografia. Revisão de Algoritmos: 
procedimentos, funções e passagens de parâmetros. 
2ª Registros. Aplicações, Sintaxes e Exemplos. Exercícios. 
3ª Manipulação de registros. Exercícios práticos. 
4ª 
Ordenação ou Classificação de dados. Conceitos. Algoritmos clássicos 
de ordenação. Simulação desses algoritmos. 
5ª 
Pesquisa ou Busca de dados. Conceitos. Algoritmos de Pesquisa 
Sequencial e Pesquisa Binária. 
6ª 
Cálculos de desempenho para algoritmos de pesquisa. Exemplos. 
Lista de Exercícios. Correção dos Exercícios. 
7ª 
Introdução às estruturas do tipo Lista. Conceitos e Aplicações. Tipos de 
Listas. Lista Estática Sequencial. Operações e Algoritmos. Simulação. 
8ª Lista Estática Encadeada. Operações e Algoritmos. Simulação. 
9ª Listas de Exercícios: listas estáticas – sequencial e encadeada. 
10ª Atendimento às dúvidas. 1ª Avaliação de Estruturas de Dados. 
11ª 
Alocação Estática X Alocação Dinâmica de Memória. Listas Dinâmicas. 
Conceitos e Aplicações. Exemplos. 
12ª 
Ponteiros. Conceitos. Notações. Exemplos. Operações e Algoritmos. 
Simulação. 
13ª 
Pilhas. Conceitos e Aplicações. Operações sobre Pilhas. Exemplos. 
Algoritmos. Simulação. 
14ª 
Filas. Conceitos e Aplicações. Operações sobre Filas. Exemplos. 
Algoritmos. Simulação. 
15ª 
Espalhamento (ou hashing). Conceitos e Aplicações. Exemplos. 
Tabelas de Espalhamento. 
16ª 
Recursividade. Conceitos e Aplicações. Vantagens e desvantagens do 
uso de recursividade. Exemplos. 
17ª 
Árvores. Conceitos e Aplicações. Operações sobre Árvores. Algoritmos. 
Exercícios. Simulação dos exercícios. 
18ª Atendimento às dúvidas. 2ª Avaliação de Estruturas de Dados. 
19ª Entrega de notase atendimento às dúvidas dos alunos. 
20ª Avaliação P3 de Estruturas de Dados e encerramento da disciplina. 
1 – INTRODUÇÃO AO ESTUDO DAS ESTRUTURAS DE DADOS 
 
 
Um programa de computador consiste em basicamente duas coisas: instruções e locais 
para se armazenarem dados e informações. Desse modo, as linguagens de programação são 
“equipadas” com mecanismos para poder controlar as instruções e os dados. Esses mecanismos 
são denominados “estruturas” e todas as linguagens de programação contemporâneas contam 
com dois tipos de estruturas: as estruturas de controle de fluxo de execução (para instruções) e 
as estruturas de dados (para os dados e informações). 
 
 
 Estruturas de Controle de Fluxo de Execução 
 
 Estrutura Sequencial; 
 Estruturas Condicionais; 
 Estruturas Iterativas; 
 Estruturas de Chamada/Retorno a/de Rotinas. 
 
 
 Estruturas de Dados 
 
 Estruturas Primitivas (Tipos de dados: inteiro, real, lógico e caracter); 
 
 Estruturas Compostas 
 
 Homogêneas (Vetores e Matrizes); 
 
 Heterogêneas (Registros e Arquivos). 
 
 Estruturas Complexas 
 
 Estáticas: Listas Estáticas (Sequenciais e Encadeadas), Pilhas, Filas, Árvores; 
 
 Dinâmicas: Listas Dinâmicas (Ponteiros), Pilhas, Filas, Árvores. 
 
 
 
2 – REVISÃO DE TÓPICOS 
 
 - Modularização; 
 
 - Variáveis Locais e Globais; 
 
 - Passagens de Parâmetros. 
 
 
Exemplos: 
 
 Algoritmos para cálculo do fatorial de um número n. 
 
 
 
Exercícios 
 
1) Escreva três algoritmos que recebam um número inteiro e exibam se esse número é primo ou 
não. Cada algoritmo com uma técnica diferente: procedimento com passagem de parâmetros por 
valor, procedimento com passagem de parâmetros por referência e por meio de função. 
 
2) Escreva um algoritmo que receba 100 números quaisquer e armazene-os em um vetor. 
Calcular e exibir o maior número e o menor número. 
 
 
 
3 – REGISTROS 
 
As estruturas de dados compostas, utilizadas até o momento (vetores e matrizes), 
permitem o armazenamento de vários valores na mesma estrutura, porém, cada estrutura só pode 
ser definida para um único tipo de dados. 
 Quando foi preciso utilizar dados de diferentes tipos para a solução de problemas, foi 
necessário o uso de diferentes estruturas. 
 Agora, é apresentada uma estrutura de dados em que é possível armazenar, na mesma 
estrutura, diversos valores de diferentes tipos de dados. Essa estrutura é chamada de Registro e, 
por sua característica, classificada como uma estrutura de dados heterogênea. 
 
Um exemplo de registro: 
 
 
 
 
 
 
 
 
 
 
 
 
Sintaxe: 
 TIPO 
 identificador_registro = REGISTRO 
 campo1: tipo de dado; 
 campo2: tipo de dado; 
 . 
 . 
 . 
 campoN: tipo de dado; 
 FIM; 
 VAR 
 identificador_variavel: identificador_registro; 
 
 
 
Exemplo: 
 BOLETIM ESCOLAR 
 
Aluno.......: Fulano de Tal 
 
1ª Nota....: 8,5 
2ª Nota....: 9,0 
3ª Nota....: 7,5 
 
Média......: 7,5 
 
 
 TIPO 
 cad_aluno = REGISTRO 
 nome: caracter; 
 nota1: real; 
 nota2: real; 
 nota3: real; 
 media: real; 
 FIM; 
 VAR 
 aluno: cad_aluno; 
 
 
Referência: 
 
identificador_variavel.campo 
 
 aluno.nome  “João”; 
 
 leia (aluno.nota1); 
 
 exiba (aluno.media); 
 
 
Exercício 
 
Escreva um algoritmo que receba o nome e as 4 notas de aluno, calcule e exiba a média das 
notas e a situação (aprovado ou reprovado) baseado na média maior ou igual a 6,0. 
 
Outro exemplo de registro: 
 
 
 
 
 
 
 
 
 
 
Exemplo: 
 
 TIPO 
 bimestre = VETOR [1..4] de real; 
 
 cad_aluno = REGISTRO 
 nome: caracter; 
 nota: bimestre; 
 media: real; 
 FIM; 
 VAR 
 aluno: cad_aluno; 
 i: inteiro; 
 
 
 BOLETIM ESCOLAR 
 
Aluno.......: Fulano de Tal 
 
Notas 
1 2 3 4 
 
 
Média......: 7,5 
 
Referência: 
 
identificador_variavel.campo[ i ] 
 
 leia (aluno.nota[ i ]); 
 
 exiba (aluno.nota[ i ]); 
 
Exercícios 
 
1) Escreva um algoritmo para manipular a ocorrência de um único aluno e suas 4 notas 
bimestrais. Receba os dados do usuário e exiba o boletim conforme o último layout apresentado. 
 
2) Idem ao anterior, porém manipular os dados para uma sala com 40 alunos. (E agora, como fica 
a estrutura de dados?). 
 
TIPO 
 bimestre = VETOR [1..4] de real; 
 
 cad_aluno = REGISTRO 
 nome: caracter; 
 nota: bimestre; 
 media: real; 
 FIM; 
 
 aluno_vet = VETOR [1..40] de cad_aluno; 
 
VAR 
 aluno: aluno_vet; 
 i, j: inteiro; 
 
 
Referências: 
 
 
 
 
leia (aluno[ i ].nome); 
 leia (aluno[ i ].nota [ j ]); 
 exiba (aluno[ i ].media); 
 
 
Exercícios 
 
1) Considerando o cadastro de uma agenda pessoal de nomes, telefones e cidades, defina a estrutura de 
registros apropriada e construa um algoritmo para armazenar 50 contatos nessa agenda. Após o 
armazenamento, exibir um relatório com os dados de todos os contatos que residem em Botucatu. 
 
 
2) Considerando o cadastro de uma agenda de prestadores de serviços contendo nome, código de área, 
telefone e cidade, defina a estrutura de registros apropriada e construa um algoritmo para armazenar 80 
contatos nessa agenda. Após o armazenamento, exibir um relatório com os dados de todos os prestadores 
de serviço de uma determinada área de telefone. Essa informação deve ser solicitada para o usuário. Obs: 
o código de área deve ser um campo separado do número do telefone (para possibilitar a consulta prevista 
no algoritmo). 
 
identificador_variavel[ i ].campo[ j ] identificador_variavel[ i ].campo 
4 – ALGORITMOS DE ORDENAÇÃO OU CLASSIFICAÇÃO 
 
 
4.1 Algoritmo Bubble Sort (ou método da bolha) 
 
Por ser simples e de fácil implementação o algoritmo Bubble Sort ou método da bolha está 
entre os mais conhecidos e difundidos métodos de ordenação de arranjos de dados. Mas não se 
trata do algoritmo mais eficiente. É estudado para desenvolvimento do raciocínio lógico e como 
introdução ao assunto de ordenação ou classificação de dados. 
O princípio da dinâmica de funcionamento desse algoritmo é o teste e a troca de valores 
entre as posições consecutivas do arranjo, fazendo com que os valores mais altos (ou mais 
baixos) “borbulhem” para o final do arranjo (ou começo). Este algoritmo realiza (n-1) iterações. 
 
Exemplo: 
 
 Situação inicial: 
1 2 3 4 5 
7 9 8 5 3 
 
 
1ª Iteração 
1 2 3 4 5 
7 8 5 3 9 
 
 
 2ª Iteração 
1 2 3 4 5 
7 5 3 8 9 
 
 
 3ª Iteração 
1 2 3 4 5 
5 3 7 8 9 
 
 
4ª Iteração 
 
1 2 3 4 5 
3 5 7 8 9 
 
 
 
 
Exercício 
 
Escreva um algoritmo que armazene 100 valores num vetor e exiba-os em ordem crescente, 
implementando o método bubblesort. 
 
 
 
4.2 Algoritmo Selection Sort 
 
O algoritmo do método de ordenação Selection Sort seleciona o maior elemento do arranjo 
e troca-o com o elemento da última posição. A cada iteração desconsidera a “última” posição do 
vetor fazendo com que o arranjo fique “menor”. Esse algoritmo também realiza (n-1) iterações 
para garantir que os elementos estejam ordenados. 
 
Dinâmica de funcionamento: 
 
- Na primeira iteração o algoritmo encontra o maior elemento do vetor e troca este 
elemento com o elemento que está na n-ésima posição; 
 
 - Na segunda iteração despreza-se o n-ésimo elemento e encontra-se novamente o maior 
elemento (exceto o maior elemento já identificado na primeira iteração, este segundo maior é o 
maior entre os demais) e troca-se com o elemento que está na (n-1)-ésima posição; 
 
 - Este processo se repete até que se tenha ordenado todos os elementos do arranjo. 
 
 
Exemplo: 
1 2 3 4 5 
7 9 8 5 3 
 
 
 - Percorre-se o vetor na busca do maior elemento. Neste caso, o maior elemento é o 9, que 
está na posição 2. Troca-se então esse elemento com o elemento que está na última posição. 
 
 
 Situação inicial: 
1 2 3 4 5 
7 9 8 5 3 
 
 
 
 
1ª Iteração 
1 2 3 4 5 
7 3 8 5 9 
 
 
 - Finalizada a primeira iteração inicia-se o processo novamente, selecionando o maior 
elementoe trocando-o com a penúltima posição. E assim sucessivamente... 
 
 
Exercício 
 
Escreva um algoritmo que armazene 100 valores num vetor e exiba-os em ordem crescente, 
implementando o método selection sort. 
 
 
 
 
4.3 Algoritmo Insertion Sort 
 
O algoritmo do método de ordenação Insertion Sort utiliza a técnica de indução algorítmica 
para resolver o problema de ordenação. Assim, sabendo-se resolver um problema menor, 
resolve-se um problema maior. 
Dinâmica de funcionamento: 
 
 Considere o vetor V assim definido: V = { V1, V2, V3, . . . ., Vn-1, Vn }. 
 
 Considere o vetor V´ assim definido e já ordenado: V´ = { V1}. 
i-maior 
 
 A dinâmica consiste em comparar do segundo elemento em diante do vetor V com o 
elemento (sempre já ordenado) do vetor V´ e inseri-los na posição correta do vetor V´. 
 
 Exemplo: 
1 2 3 4 5 
9 8 7 5 3 
 
 
 
Tem-se: V´ = 9 
 
 V = 8 7 5 3 
 
 Inserir o elemento 8 no vetor já ordenado V´. 
 
1 2 3 4 5 
9 8 7 5 3 
 
 
 Para inserir o elemento 8 na posição correta do vetor V´, desloca-se o elemento 9 
para uma posição a direita. 
 
1 2 3 4 5 
8 9 7 5 3 
 
 
 
 Assim, o processo se repete até que o vetor esteja ordenado. 
 
 
1 2 3 4 5 
8 9 7 5 3 
 
 
 
1 2 3 4 5 
7 8 9 5 3 
 
 
 
 
1 2 3 4 5 
5 7 8 9 3 
 
 
 
 
1 2 3 4 5 
3 5 7 8 9 
 
 
Exercício 
 
Escreva um algoritmo que armazene 100 valores num vetor e exiba-os em ordem crescente, 
implementando o método insertion sort. 
V´ V 
V´ V 
V´ V 
V´ V 
5 – ALGORITMOS DE PESQUISA (OU BUSCA) 
 
 
 São dois os métodos de pesquisa ou busca por uma ocorrência de algum elemento dentro 
de um arranjo de dados que são mais comumente usados. Geralmente é o usuário da aplicação 
quem fornece o valor do elemento que está sendo procurando e que tem interesse na pesquisa. 
Esses dois métodos são: a pesquisa sequencial e a pesquisa binária. 
 Sobre qual desses tipos de pesquisa apresenta o melhor resultado, depende-se 
exclusivamente da quantidade de operações realizadas para encontrar determinado elemento no 
arranjo. E isso é determinado por dois fatores: a quantidade de elementos do arranjo e a 
quantidade de consultas que se faça no mesmo. 
 Após conhecer como funcionam os dois tipos de pesquisa, no próximo capítulo serão 
apresentados alguns cálculos sobre como calcular a quantidade de operações necessárias para 
encontrar (ou não) um elemento dentro do arranjo de dados. Assim, pode-se decidir de modo 
mais exato, qual dos dois métodos é o melhor aplicar em cada situação. 
 
 
5.1 Pesquisa Sequencial 
 
O método de pesquisa sequencial consiste em efetuar a busca da informação desejada a 
partir do primeiro elemento, percorrendo o vetor sequencialmente até o último elemento. 
Localizando a informação procurada em algum dos elementos, esta é apresentada ao usuário e 
encerra-se a busca. Este método de pesquisa é, na média, um tanto lento. Porém, eficiente nos 
casos em que o vetor contenha seus elementos de forma desordenada. 
 
 Exercício: Escreva um algoritmo que implemente o método de pesquisa sequencial. 
 
 
5.2 Pesquisa Binária 
 
O método da pesquisa binária apresenta um mecanismo que, na média, se mostra mais 
rápido em comparação ao método da pesquisa sequencial. Uma diferença é que, para aplicar a 
pesquisa binária, o arranjo de dados deve, obrigatoriamente, estar previamente ordenado. 
Depois de ordenado o vetor, este é dividido em duas partes e examinado se a informação a 
ser pesquisada se encontra na linha de divisão (meio) do vetor ou se está acima ou abaixo desta 
linha de divisão. Se estiver acima, toda a metade inferior é desprezada para verificação. Em 
seguida, se a informação não foi encontrada no meio (lembre-se de que o vetor já está 
ordenado!), dividimos novamente esta metade do vetor em duas partes e examinamos se a 
informação está no meio, acima ou abaixo da linha divisória. Assim, o processo de divisão e 
descarte continua até que a informação seja encontrada ou até se acabar os elementos do 
arranjo. 
 
 
 
 
 
Exercício: Escreva um algoritmo que implemente o método de pesquisa binária. 
 
 
 
Exercício 
 
Escreva um algoritmo que exiba um menu para o usuário com as opções: Tamanho do Vetor, 
Armazenar Valores, Ordenar Valores, Tipo de Pesquisa, Pesquisar e Sair; e implemente essas 
funcionalidades. 
 
 
 
 
 
 
 
 
6 – COMPARATIVO ENTRE OS ALGORITMOS DE PESQUISA 
 
 
 Cálculo do nº de Operações para Pesquisas Sequencial e Binária 
 
 
Considerações: 
 
 Para a Ordenação do arranjo: 
 
o tem-se (n – 1) iterações; 
o o vetor verificará (n – 1) elementos; 
o logo, (n – 1).(n – 1) = n2 – 2n + 1. 
o a qtde de operações 
é proporcional a n2 
 
 
 Para a Pesquisa no arranjo: 
 
o n = nº de iterações por pesquisa ou nº de elementos do arranjo; 
o m = qtde de pesquisas; 
o op = nº de operações realizadas. 
 
 
 
 Pesquisa Sequencial 
 
 
Op = n . m 
 
 
 
 Pesquisa Binária 
 
 
- Na ordenação: op´ = n2 
 
- Na pesquisa: 
1ª iteração  n/2 = n/21 
 
 
 log2 (n) = x  
2ª iteração  n/4 = n/22 
3ª iteração  n/8 = n/23 
. . 
. . 
xª iteração  n/2x = 
 
 
 - Se forem realizadas m pesquisas, tem-se: op´´ = m . log2 (n) 
 
 - Logo, o nº total de operações para a pesquisa binária é dado por op = op´ + op´´ 
 
 -  
 
 Op = n2 + m . log2 (n) 
 
 
desprezível 
2x = n 
 Exemplo: Arranjo com 8 elementos 
 
 n = 8 
 
 log2 (8) = 
 
2x = 8 
 
x = 3 
 
 São necessárias 3 iterações (operações) 
 
 
 
 
 Exercícios 
 
 
 1) Dado um vetor com 8 elementos, decidir e apontar qual o melhor tipo de pesquisa a ser 
aplicada no caso de necessidade de 1000 consultas nesse vetor. 
 
 
 2) Considere um arranjo com 8192 elementos. Qual o tipo de pesquisa é mais vantajoso 
para 1000 consultas? 
 
 
 3) Dado um vetor com 30 elementos, indicar qual o melhor método de pesquisa para uma 
necessidade de 250 consultas. 
 
 
 4) Determinado arranjo contém 3875 elementos e há necessidade de realizar 327 
consultas. Nesse caso, qual método de pesquisa aplicar? 
 
 
 5) Dado um vetor com 1480 elementos e necessidade de 15 consultas qual tipo de 
pesquisa você implementaria? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7 – LISTAS 
 
 
 Uma Lista é uma estrutura de dados que armazena em memória um conjunto de 
elementos, sendo estes dispostos um após o outro, como em uma lista telefônica, um catálogo de 
peças, entre outros. Existem vários tipos de listas, e as diferenças que os determinam são: o 
modo e a política como são realizadas as operações sobre cada tipo de lista. As principais 
operações são, entre outras, inclusão de elementos na lista, acesso a um determinado elemento 
da lista, exclusão de um elemento, verificação de lista vazia, verificação de lista cheia e 
quantidade de elementos na lista. 
A partir de agora, praticamente todas as estruturas de dados que serão estudadas são 
derivadas de algum tipo de lista. As listas podem ser classificadas de várias formas, que 
dependem de alguns fatores, como: o modo como é implementada a alocação de memória; a 
natureza de manipulação dos elementos da lista e, ainda, como ficam dispostos os elementos em 
relação à linearidade ou à hierarquia da estrutura. 
 
 
Classificação e Tipos de Listas 
 
 Quanto à Linearidade ou Hierarquia da Estrutura 
 
 Listas Lineares (Listas Seqüenciais, Encadeadas, Pilhas e Filas); 
 Listas Não-Lineares (Árvores). 
 
 Quanto à Alocação de Memória 
 
 Estática; 
 Dinâmica. 
 
 Quanto à Natureza de Manipulação dos Elementos 
 
 Sequencial; 
 Encadeada. 
 
 
8 – ALOCAÇÃO ESTÁTICA DE MEMÓRIA 
 
 Com alocação estática de memória, as listas podem ser implementadas de forma 
sequencial ou encadeada. 
 
 
8.1 – Lista Estática Sequencial 
 
 A lista estática sequencial é uma lista linear implementada como um arranjo de registros 
onde estão estabelecidas regras de precedência entre os seus elementos e se configura como 
uma coleção ordenada de componentes do mesmo tipo.Exs: Lista de telefones e Lista de alunos. 
 
 Características 
 
- Os elementos na lista estão ordenados e armazenados fisicamente em posições 
consecutivas; 
- A inserção de um elemento na posição i causa o deslocamento a direita dos 
elementos de i até o último; 
- A eliminação do elemento i requer o deslocamento a esquerda dos elementos (i+1) 
até o último; 
- Uma lista estática seqüencial L, ou é vazia ou pode ser descrita como: 
 
L = 
índice (i) 1 2 3 ... ... n 
elemento a1 a2 a3 ... ... an 
 
 onde: 
 a1 é o primeiro elemento da lista; 
 ai precede ai+1; 
 an é o último elemento da lista. 
 Vantagens 
 
- Acesso direto indexado a qualquer elemento da lista; 
- Tempo constante para acessar o elemento da posição i. 
 
 Desvantagens 
 
- Movimentação de elementos nas operações de inserção e eliminação; 
- O tamanho máximo da lista deve ser pré-estimado. 
 
 Quando usar 
 
- Listas pequenas; 
- O tamanho máximo da lista for bem definido; 
- Manipulação de dados com características de inserção e eliminação no final da 
lista. 
 
 
 Implementação 
 
TAD (Tipo Abstrato de Dados) 
 
CONST 
 max = ----; 
 
TIPO 
 Lista = REGISTRO 
 elem: VETOR [1..max] de T; 
 num: 0..max; 
 FIM; 
VAR 
 L: Lista; 
 
 
Exemplos: 
 
a) Rotina para criar uma lista estática sequencial. 
 
Procedimento CRIA_LISTA (var L: Lista); 
Inicio 
 L.num  0; 
Fim; 
Tipo de Dado 
inteiro, real, 
lógico ou caracter 
b) Rotina para verificar se a lista está ou não vazia. 
 
Funcao VAZIA (L: Lista): logico; 
Inicio 
 se (L.num = 0) 
 entao VAZIA  verdadeiro 
 senao VAZIA  falso; 
 fim se; 
Fim; 
 
 
Operações sobre Listas Estáticas Sequenciais 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
1) Inserir um elemento na lista, em sequência. 
2) Inserir um elemento na lista, em determinada posição. 
3) Retornar o primeiro elemento da lista. 
4) Retornar o último elemento da lista. 
5) Retornar a quantidade de elementos da lista. 
6) Eliminar um elemento da lista (não sendo o último). 
7) Eliminar o último elemento da lista. 
8) Verificar se os elementos da lista estão ordenados. 
 
 
 
8.2 – Lista Estática Encadeada 
 
 
 Os elementos de uma lista estática encadeada são registros com um dos componentes 
(campos) destinados a guardar o endereço do próximo registro, possibilitando assim o 
encadeamento dos elementos da lista. Cada registro tem o seguinte formato: 
 
 
Valor lig Ex: Alessandra 2 
 
 
 
 Uma lista hipotética L possui os seguintes elementos: Bruna, Daniel, Kátia, Mário e Rose. 
Então, pode-se representar a lista L da seguinte forma: 
 
 
 
L = Bruna Daniel Kátia Mário Rose 
 
 
 
 
 
 
1 2 3 4 5 
1º 
elemento 
último 
elemento fim da 
lista 
 Para gerenciar esse tipo de lista deve-se trabalhar com dois conjuntos de informação: os 
elementos da lista (armazenados) e as posições da lista que ainda estão disponíveis. Obs: 
Considera-se como “fim da lista” o último elemento do vetor que tenha valor armazenado, que 
pode não ser necessariamente o tamanho máximo do vetor. Convencionou-se a utilizar o valor 0 
(zero) para referenciar o fim da lista. Assim tem-se: 
 
 
 
 
L = Bruna Daniel Kátia Mário Rose 
 
 
 
 
 
 
 Como exemplo o elemento com o valor “Kátia” será eliminado da lista. Nesse caso, o 
registro desta posição ficará disponível e pronto para ser usado novamente. Assim, a referência 
desse registro deve passar a integrar a lista denominada por “Dispo” que contém os registros 
ainda livres (disponíveis) da lista. 
 
 
 
 
 
L = Bruna Daniel Kátia Mário Rose 
 
 
 
 
 
 Se numa próxima inserção houver a necessidade de inserir o valor “Silvia” na lista, esta 
deve ficar configurada da seguinte forma: 
 
 
 
L = Bruna Daniel Silvia Mário Rose 
 
 
 
 
 
 Deve ficar claro que o que importa é o encadeamento dos elementos e não a ordem 
seqüencial física do armazenamento. 
 
 
 Vantagens 
 
- Não requer a movimentação dos elementos nas operações de inserção e eliminação; 
- Apenas os campos de ligação são manipulados e alterados. 
 
 
 Desvantagens 
 
- Necessário prever espaço máximo da lista; - Aumento no tempo de execução; 
- Necessidade de gerenciar o campo Dispo; - Reserva de espaço para Dispo. 
1 2 3 4 5 
1º 
elemento 
(Prim) 
último 
elemento 
Dispo 
6 ... max 
1 2 3 4 5 
1º 
elemento 
(Prim) 
último 
elemento 
Dispo 
6 ... max 
1 2 3 4 5 
1º 
elemento 
(Prim) 
último 
elemento 
Dispo 
6 ... max 
- O acesso não é indexado; 
 
 
 Quando usar 
 
- Quando for possível fazer uma boa previsão do espaço utilizado; 
- Quando o ganho dos movimentos dos elementos sobre a perda de acesso direto a cada 
elemento for compensatório. 
 
 
 Implementação 
TAD (Tipo Abstrato de Dados) 
 
CONST 
 max = ----; 
 
TIPO 
 endereço = 0..max; 
 
 Reg = REGISTRO 
 info: T; 
 lig: endereco; 
 FIM; 
 
 Lista = REGISTRO 
 A: VETOR [1..max] de Reg; 
 prim, dispo: endereco; 
 FIM; 
VAR 
 L: Lista; 
 
 
 Operações sobre listas seqüenciais encadeadas 
 
 
- Inicialização da lista; - Acesso ao último elemento da lista; 
 
- Inserção com a lista vazia e não vazia; - Verificação de lista vazia ou cheia; 
 
- Inserção antes ou após o registro x; - Eliminação de elementos da lista; 
 
- Acesso ao primeiro elemento da lista; - Qtde de elementos da lista. 
 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
 
1) Inicializar uma lista estática encadeada. 
 
2) Retornar se a lista está vazia. 
 
3) Retornar se a lista está cheia. 
 
4) Inserir um elemento em lista vazia. 
 
5) Obter um nó (posição) da lista. 
 
6) Inserir um elemento em lista não vazia. 
 
7) Retornar o primeiro elemento da lista. 
 
8) Retornar o último elemento da lista. 
 
9) Retornar a quantidade de elementos da lista. 
 
10) Inserir um elemento após o elemento x. 
 
11) Eliminar um elemento da lista. 
 
12) Devolver um nó (posição) disponível para a lista. 
 
 
 
Esboço do T.A.D 
 
L 
A 
 
 
 
Info lig 
 
 
 
Info lig 
 
 
Info lig 
 
 
Info lig 
 
 
Info lig 
 
 
 
prim 
 
dispo 
 
 
 
 
 
1 2 3 ... max N ... 
 
 
9 – ALOCAÇÃO DINÂMICA DE MEMÓRIA 
 
 
9.1 – Ponteiros 
 
 Na alocação estática de memória, conforme já abordamos, há a necessidade de o 
programador fazer uma estimativa prévia da quantidade de memória a ser ocupada pelos dados 
de sua aplicação. Isso se deve porque as estruturas de dados estáticas necessitam ser 
declaradas antes do início do código, sendo assim, chamadas de estruturas pré-referenciadas. A 
partir daí o programador não tem muita flexibilidade para mudar essa situação. 
Em contrapartida, na alocação dinâmica de memória o programador dispõe de estruturas 
de dados pós-referenciadas, criando novos registros sob demanda e necessidade da aplicação, 
ficando limitação apenas em relação à quantidade de memória física disponível no hardware. 
As linguagens de programação modernas tornaram possível explicitar não apenas os 
dados, mas também os endereços desses dados. Isso é possível com a utilização de ponteiros, 
que são variáveis de memória que “apontam” para endereços de memória. Esses endereços de 
memória apontados pelos ponteiros são conhecidos como variáveis dinâmicas. 
 
 Exemplo: 
 
 
 
 
 
 
 
 
 
 A notação introduzida por Wirth para a linguagem de programação Pascal é: 
 
Type 
tp = ^T; 
 
 
Essa declaração expressa que valores do tipo tp são ponteiros para dados do tipo T. 
Portanto, lê-se o símbolo “^” como “ponteiro para”. 
 Valores para ponteiros são gerados quando dados correspondentes a seus tipos são 
alocados/desalocados dinamicamente. Em pascal os procedimentos new() e dispose() existem 
com esse propósito. 
 
Em pseudolinguagem serão adotados os comandos: 
 
 
 ALOCA: cria um ponteiro que automaticamente aponta para um endereço de memória 
existente. Ex: 
 
 ALOCA (p); =DESALOCA: destrói um ponteiro juntamente com a variável dinâmica associada. Ex: 
 
 
 DESALOCA (p); = 
 
2BF57 conteúdo 
p 2BF57 
ponteiro 
endereço 
físico 
variável 
dinâmica 
p variável dinâmica 
p variável dinâmica 
 Exemplo: 
 
 
ALGORITMO EXEMPLO; 
 
TIPO 
 p = ^ caracter; 
VAR 
 nome: p; 
 
INICIO 
 ALOCA (nome); 
 leia (nome^); 
 exiba (nome^); 
 DESALOCA (nome); 
FIM. 
 
 
 
Exercício: Usando os conceitos de ponteiro e variáveis dinâmicas, escreva um algoritmo que 
armazene o nome de um aluno e suas duas notas de prova. Calcule a média das notas e exiba o 
nome e a média. 
 
 
 
9.2 – Listas Dinâmicas 
 
 
 A implementação de listas dinâmicas é feita com o uso de ponteiros e dessa forma o 
trabalho de alocação de memória fica facilitado. É possível então criar registros por meio de 
ponteiros e, conforme a necessidade e a demanda, acrescentando elementos ou eliminando 
posições no arranjo de dados ou lista dinâmica. 
 
 
 
 Operações sobre Listas Dinâmicas 
 
- Criar lista vazia; 
- Inserir o primeiro elemento na lista; 
- Inserir elemento no início da lista; 
- Acessar o primeiro elemento; 
- Acessar o último elemento; 
- Quantidade de elementos da lista; 
- Inserir valor (após determinado elemento ou na posição x); 
- Eliminar elemento (após determinado elemento ou da posição x). 
 
 
 
 Registros com ponteiros 
 
Uma variável do tipo p_rec (por exemplo), aponta para ou é um ponteiro para um registro 
do tipo de dados registro, conforme trecho de declaração da estrutura de dados abaixo: 
 
 
 
TAD (Tipo Abstrato de Dados) 
 
TIPO 
 p_rec = ^rec; 
 
 Lista = p_rec; 
 
 rec = REGISTRO 
 info: T; 
 lig: Lista; 
 Fim; 
VAR 
 L: Lista; 
 
 
Obs: O tipo de dados ponteiro é o único tipo que pré-referencia outro tipo em Pascal. 
 
 
Um ponteiro do tipo “Lista” (definido na estrutura acima) pode assumir o conjunto de 
valores que corresponde a endereços reais de memória para os campos “info” e “lig”. 
Exemplo: 
 
 
 
 
 
Onde o conteúdo de P corresponde ao endereço do objeto (conjunto de campos info e lig). 
Esses endereços são as ligações das listas encadeadas dinâmicas. 
 
 
 
 Referências – Sintaxe 
 
 
- O acesso ao registro depende do tipo de alocação adotada. Se utilizar alocação em vetor, 
referencia-se como: L.A[p]; e se a alocação for dinâmica, referencia-se como: p^. 
 
 
- Para referenciar ponteiro, objeto e campo, as sintaxes são: 
 
 - ponteiro: p 
 
 - objeto: p^ 
 
 - campos: p^.info 
 p^.lig 
 
 
- Para referenciar e controlar a informação sobre fim da lista ou lista vazia, também se deve 
utilizar o valor 0 (zero), também conhecido como endereço nulo ou terra para esse fim. 
 
Obs: A linguagem de programação Pascal possui uma constante pré-definida para denotar 
esse endereço nulo chamada “nil”. 
 
 
P 
objeto endereço 
Info lig 
( ) 
 Ponteiro X Objeto apontado 
 
 
Ex: 
 a) p  q; (ponteiros) 
 
 
 b) p^  q^; (conteúdo dos registros apontados pelos ponteiros) 
 
 
 
 
Ex: 
 Situação Inicial 
 
 
 
 
 
 
 
 
 
 
 a) p  q; 
 
 
 
 
 
 
 
 
 
 
 b) p^.lig  q^.lig; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Kátia Mário Rose 
Bruna Daniel Silvia 
Bruna Daniel Silvia 
Kátia Mário Rose 
Bruna Daniel Silvia 
p 
q 
p q 
p 
q 
 Manipulação de Registros 
 
1) Criação de um registro 
 
 
ALOCA (p); 
 
 
Substitui o procedimento Obter_No (j), utilizado em listas estáticas encadeadas, dada uma 
variável do tipo ponteiro para tipo ^rec. 
 
 
- Efetivamente aloca uma variável do tipo rec; 
- Gera um ponteiro ^rec apontado para aquela variável; 
- Atribui o ponteiro à variável p. 
 
A partir daí: 
 
- O ponteiro pode ser referenciado como p; 
- A variável referenciada por p é denotada por p^. 
 
 
2) Liberação de um registro 
 
 
DESALOCA (p); 
 
 
Substitui o procedimento Devolver_No (j). 
 
- Esta operação libera o espaço apontado por p; 
- p passa a ter valor indefinido. 
 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
1) Criar uma lista. 
 
2) Retornar se a lista está ou não vazia. 
 
3) Inserir o primeiro elemento na lista. 
 
4) Inserir um elemento no início da lista. 
 
5) Inserir um elemento no final da lista. 
 
6) Retornar o primeiro elemento da lista. 
 
7) Retornar o último elemento da lista. 
 
8) Retornar a quantidade de elementos da lista. 
 
9) Inserir um elemento após outro na lista. 
 
10) Inserir um elemento na posição “x” da lista. 
 
11) Eliminar o primeiro elemento da lista. 
 
12) Eliminar o último elemento da lista. 
 
13) Eliminar o elemento da posição “x” da lista. 
p 
Info lig 
p 
Info lig 
Exercícios 
 
 
1) Diferencie Alocação Estática de Memória de Alocação Dinâmica de Memória. 
 
 
2) Explique o que são ponteiros. 
 
 
3) O que são listas? Explique e dê exemplos. 
 
 
4) Defina, sintaticamente: 
 
a) ponteiro 
 
b) objeto 
 
c) campo 
 
 
5) Explique os seguintes comandos de atribuição: 
 
a) p^  q^; 
 
b) p  p^.lig; 
 
c) p  q; 
 
 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
10 – PILHAS 
 
 
 Pilhas são listas onde as inserções de novos elementos ou as eliminações de elementos já 
armazenados se dão em uma única extremidade da lista: no topo. 
 Pilhas também são conhecidas como Listas LIFO (Last In First Out – Último que Entra, 
Primeiro que Sai), ou seja, o último elemento inserido é o primeiro a ser acessado, lido, excluído, 
processado. 
 
 
 
Pilha Vazia 
 
 
 
 
Insere (A) A 
 
 
 
 
Insere (B) A B 
 
 
 
 
Remove (B) A B 
 
 
 
 
Insere (C) A C 
 
 
 
 
 
 
10.1 Operações sobre Pilhas 
 
 
- Criar (P): cria uma pilha vazia; 
- Inserir (x, P): insere x no topo da pilha P. Também conhecida como empilha (ou push); 
- Vazia (P): testa se a pilha está vazia; 
- Topo (P): acessa o elemento do topo da pilha; 
- Remove (P): elimina um elemento da pilha P. Conhecida como desempilha (ou pop). 
 
 
 
 
 
 
 
topo 
topo 
topo 
topo 
topo 
10.2 Aplicações de Pilhas 
 
Exemplo: Chamadas de Rotinas 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Quando a rotina R1 é executada ela efetua uma chamada a rotina R2, que deve carregar 
consigo o endereço de retorno e1. Ao término de R2 o processamento deve retornar a 
rotina R1 no devido endereço. Situação idêntica ocorre em R2 e R3. 
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 operacional para controle na execução de 
programas. Obs: e0 é o endereço de retorno de R1. 
 
 
 
10.3 Implementação de Pilhas 
 
 
Como implementar uma pilha? 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 dos deslocamentos necessários quando da 
inserção ou eliminação dos elementos. 
No caso de pilhas, essas operações de deslocamentos não ocorrem. Portanto, pode-se 
afirmar que a alocação sequencial é mais vantajosa na maioria das vezes. 
 
 
 
10.4 Alocação Sequencial de Pilhas 
 
 
TAD (Tipo Abstrato de Dados) 
CONST 
 max_pilha = ----; 
 
TIPO 
 indice = 0..max_pilha; 
 
 Pilha = VETOR [1..max_pilha] de T; 
 
VAR 
 P: Pilha; 
 topo: indice; 
rotina R1; 
 
 
 
 R2; 
e1 
 
 
fim; 
rotina R2; 
 
 
 
 R3; 
e2 
 
 
fim; 
rotina R3; 
 
 
 
 R4; 
e3 
 
 
fim; 
rotina R4; 
 
 
 
 
 
 
 
fim; 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
 
1) Criar uma pilha. 
 
2) Retornar se a pilha está vazia. 
 
3) Retornar se a pilha está cheia. 
 
4) Inserir um elemento na pilha (empilhar). 
 
5) Acessar elemento da pilha. 
 
6) Eliminarelemento da pilha. 
 
7) Acessar elemento da pilha e eliminá-lo em seguida (desempilhar). 
 
 
 
 
 
 
 
 
 
 
 
 
10.5 Alocação Dinâmica de Pilhas 
 
 
TAD (Tipo Abstrato de Dados) 
TIPO 
 pont = ^reg_pilha; 
 
 Pilha = pont; 
 
 reg_pilha = REGISTRO 
 info: T; 
 lig: pont; 
 FIM; 
VAR 
 P: Pilha; 
 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
 
1) Criar uma pilha. 
 
2) Retornar se a pilha está vazia. 
 
3) Empilhar um elemento. 
 
4) Acessar a pilha. 
 
5) Eliminar elemento da pilha. 
 
6) Desempilhar elemento. 
 
 
 
 
 
 
 
 
 
 
 
11 – FILAS 
 
 
 Filas são listas em que as inserções de novos elementos são feitas numa extremidade da 
lista e as eliminações na outra.Filas também são conhecidas como Listas FIFO (First In First Out 
– Primeiro que Entra, Primeiro que Sai), ou seja, o primeiro elemento inserido é o primeiro a ser 
acessado, lido, excluído, processado. 
 
 
( a1, a2, a3, ..., an -1, an ) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11.1 Operações sobre Filas 
 
- Criar (F) – cria uma fila vazia; 
- Inserir (x, F) – insere x no final da fila; 
- Vazia (F) – testa se a fila esta vazia; 
- Primeiro (F) – acessa o elemento do inicio da fila; 
- Ultimo (F) – acessa o elemento do final da fila; 
- Elimina (F) – elimina o elemento do inicio da fila. 
 
 
 
11.2 Aplicações de Filas 
 
Exemplo: Escalonamento de jobs (fila de processos aguardando recursos do S.O.). 
 
 
 
 
11.3 Implementação de Filas 
 
Como implementar uma fila? Como lista sequencial ou encadeada? Estática ou Dinâmica? 
Só tem sentido falar em fila sequencial estática ou fila 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. 
 
 
Fila 
Eliminações 
no Início 
Inserções 
no Final 
Começo Final 
11.4 Alocação Estática Sequencial de Filas 
 
 
TAD (Tipo Abstrato de Dados) 
CONST 
 max_fila = ----; 
 
TIPO 
 indice = 0..max_fila; 
 
 Fila = VETOR [1..max_fila] de T; 
 
VAR 
 F: Fila; 
 Comeco, {posição anterior ao primeiro elemento} 
Final: indice; {posição do último elemento} 
 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
 
1) Criar uma fila. 
 
2) Retornar se a fila está vazia. 
 
3) Retornar se a fila está cheia. 
 
4) Inserir um elemento na fila. 
 
5) Acessar o primeiro elemento da fila. 
 
6) Acessar o último elemento da fila. 
 
7) Eliminar elemento da fila. 
 
 
 
 Problemas na Alocação Estática Sequencial de Filas 
 
 
O que aconteceria com a fila considerando a seguinte sequência de operações? I, E, I, E, I, 
E, I, E. Legenda: I – Inclusão; E – Exclusão. 
 
Resp.  A fila terá sempre um elemento (ou nenhum), e no entanto, num certo 
momento: 
 
 
 
 
 
 
 
 
 
Fila 
Começo 
Final 
 Ou seja, apenas um elemento (ou nenhum) na fila, ocupando a última posição do 
vetor. Na próxima inserção ocorrerá uma condição de overflow e na verdade a fila está 
vazia! 
 
 
Exercício: Implemente uma solução para resolver o problema. 
 
 
Solução: Na rotina de eliminação, após a atualização da variável Comeco, verificar se a fila 
ficou vazia, isto é, se Comeco = Final. Neste caso, reinicializar: Comeco e Final  0. 
 
 
Procedimento ELIMINA (var Comeco, Final: indice); 
Inicio 
 se (VAZIA = falso) 
 entao Comeco  Comeco + 1; 
 se (Comeco = Final) 
 entao Comeco  0; 
 Final  0; 
 fim se; 
 fim se; 
Fim; 
 
 
E o que aconteceria com a fila se a sequência de operações fosse: I, I, E, I, E, I, E, I, E, I? 
 
Resp.:  A fila estaria com no máximo dois elementos e ainda assim ocorreria 
overflow com a fila quase vazia. 
 
 
 
Alternativa: Forçar Final a usar o espaço liberado por Comeco, implementando o que se 
conhece por Fila Circular! 
 
 
 
11.5 Fila Circular 
 
Fila Circular implementada como um Anel. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Começo 
Final 
Condições: 
 
 
- Índices do vetor: 0..max_fila - 1; 
 
- Variáveis de controle: comeco e final; 
 
- Inicialmente: comeco = final = 0; 
 
- Quando Final = max_fila - 1, o próximo elemento será inserido na posição 0 (se essa 
posição estiver vazia!); 
 
- Condição de fila vazia: Comeco = Final. 
 
 
 
 
T.A.D. 
 
 TIPO 
indice = 0..max_fila - 1; 
 
Fila = VETOR [0..max_fila -1] de T; 
 
 VAR 
 F: Fila; 
 Comeco, Final: indice; 
 
 
 
 
Procedimento INSERE (var F: Fila; var Final: indice; Comeco: indice; valor: T); 
Inicio 
 se ( (Final + 1) MOD max_fila = Comeco) ) 
 entao exiba (“Fila Cheia!”) 
 senao 
 Final  (Final + 1) MOD max_fila; 
 F [Final]  valor; 
 fim se; 
Fim; 
 
 
 
Procedimento ELIMINA (var Comeco: indice); 
Inicio 
 Comeco  (Comeco + 1) MOD max_fila; 
Fim; 
 
 
 
 
 
 
11.6 Alocação Dinâmica de Filas 
 
 
TAD (Tipo Abstrato de Dados) 
 
 TIPO 
pont = ^reg_fila; 
 
Fila = pont; 
 
reg_fila = REGISTRO 
 info: T; 
 lig: pont; 
 FIM; 
 VAR 
 Comeco, Final: Fila; 
 
 
 
Exercícios – Escreva, com base no TAD apresentado, as rotinas para as respectivas operações: 
 
 
1) Criar uma fila. 
 
2) Retornar se a fila está vazia. 
 
3) Inserir o primeiro elemento na fila. 
 
4) Inserir um elemento na fila. 
 
5) Retornar o primeiro elemento da fila. 
 
6) Retornar o último elemento da fila. 
 
7) Eliminar elemento da fila. 
 
 
 
 
 
12 – ESPALHAMENTO (HASHING) 
 
 
• Técnica eficiente para armazenamento e recuperação de dados; 
 
• Vantagem: não requer ordenação dos dados. 
 
 
12.1 Fundamentos 
 
• Chama-se espalhamento (ou hashing) de um conjunto C a sua divisão em um número finito 
de partes: C1, C2,..., Cn, para n>1, tal que: 
 
• C1 ᴗ C2 ᴗ ... ᴗ Cn = C, ou seja, todo elemento de C ocorre em uma dessas partes; 
 
• Ci ∩ Cj = Ø, para 1 ≤ i < j ≤ n, isto é, nenhum elemento de C ocorre em mais de uma 
dessas partes; 
 
• Tais propriedades garantem que em um espalhamento de um conjunto C em n partes, 
nenhum elemento seja perdido ou duplicado; 
 
• A distribuição unívoca dos elementos de C em n partes, sugere a existência de uma função 
h: [1..n], denominada função de espalhamento, que mapeia cada elemento de C à sua 
respectiva parte Ci, isto é: x Є C x Є C h(x); 
 
• Caso um espalhamento efetuado por uma função h e o resultado da diferença absoluta 
entre os tamanhos de duas partes quaisquer seja no máximo 1, diz-se que essa função h é 
ótima; 
 
• Exemplo: 
 
Sejam o conjunto C = {a,b,c,d,e} e h uma função de espalhamento h: C [1..3] que 
resulte nos seguintes valores para os elementos de C: 
 
h(a) = 2 
h(b) = 1 
h(c) = 3 
h(d) = 3 
h(e) = 1 
 
Então, por h, os elementos de C serão distribuídos da seguinte forma: 
 
C1 = {b,e} 
C2 = {a} 
C3 = {c,d} 
 
 
• Como a diferença absoluta entre os tamanhos das partes de C geradas pela função h é de 
no máximo 1, pode-se dizer que essa função é ótima para esse espalhamento; 
 
• Como todas as partes de C possuem aproximadamente o mesmo tamanho, diz-se que o 
espalhamento é uniforme, ou seja, a menor parte possui (|C| div n) elementos e a maior 
parte possui (|C| div n) + 1 elementos; 
 
• Considerando o espalhamento de um conjunto C, por uma função ótima (h: C [1..|C|]), 
isto é, o número de partes é igual ao número de elementos do conjunto C, e que o 
espalhamento é uniforme (h é ótima!), cada parte terá exatamente um elemento do 
conjunto C, e aí se diz que o espalhamento é perfeito; 
 
• Na prática é muito difícil de se obter espalhamentos perfeitos. Geralmente, ao menos uma 
das partes é vazia ou possui mais de um elemento (colisão); 
 
• Aplicações de Espalhamento 
• Consultas; 
• Transformação de elementos alfanuméricos; 
• Tratamento de permutações. 
 
• Considere x Є C e o valor h (x) que possibilita acesso direto na parte de C que contém x. 
Assim, caso C seja um arranjo a ser consultado, um espalhamento permitirá um processo 
de busca muito eficiente, pois essa busca estará restritaa uma pequena parte do conjunto 
C; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Espalhamento  técnica de redução do espaço de busca. Quando o tamanho das partes 
diminui, a eficiência da busca aumenta. Na situação extrema do espalhamento perfeito, o 
valor h (x) permite acesso direto à posição de x, tornando-se o mais eficiente método de 
busca existente. 
 
 
12.2 Funções de Espalhamento 
 
• Mapeia cada elemento de um conjunto em um endereço; 
 
• Situação ideal: n elementos distintos  n endereços distintos; 
 
• Existem n! modos de se fazer esse mapeamento ideal; 
 
• Existem nn maneiras de mapear n elementos a n endereços; 
 
• Probabilidade espalhamento perfeito: mínima! (n!/nn); 
 
• Contente-se com funções de mapeamentos razoáveis (distribuições de elementos 
medianamente uniformes em endereços); 
 
• Já foi dispendido muito esforço para se criar funções de espalhamentos eficientes. 
Paradoxalmente, um dos métodos mais simples (divisão) é o que vem apresentando os 
melhores resultados na prática. 
 
x = “João” 
Antônio 
 Pietra 
João 
 Carla 
Martin 
C 
Busca sem espalhamento 
C
3
 
x = “João” 
h(x) = 2 
Antônio 
 Pietra 
 
 João 
 Carla 
 
Martin 
C
2
 
C
1
 
Busca com espalhamento 
Antônio 
 
 Pietra 
 
 João 
 
 Carla 
 
Martin 
x = “João” 
h(x) = 3 
C
1
 
C
2
 
C
3
 
C
4
 
C
5
 
Espalhamento perfeito 
• Método da Divisão 
 
• Indicado para C como subconjunto de N; 
 
• Efetua-se uma divisão por n, considere o resto e soma-se 1; 
 
• Exemplo: 
 
Para n = 3 e C = {9, 12, 22, 35, 47, 51}, tem-se os seguintes valores para h: 
 
h (9) = ( 9 mod 3) + 1 = 1 
h (12) = (12 mod 3) + 1 = 1 
h (22) = (22 mod 3) + 1 = 2 
h (35) = (35 mod 3) + 1 = 3 
h (47) = (47 mod 3) + 1 = 3 
h (51) = (51 mod 3) + 1 = 1 
 
• Portanto: 
 
C1 = {9, 12, 51} 
C2 = {22} 
C3 = {35,47} 
 
 
• Transformação de Elementos Alfanuméricos 
 
• Com elementos alfanuméricos o método da divisão não pode ser usado direto; 
• Devem, antes, serem convertidos em valores numéricos; 
• Dica: somar o código ASCII de cada caracter do elemento; 
• Exemplo em Pascal: 
 
function h (x: string): integer; 
var i, s: integer; 
begin 
 s := 0; 
 for i := 1 to length (x) do 
 s := s + ord (x[i]); 
 h := (s mod n) + 1; 
end; 
 
 
• Considere: 
 
 n = 7 e C = {Bia, Décio, Edu, Lucy, Neusa, Rose, Sueli, Thais, Yara} 
 
• Tem-se: 
 
h (“Bia”) = 3 Portanto: 
h (“Décio”) = 2 
h (“Edu”) = 7 C1 = {Lucy} 
h (“Lucy”) = 1 C2 = {Décio, Thais} 
h (“Neusa”) = 5 C3 = {Bia} 
h (“Rose”) = 4 C4 = {Rose, Sueli} 
h (“Sueli”) = 4 C5 = {Neusa} 
h (“Thais”) = 2 C6 = {Yara} 
h (“Yara”) = 6 C7 = {Edu} 
 
12.3 Tabelas de Espalhamento 
 
 
• Estruturas de dados que permitem a implementação do espalhamento de um conjunto C 
em aplicações computacionais; 
 
 
• Representada por um vetor onde cada posição (encaixe), mantém uma parte de C; 
 
 
• Evidente: número de encaixes coincide com o número de partes criadas pela função de 
espalhamento; 
 
 
• Se admitir a existência de elementos sinônimos em C, espera-se a ocorrência de pelo 
menos uma colisão (necessidade de armazenar um elemento em uma posição já ocupada); 
 
 
• Solução: tratamento de colisão por espalhamento externo; 
 
 
• Princípio de que existirão muitas colisões na inserção dos elementos numa tabela; 
 
 
• Ao invés de armazenar só um elemento, cada encaixe T[i] guardará uma coleção de 
elementos sinônimos. Como a quantidade destes pode variar bastante, recomenda-se o 
uso de lista encadeada; 
 
 
• Assim, uma tabela de espalhamento externo será um vetor de listas encadeadas, cada 
uma delas uma parte de C; 
 
 
• O termo “externo” se dá em função dos elementos serem armazenados fora da tabela de 
espalhamento (área de memória alocada de modo dinâmico). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 
2 
3 
4 
5 
23 62 
8 14 
11 51 37 
34 83 59 
8 14 
• Tipo Abstrato de Dados (TAD) 
 
 Const 
 n = 5; 
 Tipo 
 Lista = ^rec; 
 rec = REGISTRO 
 info: T; 
 lig: Lista; 
 FIM; 
 Tab_Esp = VETOR [1..n] de Lista; 
 Var 
 TE: Tab_Esp; 
 
 
• Operações Básicas com Tabelas de Espalhamento 
 
Inicialização da Tabela 
 
Procedimento INICIALIZA_TABELA (var TE: Tab_Esp); 
 var 
 i: integer; 
 Inicio 
 para i  1 to n faca 
 CRIAR_LISTA (TE[i]); 
 fim para; 
 Fim; 
 
Inserção na Tabela 
 
Procedimento INSERE_TABELA (var TE: Tab_Esp; valor: T); 
Inicio 
 se (L = 0) 
 entao INSERE_PRIMEIRO_ELEMENTO (TE [ h(valor) ], valor: T ) 
 senao INSERE_INICIO_LISTA (TE [ h(valor) ], valor: T ); 
 fim se; 
Fim; 
 
Eliminação de elemento da Tabela 
 
Procedimento ELIMINA_ELEMENTO (var L: Lista; valor: T); {a lista deve estar ordenada} 
var n, p: Lista; 
Inicio 
 se (valor = L^.info) 
 entao n  L; 
 L  L^.lig; 
 DESALOCA (n); 
 senao p  L; 
 enquanto (p^.lig <> 0) E (valor > p^.lig^.info) faca 
 p  p^.lig; 
 fim enquanto; 
 n  p^.lig; 
 p^.lig  n^.lig; 
 DESALOCA (n); 
 fim se; 
Fim; 
 
Procedimento ELIMINA_ELEMENTO_TABELA (var TE: Tab_Esp; valor: T); 
Inicio 
 ELIMINA_ELEMENTO (TE [ h (valor) ], valor: T ); 
Fim; 
13 – RECURSIVIDADE 
 
 
• Método que possibilita a solução de um problema P a partir das soluções de subproblemas 
de P e que são semelhantes ao próprio P; 
 
• Decompõe-se P até a obtenção de subproblemas simples que possam ser resolvidos 
diretamente sem ser preciso novas decomposições (triviais); 
 
• Os resultados obtidos compõem a solução do problema original; 
 
• Considere P(i) um algoritmo que resolve o problema P com entrada i. Diz-se que P(i) é uma 
instância de P. Sendo P(i) e P(i’) duas instâncias de P, denota-se P(i’) < P(i) indicando 
que P(i’) é mais simples que P(i); 
 
• Podendo uma instância ser decomposta em outra mais simples, diz-se que ela é não 
trivial e pode ser reduzida. Quando uma instância não pode ser reduzida ela é 
denominada trivial; 
 
 
 
 
• Um algoritmo recursivo é composto de duas partes de destaque: 
 
• base de recursão (resolve instâncias triviais diretamente); 
 
• passo de recursão (resolve instâncias não triviais recursivamente); 
 
 
13.1 Implementação de Recursão 
 
• Exemplo: Cálculo de fatorial 
 
• Def.: 
 1 para n = 0 
 
 n...3.2.1 para n > 0 
 
 
 
• Tomando por exemplo: a instância 3! é mais simples que a instância 4!, pois 3! necessita 
de uma multiplicação a menos que 4!; 
 
• Como 0 é o menor número natural, a instância 0! não pode mais ser reduzida à outra 
instância mais simples (:. é trivial); 
n! = 
• Classificadas as instâncias do problema fatorial em triviais e não triviais, pode-se resolvê-
las aplicando as seguintes regras: 
 
• Base de recursão: para n=0, a instância n! é trivial e sua solução é 1; 
 
• Passo de recursão: para n>0, a instância n! é não trivial e sua solução é n.(n-1)!. 
 
 
 
 
 
Pseudocódigo 
 
Funcao fat (n: inteiro): inteiro; 
Inicio 
 se (n = 0) 
 entao fat  1 
 senao fat  n * fat (n – 1); 
Fim; 
 
 
Simulação da execução de fat(4) usando substituições sucessivas 
 
 
 
 
 
 
 
 
Outro modo de simular a dinâmica de uma função recursiva 
 
 
fat(4) = 4 * fat(3) = 4 * 3 * fat(2) = 4 * 3 * 2 * fat(1) = 4 * 3 * 2 * 1 * fat(0) = 4 * 3 * 2 * 1 *1 
Substituições sucessivas efetuadas para alcançar uma instância trivial Instância 
não trivial 
Solução 
obtida 
24 = 
 
 
• Para cada chamada recursiva, reduz-se uma instância não trivial em outra mais simples e a 
operação de multiplicação fica pendente, esperando a propagação da resolução da 
instância mais simples; 
 
• Considera-se que a função que chama fica congelada, esperando a finalização da 
chamada recursiva para a continuidade da execução; 
 
• Isso é possível porque há o empilhamento do endereço de retorno da função que faz a 
chamada,da qual a execução deve seguir na instrução que faz o cálculo da multiplicação; 
 
• Ao se obter a instância trivial, as chamadas “congeladas” são reativadas em uma ordem 
inversa daquela em que ocorreram; 
 
• Por essa razão a base de recursão de uma função recursiva é tão importante!; 
 
• Sem ela, o circuito cíclico das chamadas recursivas nunca será finalizado, gerando o que é 
conhecido como stack overflow, ou seja, um erro que causa o estouro da pilha que controla 
o fluxo de execução da função. 
 
Outros exemplos usando recursão 
 
Cálculo de Potência 
 
 As regras utilizadas para determinar as instâncias do problema da potenciação são: 
 
 Base de recursão: se n = 0, a instância xn é trivial e sua solução é 1; 
 Passo de recursão: se n > 0, a instância xn é não trivial e sua solução é x.xn-1. 
 
 
 
 
 
 
 
 
 
 
 
 
2
3
 
8 
4 
*2 
2
2
 
Caso geral 
*n 
x
n - 1
 x
n - 1
 
x.x
n - 1
 
x
n
 
Caso particular 
Pseudocódigo 
 
Funcao potencia (x: real; n: inteiro): real; 
Inicio 
 se (n = 0) 
 entao potencia  1 
 senao potencia  x * potencia (x, n-1); 
Fim; 
 
 
13.2 Recursão Degenerada 
 
• Os aspectos de simplicidade e legibilidade se apresentam como principais benefícios da 
técnica de recursão; 
 
• Entretanto, existem dois casos em que tais benefícios não são alcançados: 
 
 Recursão de Cauda; 
 Recursão Redundante. 
 
Recursão de Cauda 
 
• Ocorre quando existe uma única chamada recursiva no final de uma rotina. Assim, 
nenhuma instrução dessa rotina fica pendente de ser executada depois de terminar a 
execução dessa chamada recursiva; 
 
• Portanto, o único objetivo dessa recursão (cauda) é a criação de um looping, o qual 
pode ser mais eficientemente implementado por um comando iterativo. 
 
Funcao SOMA (n1, n2: inteiro): inteiro; 
Inicio 
 se (n1 = 0) 
 entao SOMA  n2 
 senao SOMA  SOMA (pred (n1), succ (n2) ); 
Fim; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Execução da chamada recursiva SOMA (3,4) 
SOMA(3,4) 7 
SOMA(2,5) 
SOMA(1,6) 
SOMA(0,7) 
7 
7 
7 
• A utilização de recursão deixa essa execução mais custosa, pois cada chamada 
recursiva necessita da alocação de variáveis locais para armazenar os parâmetros n1 e 
n2, e também empilhar o endereço de retorno para a função que realiza a chamada; 
 
• Conclui-se que é mais eficiente substituir essa recursão por um laço iterativo. 
 
 
Funcao SOMA (n1, n2: inteiro): inteiro; 
Inicio 
 Enquanto (n1 > 0) faca 
 n1  pred (n1); 
 n2  succ (n2); 
 Fim Enquanto; 
 SOMA  n2; 
Fim; 
 
 
Recursão Redundante 
 
• Outro exemplo no qual uma solução iterativa é mais vantajosa que uma recursiva são 
os casos em que ao decompor o problema resultam inúmeros subproblemas iguais (por 
isso, recursão redundante!); 
 
• Exemplo: sequência de Fibonacci (1, 1, 2, 3, 5, 8, 13, ...). 
 
 
Funcao FIBO (n: inteiro): inteiro; 
Inicio 
 se (n < 3) 
 entao FIBO  1 
 senao FIBO  FIBO (n - 2) + FIBO (n - 1); 
Fim; 
 
 
 
 
 
 
Solução iterativa em substituição à função recursiva para cálculo de Fibonacci 
 
Funcao FIBO (n: inteiro): inteiro; 
var 
 i, a, b, c: inteiro; 
Inicio 
 a  1; 
 b  0; 
 para i  1 ate n faca 
 c  a + b; 
 a  b; 
 b  c; 
 fim para; 
 FIBO  c; 
Fim; 
 
 
13.3 Eliminação de Recursão 
 
• O controle do fluxo entre chamadas/retornos de rotinas é realizado por uma pilha 
administrada pelo SO que vai empilhando endereços de retorno e as variáveis locais; 
 
• Desse modo, usando instruções iterativas e pilhas, podemos converter qualquer rotina 
recursiva em uma rotina iterativa; 
 
• Em geral, rotinas iterativas são mais rápidas que rotinas recursivas; 
 
• No entanto, caso haja uma quantidade muito grande de instruções iterativas e muitas pilhas 
para converter recursão em iteração, talvez seja melhor ficar com a versão recursiva 
mesmo; 
 
• Um programa com código simples e claro é mais vantajoso que outro que execute apenas 
ligeiramente mais rápido; 
 
• Quando uma chamada recursiva é executada, o endereço de retorno e todas as variáveis 
locais precisam ser recriadas na pilha; 
 
• Exemplo: chamada recursiva de fat(4). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Ao ser executada, a variável n é criada no topo da pilha com o valor passado no momento 
da chamada. Ao terminar, a última cópia de n criada é destruída. Desse modo, em 
qualquer instante da execução o valor de n será o que estiver no topo da pilha. 
 
 
Relação entre Recursão e a estrutura de Pilha 
 
• Para melhor compreensão da relação entre recursividade e manipulação de pilhas, observe 
o procedimento recursivo abaixo, o qual exibe os itens de uma lista ordenada em ordem 
inversa. 
Fat (4) 
4 
n 
Fat (3) 
3 
4 
n 
Fat (2) 
3 
2 
4 
n 
Fat (1) 
3 
2 
1 
4 
Fat (0) 
3 
2 
1 
0 
4 n 
n 
 
 
Procedimento Exibe_Itens (L: lst_ord); 
Inicio 
 se (nao VAZIA (L) ) 
 entao 
 Exibe_Itens (restante (L) ); 
 exiba (primeiro (L) ); 
 fim se; 
Fim; 
 
 
 
 
 
• Para a exibição dos itens de uma lista em ordem inversa o algoritmo deve exibir o resto 
dessa lista em ordem inversa e, por último, exibir o primeiro item; 
 
• Para cada chamada recursiva ( Exibe_Itens (L) ) uma cópia da variável L é criada para 
manter o endereço do próximo bloco dessa lista; 
 
• Durante as etapas de execução os endereços dos blocos vão sendo empilhados até a lista 
ficar vazia, momento em que se retorna o controle para a instrução exiba ( primeiro (L) ), a 
qual vai exibir os itens da lista, do último para o primeiro (ordem inversa); 
 
• Nota-se, nesse caso, que o único objetivo desse procedimento recursivo é o de simular 
uma pilha onde os endereços dos blocos da lista precisam esperar o momento para os 
itens serem exibidos; 
 
• Assim, com o uso de uma pilha, pode-se substituir o procedimento recursivo por uma 
versão iterativa equivalente, conforme o código a seguir. 
 
 
Procedimento Exibe_Itens (L: lst_ord); 
 
var 
 P: Pilha; 
 
Inicio 
 
 CRIA (P); 
 
 Enquanto (nao VAZIA (L) ) faca 
 EMPILHA (primeiro (L), P ); 
 L  resto (L); 
 Fim Enquanto; 
 
 Enquanto (nao VAZIA (P) ) faca 
 exiba (DESEMPILHA (P) ); 
 Fim Enquanto; 
 
Fim; 
 
 
 
Funcao restante (L: Lista): Lista; 
Inicio 
 restante  L^.lig; 
Fim; 
 
 
 
Funcao primeiro (L: Lista): T; 
Inicio 
 primeiro  L^.info; 
Fim; 
 
 
 
Etapa de reduções 
Etapa de propagação 
14 – ÁRVORES 
 
 
• Árvores são estruturas de dados que permitem organizar dados de modo hierárquico. 
 
 
14.1 Fundamentos 
 
• Uma árvore A é uma estrutura composta por n nós, para n ≥ 0; 
 
• Para n = 0, diz-se que a árvore A é vazia; Senão: 
 
 há um nó especial em A chamado de raiz; 
 
 os outros nós de A são organizados em A1, A2, ..., Ak estruturas de árvores 
disjuntas, denominadas de subárvores de A. 
 
• Por definição, árvores são estruturas recursivas, isto é, caso a raiz de uma árvore 
seja removida, tem-se uma coleção de árvores; 
 
• Cada nó de uma árvore é raiz de alguma subárvore; 
 
• Representação gráfica de uma árvore 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
• Nó pai e nó filho; 
 
• A raiz (principal) de uma árvore é o único nó que não tem pai; 
 
• A quantidade de filhos de um nó é denominada grau, assim como um nó que tenha 
grau 0 é denominado folha; 
 
• O grau de uma árvore é o máximo entre os graus de seus nós; 
 
• A altura de uma árvore é o máximo dos níveis de seus nós; 
 
• Por definição, uma árvore vazia possui altura 0; 
 
• Árvores são usadas para representar dados e informações com necessidade de 
organização de modo hierárquico. Exemplos: árvores genealógicas, árvores 
gramaticais, árvores taxonômicas, entre outros; 
A 
B C 
D F E 
G 
• Na área de sistemas operacionais são úteis na representação de arquivos e 
estruturas de diretórios e subdiretórios além de outras aplicações (adiante). 
 
 
14.2 Árvores Binárias 
 
 
 Uma árvore binária é um tipo particular de árvore que possui grau 2 e onde se distingueuma subárvore esquerda de uma subárvore direita; 
 
 Definição do tipo árvore binária 
 
 Tipo 
 arvb = ^bloco_no; 
 bloco_no = registro 
 esq: arvb; 
 info: T; 
 dir: arvb; 
 fim; 
 
 
Operações básicas com árvores binárias 
 
Criação de uma árvore 
 
Funcao NO (e: arvb; valor: T; d: arvb): arvb; 
var 
 A: arvb; 
Inicio 
 Aloca (A); 
 A^.esq  e; 
 A^.info  valor; 
 A^.dir  d; 
 NO  A; 
Fim; 
 
 
Verificação de árvore vazia 
 
Funcao VAZIA (A: arvb): logico; 
Inicio 
 VAZIA  (A = 0); 
Fim; 
 
 
Retorno do item da raiz da árvore 
 
Funcao RAIZ (A: arvb): T; 
Inicio 
 RAIZ  A^.info; 
Fim; 
 
 
 
 
Retorno da subárvore esquerda 
 
Funcao ESQUERDA (A: arvb): arvb; 
Inicio 
 ESQUERDA  A^.esq; 
Fim; 
 
 
Retorno da subárvore direita 
 
Funcao DIREITA (A: arvb): arvb; 
Inicio 
 DIREITA  A^.dir; 
Fim; 
 
 
14.3 Percursos em Árvores Binárias 
 
 Percurso é um modo sistemático de percorrer cada nó de uma árvore exatamente um 
por vez; 
 
 Tipos de percursos: 
 
 Percursos em profundidade; 
 Percursos em largura. 
 
 
• Percursos em Profundidade 
 
 Em-ordem; 
 Pré-ordem; 
 Pós-ordem. 
 
• Percurso em Largura 
 
 Em-nível. 
 
 
Percursos em Profundidade 
 
 Em-ordem: percorre recursivamente a subárvore esquerda, volta a raiz da árvore e, 
por último percorre recursivamente a subárvore direita; 
 
 Pré-ordem: percorre a raiz da árvore e depois percorre recursivamente as 
subárvores esquerda e direita, respectivamente; 
 
 Pós-ordem: percorre recursivamente as subárvoes esquerda e direita, 
respectivamente, e por último, volta a raiz da árvore. 
 
 
 
 
 
 
 
Podemos compreender melhor esses percursos quando comparamos o funcionamento 
destes com as formas infixa, prefixa e posfixa de expressões aritméticas. 
 
 
 
 
 
 
 
 
 
 
 
 
Forma infixa da expressão  Aplica-se o percurso em-ordem 
 
 Exibir a subárvore esquerda; (a) 
 Exibir a raiz; (+) 
 Exibir a subárvore direita; (b) 
 
 
Forma prefixa da expressão  Aplica-se o percurso pre-ordem 
 
 Exibir a raiz; (+) 
 Exibir a subárvore esquerda; (a) 
 Exibir a subárvore direita; (b) 
 
 
Forma posfixa da expressão  Aplica-se o percurso pos-ordem 
 
 Exibir a subárvore esquerda; (a) 
 Exibir a subárvore direita; (b) 
 Exibir a raiz; (+) 
 
 
Com o uso de recursão, podemos generalizar esse raciocínio e desenvolver a forma 
posfixa da expressão abaixo, percorrendo, em pós-ordem, a subárvore esquerda (ab*), depois a 
subárvore direita (cd/) e, finalmente, a raiz (+). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Expressão aritmética a*b + c/d 
representada por uma árvore binária 
+ 
* 
a b 
/ 
c d 
+ 
a b 
Expressão aritmética a + b 
representada por uma árvore 
binária 
Ao final, teremos a expressão: 
 
a b * c d / + 
14.4 Algoritmos dos 3 tipos de percurso em profundidade 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Retorno da subárvore esquerda 
 
Funcao ESQUERDA (A: arvb): arvb; 
Inicio 
 ESQUERDA  A^.esq; 
Fim; 
 
 
Retorno da subárvore direita 
 
Funcao DIREITA (A: arvb): arvb; 
Inicio 
 DIREITA  A^.dir; 
Fim; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Procedimento EM_ORDEM (A: arvb); 
Inicio 
 EM_ORDEM (ESQUERDA (A) ); 
 exiba (RAIZ (A) ); 
 EM_ORDEM (DIREITA (A) ); 
Fim; 
Procedimento PRE_ORDEM (A: arvb); 
Inicio 
 exiba (RAIZ (A) ); 
 PRE_ORDEM (ESQUERDA (A) ); 
 PRE_ORDEM (DIREITA (A) ); 
Fim; 
Procedimento POS_ORDEM (A: arvb); 
Inicio 
 POS_ORDEM (ESQUERDA (A) ); 
 POS_ORDEM (DIREITA (A) ); 
 exiba (RAIZ (A) ); 
Fim; 
Percurso em Largura 
 
 Conhecido por percurso em-nível; 
 
 Percorre-se os nós de uma árvore por nível: 
 
• de cima para baixo; 
 
• da esquerda para a direita. 
 
 Exemplo: na expressão a*b + c/d, teremos: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Na implementação do percurso em largura (em-nível), inicia-se uma fila possuindo só o nó 
da raiz da árvore. Em seguida, enquanto essa fila não ficar vazia, elimina-se dessa um nó, exibe-
se o seu conteúdo e armazena-se seus filhos de volta na mesma. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
+ * / a b c d 
+ 
* 
a b 
/ 
c d 
Procedimento EM_NIVEL (A: arvb); 
var 
 F: Fila; 
Inicio 
 CRIA_FILA (F); 
 ENFILEIRA (A, F); 
 Enquanto (nao VAZIA (F) ) faca 
 A  ELIMINA (F); 
 exiba (RAIZ (A) ); 
 se nao VAZIA (ESQUERDA (A) ) 
 entao ENFILEIRA (ESQUERDA (A), F ); 
 se nao VAZIA (DIREITA (A) ) 
 entao ENFILEIRA (DIREITA (A), F); 
 Fim Enquanto; 
Fim; 
14.5 Árvores de Busca Binária 
 
Considere A como uma árvore binária na qual sua raiz contenha o item r. 
 
Essa árvore A será uma Árvore de Busca Binária (ordenada), se e somente se: 
 
 Todo elemento armazenado na subárvore esquerda de A seja menor ou igual a r; 
 Todo elemento armazenado na subárvore direita de A seja maior que r; 
 Toda subárvore de A seja também uma árvore de busca binária. 
 
Assim, os elementos de uma árvore de busca binária A estarão ordenados de acordo com 
a propriedade de uma busca binária, ou seja, para todo elemento x Є A, quando um elemento y 
está armazenado à esquerda de x, então y < x. Já quando y está armazenado à direita de x, 
então y > x. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Uma observação importante acerca da propriedade de busca binária faz com que 
cheguemos a conclusão de que ao projetar uma árvore de busca binária obteremos uma 
sequência ordenada de todos os seus elementos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ordenada 
c 
b 
a 
f 
e g 
d 
Não Ordenada 
d 
a 
b c 
f 
e g 
4 6 9 
8 
5 
0 1 2 3 4 5 6 7 8 9 
1 
0 2 
3 7 
14.6 Implementação de Árvores de Busca Binária 
 
 O TAD para implementar árvores de busca binária é idêntico ao de árvores binárias; 
 
 Tipo 
 arvbb = ^bloco_no; 
 bloco_no = registro 
 esq: arvbb; 
 info: T; 
 dir: arvbb; 
 fim; 
 
 Esse fato denota que as propriedades da busca binária não são exclusivas dessa estrutura. 
Portanto, suas características devem ser desenvolvidas por meio das operações que farão 
uso dela. 
 
 
Criação e teste de árvore vazia 
 
Procedimento CRIA (var A: arvbb); 
Inicio 
 A  0; 
Fim; 
 
Funcao VAZIA (A: arvbb): logico; 
Inicio 
 VAZIA  (A = 0); 
Fim; 
 
 
Acesso em árvore de busca binária 
 
Funcao RAIZ (A: arvbb): T; 
Inicio 
 se (A = 0) 
 entao exiba (“Árvore binária vazia!”); 
 fim se; 
 RAIZ  A^.info; 
Fim; 
 
Funcao ESQUERDA (A: arvbb): arvbb; 
Inicio 
 se (A = 0) 
 entao exiba (“Árvore binária vazia!”); 
 fim se; 
 ESQUERDA  A^.esq; 
Fim; 
 
Funcao DIREITA (A: arvbb): arvbb; 
Inicio 
 se (A = 0) 
 entao exiba (“Árvore binária vazia!”); 
 fim se; 
 ESQUERDA  A^.dir; 
Fim; 
Inserção em árvore de busca binária 
 
Funcao FOLHA (valor: T); 
var 
 A: arvbb; 
Inicio 
 ALOCA (A); 
 A^.esq  0; 
 A^.info  valor; 
 A^.dir  0; 
 FOLHA  A; 
Fim; 
 
 
Procedimento INSERE (valor: T; var A: arvbb); 
Inicio 
 se ( VAZIA (A) ) 
 entao A  FOLHA (valor) 
 senao se ( valor <= RAIZ (A) ) 
 entao INSERE (valor, A^.esq) 
 senao INSERE (valor, A^.dir); 
 fim se; 
 fim se; 
Fim; 
 
 
Remoção em árvore de busca binária 
 
Funcao SUBSTITUI (var valor: T; var A: arvbb): arvbb; 
Inicio 
 se (A^.dir = 0) 
 entao 
 SUBSTITUI  A; 
 valor  A^.info; 
 A  A^.esq; 
 senao 
 SUBSTITUI  SUBSTITUI (valor, A^.dir); 
 fim se; 
Fim; 
 
 
Procedimento REMOVE (valor: T; var A: arvbb); 
var 
 n: arvbb; 
Inicio 
 se ( VAZIA (A) ) 
 entao Sair; 
 se ( valor = RAIZ (A) ) 
 entao 
 n  A; 
 se ( ESQUERDA (A) = 0 ) 
 entao A  A^.dir 
 senao se ( DIREITA (A) = 0 ) 
 entao A  A^.esq 
 senao n  SUBSTITUI(A^.info, A^.esq); 
 fim se; 
 fim se; 
 DESALOCA (n); 
 senao 
 se ( valor <= RAIZ (A) 
 entao REMOVE (valor, A^.esq) 
 senao REMOVE (valor, A^.dir); 
 fim se; 
 fim se; 
Fim; 
 
 
Busca em árvore de busca binária 
 
Funcao BUSCA (valor: T; A: arvbb): logico; 
Inicio 
 se ( VAZIA (A) ) 
 entao BUSCA  falso 
 senao se ( valor = RAIZ (A) ) 
 entao BUSCA  verdadeiro 
 senao se ( valor < RAIZ (A) ) 
 entao BUSCA  BUSCA (valor, ESQUERDA (A) ) 
 senao BUSCA  BUSCA (valor, DIREITA (A) ); 
 fim se; 
 fim se; 
 fim se; 
Fim; 
 
 
Algumas aplicações de árvores 
 
 Consultas de dados; 
 Avaliação de expressões aritméticas; 
 Geração de índices remissivos; 
 Manipulação de arquivos indexados; 
 Implementação de filas de prioridades. 
 
 
 
 
 
 
 
 
 
 
 
 
 
BIBLIOGRAFIA* 
 
 
 
FORBELLONE, A. L.; EBERSPACHER, H. F. Lógica de programação: a construção de 
algoritmos e estruturas de dados. São Paulo: Prentice Hall, 2005. 
 
 
GUIMARAES, A. e LAGES, N. Algoritmos e estruturas de dados. Rio de Janeiro: LTC, 1994. 
 
 
MANZANO, J. A. Lógica estruturada para programação de computadores. São Paulo: Érica, 
2001. 
 
 
PEREIRA, Silvio do L. Estruturas de dados fundamentais: conceitos e aplicações. 12 ed. São 
Paulo: Érica, 2008. 
 
 
 
* Esta apostila foi elaborada com base nas obras relacionadas neste item.