Mapeie uma matriz 2D em uma matriz 1D

90

Eu quero representar uma matriz 2D com uma matriz 1D. Uma função passará os dois indicadores (x, y) e o valor a armazenar. Esses dois indicadores representariam um único elemento de uma matriz 1D e configurariam de acordo. Eu sei que a matriz 1D precisa ter o tamanho de arrayWidth × arrayHeight, mas não sei como definir cada elemento.

Por exemplo, como faço para distinguir (2,4,3) de (4,2,3)? Tentei definir a matriz como x * y, mas 2 * 4 e 4 * 2 resultariam no mesmo ponto na matriz e preciso que sejam diferentes.

Blackbinary
fonte

Respostas:

161

Você precisa decidir se os elementos da matriz serão armazenados na ordem das linhas ou das colunas e, então, ser consistente sobre isso. http://en.wikipedia.org/wiki/Row-major_order

A linguagem C usa a ordem das linhas para matrizes multidimensionais

Para simular isso com uma única matriz dimensional, você multiplica o índice da linha pela largura e adiciona o índice da coluna assim:

 int array[width * height];

 int SetElement(int row, int col, int value)
 {
    array[width * row + col] = value;  
 }
John Knoeller
fonte
7
Acho que essa resposta é mais clara, principalmente para iniciantes é melhor não escrever funções em uma linha ... !! É uma prática ruim de qualquer maneira .. :)
Lipis
3
Esta resposta também é útil quando você tem um compilador (por exemplo, sistemas embarcados) que não tem suporte a array multidimensional adequado
Alex Marshall
1
É incrível quantas pessoas conseguem responder à mesma pergunta corretamente, mas apenas UMA delas o diz de forma fácil de entender. Esta é a resposta mais simples possível. No entanto, John é o único que realmente fornece uma boa resposta para isso. Todo o resto é lixo que só pode ser facilmente compreendido por quem já sabe a resposta. Obrigado John, por falar em inglês ao invés de estrangeiro. Isso só mostra como algumas pessoas são ruins no ensino e como bons professores como John Knoeller sabem como simplificar e se comunicar com muito mais eficácia do que qualquer outra pessoa.
user2948630 de
6
Seria bom mostrar como inverter esse mapeamento: se o índice do array 1D for alpha, e o array 2D tiver dimensão Nem ambas as direções com índices x, y, então de acordo com @JohnKnoeller alpha=x+N*y,. A maneira de inverter isso seria definindo x=alpha%Ne y= (alpha-alpha%N)/N.
Tim
Venho aqui quase todos os dias!
Felipe Gutierrez
23

A fórmula típica para recálculo de índices de matriz 2D em índice de matriz 1D é

index = indexX * arrayWidth + indexY;

Alternativamente, você pode usar

index = indexY * arrayHeight + indexX;

(assumindo que arrayWidthé medido ao longo do eixo X e arrayHeightao longo do eixo Y)

Claro, pode-se chegar a muitas fórmulas diferentes que fornecem mapeamentos exclusivos alternativos, mas normalmente não há necessidade disso.

Em linguagens C / C ++, os arrays multidimensionais integrados são armazenados na memória para que o último índice mude mais rápido, o que significa que para um array declarado como

int xy[10][10];

elemento xy[5][3]é imediatamente seguido por xy[5][4]na memória. Você também pode querer seguir essa convenção, escolhendo uma das duas fórmulas acima, dependendo de qual índice (X ou Y) você considera ser o "último" dos dois.

Formiga
fonte
17

Exemplo: queremos representar um array 2D de tamanho SIZE_X e SIZE_Y. Isso significa que teremos MAXY linhas consecutivas de tamanho MAXX. Portanto, a função definida é

void set_array( int x, int y, int val ) { array[ x * SIZE_Y + y ] = val; }

O resultado seria:

int get_array( int x, int y ) { return array[ x * SIZE_Y + y ]; }
Kornel Kisielewicz
fonte
1
Seus valores MAXXe MAXYsão nomeados de forma confusa, porque os valores máximos de xe ysão MAXX - 1e, MAXY - 1respectivamente. Talvez SIZE_Xe SIZE_Ypossa ser melhor?
caf
3
[y * maxx + x] é a ordem das colunas, não da linha. Esta é a forma como o matlab funciona, mas não é a forma como os arrays normalmente funcionam em C.
John Knoeller
@todos: a menos que você mantenha os dados alterados, mas apenas essas duas funções get / set, e elas usem a mesma fórmula, você pode fazer assim ou ASSIM. (Garantido!)
imacake
Uma macro pode ser mais apropriada aqui para que você não empilhe chamadas de função desnecessárias no que deveria ser um acesso de dados de baixo nível (especialmente porque a indexação 1d em arrays pseudo-2d às vezes é uma técnica de otimização.
krs013
Supondo que o código seja um membro da classe, esse código ficará embutido. Caso contrário, inline explícito é MUITO melhor do que uma macro.
Kornel Kisielewicz
7

Como outros disseram, mapas C em ordem de linha

   #include <stdio.h>

   int main(int argc, char **argv) {
   int i, j, k;
   int arr[5][3];
   int *arr2 = (int*)arr;

       for (k=0; k<15; k++) {
          arr2[k] = k;
          printf("arr[%d] = %2d\n", k, arr2[k]);
       }

       for (i=0; i<5; i++) {
         for (j=0; j< 3; j++) {
            printf("arr2[%d][%d] = %2d\n", i, j ,arr[i][j]);
         }
       } 
    } 

Resultado:

arr[0] =  0
arr[1] =  1
arr[2] =  2
arr[3] =  3
arr[4] =  4
arr[5] =  5
arr[6] =  6
arr[7] =  7
arr[8] =  8
arr[9] =  9
arr[10] = 10
arr[11] = 11
arr[12] = 12
arr[13] = 13
arr[14] = 14
arr2[0][0] =  0
arr2[0][1] =  1
arr2[0][2] =  2
arr2[1][0] =  3
arr2[1][1] =  4
arr2[1][2] =  5
arr2[2][0] =  6
arr2[2][1] =  7
arr2[2][2] =  8
arr2[3][0] =  9
arr2[3][1] = 10
arr2[3][2] = 11
arr2[4][0] = 12
arr2[4][1] = 13
arr2[4][2] = 14
Sammy
fonte
3

usando o exemplo principal da linha:

A(i,j) = a[i + j*ld]; // where ld is the leading dimension
                      // (commonly same as array dimension in i)

// matrix like notation using preprocessor hack, allows to hide indexing
#define A(i,j) A[(i) + (j)*ld]

double *A = ...;
size_t ld = ...;
A(i,j) = ...;
... = A(j,i);
Anycorn
fonte
1

É importante armazenar os dados de forma que possam ser recuperados nos idiomas usados. A linguagem C armazena na ordem da linha principal (toda a primeira linha vem primeiro, depois toda a segunda linha, ...) com cada índice indo de 0 a sua dimensão-1. Portanto, a ordem da matriz x [2] [3] é x [0] [0], x [0] [1], x [0] [2], x [1] [0], x [1] [ 1], x [1] [2]. Portanto, na linguagem C, x [i] [j] é armazenado no mesmo lugar que uma entrada de array unidimensional x1dim [i * 3 + j]. Se os dados forem armazenados dessa forma, é fácil recuperá-los em linguagem C.

Fortran e MATLAB são diferentes. Eles são armazenados na ordem da coluna principal (toda a primeira coluna vem primeiro, depois toda a segunda linha, ...) e cada índice vai de 1 para sua dimensão. Portanto, a ordem do índice é o inverso de C e todos os índices são 1 maior. Se você armazenar os dados na ordem da linguagem C, FORTRAN pode encontrar X_C_language [i] [j] usando X_FORTRAN (j + 1, i + 1). Por exemplo, X_C_language [1] [2] é igual a X_FORTRAN (3,2). Em matrizes unidimensionais, esse valor de dados está em X1dim_C_language [2 * Cdim2 + 3], que é a mesma posição que X1dim_FORTRAN (2 * Fdim1 + 3 + 1). Lembre-se de que Cdim2 = Fdim1 porque a ordem dos índices é invertida.

MATLAB é igual a FORTRAN. Ada é igual a C, exceto que os índices normalmente começam em 1. Qualquer idioma terá os índices em uma dessas ordens C ou FORTRAN e os índices começarão em 0 ou 1 e podem ser ajustados de acordo para obter os dados armazenados.

Desculpe se esta explicação é confusa, mas acho que é precisa e importante para um programador saber.

Marca
fonte
-2

Você deve ser capaz de acessar o array 2d com um simples ponteiro no lugar. A matriz [x] [y] será organizada no ponteiro como p [0x * largura + 0y] [0x * largura + 1y] ... [0x * largura + n-1y] [1x * largura + 0y] etc .

Arthur Kalliokoski
fonte