document onl_apostila-de-c-559bf457d3ee1

Prévia do material em texto

5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 1/61
 
AEDAED –– Algoritmos e EstruturasAlgoritmos e Estruturas
de Dadosde Dados
Estruturas de dados em C++
(atualizado em 25/9/2007)
Renato Fabiano Matheus, PUC Minas, 2007/2Sistemas de Informação
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 2/61
 
25/9/2007 / 2AED / PUC Minas / 2007-2
AgendaAgenda
 Visão geral

Programação em C++ - C++
 Programação orientada a objetos - POO
 Estruturas de dados – AED
 Pilhas
 Filas
 Listas
 Listas circulares
 Tabelas
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 3/61
 
25/9/2007 / 3AED / PUC Minas / 2007-2
AgendaAgenda
 Visão geral

Programação em C++ - C++
 Programação orientada a objetos - POO
 Estruturas de dados – AED
 Pilhas
 Filas
 Listas
 Listas circulares
 Tabelas
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 4/61
25/9/2007 / 4AED / PUC Minas / 2007-2
Visão geral do móduloVisão geral do módulo
 C++

POO
 AED
POO
AEDC++
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 5/61
25/9/2007 / 5AED / PUC Minas / 2007-2
AgendaAgenda
 Visão geral

Programação em C++
 Programação orientada a objetos - POO
 Estruturas de dados – AED
 Pilhas
 Filas
 Listas
 Listas circulares
 Tabelas
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 6/61
25/9/2007 / 6AED / PUC Minas / 2007-2
C++ / ConceitosC++ / Conceitos
 Algoritmo = descrição de um padrão de comportamento
representado por um conjunto finito de ações.
 Dado = representação abstrata da informação que pode ser
tratada computacionalmente.
 Programa = formulações concretas de algoritmos abstratos,
baseados em representação e estruturas específicas de
dados. Representam classes especiais de algoritmos
capazes de serem seguidos por computadores.
PROGRAMA = ALGORITMO + ESTRUTURA DE DADOS
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 7/61
25/9/2007 / 7AED / PUC Minas / 2007-2
C++ / ConceitosC++ / Conceitos
 Tipo de dado = especificação da classe de valores que podem ser
associados a um dado, bem como das operações que podem ser
usadas para criar, acessar e modificar estes valores.
 Tipos simples ou primitivos
 Ex: inteiro, real, lógico, caractere
 int contador = 0;
 Tipos compostos ou estruturados = coleção de valores simples
 Ex.: registros, arranjos, arquivos
 struct _Cubo {
int tamanhoAresta_cm;
int calculaVolume();
}
 Tipos definidos pelo usuário = tipos compostos definidos pelo usuário
 Ex.: estruturas, classes
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 8/61
25/9/2007 / 8AED / PUC Minas / 2007-2
C++ / Ambiente de desenvolvimentoC++ / Ambiente de desenvolvimento
 Ambiente de desenvolvimento Bloodshed Dev-C++
 http://www.bloodshed.net/devcpp.html
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 9/61
25/9/2007 / 9AED / PUC Minas / 2007-2
C++ / A linguagemC++ / A linguagem
 A linguagem C é um subconjunto da linguagem
C++
 C++ é uma linguagem OO (Orientada a Objeto)
 Foi proposta por Bjarne Stroustrup (1997, p. 10)
a partir da linguagem C (KERNIGHAN;
RITCHIE, 1978)
 http://www.research.att.com/~bs/homepage.html
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 10/61
25/9/2007 / 10AED / PUC Minas / 2007-2
C++ / Programa mínimoC++ / Programa mínimo
Inclusão de arquivos de cabeçalhos
de bibliotecas padrão (STL)
Inclui namespace
std no
namespace global.
Evitando
necessidade de
prefixar:
(e.g. std::cout)
(STROUSTRUP,
1997, p. 117) Variável “nome” do tipo “string”,definido na STL
Entrada e saída
padrão
Assinatura da função
“main”
Início e fim de bloco
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 11/61
25/9/2007 / 11AED / PUC Minas / 2007-2
C++ / C++ / namespacenamespace stdstd
#include <iostream>
int main (int argc, char* argv[])
{
std::cout << "H e l l o , n e w w o r l d !\ n ";
}
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 12/61
25/9/2007 / 12AED / PUC Minas / 2007-2
C++ / SintaxeC++ / Sintaxe
 Sintaxe da linguagem C/C++
http://www.cprogramming.com/reference/ 
 Referência de library
http://www.cplusplus.com/reference
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 13/61
25/9/2007 / 13AED / PUC Minas / 2007-2
C++ / SintaxeC++ / Sintaxe
 Sensível a maiúsculas e minúsculas

“A” diferente de “a”
 INT não é um tipo de dado válido
 Operadores

Lógicos: AND && OR || NOT EQUAL !=
EQUAL ==
 Atribuição: = += -=

Comentários
 de linha: //
 de bloco: /* … */
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 14/61
25/9/2007 / 14AED / PUC Minas / 2007-2
C++ / SintaxeC++ / Sintaxe
 Pós e pré-incremento

++i--
 Vetores e matrizes (índices começam pelo
elemento 0)

int matriz[10][9]
 Primeiro elemento matriz[0][0]
 Último elemento matriz[9][8]
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 15/61
25/9/2007 / 15AED / PUC Minas / 2007-2
C++ / SintaxeC++ / Sintaxe
 Loops
// como não há blocos, só próximo comando está no loopfor (cont = 0; cont < 100, sequencia[cont] != 0; cont++)
soma += sequencia[cont];
cont = 0;
do
{
sprintf( mensagem, "Qual o numero de ordem %d? ", cont
+ 1 );
sequencia[cont] = leNumero(mensagem);
// Na primeira execução da primeira comparação, cont
// tem valor 0 e na segunda conta tem valor 1, devido
// ao operador de pós-incremento ++
} while( cont++ < 100 && sequencia[cont] != 0 );
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 16/61
25/9/2007 / 16AED / PUC Minas / 2007-2
C++ / Escopo de variáveisC++ / Escopo de variáveis
 Declaração
 pode acontecer em qualquer lugar onde um
comando qualquer pode (STROUSTRUP,
1997, p. 14)
 Escopo
 Globais
 Locais
 Modificadores de tipo
 const
 static
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 17/61
25/9/2007 / 17AED / PUC Minas / 2007-2
C++ / Tipos de variáveisC++ / Tipos de variáveis
 Tipos de dados simples: string, int

Tipos de dados estruturados, definidospelo usuário
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 18/61
25/9/2007 / 18AED / PUC Minas / 2007-2
C++ / Passagem de parâmetrosC++ / Passagem de parâmetros
 Por valor
 Dados simples são passados normalmente por valor
 Cria na pilha de parâmetros da função uma cópia da
variável original, que permanecerá inalterada caso
sejam feitas modificações localmente.
 Por ponteiros: modificador ‘*’
 Passa o endereço para o método.
 Por referência: modificador ‘&’
 Cria na pilha de parâmetros da função uma variável
que na verdade aponta para mesmo endereço doparâmetro original.
 Vetores são sempre passadas por referência
 Exemplos: projeto aed.dev
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 19/61
25/9/2007 / 19AED / PUC Minas / 2007-2
C++ / Exemplos de parâmetrosC++ / Exemplos de parâmetros
 // Passagem por valor
 void imprimePontoPorValor( Ponto p1 )
 {

cout << "Por valor"; cout << "X = " << dec << p1.x << " Y = " << dec <<
p1.y << endl;

 p1.x += p1.x;
 p1.y += p1.y;

}
 // Referência altera
 void imprimePontoPorReferencia( Ponto& p1 )
 {
 cout << "Por referência"; cout << "X = " << dec << p1.x << " Y = " << dec <<
p1.y << endl;
 p1.x += p1.x;
 p1.y += p1.y;
 }
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 20/61
25/9/2007 / 20AED / PUC Minas / 2007-2
C++ / Funções e métodos versusC++ / Funções e métodos versus
procedimentosprocedimentos
 Funções retornam valor
 Procedimentos não retornam (void)

Assinatura de um método/procedimento
 Nome do método
 Tipos e nomes dos parâmetros
 Tipo de dado retornado
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 21/61
25/9/2007 / 21AED / PUC Minas / 2007-2
C++ / Alocação de memóriaC++ / Alocação de memória
 Alocação estática
 Variáveis
 Estruturas
 Vetores (arrays) e matrizes
 Alocação dinâmica
 Ponteiros
 Endereço é um valor, logo pode ser guardado na memória
 Apontador = variável cujo valor é um endereço da memória
 Vantagens: otimiza o gerenciamento da memória, podendo tornar uma
implementação mais eficiente
 Desvantagens: difícil de aprender a gerenciar sem erros a memória
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 22/61
25/9/2007 / 22AED / PUC Minas / 2007-2
C++ / Exemplo de alocação
C++ / Exemplo de alocação
#include <cstdio>
int x = 10;
int *ptr = &x;
void mostrar(){
cout << “\nVariavel x:” << x;
cout << “\nEndereco de x: ” << &x;
cout << “\nVariavel ptr: ” << ptr;
cout << “\nConteudo de ptr: ” <<
*ptr;
cout << “\nEndereco de ptr: ” <<
&ptr;
}
void main(){
mostrar();
*ptr = 830;
mostrar();
}
Variavel x:10
Endereco de x: F81A
Variavel ptr: F81A
Conteudo de ptr: 10
Endereco de ptr: F84A
Variavel x:830
Endereco de x: F81A
Variavel ptr: F81A
Conteudo de ptr: 830
Endereco de ptr: F84A
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 23/61
25/9/2007 / 23AED / PUC Minas / 2007-2
C++ / Exemplo de alocação
C++ / Exemplo de alocação
#include<stdio.h>
void main(){
char u, v = ‘S’;
char *pu, *pv = &v;
*pv = v + 1;
u = *pv + 1;
pu = &u;
}
Suponha que cada caractere ocupe 1 byte.Se o valor atribuído a u é armazenado no
endereço F8C e o valor atribuído a v é
armazenado no endereço F8D, então:

Qual o valor representado por &v?
 Qual valor é atribuído a pv?
 Qual valor é representado por *pv?
 Qual valor é atribuído a u?
 Qual valor é representado por &u?
 Qual valor é atribuído a pu?
 Qual valor é representado por *pu?
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 24/61
25/9/2007 / 24AED / PUC Minas / 2007-2
C++ / versus C
C++ / versus C
 Alocação dinâmica de memória
 C: malloc / free / realloc
 Realocação de espaços
 C++: new / delete
 Coleta de lixo automática em C++ (garbage collection)
 Uso de classe vector() da STL (Standard Template Library) para
realocação dinâmica
 Otimização
 Evitar uso de macros, usar const (STROUSTRUP, 1997, p. 14)
 Programação genérica em C++ (STROUSTRUP, 1997, p. 40)
 Métodos virtuais
 STL

String versus char[]
 Sobreposição de métodos
 POO
 Interfaces de classes e encapsulamento
 Construtores e destrutores
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 25/61
25/9/2007 / 25AED / PUC Minas / 2007-2
C++ / Gerenciamento de memória
C++ / Gerenciamento de memória
Sistema
Operacional
Código do
programa
Dados
Variáveis globais e estáticas
Heap Memória gerenciada dinamicamente
↓↓↓↓
↑↑↑↑
Pilha
Variáveis automáticas (funções e procedimentos)
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 26/61
25/9/2007 / 26AED / PUC Minas / 2007-2
POO / POO / structuresstructures com métodos ecom métodos e
acesso a membros da estruturaacesso a membros da estrutura
struct Ponto
{
int x;
int y;
// Funções
void display();
};
Ponto p;
p.x; p.y; p.display;
Ponto *p = new Ponto;
P->x; p->y; p->display.
Acesso a membros de
estruturas estáticas
Acesso a membros de
estruturas dinâmicas
(ponteiros)
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 27/61
25/9/2007 / 27AED / PUC Minas / 2007-2
POO / STL / 
POO / STL / 
strings
strings
 Classe string
 #include <string>
 using std::string;
 Métodos
 empty(), size(), length(), substr(), replace(), erase(), finde
 c_str()

conversão de string para array de caracteres
 Exemplos (projeto aed.dev)
string s = "abc def abc";
string s2 = "abcde uvwxyz";
char c;
char ch[] = "aba daba do";
char *cp = ch;unsigned int i;
 Fonte:
http://www.bgsu.edu/departments/compsci/docs/string.html
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 28/61
25/9/2007 / 28AED / PUC Minas / 2007-2
POO / STL / POO / STL / stringsstrings: exemplo: exemplo
cin >> s; Lê até o separador espaço
getline(cin, s); Lê até o caractere ENTER
cout << s; Envia para saída padrão
s = s2; s = "abc";
s = ch; s = cp;
Um array, literal ou variável podem ser atribuídos diretamente a um
string. ch ou cp têm mesmo efeito.
s[1] = 'c';c = s[1]; Muda s para "acc def abc".Operador subscript retorna um char e não string.
i = s.length();
i = s.size();
Ambos retornam tamanho de s
if(s.empty()) i++;
if(s == "") i++;
Ambos adicionam 1 a i caso s esteja vazio.
If (s < s2) i++; Campara código ASCII dos strings.
s = s + "x";
s += "x";
Exemplos adicionam x ao fim de s
S = s.substr(1,4); Retorna substring ‘bc d’.
s.replace(4,3,"x");
Substitui 3 caracteres de ‘s’, a partir da posição 4, por ‘x’. Retorno "abc
x abc".
s.erase(4,5);
s.erase(4);
Apaga 5 caracteres da string a partir da posição 4.
s = ch; Converte array de caracteres para string
cp = s.c_str();
Ponteiro cp passa a apontar um array de caracteres com o conteúdo
equivalente a s.
i = s.find("ab",4);
if(s.rfind("ab",4)
!= string::npos)
Retorna a posição do substring “ab”, começando a busca na posição 4.
Se não encontrar, retorna unsigned int string::npos.
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 29/61
25/9/2007 / 29AED / PUC Minas / 2007-2
POO / STL / POO / STL / mathmath
 Classe math
#include <cmath>
 Funções
 trigonométricas (cos, sin, tan, aços, asin, atan, atan2);

hiperbólicas (cosh, sinh, tanh);
 exponencial e logarítmicas (exp, frexp, ldexp, log,
log10, modf);
 potencia (pow, sqrt); arredondamento e valor absoluto
(ceil, fabs, floor, fmod)
 Fonte: http://www.cplusplus.com/reference/clibrary/cmath/ 
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 30/61
25/9/2007 / 30AED / PUC Minas / 2007-2
POO / STL / POO / STL / mathmath
 Distância entre dois pontos
 Distância entre dois pontos em C++
 sqrt(pow(x1 – x2, 2) + pow(y1 – y2, 2));

Exemplos: projeto aed-poo.dev
2
21
2
21 )()( y y x x −+−
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 31/61
25/9/2007 / 31AED / PUC Minas / 2007-2
C++ / Qualidade de códigoC++ / Qualidade de código
 Legibilidade (clareza no código)
 Comentários
 Nomes de métodos e variáveis
 Identação
 Controle de fluxo
 Não usar goto (desvio incondicional)

return só no final das funções Usar CONSTANTES e não números mágicos
 Exemplo: programa “aed-qualidadecodigo”
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 32/61
25/9/2007 / 32AED / PUC Minas / 2007-2
C++ / Qualidade de códigoC++ / Qualidade de código
 Acoplamento e coesão
 Divisão em módulos e funções, bem como classes,
com uma única função
 Permite concentrar a atenção em módulos específicos em diferentes
momentos
 Facilita a manutenção do programa
 Facilita a reutilização do programa
 Fatores externos
 Eficiência
 Robustez

EscalabilidadeInterface
 Documentação
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 33/61
25/9/2007 / 33AED / PUC Minas / 2007-2
AgendaAgenda
 Visão geral

Programação em C++ - C++ Programação orientada a objetos - POO
 Estruturas de dados – AED
 Pilhas
 Filas
 Listas
 Listas circulares
 Tabelas
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 34/61
25/9/2007 / 34AED / PUC Minas / 2007-2
POO / PrincípiosPOO / Princípios
 Encapsulamento
 Herança
 Permite definição de uma classe a partir de
outro, facilitando a reutilização de código
 Polimorfismo
 Métodos com mesmo nome mas cuja
assinatura é diferente, sendo qual será usado
de acordo com os tipos de parâmetros e valor
de retorno
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 35/61
25/9/2007 / 35AED / PUC Minas / 2007-2
POO / ElementosPOO / Elementos
 Classes
 modelos para a criação de objetos
 Animais são seres vivos:
 O que podem fazer:
 Nascem, vivem, crescem e morrem
 Podem se movimentar
 Têm pai e mãe
 Quais características têm:
 Idade
 Peso
 Atributos ou propriedades (características)
 características dos objetos
 Métodos (o que podem fazer)
 comportamento (ações) dos objetos da classe
 Objetos
 instâncias de uma classe
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 36/61
25/9/2007 / 36AED / PUC Minas / 2007-2
POO / Implementação em C++POO / Implementação em C++
 Classes
 Interfaces
 Arquivo de cabeçalho contendo nome, propriedades e métodos da
classe, bem como suas assinaturas
 Ex.:
 #include “animal.h”
 Implementação
 Arquivo contendo a implementação dos métodos cuja assinatura é
definida na interface da classe
 Ex.:
 animal.cpp
 Construtores

Inicialização de objetos
 Destrutores
 Liberação de espaço e controles
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 37/61
25/9/2007 / 37AED / PUC Minas / 2007-2
POO / Implementação em C++POO / Implementação em C++
 Visibilidade de métodos e propriedades
 public:
 private:
 protect:

Métodos e propriedades de classe
 static
 Propriedades e métodos da classe
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 38/61
25/9/2007 / 38AED / PUC Minas / 2007-2
POO / Implementação em C++POO / Implementação em C++
 Herança
 Classe filho herda estrutura e comportamento da classe pai

Tipos
 •Herança simples: uma classe pai
 •Herança múltipla: mais de uma classe pai
 Ex.:
 class cachorro:animal { }
 A classe derivada pode acessar os membros public e
protected do pai
 Declaração da nova classe / herança
class <nova classe> : [private|public] <pai>
 private: default
 public: tudo o que é público aos utilizadores da classe pai, será
público para os utilizadores da classe filho, a não ser que seja
sobrecarregado na função filho.
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 39/61
25/9/2007 / 39AED / PUC Minas / 2007-2
POO / Implementação em C++POO / Implementação em C++
 Implementação de métodos de classe
 Métodos virtual
 virtual void movimentaAnimal();
 Apontador “this->” para propriedades do objeto
 this->tamanho++; // usado dentro dos métodos da
classe
 Exemplo: aed-Cubo.dev
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 40/61
25/9/2007 / 40AED / PUC Minas / 2007-2
POO / Estruturas versus classesPOO / Estruturas versus classes
Abstração Variáveis / 
propriedades
Funções / 
métodos
Herança Escopo
 protect 
Estrutura Sim Sim Não Não
Classe Sim Sim Sim Sim
 Interface da classe

Nome da classe
 Propriedades da classe
 Assinatura dos métodos e procedimentos da
classe
 
POO / Interface da classePOO / Interface da classe
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 41/61
25/9/2007 / 41AED / PUC Minas / 2007-2
POO / Interface da classePOO / Interface da classe
(#(#includeinclude “cubo. h”)“cubo. h”)class Cubo
{
private:
int altura, largura, profundidade;
public:
Cubo( int, int, int );
~Cubo();
int volume( void );
};
 
POO / ImplementaçãoPOO / Implementação
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 42/61
25/9/2007 / 42AED / PUC Minas / 2007-2
POO / ImplementaçãoPOO / Implementação
(Cubo.cpp)(Cubo.cpp)#include “cubo.h”
// Função construtora
Cubo::Cubo( int ht, int wd, int dp )
{
altura = ht;
largura = wd;
profundidade = dp;
}
// Função Destruidora
Cubo::~Cubo()
{
// não faz nada
}
int Cubo::volume()
{
return altura * largura * profundidade;
}
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 43/61
25/9/2007 / 43AED / PUC Minas / 2007-2
AgendaAgenda
 Visão geral
 Programação em C++ - C++
 Programação orientada a objetos - POO
 Estruturas de dados – AED
 Pilhas
 Filas
 Listas
 Listas circulares
 Tabelas
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 44/61
25/9/2007 / 44AED / PUC Minas / 2007-2
AED / ListasAED / Listas
 Lista linear
 Definição

“Lista é uma estrutura em que as operações inserir, retirar elocalizar são definidas. [...] Uma lista linear é uma seqüência
de zero ou mais itens x1, x2, ... Xn, na qual xi é de um
determinado tipo e n representa o tamanho da lista linear.”
(ZIVIANI, 2004, p. 63)
 Operações
 Para se implementar uma lista linear é necessário um
conjunto básico de operações
 Lista.FazListaVazia()

Lista.EstaVazia()
 Lista.Insere( x )
 Lista.Retira( p, x )
 Lista.Imprime()
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 45/61
25/9/2007 / 45AED / PUC Minas / 2007-2
AED / Listas e FilasAED / Listas e Filas
 Fila
 Definição
 “Uma fila é uma lista linear em que todas as
inserções são realizadas em um extremo da lista, e
todas as retiradas e, geralmente, os acessos são
realizados no outro extremo da lista” (ZIVIANI,2004, p. 81)
 Comportamento

FIFO – First In First Out = Fila
 “Primeiro a entrar, primeiro a sair” (CORMEM et
al., 2002, p. 163)
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 46/61
25/9/2007 / 46AED / PUC Minas / 2007-2
AED / Listas e PilhasAED / Listas e Pilhas
 Pilha
 Definição
 “Uma pilha é uma lista linear em que todas as
inserções, retiradas e, geralmente, todos os acessos
são feitos em apenas um extremo da lista.”
(ZIVIANO, 2004, p. 72)
 Comportamento
 LIFO – Last In Last Out = Pilha

“Último a entrar, primeiro a sair” (CORMEM etal., 2002, p. 163)
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 47/61
25/9/2007 / 47AED / PUC Minas / 2007-2
AED / FilasAED / Filas
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 48/61
25/9/2007 / 48AED / PUC Minas / 2007-2
AED / Operações simplesAED / Operações simples
 Operações simples (sobre elementos)
 Inserir
 Excluir
 Proximo

Anterior
 Minimo
 Máximo
 
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 49/61
25/9/2007 / 49AED / PUC Minas / 2007-2
AED / Operações sobre a listaAED / Operações sobre a lista
 Procurar elemento
 Inverter
 Vetor
 Lista encadeada

Lista duplamente encadeada
 Ordenar (método da bolha)
 Vetor
 Matriz
 Lista encadeada / lista duplamente encadeada
 
AED / Pilh
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 50/61
25/9/2007 / 50AED / PUC Minas / 2007-2AED / PilhaAED / Pilha
 Implementação com vetor estático
 Implementação com vetor dinâmico
 Implementação com STL “vector”
 Implementação com alocação dinâmica de
células / lista encadeada linear
 
A / ilh / ClAED / Pilh / Cl (S )(STL)
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 51/61
25/9/2007 / 51AED / PUC Minas / 2007-2
AED / Pilha / ClasseAED / Pilha / Classe vectorvector (STL)(STL)
 Classe “vector” da Standard Template
Library
 #include <vector>
 Declaração
 vector<int> vec_one;

Desempilhavoid pop(vector<int>& v)
{
v.erase( v.end()-1, v.end() ) ;
}
 Empilha
 vec_one.push_back(9);
 
AED / Lista duplamenteAED / Lista duplamente
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 52/61
25/9/2007 / 52AED / PUC Minas / 2007-2
AED / Lista duplamentep
encadeada (ou lista ligada)encadeada (ou lista ligada)
 Fonte: (CORMEM et al., 2002, p. 166)
 
AED / Li d d hAED / Li t d d h
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 53/61
25/9/2007 / 53AED / PUC Minas / 2007-2
AED / Lista encadeada.hAED / Lista encadeada.h
// Tipo de dados de cada elemento individual da Pilha
class ElementoLista
{
public:
int codigo;
ElementoLista* proximo;
ElementoLista* anterior;
}; //class ElementoLista
 
AED / Li t d d hAED / Li t d d h
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 54/61
25/9/2007 / 54AED / PUC Minas / 2007-2
AED / Lista encadeada.hAED / Lista encadeada.h
/*
* No description
*/
class ListaEncadeada
{
private:
int tamanho;ElementoLista* primeiro;
ElementoLista* ultimo;
public:
// class constructor
ListaEncadeada();
// class destructor
~ListaEncadeada();
int insereElemento( int codigo );
int obtemTamanho( int &tam );
int excluiElemento( int codigo );
ElementoLista* encontraElemento( int codigo );
// Métodos de entrada e saída
void ListaEncadeada::imprimeTamanho();
void ListaEncadeada::imprimeElementos();
void ListaEncadeada::imprimeMenu();
};
 
AED / Li t i lAED / Li t i l
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 55/61
25/9/2007 / 55AED / PUC Minas / 2007-2
AED / Lista circularAED / Lista circular
 Sentinelas (CORMEM et al., 2002, p. 163)
 Lista circular implementada com lista
encadeada
 
AED / Li t i l tAED / Lista circular com etor
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 56/61
25/9/2007 / 56AED / PUC Minas / 2007-2
AED / Lista circular com vetorAED / Lista circular com vetor
 (ZIVIANI, 2004, p. 82)
 
Res moResumo
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 57/61
25/9/2007 / 57AED / PUC Minas / 2007-2
ResumoResumo
 O entendimento da linguagem (C++) e dos
princípios da orientação a objetos, bem
como das estruturas de dados básicas, é
fundamental para a modelagem de
problemas computacionais mais
complexos.
 
GlossárioGlossário
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 58/61
25/9/2007 / 58AED / PUC Minas / 2007-2
GlossárioGlossário
 Variáveis
 Escopo
 Passagem de parâmetros
 Funções, procedimentos e métodos
 TAD - tipo abstrato de dados
 AED - algoritmo e estrutura de dados
 Programa +
 TADs
 POO - programação orientada a objetos
 STL – Standard Template Library
 
GlossárioGlossário
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 59/61
25/9/2007 / 59AED / PUC Minas / 2007-2
GlossárioGlossário
 OO: Orientada a Objeto
 
ReferênciasReferências
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 60/61
25/9/2007 / 60AED / PUC Minas / 2007-2
ReferênciasReferências
 CORMEM; LEISERSON; RIVEST;
STEIN. Algoritmos: teoria e prática.
Campus, 2002.
 STROUSTRUP, Bjarne. C++
Programming Language. 3ed. Addison-
Wesley, 1997.
 KERNIGHAN, Brian W.; RITCHIE,
Dennis M. The C Programming Language.
PrenticeHall.Englewood Cliffs, New
Jersey. 1978.
 
Onde obter mais informaçõesOnde obter mais informações
5/8/2018 Apostila-de-C++ - slidepdf.com
http://slidepdf.com/reader/full/apostila-de-c-559bf457d3ee1 61/61
25/9/2007 / 61AED / PUC Minas / 2007-2
Onde obter mais informaçõesOnde obter mais informações
 Email
 rfmatheus@yahoo.com.br
 Homepage
 http://rfmatheus.com.br/content/blogcategory/16/28/ 
 LearnLoop
 http://ww.inf.pucminas.br/learnloop