Linkitetyn luettelon opas: – Dynaamisen tietojen tallennuksen aloittaminen

Disclosure: Tukisi auttaa pitämään sivuston toiminnassa! Ansaitsemme lähetysmaksun joistakin tämän sivun suosittelemista palveluista.


Linkitetyt luettelot voivat olla arvokas työkalu, kun joudutaan rakentamaan erilaisia ​​tietojoukkoja ja järjestämään ohjelman lineaarinen tieto. Niitä käytetään yleisesti taulukon korvikkeena, koska niiden käytöllä on tiettyjä etuja.

Sen ytimessä linkitetty luettelo on yksinkertainen tietorakenne, joka pitää sisällään solmusarjan. Jokaisella solmulla on omat tiedot, plus osoitin toiseen solmuun. Itse asiassa heitä opetetaan usein saadakseen opiskelijat viihtymään osoittimien kanssa.

Alla opit, mitkä linkitetyt luettelot ovat, miksi ne ovat arvokkaita ja miten ne luodaan. Tarjoamme myös muutamia lisäresursseja koulutuksen edistämiseksi.

Mitkä ovat linkitetyt luettelot?

Yksinkertaisesti sanottuna, linkitetty luettelo on tilattu tietokokoelma. Se on tarkoitettu lineaarisille tietorakenteille ja on yksi helpoimmista dynaamisista tietorakenteista. Jokaista dataelementtiä kutsutaan solmuksi ja sisältää yhden arvon ja osoittimen luettelon seuraavaan solmuun. Jos osoittimella on NULL-arvo, kyseinen solmu on viimeinen luettelossa.

Tässä on esimerkki tietotekniikan ulkopuolelta käsityksen ymmärtämiseksi:

Oletetaan, että arvioit jokaista toimistossa olevaa henkilöä kirjoitusnopeuden perusteella. Luettelosi alkaisi Annillä, koska kaikki tietävät olevansa nopein – voit kuulla hänen kaapistaan ​​tulevan äänen. Hänelle on kerrottu, että seuraava nopein henkilö on Steve. Steve tietää, että hänen kirjoitusnopeutensa on lähellä Annin, mutta ei aivan yhtä hyvä. Hän tietää myös, että Karen on melkein yhtä nopea kuin on, mutta ei aivan. Luetteloa voidaan sitten jatkaa tällä tavalla. Jokaisella jäsenellä on ainutlaatuinen tieto ja indikaattori siitä, kuka on seuraava nopein konekirjoittaja.

Koska solmut ovat toisistaan ​​riippumattomia, paitsi osoitussuhteen avulla, ne on erittäin helppo lisätä, poistaa ja siirtää.

Yhdistettyjen luetteloiden tyypit

On olemassa muutamia erityyppisiä linkitettyjä luetteloita. Yksi linkitetty luettelo, kaksinkertaisesti linkitetty luettelo, monilinkitty luettelo ja pyöreä linkitetty luettelo. Tutkimme kutakin tarkemmin alla. Linkitettyjen luetteloiden avulla voit suorittaa lisäys-, poisto- ja poistotoimenpiteitä.

1. Yhden linkitetyn luettelon

Yksi linkitetty luettelo on kokoelma tietoobjekteja, jotka on linkitetty toisiinsa tietyillä viittauksilla objektista toiseen. Näitä esineitä kutsutaan usein solmuiksi. Jokainen solmu sisältää ainakin yhden tietokentän ja viittauksen seuraavaan solmuun. Yksittäisiin linkitettyihin luetteloihin pääsee ensimmäisen solmun kautta ja niitä voidaan kuljettaa luettelon loppuun asti.

2. Kaksinkertaisesti linkitetty luettelo

Kaksinkertaisesti linkitetyillä luetteloilla on kaksi viittausta kutakin solmua kohti. Viitteet osoittavat kohti seuraavaa solmua ja edellistä solmua. Tämän rakenteen avulla sinulla on kaksisuuntainen pääsy tietojoukkoon, ja se tarjoaa sinulle enemmän joustavuutta ja nopeutta, koska voit navigoida luettelossa molemmissa suunnissa.

3. Monilinkitty luettelo

Monilinkit ovat yleisesti linkitettyjä luetteloita, joissa on useita lisäluetteloita tietystä solmusta. Uudet luettelot voivat olla missä tahansa tässä mainituista tyyleistä. Tämä luettelotyyli voi olla hyödyllinen lajittelemalla luettelo, joka on eritelty käyttäjän nimen ja iän mukaan. Tai muita tietojoukkotyyppejä, joissa jokaisella datapisteellä on lisäluokituksia.

4. Pyöreä linkitetty luettelo

Lopullista linkitetyn luettelon tyyppiä kutsutaan pyöreäksi linkitetyksi luetteloksi. Sen sijaan, että lopullisella solmulla olisi NULL-komento, se viittaa takaisin luettelon päähän. Luettelon rakenne on samanlainen kuin yllä olevat vaihtoehdot.

Miksi linkitetyt luettelot ovat tärkeitä

Linkitetyt luettelot ovat hyödyllisiä niiden dynaamisen luonteen vuoksi. Laskennallisessa mielessä se varaa muistia vain tarvittaessa. Joten jos sinulla on sovellus, joka vaatii usein kokoa, poistoja, lisäyksiä ja tietojen päivityksiä, linkitetty luettelo on täydellinen.

Linkitettyjä luetteloita käytetään yleisesti kaavioiden, pinojen, jonojen ja muiden vastaavien ohjelmien toteuttamiseen. Linkitetyllä luettelolla voit lisätä kohteita mihin tahansa luettelon kohtaan. Lisäksi sinun ei tarvitse tietää lopullisen luettelon kokoa etukäteen. Sen koko voi kasvaa tai pienentyä mielestäsi.

Helppo lisääminen ja poistaminen on tärkeä etu linkitettyihin luetteloihin. Voit esimerkiksi käyttää taulukkoa, mutta taulukot antavat vain lisätä ja poistaa sarjan viimeisen objektin siirtämättä joukkoa tietoja avoimen paikan luomiseksi. Yhdistetyt luettelot mahdollistavat datan joukon helpon käsittelyn peräkkäin aiheuttamatta suurta rasitusta muistin resursseille.

Useimmat tietotekniikkaohjelmat opettavat edelleen opiskelijoille linkitettyjen luetteloiden toteuttamista. Tämä on vankka johdatus dynaamisiin tietorakenteisiin, joita haluat ehkä käyttää oikeissa ohjelmissa. Lisäksi, vaikka et koskaan käyttäisi linkitettyä luetteloa, se antaa sinulle riittävän ymmärryksen osoittimien käyttämiseen. Käytät varmasti osoittimia monissa tosielämäsi ohjelmissa.

Linkitetyn luettelon haitat

Linkitetyt luettelot ovat loistavia helposti muokattavan luettelon luomiseen. Ne eivät kuitenkaan ole täydellinen ratkaisu jokaiselle ohjelmalle, kuten näet alla:

  1. Linkitetyt luettelot eivät tarjoa satunnaista tukiasemaa. Jotta pääset tiettyyn kohtaan luettelossa, sinun täytyy iteroida jokaisen luettelon kohteen kohdalla siihen saakka.
  2. Koodista voi tulla hieman monimutkainen, koska koodin toiminta edellyttää sekä dynaamista muistin allokointia että osoittimia.
  3. Linkitetyn luettelon kokonaiskustannukset voivat olla korkeammat kuin taulukko, koska luettelot allokoidaan dynaamisesti.

Kaikki mitä sanotaan, linkitettyjen luetteloiden käytön tunteminen auttaa hallitsemaan osoittimien käytön ja ymmärtämään paremmin dynaamisia tietojoukkoja kokonaisuutena.

Linkitettyjen luetteloiden opetusohjelma

Alla opit luomaan ja toteuttamaan linkitetyn perusluettelon. Aloitamme luomalla yhden linkitetyn luettelon ja sen solmut, ja näytämme kuinka poistaa ja lisätä uusia solmuja.

Solmurakenteen luominen

Linkitetty luettelo koostuu useista solmuista, joten meidän on luotava solmu määrittelevä rakenne. Tämän on sisällettävä ainakin yksi datan muuttuja ja yksi osoitin seuraavalle solmulle viittaamiseksi. Pidämme kiinni kirjoitusnopeuden esimerkistämme ja käytämme henkilön nimeä ja nopeutta sekä tietojamme. Kohdassa C tiedot määritellään rakenteessa seuraavasti:

rakenteellinen solmu {
merkkijonon nimi [32];
int nopeus;
rakenne solmu * seuraavaksi;
}

Tärkeä asia on seuraava osoitin, jonka avulla voimme työskennellä luettelon läpi.

Linkitetyn luettelon luominen

Nyt meidän on luotava luettelo, joka todella on vain ensimmäisen solmun luominen. Joten määrittelemme sen, varaamme tarpeeksi muistia yhdelle solmulle ja asetamme seuraavan osoittimen arvoon NULL, jotta tiedämme, että tämä on luettelon loppu. Voit myös asettaa pääosoittimen siihen, koska linkitetty luettelo alkaa tästä.

Sitten voit täyttää tämän solmun tiedot: työntekijän nimi ja hänen kirjoitusnopeus.

Solmun lisääminen

Perusluettelomme avulla voimme nyt alkaa lisätä elementtejä luetteloon. Oletetaan siis, että aloitit Karenilla, jolla on kirjoitusnopeus 58 sanaa minuutissa. Seuraavaksi haluat kirjoittaa Steven nopeudella 63. Luodaan hänelle solmu ja täytetään tiedot. Sitten etsit linkitetystä luettelosta, mutta tässä tapauksessa olisi vain yksi elementti. Huomaa, että Stevellä on nopeampi kirjoitusnopeus, joten asetat hänen seuraavan osoittimen Karenin osoittimeen. Koska Karenin osoitin on myös päänosoitin, sinun pitäisi osoittaa pääkohta Steven solmuun.

Nyt sinulla on linkitetty luettelo, joka alkaa Steven solmulla. Seuraava osoittaa Karenin solmulle. Ja Karenin solmu osoittaa kohtaan NULL osoittaen, että hänen solmu on luettelon viimeinen.

Jos työntekijä palkataan kirjoitusnopeudella Karenin ja Steven välille, heille luodaan solmu. Mutta sitten Steven seuraava osoittaisi uutta työntekijää, ja uuden työntekijän seuraava osoittaisi Karenin.

Toisaalta, jos työntekijä palkataan kirjoitusnopeudella, joka on pienempi kuin Karenin, heille luodaan jälleen solmu. Mutta silloin Karenin seuraava osoittaisi uutta työntekijää, ja uuden työntekijän seuraava osoittaisi NULL: iin.

Solmun poistaminen

Solmun poistaminen linkitetystä luettelosta on itse asiassa melko helppo prosessi. Haluamme tehdä seuraavan työntekijän osoittimen ennen työntekijää, jonka haluamme poistaa, osoittamalla työntekijälle osoitetta poistettavan työntekijän jälkeen. Vapauttaisimme sitten poistetun solmun muistin tai päätyisimme muistivuotoon.

Linkitetyillä luetteloilla on tietenkin paljon muuta. Jos olet kiinnostunut tutkimaan linkitettyjä luetteloita edelleen, tutustu alla korostettuihin resursseihin.

Linkitetyt luetteloresurssit

Kun olet ymmärtänyt linkitettyjen luetteloiden peruskäsitteen, on aika kasvattaa tietosi. Alla tarjoamme muutamia lisäresursseja linkitettyjen luetteloiden todelliseksi hallitsemiseksi ja tietorakenteiden ymmärtämisen syventämiseksi:

  • Tietorakenteet ja algoritmit, jotka on tehty helpoksi (2016), kirjoittanut Narasimha Karumanchi: loistava kirja tietorakenteista, joka vie sinut paljon linkitettyjen luetteloiden ulkopuolelle.
  • Linkitettyjen luetteloiden perusteet (PDF): Tämä 26-sivinen PDF tarjoaa sinulle kaiken, mitä haluat koskaan tietää pseudokoodin ja C-kielen esimerkkien avulla..
  • Hieno kuvaus tietorakenteista: Tämä yksinkertainen johdanto vie sinut kokonaan luomalla ensimmäisen linkitetyn luettelon ohjelman.
  • Linkitetyn luettelon oppaat: Tämä on kokoelma 7 lyhyttä videota linkitettyjen luetteloiden luomisesta C: ssä++.
  • Opi-C.org linkitettyjen luetteloiden sivu: tämä sivu opastaa sinua luomaan yksinkertaisen C-kielellä linkitetyn luettelon.
  • Tietorakenteet Javascriptin avulla: opi linkitetyt luettelot selaimesi sisällä tällä JavaScript-opetusohjelmalla.

Yhteenveto

Yhdistetyt luettelot tarjoavat loistavan konseptin ja käytännöllisen tavan hallita ja luoda dynaamisia tietojoukkoja. Toivottavasti yllä olevat tiedot ovat auttaneet sinua ymmärtämään ja toteuttamaan linkitetyn perusluettelon, ja siirryt eteenpäin sieltä.

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map