JASON Hirschhorn: Tere kõigile sektsioonile Seven. Oleme nädalal seitse muidugi. Ja selle nädala neljapäev on Halloween, et ma olen ehitud nagu kõrvits. Ma ei saanud kõigest väest ja panna minu kingad, nii et miks ma olen lihtsalt seljas sokid. Ma ka ei kanna midagi alla see, et ma ei suuda seda välja, kui see on häirivad sind. Vabandan juba ette, et. Sul ei ole vaja ette kujutada, mis toimub. Ma kannan poksijad. Nii et see on kõik hea. 

Mul on pikem lugu, miks ma olen riides nagu kõrvits, aga ma lähen salvestada, et selles lõigus hiljem sest ma ei taha, et alustada. Meil on palju põnevat minna üle sel nädalal. Enamik neist otseselt seotud käesoleva nädala probleem komplekt, õigekirjavead. Me läheb üle, mis on seotud nimekirjad ja hash tabeleid kogu lõik. Panin selle nimekirja iga nädal nimekirja vahendeid, et aidata teil koos Materjali sellel muidugi. Kui kahjumiga või kui otsite mõnda Lisainformatsiooni kontrollida üks neid vahendeid. 

Jällegi pset6 on õigekirjavead Selle nädala pset. Ja see julgustab ka sind, ja ma kutsun teid, et kasutada mõnda muud vahendid spetsiaalselt selle pset. Eelkõige kolm Olen loetletud ekraanile - gdb, mis me oleme tuttavad ja kasutanud juba mõnda aega, on saab olema väga kasulik sel nädalal. Nii et ma panen selle siia üles. Aga kui te töötate C, sa peaksid alati kasutama gdb programmide silumiseks. See nädal ka valgrind. Kas keegi teab, mida valgrind teeb? 

Publik: See kontrollib mälu lekkeid? 

JASON Hirschhorn: Valgrind kontrollib mälu lekkeid. Nii et kui sa malloc midagi oma programmi, siis palud mälu. Lõpus oma programmi, siis on kirjutada tasuta kõik olete malloced anda mälu tagasi. Kui te ei kirjuta tasuta lõpus ja teie programm jõuab järeldusele, kõik automaatselt vabastada. Ja väikesed programmid, see on ei ole nii suur asi. Aga kui sa oled kirjalikult pikem jooks programmi, mis ei sulguda, tingimata, et paar minutit või paar sekundit ja seejärel mälu lekib võib saada suur asi. 

Nii pset6, ootus on, et siis on null mälu lekkeid oma programmi. Kontrollida mälu lekib, joosta valgrind ja see annab sulle mõned kena väljund üürile te teate, kas või ei kõik oli tasuta. Me harjutame seda hiljem täna, loodetavasti. 

Lõpuks käsu diff. Sa kasutasid midagi sarnast see aastal pset5 koos Peek vahend. Lubatud sa sisse vaadata. Sul on ka kasutada diff ka ühe lahendamist spec. Aga lubatud teil võrrelda kahte faile. Võiksite võrrelda bitmap faili ja info päised personal lahendus ja teie lahendus pset5 kui valisid seda kasutada. Diff võimaldab teil seda teha, samuti. Võite võrrelda õige vastus Selle nädala lahendamist oma vastus ja vaata, kas see rida üles või vaadake kui vead on. 

Nii et need on kolm head vahendid, et peate kasutama sel nädalal, ja Kindlasti kontrollige oma programmi Nende kolme tööriistad enne kui selle sisse Jällegi, nagu ma juba mainisin iga nädal, Kui teil on mingeid tagasiside minu jaoks - nii positiivne ja konstruktiivne - julgelt suunduda veebilehel allosas käesoleva slaidile ja sisend seal. Ma tõesti hindan iga ja kõik tagasiside. Ja kui sa ei anna mulle konkreetsed asjad, mis Ma võin teha, et parandada või et ma olen läheb hästi, et sa tahaksid mind jätkata, ma võtan selle oma südameasjaks ja tegelikult üritan kuulata teie tagasisidet. Ma ei saa lubada, et ma teen kõik, aga nagu seljas kõrvitsa kostüüm iga nädal. 

Nii et me ei kavatse kulutada suurema osa jagu, nagu ma mainisin, räägime ahelloendid ja hash tabeleid, mis on vahetult kohaldatavad lahendamist sel nädalal. Ahelloendid läheme üle suhteliselt kiiresti, sest oleme kulutanud päris bit aega läheb üle see osa. Ja nii me jõuame otse kodeerimise probleemid seotud nimekirju. Ja siis lõpuks me räägime räsitabeli ja kuidas need kehtivad käesoleva nädala lahendamist. 

Olete näinud seda koodi enne. See on struktuure ning seda määratletakse midagi uut nimetatakse sõlme. Ja sees sõlm on täisarv siin ja seal on viit teise sõlme. Me oleme näinud seda enne. See on tulemas paar nädalat nüüd. See ühendab suunanäitajaks, mis me oleme töötamisel ja structs, mis võimaldavad meil ühendada kaks erinevat asjad ühte andmetüüpi. 

Seal on palju toimub ekraanil. Kuid kõik see peaks olema suhteliselt tuttav teile. Esimesel real, me kuulutada uus sõlm. Ja siis sees, et uus sõlm, seadsin täisarv, et sõlme üks. Näeme järgmisel real ma teen printf käsku, aga ma pole tuhm printf käsk, sest tegelikult Oluline osa on siin kandis - new_node.n. Mis dot tähendab? 

Publik: Mine sõlm ja hindab n väärtust ta. 

JASON Hirschhorn: See on täpselt õige. Dot tähendab juurdepääsu n osa Uue sõlme. See reale mida teeb? Michael. 

Publik: See loob teise sõlme mis toob välja uue sõlme. 

JASON Hirschhorn: nii et see ei Uue sõlme. See tekitab mida? 

Publik: pointer. 

JASON Hirschhorn: kursor sõlme, nagu näidatud käesoleva sõlme * siin. Seega loob kursor sõlme. Ja mis sõlm see osutab et, Michael? 

Publik: uus sõlm? 

JASON Hirschhorn: uus sõlm. Ja see on suunaga sinna, sest me oleme arvestades seda aadressi uus sõlm. Ja nüüd seda joont näeme kaks eri viise väljendades sama. Ja ma tahtsin juhtida tähelepanu sellele, kuidas need kaks asja on samad. Esimeses reas me endid pointer. Läksime sõlme. Seda see täht tähendab. Me oleme näinud, et enne näidikumehhanism. Mine, et sõlme. See on sulgudes. Ja siis ligi kaudu dot operaator n elementi, et sõlme. 

Nii et vőtab süntaks nägime siin ja praegu kasutades seda pointer. Muidugi, see läheb omamoodi hõivatud kui sa oled kirjalikult need sulgudesse - et täht ja punkt. Läheb veidi hõivatud. Nii et meil on mõned süntaktiline suhkur. Ja see joon siin - ptr_node-> n. See täpselt sama asi. Nii et need kaks rida koodi on samaväärne ja teeme täpselt sama asi. 

Aga ma tahtsin juhtida need läbi enne kui me minna kaugemale, et te mõistate, et tegelikult see asi siin on lihtsalt süntaktiline suhkru viite mahavõtmine kursor ja siis läheb n osa sellest struktuure. Küsimusi selle slaidi? OK. 

Nii et me läheme läbi paar toiminguid, mida saate teha on ahelloendid. Seotud nimekirja, mäletate, on rida sõlmed, mis viitavad ühele teisele. Ja me algavad tavaliselt pointer kutsutud pea üldiselt, mis osutab Esimene asi nimekirjas. Nii esimesel real siin, me on meie algne L esimene. Nii et asi, mida sa ei mõtle - see tekst siin võite mõelda nagu lihtsalt kursor oleme salvestatud kusagilt, et punkte Lisa esimese osaga. Ja see on seotud nimekirja meil on neli sõlme. Iga sõlm on suur kast. Mida suurem kast sees suur kast on täisarv. Ja siis on meil pointer osa. 

Need lahtrid ei pöörata skaala, sest kui suur on täisarv baiti? Kui suur on? Neli. Ja kui suur on pointer? Neli. Nii et tõesti, kui me joonistaks see, et skaala mõlemad kastid oleks sama suurusega. Sellisel juhul me tahame lisada midagi arvesse seotud nimekirja. Nii et näete, siin me lisades viis Me läbida kaudu seotud nimekirja, leida, kui viis läheb ja seejärel lisada see. 

Olgem murda see maha ja mine natuke aeglasemalt. Ma viitavad pardal. Nii et meil on meie sõlme viis, et oleme loodud mallocs. Miks on kõik naeravad? Lihtsalt nalja. OK. Nii oleme malloced viis. Lõime selle sõlme kusagil mujal. Meil on see valmis. Alustame ees meie nimekirjas kaks. Ja me tahame, et sisestada aastal sorteeritud mood. 

Nii et kui me näeme, kaks ja me tahame panna viis, mida me teeme, kui me näeme midagi alla meie juures? Mida? Me tahame lisada viis sellesse seotud nimekirja, hoides seda sorteerida. Näeme number kaks. Mida me siis teeme? Marcus? 

Publik: Call pointer Järgmise sõlme. 

JASON Hirschhorn: ja miks läheme järgmine? 

Publik: Sest see on Järgmine sõlme nimekirja. Ja me teame ainult, et muud asukohta. 

JASON Hirschhorn Ja viis on suurem kui kaks, eelkõige. Kuna me tahame hoida seda sorteerida. Nii viis on suurem kui kaks. Nii liigume edasi järgmise üks. Ja nüüd jõuame neli. Ja mis juhtub, kui me jõuame neli? 

Viis on suurem kui neli. Nii et me jätkame. Ja nüüd me oleme kuus. Ja mida me näeme kell kuus? Jah, Carlos? 

Publik: Kuus on suurem kui viis. 

JASON Hirschhorn: Kuus on üle viie. Nii et kui me tahame lisada viis. Kuid pidage meeles, et kui me ainult üks pointer siin - see on meie pildi pointer, mis on liiklevad läbi nimekirja. Ja me osutades kuus. Me oleme kaotanud jälgida, mida tuleb enne kuus. Nii et kui me tahame, et lisada midagi arvesse see nimekiri hoides seda järjestatud oleme tõenäoliselt vaja, kui palju viiteid? 

Publik: Kaks. 

JASON Hirschhorn: Kaks. Üks jälgida praegust üks ja üks, et jälgida eelmine. See on ainult üksikult seotud nimekirja. See ainult läheb ühes suunas. Kui meil oleks kahekordselt seotud nimekirja, kus kõik oli osutades asi pärast seda ja asi enne seda, siis me ei pea seda tegema. Aga sel juhul me ei taha kaotada jälgida, mida tuli enne meid korral meil vaja lisada viis kuhugi aasta keskel. Ütle, et me lisades üheksa. Mis juhtuks, kui saime kaheksa? 

Publik: Sa pead saada, et null punkti. Selle asemel, et null punkti on teil lisada element ja siis on see viidata üheksa. 

JASON Hirschhorn: Täpselt. Nii saame kaheksa. Jõuame lõpuks nimekirja, sest see on suunatud tühjaks. Ja nüüd, selle asemel, et viidata null meil on see punkt, et meie uus sõlm. Ja seadsime kursorit meie uus sõlm tühjaks. Kas kellelgi on küsimusi kuidas lisada? Mida teha, kui ma ei hooli loetelu pidamise järjestatud? 

Publik: liialdama alguses või lõpus. 

JASON Hirschhorn: liialdama alguses või lõpus. Kumba me peaksime tegema? Bobby? Miks lõpetada? 

Publik: Kuna algusest on juba täidetud. 

JASON Hirschhorn: OK. Alguses on juba täidetud. Kes tahab vastu vaielda Bobby. Marcus. 

Publik: Noh sa ilmselt tahad liialdama alguses, sest muidu kui sa paned seda aasta lõpuks on teil läbida kogu nimekirja. 

JASON Hirschhorn: Täpselt. Seega, kui me mõtleme, runtime, runtime sisestades lõpus oleks n, suurus selles. Mis on suur O runtime sisestades alguses? Pidev aeg. Nii et kui te ei hooli hoides midagi sorteerida, palju parem lihtsalt sisestada alguses seda nimekirja. Ja et on võimalik teha pidevalt aega. 

OK. Järgmine toiming on leida, mis muu - oleme sõnastanud seda otsida. Aga me ei kavatse vaadata läbi seotud nimekirja mõnda objekti. Te olete näinud kood otsi varem loeng. Aga me justkui lihtsalt tegi seda sisestada või vähemalt sisestamist midagi sorteerida. Sa vaatad läbi, läheb sõlme poolt sõlme, kuni leiad number, et sa oled otsin. Mis juhtub, kui sa jõuad lõpuks nimekirja? Ütle Otsin üheksa ja ma jõuda lõpuks nimekirja. Mida me siis teeme? 

Publik: Tagasi vale? 

JASON Hirschhorn: tagasi false. Me ei leia seda. Kui jõuate nimekirja lõppu ja sa ei leia number sa oled otsin, see ei ole seal. Kõik küsimused leiavad? Kui see oli sorteeritud nimekirja, mis oleks olla erinev meie otsimine? Jah. 

Publik: Oleks leida esimene väärtus see on suurem kui üks otsite ja siis tagasi vale. 

JASON Hirschhorn: Täpselt. Nii et kui see on sorteeritud nimekirja, kui saame midagi, mis on suurem kui see, mida me otsime, me ei pea jätkame nimekirja lõppu. Me saame sel hetkel tagasi false sest me ei kavatse seda leida. Küsimus on nüüd, oleme rääkinud hoides ahelloendid sorteeritud, hoides neid sortimata. See saab olema midagi, mida sa oled ilmselt läheb mõtlema kui kodeerimine lahendamist viis, kui te vali hash tabelis eraldi Aheldamise meetod, mis me räägime hiljem. 

Aga see on seda väärt, et hoida nimekiri sorteeritud ja siis saaks võib-olla kiiremini otsinguid? Või on parem kiiresti sisestada midagi pidevas runtime kuid siis on enam otsima? See on kompromiss seal, et sa saad otsustada, milline on kõige sobivam oma konkreetse probleemiga. Ja seal ei ole tingimata üks täiesti õige vastus. Aga see on kindlasti otsus saad teha, ja ilmselt hea kaitsta et, ütleme, kommentaar või kaks, miks valisite üks teiste üle. 

Lõpuks kustutada. Me oleme näinud kustutamine. See on sarnane otsides. Otsime element. Ütle, me üritame kustutada kuus. Nii leiame kuus siin. Asi, mida me peame tegema, et me teha on see, et mis iganes on suunaga kuus - nagu me näeme samm kaks siin - mis iganes osutades kuus vaja vahele kuus nüüd ja muuta, et olenemata kuus osutab. Me ei taha kunagi harva mujal meie nimekirjas, unustades, et seada see eelmine pointer. Ja siis mõnikord, olenevalt programmi, siis nad lihtsalt kustutada sõlme täielikult. Mõnikord sa tahad tagasi väärtus, mis on selles sõlme. Nii see on, kuidas kustutada töid. Kõik küsimused kustutada? 

Publik: Nii et kui sa tahad, et kustutada see, kas sa lihtsalt kasutada tasuta, sest arvatavasti oli see malloced? 

JASON Hirschhorn: Kui soovite tasuta midagi, mis on täpselt õige ja te malloced ta. Ütle tahtsime tagastab väärtuse. Võiksime tagasi kuus ja siis tasuta Selle sõlme ja kõne tasuta ta. Või me tahaks ilmselt helistada tasuta esimene ja siis tagasi kuus. 

OK. Nii liigume edasi harjutada kodeerimine. Me läheme koodi kolm ülesannet. Esimest nimetatakse insert_node. Nii et teil on kood, et ma saatsin teid ja kui sa vaatad seda hiljem pääsete koodi linked.c edasi CS50 veebisaidil. Aga linked.c, seal on mõned skelett kood, mis on juba kirjutatud teile. Ja siis on paar funktsiooni teil on vaja kirjutada. 

Esiteks me läheme kirjuta insert_node. Ja mis insert_node ei tähendab lisab täisarv. Ja sa oled andes täisarv arvesse seotud nimekirja. Ja eriti, peate hoida nimekirja sorteeritakse alates väiksemast ja lõpetades suuremaga. Ka te ei taha pange duplikaadid. Lõpuks, nagu te näete insert_node naaseb bool. Nii et sa peaksid lasta kasutaja teadma kas insert oli edukas tagastades õige või vale. Lõpus see programm - ja selles etapis ei pea te muretsema vabastades midagi. Nii et kõik, mida sa teed on võttes täisarv ja sisestamist nimekirja. 

See on see, mida ma palun teil teha nüüd. Jällegi linked.c, mida kõik on, on skelett kood. Ja sa näed põhja poole proovi funktsiooni deklaratsiooni. Kuid enne laskumist kodeerimine see C, ma väga soovitame teil minna läbi samme me oleme praktiseerivad iga nädal. Me oleme juba läbi käinud sellest pilti. Nii et sa peaksid olema mingi ettekujutus kuidas see toimib. Aga ma kutsun teid üles kirjutama mõned pseudokoodi enne sukeldumise sisse Ja me läheme üle pseudokoodi rühmana. Ja siis, kui olete kirjutanud oma pseudokoodi ja kui oleme kirjutanud meie pseudokoodi rühmana, saate minna kodeerimine see C. 

Nagu heads up, insert_node funktsioon Tõenäoliselt on kõige keerulisem ja kolm me kirjutada, sest ma lisatud mõned täiendavad piirangud oma programmi, eelkõige sa ei kavatse lisada iga duplikaadid ja et nimekiri peaks jääma sorteerida. Nii et see on mitte-triviaalne programm et teil on vaja koodi. Ja miks sa ei võta 06:55 minutit lihtsalt saada tööd pseudokoodi ja kood. Ja siis algab läheb rühmana. Jällegi, kui teil on küsimusi, siis tõsta oma käsi ja ma tulen umbes. . 

Meil on ka tavaliselt teeme need - või ma ei ole selgesõnaliselt öelda, et sa võib töötada inimestega. Aga loomulikult, ma väga soovitame teil, Kui teil on küsimusi, paluda naaber istub sinu kõrval või isegi töö kellegagi muidu, kui soovite. See ei pea olema individuaalne vaikne tegevus. 

Alustame kirjalikult mõned pseudokoodi laual. Kes saab mulle esimene rida pseudokoodi selle programmiga? Funktsiooni pigem - insert_node. Alden? 

Publik: Nii et esimene asi, mida ma tegin, oli Uue kursor sõlme ja ma käivitatud, siis osutab sama asi, et nimekirjas on suunaga. 

JASON Hirschhorn: OK. Nii loote uue pointer nimekirja, mitte sõlme. 

Publik: Õigus. Jah. 

JASON Hirschhorn: OK. Ja siis me tahame seda teha? Mis on pärast seda? Aga sõlm? Meil ei ole sõlme. Meil on lihtsalt raha. Kui me tahame lisada sõlme, mida me pead tegema, enne saame isegi mõtle sisestamist? 

Publik: Oh, vabandust. peame malloc ruumi sõlme. 

JASON Hirschhorn: Suurepärane. Teeme - OK. Ei jõua, et kõrge. OK. Me läheme alla ja seejärel me kasutame kaks veergu. Ma ei saa minna, et - OK. Loo uus sõlm. Võite luua uue pointer nimekirja või saate lihtsalt kasutada nimekirja, kuna see on olemas. Sa tõesti ei pea seda tegema. 

Nii loome uue tipu. Suur. See, mida me teha esimene. Mis edasi? 

Publik: Oota. Kas peaksime looma uue sõlme nüüd või me peaksime ootama, et veenduda, et pole duplikaadid sõlme nimekirja enne, kui me luua? 

JASON Hirschhorn: Hea küsimus. Teeme seda hoida hiljem, sest Enamuse ajast oleme me luua uus sõlm. Nii et me hoiame seda siin. Aga see on hea küsimus. Kui me loome seda ja leiame eksemplaris, mis peaks teeme naasid? 

Publik: Vabastage ta. 

JASON Hirschhorn: Jah. Tõenäoliselt vaba ta. OK. Mida me teeme, kui me luua uus sõlm? Annie? 

Publik: Asetame number sõlme? 

JASON Hirschhorn: Täpselt. Panime number - me malloc ruumi. Ma jätan selle kõik ühe reana. Aga sul on õigus. Me malloc ruumi ja seejärel paneme number sisse Me saame isegi määrata pointer osa tühjaks. See on täpselt õige. Ja siis umbes pärast seda? Jälle see pilt laual. Mida me siis teeme? 

Publik: Me läheme läbi nimekirja. 

JASON Hirschhorn: Mine läbi nimekirja. OK. Ja mida me kontrollida iga sõlme. Kurt, mida me vaadata võtta iga sõlme? 

Publik: Vaata, kas n väärtus et sõlm on suurem kui n väärtus meie sõlme. 

JASON Hirschhorn: OK. Ma lähen tegema - Jah, OK. Nii et see on n - Ma ütlen, kui väärtus on suurem kui see sõlm, siis mida me teeme? 

Publik: Noh, siis me lisada asi õige enne seda. 

JASON Hirschhorn: OK. Nii et kui see on suurem kui see, siis me tahame lisada. Aga me tahame lisada see vahetult enne sest me ka ei pea olema jälgida, siis mis oli enne. Nii sisestada enne. Nii et me ilmselt jäi midagi varem. Ilmselt tuleb hoida jälgida, mis toimub. Aga me jõuame tagasi sinna. Niisiis, milline väärtus on väiksem kui? Kurt, mida me teeme, kui väärtus on väiksem? 

Publik: Siis muudkui läheb kui see on viimane. 

JASON Hirschhorn: mulle meeldib. Nii minna järgmisele sõlme. Kui see pole viimane - me ilmselt kontrollides, et aastal tingimuste seisukorras. Aga jah, järgmine sõlme. Ja see muutub liiga väike, nii me liikuda siin. Aga kui - võib igaüks näha seda? Kui me oleme võrdsed, mida me teeme? Kui raha me üritame lisada on võrdne selle sõlme väärtus? Jah? 

Publik: [kuuldamatu]. 

JASON Hirschhorn: Jah. Arvestades seda - Marcus on õige. Meil oleks võinud olla tehtud midagi erinevat. Kuid arvestades, et oleme loonud siin me peaks vaba ja siis tagasi. Oh boy. Kas see on parem? Kuidas nii? OK. Vaba ja siis mida me tagasi, [kuuldamatu]? OK. Kas me puudu midagi? Nii et kui me jälgida eelneva sõlm? 

Publik: Ma arvan, et see läheks pärast luua uus sõlm. 

JASON Hirschhorn: OK. Nii alguses me ilmselt - Jah, me saame luua kursori uus sõlme, nagu eelmine sõlm pointer ja aktiivse sõlme pointer. Niisiis olgem lisada, et siin. Loo praegune ja eelmine vihjeid sõlmed. Aga kui me kohandada neid vihjeid? Kui me seda teeme, et kood on? Jeff? 

Publik: - väärtus tingimustel? 

JASON Hirschhorn: Milline üks eriti? 

Publik: Ma lihtsalt segaduses. Kui väärtus on suurem kui see sõlm, ei see tähendab, et sa tahad minna Järgmise sõlm? 

JASON Hirschhorn: Nii et kui meie raha on suurem väärtus see sõlm. 

Publik: Jah, siis sa tahad minna veelgi kaugemale line, eks? 

JASON Hirschhorn: Õigus. Nii et me ei sisesta see siia. Kui väärtus on väiksem kui käesoleva sõlm, siis me minna järgmisele sõlme - või siis sisestada enne. 

Publik: Oota, mis see on sõlm ja mis on väärtus? 

JASON Hirschhorn: Hea küsimus. Väärtus kohta seda funktsiooni definitsioon on see, mida me oleme andnud. Seega väärtus on number, et me antud. Nii et kui väärtus on väiksem kui selle sõlm, me vajame aega, et sisestada. Kui väärtus on suurem kui see sõlm, me minna järgmisele sõlme. Ja tagasi algse küsimuse, aga kus - 

Publik: Kui väärtus on suurem kui seda sõlme. 

JASON Hirschhorn: Ja nii Mida me siin teeme? Sweet. See on õige. Ma lihtsalt kirjutada uuendada viiteid. Aga jah, koos praeguse siis oleks seda uuendada punkt järgmise üks. Midagi muud meil puuduvad? Nii et ma lähen kirjuta see kood gedit. Ja kui ma seda teen, siis võib olla Paar minutit veel tööd kodeerimine Seda C. 

Nii et mul on sisend pseudokoodi. Kiire märkus enne kui me alustame. Me ei pruugi olla võimalik täiesti Lõpetame selle kõigis need kolm ülesannet. On õige lahendusi neile et ma e-kirju, et teid Pärast punkti ja see postitati CS50.net. Nii et ma ei soovita teil mine vaata lõigud. Ma kutsun teid, et proovida neid oma omada, ja siis kasuta tava probleeme oma vastuste kontrollimiseks. Need kõik on mõeldud tihedalt seotud ja järgima mis sa pead tegema, on probleem komplekti. Nii et ma kutsun teid harjutada seda oma ja siis kasuta koodi kontrollida oma vastuseid. Sest ma ei taha, et liikuda edasi hash lauad mingil hetkel osa. Nii et me ei pruugi saada läbi kõik. Aga me teeme nii palju saame nüüd. 

OK. Alustagem. Asam, kuidas me loome uue tipu? 

Publik: Sa konstrueerib *. 

JASON Hirschhorn: Nii et me on see siin. Oh, vabandust. Sa ütlesid struct *. 

Publik: Ja siis [? lahke?] sõlme või c sõlme. 

JASON Hirschhorn: OK. Ma kutsun seda new_node et saaksime jääda järjekindel. 

Publik: Ja sa tahad, et seada see pea esimese sõlme. 

JASON Hirschhorn: OK. Nüüd see osutab - nii et see ei loonud uue sõlme veel. See on lihtsalt osutades esimese sõlme nimekirja. Kuidas luua uus sõlm? Kui mul on vaja ruumi, et luua uus sõlm. Malloc. Ja kui suur? 

Publik: suurus struktuure. 

JASON Hirschhorn: suurus struct. Ja mis struct nimetatakse? 

Publik: Sõlme? 

JASON Hirschhorn: sõlme. Nii malloc (sizeof (node)); annab meile ruumi. Ja on seda joont - üks asi on vale sellel liinil. Kas new_node kursor struct? See on üldnimetus. Mis see on - sõlme täpselt. See sõlm *. Ja mida me teha kohe pärast me malloc midagi, Asan? Mis on esimene asi, mida me saame teha? Mis siis, kui see ei tööta? 

Publik: Oh, vaadake, kui see märgib, et sõlm? 

JASON Hirschhorn: Täpselt. Nii et kui sa new_node võrdne võrdsete null, mida me teeme? See tagastab bool see funktsioon. Täpselt. Näeb hea välja. Midagi lisada sinna? Lisame asjad lõpus. Aga siiani tundub hea. Loo praegune ja eelmine suunanäitajaks. Michael, kuidas ma seda teen? 

Publik: Sa oleks pidanud teha sõlme *. Sa pead tegema üks ei jaoks new_node kuid sõlmede meil juba on. 

JASON Hirschhorn: OK. Nii aktiivse sõlme me oleme. Ma helistan, et Val. Hea küll. Oleme otsustanud me tahame hoida kaks, sest meil on vaja teada, mis enne seda. Mida nad saavad initsialiseerida? 

Publik: nende väärtus meie nimekirjas. 

JASON Hirschhorn: Mis on Esimene asi, mida meie nimekirjas? Või kuidas me teame, kus Alguses meie nimekiri on? 

Publik: Kas pole möödas arvesse funktsioon? 

JASON Hirschhorn: Õigus. See oli möödunud aastal siin. Nii et kui see on vastu võetud, funktsioon, alustada nimekirja, mida me kehtestatud praegune võrdne? 

Publik: List. 

JASON Hirschhorn: List. See on täpselt õige. Nüüd on aadress algusest meie nimekirjas. Ja mis eelmine? 

Publik: List miinus üks? 

JASON Hirschhorn: Ei midagi enne seda. Mida me saame teha, et tähenda midagi? 

Publik: Null. 

JASON Hirschhorn: Jah. See kõlab nagu hea mõte. Perfect. Aitäh. Läbida nimekirja. Constantine, kui kaua me läbida nimekirja? 

Publik: kuni jõuame null. 

JASON Hirschhorn: OK. Niisiis, kui selle jaoks silmus. Mida me teeme? 

Publik: Võib-olla loop? 

JASON Hirschhorn: Teeme silmus. OK. 

Publik: Ja me ütleme - kuni praegune pointer ei ole võrdne null. 

JASON Hirschhorn: Nii et kui me teame, tingimus, kuidas me saame kirjutada loop põhineb off see tingimus. Milline loop me peaksime kasutama? 

Publik: Kuigi. 

JASON Hirschhorn: Jah. See on mõttekam põhineb off, mis sa ütlesid. Kui me tahame minna me seda teeks lihtsalt tean, et asi, oleks mõtet teha samas silmus. Kuigi praegune ei võrdu null, kui väärtus on väiksem kui käesoleva sõlme. Akshar, anna mulle seda joont. 

Publik: Kui praegused-> n n väiksem väärtus. Või ei pööra seda. Lülitage et sulg. 

JASON Hirschhorn: Vabandust. 

Publik: Muuda sulg. 

JASON Hirschhorn: Nii et kui see on suurem väärtus. Sest see tekitab segadust comment eespool, ma teen seda. Aga jah. Kui meie väärtus on väiksem kui selle sõlme, mida me teeme? Oh. Mul on see siin. Sisesta enne. OK. Kuidas me seda teeme? 

Publik: Kas see on ikka minuga? 

JASON Hirschhorn: Jah. 

Ideid: - new_node-> kõrval. 

JASON Hirschhorn: Mis siis et läheb võrdsed? 

Publik: See läheb võrdne praegune. 

JASON Hirschhorn: Täpselt. Ja teine ​​- Mis meil veel on vaja uuendada? 

Publik: Kontrollige, kas viimase võrdub null. 

JASON Hirschhorn: kui eelmine - nii et kui eelmine võrdub null. 

Publik: See tähendab, et see saab saada pea. 

JASON Hirschhorn: See tähendab see on muutunud pea. Niisiis, mida me teeme? 

Publik: Teeme head võrdub new_node. 

JASON Hirschhorn: Head võrdub new_node. Ja miks pea siin ei loetle? 

Publik: Sest pea on ülemaailmne muutuja, mis on lähtepunkt. 

JASON Hirschhorn: Sweet. OK. Ja - 

Publik: Siis sa muidu eelmine-> Järgmise võrdub new_node. Ja siis tagasi tõsi. 

JASON Hirschhorn: Kust seadsime new_node end? 

Publik: oleksin - Ma seda alguses. 

JASON Hirschhorn: Mis liin? 

Publik: Pärast kui avaldus kontrollimine, kui see on teada. 

JASON Hirschhorn: Right here? 

Publik: Teeksin new_node-> n võrdub raha. 

JASON Hirschhorn: Kõlab hästi. Ilmselt on mõistlik - me ei pead teadma, mida nimekirjas me oleme sest me oleme ainult tegelevad ühe nimekirja. Nii parem funktsioon deklaratsioon see on lihtsalt vabaneda käesoleva täielikult ja lihtsalt sisestada väärtuse pea. Me ei peagi teadma mida nimekirjas oleme sees Aga ma hoida seda praegu ja siis muutus see pärast ajakohastamist slaidid ja kood. Nii et tundub hea nüüd. Kui väärtus - kes saab teha seda joont? Kui - Mida me teeme siin, Noah. 

Publik: Kui väärtus on suurem kui Val-> n - 

JASON Hirschhorn: Kuidas teha me minna järgmisele sõlm? 

Publik: Val-> n võrdne new_node. 

JASON Hirschhorn: Nii n on milline osa struct? Täisarv. Ja new_node on viit tipu. Millisest Val peaksime uuendada? Kui ei ole n, siis mida see teine ​​osa? Noah, mis on teine ​​osa. 

Publik: Oh, järgmine. 

JASON Hirschhorn: Järgmine, täpselt. Täpselt. Järgmine on õige. Ja mis meil veel vaja on uuendada, Noah? 

Publik: suunanäitajaks. 

JASON Hirschhorn: So me ajakohastada praegust. 

Publik: Eelmised-> kõrval. 

JASON Hirschhorn: Jah. OK, me pausi. Kes saab meid siin aidata? Manu, mida me peaksime tegema? 

Publik: Sul seada see võrdub Val-> kõrval. Aga seda, et enne eelmise rea. 

JASON Hirschhorn: OK. Midagi veel? Akshar. 

Publik: ma ei arva, et oled tähendas, et muuta Val-> Next. Ma arvan, et sa oled selleks loodud Val võrdsete Val-> kõrval minna järgmisele sõlme. 

JASON Hirschhorn: Vabandust, kus? On mida joon? See rida? 

Publik: Jah. Tee Val võrdub Val-> kõrval. 

JASON Hirschhorn: Nii et õige sest praegune on kursor sõlme. Ja me tahame seda juhtida järgmisele sõlm, mis su praegu osutas. Val ise on järgmine. Aga kui me uuendada curr.next oleme oleks ajakohastamine tegelik märkus ise, mitte siis, kui see pointer oli suunatud. Aga see rida, kuigi. Avi? 

Publik: Eelmised-> järgmine võrdub Val. 

JASON Hirschhorn: Nii et taas, kui eelmine on kursor sõlme, eel-> kõrval on tegelik pointer sõlme. Nii et see oleks ajakohastamine kursor sõlme Val. Me ei taha, et ajakohastada kursor sõlme. Me tahame, et uuendada eelmine. Niisiis, kuidas me seda teeme? 

Publik: See oleks lihtsalt eelmine. 

JASON Hirschhorn: Õigus. Eelmised on viit tipu. Nüüd oleme selle muutmist uus kursor sõlme. OK Siirtykäämme alla. Lõpuks see viimane tingimus. Jeff, mida me teeme siin? 

Publik: Kui raha on võrdne Val-> n. 

JASON Hirschhorn: Vabandust. Oh mu jumal. Mida? Väärtus == Val-> n. Mida me siis teeme? 

Publik: Sa tasuta meie new_node, ja siis sa tagasi false. 

JASON Hirschhorn: See on see, mida me oleme kirjutanud siiani. Kas kellelgi on midagi lisada enne teeme? OK. Proovime seda. Kontroll võib jõuda lõpuni mitte-tühine funktsioon. Avi, mis toimub? 

Publik: sa peaksid panna tagastamine tõsi väljaspool samas loop? 

JASON Hirschhorn: Ma ei tea. Kas sa tahad, et? 

Publik: Vahet pole. Ei. 

JASON Hirschhorn: Akshar? 

Publik: Ma arvan, et sa mõtlesid, et panna tagasi false lõpus on samas silmus. 

JASON Hirschhorn: Nii et kui sa tahad seda teha? 

Publik: Nagu väljaspool samas silmus. Nii et kui te väljute samas loop et vahendid , kui olete jõudnud lõpuks ja pole midagi juhtunud. 

JASON Hirschhorn: OK. Mida me siin teeme? 

Publik: Sa tagasi false seal hästi. 

JASON Hirschhorn: Oh, me seda mõlemas kohas? 

Publik: Jah. 

JASON Hirschhorn: OK. Kas me peaksime minema? Oh mu jumal. Vabandust. Vabandan ekraanil. See on omamoodi hullumas meist. Nii et valida valik. Zero kohta kood, sulgub programm. Üks lisab midagi. Lisame kolm. Insert ei õnnestunud. Ma lähen välja printida. Mul ei ole midagi. OK. Võib-olla see oli lihtsalt õnnelik juhus. Pange üks. Ei õnnestunud. OK. Olgem joosta GDB tõesti kiiresti vaata, mis toimub. 

Mäleta gdb. / Nime oma Programmi saab meid GDB. On seda palju, et käepide? Vilgub? Tõenäoliselt. Sule silmad ja võtta mõned sügavad hingetõmmetega kui te väsi vaadates seda. Olen GDB. Mis on esimene asi, mida ma teha GDB? Me peame välja mõtlema, mis siin toimub. Vaatame. Meil on kuus minutit näitaja saada, mis toimub. Break peamine. Ja mis ma siis teen? Carlos? Käivita. OK. Valime valik. Ja mida see N teha? Next. Jah. 

Publik: Kas sa ei maininud - sa ei öelnud, et pea oli algväärtustatud null alguses. Aga ma arvasin, et sa ütlesid, et see oli OK. 

JASON Hirschhorn: Lähme - vaatame GDB ja siis lähen tagasi. Aga see kõlab nagu teil on juba mõned mõtted selle kohta, mis toimub. Nii et me tahame lisada midagi. OK. Oleme sisestada. Palun sisestage int. Me sisestada kolm. Ja siis ma olen sellel liinil. Kuidas minna alustada silumine insert tuntud funktsioon? Oh mu jumal. Seda on palju. Kas see hullumas palju? 

Publik: Oh, see on surnud. 

JASON Hirschhorn: Ma tõmbas ta välja. OK. 

Publik: Võib-olla see on teine ​​ots traati. 

JASON Hirschhorn: Wow. Nii et alumine rida - mida sa ütlesid? 

Publik: ütlesin iroonia tehniliste raskusi sellesse klassi. 

JASON Hirschhorn: Ma tean. Kui mul oleks vaid kontrolli üle, et osa. [Kuuldamatu] See kõlab hästi. Miks sa ei poisid hakata mõtlema mida me oleks teinud valesti, ja me tagasi 90 sekundit. 

Avica, ma küsin teilt, kuidas edasi minna sees insert_node siluda ta. Nii et see on koht, kus me viimati pooleli jäi. Kuidas ma sisse minna insert_node, Avica, uurida, mis toimub? Mida GDB käsk? Break ei võtaks mind seest. Kas Marquise tead? 

Publik: Mis on? 

JASON Hirschhorn: Mis GDB käsk Ma kasutan minna sees seda funktsiooni? 

Publik: samm? 

JASON Hirschhorn: Samm kaudu S. See viib mu sees. OK. New_node mallocing ruumi. See kõik tundub tema läheb. Uurime new_node. Ta sai mõned mälu aadressi. Vaatame - see on kõik õige. Seega kõik siin tundub töötavad korralikult. 

Publik: Mis vahet vahel P ja ekraan? 

JASON Hirschhorn: P seisab kirjas. Ja nii sa küsid mis Vahe selle ja see? Sel juhul midagi. Aga üldiselt on mõningaid erinevusi. Ja siis tuleb vaadata GDB kasutusjuhend. Kuid sel juhul midagi. Me kipume kasutada print, kuigi, sest meil ei ole vaja teha palju rohkem, kui printida ühe väärtuse. 

OK. Seega on meil on line 80 meie kood, millega sõlme * Val võrdne nimekirja. Olgem välja printida Val. See võrdub nimekirja. Sweet. Oota. See võrdub midagi. See ei tundu õige. Niimoodi. See on sellepärast, GDB, parem, kui see joon oled see ei ole täidetud veel. Nii et sa pead tegelikult tüüp kõrval täita rida enne näeme selle tulemusi. Nii et siin me oleme. Me lihtsalt täide seda joont, eelmine võrdub null. Nii et taas, kui me printida eelmine me ei näe midagi imelikku. Aga kui me tegelikult täita, et line, siis näeme et see liin töötas. 

Nii et meil on Val. Need on nii hea. Eks ole? Nüüd oleme sellel joonel siin. Kuigi Val ei võrdu null. Noh, mis teeb Val võrdne? Me nägime seda korranud null. Me trükitud välja. Ma välja trükkida uuesti. Nii on, et kuigi loop läheb täide? 

Publik: Ei. 

JASON Hirschhorn: Nii et kui ma kirjutada, et line, näed me hüppas kogu tee alaserva, tagastab false. Ja siis me lähme tagasi false ja minna tagasi meie programmi ja lõpuks välja printida, nagu me nägime, insert ei õnnestunud. Niisiis, keegi on mingeid ideid selle kohta, mida meil on vaja teha, et seda parandada? Ma ootama kuni ma näen paar käed tõusevad. Me ei saa täita seda. Pidage meeles, et see oli esimene asi, mida me tegime. Ma ei kavatse seda teha paari. Ma teen mõned. Kuna paar tähendab kahte. Ma ootan rohkem kui kaks. 

Esimene sisestamise Val, vaikimisi võrdub null. Ja see loop täidab üksnes kui Val pole null. Niisiis, kuidas ma saan selle ümber? Ma näen kolme kätte. Ma ootan rohkem kui kolm. Marcus, mida sa arvad? 

Publik: Noh, kui teil on vaja täita rohkem kui üks kord, siis lihtsalt muuda see do-kui ahela. 

JASON Hirschhorn: OK. Kas see lahendada meie probleem, kuigi? 

Publik: Sel juhul ei ole, sest Asjaolu, et nimekiri on tühi. Nii siis ilmselt lihtsalt vaja lisada kinnitus, et kui silmus väljapääsu siis sa pead olema lõpus nimekirja, mille juures te lihtsalt sisestage see. 

JASON Hirschhorn: mulle meeldib. See on loogiline. Kui loop väljub - kuna naasen vale siin. Nii et kui silmus väljapääsu, siis me oleme nimekirja lõppu, või äkki alustada nimekirja, kui seal on midagi, see, mis on sama kui lõpus. Nüüd me tahame lisada midagi. Niisiis, kuidas see kood vaata, Marcus? 

Publik: Kui juba sai sõlme malloced, siis võiks lihtsalt öelda, new_node-> järgmine võrdub null, sest see peab olema lõpus. Või new_node-> järgmine võrdub null. 

JASON Hirschhorn: OK. Vabandust. New_node-> järgmine võrdub null sest me oleme lõpuks. See ei pane see sisse Kuidas me paneme selle nimekirja? Õige. See on lihtsalt, millega see võrdne. No kuidas me tegelikult pane see nimekiri? Mis osutades nimekirja lõppu? 

Publik: Head. 

JASON Hirschhorn: Vabandust? 

Publik: Head osutab Lisa lõpuks nimekirja. 

JASON Hirschhorn: Kui seal on midagi, nimekiri, pea on suunaga nimekirja lõppu. Nii et ma töötan Esimene sisestamist. Aga kui seal on paar asjad nimekirjas? Kui me ei taha seada pea võrdne new_node. Mida me tahame teha on? Jah? Arvatavasti eelmine. Kas see toimib? Tuletame meelde, et eelmine on lihtsalt kursor sõlme. Ja eelmine on kohaliku muutuja. Nii et see rida loob kohaliku muutuja, eelmine, mis on võrdne või osutades sellele uus sõlm. See ei ole tegelikult panna meie nimekirjas, kuigi. Kuidas me paneme ta meie nimekirjas? Akchar? 

Publik: Ma arvan, et sa teha praeguse-> Next. 

JASON Hirschhorn: OK. Val-> kõrval. Nii et taas, ainus põhjus, miks me oleme alla siin on, mida teeb praegune võrdne? 

Publik: Vastus null. 

JASON Hirschhorn: Ja mis juhtub, kui me teeme null-> järgmine? Mida me saame? Me saame killustatust süü. 

Publik: Do Val võrdub null. 

JASON Hirschhorn: See on sama asi nagu eelmine, aga kuna seal on kohaliku muutuja me seame võrdub see uus sõlm. Lähme tagasi meie pilt sisestades midagi. Ütle, et me lisades lõpus nimekirja, nii et siin. Meil on praegune pointer, mis on osutades tühjaks ja eelmises punktis mis sihib 8. Niisiis, mida me vajame, et ajakohastada, Avi? 

Publik: Eelmine-> järgmine? 

JASON Hirschhorn Eelmised-> kõrval on see, mida me tahame uuendada, sest see tegelikult lisab selle lõpuks nimekirja. Meil on veel üks viga, kuigi et me ei kavatse joosta. Mis see on viga? Jah? 

Publik: See läheb tagasi vale sel juhul? 

JASON Hirschhorn: Oh, ei ei läheb tagasi false. Aga on veel üks viga. Nii me vaja panna return true. 

Publik: Kas eelmine ikka võrdsed null ülaosas nimekirja? 

JASON Hirschhorn: Nii eelmine veel võrdub null alguses. Niisiis, kuidas me sellega hakkama saame? Jah? 

Publik: Ma arvan, et sa saad teha check enne kui loop, kas see on tühja nimekirja. 

JASON Hirschhorn: OK. Lähme siit. Kas kontroll. Kui - 

Publik: Nii et kui pea võrdub võrdub null. 

JASON Hirschhorn: Kui juht võrdub võrdub null - mis sa meile öelda, kas see on tühi nimekirja. 

Publik: Ja siis teha head võrdub uus. 

JASON Hirschhorn: Head võrdub new_node? Ja mis meil veel vaja teha? 

Publik: Ja siis tagasi tõsi. 

JASON Hirschhorn: Mitte päris. Meil puuduvad üks samm. 

Publik: New_node järgmine on juhtida tühjaks. 

JASON Hirschhorn: Täpselt, Alden. Ja siis me saame naasta tõsi. OK. Aga see on ikka hea mõte teha asju aasta lõpus nimekiri, eks? Hea küll. Me ikka võiks tegelikult saada Lisa lõpuks nimekirja. Nii on see kood trahvi, kui me oleme loendi lõppu ja seal on mõned asjad nimekirjas? Eks ole? Kuna meil on veel Marcus idee. Võiksime väljumiseks loop sest me aasta lõpus nimekirja. Nii et me ikka tahame seda koodi siia alla? 

Publik: Jah. 

JASON Hirschhorn: Jah. Ja mida me vajame seda muuta? True. Kas see hea hea kõigile nii palju? Keegi on - Avi, sa pead midagi lisada? 

Publik: Ei. 

JASON Hirschhorn: OK. Nii et me oleme teinud paar muutused. Me oleme teinud seda kontrolli, enne kui me läks tühja nimekirja. Nii oleme hoolitsenud tühja nimekirja. Ja siin me hoolitses sisestamist millegi lõppu nimekirja. Nii tundub, et see samas loop võtmine hoolt asjad vahel, kusagil nimekiri kui On asju, mida nimekirjas. 

OK. Olgem käivitada see programm uuesti. Ei õnnestunud. 

Publik: Sa ei teinud seda. 

JASON Hirschhorn: Oh, Ma ei teinud seda. Hea mõte, Michael. Lisame make seotud. Line 87 seal on viga. Line 87. Alden oli see liin sa mulle andsid. Mis viga? 

Publik: See peab olema tühjaks. 

JASON Hirschhorn: Suurepärane. Täpselt nii. See peaks olema null. Teeme uuesti. Koostage. OK. Lisame kolm. Insert oli edukas. Lähme välja trükkida. Oh, kui ainult me ​​võiks vaadata. Aga me ei ole teinud väljatrükki veel. Olgem sisestage midagi muud. Mida me peaksime sisenema? 

Publik: Seven. 

JASON Hirschhorn: Seven? 

Publik: Jah. 

JASON Hirschhorn: Meil ​​seg süü. Nii saime ühe, kuid me selgelt ei saa kahte. See on 05:07. Nii võiksime siluda seda kolm minutit. Aga ma lähen jäta meid siin ja liikuda edasi räsitabeli. Aga jälle, vastused selle koodi Ma saatke see teile natuke. Me oleme väga lähedal. Ma väga soovitame teil aru saada, mis siin toimub ja seda parandada. Nii et ma meilis selle koodiga hästi plus lahendus - ilmselt lahus hiljem. Esiteks on see kood. 

Teine asi, mida ma tahan teha, enne kui me viimistlus me pole vabanenud midagi. Nii et ma tahan teile näidata, mida valgrind välja näeb. Kui võtame valgrind piirid meie programmi. / seotud. Jällegi, vastavalt sellele slaidile me peaks kulgema valgrind teatud tüüpi variant, käesoleval juhul - Lekke-check = täis. Nii et kirjutame valgrind - Lekke-check = täis. Nii et see kestab valgrind meie programm. Ja nüüd programm tegelikult töötab. Nii et me ei kavatse kasutada seda nagu enne, pane midagi sisse Ma panen kolme. See toimib. Ma ei üritagi luua midagi muud, sest me ei kavatse saada seg vale sellisel juhul. Nii et ma olen lihtsalt kavatse loobuda. 

Ja nüüd te näete siin lekkida ja hunnik kokkuvõte. Need on head asjad, soovite kontrollida. Nii hunnik kokkuvõte - ta ütleb, kasutusel väljumisel - kaheksa baiti üks plokk. See üks plokk on sõlme me malloced. Michael, sa ütlesid enne sõlm on kaheksa hammustused, sest see on täisarv ja kursor. Nii et meie sõlme. Ja siis ta ütles, et me kasutada malloc seitse korda ja me vabanenud midagi kuus korda. Aga me ei helistanud tasuta, nii et ma ei ole tea, mida see räägib. 

Aga piisab, kui öelda, et kui Programm jookseb, malloc on kutsutud mõnedes teistes kohtades, et me ei ole vaja muretseda. Nii malloc ilmselt nimetatakse mõnes kohas. Me ei pea muretsema, kus. Aga see on tõesti meile. Esimene rida on meile. Me jätsime selle blokeerida. Ja te näete, et siin aastal leke kokkuvõte. Ikka leia - kaheksa baiti üks plokk. See tähendab, et mälu - oleme lekkinud, et mälu. Kindlasti kadunud - midagi on kadunud igaveseks. Üldiselt sa ei näe midagi seal. Veel kättesaadav on tavaliselt kus näete asju, kus tahad vaatame, mis koodi peaks teile on vabastatud, kuid sa unustasid tasuta. 

Ja siis, kui see nii ei olnud, kui me tegime tasuta kõik, saame näha, et. Lihtsalt käivitage programm ei lase midagi. Näete siin kasutusel exit - null baiti null plokke. See tähendab, et meil oli midagi jäänud kui see programm lahkutakse. Nii et enne keerates pset6 käivitage valgrind ja veenduge, et teil ei ole iga mälulekked oma programmi. Kui teil on küsimusi valgrind, julgelt jõuda. Aga see, kuidas sa seda kasutada. Väga lihtne - vaata, kui sa on kasutusel exit - iga baiti igal plokke. 

Nii et me töötasime sisestada sõlme. Mul oli kaks muid funktsioone siin - prindi sõlmede ja vaba sõlmed. Jällegi on need funktsioonid, mis on saab olema hea teie jaoks harjutada sest nad aitavad teil mitte ainult Nende proovi harjutusi, vaid ka probleemile kehtestada. Nad kaart üsna tihedalt asju sa lähed pead tegema lahendamist. Aga ma ei taha, et veenduda me puudutada kõike. Ja hash tabeleid on ka oluline mida me teeme jaos see nädal - või probleem komplekti. 

Nii et me ei kavatse lõpetada jagu räägime hash tabeleid. Kui märkate tegin vähe hash tabel. See ei ole see, mida me räägime kohta siiski. Me räägime eri tüüpi hash tabeleid. Ja selle keskmes, hash tabel on midagi enamat kui array pluss hash funktsiooni. Me räägime natuke lihtsalt veenduda igaüks saab aru, mida hash funktsiooni. Ja ma ütlen teile nüüd, et ta on midagi enamat kui kahte asja - massiivi ja hash funktsiooni. Ja siin on sammud läbi mis see toimib. 

Seal on meie massiivi. See on meie ülesanne. Eelkõige räsifunktsioonid vaja teha paar asja sellega. Ma lähen rääkida konkreetselt selle lahendamist. See on ilmselt läheb võtta string. Ja mis läheb tagasi? Mis andmed tüüp? Alden? Teie räsifunktsiooni tagasi? Täisarv. Nii et see on see, mida hash tabel koosneb - tabeli kujul array ja hash funktsiooni. Kuidas see töötab? See töötab kolmes etapis. Anname see võti. Sel juhul me anname seda string. Kutsume räsifunktsiooni per etapp võtme ja saame raha. 

Täpsemalt, me öelda saame täisarv. See täisarv, on väga spetsiifiline piirid, mida see täisarv võib olla. Selles näites meie massiivi on suurus kolm. Mis siis numbrid on, et täisarv olema. Mis on vahemikus kehtivad väärtused et täisarv, tagastab tüüpi see räsifunktsiooni? Null, üks ja kaks. Koht hash funktsioon on nuputada koht massiivi kus meie peamiste läheb. On ainult kolm võimalikku kohad siin - null, üks või kaks. Nii et see ülesanne suuremat tulu null, üks või kaks. Mõned kehtivad indice selle massiivi. 

Ja siis sõltuvalt sellest, kuhu ta naaseb, näete array avatud ümbritsevad väärtus. See, kui me paneme võtme. Nii et me visata kõrvits, saame välja nulli. At array sulg 0 panime kõrvits. Me visata kassid, saame välja üks. Panime kassile üks. Panime ämblik. Saame välja kaks. Panime ämblik array sulg kaks. Oleks tore, kui see töötas nii. Kuid kahjuks, nagu me näeme, see on natuke keerulisem. 

Enne kui sinna jõuame küsimusi selle põhi ülesseadmine hash tabel? See on pilt täpselt Mida me juhtis laual. Aga kuna me juhtis ta laual, I ma ei lähe see kaugemale. Sisuliselt võtmed, magic black box - või antud juhul, teal box - on räsifunktsiooni paneb neid ämbrid. Ja selles näites me oleme ei pane nimi. Me paneme seotud telefoni number nime ämbrisse. Aga sa võiksid väga hästi lihtsalt pane nimi ämbrisse. 

See on lihtsalt pilt, mida me juhtis laual. Meil on võimalikud tagasilöögid, kuigi. Ja seal on kaks eriti slaidid, et ma tahan minna üle. Esimene on umbes hash funktsiooni. Nii ma küsisin küsimuse, mis teeb hea hash funktsioon? Annan kaks vastust. Esimene on see, et see on determineeritud. In kontekstis räsifunktsiooni, Mida see tähendab? Jah? 

Publik: See võib leida indeks pidevalt aega? 

JASON Hirschhorn: See ei ole, mida see tähendab. Aga see on hea oletus. Kas keegi on vist et mida see tähendab? See hea räsifunktsiooni on determineeritud? Annie? 

Publik: See võti saab kaardistada ühe koha hash tabel. 

JASON Hirschhorn: See on täpselt õige. Iga kord, kui paned kõrvits, ta naaseb alati null. Kui paned kõrvits ja oma hash funktsioon tagastab null, kuid on naasmise tõenäosus midagi veel suurem kui null - et äkki ta saab tagasi ühe mõnikord või kaks korda - see ei ole hea räsifunktsiooni. Sa oled täpselt õige. Teie räsifunktsiooni peaks tagasi sama täpne täisarv, käesoleval juhul võtta täpselt sama string. 

Võib-olla ta naaseb sama täpne täisarv sama täpne string olenemata kapitaliseeritust. Aga sel juhul on ikka determineeritud, sest mitu asja kaardistatakse peale sama väärtusega. See on hea. Niikaua kui on olemas ainult üks väljund antud sisendi. 

OK. Teine asi on see, et tagastab kehtiv indeksid. Tõime välja, et varem. See räsifunktsiooni - oh boy - räsifunktsiooni peaks tagasi kehtiv indeksid. Nii öelda - lähme tagasi selle näite. Minu räsifunktsiooni loeb üles tähed sõna. See on hash funktsiooni. Ja tootlus täisarv. Nii et kui mul on sõna, see on läheb tagasi ühe. Ja see saab panna siin. Mis siis, kui panin sõna nahkhiir? Ta läheb tagasi kolm. Kus nahkhiir minna? 

See ei sobi. Aga ta peab minema kuhugi. See on minu hash tabel ju ja kõik peab minema kuhugi. Nii et kui peaks nahkhiir minna? Kõik mõtted? Oletused? Hea oletused? 

Publik: Zero. 

JASON Hirschhorn: Miks null? 

Publik: Sest kolm mooduli kolm on null? 

JASON Hirschhorn: Kolm mooduli kolm on null. See on suur oletus, ja see on õige. Nii et kui see peaks Tõenäoliselt lähevad nulli. Nii hea viis tagada, et see hash funktsioon annab ainult kehtiva indeksi Lisa modulo seda suurus tabelis. Kui te moodul iganes seda kasumit, kolm, sa oled alati hakka midagi vahel null, üks, kaks. Ja kui see ikka tagasi seitse ja sa alati moodul kolm, sa oled alati hakka sama asja. 

Nii et see on ikka determineeritud kui sa moodul. Aga see, et sa ei saa kunagi midagi - kehtetu tööstusele. Üldiselt see moodul peaks juhtuma sees hash funktsiooni. Nii et sa ei pea muretsema selle. Sa lihtsalt võimalik tagada, et see on kehtiv indice. Kõik küsimused selle potentsiaal lõksu? 

OK. Ja seal me läheme. Järgmine potentsiaal lõksu ja see on suur. Mida teha, kui kaks võtit kaart sama väärtus? Seega on kaks võimalust, et tegelen sellega. Esimest nimetatakse lineaarse katsetamine, mis ma olen ei lähe üle. Aga sa peaksid olema kursis, kuidas mis töötab ja mis see on. 

Teine ma lähen üle sest see on üks, et paljud inimesed ilmselt lõpuks otsustada kasutada oma probleem komplekti. Muidugi, te ei pea seda tegema. Aga probleem kogum, paljud inimesed kipuvad valima luua hash tabel eraldi Aheldamise rakendada oma sõnastikku. Nii et me läheme selle üle, mida see tähendab, luua hash tabel eraldi ühendamine. 

Nii panin kõrvits. Ta naaseb null. Ja panin kõrvitsa siin. Siis panin - Mis on veel Halloween-teemastatud asi? 

Publik: Candy. 

JASON Hirschhorn: Candy! See on suur. Panin kommi ja kommi Samuti annab mulle null. Mida ma pean tegema? Iga ideid? Kuna te kõik justkui mida eraldi ühendamine toimub. Nii tahes ideid, mida teha? Jah. 

Publik: Haara string tegelikult hash tabel. 

JASON Hirschhorn: Nii et me läheme juhtida hea mõte siin. OK. 

Publik: Kas Hashtable [Kuuldamatu] pointer, mis osutab alguses nimekirja. Ja siis on kõrvits esimene väärtus et seotud nimekirja ja kommi olema teine ​​väärtus, mis on seotud nimekirja. 

JASON Hirschhorn: OK. Marcus, see oli suurepärane. Ma lähen, et murda see maha. Marcus ütleb ei kirjutada kõrvits. See oleks halb. Ärge pange kommid kusagil mujal. Me paneme nad mõlemad nullis. Aga me ei kavatse tegeleda seades nulli luua nimekiri null. Ja me ei kavatse luua nimekirja kõik, mis kaardistatakse null. Ja parim viis, kuidas me õppinud, et luua nimekirja, mis võib kasvada ja kahaneb dünaamiliselt ei kuulu teise massiivi. Nii ei mitmemõõtmeline massiiv. Aga lihtsalt luua seotud nimekirja. 

Mis siis tegi ta ettepaneku - Ma lähen, et saada uus - on luua massiivi osuti, massiivi osuti. OK. Iga mõte või vihje, mis laadi Selle osuti olema? Marcus? 

Publik: Näiturid - 

JASON Hirschhorn: Sest sa ütles seotud nimekirjas, siis - 

Publik: Sõlme vihjeid? 

JASON Hirschhorn: Sõlme suunanäitajaks. Kui asjad meie seotud nimekiri on sõlmed, siis nad peaks olema node suunanäitajaks. Ja mida nad võrdsed esialgu? 

Publik: Null. 

JASON Hirschhorn: Null. Nii et meie tühi asi. Pumpkin tagastab null. Mida me siis teeme? Kõnni mind läbi? Tegelikult Marcus juba andsid mulle. Keegi teine ​​kõndida mind läbi. Mida me teeme, kui me - see näeb välja väga sarnane mida me lihtsalt teeme. Avi. 

Publik: ma lähen vist. Nii et kui sa saad kommi. 

JASON Hirschhorn: Jah. Noh, meil on kõrvits. Lähme meie esimene. Meil on kõrvits. 

Publik: OK. Pumpkin tagastab null. Nii et sa pane see, et. Või tegelikult, siis pane see aastal seotud nimekirja. 

JASON Hirschhorn: Kuidas me pane see seotud nimekirja? 

Publik: Oh, tegelik süntaks? 

JASON Hirschhorn: Just kõndida - rohkem öelda. Mida me siis teeme? 

Publik: Sa lihtsalt sisestada see esimene sõlm. 

JASON Hirschhorn: OK. Nii et meil on meie sõlme, kõrvits. Ja nüüd, kui ma lisada seda? 

Publik: määrake see osuti. 

JASON Hirschhorn: Milline pointer? 

Publik: pointer null. 

JASON Hirschhorn: Nii et kui kas selles küsimuses? 

Publik: Null kohe. 

JASON Hirschhorn: Noh, see osutavad tühjaks. Aga ma panen kõrvits. Nii et kust see mõte? 

Publik: Pumpkin. 

JASON Hirschhorn: Et kõrvits. Täpselt. Seega viitab see kõrvits. Ja kui ei, see pointer kõrvits punkt? Kuni 

Publik: Null. 

JASON Hirschhorn: Null. Täpselt. Nii et me lihtsalt lisada midagi arvesse seotud nimekirja. Me lihtsalt kirjutasin selle koodi seda teha. Peaaegu me peaaegu sain selle täiesti katki. Nüüd sisesta kommi. Meie candy läheb ka nulli. Niisiis, mida me teeme koos kommi? 

Publik: See sõltub sellest, kas ei me üritame sorteerida. 

JASON Hirschhorn: See on täpselt õige. See sõltub sellest, kas me üritame sorteerida. Oletame, et me ei ole läheb sortida. 

Publik: Noh, siis, kui me arutasime enne, see on lihtsaim lihtsalt panna see kohe alguses nii pointer nullist võrra kommi. 

JASON Hirschhorn: OK. Oota. Lubage mul luua kommi siin. Nii et see pointer - 

Publik: Jah, peaks nüüd osutades kommi. Siis on pointer candy käsk kõrvits. 

JASON Hirschhorn: Niimoodi? Ja ütleme, et meil on veel üks asi kaardistada nulli? 

Publik: Noh, sa lihtsalt teha sama asi? 

JASON Hirschhorn: Kas sama asi. Nii et sel juhul, kui me ei tahad hoida järjestatud see Kõlab üsna lihtne. Võtame kursorit indice andnud meie hash funktsiooni. Meil on selles küsimuses meie uus sõlm. Ja siis mis see oli suunaga varem - sel juhul null, in Teisel juhul kõrvits - mis iganes see osutab varem, lisame järgmisesse kohta meie uus sõlm. Me lisades midagi aasta alguses. Tegelikult on see palju lihtsam kui püüame hoida nimekirja sorteerida. Aga jälle, otsides saab keerulisem on siin. Meil on alati minna lõpuni. 

OK. Küsimusi eraldi ühendamine? Kuidas see toimib? Palun paluge nüüd. Ma tõesti tahan, veendumaks, et kõik mõista seda enne kui me suundume. 

Publik: Miks sa paned kõrvits ja kommi samasse osa hash tabel? 

JASON Hirschhorn: Hea küsimus. Miks me panna neid sama osa hash tabel? Noh, sel juhul meie räsifunktsiooni tagasi nulli mõlemad. Nii et nad peavad minema kell indice null sest see on kui me ei kavatse otsima neid, kui me kunagi tahan vaadata neid. Jällegi, kusjuures lineaarne sondeerimise lähenemisviisi me ei pane neid nii nullis. Kuid eraldi hõlmav lähenemisviis, me panna neid nii nullis ja seejärel luua nimekirja ära nullis. 

Ja me ei taha kirjutada kõrvits lihtsalt selle eest, sest siis me eeldada, et kõrvits oli kunagi sisestatud. Kui me lihtsalt hoida ühte asja asukoht, mis oleks halb. Siis ei oleks Vihma meile kunagi - kui me kunagi eksemplaris, siis me oleks lihtsalt kustutada meie esialgsest väärtusest. Nii et miks me seda lähenemist. Või sellepärast valisime - kuid jällegi, me Valisin eraldi Aheldamise meetod, mis on palju muid lähenemisviise keegi võiks valida. Kas see vastab su küsimusele? 

OK. Carlos. Linear katsetamine tähendaks - kui me leidsime kokkupõrge nullis me näeks järgmises kohapeal näha, kui see oli lahti ja pane see sinna. Ja siis me vaatame järgmise sport ja kas see oli lahti ja pane see sinna. Nii leiame järgmise saadaval avatud kohapeal ja pani selle sinna. Muid küsimusi? Jah, Avi. 

Publik: Nagu järelmeetmena, et mida sa mõtled järgmine koht? In hash tabel või seotud nimekirja. 

JASON Hirschhorn: Lineaarsete programmeerimine, ei ahelloendid. Järgmine kohapeal hash tabel. 

Publik: OK. Nii hash tabel oleks initsialiseeritud suurus - nagu Sõnesid et sa olid sisestamist? 

JASON Hirschhorn: Sa ei teeks tahan, et see oleks tõesti suur. Jah. Siin on pilt, mida me lihtsalt juhtis laual. Jällegi, meil on kokkupõrge siin. juures 152. Ja te näete, oleme loonud seotud nimekirja välja sellest. Jällegi, hash tabelis eraldi Aheldamise lähenemine on vale võtma ette püstitatud probleeme Kuue kuid on üks, mis palju üliõpilased kipuvad võtma. Seega on see teatis rääkigem lühidalt enne kui me suundume katkisest kuus, ja siis ma jagan lugu teiega. Meil on kolm minutit. 

Ülesanded kuus. Sul on neli funktsiooni - koormus, kontrollige, suurus, peale-ja mahalaadimist. Load - Noh, me oleme käinud üle koormus lihtsalt nüüd. Jälle koormus laual. Ja me isegi alustanud kodeerimine palju sisestamist seotud nimekirja. Nii juures on palju rohkem kui mida me oleme lihtsalt teinud. 

Check on, kui sul on midagi laadida. On sama protsessi nagu seda. Samal kaks esimest osa, kus sa visata midagi sisse räsifunktsiooni ja saada oma raha. Aga nüüd me ei sisestamist. Nüüd me otsime seda. Olen proovi kood kirjutatud leidmiseks midagi, mis on seotud nimekirja. Ma kutsun teid üles harjutama seda. Aga intuitiivselt leida midagi üsna sarnane, lisades midagi. Tõepoolest, me joonistasin pildi leidmine midagi, mis on seotud nimekirja, liikudes läbi kuni sul lõpuks. Ja kui sul lõpuni ja ei suutnud leia seda, siis see ei ole seal. Nii et vaatame, sisuliselt. 

Järgmine on suurus. Jätame suurus. Lõpuks olete maha laadida. Sulgeda on üks me ei ole koostatud lauale või kodeeritud veel. Aga ma kutsun teid proovida kodeerimine see meie proovi seotud nimekirja näide. Aga lossimiseks intuitiivselt sarnaneb tasuta - või ma mõtlen on sarnane kontrollida. Välja arvatud nüüd iga kord, kui sa lähed läbi, sa ei lihtsalt kontrollisin, kas teil on oma raha sinna. Aga te võtate, et sõlm ja vabastades ta sisuliselt. Seda unload sul teha palub. Vaba kõik olete malloced. Nii et sa lähed läbi kogu nimekiri jälle läbimas kogu hash laua uuesti. Seekord ei vaadata näha, mis seal on. Just vaba, mis seal on. 

Ja lõpuks suurus. Suurus tuleks rakendada. Kui sul ei ole ellu suurus - Ma ütlen seda niimoodi. Kui sul ei ole ellu suurus täpselt üks rida koodi ka tagasi avalduse, siis on teeme suurus valesti. Seega veenduge, et suurus, täielik disain punkte, et sa teed seda täpselt üks koodirida, sealhulgas tagastamise avalduse. 

Ja ärge pakkige veel Akchar. Työhullu. Ma tahtsin öelda, tänan teid tulite osa. Kas Happy Halloween. See on minu kostüüm. Ma kannan seda neljapäeval kui ma näen sind tööajal. Ja kui sa oled uudishimulik veel tausta, et see kostüüm, tunda tasuta kontrollida 2011 jagu jaoks lugu sellest, miks ma olen seljas kõrvitsa kostüümi. Ja see on kurb lugu. Seega veenduge, et teil on teatud kudede lähedal. Aga see, kui teil on küsimused Pistan ümber väljaspool pärast jagu. Õnn lahendamist kuus. Ja nagu alati, kui teil on küsimusi, andke mulle teada.