Duomenų struktūra

**Duomenų struktūra** (*duomenų tipas*) – duomenys, logiškai jungiantys keletą paprastųjų duomenų tipų (reikšmių) arba kelias paprastesnes duomenų struktūras.

Pirmosios duomenų struktūros naudotos tik kaip reikšmių aibės, bet vėliau pradėti naudoti **abstraktieji duomenų tipai** (ADT) apibrėžia operacijų aibę, galimų grupuojamiems duomenimis.

## Savybės
Bendrosios duomenų tipų savybės 1972 metais suformuotos Horo (*Hoare*):
# Duomenų tipas apibrėžia klasę reikšmių, kurias gali įgyti kintamasis ar reiškinys
# Kiekviena reikšmė priklauso vienam ir tik vienam duomenų tipui
# Konstantos, kintamojo ar reiškinio tipą galima nustatyti iš teksto arba iš operando pavidalo, nepriklausomai nuo reikšmių.
# Kiekvienos operacijos operandų ir rezultato tipai yra fiksuoti. Tais pačiais simboliais žymimos skirtingų tipų operacijos laikomos daugiareikšmėmis ir žymi skirtingas operacijas (pavyzdžiui, sudėtis „+“).
# Duomenų tipo reikšmių savybės ir su reikšmėmis atliekamų operacijų savybės apibrėžiamos aksiomomis
# Duomenų tipai turi atitikmenis matematikoje (Dekarto sandauga, aibė, seka, funkcija, rekursija)

Barbara Liskov 1975 metais suformulavo tokius reikalavimus, kuriuos turi tenkinti abstraktus duomenų tipas:
# Duomenų tipo apraše turi būti apibrėžtos visos tipo reikšmėms taikytinos operacijos
# ADT naudotojas neturi žinoti, kaip reikšmės vaizduojamos kompiuterio atmintyje
# ADT naudotojas gali operuoti tipo reikšmėmis tik to tipo operacijomis, o ne tiesiogiai reikšmių atvaizdais atmintyje.

## Istorija
Duomenų struktūrizavimas prasidėjo atsirandant aukšto lygio programavimo kalboms. Kintamųjų tipizavimas pirmą kartą įvestas Fortran kalboje (1953), šioje kalboje naudoti skaičių tipai bei masyvai. Algol-60 išplėtė masyvo panaudojimą neribodami indeksų ir matmenų. Cobol (1961) įvesti tipai simbolių eilutei, įrašui, bylai saugoti. PL/1 (1965) leido laisvą reikšmių struktūrinimą, rodykles. Simula-67 pirmoji eksperimentinė kalba, kurioje įvesta klasė. Algol-68 (1973) ir Pascal (1970) kalbose įvestas tipų vardinimas, Pascal taip pat įvestas tipų sisteminimas. Ada (1983) plačiau pradėti naudoti abstraktieji duomenų tipai.

## Skirstymas
Duomenys pagal struktūrinimo laipsnį skirstomi į dvi klases – **paprastuosius** ir **struktūrinius duomenų** tipus. Paprastųjų tipų reikšmės nedalomos, o struktūriniai sudaryti iš kelių paprastųjų ar struktūrinių reikšmių. Struktūriniai duomenų tipai, kurių realizacija paslėpta, o reikšmėmis manipuliuoti galima tik naudojant apibrėžtą operacijų aibę, vadinami abstrakčiaisiais duomenų tipais.

Kai kurie dažniau naudojami duomenų tipai ir struktūros:
* Paprastieji tipai
** Loginis tipas – paprasčiausias duomenų tipas, turintis dvi reikšmes (teisinga ar klaidinga). Galimos Būlio algebros apibrėžtos operacijos.
** Vardinis tipas – diskretus tipas, kai tipo apraše išvardinamos visos galimos reikšmės
** Simbolinis tipas – diskretus tipas, kurio galimos reikšmės – simboliai
** Atkarpos tipas – kai aprašomos kraštutinės reikšmės (apatinis ir viršutinis rėžiai) tam tikroje aibėje (sveikųjų skaičių, simbolių)
** Sveikųjų skaičių tipas – galimos reikšmės iš sveikųjų skaičių aibės.
** Realiųjų skaičių tipas – teoriškai galimos reikšmės iš realiųjų skaičių aibės, tačiau praktiškai realizuojama reikšmėmis iš mažesnės racionaliųjų skaičių aibės.
* Struktūriniai duomenų tipai
** Alternatyva – aprašomi keli tipai, tačiau vienu metu galioja tik vieno tipo reikšmė.
** Rinkinys (įrašas, struktūra) – tiesioginis kelių tipų grupavimas.
** Masyvas – daugelio to paties tipo reikšmių jungimas į vieną sudėtinę reikšmę. Komponentai vadinami elementais, o pasiemiami naudojant indeksus.
** Eilė – daugelio to paties tipo reikšmių jungimas į vieną reikšmę, kai komponentai saugomi ta tvarka, kuria buvo į eilę įdėti, o išimti iš eilės galima tik pirmą įdėtą komponentą.
** Sąrašas
** Medis
*** Krūva
*** Dvejetainis paieškos medis
*** Besibalansuojantys medžiai
**** Raudonai-Juodas medis
**** AVL medis
**** B medis
**** 2-3-4 medis
** Grafas
** Dėstymo lentelė
** Prioritėtų eilė