EDD_ebook

Prévia do material em texto

ESTRUTURA DE DADOS
ESTRUTURA DE DADOS
Copyright © UVA 2019
Nenhuma parte desta publicação pode ser reproduzida por qualquer 
meio sem a prévia autorização desta instituição.
Texto de acordo com as normas do Novo Acordo Ortográfico 
da Língua Portuguesa.
AUTORIA DO CONTEÚDO
Alfredo Nazareno Pereira Boente
REVISÃO
Clarissa Penna
Theo Cavalcanti
PROJETO GRÁFICO
UVA
DIAGRAMAÇÃO
UVA
SUMÁRIO
Apresentação
Autor
6
7
Estruturas lineares encadeadas: listas 28
• Lista simplesmente encadeada
• Lista duplamente encadeada
• Lista circular
UNIDADE 2
8
• Estrutura de dados e seus tipos
• Vetores e matrizes de dados
• Ponteiros ou apontadores
Introdução às estruturas de dados
UNIDADE 1
SUMÁRIO
Grafos e árvores 70
• Grafos e árvores
• Árvores binária e AVL
• Buscas em árvore
UNIDADE 4
52
• Trabalhando com filas
• Trabalhando com pilhas
• Filas circulares
Estruturas lineares encadeadas: filas e pilhas
UNIDADE 3
6
A estrutura de dados tem por objetivo permitir ao estudante conhecer os conceitos bási-
cos de estruturas e seus tipos, implementando soluções computacionais com as princi-
pais estruturas de dados: vetores, matrizes, ponteiros/apontadores, lista, fila, pilha, grafos 
e árvores.
A disciplina está dividida logicamente em quatro unidades, distribuídas da seguinte forma:
• Na Unidade 1, serão abordadas as estruturas de dados e seus tipos, implementando 
soluções com vetores, matrizes e ponteiros.
• Na Unidade 2, será apresentada a estrutura lista nos formatos linear e circular, vi-
sando à implementação de soluções computacionais com essa estrutura de dados.
• Na Unidade 3, serão implementadas soluções algorítmicas com as estruturas de-
dados fila e pilha.
• Na Unidade 4, serão estudados os conceitos de grafos e árvores, buscando imple-
mentar programas com árvores de dados, árvores binárias e árvores AVL.
APRESENTAÇÃO
7
ALFREDO NAZARENO PEREIRA BOENTE
Pós-doutorado em Neurociência e Sistemas Lógicos aplicados a Gestão Empresarial, 
Educação e Pesquisa Experimental pelo Programa de Pós-Graduação em História das 
Ciências e das Técnicas e Epistemologia da Universidade Federal do Rio de Janeiro – 
HCTE/UFRJ (2014), doutorado em Ciências da Engenharia de Produção pelo Instituto 
Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia da UFRJ – Coppe/
UFRJ (2013), doutorado em Processamento de Dados pela American World University 
– AWU (EUA) (2006), mestrado em Administração e Desenvolvimento Empresarial pela 
Universidade Estácio de Sá – Unesa (2009), mestrado em Ciências da Computação pela 
Universidad de La Habana (Cuba, 2003), mestrado em Engenharia de Software pela AWU 
(EUA, 2002), especialização em Análise de Sistemas pela Unesa (2000), especialização 
em Docência Superior pela Universidade Candido Mendes – Ucam (2001), especializa-
ção em Tecnologia em Banco de Dados pela Unesa (2001), especialização em Ciências 
da Computação pela Universidad de La Habana (Cuba, 2002), especialização em Ad-
ministração Escolar pela Unesa (2003), especialização em Logística Empresarial pela 
Faculdade Internacional Signorelli (2016), graduação em Processamento de Dados com 
ênfase em Projeto e Análise de Sistemas pelas Faculdades Reunidas Professor Nuno 
Lisboa – FRNL (1996), graduação em Processos Gerenciais – Gestão Empresarial pela 
Universidade Veiga de Almeida – UVA (2018), graduação em Engenharia de Produção 
pela UVA (2019).
AUTOR
Introdução às 
estruturas de dados
UNIDADE 1
9
Esta unidade é importante para o estudante porque apresenta as principais estruturas de
dados e seus tipos, além de implementar soluções com o uso das estruturas vetores, 
matrizes e ponteiros/apontadores — alocação dinâmica.
INTRODUÇÃO
Nesta unidade, você será capaz de:
• Analisar as estruturas de dados, implementando soluções algorítmicas com 
vetores, matrizes e ponteiros — alocação dinâmica.
OBJETIVO
10
Estrutura de dados e seus tipos 
No que tange ao estudo das estruturas de dados, segundo Forbellone e Eberspächer 
(2005),a partir dos tipos de dados primitivos, serão compostos os tipos de dados 
construídos, ora denominados estrutura de dados. Cada estrutura de dados tem um 
tipo peculiar de organização e forma de manipulação dos dados, o que, teoricamente, 
constituirá certa estrutura de dados especificamente.
Então, é verdadeiro afirmar que uma estrutura de dados se refere a uma forma única e 
peculiar de armazenamento e organização de dados que se mostra eficiente quando é 
adequada a diferentes tipos de aplicações, com suas tarefas específicas.
Decerto, algoritmos e estruturas de dados são considerados temas fundamentais para 
o estudo da computação. Em linhas gerais, um problema pode ser resolvido facilmente 
por uma estrutura de dados específica, embora todas as estruturas de dados possam 
ser utilizadas para resolver o mesmo tipo de problema. Pugga e Rissetti (2009) afirmam 
que a escolha da estrutura de dados mais adequada para certo estudo inclui os padrões 
de acesso, os mecanismos de busca e os requisitos de armazenamento de dados.
As estruturas de dados podem ser apresentadas como estruturas homogêneas ou 
heterogêneas. 
Elas são ditas homogêneas quando 
o conjunto de dados apresentado 
por essa estrutura de dados é um 
dado primitivo do mesmo tipo.
Já as estruturas de dados hetero-
gêneas apresentam um conjunto 
de dados formado por dados primi-
tivos de tipos diferentes.
As estruturas de dados são utilizadas para armazenar dados considerados de média 
complexidade, visando ao atendimento das necessidades inerentes de um programa, a 
fim de solucionar certo problema.
Na literatura existem diferentes estruturas de dados, cada qual com suas características 
e especificidades.
11
Tipos de estruturas de dados
Diversas estruturas de dados podem ser utilizadas a fim de buscar a solução de um 
problema computacionalmente. Serão apresentadas as seguintes estruturas de dados: 
vetores, matrizes, ponteiros, listas, filas, pilhas, grafos e árvores. 
Mantenha o foco e vamos conhecê-las!
Vetor (array)
Uma estrutura indexada é um conjunto de elementos de dados do mesmo tipo acessa-
dos por meio de índices, equivalentes à sua posição na estrutura (PUGGA; RISSETTI, 
2009). Por analogia, podemos imaginar algo semelhante a um texto ou livro, em que os 
títulos estão especificados no sumário, com a designação da respectiva página. Dessa 
forma, para que certo assunto seja encontrado, basta localizar no índice a página para 
acessar seu conteúdo de forma direta e objetiva.
Um vetor é uma estrutura unidimensional de dados indexada com dados do mesmo
tipo, também conhecida como array, que necessita apenas de um índice para identificar
e localizar um determinado elemento nela armazenado. 
Um vetor pode ser representado por uma linha de contêiner ou espaços predefinidos e 
identificados por índice, conforme ilustrado na Figura 1.
Dessa forma, tem-se o vetor como uma coleção de variáveis do mesmo tipo que com-
partilham o mesmo nome e o mesmo endereço de memória em posições consecutivas.
Figura 1: Representação de um vetor.
Fonte: Pugga e Rissetti (2009).
índice: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
nome: temp 18 17 20 26 32 29 15 12 16 21
12
Matriz
Uma matriz nada mais é que um vetor multidimensional caracterizado pelo uso de,pelo 
menos, duas dimensões do mesmo endereço de memória com dados do mesmo tipo. 
Apresenta conceito equivalente ao do estudo de matrizes da disciplina Álgebra Linear, 
ou seja, todas as propriedades das matrizes existentes na matemática podem ser ado-
tadas em programas que manipulam essa estrutura de dados em busca de solução de 
problemas.
As estruturas indexadas, que necessitam de mais de um índice para identificar um de 
seus elementos, são chamadas de matriz de dimensão n, sendo que n representa o nú-
mero de índices requeridos (PUGGA; RISSETTI, 2009).
Então, um elemento da matriz pode ser identificado por um número de linha e coluna 
dessa matriz, conforme ilustrado na Figura 2.
Ponteiro
De acordocom Mizrahi (2008), o nome de uma variável indica o que será armazenado 
nela. A isso dá-se o nome de variável significativa. O endereço de uma variável é um pon-
teiro. Seu valor indica em que parte da memória do computador a variável está alocada. 
Uma variável ponteiro, também conhecida tecnicamente como variável apontadora (ver 
Figura 3), é aquela que, no lugar de armazenar conteúdo de dado, guarda o espaço, o 
endereço de memória de outra variável, para posterior manipulação.
Figura 2: Representação de uma matriz.
Fonte: Pugga e Rissetti (2009).
Quantidade
Va
lo
r (
R$
)
n
...
5
4 Região X
3
2
1
1 2 3 4 5 ... n
13
Ponteiros ou apontadores proporcionam um método de acesso à variável sem que haja 
a necessidade de a referenciar diretamente, ou seja, realiza o modo indireto de acesso.
Lista
Uma lista é uma estrutura de dados linear que pode ser caracterizada como encadeada 
ou circular, composta por nós indicativos do próximo elemento da lista, do primeiro ao 
penúltimo, pois o último elemento da lista não aponta para ninguém (NULL).
A Figura 4, conforme explica Forbellone e Eberspächer (2005), ilustra um exemplo clás-
sico de lista de tarefas a serem cumpridas no centro da cidade do Rio de Janeiro. Ini-
cialmente, cada atividade é relacionada conforme vai surgindo na memória, até que se 
esgotem.
Figura 3: Representação de ponteiro.
Fonte: Elaborada pelo autor (2019).
Índices 112 113 114 115 116 117 118 119 120 121
Conteúdos 0 0 1 0 2 1 113 0 1 0
Figura 4: Exemplo de uma lista de tarefas.
Fonte: Forbellone e Eberspächer (2005).
Lista de tarefas
1. Pagar as contas no banco.
2. Comprar os livros na livraria.
3. Deixar o carro no estacionamento.
4. Pegar algumas fitas na videolocadora.
5. Enviar correspondências pelo correio.
6. Buscar as fotos reveladas.
7. Autenticar documentos no cartório.
8. Passar na banca de jornal.
14
Subentende-se, portanto, que a primeira tarefa da lista a ser realizada é a de número 1 
— pagar as contas no banco. Em seguida, a tarefa 2 — comprar os livros na livraria — é a 
próxima, e assim por diante, até que a tarefa número 8 — passar na banca de jornal — seja 
executada, terminando, assim, todas as tarefas da lista. Note que, depois da tarefa 8, não 
existem outras a serem executadas.
Fila
As listas encadeadas, filas e pilhas são, na verdade, listas de dados cuja diferença principal 
está na forma de acesso à inclusão e à remoção de seus elementos (PUGGA; RISSETTI, 
2009). O conceito de fila de programação é o mesmo de quando esperamos para sermos 
atendidos em determinada ordem: o primeiro elemento a entrar na fila será o primeiro a 
sair dela. Esse conceito é tecnicamente conhecido como Fifo (first in, first out), ou seja, 
o primeiro que entra na fila é o primeiro a sair dela. Em português, também é conhecido 
como Peps (primeiro a entrar, primeiro a sair), conforme ilustra a Figura 5.
Figura 5: Estrutura de dados fila.
Fonte: Pugga e Rissetti (2009).
Pilha
As pilhas, de acordo com Pugga e Rissetti (2009), são estruturas de dados conhecidas 
como listas Lifo (last in, first out), ou seja, o último elemento a entrar será o primeiro a sair. 
Em português, também é conhecida como Ueps (último a entrar, primeiro a sair).
Novos elementos 
são armazenados 
no fim da fila
O primeiro elemento a 
entrar será o primeiro 
a sair (Peps)
Elementos armazenados na fila
15
Na verdade, trata-se de uma estrutura do tipo lista linear, em que todas as operações 
feitas — inclusão e remoção — são realizadas por um único extremo, pelo topo da pilha, 
conforme ilustra a Figura 6.
Figura 7: Representação de grafo.
Fonte: Simões-Pereira (2014).
Grafo
No estudo da teoria dos grafos, um grafo representa um conjunto de pontos, denomina-
dos vértices, ligados por retas, denominadas arestas, que, dependendo do tipo de aplica-
ção, poderá apresentar setas ou não. Segundo Simões-Pereira (2014), matematicamente, 
dizemos que um grafo é representado da seguinte forma: G = (V, E), que se refere a um 
sistema formado por um conjunto V de elementos denominados vértices e um conjunto 
E de arestas, conforme ilustra a Figura 7.
Figura 6: Estrutura de dados pilha.
Fonte: Elaborada pelo autor (2019).
n Tamanho da pilha
(...)
5
5 B 4
Topo D 3
A 2
1 C 1
Base Itens
Pilha
a u
x
v b
16
Quando um grafo tem arestas que apresentam setas nas extremidades para 
representar o sentido, ou seja, a direção do fluxo, ele é chamado tecnicamente 
de grafo dirigido, ou dígrafo.
Saiba mais
Árvore
A estrutura de dados árvore é uma lista na qual cada elemento possui dois ou mais su-
cessores, porém todos os elementos possuem um, e apenas um, antecessor, conforme 
ilustra a Figura 8 (FORBELLONE; EBERSPÄCHER, 2005).
MIDIATECA
Acesse a midiateca da Unidade 1 e veja o conteúdo complementar indicado 
pelo professor sobre linguagem C.
Figura 8: Exemplo de árvore.
Fonte: Forbellone e Eberspächer (2005).
A
B
C
G M
F
E
D H
I
J
L
17
Para ler uma abordagem mais aprofundada sobre vetores e matrizes de dados, 
com exercícios propostos para fixação de conteúdo, sugerimos o capítulo 7 
(p.181-193) do seguinte livro, disponível na Biblioteca Virtual:
MIZRAHI, V. V. Treinamento em linguagem C. 2. ed. São Paulo: Pearson 
Education do Brasil, 2008.
Dica
18
Vetores e matrizes de dados 
Uma estrutura vetor representa um endereço de memória em que serão armazenados 
diversos dados de acordo com o dimensionamento dado a ele, na própria definição, no-
momento da criação da variável vetor (PUGGA; RISSETTI, 2009).
Imagine você escrever um programa para ler três notas de alunos de uma turma para 
calcular sua média aritmética sem o uso de vetor. A solução poderia ser algo assim:
/* Comentario: Calculo de media de 3 notas SEM vetor */
# include “stdio.h”
float nota1, nota2, nota3, media;
void main( )
{
 printf (“Digite a nota 1: “); scanf (“%f”, nota1);
 printf (“Digite a nota 2: “); scanf (“%f”, nota2);
 printf (“Digite a nota 3: “); scanf (“%f”, nota3);
 media = (nota1 + nota2 + nota3) / 3;
 printf (“Media = %.2f\n”, media);
}
/* Comentario: Calculo de media de 3 notas COM vetor */
# include “stdio.h”
float notas[3], media;
int i;
void main( )
{
 for (i=1; i<=3; i++)
 {
 printf (“Digite a nota %d: “, i); 
 scanf (“%f”, notas[i]); 
Agora vamos escrever um programa para solucionar o mesmo problema, porém com o 
uso de vetor unidimensional:
19
media += notas[i];
 }
 media /= 3;
 printf (“Media = %.2f\n”, media);
}
/* programa exemplo de vetor */
#define DIM 5
#include <stdio.h>
/* Corpo principal do programa */
void main ( )
{
 int i, vetor1[DIM], vetor2[DIM];
 for ( i=0; i<DIM; i++ )
 {
 printf (“vetor1[%d]=“, i);
 scanf (“%d”, &vetor1[ i ]);
 }
 for ( i=0; i<DIM; i++ )
 {
 printf (“vetor2[%d]=“, i);
 scanf (“%d”, &vetor2[ i ]);
 }
 for ( i=0; i<DIM; i++ )
 printf (“vetor1[%d] + vetor2[%d] = %d\n”, i, i, vetor1[ i ] + vetor2[ i ]);
}
Vejamos outro exemplo prático do uso de vetor unidimensional:
Por definição, uma matriz é uma coleção de variáveis do mesmo tipo que compartilham 
o mesmo nome (MIZRAHI, 2008). Dessa forma, quando temos vetores com mais de uma 
dimensão, dizemos estar manipulando vetores multidimensionais ou, simplesmente, ma-
trizes. Veja o exemplo a seguir:
20
/* Comentario: Exemplo de MATRIZ */
#include <stdio.h>
#define LIN 2
#define COL 2
void main ( )
{
 int
 mat [LIN][COL],
 i, j;
 for ( i=1; i<3; i++ )
 for ( j=1; j<3; j++ )
 {
printf (“\nEntre com o elemento[%d][%d]”, i, j);
 scanf (“%d”, &mat[ i ][ j ]);
 }
 for ( i=1; i<3; i++ )
 for ( j=1; j<3; j++ )
 if ( i == j )
 printf (“\n%d”, mat[ i ][ j ]);
}
O programa exemplo apresentado permite criar uma matriz quadrada de ordem 2, ou 
seja, uma matriz 2x2 cujos elementos são valores inteiros. Ao final do processamento 
serão exibidos todos os elementos que façam parte da diagonal principal.
MIDIATECA
Acesse a midiateca da Unidade 1 e veja o conteúdo complementar indicado 
pelo professor sobre matrizes.
21
Ponteiros ou apontadores 
Como já estudamos anteriormente,um ponteiro, ou apontador, é uma variável que arma-
zena no seu espaço de memória um endereço de memória referente a outra variável no 
lugar de armazenar um conteúdo de dado. A alocação dinâmica de memória em tempo 
de execução é realizada em linguagem C por meio de ponteiro, como podemos analisar 
no código de programa abaixo:
/* Comentario: alocacao de memoria dinamica */
#include <stdio.h>
#include <malloc.h>
#include <dos.h>
void main ( )
{
// Declaracao do ponteiro
 int
 *ptr;
 ptr = ( int * ) malloc( sizeof( int ));
 *ptr = 3;
 system(“CLS”);
 printf (“Conteudo do ponteiro: %d\n\n”, *ptr);
 system(“PAUSE”);
}
Note que, no programa apresentado, atribuímos à variável ptr um valor retornado por 
uma função chamada malloc( ), a qual é declarada na biblioteca padrão malloc.h. Para 
que possamos entender a instrução ptr = ( int * ) malloc( sizeof( int )), vamos dividi-la em 
partes:
- O operador sizeof( ) devolve o tamanho, em bytes, do tipo ou da expressão entre parên-
teses.
- A função malloc( ) tem o objetivo de retornar um ponteiro para uma área livre de memó-
ria a ser identificada por ela.
22
Dessa forma, a instrução ptr = ( int * ) malloc( sizeof( int )) cria dinamicamente uma variá-
vel inteira referenciada por *ptr. Podemos, ao mesmo tempo, trabalhar com muitas variá-
veis do tipo ponteiro na memória do computador. A determinação referente à quantidade 
necessária para utilização em um determinado programa depende exclusivamente de a 
que o programa se propõe.
Veja a saída produzida pelo programa:
Vamos analisar outro exemplo de ponteiro/apontador:
/* Comentario: Outro exemplo de ponteiro/apontador */
#include <stdio.h>
#include <conio.h>
#include <dos.h>
int main(void)
{
int 
 num = 13;
// Declaracao do ponteiro
int 
 *ptr;
23
// Atribuicao do endereco da variavel num ao ponteiro ptr
ptr = &num;
system(“CLS”);
printf (“\nUtilizando ponteiros”);
printf (“\n\nConteudo da variavel num: %d”, num);
printf (“\nEndereco da variavel num: %x”, &num);
printf (“\nConteudo da variavel ponteiro ptr: %x”, ptr);
system(“PAUSE”);
return(0);
}
Veja a saída produzida pelo programa:
Toda variável ponteiro, ou apontador, depois da especificação de seu tipo, apre-
senta um asterisco à esquerda, identificando, portanto, que se trata, efetiva-
mente, de uma variável ponteiro.
Saiba mais
24
MIDIATECA
Acesse a midiateca da Unidade 1 e veja o conteúdo complementar indicado 
pelo professor sobre ponteiros.
NA PRÁTICA
Você é programador da empresa Renalf Mega Data e seu gerente de projetos 
de sistemas solicitou que você fizesse um programa de computador que imple-
mentasse um vetor de 50 posições para armazenamento de dados, fornecido 
via teclado, para cada uma das seguintes variáveis: código, mercadoria, quanti-
dade e preço unitário. Deve-se armazenar também o preço total, que deverá ser 
calculado automaticamente pelo sistema (quantidade versus preço unitário). 
No final do processamento, imprimir todos os códigos das mercadorias e seus 
respectivos preços totais para todos os registros cuja quantidade seja igual ou 
superior a 100 unidades.
/* Comentario: Uma possivel solucao */
#include <stdio.h>
 int codigo[50], quantidade[50];
 char mercadoria[10][50];
 float preco_unitario[50], preco_total[50];
 int i;
void main( )
{
/* Entrada de Dados */ 
 for(i=1; i<=50; i++)
 {
 printf(“\nCodigo ? “); scalf(“%d”, &codigo[ i ]);
 printf(“\nMercadoria ? “); scalf(“%s”, &mercadoria[ i ]);
 printf(“\nQuantidade ? “); scalf(“%d”, &quantidade[ i ]);
 printf(“\nPreco Unitario ? “); scalf(“%f”, &preco_unitario[ i ]);
 preco_total[ i ] = quantidade[ i ] * preco_unitario[ i ];
}
25
/* Saida de Informacoes */
 for(i=1; i<=50; i++)
 if(quantidade[ i ] >= 100)
 printf(“\nCodigo: %d Preco Total: %.2f “, codigo[ i ], preco_total[ i ]);
}
26
Resumo da Unidade 1
Nesta unidade, você conheceu as principais estruturas de dados e seus tipos, implemen-
tou soluções computacionais que envolvessem o uso de vetores e matrizes de dados, 
assim como a estrutura ponteiro/apontador — alocação dinâmica.
Para complementar seus estudos, sugerimos que leia os livros indicados nas referências. 
Nesta unidade, destacaram-se o conhecimento das estruturas de dados e seus 
tipos, a manipulação dos programas de computador com o uso de vetores e 
matrizes de dados e o desenvolvimento de algoritmos computacionais de alo-
cação dinâmica com ponteiros e apontadores.
CONCEITO
27
Referências 
FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. Lógica de programação: a construção de 
algoritmos e estruturas de dados. 3. ed. São Paulo: Pearson Prentice Hall, 2005. Bibliote-
ca Virtual. 
MIZRAHI, V. V. Treinamento em linguagem C. 2. ed. São Paulo: Pearson Education do 
Brasil, 2008. Biblioteca Virtual. 
PUGGA, S.; RISSETTI, G. Lógica de programação e estrutura de dados com aplicações 
em Java. 3. ed. São Paulo: Pearson Prentice Hall, 2009. Biblioteca Virtual.
SIMÕES-PEREIRA, J. M. S. Grafos e redes: teoria e algoritmos básicos. Rio de Janeiro: 
Interciência, 2014. Biblioteca Virtual.
Estruturas lineares 
encadeadas: listas
UNIDADE 2
29
Esta unidade é importante para que o estudante compreenda os processos de manipula-
ção da estrutura de dados lista, com suas possíveis variações de encadeamento — sim-
ples e duplamente encadeada —, assim como operações elementares com lista circular.
INTRODUÇÃO
OBJETIVO
Nesta unidade, você será capaz de:
• Compreender a estrutura linear encadeada por meio de lista simplesmente 
encadeada.
• Implementar algoritmo computacional com lista duplamente encadeada.
• Desenvolver soluções computacionais com a estrutura de dados lista circular.
30
Lista simplesmente encadeada
De acordo com Forbellone e Eberspächer (2005), denomina-se lista, ou lista encadea-
da, um conjunto de elementos individualizados em que cada elemento referencia outro 
como sucessor.
As listas são estruturas de dados complexas que podem ser trabalhadas sob três confi-
gurações distintas: 
• Lista simplesmente encadeada, que será estudada neste tópico.
• Lista duplamente encadeada, que será estudada no segundo tópico.
• Lista circular, que será estudada no terceiro tópico.
A lista simplesmente encadeada refere-se a uma sequência de nós em que cada nó 
possui armazenado certo dado e também o endereço do seguinte nó da lista, conforme 
ilustra a Figura 1.
Lista refere-se a um ponteiro para o primeiro nó efetivo da lista, que contém, neste caso, 
o valor “1”, assim como um ponteiro para o próximo nó dessa lista. Observe que o último 
nó aponta para NULL, ou seja, indica o final da lista.
Note que o sentido da lista é linearmente descrito da esquerda para a direita. 
Então, o início da lista se dá à esquerda, enquanto o final da lista simplesmente 
encadeada termina à direita.
Curiosidade
Figura 1: Representação de uma lista simplesmente encadeada.
Fonte: Elaborada pelo autor (2019).
1 2 3Lista
31
Vejamos, em seguida, um programa exemplo de lista simplesmente encadeada:
/* Comentario: Lista Simplesmente Encadeada */
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
/* Comentario: Declaracao da Estrutura Nodo */
typedef struct sNodo 
{
 int info;
 struct sNodo *prox;
} Nodo;
/* Comentario: Declaracao da Estrutura Lista Simplesmente Encadeada */
typedef struct sListaSimplesEnc 
{
 Nodo *prim;
} ListaSimplesEnc;
/* Comentario: Criar Lista Vazia */
void criarLista(ListaSimplesEnc *pList) 
{
 pList->prim = NULL;
}
/* Comentario: Mostrar Elementos da Lista */
void mostrarLista(ListaSimplesEnc *pList) 
{
 Nodo *p;
 printf(“Lista: “);
 
 for (p = pList->prim; p != NULL; p = p->prox) 
 {
 printf(“%d -> “, p->info);
 }
 printf(“NULL\n”);
}
/* Comentario: Inserir no Inicio da Lista */
void inserirIni(ListaSimplesEnc *pList, int v) 
{
 Nodo *novo;
 
 novo = (Nodo*)malloc(sizeof(Nodo));
 if (novo != NULL) 
 {
32
novo->info = v;
 novo->prox = pList->prim;
 pList->prim = novo;
 }
 else 
 {
 printf(“Memória Insuficiente\n”);
 }
}
/* Comentario: Remover no Inicio da Lista */
void removerIni(ListaSimplesEnc*pList) 
{
 Nodo *pAux = pList->prim;
 if (pAux != NULL) 
 {
 pList->prim = pList->prim->prox;
 free(pAux);
 printf(“Valor Removido\n”);
 }
 else 
 {
 printf(“Lista Vazia\n”);
 }
}
/* Comentario: Inserir Elemento em Ordem na Lista */
void inserirOrd(ListaSimplesEnc *pList, int v) 
{
 Nodo *novo;
 novo = (Nodo*)malloc(sizeof(Nodo));
 if (novo != NULL) 
 {
 novo->info = v;
 Nodo *pAtu, *pAnt;
 pAnt = NULL;
 pAtu = pList->prim;
 while (pAtu != NULL && pAtu->info < v) 
 {
 pAnt = pAtu;
 pAtu = pAtu->prox;
 }
 novo->prox = pAtu; 
33
 if (pAnt != NULL) 
 { 
 pAnt->prox = novo;
 }
 else 
 {
 pList->prim = novo;
 }
 }
 else 
 {
 printf(“Memória Insuficiente\n”);
 }
}
/* Comentario: Remover um Elemento Especifico da Lista */
void removerEle(ListaSimplesEnc *pList, int v) 
{
 Nodo *pAtu, *pAnt;
 pAnt = NULL;
 pAtu = pList->prim;
 while (pAtu != NULL && pAtu->info != v) 
 {
 pAnt = pAtu;
 pAtu = pAtu->prox;
 }
 if (pAnt != NULL) 
 {
 if (pAtu != NULL) {
 pAnt->prox = pAtu->prox;
 free(pAtu);
 printf(“Valor Removido\n”);
 }
 else 
 {
 printf(“Valor não encontrado\n”);
 }
 }
 else 
 {
 printf(“Lista Vazia\n”);
 }
}
/* Comentario: Remover Todos os Elementos da Lista */
void removerTudo(ListaSimplesEnc *pList) 
{
 Nodo *pAux = pList->prim;
34
 if (pAux != NULL) 
 {
 while (pAux != NULL) 
 { 
 pList->prim = pAux->prox;
 free(pAux);
 pAux = pList->prim;
 } 
 printf(“Todos os elementos foram removidos!\n”);
 }
 else 
 {
 printf(“Lista Vazia\n”);
 }
}
/* Comentario: Alterar Elemento da Lista */
void alterarEle(ListaSimplesEnc *pList, int v1, int v2) 
{
 Nodo *pAtu, *pAnt;
 pAnt = NULL;
 pAtu = pList->prim;
 while (pAtu != NULL && pAtu->info != v1) 
 {
 pAnt = pAtu;
 pAtu = pAtu->prox;
 }
 if (pAnt != NULL) 
 {
 if (pAtu != NULL) 
 {
 pAtu->info = v2;
 printf(“Valor alterado\n”);
 }
 else 
 {
 printf(“Valor não encontrado\n”);
 }
 }
 else 
 {
 printf(“Lista Vazia\n”);
 }
}
/* Comentario: Lista Vazia */
int estaVazia(ListaSimplesEnc *pList) {
 return(pList->prim == NULL);
}
35
/* Comentario: Programa Principal */
void main() 
{
 setlocale(LC_ALL, “portuguese”);
 ListaSimplesEnc minhaLista;
 int valor, op, valorAlt;
 criarLista(&minhaLista);
 printf(“Escolha uma opção:\n”);
while (1) {
 printf(“\n(1) Inserir elemento no início da Lista\n”);
 printf(“(2) Inserir elemento em ordem (verifique se a lista está orde-
nada)\n”);
 printf(“(3) Remover elemento no início da Lista\n”);
 printf(“(4) Remover elemento específico da Lista\n”);
 printf(“(5) Mostrar Lista\n”);
 printf(“(6) Apagar todos os elementos da Lista\n”);
 printf(“(7) Alterar elemento da Lista\n”);
 printf(“(0) Sair\n”);
 printf(“ ? “);
 scanf(“%d”, &op);
 system(“cls”);
 switch (op) {
 case 1: // inserir elemento no inicio
 printf(“Valor? “);
 scanf(“%d”, &valor);
 inserirIni(&minhaLista, valor);
 break;
 case 2: // inserir elemento ordenado
 printf(“Valor? “);
 scanf(“%d”, &valor);
 inserirOrd(&minhaLista, valor);
 break;
 case 3: // remover o primeiro
 removerIni(&minhaLista);
 break;
 case 4: // remover determinado elemento
 printf(“Valor? “);
 scanf(“%d”, &valor);
 removerEle(&minhaLista, valor);
 break;
 case 5: // mostrar lista
 if (estaVazia(&minhaLista)) {
 printf(“Lista vazia\n”);
 }
 else {
 mostrarLista(&minhaLista);
36
 }
 break;
 case 6: // apagar todos os elementos da Lista
 removerTudo(&minhaLista);
 break;
case 7: // alterar um elemento
 printf(“Valor a ser alterado? “);
 scanf(“%d”, &valor);
 printf(“Novo valor? “);
 scanf(“%d”, &valorAlt);
 alterarEle(&minhaLista, valor, valorAlt);
 break;
 case 0: // abandonar o programa
 removerTudo(&minhaLista);
 exit(0);
 default:
 printf(“Opção inexistente!\n”);
 }
 }
}
MIDIATECA
Acesse a midiateca da Unidade 2 e veja o conteúdo complementar indicado 
pelo professor sobre lista encadeada.
37
Lista duplamente encadeada
Conforme afirmam Pugga e Rissetti (2009), o encadeamento duplo de lista, ou lista du-
plamente encadeada, apresenta como característica a possibilidade de ligação com du-
plo sentido — horário e anti-horário —, ou seja, pode varrer os elementos da lista tanto 
da esquerda para a direita como da direita para a esquerda, conforme ilustra a Figura 2.
Em uma lista duplamente encadeada, cada nó tem um ponteiro para o próximo elemento
e um para o elemento anterior. Assim, ao acessar um elemento da lista duplamente en-
cadeada, acessam-se também os elementos adjacentes, ou seja, o próximo e o anterior.
Vejamos, em seguida, um programa exemplo de lista duplamente encadeada:
/* Comentario: Lista Duplamente Encadeada */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
enum OpcoesMenu{SAIR=0,CRIAR_LISTA,INSERIR_AMIGO,IMPRIMIR_LISTA,REMOV-
ER_AMIGO,VERIFICAR_LISTA_VAZIA,LIBERAR_MEMORIA};
#define TAMMAX_AMIGO 40
/* Comentario: Define Estrutura da lista */
struct no 
{
 char amigo[TAMMAX_AMIGO];
 struct no * anterior;
 struct no * proximo;
};
Figura 2: Representação de uma lista duplamente encadeada.
Fonte: Elaborada pelo autor (2019).
1 2 3Lista
38
/* Comentario: Lista Duplamente Encadeada */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
enum OpcoesMenu{SAIR=0,CRIAR_LISTA,INSERIR_AMIGO,IMPRIMIR_LISTA,REMOV-
ER_AMIGO,VERIFICAR_LISTA_VAZIA,LIBERAR_MEMORIA};
#define TAMMAX_AMIGO 40
/* Comentario: Define Estrutura da lista */
struct no 
{
 char amigo[TAMMAX_AMIGO];
 struct no * anterior;
 struct no * proximo;
};
/* Comentario: Criar Lista Duplamente Encadeada */
No * criar_elemento() 
{
 No * e = (No*) malloc(sizeof(No));
 e->anterior = e->proximo = NULL;
 e->amigo[0] = ‘\0’;
 return e;
}
/* Comentario: Incluir Amigo no Final da Lista */
void inserir(No * lista, char * nome_amigo) 
{
 if (is_vazia(lista)) 
 {
 strncpy(lista->amigo, (const char *) nome_amigo, strlen(nome_amigo)); 
 } else 
 {
No * tmp = lista;
 while(tmp->proximo != NULL) 
 { 
 tmp = tmp->proximo; 
 }
 
 No * e = criar_elemento();
 
 strncpy(e->amigo, (const char *) nome_amigo, strlen(nome_amigo));
 e->anterior = tmp;
 e->proximo = NULL;
 
 tmp->proximo = e;
 }
}
39
/* Comentario: Pesquisar Amigo */
No * pesquisar (No * inicio_lista, char * nome_amigo) 
{
 No * tmp;
 if (is_vazia(inicio_lista)) 
 {
 tmp = NULL; 
 } else 
 {
 tmp = inicio_lista;
 while(tmp != NULL) 
 {
 if (strcasecmp(tmp->amigo, nome_amigo) == 0) 
 return tmp;
 
 tmp = tmp->proximo;
 }
 }
 
 return tmp;
}
/* Comentario: Imprimir Lista de Amigos */
void imprimir(No * lista) 
{
 if (is_vazia(lista)) 
 {
 puts(“\nSua lista de amigos está vazia.\n”);
 } else 
 {
 No * tmp = lista;
 printf(“\n* * * Lista de Amigos * * *\n”);
 
 while(tmp != NULL) 
 {
 printf(“%s\n”, tmp->amigo);
 tmp = tmp->proximo;
 } 
 }
}
/* Comentario: Remover Amigo da Lista */
No * remover(No * lista, No * elemento) 
{
 No * tmp_inicio;
 if (elemento == lista) 
 {
40
tmp_inicio = lista;
 tmp_inicio = elemento->proximo;
 tmp_inicio->anterior = NULL;
 } else 
 {
 tmp_inicio = elemento->anterior;
 tmp_inicio->proximo = elemento->proximo;
 tmp_inicio = lista;
 }
 
 free(elemento);
 
 return tmp_inicio;
}
/* Comentario: Apagar Lista Duplamente Encadeada */
void liberar_memoria(No * lista) 
{
 if (lista->proximo == NULL) 
 {
 free(lista);
 } else 
 {
 return liberar_memoria(lista->proximo);
 }
}
/* Comentario: Menu de Escolhas */
void menu_escolha() 
{
printf(“\n* * * M E N U * * *\n\n”);
 printf(“%d) Sair\n”, SAIR);
 printf(“%d) Criar lista\n”, CRIAR_LISTA);
 printf(“%d) Inserir amigo\n”, INSERIR_AMIGO);
 printf(“%d) Imprimir lista de amigos\n”, IMPRIMIR_LISTA);
 printf(“%d) Remover amigo\n”, REMOVER_AMIGO);
 printf(“%d) Verificar se lista está vazia\n”, VERIFICAR_LISTA_VAZIA);
 printf(“%d) Apagar lista\n”, LIBERAR_MEMORIA);
}
/* Comentario: Leitura do Nome do Amigo */
char * ler_amigo() 
{
 char nome[TAMMAX_AMIGO];
 printf(“\nQual o nome do Amigo: “);
 fgets(nome, TAMMAX_AMIGO, stdin);
 (*strrchr(nome, ‘\n’))= ‘\0’;
 
 return strdup(nome);
}
41
/* Comentario: Programa Principal */
int main() 
{
 int opcao;
 char * nome_amigo;
 No * lista = NULL;
 
 setlocale(LC_ALL, “portuguese”);
 
 while(1) 
 {
 system(“CLS”);
 menu_escolha();
 printf(“\nOpção: “);
 scanf(“%d%*c”, &opcao);
 
 if (opcao == SAIR) break;
 
 if (lista == NULL && opcao != CRIAR_LISTA) 
 {
 puts(“\nA lista não foi criada.\n”);
 } else 
 {
 
 switch(opcao) 
 {
 case CRIAR_LISTA:
 lista = criar_elemento();
 printf(“\nLista criada com sucesso.\n”);
 break;
 
 case INSERIR_AMIGO:
 puts(“\n* * * INCLUSÃO * * *”);
 nome_amigo = ler_amigo();
 if (pesquisar(lista, nome_amigo) == NULL) 
 {
 inserir(lista, nome_amigo);
 } else 
 {
 puts(“\nAmigo já consta na lista.\n”);
 }
 break;
 
 case IMPRIMIR_LISTA:
 imprimir(lista);
 break;
42
 case REMOVER_AMIGO:
 puts(“\n* * * REMOÇÃO * * *”);
 nome_amigo = ler_amigo();
 No * registro = pesquisar(lista, nome_amigo);
 if (registro == NULL) 
 {
 puts(“\nAmigo não encontrado.\n”);
 } else 
 {
 lista = remover(lista, registro);
 }
 break;
 
 case VERIFICAR_LISTA_VAZIA:
 printf(“\nA lista%sestá vazia\n”, is_vazia(lista)? “ “ : “ não “);
 break;
 
 case LIBERAR_MEMORIA:
 liberar_memoria(lista);
 lista = NULL;
 printf(“\nLista apagada.\n”);
 break;
 
 default:
 printf(“\nDigite uma opção válida.\n”);
 }
 
 }
 system(“PAUSE”);
 }
 
 /* Comentario: Liberar a Lista Duplamente Encadeada da Memória */
 if (lista != NULL) liberar_memoria(lista);
 
 return 0;
}
MIDIATECA
Acesse a midiateca da Unidade 2 e veja o conteúdo complementar indicado 
pelo professor sobre lista duplamente encadeada.
43
Lista circular
A lista circular, conforme ilustra a Figura 3, nada mais é que uma lista ligada, ou lista sim-
plesmente encadeada, cujo último elemento aponta diretamente para o primeiro dessa 
lista (FORBELLONE; EBERSPÄCHER, 2005).
Vejamos em seguida um programa exemplo de lista circular:
/* Comentario: Lista Circular */
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
/* Comentario: Declaração da Estrutura da Lista Circular */
struct no
{
 int info;
 struct no *prox;
};
/* Comentario: Descrição das Funções */
void addinicio(struct no *head, int valor);
void addfim(struct no *head, int valor);
void remover(struct no *head, int valor);
void buscar(struct no *head, int valor);
void imprimir(struct no *head);
void menu();
/* Comentario: Inserir Elemento no Início da Lista Circular */
void addinicio(struct no *head, int valor)
{
Figura 3: Representação de uma lista circular.
Fonte: Elaborada pelo autor (2019).
1 2 3Lista
44
struct no *p;
 printf(“\nValor do Elemento: “);
 scanf(“%d”,&valor);
 
 if((p = malloc(sizeof(struct no))) == NULL)
 {
 printf(“\nErro de Memória\n”);
 }
 else
 {
 p->info = valor;
 p->prox = head->prox; 
 head->prox = p; 
 }
}
/* Comentario: Inserir no Final da Lista Circular */
void addfim(struct no *head, int valor)
{
 struct no *pNow, *pNext;
 printf(“\nValor do elemento: “);
 scanf(“%d”,&valor);
 
 if((pNow = malloc(sizeof(struct no))) == NULL)
 {
 printf(“\nErro de Memória\n”);
 }
 else
 {
 pNow->info = valor; 
 pNext = head->prox; 
 
 while(pNext->prox != head)
 {
 pNext = pNext->prox;
 }
 pNow->prox = pNext->prox;
 pNext->prox = pNow;
 }
}
/* Comentario: Remover Elemento da Lista Circular */
void remover(struct no *head, int valor)
{
 struct no *p, *aux;
 printf(“\nValor a Remover: “);
 scanf(“%d”,&valor);
 
 p = head->prox;
 aux = head; 
 head->info = valor; 
45
while(p->info != valor)
 {
 aux = p;
 p = p->prox;
 } 
 if(p == head)
 {
 printf(“\nElemento não encontrado\n”);
 }
 else
 {
 aux->prox = p->prox; 
 free(p);
 
 printf(“\nElemento removido com Sucesso!\n”);
 }
}
/* Comentario: Imprimir Elementos da Lista Circular */
void imprimir(struct no *head)
{
 struct no *p;
 int okay = 0;
 p = head->prox;
 
 while(p!=head)
 {
 printf(“\n%d”,p->info);
 p = p->prox;
 okay = 1;
 }
if(okay == 0)
 {
 printf(“\nLista Vazia\n”);
 }
}
/* Comentario: Pesquisar Elemento na Lista Circular */
void buscar(struct no *head, int valor)
{
 struct no *p;
 printf(“\nBuscar elemento: “);
 scanf(“%d”,&valor);
 
 p = head->prox; 
 head->info = valor;
 
 while(p->info != valor)
 {
 p = p->prox;
 }
46
 if(p == head)
 {
 printf(“\nElemento não encontrado!\n”);
 }
else 
 {
 printf(“\nElemento encontrado com sucesso!\n”);
 }
}
/* Comentario: Menu de Escolhas */
void menu()
{
 printf(“\n1) Inserir no Início”);
 printf(“\n2) Inserir no Final”);
 printf(“\n3) Buscar Elemento”);
 printf(“\n4) Remover Elemento”);
 printf(“\n5) Imprimir Lista”);
 printf(“\n\n0) Sair: “);
}
/* Comentario: Programa Principal */
int main(int argc, char *argv)
{
 struct no *head;
 int op, valor;
 
 setlocale(LC_ALL, “portuguese”);
 
 if((head = malloc(sizeof (struct no))) == NULL)
 {
 printf(“\nErro de Memória\n”);
 }
 else
 {
head->prox = head;
 do
 {
 system(“CLS”);
 menu();
 scanf(“%d”,&op);
 
 switch(op)
 {
 case 0:
 break;
 case 1: 
 addinicio(head, valor);
 break; 
47
 case 2:
 addfim(head, valor);
 break;
 
 case 3:
 buscar(head, valor);
 break;
case 4:
 remover(head, valor);
 break;
 
 case 5:
 imprimir(head);
 break;
 
 default:
 printf(“\nOpçção Inválida!\n”);
 break;
 }
 
 printf(“\n”);
 system(“PAUSE”);
 }
 
 while(op!=0);
 return 0;
 } 
}
Existe também a possibilidade de implementação de soluções computacionais 
com listas duplamente circulares.
Curiosidade
48
MIDIATECA
Acesse a midiateca da Unidade 2 e veja o conteúdo complementar indicado 
pelo professor sobre listas circulares.
NA PRÁTICA
A empresa Data Systems tem a necessidade de implementar uma solução 
computacional em linguagem C que tenha por objetivo o registro de uma senha 
alfabética como elemento de controle de certo aplicativo web cuja estratégia é 
ter desenvolvido um programa com lista duplamente encadeada para habilitar 
(incluir) e desabilitar (remover) a senha alfabética dessa lista. Então, sua mis-
são é descrever essas rotinas em linguagem C.
/* Comentario: Solução Rotinas Lista Duplamente Encadeada */
void inserir(No * lista, char * senha_alfa) // Habilitar senha na lista duplamente 
encadeada
{
 if (is_vazia(lista)) 
 {
MIDIATECA
Acesse a midiateca da Unidade 2 e veja o conteúdo complementar indicado 
pelo professor sobre lista duplamente circular.
49
 strncpy(lista->senha, (const char *) nome_senha, strlen(nome_senha)); 
 } else 
 {
 No * tmp = lista;
 while(tmp->proximo != NULL) 
 { 
 tmp = tmp->proximo; 
 }
No * e = criar_elemento();
 
 strncpy(e->senha, (const char *) nome_senha, strlen(nome_senha));
 e->anterior = tmp;
 e->proximo = NULL;
 
 tmp->proximo = e;
 }
}
No * remover(No * lista, No * elemento) // Desabilitar senha na lista duplamente 
encadeada
{
 No * tmp_inicio;
 if (elemento == lista) 
 {
 tmp_inicio = lista;
 tmp_inicio = elemento->proximo;
 tmp_inicio->anterior = NULL;
 } else 
 {
 tmp_inicio = elemento->anterior;
 tmp_inicio->proximo = elemento->proximo;
 tmp_inicio = lista;
 }
 
 free(elemento);
 
 return tmp_inicio;
}
50
Resumo da Unidade 2
Nesta unidade, você conheceu as estruturas lineares encadeadas (listas), nas variações 
de lista simplesmente encadeada, lista duplamente encadeada e lista circular, por meio 
da implementação de programas de computador.
CONCEITO
Nesta unidade, destacam-se o conhecimento e a implementação de solução 
computacional por meio das estruturas de dados lista simplesmente encadea-
da, lista duplamente encadeada e lista circular.
51
Referências
FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. Lógica de programação: a construção de 
algoritmos e estrutura de dados. 3. ed. São Paulo: Pearson Prentice Hall, 2005. Biblioteca 
Virtual.
Estruturas lineares 
encadeadas: filas e pilhas
UNIDADE 3
53
Nesta unidade, o estudante conhecerá os procedimentos necessários para a manipula-
ção de filas e pilhas lineares encadeadas, assim como das filas circulares, como opção 
de estrutura de dados complexa.
INTRODUÇÃO
Nestaunidade, você será capaz de:
• Entender as estruturas de dados fila e pilha.
• Implementar solução com fila linear.
• Implementar solução com pilha linear.
• Desenvolver programa de computador com a estrutura fila circular.
OBJETIVO
54
Trabalhando com filas 
A fila é uma estrutura de dados dinâmica que admite a inserção e a remoção de ele-
mentos a partir da técnica conhecida como Fifo (first in, first out), ou seja, o primeiro 
elemento a entrar na fila será o primeiro a sair dela, conforme ilustrado na Figura 1 
(MIZRAHI, 2008).
Figura 1: Estrutura de dados fila linear.
Fonte: Elaborada pelo autor (2019).
Em português, a técnica Fifo é conhecida como Peps, ou seja, o “primeiro a entrar é o 
primeiro a sair”.
Vejamos um exemplo de programa com a estrutura de dados fila:
/* Comentario: Trabalhando com a Estrutura de Dados Fila Linear */
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
/* Comentario: Declaração da Estrutura Fila */
struct Fila 
{
 int capacidade;
 int *dados;
 int primeiro;
 int ultimo;
 int nItens; 
};
/* Comentario: Criar Fila */
void criarFila( struct Fila *f, int c ) 
{ 
1 3 n2 ... n + 1
Remoção
Final da fila Início da fila
Inserção
55
 f->capacidade = c;
 f->dados = (int*) malloc (f->capacidade * sizeof(int));
 f->primeiro = 0;
 f->ultimo = -1;
 f->nItens = 0; 
}
/* Comentario: Inserir Elemento na Fila */
void inserir(struct Fila *f, int v) 
{
 if(f->ultimo == f->capacidade-1)
 f->ultimo = -1;
 f->ultimo++;
 f->dados[f->ultimo] = v; 
 f->nItens++; 
}
/* Comentario: Remover Elemento da Lista */
int remover( struct Fila *f ) 
{
 int temp = f->dados[f->primeiro++]; 
 if(f->primeiro == f->capacidade)
 f->primeiro = 0;
 f->nItens--;
 
 return temp;
}
/* Comentario: Fila Vazia */
int estaVazia( struct Fila *f ) 
{
 return (f->nItens==0);
}
/* Comentario: Fila Cheia */
int estaCheia( struct Fila *f ) 
{
 return (f->nItens == f->capacidade);
}
/* Comentario: Mostrar Elementos da Fila */
void mostrarFila(struct Fila *f)
{
 int cont, i;
 for ( cont=0, i= f->primeiro; cont < f->nItens; cont++)
 {
 printf(“%d “,f->dados[i++]);
56
 if (i == f->capacidade)
 i=0;
 }
 printf(“\n”);
}
/* Comentario: Programa Principal */
void main () 
{
 int opcao, capa;
 int valor;
 struct Fila umaFila;
 
 setlocale(LC_ALL, “portuguese”);
 system(“CLS”);
 printf(“Capacidade da Fila?”);
 scanf(“%d”,&capa);
 criarFila(&umaFila, capa);
 while( 1 )
 {
 system(“CLS”);
 printf(“ * * * FAÇA SUA ESCOLHA * * * \n\n”);
 printf(“ 1- Inserir elemento na Fila \n”);
 printf(“ 2- Remover elemento da Fila \n”);
 printf(“ 3- Mostrar elementos da Fila \n”);
 printf(“ 0- Sair \n\n”);
 printf(“Opção? “);
 scanf(“%d”, &opcao);
 switch(opcao){
 case 0: exit(0);
 case 1:
 if (estaCheia(&umaFila))
 {
 printf(“\nA Fila está Cheia.\n”);
 system(“PAUSE”);
 }
 else 
 {
 printf(“\nElemento a ser inserido?”);
 scanf(“%d”, &valor);
 
 inserir(&umaFila,valor);
 }
57
 break;
 case 2:
 if (estaVazia(&umaFila))
 {
 printf(“\nA Fila está Vazia.\n”);
 system(“PAUSE”);
 }
 else 
 {
 valor = remover(&umaFila);
 printf(“\nO Elemento %d foi removido com 
sucesso.\n”, valor) ; 
 system(“PAUSE”);
 }
 break;
 case 3:
 if (estaVazia(&umaFila))
 {
 printf(“\nA Fila está Vazia.\n”);
 system(“PAUSE”);
 }
 else 
 {
 printf(“\nElementos da Fila: “);
 mostrarFila(&umaFila);
 printf(“\n”);
 system(“PAUSE”);
 }
 break;
 default:
 printf(“\nOpção Inválida.\n”);
 system(“PAUSE”);
 }
 }
}
58
Acesse a midiateca da Unidade 3 e veja o conteúdo complementar indicado 
pelo professor sobre programação em linguagem C.
MIDIATECA
59
Trabalhando com pilhas 
As pilhas são uma lista na qual é aplicada a disciplina de acesso antagônica denomi-
nada Ueps (o último a entrar é o primeiro a sair), ou, em inglês, o termo Lifo (last in, first 
out), ou seja, qualquer elemento que entrar na pilha somente sairá quando todos os que 
entraram depois dele saírem (PUGGA; RISSETTI, 2009). A Figura 2 ilustra a estrutura 
de dados pilha linear.
Figura 2: Estrutura de dados pilha linear.
Fonte: Elaborada pelo autor (2019).
Vejamos um exemplo de programa com a estrutura de dados pilha:
/* Comentario: Trabalhando com a Estrutura de Dados Pilha Linear */
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
/* Comentario: Declaração da Estrutura de Dados Pilha */
struct Pilha 
{
 int topo;
 int capa;
 int *pElem;
};
int capacidade;
Empilha elemento
(Push)
Pilha Base
Topo
Desempilha elemento
(Pop)
n + 1
...
2
n
3
1
60
/* Comentario: Criar Pilha */
void criarpilha( struct Pilha *p, int c )
{
 p->topo = -1;
 p->capa = c;
 p->pElem = (int*) malloc (c * sizeof(int));
}
/* Comentario: Pilha Vazia */
int estavazia ( struct Pilha *p )
{
 if( p-> topo == -1 )
 return 1;
 else
 return 0;
}
/* Comentario: Pilha Cheia */
int estacheia ( struct Pilha *p )
{
 if (p->topo == p->capa - 1)
 return 1;
 else
 return 0;
}
/* Comentario: Inserir Elemento na Pilha - Empilhar */
void empilhar ( struct Pilha *p, int v)
{
 p->topo++;
 p->pElem [p->topo] = v;
}
/* Comentario: Remover Elemento da Pilha - Desempilhar */
float desempilhar ( struct Pilha *p )
{
 int aux = p->pElem [p->topo];
 p->topo--;
 return aux;
}
/* Comentario: Direciona ao Topo da Pilha */ 
int retornatopo ( struct Pilha *p )
{
 return p->pElem [p->topo];
}
/* Comentario: Programa Principal */
int main()
{
 struct Pilha minhapilha;
 int op;
 int valor;
 
61
 setlocale(LC_ALL, “portuguese”);
 system(“CLS”);
 printf( “Capacidade da Pilha?” );
 scanf( “%d”, &capacidade );
 criarpilha (&minhapilha, capacidade);
 while( 1 )
 {
 system(“CLS”);
 printf(“ * * * FAÇA SUA ESCOLHA * * * \n\n”);
 printf(“ 1- Inserir Elemento na Pilha [Empilhar] \n”);
 printf(“ 2- Remover Elemento da Pilha [Desempilhar] \n”);
 printf(“ 3- Mostrar Elemento do Topo da Pilha \n”);
 printf(“ 0- Sair \n\n”);
 printf(“Opção?”);
 scanf(“%d”, &op);
 switch (op){
 case 0:
 
 exit(0);
 break;
 
 case 1:
 if( estacheia( &minhapilha ) == 1 )
 printf(“\nA Pilha está Cheia. \n”);
 else 
 {
 printf(“\nValor ? “);
 scanf(“%d”, &valor);
 
 empilhar (&minhapilha, valor);
 }
 break;
 case 2:
 if ( estavazia(&minhapilha) == 1 )
 printf( “\nA Pilha está Vazia. \n” );
 else
 {
 valor = desempilhar (&minhapilha);
 printf ( “\nO Elemento %d foi Desempilha-
do. \n”, valor );
 }
 break;
62
Acesse a midiateca da Unidade 3 e veja o conteúdo complementar indicado 
pelo professor sobre pilha dinâmica.
MIDIATECA
 case 3:
 if ( estavazia (&minhapilha) == 1 )
 printf( “\nA Pilha está Vazia. \n” );
 else 
 {
 valor = retornatopo (&minhapilha);
 printf( “\nElemento do Topo da Pilha: %d\n”, valor );
 }
 break;
 default: printf( “\nOpção Inválida. \n” );
 }
 system(“PAUSE”);
 }
}
63
Filas circulares
De acordo com Forbellone e Eberspächer (2005), uma fila circular é um vetor dinâmi-
co cujo término se encontra com seu início. No entanto, os elementos da fila circular 
podem não estar ocupando fisicamente todas as posições desse vetor, identificando 
esse final, portanto, como NULL. Vejamos a ilustração de uma fila circular na Figura 3. 
Figura 3: Estrutura de dados fila circular.
Fonte: Elaborada pelo autor (2019).
A fila circular ilustrada anteriormente é composta por 16 espaços de memória (MÁX. 
= 16). No entanto, apenas seis dessas posições estão com elementos fisicamente pre-
sentes. Vejamos um exemplo prático de fila circular:
/* Comentario: Estrutura de Dados Fila Circular */
#include<stdio.h>
#include<stdlib.h>
#include <locale.h>
#define MAX 5
/* Comentario: Declaração da Estrutura Fila Circular */
struct circular
{ int com;
 int fim;
 int total;
Início
Final
1
2
3
4
5
6
64
 int memo[MAX];
};
typedef struct circularcircular;
void enfileirar(struct circular *F, int x);
int desenfileirar(struct circular *F);
void listar(struct circular A);
int busca(struct circular B, int x);
/* Comentario: Inserir Elemento na Fila Circular */
void enfileirar(struct circular *F, int x)
{
 F->fim++;
 
 if(F->fim == MAX)
 F->fim = 0;
 F->memo[F->fim] = x;
 F->total++;
}
/* Comentario: Remover Elemento da Fila Circular */
int desenfileirar(struct circular *F)
{
 int aux;
 aux = F->memo[F->com];
 F->com++;
 if(F->com == MAX)
 {
 F->com = 0;
 }
 F->total --;
 
 return aux;
}
/* Comentario: Listar os Elementos da Fila Circular */
void listar(struct circular A)
{
 printf(“\nElementos da Fila Circular \n\n”);
 
 while(A.total!=0)
 {
 printf(“%d “, desenfileirar(&A));
 }
 printf(“\n”);
}
/* Comentario: Buscar um Elemento na Fila Circular */
int busca(struct circular B, int x)
{ 
 int achou;
 
65
 while(B.total!=0)
 {
 if(x == desenfileirar(&B))
 {
 achou = 1;
 }
 }
 return achou;
}
/* Comentario: Menu de Opções */
int menu()
{
 int opc;
 
 system(“CLS”);
 printf(“* * * FAÇA SUA ESCOLHA * * *\n\n”);
 printf(“ 1- Enfileirar Elemento \n”);
 printf(“ 2- Desenfileirar Elemento \n”);
 printf(“ 3- Listar Elementos \n”);
 printf(“ 4- Buscar Elemento na Fila \n”);
 printf(“ 0- Sair \n\n”);
 printf(“ Opção: “);
 scanf(“%d”, &opc);
 
 return opc;
}
/* Comentario: Programa Principal */
int main ()
{
 struct circular F;
 F.com = 0;
 F.total = 0;
 F.fim = -1;
 
 int opc,x,pos,num;
 setlocale(LC_ALL, “portuguese”);
 
 do
 {
 opc = menu();
 switch(opc)
 {
 case 0:
 exit (0);
 break;
 
 case 1:
 if(F.fim==MAX-1)
 {
 printf(“\nA Fila está Cheia. “);
 }
66
 else
 {
 printf(“\n Elemento (número) a ser inserido na Fila: “);
 scanf(“%d”, &x);
 
 if(busca(F,x) == 1)
 {
 printf(“Não é possível inserir elementos repetidos “);
 }
 else
 {
 enfileirar(&F, x);
 }
 }
 break;
 
 case 2:
 if(F.total == 0)
 printf(“\nA Fila está Vazia. “);
 else
 printf(“\nElemento retirado da Fila Circular => %d”, 
desenfileirar(&F));
 break;
 
 case 3:
 if(F.fim == -1)
 printf(“\nA Fila está Vazia. “);
 else
 listar(F);
 break;
 
 case 4:
 printf(“\nQual é o elemento que deseja localizar?”);
 scanf(“%d”, &x);
 
 if((busca(F,x)==1))
 printf(“\nO elemento %d está na Fila. “, x);
 else
 printf(“\nO elemento %d não está na Fila. “, x);
 break;
 
 default: printf(“\nOpção Inválida. \n”);
 }
 
 printf(“\n”); 
 system(“PAUSE”);
 }while(opc!=0);
}
67
Acesse a midiateca da Unidade 3 e veja o conteúdo complementar indicado 
pelo professor sobre fila dinâmica.
MIDIATECA
A empresa Renalf S/A precisa desenvolver uma rotina (procedimento) de pro-
gramação, escrita em linguagem C, com o objetivo de realizar as operações de 
empilhamento e desempilhamento de elementos (código de acesso secreto) a 
partir da estrutura de dados pilha considerando a estrutura de uma pilha.
/* Comentario: Declaração da Estrutura Pilha */
struct Pilha 
{
 int topo;
 int capa;
 int *pElem;
};
/* Comentario: Procedimento de Empilhamento */
void empilhar ( struct Pilha *p, int v)
{
 p->topo++;
 p->pElem [p->topo] = v;
}
/* Comentario: Procedimento de Desempilhamento */
float desempilhar ( struct Pilha *p )
{
 int aux = p->pElem [p->topo];
 p->topo--;
 return aux;
}
NA PRÁTICA
68
Resumo da Unidade 3
Nesta unidade, você conheceu e implementou as estruturas de dados fila e pilha lineares. 
Também foi desenvolvido programa de computador com a estrutura fila circular com fins 
de aprofundamento de estudo. 
O estudo das estruturas de dados, além dos vetores, das matrizes, dos pon-
teiros/apontadores e das listas, também apresenta o recurso de filas e pilhas. 
Nesse contexto, quando utilizamos a estrutura de dados fila, aplicamos o méto-
do conhecido como Fifo (first in, first out), ou seja, o primeiro elemento a entrar 
na fila será, sempre, o primeiro elemento a ser retirado dela. De forma análoga, 
ao utilizarmos a estrutura de dados pilha, aplicamos o método conhecido como 
Lifo (last in, first out), ou seja, o último elemento a entrar na pilha (empilhamen-
to) será o primeiro a ser retirado dela (desempilhamento).
CONCEITO
69
Referências 
FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. Lógica de programação: a construção de 
algoritmos e estruturas de dados. 3. ed. São Paulo: Pearson Prentice Hall, 2005. Bibliote-
ca Virtual.
MIZRAHI, V. V. Treinamento em linguagem C. 2. ed. São Paulo: Pearson Education do 
Brasil, 2008. Biblioteca Virtual.
PUGGA, S.; RISSETTI, G. Lógica de programação e estrutura de dados com aplicações 
em Java. 3. ed. São Paulo: Pearson Prentice Hall, 2009. Biblioteca Virtual.
SIMÕES-PEREIRA, J. M. S. Grafos e redes: teoria e algoritmos básicos. Rio de Janeiro: 
Interciência, 2014. Biblioteca Virtual.
Grafos e árvores
UNIDADE 4
71
Nesta unidade, o estudante conhecerá a teoria dos grafos e a estrutura de dados árvore
— sua variação como árvore binária e árvore AVL —, explorando também os percursos
em árvore e os algoritmos de busca.
INTRODUÇÃO
Nesta unidade, você será capaz de:
• Entender o funcionamento de programas executáveis a partir da visão da ar-
quitetura de computadores, assim como a diferença entre a linguagem interpre-
tada e a linguagem montadora.
OBJETIVO
72
Grafos e árvores
Grafo
O conceito de grafo, definido por Simões-Pereira (2014), apresenta o grafo G = (V, E) 
como um sistema formado por:
• Um conjunto V de elementos chamados vértices, pontos ou nodos. 
• Um conjunto E de pares não ordenados de vértices denominados arestas ou linhas. 
Figura 1: Representação de um grafo.
Fonte: Simões-Pereira (2014).
Dígrafo ou grafo dirigido
Um dígrafo D = (V, A) é definido de modo semelhante, em que A representa um conjunto 
de pares ordenados que chamamos de arcos, conforme ilustra a Figura 2.
Figura 2: Representação de um dígrafo.
Fonte: Simões-Pereira (2014).
1
4
2
3
1 2
3
73
As figuras 1 e 2 podem ser representadas, respectivamente, da seguinte forma algébrica:
G = (V ’ , E) 
V ’ = { 1, 2, 3, 4 }
E = { [1, 2], [2, 3], [3, 1], [1, 4] }
D = (V ’’, A)
V ’’ = { 1, 2, 3 }
A = { (1, 2), (2, 1), (1, 3), (2, 3) }
Árvore
Segundo Pugga e Rissetti (2009), a árvore é uma estrutura de dados bidirecional, não 
linear, constituída de nós que representam um modelo hierárquico, uma vez que armaze-
nam dados com base em relações de dependência.
As estruturas de dados do tipo árvore permitem a implementação de algoritmos que:
• Realizam suas tarefas de forma mais eficiente que vetores, listas e conjuntos. 
• Oferecem uma organização mais natural para os dados.
O sentido do fluxo de dados em um grafo tradicional sempre é bidirecional, 
enquanto o fluxo de dados em um dígrafo é unidirecional, determinado pela 
direção da seta.
Importante
74
Figura 3: Representação hierárquica da estrutura árvore.
Fonte: Pugga e Rissetti (2009).
Vamos entender melhor o esquema de representação hierárquica da estrutura árvore?
• O nó A é considerado o nó raiz ou o pai da árvore (A).
• Todos os nós da árvore que contêm filhos são denominados nós intermediários (B, E, 
F, D e G).
• Todo nó da árvore que não apresenta nenhum filho é chamado, tecnicamente, de nó 
folha ou nó terminal (C, I, J, K, H e L). 
O nível da árvore indica a posição hierárquica em relação à raiz:
• O nó A tem nível 0. 
• Os nós B, C e D têm nível 1. 
• Os nós E, F, G e H têm nível 2. 
• Os nós I, J, K e L têm nível 3.
A altura ou profundidade é definida pelo nível máximo de nós:
• A árvore T tem altura igual a 3. 
• A subárvore da esquerda(B) tem altura igual a 2.
O grau de um nó é indicado por seu número de filhos:
• O nó B tem grau 2. 
• O nó F tem grau 1.
• O nó C tem grau 0.
A
B
E G
I K
C
F H
J L
D
75
Subárvore
Quando existe a representação de uma árvore dentro de outra, dá-se, tecnicamente, o 
nome de subárvore.
Figura 4: Representação de subárvore.
Fonte: Pugga e Rissetti (2009).
Nesse caso, podemos visualizar as subárvores da esquerda e da direita da árvore A.
Representação por parênteses aninhados
Cada nó é associado a seus respectivos descendentes ou filhos, conforme ilustra a 
Figura 5.
Figura 5: Representação por parênteses aninhados de uma árvore.
T = ( A ( B ( E ( I ) ( J ) ) ( F ( K ) ) ) ( C ) ( D ( G ( L ) ) ( H ) ) )
Fonte: Elaborada pelo autor (2019).
A
B
E G
I K
C
F H
J L
D
T1 T2
Além da forma hierárquica, uma árvore pode ser representada por:
• Parênteses aninhados.
• Inclusão.
• Identação.
Curiosidade
76
Representação por inclusão
Cada nó é simbolizado por uma figura geométrica, e seus descendentes são inseridos ou 
incluídos nessa figura, de modo que o nó principal englobe os demais.
Figura 6: Representação por inclusão de uma árvore.
Fonte: Pugga e Rissetti (2009).
Representação por identação
Esse tipo de representação coloca os nós identados, de acordo com a prioridade, acerca 
do nó que está classificado como raiz, pai, filho ou folha.
Figura 7: Representação por identação de uma árvore.
Fonte: Elaborada pelo autor (2019).
 
A
B
E
I
J
F
K
C
D
G
H
L
A
B
E
I
J
F K
C
G L
D
H
77
Árvores binária e AVL
Árvore binária
Uma árvore binária, de acordo com Mizrahi (2008), é um conjunto de registros ou nós em 
forma de estrutura de dados que satisfaz determinadas condições e é caracterizado por:
• Um nó especial denominado raiz.
• Nenhum nó possuir grau superior a dois, isto é, nenhum nó possui mais de dois 
descendentes ou filhos.
• Uma distinção entre uma subárvore esquerda e uma subárvore direita.
Figura 8: Representação de uma árvore binária.
Fonte: Elaborada pelo autor (2019).
O atravessamento, ou caminhamento, de árvore é a passagem de forma siste-
mática por cada um de seus nós.
Saiba mais
78
A árvore binária apresenta como particularidade o posicionamento de seus nós, confor-
me afirmam Pugga e Rissetti (2009):
• Os nós da direita sempre possuem valor superior ao do nó pai. 
• Os nós da esquerda sempre possuem valor inferior ao do nó pai.
Figura 9: Árvore binária.
Fonte: Pugga e Rissetti (2009).
Uma árvore binária pode também ser classificada como completa ou cheia, conforme 
ilustra a Figura 10.
Figura 10: Árvore binária cheia.
Fonte: Adaptado de Forbellone e Eberspächer (2005).
Assim como qualquer estrutura de dados, a árvore também é representada em forma de 
vetor.
57
45 77
13 84
78
60
609
79
Figura 11: Representação de uma árvore em forma de vetor de dados.
Fonte: Forbellone e Eberspächer (2005).
Árvore AVL
Segundo Mizrahi (2008), a árvore AVL é uma árvore binária de busca balanceada, confor-
me pudemos observar na Figura 10, também conhecida como Adelson-Velsky e Landis, 
em homenagem a seus criadores.
Uma árvore balanceada é aquela que busca minimizar o número de comparações rea-
lizadas, no pior caso, para uma busca com chaves de probabilidades de ocorrências 
idênticas.
0 1 2 3 4 5 6
80
Buscas em árvore
As buscas em árvores são estabelecidas pelos percursos que seguimos para percorrer 
os nós dessa árvore. 
De acordo com Forbellone e Eberspächer (2005), o percurso em árvores refere-se à 
forma como os vértices são visitados durante o processo de varredura (leitura) da árvore.
Os percursos caracterizam as chamadas árvores de busca, que poderão utilizar dois 
métodos: 
• Busca em profundidade (DFS – depth-first search). 
• Busca em largura (BFS – breadth-first search).
Busca em profundidade
A busca em profundidade pode adotar três técnicas distintas para explorar esses 
percursos: 
• Pré-ordem.
• Em ordem. 
• Pós-ordem.
Na técnica pré-ordem, o percurso primeiro visita o nó raiz, em seguida percorre o nó da 
esquerda e, por último, trilha o nó da direita.
RED: raiz esquerda direita
Já na técnica em ordem, o percurso visita o nó da esquerda, percorre a raiz e, por fim, 
trilha o nó da direita.
ERD: esquerda raiz direita 
Finalmente, a técnica pós-ordem apresenta o percurso visitando o nó da esquerda, em 
seguida percorrendo o nó da direita e, por fim, o nó raiz.
EDR: esquerda direita raiz 
81
Tomando como base a árvore binária representada a seguir, na Figura 12 temos:
• Percurso pré-ordem (RED): A, B, D, E, C e F.
• Percurso em ordem (ERD): D, B, E, A, C e F.
• Percurso pós-ordem (EDR): D, E, B, F, C e A.
Figura 12: Busca em profundidade em árvore binária.
Fonte: Elaborada pelo autor (2019).
Busca em largura
Na busca em largura, intuitivamente começa-se pelo nó raiz e se exploram (visita) todos 
os vértices vizinhos.
Então, para cada um dos vértices mais próximos, exploramos seus vértices vizinhos 
inexplorados, e assim por diante, até que ele encontre o alvo da busca ou termine os nós 
visitados na árvore.
Figura 13: Busca em largura em árvore binária.
Fonte: Elaborada pelo autor (2019).
A
B
D E F
C
A
B
D E F
C
82
Note, na ilustração da Figura 13, que a varredura começa sempre de cima para 
baixo e da esquerda para a direita a partir do nó raiz. Ao aplicar a técnica de 
busca em largura, com base na árvore apresentada, a seguinte saída é obtida: 
A, B, C, D, E e F.
Importante
Vejamos um exemplo prático do uso de operações com árvores.
/* Comentario: Manipulação com Árvore Binária */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <locale.h>
/* Comentario: Declaração da Estrutura do Registro */
struct carro
{
char nome[30];
char marca[30];
int ano;
float preco;
};
/* Comentario: Declaração da Estrutura da Árvore */
struct No
{
int numero;
struct carro x;
struct No *esquerda;
struct No *direita;
};
typedef struct No No;
/* Comentario: Criar Árvore */
void criarArvore(No **pRaiz)
{
*pRaiz = NULL;
}
/* Comentario: Inserir Elemento */
void inserir(No **pRaiz, int numero, struct carro x)
{
if(*pRaiz == NULL)
{
*pRaiz = (No *) malloc(sizeof(No));
(*pRaiz)->esquerda = NULL;
(*pRaiz)->direita = NULL;
83
(*pRaiz)->numero = numero;
(*pRaiz)->x = x;
}
else
{
if(numero < (*pRaiz)->numero)
inserir(&(*pRaiz)->esquerda, numero, x);
if(numero > (*pRaiz)->numero)
inserir(&(*pRaiz)->direita, numero, x);
}
}
/* Comentario: Teste Nó Maior Direita */
No *MaiorDireita(No **no)
{
if((*no)->direita != NULL)
return MaiorDireita(&(*no)->direita);
else
{
No *aux = *no;
if((*no)->esquerda != NULL) 
*no = (*no)->esquerda;
else
*no = NULL;
return aux;
}
}
/* Comentario: Teste Nó Maior Esquerda */
No *MenorEsquerda(No **no)
{
if((*no)->esquerda != NULL)
return MenorEsquerda(&(*no)->esquerda);
else
{
No *aux = *no;
if((*no)->direita != NULL) 
*no = (*no)->direita;
else
*no = NULL;
return aux;
}
}
/* Comentario: Remover Elemento */
void remover(No **pRaiz, int numero)
{
if(*pRaiz == NULL)
{
printf(“\nNúmero não existe na árvore!\n”);
return;
}
if(numero < (*pRaiz)->numero)
remover(&(*pRaiz)->esquerda, numero);
else
84
if(numero > (*pRaiz)->numero)
remover(&(*pRaiz)->direita, numero);
else
{ 
No *pAux = *pRaiz; 
if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL))
{ 
free(pAux);
printf(“\nRemovido com Sucesso! \n”);
(*pRaiz) = NULL;
}
else
{
if ((*pRaiz)->esquerda == NULL)
{
(*pRaiz) = (*pRaiz)->direita;
pAux->direita = NULL;
free(pAux); pAux = NULL;
printf(“\nRemovido com Sucesso! \n”);
}
else
{ 
if ((*pRaiz)->direita == NULL)
{
(*pRaiz) = (*pRaiz)->esquerda;
pAux->esquerda = NULL;
free(pAux); pAux = NULL;
printf(“\nRemovido com Sucesso! \n”);
}
else
{
pAux = MaiorDireita(&(*pRaiz)->esquerda); 
pAux->esquerda = (*pRaiz)->esquerda;
pAux->direita = (*pRaiz)->direita;
(*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
free((*pRaiz)); *pRaiz = pAux; pAux = NULL;
printf(“\nRemovido com Sucesso! \n”);
}
}
}
}
}
/* Comentario: Percurso Pre Ordem */ 
voidexibirPreOrdem(No **pRaiz)
{
if((*pRaiz) != NULL)
{
printf(“%i\n”, (*pRaiz)->numero);
exibirPreOrdem(&(*pRaiz)->esquerda);
exibirPreOrdem(&(*pRaiz)->direita);
}
}
85
/* Comentario: Percurso Em Ordem */
void exibirEmOrdem(No **pRaiz)
{
if((*pRaiz) != NULL)
{
exibirEmOrdem(&(*pRaiz)->esquerda);
printf(“%i\n”, (*pRaiz)->numero);
exibirEmOrdem(&(*pRaiz)->direita);
}
}
/* Comentario: Percurso Pós-Ordem */
void exibirPosOrdem(No **pRaiz)
{
if((*pRaiz) != NULL)
{
exibirPosOrdem(&(*pRaiz)->esquerda);
exibirPosOrdem(&(*pRaiz)->direita);
printf(“%i\n”, (*pRaiz)->numero);
}
}
/* Comentario: Verifica Quem é o Maior */
int maior(int a, int b){
if(a > b)
return a;
else
return b;
}
/* Comentario: Imprimir Árvore */
int imprimir(No **pRaiz)
{
if((*pRaiz) != NULL)
{
 if((*pRaiz) != NULL) 
 printf(“\nPai %i\n”,(*pRaiz)->numero);
 
 if((*pRaiz)->esquerda != NULL)
 printf(“Esq: %i\t”,(*pRaiz)->esquerda->numero);
 else
 printf(“Esq: NULL\t”);
 
 if((*pRaiz)->direita != NULL)
 printf(“Dir: %i\t”,(*pRaiz)->direita->numero);
 else
 printf(“Dir: NULL\t”);
 
 if((*pRaiz)->esquerda != NULL)
 imprimir(&(*pRaiz)->esquerda);
 
 if((*pRaiz)->direita != NULL)
 imprimir(&(*pRaiz)->direita);
}
86
else
 printf(“A árvore está vazia! \n”);
}
/* Programa Principal */
int main ()
{
struct carro ca;
int c;
No *pRaiz;
criarArvore(&pRaiz);
setlocale(LC_ALL, “portuguese”);
int op;
do{
 system(“CLS”);
 printf(“* * * FAÇA SUA ESCOLHA * * *\n\n”);
 printf(“1. Inserir Veículo: \n”);
 printf(“2. Remover Veículo: \n”);
 printf(“3. Mostrar PRÉ-ORDEM: \n”);
 printf(“4. Mostrar EM ORDEM: \n”);
 printf(“5. Mostrar PÓS-ORDEM: \n”);
 printf(“6. Imprimir Árvore \n”);
 printf(“\nOpção [0 para Sair]: “);
 scanf(“%d”, &op);
switch(op)
{
case 1:
 system(“CLS”);
 printf(“\nCarro: “);
 scanf(“%s”, &ca.nome);
 printf(“\nMarca: “);
 scanf(“%s”,&ca.marca);
 printf(“\nAno de Fabricação: “);
 scanf(“%d”, &ca.ano);
 printf(“\nPreço do Veículo: “);
 scanf(“%f”, &ca.preco);
 printf(“\nDigite um Número (Referência na Árvore): “);
 scanf(“%d”,&c);
 inserir(&pRaiz,c,ca);
 system(“PAUSE”);
 break;
case 2:
 system(“CLS”);
 printf(“\nDigite um Número: “);
 scanf(“%d”,&c);
 remover(&pRaiz,c);
 system(“PAUSE”);
 break;
 
87
case 3:
 system(“CLS”);
 exibirPreOrdem(&pRaiz);
 system(“PAUSE”);
 break;
 
case 4:
 system(“CLS”);
 exibirEmOrdem(&pRaiz);
 system(“PAUSE”);
 break;
case 5:
 system(“CLS”);
 exibirPosOrdem(&pRaiz);
 system(“PAUSE”);
 break;
case 6:
 system(“CLS”);
 imprimir(&pRaiz);
 printf(“\n”);
 system(“PAUSE”);
 break;
 
case 0:
 break;
default:
printf(“\n\nOpção Inválida. \n”);
system(“PAUSE”);
break;
}
}while(op!=0);
return 0;
}
88
Considerando a estrutura de dados árvore binária e o percurso sendo executa-
do por meio de busca em profundidade, apresente as rotinas de programação 
em linguagem C que correspondem aos percursos: pré-ordem, em ordem e 
pós-ordem.
void exibirPreOrdem(No **pRaiz) {
if((*pRaiz) != NULL) {
 printf(“%i\n”, (*pRaiz)->numero);
 exibirPreOrdem(&(*pRaiz)->esquerda);
 exibirPreOrdem(&(*pRaiz)->direita); }
}
void exibirEmOrdem(No **pRaiz) {
if((*pRaiz) != NULL) {
 exibirEmOrdem(&(*pRaiz)->esquerda);
 printf(“%i\n”, (*pRaiz)->numero);
 exibirEmOrdem(&(*pRaiz)->direita); }
}
void exibirPosOrdem(No **pRaiz) {
if((*pRaiz) != NULL) {
 exibirPosOrdem(&(*pRaiz)->esquerda);
 exibirPosOrdem(&(*pRaiz)->direita);
 printf(“%i\n”, (*pRaiz)->numero); }
NA PRÁTICA
89
Resumo da Unidade 4
Nesta unidade, você conheceu os conceitos e os fundamentos das estruturas de dados 
grafos e árvores. Compreendeu, também, o funcionamento de uma árvore binária e sua
variação de árvore AVL, e implementou solução que manipulasse árvores binárias em 
linguagem C.
Nesta unidade, foram apresentados os conceitos de grafos e de árvores como 
estruturas de dados dinâmicas para a solução de problemas complexos. Nesse 
viés, foram apresentadas as árvores binárias de buscas, explorando a busca 
em profundidade e a busca em largura, com suas possíveis variações.
CONCEITO
90
Referências 
FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. Lógica de programação: a construção de 
algoritmos e estruturas de dados. 3. ed. São Paulo: Pearson Prentice Hall, 2005. Bibliote-
ca Virtual. 
MIZRAHI, V. V. Treinamento em linguagem C. 2. ed. São Paulo: Pearson Education do 
Brasil, 2008. Biblioteca Virtual.
PUGGA, S.; RISSETTI, G. Lógica de programação e estrutura de dados com aplicações 
em Java. 3. ed. São Paulo: Pearson Prentice Hall, 2009. Biblioteca Virtual.
SIMÕES-PEREIRA, J. M. S. Grafos e redes: teoria e algoritmos básicos. Rio de Janeiro: 
Interciência, 2014. Biblioteca Virtual.