ED - matéria - ines

Prévia do material em texto

Estrutura de 
Dados 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 
 
Conceitos de Programação Orientada a Objetos(POO) e Tipos abstratos de Dados(TAD) 
 
Programação Orientada a Objetos -> é a programação por meio de envio de mensagens a objetos. 
 
Soluções de Problemas OO 
 Identificar os objetos 
 Mensagens 
 Envio de sequencias de mensagens p/ obter a solução 
 
Conceitos Fundamentais em POO 
 Abstração 
 Encapsulamento 
 Herança 
 Polimorfismo 
 
Objetivos principais da POO 
Construção de sofware: 
 Mais rápido 
 Mais barato 
 Flexível(fácil de alterar) 
 
Abstração – é o processo de observar uma realidade e extrair informações relevantes a uma determinada 
aplicação. São operações mentais tais como classificação, instanciação, generalização, especialização, etc. 
 Classificação(ou categorização) : o agrupamento em classes , com base em um conjunto de atributos 
comuns a todos. 
 Generalização/Especialização: Observamos várias classes e abstraímos delas uma classe mais genérica. 
 Hierarquia de Abstrações: Composta por classes (ou categorias) da mais genérica para a mais particular. 
 
Herança – A classe veículos possui atributos comuns a todos os veículos. As classes aéreos, terrestres e 
aquáticos, herdam os atributos de veículos, além de possuírem atributos particulares. 
 
Encapsulamento – As classes encapsulam (mantém) dados e comportamentos e deixam visível á outras 
classes somente serviços que são relevantes á outras partes do programa. 
 
Polimorfismo – (várias formas) – no paradigma O.O podemos definir o mesmo comportamento em objetos de 
classes diferentes. Ex: o comportamento mover em uma peça de xadrez e, também em uma janela de uma tela de 
computador. 
 
 
 
 
2 
 
TAD e Linguagem de Programação 
TAD é um conceito importante em projetos de programas. 
O conceito tipo abstrato de Dados: apareceu pela 1º vez no trabalho de Parnas: “Criterio a serem utilizados para 
decompor sistemas em módulos” (1972) 
Ideia Principal: Ocultamento de informações: módulos devem expor a outros módulos somente a informação 
necessária para que operem corretamente. 
Tipo de Dado: em linguagem de programação, refere-se ás formas de dados que as variáveis podem assumir. São 
os tipos primitivos característicos das linguagens. Ex: real, inteiro, caractere, booleano, etc. 
Tipo de Dados Compostos: tipos de dados definidos pelo usuário usando os tipos primitivos de dados. Ex: O tipo 
de dados Funcionário, constituído de tipos tais como caracteres, real, inteiro, etc. 
Em c: O tipo funcionário seria definido como um tipo chamado de struct Funcionário. Com os campos: nome, RG, 
cargo, salário, nº de dependentes, etc. 
Tipo abstrato de Dados: composto pelos tipos de dados + operações associadas. TAD é um tipo de dado definido 
pelo programador cujas funções especificam como um cliente(outros módulos, ou o programa principal) pode 
manipular dados. 
Definição formal de TAD: é um modelo matemático que pode ser definido pelo par (V,θ), onde V é o conjunto de 
valores e θ é um conjunto de operações definidas sobre esses valores. EX: 
1. Tipo real(float) associado aos seus valores + operações válidas.(*,/,+,-,menos unitário(-)) 
2. Grafos+operações associadas 
 
 
 
 
 
 
 
 
Propriedades 
 Encapsulamento(dados+operações) 
 Ocultamento de informação : termo utilizado para descrever a habilidade de separar o conceito de sua 
implementação (característica essencial de um TAD) 
 Ao usuário são fornecidos a descrição dos valores e o conjunto de operações, mas a implementação é 
invisível e inacessível. 
 Levam a projetos 
o Reutilizáveis 
o Portáveis 
o Modulares 
 
Estrutura de Dados: implementação dos TADs em uma linguagem de programação. 
As diferentes linguagens de programação tem maneiras diferentes de implementar um TAD (algumas de 
forma mais direta do que outras). C++ ( e outras LP00) implementa TAD por meio de classes, objetos e 
métodos , onde são utilizados os conceitos de abstração e ocultamento de informação. 
Dados 
Operações 
Associadas 
TAD 
 
 
3 
 
Introdução ao C++ 
A orientação a objetos surgiu para suprir a grande demanda por software, o qual precisava ser 
construído rápido, correta e economicamente. 
Fortemente baseada no principio de reutilização de componentes, a orientação a objetos permite uma 
redução do tempo de implementação, e por meio da organização modular e independente, melhora o 
tempo de manutenção e aumenta a confiabilidade dos programas. 
1. Primeiros Programas 
Entrada e saída por meio de cin e cout. (substituindo o scanf e o printf, respectivamente, da linguagem 
c) 
*abrir Ex1.cpp* 
 
2. Namespace 
No programa anterior, prefixamos as funções cin, cout e endl por std:: (as 3 funções ao mesmo namespace std). 
Para omitir o std na frente de cada função precisamos avisar o compilador usando a seguinte declaração: 
using namespace std; 
antes da função main 
*abrir Ex2.cpp* 
 
 
3. Uma visão geral de orientação a objetos em c++ 
C++ implementa os 3 conceitos fundamentais de O.O: 
 Encapsulamento 
 Herança 
 Polimorfismo 
 
 
4 
 
 
*abrir Ex3.cpp* 
 
*abrir Ex4.cpp* 
 
 
 
 
 
5 
 
*abrir Ex5.cpp* 
 
 
 
 
6 
 
22/10/2014 
Exemplo 2: (*Ex6.cpp*) Projetar um TAD para um circulo. O circulo é definido por meio do raio e as operações 
incluem: o construtor de um objeto circulo, a função que calcula a área de um circulo e a 
função que calcula o perímetro do circulo. 
 
 
 
 
 
 
 
 
 
7 
 
Herança: 
Exemplo(*Ex7.cpp*) Vamos supor o TAD cilindro. Dados incluem: raio e a altura(h). Operações incluem: 
construtor de cilindro, área do cilindro, volume do cilindro. 
Área = Perímetro da Base * (Altura+raio) 
 
Volume = Área da Base * Altura 
 
 
 
 
 
 
8 
 
 
A classe Cilindro: pode ser derivada da classe circulo, herdando suas propriedades. 
Classe circulo: passar a visibilidade dos atributos privados(private) para as classes derivadas, fazendo-os 
protected. 
 
Forma Geral para a definição de uma classe derivada 
class Derivada::modificador_acesso Base{ 
 ... 
}; 
 
Modificador_acesso: pode ser public ou private. Possui o seguinte comportamento: 
Acesso na classe Base Modificador de Acesso Acesso herdado da Base 
Private Public Não acessível 
public Public Public 
Protected Public Protected 
Private Private Não acessível 
Public Private Private 
protected private Private 
 
 
 
 
9 
 
Listas lineares: Pilhas, filas, listas, listas circulares, filas de 
propriedades(estruturas lineares) 
1. Introdução 
Listas lineares: é um conjunto de n (N>0) elementos de informação ( em que: 
 é o primeiro elemento 
 Para 1<k<n, é precedido por e é seguido de 
 é o último elemento do conjunto 
 
Operações comuns 
1. Ter acesso a , k qualquer, para examinar ou alterar o seu conteúdo. 
2. Inserir um elemento novo antes ou depois de . 
3. Remover 
4. Combinar 2 ou mais listas lineares em uma só lista linear 
5. Quebrar uma lista linear em duas ou mais listas 
6. Copiar uma lista linear em um outro espaço 
7. Determinar o número de elementos de uma lista linear, e outras... 
 
Nomes especiais, como pilha ou fila, são dados para as listas lineares, de acordo com a maneira que 
essas operações são realizadas. 
 Amaneira de representar listas depende das operações mais frequentes. 
 Não existe, em geral, uma única representação para a qual todas as operações são eficientes. 
EX: Como atender de maneira eficiente as duas operações: 
1. Ter acesso fácil(direto) ao k-ésimo elemento da lista ( 
2. Inserir ou remover elementos em qualquer posição da lista 
 
Pilha 
Definição: é uma lista linear em que todas as inserções e remoções 
são feitas em uma mesma extremidade da lista linear. Esta 
extremidade é chamada de topo da pilha. É conhecida como uma 
estrutura do tipo LIFO(Last In First Out). 
 
Operações definidas para uma pilha 
1. Verificar se a pilha está vazia (EMPTY) 
2. Inserir um elemento na pilha (empilhar ou push) no lado do topo 
3. Remover um elemento (desempilhar ou pop) do lado do topo 
4. Consultar ou mostrar o elemento que se encontrar no topo da pilha (TOP) 
5. Mostrar quanto elementos estão na pilha 
 
Exemplo de aplicação de pilhas 
1. Na execução de um programa: é usada na chamada de funções para armazenar o endereço de 
retorno. 
 
 
10 
 
2. Na avaliação de expressões aritméticas: a pilha pode ser usada para transformar expressões em 
notação polonesa reversa e, também, é usada na avaliação da expressão em notação polonesa 
reversa. 
 
Alocação sequencial 
Os elementos da pilha ocupam posições consecutivas na memória (vetor contendo os elementos da 
pilha) 
 
Vetor de inteiros (reais, caracteres, ou um outro tipo definido pelo usuário) 
Topo – valor inteiro: indicando a posição do elemento que está no topo da lista. 
 
Especificação do TAD Pilha 
Usando classes em C++ 
*abrir Ex8.cpp* 
 
 
 
11 
 
 
 
 
 
 
12 
 
28/10/2014 
Uso do tipo de dados genérico template para o TAD pilha 
Template : especifica um nome genérico para o tipo de dado manipulado pela classe, função, ou mesmo 
uma coleção(vetor, matriz, etc). Por exemplo, pode-se dar o nome genérico Tobjeto para definir o tipo 
de dados manipulado por uma classe. 
Ex: 
class colecao{ 
 ... 
 int A[100]; 
 ... 
}; 
Declaração do objeto: 
Colecao obj; 
Usando Template: 
template<class Tobjeto> 
class coleção{ 
 ... 
 Tobjeto; 
 ... 
 public: 
 coleção(); 
 Tobjeto metodo1(Tobj); 
}; 
Declaração de Objeto 
colecao<int>obj1; 
colecao<float>obj2; 
colecao<char>obj3; 
Obs: 
1. Tobjeto representa o nome genérico, o qual pode ser um tipo primitivo da linguagem C ou um tipo 
definido pelo usuário. 
2. A lista de padrões template 
<class T1, class T2,..., class Tn> deverá precede a especificação da classe template. 
3. Os métodos da classe que usa templates devem ser tratados como funções template. Na 
implementação dos métodos: 
template<class Tobjeto> 
Coleção::Coleção(){ 
 ... 
} 
Template<class Tobjeto> 
Tobjeto Coleção::modelo1(Tobjeto E){ 
 .... 
} 
4. Todas as referencias á classe como um tipo de dado deve incluir o tipo do template entre “<” e “>” 
Template<class Tobjeto> 
Tobjeto Coleção<TObjeto>::modelo1(Tobjeto E){ 
 .... 
} 
5. Templates também podem ser usados para definir funções templates, permitindo que sejam 
utilizados parâmetros genéricos. 
Ex: 
 
 
13 
 
template<class Tgenerico> 
int BuscaSequencia(Tgenerico x[], Tgenerico y){ 
 ... 
} 
Redefinição do TAD pilha usando template 
*abrir ex9.cpp* 
 
 
 
 
14 
 
 
Obs: Os argumentos da definição template podem incluir expressões constantes, além de nomes de 
tipos de dados genéricos. 
Ex: template<class TPILHA, int MAX> 
 class pilha{ 
 ... 
 TPILHA S[MAX]; 
 ... 
}; 
Na implementação dos métodos 
template<class TPILHA, int MAX> 
 … 
 Topo=-1; 
 … 
} 
(fazer de forma semelhante para os demais métodos) 
Na declaração de objetos da classe pilha 
pilha<int, 100> P1; //pilha p/ armazenar inteiros 
pilha<char, 200> P2; //pilha p/ armazenar caracteres 
 
Implementação Dinâmica do TAD Pilha 
a) Ponteiros em C 
 Int *p, *q; //ponteiros para inteiros 
 Int a=5,b; 
 P=&b;//p recebe o endereço de b 
 *p=a;//b=5. Isso significa que o conteúdo da variável 
apontada por p 
 
b) Ponteiros para classes 
 
 
15 
 
Objetos que apresentam uma referencia para alguma classe são tratados de forma semelhante aos 
ponteiros para estruturas(struct) em c. 
class *p; { pilha *p; 
c) Representação encadeada de pilha 
Antes de especificar o TAD pilha, que será definido por meio de nós encadeado, vamos definir 
inicialmente o nó da pilha como sendo uma classe. 
 
d) Definição da classe Nó da pilha 
 
*abrir ex11.cpp* 
 
e) Implementação da classe Nó 
*abrir ex11.cpp* 
 
 
16 
 
 
05/11/14 
 
 
 
17 
 
 
 
 
 
 
18 
 
Aplicações do TAD Pilha 
a) Avaliação do balanceamento de expressões matemáticas 
O TAD pilha pode ser usado para avaliar o balanceamento de parênteses, colchetes e chaves em uma 
expressão. O programa deve verificar se existe um número igual de abre e fecha parênteses (chaves, 
colchetes, etc.). 
EX: {(A-[B-C]+D)-[E+F]} 
Solução: utiliza-se uma estrutura de pilha: 
I. A cada símbolo {([ encontrado na expressão, coloca-o na pilha 
II. A cada símbolo })] encontrado a pilha será examinada. 
Se estiver vazia, a expressão é considerada inválida. 
Senão retira-se o elemento da pilha e compara-o com o símbolo atual: 
Se for o símbolo correspondente, continua-se a análise. 
Senão a expressão está inválida 
III. No final, a pilha deve estar vazia, do contrário a expressão é mal formada. 
*abrir ex12.cpp* 
 
 
 
19 
 
 
 
 
 
20 
 
 
 
 
 
 
 
21 
 
b) Notação de Expressões 
 Forma infixa: A+B 
 Forma pré-fixa: +AB 
 Forma pós-fixa: AB+ 
Transformação de expressões na forma infixa para forma pós fixa 
1. Parentizar a expressão de acordo com as regras de precedência das operações. 
2. Converte a expressão parentizada 
3. Retirar os parênteses 
 
 
 
 
 
 
 
c) Avaliação da Pós-fixa 
Uso de uma pilha de operandos 
Processo de Avaliação 
Dado uma expressão matemática na notação posfixa(notação polonesa reversa). 
1. Criar uma pilha de operandos 
2. Ler símbolos 
 Se operandos empilhá-lo 
 Se operador Desempilhar os dois últimos operandos, efetuar a operação e, colocar o resultado 
na pilha 
3. Continuar a leitura de símbolos enquanto expressão não terminar 
4. O resultado está no topo da pilha 
12/11/2014 
Ex: 623+-382/+*2^3+= 52 
 
Algoritmo para Avaliação 
*abrir ex13.cpp* 
A+B*C = (A+(B*C)) = (A+(BC*) = (A(BC*)+) = ABC*+ 
Ex1 1 2 2 3 
A/B^C+D*E-A/C = (((A/(B^C))+(D*E))-(A/C)) = (((A/(BC^))+(DE*))-(AC/)) = (((A(BC^)/)+(DE*)-(AC/)) = -> 
Ex2 1 2 2 
(((A(B^C)/)(DE*)+)-(AC/)) = ABC^/DE*+AC/- 
2 3 
 
 
22 
 
 
 
 
 
23 
 
 
 
 
 
 
24 
 
 
 
Processo de Transformação da notação infixa para a posfixa 
Exemplo: A*(B+C)/D= 
Símbolo lido Pilha de Operadores Posfixa 
- vazia - 
A vazia A 
* * A 
( -> sempre empilha *( A 
B *( AB 
+ *(+ AB 
C *(+ ABC 
) ->desempilhar operadores ate ) * ABC+ 
/ / ABC+* 
D / ABC+*D 
= Vazia ABC+*D/ 
 
 
 
 
 
 
25 
 
Definição das prioridades dos operadores 
 Prioridade 1 Prioridade 2 
Operador Prioridade dentro da Pilha Prioridade de chegada 
^ 3 4 
* 2 2 
/ 2 2 
+ 1 1 
- 1 1 
( 0 5 
 
Processo de Conversão para Posfixa 
1. Constroi-se uma pilha de operadores 
2.Ler símbolo 
 Se for operando, coloca-o na posfixa 
 Se for operador, verificar sua prioridade (prioridade 2) com a prioridade do elemento que está 
no topo da pilha(prioridade 1): 
 Enquanto a prioridade do operador lido for menor ou igual a prioridade do elemento do 
topo, desempilhar o operador e coloca-lo na posfixa 
 Empilhar o símbolo lido 
 Se simb é um ‘)’, desempilhar todos os operadores da pilha até encontrar o ‘(‘ e coloca-los na 
posfixa 
3. Até que expressão não terminar 
4. Esvaziar a pilha, colocando os operadores na posfixa 
 
Algoritmo para conversão 
*abrir ex14.cpp* 
 
 
 
26 
 
 
Avaliação de Expressões matemáticas (conversão + avaliação) 
Ex: 12/3*2+6*2-12*2= 123/2*62*+122*- 
 
 
Processo de conversão e avaliação 
1. Constroe-se 2 pilhas: uma de operando e outra de operadores 
2. Ler símbolos 
 Se operando, coloca-o na pilha de operandos 
 Se operador, verificar sua prioridade sobre o ultimo operador. Colocar no topo da pilha 
Enquanto a prioridade 2(símbolo) for maior ou igual a prioridade 1 do elem do topo da pilha: 
 Resolver a operação removendo-se 2 elementos da pilha de operando com o 
operador que está no topo da pilha e coloca o resultado na pilha de operando 
 Empilha-se o símbolo lido na pilha de operadores 
 Se operador for ‘)’, resolve-se as operações que estão na pilha, colocando-se os 
resultados na pilha de operando ate encontrar o ‘(‘ correspondente. 
3. Até que símbolo seja igual a ‘=’ 
4. Esvaziar a pilha de operadores, resolvendo-se as operações e colocando os resultados na pilha de 
operadores 
 
Algoritmo em c++ 
*abrir ex15.cpp* 
12/3*2+6*2-12*2 = ((((12/3)*2)+(6*2))-(12*2)) = ((((123/)*2)+(62*))-(122*)) = ((((123/)*2)+(62*))-(122*)) = 
 1 2 2 
((((123/)2*)+(62*))-(122*)) = ((((123/)2*)(62*)+)-(122*)) = ((((123/)2*)(62*)+)(122*)-) = 123/2*62*+122*- 
2 2 2 3 
 
 
27 
 
 
 
 
Fazer Lista de exercícios 1 sobre classes e pilhas 
 
 
 
 
28 
 
Fila 
É uma estrutura linear do tipo FIFO(First In First Out) no qual todas as inserções são feitas em uma 
extremidade (fim da fila) e as remoções são feitas da outra extremidade (o início da fila). 
1. Operações que são realizadas em uma fila 
 Criar uma fila vazia 
 Inserir um elemento na fila 
 Eliminar um elemento da fila 
 Verificar se a fila está vazia 
 Verificar se a fila está cheia 
2. Representação sequencial de uma Fila 
 
Convenção 
Fim – indica a posição onde se encontrar o 
elemento que está no final da fila. 
Inicio – indica a posição anterior ao elemento 
que está no ínicio da fila. 
 
 
 
Definição do TAD fila em C++ usando classes: 
*abrir ex16.cpp* 
 
 
 
29 
 
 
 
 
 
 
 
30 
 
19/11/14 
O TAD fila circular e sua representação 
 
Convenções 
1. Representação por um vetor, cujos índices estão no intervalo [0, N-1] 
2. Ponteiros de controle: inicio e fim 
3. Inicialmente inicio=fim=0(fila vazia) 
4. Condição de fila vazia: inicio=fim 
5. Quando fim=N-1, o próximo elemento será inserido na posição 0 
Ex: Suponha que N=10, o cálculo das posições de inserção na fila será: 
 0 módulo 10=0 
 1 módulo 10=1 
 2 módulo 10=2 
 ... 
 9 módulo 10=9 
 10 módulo 10=0 
 
O TAD fila circular 
Definição : É exatamente a mesma vista anteriormente( Representação Sequencial) 
Implementação de alguns Métodos 
*abrir ex17.cpp* 
Fim=(fim+1) módulo N 
e não fim=fim+1 
Se fim=9 e N=10 => fim=(9+1) módulo 10 = 0 
 
 
31 
 
 
 
 
 
 
32 
 
O TAD fila e a sua representação encadeada (alocação Dinâmica de 
Memória) 
 
A definição da classe Nó da fila 
Igual á classe Nó de pilha 
*Abrir Ex12.cpp* 
Definição da classe fila 
A estrutura da fila terá informação sobre: inicio e fim da fila. 
E fornecerá os seguintes métodos: 
 Construtor 
 Método p/ inserir elementos 
 Método p/ remover elementos 
 Método p/ verificar se fila vazia 
 Método p/ exibir o primeiro elemento da fila 
 Método p/ destruir a estrutura encadeada 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
33 
 
Definição da classe fila em C++ 
*abrir ex18.cpp* 
Inserção 
1º caso: Fila Vazia 
 
inicio = novo; 
fim = novo; 
2º caso: Fila com elementos 
 
fim -> SetProx(novo); 
fim = novo; 
Remoção 
1º caso: Fila Vazia : não faz nada 
2º caso: Fila com um único elemento 
 
incio = NULL; 
fim = NULL; 
3º caso: Fila com mais de um elemento 
 
aux = inicio; 
inicio = inicio->GetProx(); 
delete aux; 
 
 
34 
 
 
 
 
 
35 
 
 
O TAD fila com prioridades 
Em algumas aplicações deseja-se ordenar a fila não apenas pela ordem de chegada, mas também 
através da associação de prioridades a cada elemento. 
=>Neste caso a fila é ordenada por prioridades. 
=>Alterações á implementação anterior: 
 Nó da Fila: acrescentar mais um campo para representar o nível de prioridade 
 Modificação do algoritmo de inserção (para considerar não só a ordem de chegada, mas também 
a prioridade do elemento. Ou então a modificação do algoritmo de remoção.) 
26/11/2014 
Nó da Fila com Prioridade 
 
*abrir ex19.cpp* 
 
 
 
 
 
 
 
36 
 
implementação do método Insert na classe fila com prioridade 
Inserção 
1º caso: Fila Vazia 
 
inicio = novo; 
fim = novo; 
2º caso: Inserção no inicio da Fila 
 
Nesse caso q vale null e faz-se 
Novo->setProx(p); 
Inicio=null; 
3º caso: Inserção no final da Fila 
 
Nesse caso p vale null 
q->setProx(nvovo); 
novo->setProx(null); 
fim=novo; 
4º caso: Inserção no meio da Fila 
 
q->setProx(Novo); 
novo->setProx(p); 
 
 
 
37 
 
 
 
 
 
38 
 
 
 
 
 
39 
 
 
 
 
Fazer lista de Exercicios 2 sobre Fila 
 
 
40 
 
Lista Encadeadas 
Definição : é uma coleção de objetos, os quais possuem tipos de dados iguais. 
Operações que podem ser realizadas: 
1. Inserção de um elemento na lista: 
 Inserção no Inicio 
 Inserção entre 2 elementos quaisquer 
 Inserção no final da lista 
 Inserção após um determinado elemento 
2. Localização de um elemento na lista 
3. Exibição de um elemento corrente 
4. Verificação de lista vazia 
5. Concatenação de uma lista com outra lista 
6. Intercalação de 2 listas, gerando-se uma única lista 
7. Inversão de uma lista(inversão dos ponteiros de uma lista) 
8. Intercalação de 2 listas, criando-se uma terceira lista 
9. Etc... 
Lista simplesmente encadeada 
 
Definição da classe lista com alocação dinâmica e implementação de alguns métodos 
OBS: uso da classe genérica No<T> para definir a lista encadeada. 
*abrir Ex20.cpp* 
Inserção 
1º caso: Fila Vazia 
 
2º caso: Inserção no inicio da Fila 
 
3º caso: Inserção no meio da Fila 
 
 
41 
 
 
 
 
 
 
 
42 
 
 
 
 
 
43 
 
 
 
10/12/14 
A implementação do método Find() 
O método Find() retorna o endereço do nó anterior ao nó que contém o elemento procurado. Find() 
retornará NULL caso o elemento esteja no primeiro, ou então não esteja na lista. Dessa forma será 
necessário retornar também uma segunda variável indicando se achou ou não o elemento na lista. 
*abrir ex20.cpp* 
 
 
 
44 
 
 
 
Remoção 
1º caso: Fila Vazia: Não há o que remover da lista 
2º caso: Remoção do primeiro elemento da lista 
 
P=L; 
L=L->GetProx(); 
Delete p; 
 
3º caso: Remoção no meio e no fim da lista 
 
P=ant.getProx(); 
Ant->SetProx(p->GetProx()); 
Delete p;45 
 
 
Concatenar 
 
L<- L->Front(); //obter o nó inicial de L 
P<-inicio; 
While(p->GetProx()!=NULL) p=p-
>GetProx(); 
p->SetProx(l);//ligando o ultimo nó da 
lista corrente com a lista l 
 
 
 
 
 
46 
 
Lista Duplamente Encadeada 
 
Implementação da classe NoDuplo 
*abrir ex21.cpp* 
 
 
 
47 
 
 
A classe Lista Duplamente Encadeada 
 
 
 
 
 
48 
 
Inserção 
1º caso: Lista Vazia 
 
2º caso: Inserção no inicio da Lista 
 
Novo->SetDir(I); 
I->SetEsq(Novo); 
I=Novo; 
3º caso: Inserção no final da Lista 
 
Novo->SetEsq(F); 
F->SetDir(Novo); 
F=Novo; 
4º caso: Inserção no meio da Lista 
 
Q=P->GetEsq(); 
P->SetEsq(Novo); 
Novo->SetDir(P); 
Q->SetDir(Novo); 
Novo->SetEsq(Q); 
 
 
 
 
49 
 
Remoção 
1º caso: Fila Vazia: Não há o que remover da lista 
2º caso: Remoção do primeiro nó da lista 
 
I=I->GetDir(); 
I->SetEsq(NULL); 
Detele p; 
 
3º caso: Remoção do ultimo nó da lista 
 
F=f->GetEsq(); 
F->SetDir(NULL); 
Delete p; 
 
4ºcaso: Remoção no meio da lista 
 
O=p->GetEsq(); 
Q=p->GetDir(); 
O ->SetDir(Q); 
Q->SetEsq(O); 
Delete p; 
 
 
 
 
Fazer Lista de Exercícios 3 sobre Listas 
 
 
50 
 
17/12/2014 
Arvores 
São estruturas não lineares, onde um elemento da estrutura pode ter múltiplos sucessores. 
 
Definição 
Árvore é um conjunto finito de um ou mais nós de tal forma que: 
 Existe um nó especialmente chamado de raiz 
 Os nós restantes são desdobrados em , onde cada um destes conjuntos constituem uma 
árvore. são denominados subarvores da raiz. 
 
Terminologia 
 
 Nó raiz: origem da árvore. Nó raiz:A. 
 Grau de um nó: número de subárvores que partem do nó. Grau(A)=3, Grau(B)=2, Grau(I)=0 
 Nós folhas ou nós terminais: são os nós que possuem grau 0. Ex: {k, L, F, G, M, I, J} 
 Grau de uma árvore: é o grau máximo de seus nós. Na árvore exemplo, o grau da árvore é 3. 
 Altura ou profundidade de uma árvore: é o nível máximo da árvore. Na árvore exemplo, o nível 
da árvore é 4. 
 As raízes das subarvores de um nó x são chamados de filhos de x. x é chamado pai desses filhos. 
Os filhos de um mesmo pai são denominados irmãos. No exemplo: A é pai de {B, C, D}, e B,C e D 
são irmãos. 
 
 
 
 
51 
 
Árvores Binárias 
 
Definição: uma árvore binária é: 
I. Um conjunto vazio de nós 
II. Um nó raiz com duas árvores binárias separadas, denominadas subárvore esquerda e subárvore 
direita. 
 
Nós da Árvore: 
 
 
*abrir ex22.cpp* 
 
 
 
 
 
52 
 
 
 
 
 
 
 
 
53 
 
Árvore Binária de Busca 
Nesta árvore todos os elementos presentes na subárvore esquerda são menores do que o conteúdo do 
nó raiz e todos os elementos da subárvore á direita são maiores ou iguais ao conteúdo do nó raiz. 
 
*abrir ex23.cpp* 
 
 
 
 
 
54 
 
Busca e Inserção 
 
Se a árvore for vazia, criar o nó raiz com o elemento a ser inserido(elem) 
Senão percorrer a árvore e localizar a posição de inserção: 
 Enquanto (existe nó) faça 
 Se (elem<conteúdo do nó) 
 Acessar a subárvore á esquerda 
 Senão acessar a subárvore a direita 
 Acessar o nó folha e inserir o novo elem 
 
 
 
55 
 
 
 
 
 
 
 
56 
 
Travessia ou percurso em Árvore Binária 
Consiste em “visitar” todos os nós de uma árvore uma única vez, realizando uma operação qualquer 
sobre o seu conteúdo. 
Existem três maneiras diferentes de percorrer uma árvore binária: 
 
 Pré-Ordem: visita inicialmente o nó e depois percorre-se as subárvores esquerda e direita. 
1. Visitar a raiz 
2. Percorrer a subárvore esquerda em pré-ordem 
3. Percorrer a subárvore direita em pré-ordem 
Ex: 
 
 
 
 In-Ordem: percorre-se a subárvore esquerda do nó, e depois visita o nó, e passa-se á subárvore 
direita percorrendo-a. Ex: para escrever em ordem. 
1. Percorrer em In-Ordem a subárvore esquerda 
2. Visitar a raiz 
3. Percorrer em In-Ordem a subárvore direita 
 
 
 
57 
 
 
 
 Pos-Ordem: primeiro percorre-se as subárvores esquerda e direita e depois, visita-se o nó. Ex: para 
apagar. 
1. Percorrer em Pós-Ordem a subárvore esquerda 
2. Percorrer em Pós-Ordem a subárvore direita 
3. Visitar a raiz 
 
 
Depende do que queremos fazer, determinada maneira de percorrer é mais correta ou necessária. 
 
07/01/2015 
Exemplos 
1. Percorrer a árvore 
 
 
 
58 
 
Pré-ordem: *+a/BC-d*ef: notação pré-fixa da expressão matemática 
In-ordem: a+b/c*d-e*f: notação infixa 
Pós-ordem: abc/+def*-*:notação pós-fixa 
 
2. Construir a árvore binária que originou os percursos: 
a) Pré-ordem: ABDCEGFHI 
b) In-Ordem: DBAEGCHFI 
 
3. Construir a árvore binária que originou os percursos: 
a) In-ordem: HDBIEAJFCG 
b) Pós-Ordem: HDIEBJFGCA 
 
4. Construir a árvore binária que originou os percursos: 
a) Pré-ordem: ABCDE 
b) In-Ordem: ABCDE 
 
 
 
 
 
59 
 
 
versão não recursiva para o percurso em Pré-Ordem 
 Processar a raiz de A 
 Guardar A para poder percorrer a sua subárvore C. 
 Passar á subárvore esquerda (B) e processar usa subárvore 
 Idem a subárvore D 
 Retornar a A(pilha) para acessar C. 
 
Algoritmo 
Inicio 
Inicializar uma pilha com os endereços dos nós da árvore 
Enquanto existir nós a serem processados 
 Percorrer a subárvore esquerda, mostrando o conteúdo do nó e empilhando-o até 
chegar a um nó folha. (repetição) 
 Se pilha não estiver vazia então 
 Acessar o topo, eliminando-o da pilha 
 Posicionar na subárvore a direita 
 Senão acabaram-se os nós a serem percorridos 
 Fim enquanto 
Fim 
*abrir ex23.cpp* 
 
 
60 
 
 
 
 
14/01/2015 
1. Escrever uma função na classe Árvore Binária para retornar o menor elemento da árvore. Neste 
caso considerar que a árvore não está ordenada. Desta forma, deve-se percorrer a árvore toda para 
encontrar tal elemento. Ex: 
 
 
61 
 
 
*abrir ex23.cpp* 
 
Obs: Foi utilizado percurso em pós-ordem no método Menor. 
 
2. Escrever uma função na classe Árvore Binária para calcular a quantidade de nós da árvore até o 
nível n que será fornecido, sabendo-se que o nó raiz está no nível 0, os filhos da raiz estão no nível 1 e 
assim por diante. 
 
Se p==NULL => return 0 
Se n==0 => return 1 
Se n>0 => return 1 + Contar(p->Esquerda(), n-1) + Contar(p->Direita(), n-1) 
*abrir ex23.cpp* 
 
 
62 
 
 
 
3. Escrever uma função na classe Árvore Binária para contar quantos nós não folhas existem na 
árvore. 
 
*abrir ex23.cpp* 
 
 
Função Busca 
Algoritmo modificado, onde a função retorna o nó onde o elemento foi encontrado e também o pai do 
nó. Se o elemento encontrado não tem pai(==NULL), significa que ele é a raiz da árvore. Caso o 
elemento não seja encontrado, a função retorna NULL. 
 
 
 
63 
 
*abrir ex23.cpp* 
 
 
Operação de Remoção em uma Árvore Binária de Busca 
 Encontrar o nó a ser removido D e o pai dele p. 
 Encontrar um nó substituto (nó a ser conectado ao pai p e que toma o lugar do nó a ser removido). 
 Eliminar o nó 
 A Árvore deve se manter ordenada 
 
Casos de Remoção 
Dependentes do número de filhos que o nó a ser removido possui. 
1º caso – o nó D não possui filhos(é um nó folha) => atualizar o pai p com uma subárvore vazia 
 
R – nó substituição 
R=NULL; 
p->Esquerda(R); 
2º caso – o nó D a ser removido possui um filho esquerdo, mas não um direito. 
 
 
64 
 
 
R = D->Esquerda(); 
p->Direita(R);3º caso – o nó D a ser removido possui um filho direito, mas não um esquerdo. 
 
R = D->Direita(); 
p->Esquerda(R); 
4º caso – O nó D a ser removido possui ambos os filhos esquerdo e direito. 
 
 
*O nó de substituição R deve ser o maior nó da subárvore esquerda. 
 
 
65 
 
** O nó de substituição R deve ser o menor nó da subárvore direita. 
 Selecionar o nó R, o mais a direita na subárvore esquerda. 
 Desligar esse nó da Árvore: 
-Conectar sua subárvore esquerda ao seu pai(PR) 
-Conectar R ao nó removido 
 
Algoritmo para encontrar o nó de substituição R que está mais á direita na subárvore esquerda de D 
1. Como o nó R é menor do que o nó D, vamos descer á subárvore esquerda de D. 
2. Uma vez que R é o maior dos nós á esquerda, ele será localizado percorrendo o caminho das 
subárvores á direita. Durante o percurso, deve-se guardar o nó predecessor de R, é o pai de R(PR) 
No percurso das subárvores á direita, tem-se 2 casos: 
1º caso: A subárvore direita é nula(vazia) 
 
R = Direita(D->Direita()); 
p->Esquerda(R); 
2º caso: A subárvore direita não é vazia e 
a) R é um nó folha => desliga-lo da árvore 
 
PR = Direita(NULL); //R->Esquerda()==NULL 
R->Esquerda(D->Esquerda()); 
R->Direita(D->Direita()); 
p->Esquerda(R); 
 
 
66 
 
b) R não é um nó folha => o nó R tem uma subárvore á esquerda 
 
PR = Direita(R->Esquerda()); 
R->Esquerda(D->Esquerda()); 
R->Direita(D->Direita()); 
p->Esquerda(R); 
 
Finalização: 
Depois de ter encontrado o nó R 
O nó D é substituído pelo nó R: 
 Ligar os filhos de D como filhos de R: 
 R->Esquerda(D->Esquerda()); 
 R->Direita(D->Direita()); 
Completar a ligação com o nó pai p 
 Se (p==NULL) => raiz = R 
 Senão 
 Se(D->GetDado()<p->GetDado()) 
 P->esquerda(R); 
 Senão p->Direita(R); 
 
O método Remove 
Dado elem, se elem for encontrado na árvore, remove-lo. 
*abrir ex23.cpp* 
 
 
67 
 
 
 
 
 
 
68 
 
21/01/2015 
Árvore de Busca Balanceada(AVL) 
A.Adilson V.Volsky L.Landis 
Definição de Árvore Balanceada 
Uma árvore é considerada balanceada se e somente se para cada nó, a altura da subárvore esquerda e 
da subárvore á direita diferem em no máximo 1. 
 
 Associado a cada nó da árvore AVL, existe um peso indicando o seu balanceamento, cujo valor 
deve ser necessariamente 0, 1 ou -1, indicando a diferença a altura da subárvore á esquerda e da 
subárvore a direita. 
 
Estrutura de um nó da árvore AVL 
 
Especificação da classe No_AVL(ex24.cpp) 
 
 
 
69 
 
Especificação da classe AVL 
 
Método para calcular a altura da árvore AVL 
 
 
 
 
 
 
 
 
70 
 
Busca e Inserção em uma Árvore AVL 
Estudar os casos de desbalanceamento e o rebalanceamento de árvore AVL. 
Fator de Balanceamento de um nó(FB): é a altura da subárvore esquerda do nó menos a altura da 
subárvore direita do nó. 
Inserção na árvore AVL : pode acarretar o desbalanceamento da árvore AVL. Podem ocorrer diversos 
casos de desbalanceamento. 
 
A inserção dos nós 9 e 11 não causa desbalanceamento na árvore. A árvore ficou melhor balanceada. 
Por outro lado, a inserção dos nós 3, 5 ou 7 requerem que a árvore seja rebalanceada. 
 
Para fazer o rebalanceamento deve-se analisar 2 casos de desbalanceamento. 
 
1º caso de Desbalanceamento(caso 1) 
O nó x foi inserido á esquerda de p e causou desbalanceamento FB(p)=2(ficou mais pesado á esquerda) 
e: 
1.1 Tem um filho q com FB(q)=1(sinais iguais e positivos) => fazer rotação á direita 
Ex: 
 
 
71 
 
 
Rotação a direita 
 Seja q o filho á esquerda de p 
 Torna-se p como filho direito de q 
 Torna-se o filho direito de q como filho esquerdo de p 
 
1.2 Tem um filho q com FB(q)=-1(sinais diferentes – raiz p é positiva e o filho q é negativo) => fazer duas 
rotações: Rotação_Esquerda_Direita 
 Roda-se o nó q (FB=-1) á esquerda 
 Roda-se o nó p (FB=2) a direita 
 
Rotação do nó q a esquerda 
 Seja q o filho esquerdo de p 
 
 
72 
 
 Seja np o filho direito de q 
 Torna-se q o filho esquerdo de np 
 Torna-se o filho esquerdo de np como o filho direito de q 
Rotação do nó p a direita 
 Faça p como filho direito de np 
 Faça o filho direito de np como filho esquerdo de p 
 
 
28/01/2014 
2ºcaso de desbalanceamento: x foi inserido a direita e causou desbalanceamento em P, em que FB(P) 
= -2 (-1<=FB<=1) e: 
2.1 FB(P) = -2 e possui um filho q com FB(q) = -1 (sinais iguais e negativos) 
 
 
 
73 
 
Rotação á esquerda 
 Seja q o filho direito de p 
 Torne o p filho esquerdo de q 
 Torne o filho esquerdo de q como filho direito de p 
 
2.2 FB(P) = -2 possui um filho q com FB(q) = 1 (sinais diferentes->filho positivo, rotação a direita – pai 
negativo rotação a esquerda) 
 
 Rotação do nó q a direita(FB(q) = 1 – sinal positivo) 
 Rotação do nó p a esquerda(FB(p) = - 2 – sinal negativo) 
 
 
 
74 
 
 
 
Implementação separada dos métodos caso1 e caso2 de desbalanceamento 
 
 
 
Inserção em uma árvore AVL 
Processo de inserção: 
Seja T uma árvore AVL e um elemento item a ser inserido em algum novo nó x. 
Busca-se o item 
1. Se item estiver na árvore, nada a ser feito 
2. Senão, a busca determina a posição de inserção 
3. Insere-se o novo nó na árvore 
4. Verifica-se se a inserção ocasionou desbalanceamento em algum nó 
5. Caso não tenha desbalanceado, fim da inserção 
6. Senão fazer o rebalanceamento de T, por meio das rotações 
7. Fim da inserção 
 
Verificação se algum nó de T ficou desbalanceado 
 Para cada nó v, o fator B armazena o valor hE(v) – hD(v). O nó v está balanceado se -1<=FB(v)<=1. 
 Se x for inserido na subárvore esquerda de v, e esta inclusão ocasionar um aumento na altura desta 
subárvore, soma-se 1 ao fator B de v. Se esse valor ficar igual a 2, v ficou desbalanceamento. 
 
 
75 
 
 Verificar os casos em que a inclusão de x provoca um aumento na altura h(v) da subárvore: 
 A inserção do nó x acarreta alteração na subárvore esquerda no seu nó pai w. 
 O campo FatorB permite avaliar se essa alteração pode ou não se propagar aos outros nós v que 
estão no caminho entre w e a raiz da árvore. 
 Senão, se x for inserido na subárvore direita de v, casos simétricos deverão ser considerados. 
 
EX: suponha que o nó x foi inserido na subárvore esquerda de v. 
 
 
 
A analise inicia no nó w e propaga-se em seus nó 
ancestrais, de forma recursiva. O processo é 
encerrado quando se acha a raiz de uma subárvore 
Tv, que não foi modificada. 
Três situações distintas podem ocorrer: 
 
 
 
Caso a: FatorB(v) = -1 antes da inclusão do nó x(mais pesado à direita) 
 
 
FB(v) fica 0 e a altura da subárvore v não foi modificada. 
Os balanços dos nós no caminho entre v e a raiz não foram alterados. (se 
v é a raiz – nada fazer também) 
 
 
 
Caso b: FB(v) = 0 antes da inclusão de x. 
 
 
O fatorB(v) = 1, e a altura da subárvore foi modificada. 
Analisar os demais nós no caminho até a raiz da árvore. Se v 
é a raiz, encerrar a analise, senão repetir o processo. 
 
 
 
Caso c: FB(v) = 1 antes da inclusão de x. 
O FatorB(v) = 2, o nó v ficou desbalanceado: 
 Aplicar a rotação correta. 
 Qualquer rotação implica que a subárvore resultante tenha a mesma 
altura da subárvore antes da inclusão: as alturas dos nós ancestrais não 
precisam ser avaliados. 
 
 
76 
 
 
Implementação do algoritmo de inserção