Can I store values without using static vectors?

1

I need to create a sparse array of type dynamic cross-list and my cells are of type:

typedef struct CELULA{
    int linha;
    int coluna;
    double valor;

}CELULA;

However, every time I create a new cell in a function, I do not know how to store it. I need to store each cell because in a later function my program needs to retrieve cells according to their values and positions. Also, I can not store such cells in a static vector.

    
asked by anonymous 05.11.2017 / 12:40

3 answers

1

You can allocate an array of pointers (rows), each pointing to an array of CELULAS (columns). Illustrating the idea:

Hereisatestedandcommentedcodedemonstratingapossiblesolution:

#include<stdio.h>#include<stdlib.h>#include<time.h>typedefstructCELULA{intlinha;intcoluna;doublevalor;}CELULA;CELULA**matriz_criar(intncolunas,intnlinhas){inti=0;/*Alocaarraydeponteirosrepresentandocadaumadaslinhas*/CELULA**c=(CELULA**)malloc(nlinhas*sizeof(CELULA*));/*AlocaumaarraydeCELULASrepresentandocadacoluna*/for(i=0;i<nlinhas;i++)c[i]=(CELULA*)malloc(ncolunas*sizeof(CELULA));returnc;}voidmatriz_destruir(CELULA**c,intnlinhas){inti=0;for(i=0;i<nlinhas;i++)free(c[i]);free(c);}voidmatriz_preencher(CELULA**m,intncolunas,intnlinhas){inty=0;intx=0;srand(time(NULL));for(y=0;y<nlinhas;y++)for(x=0;x<ncolunas;x++)/*Atribuindovaloraceluladamatriz*/m[y][x].valor=rand()/((double)RAND_MAX);}voidmatriz_exibir(CELULA**m,intncolunas,intnlinhas){inty=0;intx=0;for(y=0;y<nlinhas;y++){for(x=0;x<ncolunas;x++)/*Lendovalorcontidonaceluladamatriz*/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 Output:

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 be even simpler if you had an abstraction of matriz instead of an abstraction of celulas da matriz :

typedef struct MATRIZ {
    int nlinhas;
    int ncolunas;
    double ** celulas;
} MATRIZ;

The code looks 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;
}
    
05.11.2017 / 18:41
1

Yes, there are several ways to do this. And one of them is the static vector itself.

Yes, it is possible to create a rhythm something that manipulates the vector by creating another one when you need to put 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 is not for all cases.

You can use a static vector as a map for the actual objects that interest you.

You can create a dynamic vector in heap with malloc() , but although we use the term dynamic there are restrictions on how to modify its size, in most cases with the same restrictions of a static vector. This is not magic.

As the question already points out, you can do a linked list , so each element is in an area of memory independent and maps itself to where the next and / or the previous one is. You may need a tree or graph.

It is possible to do something hybrid with interdependent blocks, so you have a linked list or a mapped vector of vectors and not elements, which can be a nice gain.

Software development is engineering; it is finding the best solution to the specific problem. It's not copying cake recipes, as most people think. The "good" part is that virtually every problem already has a ready-to-use solution, but as an ingredient, everyone has to know everything that exists and when to use it individually and in a composite way in each case. It's just like math, it's not decorating formulas, it's getting to know them and knowing how and when to apply.

Each data structure and algorithm has its advantages and disadvantages.

    
05.11.2017 / 13:20
0
Therefore, each cell would have two (or four) pointers: one for the next element in the row and one for the next element in the column. (The two extras would be for the previous element, if it is interesting.)

For example, consider the array

 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 as follows 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

(Omit, for laziness, vectors that point to the first elements of rows and columns ...)

Your function should receive the value to be stored and its row-column position; so the insertion is just a matter of tuning, and the search for specified elements is a search in a linked list

    
05.11.2017 / 14:51