Duomenų struktūra

Bendrosios duomenų tipų savybės 1972 metais suformuotos Horo (Hoare):

1. Duomenų tipas apibrėžia klasę reikšmių, kurias gali įgyti kintamasis ar reiškinys
2. Kiekviena reikšmė priklauso vienam ir tik vienam duomenų tipui
3. Konstantos, kintamojo ar reiškinio tipą galima nustatyti iš teksto arba iš operando pavidalo, nepriklausomai nuo reikšmių.
4. 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 „+“).
5. Duomenų tipo reikšmių savybės ir su reikšmėmis atliekamų operacijų savybės apibrėžiamos aksiomomis
6. Duomenų tipai turi atitikmenis matematikoje (Dekarto sandauga, aibė, seka, funkcija, rekursija)

Barbara Liskov 1975 metais suformulavo tokius reikalavimus, kuriuos turi tenkinti abstraktus duomenų tipas:

1. Duomenų tipo apraše turi būti apibrėžtos visos tipo reikšmėms taikytinos operacijos
2. ADT naudotojas neturi žinoti, kaip reikšmės vaizduojamos kompiuterio atmintyje
3. ADT naudotojas gali operuoti tipo reikšmėmis tik to tipo operacijomis, o ne tiesiogiai reikšmių atvaizdais atmintyje.

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.

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ė