[MUZIKO Ludante] 

ANDI PENG: Bonvenon semajno 6 de sekcio. Ni deviis de nia normo sekcio tempo de mardo posttagmezo al tiu bela dimanĉa mateno. Dankon por ĉiuj kiuj aliĝis al mi hodiaŭ, sed serioze, ĉirkaŭvojon de aplaŭdoj. 

Tio estas sufiĉe granda peno. Mi preskaŭ ne eĉ fari en tempo, sed estis okej. Do mi scias ke vi ĉiuj ĵus faris ĝin al la kvizo. Unue, bonvenon al la flip flanko de tio. 

Due, ni parolos pri tio. Ni parolos pri la kvizo. Ni parolos pri kiom vi faras en la klaso. Vi estos bone. Mi havas viajn kvizojn por vi fine de tie, do se vi infanoj volas preni oni rigardas ĝin, tute bone. 

Tiel rapide ol ni komencos, la tagordo por hodiaŭ estas kiel sekvas. Kiel vi povas vidi, ni estas esence rapidan pafon tra tuta fasko de datumstrukturoj vere, vere, vere rapide. Do kiel tia, ĝi ne estos súper interaga hodiaŭ. Ĝi devos simple esti mi specon de bruo aferojn vi, kaj se mi konfuzas vin, se mi iras tro rapide, sciigu min. Ili estas nur diversaj datumoj strukturoj, kaj kiel parto de via pset por tiu venonta semajno, vi esti demandita apliki unu el ili, eble du el them-- ambaux en via pset. Bone, do mi simple tuj starti kun iuj anoncoj. Ni transiru stakoj kaj atendovicoj pli en profundo ol kion ni faris antaŭe la kvizo. Ni transiru ligitaj listo denove, refoje, pli ĝisfunde ol kio ni havis antaŭ la kvizo. Kaj tiam ni parolos pri hash tabloj, arboj kaj provas, kion estas ĉiuj belaj necesa por via pset. Kaj tiam ni iros super kelkaj helpema konsiloj por pset5. 

Bone, do kvizo 0. La mezumo estis de 58%. Ĝi estis tre malalta, kaj tiel vi infanoj ĉiuj faris tre, tre bone en konsento kun tio. 

Pli malpli, regulo de thumb estas se vi estas ene norma devio de la meznombro Precipe pro ni estas en malpli comfy sekcio, vi tute bone. Vi estas sur trako. Vivo estas bona. 

Mi scias ke estas timiga pensi ke Mi akiris kiel 40% sur tiu kvizo. Mi tuj malsukcesos tiu klaso. Mi promesas al vi, ke vi ne estas tuj malsukcesos la klaso. Vi tute bone. 

Por tiuj de vi kiu superis Dume, impresa, impona, kiel, serioze bone farita. Mi havas ilin kun mi. Bonvolu veni akiri ilin fine de sekcio. Lasu min scii se vi havas ajnan demandoj, demandojn kun ili. Se ni aldonas vian poentaron erara, sciigu nin. 

Bone, do pset5, tiu estas vere weird semajno por Yale en la senco ke nia pset estas pro Merkredo tagmeze inkluzive Fine tago, do ĝi estas reale teorie pro mardo tagmeze. Probable neniu finis ĉe mardo tagmeze. Tio estas tute bone. Ni tuj devas oficejo horoj ĉinokte krom lundo nokte. Kaj ĉiuj de la sekcioj tiu semajno reale esti igitaj metiejoj, do bonvolu aperigi en ajna sekcio vi volas, kaj ili estos speco de mini-pset laborejoj por helpo pri tio. Do kiel tia, tio estas la nura sekcio kie ni instrumaterialo. Ĉiuj aliaj sekcioj estos koncentranta ekskluzive en helpo por la pset. Yeah? 

Spektantaro: Kie oficejo horoj? 

ANDI PENG: Oficejo horoj tonight-- ho, bona demando. Mi pensas oficejo horoj ĉinokte estas en Teal aŭ ĉe Komunejo. Se vi kontrolu rete CS50 kaj vi iros al oficejo horoj, tie devus esti horaro kiu diras vin kie ĉiuj ili estas. 

Mi scias ĉu ĉi-nokte aŭ morgaŭ estas Teal, kaj mi pensas ke ni povas havi commons por kelkaj noktoj. Mi ne certas. Bona demando. Kontrolu sur CS50. 

Cool, demandojn pri la horaro por la venonta kiel tri tagoj? Mi promesas vin uloj kiel Davido diris, ĉi tiu estas la supro de la monteto. Vi uloj estas preskaŭ tie. Nur tri tagojn. Akiri tie, kaj poste ni ĉiuj venos. Ni havos belan CS-libera paŭzo. Ni revenos. Ni plonĝi en retejo programado kaj disvolviĝo, aferojn, kiuj estas tre amuza kompari al iuj el la aliaj psets. Kaj ĝi estos malvarma, kaj ni havos multa amuza. Ni devos pli dolĉa. Pardonu pro dolĉaĵoj. Mi forgesis dolĉaĵoj. Estis malglata mateno. Do vi infanoj estas preskaŭ tie, kaj mi estas vere fiera pri vi uloj. 

Bone, do stakigas. Kiu amis la demando pri Jack kaj liaj vestoj sur la kvizo? Neniu? Okej, tio estas bone. 

Do esence kiel vi povas bildo Joĉjo, ĉi ulo ĉi tie, amas preni la vesto el la supro de la pilo, kaj li metas ĝin reen sur la pilo post li faris. Do en tiu maniero, li neniam ŝajnas esti akiranta al la fundo de la pilo en sia vesto. Do tiu tipo de Priskribas la baza datumstrukturo de kiel stako estas efektivigita. 

Esence, elpensi pilo kiel ajna stako de objektoj kie meti aferojn sur la supro, kaj tiam vi pop ilin de la supro. Do LIFO estas mallongigo ni ŝatas al use-- Lasta En, Unua Out. Kaj tiel daŭris en la supron de la pilo estas la unua kiu eliras. Kaj do la du terminoj ni ŝatas asocii kun tiel nomataj puŝo kaj popo. Kiam vi puŝi ion sur la pilo, kaj vi pop ĝin reen supren. 

Kaj do versxajne tiu estas speco de abstrakta koncepto por tiuj de vi kiuj volas vidi kiel fakta efektivigo de tiu en la reala mondo. Kiel multaj el vi skribis eseon eble kiel horo antaŭ ĝi ŝuldiĝis, kaj vi hazarde forigita grandega eron de ĝi, kiel hazarde? Kaj tiam kion fari kontrolo ni uzas por meti ĝin reen? Kontrolo-Z, Yeah? Kontrolo-Z, do la kvanton de tempoj ke Kontrolo-Z savis mian vivon, savis mian pugon, ĉiufoje ke estas implementado tra pilo. 

Esence ĉiu informo jen sur via Word dokumento, gets puŝis kaj krevita laŭvole. Kaj tiel esence kiam ajn vi forigi ion, vi pop ĝin reen supren. Kaj tiam se vi bezonas ĝin reen sur, vi puŝi ĝin, kiu estas kion Kontrolo-C faras. Kaj tiel reala mondo funkcio de kiel simpla datumstrukturo povas helpi kun via ĉiutaga vivo. 

Do struct estas la vojo ni fakte krei pilo. Ni tajpu difini struct, kaj tiam ni nomas ĝin stakigi funde. Kaj ene de la stako, ni havos du parametroj ke ni povas esence manipuli, do ni havos char stelo kordoj kapablo. 

Ĉiuj ke ĝi faras kreas tabelon ke ni povas stoki ajn vi volas kion ni povas determini lian kapablon. Kapablo estas nur la max kvanto de erojn ni povas meti en tiun tabelo. int grandeco estas la vendotablo kiu tenas trako de kiom da eroj estas aktuale en la stako. Tial do ni povu kontroli, A, ambaŭ kiom granda la fakta pilo estas, kaj, B, kiom de tiu pilo ni plenigis ĉar ni ne volas superflui super kio nia kapablo estas. 

Do ekzemple, ĉi amindaj demando estis en via kvizo. Esence kio faras nin puŝi sur la supro de stako. Sufiĉe simpla. Se vi rigardas ĝin, ni trairu ĉi. Se [inaudible] size-- memoras, kiam ajn vi deziras aliri ajnan parametro ene struct, vi faru la nomon de la struct.parameter. 

En tiu kazo, s estas la nomo de nia stako. Ni volas aliri la grandeco de ĝi, do ni faru s.size. Do tiel longe kiel la grandeco ne estas egala al kapacito aŭ kiel longe kiel ĝi estas malpli ol kapablo, ĉu laborus tie. 

Vi volas aliri interne de via pilo, do s.strings, kaj vi tuj metis tiun novan numeron ke vi volas enmeti en tie. Ni nur diras ni volas enmeti int n sur la pilo, ni povus fari s.strings, krampoj, s.size egalas n. Pro grandeco estas kie ni nuntempe estas en la stako se ni tuj puŝi ĝin, ni simple aliri kie ajn la grandeco estas, la nuna pleneco de la pilo, kaj ni puŝi la int n sur ĝi. Kaj poste ni volas certigi ke ni ankaŭ pliigante grandecon de la n, tiel ni povas sekvigi ni havas aldonis ekstran aferon al la stako. Nun ni havas pli grandan grandecon. Ĉu ĉi tie sencon ĉiuj, kiel logike funkcias? Estis speco de rapida. Spektantaro: Ĉu vi povas iri super la s.stringss.strings [s.size] denove? ANDI PENG: Certe, do kion faras s.size nuntempe al ni? Spektantaro: Ĝi estas la aktuala grandeco. ANDI PENG: Ekzakte, do la nuna indekso ke nia grandeco estas je, kaj do ni volas meti la nova entjero ke ni volas enmeti en s.size. Ĉu tio havas sencon? Ĉar s.strings, cxiuj estas estas la nomo de la tabelo. Ĉiuj estas estas aliranta la tabelo ene nia struct, kaj do se ni volas meti n en tiun indekson, ni povas simple aliri ĝin uzante krampoj s.size. Malvarmeta. 

Bone, popo, mi _Pseudocode_ ĝin cxar vi uloj, sed simila koncepto. Ĉu tio havas sencon? Se la grandeco estas pli granda ol nulo, tiam vi scias ke vi volas preni ion ĉar se la grandeco ne estas pli granda ol nulo, tiam vi havas nenion en la stako. 

Do vi nur volas ekzekuti tiun kodon, ĝi povas nur pop se estas iu krevi. Do se la grandeco estas pli granda ol 0, ni minus la grandeco. Ni dekremento la grandeco kaj tiam reveni kiom estas ene de ĝi pro per krevanta, ni volas aliro ajn estas stokita en la indekso de la supro de la stako. Ĉio estas ebla solvo? Se mi vin uloj skribi ĉi ekstere, volus vin uloj povos skribi gxin? OK, vi infanoj povas ludi kun ĝi. Neniu ĉagrenoj se vi ne ricevas ĝin. Ni ne havas tempon por programi ĝin hodiaŭ ĉar ni jam akiris multan tiuj strukturoj iri tra, sed esence _pseudocode_, tre, tre simila al peli. Nur sekvi laŭ la logiko. Certiĝu vi konsentas ĉiuj ĉefaĵoj de via struct korekte. Yeah? 

Publiko: Will tiuj diapozitivoj kaj tiu tuta afero esti ĝis hodiaŭ-ish? ANDI PENG: Ĉiam, Yep. Mi tuj provos meti ĉi supre kiel horo post. Mi retmesaĝi David David provos meti ĝin supre kiel horo post tio. 

Bone, do tiam ni moviĝas en tiu alia amindaj datumstrukturo nomata vosto. Kiel vi uloj povas vidi ĉi tie, atendovico, por la britoj inter ni, ĉiuj estas estas linio. Do male al kio vi pensas pilo estas, atendovico estas ekzakte kion logike vi pensas ĝin estas. Ĝi estas tenita fare de la reguloj de FIFO, kiu estas la unua en, Unua Out. Se vi estas la unua unu en la vico, vi estas la unua kiu venas el la linio. 

Do kion ni ŝatas nomi tiun estas dequeueing kaj enqueueing. Se ni volas aldoni ion al nia vosto, ni enqueue. Se ni volas dequeue, aŭ preni io for, ni dequeue. 

Do sama senco ke ni estas speco de kreanta fiksa grandeco elementoj kiujn ni povas stoki iujn aferoj, sed ni ankaŭ povas ŝanĝi kie ni metante parametroj ene de ili bazita sur kio tipo de funcionalidad ni volas. Do stakoj, ni volis la lasta unu, N al esti la unua unu eksteren. Atendovico estas ni volas la unua aĵo en esti la unua afero ekstere. 

Do la struct-tipo difini, kiel vi povas vidi, ĝi estas iomete malsama el kio la stako estis ĉar ne nur ni devas teni trako de kie la grandeco aktuale estas, ni ankaŭ volas konservi trako de la kapo krom kie ni nune estas. Do mi pensas, ke estas pli facile se mi tiros ĉi supre. Do imagu ni hvas atendovico, tiel diru la estro estas ĉi tie. La kapo de la linio, ni nur diru ke estas aktuale tie, kaj ni volas enmeti io en la vico. Mi tuj vokos grandeco esence Estas la sama afero kiel vosto, Fine de kien viaj atendovico estas. Ni nur diras grandeco pravas tie. 

Do kiel faras unu feasibly enmeti ion en atendovico? Kio indekso ni volas meti kie ni volas enmeti en. Se ĉi tiu estas la komenco de via vosto kaj ĉi tiu estas la fino de ĝi aŭ la grandeco de ĝi, kie ni volas aldoni la sekvantan objekton? 

Spektantaro: [inaudible] ANDI PENG: Precize, vi volas aldoni ĝi depende vi skribis ĝin. Ĉu tiu estas blanka aux blanka. Do vi volas aldoni ŝin probable tie ĉar se la grandeco is-- se tiuj estas tute plena, vi volas aldoni ĝin ĉi tie, ĉu ne? 

Kaj tiel tio estas, dum tre, tre simpla, tute ne ĉiam ĝusta ĉar la ĉefa diferenco inter vosto kaj pilo estas ke la vosto povas reale manipulitaj tiel ke la kapo ŝanĝoj depende kie vi volas la komenco de via cue komenci. Kaj kiel rezulto, via vosto Ankaŭ tuj ŝanĝos. Kaj do rigardu tiu kodo nun. Kiel vi uloj ankaŭ demandis al skribi sur la kvizo, enqueue. Eble ni parolos tra kial la respondo estis kio estis. 

Mi ne tute konvenas ĉi linion sur unu, sed esence tio koderon devus esti sur unu linio. Elspezi kiel 30 sekundoj. Rigardu kaj vidu kial tiu estas la vojo kiu estas. 

Tre, tre simila struct, tre, tre similan strukturon kiel la antaÅ­a pilo krom eble unu linio de kodo. Kaj ke unu linio de kodo determinas la funcionalidad. Kaj vere diferencas atendovico de pilo. 

Ĉiu volas preni ponardopiko ĉe klarigante kial vi havas akiris ĉi komplika afero tie ĉi? Ni vidas la revenon de nia mirinda amiko modulo. Kiel vi uloj Baldaŭ venos rekoni en programado, preskaŭ anytime vi bezonas ion volvi ĉirkaŭ io, modulon tuj estos la maniero fari ĝin. Do sciante ke, ĉu iu volas provi klarigi tiun linion de kodo? Jes, ĉiuj respondoj estas akceptita kaj bonvenon. Spektantaro: Ĉu vi parolas al mi? ANDI PENG: Yeah. Publiko: Ho, ne bedaŭras. ANDI PENG: Bone, do ni marŝi tra tiu kodo. Do kiam vi provas aldoni ion sur atendovico, en la bela kazo ke la kapo okazas esti tie, ĝi estas tre facila por ni nur iri al la fino enmeti ion, ĉu ne? Sed la tuta punkto de atendovico estas ke la kapo povas fakte dinamike ŝanĝi dependanta sur kie ni volas la komenco de nia q esti, kaj kiel tia, la vosto Ankaŭ tuj ŝanĝos. 

Kaj do imagi ke tiu ne estis la atendovico, sed prefere tiu estis la vico. Diru la estro estas ĉi tie. Diru nia queue similis tion. Se ni volis movi kie la komenco de la linio estas, diru ni ŝanĝis kapo unuflanken kaj grandecoj tie. 

Nun ni volas aldoni ion al tiu vosto, sed kiel vi uloj povas vidi, ĝi ne estas tiel simpla kiel simple aldonu kiom estas post la grandeco ĉar tiam ni kuras el limojn de nia fakta tabelo. Kie ni volas vere aldonas estas tie. Jen la beleco de atendovico koncernas nin, vide ĝi aspektas kiel la linio iras tiel, sed kiam stokitaj en datumstrukturo, ili doni ĝin kiel kiel ciklo. Ĉio envolvas ĉirkaŭ al la fronto la sama maniero ke linio povas ankaŭ ĉirkaŭfermi ĉirkaŭ depende kie vi volas komenco de la linio esti. Kaj do se ni prenas rigardi malsupren tie, ni diru ni volis krei funkcio nomita enqueue. Ni volis aldoni int n enen ke q. Se q.size q-- ni vokos ke niaj datumoj structure-- se nia queue.size ne egala al kapacito aŭ se ĝi estas malpli ol kapablo, q.strings estas la tabelo ene nia q. Ni tuj starigis ke egalas q.heads, kiu estas dekstre tie, plus q.size modulon per la kapablo, kiun ĉirkaŭfermi nin reen ĉirkaŭ tie. 

Do en tiu ekzemplo, indekso de kapo estas 1, ĉu ne? La indekso de grandeco estas 0, 1, 2, 3, 4. Do ni povas fari 1 plus 4 modulo per nia kapablo kiu estas 5. Kion tio al ni? Kio estas la indico kiu venas el tio? 

Publiko: 0. 

ANDI PENG: 0, kiu hazarde estas ĉi tie, kaj tiel ni volas povi enmeti en ĝuste ĉi tie. Kaj do ĉi tie ekvacio speco de nur funkcias kun ajna nombroj depende kie via kapo kaj via grandeco estas. Se vi scias kion tiuj aferoj, vi scias ĝuste kie vi volas enigi kiom estas post via vico. Ĉu tio havas sencon por ĉiuj? 

Mi konas ia cerba teaser Precipe pro tio venis en la sekvo de via kvizo. Sed espereble ĉiuj nun povas kompreni kial tiu solvo aŭ tiun funkcio estas la maniero ke ĝi estas. Ĉiu iom neklara sur tio? BONE. 

Kaj tial nun, se vi volis dequeue, ĉi estas kie nia kapo estus sxangxigxantaj ĉar se ni devis dequeue, ni ne demetas la fino de la q. Ni volas demeti la kapon, ĉu ne? Do rezulte, kapo tuj ŝanĝos, kaj tial kiam vi enqueue, vi devas sekvigi kie via kapo kaj via grandeco estas povi enŝovi en la ĝusta pozicio. 

Do kiam vi dequeue, Mi ankaŭ _Pseudocode_ ĝin. Bonvolu se vi deziras provu kodigo ĉi ekstere. Vi volas movi la kapon, ĉu ne? Se mi volis dequeue, mi movus la kapon super. Ĉi tiu estus la kapo. 

Kaj nia nuna grandeco volus subtrahi ĉar ni ne plu havas kvar elementoj en la tabelo. Ni nur havas tri, kaj poste ni volas reveni ajn estis stokita interne de la kapo ĉar ni volas preni tiun valoro el tiel tre similaj al la stako. Nur vi prenas el malsama loko, kaj vi havas religi vian montrilon al malsama loko kiel rezulto. Logike, ĉiuj sekvas? Granda. 

Bone, do ni iras por paroli iomete pli en profundo pri ligitaj listoj ĉar ili estos tre, tre valora por vi en la paso de ĉi tiu semajno psets. Ligitaj listoj, kiel vi infanoj povas memori, ili cxiuj, estas nodoj kiuj estas nodoj de certaj valoroj de ambaŭ valoro kaj puntero ke kunligitaj per tiujn punteros. Kaj tial la struct en kiel ni krei nodon tie estas ni havas int n, kiu estas kio ajn la valoron en oni tendencas aŭ ŝnuro n aŭ kion ajn vi volas nomas ĝin, la char stelo n. Struct nodo stelo, kiu estas la montrilon ke vi volas havi en ĉiu nodo, vi tuj havos tiun puntero punkton al proksimaj. Vi havos la kapo de ligillisto tio tuj atentigi al la cetera la valoroj tiel plu kaj tiel plu ĝis eventuale atingi la finon. Kaj ĉi lasta nodo estas nur tuj ne havas puntero. Ĝi tuj celi nula, kaj tio estas kiam vi scias ke vi trafis la fino de via ligitaj listo estas kiam via lasta montrilon ne notas al nenio. 

Do ni tuj iru iom pli en profundo pri kiel oni farus eble serĉu ligillisto. Memoru kion estas iuj de la malavantaĝoj de la ligitaj listoj versoj tabelo pri serĉoj. Tabelo vi povas duuma serĉo, sed kial ne povas vin fari tion en ligillisto? 

Publiko: Ĉar ili ĉiuj konektita, sed vi ne scias precize kie [Inaudible]. 

ANDI PENG: Jes, ĝuste tial memoru ke la brilo de tabelo estis la fakto ke ni devis senvica atingo memoro kie se mi volus la valoro de indekso ses, mi povis nur diri indekso ses, donu al mi tiun valoron. Kaj tio estas ĉar tabeloj estas ordo en apuda spaco de memoro en unu loko, dum speco de ligitaj listoj estas hazarde intermetita ĉie, kaj la sola maniero vi povas trovi unu estas per montrilo ke informas vin la adreso de kie tiu sekva nodo. 

Kaj tiel kiel rezulto, la nura maniero serĉi tra ligillisto estas lineara serĉo. Ĉar mi ne ĝuste scias kie la 12-a valoro en la ligillisto estas, Mi devas kruci la tuteco de tiu ligillisto unu per unu el la kapo al la unua nodo, al la dua vertico, al la tria vertico, tuta vojo malsupren ĝis mi finfine akiras al kie tiu nodo Mi serĉas estas. Kaj tiel en tiu senco, serĉo sur ligillisto estas ĉiam n. Ĉiam n. Ĉiam en lineara tempo. 

Kaj tial la kodo en kiu ni efektivigu tiun, kaj tiu estas iom nova por vi uloj ĉar vi infanoj ne vere parolis aŭ iam vidita punteros en kiel traserĉi punteros, do ni trairu ĉi tre, tre malrapide. Do bool serĉo, dekstra, imagu ni volas krei funkcion nomita serĉo kiu revenas vera se vi trovis valoron ene la ligitaj listo, kaj False alie. Nodo stelo listo estas Nuntempe nur la montrilon al la unua ero en via ligitaj listo. int n estas la valoro kiun vi estas serĉanta en tiu listo. 

Do nodo stelo puntero egalas listo. Tio signifas ke ni opcio kaj kreante montrilon al tiu unua nodo ene de la listo. Ĉiu kun mi? Do se ni devis iri tien, mi havus pravalorizitaj montrilo kiu indikas al la kapo de kio ajn tiu listo estas. 

Kaj tiam unufoje vi akiras ĉi tie, dum montrilon ne egala NULL, tiel ke estas la buklo en kiu ni estas tuj estos poste lauxiris la resto de nia listo pro kio okazas kiam puntero egalas nula? Ni scias ke ni have-- 

Spektantaro: [inaudible] 

ANDI PENG: Ekzakte, do ni scias ke ni atingis la finon de listo, ĉu ne? Se vi iros tien, ĉiu nodo devus esti montrante al alia nodo kaj tiel plu kaj tiel plu ĝis vi batis eventuale la vosto de via ligillisto, kiu havas puntero kiu ĵus ne notas ie alia ol neniu. Kaj tial vi scias ke esence via listo estas ankoraŭ tie supren ĝis montrilon ne egala nulaj ĉar iam ĝi egalas nula, vi scias ke estas nenia pli aĵoj. 

Do kiu estas la buklo en kiu ni estas tuj havos la fakta serĉo. Kaj se la pointer-- ĉu vi vidas tian sagon funkcio ekzistas? Do se puntero punktoj al n, se la montrilo ĉe n egalas egalas n, por ke signifas ke se la puntero kiu vi estas serĉanta sur la fino de ĉiu nodo estas fakte egala al la valoro vi serĉas, tiam Vi volas reveni vera. Do resume, se vi estas ĉe nodo ke havas la valoron, ke vi serĉas, vi scias, ke vi estis povis sukcese serĉu. 

Alie, vi volas agordi vian sagon al la sekva nodo. Tion tiun linion tie faras. Puntero egalas puntero sekva. Cxiu komprenas kiel tio funkcias? 

Kaj esence vi tuj nur kruci la tuteco de la listo, rekomenciganta via puntero ĉiu tempo ĝis vi finfine atingis la finon de la listo. Kaj vi scias, ke ne ekzistas pli nodoj al traserĉi, kaj tiam vi povas reveni falsaj ĉar vi scias ke, ho, nu, se mi povis serĉi tra la tuteco de la listo. Se en ĉi tiu ekzemplo, se mi volus serĉi la valoro de 10, kaj mi komencos je la kapo, kaj Mi traserĉos la vojo malsupren, kaj mi fine atingis tion, kio puntero kiu notas al nula, Mi scias ke, crap, mi supozas 10 Ne en tiu listo ĉar mi ne povis trovi ĝin. Kaj mi estas fine de la listo. Kaj tiaokaze vi scias Mi tuj revenos falsaj. 

Lasu ke trempi en ĉar iomete. Tiu estos bela grava por via pset. La logiko de tio estas tre simpla, eble sintakse ĵus efektiviganta ĝin. Vi infanoj deziras fari certas ke vi komprenos. Malvarmeta. 

OK, do kiel ni estus enmeto nodoj, dekstra, en listo ĉar memori kio estas la kiom da avantaĝoj havi ligillisto kontre tabelo en terminoj de stokado? 

Spektantaro: Ĝi estas dinamika, do ĝi estas pli facile to-- 

ANDI PENG: Precize, do ĝi estas dinamika, kiu signifas ke ĝi povas pligrandigi kaj retiri dependanta sur la uzanto bezonoj. Kaj tiel, en tiu senso, ni ne bezonas malŝpari nenecesa memoro ĉar mi se mi ne scias kiom da valoroj Mi volas al vendejo, ĝi ne havas sencon por mi krei tabelo ĉar se mi volas konservi 10 valoroj kaj mi kreos tabelo de 1.000, jen multajn malŝparita memoro, donitan. Tial ni volas uzi kunligita listo por povi dinamike ŝanĝi aŭ ŝrumpi nia grandeco. 

Kaj tial faras inserción iom pli komplikita. Ĉar ni ne povas aliri hazarde elementoj la vojo, ke ni devus de tabelo. Se mi volas enmeti ero en la sepa indekso, Mi nur povas enmeti ĝin en la sepa indekso. Sur ligillisto, ĝi ne tute labori kiel facile, kaj do se ni volas enmeti la tie en la ligillisto, vide, ĝi estas tre facile vidi. Ni nur volas enmeti ĝin ĝuste tie, ĝuste en la komenco de la listo, dekstra post kapo. 

Sed la maniero en kiu ni havas religi la punteros estas iom malsimpla aŭ, logike, ĝi havas sencon, sed Vi volas certigi ke vi havas ĝin tute malsupren ĉar la lasta afero vi volas estas religi puntero la maniero ke ni faras ĉi tie. Se vi dereference la montrilo de la kapo ĝis 1, tiam subite la resto de via ligitaj listo estas perdita ĉar vi havas ne reale kreis provizoran nenion. Jen montris la 2. Se vi preferas religi la montrilo, tiam la resto de via listo estas tute perdita. Do vi deziras esti tre, zorgoplenaj unue atribui la montrilo el ajn vi volas enmeti en kie ajn vi volas, kaj tiam vi povas dereference la resto de via listo. 

Do ĉi validas por kien vi provas enmeti en. Se vi volas enigi ĉe la kapo, se vi volas respondi tie, se vi volas enmeti en Fine, nu, fine mi divenu vi simple ne havas puntero, sed vi volas certigi ke vi ne perdi la reston de via listo. Vi ĉiam volas certigi via nova nodo notas al kio ajn vi volas enmeti en, kaj tiam vi povas aldoni la ĉenante plu. Ĉiu klara? 

Ĉi tuj estos unu el la veraj temoj. Unu de la plej gravaj aferoj vi tuj havos sur via pset estas ke vi tuj provi krei ligillisto kaj enigaĵo aferoj sed tiam simple perdi la resto de via ligitaj listo. Kaj vi tuj estos kiel mi ne scias kial tio okazas? Kaj ĝi estas doloro trapasi kaj serĉi ĉiun de viaj indikoj. 

Kaj mi garantias vin sur ĉi pset, skribado kaj desegnado tiuj nodoj eksteren estos tre, tre helpema. Do vi povas tute sekvigi de kie ĉiuj viaj indikoj estas, kio okazas erara, kie ĉiuj nodoj estas via, kion vi bezonas fari por aliri aŭ enmeti aŭ forigi aŭ ajna de ili. Ĉiu bona kun tiu? Malvarmeta. 

Do se ni volis rigardi la kodon? Ho, mi ne scias se ni povas vidi the-- Bone, do ĉe la supro ĉiu estas estas funkcio nomita insert kie ni volas enmeti int n en la ligillisto. Ni tuj trairu ĉi. Ĝi estas multe da kodo, multan novan sintakson. Ni estos OK. 

Do supren ĉe la supro, kiam ajn ni volas krei ion kion ni devas fari, Precipe se vi deziras ĝin ne esti stokitaj sur la stako sed en la amaso? Ni iras al malloc, dekstra? Do ni tuj krei puntero. Nodo, montrilo, novaj egaluloj malloc la grandeco de nodo ĉar ni volas ke nodo estu kreita. Ni volas la kvanto de memoro kiu nodo dissxutas esti asignita por la kreo de la nova nodo. 

Kaj tiam ni tuj kontrolu ĉu nova egaluloj egalas nula. Memoru kion ni diris? Kion ajn vi malloc, Kion vi devas ĉiam fari? Vi devas ĉiam kontroli por vidi ĉu aŭ ne ke estas nula. 

Ekzemple, se via mastruma sistemo estis tute plena, se vi jam ne havis memoron ĉe ĉiuj kaj vi provas malloc, revenus nula por vi. Kaj do se vi provas uzi ĝin kiam montrante al nula, vi ne tuj povis aliri tiun informon. Do kiel tia, ni volis fari certas ke kiam ajn vi mallocing, vi ĉiam kontrolas, ĉu tiu memoro, al vi estas nula. Kaj se ĝi ne estas, tiam ni povas movi sur kun la resto de nia kodo. 

Do ni tuj pravalorizi la nova nodo. Ni tuj faros novan n egalas n. Kaj tiam ni tuj faros metis novajn la montrilo sur nova al nula ĉar nun ni ne volas nenion por ŝi atentigi al. Ni ne scias kien ĝi tuj metos vin, kaj tiam se ni volas enmeti ĝin ĉe la kapo, tiam ni povas reassign la sagon al la kapo. Ĉu ĉiuj sekvi la logikon de kie ke okazas? 

Ĉiuj ni faras estas kreante nova nodo, fiksanta la montrilon al nula, kaj tiam reassigning ĝin al la kapo se ni scias ni volas enmeti gxin en la kapo. Kaj tiam la kapo tuj atentigi al tiu nova nodo. Ĉiu OK kun tiu? 

Do estas du-paŝa procezo. Vi devas atribui unua ajn vi kreas. Ŝanĝu ke puntero al la referenci kaj tiam vi povas ia dereference la unua montrilo kaj punkto al la nova nodo. Kie ajn vi volas enigi ĝin, ke logiko tuj teni vera. 

Estas ia kiel asignanta temporal variablo. Memoru, vi havas certigi ke vi ne perdas trakon de se vi interŝanĝante. Vi volas certigi ke vi havas temporal variablo tian tenas trako de kie tiu afero estas stokita por ke vi ne perdas neniun valoron en la kurso de kiel rompado ĉirkaŭe kun ĝi. 

Bone, do kodo estos tie. Vi uloj rigardu post sekcio. Estos tie. 

Do mi supozas kiel faras ĉi diferenciĝas se ni volis enmeti en la mezo aŭ la fino? Ĉu iu havas ideon pri kio estas la _pseudocode_ kiel la logika referenco ke ni prenus se ni volis enmeti ĝin en la mezo? Do se ni volis enmeti ĝin ĉe la kapo, ĉiuj ni faras estas krei nova nodo. Ni starigu la montrilo de tiu nova nodo al kiom la kapo, kaj poste ni almetis la kapon al la nova nodo, ĉu ne? Se ni volis enmeti ĝin en la mezo de la listo, kion ni devas fari? 

Spektantaro: estus ankoraÅ­ esti simila procezo de kiel asignanta puntero kaj tiam asignanta ke puntero, sed ni devus loki tie. 

ANDI PENG: Ekzakte, do precize la sama procezo krom vi devas lokalizi kie ekzakte vi volas ke novaj montrilon al internigi, do se mi volas enmeti en la mezo de ligitaj list-- OK, diru ke estas nia ligillisto. Se ni volas enmeti ĝin ĉi tie, ni iras al krei novan nodon. Ni tuj malloc. Ni tuj kreos novan nodon. Ni tuj asigni la montrilo de tiu nodo tie. 

Sed la problemo kiu diferencas de kie la kapo estas estas ke ni sciis ĝuste kie la kapo estas. Estis ĝuste en la unua, ĉu ne? Sed tie ni devas konservi trako de kie ni enmeto ĝin. Se ni enmeto nia nodo tie, ni havas certigi ke la unu antaŭa al tiu nodo Estas kiu reassigns la montrilo. Tial do vi devas ia sekvigi du aferoj. Se vi konservi trako de kie tiu nodo aktuale estas enmeto en. Vi ankaŭ devas konservi trako de kie la antaŭa nodo ke vi rigardas estis ankaŭ tie. Ĉiu bona kun tiu? BONE. 

Kion pri enmeto en la fino? Se mi volis aldoni ĝin here-- se mi volus aldoni novan nodon al la fino de listo, kiom povus mi iras pri faranta tion? Publiko: Do ​​nuntempe, la lasta onies indikis nula. ANDI PENG: Yeah. Precize, do ĉi tiu aktuale estas pinta scii, kaj do versxajne, en tiu senco, estas tre facile aldoni al la fino de listo. Ĉiuj vi devas fari estas starigis ĝin egala al nula kaj tiam Eksplodo. Dekstre, tre facila. Tre simpla. 

Tre simila al la kapo, sed logike vi volas certigi ke la paŝoj vi prenas al fari ion el tiu, vi sekvajn kune. Estas tre facile, en la mezo de via kodo, akiri kaptita supre sur, ho, mi havas tiom da montriloj. Mi ne scias kie io estas indikante. Mi eĉ ne scias kiu nodo Mi estas sur. Kio okazas? 

Relax, trankviligi, prenu profunda spiro. Eltiru vian ligillisto. Se vi diras, mi scias, kie ĝuste Mi bezonas enmeti ĉi en kaj mi scias precize kiel religi mian punteros, multe, multe pli facile bildigi fjordon multe, multe pli facile ne perdiĝi en la cimoj de via kodo. Ĉiu OK kun tiu? BONE. 

Do mi supozas estas koncepto kiun ni havas ne vere priparolis antaŭ nun, kaj mi supozas ke vi probable ne renkontas multe yet-- ĝi estas speco de progresinta concept-- estas ke ni efektive havas datumojn strukturo nomiĝas duoble ligitaj listo. Do kiel vi uloj povas vidi, ĉiuj ni faras estas kreante fakta valoro, ekstra montrilon sur ĉiu el niaj nodoj kiu ankaŭ notas al la antaŭa nodo. Do ne nur ni havas niajn nodoj atentigi al la venonta unu. Ili ankaŭ indikas la antaŭa. Mi tuj ignori tiujn du nun. 

Sekve vi cxeno kiu povas movi ambaŭ manieroj, kaj tiam ĝi estas iom pli facile al logike sekvi kune. Kiel tie, anstataŭ konservanta trako de, ho, mi devas scii ke ĉi tiu nodo estas kiu mi devos religi, Mi povas nur iri tien kaj nur tiri la antaŭa. Tiam mi scias precize kie tio estas, kaj tiam vi ne devas trairi la tuteco de la ligitaj listo. Estas iom pli facile. 

Sed kiel tiaj, vi havos duoble la kvanto de punteros, jen duobla la kvanto de memoro. Estas multaj indikoj spuri. Estas iom pli kompleksaj, sed estas iom pli uzanto amika depende sur kion vi provas sukcesi. 

Do tiu tipo de datumoj strukturo totalmente ekzistas, kaj la strukturon por estas tre, tre simpla krom ĉiuj vi devi estas, anstataŭ simple montrilo al proksima, vi ankaŭ havas montrilon por antaŭa. Jen ĉio la diferenco estis. Ĉiu bona kun tiu? Malvarmeta. 

Bone, do nun mi estas por vere elspezi probable kiel 15 al 20 minutoj aÅ­ la plejparton de la resto de la tempo en sekcio parolante pri hash tabloj. Kiel multaj el vi infanoj legis pset5 specifon? Bone, bone. Jen altaj ol la 50% de normale. Estas bone. 

Do kiel vi infanoj vidos, vi estas defio en pset5 Estos implementar vortaron kie vi ŝarĝi super 140.000 vortoj ke ni donu al vi kaj literumilo ĝin kontraŭ la tuta de la teksto. Ni donos al vi hazarda pecoj de literaturo. Ni donos al vi La Odiseado. Ni donos al vi La Iliado. Ni donos al vi Austin Powers. 

Kaj via defio Estos por literumilo ĉiu unuopa vorto en ĉiu de tiuj vortaroj esence kun niaj literumilo. Kaj tiel ekzistas kelkaj partoj krei ĉi pset, unue vi volas esti povis reale ŝarĝi ĉiuj vortoj en vian vortaro, kaj tiam vi deziras povi literumilo ĉiuj ili. Kaj tiel kiel tiaj, vi tuj postuli datumstrukturo kiu povas fari tion rapide kaj kompetente kaj dinamike. 

Do mi supozas la plej facila maniero fari tion, vi verŝajne krei tabelon, dekstra? La plej facila maniero de stokado estas vi povas krei tabelon de 140.000 vortoj kaj simple meti ilin ĉiuj tie kaj tiam kruci ilin per duuma serĉo aŭ por selektadoj aŭ not-- bedaŭras ke estas ordigado. Vi povas ordigi ilin kaj tiam kruci ilin per duuma serĉo aŭ nur lineara serĉo kaj nur finaj vortoj, sed ke prenas grandegan kvanton da memoro, kaj ĝi ne estas tre efika. 

Kaj tial ni tuj komencos parolas pri manieroj de farado nia rultempo pli efika. Kaj nia celo estas atingi konstanta tempo kie Estas preskaŭ kiel sensilo, kie vi havos tujan aliron. Se mi volis serĉi ion, Mi volas povi ĝuste, eksplodo, trovas ĝin ĝuste, kaj tiri ĝin ekstere. Kaj tiel strukturo en kiu ni estos igante tre proksima por povi aliri konstanta tempo, tiu sankta grail en programado de konstanta tempo nomata hash tablo. Kaj David antaŭe menciita la [Inaudible] iomete en prelego, sed ni tuj vere plonĝo en profunda tiu semajno sur peco kiu estas rilate kiom hash tablo funkcias. 

Do la vojo ke hash tablo verkoj, ekzemple, se mi volis konservi aron da vortoj, faskon da vortoj en la angla lingvo, Mi povus teorie metis banano, pomo, kivo, tenilo, paro, kaj melono ĉiuj sur nur tabelo. Cxiuj povis havi en kaj esti trovi. Estus speco de doloro serĉu tra kaj aliro, sed la facila maniero fari tiun estas ke ni povas krei fakte strukturo nomata hash tablo kie nin hash. Ni kuras ĉiujn de niaj klavoj tra hash funkcio, ekvacio, kiu igas ilin ĉiujn en ia valoro ke poste ni povos stoki sur esence tabelo de ligillisto. 

Kaj do ĉi tie, se ni volis stoki anglaj vortoj, ni povis potenciale simple, mi ne faras scias, turni ĉiujn unua literoj en ia nombro. Do, ekzemple, se mi volus A esti sinonimo apple-- aŭ kun la indico de 0, kaj B esti sinonima kun 1, ni povas havi 26 eniroj kiu povas nur stoki ĉiuj leteroj de la alfabeto kiu ni komencos kun. Kaj tiam ni povas havi pomo je la indekso de 0. Ni povas havi banano ĉe la indico de 1, melono ĉe la indico de 2, kaj tiel plu kaj tiel antaŭen. Kaj tiel, se mi volis serĉi miaj hash tablo kaj aliro pomo, Mi scias pomon komenciĝas per A, kaj mi scias precize ke ĝi devas esti kaj la hash tablo ĉe indekso 0 ĉar de la funkcio antaŭe asignita. 

Do mi ne scias, ni uzanto programo kie vi estos akuzita arbitrarily-- ne arbitre, kun provanta pensoplene elpensi bonan ekvacioj povi disvastigi el ĉiuj viaj valoroj en maniero ili povas facile aliri ĝin poste kun kiel ekvacio ke vi mem scias. Do en tiu senco, se mi volis iri al mango, mi scias, ho, ĝi komenciĝas kun m. Devas esti ĉe la indico de 12. Mi ne devas traserĉi nenion. Mi scias exactly-- mi povus nur iri al la indekso de 12 kaj tiri ke ekstere. 

Ĉiu klara pri kiel oni hash tablo funkcio laboras? Estas speco de nur pli kompleksa tabelo. Jen ĉio estas. BONE. 

Do mi supozas ke ni renkontas tiu demando de kio okazas se vi havas plurajn aferojn kiuj donas vin la sama indico? Do diru nia funkcio, ĉiuj ĝi faris estis preni tiun unuan literon kaj turni kiuj en respektiva 0 tra 25 indekso. Tio estas tute bone se vi nur havas unu de ĉiu. Sed la dua vi komencas havante pli, vi estas tuj havas kio nomiĝas kolizio. 

Do se mi provas enmeti enterigi en hash tablo kiu jam havas bananon sur ĝi, kio okazos kiam vi provas enmeti tio? Malbonaj aferoj ĉar banano jam ekzistas ene de la indekso ke vi volas konservi ĝin en. Bero ia similas, ha, kion mi faru? Mi ne scias kien iri. Kiel mi solvi ĉi? 

Do vi infanoj volas ia vidu ni faros ĉi delikata afero Kie ni povas ia reale krei ligillisto en niaj tabeloj. Kaj do la plej facila vojo pensi pri tio, ĉiuj hash tablo estas tabelo de ligitaj listoj. Kaj tiel, en tiu senco, vi devos tiu bela tabelo de punteros, kaj tiam ĉiu montrilon en ke valoro, en tiu indekso, povas fakte indiki al aliaj aferoj. Kaj tial vi havas ĉiujn tiujn apartajn ĉenoj elspezi de unu granda tabelo. 

Kaj do ĉi tie, se mi volis enmeti bero, Mi scias, OK, mi tuj enigo ĝin tra mia hash funkcio. Mi tuj finos kun la indico de 1, kaj tiam mi tuj povos havi nur malgrandan subaron de tiu giganto 140.000-vorto vortaro. Kaj tiam mi povas nur rigardi tra 1/26 de tiu. 

Kaj tiel do mi povas simple enŝovi bero aŭ antaŭ aŭ post banano en tiu kazo? Post, dekstra? Kaj do vi tuj volas enmeti ĉi nodo post banano, kaj tiel vi tuj enmeti ĉe la vosto de tiu ligillisto. Mi tuj iros reen al tiu antaŭa glitejo, do vi uloj povas vidi kiel hash funkcio laboras. 

Do krada funkcio estas tiu ekvacio ke vi uzas specon de via enigo tra akiri ajn indekso vi volas atribui al ĝi. Kaj tiel, en tiu ekzemplo, ĉiuj ni volis fari estis preni la unua litero, igi tiun en indekso, tiam ni povas stoki ke en nia hash funkcio. Ĉiuj ni faras ĉi tie estas ni konvertanta la unua litero. Do keykey [0] estas nur la unua litero sendistinge kordoj ni havas, ni pasante en. Ni konvertas ke al supra, kaj ni forprenante per majuskla A, do ĉiuj kiuj faras donas al ni kelkajn en kiu ni povas hash niajn valorojn sur. 

Kaj tiam ni tuj reveni hash modulo grandeco. Estu tre, tre zorgema ĉar, teorie, tie via hash valoro povis esti malfinio. Ĝi povus simple daŭrigi kaj sur kaj sur. Ĝi povus esti kelkaj vere, vere granda valoro, sed ĉar via hash tablo ke vi kreis nur havas 26 indeksas, Vi volas certigi vian modulusing por ke vi ne run-- ĝi estas la sama aĵo kiel via queue-- por ke vi ne kuras ekstere la fundo de via hash funkcio. 

Vi volas enpaki ĝin ĉirkaŭ sammaniere en [inaudible] kiam vi havis kiel tre, tre grandan leteron, vi ne volis ke al nur kuri for la fino. Sama afero ĉi tie, vi volas certigi ĝi ne kuras for la fino envolviendo ĉirkaŭ la supro de la tablo. Do tio estas nur tre simpla hash funkcio. Ĉiuj kiuj faris estis preni la unuan letero de whatever niaj enigo estis kaj turni kiuj en indico kiu Ni povus meti en niajn hash tablo. 

Yeah, kaj tiel kiel mi diris antaŭe, la vojo, ke ni solvi kolizioj en nia hash tabloj estas havanta, kion ni nomas, ĉenante. Do se vi provas enmeti plurajn vortoj kiuj komenciĝas kun la sama afero, vi tuj havos unu hash valoro. Aguacates kaj pomon, se vi havas ruli ĝin per nia hash funkcio, tuj donos al vi la sama nombro, la nombro de 0. Kaj tial la maniero kiun ni decidu, ke estas ke ni povas efektive ia ligas ilin kune tra ligitaj listoj. 

Kaj tiel en tiu senco, vi uloj povas vidi specon de kiel datumstrukturoj ke ni estis fiksanta antaŭe kiel sekvinberoj ligillisto speco de povas kunvenos. Kaj tiam vi povas krei multe pli efika datumstrukturoj kiu povas manipuli grandajn kvantojn de datumoj, kiuj dinamike regrandigi depende sur viaj bezonoj. Ĉiu klara? Ĉiu speco de klara kio okazas ĉi tie? 

Se mi volis insert-- kio estas frukto kiu komenciĝas per, mi ne scias, B, aliaj ol bero, banano. 

Publiko: Blackberry. 

ANDI PENG: Blackberry, rubuso. Kie rubusbero iras tien? Nu, ni fakte ne ordo ĉi ankoraŭ, sed teorie se ni volus havi tiun en alfabeta ordo, kie devus BlackBerry iras? 

Spektantaro: [inaudible] 

ANDI PENG: Precize, post ĉi tie, ĉu ne? Sed ĉar ĝi estas tre malfacile reorder-- Mi supozas lin tuŝas al vi uloj. Vi uloj povas tute apliki kion vi volas. La pli efika maniero fari tion eble estus ordigi vian ligitaj listo en alfabeta ordo, kaj do kiam vi estas enmeto aferoj, vi volas certi enigi ilin en alfabeta ordo por ke poste kiam vi estas provas serĉi ilin, vi ne devas trairi ĉiu. Vi scias precize kie ĝi estas, kaj ĝi estas pli facila. 

Sed se vi ia havas aferojn intermetita hazarde, vi ankoraŭ havos al _traverse_ ĝi anyways. Kaj do se mi volis nur enmeti rubusbero tie kaj mi volis serĉi ĝi, mi scias, ho, rubusbero devas komenci kun la indico de 1, do mi scias instantáneamente nur serĉu ĉe 1. Kaj tiam mi povas ia kruci la ligillisto ĝis mi alvenas al BlackBerry, kaj then-- yeah? 

Publiko: Se vi provas create-- Mi supozas kiel ĉi estas tre simpla hash funkcio. Kaj se ni volis fari multoblaj tavoloj de tiu kiel, OK, ni volas apartigi en kiel ĉiuj alfabeta literoj kaj tiam denove ŝati alia aro de alfabeta literoj ene de tiu, ni metante kiel hash tablo ene hash tablo, aŭ kiel funkcio ene funkcio? Aŭ estas that-- 

ANDI PENG: Do via hash function-- via hash tablo povas esti kiel granda kiel vi deziras ĝin. Do en tiu senco, mi pensis gxi estas tre facila, tre simpla por mi nur ia bazita sur literoj de la unua vorto. Do ekzistas nur 26 eblojn. Mi povas nur akiri 26 ebloj de 0 ĝis 25 ĉar ili povas nur komenci de A ĝis Z. Sed Se vi volis aldoni, eble, pli komplekseco aŭ rapida kuri tempo por via hash tablo, vi absolute povas fari ĉiajn aferojn. Vi povas fari vian propran ekvacio kiu donas pli dissendo en via vortoj, tiam kiam vi serĉi, ĝi tuj estos pli rapida. 

Ĝi estas tute ĝis vi infanoj kiom vi volas apliki tion. Pensu pri ĝi kiel ĵus siteloj. Se mi volus havi 26 siteloj, mi tuj ordigi aferojn en tiuj siteloj. Sed mi tuj havas faskon de aĵoj en ĉiu sitelo do se vi volas fari ĝin rapida kaj pli efika, mi havas cent sitelojn. 

Sed tiam vi devas eltrovi maniero ordigi aferojn tiel ke ili estas en la konvena sitelo ili devus esti en. Sed tiam kiam vi efektive volas rigardi ke sitelo ĝi estas multe pli rapida ĉar tie estas malpli havajxoj en ĉiu sitelo. Do, jes, tio estas vere la lertaĵo por vi uloj en pset5 estas ke vi estos defiita simple krei kiom estas la plej efika funkcio povas pensi ke povi stoki kaj kontroli tiujn valorojn. 

Tute supren al vi infanoj tamen vi volas fari ĝin, sed tio estas vere bona punkto. Ke tia logiko vi volas komenci pensi pri estas, nu, kial ne mi faras pli siteloj. Kaj tiam mi devos serĉi malpli aĵoj, kaj tiam eble mi havas malsaman hash funkcio. 

Jes, ekzistas multe da manieroj fari tion pset, iuj estas pli rapida ol aliaj. Mi tute tuj ĝuste vidi kiel rapida estis la plej rapida vi infanoj estos povos akiri vian funkciojn labori. OK, ĉiuj bone sur ĉeni kaj hash tabloj? Ĝi estas fakte kiel tre simpla koncepto se vi pensas pri ĝi. Ĉiuj estas estas disigante ajn viaj enigoj estas en siteloj, ordigado de ili, tiam serĉanta la listas ke estas asociita kun. 

Malvarmeta. Bone, nun ni havas malsaman specon de datuma strukturo kiu nomiĝas arbo. Ni plu iru kaj parolu pri tries kiuj estas klare malsamaj, sed en la sama kategorio. Esence, ĉiu arbo estas anstataŭe organizi datumojn en la maniero lineal ke hash tablo does-- vi Sciu, ĝi estas atingis supro kaj fundo kaj tiam vi ia ligi ekstere de it-- a arbo havas maksimuman kiun vi nomas la radiko, kaj tiam ĝi havas foliojn tute ĉirkaŭ ĝi. 

Kaj do ĉiuj vi havas ĉi tie estas nur la pinta nodo kiu notas al aliaj nodoj, kiuj punktoj al pli nodoj, kaj tiel plu kaj tiel antaŭen. Kaj tial vi nur devas forkiĝanta branĉoj. Estas nur alia maniero de organizado datumoj, kaj ĉar ni nomas ĝin arbo, vi uloj just-- estas nur modelita eksteren rigardi kiel arbo. Tial ni nomas ĝin arboj. 

Hash tablo aspektas kiel tablo. Arbo nur aspektas kiel arbo. Ĉiuj estas estas aparta maniero organizi nodoj Dependanta sur kio viaj bezonoj estas. 

Do vi havas radikon kaj tiam vi havas foliojn. La maniero kiun ni povas aparte pensi pri ĝi estas duuma arbo, duuma arbo estas nur specifa tipo de arbo kie ĉiu nodo nur punktoj al, je maks, du aliaj nodoj. Kaj do jen vi havas distingan simetrio en via arbo ke faciligante ia rigardu ĉe kio aprezas vi estas ĉar tiam vi havas ĉiam maldekstran aŭ dekstren. Ekzistas neniam kiel maldekstra tria el maldekstren aŭ kvarono de la maldekstro. Ĝi estas nur vi havas maldekstra kaj dekstra kaj vi povas serĉi aŭ de tiuj du. Kaj do kial estas tiu utila? La maniero ke tiu estas utila estas se vi serĉas serĉi tra valoroj, dekstra? Prefere ol efektivigado duuma serĉu en eraro tabelo, se vi volis povi enigi nodoj kaj forigos nodoj ĉe volo kaj ankaŭ konservi la serĉo kapabloj de duuma serĉo. Do tiamaniere, ni estas speco de tricking-- memoras kiam ni diris ligitaj listoj ne povas duuma serĉo? Ni ia kreante datumstrukturo ke lertaĵoj ke en laboranta. 

Kaj tiel ĉar ligitaj listoj estas linearaj, ili nur ligas unu post la alia. Ni povas ia havas Alispeca punteros ke punkto al malsamaj nodoj kiu povas helpi nin per serĉo. Kaj do ĉi tie, se mi volus havas duuma serĉo arbo, Mi scias ke miaj mezo se 55. Mi simple tuj krei ke kiel mia mezo, kiel mia radiko, kaj tiam mi iros al havi valoroj spin off de ĝi. 

Do jen, se mi iros por serĉi la valoro de 66, mi povas komenci ĉe 55. Estas 66 pli granda ol 55? Jes ĝi estas, do mi scias mi mus serĉu I n la dekstra montrilo de tiu arbo. Mi iros al 77. OK, estas 66 malpli ol aŭ pli granda ol 77? Ĝi estas malpli ol, tiel vi scias, ho, kiu devas esti la maldekstra nodo. 

Do jen ni estas speco de konservado ĉiuj la grandaj aferoj pri arrays, tiel kiel dinamika regrandigo de objektoj, estante povos enmeti kaj forigi laŭvole, sen devi maltrankviligi la fiksa kvanto de spaco. Ni ankoraŭ konservas ĉiujn tiujn mirindaĵojn dum ankaŭ povante konservi la ensaluti kaj serĉu tempo de duuma serĉo ke ni nur antaŭe kapabla akiri frazo. 

Cool datumstrukturo, ia kompleksa implementar, la nodo. Kiel vi povas vidi, ĉiuj ĝi estas la struct de la nodo estas ke vi havas maldekstre kaj dekstra montrilo. Jen ĉio estas. Do anstataŭ nur havanta x aŭ antaŭan. Vi havas maldekstra aŭ dekstra, kaj tiam vi povas ia ligas ilin kune tamen vi tiel elektos. 

OK, Ni efektive tuj nur preni kelkajn minutojn. Do ni tuj iru tien. Kiel mi diris antaŭe, Mi specon de klarigis la logiko malantaŭ kiel ni estus traserĉi ĉi. Ni tuj provos pseudocoding ĉi ekstere al vidi se ni povas ia apliki la sama logiko de binara serĉo al malsama tipo de datumstrukturo. Se vi infanoj volas preni kiel paro Minutoj ĵus pensas pri tiu. BONE. Bone, mi tuj efektive nur donas vin the-- ne, ni parolos pri la _pseudocode_ unue. Do ĉu iu volas doni ponardopiko ĉe kio la unua afero vi deziras fari kiam vi elkomencanta serĉado estas? Se ni serĉas la valoro de 66, kio estas ni unue volas fari se ni volas duuma serĉo ĉi arbo? 

Spektantaro: Vi volas rigardi dekstra kaj rigardu maldekstren kaj vidu [inaudible] pli granda nombro. 

ANDI PENG: Jes, ĝuste. Do vi tuj rigardi vian radikon. Ekzistas multaj manieroj vi povas nomi ĝin, via patro nodo homoj diras. Mi ŝatas diri radiko ĉar jen kiel la radiko de la arbo. Vi tuj rigardi via radika vertico, kaj vi estas tuj vidos estas 66 grandaj ol aŭ malpli ol 55. Kaj se ĝi estas pli granda ol, nu, tio estas granda ol, kie ni volas rigardi? Kie ni volas serĉi nun, ĉu ne? Ni volas serĉi dekstra duono de tiu arbo. 

Do ni havas, oportune, a puntero kiu notas al la dekstra. Kaj tiel do ni povas fiksi nia nova radiko esti 77. Ni povas nur iri al kie ajn la puntero estas indikante. Nu, ho, tie ni startanta ĉe 77, kaj ni povas nur fari tion rekursie denove kaj denove. Tiamaniere, vi afabla de havi funkcion. Vi havas vojon de serĉado ke vi povas nur ripeti denove kaj denove kaj denove, Dependanta sur kie vi volas rigardi ĝis vi fine atingos la valoro ke vi estas serĉanta. Sencon? 

Mi volis montri al vi la fakta kodo, kaj ĝi estas multe da kodo. Ne necesas Freak Out. Ni parolos tra ĝi. 

Efektive, ne. Tiu estis nur _pseudocode_. OK, ke estis nur la _pseudocode_, kio estas iom kompleksa, sed estas tute bone. Ĉiu sekvanta kune tie? Se la radiko estas nula, reveno falsa pro tiu rimedo vi eĉ ne havas tie ion. 

Se radiko n estas la valoro, tial se ĝi hazarde estas la unu vi rigardas, tiam vi tuj reveni vera ĉar vi scias ke vi trovis ĝin. Sed se la valoro estas malpli ol radiko de n, vi estas tuj serĉu maldekstre infano aŭ la maldekstra folio, kion ajn vi volas nomi ĝin. Se la valoro estas pli granda ol radiko, vi tuj serĉu la dekstra arbo, tiam nur ruli la funkcio tra serĉo denove. 

Se radiko estas nula, ke tiu signifas vi atingis la finon? Tio signifas ke vi ne havas pli pli folioj esplori, tiam sciu, ho, mi supozas ke ne tien ĉar post mi rigardis tra la tuta afero kaj ĝi ne estas tie ĉi, ĝi simple ne povus esti ĉi tie. 

Ĉu tio havas sencon por ĉiuj? Do estas kiel duuma serĉo konservante la kapabloj de ligitaj listoj. Cool, kaj tiel la dua tipo de datumstrukturo vi infanoj povas provi efektiviganta vian pset, Vi nur devas elekti unu metodo. Sed eble alternativa metodo al la hash tablo estas kion ni nomas trie. 

Ĉiuj trie estas estas specifa tipo de arbo kiun havas valorojn kiuj iras al aliaj valoroj. Do anstataŭ havi binaran arbo en la senco, ke nur unu afero povas celi du, vi povas havi unu aferon punkto al multaj, multaj aĵoj. Vi esence havas arrays ene de kiu vi stoki punteros ke indikas aliaj tabeloj. 

Do la nodo de kiel ni difinus trie Estas ni volas havi Buleaj, c vorto, ĉu ne? Do la nodo estas Bulea kiel vera aŭ falsa, Unue ĉe la kapo de ke tabelo estas la jena vorto? Due, vi volas havi punteros al kiom la resto de ili estas. Iom komplika, iom abstrakta, sed Mi klarigos kion tio ĉiuj rimedoj. 

Do jen, supre, se vi havas tabelo deklaris jam, nodo kie vi havas Bulea valoro stokita en la fronto kiu diras vin estas tiu vorto? Ĉu tio ne estas vorto? Kaj tiam vi havas la resto de via tabelo ke fakte stokas ĉiujn ebloj de kio povis esti. Do, ekzemple, kiel ĉe la supro vi havas la unua kiu diras veraj aŭ falsa, jes aŭ ne, ĉi tiu estas vorto. 

Kaj tiam vi havas 0 tra 26 de la literoj, ke vi povas stoki. Se mi volis serĉi tie por vesperto, mi iras al la supro kaj mi serĉos B. mi trovas B en mia tabelo, do mi scias, OK, estas B vorton? B ne estas vorto, do tiel Mi devas teni serĉanta. Mi iras de B, kaj mi rigardas al la montrilo ke B notas al kaj mi vidas alian aron de informoj, la sama strukturo kiun ni havis antaŭe. 

Kaj here-- ho, la sekva letero en [inaudible] estas A. Do ni rigardu en tiu tabelo. Ni trovas la oka valoro, kaj tiam ni rigardu vidi, ho, hey, estas ke vorto, estas B-Al unu vorton? Ĝi ne estas vorto. Ni devas teni rigardante. 

Kaj tiel do oni konsideras kie la montrilon de A punktoj, kaj ĝi notas al alia maniero en kion ni havas pli valoro stokita. Kaj fine, ni atingos B-Al-T, kiu estas vorto. Do la sekvanta tempo vi aspektas, vi tuj havi tiun ĉeko de, jes, ĉi Bulea funkcio estas vera. Kaj tiel en la senco ni estas speco havi arbon kun tabeloj. 

Tial do vi povas ia serĉu suben. Anstataŭ hashing funkcio kaj asignanta valorojn per ligillisto, Vi povas simple apliki trie ke sercxojn downwords. Vere, vere komplikitaj aĵoj. Ne facilas pensi ĉar mi ŝatas kracxi tiel multaj datumstrukturoj el ĉe vi, sed faras ĉiu tipon de kompreni kiel la logiko de tio funkcias? 

Bone, mojose. Do B-Al-T, kaj tiam vi tuj serĉu. La venontan fojon vi tuj vidi, ho, hej, ĝi estas vera, tiele mi konas ĉi devas esti vorto. 

Sama afero por zoo. Do jen la afero nun, se ni volis serĉi bestoĝardeno, nun, aktuale bestoĝardeno ne estas vorto en nia vortaro ĉar, kiel vi infanoj povas vidi, la unua loko kiun ni havas Bulea reveni vera estas fine de zoom. Ni havas Z-ho-ho-M. 

Kaj do ĉi tie, ni ne vere havas la vorto, zoo, en nia vortaro ĉar tiu markobutono ne estas markita. Do la komputilo ne scias ke bestoĝardeno estas vorto ĉar la vojo kiun ni stokita, nur zoom tie efektive havas Bulea valoro ke tio estis turnita vera. Do se ni volas enmeti la vorto: zoo, en nia vortaro, Kiel ni iras pri faranta tion? Kion ni devas fari por certigi nian komputilo scias ke Z-ho-ho estas vorto kaj ne la unua vorto estas Z-ho-ho-M? 

Spektantaro: [inaudible] 

ANDI PENG: Ĝuste, ni volas certigi ke ĉi tie, ke Bulea valoro estas kontrolis ekstere ke ĝi estas vera. Z-ho-ho, tiam ni tuj kontroli tion, tial ni scias precize, hej, bestoĝardeno estas vorto. Mi tuj rakontos la komputilo ke ĝi estas vorto tiom ke kiam la komputilo ĉekojn, ĝi scias ke bestoĝardeno estas vorto. 

Ĉar memori ĉiuj ĉi tiuj datumoj strukturoj, ĝi estas tre facila por ni diri, ho, vesperto estas vorto. Zooparko estas vorto. Zoom estas vorto. Sed kiam vi konstruado ĝi, la komputilo havas nenian ideon. 

Do vi devas diri ĝin precize en kio punkto estas tiu vorto? Ĉe kiu punkto ĝi estas ne unu vorton? Alian punkton mi bezonas serĉi aferojn, kaj en kio punkto mi devas nun iri? Ĉiu klara de tiu? Malvarmeta. 

Kaj tiel do venas la problemo de kiel estus ni iri pri enmeto ion ke fakte ne ekzistas? Do ni nur diros ni volas enmeti la vorto, bano, en nian trie. Kiel vi uloj povas vidi kiel nuntempe ĉiuj ni havas nun estas B-Al-T, kaj tiu nova datumstrukturo tie havis pint ke montris nula ĉar ni supozas ke, ho, ekzistas neniu vortoj post B-Al-T, kial ni devas teni havanta aferojn post ke T. 

Sed la problemo ekestas se ni faras vin deziras havi vorton kiu venas post la T. Se vi havas banon, vi estas tuj volas H pravas. Kaj tiel la vojon ni tuj faros kiu estas ni tuj krei apartan nodon. Ni ne allot ajn kvanto de memoro por tiu nova tabelo, kaj ni tuj reassign punteros. 

Ni tuj asigni la H, Unue, tiu nula, ni tuj forigi. Ni tuj devas la H punkto suben. Se ni vidas H, ni volas ĝin iri al ie alia. 

En tie, ni povas tiam kontroli ekstere jes. Se ni batis H post la T, ho, tiam ni scias ke tiu estas vorto. La Buleaj tuj reveni vera. Ĉiu klara de kiel tio okazis? BONE. 

Do esence, ĉiuj tiuj datumstrukturoj ke ni trapasis hodiaŭ, mi havas trairinte ilin vere, vere rapide kaj ne en multa detalo, kaj tio estas okej. Unufoje vi komencas rompado kun ĝi, Vi estos konservanta trako de kie ĉiuj punteros estas, kio okazas en via datumstrukturoj, kaj tiel plu. Ili estos tre utilaj, kaj ĝi estas ĝis vi guys tute elkompreni kiel vi volas apliki aferojn. 

Kaj tiel pset4, de 5-- ho, tio estas erara. Pset5 estas fuŝo. Kiel mi diris antaŭe, vi tuj, fojo denove, elŝuti fontkodon de ni. Tie tuj estos tri ĉefaj aferoj vi estos elŝuto. Vi elŝuti vortarojn, KERS, kaj tekstoj. 

Ĉiuj tiuj aferoj estas estas ĉu vortarojn de vortoj ke ni volas ke vi kontrolu aŭ testo de informo ke ni deziras vin literumilo. Kaj tial la vortaroj Ni donas vin iras doni vin precizaj vortoj, ke ni volas vi stoki iel en maniero kiu estas pli efika ol tabelo. Kaj tiam la tekstoj estas tuj estos kio ni estas demandante vin literumi kontroli por certiĝi ĉiuj vortoj estas veraj vortoj. 

Kaj tiel la tri blokoj de programoj kiuj ni donos al vi nomas dictionary.c, dictionary.h kaj speller.c. Kaj tial ĉiuj dictionary.c faras estas kion vi demandis apliki. Ĝi ŝarĝas vortoj. Ĝi literumi ĉekojn ilin, kaj ĝi certigas ke ĉio estas enigita konvene. 

diction.h estas nur biblioteko dosiero kiu deklaras ĉiuj tiuj funkcioj. Kaj speller.c, ni tuj donas vin. Vi ne bezonas modifi iuj ĝi. Ĉiuj speller.c faras estas preni tiun, ŝarĝoj, kontrolas la rapidon de ĝi, testas la etalono de kiel kiom rapide vi povos fari aferojn. 

Estas literumanto. Nur ne salaton kun ĝi, Sed faro certe vin komprenas kion ĝi faras. Ni uzi funkcio nomita getrusage ke testas la rendimenton de via sorĉas kontrolilo. Ĉiuj faras estas esence testi la tempo de ĉio en via vortaro, Tiel faro certe vi komprenas. Penu ne salaton kun ĝi aŭ alia aĵoj ne kuras konvene. 

Kaj la plejparton de tiu defio estas por you guys vere modifi dictionary.c. Ni tuj donos al vi 140.000 vortojn en vortaro. Ni tuj donos al vi tekston dosieron kiu havas tiujn vortojn, kaj ni volas ke vi povos organizi ilin en hash tablo aŭ trie ĉar kiam ni petas vin literumi check-- imagi se vi estas sorĉo kontrolanta kiel Homero Odiseado. Estas kiel tiu grandega, grandega provo. 

Imagu se ĉiu unuopa vorto vi devis serĉi tra tabelo de 140.000 valoroj. Kiu portus ĉiam por via maŝino kuri. Tial ni volas organizi niajn datumojn en pli efika datumstrukturoj kiel hash tablo aŭ trie. Kaj tiam vi uloj povas ia de kiam vi serĉu aliro aferojn pli facile kaj pli rapide. 

Kaj do atentu solvi kolizioj. Vi tuj ricevos multajn vortoj de kiuj komenciĝas je A. Vi tuj ricevos multajn vortojn ke komenco kun B. Ĝis vi uloj kiel vi volas solvi ĝin. Eble ekzistas pli efika hash funkcio ol nur la unua litero de io, kaj tiel ke estas ĝis vi uloj al speco de fari kion vi volas. 

Eble vi deziras aldoni ĉiuj literoj kune. Eble vi volas ŝatas fari strangajn aferojn ĝi rakontas la nombro de literoj, ajn. Ĝis vi uloj kiel vi volas fari. Se vi volas fari hash tablo, se vi volas provi trie, tute dependas de vi. Mi avertas vin antaŭ tempo ke la trie estas tipe iom pli malfacila nur ĉar ekzistas multe pli punteros spuri. Sed tute dependas de vi uloj. Estas multe pli efika en plej kazoj. Vi volas vere esti kapabla teni trako de ĉiuj viaj indikoj. Kiel fari la saman aferon ke mi estis faranta tie. Kiam vi provas enmeti valorojn en hash tablo aŭ forviŝi, certiĝu ke vi estas vere konservanta trako de kie ĉiu estas ĉar ĝi estas vere facila por se mi provas enmeti kiel la vorto, andy. Ni nur diras, ke estas reala vorto, la vorto, andy, en giganta listo de A vortojn. 

Se mi nur hazarde reassign montrilo malĝusta, oops, tie iras la tuteco de la resto de mia ligillisto. Nun la nura vorto mi havas estas andy, kaj nun ĉiuj la aliaj vortoj en la vortaro perdiĝis. Kaj do vi deziras fari certe vin sekvigi ĉiuj viaj indikoj aŭ alie vi ricevos grandegaj problemoj en via kodo. Desegni aferojn zorge paŝon post paŝo. Ĝi faras ĝin tre pli facila elpensi. 

Kaj fine, vi volas povi testi vian rendimenton de via programo sur la granda tabulo. Se vi infanoj prenas rigardas CS50 nun, ni havos kion nomas la granda tabulo. Estas la partituro folio de la plej rapida literumi kontrolanta fojojn tra ĉiuj de CS50 Ĝuste nun, mi kredas ke la supro kiel 10 tempoj mi pensas ok de ili estas bastono. Ni vere volas vin infanoj bati nin. 

Ni ĉiuj provis implementar la plej rapidan kodon kiel ebla. Ni volas vin infanoj provi defii ni kaj efektivigi pli rapide ol ni ĉiuj povas. Kaj tiel tio estas vere la unua tempo ke ni estas demandante vin infanoj fari pset ke vi povas vere fari en ajn metodo vi volas. 

Mi ĉiam diras, tiu estas pli parenca al reala-vivo solvo, ĉu ne? Mi diras, hey, mi bezonas vin por fari tion. Konstruu programo kiu faras tion por mi. Ĉu ĝi tamen vi volas. Mi nur scias ke mi volas fasti. Tio estas via defio por tiu semajno. Vi uloj, ni tuj doni al vi taskon. Ni tuj donos al vi defion. Kaj tiam ĝi estas ĝis vi infanoj tute simple elkalkuli kio estas la plej rapida kaj plej efika maniero por efektivigi tion. Yeah? 

Spektantaro: Ĉu ni permesis al se volis esplori pli rapida manieroj fari hash tabloj linio, ni povas fari ke kaj cite aliulaj kodo? ANDI PENG: Jes, tute bone. Do se vi infanoj legi la spec, ekzistas linio en la spec kiu diras vin infanoj estas tute libera por priesplori hash funkcioj sur kio estas iuj de la rapida kradaj funkcioj kuri aĵojn tra kiel longe kiel vi citas ke kodo. Do iuj personoj havas jam eltrovis rapidaj manieroj fari sorĉas kontroliloj, de rapida manieroj de stoki informon. Tute supren al vi knaboj, se vi volas nur prenu ke, dekstra? Certiĝu vi citante. La defio ĉi tie vere ke ni provas testi estas certigi ke vi scias vian vojon ĉirkaŭ punteros. Koncerne vin efektivigado la fakta hash funkcio kaj venanta supre kun kiel la math fari tion, vi uloj povas priesplori ajn metodoj rete vi uloj volas. Yeah? 

Spektantaro: Ĉu ni povas citi nur uzante la [inaudible]? 

ANDI PENG: Yeah. Vi povas simple, en via komento, vi povas citi kiel, oh, prenita de Yada, Yada, Yada, hash funkcio. Iu havas demandojn? Ni efektive breezed tra sekcio hodiaÅ­. Mi estos supren tie al respondi demandojn ankaÅ­. 

Ankaŭ, kiel mi diris, oficejo horoj ĉinokte kaj morgaŭ. La specifo ĉi semajno estas reale super facila kaj super mallonga legi. Mi sugestus prenante rigardu, ĝuste legi tra la tuteco de ĝi. 

Kaj Zamyla reale promenas vin tra ĉiu de la funkcioj Vi devas efektivigi, kaj tiel ĝi estas tre tre klara kiel fari ĉion. Ĝuste certigi ke vi estas konservanta trako de punteros. Tio estas tre defia pset. 

Ĝi ne estas defianta ĉar kiel, ho, la konceptoj estas tiel multe pli malfacila, aŭ vi devas lerni tiel nova sintakso la vojon ke vi faris por la lasta pset. Ĉi pset estas malfacila ĉar Estas tiom multaj indikoj, kaj tiam ĝi estas tre, tre facile tuj vi havas cimon en via kodo ne povos trovi kie tiu cimo estas. 

Kaj tiel kompleta kaj absoluta fido en vi uloj povi bati nia [inaudible] literumojn. Mi efektive ne havas skribita la mia ankoraÅ­, sed mi volis skribi mian. Do dum vi skribas via, mi skribos mia. Mi tuj provos fari mia rapida ol la via. Ni vidos kiu havas la plej rapida unu. 

Kaj jes, mi vidos ĉiujn vi uloj tie marde. Mi kuras speco kiel pset ateliero. Ĉiuj la sekcioj ĉi semajno estas pset metiejoj, tiel vi infanoj havas multajn ŝancojn por helpo, oficejo horoj kiel ĉiam, kaj mi vere atendas senpacience leganta ĉiujn de viaj infanoj 'kodo. Mi havas kvizojn ĉi tien se vi uloj volas veni akiri tiujn. Tio estas ĉio.