[Powered by Google Translate] [Kju]
[Chris Gerber, Università ta 'Harvard]
Dan huwa CS50, CS50.TV]
Wieħed utli struttura tad-data għall-ħażna ġabra ordnata ta 'elementi huwa kju.
Huwa jintuża meta l-elementi għandhom jitneħħew
fl-istess ordni kif kienu miżjuda.
Dan il-kunċett huwa msejjaħ FIFO, li huwa akronimu għal ewwel, l-ewwel barra.
Biex tgħin Ħares dan, jista 'jkun utli li stampa
linja checkout fil-maħżen.
Billi n-nies jaslu, huma jistennew fuq wara tal-linja.
Il-kaxxier mbagħad jieħu dawriet li jservu lill-klijenti fuq quddiem,
li mbagħad ħruġ tal-linja waħda kull darba.
Fix-xjenza tal-kompjuter, aħna nirreferu għall-quddiem tal-kju bħala l-kap
u d-dahar bħala l-denb.
Eżempju ta 'meta aħna jistgħu jużaw din f'applikazzjoni
huwa waitlist għal reġistrazzjonijiet klassi.
Kif sedili jsiru disponibbli fil-klassi,
il-persuna fil-kap tal-lista ta 'stennija hija pprovduta l-opportunità li jinkitbu fil-klassi.
>> A kju jistgħux jiġu mibnija bl-użu kull ġbir
li taħżen informazzjoni sabiex, bħal firxa jew lista marbuta.
Flimkien mal-ġbir li jaħżen l-oġġetti fil-kju,
aħna wkoll bżonn ta 'metodu li wieħed iżid punti fl-aħħar tal-kju,
li hija imsejħa enqueuing,
u ieħor li tneħħi oġġett mill-kap tal-kju,
li tissejjaħ dequeuing.
Huwa ta 'spiss utli li tinkludi metodu ieħor li tirritorna t-tul attwali tal-kju
kif ukoll bħala metodu biex jiċċekkjaw jekk il-kju hija vojta.
Ejja nħarsu lejn kif nistgħu timplimenta kju tan-numri interi fis-C,
użu ta 'firxa għall-ġbir ta' elementi.
L-ewwel, noħolqu struttura msejħa kju biex iżommu varjabbli tagħna.
Aħna ser tuża fiss daqs 0 indiċi firxa ta 'numri interi
li jaħżen l-elementi.
Aħna se jinkludi wkoll ras varjabbli imsejjaħ
li taħżen l-indiċi ta 'l-element li huwa attwalment fir-ras ta' l-kju.
A varjabbli tielet, imsejħa tul, se tintuża
li jżommu rekord tan-numru ta 'elementi fil-firxa.
Bħala alternattiva, inti tista 'tikkunsidra tuża denb varjabbli imsejjaħ
għall-punt għall-element qasam aħħar fil-firxa.
Qabel ma aħna jikteb il-kodiċi kwalunkwe aktar,
ejja jippruvaw disinn tagħna.
Nibdew ma 'firxa vojta ta' tul 0,
bir-ras stabbiliti għal 0.
Issa ejja enqueue 4 Valuri - 6, 2, 3, u 1.
It-tul issa se jkun ta '4,
u l-kap se jibqa '0.
>> X'jiġri jekk aħna dequeue valur?
Aħna se jnaqqas it-tul sa 3,
jistabbilixxu l-ras għal 1,
u jirritorna l-valur 6.
Dik il-kodiċi tista 'tidher bħal dan.
Hawnhekk għandna l-funzjoni dequeue,
li tieħu pointer għall-kju - q - u pointer għall-element,
li huwa int tip.
L-ewwel għandna jiċċekkja t-tul tal-kju biex tagħmel ċert li huwa aktar minn 0,
biex jiżguraw li jkun hemm element li għandu dequeued.
Imbagħad aħna nħarsu fil-firxa elementi, il-kap pożizzjoni,
u tistabbilixxi l-valur ta 'element li jkun il-valur f'dik il-pożizzjoni.
Imbagħad aħna jibdlu l-ras li tkun l-indiċi li jmiss
% Tal-kapaċità.
Aħna mbagħad jitnaqqas it-tul tal-kju sa l-1.
Fl-aħħarnett, nerġgħu lura minnu li jindikaw li l-dequeue kienet ta 'suċċess.
Jekk aħna dequeue darb'oħra, it-tul se jsiru 2,
il-kap se jsir ukoll 2,
u l-valur tar-ritorn se jkun 2.
>> X'jiġri jekk aħna enqueue valur ieħor bħal 7?
Kif konna fl-aħħar tal-kju,
ser ikollna bżonn biex nagħlaq madwar u jaħżnu l-valur fil-0 element ta 'l-array.
Matematikament, dan jista 'jiġi rappreżentat billi żżid it-tul
l-indiċi tar-ras
u jwettqu modulus użu tal-kapaċità kju.
Hawnhekk jiġifieri 2 +2, li huwa ta '4% 4,
li hija 0.
Traduzzjoni din l-idea għall-kodiċi li għandna din il-funzjoni.
Hawnhekk naraw il-funzjoni enqueue,
li tieħu pointer għall-kju - q -
u jieħu l-element li għandu enqueued, li huwa integer.
Aħna li jmiss jivverifika sabiex ikun żgur li l-kapaċità tal-kju
għadu akbar mit-tul attwali tal-kju.
Sussegwentement, aħna jaħżnu l-element fil-firxa elementi
li l-indiċi li huwa determinat mill-kap +% tul il-kapaċità tal-kju.
Aħna mbagħad tiżdied it-tul kju sa l-1,
u mbagħad jirritornaw veru li jindika li l-funzjoni enqueue kienet ta 'suċċess.
>> Minbarra l-żewġ funzjonijiet konna msemmija,
hemm żewġ funzjonijiet addizzjonali.
L-ewwel hija l-funzjoni isempty,
li tieħu pointer għall-kju
u jivverifika li t-tul huwa 0.
It-tieni hija l-funzjoni tul,
li wkoll jieħu pointer għall-kju
u jirritorna l-tul attwali mill-Struct.
Dan l-inventarju qasir wera 1 implimentazzjoni possibbli ta 'kju.
Wieħed mill-limitazzjonijiet li din l-implimentazzjoni
hija li l-kju għandu daqs massimu fiss.
Jekk nippruvaw li jiżdiedu elementi aktar milli l-kju tista 'żżomm,
għandna jistgħu jeħtieġu li jinjoraw it-talba u qatra l-element,
jew aħna jistgħu jippreferu li jirritorna xi tip ta 'żball.
Bl-użu ta 'lista marbut minflok firxa
jagħmilha aktar faċli għad-daqs dinamiku-kju.
Madankollu, peress li aħna ma jkollhomx aċċess dirett għall-elementi ta 'lista marbuta,
jekk aħna ma jżommu rekord tad-denb,
rridu naraw li skennjati l-lista kollha marbuta li tikseb sa l-aħħar ta kull darba.
Aħna jista 'wkoll tikkunsidra li tuża firxa ta' tip ieħor ta 'data,
bħal structs, li joħolqu kjuwijiet ta 'elementi aktar kumplessi.
Thinking lura għall-eżempju tagħna ta 'waitlist klassi,
dawn l-istrutturi jistgħu jirrappreżentaw l-istudenti individwali.
>> Jisimni Chris Gerber, u dan huwa CS50.
[CS50.TV]
U l-prospetti - >> Wieħed aktar ħin.
U r-ritorn vera li jindikaw li - l-kju kien suċċess.
-% Tal-kapaċità tal-kju -
Huwa ser tkun divertenti fil jeditjaw. [Daħk]