Parolanto 1: Bone, do ĉi estas CS50 Jen la fino de semajno kvin. Kaj memoras ke lastfoje ni komenciĝis rigardante la amatoro datumoj strukturoj kiuj komencis solvi problemoj, kiuj komencis enkonduki novaj problemoj, sed la ŝlosilo al tiu estis la speco de threading ke ni komencis fari de nodo al nodo. Do tiu kompreneble estas oni unuope ligita listo. Kaj per unuope ligitaj, Mi signifas restas nur unu fadeno inter ĉiu el tiuj nodoj. Rezultas vi povas fari amatoro aĵoj kiel duoble ligitaj listoj whereby vi havas sagon irante en ambaŭ direktoj, kiuj povas helpi kun iuj efikecojn. Sed tiu solvis la problemon? Kio problemo ja ĉi solvi? Kial ni zorgas lunde? Kial, en teorio, ni zorgas lunde? Kion ĝi faras? 

Publiko: Ni povas dinamike regrandigi ĝin. 

Parolanto 1: Bone, do ni povas dinamike regrandigi ĝin. Bonege vi ambaŭ. Do vi povas dinamike regrandigi ĉi datumstrukturo, dum tabelo, revokon, vi devas scii priori kiom spaco vi volas kaj se vi bezonas iom pli spaco, vi estas speco de el sorton. Vi devas krei tutan novan tabelo. Vi devas movi ĉiuj viaj datumoj de unu al la alia, eventuale liberigi la malnova tabelo se vi povas, kaj poste plu. Kiuj nur sentas tre multekosta kaj tre malkompetenta, kaj ja povas esti. Sed tio ne estas tute bona. Ni pagas prezon, kio estis unu de la pli evidentaj prezoj ni pagi uzante ligitaj listo? 

Publiko: Ni devas uzi duobla spaco por ĉiu. Parolanto 1: Jes, do ni bezonas almenaŭ duoble da spaco. Fakte, mi rimarkis tiun foton la eĉ iom misgvida, ĉar sur CS50 IDE en multaj modernaj komputiloj, montrilo aŭ adreson ne estas fakte kvar bajtoj. Ĝi estas tre ofte tiuj tagoj ok bajtoj, kiuj signifas la fundo plej rektangulojn tie en realo estas ia duoble granda kiel kion mi desegnis, kio signifas vi uzas trioble da spaco kiel ni havu alie. Nun samtempe, ni estas ankoraŭ parolas bitokoj, ĉu ne? Ni ne nepre parolanta megabajtoj aŭ gigabajtoj, krom se tiuj datumstrukturoj akiri grandan. 

Kaj do hodiaŭ ni komencas konsideri kiel ni povus esplori datumoj pli efike se en Fakte la datumoj akiras pli grandan. Sed ni provu canonicalize la operacioj unua ke vi povas fari en ĉi tiuj specojn de datumstrukturoj. Do iu kiel ligitaj lerta ĝenerale subtenas operacioj ŝatas forigi, enmeti kaj serĉu. Kaj kion mi volas diri per tio? Tio simple signifas ke kutime, se personoj uzas ligillisto, ili aŭ iu alia estas implementado funkcioj kiel delete, insert, kaj serĉo, tiel vi povas efektive fari ion utila kun la datumstrukturo. Do ni prenu rapidan rigardon kiel ni povus efektivigi iu kodo por ligillisto jene. 

Do tiu estas nur iuj C kodo, eĉ kompletan programon ke mi vere rapide ekfrapis. Ĝi ne estas linio en la dissendo kodo, ĉar ĝi ne reale kuri. Sed rimarki Mi havas precize kun komenton diris, dot dot dot, ekzistas io tie, dot dot dot, ion tie. Kaj ni simple rigardi kion la sukaj partoj estas. Do sur linio tri, memoras ke tiu estas nun Ni proponis deklari nodo lasta tempo, unu el tiuj rektangulaj objektoj. Ĝi havas int ke ni vokos N, sed ni povus nomi ion, kaj tiam struct nodo stelo nomas proksima. Kaj nur por esti klara, ke dua linio, sur linio ses, kio estas tio? Kio ĝi faras por ni? Ĉar ĝi certe aspektas pli kamufla ol nia kutima variabloj. 

Spektantaro: Ĝi igas ĝin moviĝi super unu. 

Parolanto 1: Ĝi igas ĝin moviĝi super unu. Kaj por esti pli preciza, ĝi stokos la adreson de la nodo kiu signifis esti semantike apud ĝi, ĉu ne? Do ne tuj nepre movi ion. Ĝi simple tuj stoki valoron, kiu estas tuj estos la adreso de iu alia nodo, kaj tial ni diris struct nodo stelo, la stelo signifanta montrilo aŭ adreson. Bone, do nun se vi supozas ke ni devos tiu N havebla al ni, kaj ni supozas ke iu alia havas insertita tutan faskon de entjeroj en ligillisto. Kaj ke ligillisto estas almontras iu punkto ŝanĝiĝema nomita listo jen pasis en tie kiel parametro, kiel mi iros sur linio 14 efektivigado serĉo? En aliaj vortoj, se mi efektivigado funkcio kies celo en la vivo estas preni int kaj poste la komencante de ligillisto, ke estas puntero al la ligillisto. Kiel unua, kiu mi pensas Davido Estis nia volontulo lunde, li indik la tutan ligillisto, ĝi estas kvazaŭ ni pasante David en kiel nia argumento tie. Kiel ni iras pri petolanta tiu listo? Nu, Ĝi rezultas ke kvankam punteros estas relative nova nun por ni, Ni povas fari ĉi relative rekte?. 

Mi tuj iros antaŭen kaj deklari portempa variablo kiu per konvencio estas ĝuste tuj esti nomata montrilo, aŭ PTR, sed vi povus voki ĝi ajn vi volas. Kaj mi tuj pravalorizi ĝin al la komenco de la listo. Do vi povas ia pensas pri ĉi kiel mi la majstro la alia tago, ia montrante iun inter niaj homoj kiel volontuloj. Do mi estas portempa variablo tio nur montrante la saman aferon ke nia hazarde nomis volontulo David ankaŭ atentiganta. Nun dum puntero estas ne nula, ĉar revoko ke nula estas iuj specialaj sentinelo valoro la demarca la fino de la listo, do dum mi ne montrante la tero kiel nia lasta volontulo estis, ni iru antaŭen kaj fari la sekvan. Se pointer-- kaj nun mi specon de volas fari kion ni faris kun la studento structure-- se puntero punkto apud equals-- prefere, se puntero punkto N egalas egalas la variablo n, la argumento ke tio estis pasita en, tiam mi volas antaŭeniri kaj diri reveni vera. Mi trovis la nombro N ene de unu el la nodoj de mia ligillisto. Sed la punkto ne plu laboras en tiu kunteksto, ĉar montrilo, PTR, estas ja puntero, adreson, ni efektive povas mirinde uzi fine peco de sintakso tian fabrikas intuicia senco kaj reale uzi sago tie, kio signifas iri de tiu adreso al la entjera tie. Do estas tre similaj en spiriton al la skalara operatoro, sed ĉar montrilon ne montrilo kaj ne reala struct mem, Ni simple uzu la sago. 

Do se la nuna nodo ke Mi, la provizora variablo, am indik ne N, kion mi volas fari? Nu, kun mia homaj volontuloj ke ni havis tie la alia tago, se mia unua homa ne estas la unu mi volas, kaj eble la dua homa estas ne la unu mi volas, kaj la tria, mi bezonas konservi fizike movante. Kiel kiel mi paŝi tra listo? Kiam ni havis tabelo, vi nur faris kiel mi plie kaj plie. Sed en ĉi tiu kazo, sufiĉas fari puntero, Akiras, montrilo, sekva. En aliaj vortoj, la sekvanta kampo estas kiel ĉiuj de la maldekstra mano ke nia homa volontuloj lunde estis uzante noti al iu alia nodo. Tiuj estas iliaj proksimaj najbaroj. 

Do se mi volas paŝi tra tiu listo, Mi ne povas simple fari mi plie plus plu, Mi anstataŭe devas diri Mi, montrilo, tuj egali ajn la sekva kampo estas, la sekva kampo, la sekva kampo estas, sekvante ĉiuj tiuj postlasitaj manoj ke ni havis sur scenejo indikanta al iuj sekvaj valoroj. Kaj se mi akiras tra ke tutaj ripeto, kaj fine, mi batis nula ne havanta trovis N tamen, mi simple reveni falsaj. Do denove, cxiuj ni faras ĉi tie, kiel por la bildo antaŭ momento, komencas per fingromontrante la komencante de la listo supozeble. Kaj tiam mi kontrolu, estas la valoro Mi serĉas egalas naŭ? Se jes, mi revenas vera kaj mi estas farita. Se ne, mi ĝisdatigos mian manon, AKA montrilo, atentigi ĉe la venonta sago situo, kaj tiam la sekva sago situo, kaj la sekva. Mi simple piediranta tra ĉi tabelo. 

Do denove, al kiu gravas? Kiel kio estas tiu ingredienco por? Nu, memoru ke ni enkondukis la nocio de pilo, kiu estas abstrakta datumtipo mezuro estas ne C afero, ĝi ne estas CS50 afero, ĝi estas abstrakta ideo, tiu ideo de stakiganta aferoj unu sur alian kiuj povas esti efektivigitaj en gxibo de malsamaj manieroj. Kaj unu vojo ni proponis estis kun tabelo, aŭ kun ligillisto. Kaj ĝi rezultas ke kanone, a pilo subtenas almenaŭ du operacioj. Kaj la zumado vortoj estas puŝo, por puŝi ion sur la pilo, kiel nova pleto en la manĝejo, aŭ popo, kio signifas forigi la plejsupra pleto de la stako en la manĝ halon, kaj tiam eble iuj aliaj operacioj ankaŭ. Do kiel povus ni difini la strukturon ke ni nun nomante pilo? 

Nu, ni havas ĉiujn la kondiĉo sintakso ĉe nia dispono en C. Mi diras, Donu al mi tipon de difino struct ene de pilo, Mi tuj diros estas tabelo, de tuta aro da nombroj kaj tiam grandeco. Do alivorte, se mi volas implementar ĉi en kodo, permesu al mi iri kaj nur speco de desegni kion tiu diras. Do tiu diras, donu al mi strukturo kiu estas alvenis tabelo, kaj mi ne scias kion kapablo estas, ĝi estas ŝajne iu konstanto ke mi havas difinitaj aliloke, kaj tio estas bone. Sed certe nun nur unu, du, tri, kvar, kvin. Do kapablo estas 5. Tiu elemento ene de mia strukturo estos nomitaj nombroj. Kaj tiam mi bezonas unu alia variablo ŝajne nomata grandeco kiu komence Mi tuj al kondiĉas inicializa al nulo. Se nenio estas en la pilo, esas nulo, kaj ĝi estas rubo valorojn en nombroj. Mi havas neniun ideon kio estas tie interne ĵus ankoraŭ. 

Do se mi volas puŝi ion sur la pilo, supozas ke mi nomas la funkcion puŝo, kaj Mi diras puŝi 50, kiel la numero 50, kie vi proponas Mi tiros lin en tiu tabelo? Ekzistas kvin malsamaj eblaj respondoj. Kie vi volas puŝi la numero 50? Se la celo tie, denove, invitu funkcio puŝo, pasas en argumento de 50, kie mi metis ĝin? Kvin possible-- 20% ŝanco de konjektanta korekte. Jes? 

Publiko: ekstremdekstro. 

Parolanto 1: ekstremdekstro. Estas nun 25% ŝanco de konjektanta korekte. Por ke estus vere bone. Por konvencio, mi diru kun tabelo, ni ĝenerale komenci ĉe la maldekstra, sed ni certe povus komencu ĉe la dekstra. Do ruiniganto tie estus mi probable tuj tiros gxin maldekstre, Ĝuste kiel en normala tabelo kie Mi komencas irita maldekstre dekstren. Sed se vi povas flip la aritmetiko, fajna. Ĝi estas nur ne convencionales. OK, mi bezonas fari unu pli ŝanĝo tamen. Nun ke mi puŝis ion sur la pilo, kio estas poste? 

Bone, mi devas pliigo la grandeco. Do lasu min antaŭeniri kaj justa ĝisdatigu tiun, kiu estis nulo. Kaj anstataŭe nun, mi tuj meti en la valoro unu. Kaj nun supozu mi puŝas alian numeron sur la pilo, kiel 51. Nu, mi devas fari unu pli ŝanĝo, kiu estas ĝis la grando du. Kaj tiam mi supozas puŝi pli numeron sur la pilo kiel 61, nun mi bezonas ĝisdatigi la grandeco pli tempo, kaj akiri la valoron 3 kiel la grandeco. Kaj nun supozu mi nomas popo. Nun pop, per konvencio, ne prenas argumenton. Kun pilo, la tuta punkto de la pleto metaforo estas ke vi ne havas bontrovo iri atingi tiun pleton, Ĉiuj vi povas fari estas pop la plejsupra unu el la stako, nur ĉar. Tion ĉi datumstrukturo faras. 

Do per tiu logiko se mi diru popmuziko, kion elspezas? Do 61. Do kio vere estas la komputilo faros en memoro? Kion mia kodo devas fari? Kion vi proponas ni ŝanĝas sur la ekrano? Kio devus ŝanĝi? Pardonon? Do ni forigi 61. Do mi sendube povas tion fari. Kaj mi povas forigi 61. Kaj tiam kion aliaj ŝanĝo bezonas okazi? Grandeco probable devas reiri al du. Kaj do tio estas bone. Sed atendu momenton, grandeco antaŭ momento estis tri. Ni nur faru rapidan prudento ĉeko. Kiel ni scias ke ni volis forigi 61? Ĉar ni krevanta. Kaj tial mi havas tiun duan propraĵo grandeco. 

Atendu minuton, mi estas pensante reen al semajno du kiam ni komencis paroli pri arrays, kie tiu estis loko nulo, tiu estis loko unu, tiu estis loko du, tio estas loko tri, kvar, ĝi aspektas kiel la interrilato inter grandeco kaj la elemento kiu mi volas forigi el la tabelo aperas nur esti kio? Grandeco minus unu. Kaj do tiel estas kiel kiel homoj ni scias 61 venas unue. Kiel fartas la komputilo tuj scias? Kiam via kodo, kie vi probable volas fari grandeco minus unu, tial tri minus unu estas du, kaj ke Do oni volas forigi 61. Kaj tiam ni povas ja ĝisdatigi la grandeco por ke grandeco nun iras de tri al nur du. Kaj ĝuste por esti pedanta, mi tuj proponi ke mi faris, ĉu ne? Vi proponis intuicie ĝuste mi devus forigi 61. Sed ne mi specon de ia liveris de 61? Mi efektive forgesis ke fakte ekzistas. Kaj pensas reen al PSET4, se vi legis la artikolo pri jura, la PDF ke ni devis vin uloj legi, aŭ vi legos tiun semajnon por PSET4. Memoru ke ĉi tiu estas reale germane al la tuta ideo de komputilo jura. Kio komputilo ĝenerale faras estas ĝi simple forgesas kie io estas, sed ne eniros kaj kiel provu skrapi ĝin aŭ override tiuj bitoj kun nuloj kaj aŭ alian hazarda padrono krom se vi mem faras tiel intence. Do via intuicio estis Bone, ni forigi 61. Sed en realo, ni ne devas tedi. Ni nur bezonas forgesu ke ĝi estas tie ŝanĝante nia grandeco. 

Nun estas problemo kun tiu pilo. Se mi tenas puŝante aferoj sur la pilo, kio estas evidente okazos en nur kelkaj momentoj tempo? Ni tuj kuri el spaco. Kaj kion ni faru? Ni speco de ŝraŭbita. Tiu efektivigo ne lasas ni regrandigi la tabelo, ĉar uzante tiu sintakso, se vi pensas reen al semajno du, iam vi deklaris la grandeco de tabelo, ni ne vidis mekanismo ankoraŭ kie vi povas ŝanĝi la grandecon de la tabelo. Kaj efektive C ne havas tiun karakterizaĵon. Se vi diras al mi kvin Nths, nomu ilin nombroj, jen ĉio vi tuj ricevos. Do ni faru nun kiel de lundo, havas la kapablo esprimi solvon tamen, ni devas nur tweak la difino de nia stako por ne esti iu malmola-kodita tabelo, sed nur por stoki adreson. 

Nun kial estas tio? Nun ni nur devas esti komforta kun la fakto ke kiam mia programo kuras, Mi supozeble tuj devas demandi la homaj, kiom da ciferoj vi volas konservi? Do la enigo devas veni de ie. Sed iam mi scias ke nombro, tiam mi povas nur uzu kio funkcii doni mi eron de memoro? Mi povas uzi malloc. Kaj mi povas diri ajnan numeron de bajtoj mi volas reveni por tiuj Nths. Kaj ĉiuj mi devi stoki en la nombroj ŝanĝiĝema tie ene de ĉi struct devus esti kio? Kio reale iras en la nombroj en tiu scenaro? Yeah, montrilo al la unua bitoko de tiu bloko de memoro, aŭ pli specife, la adreso de la unua el tiuj bajtoj. Ne gravas se ĝi estas unu bajto aŭ miliardoj bajtoj, Mi nur devas zorgi pri la unua. Pro kio malloc garantiojn kaj mia mastruma sistemo garantiojn, estas ke la eron de memoro akiri, ĝi tuj estu apudaj. Tie ne iras esti breĉoj. Do se mi petis 50 bitokoj aŭ 1000 bitokoj, ili cxiuj iras al esti malantaŭo al malantaŭo al dorso. Kaj tiel longe kiel mi memoras kiom granda, kiom multe mi petis, mi nur bezonas scii Estas la unua tia adreso. 

Do nun ni havas la kapablecon en kodo. Kvankam, ĝi estas tuj prenos nin pli tempon skribi ĉi supre, ni nun povis reallocate ke memoron per nur stokante malsaman adreson tie se ni volas pli grandan aŭ eĉ pli malgrandan eron de memoro. Do jen al komerco ekstere. Nun ni akiras dinamismo. Ni ankoraŭ havas contiguousness Mi asertante. Ĉar malloc donos nin apudan eron de memoro. Sed ĉi tiu tuj estos doloro en la kolo por ni, la programisto, efektive programi supren. Estas nur pli laboro. Ni bezonas kodo parenca al kio mi estis batante eksteren nur antaŭ momento. Tre doable, sed aldonas kompleksecon. Kaj tiel ellaboranto tempo, programisto tempo estas alia rimedo ke ni eble bezonas por elspezi iun tempon akiri novajn funkciojn. Kaj tiam kompreneble estas atendovico. Ni ne iros en tiun en multe da detalo. Sed ĝi estas tre simila en spirito. Mi povus praktikigi atendovico, kaj lia responda operacioj, enqueue aŭ dequeue, kiel aldoni aŭ forigi, ĝi estas nur amatoro maniero diri ĝin, enqueue aŭ dequeue, jene. Mi povas nur doni min struct ke denove havas nombro de tabelo, ke denove havas grandecon, sed kial mi nun bezonas konservi trako de la fronto de atendovico? Mi ne bezonas scii la fronto de mia stako. Nu, se mi denove por queue-- ni nur malfacile programi ĝin havante kiel kvin entjeroj tien potenciale. Do tiu estas nulo, unu, du, tri, kvar. Ĉi tuj estos nomitaj nombroj denove. Kaj tiu estos nomata grandeco. 

Kial estas ne sufiĉa havi nur grandecon? Nu, ni puŝi tiujn samajn numerojn sur. Do mi pushed-- mi enqueued, aŭ puŝis. Nun mi enqueue 50, kaj poste 51, kaj tiam 61, kaj dot dot dot. Do jen enqueue. Mi enqueued 50, tiam 51, do 61. Kaj kiu aspektas identa al pilo tiel longe, krom mi bezonas fari unu ŝanĝo. Mi bezonas ĝisdatigi ĉi tiu grandeco, do mi iros de nulo al unu al du al tri nun. Kiel mi dequeue? Kio okazas kun dequeue? Kiu devus elspezi tiun liston unua se ĝi estas la linio je la Apple Store? Do 50. Do ĝi estas speco de trickier tiu tempo. Dum lasta tempo ĝi estis ekstra facile simple fari grandeco minus unu, Mi alvenas al la finon de mia tabelo efike kie la numeroj estas, ĝi eltiras 61. Sed mi ne volas forigi 61. Mi volas preni 50, kiu estis tie je 5:00 atm laŭliniigi por la nova iPhone aŭ whatnot. Kaj tiel seniĝi de 50, mi povas ne nur faru tion, ĉu ne? Mi povas transiri el 50. Sed ni ĵus diris nin ne devas esti tiel anal kiel skrapi eksteren aŭ kaŝi la datumojn. Ni povas simple forgesos kie ĝi estas. 

Sed se mi ŝanĝas mian grandecon nun al du, estas tiu sufiĉa informo scii kio okazas en mia vosto? Ne vere. Kiel mia esas du, sed tio rilatas al la atendovico komenci, precipe se mi ankoraŭ havas tiujn samajn numerojn en memoro. 50, 51, 61. Do mi devas memori nun kie la fronto estas. Kaj tiel kiel mi proponis supren tie, ni ĵus nomis Na fronto, kies komencaj valoro devus esti kio? Nulo, nur la komenco de la listo. Sed nun krom decrementing la grandeco, ni ĵus pliigo la fronto. Nun jen alia problemo. Do iam mi plu iri. Supozi ĉi estas la nombro de kiel 121, 124, kaj tiam, Dammit, Mi estas el spaco. Sed atendu momenton, mi ne estas. Do je ĉi tiu punkto en la rakonto, supozas ke la grandeco estas unu, du, tri, kvar, do supozu ke la grandeco estas kvar, la fronto estas unu, do 51 estas ĉe la fronto. Mi volas meti alian numeron tie, sed, Dammit, mi estos for de spaco. Sed mi ne vere, rajto? Kie mi povus meti iun aldona valoro, kiel 171? Jes, mi povis nur speco de reiri tien, ĉu ne? Kaj tiam transiri el la 50, aŭ simple anstataŭigi ĝin per 171. Kaj se vi scivolas kial niaj nombroj akiris tiom hazarda, tiuj estas kutime prenita komputilo scienco kursojn en Harvard post CS50. Sed tio estis bona optimumigo, ĉar nun mi ne malŝparas spacon. Mi ankoraŭ devas memori kiom granda afero estas entute. Estas kvin entute. Ĉar mi ne volas komenci superskribi 51. Do nun mi restas ekstere de spaco, do la saman problemon antaŭe. Sed vi povas vidi kiel nun en via kodo, vi probable devas skribi iom pli komplekseco fari ke okazas. Kaj fakte, kion operatoro en C probable lasas vi magie fari ĉi la circularidad? Yeah la module operatoro, la procentoj signo. Do kio estas speco de cool pri atendovico, eĉ se ni plenumas desegnante tabeloj kiel tiuj kiel rektoj, se vi ia pensas pri tio kiel kurbigante ĉirkaŭe kiel cirklo, tiam nur intuicie gxi ia laboras mense Mi pensas iom pli pure. Vi ankoraŭ devas apliki ke mensa modelo en kodo. Do ne estas tiel malfacila, finfine, al implementar, sed ni ankoraŭ perdi la size-- prefere, la kapablo regrandigi, krom se ni faras tion. 

Ni devas forigi la tabelo, ni anstataŭigi ĝin per sola puntero, kaj tiam ie en mia kodo mi devas alvokon kio funkcii por fakte krei la tabelo nomita nombroj? Malloc, aŭ iu simila funkcio, ĝuste. Demandojn sur stakoj aŭ vostoj. Yeah? Bona demando. Kio module estus vi uzas ĉi tie. Do ĝenerale, kiam oni uzas mod, vi farus kun la grandeco de la tutaj datumstrukturo. Do ion kiel kvin aŭ kapablo, se ĝi estas konstanta, probable implikitaj. Sed ĝuste faras module kvin probable ne suficxus, ĉar ni bezonas scii ĉu ni envolver ĉirkaŭe ĉi tie aŭ ĉi tie aŭ tie. Do vi probable ankaŭ tuj volas engaĝi la grandeco de la afero, aŭ la fronto variablo tiel. Do estas nur tiu relative simpla aritmetiko esprimo, sed module estus la ŝlosilo ingredienco. 

Tiel mallonga filmo se vi volas. Kuraĝigo kiu iuj uloj de alia universitato kunmetis ke ni adaptitaj por ĉi tiu diskuto. Ĝi implikas Jack lernas la faktoj pri atendovicoj kaj statistikojn. 

FILMO: Iam, ekzistis ulo kiu nomiĝas Jack. Kiam ĝi venis al amikiĝi, Jack ne havas povoscion. Do Joĉjo iris paroli kun la plej populara ulo li sciis. Li iris al Lou kaj demandis: Kion mi faru? Lou vidis ke lia amiko Estis vere premata. Nu, li komencis, ĵus rigardu, kiel vi estas vestita. Ĉu vi ne havas ajnan vestoj kun malsama rigardo? Jes, diris Joĉjo. Mi certas fari. Venu al mia domo kaj Mi montros ilin al vi. Do ili iris al Jack. Kaj Jack montris Lou la skatolo kie li observis cxiujn liajn ĉemizojn, kaj lia pantalono, kaj lia ŝtrumpetoj. Lou diris, mi vidas ke vi havas ĉiujn viajn vestojn en amaso. Kial ne vi portas iuj aliaj unufoje en kelktempe? 

Joĉjo diris, bone, kiam mi forigi vestojn kaj ŝtrumpetoj, Mi lavos ilin kaj metis ilin en la skatolon. Tiam venas la sekva mateno, kaj supre mi hop. Mi iras al la skatolo kaj akiri miaj vestoj de la supro. Lou rapide komprenis la problemo kun Jack. Li tenis vestojn, KD-a, kaj libroj en la stako. Kiam li atingis por io por legi aŭ surhavi, li elektus la supro libro aŭ subvestoj. Kiam do li faris, li metus lin rekte reen. Reen ĝi irus, sur supro de la stako. Mi konas la solvon, diris triumfa Loud. Vi devas lerni ekuzi atendovico. Lou prenis Jack vestojn kaj pendigis ilin en la ŝranko. Kaj kiam li malplenigis la skatolon, li simple forĵetis ĝin. 

Tiam li diris, nun Joĉjo, fine de la tago, meti viajn vestojn en la maldekstra kiam vi metis ilin. Tiam morgaŭ matene kiam vi vidi la sunlumon atingi viajn vestojn dekstre, de la fino de la linio. Ĉu vi ne vidas? diris Lou. Estos tiel bela. Vi surhavas ĉiu iam antaŭ vi surhavas ion dufoje. Kaj kun ĉio en atendovicoj en sia ŝranko kaj breto, Jack komencis senti tute certa pri si. Ĉiu danke al Lou kaj lia mirinda atendovico. Parolanto 1: Bone, estas adorable. Do kio estis vere iranta sur sub la kapuĉo nun? Ke ni havas punteros, ke ni havas malloc, ke ni havas la eblon krei pecoj de memoro por ni mem dinamike. Do tiu estas bildo ni duonvidis ĵus la alia tago. Ni ne vere logxas sur ĝi, sed tiu bildo estis daŭriganta sub la kapuĉo por semajnoj nun. Kaj tiel tio reprezentas, nur rektangulo kiu ni desegnas, via komputilo la memoro. Kaj eble via komputilo, aŭ CS50 ID, havas gigabajto de memoro aŭ RAM aŭ du gigabajtoj aŭ kvar. Fakte ne gravas. Via operaciumo Windows aŭ Mac VIN aŭ Linukso, esence permesas via programo pensi ke ĝi havas atingo al la tuteco de via komputilo la memoro, Eĉ kvankam vi povus esti kurante multoblaj programoj samtempe. Do fakte, tio ne vere funkcias. Sed ĝi estas speco de iluzio donita al ĉiuj viaj programoj. Do se vi havus du koncertoj de RAM, ĉi tale la komputilo povus pensi pri tio. 

Nun hazarde, unu el tiuj aferoj, unu el tiuj segmentoj de memoro, nomata stako. Kaj ja neniu tempo tiel ege skribe kodo ke vi nomiĝas funkcio, ekzemple ĉefa. Memoru ke ajna tempo mi havas tirita komputilo memoro, Mi ĉiam tiri ian duono de rektangulo tie kaj ne ĝenas parolante pri kio estas supre. Ĉar kiam ĉefa nomas, mi postulas ke vi akiras ĉi Sliver de memoro kiu iras malsupren tie. Kaj se ĉefa nomas funkcio kiel interŝanĝa, bone interŝanĝa iras tien. Kaj ĝi rezultas, jen kie ĝi estas fini. Sur iun nomita parva ene de via komputilo la memoro. Nun je la fino de la tago, tio decas adresoj. Estas kiel bitoko nulo, bajto unu, bajto 2 miliardoj. Sed se vi pensas pri ĝi kiel tiu rektangula objekto, ĉiuj ni faras ĉiun tempo ni nomas funkcio estas layering nova tranĉaĵo de memoro. Ni donas domadministranto tranĉaĵo de lia propra memoro por labori kun. 

Kaj memoru ke nun tiu estas grava. Ĉar se ni havas io kiel interŝanĝa kaj du lokaj variabloj kiel A kaj B kaj ni ŝanĝas tiujn valorojn de unu kaj du du kaj unu, revoko ke kiam interŝanĝa revenas, ĝi estas kvazaŭ ĉi tranĉaĵo de memoro estas nur irita. En realeco, ĝi estas ankoraŭ tie forensically. Kaj io ankoraŭ efektive tie. Sed koncepte, tio estas tiel kvankam ĝi estas tute irita. Kaj tiel ĉefa ne konas iun el la verkon kio okazis en tiu interŝanĝa funkcio, krom se ĝi estas vere pasis en tiuj argumentojn per montrilo aŭ referenco. Nun, la fundamenta solvo al tiu problemo kun swap preterpasas aferoj por adreso. Sed rezultas, tro, kio estas daŭras jam super tiu parto de la rektangulo ĉiu ĉi tiu tempo estas tamen ekzistas pli memoro tie supre. Kaj kiam vi dinamike rezervi memoron, ĉu ĝi estas ene de GetString, kiu ni estis farante por vi en la CS50 biblioteko, aŭ se vi infanoj vokas malloc kaj petu la operaciumo por eron de memoro, ĝi ne venas de la stako. Ĝi venas de alia loko en via komputilo la memoro ke nomiĝas la havaĵo. Kaj tio ne ajna malsama. Ĝi estas la sama RAM. Ĝi estas la sama memoro. Estas nur la RAM tio estas supren tie anstataŭ malsupren tie. 

Kaj tiel kion tio signifas? Nu, se via komputilo havas finia kvanto de memoro kaj la pilo kreskas supren, tiel paroli, kaj la havaĵon, laŭ al ĉi sago, kreskas malsupren. En aliaj vortoj, ĉiu tempo vi vokas malloc, vi transdonitan tranĉaĵo de memoro de supre, tiam eble iom pli malalta, tiam iom malsupra, ĉiufoje vi nomas malloc, la amaso, estas uzado, estas speco de kultivado, kreskanta pli kaj pli proksimen al kio? La pilo. Do ĉu tio ŝajnas kiel bona ideo? Mi volas diri, kie ĝi ne estas vere klara kion alian vi povas fari se vi nur havi finia kvanto de memoro. Sed tio estas certe malbona. Tiuj du sagoj estas sur kraŝi kurson por unu alia. 

Kaj ĝi rezultas ke malbona ulo, uloj kiuj estas aparte bona pri programado, kaj provanta haki en komputiloj, povas ekspluati tiun realecon. Fakte, ni konsideru iom fragmento. Do tiu estas ekzemplo vi povas legi pri pli detale en Vikipedio. Ni atentigi vin je la artikolo se scivola. Sed estas atako ĝenerale konata kiel la buffer overflow ke ekzistis tiel longe kiel homoj havis la kapablon manipuli komputilo memoro, speciale en C. Do temas pri tre arbitra programo, sed ni legis ĝin de malsupre supren. Ĉefa en argc char stelo argv. Do estas programo kiu prenas komandliniajn argumentojn. Kaj ĉiuj ĉefaj does ŝajne estas alvoko funkcio, nomas ĝin F por simpleco. Kaj ĝi pasas en kio? Argv de unu. Do pasas en F ajn la vorto estas ke la uzanto tajpas ĉe la prompto post la programo nomon. Tiel kiel Cezaro aŭ Vigenère, kiu vi eble memoras faras kun argv. 

Do kio estas F? F prenas en ĉeno kiel lia sola argumento, AKA char stelo, sama afero, kiel ĉeno. Kaj ĝi nomiĝas arbitre trinkejo en tiu ekzemplo. Kaj tiam char c 12, nur en laiko La terminoj, kio estas char c krampo 12 faras por ni? Kio ĝi faras? Asignante memoron, specife 12 bajtoj por 12 signoj. Ekzakte. Kaj tiam la lasta linio, veku kaj kopion, vi probable ne vidis. Ĉi estas ĉeno kopion funkcio kies celo en la vivo estas kopii lian duan argumenton en lia unua argumento, sed nur supren al iu numero de bajtoj. Do la tria argumento diras, kiom da bajtoj devus vi kopias? La longo de trinkejo, kiom la uzanto tajpas en. Kaj la enhavo de bari, ke kordoj, estas kopiis en la memoro indik ĉe C. 

Do tio ŝajnas ia stulta, kaj ĝi estas. Ĝi estas elpensita ekzemplo, sed estas reprezentanto de klaso de atako vektoroj, maniero de ataki programon. Ĉiuj estas belaj kaj bonaj se la uzanto tipoj en vorton kiu estas 11 karakteroj aŭ malpli, plus la backslash nula. Kio se la uzanto tajpas en pli ol 11 aŭ 12 aŭ 20 aŭ 50 signoj? Kio estas tio programo faros? Potenciale seg kulpo. Ĝi tuj blinde kopii ĉion en trinkejo supren al ĝia longo, kiu estas laŭvorte ĉio en trinkejo, en la adreson notita al C. Sed C nur preventa donita kiel 12 bajtoj. Sed estas neniu plia ĉeko. Mankas se kondiĉoj. Mankas eraro kontrolanta tie. 

Kaj tiel kion ĉi programo estas tuj fari estas simple blinde kopii ion al la aliaj. Kaj do se ni desegni tiun kiel bildo, jen nur Sliver de la memoro spaco. Do rimarki ĉe la fundo, ni havi la loka variablo trinkejo. Por ke puntero ke tuj store-- prefere ke lokaj argumento tio tuj stoki la kordo trinkejo. Kaj tiam rimarkos nur super ĝi en pilo, ĉar ĉiufoje kiam vi petos por memoro sur la stako, iras iomete super ĝi bilde, avizo ke ni havas 12 bajtoj tie. La supro maldekstra estas C krampo nulo kaj la dekstra malsupra unu estas C krampo 11. Tio estas nur kiamaniere la komputiloj tuj metos ĝin. Do ĝuste intuicie, se stango havas pli ol 12 karakteroj en totala, inkluzive de la backslash nulo, kie estas la 12 aŭ la C krampo 12 tuj iros? Aŭ prefere, kie estas la 12-a karakteron aŭ la 13a karaktero, la centa karaktero iranta por fini en la bildo? Supre aŭ malsupre? 

Bone, ĉar kvankam la pilo mem kreskas pli, iam vi metis aĵon en ĝin, por dezajno kialoj, metas la memoro de supro al fundo. Do se vi havas pli ol 12 bajtoj, vi tuj komenci anstataŭigi trinkejo. Nun tio estas cimo, sed estas Ne vere granda interkonsento. Sed estas granda interkonsento, ĉar estas pli stuff daŭriganta en memoro. Do jen kiel ni povus metis saluton, esti klara. Se mi tajpis en saluton ĉe la prompto. H-E-L-L-O backslash nulo, finas ene tiuj 12 bajtoj, kaj ni estas súper sekura. Ĉio bonas. Sed se mi tajpas ion plu, potenciale estas tuj rampas en trinkejo spaco. Sed pli malbone ankoraŭ, rezultas el ĉiuj ĉi tempo, kvankam ni neniam parolis pri ĝi, la pilo estas uzata por aliaj aferoj. Ĝi estas ne nur loka variabloj. 

C estas tre malalta nivelo lingvo. Kaj ia sekrete uzas la stako ankaŭ memori kiam funkcio estas vokita, kio la adreso estas de la antaŭa funkcio, do ĝi povas salti reen al tiu funkcio. Do kiam ĉefa alvokoj interŝanĝi, inter tion puŝis sur la pilo ne nur interŝanĝas lokaj variabloj, aŭ ĝiaj argumentoj, ankaŭ sekrete puŝis sur la pilo kiel reprezentitaj per la ruĝa tranĉaĵo tie, estas la adreso de ĉefa fizike en via komputilo memoro, tiel ke kiam interŝanĝa estas farita, la komputilo scias min devas reiri al ĉefa kaj fini ekzekuti la ĉefa funkcio. Do tiu estas danĝera nun, ĉar se la uzanto tajpas en bone pli ol saluton, tia ke la uzanto enigo clobbers aŭ overwrites ke ruĝa sekcio, logike se la komputilo nur tuj blinde supozi ke la bitokoj en tiu ruĝa tranĉaĵo estas la adreso al kiu devus reveni, kion se la kontraŭulo estas sufiĉe lerta aŭ bonŝancon meti sekvenco de bajtoj tie kiu similas adreson, sed ĝi estas la adreso de kodo ke li aŭ ŝi volas la komputilon ekzekuti anstataŭ ĉefa? 

En aliaj vortoj, se kio la uzanto estas tajpi ĉe la prompto: ne nur io nenoca kiel saluton, sed estas reale kodo kiu estas ekvivalenta forigi ĉiujn ĉi uzanto dosierojn? Aŭ retpoŝtu sian pasvorton al mi? Aŭ komenci ensalutanta ilia pulsbatoj, dekstra? Iufoje vojo, ni kondiĉas hodiaŭ, ke ili povus entajpi ne ĝuste saluton mondo aŭ ilia nomo, ili povus esence Iam en kodo, kaj nuloj tiuj, kiujn la komputilo erarojn por ambaŭ kodo kaj adreson. Do kvankam iom abstrakte, se la uzanto tajpas en sufiĉe adversarial kodo ke ni ĝeneraligi tie kiel A. A estas atako aŭ kontraŭuloj. Do simple malbonaj aĵoj. Ni ne zorgas pri la nombroj aŭ la nuloj aŭ aĵoj hodiaŭ, tia ke vi finos superskribi ke ruĝa sekcio, rimarkos ke sekvenco de bajtoj. O 835 C nulo ok nul. Kaj nun kiel Vikipedia artikolo tie proponis, se vi nun vere komenci etikedi la bajtoj en via komputilo memoro, kion la Vikipedia artikolo estas proponante estas ke, se la adreso de tiu pinta maldekstra bajto estas 80 C 0 3508. 

En aliaj vortoj, se la malbona ulo estas sufiĉe lertaj kun lia aŭ ŝia kodo por fakte metis kelkajn tie ke respondas al la adreso de la kodo li aŭ ŝi injektis en la komputilo, vi povas trompi la komputilo en fari ion. Forigado dosieroj, emailing aferojn, snufante vian trafiko, laŭvorte povus esti io injektita en la komputilo. Kaj tiel buffer overflow atako en sia kerno estas nur stulta, stulta supera de tabelo ke ne havis lian limojn kontrolis. Kaj tiu estas kio estas super danĝera kaj samtempe super potencaj en C estas ke ni ja havas aliro al anywhere en la memoro. Ĝi dependas de ni, la programistoj, kiuj skribas la originala kodo kontroli la Darn longo de ajna arrays ke ni manipulas. Do esti klara, kio estas la embaraso? Se ni ruliĝi reen al tiu kodo, mi devus ne nur ŝanĝi la longo de trinkejo, kio alie mi devus esti kontrolanta? Kion alian mi devus esti faranta al malebligi ĉi atako tute? Mi ne volas simple blinde diri ke vi kopiu kiel multaj bitokoj kiel estas la longo de trinkejo. Mi volas diri, kopiu kiel multaj bitokoj kiel estas en trinkejo ĝis la asignitaj memoro, aŭ la 12 maksimume. Do mi bezonas ian se kondiĉo kiu faras kontrolu la longo de trinkejo, sed se ĝi superas 12, ni nur malfacile kodo 12 kiel la maksimuma ebla distanco. Alie la tn bufro overflow atako povas okazi. Funde de tiuj diapozitivoj, se vi estas scivola legi pli estas la fakta originala artikolo se vi ŝatus preni rigardon. 

Sed nun, inter la prezoj pagis refarigxis ineficiencias. Do kiu estis rapida malalta nivelo rigardi kion problemoj povas ekesti nun ke ni havas aliron al komputilo la memoro. Sed alia problemo ni jam stumblis lunde Estis ĝuste la neefikecon de ligitaj listo. Ni estas reen al lineara tempo. Ni ne plu havas apudan tabelon. Ni ne havas aliro aleatorio. Ni ne povas uzi kvadrata krampo skribmaniero. Ni laŭvorte devas uzi dum buklo kiel la unu mi skribis antaŭ momento. Sed lunde, ni asertis, ke ni povas rampi reen al la regno de efikeco atingi ion tio logaritma eble, aŭ bona ankoraŭ, eble eĉ iu kiu estas tn konstanta tempo. Do kiel ni povas fari tion de uzanta ĉi tiujn novajn iloj, tiuj adresoj, tiuj punteros, kaj fadenigante aferojn de nia propra? Nu, supozu ke tie, ĉi tiuj estas aro de nombroj kiun ni volas konservi en datumstrukturo kaj serĉo kompetente. Ni povas absolute malantaŭenigi al semajno du, ĵeti tiujn en tabelo, kaj serĉu ilin uzante binaran serĉon. Dividu kaj konkeru. Kaj fakte vi skribis Binara serĉo en PSET3, kie implementado la trovaĵo programo. Sed vi scias kion. Tie estas speco de pli ruza maniero fari tion. Ĝi estas iom pli malnaiva kaj ĝi eble permesas al ni vidi kial duuma serĉo estas tiel rapida. Unue, ni enkonduki la nocio de arbo. Kiu kvankam en realaĵo arboj ia kreski kiel tiu, en la mondo de komputilo scienco ili ia kreski malsupren kiel familio arbo, kie vi havas viaj avoj aŭ grandaj geavoj aŭ whatnot ĉe la supro, la patriarko kaj la matriarko de la familio, nur unu tn radiko, nodo, sube kiuj estas liaj filoj, sub kiu estas liaj infanoj, aŭ liaj posteuloj pli ĝenerale. Kaj iu pendis ekstere la fundo de la familio arbo, krom esti la plej juna en la familio, povas ankaŭ esti nur genéricamente vokis la folioj de la arbo. 

Do tio estas nur aro de vortoj kaj difinoj por iu nomita arbo en komputilo scienco, multe kiel familio arbo. Sed estas amatoro enkarniĝoj de arboj, el kiuj unu nomiĝas binara serĉo arbo. Kaj vi povas ia tease dise kio tion faras. Nu, estas duuma en kiu senco? Kien la duuma veni de tie? Pardonon? Ĝi ne estas tiel multe kiel aŭ aŭ. Estas pli ke ĉiu el la nodoj ne havas pli ol du infanojn, kiel ni vidos tie. Ĝenerale, tree-- kaj viaj gepatroj kaj geavoj povas havi tiom da infanoj aŭ nepoj kiel ili efektive volas, kaj tiel ekzemple tie ni havas tri infanoj ekstere ke dekstra mano nodo, sed en duuma arbo, nodo havas nul, unu, aŭ du infanojn maksimume. Kaj tio estas bela propraĵo, ĉar se ĝi estas haltigataj per du, ni tuj povos akiri malgrandan log bazo du ago okazas tie finfine. Do ni havas ion logaritma. Sed pli en kiu tre frue. Serĉu arbo signifas, ke la ciferoj estas aranĝita tia ke la maldekstra infano valoro estas pli granda ol la radiko. Kaj lia dekstra infano estas granda ol la radiko. Alivorte, se vi prenos iun el la nodoj, la cirkloj en ĉi tiu bildo, kaj rigardas lian maldekstran infano kaj lia dekstra infano, la unua devus esti malpli ol, la dua devus esti pli granda ol. Do prudento kontroli 55. Ĝi lasis infano estas 33. Ĝi estas malpli ol. 55, lia dekstra infano estas 77. Ĝi estas pli granda ol. Kaj tio estas rekursia difino. Ni povis kontroli ĉiu el tiuj nodoj kaj la sama padrono tenus. 

Do kio estas agrabla en duuma serĉo arboj tiu, ni povas apliki ĝin kun struct, nur ŝatas tion. Kaj kvankam ni ĵetante multaj strukturoj ĉe via, ili estas iom intuicia nun espereble. La sintakso estas ankoraŭ arcano por certa, sed la enhavon de nodo en ĉi context-- kaj ni plenumas uzante la vorton nodo, ĉu ĝi estas rektangulo sur la ekrano aŭ cirklo, ĝi estas nur kelkaj genraj ujo, en tiu kazo de arbo, kiel la ni vidis, ni bezonas entjero en ĉiu de la nodoj kaj tiam Mi bezonas du punteros montradon maldekstren infano kaj la dekstra infano, respektive. Do jen kiel ni povus apliki ke en struct. Kaj kiel povus mi implementarlo en kodo? Nu, ni prenu rapidan rigardi tiun etan ekzemplon. Ĝi ne estas praktika, sed mi havas kopiitaj kaj batitaj de tiu strukturo. Kaj se mia funkcio por duargumenta serĉo arbo nomiĝas serĉo, kaj tio prenas du argumentojn, entjero N kaj puntero al nodo, do puntero al la arbo aŭ montrilo al la radiko de arbo, kiel mi iros priserĉi por N? Nu, unue, ĉar mi estas pritraktas punteros, Mi tuj fari prudento ĉeko. Se arbo egaluloj egalas nula, estas N en ĉi tiu arbo aŭ ne en ĉi tiu arbo? Ne povas esti, ĉu ne? Se mi estas pasinteco nula, nenio estas tie. Mi povus tiel simple blinde diri reveni falsaj. Se vi donos al mi nenion, mi certe ne povas trovi ajnan nombron N. Do kion alian povus mi kontroli nun? Mi tuj diros bone alia se N estas malpli ol kiom estas ĉe la arbo nodo ke mi estis transdonita N valoro. En aliaj vortoj, se la nombro mi serĉas, N, estas pli malgranda ol la nodo ke mi rigardas. Kaj la nodo Mi serĉas ĉe nomata arbo, kaj memoras de la antaŭa ekzemplo atingi la valoron en puntero, Mi uzas la saga skribmaniero. Do se N estas malpli ol arbo sagon No, mi volas koncepte iros maldekstren. Kjel mi esprimas Searching forlasis? Esti klara, se tio estas la bildo en demando, kaj Mi estis pasita ke plejsupra arrow ke estas indikante malsupren. Jen mia arbo montrilo. Mi fingromontrante la radiko de la arbo. Kaj Mi serĉas diru, por la nombro 44, arbitre. Estas 44 malpli ol aŭ pli granda ol 55 evidente? Do estas malpli ol. Kaj tiel ĉi se kondiĉo validas. Do koncepte, kion mi volas serĉu apud se Mi serĉas 44? Yeah? 

Ekzakte, mi volas serĉu la maldekstra infano, aŭ maldekstre sub-arbo de tiu bildo. Kaj fakte, lasu min tra la bildo malsupren tie por nur momento, kiam Mi ne povas skrapi ĉi ekstere. Se mi komencas ĉi tie ĉe 55, kaj Mi scias ke la valoro 44 Mi serĉas estas la maldekstra, ĝi estas speco de kiel ŝirante la telefono libro en duono aŭ ŝirante la arbo en duono. Mi ne plu devos zorgi pri tiu tuta duono de la arbo. Kaj tamen, scivoleme en terminoj de la strukturo, tion super tie ke komenciĝas kun 33, kiu mem estas duuma serĉo arbo. Mi diris la vorton rekursia antaŭ ĉar ja tiu estas datumstrukturo ke laŭdifine estas rekursiaj. Vi povus havi arbo kiu estas tio grandan, sed ĉiu el liaj infanoj reprezentas arbon nur iom pli malgranda. Anstataŭ ĝi estanta avo aŭ avino, nun ĝi estas nur panjo or-- Mi ne povas say-- ne panjon aŭ paĉjo, ke estus stranga. Anstataŭ la du infanoj tie estus kiel frato kaj gefrato. Nova generacio de la familio arbo. Sed strukture ĝi estas la sama ideo. Kaj ĝi rezultas mi havas funkcion kun kiu mi povas serĉi duuma serĉo arbon. Ĝi nomiĝas serĉo. Mi serĉi N en arbo sago maldekstren alie se N estas pli granda ol la valoro ke mi estas nune en. 55 en la rakonto antaŭ momento. Mi havas funkcion nomita serĉo ke mi povas nur pasi N ĉi kaj rekursie serĉo la sub-arbo kaj simple reveno kio ajn tiu respondo. Alie Mi havas iuj fina bazo kazo tie. 

Kio estas la fina kazo? Arbo estas aŭ nula. La valoron mi ĉu serĉas estas malpli ol aŭ pli granda ol tiu aŭ egala al ĝi. Kaj mi povus diri egalaj egalaj, sed logike ĝi estas ekvivalenta al nur diras alia ĉi tie. Tiel vera kiel mi trovas ion. Do espereble tiu estas eĉ pli konvinka ekzemplo ol la stulta sigma funkcio ni faris kelkajn prelegojn reen, kie estis egale facile uzi buklo kalkuli ĉiujn numerojn de unu al N. tie kun datumstrukturo ke mem estas rekursie difinita kaj rekursie desegnita, nun ni havas la kapablon esprimi nin en kodo kiu mem estas rekursiaj. Do tiu estas la ĝusta sama kodo tie. 

Do kion aliaj problemoj povas ni solvi? Tiel rapida paŝo for de arboj por nur momento. Jen, diru, la germana flago. Kaj estas klare ekzemplo por tiu flago. Kaj estas multaj flagoj en la mondo kiu estas tiel simpla kiel tiu en terminoj de siaj koloroj kaj skemoj. Sed supozu, ke tiu estas stokita kiel .gif, Aŭ JPEG aŭ bitmap aŭ ping, ajna grafika dosierformato kun kiu vi konas, Kelkaj de kiu ni estas ludante kun en PSET4. Ĉi tio ne ŝajnas inda enteni nigra pikselo, nigra pikselo, nigra pikselo, dot, punkto, punkto, tuta aro de nigraj pikseloj por la unua scanline, aŭ vico, tiam tuta amaso de la sama, tiam tutan faskon de la sama, kaj tiam tutan faskon de ruĝa rastrumeroj, ruĝa rastrumeroj, ruĝa rastrumeroj, tiam tuto faskon da flavaj rastrumeroj, flava, dekstra? 

Ekzistas tiaj senefikeco tie. Kiel vi intue kunpremi la germana flago se efektiviganta ĝin kiel dosieron? Kiel kion informo povas ni ne ĝeni stokante en disko por malpliigi niajn grandeco de dosiero el kiel megabajto al kilobajto, io malgrandaj? Kien kuŝas la redundo tie esti klara? Kion vi povus fari? Yeah? Ekzakte. Kial ne prefere ol memori la koloro de ĉiu Darn rastrumero kiel vi faras en PSET4 kun la bitmap dosiero formato, kial vi ne simple reprezenti la plej maldekstra kolumno de rastrumeroj, ekzemple faskon de nigra rastrumeroj, faskon de ruĝa, kaj faskon da flavaj, kaj tiam simple iel kodas la ideon de ripeti ĉi 100 fojoj aŭ ripeti tiun 1,000 fojoj? Kie 100 aŭ 1,000 estas nur entjero, do vi povas foriri kun nur unu nombro anstataŭ centoj aŭ miloj de pliaj rastrumeroj. Kaj efektive, jen kiel ni povis kunpremi la germana flago. Kaj Nun kio pri la franca flago? Kaj iom ian mensa ekzerco, kiu flagon povas kunpremi pli surdiske? La germana flago aŭ la franca flago, se ni prenas tiun aliron? La germana flago, ĉar estas pli horizontala redundo. Kaj projekte, multaj grafikaj dosieron formatoj ĉu vere labori kiel skanado liniojn horizontale. Ili povis funkcii vertikale, ĵus homaro decidis jaroj ke ni ĝenerale pensas pri aferoj vico per vico anstataŭ kolumno por kolumno. Do efektive, se vi estus por rigardi la dosieron grandeco de germana flago kaj franca flago, tiel longe kiel la rezolucio estas la sama, la sama larĝo kaj alteco, ĉi tiu tie tuj estos pli granda, ĉar vi devos ripeti mem trifoje. Vi devas entajpi blua, ripeto mem, blanka, ripeti mem, ruĝa, ripetas vin. Vi ne povas simple iru ĉiuj la vojo dekstre. Kaj kiel flanken, por fari liberigi la kunpremo estas ĉie, se tiuj estas kvar kadroj de video-- vi eble memoras ke filmo aŭ video estas ĝenerale kiel 29 aŭ 30 kadroj je sekundo. Estas kiel iom flip libro kie vi nur vidu bildon, bildo, bildo, bildo, bildo ĵus super rapida tiel ĝi aspektas kiel la aktoroj sur la ekrano estas movanta. Jen burdoj sur supro de faskon da floroj. Kaj kvankam ĝi povus esti speco de malfacile vidi unuavide, la sola afero movanta en tiu filmo estas la abelo. 

Kio estas muta pri stokante video kunpremitaj? Estas speco de malŝparo stoki video kiel kvar preskaŭ identaj bildoj kiu diferencas nur en la mezuro kie la abelo estas. Vi povas forĵeti plej de tiu informo kaj memori nur, ekzemple, la unua kadro kaj la lasta kadro, ŝlosilo kadroj se vi havas iam aŭdis la vorton, kaj simple stoki en la mezo kie la abelo estas. Kaj vi ne devas stoki ĉiujn la rozo, kaj bluan, kaj la verda valoroj ankaŭ. Do tio estas nur por diri ke kunpremo estas ĉie. Estas tekniko ni ofte uzas aŭ preni por donita tiujn tagojn. 

Sed kiel vi kunpremi teksto? Kiel vi iras pri kunpremante teksto? Nu, ĉiu el la karakteroj en Ascii estas unu bajto, aŭ ok bitoj. Kaj jen speco de mutaj, dekstra? Ĉar vi probable Speco kaj E kaj I kaj O kaj U multe pli ofte ol kiel W aŭ Q aŭ Z, depende de la lingvo en kiu vi skribas certe. Kaj do kial ni uzas ok bitojn por ĉiu litero, Inkluzivanta la malplej populara literoj, dekstra? Kial ne uzi pli malmultajn bitoj por la súper populara literoj, kiel E, tion vi divenu unua en Rado de Fortuno, kaj uzi pli bitojn por la malpli populara literoj? Kial? Ĉar ni ĵus tuj uzi ilin malpli ofte. 

Nu, Ĝi rezultas ke havas estis provoj faritaj por fari tion. Kaj se vi memoras de lernojaro lernejo aŭ mezlernejo, Morsa kodo. Morsa kodo havas punktojn kaj strekoj kiuj povas esti transdonita kune drato kiel sonas aŭ signaloj de iu speco. Sed Morsa kodo estas super pura. Estas speco de duuma sistemo en ke vi havas punktoj aŭ streketoj. Sed se vi vidas, ekzemple, du punktoj. Aŭ se vi pensas reen al la operatoro kiu iras tiel pepi, pepi, pepi, pepi, trafante iom ellasilon kiu transdonas signalon, se vi, la ricevanto, ricevas du dots, kion mesaĝon vi ricevis? Tute arbitra. 

Mi? Mi? Aŭ kion about-- aŭ mi? Eble estis nur du E pravas? Do ekzistas tiu problemo de decodability kun Morso kodo, per kiu krom se la persono sendas la mesaĝon fakte paŭzoj tiel vi povas ordigi de vidi aŭ aŭdi la breĉoj inter literoj, ĝi ne estas sufiĉa nur por sendu torenton da nuloj kaj, aŭ punktoj kaj strekoj, ĉar ekzistas ambigueco. E estas sola punkto, do se vi vidas du punktojn aŭ aŭdi du punktojn, Eble estas du E aŭ eble estas unu I. Do ni bezonas sistemon kiu estas iom pli ruza ol tio. Do viro nomis Huffman jaroj antaŭ venadis kun precize tiu. Do ni simple tuj preni rapidan rigardon ĉe kiel arboj estas germane al tiu. Supozu ke tiu estas iuj stulta mesaĝo vi volas sendi, formita de nur A, B, C la D kaj E, sed ekzistas multe de redundo tie. Ĝi ne estas intencita esti angla. Ĝi ne estas ĉifrita. Estas nur stulta mesaĝon kun multe da ripeto. Do se vi reale kalkuli ĉiujn -a, B, C la, D, kaj E, jen la frekvenco. 20% de la literoj estas -a, 45% de la literoj estas E, kaj tri aliaj frekvencoj. Ni kalkulis tie supre permane kaj ĝuste faris la math. 

Do rezultas ke Huffman, antaŭ kelka tempo, rimarkis ke, vi scias kio, se mi komencas konstruaĵo arbo aŭ arbaro de arboj, se vi volas, jene, mi povas fari la sekvajn. Mi tuj donos al ĉiu nodo de la leteroj kiujn mi zorgas pri kaj mi tuj stoki ene de tiu nodo la frekvencoj kiel glitpunktaj valoro, aŭ vi povus uzi ĝin N, tro, sed ni simple uzu kaleŝego tie. Kaj la algoritmo kiu li proponita estas ke vi prenu ĉi arbaro de ununura nodo arboj, tiel super mallonga arboj, kaj vi komencas konektante ilin kun novaj grupoj, novaj gepatroj, se vi volas. Kaj vi faros tion elektante la du pli malgrandaj frekvencoj samtempe. Do mi prenis 10% kaj 10%. Mi kreas novan nodon. Kaj mi alvokis la nova nodo 20%. 

Kiu du nodoj mi kombinas poste? Ĝi estas iom ambigua. Do ekzistas iu angulo kazoj konsideri, sed konservi aferojn belajn, Mi tuj elektos 20% - Mi nun ignori la infanoj. Mi tuj elektos 20% kaj 15% kaj desegni du novaj lateroj. Kaj nun kiu du nodoj mi logike kombini? Ignori ĉiujn infanojn, ĉiuj genepoj, nur rigardas la radikojn nun. Kiu du nodoj mi jungu kune? Punkto du kaj 0.35. Do lasu min tiri du novaj lateroj. Kaj tiam mi havas nur unu maldekstra. Do jen arbo. Kaj ĝi estas estita desegnita intence rigardi ia bela, sed rimarki ke la lateroj havas ankaŭ estis etikeditaj nulo kaj unu. Do ĉio maldekstre randoj estas nulo arbitre, sed konstante. Ĉiuj rektaj randoj estas ones. 

Kaj tiel kion Hoffman proponitaj estas, se vi volas reprezenti B, anstataŭ reprezenti la numero 66 kiel an Ascii kiu estas ok tutan bitoj, Vi scias kion, simple vendejo desegnon nulo, nulo, nulo, nulo, ĉar tio estas la vojo de mia arbo, sinjoro Huffman la arbo, al la folio de la radiko. Se vi volas stoki Kaj, kontraste, ne sendu ok bitoj kiuj reprezentas E. Anstataŭe, sendu kion mastro de bitoj? Unu. Kaj kio estas agrabla pri tio estas ke E estas la plej populara letero, kaj vi uzas la mallonga kodo por ĝi. La venonta plej popularaj letero aspektas kiel ĝi estis A. Sed do kiom da bitoj Ĉu li proponis uzi por tio? Zero, unu. 

Kaj ĉar ĝi estas implementado kiel tiu arbo, nun lasu min kondiĉas ekzistas neniu ambigueco kiel en Morse kodo, ĉar ĉiuj el la literojn vi zorgas pri estas ĉe la fino de ĉi tiuj lateroj. Do jen nur unu apliko de arbo. Ĉi is-- kaj mi skuos mian manon je ĉi kiamaniere vi povus efektivigi tion kiel C strukturo. Ni nur bezonas kombini simbolo, kiel char, kaj la ofteco en maldekstra kaj dekstra. Sed ni rigardu du fina ekzemploj ke vi akiri sufiĉe familiara kun post kvizo nulo en problemo starigis kvin. 

Do estas la datumstrukturo konata kiel hash tablo. Kaj hash tablo estas speco de malvarmigi en tio ĝi havas siteloj. Kaj supozu ke estas kvar sitelojn tie, nur kvar malplenan spacoj. Jen ludkartaro de kartoj, kaj tie estas klubo, fosilon, klubo, diamantoj, klubo, diamantoj, klubo, diamantoj, clubs-- do ĉi tiu estas la hazardo. Koroj, hearts-- do mi estas bucketizing ĉiuj enigoj tie. Kaj hash tablo bezonoj rigardi vian enigo, kaj tiam metis ĝin en certa meti bazita sur kio vi vidas. Ĝi estas algoritmo. Kaj mi estis uzanta super simpla vida algoritmo. La plej malfacila parto de kiu estis memorante kion la bildoj estis. Kaj tiam tie estas kvar aferoj entute. 

Nun la stakoj estis kreskantaj, kiu Estas intenca dezajno afero tie. Sed kion alian povus mi fari? Do fakte tie ni havas faskon de malnova lernejo ekzameno libroj. Supozu ke faskon da studentoj nomoj estas tie. Jen pli granda hash tablo. Anstataŭ kvar siteloj, Mi, ni diru 26. Kaj ni ne volas iri prunteprenos 26 aferojn de ekstere [? Annenberg?], Do jen kvin kiuj reprezentas A tra Z. Kaj se mi vidu studento kies nomo komenciĝas per A, Mi tuj metis sian kvizo tie. Se iu komencas kun C, tien, A-- reale, ne volis fari tion. B iras tien. Do mi havas A kaj B kaj C. Kaj nun jen alia studento. Sed se tiu hash tablo estas implementado kun tabelo, Mi estas speco de ŝraŭbita ĉe tiu punkto, dekstra? Mi ia bezonas meti tiun ie. 

Do unu maniero mi povas solvi tio, ĉiuj Bone, A estas okupita, B estas okupata, C estas okupata. Mi tuj metis lin en D. Tiel ĉe unue, mi havas hazardaj tuja aliro al ĉiu el la siteloj por la studentoj. Sed nun ĝi estas speco de transdonitaj en ion lineara, ĉar se mi volas serĉi iun kies nomo komenciĝas per A, mi kontrolu ĉi tie. Sed se tio ne estas la A Studento Mi serĉas, Mi specon de devas komenci kontrolanta la siteloj, ĉar kion mi faris estis speco de lineare sondi la datumstrukturo. Stulta maniero diri simple aspektas por la unua havebla malfermo, kaj meti kiel planon B, tiel diri, aŭ planon D en tiu kazo, la valoro en tiu loko anstataŭe. Tiu estas nur tiel ke se oni devas ricevis 26 lokojn kaj ne lernantoj kun la nomo Q aŭ Z, aŭ io simila ke, almenaŭ vi uzas la spacon. 

Sed ni jam vidis pli clever solvojn ĉi tie, ĉu ne? Kion vi farus anstataŭ se vi havas kolizion? Se du personoj havas la nomo A, kion farus estinti pli inteligenta aŭ pli intuicia solvo ol nur Metante kie D estas supozita esti? Kial mi ne nur iri eksteren [? Annenberg?], kiel malloc, alia nodo, metis ĝin tie kaj surmetu ke studento tie. Por ke mi esence havas ia tabelo, aŭ eble pli elegante kiel ni estas ekvidas ligillisto. 

Kaj tiel hash tablo estas strukturo kiuj povis rigardi ĝuste kiel ĉi, sed pli lerte, vi ion nomatan apartan sinsekvon, per hash tablo tute simple estas tabelo, ĉiu el kies elementoj ne estas nombro, estas sin ligillisto. Tiel ke vi ricevas super rapida aliro decidi kie hash via valoro. Multe kiel kun la kartoj ekzemple, Mi faris súper rapidajn decidojn. Koroj iras tie, diamantoj iras tien. Sama ĉi tie, A iras tie, D iras tie, B iras tien. Do super rapida rigardo-ups, kaj se vi hazarde trafos kazo kie vi havas koliziojn, du homoj kun la sama nomo, bone tiam vi simple komenci ligante ilin kune. Kaj eble vi gardos ilin ordo alfabete, eble ne. Sed almenaŭ nun ni havas la dinamismo. Do unuflanke ni havas súper rapida konstanta tempo, kaj speco de lineara tempo implikita se tiuj ligitaj lertaj komencas akiri iom longa. 

Do tiu speco de stulta, geeky ŝerco jaroj. Ĉe la CS50 hako-a-thon, kiam studentoj kontroli en, iuj TF aŭ CA ĉiujare pensas ĝi estas amuza toleri signo kiel tiu, kie nur signifas se via nomo komenciĝas per A, iri tiun vojon. Se via nomo komenciĝas kun B, iru this-- OK, ĝi estas amuza eble poste en la semestro. Sed estas alia maniero fari tion, ankaŭ. Revenu al tio. 

Do ekzistas tiu strukturo. Kaj tiu estas nia lasta strukturon por hodiaŭ, kiu estas iu nomita trie. T-R-Mi-E, kiu ial estas mallonga por rehavigo, sed ĝi nomiĝas trie. Do trie estas alia interesa amalgama de multe de tiuj ideoj. Ĝi estas arbo, kiun ni vidis antaŭe. Ĝi ne estas duuma serĉo arbo. Ĝi estas arbo kun iu ajn nombro de infanoj, sed ĉiu el la infanoj en trie estas tabelo. Tabelo de grandeco, diru, 26 aŭ eble 27 se vi volas subteni skripto nomoj aŭ apostrofoj en nomojn de homoj. 

Kaj tiel tio estas datumstrukturo. Kaj se vi rigardas el supro sube, kiel se rigardi la supro nodo tie, M, estas indikante la plej maldekstra afero tie, kiu tiam estas A, X, W, E, L, L. Jen nur datumstrukturo ke arbitre estas stokante popolaj nomoj. Kaj Maxwell estas stokita per nur jenaj vojeto tabelo tabelo al tabelo. Sed kio estas mirinda pri trie estas ke, dum ligillisto kaj eĉ tabelo, la plej bona ni iam alveninta estas lineara tempo aŭ logaritma tempo rigardanta iu supren. En tiu datumstrukturo de trie, se miaj datumstrukturo havas unu nomon en ĝi kaj Mi serĉas Maxwell, mi estas tuj trovos lin bela rapide. Mi nur serĉas M-Al-X-W-E-L-L. Se tiu datumstrukturo, kontraste, se N estas miliono, se ekzistas milionoj nomoj en ĉi datumstrukturo, Maxwell estas ankoraŭ tuj estos discoverable post ĵus G-Al-X-W-E-L-L paŝojn. Kaj David-- D-Al-V-mi-D paŝoj. Alivorte, per konstruado datumstrukturo tio ricevis ĉiujn tiujn arrays, ĉiuj kiuj sin apogi hazarda aliro, Mi povas komenci suprenrigardinte popola nomi uzante kvanto de tempo kiu estas proporcia al la nombro ne de aferoj en la datumstrukturo, kvazaŭ miliono ekzistantaj nomoj. La kvanto de tempo ĝi prenas al mi trovi M-Al-X-W-E-L-L en ĉi datumstrukturo estas proporcia ne al la grandeco de la datumstrukturo, sed la longeco de la nomo. Kaj realisme la nomojn ni suprenrigardinte estas neniam iranta esti freneza longa. Eble iu havas 10 karaktero citi, 20 karaktero nomo. Estas certe finia, dekstra? Estas homa sur la Tero, kiuj havas la plej longan eblan nomon sed tiu nomo estas konstanta valoro longo, dekstra? Ĝi ne varias en iu senco. Do tiamaniere, ni atingita datumstrukturo ke estas konstanta tempo rigardo-supren. Ĝi faras preni kelkajn paŝojn depende de la longo de la enigo, sed ne la nombron de nomo en la datumstrukturo. Do se ni duobligi la numeron de nomoj sekva jaro de miliardo al du miliardoj, trovo Maxwell tuj prenos la ĝusta sama nombro de sep ŝtupoj trovi lin. Kaj tial ŝajne ni atingis nia sankta grail de rula tempo. 

Do kelkajn rapidajn anoncoj. Kvizo nulo venas supren. Pli sur tiu en la paso de afiŝinto dum la venontaj kelkaj tagoj. Lundo la lecture-- ĝi estas ferio tie en Harvard lunde. Ĝi ne estas en New Haven, do ni prenas la klaso al New Haven por prelego lunde. Ĉio estos filmado kaj eksudita vivas kiel kutime, sed ni finos hodiaŭ kun 30 dua tranĉeto nomita "Deep Thoughts" per Daven Farnham, kiu estis inspirita lasta jaro por sabato Night Live la "Deep Thoughts" por Jack Handy, kiu devus nun sencon. 

FILMO: Kaj nun, "Deep Pensoj "de Daven Farnham. Hash tablo. 

Parolanto 1: Bone, tio estas ĝi nun. Ni vidos vin proksima semajno. 

DOUG: Vidi ĝin en ago. Do ni rigardu tion tuj. Do jen, ni havas unsorted tabelo. 

IAN Doug, vi povas iri antaŭen kaj rekomenco tion por nur sekundo, bonvolu. Bone, fotiloj ruliĝas, do ago kiam ajn vi pretos, Doug, OK? DOUG: Bone, do kion ni havi jen unsorted tabelo. Kaj mi koloraj ĉiujn la elementoj ruĝa por indiki ke ĝi estas, fakte, unsorted. Do memoru, ke la unua afero ni fari Estas ni ordigi la maldekstra duono de la tabelo. Tiam ni ordigi la dekstra duono de la tabelo. Kaj ya-da, ya-da, ya-da, ni kunfandi ilin kune. Kaj ni havas tute ordo tabelo. Do jen kiel kunfandi speco funkcias. 

IAN: Halt, halt, halt, tranĉo, tranĉo, tranĉo, tranĉi. Doug, ne eblas simple ya-da, ya-da, ya-donu, vian vojon tra merge varon. 

DOUG: mi ĵus faris. Ĝi estas bone. Ni estas bone iri. Ni simple teni ruliĝanta. Do ĉiuokaze, 

IAN: Vi devas klarigi ĝi pli plene ol tio. Tio estas nur ne sufiĉe. DOUG: Ian, tamen ni ne bezonas reiri al unu. Ĝi estas bone. Do ĉiuokaze, se ni daŭrigas kun merge-- Ian, ni estas en la mezo de la filmación. 

IAN: Mi scias. Kaj ni ne povas simple ya-da, ya-da, ya-da, tra la tuta procezo. Vi devas klarigi kiel la du flankoj akiri kunfanditaj kune. 

DOUG: sed ni jam klarigis kiel la du sides-- 

IAN: Vi ĵus montrita ili merge tabelo. DOUG: Ili konas la procezon. Ili estas belaj. Ni iris super ĝi dek fojojn. 

IAN: Vi nur saltis rajton super ĝi. Ni iras reen al unu, vi ĉu ne ya-da, ya-da super ĝi. Bone, reen al unu. 

DOUG: Mi devos reiri tra ĉiuj de la diapozitivoj? Mia Dio. Estas kiel la sesa fojo, Ian. Ĝi estas bone. 

IAN: Bone. Vi preta? Granda. Ago.