Parolanto 1: Bone, do ni estas dorso. Bonvenon CS50. Jen la fino de semajno sep. Do memoru ke lasta fojo, ni komencis rigardas iomete pli kompleksa datumstrukturoj. De supre ĝis nun, ĉio ni havis vere je nia dispono, estis jena: tabelo. Sed antaŭ ol ni forĵeti la tabelo kiel ne cxion, kio interesa, kiu efektive efektive estas, kiaj estas kelkaj el la pluses de tiu simpla datumoj strukturon tiel multe? Kio estas tio bona? Ĝis nun, kiel ni vidis? Kion vi havas? Nenio. Lernanto: [inaudibles]. Parolanto 1: Kio estas tio? Lernanto: [inaudibles]. Parolanto 1: Fiksa grandeco. Bone, do kial estas fiksita grandeco bona kvankam? Lernanto: [inaudibles]. Parolanto 1: Bone, do ĝi estas efika en la senso ke oni povas atribui al fiksa sumo de spaco, kiu espereble Estas ĝuste tiel spaco kiel vi volas. Por ke povus esti absolute a alpago. Kio estas alia ĉe flanko de tabelo? Jes? Lernanto: [inaudibles]. Parolanto 1: Ĉiuj - sorry? Lernanto: [inaudibles]. Parolanto 1: Ĉiuj skatoloj en memoro aŭ apud la alia. Kaj tio estas utila - kial? Tio estas tute vera. Sed kiel ni povas ekspluati kiun veron? Lernanto: [inaudibles]. Parolanto 1: Ekzakte, ni povu kontroli kiu kie ĉiu estas nur sciante unu adreso, nome la adreso de la unua bitoko de tiu eron de memoro. Aŭ en la kazo de la kordo, la adreso de la unua char en tiu linio. Kaj de tie, ni povas trovi la finon de la kordo. Ni povas trovi la dua elemento, la tria elemento, kaj tiel plu. Kaj tial la ornama metodo de priskribi ke trajto estas ke arrays doni al ni hazarda aliron. Nur uzante la kvadrata krampo skribmaniero kaj numero, vi povas salti al specifa elemento en la tabelo en konstanta tempo, granda O de unu, por tiel diri. Sed jam pasis kelkaj downsides. Kio tabelo ne tre facile? Kio estas tio Ne bona? Lernanto: [inaudibles]. Parolanto 1: Kio estas tio? Lernanto: [inaudibles]. Parolanto 1: Pligrandigi en grandeco. Do la downsides de la tabelo estas precize la malo de kion la upsides estas. Do unu el la downsides estas ke ĝi estas fiksa grandeco. Do vi ne povas vere kreski ĝin. Vi povas reallocate pli grandan parton de memoro, kaj poste movi la malnovaj elementoj en la nova tabelo. Kaj poste libera la malnova tabelo, por Ekzemple, uzante malloc aŭ similan funkcio nomita realloc, kiu reallocates memoro. Realloc, kiel flanken, provas doni al vi memoro kiu estas apud la tabelo ke vi jam havas. Sed ĝi povus movi aĵojn ĉirkaŭ aro. Sed en mallonga, tio estas multekosta, ĉu ne? Ĉar se vi havas eron de memoro de tiun grandecon, sed vi vere volas unu de tiu grandeco, kaj vi volas konservi la originalaj elementoj, vi havas proksimume lineara tempo kopiado procezo kiu bezonas por pasi de malnova tabelo al nova. Kaj la realo estas demandi la mastruma sistemo denove kaj denove kaj denove por grandaj pecoj da memoro povas komenci kostos vin iom da tempo ankaŭ. Do ĝi estas tiel benon kaj malbenon en maski, la fakto ke tiuj arrays estas de fiksa grandeco. Sed se ni enkonduki anstataŭ io kiel tiu, kiun ni nomas kunligita listo, ni preni kelkajn upsides kaj kelkaj downsides tie ankaŭ. Do ligitaj listo estas simple datumoj strukturo formita de C structs en ĉi kazo, kie struct, revokon, estas nur ujo por unu aŭ pli specifajn tipojn de variabloj. En ĉi tiu kazo, kion fari la datumtipoj ŝajnas esti ene de la struct ke lasta tempo ni nomas nodon? Ĉiu de ĉi tiuj ortanguloj estas nodo. Kaj ĉiu el la plej malgrandaj ortanguloj ene de ĝi estas datumtipo. Kio tipoj ni diru ili estis lunde? Jes? Lernanto: [inaudibles]. Parolanto 1: A ŝanĝiĝema kaj puntero, aŭ pli specife, la int, por n, kaj puntero malsupre. Ambaŭ el tiuj hazarde estas 32 bitoj, ĉe Almenaŭ en komputilo kiel ĉi CS50 Aparato, kaj tiel ili estas desegnita same en grandeco. Do kio estas uzanta la puntero kvankam por ŝajne? Kial aldoni tiun sagon nun kiam arrays estis tiom bela kaj pura kaj simpla? Kio estas la puntero fari por ni en ĉiu el tiuj nodoj? Lernanto: [inaudibles]. Parolanto 1: Ekzakte. Oni diras al vi kie la sekvanta oni estas. Do mi specon de uzi la analogio de uzante fadeno ordigi de enhebrar tiuj nodoj kune. Kaj tio estas ĝuste kion ni faras kun montriloj ĉar ĉiu el tiuj pecoj de memoro povas aŭ ne esti Bela, malantaŭo al malantaŭo apogi ene de RAM, ĉar ĉiufoje kiam vi voki malloc dirante: donu al mi sufiĉe bajtoj por nova nodo, ĝi povus esti ĉi tie aŭ povus esti ĉi tie. Povus esti ĉi tie. Povus esti ĉi tie. Vi simple ne scias. Sed uzante indikoj en la adresojn de tiujn nodojn, vi povas punkto ilin kune en maniero kiu similas vide kiel lerta eĉ se ĉi tiuj aferoj estas ĉiuj etendis en viaj unu aŭ viaj du aŭ vian kvar gigabajtoj de RAM ene de via propra komputilo. Do la malavantaĝo, ĉar, de lerta kunligita estas kio? Kio estas prezo ni estas ŝajne pagi? Lernanto: [inaudibles]. Parolanto 1: Pli spaco, ĉu ne? Ni, en ĉi tiu kazo, duobligis la kvanto de spaco ĉar ni foriris de 32 bitoj por ĉiu nodo, por ĉiu int, tiel nun 64 bitoj ĉar ni devos teni ĉirkaŭ puntero tiel. Vi ricevas pli efikeco se via struct estas pli granda ol tiu simpla afero. Se vi efektive havas studento ene el kiuj estas paro de ŝnuroj por nomo kaj domo, eble oni ID numeron, eble iuj aliaj kampoj entute. Do se vi havas sufiĉe granda struct, tiam eble la kosto de la puntero estas Ne tia granda interkonsento. Tiu estas iom de angulo kazo en tiu ni stokante tia simpla komenca ene de la ligitaj listo. Sed la punkto estas la sama. Vi certe pasi pli memoro, sed vi fariĝas fleksebleco. Ĉar nun se mi volas aldoni elementon komence de ĉi tiu listo, Mi devas atribui nova nodo. Kaj mi devas nur ĝisdatigi tiujn sagoj iel por nur movas iuj indikoj ĉirkaŭe. Se mi volas enmeti ion en la Meze de la listo, mi ne devas puŝi ĉiuj flanken kiel ni faris en semajnoj estinteco kun niaj volontuloj kiuj reprezentis tabelo. Mi povas nur atribui nova nodo kaj tiam simple notas la sagoj en malsamaj direktoj ĉar ĝi ne devas resti en reala memoro veran linion kiel mi desegnis ĝin ĉi tie en la ekrano. Kaj poste laste, se vi volas enmeti ion al la fino de la listo, estas eĉ pli facila. Ĉi tiu estas speco de arbitra skribmaniero, sed 34 La pointer, prenu konjekton. Kiu estas la valoro de lia puntero plej verŝajne desegnita ia kiel malnova lernejo anteno tie? Lernanto: [inaudibles]. Parolanto 1: Estas probable nula. Kaj ĝuste tiu estas unu aŭtoro reprezento de nula. Kaj estas nulaj ĉar vi absolute bezonas scii kie la fino de kunligita listo estas, ke vi observu sekva kaj sekvante kaj sekvante tiujn sagoj al iu rubo valoro. Do nula estos signifi ke ne estas pli nodoj al la rajto de la numero 34, en ĉi tiu kazo. Do ni proponas ke ni povas apliki tiu nodo en kodo. Kaj ni vidis tian de sintakso antaŭe. Typedef ĝuste difinas nova tipo por ni, donas al ni sinonimo kiel kordo estis por char *. En tiu kazo, ĝi tuj doni al ni stenografio skribmaniero por ke struct nodo povas anstataŭ simple esti skribita kiel nodo, kiu estas multe pli pura. Ĝi estas multe malpli verbose. Ene de nodo estas ŝajne int vokis n, kaj tiam struct nodo * kio signifas ekzakte kion ni deziris la sagojn por signifi, puntero al alia nodo de la ĝusta sama datumtipo. Kaj mi proponas ke ni povus efektivigi serĉo funkcio kiel tiu, kiu en unuavide povus ŝajni iom kompleksa. Sed ni vidu ĝin en kunteksto. Permesu al mi iri al la aparato tie. Permesu al mi malfermi dosieron nomatan Listo nula punkto h. Kaj tio nur enhavas la difinon ni nur vidis antaŭ momento por ĉi datumoj tipo nomita nodo. Do ni metis tiun en dot h dosiero. Kaj kiel flanken, kvankam ĉi programo kiu vi estas, por vidi estas Ne ĉiuj kiuj kompleksaj, estas ja konvencion kiam skribi programon por meti aĵojn kiel datumtipoj, tiri konstantoj kelkfoje, ene de via header dosiero kaj ne nepre en via C dosiero, certe kiam via programoj akiri pli kaj pli grandaj, tiel ke vi scias kie serĉi ambaŭ por dokumentaro en kelkaj kazoj, aŭ por fundamentojn kiel ĉi tio, la difino de iu tipo. Se mi nun malfermi liston nula punkto c, rimarki kelkajn aferojn. Ĝi inkludas kelkajn header files, plej pri kiu ni vidis antaŭe. Ĝi inkludas lia propra header dosiero. Kaj kiel flanken, kial tio estas duobla citilojn tie, kontraste al la angulo krampoj en la linio kiu Mi reliefigis tie? Lernanto: [inaudibles]. Parolanto 1: Jes tuj kiam estas loka dosiero. Do, se ĝi estas loka dosiero de via propra ĉi tie on line 15, ekzemple, oni uzas citiloj anstataŭ de la angled krampoj. Kaj jen estas ia interesa. Rimarku, ke mi deklaris tutmonda variablo en tiu programo on line 18 nomita unue, la ideo esti ĉi estas tuj estos referenco al la unua nodo en mia ligillisto, kaj mi havas inicializado ĝin al nula, ĉar mi havas ne asignitaj ajna reala nodoj nur ankoraŭ. Do tio reprezentas, pictóricamente, kion ni vidis antaŭ momento en la bildo kiel ke puntero sur la fora forlasis flanko. Do nun, ke puntero ne havas sagon. Ĝi anstataŭe estas nur nula. Sed reprezentas kio estos la adreso de la unua efektiva nodo en tiu listo. Do mi implementado ĝi estas tutmonda ĉar, kiel vi vidas, ĉiuj ĉi programo faras en la vivo estas implemento lerta kunligita por mi. Nun mi havas kelkajn prototipojn tie. Mi decidis apliki karakterizaĵoj kiel forigo, inserción, serĉado, kaj trairado - la lasta nur esti promenado tra la listo, presi el ĝiaj eroj. Kaj nun jen mia ĉefa rutino. Kaj ni ne pasigas tro da tempo sur tiuj ekde ĉi tiu estas speco de, mi esperas malnova ĉapelo de nun. Mi tuj faros la sekvajn, dum la uzanto kunlaboras. Do, mi tuj presi tiun menuon. Kaj mi formatita kiel pure kiel mi povis. Se la uzanto tajpas en unu, tio signifas ili volas forigi ion. Se la uzanto tajpas en du, kiu signifas ili volas enŝovu ion. Kaj tiel plu. Mi tuj poste instigas tiam por komando. Kaj poste mi iros por uzi GetInt. Do tiu estas vere simpla menuing interfaco kie vi nur devas tajpi nombro surĵeto al unu el tiuj komandoj. Kaj nun mi havas belan pura ŝaltilo aserto, ke tuj ŝalti kion ajn la uzanto tajpas in Kaj se ili tajpis unu, mi instruos vin voki forviŝi kaj rompi. Se ili enigis du, mi instruos vin voki insertar kaj rompi. Kaj nun rimarki Mi metis ĉiu de ĉi tiuj sur la sama linio. Ĉi tio estas nur stila decido. Tipe ni vidis ion kiel ĉi tio. Sed mi ĵus decidis, sincere, mia programo aspektis pli legebla ĉar estis nur kvar kazoj nur printi ĝin kiel ĉi tio. Plene legitima uzo de stilo. Kaj mi faros ĉi tiel longe kiel la uzanto ne tajpis nulo, kiun mi decidis signifos ili volas forlasi. Do nun rimarkas kion mi tuj faros ĉi tie. Mi tuj liberigi la listo ŝajne. Sed pli sur tiu en nur momento. Ni unue kuri ĉi tiu programo. Do lasu min fari pli grandan fina fenestro, ĝi pentras oblikvo listo 0. Mi tuj iros antaŭen kaj enmeti per tajpante du, numero kiel 50, kaj nun vi vidos la listo estas nun 50. Kaj mia teksto nur scrolled supren iom. Do nun rimarkas la listo enhavas la nombro 50. Ni faru alian insert per prenante du. Ni entajpi la numeron kiel unu. Listo estas nun unu, sekvita de 50. Do tiu estas nur teksta prezento el la listo. Kaj ni enigi pli numeron kiel la numero 42, kiu estas espereble tuj finos en la mezo, ĉar tiu programo en aparta klaso ĝin elementoj kiel ĝi enmetas ilin. Do ni havas ĝin. Super simpla programo kiu povis absolute uzis tabelo, sed mi okazi esti uzanta ligillisto nur tiel mi povas dinamike kreski kaj retiri ĝin. Do ni rigardu por serĉo, se mi kuri komando tri, mi volas serĉi por, ni diru, la numero 43. Kaj nenio ŝajne trovis, ĉar mi reiris neniu respondo. Do ni faru ĉi denove. Serĉi. Ni serĉu 50, aŭ pli ĝuste serĉi por 42, kiu havas belan iom subtila signifon. Kaj mi trovis la signifon de la vivo tie. Numero 42, se vi ne scias, la referenco, Google ĝin. Ĉio bone. Do kio tiu programo farita por mi? Ĝi simple permesis al mi enmeti tiel for kaj serĉo de elementoj. Ni rapide antaŭen, tiam, tiu funkcio ni rigardis lundon kiel teaser. Do tiu funkcio, mi asertas, serĉoj por elementon en la listo per unua unu, instigante la uzanto kaj tiam nomante GetInt akiri realan int ke vi volas serĉi. Tiam rimarki tion. Mi tuj kreos provizoran variablo en linio 188 nomis puntero - PTR - povus esti nomata ĝi nenion. Kaj ĝi estas puntero al nodo ĉar mi diris nodo * tie. Kaj mi inicializar ĝin esti egala al unua tiel, ke mi efektive havas mian fingro, por tiel diri, en la tre unua ero de la listo. Do, se mia dekstra mano jen PTR mi montrante la saman aferon tiu unua notas ĉe. Do nun denove en kodo, kio okazas poste - ĉi tiu estas komuna paradigmo kiam ripetanta super strukturo kiel ligitaj listo. Mi tuj faros la sekvajn dum pointer ne estas egala al nula Do dum mia fingro ne montras al iuj nulaj valoro, se puntero sago n egalas n. Ni rimarkas unue ke n estas kion la uzanto tajpita en po GetInts nomas ĉi tie. Kaj puntero sago n signifas kion? Nu, se ni reiru al la bildo tie, se mi havas fingro montrante tiu unua nodo enhavas naŭ, la sago esence signifas iri al tiu nodo kaj ekpreni la valoro je situo n, en ĉi tiu kazo, la datumoj kampo nomata n. Kiel flanken - kaj ni vidis tiun paron de semajnoj kiam iu demandis - tiu sintakso estas nova, sed ne doni al ni povojn kiujn ni ne jam havas. Kio estis tiu frazo ekvivalenta al uzante dot notacio kaj stelo paro de semajnoj, kiam ni senŝeligita reen ĉi tiu mantelo iom antaŭtempe? Lernanto: [inaudibles]. Parolanto 1: Ekzakte, estis stelo, kaj tiam estis stelo dot n, kun parentezoj tie, kiu aspektas, sincere, mi pensas multe pli kripta legi. Sed stelo pointer, kiel ĉiam, per iri tien. Kaj kiam vi estas tie, kio datumoj kampo vi volas aliri? Nu vi uzas la skalara skribmaniero por aliri oni structs datumoj kampon, kaj mi specife volas n. Sincere, mi argumentas ĉi estas nur malfacile legi. Estas pli malfacile memoras kie do la parantezoj iru, la stelo kaj ĉiuj tion. Do la mondo adoptis iujn sintaksa sukero, por tiel diri. Nur sexy maniero diri, ĉi tiu estas ekvivalento, kaj eble pli intuicia. Se puntero estas ja pointer, la saga skribmaniero signifas iri tien por trovi la kampo en tiu kazo nomata n. Do, se mi trovas ĝin, rimarkos, kion mi faros. Mi simple presi, mi trovis procento i, ŝtopanta en la valoro por int. Mi nomas dormi por dua nur speco de paŭzo aĵoj en la ekrano por doni al la uzanto dua sorbi kio ĵus okazis. Kaj tiam mi rompos. Alie, kion mi faru? Mi ĝisdatigos puntero al egala pointer sago tuj. Do nur por esti klara, tio signifas iri tie, uzante mian malnovan-lernejo skribmaniero. Do tio nur signifas iri al kiom vi fingromontrante, kio en la tre unua kazo estas mi indik la struct kun naŭ en ĝi. Do mi iris tie. Kaj tiam la skalara skribmaniero signifas, atingi la valoro je proksimaj. Sed la valoro, kvankam ĝi estas desegnita kiel mallarĝa, estas nur nombro. Ĝi estas nombraj adreso. Do ĉi tiu linio de kodo, ĉu skribita kiel ĉi tio, la pli kripta maniero, aŭ kiel ĉi tio, la iomete pli intuicia maniero, nur signifas movi mian manon de la unua nodo al la sekva, kaj tiam la sekva, kaj tiam la sekva, kaj tiel plu. Do ni ne loĝas sur la alia realigoj de enigi kaj forigi kaj trairado, la du unuaj de kiuj estas sufiĉe implikitaj. Kaj mi kredas ke estas sufiĉe facile akiri perdis farinte ĝin parole. Sed kion ni povas fari ĉi tie estas provi determini kiel bona por fari ĉi vide. Ĉar mi proponus, ke se ni volas enmeti elementojn en tiun ekzistanta listo, kiu havas kvin elementoj - 9, 17, 22, 26, kaj 33 - se mi tuj apliki tion en kodo, mi bezonas konsideri kiel iri pri fari ĉi tion. Mi proponus porti bebon paŝoj per kiu, en tiu kazo mi volas diri, kio estas la eblaj scenaroj, ke ni povus renkonti ĝenerale? Kiam apliki insert por kunligita listo, tiu simple okazas al esti specifa ekzemplo de grandeco kvin. Nu, se vi volas enmeti numeron, kiel diras la nombro unu kaj subteni ordo ordo, kie evidente plenumas la numero oni bezonas iri en ĉi tiu specifa ekzemplo? Kiel en la komenco. Sed kio estas interesa estas ke se vi volas enmeti unu en tiun listo, kion speciala puntero bezonas esti ĝisdatigita ŝajne? Unua. Do mi dirus, tiu estas la unua kazo ke ni volas konsideri, oni scenaro engaĝante enmeto en la komenco de la listo. Ni desxiri ekstere eble estas tiel facila aŭ eĉ facilan kazon, relative parolas. Supozu mi volas enmeti la numero 35 en ordo ordo. Ĝi evidente apartenas tie. Do kio puntero evidente tuj devas esti ĝisdatigita en tiu scenaro? 34 La puntero igante ne nula sed la adreso de la struct enhavanta la nombron 35. Do jen kazo du. Do jam mi estas speco de cuantizando kiom da laboro mi devas fari ĉi tie. Kaj fine, la evidenta mezo kazo estas ja, meze, se mi volas enŝovu iun kiel diras 23, kiu iras inter la 23 kaj la 26, sed nun aĵoj iom pli implikitaj pro kio montriloj bezonas esti ŝanĝita? Do 22 evidente bezonas esti ŝanĝita ĉar li ne povas atentigi al 26 anymore. Li bezonas atentigi al la nova nodo ke Mi devos atribui nomante malloc aŭ iu ekvivalento. Sed tiam mi ankaŭ bezonas, ke nova nodo, 23 en ĉi tiu kazo, havi lian puntero indik kiu? 26. Kaj tuj esti ordo de operacioj tie. Ĉar se mi tion faras malsagxe kaj mi ekzemple komenco komence de la listo, kaj mia celo estas enigi 23. Kaj mi kontrolu, ĉu ĝi apartenas ĉi tie, proksime naŭ? No Ĉu ĝi apartenas ĉi tie, apud 17? No Ĉu ĝi apartenas tie apud 22? Jes. Nu, se mi estas malsaĝa tie, kaj ne pensante ĉi, Mi povus destini mia nova nodo por 23. Mi povus ĝisdatigi la puntero de la nodo vokis 22, montrante ĝin ĉe la nova nodo. Kaj tiam kion mi devas ĝisdatigi la nova nodo puntero esti? Lernanto: [inaudibles]. Parolanto 1: Ekzakte. Indik 26. Sed damne, se mi ne jam ĝisdatigi 22 La puntero atentigi en ĉi ulo, kaj nun mi havas orfoj, la resto de la listo, tiel diri. Do ordo de operacioj tie tuj estos grava. Por fari tion mi povus sxtelu; diru, ses volontuloj. Kaj vidu se ni ne povas fari ĉi vide anstataŭ kodo-saĝa. Kaj ni havas kelkajn belajn streso pilkoj por vi hodiaŭ. OK, kiel pri unu, du, en la reen - sur la pinto tie. tri, kvar, ambaŭ de vi infanoj je la fino. Kaj kvin, ses. Certe. Kvin ses. Bone kaj ni venos al vi infanoj proksima fojo. Bone, venu supren. Bone, ĉar vi ĝis tie unue, vi ŝatus esti tiu mallerte en Google Vitra tie? Bone, do, bone, Pokalo, gravuri video. OK, vi estas bona iri. Bone, do se vi infanoj povas veni pli ĉi tie mi preparis anticipe iujn numerojn. Bone, venu al ĉi tie. Kaj kial vi ne iru iom plu tiel. Kaj vidu, kio estas via nomo, kun la Google Vitra? Lernanto: Ben. Parolanto 1: Ben? OK, Ben, vi estos la unua, laŭvorte. Do ni tuj sendos al la fino de la scenejo. Bone, kaj via nomo? Lernanto: Jason. Parolanto 1: Jason, OK vi instruos vin esti numero naŭ. Do se vi volas sekvi Ben tiu vojo. Lernanto: Jill. Parolanto 1: Jill, vi tuj estos 17, kiu se mi faris tion pli inteligente, mi havus komenciĝis ĉe la alia fino. Vi iras tiun vojon. 22. Kaj vi estas? Lernanto: Maria. Parolanto 1: Mary, vi estos 22. Kaj via nomo estas? Lernanto: Chris. Parolanto 1: Chris, vi estos 26. Kaj poste persiste. Lernanto: Diana. Parolanto 1: Diana, vi estos 34. Do vi venu ĉi tien. Bone, do perfektigi ordo ordigi jam. Kaj ni iru antaŭen kaj faros cxi tiel ke ni povas vere - Ben vi estas nur speco de rigardi Tra nenie tie. Bone, do ni iru antaŭen kaj priskribas tiun uzante armilojn, multe kiel mi estis, precize, kio okazas. Do iru antaŭen kaj dedicxu vin al piedo aŭ du inter vi mem. Kaj iru antaŭen kaj atentigi per unu mano al kiu ajn vi devu indik surbaze de tio. Kaj se vi estas nula nur atentigi rekte sur la plankon. Bone, do bone. Do nun ni havas ligitaj liston, lasu min proponas ke mi ludos la rolon de PTR, do mi ne ĝeni portante ĉi ĉirkaŭe. Kaj poste - iu stulta konvencio - vi povas nomi tiun ion vi volas - antaŭulo pointer, pred puntero - estas nur la alnomon ni donis en nia specimeno kodon al mia maldekstra mano. La alia mano, kiu tuj estos gardi spuri de kiu estas kiu en la post scenejoj. Do supozu, unue, mi volas desxiri ekstere tiu unua ekzemplo de enmeto, diru 20, en la listo. Do mi tuj bezonas iun al enkorpigi la numero 20 por ni. Do mi bezonas malloc iu de la aŭskultantaro. Venu supren. Kio estas via nomo? Lernanto: Brian. Parolanto 1: Brian, ĉiuj rajtas, tiel vi estos la nodo enhavis 20. Bone, venu al ĉi tie. Kaj evidente, kie ne Brian apartenas? Do, en la mezo de - efektive, atendi minuton. Ni faras ĉi paneas. Ni faris ĉi multe pli malfacila ol ĝi bezonas esti en komenco. Bone, ni iras al libera Brian kaj realloc Brian kiel kvin. Bone, do nun ni volas enmeti Brian kiel kvin. Do venu ĉi tien apud Ben por nur momento. Kaj vi povas supozeble diri kie ĉi tiu rakonto tuj. Sed ni zorge pripensi la ordo de operacioj. Kaj estas ĝuste ĉi tiu vida ke tuj laŭliniigi kun tiu specimeno kodo. Do jen mi PTR indikante komence ne je Ben, per, sed je ajn taksas Li enhavas, kiu en ĉi tiu kazo estas - kio estas via nomo denove? Lernanto: Jason. Parolanto 1: Jason, tial ambaŭ Ben kaj mi estas indik Jason en ĉi tiu momento. Do nun mi devas determini, kie ne Brian apartenas? Do la sola afero mi havas aliron al nun estas lia n elemento de datumoj. Do mi iros por kontroli, estas Brian malpli ol Jason? La respondo estas vera. Do kio nun devas okazi, en la ĝusta ordo? Mi bezonas ĝisdatigi kiom da referencoj en tuta en cxi tiu rakonto? Kie mia mano ankoraŭ indik Jason kaj vian manon - se vi volas metu vian manon kiel, ia, mi ne scias, demandosigno. Bone, nu. Bone, do vi havas kelkaj kandidatoj. Aux Ben aŭ mi aŭ Brian aux Jason aŭ ĉiuj aliaj, kiuj montriloj bezonas ŝanĝi? Kiom entute? Bone, do du. Mia puntero ne vere gravas anymore ĉar mi estas nur dumtempa. Do estas tiuj du infanoj, supozeble, ambaŭ Ben kaj Brian. Do mi proponas ke ni ĝisdatigi Ben, ĉar li estas unua. La unua ero de tiu ĉi listo nun tuj estos Brian. Do Ben punkto je Brian. OK, nun kion? Kiu akiras notita al kiu? Lernanto: [inaudibles]. Parolanto 1: Bone tiel Brian havas atentigi ĉe Jason. Sed mi miskalkulis ke puntero? Ĉu mi scias, kie Jason estas? Lernanto: [inaudibles]. Parolanto 1: Mi faros, kiam mi estas la provizora puntero. Kaj supozeble mi ne ŝanĝiĝis atentigi ĉe la nova nodo. Do ni povas simple havi Brian punkto en kiu ajn mi fingromontrante. Kaj ni faris. Do kazo, inserción en la komencante de la listo. Estis du ŝlosilaj paŝoj. Unu, ni devas ĝisdatigi Ben, tiam ni ankaŭ devas ĝisdatigi Brian. Kaj tiam mi ne devas ĝeni traipsing tra la resto de la listo, ĉar ni jam trovis sian situo, ĉar li apartenis al la maldekstre de la unua ero. Bone, do sufiĉe simpla. Fakte, ĝi sentas kiel ni estas preskaŭ farante ĉi tro komplika. Do ni nun desxiri ekstere de la fino el la listo, kaj rigardu, kie la komplekseco startas. Do se nun mi alloc de la aŭskultantaro. Ĉiu volas ludi 55? Bone, mi vidis vian manon unue. Venu supren. Jes. Kio estas via nomo? Lernanto: [inaudibles]. Parolanto 1: Habata. OK, venu supren. Vi estos la nombro 55. Do vi, kompreneble, ili apartenas fine de la listo. Do ni Replay la simulado kun mi esti la PTR por nur momento. Do mi unue iri al punkto en kion ajn Ben estas indik. Ni ambaŭ montrante nun Brian. Do 55 estas ne malpli ol kvin. Do mi tuj ĝisdatigi min per indikante Brian sekva pointer, kiu nun estas kompreneble Jason. 55 Ne malpli ol naŭ, tiel Mi tuj ĝisdatigi PTR. Mi tuj ĝisdatigi PTR. Mi tuj ĝisdatigi PTR Mi tuj ĝisdatigi PTR. Kaj mi tuj - hmm, kio estas Via nomo denove? Lernanto: Diana. Parolanto 1: Diana notas, kompreneble, ĉe nula per sia maldekstra mano. Do kie faras Habata reale apartenas klare? Al la maldekstra, ĉi tie. Do kiel mi scias meti sxin tie Mi kredas ke mi ŝraŭbita supren. Ĉar kio estas PTR arto ĉi tiu momento en tempo? Nula. Do kvankam, vide, ni povas evidente vidi ĉiujn tiujn infanoj tie sur la scenejo. Mi ne gardis spuro de la antaŭa persono en la listo. Mi ne havas fingron markante, en ĉi tiu kazo, la nodo numero 34. Do ni vere komencos tion. Do nun mi vere ne bezonas duan loka variablo. Kaj jen estas, kion vi vidos en la reala specimeno C kodo, kie kiel mi foriras, kiam mi ĝisdatigos mian dekstran manon por noti Jason, tiel lasante Brian malantaŭe, mi pli bone komenci per mia maldekstra mano ĝisdatigi kie mi estis, tiel ke, kiel mi foriras tra ĉi tiu listo - pli mallerte ol mi intencis nun tie vide - Mi tuj alvenos al la fino de la listo. Tiu mano ankoraŭ estas nula, kiu estas sufiĉe senutila, krom por indiki Mi estas klare al la fino de la listo, sed nun almenaŭ mi havas antaŭulo puntero indikante ĉi tie, do nun kio manoj kaj kio montriloj bezonas esti ĝisdatigita? Kies mano vi volas por reagordi unua? Lernanto: [inaudibles]. Parolanto 1: Bone, do Diana aj jaroj. Kie vi volas atentigi Diana la maldekstra puntero at? Je 55, supozeble, por ke ni insertos tie. Kaj kie devus 55 puntero iras? Malsupren, reprezentante nula. Kaj de miaj manoj, je ĉi tiu punkto, ne gravas ĉar ili estis nur temporal variabloj. Do nun ni faris. Do la aldonan komplekseco tie - kaj ĝi ne estas tiel malfacila por apliki, sed ni bezonas malĉefan variablo fari certa, ke antaŭ ol mi movi mian rajton Unuflanke, mi ĝisdatigos la valoro de mia maldekstra mano, pred puntero en ĉi tiu kazo, tiel ke mi havas trenante puntero konservi spuron de kie mi estis. Nun kiel flanken, se vi pensas ĉi tra, tiu sentas kiel ĝi estas iom ĝena devos konservi spuri de ĉi tiu maldekstra mano. Kion farus alian solvon al tiu problemo estis? Se vi alvenis al restrukturi la datumoj strukturo ni parolas tra ĝuste nun? Se tio nur speco de sentas iom ĝena havi, ŝati, du montriloj irante tra la listo, kiu alia povus esti, en ideala mondo, subtenitaj informo kiun ni bezonas? Jes? Lernanto: [inaudibles]. Parolanto 1: Ekzakte. Ĝuste tiel ne estas vere interesa ĝermo de ideo. Kaj ĉi tiu ideo de antaŭa pointer, montrante la antaŭa ero. Kio se Mi nur enkorpigita ke ene de la listo mem? Kaj ĝi tuj estos malfacile bildigi ĉi tio sen tuta papero fali sur la plankon. Sed supozu ke tiuj infanoj uzis ambaŭ de siaj manoj havi antaŭan pointer, kaj proksima pointer, tiamaniere apliki kion ni vokos duoble ligitaj listo. Tio permesus min ordigi de rebobinado, multe pli facile sen mi, la programisto, devi teni spuri permane - vere permane - el kie mi estis estinta antaŭe en la listo. Do ni ne faros tion. Ni tenu gxin simpla ĉar tio tuj venos al prezo, duoble da spaco por la montriloj, se vi volas dua. Sed tio estas ja komuna datumstrukturo konata kiel duoble ligitaj listo. Ni faros la fina ekzemplo tie kaj meti ĉi tiuj infanoj el ilia mizero. Do malloc 20. Venu supren for de la koridoro tie. Bone, kio estas via nomo? Lernanto: [inaudibles]. Parolanto 1: Pardonu? Lernanto: [inaudibles]. Parolanto 1: Demeron? OK veni supren. Vi estos 20. Vi evidente tuj apartenas inter 17 kaj 22. Do mi lernas mian lecionon. Mi tuj komencos puntero indik Brian. Kaj mi tuj devos mia maldekstra mano nur ĝisdatigi al Brian kiel Mi movi al Jason, kontrolanta faras 20 malpli ol naŭ? No Estas 20 malpli ol 17? No Estas 20 malpli ol 22? Jes. Do kio montriloj aŭ manoj bezonas ŝanĝi kie ili estas montrante nun? Do ni povas fari 17 indik 20. Por ke estas bone. Kie ni volas atentigi via puntero nun? Je 22. Kaj ni scias, kie 22 estas, denove dankon al mia provizora puntero. Do ni estas okej tie. Do pro tio provizora stokado Mi tenis spuro de kie ĉiuj estas. Kaj nun vi povas vide iru en kie vi apartenas, kaj nun ni bezonas 1, 2, 3, 4, 5, 6, 7, 8, 9 streso pilkoj, kaj ronda da aplaŭdoj por ĉi tiuj infanoj, se ni povus. Bele farita. [Aplaŭdo] Parolanto 1: Bone. Kaj vi rajtas konservi la pecoj de papero kiel mementos. Bone, do, fidu min ĝi estas multe facile marŝi tra tiu kun homoj ol estas kun reala kodo. Sed kion vi trovos en nur momenton nun, estas tiu sama - ho, dankon. Dankon - estas ke vi trovos ke la samaj datumoj strukturo, lerta kunligita, ĉu vere esti uzata kiel konstruaĵo bloko al eĉ pli kompleksa datumstrukturoj. Kaj realigi tro la temo estas, ke ni absolute enkondukis pli komplekseco en la efektivigo de ĉi tiu algoritmo. Insertion, kaj se ni iris tra ĝi, protokolo pri forigado kaj serĉado, estas iom pli komplika ol ĝi Estis kun tabelo. Sed ni gajnas iom dinamismo. Ni ricevas adapta datumstrukturo. Sed denove, ni pagas prezon de havi iun aldona komplekseco, ambaŭ en apliki ĝin. Kaj ni rezignis hazarda aliron. Kaj por esti honesta, tie ne estas iu agrabla purigi diapozitivoj mi povas doni al vi, ke diras jen kial ligitaj listo estas pli bona ol tabelo. Kaj lasi ĝin ĉe tio. Ĉar la temo reoccurring nun, eĉ pli en la venontaj semajnoj, estas ke tio ne nepre ĝentilan respondon. Jen kial ni havas la apartan akso de dezajno por problemo aroj. Estos tre kuntekston sentiva ĉu vi volas uzi tiun datumoj strukturo aŭ tiu, kaj volo dependi sur kio gravas al vi en terminoj de rimedoj kaj komplekseco. Sed mi proponas ke la ideala datumoj strukturo, la Holy Grail, estus iu kiu estas konstanta tempo, sendepende de kiom materialo estas interne de ĝi, ĉu ne estus mirinda se datumstrukturo revenis respondojn en konstanta tempo. Jes. Tiu vorto estas en via grandega vortaro. Aŭ ne, tiu vorto ne estas. Nek ion tian problemon tie. Nu vidu, se ni ne povas almenaŭ paŝon al tio. Permesu al mi proponi novan datumstrukturo kiun povas uzi por malsamaj aferoj, en ĉi tiu kazo nomata hash tablo. Kaj tiel ni fakte reen al ekrigardante en tabelo, en ĉi tiu kazo, kaj iom arbitre, mi desegnis tiun hash tablo tiel tablo kun speco de du-dimensia tabelo - aŭ pli ĝuste ĝi estas reprezentita tie kiel du dimensia tabelo - sed tio estas nur tabelo de amplekso 26, tia, ke se ni vokas la tabelo tablo, tabulo krampo nulo estas la rektangulo ĉe la supro. Tabelo krampo 25 estas la rektangulo ĉe la malsupro. Kaj ĉi tiu estas kiel mi povus desegni datumoj strukturo, en kiu mi volas konservi popola nomoj. Tiel ekzemple, mi ne eltiris la tuta afero ĉi tie sur la superkape, se mi havis ĉi tabelo, kiun mi nun iras al voki hash tablon, kaj tiu estas denove situo nulo. Ĉi tie estas situo unu, kaj tiel plu. Mi asertas, ke mi volas uzi ĉi datumoj strukturo, pro diskuto, stoki popola nomoj, Alice kaj Bob kaj Charlie kaj aliaj tiaj nomoj. Tiel pensas pri tiu nun kiel la komencoj de, ekzemple, vortaro kun multe da vortoj. Ili hazarde estas nomoj en nia ekzemplo tie. Kaj jen estas ĉiuj tro germane, eble, apliki sorĉas kontrolilo, kiel ni eble pro problemo starigis ses. Do, se ni havas tabelo de tuta grandeco 26 por ke cxi tiu estas la 25-a loko ĉe la malsupro, kaj mi asertas ke Alico trovas la unua vorto en la vortaro de nomoj kiuj mi volas enmeti en RAM, en ĉi tiu datumstrukturo, kie estas instinktoj diras al vi ke Alicio nomo devus iri en ĉi tiu tabelo? Ni havas 26 ebloj. Kie ni volas meti sxin? Ni volas ke ŝi en krampo nulo, ĉu ne? A por Alico, ni nomas tion nulo. Kaj B estos unu, kaj C estos du. Do ni tuj skribos Alicio nomon ĉi tie. Se ni do enigi Bob, lia nomo iros tien. Charlie iros tien. Kaj tiel plu malsupren tra tiu datumstrukturo. Tio estas mirinda datumstrukturo. Kial? Nu, kio estas la rula tempo de enmeto de homa nomo en tiun datumstrukturo ĝuste nun? Donita ke ĉi tiu tablo estas implementado, vere, kiel tabelo. Nu estas konstanta tempo. Ĝi estas ordo de unu. Kial? Nu kiel vi determini kie Alico apartenas? Vi aspektas en kiu letero de ŝia nomo? La unua. Kaj vi povas atingi tien, se ĝi estas ĉeno, por nur rigardante kordo krampo nulo. Do la nula karaktero de la kordo. Tio estas facila. Ni faris tion en la kripto asigno semajnoj. Kaj tiam tuj sciu ke Alico letero estas ĉefurbo, oni povas subtrahi for 65 aŭ ĉefurbo A sin, kiu donas al ni nulo. Tiel ni nun scias, ke Alico apartenas ĉe situo nulo. Kaj donita puntero al ĉi datumoj strukturon, de iu speco, kiel longe faras ĝin prenu min por trovi situo nulo en tabelo? Nur unu paŝon, dekstra Estas konstanta tempo pro la hazarda aliro ni proponita estis karakteriza de tabelo. Do mallonge, decidi kio la indekso de Alicio nomo estas, kio estas, tiu kazo, estas A, aŭ ni simple solvi ke al nulo, kie B estas unu kaj C estas du, imagante, ke el estas konstanta tempo. Mi nur devas rigardi sian unuan leteron, elŝeligi kie nulo estas tabelo estas ankaŭ konstanta tempo. Do teknike tio kiel du paŝoj nun. Sed tio ankoraŭ konstanto. Do ni nomas tiu granda O de unu, tiel ni insertos Alico en tiun tablon en konstanta tempo. Sed kompreneble, mi esti naiva tie, ĉu ne? Kio se tie estas Aaron en la klaso? Aŭ Alicia? Aŭ ajna alia nomoj komencante per A. Kien ni iras meti tiu persono, ĉu ne? Mi volas diri, nun ekzistas nur tri homoj sur la tablo, do eble ni devus meti al Aaron sur la situo nulo unu du tri. Ĝuste, mi povus meti A tie. Sed tiam, se ni provu enmeti David en tiu listo, kie tio David iris? Nun nia sistemo komencas rompi malsupren, ĉu ne? Ĉar nun Davido finas ĉi tie se Aaron estas efektive tie. Kaj tial nun tiu tuta ideo de havi pura datumstrukturo kiun donas al ni konstanta tempo inserciones ne plu estas konstanta tempo, ĉar mi devas kontroli, ho, damnit, iu estas jam ĉe Alicio loko. Lasu min sondi la resto de ĉi datumoj strukturo, serĉante lokon por meti iu kiel la nomon de Aaron. Kaj por ke tro komencas preni lineara tempo. Cetere, se vi nun volas trovi la Aaron en tiu datumstrukturo, kaj vi kontrolu, kaj Aaron nomo ne estas tie. Ideale, vi simple diru Aaron ne en la datumstrukturo. Sed se vi faras komenci farante lokon por Aaron kie devus esti D aŭ E, vi, plej malbona kazo, devas kontroli la tuta datumstrukturo, en kies kazo devolves en ion lineara en la grandeco de la tablo. Do bone, mi riparos tion. La problemo estas, ke mi havis 26 eroj en ĉi tiu tabelo. Lasu min ŝanĝi ĝin. Whoops. Lasu min ŝanĝi ĝin tiel ke prefere esti de grandeco 26 entute, rimarki la fundo indekso tuj ŝanĝos al n minus 1. Se 26 estas klare tro malgranda por homoj ' nomoj, ĉar tie estas miloj da nomoj de la mondo, ni simple faru en 100 aŭ 1000 aŭ 10.000. Ni nur malŝparas multan pli da spaco. Nu, kiu ne nepre malpliigi la probablo, ke ni ne havas du personoj kun nomoj komencante kun A, kaj tiel, vi tuj provi meti A nomoj en loko nulo ankoraŭ. Ili estas ankoraŭ tuj kolizias, kiu signifas ke ni ankoraŭ bezonas solvon meti Alice kaj Aaron kaj Alicia kaj aliaj nomoj komencante kun A aliloke. Sed kiom de problemo estas tio? Kio estas la probablo ke vi havi kolizioj en datumoj strukturon kiel tiu? Nu, lasu min - ni revenos al tiu demando tie ĉi. Kaj rigardu kiel ni povus solvi ĝin unue. Lasu min eltiri supren tiu propono ĉi tie. Kion ni jxus priskribita estas algoritmo, heŭristika nomita lineara sondado per kiu, se vi provus insertar io tie en ĉi tiu datumoj strukturo, kiu nomiĝas hash tablo, kaj ne estas loko tie, vi vere sondi la datumstrukturo kontrolanta, estas ĉi disponebla? Ĉu ĉi Disponeblaj estas ĉi disponebla? Ĉu tio estas havebla? Kaj kiam fine, vi enmeti la enoficigi ke vi origine intencis aliloke en tiu loko. Sed en la plej malbona kazo, la sola loko eblus la tre fundo de la datumoj strukturo, la fino de la tabelo. Do lineara sondado, en la plej malbona kazo, devolves enen lineara algoritmo kie Aaronon, se li pasas al insertos lasta en ĉi tiu datumstrukturo, li povus kolizias kun tiu unua loko, sed tiam kabo por malbona sorto en la fino. Do tiu estas ne konstanto tempo Holy Grail por ni. Ĉi tiu alproksimiĝo de enmeto de elementoj en oni datumstrukturo nomata hash tablo ne ŝajnas esti konstanta tempo almenaŭ ne en la ĝenerala kazo. Ĝi povas devolve en iu lineara. Do kio se ni solvi koliziojn iom malsame? Do jen pli kompleksa alproksimigi al kio ankoraŭ nomata hash tablo. Kaj per hash, kiel flanken, kion Mi volas diri estas la indico, ke Mi raportis al pli frua. Por hash io povas esti penso de kiel verbo. Do se vi hash Alico estas nomo, kradon funkcio, por tiel diri, devus reveni numero. En ĉi tiu kazo estas nulo se ŝi apartenas al situo nulo, unu, se ŝi apartenas al situo, kaj tiel plu. Do mia hash funkcio tiel nun estis super simpla, nur rigardante la unua letero en ies nomon. Sed hash funkcio prenas kiel enigo iu peco de datumoj, kordo, oni int, kion ajn. Kaj ĝi sputas el tipe numero. Kaj tiu nombro estas kie tiu datumo elemento apartenas en datumstrukturo montrigxos kiel hash tablo. Do nur intuicie, tio estas iomete malsama kunteksto. Tiu fakte estas referenco al ekzemplo engaĝante naskiĝtago, kie povus esti tiom, kiom 31 tagoj en la monato. Sed kion tiu persono decidas fari en kazo de kolizio? Kunteksto nun esti, ne estas kolizio de nomojn, sed kolizio de naskiĝtago, se du personoj havas la saman naskiĝtagon sur la 2-a de oktobro, ekzemple. Lernanto: [inaudibles]. Parolanto 1: Jes, ankaŭ ĉi tie ni havas la utiligante de lertaj kunligitaj. Tiel ĝi aspektas iom alie ol ni tiris ĝin pli frue. Sed ni ŝajne devos tabelo sur la maldekstra flanko. Tio estas unu indico, ĉar neniu aparta kialo. Sed estas ankoraŭ tabelo. Ĝi estas aro de montriloj. Kaj ĉiu el tiuj elementoj, ĉiu el tiuj rondoj aŭ slashes - la oblikvo reprezentas nula - ĉiu de tiuj montriloj estas ŝajne montrante kio datumstrukturo? Al ligitaj listo. Do nun ni havas la kapablon malmola kodon en nia programo la grandeco de la tablo. En tiu kazo, ni scias ke estas neniam pli ol 31 tagoj en monato. Tiel forta kodigo valoron kiel 31 estas racia en tiu kunteksto. En la kunteksto de nomoj, malmola kodigo 26 ne estas senkaŭza ĝin popola nomoj nur starti kun, ekzemple, la alfabeto engaĝante A tra Z. Ni povas Cram ilin ĉiujn en kiun datumoj strukturon tiel longe kiel, kiam ni preni kolizio, ni ne meti la nomojn ĉi tie, ni anstataŭ pensi pri tiuj ĉeloj ne kiel kordoj mem, sed kiel montriloj al, ekzemple, Alice. Kaj tiam Alico povas havi alian puntero al alia nomo komencante per A. Kaj Bob vere iras tien. Kaj se estas alia nomo startanta kun B, li finas ĉi tie. Kaj tiel ĉiu el la elementoj de tiu tablo du, se ni desegnis ĉi tio Iom pli lerte - come on - se ni desegnis ĉi iom pli lerte, nun iĝas adapta datumoj strukturo, kie ne estas malfacila limo sur kiom da elementoj vi povas enmeti en ĝin ĉar se vi ja havas kolizio, ke estas bone. Nur antaŭeniri kaj postglui al kion ni vidis iom antaŭe estis konata kiel lerta kunligita. Nu ni paŭzo por nur momento. Kio estas la probablo de kolizio en la unua loko? Ĝuste, eble mi pli pensas, eble Mi estas super Engineering tiu problemo, ĉar vi scias kion? Jes, mi povas veni supren kun arbitraj ekzemploj sur la supro de mia kapo, kiel Allison kaj Aaronon, sed en realeco, donita uniforma distribuo de enigoj, tio estas iom hazarda inserciones en datumstrukturo, kio vere estas la probablo de kolizio? Nu rezultas, fakte super altaj. Lasu min ĝeneraligi ĉi problemo estas kiel ĉi tio. Do en ĉambro de n CS50 studentoj, kio estas la probablo ke almenaŭ du studentoj en la cxambro havas la saman naskiĝtagon? Do ne estas kion. kelkaj Hund - 200, 300 homoj tie kaj pluraj cent homoj hejme hodiaŭ. Do se vi volis demandi nin kio estas la probablo de du personoj en ĉi tiu ĉambro havante la saman naskiĝtagon, ni povas kompreni tion ĉi. Kaj mi asertas efektive estas du personoj kun la sama naskiĝtago. Ekzemple, ĉu iu havas naskiĝtagon hodiaŭ? Hieraŭ? Morgaŭ? Bone, do ĝi sentas kiel mi iros havi tion fari 363 aŭ tiel plu fojoj por fakte elkompreni se ni faras havi kolizio. Aŭ ni povus simple fari ĉi matematike anstataŭ tediously fari tion. Kaj proponas la sekvajn. Do mi proponas ke ni povus modeligi la probablo de du personoj havanta la sama naskiĝtago kiel la probablon de 1 minus la probablo de neniu, la saman naskiĝtagon. Do por atingi ĉi, kaj ĉi tiu estas nur la ornama metodo por skribi ĉi, por la unua persono en la ĉambron, li aŭ ŝi povas havi iu el la eblaj naskiĝtago supozante 365 tagoj en la jaro, kun pardonpetoj al personoj kun la 29-a de februaro naskiĝtago. Do la unua persono en ĉi tiu ĉambro estas libera havi ajnan numeron de naskiĝtago el la 365 eblecojn por ke ni faros ke 365 dividita per 365, kiu estas unu. La sekva persono en la ĉambron, se la celo estas eviti kolizion, povas nur havi sian naskiĝtagon pri kiel multaj malsamaj eblaj tagoj? 364. Do la dua termino en tiu esprimo estas esence faras ke matematiko por ni per subtrahanta for unu ebla tago. Kaj tiam la sekva tago, la sekva tago, la sekvanta tago malsupren al la tuta nombro de personoj en la ĉambro. Kaj se ni tiam rigardu, kio tiam estas la probablo ne de ĉiuj havanta unika naskiĝtago, sed denove 1 minus ke, kio ni atingos estas esprimo kiu povas tre fancifully aspekti kiel ĉi tio. Sed estas pli interesa rigardi vide. Tio ĉi estas abako kie sur la x-akso estas la nombro de homoj en la ĉambro, la numeron de naskiĝtago. Sur la y-akso estas la probablo de kolizio, du personoj havantaj la saman naskiĝtagon. Kaj la takeaway el tiu kurbo estas ke tuj kiam vi atingos like 40 studentoj, vi estas supren je 90% probablo combinatorically de du homoj aŭ pli havanta la saman naskiĝtagon. Kaj iam vi atingos like 58 homoj estas preskaŭ 100% de la ŝanco de la du homoj en la ĉambro tuj havos la saman naskiĝtagon, kvankam ekzistas 365 aŭ 366 eblaj siteloj, kaj nur 58 personoj en la ĉambro. Nur statistike vi supozeble akiri kolizioj, kiuj en mallonga motivas ĉi tiu diskuto. Ke eĉ se ni preni imago tien, kaj komenci havi tiuj ĉenoj, ni ankoraŭ tuj havas kolizioj. Por ke petegas la demando, kio estas la kosto de fari interpolaciones kaj forigoj en datumstrukturo tiel? Nu mi proponas - kaj mi reiros al la ekrano pli tie - se ni n elementoj en la listo, do se ni provas enmeti n eroj, kaj ni havas kiom da tutaj siteloj? Diru 31 entute siteloj en la kazo de naskiĝtago. Kio estas la maksimuma longo de unu de ĉi tiuj katenoj potenciale? Se denove ekzistas 31 eblaj naskiĝtago en donita monato. Kaj ni nur clumping ĉiuj - fakte tio estas stulta ekzemplo. Ni faru 26an anstataŭe. Do, se efektive havas personoj kies nomojn komenci kun A tra Z, donante ni 26 eblecojn. Kaj ni uzas datumstrukturo kiel tiu, kiun ni ĵus vidis, per kiu ni havas tabelo de montriloj, ĉiu el kiuj notas al ligillisto kie la unua listo estas ĉiuj kun la nomo Alico. La dua listo estas ĉiu kun la enoficigi komencante kun A, komencante kun B, kaj tiel plu. Kio estas la probabla longo de ĉiu el tiuj listoj se ni supozas belan pura dissendo de nomoj A tra Z trans la tuta datumstrukturo? Estas n popolo en la datumstrukturo dividita de 26, se ili estas bele etendis super la tuta datumstrukturo. Do la longecon de ĉiu el tiuj ĉenoj estas n dividita per 26. Sed en granda a skribmaniero, kio estas tio? Kio estas tio vere? Do estas vere nur n, ĉu ne? Ĉar ni diris en la pasinteco, ke uf vi dividi per 26. Jes, en la realo estas pli rapida. Sed en teorio, ne estas fundamente cxio, kion pli rapida. Do ni ne ŝajnas esti tiom multe pli proksima al tiu sankta Grail. Fakte, ĉi tiu estas nur lineara tempo. Heck, je ĉi tiu punkto, kial ni ne nur uzi unu grandega ligitaj listo? Kial ni ne simple uzi unu grandega tabelo por stoki la nomojn de ĉiuj en la ĉambro? Nu, estas tie ankoraŭ ion konvinka pri hash tablo? Ĉu ekzistas ankoraŭ io konvinka pri datumstrukturo kiu similas al tio? Ĉi tiu. Lernanto: [inaudibles]. Parolanto 1: Dekstra, kaj denove se estas nur lineara tempa algoritmo, kaj lineara tempo datumstrukturo, kial mi ne nur stoki ĉies nomon en granda tabelo, aŭ en granda ligitaj listo? Kaj ĉesas fari CS tiel malfacila ol ĝi bezonas esti? Kio estas konvinka pri tio, eĉ kvankam mi gratis gxin? Lernanto: [inaudibles]. Parolanto 1: inserciones ne? Multekosta plu. Do inserciones potenciale povus ankoraŭ esti konstanta tempo, eĉ se via datumoj strukturo similas tiun, tabelo de montriloj, ĉiu el kiuj estas indik potenciale ligillisto. Kiel vi povis atingi konstanto tempo inserción de nomoj? Trae en la antaŭa, ĉu ne? Se ni oferas dezajnon golo de antaŭe, kie ni volis subteni ĉies nomon, ekzemple, ordo, aŭ ĉiuj el la numeroj en la scenejo ordo, supozu ke ni havas unsorted ligitaj listo. Ĝi nur kostas al ni unu aŭ du paŝojn, kiel en la kazo de Ben kaj Brian antaŭe, por enmeti ero ĉe la komenco de la listo. Do, se ni ne zorgas pri ordiga ĉiuj de la nomoj komencante kun A aŭ ĉiuj la nomoj komencante kun B, ni povas ankoraŭ atingi konstanta tempo inserción. Nun suprenrigardinte Alico aŭ Bob aŭ ajna nomo pli ĝenerale estas ankoraŭ kio? Estas granda O de n dividita de 26, en la ideala kazo kie ĉiuj estas unuforme distribuita, kie ekzistas tiom da A kiel estas Z, kiu verŝajne estas nerealisma. Sed tio ankoraŭ lineara. Sed ĉi tie, ni revenu al la punkto de asimptota skribmaniero esti teorie vera. Sed en la reala mondo, se mi pretendas, ke mia programo povas ion fari 26 fojoj rapida ol la via, kies programo vi intencas preferas uzi? Via aŭ mia, kiu estas 26 fojoj pli rapida? Realisme, la persono kies estas 26 fojojn pli rapide, eĉ se teorie nia algoritmoj kuri en la sama asimptota rula tempo. Permesu al mi proponi malsamajn solvo entute. Kaj se tio ne blovu via menso, ni estas el datumstrukturoj. Do tiu estas ĝin trie - speco de stultan nomon. Ĝi devenas retrievals, kaj la vorto estas literumita trie, t-r-i-kaj, pro Kompreneble reakiro sonas trie. Sed tio estas la historio de la vorto trie. Do trie ja estas ia arbo, Kaj ĝi estas ankaŭ ludo de tiu vorto. Kaj eĉ se vi ne povas sufiĉe vidu kun ĉi videbligo, en trie estas arbo strukturitaj, kiel familio arbo kun unu praulo al la kapo kaj multaj de nepoj kaj pranepoj kiel ĝi lasas sur la fundo. Sed ĉiu nodo en trie estas tabelo. Kaj ĝi estas en tabelo - kaj Ni oversimplify dum momento - ĝi estas tabelo, en ĉi tiu kazo, de amplekso 26, kie ĉiu nodo denove estas tabelo de grandeco 26, kie la nula ero en tiu tabelo reprezentas A, kaj la lasta elemento en chiu tia tabelo reprezentas Z. Do mi proponas, do, ke ĉi datumoj strukturo, konata kiel trie, povas esti uzata ankaŭ por stoki vortoj. Ni vidis antaŭ momento kiel povus stoki vortoj, aŭ en ĉi tiu kazo nomojn, kaj ni vidis antaŭe kiel ni povas stoki nombroj, sed se ni enfokusigi nomoj aŭ kordoj ĉi tie, rimarki kio estas interesa. Mi asertas ke la nomo de Maxwell estas ene de ĉi datumstrukturo. Kie vi vidas Maxwell? Lernanto: [inaudibles]. Parolanto 1: Maldekstre. Do kio estas interesa kun ĉi datumoj strukturo estas iom ol tendencas la kordo M-Al-X-W-E-L-L backslash nulo, ĉiuj contiguously, kion vi anstataŭ fari sekvas. Se ĉi tiu estas trie kiel datumstrukturo, ĉiu el kies verticoj estas denove tabelo, kaj vi volas konservi Maxwell, vi unue indekso kaj do la radiko de nodo, tial paroli, la plejsupra nodo, ĉe situo M, dekstra, do proksimume en la mezo. Kaj tiam el tie, vi sekvu la puntero al infanaj verticoj, por tiel diri. Do, en la familio arbo senso, vi lin sekvas sube. Kaj tio kondukas vin al alia nodo sur la maldekstra, kiu estas nur alia tabelo. Kaj poste se vi volas konservi Maxwell, vi trovos la puntero kiu reprezentas A, kio estas ĉi tie. Tiam vi iros al la sekva nodo. Kaj avizo - tiu ĉi estas kial la bildon de iom trompanta - tiu nodo rigardu super eta. Sed al la rajto de ĉi tiu estas Y kaj Z. Ĝi estas nur la aŭtoro detranĉis la bildo por ke vi efektive vidi tion. Alie ĉi tiu bildo Estus ege larĝa. Do nun vi indekson en situo X, tiam W, tiam E, tiam L, tiam L. Tiam kio estas ĉi vidindaĵo? Nu, se ni uzas ĉi tia nova alpreni kiel memori ĉenon en datumstrukturo, vi ankoraŭ bezonas esence kontroli ekstere en la datumoj strukturo ke vorto finiĝas tie. En aliaj vortoj, ĉiu el tiuj nodoj iel devas memori, ke ni efektive sekvis ĉiuj de ĉi tiuj indikoj kaj estas lasante iom pano panero ĉe la malsupro de ĉi tie strukturo indiki M-Al-X-W-E-L-L estas ĝuste en ĉi tiu datumstrukturo. Do ni povus fari tion jene. Ĉiu el la nodoj en la bildo kiun ni ĵus montaro havas unu, tabelo de amplekso 27. Kaj estas nun 27, ĉar en p metis ses, ni vere donas al vi apostrofo, do ni povas havi nomojn kiel O'Reilly kaj aliaj kun apostrofoj. Sed sama ideo. Ĉiu de ĉi tiuj elementoj en la tabelo notas al struct nodo, tial nur nodo. Do tiu estas tre memorigas de nia ligillisto. Kaj tiam mi havas Bulea, kiun Mi instruos vin voki vorto, kiu estas ĝuste tuj estos vera se vorto finas en tiu nodo en la arbo. Ĝi efektive reprezentas la malgrandan triangulo kiun ni vidis antaŭ momento. Do, se vorto finas en tiu nodo en la arbo, tiu vorto kampo estos vera, kiu koncepte kontrolanta malproksime, aŭ ni desegnante ĉi tiu triangulo, jes estas vorto ĉi tie. Do tiu estas trie. Kaj nun la demando estas, kion estas lia rula tempo? Ĉu granda O de n? Ĉu io alia? Nu, se vi n nomoj en ĉi datumoj strukturo, Maxwell esti nur unu el ili, kio estas la rula tempo de enmeto aŭ trovo Maxwell? Kio estas la rula tempo de enmeto de Maxwell? Se tie estas n aliaj nomoj jam en la tablo? Jes? Lernanto: [inaudibles]. Parolanto 1: Jes, ĝi estas la longo de la nomo, ĉu ne? Do M-a-x-w-e-l-l tiel sentas kiel tiu algoritmo estas granda a de sep. Nun, kompreneble, la nomo estos varii de longitudo. Eble estas mallonga nomo. Eble estas pli longa nomo. Sed kio estas ŝlosilo estas, ke ĝi estas konstanta nombro. Kaj eble ĝi ne estas vere konstanto, sed dio, se realisme, en vortaro, estas probable iu limo pri la nombro de literoj en persono nomon en aparta lando. Kaj tial ni povas supozi ke valoro estas konstanta. Mi ne scias kion ĝi estas. Estas probable pli granda ol ni pensas ĝi estas. Ĉar ĉiam iu angulo kazo kun freneza longa nomo. Do ni nomas ĝin k, sed estas ankoraŭ konstanta supozeble, ĉar ĉiu enoficigi en la mondo, almenaŭ en aparta lando, estas ke longo aŭ mallonga, do ĝi estas konstanto. Sed kiam ni diras ion aĝas Ho de konstanta valoro, kio estas tio vere ekvivalenta al? Tio estas vere la sama afero kiel dirante konstanta tempo. Nun ni estas speco de kaptiloj, ĉu ne? Ni estas speco de utiligante iuj teorio tie por diri, ke bone, komisio de k estas vere nur petita de unu, kaj estas konstanta tempo. Sed vere estas. Ĉar la ŝlosilo komprenon tie estas ke se ni n nomoj jam en ĉi tiu datumstrukturo, kaj ni insert Maxwell, estas la kvanto de tempo nin portas enŝovu Maxwell tute tuŝitaj por kiel multaj aliaj personoj estas en la datumstrukturo? Ne ŝajnas esti. Se mi havus unu miliardo pli elementoj al ĉi tiu trie, kaj poste enigi Maxwell, estas li tute tuŝita? No Kaj tio estas malsimila al ĉiu de la tago datumoj strukturoj kiujn ni vidis ĝis nun, kie la rula tempo de via algoritmo estas tute sendepende de kiom aĵoj estas aŭ ne estas jam en tiu datumstrukturo. Kaj tial kun ĉi havigas al vi nun estas ŝanco por p aro ses, kiuj volas denove impliki apliki vian propran ortografia kontrolilo, legante en 150.000 vortoj, kiel plej bone stoki ke ne estas nepre evidentaj. Kaj kvankam mi aspiris trovi the Holy Grail, mi ne laŭ kiuj trie estas. Fakte, hash tablo povas tre bone pruvi al esti multe pli efika. Sed tiuj estas nur - tio estas nur unu el la decidoj de dezajno vi devos fari. Sed en fermi ni prenu 50 aŭ tiel sekundoj preni peek je kio kuŝas antaŭen proksima semajno kaj preter ni transiro el tiu komandlinio mondo se C programoj al aĵoj retejo starigi kaj lingvoj kiel PHP kaj JavaScript kaj la interreto mem, protokoloj kiel HTTP, kion vi havas memkompreneble, dum jaroj nun, kaj tajpita plej ĉiu tago, eble, aŭ vidis. Kaj ni komencos ŝelo redonas la tavoloj de kio estas la interreto. Kaj kio estas la kodo kiu kuŝas sub la hodiaŭa iloj. Do 50 sekundoj de ĉi teaser tie. Mi donas al vi Soldatoj de la Reto. [VIDEO reprodukto] -Li venis kun mesaĝo. Kun protokolo ĉiuj liaj propraj. Li venis al mondo de kruela cortafuegos, uncaring routers, kaj danĝeroj malproksime pli malbona ol morto. Li estas rapida. Li estas forta. Li estas TCPIP. Kaj li havas vian adreson. Soldatoj de la Reto. [FINO reprodukto de vídeo] Parolanto 1: Tio estas kiel la interreto gxi funkcios ekde proksima semajno.