GRA Estrutura de Dados

Prévia do material em texto

ESTRUTURA DE DADOS
Sandra Rovena Frigeri
APRESENTAÇÃO
Algoritmos são desenvolvidos para resolver problemas, assim expressam 
soluções computacionais que atendem necessidades específicas. Desejável 
que os algoritmos façam um uso eficiênte dos recursos computacionais 
(memória, armazenamento e processamento), para isso, é necessário 
fazer escolhas e implementações adequadas das estruturas de dados. 
Isso é importante, pois a forma como os dados estão organizados durante 
o processamento fazem com que o sistema tenha uma melhor ou pior 
performance. Já, as estruturas de dados definem a organização dos dados 
e as funcionalidades de acesso e manipulação desses. Dessa forma, o 
principal objetivo deste material é apresentar as estruturas de dados mais 
utilizadas no desenvolvimento de programas, descrever sua organização 
de dados, sua lógica de funcionamento e operações de manipulação.
3ESTRUTURA DE DADOS
SUMÁRIO
CENTRO UNIVERSITÁRIO UNIFTEC
Rua Gustavo Ramos Sehbe n.º 107. 
Caxias do Sul/ RS 
REITOR
Claudino José Meneguzzi Júnior
PRÓ-REITORA ACADÊMICA
Débora Frizzo
PRÓ-REITOR ADMINISTRATIVO
Altair Ruzzarin
DIRETORA DE EDUCAÇÃO A DISTÂNCIA (NEAD)
Lígia Futterleib
Desenvolvido pelo Núcleo de Educação a 
Distância (NEAD)
Designer Instrucional 
Sabrina Maciel
Diagramação, Ilustração e Alteração de Imagem
Igor Zattera, Gabriel Olmiro de Castilhos
Revisora
Ana Clara Garcia
APRESENTAÇÃO 2
INTRODUÇÃO 4
PILHAS (STACK) 9
Tipos Abstratos de Dados (TAD) 10
TAD Pilha 13
Implementação do TAD Pilha 17
FILAS (QUEUE) 26
Implementação do TAD fila com Encadeamento 29
LISTAS (LIST) 34
Tipos de Listas 35
Implementação do TAD com lista de encadeamento 36
ÁRVORES (TREE) 45
Árvores Binárias 47
GRAFOS (GRAPH) 61
Definições 63
Representação 66
Menor Caminho 67
MÉTODOS DE ORDENAÇÃO 72
Bubble Sort 73
REFERÊNCIAS 81
4ESTRUTURA DE DADOS
INTRODUÇÃO
“Imagination is more important than knowledge. For knowledge is 
limited, where an imagination embraces the entire world, stimulating 
progress, giving birth to evolution” (Albert Einstein)
Você tem ideia de como são organizados os 
dados dos programas na memória? 
Você já se perguntou como se organizam as 
relações entre os dados? 
A estrutura básica de organização dos dados nos pro-
gramas se efetiva através das variáveis, que são vinculadas 
aos tipos de dados (numérico, alfanumérico, booleano e seus 
derivados). Cada tipo de dado restringe os possíveis valores 
que as variáveis/constantes podem receber, além de determi-
nar as operações que podem ser realizadas sobre esses dados.
Vamos analisar juntos alguns exemplos: 
1. Considere que você tem uma variável numérica (inteira) 
para armazenar a idade de uma pessoa. Você poderá fazer 
operações de soma, subtração, divisão, multiplicação 
com essa variável, pois são operações definidas para o 
tipo de dado inteiro. Além disso, essa variável poderá 
receber somente números inteiros (neste caso, valores 
reais – ponto-f lutuante – não poderão ser atribuídos à 
variável, nem dados alfanuméricos - caracteres).
5ESTRUTURA DE DADOS
2. Agora, se você tiver uma variável alfanumérica para guar-
dar um endereço, as operações permitidas irão concatenar 
strings, buscar um substring, substituir elementos na 
string, enfim, operações definidas para variáveis deste 
tipo. Essa variável pode receber informação textual (letras, 
dígitos numéricos e alguns caracteres especiais).
3. E se você tiver uma variável do tipo booleano para testar 
se o usuário confirmou a opção de compra, esta variável 
poderá receber somente os valores Verdadeiro (true) ou 
Falso (false), bem como as operações, normalmente, res-
tringem-se às operações booleanas (conjunção “e lógico”, 
disjunção “ou lógico”, negação “não lógico”, entre outras).
A capacidade de armazenamento (tamanho), extensão 
dos valores permitidos e operações permitidas para cada tipo 
de dado podem variar de uma linguagem de programação para 
outra. Esses tipos de dados disponibilizados pela linguagem são 
denominados de tipos primitivos. 
Além desses, as linguagens de programação possuem 
estruturas para definir conjuntos de dados. Esses podem ser 
homogêneos, e são representados pelos vetores, os quais são 
conjuntos de dados em que cada elemento possui um índice de 
acesso e todos os elementos possuem o mesmo tipo. Desse modo, 
podemos ter vetores com elementos numéricos, alfanuméricos, 
booleanos e também podendo ser conjuntos. Por exemplo, po-
demos ter vetores de temperaturas, vetores de idades, vetores 
de nomes, vetores de dados de pessoas. 
Os conjuntos de dados também podem ser heterogêneos, 
ou seja, formado por diversos dados e cada dado definido com 
um tipo específico, esses conjuntos são normalmente deno-
minados registros (estruturas). Por exemplo, podemos ter um 
registro com os dados cadastrais de uma pessoa, contendo có-
digo (numérico), nome (alfanumérico), idade (numérico), sexo 
(alfanumérico), entre outros dados.
Nesta disciplina vamos estudar os tipos abstratos de dados, 
que são definidos pelo usuário (programador), utilizando os tipos 
primitivos e estruturas de conjuntos de dados disponibilizados 
pelas linguagens de programação. 
Vamos entender o conceito de estrutura de dados?
Estruturas de dados (Data Structures) é a denominação 
da organização de dados e algoritmos. De modo a otimizar o 
6ESTRUTURA DE DADOS
seu uso, dependendo desses elementos, podemos solucionar de 
forma simples problemas extremamente complexos. Também, 
existem diversos modelos de estruturas de dados, e novos mo-
delos são criados constantemente, pois acompanham a evolução 
dos algoritmos e das linguagens de programação.
Você deve estar se perguntando em quais situações precisará 
utilizar estruturas de dados!
Na verdade, todos os programas possuem estruturas de 
dados, mesmo que sejam variáveis simples! A seguir, vamos 
analisar alguns exemplos de situações que exigem estruturas 
de dados específicas!
 
Considere que você precisa organizar um fichário com 
dados de clientes. A forma mais prática seria manter as fichas 
em ordem alfabética, pois facilitará a localização. As operações 
básicas que serão realizadas nesse fichário serão: incluir uma 
nova ficha (mantendo a ordenação), excluir fichas, consultar 
fichas, entre outras.
Nesse caso, a estrutura de dados que vamos utilizar é 
denominada LISTA (LIST), que provê uma sequência de in-
formações que se mantém ordenada por algum dos dados.
Outra situação é organizar as pessoas que precisam ser 
atendidas em um guichê. A forma mais racional de resolver essa 
situação é organizar as pessoas em fila, sendo que novas pessoas 
ficam no fim da fila e será atendido primeiro quem estiver no 
início da fila. As operações básicas serão: incluir nova pessoa 
na fila, consultar posição da fila, excluir pessoa da fila (em caso 
de alguém desistir).
A estrutura de dados que utilizaremos tem o mesmo 
nome, chama-se FILA (QUEUE), que provê uma sequência 
de informações que são ordenadas pela ordem de entrada das 
informações na FILA. O critério de ordenação de uma FILA 
denomina-se FIFO (First-In-First-Out, o primeiro a entrar é 
o primeiro a sair).
7ESTRUTURA DE DADOS
Vamos analisar outra situação: em uma organização em-
presarial deseja-se saber a estrutura dos cargos e as pessoas que 
ocupam cada um deles, considerando que cada cargo somente 
tem um superior direto. Nessa situação, constrói-se o organo-
grama da empresa. Logo, as operações básicas serão a inclusão 
de novos cargos, a relação hierárquica de um cargo, a vinculação 
de uma pessoa a um cargo, a exclusão de um cargo, entre outras.
Para atender a essa necessidade, utilizaremos uma estru-
tura de dados hierárquica, denominada ÁRVORE (TREE), 
que possui uma origem (raiz, no exemplo o cargo mais alto da 
organização) e todos os outros elementos serão organizados, de 
forma hierárquica, “abaixo” deste.
Agora, considere que você precisa organizar os pratos de 
um restaurante, a melhor forma é dispô-los em pilhas. Assim, 
o primeiro prato ficana base da pilha e o último é sempre colo-
cado no topo da pilha. Para usar os pratos, pegaremos primeiro 
aquele que estiver no topo da pilha e assim, subsequentemente, 
visto que, se tentarmos puxar o prato da base, derrubaremos a 
pilha. As operações básicas serão colocar pratos na pilha, tirar 
pratos da pilha, consultar tamanho da pilha, entre outras.
Utilizaremos aqui uma estrutura de dados que se chama 
PILHA (STACK), que é uma estrutura sequencial, a qual segue 
o critério LIFO de ordenação dos elementos (Last-In-First-Out, 
o último a entrar é o primeiro a sair).
8ESTRUTURA DE DADOS
Agora, se tivermos que organizar um trajeto para per-
correr todos os pontos turísticos de uma cidade. Teríamos que 
consultar um mapa e estabelecer as possíveis rotas e depois 
escolher a melhor delas. As operações possíveis seriam indicar 
os destinos, calcular os tempos e distâncias para ir de um ponto 
a outro, calcular rotas alternativas, etc. 
 A representação de mapas e informações geográficas são 
normalmente construídas através de GRAFOS (GRAPH), 
que são estruturas genéricas que permitem organizar diversos 
elementos, estabelecendo relações entre eles, aos pares.
Esses exemplos de aplicações referem-se às estruturas de 
dados básicas: Pilhas, Filas, Listas, Árvores e Grafos, que são 
o foco de estudo desta disciplina. 
Percebas que a maioria das estruturas de dados tem por 
princípio alguma forma de ordenação dos dados, principalmente 
porque isso facilita as consultas. Assim, também estudaremos 
diversos métodos de ordenação de dados. 
Temos certeza que você gostará de aprender o funciona-
mento e o desenvolvimento computacional das estruturas de 
dados! 
Amplie seus conhecimentos!
Pense (pesquise) outras aplicações que podem ser 
solucionadas com as estruturas de dados que estudaremos 
nesta disciplina: PILHAS, FILAS, LISTAS, ÁRVORES e 
GRAFOS.
9ESTRUTURA DE DADOS
PILHAS (STACK)
Você já se deu conta que muitos termos da 
informática foram tirados no mundo real e 
adaptados ao contexto computacional? 
Isso ocorre, porque a informática busca imitar, simular 
e replicar o mundo real. Entretanto, devido às limitações 
tecnológicas, o que se faz é uma abstração da nossa realidade 
para que possamos capturar o que existe de mais relevante 
em uma situação real, possibilitando a construção de mode-
los que constituem soluções computacionais que possam ser 
implementadas.
10ESTRUTURA DE DADOS
Uma abstração é uma representação que construímos de 
uma determinada realidade. É desejável que sejam construídos 
bons modelos, para tanto, é preciso conhecer bem os detalhes 
que formam a situação real e expressá-los através de uma es-
trutura de dados adequada, além de implementar os algoritmos 
necessários para sua manipulação.
Isso nos leva ao conceito de Tipo Abstrato de Dados 
(TAD), que é um agregado composto por um conjunto de dados 
e um conjunto de funcionalidades (operações) e operadores que 
podem ser utilizados para manipulação desses dados. Tudo isso, 
para atender uma necessidade específica.
Tipos Abstratos de Dados (TAD)
Vamos entender melhor esse conceito de TAD! 
Suponha que criamos uma variável do tipo ferramenta, ela 
poderia assumir os valores serrote, martelo, alicate, etc, e pode-
ríamos fazer as seguintes operações com esta variável: comprar, 
afiar, utilizar, vender, etc. Este seria o nosso TAD ferramentas.
Assim, ao definir um TAD, não levamos em conta de-
talhes de implementação. Pode até ser que não seja possível 
implementar um TAD numa determinada linguagem, mas 
devemos saber para que serve, que informações contém e quais 
operações/operadores podem ser utilizados.
11ESTRUTURA DE DADOS
Quando devemos identificar e projetar os Tipos Abstratos 
de Dados? 
De forma resumida, podemos dizer que o ciclo de vida 
de desenvolvimento de software engloba as etapas de análise, 
projeto, implementação, teste e manutenção. Na etapa de aná-
lise, nós iremos determinar o que o sistema deverá fazer, qual 
seu foco, quais informações irá manipular, etc. Já na etapa de 
projeto, definiremos como o sistema será desenvolvido. Aqui, 
a ideia é especificar uma definição geral, mas não os detalhes 
de desenvolvimento. Nessa etapa, decidimos a arquitetura do 
software, organizamos seus principais módulos, assim, a partir 
disso, podemos organizar a equipe de programadores para sua 
implementação. 
As outras etapas são relativas à implementação: codificação 
em uma linguagem de programação; testes para garantir que o 
software funcione adequadamente; e manutenção, que se refere 
aos ajustes que podem ser necessários a tempo de uso.
Assim, os TAD serão especificados (identificados e pro-
jetados) na etapa de projeto do software, ou seja, quando cons-
truímos uma visão geral de como o software deverá ser desen-
volvido, sem nos preocuparmos com detalhes de implementação. 
Além disso, tenha em mente que o princípio básico do Tipo 
Abstrato de Dados (TAD) é permitir que o programador pos-
sa separar o conceito (aquilo que o TAD deve ser e fazer) de 
sua implementação (detalhes de como deve ser desenvolvido, 
recursos, etc.). Essa separação possibilita que sejam realizadas 
mudanças na implementação e essas não alterarão o programa 
que utiliza o TDA.
Agora reflita: por que devemos utilizar Tipos Abstratos de 
Dados?
Podemos indicar algumas vantagens:
• É mais fácil programar quando não é necessário se pre-
ocupar com detalhes de implementação. 
• É mais fácil garantir a integridade dos dados, pois apenas 
as operações do TAD podem alterar os dados armaze-
nados. 
12ESTRUTURA DE DADOS
A utilização de Tipos Abstratos de Dados (TAD) melhora a 
portabilidade e a reutilização do software, reduzindo os custos 
de desenvolvimento e manutenção.
Um “programa” que não funciona, na verdade não é um 
programa!
• Maior independência e portabilidade de código, pois 
alterações na implementação de um TAD não provocam 
alterações nas aplicações. 
• Maior potencial de reutilização de código, pois alterações 
na lógica de um programa não implicam na reconstrução 
das estruturas de armazenamento. 
Pilhas, Filas, Listas, Árvores e Grafos são tipos abs-
tratos de dados!
A utilização de TAD está relacionada com o desenvolvi-
mento de bons programas! Mas o que significa desenvolver um 
bom programa? É suficiente “funcionar”?
Mas para ser um bom programa não é suficiente apenas 
funcionar! Um bom programa deve ter algumas características 
que os diferenciarão dos programas ruins:
• Um importante critério que caracteriza bons programas 
é sua eficiência, ou seja, programas que são rápidos e 
utilizam pouca memória, normalmente, são considerados 
melhores. Isso, porque muitas vezes temos restrições de 
espaço de armazenamento e requisitos de rapidez.
• Outra característica relevante é a reusabilidade! Você sabe 
o que isso significa? De forma simplificada, reutilizar, ou 
seja, você desenvolve um programa com um objetivo e este 
pode ser reutilizado dentro de outro programa/sistema. 
Esta é a ideia básica das bibliotecas de funções.
• Nós temos diversos tipos de computadores e diferentes 
sistemas operacionais, assim é desejável que os sistemas 
(programas) possam ser executados em diferentes plata-
formas. Essa característica de um programa é denominada 
portabilidade de software e é muito relevante para avaliar 
um bom programa.
Softwares que possuam portabilidade e reusabilidade têm 
custo mais baixo de desenvolvimento e manutenção.
13ESTRUTURA DE DADOS
TAD Pilha
O que é uma Pilha? Como uma pilha se transforma no TAD 
Pilha?
 Quando empilhamos objetos construímos uma pilha! 
Assim podemos ter pilhas de livros, pilhas de pratos, pilhas de 
cartas, pilhas de roupas, etc. Todas essas pilhas possuem um 
comportamento em comum: sempre que se deseja colocar um 
novo objeto na pilha, este é colocado no topo da mesma. Ele é 
empilhado, colocado em cima do último objeto que foi colocado 
na pilha. Para retirar objetos da pilha, retira-se, desempilha-se 
o objeto que está notopo, pois, de forma geral, se tentarmos 
tirar algum outro objeto acabaremos por derrubar a pilha!
O tipo abstrato de dados PILHA (TAD PILHA) possui 
a mesma lógica de funcionamento das pilhas de objetos, desta 
maneira podemos caracterizá-lo como: 
• Conjunto ordenado de elementos, em que o critério de 
ordenação é a ordem de inclusão;
• Novos elementos são sempre empilhados no topo da pilha;
• O único elemento que pode ser retirado da pilha é o que 
está no topo;
• Obedece ao critério LIFO (Last-In-First-Out), ou seja, 
o último a entrar é o primeiro a sair.
Agora, podemos definir um conjunto de operações básicas 
do TAD PILHA:
• Cria(P): função que cria a pilha na memória do compu-
tador e faz a inicialização de dados, necessários ao seu 
adequado funcionamento.
14ESTRUTURA DE DADOS
• Vazia(P): função que verifica se a pilha passada como 
parâmetro está vazia, ou seja, não possui elementos.
• Empilha(P, X): função que empilha o elemento X na pilha 
P, ambos passados como parâmetros. Costumeiramente, 
essa função é nomeada em inglês como: PUSH(P, X)
• Desempilha(P, X): função que desempilha o topo da 
pilha P e o atribui ao parâmetro X. Normalmente essa 
função é nomeada em inglês como: POP(P, X)
• Libera(P): função que libera da memória as estruturas 
que foram utilizadas para a pilha, ou seja, destrói a pilha.
Também podemos definir algumas operações complemen-
tares, que podem fazer parte do conjunto de operações básicas 
do TAD PILHA: 
• Cheia(P): função que verifica se uma pilha está cheia, 
pois normalmente as pilhas no computador possuem um 
limite de capacidade de armazenamento de elementos e 
este pode ter sido atingido.
• Topo(P, X): função que consulta o topo da pilha P e o 
atribui ao parâmetro X. Geralmente, essa função é no-
meada em inglês como: TOP(P, X)
• Tamanho(P, T): função que conta quantos elementos tem 
na pilha e atribui ao parâmetro T.
Destacamos que esse conjunto de operações básicas 
pode variar!
Utilizando essas operações básicas, diversas outras ope-
rações podem ser construídas para trabalhar com pilhas. Por 
exemplo, suponha que temos duas pilhas P1 e P2, P1 tem um 
conjunto de elementos, P2 está vazia e desejamos transferir 
os elementos de P1 para P2. Assim, poderíamos descrever a 
operação Transfere (P1, P2) para atender a esse objetivo. Lem-
bre-se que podemos utilizar somente as operações básicas de 
manipulação do TAD PILHA. A seguir, veja uma proposta de 
implementação dessa nova operação:
Vamos entender o funcionamento desta função e o uso 
das operações básicas do TAD PILHA.
Considere que a pilha P1 está definida da seguinte ma-
neira: P1(3, 6, 2, 9), sendo que o número 3 foi o primeiro a ser 
//Função que transfere todos os elementos de P1 para P2
Transfere(parâmetros por referência P1, P2 do tipo PILHA){
 Variável Elemento do tipo Dados_Pilha;
 Enquanto ( Vazia(P1) == Falso ) Faça {
 Desempilha(P1, Elemento);
 Empilha(P2, Elemento);
 }
}
15ESTRUTURA DE DADOS
colocado na pilha (base da pilha) e o número 9 foi o último a ser 
colocado, logo, ele está no topo da pilha. As próximas figuras 
demonstram o processo de execução da função Transfere (P1, 
P2), conforme a implementação apresentada. Perceba que a 
função possui uma repetição e enquanto a pilha P1 não estiver 
vazia, será repetido o processo que desempilha um elemento 
da pilha P1 e o empilha na pilha P2. Assim, na iteração 1, 
será desempilhado de P1 o elemento 9 e este será empilhado 
em P2. Na iteração 2, será desempilhado de P1 o elemento 
2 e este será empilhado em P2. Na sequência, na iteração 3, 
será desempilhado de P1 o elemento 6 e este será empilhado 
em P2. Depois será desempilhado de P1 o elemento 3 e este 
será empilhado em P2. Agora, a pilha P1 está vazia, portanto 
a repetição termina e todos os elementos da pilha P1 foram 
transferidos para a pilha P2. Agora, vamos analisar como ficaram os elementos da 
pilha P2: Eles estão dispostos da mesma maneira que estavam 
na pilha P1? 
Verifique se os elementos estão invertidos! Ou seja, a pilha 
P2 tem os mesmos elementos que a pilha P1, porém eles não 
estão na mesma ordem! Mas se nós quiséssemos que, ao transferir 
os elementos da pilha P1 para a pilha P2, eles fossem mantidos 
na mesma ordem, como deveríamos fazer essa implementação? 
Vamos construir juntos essa solução?
Você já percebeu que ao utilizar a função Transfere(P1, 
P2), ela transfere todos os elementos da pilha P1 para a pilha 
16ESTRUTURA DE DADOS
P2, porém os inverte. Agora, para construir uma função que 
transfira os elementos de P1 para P2, mas preservando a ordem, 
teríamos que chamar duas vezes a função transfere, a primeira 
para inverter e a segunda para “desinverter”, passando os dados 
por uma pilha auxiliar (AUX). Desta forma, a função Trans-
fereIgual(P1, P2) pode ser implementada da seguinte maneira:
Note, que ainda não nos preocupamos com a implementa-
ção (codificação), na linguagem de programação, das operações 
básicas do TAD PILHA, mas sim com o funcionamento do 
TAD e utilização de suas operações básicas! Essa é a essência 
dos Tipos Abstratos de Dados, você tem uma estrutura de 
informações (no caso atual o tipo PILHA) e um conjunto de 
operações básicas, a partir desses elementos você constrói as 
aplicações que utilizam pilhas! Isso é semelhante ao uso do 
tipo primitivo inteiro das linguagens de programação, você não 
se preocupa em como são implementadas pelo compilador as 
operações aritméticas, apenas as utiliza quando precisa, certo? 
Essa é a mesma ideia do TAD.
Ainda, precisamos conhecer dois conceitos relativos aos 
tipos abstratos de dados: operações primitivas e operações não 
primitivas. As operações primitivas de um TAD são aquelas 
que dependem da estrutura de armazenamento do TAD e dos 
recursos específicos da linguagem de programação para serem 
implementadas, são as operações básicas do TAD. Já as opera-
ções não primitivas de um TAD são aquelas que não dependem 
da estrutura de armazenamento do TAD e são implementadas 
através de chamadas de operações primitivas (básicas) do TAD.
Então, vamos analisar como são implementadas as ope-
rações primitivas do TAD PILHA.
//Função que transfere todos os elementos de P1 para P2,
//preservando a ordem original
TransfereIgual(parâmetros por referência P1, P2 do tipo PILHA){
 Variável AUX do tipo PILHA;
 Transfere(P1, AUX);
 Transfere(AUX, P2);
}
Desafio!
Construa uma nova função utilizando as operações básicas da 
TAD PILHA com o seguinte objetivo: Verificar se duas pilhas 
são exatamente iguais. TestaIgual(P1, P2)
17ESTRUTURA DE DADOS
Implementação do TAD Pilha
É possível implementar a TAD PILHA de diversas ma-
neiras, e elas se distinguem pela natureza dos seus elementos, 
pela forma de armazenamento dos elementos e pelas operações 
de tratamento da pilha que são disponibilizadas. Assim, para 
implementar as operações primitivas do TAD PILHA, é ne-
cessário definir a estrutura de armazenamento dos dados da 
pilha e a partir dessa desenvolver as funções de manipulação 
desta estrutura. 
Para nosso estudo consideraremos duas alternativas de 
implementação de pilha: a primeira com vetor e a outra com 
lista encadeada. Para tornar mais simples os exemplos, nós 
consideraremos que pilha armazena valores reais. Independente 
da alternativa de implementação, podemos definir a interface 
do TAD PILHA, que é composta pelas operações que serão 
disponibilizadas para manipular e acessar as informações da 
pilha. Para nossa implementação consideraremos as seguintes 
operações primitivas do TAD PILHA: Cria; Vazia; Push; Pop; 
Libera. Inicialmente, precisamos definir a interface do TAD 
PILHA, essa terá a estrutura de dados da pilha e a assinatura 
das funções de manipulação dessa estrutura (a definição do 
nome das funções, seus parâmetros e retornos).
Se considerarmos a implementação na linguagem C, para 
a definição da interface deste TAD precisaremos criar um ar-
quivo pilha.h, que terá o seguinte código:
typedef struct pilha Pilha;//estruturado tipo pilha
Pilha* cria (void);//função para criação da pilha
void push (Pilha* p, float v);//função para empilhar v na pilha p
float pop (Pilha* p);//função que retorna o valor do topo e o desempilha
int vazia (Pilha* p);//função que testa se a pilha está vazia
void libera (Pilha* p);//função que libera a memória
18ESTRUTURA DE DADOS
Implementação do TAD pilha com vetor
É possível implementar o TAD PILHA usando um sim-
ples vetor?
Sim! Muitas vezes, nas aplicações que utilizam pilhas, é 
possível conhecer o tamanho máximo dela, ou seja, sua quan-
tidade máxima de elementos é previamente conhecida e nessa 
situação podemos utilizar um vetor para implementar o TAD 
PILHA. A implementação será muito simples e a estrutura da 
pilha deverá ter o vetor e a quantidade de elementos armazena-
dos na mesma. Se a quantidade de elementos for igual a zero, 
a pilha estará vazia. Na linguagem C, o primeiro elemento do 
vetor possui o índice 0 (zero), dessa maneira, o índice do topo 
será a quantidade de elementos menos um.
Assim, podemos definir a estrutura da pilha conforme 
mostrado a seguir, onde MÁXIMO define a quantidade máxima 
de elementos que a pilha poderá conter, tamanho armazenará 
a quantidade de elementos empilhados e o vetor conterá estes 
elementos. 
Vamos implementar agora as funções de manipulação 
do TAD PILHA.
Para implementar a função que cria a pilha, deveremos 
alocar dinamicamente a pilha e inicializar seu tamanho com 
zero, indicando a pilha que está vazia. Veja a seguir a imple-
mentação desta função na linguagem C:
Para implementar a função que testa se a pilha está vazia, 
precisamos apenas testar o tamanho dela. A seguir você pode 
verificar essa implementação.
#define MAXIMO 100
struct pilha {
 int tamanho;
 float vetor[MAXIMO];
};
Pilha* cria ()
{
 Pilha* p = (Pilha*) malloc(sizeof(Pilha));
 p->tamanho = 0; /* inicializa com zero elementos */
 return p;
}
19ESTRUTURA DE DADOS
A função para liberar a memória alocada pela pilha é 
bastante simples, basta liberar o ponteiro criado para armazenar 
a pilha, veja a seguir como fica esta implementação:
Para empilhar um elemento na pilha, será usada a próxi-
ma posição livre do vetor, se ainda houver espaço (considerar o 
limite máximo de elementos). A seguir, você poderá verificar 
a implementação desta função: 
Para desempilhar o elemento que está no topo da pilha, 
precisamos primeiro verificar se a mesma possui elementos, se 
não está vazia. Assim, logo você poderá analisar a implemen-
tação da função POP:
Tenho certeza que você achou bem simples essas imple-
mentações, e se desejar fazer uma aplicação que utilize pilhas 
com tamanho máximo predefinido, poderá utilizar as funções 
dadas anteriormente para constituir a interface do TAD PILHA 
e, então, apenas precisará utilizar as operações primitivas sem 
ter que se preocupar com sua implementação, e elas já estarão 
prontas!
int vazia (Pilha* p)
{
 return (p->tamanho == 0);
}
void libera (Pilha* p)
{
 free(p);//libera a memória alocada para a pilha
}
void push (Pilha* p, float v)
{
 if (p->tamanho == MAXIMO){ /*esgotou tamanho da pilha */
 printf(“Pilha atingiu limite máximo.\n”);
 }
 else {
 /* novo elemento é inserido depois do topo */
 p->vetor[p->tamanho] = v;//guarda o valor no topo
 p->tamanho = p->tamanho + 1;//incrementa o tamanho
 }
}
float pop (Pilha* p)
{ 
 float v;
 if (vazia(p)) {
 printf(“Não há elementos na pilha.\n”);
 }
 else {
 /* desempilha elemento do topo */
 v = p->vetor[p->tamanho - 1];//consulta o valor do topo
 p->tamanho = p->tamanho – 1;//decrementa o tamanho
 return v;
 }
}
20ESTRUTURA DE DADOS
Implementação do TAD pilha com encadeamento
Dados encadeados ficam semelhantes a uma corrente, co-
nectados!
Muitas vezes o número máximo de elementos que será 
armazenado na pilha não é conhecido, nessa situação, a melhor 
forma de fazer a implementação é utilizar alocação dinâmica 
(onde a memória é gerenciada sob demanda em tempo de exe-
cução) através de encadeamento, elementos interligados. Parece 
complicado, mas não é! 
A ideia básica do encadeamento é fazer a ligação entre os 
elementos! Quando utilizamos alocação dinâmica é reservado 
um espaço na memória e para acessarmos esse dado, temos o 
endereço de onde foi alocado. Para fazer um encadeamento 
referenciamos o endereço de um elemento em outro elemento, 
dessa forma eles ficam relacionados (encadeados)! Nesse tipo 
de implementação, os elementos são organizados em posições 
não-contíguas, ficando dispersos ao longo da memória. Por essa 
razão, não é preciso estimar a priori o tamanho da estrutura, 
visto que o espaço é alocado conforme a necessidade. 
A base da construção de uma estrutura encadeada são os 
nodos (também conhecidos como “nós”), onde é armazenada 
a informação do elemento e o endereço do nodo relacionado. 
Dependendo das escolhas de estruturação do TAD, é possível 
ter mais de um endereço, por exemplo, para o próximo elemen-
to e para o elemento anterior. Entretanto, veremos isso mais 
adiante, quando estudarmos o TAD LISTA. Na imagem a 
seguir, você poderá visualizar a representação gráfica do nodo 
(informação + endereço) e de uma estrutura encadeada, onde 
cada nodo conecta-se a outro nodo.
 Agora vamos representar uma pilha através da estrutura 
de nodos! Para isso, vamos considerar a seguinte pilha P com 5 
elementos que possuem uma informação numérica: P (4, 2, 8, 
5, 3), sendo 4 o valor que está na base da pilha e 3 que está no 
topo da pilha. Cada novo elemento que será adicionado na pilha 
aponta para o endereço do elemento que está no topo, e então, 
21ESTRUTURA DE DADOS
torna-se o novo topo da pilha. Dessa maneira, cada elemento 
aponta para o elemento anterior. O primeiro elemento da pilha, 
que fica na sua base, não referencia outro nodo, pois não há um 
nodo anterior a ele, por isso no campo de endereço desse nodo 
é colocado o valor NULL (que indica nulo, sem valor). Desse 
modo, fica estruturada uma pilha encadeada.
Agora, podemos analisar a implementação do TAD PI-
LHA com encadeamento. Assim, primeiro precisamos definir a 
estrutura do nodo, e a Pilha será um ponteiro para esta estrutura. 
A partir dessa definição, podemos fazer a implementação 
das operações primitivas de manipulação da pilha. A primeira 
operação é a de criação dessa, que apenas devolverá um ponteiro 
nulo, pois estará vazia.
Para testar se a pilha está vazia, também é muito simples, 
basta testar se o seu valor é igual a NULL:
Para empilhar um novo elemento, teremos que alocar 
memória (tomando o cuidado de verificar se há memória su-
typedef struct nodo{
 float elemento;
 nodo* endereco;
};
typedef nodo* Pilha;
Pilha Criar(){
 return (NULL);
}
//Para usar a função:
Pilha p = Criar();
int Vazia(Pilha p){
 if (p == NULL)
 return(1);
 else
 return(0);
}
22ESTRUTURA DE DADOS
ficiente), bem como depois fazer com que esse novo elemento 
aponte para o endereço da pilha (que sempre estará apontando 
para o topo). Observe que se for o primeiro elemento, o ende-
reço da pilha é NULL (pois foi recém criada). Logo, o primeiro 
elemento terá no endereço o valor NULL (conforme vimos na 
representação gráfica da pilha encadeada). Vejamos como fica 
a implementação da função PUSH (empilhar):
A função para desempilhar (POP) deverá verificar se há 
elementos na pilha e se houver, consultar a informação do topo, 
alterar o topo da pilha e liberar a memória que era utilizada pelo 
topo anterior que será removido. A seguir, poderemos visualizar 
a implementação desta função.
Pronto! Temos agora o conjunto de operações primitivas 
do TAD PILHA utilizando encadeamento! São essencialmente 
as mesmas funções que desenvolvemos com vetor, apenas não 
precisamos da função libera, pois a própria função pop já libera 
progressivamente a memória a cada elemento que é desempilha-
do. Assim como, existem outras alternativas de implementaçãode pilhas, também há variações das implementações apresenta-
das, você pode pesquisar e identificar as diferenças entre elas.
void Push (Pilha p, float x) {
 nodo novo = (nodo) malloc (sizeof (nodo));
 if (novo == NULL){
 printf (“Memoria insuficiente!!”);
 }
 else {
 novo -> elemento = x;
 novo -> endereco = p;//o novo elemento aponta para o topo
 p = novo; //o topo da pilha passa a ser o novo endereço
 }
}
float pop(Pilha p) {
 nodo * remover;
 float x;
 if (vazia(p)){
 printf (“Pilha vazia.”);
 } 
 else {
 remover = p;
 x = remover->elemento;
 p = p->endereco;
 free(remover);
 return(x);
 }
}
Desafio!
Você já ouviu falar das Torres de Hanoi? Pesquise sobre esse jogo e 
estruture a lógica para cumprir o objetivo das Torres de Hanoi. Dica, 
você precisará de 3 pilhas (p1, p2 e p3) para representar os pinos. A 
informação da pilha será um número inteiro que representa o tamanho 
de cada disco. 
23ESTRUTURA DE DADOS
Os Tipos Abstratos de Dados são uma importante ferra-
menta para o desenvolvimento de sistemas, são versáteis e visam 
o desenvolvimento de bons programas que buscam a portabili-
dade e reusabilidade. Conhecer os TAD clássicos, como o TAD 
PILHA, é fundamental para os programadores e projetistas 
de softwares. Pratique! Desenvolva programas usando Tipos 
Abstratos de Dados. 
Amplie seus conhecimentos!
Pesquise sobre as aplicações do Tipo Abstrato de Dados 
PILHA para a computação! Principalmente, pesquise sobre o 
processo de passagem de parâmetros na chamada de funções 
e procedimentos, em que o sistema operacional utiliza pilha.
Vamos lá! Verifique o que aprendeu nesta lição!
1. Por que utilizamos abstrações em computação?
2. Explique o que é e para que servem os Tipos Abstratos de 
Dados?
3. Explique quando devemos identificar e projetar os Tipos 
Abstratos de Dados para uma aplicação:
4. Explique por que devemos utilizar Tipos Abstratos de Dados:
5. Explique os critérios para determinar se um programa é bom, 
diferenciando-o de programas ruins:
6. Conceitue e descreva as características do TAD PILHA:
7. Enumere e explique as operações primitivas (básicas) do TAD 
PILHA:
8. Quando queremos utilizar o TAD PILHA para o desenvolvimento 
de uma aplicação, precisamos, necessariamente, implementar 
todas as funções da aplicação considerando a estrutura de 
armazenamento do TAD PILHA ,ou apenas utilizamos as funções 
(operações) primitivas? Por quê?
9. Existe somente uma forma de implementar o TAD PILHA? 
Por quê?
10. Quais os elementos que devem fazer parte da interface do 
TAD PILHA? O que é uma interface de um TAD?
11. Explique, de forma resumida, como o TAD PILHA pode ser 
implementado usando vetor.
12. Explique o que é alocação dinâmica e encadeamento.
13. Compare a implementação do TAD PILHA usando vetor e 
encadeamento.
14. Considere uma pilha que armazena em cada elemento um 
caracter (char), com a seguinte estrutura:
Agora, considere que essa pilha será utilizada para armazenar os 
caracteres de uma palavra, assim, em cada nodo da pilha teremos 
uma letra da palavra. Agora o desafio é construir uma função 
que verifique se a palavra é um palíndromo, que são palavras 
ou expressões que podem ser lidas da esquerda para a direita 
ou da direita para a esquerda. Exemplo de palíndromos: asa, 
typedef struct nodo{
 char elemento;
 nodo* endereco;
};
typedef nodo* Pilha;
arara, osso, radar, reviver, ovo, ana. A função a ser construída 
deve usar as operações primitivas da pilha (não manipulando 
a estrutura de dados diretamente) e ter a seguinte assinatura:
int palindromo(Pilha p);
Deverá retornar 1, se o conteúdo da pilha formar um palíndromo 
e, caso contrário, retornar 0 (zero). Dica, lembre das funções 
transfere e transfereigual, desenvolvidas ao longo do capítulo, 
elas podem ser úteis para atingir nosso objetivo.
26ESTRUTURA DE DADOS
FILAS (QUEUE)
Usamos filas no nosso dia a dia! Filas para 
caixas em supermercados e lojas, filas para 
atendimento em bancos, filas para atendimento 
em serviços públicos, entre outros. Além disso, 
usamos filas no computador, como exemplo, 
temos a fila de impressão! 
Filas são estruturas sequenciais, onde novos elementos 
são sempre incluídos no final da fila e o elemento que será 
utilizado (atendido) será aquele que estiver no início da fila, 
sendo, então, removido dela. As filas atendem a um critério 
de funcionamento denominado FIFO (First-In-First-Out), 
ou seja, o primeiro a entrar na fila será o primeiro a sair. Uma 
fila inicia vazia, considere uma fila de banco quando este está 
recém abrindo, quando chega a primeira pessoa essa se torna 
a primeira e a última pessoa da fila. Na sequência, novas 
pessoas irão para o fim da fila e quando o caixa do banco for 
atender, atenderá a primeira pessoa que está na fila, então ela 
sai da fila e a próxima se torna a primeira da fila. Portanto, 
precisamos saber quem está no início e quem está no fim da 
fila, esses são os dados básicos. Vamos compreender como funciona o Tipo Abstrato de Dados Fila!
27ESTRUTURA DE DADOS
0 1 2 3 4
tamanho=1 
Ana
Início Fim
Inclusão do Primeiro Elemento
0 1 2 3 4
tamanho=0 Fila Vazia
Assim como TAD PILHA, podemos implementar o 
TAD FILA utilizando vetores (que também pode ser chama-
do de alocação estática) ou encadeamento (alocação dinâmica). 
Porém, há alguns inconvenientes na implementação da FILA 
com vetores. 
Usualmente, filas não tem um limite, portanto fica difícil 
definir o tamanho do vetor que deverá conter a fila. Diferente 
do TAD PILHA, em que a base da pilha está sempre na mesma 
posição e tanto as operações de empilhar como desempilhar são 
sempre realizadas no topo. No TAD FILA a operação de incluir 
um novo elemento sempre o faz no fim da fila, já a operação 
de remover um elemento da fila sempre se faz no início dela. 
Dessa maneira, sempre estaremos utilizando duas posições do 
vetor, uma indicando o início da fila e outro seu fim. E a prin-
cipal característica a considerar é que o início da fila poderá 
passar a não coincidir com o início físico do vetor e isso torna 
esta implementação mais complexa. Além disso, o fim da fila, 
também acabará por não coincidir com o fim físico do vetor. 
Isso ocorre, porque vão sendo retirados elementos do início e 
estes espaços do vetor poderão ser aproveitados para inclusão 
de novos elementos. 
Para entender melhor essa situação, vejamos a sequência 
de imagens, a seguir, que apresentam a estruturação de uma 
fila utilizando vetores. 
Estamos utilizando um vetor de 5 posições, com os índices 
entre 0 e 4, e uma variável para conter o tamanho. Iniciamos com 
a fila vazia, tamanho = 0. Na sequência, adicionaremos a cada 
etapa um elemento novo, no final da fila. Assim, perceba que o 
tamanho será incrementado e que o fim da fila será deslocado, 
sempre apontando para o último elemento que foi incluído. Fa-
zemos isso até encher a fila. Depois passamos a atender pessoas 
da fila e removê-las, nessa situação, a cada remoção o início da 
fila passa a ser alterado, bem como começam a existir espaços 
vagos no início físico do vetor. Por fim, demonstramos o que 
irá acontecer ao adicionar mais um elemento na fila, que será 
o último, mas acabará sendo incluído no início do vetor, pois é 
a próxima posição livre. Terminando o nosso exemplo, o início 
da fila estará na posição 3 do vetor e o fim da fila na posição 0.
28ESTRUTURA DE DADOS
0 1 2 3 4
tamanho=4 
Ana Maria José Marco
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=5 
Ana Maria José Marco Lúcia
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=4 
Maria José Marco Lúcia
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=3 
José Marco Lúcia
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=2 
Ana Maria
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=3
 
Ana Maria José
Início Fim
Inclusão do Próximo Elemento
29ESTRUTURADE DADOS
O vetor não é uma estrutura de dados f lexíveis, pois preci-
samos definir a quantidade máxima de elementos no código do 
programa, que se tornará fixo nas execuções. Caso o número de 
elementos venha exceder o limite previsto para o vetor, teremos 
um problema. Por outro lado, se esse número de elementos for 
muito menor que o limite, teremos desperdício de espaço de 
memória reservado para o vetor. 
Normalmente, a intenção de utilizar vetores para im-
plementação do TAD é oferecer simplicidade e facilidade de 
desenvolvimento, mas isso não ocorrerá com a implementação 
do TAD FILA com vetores. Portanto, optaremos por não tra-
balhar a implementação dessa alternativa neste livro.
Implementação do TAD fila com Encadeamento
Veremos que a implementação do TAD FILA utilizan-
do encadeamento é semelhante a implementação do TAD 
PILHA com encadeamento.
A diferença está nas informações que são necessárias para 
gerenciar a fila, pois agora precisamos saber o endereço do início 
e fim da fila e também seu tamanho, isso é importante para que 
não tenhamos que varrer toda a fila para obter essa informa-
ção. Esses dados formarão o que denominamos cabeçalho da 
fila (queue header, em inglês). Desta forma, podemos definir 
a estrutura deste cabeçalho na linguagem C conforme segue: 
0 1 2 3 4
tamanho=2 
Marco Lúcia
Início Fim
Inclusão do Próximo Elemento
0 1 2 3 4
tamanho=3 
MarcoEduardo Lúcia
InícioFim
Inclusão do Próximo Elemento
30ESTRUTURA DE DADOS
Já a estrutura do nodo da fila fica muito semelhante ao 
nodo da pilha, a diferença aqui é o ponteiro para o endereço, 
que neste caso denominamos próximo, porque irá apontar para 
o próximo elemento da fila. Por questões de simplicidade, es-
tamos considerando que o conteúdo do elemento é apenas um 
valor real (f loat).
Precisamos definir a interface de funções do TAD FILA 
que pode ser visualizado a seguir:
Vamos analisar a implementação de cada uma dessas 
funções.
A função para criação da fila deve alocar o cabeçalho da 
mesma e inicializar os seus campos, de maneira que, tamanho 
= 0 (zero elementos) e início e fim, recebem NULL (nulo), 
indicando que não apontam para nodos.
A função que inclui elementos no final da fila deve alocar 
o novo nodo (verificando se há memória suficiente para este 
processo), depois o novo elemento pode ser encadeado. Para 
isso, é necessário que o último elemento da fila passe a apontar 
para esse novo elemento. Todavia, a exceção é quando a fila está 
vazia, pois neste caso não há último elemento, então o início 
e o fim apontarão para o novo elemento, que será o primeiro 
da fila. Em ambas as situações, o fim da fila passa ser o novo 
elemento.
struct fila {
 int tamanho;
 nodo* inicio, fim;
};
typedef struct fila Fila;//estrutura do tipo pilha
typedef struct nodo{
 float elemento;
 nodo* proximo;
};
//função para criação da fila
Fila* cria (){
 Fila* f = (Fila) malloc (sizeof (Fila));//aloca cabeçalho
 f->tamanho = 0;
 f->inicio = NULL;
 f->fim = NULL;
 return(f);
}
Fila* cria ();//função para criação da fila
void insere (Fila* f, float v);//função para incluir v 
na fila f
float remove (Fila* f);//função que retorna o valor do 
início da fila f e o exclui
int vazia (Fila* f);//função que testa se a fila está vazia
void libera (Fila* f);//função que libera a memória
int elementos(Fila* f);//função que retorna o tamanho 
da fila
31ESTRUTURA DE DADOS
//função que testa se a fila está vazia
int vazia (Fila* f){
 if (f->inicio == NULL)
 return(1);
 else
 return(0);
}
A função que remove o elemento do início da fila precisa 
verificar se a fila possui elementos, ou seja, se não está vazia. 
Se tiver elementos é necessário guardar o ponteiro do primeiro 
elemento para que possa ser liberado da memória. Além disso, 
é necessário atualizar o início da fila, que será o próximo (o 
seguinte) da fila. Devemos ter o cuidado de verificar se a fila 
ficou vazia, ou seja, se ao remover o elemento não restaram 
elementos nela, nesse caso, será necessário atualizar o fim da 
fila. Por fim, liberamos o ponteiro do elemento removido e é 
retornada a sua informação. Veja sua implementação a seguir:
A função que testa se a fila está vazia é simples, basta 
testar se o início da fila é NULL (nulo), indicando que não 
tem elementos.
//função para incluir v na fila f
void insere (Fila* f, float v){
 nodo* anterior;
 nodo* novo = (nodo) malloc (sizeof (nodo));
 if (novo == NULL){
 printf (“Memoria insuficiente!!”);
 }
 else {
 novo -> elemento = v;
 novo -> proximo = NULL;//o novo elemento será o último da fila
 f->tamanho = f->tamanho + 1;//incrementa tamanho
 //agora temos que encadear a fila
 if (f->inicio == NULL){//fila está vazia
 f->inicio = novo;
 f->fim = novo;
 }
 else{
 anterior = f->fim;
 anterior->próximo = novo;//o último elemento aponta para o novo
 f->fim = novo;//o novo elemento se torna o novo fim da fila
 }
 }
}
//função que retorna o valor do início da fila f e o exclui
float remove (Fila* f){
 nodo* primeiro;
 float v;
 if (vazia(f)){
 printf (“Fila Vazia!!”);
 return(0);
 }
 else {
 primeiro = f->inicio; 
 v = primeiro->elemento;
 //agora temos que atualizar o novo início da fila
 f->inicio = primeiro->proximo;
 f->tamanho = f->tamanho - 1;//decrementa tamanho
 if (f->inicio == NULL){//verifica se a fila ficou vazia
 f->fim = NULL;
 }
 free(primeiro);
 return(v);
 }
}
32ESTRUTURA DE DADOS
Por fim, temos a função que libera memória, que irá li-
berar o espaço alocado pelo cabeçalho da fila.
Para sabermos quantos elementos estão armazenados na 
pilha, temos a função elementos, que retorna à informação que 
está armazenada no campo tamanho do cabeçalho da pilha. 
Lembremo-nos que a função insere, incrementa esse campo e 
que a função remove, decrementa.
Esse conjunto de operações primitivas do TAD FILA 
permite que diversas outras operações possam ser construídas 
utilizando-as como base. É importante que ao utilizar um TAD, 
isso sempre seja feito através de sua interface, ou seja, apenas 
utilizando as operações primitivas. Se necessário, podemos am-
pliar a interface, adicionando novas operações. Quem utiliza o 
TAD não deve manipular a estrutura de armazenamento dele.//função que libera a memória
void libera (Fila* f){ 
 if (f != NULL)
 free(f);
}
//função que retorna o tamanho da fila
int elementos(Fila* f){ 
 if (f != NULL)
 return(f->tamanho);
 else
 return(0);
}
Amplie seus conhecimentos!
Pesquise sobre o funcionamento da fila de impressão! Quais 
funcionalidades possui, quais informações são registradas de 
cada requisição de impressão. A partir disso, veja que podem 
existir filas com prioridades, então pesquise e reflita como 
poderia ser feito esse tipo de implementação!
Vamos lá! Verifique o que aprendeu nesta lição:
1. Qual a lógica de funcionamento do TAD FILA?
2. O que é o critério FIFO?
3. Quais as diferenças entre o TAD FILA e o TAD PILHA?
4. Explique como poderíamos utilizar um vetor para implementar 
o TAD FILA.
5. Descreva quais os inconvenientes de utilizar vetor para 
implementar o TAD FILA.
6. Descreva a interface do TAD FILA.
7. Explique as operações primitivas do TAD FILA.
8. Você precisa construir uma função que esvazia a FILA, que 
pode conter diversos elementos, ou seja, enquanto a fila não 
estiver vazia você deve remover um elemento. Você somente 
pode utilizar as operações primitivas da fila. A assinatura 
desta função é:
• void esvazia(Fila* f).
9. Construa, usando somente operações primitivas da fila, uma 
função que faça a cópia de uma fila f1 para uma fila f2. Utilize 
a seguinte assinatura para esta função:
• void copia(Fila* f1, Fila* f2).
10. Se desejarmos procurar um elemento específico dentroda 
fila (por exemplo o elemento = 3), é possível fazer essa busca 
utilizando apenas as operações primitivas ou precisaríamos 
implementar uma nova operação primitiva? Por quê?
11. Considere que estamos usando um sistema para controlar 
as filas de atendimento de caixas de um supermercado, onde 
cada pessoa entra em uma fila específica e para nosso exemplo 
temos apenas 2 filas f1 e f2, porém ocorreu um problema em 
um dos caixas e apenas um se manteve funcionando. Assim, 
agora você deve construir uma função que irá transferir os 
elementos da fila f2, colocando-os no fim da fila f1, para isso 
você apenas pode utilizar as operações primitivas do TAD fila, 
sem manipular diretamente sua estrutura interna. A assinatura 
desta função é:
• void transferir(Fila* f1, Fila*f2);
34ESTRUTURA DE DADOS
LISTAS (LIST)
Listas são um importante recurso que 
estamos acostumados a utilizar! Fazemos 
lista de compras, lista de convidados para 
uma festa, lista de alunos em uma disciplina, 
entre outros. 
Conjuntos de elementos podem ser intuitivamente re-
presentados através de listas. Essas são estruturas lineares e 
f lexíveis, uma vez que as operações de inclusão e remoção de 
dados possam ser feitas em qualquer ponto da lista, conforme 
o critério de ordenação que for adotado. A ordem de uma 
lista pode ser simplesmente a ordem de inclusão, como ocorre 
com filas e pilhas, mas também pode ter algum campo(s) que 
determina(m) a relação de ordem dos elementos da lista. Por 
exemplo, se tivermos uma lista com dados de pessoas, esta 
poderia ser ordenada pelo nome. 
Assim como pilhas e filas, as listas podem conter todo 
tipo de informação em cada um de seus elementos. O ele-
mento pode ser apenas um número ou caractere, mas também 
pode ser um conjunto heterogêneo de dados: um registro. Por 
exemplo, um registro com os dados de pessoas (código, nome, 
idade, telefone, etc.). 
Nosso objetivo agora é compreender e aprender a implementar o Tipo 
Abstrato de Dados Lista
35ESTRUTURA DE DADOS
Listas são uma generalização das pilhas e filas. Todas 
são estruturas lineares, onde os elementos possuem relação 
de ordem entre eles. Essa relação pode ser estabelecida por 
contiguidade física (no caso dos vetores) ou por encadeamento 
(alocação dinâmica). Entretanto, pilhas e filas possuem uma 
lógica de funcionamento restrita, pois pilhas somente incluem e 
removem elementos no topo (“fim” da pilha), já as filas somente 
incluem elementos no fim da fila e somente removem elementos 
no início da mesma. Por outro lado, as listas permitem que a 
inserção de novos elementos seja feita no início, meio ou fim 
da lista e a remoção de elementos também pode ser realizada 
no início, meio ou fim da lista. 
Tipos de Listas
Existem diversos tipos de listas, conforme a definição da 
estrutura de dados e lógica de operação.
Assim, temos: Listas simplesmente encadeadas; Listas 
duplamente encadeadas; e Listas circulares.
Nas listas, cada nodo (também chamado de nodo ou nó), 
possui suas informações e referência (endereço). 
Nas listas simplesmente encadeadas, a referência aponta 
para o próximo elemento da lista, que é um ponteiro para o 
endereço alocado para o nodo. Nesse tipo de lista a varredura 
é sempre realizada em um único sentido, a partir do início da 
lista para frente (em inglês, forward), passando pelos nodos e 
chegando ao fim da lista, que é indicado pelo nodo em que a 
referência para o próximo é nula (NULL). Observe a seguir a 
representação desse tipo de lista.
Já nas listas duplamente encadeadas, é adicionado ao nodo 
mais um ponteiro (referência), que apontará para o elemento 
(nodo) anterior. Desse modo, caso possua mais f lexibilidade de 
varredura na lista, podemos varrer a mesma do início para o 
fim, bem como do fim para o início, também podemos chegar 
a qualquer extremidade a partir de qualquer nodo! Perceba que 
o próximo do último elemento é nulo (NULL), indicando o 
fim da lista e que o anterior do primeiro elemento também é 
nulo (NULL), indicando o início da lista. Você pode ver isso 
na figura a seguir:
Agora, vamos ver o que muda quando utilizamos listas 
circulares!
Início
Fim
NULL
Informação Próximo Informação Próximo
InformaçãoPróximoInformaçãoPróximo
Fim
InformaçãoPróximo Anterior
Início
InformaçãoPróximo Anterior
Informação PróximoAnteriorInformação PróximoAnterior
36ESTRUTURA DE DADOS
Início
Fim
Informação Próximo Informação Próximo
InformaçãoPróximoInformaçãoPróximo
Fim InformaçãoPróximo Anterior
Início
InformaçãoPróximo Anterior
Informação PróximoAnteriorInformação PróximoAnterior
A ideia das listas circulares é criar um anel, como se a 
lista não tivesse nem início e nem fim. Isso torna mais f lexível 
a varredura da lista. Logo, nas listas circulares, simplesmente 
encadeadas, a referência próxima do último nodo passa a apontar 
para o primeiro nodo, criando um círculo de encadeamento. Já 
no caso das listas circulares duplamente encadeadas, o ponteiro 
para o elemento anterior do primeiro nodo passa a apontar para 
o último. Assim, nesse tipo de lista, não temos delimitadores 
nos nodos (elementos) que indicam o início ou fim da lista 
(ponteiros próximo ou anterior com valores NULL), apenas 
as informações do cabeçalho da lista indicarão os limites dela. 
A figura seguinte apresenta a estrutura de uma lista circular 
simplesmente encadeada, onde é possível observarmos que o 
ponteiro próximo do último nodo da lista aponta (referencia) 
para o primeiro nodo da lista.
E a seguir você pode visualizar uma lista circular dupla-
mente encadeada:
A escolha do tipo de lista é uma decisão de quem está 
implementando o TAD (Tipo Abstrato de Dados) LISTA, pois 
não interfere na interface do TAD, visto que não interfere na 
interface de operações primitivas, mas sim define alternativas 
para a estrutura de dados do TAD e, consequentemente, terá 
impacto na implementação, que em alguns casos poderá facilitar a 
realização de algumas operações e tornar outras mais complexas. 
Implementação do TAD com lista de encadeamento
Para trabalharmos com uma lista encadeada, temos que 
ter em mente que para cada novo elemento que é inserido na 
estrutura, devemos alocar dinamicamente um espaço de memória 
37ESTRUTURA DE DADOS
A partir disso podemos definir a estrutura do nodo:
Agora, faremos a definição do cabeçalho da lista - nós já 
utilizamos esse recurso na implementação das FILAS, e sabemos 
que tem por objetivo ter as informações da estrutura da lista. 
As informações básicas do cabeçalho são: início (ponteiro para 
o primeiro nodo da lista); fim (ponteiro para o último nodo 
da lista); tamanho (que indica quantos elementos constituem a 
lista, economizando o processo de varrer a lista para obter esse 
dado). Assim, podemos definir esta estrutura:
struct dado {
 int codigo;
 char nome[40];
 int idade;
};
struct nodo {
 dado informacao;
 struct nodo* proximo;
};
struct lista {
 int tamanho;
 struct nodo* inicio, fim;
};
struct lista* LISTA;
para armazená-lo. Dessa forma, o espaço de armazenamento 
na memória é proporcional à quantidade de elementos. No 
entanto, a alocação dinâmica não ocupa espaços contíguos de 
memória, portanto não é possível ter acesso direto aos elementos 
da lista. Assim, para constituir a lista precisamos encadear os 
elementos, ou seja, cada elemento precisa referenciar o próximo 
elemento da estrutura (e o anterior, no caso de listas duplamente 
encadeadas) e essa referência aponta para o endereço alocado 
de cada elemento, conforme a ordem pré-definida para a lista. 
Dessa forma, cada elemento possui sua informação (número, 
caractere, estrutura de informações, etc.) mais a informação de 
referência que é ponteiro para o próximo elemento e ponteiro 
para o anterior, conforme o tipo de lista.
Vamos considerar a implementação de uma Lista Sim-
plesmente Encadeada!
Precisamos definir, usando a linguagem de programação, 
a estrutura de dados da LISTA, seu cabeçalho e as operações 
primitivas do TAD que constituemsua interface básica. Vamos 
considerar em nossos exemplos um registro simples de dados de 
pessoas, com as seguintes informações: código (que identifica 
cada pessoa); nome; idade. Você pode facilmente incluir mais 
informações nesse registro. Esses dados foram escolhidos pen-
sando em diferentes possibilidades de ordenação da lista. Desse 
modo, a informação do nodo será uma estrutura conforme segue:
38ESTRUTURA DE DADOS
A partir da definição da estrutura de armazenamento do 
TAD LISTA, podemos definir sua interface de funções, ou seja, 
as operações primitivas do TAD que manipulam sua estrutura.
Na sequência, você poderá analisar a implementação de 
cada uma dessas funções.
Podemos implementar a função de criação da lista de 
forma bem simples, pois consiste apenas em alocar o cabeçalho, 
inicializar o tamanho e atribuir NULL para o início e fim da 
lista, visto que estamos criando uma lista vazia (que ainda não 
possui elementos).
Para verificar se uma lista está vazia, podemos testar se 
o tamanho é 0 (zero) ou se o início ou fim são nulos (NULL). 
Optaremos por testar o início da lista, se este for igual NULL, 
indica que não há elementos na lista e a função retornará o valor 
1, caso contrário, retornará 0. Veja a seguir a implementação 
desta função:
//função para criação da lista 
LISTA * cria (){
 LISTA* p;
 p = (LISTA) malloc (sizeof (LISTA));
 p->tamanho=0;
 p->inicio=NULL;
 p->fim=NULL;
 return(p);
}
//função que testa se a lista está vazia 
int vazia (LISTA * l){
 if (l->inicio == NULL)
 return(1); 
 else
 return(0);
}
//função para criação da lista 
LISTA* cria ();
 
//função que testa se a lista está vazia 
int vazia (LISTA * l); 
//função que libera a memória 
void libera (LISTA * l); 
//função que retorna o tamanho da lista
int elementos(LISTA * l);
//função para incluir os dados v na lista l
void insere (LISTA * l, dado v); 
//função que retorna o valor do início da lista l e o exclui
int remove (LISTA * l, dado* v); 
39ESTRUTURA DE DADOS
A função que libera memória precisa liberar o espaço 
alocado para o cabeçalho. Em princípio, consideraremos que a 
lista está vazia e, portanto, não precisam ser liberados os nodos 
ocupados. Seria possível implementar uma função que esvazia 
uma lista, mais adiante faremos isso. A seguir, veja a imple-
mentação da função libera:
Para consultar a quantidade de elementos da lista, bas-
ta consultar a informação de tamanho do cabeçalho da lista, 
conforme segue:
Agora vamos analisar a implementação da função de 
inclusão de novos elementos. 
//função que retorna o tamanho da lista
int elementos(LISTA * l){
 return(l->tamanho);
}
//função que libera a memória 
void libera (LISTA * l){
 free(l);
} 
Um novo elemento pode ser incluído no fim da lista, nesse 
caso a lista passa a ter um comportamento semelhante ao de 
uma fila, onde o critério de ordenação é a ordem de inclusão. 
Por outro lado, a lista pode ter outro critério de ordenação de 
seus elementos, que pode ser a ordem crescente dos códigos de 
identificação das pessoas. Nesse caso, o novo elemento poderá 
ser incluído no início, no meio ou no fim da lista. 
Vamos analisar tal situação! 
Considere uma lista em que já foram incluídos 3 elementos 
(na figura, apenas estamos representando os códigos da infor-
mação). Se formos adicionar um novo nodo em que o código 
da pessoa for 3, esse deverá ser incluído antes do atual início 
da lista, conseguintemente, passará a ser o novo início. Agora, 
se formos adicionar o código 11, este novo elemento deverá 
ser encadeado entre os nodos de código 9 e 15. Por outro lado, 
se formos adicionar o nodo com o código 20, este deverá ser 
encadeado no fim da lista.
40ESTRUTURA DE DADOS
Verifique na figura a seguir a inclusão de um novo ele-
mento antes do início da lista, onde o novo elemento com código 
3 tem como próximo o atual início da lista e o início passa a 
apontar para o novo elemento.
Agora, o diagrama demonstra a inclusão de um novo 
elemento no meio da lista, ajustando os ponteiros para manter 
o encadeamento conforme o critério de ordenação.
Por fim, veja a representação da inclusão de um novo 
nodo no fim da lista:
Como definir onde o novo nodo deve ser incluído?
Para definir onde o novo nodo deve ser incluído, teremos 
que fazer uma varredura da lista, ou seja, a partir do início da 
lista comparar a chave de ordenação do novo nodo com a do 
nodo corrente, se a do novo elemento for menor, significa que 
41ESTRUTURA DE DADOS
ele será inserido antes do atual. Todavia, se chegarmos ao final 
da lista e não encontrarmos um elemento maior que o novo, 
ele se tornará o novo final da lista. Sendo assim, em todas as 
situações é necessário preservar o encadeamento.
A implementação da função de inclusão de um novo nodo 
deve considerar todas essas situações, inclusive o fato de a lista 
estar vazia. Então, vamos ver essa implementação:
Por fim, vamos implementar a função que remove um 
elemento da lista e retorna as suas informações! Em primeiro 
lugar, precisamos determinar qual será o nodo que será excluí-
do! Optamos por receber o código do elemento a ser excluído, 
localizá-lo, consultar seus dados e, então, excluí-lo. Podemos 
identificar 4 situações a partir dessa busca: 1ª) O código não 
existe, portanto nada será excluído ou retornado; 2ª) O elemento 
a ser excluído é o primeiro da lista, portanto o seu início preci-
sa ser ajustado; 3ª) O elemento a ser excluído está no meio da 
lista, assim precisamos ajustar os ponteiros; 4ª) O elemento é o 
último elemento da lista, portanto precisamos ajustar o seu fim. 
Sempre que um elemento for removido, precisamos atualizar o 
tamanho da lista, decrementando. Além disso, a função retorna 
1 se teve êxito, caso contrário, será 0 (zero). 
//função que retorna um elemento da lista e o exclui
int remove (LISTA * l, dado* v){
 int código = *v.codigo;
 nodo* anterior, corrente;
 if (vazia(l)){ return(0);}
 else{
 corrente = l->inicio;
 if (codigo == corrente->codigo){//achou no início!
 strcpy(*v.nome,corrente->nome);
 *v.idade=corrente.idade;
 l->inicio = corrente->proximo;
 free(corrente);
 l->tamanho = l->tamanho – 1;
 return(1);
 }
 else{
 while((corrente != NULL) && 
 (codigo != corrente->codigo)&&
//função para incluir os dados v na lista l
void insere (LISTA * l, dado v){
 nodo* novo;
 nodo* anterior, corrente;
 novo = (nodo) malloc(sizeof(nodo));//alocação dinâmica do novo nodo
 //a seguir passamos as informações do registro v para o nodo
 nodo->codigo = v.codigo;
 strcpy(nodo->nome,v.nome);
 nodo->idade = v.idade;
 nodo->próximo=NULL;
 if (vazia(l)){ //o novo elemento será o início e fim da lista
 l->inicio = novo;
 l->fim = novo;
 }
 else{
 //agora precisamos determinar a posição de inclusão do novo nodo
 corrente = l->inicio;
 if (novo->codigo < corrente->codigo){//inclusão no início 
 novo->proximo = l->inicio;
 l->inicio = novo;
 }
 else {//varredura da lista
 while((corrente != NULL)&&(novo->código >= corrente->codigo)){
 anterior = corrente;
 corrente = anterior->proximo; 
 }
 anterior->proximo = novo;
 novo->proximo = corrente;
 if (corrente == NULL)
 l->fim = novo;
 }
 }
 l->tamanho = l->tamanho + 1; //incrementa tamanho
}
42ESTRUTURA DE DADOS
Podemos adicionar algumas operações à interface desse 
TAD, como por exemplo: procurar um elemento na lista, e caso 
encontre, os dados irão retornar e esvaziar a. Vamos implementar 
essas duas funcionalidades!
 (codigo > corrente->codigo)){
 anterior = corrente;
 corrente = anterior->próximo;
 }
 if (corrente == NULL){//não encontrou
 return(0);
 }else {
 strcpy(*v.nome,corrente->nome);
 *v.idade=corrente.idade;
 anterior->próximo = corrente->próximo;
 if (l->fim == corrente){//é o último elemento
 l->fim = anterior;
 }
 l->tamanho = l->tamanho – 1;
 free(corrente);
 return(1);
 }
 }
 }
}
A função que esvazia a lista é muito simples, navegamos 
na lista e vamos liberando a memória! Importante: devemos 
atualizar o cabeçalho da lista!
Pronto, agora já temos o ferramental básico para gerenciar 
o TAD LISTA! Sua f lexibilidade para as operações de inclusão 
e remoção de elementos o torna um pouco mais complexo que 
PILHAS e FILAS, mas temos certeza que você conseguiu 
entender como funciona.
//função que procura um elemento na lista com base no seu código
//se encontrar retorna o ponteiro para o nodo, caso contrário 
NULL
nodo* procura(LISTA * l, int codigo){
 nodo* corrente;
 if (vazia(l)) return(NULL);
 else {
 corrente = l->inicio;
 while ((corrente != NULL) && 
 (n->codigo != corrente->codigo)&&
 (n->codigo > corrente->codigo)){
 corrente = corrente->próximo;//ponteiro navega pela lista
 }
 if((corrente==NULL)|| (n->codigo != corrente->codigo)){
 //não encontrou
 return(NULL);
 }
 else{
 return(corrente); 
 }
 }
}
//função que esvazia a lista
void esvazia(LISTA * l){
 nodo* corrente, libera;
 if (!vazia(l)){
 corrente=l->inicio;//ponteiro auxiliar para navegar na lista
 while(corrente != NULL){
 libera = corrente;
 corrente = libera->próximo;
 free(libera);
 }
 //atualizar o cabeçalho da lista que agora está vazia
 l->tamanho = 0;
 l->inicio = NULL;
 l->fim = NULL;
 }
}
43ESTRUTURA DE DADOS
Desafio!
Altere as funções insere, remove e procura, considerando 
como critério de ordenação da lista o nome de uma pessoa! 
Devendo a lista ser em ordem crescente de nome! Temos 
certeza que você consegue! 
Amplie seus conhecimentos!
Pesquise sobre a implementação de listas duplamente 
encadeadas. O que muda nas funções para inserir e remover 
elementos? Quais as vantagens do encadeamento duplo?
Vamos lá! Verifique o que aprendeu nesta lição!
1. Construa uma tabela comparativa com os TAD PILHA, FILA e 
LISTA. Considere os seguintes aspectos de cada TAD: estrutura 
do nodo, lógica de funcionamento, operações primitivas, inclusão 
de novos elementos, exclusão de elementos. Ao final, analise 
a tabela que construiu e identifique as principais semelhanças 
e diferenças entre essas estruturas lineares.
2. Liste os tipos de listas encadeadas e descreva-os brevemente, 
diferenciando-os.
3. O que é o cabeçalho de uma lista e quais informações contêm?
4. Descreva a operação de inserir um novo elemento em uma 
lista.
5. Descreva a operação de remover um elemento de uma lista.
6. Considere a seguinte estrutura de informações de uma lista 
que gerencia coordenadas cartesianas (x,y).
 
Além disso, os elementos (nodos) são mantidos em ordem de 
inclusão, ou seja, novos nodos são sempre incluídos no fim 
da lista. Para implementar o TAD LISTA para esta estrutura 
de dados, quais funções precisam ser alteradas e quais não 
necessitam de ajustes?
7. Temos um conjunto de dados E, que define a ordem de 
códigos (separados por vírgulas) que serão progressivamente 
incluídos em uma lista. E={7, 20, 11, 30, 9, 5}.
Você deve fazer a representação gráfica (desenho) da lista, 
demonstrando sua situação após cada operação de inclusão 
de dados. Identificando início e fim da lista, tamanho e 
encadeamento entre os elementos. Tome por base a estrutura 
de funcionamento de uma lista simplesmente encadeada. 
struct dado {
 float x, y;
};
45ESTRUTURA DE DADOS
ÁRVORES (TREE)
Árvores na natureza possuem raiz, tronco, 
galhos e folhas. 
Usamos uma metáfora dessa estrutura para representar 
informações hierárquicas na construção de organogramas, 
árvores genealógicas e diretórios de arquivos, por exemplo. 
Vamos agora conhecer o Tipo Abstrato de Dados Árvore!
46ESTRUTURA DE DADOS
As árvores são um importante recurso computacional, 
ideal para organizar informações que possuem relações hie-
rárquicas. Vejamos um exemplo de estrutura hierárquica. O 
conjunto A contém os subconjuntos B, C e D. O subconjunto D 
possui os subconjuntos E, F e G. E o subconjunto G possui os 
subconjuntos H e I. A imagem a seguir apresenta essa relação 
entre os conjuntos:
Esta estrutura de conjuntos pode ser representada da 
seguinte forma hierárquica:
Assim, percebemos que hierarquias podem representar 
relações de pertinência (como no exemplo dos conjuntos), relação 
de subordinação (como no caso de um organograma) ou relação 
de ordem (como no caso de expressões matemáticas).
A partir dessa compreensão, vamos analisar a definição 
computacional das árvores!
Uma árvore é uma estrutura não linear, composta por um 
conjunto de nós. As árvores possuem um nó (nodo) especial, 
denominado raiz e este pode estar ligado às subárvores (zero 
ou mais). As subárvores de uma raiz são denominadas como seus 
filhos, logo, a raiz é o pai destas subárvores. Se considerarmos 
o exemplo dado, da estrutura hierárquica dos conjuntos, a raiz 
é A e suas subárvores são B, C e D. Assim, B, C e D são filhos 
de A. E A é pai de B, C e D. 
Toda subárvore é uma árvore, formando uma definição 
recursiva. No nosso exemplo, D é uma subárvore da raiz A, por 
outro lado, toda subárvore é uma árvore, portanto, D é uma raiz 
e tem suas subárvores E, F e G, que são seus filhos. 
Propriedade Fundamental das
Árvores
Somente existe um único caminho que liga cada nodo a raiz 
da árvore. Todo nodo somente tem um pai (ascendente).
47ESTRUTURA DE DADOS
A quantidade de subárvores de um nodo define o seu 
grau. Desta forma, no nosso exemplo, o grau de A é 3, pois 
possui 3 subárvores (filhos), já o grau de G é dois, pois possui 
2 subárvores, por outro lado é 0 (zero) o grau dos nós B, C, E, 
F, H e I, pois não possuem subárvores. Nós com grau 0 (zero) 
são denominados folhas. Analisando os graus de cada um dos 
nodos de uma árvore, podemos definir o grau da árvore, que 
é o maior grau de algum de seus nodos. No nosso exemplo, o 
grau da árvore é 3.
Outra informação importante sobre as árvores é a altura, 
que é medida a partir da raiz (altura 0 – zero) e contanto 1 a 
cada nível que se desce na hierarquia até chegar a folha mais 
distante. Portanto a altura da árvore é o caminho mais longo 
que liga a raiz a uma de suas folhas. No nosso exemplo a árvore 
tem altura 3: A – D (+1), D – G (+1), G – H (+1), assim entre 
A – H temos 3 passos em níveis da hierarquia.
Também precisamos conhecer o nível de um nodo, que 
é medido em relação a raiz. O nível da raiz é 0 (zero) e, partir 
disso, definimos os outros níveis. No nosso exemplo, o nível de 
A é 0 (zero), o nível de B, C e D é 1; o nível de E, F e G é 2; 
e o nível de H e I é 3. Essa é uma outra forma de considerar a 
altura de uma árvore, mensuramos o nível das folhas e o maior 
valor e teremos a altura da árvore.
A quantidade máxima de subárvores (filhos) que um nodo 
raiz pode ter determina o tipo de árvore, desta forma temos:
• Árvores Binárias: onde todos os nodos podem ter no 
máximo duas subárvores, filhos;
• Árvores Genéricas: onde a quantidade de subárvores de 
cada nodo é ilimitada. O exemplo dado, o qual estamos 
analisando, representa uma árvore genérica!
As árvores binárias, por terem um número limitado de 
subárvores para cada nodo, possibilitam uma implementação 
mais simples do que as árvores genéricas. Além disso, existem 
formas de mapear uma árvore genérica para uma estrutura de 
árvore binária – que veremos mais adiante. Por essas razões, o 
nosso estudo agora será focado nas árvores binárias!
Árvores Binárias
48ESTRUTURA DE DADOS
• Um nó raiz quepossui duas subárvores: subárvore esquerda 
(SAE) e subárvore direita (SAD);
• Uma subárvore é uma árvore (definição recursiva, ou seja, 
uma árvore é composta por árvores).
Esquematicamente, a árvore binária é:
Para percorrer e utilizar os elementos de uma árvore bi-
nária é possível utilizar três diferentes percursos, cada um irá 
tratar os elementos em uma ordem diferente. A denominação 
dos percursos está relacionada com o momento em que a raiz é 
tratada (utilizada). Os três tipos de percurso são:
Você já pensou que podemos representar expressões ma-
temáticas utilizando uma árvore binária?
Analise os operadores matemáticos básicos: + (soma), - 
(subtração), * (multiplicação), / (divisão). São todos operadores 
binários, ou seja, trabalham com dois operandos para realizar 
a operação. Considere a seguinte expressão: (4 + 12) * (3 – 1) 
/ (2 * 4) e a sua representação através de uma árvore binária:
Outra aplicação que pode ser facilmente representada 
através de árvores binárias são os jogos de diversos campeonatos 
que envolvem dois times!
Assim, podemos definir uma árvore da seguinte forma:
• Uma árvore vazia;
49ESTRUTURA DE DADOS
Vejamos como ficarão os elementos a partir de cada um 
dos percursos:
• Percurso In-fixo: 4 + 12 * 3 – 1 / 2 * 4
• Percurso Pré-fixo: / * + 4 12 – 3 1 * 2 4
• Percurso Pós-fixo: 4 12 + 3 1 - * 2 4 * /
Agora, vamos considerar um exemplo de uma árvore 
binária, onde cada nodo contém um número:
• Percurso In-fixo, também denominado ‘em ordem’: nesse 
caso, é percorrida a subárvore esquerda, depois utiliza-se 
a raiz e depois é percorrida a subárvore à direita. (SAE, 
Raiz, SAD)
• Percurso Pré-fixo, também denominado ‘pré-ordem’: 
nesse caso, utiliza-se primeiro a raiz, depois se percorre 
a subárvore esquerda e, por fim, a subárvore à direita. 
(Raiz, SAE, SAD)
• Percurso Pós-fixo, também denominado ‘pós-ordem’: 
aqui, primeiro, percorremos a subárvore esquerda, depois 
a subárvore direita e, por fim, utilizamos a raiz. (SAE, 
SAD, Raiz)
Vamos retomar o exemplo da expressão aritmética para 
entender cada um dos tipos de percursos:
50ESTRUTURA DE DADOS
Vejamos como ficarão os números a partir de cada um 
dos percursos:
• Percurso In-fixo: 4, 15, 18, 25, 27, 30, 35, 40, 70, 80, 90 
(raiz no meio)
• Percurso Pré-fixo: 40, 25, 15, 4, 18, 30, 27, 35, 80, 70, 
90 (raiz primeiro)
• Percurso Pós-fixo: 4, 18, 15, 27, 35, 30, 25, 70, 90, 80, 
40 (raiz no fim)
Árvore Binária de Busca
Uma caso especial das árvores binárias são as árvores 
binárias de busca, que são construídas seguindo um critério 
de ordenação, logo, considerando a raiz, todos os elementos 
da subárvore esquerda (SAE) possuem valores menores que a 
raiz e todos os elementos da subárvore direita (SAD) possuem 
valores maiores que a raiz. Esse critério determina a forma que 
os elementos serão incluídos na árvore e deve ser respeitado, 
quando elementos forem excluídos.
Assim, considerando a seguinte sequência de valores V a 
serem incluídos em uma árvore de pesquisa binária V = {40, 3, 
50, 10, 5, 7, 14, 45, 60}. O primeiro elemento (40) será a raiz 
da árvore e, a partir desse os outros elementos serão incluídos, 
(3) é menor que (40), portanto, será incluído na SAE, já (50) é 
maior que (40), consequentemente, será incluído na SAD. De-
pois, (10) é menor que (40), logo, será incluído na SAE, onde já 
temos o valor (3), e (10) é maior que (3), portanto será incluído 
na sua SAD. Assim, subsequentemente, veja como ficará a ár-
vore binária de busca para esse conjunto de entrada de dados:
Perceba que para manter a visualização da árvore binária 
mais equilibrada, foram colocados nodos sem valor (/).
51ESTRUTURA DE DADOS
Agora, vejamos um exemplo de uma árvore binária, o qual 
parece uma árvore binária de busca, mas não segue estritamente 
o critério deste tipo de árvore:
Esta árvore parece seguir o critério da árvore binária de 
busca, pois se analisarmos isoladamente, cada raiz e seus filhos 
diretos respeitam a regra. No entanto, a mesma refere-se a toda 
a SAE, que precisa ter valores menores que a raiz e toda a SAD 
precisa ter elementos maiores que raiz. Veja que o valor (25) 
está na SAE da raiz (20), mas não poderia estar, pois é maior 
que a raiz. Também note que o valor (19) está na SAD da raiz 
(20), mas não poderia estar, visto que é menor que a raiz. Dessa 
forma, essa é uma árvore binária, mas não é uma árvore binária 
de busca.
Outra característica da árvore binária de busca é que ao 
utilizar um percurso infixo (em ordem) obtemos uma lista or-
denada dos elementos. 
Implementação da árvore binária de busca
Como acontece com os outros tipos abstratos de dados, 
precisamos definir a estrutura de armazenamento da árvore e 
as operações de manipulação desta estrutura. Comecemos pela 
estrutura, que na linguagem C fica:
typedef struct nodo{
 int info;
 struct nodo * esquerda;
 struct nodo * direita;
}nodo;
52ESTRUTURA DE DADOS
Agora vamos definir o conjunto de operações primitivas 
do TAD Árvore, sua interface:
A seguir, veremos a implementação destas funções. Você 
perceberá que a maioria delas utiliza recursividade! Isto é práti-
co, uma vez que a estrutura da árvore também é recursiva (uma 
árvore possui subárvores, que são árvores)!
Iniciamos pela implementação da função que inclui ele-
mentos no TAD ARVORE BINÁRIA DE BUSCA. Nessa, 
verificamos se o ponteiro para a árvore é NULL, se for ali, será 
adicionado o novo elemento, do contrário, comparamos o valor 
do novo elemento com aquele que está no nodo corrente. Já, 
se for menor, chamamos recursivamente a função para incluir 
o novo nodo à esquerda, caso contrário, ou seja, se for maior, 
chamamos recursivamente a função para incluir o novo nodo à 
direita. Veja na página a seguir essa implementação:
//Inclusão de um nodo na árvore a partir da 
raiz
void insere_folha(nodo ** arv, int info);
//Caminhamento pre-ordem
void pre_ordem(nodo * arv);
//Caminhamento em-ordem
void em_ordem(nodo * arv);
//Caminhamento pos-ordem
void pos_ordem(nodo * arv);
//Pesquisar um nodo
void pesquisar_nodo(nodo * arv, char pesq);
//retornar o nível de um nodo
int nivel_do_nodo(nodo * arv, char info);
//liberar a memória da árvore
void libera(nodo *arv);
//remover um nodo da árvore
nodo* retira (nodo* arv, int v);
O que é Recursividade?
A recursividade é a definição de uma rotina (função ou método) 
que pode chamar a si mesma. Em geral, uma definição recursiva é 
definida por casos: um número limitado de casos base (que finalizam o 
processo recursivo); e casos recursivos (que chamam a própria rotina, 
normalmente modificando os parâmetros). 
De maneira simplificada: pense que temos um processo de subir uma 
escada, onde o parâmetro é um ponteiro para a escada, neste verificamos 
se chegamos ao fim da escada (esse é nosso caso base), se sim, termina, 
caso contrário, subimos um degrau e chamamos, recursivamente, o 
processo de subir a escada para o resto da mesma.
Pesquise mais sobre a implementação de funções recursivas e analise 
alguns exemplos clássicos: Fibonacci recursivo e Fatorial recursivo.
53ESTRUTURA DE DADOS
Depois de construir a árvore, temos que definir as fun-
ções para realização dos percursos (caminhamento), ou seja, 
as funções que irão apresentar (mostrar) ou fazer outro uso de 
todos os nodos da árvore. Assim, temos, na sequência, funções 
que implementam os percursos: em pré-ordem, em-ordem e em 
pós-ordem. Cada uma se diferencia pelo momento em que a raiz 
é mostrada (ou utilizada). Se desejarmos mostrar os elementos 
da Árvore Binária de Busca, devemos utilizar o percurso em-or-
dem (infixo). As três funções a seguir têm por objetivo mostrar 
todos os elementos conforme o percurso escolhido.
A seguir temos a função que faz o percurso infixo (em-
-ordem), que apresentará os elementos em ordem crescente!
//Inclusão de um nodo na árvore a partir da raiz
void insere_folha(nodo ** arv, int info){
 if (*arv == NULL){
 *arv = cria_elemento(info);
 }else{