[Powered by Google Translate] [Semajno 6] [Davido J. Malan] [Universitato Harvard] [Jen CS50.] [CS50.TV] 

Ĉi tiu estas CS50, kaj ĉi tiu estas la komenco de Semajno 6, tial kelkaj novaj iloj estas nun disponebla por vi utiligi, la unua el kiuj estas nomita CS50 Stilo. Odds estas se vi estas kiel mi aŭ iu el la instruado uloj, vi probable vidis programon kies stilo aspektas iom io tiamaniere. Eble vi komencas tranĉi kelkajn angulojn malfrue en la nokto, aŭ vi trakti ĝin poste, kaj tiam TF aŭ CA venas super dum oficejo horoj. Tiam estas malfacile por ni legas. Nu, ĉi tiu kodo estas sintakse ĝusta, kaj ĝi estos kompili, kaj ĝi estos reale kuri. Sed estas certe ne estas 5 por stilo. 

Sed nun, se ni iros en tiu ĉi dosierujo tie- kaj rimarki ke mi havas conditions2.c- kaj mi kuras tiu nova komando, style50, sur ĉi tiu dosiero conditions2.c, Enter, rimarki ke ĝi estas informis min ke estis stiligita. Gedit rimarkis, ke la dosiero estas ŝanĝita je disko, kaj se mi alklakos reŝargi, ĉiuj viaj problemoj estas jam aŭtomatigita. [Aplaŭdo] Tio estas unu el la aĵoj kiujn ni faris tiun semajnfinon. Rimarkas ke estas malperfekta ĉar estas iom da kodo ke simple ne povos stylize perfekte, sed realigi ĉi estas nun ilo vi povas utiligi eĉ se nur por ordigita kelkaj el la pli errantly metis frizita krampoj kaj similaj. 

Sed pli konvinkaj nun estas CS50 Check. Kun CS50 Check, vi povas efektive realigi la saman praveco provoj en via propra kodo kiu la instruado uloj kapablas. Tio ĉi estas komandlinio utileco kiu venas nun en la aparaton tuj kiam vi faras la update50 kiel por pset 4 especificaciones, kaj vi uzas ĝin esence kiel tion ĉi. Vi kuras la komando check50. Tiam vi pasos en komanda linio argumento, aŭ pli ĝenerale konita kiel ŝaltilo aŭ flago. Ĝenerale, la aĵoj kiuj havas streketoj estas nomitaj ŝaltilo al komandlinio programo, tiel c specifas la ĉekoj, kiujn vi volas kuri. 

La provoj, kiujn vi volas kuri estas identigitaj unike per ĉi ŝnuroj, 2012/pset4/resize. En aliaj vortoj, tio estas nur arbitra sed unika linio ke ni uzas por unike identigi pset 4 de praveco provoj. Kaj tiam vi specifi spaco disigita listo de la dosieroj, kiujn vi volas alŝuti al CS50 Check por analizo. Ekzemple, se mi iros en mian solvon ĉi tie por resize.c- lasu min malfermi pli granda fina fenestro- kaj mi iras antaŭen kaj kuri diru check50-c 2012/pset4/resize, kaj poste mi iras antaŭen kaj specifi la nomoj de la dosieroj, resize.c, kaj poste batis Entajpu, ĝi kunpremas, ĝi alŝutoj, ĝi kontrolas, kaj mi simple ne sukcesis tuta amaso de provoj. La en ruĝa ĉe supre maldekstre diras ke resize.c kaj bmp ekzisti. Tio estis la provo. Tio estis la demando ni demandis. Kaj estas malfeliĉa ĉar la respondo estis falsaj. La blanka suba teksto diras atendis bmp.h ekzisti, kaj tio estas simple mia kulpo. Mi forgesis alŝuti ĝin, do mi bezonas alŝuti ambaŭ dosieroj, resize.c kaj bmp.h. Sed nun rimarki ĉiuj aliaj provoj estas en flava cxar ili ne kuras, kaj do la smiley vizaĝo estas vertikala ĉar li estas nek feliĉaj nek malgaja, sed ni devas kompensi ke afero en ruĝa antaŭ tiuj aliaj ĉekojn kuros. 

Lasu min ripari tion. Lasu min malzomi kaj rerun ĉi, ĉi-foje kun bmp.h ankaŭ sur la komanda linio, Enter, kaj nun se ĉiu iras bone, ĝi tuj kontroli kaj tiam revenu rezulto de-teni vian spiron- ĉiuj verdaj, kio signifas mi faras vere bone en pset 4 ĝis nun. Vi povas vidi kaj konkludi el la priskriba teksto tie ĝuste kio estas ni provis. Ni provis unue ĉu la dosieroj ekzistas? Ni tiam provis faras resize.c kompili? Tiam ni provis faras ĝi ne regrandigi a 1x1 pixeles BMP kiam n, la Regrandigi faktoro, estas 1. Nun, se vi ne havas ideon kion n estas, vi iam vi plonĝi en pset 4, sed tio simple estas prudento kontroli por certiĝi, ke vi ne regrandigi bildo ajn se la Regrandigi faktoro estas 1. Se, kontraŭe, ĝi resizes a 1x1 bilderoj al 1x1 bilderoj BMP al 2x2 korekte kiam n estas 2, tiam simile, mia formas laŭe. 

Unuvorte, tiu celas, oni, prenu la transirante la fingroj eksteren de la ekvacio ĝuste antaŭ vi proponi vian pset. Vi scias precize kion vi TF baldaux scios kiam vi iros sur submeti kelkajn el tiuj problemo aroj, kaj ankaŭ la pedagogian motivado estas vere meti la ŝancon antaŭ vi por ke kiam vi scias apriore ke estas eraroj en via kodo kaj testoj kiuj ne esti aprobita, vi povas meti en pli efika tempo ĝis fronto por solvi tiujn problemojn anstataŭ perdi punktoj, get sugestoj de via TF, kaj poste iru, "Ahh", kiel mi devus pensis, eksteren. Nun almenaŭ ekzistas ilo por helpi vin trovi tion. Oni ne tuj atentigi kie la cimo estas, sed rakontos al vi kio estas sintomático de ĝi. 

Nun realigi la testoj ne estas nepre ĝisfunda. Nur ĉar vi ricevas ekranon plenan de verda smiley edroj ne signifas via kodo estas perfekta, sed ĝi signifas ke jam pasis unu provoj preskribita de la specifon. Foje ni ne liberigi ĉekoj. Ekzemple, whodunit, unu el la aspektoj de pset 4, estas ia seniluziiga se ni donas al vi la respondo pri kio ĝi estas, kaj estas pluraj manieroj por malkaŝi kiu la persono estas en tiu ruĝa bruo. La specifo ĉiam specifi en la estonteco por pset 5 antaŭen kio kontrolas ekzistas por vi. Vi rimarkos ke estas tio blanka URL malsupre. Por la momento, ĉi tiu estas nur diagnozas eligo. Se vi vizitas ke URL, vi ricevos tutan faskon da freneza, kripta mesaĝojn ke vi plene rajtas trarigardi, sed estas plejparte por la personaro por ke ni povas diagnozi kaj elpurigi erarojn en check50 mem. 

Sen enkonduko, ni movos al kie ni cxesis. CS50 biblioteko ni prenis donita por iuj semajnoj, sed tiam lasta semajno, ni komencis senŝeligi reen de la manteloj de ĝi. Ni komencis metante flanken string favore kio anstataŭ? [Studentoj] Char. Char *, kiu estis char * ĉio ĉi momento, sed nun ni ne devas ŝajnigi ke ĝi estas reala datumtipo kordoj. Pli ĝuste, ĝi estas estinta sinonimo de varoj por char *, kaj linio estas vico de signoj, do kial ne havas sencon por reprezenti ĉenojn kiel char * s? Kion oni char * reprezenti en la kunteksto de tiu koncepto de kordoj? Yeah. >> [Studenta] La unua karaktero. Nu, la unua signo, sed ne tute la unua karaktero. Ĝi estas la-[Studentoj] Adreso. Nu, la adreso de la unua signo. Ĉio, kion necesas por reprezenti ĉenon en komputilo la memoro Estas ĝuste la sola adreso de lia unua bitoko. Vi eĉ ne devos scii kiom longe ĝi estas ĉar kiel vi povas diveni ke el dinamike? [Studenta] String longo. Vi povas nomi ĉenon longo, bonega, sed kio faras string longo laboro? Kion ĝi faras? Yeah. [Studenta] Konservu iri ĝis vi ricevas la nula karaktero. Yeah, precize, ĝi nur iterates kun por ciklo, dum ciklo, kion ajn el * al la fino, kaj la fino estas reprezentita per \ 0, la tiel nomata nul karaktero, nul, ne konfuzi kun nula, kiu estas puntero, kiu venos en konversacio denove hodiaŭ. 

Ni senŝeligita reen mantelo de GetInt, kaj tiam ni prenis rigardu GetString, kaj memorigi, ke ambaŭ tiuj funkcioj, aŭ vere, GetString, estis uzanta iu funkcio por fakte analizi, kiu, legu aŭ analizi, la uzanto enigo. Kaj kio estis tiu nova funkcio? Scanf aŭ sscanf. Ĝi fakte venas en kelkaj diversaj gustoj. Estas scanf, ekzistas sscanf, ekzistas fscanf. Nuntempe, tamen, ni enfokusigas la plej facile ilustrita, kaj lasu min antaŭeniri kaj malfermu la aparaton dosiero kiel ĉi tiu, scanf1.c. Ĉi tiu estas super simpla programo, sed kiu faras ion, ke ni neniam faris sen la helpo de la CS50 biblioteko. Ĉi gets an int de uzanto. Kiel ĝi funkcias? Nu, en linio 16 tie, rimarki, ke ni deklaru int nomata x, kaj je ĉi tiu punkto en la historio, kio estas la valoro de x? [Inaudible studento respondon] [Davido M.] Dekstra, kiu scias, iu rubo valoro potenciale, do en 17, ni simple diru al la uzanto donu al mi numeron, bonvolu, kaj paŝo 18 estas kie alvenas interesa. Scanf ŝajnas prunteprenos ideon de printf en kiu uzas tiujn formato kodoj en citilojn. % D estas kompreneble dekuma nombro. Sed kial mi pasante en & x anstataŭ ĝuste x? La unua estas ĝusta. Yeah. [Inaudible studento respondon] Ĝuste, se la celo de tiu programo, kiel la funkcio GetInt mem, estas al preni int de la uzanto mi povas pasi funkcioj ĉiuj variabloj mi volas, sed se mi ne pasi ilin por referenco aux per adreso aŭ per pointer, ĉiuj sinonimo por la hodiaŭa intencoj, tiam tiu funkcio ne havas kapablon ŝanĝi la enhavon de tiu variablo. Tiu pasus en kopio same kiel la kalesxon versio de interŝanĝa ke ni jam parolis pri kelkaj fojoj nun. 

Sed anstataŭe, farante & x, mi laŭvorte pasante en kio? [Studenta] La adreso. >> La adreso de x. Estas kiel desegni mapon por la funkcio nomita scanf kaj dirante tie, tiuj estas direktoj por eron de memoro en la komputilo ke vi povas iri stoki iu entjero in En ordo por sscanf nun faros tion kio operatoro, kion peco de sintakso estas ĝi tuj devos uzi eĉ kvankam ni ne povas vidi ĝin ĉar iu alia skribis ĉi tiun funkcion? En aliaj vortoj - kio estas tio? [Studenta] X legi. Tie tuj estos iuj legado, sed nur rilate al x tie. Se scanf estas pasis la adreso de x, sintakse, kion operatoro estas ligita al ekzistas ie ene de scanf la efektivigo por ke scanf povas fakte skribi numero 2 al tiu adreso? Yeah, do la *. Memoru ke la * estas nia dereference operatoro, kiu esence signifas iri tien. 

Kiam vi estis transdonita adreson, kiel estas la kazo tie, scanf probable-se ni efektive rigardis ĉirkaŭ lia fontkodon- faras * x aŭ la ekvivalento al reale iri al tiu adreso kaj metis kelkajn valoron tie. Nun, kiel por kiel scanf ricevas enigon el la klavaro, ni skuu niaj manoj ekster hodiaŭ. Nur supozi ke la mastruma sistemo permesas sscanf paroli al la uzanto klavaro, sed en ĉi tiu punkto nun en linio 19, kiam ni simple presi x, ŝajnas esti la kazo ke scanf metis an int en x. Tio estas ĝuste kiel scanf funkcias, kaj memori pasintsemajne jen precize kiel GetString kaj GetInt kaj lia alia familio de funkcioj finfine funkcias, kvankam kun malpeza varianco kiel sscanf, kio signifas skani ĉenon anstataŭ la klavaro. Sed ni rigardu iom varianco de ĉi. En scanf2, mi vere ŝraŭbita supren. Kio estas erara-kaj mi kaŝos la komento klarigas tiel- kio estas malbone en tiu programo, versio 2? Estu kiel teknika kiel eble ĉi tiu tempo. Ĝi aspektas sufiĉe bone. Ĝi estas bele dentado, sed- bone, kion pri ni pritrancxu ĝin al pli mallongaj demandoj? Linio 16. Kio estas linio 16 faras en preciza sed teknika angla? Ricevas iom mallerta. Jes, Michael. [Studenta] Oni indikante la unuan literon de kordoj. 

Konsentite, proksima. Lasu min tweak ke iom. Indikante la unuan literon de kordoj, vi estas deklari variablon nomis buffer kiu indikas la unuan adreson de kordoj, aŭ pli ĝuste, ke notos pli specife al char. Rimarku ĝi estas fakte ne montrante ie ĉar ne estas asigno operatoro. Ne egala signo, do ĉiuj ni faras estas atribuo la variablo nomita buffer. Ĝi okazas al esti 32 bitoj ĉar ĝi estas puntero, kaj la enhavo de bufro supozeble fine enhavos adreson de char, sed por nun, kion signifas buffer enhavi? Nur iuj falsaj, kiu scias, iu rubo valoro, ĉar ni ne eksplicite inicializado ĝin, do ni ne devus supozi nenion. Konsentite, tiel nun linio 17 estas-kio ne linion 17 faru? Eble estos varmigi ĉi supre. Ĝi presas kordoj, ĉu ne? Ĝi presas String bonvole. 

Linio 18 estas speco de familiaraj nun en kiujn ni ĵus vidis varianco de ĉi sed kun malsama formato kodo, tiel en linio 18, ni diras scanf jen la adreso de eron de memoro. Mi volas ke vi sonorigi en ĉeno, kiel implicita de% s, sed la problemo estas ke ni ne faris kelkajn aferojn tie. Kio estas unu el la problemoj? [Studenta] Oni provas dereference nula puntero. Bona, nula aŭ nur alie nekonataj punteros. Vi transdonis scanf adreson, sed vi ĵus diris antaŭ momento ke tiu adreso estas iuj rubo valoron ĉar ni ne reale atribui ĝin al nenion, kaj tiel vi diras scanf efektive iru metis ĉenon tie, sed ni ne scias kie tie ankoraux estas, tial ni ne efektive asignitaj memoron por bufro. Cetere, kio vi estas ankaŭ eĉ ne diras scanf? Supozi tio eron de memoro, kaj ne estis rubo valoro, sed vi ankoraŭ ne rakontis scanf io grava. [Studenta] Kie fakte estas, la signo. Ampersand, do en tiu ĉi kazo, ĝi estas bone. Ĉar buffer jam deklaris kiel puntero kun la * peco de sintakso, ni ne bezonas uzi signo ĉar ĝi estas jam adreson, sed mi kredas ke mi aŭdis ĝin ĉi tie. [Studenta] Kiom granda estas tio? Bona, ni ne diras scanf kiom granda ĉi buffer estas, kio signifas eĉ se buffer estis pointer, ni jene scanf, metis ĉenon tie, sed tie povis esti 2 bajtoj, povus esti 10 bitokoj, povus esti megabajto. Scanf havas neniun ideon, kaj ĉar ĉi tiu estas peco de memoro supozeble, ne ĉenon ankoraŭ. Tio estas nur linio iam skribas signojn kaj \ 0 tiun eron de memoro. Nun estas nur iu bloko de memoro. Scanf ne scias kiam halti skribi al tiu adreso. 

Se vi memoras iujn ekzemplojn en la pasinteco, kie mi hazarde tajpita sur la klavaro provante superflui buffer, kaj ni parolis vendrede pri ekzakte tio. Se kontraŭulo iel injektas en vian programon multe pli grandan vorton aŭ frazo aŭ frazo tiam vi atendis povas invadita eron de memoro, kiu povas havi malbonajn konsekvencojn, kiel porti sur la tuta programo mem. Ni devas redifini tiun iel. Lasu min malzomi kaj iru en versio 3 de tiu programo. Tio estas iomete pli bona. En ĉi tiu versio, rimarki la diferencon. En linio 16, mi denove deklari variablon nomis buffer, sed kio estas tio nun? Ĝi estas tabelo de 16 signoj. Ĉi tiu estas bona ĉar tio signifas Mi povas nun diri scanf jen reala bloko de memoro. Vi povas preskaŭ pensas pri tabeloj kiel punteros nun, kvankam ili ne estas reale ekvivalento. Ili devos konduti malsame en malsamaj kuntekstoj. Sed estas certe la kazo ke buffer estas referenco 16 apudaj signoj ĉar tio estas kio tabelo estas kaj estis por iuj semajnoj nun. 

Ĉi tie, mi diras scanf jen eron de memoro. Ĉi-foje ĝi estas reale eron de memoro, sed kial estas tiu programo ankoraŭ explotable? Kio okazas ankoraŭ? Mi diris al mi 16 bitokoj sed- [Studenta] Kio se tajpi en pli ol 16? Ĝuste, kio okazos se la uzanto tajpas en 17 signoj aŭ 1700 karakteroj? Fakte, ni vidu, se ni ne povas vojaĝo super ĉi eraro nun. Estas bona, sed ne perfekta. Lasu min kaj kuras fari scanf3 kompili tiun programon. Mi kuros scanf3, String petas: saluton, kaj ni ŝajnas esti bone. Lasu min provi iomete pli longa unu, saluton tie. Konsentite, ni do saluton tie kiel vi fartas hodiaŭ, Enter. Getting ia sorto tie, diru saluton tie kiel vi fartas. Damn it. Konsentite, do ni havas bonŝanca. Ni vidu se ni ne povas ripari tion. Ne, ĝi ne tuj lasu min kopii. Ni provu ĉi denove. Bone, staras. Ni vidos kiel longe mi povas ŝajnigi enfokusigi dum ankoraŭ faras tion. Damn it. Tio estas iom taŭga, fakte. Tie ni iru. Punkto faris. 

Tiu, hontinda kvankam ankaŭ estas, ĝi estas ankaŭ unu el la fontoj de granda konfuzo kiam skribas programojn kiuj havas erarojn ĉar ili elmontras sin nur tempaltempe kelkfoje. La realaĵo estas, ke eĉ se via kodo estas tute rompita, eble nur tute rompita tempaltempe ĉar kelkfoje, esence kio okazas estas la mastruma sistemo allocates iom pli memoro ol vi vere bezonas ial ajn kaj tiel neniu alia uzas la memoron dekstra post via bloko de 16 signoj, do se vi iras al 17, 18, 19, ajn, ne tiom granda interkonsento. Nun, la komputilo, eĉ se ĝi ne frakasi al tiu punkto, povus eventuale uzi bajto numero 17 aŭ 18 aŭ 19 por io alia, je kiu notas viajn datumojn kiujn vi metis tie, kvankam troe longa, tuj akiri anstataŭigi potenciale per iu alia funkcio. Oni ne nepre tuj restos nerompita, sed ne nepre kaŭzas seg kulpo. Sed en ĉi tiu kazo, mi fine havigis sufiĉe da signoj ke mi esence superis mian segmento de memoro, kaj bam, la mastruma sistemo diris: "Pardonu, ke estas nenia bono segmentación kulpo." 

Kaj ni vidu nun se kio restas tie en mia katalogo- rimarki, ke mi havas tiun dosieron ĉi tie, kerno. Rimarku ke tiu estas denove alvokis kernan dump. Estas esence dosiero kiu enhavas la enhavo de via programo memoro je la punkto al kiu frakasis, kaj justa por provi iom ekzemplo tie lasu min iri ĉi tien kaj kuri gdb en scanf3 kaj tiam specifi tria argumento nomata kerno, kaj rimarki tie ke se mi printi la kodon, ni povos kiel kutime kun gdb komenci promenante tra tiu programo, kaj mi povas ruli ĝin kaj tuj kiam mi batis-kiel kun la paŝo komandon en gdb- kiam mi batis la potenciale kalesxo linio post tajpi en grandioza kordoj, Mi povos reale identigi ĝin ĉi tie. Pli pri tio, tamen, en sekcio en terminoj de kerno vertederos kaj similaj tiel ke vi povas reale poke ĉirkaŭ interne de la kerno escorial kaj vidi sur kio linio la programo fiaskis. Demandojn tiam punteros kaj sur adresoj? Ĉar hodiaŭ, ni tuj komencos prenante por koncedis, ke tiuj aĵoj ekzistas kaj ni scias precize, kion ili estas. Jes. 

[Studenta] Kiel veni al vi ne devis meti signon apud la parto- Bona demando. Kiel veni, mi ne devas meti-simbolo apud la karaktero tabelo kiel mi faris antaŭe kun la plimulto de niaj ekzemploj? La mallonga respondo estas tabeloj estas iom speciala. Vi povas preskaŭ pensas buffer kiel reale esti adreson, kaj ĝuste tiel okazas al esti la kazo ke la kvadrata krampo skribmaniero estas oportuneco por ke ni povas iri en krampo 0, krampo 1, krampo 2, sen devi uzi la * skribmaniero. Tio estas iom da blanka mensogo ĉar tabeloj kaj punteros Estas, fakte, iomete malsama, sed ili povas ofte sed ne ĉiam povas uzi sendiference. Mallonge, kiam funkcio atendas puntero al eron de memoro, vi povas ĉu pasi ĝin adreson kiu revenis por malloc, kaj ni vidos malloc denove antaŭ longaj, aŭ vi povas pasi ĝin la nomo de tabelo. Vi ne devas fari signon kun tabeloj ĉar ili estas jam esence kiel adresoj. Tio estas la escepto. La rektaj krampoj fari ilin speciala. 

Ĉu vi povas meti signon apud la buffer? Ne en ĉi tiu kazo. Tio ne funkcias ĉar, denove, de ĉi tiu angulo kazo kie tabeloj ne estas sufiĉe reale adresoj. Sed ni eble revenos al tiu post nelonge kun aliaj ekzemploj. Ni provu solvi problemon ĉi tie. Ni havas datumstrukturo kiun ni uzis por iu tempo konata kiel tabelo. Kazo en punkto, tio estas kio ni ĵus havis. Sed tabeloj havas iun upsides kaj downsides. Arrays estas bela kial? Kio estas unu afero, kiun vi ŝatus-al la mezuro vi ŝatas arrays-pri tabeloj? Kio estas konvena por ili? Kio estas konvinkaj? Kial ni enkondukas ilin en la unua loko? Yeah. [Studenta] Ili povas stoki multe da datumoj, kaj vi ne devas uzi tutan aferon. Vi povas uzi sekcio. Bona, kun tabelo vi povas stoki multe da datumoj, kaj vi ne nepre devas uzi ĉiuj ĝin, do vi povas overallocate, kiu povus esti oportune se vi ne scias anticipe kiom de io devas atendi. 

GetString estas perfekta ekzemplo. GetString, skribita de ni, ne havas ideon kiom da signoj por atendi, do la fakto, ke ni povas atribui pecoj de apudaj memoro estas bona. Arrays ankaŭ solvi problemon ni vidis paron semajnoj nun kie estas via kodo komencas devolve en iu tre malbone desegnitaj. Memori, ke mi kreis studento strukturo alvokis Davidon, kaj do estis fakte alternativo, kvankam, al havi variablo nomis nomon kaj alia variablo nomas, mi kredas, domo, kaj alia variablo nomata ID ĉar en tiu rakonto mi tiam volis enkonduki ion alian kiel Rob en la programo, do tiam mi decidis atendi minuton, Mi bezonas renomi tiujn variablojn. Ni nomas mia name1, ID1, house1. Ni nomas Rob la name2, house2, ID2. Sed tiam atendi minuton, kio pri Tommy? Tiam ni havis tri pli variabloj. Ni enkondukis iu alia, kvar aroj de variabloj. La mondo komencis akiri senorda tre rapide, do ni enkondukis structs, kaj kio estas konvinkaj pri struct? Kion C struct lasu vin fari? Estas vere mallertaj hodiaŭ. Kio? >> [Inaudible studento respondon] Yeah, specife, typedef permesas krei novan datumtipo, kaj struct, la struct ŝlosilvorto, permesas encapsular koncepte rilataj pecoj de datumo kune kaj poste nomi ilin iu kiel studento. 

Tio estis bona ĉar nun ni povas modeli multe pli ia koncepte konsekvenca la nocio de studento en variablo anstataŭ arbitre havi unu por linio, unu por ID, kaj tiel plu. Arrays estas bela ĉar ili permesas al ni starti purigi nian kodon. Sed kion estas malavantaĝo nun de tabelo? Kion vi povas fari? Yeah. [Studenta] Vi devas scii kiom granda estas. Vi devas scii kiom granda ĝi estas, tia ĝi estas speco de doloro. La de vi kun antaŭa programado sperto scias, ke en multaj lingvoj, kiel Java, vi povas peti eron de memoro, specife tabelo, kiom granda vi estas, kun longa, posedaĵoj, por tiel diri, kaj tio estas vere oportuna. En C, oni povas eĉ nomi strlen sur generic tabelo ĉar strlen, kiel la vorto indikas, estas nur por kordoj, kaj vi povas diveni la longo de kordoj pro ĉi tiu homa konvencio havi \ 0, sed tabelo, pli genéricamente, estas nur eron de memoro. Se estas array de ints, tie ne estas tuj estos iu speciala karaktero fine atendas vin. Oni devas memori, la longo de tabelo. Alia malavantaĝo de tabelo starigis lian kapon en GetString mem. Kio estas alia malavantaĝo de tabelo? Sinjoro, nur vi kaj mi hodiaŭ. [Inaudible studento respondon] >> Estas kio? Oni deklaris la stako. Konsentite, deklaris je la stako. Kial vi ne volas tion? [Studenta] Ĉar ĝi prenas reutilizado. Ĝi prenas reutilizado. Konsentite, se vi uzas tabelo destini memoro, vi ne povas, ekzemple, redoni ĝin ĉar ĝi estas sur la stako. Konsentite, tio estas malavantaĝo. Kaj kiel pri unu alia kun tabelo? Kiam vi destini ĝin, vi estas speco de ŝraŭbita se vi bezonas pli da spaco ol tiu tabelo havas. 

Tiam ni enkondukis, revokon, malloc, kiu donis al ni la kapablon dinamike rezervi memoron. Sed kion se ni provis alian mondon tute? Kio se ni volis solvi kelkajn el tiuj problemoj do ni anstataŭ-mia plumo falis dormanta tie- kio se ni anstataŭ volis esence krei mondo kiu ne plu tiel? Jen tabelo, kaj, kompreneble, ĉi tiu speco de malboniĝas iam ni batis la fino de la tabelo, kaj mi nun ne plu havas spacon por alia entjero aŭ alia signo. Kio se ni ia preemptively diri bone, kial ni ne relax ĉi tiun kondiĉon, ke ĉiuj tiuj pecoj de memoro estu apudaj malantaŭo al malantaŭo, kaj kial ne, kiam mi bezonos int aŭ char, nur donu al mi spacon por unu el ili? Kaj kiam mi bezonas alian, donu al mi alian spacon, kaj kiam mi bezonas alian, donu al mi alian spacon. La avantaĝo de kiu nun estas ke se iu alia prenas la memoro pri cxi tie, sen granda interkonsento. Mi prenos tiun plian eron de memoro tie kaj tiam ĉi tiu. 

Nun, la sola catch tie estas kiu ĉi tiu preskaŭ sentas mi havas tuta amaso de malsamaj variabloj. Ĉi sentas kvin malsamaj variabloj potenciale. Sed kion se ni sxtelus ideon de kordoj per kiu ni iel ligi tion kune koncepte, kaj kion se mi faris ĉi tion? Ĉi tio estas mia tre malbone desegnita sago. Sed supozu ke ĉiu el tiuj pecoj de memoro punktita al la alia, kaj tiu ulo, kiu ne havas frato al lia dekstra, havas ne tia sago. Tiu estas fakte kio nomiĝas ligillisto. Tio ĉi estas nova datumstrukturo kiu permesas al ni destini eron de memoro, tiam alia, tiam alia, tiam alia ajn ni volas dum programo, kaj ni memoru, ke ili estas ĉiuj iel rilataj per laŭvorte ĉenante ilin kune, kaj ni faris tiun pictóricamente tie kun sago. Sed en kodo, kio estus la meĥanismo per kiu vi povus iel konekti, preskaŭ kiel Scratch, unu eron al alia bloko? Ni povus uzi pointer, ĉu ne? Ĉar vere la sagon kiu okazas de la supro maldekstro kvadrata, this guy tie al ĉi tiu, povus enhavi ene de ĉi tiu kvadrata Ne nur iuj ints, ne nur kelkaj char, sed kio se mi efektive asignitaj iom superflua spaco por ke nun, ĉiu el miaj pecoj de memoro, kvankam tiu tuj kostis al mi, nun aspektas iom pli rektangula kie unu el la pecoj de memoro estas uzata por nombro, kiel la numero 1, kaj tiam se ĉi ulo stokas la numero 2, tiu alia bloko de memoro estas uzata por sago, aŭ pli konkrete, puntero. Kaj supozu mi stoki la numero 3 super tie, dum mi uzas tiun noti en tiu ulo, kaj nun ĉi ulo, ni supozas, ke mi nur volas tri tiaj pecoj de memoro. Mi desegnas linion tra tiu, indikante nula. Ne estas plia signo. 

Efektive, tiu estas kiel ni povas iri sur implementando iu kiu nomas lerta kunligita. Al ligitaj listo estas nova datumstrukturo, kaj ĝi estas ŝtupo al multe amatoro datumstrukturoj kiuj komencas solvi problemojn laŭ la linioj de Facebook-tipo problemoj kaj Google-tipo problemoj kie vi havas grandegan datumoj aroj, kaj ĝi ne plu tranĉas ĝin stoki ĉio contiguously kaj uzi ion kiel lineara serĉo aŭ eĉ iu kiel duuma serĉo. Vi volas eĉ pli bone kurante foje. Fakte, unu el la Sankta Grails ni parolos pri ĝi poste ĉi-semajne aŭ apud estas algoritmo kies rula tempo estas konstanta. En aliaj vortoj, ĝi ĉiam havas la saman kvanton de tempo ne gravas kiel granda la enigo estas, kaj ke ili estas konvinkaj, eĉ pli ol io logaritma. Kio estas tio sur la ekrano tie? Ĉiu el la rektanguloj estas precize kion mi ĵus tiris mane. Sed la afero tuta vojo maldekstre estas speciala variablo. Ĝi okazas esti sola puntero ĉar la gotcha kun ligitaj listo, kiel tion nomas, estas ke vi devas pendi sur unu fino de la ligitaj listo. 

Ĝuste kiel kun ĉeno, vi devas scii la adreson de la unua signo. Sama traktado por ligitaj listoj. Vi devas scii la adreson de la unua bloko de memoro ĉar de tie, vi povas atingi ĉiun alia. Malavantaĝo. Kio prezo ni pagas por ĉi versatilidad havi dinamike konsiderinda datumstrukturo ke se ni iam bezonos pli memoro, fajna, nur atribui pli chunk kaj desegni puntero de la malnova al la nova vosto de la listo? Yeah. [Studenta] Ĝi prenas pri duoble da spaco. Ĝi prenas duoble da spaco, tiel ke estas definitive malavantaĝo, kaj ni vidis tiun tradeoff antaŭe inter tempo kaj spaco kaj fleksebleco kie por nun, ni bezonas ne 32 bitojn por ĉiu el tiuj numeroj. Ni vere bezonas 64, 32 por la nombro kaj 32 por la puntero. Sed hey, mi havas 2 gigabajtoj de RAM. Aldoni alian 32 bitoj tie kaj ĉi tie ne ŝajnas, ke granda de traktadon. Sed por grandaj datenaroj, ĝi definitive aldonas ĝis laŭvorte duoble da. Kio estas alia malavantaĝo nun, aŭ kio trajto ni rezignu, se ni reprezentas lertaj de aĵoj kun ligitaj listo kaj ne tabelo? [Studenta] Oni ne povas trairi ĝin malantaŭen. Vi ne povas trairi ĝin malantaŭen, do vi estas speco de ŝraŭbita se vi marŝante de maldekstre al dekstre uzante por buklo aŭ dum buklo kaj tiam vi rimarkas, "Ho, mi volas reiri al la komenco de la listo." Vi ne povas ĉar tiuj indikoj nur iri de maldekstre al dekstre, kiel la sagoj indikas. 

Nun, vi povus memori la komencon de la listo kun alia variablo, sed tio estas komplekseco teni en la menso. Tabelo, ne gravas kiom for you go, vi povas ĉiam fari minus, minus, minus, minus kaj reiri de kie vi venis. Kio estas alia malavantaĝo tie? Yeah. [Inaudible studento demando] Vi povus, do vi fakte nur proponis datumstrukturo nomata duoble ligitaj listo, kaj ja, vi aldonus alian sagon al ĉiu el tiuj rektanguloj kiu iras al la alia direkto, la supra parto de kiuj estas nun vi povas trairi tien kaj reen, la malavantaĝo de kiuj estas nun vi uzas trioble tiel memoro kiel ni uzas por kaj ankaŭ aldoni komplekseco en terminoj de la kodo vi devas skribi por ricevi ĝin dekstre. Sed tiuj estas ĉiuj eble tre racia tradeoffs, se la renversigon estas pli grava. Yeah. [Studenta] Vi ankaŭ povas ne havi 2D ligillisto. Bona, vi ne povas vere havi 2D ligitaj listo. Vi povus. Ne preskaŭ tiel facila kiel tabelo. Kiel tabelo, vi faras malferma krampo, fermita krampo, malferma krampo, fermita krampo, kaj vi ricevas iun 2-dimensia strukturo. Vi povus efektivigi 2-dimensia ligitaj listo se vi faros add-kiel vi proponis-tria puntero al ĉiu el tiuj aĵoj, kaj se vi pensas pri alia listo venas ĉe vi 3D stilo de la ekrano al ni ĉiuj, kiu estas nur alia ĉeno de ia. Ni povus fari ĝin, sed ĝi ne estas tiel simpla kiel tajpi malferma krampo, kvadrata krampo. Yeah. [Inaudible studento demando] Bona, do ĉi tiu estas vera kicker. 

Ĉi tiuj algoritmoj kiuj ni pined super, kiel ho, duuma serĉo, Vi povas serĉi tabelo de nombroj sur la tabulo aŭ telefono libro tiom pli rapide se vi uzas dividi kaj venki kaj duuma serĉo algoritmo, sed duuma serĉo postulis du supozoj. Unu, kiun la datumoj estis ordo. Nun, ni povas supozeble teni ĉi ordo, do eble tio ne maltrankvilo, sed duuma serĉo supozis ankaŭ ke vi havis hazarda aliro al la listo de nombroj, kaj tabelo permesas havi senvica atingo, kaj por hazarda aliron, Mi volas diri, se vi donas tabelo, kiom da tempo estas preni vin alveni ĝis krampo 0? Unu operacio, vi simple uzu [0] kaj vi pravas tie. Kiom da paŝoj necesas por atingi lokon 10? Unu paŝo, kiun vi ĵus iras al [10] kaj vi estas tie. Kontraste, kiel vi atingos la 10-a entjero en ligitaj listo? Vi devas starti komence ĉar vi nur memorante la komencon de ligitaj listo, nur kiel cxeno estas memoris per la adreso de lia unua char, kaj trovi ke 10th int aŭ kiu 10th karaktero en linio, oni devas serĉi la tuta malbenita afero. 

Denove, ni ne solvanta ĉiu el niaj problemoj. Ni enkondukante novaj, sed vere dependas de kion vi provas desegni por. En terminoj de efektivigo de ĉi tiu, ni povas pruntepreni ideon de tiu studento strukturo. La sintakso estas tre similaj, krom nun, la ideo estas iom pli abstrakta ol domo kaj nomon kaj IRU. Sed mi proponas ke ni povus havi datumstrukturo en C kiu estas nomata nodo, kiel la lasta vorto sur la glito sugestas, ene de nodo kaj nodo estas nur ĝenerala ujo en komputiko. Ĝi estas kutime desegnitaj kiel cirklo aŭ kvadrato aŭ rektangulo kiel ni faris. Kaj en ĉi tiu datumstrukturo, ni havas int, n, do jen la nombro mi volas konservi. Sed kio estas tiu dua linio, struct nodo * poste? Kial estas ĉi ĝentila, aŭ kio rolon faras tion ludo, kvankam ĝi estas iom enigmaj unuavide? Yeah. [Inaudible studento respondon] Precize, do la * ia boteto ke ĝi estas puntero de iu tipo. La nomo de ĉi puntero estas arbitre proksima, sed ni povus esti nomis ion ni volas, sed kion faras ĉi puntero punkto al? [Studenta] Alia nodo. >> Precize, ĝi notas al alia tia nodo. 

Nun, ĉi tiu estas speco de vidindaĵo de C. Rememoru, ke C estas legita de tradukilo supre sube, maldekstre dekstren, kio signifas se-ĉi estas iom malsama kion ni faris kun la lernanto. Kiam ni difinis studento, ni efektive ne enmetis vorton tie. Ĝi simple diris typedef. Tiam ni havis int id, kordoj nomo, string domo, kaj tiam studento en la fundo de la struct. Tiu deklaro estas iom malsama ĉar, denove, la C-tradukilo estas iom stulta. Ĝi estas nur tuj legi supre sube, do se ĝi atingas la 2-a linio tie kie apud estas deklarita kaj vidas, ho, jen variablo nomas proksima. Estas puntero al struct nodo. La tradukilo tuj rimarkas kion estas struct nodo? Mi neniam aŭdis pri tiu afero antaŭ, ĉar la vorto nodo eble ne alie aperas ĝis la fundo, tiel estas ĉi redundo. Vi devas diri struct nodo tie, kiu povas tiam mallongigi poste danke al typedef cxi tie, sed ĉi tio estas ĉar ni referenco la strukturo mem ene de la strukturo. Tio estas la gotcha tie. 

Kelkaj interesaj problemoj tuj levigxu. Ni havas liston de nombroj. Kiel ni enŝovu en ĝin? Kiel ni serĉi ĝin? Kiel ni forigi el ĝi? Speciale nun ke ni devas administri ĉiujn tiujn punteros. Vi pensis punteros estis ia menso-fleksio kiam vi havis unu el ili nur klopodis legi int al ĝi. Nun ni devas manipuli ĉiun listo de valoris. Kial ni ne prenos nian 5-minuta paŭzo tie, kaj tiam ni venigos iuj homoj sur scenejo fari precize tion. 

C estas multe pli amuza kiam ĝi agis eksteren. Kiu laŭvorte ŝatas esti la unua? Konsentite, venu supren. Vi estas unua. Kiu ŝatus esti 9? Konsentite, 9. Kion pri 9? 17? Iom kliko tie. 22 kaj 26 en tiu unua vico. Kaj tiam kion pri iu tie esti notita al. Vi estas 34. Konsentite, 34, venu supren. Unue estas tie. Konsentite, ĉiuj kvar el vi guys. Kaj kiu ni ne diras por 9? Kiu estas nia 9? Kiu vere volas esti 9? Bone, iras, esti 9. Ĉi tie ni iru. 34, ni renkontos vin tie. La unua parto estas fari vin rigardi tiel. 26, 22, 17, bona. Se vi povas stari sur la flanko, ĉar nin tuj malloc vi en momento. 

Bona, bona. Konsentite, bonega, do ni petu kelkajn demandojn tie. Kaj efektive, kio estas via nomo? >> Anita. Anita, bone, venu ĉi tien. Anita tuj por helpi al ni ia solvi unu sufiĉe simpla demando en la komenco, kiu estas kiel vi trovos ĉu valoro estas en la listo? Nun, rimarki ke unue, reprezentita tie de Lucas, estas iom malsamaj, kaj tial lia peco de papero estas intence flanken ĉar ĝi estas ne tute tiel alta kaj ne prenu tiom da bitoj, kvankam teknike li havas la saman grandecon de papero nur turnis. Sed li estas iom malsama en kiu li estas nur 32 bitoj por puntero, kaj ĉiuj el tiuj infanoj estas 64 bitoj, duono el ili estas la numero, duono el kiuj estas puntero. Sed la montrilo ne priskribis, do se vi infanoj povis iom mallerte uzu vian maldekstran manon por noti en la persono apud vi. Kaj vi estas numero 34. Kio estas via nomo? Ari. Ari, do vere, teni la paperon en Via dekstra mano, kaj maldekstra mano iras rekte malsupren. Vi reprezentas nula maldekstre. 

Nun nia homa bildo estas tre kohera. Tiu estas fakte kiel punteros labori. Kaj se vi povas scrunch iom tiamaniere tiom Mi ne en via vojo. Anita tie, trovi min la numero 22, sed supozas limigo de ne homoj tenante supren pecoj de papero, sed ĉi tiu listo, kaj vi havas nur Lucas komenci kun ĉar li estas laŭvorte la unua montrilo. Supozi vi mem estas puntero, kaj tiel vi tro havas la kapablon marki ion. Kial ne komenci per la atentigo ke precize kion Lucas montrante? Bona, kaj lasu min proklami ĉi super tie. Ĝuste pro diskuto, lasu min eltiri supren malplenan paĝon tie. Kiel vi literumi vian nomon? >> Anita. Konsentite, Anita. Diru nodo * Anita = Lucas. Nu, ni ne nomu vin Lucas. Ni devus voki vin unue. Kial estas ĉi fakte konsekvenca kun realo ĉi tie? Unu, unue jam ekzistas. Unue estis asignitaj supozeble ie ĉi tien. Nodo * unue, kaj ĝi estas estinta asignitaj listo iel. Mi ne scias kiel tio okazis. Tio okazis antaux klaso komencis. Ĉi ligitaj listo de homoj estas kreita. Kaj nun, je ĉi tiu punkto en la historio-ĉi estas ĉiuj tuj en Facebook ŝajne poste- en ĉi tiu punkto en la historio, Anita estis inicializado esti egala al la unua, kio ne signifas ke Anita punktoj je Lucas. Pli ĝuste, ŝi notas al tio, kion li notas en ĉar la sama adreso kiu estas interne de Lucas de 32 bitoj - 1, 2, 3 - nun estas ankaŭ ene de Anita la 32 bitoj - 1, 2, 3. 

Nun trovi 22. Kiel vi irados tra faras tion? Kio estas tio? >> Punkto al kiom. Indikas kion ajn, do iru antaŭen kaj agi ĝin kiel plej bone tie. Bona, bona, kaj nun vi montras al-kio estas via nomo kun 22? Rajmondo. >> Rajmondo, tiel Rajmondo estas tenante ĉe 22. Vi nun faris ĉekon. Ĉu Rajmondo == 22, kaj se jes, ekzemple, ni povas reveni vera. Lasu min-dum tiuj infanoj staras tie iom mallerte- lasu min fari ion rapide kiel bool trovi. Mi tuj iros antaŭen kaj diru (nodo * listo, int n). Mi tuj revenis kun you guys. Mi nur devas skribi iom da kodo. Kaj nun mi iros al faru tion, nodo * Anita = listo. Kaj mi tuj iros antaŭen kaj diru dum (Anita! = NULL). 

La metaforo tie ricevas iom streĉita, sed dum (Anita! = NULL), kion mi volas fari? Mi bezonas iun vojon de referenco la entjera ke Anita estas montrante. En la pasinteco, kiam ni havis strukturoj, kiuj nodo estas, ni uzis la skalara skribmaniero, kaj ni devus diri ion kiel anita.n, sed la problemo estas, ke Anita ne estas struct per si mem. Kio ŝi estas? Ŝi estas puntero, do vere, se ni volas uzi ĉi punkto notacio- kaj ĉi tuj serĉos intence iom críptico- ni devas fari ion kiel iri al kiom Anita la maldekstra mano montrante kaj poste la kampo nomata n. Anita estas puntero, sed kio estas * Anita? Kion vi trovos kiam vi iras al kio Anita notas en? Al struct, nodo, kaj nodo, revokon, havas kampo nomata n ĉar ĝi, memoras, tiuj 2 kampoj, apud kaj n, kiun ni vidis antaŭ momento ĉi tie. 

Por reale imiti tion en kodo, ni povus fari tion, kaj diru se ((* Anita). n == n), la n kiun Mi serĉas. Rimarku ke la funkcio estis aprobita en la numero mi zorgas pri. Tiam mi povas faru iun kiel reveno vera. Alian, se tio ne estas la kazo, kion mi volas fari? Kiel mi traduki por kodi kion Anita faris tiel intuicie marŝante tra la listo? Kion mi faru ĉi tien por simuli Anita porti tiun paŝon al la maldekstro, kiu paŝo al la maldekstra? [Inaudible studento respondon] >> Kio estas tio? [Inaudible studento respondon] Bona, Ne malbona ideo, sed en la pasinteco, kiam ni faris tion, ni faris Anita + + ĉar tio aldonus la numero 1 al Anita, kiu tipe notas en la sekvanta persono, kiel Rajmondo, aŭ la persono apud li, aux la apud li persono laŭ la linio. Sed tio ne estas sufiĉe bona ĉi tie, ĉar kion signifas tion rigardi kiel en memoro? Ne tiel. Ni devas malebligi tion. Ĝi aspektas kiel tiu en la memoro, kaj kvankam mi desegnis 1 kaj 2 kaj 3 proksimaj unu al la alia, se ni vere simuli ĉi-can you guys, dum ankoraŭ montrante ĉe la sama homo, povas iujn el vi prenu hazarda retropaŝo, iuj el vi hazarda paŝo antaŭeniras? 

Ĉi salaton estas ankoraŭ ligillisto, sed ĉi tiuj infanoj povis esti ie ajn en memoro, tiel Anita + + ne tuj funkcias kial? Kio estas en loko Anita + +? Kiu scias. Estas kelkaj aliaj valoro kiu ĝuste tiel pasas al intermetis inter ĉiuj tiuj nodoj hazarde ĉar ni ne uzante tabelo. Ni destinis ĉiu el tiuj nodoj individue. Konsentite, se vi infanoj povas purigi vin back up. Lasu min proponas ke anstataŭ Anita + +, ni anstataŭ fari Anita gets- bone, kial ni ne iras al kiom Anita estas montrante kaj poste fari. poste? Alivorte, ni iru al Rajmondo, kiu kaŝas la numero 22, kaj tiam. sekva estas kvazaŭ Anita estus kopii lian maldekstran manon puntero. Sed ŝi ne volis iri pli for ol Rajmondo ĉar ni trovis 22. Sed tio estus la ideo. Nun, ĉi tiu estas dio-terura katastrofo. Honeste, neniu iam memoras tiun sintakson, kaj tiel dankeme, ĝi estas fakte iom diskutita-ho, vi ne vere vidi kion mi skribis. Ĉi tiu estus pli konvinkaj se vi povus. Voila! 

Malantaŭ la kulisoj, mi solvi la problemon tiel. Anita, preni tiun paŝon al la maldekstro, unue, ni iru al la adreso kiun Anita estas montrante kaj kie ŝi trovos ne nur n, kiun ni ĵus kontrolis por komparo, kalkaj, sed vi trovos ankaŭ sekva - en ĉi tiu kazo, Rajmondo la maldekstra mano montrante al la sekvanta nodo en la listo. Sed ĉi tiu estas la dio terura katastrofo, al kiu mi raportis pli frue, sed ĝi rezultas C lasas nin simpligi ĉi. Anstataŭ skribo (* Anita), ni povas anstataŭ simple skribi Anita-> n, kaj estas la ĝusta sama afero funkcie, sed estas multe pli evidenta, kaj estas multe pli kohera kun la bildo kiun ni estis desegni tiel longe uzante sagoj. 

Fine, kion ni bezonas por fari al la fino de tiu programo? Estas unu linio de kodo restanton. Reveno kio? Falsa, ĉar se ni finos la tutan dum buklo kaj Anita estas, fakte, nula, kiu signifu ŝi iris tutan vojon al la fino de la listo kie ŝi notis al-kio estas via nomo denove? Ari. >> Ari la maldekstra mano, kiu estas nula. Anita nun nula, kaj mi rimarkas ke vi ĵus staris tie mallerte en la limbo ĉar mi ekpaŝis sur monologo tie, sed ni engaĝi vi denove en nur momento. Anita estas nula en tiu punkto en la historio, do la dum buklo finiĝas, kaj ni devas reveni malvera ĉar se ŝi atingis la tutan vojon al Ari la nula puntero tiam ne estis numero kiu ŝi serĉis en la listo. Ni povas purigi ĉi tro, sed ĉi tiu estas sufiĉe bona apliko tiam de traversal funkcio, oni trovos funkcio por ligitaj listo. Estas ankoraŭ lineara serĉo, sed ne estas tiel simpla kiel + + puntero aŭ + + an i variablon ĉar nun ni ne povas diveni kie ĉiu de ĉi tiuj nodoj estas en memoro. Ni devas laŭlitere sekvi la spuron de paderoj aŭ, pli specife, punteros, por preni de unu vertico al alia. 

Nun ni provu alian. Anita, ĉu vi volas veni cxi tien? Kial ni ne iru antaŭen kaj destini unu alia persono de la aŭdienco? Malloc-kio estas via nomo? >> Rebeka. Rebeka. Rebecca estis malloced de la publiko, kaj ŝi nun provizon la numeron 55. Kaj la golo en mano nun estas por Anita insertar Rebeka en la ligitaj listo tie en ĝia taŭga loko. Venu ĉi tien dum momento. Mi faris ion kiel ĉi tio. Mi faris nodon *. Kaj kio estas via nomo denove? Rebeka. >> Rebeka, okay. Rebecca gets malloc (sizeof (nodo)). Samkiel ni destinis aĵojn kiel studentoj kaj whatnot en la pasinteco, ni bezonas la grandeco de la nodo, tial nun Rebeka notas en kio? Rebecca havas du kampojn interne de ŝi, unu el kiuj estas 55. Ni faras kion, rebecca-> = 55. Sed tiam rebecca-> sekva estu-like nun, ŝia mano estas speco de kiu scias? Oni montras al iuj rubo valoron, do kial ne por bono mezuro ni almenaŭ fari tion por ke maldekstra mano estas nun ĉe lia flanko. Nun Anita, prenu ĝin de tie. Vi havas Rebeka estinte asignotaj. Iru antaŭen kaj trovi kie ni devus meti Rebeka. Bona, tre bona. Konsentite, bona, kaj nun ni bezonas vin por havigi iom da direkto, tiel vi atingis Ari. Lia maldekstra mano estas nula, sed Rebeka klare apartenas al la dekstra, tiel kiel ni devas ŝanĝi ĉi ligitaj listo por enmeti Rebecca en la taŭgan lokon? Se vi povus laŭvorte movi popola maldekstra manoj ĉirkaŭ drajvo, ni ripari la problemon tiamaniere. Konsentite, bona, kaj dume, Rebecca maldekstre estas nun apud ŝi. 

Tio estis tro facila. Ni provu atribuo-we're preskaŭ farita, 20. Konsentite, venu supren. 20 estis atribuitaj, do lasu min antaŭeniri kaj diru denove ĉi tie ni ĵus faris nodon * Saad. Ni havas malloc (sizeof (nodo)). Ni tiam fari same ĝusta sintakso kiel ni faris antaŭe por 20, kaj mi faros = NULL, kaj nun ĝi estas ĝis Anita insertar vin en la ligitaj listo, se vi povus ludi, ke ĝusta sama rolo. Ekzekuti. Konsentite, bona. Nun zorge pensu antaux vi komencas movi maldekstren manoj ĉirkaŭe. Vi kun tre atingis la plej mallerta rolon hodiaŭ. Kies mano devas esti movita unua? Okay, atendu, mi aŭdis iujn ne-aj jaroj. Se iuj homoj estus ĝentile ŝatas helpi solvi maloportuna situacio tie. Kies maldekstra mano estu ĝisdatigita unua eble? Yeah. [Studenta] Saad aj jaroj. Konsentite, Saad la, kial, kvankam? [Inaudible studento respondon] Bona, ĉar se ni movas-kio estas via nomo? >> Marshall. Marshall, se ni movas la manon unue malsupren al nula, nun ni laŭvorte orfoj kvar homoj en tiu listo cxar li estis la sola afero montrante Rajmondo kaj cxiu al la maldekstra, tiel ĝisdatigante ke puntero unua estis malbona. Ni malfari tion. Bona, kaj nun iru antaŭen kaj movi la taŭga maldekstra mano montrante Rajmondo. Ĉi sentas iom redunda. Nun ekzistas du personoj montrante Rajmondo, sed tio estas bone ĉar nun, kiel ajn ni ĝisdatigi la liston? Kio aliflanke devas movi? Bonega, nun ni havas perdis neniun memoro? Ne, tiel bona, vidu se ni ne povos ignori cxi tiun fojon pli. 

Mallocing lasta fojo, numero 5. Tuta vojo en dorso, venu malsupren. Ĝi estas tre ekscita. [Aplaŭdo] Kio estas via nomo? >> Ron. Ron, bone, vi malloced kiel numero 5. Ni ĵus ekzekutita kodo kiu estas preskaŭ identa al tiuj kun nur malsama nomo. Bonega. Nun, Anita, bonan sorton enmeto numero 5 en la listo nun. Nu, kaj? Bonega, do ĉi tiu estas vere la tria el la tri tuta kazoj. Ni unue havis iun je la fino, Rebeka. Ni tiam havis iun en la mezo. Nun ni havas iun je la komenco, kaj en ĉi tiu ekzemplo, ni nun devis ĝisdatigi Lucas por la unua fojo ĉar la unua ero en la listo nun devas atentigi en nova nodo, kiu, siavice, estas montrante nodo numero 9. 

Tio estis ege mallerta pruvo, mi certas, tiel grandan ĉirkaŭvojon de aplaŭdoj por tiuj infanoj, se vi povus. Bele farita. Tio estas ĉio. Vi povas konservi viajn pecojn de papero kiel malgranda memoro. Rezultas ke farante tion en kodo estas ne tute tiel simpla kiel simple movi manojn ĉirkaŭ kaj montrante punteros en malsamaj aĵoj. Sed rimarkas ke kiam temas tempo realigi ion kiel kunligita listo aŭ varianto de ĝi, se vi enfokusigi vere tiuj bazaj fundamentojn, la mordo-grandeco problemojn mi devas diveni, ĉu ĉi mano aŭ tiun manon, rimarkas ke kio estas alia maniero sufiĉe kompleksa programo povas, fakte, povas redukti al sufiĉe simpla konstruaĵo blokoj ŝatas tion. 

Ni prenu tion en pli kompleksaj direkto senmova. Ni nun havas la nocion de la ligitaj listo. Ni ankaŭ havas-danke al la sugesto reen tie-duoble ligitaj listo, kiu aspektas preskaŭ la sama, sed nun ni havas du punteros ene de la struct anstataŭ unu, kaj ni povus probable voki la punteros antaŭa kaj apud aŭ maldekstra aŭ dekstra, sed ni, fakte, bezonas du el ili. La kodo estus iom pli implikitaj. Anita estus devinta fari pli da laboro tie sur la scenejo. Sed ni povus certe apliki tian strukturon. En terminoj de rula tempo, tamen, kio estus la rula tempo por Anita de trovanta nombro n en ligitaj listo nun? Ankoraŭ granda a de n, do ĝi ne estas pli bona ol lineara serĉo. Ni ne povas fari duuma serĉo, kvankam, denove. Kial estis ke la kazo? Vi ne povas salti ĉirkaŭe. Eĉ kvankam ni evidente vidas ĉiuj homoj sur la scenejo, kaj Anita povus esti eyeballed ĝin kaj diris: "Jen estas la mezo de la listo," ŝi ne scius, ke se ŝi estus la komputila programo ĉar la sola afero devis fermi al la komenco de la scenaro estis Lucas, kiu estis la unua montrilo. Ŝi nepre devas sekvi tiujn ligojn, rakonti sian vojon ĝis ŝi trovis proksimume la mezo, kaj eĉ tiam, ŝi ne tuj scii kiam ŝi atingis la mezo krom se ĝi iras tuta vojo al la fino eltrovi kiom da ekzistas, tiam backtracks, kaj ke estus tro malmola se vi havis duoble ligitaj listo de ia. 

Solvi iujn problemojn hodiaŭ, sed enkondukante aliaj. Kio pri malsama datumstrukturo aro? Tio estas foto de la pletoj en Mather Domo, kaj en ĉi tiu kazo, ni havas datumstrukturo ni ankaŭ speco de jam parolas. Ni parolis pri stako en la kunteksto de memoro, kaj tio ia intence nomis ĉar pilo en la terminoj de memoro estas efektive datumstrukturo kiu havas pli kaj pli stuff manteloj sur ĝi. Sed la interesa afero pri pilo, kiel estas la kazo en realeco, estas ke ĝi estas speciala speco de datumstrukturo. Ĝi estas datumstrukturo per kiu la unua elemento en estas la lasta elemento eksteren. Se vi estas la unua pleto por esti metita sur la pilo, vi tuj estos bedaŭrinde la lasta pleto esti demetinta la pilo, kaj tio ne nepre estas bona afero. Male, vi povas pensi pri tio la revés, la lasta en la unua eksteren. 

Nun, ĉu iu scenaroj venas al la menso kie havi pilo datumstrukturo kie vi havas tiun propraĵo de la lasta en, unua el, estas fakte konvinkaj? Ĉu tio estas bona afero? Ĉu tio estas malbona? Estas definitive malbona se la pletoj ne estis ĉiuj identa kaj ili cxiuj estis speciala malsamaj koloroj aŭ whatnot, kaj la koloron vi volas estas la tuta vojo al la fundo. Kompreneble, vi ne povas atingi tiun sen granda peno. Vi devas komenci de la supro kaj labori vian vojon malsupren. Simile, kio se vi estis unu el tiuj fano infanoj kiuj atendas la tutan nokton provante atingi iPhone kaj regiono en loko kiel tiu? Ĉu ne estus bela se la Apple vendejo estis stako datumstrukturo? Yay? Ne? Estas nur bona por la popolo, kiu aperas en la lasta ebla minuto kaj tiam preni desxiritan la vico. Kaj fakte, la fakto ke mi estis tiom emas diri vosto Estas vere kohera kun kion ni nomas tian datumstrukturo, en realeco kie la ordo gravas, kaj vi volas ke la unua en esti la unua el se nur pro homa justeco. Ni ĝenerale nomas ke queue datumstrukturo. 

Ĝi rezultas krom ligitaj listoj, ni povas ekuzi tiujn samajn bazajn ideojn kaj komenci krei novan kaj diversaj specoj de solvoj al problemoj. Ekzemple, en la kazo de pilo, ni povus reprezenti stako uzante datumstrukturo kiel ĉi tiu, mi proponas. En ĉi tiu kazo, mi deklaris struct, kaj mi diris interne de tiu strukturo estas tabelo de nombroj kaj poste variablo nomas grandecon, kaj mi iras por voki ĉi tiun aĵon pilo. Nun, kial ĉi tiu vere funkcias? En la kazo de pilo, mi povus desegni ĉi efektive sur la ekrano tiel tablo. Jen mia pilo. Tiuj estas miaj ciferoj. Kaj ni desegni ilin kiel ĉi tio, tio, tiu, tio, tiu. Kaj tiam mi havas iujn aliajn datumojn membro tie, kiu estas nomata grandeco, do ĉi tiu estas grandeco, kaj ĉi tiu estas nombroj, kaj kolektive, la tuta iPad tie reprezentas unu pilo strukturo. Nun, implicite, grandeco supozeble alvenis al inicializado al 0, kaj kio estas ene de la tabelo de nombroj komence kiam mi unue atribui tabelo? Rubo. Kiu scias? Kaj ĝi ne vere gravas. Ne gravas se tiu estas 1, 2, 3, 4, 5, tute hazarde por malbona sorto stokitaj en mia strukturon ĉar tiel longe, kiel mi scias, ke la grandeco de la stako estas 0, tiam mi scias programmatically, ne rigardu iu el la eroj en la tabelo. Ne gravas kio estas tie. Ne rigardu ilin, kiel estus la implikaĵon de grandeco de 0. 

Sed supozu nun mi iras antaŭen kaj enmeti ion en la stako. Mi volas enmeti la numero 5, do mi metis numero 5 tie, kaj tiam kion mi metis ĉi tien? Nun mi fakte sufoki 1 por la grandeco, kaj nun la pilo estas de amplekso 1. Kio se mi iras antaŭen kaj enmeti la numeron, diru, 7 poste? Ĉi tiam gets ĝisdatigita al 2, kaj poste ni faros 9, kaj tiam ĉi gets ĝisdatigita al 3. Sed la interesa trajto nun de ĉi pilo estas ke Mi supozis forigi kion elemento se mi volas popo io ekstere de la pilo, por tiel diri? 9 estus la unua kiu iri. Kiel se la bildo ŝanĝi se mi volas popo ero ekstere la pilo, multe kiel pleto en Mather? Yeah. >> [Studenta] Ara grandeco al 2. Ekzakte, ĉiuj mi faras estas metita grandeco al 2, kaj kion mi faras kun la tabelo? Mi ne devas fari ion. Mi povus, nur por esti anal, metu 0 tie aŭ -1 aŭ ion por signifi ke tio ne estas legit valoro, sed ne gravas ĉar Mi povas gravuri ekster la tabelo mem kiel longe estas tiel, ke mi konas nur rigardi la du unuaj elementoj en ĉi tiu tabelo. Nun, se mi iros kaj aldoni la numero 8 al ĉi tabelo, kiel faras la bildo ŝanĝas poste? Ĉi igas 8, kaj ĉi tiu iĝas 3. Mi tranĉis kelkaj anguloj tie. Nun ni havas 5, 7, 8, kaj ni reen al grandecon de 3. Ĉi tiu estas bela simpla apliki, sed kiam ni tuj bedaŭras ĉi dezajno decido? Kiam do aferojn komencos iri tre tre malbone? Yeah. [Inaudible studento respondon] Kiam vi volas iri reen kaj akiri la unuan elementon vi enmetita tien 

Ĝi rezultas tie kvankam pilo estas tabelo sub la kapuĉo, tiuj datumstrukturoj ni komencis paroli pri ili ankaŭ ĝenerale konata kiel abstrakta datumstrukturoj per kiom ili estas implementado estas tute krom la punkto. Al datumstrukturo kiel stako supozas aldoni subtenon operaciojn kiel puŝo, kiu pelas pleton sur la pilo, kaj popo, kiu forprenas ero de la pilo, kaj tio estas ĝi. Se vi estus por elŝuti de iu alia kodo, kiuj jam implementado tion nomis pilo, tiu persono estus skribinta nur du funkcioj por vi, puŝi kaj popo, kies sola celo en la vivo estus fari precize tion. Vi aŭ li aŭ ŝi kiu implementado tiu programo estus estinta tute la decidi kiel apliki la semantiko de puŝas kaj krevi sub la kapuĉo aŭ la funkcioj de puŝas kaj krevi. Kaj mi faris iom miopa decidon ĉi tie per apliko mia pilo kun tiu simpla datumstrukturo kial? Kiam tion faras datumstrukturo ripozon? Kie estas la limo do mi devas reveni eraron kiam la uzanto vokas puŝo, ekzemple? [Studenta] Se ne estas pli da spaco. Ĝuste, se estas neniu pli spaco, se mi superis kapablo, kiu estas la tuta kaskedoj ĉar ĝi sugestas, ke estas ia tutmonda konstanto. Nu, tiam mi simple tuj devos diri: "Pardonu, mi ne povas puŝi alia valoro sur la pilo, "multe kiel en Mather. 

En iu momento, ili tuj frapis la supera parto de tiu iom kabineto. Ne pli spaco aŭ kapablo en la pilo, en kiu punkto ekzistas ia eraro. Ili devas meti la elementon en alia loko, la pleto aliloke, aŭ nenie ajn. Nun, kun vosto, ni povus efektivigi ĝin iom malsame. Al vosto estas iom malsama en kiu sub la kapuĉo, ĝi povas esti realigita tiel tablo, sed kial, ĉi-kaze, mi proponas havi ankaŭ kapon elemento reprezentas la kapo de la listo, la fronto de la listo, la unua persono en linio je la Apple vendejo, krom grandeco? Kial mi bezonas plian pecon da datumoj tie? Pensu reen al kio nombroj estas se mi desegnis ĝin jene. Supozi ĉi estas nun queue anstataŭ pilo, la diferenco-samkiel la Apple vendejo-vosto estas justa. La unua persono en linio je la komenco de la listo, numero 5 en ĉi tiu kazo, li aŭ ŝi tuj estos enlasitaj sur la vendejo unua. Ni faras tion. Supozu ke tiu estas la stato de mia vosto en ĉi tiu momento en tempo, kaj nun la Apple vendejo malfermas kaj la unua persono, numero 5, estas direktita al la vendejo. Kiel mi ŝanĝu la bildon nun ke mi de-vosto la unua persono ĉe la fronto de la linio? Kio estas tio? >> [Studenta] Ŝanĝi la vico. Ŝanĝi la kapon tiel, 5 malaperas. Fakte, ĝi estas kvazaŭ-kiel plej bone fari tion? Fakte, ĝi estas kvazaŭ tiu ulo malaperas. Kion numero 7 fari en reala vendejo? Ili prenus grandan paŝon antaŭen. 

Sed kion ni venis por estimi kiam temas pri tabeloj kaj movante aĵoj ĉirkaŭ? Tio estas speco de malŝparo de via tempo, ĉu ne? Kial vi devas esti tiel anal kiel havi la unua persono je la komenco de la linio je fizike la komenco de la bloko de memoro? Tio estas tute nenecesa. Kial? Kion mi povus simple memori anstataŭe? >> [Inaudible studento respondon] Precize, mi povus simple memori kun ĉi pliaj datumoj membro kapo ke nun la estro de la listo ne plu estas 0, kio estis antaŭ momento. Nun ĝi estas vere la nombro 1. Tiamaniere, mi alvenas malpeza optimumigo. Nur ĉar mi de-vosto iu de linio en la komenco de la linio je la Apple vendejo ne signifas ke ĉiuj devas ŝanĝi, kiu memoros estas lineara operacio. Mi povas anstataŭ pasi konstanta tempo nur kaj atingi tiam multe pli rapida respondo. Sed la prezo Mi pagas estas kion gajni ke plia agado kaj ne devi ŝanĝi ĉiuj? Yeah. >> [Inaudible studento respondon] Povas aldoni pli da homoj, nu, tiu problemo estas perpendikulara al la fakto ke ni ne ŝanĝante homoj ĉirkaŭe. Estas ankoraŭ tabelo, do ĉu ni ŝanĝi ĉiuj aŭ ne- ho, mi vidas tion, kion vi volas diri, okay. Efektive, mi konsentas kun kion vi diris en tiu estas preskaŭ kvazaŭ ni nun neniam tuj uzos la komenco de ĉi tiu tabelo plu ĉar se mi forpelus 5, tiam mi forigi 7. Sed mi nur metis la homo al la dekstra. 

Sentas mi malŝparas spacon, kaj eventuale mia vosto malintegras en nenion, do ni povus simple devas homoj wraparound, kaj ni povus pensi pri tiu tabelo vere kiel ia cirkla strukturo, sed ni uzas kion operatoro en C por fari tiajn wraparound? [Inaudible studento respondon] >> La module operatoro. Estus iom ĝena pensi tra how do you do la wraparound, sed ni povus fari gxin, kaj ni povus komenci meti homojn je kioma kutimis esti la fronto de la linio, sed ni nur memoras kun tiu kapo variablo kiu estas la reala kapo de la linio estas. Kio se, anstataŭe, nia celo finfine, tamen, estis serĉi nombroj, kiel ni faris ĉi tie sur la scenejo kun Anita, sed ni vere volas la plej bonan el cxiuj tiuj mondoj? Ni volas pli sofisticación ol tabelo permesas ĉar ni deziras la kapablon dinamike kreski la datumstrukturo. Sed ni ne volas havi recurrir al iu kiun ni atentigis en la unua prelego ne estis optimuma algoritmo, tiu de lineara serĉo. Rezultas, ke vi povas, fakte, atingi aŭ almenaŭ proksime al konstanta tempo, per kiu iu kiel Anita, se ŝi configures ŝi datumstrukturo ne esti ligillisto, ne esti pilo, ne esti vosto, povus, fakte, supreniru kun datumstrukturo kiu permesas sxin rigardi aferojn, eĉ vortoj, ne nur numeroj, en kio ni vokos konstanta tempo. 

Kaj fakte, rigardante antaŭen, unu el la psets en ĉi klaso estas preskaŭ ĉiam realigo de literumilo, per kiu ni donu al vi denove iuj 150.000 anglaj vortoj kaj la celo estas montru tiujn en memoron kaj rapide povos respondi al demandoj de la formo Estas ĉi tiu vorto ĝuste literumita? Kaj ĝi vere suck se vi havis ankaŭ persisti tra ĉiuj 150.000 vortojn por respondi. Sed, fakte, ni vidos, ke ni povas fari ĝin en tre, tre rapida tempo. Kaj tuj engaĝi implementando iu nomita hash tablo, kaj kvankam unuavide tiu afero nomata hash tablo tuj ni atingi tiujn super rapida respondo tempoj, ĝi rezultas ke tie estas fakte problemo. Kiam temas tempo realigi tiun aferon nomita-denove, mi faras ĝin denove. Mi estas la sola ĉi tie. Kiam temas tempon por efektivigi tion nomas hash tablo, ni tuj devos preni decidon. Kiel granda devas tion efektive estus? Kaj kiam ni komencos enmeto nombroj en ĉi hash tablo, kiel ni por stoki ilin en tia maniero ke ni povas atingi ilin el tiel rapide kiel ni ricevis ilin en? Sed ni vidos antaux longe ke tiu demando pri kiam ĉies naskiĝtago estas en la klaso estos sufiĉe germane. Rezultas, ke en ĉi tiu ĉambro, ni havas kelkajn cent homoj, do la probablo ke du el ni havas la saman naskiĝtagon estas probable sufiĉe alta. Kio se estis nur 40 el ni en tiu ĉambro? Kio estas la probablo de du personoj havanta la saman naskiĝtagon? [Studentoj] Pli ol 50%. Yeah, super 50%. Fakte, mi eĉ kunportis abako. Ĝi rezultas-kaj ĉi tiu estas vere nur sneak antaŭmontro- se estas nur 58 el ni en tiu ĉambro, la probablo de 2 el ni havante la saman naskiĝtagon estas ege alta, preskaŭ 100%, kaj tio tuj kaŭzos tuta amaso de vundita por ni merkredon. 

Kun kiu diris, ni adjourn tie. Ni vidos vin merkredon. [Aplaŭdo] [CS50.TV]