[MUZIKO Ludante] 

[VIDEO reprodukto] 

-Li Mensogas. 

-Pri kio? 

-Mi ne scias. 

-Do Kion ni scias? 

-Tio Je 9:15, Ray Santoya estis ĉe la ATM. -Yeah. Do la demando estas, kion li faris je 9:16? 

-Shooting La 9 milimetro je io. Eble li vidis la francotirador. 

-OR Laboris kun li. 

-Wait. Reiru unu. 

-Kio Vi vidas? 

-Bring Sian vizaĝon supren plena ekrano. 

-His Glasojn. 

-There Estas reflekto. 

-ĝi Estas la Nuevitas basbalteamo. Tio estas ilia emblemo. 

-Kaj Li parolas al Kiu surhavas ke jako. 

[FINO reprodukto] 

DAVID Malan: Bone. Jen CS50 kaj ĉi tiu estas iom pli de [inaudible], per kiu vi estas plaŭdado kun problemo starigis kvar. Hodiaŭ ni komencos rigardi iom pli profunde ĉe tion nomis punteros, kiu kvankam ĝi estas bela arcano temo, ĝi rezultas ke ĝi tuj esti la rimedoj, per kiu ni povas komenci konstrui kaj ariganta multe pli kompleksaj programoj. Sed ni faris ĝin sur lasta merkredo tra iuj Claymation unue. Do tiu, revokon, estas Binky kaj ni uzis lin preni rigardi programo kiu ne vere fari ion interesan, sed faris malkaŝi kelkajn problemojn. Do komenci hodiaŭ, kial ni ne iros rapide tra kelkaj el tiuj ŝtupoj, provu distili en homaj terminoj precize kio okazas ĉi tie kaj kial tio estas malbona, kaj tiam pluiri kaj fakte komenci konstrui ion kun tiu tekniko? Do jen la unua du liniojn en tiu programo kaj en laiko La terminoj, kio estas tiuj du linioj faras? Iu kiu estas prudente komforta kun kio deklaris sur la ekrano? Kion signifas tiuj du linioj faras? Ĝi ne estas ĉiuj ke malsama semajno unu, Sed estas iu nova speciala simbolo. Yeah? Revenigu tien. 

Publiko: Deklarante punteros? DAVID Malan: Diru denove? Publiko: Deklarante punteros? DAVID Malan: Deklarante punteros kaj ni rafini ĝin iomete pli. Spektantaro: [inaudible] Adreso x kaj tiam y. DAVID Malan: Kaj poste trakti. Do konkrete kion ni faras Estas ni deklari du variabloj. Tiuj variabloj, tamen, iras esti de tipo int stelo, kiu pli specife signifas ili tuj stoki la adreso de int, respektive, x kaj y. Nun estas tie ajna valoroj? Ĉu ekzistas efektiva adresoj en tiuj du variabloj ĉe tiu punkto en tempo? No. Ĝi simple tn rubo valoroj. Se vi ne efektive asigni variablo, kiom estis en RAM antaŭe tuj plenigos kun nuloj kaj aĵoj ambaŭ de tiuj variabloj. Sed ni ankoraŭ ne scias kio estas kaj tio tuj estos ŝlosilo al kial Binky perdis la kapon pasintsemajne. 

Do tio estis la Claymation enkarniĝo de tiu whereby vi havas nur du variabloj, iom cirkla pecoj de argilo, kiu povas enteni variablojn, sed kiel la enpakita sagoj indikas, ili fakte ne indikante al ie konata por se. Tial do ni havis ĉi tiun linion, kaj tiu estis nova lasta semajno, malloc por memoro atribuo, kiu estas nur ornama metodo diri la mastruma sistemo, Linukso aŭ Mac OS aŭ Vindozo, hey, donu al mi iom da memoro, kaj ĉiuj vi devas diri al la operaciumo estas kio al la demandi lin por memoro. Oni ne tuj zorgi kion vi faros pri ĝi, sed vi devas diri al la mastruma sistemo kio pere de malloc. Yeah? 

Publiko: Kiom? DAVID Malan: Kiom? Kiom en bajtoj, do, tiu, denove, oni elpensita ekzemplo, estas ĝuste diri: donu min la grandeco de int. Nun, la grandeco de int Estas kvar bajtoj aŭ 32 bitoj. Do tio estas nur maniero de dirante, hej, mastruma sistemo, donu al mi kvar bajtoj de memoro ke mi povas uzi en mia dispono, kaj specife, kion faras malloc revenas kun respekto por ke eron de kvar bajtoj? Spektantaro: Adreso? DAVID Malan: La adreso. La adreso de tiu bloko de kvar bajtoj. Ekzakte. Kaj por ke-a kio stokitaj finfine en x kaj tial ni ne vere zorgas kion la nombro de tiu adreso estas, ĉu ĝi estas OX1 aŭ OX2 aŭ iu kripta deksesuma adreso. Ni nur zorgas bilde ke tiu variablo x estas nun indikante ke bloko de memoro. Do la sago reprezentas pointer, aŭ pli specife, memoro adreso. Sed denove, ni ne tipe zorgas kio tiuj faktaj adresoj estas. Nun, ĉi tiu linio diras kion en laiko La terminoj? Stelo x prenas 42 punktokomo. Kion tio signifas? Vi volas? Ne skrapi via kolo. 

Publiko: La adreso de x estas ĉe la 42. 

DAVID Malan: La adreso de x estas ĉe 42. Ne tute. Tiel proksima, sed ne sufiĉe, ĉar estas la stelo kiu estas prefiksi ĉi x. Do ni bezonas tweak iomete. Yeah? 

Publiko: La valoro kiun la puntero x estas indikante estas 42. DAVID Malan: Bone. La valoro kiun la montrilo x estas indikante, diru, estos 42, aŭ meti alia maniero, la stelo x diras, iru al kiom Adreso estas en x, ĉu ĝi estas 1 Oksfordo Strato aŭ 33 Oksfordostrato aŭ OX1 aŭ ox33 ajn ke nombra adreso estas: stelo x estas la dereferencing de x. Do iri al tiu adreso kaj tiam metis la numero 42 tie. Do tio estus ekvivalenta maniero diri tion. Do jen ĉio bone kaj tiam ni reprezentus la bildon kiel sekvas kie ni aldonis la 42 al tiu bloko de kvar bajtoj sur la dekstra flanko, sed tiu linio estis kie aferoj iris malbone kaj Binky kapo krevita ĉe tiu punkto, ĉar malbonaj aferoj okazos kiam vi dereference rubo valoroj aŭ vi dereference nevalida montriloj, kaj mi diras nevalida ĉar ĉe tiu punkto en la rakonto, kio estas ene de y? Kio estas la valoro de y bazita sur la lastaj paŝoj? Yeah? Kio estas tio? 

Publiko: An adreso. DAVID Malan: An adreso. Ĝi devus esti parolado sed mi pravalorizitaj ĝi? Do mi ankoraŭ ne havas. Do kio estas konata esti tie? Estas nur iuj rubo valoro. Ĝi povus esti ajna Adreso de nulo al 2 miliardoj, se vi havas du koncertoj de RAM, aŭ nulo al 4 miliardoj se vi havas ricevis kvar gigabajtoj de RAM. Estas iuj rubo valoro, sed la problemo estas ke la mastruma sistemo, se ĝi ne donis al vi ke bloko de memoro specife ke vi provas iri, ĝi estas ĝenerale iranta kaŭzi kio ni vidis kiel segmentación kulpo. Do fakte, iu el vi kiu havas baraktis ĉe problemojn ĉe oficejo horoj aŭ en problemoj kiuj estas pli ĝenerale per provi elkompreni segmentación kulpo, kiu ĝenerale signifas vi tuŝi segmenton de memoro kiun vi ne devus esti. Vi tuŝi memoro kiu la mastruma sistemo havas ne permesis vin tuŝi, ĉu ĝi estas irante tro longen en via tabelo aŭ komencante nun, ĉu ĝi estas ĉar vi tuŝi memoron kiu ĝuste estas iu rubo valoro. 

Tion farante stelo x tie estas ia nedifinita konduto. Vi neniam devus fari ĝin pro malakordo estas, la programo estas ĵus tuj frakasos, ĉar vi diras, iri al tiu adreso kaj vi ne scias kien tiu adreso fakte estas. Do la mastruma sistemo estas verŝajna tuj frakasos vian programon kiel rezulto kaj efektive, jen kio okazis tie al Binky. Do finfine, Binky fiksita tiun problemon kun tiu. Por ke programo mem estis mankhava. Sed se vi ia forĝi antaŭen kaj ekzekuti ĉi tiun linion anstataŭe, y egalas x nur signifas ajn Adreso estas x, ankaŭ metis ĝin en y. 

Kaj tiel bilde, ni reprezentis tiun kun du sagoj de x kaj de y montradon al la sama loko. Do semantike, x egalas al y ĉar ambaŭ de tiuj amasigas la sama adreso, ergo montrante 42, kaj nun, kiam vi diras stelo y, iru al la adreso en y, tiu havas interesan kromefikon. Do la adreso en y estas la samon kiel la adreson en x. Do se vi diras iri al la adreso en y kaj ŝanĝi la valoron 13, Kiu alia estas tuŝita? X estas, punkto D, tiel diri, devus esti tuŝita ankaŭ. 

Kaj efektive, kiom Nick tiris tiun bildo en Claymation estis ĝuste tio. Kvankam ni sekvas la montrilon y, ni finis en la sama loko, kaj do se ni devis presi eksteren x aŭ y-oj pointee, tiam ni vidus la valoro de 13. Nun, mi diras pointee esti konsekvenca kun la vídeo. Programistoj, al mia scio, neniam reale diri la vorton pointee, kio estas pinta je, sed por konsistenco kun la vídeo, realigi jen ĉio tio estis signifis en tiu situacio. Do demandojn sur Claymation aŭ punteros aŭ malloc nur ankoraŭ? Neniu? Bone. 

Do sen plua ado, ni rigardu al kie tiu havas reale estis uzita por iom da tempo. Do ni havis ĉi CS50 biblioteko ke estas atingis ĉiujn tiujn funkciojn. Ni uzis GetInt multe, GetString, verŝajne GetLongLong frue en mia pset aŭ tiel, sed kio efektive estis okazanta? Nu, ni prenu rapidan rigardon sub la kapuĉo je programo kiu inspiras kial ni doni vin la CS50 biblioteko, kaj ja kiel de lasta semajno, ni komencis prenante tiujn trejnado radoj ekstere. Do tiu estas nun ordo de postmortem de kio estis daŭriganta ene la CS50 biblioteko, eĉ se ni nun komencos movanta for de ĝi por plej programoj. 

Do tiu estas programo nomita scanf 0. Estas super mallonga. Ĝi nur havas tiujn liniojn, sed ĝi Enkondukas funkcio nomita scanf ke ni vere tuj vidos en momento ene de la CS50 biblioteko, kvankam en iomete malsama formo. Do tiu programo sur linio 16 estas deklari variablon x. Do donu al mi kvar bitokoj por int. Ĝi estis rakontanta uzanto, numeron bonvolu, kaj tiam tiu estas interesa linio kiu fakte ligas kune pasintsemajne kaj ĉi. Scanf, kaj tiam rimarkos prenas formato kordoj, ĝuste kiel printf, % i signifas int, kaj tiam ĝi prenas dua argumento kiu aspektas iom funky. Ĝi estas simbolo x, kaj memorigi, ni nur vidis unufoje pasintsemajne. Kion ampersand x reprezentas? Kion ampersand fari en C? Yeah? 

Publiko: La adreso de. DAVID Malan: La adreso de. Do estas la malo de la stelo operatoro, dum la stelo operatoro diras, iru al tiu adreso, la ampersand operatoro diras, diveni la Adreso de ĉi variablo, kaj tiel tio estas ŝlosilo, ĉar scanf la celo en la vivo estas skani la uzanto enigo per klavaro, depende kion ajn li aŭ ŝi tipoj, kaj tiam legis ke uzanto enigo en variablon, sed ni vidis en la pasintaj du semajnoj ke tiu interŝanĝa funkcio kiu ni provis senpene implementar estis ĵus rompita. Memoru ke kun la interŝanĝa funkcio, se ni nur deklaris A kaj B kiel ints, ni sukcese interŝanĝi la du variabloj ene de swap Ĝuste kiel kun la lakto kaj OJ, sed tuj kiam interŝanĝa rehejmigxis kio estis la rezulto kun respekto al x kaj y, la originalaj valoroj? Nenio. Yeah. Nenio okazis tiam, ĉar svopoj ŝanĝi nur lia loka kopiojn, kiu estas, ĉiuj tiu tempo, kiam ni havas estis pasanta en argumentoj al funkcioj, ni estas nur pasanta kopioj de tiuj argumentoj. Vi povas fari kun tio kion vi volas kun ili, sed ili tuj devas ne Efekto en la originala valoroj. Do tio estas problema se vi volas havi funkcion kiel scanf en vivo, kies celo estas skani la uzanto enigo per klavaro kaj tiam plenigi la truojn, por tiel paroli, tio estas, doni variablon kiel x valoro, ĉar se mi estus nur pasas x al scanf, se vi konsideras la logiko de lasta semajno, scanf povas fari kion ajn ŝi volas kun kopio de x, sed ne povis konstante ŝanĝas x se ni donas scanf trezoron mapo, tiel diri, kie x signas la lokon, per ni pasas en la adreso de x tia ke scanf povas iri tien kaj reale ŝanĝo la valoro de x. Kaj tiel ja, ĉiuj ke tiu programo faras se mi scanf 0, en mia fonto 5m dosierujo, fari scanf 0, dot oblikvo scanf, nombro bonvolu 50, dankon pro la 50. 

Do estas ne cxiuj interesaj, sed kio ja okazas estas ke tuj kiam mi vokas scanf tie, la valoro de x estas konstante ŝanĝis. Nun, ĉi tio ŝajnas bela kaj bona, kaj fakte, ĝi Evidente, ni ne vere bezonas la CS50 biblioteko ĉe ĉiuj anymore. Ekzemple, ni kuros tiun fojon pli ĉi tie. Lasu min remalfermi ĝin por dua. Ni provu kelkajn bonvolu kaj anstataŭ diri 50 kiel antaŭe, ni nur diras ne. Okej, tio estas iom stranga. BONE. Kaj nur iuj sensencaĵo tie. Do ĝi ne ŝajnas manipuli eraraj situacioj. Do ni bezonas minimume komenco aldonante iuj eraro-kontrolanta certigi ke la uzanto havas tajpita en fakta nombro kiel 50, ĉar ŝajne tajpi vortojn ne estas detektita kiel problema, sed probable devus esti. 

Ni rigardu ĉi versio nun jen mia provo reverki GetString. Se scanf havas ĉiujn ĉi funkciojn konstruita, kial ni estis plaŭdado kun tiuj trejnado radoj kiel GetString? Nu, jen eble mia propra simpla versio de GetString per unu semajno, mi povus diri, donu al mi ĉenon kaj nomas ĝin buffer. Hodiaŭ, mi tuj komencos simple dirante char stelo, kiu, memoru, estas nur sinonimo. Ĝi aspektas pli timinda sed estas la ĝusta sama afero. Do donu al mi variablo nomis buffer ke tuj stoki ĉenon, diri la uzanto kordo bonvolu, kaj tiam, ekzakte kiel antaŭe, ni provu pruntepreni tiun lecionon scanf % s tiu tempo kaj poste pasos en bufro. Nun, rapida prudento kontroli. Kial mi ne diras ampersand buffer tiu tempo? Konkludi el la antaŭa ekzemplo. Publiko: Char stelo estas puntero. DAVID Malan: Ĝuste, ĉar tiu tempo, char stelo estas jam pointer, adreson, per difino de tiu stelo estanta tie. Kaj se scanf atendas adreson, sufiĉas nur Iam en bufro. Mi ne bezonas diri ampersand bufro. Por la scivolaj, vi povis fari ion kiel tiu. Ĝi havus malsaman signifon. Tiu donus al vi montrilo al puntero, kiu estas fakte validan afero en C, sed por nun, ni teni ĝin simpla kaj konservi la historion konsekvenca. Mi simple tuj pasos en buffer kaj tio estas korekta. La problemo tamen estas tiu. Lasu min kaj kuras ĉi programo post kompili ĝin. Faru scanf 1. Damn, mia tradukilo kaptante mia eraro. Deme dua. Tin. Diru scanf-1.c. BONE. Tie ni marŝos. Mi bezonas ĝin. CS50 ID havas diversajn agordadaj difinoj ke protekti vin kontraŭ vi mem. Mi bezonis malfunkciigi tiujn per kurante Clang permane tiu tempo. Do string bonvolu. Mi tuj iros antaŭen kaj tajpu en mia ŝatata saluton mondo. OK, nula. Tio ne estas kion mi tajpis. Do estas indika de io esti erara. Lasu min kaj tajpu en vere longa ŝnuro. Dankon pro la nula kaj mi ne scias se mi tuj povus frakasi ĝin. Ni provu iom kopion algluu kaj vidi se tiu helpas. Nur alglui multajn ĉi. Estas definitive granda ŝnuro ol kutime. Ni nur vere skribi ĝin. No. Damnu ĝin. Ordonu ne trovis. Do jen senrilataj. Tio estas ĉar mi pasted iuj malbonaj karakteroj, sed ĉi rezultas ne tuj funkcios. 

Ni provu ĉi denove, ĉar ĝi estas pli amuza se ni efektive kraŝi ĝin. Ni tajpi tion kaj nun mi estas tuj kopii vere longa kordo kaj nun ni vidu se ni povas frakasi tiun aferon. Rimarku ke mi preterlasis spacoj kaj novaj linioj kaj punktokomojn kaj ĉiuj funky karakteroj. Enter. Kaj nun la reto estas nur esti malrapida. Mi tenis malsupren Komando-V tro longaj, klare. Damnu ĝin! Ordonu ne trovis. 

BONE. Nu, la punkto estas tamen la sekvan. Do kio estas efektive iranta sur kun ĉi deklaro char stelo bufro sur linio 16? Do kion mi ricevas kiam mi deklaras puntero? Ĉiuj mi ricevas estas kvar bajto valoro nomata buffer, sed kio estas ene de ĝi ĉe la momento? Estas nur iuj rubo valoro. Ĉar ajna momento vi deklaras variablon en C, estas nur iuj rubo valoron, kaj ni komencas vojaĝo super ĉi tiu realaĵo. Nun, kiam mi diras scanf, iri al tiu adreso kaj meti ajn la uzanto tajpas en. Se la uzanto tajpas en saluton mondo, nu, kie mi metis ĝin? Buffer estas rubo valoro. 

Do jen speco de kiel sago ke estas indikante kiu scias kie. Eble ĝi estas indikante ĝuste ĉi tie en mia memoro. Kaj do kiam la uzanto tipoj en saluton mondo, la programo provas meti la kordo saluton mondo backslash 0 en tiu bloko de memoro. Sed kun alta probablo, sed klare ne 100% probableco, la komputilo tuj poste kraŝi la programo pro tio ne memoro mi devus esti permesita tuŝi. Do mallonge, tiu programo estas mankhava ĉar ĝuste tio. Mi principe ne faras kion? Kio paŝoj mi preterlasis, samkiel ni preterlasis kun Binky unua ekzemplo? Yeah? 

Publiko: Memoro atribuo? 

DAVID Malan: Memoro atribuo. Mi ne efektive asignitaj ajna memoro por ke kordoj. Do ni povas fiksi tion en kelkaj manieroj. Unu, ni povas teni ĝin simpla kaj fakte, nun vi estas tuj komencos vidi malklarigante de la linioj inter kio tabelo estas, kion kordo estas, kia char stelo estas, kion tabelo de signoj estas. Jen dua ekzemplo implikantaj kordoj kaj avizo ĉiuj mi faris sur linio 16 estas, anstataŭ diri ke buffer tuj estos char stelo, puntero al bloko de memoro, Mi tuj tre proactively donu min buffer por 16 karakteroj, kaj fakte, se vi konas kun la termino buffering, probable de la mondo de vídeos, kie video estas buffering, buffering, buffering. Nu, kio estas la rilato tie? Nu, Inside de YouTube kaj ene de video ludantoj ĝenerale estas tabelo Tiu estas pli granda ol 16. Povus esti tabelo de grandeco unu megabajto, eble 10 megabajtoj, kaj en tiu tabelo faras via retumilo elŝuti tutan faskon de bajtoj, tuta aro da megabajtoj de video kaj la video ludanto, YouTube aŭ kiu ajn estas, komenciĝas legante la bajtoj de tiu tabelo, kaj iam vi vidos la vorto buffering, buffering, kiu signifas la ludanto havas alvenis al la fino de tiu tabelo. La reto estas tiel malrapida ke ĝi havas ne replenigis la tabelo kun pli bajtoj kaj tial vi estas el bitoj por montri al la uzanto. 

Do bufro estas kapabla termino tie en tiu ĝi estas nur tabelo, eron de memoro. Kaj ĉi riparos ĝin ĉar ĝi rezultas ke vi povas trakti arrays kvazaŭ ili estas adresojn, kvankam bufro estas nur simbolo, ĝi estas sekvenco de karakteroj, bufro, ke estas utila por mi, la programisto, vi povas pasi lian nomon ĉirkaŭ kvazaŭ ĝi estus montrilo, kvazaŭ ĝi estis la adreso de eron de memoro por 16 signoj. Do jen diri, mi povas pasi la scanf ĝuste tiu vorto kaj tial nun, se mi faras tiun programon, fari scanf 2, dot oblikvo scanf 2, kaj tajpi en saluton mondo, Entajpu, ke time-- 

Hmm, kio okazis? String bonvolu. Kion mi faras malbone? Saluton mondo, buffer. Saluton mondo. Jes mi scias kio ĝi estas faranta. BONE. Do ĝi estas leganta supren ĝis la unua spaco. Do ni cheat por nur momento kaj diras mi nur volis tajpi ion vere longa kiel tiu estas longa frazo jen unu, du, tri, kvar, kvin, ses, sep, ok, naux, 10, 11, 12, 13, 14, 15, 16. BONE. Ĝi estas ja longa frazo. Do tiu frazo estas longa ol 16 karakteroj kaj do kiam mi batis Enter, kio okazos? Nu, en tiu kazo de la rakonto, mi deklaris bufro por fakte esti tabelo kun 16 signoj preta iri. Do unu, du, tri, kvar, kvin, ses, sep, ok, naŭ, 10, 11, 12, 13, 14, 15, 16. Do 16 karakterojn, kaj nun, kiam mi legi en iu kiel tiu estas longa frazo, kio okazos estas ke mi legos en tiu estas longa S-Kaj-N-T-Kaj-N-C-Kaj, frazo. 

Do tiu estas intence malbona afero teni skribanta trans limoj de mia tabelo, preter la limoj de mia bufro. Mi povis akiri bonŝanca kaj la programo tenos sur kurado kaj ne zorgas, sed ĝenerale parolante, tiu ja frakasi mian programon, kaj tio estas cimo en mia kodigi la momento mi paŝi preter la limoj de tiu tabelo, ĉar mi ne scias se ĝi estas nepre tuj frakasos aŭ se mi nur ricevos bonŝanca. Do tio estas problema ĉar en tiu kazo, ĝi ŝajnas funkcii kaj ni incitos sorton tie, kvankam la IDE ŝajnas toleri tre iom of-- 

Tie ni marŝos. Fine. Do mi estas la sola kiu povas vidi tion. Do mi simple havis multan amuzan tajpadon el vere longa fakta frazo ke ĝi certe superis 16 bajtoj, ĉar mi tajpita en tiu freneza longa plurliniaj frazo, kaj tiam rimarkas kio okazis. La programo provis videbligi ĝin kaj tiam ricevis segmentación kulpo kaj segmentación kulpoj estas kiam io kiel tio okazas kaj la mastruma sistemo diras Ne, ne povas tuŝi ke memoro. Ni tuj mortigi la programo entute. 

Do tio ŝajnas problema. Mi plibonigis la programon per kiu almenaŭ havi iu memoro, sed tiu ŝajnus ĉirkaŭlimigi la funkcio GetString al akiranta kordoj de iu finia longo 16. Do se vi volas subteni plu frazoj ol 16 karakteroj, kion vi faras? Nu, vi povas pligrandigi la grandeco de ĉi buffer 32 aŭ kiu ŝajnas ia mallonga. Kial ni ne simple ĝi 1.000 sed puŝas reen. Kio estas la respondo intuicie de nur evitante tiun problemon farante mian bufron granda, kiel 1.000 signoj? Per efektivigado GetString tiamaniere. Kio estas bona aŭ malbona ĉi tie? Yeah? Publiko: Se vi prenos multajn de spaco kaj vi ne uzas ĝin, tiam vi ne povas reallocate tiu spaco. DAVID Malan: Absolute. Ĝi estas malŝparema mezuro se vi faras ne vere bezonas 900 el tiuj bajtoj kaj tamen vi petante 1,000 en totala ĉiuokaze, vi nur konsumas pli memoro sur la uzanto komputilo ol vi bezonas, kaj finfine, iuj el vi jam renkontis en vivo ke kiam vi estas kurante multaj programoj kaj ili manĝas supren multa memoro, tiu povas fakte efikos agado kaj la uzanto sperto sur la komputilo. Do jen speco de mallaborema solvo, por certa, kaj inverse, ĝi estas ne nur malŝparo, kion problemo ankoraŭ restas, eĉ se mi faras mian bufron 1.000? Yeah? 

Publiko: La kordoj estas longo 1,001. DAVID Malan: Ĝuste. Se via ĉeno estas longo 1,001, vi havas la ĝustan saman problemon, kaj per mia argumento, mi volus ĝuste tiam fari ĝin 2000 sed vi ne scias en antaŭi kiom granda ĝi devus esti, kaj tamen, mi ja devas kompili mia programo antaŭ lasanta homoj uzas kaj malŝarĝo ĝin. Do tiu estas ĝuste la speco de aĵoj kiuj la CS50 biblioteko tries helpi nin per kaj ni nur rigardo en iu el la subaj efektivigo tie, sed tiu estas CS50 skalara C. Ĉi estas la dosiero kiu estas estita sur CS50 IDE ĉiuj tiuj semajnoj ke vi estis uzante. Ĝi estas pre-kompilita kaj vi havas estis uzante ĝin aŭtomate nature havi la interfrapigos L CS50 flago kun Clang, sed se mi rulumu malsupren tra ĉiuj tiuj funkcioj, jen GetString, kaj nur por doni al vi guston de kio okazas, ni prenu rapidan rigardon al la relativa komplekseco. Ĝi ne estas súper longa funkcion, sed ni ne devas pensi pri ĉiuj malfacile kiel iri pri akiri kordoj. 

Do jen mia bufro kaj mi ŝajne pravalorizi ĝin al nula. Tio, kompreneble, estas la samon kiel char steloj, sed mi decidis en implementando la CS50 biblioteko ke se ni tuj tute dinamika, Mi ne scias anticipe kiom granda de string uzantoj tuj volas ricevi. Do mi tuj komencu kun nur malplenan ĉenon kaj mi tuj konstru tiel memoro kiel mi bezonas persvadi la uzanto kordo kaj se mi ne havas sufiĉas, mi tuj demandas la mastruma sistemo por pli memoro. Mi tuj movi siajn kordo en pli grandan eron de memoro kaj mi tuj liberigi aŭ liberigi la nesufiĉe granda bloko de memoro kaj ni ĵus tuj fari tiun ripete. 

Tiel rapida rigardo, tie estas nur variablo kun kiu mi tuj sekvigi de la kapablo de mia bufro. Kiom da bajtoj povas min persvadi? Jen variablon n kun kiun mi tuj konservi trako de kiom da bajtoj estas reale en la bufron aŭ ke la uzanto tajpas. Se vi ne vidis tion antaŭe, vi povas specifi ke variablo kiel int estas sensigna, kiu kiel la nomo indikas, signifas ke estas ne-negativa, kaj kial Mi iam volas ĝeni preciziganta ke int ne nur int, sed estas sensigna int? Ĝi estas nenegativa int. Kion faras la [inaudible] signifas? 

Spektantaro: Ĝi estas priskribanta kvanto de memoro kiu povas esti [inaudible]. 

DAVID Malan: Yeah. Do se mi diras sensigna, tio estas fakte donante al vi unu pecon da ekstra memoro kaj ĝi similas specon de stulta, sed se vi havas unu pecon da aldona memoro, ke signifas vin havas duoble tiom da valoroj povas reprezenti, ĉar ĝi povas esti 0 aŭ 1. Do defaŭlte, int povas esti malglate negativa 2 miliardo tuta vojo ĝis pozitiva 2 miliardoj. Tiuj estas grandaj teritorioj, sed ĝi estas ankoraŭ ia malŝparema se vi nur zorgas pri grandecoj, kiuj nur intuicie devus esti nenegativa aŭ pozitiva aŭ 0, bone tiam, kial vi malŝparas 2 miliardoj eblaj valoroj por negativaj nombroj se vi neniam uzos ilin? Do dirante sensigna, nun mia int povas esti inter 0 kaj malglate 4 miliardoj. 

Do jen nur int C por kialoj ni ne enir ĵus nun kiel al kial ĝi estas int anstataŭe de char, sed ĉi tie estas la esencon de kio okazas on, kaj kelkaj el vi eble uzante, ekzemple, la fgetc funkcio eĉ en pset kvar aŭ poste, ni vidos ŝin denove en problemo starigis kvin, fgetc estas bela ĉar kiel la nomo ia, ia arcanely sugestas, ĝi estas funkcio kiu ricevas karaktero kaj tiel, kio estas fundamente malsama pri kion ni faras en GetString estas ni ne uzante scanf sammaniere. Ni nur rampante kune paŝo post paŝo super kio ajn la uzanto tajpas en, ĉar ni povas ĉiam rezervi unu char, kaj tiel ni povas ĉiam sekure rigardi unu char samtempe, kaj la magio komencas okazi tie. Mi tuj rulumu malsupren al Meze de ĉi tiu funkcio nur enkonduki mallonge tiu funkcio. Tre kiel ekzistas malloc funkcio, ekzistas a realloc funkcio kie realloc permesas reallocate eron de memoro kaj fari ĝin pli granda aŭ pli malgranda. Do longan rakonton kaj kun ondo de mia mano por hodiaŭ, scias ke kion GetString faras estas ĝi estas speco de magie kreskanta aŭ ŝrumpanta la bufro kiel la uzanto entajpas sian ĉenon. 

Do se la uzanto tajpas en mallonga kordo, ĉi kodo nur allocates sufiĉe memoro konveni la kordo. Se la uzanto tenas tajpadon kiel mi faris ĝin denove kaj denove kaj denove, bone, se la buffer la komence ĉi tiu granda kaj la programo rimarkas, al atendu momenton, mi estos for de spaco, ĝi tuj duobligi la grandeco de la bufro kaj tiam duobligi la grandecon de la bufro kaj la kodo kiu faras la duobligo, se ni rigardas ĝin tie, ĝi estas nur tiun lertan unu-Liner. Vi eble ne jam vidis ĉi sintakso antaŭe, sed se vi diras stelo egalas, ĉi tiu estas la sama aĵo kiel dirante kapablo fojojn 2. Do ĝi nur tenas duobliganta la kapablo de la bufro kaj tiam rakontanta realloc doni mem ke multe pli da memoro. 

Nun, kiel flanken, tie Estas aliaj funkcioj tien ke ni ne aspektos en ajnan detalon krom montri en GetInt, ni uzas GetString en GetInt. Ni kontrolu ke ĝi ne estas nula, kiu, memoru, estas la speciala valoro kiu signifas ion misokazis. Ni estas el memoro. Pli bona kontroli por tio. Kaj ni resendas sentinelo valoro. Sed mi cedu al la komentoj kiel al kial kaj tiam ni uzas tiun kuzo de scanf nomata sscanf kaj rezultas ke sscanf, aŭ ŝnuro scanf, permesas preni rigardi la linion kiu la uzanto tajpas en kaj lasos vin analizi ĝi esence kaj kion mi faras ĉi tie estas fakton mi sscanf, analizi ajn la uzanto havas tajpitaj kaj certiĝu% i, estas entjero en ĝi, kaj ni ne enir hodiaŭ ĝuste kial ekzistas ankaŭ a% c tie, sed ke en malmultaj vortoj permesas nin al detekti se la uzanto tajpita en io blufa post la nombro. Do la kialo ke GetInt kaj GetString diras reprovi, reprovi, reprovi estas pro ĉiuj ke kodo ni skribis, Estas ia rigardante la uzanto enigo en faranta certe ĝi estas tute numera aŭ ĝi estas fakta Floating punkto valoro aŭ simile, depende kion valoro funkcii vi uzas. 

Whew. BONE. Tio estis buŝplenon sed la punkto ĉi tie estas ke la kialo ni devis tiujn trejnado radoj sur estas ĉar ĉe la plej malalta nivelo, tie estas nur tiom da aferoj kiuj povas iri malbone, ke ni volis al preemptively manipuli tion certe en la fruaj semajnoj de la klaso, sed nun kun pset kvar kaj pset kvin preter vi vidos ke ĝi estas pli al vi sed ankaŭ vi estas pli kapabla solvi tiujn specojn de problemoj mem. Demandojn sur GetString aŭ GetInt? Yeah? 

Publiko: Kial vi duobligi la kapablo de la bufro anstataŭ nur kreskanta ĝin per la ĝusta kvanto? 

DAVID Malan: Bona demando. Kial ni duobligi la kapaciton de la bufro kontraste nur pliigante ĝin de iu konstanta valoro? Ĝi estis dezajno decido. Ni ĵus decidis ke ĉar ĝi emas esti iom multekosta tempo-saĝa demandi la operaciumo por memoro, ni ne volas finas por eniri situacio por grandaj kordoj ke ni petis la VIN multfoje kaj denove kaj denove en rapida sinsekvo por memoro. Do ni simple decidis, iom arbitre sed ni esperas prudente, ke, vi scias kio, ni provu akiri antaŭen de ni mem kaj ĝuste teni duobliganta ĝin por ke ni minimumigi la kvanton de tempoj ni devas nomi malloc aŭ realloc, sed tuta juĝo alvoku la foresto de scianta kio uzantoj eble volas enmeti. Ambaŭ manieroj povus esti diskutindaj. Disputeble bona. 

Do ni rigardu paro de aliaj kromefikoj de memoro, aĵoj kiuj povas iri malbone kaj iloj kiu vi povas uzi kapti tiajn erarojn. Rezultas vi ĉiuj, eĉ kvankam check50 ne sciigis vin kiom, estis skribanta kalesxon kodo ekde semajno unu, eĉ se ĉiuj check50 testoj estas pasis, kaj eĉ se vi kaj via TF estas super certa ke via kodo laboras kiel intencita. Via kodo estis kalesxo aŭ mankhava en tio vi ĉiuj, en uzi la CS50 biblioteko, ili iris filtrante memoro. Vi estis petante la mastruma sistemo por memoro en la plej multaj el la programoj vi skribis, sed vi havas neniam fakte donis ĝin reen. Vi nomas GetString kaj GetInt kaj GetFloat, sed kun GetString, vi havas neniam nomis unGetString aŭ Give String Reen aŭ simile, sed ni vidis ke GetString faras rezervi memoron tra malloc aŭ tiun funkcio realloc, kiu estas nur tre simila en spirito, kaj tamen, ni estis petante la mastruma sistemo por memoro kaj memoro multfoje sed neniam donante ĝin. 

Nun, kiel flanken, ĝi rezultas ke kiam programo malekas, ĉiuj la memoro aŭtomate liberigitaj. Do ĝi ne estis grandega interkonsento. Tio ne tuj rompos la IDE aŭ malrapida aferojn malsupren, sed kiam programoj fari ĝenerale liki memoro kaj ili estas kuranta dum longa tempo. Se vi iam vidis la stultan iom strando pilko en Mac VIN aŭ la sablohorloĝo en Vindozo kie estas afable desaceleración aŭ pensi aŭ pensado aŭ nur vere komenciĝas malrapidigi al crawl, ĝi tre eble povus esti la rezulto de memoro liko. La programadores kiu skribis la softvaro vi estas uzanta demandu la mastruma sistemo por memoro ĉiu malmultaj minutoj, ĉiuhore. Sed se vi uzas la programaron, eĉ se ĝi estas minimumigita en via komputilo dum horoj aŭ tagoj sur fino, vi povus esti petante pli kaj pli memoro kaj neniam fakte uzante ĝin kaj tiel via kodo povus esti, aŭ programoj povus esti likanta memoro, kaj se vi komencos filtri memoro, Tie estas malpli da memoro por aliaj programoj, kaj la efiko estas malrapidigi ĉiu malsupren. 

Nun, ĉi tiu estas nedisputeble unu el la plej abomenaj programoj vi havos ŝancojn kuri en CS50 mezuro kiel ĝia eligo estas eĉ pli esotera ol tin La aŭ fari la aŭ ajna de la komando linio programoj ni kuras antaŭ sed dankeme, enigita en lian eligo Estas iuj super helpema konsiletoj kiu estos utila aŭ por pset kvar aŭ certe pset kvin. Do valgrind estas ilo kiu povas esti uzita rigardi por memoro fugoj en via programo. Ĝi estas relative simpla kuri. Vi kuras valgrind kaj tiam, eĉ kvankam ĝi estas iom parolema, haltostreko haltostreko liko ĉeko egalas plena, kaj tiam dot oblikvo kaj la nomo de via programo. Do valgrind tiam kuri via programo kaj ĉe la fino de via programo kurante antaŭ ĝi malekas kaj donas alian prompto, ĝi tuj analizos vian programo dum ĝi estas estinta kurante Diri al vi vi likas ajna memoro kaj pli bona ankoraŭ, vi tuŝos memoro kiu ne apartenis al vi? Ĝi ne povas kapti ĉion, sed ĝi estas sufiĉe bona ĉe kaptante plej aferoj. 

Do jen ekzemplo de mia kuris tiu programo, kuris valgrind, sur programo nomata memoro, kaj mi tuj reliefigi la liniojn kiuj estas finfine de intereso al ni. Do ekzistas eĉ pli distroj ke mi forigis el la diapozitivo. Sed ni vidos, kian tiu programo kapablas diranta nin. Ĝi estas kapabla je diranta nin aferoj kiel nevalidan registran de grandeco 4. Alivorte, se vi tuŝas la memoro, specife 4 bajtoj de memoro ke vi ne devus havi, valgrind povas diri al vi ke. Nevalida registran de grandeco 4. Vi tuŝis kvar bajtoj ke vi ne devus havi. Kie vi faris tion? Jen la beleco. Memoro punkto c linio 21 estas kie vi ŝraŭbita supren kaj tial ĝi estas helpema. Tre kiel GDB, ĝi povas helpi atentigi vin je la fakta eraro. 

Nun, ĉi tiu estas iom pli parolema, se ne konfuza. 40 bitokoj en 1 blokoj estas definitive perdita en perdo rekordo 1 de 1. Kion tio signifas? Nu, ĝi nur signifas ke vi petis 40 bajtoj kaj vi neniam donis ĝin reen. Vi nomas malloc aŭ vi vokis GetString kaj la mastruma sistemo donis vin 40 bajtoj, sed vi neniam liberigita aŭ liberigita ke memoro, kaj esti justa, ni neniam montras vi kiom redoni memoro. Rezultas ke estas súper simpla funkcio nomita libera. Prenas unu argumenton, la afero Vi volas liberigi aŭ redoni, sed 40 bitokoj, ŝajne, en tiu programo perdiĝis ĉe linio 20 de memoro dot c. 

Do ni vidas ĉi programo. Estas súper senutila. Ĝi nur pruvas tiu aparta eraro. Do ni rigardu. Jen ĉefa kaj ĉefa, avizo, alvokoj funkcio nomita f kaj tiam revenas. Do ne cxiuj interesaj. Kion f faru? Rimarku ke mi ne tedis kun prototipo. Mi volis teni la kodo kiel minimumaj kiel ebla. Do mi metis f super ĉefa kaj tio estas bone, certe, por mallongaj programoj kiel ĉi. Do f ne reveni nenion kaj faras ne preni ion, sed ĝi faras tion. Ĝi deklaras, tre kiel en la Binky ekzemple, puntero nomata x ke tuj stoki la adreson de int. Do jen la maldekstra flanko. En la angla, kio estas la dekstra flanko faras? Iu ajn? Kio estas ĉi faras por ni? Yeah? 

Spektantaro: [inaudible] fojojn la grandeco de int kio estas 10 fojoj ke [inaudible] DAVID Malan: Bona kaj mi resumos. Do asigni sufiĉan spacon por 10 entjeroj aŭ 10, kio estas la grandeco de int, ĝi estas kvar bajtoj, do 10 foje 4 estas 40, tiel ke dekstra flanko kiu mi havas emfazata estas doni al mi 40 bajtoj kaj stoki la adreson de la unua bitoko en x. Kaj nun laste, kaj jen kien tiu programo estas kalesxo, kio estas misas linio 21 bazita sur tiu logiko? Kio okazas kun linio 21? Yeah? Spektantaro: Vi ne povas indekson en x [inaudible]. DAVID Malan: Yeah. Mi devus ne indekson en x tiel. Do sintakse, tio estas bone. Kio estas bela estas, multe kiel vi povas trakti la nomon de tabelo kvazaŭ ĝi estas puntero, simile povas trakti montrilo kvazaŭ ĝi estas tabelo, kaj tial mi povas sintakse diru x krampo ion, x krampo i, sed la 10 estas problema. Kial? 

Publiko: Ĉar ĝi ne estas ene. 

DAVID Malan: Ne ene ol bloko de memoro. Kio estas la plej granda valoro mi metante en tiuj rektaj krampoj? 9, 0 tra 9. Pro nulo indeksado. Do 0 tra 9 estus bone. Krampo 10 Ne bone kaj sed, memoru tamen, ĉiufoje Mi ŝajnas provi fari CS50 IDE kraŝo tajpante en blufa valoroj, ĝi ne ĉiam kunlaboras, kaj ja, vi ofte Get Lucky nur ĉar la mastruma sistemo ne rimarkos ke vi iam tiel iomete pasi iun eron de memoro, ĉar vi restus ene teknike via segmento, sed pli sur tiu en operaciumoj klaso, kaj do ion tiel povus tre facile iri desapercibido. Via programo estas neniam tuj frakasos konsekvence sed eble unufoje en kelktempe. 

Kaj tiel ni provu valgrind sur tiu, kaj jen kie ni akiros superŝutita per la eligo momente. Do fari memoron valgrind liko ĉeko egalas plena dot oblikvo memoro. Kaj jen kial mi promesas ĉi surverŝos. Jen kion valgrind, jen kion programisto, iuj jaroj ago- decidis ke estus bona ideo por la eligo aspekti. Do ni sencon de tiu. Do tute maldekstre-mana flanko por neniu bona kialo estas la procezo ID de la programon ni nur kuri, la solan ensalutilo por la programo ni nur kuris. Ni forigita ke de la glito, sed ekzistas estas kelkaj utilaj informoj en ĉi tie. 

Ni rulumu supren al la pinto. Jen kie ni komencis. Do estas ne ĉiuj kiuj multe eligo. Jen ke nevalida registran de grandeco 4 sur linio 21. Nu, kio estis linio 21? Linio 21 estis ĝuste tiu kaj ĝi havas sencon ke mi estas en valide skribi 4 bajtoj ĉar mi estas provante meti ĉi entjero, kiu povus esti io, ĝi nur hazarde estas nulo, sed mi provas meti ĝin je situo kiu ne apartenas al mi. Cetere, cxi tie, 40 bajtoj en unu blokoj estas definitive perdis en rekordo 1. Tio estas ĉar kiam mi vokas malloc tie, mi neniam fakte liberigi la memoron. 

Do kiel ni povas ripari tion? Lasu min kaj esti iom pli sekuraj kaj fari 9an tie kaj lasu min tie liberaj x. Tiu estas la nova funkcio por hodiaŭ. Se mi nun rerun fari memoron dot oblikvo, ni kuras valgrind sur ĝi denove maksimumigi mia fenestro kaj batis Enter. Nun, ĝi estas bona. Enterigos la bona novaĵo en ĉiuj ĉi eligo. Ĉiuj tenujon blokoj estis liberaj. Ni revenos al kio la havaĵon estas, sed neniu filtraciones estas eblaj. Do tiu estas nur alia ilo por via ilo kit kun kiu vi povas komenci trovu eraroj tiel. 

Sed ni vidu kion pli povas iri malbone tie. Ni transiro nun al reale solvi problemon. Kiel flanken, se tiu estos malpezigi Iomete de konfuzo aŭ streĉiĝo, tiu estas nun amuza. Yeah. Tio estas sufiĉe bona. Ĉar punteros estas adresoj kaj adresoj ĝenerale per konvencio skribita kun deksesuma. Ha, ha, tio estas amuza nun. Cxiukaze, do ni nun reale solvi problemon. Tia estis súper, super malalta nivelo tiel malproksime, kaj ni povas reale fari utilajn aĵoj kun ĉi tiuj malalta nivelo detaloj. 

Do ni enkondukis kelkajn semajnojn antaŭ la nocio de tabelo. Tabelo estis bela ĉar estas malfacile purigi nian kodo ĉar se ni volus skribi programo kun multoblaj studentoj aŭ multoblaj nomoj kaj domoj kaj dormejoj kaj kolegioj kaj ĉiuj de tiu, ni povis stoki ĉiu pli pure ene de tabelo. Sed proponi unu downside de tabelo tiom. Eĉ se vi ne suferis ĝin vi mem en programo, nur instinkte, kio estas malbona afero pri tabelo, eble? Mi aŭdas iun murmuroj. Spektantaro: Ĝi estas malfacila por ŝanĝi la grandecon. DAVID Malan: Estas malfacila por ŝanĝi la grandecon. Vi ne povas ŝanĝi la grandecon de tabelo, fakte, per si en C. Vi povas atribui alia tabelo, movi ĉiun el la malnova en la novan, kaj nun havi iun ekstran spacon, sed ĝi estas ne kiel lingvo kiel Java aŭ Python aŭ ajnan numeron de aliaj lingvoj kun kiu iuj el vi povus esti familiara, kie vi povas simple observu aldonante aferoj ad nauseam al la fino de tabelo. Kiam vi havas aron de grandeco 6, kiu estas lia grandeco, kaj tiel kiel la pli frua ideo havi bufron de certa grandeco, vi devas diveni el la pordego Kiun grandecon vi volas esti? Se vi divenas tro granda, vi malŝparas spacon. Se vi divenas tro malgranda, vi ne povas stoki datumojn kiuj, almenaŭ sen multe pli laboras. 

Do hodiaŭ, danke al punteros, ni povas komenci riparante kune nian propran datumstrukturoj, kaj en Fakte, ĉi tie estas io kiu aspektas iom pli kamufla unuavide, sed tio kion ni nomas kunligita listo, kaj ĝia nomo ia resumas ĝin. Estas listo de nombroj, aŭ en tiu kazo, listo de nombroj, sed povus esti listo de io, sed ĝi estas kunligitaj pere de sagoj, kaj simple preni divenon kun kio tekniko ni tuj povos stebi kune, ia kiel pufmaizo kun fadeno, kunligita listoj rektangulojn tie? Lia nombroj? Kio estas la suba lingvo trajto? 

Publiko: puntero. 

DAVID Malan: puntero. Do ĉiu el tiuj sagoj tie reprezentas montrilo aŭ nur adreson. Do alivorte, se mi volas stoki liston de nombroj, Mi ne povas simple stoki ĝin se mi volas la kapablo kreski kaj ŝrumpi miaj datumstrukturo en tabelo. Do mi devas havi iom pli sofisticación, sed rimarki ke ĉi bildo ia sugestas ke se vi ĵus akiris iom fadenoj konektanta ĉio kune, verŝajne ne estas ke malfacile fari spacon intere du el tiuj rektangulojn aŭ du el tiuj nodoj, kiel ni komencos nomante ilin, metis en nova nodo, kaj tiam kun iu nova fadeno, nur fosaĵo la tri nodoj kune, la unua unu, la lasta, kaj la ke vi ĵus enmetita en la mezo. 

Kaj efektive ligillisto, kontraste tabelo, estas dinamika. Ĝi povas kreski kaj povas ŝrumpi kaj vi ne devas scii aŭ zorgi anticipe kiom multe datumoj vi tuj estos stokante, sed rezultas ni devas esti iom zorgema pri kiel apliki ĉi. Do unue ni pripensi kiel ni efektivigu unu el tiuj malgranduloj ortanguloj. Ĝi estas facila de implementar int. Vi nur diri int n kaj tiam vi ricevas 4 bajtoj por int, sed kiel mi ricevas int, nomas ĝin n, kaj tiam puntero, ni nomas ĝin sekva. Ni povus nomi tiujn aferojn ion ni volas sed mi bezonas kutimo datumstrukturo. Yeah? 

Publiko: ampersand [inaudible]. 

DAVID Malan: Do ampersand ni uzos atingi la adreson de nodo potenciale. Sed ni bezonas alian trajto de C por doni al mi la eblecon krei tiu kutimo rektangulo, tiu kutimo variablo, se vi volas, en memoro. Publiko: struct. DAVID Malan: struct. Memoras de lasta semajno, ni enkondukis struct, tiu relative simpla ŝlosilvorto kiu permesas nin fari aferojn tiel. C ne venis kun datumoj strukturo nomita studento. Ĝi venas kun int kaj kaleŝego kaj char kaj tia, sed ĝi ne venas kun studento, sed ni povas krei studento datumtipo, studento strukturo, kun tiu sintakso tie. Kaj vi vidos tion denove kaj denove. Do ne zorgu pri enmemorigi la ŝlosilvortoj, sed la ŝlosilvorto jen grava estas nur la fakto ke ni diris struct kaj tiam ni nomis studento kaj interne de la studento estis nomo kaj domo aŭ dormejo aŭ similaj. 

Kaj tial nun hodiaŭ, ni proponas ĉi. Mi aldonis kelkajn vortojn, sed se mi volas implementar ĉi rektangulo tio akiris ambaŭ int kaj montrilo, vi scias kion, mi estas tuj deklari struct nomita nodo. Mi ankaŭ, ene de ĝi, tuj diri ke nodo, ĉi ortangulo, ĝi havas int kaj ni vokos ĝi n kaj ĝi havas sekva puntero. Kaj tio estas iom parolema, sed se vi pensas pri ĝi, la sagoj, kiuj estis en la bildo antaŭ momento estas de kion datumtipo? Kie ĉiu de tiuj sagoj notas al kio tipo de datumstrukturo? Ĝi ne montras ĝuste al int por se. Ĝi estas indikante la tutaj rektangula afero kaj ke rektangula aferon, ni diris, estas nomita nodo. Kaj tial ni ia devas rikure difinas ĉi tiaj ke nodo, ni diros, enhavos int nomis n kaj puntero nomis sekva kaj la tipo de datumstrukturo al kiu ke puntero punktoj estas ŝajne tuj esti struct nodo. 

Do tiu estas agrene abundajn kaj nur esti pedanta, la kialo kial ni ne povas simple diru tiu, kiu sincere aspektas multe pli legebla, Estas ĉar revokon ke C legi aferojn supre sube, maldekstre dekstren. Ĝi ne estas ĝis ni preni la punktokomo ke la ŝlosilvorto nodo reale ekzistas. Do se ni volas havi tian cikla referenco ene de la datumoj strukturo, ni devas tion fari, kie ni diri struct nodo ĉe la supro, kiu donas al ni plu vojo priskribi ĉi aferon, tiam ene ni diras struct nodo, kaj tiam ĉe la lasta linio ni diru, bone, C, cetere, simple nomas tiun tutan malbenitan afero nodo kaj haltigi uzante la ŝlosilvorto struct entute. Do tio estas nur ia sintaksa lertaĵo kiu finfine permesas nin krei iu kiu aspektas precize kiel tiu. 

Do se ni supozas nun ni povas efektivigi tion en C, kiel do ni efektive komenci petolanta ĉi? Nu, fakte, ĉiuj ni devas fari estas persisti de maldekstre dekstren kaj ĵus ia enigi nodoj aŭ forigi nodojn aŭ serĉi aferojn kie ajn ni volas, sed por fari tion, ni iru antaŭen kaj fari aferojn iom pli reala pro tio estis súper malaltnivela tiom. Ĉu iu laŭvorte ŝatus esti la unua? BONE. Venu supren. Kio estas via nomo? 

DAVID David. DAVID Malan: Davido. Agrable renkonti vin. Ankaŭ mi. Bone. Kaj ni bezonas numero 9. Ne tiel bona kiel la unua, eble. OK, numero 9. Kelkaj 17, bonvolu. Lasu min reiri iom pli malproksime. Numero 22, bonvolu, kaj kion pri fora reen se mi vidas neniun manoj kun tuta lumo aŭ ne. Iu estas estanta volontulis prava. Ĉu vi volas veni supren? Via antaŭbrako estas perforte suprenirantaj. OK, 17. 22. 26 Venas malsupren. Ĉu ajnulo ŝatas forcefully-- Venu supren. Fakta volontulo. 

Do tre rapide, se vi uloj povus aranĝi vi simple ŝatas la nodoj sur la ekrano. Dankon. Kaj vi estos 26. Bone kaj rapida enkondukoj. Do mi estas Davido kaj vi ankaŭ? DAVID David. DAVID Malan: Kaj vi estas? JAKE: Jake. SUE Sue. ALEX: Alex. RAPHAEL: Rafaelo. Taylor: Taylor. DAVID Malan: Taylor. Bonege. Tiuj estas niaj volontuloj cxar hodiaux kaj antaŭeniri kaj ŝanĝi iom tiu maniero, kaj ĝuste iri antaŭen kaj teni tenante viajn nombrojn kiel vi aŭ via unua signo kaj uzanta vian maldekstran manon iri antaŭen kaj nur efektivigu tiuj sagoj, ĵus por ke via maldekstra mano estas laŭvorte montrante kion vi devus celi je, kaj doni vin iu ĉambro tiel ke ni povas vide vidi viajn brakojn reale notante, kaj vi povas simple atentigi ia ĉe la grundo estas bona. 

Do jen ni havas ligillisto de unu, du, tri, kvar, kvin nodoj komence, kaj rimarki ni havas tiun specialan montrilo ĉe la komenco, kiuj estas ŝlosilo ĉar ni devas konservi trako de la tuta longo listo iel. Tiuj infanoj, eĉ se ili restas al dekstre, reen malantaŭeniri en memoro, ili povas reale esti ie en la komputilo la memoro. Do tiuj infanoj povus esti staras ie sur la scenejo kaj tio estas bone, tiel longe kiel ili estas reale montrante unu la alian, sed konservi aferojn pura kaj simpla, ni nur tiros ilin lasis al rajto kiel tiu, sed povus esti masiva breĉoj en inter tiuj nodoj. 

Nun, se mi volas reale enmeti iun nova valoro, ni iru antaŭen kaj fari tion. Ni havas ŝancon nun elekti alian nodon. Diru ni dividas kun mallocing 55. Ĉu iu gravas esti malloc? OK, venu supren. Kio estas via nomo? RAINBOW: Ĉielarko. DAVID Malan: Ĉielarko? Bone. Malloc Ĉielarko. Venu supren. Do nun ni devas demandi al ni algorítmicamente kie ni povas meti 55. Do ni ĉiuj scias, evidente, kie ŝi verŝajne apartenas se ni provas teni ĉi ordo kaj se vi infanoj povus gluti retropaŝi do ni ne defali la etapo, kiu estus granda. Do efektive, Ĉielarko, komencu super tie kun mi, ĉar ni kiel la komputilo nun povas nur vidi unu variablo samtempe. Do se tiu estas la unua nodo. Rimarku li ne estas nodo, li estas nur montrilo, kaj tial li estas tirita al esti nur la grandecon de puntero, ne unu el tiuj plenaj ortanguloj. Do ni tuj kontroli ĉe ĉiu ripeto estas 55 malpli ol 9? No. Estas 55 malpli ol 17? No. Malpli ol 22? Malpli ol 26? Malpli ol 34? Kaj tial nun, evidente Ĉielarko apartenas fine. Do esti klara, kaj kion estis via nomo, Taylor? 

Taylor: Taylor. DAVID Malan: Do inter Taylor maldekstra mano kaj Cxielarko manoj tien, kies mano devas noti al kio en ordigi enigi 55 en tiu listo? Kion ni devas fari? Yeah? 

Publiko: Taylor mano bezonas atentigi maldekstra. 

DAVID Malan: Ĝuste. Do enmeto nodo en la fino de la listo estas sufiĉe simpla ĉar Taylor ĵus devas atentigi, anstataŭ je la grundo aŭ ni nomas ĝin nula, null estas speco de la foresto el puntero aŭ speciala nulo montrilo, vi estas tuj atentigi kun via maldekstra manon ĉe Ĉielarko kaj tiam Ĉielarko, Kien via maldekstro mano probable punkto? Malsupren. Ĝi ne estas bona se sxi estas speco de indikanta ekstere tie aŭ ia ajn kiudirekten. Kiu konsiderus rubo valoro, sed se ŝi montras al iu konata valoro, ni nomas ĝin nulo aŭ nula, tio estas OK ĉar ni havas terminon en tiu kaj ni konas la listo nun estas kompletaj. 

Do kio estas alia relative simpla kazo? Could ni malloc 5? Venu supren. Kio estas via nomo? TIFFANY: Tiffany. DAVID Malan: Mi bedaŭras? TIFFANY: Tiffany. DAVID Malan: Tiffany. Bone. Tiffany estis malloced kun la valoro 5. Venu supren. Ĉi tiu estas relative facila tro, sed ni konsideru ordo de operacioj nun. Estis sufiĉe facile kun Taylor ĉe la fino. Numero 5 estas kompreneble malpli ol 9 kaj do ni havis David ni havas Tiffany, kaj kio estis via nomo? 

JAKE: Jake. 

DAVID Malan: Jake. Tiffany, Jake, kaj Davido. Kies mano devus esti ĝisdatigita unuan? Kion vi volas fari tie? Ekzistas paro eblaj manieroj, sed Tie estas ankaŭ unu aŭ pli erara manieroj. 

Publiko: Komenci kun plej maldekstra. 

DAVID Malan: Komenci kun la plej maldekstra. Kiu estas la plej maldekstra tie tiam? Publiko: Unua. 

DAVID Malan: Bone. Do komencu kun la unua kaj kie do vi volas ĝisdatigi David manoj esti? Publiko: Al la 5. DAVID Malan: Bone. Kaj David, punkto je kvin aŭ Tiffany tie, kaj nun? 

Publiko: Tiffany notas al la 9? DAVID Malan: Perfekta, krom Binky La kapo nur ia defalis, dekstra? Ĉar kio estas malbone kun ĉi bildo laŭvorte? Publiko: Nenio estas indikante. DAVID Malan: Nenio indikante Jake nun. Ni laŭvorte orfinoj 9 kaj 17, kaj havas ni laŭvorte likis ĉiujn ĉi memoro, ĉar per ĝisdatiganta David mano unuan, jen fajnan mezuro ĝi estas korekte montrante Tiffany nun, sed se neniu havis la Foresight noti al Jake, poste ni perdis la tuteco de tiu listo. Do ni malfari. Por ke estis bona afero stumbli sed ni korektos nun. Kion ni faru unuan anstataŭe? Yeah? 

Publiko: Tiffany devus celi ĉe la 9? DAVID Malan: mi ne povas su ke proksime al vi. Kiu devus celi ĉe la 9? 

Publiko: Tiffany. 

DAVID Malan: Bone. Do Tiffany devus unue punkto je la 9. Do Tiffany devus preni sur identa valoro al David, tio ŝajnas redunda dum momento, sed tio estas bone ĉar nun, dua paŝo, ni povas ĝisdatigi David mano atentigi ĉe Tiffany, kaj tiam se ni nur speco de pura aĵojn kvazaŭ tiu estas speco de printempo-kiel, Jen vere korekta inserción. Do bonega. Do nun ni estas preskaŭ tie. Ni enmeti unu fina valoro kiel la valoro 20. Se ni povus malloc unu fina volontulo? Venu supren. Do ĉi tiu estas iom pli malfacila. Sed vere, la kodo ni estas skribanta, kvankam parole, Estas ĝuste kiel havi faskon de se kondiĉoj nun, ĉu ne? Ni havis kondiĉon kontrolanta se ĝi apartenas fine, eble la komenco. Ni bezonas ian buklo trovi surloke en la mezo. Do ni faru ke kun kio estas via nomo? 

ERIC: Eric. 

DAVID Malan: Eric? Eric. Agrable renkonti vin. Do ni havas 20. Malpli ol kvin? No. Malpli ol naŭ? No. Malpli ol 17? No. BONE. Li apartenas tie kaj viaj nomoj denove estas? SUE Sue. DAVID Malan: Sue. ALEX: Alex. DAVID Malan: Sue, Alex, kaj? ERIC: Eric. DAVID Malan: Eric. Kies manoj devas akiri ĝisdatigita unuan? 

Publiko: Eric. BONE. Do Eric devus celi al kie? Je 22. Bona. Kaj nun kio estas poste? Sue povas tiam noti al Eric kaj nun, se vi infanoj ĵus fari iu ĉambro, kiu estas fajna vide, nun ni faris la inserción. Do ni nun konsideras demandon sed Dankoni vin tiel por niaj volontuloj. Tre bone farita. Vi povas konservi tiujn, se vi volas. Kaj ni havas belan adiaŭa donaco se oni kredus ĉiu ŝatas preni streso pilko. Lasu min nur pasi ĉi malsupren. Do kio estas la takeaway de tio? Ĉi tio ŝajnas esti miriga mezuro ni havas nun enkondukita alternativo al tabelo kiu ne tiel limigita al tabelo de iuj fiksa grandeco. Ili povas kreski dinamike. 

Sed multe kiel ni vidis en semajnoj pasinteco, ni neniam ricevas nenion senpage, kiel certe ekzistas avantaĝinterŝanĝo tie. Do kun inversita de ligitaj listo, estas tiu dinamismo? Tiu kapablo kreski kaj sincere, ni povus fari delete kaj ni povis retiri drajvo. Kio prezo ni pagas? Duoble da spaco, antaŭ ĉio. Se vi rigardas la bildon, ne plu mi stokante listo de entjeroj. Mi stokante listo de entjeroj plus punteros. Do mi duobligante la kvanton de spaco. Nun, eble tio ne tiom granda interkonsento 4 bajtoj, 8 bajtoj, sed certe povus aldoni ĉe grandaj datenaroj. Kio estas alia malavantaĝo? Yeah? 

Publiko: Ni devas _traverse_ ilin unu post unu. DAVID Malan: Yeah. Ni devas trairi ilin unu post unu. Vi scias kion, ni rezignis tiun súper konvena trajto de kvadrata krampo skribmaniero, pli konvene konata kiel hazarda aliro, kie ni povas simple salti al individua elemento sed nun se mi ankoraŭ havis miaj volontuloj tie, se mi volis trovi la numero 22, tion mi ne povas ĝuste salti al krampo ion ion. Mi devas rigardi la liston, multe kiel nia serĉado ekzemploj lineare, trovi la nombron 22. Do ŝajne ni pagis prezon tie. Sed ni povas tamen solvi aliajn problemojn. 

Fakte, mi konigu nur kelkaj vidaĵojn. Do se vi jam estis malsupren al Mather la Dining Hall ĵus, vi memoras, ke iliaj stakoj de pletoj kiel tiu, ni prunteprenis tiujn de Annenberg antaŭ klaso. Do tiu pilo de pletoj, tamen, estas reprezentanto reale de komputika datumstrukturo. Estas datumstrukturo en komputiko konata kiel stako kiu tre bele pruntas al ekzakte tiu vida. Do se ĉiu el tiuj pletoj estas ne pleto sed kiel numero kaj mi volis stoki numerojn, mi povis meti unu malsupren tie, kaj mi povus meti alian tie, kaj daŭrigi stakiganta nombroj unu sur la alia, kaj kio estas potenciale helpema pri tiu estas ke kio estas la implikaĵon de tiu datumstrukturo? Kiun numeron mi povas tiri el unua plej oportune? La plej laste metis sur tie. 

Do ĉi tiu estas kion nomus en komputiko oni LIFO datumstrukturo. Daŭri en, unua el. Kaj ni vidos post nelonge kial kiuj povus esti utilaj sed nuntempe, nur konsideru la proprieto. Kaj ĝi estas speco de stulta se vi opinias pri kiel la manĝejo faras. Ĉiufoje pura pletoj kaj metis la freŝaj sur supro, vi povus havi antaŭe pura sed eventuale tre malpura kaj polvokovrita pleto je la tre fundo se vi neniam reale akiri al la fundo de tiu pilo, ĉar vi simple teni metante la novan kaj purulo sur gxian supron. La sama afero povus okazi en superbazaro ankaŭ. Se vi havas pri kazo de lakto kaj ĉiufoje CVS aŭ kiu ajn akiras pli lakto, vi simple baton la lecha vi jam havas la dorson kaj vi metis la novajn supren fronto, vi tuj havos kelkajn belajn aĉa lakto fine de la datumstrukturo, ĉar ĝi estas ĉiam ĉe la fundo aŭ ekvivalente ĝi estas ĉiam ĉe la dorso. 

Sed estas alia maniero pensi viciganta datumoj kaj ekzemple, tiu. Se vi estas unu de tiuj personoj kiuj ŝatas laŭliniigi ekster Apple tendencas kiam nova produkto venas eksteren, vi probable Ne uzante pilo datumoj strukturo ĉar vi estus fremdigas ĉiuj aliajn kiu estas viciganta aĉeti iun novan ludilon. Prefere, vi probable uzante kia datumstrukturo kian sistemon en la reala mondo? Espereble ĝi estas linio, aŭ pli konvene aŭ pli brite kiel, atendovico. Kaj ĝi rezultas atendovico estas ankaŭ datumstrukturo en komputiko, sed atendovico havas tre malsama proprieto. Ne LIFO. Daŭri en, unua el. Malproksima. Ĝi estas anstataŭe FIFO. Unua en, unua el. Kaj tio estas bona afero por justeco mem certe kiam vi tegante supren super frumatene. Se vi akiras tie la unua, vi volas eliri unuaj ankaŭ. 

Kaj tial ĉiuj ĉi tiuj datumoj strukturoj, vostoj kaj stakoj kaj aroj da aliaj, rezultas vi povas pensi pri tio kiel nur tabelo. Jen tabelo, eble fiksa grandeco 4, sed ĝi estus esti ia agrabla se ni povus simple amasiĝas pletoj preskaŭ senlime alta se ni havas ke multaj pletoj aŭ nombroj. Do eble ni volas uzi ligillisto tie, sed la komerco-off estas iranta esti potenciale ke ni bezonas pli memoro, prenas iom pli da tempo, sed ni ne limigi la altecon de la pilo, multe kiel Mather la ekrano kazo povus limigi la grandecon de la pilo, kaj tiel ili estas dezajno decidojn aŭ disponeblaj ebloj al ni finfine. Do kun tiuj datumoj strukturoj, ni komencis vidante novaj superaj baroj potenciale sur kio antaŭe estis super rapida kaj kie ni lasos ekstere hodiaŭ kaj kie ni esperas atingi estas merkrede, ni komenci rigardi datumoj strukturo, kiu ebligas al ni serĉi tra datumojn en log fino fojo. Kaj ni vidis ke, memoru, en semajno nulo kaj unu kun duuma serĉo aŭ dislimo kaj konkeri. Oni revenis kaj pli bona ankoraŭ, la sankta gralo por tiu merkredo estos veni supren kun la datumstrukturo kiu kuras vere aŭ teorie en konstanta tempo, per kiu ne gravas kiom da milionoj aŭ miliardoj da aferoj ni havas en la datumstrukturo, ĝi volo preni nin konstanta tempo, eble unu paŝo aŭ du paŝojn aŭ 10 paŝojn, sed konstanta nombroj de paŝoj serĉi tra tiu datumstrukturo. Tio ja estos la Sankta gralo sed pli sur tiu merkrede. Vidu ya tiam. 

[MUZIKO Ludante]