Struktury danych/Tablice

Z Wikibooks, biblioteki wolnych podręczników.

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

Spis treści 1 Tablice 1.1 Cechy tablic 1.2 Implementacja 1.3 Ćwiczenia

[edytuj] 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.

[edytuj] 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:

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

[edytuj] 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.

[edytuj] Ćwiczenia

Ć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?