Strona główna » Algorytmy » Artykuły » Spłaszczanie Tablic 2D
 

Spłaszczanie Tablic 2D

Wstęp

Każdą tabliće dwuwymiarową o znanych wymiarach można zapisać jako tablice jednowymiarową. Języki programowanie zwykle pozwalają na tworzenie dwuwymiarowych tablic, ale mogą być one przechowywane we wspomniany sposób. W tym artykule zostanie przedstawiony jak konwertować tablicę 2D na 1D.

Tablica dwuwymiarowa

W celu odwołania się do konkretnego obiektu w tablicy dwuwymiarowej o wymiarach w×h należy użyć pary współrzędnych (x, y). Zakładając, że indeksujemy pola od 0 oto przykładowa tablica w której zapisano w każdym polu współrzędne odwołania.

(0, 0)(1, 0)(2, 0)..(w - 1, 0)
(0, 1)(1, 1)(2, 1)..(w - 1, 1)
(0, 2)(1, 2)(2, 2)..(w - 1, 2)
..........
(0, h - 1)(1, h - 1)(2, h - 1)..(w - 1, h - 1)

Chcąc przekształcić powyższą w tablicę należałoby przypisać każdemu polu jego pozycję (tj. unikalny numer) w taki sposób, aby można się było do niego odwołać. Najprostszy sposób polega na zapisaniu wiersza jeden za drugim czyli na koniec wiersza dopisujemy wiersz kolejny, a następnie nadajemy polom kolejne pozycje. Przyporządkowanie wyglądałoby następująco:

Współrzędne(0, 0)(1, 0)..(w - 1, 0)(0, 1)..(w - 1, 1)..(0, h - 1)(1, h - 1)(2, h - 1)..(w - 1, h - 1)
Pozycja01..(w - 1, 0)(0, 1)..(w - 1, 1)..(0, h - 1)(1, h - 1)(2, h - 1)..(w - 1, h - 1)

Do elementów tak zapisanej tablicy wciąż jest możliwe odwołanie jak do tablicy dwuwymiarowej, ale należy dla pary (x, y) wyliczyć pozycję p. Jak można zauważyć i-ty wiersz ma swój pierwszy element na pozycji i·w w tablicy 1D. W celu odwołania się do kolejnego elementu w tym wierszu należałoby dodać do pozycji pierwszego elementu wiersza dodać numer elementu w wierszu. W zapisie współrzędnych odpowiada to współrzędnej x.

Ostatecznie można wyprowadzić można wyprowadzić wzór na pozycję elementu (x, y): p = y·w + x. Oczywiście należy pamiętać, że indeksujemy od 0 oraz, że para (x, y) musi istnieć w tablicy. Inaczej można pobrać niewłaściwy element, albo spróować pobrać element spoza tablicy.

Implementacja

Funkcja ustawXY() służy do ustawiania elementu (x, y) w pewnej tablicy 1D, która jest przekazywana jako argument tab1D. Oczywiście potrzebna jest także szerokość tablicy w, aby wyliczyć odpowiednią pozycję.

C++
C#
  1. static void ustawXY(int[] tab1D, int x, int y, int w, int wartosc) {
  2.   tab1D[y * w + x] = wartosc;
  3. }

Analogicznie działa funkcja pobierzXY(), która wymaga podania tych samych argumentów.

C++
C#
  1. static int pobierzXY(int[] tab1D, int x, int y, int w) {
  2.   return tab1D[y * w + x];
  3. }

Napisawszy funkcje pomocnicze można przejść teraz do napisania funkcji konwertującej tablicę 2D na 1D. Taka funkcja wymaga podania trzech argumentów tab2D - tablica dwuwymiarowa do skonwertowania, oraz jej wymiary w - szerokość i h - wysokość.

C++
C#
  1. static int[] na1D(int[,] tab2D, int w, int h) {
  2.   int[] tab1D = new int[w * h];
  3.   for (int y = 0; y < h; y++)
  4.     for (int x = 0; x < w; x++)
  5.       ustawXY(tab1D, x, y, w, tab2D[x, y]);
  6.   return tab1D;
  7. }

Testowanie funkcji

Poniższa funkcja main() deklaruje nową tablicę 2D, a następnie wypełnia ją wartościami. Każde z pól otrzymuje wartość pozycji na której będzie zapisane w tablicy 1D. Tablica 2D jest wypisana, a następnie skonwertowana i ponownie wypisana.

C++
C#
  1. static void Main(string[] args) {
  2.   int w = 2, h = 3;
  3.   int[,] tab2D = new int[w, h];
  4.   for (int y = 0; y < h; y++)
  5.     for (int x = 0; x < w; x++)
  6.       tab2D[x, y] = y * w + x;
  7.   Console.WriteLine("Tablica 2D");
  8.   for (int y = 0; y < h; y++) {
  9.     for (int x = 0; x < w; x++) {
  10.       Console.Write("{0}\t", tab2D[x, y]);
  11.     }
  12.     Console.WriteLine();
  13.   }
  14.   Console.WriteLine("\nTablica 1D");
  15.   int[] tab1D = na1D(tab2D, w, h);
  16.   for (int y = 0; y < h; y++)
  17.     for (int x = 0; x < w; x++)
  18.       Console.Write("{0} ", pobierzXY(tab1D, x, y, w));
  19.   Console.WriteLine();
  20.   Console.ReadKey();
  21. }

Zadania

Zadanie 1

Napisz program, który pozwoli skonwertować tablicę 1D na 2D na podstawie długości tablicy 1D n i rozmiarów tablicy 2D w×h. Przetestuj działanie programu w podobny sposób jak została sprawdzona Implementacja.