Tietokoneiden keksimisestä lähtien ihmiset ovat käyttäneet termiä ' Data ' tarkoittaa joko siirrettyjä tai tallennettuja tietokonetietoja. On kuitenkin olemassa dataa, joka on olemassa myös tilaustyypeissä. Data voi olla numeroita tai tekstejä, jotka on kirjoitettu paperille, elektronisten laitteiden muistiin tallennettuina bitteinä ja tavuina, tai ihmisen mieleen tallennettuja faktoja. Kun maailma alkoi modernisoitua, näistä tiedoista tuli merkittävä osa jokaisen jokapäiväistä elämää, ja erilaiset toteutukset antoivat heille mahdollisuuden tallentaa niitä eri tavalla.

Data on kokoelma tosiasioita ja lukuja tai joukko arvoja tai tietyn muotoisia arvoja, jotka viittaavat yhteen nimikearvojen joukkoon. Tietokohteet luokitellaan sitten alanimikkeisiin, jotka ovat kohteiden ryhmä, joita ei tunneta alkion yksinkertaisena ensisijaisena muotona.

Tarkastellaanpa esimerkkiä, jossa työntekijän nimi voidaan jakaa kolmeen alakohtaan: Ensimmäinen, keskimmäinen ja viimeinen. Työntekijälle annettu tunnus katsotaan kuitenkin yleensä yhdeksi tavaraksi.

Kuvio 1: Tietojen esitys

Yllä mainitussa esimerkissä kohteet, kuten tunnus, ikä, sukupuoli, ensimmäinen, keskimmäinen, viimeinen, katu, paikkakunta jne., ovat perustietokohteita. Sitä vastoin Nimi ja osoite ovat ryhmätietokohteita.

Mikä on tietorakenne?

Tietorakenne on tietojenkäsittelytieteen ala. Tietorakenteen tutkiminen antaa meille mahdollisuuden ymmärtää tiedon organisointia ja tietovirran hallintaa minkä tahansa prosessin tai ohjelman tehokkuuden lisäämiseksi. Tietorakenne on erityinen tapa tallentaa ja järjestää tietoja tietokoneen muistissa, jotta nämä tiedot voidaan helposti hakea ja hyödyntää tehokkaasti tulevaisuudessa tarvittaessa. Tietoa voidaan hallita monin eri tavoin, kuten looginen tai matemaattinen malli tietylle dataorganisaatiolle tunnetaan tietorakenteella.

Tietyn tietomallin laajuus riippuu kahdesta tekijästä:

1. Ensinnäkin se on ladattava rakenteeseen tarpeeksi, jotta se heijastelee tietojen selvää korrelaatiota todellisen kohteen kanssa.
2. Toiseksi muodostuksen tulee olla niin suoraviivaista, että voidaan mukautua käsittelemään tietoja tehokkaasti aina kun se on tarpeen.

Joitakin esimerkkejä tietorakenteista ovat taulukot, linkitetyt luettelot, pino, jono, puut jne. Tietorakenteita käytetään laajalti lähes kaikilla tietojenkäsittelytieteen osa-alueilla, eli kääntäjien suunnittelussa, käyttöjärjestelmissä, grafiikassa, tekoälyssä ja monissa muissa.

Tietorakenteet ovat pääosa monissa tietojenkäsittelytieteen algoritmeissa, koska niiden avulla ohjelmoijat voivat hallita tietoja tehokkaasti. Sillä on ratkaiseva rooli ohjelman tai ohjelmiston suorituskyvyn parantamisessa, sillä ohjelmiston päätavoitteena on tallentaa ja hakea käyttäjän tiedot mahdollisimman nopeasti.

java merkkijono liittyä

Tietorakenteisiin liittyvät perusterminologiat

Tietorakenteet ovat minkä tahansa ohjelmiston tai ohjelman rakennuspalikoita. Ohjelmalle sopivan tietorakenteen valitseminen on erittäin haastava tehtävä ohjelmoijalle.

Seuraavassa on joitain perusterminologioita, joita käytetään aina, kun tietorakenteet ovat mukana:

Tiedot:Voimme määritellä datan perusarvoksi tai arvojen kokoelmaksi. Esimerkiksi Työntekijän nimi ja tunnus ovat työntekijään liittyviä tietoja.Tietokohteet:Yksittäinen arvoyksikkö tunnetaan nimellä Data Item.Ryhmäkohteet:Tietokohteita, joilla on alempia tietokohteita, kutsutaan ryhmäkohdiksi. Esimerkiksi työntekijän nimessä voi olla etu-, keski- ja sukunimi.Perusasioita:Tietokohteita, joita ei voida jakaa alakohdiksi, kutsutaan perustietokohdiksi. Esimerkiksi työntekijän tunnus.Entiteetti ja attribuutti:Tiettyjen objektien luokkaa edustaa entiteetti. Se koostuu erilaisista ominaisuuksista. Jokainen ominaisuus symboloi kyseisen entiteetin tiettyä ominaisuutta. Esimerkiksi,

Entiteetit, joilla on samanlaiset attribuutit, muodostavat an Entiteettijoukko . Jokaisella entiteettijoukon attribuutilla on arvoalue, joukko kaikkia mahdollisia arvoja, jotka voidaan määrittää tietylle attribuutille.

Termiä 'tieto' käytetään joskus tiedoista, joilla on tietyt merkityksellisten tai käsiteltyjen tietojen attribuutit.

Ala:Yksittäinen perustietoyksikkö, joka symboloi entiteetin attribuuttia, tunnetaan nimellä kenttä.Ennätys:Joukko erilaisia ​​tietokohteita tunnetaan tietueina. Jos esimerkiksi puhumme työntekijäkokonaisuudesta, sen nimi, tunnus, osoite ja tehtävänimike voidaan ryhmitellä työntekijän tietueen muodostamiseksi.Tiedosto:Yhden entiteettityypin eri tietueiden kokoelma tunnetaan nimellä tiedosto. Jos työntekijöitä on esimerkiksi 100, vastaavassa tiedostossa on 25 tietuetta, jotka sisältävät tiedot jokaisesta työntekijästä.

Tietorakenteiden tarpeen ymmärtäminen

Sovelluksista tulee monimutkaisempia ja tiedon määrä kasvaa joka päivä, mikä voi johtaa ongelmiin tiedonhaussa, käsittelynopeudessa, useiden pyyntöjen käsittelyssä ja monissa muissa. Tietorakenteet tukevat erilaisia ​​tapoja järjestää, hallita ja tallentaa tietoja tehokkaasti. Tietorakenteiden avulla voimme helposti kulkea tietokohteiden läpi. Tietorakenteet tarjoavat tehokkuutta, uudelleenkäytettävyyttä ja abstraktiota.

Miksi meidän pitäisi oppia tietorakenteet?

1. Tietorakenteet ja algoritmit ovat kaksi tietojenkäsittelytieteen keskeistä osa-aluetta.
2. Tietorakenteet antavat meille mahdollisuuden järjestää ja tallentaa tietoja, kun taas algoritmien avulla voimme käsitellä niitä mielekkäästi.
3. Tietorakenteiden ja algoritmien oppiminen auttaa meitä tulemaan paremmiksi ohjelmoijiksi.
4. Pystymme kirjoittamaan koodia, joka on tehokkaampi ja luotettavampi.
5. Pystymme myös ratkaisemaan ongelmia nopeammin ja tehokkaammin.

Tietorakenteiden tavoitteiden ymmärtäminen

Tietorakenteet täyttävät kaksi toisiaan täydentävää tavoitetta:

Oikeus:Tietorakenteet on suunniteltu toimimaan oikein kaikenlaisille syötteille kiinnostuksen kohteena olevan verkkotunnuksen perusteella. Toisin sanoen oikeellisuus on tietorakenteen ensisijainen tavoite, joka riippuu aina ongelmista, joita tietorakenteen on tarkoitus ratkaista.Tehokkuus:Tietorakenteet edellyttävät myös tehokkuutta. Sen pitäisi käsitellä tiedot nopeasti käyttämättä monia tietokoneen resursseja, kuten muistitilaa. Reaaliaikaisessa tilassa tietorakenteen tehokkuus on avaintekijä prosessin onnistumisen ja epäonnistumisen kannalta.

Tietorakenteiden tärkeimpien ominaisuuksien ymmärtäminen

Jotkut tietorakenteiden merkittävistä ominaisuuksista ovat:

Kestävyys:Yleensä kaikki tietokoneohjelmoijat pyrkivät tuottamaan ohjelmiston, joka tuottaa oikean tuloksen jokaiselle mahdolliselle syötteelle sekä tehokkaan suorituskyvyn kaikilla laitteistoalustoilla. Tämän tyyppisen vankan ohjelmiston täytyy hallita sekä kelvollisia että virheellisiä syötteitä.Sopeutuvuus:Ohjelmistosovellusten, kuten verkkoselainten, tekstinkäsittelyohjelmien ja Internet-hakukoneen, rakentaminen sisältää valtavia ohjelmistojärjestelmiä, jotka vaativat oikeaa ja tehokasta toimintaa useiden vuosien ajan. Lisäksi ohjelmistot kehittyvät uusien teknologioiden tai jatkuvasti muuttuvien markkinaolosuhteiden vuoksi.Uudelleenkäytettävyys:Ominaisuudet, kuten Uudelleenkäytettävyys ja Muokattavuus, kulkevat käsi kädessä. Tiedetään, että ohjelmoija tarvitsee monia resursseja minkä tahansa ohjelmiston rakentamiseen, mikä tekee siitä kalliin yrityksen. Kuitenkin, jos ohjelmisto on kehitetty uudelleen käytettävällä ja mukautuvalla tavalla, sitä voidaan soveltaa useimmissa tulevissa sovelluksissa. Näin ollen laadukkaita tietorakenteita toteuttamalla on mahdollista rakentaa uudelleenkäytettäviä ohjelmistoja, jotka vaikuttavat kustannustehokkaalta ja aikaa säästävältä.

Tietorakenteiden luokitus

Tietorakenne tarjoaa jäsennellyn joukon muuttujia, jotka liittyvät toisiinsa eri tavoin. Se muodostaa perustan ohjelmointityökalulle, joka ilmaisee dataelementtien välisen suhteen ja antaa ohjelmoijille mahdollisuuden käsitellä tietoja tehokkaasti.

Voimme luokitella tietorakenteet kahteen luokkaan:

1. Primitiivinen tietorakenne
2. Ei-primitiivinen tietorakenne

Seuraavassa kuvassa on esitetty tietorakenteiden eri luokitukset.

Kuva 2: Tietorakenteiden luokitukset

Primitiiviset tietorakenteet

Primitiiviset tietorakenteetovat tietorakenteita, jotka koostuvat numeroista ja tulevista merkeistä sisäänrakennettu ohjelmiin.
1. Näitä tietorakenteita voidaan manipuloida tai käyttää suoraan konetason käskyillä.
2. Perustietotyypit, kuten Kokonaisluku, Float, Merkki , ja Boolean kuuluvat primitiivisten tietorakenteiden alle.
3. Näitä tietotyyppejä kutsutaan myös Yksinkertaiset tietotyypit , koska ne sisältävät merkkejä, joita ei voi jakaa enempää

Ei-primitiiviset tietorakenteet

Ei-primitiiviset tietorakenteetovat ne tietorakenteet, jotka on johdettu primitiivisistä tietorakenteista.
1. Näitä tietorakenteita ei voi manipuloida tai käyttää suoraan konetason ohjeilla.
2. Näiden tietorakenteiden painopiste on tietoelementtien joukon muodostamisessa, joka on joko homogeeninen (sama tietotyyppi) tai heterogeeninen (eri tietotyypit).
3. Tietojen rakenteen ja järjestelyn perusteella voimme jakaa nämä tietorakenteet kahteen alaluokkaan -
   1. Lineaariset tietorakenteet
   2. Epälineaariset tietorakenteet

Lineaariset tietorakenteet

Tietorakenne, joka säilyttää lineaarisen yhteyden tietoelementtiensä välillä, tunnetaan nimellä Lineaar Data Structure. Tietojen järjestely tapahtuu lineaarisesti, jolloin jokainen elementti koostuu seuraajista ja edeltäjistä ensimmäistä ja viimeistä tietoelementtiä lukuun ottamatta. Se ei kuitenkaan välttämättä pidä paikkaansa muistin tapauksessa, koska järjestely ei välttämättä ole peräkkäinen.

Muistin varauksen perusteella lineaariset tietorakenteet luokitellaan edelleen kahteen tyyppiin:

Staattiset tietorakenteet:Kiinteän kokoisia tietorakenteita kutsutaan staattisiksi tietorakenteiksi. Muisti näille tietorakenteille varataan kääntäjän aikaan, eikä käyttäjä voi muuttaa niiden kokoa kääntämisen jälkeen; niihin tallennettuja tietoja voidaan kuitenkin muuttaa.
The Array on paras esimerkki staattisesta tietorakenteesta, koska niillä on kiinteä koko ja sen tietoja voidaan muokata myöhemmin.Dynaamiset tietorakenteet:Tietorakenteet, joilla on dynaaminen koko, tunnetaan nimellä Dynamic Data Structures. Näiden tietorakenteiden muisti varataan ajon aikana, ja niiden koko vaihtelee koodin ajon aikana. Lisäksi käyttäjä voi muuttaa kokoa sekä näihin tietorakenteisiin tallennettuja tietoelementtejä koodin ajon aikana.
Linkitetyt luettelot, pinot , ja Hännät ovat yleisiä esimerkkejä dynaamisista tietorakenteista

Lineaaristen tietorakenteiden tyypit

Seuraavassa on luettelo lineaarisista tietorakenteista, joita yleensä käytämme:

1. Taulukot

An Array on tietorakenne, jota käytetään keräämään useita saman tietotyypin tietoelementtejä yhdeksi muuttujaksi. Sen sijaan, että tallentaisimme useita samojen tietotyyppien arvoja erillisiin muuttujien nimiin, voisimme tallentaa ne kaikki yhdessä yhdeksi muuttujaksi. Tämä lause ei tarkoita, että meidän on yhdistettävä kaikki saman tietotyypin arvot missä tahansa ohjelmassa yhdeksi kyseisen tietotyypin matriisiksi. Mutta usein tulee aikoja, jolloin tietyt saman tietotyypin muuttujat liittyvät kaikki toisiinsa taulukolle sopivalla tavalla.

yhdistä lajittelualgoritmi

Array on luettelo elementeistä, joissa jokaisella elementillä on yksilöllinen paikka luettelossa. Taulukon tietoelementeillä on sama muuttujan nimi; jokaisella on kuitenkin eri indeksinumero, jota kutsutaan alaindeksiksi. Voimme käyttää mitä tahansa tietoelementtiä luettelosta sen sijainnin avulla luettelossa. Siten taulukoiden keskeinen ominaisuus on ymmärtää, että tiedot tallennetaan vierekkäisiin muistipaikkoihin, jolloin käyttäjät voivat kulkea taulukon tietoelementtien läpi käyttämällä vastaavia indeksejä.

Kuva 3. Taulukko

Taulukot voidaan luokitella eri tyyppeihin:

Yksiulotteinen taulukko:Array, jossa on vain yksi rivi tietoelementtejä, tunnetaan yksiulotteisena taulukona. Se on tallennettu nousevaan säilytyspaikkaan.Kaksiulotteinen taulukko:Useista tietoelementtien riveistä ja sarakkeista koostuvaa taulukkoa kutsutaan kaksiulotteiseksi taulukoksi. Se tunnetaan myös nimellä Matrix.Moniulotteinen taulukko:Voimme määritellä moniulotteisen taulukon taulukoiden taulukoksi. Moniulotteisia taulukoita ei ole rajoitettu kahteen indeksiin tai kahteen ulottuvuuteen, koska ne voivat sisältää niin monta indeksiä kuin tarve.

Jotkut Array-sovellukset:

1. Voimme tallentaa luettelon samaan tietotyyppiin kuuluvista tietoelementeistä.
2. Taulukko toimii muiden tietorakenteiden apumuistina.
3. Taulukko auttaa myös tallentamaan kiinteän määrän binääripuun dataelementtejä.
4. Array toimii myös matriisien varastona.

2. Linkitetyt luettelot

A Linkitetty lista on toinen esimerkki lineaarisesta tietorakenteesta, jota käytetään dataelementtien kokoelman tallentamiseen dynaamisesti. Tämän tietorakenteen tietoelementtejä edustavat solmut, jotka on yhdistetty linkkien tai osoittimien avulla. Jokainen solmu sisältää kaksi kenttää, tietokenttä koostuu todellisista tiedoista ja osoitinkenttä luettelossa olevien seuraavien solmujen osoitteista. Linkitetyn listan viimeisen solmun osoitin koostuu nollaosoittimesta, koska se ei osoita mihinkään. Toisin kuin Arrays, käyttäjä voi dynaamisesti säätää linkitetyn luettelon kokoa vaatimusten mukaisesti.

Kuva 4. Linkitetty lista

Linkitetyt luettelot voidaan luokitella eri tyyppeihin:

Yksittäin linkitetty lista:Yksittäin linkitetty luettelo on yleisin linkitettyjen luetteloiden tyyppi. Jokaisella solmulla on dataa ja osoitinkenttä, joka sisältää osoitteen seuraavaan solmuun.Kaksoislinkitetty lista:Kaksinkertaisesti linkitetty luettelo koostuu tietokentästä ja kahdesta osoitinkentästä. Tietokenttä sisältää tiedot. Ensimmäinen osoitinkenttä sisältää edellisen solmun osoitteen, kun taas toinen osoitinkenttä sisältää viittauksen seuraavaan solmuun. Näin ollen voimme mennä molempiin suuntiin (sekä taaksepäin että eteenpäin).Pyöreä linkitetty luettelo:Pyöreä linkitetty luettelo on samanlainen kuin yksittäinen linkitetty luettelo. Ainoa keskeinen ero on, että viimeinen solmu sisältää ensimmäisen solmun osoitteen muodostaen ympyränmuotoisen silmukan Circular Linked List -luetteloon.

Jotkut linkitettyjen luetteloiden sovellukset:

1. Linkitetyt listat auttavat meitä toteuttamaan pinoja, jonoja, binääripuita ja ennalta määritellyn kokoisia kaavioita.
2. Voimme myös toteuttaa Operating Systemin toiminnon dynaamiseen muistinhallintaan.
3. Linkitetyt listat mahdollistavat myös matemaattisten operaatioiden polynomin toteutuksen.
4. Voimme käyttää Circular Linked List -luetteloa toteuttamaan käyttöjärjestelmiä tai sovellustoimintoja, jotka pyörittävät tehtävien suorittamista.
5. Pyöreä linkitetty luettelo on hyödyllinen myös diaesityksessä, jossa käyttäjän on palattava ensimmäiseen diaan viimeisen dian esittämisen jälkeen.
6. Kaksoislinkitettyä listaa käytetään eteen- ja taaksepäin-painikkeiden toteuttamiseen selaimessa, jotta voit siirtyä eteenpäin ja taaksepäin verkkosivuston avatuilla sivuilla.

3. Pinot

A Pino on lineaarinen tietorakenne, joka seuraa LIFO (Last In, First Out) -periaate, joka mahdollistaa toiminnot, kuten lisäämisen ja poistamisen pinon yhdestä päästä, eli Topista. Pinot voidaan toteuttaa vierekkäisen muistin, taulukon ja ei-viereisen muistin, linkitetyn listan, avulla. Tosielämän esimerkkejä Stacksista ovat kirjapinot, korttipakat, rahakasat ja monet muut.

Kuva 5. Tosielämän esimerkki pinosta

Yllä oleva kuva esittää tosielämän esimerkkiä pinosta, jossa toiminnot suoritetaan vain yhdestä päästä, kuten uusien kirjojen lisääminen ja poistaminen pinon yläosasta. Se tarkoittaa, että pinon lisääminen ja poistaminen voidaan tehdä vain pinon yläosasta. Voimme käyttää vain Stackin yläosia kulloinkin.

verkkopankkitoiminnan haittoja

Pinon ensisijaiset toiminnot ovat seuraavat:

Työntää:Toimenpidettä uuden elementin lisäämiseksi pinoon kutsutaan työntötoiminnoksi.Pop:Toimintoa pinosta elementtien poistamiseksi tai poistamiseksi kutsutaan pop-operaatioksi.

Kuva 6. Pino

Jotkut pinojen sovellukset:

1. Pinoa käytetään tilapäisenä tallennusrakenteena rekursiivisia operaatioita varten.
2. Pinoa käytetään myös lisätallennusrakenteena funktiokutsuille, sisäkkäisille toiminnoille ja viivästetyille / lykätyille funktioille.
3. Pystymme hallitsemaan toimintokutsuja Stacksin avulla.
4. Pinoja käytetään myös eri ohjelmointikielien aritmeettisten lausekkeiden arvioimiseen.
5. Pinot ovat hyödyllisiä myös infix-lausekkeiden muuntamisessa postfix-lausekkeiksi.
6. Pinojen avulla voimme tarkistaa lausekkeen syntaksin ohjelmointiympäristössä.
7. Voimme täsmäyttää sulut käyttämällä pinoja.
8. Pinoja voidaan käyttää merkkijonon kääntämiseen.
9. Pinot auttavat ratkaisemaan perääntymiseen perustuvia ongelmia.
10. Voimme käyttää pinoja syvähaussa graafin ja puun läpikäymisessä.
11. Pinoja käytetään myös käyttöjärjestelmätoiminnoissa.
12. Pinoja käytetään myös muokkauksen UNDO- ja REDO-toiminnoissa.

4. Hännät

A Jonottaa on lineaarinen tietorakenne, joka on samanlainen kuin pino, jossa on joitain rajoituksia elementtien lisäämisessä ja poistamisessa. Elementin lisääminen jonoon tehdään toisessa päässä ja poistaminen toisessa tai vastakkaisessa päässä. Siten voimme päätellä, että Queue-tietorakenne noudattaa FIFO-periaatetta (First In, First Out) dataelementtien käsittelyssä. Jonojen käyttöönotto voidaan tehdä taulukoiden, linkitettyjen listojen tai pinojen avulla. Joitakin tosielämän esimerkkejä Jonoista ovat jono lipputiskillä, liukuportaat, autopesula ja monet muut.

Kuva 7. Tosielämän esimerkki jonosta

Yllä oleva kuva on tosielämän esimerkki elokuvalipputiskistä, joka voi auttaa meitä ymmärtämään jonon, jossa ensin palvellaan aina ensimmäisenä olevaa asiakasta. Viimeisenä saapuvaa asiakasta palvellaan epäilemättä viimeisenä. Jonon molemmat päät ovat avoimia ja voivat suorittaa erilaisia ​​toimintoja. Toinen esimerkki on ruokakenttälinja, jossa asiakas työnnetään sisään takapäästä, kun taas asiakas poistetaan etupäästä pyydetyn palvelun suorittamisen jälkeen.

Seuraavat ovat jonon ensisijaiset toiminnot:

Jono:Joidenkin tietoelementtien lisäämistä tai lisäämistä jonoon kutsutaan jonoksi. Elementtien lisäys tehdään aina takaosoittimen avulla.Poistaa jonosta:Tietoelementtien poistamista tai poistamista jonosta kutsutaan jonoksi. Elementin poisto tehdään aina etuosoittimen avulla.

Kuva 8. Jonottaa

Jotkut jonojen sovellukset:

1. Jonoja käytetään yleensä Graphsin leveyshaussa.
2. Jonoja käytetään myös käyttöjärjestelmien Job Scheduler -toiminnoissa, kuten näppäimistön puskurijono käyttäjien painamien näppäinten tallentamiseen ja tulostuspuskurijono tulostimen tulostamien asiakirjojen tallentamiseen.
3. Jonot vastaavat suorittimen ajoituksesta, työn ajoituksesta ja levyn ajoituksesta.
4. Priority Queues -jonoja käytetään tiedostojen lataamiseen selaimessa.
5. Jonoja käytetään myös tiedon siirtämiseen oheislaitteiden ja CPU:n välillä.
6. Jonot ovat myös vastuussa käyttäjäsovellusten CPU:lle luomien keskeytysten käsittelystä.

Epälineaariset tietorakenteet

Epälineaariset tietorakenteet ovat tietorakenteita, joissa tietoelementtejä ei ole järjestetty peräkkäiseen järjestykseen. Tässä tiedon lisääminen ja poistaminen ei ole mahdollista lineaarisesti. Yksittäisten tietokohteiden välillä on hierarkkinen suhde.

Epälineaaristen tietorakenteiden tyypit

Seuraavassa on luettelo epälineaarisista tietorakenteista, joita yleensä käytämme:

b+ puu

1. Puut

Puu on epälineaarinen tietorakenne ja hierarkia, joka sisältää kokoelman solmuja siten, että jokainen puun solmu tallentaa arvon ja luettelon viittauksista muihin solmuihin ('lapsiin').

Puun tietorakenne on erikoistunut tapa järjestää ja kerätä tietoja tietokoneeseen käytettäväksi tehokkaammin. Se sisältää keskussolmun, rakenteelliset solmut ja alisolmut, jotka on yhdistetty reunojen kautta. Voimme myös sanoa, että puun tietorakenne koostuu juurista, oksista ja lehdistä, jotka on yhdistetty toisiinsa.

Kuva 9. Puu

Puut voidaan luokitella eri tyyppeihin:

Binääripuu:Puutietorakennetta, jossa jokaisella pääsolmulla voi olla enintään kaksi lasta, kutsutaan binääripuuksi.Binäärihakupuu:Binäärihakupuu on puun tietorakenne, jossa voimme helposti ylläpitää lajiteltua numeroluetteloa.AVL-puu:AVL-puu on itsetasapainottava binäärihakupuu, jossa jokainen solmu ylläpitää ylimääräistä tietoa, joka tunnetaan tasapainotekijänä, jonka arvo on joko -1, 0 tai +1.B-puu:B-puu on erityinen itsetasapainottuva binaarihakupuu, jossa jokainen solmu koostuu useista avaimista ja sillä voi olla enemmän kuin kaksi lasta.

Jotkut puiden sovellukset:

1. Puut toteuttavat hierarkkisia rakenteita tietokonejärjestelmissä, kuten hakemistoissa ja tiedostojärjestelmissä.
2. Puita käytetään myös verkkosivuston navigointirakenteen toteuttamiseen.
3. Voimme luoda koodia, kuten Huffmanin koodia käyttämällä puita.
4. Puut ovat avuksi myös pelisovellusten päätöksenteossa.
5. Puut ovat vastuussa prioriteettijonojen toteuttamisesta prioriteettipohjaisille käyttöjärjestelmän ajoitustoiminnoille.
6. Puut vastaavat myös lausekkeiden ja lausekkeiden jäsentämisestä eri ohjelmointikielten kääntäjissä.
7. Voimme käyttää puita dataavainten tallentamiseen tietokannan hallintajärjestelmän (DBMS) indeksointia varten.
8. Spanning Treesin avulla voimme reitittää päätökset tietokone- ja viestintäverkoissa.
9. Puita käytetään myös tekoäly-, robotiikka- ja videopelisovelluksissa toteutetussa polunhakualgoritmissa.

2. Kaaviot

Graafi on toinen esimerkki epälineaarisesta tietorakenteesta, joka käsittää äärellisen määrän solmuja tai pisteitä ja niitä yhdistäviä reunoja. Graafeja käytetään ratkaisemaan todellisen maailman ongelmia, joissa se kuvaa ongelma-aluetta verkkona, kuten sosiaaliset verkostot, piiriverkostot ja puhelinverkot. Esimerkiksi Graafin solmut tai kärjet voivat edustaa yhtä käyttäjää puhelinverkossa, kun taas reunat edustavat niiden välistä linkkiä puhelimen kautta.

Graph-tietorakennetta G pidetään matemaattisena rakenteena, joka koostuu joukosta kärkijoukkoja V ja joukosta reunoja E, kuten alla on esitetty:

G = (V,E)

Kuva 10. Kaavio

Yllä oleva kuva edustaa kuvaajaa, jossa on seitsemän kärkeä A, B, C, D, E, F, G ja kymmenen reunaa [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] ja [E, G].

skriptien ajaminen linuxissa

Huippupisteiden ja reunojen sijainnista riippuen graafit voidaan luokitella eri tyyppeihin:

Nollakaavio:Graafia, jossa on tyhjät reunat, kutsutaan nollakuvaajaksi.Triviaali kaavio:Grafia, jossa on vain yksi kärki, kutsutaan triviaaliksi kuvaajaksi.Yksinkertainen kaavio:Graafia, jossa ei ole itsesilmukoita tai useita reunoja, kutsutaan yksinkertaiseksi kuvaajaksi.Monikuvaaja:Graafin sanotaan olevan moni, jos se koostuu useista reunoista, mutta ei itsesilmukoita.Pseudokaavio:Graafia, jossa on itsesilmukat ja useita reunoja, kutsutaan pseudograafiksi.Ohjaamaton kaavio:Suuntaamattomista reunoista koostuvaa kuvaajaa kutsutaan ohjaamattomaksi kuvaajaksi.Ohjattu graafi:Graafia, joka koostuu suunnatuista kärkien välisistä reunoista, kutsutaan suunnatuksi kuvaajaksi.Yhdistetty kaavio:Graafia, jossa on vähintään yksi polku jokaisen kärkiparin välillä, kutsutaan yhdistetyksi kuvaajaksi.Irrotettu kaavio:Graafia, jossa ei ole polkua vähintään yhden kärkiparin välillä, kutsutaan katkaistuksi kuvaajaksi.Tavallinen kaavio:Graafia, jossa kaikilla pisteillä on sama aste, kutsutaan säännölliseksi kuvaajaksi.Täydellinen kaavio:Graafia, jossa kaikilla pisteillä on reuna jokaisen pisteparin välillä, kutsutaan täydelliseksi kuvaajaksi.Kiertokaavio:Graafin sanotaan olevan sykli, jos siinä on vähintään kolme kärkeä ja reunaa, jotka muodostavat syklin.Syklinen kaavio:Graafin sanotaan olevan syklinen, jos ja vain jos vähintään yksi sykli on olemassa.Asyklinen kaavio:Graafia, jossa on nolla sykliä, kutsutaan asykliseksi kuvaajaksi.Rajallinen kuvaaja:Graafia, jossa on äärellinen määrä pisteitä ja reunoja, kutsutaan rajalliseksi kuvaajaksi.Ääretön kaavio:Graafi, jossa on ääretön määrä pisteitä ja reunoja, tunnetaan äärettömänä kuvaajana.Kaksiosainen kaavio:Graafia, jossa pisteet voidaan jakaa itsenäisiksi joukoiksi A ja B, ja joukon A kaikki kärjet tulisi yhdistää vain joukossa B oleviin kärkikohtiin joillakin reunoilla, kutsutaan bipartite Graphiksi.Tasokaavio:Graafin sanotaan olevan taso, jos voimme piirtää sen yhdelle tasolle, jossa kaksi reunaa leikkaa toisiaan.Euler-kaavio:Graafin sanotaan olevan Euler, jos ja vain jos kaikki kärjet ovat parillisia asteita.Hamiltonin kaavio:Hamiltonin piiristä koostuva yhdistetty kuvaaja tunnetaan Hamiltonin kuvaajana.

Jotkut kaavioiden sovellukset:

1. Kaaviot auttavat meitä esittämään reittejä ja verkkoja kuljetus-, matkailu- ja viestintäsovelluksissa.
2. Graafeja käytetään reittien näyttämiseen GPS:ssä.
3. Graafit auttavat meitä myös esittämään sosiaalisten verkostojen ja muiden verkkopohjaisten sovellusten välisiä yhteyksiä.
4. Kaavioita käytetään kartoitussovelluksissa.
5. Kaaviot vastaavat käyttäjien mieltymysten esittämisestä verkkokaupan sovelluksissa.
6. Kaavioita käytetään myös kunnallisverkoissa paikallisten tai kunnallisten yritysten ongelmien tunnistamiseen.
7. Graafit auttavat myös hallitsemaan organisaation resurssien käyttöä ja saatavuutta.
8. Kaavioista tehdään myös verkkosivujen dokumenttilinkkikarttoja, jotta sivujen väliset liitännät voidaan näyttää hyperlinkkien kautta.
9. Graafia käytetään myös robottiliikkeissä ja hermoverkoissa.

Tietorakenteiden perustoiminnot

Seuraavassa osiossa käsittelemme erilaisia ​​toimintoja, joita voimme suorittaa tietojen käsittelemiseksi jokaisessa tietorakenteessa:

Läpikulku:Tietorakenteen läpikäyminen tarkoittaa, että jokaiseen tietoelementtiin päästään tarkalleen kerran, jotta sitä voidaan hallita. Esimerkiksi läpikulku vaaditaan tulostettaessa kaikkien osaston työntekijöiden nimiä.Hae:Haku on toinen tietorakennetoiminto, joka tarkoittaa yhden tai useamman tietyt rajoitukset täyttävän tietoelementin sijainnin löytämistä. Tällainen tietoelementti voi olla tai ei välttämättä ole annetussa tietoelementtijoukossa. Hakutoiminnon avulla voimme esimerkiksi löytää kaikkien yli 5 vuoden kokemuksella olevien työntekijöiden nimet.Lisäys:Lisääminen tarkoittaa uusien tietoelementtien lisäämistä tai lisäämistä kokoelmaan. Voimme käyttää lisäystoimintoa esimerkiksi lisätäksesi yrityksen äskettäin palkkaaman uuden työntekijän tiedot.Poisto:Poistaminen tarkoittaa tietyn tietoelementin poistamista tai poistamista annetusta tietoelementtiluettelosta. Poistotoiminnolla voimme esimerkiksi poistaa työstä lähteneen työntekijän nimen.Lajittelu:Lajittelu tarkoittaa tietoelementtien järjestämistä joko nousevaan tai laskevaan järjestykseen sovelluksen tyypistä riippuen. Lajittelutoiminnon avulla voimme esimerkiksi järjestää osastolla olevien työntekijöiden nimet aakkosjärjestykseen tai arvioida kuukauden kolme parasta suorittajaa järjestämällä työntekijöiden suoritukset laskevaan järjestykseen ja poimimalla kolmen parhaan tiedot.Yhdistää:Yhdistäminen tarkoittaa kahden lajitellun luettelon tietoelementtien yhdistämistä yhdeksi lajitettujen tietoelementtien luetteloksi.Luoda:Luo on toiminto, jolla varataan muistia ohjelman tietoelementeille. Voimme suorittaa tämän toiminnon käyttämällä ilmoituslauseketta. Tietorakenteen luominen voi tapahtua joko seuraavan aikana:
1. Käännösaika
2. Ajoaika
   Esimerkiksi, malloc() funktiota käytetään C-kielessä tietorakenteen luomiseen.
Valinta:Valinta tarkoittaa tietyn tiedon valitsemista saatavilla olevista tiedoista. Voimme valita mitä tahansa tiettyä dataa määrittämällä ehdot silmukan sisällä.Päivittää:Päivitystoiminnon avulla voimme päivittää tai muokata tietorakenteen tietoja. Voimme myös päivittää mitä tahansa tiettyä dataa määrittämällä joitain ehtoja silmukan sisällä, kuten valintatoiminto.Jakaminen:Splitting-toiminto mahdollistaa tietojen jakamisen eri alaosiin, mikä vähentää prosessin kokonaisaikaa.

Abstraktin tietotyypin ymmärtäminen

Kuten mukaan National Institute of Standards and Technology (NIST) , tietorakenne on tietojen järjestely, yleensä muistissa, algoritmin tehokkuuden parantamiseksi. Tietorakenteet sisältävät linkitettyjä luetteloita, pinoja, jonoja, puita ja sanakirjoja. Ne voivat olla myös teoreettinen kokonaisuus, kuten henkilön nimi ja osoite.

Yllä mainitusta määritelmästä voimme päätellä, että tietorakenteen toiminnot sisältävät:

1. Suuri määrä abstraktioita, kuten kohteen lisääminen tai poistaminen luettelosta.
2. Kohteen etsiminen ja lajittelu luettelosta.
3. Pääsy luettelon korkeimman prioriteetin kohteeseen.

Aina kun tietorakenne suorittaa tällaisia ​​toimintoja, se tunnetaan nimellä an Abstrakti tietotyyppi (ADT) .

Voimme määritellä sen tietoelementtien joukoksi yhdessä datan toimintojen kanssa. Abstraktilla tarkoitetaan sitä, että dataa ja sillä määriteltyjä perustoimintoja tutkitaan niiden toteutuksesta riippumatta. Se sisältää mitä voimme tehdä tiedoilla, ei sitä, miten voimme tehdä sen.

ADI-toteutus sisältää tallennusrakenteen perustoimintojen tietoelementtien ja algoritmien tallentamiseksi. Kaikki tietorakenteet, kuten taulukko, linkitetty luettelo, jono, pino jne., ovat esimerkkejä ADT:stä.

ADT:n käytön edut ymmärtäminen

Todellisessa maailmassa ohjelmat kehittyvät uusien rajoitusten tai vaatimusten seurauksena, joten ohjelman muokkaaminen vaatii yleensä yhden tai useamman tietorakenteen muuttamisen. Oletetaan esimerkiksi, että haluamme lisätä uuden kentän työntekijän tietueeseen, jotta voimme seurata kunkin työntekijän lisätietoja. Siinä tapauksessa voimme parantaa ohjelman tehokkuutta korvaamalla taulukon linkitetyllä rakenteella. Tällaisessa tilanteessa jokaisen muutettua rakennetta hyödyntävän proseduurin uudelleenkirjoittaminen ei ole sopivaa. Tästä syystä parempi vaihtoehto on erottaa tietorakenne sen toteutustiedoista. Tämä on abstraktien tietotyyppien (ADT) käytön periaate.

Jotkut tietorakenteiden sovellukset

Seuraavassa on joitain tietorakenteiden sovelluksia:

1. Tietorakenteet auttavat tietojen järjestämisessä tietokoneen muistissa.
2. Tietorakenteet auttavat myös tietojen esittämisessä tietokantoissa.
3. Tietorakenteet mahdollistavat algoritmien toteuttamisen tietojen hakemiseksi (esimerkiksi hakukone).
4. Voimme käyttää tietorakenteita datan käsittelyalgoritmien toteuttamiseen (esimerkiksi tekstinkäsittelyohjelmat).
5. Voimme myös toteuttaa algoritmeja datan analysointiin käyttämällä tietorakenteita (esim. datalouhinta).
6. Tietorakenteet tukevat algoritmeja tietojen luomiseen (esimerkiksi satunnaislukugeneraattori).
7. Tietorakenteet tukevat myös algoritmeja tietojen pakkaamiseen ja purkamiseen (esimerkiksi zip-apuohjelma).
8. Voimme käyttää tietorakenteita myös algoritmien toteuttamiseen tietojen salaamiseksi ja salauksen purkamiseksi (esimerkiksi turvajärjestelmä).
9. Tietorakenteiden avulla voimme rakentaa ohjelmistoja, joilla voidaan hallita tiedostoja ja hakemistoja (esim. tiedostonhallinta).
10. Voimme myös kehittää ohjelmistoja, jotka voivat renderöidä grafiikkaa tietorakenteiden avulla. (Esimerkiksi verkkoselain tai 3D-renderöintiohjelmisto).

Näiden lisäksi, kuten aiemmin mainittiin, on monia muita tietorakenteiden sovelluksia, jotka voivat auttaa meitä rakentamaan minkä tahansa haluamasi ohjelmiston.