Mapper le tableau 2D dans le tableau 1D

Question

Pour le plaisir, j'essaye de représenter un tableau 2D dans le tableau 1D. Comment puis-je mapper un tableau bidimensionnel au tableau 1 dimensionnel?

Par exemple, supposons que nous donne un tableau:

char[][] 2dArray = new char[4][4]; 

Dans l'espace 2 dimensions, la gamme (0,0),(2,2) représenterait 9 éléments (représentés comme O ci-dessous): O, O, O, X O, O, O, X O, O, O, X X, X, X, X

Si nous représentons le tableau à deux dimensions sous la forme d'un tableau à une dimension:

char[] 1dArray = new char[16]; 

cela ressemblerait à ceci:

O, O, O, X, O, O, O, X, O, O, O, X, X, X, X, X 

Je sais déjà que je peux trouver l'index d'un seul point dans mon tableau 1 dimensions par la formule: (rows * x + y).

c.-à-d. Que le 2d point (2,3) correspondrait à l'index 1d 11 dans l'exemple donné.

Soit deux 2D coordonnées, Comment puis-je mapper une section rectangulaire de points à un tableau 1D? Je préfère ne pas utiliser l'imbrication en boucle, si possible.

Answer 1

supposons tableau 2D rectangulaire de chars de ce genre:

const int xs=6; // columns 
const int ys=4; // rows 
char dat2D_xy[xs][ys]= 
    { 
    "06ci", 
    "17dj", 
    "28ek", 
    "39fl", 
    "4agm", 
    "5bhn", 
    }; 
char dat2D_yx[ys][xs]= 
    { 
    "", 
    "6789ab", 
    "cdefgh", 
    "ijklmn", 
    }; 
dat2D_xy[5][3] == dat2D_yx[3][5] == 'n'; 

ensuite convertir x,y coordonnées à l'index 1D et arrière, vous pouvez utiliser:

i=x+(xs*y); 
x=i%xs; 
y=i/xs; 

Ou ceci:

i=y+(ys*x); 
x=i%ys; 
y=i/ys; 

n'a pas d'importance, il change juste l'ordre des éléments le tableau 1D. Pour copier un tableau entier sur 1D, vous devez utiliser 2 boucles imbriquées ou simplement une seule avec ajout à DMA ou tout autre transfert de mémoire. Quelque chose comme ceci:

int i,x,y; 
char dat1D[xs*ys]; 
for (i=0,y=0;y<ys;y++) 
for (x=0;x<xs;x++,i++) 
    dat1D[i]=dat2D_xy[x][y]; 
//dat1D[i]=dat2D_yx[y][x]; 

//dat1D[]="abcdefghijklmn"; 

ou:

int i,x,y; 
for (i=0,x=0;x<xs;x++) 
for (y=0;y<ys;y++,i++) 
    dat1D[i]=dat2D_xy[x][y]; 
//dat1D[i]=dat2D_yx[y][x]; 

//dat1D[]="06ci17dj28ek39fl4agm5bhn"; 

Il n'y a pas besoin X ... sauf si vous voulez ajouter aussi les caractères de terminaison null à la fin de chaque ligne/ligne pour faciliter le débogage jusqu'à afficher ou traiter des lignes ou des colonnes en tant que chaînes. Dans ce cas, vous ajoutez +1 pour la taille de ligne et ajoutez votre caractère de terminaison.

Answer 2

Il est facile, d'abord décider d'un ordre de stockage (colonne principale ou de la ligne principale), puis avec une boucle imbriquée vous remplissez de la matrice 2D A le tableau 1D B:

Exemple:

A est une matrice NxM

for i in 
    for j in M 
     B[i*M + j] = A[i][j] 

Answer 3

Je pense que vous aurez besoin de certaines fonctionnalités de langue si vous ne voulez pas de boucle neseted. Ceci est mon exemple en python.

Tout d'abord permet de créer une liste a de dimension 4 x 4 où a[i][j] est un tuple de (i, j)

a = [[(i, j) for j in range(4)]for i in range(4)] 

Supposons maintenant que nous voulons que la sous-matrice (1, 1)-(2, 3). Tout d'abord permet des éléments de filtre de ligne 1 à rangée 2

rows = a[1:3]

Ensuite, nous obtenons les éléments entre 1 et col col 3 pour obtenir le sous-matrice.

submatrix = [row[1:4] for row in rows]

Maintenant, nous avons le sous-matrice, pour le convertir à la liste 1d, nous pouvons utiliser sum

ans = sum(submatrix, [])

Enfin, si nous imprimons ans, nous aurons

[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)]

Combiner les choses er, nous avons cette fonction, où a est la matrice d'entrée, p1 et p2 sont des points d'entrée pour localiser le sous-matrice

def f(a, p1, p2): 
    x1, y1 = p1 
    x2, y2 = p2 

    return sum([row[y1:y2 + 1] for row in a[x1:x2 + 1]], []) 

Answer 4

Il est possible sans boucle imbriquée et aucune prise en charge linguistique (et n'a pas encore mentionné), mais je doute qu'il sera plus rapide (tableau avec n lignes et m colonnes):

for (int i = 0; i < n * m; i++) 
    arr1D[i] = arr2D[i/m][i % m]; 

Le modulo donne évidemment 0, 1, 2, ..., m - 1, puis commence à 0 à nouveau, comme devrait et le résultat de la division entière est augmenté de un après qu'une ligne est pleine. Ou lire colonne par colonne (pire dans la plupart des langues, mieux lire ligne par ligne comme ci-dessus):

for (int i = 0; i < n * m; i++) 
    arr1D[i] = arr2D[i % n][i/n];  

Cependant cela ne fonctionne qu'avec des matrices rectangulaires. par exemple contre:

int[][] arr2D = new int[2][]; 
arr2D[0] = new int[1]; 
arr2D[1] = new int[2]; 

Dans ce cas, il serait préférable de le faire de façon standard, en utilisant une liste ici parce que je ne sais pas ce que la longueur du résultat va être (ajouter des contrôles null si null est une possibilité):

List<Integer> list = new ArrayList<>(); 
for (int i = 0; i < arr2D.lengh; i++) 
    for (int j = 0; j < arr2D[i].length; j++) 
     list.add(arr2D[i][j]);