Kapcsolódó lista oktatóanyaga: – A dinamikus adattárolás megkezdése

Közzététel: Támogatása segít fenntartani a webhely működését! Az ezen az oldalon javasolt szolgáltatások némelyikén referenciadíjat keresünk.


A kapcsolt listák értékes eszköz lehetnek, amikor különféle adatkészleteket kell felépíteni és a programhoz lineáris információkat kell szervezni. Általában egy tömb pótlására használják, mert bizonyos előnyeik vannak a használatukhoz.

A kapcsolt lista lényege egy egyszerű adatszerkezet, amely csomópontok sorozatát tartalmazza. Minden csomópontnak megvannak a saját adatai, plusz egy mutató egy másik csomóponthoz. Valójában gyakran tanítják őket annak érdekében, hogy a hallgatók kényelmesebbé tegyék a mutatókat.

Az alábbiakban megtudhatja, mi a hivatkozott listák, miért értékesek, és hogyan lehet azokat létrehozni. Néhány további forrást kínálunk az oktatás továbbfejlesztéséhez.

Mik a kapcsolt listák??

Egyszerűen fogalmazva: a csatolt lista rendezett adatgyűjtemény. Lineáris adatszerkezetekre készült, és az egyik legkönnyebben megvalósítható dinamikus adatszerkezet. Minden adatelemet csomópontnak hívnak, és egyetlen értéket és mutatót tartalmaz a lista következő csomópontjához. Ha a mutató NULL értéke van, akkor a csomópont az utolsó a listában.

A koncepció megértésének érdekében a számítógépes technológián kívüli példa a következő:

Tegyük fel, hogy az irodában mindenkit a gépelési sebesség alapján értékel. A listád Annnal kezdődik, mert mindenki tudja, hogy ő a leggyorsabb – hallani tudja a hangfülkéjéből származó hangot. Azt mondták neki, hogy a következő leggyorsabb ember Steve. Steve tudja, hogy gépelési sebessége közel áll Annához, de nem annyira jó. Azt is tudja, hogy Karen majdnem olyan gyors, mint ő, de nem egészen annyira. A lista ezt követően folytathatja. Minden tag egyedi információval rendelkezik, valamint egy mutatóval arról, hogy ki a következő leggyorsabb gépíró.

Mivel a csomópontok léteznek egymástól függetlenül, kivéve a mutató viszonyt, nagyon egyszerű őket hozzáadni, törölni és áthelyezni.

Kapcsolódó listák típusai

Néhány különféle típusú kapcsolt lista létezik. Egyetlen kapcsolt lista, kétszeresen összekapcsolt lista, többszörözött lista és körkörösen csatolt lista. Az alábbiakban részletesebben vizsgáljuk meg őket. A csatolt listákkal beillesztési, törlési és átjárási műveleteket hajthat végre.

1. Egységesített lista

Az egyetlen csatolt lista olyan adatobjektumok gyűjteménye, amelyeket bizonyos referenciák kapcsolnak össze az egyik objektumról a másikra. Ezeket az objektumokat gyakran csomópontoknak nevezik. Minden csomópont tartalmaz legalább egy adatmezőt és hivatkozást a következő csomópontra. Az összekapcsolt listák az első csomóponton keresztül érhetők el, és a lista végéig átjárhatók.

2. Kettős csatolt lista

A duplán összekapcsolt listákonként két-egy referencia található. A referenciák a következő csomópont és az előző csomópont felé mutatnak. Ezzel a struktúrával kétirányú hozzáféréssel rendelkezik az adatkészlethez, és ez nagyobb rugalmasságot és gyorsaságot kínál, mivel mindkét irányban navigálhat a listán..

3. Összekapcsolt lista

Az összekapcsolt listák általában összekapcsolt listák, amelyek egy adott csomópontból több további listát tartalmaznak. Az új listák bármelyik stílusban szerepelhetnek. Ez a listastílus hasznos lehet a felhasználói név és életkor szerint lebontott lista rendezésében. Vagy más adatkészlet-stílusok, ahol az egyes adatpontok további osztályozással rendelkeznek.

4. Körben kapcsolt lista

A kapcsolt lista végleges típusát körkörösen csatolt listának nevezzük. Ahelyett, hogy a végső csomópont NULL-paranccsal rendelkezne, a lista fejére hivatkozik. A lista felépítése hasonló a fenti lehetőségekhez.

Miért fontos a kapcsolt listák?

Az összekapcsolt listák dinamikus jellegük miatt hasznosak. Számítástechnikai szempontból csak akkor tárol memóriát, ha szükséges. Tehát, ha van egy olyan alkalmazás, amely gyakran átméretezést, törléseket, beillesztéseket és adatfrissítéseket igényel, akkor a csatolt lista tökéletes.

A kapcsolt listákat általában grafikonok, halmok, sorok és más hasonló programok végrehajtására használják. Egy összekapcsolt listával bármilyen elemet beszúrhat a listába. Ráadásul nem kell előre tudnia a végleges lista méretét. Növeli vagy csökkentheti a méretet, ahogy te látja.

A könnyebb beillesztés és törlés a linkelt listák fő előnye. Használhat például egy tömböt, de a tömbök csak akkor adhatják hozzá és távolíthatják el a sorozat utolsó objektumát, anélkül, hogy egy csomó adatot mozgatna egy nyitott nyílás létrehozásához. Az összekapcsolt listák lehetővé teszik az egyszerű szekvenciális manipulációt anélkül, hogy a memória erőforrásainak jelentős terhet jelentenének.

A legtöbb számítástechnikai program továbbra is tanítja a hallgatókat a hivatkozott listák végrehajtásáról, mivel ez egy bevezetés a dinamikus adatszerkezetekbe, amelyeket érdemes lehet a valódi programokban használni. Ráadásul, még ha soha nem is használ összekapcsolt listát, akkor elegendő megértést biztosít a mutatók használatához. Bizonyára sok mutatót használ a valós programokban.

Kapcsolt lista hátrányai

A kapcsolt listák kiválóan alkalmasak a könnyen módosítható listák létrehozására. Ugyanakkor ezek nem minden program tökéletes megoldása, amint azt alább láthatja:

  1. A kapcsolt listák nem kínálnak véletlen hozzáférési pontot. Annak érdekében, hogy egy bizonyos elemet elérjék a listán, a lista minden elemére el kell végezni, addig a pontig.
  2. A kód kissé bonyolulttá válhat, mivel a kód működéséhez mind a dinamikus memóriaelosztás, mind a mutatók szükségesek.
  3. A kapcsolt listák összterhelése nagyobb lehet, mint egy tömb, mivel a listákat dinamikusan osztják el.

Mindemellett, a linkelt listák használatának ismerete segít megtanulni a mutatók használatát, és jobban megérti a dinamikus adatkészletek egészét.

Kapcsolódó listák bemutatója

Az alábbiakban megtudhatja, hogyan hozhat létre és valósíthat meg egy alapvető linkelt listát. Egy összekapcsolt lista és annak csomópontjainak létrehozásával kezdjük, és megmutatjuk, hogyan kell törölni és beilleszteni az új csomópontokat.

Csomópont-struktúra létrehozása

A csatolt lista több csomópontból áll, így létre kell hoznunk egy csomópontot meghatározó struktúrát. Ennek tartalmaznia kell legalább egy változót az adatokhoz és egy mutatót a következő csomóponthoz való hivatkozáshoz. Célunkra ragaszkodni fogunk a gépelési sebesség példájához, és felhasználjuk a személy nevét és sebességét, valamint adatainkat. A C pontban az adatokat a következőképpen definiálják egy struktúrában:

struct node {
karakterlánc neve [32];
int sebesség;
struct node * következő;
}

Itt fontos a következő mutató, amely lehetővé teszi számunkra, hogy végiggondoljuk a listát.

Kapcsolt lista létrehozása

Most létre kell hoznunk egy listát, amely valójában csak az első csomópont létrehozása. Tehát definiáljuk, elegendő memóriát rendelünk egyetlen csomóponthoz, és a következő mutatót NULL-re állítjuk, hogy tudjuk, hogy ez a lista vége. A fejmutatót arra is beállítja, mert itt indul a csatolt lista.

Ezután kitölti a csomópont adatait: a munkavállaló nevét és gépelési sebességét.

Csomópont beillesztése

Az alaplistánk elkészítésével megkezdhetjük az elemek hozzáadását a listához. Tehát tegyük fel, hogy Karennel kezdte, aki gépelési sebessége 58 szó / perc. Ezután Steve-be akar lépni 63-as sebességgel. Létrehozna egy csomópontot neki, és kitölti az adatokat. Akkor keresse meg a csatolt listát, de ebben az esetben csak egy elem lenne. Megjegyezzük, hogy Steve gyorsabb gépelési sebességgel rendelkezik, tehát a következő mutatót Karen mutatóra állítja. Mivel Karen mutatója egyben a fej mutatója, mutatnod kell a fejet Steve csomópontjára.

Most már van a csatolt lista, amely Steve csomópontjával kezdődik. Ez a következő Karen csomópontjára mutat. És Karen csomópontja a NULL-ra mutat, jelezve, hogy csomópontja az utolsó a listában.

Ha egy alkalmazottat gépelési sebességgel alkalmaznának Karen és Steve között, akkor csomópont jön létre számukra. De akkor Steve legközelebbi az új alkalmazottra mutat, és az új alkalmazottja Karenre mutat.

Másrészt, ha egy alkalmazottat Karennél alacsonyabb gépelési sebességgel alkalmaznának, akkor ismét csomópont jön létre számukra. De akkor Karen következője az új alkalmazottra mutat, az új alkalmazottja pedig a NULL-ra mutat.

Csomópont törlése

Egy csomópont törlése egy összekapcsolt listából valójában meglehetősen egyszerű folyamat. A törölni kívánt munkavállaló előtt a munkavállaló következő mutatóját a törölni kívánt munkavállaló utáni mutatóra mutatjuk. Ekkor elengedjük a törölt csomópont memóriáját, vagy memóriaszivárgás következne be.

Természetesen sokkal többet tehet a linkelt listákkal. Ha érdekli a linkelt listák további tanulmányozása, akkor nézd meg az alább kiemelt erőforrásokat.

Kapcsolt lista forrásai

Miután megértette a hivatkozott listák alapfogalmát, ideje bővíteni tudását. Az alábbiakban néhány további forrást kínálunk a hivatkozott listák valódi elsajátításához és az adatszerkezetek mélyebb megértéséhez:

  • Adatstruktúrák és algoritmusok, Made Easy (2016), készítette Narasimha Karumanchi: egy nagyszerű könyv az adatszerkezetekről, amely messze túlmutat a linkelt listákon.
  • Kapcsolódó listák alapjai (PDF): ez a 26 oldalas PDF szinte mindent tartalmaz, amit valaha is szeretne tudni, ál álkóddal és C nyelvű példákkal.
  • Gyengéd bevezetés az adatszerkezetekbe: ez az egyszerű bevezetés végigvezeti Önt az első csatolt listaprogram létrehozásában.
  • Linked List oktatóprogramok: ez a 7 rövid videó gyűjteménye a linkelt listák létrehozásáról a C-ban++.
  • Learn-C.org Kapcsolódó listák oldala: ezen az oldalon bemutathatja egy egyszerű, C-nyelvhez csatolt lista létrehozását.
  • Adatszerkezetek Javascript használatával: Tanulja meg a hivatkozott listákat közvetlenül a böngészőjében ezzel a JavaScript oktatóanyaggal.

összefoglalás

A kapcsolt listák nagyszerű koncepciót és gyakorlati módszert kínálnak a dinamikus adatkészletek kezelésére és létrehozására. Remélhetőleg a fenti információk segítenek megérteni és végrehajtani az alapvető hivatkozott listát, és továbblépnek innen.

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me