[Muzikos grojimo]
SPEAKER 1: Gerai.
Kiekvienas sveikintinas grįžti į skyrių.
Tikiuosi, kad jūs visi esate sėkmingai išieškoti iš jūsų viktorinos
nuo praėjusios savaitės.
Žinau, kad tai šiek tiek kvailai, kartais.
Kaip jau sakiau anksčiau, jei esate per standartinį nuokrypį,
nelabai nerimauti, ypač už mažiau patogus skyriuje.
Štai apie tai, kur ir turėtų būti.
>> Jei taip puiku, tada awesome.
Kudos į jums.
Ir jei jūs manote, kaip jums reikia šiek tiek daugiau pagalbos, prašome
nedvejodami pasiekti iš bet kuriai TFS.
Mes visi esame čia, kad padėtų.
>> Štai kodėl mes mokome.
Štai kodėl aš čia kiekvieną pirmadienį jums vaikinai ir ne darbo valandomis ketvirtadieniais.
Taigi, prašome nedvejodami praneškite man žinoti jei esate susirūpinę nieko
arba, jei nėra nieko ant Viktorinos kad jūs tikrai patinka spręsti.
>> Taigi šiandien darbotvarkę viskas apie duomenų struktūras.
Kai kurie iš jų yra tik ketina būti tik gauti Jums supažindinti su šiomis.
Jūs negalite niekada įgyvendinti juos į šią klasę.
Kai kurie iš jų bus, kaip jūsų Speller pset.
>> Jūs galite pasirinkti tarp maišos lentelėmis ir bando.
Taigi mes tikrai reikia eiti per juos.
Ji ketina būti tikrai daugiau rūšių iš horizontalaus aukštos šiandien, nors,
nes ten yra daug iš jų, o jei nuėjome į įgyvendinimo detales
dėl visų šių, mes gi ne net gauti per susijusias sąrašus
o gal šiek tiek maišos lenteles.
>> Taigi būti su manimi.
Mes neketiname daryti kaip daug kodavimo šį kartą.
Jei turite kokių nors klausimų apie tai ar jūs norite pamatyti, kuris įgyvendino
arba patys jį išbandyti, Aš tikrai rekomenduoju
ketina study.cs50.net, kuris pavyzdžiai turi visa tai.
Tai turite savo PowerPoints su pastabomis, kad mes
linkę naudoti taip pat kai programavimo pratimai, ypač už tai, ko
kaip susijusių sąrašų ir dvejetainės medžiai vamzdžiai ir užuominas.
Taigi šiek tiek daugiau aukšto lygio, kuris gali būti gražus jums vaikinai.
>> Taigi su tuo, mes pradėti.
Ir taip pat, yes-- viktorinos.
Manau, kad dauguma iš jūsų, kurie yra mano sekcija turi savo viktorinos,
bet kiekvienas ateina arba kokios nors priežasties jums ne, jie tiesiog čia, priekyje.
>> Taigi susietas sąrašus.
Aš žinau, tai rūšies eina atgal prieš savo viktoriną.
Tai buvo prieš savaitę kad mes sužinojome apie tai.
Tačiau šiuo atveju, mes tiesiog eiti šiek tiek daugiau į gylį.
>> Tad kodėl gali renkamės susijęs sąrašas per masyvą?
Jų skiriamieji?
Taip?
>> AUDITORIJA: Galite išplėsti susijęs sąrašą, palyginti masyvą fiksuotas dydis.
SPEAKER 1: Teisė.
Masyvas turi fiksuotas dydis tarpu susijęs sąrašas yra kintamas dydis.
Taigi, jei mes nežinome, kaip daug norime išsaugoti,
susijęs sąrašas suteikia mums puikus būdas tai padaryti, nes mes galime tiesiog
pridėti kitą mazgas ir pridėti kitas mazgas ir pridėti kitą mazgą.
Bet kas gali būti kompromisas?
Ar kas nors prisimena kompromisą tarp matricos ir susijusių sąrašus?
Mmhmm?
>> AUDITORIJA: Jūs turite pereiti visą kelią
Susietos sąrašą rasti sudarant sąrašą elementą.
Masyve, galite tiesiog rasti elementą.
>> SPEAKER 1: Teisė.
Taigi su arrays--
>> AUDITORIJA: [nesigirdi].
>> SPEAKER 1: Su masyvais, turime tai, kas vadinama operatyvioji.
Tai reiškia, kad jei mes norime ką kada penktoji vieta iš sąrašo
arba penktasis taškas mūsų masyvas, galime tiesiog paimti jį.
Jei tai susiję sąrašas, turime kad paeiliui per, tiesa?
Taigi gauti in elementą masyvas yra pastovus laikas,
o su susietą sąrašą Būtų greičiausiai būtų tiesinis laiko, nes gal
elementas yra mūsų visi pabaigoje būdas.
Mes turime ieškoti per viską.
Taigi visus šiuos duomenis struktūros Važiuojame
reikia skirti šiek tiek daugiau laiko, kokie pliusai ir negatyvai.
Kai gali norime naudoti vieną virš kito?
Ir kad tipo didesnis dalykas atimti.
>> Taigi, mes turime čia apibrėžimas mazgas.
Tai kaip vieną elementą mūsų susijęs sąrašas, tiesa?
Taigi, mes visi susipažinę su mūsų Typedef structs,
kurioje mes visi drauge perėjo peržiūros paskutinį kartą.
Iš esmės tai buvo tiesiog sukurti kitas duomenų tipas, kad mes galime naudoti.
>> Ir šiuo atveju, tai kai mazgas kad laikys tam tikrą sveikuosius.
Ir tada kas antra dalis čia?
Kiekvienas?
>> AUDITORIJA: [nesigirdi].
>> SPEAKER 1: Taip.
Tai žymiklį į kitą mazgą.
Taigi tai iš tiesų turėtų būti čia.
Tai tipo rodyklė mazgas į kitą dalyką.
Ir tai, ką jie apima mūsų mazgas.
Cool.
>> Gerai, taigi su paieškos, kaip mes buvome tiesiog pasakyti prieš vertus, jei esate
ketina ieškoti, jūs turite iš tikrųjų pakartoti
per savo susietą sąrašą.
Taigi, jei mes ieškome numerį 9, mes pradėti mūsų galvos
ir kad mums primena pradžioje Mūsų susietą sąrašą, ar ne?
Ir mes sakome, gerai, tai daro mazgas yra skaičių 9?
Ne?
>> Gerai, eikite į kitą.
Sekite jį.
Ar jame skaičių 9?
Ne.
Sekite kitą.
>> Taigi, mes turime iš tikrųjų pakartoti per mūsų susietą sąrašą.
Mes galime ne tik eiti tiesiai ten, kur 9 yra.
Ir jei jus vaikinai iš tikrųjų nori matyti kai pseudo-kodas ten.
Mes kai paieškos funkcija čia kad mano in-- ką reikia iš?
Ką manote?
Taigi lengva.
Kas tai yra?
AUDITORIJA: [nesigirdi].
SPEAKER 1: skaičius mes ieškome.
Teisė?
Ir kas galėtų tai atitinka?
Tai žymiklį?
>> AUDITORIJA: mazgas.
>> SPEAKER 1: mazgas į sąrašą kad mes ieškome, ar ne?
Taigi, mes turime kai mazgai yra žymeklis čia.
Tai vieta, kad ketina tikrai kartoti, kad mūsų sąraše.
Mes nustatėme, kad lygus sąrašą nes tai tik
nustatant ji lygi pradėti mūsų susietą sąrašą.
>> Ir nors tai nėra NULL, o mes vis dar turime dalykų mūsų sąraše,
patikrinkite, ar kad mazgas turi skaičius mes ieškome.
Grąžina true.
Kitaip, atnaujinti jį, ar ne?
>> Jei jis yra NULL, mes išeiti mūsų while cikle ir grįžti klaidinga
nes tai reiškia, kad mums nepavyko rasti jį.
Ar visi gauti, kaip tai veikia?
Gerai.
>> Taigi su įterpimą, turi tris skirtingus būdus.
Galite Dėti galite pridėti ir jūs galite įdėti į asorti.
Šiuo atveju, mes ketinate daryti Dėti.
Ar kas nors žino, kaip tie, trys atvejai gali skirtis?
>> Taigi pridėkite reiškia, kad jūs galėsite įdėti tai ne jūsų sąrašo priekyje.
Taigi tai reikštų, kad nesvarbu, koks jūsų mazgas, nesvarbu
kas vertė yra, jūs ketinate įdėti ją tiesiog čia, priekyje, gerai?
Ji ketina būti pirmas elementas yra sąraše.
>> Pridėjus tai, kad vyksta eiti į savo sąrašą, nugaros.
Ir įdėkite į asorti reiškia, kad jūs ketina pateikti faktiškai į vietą
kur ji saugo jūsų susijęs sąrašas rūšiuojami.
Vėlgi, kaip jūs naudojate tie ir kai jūs naudojate
jiems gali skirtis priklausomai nuo jūsų atveju.
Jei jis neturi reikia rūšiuoti, pridėkite linkęs
būti tai, ką dauguma žmonių naudoti, nes jūs neturite
turi eiti per visą sąrašą rasti pabaigą pridėti jį prie, tiesa?
Jūs galite tiesiog klijuoti tiesiai.
>> Taigi mes bus eiti per įterpimas 1 dabar.
Taigi vienas dalykas, kad aš ruošiuosi labai rekomenduoju šia pset
atkreipti dalykus, kaip visada.
Tai labai svarbu, kad jūs atnaujinsite jūsų patarimų teisinga tvarka
nes jei juos atnaujinti šiek tiek iš tam,
jūs ketinate baigti prarasti dalių sąrašo.
>> Taigi, pavyzdžiui, šiuo atveju, mes sako tiesiog taško galva 1.
Jei mes tiesiog padaryti, kad neįrašę šį 1,
mes neturime supratimo, ką 1 turėtų nurodyti dabar
nes mes jau prarado, ką vadovas pabrėžė.
Taigi vienas dalykas prisiminti kai darai Dėti
yra išsaugoti tai, ką Galvos nurodo, pirma,
tada iš naujo priskirti, o tada atnaujinkite ką jūsų naujasis mazgas turėtų nurodyti.
Šiuo atveju, tai yra vienas būdas tai padaryti.
>> Taigi, jei mes padarė jį šiuo būdu kur mes tiesiog perskirstomas galvą,
mes prarasime esmės DUK Visas sąrašas, tiesa?
Vienas iš būdų tai padaryti yra turėti 1 tašką šalia, ir tada turėti galvos tašką 1.
Arba jūs galite padaryti šiek tiek kaip laikinas saugojimas, kurį aš kalbėjau apie.
>> Bet perskirstymo tavo rodykles teisinga tvarka
bus labai, labai svarbu, kad šis pset.
Priešingu atveju, jūs ketinate turėti maišos stalo arba pabandyti tai tik bus
tik dalis žodžių, o tuomet you're-- mmhmm?
AUDITORIJA: Koks buvo laikinas saugojimas dalykas, kurį buvo kalbi?
SPEAKER 1: laikinas saugojimas.
Taigi, iš esmės kito būdas galite tai padaryti
yra saugoti galva kažko, kaip laikykite laikiną kintamąjį.
Priskirti ją 1 ir tada atnaujinkite 1 taškas
į ką galva naudojamas nurodyti.
Taip, žinoma, daugiau elegantiškas, nes jums
nereikia laikiną vertės, tačiau tik siūlyti kitą būdą tai padaryti.
Ir mes iš tikrųjų turime kai už tai kodas.
Taigi susietas sąrašą, mes iš tikrųjų turi tam tikrą kodą.
Taigi įterpti čia tai prepending.
Taigi tai, įveda jį į galvą.
>> Taigi pirmas dalykas, ką jums reikia sukurti naują mazgas, žinoma,
ir patikrinkite, ar NULL.
Visada geras.
Ir tada jūs turite priskirti vertybes.
Kiekvieną kartą, kai jūs sukuriate naują mazgas, jums nežinau, ką ji nukreipta į kitas,
todėl jūs norite inicijuoti ją null.
Jei jis galų gale nukreipta į kažką kita, jis bus perkeltas ir tai gerai.
Jei tai pirmas dalykas, į sąrašą, ji turi
atkreipti NULL nes tai sąrašo gale.
>> Taigi tada įdėkite jį matome čia mes yra priskirti kitą reikšmę mūsų mazgas
būti kokia galva, o tai, ką mes turėjome čia.
Štai ką mes ką tik padarė.
Ir tada mes priskiriame galvos iki taško į mūsų naują mazgą, nes atsimenu,
Nauja tai kai Rodyklė į mazgą, Ir tai būtent tai, ką galva.
Būtent todėl mes turi šią rodyklės accessor.
Cool?
Mmhmm?
>> AUDITORIJA: Ar turime inicijuoti naują Next NULL pirma,
ar mes galime tiesiog inicijuoti jį į galvą?
>> SPEAKER 1: Naujoji Kitas turi būti lygus NULL pradėti
nes jūs nežinote, kur jis bus.
Be to, tai yra natūra tiesiog patinka paradigmos.
Jūs nustatote, kad lygus NULL, tik, kad įsitikinkite, kad visi jūsų bazės apima
pries tai jokios paskirties pakeitimą taip, kad jūs visada garantuojama, kad jis bus
būti nukreipta į tam tikra specifine verte prieš kaip šiukšlių vertę.
Nes, taip, mes priskirti Naujas šalia automatiškai
bet tai daugiau kaip gera praktika inicijuoti ją
tokiu būdu ir tada perleisti.
>> Gerai, kad dvigubai susietas sąrašus dabar.
Ką mes manome?
Koks skirtumas su dvigubai susietas sąrašus?
>> Taigi mūsų susijusių sąrašus, galime perkelti tik į vieną pusę, į dešinę?
Mes turime tik šalia.
Mes galime tik eiti į priekį.
>> Su dvigubai susietas sąrašą mes taip pat galite perkelti atgal.
Taigi, mes turime ne tik skaičius, kad mes norime saugoti,
turime kur ji nurodo kitas ir kur mes tiesiog atėjo.
Taigi tai leidžia kai geriau Sankryþos.
>> Taigi dvigubai susiję mazgai, labai panašus, tiesa?
Skirtumas tik tas, dabar mes turėti šalia ir ankstesnių.
Tai vienintelis skirtumas.
>> Taigi, jei mes Dėti arba append-- mes Neturime kodas tai iki here--
bet jei jums buvo išbandyti ir įdėkite jį, svarbiausia
yra jums reikia padaryti kad jūs priskirdami
tiek savo ankstesnio ir savo Kitas žymeklis teisingai.
Taigi šiuo atveju, jūs, ne tik inicijuoti kitas,
Jūs inicijuoti ankstesnę.
Jei mes ne sąrašo galvos, mes būtų ne tik, kad galva lygi naujas,
bet mūsų naujas ankstesnę dozę atkreipti į galvą, ar ne?
>> Tai vienintelis skirtumas.
O jei norite daugiau praktikos su tai su susijusiomis sąrašus, kuriuose įterpimo,
su išbraukiant, su įdėklu į asorti sąrašą
prašome patikrinti study.cs50.net.
Yra daug puikių pratimų krūva.
Aš labai rekomenduoju juos.
Aš noriu, kad mes turėjome laiko eiti per juos bet ten iš duomenų struktūrų daug
perėmė kamuolį.
>> Gerai, kad maišos lenteles.
Tai turbūt pats naudinga tiek Jūsų pset
čia, nes jūs ketinate būti Įgyvendinant vieną iš šių arba pabandyti.
Man labai patinka maišos lenteles.
Jie gana kietas.
>> Taigi, iš esmės tai, ką atsitinka maišos lentelė
yra tada, kai tikrai reikia greitai įvesti, ištrinti ir peržvalgos.
Tai yra tai, kas mes esame pirmenybę tam maišos lentelė.
Jie gali gauti gana didelis, bet kaip pamatysite su bando,
yra dalykų, kurie yra daug didesni.
>> Bet iš esmės, visi maišos lentelė maišos funkcija
kad jums pasakys, kuris kibirą įdėti kiekvienas savo duomenis, kiekvienam iš jūsų elementų.
Paprastas būdas galvoti apie maišos lentelė yra tai, kad tai tik kibirai dalykų,
tiesa?
Taigi, kai jūs rūšiavimas dalykus kaip pirmąją raidę savo vardą,
kad tipo kaip maišos lentelėje.
>> Taigi jūs vaikinai, jei aš buvo grupėje į grupes kas prasideda vardas
su daugiau nei čia, arba tas, kas yra gimtadienis yra sausio, vasario, kovo,
kas, kad yra veiksmingiau sukurti maišos lentelę.
Tai tiesiog sukurti kibirus, kad galimybę rūšiuoti elementus į
taip, kad jūs galite juos rasti lengviau.
Taigi tokiu būdu, kai man reikia rasti iš jūsų,
Aš neturiu ieškoti per kiekvieną savo pavardes.
Galiu būti kaip, oh, aš žinau, kad Danielle gimtadienis yra in--
AUDITORIJA: --April.
SPEAKER 1: Balandžio.
Taigi man atrodo, mano balandis kibiras, ir su bet sėkmės,
ji bus viena iš ten tik ir mano laikas buvo pastovus šia prasme,
o jei turiu ieškoti per visa krūva žmonių,
jis ketina imtis daug ilgiau.
Taigi maišos lentelės tikrai tik kibirai.
Lengvas būdas galvoti apie juos.
>> Taigi labai svarbus dalykas apie maišos lentelė maišos funkcija.
Taigi ką aš ką tik kalbėjau apie, pavyzdžiui, Jūsų pirmoji raidė jūsų vardas
ar jūsų gimtadienis mėnesį Šiuos pratimus
tikrai koreliuoja su maišos funkcija.
Tai tiesiog nuspręsti, kelias, kuris kaušas esi elemento eina į, gerai?
Taigi šiam pset galite ieškoti beveik bet maišos funkcija norite.
>> Neturi būti savo.
Yra keletas tikrai cool tie iš ten, kad padaryti visus crazy matematika rūšių.
Ir jei jūs norite, kad jūsų Korektorius super greitai,
Aš, be abejo, pažvelgti į vieną iš jų.
>> Tačiau taip pat yra paprastų, kaip Compute
iš žodžių, suma kaip Kiekviena raidė turi numerį.
Apskaičiuojamas sumą.
Kuris lemia kibirą.
Jie taip pat turi lengvai tuos, tiesiog kaip visi 's čia
visi B čia.
Bet kuris iš tų vienas.
>> Iš esmės, tai tiesiog jums pasakys, kuris masyvas indeksuoti jūsų elementas turėtų eiti į.
Tiesiog sprendžiant bucket-- tai viskas maišos funkcija.
Taigi čia mes turime pavyzdį, kuris yra tiesiog pirmoji raidė eilutę
kad aš tik kalbu.
>> Taigi, jūs turite tam tikrą maišos tai tik Raide savo styginių minus,
kuri duos jums kai skaičius tarp 0 ir 25.
Ir tai, ką jūs norite daryti yra įsitikinkite, kad tai yra
Jūsų maišos dydis table-- kiek kibirai yra.
Su daugeliu iš jų maišos funkcijos, jie
bus grąžinti vertybes, galėtų būti gerokai aukštesnis segmentų skaičių
kad jūs iš tikrųjų turi jūsų maišos lentelės,
todėl jums reikia padaryti Būtinai ir mod tie.
Priešingu atveju, jis ketina pasakyti, oh, tai turėtų būti kibirą 5000
bet jūs turite tik 30 kibirai Jūsų maišos lentelė.
Ir, žinoma, mes visi žinome, kad tai atves prie kai kurių kvailai klaidų.
Todėl įsitikinkite, kad mod dydžio jūsų maišos lentelės.
Cool.
Taigi susidūrimų.
Ar visi gerai iki šiol?
Mmhmm?
>> AUDITORIJA: kodėl jis grįžti tokį masinį vertę?
>> SPEAKER 1: Priklausomai nuo algoritmas kad jūsų maišos funkcija naudoja.
Kai kurie iš jų bus padaryti pamišęs daugyba.
Ir visa tai apie tai tolygus,
todėl jie ką nors tikrai beprotiškai kartais.
Tai viskas.
Ką nors?
Gerai.
>> Taigi susidūrimų.
Iš esmės, kaip jau minėjau, geriausiu atveju,
bet kibiras žiūriu į tai teks vienas dalykas,
todėl aš neturiu ieškoti ne visi, tiesa?
Aš tiek žinau, tai ten ar tai ne, ir tai, ką mes iš tikrųjų norime.
Bet jei mes turime dešimtis tūkstančių duomenų taškai ir mažiau nei už tą skaičių
kaušai, mes ketiname turėti Susidūrimai kur galiausiai kažkas
teks baigti su kibiras, kad jau turi elementą.
>> Taigi kyla klausimas, ką darome tokiu atveju?
Ką mes darome?
Mes jau turime kažką ten?
Ar mes tiesiog mesti jį iš?
>> Ne.
Mes turime išlaikyti abu.
Taigi būdas, kad mes paprastai padaryti tai, ką?
Kas yra duomenų struktūra mes tiesiog kalbėjomės apie?
AUDITORIJA: Susijęs sąrašas.
SPEAKER 1: susijęs sąrašas.
Taigi dabar, užuot kiekvienas iš jų kibirai tiesiog vieną elementą,
jis ketina būti susietas sąrašą elementus, kurie buvo maiša į jį.
Gerai, ar visi rūšies gauti šią idėją?
Nes negalėjome masyvą nes mes nežinome, kiek daug
ketinate būti ten.
Susijęs sąrašas leidžia mums turite tik tikslaus skaičiaus, kad
yra maiša į tą kibirą, tiesa?
>> Taigi linijinis zondavimo yra iš esmės tai idea--
tai vienas iš būdų kovoti su susidūrimo.
Ką jūs galite padaryti, tai, jeigu tai atvejis, uogų buvo maiša į 1
ir mes jau turime kažkas ten, jūs tiesiog
nesustoti, kol Apie pastebėtas tuščią lizdą.
Štai vienas iš būdų susitvarkyti.
Kitas būdas spręsti tai yra tai, ką mes ką tik
called-- susijęs sąrašas yra vadinamas grupavimo.
>> Taigi ši idėja veikia, jei Jūsų maišos lentelė manote
yra daug didesnis nei Jūsų duomenys nustatyti arba jei
nori pabandyti ir sumažinti Grupavimo kol jis būtinas.
Taigi vienas dalykas yra tiesinė Atidžiau akivaizdžiai reiškia
kad jūsų maišos funkcija yra ne visai taip pat naudinga,
nes jūs ketinate baigti naudojant Jūsų maišos funkcija, gauti iki taško,
Jūs linijinis zondas iki kai vieta, kuri yra prieinama.
Bet dabar, žinoma, nieko kita, baigiasi ten,
jūs ketinate turi ieškoti net toliau.
>> Ir ten yra daug daugiau paieška sąskaita, kad
eina į įvedusi elementą jūsų maišos lentelės dabar, tiesa?
Ir dabar, kai jūs einate ir pabandyti ir sužinoti uoga vėl, jūs ketinate maišos jį,
ir jis ketina pasakyti, oh, ieškoti kibirą 1,
ir ji nesiruošia būti į kibirą 1, todėl jūs
teks feed per šių poilsio.
Taigi kartais verta, tačiau daugeliu atvejų,
mes ketiname pasakyti, kad grupavimo, ką jūs norite daryti.
>> Taigi, mes kalbėjome apie tai anksčiau.
Gavau šiek prieš save.
Bet grupavimo iš esmės, kad kiekvienas savo maišos lentelė kibiras
yra tik susijęs sąrašas.
>> Taigi dar vienas būdas, arba daugiau techninės būdas, galvoti apie maišos lentelė
yra tai, kad tai tik masyvas Susietų sąrašus, kurie
kai rašote savo žodyną, ir bandote jį įkelti,
galvoju apie tai, kaip masyvas, susijusių sąrašus
bus daug lengviau jums inicijuoti.
>> AUDITORIJA: Taigi maišos lentelė turi iš anksto nustatytą dydį,
kaip [nesigirdi] kaušų?
>> SPEAKER 1: Teisė.
Todėl jis turi nustatytą skaičių kibirai, kad jūs determine--
kurie vaikinai turėtų nedvejodami žaisti.
Tai gali būti gana kietas pamatyti, kas vyksta
kaip galite pakeisti savo numerį Kaušų.
Bet taip, ji turi nustatyti skaičius kibirai.
Ką, Jūs galėsite taip daug elementų, kaip jums reikia
tai atskiras grupavimo kur jus susiejo sąrašus kiekviename segmente.
Tai reiškia, kad jūsų maišos lentelę bus lygiai dydis
kad jums reikia, kad ji būtų, ar ne?
Štai esmė susijusių sąrašus.
Cool.
>> Taigi kiekvienas Gerai ten?
Gerai.
Ak.
Kas atsitiko?
Tikrai dabar.
Atspėk kas manimi nužudyti mane.
>> Gerai, mes ketiname eiti į bando, kurie šiek tiek beprotiška.
Man patinka maišos lenteles.
Manau, kad jie tikrai gerai.
Bando yra cool, taip pat.
>> Taigi ar kas nors prisiminti, ką pabandyti tai?
Turėtumėte perėjo jis trumpai veikia paskaitos?
Ar pamenate natūra, kaip ji veikia?
AUDITORIJA: Aš tiesiog linksinčią kad mes eiti per jį.
SPEAKER 1: Mes eiti per jį.
Gerai, mes tikrai ketiname eiti per tai dabar yra tai, ką mes pasakyti.
>> AUDITORIJA: Štai už apsikeitimo medį.
>> SPEAKER 1: Taip.
Tai paieškos medis.
Nuostabus.
Taigi vienas dalykas, kad pranešimas čia yra, kad mes ieško individualių personažų
čia, tiesa?
>> Taigi prieš mūsų maišos funkcija, mes buvo ieško žodžių, kaip visumos,
ir dabar mes ieškome daugiau ne simbolių, tiesa?
Taigi, mes turime Maxwell čia ir Mendel.
Taigi, iš esmės try-- būdas galvoti apie tai, kad kiekvienas lygis čia
yra raidžių masyvas.
Taigi tai yra jūsų šakninis mazgas čia, tiesa?
Tai turi visus simbolius abėcėlė už kiekvieno žodžio pradžioje.
>> Ir tai, ką jūs norite daryti yra tarkim, Gerai, mes kai M žodį.
Mes ketiname ieškoti Maxwell, todėl mes einame į M. ir M taškų visuma
kitas masyvas, kur kiekvienas žodis, taip ilgai, kaip ten
yra žodis, kuris turi A kaip antruoju minėtuoju raštu
kol žodis, turi B, kaip antruoju minėtuoju raštu
jis turės žymiklį į kažkokį kitą masyvą.
>> Tikriausiai ne Žodis MP kažkas,
būdamas P padėtį tai masyvas, tai būtų tik NULL.
Jis sakydavo: Gerai, nėra žodžio , kuri po kurio M P, gerai?
Taigi, jei mes apie tai galvoti, kiekvienam viena iš šių mažesnių dalykų
iš tikrųjų yra vienas iš šių dideli masyvai nuo A iki Z.
Taigi, ką gali vienas iš dalykų, kad yra natūra iš pabandyti drobeko?
>> AUDITORIJA: daug atminties.
>> SPEAKER 1: Tai atminties ton, tiesa?
Kiekvienas iš šių blokų čia atstovauja 26 skyriai 26 elementų masyvą.
Taigi bando gauti neįtikėtinai erdvę sunkus.
>> Bet jie yra labai greitai.
Taip neįtikėtinai greitai, bet tikrai erdvę neefektyviai.
Rūšies turite išsiaiškinti iš kurių vienas nori.
Tai yra tikrai cool jūsų pset, tačiau jie užima daug atminties,
todėl jūs kompromisą.
Taip?
>> AUDITORIJA: Ar būtų galima įsteigti pabandyti ir tada
Kai turite visus duomenų į ją, kad jūs need--
Aš nežinau, jei tai būtų prasminga.
Buvau atsikratyti visų NULL simbolių, bet tada
jūs negalėsite them-- indekso
>> SPEAKER 1: Jūs vis dar reikia.
>> AUDITORIJA: - taip pat, kiekvieną kartą.
SPEAKER 1: Taip.
Jums reikia null simbolių leiskite jūs žinote, jei ten ne žodis ten.
Ben tu turi ką norite?
Gerai.
Gerai, kad mes ketiname eiti truputį daugiau
į technines smulkmenas, už pabandykite ir dirbti kaip pavyzdys.
>> Gerai, kad tai yra tas pats dalykas.
Kadangi susietoje sąrašą, mūsų pagrindinis rūšies of-- kas žodis, kaip reikia? -
kaip statybinis blokas buvo mazgas.
Be pabandyti, mes taip pat turime mazgas, bet jis skirtingai apibrėžiama.
>> Taigi, mes turime šiek tiek bool kad atstovauja ar žodžio iš tikrųjų
egzistuoja šioje vietoje, ir tada mes kai masyvas here-- arba, tiksliau,
tai rodyklė į masyvas 27 simbolių.
Ir tai yra dėl, šiuo atveju, tai 27-- aš tikras, kad visi esame kaip, palaukite,
yra 26 raidės abėcėlės.
Kodėl mes turime 27?
>> Taigi priklausomai nuo kaip jums įgyvendinti tai,
tai iš pset kad leidžiama kabutes.
Štai kodėl papildomas vienas.
Jūs taip pat turėsite kai atvejai null terminatorines
yra įtraukta kaip vienas iš simboliai, tai leidžiama,
ir tai, kaip jie patikrins pamatyti, jei ji Žodžio pabaiga.
Jei jus domina, patikrinkite Kevin vaizdo study.cs50,
taip pat turi Vikipedija gerų ištekliai ten.
>> Bet mes ketiname eiti per ką tik natūra kaip jums gali dirbti per pabandyti
jei jums suteikta viena.
Taigi, mes turime super paprasta, kad čia turi žodžiai "šikšnosparnis" ir "Zoom" jais.
Ir, kaip matome čia, tai mažai vietos čia
simbolizuoja mūsų bool kad sako, taip, tai yra žodis.
Ir tada tai turi DUK matricos simbolių, tiesa?
>> Taigi, mes ketiname eiti per rasti GPGB "šiame pabandyti.
Taigi pradėti viršuje, tiesa?
Ir mes žinome, kad b atitinka antra indeksas, antrasis elementas
šiame masyve, nes ir b.
Taigi maždaug antrasis.
>> Ir jis sako, gerai, kietas, atlikite kad į Kitas masyvas, nes jei mes prisimename,
tai nereiškia, kad kiekvienas iš jų iš tikrųjų sudaro elementas.
Kiekvienas iš šių masyvų reikšmę Rodyklė, tiesa?
Tai svarbus skirtumas, kad.
>> Aš žinau, tai ketina be-- bando yra tikrai sunku gauti dėl pirmą kartą,
todėl net jei tai antrą ar trečią kartą
ir jis vis dar geras iš tariamas sunku,
Pažadu, jei jūs einate žiūrėti trumpas rytoj,
tai turbūt padaryti daug daugiau prasmės.
Tai užtrunka daug virškinti.
Aš vis dar kartais esu kaip, palauk, kas pabandyti?
Kaip man tai naudoti?
>> Taigi, mes turime b šiuo atveju, kuris yra mūsų antras puslapis.
Jei mes turėjo, tarkim, c arba d arba bet kuri kita raidė,
turime žemėlapį, kad atgal į indeksą mūsų masyvas kad atitinka.
Taigi, mes imsis kaip rchar ir mes tiesiog atimti ne į žemėlapį ją 0-25.
Visi geri, kaip mes map mūsų personažus?
Gerai.
>> Taigi mes einame į antrąjį vienas ir mes matyti, kad taip, tai nėra NULL.
Galime pereiti prie šio kito masyvo.
Taigi mes einame į šį kito masyvo čia.
>> Ir mes sakome, gerai, dabar mes reikia pamatyti, jei yra čia.
Ar null arba daro iš tikrųjų eiti į priekį?
Taigi iš tikrųjų juda perduoti šiame masyve.
Ir mes sakome, gerai, t yra mūsų paskutinis laiškas.
Taigi mes einame į t tuo indeksą.
Ir tada mes judėti į priekį nes ten dar viena.
Ir tai vienas iš esmės sako, kad taip, jis sako, kad yra žodis here--
kad jei atlikite tai Kelias, turite atvykti
ne vienu žodžiu, kurį mes žinome, yra "šikšnosparnis".
Taip?
>> AUDITORIJA: Ar šis standartas turės kad kaip 0 ir indekso tada turėti bent 1 rūšiuoti
arba turėti ne, galų gale?
>> SPEAKER 1: Ne
Taigi, jei mes pažvelgti atgal į mūsų deklaracija čia, tai bool,
todėl savo elementas jūsų mazgas.
Taigi, tai nėra dalis masyvo.
Cool.
Taigi, kai mes baigsime žodį ir mes Šiuo masyvo, ką mes norime daryti
yra padaryti čekį tai žodis.
Ir šiuo atveju, jis sugrįš taip.
>> Taigi dėl šio rašto, mes žinome, kad "zoologijos" - mes žinome, kaip žmogui, kad "zoologijos sodas" yra žodis,
tiesa?
Bet pabandyti čia būtų sako, ne, tai ne.
Ir sakyčiau, kad, nes mes ji netaikoma kaip žodis čia.
Nors mes galime feed iki šio masyvo,
tai bandymas sakyčiau, kad ne, zoo nėra jūsų žodyną
nes mes turime ne paskirta kaip tokią.
>> Taigi vienas iš būdų tai padaryti that-- Oi, atsiprašau, tai vienas.
Taigi, šiuo atveju, "zoo" yra ne žodis, bet jis yra mūsų pabandyti.
Bet šis, sako, kad mes norime jį pristatyti žodį "pirtis", kas atsitinka
yra sekame through-- b, a, t.
Mes šiame masyve ir mes einame ieškoti val.
>> Šiuo atveju, kai mes ieškoti rodyklės ne h,
tai nukreipta NULL, gerai?
Taigi, jei tai aiškiai nukreipta į kitą masyvą,
Jūs prielaidą, kad visi žymekliai šiame masyve yra nukreipta į null.
Taigi šiuo atveju yra nukreipta h null todėl mes negalime nieko daryti,
todėl taip pat grįžti false "vonia" yra ne čia.
Taigi, dabar mes tikrai ketina pereiti
kaip mes turime iš tikrųjų pasakyti kad "zoologijos sodas" yra mūsų pabandyti.
Kaip mes įterpti "zoologijos" į mūsų pabandyti?
Taigi tuo pačiu būdu, kad mes su prasidejo mūsų susijęs sąrašas, pradedant šaknis.
Jei abejojate, pradėkite Šių dalykų šaknys.
>> Ir mes pasakyti, GERAI, z.
z egzistuoja, ir apie tai daro.
Taigi jūs judate į kitas jūsų masyvas, gerai?
Ir tada ant kito, mes sakome, gerai, nėra o egzistuoja?
Ji veikia.
Tai vėl.
>> Ir taip mūsų kito, mes pasakė, Gerai, "zoo" jau yra čia.
Visi mes turime padaryti, tai nustatyti tokios vienodos true, kad yra žodis ten.
Jei laikėsi viską iki prieš šį momentą,
tai žodis, todėl tiesiog nustatyti, kad jis lygus tokių.
Taip?
>> AUDITORIJA: Taigi tai daro reiškia, kad "ba" yra žodis, taip pat?
>> SPEAKER 1: Ne
Taigi, šiuo atveju, "ba" gautume čia mes sakytume tai žodis,
ir ji vis dar nebūtų.
Gerai?
Mmhmm?
>> AUDITORIJA: Taigi, kai jūs tai Žodis ir pasakyti "taip, tai
bus pateikta eiti į m?
>> SPEAKER 1: Taigi tai turi daryti with-- esate pakrovimo tai.
Jūs sakote, "zoo" yra žodis.
Kai jūs einate į check-- kaip, tarkim, jūs norite pasakyti,
reiškia "zoologijos sodas" yra šios žodyną?
Jūs tik ketina ieškoti "zoologijos" ir tada patikrinkite, ar tai žodis.
Jūs niekada pereiti iki m, nes tai ne
ką jūs ieškote.
>> Taigi, jei mes iš tikrųjų norėjo pridėti "vonioje" į šį pabandyti,
mes tą patį padaryti kaip mes padarėme su "zoologijos sodo"
išskyrus pamatytume, kad kai mes išbandyti ir gauti iki h, jis neegzistuoja.
Taigi, ką galima galvoti apie tai, kaip bando pridėti naują mazgas į objektą, susietą sąrašą,
todėl mums reikia pridėti kitą viena iš šių masyvų, pavyzdžiui, taip.
Ir tada, ką mes darome, mes tiesiog nustatykite h elementas šiame masyve nukreipta į tai.
>> Ir kas tada būtų, mes norime padaryti čia?
Pridėti jį lygi true nes tai žodis.
Cool.
Žinau.
Bando ne labiausiai jaudinantis.
Patikėkit manim, aš žinau.
>> Taigi vienas dalykas suvokti su bando, Aš pasakiau, kad jie labai veiksminga.
Taigi mes matėme tie, užima erdvę toną.
Jie rūšies painu.
Tai kodėl mes kada nors naudoti šiuos?
Mes naudojame juos, nes jie neįtikėtinai veiksminga.
>> Taigi, jei jūs kada nors ieškote iki Žodžiu, esate tik
apriboti žodžio ilgį.
Taigi, jei jūs ieškote Žodis yra ilgio penkių,
jūs tik kada nors teks padaryti dažniausiai per penkis palyginimų, gerai?
Taigi ji tampa iš esmės pastovus.
Kaip įdėti ir peržvalgos Iš esmės yra pastovus laiko.
>> Taigi, jei jūs kada nors gauti kažkas nuolat laiku,
tai taip gerai, kaip ji pasireiškia.
Jūs negalite gauti geriau nei pastovus laikas šių dalykų.
Taigi, kad yra vienas iš didžiuliai pliusai, bando.
>> Bet tai yra daug erdvės.
Taigi jūs rūšies turite nuspręsti kas daugiau jums svarbu.
Ir šiandienos kompiuterių, erdvė, bandymas gali trukti iki
gal neveikia Jūs, kad daug, bet gal
jūs susiduriame su kažkuo kad turi daug, daug daugiau dalykų,
ir pabandyti tiesiog nėra pagrįstas.
Taip?
>> AUDITORIJA: Palaukite, todėl jūs turite 26 raidės kiekvieną vieną?
>> SPEAKER 1: Mmhmm.
Taip, jūs turite 26.
Turite kai yra žodis žymeklį ir tada turite 26 rodykles į kiekvienas.
Ir jie point--
>> AUDITORIJA: Ir kas 26, jie kiekvienas turi 26?
>> SPEAKER 1: Taip.
Ir štai kodėl, kaip jūs galite pamatyti, ji plečiasi gana sparčiai.
Gerai.
Taigi, mes ketiname gauti į medžius, kurie Jaučiu, kaip yra lengviau ir tikriausiai
būti gražus leisti atsikvėpti nuo bando ten.
Taigi, tikiuosi, kad dauguma iš jūsų mačiau medį prieš.
Nepatinka gana tie lauke, kurį aš
Nežinau, ar kas nors nuvyko lauke neseniai.
Nuėjau obuolių skinti šį savaitgalį, ir oh my GOSH, tai buvo graži.
Aš nežinojau, lapai galėtų atrodyti, kad gana.
>> Taigi, tai tik medis, tiesa?
Tai tik keletas mazgas, ir jis atkreipia dėmesį į kitų mazgų krūva.
Kaip matote čia, tai yra rūšies kartojasi tema.
Mazgai, rodanti į mazgų rūšies Daugelio duomenų struktūrų esmė.
Tai tiesiog priklauso nuo to, kaip juos rodo vienas kitą
ir kaip mes feed per juos ir kaip mes
įterpti dalykus, nustato jų skirtingas savybes.
>> Taigi tik keletas terminologija, kuris aš naudojamas anksčiau.
Taigi esmė yra kokia yra pačiame viršuje.
tai kur mes visada prasideda.
Jūs galite galvoti apie tai, kaip galvos taip pat.
Bet medžiai, mes linkę nurodo kaip root.
>> Viskas, kas apačioje here-- ne labai, labai bottom--
laikomi lapai.
Taip eina kartu su Visa medis dalykas, tiesa?
Lapai ne jūsų medžio briaunų.
>> Ir tada mes taip pat turime ir pora terminai kalbėti apie mazgų atžvilgiu
viena su kita.
Taigi, mes turime iš tėvų, vaikai ir broliai ir seserys.
Taigi šiuo atveju yra 3 patronuojanti 5, 6 ir 7.
Taigi tėvai yra kokia yra vienas žingsnis virš kokia esi
nurodant, kad tik kaip šeimos medį.
Tikimės, kad tai yra viskas šiek tiek tiek daugiau intuityviai nei bando.
>> Broliai ir seserys yra bet kad turi pats tėvas, tiesa?
Jie tame pačiame lygyje čia.
Ir tada, kaip man buvo sakydamas vaikai tiesiog
kokia yra vienas žingsnis toliau tas mazgas, gerai?
Cool.
Taigi dvejetainis medis.
Ar kas nors rizikuočiau spėti į vieną iš dvejetainis medis charakteristikos?
>> AUDITORIJA: Max du lapai.
>> SPEAKER 1: Teisė.
Taigi max dviejų lapų.
Taigi šis prieš, mes turėjome šį vieną kad turėjo tris, bet dvejetainėje medžio,
turite du max vaikai per tėvų, tiesa?
Yra ir kita Įdomus bruožas.
Ar kas nors žino, kad?
Binary tree.
>> Taigi dvejetainis medis turės viską ant the-- šis yra ne sorted--
bet tam surūšiuoti dvejetainiu medžiu, viskas dešinėje
yra didesnė nei tėvų, ir viskas kairėje
yra mažesnis nei tėvų.
Ir kad buvo viktorina klausimas anksčiau, todėl gera žinoti.
Taigi, kaip mes nustatyti tai, vėl turime dar vieną mazgą.
Tai atrodo labai panašūs į tai, ką?
Dvigubai
>> Auditorija: Susijęs sąrašai
>> SPEAKER 1: dvigubas susijęs sąrašas, tiesa?
Taigi, jei mes pakeisti šią su ankstesnės ir naujos,
tai būtų dvigubai susiję sąrašas.
Tačiau šiuo atveju, mes iš tikrųjų turi kairę ir į dešinę, ir viskas.
Priešingu atveju, tai lygiai tas pats.
Mes vis dar turime elementą Jūs ieškote,
ir jūs tiesiog turite dvi rodykles ketina ką daryti toliau.
Taip, taip, dvejetainis paieškos medis.
Jei pastebime, viską čia yra didesnis than--
ar viskas iš karto į čia
yra didesnis nei, viskas čia yra mažesnis nei.
>> Taigi, jei mes ieškoti, ją turėtų atrodyti labai arti dvejetainis paieškos
čia, tiesa?
Išskyrus užuot ieškojus pusę masyvo,
mes tiesiog ieško arba į kairę, pusė arba dešinėje medžio.
Taigi ji tampa šiek tiek paprastesnis, manau.
>> Taigi, jei jūsų šaknys yra NULL, žinoma, ji tiesiog neteisinga.
Ir jei jis ten, be abejo, tai tiesa.
Jei tai mažiau nei mes ieškoti kairę.
Jei tai didesnis nei, mes ieškome teisę.
Tai yra būtent tai, kaip dvejetainiai paieškos, tiesiog kitoks duomenų struktūra
kad mes naudojame.
Vietoj masyvo tai tik dvejetainiai medžių.
>> Gerai, kaminai.
Ir taip pat, atrodo, kad mes gali turėti šiek tiek laiko.
Jei mes darome, Man malonu eiti per bet tai dar kartą.
Gerai, kad kaminai.
Ar kas nors prisiminti, ką stacks-- bet koks kamino savybės?
>> Gerai, kad dauguma iš mūsų, manau, valgyti pietūs halls--
kiek mes negali patinka.
Tačiau akivaizdu, galite galvoti apie rietuvės pažodžiui tik kaip padėklai kamino
arba daiktų rietuvė.
Ir tai, kas svarbu suprasti, kad tai
something-- charakteristika kurį mes vadiname tai by-- yra LIFO.
Ar kas nors žino, ką tai reiškia?
Mmhmm?
>> AUDITORIJA: Paskutinis in, first out.
>> SPEAKER 1: Teisė, paskutinė, first out.
Taigi, jei mes žinome, jei mes krovimas dalykus iki, lengviausias dalykas patraukti off--
o gal vienintelis dalykas, mes galime paimti off, jei mūsų šūsnis didelis enough--
yra tai, kad top elementas.
Taigi kokia buvo įtrauktas last-- kaip matome čia,
kokia buvo stumiama daugumoje recently-- yra
bus pirmas dalykas, kad mes nusibaigti, gerai?
>> Taigi, ką mes turime čia yra kitas Typedef konstrukto.
Tai tikrai tik patinka Avarijos metu į duomenų struktūrą,
taip yra daug mesta jums vaikinai.
Žinau.
Taigi dar vienas konstrukto.
Yay už struktūras.
>> Ir šiuo atveju, tai kai žymeklis į masyvą, kuris turi tam tikrą pajėgumų.
Taigi tai yra mūsų krūvą Čia, kaip ir mūsų tikrojo masyvo
Štai laikydami savo elementus.
Ir tada čia mes kai dydį.
>> Ir paprastai, kurį norite išsaugoti kūrinys, kaip didelis jūsų šūsnis
nes tai, ką jis ketina leisti jums reikia padaryti, tai, jei jūs žinote, dydis,
jis leidžia pasakyti, Gerai, aš ne pajėgumai?
Ar galiu pridėti ką nors daugiau?
Ir jis taip pat pasakys, kur Jūsų žetonų viršaus
yra, kad jūs žinote, ką jūs iš tikrųjų gali pakilti.
Ir tai iš tikrųjų vyksta būti šiek tiek daugiau aišku čia.
>> Taigi tiesioginio ryšio, vienas dalykas, jei jums kada nors įgyvendinti stumti,
kaip man buvo tiesiog pasakyti, jūsų kamino turi ribotą dydį, teisingai?
Mūsų masyvas turėjo tam tikrą pajėgumų.
Tai masyvas.
Tai fiksuoto dydžio, todėl reikia įsitikinkite, kad mes ne išleisti daugiau
į mūsų masyvas, nei mes iš tikrųjų turi erdvę.
>> Taigi, kai jūs kuriate stumti funkcija, pirmas dalykas, kurį jūs darote, yra tarkim, Gerai,
turiu vietos mano kamino?
Nes jei aš ne, atsiprašau, Negaliu laikyti savo elementą.
Jei aš, tuomet jūs norite saugoti ji tuo kamino viršuje, tiesa?
>> Ir tai, kodėl mes turime sekti mūsų dydžio.
Jei mes neturime sekti mūsų dydžio mes nežinome, kur įdėti.
Mes nežinome, kaip daug dalykų yra jau mūsų masyvas.
Kaip akivaizdžiai yra būdų kad gal galite tai padaryti.
Galite inicijuoti viską NULL ir tada patikrinkite, ar naujausia NULL
bet daug lengviau dalykas yra tiesiog pasakyti, GERAI, sekti dydį.
Kaip aš žinau, kad turiu keturis elementus mano matrica, todėl kitas dalykas
kad mes įdėti, mes ketina išlaikyti ne 4 indeksą.
Ir tada, žinoma, tai reiškia, kad Jūs sėkmingai pastūmėjo kažkas
ant savo krūvos, jūsų norite padidinti dydžio
taip, kad jūs žinote, kur yra tiek kad galite stumti daugiau dalykų.
>> Taigi, jei mes bandome pop kažkas nuo kamino,
kas gali būti pirmas dalykas, kad mes norime patikrinti?
Jūs bandote imtis kažkas ne savo kamino.
Ar tikrai ten kažkas jūsų kamino?
Ne.
Taigi, kas gali norime patikrinti?
>> AUDITORIJA: [nesigirdi].
SPEAKER 1: Patikrinkite dydžio?
Dydis.
Taigi, mes norime patikrinti, ar mūsų dydis yra didesnis už 0, gerai?
Ir jei ji yra, tada mes norime mažėjimą Mūsų dydis iki 0 ir grįžti, kad.
Kodėl?
>> Pirmuoju mes buvome stumdymas, mes seniai ji
ant dydžio ir tada atnaujinta dydžio.
Šiuo atveju, mes mažėjančio dydžio ir tada imtis jį išjungti, skynimas jį
iš mūsų masyvas.
Kodėl mes galime padaryti?
Taigi, jei aš turiu vieną dalyką mano kaminą, koks būtų mano dydis tuo momentu?
1.
>> Ir kur yra elementas 1 saugomi?
Kokiame puslapis?
AUDITORIJA: 0.
SPEAKER 1: 0.
Taigi šiuo atveju, mes visada reikia padaryti sure--
o ne grąžinant dydis minus 1, nes mes
žinome, kad mūsų elementas bus saugomi ne mažiau 1
kokia mūsų dydis, tai tiesiog rūpinasi juo.
Tai šiek tiek daugiau elegantiškas būdas.
Ir mes tiesiog Mažėja DUK dydis, o tada grįžti dydį.
Mmhmm?
>> AUDITORIJA: Spėju tiesiog apskritai, kodėl gi tai duomenų struktūra
būti naudingas?
>> SPEAKER 1: Tai priklauso nuo jūsų požiūriu.
Taigi kai kurie iš teoriją, jei dirbate with-- Gerai,
Aš noriu pamatyti, jei yra naudingi vienos kad yra naudinga daugiau nei už
CS.
Su kaminai, bet kuriuo metu jums reikia sekti kažką, kad
yra neseniai pridėta, kai jūs ketinate norite naudoti kamino.
>> Aš negaliu galvoti apie gerai pavyzdys, kad dabar.
Bet kai naujausi dalykas yra jums svarbiausi,
tai, kai stekas bus naudinga.
Bandau galvoti, jei ten gera už tai.
Jei aš manau, yra geras pavyzdys ir kitas 20 minučių, aš tikrai pasakys.
>> Bet apskritai, jei nėra nieko, kaip ir sakiau dauguma, kur naujausių
Svarbiausia, kad manimi kur kamino ateina į žaidimą.
Kadangi eilėse yra rūšies priešingai.
Ir visi mažieji šunys.
Ar tai nėra didysis, tiesa?
Aš jaučiuosi kaip aš turėtų Tiesiog Bunny vaizdo
pačiame viduryje skyrius jums vaikinai
nes tai yra intensyvus skirsnis.
>> Taigi eilė.
Iš esmės eilė kaip linija.
Jūs vaikinai aš tikiu naudojimas tai kasdien tiesiog patinka mūsų valgyklose.
Taigi, mes turime eiti į ir gauti mūsų padėklai, aš tikiu,
įsitikinkite, kad turite laukti eilėje servetėlės ​​ar jūsų maisto.
>> Taigi skirtumas čia kad tai yra FIFO.
Taigi, jei LIFO paskutinė buvo pirmasis out, FIFO yra first in, first out.
Taigi tai yra, kai ką įdėti ant pirmas tavo svarbiausia.
Taigi, jei jums buvo laukia į line-- Ar galite
įsivaizduokite, jei išvyko į eikite gauti naują iPhone
ir tai buvo kaminas kur paskutinis asmuo atitinka gavo jį pirmas,
žmonės žudo vieni kitus.
>> Taigi FIFO, mes visi labai gerai susipažinęs su realaus pasaulio čia
ir visa tai turi daryti su iš tikrųjų rūšies atkurti visą šią liniją
ir aptarnavimo struktūrą.
Todėl nors su kamino, mes turime stumti ir pop.
Su eilėje, turime Įtraukti į eilę ir dequeue.
Taigi į eilę iš esmės reiškia, padėkite jį ant nugaros,
ir dequeue priemonės imtis išjungti iš priekio.
Taigi, mūsų duomenų struktūra nėra šiek tiek daugiau sudėtinga.
Turime antrą dalyką sekti.
>> Taigi be galvos, tai būtent kamino, tiesa?
Tai yra tas pats, kaip struktūra kamino.
Vienintelis dalykas, skiriasi dabar yra mums turi šią galvutę, kuri Ką manote
ketina sekti?
>> AUDITORIJA: pirmasis.
>> SPEAKER 1: Teisė, Pirmas dalykas, kad mes įdėti į.
Mūsų eilėje galva.
Kas pirmas eilėje.
Gerai, taigi, jei mes į eilę.
Vėlgi, su bet kuriuo iš šie duomenų struktūros,
nes mes susiduriame su masyvo, mes turime patikrinti, ar mes turime erdvę.
>> Tai tipo kaip man pasakojo vaikinai, jeigu Jūs atidarote failą,
jums reikia patikrinti null.
Su bet kuriuo iš šių kaminai ir eiles, jums reikia
pamatyti, jei ten vietos, nes mes susijusius su fiksuoto dydžio masyvą,
kaip matome here-- 0, 1 visa iki 5.
Taigi, ką mes darome, kad tokiu atveju yra patikrinti pamatyti, jei mes vis dar turime vietos.
Mūsų dydis mažiau nei pajėgumų?
>> Jei taip, mes turime laikyti jį Uodega ir mes atnaujiname mūsų dydžio.
Taigi, ką gali uodega būtų šiuo atveju?
Tai nėra aiškiai parašytas.
Kaip mes saugome jį?
Ką uodega būtų?
>> Taigi galime eiti per šį pavyzdį.
Taigi tai yra jų dydis 6 masyvas, tiesa?
Ir mes turime dabar, mūsų dydis yra 5.
Ir kai mes įdėti ją, ji vyksta eiti į penktą indekso, tiesa?
Taigi sandėliuoja uodegos.
>> Kitas būdas rašyti uodega tiesiog būti mūsų masyvas prie rodiklio dydžio, tiesa?
Tai dydis 5.
Kitas dalykas ketina eiti į 5.
Cool?
Gerai.
Ji gauna šiek tiek sudėtingiau kai mes pradedame su maitinimu galvą.
Taip?
>> AUDITORIJA: Ar tai reiškia, kad mes būtų paskelbta matrica,
buvo penki elementai ilgai ir tada mes įtraukiame į jį?
>> SPEAKER 1: Ne
Taigi šiuo atveju, tai yra kaminai.
Tai būtų skelbiama kaip dydis 6 masyvo.
Ir šiuo atveju, mes tik vieną paliekamas.
>> Gerai, kad vienas dalykas yra tai atveju, jei mūsų galva yra ne 0,
tada mes tiesiog įdėti gali ne dydis.
Bet ji tampa šiek tiek sudėtingesnis nes iš tikrųjų, jie
neturite skaidrės už tai, kad aš ruošiuosi
atkreipti vieną, nes tai nėra taip paprasta, kai jums
pradėti atsikratyti daiktų.
Todėl nors su kamino Jūs tik kada nors
nerimauti, kokio dydžio yra pridėdami kažką,
su eilėje jums taip pat reikia padaryti Įsitikinkite, kad jūsų galva yra apskaitomas,
nes cool dalykas apie eiles yra tai, kad, jei esate ne pajėgumo,
jūs iš tikrųjų galite padaryti jį apvynioti.
>> Gerai, kad vienas thing-- oh, tai baisi kreida.
Vienas dalykas, apsvarstyti, yra tas atvejis.
Mes tik atlikti penki.
Gerai, kad mes ketiname sako vadovas yra čia.
Šis yra 0, 1, 2, 3, 4.
>> Galva ten, ir prašome turėti dalykų juose.
Ir mes norime pridėti kažką, ar ne?
Taigi, ką mes turime žinoti yra tai, kad vadovas yra visada
ketina perkelti šį kelią ir tada kilpa atgal aplink, gerai?
>> Taigi tai eilė yra vietos, tiesa?
Jis turi erdvę pačioje pradžioje, rūšies į tai priešais.
Taigi, ką mes turime padaryti, tai mes reikia apskaičiuoti uodegą.
Jei žinote, kad jūsų vadovas nepadarė, uodega
tik jūsų masyvas ne iš dydžio indeksas.
>> Bet iš tikrųjų, jei jūs naudojate eilę, jūsų galva tikriausiai nuolat atnaujinami.
Taigi, ką jums reikia padaryti, tai realiai apskaičiuoti uodegą.
Taigi, ką mes darome, yra ši formulė čia aš ruošiuosi let you
vaikinai manote apie, ir tada mes kalbame apie tai.
Taigi tai yra talpa.
>> Taigi tai tikrai jums, kaip tai padaryti.
Nes šiuo atveju, ką?
Mūsų pagrindinė yra 1, mūsų dydis yra 4.
Jei mes mod kad 5, gauname 0, kuris yra kur turėtume įrašyti šiuos duomenis.
>> Taigi tada į kitą atveju jei mes tai padaryti,
mes sakome, gerai, tegul dequeue kažką.
Mes dequeue tai.
Mes imti šį elementą, tiesa?
>> Ir dabar mūsų galva nukreipta čia ir mes norime pridėti dar vieną dalyką.
Tai iš esmės yra atgal mūsų linijos, ar ne?
Eiles gali apsukti masyvo.
Tai vienas iš pagrindinių skirtumų.
Stacks, jūs padaryti negalite.
>> Su eilėse, galite nes visi klausimai
yra tai, kad jūs žinote, ką Naujausias pridėta.
Kadangi viskas vyksta į papildomas tai į kairę kryptis, šiuo atveju,
ir tada apvynioti, galite toliau įgyvendinant naujus elementus
ne masyvo priekyje nes tai tikrai ne
masyvo priekyje nebėra.
Jūs galite galvoti apie pradžioje masyvas kaip kai jūsų galva yra iš tikrųjų.
>> Taigi ši formulė kaip jums apskaičiuoti savo uodegą.
Ar tai prasminga?
Gerai.
Gerai, dequeue, tada jus vaikinai 10 minučių
paklausti man kokių nors, patikslinančius klausimus norite, nes žinau, kad tai beprotiška.
>> Visos teisės, todėl toje pačioje way-- Aš nežinau, jei jus vaikinai pastebėjo,
bet CS yra visa informacija apie modelius.
Daiktai yra gana daug tas pats, tik su maža tweaks.
Taigi pats čia.
Mes turime patikrinti, ar mes iš tikrųjų turi kažką mūsų eilėje, tiesa?
Pasakykite, OK, mūsų dydis yra didesnis nei 0?
Cool.
>> Jei mes darome, tada mes judėti mūsų galvą, kuris yra tai, ką aš ką tik įrodė čia.
Mes nuolat atnaujiname mūsų galva, yra viena daugiau.
Ir tada mes Mažėja mūsų dydis ir grįžti elementą.
>> Yra daug daugiau betono kodas ant study.cs50.net,
ir aš labai rekomenduoju vyksta per jį, jei turite laiko,
net jei tai tik pseudo-kodas.
Ir jei jus vaikinai nori kalbėti per kad su manim vienas ant vieno, praneškite man,
žinoti.
Aš mielai.
Duomenų struktūros, jei vartojate CS 124, jums
žinau, kad duomenų struktūros gauti labai smagu ir tai yra tik pradžia.
>> Taigi, aš žinau, tai sunku.
Viskas OK.
Mes kovoti.
Aš vis dar.
Taigi nesijaudinkite, per daug apie ją.
>> Bet tai iš esmės tavo Avarijos metu į duomenų struktūras.
Žinau, kad tai labai daug.
Ar yra kas nors, kad mes norėtų eiti vėl?
Viskas, ką mes norime kalbėti per?
Taip?
>> AUDITORIJA: Dėl šios Pavyzdžiui, taip Naujas uodega yra 0 per tai?
SPEAKER 1: Taip.
AUDITORIJA: Gerai.
Taigi išgyvena, jūs turite 1 plius 4 or--
>> SPEAKER 1: Taigi jums buvo pasakyti, kai mes norime eiti tai padaryti dar kartą?
AUDITORIJA: Taip.
Taigi, jei jums buvo suprasti out-- kur yra Jūs skaičiuojant nuo tuo, kad uodega?
>> SPEAKER 1: Taigi uodega buvo in-- aš pakeitė.
Taigi šiame pavyzdyje čia, tai buvo masyvas mes ieškome, gerai?
Taigi, mes turime dalykus 1, 2, 3, ir 4.
Taigi, mes turime mūsų galva yra lygi 1 metu šis punktas, o mūsų dydis yra lygus 4
šiuo metu, ar ne?
>> Jūs visi sutinka, kad toks atvejis?
Taigi mes galvą plius dydis, kuris suteikia mums 5, ir tada mes mod 5.
Sulaukiame 0, kuris pasakoja, kad 0 yra kur yra mūsų uodega, kur mes turime erdvę.
>> AUDITORIJA: Kas dangtelis?
>> SPEAKER 1: talpa.
Atsiprašau.
Taigi tai yra jūsų masyvo dydis.
Taip?
>> AUDITORIJA: [nesigirdi] prieš mes grįžti elementą?
>> SPEAKER 1: Taigi mes einame galvos arba grąžinti momentą?
Taigi, jei mes perkelti vieną, Mažėja dydį?
Prašome palaukti.
Aš tikrai pamiršo kitą.
Never mind.
Nėra kito formulė.
Taip, kad jūs norėtumėte grįžti galva ir tada perkelti jį atgal.
>> AUDITORIJA: Gerai, nes šiuo taškas, galva buvo 0,
ir tada jūs norite grįžti 0, o indeksų tada galvos 1?
>> SPEAKER 1: Teisė.
Manau, kad yra dar vienas formulė lyg tai.
Aš neturiu ją viršuje, kaip mano galva Nenoriu, kad turėtumėte klaidingą vieną.
Bet manau, kad tai visiškai galioja iki tarkim, Gerai, nelaikykite šio element-- kokia
galvutės elementas is-- Mažėja jūsų dydis, judinkite galvą virš, ir grąžinimas
kad ir ką tai elementas.
Štai puikiai tinka.
Gerai.
Jaučiu, tai nėra kaip most-- nesate
ketina išeiti iš čia kaip, taip, aš žinau, bando.
Aš jį visą.
Tai gerai.
Pažadu.
Bet duomenų struktūros yra kažkas, kad ji užima daug laiko priprasti prie.
Bene sunkiausiai dalykų, manau, į paskaitas.
>> Taigi jis tikrai užima kartojimas ir ieško at-- I
nelabai žinau, susijusius sąrašus kol aš per daug su jais,
tuo pačiu būdu, kad aš ne tikrai suprasti patarimų
kol aš turėjo mokyti jį dviems metų ir padaryti savo pačių psets su juo.
Tai užtrunka daug pakartojimu ir daug laiko.
Ir galiausiai, tai kokios spustelėkite.
>> Tačiau kol kas, jei turite geras aukšto lygio specialistų supratimą, kas
tai padaryti, jų privalumus ir cons-- kuris yra tai, ką
mes tikrai linkę akcentuoti, ypač intro kursą.
Kaip, kodėl mes naudojame pabandykite per masyvą?
Kaip, kas yra teigiami ir negatyvai, apie kiekvieną tų?
>> Ir suprasti kompromisus tarp kiekvienos iš šių struktūrų
yra tai, kas daug svarbiau dabar.
Gali būti vienas iš proto klausimas ar du, kad yra
Paprašysiu jus įgyvendinti stumti ar įgyvendinti pasipriešinimo arba į eilę ir dequeue.
Tačiau didžioji dalis, kurios, kad aukštesnio lygio supratimą ir daugiau
iš intuityvus čiupti yra svarbesnis nei iš tikrųjų
kad galėtų ją įgyvendinti.
>> Tai būčiau tikrai nuostabus, jei jūs visi gali eiti ir eiti įgyvendinti pabandyti,
bet mes suprantame, kad tai nebūtinai Tinkamiausias dalykas dabar.
Bet jūs galite savo pset, jei norite , tada jūs gausite praktiką,
ir tada gal jums tikrai suprasti.
Taip?
>> AUDITORIJA: Gerai, kad kuris iš jų yra mes reiškė naudoti į pset?
Ar man reikia naudoti vieną iš jų?
SPEAKER 1: Taip.
Taigi jūs turite savo pasirinkimą.
Spėju, šiuo atveju, mes galime kalbėti apie pset dalelę
nes išbėgau pro juos.
Taigi jūsų pset, turite pasirinkimas bando ar hash lenteles.
Kai kurie žmonės bando ir naudoti žydėti filtrai,
bet kurie techniškai nėra teisinga.
Dėl jų tikimybinis pobūdis, jie klaidingai teigiami, kartais.
Jie kietas žvilgsnis į, nors.
Labai rekomenduoju ieškote į juos bent.
Bet jūs turite savo pasirinkimą tarp maišos lentelė ir pabandyti.
Ir kad tai bus kur Jūs kraunate savo žodyną.
>> Ir jums reikia pasirinkti Jūsų maišos funkcija,
jums reikia pasirinkti, kiek kaušai turite, ir jis gali varijuoti.
Pavyzdžiui, jei turite daugiau kibirai, gal jis bus paleisti greičiau.
Bet gal jūs eikvoti daug erdvės, kad taip, nors.
Turite suprasti jį.
Mmhmm?
>> AUDITORIJA: Jūs sakėte, prieš tai mes galime naudoti kitų maišos funkcijas,
kad mes neturime į sukurti maišos funkcija?
>> SPEAKER 1: Taip, tiesa.
Taigi pažodžiui jūsų maišos funkcija, kaip google "maišos funkcija"
ir surasti kai cool tie.
Jūs nesate tikimasi pastatyti jūsų pačių maišos funkcijos.
Žmonės praleidžia savo tezės apie šiuos dalykus.
>> Taigi nesijaudinkite apie pastato savo.
Ieškoti vieną internete pradėti.
Kai kurie iš jų, jūs turite manipuliuoti truputį
įsitikinti, ar grąžinimo tipai atitikmenys ir Papuošalą, todėl iš pradžių,
Norėčiau rekomenduoti naudojant kažką tikrai paprasta, kad gal tiesiog
maišų pirmąją raidę.
Ir tada, kai jūs turite, kad darbas, įtraukiant aušintuvas maišos funkcija.
Mmhmm?
>> AUDITORIJA: Ar bandyti būti arba efektyvus, bet tik sunkiau, like--
>> SPEAKER 1: Taigi pabandyti, manau, yra intuityviai sunku įgyvendinti
bet yra labai greitas.
Tačiau užima daugiau vietos.
Vėlgi, jūs galite optimizuoti tiek tiems, įvairiais būdais ir yra būdų to--
AUDITORIJA: Kaip mes rūšiuojami tai?
Ar tai matter--
>> SPEAKER 1: Taigi jūs surūšiuoti įprastu būdu.
Jūs ketinate būti rūšiuojami dizainas.
Nesvarbu, kaip jūs darote, jūs norite įsitikinkite, kad jis, kaip elegantiškas, nes jis gali būti
ir tokia veiksminga, kaip jis gali būti.
Tačiau jei jūs pasirinksite pabandyti arba maišos lentelė, taip ilgai, kaip ji veikia,
mes džiaugiamės, kad.
Ir jei jūs naudojate kažką, kad maišos pirmame laiške, tai gerai,
kaip gal kaip dizaino atžvilgiais.
Mes taip pat pasiekė taškas šiame semester--
Aš nežinau, jei jums vaikinai noticed-- jei esate
pset rūšių mažėti šiek tiek dėl dizaino ir Papuošalą,
kad puikiai gerai.
Tai vis iki taško, kur yra jūsų programos darosi sudėtingesnis.
Yra daugiau vietų galite pagerinti.
>> Taigi, tai visiškai normalu.
Tai nereiškia, kad jūs esate daro blogiau savo pset.
Tai tiesiog mes yra sunkiau jums dabar.
Taigi kiekvienas manimi jausmas.
Aš tiesiog surūšiuoti visus psets.
Aš žinau, visi yra jausmas.
>> Taigi nereikia nerimauti, kad.
Ir jei turite kokių nors klausimų apie tai išankstiniai psets ar būdų, kaip galite pagerinti,
Bandau ir komentuoti konkrečių vietos, bet kartais tai vėlai
ir aš pavargsta.
Ar yra kitų dalykų, apie duomenų struktūros?
Aš tikiu, kad jūs vaikinai nelabai noriu kalbėti apie jų nebėra,
bet jei yra, aš esu laimingas, kad eiti per juos, taip pat nieko
iš paskaitos tai praeities savaitę ar praeitą savaitę.
>> Žinau, praeitą savaitę buvo viskas peržiūra, todėl mes galėjo praleisti per tam tikrą peržiūros
iš paskaitos.
Kitus klausimus galiu atsakyti?
Gerai, gerai.
Na, vaikinai išeiti 15 minučių anksčiau.
>> Tikiuosi, kad tai buvo pusiau naudinga bent ir aš pamatysiu jus vaikinai kitą savaitę,
ar ketvirtadienis darbo valandomis.
Ar yra pareikalavimas užkandžiai kitą savaitę, tai dalykas?
Nes aš pamiršau saldainiai šiandien.
Atvedžiau saldainiai paskutinį savaitę, bet tai buvo Kolumbo diena,
tad tikrai buvo kaip šešių žmonių, kurie turėjo keturis maišelius saldainių sau.
Galiu duoti pliūpsniais dar kartą, jei norite.
Pliūpsniais?
Gerai, gerai skamba.
Iki pasimatymo, vaikinai.