Estrutura de Dados – Básica
Professor: Osvaldo Kotaro Takai.
Aula 6: Tipos Abstratos de Dados
O objetivo desta aula é introduzir os conceitos envolvidos em Tipos Abstratos de Dados e
explorar esses conceitos implementando-os com uma linguagem de programação orientada a
objetos.
Tratando os Problemas
A primeira coisa com a qual nos confrontamos quando escrevemos programas é o problema.
Normalmente, você é desafiado com problemas reais e você quer facilitar sua vida fornecendo
um programa para o problema. No entanto, problemas reais são nebulosos e a primeira coisa
que você faz é tentar entender o problema separando os detalhes necessários e descartando
os desnecessários: Você tenta obter sua própria visão abstrata, ou modelo, do problema. Este
processo de modelagem é chamado abstração e é ilustrado na figura abaixo.
O modelo define uma visão abstrata do problema. Isso implica que o modelo focaliza apenas
nos assuntos associados ao problema e para o qual você tenta definir as propriedades do
problema. Dentre essas propriedades estão: a) os dados que são afetados no problema, e b)
as operações que são identificadas no problema.
Como exemplo, considere a administração de empregados em uma instituição. O chefe da
administração pede que você crie um programa que permita administrar os empregados. Bem,
isso não é muito específico. Por exemplo, quais informações de empregados são necessárias
para a administração? Quais tarefas devem ser permitidas? Os empregados são pessoas reais
que podem ser caracterizados por várias propriedades, tais como:
•
•
•
•
•
•
•
•
nome,
altura,
data de nascimento,
foto,
número do rg,
número da sala,
cor do cabelo,
passatempo.
Certamente, nem todas estas propriedades não necessárias para resolver o problema da
administração. Apenas algumas são relevantes ao problema. Consequentemente, você cria um
1
modelo de um empregado para o problema. Este modelo apenas indica propriedades que são
necessárias para atender aos requisitos da administração, por exemplo, o nome, a data de
nascimento e o número do rg. Estas propriedades são chamadas “dados do modelo
(empregado)”. Agora você poderá que descrever as pessoas reais com a ajuda de um
empregado abstrato.
Naturalmente, uma mera descrição não será suficiente. Devem existir algumas operações para
que a administração esteja apta a manipular os empregados abstratos. Por exemplo, deve
existir uma operação que permita criar um novo empregado quando uma pessoa é contratada
pela instituição. Consequentemente, você terá que identificar as operações que permitam
manipular o empregado abstrato. Você também decide que os dados de empregados devem
ser acessados apenas pelas operações associadas. Isso irá garantir que os elementos de
dados sempre estejam num estado apropriado. Por exemplo, você terá condições de verificar
se uma data fornecida é válida.
Para resumir, a abstração é a estruturação de um problema nebuloso em entidades bemdefinidas através de seus dados e operações. Consequentemente, tais entidades combinam
dados e operações. Eles não estão desassociados.
Propriedades dos Tipos Abstratos de Dados
O exemplo anterior mostra que com a abstração você cria entidades bem-definidas e que
podem ser manipuladas apropriadamente. Essas entidades definem a estrutura de dados de
um conjunto de itens. Por exemplo, cada empregado administrado tem um nome, data de
nascimento e número do rg.
A estrutura de dados só pode ser acessada pelas operações definidas. Esse conjunto de
operações é chamado de interface e é exportado pela entidade. Uma entidade que tenha essas
propriedades descritas é chamada de tipo abstrato de dados (TAD).
A figura abaixo ilustra um TAD que consiste de uma estrutura de dados e operações. As
operações que são visíveis pelo lado de fora definem a interface.
Quando um novo empregado é “criado”, a estrutura de dados é preenchida com os valores
reais: Você agora tem uma instância de um empregado abstrato. Você pode criar quantas
instâncias de um empregado abstrato quanto forem necessárias para descrever todas as
pessoas realmente empregadas.
Vamos tentar colocar as características de um TAD de maneira mais formal:
Definição de Tipo Abstrato de Dados: Um tipo abstrato de dados (TAD) é caracterizado pelas
seguintes propriedades:
1. Ele exposta um tipo.
2. Ele exporta um conjunto de operações. Esse conjunto é chamado de interface.
3. As operações da interface são os únicos mecanismos de acesso à estrutura de dados
do tipo.
4. Axiomas e pré-condições definem o domínio da aplicação do tipo.
Com a primeira propriedade é possível criar mais do que uma instância de um TAD com
exemplificado no exemplo de empregado.
2
A importância de encapsular a estrutura de dados
O princípio de esconder a estrutura de dados utilizada e fornecer apenas uma interface bemdefinida é conhecido como encapsulamento. Por que é tão importante encapsular a estrutura
de dados?
Para responder a esta pergunta, considere o seguinte exemplo matemático onde queremos
definir um TAD para os números complexos. Para isso, é necessário apenas saber que os
números complexos consistem de duas partes: a parte real e a parte imaginária; ambas
representadas por números reais. Os números complexos definem várias operações: adição,
subtração, multiplicação e divisão, entre outras. Axiomas e pré-condições válidos são os
definidos pela matemática dos números complexos. Por exemplo, existe um elemento neutro
para a adição.
Para representar um número complexo é necessário definir a estrutura de dados utilizada pelo
TAD. Podemos pensar no mínimo em duas possibilidades para fazer isso:
•
As partes são armazenadas num vetor de duas posições, onde a primeira posição
guarda a parte real e a segunda a parte imaginária do número complexo. Se você
deseja obter a parte real em x e a parte imaginária em y, você acessar diretamente as
posições do vetor: x= c[0] e y = c[1].
•
As partes são armazenadas num registro com dois elementos. Se o nome do elemento
da parte real é r e a parte imaginária i, x e y podem ser obtidos fazendo: x = c.r e y =
c.i.
O terceiro item da definição de TAD diz que cada acesso à estrutura de dados deve possuir
uma operação definida. O exemplo de acesso exemplificado anteriormente parece ir contra a
este requisito. Isso é verdade?
Permita-nos verificar novamente as duas possibilidades de representar números complexos.
Vamos nos ater à parte real. Na primeira versão, x recebe c[0]. Na segunda versão, x recebe
c.r. Nos dois casos, x recebe “alguma coisa”. Essa “alguma coisa” varia de acordo com a
estrutura de dados utilizada. Mas em ambos os casos a operação realizada “recebe” possui o
mesmo significado: atribuir à variável x a parte real de um número complexo c; e nos dois
casos, esta semântica é alcançada.
Se você pensar em operações mais complexas o impacto de separar a estrutura de dados de
suas operações ficará mais evidente. Por exemplo, a adição de dois números complexos exige
que você realize uma adição para cada parte. Consequentemente, você deve acessar o valor
de cada parte que é diferente para cada versão. Ao fornecer uma operação “add” você pode
encapsular esses detalhes de quem for utilizá-la. Num contexto de uma aplicação, você
simplesmente “adiciona dois números complexos” sem pensar em como essa funcionalidade é
realmente executada.
Uma vez que você tenha criado um TAD para os números complexos, digamos complex, você
pode usá-lo da mesma forma que os tipos de dados bem-conhecidos, tais como o int, float,
entre outros.
Resumindo: A separação da estrutura de dados e operações, e a restrição de somente acessar
a estrutura de dados via um interface bem-definida, permitem que você escolha a estrutura de
dados mais apropriada para o problema que você está resolvendo.
Criando TAD complex em linguagem C
Imagine que a sua equipe precise desenvolver um sistema, em linguagem C, que faz uso
intenso de números complexos como, por exemplo, um sistema para controle do consumo de
energia elétrica. Após algumas discussões, a equipe decidiu que seria necessário criar uma
única biblioteca de funções que manipule números complexos, para facilitar o desenvolvimento
do sistema. A pessoa que ficou responsável para desenvolver tal biblioteca foi você.
A melhor forma de criar essa biblioteca é fazer uso dos conceitos de TAD. Infelizmente, a
linguagem C não possui mecanismos explícitos para criar um TAD. No entanto, você pode
implementar um TAD nesta linguagem criando 3 arquivos separados. O primeiro arquivo
(complexo.h) conterá as definições das interfaces (protótipos de funções) e a definição da
3
estrutura de dados. O segundo arquivo (complexo.c) conterá as implementações das interfaces
e das funções auxiliares (funções que não fazem parte da interface). O terceiro arquivo
(main.c) faz uso do TAD complex. Para implementar este exemplo em Dev-C++, crie um novo
projeto com o nome TAD complex e associe mais dois arquivos ao projeto além do main.c.
Veja a figura abaixo:
Em cada arquivo, inclua os códigos correspondentes descritos abaixo. Analise atentamente o
código contido nesses três arquivos:
Arquivo 1: complexo.h
Lembre-se que os arquivos com extensão “h” (h de header) são arquivos que devem conter
apenas as definições de tipos, constantes e cabeçalhos de funções. Este arquivo foi construído
tendo em mente que as funções set, add, sub, mult e notation são as únicas operações de
números complexos que a sua equipe irá precisar para construir o sistema; ou seja, todas as
interfaces do seu TAD complex.
Este arquivo deve ser distribuído à equipe juntamente com a biblioteca que ainda não foi
construída, mas a sua implementação encontra-se no arquivo complexo.c.
4
Arquivo 2: complexo.c
Note que o arquivo complexo.c acima é um programa normal em linguagem C. A única
diferença é que ele não possui a função principal (main). Nesse arquivo são implementadas
todas as operações, sejam de interface ou auxiliares (funções que auxiliam na implementação
das interfaces, no caso: getR() e getI()).
5
Para verificar se a sua biblioteca funciona, crie um programa que use a sua biblioteca, como
por exemplo, o programa main.c abaixo.
Arquivo 3: main.c
Este programa pode servir de exemplo para que a sua equipe saiba como utilizar a sua
biblioteca.
A seguinte saída será apresentada quando esse programa for executado:
Observe que após a compilação desse programa, o arquivo complexo.o foi criado no diretório
do projeto. Esse arquivo é o programa-objeto, versão em código binário do programa
complexo.c.
Agora, para concluir, distribua para a sua equipe os arquivos complexo.h e complexo.o como
sendo a biblioteca e o arquivo main.c como um programa que exemplifica a utilização dessa
biblioteca.
Note que você não distribuiu o arquivo complexo.c. Isso normalmente é feito para evitar que
alguém altere indevidamente a sua biblioteca.
Utilizando o TAD complex
Os membros de sua equipe podem fazer uso de sua biblioteca incluindo em seu programafonte o arquivo complexo.h (da mesma forma que foi feito no programa main.c), e indicando ao
compilador para linkeditar o arquvio.o fornecido. Isso é feito em Dev-C++ seguindo os
seguintes passos:
6
a) Crie um novo projeto, por exemplo: UsandoTADComplex e digite o programa que use o
TAD Complex.
b) Selecione a opção “Opções do Projeto” do menu Projeto.
c) Na aleta Parâmetros, pressione o botão “Adicionar”.
7
d) Navegue até o local onde o arquivo complexo.o foi copiado e selecione na caixa de
lista Arquivos do tipo: a extensão Object (*.o, *.obj).
e) Selecione o arquivo complexo.o e pressione o botão “Abrir”.
8
f)
Agora, o arquivo complexo.o será ligado pelo Dev-C++ quando o programa quando for
compilado.
Implementando o TAD complex com classes da linguagem C++
A linguagem C++ fornece melhores mecanismos para implementar um TAD. A intenção desta
seção não é apresentar todos os conceitos envolvidos na programação orientada a objetos. A
idéia aqui é simplesmente apresentar uma outra forma de implementar um TAD utilizando
alguns mecanismos da linguagem C++. Para maiores detalhes sobre a linguagem C++,
consulte http://www.cplusplus.com/doc/tutorial/index.html ou
http://oopweb.com/CPP/Files/CPP.html.
Arquivo 1: complexoOO.h
9
Arquivo 2: complexoOO.cpp
Arquivo 3: main.c
10
Tipos de dados abstratos genéricos
Este assunto será discutido na aula 8, quando for discutido a estrutura de dados Pilha.
Pré-condições e Pós-condições
As pré-condições e pós-condições permitem que o programador especifique as rotinas que ele
deve implementar.
Frequentemente o programador necessita comunicar precisamente o que uma rotina deve
realizar, sem qualquer indicação de como ela deve ser implementada.
Por exemplo, suponha que você seja o chefe de um grupo de programadores e você quer que
um dos programadores escreva uma função como parte de um projeto.
As pré-condições e pós-condições são declarações de requisitos de uma rotina. A declaração
da pré-condição indica o que deve ser verdadeiro antes que a rotina seja chamada. A
declaração da pós-condição indica o que deve ser verdade quando a rotina terminar o seu
trabalho. Por exemplo:
As pré-condições e pós-condições devem aparecer como comentários no seu programa e são
colocadas normalmente depois do cabeçalho de uma rotina. A pós-condição sempre indica
qual trabalho deve ser realizado pela rotina. Neste caso, quando a função finalizar, a raiz
quadrada de n deve ser retornada.
11
Note que ehVogal(‘A’) deve retornar 1 (verdadeiro); ehVogal(‘Z’) deve retornar 0 (falso); e
ehVogal(‘?’)? Ninguém sabe, pois a pré-condição está sendo violada. O programador que
chama a função é responsável por certificar que a pré-condição seja válida quando o
procedimento é chamado.
Por outro lado, programadores cuidadosos também seguem as seguintes regras:
•
Quando você escreve uma função, você deve detectar em quais condições uma précondição será violada.
•
Se você detectar que uma pré-condição foi violada, então imprima uma mensagem de
erro e aborte o programa.
12
Vantagens:
•
Descreve resumidamente o comportamento de uma função, sem entrar em detalhes de
implementação.
•
Posteriormente, você pode reimplementar a função de uma nova forma, entretanto, os
programas, os quais dependem exclusivamente da pré-condição e pós-condição,
continuarão a funcionar sem alterações.
Exercícios
Estenda as duas implementações do TAD complex com as seguintes operações:
a) Módulo de um número complexo.
b) Divisão de dois números complexos.
c) Verificar se dois números complexos são iguais. Retornar 1 se for igual e 0 caso
contrário.
13