1
I need to create a sparse matrix of the cross-dynamic list type and my cells are the type:
typedef struct CELULA{
int linha;
int coluna;
double valor;
}CELULA;
But every time I create a new cell in a function, I don’t know how to store it. I need to store each cell because in a later function my program needs to recover cells according to their values and positions. Also, I cannot store such cells in a static vector.
1
Yes, there are several ways to do this. And one of them is the static vector itself.
Yes, it is possible to create something rhythm that manipulates the vector creating another one when you need to place new items. I do not know if it is the most suitable for your need, but it is one of the most used forms. But there are cases that the simple solution is just to create a large vector. This is more practical than I imagine, but of course it doesn’t suit all cases.
You can use a static vector as a map for the real objects that interest you.
It is possible to create a dynamic vector in the heap with malloc(), but although we use the term dynamic there are restrictions on how it can modify its size, in most cases with the same constraints as a static vector. This is not magic.
As the question already indicates it is possible to make a linked list, so each element stays in an area of independent memory and itself maps where the next and/or the previous one is. You may need a tree or graph.
You can do something hybrid with interdependent blocks, so you have a linked list or a vector map of vectors, not elements, which can be a nice gain.
Software development is engineering, is to find the best solution to the specific problem. It is not copying cake recipes, as many people think. The "good" part is that virtually every problem already has a ready-to-use solution, but as an ingredient, each has to know everything that exists and when to use individually and componently in each case. It’s equal math, it’s not memorizing formulas, it’s knowing them and knowing how and when to apply.
Every data structure and every algorithm has its advantages and disadvantages.
1
You can allocate one array of pointers (lines), each pointing to a array of CELULAS (columns). Illustrating the idea:
Follow a tested and commented code demonstrating a possible solution:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct CELULA {
int linha;
int coluna;
double valor;
} CELULA;
CELULA ** matriz_criar( int ncolunas, int nlinhas )
{
int i = 0;
/* Aloca array de ponteiros representando cada uma das linhas */
CELULA ** c = (CELULA**) malloc( nlinhas * sizeof(CELULA*) );
/* Aloca uma array de CELULAS representando cada coluna */
for( i = 0; i < nlinhas; i++ )
c[i] = (CELULA*) malloc( ncolunas * sizeof(CELULA) );
return c;
}
void matriz_destruir( CELULA ** c, int nlinhas )
{
int i = 0;
for( i = 0; i < nlinhas; i++ )
free(c[i]);
free(c);
}
void matriz_preencher( CELULA ** m, int ncolunas, int nlinhas )
{
int y = 0;
int x = 0;
srand(time(NULL));
for( y = 0; y < nlinhas; y++ )
for( x = 0; x < ncolunas; x++ )
/* Atribuindo valor a celula da matriz */
m[y][x].valor = rand() / ((double)RAND_MAX);
}
void matriz_exibir( CELULA ** m, int ncolunas, int nlinhas )
{
int y = 0;
int x = 0;
for( y = 0; y < nlinhas; y++ ){
for( x = 0; x < ncolunas; x++ )
/* Lendo valor contido na celula da matriz */
printf( "%0.3f ", m[y][x].valor );
printf("\n");
}
}
int main( void )
{
int ncolunas = 10; /* Numero de colunas */
int nlinhas = 20; /* Numero de linhas */
/* Cria matriz contendo as dimensoes desejadas */
CELULA ** m = matriz_criar( ncolunas, nlinhas );
/* Preenche matriz com numeros aleatorios */
matriz_preencher( m, ncolunas, nlinhas );
/* Exibe conteudo da matriz preenchido */
matriz_exibir( m, ncolunas, nlinhas );
/* Desaloca memoria ocupada pela matriz */
matriz_destruir( m, nlinhas );
/* Sucesso */
return 0;
}
Possible Exit:
0.104 0.915 0.099 0.313 0.186 0.395 0.298 0.533 0.440 0.751
0.483 0.265 0.465 0.988 0.265 0.319 0.224 0.165 0.884 0.729
0.594 0.395 0.697 0.722 0.146 0.469 0.390 0.747 0.210 0.846
0.736 0.314 0.760 0.835 0.627 0.946 0.230 0.925 0.480 0.670
0.676 0.963 0.935 0.141 0.951 0.200 0.459 0.175 0.365 0.343
0.905 0.959 0.738 0.601 0.681 0.884 0.070 0.071 0.630 0.280
0.917 0.366 0.594 0.677 0.201 0.221 0.623 0.431 0.146 0.103
0.101 0.822 0.066 0.037 0.963 0.017 0.237 0.422 0.192 0.602
0.765 0.096 0.560 0.502 0.698 0.242 0.386 0.768 0.313 0.017
0.049 0.229 0.383 0.643 0.906 0.584 0.864 0.529 0.015 0.010
0.633 0.117 0.832 0.698 0.153 0.795 0.715 0.390 0.216 0.906
0.992 0.981 0.003 0.552 0.484 0.701 0.794 0.870 0.469 0.106
0.886 0.517 0.335 0.269 0.160 0.242 0.853 0.024 0.771 0.868
0.034 0.404 0.985 0.866 0.102 0.138 0.661 0.817 0.528 0.878
0.723 0.520 0.859 0.726 0.072 0.342 0.426 0.865 0.212 0.895
0.972 0.099 0.412 0.307 0.368 0.572 0.549 0.221 0.596 0.320
0.089 0.631 0.723 0.073 0.497 0.825 0.211 0.158 0.642 0.739
0.036 0.365 0.259 0.895 0.091 0.331 0.238 0.517 0.196 0.450
0.413 0.168 0.549 0.825 0.475 0.916 0.397 0.023 0.137 0.994
0.343 0.226 0.624 0.066 0.299 0.121 0.891 0.511 0.280 0.533
Things could get even simpler if you had an abstraction of matriz rather than an abstraction of celulas da matriz:
typedef struct MATRIZ {
int nlinhas;
int ncolunas;
double ** celulas;
} MATRIZ;
The code would look like this:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct MATRIZ {
int nlinhas;
int ncolunas;
double ** celulas;
} MATRIZ;
MATRIZ * matriz_criar( int ncolunas, int nlinhas )
{
int i = 0;
/* Aloca a matriz */
MATRIZ * m = (MATRIZ*) malloc( sizeof(MATRIZ) );
/* Aloca uma array de ponteiros */
m->celulas = (double**) malloc( nlinhas * sizeof(double*) );
/* Aloca uma array de doubles para cada linha da matriz */
for( i = 0; i < nlinhas; i++ )
m->celulas[i] = (double*) malloc( ncolunas * sizeof(double) );
m->nlinhas = nlinhas;
m->ncolunas = ncolunas;
return m;
}
void matriz_destruir( MATRIZ * m )
{
int i = 0;
for( i = 0; i < m->nlinhas; i++ )
free(m->celulas[i]);
free(m->celulas);
free(m);
}
void matriz_preencher( MATRIZ * m )
{
int y = 0;
int x = 0;
srand(time(NULL));
for( y = 0; y < m->nlinhas; y++ )
for( x = 0; x < m->ncolunas; x++ )
/* Atribuindo valor a celula da matriz */
m->celulas[y][x] = rand() / ((double)RAND_MAX);
}
void matriz_exibir( MATRIZ * m )
{
int y = 0;
int x = 0;
for( y = 0; y < m->nlinhas; y++ ){
for( x = 0; x < m->ncolunas; x++ )
/* Lendo valor contido na celula da matriz */
printf( "%0.3f ", m->celulas[y][x] );
printf("\n");
}
}
int main( void )
{
int ncolunas = 10; /* Numero de colunas */
int nlinhas = 20; /* Numero de linhas */
/* Cria matriz contendo as dimensoes desejadas */
MATRIZ * m = matriz_criar( ncolunas, nlinhas );
/* Preenche matriz com numeros aleatorios */
matriz_preencher( m );
/* Exibe conteudo da matriz preenchido */
matriz_exibir( m );
/* Desaloca memoria ocupada pela matriz */
matriz_destruir( m );
/* Sucesso */
return 0;
}
0
Each cell would have two (or four) pointers: one for the next element in the row and the other for the next element in the column. (The two extras would be for the previous element, if it is interesting.)
For example, consider the matrix
X | 0 1 2 3 4
- + - - - - -
0 | 1 1 0 0 0
1 | 0 2 2 0 0
2 | 0 0 3 3 0
3 | 0 0 0 4 4
4 | 5 0 0 0 5
It could be represented in the following way in memory:
[1;(0,0)] -> [1;(0,1)] -> NULL
| |
| V
| [2;(1,1)] -> [2; (1,2)] -> NULL
| | |
| V V
| NULL [3; (2,2)] -> [3; (2,3)] -> NULL
| | |
| V V
| NULL [4; (3,3)] -> [4;(3,4)] -> NULL
| | |
| V |
| NULL |
V V
[5;(4,0)] ------------------------------------------> [5;(4,4)] -> NULL
| |
V V
NULL NULL
(I omitted, by laziness, the vectors that point to the first elements of the rows and columns...)
Your function must receive the value to be stored and its row-column position; thus the insertion is merely a matter of adjustment, and the search for specified elements is a search in a chained list
Browser other questions tagged c array list matrix chain-list
You are not signed in. Login or sign up in order to post.
Have you tried using malloc?
– Nayron Morais
But using malloc in which vector will I store? In a cell-like vector?
– heavydsoul