[Powered by Google Translate] [Queue]
[Chris Gerber, Harvard University]
Ez CS50, CS50.TV]
Egy hasznos adatstruktúra tárolására rendezett gyűjteménye elemek a sorban.
Akkor használják, ha az elemeket el kell oszlatni
abban a sorrendben, ahogy adunk.
Ez a koncepció nevezik FIFO, ami egy mozaikszó az első be, első ki.
Annak érdekében, hogy láthatóvá E, hasznos lehet a kép
a pénztárnál sorban egy boltban.
Mivel az emberek érkeznek, hogy várjon a hátsó sorban.
A pénztáros ezután felváltva szolgálja az ügyfelek az első,
aki aztán kilép a vonalon egy időben.
A számítógép-tudomány, utalunk az első a sorban, mint a fej
és a hátsó, mint a farok.
Egy példa, amikor talán ezt egy alkalmazásban
a várólista osztály beiratkozást.
Mivel a helyek válnak elérhetővé az osztályban,
az a személy, az élén a várakozási lista lehetőséget biztosított, hogy beiratkozik az osztályban.
>> A sort lehet kialakítani bármilyen gyűjtemény
hogy tárolja az adatokat annak érdekében, mint például a tömb vagy egy láncolt lista.
Együtt a gyűjtemény tárolni az elemeket a sorban,
azt is meg kell egy módszert hozzá elem a végén a sor,
amely az úgynevezett enqueuing,
és egy másik, hogy távolítsa el egy elemet a fejét a sorban,
amely az úgynevezett dequeuing.
Gyakran hasznos fel más módszert, hogy visszatérjen a jelenlegi hossza a sorban
valamint egy módszer annak ellenőrzésére, a sor üres.
Nézzük meg, hogyan lehet végrehajtani a sorban Egész számok C,
használ egy tömböt gyűjtésére elemeket.
Először is, hozzon létre egy struktúrát nevű sorban, hogy tartsa meg a változókat.
Fogjuk használni egy fix méretű tömb indexe 0 egészek
tárolni az elemeknek.
Mi is egy változó nevű fej
amely tárolja az index az elem, hogy a jelenleg a fejét a sorban.
Egy harmadik változó, úgynevezett hosszúságú, lesz használva
nyomon követni az elemek száma a tömbben.
Ennek alternatívájaként, akkor fontolja meg a változó nevű farok
pont az utolsó field elem a tömbben.
Mielőtt írni többé kódot,
próbáljuk ki a design.
Kezdjük egy üres tömb hossza 0,
a fej 0-ra.
Most sorba állítása 4 értéke - 6, 2, 3, és 1.
A hossza most már 4,
és a fej marad 0 °.
>> Mi történik, ha dequeue érték?
Csökkenteni fogjuk a hossza 3,
állítsa be a fejét, hogy 1,
és vissza az érték 6.
Ez a kód ilyesmi.
Itt van a dequeue funkciót,
amely úgy a mutatót a sorban - q -, és a mutatót az elem,
amely egyfajta int.
Először is ellenőrizze a hossza a sorban, hogy megbizonyosodjon arról, hogy ez több, mint 0,
annak érdekében, hogy van egy elemét lehessen úgy dequeued.
Akkor nézze meg a tömb elemeit, a helyzet fejét,
és állítsa be az értéket az elem, hogy az érték az adott helyzetben.
Ezután módosítsa a fejét, hogy a következő index
%-A kapacitás.
Ezután csökkenti a hosszát a sor 1-gyel.
Végül vissza, jelezve, hogy igaz az dequeue volt sikeres.
Ha dequeue ismét, a hossz válik 2,
a fej is lesz 2,
és a visszatérési érték lesz 2.
>> Mi történik, ha sorba állításához más érték, mint a 7?
Mint voltunk végén a sor,
meg kell köré és tárolja az értéket 0 elem a tömbben.
Matematikailag ez képviseli hozzáadásával hossz
Az index a fej
végző és modulus segítségével queue kapacitást.
Itt, hogy a 2 +2, ami 4% 4,
amely jelentése 0.
Fordítás ezt a gondolatot kódot, rendelkezik ezzel a funkcióval.
Itt látjuk a sorba állítása funkció
amely úgy a mutatót a sorban - q -
és úgy az elemét lehessen úgy enqueued, ami egy egész szám.
Mi mellett ellenőrizze, hogy győződjön meg arról, hogy a kapacitás a sor
még mindig nagyobb, mint a jelenlegi hossza a sorban.
Következő, tárolunk az elem elemeiben tömb
az index határozza meg a fej + hossz%-kapacitása a sorban.
Ezután növelje a queue hossza 1,
majd a return true, jelezve, hogy a sorba állítása funkció sikeres volt.
>> Amellett, hogy a két funkció általunk említettük,
két további funkciókat.
Először is a IsEmpty funkció,
amely úgy a mutatót a sorban
és ellenőrzi, hogy a hossza 0.
A második a hossz funkció,
is vesz egy mutatót a sorban
és visszaadja az aktuális hossza a struct.
Ez a rövid áttekintés bebizonyította egyik lehetséges megvalósítása sorban.
Az egyik a korlátait, a végrehajtás
az, hogy a sorban van egy rögzített maximális méretet.
Ha megpróbáljuk, hogy adjunk több elem, mint a sorba fér,
szükség lehet arra, hogy figyelmen kívül hagyja a kérést, és dobja az elemet,
vagy talán inkább vissza valamilyen hiba.
Egy láncolt lista helyett egy tömböt
lehetővé tenné, hogy dinamikusan méret a sorban.
Azonban, mivel nem rendelkeznek közvetlen hozzáféréssel a elemeit láncolt lista,
ha nem tartjuk számon a farok,
mi lett volna, hogy átvizsgálja a teljes láncolt lista, hogy a végén minden alkalommal.
Azt is fontolja meg egy sor más adattípusok,
mint például a struktúrákat, hogy hozzon létre sorok bonyolultabb elemeket.
Gondolkodás vissza az például egy osztály várólista,
ezek a struktúrák jelenthet az egyéni versenyző.
>> A nevem Chris Gerber, és ez CS50.
[CS50.TV]
És visszatér - >> Mégegyszer.
És return true azt jelzi, hogy - a sorban sikeres volt.
-% A kapacitás a sor -
Ez lesz szórakoztató a szerkesztés. [Nevetés]