Tad Complex

Prévia do material em texto

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 bem-
definidas 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 bem-
definida é 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 programa-
fonte 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
	Estrutura de Dados – Básica
	Aula 6: Tipos Abstratos de Dados
	Tratando os Problemas
	Propriedades dos Tipos Abstratos de Dados
	A importância de encapsular a estrutura de dados
	Criando TAD complex em linguagem C
	Utilizando o TAD complex
	Implementando o TAD complex com classes da linguagem C++
	Tipos de dados abstratos genéricos
	Pré-condições e Pós-condições
	Exercícios