[Powered by Google Translate] [6. jagu] [mugavam]
[Rob Bowden] [Harvardi Ülikool]
[See on CS50.] [CS50.TV]
>> Me ei pea meie osa küsimustele.
Saatsin URL ruumi enne.
Lõigu alguses esitatud küsimuste öelda-
ilmselt ma ei ole päris unsick-on väga lihtne küsimus
on just see, mida on valgrind?
Mis valgrind teha?
Igaüks taha öelda, mida valgrind teeb?
[Student] Kontrollimine mälu lekkeid.
Jah, valgrind on üldine mälu kontrollija.
See, et lõpuks ütleb teile, kui teil on mõni mälu lekked,
mis on enamasti mida me kasutame seda, sest kui sa tahad
teha ka lahendamist või kui soovite
saada suurt ekraani, pead ei ole mälu lekkeid üldse,
ja kui sul on mälu leke et sa ei leia,
Samuti pidage meeles, et iga kord, kui avate faili
ja kui sa ei sulge, see on mälu leke.
>> Paljud inimesed otsivad mõned sõlme, et nad ei vabastamine
kui tõesti, nad ei sulgenud sõnaraamatu kõige esimene samm.
Samuti ütleb teile, kui teil on mõni vigane loeb või kirjutab,
mis tähendab, kui sa püüad ja määra
see on kauem hunnik ja see ei juhtu SEG süü
kuid valgrind saak see, kui sa ei peaks tegelikult olema kirjalikult seal,
ja nii sa kindlasti ei tohiks olla nende kas.
Kuidas kasutada valgrind?
>> See on üldine küsimus
selline käivitada ja vaadata väljund.
Väljund on valdav palju kordi.
Seal on ka lõbus vigu kui kui teil on mõned kohutavalt vale asja
toimub silmuse, siis hakkab see lõpuks öelda: "Liiga palju vigu.
Ma lähen lõpetada lugedes nüüd. "
See on põhimõtteliselt tekstiline väljund, et teil on sõeluda.
Lõpuks ta ütleb sulle ükskõik mälu lekkeid, mis sul on,
kui palju plokid, mis võib olla kasulik, sest
kui see on üks plokk unfreed, siis on see tavaliselt kergem leida
1000 plokki unfreed.
1000 plokki unfreed tähendab ilmselt sa ei vabastamine
Teie seotud nimekirju asjakohaselt või midagi.
See on valgrind.
>> Nüüd on meil osa küsimusi,
mis sa ei pea alla laadida.
Võite klõpsata minu nimi ja tõmmata neid üles ruumis.
Nüüd klõpsa mind.
Versioon 1 on pinu, mis me teeme esimene.
Kontroll 2 on järjekorda ja Kontroll 3 on üksikult seotud nimekirja.
Alustades meie pinu.
Nagu öeldakse siin, korstnat on üks kõige elementaarsem,
põhiline andmestruktuurid infotehnoloogia.
Väga prototüübi näide on
virna plaate söögisaalis.
See on põhimõtteliselt alati, kui on sisse, et korstnat
keegi kavatseb öelda: "Oh, nagu virna plaate."
Sa Kestab plaadid üles.
Siis, kui lähete tõmmake salve,
esimene plaat, mis on saada tõmmatakse, on viimane, mis pandi virna.
Korstnat ka-nagu öeldakse siin-
meil segment mälu nimetatakse pinu.
Ja miks on selle nimi korstnat?
>> Sest nagu pinu andmestruktuur,
see lükkab ja hüppab korstna raamid korstnat
kus korstna raamid on nagu konkreetse kõne funktsioon.
Ja nagu pinu, siis on alati naasta
alates funktsioon kõne enne saate ette võtta madalama korstnat raamid uuesti.
Sul ei saa olla peamine kõne suva kõne baar ja baar naasta peamine otse.
See on alati pead järgima õige korstna surudes ja popping.
Kaks operatsiooni, nagu ma ütlesin, on push ja pop.
Need on universaalsed tingimused.
Sa peaksid teadma, push ja pop nii korstnad ükskõik mida.
Eks näis järjekorrad on kuidagi teistsugused.
See ei ole tõesti universaalne termin, kuid push ja pop on universaalsed korstnad.
Push on lihtsalt panna virna.
Pop on startida pinu.
Ja me näeme siin oleme meie typedef struktuure korstnat
nii et meil on char ** stringid.
Ära lase hirmul ükski **.
See läheb lõpuks on massiivi stringe
või massiivi osuti sellistele tegelastele, kus
viiteid, et märki kipuvad olema stringid.
See ei pea olema stringid, kuid siin, nad ei kavatse olla stringid.
>> Meil on hulgaliselt stringid.
Meil on suurus, mis näitab, mitu elementi on praegu korstnat
ja siis me võime, mis on, kui palju elemente võib olla pinu.
Võimsus peaks alustad nagu midagi suurem kui 1,
kuid suurus läheb alustad kui 0.
Nüüd on põhiliselt kolmel erineval viisil saab mõelda pinu.
Noh, seal on ilmselt rohkem, kuid kaks peamist võimalust on
mida saab rakendada, kasutades massiivi, või saab rakendada, kasutades seotud loetelu.
Seotud nimekirjad on selline triviaalne teha korstnad.
See on väga lihtne teha virna kasutades lingitud nimekirjad,
Nii et siin me läheme tegema korstnat kasutades massiive,
ja siis kasutades massiive, seal on ka kaks võimalust võite mõelda.
Enne, kui ma ütlesin, et meil on võime korstna
nii me mahub elemendi pinu.
>> Üks viis see võib juhtuda, on nii kiiresti kui jõuad 10 elementi, siis sa oled teinud.
Sa võid teada, et on ülemine piir 10 asja maailmas
et sa ei pea kunagi rohkem kui 10 asju oma korstnat
millisel juhul saab olema ülemise suuruse kohta oma korstnat.
Või siis võiks olla oma korstnat tuleb ääretu,
aga kui sa teed massiivi, mis tähendab, et iga kord kui jõuad 10 elementi,
siis sa lähed pea kasvada kuni 20 elementi, ja kui vajutad 20 elementi,
sa lähed on kasvatada oma array 30 elementi või 40 elementi.
Sa lähed vaja suurendada võimsust, mis on see, mida me teeme siin.
Iga kord jõuame maksimaalne suurus meie korstnat
kui vajutada midagi muud, me ei kavatse vaja suurendada võimsust.
Siin me oleme push deklareeritud bool push (char * str).
Char * str on string, mis me surudes peale virna,
ja bool lihtsalt ütleb, kas meil õnnestus või ebaõnnestus.
>> Kuidas saaksime jätta?
Mis on ainus asjaolu, et sa ei mõtle
kus meil oleks vaja tagasi false?
Jah.
[Student] Kui see on täis ja me kasutame piirneb rakendamist.
Jah, nii kuidas me määratleme-ta vastas
kas see on täielik ja me kasutame tõkestatud rakendamist.
Siis me kindlasti tagasi false.
Niipea kui me hit 10 asja sisse massiiv, me ei mahu 11, nii et me tagasi false.
Mis siis, kui see on ääretu? Jah.
Kui te ei saa laiendada massiivi mingil põhjusel.
Jah, nii mälu on piiratud ressurss,
ja lõpuks, kui me hoida surudes asju peale virna ikka ja jälle,
me ei kavatse proovida ja eraldada suurem massiiv sobivaks
suurem võimsus ja malloc või mis iganes me kasutame läheb tagasi false.
Noh, malloc naaseb null.
>> Pea meeles, et iga kord, kui kunagi helistada malloc, siis tuleks kontrollida, kas see
tagastab null või muud, mis on õigsuse mahaarvamist.
Kuna me tahame ääretu korstnat
ainult juhul me ei kavatse tagasi vale on, kui püüame
suurendada suutlikkust ja malloc või mis iganes FALSE.
Siis pop võtab ühtegi argumenti,
ja see tagastab stringi, mis on peal virnas.
Ükskõik oli viimati lükatakse edasi pinu on see, mis pop on tagasi,
ja see ka eemaldab selle virna.
Ja märkate, et ta naaseb null, kui pole midagi pinu.
Alati on võimalik, et korstnat on tühi.
Java, kui sa oled harjunud, et või teistes keeltes,
püüdes pop tühjast korstnat võib põhjustada erand või midagi.
>> Aga C, null on selline palju juhtumeid, kuidas me käsitleme neid probleeme.
Tulles null on, kuidas me kavatseme tähenda, et korstnat oli tühi.
Oleme lisanud koodi, mis paneb proovile oma korstnat funktsionaalsust,
rakendada push ja pop.
See ei ole palju koodi.
Ma ei unusta kunagi tegelikult, enne kui me seda teeme, vihje, vihje-
kui sa pole seda näinud, malloc ei ole ainus funktsioon
et eraldab mälu hunnik teile.
On pere alloc funktsioone.
Esimene on malloc, mis sa oled harjunud.
Siis on calloc, mis teeb sama asja nagu malloc,
kuid see nulli kõike sinu eest.
Kui sa oled kunagi tahtnud, et seada kõik tühjaks pärast mallocing midagi
sa oleks pidanud lihtsalt kasutada calloc esimese koha asemel kirjalikult
jaoks silmus nullini viia kogu ploki mälu.
>> RealLOC on nagu malloc ja on palju erijuhtudel
kuid põhimõtteliselt mida RealLOC ei ole
see võtab osuti, mis oli juba eraldatud.
RealLOC on funktsioon, mida soovite pöörata tähelepanu siia.
See võtab osuti, mis olid juba naasnud malloc.
Oletame, et teil nõuda malloc pointer 10 baiti.
Siis hiljem saad aru, et sa tahtsid 20 baiti,
nii te nimetate RealLOC selle osuti on 20 baiti,
ja RealLOC kopeerib automaatselt üle kõik sinu jaoks.
Kui sa just helistas malloc jälle, nagu mul on plokk 10 baiti.
Nüüd on mul vaja plokk 20 baiti,
nii et kui ma malloc 20 baiti, siis mul on käsitsi kopeerida üle 10 baiti alates esimese asjana
arvesse teise asi ja siis vaba esimene asi.
RealLOC tegelen selle sulle.
>> Teade allkirja saab olema tühine *,
mis on lihtsalt tagastab viida, mis ploki mälu,
siis void * ptr.
Sa ei mõtle void * geneerilise pointer.
Üldiselt sa kunagi tegelema void *,
kuid malloc on tagasi void *, ja siis ta on lihtsalt kasutada nagu
see on tegelikult saab olema char *.
Eelmine void *, mis oli tagastatud malloc
hakkab nüüd tuleb edasi anda RealLOC ja seejärel suurus
on uus baitide arv, mida soovite jagada, nii endale võimsust.
Ma annan sulle paar minutit, ja teha seda meie ruumis.
Alusta 1. läbivaatamine.
Ma peatan teie pärast loodetavasti umbes piisavalt aega, et rakendada push,
ja siis ma teen sulle veel ühe pausi teha pop.
Aga see tõesti ei ole nii palju koodi üldse.
Kõige kood on tõenäoliselt laieneb kraami, laiendades võimsust.
Okei, mingit survet olla täiesti tehtud,
kuid nii kaua, kui teil on tunne, et sa oled õigel teel, see on hea.
>> Kas keegi mingit koodi nad tunnevad end minuga mugavalt tõmmates?
Jah, ma teen seda, aga kas keegi on mingeid koodi ma ei tõmba?
Okei, sa saad alustada, salvestage see, mis see on?
Olen alati unustada, et samm.
Okei, vaadeldes tõuke,
sa tahad selgitada oma koodi?
[Student] Esiteks, ma kasvanud suurus.
Ma arvan, et ma peaks olema, et-igatahes, ma kasvanud suurus,
ja ma näen, kui see on väiksem kui võimsus.
Ja kui see on väiksem kui võimsus, lisan, et massiivi meil juba on.
Ja kui see ei ole, ma korrutan võimsus 2,
ja ma ümber stringid massiivi midagi suurem võimsus suurus nüüd.
Ja siis kui see ebaõnnestub, ma ütlen kasutaja ja tagastab false,
ja kui see on korras, siis panin stringi uue koha.
>> [Rob B.] ka teate, et me kasutasime kena BitWise operaatori siin
korrutada 2-ga.
Pea meeles, vasakule nihe alati saab korrutatakse 2-ga.
Right Shift on jagatud 2 nii kaua kui mäletan, et see tähendab,
jagage 2 nagu täisarv jagatud 2.
See võib kärpida 1 siin või seal.
Aga nihe vasakule 1. alati saab korrutada 2
kui sa ülevoolu piire täisarv, ja siis ei ole see.
Külg kommentaari.
Mulle meeldib teha-see ei muutu kodeerimine mingil moel,
aga mulle meeldib teha midagi sellist.
See tegelikult toimub, et see veidi kauem.
Võib-olla see ei ole täiuslik asja näidata,
aga mulle meeldib segmendi see need plokid-
okei, kui see, kui juhtub, siis ma teen midagi,
ja siis funktsioon on tehtud.
Ma ei pea seejärel kerige minu silmis täiesti alla funktsioon
näha, mis juhtub pärast teine.
See on kui see, kui juhtub, siis ma lihtsalt tagasi.
Samuti on kena lisakasu kõik väljaspool seda
nüüd nihutatakse vasakule kord.
Ma ei pea enam-kui sa kunagi lähedal naeruväärselt pikad read,
siis need 4 baiti aitab, ja ka rohkem vasakule midagi on,
vähem ülekoormatud te arvate, kui meeldib-okei, ma pean meeles pidama
Ma olen praegu samas silmus sees veel sees jaoks silmus.
Anywhere võite seda teha kohe tagasi, mulle nagu meeldib.
See on täiesti vabatahtlik ja mitte oodata kuidagi.
>> [Student] Kas tuleb suur - seda negatiivsete tingimus?
Ebaõnnestuvad seisukorras siin on meil õnnestunud RealLOC, nii et jah.
Märka, kuidas on negatiivsete seisukorras, arvatavasti,
kui me tasuta kraami hiljem, me alati läbi kukkunud
ükskõik kui palju kordi me proovi sundida midagi.
Kui me hoida surudes, me hoida incrementing suurus,
kuigi me ei pane midagi peale virna.
Tavaliselt me ​​ei juurdekasvu suurus kuni
pärast oleme edukalt panna see pinu.
Soovime seda teha, öelda, kas siin ja siin.
Ja siis selle asemel, et öelda s.size ≤ maht, seda on vähem kui võimsus,
ainult sellepärast kolisime kus kõik oli.
>> Ja pidage meeles, ainus koht, et me võiks tagasi false
on siin, kus RealLOC tagastatakse null,
ja kui juhtub, et mäletan standardviga,
äkki sa võiksid kaaluda seda juhul, kui soovite printida standardviga,
nii fprintf stderr asemel lihtsalt printida otse standard välja.
Jällegi, see pole ootus, kuid kas see on viga,
kirjuta printf, siis võiksite teha seda printida standardviga asemel standard välja.
>> Igaüks on midagi märkida? Jah.
[Student] Kas te lähete üle [kuuldamatu]?
[Rob B.] Jah, tegelik binariness seda või lihtsalt, mis see on?
[Student] Nii et sa korrutada see 2?
[Rob B.] Jah, põhimõtteliselt.
In binaarne maa, meil on alati meie kogumi numbrit.
Shifting see vasak 1. põhiliselt lisab seda siin paremal pool.
Tagasi sellele, lihtsalt pea meeles, et kõik binaarne
on võimsus 2, nii et see moodustab 2 0,
see 2 kuni 1, see 2 2.
Kui sisestate 0 kuni paremal pool nüüd, me lihtsalt minema kõik üle.
Mida varem 2 0 on nüüd 2 1, 2 kuni 2.
Paremal küljel, et me sisestatud
paratamatult saab olema 0,
mis mõtet.
Kui sa kunagi Arvu korrutamiseks 2, ta ei kavatse lõpuks kummaline,
nii 2 0 koht peaks olema 0,
ja see, mida I poolaasta hoiatati enne on, kui sul juhtub minema
kaugemale bittide arvuga täisarv,
siis see 1 läheb lõpuks läheb maha.
See on ainus mure, kui teil juhtub olema tegemist tõesti suur võimekus.
Aga sel hetkel, siis olete tegelevad massiivi miljardeid asju,
mis ei pruugi sobituda mälu niikuinii.
>> Nüüd saame pop, mis on veelgi lihtsam.
Sa võid seda teha nagu kui juhtub, et pop terve hunnik,
ja nüüd sa oled poole võimsusega uuesti.
Sa võid RealLOC kahaneb mälu teil on,
aga sa ei pea muretsema, et nii ainult RealLOC juhul saab olema
kasvab mälu, kunagi kahanemine mälu,
mis toimub, et pop super lihtne.
Nüüd järjekorrad, mis saab olema nagu korstnad,
kuid selleks, et te võtate asju teha vastupidine.
Prototüübi näide järjekord on rida,
nii et ma arvan, kui sa olid inglise, oleksin öelnud
prototüübi näide järjekord on sabas.
Nii nagu joon, kui sa oled esimene inimene liin,
ootate olla esimene inimene väljaspool järjekorda.
Kui sa oled viimane inimene kooskõlas, te ei kavatse on viimane inimene hooldada.
Kutsume et FIFO muster, samas korstnat oli LIFO muster.
Need sõnad on päris universaalne.
>> Nagu korstnad ja erinevalt massiivid, järjekorrad tavaliselt ei võimalda juurdepääsu elemendid keskel.
Siin korstnat, meil on push ja pop.
Siin me juhtumisi on neid kutsunud Lisa järjekorda ja dequeue.
Olen kuulnud neid nimetatakse vahetustega ja unshift.
Olen kuulnud inimesi rääkimas, push ja pop kohaldatakse ka järjekorrad.
Olen kuulnud, sisestage, eemaldage,
nii push ja pop, kui te räägite korstnad, olete tõukamiseks ja popping.
Kui sa räägid järjekorrad, võid valida sõnu, mida soovite kasutada
paigaldamise ja eemaldamise ning puudub üksmeel selles, milline see peaks olema nn.
Aga siin on meil Lisa järjekorda ja dequeue.
Nüüd struct näeb välja peaaegu identsed korstnat struct.
Aga meil on jälgida pea.
Ma arvan, et see ütleb siin, kuid miks me vajame peas?
Prototüübid on põhimõtteliselt identne push ja pop.
Sa ei mõtle seda push ja pop.
Ainus erinevus on see pop on tagasi-, mitte viimasena, see on jälle esimene.
2, 1, 3, 4, või midagi.
Ja siin on algus.
Meie järjekord on täiesti täis, nii et seal on neli elemente.
Lõpuks meie järjekord on praegu 2
ja nüüd me läheme lisada midagi muud.
>> Kui me tahame lisada, et midagi, mida meie tegime korstna versioon
on meil laiendada meie ploki mälu.
Mis on sellega probleem?
[Student] Sa liigud 2.
Mis ma enne ütlesin on otsas järjekorda,
see ei ole loogiline, et me stardivad 1,
siis me tahame dequeue 1, siis dequeue 3, siis dequeue 4,
siis dequeue 2, siis dequeue see üks.
Me ei saa kasutada RealLOC nüüd,
või vähemalt, sa pead kasutama RealLOC teistmoodi.
Aga sa ilmselt ei tohiks lihtsalt kasutada RealLOC.
Sa ei kavatse on käsitsi kopeerida oma mälu.
>> Seal on kaks funktsiooni kopeerida mälu.
Seal on memcopy ja memmove.
Ma olen praegu lugemine mees leheküljed, et näha, milline neist sa lähed soovite kasutada.
Okei, memcopy, vahe on
et memcopy ja memmove, üks tegeleb juhtumi õigesti
kuhu kopeerimine arvesse piirkonnas, mis juhtub kattuda regioon
sa kopeerimist.
Memcopy ei saa sellega hakkama. Memmove teeb.
Sa ei mõtle probleemi-
oletame, et ma tahan kopeerida selle kuti,
Nende nelja kuni see kutt.
In the end, mida array peaks välja nägema
pärast koopia on 2, 1, 2, 1, 3, 4, ja siis mõned asjad lõpus.
Aga see sõltub, millises järjekorras me tegelikult kopeerida,
sest kui me ei arva, et piirkond me kopeerimine sisse
kattub üks me kopeerimist,
siis me võiksime teha nagu alguses siin, kopeerige 2 arvesse kohas me tahame minna,
seejärel liikuda meie osuti edasi.
>> Nüüd me ei kavatse olla siin ja siin, ja nüüd tahame kopeerida
see kutt seda meest ja liikuda meie osuti edasi.
Mis me hakkame lõpuks saada on 2, 1, 2, 1, 2, 1
asemel korral 2, 1, 2, 1, 3, 4, sest
2, 1 kaalus originaal 3, 4.
Memmove käepidemed, et õigesti.
Sel juhul põhiliselt just alati kasutada memmove
sest see tegeleb ta õigesti.
See üldiselt ei täida enam hullemaks minna.
Idee on mitte alustada algusest ja kopeerimine sel viisil
nagu me tegime siin, siis hakkab otsast ja kopeerib,
ja sel juhul sa ei saa kunagi olla probleem.
Ei saa jõudluse kadunud.
Kasutage alati memmove. Mitte kunagi muretsema memcopy.
Ja see, kui sa lähed pea eraldi memmove
pakitud ümber osa oma järjekorda.
Ära muretse, kui mitte täiesti valmis.
See on raskem kui pinu, push ja pop.
>> Igaüks on kood, võiksime teha koostööd?
Isegi kui täiesti puudulik?
[Student] Jah, see on täiesti puudulik, kuigi.
Täiesti puudulik on ilus nii kaua kui me-saate salvestada läbivaatamist?
Ma unustada, et iga kord.
Okei, ignoreerides mis juhtub, kui me peame suurust asju.
Täiesti ignoreerida resize.
Selgitage see kood.
Ma kontrollin kõigepealt, kui suurus on väiksem kui koopia kõigepealt
ja siis pärast, et ma sisestan-ma võtan pea + suurus,
ja ma veenduge, et see murtakse võimsus massiiv,
ja ma sisestan uue stringi selles asendis.
Siis ma suurendama ning tagastab tõsi.
>> [Rob B.] See on kindlasti üks neid juhtumeid, kus sa lähed tahad olla kasutades mod.
Igasugune Juhul kui olete ümbriste ümber, kui te arvate ümbriste ümber,
kohe mõte peaks olema moderaator.
Nagu kiire optimeerimine / muuta oma koodi ühele reale lühem,
märkate, et joon kohe pärast selle ühe
on lihtsalt suuruse + +, nii et teil ühendada seda arvesse seda joont, suurus + +.
Nüüd on siin, meil puhul
kus meil ei ole piisavalt mälu,
nii me suurendada meie suutlikkust 2.
Ma arvan, et sa võiksid olla sama probleem, kuid me ei saa eirata seda nüüd,
kus, kui sa ei tõsta oma suutlikkust,
siis sa lähed tahad, et vähendada oma võimsust 2 uuesti.
Teine lühike märkus on nagu saate teha + =,
saate ka teha << =.
Peaaegu kõike saab minna enne võrdub, + =, | =, & =, << =.
Char * uus on meie uus ploki mälu.
Oh, siin.
>> Mida inimesed mõtlevad tüüp meie uus ploki mälu?
[Student] See peaks olema char **.
Mõeldes tagasi meie struct siin,
stringid on see, mida me ümberjaotamise.
Teeme kogu uus dünaamiline ladustamise elemendid järjekorda.
Mida me ei kavatse paigutada oma stringid on see, mida me mallocing just nüüd,
ja nii uus saab olema char **.
See saab olema array stringid.
Siis milline on juhtum, mille alusel me läheme tagasi false?
[Student] me peaksime tegema char *?
[Rob B.] Jah, hea kõne.
[Student] Mis see oli?
[Rob B.] Me tahtsime teha suurus char * sest me ei ole enam-
see oleks tegelikult väga suur probleem, sest sizeof (char) oleks 1.
Sizeof char * saab olema 4,
nii palju kordi, kui olete tegelevad ints,
siis kipuvad minema sellega kuna suurus int ja suurus int *
32-bitine süsteem saab olema sama asi.
Aga siin, sizeof (char) ja sizeof (char *) nüüd saab olema sama asi.
>> Milline on olukord, kus me tagasi false?
[Student] Uus on null.
Jah, kui uus on null, siis tagastab false,
ja ma viskan siia alla-
[Student] [kuuldamatu]
[Rob B.] Jah, see on hea.
Sa võid kas teha 2 korda suutlikkuse või tootmisvõimsuse muutus 1 ja seejärel ainult määratud see siia alla või mis iganes.
Me teeme seda nagu meil oli see.
Maht >> = 1.
Ja sa oled kunagi muretsema kaotamata 1. koht
sest sa jätsid nihutatakse 1, seega 1 koht on tingimata 0,
nii õige nihkub 1., sa oled ikka läheb hästi.
[Student] Kas sa pead tegema, et enne tagasi?
[Rob B.] Jah, see teeb absoluutselt mingit mõtet.
>> Oletame nüüd, me ei kavatse lõpuks tagasi tõsi lõpuni.
Kuidas me teeme neid memmoves,
me peame olema ettevaatlikud, kuidas me teeme neid.
Kas kellelgi on mingeid ettepanekuid, kuidas me teeme neid?
Siin on meie start.
Paratamatult me ​​tahame alustada algusest uuesti
ja koopia asju sealt, 1, 3, 4, 2.
Kuidas sa seda tegid?
Esiteks, ma pean vaatama man-leheküljelt memmove uuesti.
Memmove, et argumente on alati oluline.
Me tahame, et meie sihtpunkt esimene, allikas teiseks suurus kolmandik.
Seal on palju funktsioone, mis tagurdama allikas ja sihtpunkt.
Sihtkoht, allikas kipub olema kooskõlas mõnevõrra.
Teisalda, mida ta tagasi?
Ta naaseb kursor sihtkohta ükskõik mis põhjusel võiksite seda.
Võin pilti lugeda, kuid me tahame liikuda meie sihtkohta.
>> Mis on meie sihtkoht saab olema?
[Student] Uus.
[Rob B.] Jah, ja kuhu me kopeerimist?
Esimene asi, mida me kopeerimine on see 1, 3, 4.
Mis on-see 1, 3, 4.
Mis on aadress selle 1?
Mis on aadress, et 1?
[Student] [kuuldamatu]
[Rob B.] Head + aadress esimese osaga.
Kuidas me esimest elementi massiivi?
[Student] järjekorda.
[Rob B.] Jah, q.strings.
Pea meeles, siin, meie peas on 1.
Darn it. Ma lihtsalt arvan, et see võluväel-
Siin on meie peas on 1. Ma muudan värvi ka.
Ja siin on stringid.
See, saame kas kirjutada see nagu tegime siin
peaga + q.strings.
Paljud inimesed ka seda kirjutada ja q.strings [juht].
See ei ole tõesti kuidagi vähem tõhus.
Sa võid arvan et kui te viite mahavõtmine ja siis saada aadress,
kuid kompilaator saab tõlkida seda mis meil oli enne niikuinii, q.strings + pea.
Mõlemal juhul te soovite mõelda.
>> Ja kui palju baite me tahame kopeerida?
[Student] Capacity - peas.
Maht - peas.
Ja siis sa võid alati kirjutada näiteks
aru saada, kui see on õige.
[Student] Tuleb jagatud 2 siis.
Jah, nii et ma arvan, et me võiks kasutada suurus.
Meil on veel suurus on-
kasutades suurus, meil on suurus, mis võrdub 4.
Meie suurus on 4. Meie pea on 1.
Me tahame kopeerida need 3 elementi.
See on meelerahu vaadata, et suurus - pea on õigesti 3.
Ja tulevad siia tagasi, nagu me varem öelnud,
kui me kasutada võimsust, siis oleks meil jagada 2
sest me oleme juba kasvanud meie suutlikkust, et selle asemel, me ei kavatse kasutada suurus.
See koopiate osa.
Nüüd on vaja kopeerida teiste osa, osa mis on jäänud algusest.
>> See saab memmove arvesse millisel positsioonil?
[Student] Plus suurus - peas.
Jah, nii oleme juba kopeeritud suurus - pea baite
ja seda siis, kui me tahame, et kopeerida ülejäänud baidid on uus
ja siis miinus-hästi, baitide arvu me oleme juba kopeeritud sisse
Ja siis, kui me kopeerimist?
[Student] Q.strings [0].
[Rob B.] Jah, q.strings.
Võiksime kas teha ja q.strings [0].
See on oluliselt vähem levinud kui see.
Kui see on lihtsalt saab olema 0, siis saate kipuvad vt q.strings.
See, kui me kopeerimist.
Mitu baiti me lahkunud kopeerida? >> [Student] 10.
Õigus.
[Student] Kas peame korrutama 5-10 korda suurem baiti või midagi?
Jah, nii see on, kus-mis täpselt me ​​kopeerimist?
[Student] [kuuldamatu]
Mis tüüpi on asi, mida me kopeerimist?
[Student] [kuuldamatu]
Jah, nii char * s, et me kopeerimine, me ei tea, kust need tulevad.
Noh, kus nad osutavad, nagu stringid, me lõpuks surudes seda peale järjekorda
või enqueuing peale järjekorda.
Kui need tulevad, me ei tea.
Me lihtsalt vaja jälgida char * s ise.
Me ei taha kopeerida suurus - pea baiti.
Me tahame kopeerida suurus - pea char * s,
nii me läheme korrutada seda sizeof (char *).
Sama siin, pea * sizeof (char *).
>> [Student] Aga [kuuldamatu]?
See siin?
[Student] Ei, alla selle suurus - peas.
[Rob B.] See siin?
Pointer aritmeetika.
Kuidas pointer aritmeetika läheb tööle on
see automaatselt korrutab suurusest tüüp, et me tegeleme.
Just nagu siin, uus + (suurus - pea)
on samaväärne & uus [size - pea]
kuni me eeldame, et töötada õigesti,
sest kui me tegeleme int massiiv, siis me ei indeks int-
või kui see on suuruse 5 ja soovite 4. osa, siis me indeks
int massiiv [4].
Sa ei-[4] * suurus int.
See tegeleb ta automaatselt, ja sel juhul
on sõna otseses mõttes samaväärne, nii sulg süntaks
lihtsalt läheb ümber selle niipea kui kompileerida.
See on midagi, sa pead olema ettevaatlik, et
kui lisate suurus - pea
seote mitte üks bait.
Sa lisades ühe char *, mis võib olla üks baiti või mis iganes.
>> Muud küsimused?
Okei, dequeue saab olema lihtsam.
Ma annan sulle hetke rakendada.
Oh, ja ma arvan, et see on samas olukorras, kus
Mis Lisa järjekorda juhul, kui me enqueuing null,
võibolla me tahame seda käsitlemast, äkki meil ei ole.
Me ei tee seda enam siin, kuid samas on meie stack nii.
Kui me Lisa järjekorda null, tahetakse jätta see.
Igaüks on natuke koodi ma ei tõmba?
[Student] ma lihtsalt pean dequeue.
Versioon 2 on see, et-eks.
Sa tahad seletada?
[Student] Esmalt veenduge, et seal on midagi järjekorras
ja mis suurus läheb alla 1.
Sa pead seda tegema, ja siis tagasi pea
ja seejärel liikuda pea üles 1.
Okei, nii et seal on nurgas juhul peame kaaluma. Jah.
[Student] Kui su peas on viimasel element,
siis sa ei taha pea juhtida väljaspool massiivi.
>> Jah, nii kiiresti kui pea tabab lõpuks meie massiiv,
kui me dequeue, meie pea peaks olema modded tagasi 0.
Kahjuks me ei saa seda teha ühe sammuga.
Ma arvan nii, nagu ma tahaks ilmselt seda parandada on
see saab olema char *, mida me tagasi,
sõltumata oma muutuja nimi tahab olla.
Siis tahame mod pea meie suutlikkust
ja siis tagasi ret.
Paljud inimesed siin ka neile võib do-
see on nii-Küll sa näed inimesi teha, kui pea
on suurem kui võimsus, teha head - võimsus.
Ja see on just töö ümber, mida moderaator on.
Head mod = võimsus on palju puhtam
ja ümbriste ümber kui siis, kui pea on suurem kui tootmisvõimsuse pea - võimsus.
>> Küsimused?
Okei, viimane asi, mida me oleme jätnud on meie seotud nimekirja.
Sa võid kasutada mõned seotud nimekirja käitumist, kui sa tegid
seotud loendite oma hash tabeleid, kui sa hash tabelit.
Soovitan soojalt teed hash tabelit.
Te olete juba teinud trie,
vaid üritab raskem.
Teoreetiliselt nad asümptootiliselt parem.
Aga vaata Suurele lauale
ja proovib kunagi paremini teha, ja nad võtavad rohkem mälu.
Kõike üritab jõuab on halvem rohkem tööd.
See on see, mida David Malan lahendus alati on
on ta alati postitust oma trie lahendus, ja vaatame, kus ta praegu on.
Milline oli ta all, David J?
Ta on # 18, nii et ei ole väga halb,
ja et see saab olema üks parimaid üritab võite mõelda
või üks parimaid üritab kohta trie.
Kas ei ole isegi oma originaalse lahenduse?
Mul on tunne, trie lahendused kipuvad olema selles vahemikus RAM kasutust.
>> Mine alla väga üleval, ja RAM kasutust on ühekohalised numbrid.
Mine alla põhja poole, ja siis hakkate nägema püüab
kus sa saad absoluutselt tohutu RAM kasutust,
ja üritab raskem.
Mitte täielikult seda väärt, kuid õpetlik kogemus, kui sa tegid ühe.
Viimane asi on meie seotud nimekirja,
ja need kolm asja, korstnad, järjekorrad, ja lingitud nimekirjad,
tulevaste asi, mida kunagi teha infotehnoloogia
eeldab teil on tuttav neid asju.
Nad on lihtsalt nii fundamentaalne, kõike.
>> Seotud nimekirjades, ja siin me oleme üksikult seotud nimekirja saab olema meie rakendamist.
Mis üksikult seotud tähenda mitte kahekordselt seotud? Jah.
[Student] See ainult punkti järgmisele osuti asemel suunanäitajaks,
nagu üks eelnenud ja üks pärast seda.
Jah, nii pildivormingu, mida ma just teha?
Mul on kaks asja. Mul on pilt ja pilt.
Aastal pildivormingu, meie üksikult seotud nimekirju,
paratamatult on meil mingi kursor pea meie nimekirjas,
ja siis meie nimekirjas, me lihtsalt viiteid,
ja äkki viitab see tühjaks.
See saab olema teie tüüpiline joonis üksikult seotud nimekirja.
Kahekordselt seotud nimekirja, võite minna tagasi.
Kui ma annan teile mingit sõlme nimekirja, siis saate kindlasti saada
muu sõlme loetelu, kui see on kahekordselt seotud nimekirja.
Aga kui ma saan sulle kolmanda sõlme nimekiri ja see on eraldi lingitud nimekiri,
kuidagi sa oled kunagi saada esimese ja teise tippu.
Ja seal on kasu ja puudustega ja üks ilmne
on teil võtavad rohkem suuruse ja teil on jälgida, kus need asjad on suunatud nüüd.
Aga me ainult hoolid üksikult seotud.
>> Mõned asjad me lähed on rakendada.
Sinu typedef struktuure sõlme, int i: struct tipp * next; sõlme.
See typedef tuleb põletada oma mõtetes.
Viktoriin 1 tuleks meeldib anda typedef on seotud nimekirja sõlme,
ja sa peaks olema võimalik kohe kritseldus, et alla
ilma isegi mõelda seda.
Ma arvan, et paar küsimust, miks me vajame vatseti siin?
Miks ei saa me öelda sõlme *?
[Student] [kuuldamatu]
Jah.
Ainuke asi, mis määratleb sõlme kui asi
on typedef ise.
Aga kui selle punkti, kui me sellist parsing läbi selle struct tipp määratlus,
me ei ole valmis meie typedef veel, et kuna typedef pole lõpetanud,
sõlme ei eksisteeri.
Aga struct sõlme teeb, ja see sõlme siin,
see võib nimetada ka midagi muud.
Seda võiks nimetada n.
Seda võib nimetada seotud nimekirja sõlme.
Seda võib nimetada midagi.
Aga see struct tipp tuleb kutsuda sama asi kui see struct tipp.
Mida te nimetate seda peab ka siin olema,
ja nii, et vastab ka teises punktis küsimus
mistõttu-palju kordi, kui näed structs ja typedefs kohta structs,
näete anonüümne structs kus saad lihtsalt näha typedef struktuure,
rakendamise struktuure, sõnastik, või mis iganes.
>> Miks siin me peame ütlema sõlme?
Miks ei saa see olla anonüümne struct?
See on peaaegu sama vastus.
[Student] Sa pead viitama jooksul struct.
Jah jooksul struct, peate viitama struct ise.
Kui te ei anna struct nimi, kui see on anonüümne struct, siis ei saa sellele viidata.
Ja last but not least-need peaksid olema mõnevõrra arusaadav,
ja need peaksid aitama teil mõista, kui olete kirjalikult selle alla
et sa teed midagi valesti, kui neid erinevaid asju ei ole mõistlik.
Last but not least, miks see peab olema struct tipp *?
Miks ei saa see lihtsalt olla vatseti sõlme edasi?
[Student] kursor järgmisele struct.
See on paratamatult seda, mida tahame.
Miks see võiks kunagi olla struct tipp edasi?
Miks see peab olema struct tipp * edasi? Jah.
[Student] See on nagu lõputu silmuse.
Jah.
[Student] See oleks kõik ühes.
Jah, lihtsalt mõelda, kuidas me teeks suurus või midagi.
Suurus struct on põhimõtteliselt + või - mõni muster siin või seal.
See on põhimõtteliselt saab olema summa suuruses asju struct.
See siin, muutmata midagi, suurus saab olema lihtne.
Suurus struct tipp saab olema suurus i + suuruse kõrval.
Suurus i saab olema 4. Suurus järgmise saab olema 4.
Suurus struct tipp saab olema 8.
Kui meil ei ole *, mõtlesin sizeof,
siis sizeof (i) saab olema 4.
Suurus struct tipp kõrval saab olema suurus i + suurus struct tipp kõrval
+ Suurus i + suurus struct tipp kõrval.
Oleks lõpmatu rekursiooni sõlmede.
See on põhjus, miks see on, kuidas asjad peavad olema.
>> Jällegi, kindlasti meelde, et
või vähemalt mõista seda piisavalt, et võite olla võimeline
põhjusel läbi, mida ta peaks nägema.
Asju, mida me ei kavatse soovite rakendada.
Kui pikkus nimekirja-
sa petad ja hoida umbes
globaalse pikkus või midagi, aga me ei kavatse seda teha.
Me loen pikkus nimekirja.
Oleme sisaldab, nii see on põhimõtteliselt nagu otsing,
nii et meil on seotud nimekirja täisarvud, et näha, kui see täisarv on seotud nimekirja.
Nimedele läheb sisestada alguses nimekirja.
Liida läheb sisestada lõpus.
Insert_sorted läheb lisada järjestatud positsiooni nimekirja.
Insert_sorted liiki eeldab, et oled kunagi kasutanud nimedele või lisada halva viisil.
>> Insert_sorted kui sa rakendamisel insert_sorted-
oletame, et meil on seotud nimekirja.
See on see, mida ta praegu välja näeb, 2, 4, 5.
Ma tahan lisada 3, nii kaua, kui nimekiri ise on juba sorteeritud,
see on lihtne leida kus 3 kuulub.
Hakkan temperatuuril 2.
Okei, 3 on suurem kui 2, nii et ma tahan edasi.
Oh, 4 on liiga suur, nii et ma tean 3 kavatse minna 2 kuni 4,
ja ma pean määrata viiteid ja kõik see kraam.
Aga kui me ei ole rangelt kasutada insert_sorted,
meeldib ütleme lihtsalt ma ülaloleva 6
siis minu lingitud nimekiri läheb muutunud see.
See nüüd ei ole mõtet, nii insert_sorted, saate lihtsalt eeldada
et nimekiri on sorteeritud, kuigi tegevus olemas
mis võib põhjustada seda ei saa lahendada, ja ongi kõik.
Leia kasulik lisada-nii need on peamised asjad, mida sa lähed on rakendada.
>> Sest nüüd, võta minut aega, et teha pikk ja sisaldab
ja need peaks olema suhteliselt kiire.
Lähenemas sulgemise aeg, et keegi on midagi pikkus või sisaldab?
Nad ei kavatse olla peaaegu identsed.
[Student] pikkus.
Vaatame, läbivaatamine.
Okei.
Sa tahad seletada?
[Student] Ma lihtsalt luua kursori sõlme ja initsialiseerida ta kõigepealt, mis on meie globaalse muutuja,
ja siis ma vaadata, kui see on null nii et ma ei saa SEG süü ja tagastab 0, kui see on nii.
Muidu ma ahela kaudu, jälgimine jooksul täisarv
mitu korda olen avanud järgmise elemendi nimekirja
ja samas juurdekasvu töö juurde ka, et tegelik element,
ja siis ma pidevalt tegema vaadata, kui see on null,
ja kui see on null, siis katkestab ja lihtsalt tagastab elementide arvu olen avanud.
>> [Rob B.] Kas keegi on mingeid kommentaare midagi?
See tundub hea õigsuse tark.
[Student] Ma ei usu, teil on vaja sõlme == null.
Jah, nii et kui sõlm == null return 0.
Aga kui sõlme == null, siis see-oh, on õigsuse küsimus.
See oli lihtsalt naasete i, kuid see ei ole ulatuselt kohe.
Sa lihtsalt vaja int i, nii et i = 0.
Aga kui sõlm on null, siis ma ikka saab olema 0,
ja me ei kavatse naasta 0, seega antud juhul on identsed.
Teine levinud asi on hoida deklaratsioon
sõlme sees jaoks silmus.
Võiks öelda, oh, ei.
Jätame selle, kuna see.
Ma oleks ilmselt panna int i = 0 siin,
siis sõlme * sõlm = esimesena siin.
Ja see on ilmselt kuidas-vabanemiseks see nüüd.
See on ilmselt kuidas ma oleksin selle kirjutanud.
Sa võid ka-vaadates seda niimoodi.
See loop struktuur siinsamas
peaks olema peaaegu sama loomulik teile nagu int i = 0
i on väiksem kui pikkus massiivi i + +.
Kui see on, kuidas sa itereerime massiiv, on see, kuidas sa itereerime seotud nimekirja.
>> See peaks olema teist laadi mingil ajahetkel.
Seda silmas pidades, see saab olema peaaegu sama asi.
Sa lähed tahan kinnitada, üle seotud nimekirja.
Kui lümfisõlm-Mul pole aimugi, milline väärtus on nn.
Sõlme i.
Kui näit sel sõlm = i tagasi true, ja ongi kõik.
Pange tähele, et ainus viis, kuidas kunagi tagasi false
on see, kui me kinnitada, kogu seotud nimekirja ja kunagi tagasi tõsi,
nii see on, mida see teeb.
Nagu pool tähele-me ilmselt ei jõua lisama või ülaloleva.
>> Quick viimase noodi.
Kui näed staatiline märksõna, nii oletame staatilise int count = 0,
siis me teeme count + +, saab põhimõtteliselt ma arvan et kui globaalne muutuja,
kuigi ma just ütlesin see ei ole, kuidas me kavatseme rakendada pikkus.
Ma teen seda siin, ja siis loota + +.
Kuidagi saame alustada sõlme meie seotud nimekirja me incrementing meie arv.
Punkt on see, mida staatiline märksõna tähendab.
Kui mul oli just int count = 0, mis oleks regulaarne vana globaalne muutuja.
Mida staatiline int count tähendab, et see on globaalne muutuja selle faili.
On võimatu mõne muu faili,
meeldib mõelda pset 5, kui olete alustanud.
Sul on nii speller.c, ja sul on dictionary.c,
ja kui sa just kuulutada asi maailmas, siis midagi speller.c
saab kasutada dictionary.c ja vastupidi.
Globaalsed muutujad on kättesaadav ühelegi. C faili
kuid staatilised muutujad on kättesaadavad üksnes seestpoolt faili ennast,
nii seest õigekirjakontrolli või sees dictionary.c,
see on selline, kuidas ma kuulutada minu muutuja suurust minu massiivi
või suurust minu sõnade arv sõnaraamat.
Kuna ma ei taha kuulutada globaalne muutuja, et kellelgi on juurdepääs,
Ma tõesti ainult hoolid teda enda tarbeks.
>> Hea asi see on ka kogu nimi kokkupõrke värk.
Kui mõne muu faili üritab kasutada globaalse muutuja nimega loota, asjad lähevad väga, väga vale,
nii et see kenasti hoiab asju ohutu, ja ainult saate kasutada seda,
ja keegi teine ​​ei saa, ja kui keegi deklareerib globaalse muutuja nimega loota,
siis see ei häiri oma staatiline muutuja nimega loota.
Seda staatilise on. On faili globaalset muutujat.
>> Küsimused midagi?
Kõik komplekti. Nägemist.
[CS50.TV]