Resumo_TAD

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

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 TAD de 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! :)