Estruturas de Dados e Tipos Abstratos

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

*
*
ESTRUTURAS DE DADOS – AULA 1
ANITA MACIEL
Rio de Janeiro, 2011
*
*
CONHECENDO AS ESTRUTURAS DE DADOS
*
*
“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
*
*
(PREISS, B. R., 2000, p.1)
*
*
(PREISS, B. R., 2000, p.1)
*
*
(PREISS, B. R., 2000, p.1)
*
*
(PREISS, B. R., 2000, p.1)
*
*
“O campo da Estruturas de Dados é concebido para construir ferramentas para serem incorporadas e usadas pelos programas de aplicação e para encontrar Estruturas de Dados que possam realizar certas operações rapidamente sem impor muita carga à memória do computador”.
(DROZDEK, A, 2002, P.31)
*
*
Tipo de Dados Abstratos(TDA)
“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”
(MORAES, C.R., 2001, p.5)
*
*
*
*
Exemplos 1 – Gravar um vetor em um arquivo binário
2 – Usar o TDA int
*
*
Exemplo Como se processa o comando de atribuição?
*
*
CONTEÚDO DA DISCIPLINA
É muito extenso, mas apaixonante.
Procurei desmistificar, abusando de figuras, cores e exemplos clássicos bem escolhidos.
Sei que é um grande desafio, mas nós, professores, estaremos com vocês o tempo todo para que, ao final do curso, possamos dizer: conseguimos. 
*
*
2a AULA - FUNÇÕES
*
*
3a AULA - struct
*
*
4a AULA 
ORDENAÇÃO / PESQUISA
*
*
5a AULA - LISTAS LINEARES
*
*
6a AULA - PILHA(LIFO) 
*
*
7a AULA - FILA(FIFO) 
*
*
8a AULA
ALOCAÇÃO DINÂMICA
 LISTA ENCADEADA
*
*
9a AULA
LISTAS LINEARES ENCADEADAS
PILHA DINÂMICA
FILA DINÂMICA
*
*
10a AULA
LISTAS DUPLAMENTE ENCADEADAS
*
*
 Não acumule aulas porque elas estão muito extensas .
 Lembre-se de que Algoritmos e Estruturas de Dados formam uma parceria perfeita, contribuindo para seu aperfeiçoamento como desenvolvedor.
METODOLOGIA DE ESTUDO
*
*
Reveja todos os conceitos da aula.
Aprimore seus conhecimentos pesquisando no material didático e na bibliografia recomendada (procure na Biblioteca Virtual/ SIA ou na Biblioteca do campus).
Assista aos filmes, se estiverem disponíveis na aula, ou então, pesquise na Internet.
*
*
Esteja sempre em contato com seu professor on-line.
Assista a esta aula quantas vezes for necessário.
*
*
Será? Que tal pesquisar o que significa
*
*
Referências Bibliográficas
*
DROZDEK, A. Estruturas de Dados e Algoritmos
 em C++. São Paulo: Pioneira Thomson, 2002.
MORAES, C. R. Estruturas de Dados e Algoritmos.
 São Paulo: Berkley Brasil, 2001.
PREISS, B. R. Estruturas de Dados e Algoritmos.
 Rio de Janeiro: Campus, 2000.
SENAC.DN. Estruturas de Dados. OLIVEIRA, R.S.,
 TAVEIRA, G. A.,BOTINI, J. Ed. Senac Nacional,
 1999.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Matrizes Unidimensionais (vetores)
tipo nomeMatriz[tamanho] ;
Dimensionamento
*
*
1) Armazenar a quantidade de 10 livros em uma livraria.
Vamos treinar
*
*
1) Armazenar a quantidade de 10 livros em uma livraria.
int livros[10];
Vamos treinar
*
*
2) Altura e peso de 20 pacientes.
Vamos treinar
*
*
2) Altura e peso de 20 pacientes.
float altura[20], peso[20]; 
Vamos treinar
*
*
3) Sexo de 100 pessoas.
Vamos treinar
*
*
3) Sexo de 100 pessoas.
char sexo[100];
Vamos treinar
*
*
4) Nome de uma pessoa.
Vamos treinar
*
*
4) Nome de uma pessoa.
char nome[31];
Vamos treinar
*
*
*
*
*
*
Por que 0?
Vou lhe explicar.
*
*
O nome de uma matriz corresponde ao primeiro endereço do conjunto de endereços na Memória Principal. Para localizarmos um elemento da matriz, usamos a fórmula abaixo.
endereço-base + deslocamento*tamanho do tipo 
*
*
Então, o 0 significa que não tem deslocamento?
Perfeito. Vou lhe provar.
*
*
*
*
*
*
Trecho de Entrada
for( var=0; var <tamanho; var ++)
{
 cout<< “\nmensagem: “;
 cin>>nomeMatriz[var];
} 
*
*
1) Trecho de entrada que armazena a quantidade de livros.
 for(x=0; x<10; x++)
 {
 cout<<"\nIdade: ";
 cin>>livros[x];
 }
Vamos treinar
*
*
 cout<<"\n\nTitulo\n\n";
 for(var=0; x<tamanho; var++)
 {
 cout<<nomeMatriz[var], “\t”;
 } 
matriz linha
Trecho de Saída
*
*
 cout<<"\n\nTitulo\n\n";
 for(var=0; x<tamanho; var++)
 {
 cout<<nomeMatriz[var], “\n”;
 } 
matriz coluna
Trecho de Saída
*
*
int idades[10] , x;
1) Os três trechos - matriz linha
Vamos treinar
*
*
 for(x=0; x<10; x++)
 {
 cout<<"\nIdade: ";
 cin>>idades[x];
 }
int idades[10] , x;
1) Os três trechos - matriz linha
Vamos treinar
*
*
 for(x=0; x<10; x++)
 {
 cout<<"\nIdade: ";
 cin>>idades[x];
 }
int idades[10] , x;
1) Os três trechos - matriz linha
Vamos treinar
 cout<<"\n\nIdades\n\n";
 for(x=0; x<10; x++)
 {
 cout<<idades[x]<<"\t";
 } 
*
*
int idades[10] , x;
1) Os três trechos - matriz coluna
Vamos treinar
*
*
 for(x=0; x<10; x++)
 {
 cout<<"\nIdade: ";
 cin>>idades[x];
 }
int idades[10] , x;
1) Os três trechos - matriz coluna
Vamos treinar
*
*
 cout<<"\n\nIdades\n\n";
 for(x=0; x<10; x++)
 {
 cout<<idades[x]<<"\n";
 } 
 for(x=0; x<10; x++)
 {
 cout<<"\nIdade: ";
 cin>>idades[x];
 }
int idades[10] , x;
1) Os três trechos - matriz coluna
Vamos treinar
*
*
2) Duas notas, guarda média de cada aluno no vetor m e a calcula média de 50 alunos...
Trecho que gera a média - aluno
Vamos treinar
*
*
 for(x=0; x<50; x++)
 {
 m[x]=(nt1[x] + nt2[x])/2;
 }
2) Duas notas, guarda média de cada aluno no vetor m e a calcula média de 50 alunos...
Trecho que gera a média - aluno
Vamos treinar
*
*
2) ...Trecho que calcula a média da turma, supondo o vetor m
soma=0;
for(x=0; x<50; x++)
 {
 soma += m[x];
 }
media=soma/5;
Vamos treinar
*
*
*
*
tipo nomeMatriz[tamL] [tamC] ;
Matrizes Bidimensionais
Dimensionamento
*
*
Bem parecido com o armazenamento da matriz unidimensional. Leia na aula online.
Endereço base + número de colunas da matriz * deslocamento linha * número de bytes do tipo
*
*
Vamos treinar
1) Suponha que um médico deseje contratar você para construir um programa que possa armazenar nomes, peso, altura e IMC de 10 pacientes. 
Ele lhe entregou um desenho parecido com o do próximo slide.
*
*
Vamos treinar
*
*
Vamos treinar
*
*
Vamos treinar
*
*
float pacienteDados[10] [3] ;
char pacienteNome[10] [30] ;
Dimensionando as Matrizes
Vamos treinar
*
*
Não consigo entender matriz de char.
Vou explicar.
*
*
char nome [30];
Quando desejamos armazenar um nome nessa Matriz Unidimensional, tratamos como se ela fosse uma variável simples.
cin.getline(nome, 30);
*
*
cin.getline(..., ...)? Não era cin>>... ;?
Calma! Vou explicar a diferença.
*
*
Este objeto libera o teclado para a entrada de dados, mas, em se tratando de um vetor de char, no primeiro espaço encontrado, os caracteres após serão abandonados.
cin>>nome;
*
*
Vamos treinar
*
*
Vamos treinar
*
*
Entendi. Então, existe um comando especial?
O objeto é o mesmo,cin, mas combinado com o método getline(..., ...) 
cin.getline(var, tam);
tam -> número de caracteres + \0 
*
*
Vamos treinar
*
*
Vamos treinar
*
*
2) Suponha que você foi contratado para construir um programa que possa controlar as despesas de um ano de uma pessoa. 
Ele lhe entregou um desenho parecido com o do próximo slide.
Vamos treinar
*
*
Vamos treinar
*
*
Vamos treinar
*
*
Vamos treinar
*
*
float despesasValor[8] [12] ;
char despesasNome[8] [20] ;
Dimensionando as Matrizes
Vamos treinar
*
*
 for(L=0; L < tamanhoLinha ; L++)
 for(C=0; C < tamanhoColuna ; C++)
 nomeMatriz[L] [C]= valor;
valor é uma expressão que pode envolver constante ou operações com outra(s) matriz(es). 
Atribuição
*
*
Atribuindo valores à Matriz bidimensional
 int mat[ ][3]={9,10,10,7,8,9,9,9,10,6,7,8};
//nessa declaração / atribuição, assume-se que a matriz tem quatro linhas
*
*
for(L=0; L < tamanhoLinha ; L++)
{ 
 for(C=0; C < tamanhoColuna
; C++)
 { 
 cout<<”\nLinha ”<<L+1<<” coluna ”<<C+1<<”: ”;
 cin>>nomeMatriz[L][C];
 }
 } 
Entrada via teclado
*
*
Matriz de char
 for(L=0; L < tamanhoLinha ; L++)
 { 
 cout<<”\nNumero da linha ”<<L+1<<”: ”;
 cin.getline(nomeMatriz[L], tam);
 } 
tam valor declarado no dimensionamento (colunas)
Entrada via teclado
*
*
system(”cls”);//limpar a tela ou clear - LINUX
cout<<”\nTitulo\n”;
for (L= 0; L < tamanhoLinha ; L++)
{ 
 for(C=0; C < tamanhoColuna ; C++)
 {
 cout<<nomeMatriz[L][C]<< ”\t”;
 }
 cout<<”\n”;
 } 
Trecho de saída
*
*
Apresentarei os trechos de entrada e saída nos próximos slides para o exemplo 1. No programa, usei tamanho 3 para facilitar o teste. 
Vamos treinar
*
*
 for(L=0; L < TL ; L++) 
 { 
 cout<<"\nNome "<<L+1<<": ";
 cin.getline(pacienteNome[L], 30); 
 cout<<"\nPeso "<<L+1<<": "; 
 cin>>pacienteDados[L][0];
 cout<<"\nAltura "<<L+1<<": "; 
 cin>>pacienteDados[L][1]; 
 pacienteDados[L][2] = pacienteDados[L][0] / (pacienteDados[L][1]* pacienteDados[L][1]); 
 } 
Vamos treinar - entrada
*
*
 system("cls");
 cout<<"\nPeso\tAltura\tIMC\tNome\n";
 for(L= 0; L < TL ; L++)
 cout<<"\n"<<pacienteDados[L][0]<< "\t"<<pacienteDados[L][1]<<"\t"<<pacienteDados[L][2]<<"\t"<<pacienteNome[L];
 
Vamos treinar - saída
*
*
Vamos treinar - programa
*
*
Vamos treinar - Problema
*
*
Vamos treinar - Solução
Limpar o buffer 
cin.get(); 
*
*
 for(L=0; L < TL ; L++) 
 { 
 cout<<"\nNome "<<L+1<<": ";
 cin.getline(pacienteNome[L], 30); 
 cout<<"\nPeso "<<L+1<<": "; 
 cin>>pacienteDados[L][0];
 cout<<"\nAltura "<<L+1<<": "; 
 cin>>pacienteDados[L][1]; 
 pacienteDados[L][2] = pacienteDados[L][0] / (pacienteDados[L][1]* pacienteDados[L][1]); 
 cin.get(); // limpa o buffer 
 } 
Vamos treinar
*
*
Vamos treinar
*
*
Vamos treinar - Entrada
*
*
Vamos treinar - Saída
*
*
*