2014912_121813_Semana7-2-RevisaoGeralAV1

Prévia do material em texto

Estrutura de Estrutura de 
Dados IDados IDados IDados I
Prof. Alex Salgado
Curso: Sistemas de Informação
9/12/2014 1
AgendaAgenda
• Exercícios de revisão
-Recursividade
- TAD
- Algoritmos de Busca
- Algoritmos de Ordenação- Algoritmos de Ordenação
- Notação Big O
2
AvisosAvisos
• Datas importantes:
o Prova AV1 – 18/09/2014
o Entrega do trabalho 1 – 22/09/2014 (7:00h) – Instruções no 
portal
3
RecursividadeRecursividade
• As funções podem ser chamadas 
recursivamente, isto é, dentro do 
corpo de uma função podemos 
chamar novamente a própria 
função. 
• Diversas implementações ficam 
muito mais fáceis usando muito mais fáceis usando 
recursividade. Por outro lado, 
implementações não recursivas 
tendem a ser mais eficientes.
4
RecursividadeRecursividade
Condição de PARADA
Padrão de execução normal
Importante
identificar {
0, Se m <= 0 
sigma{
9/12/2014Footer Text 5
(m + sigma ( m – 1), se m>0
sigma{
11--ExercícioExercício
Sabendo que a sequencia de Fibonacci é uma sequência de números 
inteiros, começando normalmente por 1, na qual, cada termo 
subsequente (número de Fibonacci) corresponde a soma dos dois 
anteriores, na forma:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …
2.1- Crie uma função recursiva int 
6
2.1- Crie uma função recursiva int 
fibo(int n) que retorne o número de 
Fibonacci do termo n.
2.2- Crie um programa para 
imprimir a sequencia de Fibonnaci 
até o termo n (entrada por teclado).
11--Exercício RespostaExercício Resposta
9/12/2014 7
22--ExercícioExercício
Escreva uma função recursiva para calcular o valor de uma base x 
elevada a um expoente y.
Protótipo:
int expo (int x, int y) 
2.2- Crie um programa principal para utilizar sua função e exibir 
o resultado.
8
o resultado.
22--Exercício RespostaExercício Resposta
#include <stdio.h> 
int expo (int x, int y) 
{ 
if (y == 0) 
return 1; 
if (y == 1) 
return x; 
return x*expo(x,y-1); 
} 
int main(void) { 
int x=2, y=4, e; 
e=expo(x,y); 
printf("\n\nX elevado a y eh: %d", e); 
getcch();
}
9
Tipo Abstrato de DadosTipo Abstrato de Dados
• Tipo Abstrato de Dado (TAD) é uma 
especificação de um conjunto de dados
e operações que podem ser executadas 
sobre esses dados. Além disso, é uma 
metodologia de programação que tem 
como proposta reduzir a informação 
10
como proposta reduzir a informação 
necessária para a criação/programação 
de um algoritmo através da 
abstração das variáveis envolvidas em 
uma única entidade fechada, com 
operações próprias à sua natureza.
Tipo Abstrato de DadosTipo Abstrato de Dados
• Definição
o Conjunto de valores (domínio)
o Possíveis operações
o Ex.: Biblioteca gráfica
• Tipo: Ponto (coordenadas x,y de int);
• Operações: desenhaCirculo, desenhaQuadrado, 
etc.
11
• Tipo:int
• Operações: +,-,>,<
o Ajuda modelar/organizar o pensamento lógico 
de forma a resolver problemas computacionais 
complexos. Além de promover o reuso e 
otimização do custo computacional.
Alocação Dinâmica Alocação Dinâmica vsvs EstáticaEstática
9/12/2014Footer Text 12
33--ExercícioExercício
• Crie um tipo de dados ContaBancaria, com os campos:
o numero(int)
o saldo(float)
• As operações possíveis para este TAD são:
o Iniciar uma conta com um número e saldo inicial;
o Depositar um valor;
o Sacar um valor;
o Imprimir o saldo
• Crie um pequeno programa para testar o seu TAD.
• (Utilize alocação dinâmica)
13
33--ExercícioExercício
• Dica : Protótipo das funções:
TContaBancaria *criaConta( int num, float saldo);
void depositar(TContaBancaria *conta, float valor);
void sacar(TContaBancaria *conta, float valor);
void imprimir( TContaBancaria *conta);
14
33--ExercícioExercício--RespostaResposta
#include <stdlib.h> /* malloc, free*/
#include <stdio.h> /* printf */
typedef struct{
int numero;
float saldo;
}TContaBancaria;
TContaBancaria *criaConta( int num, float saldo);
void depositar(TContaBancaria *conta, float valor);
void sacar(TContaBancaria *conta, float valor);
void imprimir( TContaBancaria *conta);
int main()
{
15
{
TContaBancaria *conta;
conta = criaConta(1, 10.0);
imprimir( conta );
depositar(conta, 20.0);
imprimir( conta );
sacar(conta, 10.0);
imprimir( conta );
free(conta);
return 0;
}
33--ExercícioExercício--RespostaResposta
TContaBancaria* criaConta( int num, float psaldo)
{
TContaBancaria *conta;
conta = (TContaBancaria*)malloc(sizeof(TContaBancaria));
if (conta == NULL) {
printf("Memoria insuficiente");
exit(1);
}
conta->numero = num;
conta->saldo = psaldo;
return conta;
}
void depositar(TContaBancaria *conta, float valor)
16
void depositar(TContaBancaria *conta, float valor)
{
conta->saldo = conta->saldo + valor;
}
void sacar(TContaBancaria *conta, float valor){
conta->saldo = conta->saldo - valor;
}
void imprimir( TContaBancaria *conta)
{
printf("Conta: %d\n", conta->numero);
printf("Saldo: %f\n", conta->saldo);
}
44--ExercícioExercício
• Crie um tipo de dados que represente um triangulo 
contento os inteiros: lado1, lado2, lado3;
• Criar uma função que crie e retorne uma instância de 
TTriangulo(alocação dinâmica).
• Crie uma função que receba uma instância do triangulo 
e retorne a categoria do mesmo: isósceles, equilátero, e retorne a categoria do mesmo: isósceles, equilátero, 
escaleno;
• Crie um programa principal que crie uma instância de 
um triangulo, leia as informações do teclado e imprima 
sua classificação utilizando as funções anteriores.
• O programa só termina após a pergunta: 
deseja continuar(s/n)?
17
55--ExercícioExercício
• Crie uma biblioteca em c (busca_ordena.h) com as seguintes 
funções.
int buscaLinear(int tam, int *vet, int elem);
int buscaBinaria(int tam, int *vet, int elem);
void bubbleSort(int tam, int *vet);void bubbleSort(int tam, int *vet);
void selectionSort (int tam, int *vet);
void insertionSort (int tam, int *vet);
void mergeSort( int tam, int *vet);
18
66--ExercícioExercício
Complemente o programa da aula anterior, incorporando 
os novos algoritmos de ordenação;
****************************************
Entre com um vetor de 5 elementos
****************************************
Elemento 1: 
Elemento 2: 
Elemento 3: 
Elemento 4: 
Elemento 5: 
**********************************
19
66--ExercícioExercício
Vetor = 10 20 50 60 1
****************************************
Entre com o elemento de busca: 10
Escolha o método de busca
****************************************
1– busca linear
2- busca binaria (bubble sort)2- busca binaria (bubble sort)
3- busca binaria (selection sort)
4- busca binaria (insertion sort)
5- busca binaria (merge sort)
**********************************
Parabéns!! elemento entrado na posição 0
ou (Elemento não existe no vetor)
Continuar(s/n) ?
20
Busca LinearBusca Linear
9/12/2014 21
Busca BináriaBusca Binária
9/12/2014 22
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Algoritmos de Ordenação Algoritmos de Ordenação ––
SelectionSelection SortSort
24
Algoritmos de Ordenação Algoritmos de Ordenação ––
InsertionInsertion SortSort
25
Algoritmos de Ordenação Algoritmos de Ordenação –– Merge Merge SortSort (1)(1)
// Funcao para combinar vetores L(Esq) e R(Dir) e criando o A 
// tamEsq = numero de elementos de Esq
// tamDir = numero de elementos de Esq 
void Merge(int *A,int *Esq,int tamEsq,int *Dir,int tamDir) {
9/12/2014 26
void Merge(int *A,int *Esq,int tamEsq,int *Dir,int tamDir) {
int i,j,k;
// i - para contar o indice do sub-array esquerdo
// j - para contar o indice do sub-array direito
// k - para contar o indice do array resultantei = 0; j = 0; k =0;
while(i<tamEsq && j< tamDir) {
if(Esq[i] < Dir[j]) A[k++] = Esq[i++];
else A[k++] = Dir[j++];
}
while(i < tamEsq) A[k++] = Esq[i++];
while(j < tamDir) A[k++] = Dir[j++];
}
Algoritmos de Ordenação Algoritmos de Ordenação –– Merge Merge SortSort(2)(2)
// Funcao recursiva para ordenar um array de inteiros. 
void MergeSort(int *A,int n) {
9/12/2014 27
void MergeSort(int *A,int n) {
int meio,i, *Esq, *Dir;
if(n < 2) return; // condicao base
meio = n/2; // procura o indice do meio 
// cria os vetores Esquerdo e Direito
Esq = (int*)malloc(meio*sizeof(int)); 
Dir = (int*)malloc((n- meio)*sizeof(int)); 
for(i = 0;i<meio;i++) Esq[i] = A[i]; 
for(i = meio;i<n;i++) Dir[i-meio] = A[i]; 
MergeSort(Esq,meio); 
MergeSort(Dir,n-meio;
Merge(A,Esq,meio,Dir,n-meio);
}
Resumo da teoria dos Resumo da teoria dos 
algoritmos de ordenaçãoalgoritmos de ordenaçãoalgoritmos de ordenaçãoalgoritmos de ordenação
9/12/2014Footer Text 28
Algoritmos de Ordenação Algoritmos de Ordenação –– BubbleBubble SortSort
Bubblesort – método de bolha
O bubble sort, ou ordenação por 
flutuação (literalmente "por 
bolha"), é um algoritmo de 
ordenação dos mais simples. A 
idéia é percorrer o vetor diversas 
vezes, a cada passagem 
fazendo flutuar para o topo o 
maior elemento da sequência. 
29
maior elemento da sequência. 
Essa movimentação lembra a 
forma como as bolhas em 
um tanque de água procuram 
seu próprio nível, e disso vem o 
nome do algoritmo.
Algoritmos de Ordenação Algoritmos de Ordenação ––
SelectionSelection SortSort
• Definição
• Analogamente as cartas de baralho, espalhe as 
cartas sobre a mesa, selecione a carta de menor 
valor, retire-a do baralho e segure-a na sua mão. 
30
• Esse processo continua até que todas as cartas 
estejam em sua mão. As cartas em sua mão 
estarão ordenadas quando o processo terminar.
Algoritmos de Ordenação Algoritmos de Ordenação –– SelectionSelection SortSort
Sequência:
5 - 3 - 1 - 4 - 2
Verifica quem é o menor e troca com a primeira posição.
1 - 3 - 5 - 4 - 2
Verifica o mesmo só que a partir da segunda posição:
31
Verifica o mesmo só que a partir da segunda posição:
1 - 2 - 5 - 4 - 3
e assim sucessivamente até que não exista mais menores após 
determinada posição:
1 - 2 - 3 - 4 - 5
Algoritmos de Ordenação Algoritmos de Ordenação –– Merge Merge SortSort
Definição
Omerge sort, ou ordenação por mistura, é um exemplo 
de algoritmo de ordenação do tipo dividir-para-
conquistar.
32
Sua ideia básica consiste em Dividir (o problema em 
vários sub-problemas e resolver esses sub-problemas 
através da recursividade) e Conquistar (após todos os 
sub-problemas terem sido resolvidos ocorre a conquista 
que é a união das resoluções dos sub-problemas).
Algoritmos de Ordenação Algoritmos de Ordenação ––
InsertionInsertion SortSort
• Definição
• Analogamente as cartas de baralho, segure todas 
as cartas em sua mão. Ponha uma carta por vez na 
mesa, sempre inserindo-a na posição correta. O 
baralho estará ordenado sobre a mesa quando 
33
baralho estará ordenado sobre a mesa quando 
não houver mais cartas em sua mão.
Algoritmos de Ordenação Algoritmos de Ordenação –– InsertionInsertion SortSort
34
Big Oh Big Oh NotationNotation
O
Busca linear n
Busca binária log n
Vamos resumir os tempos de execução dos algoritmos que discutimos até agora, 
medida usando uma tabela. Na chamada notação O (Big Oh), O representa o pior 
caso de funcionamento tempo e Ω representa o melhor caso a ocorrer do tempo. 
Ex.: Na melhor das hipóteses para a busca linear e binária, o número que você 
está procurando é o primeiro.
35
Busca binária log n
bubble sort n2
selection sort n2
insertion sort n2
Merge sort n log n