Struktury danych — definicja, zastosowania i przykłady w informatyce

Array

Najprostszym typem struktury danych jest tablica liniowa. Znana również jako tablica jednowymiarowa. Tablica przechowuje kilka wartości tego samego typu (Integer, Floats, String, itd.). Dostęp do elementów wewnątrz tablicy jest bardzo szybki. Tablica ma zazwyczaj stały rozmiar. Po tym, jak rozmiar tablicy jest określony na początku, może nie być możliwe zwiększenie rozmiaru tablicy bez utworzenia nowej większej tablicy i skopiowania wszystkich wartości do nowej tablicy. W informatyce, macierzowa struktura danych lub po prostu tablica jest strukturą danych składającą się z kolekcji elementów (wartości lub zmiennych), z których każdy jest identyfikowany przez co najmniej jeden indeks tablicy lub klucz. Tablica jest przechowywana w taki sposób, że pozycja każdego elementu może być obliczona z jego indeksu tuple za pomocą formuły matematycznej.

Na przykład, tablica 10 zmiennych całkowitych o indeksach od 0 do 9 może być przechowywana jako 10 słów pod adresami pamięci 2000, 2004, 2008, 2036, tak że element o indeksie i ma adres 2000 + 4 × i.

Ponieważ matematyczna koncepcja macierzy może być reprezentowana jako dwuwymiarowa siatka, dwuwymiarowe tablice są również czasami nazywane macierzami. W niektórych przypadkach termin "wektor" jest używany w informatyce w odniesieniu do tablicy, chociaż tuple, a nie wektory są bardziej poprawnym odpowiednikiem matematycznym. Tablice są często używane do implementacji tablic, zwłaszcza tablic wyszukujących; słowo tablica jest czasami używane jako synonim tablicy.

Tablice są jedną z najstarszych i najważniejszych struktur danych i są używane przez prawie każdy program. Mogą być również używane do implementacji wielu innych struktur danych, takich jak listy i łańcuchy. Efektywnie wykorzystują one logikę adresowania komputerów. W większości nowoczesnych komputerów i wielu zewnętrznych urządzeń pamięciowych, pamięć jest jednowymiarową tablicą słów, których indeksami są ich adresy. Procesory, zwłaszcza wektorowe, są często zoptymalizowane do operacji tablicowych.

Tablice są użyteczne, ponieważ indeksy elementów mogą być obliczane w czasie pracy. Między innymi ta cecha pozwala pojedynczemu poleceniu iteracyjnemu przetworzyć dowolnie wiele elementów tablicy. Z tego powodu wymaga się, aby elementy struktury danych tablicy miały ten sam rozmiar i powinny używać tej samej reprezentacji danych. Zbiór poprawnych krotek indeksowych i adresy elementów (a więc i formuła adresowania elementów) są zazwyczaj, ale nie zawsze, stałe podczas użytkowania tablicy.

Termin tablica jest często używany do określenia tablicowego typu danych, rodzaju typu danych dostarczanego przez większość języków programowania wysokiego poziomu, który składa się z kolekcji wartości lub zmiennych, które mogą być wybrane przez jeden lub więcej indeksów obliczanych w czasie wykonywania. Typy tablicowe są często implementowane przez struktury tablicowe; jednak w niektórych językach mogą być implementowane przez tablice hash, listy połączone, drzewa wyszukiwania lub inne struktury danych.

Lista połączona

Połączona struktura danych to zbiór informacji/danych połączonych ze sobą za pomocą odniesień. Dane są często nazywane węzłami. Odniesienia są często nazywane odnośnikami lub wskaźnikami. Od tej pory słowa węzeł i wskaźnik będą używane dla tych pojęć.

W połączonych strukturach danych, wskaźniki są tylko dereferencjonowane lub porównywane dla równości. Tak więc połączone struktury danych różnią się od tablic, które wymagają dodawania i odejmowania wskaźników.

Listy połączone, drzewa wyszukiwania i drzewa wyrażeń są wszystkimi połączonymi strukturami danych. Są one również ważne w algorytmach takich jak sortowanie topologiczne i szukanie unii zbiorów.

Stack

Stos jest podstawową strukturą danych, która może być logicznie myślana jako struktura liniowa reprezentowana przez rzeczywisty fizyczny stos lub stos, strukturę, w której wstawianie i usuwanie elementów odbywa się na jednym końcu zwanym wierzchołkiem stosu. Podstawowa koncepcja może być zilustrowana przez myślenie o twoim zestawie danych jako stosie talerzy lub książek, gdzie możesz tylko zdjąć górny element ze stosu, aby usunąć z niego rzeczy. Ta struktura jest używana przez całe programowanie.

Podstawowa implementacja stosu jest również nazywana strukturą "Last In First Out"; istnieją jednak różne odmiany implementacji stosu.

Istnieją zasadniczo trzy operacje, które można wykonać na stosach. Są to:

• wstawianie ("pchanie") elementu na stos
• usuwanie ("wyskakiwanie") elementu ze stosu
• wyświetlanie zawartości najwyższego elementu stosu ("peeking")

Kolejka

Kolejka jest abstrakcyjnym typem danych lub liniową strukturą danych, w której pierwszy element jest wstawiany z jednego końca ("ogon"), a usuwanie istniejącego elementu odbywa się z drugiego końca ("głowa"). Kolejka jest strukturą typu "First In First Out". "First In First Out" oznacza, że elementy włożone do kolejki jako pierwsze wyjdą jako pierwsze, a elementy włożone do kolejki jako ostatnie wyjdą jako ostatnie. Przykładem kolejki są linie oczekujących osób. Pierwsza osoba w kolejce wychodzi jako pierwsza, a ostatnia jako ostatnia.

Proces dodawania elementu do kolejki nazywany jest "enqueuing", a proces usuwania elementu z kolejki nazywany jest "dequeuing".

Wykres

Graf jest abstrakcyjnym typem danych, który ma na celu implementację koncepcji grafu i hipergrafu z matematyki.

Struktura danych grafu składa się ze skończonego (i ewentualnie zmiennego) zbioru uporządkowanych par, zwanych krawędziami lub łukami, pewnych jednostek zwanych węzłami lub wierzchołkami. Podobnie jak w matematyce, krawędź (x,y) jest powiedziane, aby wskazać lub przejść z x do y. Węzły mogą być częścią struktury grafu lub mogą być zewnętrznymi jednostkami reprezentowanymi przez indeksy całkowite lub odniesienia. Struktura danych grafu może również przypisywać każdej krawędzi pewną wartość krawędzi, taką jak etykieta symboliczna lub atrybut numeryczny.

Drzewo

Drzewo jest jedną z najpotężniejszych zaawansowanych struktur danych. Często pojawia się w zaawansowanych tematach, takich jak sztuczna inteligencja (AI) i projektowanie. Zaskakująco, drzewo jest ważne w znacznie bardziej podstawowym zastosowaniu - prowadzeniu wydajnego indeksu.

Gdy używane jest drzewo, istnieje duże prawdopodobieństwo, że używany jest indeks. Najprostszym typem indeksu jest posortowana lista pól kluczowych. Drzewo zazwyczaj ma określoną strukturę. W przypadku drzewa binarnego, możesz użyć wyszukiwania binarnego, aby zlokalizować dowolny element bez konieczności przeglądania każdego elementu.

Typ danych drzewo jest rodzajem grafu, co oznacza, że wiele algorytmów stworzonych w celu przemierzania grafu działa również z drzewem, jednakże algorytmy mogą być bardzo podobne i muszą mieć dedykowany węzeł startowy, czyli węzeł, do którego nie ma żadnych innych węzłów łączących się z nim.

Problem z prostą uporządkowaną listą pojawia się, gdy zaczynasz dodawać nowe elementy i musisz utrzymać listę posortowaną - można to zrobić w miarę wydajnie, ale wymaga to pewnych modyfikacji. Dodatkowo, indeks liniowy nie jest łatwy do współdzielenia, ponieważ cały indeks musi być "zablokowany", gdy jeden użytkownik go edytuje, podczas gdy jedna "gałąź" drzewa może być zablokowana, pozostawiając inne gałęzie edytowalne przez innych użytkowników (ponieważ nie mogą być dotknięte).

Tabela Hash

Tablica hash jest tablicą, w której każdy indeks wskazuje na listę połączoną w oparciu o wartość hash. Wartość haszująca jest wartością określoną przez funkcję haszującą. Funkcja hash określa unikalną wartość na podstawie danych, które przechowuje. Pozwala to na dostęp do danych w stałym czasie, ponieważ komputer zawsze wie, gdzie szukać.