Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Struktury danych liniowe

21 pojęć w 5 podgrupach, z prostymi definicjami i źródłami.

Abstrakcyjne typy liniowe · 5

  • 01kolejkaFIFO → kolejkaLiniowa struktura o dyscyplinie FIFO: element pierwszy włożony jest pierwszym usuwanym; wstawianie na końcu, pobieranie z początku.
  • 02kolejka dwustronnadeque → kolejka dwustronnaKolejka pozwalająca wstawiać i usuwać elementy z obu końców (z ang. deque).
  • 03kolejka priorytetowaStruktura, w której każdy element ma priorytet, a pobierany jest zawsze element o najwyższym (lub najniższym) priorytecie.
  • 04stosLIFO → stosLiniowa struktura o dyscyplinie LIFO: element ostatnio włożony jest pierwszym usuwanym; operacje push i pop działają na jednym końcu.
  • 05tablica asocjacyjnamapa → tablica asocjacyjnaStruktura odwzorowująca klucze na wartości, umożliwiająca wyszukiwanie wartości po kluczu.

Listy · 5

  • 01listaUporządkowany ciąg elementów wspierający wstawianie, usuwanie i przeglądanie w kolejności liniowej.
  • 02lista cyklicznaLista powiązana, w której ostatni węzeł wskazuje na pierwszy, tworząc zamknięty pierścień bez wyróżnionego końca.
  • 03lista dwukierunkowaLista powiązana, w której każdy węzeł ma wskaźniki do następnika i poprzednika, umożliwiając przechodzenie w obu kierunkach.
  • 04lista powiązanaLiniowa struktura, w której każdy element (węzeł) przechowuje dane oraz wskaźnik do następnego węzła, bez wymogu ciągłości w pamięci.
  • 05lista z przeskokamiskip list → lista z przeskokamiProbabilistyczna struktura listowa z wieloma warstwami wskaźników, umożliwiająca wyszukiwanie i wstawianie w oczekiwanym czasie logarytmicznym.

Podstawy pojeciowe · 4

  • 01abstrakcyjny typ danychADT → abstrakcyjny typ danychModel danych zdefiniowany przez zbiór wartości i operacje na nich, niezależny od konkretnej implementacji.
  • 02analiza zamortyzowanaMetoda wyznaczania średniego kosztu operacji w ciągu działań na strukturze, gdzie kosztowne operacje są równoważone wieloma tanimi.
  • 03przepełnienie stosustack overflow → przepełnienie stosuStan błędu polegający na próbie włożenia elementu na stos, który osiągnął maksymalną pojemność.
  • 04struktura danych liniowaStruktura, w której elementy tworzą uporządkowany ciąg, gdzie każdy element ma co najwyżej jednego następnika i jednego poprzednika.

Reprezentacje liniowe · 5

  • 01bufor cyklicznybufor pierścieniowy → bufor cyklicznyBufor o stałym rozmiarze traktowany jako pierścień, w którym po osiągnięciu końca zapis wraca na początek; realizuje kolejkę FIFO na tablicy.
  • 02łańcuch znakówstring → łańcuch znakówSkończony, uporządkowany ciąg znaków z ustalonego alfabetu, traktowany jako liniowa sekwencja.
  • 03wartowniksentinel → wartownikFikcyjny węzeł graniczny upraszczający operacje na strukturze powiązanej przez wyeliminowanie przypadków brzegowych, np. pustej listy.
  • 04węzełPodstawowy element struktury powiazanej, przechowujacy dane oraz wskaznik (lub wskazniki) do innych elementow tej struktury.
  • 05wskaźnikWartość przechowująca adres innego obiektu w pamięci, używana do łączenia węzłów struktur powiązanych.

Tablice · 2

  • 01tablicaStruktura przechowująca elementy tego samego typu w ciągłym obszarze pamięci, z dostępem do dowolnego elementu w czasie stałym po indeksie.
  • 02tablica dynamicznaTablica o zmiennej pojemności, automatycznie powiększana (zwykle przez podwajanie) przy braku miejsca, dająca zamortyzowany stały koszt dopisania na końcu.

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych21 haseł