aula 1

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
C
O
N
H
E
C
I
M
E
N
T
O
S
S
Ó
L
I
D
O
S
O
(PREISS, B. R., 2000,
p.1)
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
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
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
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
FAZER
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
33
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
34
REVISÃO - MATRIZES
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
MATRIZES
2
3
1
13
A4x1
2 3 1 13A1x4
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 13A1x4
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+ / 2 =
8
7
94
B
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 ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
2) Duas notas e a média de 50 alunos.
1) Guardar 10 idades.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
2) Duas notas e a média de 50 alunos.
1) Guardar 10 idades.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
2) Duas notas e a média de 50 alunos.
1) Guardar 10 idades.
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
4) Sexo de 30 pessoas.
3) Matrícula e CR de 60 alunos.
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
4) Sexo de 30 pessoas.
3) Matrícula e CR de 60 alunos.
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
5) Nome de uma pessoa.
6) Nomes de 10 pessoas.
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
Armazenamento na Memória Principal
endereço-base + 2 * 4 = 1008
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo
Armazenamento na Memória Principal
endereço-base + 2 * 4 = 1008
10008
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
10000
endereço-base + deslocamento * tamanho do tipo
Armazenamento na Memória Principal
endereço-base
10012 1001610004 10008
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
Numérico ou vetor de char – unidimensional
DECLARAÇÃO / ATRIBUIÇÃO
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
Numérico ou vetor de char – Bidimensional
DECLARAÇÃO / ATRIBUIÇÃO
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
Numérico ou vetor de char – Bidimensional
DECLARAÇÃO / ATRIBUIÇÃO
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
ATRIBUIÇÃO
Numérico – Bidimensional
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
TRECHO de SAÍDA
Numérico ou char (Matriz Coluna) – unidimensional
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de SAÍDA
Numérico ou char (Matriz Linha) – unidimensional
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de SAÍDA
Vetor de char – unidimensional
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de SAÍDA
Numérico – bidimensional
APRESENTANDO AS ESTRUTURAS DE DADOS – AulA1
ESTRUTURA DE DADOS
TRECHO de SAÍDA
char – bidimensional
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