Projeto 01 Matrizes Esparsas em C - Implementacao de TAD e Operacoes

25052023 A solucao do problema descrito neste documento deve ser entregue ate as 23h59min do dia 10062023 Leia atentamente as instrucoes abaixo Instrucoes Este trabalho deve ser implementado usando a linguagem de programacao C Coloque a solucao do projeto em uma pasta especıfica O seu trabalho deve ser compactado zip rar etc e enviado na atividade correspondenteao Projeto 01 Identifique o seu codigofonte colocando o nome e matrıcula como comentario no inıcio de seu codigo Indente corretamente o seu codigo para facilitar o entendimento Trabalhos com codigos maus indentados sofrerao reducao na nota As estruturas de dados devem ser implementadas como TAD usando classes como fizemos para as demais estruturas de dados programadas em aula Os programasfonte devem estar devidamente organizados e documentados Observacao Lembrese de desalocar os enderecos de memoria alocados quando os mesmos nao forem mais ser usados 1 Matrizes esparsas Projeto retirado do livro de Nivio Ziviani 1 11 Objetivos Concretizar os conceitos de listas simplesmente encadeadas atraves de uma aplicacao matrizes esparsas 12 Descricao Matrizes esparsas sao matrizes nas quais a maioria das posicoes e preenchida por zeros Para essas matrizes podemos economizar um espaco significativo de memoria se apenas os termos diferentes de zero forem armazenados As operacoes usuais sobre essas matrizes somar multiplicar inverter pivotar tambem podem ser feitas em tempo muito menor se nao armazenarmos as posicoes que contˆem zeros Ha numerosos exemplos de aplicacoes que exigem o processamento de matrizes espar sas Muitas se aplicam a problemas cientıficos ou de engenharia que so sao facilmente entendidos por peritos No entanto ha uma aplicacao muito familiar que usa matriz esparsa um programa de planilha como Excel Muito embora a matriz de uma planilha comum seja muito grande digamos 999 por 999 apenas uma porcao da matriz pode re almente estar sendo usada em um dado momento Planilhas usam a matriz para guardar formulas valores e strings associados a cada posicao Em uma matriz esparsa o armaze namento para cada elemento e alocado de um espaco de memoria livre heap conforme se torne necessario Embora apenas uma pequena porcao dos elementos esteja realmente sendo usada a matriz pode parecer muito grande maior do que o que normalmente ED PROJETO 25052023 caberia na memoria do computador Uma maneira eficiente de representar estruturas com tamanho variavel eou desco nhecido e com o emprego de alocacao encadeada utilizando listas Vamos usar essa repre sentacao para armazenar as matrizes esparsas Cada coluna da matriz sera representada por uma lista simplesmente encadeada circular com um no sentinela Da mesma maneira cada linha da matriz tambem sera representada por uma lista simplesmente encadeada circular com um no sentinela Cada no da estrutura alem dos nossentinela representara os termos diferentes de zero da matriz e devera ser como no codigo abaixo 1 struct Node 2 Node direita 3 Node abaixo 4 int linha 5 int coluna 6 double valor 7 O campo abaixo do struct Node deve ser usado para referenciar o proximo elemento diferente de zero na mesma coluna O campo direita deve ser usado para referenciar o proximo elemento diferente de zero na mesma linha Dada uma matriz A para um valor Ai j diferente de zero devera haver um no com o campo valor contendo Ai j o campo linha contendo i e o campo coluna contendo j Esse no devera pertencer a lista circular da linha i e tambem devera pertencer a lista circular da coluna j Ou seja 25052023 cada no pertencera a duas listas ao mesmo tempo As celulas da matriz sao indexadas a partir do numero 1 Logo 1 i linha e 1 j coluna Como exemplo considere a seguinte matriz esparsa 50 0 0 0 10 0 20 0 A 0 0 0 0 30 0 60 5 A representacao da matriz A pode ser vista na Figura 1 Figura 1 Exemplo de matriz esparsa Com essa representacao uma matriz esparsa m n com r elementos diferentes de zero gastara m n r 1 nos E bem verdade que cada no ocupa varios bytes na memoria no entanto o total de memoria usado sera menor do que as m n posicoes necessarias para representar a matriz toda desde que r seja suficientemente pequeno 25052023 13 TAD SparseMatrix O trabalho consiste em desenvolver em C uma classe chamada SparseMatrix com pelo menos as seguintes operacoes conforme esta especificacao SparseMatrixint m int n Construtor da classe Inicializa uma matriz esparsa vazia com capacidade para m linhas e n colunas Essa funcao deve checar se os valores passados sao validos se sao inteiros positivos ou seja m 0 e n 0 se nao forem uma excecao deve ser lancada O esquema de uma matriz esparsa vazia e ilustrado na Figura 2 Atencao Nao deve ser alocado arrays nesse trabalho apenas nos Alocacao de arrays de qualquer coisa que seja sera penalizado Figura 2 Esquema de uma matriz esparsa vazia SparseMatrix Destrutor Libera toda a memoria que foi alocada dinamicamente para a matriz void insertint i int j double value Esta funcaomembro faz o valor na celula i j da matriz ser igual a value onde i e a linha e j e a coluna Se ja houver um valor nessa posicao ele e atualizado para esse novo valor Essa funcao deve checar se os ındices i j passados por parˆametro sao validos se nao forem validos uma excecao deve ser lancada Atencao No caso em que o valor do argumento value for igual a zero a funcao deve desconsiderar e nao fazer nada neste caso Ou seja chamadas dessa funcao passando o valor 0 nao terao efeito algum double getint i int j Devolve o valor na celula i j da matriz onde i e a linha e j e a coluna Essa funcao deve checar se os ındices passados sao validos se nao forem validos uma excecao deve ser lancada 25052023 void print Esta funcao imprime a matriz A no terminal inclusive os elementos iguais a zero As funcoesmembro descritas acima sao necessarias para possibilitar o mınimo de funcionamento da matriz Se vocˆe identificar que precisa de funcoesmembro adicionais ou que precisa implementar funcoes auxiliares que facilitem a programacao da estrutura de dados SparseMatrix vocˆe tem liberdade para programalas 14 Arquivo maincpp Alem do TAD SparseMatrix vocˆe deve implementar trˆes funcoes adicionais no arquivo maincpp nao sao funcoesmembro da SparseMatrix sao funcoes externas a classe SparseMatrix readSparseMatrixstdstring nome do arquivo Essa funcao lˆe de um arquivo de entrada os elementos diferentes de zero de uma matriz esparsa e monta a estrutura especificada anteriormente devolvendo um pon teiro para a SparseMatrix alocada dinamicamente Considere que a primeira linha do arquivo de entrada consiste dos valores m e n numero de linhas e de colunas da matriz e as demais linhas do arquivo sao constituıdas de triplas i j valor para os elementos diferentes de zero da matriz Por exemplo para a matriz A anterior o conteudo do arquivo de entrada seria 4 4 1 1 500 2 1 100 2 3 200 4 1 300 4 3 600 4 4 50 Dica O C possui a biblioteca fstream que possibilita abrir arquivos ler e escrever neles de forma intuitiva muito parecida com a leitura e escrita usando cin e cout Pesquise sobre essa biblioteca em livros ou na internet Existem muitos livros de C que possuem um capıtulo exclusivo ensinando como ler e escrever em arquivostexto Ache o melhor livro que vocˆe puder e estude o tal capıtulo a fim de aprender como manipular arquivos usando o C ATENC AO As matrizes podem ter ate 30000 linhas e 30000 colunas SparseMatrix sumSparseMatrix A SparseMatrix B Essa funcao recebe como paraˆmetro as matrizes A e B devolvendo uma matriz C que e a soma de A e B SparseMatrix multiplySparseMatrix A SparseMatrix B Essa funcao recebe como paraˆmetro as matrizes A e B devolvendo uma matriz C que e a multiplicacao de A por B Observacao E obrigatorio o uso de alocacao dinˆamica de memoria para implementar as listas de adjacˆencia que representam as matrizes 25052023 Alem da matriz A outras matrizes podem ser lidas para testar os metodos como por exemplo 50 30 0 0 B 10 0 20 0 C 0 0 0 0 0 0 0 5 3 0 0 0 1 0 Observacao Desenvolva uma main interativa com menu ou com comandos fique a vontade para escolher o melhor formato porem nao esqueca de documentar os comandos no relatorio final para que eu tenha um lugar para saber quais comandos usar a fim de executar o seu programa com sucesso Uma possibilidade adicional e colocar um helper no seu programa a fim de disponibilizar no proprio programa uma listagem dos comandos que o usuario pode utilizar 15 O que deve ser submetido Devera ser submetido 1 Um relatorio do trabalho realizado contendo i a descricao completa da estrutura de dados que foi implementada suas aplicacoes e tudo o mais que sirva de motivacao ii as decisoes tomadas relativas aos casos e detalhes de especificacao que porventura estejam omissos no enunciado por exemplo se vocˆe precisar escrever funcoes auxiliares iii Uma secao descrevendo como o trabalho foi dividido entre a dupla se for o caso iv As dificuldades encontradas v Listagem dos testes executados vi O relatorio deve conter tambem uma analise da complexidade de pior caso das funcoes insert get e sum vii Referˆencias bibliograficas tutoriais vıdeos ou outros materiais consulta dos 2 O codigofonte devidamente organizado e documentado Alem disso os ar quivos das matrizes que foram utilizadas como teste Você pode desenvol ver diversos testes que ficam a criterio 3 Relatorio escrito em Latex 02 ponto extra O Latex e um programa de edicao de texto que tem uma linguagem de marcacao propria No Moodle eu coloquei links para minicursos de introducao ao Latex usando o Overleaf Acho que vale a pena ver 16 Comentarios Gerais Comece a fazer este trabalho logo enquanto o problema esta fresco na memoria e o prazo para terminalo esta tao longe quanto jamais podera estar Clareza identacao e comentarios no programa tambem vao valer pontos 25052023 O trabalho e individual Trabalhos copiados receberao nota ZERO Um dos parˆametros utilizados na avaliacao da qualidade de uma implementacao consiste na constatacao da presenca ou ausˆencia de comentarios Comente o seu codigo Mas tambem nao comente por comentar forneca bons comentarios Outro paraˆmetro de avaliacao de codigo e a portabilidade Dentre as diversas pre ocupacoes da portabilidade existe a tentativa de codificar programas que sejam compilaveis em qualquer sistema operacional Como testarei o seu codigo em uma maquina que roda Linux nao use bibliotecas que so existem para o sistema Windows como por exemplo a biblioteca conioh e outras tantas Obs Nao serao aceitos trabalhos submetidos apos o prazo final 88 996882146 obs meu whatsapp Referˆencias 1 N Ziviani F C Botelho Projeto de Algoritmos com implementacoes em Java e C Editora Cengage Learning 2006