Lineáris kétirányú listák
1.1. Meghatározása a kétirányú lista
A dinamikus lista, amelyben minden egyes elem (kivéve az első és az utolsó lehetséges) kapcsolódik az előző és a következő elem az úgynevezett kétszeresen kapcsolt. Minden eleme ez a lista két mezőt mutató: az egyik mező egy hivatkozást a következő elem, egy másik területen - hivatkozás az előző tételt, és a harmadik mező - információkat. A jelenléte linkek a következő hivatkozás az előző, és lehetővé teszi, hogy mozoghat a listát minden kapcsolat mindkét irányban: a szinten, hogy a végén a listából vagy a link a lista elejére, így ez a lista is nevezik kétirányú.
1. ábra. BETA karaktersorozatot által képviselt kétszeresen láncolt lista
Az első link egy hivatkozást az előzőhöz, az utolsó láncszem nincs utalás a következő link-et (lásd. Ábra. 2.).
2. ábra. BETA karaktersorozatot képviselő cirkuláris listán
Egy ilyen listát (lásd. Ábra. 2.) nevezett gyűrű alakú (körkörös). Itt az első link egy link az utolsó, az utolsó link az első. Ezért kezdődik feldolgozása egy ilyen lista, mint akkor az első link, és az utóbbival. Kétszeresen láncolt lista lehet egy címet egység (lásd. 3. ábra).
3. ábra. A cím linket kétszeresen láncolt lista
A cím link segítségével feldolgozza az első és az utolsó egységek, valamint a többiek.
Vannak más kétszeresen láncolt lista szerkezete.
Feladat kétszeresen láncolt lista:
list2 mellett * * pred;>
Itt írja - az információ típusa mező listaelemet. Headlist2 pointer változó a lista azokat egyetlen szoftver objektum, annak értéke - egy mutatót az első (vagy cím) elemet a lista (lásd 3. ábra ..).
2. példa A továbbiakban egy kétirányú gyűrű lista
list2 mellett * * pred;>
l -> következő = l; // gyűrű listája
l -> pred = l; // egy felső lengőkar
míg a ((sym = getchar ())! = '\ n')
x -> ELEM = sym; // Létrehozunk a következő szintre
x -> következő = r -> következő; // mező mellett - mutatót a következő hivatkozás
// A mutatót az első lista a linket
x -> pred = R; // mező pred - az előző link mutató kapott
// mutató az aktuális listáját a legújabb linkek
R -> következő = x; // mező mellett ezt az utolsó tétel - egy pointert
// következő elem, hogy egy mutató egy új értéket
// elem tehát új linket adunk a vége
R -> következő -> pred = x; // Field pred title elem - Pointer
// az utolsó láncszem a listát kapott mutató értéke
// adunk a végén egy lista elem, így
// képződött cirkuláris listán
// Aktuális Index volt a referenciaérték
// új utolsó tétel a listán
Fő végrehajtott műveletek a kétszeresen láncolt lista, ugyanaz, mint a láncolt lista. Tehát, mint egy kétszeresen láncolt lista rugalmasabb, mint egyszerűen csatlakoztatható, amikor a tételt a listában, akkor az index egy elem, amelynek van egy kapcsoló, és egy mutatót, egy elem, amely előtt van egy felvétel. Ha kizárja egy elemet a listából lehet használni, mint egy mutató önmagában negatív elemet és egy mutatót az elem előző vagy a következő érettségiző. De mint egy elemének kétszeresen láncolt lista két mutató, majd ha a kapcsolási művelet / kizárási elemet cserélni kell további linkek mint egy láncolt lista.
Keresés az elem egy kétszeresen láncolt lista végezhetjük:
a) szkennerekben elejétől a végéig a listán,
b) szkennelés elemek végétől a listát, hogy a felső,
c) a listában mindkét irányban egyidejűleg az elejétől a közepén a listán, és a végén, hogy a közepén a (figyelembe véve, hogy a terméket a listából lehet páros vagy páratlan szám).
3. példa: Töredékek programok különböző műveletek a kétszeresen láncolt lista:
// a lista nélkül címlinkre
ha (p = = NULL) visszatérési;
// p nem egyenlő a jel a lista tetején - ph
// egy listát a címlinkre
ha (p -> következő = = p) visszatérési;
pr = p -> pred; // Az aktuális mutató pr kapott referenciaértéket
// az utolsó elem a lista
// nem egyenlő az index címlinkre lista - p
X = az új list2; // engedélyezése az új elem (a listán
x -> pred = p -> pred; // nagybetűs link) előtt az elemet a
x -> következő = p; // hivatkozott p
p -> pred -> következő = x;
p -> pred -> következő = p -> következő; // eltávolítása a listából a cím
p -> következő -> pred = p -> pred; // link elem, amelyre
törölni p; // utal mutató p