[Powered by Google Translate] [Radhë]
[Chris Gerber, Universiteti i Harvardit]
Kjo është CS50, CS50.TV]
Një strukturë e dobishme për ruajtjen e të dhënave një koleksion urdhëruar të elementeve është një radhë.
Ajo është përdorur kur elemente duhet të hiqen
në të njëjtën mënyrë si ata janë shtuar.
Ky koncept është përmendur si FIFO, e cila është një akronim për të parë në, së pari jashtë.
Për të ndihmuar kujtoj këtë, ajo mund të jetë e dobishme për fotografinë
një linjë arka në një dyqan.
Ndërsa njerëzit arrijnë, ata presin në pjesën e pasme të linjës.
Me turp pastaj merr kthehet duke shërbyer klientëve në pjesën e përparme,
të cilët pastaj të dalë nga një linjë në një kohë.
Në shkenca kompjuterike, ne i referohemi frontin e radhës si kryetar
dhe prapa si bisht.
Një shembull i kur ne mund të përdorin këtë në një aplikim
është një waitlist për regjistruarve klasës.
Si vende të bëhen të disponueshme në klasë,
personi në krye të listës së pritjes është dhënë mundësia të regjistrohen në klasë.
>> Një radhë mund të ndërtohet duke përdorur ndonjë koleksion
që ruan të dhënat në mënyrë, të tilla si një grup ose një listë të lidhura.
Së bashku me mbledhjen për të ruajtur sendet në radhë,
ne gjithashtu nevojë për një metodë për të shtuar artikuj në fund të rreshtit,
cila është e quajtur enqueuing,
dhe një tjetër për të hequr një artikull nga kreu i radhës,
cila është e quajtur dequeuing.
Kjo është shpesh e dobishme për të përfshirë një tjetër metodë për të kthyer gjatësinë aktuale të radhës
si një metodë për të kontrolluar nëse queue është bosh.
Le të shohim se si ne mund të zbatojë një radhë të integers në C,
duke përdorur një rrjet për mbledhjen e elementeve.
Së pari, ne kemi krijuar një strukturë të quajtur radhë për të mbajtur variablave tona.
Ne do të përdorë një fikse-size index grup i integers 0
për të ruajtur elementet.
Ne gjithashtu do të përfshijë një kokë ndryshueshme quajtur
që ruan indeksin e elementit që është aktualisht në krye të rreshtit.
Një variabël i tretë, të quajtur gjatësia, do të përdoret
të mbajnë gjurmët e numrit të elementeve në array.
Si një alternativë, ju mund të konsideroni përdorimin e një bisht ndryshueshme quajtur
për pikë në elementin e fundit në terren në rrjet.
Para se të shkruani kodin më,
le të provoni dizajn tonë.
Le të fillojmë me një grup të zbrazët gjatësi 0,
me kokë të vendosur për të 0.
Tani le të enqueue 4 - 6 vlerat, 2, 3, dhe 1.
Gjatësia tani do të jetë 4,
dhe koka do të qëndrojë në 0.
>> Çfarë ndodh nëse ne dequeue një vlerë?
Ne do të reduktojë kohëzgjatjen deri në 3,
vendosur kokën në 1,
dhe kthimin e vlerës 6.
Se kodi mund të duket si kjo.
Këtu kemi funksionin dequeue,
e cila merr një tregues për radhë - Q - dhe një tregues për elementin,
cila është një int lloj.
Së pari ne kontrolloni kohëzgjatjen e radhës për t'u siguruar se është më shumë se 0,
për të siguruar se ka një element të dequeued.
Pastaj ne shikojmë në grup elementesh, në krye pozicion,
dhe vendosur vlerën e elementit të jetë vlera në atë pozitë.
Pastaj ne të ndryshojë kokën të jetë indeksi tjetër
% Kapacitet.
Ne pastaj të zvogëlojë kohëzgjatjen e radhës nga 1.
Së fundi, ne kthim i vërtetë për të treguar se dequeue ishte i suksesshëm.
Nëse ne dequeue përsëri, gjatësia do të bëhet 2,
kreu gjithashtu do të bëhen 2,
dhe vlera e kthimit do të jetë 2.
>> Çfarë ndodh nëse ne enqueue një tjetër vlerë të tilla si një 7?
Si ne ishin në fund të rreshtit,
ne do të duhet për të përfunduar rreth dhe ruajtur vlerën në 0 element të vektorit.
Matematikisht, kjo mund të përfaqësohet nga shtuar gjatësinë
me indeksin e kokës
dhe kryerjen e një modulus duke përdorur kapacitetin radhë.
Këtu që është 2 2, e cila është 4% 4,
cila është 0.
Përkthimi këtë ide të kodit ne kemi këtë funksion.
Këtu ne shohim funksionin enqueue,
e cila merr një tregues për radhë - Q -
dhe merr elementi të enqueued, e cila është një numër i plotë.
Ne ardhshëm kontrolloni për t'u siguruar se kapaciteti i radhës
është ende më e madhe se gjatësia e tanishme e radhës.
Tjetra, ne dyqan elementin në rrjet elementeve
në indeksin e cila është përcaktuar nga kreu +% gjatësia kapaciteti i radhë.
Ne pastaj të rritur gjatësinë radhë me 1,
dhe pastaj kthehen e vërtetë për të treguar se funksioni enqueue ishte i suksesshëm.
>> Përveç këtyre dy funksioneve që kemi përmendur,
ka dy funksione shtesë.
Së pari është funksioni isempty,
cili merr nje tregues te radhë
dhe verifikon se gjatësia është 0.
E dyta është funksioni gjatësi,
i cili gjithashtu merr një tregues për radhë
dhe kthen gjatësinë aktuale nga struct.
Kjo pasqyrë e shkurtër e ka demonstruar një implementimin e mundshëm të një radhë.
Një nga kufizimet në zbatim të këtij
është se radhë ka një madhësi të caktuar maksimale.
Nëse ne përpiqemi për të shtuar elementet më shumë se sa mund të mbajë radhë,
ne mund të kenë nevojë të injorojë kërkesën dhe të heqë elementin,
ose ne mund të preferojnë të kthehen disa lloj të gabimit.
Duke përdorur një listë e lidhur më tepër se një grup
do ta bënte më të lehtë për madhësi dinamike radhë.
Megjithatë, pasi ne nuk kemi qasje të drejtpërdrejtë në elementet e një liste të lidhura,
në qoftë se ne nuk i mbajnë gjurmët e bisht,
ne do të duhet të scan të gjithë listën lidhur për të marrë në fund çdo kohë.
Ne gjithashtu mund të konsiderojnë duke përdorur një rrjet të një lloji tjetër të të dhënave,
të tilla si structs, për të krijuar rradhë të elementeve më komplekse.
Duke menduar përsëri në shembullin tonë të waitlist klasës,
këto struktura mund të përfaqësojnë studentët individuale.
>> Emri im është Chris Gerber, dhe kjo është CS50.
[CS50.TV]
Dhe kthimit - >> Njëri më shumë kohë.
Dhe kthimin e vërtetë për të treguar se - queue ishte i suksesshëm.
-% Kapaciteti i radhës -
Ajo do të jetë kënaqësi në redaktim. [Qeshura]