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. 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. 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. int* na1D(int tab2D[w][h], const int w, const 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. int main() { 
  2.   int tab2D[w][h];
  3.   for (int y = 0; y < h; y++)
  4.     for (int x = 0; x < w; x++)
  5.       tab2D[x][y] = y*w + x;
  6.   cout << "Tablica 2D" << endl;
  7.   for (int y = 0; y < h; y++) {
  8.     for (int x = 0; x < w; x++) {
  9.       cout << tab2D[x][y] << "\t";
  10.     }
  11.     cout << endl;
  12.   }
  13.   cout << "\nTablica 1D" << endl;
  14.   int* tab1D = na1D(tab2D, w, h);
  15.   for (int y = 0; y < h; y++)
  16.     for (int x = 0; x < w; x++)
  17.     cout << pobierzXY(tab1D, x, y, w) << " ";
  18.   cout << endl;
  19.   system("pause");
  20.   return 0;
  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.