Buscar

Aula 1 PARTE 1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 12 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

ESTRUTURA DE
DADOS
Profa. Jane 
Mestre em Engenharia de Sistemas e Computação 
COPPE /UFRJ
Aula 1- parte 1 
AULA 1 
 Unidade 1 
 Introdução
 Revisão de vetor/matriz
2
MOTIVAÇÃO PARA O ESTUDO DE
ESTRUTURA DE DADOS
 Para a solução de um problema é importante 
determinarmos uma abstração da realidade, o 
que significa representar as informações 
(dados) que são relevantes para a solução 
deste problema. 
 A abstração pode ser vista como uma 
simplificação dos dados. 
 Exemplo : Considere um cadastro de alunos de 
uma escola. Existem dados relevantes (nome, 
matrícula, disciplinas, ano ...) e irrelevantes
(cor dos olhos do aluno, cor da mochila, marca da 
borracha ...). 3
 Como escolher os dados relevantes ? 
Analisando as características do problema a 
ser resolvido. 
 Uma vez feito isto, como representar estas 
informações ? 
A escolha da forma de representar os dados não 
é trivial e vai depender das relações 
existentes entre tais dados, ou seja, da 
organização dos dados e também, da forma 
com que eles serão manipulados para a 
solução do problema.
4
Niklaus Wirth : 
programa = algoritmo + dados
Para programar é fundamental sabermos 
como organizar (estruturar) os dados dos 
nossos programas e realizar operações 
(manipulações) sobre tais dados, através das 
instruções dos algoritmos.
5
PORTANTO : 
 As estruturas de dados estudam as relações 
lógicas existentes entre os dados (ex: relação 
linear, relação hierárquica ..) e serão 
manipuladas através de operações sobre os 
dados (ex: consultar uma informação em um 
conjunto de fichas de alunos, remover um 
assinante de uma lista de assinantes, apagar um 
diretório em uma árvore de diretórios e 
subdiretórios...). 
 A escolha da estrutura de dados a ser 
utilizada, refletirá diretamente na construção de 
uma solução mais eficiente ou menos eficiente 
para o problema. 
6
NÃO FAÇA CONFUSÃO DE ...
 Estrutura de dados ≠ tipos de dados.
 Note que os tipos de dados dividem-se em :
 Tipos primitivos : estão embutidos na linguagem. 
Exemplos no C++ : os tipos int, float, double, char, 
bool.
 Tipos agregados : podem ser construídos.
Exemplos : vetor (array), matriz, registro (no C/C++ 
usamos a palavra reservada struct para criar registro)
7
EXEMPLOS DE ESTRUTURAS DE DADOS
 Lista
 Pilha
 Fila
 Árvore
 Grafo
 1) Como representar a estrutura organizacional 
de uma empresa com 1 presidente, 1 vice-
presidente, 2 diretores (Vendas e Finanças) e 3 
sub-diretores ? 
 2) Como representar o conjunto de livros 
informados nesta disciplina ?
 3) Como organizar o esquema de tele-entrega de 
pizzas ? Imagine uns 4 tipos de pizzas. Como 
devem ser organizadas, estruturadas para que o 
esquema de entrega seja mais adequado ? 
Imagine como as pizzas podem ser organizadas 
na garupa da moto de um moto-boy. 9
Exemplos : Como você representaria 
graficamente e de forma livre, sem 
formalismos, cada item a seguir ?
 4) Como funciona o sistema de atendimento nas 
linhas de ônibus ?
 5) Como funciona a entrega de cigarros de uma 
marca X na Tijuca, sabendo-se que existe uma 
Van que cobre 10 pontos de vendas, conectados 
por ruas de mão única e de mão dupla ? Como 
representar estes pontos e as ligações entre eles ?
10
CONCLUINDO ....
 Estrutura de dados linear  lista, pilha, fila 
relação linear entre os dados (existe um 1º. 
elemento, um último elemento e dado um 
elemento qualquer (exceto o 1º. e o último), ele 
possui um antecessor e um sucessor.) Exemplos : 
2, 3 e 4
 Estrutura de dados não lineares  árvore e 
grafo. No caso de árvore, existe uma relação de 
hierarquia, de subordinação. Já no caso do grafo, 
existe possibilidade de relação entre quaisquer 
elementos. Exemplos 1) e 5) – slides 20 e 21 11
POR EXEMPLO ...
PENSANDO NA ESTRUTURA DE DADOS LISTA ...
Como representar na memória do computador os dados 
de uma lista ? Há 2 formas :
 sequencial (contígua) : os dados estão dispostos de 
forma seqüencial na memória, um após o outro, em 
endereços seqüenciais ou contíguos. Devemos pré-
definir o tamanho máximo da lista. Usa-se vetor.
 encadeada : os dados estão dispostos de forma 
encadeada na memória, não seguindo uma ordem 
seqüencial, mas sim um armazenamento aleatório. 
Não é preciso pré-definir um tamanho máximo.

Outros materiais