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

Grafika przedstawia listę cztero‑elementową zapisaną w małej siatce jednorzędowej: 2, 5, 7, 1. Elementy mają indeksy od 0 do 3.

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ść $0$ bądź $1$. 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 $0$):

tab[] ← {1, 2, 5}	// 3 elementowa tablica liczb

tab[0] ← 3
a ← tab[0] + tab[2]
wypisz(a)			// 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:

Struktura Punkt {
	wsp_x			// piersza składowa
	wsp_y			// druga składowa
}

Punkt a
a.wsp_x ← 1
a.wsp_y ← (a.wsp_x + 3)

wypisz(a.wsp_y)		// 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

Grafika przedstawia kwadraty, które przedstawiają fragmenty pamięci przechowujące różne wartości. Przedstawiono podział na dwie listy, górną i dolną, górna posiada kwadraty, z których poprzedni wskazuje na następny element pojedynczą strzałką. Dolna lista zaś, posiada strzałki dwukierunkowe, element następny wskazuje na poprzedni jak i na odwrót. Wartości wpisane w górnej liście to 8 wskazuje na 2, które wskazuje na 4, następnie na 3 i na końcu 10. Lista dolna, 15, 6, 7, 1 oraz 9.

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

Ilustracja przedstawia prostokąty ilustrujące elementy stosu, które tworzą kolumnę, na szczycie której, widoczne 2 prostokąty, jeden z podpisem "dodaj", drugi z "usuń". Pierwszy posiada strzałkę wskazującą od prostokątu na stos, drugi odwrotnie.

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

Ilustracja przedstawiająca rząd prostokątów, po lewej stronie napis "KONIEC" do którego kieruje strzałka z napisem "dodaj". Po prawej stronie napis "POCZĄTEK", od którego kieruje strzałka na wolny element z napisem "usuń".

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

Ilustracja przedstawia okręgi, które tworzą graf, w środku znajdują się litery alfabetu: A, B, C oraz D. Ułożone w kształcie kwadratu są okręgu A, B oraz C. Strzałki pomiędzy kolejnymi elementami mają liczby, niektóre z tych strzałek są dwukierunkowe, inne jedno. Strzałka z napisem 3 wychodzi i zawraca do A, podczas gdy numer 2 wychodzi z litery B i wskazuje na literę C, a 4 wychodzi z litery C i wskazuje A. Strzałka 10 jest dwukierunkowa i wskazuje pomiędzy A i B. Do litery D nie wskazuje żadna strzałka.

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

Ilustracja przedstawia okręgi połączone strzałkami. Na górze znajduje się jeden okrąg oznaczony napisem "korzeń", z niego wyprowadzone są 3 strzałki, każda wskazuje na nowy okrąg. Poszczególne kolejne okręgi mogą wskazywać na wiele kolejnych, bądź też zakończyć wskazywanie, każdy z takich końcowych elementów nazywany jest liściem.

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