[Powered by Google Translate] [6.pants: mazāk apmierināti]
[Nate Hardison] [Hārvarda]
[Tas ir CS50.] [CS50.TV]
Labi. Laipni lūdzam 6.daļā.
Šajā nedēļā, mēs ejam runāt par datu struktūras sadaļā,
galvenokārt tāpēc, ka šīs nedēļas problēma, kas par spellr
tas viss ķekars dažādu datu struktūru izpētei.
Ir dažādi veidi, kā jūs varat iet ar problēmu kopumu ķekars,
un jo vairāk datu struktūras tu zini, jo vairāk labas lietas jūs varat darīt.
>> Tāpēc pieņemsim sāktu. Vispirms mēs esam gatavojas runāt par skursteņi,
kaudzīti un rinda datu struktūras, ka mēs ejam runāt.
Skursteņi un rindas ir patiešām noderīga, ja mēs sākam runāt par grafiku,
kas mēs neesam gatavojas darīt tik daudz tiesības tagad.
Bet viņi tiešām labi, lai saprastu vienu no lielajām pamattiesību datu struktūrās CS.
Apraksti problēmu kopas specifikāciju,
ja jūs pull to, runā par skursteņi kā līdzīgs
pāļu ēdināšanas paplātēm, kas jums ir kafejnīcā pie ēdamzāles
kur, kad restorānvagonos darbinieki nāk un liek ēdamistabas paplātes, pēc viņi iztīra tos,
tās kaudze viņiem viens uz otru.
Un tad, kad bērni nāk, lai iegūtu pārtiku,
viņi pull teknes pie pirmās top viens, tad viens zem tā, tad viens zem ka.
Tātad, faktiski, pirmā paplāti, ka pusdienu darbinieki nolika ir pēdējais, kas izpaužas pacēlies.
Pēdējais ka restorānvagonos darbinieki likts uz ir pirmais, kas izpaužas pacēlies uz vakariņām.
Jo šī problēma Set s spec, ko jūs varat lejupielādēt, ja jums vēl nav,
mēs runājam par modelēšana kaudze datu Ārējie Inženiertīkli izmantojot šāda veida struct.
>> Tātad, ko mēs esam ieguvuši šeit, tas ir līdzīgs tam, kāds tika iesniegts lekciju,
izņemot lekcijā mēs iepazīstināja to ar Ints pretstatā char * s.
Tas būs kaudze, kas veikalos, ko?
Daniel? Ko mēs uzglabājot šajā kaudze?
[Daniels] stīgas? >> Mēs uzglabājot stīgas šajā kaudze, tieši tā.
Viss, kas jums ir, lai izveidotu kaudze ir masīvs
konkrēta jaudu, kas šajā gadījumā,
jauda būs visos cepures, jo tas ir nemainīgs.
Un tad papildus masīvs, viss mums ir nepieciešams izsekot ir pašreizējā lielums masīvā.
Viena lieta atzīmēt šeit, ka ir veida atdzist
ir tāds, ka mēs esam radot stacked datu struktūru uz cita datu struktūra, masīvs.
Ir dažādi veidi, kā īstenot skursteņi.
Mēs to darīt diezgan vēl, bet cerams pēc darot saistīts-list problēmas,
jūs redzēsiet, kā jūs varat viegli īstenot kaudze virsū saistīts saraksts, kā arī.
Bet tagad, mēs stick ar masīviem.
Tātad vēlreiz, viss, kas mums vajadzīgs, ir masīvs un mēs vienkārši nepieciešams, lai izsekotu lielumu masīva.
[Sems] Atvainojiet, kāpēc ir tā, ka jūs teicāt, kaudze ir uz augšu no virknes?
Man šķiet, piemēram stīgas atrodas kaudze.
[Hardison] Jā. Mēs esam radot, mēs esam ņemot mūsu masīvu datu struktūra -
ka ir liels jautājums. Tātad jautājums ir, kāpēc, par cilvēkiem, kas skatās šo tiešsaistē,
kāpēc mēs sakot, ka kaudze ir uz augšu no stīgas,
jo šeit tas izskatās stīgas ir iekšā kaudze?
Kas ir pilnīgi gadījums.
Ko es atsaucoties uz bija tas, ka mēs esam ieguvuši masīvu datu struktūra.
Mēs esam ieguvuši masīvu char * s, šis masīvs stīgas,
un mēs pievienot, ka, lai radītu stacked datu struktūra.
>> Tātad kaudze ir nedaudz sarežģītāka nekā masīvā.
Mēs varam izmantot masīvu, lai izveidotu kaudze.
Tā ka, ja mēs sakām, ka kaudze ir veidota uz augšu no masīva.
Tāpat kā es teicu iepriekš, mēs varam veidot kaudze uz augšu saistītajā sarakstā.
Tā vietā, izmantojot masīvu turēt mūsu elementus,
mēs varētu izmantot saistīts saraksts turēt mūsu elementiem un veidot kaudzīti ap to.
Apskatīsim pāris piemērus, aplūkojot kādu kodu,
lai redzētu, kas patiesībā notiek šeit.
Pa kreisi, es esmu nomests ko tas kaudze struktūrai būtu jāizskatās atmiņā
ja jauda bija # noteikts kā četri.
Mēs esam ieguvuši mūsu četru elementu char * masīvs.
Mēs esam ieguvuši stīgas [0], stīgas [1], stīgas [2], stīgām [3],
un tad, ka pēdējā vieta mūsu lieluma skaitlim.
Vai tas ir jēga? Labi.
Tas ir tas, kas notiek, ja tas, ko es daru pa labi,
kas būs mans kods, ir tikai atzīt struct, stacked struct sauc s.
Tas ir tas, ko mēs saņemam. Tā nosaka šo nospiedumu atmiņā.
Pirmais jautājums ir, kādi ir šīs kaudze struct saturs?
Tieši tagad viņi neko, bet viņi nav pilnīgi nekas.
Viņi šāda veida atkritumiem. Mums nav ne jausmas, kāda ir tiem.
Kad mēs atzīt kaudze s, mēs esam tikai throwing ka virsū atmiņas.
Tas ir veids kā atzīst int i un nav inicializēta to.
Tu nezini, kas ir tur. Jūs varat izlasīt to, kas tur,
bet tas varētu būt super noderīga.
Viena lieta, jūs vēlaties, lai vienmēr atcerēties to darīt, ir inicializ kāds nepieciešams inicializēts.
Šajā gadījumā, mēs ejam, lai sāktu izmēru nullei,
jo tas gatavojas izrādīties ļoti svarīgi, lai mums.
Mēs varētu iet uz priekšu un sāktu visu no norādes, visi char * s,
būt daži saprotams vērtība, iespējams, Null.
Bet tas nav pilnīgi nepieciešams, ka mēs to darām.
>> Tagad, divi galvenie operācijas skursteņi ir?
Kāds atcerēties no lekciju, ko jūs darīt ar skursteņi? Jā?
[Stella] Grūšana un popping? >> Tieši tā.
Stumšana un popping ir divi galvenie darbības uz skursteņi.
Un ko push darīt? >> Tas liek kaut uz augšu
no skursteņa, un tad popping ņem to nost.
[Hardison] Tieši tā. Tāpēc spiežot nospiež kaut virsū kaudze.
Tas ir tāpat kā pusdienu darbiniekiem liekot pusdienu paplāti uz leju uz letes.
Un popping veic pusdienu paplāti nost no skursteņa.
Apskatīsim pāris piemērus, kas notiek
kad mēs push lietas vērā kaudze.
Ja mēs virzīt virkni "sveiki" uz mūsu kaudze,
tas ir tas, ko mūsu diagramma izskatās tagad.
Redzēt, kas notiek?
Mēs uzstājām uz pirmo elementu mūsu stīgas masīva
un mēs upped mūsu izmēra skaits ir 1.
Tātad, ja mēs skatāmies uz atšķirību starp diviem slaidiem, šeit bija 0, šeit pirms push.
Šeit ir pēc push.
Pirms push, pēc push.
Un tagad mums ir viens elements mūsu kaudze.
Tā ir virkne "sveiki", un tas arī viss.
Viss pārējais masīvā, jo mūsu Stīgu masīvs, joprojām ir atkritumu.
Mēs esam nav inicializēts to.
Teiksim mēs push citu stīgu uz mūsu kaudze.
Mēs ejam, lai push "pasauli", par šo laiku.
Tātad jūs varat redzēt "pasaule" šeit iet uz augšu "sveiki",
un izmēru skaits pieaugs līdz 2.
Tagad mēs varam virzīt "CS50", un ka iešu uz augšu vēlreiz.
Ja mēs ejam atpakaļ, jūs varat redzēt, kā mēs spiežot lietas uz augšu kaudze.
Un tagad mēs to pop.
Kad mēs popped kaut nost no skursteņa, kas notika?
Ikviens redzēt atšķirību? Tas ir diezgan smalks.
[Studentu] lielumu. >> Jā, izmērs mainīts.
>> Ko vēl jūs sagaidīt, lai mainītu?
[Studentu] stīgas, too. >> Tiesības. Stīgas too.
Izrādās, ka tad, kad jūs darāt to šādā veidā,
jo mēs esam ne kopējot elementus mūsu kaudze,
mums patiesībā nav jādara kaut, mēs varam tikai izmantot lielumu
lai sekotu par vairākām lietām, kas mūsu masīvā
lai tad, kad mēs pop atkal, atkal mēs vienkārši samazināšanās mūsu izmēra leju līdz 1.
Nav nepieciešams, lai faktiski iet un pārrakstīt neko.
Veida bailīgs.
Izrādās, ka mēs parasti vienkārši atstāt lietas atsevišķi, jo tas ir mazāk darba mums darīt.
Ja mums nav iet atpakaļ un pārrakstīt kaut ko, tad kāpēc to darīt?
Tātad, kad mēs pop divreiz nost no skursteņa, viss, kas dara, ir samazinājums ir no lieluma pāris reizes.
Un atkal, tas ir tikai tāpēc, ka mēs esam ne kopējot lietas vērā mūsu kaudze.
Jā? Iet uz priekšu.
[Studentu, nesaprotami] >> Un tad kas notiek, ja jūs push kaut vēlreiz?
Kad jūs push kaut atkal, ja tas iet?
Kur tas iet, Basil? >> Into stīgas [1]? >> Tiesības.
Kāpēc ne iet uz stīgām [3]?
[Baziliks] Jo tas aizmirsa, ka tur bija kaut virtenēs [1] un [2]?
[Hardison] Tieši tā. Mūsu kaudze, būtībā, "aizmirsa", ka tā bija saimniecības uz jebko
virtenēs [1] vai virknes [2], tad, kad mēs push "woot",
tas tikai liek ka uz elementu pie virknes [1].
Vai ir kādi jautājumi par to, kā tā darbojas, pie pamata līmenī?
[Sems] Tātad tas nav dinamisks nekādā veidā, kas apjoma ziņā
vai kā lieluma kaudze?
[Hardison] Tieši tā. Tas ir - punkts bija, ka tas nav dinamiski growning kaudze.
Tas ir kaudze, kas var turēt, labākajā, četri char * s, ne vairāk kā četri lietām.
Ja mēs mēģinātu virzīt 1/5 lieta, ko jūs domājat vajadzētu notikt?
[Studenti, nesaprotami]
[Hardison] Tieši tā. Ir lietas, kas varētu notikt numuru.
Tas, iespējams, varētu SEG vainu, atkarībā no tā, ko mēs -
kā tieši mēs īsteno back-end.
Tā varētu pārrakstīt. Tā varētu būt, ka bufera pārpildes ka mēs runājām par klasē.
Kāds būtu visvairāk acīmredzama lieta, kas varētu būt pārrakstīta
ja mēs mēģinājām virzīt papildu lieta, par mūsu kaudze?
Tātad jūs minējāt bufera pārpildes.
Kāda varētu būt lieta, kas varētu saņemt rakstisku pāri vai stomped par
ja mēs pārplūda nejauši, mēģinot virzīt papildus lieta?
[Daniels, nesaprotami] >> iespējams.
Bet sākotnēji, kas varētu notikt? Ko darīt, ja mēs centāmies push Ceturtā lieta?
Tas varētu pārrakstīt lielumu, vismaz ar šo atmiņas diagrammu ka mēs esam ieguvuši.
>> Jo problēma noteikto specifikāciju, kas ir tas, ko mēs gribam būt īstenošanai šodien,
ko mēs vēlamies darīt, ir tikai atgriezties viltus.
Mūsu push metode gatavojas atgriezties Būla vērtību,
un ka Būla vērtība būs taisnība, ja push izdodas
un viltus ja mēs nevaram virzīt neko vairāk, jo kaudze ir pilna.
Apskatīsim mazliet minētā kodeksa tiesības tagad.
Lūk, mūsu push funkciju.
Mūsu push funkciju kaudze gatavojas pieņemt virknē likt uz skursteņa.
Tas notiek, lai atgrieztos taisnība, ja stīgu tika veiksmīgi uzstāja
gada kaudze un viltus citādi.
Jebkādi kādi ieteikumi varētu būt labs pirmais, kas jādara šeit?
[Sems] Ja lielums ir vienāds jaudu tam atgriezties viltus?
[Hardison] Bingo. Jauki darbs.
Ja izmērs ir spēja, mēs ejam, lai atgriezties viltus.
Mēs nevaram likt neko vairāk mūsu kaudze.
Pretējā gadījumā mēs vēlamies, lai kaut uz augšu kaudze.
Kas ir "no skursteņa augšu," sākotnēji?
[Daniels] lielums 0? >> Size 0.
Kāda ir kaudze pēc tur ir viena lieta, kas kaudze augšu? Missy, jūs zināt?
[Missy] Viens. >> Izmērs ir viens, tieši tā. Jūs glabāt pievienojot ar izmēru,
un katru reizi, kad jūs esat liekot jaunā elementa pie indeksa lielumu masīvā.
Mēs varam darīt to ar šāda veida viena līnijpārvadātāju, ja tas ir jēga.
Tāpēc mēs esam ieguvuši mūsu stīgas masīvs, mēs ejam, lai piekļūtu to izmēru indeksu,
un mēs esam tikai gatavojas glabāt savu char * tur.
Paziņojums, kā tur nav virknes kopēšana notiek šeit,
Nav dinamisks sadalījumu atmiņas?
Un tad Missy audzināti ko mums tagad ir jādara,
jo mēs esam glabājas stīgu atbilstošā vietā masīvā,
un viņa teica, ka mums bija, lai pieauguma lielumu par vienu, lai mēs esam gatavi nākamajam push.
Tātad, mēs varam darīt, ka ar s.size + +.
Šajā brīdī, mēs esam uzstāja mūsu masīvs. Kāda ir pēdējā lieta, kas mums jādara?
[Studentu] Atgriešanās taisnība. >> Atgriešanās taisnība.
Tātad tas ir diezgan vienkārši, diezgan vienkāršs kods. Ne pārāk daudz.
Kad esat ietin savu galvu apkārt kā kaudze darbi,
tas ir diezgan vienkārši īstenot.
>> Tagad nākamais daļa no šī ir popping virkni nost no skursteņa.
Es esmu gatavojas sniegt jums, puiši kādu laiku strādāt pie šīs mazliet.
Tas ir gandrīz būtībā reversā, ko mēs esam darījuši šeit push.
Ko es esmu darījis, ir reāli - hmm.
Es esmu booted up ierīci nekā šeit, un ierīces,
Es esmu velk uz augšu problēma noteikti 5 specifikāciju.
Ja mēs tuvinātu šeit, mēs varam redzēt, es esmu pie cdn.cs50.net/2012/fall/psets/pset5.pdf.
Vai jums puiši lejupielādēt šo kodu, kas ir atrodas šeit, section6.zip?
Labi. Ja jums nav darījuši, darīt tieši tagad, tiešām ātri.
Es darīšu to manā termināļa logā.
Es tiešām to šeit. Yeah.
Jā, Sam? >> Man ir jautājums par to, kāpēc tu teici s.string ir amplitūdas lieluma = str?
Kas ir str? Ir definēta kaut kur pirms tam, vai - ak, kas char * str?
[Hardison] Jā, tieši tā. Tas bija arguments. >> Ak, labi. Žēl.
[Hardison] Mēs norādot virkni push collas
Otrs jautājums, kas varētu nākt klajā, ka mums nav īsti runāt par šeit bija
mēs ņēmām par pašsaprotamu, ka mums bija šo mainīgo sauc as
kas bija apjoma un pieejamā mums.
Mēs ņēmām par pašsaprotamu, ka s bija šī kaudze struktūrai.
Tāpēc atskatoties uz šo push kodu,
Jūs varat redzēt, ka mēs darām lietas ar šīs virknes, kas ieguva pagāja
bet tad visi pēkšņi, mēs piekļūt s.size, piemēram, no kurienes s nāk no?
Kodā, ka mēs ejam apskatīt sadaļā arhīvā
un tad sīkumi, ka jums tiks dara jūsu problēmu kopas,
mēs esam padarījuši mūsu steks struct globālā mainīgā
lai mēs varētu piekļūt to visiem mūsu dažādas funkcijas
bez manuāli iet tā apkārt un nodot to ar atsauci,
darīt visu šāda veida sīkumi uz to.
Mēs esam tikai krāpšanos mazliet, ja jūs, lai padarītu lietas nicer.
Un tas ir kaut mēs darām šeit, jo tas ir jautri, tas ir vieglāk.
Bieži vien jūs redzēsiet cilvēki dara, ja viņi ir viens liels datu struktūra
kas ir tiek ekspluatēti savā programmā.
>> Ejam atpakaļ pār ierīci.
Vai ikviens sekmīgi iegūt section6.zip?
Ikviens unzip to, izmantojot unzip section6.zip?
Ja jūs iet uz punktu 6 katalogs -
Aah, visas vietas -
un jūs sarakstu, kas ir šeit, jūs redzēsiet, ka jūs esat ieguvuši trīs dažāda. c failus.
Tev rindā, SLL, kas ir atsevišķi piesaistīto saraksts un kaudze.
Ja jūs atvērt stack.c,
Jūs varat redzēt, ka mēs esam ieguvuši šo struct definēto mums,
precīza struktūrai ka mēs tikko runāja par slaidiem.
Mēs esam ieguvuši mūsu globālo mainīgo, lai kaudze,
mēs esam ieguvuši mūsu push funkciju,
un tad mēs esam ieguvuši mūsu pop funkciju.
Es nolikšu kodu par push atpakaļ uz augšu slaidā šeit,
bet ko es gribētu jūs guys darīt, ir, lai cik jūsu spēju,
iet un ieviest pop funkciju.
Kad esat to īstenoja, jūs varat sastādīt to ar dara kaudze,
un tad palaist iegūtais steka izpildāmā,
un kas darbosies visu testa kodu noteikti šeit tas ir galvenais.
Un galvenais rūpējas par faktiski padarot push un pop zvani
un pārliecināties, ka viss iet caur visu labo.
Tā arī initializes kaudze izmēru tieši šeit
tāpēc jums nav jāuztraucas par inicializēšana kas.
Jūs varat pieņemt, ka tas ir bijis pareizi inicializēts
līdz brīdim, kad jūs tai piekļūt pop funkciju.
Vai ir jēga?
Tāpēc šeit mēs iet. Tur push kodu.
Es jums puiši 5 vai 10 minūtes.
Un, ja jums ir kādi jautājumi tikmēr, kamēr jūs kodēšanas,
lūdzu uzdot viņiem skaļi.
Tātad, ja jums ir uzlīmēšanu punktu, vienkārši jautājiet.
Let me know, let ikviens cits zina.
Strādā ar savu kaimiņu pārāk.
[Daniels] Mēs esam tikai īstenojot pop tieši tagad? >> Tikai pop.
Lai gan jūs varat kopēt īstenošanu push ja vēlaties
lai testēšanas strādās.
Jo tas ir grūti pārbaudīt lietas nokļūst -
vai, tas ir grūti, lai pārbaudītu popping lietas no skursteņiem, ja nav kaut kas kaudze, lai sāktu ar.
>> Kas ir pop vajadzēja būt atpakaļ? Elementa no augšas kaudze.
Tas ir paredzēts, lai iegūtu elementu nost no augšējās
un tad Samazināt izmēru kaudze,
un tagad jūs esat zaudējis elementu uz augšu.
Un tad jūs atgriezties elementu uz augšu.
[Studentu, nesaprotami]
[Hardison] Tātad, kas notiek, ja jūs to darīt? [Studentu, nesaprotami]
Kas nonāks notiek ir jūs, iespējams piekļūt vai nu
elements, kas nav inicializēts vēl, lai jūsu aprēķins
, kur pēdējais elements ir ir izslēgts.
Tātad šeit, ja pamanāt, jo push, mēs piekļūt stīgas pie s.size elementā
jo tas ir jauns indekss.
Tas ir jauns augšējās.
Tā kā pop, s.size būs nākamais telpa,
telpa, kas ir virs visiem jūsu kaudze elementiem.
Tā top-visvairāk elements nav s.size,
bet drīzāk, tas ir zem tā.
>> Otra lieta, ko darīt, ja tu - pop,
ir jums ir, lai samazinājums ir izmēru.
Ja jūs atceraties atpakaļ uz mūsu maz diagrammu tieši šeit,
tiešām, vienīgais, ko mēs redzējām notiek, kad mēs sauc pop
bija tas, ka šis lielums samazinājās, vispirms 2, tad uz 1.
Tad, kad mēs uzstājām jaunu elementu, tas varētu doties uz nepieciešamajā vietā.
[Baziliks] Ja s.size ir 2, tad nebūtu tas iet uz 2 elementu,
un tad jūs vēlaties, lai pop šo elementu off?
Tātad, ja mēs devāmies uz - >> Tātad, pieņemsim apskatīt to atkal.
Ja šī ir mūsu kaudze šajā brīdī
un mēs saucam pop,
pie kura indekss ir top-visvairāk elements?
[Baziliks] Pie 2, bet tas būs pop 3. >> Tiesības.
Tā ka, ja mūsu izmērs ir 3, bet mēs vēlamies, lai pop elementu pie 2 indeksu.
Tas, ka tipisks veida off vienu, kas jums ir ar nulles indeksāciju masīviem.
Tātad jūs vēlaties, lai pop trešo elementu, bet trešais elements ir ne pie 3 indeksā.
Un iemesls mums nav jādara, ka mīnus 1, ja mēs esam stumšanai
ir tāpēc, ka tieši tagad, jūs ievērosiet, ka top-visvairāk elements,
ja mēs push kaut kas cits uz skursteņa šajā brīdī,
mēs vēlamies, lai push to pie 3 indeksu.
Un tas tikai tā notiek, ka izmērs un indeksi rindā kad jūs stumšanas.
>> Kurš ir ieguvuši darba kaudze īstenošanu?
Tev darba kaudze vienu. Vai jums ir pop darba vēl?
[Daniels] Jā. Es tā domāju.
>> Programmas darbojas un nav SEG Faulting, tas izdrukāt?
Vai tas izdrukāt "veiksmīgām" palaižot to?
Yeah. Padarīt kaudze, palaist to, ja tā izdrukā "panākumus" un nav iet uzplaukums,
tad viss ir labi.
Labi. Iesim pa tām iekārtām tiešām ātri,
un mēs staigāt pa šo.
Ja mēs skatāmies uz to, kas notiek šeit ar pop,
Daniel, kāds bija pirmā lieta, kas jums bija?
[Daniels] Ja s.size ir lielāks par 0.
[Hardison] Labi. Un kāpēc jūs to darīt?
[Daniels] Lai pārliecinātos, ka tur bija kaut kas iekšā kaudze.
[Hardison] labi. Jūs vēlaties, lai pārbaudītu, lai pārliecinātos, ka s.size ir lielāks par 0;
citādi, ko jūs vēlaties, lai būtu notikt?
[Daniels] atgriezties null? >> Atgriezties null, tieši tā.
Tātad, ja s.size ir lielāks par 0. Tad ko mēs darīsim?
Ko mums darīt, ja kaudze nav tukša?
[Stella] Jūs Samazināt izmēru? >> Jūs Samazināt izmēru, labi.
Tātad, kā jūs to darīt? >> S.size--.
[Hardison] Lielā. Un tad ko jūs darījāt?
[Stella] Un tad es teicu atdeve s.string [s.size].
[Hardison] Lielā.
Pretējā gadījumā jūs atgriezties null. Jā, Sam?
[Sems] Kāpēc tas nav nepieciešams būt s.size + 1?
[Hardison] Plus 1? >> Jā. >> Got to.
[Sems] Es domāju, jo jūs lietojat 1 no,
tad jūs esat būs atpakaļ ne vienu, ka viņi lūdza.
[Hardison] Un tas bija tieši tas, ko mēs runājām par šo visu jautājumu no 0 indeksu.
Tātad, ja mēs tuvinātu atpakaļ vairāk nekā šeit.
Ja mēs skatāmies uz šo puisis šeit, jūs varat redzēt, ka tad, kad mēs pop,
mēs popping elementu pie 2 indeksu.
>> Tātad mēs samazināt mūsu izmēra vispirms, tad mūsu izmērs atbilst mūsu indeksu.
Ja mums nav samazināšanās lielumu, pēc tam mums ir jādara izmēru -1 un tad samazināšanās.
Lieliski. Viss labi?
Kādi jautājumi par šo?
Ir dažādi veidi, lai rakstītu šo kā labi.
Patiesībā, mēs varam kaut ko darīt, pat - mēs varam darīt vienu slāni.
Mēs varam darīt vienu līniju atdevi.
Tātad, mēs varam reāli samazināšanās, pirms mēs atgriežamies darot to.
Tā liekot - pirms s.size.
Tas padara līnija tiešām blīvs.
Ja atšķirība starp -. Lielumu un s.size--
ir tāds, ka šis postfix - viņi to sauc postfix jo - nāk pēc s.size--
nozīmē, ka s.size tiek novērtēta par atrast indeksu vajadzībām
kā tas ir šobrīd, kad šī līnija ir izpildīts,
un tad tas - notiek pēc līnijas izpaužas izpildīts.
Pēc pie indeksa s.size elements ir pieejama.
Un tas nav tas, ko mēs gribam, jo ​​mēs vēlamies, lai samazināšanās varētu notikt pirmās.
Othewise, mēs ejam, lai būtu piekļuvei masīvs, efektīvi, no robežas.
Mēs ejam, lai būtu piekļuvei elementu virs viena, ka mēs tiešām vēlamies, lai piekļūtu.
Yeah, Sam? >> Vai tas ātrāk vai izmantot mazāk RAM, lai vienā rindā vai ne?
[Hardison] Godīgi sakot, tas tiešām ir atkarīgs.
[Sems, nesaprotami] >> Jā, tas ir atkarīgs. Jūs varat darīt kompilators trikus
lai iegūtu kompilators atzīt, ka, parasti, es iedomāties.
>> Tātad mēs esam minēts mazliet par šo kompilators optimizācijas sīkumi
ka jūs varat darīt, apkopojot,
un tas ir tāda veida lieta, ka kompilators varētu izrēķināt,
piemēram ak, hey, varbūt es varu darīt visu vienā operācijā,
pretstatā iekraušanas izmēra mainīgo no RAM,
decrementing to, uzglabājot to atpakaļ, un tad ielādējot to atpakaļ vēlreiz
apstrādāt pārējā šo operāciju.
Bet parasti, nē, tas nav tāda veida lieta
kas notiek, lai padarītu savu programmu ievērojami ātrāk.
Vai ir vēl kādi jautājumi par skursteņi?
>> Tik stumšanas un popping. Ja jūs puiši vēlas izmēģināt hakeru valodā,
ko mēs esam darījuši hakeru izdevumā ir faktiski gājusi
un padarīja šo kaudze aug dinamiski.
Uzdevums ir galvenokārt izveidota šeit push funkciju,
izdomāt, kā padarīt, ka masīvu augt
kā saglabāt stumšanas vairāk un vairāk elementus, lai kaudze.
Tas tiešām nav pārāk daudz papildu kodu.
Tikai aicinājums - jums ir jāatceras, lai saņemtu zvanus uz malloc tur pareizi,
un tad izdomāt, kad jūs gatavojas zvanīt realloc.
Tas ir jautri izaicinājums, ja jūs interesē.
>> Bet pagaidām, pāriesim, un parunāsim par rindām.
Ritinātu šeit.
Rinda ir cieša brālis kaudze.
Tātad kaudze, lietas, kas tika izsludināts pagājušajā
bija pirmās lietas, lai pēc tam varētu iegūt.
Mēs esam ieguvuši šo pēdējais iekšā, pirmais ārā, vai LIFO, pasūtot.
Tā kā rindā, kā jūs gaidījāt no brīža, kad jūs esat stāv rindā,
pirmā persona, lai saņemtu rindā, pirmā lieta, lai nokļūt rindā,
ir pirmā lieta, kas izpaužas iegūti no rindas.
Rindas ir arī bieži izmanto, kad mums ir darīšana ar grafiku,
tāpat kā mēs runājām par īsumā ar skursteņi,
un rindas ir arī ērts ķekars citas lietas.
Viena lieta, kas nāk klajā bieži cenšas saglabāt, piemēram,
sakārtoti elementu saraksts.
Un jūs varat darīt ar masīvu. Jūs varat saglabāt sakārtoti sarakstu ar lietām masīvā,
bet kur tas izpaužas grūts, tad jūs vienmēr ir jāatrod
piemērota vieta, lai ievietotu nākamo lieta.
Tātad, ja jums ir masīva skaitļiem, 1 līdz 10,
un tad jūs vēlaties, lai paplašinātu ka visiem skaitļiem no 1 līdz 100,
un jūs saņemat šos skaitļus nejaušā secībā un cenšas saglabāt visu
sakārtoti, kā jums iet cauri, jūs galu galā, kam darīt daudz mainās.
Ar dažu veidu rindām un noteiktu veidu notikušo datu struktūras,
Jūs faktiski var saglabāt to diezgan vienkārši.
Jums nav pievienot kaut ko un tad pārgrupēšanās viss katru reizi.
Ne arī jums ir jādara daudz novirzot no iekšējiem elementiem apkārt.
Kad mēs skatāmies uz rindā, jūs redzat, ka - arī queue.c sadaļā kodu -
the struktūrai ka esam radījuši jums ir patiešām līdzīgs struct ka mēs deva jums kaudze.
>> Ir viens izņēmums, un ka viens izņēmums
ir tas, ka mums ir šī papildu skaitlis sauc galvu,
un galva šeit ir, lai sekotu galvas rindā,
vai pirmais elements rindā.
Ar kaudze, mums bija iespēja sekot līdzi elementa ka mēs par to iegūtu,
vai augšējās, izmantojot tikai izmēru,
tā kā ar rindā, mēs esam, kam, lai risinātu ar pretējiem galiem.
Mēs cenšamies, lai sadiegšana lietas uz beigās, bet tad atgriezties lietas no priekšpuses.
Tik efektīvi, ar galvu, mums ir indeksu sākumā rindā,
un izmērs dod mums indeksu rindas beigās
lai mēs varētu iegūt lietas no galvas un pievienot lietas uz astes.
Tā kā ar steku, mums bija tikai kādreiz nodarbojas ar augšējās.
Mums nekad nav bijis, lai piekļūtu apakšā skursteņa.
Mēs tikai pievienot lietas uz augšu un bija lietas nost no augšas
tāpēc mums nav nepieciešams, ka papildu lauku iekšpusē mūsu struct.
Vai tas vispār ir jēga?
Labi. Jā, Šarlote? [Charlotte, nesaprotami]
[Hardison] Tas liels jautājums, un tas bija viens, kas nāca klajā ar lekciju.
Varbūt ejot cauri dažiem piemēriem parādīsim, kāpēc
Mēs nevēlamies, lai izmantotu stīgām [0] kā vadītājs rindā.
>> Tātad, iedomāties, ka mums ir mūsu rindā, mēs ejam, lai izsauktu to rinda.
Sākumā, kad mēs esam tikai instantiated to,
kad mēs esam tikko paziņoja, mēs esam nav inicializēts neko.
Tas viss atkritumu. Tātad, protams, mēs vēlamies, lai pārliecinātos, ka mēs sāktu
gan izmēru un galvas lauki ir 0, kaut saprātīgi.
Mēs varētu arī iet uz priekšu un null izklāstīti elementi mūsu rindā.
Un, lai padarītu šo diagramma fit, ievērosiet, ka tagad mūsu rindas var būt tikai trīs elementi;
tā kā mūsu kaudze varētu turēt četrus, mūsu rindas var būt tikai trīs.
Un tas ir tikai, lai diagramma fit.
Pirmā lieta, kas notiek šeit ir mums ierindod virkni "hi".
Un tāpat kā mēs to darījām ar skursteņiem, nekas briesmīgi atšķirīgs šeit,
mēs mest virkni plkst stīgām [0] un pieauguma mūsu izmēra līdz 1.
Mēs ierindod "atā", tā izpaužas likts uz.
Tātad tas izskatās kaudze par lielāko daļu.
Mēs sākām off šeit, jauns elements, jauns elements, izmērs tur iet uz augšu.
Kas notiek šajā brīdī, kad mēs vēlamies dequeue kaut ko?
Ja mēs vēlamies dequeue, kas ir elements, ko mēs vēlamies dequeue?
[Baziliks] stīgas [0]. >> Zero. Tieši labi, baziliks.
Mēs vēlamies, lai atbrīvotos no pirmās virknes, šo vienu, "Hi".
Tātad, kāds bija cita lieta, ka mainījies?
Pamanīt, kad mēs popped kaut nost no skursteņa, mēs vienkārši mainīt izmēru,
bet šeit, mēs esam ieguvuši pāris lietas, kas mainās.
Ne tikai izmēru maiņu, bet galva izmaiņas.
Šis ir došanās atpakaļ uz Šarlotes punktu agrāk:
kāpēc mums ir šī galva, kā arī?
Vai ir kāda jēga tagad, Šarloti? >> Veids.
[Hardison] veids? Tātad, kas notika, kad mēs dequeued?
Ko galvu darīt tagad ir interesanti?
[Šarlote] Ak, jo tas mainījies - labi. Es saprotu.
Jo galva - ja galva ir vērsta uz izmaiņām attiecībā uz atrašanās vietu.
Tas vairs vienmēr nulle indekss vienu. >> Jā, tieši tā.
Kas notika bija, ja dequeueing augstu elementu
tika darīts, un mums nebija šo galvas lauks
jo mēs vienmēr aicinām šo virkni ar 0 indeksa vadītājs mūsu rindā,
tad mēs būtu novirzīt pārējo rindā uz leju.
Mēs ir novirzīt "atā" no no virknes [1], līdz pat stīgu instrumentiem [0].
Un virknes [2] līdz stīgas [1].
Un mēs gribētu to darīt, lai visu sarakstu elementiem,
viss masīvs elementiem.
Un, kad mēs darām to ar masīvu, kas izpaužas ļoti dārgi.
Tātad šeit, tas nav liels darījumu. Mums vienkārši ir trīs elementi mūsu masīvā.
Bet, ja mums bija tūkstoš elementu rinda vai miljons elementus,
un tad visi pēkšņi, mēs sāktu īstenot ķekars dequeue aicina visus pa apli,
lietas ir patiešām gatavojas palēnināt, pārejot viss uz leju nepārtraukti.
Jūs zināt, novirzīt 1, pāreju ar 1 maiņā 1, maiņu 1.
Tā vietā, mēs izmantojam šo galvu, mēs to saucam par "rādītājs", pat ja tas nav īsti rādītājs
šaurā nozīmē, tas nav rādītājs tips.
Tas nav int * vai char * vai kaut kā tā.
Bet tas norādot, vai norādot galvu mūsu rindā. Yeah?
>> [Studentu] Kā dequeue zina tikai pop off kāds ir pie galvas?
[Hardison] Kā dequeue zināt, kā pop off kāda ir pie galvas? >> Pareizi, jā.
>> Kas tas meklē ir tikai neatkarīgi galva lauks ir iestatīts uz.
Tātad šajā pirmajā gadījumā, ja mēs skatāmies šeit,
Mūsu galvenais ir 0, indekss 0. >> Tiesības.
[Hardison] Tātad tā vienkārši saka labi, labi, elements ir 0 indeksu, virkne "čau",
ir elements pie galvas mūsu rindā.
Tāpēc mēs esam gatavojas dequeue ka puisis.
Un tas būs elements, kas izpaužas atgriezās zvanītāju.
Jā, Saad? >> Tātad galva būtībā nosaka fondu - kur jūs gatavojas indekss to?
Tas ir sākums no tā? >> Jā. >> Labi.
[Hardison] Tas kļūst jaunais sākums mūsu masīvs.
Tātad, ja jūs dequeue kaut ko, viss, kas jums jādara, ir piekļūt elementu pašā indeksa q.head,
un ka būs elements, kas jūs vēlaties, lai dequeue.
Jums ir arī samazinājums ir izmēru.
Mēs redzēsim, kas mazliet, ja lietas iegūt nedaudz grūts ar šo.
Mēs dequeue, un tagad, ja mēs ierindod atkal,
ja mēs ierindod?
Kur nākamais elements iet mūsu rindā?
Saka, ka mēs vēlamies, lai ierindod virkni "CS".
Kurā indekss būs tas iet? [Studenti] stīgas [2]. >> Divi.
Kāpēc 2 un ne 0?
[Baziliks] Jo tagad galva ir 1, tā ka tāpat sākuma sarakstā?
[Hardison] labi. Un ko apzīmē saraksta beigām?
Kādi bija mums izmanto, lai apzīmētu beigas mūsu rindā?
Galva ir galva mūsu rindā, sākums mūsu rindā.
Kāda ir mūsu rindā beigas? [Studentiem] izmērs. >> Izmērs, tieši tā.
Tātad mūsu jauni elementi iet pie lieluma, un elementi, kas mums pacelties nāk off galvu.
Kad mēs ierindod nākamo elementu, mēs esam liekot to pie lieluma.
[Studentu] Pirms jūs nodot, ka, lai gan, izmērs bija 1, labi?
[Hardison] labi. Tātad ne gluži izmēru. Izmērs +, nevis 1, bet + galva.
Jo mēs shifted viss ar galvu summu.
Tātad šeit, tagad mēs esam ieguvuši rindā 1 izmērs, kas sākas ar 1 indeksu.
Aste ir indekss 2. Jā?
>> [Studentu] Kas notiek, ja jūs dequeue stīgas [0], un stīgām "nišas atmiņā
tikai iegūt iztukšotas, būtībā, vai vienkārši aizmirst?
[Hardison] Jā. Šajā ziņā mēs esam tikai aizmirstot tos.
Ja mēs uzglabātu kopijas tām -
daudz datu struktūras bieži glabāt savus kopijas elementiem
tā ka persona, kas vada datu struktūru, nav jāuztraucas
par to, kur visi šie norādes iet.
Datu struktūra tur uz visu, tur uz visiem eksemplāriem,
lai pārliecinātos, ka viss turpinās pienācīgi.
Tomēr šajā gadījumā šie dati struktūras tikai, vienkāršības,
nav padarīt kopijas par jebko, kas mēs esam glabāšanai tiem.
[Studentu] Tātad tas ir nepārtraukts masīvs -? >> Jā.
Ja mēs atskatāmies uz to, ko definīcija bija par šo struktūru, tas ir.
Tas ir tikai standarta masīvs kā jūs esat redzējuši,
masīvs char * s.
Vai tas -? >> Jā, man bija tikai jautājums
ja jūs, iespējams darbināt no atmiņas, lai zināmā mērā,
ja jums ir visas šīs tukšās vietas jūsu masīvs?
[Hardison] Jā, tas ir labs punkts.
>> Ja mēs skatāmies uz to, kas ir noticis tagad, šajā brīdī,
mēs esam piepilda mūsu rindā, tas izskatās.
Bet mēs neesam īsti piepilda mūsu rinda
jo mums ir rinda, kas ir izmērs 2, bet tas sākas pie 1 indekss,
jo tas ir, ja mūsu galva rādītājs ir.
Kā jums bija sakot, ka šis elements ir stīgas [0], ir 0 indeksu, nav īsti tur.
Tas nav mūsu rindā vairs.
Mēs vienkārši nav apnikt iet un pārrakstīt to, kad mēs dequeued to.
Tātad, pat ja izskatās, ka mēs esam pietrūkt atmiņas, mums tiešām nav.
Tas vietas ir pieejamas, lai mēs izmantot.
Piemērots uzvedība, ja mēs mēģinātu un pirmais dequeue kaut
piemēram, "atā", kas pop atā off.
Tagad mūsu rinda sākas pie 2 indeksu un ir 1 izmēru.
Un tagad, ja mēs mēģinātu ierindod kaut jauna, teiksim 50,
50 vajadzētu iet šajā vietā pie 0 indeksu
jo tas joprojām ir pieejams par mums. Jā, Saad?
[Saad] Vai tas notiks automātiski?
[Hardison] Tas nenotiek gluži automātiski. Jums ir darīt to math
lai tā darbotos, bet būtībā tas, ko mēs esam darījuši, ir, mēs esam tikai aptīt.
[Saad] Un tas ir labi, ja tas ir caurumu vidū tā?
[Hardison] Tas ir, ja mēs varam padarīt matemātikas darboties pareizi.
>> Un izrādās, ka tas tiešām nav tik grūti to darīt ar mod operatoru.
Tātad tāpat kā mēs to darījām ar Cēzars un kriptogrāfiskā sīkumi,
izmantojot mod, mēs varam iegūt lietas, lai wrap ap un tur notiek
apkārt un apkārt un apkārt ar mūsu rindā,
tur, ka galva rādītājs pārvietojas.
Pamanīt, ka izmērs ir vienmēr ievērojot vairākus elementus patiešām atrodas rindā.
Un tas ir tikai galva rādītājs, kas uztur riteņbraukšana cauri.
Ja mēs skatāmies uz to, kas noticis šeit, ja mēs ejam atpakaļ uz sākumu,
un jūs tikai skatīties, kas notiek ar galvu
kad mēs ierindod kaut ko, nekas noticis ar galvu.
Kad mēs enqueued kaut kas cits, nekas noticis ar galvu.
Tiklīdz mēs dequeued kaut ko, galva iet uz augšu pa vienam.
Mēs enqueued kaut ko, nekas nenotiek uz galvas.
Kad mēs dequeue kaut ko, visi pēkšņi galva izpaužas palielināts.
Kad mēs ierindod kaut ko, nekas nenotiek uz galvas.
>> Kas notiktu, šajā brīdī, ja mēs dequeue kaut vēlreiz?
Jebkurš domas? Kas notiks ar galvu?
Kas notiek ar galvu
ja mēs dequeue kaut ko citu?
Galva šobrīd ir 2 indeksu,
kas nozīmē, ka rindā vadītājs ir stīgas [2].
[Studentu] Kurš atgriež 0? >> Tas būtu atgriezties uz 0. Tas būtu wrap atpakaļ apkārt, tieši tā.
Līdz šim katru reizi mēs sauc dequeue, mēs esam pievienojot vienu uz galvas,
pievienot vienu uz galvas, pievieno vienu uz galvas, pievieno vienu uz galvas.
Tiklīdz šī galva rādītājs izpaužas ar pēdējo indeksa mūsu masīvs,
tad mums ir wrap to atpakaļ ap sākumā, iet atpakaļ uz 0.
[Šarlote] Kas nosaka spēju rindas kaudze?
[Hardison] Šajā gadījumā, mēs esam tikko izmantojot # noteikta nemainīga. >> Labi.
[Hardison] Jo faktiskās. C failu, jūs varat iet un piemēslot ar to mazliet
un dara to tik liels vai maz, cik vēlaties.
[Šarlote] Tātad, ja jūs esat padarot to rinda, kā jūs padarīt datoru zina
cik liels vēlaties kaudze būt?
[Hardison] Tas ir liels jautājums.
Ir veidos pāris. Viens no tiem ir vienkārši definēt uzreiz
un saka, tas būs rinda, kas ir 4 elementi vai 50 elementiem vai 10000.
Otrs veids ir darīt to, ko hakeru izdevums ļaudīm dara
un izveidot funkciju, lai jūsu rindas aug dinamiski, jo vairāk lietas iegūt pievienots iekšā
>> [Šarlote] Tātad, lai iet ar pirmo variantu, ko sintakse jūs izmantojat
pateikt programmu, kāda ir rindā izmērs?
[Hardison] Ah. Tāpēc pieņemsim iegūt no šīs.
Es esmu vēl stack.c šeit, tāpēc es esmu tikai gatavojas ritinātu uz augšu uz augšu šeit.
Vai jūs varat redzēt šīs tiesības šeit? Tas ir # define jaudu 10.
Un tas ir gandrīz tieši tā pati sintakse, ka mums ir par rindā.
Izņemot rindā, mēs esam ieguvuši, ka papildu struct lauku šeit.
[Šarlote] Ak, es domāju jaudas nozīmēja spēju virknē.
[Hardison] Ah. >> Ka tas ir maksimālais garums vārda. >> Got to.
Yeah. Jauda - šis ir lielisks punkts.
Un tas ir kaut kas ir grūts,
jo tas, ko mēs esam deklarēti šeit ir masīvs char * s.
Masīvs norādes.
Tas ir masīvs chars.
Tas ir iespējams, ko jūs esat redzējuši, kad jūs esat deklarējot savu buferi failu I / O,
kad jūs esat radot stīgas manuāli uz skursteņa.
Tomēr, ko mēs esam ieguvuši šeit ir masīvs char * s.
Tātad, tas ir masīvs norādes.
Patiesībā, ja mēs atkal tālināt un mēs skatāmies, kas notiek šeit
prezentācijā, jūs redzat, ka faktiskie elementi, raksturs dati
netiek glabāti masīvs pati.
Kas glabājas mūsu masīva šeit ir norādes uz rakstzīmju datiem.
Labi. Tāpēc mēs esam redzējuši, kā no rindā lielums ir tāpat kā ar steku,
lielums vienmēr respektē elementu skaitu patlaban rindā.
Pēc tam 2 enqueues, izmērs ir 2.
Pēc tam, kad dequeue izmērs ir tagad 1.
Pēc tam vēl ierindod lielums ir atpakaļ līdz 2.
Tātad lielums noteikti respektē elementu skaitu rindā,
un tad galva tikai tur velosipēdu.
Pats no 0-1-2, 0-1-2, 0-1-2.
Un katru reizi, kad mēs saucam dequeue, galvas rādītājs izpaužas palielināts līdz nākamajam indeksu.
Un, ja galva ir aptuveni iet pāri, tas cilpas atkal ap 0.
Tātad ar to, mēs varam rakstīt dequeue funkciju.
Un mēs ejam atstāt ierindod funkciju jūs puiši, lai īstenotu vietā.
>> Kad mēs dequeue elementu no mūsu rindā,
kāda bija pirmā lieta, ka Daniels bija, kad mēs sākām rakstīt pop funkciju skursteņi?
Ļaujiet man dzirdēt no kāds, kurš nav runājis vēl.
Let 's redzēt, Saad, vai tu atceries, ko Daniels darīja kā pirmā lieta, kad viņš rakstīja pop?
[Saad] Tur bija, tā bija - >> viņš testē kaut.
[Saad] Ja izmērs ir lielāks par 0. >> Tieši tā.
Un kāda bija, ka testēšana?
[Saad] Tas bija testēšana, lai redzētu, vai tur ir kaut kas iekšā masīvā.
[Hardison] Jā. Tieši tā. Tātad, jūs nevarat pop neko no skursteņa, ja tas ir tukšs.
Tāpat jūs nevarat dequeue neko no rindas, ja tas ir tukšs.
Kas ir pirmā lieta, ko mums vajadzētu darīt mūsu dequeue funkciju šeit, jūs domājat?
[Saad] Ja izmērs ir lielāks par 0? >> Jā.
Šajā gadījumā, es esmu faktiski tikai pārbaudīt, lai redzētu, vai tas ir 0.
Ja tas ir 0, mēs varam atgriezties null.
Bet precīzi tāda pati loģika.
Un pieņemsim turpināt ar šo.
Ja izmērs nav 0, kur ir elements, ko mēs vēlamies dequeue?
[Saad] Pie galvas? >> Tieši tā.
Mēs varam vienkārši izraut pirmais elements mūsu rindā
piekļūstot elementu pie galvas.
Nekas traks.
Pēc tam, ko mums vajadzētu darīt? Kas ir noticis?
Kāds bija cita lieta, ka mēs runāja par dequeue?
Divas lietas ir notikt, jo mūsu rinda ir mainījusies.
[Daniels] Samazināt izmēru. >> Mums ir samazināt izmēru, un palielināt galvu? Tieši tā.
Lai palielinātu galvu, mēs varam ne tikai akli palielināt galvu, atcerēties.
Mēs nevaram vienkārši darīt queue.head + +.
Mums ir arī šī mod ar jaudu.
Un kāpēc mēs mod ar jaudu, Stella?
[Stella] Jo tas ir wrap apkārt. >> Tieši tā.
Mēs mod ar jaudu, jo tā ir wrap atpakaļ ap 0.
Tāpēc tagad, šajā brīdī, mēs varam darīt to, ko Daniels teica.
Mēs varam Samazināt izmēru.
Un tad mēs varam vienkārši atgriezties elements, augšpusē rindā.
Tas izskatās veida gnarly sākumā. Jums varētu būt jautājums. Žēl?
>> [Sems] Kāpēc ir pirmais augšpusē rindā? Ja tas, ka iet?
[Hardison] Tas nāk no ceturtās līnijas no apakšas.
Kad mēs pārbaudīt, lai pārliecinātos, ka mūsu rinda nav tukša,
Mēs izraut char * Pirmkārt, mēs izvelciet elements, kas sēž pie galvas indekss
Mūsu masīvs, mūsu Stīgu masīva, >> un zvanu, ka pirmais?
[Hardison] Un mēs to saucam pirmās. Yeah.
Vienkārši sekot līdzi, ka, kāpēc jūs domājat, mums bija darīt?
[Sems] Katrs Pirmais tikai atgriežas q.strings [q.head]? >> Jā.
>> Jo mēs darām šo mainot q.head ar mod funkciju,
un tur nav veids, kā to darīt laikā atgriezes līnijai arī.
[Hardison] Tieši tā. Tu esi spot on. Sam ir pilnīgi spot on.
Iemesls mums bija izraut pirmais elements mūsu rindā un uzglabāt to mainīgo
ir tāpēc, ka šo līniju, kur mums bija tikko q.head,
tur mod operators tur nav kaut kas, ko mēs varam darīt
un ir tā stājas spēkā uz galvas bez - vienā rindā.
Tāpēc mums tiešām ir izraut pirmo elementu, tad pielāgot galvas,
pielāgot izmēru, un pēc tam atgriezties elementu ka mēs izvilka.
Un tas ir kaut kas, mēs redzēsim nākt klajā vēlāk ar
saistīti saraksti, kā mēs spēlēt aptuveni ar tiem.
Bieži, kad jūs atbrīvojot vai atsavināt saistītas sarakstos
Jums ir nepieciešams atcerēties nākamo elementu, nākamais rādītājs par saistīts saraksts
pirms izmešanas pašreizējo.
Jo citādi jūs mest prom informāciju par to, kas palicis pāri sarakstā.
Tagad, ja jūs doties uz savu ierīci, jūs atvērt queue.c--x no šīs.
Tātad, ja es atvērt queue.c, ļaujiet man zoom šeit,
Jūs redzēsiet, ka jums ir līdzīgi izskata failu.
Līdzīga izskata fails, ko mums bija agrāk ar stack.c.
Mēs esam ieguvuši mūsu struct par rindā definēta tāpat kā mēs redzējām uz slaidiem.
>> Mums ir mūsu ierindod funkciju, kas ir, lai jūs varētu darīt.
Un mums ir dequeue funkcija šeit.
The dequeue funkciju failā tiek īstenoti,
bet es nolikšu to atpakaļ uz augšu uz PowerPoint, lai jūs varat ierakstīt to, ja vēlaties.
Tāpēc par nākamajiem 5 minūtēm vai tamlīdzīgi, jūs puiši strādā pie ierindod
kas ir gandrīz tieši pretējs dequeue.
Jums nav pielāgot galvu, kad jūs enqueueing, bet ko darīt, jums ir pielāgot?
Lielumu. Tātad, ja jūs Enqueue, galvas paliek neskarta, izmērs izpaužas mainījusies.
Bet tas prasa mazliet - jums būs spēlēt aptuveni ar šo mod
izdomāt, ko tieši indeksa jaunais elements ir jāievieto pie.
Tāpēc es došu jums, puiši mazliet, ielieciet dequeue atpakaļ uz augšu slaidā
Un, kā jūs puiši ir jautājumi, kliegt tos tā, ka mēs varam
visi runā par tiem kā grupa.
Arī ar izmēru jums Don '- kad jūs pielāgot izmēru, jūs vienmēr varat vienkārši -
Vai jums ir mod izmēru jebkad? [Daniels] Nē >> Jums nav mod izmēru, labi.
Jo izmērs būs vienmēr, ja jūs esat nokļuvis - pieņemot, ka jūs pārvaldīt lietas pareizi,
lielums vienmēr būs no 0 līdz 3.
Kur jums ir mod, kad jūs darāt ierindod?
[Studentu] Tikai galvas. >> Tikai galvu, tieši tā.
Un kāpēc jums ir mod nemaz Rindu?
Ja ir situācija, kurā jūs ir mod?
[Studentu] Ja jums ir sīkumi pie telpām, piemēram, pie telpām 1 un 2,
un tad jums nepieciešams pievienot kaut ar 0.
[Hardison] Jā, tieši tā. Tātad, ja jūsu galva rādītājs ir pašās beigās,
vai ja jūsu izmērs plus jūsu galva ir lielāks, vai drīzāk, gatavojas aptīšanas rindā.
>> Tātad šajā situācijā, ka mēs esam ieguvuši šeit slaidā tieši tagad,
ja es gribu ierindod kaut tiesības tagad,
Mēs vēlamies ierindod kaut pie 0 indekss.
Tātad, ja paskatās kur 50 iet, un es aicinu ierindod 50,
tā iet uz leju tur apakšā. Tā iet indeksu 0.
Tas aizvieto "hi", kas jau bija dequeued.
[Daniels] Vai jums rūpēties par ka dequeue jau?
Kāpēc tas jādara kaut ar galvu ierindod?
[Hardison] Ak, lai jūs neesat groza galvu, piedodiet.
Bet jums ir izmantot mod operatoru kad jūs piekļūstot
elements, kas jūs vēlaties, lai ierindod kad jūs piekļūstot
nākamais elements savā rindā.
[Baziliks] Es to nedarīju, un es saņēmu "veiksmi" par tur.
[Daniels] Ak, es saprotu, ko tu runā.
[Hardison] Tātad jūs didn't - jūs vienkārši darīja q.size?
[Baziliks] Jā. Es tikko mainīts puses, man nav neko ar galvu.
[Hardison] Jums nav faktiski ir reset galvu būt jebkas,
bet, kad tu indekss uz stīgas masīvs,
Jums tiešām ir iet uz priekšu un aprēķināt, kur nākamais elements ir,
jo vica kaudzīti, nākamais elements jūsu kaudze vienmēr bija
pie indeksa, kas atbilst izmēram.
Ja mēs atskatāmies uz augšu mūsu kaudze push funkciju,
mēs vienmēr varētu trinkšķis mūsu jaunā elementa labi pie indeksa lieluma.
Tā kā ar rindā, mēs nevaram darīt
jo, ja mēs esam šajā situācijā,
ja mēs enqueued 50 mūsu jauno stīgu varētu iet labi pie virknes [1]
ko mēs negribam darīt.
Mēs vēlamies, lai būtu jauna stīgu iet pie 0 indekss.
>> Vai kāds - jā? [Studentu] Man ir jautājums, bet tas nav īsti saistīts.
Ko tas nozīmē, kad kāds piezvana kaut kas līdzīgs pred rādītājs?
Kas ir tas, ka nosaukums īss? Es zinu, tas ir tikai nosaukums.
[Hardison] pred rādītājs? Pieņemsim redzēt. Kādā kontekstā?
[Studentu] Tas bija par ieliktņa. Es varu lūgt jums vēlāk, ja jūs vēlaties
jo tas nav īsti saistīts, bet es tikai -
[Hardison] No Dāvida ierakstīt kodu no lekciju?
Mēs varam pull ka augšu un runāt par to.
Mēs runājam par to, ka nākamais, kad mēs nokļūt saistīto saraksti.
>> Tāpēc pieņemsim tiešām ātri apskatīt to, ko Enqueue funkcija izskatās.
Kas bija pirmā lieta, ka cilvēki centās darīt savā ierindod rindā? Šajā rindā?
Līdzīgs tam, ko jūs par kaudze stumšanas.
Ko jūs darījāt, Stella?
[Stella, nesaprotami]
[Hardison] Tieši tā. Ja (q.size == jauda) -
Man vajag, lai manu bikšturi pareizajā vietā - atgriezties viltus.
Tuvināt mazliet. Labi.
Tagad to, kas ir nākamā lieta, kas mums bija jādara?
Tāpat kā ar steku, un ievietots īstajā vietā.
Un tā, kādi bija īstā vieta, lai ievietotu šo?
Ar steku tā bija indekss lielums, ar šo tas nav gluži tā.
[Daniels] Man ir q.head--vai - >> q.strings? >> Jā.
q.strings [q.head + q.size Mod JAUDA]?
[Hardison] Mēs, iespējams, vēlas, lai iekavas ap šo
lai mēs esam iegūt atbilstošu prioritāti un tā ka cleart visiem.
Un noteikt, ka vienāda? >> Str? >> Str. Lieliski.
Un tagad, kas ir pēdējā lieta, kas mums jādara?
Tāpat kā mēs darījām kaudze. >> Pieaugums lielumu? >> Pieaugums lielumu.
Uzplaukums. Un tad, jo startera kodu tikko atgriezies viltus pēc noklusējuma,
Mēs gribam mainīt šo taisnība, ja visi iet cauri, un viss iet labi.
Labi. Tas ir daudz informācijas par sadaļā.
Mēs esam ne gluži galā. Mēs vēlamies runāt tiešām ātri par atsevišķi saistītiem sarakstiem.
Es nolikšu šo augšu, lai mēs varētu doties atpakaļ uz to vēlāk.
Bet iesim atpakaļ uz mūsu prezentāciju, lai tikai dažus vairāk slaidiem.
Tātad Enqueue ir TODO, tagad mēs esam darījuši.
>> Tagad pieņemsim apskatīt atsevišķi saistītiem sarakstiem.
Mēs runājām par šiem nedaudz vairāk lekciju.
Cik daudzi no jums, puiši ieraudzīja demo kur mums bija cilvēki
neveikli norādot uz otru un saimniecība numuriem? >> Man bija tā.
>> Ko jūs puiši domājat? Izdarīju, cerams atmaskot šos mazliet?
Ar sarakstu, izrādās, ka mēs galā ar šāda veida, ka mēs ejam, lai izsauktu mezglu.
Tā kā saskaņā ar rindā un kaudze mums bija structs ka mēs gribētu zvanu rindas, kas kaudze,
Mums bija šīs jaunās rindas kaudze veidu,
šeit saraksts ir tiešām tikai veido ķekars mezgliem.
Tādā pašā veidā, ka stīgas ir tikai ķekars chars visu ierindots blakus viens otram.
Saistīts saraksts ir tikai mezglu un citu mezglu un citu mezglu un citu mezglu.
Un nevis smashing visus mezglus kopā un uzglabājot tos contiguously
visi blakus viens otram atmiņā,
ņemot šo nākamo rādītāju ļauj mums uzglabāt mezgliem kur, pēc nejaušības principa.
Un tad veida stiepļu tos visus kopā, lai norādīt no viena uz nākamo.
>> Un kāda bija liela priekšrocība, ka tas bija vairāk nekā masīvā?
Virs uzglabāšanas viss contiguously tikai iestrēdzis blakus viens otram?
Jūs atceraties? Yeah? >> Dinamiskā atmiņas sadale?
>> Dinamiskā atmiņas sadale, kādā nozīmē?
[Studentu] Jo kas var glabāt padarot to lielāku un jums nav, lai pārvietotu visu jūsu masīvs?
[Hardison] Tieši tā. Tātad ar masīvu, ja jūs vēlaties, lai izveidotu jaunu elementu vidū to,
jums ir novirzīt visu, lai padarītu telpu.
Un, tāpat kā mēs runājām par ar rindā,
tāpēc mēs turpinām šo galvas rādītāju,
tāpēc, ka mēs neesam pastāvīgi mainās lietas.
Jo tas izpaužas dārgi, ja jūs esat ieguvuši lielu masīvu
un jūs pastāvīgi dara šīs izlases iestarpinājumiem.
Tā kā ar sarakstu, viss, kas jums jādara, ir mest to uz jaunu mezglu,
pielāgot norādes, un jūs darīts.
Ko sūkā par šo?
Neņemot vērā faktu, ka tas nav tik viegli strādāt ar tik masīvu? Yeah?
[Daniels] Nu, es domāju, tas ir daudz grūtāk piekļūt konkrētu elementu, kas saistīti sarakstā?
[Hardison] Jūs varat ne tikai lēkt uz patvaļīgu elementu vidū jūsu saistīts saraksts.
Kā jūs to darīt to vietā? >> Jums ir soli pa visu lieta.
[Hardison] Jā. Jums ir jāiet cauri vienam laikā, vienā laikā.
Tas ir milzīgs - tas ir sāpes.
Kas cits - tur ir cita krišanu uz šo.
[Baziliks] Jūs nevarat iet uz priekšu un atpakaļ? Jums ir iet vienā virzienā?
[Hardison] Jā. Tātad, kā mēs risinām, ka reizēm?
[Baziliks] Divkārt piesaistīta sarakstos? >> Tieši tā. Ir divkārt saistīti saraksti.
Ir arī - žēl?
>> [Sems] Vai tas pats, izmantojot pred lieta, ka -
Es tikko atcerējos, nav tas, kas ieteik lieta ir?
Vai nav, ka starp divkārt un atsevišķi?
[Hardison] Apskatīsim, ko tieši viņš dara.
Tāpēc šeit mēs iet. Lūk saraksts kodu.
Šeit mums ir predptr, kas šeit. Vai tas, ko tu runā?
Tā tas bija - viņš atbrīvojot sarakstu un viņš mēģina saglabāt rādītāju uz to.
Šī nav divkārt, atsevišķi Linked-saraksti.
Mēs varam runāt vairāk par šo vēlāk, jo tas runā par atbrīvojot sarakstu
un es vēlos parādīt dažas citas lietas pirmās.
bet tas ir tikai - tas atceroties vērtību PTR
[Studentu] Ak, tas ir Iepriekšējā rādītājs? >> Jā.
Lai mēs varētu pēc tam pieauguma PTR pati pirms mēs tad bez kāda predptr ir.
Jo mēs nevaram brīvi PTR un tad zvana PTR = PTR nākamais, vai ne?
Tas būtu slikti.
Tātad, pieņemsim redzēt, atpakaļ uz šo puisis.
>> Otra Slikti par sarakstiem ir tas, ka tā ar masīvu
Mums vienkārši ir visi elementi paši kaudzē blakus viens otram,
šeit mēs arī esam ieviesuši šo rādītāju.
Tātad tur ir papildu rieciens atmiņas, kas mēs esam, lai izmantotu
par katru elementu ka mēs uzglabāt mūsu sarakstā.
Mēs iegūtu elastību, bet tas nāk pie izmaksām.
Tas nāk ar šo laika izmaksu,
un tas nāk ar šo atmiņas izmaksas pārāk.
Laiks, kas nozīmē, ka mums tagad ir iet caur katru elementu masīvā
lai atrastu vienu pie 10 indeksa, vai ka būtu bijis indekss 10 masīvā.
>> Tikai tiešām ātri, kad mēs diagramma šos sarakstus,
parasti mēs turēt uz saraksta galvas vai pirmās šautras saraksta
un atzīmē, ka tas ir patiess rādītājs.
Tas ir tikai 4 baiti. Tas nav faktiskā mezglā pati.
Tātad jūs redzat, ka tai nav int vērtības tajā, ne nākamajā rādītājs tajā.
Tas ir burtiski tikai rādītājs.
Tas notiek, lai norādītu uz kaut ko, kas faktiskā mezglā struktūrai.
[Sems] rādītājs sauc mezgls? >> Tas ir - nē. Tas ir rādītājs, lai kaut ko tipa mezglā.
Tas ir rādītājs, lai mezglu struct. >> Ak, labi.
Diagramma kreisajā, kodu labajā pusē.
Mēs varam noteikt to null, kas ir labs veids, kā sākt.
Kad jūs diagramma to, jums ir vai nu rakstīt to par spēkā vai jūs nodot līniju caur to tāpat.
>> Viens no vienkāršākajiem veidiem, kā strādāt ar sarakstiem,
un mēs lūdzam jūs gan prepend un pievieno, lai redzētu atšķirības starp diviem,
bet prepending noteikti ir vieglāk.
Kad jūs prepend, tas ir, ja jūs - kad jūs prepend (7),
jums iet un izveidot mezglu struct
un jūs noteikti vispirms norādīt uz to, jo tagad, jo mēs priekšā pieliek tā,
tas būs sākumā sarakstā.
Ja mēs prepend (3), kas rada citu mezglā, bet tagad 3 nāk pirms 7.
Tāpēc mēs esam būtībā stumšanas lietas uz mūsu sarakstā.
Tagad, jūs varat redzēt, ka prepend, dažreiz cilvēki to sauc par push,
jo jūs stumšanas jaunu elementu uz savu sarakstu.
Tas ir arī viegli izdzēst priekšā saraksta.
Lai cilvēki bieži zvana, ka pop.
Un šādā veidā, jūs varat sacensties kaudzīti izmantojot saistīts saraksts.
Whoops. Atvainojiet, tagad mēs esam nokļūst pievienot. Tātad šeit mēs priekšā pieliek (7), tagad mēs prepend (3).
Ja mēs priekšā pieliek kaut kas cits uz šo sarakstu, ja mēs priekšā pieliek (4),
tad mēs gribētu būt 4 un pēc tam 3 un tad līdz 7.
Tātad, tad mēs varētu pop un noņemt 4, Noņemt 3, noņemt 7.
Bieži intuitīvi veids, kā domāt par šo ir ar pievienošanas.
Tāpēc es esmu diagrammed, kas tas varētu izskatīties ar pievienot šeit.
Lūk, kas pievienots (7) neizskatās atšķirīgi
jo tur ir tikai viens elements sarakstā.
Un pievienojot (3) liek to beigās.
Varbūt jūs varat redzēt tieši tagad triks ar Append
ir, ka kopš mēs tikai zinām, kur saraksta sākums ir,
pievienot uz sarakstu jums ir staigāt visu ceļu cauri sarakstam
nokļūt līdz beigām, apstāties, tad veidot savu mezglā un nogāzt viss uz leju.
Vadu visi sīkumi augšu.
Tātad ar prepend, jo mēs tikko izvilkts caur šo patiešām ātri,
kad tu prepend sarakstam, tas ir diezgan vienkārši.
>> Jūs veicat savu jauno mezglā, zināmā dinamisku atmiņas sadalījumu.
Tātad šeit mēs nesam mezglu struct izmantojot malloc.
Tāpēc malloc mēs izmantojam, jo ​​tas būs atcelt atmiņā mums vēlāk
jo mēs nevēlamies šo - mēs vēlamies, lai šī atmiņa saglabājas ilgu laiku.
Un mēs rādītāju uz vietas atmiņā, ka mēs tikko piešķirts.
Mēs izmantojam lielumu mezglā, mēs kopsumma nav laukus.
Mums nav manuāli radīt baitu skaitu,
vietā mēs izmantojam sizeof lai mēs zinām, mēs esam iegūt atbilstošu skaitu baitu.
Mēs rūpējamies, lai pārbaudītu, ka mūsu malloc zvans izdevās.
Tas ir kaut kas jūs vēlaties darīt vispār.
Uz mūsdienu mašīnām, darbojas no atmiņas nav kaut kas ir viegli
ja jūs piešķirot ton stuff un veicot milzīgu sarakstu,
bet, ja jūs ēkas sīkumi, teiksim, piemēram, iPhone vai Android,
Jums ir ierobežots atmiņas resursi, it īpaši, ja jūs darāt kaut ko intensīvu.
Tāpēc tas ir labi, lai iegūtu praksē.
>> Ievērojiet, ka es esmu, ko izmanto pāris dažādas funkcijas šeit
ka jūs esat redzējuši, ka ir sava veida jaunu.
Tik fprintf ir tāpat kā printf
izņemot savu pirmo argumentu ir plūsma uz kuru vēlaties drukāt.
Šajā gadījumā mēs gribam drukāt uz standarta kļūdu virknes
kas atšķiras no standarta outstream.
Pēc noklusējuma tā parādās tajā pašā vietā.
Tā arī izdrukā uz termināli, bet jūs varat -
izmantojot šīs komandas jums uzzināju par, novirzīšanas metodes
jūs esat iemācījušies par in Tommija video par problēmu kopumu 4, jūs varat virzīt to
dažādām jomām, tad izejiet, tieši šeit, izejas savu programmu.
Tas ir būtībā tāpat atgriežas no galvenā,
izņemot mēs izmantojam izeju jo šeit atgriešanās nedarīs neko.
Mēs esam ne galvenais, lai atgriežoties nav izietu no programmas, piemēram, mēs gribam.
Tāpēc mēs izmantojam EXIT funkciju un piešķir tai kļūdas kodu.
Tad šeit mēs noteikti jaunās mezglu vērtību lauku, tā man lauka ir vienāda uz i, un tad mēs vadu to uz augšu.
Mēs noteikti jaunā mezglu blakus rādītāju norādīt uz pirmo,
un tad vispirms būs tagad norāda uz jauno mezglu.
Pirmie rindas kods, mēs esam patiešām veidojot jaunu mezglu.
Ne pēdējās divas rindas šīs funkcijas, bet pirmie.
Jūs faktiski var izraut uz funkciju, par palīgs funkcijas.
Tas ir bieži, ko es daru, es velciet to ārā funkciju,
Es aicinu to kaut kā būvēt mezglā,
un kas uztur prepend funkciju diezgan maza, tas ir tikai 3 līnijas tam.
Es piezvanīt uz manu būvēt mezgla funkciju, un tad es vadu viss uz augšu.
>> Pēdējā lieta es gribu jums parādīt,
un es jums darīt pievienot un visu to par savu,
ir, kā atkārtot pa sarakstu.
Ir dažādi veidi, lai atkārtot pa sarakstu ķekars.
Šajā gadījumā, mēs spēsim atrast garumu saraksta.
Tātad sākam ar garumu = 0.
Tas ir ļoti līdzīgs rakstot strlen par virkni.
Tas ir tas, ko es vēlos parādīt jums, šis cilpa tieši šeit.
Tas izskatās kinda bailīgs, tas nav ierasts int i = 0, i <neatkarīgi, i + +.
Tā vietā tas ir inicializēšana mūsu mainīgo n būt sākums saraksta.
Un tad kamēr mūsu iterator mainīgais nav nulle, mēs turpinām iet.
Tas ir tāpēc, pēc vienošanās, mūsu saraksta beigās būs nulle.
Un tad, lai pieauguma, nevis darot + +,
saistīts saraksts ekvivalents + + ir n = n-> nākamo.
>> Es jums aizpildīt robus šeit, jo mēs esam no laika.
Bet paturēt to prātā, kā jūs strādāt pie jūsu spellr psets.
Saistīti saraksti, ja jūs īstenot hash tabulu,
būs noteikti nāk ļoti ērts.
Un ņemot šo idiomu lai looping pār lietām padarīs dzīvi daudz vieglāk, cerams.
Kādi jautājumi, ātri?
[Sems] Vai jūs izsūtīt aizpildīta SLL un SC?
[Hardison] Jā. Es izsūtīt aizpildītās slaidus un aizpildītu SLL kaudze un queue.cs.
[CS50.TV]