ESTRUTURA DE DADOS
Professor: Marcelo Mendes
Turma: MBI-1
Período Letivo: 2015/1
Carga Horária: 80 horas
Período da disciplina: 31/03 a 30/04/2015
Número de Avaliações: 3
OBJETIVO DA DISCIPLINA
“Possibilitar aos alunos a utilização otimizada das diversas
estruturas de dados apresentadas, levando em consideração o
problema a ser resolvido ou otimizado, e também o contexto no
qual ocorre esse problema.”
ABSTRAÇÃO DE DADOS
Um processo é qualquer seqüência finita e ordenada de passos que visa promover
transformações definidas sobre uma determinada matéria-prima. Se denominamos
entrada a matéria-prima no seu estado inicial; e saída o que se obtém após as
transformações realizadas pelo processo, temos o esquema geral a seguir:
Matéria-prima abstrata: é processamento de dados.
Abstrata: apresenta-se sob a forma de valores.
Processamento realizado pelo computador:
Entrada: dados colhidos do mundo real externo ao computador;
Processo: série finita de operações que são realizadas a partir desses
dados;
Saída: transformação sofrida pelos dados através de um processo.
TIPOS DE DADOS (TDS)
Embora os termos "tipos de dados", "estruturas de dados" e "tipos abstratos
de dados" sejam parecidos, têm significados diferentes. Em linguagens de
programação o tipo de dados de uma variável define o conjunto de valores
que a variável pode assumir. Exemplo: BOOLEAN pode assumir valores TRUE
ou FALSE. A declaração de uma variável em Pascal especifica duas coisas:
Quantidade de bytes reservados para a variável (ex. 2bytes);
Como o dado representado por esses bytes pode ser interpretado. (ex. 2
bytes = 16 bits = 65536 combinações. Um integer é interpretado de -32767 a
32768 sendo o ponto "zero" bem no meio desses dois bytes).
Tipos de Dados: São métodos para interpretar o conteúdo da memória do
computador. Exemplo de conjunto básico de tipos de dados primitivos
(inteiro, real, caractere, lógico) oferecidos pelas linguagens de programação; e
agrupamentos complexos de dados desses tipos primitivos (vetor, registro,
ponteiro).
TIPOS ABSTRATOS DE DADOS (TADS)
TAD - formado por um conjunto de valores e uma série de
funções que podem ser aplicadas sobre estes valores.
Funções + valores (em conjunto) = modelo matemático
empregado para "modelar" e solucionar problemas do
mundo real:
 Especifica características relevantes dos objetos
envolvidos no problema;
 Especifica forma com que eles se relacionam; e
 Especifica como podem ser manipulados.
TIPOS ABSTRATOS DE DADOS (TADS)
TAD não leva em consideração como os valores são
representados na memória do computador e
nem se preocupa com o "tempo" gasto para
aplicar as funções sobre tais valores.
• Exemplos:
 Listas;
 Pilhas;
 Filas;
AS ESTRUTURAS DE DADOS (EDS)
• É um método particular de implementar um
TAD. A implementação de um TAD escolhe
uma ED para representá-lo. Cada ED é
constituída de tipos básicos (integer, char,
real) ou dos tipos estruturas (array, record) de
uma linguagem.
OBJETIVO DAS ESTRUTURAS DE DADOS:
Teórico: Identificar e desenvolver modelos
matemáticos, determinando que classes de
problemas podem ser resolvidos com o uso
deles.
Prático: Criar representações concretas dos
objetos e desenvolver rotinas capazes de
atuar sobre essas representações, de acordo
com o modelo considerado.
LISTAS LINEARES
• É uma estrutura que armazena elementos de
forma alinhada, ou seja, com elementos
dispostos um após o outro, como em uma lista
de nomes, peças, valores, pessoas, compras,
etc.
FUNDAMENTOS
Uma Lista Linear, é uma coleção L: [a1, a2, ...,
an], n>=0, cuja propriedade estrutural baseiase apenas na posição relativa dos elementos,
que são dispostos linearmente. Se n=0,
dizemos que a lista L é vazia; caso contrário,
são válidas as seguintes propriedades:
a1 é o primeiro elemento de L;
an é o último elemento de L;
Característica fundamental de uma lista linear é o sentido de
ordem unidimensional dos elementos que a compõem.
Assim, não temos dúvida onde inicia ou termina a lista.
Algumas operações com listas:
 acessar um elemento qualquer;
 inserir um elemento numa posição específica;
 remover um elemento de uma posição específica;
 combinar duas listas em uma única;
 particionar uma lista em duas;
 obter cópias de uma lista;
 determinar o total de elementos na lista;
 ordenar os elementos da lista;
 procurar um determinado elemento na lista;
 apagar uma lista;
 outras...
Uma lista com um array, pode ser implementada como uma seqüência
de records com elementos disponíveis:
de forma consecutiva - Lista Estática Seqüencial;
de forma não consecutiva - Lista Estática Encadeada;
Uma lista pode ser ordenada ou não. Pascal permite construir EDs
avançadas - Lista Dinâmicas; mais versáteis, utilizando ponteiros e
variáveis dinâmicas.
Considerando apenas operações de acesso, inserção e remoção
restritas aos extremos das listas, temos casos especiais:
 Pilha: inserção, remoção, acesso realizados em um único extremo.
Lista LIFO.
 Fila: inserção num extremo e remoção, acesso no outro extremo.
Lista FIFO.
ALOCAÇÃO DE MEMÓRIA
• Para implementar uma lista linear: como
podemos armazenar os elementos da lista
dentro do computador? Alocar área de
memória é responsabilidade do programador
e estará em uma das quatro categorias abaixo:
ALOCAÇÃO ESTÁTICA X ALOCAÇÃO DINÂMICA
ALOCAÇÃO ESTÁTICA:
 Quantidade total de memória utilizada pelos dados é
previamente conhecida e definida de modo imutável, no
próprio código-fonte do programa. Durante o programa não
varia a quantidade de memória.
ALOCAÇÃO DINÂMICA:
 Programa cria novas variáveis enquanto executa, ou seja,
áreas de memórias não declaradas no programa passam a
existir durante a execução.
Um ponteiro é uma variável que contém o endereço da memória de outra variável ou
estrutura de dados.