[Muusika mängib] 

ANDI PENG: Tere tulemast nädal 6 punkti. Me kõrvale kaldunud meie standard paragrahvi Teisipäeval Pärastlõunal see armas pühapäeva hommikul. Aitäh kõigile, et koos minuga täna, kuid tõsiselt, aplausi. 

See on päris suur pingutus. Ma peaaegu isegi ei oleks üles ajas, aga see oli OK. Nii et ma tean, et te kõik just tegin seda viktoriini. Esiteks, tere tulemast Tagakülg selle. 

Teiseks, me räägime sellest. Me räägime viktoriin. Me räägime, kuidas sa teed klassis. Sa saad trahvi. Mul on oma viktoriinid sa lõpuks siin, nii et kui te poisid tahavad võtta pilk see, täiesti korras. 

Nii kiiresti, enne kui hakkame, siis päevakorda täna on järgmine. Nagu näete, oleme põhimõtteliselt kiire süütamise läbi terve hunnik andmestruktuurid tõesti, tõesti, tõesti kiiresti. Nii sellisena, siis ei ole super interaktiivne täna. Seda saad lihtsalt mind mingi karjumine asju, mida ja kui ma teid segadusse ajada, kui ma lähen liiga kiiresti, andke mulle teada. Nad on lihtsalt erinevad andmed struktuure ning osana oma pset selle järgmiseks nädalaks, siis saad palutakse rakendada üks neist, võibolla kaks them-- kaks neist Teie pset. OK, nii et ma olen lihtsalt kavatse alustada mõned teated. Me läheme üle korstnad ja järjekorrad rohkem sügavus üle, mida me tegime enne viktoriini. Me läheme üle seotud list jälle taas põhjalikum kui see, mida meil oli enne viktoriini. Ja siis me räägime hash tabelid, puud ja üritab, mis kõik päris vajalik oma pset. Ja siis me läheme üle mõned kasulikke nõuandeid pset5. 

OK, nii viktoriini 0. Keskmine oli 58%. See oli väga madal ja nii kutid kõik tegi väga hästi kooskõlas sellega. 

Päris palju, rusikareegel on, kui sa oled lähemal standardhälbega keskmine eriti kuna me oleme vähem Mugav osa, sa oled täiesti korras. Sa oled õigel teel. Elu on hea. 

Ma tean, et see on hirmutav mõelda, et Ma sain nagu 40% selle viktoriini. Ma ei suuda seda klassi. Ma luban teile, te ei ole läheb suuda klassis. Sa oled täiesti korras. 

Neile teist, kes sai üle keskmine, muljetavaldav, muljetavaldav, nagu tõsiselt hästi tehtud. Mul on neid minuga. Julgelt tulevad jõuda lõpus osa. Anna mulle teada, kui teil on mõni küsimused, küsimused koos nendega. Kui lisame oma skoor vale, andke teada. 

OK, nii pset5, see on tõesti imelik nädal Yale'i selles mõttes, et meie pset on tingitud Kolmapäeva keskpäeval sealhulgas lõpus päev, nii et see on tegelikult teoreetiliselt tõttu teisipäeval kell keskpäeval. Ilmselt keegi valmis Teisipäevasel keskpäeval. See on täiesti korras. Me läheme on tööaega täna samuti esmaspäeva õhtul. Ja kõik osad sel nädalal tegelikult muutunud töötoad, nii et võid vabalt pop ükskõik mida soovite, ja nad on omamoodi mini-pset töötoad abi, et. Nii sellisena, et see on ainus lõik kus me õppematerjale. Kõik teised lõigud on keskendunud ainult abiks pset. Jah? 

Sihtrühm: Kus tööaega? 

ANDI PENG: Lahtiolekuajad tonight-- oh, hea küsimus. Ma arvan, et lahtiolekuaeg täna on Teal või Commons. Kui teil vaadata online CS50 ja te lähete tööaega, tuleks ajakava, mis ütleb teile, kus kõik on. 

Ma tean, kas täna või homme on sinakasroheline, ja ma arvan, et meil võib olla common ööl. Ma ei ole kindel. Hea küsimus. Kontrollida CS50. 

Cool, küsimusi ajakava järgmiseks nagu kolm päeva? Ma luban teile, poisid nagu David ütles, et see on mäe. Te olete peaaegu kohal. Lihtsalt veel kolm päeva. Sinna, ja siis me kõik langenud. Me peame kena CS-intervalli. Me tuleme tagasi. Me sukelduda web programmeerimine ja arendamine, asju, mis on väga lõbus võrreldes mõnedele teistele psets. Ja see saab olema chill ja me on palju nalja. Me peame rohkem kommi. Vabandame kommi. Ma unustasin kommi. See oli karm hommikul. Nii kutid on peaaegu olemas, ja ma olen tõesti uhke teie kutid. 

OK, nii korstnad. Kes armastas küsimus Jack ja tema riided viktoriini? Mitte keegi? OK, see on hea. 

Nii et sisuliselt kui võimalik Pildi Jack, see kutt siin, armastab võtta riided välja riidale, ja ta paneb selle tagasi peale virna pärast ta on teinud. Nii et sel viisil, et ta kunagi Tundub, et saada to põhja Kestab oma riided. Nii sedalaadi kirjeldab lähteandmete struktuur kuidas virna rakendatakse. 

Sisuliselt mõelda Kestab nagu virnas objektid kui paned asjad peale top, ja siis sa pop neid ülevalt. Nii LIFO on lühend meile meeldib to use-- Last In, First Out. Ja nii kesta kuni tippu stack on esimene, mis väljub. Ja nii need kaks sõna meile meeldib siduda selle kutsutakse push ja pop. Kui vajutada midagi peale Kestab ja sa pop seda uuesti üles. 

Ja nii ma arvan, et see on omamoodi abstraktne mõiste neile, kes tahavad näha nagu tegeliku rakendamise reaalses maailmas. Kui paljud teist on kirjutatud essee äkki nagu tund enne seda oli tingitud ja sa kogemata kustutatud suur patakas see, nagu kogemata? Ja mis siis kontrolli teha Me kasutame seda ellu tagasi? Kontroll-Z, jah? Kontroll-Z, nii kogus korda et kontroll-Z on päästnud mu elu, on salvestatud my ass, iga kord mis on ellu virna. 

Sisuliselt kogu teave see on teie Wordi dokument, see saab tõugata ja hüppasid tahtmist. Ja nii sisuliselt kui sa kustutada midagi, kui pop see tagasi üles. Ja siis, kui seda vajate tagasi, siis lükake see, mis on see, mida Kontroll-C teeb. Ja nii reaalses maailmas funktsiooni kuidas lihtsate andmete struktuur aitab oma igapäevaelus. 

Nii struct on nii, et me tegelikult luua pinu. Me kirjutada määratleda struct ja seejärel Me nimetame seda korstna allosas. Ja jooksul korstnat, meil on kaks parameetrit et me saame sisuliselt manipuleerida, nii et meil on char star stringid võimsust. 

Kõik, mis ta teeb loob massiivi et meil saab salvestada mida iganes sa tahad mida me saame kindlaks oma suutlikkust. Võimsus on ainult max summa kirjed saame panna selle massiivi. int suurus on counter, mis hoiab lugu sellest, kuidas paljud teemad on praegu pakis. Siis saame jälgida, A, nii, kui suur tegelik stack on, ja B, kui palju, et korstnat me täitsime, sest me ei taha koguneda üle, mida meie võime on. 

Nii näiteks see armas Küsimus oli oma viktoriini. Sisuliselt kuidas me push külge üles virna. Päris lihtne. Kui te vaatate seda, me käime läbi selle. Kui [kuuldamatu] size-- mäletan, kui te tahad pääseda mistahes parameeter jooksul struct, sa nime struct.parameter. 

Sellisel juhul s on nimi meie stack. Me tahame, et pääseda suurus see, et me teeme s.size. Nii kaua kui suurus ei ole võrdub võimsusega või nii kaua, kui see on väiksem kui võimsust, kas teeks siin. 

Sa tahad, et pääseda sees oma korstnat, nii s.strings, ja sa lähed panna, et uus number mis sa tahad lisada sinna. Ütleme nii, et me tahame lisada int n peale virna, me võiks teha s.strings, sulgudes s.size võrdne n. Kuna suurus on koht, kus me Praegu on pakis Kui me läheme suruda see, et me lihtsalt juurde sõltumata suurusest, seda Praeguse täius virna, ja me push int n peale seda. Ja siis me tahame veenduda, et me ka incrementing suurus n, nii saame jälgida me oleme lisada ekstra asi virna. Nüüd on meil suurem suurus. Kas see siin mõtet kõik, kuidas loogiliselt see toimib? See oli selline kiire. Sihtrühm: Kas te lähete üle s.stringss.strings [s.size] jälle? ANDI PENG: Muidugi, mis siis teeb s.size praegu meile? Sihtrühm: See on praeguse suuruse. ANDI PENG: Täpselt, nii et indeks, mis meie suurus on, ja nii me tahame panna uue täisarv et me tahame lisada s.size. Kas see on mõtet? Kuna s.strings, kõik, mis on on nimi massiivi. Kõik see on on pääseda massiivi meie struct, ja nii kui me tahame paigutada n sellesse indeks, saame lihtsalt kasutada seda kasutades sulgudes s.size. Cool. 

Olgu, pop, ma pseudokoodi it out kutid, kuid sarnane kontseptsioon. Kas see on mõtet? Kui suurus on suurem kui null, siis tean, et sa tahad teha midagi välja, sest kui suurus ei ole suurem kui null, siis pole midagi pakis. 

Nii tahad ainult käivitada Selle koodiga see võib ainult pop, kui midagi on pop. Nii et kui suurus on suurem kui 0, me miinus suurusest. Me kahandab suurus ja siis tagasi kõik, mis on sees, sest popping, me tahame juurdepääsu iganes on salvestatud indeks on riidale. Kõik mõtet? Kui ma tegin teiega kirjutada see välja, te poisid oleks võimalik kirjutada välja? OK, kutid saavad mängida seda. Ära muretse, kui sa ei saa aru. Meil ei ole aega, et koodi seda täna, sest me oleme sain palju need struktuurid läbida, kuid sisuliselt pseudokoodi, väga, väga sarnane suruda. Jälgi mööda loogika. Veenduge, et olete juurdepääsusoovide kõiki Teie struct õigesti. Jah? 

Sihtrühm: Kas need slaidid ja kogu see asi olla täna-ish? ANDI PENG: Alati, eks. Ma lähen, et proovida panna see üles nagu tund pärast. Ma posti David, David püüab pane see üles nagu tund pärast seda. 

OK, nii et siis Astume seda teiste armas andmete struktuuri nimetatakse järjekorda. Nagu te poisid näen siin, et järjekorda, Briti meie hulgas kõik see on on line. Nii et vastupidi te arvate virna on, järjekorras on täpselt see, mida loogiliselt see on teie arvates. Mess toimub reeglite järgi FIFO, mis on First In, First Out. Kui oled esimest üks rida, sa oled esimene, mis väljub liin. 

Mida me tahame nimetame seda on dequeueing ja enqueueing. Kui me tahame midagi lisada meie järjekorda, me Lisa järjekorda. Kui me tahame dequeue või võtta midagi ära, me dequeue. 

Nii sama tunne, et me oleme omamoodi luua kindla suurusega elemente, mida me saab salvestada teatud asju, aga saame ka muuta, kui me pannes parameetrite sees neist põhineb millist funktsionaalsus, mida me tahame. Nii korstnad, tahtsime viimase üks, N olla esimene välja. Järjekord on tahame esimene asi aastal olla esimene asi välja. 

Nii struct-tüüpi määratleda, nagu näete, see on natuke erinev sellest, mida pakis oli sest mitte ainult meil hoida peal, kus suurust praegu on, tahame ka jälgida juht samuti, kus me praegu oleme. Nii et ma arvan, et see on lihtsam kui ma juhtida selle üles. Nii saab kujutada meil järjekorras, Ütleme, et juht on siinsamas. Pea line, olgem lihtsalt öelda, et on praegu olemas, ja me tahame lisada midagi järjekorda. Ma kutsun suurus sisuliselt on sama asi nagu saba, lõpuks kõikjal oma järjekord. Ütleme nii, et suurus on siinsamas. 

Niisiis, kuidas üks feasibly lisada midagi ümber järjekorda? Mis indeks me tahame panna kus me tahame lisada. Kui see on alguses oma järjekorda ja see on lõpuks see või suurusest see, kus me tahan lisada järgmise objekti? 

Sihtrühm: [kuuldamatu] ANDI PENG: Täpselt, mida soovite lisada see sõltub olete kirjutanud. Kas see on tühi või mis on tühi. Nii et sa tahad lisada see ilmselt siin, sest kui suurus on-- kui need kõik on täis, sa tahad lisada see siin, eks? 

Ja nii see on, kuigi väga Lihtne, mitte päris alati õige sest peamine erinevus vahel järjekorras ja korstna on see, et järjekorda ei tegelikult manipuleerida nii et pea muudatusi sõltuvalt sellest, kus sa tahad alguses oma kii alustada. Ja selle tulemusena oma saba Samuti muutub. Ja nii, kui heita pilk See kood praegu. Nagu te poisid paluti ka kirjuta läbi viktoriini, Lisa järjekorda. Võib-olla me räägime läbi, miks vastus oli, mis see oli. 

Ma ei saanud päris sobi see joon ühe, kuid sisuliselt see tükk koodi peaks olema üks rida. Kuluta nagu 30 sekundi jooksul. Heitke pilk, ja miks see on nii, et see on. 

Väga, väga sarnane struct, väga, väga sarnase struktuuriga kui eelmine Kestab välja arvatud ehk üks rida koodi. Ja et üks rida koodi määrab funktsionaalsus. Ja see on tõesti eristavad järjekorras korstnatest. 

Igaüks taha võtke torkehaav oli selgitada, miks olete sain selle keerulise asi siin? Me näeme tagasipöördumist meie imeline sõber moodul. Nagu te poisid peagi tunnustada programmeerimine, Peaaegu igal vajate midagi ümbritsev midagi, moodul saab olema nii, et seda teha. Nii teades, et keegi ei taha proovida selgitades, et koodirida? Jah, kõik vastused on tunnustatud ja oodatud. Sihtrühm: Kas sa räägid minuga? ANDI PENG: Jah. Sihtrühm: Oh, no sorry. ANDI PENG: OK, nii et olgem kõndida läbi selle koodi. Nii et kui sa üritad lisada midagi peale järjekorda, kenas nii, et pea juhtub olla siin, see on väga lihtne meile minge lõpuni lisada midagi, eks? Aga mõte järjekord on et pea saab tegelikult dünaamiliselt muutuda sõltuvalt kus me tahan algust meie q olema, ning sellistena saba Samuti muutub. 

Ja nii kujutan ette, et see ei olnud järjekorras, vaid see oli järjekorras. Oletame, et juht on siinsamas. Oletame, et meie järjekorda nägi välja selline. Kui me tahtsime minna, kus Alguses rida, oletame me nihkunud pea Sel moel ja suurused siin. 

Nüüd tahame midagi lisada Selles järjekorras, kuid kui poisid näevad, see ei ole nii lihtne kui lihtsalt lisada iganes on pärast suurus sest siis otsa piire meie tegelik massiivi. Kus me tahame tõesti lisada siin. See on ilu järjekorras on see, et meile, visuaalselt see Tundub, et liin läheb niimoodi, aga kui salvestatud andmete struktuur, Annavad see nii nagu tsüklis. See liik murtakse ees samamoodi et liin võib ka pakkima ümber sõltuvalt kus sa tahan rea algusesse olla. Ja kui me võtame odavnema siin, olgem öelda tahtsime luua funktsiooni nimetatakse Lisa järjekorda. Me tahtsime, et lisada int n sellesse q. Kui q.size q-- me kutsume, et meie andmed structure-- kui meie queue.size ei võrdne võimsus või kui see on vähem kui võimsust, q.strings on massiivi meie q. Me läheme seatud mis võrdub q.heads, mis on siinsamas, pluss q.size moodul poolt võimsust, mis murrab meid tagasi siinkandis. 

Nii selles näites indeksi Pea on 1, eks? Indeks suurus on 0, 1, 2, 3, 4. Nii saame teha 1 pluss 4 moodulit meie suutlikkust, mis on 5. Mida see meile annab? Mis on indeks, mis väljub seda? 

Sihtrühm: 0. 

ANDI PENG: 0, mis juhtub olema just siin, ja nii me tahame, et oleks võimalik et lisada siin. Ja nii see võrrand siin mingi lihtsalt töötab iga numbrid sõltuvalt sellest, kus teie pea ja oma suurus on. Kui sa tead, mida need asjad on, sa tead täpselt, kuhu soovite lisada kõik, mis on pärast oma järjekorda. Kas see mõtet kõigile? 

Ma tean, et mingi aju teaser eriti kuna see tuli pärast oma viktoriini. Aga loodetavasti kõik Nüüd saan aru, miks see lahendus või selle funktsiooni on nii, et see on. Igaüks natuke ebaselge, mis? OKEI. 

Ja nii nüüd, kui te tahtsin dequeue, seda on koht, kus meie peas oleks nihkub sest kui me dequeue, me ei stardi lõppu q. Me tahame võtta pea maha, eks? Nii tõttu, peas on muutu, ja sellepärast, kui teil Lisa järjekorda, sul jälgida kus oma peaga ja oma suurus oleksid võimelised sisestada õigesse asendisse. 

Ja nii, kui sa dequeue, Ma ka pseudokoodi välja. Julgelt kui soovite püüda kodeerimine selle välja. Sa tahad, et liigutada pea, eks? Kui ma tahtsin dequeue, ma liiguksid pea üle. See oleks peas. 

Ja meie praegune suurus oleks lahutada, sest meil ei ole enam on neli elementi massiivi. Meil on ainult kolm, ja siis me tahame tagasi iganes oli ladestunud pea, sest me tahame seda väärtust, nii väga sarnane pinu. Just te võtate alates erinevas kohas ja sa pead ümber jaotada pointer et teises kohas kui tulemus. Loogiliselt igaüks jälgida? Hea. 

OK, nii et me ei kavatse rääkida natuke põhjalikum umbes ahelloendid sest nad on väga väärtuslik Teile käigus sel nädalal psets. Ahelloendid, kui poisid ei mäleta, kõik nad on on sõlmed, mis on sõlmede teatud väärtused nii väärtus ja osuti mis on omavahel ühendatud need suunanäitajaks. Ja nii struct kuidas loome sõlme siin on meil on int n, mis on iganes väärtus poest või string n või mis iganes soovid nimetame seda, süsi star n. Struct node täht, mis on pointer et sa tahad olla iga sõlme, sa lähed on, et pointer punkti suunas kõrval. Sul on head on seotud loend, mis on läheb viitavad ülejäänud väärtused nii edasi ja nii edasi kuni sa lõpuks jõuda lõpuni. Ja see viimane sõlm on lihtsalt läheb ole kursorit. See saab osutada null, ja see on kui sa tead, olete tabanud lõpuks oma ahelloendid on siis, kui viimane pointer ei viita midagi. 

Nii et me läheme veidi rohkem sügavus kohta, kuidas keegi võib-olla otsi ahelloend. Pea meeles, mida on mõned puudused ahelloendid salmid massiivi osas otsingud. Hulgaliselt saate Kahendotsingupuu, kuid miks ei saa sa seda teha ahelloend? 

Sihtrühm: Sest nad kõik ühendatud, kuid sa ei tea täpselt, kus [Kuuldamatu]. 

ANDI PENG: Jah, täpselt nii, mäletan et sära massiivi oli see, et meil oli muutmälu, kus kui ma tahtsin väärtuse indeksi kuus, võin öelda indeks kuus, mulle, et väärtus. Ja seda sellepärast, massiivid on järjestatud saadakse katkematu space mälu ühes kohas, samas Selline ahelloendid on juhuslikult segamini kogu, ja ainus viis sa leiad ühe on läbi osuti, mis ütleb, aadress, kus see järgmine sõlm. 

Ja nii selle tulemusena ainus viis otsida ahelloend on lineaarne otsing. Kuna ma ei tea täpselt, kus 12. väärtusega seotud nimekiri on, Mul on läbida tervikuna Selle ahelloendid üks ühe peast esimese sõlme, Teise sõlme, kolmandale sõlme, täiesti alla, kuni ma lõpuks saada kust selle sõlme Otsin on. Ja nii selles mõttes, otsi kohta ahelloend on alati n. See on alati n. See on alati lineaarne aeg. 

Ja nii kood, milles meil rakendada seda, ja see on natuke uue kutid, sest sa poisid on tõesti ei rääkinud või kunagi näinud viiteid, kuidas Otsige vihjeid, nii me käime läbi see väga aeglaselt. Nii bool otsing, õige, Oletame, me tahame luua funktsiooni nimetatakse otsing, mis tagastab true Kui olete leidnud väärtus sees seotud nimekirja ning ta naaseb vale teisiti. Sõlme star nimekiri on Praegu lihtsalt kursor esimese punkti oma ahelloendid. int n on väärtus, et sa oled otsivad selles nimekirjas. 

Nii sõlme star pointer võrdub nimekirja. See tähendab, et me, millega ja luua pointer Seda esimest sõlme sisemusse nimekirja. Igaüks minuga? Nii et kui me olime minna siia tagasi, oleksin vormindatud osuti, mis viitab juht iganes see nimekiri on. 

Ja siis kui sa siin, samas osuti ei võrdu null, nii et on silmus, kus me oleme läheb hiljem liiklevad Ülejäänud meie nimekirjas, sest mida juhtub, kui osuti võrdub null? Me teame, et me have-- 

Sihtrühm: [kuuldamatu] 

ANDI PENG: Täpselt, nii et me teame, et oleme jõudnud nimekirja, eks? Kui sa lähed tagasi siin, iga sõlm tuleks juhtides teise sõlme ja nii edasi ja nii edasi kuni jõuad lõpuks saba oma ahelloendid, mis on viit, et lihtsalt ei viita kusagil peale no. Ja nii sa põhimõtteliselt teada, et Sinu loend on ikka seal üleval kuni osuti ei võrdu null, sest kui see võrdub null, sa tead, et seal ei ole rohkem asju. 

Nii et on silmus, kus me oleme läheb on tegelik otsing. Ja kui pointer-- näete sellist nool funktsioon olemas? Nii et kui osuti osutab n, kui osutiga kell n võrdub võrdub n, et tähendab, et kui kursorit, et sa oled otsivad otsas iga sõlm on tegelikult võrdub otsite, siis soovite naasta tõsi. Ühesõnaga, kui sa oled sõlmes, et on väärtus, mida te otsite, sa tead, et sa oled olnud edukalt otsida. 

Muidu soovite seada kursor järgmisele sõlme. Just seda rida siin teeb. Pointer võrdub pointer kõrval. Igaüks, kuidas see töötab? 

Ja sisuliselt sa lähed lihtsalt läbida kogu nimekirja ennistamist kursor iga kord enne sa lõpuks tabas nimekirja lõppu. Ja sa tead, et ei ole rohkem sõlmede otsida, ja siis saate tagasi vale sest sa tead, et oh, noh, kui ma olen suutnud leida läbi kogu nimekiri. Kui käesoleva näite, kui ma tahtsin otsima väärtuses 10, ja ma hakkan eesotsas, ja Ma otsin täiesti alla, ja ma lõpuks sain selle, mis osuti, mis juhib tühjaks, Ma tean, et jama, ma arvan, et 10 ei ole seda nimekirja, sest ma ei suutnud seda leida. Ja Kõht lõpus nimekirjast. Ja sel juhul sa tead Ma lähen tagasi vale. 

Lubage, et õlil natuke. See on päris oluline oma pset. Loogika on väga lihtne, ehk süntaktiliselt lihtsalt rakendamisel. Tahate teha Veenduge, et saate aru. Cool. 

OK, nii et kui me oleks sisestades sõlmed, õigus, loendisse, sest mäletan Mis on see, mis kasu võttes ahelloend versus massiivi nii ladustamise? 

Sihtrühm: See on dünaamiline, nii et see on lihtsam mina-- 

ANDI PENG: Täpselt, nii et see on dünaamiline, mis tähendab, et seda saab laiendada ja kahaneb sõltuvalt kasutaja vajadustest. Ja nii, selles mõttes, et me ei vaja raisata tarbetu mälu, sest ma kui ma ei tea, kui palju väärtusi ma tahan salvestada, siis ei ole mõtet mind luua massiivi sest kui ma tahan salvestada 10 väärtused ja ma luua massiivi 1000, mis on palju raisatud mälu, eraldatud. Sellepärast me tahame kasutada seotud nimekirja saaks dünaamiliselt muuta või vähendada meie suurus. 

Ja nii, et teeb sisestamise natuke keerulisem. Kuna me ei saa juhuslikult juurde elemendid nii, et me oleks massiivi. Kui ma tahan lisada element arvesse seitsmenda indeks, Ma lihtsalt ei aseta arvesse seitsmenda indeks. On ahelloend, see ei ole päris töö nii lihtsalt, ja nii kui tahtsime sisestada üks siin seotud nimekirja, visuaalselt, et see on väga lihtne näha. Tahame lihtsalt sisestada see seal, kohe alguses nimekirja, kohe pärast pea. 

Aga kuidas on meil võimalik loovutada suunanäitajaks on natuke keerdunud või loogiliselt, on mõttekas, kuid soovite veenduda, et teil on see täiesti alla, kuna viimane asi, mida sa tahad on ümberhindamist pointer nii, et me teeme siin. Kui te apparent pointer pealaest 1 siis kõik äkki ülejäänud ahelloendid on kadunud, sest sa ei ole tegelikult loodud ajutine midagi. See on osutanud 2. Kui te ümber jaotada kursorit, siis Ülejäänud oma nimekirja täiesti kadunud. Nii et sa tahad olla väga, väga ettevaatlik siin kõigepealt määrata pointer alates iganes tahan lisada kõikjal soovite, ja siis saab apparent ülejäänud oma nimekirja. 

Nii et see kehtib kõikjal sa üritad lisada. Kui soovite sisestada juures pea, kui soovite vastata siin Kui soovite lisada juures lõpus, noh, ma lõpuks arvan, et sul oleks lihtsalt ei viida, kuid sa soovite veenduda, et te ei kaotavad oma ülejäänud nimekirja. Tahad alati veenduda endale sõlme on suunatud suunas iganes tahan lisada, ja siis saad lisada aheldamine kohta. Igaüks selge? 

See saab olema üks tegelikke probleeme. Üks peamisi küsimusi sa lähed on oma pset on see, et sa lähed, et proovida luua ahelloend ja lisada asju aga siis lihtsalt kaotada ülejäänud seotud nimekirja. Ja sa lähed on, ma ei tea, miks see toimub? Ja see valu läbi minna ja otsida kõiki oma suunanäitajaks. 

Ja ma garanteerin teile selle pset, kirjutamise ja joonistamise need sõlmed välja on väga, väga kasulik. Nii saab täiesti jälgida kus kõik oma suunanäitajaks on, mis toimub vale, kus kõik oma sõlmed, mida sa pead tegema, et pääseda või sisestada või kustutada või ühtegi neist. Igaüks hea on? Cool. 

Nii et kui me tahtsime vaadata koodi? Oh, ma ei tea, kas me näete the-- OK, nii et ülaosas kõik see on funktsioon nimega insert, kus me tahame lisada int n arvesse seotud nimekirja. Me läheme suudad seda. See on palju koodi, palju uusi süntaks. Me oleme OK. 

Nii up tipus, kui see me tahame luua midagi Mida me peame tegema, eriti kui teil tahad seda ei tohi hoida virnas kuid hunnik? Läheme malloc, eks? Nii et me läheme luua pointer. Sõlme, pointer, uus võrdsete malloc suurust sõlme sest me tahame, et sõlm luua. Me soovime, et summa mälu, et sõlm kulub jaotatava jaoks loomiseks uute sõlme. 

Ja siis me ei kavatse vaadata, kas uue võrdsete võrdub null. Pea meeles, mida me ütlesime? Mida iganes sa malloc, mida tuleb alati teha? Alati tuleb vaadata, kas see on null. 

Näiteks, kui teie operatsioonisüsteemi Süsteem oli täiesti täis, Kui te ei ole enam mälu kõik ja püüad malloc, oleks tagasi null teile. Ja kui sa püüad seda kasutada kui see oli juhtides tühjaks, sa ei kavatse võimalik juurdepääsu sellele teabele. Ja nii, nagu me tahtsime teha Veenduge, et iga kord, kui sa oled mallocing, sa oled alati kontrollida, et näha, kas et mälu antakse teile on null. Ja kui see ei ole, siis saame edasi liikuda kohta koos kogu meie koodi. 

Nii et me läheme initsialiseerida uus sõlm. Me teeme uue n võrdne n. Ja siis me teeme seada uusi kursorit uus to null sest praegu me seda ei tee taha midagi selle eest osutada. Me ei tea, kus see saab panna teid, ja siis, kui me tahame lisab selle juht, siis saame ümber jaotada kursor pea. Kas kõik järgivad loogikat kus see toimub? 

Kõik me teeme on loomisel uus sõlm, milles kursorit tühjaks, ja siis ümberjagamise see pähe, kui me tea me tahame lisada see eesotsas. Ja siis pea läheb kohakuti, et uus sõlm. Igaüks OK on? 

Nii et see on kaheastmeline protsess. Sul Esmalt määrake iganes sa luua. Määra et kursor viide, ja siis saab omamoodi apparent Esimeses pointer ja suunake see kaasa uue sõlme. Kui sa tahad lisada see, Selle loogika läheb paika. 

See on selline nagu määrates Ajutise muutujaid. Pea meeles, et sul veenduda, et teil ei kaota peal kui sa vahetada. Sa tahad teha kindel, et teil on Ajutise muutuja sellist hoiab jälgida, kui see asi on säilitatud nii, et teil ei kaota väärtust käigus ja nagu jamada sellega. 

OK, nii et kood on siin. Te heita pilk peale osa. See on seal. 

Nii et ma arvan, kuidas Selle erinevad, kui me tahtsime lisada keskele või lõppu? Kas kellelgi on aimu, milline on pseudokoodi kui loogilist viide et me võtaks, kui me tahtsime lisada see keskel? Nii et kui me tahame, et lisab selle Pea kõik me teeme, on luua uus sõlm. Seame kursorit selle uus sõlm iganes pähe, ja siis seadsime juht Uue sõlme, eks? Kui me tahame lisada selle keskel nimekirja, mis oleks me peame tegema? 

Sihtrühm: ikkagi olla sarnane protsess samasuguse määrates viit ja Seejärel määrates, et osuti, aga oleks meil leida seal. 

ANDI PENG: Täpselt nii täpselt sama protsessi peale sinu on leida, kus täpselt sa tahan, et uue viida minema, nii et kui ma tahan lisada Keset seotud list-- OK, Oletame, et on meie ahelloendid. Kui me tahame, et lisada see siin, me läheme uue sõlme. Me läheme malloc. Me läheme uue sõlme. Me läheme loovutada pointer selle sõlme siin. 

Aga probleem, mis erineb kust on pea on see, et me teadsime täpselt kus pea. See oli kohe esimene, eks? Aga siin on meil jälgida kus me sisestamist. Kui me sisestamist meie sõlme siin, meil veenduda, et üks eelmise sellele sõlme on see, et omistab pointer. Nii siis on selline jälgida kahte asja. Kui teil jälgida, kui see sõlme praegu on sisestamisel arvesse. Sul on ka jälgida, kui Eelmise sõlme, et te vaatate Samuti oli seal. Igaüks hea on? OKEI. 

Kuidas panemist lõpus? Kui ma tahtsin lisada siin-- kui ma tahtsin lisada uue tipu lõpu nimekirja, kuidas võiks ma minna seda teed, et? Sihtrühm: Nii praegu on Viimane on osutanud null. ANDI PENG: Jah. Täpselt nii see Praegu on märgitud teada, ja nii ma arvan, selles mõttes, et see on väga lihtne lõppu lisada nimekirja. Kõik, mida pead tegema, on määrata see võrdne tühjaks ja siis buum. Just sinna, väga lihtne. Väga lihtne. 

Väga sarnane pea, kuid loogiliselt teile soovite veenduda, et sammud te võtate poole teed kõik selle, Te jälgite mööda. See on väga lihtne, keskel oma koodi, sattuda kohta, oh, mul on nii palju viiteid. Ma ei tea, kus midagi osutades. Ma isegi ei tea, mis sõlme ma olen. Mis toimub? 

Relax, rahune maha, hinga sügavalt sisse. Joonista välja oma ahelloendid. Kui te ütlete, ma tean, kus täpselt Mul on vaja sisestada seda arvesse ja ma tean täpselt, kuidas ümber jaotada minu suunanäitajaks, palju, palju lihtsam pilt out-- palju, palju kergem ole eksida vigu oma koodi. Igaüks OK on? OKEI. 

Nii et ma arvan, et mõiste, et me ei ole tõesti rääkisime enne nüüd, ja ma arvan, et sa ilmselt ei esine palju yet-- see on selline arenenud concept-- on see, et me tegelikult on andmed struktuuri nimetatakse kahekordselt seotud nimekirja. Nii nagu te poisid ei vaata, kõik me teeme on luua tegelik väärtus, extra osuti iga meie tippe mis viitab ka eelmise sõlme. Nii et mitte ainult meil meie sõlmede juhtida järgmise üks. Nad juhivad tähelepanu ka eelmine. Ma ei pea neid kahte just nüüd. 

Nii siis on kett mis võib liigutada mõlemas suunas, ja siis see on natuke lihtsam loogiliselt jälgida mööda. Nagu siin asemel jälgida, oh, ma on teada, et see sõlm üks, mis ma pean ümber jaotada, Ma lihtsalt minna siin ja lihtsalt tõmmake eelmisest. Siis ma tean täpselt, kus mis on, ja siis ei ole liiklemiseks tervikuna on seotud nimekirja. See on natuke lihtsam. 

Aga kui sellist, siis on kahekordselt summa suunanäitajaks, see on kaks korda rohkem mälu. See on palju viiteid jälgida. See on natuke keerulisem, kuid see on natuke kasutajasõbralikumaks sõltuvalt mida sa üritad saavutada. 

Nii seda tüüpi andmeid struktuuri täiesti olemas, ja struktuur on väga, väga Lihtne peale kõik sul on, selle asemel, et lihtsalt kursor kõrval, teil ka viit eelmist. See on kõik, vahe oli. Igaüks hea on? Cool. 

Olgu, nii et nüüd ma olen tõesti kulutada ilmselt nagu 15-20 minutit või lahtiselt ülejäänud aja osas räägime hash tabeleid. Kui paljud kutid lugenud pset5 spec? Hea küll, hea. See on suurem kui 50% normaalselt. See on OK. 

Nii nagu te poisid näevad, sa oled väljakutse pset5 saab rakendada sõnastik kus sisestad üle 140.000 sõnad et me anname teile ja õigekirja kontroll seda vastu kogu tekst. Anname juhuslik tükki kirjandust. Anname Odüsseia. Anname Ilias. Anname Austin Powers. 

Ja teie väljakutse on õigekirja kontrolli iga sõna kõigis nende sõnastikud sisuliselt meie õigekirjakontrolli. Ja nii seal on mõned osad luua selle pset, Alguses sa tahad olla suudab tegelikult koormus kõik sõnad oma sõnastik, ja siis taha olla võimelised õigekirja kontrolli neid kõiki. Ja nii, nagu sa lähed vaja andmestruktuur, et seda teha kiiresti ja tõhusalt ja dünaamiliselt. 

Nii et ma arvan, et kõige lihtsam kuidas seda teha, siis ilmselt luua massiivi, eks? Lihtsaim viis ladustamiseks on teil saab luua massiivi 140.000 sõnad ja lihtsalt panna need kõik olemas ja siis läbida neid Kahendotsingupuu või valikute või Mitte-- kahju, et sorteerimiskeskuses. Teil on võimalik järjestada neid ja siis läbida neid poolt Kahendotsingupuu või lihtsalt lineaarne otsing ja lihtsalt lõplik sõna, kuid mis võtab tohutu mälu, ja see ei ole väga tõhus. 

Ja nii me ei kavatse hakata räägi, kuidas muuta Meie sõiduaega tõhusamaks. Ja meie eesmärk on saada konstantse ajaga, kus see on peaaegu nagu massiivid, kus sul on hetkeline juurdepääs. Kui ma tahtsin otsida midagi, Ma tahan, et oleks võimalik lihtsalt, Buumi leida täpselt, ja tõmmake see välja. Ja nii struktuuri, mis saadame muutumas väga lähedal to pääse konstantse aega, see Püha Graal programmeerimise pidev aega nimetatakse hash tabelit. Ja nii David varem mainitud [Kuuldamatu] natuke loengus, aga me läheme tõesti sukelduda sügavale sel nädalal tükk, mis on seoses kuidas hash tabelis toimib. 

Nii nii, et räsi Tabelis teoseid, näiteks kui ma tahtsin salvestada kamp sõnadega, kamp sõna inglise keeles, Ma võiks teoreetiliselt panna banaan, õun, kiivi, mango, paar, ja cantaloupe kõik lihtsalt massiivi. Nad võiksid kõik sobib ja võib leida. Oleks selline valu Otsige ja juurdepääsu, kuid lihtsam viis seda teha on et suudame luua tegelikult struktuur nimetatakse hash tabelit, kus me hash. Meil töötavad kõik meie võtmeid räsi funktsioon, võrrand, mis muudab neid kõiki mingi väärtus et siis saame salvestada peale sisuliselt massiivi seotud nimekirja. 

Ja nii siin, kui me tahtsime salvestada inglise sõnad me võiks lihtsalt, ma ei tean, muuta kõik esimesed tähed mingisugune hulk. Ja nii, kui näiteks tahtsin A sünonüüm apple-- või indeksiga 0 ja B sünonüümideks 1, meil on 26 kirjed et lihtsalt hoida kõik tähed tähestiku, et hakkame koos. Ja siis saame Apple on indeks 0. Saame banaani indeks 1, melon on indeks 2, ja nii edasi ja nii edasi. Ja nii kui ma tahtsin otsida minu hash tabelit ja juurdepääsu õun, Ma tean, et apple algab A, ja ma tean täpselt et see peab olema ja hash laua indeks 0, sest Funktsiooni varem määratud. 

Nii et ma ei tea, me oleme kasutaja programm, kus Teil tuleb tasuda koos arbitrarily-- ei omavoliliselt üritab mõtlikult arvan hea võrrandid saaks levida välja kõik oma väärtusi nii nad saavad hõlpsasti see hiljem koos nagu võrrand mis sa, ise tead. Nii selles mõttes kui ma tahtsin minna mango, ma tean, oh, see algab m. See peab olema indeks 12. Mul ei ole otsida midagi. Ma tean exactly-- ma võiks lihtsalt minna indeks 12 ja tõmmake see välja. 

Igaüks selge, kuidas hash tabeli funktsioon toimib? See on selline lihtsalt keerulisem massiivi. See on kõik see. OKEI. 

Nii et ma arvan, et me joosta see küsimus, mida juhtub, kui teil on mitu asja et teile sama indeksit? Nii öelda meie funktsioon, kõik see ei olnud võtta, et esimene täht ja keerake seda arvesse vastavate 0 kuni 25 indeks. See on täiesti trahvi, kui sul on ainult üks iga. Aga teine ​​hakkad millel on rohkem, sa oled läheb on, mida nimetatakse kokkupõrget. 

Nii et kui ma püüan sisestada matta ümber hash tabel, mis on juba banaani peal, Mis juhtub, kui üritate sisestada, et? Halbu asju, sest banaan juba olemas indeksi et sa tahad seda säilitada. Berry selline on nagu, ah, mida ma pean tegema? Ma ei tea, kuhu minna. Kuidas lahendada? 

Ja nii kutid liiki vaata me seda keeruline asi kus saame sellist tegelikult luua ahelloendid meie massiivid. Ja nii on kõige lihtsam viis mõtlema sellele, kõik hash tabel on massiivi seotud nimekirju. Ja nii, selles mõttes, sa pead see ilus massiivi osuti, ja siis iga kursorit et väärtus nimetatud indeksis, saab tegelikult viidata muid asju. Ja siis on kõik need eraldi ketid maha tulemata üks suur massiiv. 

Ja nii siin, kui ma tahtsin lisada marja-, Ma tean, OK, ma lähen sisend läbi minu hash funktsiooni. Ma lähen lõpuks indeks 1, ja siis ma lähen saama vaid väiksemad alagrupis seda hiiglane 140000-sõna sõnastikku. Ja siis ma lihtsalt otsida läbi 1/26 sellest. 

Ja nii siis ma lihtsalt sisestada marja kas enne või pärast banaani sel juhul? Pärast, eks? Ja nii sa lähed tahan sisestada selle sõlme pärast banaan, ja nii sa lähed sisestada kell saba, mis on seotud nimekirja. Ma lähen tagasi Selle eelmise slaidi nii kutid saavad näha, kuidas hash funktsiooni toimib. 

Nii hash funktsiooni on see võrrand et näed selline oma panus läbi saada olenemata indeks soovite määrata selle suunas. Ja nii, selles näites, kes kõik tahtsime teha oli võtta esimene täht, keerata, et võtta indeks, siis me saab salvestada et meie hash funktsiooni. Kõik me teeme siin me oleme ümberehitamiseks esimene täht. Nii keykey [0] on lihtsalt esimese tähe mis tahes string meil oli, me möödaminnes. Me muutma seda, et ülemine ja me lahutades poolt suur- A, seega kõik, mis teeb annab meile mitmeid kus saame hash meie väärtuste peale. 

Ja siis me läheme tagasi hash moodul suurus. Ole väga ettevaatlik sest teoreetiliselt siit Sinu räsi väärtus võib olla lõpmatu. See võiks lihtsalt minna ja edasi ja edasi. See võiks olla mõned tõesti, tõesti suur väärtus, kuid kuna teie hash tabelit, et olete loonud ainult 26 indeksid, sa tahad teha kindel, et teie modulusing nii, et teil ei run-- see on sama asja nagu oma queue-- nii et sa ei jookse ära alt oma hash funktsiooni. 

Tahad murrab ta tagasi umbes samamoodi [kuuldamatu] kui sul oli nagu väga, väga suur täht, sa ei taha, et lihtsalt joosta ära lõpuks. Sama asi siin, sa tahad teha kindel, see ei tööta otsast maha pakkimine ümber ülemise tabeli. Nii et see on lihtsalt väga Lihtne hash funktsiooni. Kõik, mis tegin oli võtta esimese kirjas iganes meie panus oli ja keerake seda arvesse indeks, mis me võiks panna meie hash tabelit. 

Jah, ja nii nagu ma enne ütlesin, nii, et me lahendada kokkupõrked Meie hash tabeleid võttes, mida me nimetame, ühendamine. Nii et kui sa püüad lisada mitu sõnad, mis algavad sama asi, sa lähed on üks räsi. Avokaadod ja õuna, kui olete kestab see läbi meie hash funktsiooni, annan sulle sama numbrit, mitmeid 0. Ja nii nagu me lahendada see et me saame tegelikult omamoodi siduda need koos läbi ahelloendid. 

Ja nii selles mõttes, kutid näen sellist kuidas andmestruktuurid, et me oleme, millega varem nagu rosina seotud nimekirja lahke on võimalik kokku ühte. Ja siis saate luua palju tõhusam andmestruktuurid et saab hakkama suuremaid summasid andmed, mis dünaamiliselt suurust sõltuvalt oma vajadustele. Igaüks selge? Igaüks omamoodi selge mis juhtub siin? 

Kui ma tahtsin insert-- mida on puu, mis algab, ma ei tea, B, välja arvatud marja-, banaan. 

Sihtrühm: Blackberry. 

ANDI PENG: Blackberry, murakas. Kust Blackberry minna siin? Noh, me tegelikult ei ole järjestatud see veel, kuid teoreetiliselt kui me tahtnud seda tähestikulises järjekorras, kus peaks Blackberry minna? 

Sihtrühm: [kuuldamatu] 

ANDI PENG: Täpselt pärast siin, eks? Aga kuna see on väga raske reorder-- Ma arvan, et see on kuni teil poisid. Te saate täielikult rakendada iganes sa tahad. Tõhusama tehes seda ehk oleks sortida seotud nimekirjast tähestikulises järjekorras ja nii kui sa oled sisestades asju, mida soovid olla kindel, pange arvesse tähestikulises järjekorras et siis, kui sa oled üritan otsida neid, sa ei pea läbida kõike. Sa tead täpselt, kus see on, ja see on lihtsam. 

Aga kui sa selline on asju segamini juhuslikult, sa ikka lähed on läbida niikuinii. Ja nii kui ma tahtsin lihtsalt lisada Blackberry siin ja ma tahtsin otsida see, ma tean, oh, murakas peab algama indeks 1, nii et ma tean silmapilkselt lihtsalt otsida 1. Ja siis ma ei saa sellist läbida seotud nimekirja kuni saan Blackberry, ja then-- jah? 

Sihtrühm: Kui sa üritad create-- Ma arvan, et niimoodi on väga lihtne hash funktsiooni. Ja kui me tahtsime teha mitmekihilisuse, et nagu, OK, me tahame eraldub nagu kõik tähestiku tähti ja siis jälle meeldima teine ​​komplekt tähtedest tähed selles, me panna nagu hash Tabelis jooksul hash tabelit, või nagu funktsiooni funktsioon? Või on selle-- 

ANDI PENG: Nii et teie hash funktsioon-- oma hash tabelis võib olla nii suur kui sa tahad seda. Nii selles mõttes, ma arvasin see oli väga lihtne, väga lihtne minu jaoks justkui põhineb kirjadele esimese sõna. Ja nii seal on ainult 26 võimalusi. Võin ainult saada 26 valikutest 0 kuni 25, kuna nad saavad ainult alustada A-st Z aga kui sa tahtsid lisada ehk rohkem keerukust või kiiremini joosta aega oma hash tabelit, mida absoluutselt saab teha igasuguseid asju. Võite teha oma võrrandit, mis annab teile rohkem jaotus oma sõnad, siis, kui te otsite, see saab olema kiirem. 

See on täiesti su poisid kuidas sa tahad seda rakendama. Mõtle seda lihtsalt ämbrid. Kui ma tahtsin olla 26 ämbrid, ma lähen sorteerida asju neisse ämbrid. Aga ma lähen on kamp kraami iga ämber, nii et kui sa tahad teha seda kiiremaks ja tõhusamaks, andke mulle sada ämbrid. 

Aga siis sa pead välja mõtlema viis sorteerida asju, et nad oleksid õiges kopp nad peaksid olema. Aga siis, kui sa tegelikult tahan vaadata, et kopp, see on palju kiirem, kuna seal on vähem kraami iga ämber. Ja nii, jah, see on tegelikult trikk kutid pset5 on see, et sa pead olema vaidlustas lihtsalt luua kõik, mis on kõige tõhusam funktsiooni võite mõelda, et olla võimalik salvestada ja vaadata neid väärtusi. 

Täiesti kuni kutid aga sa tahad seda teha, aga see on tõesti hea koht. Et selline loogika sul tahan hakata mõtlema on hästi, miks ma ei tee enam ämbrid. Ja siis ma pean otsima vähem asju, ja siis äkki ma on erinev hash funktsiooni. 

Jah, seal on palju võimalusi, kuidas seda teha pset, mõned on teistest kiiremini. Ma täiesti läheb lihtsalt näha, kuidas kiire oli kiireim kutid oleks võimalik saada oma funktsioonide tööd. OK, kõik hea ühendamine ja hash tabeleid? See on tegelikult nagu väga lihtne mõiste kui sa mõtle selle peale. Kõik see on on eraldades iganes Sinu sisendid on kopad, sorteerimist, ja siis otsida loetleb, et seal on seostatud. 

Cool. Olgu, nüüd on teistmoodi andmete struktuur, mis nimetatakse puu. Lähme sisse ja rääkida üritab mis on selgelt erinevad, aga samasse kategooriasse. Sisuliselt kõik puud on selle asemel korraldamise andmete lineaarselt et hash tabelis does-- sa teate, see sai ülemiseks ja alumiseks ja siis mingi link välja see-- Puu on top kuhu helistada juur, ja siis on lehed kõik selle ümber. 

Ja nii kõik olete siin on lihtsalt ülemise sõlme mis osutab muude sõlmede, et punktid rohkem sõlmed, ja nii edasi ja nii edasi. Ja nii sa lihtsalt osadeks oksad. See on lihtsalt teistmoodi korraldada andmed, ja kuna me nimetame seda puud, kutid lihtsalt-- see on lihtsalt modelleeritud välja nägema puu. Sellepärast me nimetame seda puud. 

Hash tabel näeb välja nagu tabelis. Puu lihtsalt näeb välja nagu puu. Kõik see on on eraldi korraldamise viis sõlmed sõltuvalt sellest, mida teie vajadused. 

Nii et teil on root ja siis on lehed. Nii, et me saame eriti mõtle selle peale on Binääripuu, Binääripuu on lihtsalt konkreetset tüüpi puu kus iga sõlme ainult punktid to, maks, kaks sõlmed. Ja nii siin on erinevad sümmeetria oma puu mis muudab lihtsamaks liiki otsima millise väärtustab olete, sest siis on alati vasakule või paremale. Seal on kunagi nagu vasakul kolmas vasakul või 4. vasakult. See on lihtsalt sul on vasakul ja paremal ja võite otsida kumbagi. Ja miks on see kasulik? Nii, et see on kasulik on kui otsite otsida väärtusi, eks? Selle asemel, et rakendada binaarne otsida viga massiiv, kui sa tahad, et oleks võimalik sisestada sõlmed ja ära sõlmi tahte ja ka säilitada otsing võimekust Kahendotsingupuu. Nii et sel viisil, et me oleme omamoodi tricking-- mäletan, kui me ütles ahelloendid saa Kahendotsingupuu? Me mingi luua andmebaasi struktuuri mis trikke, et tööle jääda. 

Ja seda sellepärast, et ahelloendid on lineaarne, nad ainult siduda üksteise järel. Saame selline on teistsuguse viiteid Sel hetkel erinevate sõlmede mis võib aidata meil otsida. Ja nii siin, kui ma tahtsin on kahendotsingupuu, Ma tean, et mu keskmine kui 55. Ma lihtsalt luua, et kui mu keskmine, nagu minu juure, ja siis ma lähen väärtuste eralduma ta. 

Nii et siin, kui ma lähen otsima väärtus 66, võin hakata 55. On 66 üle 55? Jah, see on, nii et ma tean, et ma mus otsida i n õige kursori selle puu. Ma lähen 77. OK, on ​​66 alla või üle 77? See on vähem kui, et sa tead, oh, mis peab olema vasakul sõlme. 

Ja nii siin me sellist säilitamine kõik suuri asju massiivid, nii nagu dünaamiline saneerimist objektide, olles võimalik sisestada ja kustutada tahtmist, ilma et peaks muretsema fikseeritud palju ruumi. Meil on veel säilitada kõik neid imelisi asju samas on võimalik säilitada sisse ja otsida aeg Kahendotsingupuu et meil oli ainult varem võimalik saada fraasi. 

Cool andmete struktuuri, millist keeruline rakendada, sõlme. Nagu näete, kõik see on struct sõlme on see, et teil on vasakul ja õigus pointer. See on kõik see. Nii et pigem lihtsalt võttes x või eelmise. Sul on vasakul või paremal, ning seejärel saab omamoodi ühendame aga sa nii valida. 

OK, me tegelikult toimub lihtsalt võtta paar minutit. Nii et me läheme tagasi siia. Nagu ma ütlesin varem, Ma nagu selgitas loogika, kuidas me oleks otsida seda. Me läheme püüdma pseudocoding see välja näha kui saame mingi kohaldada Sama loogika Kahendotsingupuu Erinevat liiki andmete struktuuri. Kui te tahate võtta nagu paar minutit ainult mõelda sellele. OKEI. Olgu, ma lähen tegelikult lihtsalt teile the-- ole, me räägime pseudokoodi esimene. Nii ei keegi taha anda torkehaav, mida Esimene asi, mida sa teha tahad, kui sa oled hakanud välja otsimine on? Kui me otsime väärtus 66, mis on Esimene asi, mida me tahame teha, kui tahame Kahendotsingupuu see puu? 

Sihtrühm: Sa tahad otsida õige ja vaatame vasakule ja vaata [kuuldamatu] suurem number. 

ANDI PENG: Jah, täpselt. Nii et sa lähed vaatama oma juurte. Seal on palju võimalusi, kuidas helistada see, teie vanem sõlme inimesed ütlevad. Mulle meeldib öelda root sest see on nagu puu juur. Sa lähed vaadata Sinu Juursõlme, ja sa oled näeme on 66 suurem või väiksem kui 55. Ja kui see on suurem kui, noh, see on suurem kui kui me tahame vaadata? Kus me tahame leida nüüd, eks? Me tahame, et otsida paremal pool seda puud. 

Nii et meil on, Sobivalt pointer, mis osutab paremale. Ja nii siis saame meie uus root olema 77. Me lihtsalt minna sinna, kus osuti osutab. Noh, oh, siin me oleme hakanud kell 77, ja me saame lihtsalt Selleks rekursiivselt uuesti ja uuesti. Sel moel saad liiki kohta on funktsiooni. Sul on võimalus otsida, et te lihtsalt korrata ikka ja jälle ja jälle, sõltuvalt sellest, kus sa tahad otsida kuni sa lõpuks saada väärtus mis te otsite. On loogiline? 

Ma olen umbes näidata teile tegelik kood, ja see on palju koodi. Ei ole vaja närvi. Me räägime läbi. 

Tegelikult mitte. See oli lihtsalt pseudokoodi. OK, see oli lihtsalt pseudokoodi, mis on natuke keeruline, aga see on täiesti korras. Igaüks järgmisi koos siin? Kui juur on null, tagastamise vale, sest see tähendab sa ei pea isegi midagi seal. 

Kui root n on väärtus, nii et kui see juhtub olema üks vaatate, siis sa lähed tagasi true sest sa tead, sa leidsid. Aga kui väärtus on väiksem kui juur n, sa oled läheb otsima vasakul laps või vasakule lehed, mida iganes sa tahad seda kutsuda. Ja kui väärtus on suurem kui juurestik, sa lähed otsima õige puu, siis lihtsalt käivitada funktsiooni läbi otsida uuesti. 

Ja kui juur on null, et see tähendab olete jõudnud? See tähendab, et sa ei ole rohkem rohkem lehti otsida, siis sa tead, oh, ma arvan, et see ei ole siin sest pärast Olen tutvunud läbi kogu asi ja see ei ole siin, see lihtsalt ei pruugi olla siin. 

Kas see mõtet kõigile? Nii et see on nagu Kahendotsingupuu säilitamine võimeid ahelloendid. Cool, ja nii teist tüüpi andmete struktuuri kutid võid proovida rakendada oma pset, sul on ainult valida üks meetod. Aga võib-olla alternatiivne meetod hash tabelis on see, mida me nimetame Prefiksipuu. 

Kõik Prefiksipuu on on konkreetset tüüpi puu on väärtused, mis lähevad muud väärtused. Nii et selle asemel, millel on binaarsed puu selles mõttes, et ainult üks asi võib tuua kaks, sul võib olla üks asi käsk palju, palju asju. Sa põhimõtteliselt on massiivid mille sees hoiad viiteid, mis viitavad teistele massiivid. 

Nii sõlme, kuidas me oleks määratleda Prefiksipuu on me tahame olla Loogiline, c sõna, eks? Nii et sõlm on Boole'i nagu õige või vale, Kõigepealt eesotsas et massiivi, on see sõna? Teiseks, sa tahad olla suunanäitajaks mis iganes mujal neid on. Natuke keeruline, natuke abstraktne, kuid Ma selgitan, mida see kõik tähendab. 

Nii et siin, tipus, kui te on hulgaliselt kuulutas juba, sõlme, kus teil on Boole'i salvestatud väärtuse ees mis ütleb teile, on see sõna? See ei ole sõna? Ja siis on ülejäänud massiivi tegelikult salvestab kõik võimalusi, mida see võiks olla. Nii näiteks, nagu ülaosas teil on Esimene asi, mis räägib tõtt või vale, jah või ei, see on sõna. 

Ja siis on 0 kuni 26 tähed, et võite salvestada. Kui ma tahtsin otsida siin Nahkhiirte, ma lähen üles ja ma vaatan B. leian B minu massiiv, ja nii et ma tean, OK, on ​​B sõna? B ei ole sõna, nii et seega Pean hoida otsimine. Ma lähevad B ja ma vaadata pointer, et B osutab ja ma ei näe teist valikut teavet, sama struktuur, mis meil oli enne. 

Ja siin-- oh, järgmise kirja [kuuldamatu] on A. Nii me vaatame, et massiivi. Leiame kaheksanda väärtus, ja siis me vaatame, oh, hei, on see, et sõna on B-A sõna? See ei ole sõna. Meil hoida otsin. 

Ja nii siis me vaatame, kus kursorit A punktid, ja see juhib teise tee mis meil on rohkem väärtust salvestatud. Ja lõpuks, saame B-A-T, mis on sõna. Ja nii et järgmine kord sa vaatad, sa lähed on, et kontrollida, jah, Selle Boole'i ​​funktsioon on tõsi. Ja nii selles mõttes, et me oleme omamoodi võttes puu massiivid. 

Nii siis võib selline otsida maha. Selle asemel hashing funktsioon ja väärtuse omistamisel poolt seotud nimekirja, võite lihtsalt ellu Prefiksipuu mis otsib downwords. Tõesti, tõesti keeruline värk. Pole lihtne mõelda, sest ma olen nagu sülitamine nii palju andmestruktuurid välja sind, kuid ei igaüks omamoodi mõista, kuidas loogika see toimib? 

OK, lahe. Nii B-A-T, ja seejärel sa lähed otsima. Järgmine kord, kui lähed näha, oh, hei, see on tõsi, seega ma tean, et see peab olema sõna. 

Sama asi loomaaias. Nii et siin on asi just nüüd, kui me tahtsin otsida loomaaias, just nüüd, Praegu loomaaias ei ole Sõna meie sõnastikku sest, nagu kutid näha, esiteks, et meil on Boole'i tagasi tõsi on lõpus zoom. Meil on Z-O-O-M. 

Ja nii siin, me tegelikult ei ole sõna, zoo, meie sõnastikku kuna see kast on märkimata. Nii arvuti ei tean, et loomaaed on sõna sest nii, et me oleme hoidnud seda, vaid zoom siin tegelikult on tõeväärtus mis on olnud välja tõsi. Nii et kui me tahame lisada Sõna, zoo, meie sõnastikku Kuidas me minema umbes teeb seda? Mida me peame tegema, et veenduda meie arvuti teab, et Z-O-O on sõna ja ole esimene sõna on Z-O-O-M? 

Sihtrühm: [kuuldamatu] 

ANDI PENG: Täpselt, me soovite veenduda, et see siin, et tõeväärtus on kontrollida off, et see on tõsi. Z-O-O, siis me läheme, et kontrollida, nii et me teame täpselt, hei, loomaaias on sõna. Ma ütlen arvuti, et see sõna nii et kui arvuti kontrolli, ta teab, et loomaaed on sõna. 

Sest mäletan kõiki neid andmeid struktuure, see on väga lihtne meile öelda, oh, nahkhiir on sõna. Loomaaed on sõna. Zoom on sõna. Aga kui sa oled hoone see, arvuti ei tea. 

Nii et teil on öelda seda täpselt millisel hetkel on see sõna? Mis hetkest on see sõna pole? Ja millisel hetkel ma vaja otsida asju, ja millisel hetkel ma pean minema edasi? Igaüks selge, et? Cool. 

Ja nii siis saabub probleem, kuidas oleks meil minna sisestamist midagi see on tegelikult ei ole seal? Nii ütleme lihtsalt tahame lisada sõna, vann, meie Prefiksipuu. Nagu te poisid ei vaata nagu praegu kõik meil nüüd on B-A-T, ja see uus andmestruktuur seal oli pint, et osutas null, sest me eeldame et oh, pole sõnu pärast B-A-T, Miks me peame hoidma võttes asju pärast, et T. 

Aga probleem tekib siis, kui me teeme teile tahad olla sõna, mis tuleb pärast T s. Kui teil on vann, sa oled lähed tahan H õigus. Ja nii nagu me teeme, mis on me ei kavatse luua eraldi sõlme. Me ei jaotada iganes summa mälu selle uue massiivi, ja me ei kavatse loovutada suunanäitajaks. 

Me läheme loovutada H, Esiteks on selles null, me läheme vabaneda. Me läheme pea H-punktist allapoole. Kui me näeme H, me tahame seda minna kuhugi mujale. 

Siin saame siis vaadake ära jah. Kui me tabanud H pärast T, oh, siis me teame, et see on sõna. Loogiline läheb tagasi tõsi. Igaüks selge, kuidas see juhtus? OKEI. 

Nii et sisuliselt kõik Nende andmestruktuuride et oleme läinud üle täna, ma olen läinud üle neid tõesti kiiresti ja mitte palju detail, ja see on OK. Kui hakkate jama Mis, sa pead olema jälgida, kus kõiki viiteid on, mis toimub teie andmestruktuuride jne. Nad on väga kasulik, ja see on kuni teil poisid täiesti aru saada, kuidas soovite rakendada asjad. 

Ja nii pset4, on 5-- oh, mis on valesti. Pset5 on kirjavead. Nagu ma enne ütlesin, sa lähed, kui uuesti laadida lähtekoodi meilt. Seal saab olema kolm peamist asjad, mida sa allalaadimine. Sa laadida sõnastikud, neelata, ja tekste. 

Kõik need asjad on on kas sõnastikud sõnu et me tahame sind vaadata või test teabe et me tahame, et te õigekirja kontroll. Ja nii sõnastikud anname sa lähed teile tegelik sõnad, mida me tahame salvestada kuidagi nii, et see tõhusam kui massiivi. Ja siis tekst on saab olema, mida me oleme palume teil kirjutada veenduge kõik sõnad on tõeline sõnu. 

Ja nii kolme plokki programme, et me anname teile nimetatakse dictionary.c, dictionary.h ja speller.c. Ja nii kõik dictionary.c teeb on mida sa palusid rakendada. See laeb sõnu. See õigekirja kontrolli neid, ja see teeb kindlasti et kõik on õigesti sisestatud. 

diction.h on vaid teegi faili mis kuulutab kõik need funktsioonid. Ja speller.c, me ei kavatse anda teile. Sa ei pea midagi muuta ta. Kõik speller.c ei ei võta, et koormustele, kontrollib kiirust see, testib mõõdupuuks meeldib, kuidas kiiresti sa oled võimeline tegema asju. 

See on speller. Lihtsalt ei jama, kuid teha Kindlasti saate aru, mida ta teeb. Me kasutame funktsiooni nimetatakse getrusage et testib täita oma õigekirja kontrollija. Kõik see on põhimõtteliselt testida ajal kõik oma sõnastikku nii, et sa sellest aru. Ole ettevaatlik, et mitte jama või muud asjad ei tööta korralikult. 

Ja suurem osa selle väljakutse on kutid tõesti muuta dictionary.c. Me läheme teile 140,000 sõnu sõnaraamatus. Me läheme teile tekst fail, mis on need sõnad, ja me tahame, peate olema suuteline korraldama neid hash tabelit või Prefiksipuu sest kui me palume teil kirjutada kontroll-- kujutage ette, kui sa oled õigekirja kontrollides nagu Homerose Odüsseia. See on nagu see suur, suur test. 

Kujutage ette, kui iga sõna, mida tuli vaatama läbi hulgaliselt 140,000 väärtusi. See võtaks igavesti Teie masin käivitada. See on põhjus, miks me tahame korraldada meie andmed tõhusam andmestruktuurid nagu hash tabelit või Prefiksipuu. Ja siis saate ikka omamoodi ja kui te otsite juurdepääsu asju lihtsamalt ja kiiremini. 

Ja nii olla ettevaatlik, et lahendada kokkupõrkeid. Sa lähed, et saada hunnik sõnade, mis algavad A. Sa lähed, et saada hunnik sõnu et alustada B. sinust poisid, kuidas sa tahad seda lahendada. Võibolla seal on rohkem tõhus hash funktsiooni kui lihtsalt esimese tähe midagi, ja nii, et sinust poisid sellist teha mida iganes sa tahad. 

Võib-olla soovite lisada kõik tähed kokku. Ehk soovid meeldib teha imelikke asju arvestab tähtede arv, mida iganes. Kuni kutid, kuidas sa tahad seda teha. Kui soovite teha hash tabelit, kui te tahan proovida Prefiksipuu, täiesti sinust. Ma hoiatan teid enne tähtaega, et Prefiksipuu on tavaliselt veidi raskem lihtsalt sellepärast, et seal on palju rohkem viiteid jälgida. Aga täiesti su poisid. See on palju tõhusam Enamasti. Sa tahad tõesti võimalik hoida meeles kõik oma suunanäitajaks. Nagu sama asja tegema et ma tegin siin. Kui sa üritad sisestada väärtused räsi tabeli või kustutada, veenduge, et olete tõesti jälgida kus kõik on seetõttu see on tõesti lihtne, kui ma olen üritan sisestada nagu sõna, Andy. Ütleme nii, et see on õige sõna, sõna, andy, hiiglane nimekirjas sõnu. 

Kui mul just ümber jaotada kursor vale, oops, seal läheb tervikuna mu ülejäänud seotud nimekirja. Nüüd ainult sõna ma on, Andy ja nüüd kõik teised sõnad sõnastik on kadunud. Ja nii sa tahad teha kindel, et sa jälgida kõiki oma suunanäitajaks või sa lähed, et saada suuri probleeme oma koodi. Joonista asju ettevaatlikult sammhaaval. See muudab palju lihtsam mõelda. 

Ja lõpuks, sa tahad, et oleks võimalik testida oma tulemuslikkust oma programmi suurel pardal. Kui kutid võtta vaata CS50 kohe, meil on, mida nimetatakse suureks pardal. On skoor lehel kiiremini õigekirjakontrolli korda kõigis CS50 Just nüüd, ma arvan, et top nagu 10 korda ma arvan, neist kaheksa on töötajad. Me tõesti tahame, et te poisid peksid meid. 

Kõik me püüdsime rakendada kiireim koodi kui võimalik. Me tahame teiega proovida vaidlustada USA ja rakendama kiiremini kui me kõik võimalik. Ja nii on see tõesti Esimest korda, et me oleme küsib kutid teha pset, et saab tõesti teha ükskõik mis meetodil sa soovid. 

Ma olen alati öelnud, et see on rohkem sarnane reaalse elu lahendus, eks? Ma ütlen, hei, ma vajan sind seda tegema. Ehitamine programm, mis teeb selle minu jaoks. Kas see aga soovite. Ma lihtsalt tean, et ma tahan kiiresti. See on teie ülesanne sellel nädalal. Te, me ei kavatse teile ülesanne. Me läheme teile väljakutse. Ja siis see on kuni teil poisid täiesti lihtsalt nuputada Mis on kiireim ja tõhusam viis täita seda. Jah? 

Sihtrühm: Kas me lubatud, kui tahtsin uurida kiiremini viise teha räsitabeli online, me saame teha seda ja tuua kellegi kood? ANDI PENG: Jah, täiesti korras. Nii et kui te poisid lugeda spec, seal on line spec, mis ütleb teile poisid on täiesti tasuta teadus hash funktsioone, mida mõned on kiirem räsifunktsioone käivitada asju läbi nagu Niikaua kui te tsiteerivad, et koodi. Nii mõned inimesed on juba arvasin, kiire viise tehes õigekirja kabe, kiire võimalusi teabe säilitamiseks. Täiesti kuni kutid kui te tahan lihtsalt võtta, eks? Veenduge, et olete viidates. Väljakutseks tõesti et me üritame testida on tagada, et sa tead teed umbes suunanäitajaks. Niipalju kui rakendatakse tegelik hash funktsiooni ja tulemas nagu matemaatika seda teha, kutid teadus iganes meetodid Online kutid tahavad. Jah? 

Sihtrühm: Kas me tsiteerida lihtsalt abil [kuuldamatu]? 

ANDI PENG: Jah. Sa võid, sinu kommentaar, Teile võib tuua näiteks, oh, võetud jutt, jutt, JANKUTUSTA, hash funktsiooni. Igaüks on mingeid küsimusi? Me tegelikult breezed läbi osa täna. Ma olen siin, et vastata küsimustele nii hästi. 

Samuti, nagu ma ütlesin, kontor tundi täna ja homme. Spec sel nädalal on tegelikult super lihtne ja super lühike lugeda. Pakun võttes pilk, just läbi lugeda kogu seda. 

Ja Zamyla tegelikult juhatab teid läbi iga funktsioone teil on vaja rakendada, ja nii see on väga, väga selge, kuidas seda teha kõike. Lihtsalt veenduge, et olete jälgida viiteid. See on väga keeruline pset. 

See ei ole keeruline, sest nagu, oh, mõisted on nii palju raske või sa pead õppima nii palju uusi süntaks teed et sa tegid viimase pset. See pset on raske, kuna seal on nii palju viiteid, ja siis on see väga lihtne, kui sul on viga teie koodi ei saa leida, kui et viga on. 

Ja nii täielik ja lausuma usu sind poisid, et oleks võimalik võita meie [kuuldamatu] kirjaviisiga. Ma tegelikult ei ole ühtegi kirjalikku kaevanduse veel, aga ma olen umbes et kirjutada minu. Niisiis, kui olete kirjalikult sinu, ma tulen kirjalikult kaevanduse. Ma püüan teha minu kiiremini kui sinu oma. Me näeme, kes on kõige kiirem. 

Ja jah, ma näen kõik kutid siin teisipäeval. Ma jooksen mingi nagu pset töökoda. Kõik lõigud see nädal on pset töötoad, nii kutid on palju võimalusi appi, tööaega nagu alati, ja ma tõesti ootan lugedes kõik oma poisid "koodi. Mul on viktoriinid siin kui te poisid tahavad tulla saan neid. See on kõik.