Introdução às Estruturas de Dados

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 1- Apresentando as Estruturas de Dados 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Atenção aos Temas Principais dessa Aula
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Conteúdo Programático desta aula
	O conceito de Estruturas de Dados;
	O conceito de TAD;
	Apresentar o conceito de funções;
	Apresentar o conceito de struct;
	Apresentar os conceitos de ordenação e pesquisa;
	Apresentar o conceito de Lista, Pilha e Fila Estática;
	Apresentar o conceito de Ponteiro;
	Apresentar o conceito de Alocação Dinâmica;
	Revisão de Matrizes
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Direto ao Assunto
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA 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)
Conceito de Estrutura de Dados
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
“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)
“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)
Conceito de Estrutura de Dados
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Armazenamento 
da Informação
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Armazenamento 
da Informação
Construção de
Algoritmos
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Armazenamento 
da Informação
Construção de
Algoritmos
Características 
das ED
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Armazenamento 
da Informação
Construção de
Algoritmos
Características 
das ED
(PREISS, B. R., 2000,
 p.1)
C
O
N
H
E
C
I
M
E
N
T
O
S
S
Ó
L
I
D
O
S
O
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
“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)
Tipo de Dados Abstratos(TDA)
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
O QUE
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
O QUE
Exemplos
1 – Gravar um vetor em um arquivo binário
2 – Usar o TDA int
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
DE COMO
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
DE COMO
Exemplo
Como se processa o comando de atribuição?
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
É 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. 
Conteúdo da Disciplina
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
void asterisco()
{
 int x;
 for(x=1: x<=50; x++)
 cout<<“*”;
}
2a AULA - FUNÇÕES
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3a AULA - STRUCT
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3a AULA - STRUCT
struct cadastro
{
 char nome[30], e-mail[20], plano[20], end [40], tel1[15], tel2[15];
 int idade;
};
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
4a AULA - ORDENAÇÃO / PESQUISA
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
5a AULA - LISTAS LINEARES
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
6a AULA – PILHA(LIFO)
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
7a AULA – FILA(FIFO)
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
8a AULA – ALOCAÇÃO DINÂMICA
 LISTA ENCADEADA
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
8a AULA – ALOCAÇÃO DINÂMICA
 LISTA ENCADEADA
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
9a AULA – LISTAS LINEARES
PILHA DINÂMICA
FILA DINÂMICA
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10a AULA – LISTAS DUPLAMENTE ENCADEADAS
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
	 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.
	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).
METODOLOGIA DE ESTUDO
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
	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.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
SERÁ? 
Que tal pesquisar o que significa
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
SERÁ? 
Que tal pesquisar o que significa
E, o mais importante: nós, professores de Estrutura de Dados, vamos fazer de tudo para que isso se torne real porque já abstraímos muito nesta primeira aula.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
*
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.
Referências Bibliográficas
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
*
REVISÃO - MATRIZES
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
MATRIZES
2
3
1
13
A4x1
2 3 1 13
A1x4
a11 a12 a13 ... a1n
a21 a22 a23 ... a3n
a31 a32 a33 ... a3n
... ... ... ... ...
am1 am1 am2 ... amn
Amxn
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
unidimensional
bidimensional
MATRIZES
2
3
1
13
A4x1
2 3 1 13
A1x4
a11 a12 a13 ... a1n
a21 a22 a23 ... a3n
a31 a32 a33 ... a3n
... ... ... ... ...
am1 am1 am2 ... amn
Amxn
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Operação – Multiplicar por um escalar
4
6
2
26
D4x1
2
3
1
13
A4x1
X 2 =
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Operação – Somar duas matrizes
2
3
1
13
A
6
9
3
39
S
4
6
2
26
B
+
=
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Operação: calcular média aritmética
4
5
6
10
A
6
6
7.5
7
M
8
7
9
4
B
+
/ 2 =
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Operação: somar os elementos da matriz
4
5
6
10
A
Soma = 25
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Dimensionando Matrizes 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Dimensionando Matrizes 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Dimensionando Matrizes 
int 
float
double
char
long long int
...
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
1) Guardar 10 idades.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
1) Guardar 10 idades.
APRESENTANDO AS ESTRUTURASDE DADOS – AulA1
ESTRUTURA DE DADOS
1) Guardar 10 idades.
2) Duas notas e a média de 50 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
1) Guardar 10 idades.
2) Duas notas e a média de 50 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
1) Guardar 10 idades.
2) Duas notas e a média de 50 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3) Matrícula e CR de 60 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3) Matrícula e CR de 60 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3) Matrícula e CR de 60 alunos.
4) Sexo de 30 pessoas.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
3) Matrícula e CR de 60 alunos.
4) Sexo de 30 pessoas.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
5) Nome de uma pessoa.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
5) Nome de uma pessoa.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
5) Nome de uma pessoa.
6) Nomes de 10 pessoas.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
6) Nomes de 10 pessoas.
5) Nome de uma pessoa.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor de tamanho 5 e do tipo inteiro de quatro bytes
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor idades
Vetor de tamanho 5 e do tipo inteiro de quatro bytes
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor idades
Vetor de tamanho 5 e do tipo inteiro de quatro bytes
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Por que a primeira variável tem deslocamento 0?
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
endereço-base + deslocamento * tamanho do tipo 
O nome de uma matriz corresponde ao primeiro endereço do conjunto de endereços da Memória Principal. Para localizarmos um elemento da matriz, usamos a fórmula abaixo.
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo 
endereço-base
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo 
endereço-base + 2 * 4 = 1008
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo 
endereço-base + 2 * 4 = 1008
10008
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo 
endereço-base
10012
10016
10004
10008
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Armazenamento na Memória Principal 
Conclui-se que 0 significa que não existe deslocamento em relação ao endereço-base.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
E onde indicamos isso?
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Observe o vetor idades[5]. Ele é formado por cinco variáveis todas com nome, idades. Dentro de um par de colchetes, fica o deslocamento.
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor de char
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor de char
Armazenamento na Memória Principal 
nome[1] = toupper(nome[1]); REnato
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
O \0 serve para finalizar o vetor de char. Dessa forma, não se esqueça de acrescentar mais uma posição quando dimensionar um vetor de char. 
Vetor de char
Armazenamento na Memória Principal 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico ou vetor de char – unidimensional 
DECLARAÇÃO / ATRIBUIÇÃO 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
DECLARAÇÃO / ATRIBUIÇÃO 
Numérico ou vetor de char – unidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
DECLARAÇÃO / ATRIBUIÇÃO 
Numérico ou vetor de char – unidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
DECLARAÇÃO / ATRIBUIÇÃO 
Numérico ou vetor de char – Bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
DECLARAÇÃO / ATRIBUIÇÃO 
Numérico ou vetor de char – Bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico – Bidimensional 
ATRIBUIÇÃO 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico ou char de um caracter – unidimensional 
TRECHO de ENTRADA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
Numérico ou char de um caracter – unidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
Vetor de char – unidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
Vetor de char – unidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
Numérico – bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
Numérico – bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
char – bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de ENTRADA 
char – bidimensional 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico ou char (Matriz Coluna) – unidimensional 
TRECHO de SAÍDA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico ou char (Matriz Linha) – unidimensional 
TRECHO de SAÍDA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vetor de char – unidimensional 
TRECHO de SAÍDA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico – bidimensional 
TRECHO de SAÍDA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
char – bidimensional 
TRECHO de SAÍDA 
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Vamos ao Bate Pronto
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
1)
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Resumindo