[INF1007] ResumoTAD

Prévia do material em texto

Programação II 
Monitor: André Vicente Pessanha 
Resumo TAD: 
 
*************************************************************************************************** 
 
OBS:​ Essa matéria só cai na P3! 
 
*************************************************************************************************** 
 
- Definição: 
 
Tipo Abstrato de Dado (TAD) é usado para criar um novo tipo que não existe em Prog! 
Exemplos de tipos conhecidos: int, float, struct, etc. 
Mas e o tipo "fração" existe? :O 
 
NÃO! Mas sabemos que uma fração é representada por uma divisão entre um numerador e 
um denominador, sendo ambos números inteiros e o denominador diferente de zero, né? 
EX: 2/3 
 
Então a partir desses dados podemos criar esse novo tipo abstrato! 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
- Como um TAD é organizado? (Programa Modularizado) 
 
Antes de se criar um TAD, é importantíssimo entender a forma como ele é organizado. 
>>TODO<< TAD é organizado/dividido em três módulos! 
 
OBS:​ Lembra que muitas vezes em Prog 1 era pedido pra fazer um Programa 
Modularizado? Mas naquela época, modularizado era simplesmente uma forma de 
organizar o programa em várias funções ao invés de fazer tudo junto na main! 
 
Na verdade, só agora em Prog 2 (Somente nessa matéria TAD!) vamos fazer um verdadeiro 
programa modularizado, ou seja, organizado em vários módulos! 
 
Um módulo do tipo "Header File" que contém os protótipos das funções e o typedef da 
struct e mais dois módulos do tipo "Source File". Um deles será o módulo de implementação 
das funções que foram definidas no Header File e o outro será o módulo do usuário do TAD. 
 
OBS:​ Pra facilitar o entendimento, recomendo abrir o Visual Studio em qualquer projeto. Dê 
uma olhada no menu "Solution Explorer" do canto esquerdo, não tem uma pasta chamada 
"Header File" e outra chamada "Source File"? 
 
São justamente esses os módulos que você vai criar no TAD! 
 
Source File é usado desde Prog 1, pois todo programa é obrigatório ter pelo menos um. 
Mas até então, nunca usamos Header File, um bom exemplo são os próprios #includes que 
fazemos. 
 
EX: #include <stdio.h> #include <stdlib.h> 
 
Todo protótipo desse tipo, terminado em >> .h << são módulos do tipo Header File! E cada 
um deles possui um conjunto de funções que >>NÃO<< fazemos a mínima ideia como 
foram implementadas! Por exemplo, sabemos e muito bem como se usa a função printf e 
scanf, ambas são do protótipo <stdio.h> , mas sabemos como foram implementadas? 
 
NÃO! É exatamente aí que está o conceito de TAD! Utilizamos funções que foram definidas 
e implementadas em outros módulos por outras pessoas! E o mais importante de tudo, sem 
poder alterar a forma como a função foi implementada! Só temos "permissão" para chamar 
a função! 
 
Na vida real cada módulo seria feito por uma pessoa diferente, seja numa empresa ou num 
grupo de programadores. Por exemplo, uma empresa quer desenvolver um programa super 
avançado com infinitas linhas de código. (Algo que levaria anos pra qualquer um fazer 
sozinho. x.x) 
 
Por ser um programa enorme (E também por questões de segurança) o programa é dividido 
em módulos, pequenos pedaços, em que cada programador fará uma pequena parte! 
Imagina que você é contratado só pra fazer a implementação das funções que serão 
necessárias para o TAD e após a conclusão, um outro programador vai utilizar essas 
funções que você implementou pra fazer uma outra parte do programa (Sem ter acesso à 
implementação que você fez! Só podendo chamar as funções!) e assim por diante. 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
Regras importantes: 
 
- Módulo de Interface do TAD: (Header File) 
 
Esse módulo contém todas os protótipos de funções (Nome, tipo de retorno e parâmetros), 
assim como o typedef da struct que representa o TAD. 
 
OBS:​ Esse é o mais tranquilo de todos, possibilidade nula de errar! Normalmente o 
enunciado da prova já te diz quais funções que serão necessárias pro TAD, então é só 
colocar os protótipos e o typedef! 
 
OBS2: ​Recomendo dar um nome pro módulo que seja compatível com o tipo do TAD! 
Ex: Se queremos fazer um TAD de fração, chamamos esse módulo de: >> fracao.h << 
Não faz sentido nenhum chamarmos de pombo.h né? :D 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
- Módulo de Implementação: (Source File) 
 
Nesse módulo fazemos a implementação de todas as funções do TAD! (Obrigatoriamente 
todas as funções em que definimos o protótipo no Módulo de Interface!) 
 
OBS:​ Imagina como se esse fosse o Módulo do "Administrador", ou seja,>>SOMENTE<< 
nesse módulo podemos acessar o conteúdo de variáveis de struct com a "setinha", usar 
alocação dinâmica, etc. 
 
OBS2: ​Nesse módulo também colocamos todos os #includes necessários, mas só de 
acordo com a necessidade! (Sim, vão tirar décimos se colocar sem motivo, cuidado!) 
Então só vamos adicionar #include <stdlib.h> por exemplo, se realmente for necessário usar 
alocação dinâmica ou utilizar a macro >NULL< que também está definido na <stdlib.h> 
 
E além disso, >>NUNCA<< podemos esquecer de colocar o protótipo do módulo de 
Interface que acabamos de criar como uma forma de "interligar" os módulos e também 
como prevenção de erro! Pois se caso colocarmos um parâmetro de função errado, o visual 
studio já vai avisar que o parâmetro >>NÃO<< está compatível com o protótipo da função 
definido no Módulo de Interface! 
 
Ex: #include "fracao.h" 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
- Módulo de Usuário do TAD: (Source File) 
 
Esse módulo contém o desenvolvimento do programa. A main >>SEMPRE<< fica nesse 
módulo e o usuário do TAD >> SÓ << tem "Permissão" pra chamar as funções do TAD! Ou 
seja, nem adianta tentar acessar conteúdo de variáveis de struct com a setinha ou fazer 
atribuições nos dados pertencentes ao TAD, pois não vai funcionar! O objetivo é fazer o que 
está sendo pedido no enunciado através das funções do próprio TAD! 
 
OBS: ​Assim como no módulo de implementação, aqui também precisamos adicionar o 
protótipo do Módulo de Interface do TAD! EX: #include "fracao.h" 
 
OBS2:​ Podemos incluir qualquer protótipo que já foi definido anteriormente no Módulo de 
Implementação com as aspas também! 
 
EX: #include "stdio.h" 
 
As aspas são justamente pra informar o Visual Studio que esse protótipo já foi definido em 
outro módulo. Mas isso é opcional, pode continuar usando < > nos #includes, >>Menos<< 
no protótipo do Módulo de Interface que é >>Sempre<< com aspas! 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
- Como se cria um TAD? 
 
Vamos usar o exemplo do TAD fração que citei no começo desse resumo: 
 
Normalmente esse tipo de questão na prova é dividido em três itens, cada um referente a 
um módulo do TAD e além disso você também precisa dar um nome para cada módulo! 
 
O primeiro item pede pra você criar o módulo de Interface do TAD Fração e diz quais são as 
funções necessárias. 
 
OBS: ​Em algumas provas (2014.1 por exemplo) o enunciado não cita as funções 
necessárias e pede pra você (Sim, você mesmo!) decidir e criar do zero as funções 
importantes para o TAD. Nesse caso, eu recomendo logo de cara já implementar as 
funções mais genéricas como: Criar, exibir, liberar e de acordo com o que for pedido pra 
fazer no módulo do usuário, você volta no módulo de interface/implementação e acrescenta 
mais funções! 
 
- Módulo de Interface: 
 
Primeiro passo é dar um nome para esse módulo, se é um TADde fração, um nome ideal 
seria: >> fracao.h << 
 
Segundo passo é organizar a typedef: 
 
typedef struct fracao Fracao; 
 
OBS:​ Aqui ainda >NÃO< temos a struct, somente o typedef, que será usado nos outros 
módulos! 
 
Agora vamos criar os protótipos das funções necessárias de acordo com a informação do 
enunciado: 
 
- Criar uma nova fração alocada dinamicamente a partir de um numerador e denominador 
recebidos como parâmetro: 
 
Fracao * cria_fracao (int num, int den); 
 
OBS: ​Sabemos que o tipo de retorno é > Fracao * < porque foi mencionado no enunciado 
que será usado Alocação Dinâmica! 
 
- Exibir a Fração: 
 
void exibe_fracao (Fracao * f); 
 
- Acessa o Numerador da fração: 
 
int acessaNum (Fracao *f); 
 
- Acessa o Denominador da fração: 
 
int acessaDen (Fracao *f); 
 
OBS: Quando o enunciado diz "Acessa", é pra você retornar o que é pedido na função! 
 
- Libera uma Fração recebida como parâmetro: 
 
void libera_fracao (Fracao * f); 
 
- Comparar duas frações, retornando 1 se a primeira é maior que a segunda, -1 se for 
menor ou zero se forem iguais: 
 
int compara_fracao (Fracao *f1, Fracao *f2); 
 
OBS:​ Aqui não tem erro, se já falaram que é usado alocação dinâmica, já sabemos que 
qualquer função que manipula o TAD vai receber um ponteiro para struct fracao, seja pra 
exibir ou liberar! 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
Em outro item, o enunciado pede pra você fazer a implementação das funções que você 
citou no módulo de Interface. 
 
- Módulo de implementação: 
 
Primeiro passo é dar um nome ao módulo: 
 
Bom, se o TAD é sobre o tipo fração > fracao.c < é uma ótima opção de nome! :) 
 
Segundo passo é colocar os #includes (Somente os que forem necessários!) 
 
#include <stdio.h> 
#include <stdlib.h> 
#include "fracao.h" 
 
OBS: ​Em algumas provas antigas pedem pra justificar cada um dos protótipos que você 
incluiu. É só citar exemplos óbvios, por exemplo: <stdio.h> por causa da função printf ou 
scanf. <stdlib.h> por causa da função malloc na alocação dinâmica, etc. 
Mas >>NUNCA<< se esqueça de sempre incluir o seu módulo de interface! 
 
OBS2​: Não sai incluindo todos os protótipos não! Somente os necessários! E sim, podem 
tirar décimos disso! :( 
O ideal é sempre deixar uma margem de espaço pra incluir outros protótipos se precisar. 
 
Terceiro passo é implementar a struct e as funções: 
 
struct fracao{ 
 int num, den; 
}; 
 
OBS:​ >>NÃO<< colocamos nenhum typedef aqui, pois ele já está no módulo de interface! 
 
Fracao * cria_fracao (int n, int d){ 
 Fracao * novo; 
 
 novo = (Fracao *) malloc (sizeof(Fracao)); 
 if(!novo) return NULL; 
 novo->num = n; 
 novo->den = d; 
 return novo; 
} 
 
OBS:​ Notou o uso do typedef Fracao? Mesmo ele não estando definido nesse módulo! 
#include "fracao.h" as aspas servem pra avisar o Visual Studio que a definição de algumas 
funções ou typedefs foram feitas em outro módulo! 
 
void exibe_fracao (Fracao *f){ 
 printf(" %d/%d\n", f->num, f->den); 
} 
 
void libera_fracao (Fracao *f){ 
 free(f); 
} 
 
int acessaNum (Fracao *f){ 
 return f->num; 
} 
 
int acessaDen (Fracao *f){ 
 return f->den; 
} 
 
int compara_fracao (Fracao *f1, Fracao *f2){ 
 float div, div2; 
 
 div = (float) f1->num / f1->den; 
 div2 = (float) f2->num / f2->den; 
 if(div > div2) return 1; 
 else if(div < div2) return -1; 
 return 0; 
} 
 
OBS:​ Como o resultado da divisão pode não ser exata, uma boa forma de comparar frações 
é convertendo o resultado da divisão para decimal, através do typecast (float). 
 
OBS2:​ Notou que nesse módulo podemos usar livremente tudo que aprendemos em prog? 
Sem restrições! Alocação dinâmica, atribuir valores, acessar contéudo de variáveis na 
struct, etc. 
 
-------------------------------------//---------------------------------------- 
 
E pra fechar, no último item o enunciado pede pra você criar duas frações, exibir as frações 
em que o numerador é maior que o denominador e por fim, comparar as frações. 
 
-​ Módulo do Usuário: 
 
Pra variar o primeiro passo é dar um nome ao módulo, como esse módulo pertence ao 
usuário do TAD, seria interessante chamar ele de > usafracao.c < 
 
Segundo passo é colocar os #includes necessários: 
 
#include "stdio.h" 
#include "fracao.h" 
 
OBS: ​Lembra que já incluímos o stdio.h no módulo de implementação? Então aqui 
podemos usar aspas pra dizer que esse protótipo já foi definido em outro módulo ou 
simplesmente usar < > sem problemas! (Com exceção do "fracao.h"!) 
 
Terceiro passo é fazer tudo que foi pedido na >>Main<<! Pois já temos todas as funções 
necessárias nos outros módulos! 
 
 
 
 
 
 
int main (void){ 
 Fracao *f1, *f2; 
 int res; 
 
 f1 = cria_fracao (7, 3); 
 if(!f1) exit(1); 
 
 f2 = cria_fracao (3, 5); 
 if(!f2) exit(2); 
 
 if(acessaNum(f1) > acessaDen(f1)) exibe_fracao(f1); 
 if(acessaNum (f2) > acessaDen(f2)) exibe_fracao(f2); 
 
 res = compara_fracao (f1, f2); 
 if(res < 0) puts("O primeiro eh menor que o segundo!"); 
 else if(res > 0) puts("O primeiro eh maior que o segundo!"); 
 else puts("Sao iguais!"); 
 
 libera_fracao (f1); 
 libera_fracao (f2); 
 return 0; 
} 
 
OBS:​ Percebeu que não incluí o protótipo <stdlib.h>? :) 
 
Somente porque no teste se f1 era NULL ou não, eu usei a forma que sempre venho 
recomendando. Pois if(!f1) é o mesmo que if(f1 == NULL) 
Mas como NULL é um macro que está definido na stdlib.h, seria obrigatório incluir esse 
protótipo se fizermos dessa outra forma! 
 
 
************************************************************************************************ 
 
Regra Importante: 
 
No módulo do Usuário >>NÃO<< podemos acessar o conteúdo das variáveis da struct com 
a "Setinha" e nem manipular qualquer dado que pertença ao TAD! (Atribuir, comparar, etc) 
 
Ex: Não podemos acessar o conteúdo do numerador dessa forma: f1->num; 
Somente dessa forma: acessaNum(f1) 
 
A >>ÚNICA<< forma é através das funções que foram criadas nos outros módulos! 
 
OBS:​ Só podemos no máximo, criar variáveis e pedir pro usuário digitar valores que serão 
enviados como parâmetro nas funções do TAD. 
 
Ex: puts("Numerador e Denominador: "); 
 scanf("%d%d", &n, &d); 
 
OBS:​ Recomendo sempre colocar manualmente valores nos parâmetros. 
EX: f1 = cria_fracao (7, 3); 
 
Não vale a pena perder tempo colocando mensagem pro usuário digitar e armazenando um 
por um. (A não ser que o enunciado peça!) 
 
 
*********************************************************************************************** 
 
OBS: ​Essa matéria costuma ser cobrada sempre numa questão com 3 itens e é sempre 
algo tranquilo e intuitivo, sendo bem raro misturarem com outras matérias. 
 
Desconsidere as G2 antigas que misturavam TAD com ordenação e busca binária! :)