-
-
Save Tomcat-42/f80a8d36a7d24bdc73960f28862152cb to your computer and use it in GitHub Desktop.
Calculadora de matrizes esparsas.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Equipe: Pablo AS Hugen | |
* Questão 01: Matrizes Esparsas */ | |
#include <stdio.h> | |
#include <stdlib.h> | |
/* Número de casas decimais dos valores impressos */ | |
#define DEC 1 | |
/* Justifica PAD casas à direita */ | |
#define PAD 4 | |
/*Comando do OS para 'limpar' a stdout*/ | |
#define CLEARCMD "clear" | |
/*Células da matriz: Armazenam um ponteiro para a celula a direita a para a celula | |
* abaixo, além da sua linha e coluna e valor armazenado */ | |
typedef struct Cell | |
{ | |
struct Cell *Right, *Down; | |
int i, j; | |
double Data; | |
}Cell; | |
/*Matriz: Armazena um ponteiro para a cabeça "Central" - que possui ponteiros para | |
* as cabeça da primeira linha e a cabeça da primeira coluna-, além disso, possui o número de linhas, colunas, | |
* e a quantidade de elementos não zeros da matriz*/ | |
typedef struct Matrix | |
{ | |
struct Cell *Head; | |
int Rows, Cols; | |
int nonZero; | |
}Matrix; | |
/*Funções principais para correção */ | |
/*Imprime os elementos da matriz a, inclusive os iguais a 0*/ | |
void printMatrix(Matrix *a); | |
/*Lê uma matriz*/ | |
void scanMatrix(Matrix *a); | |
/*Retorna uma matriz soma,a veriicação de limites deve ser feita antes*/ | |
Matrix sumMatrix(Matrix *a, Matrix *b); | |
/*Retorna uma matriz produto,a verificação de limites deve ser feita antes*/ | |
Matrix prodMatrix(Matrix *a, Matrix *b); | |
/*Insere um elemento a[i,j] na matriz a*/ | |
void insertMatrix(Matrix *a, int i, int j, double Data); | |
/*Funções auxiliares */ | |
/*Inicia a matriz: aloca uma cabeça central, 'm' celulas cabeças para as linhas e 'n' células | |
* cabeças para as colunas*/ | |
void initMatrix(Matrix *a, int Rows, int Cols); | |
/*Remove um elemento a[i,j] na matriz a, caso o elemento não existir nada acontece */ | |
void removeMatrix(Matrix *a, int i, int j); | |
/*Retorna um ponteiro para o elemento a[i,j] se ele for diferente de zero, | |
* caso contrário retorna NULL*/ | |
Cell *cellPtr(Matrix *a, int i, int j); | |
int main() | |
{ | |
/*matrizes dispnoníveis para operações */ | |
Matrix matrizes[4]; | |
/*Controle do menu*/ | |
int menu = 0; | |
/*indices das matrizes usadas nas operações*/ | |
int op1,op2,res; | |
while(1) | |
{ | |
system(CLEARCMD); | |
printf("Calculadora de Matrizes:\n"); | |
printf( "\n0)Sair" | |
"\n1)Definir uma Matriz" | |
"\n2)Imprimir uma Matriz" | |
"\n3)Somar Matrizes" | |
"\n4)Multiplicar Matrizes"); | |
printf("\n\n>>> "); | |
scanf("%d",&menu); | |
system(CLEARCMD); | |
switch(menu) | |
{ | |
case 1: | |
printf("Definir uma Matriz:\n\n"); | |
printf("0)MatA\t1)MatB\n2)MatC\t3)MatD\n"); | |
printf("\n>>> "); | |
scanf("%d", &res); | |
system(CLEARCMD); | |
scanMatrix(&matrizes[res]); | |
break; | |
case 2: | |
printf("Imprimir uma Matriz:\n\n"); | |
printf("0)MatA\t1)MatB\n2)MatC\t3)MatD\n"); | |
printf("\n>>> "); | |
scanf("%d",&res); | |
system(CLEARCMD); | |
printMatrix(&matrizes[res]); | |
printf("\nPressione [ENTER] para retornar ao menu\n"); | |
getchar(); | |
while(getchar()!='\n'); | |
break; | |
case 3: | |
printf("Somar Matrizes:\n\n"); | |
printf("0)MatA\t1)MatB\n2)MatC\t3)MatD\n"); | |
printf("\nexemplo: Para armazenar a soma das matrizes MatA e MatB na matriz MatC '4 <= 0 + 3'"); | |
printf("\n>>> "); | |
scanf("%d <= %d + %d", &res, &op1, &op2); | |
matrizes[res] = sumMatrix(&matrizes[op1], &matrizes[op2]); | |
break; | |
case 4: | |
printf("Multiplicar Matrizes:\n\n"); | |
printf("0)MatA\t1)MatB\n2)MatC\t3)MatD\n"); | |
printf("\nexemplo: Para armazenar o produto das matrizes MatA e MatB na matriz MatC '4 <= 0 * 3'"); | |
printf("\n>>> "); | |
scanf("%d <= %d * %d", &res, &op1, &op2); | |
matrizes[res] = prodMatrix(&matrizes[op1], &matrizes[op2]); | |
break; | |
default: | |
exit(0); | |
} | |
} | |
return 0; | |
} | |
void printMatrix(Matrix *a) | |
{ | |
int i,j; | |
Cell *aux0 = NULL, *aux1 = NULL; | |
printf("Número de linhas: %d\nNúmero de colunas: %d\nNúmero de elementos não nulos: %d\n\n", | |
a->Rows, a->Cols, a->nonZero); | |
/* Visita todos as cabeças das linhas e printa seus elementos*/ | |
aux0 = a->Head->Down; | |
for(i=0; i<a->Rows; i++) | |
{ | |
aux1 = aux0->Right; | |
for(j=0; j<a->Cols; j++) | |
{ | |
/*Se o nó no index a[i,j] existir seu valor é impresso | |
* Caso contrário 0 */ | |
printf("%s%*.*lf%s", | |
(j==0)?("|"):(""), | |
(int)PAD, | |
(int)DEC, | |
(j==aux1->j) ? (aux1->Data) : (0.0), | |
(j<a->Cols-1)?(" "):("|\n")); | |
/*Avança o ponteiro se um nó correspondente foi encontrado*/ | |
if(aux1->j == j) | |
aux1 = aux1->Right; | |
} | |
aux0 = aux0->Down; | |
} | |
return; | |
} | |
void scanMatrix(Matrix *a) | |
{ | |
int rows = 0, cols =0; | |
int i=0,j=0; | |
double Data=0.0; | |
printf("Número de linhas: "); | |
scanf("%d", &rows); | |
printf("Número de colunas: "); | |
scanf("%d", &cols); | |
initMatrix(a, rows, cols); | |
printf("\nLê triplas \"i j Dado\" até todos os valores serem '-1'\n"); | |
while(scanf("%d %d %lf", &i, &j, &Data) && (i>-1 && j>-1)) | |
insertMatrix(a, i, j, Data); | |
} | |
Matrix sumMatrix(Matrix *a, Matrix *b) | |
{ | |
Matrix ret; | |
Cell *auxA0 = NULL, *auxA1 = NULL, *auxB0 = NULL, *auxB1 = NULL; | |
int i,j; | |
/*As dimensões das duas matrizes devem ser iguais, | |
* assim a dimensão da matriz soma será a mesma */ | |
initMatrix(&ret, a->Rows, a->Cols); | |
/* Visita todas as linhas de ambas matrizes */ | |
auxA0 = a->Head->Down; | |
auxB0 = b->Head->Down; | |
for(i=0; i<a->Rows; i++) | |
{ | |
auxA1 = auxA0->Right; | |
auxB1 = auxB0->Right; | |
for(j=0; j<a->Cols; j++) | |
{ | |
/*Ambos os elementos são não nulos, insere a soma e avança ambas as colunas*/ | |
if(auxA1->j == j && auxB1->j ==j) | |
{ | |
insertMatrix(&ret, i, j, auxA1->Data + auxB1->Data); | |
if(auxA1 != auxA0) auxA1 = auxA1->Right; | |
if(auxB1 != auxB0) auxB1 = auxB1->Right; | |
} | |
/*Somente o elemento da primeira matriz é não nulo, somente adiciona ele*/ | |
else if(auxA1->j == j) | |
{ | |
insertMatrix(&ret, i, j, auxA1->Data); | |
if(auxA1 != auxA0) auxA1 = auxA1->Right; | |
} | |
/*Somente o elemento da segunda matriz é não nulo, somente adiciona ele*/ | |
else if(auxB1->j == j) | |
{ | |
insertMatrix(&ret, i, j, auxB1->Data); | |
if(auxB1 != auxB0) auxB1 = auxB1->Right; | |
} | |
/*Ambos são nulos, insere o 0 para depois remover (?)*/ | |
else | |
insertMatrix(&ret, i, j, 0); | |
/*Avança somente se não chegou ao final */ | |
//if(auxA1 != auxA0) auxA1 = auxA1->Right; | |
//if(auxB1 != auxB0) auxB1 = auxB1->Right; | |
} | |
auxA0 = auxA0->Down; | |
auxB0 = auxB0->Down; | |
} | |
return ret; | |
} | |
Matrix prodMatrix(Matrix *a, Matrix *b) | |
{ | |
Matrix ret; | |
Cell *auxA0 = NULL, *auxA1 = NULL, *auxB0 = NULL, *auxB1 = NULL; | |
int i, j, k; | |
double sum =0; | |
/*As dimensões da nova matriz será o número de colunas da primiera matriz | |
* e o numero de linhas da segunda matriz */ | |
initMatrix(&ret, a->Rows, b->Cols); | |
/* Basicamente o algoritmo simples de multiplicação de matrizes, | |
* mas com toda a insanidade dos ponteiros*/ | |
auxA0 = a->Head->Down; | |
for(i=0; i<a->Rows; i++) | |
{ | |
auxB0 = b->Head->Right; | |
for(j=0; j<b->Cols; j++) | |
{ | |
auxB1 = auxB0->Down; | |
auxA1 = auxA0->Right; | |
sum = 0; | |
for(k=0; k<a->Cols; k++) | |
{ | |
if(auxA1->j == k && auxB1->i == k) | |
{ | |
sum+= (auxA1->Data * auxB1->Data); | |
if(auxA1 != auxA0) auxA1 = auxA1->Right; | |
if(auxB1 != auxB0) auxB1 = auxB1->Down; | |
} | |
else if(auxA1->j == k) | |
{ | |
if(auxA1 != auxA0) auxA1 = auxA1->Right; | |
} | |
else if(auxB1->i == k) | |
{ | |
if(auxB1 != auxB0) auxB1 = auxB1->Down; | |
} | |
} | |
auxB0 = auxB0->Right; | |
insertMatrix(&ret, i, j, sum); | |
} | |
auxA0 = auxA0->Down; | |
} | |
return ret; | |
} | |
void insertMatrix(Matrix *a, int i, int j, double Data) | |
{ | |
int k; | |
Cell *auxColHead = NULL, *auxRowHead = NULL, *auxCol = NULL, *auxRow = NULL; | |
/*Aloca a nova célula */ | |
Cell *newCell = (Cell *)malloc(sizeof(Cell)); | |
newCell->i = i; | |
newCell->j = j; | |
newCell->Data = Data; | |
/*Move auxRowHead para a cabeça da linha do novo elemento*/ | |
auxRowHead = a->Head->Down; | |
for(k=0; k<i; k++) | |
auxRowHead = auxRowHead->Down; | |
/*Move auxColHead para a cabeça da coluna do novo elemento*/ | |
auxColHead = a->Head->Right; | |
for(k=0; k<j; k++) | |
auxColHead = auxColHead->Right; | |
/*Move auxRow para o elemento anterior ao novo em sua linha*/ | |
auxRow = auxRowHead->Right; | |
while(1) | |
{ | |
if((auxRow->Right != auxRowHead) && (auxRow->Right->j < j)) | |
auxRow = auxRow->Right; | |
else | |
break; | |
} | |
/*Move auxCol para o elemento anterior ao novo em sua coluna*/ | |
auxCol = auxColHead->Down; | |
while(1) | |
{ | |
if((auxCol->Down != auxColHead) && (auxCol->Down->i < i)) | |
auxCol = auxCol->Down; | |
else | |
break; | |
} | |
/*Muda os ponteiros */ | |
newCell->Right = auxRow->Right; | |
newCell->Down = auxCol->Down; | |
auxRow->Right = newCell; | |
auxCol->Down = newCell; | |
/*Incrementa o número de elementos não zeros da matriz */ | |
a->nonZero++; | |
/*Um valor 0 não precisaria ser armazenado na matriz, mas | |
* de acordo com enunciado da questão ele deve ser inserido e depois removido.(?) */ | |
if(!Data) removeMatrix(a, i, j); | |
return; | |
} | |
void initMatrix(Matrix *a, int Rows, int Cols) | |
{ | |
int i; | |
Cell *aux = NULL; | |
a->Rows = Rows; | |
a->Cols = Cols; | |
a->nonZero = 0; | |
/*Cabeção central*/ | |
a->Head = (Cell *)malloc(sizeof(Cell)); | |
a->Head->i = a->Head->j = -1; | |
a->Head->Data = 42; | |
/*Aloca 'Rows' Cabeças para as listas das linhas*/ | |
aux = a->Head; | |
for(i=0; i<Rows; i++) | |
{ | |
aux->Down = (Cell *)malloc(sizeof(Cell)); | |
aux->Down->Right = aux->Down; | |
aux->Down->Data = 0; | |
aux->Down->i = aux->Down->j = -1; | |
aux = aux->Down; | |
} | |
aux->Down = a->Head; | |
/*Aloca 'Cols' Cabeças para as listas das colunas */ | |
aux = a->Head; | |
for(i=0;i<Cols; i++) | |
{ | |
aux->Right = (Cell *)malloc(sizeof(Cell)); | |
aux->Right->Down = aux->Right; | |
aux->Right->Data = 0; | |
aux->Right->i = aux->Right->j = -1; | |
aux = aux->Right; | |
} | |
aux->Right = a->Head; | |
return; | |
} | |
void removeMatrix(Matrix *a, int i, int j) | |
{ | |
int k; | |
/*Ponteiro para o elemento a ser removido */ | |
Cell *elemento = cellPtr(a,i,j); | |
/*Ponteiros auxiliares*/ | |
Cell *aux0 = NULL, *aux1 = NULL; | |
/*Se o elemento não existe ele não pode ser removido, | |
* nesse caso a função não erguerá nenhuma exceção, somente | |
* irá retornar normalmente */ | |
if(!elemento) return; | |
/*O elemento existe, remove ele da lista da sua respectiva linha */ | |
aux0 = a->Head->Down; | |
for(k=0; k<i; k++) | |
aux0 = aux0->Down; | |
aux1 = aux0->Right; | |
while((aux1->Right != elemento)) | |
aux1 = aux1->Right; | |
aux1->Right = elemento->Right; | |
/*Remove o elemento da lista da sua respectiva coluna*/ | |
aux0 = a->Head->Right; | |
for(k=0; k<j; k++) | |
aux0 = aux0->Right; | |
aux1 = aux0->Down; | |
while(aux1->Down != elemento) | |
aux1 = aux1->Down; | |
aux1->Down = elemento->Down; | |
/*Desaloca o elemento */ | |
a->nonZero--; | |
free(elemento); | |
return; | |
} | |
Cell *cellPtr(Matrix *a, int i, int j) | |
{ | |
int k; | |
Cell *aux0 = NULL, *aux1 = NULL; | |
/*Tenta Caminhar até o elemento a[i,j] */ | |
aux0 = a->Head->Down; | |
for(k=0; k<i; k++) | |
aux0 = aux0->Down; | |
aux1 = aux0->Right; | |
for(k=0; k<j; k++) | |
{ | |
/*O elemento foi encontrado */ | |
if(aux1->j == j && aux1->i == i) | |
return aux1; | |
aux1 = aux1->Right; | |
} | |
/*O elemento foi encontrado */ | |
if(aux1->j == j && aux1->i == i) | |
return aux1; | |
/*O elemento não foi encontrado*/ | |
return NULL; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment