revisaoav1

Prévia do material em texto

ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Conteúdo Programático desta aula
Revisão dos principais conteúdos das aulas de 1 até 5;
Teste de mesa para o método de pesquisa binária;
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Direto ao Assunto
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Aula 1
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Quando declaramos uma variável com um determinado tipo, sabemos que estamos “fechando” o conjunto de operações que poderemos efetuar com os dados armazenados, quanto de memória será necessário para armazenar o dado e a forma como o dado será armazenado.
Exemplos:
O tipo inteiro só poderá usar números do conjunto dos inteiros(Z).
O tipo real só poderá usar números do conjunto dos reais(R).
Tipos de Dados
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Para que possamos implementar uma TAD, precisamos escolher uma Estrutura de Dados e, para que isso seja feito da forma mais adequada, precisamos conhecer as características de cada estrutura.
Logo, são as Estruturas de Dados que definem como os dados serão organizados e acessados.
“Estruturas de Dados são construções de uma linguagem de programação que agregam um ou mais elementos de dados para formar um tipo de dado que armazena uma quantidade maior de informações”.(OLIVEIRA, R., TAVEIRA, G., BOTTINI, J., 2003, p.11)
Estrutura de Dados
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Se nós conseguirmos dissociar o que o computador pode fazer com os dados do que o que nós queremos fazer com eles, temos o conceito de TAD.
Segundo MORAES, C.R., “Um tipo de dado abstrato pode ser definido como um conjunto de valores e uma coleção de operações que atuam sobre esses valores.
As operações devem ser consistentes com os tipos de valores”.
Tipo Abstrato de Dado (TAD)
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 Listas
 Pilhas
 Filas 
 Filas Circulares
 Listas simplesmente Encadeadas 
 Listas duplamente Encadeadas
Tipos de Estruturas de Dados Lineares
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 Árvore
 Grafo 
Tipos de Estruturas de Dados Não Lineares
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Aula 2
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
“Função é um conjunto de comandos que executam uma determinada tarefa.”(SAADE, Joell, 2003, 99)
Conceito de Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
“Função é um conjunto de comandos que executam uma determinada tarefa.”(SAADE, Joell, 2003, 99)
Conceito de Função
Conhecendo a Nomenclatura
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
<tipo de função>nomeDaFunção(declaração dos parâmetros)
{
 <declaração das variáveis locais>
 
 comandos que formam o corpo da função
 return <valor>; // ou return; ou nada
}
Definição de Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Cabeçalho da Função
<tipo de função>nomeDaFunção(declaração dos parâmetros)
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Cabeçalho da Função
<tipo de função>nomeDaFunção(declaração dos parâmetros)
<tipo de função>nomeDaFunção(declaração dos parâmetros);
Protótipo da Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
void
int
float
double
char
struct
bool
...
TIPOS
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Para onde vai o Fluxo do Programa após o Término da Função?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Para a instrução seguinte - void
Para onde vai o Fluxo do Programa após o Término da Função?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Para a instrução seguinte - void
Para o lugar de onde foi chamada - com retorno
Para onde vai o Fluxo do Programa após o Término da Função?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Exemplos de Protótipos
bool primo(int num);
float maior2(float a, float b);
float somaPA(int a1, int an, int n);
long long int fatorial(long long int num);
float desconto(float valor, float percentual);
void linha(char c, int tam);
void comibinacao(int n, int p);
float volume(float, float, float);
void insere(dados vet[], int &t, int tam);
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
PASSAGEM POR VALOR
Na passagem por valor, uma cópia do conteúdo da variável da função chamadora é passada para a função chamada e, dessa forma, o valor NÃO poderá ser alterado. 
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
PASSAGEM POR REFERÊNCIA
Na passagem por referência,&, o endereço da variável da função chamadora é passado para a função chamada e, dessa forma, o valor poderá ser alterado, ou não. 
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
void reajustaSalario(float &s)
{ s *= 1.08; } 
Passando o endereço de uma variável
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Passando o endereço de uma variável
void reajustaSalario(float &s)
{ s *= 1.08; } 
Passando vetor como parâmetro 
O nome de um vetor é seu endereço. 
Sendo assim, o operador & é dispensável(exemplos 3 e 4) 
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
parâmetros
float desconto(float valor, float percentual)
{ return valor - valor * percentual/100;}
Exemplo 1
Essa função recebe dois valores reais e retorna o resultado da operação que é o valor com desconto..
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
parâmetros
void reajusta(float &sal, float premio)
{sal+= premio;}
Exemplo 2
Essa função recebe dois valores, sendo um, o endereço de uma variável.
Ela não retorna nada, mas altera o valor da variável sal.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
parâmetros
float mediaSalarial(float sal[], int tam)
{
 float soma=0;
 for(int x=0; x<tam; x++)
 soma += sal[x]; 
 return soma/tam;
}
Exemplo 3
Esta função recebe dois valores, sendo um, o endereço de um vetor. 
Ela soma todos os salários e retorna a média salarial.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
#include <iostream>
#include <cstdlib>
#include <cctype>
using namespace std;
int contaDigitos(char p[]);
int main () 
{
 char p1[50];
 cout<<"\nDigite letras,algarismos,etc: "; 
 cin.getline(p1, 50);
 cout<<"\nAlgarismos: "<<contaDigitos(p1) <<"\n\n";
 system("pause");
}
Exemplo 4
int contaDigitos(char p[]);
contaDigitos(p1)
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Exemplo 4
Esta função recebe o endereço de um vetor de char e verifica todos os caracteres enquanto não encontrar o terminador nulo, retornando a quantidade de algarismos do vetor.
int contaDigitos(char p[])
{
 int x, contD=0;
 for( x=0; p[x] !='\0'; x++)
 if(isdigit(p[x]))contD++;
 return contD;
} 
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Exemplo 4
Substitua isdigit(c) por isalpha(c).
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ANTES da main()
FUNÇÃO
main()
Localização da Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
DEPOIS da main()
FUNÇÃO
main()
Localização da Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ANTES da main()
FUNÇÃO
main()
DEPOIS da main()
FUNÇÃO
main()
Tem que ter protótipo antes da main()
Localização da Função
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Aula 3
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Uma estrutura é formada por um ou mais elementos que são agrupados por uma lógica e associados a um nome.
Ao se definir uma struct, um novo tipo de dado é criado.
Conceito de struct
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
DEFININDO a struct
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Quais são esses elementos?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Variáveis simples, matrizes, outras estruturas e até funções.
Quais são esses elementos?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Variáveis simples, matrizes, outras estruturas e até funções.
Quais são esses elementos?
Os elementos podem ser de tipos diferentes?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Variáveis simples, matrizes, outras estruturas e até funções.
Quais são esses elementos?
Os elementos podem ser de tipos diferentes?
Sim. Essa é a grande vantagem da struct.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Variáveis simples, matrizes, outras estruturas e até funções.
Quais são esses elementos?
Oselementos podem ser de tipos diferentes?
Sim. Essa é a grande vantagem da struct.
Como é chamado um elemento?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Variáveis simples, matrizes, outras estruturas e até funções.
Quais são esses elementos?
Os elementos podem ser de tipos diferentes?
Sim. Essa é a grande vantagem da struct.
Cada elemento da estrutura é chamado de membro ou campo.
Como é chamado um elemento?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Qual a diferença entre uma estrutura global e uma estrutura local?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Qual a diferença entre uma estrutura global e uma estrutura local?
A estrutura global é definida antes de todas as funções enquanto que a local é definida dentro de uma função.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Qual a diferença entre uma estrutura global e uma estrutura local?
A estrutura global é definida antes de todas as funções enquanto que a local é definida dentro de uma função.
Onde se declara uma variável do tipo definido por uma estrutura?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Depois da definição ou junto com a definição.
Qual a diferença entre uma estrutura global e uma estrutura local?
A estrutura global é definida antes de todas as funções enquanto que a local é definida dentro de uma função.
Onde se declara uma variável do tipo definido por uma estrutura?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof[200];
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
} professor prof[200];
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof[200];
struct professor
{
 char nomeProf[31];
 float salario;
} professor prof[200];
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como se acessa um membro de uma estrutura?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como se acessa um membro de uma estrutura?
Coloca-se o nome da variável estrutura, seguida do ponto e do nome do membro.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como se acessa um membro de uma estrutura?
Coloca-se o nome da variável estrutura, seguida do ponto e do nome do membro.
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof[200];
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como se acessa um membro de uma estrutura?
Coloca-se o nome da variável estrutura, seguida do ponto e do nome do membro.
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof[200];
...prof[0].nomeProf ...
...prof[0].salario ...
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como se atribui valores aos membros?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
No momento da declaração como fazemos com variáveis simples.
Usando o comando de atribuição e um par de chaves se tiver mais de um membro.
 Através do comando de entrada via teclado, por enquanto.
Como se atribui valores aos membros?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
};
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof={“Joao Maciel”, 7450.00};
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
} prof={“Bia Siel”, 5400.00};
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
} prof;
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
} prof;
cin.getline(prof.nomeProf, 31);
cin>>prof.salario;
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct professor
{
 char nomeProf[31];
 float salario;
};
professor prof={“Joao Maciel”, 7450.00};
struct professor
{
 char nomeProf[31];
 float salario;
} prof={“Bia Siel”, 5400.00};
struct professor
{
 char nomeProf[31];
 float salario;
} prof;
cin.getline(prof.nomeProf, 31);
cin>>prof.salario;
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Como chamamos uma struct que não tem identificador?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Anônima
Como chamamos uma struct que não tem identificador?
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct
{
 int dia, mes, ano;
};
data
Definindo a struct, usando estruturas ANINHADAS
struct saude
{
 float peso, altura, IMC;
 niver;
} atleta;
data
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
struct
{
 int dia, mes, ano;
};
data
Definindo a struct, usando estruturas ANINHADAS
ACESSANDO
...atleta.niver.dia...
...atleta.peso...
struct saude
{
 float peso, altura, IMC;
 niver;
} atleta;
data
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Aula 4
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Ordenar significa dispor elementos de um conjunto seguindo um determinado critério. Esse critério estará baseado em um atributo do elemento do conjunto (nome, matrícula, salário, coeficiente de rendimento, altura, tempo, etc).
O
R
D
E
N
A
Ç
Â
O
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Quando o método de ordenação só usa a Memória Principal para realizar o processo de ordenação, esse método é classificado como de Ordenação Interna, mas se usa uma memória auxiliar porque o arquivo é muito grande, é classificado como de Ordenação Externa.
Ordenação Interna x Ordenação Externa
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 mais eficientes para para pequenos conjuntos;
 usam muitas comparações;
 códigos pequenos;
 códigos de fácil entendimento; 
Exemplos:
1. Selection Sort(Ordenação por seleção)
2. Insertion Sort(Ordenação por inserção)
3. Bubble Sort (Ordenação por troca)
Métodos Simples
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 indicados para conjuntos grandes;
 usam menos comparações;
 os códigos são grandes;
 alguns incluem conceito de recursividade, deixando-os mais complexos.
Exemplos:
Heap Sort(Ordenação por seleção em árvores) 
Shell Sort (Ordenação por inserção, vários segmentos)
Quick Sort(Ordenação por troca/partição)
Métodos Eficientes ou Sofisticados
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
O princípio básico desse método é sempre buscar o menor dos valores restantes e levá-lo às posições iniciais (ordenação crescente).
Selection Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 A ideia é pesquisar em todo o vetor o menor elemento, se a ordenação estiver sendo de forma crescente, e ir armazenando em uma variável a posição do menor que for sendo encontrado.
Após a pesquisa, haverá a troca de posições entre o elemento cuja posição está armazenada na variável com o elemento que se encontra na primeira posição.
Esse procedimento se repetirá para a busca do segundo terceiro, etc, até que o vetor esteja ordenado.
Selection Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
O princípio básico desse método é considerar o vetor como dois subvetores, um ordenado e o outro, desordenado, buscando posicionar o elemento que se encontra no subvetor desordenado, no vetor ordenado.
Insertion Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
O princípio básico desse método é considerar o vetor como dois subvetores, um ordenado e o outro, desordenado, buscando posicionar o elemento que se encontra no subvetor desordenado, no vetor ordenado.
Insertion Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
A ideia é começar comparando o elemento que se encontra na segunda posição com o da primeira posição e se for menor(ordem crescente), eles trocam de lugar.
Depois passamos para o elemento da terceira posição que deverá ser comparado com os que o antecedem, sendo colocado em sua devida posição, ou permanecendo na terceira se já estiver em ordem.
Caso ele seja menor, um deslocamento para direita será necessário para que o elemento assuma sua posição. Esse procedimento se repetirá até que o vetor esteja ordenado. 
É considerado o melhor dos três métodos estudados.
Insertion Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
O princípio básico desse método é trocar valores deposições adjacentes que se encontrem fora de ordem.
Bubble Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
A ideia é comparar dois elementos de posições adjacentes e, se estiverem fora de ordem, deverão ser trocados de lugar.
Essa troca, vindo de baixo para cima, dá uma impressão de borbulhamento.
Esse procedimento se repetirá até que o vetor esteja ordenado.
É um método simples o que justifica ser o mais conhecido, mas muito lento e considerado o pior dos três estudados.
Bubble Sort
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
cout<<"\n...? ";
cin>>varProcura;
achou=0;
for(L=0;L<tamLinha && achou==0;L++)
{ 
 if(varProcura==vetor[L])
 {
 achou=1; posicao=L;
 } 
}
if(achou==1)
 cout<<"\n...: "<<outroVetor[posicao]<<endl;
else
 cout<<"\nDado nao achado\n";
S
E
Q
U
E
N
C
I
A
L
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Uma informação importante a saber
 O vetor não precisa estar ordenado.
A busca é mais simples porque se percorre o vetor pelo índice(deslocamento).
O melhor caso é quando o elemento procurado se encontra na primeira posição e o pior, na última.
 Retorna a posição do elemento quando encontrado.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
cout<<"\n...? ";
cin>>procura;
inicio=0; 
fim= tamanho - 1;
meio=(inicio+fim)/2; 
while(procura != nomeVetor[meio] && inicio != fim)
{
 if(procura > nomeVetor[meio]) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
}
if(nomeVetor[meio]==procura)
 cout<<"\n....: "<<outroVetor[meio]<<endl;
else 
 cout<<"\nDado nao encontrado\n";
B
I
N
Á
R
I
A
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Uma informação importante a saber
 O vetor tem que estar ordenado.
 Divide-se, sucessivamente, o vetor ao meio, comparando o elemento procurado com o elemento que se encontra na posição central, descartando metade do vetor.
 É mais eficiente do que a busca sequencial.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if( procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else cout<<"\nDado nao encontrado\n";
}
inicio=meio +1;
fim=meio;
meio=(inicio+fim)/2;
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Suponha um vetor de struct com dez elementos.
Sabe-se que a struct tem dois membros: numChamada e CR.
Vamos acompanhar, no teste de mesa, a busca do número de chamada 18
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
2
13
9
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
2
13
18
9
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
2
13
18
18 > 13
9
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
5
7
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
15
23
18
9
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
5
7
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
18
15
23
18
9
Teste de Mesa - 1
18 < 23
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
5
6
7
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
15
23
18
18
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
5
6
7
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
15
23
18
18
Teste de Mesa - 1
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Vamos acompanhar, no teste de mesa, a busca do número de chamada 6
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
2
9
13
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
2
9
13
6
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
4
9
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
2
9
13
 6 < 13
6
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
2
4
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
2
13
5
6
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
0
2
4
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
2
13
5
6
 6 > 5
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
3
3
4
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
6
13
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
3
3
4
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
6
13
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
 vet i m f p
 MP
0
1
2
3
4
5
6
7
8
9
3
3
4
2
18
29
13
15
23
30
4
5
6
8.0
6.1
4.0
6.7
9.5
6.9
8.1
8.9
8.4
7.0
6
6
13
Teste de Mesa - 2
void binaria(dados vet[], int procura, int tam)
{ int inicio, fim, meio;
 inicio=0; 
 fim= tam - 1;
 meio=(inicio+fim)/2; 
 if(tam==0)
 { cout<<"Lista vazia\n"; return ;}
 while(procura != vet[meio].numChamada && inicio != fim)
 {
 if(procura > vet[meio].numChamada) inicio=meio+1;
 else fim=meio; 
 meio=(inicio+fim)/2; 
 }
 if(vet[meio].numChamada==procura)
 cout<<"\n"<<vet[meio].numChamada<<"\t"<<vet[meio].CR<<endl;
 else 
 cout<<"\nDado nao encontrado\n";
}
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Aula 5
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Uma lista é uma forma de agrupar itens com a finalidade de melhorar sua manipulação.
… É a propriedade sequencial de uma lista linear que dá a base para sua definição e seu uso.
De acordo como os dados são inseridos, ou removidos, da lista é que é sugerida uma classificação(MORAES, C.R. 2011, p27-28).
Conceito de Lista Linear
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
LIFO
FIFO
FDER(Fila De Entrada Restrita) - recuperado de qualquer extremidade, mas inserido só em uma..
FDSR( Fila De Saída Restrita - pode ser inserido em qualquer extremidade, mas recuperado só em uma.
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
DESENVOLVEDOR DECIDE!
A
L
0
C
A
Ç
Ã
o
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
DESENVOLVEDOR DECIDE!
AGRUPAMENTO
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
DESENVOLVEDOR DECIDE!
A
L
0
C
A
Ç
Ã
o
AGRUPAMENTO
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Verificar se a Lista esta vazia;
 Verificar se a Lista esta cheia;
 Inserir elemento na Lista;
 Removerelemento da Lista;
 Exibir o tamanho da lista;
 Retornar a posição de um elemento da Lista;
 Exibir a Lista;
 Ordenar; 
 Pesquisar; 
Operações realizadas com Listas Lineares
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Função insere
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Função exibe
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1
Resumindo
ESTRUTURA DE DADOS
AULA DE REVISÃO AV1