Sor-alapú tömbök
Most nézzük meg a végrehajtás szakaszában tömbalapú. Mint korábban, az egyszerűség kedvéért használja egy sor TList. Legalábbis ebben az esetben nem kell aggódnia a memória kiosztás és méretének növelése a tömbben.
Tudván, hogy hogyan hajtsák végre alapuló kapcsolt listán, az első vágy lehet szimulálni a műveletek sorba állítását, tételeket végén például TList tömb módszer hozzáadása és szimulálni eltávolítását a vonal -, hogy távolítsa el az első elemet módszerrel törlése módszer ( vagy fordítva, behelyezve az elején a tömb, és távolítsa el a végén). Mindazonáltal, lássuk, mi fog történni, ugyanakkor egy sor. Amikor az Add módszerrel nem történik semmi érdekes, kivéve, ha szükség van, hogy növelje a méret a tömb. Ez a művelet osztály O (l) - csak mire van szükség. Ami a Törlés, itt minden nem ennyire rózsás. Az a művelet végrehajtását, hogy távolítsa el a vonal a tömb TList kell távolítani az első eleme, amely elvezet a tény, hogy minden elem a tömb továbbléphetünk egy pozíciót. Egy ilyen művelet függ az elemek száma a tömbben, azaz Ez osztályhoz tartozik, 0 (n). Így vártunk rossz hír. Nem tudjuk megváltoztatni a kimutatás műveletek helyeken a sorban, és de-sorban, vagyis Mi hozzá csak a lista tetején, és távolítsa el a végén. Más szóval, még mindig kap egy osztály működését 0 (n), ha hozzáadjuk a lista tetején.
Egyes források szerint az elv még ma is használják, hogy hajtsák végre a sorban. Sőt, TQUEUE osztály Contnrs modul, esetleg ezen az elven alapulnak.
3.10. Ábra Használata egy sor sorbanállási
Hogyan kell végrehajtani egy sor minden az alapon, hogy a két alapvető műveleteket osztályába tartoznak 0 (1)?
A megoldás az, hogy egy kör alakú sorban. Képzeljünk el egy fogadáson a fogorvos. Általános szabály, hogy egy szoba székek, a falak mentén. Ezzel szemben a vonal a szupermarketben, ha jössz, hogy a tetején a sorban, rámenős egy kocsit, a recepciós akkor ül egy széken. Amikor felhívja a következő beteg a többiek ne álljon fel, és ne lépjen tovább a következő székre. Csak első a sorban - néhány nehéz megmagyarázható tulajdonság (igen, az a benyomás, hogy Amerikában nincs sorban a fogorvoshoz.) - kerül át egy másik személynek. Amikor hívja ezt az attribútumot a beteget át a következő beteg, és ez lesz a „kezdet” a sor. Így senki sem kap a székéből, csak valamilyen módon (talán a segítségével fogászati asszisztens), az első beteg a sorban meghatározzuk. Ez a fajta szervezet hívják körkörös sorban.
Megvalósítása körmérkőzéses tömbalapú mutatunk be egy változó, amely tartalmazni fogja az index az első elem a sorban. Ezen kívül bemutatjuk egy másik változót, amely pont a végén a sorban. Kezdjük néhány a tömb egy bizonyos számú elemet (mérete alapján kell a maximális lehetséges számát elemek a sorban), és létre egy kezdeti elem indexet egyenlő az index a végső elem. Tény, hogy ez az egyenlet azt jelenti, hogy a sor üres.
Queuing elem egyenérték állítóelem, ami azt jelzi, a végén a sorban index egyenlő a rögzített érték az elem sorban. Ezt követően, az a sor végére index értéke kell növelni 1. Ha a növekedés az index meg fogja haladni a tömb méretét, be kell állítani, hogy 0; az index az első cella egységet.
Eltávolítása elemet a sorból: a visszatérési értéke az elem által mutatott az index a sorban. Ezt követően, az érték a startvonalon index növekszik 1. Ha meg fogja haladni a méret a tömb után a növekedés az index, akkor állítsd 0. Nyilvánvaló, hogy eltávolítása előtt egy elemet a sorból, akkor biztosítani kell, hogy a sor nem üres. Ehhez ellenőrizze, hogy az indexek kezdete és vége a sorban egyenlő (abban az esetben, részvényindex, a sor üres).
És ez még vizsgálni egy másik probléma: ha a beállítás a sorban álló tételeket, győződjön meg arról, hogy az új érték a végén a sorban index nem egyenlő az érték a sorban index. Ha egyenlőség figyelhető meg, ez azt jelenti, hogy az összes elem teljesen fel van töltve. Sajnos, ez a helyzet azt is jelenti (legalábbis eltávolítására eljárások queue), hogy a sor üres. Így, ha egy ilyen elég abszurd helyzet áll elő - üres sorban töltött egyenértékű - növelni kell az a tömb méretét, mozgatásával az összes elemet a tömb és a változó értékei az indexek kezdete és vége a sorban.
Class TtdArrayQueue interfész ugyanúgy néz ki, mint a felület TtdQueue osztályban.
Listing 3.31. osztály TtdArrayQueue
A konstruktor és destruktor nem sokban különbözik a megfelelő módszerek TtdArrayStack osztályban.
Listing 3.32. A konstruktor és destruktor TtdArrayQueue
A legérdekesebb dolog történik módszerek Enqueue és Dequeue.
Listing 3.33. Enqueue és Dequeue módszerek osztály TtdArrayQueue
Mint látható, egy elem a sorban eltávolítása elemet tartalmaz a visszatérés, amely az index helyzetben a sorban, majd növelje az index 1 Sorba a rögzítési elemmel index helyzetben a végén a sorban, és a növekedés az index által 1. Ha a sor végére ér a kezdési , a tömb méretét növeljük módszerrel aqGrow:
Listing 3.34. Bővítése a méret a példány TtdArrayQueue
A fenti módszer a legbonyolultabb módszer az egész osztály. Amikor ez az úgynevezett sor megtelt, a végén a sorban index megegyezik az index a kezdet (ne felejtsük el, hogy ez azt is jelenti, hogy a várólista üres), hogy növelni kell a méret a tömb TList. Az első dolog, amit - növelje a tömb méretét 50% -kal. Ezután az összes szükséges rögzíteni a gyűrűt úgy, hogy kellően figyelembe veszi a rendelkezésre álló helyet. Ha az index értéke a sorban 0, a gyűrű vonal nem kör alakú, és csak annyit kell tennie, hogy - a változó értéke az a sor végére index. Ha az index értéke nem egyenlő 0-Start, a sorban volt „végtelenített” belül a tömb. , Mozgassa a tetején a tömb, és menj a végén a sorban index (mely megegyezik az index a várakozási sor), hogy végighaladhat az elemeket a megfelelő sorrendben, kezdjük a indexe a sorban, elérjük a végén a régi tömb. Most további elemek, melyek között található a régi és az új tömb végéhez. Ezért kell, hogy az elemek között található a rajtvonalon, és a régi végén a tömb, hogy azok előtt került sor az új tömb végéhez. Ezután megkapjuk a megfelelő sorrendben az elemek a kör alakú sorban.
Teljes osztály TtdArrayQueue kód megtalálható a web-oldalon a kiadó, az anyagi részt. Ezután a terhelést anyag keresni köztük TDStkQue.pas fájlt.