Struktury danych/Tablice

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Tablice

Załóżmy, że nasz program wczytał pewien zbiór danych tego samego typu, do którego elementów potrzebny jest szybki dostęp oraz o którym wiemy, że nie będzie modyfikowany. Do jego przechowywania najlepiej nadają się tablice - pierwsza, a zarazem najprostsza ze struktur danych. Jest więcej niż prawdopodobne, że spotkałeś się już z nimi, ponieważ praktycznie każdy język programowania oferuje dla nich wbudowane wsparcie. Każdy element tablicy posiada swój unikalny indeks, który określa jego położenie w tablicy. Oto prosty przykład tablicy jako zbioru argumentów pewnej funkcji matematycznej:

Indeks	0	1	2	3	4	5	6	7
Wartość	6	2	5	4	3	3	8	1

Indeks może pełnić tutaj rolę argumentu funkcji.

Istnieją także tablice wielowymiarowe, w których do identyfikacji elementu używany jest więcej niż jeden indeks. Przykładem tablicy dwuwymiarowej może być np. szkolna tabliczka mnożenia.

Cechy tablic

Charakterystyczne cechy tablic to:

• Stały rozmiar deklarowany przy tworzeniu tablicy, co znacznie utrudnia jej wykorzystanie w przypadku zmieniających się zbiorów, do których dodajemy bądź usuwamy elementy.
• Do każdego elementu gwarantowany dostęp w stałym czasie - dzięki konieczności wstępnego określenia rozmiaru tablica może zajmować ciągły obszar pamięci. W ten sposób odnalezienie elementu o podanym indeksie sprowadza się do prostego przemnożenia rozmiaru elementów przez indeks i odczytaniu danych spod otrzymanego adresu pamięci.

Na tablicach można wykonać następujące operacje (przy czym wcześniej omawiana INSERT oraz SEARCH można obecnie utożsamić z READ i WRITE) :

Tablica

• CREATE(t: Array; s:Integer) - tworzy tablicę t liczącą sobie s elementów
• DESTROY(t: Array;) - usuwa tablicę t
• READ(t: Array; i: Integer) - odczytuje wartość elementu o indeksie i
• WRITE(t: Array; i: Integer; d: Data) - zapisuje wartość d ("Data" możesz zastąpić przez dowolny typ, jaki potrzebujesz) do elementu tablicy o indeksie i

Zauważ, że nie mamy tutaj żadnej operacji "zerującej" zawartość tablicy. Wynika to z tego, iż w myśl definicji tablica posiada zawsze stałą liczbę elementów. Jeżeli masz do przechowania mniej informacji, możesz wykonać to na kilka sposobów:

• Dodatkowa zmienna przechowująca ilość faktycznie wykorzystanych elementów tablicy - rozwiązanie to wymaga, aby zajęte elementy były ułożone w tablicy w sposób ciągły, a niewykorzystane znajdowały się zawsze na końcu, jednak zawsze mamy szybki dostęp do informacji o wykorzystaniu tablicy.
• Wybranie jakiejś specyficznej wartości, np. 0 na reprezentowanie "pustych" elementów, które można wykorzystać. Dane mogą być przechowywane wtedy w sposób nieciągły.

Łącząc oba sposoby, łączymy jednocześnie ich zalety.

Dodatkowe informacje

Jak pokazaliśmy wyżej, tablica służy do przechowywania elementów w pewnych ciągłych obszarach pamięci, z tego wynika, że (w sporej części języków, np. C++) jest to struktura statyczna, tzn. nie można dowolnie powiększać jej rozmiaru, bez przekopiowywania wszystkich elementów do innego, większego obszaru w pamięci. Oczywiście, twórcy języków oferują rozwiązania, które pozwalają na pewną symulację zbioru dynamicznego, który zachowywałby się podobnie do tablicy, w standardowej bibliotece języka C++ znajduje się na przykład szablon std::vector kontenera o właściwościach podobnych do tablicy.

Implementacja

Tablice są wbudowane w niemal wszystkie języki programowania i w zasadzie nie trzeba ich samodzielnie implementować. Należy mieć na uwadze pewne różnice w implementacjach, np. Pascal dopuszcza możliwość ustalenia zakresu indeksów, podczas gdy w C/C++ elementy indeksowane są zawsze od 0. Język C++ dodatkowo posiada bardzo wygodną w użyciu i szybką implementację tablic przy pomocy pojemników (np. vector). Niektóre języki skryptowe posunęły się dalej i zlikwidowały ograniczenie stałego rozmiaru tablicy oraz typu indeks pozwalając na używanie tzw. tablic asocjacyjnych (np. PHP, który automatycznie potrafi dostosować rozmiar do ilości elementów). W rzeczywistości jednak ich interpretery implementują takie tablice jako bardziej złożone struktury danych, np. tablice haszujące.

Unikalność elementów

Tablica jest świetnym sposobem na implementację zbioru. W kontekście tablic powoduje to jednak pewne utrudnienia jak chodzi o operację wstawiania, ponieważ jak wiadomo w zbiorze jako obiekcie matematycznym elementy się nie powtarzają, powoduje to, że operacja wstawiania do zbioru nie posortowanego będzie mieć złożoność liniową ze względu na konieczność sprawdzenia czy dany element nie występuje w tablicy. Jak pokazujemy niżej można ulepszyć tą złożoność do rzędu $O(log(n))$.

Tablice posortowane

Zastanówmy się teraz jak zmieniłyby się nasze możliwości, gdybyśmy zamiast losowo uszeregowanych elementów w tablicy trzymali elementy zawsze posortowane zgodnie z jakimś porządkiem.

Przede wszystkim możliwość wyszukiwania elementu w takiej tablicy byłaby asymptotycznie znacząco szybsza. Zwyczajowo, mówiąc "tablica posortowana", myśli się o tablicach posortowanych rosnąco. Rozważmy teraz algorytm znajdowania elementu o zadanej wielkości w tablicy posortowanej rosnąco.

Wyszukiwanie połówkowe

Zwane również wyszukiwaniem binarnym (ang. binary search) wykorzystuje w swoim działaniu fakt, że znamy wielkość naszej tablicy oraz to że wraz ze wzrostem wartości rośnie również wielkość indeksu, pod którym przechowujemy elementy. Algorytm ten działa w czasie logarytmicznym, tzn. dla posortowanej tablicy przechowującej milion elementów, sprawdzenia będzie wymagało około 20 elementów ( bo $log_{2}(1\,000\,000)\approx 20$ ).

template <typename typ>
int binarySearch(typ tab[], typ klucz, int imin, int imax)
{
 //przeszukuj tak długo aż [imin,imax] nie jest pusty
 while (imin <=imax)
   {
      //znajdź środek przedziału, na którym szukamy
      int mid = (imax + imin + 1)/2;
      if (tab[mid] == klucz)
      // klucz znaleziono pod indeksem mid
        return mid;
      else if (tab[mid] < klucz)
      // ustal, w której połówce zakresu szukać dalej
           imin = mid + 1;
      else
           imax = mid - 1;
   }
   return KEY_NOT_FOUND;
}

Zastanówmy się teraz nad pewnym przykładem działania tej funkcji. Weźmy na przykład tablicę takich elementów :

	1	3	4	6	7	8	10	13	14

Załóżmy teraz, że chcemy ustalić pod którym indeksem znajduje się element o wartości 4. Prześledźmy działanie programu krok po kroku. Argumenty funkcji w pierwszym wywołaniu miałyby następujące wartości: $klucz=3,imin=0,imax=8$ z czego wynika, że warunek pętli oczywiście zachodzi.

while (imin <= imax)
{

 int mid = (8 - 0 + 1) / 2; // czyli 4 przy dzieleniu całkowitoliczbowym
...

W tym momencie będziemy porównywać klucz z wartością w tablicy o indeksie 5 czyli :

	(1	3	4	6	7	[8]	10	13	14)

Oczywiście 3 jest różne od 8 oraz dodatkowo jest od niej mniejsze. Z tego powodu będziemy zawężać zakres poszukiwań do lewej podtablicy:

	(1	3	4	6	7	)[8]	10	13	14

Teraz ponownie wykonujemy sprawdzanie warunku pętli $imin=0$ (dalej), ale teraz $imax=4$, co nie wpływa na wykonywanie bo $imin\leq imax$ jest prawdą. Tym razem wartość mid będzie wynosić 2, więc trafimy w to miejsce w pamięci:

	(1	3	[4]	6	7)	8	10	13	14

$3<4$, więc znów obcinamy zakres do lewej podtablicy.

	(1	3	) [4]	6	7	8	10	13	14

Kolejne wywołanie pętli, warunek nadal jest prawdziwy $(0\leq 2$). Tym razem $mid$ przyjmie wartość 1.

	(1	[3]	) 4	6	7	8	10	13	14

Świetnie! Znaleźliśmy indeks, pod którym znajduje się element o wartości 3. Teraz funkcja zwróci wartość 1.

Ćwiczenia

Podstawowe

Ćwiczenie 1: Napisz funkcję do zmiany rozmiaru tablicy poprzez utworzenie nowej kopii oraz przeniesienie do niej danych. Zastanów się jak będzie się ona zachowywać, jeżeli nowy rozmiar będzie mniejszy od ilości już przechowywanych w niej elementów? Jak będzie się zachowywać, jeżeli dopuścisz możliwość nieciągłego ułożenia elementów?

Ćwiczenie 2: Napisz rekurencyjną wersję wyszukiwania binarnego.

Zaawansowane

Ćwiczenie 1: Napisz funkcję implementującą algorytm wyszukiwania interpolacyjnego. Jest to bardzo podobny w działaniu do wyszukiwania binarnego algorytm służący do przeszukiwania tablicy. Jego złożoność w optymistycznym wypadku jest nawet lepsza od tego pierwszego, bo wynosi $O(log(log(n)))$. Wykorzystaj fakt, że w posortowanej tablicy, przy założeniu jednostajnego rozkładu danych, przyrost na wartości indeksu powinien być porównywalny do przyrostu na wartości znajdującej się pod tym indeksem.

Wskazówka. Typowanie nowego klucza, pod którym będziemy szukać wartości powinno zgadzać się z proporcją ${\frac {mid-imin}{imax-imin}}={\frac {klucz-tab[imin]}{tab[imax]-tab[imin]}}$.