[MUZIKO Ludante] SPEAKER 1: Bone. Ĉiuj bonvenigas reen al sekcio. Mi esperas ke vi ĉiuj estas sukcese reakirita de via kvizo de la pasinta semajno. Mi scias ke estas iom freneza kelkfoje. Kiel mi diris antaŭe, se vi estas ene de la norma devio, Ne vere maltrankviliĝu pri tio, precipe dum malpli komfortaj sekcio. Tio pri kie vi devus esti. Se vi faris grandan, tiam awesome. Kudos al vi. Se vi sentas kiel vi bezonas iom pli da helpo, bonvolu bonvolu alveni el iu el la TFS. Ni ĉiuj estas tie por helpi. Tio estas kial ni instruos. Tio estas kial mi estas tie ĉiu lundo por vi infanoj kaj je oficejo horoj en ĵaŭdo. Do bonvolu bonvolu lasu min scii se vi ĝenus pri io aŭ se estas io en la kvizo ke vi vere volonte adreso. Do la tagordo por hodiaŭ estas ĉion pri datumstrukturoj. Kelkaj el tiuj estas ĝuste tuj estos ĝuste akiri vin familiarizado kun tiuj. Vi eble ne iam implementar ili en ĉi tiu klaso. Iujn el ili vi volas, kiel via Speller pset. Vi havas vian elekton inter kradaj tabloj kaj peras. Do ni definitive iros super tiuj. Ĝi tuj estos definitive pli afabla de alta nivelo sekcio hodiaŭ, kvankam, ĉar estas multaj el ili, kaj se ni iris en la implementación detaloj en ĉiuj ĉi tiuj, ni ne eĉ akiri tra ligitaj lertaj kaj eble iom de hash tabloj. Tiel pacience min toleras. Ni ne tuj faros tiel kodigo ĉi tempo. Se vi havas demandojn pri ĝi aŭ vi volas vidi ĝin implementado aŭ provi ĝin por vi mem, Mi definitive rekomendas tuj study.cs50.net, kiu havas ekzemplojn de ĉiuj el tiuj. Ĝi havos mian PowerPoints kun la notoj kiujn ni emas uzi tiel kiel iuj programado ekzercoj, speciale por aĵoj kiel ligitaj lertaj kaj binara arboj stakoj kaj sugestoj. Do iom pli alta nivelo, kiu povus esti bela por vi uloj. Do kun tio, ni komencu. Kaj ankaŭ, yes-- kvizojn. Mi kredas plejparto de vi, kiuj en miaj sekcio havas vian kvizojn, sed iu venas en aŭ ial vi ne, ili estas ĝuste ĉi tie en la fronto. Tiel ligitaj lertaj. Mi konas tiun specon de eliras apogi antaŭ via kvizo. Tio estis la semajno antaŭe ke ni lernis pri tio ĉi. Sed en ĉi tiu kazo, ni simple iri iom pli en profundo. Do kial povus elektas ligillisto super tabelo? Kio distingas ilin? Jes? Publiko: Vi povas pligrandigi kunligita listo kontre tabelo de fiksa grandeco. SPEAKER 1: Ĝuste. Tabelo fiksis grandeco dum kiu ligillisto havas ŝanĝiĝeman grandeco. Do se ni ne scias kiel multe ni volas gardi, lerta kunligita donas al ni grandan maniero fari tion, ĉar ni povas simple aldonu en alia nodo kaj aldoni sur alia nodo kaj aldoni al alia nodo. Sed kio povus esti komerco-off? Ĉu iu memoras la komerco-off inter arrays kaj ligitaj listoj? Mmhmm? Publiko: vi devas iru tra la tuta vojo tra la ligillisto trovi ero en listo. En tabelo, vi povas ĝuste trovi elementon. SPEAKER 1: Ĝuste. Do kun arrays-- Publiko: [inaudible]. SPEAKER 1: Kun arrays, ni havas kion nomas hazarda aliro. Signifas ke se ni volas kio estas iam la kvina punkto de listo aŭ la kvina punkto de nia tabelo, ni povas simple kapti ĝin. Se ĝi estas ligillisto, ni havas persisti tra, dekstra? Do alirante ero en tabelo estas konstanta tempo, dum kun ligillisto ĝi farus plej verŝajna esti lineara tempo ĉar eble nia ero estas la tuta vojo al la fino. Ni devas serĉi tra ĉiu. Do kun ĉiuj ĉi tiuj datumoj strukturoj ni iras esti elspezante iom pli da tempo sur, kio estas la pluses kaj negativaj. Kiam eble ni volas uzi unu super la alia? Kaj tio estas speco de la granda afero por forpreni. Do ni havas ĉi tie la difino de nodo. Estas kiel unu eron en nia ligillisto, dekstra? Do ni ĉiuj konas kun niaj typedef structs, kiun ni transiris en recenzo lastan fojon. Estis esence nur kreante alia datumtipo ke ni povus uzi. Kaj en ĉi tiu kazo, ĝi estas iu nodo ke estos teni iu entjero en. Kaj tiam kio estas la dua parto tien? Iu? Publiko: [inaudible]. SPEAKER 1: Jes. Ĝi estas puntero al la venonta vertico. Do tiu devus reale esti ĝis tie. Tio estas puntero de tipo nodo al alia afero. Kaj tio estas kion ili ampleksas nia nodo. Malvarmeta. Bone, do per serĉo, kiel ni estis nur diras antaŭ mano, se vi estas tuj serĉu pere, vi devas efektive persisti tra via ligillisto. Do se ni serĉas la numeron 9, ni devus komenci je nia kapo kaj kiu notas al ni komence de nia ligillisto, dekstra? Kaj ni diras, OK, ĉu tiu nodo enhavas la numeron 9? Neniu? Bone, iru al la sekvanta unu. Sekvi ĝin. Ĉu ĝi enhavas la numeron 9? No. Sekvu la venonta unu. Do ni devas reale persisti tra nia ligillisto. Ni ne povas simple iri rekte al kie 9 estas. Kaj se vi uloj efektive volas vidi iujn pseŭdo-kodo tie supre. Ni havas kelkajn serĉo funkcio tie kiu prenas in-- kio faras ĝi preni en? Kion vi opinias? Tiel facila. Kio estas tio? Publiko: [inaudible]. SPEAKER 1: La nombro ni serĉas. Rajto? Kaj kion tio respondas al? Ĝi estas puntero al? Publiko: Nodo. SPEAKER 1: Nodo al la elenco ke ni rigardas, ĉu ne? Do ni havas iuj nodoj estas puntero tie. Tiu estas punkto kiu tuj efektive persisti tra nia dissendlisto. Ni starigu gxin egala al listo ĉar tio estas nur establante ŝin egala al la komenci de nia ligillisto. Kaj dum ŝi ne NULL, dum ni ankoraŭ havas aĵojn en nia listo, kontroli por vidi se tiu nodo havas la nombro ni serĉas. Reveni vera. Alie, ĝisdatigi ĝin, ĉu ne? Se estas NULL, ni eliras nian dum buklo kaj reveni falsaj ĉar tio signifas ke ni ne trovis ĝin. Ĉu ĉiuj atingi, kiel tio funkcias? OK. Do kun inserción, vi havas tri malsamajn vojojn. Vi povas antaŭmetu, vi povas alfiksus kaj vi povas enigi en Assorted. En ĉi tiu kazo, ni estas tuj faros antaŭmetu. Ĉu iu scias kiel tiuj tri kazoj povus diferenci? Do antaŭmetu signifas ke vi metis ĝin ĉe la fronto de via listo. Do tio signifus ke negrave kion via nodo estas, negrave kion la valoro estas, vi tuj meti ĝin ĝuste ĉi tie antaŭ, OK? Ĝi tuj estos la unua elemento en via listo. Se vi alfiksus ĝin, tuj iri al la dorso de via listo. Kaj enmetu en Assorted signifas ke vi estas tuj metos reale en la loko kie gardas vian ligillisto ordo. Denove, kial vi uzas tiuj kaj kiam oni uzas ili estos varii dependanta sur via kazo. Se ĝi ne bezonas estu ordigataj antaŭmetu inklinas esti kio plej homoj uzi, ĉar vi ne iri tra la tutan liston trovi fine aldoni ĝin, ĉu ne? Vi povas nur trae juste. Do ni iru tra inserción 1 nun. Do unu afero kiun mi tuj tre rekomendas en ĉi pset estas desegni aferojn ekstere, kiel ĉiam. Ĝi estas tre grava ke vi ĝisdatigos via punteros en la ĝentila ordo ĉar se vi ĝisdatigi ilin iomete misfunkcias, vi tuj finos perdante partojn de via listo. Do ekzemple, en tiu kazo, ni estas rakontanta al la kapo por ĝuste punkto 1. Se ni nur faras tion sen ŝpari ĉi 1 ni ne havas ideon kion 1 devus celi nun ĉar ni perdis kion la kapo montris. Do unu afero memori Kiam vi faras antaŭmetu estas savi kion la kapo punktoj al la unua, tiam religi ĝin, kaj tiam ĝisdatigi kion via nova nodo devus celi. En tiu kazo, estas unu maniero por fari ĝin. Do se ni faris gxin tiamaniere kie ni ĵus reasignado kapon ni perdas esence nia tutan liston, ĉu ne? Unu vojo fari ĝin estas havi 1 punkto nun kaj poste havas kapon punkto 1. Aŭ vi povas fari specon de kiel la provizora stokado, kiun mi raportis. Sed reassigning via punteros en la ĝentila ordo tuj estos tre, tre grava por ĉi pset. Alie, vi tuj havos hash tablo aŭ provi ke estas ĝuste tuj estos nur parton de la vortoj kiujn vi voli kaj tiam you're-- mmhmm? Publiko: Kio estis la provizora stokado afero vi parolis? SPEAKER 1: La provizora stokado. Do esence alia Tiel vi povus fari tion ĝi stokas la kapon de iu, kiel stoki ĝin dumtempa variablo. Atribuos ĝin al 1 kaj tiam ĝisdatigi 1 atentigi al kiom kapo uzitaj por marki. Tiu vojo estas evidente pli eleganta ĉar vi ne bezonas provizoran valoron, sed nur proponante alian vojon por fari ĝin. Kaj ni efektive ja havas iuj kodon ĉi. Do por ligillisto, ni efektive havas iom da kodo. Do enmeti ĉi tien, tiu estas Des-kompozar. Do tiu eniras ĝin ĉe la kapo. Do unue, necesas Krei vian novan nodon, kompreneble, kaj kontroli NULL. Ĉiam bona. Kaj tiam vi devas atribui la valoroj. Whenever vi krei novan nodon, vi ne scias kio ĝi estas indikante proksima, do vi volas pravalorizi ĝin nula. Se ĝi finas montras ion alie, ĝi prenas reasignado kaj ĝi estas bone. Se ĝi estas la unua afero en la listo, ĝi bezonas atentigi al nulaj ĉar tio estas la fino de la listo. Tial por insertarlo, ni vidos tie estas atribui la proksima valoro de nia nodo esti ajn estro estas, kiu estas kion ni havis ĉi tie. Tio estas kion ni ĵus faris. Kaj tiam ni asignanta kapon al punkto al nia nova nodo, ĉar memoru, nova estas iuj montrilon al nodo, kaj tio estas ĝuste kion kapo. Tio estas ekzakte kial ni havas tiun sagon accessor. Cool? Mmhmm? Publiko: Ĉu ni devas pravalorizi nova apud nula unua, aŭ oni povas simple pravalorizi ĝin estras? SPEAKER 1: Nova apud bezonas esti NULL komenci ĉar vi ne scias, kie tuj estos. Ankaŭ, ĉi tiu estas speco de nur ŝatas paradigmo. Vi starigis ĝin egala al NULL simple fari certas, ke ĉiuj viaj bazoj estas kovritaj antaŭ fari ajnan reasignación por ke Vi ĉiam garantiis ke ĝi volas esti indikante specifa valoro kontre kiel rubo valoro. Ĉar, jes, ni atribuos nova proksima aŭtomate, sed estas pli justa kiel bona praktiko por pravalorizi ĝi en tiu maniero kaj tiam religi. OK, do duoble ligitaj lertaj nun. Kion ni pensas? Kio estas pri duoble ligitaj listoj? Do en nia ligitaj lertaj, ni povas nur movi en unu direkto, dekstra? Ni nur havas proksiman. Ni povas nur iri antaŭen. Kun duoble ligillisto, Ni povas ankaŭ movi malantaŭen. Do ni havas ne nur la numero kiun ni volas konservi, ni havos kie notas al proksima kaj kie ni ĵus venis. Do ĉi permesas por iuj bonaj trairo. Do duoble ligitaj nodoj, tre similaj, dekstra? Nur diferenco estas nun ni havas proksiman kaj antaŭa. Ĝi estas la sola diferenco. Do se ni antaŭmetu aŭ append-- ni ne havas kodon por tiu supren here-- sed se vi volus provi insertarlo, la grava afero Estas vi bezonos fari certe vi asignanta ambaŭ viajn antaŭajn kaj via sekva puntero korekte. Do en ĉi tiu kazo, vi farus Ne nur pravalorizi proksima, vi pravalorizi antaŭa. Se ni estas en la kapo de la listo, ni ne nur fari kapo egalaj nova, sed nia nova antaŭa devus notas al la kapo, ĉu ne? Tio estas la sola diferenco. Kaj se vi volas pli oportuna per tiuj kun ligitaj lertaj, kun insertar, per forviŝo, kun enigaĵo enen Assorted lerta, bonvolu kontroli study.cs50.net. Ekzistas aro da grandaj ekzercoj. Mi forte rekomendas ilin. Mi deziras ke ni havis tempon iri tra ili sed ekzistas multaj datumstrukturoj akiri tra. OK, do hash tabloj. Ĉi tiu estas probable la plej utila iom vian pset tien ĉar vi estas iranta esti efektivigo unu el tiuj, aŭ provi. Mi vere ŝatas hash tabloj. Ili estas belaj malvarmeta. Do esence kion okazas estas hash tablo estas kiam ni vere bezonas rapidan inserción, forigoj, kaj lookup. Tiuj estas la aferoj kiujn ni doni prioritaton en hash tablo. Ili povas akiri sufiĉe grandan, sed kiel ni vidos kun peras, estas aĵoj kiuj estas multe pli granda. Sed esence, ĉiu hash tablo estas hash funkcio kiuj diras al vi kion sitelo meti ĉiun de viaj datumoj, ĉiu el viaj elementoj. Simpla maniero pensi hash tablo estas ke estas nur siteloj de aĵoj, dekstra? Do kiam vi ordig aĵojn por kiel la unua litero de lia nomo, tio estas speco de kiel hash tablo. Do se mi estus kolekti vi uloj estas en grupojn de ajn nomo komenciĝas kun A super ĉi tie, aŭ kiu ajn estas naskiĝtago Estas en januaro, februaro, marto, ajn, kiu estas efike kreante hash tablo. Ĝi simple krei rubujojn ke vi ordigi viajn eroj enen tiel ke vi povas trovi ilin facile. Do tiu maniero kiam mi bezonas trovi unu el vi, Mi ne devas serĉi tra ĉiu de viaj nomoj. Mi povas esti similaj, ho, mi scias, ke Danielle la naskiĝtago estas in-- Publiko: --April. SPEAKER 1: Aprilo. Do mi rigardas mian aprilo sitelo kaj kun ajna sorto, ŝi estos la sola en tie kaj mia tempo estis konstanta en tiu senso, dum se mi devas serĉi tra amaso de homoj, ĝi tuj prenos multe pli longe. Do hash tabloj estas vere ĝuste siteloj. Facila maniero pensi pri ili. Do tre grava afero pri hash tablo estas hash funkcio. Do tion mi nur raportis, kiel via unua letero de via persona nomo aŭ via naskiĝtago monato tiuj estas ideoj kiuj vere interligataj al hash funkcio. Estas nur maniero de decidi kiu Balde vi elemento iras en, OK? Do por ĉi pset, vi povas serĉi sufiĉe tre ajna hash funkcio vi volas. Ne devas esti via propra. Estas iuj vere malvarmeta aĵoj eliras tie fari cxiajn freneza math. Kaj se vi volas fari vian literumilo super rapida, Mi certe rigardi en unu el tiuj. Sed estas ankaŭ la naivuloj, kiel komputi la sumo de la vortoj, kiel ĉiu litero havas numeron. Komputi la sumon. Kiu determinas la rubujon. Ili ankaŭ havas la facilan kiuj Estas ĝuste kiel ĉiuj de la A a tie ĉi, ĉiuj B estas tie. Iu el tiuj. Esence, ĝi simple informas vin ke tabelo indekso via ero devus iri en. Nur decidante la bucket-- estas tute kradon funkcio estas. Do jen ni havas ekzemplon, kiu estas nur la unua litero de la kordo ke mi ĝuste parolas. Do vi havas iun hash tio estas nur la unua letero de via ŝnuro minus A kiu donos al vi kelkajn numero inter 0 kaj 25. Kaj kion vi volas fari estas certiĝi ke tiu reprezentas la grandeco de via hash table-- kiom siteloj ekzistas. Kun multaj el tiuj kradaj funkcioj, ili estas tuj estos reveni valoroj kiuj povus esti alte super la nombro de siteloj ke vi efektive havas en via hash tablo do vi devas fari sekura kaj mod de tiuj. Alie, ĝi estas dironta, ho, tio devus esti en sitelo 5000 sed vi havas nur 30 siteloj en via hash tablo. Kaj kompreneble, ĉiuj scias ke estas tuj rezultos en iuj frenezaj eraroj. Do certigi al mod de la grandeco de via hash tablo. Malvarmeta. Do kolizioj. Ĉu ĉiu bona ĝis nun? Mmhmm? Publiko: Kial ĝi reveni tia amasa valoron? SPEAKER 1: Depende de la algoritmo ke via hash funkcio uzas. Kelkaj el ili faros freneza multipliko. Kaj tio estas ĉio pri akiri oni eĉ distribuo, do ili faros iun vere freneza tion kelkfoje. Tio estas ĉio. Ion alian? OK. Do kolizioj. Esence, kiel mi diris antaŭe, en la plej bona kazo scenaro, ajna balde mi esploros estas tuj havos unu afero do mi ne devas rigardi ĉiujn, ĉu ne? Mi ankaŭ scias ke estas tie aŭ ĝi estas ne, kaj tio estas, kion ni vere volas. Sed se ni havas dekojn da miloj de datumaj punktoj kaj malpli ol tiu nombro el siteloj, ni tuj havos kolizioj kie eventuale ion tuj devas fini en sitelo kiuj jam havas elementon. Do la demando estas, kion ni faru en tiu kazo? Kion ni faru? Ni jam havas ion tie? Ĉu ni simple jxeti gxin? No. Ni devas konservi ambaŭ de ili. Do la vojon, kiun ni tipe fari tion estas kio? Kio estas la datumstrukturo Ni ĵus parolis pri? Publiko: Ligita listo. SPEAKER 1: A ligillisto. Do nun, anstataŭ ĉiu el tiuj siteloj nur havi unu elemento, ĝi tuj enhavos ligillisto de la elementoj kiuj hashed en ĝin. OK, ne ĉiuj speco de bonstata ideo? Ĉar ni ne povus havi tabelo ĉar ni ne scias, kiom da tuj estos tie. A ligillisto permesas nin havas nur la ĝusta numero kiu estas hashed en tiu sitelo dekstra? Do linearaj sondado estas esence ĉi idea-- ĝi estas unu maniero trakti kolizio. Kion vi povas fari estas se, en tiu kazo, bero estis hashed en 1 kaj ni jam havas ion tie, vi ĵus teni subiro ĝis vi trovos malplenan fendo. Tio estas unu maniero por manipuli ĝin. La alia maniero por manipuli estas kun kion ni ĵus called-- la ligitaj Listo nomas sinsekvon. Do tiu ideo funkcias se via hash tablo vi opinias estas multe pli granda ol via datuma aro aŭ se vi volas provi minimumigi ĉenante ĝis ĝi estas absolute necesa. Do unu afero estas linearaj sondado evidente signifas ke via hash funkcio estas ne tute tiel utila ĉar vi tuj finos uzante via hash funkcio, alvenante al punkto, vi linearaj sondi malsupren al iu loko kiu estas havebla. Sed nun, kompreneble, nenio alie finas tie, Vi tuj devas serĉu pluen. Kaj estas multe pli serĉo elspezo ke iras en inputting ero en via hash tablo nun, ĉu ne? Kaj nun, kiam vi iros kaj provi kaj trovi bero denove, vi tuj hash ĝi, kaj gxi tuj diros, ho, rigardu en sitelo 1 Kaj ne tuj estos en sitelo 1, do vi tuj devos trairi tra la resto de tiuj. Do ĝi estas foje utilaj, sed plej ofte, Ni tuj diru ke sinsekvon estas kion vi volas fari. Do ni parolis pri tio antaŭe. Mi havas iom antaŭ mi. Sed sinsekvon Estas esence ke ĉiu sitelo en via hash tablo estas nur ligitaj listo. Do alia maniero, aŭ pli teknika vojo, pensi de hash tablo estas ke estas nur tabelo de ligitaj listoj, kiuj kiam vi skribas vian vortaro kaj vi provas ŝarĝi ĝin, pensi pri tio kiel tabelo de ligitaj lertaj faros ĝin multe pli facile Vi devas pravalorizi. Publiko: Do ​​hash tablo havas antaŭdeterminita grandeco, kiel [inaudible] de siteloj? SPEAKER 1: Ĝuste. Do ĝi havas aron da siteloj ke vi determine-- kiun vi uloj devus bonvolu ludi kun. Ĝi povas esti tre malvarmeta por vidi, kio okazas kiel vi ŝanĝas vian numeron de siteloj. Sed jes, ĝi havas starigu da siteloj. Kio permesas al vi havi kiel multaj eroj kiel vi bezonas Estas ĉi apartan sinsekvon kie kunligis listoj en ĉiu sitelo. Tio signifas via hash tablo estos ĝuste la grandeco ke vi bezonas esti, ĉu ne? Tio estas la tuta punkto de ligitaj listo. Malvarmeta. Do ĉiuj OK tie? Bone. Ah. Kio ĵus okazis? Vere nun. Divenu iu mortigas min. OK ni tuj iru en peras, kiuj estas iom freneza. Mi ŝatas hash tabloj. Mi kredas ke ili estas vere genia. Tries estas malvarmeta, ankaŭ. Do ĉu iu memoras kion provi estas? Vi devus transkuris brevemente en prelego? Ĉu vi memoras afabla de kiel ĝi funkcias? Publiko: Mi nur kapjesas ke ni transiru ĝin. SPEAKER 1: Ni transiru ĝin. OK, ni vere tuj iros super gxi nun estas, kion ni diras. Publiko: Tio estas por reakiro arbo. SPEAKER 1: Jes. Ĝi estas reakiro arbo. Awesome. Do unu afero rimarki tie estas ke ni rigardas individuajn karakterojn ĉi tie, ĉu ne? Tiel antaux niaj hash funkcio, ni rigardis la vortojn kiel tuto, kaj nun ni serĉas pli ĉe la karakterojn, dekstra? Do ni havos Maxwell tien kaj Mendel. Do esence try-- manieron pensi pri tio, ke ĉiu nivelo tie estas tabelo de leteroj. Do tiu estas via radika nodo tie, ĉu ne? Tiu havas ĉiujn karakterojn de la alfabeto por la komenco de ĉiu vorto. Kaj kion vi volas fari estas diru, OK, ni havas kelkajn M vorto. Ni tuj serĉos Maxwell, do ni iru al M. Kaj M punktoj al tuta alia tabelo kie ĉiu vorto, tiel longe kiel ekzistas estas vorto kiu havas A kiel la dua letero, Tiel longe, kiel ekzistas vorto kiu havas B kiel la dua letero, havos montrilon irante al iu proksima tabelo. Estas probable ne vorto kiun MP ion, tiel ankaux en la P pozicion en ĉi tabelo, ĝi estus nur NULL. Ĝi dirus, OK, ne ekzistas vorto kiu M sekvita per P, OK? Do se ni pensas pri ĝi, ĉiu unu el ĉi tiuj plej malgrandaj aferoj estas fakte unu el tiuj grandaj blokoj de A tra Z Do kio povus esti unu el la aĵoj kiu estas ia malavantaĝon de provi? Publiko: Multa memoro. SPEAKER 1: Estas tunoj de memoro, dekstra? Ĉiu el tiuj blokoj tie reprezentas 26 spacojn 26 elemento tabelo. Tiel peras akiri nekredeble spaco peza. Sed ili estas tre rapida. Tiel nekredeble rapida sed vere spaco ineficiente. Speco de devas kalkuli el kiuj unu vi deziras. Tio estas vere malvarmeta vian pset, sed ili faras preni multan memoron, tial vi komerci for. Yeah? Publiko: Ĉu estus ebla starigi try kaj tiam Unufoje vi havas ĉiujn datumoj en ĝi, ke vi need-- Mi ne scias se tio estus sensencaĵo. Mi estis akiranta liverita de ĉiuj NULL karakteroj, sed tiam vi ne povos indekso them-- SPEAKER 1: Vi ankoraŭ bezonas ilin. Publiko: - la sama maniero ĉiufoje. SPEAKER 1: Jes. Vi bezonas la NULL karakteroj lasi vi scias se ekzistas ne unu vorton tie. Ben vi havas ion, kion vi volas? OK. Bone, do ni iras iri iom pli en la teknikaj detaloj malantaŭ oni provu kaj labori tra ekzemplo. OK, do tio estas la sama afero. Dum en ligillisto, nia ĉefa speco of-- kio estas la vorto mi volas? - kiel konstruaĵo bloko estis nodo. En provo, ni havas ankaŭ nodo, sed ĝi estas difinita malsame. Do ni havas kelkajn bool ke reprezentas ĉu vorto reale Ekzistas en tiu loko, kaj poste Ni havas kelkajn tabelo here-- aŭ pli ĝuste, tio estas puntero al tabelo de 27 karakteroj. Kaj tio estas ĉar, en tiu kazo, ĉi 27-- mi certas vi ĉiuj similas, atendu, estas 26 literoj en la alfabeto. Kial ni havas 27? Do laŭ la vojo vi implementar ĉi, tio estas de pset ke permesis apostrofoj. Do tio estas kial la ekstra unu. Vi ankaŭ havas en iuj kazoj la nula terminator estas inkludita kiel unu el la karakteroj kiuj ĝi estas permesita esti, kaj tiel ili kontrolu rigardu, cxu gxi estas la fino de la vorto. Se vi interesiĝas, Kontroli Kevin la video sur study.cs50, tiel kiel Vikipedio havas iuj bonaj rimedoj tie. Sed ni tuj iru tra ĝuste speco de kiel vi povus labori tra try Se vi donis unu. Do ni havas súper simpla tie havas la vortojn "batilo" kaj "zoom" en ili. Kaj kiel ni vidas nin tie, tiu malgranda spaco ĉi tie reprezentas nian bool ke diras, jes, tio estas vorto. Kaj tiam tiu havas nian arrays de karakteroj, dekstra? Do ni tuj iru tra trovanta "batilo" en tiu provo. Do komencu ĉe la supro, dekstra? Kaj ni scias, ke b respondas al la dua indico, la dua elemento en tiu tabelo, ĉar a kaj b. Do proksimume la dua. Kaj ĝi diras, OK, malvarmeta, sekvu ke en La sekva tabelo, ĉar se ni memoras, ĝi ne estas, ke ĉiu el tiuj vere enhavas la elementon. Ĉiu de ĉi tiuj matricoj enhavas puntero, dekstra? Ĝi estas grava distingo por fari. Mi scias tion tuj be-- tries estas vere malfacile atingi en la unua momento, do eĉ se tiu estas la dua aŭ tria tempo Kaj ĝi estas ankoraŭ speco simili malfacila, Mi promesas, se vi iros horloĝo La mallonga denove morgaŭ sxanco gxi faru multon pli sentita. Ĝi prenas multan digesti. Mi ankoraŭ foje am kiel, atendu, kio estas provi? Kjel mi rajtas? Do ni b tiukaze kio estas nia dua indico. Se ni havis, ekzemple, c aŭ d aŭ ajna alia letero, ni bezonas por mapi ke reen al la indekso de nia tabelo, ke tio respondas al. Do ni prenus kiel rchar kaj ni simple subtrahi suferintojn por mapi ĝin 0 al 25. Ĉiu bona kiel ni mapi niaj karakteroj? OK. Do ni iru al la dua, kaj ni vidi ke, jes, ĝi estas ne NULL. Ni povas movi sur al ĉi sekva tabelo. Do ni iru al tiu flanko tabelo tie. Kaj ni diras, OK, nun ni bezonas vidi se estas ĉi tie. Estas nula aŭ faras efektive antaŭi? Do fakte movas plusendu en tiu tabelo. Kaj ni diras, OK, t estas nia lasta letero. Do ni iru al la t en la indekso. Kaj tiam ni movas antaŭen ĉar ne estas alia. Kaj ĉi tiu lin diras esence, ke, jes, ĝi diras ke estas vorto here-- ke se vi sekvas ĉi irejo, vi alvenis en vorto, kiun ni scias estas "batilo". Jes? Publiko: Ĉu normo havi tiun kiel indico 0 kaj tiam havi specon ĉe 1 aŭ havi je la fino? SPEAKER 1: No. Do se ni retrorigardas al nia deklaro ĉi tie, ĝi estas bool, tial ĝi estas lia propra elemento en via nodo. Do ĝi ne estas parto de la tabelo. Malvarmeta. Do kiam ni finos nian vorto kaj ni en tiu tabelo, kion ni volas fari Estas fari ĉekon por estas tiu vorto. Kaj en ĉi tiu kazo, ĝi revenus jes. Do en tiu noto, ni scias ke "zoon" - ni konas homoj kiuj "bestoĝardeno" estas vorto, dekstra? Sed provu tie estus diru, ne, tio ne. Kaj ĝi dirus ke ĉar ni ne designó kiel apartajn vortojn. Kvankam ni povas trairi tra ĉi tabelo, tiu try dirus ke ne, bestoĝardeno ne estas en via vortaro ĉar ni ne havas designó kiel tia. Do unu maniero fari that-- Ho, pardonu, tiu ĉi. Do en ĉi tiu kazo, "bestoĝardeno" ne vorto, sed ĝi estas en nia provo. Sed en ĉi tiu, ke ni volas ke enkonduki la vorton "bano", kio okazas Estas ni sekvu through-- b, a, t. Ni estas en tiu tabelo, kaj Ni iru serĉi h. En tiu kazo, kiam ni rigardi la montrilo ĉe h, ĝi estas indikante NULL, OK? Do, se tio estas eksplicite indikante alia tabelo, Vi supozas ke ĉiuj punteros en tiu tabelo estas indikante nula. Do en ĉi tiu kazo, h notas al NULL do ni povas fari nenion, tiel same revenos falsa, "bano" ne estas en ĉi tie. Do nun ni estas reale tuj iros per Kiel ni fakte diras ke "zoon" estas en nia provo. Kiel do ni enmetu "bestoĝardeno" en nia provo? Do, en la sama maniero kiun ni komencis kun nia ligillisto, ni komencu ĉe la radiko. Kiam en dubo, starti je la radiko de tiuj aĵoj. Kaj ni diras, OK, z. z ekzistas en tio, kaj ĝi faras. Do vi movas al via sekva tabelo, OK? Kaj tiam la venontan unu, Ni diru, OK, ne o ekzistas? Ĝi faras. Tiu denove. Kaj tiel en nia proksima, ni diras, OK, "bestoĝardeno" jam ekzistas ĉi tie. Ĉio ni bezonas fari estas metita ĉi egalaj al vera, ke la vorto ekzistas. Se vi sekvis ĉiun ĝis antaŭ tiu punkto, ĝi estas vorto, do simple metu gxin egala al tiaj. Jes? Publiko: do faras tion signifas ke "ba" estas vorto ankaŭ? SPEAKER 1: No. Do en ĉi tiu kazo, "ba" ni akirus tie, ni devus diri estas vorto, kaj tio estus ankoraŭ ne. OK? Mmhmm? Publiko: Tiel unufoje vi trovas ĝin vorto kaj vi diros jes, tiam enhavos iri al m? SPEAKER 1: Do tiu devas vidi with-- vi ŝarĝas ĉi en. Vi diras "bestoĝardeno" estas vorto. Kiam vi iras al check-- kiel, diru vi volas diri, signifas "bestoĝardeno" ekzistas en tiu vortaro? Vi nur tuj serĉi "zoo" kaj tiam kontrolu por vidi se ĝi estas vorto. Vi neniam tuj movos tra al m ĉar tio ne estas kion vi serĉas. Do se ni efektive volis aldoni "bano" en tiu provo, ni farus la samon kiel ni faris kun "zoo" krom ni vidus ke kiam ni provi kaj instigi al h, ĝi ne ekzistas. Do vi povas pensi pri tio kiel provi aldoni novan nodon en ligillisto, do ni bezonus aldoni alian unu el tiuj matricoj, kiel tia. Kaj poste, kion ni faras estas ni nur metis la h elemento de tiu tabelo montras ĉi. Kaj tiam kion ni volas fari tie? Aldoni ĝin egala al vera ĉar ĝi estas vorto. Malvarmeta. Mi scias. Tries ne estas la plej ekscita. Kredu min, mi scias. Do unu afero realigi kun peras, Mi diris, ke ili estas tre efika. Do ni vidis lin ekkantu tuno de spaco. Ili ia malklara. Do kial ni iam uzos tiujn? Ni uzas tiujn ĉar ili estas nekredeble efika. Do se vi iam rigardis supren vorto, vi estas nur barita per la longeco de la vorto. Do, se vi serĉas vorto, kiu estas de longeco kvin, vi nur iam tuj devos fari maksimume kvin komparoj, OK? Do ĝi faras esence konstanto. Ŝati inserción kaj lookup estas esence konstanto tempo. Do, se vi povos iam preni io en konstanta tempo, tio estas same bona kiel ĝi akiras. Vi ne povas pli bone ol konstanta tempo por tio. Do kiu estas unu el la grandega pluses de tries. Sed estas multe da spaco. Do ia decidi kio estas pli grava por vi. Kaj en la hodiaŭaj komputiloj, La spaco kiu provi eble ekkantu eble ne afekti vi, kiu multe, sed eble vi kontraktanta kun iu Kiu havas multe, multe pli da aferoj, kaj provi simple ne estas racia. Jes? Publiko: Atendu, do vi havos 26 literojn en ĉiu ununura unu? SPEAKER 1: Mmhmm. Jes, vi havas 26. Vi havas kelkajn estas vorto markilo kaj tiam vi havos 26 punteros en cxiu. Kaj ili estas point-- Publiko: CXia 26 ĉu ili ĉiu havas 26? SPEAKER 1: Jes. Kaj tial, kiel vi povas vidu, ĝi ekspansiiĝas tute rapide. Bone. Do ni tuj eniri en la arboj, kiuj Mi sentas ŝatas estas pli facile kaj probable esti belan indulto el tries tie. Do espereble plejparto de vi vidis arbo antaŭe. Ne kiel la bela karaj ekstere, kiun mi Ne scias se iu iris libera ĉielo ĵus. Mi iris pomon pluki tiu semajnfino, kaj ho mia ho, tio estis bela. Mi ne scias folioj povis rigardi, ke bela. Do tio estas nur arbo, ĉu ne? Estas nur kelkaj nodo, kaj ĝi notas al aro da aliaj nodoj. Kiel vi vidas tie, tiu estas speco de temo recurrente. Nodoj indikus nodoj estas speco de La esenco de multaj datumstrukturoj. Ĝi nur dependas de kiel ni ilin marki reciproke kaj kiel ni trairi tra ili kaj kiel ni enmeti tion kiu determinas iliajn malsamajn trajtojn. Tiel nur iuj terminologio, kiun mi uzis antaŭe. Do radiko estas kio estas ĉe la plejsupro. tio estas kie ni ĉiam komencu. Vi povas pensi pri tio kiel la kapo ankaŭ. Sed por arboj, ni inklinas referi al kiel la radiko. Ion malsupre here-- en la tre tre bottom-- Estas konsiderita folioj. Do ĝi iras kune kun la tuta arbo ion, ĉu ne? Folioj estas ĉe la randoj de viaj arbo. Kaj tiam ni ankaŭ havas paron de Kondiĉoj paroli nodoj en rilato al ĉiu alia. Do ni havas gepatro, infanoj, kaj gefratoj. Do en ĉi tiu kazo, 3 estas la patro de 5, 6 kaj 7. Do la patro estas kiom estas unu paŝo supre ajn vi estas raportante al, tial simple kiel familio arbo. Espereble tiu estas ĉiu iom iom pli intuicia ol tries. Gefratoj estas iu kiu havas la sama patro, ĉu? Ili estas en la sama nivelo tie. Kaj tiam, kiam mi estis dirante, infanoj estas nur kiom estas unu paŝo sube la nodo en demando, OK? Malvarmeta. Do duuma arbo. Ĉu iu Hazard konjekto sur unu el la karakterizaĵoj de la duuma arbo? Publiko: Max du folioj. SPEAKER 1: Ĝuste. Do max de du folioj. Do en ĉi tiu antaŭ, ni havis ĉi tiun kiu havis tri, sed en duuma arbo, vi havas max de du infanoj po patro, ĉu? Jen plia Interesa karakterizaĵo. Ĉu iu scias tion? Duuma arbo. Do duuma arbo havos ĉiun sur the-- ĉi tiu ne sorted-- sed en ordo duuma arbo, ĉiu sur la dekstra estas pli granda ol la patro, kaj ĉio maldekstre estas malpli ol la patro. Kaj tio estis kvizo demando antaŭe, tiel bone konas. Do kiel ni difinas tion, Denove, ni havi alia nodo. Tiu aspektas tre simila al kio? Duoble Publiko: Ligita lertaj SPEAKER 1: Duobla ligillisto, dekstra? Do se ni anstataŭigenda kun antaŭa kaj sekva, tio estus duoble ligitaj listo. Sed en ĉi tiu kazo, ni reale havas maldekstran kaj dekstran kaj tio estas ĝi. Alie, ĝi estas precize la sama. Ni ankoraŭ havas la elemento vi serĉas, kaj vi nur havas du punteros tuj ajn sekvas. Jes, tia duuma serĉarbo. Se ni rimarkos, ĉiu sur la ĉi tie estas pli granda than-- aŭ ĉio tuj dekstren tie estas pli granda ol ĉio tie estas malpli ol. Do se ni devis serĉi tra, ĝi devus rigardi tre proksime al duuma serĉo ĉi tie, ĉu ne? Krom anstataŭ serĉi je duono la tabelo, ni nur rigardante ĉu maldekstren flankon aŭ la dekstra flanko de la arbo. Do ĝi akiras iom pli simple, mi opinias. Do se via radiko estas NULL, evidente estas nur falsaj. Kaj se ĝi estas tie, evidente ĝi estas vera. Se ĝi estas malpli ol, ni serĉu maldekstre. Se ĝi estas pli granda ol, Ni esploru la dekstra. Estas ekzakte kiel duuma serĉo, nur malsama datumstrukturo ke ni uzas. Anstataŭ tabelo, estas nur duuma arbo. OK, stakoj. Kaj ankaŭ, ĝi aspektas kiel ni havu iomete da tempo. Se ni faros, mi ĝojas iri super iu el ĉi denove. OK, do stakoj. Ĉu iu memoras kion stacks-- iu trajtojn de pilo? OK, tial la plimulto de ni, mi kredas, manĝi en la manĝ halls-- kiom ni ne ŝatas. Sed evidente, vi povas pensi pri pilo laŭvorte kiel stako de pletoj aŭ stako de aĵoj. Kaj kio estas grava rimarki estas ke something-- la karakterizo ke ni nomas ĝin by-- estas LIFO. Ĉu iu scias kion tio signifas? Mmhmm? Publiko: lasta en, unua el. SPEAKER 1: Dekstra, daŭras en, unua el. Do se ni scias, se ni Stacking aferoj supren, la plej facila afero por ekpreni off-- kaj eble la sola afero ni povas ekpreni ekstere se nia stako estas granda enough-- estas ke supro elemento. Do, kion oni metis en last-- kiel ni vidas ĉi tie, ajn estis puŝita en plej recently-- estas tuj estos la unua kion ni popo ekstere, OK? Do kion ni havas ĉi tie alia typedef struct. Tiu estas vere ĝuste ŝatas intensiva kurso en datumstrukturo, tial ekzistas multe ĵetitaj ĉe vi uloj. Mi scias. Do ankoraŭ alia struct. Yay por strukturoj. Kaj en ĉi tiu kazo, ĝi estas iu montrilo por tabelo kiu havas iun kapablon. Do tio reprezentas nian pilo tie, kiel nia reala tabelo ke estas tenanta nian elementoj. Kaj tiam tie ni havas iun grandecon. Kaj tipe, vi volas konservi aŭtoveturejo de kiel granda via pilo estas pro kio okazas al permesi Vi devas fari estas se vi scias la grandeco, ĝi ebligas al vi diri, OK, mi estas je kapablo? Ĉu mi povas aldoni ion pli? Kaj ĝi ankaŭ informas vin kie la supro de via pilo Estas tiel vi scias kion vi efektive povas ekflugi. Kaj tio efektive tuj esti iom pli klara ĉi tie. Do por puŝo, aĵo, se vi estis iam implementar puŝo, kiel mi ĵus diris, via pilo havas limigitan grandecon, dekstra? Nia tabelo havis iun kapablon. Estas tabelo. Ĝi estas fiksita grandeco, do ni bezonas certigi ke ni ne metante pli en niajn vicojn ol ni fakte havas spacon por. Do kiam vi kreas puŝo funkcio, unua kiu faras estas diri, nu bone, mi havas spacon en mia pilo? Ĉar se mi ne, pardono, Mi ne povas stoki via ero. Se mi faras, tiam vi volas konservi ĝin ĉe la supro de la stako, dekstra? Kaj ĉi tio, ni havas por konservi trako de nia grandeco. Se ni ne konservi trako de nia grandeco, ni ne scias kie meti ĝin. Ni ne scias kiom da aferoj Estas en nia tabelo jam. Ŝati evidente ekzistas manieroj ke eble vi povus fari tion. Vi povus pravalorizi ĉion null kaj tiam kontroli la lastajn NULL, sed multe pli simpla afero estas simple diri, OK, konservi trako de grandeco. Kiel mi scias, ke mi havas kvar elementoj Miaj tabelo, do la sekva afero ke ni surmetis, ni estas tuj stoki je indico 4. Kaj tiam, kompreneble, ĉi tio signifas ke Vi sukcese puŝis ion sur via pilo, vi deziras pliigi la grandecon por ke vi sciu, kie vi estas tiel ke vi povas puŝi pli aĵoj sur. Do se ni provas pop ion ekstere de la stako, kio povus esti la unua afero ke ni volas kontroli? Vi provas preni ion demetu pilo. Ĉu vi certas ke estas ion en via pilo? No. Do kio povus ni volas kontroli? Publiko: [inaudible]. SPEAKER 1: Kontrolu la grandeco? Grandeco. Do ni volas kontroli por vidi se nia grandeco estas pli granda ol 0, OK? Kaj se ĝi estas, tiam ni volas malpliigi nian grandecon per 0 kaj revenas tiel. Kial? En la unua ni estis puŝante, ni pelis ŝin sur grandeco kaj tiam ĝisdatigita grandeco. En ĉi tiu kazo, ni decrementing grandeco kaj tiam preni ĝin, plukas ĝi el nia tabelo. Kial povus ni fari? Do se mi havas ion sur mia stako, kio estus mia grandeco je tiu punkto? 1. Kaj kie estas ero 1 stokitaj? Je kio indico? Publiko: 0. SPEAKER 1: 0. Do en ĉi tiu kazo, ni ĉiam bezonos fari sure-- anstataŭ reveni grandeco minus 1, ĉar ni scias ke nia ero estas tuj stokos je 1 malpli ajn nia esas, tiu nur prizorgas ĝin. Ĝi estas iomete pli eleganta maniero. Kaj ni simple dekremento nia grandeco kaj tiam reveni grandeco. Mmhmm? Publiko: mi supozas ĝuste ĝenerale, Kial tiu datumstrukturo beneficioso? SPEAKER 1: Tio dependas de via kuntekston. Do por iuj de la teorio, se vi laboras with-- OK, mi volas vidi se estas beneficioso unu kiu estas utila por pli ol ekstere de CS. Kun stakoj, ajna tempo vi bezonas por konservi trako de iu kiu estas la plej lastatempe aldonitaj estas kiam vi tuj volas uzi pilon. Kaj mi ne povas pensi pri bona Ekzemplo de tiu rajto nun. Sed kiam ajn la plej freŝaj afero estas plej grava por vi, tio estas kiam stako tuj estos utila. Mi provas pensi se tie estas bona por tio. Se mi pensas pri bona ekzemplo en la sekva 20 minutoj, mi definitive diri al vi. Sed ĝenerale, se estas io, kiel mi diris pli, kie plej freŝaj plej gravas, ke la kie stako eniras en ludo. Dum vostoj estas speco de la malo. Kaj ĉiuj hundetoj. Ne estas tiu granda, ĉu ne? Mi sentas kiel mi devus nur havi bunny video ĝuste en la mezo de sekcio por vi uloj ĉar tiu estas intensa sekcio. Do vosto. Esence vosto similas al linio. Vi uloj mi certas uzo ĉi ĉiutaga, ĝuste kiel en nia manĝejojn. Do ni devas iri en kaj akiri niajn pletojn, mi estas certe vi devas atendi en vico al swipe aŭ akiri vian manĝon. Do la diferenco ĉi tie estas kiu klopodas FIFO. Do se LIFO estis lasta en, unua eksteren, FIFO estas unua en, unua el. Do ĉi tiu estas kie ajn vi metis je unua estas via plej grava. Do se vi atendis en line-- ĉu eblas imagu se vi iris iri akiri la nova iPhone kaj estis stako kie la lasta persono en linio havas ĝin unua, homoj mortigas unu la alian. Do FIFO, ni estas ĉiuj tre familiara kun la reala mondo tie, kaj ĉiuj devas vidi kun reale ia rekreas ĉi tuta linio kaj vicatendis strukturo. Do dum la stako, ni havos puŝo kaj popo. Kun vosto, ni havas enqueue kaj dequeue. Do enqueue esence signifas metis ĝin sur la dorson, kaj dequeue signifas preni sur la antauxa. Do nia datumstrukturo estas Iomete pli komplikita. Ni havos duan aferon spuri. Do sen la kapo, tio Estas ekzakte stako, dekstra? Ĉi tiu estas la sama strukturo kiel stako. La nura afero malsama nun estas ni havas tiun kapon, ke kion vi opinias tuj konservi trako de? Publiko: La unua. SPEAKER 1: Dekstra, La unua afero kiun ni metas en. La estro de nia vosto. Kiu estas la unua en linio. Bone, do se ni faras enqueue. Denove, kun iu el tiuj datumstrukturoj, ekde ni kontraktanta kun tabelo, ni bezonos por kontroli se ni havas spacon. Tiu estas speco de kiel mi diras al vi uloj, se vi malfermos dosieron: Vi bezonas kontroli nula. Kun iu el tiuj piloj kaj vostoj, necesas por vidi se estas spaco ĉar ni estas kontraktanta kun fiksa grandeco tabelo, kiel ni vidos here-- 0, 1 ĉiuj ĝis 5. Do kion ni faru en tiu kazo estas ĉeko por vidi se ni havas ankoraŭ spacon. Ĉu nia grandeco malpli ol kapablo? Se jes, necesas gardi ĝin la vosto kaj ni ĝisdatigi nian grandecon. Do kio povus la vosto en tiu kazo? Ĝi ne estas eksplicite skribite eksteren. Kiel ni stoki ĝin? Kio estus la vosto estas? Do ni iru tra tiu ekzemplo. Do tiu estas tabelo de amplekso 6, dekstra? Kaj ni havas nun, nia esas 5. Kaj kiam ni metis ĝin en, ĝi okazas por iri en la kvina indico, dekstra? Do stoki en vosto. Alia maniero por skribi vosto farus nur estu nia tabelo ĉe indico de grandeco, dekstra? Ĉi estas grandeco 5. Sekva afero tuj iros en 5. Cool? OK. Ĝi alvenas iomete pli komplika kiam ni komencas metante kun la kapo. Jes? Publiko: Ĉu tio signifas, ke ni estus deklarita tabelo ke Estis kvin elementoj kaj longaj tiam ni aldonas sur ĝi? SPEAKER 1: No. Do en tiu kazo, estas stako. Tiu estus deklarita kiel tabelo de amplekso 6. Kaj en ĉi tiu kazo, ni nur unu spaco maldekstre. OK, do unu afero estas en tio okazo, se nia estro estas je 0, tiam ni simple povas aldoni ĝin al grandeco. Sed metas iom trickier ĉar efektive, ili ne havas slide pro tio, ke mi iras desegni unu ĉar ĝi estas ne tute simpla unufoje vi komenci liverante de aĵoj. Do dum kun pilo Vi nur iam zorgi pri kion la grandeco estas kiam vi aldonas ion plu, kun vosto vi ankaŭ bezonos fari certa ke via kapo estas klarigita, ĉar malvarmeta afero pri vostoj estas ke se vi ne estas en kapablo, vi povas reale fari envolver ĉirkaŭe. OK, do unu thing-- ho, Estas terure kreto. Unu afero konsideri estas la kazo. Ni nur faru kvin. OK, do ni tuj diras la estro estas tie. Tiu estas 0, 1, 2, 3, 4. La kapo estas tie, kaj bonvolu havi aĵojn en ili. Kaj ni volas aldoni ion, ĉu ne? Do kion ni bezonas scii estas kiu la kapo estas ĉiam tuj movi tien kaj tiam buklo reen ĉirkaŭe, OK? Do tiu vosto havas spacon, dekstra? Ĝi havas spacon en la komenco, speco de la malon de tio. Do kion ni bezonas por fari estas ni bezonas kalkuli la vosto. Se vi scias, ke via kapo ne moviĝis, vosto estas nur via tabelo je la indico de la grandeco. Sed en realo, se vi uzas vosto, Via kapo estas probable esti ĝisdatigita. Do kion vi bezonas fari estas reale kalkuli la vosto. Do kion ni faras estas tiu formulo tie, kiun mi tuj lasos infanoj pensi, kaj tiam ni parolos pri ĝi. Do tio estas kapablo. Do tio efektive al vi vojon por fari ĝin. Ĉar en tiu kazo, kion? Nia estro estas je 1, nia esas 4. Se ni mod kiu por 5, ni preni 0, kio estas kie ni devus input ĝin. Tial en la sekvanta okazo, se ni faros tion, Ni diru, bone, ni dequeue ion. Ni dequeue ĉi. Ni prenu tiun elementon, dekstra? Kaj nun nia kapo notas ĉi tie, kaj ni volas aldoni alian aferon. Tio estas esence la dorso de nia linio, dekstra? Vostoj povas envolver ĉirkaŭ la tabelo. Tio estas unu el la ĉefaj diferencoj. Stakoj, vi ne povas fari ĉi tion. Kun vostoj, vi povas CXar cxio, kio gravas estas ke vi scias kion Estis plej lastatempe aldonitaj. Ekde ĉiu tuj estos aldonita en ĉi maldekstren direkton, tiukaze kaj tiam envolver ĉirkaŭe, vi povas daŭrigi metante novajn elementojn ĉe la fronto de la tabelo ĉar ne vere La fronto de la tabelo anymore. Vi povas pensi pri la komenco de la tabelo de kie via kapo reale estas. Do ĉi tiu formulo estas kiel vi kalkuli vian voston. Ĉu tio havas sencon? OK. OK, dequeue kaj tiam vi uloj havas 10 minutojn demandi min ajna klarigante demandoj vi volas, ĉar mi scias ke estas freneza. Bone, do en la saman way-- Mi ne scias, ĉu vi uloj rimarkis, sed CS estas ĉio pri ŝablonoj. Aĵoj estas sufiĉe tre la sama, nur kun eta tweaks. Do samon tie. Ni devas kontroli por vidi se ni reale havi ion en nia vosto, dekstra? Diru, OK, estas nia grandeco pli granda ol 0? Malvarmeta. Se ni faras, tiam ni transloki nian kapon, kiu Tion mi simple pruvis tie. Ni ĝisdatigos nia kapo esti unu pli. Kaj tiam ni dekremento nia grandeco kaj redoni la elementon. Ekzistas multe pli da konkretaj kodo sur study.cs50.net, Mi forte rekomendas iri tra ĝi, se vi havas tempon, eĉ se estas nur pseŭdo-kodo. Kaj se vi uloj volas paroli per ke kun mi unu sur unu, bonvolu sciigi min scias. Mi ŝatus. Datumstrukturoj, se vi prenas CS 124, vi scias ke datumstrukturoj akiri tre amuzo kaj ĉi estas nur komenco. Do mi scias ke estas malfacile. Estas bone. Ni luktas. Mi ankoraŭ faros. Do, ne tro maltrankviliĝu pri tio. Sed tio estas esence via intensiva kurso en datumstrukturoj. Mi scias ke estas multe. Ĉu estas io ke ni dezirus transiri denove? Io ajn ni volas paroli tra? Jes? Publiko: Por ekzemplo, do la nova vosto estas je 0 transigis tion? SPEAKER 1: Jes. Publiko: OK. Do tiam iras tra, vi havus 1 plus 4 or-- SPEAKER 1: Do vi diras, Kiam ni volas iri fari ĉi tien? Publiko: Yeah. Do se vi imagante out-- kie estas vi kalkuli la voston de en tio? SPEAKER 1: Do la vosto Estis in-- Mi ŝanĝis ĉi. Do en ĉi tiu ekzemplo tie, tio estis la tabelo ni rigardas, OK? Do ni havas aferojn en 1, 2, 3, kaj 4. Do ni havos niajn kapo egalas al 1, je tiu punkto, kaj nia esas egala al 4 ĉe tiu punkto, dekstra? Vi ĉiuj konsentas ke estas la kazo? Do ni faru la kapo plus la grandeco, kiun donas al ni 5, kaj tiam ni MOD por 5. Ni preni 0, kiu nin diras ke 0 estas kie estas nia vosto, kie ni havas spacon. Publiko: Kio estas kaskedo? SPEAKER 1: La kapablo. Pardonu. Do tio estas la grandeco de via tabelo. Jes? Publiko: [inaudible] antaŭe ni revenos la elemento? SPEAKER 1: Do ni movos la kapo aŭ redoni la momento? Do se ni movas unu, dekremento la grandeco? Rezisti. Mi definitive forgesis alian. Ne gravas. Ne estas alia formulo. Jes, vi volus redoni la kapon kaj tiam movi ĝin. Publiko: Bone, ĉar en ĉi tiu punkto, la kapo estis je 0, kaj tiam vi volas reveni indico 0 kaj tiam fari kapo 1? SPEAKER 1: Ĝuste. Mi kredas ke estas alia formulo speco de kiel oriento. Mi ne havas ĝin sur la supro de mia kapo Mi ne volas doni al vi malĝustan unu. Sed mi pensas, ke estas perfekte valide diru, OK, stoki ĉi element-- ajn kapo de elemento is-- dekremento via grandeco, movu vian kapon super kaj reveno ajn tiu elemento estas. Tio estas perfekte valida. OK. Mi sentas min kiel ĉi tiu estas ne kiel la most-- vi ne tuj iru el tie kiel, jes, mi scias tries. Mi havas ĝin ĉiuj. Tio estas en ordo. Mi promesas. Sed datumstrukturoj estas iu kiu ĝi prenas multan tempon kutimi. Probable unu el la plej malfacila tion, mi kredas, en la kurso. Do ĝi definitive prenas ripeto kaj rigardante at-- mi Ne vere scias ligitaj lertaj ĝis mi faris multe tro da kun ili, en la sama maniero kiun mi ne vere kompreni punteros ĝis mi devis instrui dum du jarojn kaj do miaj propraj psets kun ĝi. Ĝi prenas multan reiteración kaj tempo. Kaj finfine, ĝi estos ia klaku. Sed dume, se vi havas specon de altnivela kompreno de kio tiuj do, ilia pros kaj cons-- kio estas kio ni vere emas substreki, precipe en la intro kurso. Kiel, kial ni uzas oni provos sur tabelo? Kiel, kio estas la pozitivaj kaj negativaj de ĉiu el tiuj? Kaj kompreni la komerco-offs inter ĉiu de tiuj strukturoj Estas kio estas multe pli grava nun. Povas esti unu freneza demando aŭ du kiu estas tuj demandos vin implementar puŝo aŭ implementar popo aŭ enqueue kaj dequeue. Sed plejparte, havi tiun alta nivelo kompreno kaj pli de intuicia kompreno estas pli grava ol reale povante apliki ĝin. Estus vere imponega se vi ĉiuj povis eliri kaj iri implementar try, sed ni komprenas ĝin ne nepre la plej racia afero nun. Sed vi povas en via pset, se vi volas al, kaj poste vi ricevos praktiko kaj do eble vi vere komprenis. Jes? Publiko: Bone, do, kiuj estas ni intencis uzi en la pset? Ĉu mi devas uzi unu el ili? SPEAKER 1: Jes. Do vi havas preferatan. Mi supozas en ĉi tiu kazo, ni povas paroli pri la pset iomete ĉar mi trakuris tiujn. Do en via pset, vi havas vian elekton el tries aŭ hash tabloj. Iuj homoj provos kaj uzi floras filtriloj, sed tiuj teknike ne estas korekta. Pro ilia probableca naturo ili donas falsaj pozitivaj kelkfoje. Ili estas malvarmeta esploru, kvankam. Tre rekomendas serĉi ilin almenaŭ. Sed vi havas preferatan inter kradaj tablo kaj provi. Kaj ke tuj estos kie vi ŝarĝi en via vortaro. Kaj vi devas elekti via hash funkcio, vi bezonas elekti kiom siteloj vi havas, kaj ĝi varias. Kiel se vi havas pli siteloj, eble kuros pli rapide. Sed eble vi malŝparante multa spaco tiel, kvankam. Vi devas kompreni ĝin. Mmhmm? Publiko: Vi antaŭe diris ke Ni povas uzi aliajn kradaj funkcioj, ke ni ne devas krei hash funkcio? SPEAKER 1: Jes, ĝuste. Do laŭvorte por via hash funkcio, kiel google "hash funkcio" kaj serĉas iun malvarmeta aĵoj. Vi ne atendas konstrui viajn proprajn kradaj funkcioj. Homoj pasigas siajn tezo pri tiuj aferoj. Do ne zorgu pri konstruado via propra. Trovu unu linio por komenci kun. Iujn el ili vi devas manipuli iomete certigi reveno tipoj kongruas supren kaj whatnot, do en la komenco, Mi rekomendus uzi ion vere facila ke eble nur hashes je la unua litero. Kaj tiam tuj vi energio, korpigante malvarmaj hash funkcio. Mmhmm? Publiko: Ĉu oni provu esti aŭ efika sed nur malfacile, like-- SPEAKER 1: Do provi, mi kredas, Estas intuicie malfacile implementar sed estas tre rapida. Tamen, ĝi prenas supren pli spaco. Denove, vi povas optimizar ambaŭ de tiuj en malsamaj manieroj kaj ekzistas manieroj to-- Publiko: Kiel ni gradita pri tio? Ĉu matter-- SPEAKER 1: Do vi gradita normala maniero. Vi tuj estos gradita en dezajno. Kien ajn vi faras, vi volas certigi ĝi estas tiel eleganta kiel ĝi povas esti kaj kiel efika kiel ĝi eblas. Sed se vi elektas provi aŭ hash tablo, tiel longe kiel ĝi funkcias, ni estas feliĉaj kun tio. Se vi uzas iun kiu hashes sur la unua litero, estas bone, kiel eble kiel dezajno-saĝa. Ni ankaŭ atingante la punkto en ĉi semester-- Mi ne scias, ĉu vi infanoj noticed-- se vi estas pset kvalifikojn declinar iomete pro dezajno kaj whatnot, tio tute bone. Fariĝas al punkto kie via programoj iĝas pli komplika. Ekzistas pli lokoj Vi povas plibonigi plu. Do estas tute normala. Ĝi ne estas ke vi estas fari malbone vian pset. Estas nur ni esti malfacile al vi nun. Do ĉies sentante ĝin. Mi ĵus gradigita via tuta psets. Mi scias ke ĉiuj sentas ĝin. Do ne estus zorginta pri tio. Kaj se vi havas demandojn pri antaŭ psets aŭ manieroj vi povas plibonigi, Mi provu komenti la specifa lokoj, sed kelkfoje ĝi estas malfrua kaj min tedas. Ĉu estas aliaj aferoj pri datumstrukturoj? Mi certas ke vi uloj ne vere volas paroli pri ili anymore, sed se estas, mi estas feliĉa iri super ili, tiel kiel ion el prelego tiu pasinteco semajno aŭ pasintsemajne. Mi scias pasintsemajne estis tuta revizio, do ni saltis super iu recenzo el prelego. Ajna alia demandojn mi povas respondi? OK, tute certe. Nu, vi uloj eliri 15 minutoj frue. Mi esperas ĉi estis duone helpemaj almenaŭ, kaj mi vidos vin infanoj venontan semajnon, aŭ ĵaŭdo oficejo horoj. Ĉu ekzistas petas por manĝetoj por la venonta semajno, estas la afero? Ĉar mi forgesis dolĉaĵoj hodiaŭ. Kaj Mi venigis dolĉaĵoj lasta semajno, sed estis Columbus Day, tiel estis kiel ses personoj kiuj havis kvar sakojn de dolĉaĵoj al si. Mi povas venigi Starbursts denove se vi ŝatas. Starbursts? OK, sonas bone. Havas grandan tagon, knaboj.