Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius Jūs galite padėti Vikipedijai pridėdami tinkamas išna
Duomenų struktūra
| Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais. |
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, , 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
-
- Raudonai-Juodas medis
- AVL medis
- B medis
- 2-3-4 medis
- Grafas
- Dėstymo lentelė
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Duomenų struktūra, Kas yra Duomenų struktūra? Ką reiškia Duomenų struktūra?
Siam straipsniui ar jo daliai truksta isnasu į patikimus saltinius Jus galite padeti Vikipedijai pridedami tinkamas isnasas su saltiniais Duomenu struktura duomenu tipas duomenys logiskai jungiantys keleta paprastuju duomenu tipu reiksmiu arba kelias paprastesnes duomenu strukturas Pirmosios duomenu strukturos naudotos tik kaip reiksmiu aibes bet veliau pradeti naudoti abstraktieji duomenu tipai ADT apibrezia operaciju aibe galimu grupuojamiems duomenimis SavybesBendrosios duomenu tipu savybes 1972 metais suformuotos Horo Hoare Duomenu tipas apibrezia klase reiksmiu kurias gali įgyti kintamasis ar reiskinys Kiekviena reiksme priklauso vienam ir tik vienam duomenu tipui Konstantos kintamojo ar reiskinio tipa galima nustatyti is teksto arba is operando pavidalo nepriklausomai nuo reiksmiu Kiekvienos operacijos operandu ir rezultato tipai yra fiksuoti Tais paciais simboliais zymimos skirtingu tipu operacijos laikomos daugiareiksmemis ir zymi skirtingas operacijas pavyzdziui sudetis Duomenu tipo reiksmiu savybes ir su reiksmemis atliekamu operaciju savybes apibreziamos aksiomomis Duomenu tipai turi atitikmenis matematikoje Dekarto sandauga aibe seka rekursija Barbara Liskov 1975 metais suformulavo tokius reikalavimus kuriuos turi tenkinti abstraktus duomenu tipas Duomenu tipo aprase turi buti apibreztos visos tipo reiksmems taikytinos operacijos ADT naudotojas neturi zinoti kaip reiksmes vaizduojamos kompiuterio atmintyje ADT naudotojas gali operuoti tipo reiksmemis tik to tipo operacijomis o ne tiesiogiai reiksmiu atvaizdais atmintyje IstorijaDuomenu strukturizavimas prasidejo atsirandant auksto lygio programavimo kalboms Kintamuju tipizavimas pirma karta įvestas Fortran kalboje 1953 sioje kalboje naudoti skaiciu tipai bei masyvai Algol 60 isplete masyvo panaudojima neribodami indeksu ir matmenu Cobol 1961 įvesti tipai simboliu eilutei įrasui bylai saugoti PL 1 1965 leido laisva reiksmiu strukturinima rodykles Simula 67 pirmoji eksperimentine kalba kurioje įvesta klase Algol 68 1973 ir Pascal 1970 kalbose įvestas tipu vardinimas Pascal taip pat įvestas tipu sisteminimas Ada 1983 placiau pradeti naudoti abstraktieji duomenu tipai SkirstymasDuomenys pagal strukturinimo laipsnį skirstomi į dvi klases paprastuosius ir strukturinius duomenu tipus Paprastuju tipu reiksmes nedalomos o strukturiniai sudaryti is keliu paprastuju ar strukturiniu reiksmiu Strukturiniai duomenu tipai kuriu realizacija paslepta o reiksmemis manipuliuoti galima tik naudojant apibrezta operaciju aibe vadinami abstrakciaisiais duomenu tipais Kai kurie dazniau naudojami duomenu tipai ir strukturos Paprastieji tipai Loginis tipas paprasciausias duomenu tipas turintis dvi reiksmes teisinga ar klaidinga Galimos Bulio algebros apibreztos operacijos Vardinis tipas diskretus tipas kai tipo aprase isvardinamos visos galimos reiksmes Simbolinis tipas diskretus tipas kurio galimos reiksmes simboliai Atkarpos tipas kai aprasomos krastutines reiksmes apatinis ir virsutinis reziai tam tikroje aibeje sveikuju skaiciu simboliu Sveikuju skaiciu tipas galimos reiksmes is sveikuju skaiciu aibes Realiuju skaiciu tipas teoriskai galimos reiksmes is realiuju skaiciu aibes taciau praktiskai realizuojama reiksmemis is mazesnes racionaliuju skaiciu aibes Strukturiniai duomenu tipai Alternatyva aprasomi keli tipai taciau vienu metu galioja tik vieno tipo reiksme Rinkinys įrasas struktura tiesioginis keliu tipu grupavimas Masyvas daugelio to paties tipo reiksmiu jungimas į viena sudetine reiksme Komponentai vadinami elementais o pasiemiami naudojant indeksus Eile daugelio to paties tipo reiksmiu jungimas į viena reiksme kai komponentai saugomi ta tvarka kuria buvo į eile įdeti o isimti is eiles galima tik pirma įdeta komponenta Sarasas Medis Kruva Dvejetainis paieskos medis Raudonai Juodas medis AVL medis B medis 2 3 4 medis Grafas Destymo lentele