DAVID Malan: Bone. Bonvenon al CS50. Ĉi tiu estas la komenco de semajno 8. Kaj memoru ke problemo aro 5 finiĝis kun iom da defio. Do supozante ke vi reakiris ĉiujn viajn instruado Membroj kaj CA La fotojn en la card.raw dosiero, vi rajtas nun trovos ĉiujn el tiuj homoj, kaj unu bonŝanca venkinto irados domo kun unu pri tiuj aferoj, la salton movado aparato kiu vi povas uzi por fina projektoj, ekzemple. Ĉi tio, ĉiu jaro, kondukas al iom de creepiness. Kaj do kion mi pensis mi ŝatus fari estas kotizo kun vi iujn el la notoj, kiuj havas iris tien kaj reen super la bastonon listo de malfrue. Ekzemple, nur hieraŭ nokte, citaĵo unquote, de unu el la dungitaro membroj, "mi ĵus havis studento frapo sur mia pordo preni foton kun mi. Stalkers, mi diros al vi. "Partio sufiĉe priskriba kaj poste ni translokiĝis al, eble horo poste, "mi havis studento atendis min post sekcio kaj li havis ĉiujn niajn nomojn kaj fotoj sur iu paperfoliojn. "Bone. Do organizitaj, sed ne cxio, kion anime ankoraŭ. Do, "Mi estis for de la urbo ĉi tiun semajnfinon, kaj kiam mi reiris, estis unu en mia dormoĉambro. "[ridado] DAVID Malan: Venonta citaĵo de dungitaro membro, "studento venis al mia domo Somerville, je 4 GMT ĉi matene. "Sekva bastono, "mi alvenis al mia hotelo en Sankta Francisko kaj studento atendis min ĉe la premgrupo kun tri DSLRs. " Tipo de ĉambro. "Mi ne estas eĉ sur bastono tiu semestro, sed studento penetris en mian domon Matene kaj gravurita la tuta afero kun Google Pokalo. "Kaj poste laste, "Almenaŭ 12 homoj estis avide atendante por mi kiam mi eliris el mia Ŝlimo, kaj tiam mi vekis. "Bone. Do inter la fotoj, kiel vi povas memoras, estas tiu ulo ĉi tie, kiuj vin sciu, kiel Milo Banano, kiu vivas kun Lauren Carvalho, nia kapo instruante Fellow. Milo, Milo, venu tien knabo. Milo. Milo. Mind vi, li estas vestita Google Pokalo, tiel ni montros al vi cxion cxi tion poste. Do tiu estas Milo se vi ŝatus preni foton kun li poste. Se vi ŝatus elsercxu en la aŭdantaro. Akcepti. Tio estas bona materialo. Nu, Milo Banano. Ho, ne faru tion. [Ridado] Akcepti. Do vorto tiam kio kuŝas antaŭen, ĉar kiel ni komencas transiro, tiu semajno specife, de C en komandlinio medio por PHP kaj Javascript kaj SQL kaj HTML kaj CSS en retejo bazita medio, ni estos ekipi vin per cxiuj pli kono por potenciala fino projektoj. Tiucele, la kurso havas tradicio de tenante seminarioj kiuj estas sur _tangential_ temoj al la kurso. Tre rilataj al programado kaj al app disvolviĝo kaj tiel plu, sed ne nepre esploris per la kurso mem Syllabus. Do, se vi povus interesi en unu aŭ pli de la ĉijara seminarioj, enregistri cs50.net/seminar. Estas pli malnovaj seminarioj ĉe cs50.net/seminars. Kaj sur la roster tiel multe por ĉi tiu jaro estas Amazing Retejo Apps kun Ruby on Rails, kiu estas alternativa lingvo PHP. Komputa Lingvistiko. Enkonduko al IOS, kiu estas la platformo kiu estas uzata por iPhone kaj iPad disvolviĝo. Javascript por Retejo aplikaĵoj, ni kovras tio, sed en tiu seminario, vi iros pli detale. Salti Motion, do ni efektive havas iujn el niaj amikoj el Leap Motion, la propra kompanio, aliĝi. Morgaŭ, fakte, havigi oni batalas en seminarion, se interesajn por vi. Meteor.js, alternativa tekniko por uzante JavaScript ne en foliumilo, sed sur la servilo. Node.js, kio estas tre multe en tiu vejno tiel. Glata Android Dezajno. Android esti tre populara alternativo al IOS kaj Windows Phone kaj aliaj telefonoj platformoj. Kaj Retejo Sekureco Aktiva defendo. Do fakte, se vi ŝatus engaĝiĝi pri tio, lasu min fari noton pri tio. Ni estas tre feliĉa por diri ke niaj amikoj Leap Moviĝo, kiu estas startup - tiu aparato vere nur venis el kelkaj monatoj - favore donacis 30 tiaj aparatoj al la klaso por tiom da studentoj, se Vi ŝatus pruntepreni la aparataro al semestro fino kaj uzi ĝin por reala fina projekto. Ili apogas plurajn lingvojn. Neniu el ili C, neniu el ili PHP, do realigi unu aŭ pli el tiuj seminarioj por elprovi de intereso. Kaj ĉiuj ili estos filmado en la okazaĵo ke vi ne povas ĉeesti persone. La horaro estos anoncita per retposxtu kiel ni solidiĝas ĉambroj. Kaj laste, se vi iros al projects.cs.50.net, ĉi tiu estas afiŝinto ni subtenas ĉiun jaron ke ni inviti uloj de la komunumo, fakultato, fakoj, bastono, ambaŭ en ekster CS50 al proponi projekton ideoj. Aĵoj de intereso por studento grupoj. Aĵoj de intereso al fakoj. Do turnu tie se vi luktas kun necerteco, kia vi mem ŝatus pritrakti. Do lastan fojon ni prezentis nediskuteble pli kompleksa datumstrukturo ol ni volonte vidita en semajnoj pasinteco. Ni volonte estis uzante arrays bela feliĉe kiel utila se simplista datumstrukturo. Tiam ni enkondukis tiujn, kiuj kompreneble estas ligitaj listoj. Kaj kio estis unu el la motivoj por enkonduki tiun datumstrukturo? Jes? Kio estas tio? Spektantaro: Dinamikaj grandeco. DAVID Malan: Dinamikaj grandeco. Tiel dum en tabelo, vi devas koni lian grandecon anticipe kiam vi destini ĝin. En ligitaj listo, vi ne devas scii tion. Vi povas simple malloc, aŭ pli ĝenerale, destini plia nodo, por tiel diri, iam vi volas enmeti pli da datumoj. Kaj nodo havas ne antaŭdeterminita signifon. Estas nur ĝenerala termino priskribanta ia ujo kiu ni estas uzante en nia datumstrukturo stoki iu elemento de intereso, kiu en ĉi tiu kazo hazarde estas entjeroj. Sed ĉiam oni tradeoff. Do ni ricevas dinamika grandecoj de la datumoj strukturo, sed kion prezo ni pagas? Kio estas la malfacilaĵo de lertaj kunligitaj? Jes? Spektantaro: postulas pli da memoro. DAVID Malan: ĝi postulas pli memoro, kiel ĝuste? Spektantaro: [inaudibles]. DAVID Malan: Ĝuste. Do nun ni montriloj tenante plia memoro kiujn ni antaŭe ne bezonas, ĉar la avantaĝo de tabelo, kompreneble, estas tio ĉio estas apudaj, dorso apogi al malantaŭo, kiun donas hazardan aliron. Ĉar nur per rektaj krampo skribmaniero, aŭ pli teknike puntero aritmetiko, tre simpla Krome, vi povas aliri al iu elementoj en konstanta tempo. Kaj fakte, tio estas speco de aludas alia prezo kiun ni pagas per ligitaj listo. Kio okazas al la rula tempo de iu kiel Search, se mi volas trovi iun valoron kaj ene de kunligita listo? Kion mia rula tempo fariĝos? Granda a de n. Se ĝi estas ordo de? Kio se la datumstrukturo estas ordo? Ĉu mi povas fari pli bone ol granda Aŭ de n por serĉado? Ne, ĉar en la plej malbona kazo povus tre bone esti ordo, sed la numero vi serĉas povus esti granda. Ĝi povus esti la numeron 100, kiu povus okazi ke ĉiu la vojo al la fino. Kaj ĉar vi nur povas konsenti kunligita lerta en tiu efektivigo de maniero de lia unua nodo, vi estas ankoraŭ ia el sorton. Vi devas trairi la tutan aferon de komenco ĝis fino, por trovi ke granda valoro kiel 100. Aŭ por determini se estas eĉ ne ekzistas. Do ni ne povas fari kion algoritmo en datumoj strukturo kiu aspektas tiel? Ni ne povas fari duuma serĉo, ĉar duuma serĉo postulis ke ni havis hazarda aliron. Ni povus simple salti el situon situo sen devi sekvi tiuj pano panerojn en la formo de ĉiuj ĉi tiuj indikoj. Nun, kiamaniere ni apliki tio? Nu, se ni iros al la ekrano tie, se ni povas rapide reimplement ĉi datumoj strukturo - mia skribo ne estas ĉiu, kiu grandan tie, sed ni provos. Do typedef struct, kaj kion faris mi volas nomi tion ĉi tien? Nodo. Do mi devos akiri ni komencis. Kaj nun, kio devas esti ene de la datumstrukturo por unuope ligitaj listo? Kiom da kampoj? Do du. Unu estas sufiĉe facila. Do int n. Kaj ni povus nomi n ion ni volas, sed devus esti int se ni estas apliki kunligita listo por ints. Kaj nun kio faras la dua kampo devas esti? Struct nodo *. Do, se mi faras struct nodo *, kaj tiam mi povas nomi ankaux cxi tio, kion ajn mi volas, sed nur por esti klara Mi vokos ĝi venas, kiel ni estis farante. Kaj poste mi fermas mian krispa krampoj. Kaj nun, kiel lasta fojo, Mi metis nodo cxi tie. Sed se mi deklari cxi tiu estas kiel nodo, kial mi tedas esti tiel verbose tie en deklari struct nodo * proksima, kontraste al nur nodo * poste? Jes? Spektantaro: [inaudibles]. DAVID Malan: Ĝuste. Ekzakte. Ĉar C vere prenas vin laŭvorte kaj nur vidas la difino de vertico vojo cxi tie, vi ne povas referi al ĝi ĉi tie. Do ni havas ĉi tiun specon de antaŭataka deklaro tie, kiu estas Certe pli abundajn. Struct nodo, tio signifas ni povas aliri ĝin ene de la datumstrukturo. Kaj kiel flanken, ĉar ĉi tiu estas igante iom pli subjektivan nun, la stelo povas teknike iri tien, ĝi povas iri ĉi tie, ĝi povas eĉ iri en la mezo. Ni adoptis, en la stilo gvidas por la kurso, la konvencio de metante la stelo tuj apud la datumoj tipo, kiu en ĉi tiu kazo, Estus struct nodo. Sed rimarki en multaj lernolibroj kaj linio referencoj, vi povus ja vidi ĝin sur la alia flanko. Sed ĝuste rimarkas ke ambaŭ faros reale labori kaj vi devas simple esti konsekvenca. Ĉio bone. Por ke estis nia deklaro de struct nodo. Sed tiam ni komencis fari pli kompleksaj aĵoj. Ekzemple, ni decidis enkonduki iu kiel hash tablo. Do jen estas hash tablo de amplekso n, indeksitaj de 0 sur supro lasis al n minus 1 sur la fundo restis. Tio povus esti hash tablo por nenio. Sed kiajn aferojn ni parolas pri uzanta hash tablo por? Stoki kio? Nomoj. Ni povus fari nomojn kiel ni faris lastan fojon. Kaj vere, vi povas stoki nenion. Kaj ni vidos ĉi denove en PHP kaj en JavaScript. Al hash tablo estas bela speco de svisa Poŝtranĉilo kiu permesas stoki preskaux kion vi volas ene de ĝin asocii klavojn per valoroj. Klavoj kun valoroj. Nun en tiu simpla kazo, nia klavoj estas nur numerojn. Ni aplikas kradon tablo kiel tabelo. Kaj tial la klavoj estas 0, 1, 2, kaj tiel plu. Kaj tial ni, kiel homoj, ili decidis lastan semajno ke vi scias kio, se ni estas tuj vendejo nomoj, ni nur arbitre, sed sufiĉe prudente, supozi ke Alico, an A nomo, estos nur esti indeksita en 0. Kaj Bob, B nomo, estos indeksita en 1, kaj tiel plu. Do ni devis surĵeto inter enigoj, kiuj estas sanaj, kaj la hash lokoj, kiuj estas nombroj. Do tiu procezo estas ĝenerale konata kiel kradon funkcio, kaj vi povas vere apliki ĝin en kodo. Se mi volis apliki hash funkcio kiu faras ĝuste kion ni jxus priskribita de lasta fojo, mi povus deklari funkcio kiu prenas, kiel enigo ekzemple - kaj ni faru tion en tiu ekrano super tie. Se mi volis apliki hash funkcio, mi povus diri iu kiel ĉi tio. Ĝi tuj revenos al int. Ĝi tuj nomos hash, kaj estas tuj akceptus kiel argumento al ĉeno, aŭ ni povas esti pli taŭga nun, kaj diru char *, ni nomas ĝin s. Kaj tiam ĉiuj ĉi funkcio devas fari, fine, ĝi revenas al int. Nun, kiel faras tion povus ne estus tiel klara. Mi tuj apliki tion sen ajna formi de eraro kontrolanta nun. Mi simple tuj blinde diri, revenu kio ajn estas je s krampo 0, minus, diru, ĉefurbo A punktokomo. Plene rompita. Ĝi ne estas perfekta ĉar unu, kio se s estas nula? Malbonaj aferoj okazos. Du, kio okazos se la unua letero en tiu nomo ne estas majusklo? Tio ne tuj turni el bone ankaŭ ne. Ĝi povus esti minuskla litero aŭ ne leteron al ĉiuj. Do tute spaco por plibonigo tie, sed ĉi tiu estas la baza ideo. Kion ni priskribis pasintsemajne parole kiel nur proceso de mapado de Alico al 0 kaj Bob al 1 povas esti esprimita certe pli formulaically kiel C funkcii tie. Vokis denove hash, prenas ĉeno kiel eniro, kaj poste iel faras ion kun tiu enigo por produkti eligo. Ne malkiel nia nigra skatolo priskribo ke ni longe faris. Mi ne scias kiel tio povus esti laborante sub la kapuĉo. Por problemo aro 6, unu el la defioj estas por vi decidi kion via krada funkcio estas? Kio okazas al esti ene de tiu nigra skatolo, kaj supozeble, ĝi devos esti iom pli interesa ol tio, kaj definitive pli inklina al eraro kontrolanta ol tiu aparta efektivigo. Sed problemoj povas ekesti, ĉu ne? Se ni havas datumstrukturo kiel ĉi unu, kio estas unu el la problemoj vi povas kolizii kun la tempo kiel vi enŝovu pli kaj pli nomoj en la hash tablo? Vi ricevas kolizioj, ĉu ne? Kio se vi havas Alico kaj Aaron, du personoj kies nomoj okazis komenci kun A? Tio petegas la demando, kie vi meti la dua tia A nomo? Nu, eble vi naive simple metu ĝin kie Bob apartenas, sed tiam Bob estas speco de ŝraŭbita se vi provas enŝovu sian nomon sekva kaj ne estas loko por li. Tiel vi povus meti Bob kie Charlie, kaj vi povas imagi tiun tre rapide devolving en iom de malordo. Io lineara en la fino, kie vi Nur oni devas serĉi en la tuta afero serĉas Alico aŭ Bob aŭ Aaron aŭ Charlie. Do anstataŭ ni proponis, anstataŭ nur lineare tuŝoprobado por malferma spacoj kaj investi la nomoj tie, ni proponis amatoro alproksimiĝo. Al hash tablo implementado ankoraŭ kun tabelo de indeksoj, sed la datumtipon de tiuj indeksoj nun estis montriloj. Pointers por kio? Pointers al lertaj kunligitaj. Pro memoro ke ligitaj listo estas vere nur puntero al nodo, kaj la nodo havas sekva kampo, kaj tiu nodo havas sekva kampo, kaj tiel plu. Do vi nun povas pensi pri tiu tabelo en la maldekstra flanko de hash tablo kiel kondukante al kunligitaj listo. La avantaĝo de tio estas, se vi ricevas kolizio inter Alica kaj Aaron, kion vi faras kun la dua tia persono? Vi nur alfiksi lin aŭ ŝin al la fino, aŭ eĉ la komenco de tiu ligitaj listo. Kaj efektive, ni nur vermiĉeloj tra ke por ĝuste dua. Kie farus la plej senso? Se mi enŝovu Alice kaj ŝi finiĝos ĉe la unua loko, tiam mi provos enigi la nomon de Aaron, kaj tie estas evidente kolizio, mi devus meti li komence de la ligitaj listo? Tio estas en tiu unua loko, aŭ ĉe la fino? Spektantaro: [inaudibles]. DAVID Malan: okej. Mi aŭdis komenciĝis. Kial ĉe la komenco? Spektantaro: [inaudibles]. DAVID Malan: okej. Ĝi estas alfabeta, do tio estas agrabla. Tio estas bona posedaĵo. Ĝi helpos al mi iom tempon potenciale. Ne lasu min fari duuma serĉo, sed mi povus almenaŭ povos rompi de ciklo se mi rimarkas, bone, mi estas maniero estinteco estis Aaronon estus en ĉi tiu ordo ligillisto. Mi ne devas malŝpari mian tempon rigardante tuta vojo al la fino. Do jen racia. Kial alia eble vi volas enmeti la karamboli nomon ĉe la komencante de la listo? Kio estas tio? Spektantaro: [inaudibles]. DAVID Malan: Ĝi povus fari longan tempon alveni ĝis la fino de la listo. Kaj fakte, pli longa kaj pli longa. La pli nomoj vi enŝovu ke komencu per A, la longaj, ke ĉeno tuj akiras. Ju pli longe ke ligitaj listo estas tuj alvenos. Do vi estas vere ĝuste malŝparas vian tempon. Eble vi pli bone subteni konstanta inserción tempo, granda O de 1, por ĉiam meti la karamboli nomo ĉe Komence de la ligitaj listo, kaj ne zorgi tiel pri ordigado. Kio estas la plej bona respondo? Ĝi estas klara. Ĉio dependas de kion la dissendo estas, kion la ŝablono estas de la nomoj vi enmeto. Ĝi ne estas bezone evidenta respondo. Sed ĉi tie, denove, estas dezajnon ŝancon. Do ni tiam rigardis tion, kio estas vere la aliaj grandaj ŝancon por p-aro 6. Kaj realigi, se vi ne jam, Zamyla mergas en ambaŭ de ĉi tiuj, hash tabloj kaj klopodoj, en pli detalo. Kaj la video walkthrough estas enigita en p-aro spec. Tio estis trie - T-R-I-E. Kaj kio estis interesa tio estis, ke la rula tempo de serĉado Mia nomo, same kiel Maxwell lastan fojon, estis granda O de kio? Kio estas tio? Aŭdienco: La nombro de literoj. DAVID Malan: Nombro da literoj. Mi aŭdis du aĵojn. Nombro da leteroj kaj konstanta tempo. Do ni iru kun tio unue. La nombro de literoj. Nu, tiu datumstrukturo, revokon, estas kiel arbo, familio arbo, ĉiu el kies verticoj estas formitaj de arrays. Kaj tiuj matricoj estas indikoj al aliaj tiaj nodoj, aŭ aliaj tiaj arrays en la arbo. Do, se ni volis tiam determini ĉu Maxwell estas en tie, mi povus iri al la unua tabelo, ĉe la plejsupro de la arbo, la tn radiko, supro de la trie, kaj poste sekvi la m pointer, tiam la puntero, tiam x, w, e, l, l. Kaj poste, kiam mi vidas iun specialan simbolon, signifita tie kiel triangulo. En kodo vi vidos ni proponas ke vi implementado kiel bool, nur diras jes aŭ nenio, vorto haltas tie. Nu, iam ni foriris al M-Al-X-W-E-L-L, sentas sep, eble ok se ni iros unu estinteco, ok paŝojn por trovi Maxwell. Aŭ ni nomas ĝin K. Sed memoru lasta tempo, mi argumentis, ke se ekzistas realisme maksimumo longeco sur vorto, kiel 40-iuj-nepara gravuloj, maksimuma longo implicas konstanta valoro. Do vere, jes, estas teknike granda O de 8 aŭ 7, aŭ vere granda O de K. Sed se estas finia ĉapo sur kio K povus esti, ĝi estas konstanto. Kaj tial estas granda O de 1, je la fino de la tago. Ne en la reala mondo. Ne kiam vi vere komencos rigardi vian horloĝon kiel via programo kurado. Ĝi estas absolute tuj estos iom malrapida ol vere konstanto tempo kun unu paŝo. Ĝi tuj estos sep aŭ ok ŝtupoj, sed ankoraŭ tio estas multe, multe pli bone ol algoritmon kiel granda O de n kiuj dependas de la grandeco de kio estas en la datumstrukturo. Rimarku la inversita jen ni povas enigi miliono pli nomoj en tiun datumstrukturo, sed kiom da paŝoj Estas ĝi tuj portos nin trovi Maxwell en tiu kazo? Neniu. Li estas tuŝita. Kaj ĝis nun, mi ne kredas ke ni vidis ekzemplo de datumstrukturo aŭ algoritmo kiu estis tute tuŝita de eksteraj kondutojn tiel. Sed ĉi tiu ne povas esti mirinda. Ĉi tio ne povas esti la sola solvo por la p-aro Kaj ĝi ne estas. Tiu ne estas nepre la datumoj strukturo vi devus gravitas al, ĉar kiel hash tabloj, tradeoff. Kio estas la prezo vi pagas tie? Memoro. Mi volas diri, ĉi tio estas abomena kvanto da memoro. Kaj vi ne povas sufiĉe vidu ĝin ĉi tie ĉar la aŭtoro de ĉi tiu pentraĵo evidente senpintigita ĉiuj sensilo, kaj ni ne vidante multajn A kaj B kaj C-aj kaj Q kaj Y estas kaj Z estas en tiuj matricoj. Sed ili estas tie. Ĉiu de ĉi tiuj nodoj estas tuta tabelo de iuj 26 aŭ pli da bitokoj, ĉiu el kiu reprezentas leteron. 27 en nia kazo, tiel ke ni povas apogi apostrofoj en la problemo aro. Do tiu datumstrukturo estas vere, vere densa kaj larĝa. Kaj tio nur povus fini malrapidiĝanta aĵoj malsupren, aŭ almenaŭ kostas vin multe pli da spaco. Sed denove, ni povas desegni komparoj tie. Memori tempo reen, ni atingis multan pli ekscita rula tempo en ordiga kiam ni uzas merge varon, sed la prezo Ni pagis por atingi n log n por merge speco postulis ke ni elspezos pli kia rimedo? Pli spaco. Ni bezonas malĉefan tabelo por kopii popolon en, samkiel ni faris ĉi tie sur la scenejo. Do denove, ne klara gajnantoj, sed ĝuste subjektiva dezajno decidojn fari. Ĉio bone. Do kiel pri tio? Ĉiu rekonas ke D-Hall? Akcepti. Do tri el ni faras. Mather Domo. Do tio estas por Mather la manĝejo. Mi vetas ĉiuj manĝoĉambroj havas stakoj de pletoj ŝatas tion. Kaj jen estas vere reprezentanto de io ni evidente vidis jam. Ni nomis ĝin laŭvorte pilo. Kaj la pilo, en terminoj de via komputilo memoro, estas kie datumoj iras dum funkcioj estas nomata. Ekzemple, kiajn aferojn iri sur la stako kun respekto al la memoro aranĝo ni diskutis en semajnoj estinteco? Kio estas tio? Spektantaro: Alvokoj al funkcioj. DAVID Malan: mi bedaŭras. Spektantaro: Alvokoj al funkcioj. DAVID Malan: Alvokoj al funkcioj, sed specife, kio estas ene de ĉiu el tiuj kadroj? Kiajn aferojn? Jes. Do lokaj variabloj. Anytime ni bezonis iu loka stokado, kiel argumenton, aŭ int mi, aŭ int temp, aŭ kion ajn la loka variablo, ni vizitis metante ke sur la stako. Kaj ni nomas ĝin pilo ĉar de tiu layering ideo. Nur speco de alumetoj kun realo, la koncepto de gxi. Sed ĝi rezultas ke pilo povas ankaŭ vidiĝi kiel datumstrukturo, an alternativo al tabelo, alternativa al lerta kunligita. Io koncepte pli interesa kiu povas ankoraŭ esti implementado uzante ĉu de tiuj aĵoj, sed estas malsama tipo de datumstrukturo apogante, vere, nur du operacioj. Sed vi povas aldoni sur amatoro trajtojn ol tiuj. Sed jen estas la fundamentojn - puŝi kaj pop. Kaj la ideo kun pilo estas ke se mi jen, kun aŭ sen Annenberg sciante, pleto de la proksima pordo kun la numero 9 en ĝi. Do nur int. Kaj mi volas puŝi tiun sur la datumoj strukturon, kiu nuntempe estas malplena. Konsideru ĉi tiun la fundo de la pilo. Mi devus peli ĉi numero 9 sur la pilo, kaj nun ĝi estas prava. Sed la interesa afero pri pilo estas ke se mi nun volas puŝi iu alia valoro, kiel 17, kaj mi puŝi ĉi sur la pilo, mi faros la sola intuicia afero, mi nur irante meti ĝin ĝuste kie ni homoj estus inklina por meti ĝin sur pinton. Sed kio estas interesa nun estas, kiel mi alveni al la 9? Vi scias, mi faras ne sen iuj penado. Do kio estas interesa pilo estas ke per dezajno, ĝi estas LIFO datumstrukturo. Stulta maniero priskribi lasta en, unua el. Do la lasta cifero en en ĉi tiu epoko estis 17. Do se mi volas pop io ekstere de la pilo, ĝi povas esti nur 17. Do tie estas deviga ordono de operacioj tie, kie la lasta elemento en ĝi devas esti la unua el. Sekve la akronimo, LIFO. Do kial cxu tio estos utila? Estas iliaj kuntekstoj en kiuj vi volas deziras datumstrukturo tiel? Nu, ĝi estas certe estis utilaj ene de komputilo. Do mastrumaj sistemoj klare uzi ĉi speco de datumstrukturo por piloj. Ni vidas ankaŭ la sama ideo kiam temas retpaĝoj. Do tiu semajno kaj proksima semajno kaj preter, kaj kiel vi komencas apliki retejo paĝoj en lingvo nomata HTML, vi povas efektive uzi datumstrukturo kiel ĉi por determini se la paĝon Estas ĝuste formatita. Ĉar ni vidos ĉiuj retpaĝoj sekvi speco de hierarkio, la deŝovon kiu, fine de la tago, esti arbo strukturo sub la kapuĉo. Do pli sur tiu en nur iom. Sed nuntempe, ni proponas por momento, kiel ni povus iri reprezenti kion pilo estas? Permesu al mi proponi ke ni implemento pilo kun kodo ŝatas tion. Do pilo tuj havi ene de ĝi du aferoj, tabelo, nomita pletoj, nur por esti konsekvenca kun la demo. Kaj ĉiu el la artikoloj en tiu tabelo tuj estos tipo int. Kaj kapablo estas supozeble kio? Ĉar mi ne skribis la plena difino tie. Ĝi estas verŝajne la maksimuma grandeco de la tabelo. Kaj ĝi estas probable deklarita kiel akra difini ĉe la supro de la dosiero, iuj speco de konstanta kiel implicita de la nura majuskloj. Do ie kapablo estas difinita kiel la maksimuma ebla grandeco. Dume, ene de la datumstrukturo konata kiel stako tie volo esti entjero nur scias simple kiel grandeco. Do se mi estus por reprezenti tiun nun pictóricamente, ni supozu, ke tiu tuta nigra skatolo reprezentas mian pilo. Ene de ĝi estas du variabloj. Do mi tuj tiri la unue oni kiel grandeco. Kaj la dua mi iros desegni tiel tablo. Sed ĝuste por subteni tion orde, kutime mi eltirus tabelo kiel ĉi tio, sed estas speco de bela se ni kongruas realaĵo, aŭ parigi la mensa modelo. Do mi anstataŭ desegni la tabelo vertikale, kio estas justa, denove, artisto transdonado. Ne vere gravas kion estas sub la kapuĉo. Kaj ni diras, ke, implicite, kapablo tuj estos tri. Do tiu estos situo 0, ĉi tio Estos situo 1, ĉi Estos situo 2. Se mi subaĉeti kun streso pilko, ĉu iu ŝatus veni tien kaj ruli la enŝipigi tie dum nur momenta? Bone, mi vidis vian manon unue. Venu supren. Ĉio bone. Do mi opinias ke ĝi estas Steven. Venu supren. Ĉio bone. Sed supozas nun ni malantaŭenigi la komenca stato de la mondo kie mi ĵus deklaris en pilo, kaj estas tuj estos de kapablo tri. Sed grandeco ankoraŭ ne estis decidita. Pletoj ankoraŭ ne estis decidita. Do kelkaj demandoj unua. Kaj mi donos al vi mic tiel vi povas partopreni pli aktive en ĉi tio. Do kio estas ene de amplekso en ĉi tiu momento en la tempo kvazaŭ ĉiuj mi faris estas deklarita de pilo kun unu linio de kodo? Steven: Ne tre. DAVID Malan: OK, ne multe. Ĉu ni scias kio estas ene de grandeco, ni scias kio estas ene de tiu tabelo tie? Steven: Just hazarda kodo, ĉu ne? Ĝuste - DAVID Malan: Jes, mi tuj nomas ĝin kodon, sed hazarda - Steven: Aĵoj. DAVID Malan: Aĵoj kiel hazarda Steven: Bitoj. DAVID Malan: Bitoj, ĉu ne? Do rubo valoroj, ĉu ne? Do permutoj de 0-aj kaj 1-oj. Restoj de antaŭa uzoj de tiu memoro. Kaj ni ne vere scias kion la valoroj estas, do ni tipe desegni ilin kiel demandosignojn. Do la unua horo ni supozeble tuj volas fari ĉi tie - kaj mi donos al ĉi tiu kampo ene de tie oni nomo - pletoj. Kion ni supozeble pravalorizi grandeco se ni volas ekuzi ĉi pilo? Steven: Pleto estas sub 3. DAVID Malan: Do, OK. Por esti klaraj, kapablo estas deklarita aliloke kiel tri. Kaj tio estas kion mi uzis destini la tabelo. Grandeco tuj raporti al kiom pletoj estas nuntempe en la pilo. Steven: Nulo. DAVID Malan: Do ĝi devas esti nulo. Do iru antaŭen kaj kun iu ajn fingro desegni nulo en grandeco. Ĉio bone. Do nun, kio estas ene de ĉi tie, ni ne scias. Tio estas vere nur rubo valoroj. Do ni povus desegni demandosignojn, sed ni observos la estraro pura cxar nun ĉar ne gravas kio estas tie. Ni ne bezonas pravalorizi la tabelo al nenio, ĉar se ni scias, ke la grandeco de la pilo estas nulo, nu, ni oni ne rigardante ion en tiun tabelo ĉiuokaze ĉe ĉi tiu punkto en tempo. Do nun supozas, ke mi pelas la numero 9 sur la stako. Kiel do ni ĝisdatigi la datumstrukturo ene de tiu nigra skatolo? Kio valoroj bezonas ŝanĝi? Steven: Ene - la grandeco? DAVID Malan: okej. Grandeco unuiĝu kio? Steven: Grandeco estus unu. DAVID Malan: okej. Do grandeco unuiĝu tiu. Do vi povas fari tion en paro manieroj. Lasu min donu al vi, nun via fingro estas eraser. Ĉio bone. Tiam nun via fingro estas peniko. Ĉio bone. Kaj nun kio alia devas ŝanĝi, evidente, en la datumstrukturo? Steven: Ni iras el malsupro ĝis 9. DAVID Malan: 9. OK, Bona. Do ankoraŭ ne gravas kio estas ĉe situo unu aŭ du ĉar ili estas rubo valoroj, sed ni ne devas ĝeni serĉas tie ĉar grandeco estas diras al ni ke nur la unua ero estas vere legitima. Do nun mi puŝi 17 sur la listo. Kio okazas al ĉi tiu bildo? Steven: Do grandeco tuj iros al du. DAVID Malan: okej. Vi estas eraser - oops. Vi estas eraser. Steven: Eraser. DAVID Malan: Vi estas peniko. Steven: Brush. DAVID Malan: okej. Kaj kion alian? Steven: Kaj tiam ni - DAVID Malan: Ni puŝis 17. Steven: Ni bati 17 sur supro, do - DAVID Malan: Bone, bone. Steven: - faligis ĝin malsupren. DAVID Malan: Bone. Fariĝas facila. Mi ne helpos al vi tiun tempon. Push 22. Steven: Farita. Igante eraser. Mi ĉiufoje peniko. Kaj poste mi metante 22. DAVID Malan: 22. Bonega. Do unu pli longa tempo. Mi nun iras puŝi sur la stako 26. Steven: Ooh. Ho gosh. Vi vere kaptis min gvardio. DAVID Malan: Vi ne vidu ĉi alveno? Steven: Mi ne vidis ĉi venas. Ĉu ni re-komenca kapablo? DAVID Malan: Tio estas bona demando. Do ni ia pentris mem en angulo tie. Tie vere estas nenio bona eliris por Steven ĉar ni destinis tiun tabelo statike, por tiel diri, interne de la datumstrukturo. Kaj ni esence hard coded ĝin esti de amplekso tri. Do ni ne povas vere reallocate ĝin. Ni povus, se ni reiris en, ni redifinis pletoj esti puntero ke ni do uzu malloc al mano memoro. Ĉar se ni akiris la memoro de la amaso tra malloc, ni povus tiam liberigi ĝin. Sed antaŭ ol liberigi ĝin, ni povis reallocate pli grandan eron de memoro, ĝisdatigi la puntero, kaj tiel plu. Sed nuntempe, ĉi tio estas vere la bona ni povas fari. Push kaj pop estas supozeble tuj havi por marki iun eraron. Do ekzemple, niaj efektivigo de puŝo povis reveni al bool kiu antaŭe revenis vera, vera, vera. Sed la kvara fojo, ĝi tuj devos redoni malvera, ekzemple. Ĉio bone. Tre bone farita. Gratulojn. Vi gajnis via streso pilko hodiaŭ. [Aplaŭdo] Steven: Dankon. DAVID Malan: Dankon. Bone, do tio ŝajnas esti ne multe de paŝo antaŭen, ĉu ne? Ni priskribis ĉi datumstrukturo. Jam pasis konvinka, ĉu ne? Mastrumaj sistemoj ŝatas ĝin. Ŝajne la retejo povas uzi tion, kaj aliaj aplikoj ankoraŭ. Sed kia stulta limigo kiu ni estas apogi al speco de semajno du limoj kie ni fiksita grandeco arrays. Do estas ja kelkaj manieroj ni povus solvi ĉi. Ni povus dinamike atribui la tabelo, ne per malmola kodigo kiel mi havas faris ĉi tie, sed anstataŭ re-deklarante tiu, nur por esti klara, kiel iu kiel ĉi tio. Int * pletoj, ne decidi sur kapablo ankoraŭ. Sed kiam mi deklaras la pilo aliloke en mia kodo, mi povus tiam nomita malloc, atingi la adreson de eron de memoro, kaj mi povis atribui ke adreso por pletoj. Kaj poste, ĉar ĝi estas nur eron de memoro, mi povis sekvi uzi kvadratan krampo notacio en la kutima maniero. Ĉar denove, estas speco de tiu funkcia ekvivalento de arrays kaj pecoj de memoro kiu venis revenis de malloc. Ni povas trakti unu kiel la alia uzante puntero aritmetiko aŭ kvadrata krampo skribmaniero. Do jen unu alproksimiĝo. Sed kiel alie povus ni apliki tiun sama datumstrukturo, potenciale? Ĝuste? Mi sentas kiel ni ĵus solvis ĉi problemo kiel antaŭ unu semajno. Kio estis la solvo al tiu problemo ke Steven kuris en? Do ligitaj lertaj, dekstre. Se la problemo estas ke ni pentri nin en angulon de atribuo anticipe tro malmultan memoron, ke ni tiam devas iel pritrakti, bone, kial ne simple eviti tiun elsendi aro? Kial ne simple deklaras pletoj esti puntero al nodo, ergo lerta kunligita, kaj tiam simple malŝparas novaj nodoj ĉiufoje Steven bezonas ĝustigi nombro en la datumstrukturo. Do la bildo devus ŝanĝi. Oni ne tuj estos tiel pura kaj kiel simpla kiel nur tabelo de tri ints. Nun ĝi estas tuj estos referenco al struct, kaj ke struct tuj havi _int_ kaj proksima puntero. Ĝi tuj konduki tra tiu puntero al alia tia struct al alia tia struct. Do la bildo estus efektive akiri iom Messier. Kaj ni volas esti sagoj ligi ĉion kune. Sed tio estas bone, dekstra, ĉar ni vidis kiel fari tion. Kaj iam vi akiras komfortan efektivigi iun kiel kunligita listo, kiun vi devos fari se vi elekti apliki kradon tablo kun apartan ĉeni por p-aro 6, vi povas uzi ĝin kiel konstruaĵo bloko, aŭ ingredienco, aŭ en Scratch paroli, oni proceduro, iu kiu vin meti, vi kreis vian propran puzlo peco ke vi povas tiam reuzi. Do tradeoffs, sed eblaj solvoj ke ni reale vidis antaŭe. Do tre ofte, vi vidas cxi tiun ĉiu jaro aŭ du, kiam Apple ĵetoj iu nova, kaj ĉiuj frenezaj laŭliniigi eksteren de la Apple stoki aĉeti ilian marĝenan ĝisdatigi la aparataron. Mi diras tion, estas bone, ĉar Mi estas unu el tiuj personoj. Do kia datumstrukturo povus reprezenti ĉi realaĵo? Nu, ni nomas ĝin vosto, linio. Do britoj nomas ĝin tipe vosto ĉiuokaze, do ĝi estas bela nomo. Kaj la du operacioj kiuj vosto oni apogas ni nomas enqueue operacion kaj dequeue operacio, kiuj estas similaj en spirito puŝi kaj pop. Estas nur speco de malsama en konvencio, kion ni nomas tiujn. Sed por enqueue ion signifas aldoni aŭ enmeti ĝin al la datumstrukturo. Por dequeue signifas forigi ĝin. Sed dum pilo estis LIFO datumoj strukturo, vosto estas unua en, unua el datumstrukturo. Se vi estas la unua persono en linio, Vi estos la unua persono akiri el linio kaj aĉeti via nova aparato. Imagu kiel renversita tiuj homoj estus se Apple anstataŭ uzi pilo, por Ekzemple, por apliki la pluki supren de via nova ludilo. Do vostoj sencon, certe, kaj ni povas pensi pri ĉiaj aplikoj, supozeble, por vostoj, precipe kiam oni volas justeco. Do kiel eble ni apliki tiujn kiel datumstrukturo? Nu, mi proponas ke ni bezonas fari ĝin tiamaniere. Do mi tuj nun havas numerojn. Do ni devos konservi ĝin simpla kaj ne nepre parolas en terminoj de pletoj. Nur nombroj, ke homoj de alveninta. Kapablo tuj, denove, ripari la totala nombro de homoj kiuj povas esti en ĉi tiu linio, kiel tri aŭ ajn alia valoro. Sed mi proponas ke mi bezonas konservi trako ne nur de la grandeco de la vosto, kiom da aferoj estas en ĝi. Do grandeco estas la aktuala grandeco, kapablo estas la maksimuma grandeco. Nur denove, nomenklaturo per konvencio. Kial mi bezonas plian int ene de vosto al sekvigi kiuj estas en antaŭ la linio? Kial mi devas fari ke en tiu kazo? Nu, kial ĉi tiu bildo tuj ŝanĝos? Mi versxajne povas reuzi plej de ĉi tiu pentraĵo. Lasu min antaŭeniri kaj viŝi kio estas tie. Ni donos al tiu iomete malsama nomo ĝis ĉi tie. Ni forigi la 17, ni liveri de la 9, ni liveris de la 3. Kaj ni aldonu unu alia afero. Mi proponas, ke mi devas sekvigi la fronto de la listo, kiu estas ĝuste tuj estos int tiel. Kaj ni tuj teni ĝin simpla. Neniu ligitaj listo por nun. Ni agnoskas, ke ni tuj bump kontraux cxi tiun limon. Sed kion mi volas vidi okazi cxi tiun tempon? Do supozas ke mi iru antaŭen kaj la unua persono venas supren en linio, kaj ĝi estas la numero 9. Ni ja havas streson pilkojn. Ĉu mi povas sxteli, diru, du aŭ tri personoj? Unu, du, tri? Venu supren. Rajto de la fronto, ĉar ni faros ĉi tiu rapida. Ĉiu el vi nun tuj estos fano knabo en linio de Apple. Vi ne povas ricevi Apple aparataro fine de tiu though. Ĉio bone. Do vi estas numero 9, vi estas numero 17, numero 22. Ĉi tiuj estas arbitraj nombroj, kiel studento IDs aŭ whatnot. Kaj en nur momente, ni komencu komenci aldoni aferojn. Mi kuros la estraro tie ĉi tempo. Do, en tiu kazo, mi inicializado la fronto por esti - Mi fakte ne vere gravas kion la antaŭaĵo estas tio, ke la grandeco estas nulo. Do tio povus tiel simple esti demandosigno. Ĉi tiuj estas ĉiuj demandosignojn. Do nun ni komencas reale vidi iun homoj kiuj kovras ĉe la vendejo. Do se numero 9, vi estas la unua tie ĉe 5 AM, antaŭeniri kaj vicigas, aŭ la antaŭa nokto. Akcepti. Do nun 9 estas ĉi tie. Do 9 estas en la fronto de la listo. Do mi tuj iros antaŭen kaj ĝisdatigi la grandeco de tiu fluo datumoj strukturo por ne esti 0 plu, sed al esti 1. Mi tuj metos 9, je la Fronte al la listo. Lasu min antaŭeniri kaj ebligi la ekrano tiel ni povas vidi pasintajn nin ĉi tie. Kaj nun kion mi volas meti al antaŭa? Mi tuj sekvigi ke la Fronte al la vosto nun estas je situo 0. Pro kio sekva okazos? Nu, supozu nun mi enqueue 17 tiel. Do hop en linio tie. Kaj denove, la speco de pordo al la vendejo tuj estos tie. Do nun mi aldonis 17. Kaj eĉ se tiuj infanoj blokas la ekrano, tio estas OK, ĉar ni povas vidi ĝin tie. Pardonon. Spektantaro: Ni povas movi - DAVID Malan: Ne, tio estas okej. Ĝi estas grandega tie supre. Do 17 estas nun ene de la vico. Mi bezonas ĝisdatigi kiu kampoj nun kvankam? OK, definitive grandeco. Kaj kion pri antaŭa? OK, ne. Fronto ne devus ŝanĝi, ĉar kontraste de pilo, ni volas subteni justeco. Do se 9 venis unue, ni volas 9 esti la unua el la linio kaj en la vendejo. Fakte, vidu tion. Antaŭ ni enŝovu 22, ni antaŭeniri kaj dequeue 9. Kio estas via nomo denove? Spektantaro: Jake. DAVID Malan: Jake tuj esti dequeued nun. Do vi ricevas marŝi en la vendejo. Kaj ŝajnigi ke la vendejo estas tie. Do nun kio bezonas - dit-dit-dit! Kio devas okazi nun? Dezajno decido. Do ne estas malbona instinkto, sed - kio estas via nomo denove? Spektantaro: Davido. DAVID Malan: Davido. Do kio, David fari? Li provis ordigi de ripari la datumoj strukturo kaj movigxas de sia loko en Jake La eksa loko. Kaj tio estas bone se ni pretas akcepti ke kiel efektivigo detalo. Sed unue, ni ĝisdatigis la datumoj strukturo antaŭ ol ni faras tion. Ĉar mi ne placxis al mi la ideo de ĉiuj la popolo sxangxigxantaj en ĉi tiu linio. Ne estas granda interkonsento se Davido faras ĝin per unu paŝo, sed denove, opinias reen al kiam ni havis ok volontuloj en la scenejo kaj ni faris kiel inserción varon, kie ni devis komenci movi ĉiuj ĉirkaŭe. Kiu alvenis multekosta, ĉu ne? Tio igas min cringe pri granda O de n, granda O de n akordita denove. Tio ne sentante kiel idealan rezulton. Do ni simple ĝisdatigi ĉi. Do la grandeco de la vosto ne plu estas 2. Ĝi estas nun simple 1. Sed mi povas nun ĝisdatigi ion Mi ne ĝisdatigis antaŭe, la Fronte al la listo. Mi povis nur diri, estas ke situo 1? Do nun ni havas rubo valoro ĉi tie, rubo valoro ĉi tie, kaj Davidon en la Meze de ĉi tiu rubo. Sed la datumstrukturo ankoraŭ estas sendifekta. Kaj fakte, mi eĉ ne bezonas ŝanĝi Jake iama nombro 9, ĉar kiu zorgas. Mi havas sufiĉe informo nun en la grandeco, ke mi scias ke ekzistas unu persono en tiu vosto. Kaj mi scias, ke tiu persono estas en loko 1, ne 0. Mi ne rakonti. Do 1 kiel bone. Do la datumstrukturo ankoraŭ OK. Nu, kio okazas nun? Ni enqueue - kio estas via nomo? Spektantaro: Callen. DAVID Malan: Callen. Ni enqueue a Callen, kaj 22 estas nun en la vico. Do nun kio devas ŝanĝi ĉi tie? Fronto ne tuj ŝanĝi, evidente. Grandeco tuj ŝanĝos esti 2 denove. Kaj 22 finas ĉi tie, 9 estas ankoraŭ aktuala, sed estas efektive rubo valoro nun. Estas nur la restintoj de Jake pasinteco. Do nun kio okazas se Mi dequeue David? Unu lasta operacio, dequeue Davido. Ni povis ŝanĝi, sed mi proponas Atendu fari tiel malmulta laboro kiel ebla. Nun mia datumstrukturo iras apogi en grandeco de 2 al 1. Sed la fronto de la vosto nun iĝas 2. Mi ne bezonas ŝanĝi tiuj numeroj nur ankoraŭ, ĉar ili estas nur rubo valoroj. Sed nun kio okazas? Supozu mi enqueue mem, 26? Mi sentas ke mi apartenas ĉi tien. Do mi esti enqueued. Do mi specon de aparteni ĉi tie. Kaj eĉ se vi ne sufiĉe estimi ĉi vide sur la scenejo, ĉar ni havas multe da ĉambro, mi devus ne staras tie, kial? Spektantaro: Vi estas ekster limojn. DAVID Malan: Ĝuste. Mi estas el limojn. Mi indeksita preter la limoj de tiu tabelo. Mi vere devus esti en unu el la tri eblaj lokoj. Nun, kie estas plej natura iri? Mi proponas ke ni leveraged semajno unu artifiko. La mod operatoro, procento. Ĉar mi teknike staris situo 3, sed mi faras 3 _mod_ kapablo, tial 3, procento signo, 3 - kapablo estas 3. Kio estas tio? Kio estas la resto kiam vi dividas 3 por 3? 0. Do kiu metas min estis Jake estis, kiu estas vere bona. Do nun la efektivigo de tiu afero tuj esti iom pri kapdoloro. Estas vere nur unu linio de kapdoloro, de kodo. Sed almenaŭ nun tie estas rubo valoron tie, sed ekzistas du legitima ints tie. Kaj mi asertas ke nun ni faris ĝuste kion ni bezonas por fari tiel longe kiel ni ŝanĝas kion Jake la valoro devis esti 26. Ni nun havas sufiĉe informo ankoraŭ subteni la integrecon de tiu datumstrukturo. Ni estas ankoraŭ ia el sorton, kiam ni volas enmeti kvar aŭ pli entute elementoj, sed mi povas almenaŭ fari belan efika uzo de ĉi tiu konstanto tempo, fakte. Mi ne devas maltrankviligi sxangxigxantaj ĉiuj, kiel David deklivo estis. Ajna demandojn sur piloj, aŭ ĉi vosto? Spektantaro: Ĉu la kialo kial vi bezonas grandeco por vi scias kie havi persono? DAVID Malan: Ĝuste. Mi bezonas scii la grandecon de la tabelo ĉar mi bezonas scii precize kiel multaj de ĉi tiuj valoroj estas legitima, kaj por ke mi povas trovi kie meti la sekvanta persono. Ekzakte. La grandeco estas - fakte, ni ne ĝisdatigis ĉi ankoraŭ. Mi aldonis min je 26. La grandeco estas nun, ne 1, sed 2. Do nun tio ja helpas min trovi la estro de la listo, kiu estas ne 0, ne 1, sed estas 2. La fronto de la listo estas ja la numero 22. Ĉar li venis en la komenco, do li devus esti permesita en la vendejo antaŭ mi, kvankam vide Mi staras pli proksime al la vendejo. Ĉio bone? Ronda de aplaŭdo por tiuj infanoj kaj ni lasu ilin el tie. [Aplaŭdo] DAVID Malan: Mi povus lasu vi observos la pleto. Ni povis vidi kio okazas se vi volas, sed eble ne. Ĉio bone. Do kio nun faras kiuj lasas al ni? Nu, mi proponas ke tie estas kelkaj aliaj datumstrukturoj ni povis eku aldoni al nia ilo kit kiu volo reale esti sufiĉe, sufiĉe grava kiel ni plonĝi en retejo aĵoj. Kiu denove, ĝi havas ian rilaton trees en la formo de iu nomita DOM, dokumento objekto modelo. Sed ni vidos pli ke antaŭ longe. Permesu al mi proponi definitionally ke ni voki arbo nun kio vi eble scias kiel pli de familio arbo, kie vi havi iu praulo en la radikoj de la arbo. Al patriarkaj aŭ matriarca ĉe la plejsupro de la arbo. Sen lia edzino, en tiu kazo. Sed ni havas nun kion ni nomas infanoj, kiuj estas nodoj kiuj pendas ekstere la maldekstra infano aŭ la dekstra infano, sagoj kiel reprezentita tie. En aliaj vortoj, en arba datumstrukturo en komputilo, arbo havas nula aŭ pli nodoj. Se ĝi havas almenaŭ unu nodo, kiuj nomiĝas la radiko. Ĝi estas la aĵoj vide ke ni desegni ĉe la supro. Kaj tiu nodo, kiel ĉiu alia nodo, ĉu havas nulo, unu, aŭ du, aŭ tri, aŭ tamen multaj infanoj la datumstrukturo elportas. En tiu kazo, la radiko, stoki la valoro, ĝi havas du filojn, 2 kaj 3, do ni ĝenerale nomas 2 maldekstren infano kaj 3 la dekstra infano. Kaj poste kiam ni atingos suben ĝis 5, 6, kaj 7, 6 povus nomi la mezo infano. Se vi havas kvar infanojn, metas konfuza. Do ni ĉesi uzi tian de ŝparvojo parole. Sed estas vere nur familio arbo. Kaj la folioj tie estas la nodoj kiuj mem ne havas infanoj. Ili pendas sur la malsupro de la arbo. Do kiel eble ni apliki arbo kiu havas nur du infanoj maksimume? Ni nomas ĝin duuma arbo. Bi denove signifas du, en tiu kazo, kiel kun binara. Kaj tial ĝi povas havi nulo, unu, aŭ du infanoj maksimume. Mi proponas ke ni havas la nodo por tiu strukturo kun int n, kaj tiam du montriloj, oni nomas lasis, oni nomas prava. Sed tiuj estas nur bela arbitrajn konvenciojn. Kaj kio estas bela nun, speciale se vi speco de baraktis koncepte kun rekursio, aŭ pensis ke ne estis vere solvon por nenion, precipe se vi povus kuru el memoro. Nun, kiam ni parolas pri datumoj strukturoj kaj algoritmoj kiuj permesas ni trairi kaj manipuli ilin, rezultas ke rekursio revenas en multe pli konvinka se ne bela vojo. Do tio mi proponas estas la efektivigo de Serĉu funkcio. Donita du enigoj - tiel pensas pri ĉi tion kiel nigran skatolon. Donita du eniroj, n, an int, kaj puntero al arbo, puntero al nodo, aŭ vere la radiko de arbo, mi aserto, ke tiu funkcio povas reveni vera aŭ malvera, ke valoro n estas ene de ĉi arbo. Kio estas ene de la nigra skatolo? Nu, kvar branĉoj. La unua nur kontrolas. Se arbo estas nula, nur redoni malvera. Se ne estas nodo, ne estas n, ne estas nombro, nur redoni malvera. Se tamen, n, la valoro kiun vi sercxas por, estas malpli ol arbo sago n, kaj nur por esti klara, kion tio signifas kiam Mi skribas arbo kaj poste la sago notacio, n? Ekzakte. Ĝi signifas ke dereference pointer nomata arbo. Iru tie, kaj poste ene de tiu nodo kaj akiri lia kampo nomata n. Kaj poste kompari la aktualan n kiu estis pasis al Serĉu kontraux gxi. Do se n estas malpli ol, la n valoro en la arbo nodo mem, nu, kion tio signifas? Tio signifas nenion al unua vido. Ĝuste? Ĝuste kiel kiam vi havas aron da valoroj, vi eble ŝatus apliki duuma serĉi kiel formo de divido kaj venki. Sed kion supozo ni bezonas por fari por duuma serĉo por labori en la tuta en la telefono libron kaj antaŭaj ekzemploj? Kiel estu ordigita. Do ni rafini la difino de arbo tie ne esti simple arbo, kiu povas havi ajnan numeron de infanoj. Ne nur duuma arbo, kiu povas havi 0, 1, aŭ 2 maksimume. Sed kiel duuma serĉarbo, aŭ BST, kiu estas nur imago maniero diri al duuma arbo tia, ke ĉiu nodo maldekstra infano, se ĝi ĉeestas, estas malpli ol la nodo. Kaj cxiu nodo la dekstra infano, se ĉeestas, estas pli granda ol la nodo mem. Do, en aliaj vortoj, se vi estus desegni la arbo ekstere, ĉiuj de la nombroj estas atente balancis kiel ĉi tiel ke se vi havas 55 kiel la radiko, 33 povas iri al lia maldekstra ĉar ĝi estas malpli ol 55. 77 povas iri al lia dekstra ĉar ĝi estas pli granda ol 55. Sed nun rimarkas, la sama difino, ĝi estas rekursia difino parole, devas peti 33. 33 la maldekstra infano devas esti malpli ol ĝi, kaj 33 la dekstra infano, 44, devas esti pli granda ol ĝi. Do tiu estas duuma serĉo arbo, kaj Mi proponas, uzante iomete da rekursio, ni povas nun trovi n. Do se n estas malpli ol la valoro n tio nuna nodo, mi tuj iros antaŭeniris kaj liberigas, por tiel diri, kaj ĝuste revenu ajn la respondo estas de serĉante n sur la arbo maldekstra infano. Rimarku denove, ĉi tiu funkcio nur atendas nodo stelo, puntero al nodo. Do certe mi povas nur faru arbo sago maldekstren, kio kondukos mi al alia nodo. Sed kio estas tiu nodo? Nu, laŭ ĉi tiu deklaro, maldekstra estas nur referenco, tiel ke nur signifas Mi pasante al la serĉo funkcio malsama pointer, nome kiu reprezentas mia maldekstra infano arbo. Do, en tiu kazo, la puntero al 33, se tio estas nia specimeno enigo Dume, se n estas pli granda ol la valoro n je la nuna nodo en la arbo, tiam mi estas tuj iros antaŭen kaj liberigas en la alia direkto kaj nur diru, mi ne scii se tiu valoro n estas en la arbo, sed mi scias se ĝi estas, ĝi estas sube mia dekstra branĉo, por tiel diri. Do lasu min vokas: rekursie esplori, pasante n denove, sed pasante en puntero al mia dekstra infano. En aliaj vortoj, se mi estas aktuale ĉe 55 kaj Mi serĉas 99 Mi scias, ke 99 estas pli granda ol 55, do ĝuste kiel mi disŝiris la telefono libro semajnoj kaj ni iris dekstren, simile ni estas tuj iros ĉi tie. Kaj mi ne scias se ĝi estas ĉe mia dekstra infano, kaj ĝi ne estas, 77 estas tie, sed Mi scias ke estas en tiu direkto. Do mi nomas serĉu per mia dekstra infano, 77, kaj lasu serĉo figuro el tie se 99 en tiu arbitra Ekzemplo estas efektive tie. Alie, kio estas la fina kazo? Se arbo estas nula estas unu kazo. Se n estas malpli ol la aktuala nodo valoro estas alia kazo. Se n estas pli granda ol la aktuala nodo valoro estas tria kazo. Kio estas la kvara kaj lasta kazo? Mi kredas ke ni estas el kazoj, ĉu ne? Devas esti ke n estas en la nuna nodo ke mi estas sur. Do se mi sercxas 55 je ĉi tiu punkto en la rakonto, tiu branĉo de la arbo revenus vera. Do kio estas interesa estas, ke ni fakte, kontraste semajnoj pasis, ni speco de havi du bazo kazoj. Kaj oni ne devas estu ĉiuj ĉe la supro. La supro estas bazo kazo ĉar se la arbo estas nula, estas nenio por fari. Nur reveni malmola kodita valoro de falsaj. La fundo branĉo estas varo de la implicite, per kiu, se ni kontrolis por nula, ni kontrolis se ĝi devus esti forlasis, sed gxi ne, ni kontrolis se ĝi devus esti bone, sed ne devus esti, klare ĝi devas esti ĝuste kie ni estas. Tio estas baza kazo. Do ekzistas du rekursiaj kazoj sandwiched tie en la mezo. Sed mi povus esti skribita tiu en ajna ordo. Mi nur pensis ke speco de sentis natura unue kontroli por ebla eraro, tiam kontrolu restis, tiam kontrolu pravas, tiam supozu ke vi estas en la nodo vi fakte serĉas. Do kial cxu tio estos utila? Do rezultas - kaj mi saltas al teaser tie estas en la TTT. Ni tuj ekuzi ne plani lingvon unue, sed markado lingvo. Al HTML lingvon estante unu tio estas simila en spirito programado lingvo, sed ĝi ne donas al vi la kapablo esprimi sin logike. Ĝi nur donas al vi la kapablon esprimi sin strukture. Kie vi volas meti ion en la paĝo, la retpaĝo? Kian koloron vi volas fari ĝin? Kio tiparo vi volas fari ĝin? Kio vortoj ĉu vi vere volas en la retpaĝo? Do tio estas markado lingvo. Sed tiam ni devos tre rapide enkonduki Javascript, kiu estas plene disvolviĝinta programado lingvo. Tre simila sintakse laŭ aspekto al C, sed havos iujn bela, pli potenca, pli uzanto amika karakterizaĵoj. Kaj unu el la frustroj en ĉi punkto en la semestro estas ke ni instruos vin frue apliki Speller en multe malpli da linioj de kodo uzante aliajn lingvojn ol C mem permesas, sed por kialo estas ni baldaŭ komprenis. Tiu estos la unua tia retpaĝo. Ĝi estos tute underwhelming, la unua ni faras. Ĝi simple diri, saluton mondo. Sed se vi neniam vidis ĝin antaŭe, tio estas HTML, Hiperteksto Markup Language. Se vi iras al iu menuo opcion en plej ajna retumilo, en ajna retpaĝo sur interreto, vi povos vidi la HTML ke iu homo skribis al krei tiun ĉi paĝon. Kaj probable ne aspektas kiel mallonga aŭ neta kiel ĉi tio. Sed ĝi sekvos la modelon de ĉi tiuj malfermita krampoj kaj slashes kaj literoj kaj potenciale nombroj. Mi pensis, ke mi volas doni al vi teaser kion vi povos fari post preni CS50. Permesu al mi iri al cs.harvard.edu / ŝteli, nia propra Rob Bowden la hejmpaĝo. Li faris tion por ni. Do vi baldaux povos fari tion. Kaj ankaŭ, kion vi aŭdis ĉi-matene - kion vi auxdis tiun matenon - [Hamstro DANCU MUZIKO] - You'll povos fari tion. Ke atendas nin je merkredo. Ni vidos vin tiam. [Hamstro DANCU MUZIKO] DAVID Malan: Je la sekvanta CS50 -