revisaoav1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
ESTRUTURAS DE DADOS – Revisão AV1
ANITA MACIEL
Rio de Janeiro, 2011
*
*
*
*
*
*
AULA 1
*
*
*
*
Em linguagem de programação, especifica o conjunto de valores que poderá ser manipulado.
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
*
*
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.
Tipos de Dados
*
*
Tipos Abstrato de Dados
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.
*
*
“Tipos abstratos de dados(TADs)são conjunto de valores que apresentam um comportamento uniforme definido por um grupo de operações (geralmente, um grupo de constantes iniciais e um conjunto de funções e procedimentos).” 
(VAREJÃO, F., 2004,168)
Tipos Abstrato de Dados
*
*
Estruturas de Dados
Para que possamos implementar uma TAD, precisamos escolher uma Estrutura de Dados e, para que isso seja feito da forma mais adequada, temos que conhecer as características de cada estrutura.
Logo, são as Estruturas de Dados que definem como os dados serão organizados e acessados.
*
*
Tipos de Estruturas Lineares(estudaremos) 
 Listas
 Pilhas
 Filas 
 Filas Circulares
 Listas simplesmente Encadeadas 
 Listas duplamente Encadeadas
Estáticas e Dinâmicas
Estruturas de Dados
*
*
Tipos de Estruturas não Lineares
(não estudaremos) 
 Árvores
 Grafos 
Estruturas de Dados
*
*
Ler os slides da Aula 1 teletransmitida
Ler o conteúdo da AULA 1
Assistir à AULA 1 teletransmitida
*
*
AULA 2
*
*
“Função é um conjunto de comandos que executam uma determinada tarefa.”
(SAADE, Joell, 2003, 99)
*
*
Um programa pode ser formado por uma ou mais funções.
A função main sempre estará presente.
*
*
*
*
 Definição da função
*
*
 Cabeçalho da função
 Protótipo da função
*
*
 Corpo da função
(escopo)
*
*
 Chamada da função
 
 Fluxo após término da Função
No lugar em que é chamada -
Na instrução seguinte -
*
*
 Chamada da função
 
 Fluxo após término da Função
No lugar em que é chamada - retorno
Na instrução seguinte - void
Pelo nome
*
*
Tipos
void
int
float
double
char
...
*
*
PASSAGEM POR REFERÊNCIA &
PASSAGEM POR VALOR
*
*
PASSAGEM POR REFERÊNCIA &
PASSAGEM POR VALOR
Uma cópia é passada para a função, o valor original não se altera.
O endereço da variável é passado para a função. Logo, o valor da variável poderá ser alterado pela função.
*
*
Exemplo 1
float desconto(float valor, float percentual)
{
 return valor - valor * percentual/100;
}
Esta função recebe dois valores reais
e retorna o resultado da operação que é 
o valor com desconto.
parâmetros
*
*
void reajusta(float &sal, float premio)
{
 sal+= premio;
}
Esta 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.
Exemplo 2
Variável que recebe endereço
*
*
#include <iostream>
using namespace std;
void reajusta(float &sal, float premio);
int main()
{ float salario=5000, premio=300;
 cout<<"\nsalario com premio: "<<salario+premio<<endl;
 reajusta(salario, premio);
 cout<<"\nsalario com premio: "<<salario<<endl;
 system("pause");
} 
void reajusta(float &sal, float premio)
{
 sal+= premio;
}
*
*
float mediaSalarial(float sal[], int tam)
{
 float soma=0;
 for(int x=0; x<tam; x++)
 soma + sal[x]; 
 return soma/tam;
}
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
Exemplo 3
*
*
void minuscula(char pal[])
{
 int x;
 for(x=0; x<strlen(pal); x++)
 pal[x] = tolower(pal[x]);
}
Exemplo 4
Esta função recebe um endereço de um vetor de char e converte para letras minúsculas.
*
*
#include <iostream>
using namespace std;
void minuscula(char pal[]);
int main()
{ char frase[]={"CHOCOLATE"};
 minuscula(frase);
 cout<<frase<<endl;
 system("pause");
}
void minuscula(char pal[])
{
 int x;
 for(x=0; x<strlen(pal); x++)
 pal[x] = tolower(pal[x]);
}
E strcpy(..., ...) ?
Sabia!
*
*
Ler os slides da Aula 2 teletransmitida
Ler o conteúdo da AULA 2
Assistir à AULA 2 teletransmitida
*
*
AULA 3
*
*
Estrutura heterogênea
Uma estrutura é formada por um ou mais elementos que são agrupados por uma lógica e associados a um nome.
*
*
Quais são esses elementos?
Os elementos podem ser de tipos diferentes?
*
*
Quais são esses elementos?
Variáveis simples, matrizes, outras estruturas e até funções.
Os elementos podem ser de tipos diferentes?
Sim. Essa é a grande vantagem do struct.
*
*
Como é chamado um elemento?
Qual a diferença entre uma estrutura global e uma estrutura local?
*
*
Como é chamado um elemento?
Cada elemento da estrutura é chamado de membro ou campo.
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.
*
*
 Definição de struct
*
*
É permitido definir uma estrutura como variável global?
*
*
É permitido definir uma estrutura como variável global?
Claro, visto que você usará funções em seus programas que usarão struct, provavelmente.
*
*
Como chamamos uma estrutura que não tem identificador?
*
*
Como chamamos uma estrutura que não tem identificador?
Anônima.
*
*
Como se declara uma variável do tipo definido por uma estrutura?
Como se acessa um membro de uma estrutura?
*
*
Como se declara uma variável do tipo definido por uma estrutura?
Depois da definição ou junto com a definição.
Como se acessa um membro de uma estrutura?
Coloca-se o nome da variável estrutura, seguida do ponto e do nome do membro.
*
*
Como se atribui valores aos membros?
*
*
Como se atribui valores aos membros?
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.
*
*
 Exemplo de declaração
struct produto
{
 char nomeProd[21];
 float valor;
}prod1;
*
*
 Acessando os membros
...prod1.nomeProd...
...prod1.valor...
struct produto
{
 char nomeProd[21];
 float valor;
}prod1;
*
*
 Atribuindo valores aos membros na declaração
produto prod1={“grampeador”,23.15};
struct produto
{
 char nomeProd[21];
 float valor;
}prod1;
*
*
Declarando um array de estruturas
struct dados
{
 char nome[31];
 int matricula;
 float CR;
}alunos[40];
*
*
struct dados
{
 char nome[31];
 int matricula;
 float CR;
}alunos[40];
...alunos[0].nome...
...alunos[0].matricula...
...alunos[0].CR
*
*
Estruturas e Funções
PASSAGEM POR REFERÊNCIA &
PASSAGEM POR VALOR
Passamos uma cópia do valor do membro logo, ele não se altera.
Passamos o endereço do membro logo, ele pode se alterar. Vai depender da função.
*
*
Uma estrutura pode ser parâmetro de uma função?
O retorno de uma função pode ser uma estrutura?
*
*
Uma estrutura pode ser parâmetro de uma função?
Sim.
O retorno de uma função pode ser uma estrutura?
Sim.
*
*
*
*
#include <iostream>
using namespace std;
struct manipulaNumeros
{
 int contaAlgarismos(int num)
 { int cont=0;
 while(num>0)
 { cont++; num/=10; } 
 return cont;
 }
};
int main()
{ 
 manipulaNumeros entrada;
 cout<<"\nTotal:"<<entrada.contaAlgarismos(123456);
 cout<<"\n\n";
 system("pause");
}
*
*
Ler os slides da Aula 3 teletransmitida
Ler o conteúdo da AULA 3
Assistir à AULA 3 teletransmitida
*
*
AULA 4
*
*
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, etc). 
*
*
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
*
*
Métodos Simples (ordenação interna)
indicados para conjuntos pequenos;
usam muitas comparações;
os códigos são pequenos;
códigos de fácil entendimento; 
mais eficientes para pequenos arquivos.
Exemplos:
1. Selection Sort
2. Insertion Sort
3. Bubble Sort 
*
*
Métodos Eficientes ou Sofisticados(interna)
indicados para conjuntos grandes;
usam menos comparações;
os códigos são grandes;
alguns incluem o conceito de recursividade, deixando-os muito complexos.
Exemplos:
1. Shell Sort
2. Quick Sort
3. Heap Sort
4. Merge Sort
*
*
*
*
if(vet[0]>vet[1])
{
 aux=vet[0];
 vet[0]=vet[1];
 vet[1]=aux;
} 
Vetores numéricos e char de um caracter
 Comparados através dos operadores relacionais >, >=, <, <= , == e !=.
Para trocar os conteúdos das variáveis, o comando de atribuição poderá ser usado. 
*
*
 if(strcmp(vet[0],vet[1]) > 0)
 {
 strcpy(aux,vet[0]);
 strcpy(vet[0],vet[1]);
 strcpy(vet[1],aux);
 } 
Vetores de char
 strcmp(para comparar os vetores)
 strcpy( para copiar o conteúdo de um vetor de char nas posições ocupadas por outro vetor de char). 
*
*
if(alunos[0].mat>alunos[1].mat)
{
 aux=alunos[0];
 alunos[0]=alunos[1];
 alunos[1]=aux;
} 
Comparando membros de structs
 Numéricos ou char de um caracter: >, >=, <, <= , == e != e, para trocar os conteúdos das variáveis, o comando de atribuição.
 Vetor de char: strcmp e strcpy. 
*
*
Uma das vantagens de se usar struct é na comparação porque trocamos a struct toda e não precisamos de vários trechos de trocas como fazíamos quando usávamos vetores. 
*
*
A ideia é pesquisar em todo o vetor, o menor elemento se a ordenação estiver sendo de forma crescente.
Após a pesquisa, haverá a troca 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.
A lógica do Método Selection Sort
*
*
Método Selection Sort
*
*
A ideia é começar comparando o elemento que se encontra na segunda posição com o da primeira posição e se for menor(comparando em 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, se for menor ou permanecendo na terceira.
Caso ele seja menor, um deslocamento será necessário para que o elemento assuma sua posição. Esse procedimento se repetirá até que o vetor esteja ordenado.
A lógica do Método Insertion Sort 
*
*
Método Insertion Sort 
*
*
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.
A lógica do Método Bubble Sort 
*
*
Método Bubble Sort 
*
*
*
*
 Ideal para arquivos pequenos.
 Muito simples.
 Não melhora sua performance se o arquivo já estiver ordenado.
 Tem menos movimentos do que o Insertion Sort.
TRECHO DO MÉTODO
Selection Sort
Insertion Sort 
 Só ordena quando necessário.
 Existe um deslocamento quando um elemento é inserido em sua posição.
 É considerado o melhor dos três métodos estudados. 
TRECHO DO MÉTODO
Bubble Sort 
 É o mais conhecido método.
 É muito simples.
 É considerado o pior dos três estudados . 
TRECHO DO MÉTODO
*
*
PESQUISA
SEQUENCIAL
BINÁRIA
*
*
PESQUISA
SEQUENCIAL
Simples, mas ineficiente, porque faz uma busca em toda a matriz até encontrar o elemento.
*
*
PESQUISA
BINÁRIA
Mais eficiente, mas exige que a matriz(vetor) esteja ordenado.
Seu princípio é dividir, sucessivamente, ao meio o vetor e identificar em que metade pode estar o elemento até encontrá-lo.
*
*
Para Pensar
Pesquisar valor que se tem certeza de que está bem no início?
Não sei onde está o valor?
*
*
*
*
Ler os slides da Aula 4 teletransmitida
Ler o conteúdo da AULA 4
Assistir à AULA 4 teletransmitida
*
*
AULA 5
*
*
*
*
 Conceito de Lista
A estrutura que permite representar um conjunto de dados de forma a preservar a relação de ordem linear (ou total) entre eles é a lista linear. Uma lista linear é composta de nós, os quais podem conter, cada um deles, um dado primitivo ou um dado composto. (VELOSO,P.,SANTOS,C., AZEREDO,P., FURTADO, A., 1983,79) 
*
*
Nó ou nodo– é um item da lista. 
Comprimento ou tamanho de uma lista
Lista vazia é lista sem nó
*
*
Formas de agrupar elementos de uma Lista Linear na MP
Sequencial
Encadeada
Formas de alocação
Estática
Dinâmica
*
*
Processando informações
Estática - reservada durante a programação. 
Dinâmica - reservada durante a execução. 
Sequencial - elementos alocados de forma
 contígua. 
Encadeada - os elementos não são alocados de
 forma contígua.
*
*
Dizemos que uma Lista é linear porque cada nodo tem somente um sucessor.
Por que uma Lista é chamada de linear
A Lista não tem restrição quanto à forma se acesso.
Várias operações podem ser realizadas com a Lista.
A Pilha e a Fila são casos particulares da Lista.
*
*
*
*
*
*
*
*
*
*
Ler os slides da Aula 5 teletransmitida
Ler o conteúdo da AULA 5
Assistir à AULA 5 teletransmitida
*
*
 Tanta matéria para estudar. Será que vou me dar bem?
 Claro! Você não fez todas as listas? Não leu todas as aulas? Não assistiu às aulas teletransmitidas? Então, estou contando com seu 10.
*
*
*
*
*
*