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.

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:

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ę.

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.

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ść.

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.

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. }

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1