logo

Įvadas į duomenų struktūras

Nuo pat kompiuterių išradimo žmonės vartoja terminą „ Duomenys “, kad būtų nurodyta kompiuterio informacija, perduodama arba saugoma. Tačiau yra duomenų, kurie egzistuoja ir užsakymų tipuose. Duomenys gali būti skaičiai arba tekstai, užrašyti ant popieriaus lapo bitų ir baitų pavidalu, saugomi elektroninių prietaisų atmintyje, arba faktai, saugomi žmogaus galvoje. Pasauliui pradėjus modernėti, šie duomenys tapo reikšmingu kiekvieno kasdienio gyvenimo aspektu, o įvairūs diegimai leido juos saugoti skirtingai.

Duomenys yra faktų ir skaičių rinkinys arba konkretaus formato reikšmių ar verčių rinkinys, nurodantis vieną elemento reikšmių rinkinį. Tada duomenų elementai klasifikuojami į substraipsnius, tai yra elementų grupė, kuri nėra žinoma kaip paprasta pirminė elemento forma.

Panagrinėkime pavyzdį, kai darbuotojo vardą galima suskirstyti į tris poskyrius: Pirmas, Vidurinis ir Paskutinis. Tačiau darbuotojui priskirtas ID paprastai bus laikomas vienu elementu.

Įvadas į duomenų struktūras

Figūra 1: Duomenų elementų vaizdavimas

Pirmiau minėtame pavyzdyje tokie elementai kaip ID, amžius, lytis, pirmas, vidurinis, paskutinis, gatvė, vietovė ir kt. yra elementarių duomenų elementai. Priešingai, Vardas ir Adresas yra grupės duomenų elementai.

Kas yra duomenų struktūra?

Duomenų struktūra yra kompiuterių mokslo šaka. Duomenų struktūros tyrimas leidžia suprasti duomenų organizavimą ir duomenų srauto valdymą, siekiant padidinti bet kurio proceso ar programos efektyvumą. Duomenų struktūra yra ypatingas būdas saugoti ir tvarkyti duomenis kompiuterio atmintyje, kad prireikus šiuos duomenis būtų galima lengvai gauti ir efektyviai panaudoti ateityje. Duomenys gali būti tvarkomi įvairiais būdais, pavyzdžiui, loginis arba matematinis konkrečios duomenų organizacijos modelis yra žinomas kaip duomenų struktūra.

Tam tikro duomenų modelio apimtis priklauso nuo dviejų veiksnių:

  1. Pirma, jis turi būti pakankamai įkeltas į struktūrą, kad atspindėtų neabejotiną duomenų koreliaciją su realaus pasaulio objektu.
  2. Antra, formavimas turi būti toks paprastas, kad prireikus būtų galima prisitaikyti ir efektyviai apdoroti duomenis.

Kai kurie duomenų struktūrų pavyzdžiai yra masyvai, susieti sąrašai, dėklas, eilė, medžiai ir kt. Duomenų struktūros plačiai naudojamos beveik visuose kompiuterių mokslo aspektuose, t. y. kompiliatorių projektavimo, operacinės sistemos, grafika, dirbtinis intelektas ir kt.

Duomenų struktūros yra pagrindinė daugelio kompiuterių mokslo algoritmų dalis, nes jos leidžia programuotojams efektyviai valdyti duomenis. Ji atlieka labai svarbų vaidmenį gerinant programos ar programinės įrangos veikimą, nes pagrindinis programinės įrangos tikslas yra kuo greičiau saugoti ir gauti vartotojo duomenis.

miegoti javascript

Pagrindinės terminijos, susijusios su duomenų struktūromis

Duomenų struktūros yra bet kokios programinės įrangos ar programos sudedamosios dalys. Tinkamos duomenų struktūros pasirinkimas programai yra labai sudėtinga užduotis programuotojui.

Toliau pateikiami keli pagrindiniai terminai, naudojami, kai yra susijusios su duomenų struktūromis:

    Duomenys:Duomenis galime apibrėžti kaip elementarią reikšmę arba reikšmių rinkinį. Pavyzdžiui, darbuotojo vardas, pavardė ir ID yra su darbuotoju susiję duomenys.Duomenų elementai:Vienas vertės vienetas yra žinomas kaip duomenų elementas.Grupės elementai:Duomenų elementai, turintys antraeilius duomenų elementus, yra žinomi kaip grupės elementai. Pavyzdžiui, darbuotojo vardas gali turėti vardą, vidurinįjį ir pavardę.Pradiniai elementai:Duomenų elementai, kurių negalima suskirstyti į antrinius elementus, yra žinomi kaip pagrindiniai elementai. Pavyzdžiui, darbuotojo ID.Subjektas ir atributas:Tam tikrų objektų klasę vaizduoja Esybė. Jį sudaro įvairūs atributai. Kiekvienas Atributas simbolizuoja konkrečią to Esybės savybę. Pavyzdžiui,
Atributai ID vardas Lytis Darbo pavadinimas
Vertybės 1234 m Stacey M. Hill Moteris Programinės įrangos kūrėjas

Subjektai su panašiais atributais sudaro an Objektų rinkinys . Kiekvienas objekto rinkinio atributas turi reikšmių diapazoną, visų galimų reikšmių rinkinį, kurį galima priskirti konkrečiam atributui.

Terminas „informacija“ kartais vartojamas duomenims, turintiems tam tikrų reikšmingų arba apdorotų duomenų atributų.

    Laukas:Vienas elementarus informacijos vienetas, simbolizuojantis subjekto požymį, yra žinomas kaip laukas.Įrašas:Įvairių duomenų elementų rinkinys yra žinomas kaip įrašas. Pavyzdžiui, jei kalbame apie darbuotojo objektą, jo pavadinimą, ID, adresą ir pareigų pavadinimą galima sugrupuoti, kad būtų sudarytas darbuotojo įrašas.Failas:Vieno tipo skirtingų įrašų rinkinys yra žinomas kaip failas. Pavyzdžiui, jei yra 100 darbuotojų, susijusiame faile bus 25 įrašai su duomenimis apie kiekvieną darbuotoją.

Duomenų struktūrų poreikio supratimas

Kadangi taikomosios programos tampa vis sudėtingesnės, o duomenų kiekis kasdien didėja, todėl gali kilti problemų dėl duomenų paieškos, apdorojimo greičio, kelių užklausų tvarkymo ir daug daugiau. Duomenų struktūros palaiko įvairius metodus, leidžiančius efektyviai tvarkyti, valdyti ir saugoti duomenis. Duomenų struktūrų pagalba galime lengvai pereiti duomenų elementus. Duomenų struktūros užtikrina efektyvumą, pakartotinį naudojimą ir abstrakciją.

Kodėl turėtume mokytis duomenų struktūrų?

  1. Duomenų struktūros ir algoritmai yra du pagrindiniai kompiuterių mokslo aspektai.
  2. Duomenų struktūros leidžia tvarkyti ir saugoti duomenis, o algoritmai leidžia prasmingai apdoroti tuos duomenis.
  3. Duomenų struktūrų ir algoritmų mokymasis padės mums tapti geresniais programuotojais.
  4. Galėsime parašyti efektyvesnį ir patikimesnį kodą.
  5. Taip pat galėsime greičiau ir efektyviau išspręsti problemas.

Duomenų struktūrų tikslų supratimas

Duomenų struktūros atitinka du vienas kitą papildančius tikslus:

    Teisingumas:Duomenų struktūros sukurtos taip, kad tinkamai veiktų visų rūšių įvestims, atsižvelgiant į dominančią sritį. Kitaip tariant, teisingumas yra pagrindinis duomenų struktūros tikslas, kuris visada priklauso nuo problemų, kurias Duomenų struktūra turi išspręsti.Efektyvumas:Duomenų struktūros taip pat turi būti veiksmingos. Jis turėtų greitai apdoroti duomenis, nenaudodamas daugelio kompiuterio išteklių, pvz., atminties vietos. Realaus laiko būsenoje duomenų struktūros efektyvumas yra pagrindinis veiksnys, lemiantis proceso sėkmę ir nesėkmę.

Kai kurių pagrindinių duomenų struktūrų ypatybių supratimas

Kai kurios svarbios duomenų struktūrų savybės:

    Tvirtumas:Paprastai visi kompiuterių programuotojai siekia sukurti programinę įrangą, kuri duoda teisingą kiekvienos galimos įvesties išvestį ir efektyvų vykdymą visose aparatinės įrangos platformose. Šio tipo patikima programinė įranga turi valdyti ir galiojančias, ir netinkamas įvestis.Pritaikymas:Kuriant programinės įrangos programas, tokias kaip žiniatinklio naršyklės, tekstų apdorojimo įrenginiai ir interneto paieškos variklis, yra didžiulės programinės įrangos sistemos, kurioms reikalingas teisingas ir efektyvus darbas ar vykdymas daugelį metų. Be to, programinė įranga vystosi dėl naujų technologijų ar nuolat kintančių rinkos sąlygų.Pakartotinis naudojimas:Tokios funkcijos kaip Pakartotinis naudojimas ir Pritaikymas eina kartu. Yra žinoma, kad programuotojui reikia daug išteklių bet kokiai programinei įrangai sukurti, todėl tai yra brangi įmonė. Tačiau jei programinė įranga yra sukurta daugkartinio naudojimo ir pritaikomu būdu, ji gali būti pritaikyta daugumoje būsimų programų. Taigi, vykdant kokybiškas duomenų struktūras, galima sukurti daugkartinio naudojimo programinę įrangą, kuri atrodo ekonomiška ir taupanti laiką.

Duomenų struktūrų klasifikacija

Duomenų struktūra pateikia struktūruotą kintamųjų, įvairiais būdais susijusių vienas su kitu, rinkinį. Tai sudaro programavimo įrankio pagrindą, kuris reiškia ryšį tarp duomenų elementų ir leidžia programuotojams efektyviai apdoroti duomenis.

Duomenų struktūras galime suskirstyti į dvi kategorijas:

  1. Primityvi duomenų struktūra
  2. Neprimityvi duomenų struktūra

Toliau pateiktame paveikslėlyje parodytos skirtingos duomenų struktūrų klasifikacijos.

Įvadas į duomenų struktūras

2 pav. Duomenų struktūrų klasifikacijos

Primityvios duomenų struktūros

    Primityvios duomenų struktūrosyra duomenų struktūros, susidedančios iš skaičių ir gaunamų simbolių įmontuotas į programas.
  1. Šiomis duomenų struktūromis galima manipuliuoti arba tiesiogiai valdyti mašinos lygio instrukcijas.
  2. Pagrindiniai duomenų tipai, pvz Sveikasis skaičius, plūduriavimas, simbolis , ir Būlio patenka į primityviąsias duomenų struktūras.
  3. Šie duomenų tipai taip pat vadinami Paprasti duomenų tipai , nes juose yra simbolių, kurių negalima toliau skaidyti

Neprimityvios duomenų struktūros

    Neprimityvios duomenų struktūrosyra tos duomenų struktūros, gautos iš primityvių duomenų struktūrų.
  1. Šių duomenų struktūrų negalima manipuliuoti arba tiesiogiai valdyti naudojant mašinos lygio instrukcijas.
  2. Šiose duomenų struktūrose pagrindinis dėmesys skiriamas duomenų elementų rinkinio formavimui, kuris yra arba vienalytis (to paties tipo duomenų) arba nevienalytis (skirtingi duomenų tipai).
  3. Remdamiesi duomenų struktūra ir išdėstymu, šias duomenų struktūras galime suskirstyti į dvi subkategorijas –
    1. Linijinės duomenų struktūros
    2. Netiesinės duomenų struktūros

Linijinės duomenų struktūros

Duomenų struktūra, kuri išsaugo linijinį ryšį tarp duomenų elementų, yra žinoma kaip linijinė duomenų struktūra. Duomenų išdėstymas atliekamas linijiniu būdu, kai kiekvienas elementas susideda iš įpėdinių ir pirmtakų, išskyrus pirmąjį ir paskutinį duomenų elementą. Tačiau tai nebūtinai teisinga atminties atveju, nes išdėstymas gali būti nenuoseklus.

konstruktorius java

Atsižvelgiant į atminties paskirstymą, linijinės duomenų struktūros skirstomos į du tipus:

    Statinės duomenų struktūros:Fiksuoto dydžio duomenų struktūros yra žinomos kaip statinės duomenų struktūros. Šių duomenų struktūrų atmintis yra paskirstoma kompiliatoriaus metu, o jų dydžio vartotojas negali pakeisti po kompiliavimo; tačiau juose saugomi duomenys gali būti keičiami.
    The Masyvas yra geriausias statinės duomenų struktūros pavyzdys, nes jos turi fiksuotą dydį, o jos duomenis galima keisti vėliau.Dinaminės duomenų struktūros:Dinaminio dydžio duomenų struktūros yra žinomos kaip dinaminės duomenų struktūros. Šių duomenų struktūrų atmintis yra paskirstoma vykdymo metu, o jų dydis kinta kodo vykdymo metu. Be to, vartotojas gali keisti dydį ir duomenų elementus, saugomus šiose duomenų struktūrose kodo vykdymo metu.
    Susieti sąrašai, krūvos , ir Uodegos yra įprasti dinaminių duomenų struktūrų pavyzdžiai

Tiesinių duomenų struktūrų tipai

Toliau pateikiamas linijinių duomenų struktūrų, kurias paprastai naudojame, sąrašas:

1. Masyvai

An Masyvas yra duomenų struktūra, naudojama keliems to paties tipo duomenų elementams surinkti į vieną kintamąjį. Užuot saugoję kelias tų pačių duomenų tipų reikšmes atskiruose kintamųjų pavadinimuose, galėtume jas visas kartu saugoti viename kintamajame. Šis teiginys nereiškia, kad turėsime sujungti visas to paties tipo duomenų reikšmes bet kurioje programoje į vieną to duomenų tipo masyvą. Tačiau dažnai kai kurie konkretūs tų pačių duomenų tipų kintamieji yra susiję vienas su kitu masyvei tinkamu būdu.

Masyvas yra elementų sąrašas, kuriame kiekvienas elementas turi unikalią vietą sąraše. Masyvo duomenų elementai turi tą patį kintamojo pavadinimą; tačiau kiekvienas turi skirtingą indekso numerį, vadinamą apatiniu indeksu. Mes galime pasiekti bet kurį duomenų elementą iš sąrašo, naudodami jo vietą sąraše. Taigi, pagrindinė masyvų savybė, kurią reikia suprasti, yra ta, kad duomenys yra saugomi gretimose atminties vietose, todėl vartotojai gali pereiti per masyvo duomenų elementus naudodami atitinkamus indeksus.

Įvadas į duomenų struktūras

3 pav. Masyvas

Masyvai gali būti suskirstyti į skirtingus tipus:

    Vienmatis masyvas:Masyvas, kuriame yra tik viena duomenų elementų eilutė, yra žinomas kaip vienmatis masyvas. Jis saugomas didėjančioje saugojimo vietoje.Dvimatis masyvas:Masyvas, susidedantis iš kelių duomenų elementų eilučių ir stulpelių, vadinamas dvimačiu masyvu. Jis taip pat žinomas kaip Matrica.Daugiamatis masyvas:Daugiamatį masyvą galime apibrėžti kaip masyvų masyvą. Daugiamačiai masyvai nėra apriboti dviem indeksais ar dviem matmenimis, nes juose gali būti tiek indeksų, kiek reikia.

Kai kurios masyvo programos:

  1. Galime saugoti duomenų elementų, priklausančių tam pačiam duomenų tipui, sąrašą.
  2. Masyvas veikia kaip pagalbinė kitų duomenų struktūrų saugykla.
  3. Masyvas taip pat padeda saugoti fiksuoto skaičiaus dvejetainio medžio duomenų elementus.
  4. Masyvas taip pat veikia kaip matricų saugykla.

2. Susieti sąrašai

A Susietas sąrašas yra dar vienas linijinės duomenų struktūros, naudojamos dinamiškai saugoti duomenų elementų rinkinį, pavyzdys. Duomenų elementus šioje duomenų struktūroje vaizduoja mazgai, sujungti saitais arba rodyklėmis. Kiekviename mazge yra du laukai, informacijos lauką sudaro faktiniai duomenys, o rodyklės lauką sudaro tolesnių sąrašo mazgų adresai. Paskutinio susieto sąrašo mazgo rodyklė susideda iš nulinės rodyklės, nes ji nerodo nieko. Skirtingai nei masyvai, vartotojas gali dinamiškai koreguoti susieto sąrašo dydį pagal reikalavimus.

Įvadas į duomenų struktūras

4 pav. Susietas sąrašas

Susietus sąrašus galima suskirstyti į skirtingus tipus:

    Atskirai susietas sąrašas:Atskirai susietas sąrašas yra labiausiai paplitęs susietųjų sąrašų tipas. Kiekvienas mazgas turi duomenis ir žymeklio lauką, kuriame yra kito mazgo adresas.Dvigubai susietas sąrašas:Dvigubai susietą sąrašą sudaro informacijos laukas ir du rodyklės laukai. Informaciniame lauke yra duomenys. Pirmajame rodyklės lauke yra ankstesnio mazgo adresas, o kitame rodyklės lauke yra nuoroda į kitą mazgą. Taigi galime eiti abiem kryptimis (atgal ir pirmyn).Aplinkinis susietų sąrašas:Circular Linked List yra panašus į Singly Linked List. Vienintelis esminis skirtumas yra tas, kad paskutiniame mazge yra pirmojo mazgo adresas, kuris sudaro apskritą kilpą žiediniame susietų sąraše.

Kai kurios susietų sąrašų programos:

patobulinta ciklo java
  1. Susieti sąrašai padeda mums įdiegti iš anksto nustatyto dydžio krūvas, eiles, dvejetainius medžius ir grafikus.
  2. Taip pat galime įdiegti operacinės sistemos funkciją dinaminiam atminties valdymui.
  3. Susieti sąrašai taip pat leidžia matematinėms operacijoms įgyvendinti daugianario.
  4. Galime naudoti žiedinį susietą sąrašą operacinėms sistemoms ar taikomųjų programų funkcijoms, kurios apvaliai vykdo užduotis.
  5. Apvalus susietas sąrašas taip pat naudingas skaidrių demonstravimui, kai vartotojas turi grįžti į pirmąją skaidrę po paskutinės skaidrės pateikimo.
  6. Dvigubai susietas sąrašas naudojamas naršyklės mygtukams pirmyn ir atgal, kad atidarytuose svetainės puslapiuose būtų galima judėti pirmyn ir atgal.

3. Krūvos

A Stack yra linijinė duomenų struktūra, kuri atitinka LIFO (Last In, First Out) principas, leidžiantis atlikti tokias operacijas kaip įterpimas ir ištrynimas iš vieno kamino galo, t. y. viršuje. Stackus galima įdiegti gretimos atminties, masyvo ir negretimos atminties, susieto sąrašo, pagalba. Realūs Stacks pavyzdžiai yra krūvos knygų, kortų kaladė, krūvos pinigų ir daug daugiau.

Įvadas į duomenų struktūras

5 pav. Realus Stack pavyzdys

Aukščiau pateiktame paveikslėlyje pavaizduotas realus krūvos pavyzdys, kai operacijos atliekamos tik iš vieno galo, pvz., naujų knygų įdėjimas ir pašalinimas iš krūvos viršaus. Tai reiškia, kad įterpimas ir ištrynimas į krūvą gali būti atliekamas tik iš dėklo viršaus. Bet kuriuo metu galime pasiekti tik „Stack“ viršūnes.

Pagrindinės operacijos „Stack“ yra šios:

    Stumti:Naujo elemento įterpimo į krūvą operacija vadinama stūmimo operacija.Pop:Elementų pašalinimo arba ištrynimo iš kamino operacija vadinama pop operacija.
Įvadas į duomenų struktūras

6 pav. Stack

Kai kurios kaminų programos:

  1. Stackas naudojamas kaip laikina saugojimo struktūra rekursinėms operacijoms.
  2. Stack taip pat naudojamas kaip pagalbinė saugyklos struktūra funkcijų iškvietimams, įdėtoms operacijoms ir atidėtoms / atidėtoms funkcijoms.
  3. Funkcinius skambučius galime valdyti naudodami Stacks.
  4. Stackai taip pat naudojami vertinant aritmetines išraiškas skirtingomis programavimo kalbomis.
  5. Stackai taip pat naudingi konvertuojant infix išraiškas į postfix išraiškas.
  6. Stackai leidžia patikrinti išraiškos sintaksę programavimo aplinkoje.
  7. Mes galime suderinti skliaustus naudodami Stacks.
  8. Stackus galima naudoti norint pakeisti eilutę.
  9. Stackai yra naudingi sprendžiant problemas, pagrįstas atsitraukimu.
  10. Galime naudoti „Stacks“ atliekant giluminę paiešką grafike ir medžiu.
  11. Stackai taip pat naudojami operacinės sistemos funkcijose.
  12. Stackai taip pat naudojami atliekant redagavimo funkcijas UNDO ir REDO.

4. Uodegos

A Eilė yra linijinė duomenų struktūra, panaši į krūvą su tam tikrais elementų įterpimo ir ištrynimo apribojimais. Elementas įterpiamas į eilę viename gale, o pašalinimas – kitame arba priešingame gale. Taigi galime daryti išvadą, kad eilės duomenų struktūra vadovaujasi FIFO (First In, First Out) principu, kad būtų galima manipuliuoti duomenų elementais. Eilių diegimas gali būti atliekamas naudojant masyvus, susietus sąrašus arba krūvas. Kai kurie realūs eilių pavyzdžiai yra eilė prie bilietų kasos, eskalatorius, automobilių plovykla ir daugelis kitų.

Įvadas į duomenų struktūras

7 pav. Realus eilės pavyzdys

Aukščiau pateiktame paveikslėlyje yra tikroji filmų bilietų skaitiklio iliustracija, kuri gali padėti suprasti eilę, kurioje klientas, kuris ateina pirmas, visada aptarnaujamas pirmas. Paskutinis atvykęs klientas neabejotinai bus aptarnaujamas paskutinis. Abu eilės galai yra atviri ir gali atlikti skirtingas operacijas. Kitas pavyzdys yra maisto aikštelės linija, kai klientas įkišamas iš galinės dalies, o klientas pašalinamas iš priekio, suteikęs paslaugą, kurios paprašė.

Toliau pateikiamos pagrindinės eilės operacijos:

    Eilė:Kai kurių duomenų elementų įterpimas arba įtraukimas į eilę vadinamas eile. Elementų įterpimas visada atliekamas galinės rodyklės pagalba.Nutraukti į eilę:Duomenų elementų ištrynimas arba pašalinimas iš eilės vadinamas eilėmis. Elemento ištrynimas visada atliekamas naudojant priekinę žymeklį.
Įvadas į duomenų struktūras

8 pav. Eilė

Kai kurios eilių programos:

  1. Eilės paprastai naudojamos pločio paieškos operacijoje Grafikuose.
  2. Eilės taip pat naudojamos operacinių sistemų užduočių planavimo priemonėse, pavyzdžiui, klaviatūros buferio eilė, skirta vartotojų paspaustiems klavišams saugoti, ir spausdinimo buferio eilė spausdintuvo išspausdintiems dokumentams saugoti.
  3. Eilės yra atsakingos už procesoriaus planavimą, užduočių planavimą ir disko planavimą.
  4. Prioritetinės eilės naudojamos failų atsisiuntimo operacijoms naršyklėje.
  5. Eilės taip pat naudojamos duomenims perduoti tarp periferinių įrenginių ir procesoriaus.
  6. Eilės taip pat yra atsakingos už pertraukimų, kuriuos generuoja CPU vartotojo programos, tvarkymą.

Netiesinės duomenų struktūros

Netiesinės duomenų struktūros yra duomenų struktūros, kuriose duomenų elementai nėra išdėstyti nuoseklia tvarka. Čia duomenų įterpimas ir pašalinimas nėra įmanomas linijiniu būdu. Tarp atskirų duomenų elementų egzistuoja hierarchinis ryšys.

Netiesinių duomenų struktūrų tipai

Toliau pateikiamas netiesinių duomenų struktūrų, kurias paprastai naudojame, sąrašas:

1. Medžiai

Medis yra netiesinė duomenų struktūra ir hierarchija, kurią sudaro mazgų rinkinys, todėl kiekvienas medžio mazgas saugo vertę ir nuorodų į kitus mazgus ('vaikus') sąrašą.

eilutę palyginkite c#

Medžio duomenų struktūra yra specializuotas būdas tvarkyti ir rinkti duomenis kompiuteryje, kad jie būtų naudojami efektyviau. Jame yra centrinis mazgas, struktūriniai mazgai ir submazgai, sujungti per kraštus. Taip pat galime pasakyti, kad medžio duomenų struktūra susideda iš sujungtų šaknų, šakų ir lapų.

Įvadas į duomenų struktūras

9 pav. Medis

Medžius galima suskirstyti į keletą tipų:

    Dvejetainis medis:Medžio duomenų struktūra, kurioje kiekvienas pirminis mazgas gali turėti ne daugiau kaip du vaikus, vadinama dvejetainiu medžiu.Dvejetainis paieškos medis:Dvejetainis paieškos medis yra medžio duomenų struktūra, kurioje galime lengvai tvarkyti surūšiuotą skaičių sąrašą.AVL medis:AVL medis yra savaime balansuojantis dvejetainis paieškos medis, kuriame kiekvienas mazgas palaiko papildomą informaciją, vadinamą balanso faktoriumi, kurio reikšmė yra -1, 0 arba +1.B medis:B-medis yra specialus savaime balansuojantis dvejetainis paieškos medis, kuriame kiekvienas mazgas susideda iš kelių raktų ir gali turėti daugiau nei du vaikus.

Kai kurie medžių pritaikymai:

  1. Medžiai įdiegia hierarchines struktūras kompiuterinėse sistemose, tokiose kaip katalogai ir failų sistemos.
  2. Medžiai taip pat naudojami svetainės naršymo struktūrai įgyvendinti.
  3. Naudodami medžius galime sugeneruoti tokį kodą kaip Huffmano kodas.
  4. Medžiai taip pat padeda priimti sprendimus žaidimų programose.
  5. Medžiai yra atsakingi už prioritetinių OS planavimo funkcijų prioritetinių eilių įgyvendinimą.
  6. Medžiai taip pat yra atsakingi už išraiškų ir teiginių analizavimą skirtingų programavimo kalbų kompiliatoriuose.
  7. Mes galime naudoti medžius duomenų raktams saugoti duomenų bazių valdymo sistemos (DBVS) indeksavimui.
  8. „Spanning Trees“ leidžia mums nukreipti sprendimus kompiuterių ir ryšių tinkluose.
  9. Medžiai taip pat naudojami kelio paieškos algoritme, įdiegtame dirbtinio intelekto (AI), robotikos ir vaizdo žaidimų programose.

2. Grafikai

Grafas yra dar vienas netiesinės duomenų struktūros pavyzdys, susidedantis iš riboto skaičiaus mazgų arba viršūnių ir juos jungiančių kraštų. Grafikai naudojami realaus pasaulio problemoms spręsti, kai jie žymi probleminę sritį kaip tinklą, pvz., socialinius tinklus, grandinių tinklus ir telefono tinklus. Pavyzdžiui, grafiko mazgai arba viršūnės gali atstovauti vienam telefono tinklo vartotojui, o kraštai – ryšį tarp jų telefonu.

python konstruktorius

Grafo duomenų struktūra G laikoma matematine struktūra, kurią sudaro viršūnių rinkinys V ir briaunų rinkinys E, kaip parodyta toliau:

G = (V,E)

Įvadas į duomenų struktūras

10 pav. Grafikas

Aukščiau pateikta figūra vaizduoja grafiką, turintį septynias viršūnes A, B, C, D, E, F, G ir dešimt briaunų [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] ir [E, G].

Priklausomai nuo viršūnių ir briaunų padėties, grafikus galima suskirstyti į skirtingus tipus:

    Nulinis grafikas:Grafikas su tuščiu briaunų rinkiniu vadinamas nuliniu grafiku.Trivialus grafikas:Grafas, turintis tik vieną viršūnę, vadinamas trivialiuoju grafiku.Paprastas grafikas:Grafikas, neturintis nei savarankiškų kilpų, nei kelių briaunų, yra žinomas kaip paprastas grafikas.Keli grafikai:Grafas laikomas daugialypiu, jei jis susideda iš kelių briaunų, bet nėra savarankiškų kilpų.Pseudo grafikas:Grafas su savaiminėmis kilpomis ir keliomis briaunomis vadinamas pseudografu.Nenukreiptas grafikas:Grafikas, sudarytas iš nenukreiptų briaunų, yra žinomas kaip Nenukreiptas grafikas.Režisuotas grafikas:Grafikas, sudarytas iš nukreiptų briaunų tarp viršūnių, yra žinomas kaip nukreiptas grafikas.Susietas grafikas:Grafas, kuriame yra bent vienas kelias tarp kiekvienos viršūnių poros, vadinamas sujungtu grafiku.Atjungtas grafikas:Grafas, kuriame nėra kelio tarp bent vienos viršūnių poros, vadinamas atjungtu grafiku.Įprasta diagrama:Grafas, kuriame visos viršūnės turi tą patį laipsnį, vadinamas reguliariu grafiku.Visas grafikas:Grafas, kuriame visos viršūnės turi briauną tarp kiekvienos viršūnių poros, yra žinomas kaip užbaigtas grafikas.Ciklo grafikas:Grafas laikomas ciklu, jei jis turi bent tris viršūnes ir briaunas, kurios sudaro ciklą.Ciklinis grafikas:Grafikas laikomas cikliniu tada ir tik tada, kai egzistuoja bent vienas ciklas.Aciklinis grafikas:Grafikas, turintis nulį ciklų, vadinamas acikliniu grafiku.Baigtinis grafikas:Grafas su baigtiniu viršūnių ir briaunų skaičiumi yra žinomas kaip baigtinis grafikas.Begalinis grafikas:Grafas su begaliniu viršūnių ir briaunų skaičiumi yra žinomas kaip begalinis grafikas.Dvišalis grafikas:Grafas, kuriame viršūnės gali būti suskirstytos į nepriklausomas aibes A ir B, o visos aibės A viršūnės turi būti sujungtos tik su viršūnėmis, esančiomis aibėje B su kai kuriomis briaunomis, vadinamas dvišaliu grafiku.Plokštuminis grafikas:Grafas vadinamas plokštuma, jei galime nubraižyti jį vienoje plokštumoje su dviem kraštinėmis, susikertančiomis viena kitą.Eulerio grafikas:Grafas vadinamas Euleris tada ir tik tada, kai visos viršūnės yra lyginės.Hamiltono grafikas:Susietas grafikas, sudarytas iš Hamiltono grandinės, yra žinomas kaip Hamiltono grafikas.

Kai kurios grafikų programos:

  1. Grafikai padeda mums pavaizduoti maršrutus ir tinklus transporto, kelionių ir ryšių programose.
  2. Grafikai naudojami maršrutams rodyti GPS.
  3. Grafikai taip pat padeda mums pavaizduoti ryšius socialiniuose tinkluose ir kitose tinklo programose.
  4. Grafikai naudojami kartografavimo programose.
  5. Grafikai yra atsakingi už vartotojo pageidavimų pateikimą el. prekybos programose.
  6. Grafikai taip pat naudojami komunaliniuose tinkluose, siekiant nustatyti vietos ar savivaldybių įmonių problemas.
  7. Grafikai taip pat padeda valdyti išteklių panaudojimą ir prieinamumą organizacijoje.
  8. Grafikai taip pat naudojami kuriant svetainių dokumentų nuorodų žemėlapius, kad būtų rodomas puslapių ryšys per hipersaitus.
  9. Grafikai taip pat naudojami robotų judesiuose ir neuroniniuose tinkluose.

Pagrindinės duomenų struktūrų operacijos

Kitame skyriuje aptarsime įvairių tipų operacijas, kurias galime atlikti, kad manipuliuotume kiekvienos duomenų struktūros duomenimis:

    Perėjimas:Duomenų struktūros perėjimas reiškia, kad kiekvieną duomenų elementą reikia pasiekti tiksliai vieną kartą, kad jį būtų galima administruoti. Pavyzdžiui, spausdinant visų skyriaus darbuotojų vardus, reikia pereiti.Paieška:Paieška yra dar viena duomenų struktūros operacija, kuri reiškia vieno ar kelių duomenų elementų, atitinkančių tam tikrus apribojimus, vietą. Toks duomenų elementas gali būti arba nebūti duotame duomenų elementų rinkinyje. Pavyzdžiui, paieškos operacija galime rasti visų darbuotojų, turinčių daugiau nei 5 metų patirtį, pavardes.Įterpimas:Įterpimas reiškia naujų duomenų elementų įterpimą arba įtraukimą į rinkinį. Pavyzdžiui, galime naudoti įterpimo operaciją norėdami įtraukti informaciją apie naują darbuotoją, kurį įmonė neseniai pasamdė.Ištrynimas:Ištrynimas – tai konkretaus duomenų elemento pašalinimas arba pašalinimas iš pateikto duomenų elementų sąrašo. Pavyzdžiui, ištrynimo operacija galime ištrinti iš darbo išėjusio darbuotojo vardą.Rūšiavimas:Rūšiavimas reiškia duomenų elementų išdėstymą didėjančia arba mažėjančia tvarka, atsižvelgiant į programos tipą. Pavyzdžiui, galime naudoti rūšiavimo operaciją, norėdami išdėstyti skyriaus darbuotojų vardus abėcėlės tvarka arba įvertinti tris geriausius mėnesio rezultatus, sudėliodami darbuotojų rezultatus mažėjančia tvarka ir ištraukdami geriausių trejeto detales.Sujungti:Sujungti reiškia sujungti dviejų surūšiuotų sąrašų duomenų elementus, kad būtų sudarytas vienas surūšiuotų duomenų elementų sąrašas.Sukurti:Sukurti yra operacija, naudojama rezervuoti atmintį programos duomenų elementams. Šią operaciją galime atlikti naudodami deklaracijos teiginį. Duomenų struktūros kūrimas gali vykti šiais atvejais:
    1. Kompiliavimo laikas
    2. Veikimo laikas
      Pavyzdžiui, malloc () Funkcija naudojama C kalboje duomenų struktūrai sukurti.
    Pasirinkimas:Pasirinkimas reiškia tam tikrų duomenų atrinkimą iš turimų duomenų. Mes galime pasirinkti bet kokius konkrečius duomenis, nurodydami sąlygas ciklo viduje.Atnaujinimas:Atnaujinimo operacija leidžia atnaujinti arba modifikuoti duomenis duomenų struktūroje. Taip pat galime atnaujinti bet kokius konkrečius duomenis nurodydami kai kurias sąlygas ciklo viduje, pvz., pasirinkimo operaciją.Padalijimas:Padalijimo operacija leidžia padalyti duomenis į įvairias dalis, sumažinant bendrą proceso užbaigimo laiką.

Suprasti abstrakčių duomenų tipą

Pagal Nacionalinis standartų ir technologijų institutas (NIST) , duomenų struktūra yra informacijos išdėstymas, paprastai atmintyje, siekiant geresnio algoritmo efektyvumo. Duomenų struktūros apima susietus sąrašus, krūvas, eiles, medžius ir žodynus. Jie taip pat gali būti teorinis subjektas, pavyzdžiui, asmens vardas ir pavardė ir adresas.

Iš pirmiau minėto apibrėžimo galime daryti išvadą, kad operacijos duomenų struktūroje apima:

  1. Didelis abstrakcijų lygis, pvz., elemento įtraukimas arba ištrynimas iš sąrašo.
  2. Elemento paieška ir rūšiavimas sąraše.
  3. Prieiga prie aukščiausio prioriteto sąrašo elemento.

Kai duomenų struktūra atlieka tokias operacijas, ji vadinama an Abstraktių duomenų tipas (ADT) .

Galime jį apibrėžti kaip duomenų elementų rinkinį kartu su operacijomis su duomenimis. Sąvoka „abstraktus“ reiškia tai, kad duomenys ir jais apibrėžtos pagrindinės operacijos yra tiriamos nepriklausomai nuo jų įgyvendinimo. Tai apima tai, ką galime padaryti su duomenimis, o ne tai, kaip galime tai padaryti.

ADI diegime yra saugojimo struktūra, skirta duomenų elementams ir pagrindinės operacijos algoritmams saugoti. Visos duomenų struktūros, pvz., masyvas, susietas sąrašas, eilė, dėklas ir kt., yra ADT pavyzdžiai.

Supratimas apie ADT naudojimo pranašumus

Realiame pasaulyje programos vystosi dėl naujų apribojimų ar reikalavimų, todėl norint modifikuoti programą paprastai reikia pakeisti vieną ar kelias duomenų struktūras. Pavyzdžiui, tarkime, kad norime įterpti naują lauką į darbuotojo įrašą, kad galėtume sekti daugiau informacijos apie kiekvieną darbuotoją. Tokiu atveju galime pagerinti programos efektyvumą pakeisdami masyvą susietąja struktūra. Esant tokiai situacijai, nedera perrašyti kiekvienos procedūros, kurioje naudojama modifikuota struktūra. Taigi geresnė alternatyva yra atskirti duomenų struktūrą nuo jos įgyvendinimo informacijos. Tai yra abstrakčių duomenų tipų (ADT) naudojimo principas.

Kai kurios duomenų struktūrų programos

Toliau pateikiamos kai kurios duomenų struktūrų programos:

  1. Duomenų struktūros padeda organizuoti duomenis kompiuterio atmintyje.
  2. Duomenų struktūros taip pat padeda pateikti informaciją duomenų bazėse.
  3. Duomenų struktūros leidžia įgyvendinti duomenų paieškos algoritmus (pavyzdžiui, paieškos variklį).
  4. Galime naudoti duomenų struktūras, kad įdiegtume duomenų apdorojimo algoritmus (pavyzdžiui, tekstų rengyklės).
  5. Taip pat galime įdiegti algoritmus duomenims analizuoti naudodami duomenų struktūras (pavyzdžiui, duomenų kasyklas).
  6. Duomenų struktūros palaiko duomenų generavimo algoritmus (pavyzdžiui, atsitiktinių skaičių generatorių).
  7. Duomenų struktūros taip pat palaiko algoritmus duomenims suspausti ir išskleisti (pavyzdžiui, ZIP programa).
  8. Taip pat galime naudoti duomenų struktūras, kad įdiegtume duomenų šifravimo ir iššifravimo algoritmus (pavyzdžiui, apsaugos sistemą).
  9. Duomenų struktūrų pagalba galime sukurti programinę įrangą, galinčią valdyti failus ir katalogus (Pavyzdžiui, failų tvarkyklę).
  10. Taip pat galime sukurti programinę įrangą, kuri gali atvaizduoti grafiką naudojant duomenų struktūras. (Pavyzdžiui, žiniatinklio naršyklė arba 3D atvaizdavimo programinė įranga).

Be tų, kaip minėta anksčiau, yra daug kitų duomenų struktūrų programų, kurios gali padėti mums sukurti bet kokią norimą programinę įrangą.