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ó.


Az alapvető adatstruktúra


OpenCV: HSV és keressük objektumok színe


OpenCV: Keresés rögzített objektumok SURF és Flann


OpenCV: Telepítés és használat Windows alatt


OpenCV: Telepítés és használat Linux alatt


Qt Script: Bevezetés


XLib: tájékozódásra ablakok Linux


QNetworkAccessManager: Egyszerű POST-lekérdezések Qt

Kapcsolódó cikkek