02-Introducao ED

Prévia do material em texto

1 
}  Tiago Maritan 
}  tiago@ci.ufpb.br 
Universidade Federal da Paraíba 
Centro de Informática 
Departamento de Informática 
Estrutura de Dados 
Introdução às ED 
Estrutura de Dados: o que é? 
2 
}  É o ramo da Ciências da Computação que estuda os 
diversos mecanismos de organização de dados para 
atender aos diferentes requisitos de processamento. 
 
 
Ex 1: Como armazenar os dados de um 
sistema de arquivos num computador? 
3 
}  Através de estruturas do tipo Árvore! 
Ex 2: Como armazenar uma lista de clientes 
num sistema computacional ??? 
4 
}  Através de estruturas do tipo Array (vetor) ou Lista. 
Ex 3: Como estruturar o relacionamentos 
entre dados dos usuários numa rede social? 
5 
}  Através de estruturas do tipo Grafo! 
Motivação 
6 
}  O objetivo da disciplina é, portanto, analisar as melhores 
alternativas para manipular eficientemente os dados 
de uma aplicação computacional. 
Algoritmos e Estruturas de Dados 
}  Algoritmo: 
}  Sequência de ações executáveis para a solução de um 
determinado tipo de problema 
}  Exemplo: “Receita de Bolo” 
}  Em geral, Algoritmos trabalham sobre… 
 
}  … Estruturas de dados 
}  Conjunto de dados que representa uma situação real 
}  Abstração da realidade 
}  Estruturas de Dados e Algoritmos estão intimamente ligados 
8 
Algoritmos e Estruturas de Dados 
Algoritmos Estruturas de Dados 
A escolha de uma estrutura de dados adequada 
pode simplificar a implementação do algoritmo para 
um dado problema 
Representação dos Dados 
}  Dados podem estar representados (estruturados) de 
diferentes maneiras 
}  Normalmente, a escolha da representação é determinada 
pelas operações que serão utilizadas sobre eles 
}  Exemplo: Números inteiros 
}  Representação por palitinhos: II + IIII = IIIIII 
}  Boa para pequenos números (operação simples) 
 
}  Representação decimal: 1278 + 321 = 1599 
}  Boa para números maiores (operação complexa) 
 
 
Abstração e Tipos Abstratos de Dados 
10 
11 
Abstração e Tipos Abstratos de Dados 
}  Abstração: 
Copyritght 1991 © Grady Booch 
12 
Abstração e Tipos Abstratos de Dados 
}  Definição de Abstração: 
“Uma abstração é uma visualização ou 
uma representação de uma entidade que 
inclui somente os atributos de 
importância em um contexto 
particular.” 
[Robert Sebesta] 
13 
Abstração e Tipos Abstratos de Dados 
Exemplos de Abstrações: Abstração para o mundo 
14 
Abstração e Tipos Abstratos de Dados 
Exemplos de Abstrações: 
Abstrações para prédios 
15 
Abstração e Tipos Abstratos de Dados 
}  Abstração: 
}  Técnica utilizada para dominar a complexidade do mundo real, 
permitindo-nos modelar uma entidade ou conceito deste 
mundo de forma simplificada... 
}  ... focando apenas no que é interessante para resolver 
o problema. 
16 
Abstração e Tipos Abstratos de Dados 
}  Abstração em programação: 
}  Abstração de processos: 
}  Dividimos um programa em subprogramas (funções) menores e 
mais fáceis de escrever e compreender ("dividir para conquistar"). 
}  Para usar um subprograma escrito por terceiros abstraímos a sua 
implementação e nos concentramos na sua interface. 
}  Abstração de dados: 
}  Serve para representarmos entidades reais do domínio do problema 
numa linguagem de programação, identificando as propriedades destas 
entidades que interessam ao sistema bem como suas operações. 
17 
Abstração de Processos 
}  Quem usa as funções abaixo interessa-se por: 
}  Saber quantos são os parâmetros para as funções chamadas e 
em que ordem são passados 
}  Saber quais os tipos dos parâmetros 
}  Saber os tipos dos dados que as funções retornam 
}  Saber o significado desse dado retornado 
int main() { 
 char valor[] = "4"; 
 int num; 
 num = atoi(valor); 
 printf("%f", sqrt(num)); 
} 
18 
Abstração de Dados 
}  Define-se uma estrutura e operações para um novo tipo: 
typedef struct st_stack { 
 int top; 
 float data[MAX]; 
} stack; 
 
stack* newstack (int) {...} 
int push (stack *, float) {...} 
int pop (stack *, float *) {...} 
int isempty (stack) {...} 
int top (stack, float*) {...} 
int destroy (stack *) {...} 
 
Tipos Abstratos de Dados (TADs) 
19 
}  Um Tipo Abstrato de Dados (TAD) é um modelo de 
estrutura de dados que especifica: 
}  O tipo dos dados armazenados; 
}  As operações definidas sobre esses dados; 
}  Os tipos de parâmetros dessas operações 
TAD = encapsula dados + operações 
Tipos Abstratos de Dados (TADs) 
20 
}  Características de um TAD: 
}  Conceito matemático básico que define o tipo de dado; 
}  Define O QUE cada operação faz, não como faz. 
}  Não se relaciona com detalhes de implementação; 
}  Não se preocupa com eficiência de espaço e tempo, pois estas 
são questões de implementação; 
}  Estrutura de Dados: é um método particular para 
implementar um TAD em uma LP. 
Algoritmos e Estrutura de 
Dados I 
Ex: Lista de números inteiros 
}  Operações 
}  Faz Lista Vazia 
}  Insere número no começo da lista 
}  Remove de uma posição i 
20 13 02 30 Implementação por Vetores: 
void Insere(int x, Lista L) { 
 for(i=0;...) {...} 
 L[0] = x; 
} 
20 13 02 30 
Implementação por Listas Encadeadas 
void Insere(int x, Lista L) { 
 p = CriaNovaCelula(x); 
 L^.primeiro = p; 
 ... 
} 
Programa usuário do TAD: 
int main() { 
 Lista L; 
 int x; 
 
 x = 20; 
 
FazListaVazia(L); 
 Insere(x,L); 
 ... 
} 
22 
Operações em TADs 
}  Operações típicas de TADs: 
1.  Criação de um TAD; 
2.  Inclusões e remoções de dados no TAD; 
3.  Percurso no TAD (varre todos os dados armazenados); 
4.  Busca (busca algum dado dentro da estrutura). 
Implementação de TADs 
}  Em Linguagens OO (C++, Java) a implementação de 
TADs é feita através de classes 
}  Em Linguagens estruturadas (C, pascal) a 
implementação é feita pela definição de tipos 
juntamente com a implementação de funções 
24 
Tipos Abstratos de Dados 
}  Um TAD pilha implementado em C como um array: 
typedef struct st_pilha { 
 int topo; 
 float dados[MAX]; 
} pilha; 
 
void cria_pilha (pilha *){...} 
int empilha (pilha *, float) {...} 
int desempilha (pilha *, float *) {...} 
int ta_vazia (pilha) {...} 
int topo (pilha, float*) {...} 
int limpa (pilha *) {...} 
 
Representação ou estrutura 
do TAD pilha 
Operações do TAD pilha 
25 
Tipos Abstratos de Dados 
}  Um cliente para o TAD pilha: 
int main() { 
 pilha p; 
 float x; 
 
 cria_pilha(&p); 
 if (ta_vazia(p)) { 
 empilha(&p, 1.2f); 
 empilha(&p, 3.0f); 
 } 
 topo(&p, &x); 
 if (x == 3.0f) 
 desempilha (&p, &y); 
 limpe (&p); 
} 
Em respeito ao encapsulamento, 
não há acessos à representação 
da pilha nos clientes, mas apenas às 
suas operações. 
26 
Tipos Abstratos de Dados 
}  A implementação muda para lista encadeada: 
typedef struct st_pilha { 
 float dado; 
 struct st_pilha *prox; 
} nopilha; 
typedef nopilha* pilha; 
 
void cria_pilha (pilha *){...} 
int empilha (pilha *, float) {...} 
int desempilha (pilha *, float *) {...} 
int ta_vazia (pilha) {...} 
int topo (pilha, float*) {...} 
int limpa (pilha *) {...} 
 
E a implementação 
das operações 
Modifica-se 
a representação do TAD 
27 
Tipos Abstratos de Dados 
}  O cliente, no entanto, não se altera: 
int main() { 
 pilha p; 
 float x; 
 
 cria_pilha(&p); 
 if (ta_vazia(p)) { 
 empilha(&p, 1.2f); 
 empilha(&p, 3.0f); 
 } 
 topo(&p, &x); 
 if (x == 3.0f) 
 desempilha (&p, &y); 
 limpe (&p); 
} 
28 
Tipos Abstratos de Dados 
}  Entretanto, se o encapsulamentofosse violado... 
int main() { 
 pilha p; 
 float x; 
 
 cria_pilha(&p); 
 if (p.topo == -1) { 
 empilha(&p, 1.2f); 
 empilha(&p, 3.0f); 
 } 
 x = p.dados[p.topo]; 
 if (x == 3.0f) 
 desempilha (&p, &y); 
 limpe (&p); 
} 
Acessos à estrutura do TAD 
violam o encapsulamento e 
aumentam o acoplamento 
entre o TAD e seus clientes 
Estes acessos à representação 
do TAD são específicos para a 
implementação com arranjos. 
Não servem para a nova 
implementação com lista! 
29 
Tipos Abstratos de Dados 
}  O conjunto de operações públicas que um TAD oferece é 
chamado de Interface do TAD. 
}  Mudanças nos clientes só são necessárias se interface for 
modificada 
30 
Tipos Abstratos de Dados 
}  Suporte para TADs em C: 
}  C permite que se implementem TADs em módulos. 
}  Arquivo de cabecalho (extensão .h): 
}  Define tipo e os protótipos das funções. 
}  Arquivo de programa (extensão .c): 
}  Implementa as operações 
 
}  O encapsulamento de C é limitado 
}  Clientes podem acessar os campos da estrutura do tipo. 
31 
Exemplo de um módulo pilha em C 
}  Arquivo de cabeçallho (pilha.h): 
#define MAX 100 
 
typedef struct st_pilha { 
 int topo; 
 float dados[MAX]; 
} pilha; 
 
// protótipos das funções 
void cria_pilha (pilha *); 
int empilha (pilha *, float); 
int desempilha (pilha *, float *); 
int ta_vazia (pilha); 
int topo (pilha, float*); 
int limpa (pilha *); 
32 
Exemplo de um módulo pilha em C 
}  Arquivo de programa (pilha.c): 
#include "pilha.h" 
 
void cria_pilha (pilha *p) { 
 ... 
} 
 
int empilha (pilha *p, float e) { 
 ... 
} 
 
... //outras funções 
33 
Tipos Abstratos de Dados 
}  Suporte para TADs em Java e C++: 
}  Implementa TADs usando classes (arquivo .java ou .cpp). 
}  Encapsula dados + operações 
}  Pode-se controlar o nível de acesso aos atributos da 
estrutrura de dados 
34 
Exemplo de classe Pilha em Java 
public class Pilha { 
 private int topo; 
 private float[] dados; 
 
 public void empilha (float e) { 
 ... 
 } 
 
 public float desempilha() { 
 ... 
 } 
 ... // outros métodos 
 
} //fim da classe 
35 
Exemplo de classe Pilha em C++ 
class Pilha { 
 private: 
 int topo; 
 float dados[MAX]; 
 public: 
 void empilha (float e) { 
 ... 
 } 
 
 float desempilha() { 
 ... 
 } 
 ... // outros métodos 
} //fim da classe 
36 
Tipos Abstratos de Dados 
}  Benefícios da programação com TADs: 
}  Organiza programa em unidades lógicas 
}  Podem ser compiladas e mantidas em separado. 
}  Encapsulamento 
}  Promove a independência entre o TAD e seus clientes. 
}  Aumento da confiabilidade 
}  Clientes não têm acesso direto à representação do TAD, a não ser 
por suas operações. 
37 
}  Tiago Maritan 
}  tiago@ci.ufpb.br 
Universidade Federal da Paraíba 
Centro de Informática 
Departamento de Informática 
Estrutura de Dados 
Introdução às ED