Java: Tablice

Tablice są to zbiory większej ilości zmiennych zebranych pod jedną nazwą. Do odwoływania się do odpowiednich elementów tablicy służą liczby podawane w nawiasach kwadratowych. Trzeba pamiętać, że liczby te są numerowane od zera. To znaczy, że dla 5-elementowej tablicy pierwszym elementem jest 0 a ostatnim 4.

Tablicę tworzy się przez dodanie pary nawiasów kwadratowych do typu zmiennej, czyli na przykład:

int[] vec = null;

Jednak w tym momencie nie można dodawać elementów do tablicy. Dzieje się tak ponieważ sama deklaracja „int[] vec” nie rezerwuje miejsca w pamięci na tą tablicę. Takie coś jest dopiero odnośnikiem do tablicy, czyli zawiera adres miejsca w pamięci gdzie znajdować się będą dane. To znaczy w tym momencie jeszcze nie zawiera, bo został jej przypisane adres null, czyli brak adresu.

Żeby tablica wskazywała na jakiś adres pamięci, trzeba użyć operatora new, który rezerwuje miejsce w pamięci i zwraca jej adres. Czyli prawidłowe zarezerwowanie miejsca w pamięci na 5-elementową tablicę liczb całkowitych i przypisanie jej do zmiennej będzie wyglądało tak:

int[] vec = new int[5];

Operator new zwraca adres miejsca w pamięci, który jest przypisywany do zmiennej vec. W tym momencie można już normalnie korzystać z tablicy.

Każda tablica posiada dodatkową zmienną zawierającą ilość elementów w tej tablicy. Nazywa się ona length i można się do niej dobrać w taki sposób:

vec.length

Zmienna ta jest bardzo przydatna zwłaszcza przy przechodzeniu przez tablicę, czyli wykonywaniu jakiejś czynności na każdym elemencie tablicy. Pętla przechodząca przez tablicę powinna wyglądać tak:

for(int i = 0; i < vec.length; i++){
   // tu dostępna jest zmienna vec[i], zawierająca aktualnie sprawdzany
   // element tablicy
}

Ale dlaczego warunek jest i < vec.length, a nie <= ? Dlatego ponieważ największy indeks (numer elementu w tablicy) jest o jeden mniejszy od długości tablicy, a więc ostatni przebieg pętli będzie dla ostatniej wartości mniejszej od długości. Na przykład dla tablicy od długości 5 zmienna i w tej pętli będzie przybierała kolejno wartości 0, 1, 2, 3 i 4, czyli takie jakie indeksy mają elementy tablicy.

Ale to jest tylko jeden ze sposobów tworzenia tablic. Drugi to wypełnienie tablicy od razu wartościami. Robi się to tak:

int[] vec = { 1, 2, 3, 4, 5 };

Tablica vec będzie zawierała 5 elementów.

Tablice mogą być także wielowymiarowe - dwu, trzy i więcej. Jest to bardzo przydatne np. do obrazowania przestrzeni. Zmienną będącą dwuwymiarową tablicą liczb całkowitych definiuje się tak:

int[][] vec = new int[10][10];

Tak zdefiniowana tablica jest tablicą kwadratową - ma tyle samo wierszy co kolumn. Trzeba pamiętać, że w przypadku tablic współrzędne są rozmieszczone na odwrót, to znaczy zazwyczaj przy podawaniu współrzędnych pierwsza liczba jest wpółrzędną X, czyli szerokością (ilością kolumn) a druga współrzędną Y, czyli wysokością (ilością wierszy). W przypadku tablic dwuwymiarowych jest odwrotnie. Pierwsza liczba jest ilością wierszy, a druga ilością kolumn.

Tutaj też dostępna jest zmienna oznaczająca długość tablicy. Ale tutaj wygląda to trochę inaczej, ponieważ ilość wierszy jest stała, ale długość każdego wiersza może być różna (tzw. tablica szarpana). Dlatego ilość wierszy uzyskuje się przez vec.length a liczbę kolumn w danym wierszu uzyskuje się przez vec[numerWiersza].length.

Jak przejść przez tablicę dwuwymiarową? Do tego potrzebne są dwie pętle, jedna zagnieżdżona w drugiej.

for(int i = 0; i < vec.length ; i++){
   for(int j = 0; j < vec[i].length ; j++){
      // tutaj dostępny jest element vec[i][j]
   }
}

Także tablicę dwuwymiarową można zadeklarować przez podanie wartości.

int[][] vec = {
   { 1, 2, 3},
   { 2, 3, 4},
   { 3, 4, 5},
   { 4, 5, 6}
};

W ten sposób stworzona została tablica vec o czterech wierszach po trzy kolumny. W ten spsób można tworzyć też tablice szarpane:

int[][] vec = {
   { 1, 2 },
   { 2, 3, 4, 5 },
   { 3 }
};

Tablice można też tworzyć dwuetapowo. Pierwszym etapem będzie stworzenie tablicy odnośników na tablice:

int[][] vec = new int[10][];

Jak widać, vec jest już zdefiniowaną tablicą, ale nie jest tablicą dwuwymiarową. Czemu? Bo nie został stworzony drugi wymiar. Na razie jest to tablica 10 elementów, z których każdy jest odnośnikiem do miejsca w pamięci, w którym znajdować się będzie tablica liczb całkowitych. Teraz, mając taką tablicę odnośników można każdemu elementowi przypisać tablicę:

vec[0] = new int[10];
vec[1] = new int[5];
vec[2] = new int[1];

i tak dalej. Jak widać to też jest sposób na tworzenie tablic szarpanych. Można tak też stworzyć tablicę dwuwymiarową, w której każdy wiersz będzie losowej długości:

int[][] vec = int[10][];
for(int i = 0; i < vec.length; i++){
   vec[i] = new int[(int)(Math.random()*10)];
}

W powyższych przykładach wszystkie tablice są tablicami liczb całokowitych, ale mogą to być tablice dowolnych typów, np. liczb rzeczywistych czy stringów.

Po tym kawałku teorii trochę praktyki. Jednym z zadań domowych było napisanie funkcji, która pobierze jako parametr kwadratową tablicę dwuwymiarową i zwróci tablicę dwuwymiarową, ale niekoniecznie kwadratową. Tablica wyjściowa ma się mieć tyle wierszy ile tablica wejściowa, a w każdym wierszu ma być:

• Cały wiersz z tablicy wejściowej, jeśli jest to wiersz leżący po środku
  tablicy wejściowej
• Jeśli to nie jest środkowy wiersz, to w odpowiadającym mu wieszu tabeli
  wyjściowej ma być środkowy element z tego wiersza.

Sprawa nie jest taka prosta jak by się mogło wydawać, bo co będzie jeśli tabela ma parzystą liczbę wierszy lub kolumn? Wtedy nie ma jednego środkowego wiersza, więc trzeba zwrócić dwa środkowe wiersze. Może najlepiej pokazać to na przykładzie.

Tablica wejściowa:

1 2 3 4
2 3 4 5
3 4 5 6

Tablica wyjściowa:

2 3
2 3 4 5
4 5

Jak widać, tabela ma parzystą liczbę kolumn, więc konieczne jest zwrócenie w odpowiednich wierszach dwóch elementów. Tabela wejściowa ma nieparzystą liczbę wierszy, więc jest jeden wiersz który można z całą pewnością uznać za środkowy i on cały ma być przepisany do tablicy wyjściowej.

Ale jak się do tego zabrać? Jak wyliczyć środkowy element(y)? Wystarczy wpaść na pomysł. Wiersze/kolumny numerowane są od zera do (długość - 1). Załóżmy, że wiersz ma 5 elementów, więc numerowane są od zera do czterech. Środkowy element ma indeks 2. Co nam da dwójkę? Podzielenie indeksu ostatniego elementu na dwa ( (długość - 1)/2 ). To jest ten pierwszy, łatwiejszy przypadek, kiedy jest parzysta liczba elementów. Teraz rozpatrzmy przypadek parzystej liczby elementów. Teraz wiersz będzie miał 6 elementów, więc interesują nas elementy o indeksach 2 i 3. Dwójkę uzyskuje się podobnie: najwyższy indeks podzielony przez dwa - normalnie uzyskalibyśmy 2.5, ale że są to operacje na liczbach całkowitych, to wynik jest zaokrąglany do dwóch. A trójkę? Wystarczy do poprzednio uzyskanej liczby dodać jeden...

To była ta łatwiejsza część. Teraz jak zabrać się za konkretne napisanie funkcji? Na początek nagłówek funkcji:

int[][] kolwie(int[][] tab)
{

Już w tym momencie można wstępnie zadeklarować tablicę wyjściową, bo ilość wierszy jest znana - będzie taka sama jak w tablicy wejściowej:

int[][] out = new int[tab.length][];

Ja na początku wyliczyłem wszystkie wartości, żeby później nie zaciemniać kodu. A więc zadeklarowałem zmienne logiczne (boolean) np i np2. Zadeklarowana będą na samym początku funkcji. Pierwsza będzie oznaczała, czy liczba wierszy jest parzysta czy nie. Druga podobnie, tyle że dla liczby kolumn. Jak to zrobić? Proste. Liczba jest parzysta jeśli reszta z dzielenia tej liczby przez 2 jest równa 0. A więc:

boolean np  = false;
boolean np2 = false;
if(tab.length % 2 == 1)
   np = true;
if(tab[0].length % 2 == 1)
   np2 = true;

Można też od razu wyliczyć indeksy środkowych kolumn i wierszy.

int w1 = 0, w2 = 0, c1 = 0, c2 = 0;

// czy ilość wierszy jest nieparzysta
if(tab.length%2==1)
   np = true;

// niezależnie czy ilość wierszy jest parzysta czy nie, zawsze jeden
// element będzie na środku
w1 = (tab.length-1)/2;

// jeśli ilość wierszy jest parzysta, to znajdź też drugi numer kolumny
if(!np)
   w2 = ((tab.length-1)/2)+1;

// I teraz to samo dla kolumn
c1 = (tab[0].length-1)/2;

if(!np2)
   c2 = ((tab[0].length-1)/2)+1;

Teraz dostępne są następujące zmienne:

• np, np2 - wartości logiczne oznaczające czy odpowiednio
  liczba wierszy i kolumn jest parzysta
• c1 - numer środkowej kolumny
• c2 - numer ewentualnej drugiej środkowej kolumny
• w1 - numer środkowego wiersza
• w2 - numer ewentualnego drugiego środkowego wiersza

Mamy już wszystko czego potrzeba, więc można przystąpić do głównej pętli. Po kolei sprawdzamy każdy wiersz:

for(int i = 0; i < tab.length ; i++){

Jeśli jest pierwszym środkowym, albo drugim środkowym ale tylko w przypadku jeśli liczbą wierszy jest parzysta:

if( i == w1 || (i == w2 && !np) ){

...to trzeba skopiować cały wiersz. Najpierw trzeba zarezerwować miejsce w pamięci na nowy wiersz:

out[i] = new int[tab[i].length];

Teraz za pomocą prostej pętli kopiujemy element po elemencie:

for(int j = 0; j < tab[i].length ; j++){
   out[i][j] = tab[i][j];
}

Teraz trzeba rozpatrzyć pozostałe przypadki - czyli te, kiedy wiersz nie jest środkowy. Odpowiadające im wiersze tabeli wyjściowej będą miały 1 lub 2 elementy. A więc zaczynamy od else i rezerwujemy odpowiednią ilość miejsca w pamięci po czym przepisujemy odpowiednie elementy:

} else {
   if(np2){
      out[i] = new int[1];
      out[i][0] = tab[i][c1];
   } else {
      out[i] = new int[2];
      out[i][0] = tab[i][c1];
      out[i][1] = tab[i][c2];
   }
}

No i to już wszystko. Teraz trzeba zwrócić tablicę wyjściową. Posklejajmy funkcję w całość:

int[][] kolwie(int[][] tab)
{
   int[][] out = new int[tab.length][];
   boolean np  = false;
   boolean np2 = false;
   if(tab.length % 2 == 1)
      np = true;
   if(tab[0].length % 2 == 1)
      np2 = true;
   int w1 = 0, w2 = 0, c1 = 0, c2 = 0;

   if(tab.length%2==1)
      np = true;

   w1 = (tab.length-1)/2;
   if(!np)
      w2 = ((tab.length-1)/2)+1;

   c1 = (tab[0].length-1)/2;
   if(!np2)
      c2 = ((tab[0].length-1)/2)+1;
   for(int i = 0; i < tab.length ; i++){
      if( i == w1 || (i == w2 && !np) ){
         out[i] = new int[tab[i].length];
         for(int j = 0; j < tab[i].length ; j++){
            out[i][j] = tab[i][j];
         }
      } else {
         if(np2){
            out[i] = new int[1];
            out[i][0] = tab[i][c1];
         } else {
            out[i] = new int[2];
            out[i][0] = tab[i][c1];
            out[i][1] = tab[i][c2];
         }
      }
   }
   return out;
}

No i to na tyle. Jak się komuś będzie nudziło, to niech spróbuje przerobić tą funkcję tak, żeby działała dla tablic szarpanych.