DAVID Malan V redu. Dobrodošli nazaj v CS50. To je začetek 8. tednu. In opozarjajo, da problem set 5 končalo z malo izziv. Torej, ob predpostavki, da izterja vse vaše poučevanje Fellows in fotografije CA v datoteki card.raw, ste upravičeni za zdaj našli vse te ljudi, in en srečen zmagovalec bo hodil domov z enim od teh stvari, skok predlog Naprava, ki jo lahko uporabite za končno projekti, na primer. 

To, vsako leto vodi malo creepiness. Pa kaj sem mislil, da sem naredil, je delež z vami nekaj opomb, ki imajo šli naprej in nazaj Seznam osebja prepozno. Na primer, samo sinoči citatom citata iz ene osebja člani, "sem imel študentsko trkanje na moja vrata, da posnamete fotografijo z mano. Zalezovalci, vam povem. "Začelo precej opisna in potem smo se preselili na, uro ali tako kasneje, "Imel sem Študent me čaka po oddelku in je imel vse naše imena in fotografije na nekaj listov papirja. "Vse je v redu. Tako organizirana, vendar ne vse to grozljivo še ni. 

Potem, "sem bil iz mesta ta vikend, in ko sem se vrnil, je bil eden od moja spalnica. "[SMEH] DAVID Malan: Naslednji citat iz osebja član, "študent prišel v mojo hišo na Somerville ob 4:00 zjutraj. "Next Osebje, "sem prišel do mojega hotela v San Francisco in študent je čakala me je v preddverju s tremi dslr. " Vrsta fotoaparata. "Nisem niti za zaposlene ta semester, ampak študent je vlomil v mojo hišo to zjutraj in posnel celotno stvar z Google Glass. "In potem končno, "Vsaj 12 ljudi, ki so nestrpno čaka za mene, ko sem prišel iz mojega limuzina, nato pa sem zbudil. "V redu. Torej med slikami, kot si lahko spomnim, je ta človek tukaj, kdo ste Morda veste, kot Milo Banana, ki živi z Lauren Carvalho, naše glave poučevanje člana. Milo, Milo, pridi sem fant. Milo. Milo. Misli si, on je nosil Google steklo, tako da vam bomo pokazali vse to potem. Torej, to je Milo, če bi želeli slikati z njim kasneje. Če želite, da pazi na občinstvo tam. OK. To je dober posnetek. No, Milo Banana. Oh, ne delaj tega. 

[SMEH] 

OK. Torej besedo, potem o tem, kaj je pred nami, saj, kot smo začeli prehod, ta teden posebej od C pri ukazni vrstici okolja v PHP, in JavaScript ter SQL in HTML in CSS v okolje spleta, bomo vam opremljanje z vsemi Več znanja za potencialnih končnih projektov. V ta namen so, seveda ima tradicija seminarjev, ki so na dotikajo teme v teku. Zelo povezana z načrtovanjem in Razvoj app in tako naprej, vendar ni nujno proučiti Tečaj lastne učni načrt. 

Torej, če vas bo morda zanima ena ali več od letošnjih seminarjev, registrirati na cs50.net/seminar. Obstajajo starejši seminarji ob cs50.net/seminars. In na roster doslej za to leto so Amazing Web Apps z Ruby na Tirnice, ki je alternativa jezik za PHP. Computational Linguistics. Uvod v iOS, ki je platforma, ki se uporabljajo za iPhone in iPad razvoj. Javascript za Web Apps bomo zajema da, vendar v tem seminarju, boš šel bolj v podrobnosti. 

Predlog preskok, tako da bomo dejansko imeli nekaj naših prijateljev iz Leap Motion, družba sama, se nam pridružite. Jutri, v resnici, da zagotovi hands-on seminarju, če , ki vas zanimajo. Meteor.js, alternativna tehnika uporabljajo JavaScript ni v brskalniku ampak na strežniku. Node.js, ki je zelo v tej smeri, kot tudi. Tanko Android dizajn. Android pa zelo priljubljena alternativa za iOS in Windows Phone in druge mobilne platforme. In Web Security Active Defense. 

Torej, v bistvu, če bi želeli da se vključijo v to, kaj mi zapomnite si to. Zelo smo veseli, da rečemo, da Naši prijatelji Prestopna Predlog, ki je ob zagonu - ta naprava res samo prišel pred nekaj meseci - je milostno daroval 30 takih naprav v razredu za toliko študentov, če bi radi, da se zadolži strojne opreme proti koncu semestra in jo uporabite za Dejanski končni projekt. Jih podpirajo več jezikov. Nobena od njih C, nobena od njih PHP, tako dosego enega ali več od teh seminarjev lahko izkaže interesa. In vse od njih bo posnet v V primeru, da ne boste mogli udeležiti osebno. Načrt je napovedal preko email, kot smo strdi sobe. 

In nenazadnje, če greš na projects.cs.50.net, to je spletna stran trdimo, da je vsako leto povabimo ljudje iz skupnosti, fakultete, oddelki, osebje, in obe v zunanji CS50 do predlagala projektne ideje. Stvari, ki so v interesu študentskih skupin. Stvari, ki so v interesu službe. Torej, ne pa tam, če ste se borijo z negotovostjo glede tega, kaj si želi lotiti. 

Torej zadnjič, ko smo uvedli verjetno bolj zapletena struktura podatkov, kot sva videli v zadnjih tednih. Mi bi bili z uporabo nizov precej srečno kot koristno, če poenostavljeno strukturo podatkov. Potem smo uvedli ti, ki Seveda so povezane sezname. In tisto, kar je bil eden od motivov za uveljavitvijo te podatkovne strukture? Ja? Kaj je to? 

PUBLIKA: Dynamic velikost. 

DAVID Malan: Dynamic velikost. Torej, medtem ko je v polju, morate vem, njeno velikost predplačila, kadar jo dodeli. V povezano seznamu, pa ne vedeti, da. Lahko samo malloc, ali bolj na splošno, dodeli dodatna vozlišče, tako rekoč kadarkoli želite vnesti več podatkov. In vozlišče ni vnaprej določen pomen. To je samo splošen izraz, ki opisuje nekakšen posodi, ki smo uporabo v našem podatkovne strukture za shranjevanje nekatere element interesa, ki v tem primer zgodi, da bo cela. 

Ampak tam je vedno kompromis. Tako smo dobili dinamične velikosti podatkov strukture, ampak kakšno ceno bomo plačali? Kaj je slaba stran povezanih seznamov? Ja? 

PUBLIKA: zahteva več pomnilnika. 

DAVID Malan: To zahteva več spomin, kako točno? 

PUBLIKA: [neslišno]. 

DAVID Malan: Točno tako. Torej, zdaj smo kazalci prevzemu Dodatni spomin, da smo v preteklosti ni potrebno, ker prednost v matriki, seveda, da vse je stikata, nazaj nazaj na hrbtu, ki vam naključni dostop. Ker samo z uporabo kvadratnega nosilec Zapis, ali bolj tehnično kazalec aritmetika, zelo preprost dodatek, lahko dostopate do katere koli elementi v enakem času. In v resnici, da je nekako namiguje na še cena, ki smo si plačal z povezani seznam. 

Kaj se zgodi, da v času poteka nekaj podobnega Search, če želim našli nekaj vrednosti in notranjost v povezanem seznamu? Kaj mi teče čas postali? Big O n. Če je to urejeno za? Kaj pa, če je struktura podatkov razporejene? Lahko naredim bolje kot velika O n za iskanje? Ne, ker v najslabšem primeru bi lahko bilo zelo dobro rešiti, število iščete lahko velik. Morda je številka 100, ki se lahko zgodi, da bo vse Tako na koncu. In zato, ker lahko le dostop povezano Seznam v tem izvajanju, ki jih način svojega prvega vozlišča, si Še vedno nekako od sreče. Moraš prečkala celotno stvar od prve do zadnje, da bi našli da je velika vrednost kot 100.. Ali ugotoviti, če je to sploh ne obstaja. 

Torej ne moremo storiti kaj algoritem v podatkovnem struktura, ki je videti takole? Tega ne moremo narediti binarno iskanje, saj binarno iskanje potrebno, da smo imeli random access. Mi lahko samo preskok od lokacije do mesto brez nadaljnje ti krušnih drobtin v obliki vseh teh kazalcev. 

Zdaj, kako smo izvajati to? No, če gremo na zaslonu tukaj, če bomo lahko hitro reimplement te podatke strukturo - moj rokopis še ni vse, da je super tukaj, ampak bomo poskušali. Torej typedef struct, in kaj sem želite poklicati to stvar tukaj gor? Vozlišče. Tako da bom naju začel. In zdaj, kaj mora biti znotraj Struktura podatkov za to posamezno povezani seznam? Koliko polja? 

Torej dva. Ena je zelo enostavno. Torej, int n. In lahko rečemo n karkoli hočemo, vendar mora biti int, če smo izvajanje povezan seznam za ints. In kaj zdaj počne drugega polja morajo biti? Struct vozlišče *. Torej, če naredim struct vozlišče *, potem pa sem To lahko pokličete tudi kar hočem, ampak samo, da je jasno, bom poklicala je naslednji korak, saj smo počeli. In potem bom zaprem zavite oklepaje. 

In zdaj, kot zadnjič, Sem dal vozlišče tukaj. Ampak, če sem to razglasitvi je kot vozlišče, zakaj se sploh trudim, da tako verbose tukaj razglasitvi Struct vozlišče * naslednji, v nasprotju na samo vozlišče * naslednji? Ja? 

PUBLIKA: [neslišno]. 

DAVID Malan: Točno tako. Točno tako. Ker C res vas popelje dobesedno in vidi le opredelitev vozlišča Tako sem dol, ne smeš Če ga želite videti tukaj. Torej imamo te vrste preemptive Izjava tukaj, ki je sicer bolj verbose. Struct vozlišča, kar pomeni, da sedaj lahko dostopate do znotraj strukture podatkov. 

In stran, ker je to postane malo bolj subjektivna zdaj, zvezda lahko tehnično iti tukaj, da lahko gredo tu, lahko pa celo iti v sredini. Sprejeli smo v slogu priročnika za Tečaj, konvencija dajanje zvezda tik podatkov vrste, ki je v tem primeru bi struct vozlišče. Ampak uresničiti v veliko učbenikov in spletne reference, boste morda celo ga vidimo na drugi strani. Ampak samo zavedati, da bo tako dejansko delo in bi morali biti zgolj dosledna. 

Vse je v redu. Tako da je bila naša izjava od struct vozlišča. Ampak potem smo začeli delaš več prefinjene stvari. Na primer, smo se odločili, da uvedejo nekaj podobnega hash tabelo. Torej, tukaj je razpršena tabela velikosti n, indeksirane od 0 na vrhu levo do n minus 1 na dnu levo. To bi lahko hash miza za karkoli. Ampak kaj vrste stvari nismo govorili o uporabi razpršene tabele za? Shranjevanje kaj? 

Imena. Mi lahko storite imena, kot so sva zadnjič. In res, lahko shranite ničesar. In bomo to spet videli v PHP in JavaScript. Razpršene tabele je lepo nekakšen švicarski Nož, ki vam omogoča, da shranite precej karkoli hočeš v notranjosti je s povezovanjem ključe z vrednostmi. Tipke z vrednostmi. 

Zdaj v tem preprostem primeru, naša Tipke so samo številke. Mi izvajanje hash miza kot niz. In tako so tipke 0, 1, 2, in tako naprej. In tako mi, kot ljudje, odločila zadnja teden, da veš kaj, če smo bo trgovina imen, kaj je samo samovoljno, ampak precej razumno, Predvidevam, da Alice, ime, bo samo indeksirane v 0. Bob, ime B, bo indeksirana v 1, in tako naprej. Tako smo imeli preslikavo med vhodi, ki so nizi in razpršitve Mesta, ki so številke. 

Tako se ta postopek splošno znana kot hash funkcija, in lahko resnično je v kodi izvajati. Če bi želel izvajati funkcijo razpršitve da počne točno to, kar smo pravkar opisal v zadnjem času, morda sem razglasi funkcijo, ki bo, kot je vhod na primer - in dajmo to narediti na tem Zaslon tukaj. Če bi želel izvajati hašiš funkcijo, bi lahko rekel kaj takega. 

To se dogaja, da se vrnete int. To se dogaja, da se imenuje hašiš, in to je bodo sprejeti kot argument niz, ali smo lahko bolj pravilno zdaj, in pravijo, char *, bomo pa s poklicati. In potem vse to funkcijo mora storiti, na koncu se vrne int. Zdaj, kako to počne, da bi lahko Ne bodi tako jasna. Jaz grem za izvajanje tega brez Oblika preverjanja napake zdaj. Grem na slepo reči, vrnitev vse, kar je v nosilcem S 0, minus, recimo, kapital podpičjem. 

Popolnoma zlomljen. To ni popoln, saj eno, kaj pa če je ničen? Slabe stvari se bo zgodilo. Dva, kaj če prva črka v tem Ime ni začetnico? To ne bo obrniti iz vrtin. Morda bi bilo male črke ali ne, pismo sploh. Torej povsem dovolj prostora za izboljšave tukaj ampak to je osnovna ideja. 

Kaj smo ustno opisal zadnji teden samo proces kartiranje Alice v 0 in Bob 1, se lahko izrazi Vsekakor bolj formulaically kot C deluje tukaj. Je znova poklical hašiš, je niz kot vložek, nato pa nekako ne nekaj s tem input za proizvodnjo izhod. Ni za razliko od naše črne opis box da smo dolgo storili. Ne vem, kako bi to lahko bilo delajo pod pokrovom. 

Problematičnega set 6, enega izmed izzivov je za vas, da odloči, kaj bo vaš hash funkcija je? Kaj se dogaja, da se notranjost da črna polje, in verjetno, da bo malo bolj zanimivo, kot je ta, in vsekakor bolj nagnjeni k napakam preverjanje, kot to predvsem izvajanje. 

Vendar težave lahko nastopijo, kajne? Če imamo podatkovno strukturo, kot je to ena, kar je eden od problemov lahko vodijo v daljšem časovnem obdobju, kot ga vstavite več imen v razpršene tabele? Dobiš trčenja, kajne? Kaj pa, če imate Alice in Arona, dve osebi, katerih imena se je zgodilo za začetek? To Zastavlja se vprašanje, kjer ste dal drugo takšno ime? 

No, morda naivno pravkar dal kjer Bob pripada, potem pa je Bob vrsta zajebali, če boste poskušali vstavite svoje ime zraven in ni prostora za njega. Tako da boste morda dal Boba, kjer je Charlie, in si lahko predstavljate to zelo hitro decentralizacijo v malo nered. Nekaj ​​linearno na koncu, kjer ste samo treba iskati celotno stvar išče Alice in Bob ali Aaron ali Charlie. 

Torej, namesto da smo predlagali, namesto samo linearno sondiranje za odprte prostore in plopping imena Tam smo Predlog Ljubitelj pristop. Hash tabela izvajajo Å¡e z matrika indeksov, vendar podatkovni tip ti indeksi zdaj so bili kazalci. Kazalci na kaj? Kazalci, povezanih seznamov. 

Ker opozarjata, da je povezani seznam res samo kazalec na vozlišče in vozlišče ima naslednje polje, in da vozlišča Ima naslednje polje, in tako naprej. Tako lahko sedaj razmišljati o tem polju na Leva stran od razpršilne tabele kot vodi v povezano seznamu. Prednost, ki je, če dobiš trčenje med Alice in Aronu kaj storiti z Druga taka oseba? Pravkar ste mu priložite ali ji Konec ali celo začetek tega povezanega seznama. 

In pravzaprav, kaj je samo testenin preko da za sekundo. Kjer bi bila najbolj smiselna? Če sem vstavil Alice in ona pristane na prvo mesto, potem pa skušam vstaviti ime Aronovi, in tam Očitno trčenje, naj dam ga v začetku iz povezanega seznama? To je v tistem prvem mestu, ali na koncu? 

PUBLIKA: [neslišno]. 

DAVID Malan: OK. Slišal sem, začenja. Zakaj na začetku? 

PUBLIKA: [neslišno]. 

DAVID Malan: OK. To je po abecedi, tako da je lepo. To je dobra lastnost. To mi bo prihranilo nekaj časa potencialno. To ne bo pustila narediti binarno iskanje, vendar sem bi vsaj lahko izbruhnejo iz zanke, če se zavedam, no, jaz sem pot preteklosti so Aaron bi bilo v ta razporejene seznam povezano. Nimam izgubljati svoj čas iščejo vse do konca. Tako da je razumno. Zakaj bi si želeli, da vstavite trka na ime začetek seznama? Kaj je to? 

PUBLIKA: [neslišno]. 

DAVID Malan: To lahko traja dolgo časa da se na koncu seznama. In v resnici, daljša. Več imen, ki jih vstavite začnete z, več, da veriga bo dobil. Več vezana Seznam bo dobil. Torej ste res samo zapravljaš svoj čas. Morda ste bolje ohranja konstantna čas vstavitve, velik O od 1, z vedno dajanje trka na ime začetek povezano seznama in ne skrbi toliko, o razvrščanju. 

Kaj je najboljši odgovor? To je jasno. Nekako je odvisno, kaj distribucija, kaj vzorec imen vstavljate. To ni nujno Očiten odgovor. Ampak tukaj, še enkrat, je Oblikovanje priložnost. 

Tako smo nato pogledal na to stvar, ki je res druga velika priložnost za p-set 6. In zavedaš, če tega še niste storili, Zamyla potopi v oboje, zgoščevalne mize in poizkusih podrobneje. In video potopis vgrajeni v p-set spec. To je Trie - T-R-I-E. In kaj je bilo zanimivo to je bil, da čas teče o iskanju imena, kot so Maxwell Zadnjič, ko je bil velik O česa? Kaj je to? 

PUBLIKA: število črk. 

DAVID Malan: Število črk. Slišal sem dve stvari. Število pisem in konstantno časa. Torej gremo s tem prvi. Število črkami. No, ta struktura podatkov, odpoklic, je kot drevo, družinsko drevo, vsak od katerih vozlišča sestavljajo nizi. In ti nizi so kazalci druga takšna vozlišča ali drugih kot polja v drevesu. 

Torej, če smo želeli ugotoviti, nato ali je Maxwell tukaj, jaz bi šel do prvega niza, na sam vrh drevo, tako imenovani root vrh Trie in sledite m kazalec, Nato kazalec, potem x, w, e, l, l. In potem, ko sem videl nekaj posebnega simbola tukaj označen kot trikotnik. V kodi boste videli, predlagamo, da izvaja kot bool, samo rekel ja ali ne, beseda ustavi tukaj. 

No, ko smo šli na M-A-X-W-E-L-L, počuti kot sedem, morda osem, če gremo eno mimo njega, osem koraki, da bi našli Maxwell. Ali pa recimo ji K. pokličite Toda spomnimo zadnje Tokrat sem trdil, da če obstaja realno največja dolžina na beseda, kot je 40-nekaj-ak znakov, maksimalna dolžina pomeni konstanta. Torej res, ja, to je tehnično veliki O z dne 8. ali 7, ali res veliki O iz K. But če je končna kapa o tem, kaj K lahko, da je konstantna. In tako je velik O od 1 v konec dneva. 

Ne v resničnem svetu. Ne, ko ste dejansko začnete gledal ura kot delovanje vašega programa. To je absolutno bo nekoliko počasneje kot resnično konstanten Čas z enim korakom. To se dogaja, da je sedem ali osem korakov, pa še to je veliko, veliko bolje kot algoritem kot veliki O n tem je odvisna od velikosti, kaj je v struktura podatkov. 

Obvestilo glavo tu lahko vstavite milijon imen v tem podatkovne strukture, ampak koliko več korakov se dogaja, da nas bo najti Maxwell v tem primeru? Jih ni. On je nespremenjena. In do sedaj, ne verjamem, da smo videli Primer podatkovno strukturo ali Algoritem, ki je bila v celoti vpliva zunanjih vedenja, kot je ta. Ampak to ne more biti neverjetno. To ne more biti edina rešitev za p-set 

In to ni. To ni nujno podatkov Struktura morate gravitirajo, ker je tako kot hash tabele, kompromis. Kakšna je cena, ki jo plača tukaj? Spomin. Mislim, da je to grozna količino pomnilnika. In ne moreš kar vidim tukaj, ker avtor te slike Očitno okrnjena vsi nizi, in ne bomo videli veliko je in B-jev in C ter Q in Y-ov in Z je v teh nizi. Ampak oni so tam. 

Vsaka od teh vozlišč je cela vrsta nekaterih 26 ali več bajtov, v vsaki kar predstavlja pismo. 27 v našem primeru, tako da se lahko podpre opuščaji na problem nizu. Torej je to podatkovna struktura je res, res gosto in široko. In da sam morda na koncu upočasnjuje stvari navzdol, ali vsaj stanejo Veliko več prostora. Ampak spet, lahko črpamo primerjave tukaj. 

Spomnimo se nekaj časa nazaj, smo dosegli veliko bolj razburljivo tekmovanje v teku časa s sortiranjem ko smo uporabi zlivanjem, ampak cena smo plačali za doseganje n log n za spajanje sortiranje zahteva, da smo preživeli več kaj sredstev? Več prostora. Potrebovali smo sekundarni array kopiranje ljudi v, tako kot smo tukaj na odru. Torej, še enkrat, ni jasnih zmagovalcev, ampak samo subjektivna zasnova Odločitve je treba opraviti. 

Vse je v redu. Torej, kaj pa je to? Vsakdo, ki priznavajo D-Hall? OK. Torej tri od nas. Mather House. Torej, to je za jedilnico Mather je. Stavim, da so vsi jedilnici imajo skladovnice pladnjev, kot je ta. In to je pravzaprav predstavnik nečesa, kar smo jih očitno že videli. Poklicali smo ga dobesedno kup. In kup, v smislu vašega računalnika spomin, je, če gre podatki medtem ko so funkcije se imenuje. 

Na primer, kakšne stvari gredo na stack v zvezi z Postavitev spomin smo razpravljali V zadnjih tednih? Kaj je to? 

PUBLIKA: Klici funkcij. 

DAVID Malan: Žal mi je. 

PUBLIKA: Klici funkcij. 

DAVID Malan: Klici funkcij, vendar Natančneje, katero je znotraj vsakega te okvirje? Katere vrste stvari? Ja. Tako lokalne spremenljivke. Kadarkoli smo potrebovali nekaj lokalno shranjevanje, kot argument, ali int I, ali int temp, ali karkoli lokalnih spremenljivka, smo bili dajanje da na sklad. In mi je kup pokličete, ker te ideje plastenje. Nekako tekmah z realnostjo, Pogodbe koncept. 

Vendar pa se izkaže, da sklad lahko tudi treba obravnavati kot strukturo podatkov Alternativa matriko, alternativa v povezano seznamu. Nekaj ​​konceptualno bolj zanimivo da lahko še vedno izvaja z uporabo enega od tistih stvari, ampak to je drugačen tip podatkovna struktura podpira, res, le dve operacije. Lahko pa dodate na Ljubitelj funkcij, kot ti. Ampak to so osnove - potiskanje in pop. 

In ideja z dimnika je, da če sem je tu, z ali brez Annenberg vedoč, pladenj od soseda s številko 9 na njem. Torej, samo int. In hočem, da potisne na podatkih struktura, ki je trenutno prazna. Razmislite o tem na dnu dimnika. Jaz bi potisnite to številko 9 na kup, in zdaj je tam. 

Ampak zanimiva stvar dimnika je, da če bi zdaj rad potiskanje nekatere druge vrednosti, kot so 17 in porinem to na kupu, bom naredil samo intuitivno stvar, grem da bi ga tam, kjer smo ljudje bi se nagiba k temu, da dajo na vrhu. Ampak kaj je zanimivo zdaj je, kako pridem ob 9h? Veš, jaz ne bi nekaj truda. 

Torej, kaj je zanimivo stack, ki so po svoji zasnovi, to je podatkovna struktura LIFO. Neumno način opisovanja zadnji noter, prvi ven. Torej, zadnja številka v V tem času je bilo 17. Torej, če želim, da pop nekaj off iz dimnika, je lahko le 17. Torej je obvezna red Operacije tukaj, kjer je zadnji element v mora biti prva izpadla. Zato kratica, LIFO. 

Torej, zakaj bi bilo to koristno? So njihovi konteksti, v kateri ste jo želijo podatkovno strukturo, kot je ta? No, to je gotovo koristno notranjost računalnika. Torej operacijski sistemi jasno uporabljajo to vrsta podatkovne strukture za kupe. Bomo videli tudi isto idejo ko gre za spletne strani. Torej ta teden in naslednji teden in naprej, in kot ste začeti izvajati spletu Strani v jeziku, ki se imenuje HTML, lahko dejansko uporabljajo podatkovne strukture, kot to, da ugotovi, če stran je pravilno oblikovano. Ker bomo videli vse spletne strani, sledite neke vrste hierarhijo, zamik da bo ob koncu dneva, se drevesna struktura pod pokrovom. Torej, več o tem v samo nekaj. 

Ampak za zdaj, kaj je predlagala za Trenutek, kako bi lahko Å¡el okoli predstavlja, kaj stack? Dovolite mi, da predlagam, da izvajajo sklad s kodo, kot je ta. Torej sklad bo imel notri Dve stvari, matrike, ki se imenuje pladnji, samo, da je v skladu z demo. In vsaka od postavk v tej matriki se bo tip int. In zmogljivosti, je verjetno, kaj? Ker Å¡e nikoli nisem napisal Celotna definicija tukaj. 

To je verjetno največji velikost matrike. In to je verjetno deklariran kot ostra določiti na vrhu datoteke, nekateri nekako konstantna kot je vsebovano v Zgolj kapitalizacija. Torej nekje zmogljivost je opredeljena kot največjo možno velikost. Medtem, znotraj strukture podatkov znan kot dimnik tam bo je celo samo znan preprosto kot velikosti. 

Torej, če bi bil jaz, da predstavlja ta sedaj slikovno, pa domnevam, da je to celoti črna skrinjica predstavlja moj kup. Znotraj tega je dve spremenljivki. Torej bom pripraviti Prva je velikost. In druga bom pripraviti kot niz. 

Ampak samo, da se stvari urejene, običajno bi rišem matriko kot to je pa res super če ustrezajo realnosti, ali ujemajo z duševno model. Naj namesto sestaviti niz navpično, kar je prav, še enkrat, umetnikova izročitev. Sploh ni pomembno, kakšna je je pod pokrovom. In bomo rekli, da je privzeto kapaciteta se bo tri. Torej bo to mesto 0, to bo mesto 1, to bo lokacija 2. 

Če sem podkupil s stres žogo, bi nekdo rad prišel gor in teče vkrcati tukaj za trenutek? OK, prvič videl roko. Pridi gor. Vse je v redu. Torej menim, da je Steven. Pridi gor. Vse je v redu. 

Recimo, zdaj smo nazaj na začetno država na svetu, kjer sem Pravkar prijavljeni kup, in to je bo zmogljivost tri. Toda velikost še ni bila ugotovljena. Še ni bila določena pladnji. Torej nekaj vprašanj prvi. In naj ti dam mikrofon, tako da lahko sodelujejo bolj dejavno v tem. 

Torej, kaj je v velikosti v tem trenutku V času, če je vse, kar sem naredil, je prijavljeni kup z ena vrstica kode? 

STEVEN: Ne veliko. 

DAVID Malan: OK, ni veliko. Ali vemo, kaj je v velikosti, Ne vemo, kaj je notri te matrike tukaj? 

STEVEN: Samo naključno kodo, kajne? Samo - 

DAVID Malan: Ja, bom je koda poklicati, ampak naključno - 

STEVEN: Stvari. 

DAVID Malan: Stvari, kot naključno 

STEVEN: Biti. 

DAVID Malan: Biti, kajne? Torej smeti vrednosti, kajne? Torej permutacije 0 in 1 je. Ostanki prejšnjih običajih to pomnilnika. In ne bomo zares vedeli, kaj se vrednosti so, tako da smo ponavadi narisati kot vprašaji. 

Torej prva stvar, ki smo menda dogaja, da želijo narediti tukaj - in dovolite mi, da to področje v notranjosti od tod ime - pladnji. Kaj bomo predvidoma inicializacijo velikosti, da če želimo začnete uporabljati to kup? 

STEVEN: Nik je pod 3. 

DAVID Malan: Torej, v redu. Da bo jasno, se razglasi zmogljivost drugje kot tri. In to je tisto, kar sem uporabljal tudi dodeliti niz. Velikost se dogaja, da se nanašajo na koliko Pladnji so trenutno na kupu. 

STEVEN: Zero. 

DAVID Malan: Torej bi bilo nič. Tako da gredo naprej in z vsakim prstom, narisati nič v velikosti. Vse je v redu. Torej, zdaj, kaj je notri tega tukaj, ne vemo. To so res samo smeti vrednosti. Torej bi lahko potegnemo vprałaje, vendar Pustimo svet čisto za zdaj saj ni važno kaj je tam. Mi ne potrebujemo za inicializacijo niz z ničemer, kajti če vemo, da velikost svežnju nič, dobro smo se ne sme gledaš kaj v To polje je na vsak način ta trenutek. 

Torej sedaj Predvidevam, da bom pritisnil številka 9 na kupu. Kako bi morali posodobiti podatkovno strukturo notranjost te črne škatle? Katere vrednote je treba spremeniti? 

STEVEN: V - velikost? 

DAVID Malan: OK. Velikost morala postati kaj? 

STEVEN: Velikost bi bila ena. 

DAVID Malan: OK. Tako da bi postali ena velikost. Torej, lahko to storite v nekaj načinov. Naj ti dam, zdaj si Prst je radirka. Vse je v redu. Potem je zdaj vaš prst je čopič. Vse je v redu. In sedaj, kaj se mora spremeniti, Očitno je, da strukture podatkov? 

STEVEN: Gremo od spodaj do 9. 

DAVID Malan: 9. V redu, dobro. Torej še vedno ni važno, kaj je na lokaciji enega ali dva, ker so Smetarska vrednosti, vendar ne smemo ukvarjati si tam, ker velikost je nam povedali, da je samo prvi element je dejansko legitimno. Torej, zdaj bom pritisnil 17 na seznamu. Kaj se zgodi s to sliko? 

STEVEN: Torej, velikost pa je Å¡la na dva. 

DAVID Malan: OK. Ste radirka - Ups. Ste radirko. 

STEVEN: radirka. 

DAVID Malan: Ti si krtačo. 

STEVEN: Čopič. 

DAVID Malan: OK. In kaj Å¡e? 

STEVEN: In potem - 

DAVID Malan: Zavzeli smo se 17. 

STEVEN: Držimo 17 na vrhu, tako da - 

DAVID Malan: V redu, dobro. 

STEVEN: - ga spustite navzdol. 

DAVID Malan V redu. To je vse enostavno. Ne bom vam pomagala ta čas. Push 22. 

STEVEN: Končano. Postati radirko. Jaz sem postal krtačo. In potem sem dajanje 22. 

DAVID Malan: 22. Odlično. Torej, še enkrat. Zdaj sem bom za potiskanje na kupu 26. 

STEVEN: Ooh. Oh, bog. Res si me preseneti. 

DAVID Malan: Nisi videli prihajati? 

STEVEN: Nisem videl tega prihaja. Bi lahko ponovno začetna zmogljivost? 

DAVID Malan: To je dobro vprašanje. Torej smo nekako naslikal sebe v kotu tukaj. Res ni dober ven Stevenom ker smo dodeljen ta niz statično, tako rekoč, v notranjosti podatkovne strukture. In smo v bistvu težko kodirane , da je velikost tri. Torej, ne moremo zares prerazporediti. 

Lahko bi, če bi šli nazaj, smo na novo pladnji, da je kazalec, ki smo nato malloc za ročno spomin. Ker če imamo spomin iz kup prek funkcije malloc smo bi ga rešil. Toda preden je osvoboditev, smo lahko prerazporediti večji kos pomnilnika, posodabljanje kazalca, in tako naprej. Toda za zdaj je to res najboljše, kar lahko naredimo. Push in pop sta verjetno bo da so za signaliziranje nekatere napake. 

Tako, na primer, naša izvedba za lahko potisni vrne bool ki prej vrnil res, res, res. Ampak četrti čas, da se dogaja, da imajo vrne false, npr. Vse je v redu. Zelo dobro opravljeno. Čestitam. Ste zaslužili svoj stres žogo danes. 

[APLAVZ] 

STEVEN: Hvala. 

DAVID Malan: Hvala. OK, tako da se zdi, da ni veliko za korak naprej, a ne? Opisali smo to strukturo podatkov. To je bil prepričljiv, kajne? Operacijski sistemi všeč. Očitno lahko spletni uporabi tega in druge aplikacije še vedno. Ampak kaj neumnega omejitev, ki smo nazaj na neke v tednu dvema skrajnostma kjer smo določena zaporedja velikosti. 

Torej so dejansko nekaj načini, kako bi lahko rešili to. Mi lahko dinamično dodeli niz, ni jih težko kodiranje, kot sem narediti tukaj, ampak ponovno izjavlja to, samo, da bo jasno, kot je kaj takega. Int * pladnji, ne odločajo o zmogljivosti še ni. Toda, ko sem razglasila Sveženj drugje v mojem kodo, sem lahko potem pokličete malloc, dobite naslov na kos spomin, in sem lahko dodeli da je naslov na pladnjih. 

In potem, ker je samo kos spomin, sem lahko še naprej uporabljajo kvadrat Nosilec zapis na običajen način. Ker še enkrat, tam je nekako to funkcionalni ekvivalent nizi in kose pomnilnika, ki prihajajo nazaj od funkcije malloc. Mi lahko privoščite eno kot drugo uporabo kazalca aritmetično ali oglati oklepaj zapis. Tako da je en pristop. 

Ampak kako pa bi lahko izvajanje tega enako strukturo podatkov, morda? Kajne? Počutim se, kot smo pravkar rešili to problem kot pred tednom dni. Kaj je rešitev za ta problem da Steven naletela? Torej povezani seznam, prav. 

Če problem je, da smo slikarstva sami v kotu z dodelitvijo vnaprej premalo pomnilnika, ki smo Nato so se nekako ukvarjajo z, no, zakaj ne samo, da bi se izognili izda skupaj? Zakaj ne razglasi pladnji za kazalec na vozlišče, ergo povezan seznam, in nato preprosto dodelijo nove vozlišč vsakič Steven potrebno, da se prilega število v podatkovno strukturo. 

Tako da bi slika morala spremeniti. To ne bo tako čista in kot enostavno, kot le niz treh ints. Zdaj se dogaja, da se kazalec struct, in da struct bo imajo int in naslednjo kazalec. To bo vodilo preko tega kazalca drugi taki struct, da še ena taka struct. Torej slika bi dejansko dobili malo Messier. In mi bi bili puščice vezavo vse skupaj. 

Ampak to je v redu, kajne, saj smo videli, kako to storiti. In ko boste dobili udobno izvedbenih nekaj podobnega povezano Seznam, ki jih boste morali narediti, če odločijo za izvajanje razpršene tabele s Veriženje za p-set 6, lahko jo uporabite kot gradnik, ali sestavina ali nič rekoč Postopek, nekaj, kar si dal, vas ustvarili svoj kos sestavljanke da lahko potem znova. Torej kompromisi, vendar potencialne rešitve da smo dejansko videli. 

Tako pogosto, vidiš to vsak leto ali dve, ko Apple za javnost nekaj novega, in vsi nori ljudje line up zunaj Apple shranite za nakup njihovega obrobnega nadgraditi na strojni opremi. Jaz pravim, da je v redu, ker Jaz sem eden tistih ljudi. Torej, kakšne podatkovne strukture lahko predstavlja to realnost? 

No, pa je čakalna vrsta, linija pokličite. Torej bi Britanci poimenovali po navadi Čakalna vrsta nekako, tako da je lepo ime. In dve operaciji, da čakalne vrste podpirali bomo klic enqueue Delovanje in dequeue delovanje, ki so podobne duh push in pop. To je nekako drugačna Konvencija, kaj kličeš ti. Ampak enqueue kaj pomeni, da dodate ali vstaviti za podatkovno strukturo. Da dequeue pomeni, da ga odstranite. Toda medtem ko je bil kup podatkov LIFO struktura, čakalna vrsta je prvi, Prvi od strukture podatkov. 

Če ste prva oseba, ki je v skladu, da bo prva oseba, da bi dobili iz linije in kupite novo napravo. Predstavljajte si, kako razburjen bi ti ljudje če Apple namesto dimnika, za na primer, za izvajanje picking up vaše nove igrače. Torej čakalne vrste smisla, vsekakor, in lahko razmišljamo o vseh mogočih aplikacije, verjetno, za čakalne vrste, še posebej, če hočeš pravičnost. Torej, kako bi lahko izvajanje teh kot podatkovne strukture? 

No, jaz predlagam, da bi lahko morajo to storiti v to smer. Torej bom zdaj številk. Tako da bomo naj bo enostavno in ne nujno govori v smislu pladnje. Samo številke, ki ljudje gotten. Kapaciteta se bo, še enkrat, določi Skupno število oseb, ki so lahko v ta vrstica, kot tri ali koli druga vrednost. 

Ampak jaz predlagam, da moram slediti ne le velikosti Čakalna vrsta, koliko so stvari v njem. Torej velikost je sedanja velikost, zmogljivost je največja velikost. Samo enkrat, nomenklatura po dogovoru. Zakaj potrebujemo dodatno int znotraj o vrsti slediti, kdo je v sprednji strani linije? Zakaj moram to narediti v tem primeru? 

No, kako je to slika se bo spremenilo? Verjetno lahko ponovno najbolj te slike. Dovolite mi, da gredo naprej in izbrisati, kaj je tukaj. Mi bomo to lahko nekoliko drugačno ime tu gor. Znebimo od 17, znebimo od 9, dajmo se znebite 3. In dodajmo še eno stvar. Predlagam, da moram slediti sprednja stran, ki je prav bo int tudi. In bomo keep it simple. Ne povezani seznam za zdaj. 

Bomo priznati, da bomo Naleteli proti tej meji. Ampak, kaj hočem videti zgodilo tokrat? Tako, da sem šel naprej in prvi oseba, ki prihaja v liniji, in to je številka 9. Imamo stres kroglice. Lahko kradem, recimo, dveh ali treh ljudi? Ena, dva, tri? Pridi gor. Desno od spredaj, ker bomo, da je to eden hitro. 

Vsak od vas se sedaj dogaja, da se ventilator fant v vrsti na Apple. Ne boste prejemali Apple strojne opreme Na koncu tega, čeprav. Vse je v redu. Torej ste številko 9, si Številka 17, številka 22. To so poljubne številke, kot študent ID-ji ali drugih malenkosti. In čez nekaj trenutkov, začnimo za začetek dodajanja stvari. In bom teči krovu tukaj ta čas. 

Torej, v tem primeru, sem inicializiran spredaj, da - Pravzaprav sploh ne zanima, kaj spredaj je, saj znaša nič. Torej je to lahko tudi samo biti vprašaj. To so vsi vprašljiva. Torej, zdaj bomo začeli dejansko videli nekaj ljudje podloga v trgovini. 

Torej, če številka 9, ti si prvi tam ob 5:00, pojdi naprej in line up, ali večer prej. OK. Torej, zdaj 9 je tukaj. Torej 9 na sprednjem seznama. Tako da sem šel naprej in posodobiti Velikost tekočih podatkov strukture, da ne bo več 0, ampak na 1. Bom dal na 9. sprednja stran. Dovolite mi, da gredo naprej in preklopite zaslon Tako lahko vidimo, mimo nas tukaj. 

In zdaj kaj hočem dati na sprednji strani? Grem slediti, da sprednji vrsti zdaj je na mestu 0.. Ker, kaj se bo zgodilo naslednje? No, recimo, zdaj sem enqueue 17 kot tudi. Torej hop v skladu tam. In spet, nekako vratih Trgovina je, da bo tu. Torej, zdaj sem dodal 17. In čeprav so ti fantje blokiranje zaslon, da je v redu, saj ga lahko vidite tukaj gor. Žal mi je. 

PUBLIKA: Mi lahko premikate - 

DAVID Malan: Ne, to je v redu. To je velik tam gor. Torej 17 je sedaj znotraj vrste. Moram posodobiti, ki Polja sedaj, čeprav? OK, vsekakor velikost. Kaj pa spredaj? OK, ne. Spredaj se ne sme spremeniti, ker za razliko od dimnika, smo želijo ohraniti pravičnost. Torej, če 9 prišel prvi, želimo 9 da je treba najprej iz vrste in v trgovini. 

Dejstvo je, da vidimo, da je. Preden smo vstaviti 22, dajmo iti naprej in dequeue 9. Kaj ti je že ime? 

PUBLIKA: Jake. 

DAVID Malan: Jake se dogaja se dequeued zdaj. Tako da boste dobili, da hodi v trgovino. In se pretvarjamo, da trgovina je tam. Torej, kaj zdaj potrebuje - dit-dit-dit! Kaj se mora zgoditi zdaj? Odločitev oblikovanje. Torej ni slab nagon, ampak - Kako ti je ime? 

PUBLIKA: David. 

DAVID Malan: David. Torej, kaj je David storil? Poskušal je nekako popraviti podatke struktura in premik od svojega mesta v Jakov nekdanji lokaciji. In to je v redu, če smo pripravljeni sprejeti dejstvo, da so podrobno izvajanje. Ampak najprej, kaj je posodobiti podatke strukturo, preden to storimo. Ker nisem všeč zamisel, da vse ljudje premikajo v tej vrstici. 

To ni nič takega, če je David to počne z en korak, vendar še enkrat, mislim nazaj ko smo imeli osem prostovoljcev na oder in smo naredili tako kot vstavljanje razvrščanje, kjer smo morali začeti gibljejo vse okoli. Da imam drago, kajne? To me klečeplastvo o velikem O n, big O n znova na kvadrat. To ni občutek, kot idealen rezultat. 

Zato naj samo posodobiti to. Torej velikost čakalne vrste ni več 2. To je zdaj samo 1. Ampak jaz lahko sedaj posodobite nekaj Nisem posodobiti prej, sprednja stran. Jaz lahko samo povem, je, da je lokacija 1? Torej, zdaj imamo smeti vrednosti tukaj Smetarsko vrednost tukaj, in David v Sredi te smeti. Ampak struktura podatkov je nedotaknjena. 

In v resnici sploh ne potrebujete spremenite Jaku nekdanjo številko 9, ker koga briga. Nimam dovolj informacij, je zdaj v velikost, da vem, da je ena oseba v To čakalne vrste. In vem, da je ta oseba je na lokaciji 1, ne 0. Jaz se ne upošteva. Torej 1, kot tudi. Torej podatkovna struktura je še vedno v redu. 

No, kaj se zgodi potem? Debatni enqueue - Kako ti je ime? 

PUBLIKA: Callen. 

DAVID Malan: Callen. Oglejmo enqueue je Callen, in 22 je zdaj na vrsti. Torej, zdaj, kaj je tu spremenilo? Spredaj je ne bo spremeniti, seveda. Velikost se bo spremenilo, da je 2. znova. In 22 konča tukaj, 9 je še vedno prisotna, ampak to je dejansko Smetarsko vrednost zdaj. To je samo ostanek Jake preteklosti. 

Torej, zdaj, kaj se zgodi, če Jaz dequeue Davida? Še zadnja operacija, dequeue David. Mi lahko premika, ampak jaz predlagam lets ' storite tako malo dela, kot je mogoče. Zdaj moja struktura podatkov gre nazaj v velikosti 2-1. Ampak sprednji vrsti zdaj postane 2. Ni mi treba spremeniti te številke samo še, ker oni le smeti vrednosti. 

Toda zdaj, kaj se zgodi? Recimo, da sem enqueue sam, 26? Počutim se, kot da spadam sem. Torej sem se enqueued. Tako sem nekako spadam sem. In čeprav ti niso čisto cenim to vidno na odru, ker imamo dovolj prostora, da bi moral ne bi stal tukaj, zakaj? 

PUBLIKA: Ti si izven igrišča. 

DAVID Malan: Right. Sem izven igrišča. Sem indeksira preko mejá te matrike. Res bi morala biti v eni od tri možne lokacije. Zdaj, ko je najbolj naravna iti? Predlagam, da vzvodom teden en trik. Operater mod, odstotek. Ker sem tehnično znašal mesto 3, ampak jaz 3 mod zmogljivosti, tako 3, znak za odstotek, 3 - kapaciteta je 3. Kaj je to? Kaj je ostalo pri si delimo 3 za 3? 0. 

Tako, da me postavi so bili Jake je bil, kar je pravzaprav dobro. Torej, zdaj je izvajanje to stvar, ki se dogaja, da biti malo glavobol. To je res samo ena vrstica glavobola, kode. Ampak zdaj vsaj obstaja smeti Vrednost tu, vendar pa je dva zakonite ints tukaj. In trdim, da zdaj smo storili kaj moramo tako dolgo, dokler ne smo spremenili, kaj Jake vrednost naj bi bila 26. 

Zdaj imamo dovolj podatkov, še da se ohrani celovitost te strukture podatkov. Še vedno smo nekako od sreče, ko smo želite vstaviti štiri ali več skupaj Elementi, ampak lahko bi vsaj precej učinkovita uporaba ta konstanta čas, v resnici. Nimam skrbeti za prestavljanje vsakdo, kot naklona Davidove bil. 

Vsa vprašanja o skladih, ali je ta vrsta? 

PUBLIKA: Je razlog, zakaj morate velikosti, tako da boste vedeli, kjer je imela oseba? 

DAVID Malan: Točno tako. Moram vedeti, velikost matrike ker moram, kako natančno vedeti mnogi od teh vrednosti so legitimne, in da najdem, kam Naslednja oseba. Točno tako. Velikost je - pravzaprav nismo posodobili to še ni. Sam sem dodal na 26 let. Velikost je sedaj, ne 1, vendar 2. Torej, zdaj je to res mi pomaga najti glava seznama, ki ni 0, ne 1, vendar pa je 2. Sprednja stran je dejansko število 22. Ker je prišel v prvo, zato je treba dovoljeno v trgovini pred menoj, čeprav vizualno stojim bližje trgovini. 

Vse v redu? Aplavz za te fante in jih bom pustil ven. 

[APLAVZ] 

DAVID Malan: Jaz bi pustil boste obdržali pladenj. Smo lahko videli, kaj se zgodi, če hočeš, pa morda ne. Vse je v redu. Torej, kaj zdaj pa nam preostane? No, naj predlagajo, da obstaja Nekaj ​​drugih podatkovne strukture smo lahko začnete tako, da naše orodje kit, ki bo dejansko zelo, zelo pomembno, saj je smo se potopite v spletnem stvari. Ki je spet, ima nekakšno povezavo drevesom v obliki nekaj, kar se imenuje DOM, dokument objektni model. Ampak bomo videli več da je pred dolgo. 

Dovolite mi, da predlagam definitionally, da smo pokličite drevo zdaj kaj znate, kot bolj družinsko drevo, kjer si nekaj prednika na Korenine drevesa. Patriarhalna ali Matriarchs na samem vrhu drevesa. Brez njihovega zakonca, v tem primeru. Vendar imamo zdaj, kaj bomo klic otroci, ki so vozlišča, ki visi off levi otroka ali desno otroka, puščice, kot je prikazano tukaj. 

Z drugimi besedami, v podatkovno strukturo drevo v računalniku, drevo ima ničlo ali več vozlišč. Če ima vsaj eno vozlišča ki se imenuje koren. To so stvari, ki vizualno potegnemo na vrhu. In to vozlišče, kot katera koli druga vozlišča, lahko imeli nič, ena ali dve ali tri, ali glede na število otrok Struktura podatkov podpira. V tem primeru je koren, shranjevanje vrednost ena, ima dva otroka, 2 in 3, Tako smo na splošno imenujemo 2 levo otrok in 3 pravico otrok. 

Potem, ko smo dobili do 5, 6, in 7, 6 bi lahko imenovali srednji otrok. Če imate štiri otroke, postane zmedeno. Zato smo prenehali uporabljati to vrsto za bližnjico verbalno. Ampak to je res samo družinsko drevo. In listi tukaj so vozlišča, ki sami nimajo otrok. So visi off dno drevesa. 

Torej, kako bi lahko izvajala drevo, ki Ima le dva otroka, maksimalno? Mi bomo to binarno drevo klic. Bi spet pomeni dve, v tem tako, kot je z binarno. Tako ima lahko nič, ena, ali dva otroka najvišja. 

Bom predlagam, da izvajajo vozlišče Za te strukture z int n, in potem dva kazalci, ena se imenuje levo, ena imenovana pravica. Ampak to so samo lepo samovoljne konvencij. In kaj je lepo zdaj, še posebej, če vrsta boril s konceptualno rekurzija, ali misli, da ni bilo res rešitev za vse, še posebej, če bi lahko zmanjka pomnilnika. Zdaj, ko govorimo o podatkih strukture in algoritmi, ki omogočajo nam prečkanje in manipulirati z njimi, Izkazalo se je, da je rekurzija vrne v veliko bolj prepričljiv če ne lep način. 

Torej, to predlagam, je izvajanje za funkcijo iskanje. Glede na to, dva vhoda - tako da mislim, da je to črno škatlo. Glede na to, dva vhoda, n, int, in kazalec na drevo, kazalec vozlišče, ali res koren drevesa, sem Trditev, da je to funkcija vrne resnična ali neresnična, da je vrednost n je znotraj tega drevesa. 

Kaj je v te črne skrinjice? No, štiri podružnice. Prvi pravkar preverja. Če drevo je nična, samo vrne false. Če ni vozel, ni n ni več, samo vrne false. Če temu, n, vrednost iščete , da je manj kot drevo puščice n, in samo, da bo jasno, kaj pomeni, ko Pišem drevo in nato puščico zapis, n? Točno tako. To pomeni, da ciljne datoteke Kazalec se imenuje drevo. Pojdi tja, nato pa dobil v notranjosti, ki vozlišče in dobila polje z imenom n. In nato primerjati dejansko n, da je prešla v Search proti njej. 

Torej, če je n manjša od vrednosti n V drevesu samega vozlišča, dobro, Kaj to pomeni? To ne pomeni nič, na prvi pogled. Kajne? Tako kot če imate niz Vrednosti, boste morda želeli uporabiti binarno iskanje kot obliko razkoraka in vladaj. Ampak kaj predpostavka pa moramo narediti za binarno iskanje za delo na vseh v imeniku in prejšnji primeri? 

Kako se urejeno. Torej, kaj je natančnejše opredelitve drevesa Tu ni prav drevo, ki lahko ima poljubno število otrok. Ne samo binarno drevo, ki lahko ima 0, 1, 2 ali maksimalno. Ampak kot dvojiškega drevesa, ali BST, ki je samo fancy način rekel binarno drevo, tako da vsako vozlišče je levo otrok, če je prisoten, je manj kot vozlišče. Vsako vozlišče in pravica otrok, če je prisoten, je večja kot vozlišče sama. 

Torej, z drugimi besedami, če ste bili, da pripravijo drevo ven, vse številke so skrbno uravnotežene, tako da, če imate 55 kot root, 33 more iti na njegovi levi, ker je manj kot 55 let. 77 se lahko obrnejo na svoje pravice, ker to je več kot 55 let. Toda zdaj opazil, enako opredelitev, to je rekurzivna definicija verbalno, zaprositi za 33. 33 na levi Otrok mora biti manjša od njega, in 33 pravica otrok, 44, mora biti večja od njega. 

Torej je to binarno iskalno drevo, in I predlaga uporabo malo rekurzija, bomo lahko sedaj najdete n. Torej, če je n manj kot vrednost n, ki je trenutno vozlišče, jaz grem naprej in punt, tako rekoč, in samo vrne kar je odgovor na iskanje n o levo otrok drevesa. Spet opazili, ta funkcija samo pričakuje, da bo vozlišče Zvezda, kazalec na vozlišče. Torej, zagotovo sem lahko samo naredi drevo puščica levo, ki bo vodila mi drugo vozlišče. Ampak kaj je to vozlišče? 

No, glede na to izjavo, levo je samo kazalec, tako da le pomeni, da sem prehod na funkcijo iskanja drugačen kazalec, in sicer tista, ki predstavlja Moja leva otroka drevo. Torej v tem primeru kazalec 33, če to je naš vložek vzorec Medtem, če n je večja od vrednosti n na trenutno vozlišče v drevesu, potem pa sem dogaja, da gredo naprej in punt v drugo Smer in samo reči, jaz ne ve, če ta vrednost je n v drevesu vem pa, če je to, to je moja dol Pravica podružnica, tako rekoč. Torej, naj me pokliče rekurzivno iskanje, spet spustimo n, vendar gre v kazalec na moji desni otroka. 

Z drugimi besedami, če sem trenutno na 55 in iščem 99, vem, da je 99 je več kot 55 let, tako kot sem strgal tedni imenika nazaj in mi šel desno, podobno smo šli tukaj. In ne vem, če je na moji desni otrok, in to ne, 77 je tam, ampak Vem, da je v tej smeri. Zato sem poklical iskanje na moji desni otroka 77, in pustite iskanje razbrati iz pa če je 99 v tem samovoljno Primer je dejansko tam. 

Else, kaj je končni primeru? Če drevo je nična, je en primer. Če je n manj kot tok vozlišča vrednost je še en primer. Če je n večji od toka vrednost vozlišča je tretji primer. Kaj je četrti in zadnji primer? Mislim, da smo iz primerov, kajne? Zato mora biti, da je n v trenutno vozlišče, da sem naprej. 

Torej, če sem iskal 55 let na tej točki v zgodbi, ki veje Drevo bi spet res. Torej, kaj je zanimivo, je, da smo pravzaprav, za razliko od preteklih tednih smo nekako za dve bazne primerov. In ti ne bi bilo treba Vse bo na vrhu. Vrhu je osnovna ker če Drevo je nična, ni nič narediti. Pravkar vrnil težko kodirane vrednost false. 

Spodnji veja je nekako privzeto, pri čemer se, če smo preveriti null, smo preverili, če je treba levo, vendar to ne bi smelo biti, ki smo jih preveri, če bi bilo prav, vendar ne sme biti jasno, da mora biti tam, kjer smo. To je osnovni primer. Torej je dve rekurzivni primeri je stisnjena v sredini. Vendar bi jaz napisal to v poljubnem vrstnem redu. Mislil sem, da je nekako zdelo naravno najprej preverite morebitne napake, nato pa preverite v levo, nato pa preverite desno, nato Predvidevam, da ste na vozlišču ste dejansko iščejo. 

Torej, zakaj bi bilo to koristno? Tako se izkaže - in mi skočil na teaser tu se je v spletu. Bomo začeli uporabljati ne programski jezik na prvi, ampak označevalni jezik. Pa tista, ki je označevalni jezik pisane v duhu programiranja jezika, vendar pa ne dam sposobnost, da sami logično izraziti. To samo vam daje možnost, da izraziti sebe strukturno. 

Kam želite dati nekaj na strani, spletna stran? Kakšno barvo želite, da bi ga? Kaj velikost pisave hočeš narediti to? Kaj besede, kajne dejansko želim na spletni strani? Tako da je označevalni jezik. Ampak potem bomo zelo hitro uvesti JavaScript, ki je polnopravni programskega jezika. Zelo podobno skladenjsko po videzu do C, vendar pa boste morali nekaj lepo, močnejši, bolj uporabniku prijazne funkcije. 

In ena od frustracij na to točka v semestru je, da bomo Kmalu izvajati Speller v veliko manj vrstic kode, ki uporabljajo druge jezike kot C sama po sebi dovoljuje, vendar razlog je bomo kmalu razumeli. To bo prva tovrstna spletna stran. To bo popolnoma underwhelming, Prva naredimo. To bo preprosto reči, zdravo svet. Ampak, če še nikoli niste videli prej, to je HTML HyperText Markup Language. 

Če greš v neke menija v Najbolj koli brskalnik, na kateri koli spletni strani na internet, lahko vidite HTML da nekateri ljudje pisal ustvariti to spletno stran. In verjetno ne izgleda kot kratek ali kot lepo, kot je ta. Vendar pa bo sledila vzorcu teh odprte konzole in poševnice in črke in potencialno številke. 

Mislila sem, da vam teaser o tem, kaj boste mogli storiti po zaužitju CS50. Naj grem na cs.harvard.edu / rob, naše lastne Rob Bowden je domača stran. On to je za nas. Tako da boste kmalu lahko storim. In tudi, kaj ste slišali Zjutraj - kaj ste slišali danes zjutraj - 

[HAMSTER DANCE MUSIC] 

- Boš lahko, da je to. To nas čaka v sredo. Vam bomo videli potem. 

[HAMSTER DANCE MUSIC] DAVID Malan: Na naslednjem CS50 -