Rodzaje podstawowych struktur danych

W tym e‑materiale omówimy koncepcyjnie różne rodzaje podstawowych struktur danychstruktura danychstruktur danych. Nie będziemy zagłębiać się w szczegóły implementacyjne, ponieważ mogą się one różnić w zależności od wykorzystywanego języka programowania.

Tablica

Tablica jest strukturą danych, która przechowuje wiele elementów tego samego typu. Powiedzmy, że chcemy w naszym programie pracować na milionie zmiennych całkowitych. Deklarowanie każdej z nich osobno zajęłoby ogromną ilość czasu. Na szczęście możemy przy pomocy jednej instrukcji utworzyć strukturę danych, która będzie się składać z miliona komórek, a w każdej z nich będzie przechowywana jedna liczba całkowita.

RkuwzoFdztkWT
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Wartości w tablicy są przechowywane w pewnym porządku, każda komórka przechowująca wartość ma swój indeks. W zależności od języka programowania pierwszy indeks ma wartość bądź . Aby odwołać się do konkretnej komórki, zazwyczaj korzystamy z instrukcji: nazwa_tablicy[indeks].

Przykład użycia tablicy w pseudokodzie (zakładamy, że indeksujemy od ):

Linia 1. tab otwórz nawias kwadratowy zamknij nawias kwadratowy ← otwórz nawias klamrowy 1 przecinek 2 przecinek 5 zamknij nawias klamrowy prawy ukośnik prawy ukośnik 3 elementowa tablica liczb. Linia 3. tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy ← 3. Linia 4. a ← tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy plus tab otwórz nawias kwadratowy 2 zamknij nawias kwadratowy. Linia 5. wypisz otwórz nawias okrągły a zamknij nawias okrągły prawy ukośnik prawy ukośnik wypisze liczbę 8.

Struktura

Załóżmy, że w naszym programie chcielibyśmy zaimplementować algorytm pracujący na punktach na płaszczyźnie. Będą one reprezentowane w postaci współrzędnych. Używanie zwykłej tablicy jest możliwe, ale niezbyt wygodne. Możemy za to skorzystać z typu danych zwanego strukturą. W jednym obszarze pamięci może przechowywać logicznie powiązane ze sobą dane tych samych lub różnych typów.

Struktura umożliwia więc grupowanie logicznie powiązanych ze sobą informacji różnego typu i tym samym opisywanie złożonych obiektów.

Poszczególne składowe struktury (pola) są etykietowane, czyli mają swoje unikatowe nazwy, za których pomocą możemy się do nich odwoływać. Dla lepszego zrozumienia przeanalizujmy poniższy pseudokod:

Linia 1. Struktura Punkt otwórz nawias klamrowy. Linia 2. wsp podkreślnik x prawy ukośnik prawy ukośnik piersza składowa. Linia 3. wsp podkreślnik y prawy ukośnik prawy ukośnik druga składowa. Linia 4. zamknij nawias klamrowy. Linia 6. Punkt a. Linia 7. a kropka wsp podkreślnik x ← 1. Linia 8. a kropka wsp podkreślnik y ← otwórz nawias okrągły a kropka wsp podkreślnik x plus 3 zamknij nawias okrągły. Linia 10. wypisz otwórz nawias okrągły a kropka wsp podkreślnik y zamknij nawias okrągły prawy ukośnik prawy ukośnik wypisze liczbę 4.

Oczywiście, jeżeli potrzebujemy przechowywać dużą ilość punktów, możemy skorzystać z tablicy struktur. Działa ona tak samo jak zwykła tablica, tyle że przechowuje obiekty o typie naszej struktury.

Plik

Kolejną podstawową strukturą do przechowywania danych jest plik. Plik jest typem ciągłej, sekwencyjnej struktury danych o dowolnie dużym rozmiarze. Na plikach są dozwolone następujące podstawowe operacje:

  • utworzenie nowego pliku,

  • otworzenie istniejącego pliku,

  • odczyt danych z otwartego pliku,

  • zapis danych do otwartego pliku,

  • zamknięcie otwartego pliku,

  • usunięcie istniejącego pliku.

Pliki pozwalają zatem programowi na zapis i odczyt danych z zewnętrznych źródeł. Załóżmy, że napisaliśmy program, który tworzy grafikę, korzystając ze znaków ASCIIASCIIASCII i chcemy wysłać przykładową ilustrację naszemu znajomemu. Zamiast przesyłać cały program, możemy po prostu zapisać jego wynik do zewnętrznego pliku tekstowego, a następnie go przesłać.

W formie plików możemy także przechowywać dane wejściowe do naszych programów, dzięki temu nie musimy ich ręcznie wprowadzać przy każdym uruchomieniu. Pliki są dla naszego programu pewnego rodzaju zewnętrznym nośnikiem danych.

Lista

Lista jest nieco bardziej zaawansowaną strukturą danych w porównaniu do zwykłych tablic czy struktur. Przede wszystkim jest ona dynamiczna, to znaczy, że jej rozmiar może się zmieniać w trakcie działania programu. Jej główną cechą jest to, że przechowywane elementy są ułożone w liniowym porządku oraz są ze sobą wzajemnie powiązane. Poszczególne elementy listy to struktury przechowujące dane i zawierające pola wskazujące na sąsiednie elementy. Lista zawiera elementy tego samego typu.

Do konkretnych elementów listy nie możemy się odwołać wykorzystując odpowiedni indeks, tak jak mogliśmy to robić w przypadku tablic. Jako, że elementy są ułożone w określonym porządku, jedyną opcją jest przechodzenie do następnika lub poprzednika obecnie rozpatrywanego elementu.

R1b9VQ4bc4IZ2
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Wyróżnia się dwa rodzaje list: jednokierunkową oraz dwukierunkową. Różnią się one możliwością przemieszczania się po elementach listy. W liście jednokierunkowej możemy przechodzić jedynie do następnika, bez możliwości powrotu. Natomiast w dwukierunkowej możemy swobodnie przechodzić również do poprzednika.

Na liście możemy wykonywać operację dodawania oraz usuwania elementów. Dodatkowo możemy wygodnie łączyć ze sobą różne listy, oraz je rozdzielać.

Stos

Stos jest strukturą danych składającą się z elementów tego samego typu o dostępie LIFO (z ang. Last In, First Out). Tak samo jak lista, jest on dynamiczny. Jego nazwa jest analogiczna do działania. Mamy dostęp tylko i wyłącznie do elementu na samym szczycie stosu. Dodając element, dokładamy go na górę. Analogicznie operacja usunięcia elementu polega na zabraniu go ze szczytu stosu.

Nawiązuje do sposobu zapisywania i odczytywania elementów.

R1LjDhNzxfhdL
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Kolejka

Kolejka jest za to strukturą danych składającą się z elementów tego samego typu o dostępie FIFO (z ang. First In, First Out) i również jest dynamiczna. Jej działanie jest analogiczne do zwykłej kolejki, z którą możemy się spotkać w sklepie. Tylko pierwsza osoba jest obsługiwana, reszta czeka na swoją kolej. Każda nowa osoba ustawia się na końcu kolejki.

Dokładnie w taki sam sposób działa ta struktura. Operacja usunięcia elementu zabiera go z początku kolejki, natomiast dodawanie umieszcza go na samym końcu.

R1FGP4kS3YRpY
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Graf

Grafy są abstrakcyjną formą reprezentacji danych. Pozwalają one tworzyć, modelować i opisywać wszelkiego rodzaju sieci, w których występują skomplikowane zależności pomiędzy składnikami. Więcej na ich temat znajdziesz w e‑materiałach dotyczących teorii grafów. Podstawowe informacje znajdują się w e‑materiale Wprowadzenie do teorii grafówPiIOvtsALWprowadzenie do teorii grafów. Graf składa się z dwóch podstawowych rodzajów elementów, a mianowicie wierzchołków oraz krawędzi. Krawędzie reprezentują połączenie pomiędzy dwoma wierzchołkami, mogą one mieć swoją wagę, czy kierunek. Między wierzchołkami możemy się poruszać zgodnie z kierunkami łączących krawędzi.

RcavYEGS7zSJa
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Rozróżniamy różne rodzaje grafów m.in. skierowane, nieskierowane czy ważone. Przykładem grafu mogą być miasta wraz z łączącymi je drogami. Wagami krawędzi mogą być wtedy długości poszczególnych dróg.

Drzewo

Drzewo jest specjalnym rodzajem grafu. Jego najważniejszą cechą jest to, że istnieje dokładnie jedna droga między jego dowolnymi dwoma wierzchołkami. Dodatkowo wierzchołki drzewa, które nazywamy węzłami, są uporządkowane w pewnej hierarchii. Każdy węzeł z wyjątkiem korzenia i liści ma swojego ojca, czyli element znajdujący się nad nim oraz swoje dzieci, czyli elementy znajdujące się pod nim.

RAhIbk9Bc6lhA
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

W strukturze drzewa wyróżnia się jeden, charakterystyczny element nazywany korzeniem. Jego cechą jest to, że nie posiada on ojca. Dodatkowo węzły, które nie posiadają dzieci noszą nazwę liści.

Słownik

abstrakcyjny typ danych
abstrakcyjny typ danych

abstrakcyjny zbiór wartości i operacji na tych wartościach; stanowi szablon implementacyjny dla struktur danych

ASCII
ASCII

pierwotnie siedmiobitowy system kodowania znaków (współcześnie rozszerzony do ośmiu bitów); w oryginalnej wersji kodom z zakresu 0–127 przyporządkowano litery alfabetu łacińskiego, cyfry, znaki przestankowe oraz polecenia sterujące

paradygmat programowania
paradygmat programowania

wzorzec klasyfikujący języki programowania na podstawie ich własności; języki programowania mogą być sklasyfikowane do wielu różnych paradygmatów programowania

struktura danych
struktura danych

rzeczywista implementacja abstrakcyjnego typu danych