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. 
 
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. 
 
 
2 
 
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. 
 
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. 
Dados 
Operações 
Associadas 
TAD 
 
 
3 
 
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 
 
*abrir Ex3.cpp* 
*abrir Ex4.cpp* 
*abrir Ex5.cpp* 
 
 
4 
 
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. 
 
 
 
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 
 
 
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 
 
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 
 
 
5 
 
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. 
 A maneira de representar listas depende das operações mais frequentes. 
 Não existe, em geral, uma única representação para a qual todas as operaçõessã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. 
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) 
 
 
 
6 
 
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* 
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> 
 
 
7 
 
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: 
template<class Tgenerico> 
int BuscaSequencia(Tgenerico x[], Tgenerico y){ 
 ... 
} 
Redefinição do TAD pilha usando template 
*abrir ex9.cpp* 
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 
Objetos que apresentam uma referencia para alguma classe são tratados de forma semelhante aos 
ponteiros para estruturas(struct) em c. 
 
 
8 
 
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* 
05/11/14 
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* 
 
b) Notação de Expressões 
 Forma infixa: A+B 
 Forma pré-fixa: +AB 
 Forma pós-fixa: AB+ 
 
 
9 
 
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* 
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 
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 
 
 
10 
 
C *(+ ABC 
) ->desempilhar operadores ate ) * ABC+ 
/ / ABC+* 
D / ABC+*D 
= Vazia ABC+*D/ 
 
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ãoterminar 
4. Esvaziar a pilha, colocando os operadores na posfixa 
 
Algoritmo para conversão 
*abrir ex14.cpp* 
 
Avaliação de Expressões matemáticas (conversão + avaliação) 
Ex: 12/3*2+6*2-12*2= 123/2*62*+122*- 
 
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 
 
 
11 
 
 
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* 
 
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. 
 
 
 
 
12 
 
 
Definição do TAD fila em C++ usando classes: 
*abrir ex16.cpp* 
 
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 
 
 
13 
 
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 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
14 
 
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; 
 
 
 
 
 
15 
 
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* 
implementação do método Insert na classe fila com prioridade 
casos de inserção: 
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 
 
 
16 
 
 
q->setProx(Novo); 
novo->setProx(p); 
 
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 
 
 
17 
 
 
2º caso: Inserção no inicio da Fila 
 
3º caso: Inserção no meio da Fila