[Powered by Google Translate] [Sekcio 6] [Pli Vasta]
[Rob Bowden] [Universitato Harvard]
[Jen CS50.] [CS50.TV]
>> Ni povas direkti al nia sekcio de demandoj.
Mi sendis la adreson por la spaco antaŭe.
La komenco de la sekcio de la demandoj diri-
ŝajne mi ne estas tute unsick-estas tre facila demando
de ĵus kio valgrind?
Kion valgrind fari?
Ĉiu volas diri kion valgrind faras?
[Studenta] Jaques memoro likas.
Yeah, valgrind estas ĝenerala memoro Kontrolilo.
Ĝin, en la fino, informas vin se vi havas memoron fugoj,
kiu estas plejparte kion ni uzas ĝin por ĉar se vi volas
faru bone en la problemo aro aŭ se vi volas
preni en la granda tabulo, vi bezonas havi neniun memoro filtras ajn,
kaj en kazo vi havas memoron fugon ke vi ne povas trovi,
Ankaŭ memoru, ke kiam vi malfermas dosieron
kaj se vi ne fermi ĝin, tio estas memoro fugo.
>> Multaj homoj serĉas iu nodo ke ili ne liberigante
kiam vere, ili ne fermi la vortaro en la unua paŝo.
Ĝi ankaŭ diras al vi se vi havas nevalidan legas aŭ skribas,
kio signifas se vi provas kaj starigis valoro
jen trans la fino de la amaso kaj ne okazas al seg kulpo
sed valgrind kaptas ĝin, kiel vi devus ne vere povas skribi tie,
kaj tiel vi certe ne havas iun el tiuj ankaŭ ne.
Kiel vi uzas valgrind?
>> Estas ĝenerala demando de
ia ruli ĝin kaj rigardi la eligo.
La eligo estas aplastante multajn fojojn.
Ekzistas ankaux amuza eraroj kie se vi havas iujn terure erara afero
okazas en buklo, tiam ĝi estos eble diri, "Vojo tro multaj eraroj.
Mi tuj ĉesos rakonti nun. "
Estas esence tekstajn eligo ke vi devas analizi.
En la fino, ĝi rakontos al vi memoro filtras kiun vi havas,
kiom da blokoj, kiuj povas esti utila ĉar
se estas unu bloko unfreed, tiam ĝi estas kutime pli facile trovi
ol 1.000 blokoj unfreed.
1.000 blokoj unfreed probable signifas ke vi ne liberigante
vian ligitaj lertaj taŭge aŭ iu.
Tio valgrind.
>> Nun ni havas nian sekcion de demandoj,
kion vi ne bezonas elŝuti.
Vi povas klaki sur mia nomo kaj eltiris ilin; en la spaco.
Nun alklaku mi.
Revizio 1 estos pilo, kiun ni faras unue.
Redakto 2 estos vosto, kaj redaktoj 3 estos la sole ligitaj listo.
Dividante per niaj pilo.
Kiel ĝi diras ĉi tie, pilo estas unu el la plej baza,
fundamenta datumstrukturoj de komputiko.
La tre pratipa ekzemplo estas
la pilo de pletoj en la manĝejo.
Estas esence kiam ajn vi estas enkondukita al pilo,
iu tuj diris, "Ho, kiel stako de pletoj."
Vi pilo la pletoj supren.
Tiam, kiam vi iros tiri pleton,
la unua pleto ke tio getting tiris estas la lasta kiu estis metita sur la stako.
La pilo ankaŭ simila diras tie-
ni havas la segmento de memoro nomis la stako.
Kaj kial ĝi nomis la pilo?
>> Ĉar kiel stako datumstrukturo,
ĝi pelas kaj Popoj pilo kadroj en la pilo,
kie pilo kadroj estas kiel specifa alvoko de funkcio.
Kaj kiel stako, vi ĉiam devas reveni
de funkcio alvoko antaŭ ol vi povos akiri malsupren en suba pilo kadroj denove.
Vi ne povas havi ĉefan alvoko foo alvoko stango kaj trinkejo reveno al ĉefa rekte.
Oni ĉiam havas sekvi la ĝentilajn pilo pelante kaj krevi.
La du operacioj, kiel mi diris, estas puŝo kaj popo.
Tiuj estas universalaj terminoj.
Vi devas scii puŝo kaj pop en terminoj de piloj ne gravas.
Ni vidos vostoj estas speco de malsamaj.
Fakte ne havas universalan terminon, sed puŝo kaj pop estas universala por piloj.
Puŝo estas nur surmetis la stako.
Popo estas demeti la stako.
Kaj ni vidas tie ni havas niajn typedef struct pilo,
do ni havos char ** kordoj.
Ne atingas timigitaj de iu **.
Tiu tuj finos esti tabelo de kordoj
aŭ tabelo de punteros al gravuloj, kie
punteros al karakteroj inklinas esti kordoj.
Ĝi ne devas esti kordoj, sed ĉi tie, ili tuj estos kordoj.
>> Ni havas aron da kordoj.
Ni havas grandecon, kiu reprezentas kiom eroj estas nuntempe en la pilo,
kaj tiam ni havas la kapablon, kiu estas kiel multaj eroj povas esti sur la stako.
La kapablo devus dividi kiel io pli granda ol 1,
sed la grandeco tuj dividi kiel 0.
Nun, estas esence tri malsamaj manieroj vi povas pensi pri pilo.
Nu, estas probable pli, sed la du ĉefaj vojoj estas
vi povas apliki ĝin uzante tabelo, aŭ vi povas apliki ĝin uzante ligitaj listo.
Ligitaj listoj ia bagatela por fari piloj de.
Ĝi estas tre facile fari pilo uzante ligitaj lertaj,
do cxi tie, ni tuj faros pilo uzante arrays,
kaj tiam uzanta arrays, ekzistas ankaŭ du manieroj vi povas pensi pri ĝi.
Antaŭe, kiam mi diris ni havas kapablon por la pilo,
do ni povas persvadi ero sur la stako.
>> La vojo povus okazi estas tiel frue kiel vi batis 10 elementoj, tiam vi faris.
Vi eble scias, ke tie estas supera baro de 10 aĵoj en la mondo
ke vi neniam havas pli ol 10 aĵoj en via pilo,
en kiu kazo vi povas havi supera baro sur la grandeco de via pilo.
Aŭ vi povus havi viajn stack esti nebarita,
sed se vi faras tabelo, tio signifas ke ĉiu unuopa kiam vi batis 10 elementoj,
tiam vi tuj devas kreski ĝis 20 eroj, kaj kiam vi batis 20 elementoj,
vi tuj devos kreski vian tabelo al 30 eroj aŭ 40 eroj.
Vi tuj bezonas pliigi la kapablon, kiu estas tio, kion ni faros ĉi tie.
Ĉiu unuopa tempo ni atingos la maksimuman grandecon de nia stako,
kiam ni puŝi ion alian, ni tuj bezonas pliigi la kapablon.
Tie, ni puŝon deklarita kiel bool puŝo (char * str).
Char * str estas la ĉeno kiu ni puŝas sur la pilo,
kaj bool nur diras ĉu ni sukcesis aŭ malsukcesis.
>> Kiel ni povas ne?
Kio estas la sola cirkonstanco, ke vi povas pensi pri
kie ni bezonus por reveni falsa?
Yeah.
[Studenta] Se estas plena kaj ni uzas barita efektivigo.
Yeah, do kiel ni difinas-li respondis
se ĝi estas plena kaj ni uzas barita efektivigo.
Tiam ni definitive reveni falsaj.
Tuj kiam ni batis 10 aĵoj en la tabelo, ni ne povas persvadi 11, do ni revenos falsaj.
Kio se ĝi nebarita? Yeah.
Se vi ne povas pligrandigi la tabelo por iu kialo.
Yeah, do memoro estas limigita rimedo,
kaj finfine, se ni plenumas pelante aĵoj sur la stako denove kaj denove,
ni iras al provi kaj destini pli granda tabelo por persvadi
la pli granda kapablo, kaj malloc aŭ kion ajn ni uzas tuj revenos falsaj.
Nu, malloc revenos nula.
>> Memoru, ĉiu sola fojo vi iam nomas malloc, vi devus kontroli por vidi se ĝi
Revenas nula alie kiu estas praveco dedukto.
Ĉar ni volas havi nebarita pilo,
la sola kazo ni tuj estos reveni falsa estas, se ni provu
pliigi la kapablon kaj malloc aŭ kion ajn revenas falsaj.
Tiam popo prenas neniun argumenton,
kaj denove la kordo, kiu estas sur la supro de la stako.
Kion ajn estis plej laste puŝis sur la stako estas kion popo revenas,
kaj ankaŭ forigas ĝin de la stako.
Kaj rimarki ke ĝi revenas nula se estas nenio sur la stako.
Estas ĉiam ebla, ke la pilo estas malplena.
En Java, se vi uzas por tio, aŭ aliaj lingvoj,
provante popo el malplena stako povus kaŭzi escepto aŭ iu.
>> Sed en C, nula estas speco de granda parto de la kazoj kiel ni manipuli ĉi tiujn problemojn.
Reveni nula estas kiel ni iras por signifi ke la pilo estis malplena.
Ni provizis kodo kiu estos provi vian pilo de funcionalidad,
apliki puŝi kaj popo.
Tiu ne estos multe da kodo.
Mi-fakte, antaŭ ol ni faras tion, aludo, aludo-
se vi ne vidis ĝin, malloc ne estas la sola funkcio
ke allocates memoro sur la havaĵon por vi.
Ekzistas familio de alloc funkcioj.
La unua estas malloc, kiu vi kutimi.
Tiam ekzistas calloc, kiu faras la samon kiel malloc,
sed ĝi nulo ĉio por vi.
Se vi iam volis agordi cxion al nula post mallocing ion
vi devus nur uzi calloc en la unua loko anstataŭ skribi
a por buklo al nulo ekster la tutan blokon de memoro.
>> Realloc estas kiel malloc kaj havas multajn specialajn kazojn,
sed esence kio realloc faras estas
prenas puntero kiu estis jam asignitaj.
Realloc estas la funkcio vi volas esti fiksi tie.
Ĝi portas puntero ke jam estis reveninta de malloc.
Imagu ke vi petas de malloc puntero de 10 bajtoj.
Tiam poste oni rimarkas vi volis 20 bitokoj,
tiel vi nomas realloc sur tiu puntero kun 20 bitokoj,
kaj realloc aŭtomate kopii super ĉion por vi.
Se vi ĵus nomis malloc denove, kiel mi havas blokon de 10 bajtoj.
Nun mi bezonas bloko de 20 bajtoj,
do se mi malloc 20 bajtoj, do mi devas permane kopii super la 10 bitokoj de la unua horo
en la dua afero kaj tiam senpaga la unuan aferon.
Realloc manipulos, ke por vi.
>> Rimarki la subskribo tuj estos dezerta *,
kio estas ĝuste reveni puntero al la bloko de memoro,
tiam void * ptr.
Vi povas pensi void * kiel ĝenerala puntero.
Ĝenerale, oni neniam pritrakti void *,
sed malloc revenas al dezerta *, kaj tiam ĝi estas ĝuste uzata kiel
ĉi tiu estas vere tuj estos char *.
La antaŭa dezerta * kiu estis redonita de malloc
nun tuj estos pasitaj al realloc, kaj tiam grandeco
estas la nova numero de bajtoj vi volas atribui, do via nova kapablo.
Mi donos al vi post kelkaj minutoj, kaj fari ĝin en nia spaco.
Komencu kun redaktoj 1.
Mi haltos vin post espereble pri sufiĉa tempo por apliki puŝo,
kaj tiam Mi donos al vi alian rompon fari popo.
Sed vere ne estas tiel multe kodo ajn.
La plej kodo estas probable la ekspansio stuff, pligrandigante la kapablo.
Konsentite, neniu premo esti tute farita,
sed tiel longe kiel vi sentas kiel vi estas sur la ĝusta vojo, tio estas bona.
>> Ĉu iu havas kodo sentas komfortaj kun mi tirante kolektis?
Yeah, mi volas, sed ne iu havas kodon mi povas tiri supren?
Konsentite, vi povas komenci, konservu ĝin, kion ajn ĝi estas?
Mi ĉiam forgesas ke paŝo.
Okay, rigardante puŝo,
Kion ili volas klarigi vian kodon?
[Studenta] Unue, mi pliigis la grandecon.
Mi supozas eble mi devus havi tiun-ĉiuokaze, mi pliigis la grandecon,
kaj mi vidas se estas malpli ol la kapablo.
Kaj se ĝi estas malpli ol la kapablo, mi aldonas al la tabelo, ke ni jam havas.
Kaj se ĝi ne estas, mi multipliki la kapablo per 2,
kaj mi reallocate la kordoj tabelo al iu kun pli granda kapablo grandeco nun.
Kaj poste se tio malsukcesas, mi diras al la uzanto kaj reveni falsa,
kaj se ĝi estas bone, tiam mi metis la ŝnuron en la nova loko.
>> [Rob B.] Ankaŭ rimarki, ke ni uzis belan bitlarĝa operatoro tie
multipliki per 2.
Memoru, maldekstra movo ĉiam tuj estos multiplikita per 2.
Ĝuste ŝanĝo estas dividita per 2 tiom longe kiom vi memoras, ke tio signifas
dividi per 2 kiel en entjera dividita per 2.
Eble senpintigas 1 tie aŭ tie.
Sed movo lasita de 1 estas ĉiam tuj estos multiplikita per 2,
se vi ne superfluas la limojn de la entjero, kaj tiam ne estos.
Al flanko komento.
Mi ŝatas do-ĉi ne tuj ŝanĝas la kodigo iamaniere ajn,
sed mi ŝatas fari ion kiel ĉi tio.
Ĝi fakte tuj fari ĝin iomete pli longa.
Eble ĉi tio ne estas la perfekta kazo montri tion,
sed mi ŝatas segmento gxin en tiujn blokojn de-
estas bone, se ĉi se okazas, tiam Mi faros ion,
kaj tiam la funkcio estas farita.
Mi ne bezonas do rulumu miaj okuloj tuta vojo malsupren la funkcio
por vidi, kio okazas post la alia.
Estas se ĉi se okazas, tiam mi simple reveni.
Ĝi ankaŭ havas la belan aldonis profito de ĉio ekster tio
nun ŝanĝis lasis unufoje.
Mi ne plu bezonas-se vi iam proksime ridinde longajn liniojn,
tiam tiuj 4 bajtoj povas helpi, kaj ankaŭ la pli maldekstra io estas,
la malpli premita vi sentas se like-bone, mi devas memori
Mi nuntempe en kiam buklo ene de alia ene de a por buklo.
Ie ajn vi povas fari ĉi reveno tuj, mi specon de kiel.
Estas tute laŭvola kaj ne atendita en ajna formo.
>> [Studenta] Should ekzistos grandecon - en la fail kondiĉo?
La fail kondiĉo tie ni ne realloc, do jes.
Rimarku kiel en la fail kondiĉo, supozeble,
krom se ni liberan stuff poste, ni ĉiam tuj malsukcesos
negrave kiom da fojoj ni provos puŝi ion.
Se ni observas puŝante, ni observu pliigante grandeco,
kvankam ni ne meti ion sur la stako.
Kutime ni ne pliigo de la grandeco ĝis
post ni sukcese metis ĝin sur la stako.
Ni devus fari tion, diru, ĉu tie kaj tie.
Kaj tiam anstataŭ diri s.size ≤ kapablo, estas malpli ol kapablo,
nur ĉar ni kopiis kie ĉiu estis.
>> Kaj memoru, la sola loko, kiun ni povus reveni malvera
estas tie, kie realloc revenis nula,
kaj se vi hazarde memoras norma eraro,
eble vi povus konsideri tiun kazon, kie vi volas presi norma eraro,
tiel fprintf stderr anstataŭ ĝuste presi rekte al la normo eksteren.
Denove, tio estas ne espero, sed se ĝi estas eraro,
tajpi printf, tiam vi eble volas fari ĝin presi al norma eraro anstataŭ normo eksteren.
>> Ĉiu havas nenion alian por noti? Jes.
[Studenta] Ĉu vi povas iri super la [inaudible]?
[Rob B.] Jes, la reala binariness de ĝi aŭ nur kio estas?
[Studenta] Do vi multipliku ĝin per 2?
[Rob B.] Jes, esence.
En duuma tero, ni ĉiam havas nia aro de ciferoj.
Sxangxigxantaj ĉi maldekstra per 1 esence enmetas ĝin ĉi tie ĉe la dekstra flanko.
Reen al tio, nur memori ke ĉio en duuma
estas povo de 2, tiel ĉi reprezentas 2 al la 0,
ĉi 2 al la 1, ĉi 2 al la 2.
Per enmeto de 0 al la dekstra flanko nun, ni nur ŝanĝi ĉio finita.
Kio iam estis 2 al la 0 nun 2 al la 1, estas 2 al la 2.
La dekstra flanko, ke ni insertos
estas nepre destinita por 0,
kiu faras sencon.
Se vi iam multipliki numeron per 2, ĝi ne iras por fini nepara,
do la 2 al la 0 loko devus esti 0,
kaj ĉi tiu estas kion mi duonon avertita pri antaŭe estas se vi hazarde ŝanĝi
trans la nombro de bitoj en entjero,
tiam ĉi 1 tuj finos pafante.
Tio estas la sola zorgo se vi hazarde estos kontraktanta kun vere granda kapabloj.
Sed je tiu punkto, tiam vi pritraktas aron da miliardoj da aĵoj,
kiu eble ne havas en memoro ĉiuokaze.
>> Nun ni povas alveni al popo, kiu estas eĉ pli facila.
Vi povus fari ĝin kiel se vi hazarde popo tuta amaso,
kaj nun vi estas en duono kapablo denove.
Vi povus realloc encoger la kvanto de memoro vi havas,
sed vi ne devas zorgi pri tio, do la sola realloc kazo tuj estos
kreskanta memoro, neniam ŝrumpanta memoro,
kion tuj faros popo super facila.
Nun vostoj, kiu tuj estos kiel piloj,
sed la ordo, kiun vi prenos aferojn renversas.
La pratipa ekzemplo de vosto estas linio,
do versxajne se vi estus anglo, mi dirus
pratipa ekzemplo de vosto estas vico.
Do kiel linio, se vi estas la unua persono en linio,
vi atendas esti la unua persono el la linio.
Se vi estas la lasta persono en linio, vi tuj estos la lasta persono utilita.
Ni nomas tion FIFO mastro, dum pilo estis LIFO ŝablono.
Tiuj vortoj estas bela universala.
>> Kiel piloj kaj kontraste arrays, vostoj tipe ne permesas aliron al elementoj en la mezo.
Ĉi tie, pilo, ni havas puŝo kaj popo.
Tie, ni hazarde ilin vokis enqueue kaj dequeue.
Mi ankaŭ aŭdis ilin nomis movo kaj unshift.
Mi aŭdis homojn diri puŝo kaj pop ankaŭ aplikas al vostoj.
Mi aŭdis enigi, demeti,
tiel puŝi kaj popo, se vi parolas pri piloj, vi puŝas kaj krevi.
Se vi parolas pri vostoj, vi povus preni la vortoj vi volas uzi
por inserción kaj forigo, kaj ne ekzistas konsento sur kio ĝi devus nomi.
Sed cxi tie, ni havas enqueue kaj dequeue.
Nun, la struct aspektas preskaŭ identa al la pilo struct.
Sed ni devas konservi trako de kapo.
Mi supozas diras cxi tie, sed kial ni bezonas la kapo?
La prototipoj estas esence identa al puŝi kaj popo.
Vi povas pensi pri tio kiel puŝo kaj popo.
La sola diferenco estas popo revenas-anstataŭ la lasta, ĝi estas redonante la unua.
2, 1, 3, 4, aŭ io.
Kaj jen la komenco.
Nia vosto estas tute plena, do tie estas kvar elementoj en ĝi.
La fino de nia vosto estas nuntempe 2,
kaj nun ni iru por enmeti ion alian.
>> Kiam ni volas enmeti ke ion alian, kion ni faris por la pilo versio
estas ni etendis nian bloko de memoro.
Kio estas la problemo pri tio?
[Studenta] Vi movas la 2.
Kion mi diris antaŭe pri la fino de la vosto,
ĉi tio ne havas sencon, ke ni komencu je 1,
tiam ni volas dequeue 1, tiam dequeue 3, tiam dequeue 4,
tiam dequeue 2, tiam dequeue ĉi tiu.
Ni ne povas uzi realloc nun,
aŭ almenaŭ, vi devas uzi realloc en malsama maniero.
Sed vi probable ne devus nur uzi realloc.
Vi tuj devos permane kopii vian memoron.
>> Estas du funkcioj kopii memoro.
Estas memcopy kaj memmove.
Mi nuntempe legas la viro paĝoj vidi kiuj vi tuj volas uzi.
Konsentite, memcopy, la diferenco estas
ke memcopy kaj memmove, unu manipulas la kazo ĝuste
kie vi kopiado en regiono kiu okazas por koincidigi la regiono
vi kopiado de.
Memcopy ne manipulas ĝin. Memmove faras.
Vi povas pensi pri la problemo kiel-
diru mi volas kopii ĉi ulo,
ĉi tiuj kvar al ĉi ulo super.
En la fino, kion la tabelo devas rigardi kiel
post la kopio estas 2, 1, 2, 1, 3, 4, kaj tiam iuj frandajxojn cxe la fino.
Sed ĉi tiu estas dependa de la ordo en kiu ni vere kopii,
ĉar se ni ne konsideras la fakton ke la regiono ni kopiado en
parte kovras unu ni kopiado de,
tiam ni povus fari kiel komenco tie, kopii la 2 en la loko kiun ni volas iri,
tiam movi niajn punteros antaŭen.
>> Nun ni tuj estos tie kaj tie, kaj nun ni deziras kopii
ĉi ulo super ĉi ulo kaj movi niajn punteros antaŭen.
Kion ni tuj finos atingi estas 2, 1, 2, 1, 2, 1
anstataŭ la taŭga 2, 1, 2, 1, 3, 4 ĉar
2, 1 overrode la originala 3, 4.
Memmove manipulas ke ĝuste.
En ĉi tiu kazo, esence nur ĉiam uzi memmove
ĉar ĝi manipulas ĝin ĝuste.
Ĝi ĝenerale ne plenumi ian ajn malbona.
La ideo estas anstataŭ ekde la komenco kaj kopii ĉi vojo
kiel ni ĵus faris ĉi tie, ĝi komenciĝas de la fino kaj kopias en,
kaj en tiu kazo, vi neniam povas havi problemon.
Tie estas neniu agado perdita.
Ĉiam uzi memmove. Neniam zorgu pri memcopy.
Kaj tie estas kie vi tuj devas aparte memmove
la envolvis-ĉirkaŭ parton de via vico.
No worries se ne tute farita.
Ĉi tio estas pli malfacila ol pilo, puŝo, kaj popo.
>> Iu havas kodon ni povus labori kun?
Eĉ se tute nekompleta?
[Studenta] Jes, ĝi estas tute nekompleta, though.
Tute nekompleta estas fajna tiel longe kiel ni-povas vin savi la revizio?
Mi forgesas ke ĉiu unuopa tempo.
Konsentite, ignorante kio okazas kiam ni bezonas regrandigi aĵoj.
Tute ignori Regrandigi.
Klarigu tiun kodon.
Mi kontrolas unue se la amplekso estas malpli ol la kopio unue
kaj post tio, mi enmetas-Mi prenas kapo + grandeco,
kaj mi certigas ĝin envolvas ĉirkaŭ la kapablo de la tabelo,
kaj mi enŝovu la novan ĉenon en tiu pozicio.
Tiam mi pliigi la grandeco kaj reveni vera.
>> [Rob B.] This is definitive unu el tiuj kazoj kie vi tuj volas esti uzante mod.
Ajna speco de kazo kie vi kroĉas ĉirkaŭe, se vi pensas envolviendo ĉirkaŭe,
la tuja penso devus esti mod.
Kiel rapida optimumigo / faros vian kodo unu linio pli mallonga,
vi rimarkos ke la linio tuj post ĉi tiu
estas nur grandecon + +, do vi kunfandi ke en tiu linio, grandeco + +.
Nun cxi tie, ni havas la kazon
kie ni ne havas sufiĉan memoron,
do ni pliigas nian kapablon por 2.
Mi supozas ke vi povus havi la saman problemon tie, sed ni povas ignori ĝin nun,
kie se vi fiaskis pliigi vian kapablon,
tiam vi tuj volas malpliigi vian kapablon per 2 denove.
Alia mallonga noto estas kiel vi povas fari + =,
vi povas ankaŭ fari << =.
Preskaŭ ĉio povas iri antaux egalas, + =, | =, & =, << =.
Char * nova estas nia nova bloko de memoro.
Ho, super tie.
>> Kion homoj pensas pri la tipo de nia nova bloko de memoro?
[Studenta] Ĝi devus esti char **.
Pensante reen al nia struct tien,
kordoj estas kion ni reallocating.
Ni faras tutan novan dinamika stokado por la elementoj en la vico.
Kion ni tuj estos atribui al viaj kordoj estas kion ni mallocing ĝuste nun,
kaj tiel nova tuj esti char **.
Ĝi tuj estos tabelo de kordoj.
Tiam kio estas la kazo, sub kiu ni tuj revenos falsa?
[Studenta] Ĉu eblas fari la char *?
[Rob B.] Jes, bona alvokon.
[Studenta] Kio estis tio?
[Rob B.] Ni volis fari grandeco de char * ĉar ni jam ne estas-
tio efektive estus tre granda problemo ĉar sizeof (char) devus esti 1.
Sizeof char * tuj estos 4,
tiom multe da fojoj kiam vi pritraktas ints,
vi emas foriri per ĝi ĉar grandeco de int kaj grandeco de int *
sur 32-bita sistemo tuj estos la sama afero.
Sed ĉi tie, sizeof (char) kaj sizeof (char *) nun tuj estos la sama afero.
>> Kio estas la cirkonstanco kie ni revenos falsa?
[Studenta] Novaj estas nula.
Yeah, se novaj estas nula, ni revenas falsa,
kaj mi tuj ĵetu malsupren tie-
[Studenta] [inaudible]
[Rob B.] Jes, tio estas fajna.
Vi povus ĉu do 2 fojoj kapablo aŭ kapablo shift 1 kaj tiam nur starigis gxin tie aŭ kion ajn.
Ni tion faros kiel ni havis ĝin.
Kapablo >> = 1.
Kaj vi neniam iras al devas maltrankviligi perdi la 1-oj lokon
ĉar vi forlasis moviĝis per 1, do la 1-oj loko estas nepre a 0,
so right movo per 1, vi ankoraŭ tuj estos bone.
[Studenta] Do vi bezonas tion antaux reveno?
[Rob B.] Jes, tio faras absolute neniu senco.
>> Nun supozu nin tuj finos reveni fidela al la fino.
La vojo ni faros tiujn memmoves,
ni bezonas esti zorgema kun ni kiel fari ilin.
Ĉu iu havas sugestojn por kiel ni faras ili?
Jen nia komenco.
Neeviteble, ni volas komenci komence denove
kaj kopio aĵojn en el tie, 1, 3, 4, 2.
Kiel vi faris tion?
Unue, mi devas rigardi la viron paĝo memmove denove.
Memmove, ordono de argumentoj estas ĉiam grava.
Ni volas nian destinon unua, fonto dua, grandeco tria.
Ekzistas multaj funkcioj kiu inversigi fonto kaj celo.
Destino, fonto inklinas esti konsekvenca tiel.
Movado, kio ĝin reveni?
Ĝi redonas puntero al destino, ial ajn vi eble volas tion.
Mi povas bildon legis ĝin, sed ni volas movi al nia celo.
>> Kio estas nia destino tuj estos?
[Studenta] Novaj.
[Rob B.] Jes, kaj kien ni kopiado el?
La unua afero kiun ni kopiado estas ĉi 1, 3, 4.
Kio estas la-ĉi 1, 3, 4.
Kio estas la adreso de ĉi 1?
Kio estas la adreso de tiu 1?
[Studenta] [inaudible]
[Rob B.] Kapo + la adreso de la unua ero.
Kiel ni preni la unua elemento en la tabelo?
[Studenta] Queue.
[Rob B.] Jes, q.strings.
Memoru, tie, nia kapo estas 1.
Darn ĝin. Mi nur pensas, ke estas magie-
Jen, nia kapo estas 1. Mi tuj ŝanĝos mian koloron tro.
Kaj jen kordoj.
Ĉi tio, ni povas aŭ skribi ĝin kiel ni faris ĉi tie
kun kapoj + q.strings.
Multaj homoj ankaŭ skribi ĝin & q.strings [kapo].
Tio ne estas vere neniu malpli efika.
Vi eble pensas pri ĝi kiel vi dereferencing ĝin kaj tiam ricevas la adreson de,
sed la tradukilo tuj traduki ĝin al kion ni havis antaŭ ĉiuokaze, q.strings + kapo.
Either way vi volas pensi pri ĝi.
>> Kaj kiom da bitokoj ni deziras kopii?
[Studenta] Kapablo - kapo.
Kapablo - kapo.
Kaj tiam vi povus skribi ĉiam ekster ekzemplo
deĉifri ĉu tio estas prava.
[Studenta] Bezonas esti dividita per 2 tiam.
Yeah, do mi supozas ke ni povus uzi grandeco.
Ni ankoraŭ havas grandecon esti-
uzante grandeco, ni havas grandecon egalan al 4.
Nia grandeco estas 4. Nia estro estas 1.
Ni volas kopii tiuj 3 elementojn.
Tio estas la prudenton kontrolu ke grandeco - kapo estas korekte 3.
Kaj revenante tie, kiel ni diris antaŭe,
se ni uzas kapablo, tiam ni devus dividi per 2
ĉar ni jam kreskinta nia kapablo, do anstataŭe, ni tuj uzos grandeco.
Ke kopioj tiu porcio.
Nun, ni devas kopii la alia parto, la porcio, kiu restis el la komenco.
>> Tio tuj memmove en kio pozicio?
[Studenta] Plus grandeco - kapo.
Jes, do ni jam kopiis en grandeco - kapo bajtoj,
kaj tiel, kie ni volas kopii la ceteraj bitokoj estas nova
kaj tiam grandeco minus-bone, la nombro de bitokoj ni jam kopiis in
Kaj poste kien ni kopiado el?
[Studenta] Q.strings [0].
[Rob B.] Jes, q.strings.
Ni povis ĉu fari & q.strings [0].
Ĉi tiu estas signife malpli komuna ol ĉi tiu.
Se ĝi estas ĵus tuj esti 0, tiam vi emas vidi q.strings.
Tie estas kie ni kopiado de.
Kiom da bajtoj do ni forlasis kopii? >> [Studenta] 10.
Ĝuste.
[Studenta] Do ni devas multipliki 5 - 10 fojoj la grandeco de la bajtoj aŭ ion?
Yeah, do ĉi tiu estas kie-kio ekzakte ni kopiado?
[Studenta] [inaudible]
Kio estas la tipo de la aĵo ni kopiado?
[Studenta] [inaudible]
Yeah, do la char * s, ke ni kopias, ni ne scias kie tiuj venas de.
Nu, kie ili estas montrante, kiel la kordojn, ni finos puŝante ĝin sur la vosto
aŭ enqueuing sur la vosto.
Kie tiuj venas de, ni ne havas ideon.
Ni nur bezonas kontroli kiu faras la char * s mem.
Ni ne volas kopii grandeco - kapo bajtoj.
Ni volas kopii grandeco - kapo char * s,
do ni tuj multipliki ĉi tiu per sizeof (char *).
Sama cxi tie, estro * sizeof (char *).
>> [Studenta] Kio pri [inaudible]?
Tiu rajto tie?
[Studenta] Ne, sube la grandeco - kapo.
[Rob B.] Ĉi tie ĉi?
Pointer aritmetiko.
Kiel puntero aritmetiko tuj labori estas
ĝi aŭtomate multiplikas per la grandeco de la tipo kiu ni pritraktas.
Ĝuste kiel ĉi tie, nova + (grandeco - kapo)
Estas ekzakte ekvivalenta al & nova [size - kapo]
gxis ni atendas ke por funkcii ĝuste,
ĉar se ni pritraktas la int tabelo, tiam ni ne indekso de int-
aŭ se ĝi estas de amplekso de 5 kaj vi volas la 4a ero, tiam ni indekson en la
int tabelo [4].
Vi ne batu-[4] * grandeco de int.
Kiu manipulas ĝin aŭtomate, kaj ĉi tiu kazo
estas laŭvorte ekvivalenta, do la krampo sintakso
Estas ĝuste tuj estos konvertita al ĉi tiel frue kiel vi kompili.
Tio estas io, kion vi bezonas atenti de tiu
kiam vi aldonas grandeco - kapo
vi aldonante ne unu bajto.
Vi aldonante char *, kio povas esti unu bitokoj aŭ kion ajn.
>> Aliaj demandoj?
Konsentite, dequeue tuj estos pli facila.
Mi donos al vi unu minuto apliki.
Ho, kaj mi supozas ĉi tiu estas la sama situacio kie
kion la enqueue kazo, se ni enqueuing nula,
eble ni volas manipuli ĝin, eble ni ne havas.
Ni ne faros ĝin denove ĉi tie, sed sama kiel nia stako kazo.
Se ni enqueue nula, oni eble volas ignori ĝin.
Ĉiu havas iom da kodo mi povas tiri supren?
[Studenta] Mi nur devas dequeue.
Versio 2 estas tiu-okay.
Vi volas klarigi?
[Studenta] Unue, vi certigi ke estas io en la vosto
kaj kiu la grandeco estas subiro per 1.
Vi devas fari tion, kaj tiam vi revenos al la kapo
kaj poste movi la kapon 1.
Konsentite, do estas angulo kazo ni devas konsideri. Yeah.
[Studenta] Se via kapo estas en la lasta elemento,
tiam vi ne volas kapon al punkto ekster de la tabelo.
>> Yeah, do tiel frue kiel kapo batas la fino de nia tabelo,
kiam ni dequeue, nia kapo estu modded reen al 0.
Bedaŭrinde, ni ne povas fari tion en unu paŝo.
Mi supozas ke la vojo mi probable ripari ĝin estas
ĉi tiu tuj estos char *, kion ni reveni,
kion ajn vi variablo nomo volas esti.
Tiam ni volas mod kapo por nia kapablo
kaj tiam revenu ret.
Multaj homoj tie ili agu-
ĉi tiu estas la kazo de-you'll vidi homon fari se kapo
estas pli granda ol kapablo, do kapo - kapablo.
Kaj tio nur funkcias ĉirkaŭ kio mod estas.
Kapo mod = kapablo estas multe pli pura
de kroĉas ĉirkaŭ ol se kapo granda ol kapablo kapo - kapablo.
>> Demandoj?
Konsentite, la lasta afero ni forlasis estas nia ligillisto.
Vi povus esti uzata por iu el la ligitaj listo konduton, se vi faris
ligitaj listoj en via hash tabloj, se vi faris hash tablo.
Mi forte rekomendas fari hash tablo.
Vi eble jam faris trie,
sed klopodoj estas pli malfacila.
En teorio, ili estas asimptote pli bona.
Sed ĝuste rigardi la grandan tabulon,
kaj provas neniam faros pli bona, kaj ili prenu pli memoro.
Ĉion pri provas finas esti malbona por pli da laboro.
Estas kion David Malan la solvon ĉiam estas
Estas li ĉiam afiŝojn sia trie solvo, kaj ni vidu, kie li nun estas.
Kio estis li sub, Davido J?
Li estas # 18, do tio ne terure malbona,
kaj tio tuj estos unu el la plej bonaj provas vi povas pensi pri
aŭ unu el la plej bonaj provas de trie.
Ĉu ne eĉ liaj originalaj solvo?
Mi sentas trie solvoj emas esti pli en ĉi tiu rango de RAM uzado.
>> Iru al la plejsupro kaj RAM-uzado estas en la simpla ciferoj.
Iru al la fundo, kaj tiam vi komencos vidi provas
kie vi ricevis absolute amasa RAM uzado,
kaj klopodoj estas pli malfacila.
Ne tute valoras ĝin sed eduka sperton se vi faris.
La lasta afero estas nia ligillisto,
kaj ĉi tiuj tri aĵoj, piloj, vostoj, kaj kunligita lertaj,
neniu estonteco afero vi iam fari en komputiko
supozos vi havas familiarecon kun tiuj aĵoj.
Ili estas simple tiel fundamenta por ĉio.
>> Ligitaj lertaj, kaj tie ni estas sole ligitaj listo tuj estos nia efektivigo.
Kion unuope ligitaj signifi kiel kontraŭ duoble ligitaj? Jes.
[Studenta] Ĝi nur notas al la sekvanta puntero prefere ol la punteros,
kiel la antaŭira kaj la post tio.
Yeah, do en bildo formato, kion mi ne nur faru?
Mi havas du aĵojn. Mi havas bildon kaj bildoj.
En bildo formato, nia unuope ligitaj lertaj,
neeviteble, ni havas ian sagon al la kapo de nia listo,
kaj poste en nia listo, ni nur devas punteros,
kaj eble ĉi punktoj al nula.
Ĝi tuj estos via tipa desegno de unuope ligitaj listo.
Al duoble ligitaj listo, vi povas iri malantaŭen.
Se mi donas al vi neniun nodo en la listo, tiam vi povas nepre atingos
iu ajn alia nodo en la listo, se estas duoble ligitaj listo.
Sed se mi kaptos vin la tria vertico en la listo kaj ĝi estas sole ligitaj listo,
neniel vi iam ricevos por la unua kaj dua nodoj.
Kaj estas profitojn kaj detriments, kaj unu evidenta unu
estas vi levu pli grandeco, kaj vi devas konservi trako de kie ĉi tiuj aferoj estas montrante nun.
Sed ni nur zorgas pri unuope ligitaj.
>> Kelkajn aferojn ni tuj devos apliki.
Via typedef struct nodo, int i: struct nodo * sekva; nodo.
Ke typedef estu bruligita en viajn mensojn.
Kvizo 1 devus esti kiel doni typedef de ligitaj listo nodo,
kaj vi devus povi tuj scribble ke malsupren
sen eĉ pensi pri ĝi.
Mi supozas paron demandojn, kial ni bezonas struct tie?
Kial ne povas ni diri nodo *?
[Studenta] [inaudible]
Yeah.
La sola afero, kiu difinas nodo kiel afero
estas la typedef mem.
Sed de tiu punkto, kiam ni estas speco de sintaksa analizo tra ĉi struct nodo difino,
ni ne finis nian typedef ankoraŭ, do ekde la typedef ne finis,
nodo ne ekzistas.
Sed struct nodo faras, kaj ĉi nodo en ĉi tie,
ĉi tio povus ankaŭ nomiĝi io alia.
Tio povus esti nomata n.
Ĝi povus esti nomata ligillisto nodo.
Ĝi povus nomi ion.
Sed ĉi struct nodo bezonas nomi la sama afero kiel tio struct nodo.
Kion vi nomas tiun devas ankaŭ esti tie,
kaj por ke ankaŭ respondas la dua punkto de la demando
tial-multe da fojoj kiam vi vidos structs kaj typedefs de structs,
vi vidos anonima structs kie vi nur vidas typedef struct,
efektivigo de struct, vortaro, aŭ kion ajn.
>> Kial ĉi tie ni devas diri nodo?
Kial ne estus anonima struct?
Estas preskaŭ la sama respondo.
[Studenta] Vi devas raporti al tio ene de la struct.
Yeah, ene de la struct, vi devas raporti al la struct mem.
Se vi ne donos la struct nomon, se ĝi estas anonima struct, vi ne povas referi al ĝi.
Kaj laste sed ne malpleje-tiuj devus ĉiuj estos iom simpla,
kaj ili helpos vin realigi se vi skribas ĉi malsupren
ke vi faras ion malĝustan se tiajn aferojn ne havas sencon.
Laste sed ne malpleje, kial ĉi tiu devas esti struct nodo *?
Kial ne povas simple esti struct nodo poste?
[Studenta] Pointer al la sekvanta struct.
Tio estas neeviteble kion ni volas.
Kial povis ĝin neniam struct nodo poste?
Kial ĝi devas esti struct nodo * poste? Yeah.
[Studenta] Estas kiel senfina ciklo.
Yeah.
[Studenta] Estus ĉiuj estos en unu.
Yeah, nur pensi pri kiel ni farus grandeco de aŭ io.
Grandeco de struct estas esence + aŭ - iuj mastro ĉi tie aŭ tie.
Ĝi estas esence tuj estos la sumo de la grandecoj de la aĵoj en la struct.
Tiu rajto tie, sen ŝanĝi ion, la grandeco tuj estos facila.
Grandeco de struct nodo tuj estos grandeco de i + grandeco de alia.
Grandeco de i tuj estos 4. Grandeco de la proksima tuj estos 4.
Grandeco de struct nodo tuj estos 8.
Se ni ne havas la *, pensante pri sizeof,
tiam sizeof (i) tuj estos 4.
Grandeco de struct nodo sekva tuj estos grandeco de i + grandeco de struct nodo sekva
+ Grandeco de i + grandeco de struct nodo proksima.
Estus malfinia rekursio de nodoj.
Jen kial ĉi tiu estas kiel la aferoj devas esti.
>> Denove, definitive enmemorigi ke,
aŭ almenaŭ komprenas sufiĉe ke vi povas atingi
Tial per kio ĝi devus aspekti.
La aferojn kiujn ni tuj volas apliki.
Se longo de la listo-
vi povus trompi kaj observu ĉirkaŭ
tutmonda longeco aŭ ion, sed ni ne faros tion.
Ni tuj kalkulis la longo de la listo.
Ni enhavas, do tio estas esence kiel serĉo,
do ni havos ligitaj listo de entjeroj por vidi se tiun entjero estas en la ligitaj listo.
Prepend tuj enigi en la komenco de la listo.
Append tuj enigi en la fino.
Insert_sorted tuj enigi en la ordo pozicio en la listo.
Insert_sorted ia supozas ke vi neniam uzis prepend aŭ aldonas en malbonaj manieroj.
>> Insert_sorted kiam vi apliki insert_sorted-
diru ni havas niajn ligitaj listo.
Ĉi tio estas kio aktuale aspektas, 2, 4, 5.
Mi volas enmeti 3, do dum la listo mem jam ordo,
ĝi estas facile trovi kie 3 apartenas.
Mi komencos je 2.
Okay, 3 estas pli granda ol 2, do mi volas plu iri.
Ho, 4 estas tro granda, do mi scias 3 tuj iros inter 2 kaj 4,
kaj mi devas korekti punteros kaj cxio, kion aĵoj.
Sed se ni ne strikte uzi insert_sorted,
kiel ni ĵus diris mi prepend 6,
tiam mia ligillisto tuj fariĝis ĉi.
Ĝi nun ne havas senson, do por insert_sorted, vi povas simple supozi
ke la listo estas ordigita, kvankam operacioj ekzistas
kio povas kaŭzi ĝin ne povas ordo, kaj tio estas ĝi.
Trovu helpema insert-do tiuj estas la ĉefaj aĵoj vi tuj devos apliki.
>> Por la momento, prenu unu minuto por fari longa kaj enhavas,
kaj tiuj devus esti relative rapida.
Proksima fermo tempo, do neniu havas ion por longo aŭ enhavas?
Ili iras al esti preskaŭ identaj.
[Studenta] Longa.
Ni vidas, revizio.
Okay.
Vi volas klarigi?
[Studenta] Mi nur krei puntero nodo kaj pravalorizi ĝin al la unua, kiu estas nia tutmonda variablo,
kaj tiam mi kontroli por vidi se ĝi estas nula do mi ne ricevas seg kulpo kaj reveni 0 se tio estas la kazo.
Alie, mi buklo tra, konservanta trako de ene entjero
kiom da fojoj mi Montrita la sekvanta elemento de la listo
kaj en la sama pliigo operacio ankaŭ aliro ke reala elemento,
kaj tiam mi senĉese fari la ĉekon al vidi se ĝi estas nula,
kaj se ĝi estas nula, tiam abortas kaj ĝuste redonas la nombron de elementoj kiujn mi Montrita.
>> [Rob B.] Ĉu iu havas komentoj pri io?
Ĉi aspektas bela praveco saĝa.
[Studenta] Mi ne pensas, ke vi bezonas la nodo == nula.
Yeah, do se nodo == null reveno 0.
Sed se nodo == null tiam ĉi-oh, estas praveco temo.
Ĝi estis nur vi reveni i, sed ne en la medio nun.
Vi nur bezonas int i, do mi = 0.
Sed se nodo estas nula, tiam mi estas ankoraŭ tuj esti 0,
kaj ni tuj revenos 0, tiel ĉi tiu kazo estas identaj.
Alia komuna afero estas, por gardi la deklaro
de nodo ene de la por buklo.
Vi povus diri-oh, ne.
Ni observu ĝin kiel ĉi tio.
Mi verŝajne metos int i = 0 ĉi tie,
tiam nodo * nodo = unua en ĉi tie.
Kaj jen estas probable kiel-liveri de tiu nun.
Tio estas probable ke mi estus skribinta ĝin.
Vi povus ankaŭ-rigardante ĝin kiel ĉi tio.
Ĉi por buklo strukturo ĉi tie
devus esti preskaŭ kiel natura al vi kiel por int i = 0
i estas malpli ol longo de tabelo mi + +.
Se tiel estas kiel vi persisti super tabelo, jen kiel vi persisti super ligitaj listo.
>> Ĉi tiu devus esti dua naturo en iu punkto.
Kun tio en menso, ĉi tiu tuj estos preskaŭ la sama afero.
Vi tuj volas persisti super ligillisto.
Se la nodo-Mi ne havas ideon kion la valoro estas nomita.
Nodo i.
Se la valoro je tiu nodo = i revenos vera, kaj tiu estas ĝi.
Rimarku, ke la sola maniero ni iam revenos malvera
estas, se ni persisti super la tuta ligitaj listo kaj neniam revenas vera,
do tio estas kion ĉi faras.
Kiel noto-ni verŝajne ne atingos aldonas aŭ prepend.
>> Rapida lasta noto.
Se vi vidas la statika ŝlosilvorto, do diru statika int grafo = 0,
tiam ni faros grafo + +, vi povas esence pensas pri ĝi kiel tutmonda variablo,
kvankam mi ĵus diris ĉi tio ne estas kiel ni tuj apliki longa.
Mi faras ĉi tie, kaj tiam kalkulu + +.
Iamaniere oni povas eniri nodo en niajn ligillisto ni pliigante nia grafo.
La punkto de ĉi tio estas kion la statika ŝlosilvorto signifas.
Se mi nur havis int grafo = 0 kiu estus regula malnova malloka variablo.
Kio statika int grafo signifas ke estas malloka variablo por ĉi tiu dosiero.
Estas neebla por iu alia dosiero,
kiel pensi pset 5, se vi komencis.
Vi havas ambaŭ speller.c, kaj vi devas dictionary.c,
kaj se vi simple deklarus afero tutmonda, tiam nenio en speller.c
povas aliri en dictionary.c kaj inverse.
Suma variabloj estas atingebla per neniu. C dosiero,
sed statika variablo estas nur alirebla de ene la dosieron mem,
tiel ene de ortografia kontrolilo aŭ ene de dictionary.c,
ĉi tiu estas speco de kiel mi deklarus mia variablo por la grandeco de mia tabelo
aŭ la grandecon de mia nombro de vortoj en la vortaro.
Ĉar mi ne volas deklari tutmonda variablo kiu neniu havas aliron al,
Mi vere nur zorgas pri ĝi por mia propra uzo.
>> La bona afero pri ĉi tiu estas ankaŭ la tuta nomo kolizio stuff.
Se iu alia dosiero provas uzi tutmonda variablo nomas grafo, aĵoj iras tre tre malbone,
tial ĉi bele subtenas tion sekuraj, kaj nur povas konsenti ĝin,
kaj neniu alia povas, kaj se iu alia deklaras malloka variablo nomas grafo,
tiam ĝi ne malhelpas vian statika variablo nomas grafo.
Tion statika estas. Ĝi estas dosiero malloka variablo.
>> Demandojn sur ion?
Ĉiuj aro. Bye.
[CS50.TV]