W moim poprzednim poście opisałem w skrócie, czym są „algorytmy”. Teraz możemy porozmawiać o tym, czym są struktury danych, jak odnoszą się one do algorytmów i uzyskać krótki przegląd różnych struktur danych, z którymi się spotkasz.

Struktura danych polega na pobieraniu danych i organizowaniu ich, zarządzaniu lub przechowywaniu w formacie umożliwiającym łatwy dostęp i modyfikację. Wykonywanie określonych operacji obejmuje uzyskiwanie dostępu, modyfikowanie, a nawet usuwanie tych danych.

Poniżej znajduje się bardzo prosta definicja struktur danych i algorytmów oraz ich wzajemne powiązania:

  • Struktura danych polega na skutecznym organizowaniu danych i zarządzaniu nimi, abyśmy mogli efektywnie wykonywać określone operacje. Algorytm to procedura krok po kroku, którą należy wykonać, aby osiągnąć pożądany wynik.
  • Kroki algorytmu wykorzystują jedną lub wiele struktur danych do rozwiązania problemu.

Świetnie, teraz, gdy mamy podstawową wiedzę na temat dwóch różnych, ale powiązanych elementów, poniżej znajduje się lista typowych struktur danych, z którymi będziesz się spotykać, aby poradzić sobie z tymi jakże zabawnymi algorytmami!

Najpierw zrozummy, że istnieją różne rodzaje struktur danych, które nadają się do różnych zastosowań i ogólnie dzieli się je na dane liniowe i nieliniowe.

Liniowa struktura danych ma elementy danych ułożone sekwencyjnie, a każdy element składowy jest połączony z poprzednim i następnym elementem. Przechodzenie przez strukturę danych lub iteracja po strukturze danych, co oznacza „odwiedzanie” lub „dotykanie” każdego elementu struktury, ma charakter sekwencyjny. Te struktury danych są łatwe do wdrożenia, ponieważ pamięć komputera jest również sekwencyjna. Przykładami liniowych struktur danych są tablice, lista połączona, stos i kolejka.

Nieliniowe struktury danych nie są ułożone sekwencyjnie ani liniowo. Każdy element może mieć wiele ścieżek do połączenia z innymi elementami. Nie można iterować ani przechodzić przez wszystkie elementy w jednym przebiegu. Nieliniowe struktury danych nie są łatwe do wdrożenia, ale skuteczniej wykorzystują pamięć komputera. Przykładami nieliniowych struktur danych są drzewa i wykresy.

Przyjrzyjmy się pokrótce różnym strukturom danych:

Tablica

  • Tablica to najprostszy typ struktury danych, w którym przechowywane są elementy tego samego typu danych (liczba całkowita, liczba zmiennoprzecinkowa, ciąg znaków itp.)
  • Jest to liniowy typ danych
  • Dane przechowywane w każdej pozycji tablicy otrzymują wartość dodatnią zwaną indeksem.
  • Wartość indeksu zaczyna się od 0 dla pierwszego elementu tablicy.

Załóżmy, że mamy ceny 6 elementów spożywczych i ich pozycję w indeksie. Wszystkie liczby całkowite możemy przechowywać w tablicy.

Tablicę tę można zapisać w następujący sposób:

stała tablica = [10, 5, 23, 8, 12, 7]

Lista połączona

  • Lista połączona to rodzaj struktury danych składającej się z węzłów, a każdy węzeł „zna” adres następnego węzła. Dobrym przykładem może być połączenie kropek w celu stworzenia obrazu. Wiesz, jak połączyć kropki, ponieważ są ponumerowane.
  • Lista połączona to sekwencyjny zbiór elementów. Element jest przechowywany w postaci węzłów, które składają się z dwóch kluczowych informacji — samej wartości danych oraz wskaźnika / next, który odwołuje się do następnego węzła na liście.
  • Dane przechowywane na połączonej liście mogą mieć dowolną formę, ciągi, liczby lub znaki.
  • Listy połączone nie nadają się najlepiej do uzyskiwania bezpośredniego dostępu do elementu takiego jak tablica, ale są naprawdę wydajne przy wstawianiu i usuwaniu elementów ze względu na sposób, w jaki ich elementy są przechowywane w pamięci.
  • Istnieją dwa typy list połączonych — lista pojedynczo połączona, w której każdy węzeł ma jeden wskaźnik do następnego węzła na liście. Istnieje również podwójnie połączona lista, w której każdy węzeł ma wskaźnik do następnego węzła i drugi wskaźnik do poprzedniego węzła.

Główne właściwości struktury danych listy połączonej to:
- size: liczba elementów na liście połączonej
- head: pierwszy element na liście połączonej
- tail: ostatni element na połączonej liście

  • Pierwszy węzeł (zawierający 2) nazywany jest węzłem głównym, ponieważ żaden węzeł na niego nie wskazuje.
  • Węzeł 2 przechowuje adres węzła zawierający 4 i tak dalej.
  • Węzeł ogonowy wskazuje wartość null, co oznacza koniec listy.

Niektóre praktyczne zastosowania połączonej listy obejmują:

  • Obrazy są ze sobą powiązane, dzięki czemu oprogramowanie do obsługi obrazów korzysta z połączonej listy w celu przeglądania poprzednich i następnych obrazów.
  • Odtwarzacze muzyki również korzystają z listy połączonej do przełączania muzyki i często używana jest lista z łączami cyklicznymi.

Jeśli chcesz bardziej zagłębić się w listy połączone, zapoznaj się z tymi wspaniałymi zasobami:

NoobCoder — Lista połączona w JavaScript dla początkujących
Beiatrix — Listy połączone | Struktury danych w JavaScript

Tabela mieszająca

  • Struktura danych umożliwiająca utworzenie listy par klucz-wartość. Następnie możesz pobrać określoną wartość, używając klucza dla tej wartości.
  • Tabela mieszająca to struktura danych, która wykorzystuje funkcję mieszania do implementacji tablic asocjacyjnych lub mapowań par klucz-wartość
  • Funkcja skrótu lub hashowanie pobiera ciąg znaków, konwertuje go na jakąś liczbę całkowitą lub ciąg liter i cyfr, a następnie ponownie mapuje tę liczbę całkowitą na indeks.
  • Tabela skrótów zaczyna się od wielu symboli zastępczych zwanych zasobnikami, w których będzie przechowywana treść. Aby dodać dowolną parę klucz-wartość do tabeli mieszającej, bierzesz klucz i przekazujesz go przez funkcję mieszającą, która generuje liczbę odpowiadającą indeksowi w tablicy, w której będziemy przechowywać wartość

Jeśli chcesz uzyskać więcej informacji na temat tabel skrótów. Poniższy zasób pozwala głębiej zagłębić się w temat:

Informatyka — tablice mieszające i funkcje mieszające

Stos

  • Stos to struktura danych, która pomaga organizować dane w określonej kolejności i jest zgodna z zasadą „ostatnie weszło, pierwsze wyszło” (LIFO). Oznacza to, że ostatni element wstawiony do stosu jest usuwany jako pierwszy.
  • Pomyśl o stosie jako o stosie książek, z którego możesz zdjąć tylko wierzchni przedmiot ze stosu, aby usunąć z niego książki, a nową książkę możesz dodać tylko na górze. Ten rodzaj dostępu do danych nazywa się „ostatnie weszło, pierwsze wyszło”.

Kolejka

  • Liniowa struktura danych zgodna z zasadą „pierwsze weszło, pierwsze wyszło” (FIFO). Element wstawiony jako pierwszy jest usuwany jako pierwszy.
  • Typowymi przykładami kolejki są kolejki osób oczekujących na usługę lub coś do pobrania. Pierwsza osoba w kolejce obsługiwana jest jako pierwsza, natomiast osoba, która jest ostatnia w kolejce, jako ostatnia.

Wykres

  • Nieliniowa struktura danych składająca się ze skończonego zestawu wierzchołków (lub węzłów) i zestawu krawędzi łączących parę węzłów
  • Wykresy służą do przedstawiania sieci, takich jak ścieżki w mieście lub sieć telefoniczna. Wykorzystywane są także w sieciach społecznościowych Facebook i LinkedIn.

  • Na powyższym diagramie:
    Wierzchołki = {A, B, C, D, E
    Krawędzie = {AB, BE, ED, DC, CA, AD, BD}

Drzewo

  • Nieliniowa hierarchiczna struktura danych składająca się z węzłów połączonych krawędziami. Każdy węzeł zawiera wartość lub dane i może mieć węzeł podrzędny lub nie.
  • Przykładem organizacji hierarchicznej jest drzewo genealogiczne, w HTML — Document Object Model (DOM) działa jak drzewo.

Masz tam podstawowy przegląd różnych typów struktur danych, których możesz użyć w swoich algorytmach do rozwiązywania różnych problemów! Następnie zajmiemy się złożonością czasu i przestrzeni.