Estrutura Dados Aula 2 - Boente

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

*
*
Estrutura de Dados
(INF8062)
Prof. Alfredo Boente, PhD.
alfredo.boente@uva.edu.br
*
*
Introdução à Estrutura de Dados
Na computação, uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.
Diferentes tipos de estrutura de dados são adequadas a diferentes tipos de aplicação e algumas são altamente especializadas, destinando-se a algumas tarefas específicas.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
Estruturas de dados e algoritmos são temas fundamentais da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação.
Sabe-se que algoritmos tratam dados que podem apresentar certa complexidade.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
Quando estes dados estão organizados de forma coerente, caracterizam uma forma específica, uma estrutura de dados.
A organização e os métodos para manipular essa estrutura é que lhe conferem singularidade.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
As estruturas de dados são chamadas tipos de dados compostos que dividem-se em homogêneos (vetores e matrizes) e heterogêneos (registros).
As estruturas homogêneas são conjuntos de dados formados pelo mesmo tipo de dado primitivo.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
As estruturas heterogêneas são conjuntos de dados formados por tipos de dados primitivos diferentes (campos do registro) em uma mesma estrutura.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
A escolha de uma estrutura de dados apropriada pode tornar um problema complicado em um de solução relativamente simples.
O estudo das estruturas de dados está em constante desenvolvimento e se preocupa com o comportamento padrão delas.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
As Estruturas de Dados são utilizadas para comportar dados de média complexidade, em atendimento a necessidades inerentes do problema apresentado.
Existem várias estruturas de dados disponíveis: vetor, matriz, ponteiro, lista, pilha, fila etc.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
REGISTROS & ARQUIVOS
Como já foi explicado, o registro representa uma estrutura de dados heterogênea.
Um arquivo, também representa uma estrutura de dados heterogênea, é fisicamente uma coleção de registros.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
REGISTROS & ARQUIVOS
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
VETORES
A estrutura vetor representa um endereço de memória onde serão armazenados diversos dados, de acordo com o dimensionamento dado a ele, na própria definição (criação) da variável vetor.
Um vetor representa conjuntos indexados de elementos de um mesmo tipo. 
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
VETORES
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
MATRIZES
Uma matriz nada mais é que um vetor multi-dimensional (precisa ter ao menos duas dimensões).
Uma matriz, assim como o vetor, também representa conjuntos indexados de elementos de um mesmo tipo. 
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
MATRIZES
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
PONTEIROS (Apontador)
Uma variável ponteiro ou apontadora é aquela que ao invés de armazenar certo conteúdo de dado, guarda em seu espaço de memória, o endereço de memória de outra variável que normalmente apresenta um dado a ser manipulado.
Existem linguagens de programação que suprimem o uso de ponteiros ou apontadores.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
PONTEIROS (Apontador)
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
LISTAS
Uma Lista é uma estrutura de dados linear. 
Uma lista pode ser caracterizada como lista ligada ou lista encadeada, e se trata de uma estrutura linear e dinâmica, composta por nós que apontam para o próximo elemento da lista, com exceção do último, que não aponta para ninguém.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
LISTAS
Para compor uma lista encadeada, basta guardar seu primeiro elemento.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
PILHA
As pilhas são estruturas baseadas no princípio LIFO (last in, first out), na qual os dados que foram inseridos primeiros na pilha serão os últimos a serem removidos.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
PILHA
Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
FILA
As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
FILA
Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila.
A operação DEQUEUE só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
GRAFOS
Em computação, grafo é o objeto básico de estudo da teoria dos grafos, e representa um conjunto de pontos (vértices) ligados por retas (arestas).
Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
GRAFOS
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
GRAFOS
Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Um exemplo clássico é a representação de um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
ÁRVORE
Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:
 uma estrutura (uma árvore);
 um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
ÁRVORE
Não Existe árvores vazias, no mínimo haverá um nó raiz (que não possui pai)
Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.
Prof. Alfredo Boente
*
*
Introdução à Estrutura de Dados
ÁRVORE
Prof. Alfredo Boente
*
*
Medida e Análise de Performance
Uma medida de desempenho é uma maneira de medir um determinado desempenho em uma determinada área e de agir sobre os desvios em relação aos objetivos traçados.
Prof. Alfredo Boente
*
*
Medida e Análise de Performance
A mensuração só deve ser feita:
- quando possibilita tomada de ação;
é compreendida e aceita por todos;
é reprodutível.
Prof. Alfredo Boente
*
*
Medida e Análise de Performance
A Análise de Performance permite verificar a eficiência e eficácia do algoritmo computacional. O objetivo é a busca da melhoria contínua do algoritmo (diminuir sua complexidade).
Prof. Alfredo Boente
*
*
Medida e Análise de Performance
A complexidade do algoritmo é definida a partir da forma que o algoritmo está escrito. Por exemplo: podemos ter um algoritmo O(n2), O(n/2) etc.
Este estudo pode ser aprofundado em
Complexidade de Algoritmo Computacional.
Prof. Alfredo Boente
*
*
Medida e Análise de Performance
Prof. Alfredo Boente