Matrizes Esparsas

[Leonardo C. Guimarães 0]

E ae galera tranquilo?primeira vez q visito o site....parece ser bom...jah cheguei com um probleminha...eh q tenho um trabalho e n sei como fazer....c der pra me ajudar eu agradeço...Matrizes Esparsas - Utilização de Listas Através de Apontadores (Árabe, 1992).Matrizes esparsas são matrizes nas quais a maioria das posições são preenchidas por zeros. Para estas matrizes, podemos economizar um espaço significativo de memória se apenas os termos diferentes de zero forem armazenados. As operações usuais sobre estas matrizes (somar, multiplicar, inverter, pivotar) também podem ser feitas em tempo muito menor se não armazenarmos as posições que contém zeros.Uma maneira eficiente de representar estruturas com tamanho variável e/ou desconhecido é através de alocação encadeada, utilizando listas. Vamos usar esta representação para armazenar as matrizes esparsas.Cada coluna da matriz será representada por uma lista linear circular com uma célula cabeça. Da mesma maneira, cada linha da matriz também será representada por uma lista linear circular com uma célula cabeça. Cada célila da estrutura, além das células-cabeça, representará os termos diferentes de zero da matriz e devem ter o seguinte tipo:typedef struct TipoCelula_st * Apontador;typedef struct TipoCelula_st { Apontador Direita, Abaixo; int Linha, Coluna; float Valor;} TipoCelula;O campo Abaixo deve ser usado para apontar o próximo elemento diferente de zero na mesma coluna. O campo Direita deve ser usado para apontar o próximo elemento diferente de zero na mesma linha. Dada uma matriz A, para o valor A(i,j) diferente de zero, deverá haver uma célula com o campo Valor contendo A(i,j), o campo Linha contendo i e o campo Coluna contendo j. Esta célula deverá pertencer à lista circular da linha i e também deverá pertencer à lista circular da coluna j. Ou seja, cada célula pertencerá a duas listas ao mesmo tempo. Para diferenciar as células-cabeça, coloque -1 nos campos Linha e Coluna destas células.Com esta representação, uma matriz esparsa M x N com r elementos diferentes de zero gastará (M+N+r) células. É bem verdade que cada célula ocupa vários bytes na memória; no entanto, o total de memória usado será menor do que as M X N posições necessárias para representar a matriz toda, desde que r seja suficientemente pequeno.Dada a representação acima, o trabalho consiste em desenvolver cinco funções em C++, conforme especificação abaixo:a) void LeMatriz (Matriz* A);Este procedimento lê algum arquivo de entrada (ou do teclado) os elementos diferentes de zero de uma matriz e monta a estrutura especificada acima. Considere que a entrada consiste dos valores M e N (número de linhas e de colunas da matriz) seguidos de triplas (i, j, valor) para os elementos diferentes de zero da matriz. Por exemplo, para a matriz acima, a entrada seria:4 41 1 50.02 1 10.02 3 20.04 1 -30.04 3 -60.04 4 5.0B) void ApagaMatriz (Matriz* A);Este procedimento devolve todas as células da matriz A para a área de memória disponível (use a função free).c) void SomaMatriz (Matriz* A, Matriz* B, Matriz* C);Este procedimento recebe como parâmetros as matrizes A e B, devolvendo em C a soma de A com B.d) void MultiplicaMatriz (Matriz* A, Matriz* B, Matriz* C);Este procedimento recebe como parâmetros as matrizes A e B, devolvendo em C o produto de A por B.e) void ImprimeMatriz (Matriz* A);Este procedimento imprime (uma linha da matriz por linha da saída) a matriz A, INCLUSIVE os elementos iguais a zero.Para inserir e retirar células das listas que formam a matriz, crie procedimentos especiais para este fim. Por exemplo, um procedimento void Insere(int i, int j, float v, Matriz* A);para inserir o valor v na linha i, coluna j da matriz A será útil tanto na função LeMatriz, quanto na função SomaMatriz.Os procedimentos deverão ser testados com o seguinte programa:int main () {...... LeMatriz(A); ImprimeMatriz(A); LeMatriz(B); ImprimeMatriz(B); SomaMatriz(A, B, C); ImprimeMatriz©; ApagaMatriz©; MultiplicaMatriz(A, B, C); ImprimeMatriz©; ApagaMatriz(B); ApagaMatriz©; LeMatriz(B); ImprimeMatriz(A); ImprimeMatriz(B); SomaMatriz(A, B, C); ImprimeMatriz©; MultiplicaMatriz(A, B, C); ImprimeMatriz©; MultiplicaMatriz(B, B, C); ImprimeMatriz(B); ImprimeMatriz(B); ImprimeMatriz©; ApagaMatriz(A); ApagaMatriz(B); ApagaMatriz©; return 0;}SE ALGUEM TIVER INTERESSE EM ME AJUDAR EU PASSO O TRABALHO DIREITO POIS TEM UMAS FIGURAS AKI PARA MELHOR ENTENDIMENTO.OBRIGADO.

[ricci ottadnot 4]

ow leonardo..precisamos saber aonde você esta com dificuldade..você naum apontou aonde esta encontrando o problema, assim naum tem como nos ajudarmos..post aew o q devemos fazer p ajudar..flw

[Felipe Correa 0]

Não tenho nd parecido se conseguir resolver me passa pois e um grande problema criar uma função para ler , outra para apagar e outra para somar e um otimo problema..........Se alguem souber resolver tbm me passa beleza ............

[Phelipea 0]

Estou fazendo este EP tambem e tenho duvidas em relação a parte de ler a Matriz.
Por ex.: eu leio os dados de entrada (linhas e colunas), ai agora eu preciso ler os dados da tripla (linha,coluna,valor) e alocar celular pra eles...
Mas antes preciso criar as celulas cabecas pra apontar pra estas outras celulas que vao conter o valor lido.

Meu problema esta justamente ai.
Eu imaginei o seguinte: Ler os dados com o while(!feof(entrada) e ir pegando os valores, mas dentro do while teria um for, pra testar se algum dos valores de linhas e colunas lidos contem o elemento. (ex.: o primeiro elemento tem linha = 2, coluna = 1, o for vai percorrer todos os valores ate acha este elemento, e alocar pra ele uma celula, armazenando linha, coluna e valor.)

 

Meu Codigo (parte dele ne, pq ai que to garrando e por ai kkk)

typedef struct TipoCelula *TipoApontador;
typedef struct TipoCelula{
	TipoApontador direta,abaixo;
	long linha,coluna;
	double valor;
};


#include <funcao.h>


LeMatrizEsparsa (TipoCelula* Cabeca1)
{
	int i,j;
	long tempL,tempC;
	double tempV;
	TipoCelula = Matrix,celula,raiz;
	int auxlinhas,auxcolunas;
	FILE * entrada;
	entrada = fopen(entrada,"r");
	fscanf (entrada,"%l %l",&auxlinhas,&auxcolunas);
	raiz = (TipoApontador)malloc(sizeof(TipoCelula));										//criando celulas cabecas
	raiz->direita = NULL; raiz->abaixo = NULL
	raizdireita = (TipoApontador)malloc(sizeof(TipoCelula));
	raizdireita = raiz->direita;
	raizbaixo = (TipoApontador)malloc(sizeof(TipoCelula));
	raizbaixo = raiz->abaixo;
	raiz->linha = -1; raiz->coluna = -1;
	
	for(i=0;i<auxcolunas;i++){                          	//atribuindo as celulas cabecas de colunas, o valor -1 pra coluna
		raizdireita->coluna = -1;
		raizdireita = raizdireita->direita;					
			
}
raizdireita->direita = raiz;														////atribuindo as celulas cabecas de lnhas, o valor -1 pra linhas
	for(j=0;j<auxlinhas;j++){
		raizbaixo->linha = -1;
		raizbaixo = raizbaixo->abaixo;

}
raizbaixo->abaixo = raiz;
		
		
	
	while(!feof(entrada)){   						//Pegar os elementos da entrada e montar a matriz esparsa
												 	//Ler cada elemento da entrada, usar um for e ir apontando na matriz encadeada
		fscanf("%l %l %lf",&tempL,&tempC,&tempV);
		
		for (i=0;i<auxlinhas;i++){
			for(j=0;<auxcolunas;j++){
				if((i==tempL) && (j==tempC)) {				
					celula = (TipoApontador)malloc(sizeof(TipoCelula));
					celula->linha = tempL;
					celula->coluna = tempC;
					celula->valor = tempV;
				}
			}
		}}
		
		
		
		
		
		for(i=0;i<auxcolunas;i++){
			//Agora eu teria que percorrer as coluunas para apontar as cabecas para o primeiro elemento e assum sucessivamente...
			//mas nao sei como fazer.
		}
	

Talvez minha logica esteja errada e este pode nao ser o melhor jeito de fazer este EP, pois vi num PDF ai da disciplina que tem como fazer com as celulas cabecas sendo vetores... mas nao entendi mto bem.

Mas se puderem me dar ideias seram bem vidas