Tipos Abstratos de Dados e suas Características

Estrutura de dados Tipos abstratos de dados Corresponde a uma estruturação conceitual dos dados e reflete o relacionamento lógico entre dados conforme contexto estudado Conjunto de tipos de dados Operações a serem realizadas Tipo Abstrato de Dados ou TAD Tipo abstrato de dados Uma tipo abstrato de dados TAD é uma forma de definir novo tipo de dados juntamente com as operações que manipulam esse novo tipo de dado Conjunto de tipos de dados Operações a serem realizadas Tipo Abstrato de Dados ou TAD TADs São características dos tipos abstratos de dados 1 Separação entre o conceito definição do tipo e a implementação das operações 2 Visibilidade da estrutura interna do tipo fica limitada às operações 3 Aplicações que usam o TAD são denominadas clientes do tipo de dado 4 Clientes tem acesso somente à forma abstrata do TAD Resumindo O TAD estabelece o conceito de tipo de dado separado da sua representação e é definido como um modelo matemático por meio de um par v o em que v é um conjunto de valores e o é um conjunto de operações sobre esses valores TADs Uma vantagem em linguagens estruturadas da construção de TADs é a possibilidade de reuso de código fonte Maior abstração Menor abstração Imagine um conjunto Pense em um conjunto qualquer o conceito matemático mesmo e responda que dados e que operações podem ser definidas para esse ente conceitual P a e i o u 1 Verificar se um elemento pertence ao conjunto P a e i o u 1 Verificar se um elemento pertence ao conjunto 2 Retirar um elemento do conjunto 3 Contar quantos elementos esse conjunto possui 4 Determinar a interseção com outro conjunto 5 Determinar a união com outro conjunto 6 e outras tantas expressões que poderiam ser definidas Resumindo O TAD estabelece o conceito de tipo de dado separado da sua representação e é definido como um modelo matemático por meio de um par v o em que v é um conjunto de valores e o é um conjunto de operações sobre esses valores O TAD número real Dados 𝑥 ℝ Operações O TAD número real Em relação aos números reais ℝ números reais podem ser considerados os dados e as operações envolvem operações aritméticas e lógicas envolvendo esses números O TAD polígono Dados vértices Operações calcular área e perímetro O TAD polígono Nos polígonos os vértices são dados e as operações envolvem manipulações desses dados calcular área calcular perímetro etc Frações typedef struct int numerador int denominador Fracao O TAD Tipo Abstrato de Dados Fração representa um número fracionário composto por um numerador e um denominador Em C uma fração poderia ser implementada utilizando uma struct Na implementação das operações vamos considerar essa estrutura struct Frações typedef struct int numerador int denominador Fracao O TAD Tipo Abstrato de Dados Fração representa um número fracionário composto por um numerador e um denominador Em C uma fração poderia ser implementada utilizando uma struct Fração numerador denominador O TAD Tipo Abstrato de Dados Fração representa um número fracionário composto por um numerador e um denominador Para implementar um TAD Fração devese considerar uma série de operações que são comuns ao trabalhar com frações Uma possibilidade está indicada a seguir Frações 1 Criar fração 2 Somar e subtrair frações 3 Multiplicar e dividir frações 4 Simplificar fração 5 Converter fração para número decimal 6 Exibir fração 7 Comparar frações 8 Converter fração em número decimal 9 Calcular potência e raiz de fração Essas são algumas das operações comuns que você pode implementar em um TAD Fração Frações Criar Fração Função para criar uma fração a partir de um numerador e um denominador passados por valor Nessa função seria importante verificar se o denominador é diferente de zero outra possibilidade seria uma função para verificar a consistência include stdioh include fracaoh Fracao criarFracaoint numerador int denominador Fracao f fnumerador numerador fdenominador denominador return f Frações Simplificar fração Função para simplificar fração passada como parâmetro Por exemplo simplificando a fração 1220 obtemos 35 Veja com atenção 12 20 12 4 20 4 3 5 No caso 4 é o máximo divisor comum entre numerador e denominador da fração Função para calcular o máximo divisor comum MDC de dois números int mdcint a int b while b 0 int temp b b a b a temp return a Função para simplificar uma fração Fracao simplificarFracaoFracao f int gcd mdcfnumerador fdenominador fnumerador gcd fdenominador gcd return f Frações Somar fração Função para somar duas frações passadas como parâmetro Veja como pode ser realizada a soma das frações 56 e 49 5 6 4 9 5 9 4 6 6 9 45 24 54 69 54 69 3 54 3 23 18 Essa é uma alternativa para não ter que criar uma função para determinar o mínimo múltiplo comum dos denominadores Função para somar duas frações Fracao somarFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador bnumerador adenominador resultadodenominador adenominador bdenominador resultado simplificarFracaoresultado return resultado Frações Subtrair frações Função para subtrair duas frações passadas como parâmetro A seguir será realizada a subtração das frações 56 e 49 5 6 4 9 5 9 4 6 6 9 45 24 54 21 54 21 3 54 3 7 18 Essa é uma alternativa para não ter que criar uma função para determinar o mínimo múltiplo comum dos denominadores Função para subtrair duas frações Fracao subtrairFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador bnumerador adenominador resultadodenominador adenominador bdenominador resultado simplificarFracaoresultado return resultado Frações Multiplicar frações Função para multiplicar duas frações passadas como parâmetro A seguir será realizada a multiplicação das frações 57 e 2120 5 7 21 20 5 21 7 20 105 140 105 35 140 35 3 4 Note que na multiplicação de frações o resultado é uma fração em que o numerador é o produto dos numeradores e o denominador é o produto dos denominadores Função para multiplicar duas frações Fracao multiplicarFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bnumerador resultadodenominador adenominador bdenominador resultado simplificarFracaoresultado return resultado Frações Dividir frações Função para dividir duas frações passadas como parâmetro A seguir será realizada a divisão da fração 57 por 2120 5 7 21 20 5 7 20 21 5 20 7 21 100 147 Na divisão entre frações devese multiplicar a primeira fração pelo inverso da segunda fração Função para dividir duas frações Fracao dividirFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador resultadodenominador adenominador bnumerador resultado simplificarFracaoresultado return resultado Como você faria para implementar essa função utilizando a função multiplicarFração Frações Converter fração Função para devolver a representação decimal de uma fração Nesse caso é importante lembrar que fração é o resultado do quociente do numerador pelo denominador 5 7 5 7 0714286 Para implementar essa função devese observar que o resultado pode não ser inteiro Função para dividir duas frações float converterFracaoFracao f return fnumeradorfdenominador ArquivoÚnicoc ou fraçãoh fraçãoc mainc Para compilar no prompt de comando devese digitar gcc fracaoc mainc o fracaoexe A seguir para executar digite fracaoexe ou fracao fracaoh ifndef FRACAOH define FRACAOH typedef struct int numerador int denominador Fracao Fracao criarFracaoint numerador int denominador Fracao somarFracaoFracao a Fracao b Fracao subtrairFracaoFracao a Fracao b Fracao multiplicarFracaoFracao a Fracao b Fracao dividirFracaoFracao a Fracao b Fracao simplificarFracaoFracao f int mdcint a int b endif Essa diretiva significa if not defined se não definido e é usada para evitar a inclusão repetida de um arquivo de cabeçalho em um programa Funcionamento 1 Ao escrever ifndef FRACAOH é verificado se o símbolo FRACAOH não está definido antes 2 Se o FRACAOH não estiver definido o pré processador C define esse símbolo usando a diretiva define FRACAOH e o código entre ifndef e endif será incluído no programa 3 Se FRACAOH já estiver definido ou seja o arquivo de cabeçalho já foi incluído o código entre ifndef e endif será ignorado evitando a inclusão repetida fracaoc Nesse arquivo estarão as implementações das funções cujo escopo assinatura foram definidos no arquivo de cabeçalho fracaoh include stdioh include fracaoh Fracao criarFracaoint numerador int denominador Fracao f fnumerador numerador fdenominador denominador return f Função para somar duas frações Fracao somarFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador bnumerador adenominador resultadodenominador adenominador bdenominador return resultado Função para subtrair duas frações Fracao subtrairFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador bnumerador adenominador resultadodenominador adenominador bdenominador return resultado Função para multiplicar duas frações Fracao multiplicarFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bnumerador resultadodenominador adenominador bdenominador return resultado Função para dividir duas frações Fracao dividirFracaoFracao a Fracao b Fracao resultado resultadonumerador anumerador bdenominador resultadodenominador adenominador bnumerador return resultado Função para simplificar uma fração Fracao simplificarFracaoFracao f int gcd mdcfnumerador fdenominador fnumerador gcd fdenominador gcd return f Função para calcular o máximo divisor comum MDG de dois números int mdcint a int b while b 0 int temp b b a b a temp return a mainc Arquivo contendo a função principal main include stdioh include stdlibh include fracaoh int main Fracao f1 criarFracao1 2 Fracao f2 criarFracao3 4 Fracao soma somarFracaof1 f2 Fracao subtracao subtrairFracaof1 f2 Fracao multiplicacao multiplicarFracaof1 f2 Fracao divisao dividirFracaof1 f2 soma simplificarFracaosoma subtracao simplificarFracaosubtracao multiplicacao simplificarFracaomultiplicacao divisao simplificarFracaodivisao printfSoma dd somanumerador somadenominador printfSubtração dd subtracaonumerador subtracaodenominador printfMultiplicação dd multiplicacaonumerador multiplicacaodenominador printfDivisão dd divisaonumerador divisaodenominador systempause return 0 ArquivoÚnicoc ou fraçãoh fraçãoc mainc Para compilar no prompt de comando devese digitar gcc fracaoc mainc o fracaoexe A seguir para executar digite fracaoexe ou fracao Quais seriam os dados e as operações relacionadas ao TAD ponto no plano cartesiano Q01 Crie um TAD para manipular números complexos Q02 Crie um tipo abstrato de dados para manipular polígonos Q03