Informatica

UNIPAC
Universidade Presidente Antônio Carlos
Bacharelado em Ciência da Computação

Estruturas de Dados I
Material de Apoio
Parte V

Profª. Lívia Márcia Silva [e-mail] 2º sem / 2014

Tipos abstratos de Dados

• Dados: são abstrações da realidade, para a qual se conhece um modelo conceitual (físico-matemático), que permite transformá-los numa informação útil.
• Processamento: sequência finita e organizada de operações sobre os dados.
• Informação: Resultado do processamento dos dados, gerada como saída.
125

Tipos abstratos de Dados
• Um tipo de dado refere-se ao conjunto de valores a que uma constante pertence, ou que podem ser assumidos por uma variável ou expressão, ou que podem ser retornados por uma função (Wirth, 1976).
• Um Tipo Abstrato de Dados (TAD) pode ser visto como um modelo matemático acompanhado das operações definidas sobre o modelo, independente de qualquer linguagem de programação (Ziviani, 2005).
• Exemplo: o conjunto dos números inteiros acompanhado das operações aritméticas fundamentais forma um exemplo de um tipo abstrato de dados.
126

Tipos abstratos de Dados
• TAD podem ser considerados generalizações de tipos primitivos de dados.
• Da mesma forma que uma função é usada para encapsular partes de um algoritmo, o tipo abstrato de dados pode ser usado para encapsular tipos de dados.

127

Tipos abstratos de Dados
• Tipos abstratos de dados são extensivamente utilizados como base para o projeto de algoritmos.
• A definição do tipo e todas as operações definidas sobre o tipo podem ser localizadas numa única seção do programa.
TAD = Estrutura de Dados + Operações

128

Exemplos
• TADs mais comuns e utilizados:
–
–
–
–

Listas lineares
Filas
Pilhas
Árvores

129

Estrutura de Dados – Listas Lineares
•

Uma lista linear é uma sequência de n elementos de um tipo de dado: x1, x2, x3, ..., xn cuja propriedade estrutural envolve as posições relativas de