A láncolt lista - studopediya

előző ◈ a következő

Egy adatstruktúrában egy véges rendezett halmaza (csomópontok) kapcsolódnak egymáshoz által mutató, úgynevezett láncolt lista. Minden egyes elem egy láncolt lista tartalmaz egy adatmezőt, és egy mutatót (link) a következő és / vagy előző elem. Ez a szerkezet lehetővé teszi, hogy hatékonyan végrehajtani a műveletet a hozzáadása és eltávolítása a tételeket, bármilyen helyzetben a sorrendben. És ez nem igényel az átszervezés a szerkezet, amely szükséges lenne a tömbben. A hátránya a láncolt lista, valamint egyéb építmények, mint például a „listán”, szemben a tömb a hiánya képes dolgozni az adatok véletlenszerű hozzáférési módot, vagyis a lista - .. Egymást elérheti szerkezetét, míg a tömb - önkényes. Az utolsó hátránya csökkenti a hatékonyságát bizonyos műveleteket.

Minden egyes csomópont egyszerűen csatlakoztatva (egyirányú csatlakoztatva) a lista tartalmaz egy mutatót a következő csomópontot (ábra. 2.7). Egyetlen pont csak akkor kap a következő pont, így közelítve a végére. Így kapunk egyfajta áram az egyik irányba.

2.7 ábra - egyszeresen láncolt lista

Megismételni korábbi mondta. A kép minden egyes blokk képviseli az elem (csomópont) listán. Head lista - egy lista a fejléc elem (feltételezve, hogy a következő mezőbe neki). Nem tartalmaz adatokat, de csak egy hivatkozás a következő elem. A jelenléte adatokkal területén info. és linkek - következő mezőben (további hivatkozásokkal lesz felelős, és előző mező). A jel hiánya a mutató nulla területen.

Egyszeresen láncolt lista nem a legkényelmesebb típusát láncolt lista, azaz a. A. Az egyik pont csak akkor érhető el a következő pontot, így közelítve a végére. Ha csak a mutatót a következő elem egy mutató az előző, akkor ez a lista nevű kétszeresen kapcsolódik.

2.8 ábra - kétszeresen láncolt lista

A képesség, hogy mozogni előre és hátra hasznos bizonyos műveleteket, de a további jelek használatát igénylő több memóriát, mint ami szükséges a kapcsolt listában.

Amikor a memória mennyiségét bármilyen okból korlátozott, akkor az alternatív, hogy a kétszeresen láncolt lista szolgálhat az XOR-láncolt lista (ábra. 2.9). Az utóbbi használja a logikai műveletet XOR (kizáró „vagy” szigorú szétválasztás), amely a két változó értéke true, ha ez igaz, csak az egyikük, és a második, illetve hamis. Az igazság táblázat műveleteket:

2.9 ábra - XOR-láncolt lista

Egy másik típusú láncolt lista - a lista a gyűrű. A kör alakú láncolt lista az utolsó elem utal az első. Abban az esetben, egy kétszeresen összekapcsolt cirkuláris listán, valamint az első elem utal az utóbbi (ábra. 2.10). Így egy szerkezetet fixated.

2.10 ábra - Ring láncolt lista

Tekintsük az alapműveleteket kapcsolt listák.

A kétszeresen láncolt lista Például, mi magyarázza a működési elve az adatok szerkezetét. Végrehajtásakor a listát hasznos szerkezetek (Pascal - felvétel).

Az általános formája a csomópont leírása kétirányú láncolt lista, és egy mutatót az első eleme a lista:

információs mező értéke 1;

információs mező 2;

információs mező N;

egy mutatót a következő elemre;

mutató az előző elem;

struct DoubleList // node lista leírása

int adatok // információs mező

DoubleList mellett *; // mutató a következő elemre

DoubleList * dok; // mutató az előző elem

DoubleList * fej // mutató az első elemre a lista

Nos, feltételezve, hogy a leírt összeszerelés és a mutatót a fejét a listán (lásd. A fenti példában), tudjuk írni a lehetőségek listáját.

void AddList (int értéket, int pozíció)

DoubleList * node = new DoubleList; // Létrehozunk egy új bejegyzést

nyirokcsomó> adatok = érték; // hozzárendelése elem értékeit

if (fej == NULL) // ha a lista üres

nyirokcsomó> következő = csomópont; // állítsa a következő mutató

nyirokcsomó> Prev = csomópont; // állítsa előző mutató

fej = csomópont; // A lista élére kerül meghatározásra

A (int i = helyzetben; i> 1; én--) p = p-> következő;

nyirokcsomó> következő = p; // hozzáad egy elem

cout<<"\nЭлемент добавлен. \n\n";

int DeleteList (int pozíció)

if (fej == fej-> következő) // ha ez az utolsó tétel a listán

törölni fej // elem törléséhez

A (int i = helyzetben; i> 1; én--) a = a-> következő;

ha (a == fej) fej = a-> következő;

a-> prev-> következő = a-> következő; // elem törléséhez

cout<<"\nЭлемент удален. \n\n";

Ha a lista üres, akkor az üzenet tájékoztatja erről, és akkor a függvény a hívónak.

PrintList funkció megjeleníti az összes elemet a lista:

ha (fej == NULL) cout<<"Список пуст\n";

cout<<"\nЭлементы списка: ";

A lista nyomtatásához és ezen keresztül a ciklus, vagyis iteratív. Most egyesíti a három funkció egy programban, és írjon a fő funkciója, felelős hívó alprogram: