A végrehajtás egy láncolt lista a tömbök alapján
A végrehajtás egy láncolt lista a tömbök alapján
Churikov Konstantin, Donbass Állami Műszaki Egyetem
Meghatározása lineáris listák
List nevű rendezett halmaza, amely változó számú elemet, amelyek alkalmazhatóak a záró művelet, kivétel. List közötti összefüggést bemutató elemei a környéken nevezik lineáris.
A következő műveletek végezhetők végrehajtására lineáris listák imperatív programozási nyelvek:
való hozzáférés egy elem lista ellenőrzésére és / vagy a változó tartalmát a területen;
egy új elemet közvetlenül megelőző vagy azt követő egy tetszőleges eleme;
törlése egy tetszőleges elemet;
szövetség listáját két (vagy több) lineáris listák;
hasító lineáris listáját két (vagy több) a lista;
másolatot lineáris listát;
meghatározzuk az elemek száma a listán;
rendezési listát tételek;
elemeket keresni egy előre meghatározott értéket.
Az egyik programban ritkán kell használni mind a kilenc típusú műveleteket. Ugyanakkor elég nehéz létrehozni egy egységes végrehajtását lineáris listákat, amelyek hatékonyan elvégezni ezeket a műveleteket. Ezért lineáris listákat lehet végrehajtani függően eltérő osztályba ügyletek, amelyek a leginkább gyakran őket tenni a programot, vagy a legkritikusabb a végrehajtási időt.
A belső reprezentációja lineáris listák
Alapvető való tárolására szolgáló módszereket lineáris listák a számítógép memóriájában osztható szekvenciális eljárások és a kapcsolódó tároló. A szekvenciális listáját tároló elemek elrendezve egymást követő sejtekben a memóriában, egy elem közvetlenül követi a másik. Tárolására szolgáló egy rugalmasabb rendszer, ahol minden egyes eleme a lista tartalmaz egy linket a következő elem, valamint egymáshoz viszonyított helyzetét a memóriában lehet önkényes. Mindegyik módszernek megvannak a maga előnyei és hátrányai. Amikor kiválasztod a tárolási módszer egy adott programban figyelembe kell venni minden olyan művelet, és milyen intenzitással telne lineáris lista, a végrehajtás költségét és az összeget a tárolásához szükséges memória a listán.
Ez a megvalósítás nem nagyon ritkán fordulnak elő. Egyszerűen, gyakran mögött a különböző nevek - index tömbök, tömbök megfelelőségi stb Annak ellenére, hogy a különbség a nevek, ugyanazt az algoritmust. - Szerk.
A végrehajtás egy láncolt lista a tömbök alapján
Tekintsük ezt a módszert a kiviteli alak egy lineáris láncolt lista. Ennek elemei listában lineárisan rendezett. Amellett, hogy az elemek a listán van egy navigátor, amely lehet a következő pozíciókban:
a felső (azaz, mielőtt az első eleme a lista);
végén a listán (vagyis az utolsó elem a lista);
elemei között a listán.
Navigator lehet mozgatni csak az elejétől a végéig a lista egy tétel egy időben. Ezen túlmenően, add lista tételek csak abban a helyzetben, arra utal, hogy a navigátor. A változás / törölni / olvasni csak azokat az elemeket, amelyek abban a helyzetben vannak, mielőtt az egy említett a navigátor, azaz upstream annak mozgását.
A fő gondolata ezért ez külön információt tartalmát tételek listáját információt a sorrendben. Grafikusan, ez a gondolat 1. ábrán mutatjuk be.
További referenciák fogja képviselni a nyilak, ahogy a 2. ábrán látható.
Természetesen ahhoz, hogy a munka egy listát csak a kapcsolatokat az elemek nem elég - meg kell tudni, például, ha az első elem a listában, mely az utolsó elemet a többiek (sőt van olyan elemét sem). Ezekre a célokra, tudtuk bemutatni a két változó, amely tartalmazza az indexek indul és a lista végére. Mi azonban nem ezt, és használja a fogadását „gördülő gyűrű” - „visszafordulni” lista megadásával különleges képzeletbeli NULL elemet, ami mindig kell helyezni indexű elem NullElem (amelynek értéke 0) a tömb tárolására használt hivatkozás lista elemeinek (úgynevezett hivatkozásban). A 3. ábra grafikusan mutatja be a modell.
Üres lista megfelel a helyzet, amikor a gyűrű bármely más elemet NullElem, nem, hogy van, cellarendszer hivatkozási index NullElem utal magát.
Navigator között található elemek, így eladni formájában két változó ELŐTT és UTÁN, UTÁN, amely tartalmazza az index a telt el, és ELŐTT - az index még nem telt elem. Rendelet Navigator a tetején, így megfelel egy esetet, amikor egyenlő UTÁN NullElem, és a véghelyzet - ha az érték szereplő ELŐTT.
Most, egy láncolt lista szimulálják teljesen. Továbbra sem tisztázott, csak a következő kérdéseket:
Hogyan állapítható meg, a jelenléte vagy hiánya a tér a tömb elemeinek (úgynevezett Elems)?
Hogyan talál szabad elemet a tömb elemeinek a szimuláció hozzáad egy elemet a listán?
Nem tudhatjuk, mit példány Elems ingyenes, és amelyek vannak elfoglalva, hogy a döntést, folyamatosan amellett, hogy a lista elemeit alkalmazzuk a szabad listán. Az elemek a lista is kapcsolódik egy gyűrűben, kezdve a szolgáltatási elem tárolt indexű elem NullFreeSpace (egyenlő egy) egy sor hivatkozások (hivatkozásban). Grafikus ábrázolása a kapott modell a 4. ábrán látható.
Így annak megállapítására, hogy van egy szabad hely listán, akkor meg kell vizsgálni az értéke Refs elem (NullFreeSpace). Ha ez az érték NullFreeSpace (azaz saját magára mutat), a szabad hely van. Egyébként ez az érték pont az első szabad eleme a tömb elemeit. Ha hozzáad egy elemet a listából a kizárni kívánt index ennek az elemnek a szabad listán, és tartalmazza azt a fő listán. Ha töröl egy elemet, akkor kell, hogy a fordított műveletet.
4. ábra fekete jelölt vélelmezett egy láncolt lista, és piros - a rendelkezésre álló elemeket.
Egy szoftveres megvalósítása, a lista megbízás referencia index értékek virtualIndex realIndex elérhető egy külön rutin. Ezen túlmenően, az egyes rutinok kiosztani az összes kapcsolódó műveletek működését a szabad hely.
Az összes fent említett megjegyzések végrehajtása egyszerűen csatlakoztatható lineáris listát Visual Basic 6.0 alakja lehet, az alábbiak szerint.