[Muzikos grojimo] 

ANDI Peng: Sveiki skirsnio 6 savaitės. Mes nukrypo nuo mūsų standartas skyrius laikas antradienį popietę tai puikus sekmadienio rytą. Dėkojame visiems, kad prisijungė mane šiandien, bet rimtai, plojimų. 

Tai gana didelis pastangų. Aš beveik nebuvo net padaryti jį iki laiko, bet tai buvo Gerai. Taigi aš žinau, kad jūs visi ką tik padarė jį viktorinoje. Pirmiausia, kviečiame atvirkštinė pusė, kad. 

Antra, mes kalbame apie tai. Mes kalbame apie viktorinoje. Mes kalbame apie tai, kaip darote klasėje. Jums bus gerai. Turiu savo viktorinos tu ne iš čia pabaigoje, Taigi, jei jūs vaikinai nori imtis a look į jį, visiškai gerai. 

Taigi greitai, kol mes pradėsime, The darbotvarkė šiandien yra taip. Kaip matote, mes iš esmės greitas šaudymo per visa krūva duomenų struktūrų tikrai, tikrai, tikrai greitai. Taigi, kaip, pavyzdžiui, ji negali būti Super interaktyvus šiandien. Tai bus tik man rūšies šaukė dalykų, kad jūs, ir jei aš supainioti jus, jei aš ruošiuosi per greitai, let me know. Jie tiesiog įvairius duomenis struktūros, ir kaip dalis Jūsų pset Dėl šios Artėjantis savaitę, jums būti paprašyta įgyvendinti vieną iš jų, gal du them-- du iš jų Jūsų pset. Gerai, kad aš tik ketina pradėti su kai kuriais pranešimų. Mes eiti per kaminus ir eilėse daugiau gylis, nei tai, ką mes padarėme prieš viktorina. Mes eiti per susijęs vėl, vėl sąrašą, išsamiau, nei ką mes turėjome prieš viktorina. Ir tada mes kalbame apie maišos stalai, medžiai ir nutraukė, kurie visi gana reikalinga jūsų pset. Ir tada mes eiti per kai naudingų patarimų, pset5. 

Gerai, kad viktorina 0. Vidutinis buvo 58%. Tai buvo labai mažas, todėl jūs vaikinai visi padarė labai, labai gerai laikantis su tuo. 

Gana daug, nykščio taisykle yra, jei esate per standartinio nuokrypio vidurkio juolab mes mažiau Nežiūriu skyriuje, jūs visiškai gerai. Jūs esate kelyje. Gyvenimas yra geras. 

Aš žinau, tai baisu pagalvoti, kad Gavau kaip 40% šį testą. Aš ruošiuosi tai nepavyks klasę. Aš jums pažadu, jūs ne vyksta žlugti klasę. Jūs esate visiškai gerai. 

Tiems iš jūsų, kurie gavo daugiau vidutinis, įspūdingas, įspūdingas, kaip rimtai gerai padaryta. Turiu juos su manimi. Jauskitės laisvai ateiti juos gauti ne iš dalies pabaigoje. Leiskite man žinoti, jei turite kokių nors klausimai, klausimai su jais. Jei mes pridėti savo rezultatą negerai, praneškite mums. 

Gerai, kad pset5, tai yra tikrai keistai savaitę Yale ta prasme kad mūsų pset yra dėl Trečiadienį vidurdienį, įskaitant vėlai dieną, todėl tai tikrai Teoriškai dėl antradienį vidurdienį. Turbūt niekas baigtas ne antradienį vidurdienį. Štai visiškai gerai. Mes ketiname turėti darbo valandas vakarą, taip pat pirmadienį vakare. Ir visi sekcijų šią savaitę faktiškai virto seminaruose, todėl nedvejodami pop bet skyrių, kurį norite, ir jie bus pobūdžio mini pset seminarai pagalba, kad. Taigi, kaip toks, tai yra vienintelis skyrių kur mes mokyti medžiagą. Visi kiti skyriai bus dėmesio tik pagalba už pset. Taip? 

Auditorija: Kur yra darbo valandos? 

ANDI Peng: Darbo valandos tonight-- oh, geras klausimas. Manau, biuro val vakarą yra žalsvai arba Commons. Jei patikrinti internete CS50 ir jūs einate į darbo valandomis, turėtų būti grafikas, jums pasakys, kur visi jie yra. 

Žinau vieną vakarą arba rytoj kryklė, ir manau, kad mes galime turėti commons už kitą naktį. Aš nesu tikras. Geras klausimas. Patikrinkite ant CS50. 

Cool, visus klausimus dėl tvarkaraštis pan tris dienas po to? Aš jums pažadu, vaikinai, kaip Dovydo sakė, tai yra ant kalvos viršūnės. Jūs vaikinai yra beveik ten. Tik trys dienos. Plačiau Gauk ten, ir tada mes visi ateis žemyn. Mes turime gražią CS-pertraukos. Sveiki sugrįžę. Mes pasinerti į interneto programavimas ir vystymas, dalykų, kurie yra labai įdomus palyginti kai kurie iš kitų psets. Ir tai bus chill ir mes turime daug įdomus. Mes turime daugiau saldainių. Atsiprašome už saldainiai. Aš pamiršau saldainiai. Tai buvo grubus rytą. Taigi jūs vaikinai yra beveik ten, ir aš tikrai didžiuojuosi jumis vaikinai. 

Gerai, kad kaminai. Kas patiko klausimą apie Jack ir jo drabužius viktorinoje? Niekas? Gerai, kad viskas gerai. 

Taigi, iš esmės, kaip jūs galite nuotrauka Jack šis vaikinas čia myli imtis drabužius iš kamino viršaus, ir jis pateikia jį atgal į po jis kamino daroma. Taigi, tokiu būdu, kad jis niekada Atrodo, kad būti gauti į apačioje sukrauti savo drabužių. Taigi tai rūšies aprašo pagrindinis duomenų struktūra kaip kamino yra įgyvendinamas. 

Iš esmės, galvoti apie sukrauti kaip bet objektų kamino kur įdėti daiktus į viršų, ir tada jūs pop juos iš viršaus. Taigi LIFO yra akronimas mums patinka į use-- Paskutinis in, first out. Ir taip tęsis ir į viršų kamino yra pirmoji, kuri išeina. Ir taip du terminai mes norėtume susieti su tuo vadinami stūmimo ir POP. Kai jūs stumti kažką prikabinama prie kamino, ir jūs pop jį atgal į viršų. 

Ir todėl aš manau, tai yra rūšies abstrakti sąvoka tiems iš jūsų, kurie nori pamatyti kaip Tikrasis įgyvendinant šią realiame pasaulyje. Kaip daugelis iš jūsų parašyta esė gal kaip valandą prieš tai buvo dėl, ir jūs netyčia ištrynėte didžiulis riekė tai, kaip netyčia? Ir kas tada kontrolė padaryti mes naudojame įdėti ją atgal? Valdymo-Z, Yeah? Valdymo-Z, todėl kartų suma kad kontrolės Z išgelbėjo mano gyvenimą, sutaupė mano asilas, kiekvieną kartą kad manimi įgyvendinama per kaminą. 

Iš esmės visa informacija tai savo "Word" dokumentą, ji pasireiškia stumiami ir popped ne valia. Ir taip iš esmės, kai jūs nieko trinti, pop jį atgal į viršų. Ir tada, jei jums reikia jį atgal, jūs stumti jį, o tai, ką Control-C nėra. Ir taip realiame pasaulyje funkcija kaip paprastas duomenų struktūros gali padėti su savo kasdieniame gyvenime. 

Taigi konstrukto yra taip, kad mes iš tikrųjų sukurti kamino. Mes tipas apibrėžti konstrukto, tada mes vadiname tai kamino apačioje. Ir per kaminą, turime du parametrus kad mes galime iš esmės manipuliuoti, todėl mes turime char žvaigždučių stygos pajėgumus. 

Visi, kad ji tai daro yra sukurti masyvą , kad mes galime saugoti ką nori kurį mes galime nustatyti savo gebėjimus. Talpa yra tik max dydis Daiktai, kuriuos mes galime įdėti į šį masyvo. int dydis yra skaitiklis, kuris saugo kelio nuo to, kiek daiktų šiuo metu pluošte. Taigi, mes galime sekti, A, tiek kaip didelis faktinis kamino, ir, B, kaip daug, kad rietuvės mes užpildyta, nes mes nenorime perkrautas, ką mūsų pajėgumas yra. 

Taigi, pavyzdžiui, tai puikus Klausimas buvo jūsų viktorina. Iš esmės, kaip mes stumti ant rietuvės viršuje. Gana paprasta. Jei pažvelgti į tai, mes vaikščioti per tai. Jei [nesigirdi] size-- Atminkite, kad kai jūs norite naudotis bet parametras per struct, jūs darote, kad struct.parameter vardą. 

Šiuo atveju, s yra mūsų kamino pavadinimą. Mes norime patekti į dydį tai, kad mes padaryti s.size. Taigi, kaip ilgai, kaip dydis yra ne lygus talpos arba tol, kol kaip tai mažiau nei pajėgumų, arba būtų čia dirbti. 

Jūs norite prisijungti prie vidų Jūsų žetonų, todėl s.strings, ir jūs ketinate įdėti, kad naują numerį kad norite įterpti į ten. Leiskite tik pasakyti, mes norime įterpti int n ant kamino, mes galime padaryti s.strings, skliausteliuose, s.size lygus n. Kadangi dydis yra kur mes Šiuo metu yra pluošte jei mes ketiname stumti tai, mes tiesiog prieiti kur dydis yra, tuo Dabartinis pilnatvė kamino, ir mes stumti int n į jį. Ir tada mes norime įsitikinti, kad mes taip pat pokyčio dydį n, todėl mes galime sekti mes pridėjo papildomą dalyką į krūvą. Dabar mes turi didesnį dydį. Ar tai čia prasmės visi, kaip logiškai tai veikia? Tai buvo natūra greitai. Auditorija: Ar jūs einate per kad s.stringss.strings [s.size] dar kartą? ANDI Peng: Žinoma, tai kas daro s.size metu duoti mums? Auditorija: Tai dabartinis dydis. ANDI Peng: Būtent, todėl Dabartinė puslapis, kad mūsų dydis yra ne, ir taip nori įdėti naują sveikasis skaičius kad mes norime įterpti į s.size. Ar tai prasminga? Kadangi s.strings, visi, kad yra yra masyvo vardas. Visa tai yra tai naudodamiesi masyvas per mūsų struct, ir todėl, jei norime vieta n į šio indekso, mes galime tik jį pasiekti naudojant skliausteliuose s.size. Saunus. 

Visos teisės pop, aš Pseudocode jį už jus vaikinai, bet panašios koncepcijos. Ar tai prasminga? Jei dydis yra didesnis už nulį, tada jūs žinau, kad jūs norite imtis ko nors iš nes jei dydis yra ne didesnis nei nulis, tada jūs neturi nieko kamino. 

Taigi jūs tik norite vykdyti šis kodas, ji gali tik pop, jei yra kažkas, kad pop. Taigi, jei dydis yra didesnis nei 0, mes atėmus dydis. Mes Mažėja dydį ir tada grįžti kas yra viduje ji, nes Popping, mes norime prieigos kokia yra saugomi į kamino viršuje indekso. Viskas prasmės? Jei aš padariau jums vaikinai rašau tai iš, būtų vaikinai galės rašyti jį? Gerai, vaikinai gali pažaisti su juo. Nesijaudinkite, jei jūs neturite jį gauti. Neturime laiko kodas jis iš šiandien, nes mes gavo iš šių struktūrų daug eiti per, bet iš esmės Pseudocode, labai, labai panašus į stumti. Tiesiog atlikite palei logika. Įsitikinkite, kad esate susipažinimo visi Savybės jūsų struct teisingai. Taip? 

Auditorija: Ar šie skaidres ir Visa tai, ką būtų iki šiandien ish? ANDI Peng: Visada, yep. Aš ruošiuosi pabandyti įdėti tai iki kaip valandą po. Aš atsiųsime Dovydą, Davidas bandys įdėti jį kaip po šios valandos. 

Gerai, kad tada mes einame į tas kitas Lovely duomenų struktūra vadinama eilę. Kaip jus vaikinai galite pamatyti čia A eilėje, už tarp mūsų Didžiosios Britanijos, visa tai yra yra linija. Taigi, priešingai nei manote, kamino, eilėje yra būtent tai, ką logiškai manote, kad tai yra. Tai vyksta pagal FIFO taisyklių, kuris yra first in, first out. Jei esate pirmasis viena linija, esate pirmoji, kuri išeina iš linija. 

Taigi, ką mes norėtume tai vadiname yra dequeueing ir enqueueing. Jei mes norime pridėti kažką mūsų eilėje, mes į eilę. Jei norime dequeue, arba imtis kažkas toli, mes dequeue. 

Taigi pats jausmas, kad mes rūšies sukurti fiksuoto dydžio elementus, kad mes galima laikyti tam tikra dalykai, bet mes taip pat galime pakeisti, kur mes pateikimas parametrai viduje iš jų remiantis, kokio tipo funkcionalumas norime. Taigi kaminai, norėjome paskutinis viena, N, prie būti pirmasis iš. Eilė norime, kad pirmas dalykas į būti pirmas dalykas, iš. 

Taigi struct tipo apibrėžti, kaip jūs galite pamatyti, tai šiek tiek skiriasi iš to, ką kamino buvo nes ne tik mes turime išlaikyti kelio, kur dydis šiuo metu yra mes taip pat norime sekti galvos taip pat, kur šiuo metu yra. Taigi, aš manau, kad tai lengviau jei aš padaryti tai padaryti. Taigi įsivaizduokime, mes turime eilę, taip tarkim galva yra čia. Linijos vadovas, tegul tik pasakyti, kad tai šiuo metu, ir mes norime įterpti kažkas į eilę. Aš ruošiuosi skambinti dydį iš esmės yra tas pats, kaip uodega, iš kur Jūsų eilė pabaigos. Leiskite tik pasakyti dydis yra čia. 

Taigi, kaip veikia vienas realiai įterpti kažką į eilę? Kas puslapis norime vieta kur mes norime įterpti į. Jei tai yra jūsų pradžia eilėje, ir tai yra jo pabaigoje arba jo dydis, Kur mes norite pridėti kitą objektą? 

Auditorija: [nesigirdi] ANDI Peng: Būtent, jūs norite pridėti tai priklauso nuo tu parašyta ją. Bet tai yra tuščias, arba kad yra tuščias. Taigi jūs norite pridėti jį tikriausiai nes čia, jei dydis is-- jei jie visi yra pilnas, jūs norite įdėti į čia, tiesa? 

Ir taip, kad tai, o labai, labai paprastas, ne visai visada yra teisingas nes pagrindinis skirtumas tarp eilėje ir kamino yra tai, kad eilė gali iš tikrųjų bus manipuliuojama taip, kad galvos pokyčiai priklausomai nuo to, kur norite Jūsų lazda pradžia pradėti. Ir kaip rezultatas, savo uodegą taip pat ketina pakeisti. Ir taip pažvelgti šis kodas dabar. Kaip jus vaikinai taip pat buvo paprašyta rašyti ant viktorina, į eilę. Gal mes kalbame per kodėl atsakymas buvo, kas tai buvo. 

Aš negalėjau visai tinka šią eilutę į vieną, bet iš esmės tai kodo fragmentą turėtų būti vienoje eilutėje. Praleiskite kaip 30 sekundžių. Pažvelkite, ir pamatyti, kodėl tai yra būdas, kad ji yra. 

Labai, labai panašus konstrukto, labai, labai panašios struktūros kaip ankstesnis kamino išskyrus galbūt viena eilutė kodo. Ir tai viena eilutė kodo nustato funkcionalumą. Ir tai tikrai atskiria eilėje iš kamino. 

Kiekvienas nori imtis Pabandyti ne paaiškinti, kodėl jūs gavau šį sudėtingą dalyką čia? Matome grąžą mūsų nuostabus draugas modulis. Kaip jus vaikinai netrukus pripažinti programavimo, beveik bet kuriuo metu jums reikia ką nors wrap aplink nieko, modulis bus kaip tai padaryti. Taigi žinant, kad kas nors nori pabandyti paaiškinti, kad kodo eilutę? Taip, visi atsakymai yra Priimamos ir sveikintinas. Auditorija: Ar tu kalbi su manimi? ANDI Peng: Taip. Auditorija: Oi, ne gaila. ANDI Peng: Gerai, kad tegul vaikščioti per šį kodą. Taigi, kai jūs bandote pridėti kažką ant eilėje, gražioje atveju, kad galva būna būti čia, tai labai lengva mums tiesiog eiti iki galo įterpti kažką, tiesa? Bet esmė eilėje yra kad galva iš tikrųjų gali dinamiškai keistis priklausomai nuo to, kur mes nori, kad mūsų q pradžia turi būti, ir kaip toks, uodegos taip pat ketina pakeisti. 

Ir taip įsivaizduoti, kad tai buvo ne eilėje, o tai buvo eilė. Tarkime, kad galva yra čia. Tarkime, mūsų eilė atrodė taip. Jei mes norėjome perkelti kur geležinkelio linijos pradžia yra, tarkim mes persikėlė galvą Tokiu būdu ir dydžiai čia. 

Dabar mes norime pridėti kažką Ši eilė, bet kaip jus vaikinai galite pamatyti, tai nėra taip paprasta, kaip tiesiog pridėti kas yra po dydžiu nes tada mes paleisti iš ribas mūsų faktinio masyvo. Kur mes norime tikrai pridėti yra čia. Štai iš eilės grožis yra tai, kad pas mus, vizualiai jis išvaizda linija eina kaip šis, bet kai saugomi duomenų struktūros, Jie suprato, kad, kaip pavyzdžiui, ciklą. Jis rūšies kimba į priekį, taip pat, kad linijos taip pat gali wrap aplink priklausomai kur jus nori pradžia linijoje būti. Ir todėl, jei mes pažvelgsime žiūrėti žemyn čia, tegul sakyti, kad mes norėjome sukurti funkcija vadinama Įtraukti į eilę. Mes norėjome pridėti int n į tą q. Jei q.size q-- mes vadiname mūsų duomenų structure-- jei mūsų queue.size nėra lygus pajėgumų arba jeigu tai mažiau nei pajėgumų, q.strings yra per mūsų q masyvo. Mes ketiname nustatyti kad lygus q.heads, kuris yra čia, plius q.size modulis pagal pajėgumą, kuris wrap mus atgal aplink čia. 

Taigi, šiame pavyzdyje indeksą galvos yra 1, tiesa? Dėl dydžio indeksas yra 0, 1, 2, 3, 4. Taigi, mes galime padaryti 1 + 4 modulis mūsų pajėgumo, kuris 5. Ką tai mums duoda? Kas yra rodiklis, išeina apie tai? 

AUDITORIJA: 0. 

ANDI Peng: 0, kuris atsitinka būti čia, ir todėl mes nori turėti įterpti į čia. Ir todėl ši lygtis čia natūra tiesiog veikia su bet kokiu skaičių priklausomai nuo to, kur jūsų galvos ir jūsų dydis yra. Jei žinote, ką tie viskas yra, jūs žinote, tiksliai ten, kur norite įterpti kas yra po jūsų eilėje. Ar tai prasminga visiems? 

Žinau rūšies smegenų kibinimas juolab, kad ši atėjo į jūsų viktorina padarinius. Bet tikiuosi visi Dabar galite suprasti, Kodėl šis sprendimas, arba tai funkcija yra taip, kad ji yra. Kiekvienas šiek tiek neaišku, kad? GERAI. 

Ir todėl dabar, jei jus norėjau dequeue, tai kur mūsų pagrindinė būtų perkelti nes jei mes dequeue, mes ne kilimo, kad q galą. Mes norime nusiimti galvos, ar ne? Taigi, kaip rezultatas, galvos ketina keisti, ir tai, kodėl, kai jūs į eilę, jūs turite sekti kur jūsų galvos ir jūsų dydis yra, kad būtų galima įterpti į reikiamą padėtį. 

Ir todėl, kai jūs dequeue, Aš taip pat Pseudocode jį. Nesivaržykite, jei norite bandyti kodavimo this out. Jūs norite perkelti galvą, tiesa? Jei aš norėjau dequeue, aš būtų perkelti per galvą. Tai būtų galva. 

Ir mūsų dabartinė dydis būtų atimti, nes mes nebe turime keturias masyvo elementų. Mes turime tik tris, o tada mes norime grįžti kokia buvo saugomi viduje galvos, nes mes norime imtis šio vertė, išeinanti taip, labai panašios į rietuvę. Tiesiog jūs vartojate iš kitoje vietoje, ir jūs turite perleisti savo žymeklį į kitą vietą, kaip rezultatas. Logiškai mąstant, kiekvienas laikytis? Didysis. 

Gerai, kad mes ketiname kalbėti truputį išsamiau apie susijusių sąrašus nes jie bus labai, labai vertinga Jums į šios savaitės kursas psets. Susiję sąrašus, kaip jūs vaikinai atsimenu, visi jie yra yra mazgai, kurie mazgai tikras vertės tiek vertės ir rodyklė kad yra sujungti kartu šių patarimų. Ir taip, kaip konstrukto mes sukuriame mazgas čia mes turi int n, kuris yra nepriklausomai Į parduotuvėje ar styginių n vertė ar kas norite ją vadina, char žvaigždutė n. Struct mazgas žvaigždė, kuri yra žymeklis kad jūs norite turėti kiekvienas mazgas, jūs ketinate turėti, kad rodyklė taškas į kitas. Turėsite galvą Susietos sąrašą ŠTAI ketina atkreipti dėmesį į poilsio vertybės taip toliau ir taip toliau kol galiausiai pasieksite pabaigos. Ir tai paskutinis mazgas yra tik ketina neturi žymeklį. Ji ketina atkreipti dėmesį į niekinis, ir tai, kai Jūs žinote, jūs nukentėjo pabaiga susietą sąrašą yra, kai jūsų paskutinis žymeklis nerodo nieko. 

Taigi mes ketiname eiti šiek tiek daugiau gylis apie tai, kaip vienas galbūt ieškoti susietą sąrašą. Prisiminti, kokie yra kai kurie iš trūkumus, susijusius sąrašus Eilėraščiai masyvą apie paieškas. Masyvas galite dvejetainis paieškos, bet kodėl tu negali padaryti, kad susietą sąrašą? 

Auditorija: nes jie visi susiję, bet jūs neturite pakankamai žinoti, kur [Nesigirdi]. 

ANDI Peng: Taip, būtent todėl nepamirškite kad masyvo blizgesį buvo tai, kad mes turėjome laisvosios kreipties atmintį, kurioje jei aš norėjau iš indeksas vertę šešių, galėčiau tik pasakyti, šešių indeksas, duok man tą vertę. Ir tai todėl, kad matricos yra rūšiuojami į gretimos erdvės atminties vienoje vietoje, tuo tarpu rūšies susijusių sąrašus yra atsitiktinai trumpo visi aplink, ir vienintelis būdas galite rasti vieną yra per žymeklis, kad jums pasakys iš kur, kad kitą mazgas yra adresas. 

Ir taip, kaip rezultatas, yra vienintelis būdas ieškoti per susietą sąrašą yra tiesinė paieška. Kadangi aš ne tiksliai žinoti, kur 12-vertė susijusi sąraše, Turiu feed visumą tos susijęs sąrašo vieną pagal vieną iš pirmojo mazgo galvos, į antrąjį mazgas, į trečiąjį mazgas, visą kelią žemyn, kol aš pagaliau gauti kur, kad mazgas Aš ieškau yra. Ir taip ta prasme, paiešką nuo susietą sąrašą visada yra n. Jis visada n. Tai visada linijinį laiką. 

Ir taip kodo, kuria mes įgyvendinti tai, ir tai yra šiek tiek naujo jums vaikinai, nes jūs vaikinai tikrai ne kalbėjo apie ar kada nors matyti patarimų Kaip ieškoti patarimų, todėl mes vaikščioti per Tai labai, labai lėtai. Taigi bool paieška, tiesa, įsivaizduokime, mes norime sukurti funkcija vadinama Paieška kad grąžina true Jei radote vertę viduje susijusi sąrašą, ir jis grąžina false kitaip. Mazgas žvaigždė sąrašas Šiuo metu tik rodyklė į pirmą punktą savo susietą sąrašą. int n vertę, kad jūs ieškoti tame sąraše. 

Taigi mazgas žvaigždė žymeklis lygus sąrašą. Tai reiškia, kad mes kuriame ir sukurti rodyklę minėto pirmojo mazgo viduje sąrašo. Kiekvienas su manimi? Taigi, jei mes buvome eiti grįžti čia, aš norėčiau turėti inicializuoti rodyklę, kuri nukreipia į galva bet kokio, kad sąrašas yra. 

Ir tada, kai jūs gaunate žemyn čia o žymeklis nėra lygi nuliui, taip, kad yra kilpa, kurioje mes bus vėliau važiuojantiems mūsų sąrašą, nes tai, ką poilsio atsitinka, kai žymeklis yra lygus NULL? Mes žinome, kad have-- 

Auditorija: [nesigirdi] 

ANDI Peng: Būtent, todėl mes žinome, kad mes pasiekė sąrašo pabaigoje, tiesa? Jei grįžti čia kiekvienas mazgas turėtų būti nukreipta į kitą mazgas ir taip toliau ir taip toliau kol paspausite galiausiai Jūsų susietą sąrašą uodega, kuris turi žymeklį, kad tik nenurodo bet kur, išskyrus Nr. Ir taip jūs iš esmės žinoti, kad savo sąrašą dar iki kol žymiklis nėra lygi niekinis, nes kai jis lygus nuliui, jūs žinote, kad ten ne daugiau daiktų. 

Taip, kad yra kilpa, kurioje mes teks tikrąją paiešką. Ir jei pointer-- matote kad rodyklės funkciją ten natūra? Taigi, jei rodyklė kiekis n, jei rodyklė ne n lygus lygus n, taip, kad reiškia, kad jei rodyklė kad esate ieško, remiantis kiekviena pabaigoje mazgas yra faktiškai lygus vertės Jūs ieškote, tada norite grįžti tiesa. Taigi, iš esmės, jei esate ne mazgas, kad turi vertę, kad jūs ieškote, jūs žinote, kad jūs buvote sėkmingai ieškoti. 

Priešingu atveju, jūs norite nustatyti žymeklį į kitą mazgą. Tai, ką tai linija čia daro. Rodyklė lygus žymeklį šalia. Kiekvienas pamatyti, kaip, kad yra darbo? 

Ir iš esmės jūs ketinate tik feed sąrašo visumą, naujo žymeklį kiekvieną kartą, kol Jūs galų gale pateko į sąrašo pabaigą. Ir jūs žinote, kad yra ne daugiau mazgų ieškoti per, ir tada jūs galite grįžti klaidinga nes žinote, kad, oi, gerai, jei aš galėtų ieškoti per sąrašo visas. Jei šiame pavyzdyje, jei aš norėjau ieškoti 10 vertės, ir aš pradėti galvą ir Ieškoti visą kelią žemyn, ir aš galų gale tai, kuris rodyklė kad atkreipia dėmesį į NULL, Žinau, kad šūdas, spėju 10 nėra Šis sąrašas, nes aš negalėjau rasti. Ir aš ne iš sąrašo gale. Ir tokiu atveju žinote Aš ruošiuosi grįžti klaidinga. 

Leiskite, kad įsigerti truputį. Tai bus gana svarbi jūsų pset. Iš jo logika yra labai paprastas, galbūt sintaksiškai tik įgyvendinant ją. Vaikinai nori, kad Įsitikinkite, kad jūs suprantate. Saunus. 

Gerai, taip, kaip mes būtume įterpiant mazgai, į dešinę, į sąrašą, nes prisiminti kas yra kas į naudą turėti susietą sąrašą palyginti in požiūriu saugojimo masyvo? 

Auditorija: Tai dinamiška, todėl lengviau to-- 

ANDI Peng: Būtent, todėl dinamiškas, kuris tai reiškia, kad ji gali išplėsti ir trauktis priklausomai nuo vartotojo poreikius. Ir taip, šia prasme, mes nereikia gaišti be reikalo atmintį, nes aš jei aš nežinau, kiek vertės noriu į parduotuvę, tai nėra prasmės man sukurti, nes masyvo jei aš noriu laikyti 10 vertybes ir aš sukurti 1000 masyvas, tai prarastą atmintį aikštelė, skirta. Štai kodėl mes norime naudoti susijęs sąrašas, kad būtų galima dinamiškai keisti arba trauktis mūsų dydį. 

Ir taip, kad daro įterpimo šiek tiek daugiau sudėtinga. Kadangi mes negalime atsitiktinai patekti elementai taip, kad būtume masyvo. Jei aš noriu įterpti elementą į septintą indeksą, Aš tiesiog negaliu įdėkite jį į septintą indeksą. Apie susietą sąrašą, jis neturi gana dirbti, taip pat lengvai, ir todėl, jei mes norėjome įterpti vienas čia susietą sąrašą vizualiai, tai labai lengva pamatyti. Mes tik norime įterpti jį tiesiai ten, į dešinę nuo sąrašo pradžioje, iš karto po galvos. 

Tačiau būdas, kuriuo mes turime perskirstyti Į patarimų yra šiek tiek spiralinius ar logiška, logiška, bet Jūs norite įsitikinti, kad jūs turite jį galo, nes paskutinis dalykas, kurį norite yra perleisti žymeklį būdas, kad mes darome čia. Jei jums dereference žymiklį nuo galvos iki 1, tada visi staiga Kitos susietą sąrašą prarandama, nes jūs neturite iš tikrųjų sukurta laikiną nieko. Štai atkreipė dėmesį į 2. Jei priskiriate, žymeklis, tada Kitos Jūsų sąraše yra visiškai prarasta. Taigi jūs norite būti labai, labai atsargūs, čia pirmiausia priskirti rodyklė nuo Whatever You norite įterpti į kur norite, ir tada jūs gali dereference jūsų sąrašo poilsio. 

Taigi, tai taikoma ir kur Jūs bandote įterpti į. Jei norite įterpti ne galvos, jei norite atsiliepti čia jei norite įterpti ne pabaiga, gerai, galų gale aš atspėti jums tiesiog neturi žymeklį, bet jūs norite įsitikinti, kad jūs neturite prarasti savo sąrašą pailsėti. Jūs visada norite įsitikinti, jūsų naujas mazgas yra nukreipta į ką norite įterpti į, ir tada jūs galite pridėti Grupavimo toliau. Kiekvienas aišku? 

Tai bus vienas iš realių problemų. Vienas iš labiausiai pagrindinių klausimų jūs ketinate turėti savo pset yra ta, kad jūs ketinate bandyti sukurti susijusiantrosios sąrašas ir įdėkite dalykai bet tada tiesiog prarasti Kitos susietą sąrašą. Ir jūs ketinate būti kaip aš nežinau, kodėl tai vyksta? Ir tai skausmas eiti per ir ieškoti visų jūsų patarimų. 

Ir aš jums garantuoti šioje pset, rašymo ir piešimo šiuos mazgus iš bus labai, labai naudinga. Taigi jūs galite visiškai sekti kur visi jūsų patarimų yra, kas vyksta neteisingai, kur visi jūsų mazgai, ką jums reikia padaryti, norint pasiekti ar įterpti ar ištrinti ar bet kurio iš jų. Kiekvienas geras su tuo? Saunus. 

Taigi, jei mes norėjome pažvelgti į kodą? Oi, aš nežinau, jei mes galite pamatyti the-- Gerai, kad viršuje visa tai yra yra funkcija pavadintas įterpti kur mes norime įterpti int n į susietą sąrašą. Mes ketiname eiti per tai. Tai kodo daug, daug naujos sintaksės daug. Mes bus OK. 

Taigi iki viršuje, kai mes norime sukurti nieko Ką turime daryti, ypač jei noriu, kad ji negali būti laikomi ant kamino bet krūvos? Mes einame į malloc, tiesa? Taigi mes ketiname sukurti rodyklę. Mazgas, pointer, naujos nelygiaverčiai malloc apie mazgas dydį nes mes norime, kad mazgas turi būti sukurta. Mes norime, kad suma atminties, kad mazgas užima būti skiriamos už sukūrimas naujos mazge. 

Ir tada mes ketiname patikrinti pamatyti, jei naujos lygu lygu null. Prisiminkite, ką mes sakėme? Ką gi, jūs malloc, Ką reikia visada daryti? Jūs visada turi patikrinti, ar ne todėl, kad yra niekinis. 

Pavyzdžiui, jei jūsų operacinė sistema buvo visiškai pilnas, jei jums buvo ne daugiau atmintį visiems ir bandote malloc, jis sugrįš null už jus. Ir todėl, jei jūs bandote jį naudoti kai ji buvo nukreipta į NULL, esate nesiruošia galėtų prieiti prie šios informacijos. Ir taip, pavyzdžiui, mes norėjome padaryti Įsitikinkite, kad kiekvieną kartą, kai jūs mallocing, jūs visada patikrinti, pamatyti, jei kad atminties jums duota yra niekinis. Ir jei tai ne, tada mes galime judėti nuo su mūsų kodu poilsio. 

Taigi mes ketiname inicijuoti naują mazgas. Mes ketiname daryti naujus n lygus n. Ir tada mes ketiname daryti nustatyti naują dėl naujų žymiklį nulis, nes dabar mes ne nori nieko ji rodo. Mes neturime supratimo, kur jis ketina padėti jums, ir tada, jei norime įterpti jį į galvą, tada mes galime perleisti rodyklė į galvą. Ar visi vadovautis logika kur tas vyksta? 

Visi mes darome yra sukurti naujas mazgas, kuriame žymiklį NULL, ir tada perskirstymo tai į galvą, jei mes žinome, kad norite įterpti jį į galvą. Ir tada vadovas ketina nukreipta į tą naują mazgo. Kiekvienas Gerai su tuo? 

Taigi tai yra dviejų etapų procesas. Jūs turite pirmą Priskirti ką jūs kuriate. Nustatyti, kad rodyklę į nuoroda, ir tada jūs gali rūšies dereference pirmasis žymeklis ir nukreipti jį į naują mazgo. Kur norite įterpti jį, kad logika ketina laikyti tiesa. 

Tai lyg priskirdami laikini kintamųjų. Atminkite, kad jūs turite įsitikinkite, kad jums nereikia prarasti sekti, jei jūs Swapping. Jūs norite įsitikinti, kad jūs turite laikinas kintamasis, kad šios rūšies saugo stebėti, kur tą daiktą yra saugomi taip, kad jūs nereikia prarasti vertę kurso tiek kaip Messing aplink su juo. 

Gerai, kad kodas bus čia. Vaikinai pažvelgti po skirsnio. Jis bus ten. 

Taigi, manau, kaip veikia tai skiriasi, jei mes norėjome įterpti į vidurį ar gale? Ar kas nors turite ką tai idėja Pseudocode kaip logišką nuoroda kad mes imtis, jei mes norėjome įterpti jį per vidurį? Taigi, jei mes norėjome jį įterpti ne galvos, visi mes darome, yra sukurti naują mazgas. Mes nustatyti, kad žymiklis Naujas mazgas kokios galvos, ir tada mes nustatyti galvą į naują mazgo, tiesa? Jei mes norėjome įdėkite jį į vidurį sąrašo, kas mes turime daryti? 

Auditorija: jis vis būti panašus procesas tiek kaip priskiriant žymeklį ir tada priskirti tą rodyklę, bet mes turėtume ten rasti. 

ANDI Peng: Būtent, todėl tiksliai tas pats procesas, išskyrus jus turi rasti, kur tiksliai jums norite, kad naujasis žymeklis eiti į, Taigi, jei aš noriu įterpti į iš viduriniosios susijęs list-- Gerai, tarkime, kad mūsų susijusi sąrašas. Jei norime įterpti jį čia, mes ketiname sukurti naują mazgas. Mes ketiname malloc. Mes ketiname sukurti naują mazgas. Mes ketiname priskirti rodyklė šio mazgo čia. 

Bet problema, kad skiriasi iš kur galva yra yra tai, kad mes tiksliai žinojo, kur galva. Jis buvo teisus ne pirmas, teisę? Bet čia mes turime sekti kur mes įdėti jį į. Jei mes įdėti mūsų mazgas čia mes turime įsitikinkite, kad vienas prieš šio mazgo yra vienas, kad reassigns žymeklį. Taigi jūs turite natūra sekti du dalykus. Jei jums sekti kai tai mazgas metu įterpiant į. Jūs taip pat turite sekti, kur ankstesnis mazgas, kad jūs ieškote Taip pat ten buvo. Kiekvienas geras su tuo? GERAI. 

Kaip apie įterpiant į pabaigos? Jei aš norėjau pridėti jį prie here-- jei aš norėjau pridėti naują mazgas prie sąrašo pabaigoje, kaip galėčiau eiti apie tai daro? Auditorija: Taigi Šiuo metu paskutinis s nurodė null. ANDI Peng: Taip. Būtent, todėl tai vienas Šiuo metu yra pažymėti žinoti, ir todėl spėju, šia prasme, tai labai lengvai pridėti prie sąrašo gale. Viskas, ką jums reikia padaryti, tai nustatyti, kad jis lygus nuliui, o tada boom. Teisė yra labai lengva. Labai paprasta. 

Labai panaši į galvą, bet logiškai jus norite įsitikinti, kad veiksmai Jums žengti daro bet tai, jūs taip kartu. Tai labai paprasta, per vidurį Jūsų kodas, gauti pasivijo, Oh, aš turiu tiek daug patarimų. Aš nežinau, kur nieko yra nukreipta į. Aš net nežinau, kuris mazgas aš ant. Kas vyksta? 

Atsipalaiduokite, nusiraminkite, giliai įkvėpk. Ištrauk savo susietą sąrašą. Jei sakai, kad aš žinau, kur tiksliai Man reikia įterpti į tai ir aš žinau tiksliai, kaip perleisti Mano patarimų, daug, daug lengviau įsivaizduoti out-- daug, daug lengviau ne pasiklysti savo kodą klaidų. Kiekvienas Gerai su tuo? GERAI. 

Taigi, manau, koncepciją, kad mes ne tikrai kalbėjo apie prieš dabar ir aš manau, jūs tikriausiai nebus susidurti daug yet-- tai tipo Išplėstinė concept-- yra tai, kad mes iš tikrųjų turime duomenis struktūra vadinama dvigubai susietą sąrašą. Taigi, kaip jūs vaikinai galite pamatyti, visi mes darome yra sukurti faktinę vertę, papildomai rodyklė ant kiekvieno iš mūsų mazgų kad taip pat pažymi į ankstesnį mazge. Taigi mes ne tik turime mazgai atkreipti dėmesį į kitą. Jie taip pat nurodo, kad praėjusiais. Aš ruošiuosi ignoruoti šias dvi dabar. 

Taigi jūs turite grandinę kad gali judėti į abi puses, ir tada jis šiek tiek lengviau logiškai sekti kartu. Kaip ir čia, vietoj to, nuolat stebėti, oi, aš turite žinoti, kad šis mazgas yra vienas, kad aš turiu perleisti, Galiu tiesiog eiti čia ir tiesiog traukti ankstesnis. Tada aš, kur tiksliai žinoti tai yra, ir tada jūs neturite feed visuma susietą sąrašą. Tai šiek tiek lengviau. 

Bet kaip, pavyzdžiui, jūs turite dvigubai iš rodyklės suma, tai dvigubas atminties kiekis. Tai iš rodyklės daug sekti. Tai šiek tiek daugiau sudėtinga, bet tai šiek tiek daugiau patogi priklausomai apie tai, ką jūs bandote pasiekti. 

Taigi, šis duomenų tipas struktūra visiškai nėra, ir už struktūra yra labai, labai paprasta, išskyrus viskas, ko jums iškilo yra o ne tik rodyklė į kitas, jūs taip pat turite žymiklį į Ankstesnis. Štai visas skirtumas buvo. Kiekvienas geras su tuo? Saunus. 

Gerai, kad dabar aš tikrai praleisti tikriausiai kaip 15 iki 20 minučių arba urmu iš į skyrių likusį laiką kalbame apie maišos lentelėmis. Kaip daugelis iš jūsų vaikinai Perskaičiau pset5 spec? Gerai, gerai. Štai didesnis nei 50% įprastai. Viskas gerai. 

Taigi, kaip jūs vaikinai pamatys, esate iššūkis pset5 bus įgyvendinti žodyną kur įdėti per 140.000 žodžių kad mes suteikiame Jums ir rašybos tikrinimas ji prieš visą tekstą. Mes jums atsitiktinai vienetų literatūroje. Mes jums Odisėjos. Mes jums Iliada. Mes jums Austin Powers. 

Ir jūsų uždavinys bus rašybos tikrinimas kiekvienas žodis visiems tų žodynų iš esmės mūsų rašybos tikrintuvą. Ir taip ten keletas dalys sukurti šį pset, Pirmasis norite būti galėtų iš tikrųjų įkelti Visi žodžiai į savo žodynas, Ir tada jūs nori, kad būtų galima patikrinti rašybą juos visus. Ir taip, pavyzdžiui, jūs ketinate reikia duomenų struktūra, kad galite tai padaryti greitai efektyviai ir dinamiškai. 

Taigi, aš manau, lengviausia būdas tai padaryti, jums tikriausiai sukurti masyvą, tiesa? Paprasčiausias būdas sandėliuoti jus gali sukurti 140.000 žodžių masyvas ir tiesiog įdėkite juos visus ten ir tada neigia juos dvejetainiu paieškos arba selekcijos ar not-- gaila, kad manimi rūšiavimas. Jūs galite rūšiuoti juos ir tada juos feed iki dvejetainis paieškos ar tiesiog tiesinės paieškos ir tik galutiniai žodžiai, bet užima didžiulis atminties, ir tai nėra labai veiksminga. 

Ir todėl mes ketiname pradėti kalbame apie būdų, kaip padaryti Mūsų važiavimo laikas efektyviau. Ir mūsų tikslas yra gauti pastovus laikas, kai Tai beveik kaip matricos, kurioje turite momentinį priėjimą. Jei aš norėjau ieškoti nieko, Noriu, kad būtų galima tiesiog, bumas, rasti būtent tai, ir jį ištraukti. Ir taip struktūra, kurioje mes būti tampa labai arti kad būtų galima naudotis konstanta laikas, tai Gralis programavimo pastovaus laikas vadinamas maišos lentelės. Ir Dovydas anksčiau minėta, [Nesigirdi] šiek tiek į paskaitą, bet mes ketiname tikrai Dive giliai šią savaitę ant gabalas, kad manimi dėl kaip maišos lentelės veikia. 

Taigi taip, kad maišos stalo darbai, pavyzdžiui, jei aš norėjau išsaugoti žodžių krūva A krūva žodžių anglų kalba, Aš teoriškai galėtų įdėti Bananų, obuolių, kivi, mango, pora, ir Kantalupa viskas tik masyvą. Jie visi galėtų tilpti ir būti rasti. Tai būčiau rūšies skausmas ieškoti ir prieigos, bet paprastesnis būdas tai padaryti yra , kad mes galime sukurti iš tikrųjų struktūra vadinamas maišos lentelės, kur mes maišos. Mes vykdome visus mūsų raktus per maišos funkcija, lygtis, kuri paverčia juos visus į kai kurių vertė Rūšiuoti kad tada mes galime laikyti ant esmės yra susijęs sąrašo masyvas. 

Ir todėl čia, jei mes norėjome saugoti angliškų žodžių, mes galime potencialiai tiesiog, aš ne žinau, pasukite visas pirmąsias vardo raides į kai skaičių rūšiuoti. Ir taip, pavyzdžiui, jei aš norėjau A būti tapatinama su apple-- arba kartu su nuo 0 indeksą, ir B sinonimas 1, mes galime turėti 26 įrašai kad gali tiesiog laikyti visi raidžių abėcėlė, kad mes pradėti. Ir tada mes galime turėti obuolių tuo 0 indekso. Mes galime turėti bananą į indekso 1, Kantalupa tuo indeksu 2, ir taip toliau ir taip toliau. Ir taip, jei aš norėjau ieškoti mano maišos lentelės ir prieigos obuolių, Aš žinau, obuolių prasideda A, ir aš žinau tiksliai kad ji turi būti ir maišos lentelė, nes Indeksas 0 Šios funkcijos anksčiau paskirtas. 

Taigi, aš nežinau, mes esame vartotojo programa, kur jums bus pavesta arbitrarily-- ne savavališkai, su bando apgalvotai galvoti apie gerus lygtis kad būtų galima skleisti iš visų jūsų vertybes tokiu būdu, jie gali lengvai prieiti jis vėliau su kaip lygtį kad jūs, patys, žinoti. Taigi ta prasme, jei aš norėjau eiti į Mango, aš žinau, oi, ji pradeda su m. Jis turi būti bent 12 indekse. Aš neturiu ieškoti per nieko. Žinau exactly-- galėčiau tiesiog eikite į 12 ir indekso traukti, kad iš. 

Kiekvienas aišku, kaip maišos lentelės funkcija veikia? Tai tipo tik sudėtingesnio masyvo. Tai viskas yra. GERAI. 

Taigi, aš manau, kad mes paleisti į Šis klausimas, ką atsitiks, jei turite kelis dalykus kad turėtumėte patį indeksą? Taigi sako mūsų funkcija, visa tai darė, buvo imtis, kad pirmąją raidę ir pasukite, kad į "A Atitinkamas 0 per 25 indeksas. Štai visiškai gerai, jei turite tik vienas iš kiekvieno. Bet antra pradėdami turintys daugiau, jūs teks tai, kas vadinama susidūrimas. 

Taigi, jei aš pabandyti įterpti palaidoti į maišos stalo, kad jau turi bananą ant jo, kas nutiks, kai bandysite įrašyti, kad? Blogų dalykų, nes bananų jau per indeksą kad norite laikyti jį. Uogų rūšies yra tarsi Ak, ką aš galiu padaryti? Aš nežinau, kur eiti. Kaip man išspręsti šią problemą? 

Ir tokiu būdu jūs vaikinai rūšies matote, mes tai padaryti keblus dalykas kur mes galime rūšies tikrųjų sukurti susietą sąrašą mūsų matricos. Ir taip lengviausias būdas galvoti apie tai, visi maišos lentelės yra masyvas, susijusių sąrašus. Ir taip, ta prasme, jūs turite Šis gražus masyvas rodykles, ir tada kiekvienas žymeklis ši vertė, tuo indeksas, iš tikrųjų gali atkreipti į kitus dalykus. Ir todėl jūs turite visa tai atskiras grandinės atskilimas nuo vieno didelio masyvo. 

Ir todėl čia, jei aš norėjau įdėti uogų, Aš žinau, gerai, aš ruošiuosi įėjimo tai per mano maišos funkcija. Aš ruošiuosi baigti su indeksu 1, ir tada aš ruošiuosi būti suteikta galimybė tik mažesnis poaibis tai milžinišką 140.000 žodžių žodynas. Ir tada aš galiu tiesiog ieškoti per 1/26 to. 

Ir taip, tada aš galiu tiesiog įdėkite uogų prieš arba po bananų tokiu atveju? Po, tiesa? Ir taip, jūs ketinate norite įterpti šį mazgą po bananų, ir taip jūs ketinate įterpti po šios susietą sąrašo uodegos. Aš ruošiuosi grįžti šios ankstesnės skaidrės, taip vaikinai galite pamatyti, kaip maišos funkcija veikia. 

Taigi maišos funkcija Ši lygtis kad jūs dirbate rūšies jūsų indėlį per gauti bet puslapis norite priskirti jį į. Ir taip, šiame pavyzdyje, visi norėjome padaryti buvo žengti pirmą raidę, pasukti, kad į indeksą, tada mes galima laikyti, kad mūsų maišos funkcija. Visi mes darome čia mes konvertuoti pirmąją raidę. Taigi keykey [0] yra tik pirmoji raidė Bet kokios styginių mes turintys, mes einančios. Mes konvertuoti, kad į viršutinę ir mes atimant iki didžiosios A taigi visi tai daro suteikia mums numerį kurioje mes galime maišos mūsų vertybes ant. 

Ir tada mes ketiname grįžti maišos modulio dydį. Būkite labai, labai atsargūs, nes, teoriškai, čia Jūsų maišos vertė galėtų būti begalinis. Tai gali tik eiti ir apie ir apie. Tai gali būti tikrai, tikrai didelės vertės, bet todėl, kad jūsų maišos lentelė, kad jūs sukūrėte turi tik 26 indeksus, norite įsitikinti, kad jūsų modulusing, kad jūs nereikia run-- tai tas pats dalykas, kaip jūsų queue-- taip, kad jums nereikia paleisti išjungti apačioje savo maišos funkcija. 

Jūs norite, į kuriuos vyniojami aplink jį atgal vienodai [nesigirdi], kai jūs turėjote, kaip labai, labai didelis laiškas, jums nenorėjo, kad į tiesiog nubėgti į pabaigą. Tas pats čia, jūs norite įsitikinti, ji neturi nubėgti vyniojimo galą aplink lentelės viršuje. Taigi tai yra tik labai paprasta maišos funkcija. Visa tai darė, buvo priimti pirmieji laiškas kokios mūsų indėlis buvo ir pasukite, kad į indeksą, galėtume įdėti į mūsų maišos lentelė. 

Taip, ir taip kaip sakiau anksčiau, būdas, kad mes išspręsti susidūrimų Mūsų maišos lentelės turintys, ką mes vadiname, Grupavimo. Taigi, jei jūs bandote įrašyti kelių žodžiai, kurie prasideda su to paties dalyko, jūs ketinate turėti vieną maišos vertę. Avokadai ir "Apple", jei jūs paleisti jį per mūsų maišos funkcija, ketiname suteikti jums pats skaičius, 0, skaičius. Ir taip, kaip mes išspręsti tai yra kad mes galime realiai rūšies susieti juos kartu per susijusius sąrašus. 

Ir taip ta prasme, vaikinai galite pamatyti natūra kaip duomenų struktūros, kad mes jau kuriame anksčiau kaip razinų susijęs sąrašo rūšies iš gali ateiti kartu į vieną. Ir tada jūs galite sukurti gerokai efektyvesnius duomenų struktūros kuris gali apdoroti didesnes sumas duomenų, kad dinamiškai keisti priklausomai nuo nuo Jūsų poreikių. Kiekvienas aišku? Kiekvienas rūšies aišku apie tai, kas atsitinka čia? 

Jei aš norėjau insert-- Kas yra vaisius, prasideda, aš nežinau, B, išskyrus uogų, bananų. 

Auditorija: BlackBerry. 

ANDI Peng: BlackBerry, gervuogių. Kur gervuogių eiti čia? Na, mes iš tikrųjų nėra rūšiuojamos tai dar, bet teoriškai jei mes norėjome, kad tai būtų abėcėlės tvarka, kur turėtų BlackBerry eiti? 

Auditorija: [nesigirdi] 

ANDI Peng: Lygiai po čia, tiesa? Bet kadangi tai labai sunku reorder-- Aš manau, kad jis iki jums vaikinai. Vaikinai gali visiškai įgyvendinti viską, ką nori. Kuo daugiau efektyvus būdas tai padaryti, galbūt būtų rūšiuoti susijęs sąrašą į abėcėlę, ir todėl, kai jūs įterpiant dalykų, jūs norite būti tikri, kad įdėkite juos į Abėcėlės tvarka taip, kad tada, kai esate bando ieškoti jų, Jūs neturite neigia viską. Žinote, kur tiksliai ji yra, ir ji yra lengviau. 

Bet jei jūs rūšies turi viskas trumpo atsitiktinai, Jūs vis dar ketiname turėti feed anyways. Ir todėl, jei aš norėjau tik įdėkite BlackBerry čia ir aš norėjau ieškoti tai aš žinau, oi, gervuogių turi pradėti nuo 1 indeksą, todėl aš žinoti akimirksniu tiesiog ieškoti ne 1. Ir tada aš galiu rūšies feed susietą sąrašą kol aš gauti Blackberry, ir then-- Yeah? 

Auditorija: Jei jūs bandote create-- Manau, kaip tai yra labai paprastas maišos funkcija. Ir jei mes norėjome padaryti keli sluoksniai, kurie mėgsta, Gerai, kad mes norime atskirti į kaip ir visi abėcėlės raidėmis ir tada vėl norėčiau kitą rinkinį nuo abėcėlės raidėmis viduje, kad mes išleisti kaip maišos Lentelėje per maišos lentelė, arba kaip per funkcija funkcija? Arba that-- 

ANDI Peng: Taigi jūsų maišos function-- savo maišos lentelę gali būti toks didelis, kaip jūs norite, kad jis. Taigi šia prasme, aš maniau tai buvo labai lengva, labai paprastas man tiesiog tarsi remiantis ant raidės pirmojo žodžio. Ir taip yra tik 26 variantų. Aš galiu gauti tik 26 variantų iš Nuo 0 iki 25, nes jie gali tik pradėti nuo A iki Z. Bet jei jūs norėjo pridėti, ko gero, daugiau sudėtingumą arba greičiau paleisti laiko savo maišos lentelės, jums tikrai gali padaryti visų dalykų rūšių. Jūs galite padaryti savo lygtis, kuri suteikia jums daugiau platinimas jūsų žodžiai, tada, kai jums ieškoti, jis bus greitesnis. 

Tai visiškai iki jums vaikinai kaip norite įgyvendinti, kad. Pagalvokite apie tai, kaip tik kibirais. Jei aš norėjau turėti 26 kibirų, aš ruošiuosi rūšiuoti daiktus į šias kibirai. Bet aš ruošiuosi turėti krūva daiktų kiekviename segmente, Taigi, jei jūs norite, kad jis greičiau ir efektyviau, leiskite man turėti šimtus kibirų. 

Bet tada jūs turite išsiaiškinti būdas rūšiuoti dalykus taip, kad jie yra į tinkamą kibirą jie turėtų būti. Bet tada, kai jūs iš tikrųjų nori atrodyti tuo kaušu, tai daug greičiau, nes ten mažiau dalykų kiekviename segmente. Ir taip, taip, kad tikrai už jus vaikinai pset5 triukas yra ta, kad jūs būsite ginčijo tik sukurti kas yra efektyviausias funkcija jūs galite galvoti, kad būtų galima saugoti ir patikrinti šias vertybes. 

Visiškai priklauso nuo jūsų vaikinai tačiau norite tai padaryti, bet tai tikrai gera vieta. Kad logikos rūšies jūs norite pradėti galvoti apie yra gerai, kodėl ne aš padaryti daugiau kibirus. Ir tada aš turiu ieškoti mažiau dalykų, tada gal aš turi skirtingą maišos funkcijos. 

Taip, ten yra keletas būdų, kaip tai padaryti daug pset, kai yra greičiau nei kiti. Aš visiškai ketina tik pamatyti, kaip greitai buvo greičiausias vaikinai bus būti suteikta galimybė gauti jūsų funkcijos dirbti. Gerai, visi gerai Grupavimo ir maišos lentelės? Tai tikrai patinka labai paprastas koncepciją, jei jūs manote apie tai. Visa tai yra yra atskirti kokia Jūsų indėlis yra į kibirus, rūšiavimą, ir tada ieškoti sąrašus, kad ten susijęs su. 

Saunus. Gerai, dabar mes turime kitą rūšiuoti duomenų struktūrą, kuri vadinama medžio. Leiskite eiti ir kalbėti apie bandymų kurie yra aiškiai skirtingi, bet į tą pačią kategoriją. Iš esmės, visi medis yra vietoj organizuoti duomenis į linijiniu būdu kad maišos lentelės does-- jus žinote, tai atšoko viršaus ir iš apačios ir tada jūs rūšies susieti off it-- į medis turi aukščiausio kurį vadiname šaknį, ir tada jis turi lapus visi aplink jį. 

Ir taip visi jūs turite čia yra tik viršutinis mazgas kad atkreipia dėmesį į kitus mazgus, kad taškai į daugiau mazgų, ir taip toliau ir taip toliau. Ir todėl jūs tiesiog turite trupinimo filialai. Tai tiesiog skirtingi organizavimo būdas duomenys, ir dėl to mes tai medis skambinti, vaikinai just-- tai tik modeliuojama iš atrodyti medį. Štai kodėl mes jį vadiname medžiai. 

Maišos lentelė atrodo kaip stalo. Medis tik atrodo kaip medis. Visa tai yra, yra atskiras organizavimo būdas mazgai priklausomai nuo to, ką jūsų poreikius. 

Taigi jūs turite šaknis ir tada jūs turite lapus. Taip, kad mes galime ypač galvoti apie tai dvejetainis medis, dvejetainis medis yra tik konkrečios rūšies medį kur kiekvienas mazgas tik taškai kad, esant maks, kiti du mazgai. Ir todėl čia turite skiriasi simetrija savo medį kad lengviau rūšies atrodo ką vertina esate, nes tada jūs visada iš kairės arba į dešinę. Yra niekada tarsi kairėje trečdalį kairę arba iš kairės ketvirtas. Tai tiesiog turite kairę ir teisę ir jūs galite ieškoti vienoje iš šių dviejų. Ir taip, tai kodėl tai naudinga? Būdas, kad tai yra Naudinga yra, jei jūs ieškote ieškoti per vertybes, tiesa? Užuot įgyvendinant dvejetainis ieškoti klaidos masyvas, jei norite, kad būtų galima įterpti mazgai ir atimti mazgų valios ir išsaugoti paiešką pajėgumai dvejetainis paieškos. Taigi, tokiu būdu, mes rūšies tricking-- atsimenu, kai mes sakė, susijusios sąrašai negali dvejetainis paiešką? Mes rūšies sukurti duomenų struktūros kad gudrybės, kad į darbo. 

Ir todėl, susiję sąrašai yra linijinė, jie tik susieti vienas po kito. Mes galime rūšies turi skirtingo pobūdžio patarimų kad taškas skirtingų mazgų kuri gali padėti mums paiešką. Ir todėl čia, jei aš norėjau turi dvejetainį paieškos medį, Aš žinau, kad mano viduryje, jei 55. Aš tik ketina sukurti, kad kaip mano viduryje, kaip mano šaknis, ir tada aš ruošiuosi vertės nugara ne apie tai. 

Taigi čia, jei aš ruošiuosi ieškoti 66 vertė, galiu pradėti ne 55. Tai 66 daugiau nei 55? Taip, tai yra, kad aš žinau, aš Mus paiešką I n teisė žymeklis šio medžio. Aš einu į 77. Gerai, yra mažesnis nei 66 arba didesnis nei 77? Tai mažiau nei, kad jūs žinote,, OH, , kuri turi būti kairę mazgas. 

Ir todėl čia mes rūšies išsaugojimo visi iš didžiausių dalykų apie matricas, taip, kaip dinaminio dydžio keitimas Objektų, yra galėtų įterpti ir ištrinti savo valia, nereikia nerimauti fiksuoto suma erdvėje. Mes vis dar išsaugoti visus tie nuostabių dalykų o taip pat, kad galėtų išsaugoti prisijungti ir ieškoti laiką dvejetainiu paieškos kad mes buvome tik anksčiau suteikta galimybė gauti frazę. 

Nemokama duomenų struktūra, rūšies sudėtinga įgyvendinti, mazgas. Kaip matote, viskas, yra mazgas konstrukto yra tai, kad jūs turite kairę ir teisė žymeklis. Tai viskas yra. Taigi, o ne tik turintis x arba ankstesnis. Jūs turite kairę arba teisę, ir tada galite rūšies susieti juos kartu Tačiau to pageidautų. 

Gerai, mes iš tikrųjų ketiname tiesiog užtrukti keletą minučių. Taigi mes ketiname grįžti čia. Kaip minėjau anksčiau, I rūšies paaiškino Už tai, kaip mes logika būtų ieškoti per tai. Mes ketiname pabandyti pseudocoding this out pamatyti jei mes galime rūšies taikomas Ta pati logika dvejetainio paieškos į kito tipo duomenų struktūra. Jei vaikinai nori imtis, kaip pora minučių tiesiog galvoti apie tai. GERAI. Gerai, aš ruošiuosi iš tikrųjų tik suteiks jums the-- ne, mes pirmą kartą kalbėti apie Pseudocode. Taigi ar kas nors nori duoti Pabandyti ką pirmas dalykas, kurį norite padaryti, kai jūs pradedate paieška? Jei mes ieškome 66 vertė, kas pirmas dalykas, mes norime daryti, jei norime dvejetainis paieškos šį medį? 

Auditorija: Jūs norite atrodyti teisė ir surasti kairė ir pamatyti, [nesigirdi] didesnis skaičius. 

ANDI Peng: Taip, tiksliai. Taigi, jūs ketinate pažvelgti į savo šaknis. Yra daug būdų, galite skambinti tai, savo tėvų mazgas žmonės sako. Aš norėčiau pasakyti šaknis, nes tai kaip medžio šaknis. Jūs ketinate pažvelgti šakninis mazgas, ir jūs ketiname pamatyti yra 66 didesnis arba mažesnis kaip 55. Ir jei ji didesnė nei gerai, tai didesnė, jei norime atrodyti? Kur mes norime ieškoti dabar, tiesa? Mes norime atlikti paiešką teisė pusė šio medžio. 

Taigi, mes turime, patogiai A žymeklis, kad atkreipia į dešinę. Ir taip, tada mes galime nustatyti Mūsų naujas šaknis, kad būtų 77. Mes galime tiesiog eiti ten, kur rodyklė būtų nukreipta. Na, o čia mes pradedant ne 77, ir mes galime tik tai rekursyviai vėl ir vėl daryti. Tokiu būdu, jums natūra nuo turime funkciją. Jūs turite ieškoti, kad jums kelią gali tiesiog kartoti vėl ir vėl ir vėl, priklausomai nuo to, kur jūs norite atrodyti kol galiausiai patekti į vertės kad jūs ieškote. Logiška? 

Aš apie jums parodyti faktinis kodas, o tai kodo daug. Nereikia freak out. Mes kalbame per ją. 

Tiesą sakant, ne. Tai buvo tiesiog Pseudocode. Gerai, kad buvo tik Pseudocode, kuris yra šiek tiek sudėtinga, bet tai visiškai gerai. Kiekvienas taip palei čia? Jei šaknis yra niekinis, grąžinimo klaidinga nes tai reiškia, Jums net nereikia nieko ten. 

Jei šaknis n yra vertė, todėl, jei jis atsitinka būti vienas jūs ieškote, tada jūs ketinate grįžti tiesa nes jūs žinote, jūs ją radau. Bet, jei reikšmė yra mažesnė nei šaknies n, jūs ketina ieškoti į kairę vaikas ar kairysis lapas, ką jūs norite jį pavadinti. Ir jei reikšmė yra didesnė nei šaknies, jūs ketinate ieškoti tinkamą medį, tada tiesiog paleisti funkciją per paiešką dar kartą. 

Ir jei šaknys yra niekinis, kad reiškia, kad jūs pasiekėte galą? Tai reiškia, kad turite ne Plačiau lapai ieškoti, tuomet jūs žinote, oi, aš manau, kad jis ne čia nes po Matydami per visa tai, ir tai ne čia jis tiesiog gali būti ne čia. 

Ar tai prasminga visiems? Taigi, tai, kaip dvejetainiai paieškos išsaugodama aspektų, susijusių sąrašų galimybes. Cool, ir todėl antrojo tipo Duomenų struktūros jums vaikinai galite pabandyti įgyvendinti savo pset, jūs tik turite pasirinkti vieną metodą. Bet galbūt alternatyvus būdas maišos lentelė yra tai, ką mes vadiname TRIE. 

Visi A Trie yra yra konkrečios rūšies medžio, turi vertybes, eiti į kitas vertybes. Taigi vietoj to, dvejetainis medis ta prasme, kad tik vienas dalykas gali nurodyti du, jūs galite turėti vienas dalykas taškas daugelį dalykų. Jūs iš esmės turi masyvų kurio viduje galite laikyti patarimų, kurie nurodo į kitas matricas. 

Taigi, kaip mes mazgas būtų apibrėžti TRIE yra mes norime turėti Būlio c žodis, tiesa? Taigi mazgas yra Būlio kaip true arba false, visų pirma, esant galvos kad masyvas, tai žodis? Antra, jūs norite turėti rodykles kad nepriklausomai nuo jų poilsio yra. Šiek tiek sudėtinga, šiek tiek abstraktus, bet Aš paaiškinti, kas tai visais būdais. 

Taigi čia, viršuje, jei tau turi masyvas jau paskelbė, mazgas, kuriame jūs turite Būlio saugoma vertė priekyje kad jums pasakys, tai žodis? Ar tai ne žodis? Ir tada jūs turite poilsio savo matrica, iš tikrųjų saugo visus galimybės, kas tai galėtų būti. Taigi, pavyzdžiui, kaip ir viršuje turite pirmas dalykas, kad sako tiesa ar klaidinga, taip arba ne, tai yra žodis. 

Ir tada jūs turite 0 per 26 raidės, kad galite parduotuvėje. Jei aš norėjau ieškoti čia GPGB, aš einu į viršų ir aš surasti B. Manau, B ir mano masyvas, ir todėl žinau, gerai, yra B žodis? B nėra žodis, todėl tokiu būdu Turiu nuolat ieško. Aš einu iš B ir žiūriu į žymeklis, kad B atkreipia į ir matau kitą informaciją masyvą, Ta pati struktūra, kad mes turėjome anksčiau. 

Ir here-- oh, kitą laiškas [nesigirdi] yra A. Taigi, mes pažvelgti į tą masyvą. Mes rasti aštuntą vertę, ir tada mes pažiūrėkite, OH, ei, yra tai, kad Žodžiu, yra B-A žodis? Tai ne žodis. Mes turime nuolat ieško. 

Ir taip, tada mes žiūrime, kur ā kiekis žymeklis, ir ji pažymi, kad kitas būdas, kuri mes turime daugiau vertės saugomi. Ir, galų gale, mes turime B-A, T-, kuris yra žodis. Ir todėl kitą kartą jums atrodo, kad jūs ketinate turėti tą, taip čekį, tai Bulio funkcija yra tiesa. Ir taip ta prasme mes natūra turėti medį su matricos. 

Taigi galite rūšies ieškoti žemyn. Užuot maišos funkciją ir priskirdami reikšmes susietą sąrašą galite tiesiog įdiegti Trie, kuris ieško downwords. Tikrai, tikrai sudėtinga stuff. Ne lengva galvoti apie, nes aš, kaip spjaudytis tiek daug duomenų struktūras iš ne jums, bet ar visi rūšies suprasti kaip veikia ši logika? 

Gerai. Taigi, B-A, T-, ir tada jūs ketinate ieškoti. Kitą kartą jūs ketinate pamatyti, oi, ei, tai tiesa, Taigi aš žinau, tai turi būti žodis. 

Tas pats dalykas zoologijos sode. Taigi čia dalykas dabar, jei mes norėjau ieškoti zoologijos sode, dabar, Šiuo metu zoologijos sode nėra Žodis mūsų žodyno nes, kaip jūs vaikinai gali matote, Pirmoji vieta, kad mes turime Būlio grįžti teisinga yra ne iš mastelio pabaigoje. Mes turime Z-O-O-M. 

Ir todėl čia mes ne iš tikrųjų turėti žodis, zoologijos sodas, mūsų žodyno nes tai langelis nepažymėtas. Taigi kompiuteris nėra žinau, kad zoologijos sodas yra žodis nes taip, kad mes saugomi ją, tik priartinimas čia iš tikrųjų yra Būlio vertė kad buvo įjungtas tiesa. Taigi, jei norime įterpti Žodis, zoologijos sodas, į mūsų žodyną, kaip mes turime eiti apie tai daro? Ką mes turime daryti, kad mūsų kompiuteris žino, kad Z-O-O yra žodis ir ne pirmas žodis yra Z-O-O-M? 

Auditorija: [nesigirdi] 

ANDI Peng: Būtent, mes norite įsitikinti, kad ši čia, kad Būlio vertė yra patikrinti išjungti, kad tai tiesa. Z-O-O tada mes ketiname patikrinti, kad todėl mes žinome tiksliai, ei, zoologijos sodas yra žodis. Aš ruošiuosi papasakoti kompiuteris, tai žodis, todėl kad kai kompiuterinius patikrinimus, jis žino, kad zoologijos sodas yra žodis. 

Kadangi prisiminti visus šiuos duomenis struktūros, tai labai lengva mums pasakyti, oi, GPGB yra žodis. Golfas yra žodis. Zoom žodis. Bet kai jūs ją kuriant, kompiuteris neturi jokios idėjos. 

Taigi jūs turite pasakyti, tiksliai momentas, kada tai žodis? Tuo, ką taškas yra tai nė žodžio? Ir ką daryti, I vieta reikia ieškoti dalykų, ir kokia vieta man reikia eiti toliau? Kiekvienas aišku, kad? Saunus. 

Ir taip, tada ateina problema Kaip mes eiti apie įterpiant kažką kad tikrai ne ten? Taigi tegul tiesiog pasakyti, kad mes norite įterpti žodis, vonia, į mūsų TRIE. Kaip jus vaikinai galite pamatyti, kaip šiuo metu visi mes turime dabar yra B-A-T, ir ši nauja duomenų struktūra ten turėjo pintos, kad atkreipė dėmesį į null nes mes manome, kad, oi, ten ne po žodžių B-A-T, kodėl mes turime išlaikyti turintys dalykų po to T. 

Bet problema kyla, jei mes darome Jums norite turėti žodį, kuris ateina po T-aisiais. Jei turite vonia, jūs ketinate norite H teisę. Ir taip, kaip mes ketiname daryti, kad yra mes ketiname sukurti atskirą mazgą. Mes ne skirti bet kokią sumą atminties šios naujos masyvo, ir mes ketiname perleisti patarimų. 

Mes ketiname priskirti H, Pirmiausia, šis nulis, mes ketiname atsikratyti. Mes ketiname turėti H taško žemyn. Jei matome H, mes norime ją eiti į kažkur kitur. 

Čia, mes galime tada patikrinkite išjungti taip. Jei mes paspauskite H po T, OH, tada mes žinome, kad tai yra žodis. Būlio ketina grįžti tiesa. Kiekvienas aišku, kaip tai atsitiko? GERAI. 

Taigi, iš esmės, visi Šie duomenų struktūros kad mes perėjo šiandien, aš dingo virš jų tikrai, tikrai greitai o ne į daug detalė, ir kad viskas OK. Kai pradėsite Messing su juo, jūs būsite sekti, kur visos rodykles yra, kas vyksta jūsų duomenų struktūros et cetera. Jie bus labai naudinga, ir jis iki jums vaikinai visiškai išsiaiškinti, kaip norite įgyvendinti dalykus. 

Ir taip pset4, iš 5-- O, kad yra negerai. Pset5 yra rašybos klaidų. Kaip minėjau anksčiau, jūs ketinate, kai vėl parsisiųsti išeities kodą iš mūsų. Ten bus trys pagrindinės viskas jums bus atsisiųsti. Jūs parsisiųsti žodynus, Kers, ir tekstus. 

Visi šie dalykai yra yra arba žodynai žodžių kad mes norime, kad jūs patikrinti arba bandymo informacijos kad mes norime, kad jūs rašybos tikrinimas. Ir taip žodynai mes suteikiame jūs ketinate duoti jums realius žodžius, kad mes norime jums laikyti kažkaip taip, kad manimi efektyvesnis nei masyvą. Ir tada tekstai bus ką mes klausia jums rašybos įsitikinkite, visi žodžiai yra tikri žodžiai. 

Ir taip tris blokai programos, kad mes suteiksime jums yra vadinami dictionary.c, dictionary.h ir speller.c. Ir taip visi dictionary.c daro, yra ką jūs paprašė įgyvendinti. Jis įkelia žodžius. Tai rašybos čekius juos, ir tai daro tikrai kad viskas būtų teisingai įdėta. 

diction.h yra tik bibliotekos failą kad deklaruoja visas šias funkcijas. Ir speller.c, mes ketiname suteikti jums. Jums nereikia keisti bet jį. Visi speller.c ar yra imtis, kad krovinius ji, tikrina jo greitį, tikrina, kad, pavyzdžiui, kaip etalonas greitai jūs galėsite daryti dalykus. 

Tai Speller. Tiesiog nereikia netvarka su juo, bet įsitikinkite, kad jūs suprantate, ką jis daro. Mes naudojame funkcija vadinama getrusage kad tikrina savo kerus našumą tikrintuvą. Visa tai daro iš esmės yra išbandyti laikas viską savo žodyną, todėl įsitikinkite, kad jūs jį suprasti. Būkite atsargūs, ne netvarka su juo arba kitur dalykai neveiks tinkamai. 

Ir šį iššūkį urmu yra vaikinai tikrai keisti dictionary.c. Mes ketiname suteikti jums 140.000 žodžių žodyne. Mes ketiname suteikti jums tekstą failas, kuris turi tuos žodžius, ir mes norime, kad jūs gebėti organizuoti juos į maišos lentelė arba TRIE nes kai mes prašome jus rašybos check-- įsivaizduokite, jei esate rašybos tikrinti, kaip Homero Odisėjoje. Tai kaip šios didžiulės, didžiulis tyrimas. 

Įsivaizduokite, jei kiekvienas Žodis jums buvo ieškoti per 140.000 vertybių masyvo. Tai amžinai jūsų mašina paleisti. Štai kodėl mes norime organizuoti savo duomenis į efektyvesnius duomenų struktūrų pavyzdžiui, maišos lentelė arba TRIE. Ir tada jūs vaikinai gali natūra kada jums ieškoti prieigą viskas lengviau ir greitai. 

Ir todėl būkite atsargūs išspręsti susidūrimų. Jūs ketinate gauti ryšelyje Žodžių tos pradžios su A. Jūs ketinate gauti ryšelyje žodžius kad pradėti su B. Iki jumis vaikinai, kaip jūs norite ją išspręsti. Gal yra daugiau efektyvus maišos funkcija ne tik pirmąją raidę kažkas, ir taip, kad iki jums vaikinai rūšies daryti ką nori. 

Gal norite pridėti Visos raidės kartu. Gal norite patinka daryti keistus dalykus apskaityti raidžių, skaičių, nesvarbu. Iki jums vaikinai, kaip jūs norite daryti. Jei norite padaryti, maišos lentelę, jeigu jūs noriu pabandyti TRIE, visiškai priklauso nuo jūsų. Aš jus perspėti iš anksto, kad Trie paprastai yra šiek tiek sunkiau tik todėl, kad ten yra daug daugiau patarimų sekti. Tačiau visiškai iki jums vaikinai. Tai kur kas efektyviau daugeliu atvejų. Jūs norite, kad tikrai galės išlaikyti stebėti visas savo rodykles. Kaip padaryti tą patį kad aš darau čia. Kai bandote įrašyti vertybes maišos lentelę arba ištrinti, įsitikinkite, kad esate tikrai sekti kur viskas yra, nes tai tikrai lengva, jei aš bando įterpti kaip žodžio, Andy. Leiskite tik pasakyti, kad tai nekilnojamojo žodis, žodis, Andy, į milžinišką sąrašą A žodžių. 

Jei aš tiesiog atsitikti perleisti rodyklė negerai, Oi, ten eina į visumą mano susietą sąrašą poilsio. Dabar vienintelis žodis man turi Andy, o dabar visų kitų žodžius žodynas buvo prarasta. Ir todėl jūs norite įsitikinti, kad jūs sekti visus savo rodykles arba dar jūs ketinate gauti didelių problemų Jūsų kodas. Lygiosios dalykų atsargiai, žingsnis po žingsnio. Ji daro tai daug lengviau galvoti. 

Ir galiausiai, jūs norite, kad būtų galima išbandyti savo veiklos rezultatus savo programą dideliame laive. Jei vaikinai užtrukti pažvelgti CS50 dabar, mes turime tai, kas vadinama didelis lenta. Tai rezultatas lapas iš sparčiausiai tikrinti rašybą kartus per visą CS50 dabar, manau, kad kaip Top 10 kartų aš manau, kad aštuoni iš jų yra darbuotojai. Mes tikrai norime jus vaikinai įveikti mus. 

Visi mes bandome įgyvendinti sparčiausiai kodas, kaip įmanoma. Mes norime jums, vaikinai bando mesti iššūkį JAV ir įgyvendinti greičiau nei mums visiems galite. Ir taip, tai tikrai pirmas kartas, kai mes klausia jums vaikinai padaryti pset kad jūs tikrai galite padaryti kokiu nors būdu tu nori. 

Aš visada sakau, tai labiau panašus prie realaus gyvenimo sprendimas, tiesa? Sakau, ei, aš turiu jums tai padaryti. Sukurkite programą, kuri tai daro už mane. Ar ji vis dėlto norite. Aš tiesiog žinau, kad aš noriu greitai. Štai jūsų uždavinys šią savaitę. Jūs vaikinai, mes ketiname duoti jums užduotį. Mes ketiname suteikti jums iššūkį. Ir tada jis iki jums vaikinai visiškai tik išsiaiškinti, kas yra greičiausias ir labiausiai efektyvus būdas įgyvendinti tai. Taip? 

Auditorija: Ar mes leidžiama, jei norėjo ištirti greičiau būdai daryti maišos lenteles internete, mes galime padaryti kad ir pacituoti kažkieno kodą? ANDI Peng: Taip, visiškai gerai. Taigi, jei jus vaikinai skaityti spec, ten linija į spec, kad sako, kad jūs vaikinai yra visiškai nemokama mokslinių tyrimų maišos funkcijas, kas yra kai iš greičiau maišos funkcijų paleisti dalykų per taip Tol, kol jūs paminėti, kad kodą. Taigi kai kurie žmonės jau turi išsiaiškino, greitai būdų daro rašybos tikrinimo, iš greitai būdai saugoti informaciją. Visiškai priklauso nuo jūsų vaikinai jei jus noriu tiesiog, kad, tiesa? Įsitikinkite, kad esate Cituojant. Iššūkis čia tikrai kad mes bandome išbandyti yra užtikrinti, kad jūs žinote, savo kelią aplink patarimų. Kiek jums įgyvendinti faktinis maišos funkcija ir ateina su, kaip matematika tai padaryti, vaikinai gali tirti kokia metodai internete vaikinai nori. Taip? 

Auditorija: Ar mes paminėti tik naudodami [nesigirdi]? 

ANDI Peng: Taip. Jūs galite tiesiog iš savo komentarą, galite paminėti, pavyzdžiui, OH, paimti iš bla, bla, bla, maišos funkcija. Kiekvienas turi kokių nors klausimų? Mes iš tikrųjų breezed per skyrių ir šiandien. Aš būsiu čia, kad atsakyti į klausimus, taip pat. 

Be to, kaip jau minėjau, biuro val vakarą ir rytoj. SPEC šią savaitę iš tiesų yra super lengva ir super trumpas skaityti. Siūlyčiau atsižvelgiant išvaizdą, tiesiog skaityti per ją visas. 

Ir Zamyla tikrųjų walks jus per kiekvieną funkcijų Jums reikia įgyvendinti, ir todėl labai, labai aišku, kaip viską daryti. Tiesiog įsitikinkite, kad jūs esate sekti nurodymus. Tai labai sudėtinga pset. 

Tai ne iššūkis, nes kaip, Oi, sąvokos yra daug daugiau sunku, ar jūs turite išmokti tiek daug naujos sintaksės būdas kad tu paskutinį pset. Tai pset yra sunku, nes yra tiek daug patarimų, ir tada ji labai, labai lengva, kai Jūs turite savo kodą klaidą negalės surasti, kur, kad klaida yra. 

Ir taip visiškai ir pratarti tikėjimas jumis vaikinai, kad būtų galima įveikti mūsų [nesigirdi] Tarimas. Aš iš tikrųjų turime ne kokį nors rašytinį mano dar, bet aš apie rašyti mano. Taigi, nors rašote Pagarbiai, aš rašyti mano. Aš ruošiuosi pabandyti padaryti mano greičiau nei jūsų. Pamatysime, kas turi greičiausią vieną. 

Ir taip, aš pamatysite visus vaikinai čia antradienį. Aš paleisti panašaus pset dirbtuvėse natūra. Visi sekcijų šis savaitę yra pset dirbtuvės, todėl jūs vaikinai turite daug galimybių pagalbos, biuro valandas, kaip visada, ir aš tikrai laukiu skaityti visus jūsų vaikinų kodą. Turiu viktorinos iki čia, jei vaikinai nori ateiti gauti tuos. Tai viskas.