Egyszeresen láncolt lista a c - emlékeztet
A szabványos C ++ könyvtár tartalmaz egy csomó alapvető adatszerkezeteket. Között, amely megtalálható listák, vermek, sorok, készletek és mások. De ahhoz, hogy hatékonyan használják őket, akkor egy jó megértése sajátosságai munkájukat. A kérdés körül lesz az egyik alapvető struktúrák: láncolt lista.
Egyszeres kapcsolt listák elméletben
Ahhoz, hogy megértsük, hogyan kell megépíteni egy láncolt lista, elképzelni egy lánc. A láncban van eleje és vége, valamint a kapcsolatokat, amelyek szekvenciálisan kapcsolódnak egymáshoz. Könnyen megy az elejétől a végéig egy lánc, halad egymás egyik link másik:
Ez egyszerűen csatlakoztatható és munkalistákat. A lista tetején az úgynevezett a szülő elem, és linkek - csomópontok. A lista határozza meg egy speciális csomópont (NULL). Így minden egyes csomópont „tegye le” azt jelenti, hogy a szerkezet, hogy hasznos lehet:
Előnye láncolt lista, hogy a behelyezése és eltávolítása a csomópontok viszonylag könnyen végzett bárhol a listán. Ugyanakkor a szerkezet a lista korlátozza a hozzáférést a helyek az index. A lista nem indexelt tömbként. Ahhoz, hogy egy csomópont láncolt lista, akkor következetesen menjen végig a fejtől elemet a kívánt helyre.
osztály interface láncolt lista
Egyszeresen láncolt lista tárolására használatos rendezett halmaza azonos elemeket. Annak érdekében, hogy ne kell határozni minden egyes típusú adatok listáját, meghatározza az osztály sablon:
Mi osztály továbbra is fenntartja a láncolt lista csomópont hozzátéve, hogy az elején, törlésére az utolsó csomópont és a fogadó fejelemet értékeket. Ezen kívül, mi végre a bypass listát iterátorokat, valamint hozzá egy tag függvény kiszámításához a hossza a listán.
Csomópont Node segítségével határozzuk meg szerkezetét. hogy két mezőt tartalmaz: m_t - érték kötve egy csomópont, és m_next - mutató a következő csomópontot.
Kezdetben a lista üres, így a szülő elem pontot NULL:
Hozzáadása elemet a láncolt lista
Csomópont hozzáadása a linkelt lista végre az elején. Hozzáadott csomópont maga lesz az új vezetője eleme a lista:
Ha eltávolít egy elemet a láncolt lista
Ha eltávolít egy csomópontot a láncolt lista van csonkítva a szülő elem. Ha a lista még csomópontok, az új elem a szülő csomópont, miután a szülő elem, vagy NULL:
List dinamikus szerkezetét. Amikor új csomópont memóriát a kupac, hogy szabadon kell, hogy ne hozzon létre memóriavesztés. Amelynek az a funkciója kihordóelemek megvalósítani azt nem nehéz destructor láncolt lista:
Iterátor láncolt lista
Funkcionalitás hozzáadni / törölni csomópontokat a listában, hogy jobb nem összekeverni azzal a feladattal, megkerülését. Erre a célra vannak bejárók. Iterátor létre egy láncolt lista C ++ stílusban. Térjünk vissza a definíció, amely korábban hiányzott:
Mint bejáró az elején és a végén a lista a következő igaz:
Most a lista könnyen bejárható az elejétől a végéig. De ne feledkezzünk meg a függvény kiszámítására hosszát. Az általunk használt mechanizmusát iterátorokat, hogy egyszerűsítse a feladat:
következtetés
Megjegyezzük, hogy a fenti példa csak egy rövid bemutató elveinek láncolt listájának C ++. A valós programok szinte mindig jobb, hogy szabványos könyvtár végrehajtására a listát, és minden más adat struktúrát. Akkor nem csak akkor kell tennie kevesebb munka, de kapsz a rendelkezésére egy jól hangolt és optimalizált változata, amely képes lesz arra, hogy biztonságosan használható.