Uma matriz que contém muitos elementos iguais a zero é denominada matriz esparsa. Uma matriz esparsa pode ser representada por 3 vetores: val, lin e col. 0 vetor val armazena apenas os elementos diferentes de zero da matriz. Os vetores lin e col são tais que: se val[k] = x e x aparece na linha ie coluna j da matriz esparsa, então
e col
. Considerando apenas matrizes esparsas quadradas, escrever a função void codifica(int **M, int n, int * val, int *lin, int * col), que dada uma matriz esparsa
(de tamanho
), determina os vetores val, lin e col correspondentes. Escrever um programa para testar a função, gerando a matriz com valores aleatórios no intervalo [0,5]. Considerar que a alocação de memória para a matriz e para os vetores será feita dinamicamente na função main().
Passo 1
Resumindo: temos uma matriz esparsa M de dimensão n×n, alocada dinamicamente como int**. Queremos montar três vetores val, lin e col, onde para cada elemento não nulo M[i][j] guardamos seu valor em val[k], sua linha em lin[k] e sua coluna em col[k].
Passo 2
Para percorrer a matriz usamos dois loops aninhados: um sobre as linhas i de 0 a n–1 e outro sobre as colunas j de 0 a n–1. Mantemos um índice k inicializado em 0. Sempre que M[i][j]≠0, atribuímos val[k]=M[i][j], lin[k]=i e col[k]=j, e então incrementamos k.
Passo 3
Implementamos a função void codifica(int** M, int n, int* val, int* lin, int* col) seguindo exatamente esse algoritmo de varredura e armazenamento.
Passo 4
No main(), lemos n, alocamos M como um vetor de ponteiros para int de tamanho n, e para cada linha alocamos um vetor de int de tamanho n. Também alocamos os vetores val, lin e col de tamanho máximo n*n. Preenchemos M com números aleatórios em [0,5] usando rand()%6. Chamamos codifica(M,n,val,lin,col). Por fim imprimimos a matriz gerada e os três vetores resultantes, e liberamos toda a memória alocada.
Resposta
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdlib.h>
#include <time.h>
void codifica(int **M, int n, int *val, int *lin, int *col) {
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] != 0) {
val[k] = M[i][j];
lin[k] = i;
col[k] = j;
k++;
}
}
}
}
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] != 0) {
val[k] = M[i][j];
lin[k] = i;
col[k] = j;
k++;
}
}
}
}
int main() {
int n;
printf(“Digite o valor de n (dimensão da matriz): “);
if (scanf(”%d”, &n) != 1 || n <= 0) {
printf(“Entrada inválida.\n”);
return 1;
}
int n;
printf(“Digite o valor de n (dimensão da matriz): “);
if (scanf(”%d”, &n) != 1 || n <= 0) {
printf(“Entrada inválida.\n”);
return 1;
}
// Aloca matriz M
int **M = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
M[i] = malloc(n * sizeof(int));
}
// Aloca vetores val, lin, col (tamanho máximo n*n)
int maxnz = n * n;
int *val = malloc(maxnz * sizeof(int));
int *lin = malloc(maxnz * sizeof(int));
int *col = malloc(maxnz * sizeof(int));
// Gera matriz aleatória em [0,5]
srand(time(NULL));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
M[i][j] = rand() % 6; // valores entre 0 e 5
}
}
// Chama codifica
codifica(M, n, val, lin, col);
// Imprime matriz
printf("\nMatriz M gerada:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", M[i][j]);
}
printf("\n");
}
// Conta quantos elementos não nulos foram codificados
int count = 0;
for (int i = 0; i < n * n; i++) {
// Para interromper no primeiro zero extra
if (i > 0 && val[i] == 0 && lin[i] == 0 && col[i] == 0 && val[i-1] != 0) break;
if (i == 0 && val[0] == 0 && M[ lin[0] ][ col[0] ] == 0) break;
if (val[i] != 0) count++;
}
// Imprime vetores
printf("\nVetores val, lin e col (total de %d elementos não nulos):\n", count);
printf("k\tval[k]\tlin[k]\tcol[k]\n");
for (int k = 0; k < count; k++) {
printf("%d\t%d\t%d\t%d\n", k, val[k], lin[k], col[k]);
}
// Libera memória
for (int i = 0; i < n; i++) free(M[i]);
free(M);
free(val);
free(lin);
free(col);
return 0;
}