[Muusika mängimine] SPEAKER 1: Olgu. Igaühel on hea meel tagasi lõik. Loodan, et te kõik olete edukalt toibunud oma viktoriin eelmisel nädalal. Tean, et see on natuke hull aegadel. Nagu ma ütlesin enne, kui sa oled jooksul standardhälve, tõesti ei muretse selle pärast, eriti jaoks vähem mugav sektsioonis. See, kui sa peaksid olema. Kui sa tegid hästi, siis awesome. Kiitus teile. Ja kui sa tunne, mida vaja natuke rohkem abi, palun julgelt jõuda läbi ükskõik TF. Me kõik oleme siin, et aidata. 

Sellepärast me õpetame. Sellepärast ma olen siin igal esmaspäeval teile poisid ja tööajal neljapäeviti. Nii et palun andke mulle teada kui olete mures midagi või kui seal on midagi viktoriin et sa tõesti tahaks tegeleda. 

Nii päevakorda täna kõike andmestruktuurid. Mõned neist on lihtsalt saab olema lihtsalt sulle tutvustatakse neid. Sa ei pruugi kunagi ellu neid selles klassis. Mõned neist te, nagu teie speller pset. 

Sa pead oma valikut vahel hash tabeleid ja proovib. Nii et me kindlasti läheb üle need. See saab olema kindlasti mitu liiki kõrgetasemelise lõik täna, kuigi sest seal on palju neid, ja kui meil läks rakendamise üksikasjad kõik need, me ei teeks isegi läbi saama ahelloendid ja võib-olla natuke hash tabeleid. 

Nii kannavad minuga. Me ei kavatse tegema nii palju kodeerimise seekord. Kui teil on küsimusi selle kohta või sa tahad seda näha rakendatud või proovida seda ise, Ma kindlasti soovitada läheb study.cs50.net, mis on näited kõiki neid. See on teil minu Powerpoint koos lisades, et me kalduvad kasutama samuti mõned programmeerimine harjutused, eriti asjad nagu ahelloendid ja binaarne puud korstnad ja märguannetele. Nii et veidi kõrge tase, mis oleks tore kutid. 

Nii, et me alustada. Ja ka yes-- viktoriine. Ma arvan, et enamik teist, kes on minu jaos on teie viktoriinid kuid keegi tuleb, või mingil põhjusel sa ei, nad on siin ees. 

Nii ahelloendid. Ma tean, et selline läheb tagasi enne viktoriini. See oli nädal enne et me saime selle. Aga sel juhul, me lihtsalt minna natuke põhjalikumalt. 

Nii et miks võiks me valime seotud nimekirja üle massiivi? Mis eristab neid? Jah? 

Sihtrühm: võib samuti laiendada seotud list versus massiiv on fikseeritud suurus. SPEAKER 1: Õigus. Massiiv on fikseeritud suurus arvestades seotud nimekirja on muutuv suurus. Nii et kui me ei tea, kuidas palju me tahame säilitada, ahelloend annab meile suur viis seda teha, sest me ei saa lihtsalt lisada teise sõlme ja lisada kohta teise sõlme ja lisada teise sõlme. Aga milline võiks olla kompromiss? Kas keegi mäletab, kompromiss vahel massiivid ja ahelloendid? Mmhmm? 

Sihtrühm: Sa pead läbida kogu tee kaudu seotud nimekirja leida element nimekirja. Massiivi, saate lihtsalt leida element. 

SPEAKER 1: Õigus. Nii arrays-- 

Sihtrühm: [kuuldamatu]. 

SPEAKER 1: Mis massiivid meil mida nimetatakse muutmälu. Tähendab, et kui me tahame, mis on kunagi viies koht nimekiri või viies koht meie massiiv, saame lihtsalt haarata. Kui see on seotud nimekirja, meil itereerima läbi, eks? Nii tutvumise element massiiv on konstantne ajal arvestades, ahelloend see oleks tõenäoliselt lineaarne aeg, sest võib-olla Meie element on kogu tee lõpus. Meil on otsida kõike. Nii et kõik need andmed struktuuride me läheme kulutama veidi rohkem aega, Millised on plussid ja negatiivid. Kui pruugi me tahame kasutada ühte teisele? Ja see on omamoodi suurem asi ära võtta. 

Nii et meil on siin mõiste sõlme. See on nagu üks element meie seotud nimekirja, eks? Nii et me oleme kõik tuttavad meie typedef structs, mis me läksime üle läbivaatamine viimast korda. See oli põhimõtteliselt ainult luua teise andmetüübi et saaksime kasutada. 

Ja sel juhul, see on mingi sõlme et hoiab mõned täisarv. Ja mis siis on teine ​​osa siin? Keegi? 

Sihtrühm: [kuuldamatu]. 

SPEAKER 1: Jah. See on kursor järgmisele sõlme. Nii et see peaks tegelikult olema siin. See on viit tüüpi sõlme järgmine asi. Ja see, mida nad hõlmab meie sõlme. Külm. 

Olgu, nii otsingumootori, nagu me olime lihtsalt ütlen enne küljest, kui sa oled läheb läbi otsida, sa pead tegelikult itereerima läbi oma seotud nimekirja. Nii et kui me otsime arv 9, me hakkaks meie peas ja mis juhib meid alguses meie seotud nimekirja, eks? Ja me ütleme, OK, kas see sõlme sisaldama number 9? Ei? 

Olgu, minge järgmise üks. Jälgi seda. Kas see sisaldab number 9? Ei. Jälgi järgmise üks. 

Nii et me peame tegelikult itereerima meie seotud nimekirja. Me ei saa lihtsalt minna otse, kui 9 on. Ja kui te poisid tegelikult tahavad vaata mõned pseudo-kood seal. Meil on mõned allalaadimisfunktsioon siin mis võtab in-- mida see võtta? Mis sa arvad? Nii lihtne. Mis see on? Sihtrühm: [kuuldamatu]. SPEAKER 1: number otsime. Õigus? Ja milline oleks see vastama? See on kursor? 

Sihtrühm: sõlme. 

SPEAKER 1: sõlme nimekirja et me vaatame, eks? Nii et meil on mõned sõlmed on pointer siin. See on punkt, mis läheb tegelikult kordavad meie nimekirja. Seame see võrdne nimekirja sest see on just millega see võrdne alustada meie seotud nimekirja. 

Ja kuigi see ei ole NULL, kui meil on veel asju meie nimekirjas, kontrollige, kas see sõlm on arvu me otsime. Tagasi tõsi. Vastasel korral ajakohastab seda, eks? 

Kui see on NULL, me väljuda meie samas silmus ja tagasi vale sest see tähendab, et me ei ole leidnud. Kas igaüks saada, kuidas see toimib? OK. 

Nii sisestamist, siis on kolm erinevat viisi. Võite ülaloleva, saate lisada ja te saate lisada assortii. Sel juhul me oleme kavatse teha ülaloleva. Kas keegi teab, kuidas need kolmel juhul võivad olla erinevad? 

Nii ülaloleva tähendab, et paned see on ees oma nimekirja. Nii et see tähendaks, et ükskõik mida teie sõlm on, ükskõik, milline väärtus on, sa lähed pane see siin ees, eks? See saab olema esimene element nimekirjas. 

Kui lisada seda, et see läheb minna tagasi oma nimekirja. Ja lisada assortii tähendab, et sa oled panevad tegelikult paika kus ta hoiab oma seotud nimekirja sorteerida. Jällegi, kuidas kasutada neid ja kui te kasutate need varieeruvad sõltuvalt teie puhul. Kui seda ei ole vaja sorteerida, ülaloleva kipub olema, mida enamik inimesi kasutada, sest teil ei ole läbima kogu nimekirja leida end lisada seda, eks? Sa võid jääda see õigus. 

Nii et me läheme läbi sisestamise 1 kohe. Nii et üks asi, mida ma lähen väga soovitada selle pset on juhtida asju teha, nagu alati. See on väga oluline, et teil uuendada Sinu suunanäitajaks õiges järjekorras sest kui sa neid uuendada veidi rikkis, sa lähed lõpuks kaotanud osa oma nimekirja. 

Nii näiteks, sel juhul oleme räägib pea lihtsalt punkt 1. Kui me just seda, et salvestamata see 1 me ei tea, mida 1 tuleks viidata nüüd sest me oleme kaotanud, mida pea osutas. Nii et üks asi on meeles pidada kui sa teed ülaloleva on päästa mis head punktid esimene, siis ümber jaotada see ja seejärel ajakohastada mida teie uus sõlm tuleks viidata. Sel juhul see on üks viis seda teha. 

Nii et kui me oleksime teinud seda nii kus me lihtsalt ümber jaotada pea, me kaotame põhiliselt meie kogu nimekiri, eks? Üks viis seda teha on, et 1 punkt Järgmine, ja siis on pea punktist 1. Või saate teha selline nagu ajutine ladustamine, mis ma rääkisin. 

Aga ümberjagamise oma suunanäitajaks õiges järjekorras saab olema väga, väga oluline, et see pset. Muidu sa lähed on hash tabeli või proovida, mis on lihtsalt saab olema ainult osa sõnad, mida te tahad ja siis you're-- mmhmm? Sihtrühm: Mis oli ajutine ladustamise asi, mida sa rääkisid? SPEAKER 1: ajutine ladustamine. Nii et põhimõtteliselt veel kuidas sa võiksid seda teha on hoida pea midagi, nagu pange see ajutine muutuja. Määra see 1 ja seejärel värskendage 1 punkti mis iganes pea kasutada osutada. Nii on ilmselt rohkem elegantne, sest sa ei pea ajutise väärtust, kuid lihtsalt pakkuda veel üks võimalus seda teha. Ja me tegelikult ei ole mõned koodi selle eest. Nii ahelloend me tegelikult on mingi kood. Nii lisada siin, see on lisades nende ette. Nii et see sisestab selle juht. 

Nii et esimene asi, mida vaja luua endale sõlme, muidugi, ja kontrollige NULL. Alati hea. Ja siis pead määrama väärtused. Iga kord, kui loote uue sõlme, siis ei tea, mida see osutab teisele, nii soovid täita see tühjaks. Kui see lõpuks osutades midagi muud, siis saab ümber jaotada ja see on hea. Kui see on esimene asi, nimekirjas, tuleb juhtida tühjaks, sest see on loendi lõppu. 

Siis lisada see näeme siin on määrates järgmise väärtus meie sõlme olla mis iganes pea, mis on see, mis meil oli siin. See, mida me just tegid. Ja siis me määrates pea punkti meie uus sõlm, sest mäletan, Uus on mõned osuti tipu ja see on täpselt see, mida head on. See on täpselt, miks me on see nool Juurdepääsumeetodid. Cool? Mmhmm? 

Sihtrühm: Kas me peame initsialiseerida uus kõrval NULL esimene, või saame lihtsalt initsialiseerida see pea? 

SPEAKER 1: Uus järgmine peab olema NULL alustada sest sa ei tea, kus see saab olema. Ka see on selline lihtsalt meeldib paradigma. Sa seadsid ta võrdne NULL lihtsalt teha Veenduge, et kõik teie alused on hõlmatud Enne tee midagi sihtotstarbe et sa oled alati tagatud, et see osutades, mille väärtus versus nagu prügi väärtus. Sest, jah, anname uus järgmisel automaatselt, aga see on rohkem nagu Hea tava initsialiseerida see niimoodi ja siis ümber jaotada. 

OK, nii et kahekordselt ahelloendid nüüd. Mida me arvame? Mis on erinev kahekordselt ahelloendid? 

Nii et meie ahelloendid, saame liikuda ainult ühes suunas, eks? Meil on ainult järgmine. Me saame minna ainult edasi. 

Mis kahekordselt seotud nimekirja, saame ka tagasi liikuda. Nii et me ei ole mitte ainult number, et me tahame säilitada, meil on, kus ta märgib, et järgmisel ja kus me lihtsalt tulid. Nii võimaldab see mõned paremad läbipääsusüsteemid. 

Nii kahekordselt seotud sõlmed, väga sarnased, eks? Ainus erinevus on see nüüd on järgmine ja eelmine. See on ainus erinevus. 

Nii et kui me ülaloleva või append-- me ei ole mingit kood selle üles siin-- aga kui sul proovida ja sisestada, seda tähtsam on teil on vaja teha et olete määrates nii oma eelmise ja oma Järgmine pointer õigesti. Nii et antud juhul, siis oleks mitte ainult initsialiseerida kõrval, sa initsialiseerida eelmine. Kui me eesotsas nimekirja, me ei oleks ainult pea võrdne uue, aga meie uus eelmisel peaks juhtida pea, eks? 

See on ainus erinevus. Ja kui sa tahad rohkem praktikat need lingitud nimekirjad, mille paigaldamisel kustutamist, kus insert arvesse assortii nimekirja palun vaadake study.cs50.net. Seal on hunnik suurepäraseid harjutusi. Ma väga soovitada neile. Soovin, et meil oli aega minna nende kaudu kuid seal on palju andmestruktuurid läbi saama. 

OK, nii et hash tabeleid. See on tõenäoliselt kõige kasulikku bitti oma pset siin, sest sa lähed olema rakendamise üks neist, või proovida. Ma tõesti nagu hash tabeleid. Nad on päris lahe. 

Ühesõnaga, mida juhtub, on hash tabelit on see, kui me tegelikult vajame kiiret lisamise, kustutamise ja otsimise. Need on asjad, mida me oleme prioriteediks on hash tabelis. Nad saavad päris suur, kuid nagu me näeme, kus katseid on asju, mis on palju suuremad. 

Aga põhimõtteliselt on kõik hash Tabelis on räsifunktsioon mis ütleb teile, mida kopp panna iga Teie andmed iga oma elementi. Lihtne võimalus mõelda hash tabelit on see, et see on lihtsalt ämbrid asju, õige? Nii et kui te sorteerimine asju nagu esimene täht tema nime, see on selline nagu hash tabelis. 

Nii et kui ma rühm kutid on rühmadesse kes on nimi algab koos siin, või kes iganes sünnipäev on jaanuaris, veebruaris, märtsis, mis iganes, mis on tõhusalt luua hash tabelis. See on lihtsalt luua ämbrid et sa saad oma elemendid nii et võite leida neile lihtsamaks. Nii et sel viisil kui ma vajan leida üks teist, Ma ei pea otsima läbi iga oma nime. Ma võin olla nagu, oh, ma tean, et Danielle sünnipäev on in-- Sihtrühm: --April. SPEAKER 1: aprillis. Nii et ma vaatan minu aprill kopp, ja õnne, ta pead olema ainuke sinna ja minu ajal oli pidev selles mõttes, arvestades, et kui ma pean vaatama läbi terve hulk inimesi, see läheb palju kauem aega. Nii hash tabelid on tõesti ainult ämbrid. Lihtne võimalus mõelda neid. 

Seega on väga oluline asi hash tabel on hash funktsiooni. Nii et asi, mida ma lihtsalt rääkisime, nagu oma esimese kirja oma eesnimi või oma sünnipäeva kuul Need on ideed, mis tõesti korreleeruvad hash funktsiooni. See on lihtsalt viis, kuidas otsustada, mis kopp oled element läheb, eks? Nii see pset, võid otsida päris palju tahes hash funktsiooni, kui soovite. 

Ei pea olema oma. On mõned väga lahe ones out seal, et teha igasuguseid hull matemaatika. Ja kui sa tahad teha oma õigekirja super kiire, Ma tahaksin kindlasti vaata ühte nendest. 

Kuid on ka lihtsaid, nagu arvutama summa sõnadega, nagu iga täht on mitmeid. Arvuta summa. See määrab ämber. Neil on ka lihtne need, mis on nagu kõik on siin, kõik B on siin. Iga üks neist. 

Põhimõtteliselt, see lihtsalt ütleb, milline massiivi indeks element peaks minema. Lihtsalt otsustada bucket-- see kõik räsifunktsioon on. Nii et siin on meil tegemist näitega, mis on lihtsalt esimene täht string et ma lihtsalt räägin. 

Nii et teil on mõned hash see on alles esitäht oma string miinus, mis annab teile mõned number vahemikus 0 ja 25. Ja mida sa tahad teha, on veenduge, et see on suurust oma hash table-- kui palju ämbrid on. Paljude nende räsifunktsioonid, nad kavatse naasta väärtusi, mis võiksid olema palju suurem hulk ämbrid et sa tegelikult Teie hash tabelit, nii et sa pead tegema kindel ja mod need. Vastasel juhul läheb öelda, oh, see peaks olema ämber 5000 aga sul on ainult 30 ämbrid oma hash tabelis. Ja muidugi, me kõik teame, mis on läheb kaasa mõned hull vigu. Seega veenduge, mod poolt suurust oma hash tabelis. Külm. Nii kokkupõrkeid. Kas kõik head nii palju? Mmhmm? 

Sihtrühm: Miks seda tagasi sellise suure raha? 

SPEAKER 1: Sõltuvalt algoritmi et teie hash funktsiooni kasutab. Mõned neist teevad hull paljunemist. Ja see kõik on umbes saada ühtlane jaotus, nii nad teha mõned tõesti hull asju mõnikord. See on kõik. Veel midagi? OK. 

Nii kokkupõrkeid. Põhimõtteliselt, nagu ma juba ütlesin, parimal juhul stsenaariumi iga ämber vaatan on läheb on üks asi, nii et ma ei pea vaatama kõik, eks? Ma kas tead, et see on või on ei, ja see, mida me tegelikult tahame. Aga kui meil on kümneid tuhandeid andmepunkti ja väiksem number kopad, me lähed on kokkupõrked, kus lõpuks midagi läheb on sattuda kopp, mis on juba element. 

Seega on küsimus selles, mida me teeme sel juhul? Mida me teeme? Meil on juba midagi seal? Kas me lihtsalt visata see välja? 

Ei. Me peame neid mõlemaid. Niisiis, kuidas me tavaliselt teha, mis on mis? Mis on andmestruktuur me lihtsalt rääkisime? Sihtrühm: seotud nimekirja. SPEAKER 1: seotud nimekirja. Nüüd, selle asemel iga ämbrid lihtsalt on üks element, see saab sisaldada seotud nimekirja elemendid, mis olid räsitud ta. OK, ei igaüks omamoodi saada, et idee? Kuna me ei saanud massiivi sest me ei tea, kui palju ei kavatse olla seal. Ahelloend võimaldab meil just täpne arv, mis on räsitud sellesse ämbrisse, eks? 

Nii lineaarne Mõõtmine toimub põhimõtteliselt see idea-- see on üks võimalus tegeleda kokkupõrget. Mida saab teha, on see, kui selles juhul marja oli räsitud arvesse 1 ja meil on juba midagi seal, sa lihtsalt Jätkab alla, kuni leiad tühja pesa. See on üks viis, kuidas sellega hakkama. Teine viis lahendada see on, mida me lihtsalt nimetaks seotud nimekiri nimetatakse ühendamine. 

Nii et see idee töötab, kui Sinu hash tabelit te arvate on palju suurem kui Oma andmete määrata või kui te tahan proovida ja minimeerida ühendamine kuni see on absoluutselt vajalik. Nii et üks asi on lineaarne katsetamine tähendab ilmselt et teie räsifunktsioon ei ole päris nii kasulik sest sa lähed lõpuks kasutavad Sinu hash funktsiooni, saada kuni punktini, sa lineaarne sondi alla Mõnes kohas, mis on saadaval. Aga nüüd muidugi midagi muud, mis jõuab sinna, sa lähed pea Otsige veelgi allapoole. 

Ja seal on palju rohkem otsi kulu, mis läheb sisestanud element Teie hash tabelit nüüd, eks? Ja nüüd, kui lähete ja püüda leida mari jälle sa lähed hash see, ja see läheb öelda, oh, vaata ämber 1 ja ta ei kavatse olla kopp 1, nii et sa oled läheb on läbida kogu ülejäänud neid. Nii et see on mõnikord kasulik, kuid enamikel juhtudel me ei kavatse öelda, et ühendamine on see, mida sa teha tahad. 

Nii et me rääkisime sellest juba varem. Sain veidi enne ise. Aga ühendamine toimub põhiliselt, et iga ämber teie hash tabelit on lihtsalt seotud nimekirja. 

Nii et veel üks viis või rohkem tehnilisi Nii et mõtle hash tabelit on see, et see on lihtsalt massiivi Seotud nimekirjad, mis kui sa kirjutad oma sõnastik ja sa üritad seda laadida, mõtled seda massiivi ahelloendid on palju lihtsam teile käivitumist. 

Sihtrühm: Nii hash tabelit on määratud mõõtmetega, nagu [kuuldamatu] kopad? 

SPEAKER 1: Õigus. Seega on teatud arv ämbrid, et sa determine-- mis te poisid peaks vabalt mängida. See võib olla päris lahe et näha, mis juhtub, kui muudad arv ämbrid. Aga jah, see on määratud arv ämbrid. Mis saab sobitada nii palju elemente, mida vajate on see eraldi ühendamine, kus sa on seotud nimekirjade iga ämber. See tähendab, et teie hash tabelit on täpselt suurust et sa pead seda, eks? See on mõte, mis on seotud nimekirju. Külm. 

Nii et igaüks OK seal? Hea küll. Ah. Mis siis juhtus? Tõesti kohe. Guess keegi tapab mind. 

OK me ei kavatse minna katseid, mis on natuke hull. Mulle meeldib hash tabeleid. Ma arvan, et nad on tõesti lahe. Katseid on lahe ka. 

Nii et keegi ei mäleta, mida proovida on? Sa oleks pidanud üle ta lühidalt loengu? Kas mäletate, millist, kuidas see toimib? Sihtrühm: Ma lihtsalt noogutab et me ei lähe üle. SPEAKER 1: Me ei lähe üle. OK, me tõesti minna selle üle nüüd on see, mida me ütleme. 

Sihtrühm: See on ette ülekanne puu. 

SPEAKER 1: Jah. See on ülekanne puu. Awesome. Nii et üks asi, mida tähele on see, et me otsivad üksikute märkide siin, eks? 

Nii et enne meie hash funktsiooni, me vaatasid sõnad tervikuna ja nüüd me otsime rohkem kell tegelased, eks? Nii et meil on Maxwell siia ja Mendel. Nii et põhimõtteliselt try-- võimalus mõelda on see, et igal tasandil siia on hulgaliselt kirju. Nii et see on sinu juurtipust siin, eks? See on kõik tegelased tähestiku algusest iga sõna. 

Ja mida sa tahad teha, on ütleme, OK, meil on mõned M sõna. Me läheme otsima Maxwell, nii läheme M. Ja M punkte tervikuna teiste massiivi, kus iga Sõna, niikaua kui seal on sõna, mis on kui teise kirja, nii kaua, kui seal on sõna, mis on B Teine täht see on pointer läheb mõnele järgmisele massiivi. 

Seal ilmselt ei ole Sõna, mis MP midagi, nii et P positsiooni selles massiiv, see oleks lihtsalt NULL. See tähendab, OK, ei ole sõna mis on M, millele järgneb P, OK? Nii et kui me mõtleme selle peale, iga üks neist väiksemad asjad on tegelikult üks neist suur massiivide abil Z. Niisiis, milline võiks olla üks neist asjadest mis on omamoodi puuduseks proovida? 

Sihtrühm: palju mälu. 

SPEAKER 1: See on ton mälu, eks? Igaüks neist plokid siit moodustab 26 ruumid, 26 elementi massiivi. Nii püüab saada uskumatult ruumi raske. 

Aga nad on väga kiire. Nii uskumatult kiire, kuid tõesti ruumi ebaefektiivne. Kind of pead mõtlema milline neist sa tahad. Need on väga lahe oma pset, kuid nad võtavad palju mälu, nii et sa kaubelda välja. Jah? 

Sihtrühm: Kas oleks võimalik luua proovida ja siis kui sul on kõik andmeid, et te need-- Ma ei tea, kas see oleks mõistlik. Olin vabanemiseks kõik NULL märki, kuid siis siis ei oleks võimalik indeks them-- 

SPEAKER 1: Sul on vaja veel neid. 

Sihtrühm: - samal viisil iga kord. SPEAKER 1: Jah. Sa pead NULL märki lasta sa tead, kui seal ei ole sõnagi seal. Ben ei teil on midagi, mida sa tahad? OK. Olgu, nii et me läheme minna natuke rohkem arvesse tehnilisi üksikasju taga proovige ja töö kaudu näiteks. 

OK, nii et see on sama asi. Arvestades ahelloend meie peamised liiki of-- mida see sõna ma tahan? - nagu hoone plokk oli sõlme. In proovida, meil on ka sõlme, aga see on määratletud erinevalt. 

Nii et meil on mõned bool et tähistab, kas sõna tegelikult olemas selle asukoha ja seejärel meil on mõned massiivi siin-- või pigem see on viit massiivi 27 tähemärki. Ja see on antud juhul see 27-- ma olen kindel, et te kõik on nagu, oota on 26 tähte tähestikus. Miks meil on 27? 

Nii et sõltuvalt kuidas sa rakendada seda, see on pset et lubatud ülakomad. Nii et miks ekstra üks. Sul on ka mõnes juhul null terminaator sisaldub üks märki, et see on lubatud olla, ja see, kuidas nad kontrollivad, et kas see on lõpuks sõna. Kui olete huvitatud, vaadake Kevin video study.cs50, samuti Wikipedia on mõned head vahendid olemas. 

Aga me läheme läbi lihtsalt selline kuidas te võiks töötada läbi proovida kui sa oled andnud üks. Nii et meil on super lihtne siin, et on sõnad "nahkhiir" ja "zoom" neid. Ja nagu me näeme siin, see väike ruum siin esindab meie bool et ütleb: jah, see on sõna. Ja siis see on meie massiive tegelased, eks? 

Nii et me ei lähe läbi leidmise "nahkhiir" selles proovida. Nii algab ülaosas, eks? Ja me teame, et b vastab teine ​​indeks, teine ​​osa Käesoleva massiiv, sest ja b. Nii umbes teine. 

Ja ta ütleb, OK, lahe, jälgida, et arvesse Järgmise massiiv, sest kui me mäletame, see ei ole, et kõik need tegelikult sisaldavad elementi. Igaüks neist massiivid sisaldab pointer, eks? See on oluline vahet teha. 

Tean, et see on- üritab on tõesti raske saada esimest korda nii et isegi kui see on teist või kolmandat korda ja see on ikka omamoodi näilisest raske, Ma luban, kui sa lähed vaatama lühike uuesti homme, see ilmselt teha palju mõttekam. See võtab palju seedida. Ma ikka mõnikord olen nagu, oota, mis on proovida? Kuidas seda kasutada? 

Nii oleme b antud juhul mis on meie teine ​​indeks. Kui meil oleks, ütleme, c või d või muu kirja, meil on vaja kaarti, et tagasi indeks meie massiivi, mis vastab. Nii et me võtaks nagu rchar ja me lihtsalt lahutama ära kaardistada see 0 kuni 25. Kõik hea, kuidas me map meie iseloomu? OK. 

Nii et läheme teine ​​ja me näeme, et jah, see ei ole NULL. Me saame liikuda edasi selle kõrval massiivi. Nii et me läheme selle kõrval massiivi siin. 

Ja me ütleme, OK, nüüd peate mõtlema, kas on siin. Kas null või teeb seda tegelikult edasi liikuda? Nii et tegelikult liigub edastada selles massiivi. Ja me ütleme, OK, t on meie viimane täht. Nii et me läheme t indeks. Ja siis me liigume edasi sest seal on veel üks. Ja see ütleb sisuliselt, et jah, ta ütleb, et on olemas sõna siin-- et kui te järgite seda tee, olete jõudnud on sõna, mida me teame, on "nahkhiir". Jah? 

Sihtrühm: Kas see standard on, et kui indeks 0 ja siis on mingi 1 või on lõpus? 

SPEAKER 1: No. Nii et kui me vaatame tagasi meie avaldus siin, see on tõeväärtus, nii et see on oma osa teie sõlme. Nii see ei ole osa massiivi. Külm. Nii et kui me lõpetame oma sõna ja me oleme See massiiv, mida me tahame teha, on teha tšeki on see sõna. Ja sel juhul oleks tagasi jah. 

Nii et selle teadmiseks, me teame, et "loomaaed" - me teame, kui inimesed, et "loomaaed" on sõna, õige? Aga kas proovida oleks siin öelda, ei, see ei ole. Ja see oleks öelda, et kuna me kes ei ole määranud seda sõna siin. Kuigi me võime läbida kuni see massiiv, seda proovida ütleksin, et ei, Loomaaia ei ole teie sõnastik sest meil ei ole määratud seda sellisena. 

Nii et üks võimalus seda teha selle-- oh, vabandust, see üks. Nii selles asjas "zoo" ei ole sõna, kuid see on meie proovida. Aga see, ütleme, et me tahame seda kasutusele sõna "vann", mis juhtub, on me järgime through-- b, t. Me oleme selles massiiv, ja läheme otsida h. 

Sellisel juhul, kui me vaadata osuti h, see osutab NULL, OK? Nii et kui see on selgesõnaliselt osutades teise massiiv, sa eeldada, et kõik viidad Selles massiiv on suunatud tühjaks. Nii et antud juhul h osutab tühjaks, et me ei saa midagi teha, nii et see oleks ka tagasi vale, "vanni" ei ole siin. Nii et nüüd oleme tegelikult lähe läbi kuidas me tegelikult öelda et "loomaaed" on meie proovida. Kuidas lisada "loomaaed" meie proovida? Nii samamoodi, alustasime meie seotud nimekirja, hakkame keskmes. Kahtluse korral alustada juur neid asju. 

Ja me ütleme, OK, z. z olemas selles, ja see teeb. Nii et te liikudes edasi oma järgmise massiiv, OK? Ja siis järgmise üks, ütleme, OK, ei o olemas? See teeb. Seegi. 

Ja nii meie kõrval üks, me oleme öelnud, OK, "loomaaed" on juba olemas siin. Kõik me peame tegema, on seatud see võrdne tõsi, et seal on sõna seal. Kui teil on järginud kõik kuni enne seda, see on sõna, lihtsalt seada võrdsustatud. Jah? 

Sihtrühm: Nii et siis kas see tähenda, et "ba" on sõna ka? 

SPEAKER 1: No. Nii et antud juhul "ba" saaksime siin me ütleks, on see sõna, ja oleks see siiski ei ole. OK? Mmhmm? 

Sihtrühm: Nii et kui teil on see sõna ja te ütlete jah, siis sisaldab minna m? 

SPEAKER 1: Nii see on, mida teha with-- sa laadimisel sisse. Sa ütled "loomaaed" on sõna. Kui te lähete kontroll-- nagu, ütleme sa tahad öelda, ei "loomaaed" on olemas selles sõnastikku? Sa oled ainult kavatse otsida "loomaaias" ja siis vaadata, kas see on sõna. Sa ei saa kunagi liikuda kuni m, sest see ei ole mida te otsite. 

Nii et kui me tegelikult tahtsime lisada "vann" sellesse proovida, me teeks sama asja nagu tegime "loomaaias" välja näeksime, et kui me proovida ja saada h, seda ei ole olemas. Nii et sa ei mõtle seda püüdnud lisada uue sõlme seotud nimekirja, nii et meil oleks vaja lisada veel üks neist massiivid, nagu nii. Ja siis see, mida me teha, on meil lihtsalt seada h element käesoleva array juhtides seda. 

Ja mis siis oleks me tahame teha siin? Lisa see võrdne tõsi sest see sõna. Külm. Ma tean. Katseid ei ole kõige põnevam. Usu mind, ma tean. 

Nii et üks asi, mida mõistame katseid Ma ütlesin, et nad on väga tõhus. Nii et me oleme näinud neid asuda ton ruumi. Nad omamoodi segane. Miks peaks me kunagi kasuta neid? Me kasutame neid, sest nad on uskumatult tõhus. 

Seega, kui olete kunagi otsin üles sõna, siis on ainult piirneb pikkus sõna. Nii et kui te otsite Sõna, mis on pikkus viis, sa oled ainult kunagi pea teha kõige rohkem viis võrdlused, OK? Seega muudab põhimõtteliselt konstantne. Nagu sisestamise ja otsing Põhimõtteliselt on konstantne aega. 

Nii et kui te ei saa kunagi saada midagi pidevas ajal see on nii hea, kui see läheb. Sa ei saa parem kui konstantne ajas neid asju. Nii et on üks suur plussid proovib. 

Aga see on palju ruumi. Nii et sa selline pead otsustama Mis on sulle olulisem. Ja tänapäeva arvutid ruumi, et proovida võib kuluda kuni võibolla ei mõjuta teile, et palju, aga võib-olla sa oled tegelevad millegi mis on palju, palju rohkem asju, ja proovida lihtsalt ei ole mõistlik. Jah? 

Sihtrühm: Oota, nii et teil on 26 tähed iga üks? 

SPEAKER 1: mmhmm. Jah, teil on 26. Teil on on sõna marker ja siis teil on 26 viiteid iga üks. Ja nad point-- 

Sihtrühm: Ja iga 26, nad on kummalgi 26? 

SPEAKER 1: Jah. Ja sellepärast, kui saate vaata avardab see üsna kiiresti. Hea küll. Nii et me ei kavatse sattuda puud, mis Ma tunnen, et on lihtsam, arvatavasti kena väike hingetõmbeaeg alates üritab seal. Loodetavasti enamik teist näinud puu enne. Mitte nagu päris need väljaspool, mida ma ei tea, kas keegi läks õues hiljuti. Läksin apple korjamine sel nädalavahetusel, ja oh heldust, see oli ilus. Ma ei teadnud, lehed võiks vaadata, et päris. 

Nii et see on lihtsalt puu, eks? See on lihtsalt mõned sõlme, ja see märgib, et hunnik muid tippe. Nagu näete siin, on see selline korduv teema. Sõlmed osutades sõlmed on selline sisuliselt palju andmestruktuurid. See lihtsalt sõltub sellest, kuidas me lasta osutavad üksteisele ja kuidas me läbida nende kaudu ja kuidas me lisada asju, mis määrab Erinevate omaduste tõttu. 

Nii lihtsalt mõned mõisted, mis ma olen varem kasutanud. Nii et juur on kõik, mis on tipus. see on koht, kus me alati alustada. Sa ei mõtle seda kui head ka. Aga puud, kaldume nimetavad seda root. 

Midagi allosas siin-- on väga bottom-- on lugeda lehtedest. Seega läheb koos Kogu puu asi, eks? Lehed on servades oma puu. 

Ja siis on meil ka paar mõttes rääkida sõlmede suhtes üksteisele. Nii et meil on vanem, laste ja õdede-vendadega. Nii antud juhul 3 on vanem 5, 6 ja 7. Nii et vanem on kõik, mis on üks samm eespool iganes sa oled viidates, lihtsalt nagu sugupuu. Loodan, et see kõik on veidi natuke rohkem intuitiivne kui proovib. 

Õed-vennad on need, mis on sama emaettevõtja, eks? Nad on samal tasemel siin. Ja siis, kui ma olin öeldes: lapsed on lihtsalt kõik, mis on üks samm allapoole sõlme küsimus, eks? Külm. Nii Binääripuu. Kas keegi ohtu arvan ühel omadused kahendpuu? 

Sihtrühm: Max kaks lehte. 

SPEAKER 1: Õigus. Nii et max kaks lehte. Nii et see enne oli meil see mis oli kolm, kuid Binääripuu, sul on max kaks laste vanema kohta, eks? Seal on teine huvitav omadus. Kas keegi teab, mis? Kahendpuud. 

Nii Binääripuu on kõik, kohta the-- ei ole see sorted-- kuid järjestatud kahendpuu, kõik paremal on suurem kui vanem, ja kõik vasakul on väiksem kui vanem. Ja see on olnud viktoriin küsimus enne, nii hea teada. Niisiis, kuidas me defineerime seda, uuesti, meil on veel üks sõlm. See tundub väga sarnane sellega, mida? Kahekordselt 

Sihtrühm: ahelloendid 

SPEAKER 1: kahekordse seotud nimekirja, eks? Nii et kui me asendada see eelmise ja järgmise, see oleks kahekordselt seotud nimekirja. Kuid antud juhul me tegelikult on vasakule ja paremale ja see on kõik. Muidu on täpselt sama. Meil on veel element otsite, ja sa lihtsalt pead kahe viiteid läheb kõike, mis on järgmine. Jah, nii kahendotsingupuu. Kui märkame, kõike siin on suurem than-- või kõike kohe paremale siin on suurem kui kõik, Siit on alla. 

Nii et kui me otsida, siis peaks vaatama väga lähedal binaarne otsing siin, eks? Välja asemel otsin poole massiiv, me lihtsalt vaadata kas vasakule pool või paremal pool puud. Nii et see läheb veidi lihtsam, ma arvan. 

Seega, kui teie juur on NULL, ilmselt see on lihtsalt vale. Ja kui see on olemas, ilmselt see on tõsi. Kui see on väiksem kui me otsida vasakule. Kui see on suurem kui Otsime õige. See on täpselt nagu binaarne otsing, lihtsalt erinev andmestruktuur et me kasutame. Selle asemel, massiiv, see on lihtsalt Binääripuu. 

OK, korstnad. Ja ka see näeb välja nagu me Võib-olla veidi aega. Kui me seda teeme, ma olen õnnelik, et minna üle kõik see uuesti. OK, nii et korstnad. Kas keegi mäletab, mida stacks-- mis tahes omadusi korstna? 

OK, nii et enamik meist, ma arvan, süüa söögitoas halls-- nii palju kui me ei meeldi. Aga ilmselt sa ei mõtle virna sõna otseses mõttes nagu virna või virna asju. Ja mis oluline mõistma, et see on midagi-- iseloomulik et me nimetame seda by-- on LIFO. Kas keegi teab, mis see tähendab? Mmhmm? 

Sihtrühm: viimane esimene välja. 

SPEAKER 1: Õigus, kesta sisse, esimesena välja. Nii et kui me teame, kui me virnastamine asjad üles, kõige lihtsam asi haarata off-- ja võib-olla ainus asi, mida saab haarata välja, kui meie stack on suur loomult- on see, et ülemine element. Mida iganes pandi last-- nagu me näeme siin, mis iganes suruti kõige recently-- on saab olema esimene asi, mida me pop välja, OK? 

Mis meil siin on, teine ​​typedef struktuure. See on tõesti lihtsalt meeldib kiirkursuse andmestruktuur, nii seal on palju visatakse sind poisid. Ma tean. Nii et veel üks struct. Jee struktuuridele. 

Ja sel juhul, see on mingi pointer array, mis on mingil määral. Nii et see on meie korstnat siin, nagu meie tegelik massiivi mis hoiab meie elemente. Ja siis on meil siin mõned suurusest. 

Ja tavaliselt, mida soovite säilitada jälgida, kuidas suur teie stack on sest mis see saab lubada sul teha on, kui sa tead, suurus, see võimaldab teil öelda, OK, ma olen võimsuste? Kas ma saan midagi enamat? Ja see näitab ka, kus peal oma korstnat on, et sa tead, mida sa võib tegelikult startida. Ja see on tegelikult läheb olla natuke selgemaks siin. 

Nii push üks asi, kui sa olid kunagi rakendada lükkama, kui ma olin lihtsalt öeldes oma stack on piiratud suurusega, eks? Meie massiiv oli mingil määral. See on massiiv. See on kindla suurusega, nii et me peame veenduda, et me ei lase enam meie massiivi kui me tegelikult on ruumi. 

Nii et kui loote push funktsioon, esimene asi, mida teha, on öelda, OK, mul on ruumi minu stack? Sest kui ma seda ei tee, kahju, Ma ei saa salvestada element. Kui ma teen, siis soovite salvestada see ülaosas virna, eks? 

Ja see on põhjus, miks meil on jälgida meie suurus. Kui me ei jälgida oma suurusest, me ei tea, kuhu panna see. Me ei tea, kui palju on meie massiiv juba. Nagu ilmselt olemas viise et äkki sa võiksid seda teha. Sa võid initsialiseerida kõik NULL ja siis vaadata viimaseid NULL, kuid palju lihtsam asi on lihtsalt öelda, OK, jälgida suurus. Nagu ma tean, et mul on neli elementi minu massiiv, nii et järgmine asi et me panna, me oleme kavatse hoida indeksiga 4. Ja siis loomulikult tähendab see, et olete edukalt surunud midagi peale oma korstnat, siis tahad, et seda suurendada nii et sa tead, kus sa oled nii et saate suruda rohkem asju. 

Nii et kui me püüame pop midagi ära pinu milline võiks olla esimene asi, et me tahame, et kontrollida? Sa oled püüdnud võtta midagi välja oma korstnat. Oled kindel, et seal on midagi oma korstnat? Ei. Mis võiks me tahame vaadata? 

Sihtrühm: [kuuldamatu]. SPEAKER 1: Kontrollige suurus? Size. Nii et me tahame vaadata, kui Meie suurus on suurem kui 0, OK? Ja kui on, siis me tahame vähendada Meie suurus 0 ja tagastab selle. Miks? 

Esimesel üks olime lükates, oleme surunud ta peale suurus ja seejärel ajakohastada suurus. Sel juhul me decrementing suurus ja siis võta seda maha, kitkumise see meie massiivi. Miks võiks me seda teeme? Nii et kui mul on üks asi, minu stack, milline oleks minu suurus sel hetkel? 1. 

Ja kus on element 1 säilitatakse? Millisel indeks? Sihtrühm: 0. SPEAKER 1: 0. Nii antud juhul me alati on vaja teha sure-- tagasipöördumise asemel suurus miinus 1, sest me teame, et meie element on läheb ladustatakse 1 vähem mis tahes meie suurus on see lihtsalt hoolitseb ta. See on veidi rohkem elegantne viis. Ja me lihtsalt kahandab meie suurus ja siis tagasi suurusest. Mmhmm? 

Sihtrühm: Ma arvan, et lihtsalt üldiselt Miks see andmestruktuur olla kasulik? 

SPEAKER 1: See sõltub kontekstist. Nii mõned teoreetiliselt kui te töötate with-- OK, las ma vaatan, kas on kasulik üks mis on kasulik rohkem kui väljaspool CS. Mis korstnad, iga kord, kui on vaja jälgida midagi, on hiljuti lisatud on siis, kui sa lähed soovite kasutada virna. 

Ja ma ei mõtle hea näiteks, et just nüüd. Aga kui viimased asi on kõige tähtsam, see on, kui pakk saab olema kasulik. Püüan mõelda kui seal on hea selle eest. Kui ma arvan, et on hea näide järgmises 20 minutit, siis ma kindlasti öelda. 

Aga üldiselt, kui seal on midagi, nagu ma ütlesin enamik, kus viimase Kõige tähtsam on, et on kus korstna hakkavad. Arvestades järjekorrad on omamoodi vastupidine. Ja kõik väikesed koerad. Kas see ei ole suur, eks? Ma tunnen nagu ma peaks lihtsalt jänes video õigus keset lõik kutid sest see on intensiivne sektsioonis. 

Nii järjekorda. Põhimõtteliselt järjekord on nagu joon. Kutid ma olen kindel, kasutavad seda iga päev, Just nagu meie söögisaali. Nii et me peame minema ja saada meie plaate, ma olen Kindlasti olete ootama kooskõlas kaevukook või saada oma toitu. 

Nii et siin midagi on, et see on FIFO. Nii et kui LIFO oli viimane esimene välja, FIFO on esimene, first out. Nii et see on koht, kus iganes sa panna esimesel on teie kõige olulisem. Nii et kui sa ootasid in LINE sa saad kujutage ette, kui sa läksid mine saada uus iPhone ja see oli virna, kus viimane inimene liin sai see esimene, inimesed tapavad üksteist. 

Nii FIFO, me oleme kõik väga hästi koos reaalses maailmas siin ja see kõik on pistmist tegelikult liiki taasloomine kogu see rida ja järjekordi struktuuri. Nii et koos virna, meil push ja pop. Mis järjekorras on meil Lisa järjekorda ja dequeue. Nii Lisa järjekorda tähendab põhimõtteliselt asetab selle tagasi, ja dequeue abil võtta välja eestpoolt. Nii et meie andmestruktuur natuke keeruline. Meil on teine ​​asi, mida jälgida. 

Nii et ilma pea, see Just korstna, eks? See on sama struktuur virna. Ainuke asi on nüüd muutunud on me on see pea, mida mida sa arvad läheb silma peal hoida? 

Sihtrühm: esimene. 

SPEAKER 1: Õigus, Esimene asi, mida me panna. Pea oma järjekorda. Kes on esimene rida. Olgu, nii et kui me teeme Lisa järjekorda. Jällegi ühegi Nende andmestruktuuride kuna me tegeleme massiiv, peame kontrollima, kas meil on ruumi. 

See on selline nagu mina ütlen kutid, kui avate faili peate kontrollima for null. Mis tahes kõnealuse korstnad ja järjekorrad, peate et näha, kas seal on ruumi, sest me oleme tegelevad fikseeritud suurusega massiiv, nagu me näeme siin-- 0, 1 kõik kuni 5. Niisiis, mida me teeme, et asi on kontrolli et näha, kas meil on veel ruumi. Kas meie suurus on väiksem kui võimsus? 

Kui jah, siis on meil vaja seda saba ja me uuendada meie suurus. Mida võib saba olla sel juhul? See ei ole selgelt välja kirjutatud. Kuidas me seda säilitada? Mida saba olla? 

Nii et olgem kõndida läbi selle näite. Nii et see on massiivi suurus 6, eks? Ja meil on just nüüd, meie suurus on 5. Ja kui me pane see, et see läheb minna viienda indeks, eks? Nii et hoidke juures saba. 

Teine viis kirjutada saba oleks lihtsalt meie reaga indeks suurus, eks? See on suurus 5. Järgmine asi läheb minema 5. Cool? OK. Läheb veidi keerulisem kui hakkame jama peas. Jah? 

Sihtrühm: Kas see tähendab, et me oleks deklareeritud massiivi oli viis elementi pikk ja siis lisame selle peale? 

SPEAKER 1: No. Nii antud juhul on see virna. See tuleb deklareerida kui massiivi suurus 6. Ja sel juhul me lihtsalt ühe sammu vasakule. 

OK, nii et üks asi on selles juhul, kui meie juht on 0, siis me lihtsalt lisada seda suurust. Aga see läheb veidi keerukam sest tegelikult nad ei ole slaid selle eest, et ma lähen juhtida, sest see ei ole päris nii lihtne, kui sa alustada vabaneda asjadest. Nii et koos virna teil on ainult kunagi muretsema, mida suurus on kui sa oled lisades midagi, koos järjekorras pead ka tegema Veenduge, et teie pea on arvele võetud, sest lahe asi järjekorrad on see, et kui sa ei ole suutlikkust, tegelikult võite teha seda ümbritsev. 

OK, nii et üks asi-- oh, see on kohutav kriit. Üks asi, mida kaaluda on. Me lihtsalt teha viis. OK, nii et me ei kavatse öelda pea on siin. See on 0, 1, 2, 3, 4. 

Pea on olemas, ja palun, on asju neile. Ja tahame lisada midagi, eks? Nii et asi, mida me peame tean, on see, et pea on alati Liigutatav nii ja siis loop tagasi umbes, eks? 

Nii et see järjekord on ruumi, eks? See on ruum, algusest peale, omamoodi vastand. Niisiis, mida me peame tegema, on meil vaja arvutada saba. Kui te teate, et teie juht ei ole teinud, saba on lihtsalt oma reaga indeks suurus. 

Aga tegelikult, kui te kasutate järjekorda, su pea on vist uuendatakse. Nii et mida sa pead tegema, on tegelikult arvutada saba. Niisiis, mida me teeme, on see valem siin, mis ma teile poisid mõtlevad, ja siis me räägime sellest. Nii et see on võimsust. 

Nii see tegelikult teile, kuidas seda teha. Kuna antud juhul, siis mida? Meie peakontor on 1, meie suurus on 4. Kui me mod, et 5, saame 0, mis on koht, kus me peaksime sisend ta. 

Nii et siis järgmisel juhul Kui me seda teha, ütleme, OK, lähme dequeue midagi. Me dequeue see. Võtame välja see osa, eks? 

Ja nüüd meie pea on suunaga siia ja me tahame lisada teise asi. See on põhiliselt tagasi meie rida, eks? Järjekorrad võivad ümbritsev massiiv. See on üks peamisi erinevusi. Korstnad, sa ei saa seda teha. 

Mis järjekorrad, saate sest kõik, mis loeb on see, et sa tead, mida viimati oli lisatud. Kuna kõik läheb lisada Selle vastassuunaliseks suunas, käesoleval juhul ja siis murtakse, saate jätkata kasutusele uusi elemente ees massiivi sest see ei ole tõesti ees massiivi enam. Sa ei mõtle alguses massiivi kus oma peaga tegelikult on. 

Nii et see valem on see, kuidas sa arvutada oma saba. Kas see on mõistlik? OK. OK, dequeue ja seejärel kutid on 10 minutit, minu käest küsida ükskõik selgitavaid küsimusi sa tahad, sest ma tean, et see on hull. 

Olgu, nii sama way-- Ma ei tea, kas kutid märganud, aga CS on kõike mustrid. Asjad on päris palju sama, just pisikeste lisasid. Nii et sama asi siin. Meil on vaja vaadata, kui me tegelikult on midagi meie järjekorda, eks? Ütle, OK, on ​​meie suurus on suurem kui 0? Külm. 

Kui me seda teeme, siis me liigume meie peas, mis on see, mida ma siin näidatud. Me uuendada meie pea olema üks rohkem. Ja siis me kahandab meie suurus ja tagastab element. 

Seal on palju konkreetsem kood study.cs50.net, ja ma väga soovitada kavatse kaudu, kui teil on aega, isegi kui see on lihtsalt pseudo-koodi. Ja kui te tahate rääkida läbi mis minuga üks ühele, siis palun andke mulle tean. Ma oleksin hea meelega. Andmestruktuuride, kui te võtate CS 124, saate tean, et andmestruktuurid saada väga lõbus ja see on alles algus. 

Nii et ma tean, et see on raske. See on OK. Me vaeva. Ma ikka teha. Nii et ärge muretsege liiga palju seda. 

Aga see on põhimõtteliselt oma kiirkursuse andmestruktuurid. Ma tean, et see on palju. Kas on midagi, mida me tahaks minna jälle? Midagi me tahame rääkida läbi? Jah? 

Sihtrühm: Sest et näiteks nii uus saba on 0 üle on? SPEAKER 1: Jah. Sihtrühm: OK. Siis läheb läbi, soovid on 1 pluss 4 või-- 

SPEAKER 1: Nii et sa ütlesid, kui me tahame minna seda uuesti? Sihtrühm: Jah. Nii et kui sa olid viinud out-- kus on sa arvutamise saba on? 

SPEAKER 1: Nii saba oli in-- muutsin seda. Nii selles näites siin, see oli massiivi me vaatame, OK? Nii et meil on asjad 1, 2, 3 ja 4. Nii et meil on meie peas on võrdne 1 juures Sel hetkel, ja meie suurus on kuni 4 Sel hetkel, eks? 

Te kõik ühel meelel selles on asi? Nii et me teeme head, pluss suurus, mis annab meile 5 ja siis mod 5. Me saame 0, mis ütleb meile, et 0 on kus on meie saba, kus meil on ruumi. 

Sihtrühm: Mis on kork? 

SPEAKER 1: võimsus. Vabandust. Nii et on suurus oma massiivi. Jah? 

Sihtrühm: [kuuldamatu] enne naaseme element? 

SPEAKER 1: Nii et me liigume pea või tagastab hetkel? Nii et kui me liigume ühe, aland suurus? Oota. Ma kindlasti unustasin veel. Pole viga. Ei ole veel valemit. Jah, sa tahaksid tagasi pea ja seejärel liigutada tagasi. 

Sihtrühm: OK, sest sel punkt, pea oli 0, ja siis tahavad tagasi indeks 0 ja seejärel teha peaga 1? 

SPEAKER 1: Õigus. Ma arvan, et seal on teine valem selline nagu see. Ma ei ole seda peal mu pea Ma ei taha, et sulle vale. Aga ma arvan, et see on täiesti kehtib kuni ütleme, OK, hoidke element-- iganes pea on element on-- aland oma suurus, liikuda oma pea üle ja tagastamine mis iganes see element on. See on täiesti õige. OK. Ma tunnen, et see ei ole nagu most-- sa ei ole läheb käima siit nagu jah, ma tean, et proovib. Ma sain selle kõik. See on OK. Ma luban. Aga andmestruktuurid on midagi, see võtab palju aega, et harjuda. Ilmselt üks raskemaid asju, ma arvan, et muidugi. 

Nii see kindlasti võtab kordamine ja otsin at-- I ei tea ahelloendid kuni tegin liiga palju neid, samamoodi, et ma ei teinud seda tõesti aru viiteid kuni ma olen olnud seda õpetada kaks aastat ja teha oma psets ta. See võtab palju kordamist ja aega. Ja lõpuks, siis millist nuppu. 

Kuid samal ajal, kui teil on omamoodi kõrgetasemelise arusaam sellest, mida need teevad, nende plusse ja cons-- mis on see, mida me tõesti kipuvad rõhutama, eriti intro muidugi. Nagu, miks me kasutame proovida üle massiivi? Like, millised on positiivsed ja negatiivid iga nimetatud? 

Ja mõista kompromissid omavahel nende struktuuride on see, mis on palju olulisem just nüüd. Tegemist võib olla üks hull Küsimus või kaks, mis on küsin teilt rakendada push või rakendada pop või Lisa järjekorda ja dequeue. Aga enamasti, millel on mis kõrgema taseme mõistmist ja rohkem intuitiivne haarata on tähtsam kui tegelikult on võimalik seda rakendada. 

See oleks tõesti fantastiline, kui te kõik võiks minna välja ja lähevad rakendada proovida, kuid me mõistame, et see ei ole tingimata kõige mõistlikum asi kohe. Aga sa võid oma pset, kui soovite üles ja siis saad tavadele ja siis äkki saate tõesti aru. Jah? 

Sihtrühm: OK, siis millised on meil mõeldud kasutamiseks pset? Kas mul on vaja kasutada üks neist? SPEAKER 1: Jah. Nii et teil on oma valik. Ma arvan, et sel juhul saame räägime pset natuke sest ma jooksin läbi nende. Nii et teie pset, kui olete oma valik üritab või hash tabeleid. Mõned inimesed püüavad ja kasutada õitsema filtrid kuid need on tehniliselt ei ole õige. Kuna nende tõenäosuslik iseloom, nad annavad valepositiivseid mõnikord. Nad on lahe uurima, kuigi. Soovitame otsin neid vähemalt. Aga sa pead oma valikut vahel hash tabelit ja proovida. Ja see saab olema, kui laete oma sõnastikku. 

Ja sa pead valima Sinu räsifunktsioon peate valida mitu kopad sul on, ja see on erinev. Nagu siis, kui teil on rohkem ämbrid, äkki see saab töötada kiiremini. Aga võib-olla sa raiskad palju ruumi, et kuidas küll. Sa pead aru saada. Mmhmm? 

Sihtrühm: Sa ütlesid enne, et saame kasutada teiste räsifunktsioonid, et me ei pea luua hash funktsiooni? 

SPEAKER 1: Jah, muidugi. Nii et sõna otseses mõttes oma räsifunktsioon nagu google "hash funktsiooni" ning otsida mõned lahedad ones. Sa ei tohiks ehitada oma hash funktsiooni. Inimesed veedavad teesi neid asju. 

Nii et ärge muretsege hoone oma. Leia ühe online alustada. Mõned neist pead manipuleerida natuke veenduda, tagastamise tüüpi mängu üles ja tühi-tähi, nii alguses, Ma soovitaks midagi väga lihtne, et võib-olla ainult hashes esimene täht. Ja siis, kui sul on, et töö, sisaldavad jahedam hash funktsiooni. Mmhmm? 

Sihtrühm: Kas proovida olla või tõhus vaid lihtsalt raskem, like-- 

SPEAKER 1: Nii et proovida, ma arvan, on intuitiivselt raske rakendada kuid on väga kiire. Siiski võtab rohkem ruumi. Jällegi saate optimeerida nii need, erineval viisil ja on võimalusi mina-- Sihtrühm: Kuidas me sorteeritud selles küsimuses? Kas see matter-- 

SPEAKER 1: Nii et te sorteeritud tavalisel viisil. Sa lähed liigitatakse disaini. Ükskõik kuidas sa teed, sa tahad veenduge, et see on nii elegantne kui võimalik ja nii tõhus kui võimalik. Aga kui te otsustate proovida või hash tabelis, kui see töötab, me oleme õnnelikud, et. Ja kui te kasutate midagi, et hashes esimene täht, see on hea, nagu võibolla nagu disain tark. Me jõudes ka punkt selles semester-- Ma ei tea, kas te poisid noticed-- kui sa oled pset klassid väheneb natuke sest disaini ja tühi-tähi, see on täiesti trahvi. Läheb punktini, kus oma programmid saavad keerulisem. On enam kohtades saab parandada. 

Nii et see on täiesti normaalne. See ei ole, et sa oled teeb hullemaks oma pset. See on lihtsalt meil on raskem nüüd. Nii et igaüks end tunneb seda. Ma lihtsalt liigitada kõik oma psets. Ma tean, et igaüks tunneb seda. 

Nii et ei muretse, et. Ja kui teil on küsimusi selle kohta, enne psets või kuidas saab parandada, Ma püüan ja kommenteerida konkreetseid kohad, kuid mõnikord on see hilja ja ma ei väsi. Kas on muid asju umbes andmestruktuuride? Ma olen kindel, et te poisid tõesti ei tahan rääkida neid enam, kuid kui on, ma olen õnnelik, et minna üle neile, kui ka midagi alates loeng möödunud nädalal või eelmisel nädalal. 

Ma tean, et eelmisel nädalal oli kõik arvustused, nii me võib-olla vahele üle mõned läbi alates loeng. Muid küsimusi võin vastata? OK, eks. Noh, kutid välja tulla 15 minutit varem. 

Loodan, et see oli pooleldi kasulik vähemalt ja ma näen kutid järgmisel nädalal või neljapäev tööajal. Kas taotlused suupisted Järgmise nädala, see on asi? Sest ma unustasin kommi täna. Ja ma tõin kommid viimase nädalas, kuid see oli Columbus Day, nii oli nagu kuus inimest, kes oli neli kotti kommi ise. Võin tuua Starbursts uuesti, kui soovite. Starbursts? OK, kõlab hästi. Ilusat päeva, poisid.