Algoritmos Avançados
125 pág.

Algoritmos Avançados


DisciplinaAlgoritimos C++257 materiais1.379 seguidores
Pré-visualização7 páginas
Algoritmos Avançados 
Prof. José Luiz Rosa \u2013 jose.anjos@estacio.br 
Ementa 
 
 
 Análise de Algoritmo 
 
 Recursividade 
 
 Algoritmos de Ordenação 
 
 Estruturas de dados dos tipos Árvore 
 
 Algoritmos em Grafos 
Bibliografia Básica 
 
ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos de. 
Estruturas de Dados: algoritmos, análise da complexidade e 
implementações em JAVA, C/C++. São Paulo: Pearson Prentice Hall, 
2010. 
 
CORMEN, T. Desmistificando algoritmos. Rio de Janeiro: Elsevier, 
2014. 
 
Koffman, Elliot B.; Wolfgang, Paul A. T. Abstração, Estrutura de 
Dados e Projeto Usando C++. Rio de Janeiro: LTC, 2008. 
Bibliografia Complementar 
 
CELES, Waldemar; CERQUEIRA,Renato;RANGEL,José 
Lucas. Introdução a Estrutura de Dados com técnicas de 
programação em C. Rio de Janeiro : Elsevier, 2004. 
 
DROZDEK, Adam. Estrutura de dados e Algoritmos em C++. São 
Paulo: Pioneira Thomson Learning, 2005. 
 
EDELWEISS, N, GALANTE, R. M., Estrutura de Dados, Volume 18 - 
Série Livros Didáticos Informática UFRGS.1.ed.RS: Bookman, 2009. 
FORBELLONE, André Luiz Villar; EBERSPACHER, Henri 
Frederico. Lógica de Programação: A construção de Algoritmos e 
Estrutura de Dados. 3. ed. São Paulo: Makron Books, 2005. 
 
JEFF, E. Como pensar em algoritmo. Rio de Janeiro: LTC, 2010. 
 
KOFFMAN, Elliot B., WOLFGANG, Paul A.T., Objetos, Abstração, 
Estrutura de dados e Projeto usando C++, 1. ed. Rio de Janeiro: 
LTC,2008. 
 
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de 
dados e seus algoritmos. 3. ed. Rio de Janeiro, RJ: LTC, 2010. viii, 
302 p. ISBN 978-85-216-1750-1. 
Análise de Algoritmo 
 
- Revisão de C++ 
 
 . Array 
 . Registro (struct) 
 . Ponteiro 
 . Função. 
 
- Complexidade (notação O) 
Revisão de C++ 
 
Tipos 
 
 . int (inteiro): 10 
 . float (ponto flutuante de precisão simples): 10.0 
 . double (ponto flutuante de precisão dupla): 10.0 
 . char (caractere): 'A' 
 . bool (lógico): true/false 
 . void (especifica que uma função não retorna valor) 
Enumeração (contém um conjunto de valores especificados pelo 
usuário): 
 
enum binario {zero, um}; 
int valor; 
 
cout << &quot;Numero: &quot;; 
cin >> valor; 
if (valor == zero) 
 cout << &quot;Zero&quot; << endl; 
else 
 if (valor == um) 
 cout << &quot;Um&quot; << endl; 
 else 
 cout << &quot;Valor fora de limite!&quot; << endl; 
Outro exemplo: 
 
enum graus {c = 100, f = 212}; 
int temperatura; 
 
cout << &quot;Temperatura em que a água pura ferve: &quot;; 
cin >> temperatura; 
cout << &quot;A água ferve a &quot; << temperatura; 
if (temperatura == c) 
 cout << &quot; graus Celsius.&quot; << endl; 
else 
 cout << &quot; graus Fahrenheit.&quot; << endl; 
Typedef (declara um nome para um tipo): 
 
 
typedef float pontoFlutuantePrecisaoSimples; 
typedef double pontoFlutuantePrecisaoDupla; 
 
pontoFlutuantePrecisaoSimples f; 
pontoFlutuantePrecisaoDupla d; 
 
cout << &quot;Tamanho do tipo float : &quot; << sizeof (f) << endl; 
cout << &quot;Tamanho do tipo double: &quot; << sizeof (d) << endl; 
Constante (não permite a redefinição de um objeto após ser 
iniciado): 
 
const int limite = 100; 
 
A tentativa de redefinir \u201climite\u201d, gera erro de compilação: 
 
limite = 50; 
[Error] assignment of read-only variable 'limite' 
 
Definir \u201climite\u201d sem iniciá-la, gera erro de compilação: 
 
const int limite 
[Error] uninitialized const 'limit' 
Array 
 
Um array é um agregado de elementos de mesmo tipo. Declara-se 
um array em C++ como: 
 
tipo nome_array [quantidade_elementos] 
 
Por exemplo, a declaração: int v[3]; define um array de elementos 
\u201cint\u201d, de nome \u201cv\u201d e tamanho \u201c3\u201d (possui 3 elementos). 
Os elementos são indexados, sendo que o primeiro elemento 
está na posição 0 (zero), e o último, na posição \u201ctam \u2013 1\u201d. 
 
int v[3]; 
 
v[0] = 1; 
v[1] = 10; 
v[2] = 100; 
Um array pode ter mais de uma dimensão (multidimensional): 
 
double localizacao [10][15]; 
 
Sendo válida a atribuição: 
 
localizacao [7][12] = 3.45 
 
Um array pode ser iniciado por uma lista de valores: 
 
char vogal [ ] = { 'a' , 'e' , 'i' , 'o' , 'u' } ; 
 
Fazer: cout << &quot;Segunda vogal: &quot; << vogal [1]; resulta em: 
Segunda vogal: e 
Estrutura (struct) 
 
Uma struct é um agregado de elementos que podem ser de tipos 
diferentes. 
 
struct letra 
{ 
 char simbolo; 
 int ascii; 
}; 
 
 
Observe o ponto-e-vírgula após a chave de fechamento. 
O acesso aos membros da struct se faz por meio do operador 
ponto ( . ): 
 
struct letra letra_A; 
 
letra_A.simbolo = 'A'; 
letra_A.ascii = 65; 
 
Pode-se definir um array de struct: 
 
struct letra vogais[5]; 
 
vogais[0].simbolo = 'A'; 
vogais[0].ascii = 65; 
Para evitar ter de escrever \u201cstruct letra\u201d, pode-se utilizar typedef: 
 
typedef struct letra str_letra; 
 
struct letra 
{ 
 char simbolo; 
 int ascii; 
} ; 
 
str_letra letra_A; 
 
Ponteiro 
 
Uma variável do tipo ponteiro armazena um endereço de memória. 
Declara-se uma variável ponteiro, colocando-se um asterisco 
entre o tipo e o nome da variável: 
 
int *p; 
 
Uma forma de iniciar a variável \u201cp\u201d, é atribuir à mesma o endereço 
de outra variável por meio do operador de endereço &: 
 
int a; 
p = &a 
Não se pode atribuir um valor inteiro à variável \u201cp\u201d, pois a mesma 
não é do tipo \u201cint\u201d, e sim, um ponteiro para \u201cint\u201d (armazena o 
endereço inicial de memória onde está armazenado um valor do 
tipo int. Por exemplo, fazer: 
 
p = 10; 
 
gera a seguinte mensagem de erro na compilação: 
 
[Error] invalid conversion from 'int' to 'int*' 
 
A operação básica sobre um ponteiro é a derreferência (também 
chamada de indireção), pela qual faz-se referência ao objeto 
apontado pelo ponteiro. 
Esta operação utiliza o operador de derreferência *. Por exemplo: 
 
*p = 10; 
Fazer *p = 10; faz com que o endereço apontado por p (variável a) 
receba o valor 10 (lembre que \u201ca\u201d é uma variável inteira, e que 
\u201cp\u201d contém o endereço desta variável). 
 
int a , *p; 
p = &a 
 
*p = 10; 
 
cout << &quot;*p = &quot; << *p << endl; 
cout << &quot;a = &quot; << a << endl; 
 
Exibirá o valor 10, pois ambas as instruções exibem o conteúdo 
da mesma posição de memória. 
Porém, executar: 
 
cout << &quot;p = &quot; << p << endl; 
 
Produz como resultado: 
 
p = 0x6ffdec 
 
 
Observando que o endereço é mostrado em hexadecimal, e pode 
variar de sistema para sistema no qual o código seja executado. 
Ponteiros e arrays são intimamente relacionados. O nome de um 
array é um ponteiro para seu elemento inicial. Seja: 
 
int *p; 
int v[ ] = {1,2}; 
 
Fazer: 
 
p = v; 
 
é o mesmo que fazer: 
 
p = &v[0]; 
Aplicar um dos operadores aritméticos: + , - , ++ ou -- a ponteiros, 
faz com que o ponteiro aponte para uma posição de memória 
posterior ou anterior tantas posições quantas forem o tamnho do 
tipo definido para o ponteiro. Em uma plataforma na qual o valor 
do tipo int ocupe 4 bytes de memória, executar: 
 
int a; 
cout << &quot;Tamanho do tipo int: &quot; << sizeof (a) << endl; 
 
Faz com que seja exibido: 
 
Tamanho do tipo int: 4 
 
Então, as execuções abaixo produzem: 
 
int a, *p; 
p = &a ; 
 
cout << &quot;p = &quot; << p << endl; // exibe: p = 0x6ffdec 
p++; 
cout << &quot;p = &quot; << p << endl; // exibe: p = 0x6ffdf0 
p = p + 3; 
cout << &quot;p = &quot; << p << endl; // exibe: p = 0x6ffdfc 
p--; 
cout << &quot;p = &quot; << p << endl;