1

Preciso criar uma matriz esparsa do tipo lista dinâmica cruzada e minhas células são do tipo:

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

}CELULA;

Porém, toda vez que crio uma célula nova em uma função, não sei como armazená-la. Preciso armazenar cada célula pois em uma função posterior o meu programa precisa recuperar células de acordo com seus valores e posições. Além disso, não posso armazenar tais células em um vetor estático.

2
  • Já tentou utilizar malloc? Commented 5/11/2017 às 12:03
  • Mas usando malloc em qual vetor vou armazenar? Em um vetor do tipo células?
    – heavydsoul
    Commented 5/11/2017 às 12:36

3 Respostas 3

1

Voce pode alocar uma array de ponteiros (linhas), cada um apontando para uma array de CELULAS (colunas). Ilustrando a ideia:

inserir a descrição da imagem aqui

Segue um código testado e comentado demonstrando uma possível solução:

#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;
}

Possível Saída:

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 

As coisas poderiam ficar ainda mais simples se você tivesse uma abstração da matriz ao invés de uma abstração das celulas da matriz:

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

O código ficaria assim:

#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;
}
1

Sim, tem diversas formas de fazer isto. E uma delas é o próprio vetor estático.

Sim, é possível criar um algo ritmo que manipule o vetor criando outro quando precisa colocar novos itens. Não sei se é o mais adequado para sua necessidade, mas é uma das formas mais usadas. Mas tem casos que a solução simples é só criar um vetor grande. Isto é mais prático do que imagino, mas claro não serve para todos os casos.

É possível usar um vetor estático como um mapa para os objetos reais que lhe interessam.

É possível criar um vetor dinâmico no heap com malloc(), mas apesar de usarmos o termo dinâmico há restrições de como pode modificar seu tamanho, na maioria dos casos com as mesmas restrições de um vetor estático. Isto não é mágica.

Como a pergunta já indica é possível fazer uma lista ligada, assim cada elemento fica em uma área da memória independente e ela própria mapeia onde está o próximo e/ou o anterior. Pode ser que precise de uma árvore ou grafo.

É possível fazer algo híbrido com blocos interdependentes, então você tem uma lista ligada ou um vetor mapeado de vetores e não de elementos, o que pode ser um belo ganho.

Desenvolvimento de software é engenharia, é achar a melhor solução para o problema específico. Não é copiar receitas de bolo, como muita gente acha. A parte "boa" é que praticamente todos os problemas já tem uma solução pronta para uso, mas como ingrediente, cada um tem que saber tudo o que existe e quando usar individualmente e compostamente em cada caso. É igual matemática, não é decorar fórmulas, é conhecê-las e saber como e quando aplicar.

Cada estrutura de dados e cada algoritmo tem suas vantagens e desvantagens.

0

Ué, cada célula teria dois (ou quatro) ponteiros: um para o elemento seguinte na linha e outro para o elemento seguinte na coluna. (Os dois extras seriam para o elemento anterior, caso ele seja interessante.)

Por exemplo, considere a matriz

 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

Ela poderia ser representada da forma a seguir na memória:

[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

(Omiti, por preguiça, os vetores que apontam para os primeiros elementos das linhas e colunas...)

A sua função deve receber o valor a ser armazenado e sua posição linha-coluna; com isso a inserção é mera questão de ajuste, e a procura por elementos especificados é uma busca em uma lista encadeada

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .