>> [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.