logo

Ievads datu struktūrās

Kopš datoru izgudrošanas cilvēki ir lietojuši terminu ' Dati “, lai atsauktos uz datora informāciju, kas tiek pārraidīta vai saglabāta. Tomēr ir dati, kas pastāv arī pasūtījumu veidos. Dati var būt skaitļi vai teksti, kas uzrakstīti uz papīra lapas bitu un baitu veidā, kas tiek glabāti elektronisko ierīču atmiņā, vai fakti, kas glabājas cilvēka prātā. Kad pasaule sāka modernizēties, šie dati kļuva par nozīmīgu ikviena ikdienas dzīves aspektu, un dažādas ieviešanas ļāva tos uzglabāt atšķirīgi.

Dati ir faktu un skaitļu kopums vai vērtību vai noteikta formāta vērtību kopa, kas attiecas uz vienu vienumu vērtību kopu. Pēc tam datu vienumi tiek klasificēti apakšposteņos, kas ir vienumu grupa, kas nav zināma kā vienkārša elementa primārā forma.

Apskatīsim piemēru, kurā darbinieka vārdu var iedalīt trīs apakšpozīcijās: pirmais, vidējais un pēdējais. Tomēr darbiniekam piešķirtais ID parasti tiks uzskatīts par vienu vienumu.

Ievads datu struktūrās

1. attēls: Datu vienumu attēlojums

Iepriekš minētajā piemērā tādi vienumi kā ID, vecums, dzimums, pirmais, vidējais, pēdējais, iela, atrašanās vieta utt. ir elementāri datu vienumi. Turpretim nosaukums un adrese ir grupas datu vienumi.

Kas ir datu struktūra?

Datu struktūra ir datorzinātņu nozare. Datu struktūras izpēte ļauj izprast datu organizāciju un datu plūsmas pārvaldību, lai paaugstinātu jebkura procesa vai programmas efektivitāti. Datu struktūra ir īpašs veids, kā saglabāt un kārtot datus datora atmiņā, lai šos datus varētu viegli izgūt un vajadzības gadījumā efektīvi izmantot nākotnē. Datus var pārvaldīt dažādos veidos, piemēram, loģiskais vai matemātiskais modelis konkrētai datu organizācijai ir pazīstams kā datu struktūra.

Konkrēta datu modeļa apjoms ir atkarīgs no diviem faktoriem:

  1. Pirmkārt, tas ir pietiekami ielādēts struktūrā, lai atspoguļotu noteiktu datu korelāciju ar reālās pasaules objektu.
  2. Otrkārt, veidošanai jābūt tik vienkāršai, lai vajadzības gadījumā varētu pielāgoties datu efektīvai apstrādei.

Daži datu struktūru piemēri ir masīvi, saistītie saraksti, kaudze, rinda, koki utt. Datu struktūras tiek plaši izmantotas gandrīz visos datorzinātņu aspektos, t.i., kompilatoru dizainā, operētājsistēmās, grafikā, mākslīgajā intelektā un daudzos citos aspektos.

Datu struktūras ir daudzu datorzinātņu algoritmu galvenā daļa, jo tās ļauj programmētājiem efektīvi pārvaldīt datus. Tam ir izšķiroša nozīme programmas vai programmatūras veiktspējas uzlabošanā, jo programmatūras galvenais mērķis ir pēc iespējas ātrāk uzglabāt un izgūt lietotāja datus.

pasvītrot, izmantojot css

Ar datu struktūrām saistītās pamatterminoloģijas

Datu struktūras ir jebkuras programmatūras vai programmas pamatelementi. Programmai piemērotas datu struktūras izvēle programmētājam ir ārkārtīgi sarežģīts uzdevums.

Tālāk ir norādītas dažas pamata terminoloģijas, kas tiek izmantotas ikreiz, kad ir iesaistītas datu struktūras.

    Dati:Mēs varam definēt datus kā elementāru vērtību vai vērtību kopumu. Piemēram, Darbinieka vārds un ID ir ar Darbinieku saistītie dati.Datu vienumi:Viena vērtības vienība ir pazīstama kā datu vienība.Grupas vienumi:Datu vienumi, kuriem ir pakārtoti datu vienumi, ir zināmi kā grupas vienumi. Piemēram, darbinieka vārdam var būt vārds, vidējais un uzvārds.Elementārie priekšmeti:Datu vienumi, kurus nevar sadalīt apakšvienībās, ir zināmi kā elementārie vienumi. Piemēram, darbinieka ID.Entītija un atribūts:Noteiktu objektu klasi attēlo entītija. Tas sastāv no dažādiem atribūtiem. Katrs atribūts simbolizē šīs entītijas īpašo īpašību. Piemēram,
Atribūti ID Vārds Dzimums Amata nosaukums
Vērtības 1234. gads Steisija M. Hila Sieviete Programmatūras izstrādātājs

Entītijas ar līdzīgiem atribūtiem veido an Entītiju kopa . Katram entītiju kopas atribūtam ir vērtību diapazons, visu iespējamo vērtību kopa, ko varētu piešķirt konkrētajam atribūtam.

Termins “informācija” dažkārt tiek izmantots datiem ar noteiktiem nozīmīgu vai apstrādātu datu atribūtiem.

    Lauks:Viena elementāra informācijas vienība, kas simbolizē entītijas atribūtu, ir pazīstama kā lauks.Ieraksts:Dažādu datu vienumu kolekcija ir pazīstama kā ieraksts. Piemēram, ja mēs runājam par darbinieka entītiju, tad tās nosaukumu, ID, adresi un amata nosaukumu var grupēt, veidojot darbinieka ierakstu.Fails:Viena entītijas tipa dažādu ierakstu kolekcija ir zināma kā fails. Piemēram, ja ir 100 darbinieki, saistītajā failā būs 25 ieraksti, kas satur datus par katru darbinieku.

Izpratne par datu struktūru nepieciešamību

Lietojumprogrammas kļūst arvien sarežģītākas un datu apjoms katru dienu palielinās, kas var radīt problēmas ar datu meklēšanu, apstrādes ātrumu, vairāku pieprasījumu apstrādi un daudz ko citu. Datu struktūras atbalsta dažādas metodes, lai efektīvi organizētu, pārvaldītu un uzglabātu datus. Izmantojot datu struktūras, mēs varam viegli šķērsot datu vienumus. Datu struktūras nodrošina efektivitāti, atkārtotu izmantošanu un abstrakciju.

Kāpēc mums vajadzētu mācīties datu struktūras?

  1. Datu struktūras un algoritmi ir divi no galvenajiem datorzinātņu aspektiem.
  2. Datu struktūras ļauj mums sakārtot un uzglabāt datus, savukārt algoritmi ļauj apstrādāt šos datus jēgpilni.
  3. Datu struktūru un algoritmu apgūšana palīdzēs mums kļūt par labākiem programmētājiem.
  4. Mēs varēsim uzrakstīt kodu, kas ir efektīvāks un uzticamāks.
  5. Mēs arī spēsim ātrāk un efektīvāk atrisināt problēmas.

Datu struktūru mērķu izpratne

Datu struktūras atbilst diviem papildu mērķiem:

    Pareizība:Datu struktūras ir izstrādātas tā, lai tās pareizi darbotos visu veidu ievadē, pamatojoties uz interesējošo domēnu. Vārdu sakot, pareizība ir datu struktūras primārais mērķis, kas vienmēr ir atkarīgs no problēmām, kuras datu struktūrai ir paredzēts atrisināt.Efektivitāte:Datu struktūrām arī jābūt efektīvām. Tam vajadzētu ātri apstrādāt datus, neizmantojot daudzus datora resursus, piemēram, atmiņas vietu. Reāllaika stāvoklī datu struktūras efektivitāte ir galvenais faktors, kas nosaka procesa panākumus un neveiksmes.

Izpratne par dažām datu struktūru galvenajām iezīmēm

Dažas no nozīmīgajām datu struktūru iezīmēm ir:

    Izturība:Parasti visi datorprogrammētāji cenšas ražot programmatūru, kas nodrošina pareizu izvadi katrai iespējamai ievadei, kā arī efektīvu izpildi visās aparatūras platformās. Šāda veida spēcīgai programmatūrai ir jāpārvalda gan derīga, gan nederīga ievade.Pielāgošanās spēja:Tādas programmatūras lietojumprogrammas kā tīmekļa pārlūkprogrammas, tekstapstrādes programmas un interneta meklētājprogrammas ietver milzīgas programmatūras sistēmas, kurām ir nepieciešama pareiza un efektīva darbība vai izpilde daudzus gadus. Turklāt programmatūra attīstās, pateicoties jaunām tehnoloģijām vai pastāvīgi mainīgiem tirgus apstākļiem.Atkārtota izmantošana:Tādas funkcijas kā atkārtota izmantošana un pielāgojamība iet roku rokā. Ir zināms, ka programmētājam ir nepieciešami daudzi resursi, lai izveidotu jebkuru programmatūru, padarot to par dārgu uzņēmumu. Tomēr, ja programmatūra ir izstrādāta atkārtoti lietojamā un pielāgojamā veidā, to var izmantot lielākajā daļā turpmāko lietojumprogrammu. Tādējādi, izpildot kvalitatīvas datu struktūras, ir iespējams izveidot atkārtoti lietojamu programmatūru, kas šķiet rentabla un ietaupa laiku.

Datu struktūru klasifikācija

Datu struktūra nodrošina strukturētu mainīgo lielumu kopu, kas dažādos veidos ir savstarpēji saistīti. Tas veido pamatu programmēšanas rīkam, kas apzīmē attiecības starp datu elementiem un ļauj programmētājiem efektīvi apstrādāt datus.

Mēs varam klasificēt datu struktūras divās kategorijās:

listnode
  1. Primitīvā datu struktūra
  2. Neprimitīvā datu struktūra

Nākamajā attēlā parādītas dažādas datu struktūru klasifikācijas.

Ievads datu struktūrās

2. attēls: Datu struktūru klasifikācijas

Primitīvās datu struktūras

    Primitīvās datu struktūrasir datu struktūras, kas sastāv no cipariem un rakstzīmēm iebūvēts programmās.
  1. Šīs datu struktūras var manipulēt vai darbināt tieši ar mašīnas līmeņa instrukcijām.
  2. Pamatdatu veidi, piemēram Vesels skaitlis, pludiņš, rakstzīme , un Būla ietilpst primitīvajās datu struktūrās.
  3. Šos datu tipus sauc arī par Vienkārši datu veidi , jo tajos ir rakstzīmes, kuras nevar sadalīt tālāk

Neprimitīvas datu struktūras

    Neprimitīvas datu struktūrasir tās datu struktūras, kas iegūtas no primitīvajām datu struktūrām.
  1. Šīs datu struktūras nevar manipulēt vai darbināt tieši ar mašīnas līmeņa instrukcijām.
  2. Šo datu struktūru galvenā uzmanība tiek pievērsta datu elementu kopas veidošanai, kas ir vai nu viendabīgs (tas pats datu tips) vai neviendabīgs (dažādi datu veidi).
  3. Pamatojoties uz datu struktūru un izkārtojumu, šīs datu struktūras varam iedalīt divās apakškategorijās –
    1. Lineārās datu struktūras
    2. Nelineāras datu struktūras

Lineārās datu struktūras

Datu struktūra, kas saglabā lineāru savienojumu starp datu elementiem, ir pazīstama kā lineāra datu struktūra. Datu izkārtojums tiek veikts lineāri, kur katrs elements sastāv no pēctečiem un priekštečiem, izņemot pirmo un pēdējo datu elementu. Tomēr tas ne vienmēr ir taisnība atmiņas gadījumā, jo izkārtojums var nebūt secīgs.

Pamatojoties uz atmiņas sadalījumu, lineārās datu struktūras tiek iedalītas divos veidos:

    Statiskās datu struktūras:Datu struktūras ar fiksētu izmēru sauc par statiskām datu struktūrām. Atmiņa šīm datu struktūrām tiek piešķirta kompilatora laikā, un lietotājs pēc kompilēšanas to lielumu nevar mainīt; tomēr tajos saglabātos datus var mainīt.
    The Masīvs ir labākais statiskās datu struktūras piemērs, jo tām ir fiksēts lielums, un tās datus vēlāk var modificēt.Dinamiskās datu struktūras:Datu struktūras, kurām ir dinamisks izmērs, ir zināmas kā dinamiskās datu struktūras. Šo datu struktūru atmiņa tiek piešķirta izpildes laikā, un to lielums mainās koda izpildes laikā. Turklāt lietotājs koda izpildes laikā var mainīt šajās datu struktūrās saglabātos izmērus, kā arī datu elementus.
    Saistītie saraksti, skursteņi , un Astes ir izplatīti dinamisku datu struktūru piemēri

Lineāro datu struktūru veidi

Tālāk ir sniegts saraksts ar lineārajām datu struktūrām, kuras mēs parasti izmantojam:

1. Masīvi

An Masīvs ir datu struktūra, ko izmanto, lai vienā mainīgajā apkopotu vairākus viena veida datu elementus. Tā vietā, lai saglabātu vairākas viena un tā paša datu tipu vērtības atsevišķos mainīgo nosaukumos, mēs varētu tās visas saglabāt vienā mainīgajā. Šis apgalvojums nenozīmē, ka mums būs jāapvieno visas viena un tā paša datu tipa vērtības jebkurā programmā vienā šī datu tipa masīvā. Taču bieži vien daži konkrēti viena un tā paša datu tipu mainīgie ir saistīti viens ar otru masīvam piemērotā veidā.

Masīvs ir elementu saraksts, kurā katram elementam ir unikāla vieta sarakstā. Masīva datu elementiem ir vienāds mainīgā nosaukums; tomēr katram ir atšķirīgs indeksa numurs, ko sauc par apakšindeksu. Mēs varam piekļūt jebkuram datu elementam no saraksta, izmantojot tā atrašanās vietu sarakstā. Tādējādi masīvu galvenā iezīme, kas jāsaprot, ir tāda, ka dati tiek glabāti blakus esošās atmiņas vietās, ļaujot lietotājiem pārvietoties pa masīva datu elementiem, izmantojot to attiecīgos indeksus.

Ievads datu struktūrās

3. attēls. Masīvs

Masīvus var iedalīt dažādos veidos:

    Viendimensijas masīvs:Masīvu, kurā ir tikai viena datu elementu rinda, sauc par viendimensiju masīvu. Tas tiek glabāts augošā glabāšanas vietā.Divdimensiju masīvs:Masīvu, kas sastāv no vairākām datu elementu rindām un kolonnām, sauc par divdimensiju masīvu. To sauc arī par Matricu.Daudzdimensiju masīvs:Mēs varam definēt daudzdimensiju masīvu kā masīvu masīvu. Daudzdimensiju masīvi nav ierobežoti ar diviem indeksiem vai divām dimensijām, jo ​​tie var ietvert tik daudz indeksu, cik nepieciešams.

Dažas masīva lietojumprogrammas:

  1. Mēs varam saglabāt datu elementu sarakstu, kas pieder vienam datu tipam.
  2. Masīvs darbojas kā papildu krātuve citām datu struktūrām.
  3. Masīvs palīdz arī saglabāt fiksētā skaita binārā koka datu elementus.
  4. Masīvs darbojas arī kā matricu krātuve.

2. Saistītie saraksti

A Saistītais saraksts ir vēl viens piemērs lineārai datu struktūrai, ko izmanto datu elementu kolekcijas dinamiskai glabāšanai. Datu elementus šajā datu struktūrā attēlo mezgli, kas savienoti, izmantojot saites vai norādes. Katrā mezglā ir divi lauki, informācijas lauks sastāv no faktiskiem datiem, un rādītāja lauks sastāv no nākamo saraksta mezglu adreses. Saistītā saraksta pēdējā mezgla rādītājs sastāv no nulles rādītāja, jo tas norāda uz neko. Atšķirībā no masīviem lietotājs var dinamiski pielāgot saistītā saraksta izmēru atbilstoši prasībām.

saulains deols
Ievads datu struktūrās

4. attēls. Saistīts saraksts

Saistītos sarakstus var iedalīt dažādos veidos:

    Atsevišķi saistītais saraksts:Atsevišķi saistītais saraksts ir visizplatītākais saistīto sarakstu veids. Katram mezglam ir dati un rādītāja lauks, kurā ir nākamā mezgla adrese.Divkārši saistīts saraksts:Divkārši saistīts saraksts sastāv no informācijas lauka un diviem rādītāja laukiem. Informācijas lauks satur datus. Pirmajā rādītāja laukā ir iepriekšējā mezgla adrese, savukārt citā rādītāja laukā ir atsauce uz nākamo mezglu. Tādējādi mēs varam iet abos virzienos (atpakaļ un uz priekšu).Apļveida saistīto saraksts:Circular Linked List ir līdzīgs atsevišķi saistītajam sarakstam. Vienīgā galvenā atšķirība ir tā, ka pēdējā mezglā ir pirmā mezgla adrese, veidojot apļveida cilpu Circular Linked List.

Dažas saistīto sarakstu lietojumprogrammas:

  1. Saistītie saraksti palīdz mums ieviest iepriekš noteikta izmēra stekus, rindas, bināros kokus un grafikus.
  2. Varam ieviest arī operētājsistēmas funkciju dinamiskai atmiņas pārvaldībai.
  3. Saistītie saraksti pieļauj arī matemātisku darbību polinomu ieviešanu.
  4. Mēs varam izmantot Circular Linked List, lai ieviestu operētājsistēmas vai lietojumprogrammu funkcijas, kas nodrošina uzdevumu izpildi.
  5. Apļveida saistītais saraksts ir noderīgs arī slaidrādē, kurā lietotājam pēc pēdējā slaida ir jāatgriežas pie pirmā slaida.
  6. Divkārši saistīts saraksts tiek izmantots, lai pārlūkprogrammā ieviestu pogas uz priekšu un atpakaļ, lai pārvietotos uz priekšu un atpakaļ atvērtajās vietnes lapās.

3. Kaudzītes

A Kaudze ir lineāra datu struktūra, kas seko LIFO (Last In, First Out) princips, kas ļauj veikt tādas darbības kā ievietošana un dzēšana no viena steka gala, t.i., no augšas. Stackus var ieviest, izmantojot blakus esošo atmiņu, masīvu un nesaistīto atmiņu, saistīto sarakstu. Reāli Stacks piemēri ir grāmatu kaudzes, kāršu komplekts, naudas kaudzes un daudz kas cits.

Ievads datu struktūrās

5. attēls. Stacka piemērs dzīvē

Iepriekš redzamajā attēlā ir parādīts kaudzes reāls piemērs, kur darbības tiek veiktas tikai no viena gala, piemēram, jaunu grāmatu ievietošana un noņemšana no kaudzes augšdaļas. Tas nozīmē, ka ievietošanu un dzēšanu kaudzē var veikt tikai no steka augšdaļas. Mēs jebkurā laikā varam piekļūt tikai Stack virsotnēm.

Galvenās operācijas stekā ir šādas:

    Spiediet:Darbība jauna elementa ievietošanai kaudzē tiek saukta par nospiešanas darbību.Pop:Darbību elementu noņemšanai vai dzēšanai no kaudzes sauc par pop operāciju.
Ievads datu struktūrās

6. attēls. Stack

Daži steku pielietojumi:

  1. Stack tiek izmantots kā pagaidu krātuves struktūra rekursīvām operācijām.
  2. Stack tiek izmantots arī kā papildu krātuves struktūra funkciju izsaukumiem, ligzdotām darbībām un atliktajām/atliktajām funkcijām.
  3. Mēs varam pārvaldīt funkciju zvanus, izmantojot Stacks.
  4. Stacki tiek izmantoti arī, lai novērtētu aritmētiskās izteiksmes dažādās programmēšanas valodās.
  5. Stacki ir noderīgi arī, lai pārveidotu infix izteiksmes par postfix izteiksmēm.
  6. Stacki ļauj mums pārbaudīt izteiksmes sintaksi programmēšanas vidē.
  7. Mēs varam saskaņot iekavas, izmantojot Stacks.
  8. Stackus var izmantot, lai apgrieztu virkni.
  9. Stacki ir noderīgi, risinot problēmas, kuru pamatā ir atkāpšanās.
  10. Mēs varam izmantot Stacks padziļinātajā meklēšanā grafikā un kokā.
  11. Stacki tiek izmantoti arī operētājsistēmas funkcijās.
  12. Kaudzītes tiek izmantotas arī rediģēšanas funkcijās UNDO un REDO.

4. Astes

A Rinda ir lineāra datu struktūra, kas līdzīga stekam ar dažiem elementu ievietošanas un dzēšanas ierobežojumiem. Elementa ievietošana rindā tiek veikta vienā galā, un noņemšana tiek veikta citā vai pretējā galā. Tādējādi mēs varam secināt, ka rindas datu struktūra ievēro FIFO (First In, First Out) principu, lai manipulētu ar datu elementiem. Rindu ieviešanu var veikt, izmantojot masīvus, saistītos sarakstus vai skursteņus. Daži rindu piemēri dzīvē ir rinda pie biļešu kases, eskalators, automazgātava un daudz kas cits.

Ievads datu struktūrās

7. attēls. Reāls rindas piemērs

Iepriekš redzamajā attēlā ir reāli ilustrēts filmu biļešu skaitītājs, kas var palīdzēt mums saprast rindu, kurā pirmais vienmēr tiek apkalpots pirmais klients. Klients, kurš ieradīsies pēdējais, neapšaubāmi tiks apkalpots pēdējais. Abi rindas gali ir atvērti un var izpildīt dažādas darbības. Vēl viens piemērs ir pārtikas tiesas līnija, kurā klients tiek ievietots no aizmugures, bet klients tiek noņemts priekšgalā pēc tam, kad ir sniegts pakalpojums, ko viņš lūdza.

Šīs ir rindas galvenās darbības:

    Rinda:Dažu datu elementu ievietošana vai pievienošana rindā tiek saukta par rindu. Elementu ievietošana vienmēr tiek veikta ar aizmugurējā rādītāja palīdzību.Atkāpties no rindas:Datu elementu dzēšana vai noņemšana no rindas tiek saukta par rindu. Elementa dzēšana vienmēr tiek veikta ar priekšējā rādītāja palīdzību.
Ievads datu struktūrās

8. attēls. Rinda

Daži rindu lietojumi:

  1. Rindas parasti tiek izmantotas platuma meklēšanas operācijā Graphs.
  2. Rindas tiek izmantotas arī operētājsistēmu darbu plānotāja darbībās, piemēram, tastatūras bufera rinda, lai saglabātu lietotāju nospiestos taustiņus, un drukas bufera rinda, lai saglabātu printera izdrukātos dokumentus.
  3. Rindas ir atbildīgas par CPU plānošanu, darba plānošanu un diska plānošanu.
  4. Prioritātes rindas tiek izmantotas failu lejupielādes operācijās pārlūkprogrammā.
  5. Rindas tiek izmantotas arī datu pārsūtīšanai starp perifērijas ierīcēm un centrālo procesoru.
  6. Rindas ir atbildīgas arī par CPU lietotāju lietojumprogrammu radīto pārtraukumu apstrādi.

Nelineāras datu struktūras

Nelineārās datu struktūras ir datu struktūras, kurās datu elementi nav sakārtoti secīgā secībā. Šeit datu ievietošana un noņemšana nav iespējama lineārā veidā. Starp atsevišķiem datu vienumiem pastāv hierarhiskas attiecības.

Nelineāro datu struktūru veidi

Tālāk ir sniegts to nelineāro datu struktūru saraksts, kuras mēs parasti izmantojam.

saraksts uz java

1. Koki

Koks ir nelineāra datu struktūra un hierarhija, kas satur tādu mezglu kolekciju, kurā katrs koka mezgls saglabā vērtību un atsauču sarakstu uz citiem mezgliem (“bērniem”).

Koka datu struktūra ir specializēta metode datu kārtošanai un apkopošanai datorā, lai tos izmantotu efektīvāk. Tajā ir centrālais mezgls, strukturālie mezgli un apakšmezgli, kas savienoti ar malām. Mēs varam arī teikt, ka koka datu struktūra sastāv no saknēm, zariem un lapām, kas ir savienotas.

Ievads datu struktūrās

9. attēls. Koks

Kokus var iedalīt dažādos veidos:

    Binārais koks:Koka datu struktūra, kurā katram vecākajam mezglam var būt ne vairāk kā divi bērni, tiek saukta par bināro koku.Binārās meklēšanas koks:Binārā meklēšanas koks ir koka datu struktūra, kurā mēs varam viegli uzturēt sakārtotu skaitļu sarakstu.AVL koks:AVL koks ir pašbalansējošs binārais meklēšanas koks, kurā katrs mezgls uztur papildu informāciju, kas pazīstama kā līdzsvara koeficients, kura vērtība ir -1, 0 vai +1.B koks:B-Tree ir īpašs pašbalansējošais binārās meklēšanas koks, kurā katrs mezgls sastāv no vairākām atslēgām un tam var būt vairāk nekā divi bērni.

Daži koku pielietojumi:

  1. Koki ievieš hierarhiskas struktūras datorsistēmās, piemēram, direktorijos un failu sistēmās.
  2. Koki tiek izmantoti arī vietnes navigācijas struktūras ieviešanai.
  3. Mēs varam ģenerēt kodu, piemēram, Hafmena kodu, izmantojot kokus.
  4. Koki ir noderīgi arī lēmumu pieņemšanā spēļu lietojumprogrammās.
  5. Koki ir atbildīgi par prioritāro rindu ieviešanu uz prioritātēm balstītām OS plānošanas funkcijām.
  6. Koki ir atbildīgi arī par izteiksmju un paziņojumu parsēšanu dažādu programmēšanas valodu kompilatoros.
  7. Mēs varam izmantot kokus, lai saglabātu datu atslēgas datu bāzes pārvaldības sistēmas (DBMS) indeksēšanai.
  8. Spanning Trees ļauj mums maršrutēt lēmumus datoru un sakaru tīklos.
  9. Koki tiek izmantoti arī ceļa meklēšanas algoritmā, kas ieviests mākslīgā intelekta (AI), robotikas un videospēļu lietojumprogrammās.

2. Grafiki

Grafs ir vēl viens nelineāras datu struktūras piemērs, kas ietver ierobežotu skaitu mezglu vai virsotņu un tos savienojošās malas. Grafikus izmanto, lai risinātu reālās pasaules problēmas, kurās tie apzīmē problēmas apgabalu kā tīklu, piemēram, sociālos tīklus, ķēdes tīklus un tālruņu tīklus. Piemēram, diagrammas mezgli vai virsotnes var attēlot vienu lietotāju telefona tīklā, bet malas attēlo saikni starp tiem, izmantojot tālruni.

Grafika datu struktūra G tiek uzskatīta par matemātisko struktūru, kas sastāv no virsotņu kopas V un malu kopas E, kā parādīts tālāk:

G = (V,E)

Ievads datu struktūrās

10. attēls. Grafiks

Iepriekš redzamais attēls attēlo grafiku ar septiņām virsotnēm A, B, C, D, E, F, G un desmit malām [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] un [E, G].

Atkarībā no virsotņu un šķautņu atrašanās vietas grafikus var iedalīt dažādos veidos:

    Null diagramma:Grafiku ar tukšu malu kopu sauc par nulles grafiku.Triviāls grafiks:Grafu, kuram ir tikai viena virsotne, sauc par triviālu grafiku.Vienkāršs grafiks:Grafiku bez pašcilpām un vairākām malām sauc par vienkāršu grafiku.Vairāki grafiki:Tiek uzskatīts, ka grafiks ir daudzkārtējs, ja tajā ir vairākas malas, bet nav pašcilpu.Pseidografiks:Grafiku ar pašcilpām un vairākām malām sauc par pseidografiku.Nevirzīts grafiks:Grafiku, kas sastāv no nevirzītām malām, sauc par nevirzītu grafiku.Režisēts grafiks:Grafiku, kas sastāv no virzītām malām starp virsotnēm, sauc par virzīto grafiku.Savienotais grafiks:Grafiku ar vismaz vienu ceļu starp katru virsotņu pāri sauc par savienoto grafiku.Atvienots grafiks:Grafiku, kurā nav neviena ceļa starp vismaz vienu virsotņu pāri, sauc par atvienotu grafiku.Parastais grafiks:Grafiku, kurā visām virsotnēm ir vienāda pakāpe, sauc par regulāru grafiku.Pilns grafiks:Grafiku, kurā visām virsotnēm ir mala starp katru virsotņu pāri, sauc par pilnīgu grafiku.Cikla diagramma:Grafu sauc par ciklu, ja tam ir vismaz trīs virsotnes un malas, kas veido ciklu.Cikliskais grafiks:Grafiku sauc par ciklisku tad un tikai tad, ja pastāv vismaz viens cikls.Aciklisks grafiks:Grafiku, kuram ir nulle cikli, sauc par aciklisko grafiku.Galīgs grafiks:Grafiku ar ierobežotu virsotņu un malu skaitu sauc par ierobežotu grafiku.Bezgalīgs grafiks:Grafiku ar bezgalīgu virsotņu un malu skaitu sauc par bezgalīgu grafiku.Divpusējs grafiks:Grafiku, kurā virsotnes var sadalīt neatkarīgās kopās A un B, un visas kopas A virsotnes ir jāsavieno tikai ar virsotnēm, kas atrodas kopā B ar dažām malām, tiek saukta par divpusējo grafiku.Plaknes diagramma:Grafu sauc par plakni, ja mēs varam to uzzīmēt vienā plaknē ar divām malām, kas krustojas viena ar otru.Eilera grafiks:Grafu sauc par Eileru tad un tikai tad, ja visas virsotnes ir pāra grādi.Hamiltona grafiks:Savienots grafiks, kas sastāv no Hamiltona shēmas, ir pazīstams kā Hamiltona grafiks.

Daži grafiku pielietojumi:

  1. Grafiki palīdz mums attēlot maršrutus un tīklus transporta, ceļojumu un sakaru lietojumprogrammās.
  2. Grafikus izmanto, lai parādītu maršrutus GPS.
  3. Grafiki arī palīdz mums attēlot savstarpējos savienojumus sociālajos tīklos un citās tīkla lietojumprogrammās.
  4. Grafikus izmanto kartēšanas lietojumprogrammās.
  5. Grafiki ir atbildīgi par lietotāja preferenču attēlojumu e-komercijas lietojumprogrammās.
  6. Grafikus izmanto arī komunālajos tīklos, lai identificētu vietējām vai pašvaldību korporācijām radītās problēmas.
  7. Grafiki palīdz arī pārvaldīt resursu izmantošanu un pieejamību organizācijā.
  8. Grafikus izmanto arī, lai izveidotu vietņu dokumentu saišu kartes, lai parādītu savienojumu starp lapām, izmantojot hipersaites.
  9. Grafikus izmanto arī robotu kustībās un neironu tīklos.

Datu struktūru pamatoperācijas

Nākamajā sadaļā mēs apspriedīsim dažāda veida darbības, kuras varam veikt, lai manipulētu ar datiem katrā datu struktūrā:

    Šķērsošana:Datu struktūras šķērsošana nozīmē, ka katram datu elementam ir jāpiekļūst precīzi vienreiz, lai to varētu administrēt. Piemēram, pārvietošana ir nepieciešama, drukājot visu nodaļas darbinieku vārdus.Meklēt:Meklēšana ir cita datu struktūras darbība, kas nozīmē viena vai vairāku datu elementu atrašanās vietas atrašanu, kas atbilst noteiktiem ierobežojumiem. Šāds datu elements var būt vai var nebūt dotajā datu elementu kopā. Piemēram, mēs varam izmantot meklēšanas darbību, lai atrastu visu to darbinieku vārdus, kuriem ir vairāk nekā 5 gadu pieredze.Ievietošana:Ievietošana nozīmē jaunu datu elementu ievietošanu vai pievienošanu kolekcijai. Piemēram, mēs varam izmantot ievietošanas darbību, lai pievienotu informāciju par jaunu darbinieku, kuru uzņēmums nesen ir pieņēmis darbā.Dzēšana:Dzēšana ir noteikta datu elementa noņemšana vai dzēšana no dotā datu elementu saraksta. Piemēram, mēs varam izmantot dzēšanas darbību, lai izdzēstu darbinieka vārdu, kurš atstājis darbu.Šķirošana:Kārtošana nozīmē datu elementu sakārtošanu augošā vai dilstošā secībā atkarībā no lietojumprogrammas veida. Piemēram, mēs varam izmantot šķirošanas darbību, lai sakārtotu nodaļas darbinieku vārdus alfabēta secībā vai novērtētu mēneša labākos trīs izpildītājus, sakārtojot darbinieku sniegumu dilstošā secībā un izvelkot informāciju par labāko trīs.Apvienot:Apvienošana nozīmē divu sakārtotu sarakstu datu elementu apvienošanu, lai izveidotu vienu sakārtotu datu elementu sarakstu.Izveidot:Create ir darbība, ko izmanto, lai rezervētu atmiņu programmas datu elementiem. Mēs varam veikt šo darbību, izmantojot deklarācijas paziņojumu. Datu struktūras izveide var notikt šādos gadījumos:
    1. Kompilēšanas laiks
    2. Izpildes laiks
      Piemēram, malloc () funkcija tiek izmantota C valodā, lai izveidotu datu struktūru.
    Izlase:Atlase nozīmē konkrētu datu atlasi no pieejamajiem datiem. Mēs varam atlasīt jebkurus konkrētus datus, norādot nosacījumus cilpas iekšienē.Atjaunināt:Atjaunināšanas darbība ļauj atjaunināt vai modificēt datus datu struktūrā. Mēs varam arī atjaunināt jebkurus konkrētus datus, norādot dažus nosacījumus cilpas ietvaros, piemēram, atlases darbību.Sadalīšana:Sadalīšanas darbība ļauj mums sadalīt datus dažādās apakšdaļās, samazinot kopējo procesa pabeigšanas laiku.

Izpratne par abstrakto datu tipu

Saskaņā ar Nacionālais standartu un tehnoloģiju institūts (NIST) , datu struktūra ir informācijas izkārtojums, parasti atmiņā, lai uzlabotu algoritma efektivitāti. Datu struktūras ietver saistītos sarakstus, stekas, rindas, kokus un vārdnīcas. Tās varētu būt arī teorētiskas vienības, piemēram, personas vārds un adrese.

No iepriekš minētās definīcijas mēs varam secināt, ka darbības datu struktūrā ietver:

  1. Augsts abstrakciju līmenis, piemēram, vienuma pievienošana vai dzēšana no saraksta.
  2. Vienuma meklēšana un kārtošana sarakstā.
  3. Piekļuve visaugstākās prioritātes vienumam sarakstā.

Ikreiz, kad datu struktūra veic šādas darbības, to sauc par an Abstract Data Type (ADT) .

Mēs to varam definēt kā datu elementu kopu kopā ar darbībām ar datiem. Termins “abstrakts” attiecas uz faktu, ka dati un tajos definētās pamatoperācijas tiek pētītas neatkarīgi no to ieviešanas. Tas ietver to, ko mēs varam darīt ar datiem, nevis to, kā mēs varam to darīt.

mvc java

ADI ieviešana satur krātuves struktūru, lai saglabātu datu elementus un algoritmus pamatdarbībai. Visas datu struktūras, piemēram, masīvs, saistītais saraksts, rinda, kaudze utt., ir ADT piemēri.

Izpratne par ADT izmantošanas priekšrocībām

Reālajā pasaulē programmas attīstās jaunu ierobežojumu vai prasību rezultātā, tāpēc, lai mainītu programmu, parasti ir jāmaina viena vai vairākas datu struktūras. Piemēram, pieņemsim, ka vēlamies darbinieka ierakstā ievietot jaunu lauku, lai izsekotu sīkākai informācijai par katru darbinieku. Tādā gadījumā mēs varam uzlabot programmas efektivitāti, aizstājot masīvu ar saistīto struktūru. Šādā situācijā nav piemērota katras procedūras pārrakstīšana, kas izmanto modificēto struktūru. Tādējādi labāka alternatīva ir atdalīt datu struktūru no tās ieviešanas informācijas. Šis ir abstrakto datu tipu (ADT) izmantošanas princips.

Daži datu struktūru lietojumi

Tālāk ir norādītas dažas datu struktūru lietojumprogrammas.

  1. Datu struktūras palīdz sakārtot datus datora atmiņā.
  2. Datu struktūras palīdz arī attēlot informāciju datu bāzēs.
  3. Datu struktūras ļauj ieviest algoritmus, lai meklētu datus (piemēram, meklētājprogrammu).
  4. Mēs varam izmantot datu struktūras, lai ieviestu algoritmus manipulēšanai ar datiem (piemēram, tekstapstrādes programmas).
  5. Mēs varam arī ieviest algoritmus datu analīzei, izmantojot datu struktūras (piemēram, datu ieguves rīkus).
  6. Datu struktūras atbalsta algoritmus datu ģenerēšanai (piemēram, nejaušo skaitļu ģenerators).
  7. Datu struktūras atbalsta arī algoritmus datu saspiešanai un atspiešanai (piemēram, zip utilīta).
  8. Mēs varam arī izmantot datu struktūras, lai ieviestu algoritmus datu šifrēšanai un atšifrēšanai (piemēram, drošības sistēma).
  9. Ar Data Structures palīdzību mēs varam izveidot programmatūru, kas var pārvaldīt failus un direktorijus (piemēram, failu pārvaldnieks).
  10. Mēs varam arī izstrādāt programmatūru, kas var atveidot grafiku, izmantojot datu struktūras. (Piemēram, tīmekļa pārlūkprogramma vai 3D renderēšanas programmatūra).

Papildus tām, kā minēts iepriekš, ir arī daudzas citas datu struktūru lietojumprogrammas, kas var palīdzēt mums izveidot jebkuru vēlamo programmatūru.