[Powered by Google Translate] [Biðröð]
[Chris Gerber, Harvard University]
Þetta er CS50, CS50.TV]
Einn gagnlegur gögn uppbygging til að geyma að panta safn frumefni er biðröð.
Það er notað þegar atriði þarf að vera fjarri
í sömu röð og þeir voru við.
Þetta hugtak er nefnt FIFO, sem er skammstöfun fyrir fyrst inn, fyrst út.
Til að hjálpa sjón það, getur það verið gagnlegt að mynd
a stöðva línu á verslun.
Eins og fólk kemur, bíða þeir á bak við línuna.
Gjaldkeri tekur þá skiptast þjóna viðskiptavinum í framan,
sem hætta síðan línuna einn í einu.
Í tölvunarfræði, átt við að framan biðröð og höfuð
og aftur og hali.
Dæmi um hvenær við gætum notað þetta í forriti
er waitlist fyrir skráninga bekknum.
Sem sæti verða í boði í bekknum,
sá í höfuðið á biðlista er veitt tækifæri til að innritast í bekknum.
>> A biðröð getur verið smíðaður með hvaða safn
sem geymir gögn í því skyni, svo sem fylki eða tengda listanum.
Ásamt safn til að geyma hluti í biðröð,
við þurfum líka aðferð til að bæta hlutum við lok biðröð,
sem heitir enqueuing,
og aðra til að fjarlægja hlut úr höfði biðröð,
sem heitir dequeuing.
Það er oft gagnlegt að fela aðra aðferð til að skila núverandi lengd biðröð
og aðferð til að athuga hvort biðröð er tóm.
Við skulum líta á hvernig við gætum innleiða biðröð heiltalna í C,
nota fylki til innheimtu frumefni.
Fyrst skaltu búa við skipulag sem kallast biðröð til að halda breytur okkar.
Við munum nota fasta stærð 0 vísitölu fjölbreytta heiltölur
að geyma atriði.
Við munum einnig breytilega heitir höfuð
sem geymir vísitölu frumefni sem er nú í forsvari fyrir biðröð.
Þriðja breyta, length, verður notuð
til að halda utan um fjölda staka í fylki.
Sem val, þú getur íhuga að nota breytu sem heitir hala
að benda á síðasta sviði þáttur í fylki.
Áður en við að skrifa einhverjar fleiri kóða,
skulum prófa hönnun okkar.
Við skulum byrja með tóman fjölda lengd 0,
með höfuð stillt á 0.
Nú e, skulum 4 gildi - 6, 2, 3, og 1.
Lengd verður nú að vera 4,
og höfuð mun gista á 0.
>> Hvað gerist ef við dequeue gildi?
Við munum draga úr lengd í 3,
setja höfuð á 1,
og skila gildi 6.
Sá kóði getur litið svona út.
Hér höfum við dequeue virka,
sem tekur bendi á í biðröð - Q - og bendi á frumefni,
sem er tegund int.
Fyrst við athugum lengd biðröð til að ganga úr skugga um að það er meira en 0,
til að tryggja að það er þáttur í að dequeued.
Þá erum við að horfa á þætti fylking, í sömu stöðu höfuð,
og setja the gildi af frumefni að gildi á þeirri stöðu.
Þá erum við að breyta höfuð að vera næsta vísitölu
% Getu.
Við draga þá lengd biðröð eftir 1.
Að lokum, aftur við rétt til að sýna að dequeue tókst.
Ef við dequeue aftur lengd verða 2,
höfuð mun einnig verða 2,
og skilagildi verða 2.
>> Hvað gerist ef við e, annað gildi, svo sem 7?
Þegar við vorum í lok biðröð,
við verðum að vefja um og geyma verðmæti í 0 þáttur fylkisins.
Stærðfræðilega má þetta vera fulltrúa með því að bæta lengd
við vísitölu höfuð
og framkvæma stuðull með biðröðina getu.
Hér er að 2 +2, sem er 4% 4,
sem er 0.
Þýðing þessa hugmynd að kóða við höfum þessa aðgerð.
Hér sjáum við e, virka,
sem tekur bendi á biðröð - Q -
og tekur þátturinn að enqueued, sem er heiltala.
Við athuga næst að tryggja að getu biðröð
er enn meiri en núverandi lengd biðröð.
Næst geyma við þáttur í þætti fylki
á vísitölunni, sem er ákvörðuð út frá höfuð + lengd% getu biðröð.
Við aukið þá biðröð lengd um 1,
og síðan aftur rétt til að sýna að e, virka tókst.
>> Í viðbót við tvo valkosti við höfum getið,
Það eru tvær aðrar aðgerðir.
Fyrst er isempty virka,
sem tekur bendi á í biðröð
og staðfestir að lengd 0.
Annað er lengd virka,
sem tekur einnig bendi til biðröð
og skilar núverandi lengd frá strúktúr.
Þetta stutt yfirlit hefur sýnt ein hugsanleg framkvæmd af biðröð.
Ein af takmörkunum við þessa framkvæmd
er að biðröð hefur fasta hámarks stærð.
Ef við reynum að bæta við fleiri þáttum en biðröð hægt er að halda,
við gætum þurft að hunsa beiðnina og sleppa þáttur,
eða við gætum vilja til að skila einhvers konar villa.
Notkun tengd lista frekar en fylki
myndi gera það auðveldara að dynamically stærð biðröð.
En þar sem við höfum ekki beinan aðgang að þætti í tengda listanum,
Ef við gerum ekki viðurværi rekja spor einhvers af the hali,
yrðum við að skanna allt tengda listanum til að fá að enda hvert skipti.
Við gætum líka íhuga að nota fjölda annars gögn tegund,
eins structs, til að búa til biðraðir á flóknari atriði.
Hugsun aftur til okkar dæmi um tegund waitlist,
þessara stofnana gæti tákna einstaka nemendur.
>> Mitt nafn er Chris Gerber, og þetta er CS50.
[CS50.TV]
Og aftur - >> einu sinni enn.
Og aftur rétt til að sýna að - biðröð tókst.
-% Getu í biðröð -
Það er að fara að vera gaman í breytingu. [Hlátur]