[Daqq tal-mużika] 

ANDI Peng: Merħba għal 6 ġimgħa tas-sezzjoni. Aħna ddevjat mill-istandard tagħna taqsima ħin tat-Tlieta wara nofsinhar għal dan Ħadd filgħodu sabiħ. Grazzi għal kulħadd li ssieħbu lili llum, iżda serjament, rawnd ta 'applause. 

Li sforz pretty big. I kważi ma anki li jrendi din up fil-ħin, iżda Kien OK. So I jafu li kollha inti għadhom kemm għamilha biex l-kwizz. L-ewwelnett, merħba lill in-naħa flip ta 'dak. 

It-tieni, aħna ser nitkellmu dwar dan. Aħna ser jitkellmu dwar il-kwizz. Aħna ser jitkellmu dwar kif li qed isir fil-klassi. Int ser tkun multa. Għandi kwizzijiet tiegħek għall inti fl-aħħar minn hawn, hekk jekk inti guys tixtieq li tieħu a tħares lejn din, totalment multa. 

Allura malajr qabel nibdew, l Aġenda għal-lum hija kif ġej. Kif tistgħu taraw, aħna qed isparar mgħaġġel bażikament permezz mazz sħiħ ta 'strutturi ta' dejta tassew, tassew, tassew malajr. Allura bħala tali, mhux se jkun illum super interattivi. Dan ser ikun biss me tip ta 'shouting affarijiet li inti, u jekk I jħawdu inti, jekk jien ser wisq malajr, let me know. Huma qed data biss varji istrutturi, u bħala parti ta pset tiegħek għal dan ġimgħa li jmiss, inti ser jkunu mitluba li jimplimentaw waħda minnhom, aktarx tnejn mill them-- tnejn minnhom fil pset tiegħek. OK, hekk jien biss se tibda b'xi avviżi. Aħna ser jmorru fuq stacks u kjuwijiet aktar fil fond minn dak li għamilna qabel l-kwizz. Aħna ser jmorru fuq marbuta lista darb'oħra, għal darb'oħra, aktar fil-fond minn dak li kellna qabel l-kwizz. U allura aħna ser nitkellmu dwar hash tabelli, siġar u jipprova, li huma kollha pretty meħtieġa għall pset tiegħek. U allura aħna ser jmorru fuq xi pariri utli għall pset5. 

OK, hekk kwizz 0. Il-medja kien 58%. Huwa kien baxx ħafna, u għalhekk inti guys kollha ma ħafna, tajjeb ħafna skond ma 'dak. 

Pretty ħafna, ir-regola ta 'thumb huwa jekk int fi devjazzjoni standard tal-medja speċjalment peress li aħna qed fl għal inqas taqsima comfy, int totalment multa. Inti fuq il-binarji. Life hija tajba. 

Naf huwa scary biex jaħsbu li I ltqajna bħal 40% fuq dan il-kwizz. Jien ser jonqsu din il-klassi. I wegħda inti, int mhux ser jonqsu l-klassi. Inti totalment multa. 

Għal dawk minnkom li ltqajna fuq il-medja, impressjonanti, impressjonanti, bħal, magħmul serjament ukoll. I jkollhom magħhom miegħi. Ħossok liberu li ġejjin tikseb minnhom fl-aħħar tat-taqsima. Let me know jekk għandek xi kwistjonijiet, mistoqsijiet magħhom. Jekk aħna żid punteġġ tiegħek ħażin, let us know. 

OK, hekk pset5, dan huwa verament ġimgħa stramb għall Yale fis-sens li pset tagħna huwa dovut L-Erbgħa f'nofsinhar inkluża il ġurnata tard, dan huwa attwalment teoretikament dovut it-Tlieta f'nofsinhar. Probabbilment ebda wieħed lest fil it-Tlieta f'nofsinhar. C'est totalment multa. Aħna ser ikollhom ħinijiet tal-uffiċċju tonight kif ukoll it-Tnejn filgħaxija. U kollha tat-taqsimiet din il-ġimgħa se fil-fatt jiġu trasformati workshops, hekk li tħossok liberu li pop kwalunkwe taqsima trid, u dawn ser ikunu tip ta 'mini-pset workshops għall-għajnuna fuq dik. Allura bħala tali, dan huwa l-uniku sezzjoni fejn aħna qed materjal ta 'tagħlim. L-taqsimiet l-oħra se jkun qed jiffoka esklussivament fuq għajnuna għall-pset. Yeah? 

UDJENZA: Fejn huma ħinijiet tal-uffiċċju? 

ANDI Peng: Uffiċċju siegħa tonight-- oh, mistoqsija tajba. Naħseb ħinijiet tal-uffiċċju tonight huma Teal jew fuq Commons. Jekk inti tiċċekkja CS50 online u inti tmur ħinijiet tal-uffiċċju, għandu jkun hemm skeda li jgħidlek fejn kollha kemm huma. 

Naf kemm tonight jew għada huwa Teal, u I think we jista 'jkollhom commons għall oħra bil-lejl. M'inix ċert. Tajba kwistjoni. Iċċekkja fuq CS50. 

Kessaħ, xi mistoqsijiet rigward il iskeda għal dak li jmiss simili tlett ijiem? I wegħda inti guys bħal David qal, dan huwa l-quċċata tal-hill. You guys huma kważi hemm. Just tlett ijiem aktar. Naslu s'hemm, u allura aħna ser kollha jiġu stabbiliti. Aħna ser ikollhom break CS-free sbieħ. Aħna ser jiġu lura. Aħna ser adsa fis web ipprogrammar u l-iżvilupp, affarijiet li huma ħafna gost meta mqabbla xi wħud mill-psets oħra. U dan ser ikun chill, u aħna ser ikollhom lottijiet ta 'gost. Aħna ser ikollhom aktar kandju. Sorry għall-ħelu. I nesa kandju. Kien filgħodu rough. Allura inti guys huma kważi hemm, u jien verament kburi inti guys. 

OK, hekk stacks. Min iħobb il-mistoqsija dwar Jack u ħwejjeġ tiegħu fuq l-kwizz? Hadd? OK, li l-multa. 

Allura essenzjalment kemm tista ' stampa Jack, dan Guy hawn, tant iħobb li jieħdu l-ħwejjeġ mill-quċċata tal-munzell, u hu tqiegħdu lura fuq il-munzell wara li isir. Allura b'dan il-mod, hu qatt jidher li jkollna għall-qiegħ tal- munzell fil-ħwejjeġ tiegħu. Allura dan it-tip ta tiddeskrivi l-istruttura bażika tad-data ta 'kif munzell tiġi implimentata. 

Essenzjalment, think ta ' munzell bħala kwalunkwe munzell ta 'oġġetti fejn inti tpoġġi l-affarijiet fuq il-quċċata, u allura inti pop minnhom barra mill-quċċata. Allura LIFO huwa l-akronimu aħna nixtiequ li use-- Aħħar, First Out. U hekk aħħar fil-quċċata ta 'l- munzell hija l-ewwel waħda li toħroġ. U għalhekk iż-żewġ termini aħna nixtiequ li jassoċjaw ma 'dak huma msejħa push u pop. Meta timbotta xi ħaġa fuq il- munzell, u inti pop lura up. 

U so I raden dan huwa tip ta ' kunċett astratt għal dawk minnkom li jixtiequ jaraw bħal implimentazzjoni attwali ta 'din fid-dinja reali. Kemm inti ktibt esej forsi bħal siegħa qabel din kienet dovuta, u inti aċċidentalment mħassra enormi blokki ta 'dan, bħal aċċidentalment? U allura dak il-kontroll do nużaw biex jitqiegħdu lura? Kontroll Z, yeah? Kontroll Z, għalhekk l-ammont ta 'drabi li Control-Z ffranka-ħajja tiegħi, ffranka ħmar tiegħi, kull darba li l-implimentazzjoni minn ċumnija. 

Essenzjalment l-informazzjoni kollha li fuq id-dokument Word tiegħek, jiġrilha mbuttati u popped fil-se. U hekk essenzjalment kull meta inti tħassar xejn, inti pop lura up. U allura jekk għandek bżonn lura fuq, inti timbotta lilha, li huwa dak ta 'Kontroll-C ma. U funzjoni dinja hekk reali ta 'struttura data kif sempliċi jistgħu jgħinu bl ħajja ta 'kuljum tiegħek. 

Allura Struct huwa l-mod li aħna fil-fatt joħolqu munzell. Aħna tip jiddefinixxu Struct, u mbagħad aħna sejħa hija munzell fil-qiegħ. U fil-munzell, għandna żewġ parametri li nistgħu essenzjalment timmanipola, hekk aħna char kapaċità kordi stilel. 

Dak kollu li huwa qed tagħmel qed toħloq firxa li nistgħu jaħżen xi trid li nistgħu jiddeterminaw kapaċità tagħha. Kapaċità hija biss l-ammont ta 'max oġġetti nistgħu npoġġu fis dan array. daqs int huwa l-counter li jżomm rekord ta 'kemm oġġetti huma attwalment fil-ċmieni. Allura allura aħna tista 'żżomm rekord ta', A, kemm kemm tkun kbira l munzell attwali hija, u, B, kemm ta 'dak munzell aħna mimlija għaliex aħna ma rridux li jfur fuq dak kapaċità tagħna huwa. 

Hekk per eżempju, dan sabiħ kwistjoni kienet fuq kwizz tiegħek. Essenzjalment kif nistgħu push fuq il-quċċata ta 'ċumnija. Pretty sempliċi. Jekk inti tħares lejn din, aħna ser jimxu permezz ta 'dan. Jekk [inaudible] size-- ftakar, kull meta inti jridu aċċess għal kull parametru fi Struct, inti tagħmel l-isem tal-struct.parameter. 

F'dan il-każ, s hija l-isem ta 'munzell tagħna. Aħna rridu li l-aċċess tad-daqs ta 'dan, hekk nagħmlu s.size. Dan sakemm id-daqs mhuwiex daqs kapaċità jew sakemm kif huwa inqas minn kapaċità, jew tkun taħdem hawn. 

Inti tixtieq li aċċess għall-ġewwa tal munzell tiegħek, so s.strings, u int se timplimenta dak in-numru ġdid li inti tixtieq li ddaħħal fil hemmhekk. Ejja ngħidu biss aħna se tkun trid daħħal int n fuq il-munzell, stajna nagħmlu s.strings, parentesi, s.size ugwali n. Minħabba d-daqs huwa fejn aħna bħalissa huma fil-ċmieni jekk aħna qed tmur biex timbotta fuq, aħna biss aċċess kull fejn id-daqs huwa, l- milja attwali tal-munzell, u aħna imbotta l-n int fuq dan. U allura aħna tixtieq li tagħmel ċert li aħna wkoll qed inkrementazzjoni daqs tal-n, hekk aħna tista 'żżomm rekord ta konna miżjud ħaġa żejda għall-munzell. Issa għandna daqs akbar. Does this hawn jagħmilx sens li kulħadd, kif loġikament taħdem? Kien tip ta 'malajr. UDJENZA: Tista tmur fuq l s.stringss.strings [s.size] mill-ġdid? ANDI Peng: Sure, iva, liema ma s.size bħalissa tagħtina? UDJENZA: Hu l-daqs attwali. ANDI Peng: Eżattament, sabiex il- indiċi attwali li d-daqs tagħna hija fil- u hekk irridu li tqiegħed il-numru sħiħ l-ġdida li aħna rridu li ddaħħal fil s.size. Does li jagħmel sens? Minħabba s.strings, dak kollu li huwa huwa l-isem tal-firxa. Kollox huwa huwa aċċess għall- firxa fi ħdan Istituzzjonjijiet tagħna, u għalhekk jekk irridu post n f'dak l-indiċi, nistgħu biss aċċess għaliha jużaw parentesi s.size. Kessaħ. 

Dritt kollox, pop, I pseudocode out għalik guys, iżda kunċett simili. Does li jagħmel sens? Jekk id-daqs huwa akbar minn żero, allura inti taf li inti tixtieq li tieħu xi ħaġa barra minħabba jekk id-daqs ma tkunx akbar minn żero, allura inti m'għandhom xejn in-munzell. 

Allura inti biss tixtieq li tesegwixxi dan il-kodiċi, jista biss pop jekk hemm xi ħaġa li pop. Mela jekk id-daqs huwa akbar minn 0, aħna nieqes id-daqs. Aħna decrement-daqs u mbagħad jirritornaw dak kollu li huwa ġewwa ta 'dan minħabba billi popping, irridu aċċess kollu li huwa maħżun fl-indiċi tal-quċċata tal-munzell. Kollox jagħmel sens? Jekk I magħmula inti guys tikteb dan out, Kieku inti guys tkun tista 'tikteb it out? OK, inti guys tista 'tilgħab madwar magħha. Nru inkwiet jekk inti ma ġġibu. Aħna ma jkollhom il-ħin għall-kodiċi it out illum għaliex konna qbilna ħafna ta 'dawn l-istrutturi jgħaddu, iżda essenzjalment pseudocode, ħafna, simili ħafna biex timbotta. Just isegwu tul il-loġika. Kun żgur li int qed jaċċessaw l- karatteristiċi ta 'Struct tiegħek b'mod korrett. Yeah? 

UDJENZA: Se dawn slides u din il-ħaġa sħiħa tkun aġġornata llum ish? ANDI Peng: Dejjem, Yep. Jien ser tipprova tpoġġi dan up bħal siegħa wara. I ser email David, David se tipprova poġġih bħal siegħa wara dan. 

OK, hekk allura aħna qed jersqu lejn din oħra istruttura tad-data sabiħ imsejħa kju. Kif inti guys tista 'tara hawn, a kju, għall-British fostna, kollox huwa hija linja. Allura kuntrarjament għal dak taħseb munzell hu, kju huwa eżattament dak li loġikament inti taħseb li hu. Huwa miżmuma mir-regoli ta 'FIFO, li hija l-Ewwel Fil, L-ewwel Out. Jekk int l-ewwel wieħed fil-linja, int l-ewwel waħda li toħroġ mill-linja. 

Allura dak li aħna nixtiequ sejħa dan huwa dequeueing u enqueueing. Jekk irridu li żżid xi ħaġa li kju tagħna, aħna enqueue. Jekk irridu li dequeue, jew jieħdu xi ħaġa bogħod, aħna dequeue. 

Allura istess sens li aħna qed tip ta ' ħolqien Elementi daqs fiss li aħna jista 'jaħżen ċerti affarijiet, iżda nistgħu wkoll bidla fejn aħna qed tqegħid parametri ġewwa minnhom ibbażati fuq liema tip ta ' funzjonalità rridu. Allura stacks, ridna l-aħħar wieħed, N tkun l-ewwel wieħed out. Kju huwiex irridu l-ewwel ħaġa fil li tkun l-ewwel ħaġa out. 

Allura l--tip Istituzzjonjijiet jiddefinixxu, kif tistgħu taraw, huwa xi ftit differenti minn dak il-munzell kien għaliex mhux biss għandna għandhom iżommu kont ta 'fejn id-daqs huwa attwalment, aħna rridu wkoll li jżommu rekord tar-ras kif ukoll fejn aħna bħalissa. So I think it'sa aktar faċli jekk I tfassal dan up. Mela ejja jimmaġina konna ltqajna kju, so ejja ngħidu l-kap huwa dritt hawn. Il-kap tal-linja, ejja biss jgħidu li bħalissa hemm, u rridu li daħħal xi ħaġa fil-kju. Jien ser sejħa daqs essenzjalment huwa l-istess ħaġa bħat denb, l-aħħar tal kulfejn kju tiegħek. Ejja ngħidu biss daqs huwa dritt hawn. 

Allura kif ma possibbilment wieħed daħħal xi ħaġa fi kju? Dak indiċi irridu li ssir fejn irridu li ddaħħal fil. Jekk dan huwa l-bidu ta 'tiegħek kju u dan huwa l-aħħar ta 'dan jew id-daqs ta 'dan, fejn do we trid iżżid l-oġġett li jmiss? 

UDJENZA: [inaudible] ANDI Peng: Eżattament, inti trid iżżid dan jiddependi fuq usted miktuba fuqha. Jew tapplika din huwa vojt jew li huwa vojt. Allura inti trid iżżid hija probabbilment hawnhekk għaliex jekk id-daqs is-- jekk dawn huma kollha sħiħa, inti tixtieq li żżid dan id-dritt hawn, id-dritt? 

U hekk dan huwa, filwaqt li ħafna, ħafna sempliċi, pjuttost mhux dejjem korretta minħabba d-differenza ewlenija bejn kju u munzell huwa li l-kju jista fil-fatt jiġu manipulati sabiex it-tibdiliet ras jiddependi fuq fejn inti tixtieq il-bidu ta 'CUÉ tiegħek biex tibda. U bħala riżultat, denb tiegħek huwa wkoll se jibdlu. U hekk tagħti ħarsa lejn dan il-kodiċi dritt issa. Kif inti guys kienu mitluba wkoll biex jikteb fuq il-kwizz, enqueue. Forsi aħna ser nitkellmu permezz għaliex ir-risposta kienet dak li kien. 

I ma setgħux pjuttost tajbin din il-linja fuq naħa waħda, iżda essenzjalment din il-biċċa ta 'kodiċi għandha tkun fuq linja waħda. Onfoq bħal 30 sekonda. Agħti ħarsa, u ara għaliex dan huwa l-mod li jkun. 

Ħafna, Struct simili ħafna, ħafna, ħafna struttura simili bħala l-preċedenti munzell ħlief għall forsi linja waħda tal-kodiċi. U li linja waħda tal-kodiċi jiddetermina l-funzjonalità. U verament tiddistingwi kju minn munzell. 

Kull min jixtiequ li tieħu stab li tispjega għaliex inti ħadthom sibt dan ħaġa kkumplikata fil hawn? Naraw ir-ritorn ta 'tagħna modulus ħabib isbaħ. Kif inti guys dalwaqt se jidħlu li jirrikonoxxu fl-ipprogrammar, kważi ghaċ għandek bżonn xi ħaġa biex nagħlaq madwar xejn, modulus se jkun il-mod biex tagħmel dan. Allura jafu li, ma kull min jixtiequ li tipprova tispjega dik il-linja tal-kodiċi? Yeah, tweġibiet kollha huma aċċettati u jilqgħu. UDJENZA: Inti titkellem lili? ANDI Peng: Yeah. UDJENZA: Oh, no sorry. ANDI Peng: OK, so ejja jimxu permezz ta 'dan il-kodiċi. Allura meta inti qed tipprova żid xi ħaġa fuq kju, fil-każ sabiħ li l-kap jiġri li jkun dritt hawn, huwa faċli ħafna għalina li jmorru biss l-aħħar daħħal xi ħaġa, id-dritt? Iżda l-punt kollu ta 'kju huwiex li l-kap jista 'attwalment dinamiku jinbidlu skond fejn aħna jridu li l-bidu ta 'q tagħna li tkun, u bħala tali, il-denb huwa wkoll se jibdlu. 

U hekk jimmaġina li dan ma kienx il- kju, iżda pjuttost dan kien il-kju. Ejja ngħidu l-kap huwa dritt hawn. Ejja ngħidu kju tagħna dehru qishom dan. Jekk ridna li ċċaqlaq fejn il-bidu tal-linja hija, ejja ngħidu aħna qalbu ras B'dan il-mod u daqsijiet hawn. 

Issa rridu li żżid xi ħaġa li dan kju, iżda bħala inti guys tista 'tara, mhuwiex daqshekk sempliċi kemm biss żid dak kollu li huwa wara l-daqs għaliex allura aħna jispiċċaw ta ' limiti ta 'firxa attwali tagħna. Fejn irridu verament jżidu huwa hawnhekk. Dik hija l-sbuħija ta 'kju hija li lilna, viżwalment it qisu l-linja tmur bħal dan, iżda meta maħżuna fi struttura tad-data, dawn jagħtu bħala simili ċiklu. Hija tip ta 'garżi madwar il-quddiem bl-istess mod li linja tista 'wkoll wrap madwar jiddependi fuq fejn inti jridu bidu tal-linja li tkun. U hekk jekk nieħdu tfittex l isfel hawn, ejja ngħidu aħna riedu joħolqu funzjoni msejħa enqueue. Ridna li jżidu int n f'dak q. Jekk q.size q-- aħna ser sejħa li data tagħna structure-- jekk queue.size tagħna ma daqs kapaċità jew jekk huwa inqas minn kapaċità, q.strings huwa l-firxa fi ħdan q tagħna. Aħna qed tmur biex jistabbilixxu li daqs q.heads, li huwa dritt hawn, plus q.size modulus bil-kapaċità li wrap us lura madwar hawn. 

Allura f'dan l-eżempju, indiċi ta 'ras huwa 1, id-dritt? L-indiċi ta 'daqs huwa ta' 0, 1, 2, 3, 4. Allura nistgħu nagħmlu 1 plus 4 modulus mill-kapaċità tagħna li huwa 5. Xi jfisser li tagħtina? X'inhu l-indiċi li toħroġ ta 'dan? 

UDJENZA: 0. 

ANDI Peng: 0, li jiġri li jkun dritt hawn, u għalhekk irridu nkunu kapaċi li ddaħħal fil dritt hawn. U hekk din l-ekwazzjoni hawn it-tip ta 'ftit jaħdem ma' kull numri jiddependi fuq fejn tiegħek ras u daqs tiegħek huma. Jekk inti taf x'inhuma dawn affarijiet huma, inti taf eżattament fejn inti tixtieq li daħħal dak kollu li huwa wara kju tiegħek. Does li jagħmel sens għal kulħadd? 

Naf tip ta 'brain teaser speċjalment peress li dan daħal fil-konsegwenzi tal kwizz tiegħek. Iżda nisperaw kulħadd issa tista 'tifhem għaliex din is-soluzzjoni jew dan funzjoni huwa l-mod li jkun. Kulħadd daqsxejn mhux ċari fuq dan? KOLLOX SEW. 

U hekk issa, jekk inti riedu dequeue, dan huwa fejn ras tagħna tkun ċaqliq għaliex jekk konna biex dequeue, ma neħdux off-aħħar tal-q. Aħna rridu li jieħdu off-ras, id-dritt? Allura bħala riżultat, ras huwa se jibdlu, u huwa għalhekk li meta inti enqueue, inti stajt ltqajna biex iżommu kont ta ' fejn ras tiegħek u d-daqs tiegħek għandhom ikunu kapaċi li daħħal fil-pożizzjoni korretta. 

U hekk meta inti dequeue, I wkoll pseudocode out. Ħossok liberu li jekk inti tixtieq li tipprova kodifikazzjoni dan out. Inti tixtieq li jċaqalqu l-ras, id-dritt? Jekk jien ridt li dequeue, I se jimxu l fuq ras. Dan ikun il-kap. 

U d-daqs attwali tagħna se naqqas għaliex aħna m'għadx jkollhom erba 'elementi fil-firxa. Aħna biss tlieta, u mbagħad irridu li jirritornaw x'ikun kien maħżun ġewwa tar-ras għaliex irridu li jieħdu din valur hekk simili ħafna għall-munzell. Just tkun qed tieħu minn post differenti, u inti għandek jassenja mill-ġdid pointer tiegħek għall-post differenti bħala riżultat. Loġikament, kulħadd jsegwu? Great. 

OK, hekk aħna qed tmur biex jitkellmu ftit aktar fil-fond dwar listi marbuta minħabba dawn ser ikunu ħafna, ħafna valur għalik fil-kors ta 'din il-ġimgħa psets. Listi marbuta, kif inti guys tistax tiftakar, kollox huma huma lymph nodes li huma ta 'ċerti Valuri kemm ta 'valur u pointer li huma marbuta flimkien minn dawk pointers. U għalhekk l-Istituzzjonjijiet dwar kif noħolqu node hawnhekk hija li aħna jkollhom int n, li hija tkun xi tkun il-valur fil-maħżen jew string n jew kwalunkwe inti tixtieq li sejħa hija, il n istilla char. Struct star node, li hija l-pointer li inti tixtieq li jkollok f'kull node, int ser ikollhom li punt pointer lejn jmiss. Int ser ikollok l-kap ta 'lista marbuta li l- ser punt li l-bqija ta ' il-valuri hekk u ibqa 'sejjer hekk sakemm inti eventwalment jilħqu t-tmiem. U dan l-aħħar node huwa biss se ma jkollhomx pointer. Li għaddej biex jindika null, u li meta inti taf li inti ħadthom laqat il- tmiem tal-lista marbuta tiegħek huwa meta l-aħħar pointer tiegħek ma jwassalx għal xi ħaġa. 

Allura aħna qed tmur biex jmorru daqsxejn aktar fil fond dwar kif wieħed ikun possibilment tfittxija lista marbuta. Ftakar liema huma wħud mill- iżvantaġġi tal-listi marbuta versi firxa rigward tfittxijiet. Firxa Tista 'tfittex binarja, iżda għaliex ma tistax inti tagħmel dan fil-lista marbuta? 

UDJENZA: Minħabba dawn qed kollha konnessi, imma inti ma pjuttost taf fejn [Inaudible]. 

ANDI Peng: Yeah, eżattament sabiex tiftakar li l-brilliance ta 'firxa kien il-fatt li kellna memorja t'aċċess bl-addoċċ fejn jekk jien ridt il-valur mill-indiċi sitt, I tista 'biss jgħidu indiċi sitt, tagħti me dak il-valur. U dan għaliex arrays huma magħżula fi spazju kontigwi ta 'memorja f'post wieħed, filwaqt tip ta 'listi marbuta huma saltwarjament b'intervall kollha madwar, u l-uniku mod inti tista 'ssib wieħed huwa permezz ta 'werrej li jgħidlek l-indirizz ta 'fejn dik node li jmiss huwa. 

U hekk bħala riżultat, l-uniku mod tiftix permezz ta 'lista marbuta huwa tfittxija lineari. Minħabba I ma jafu eżattament fejn il-valur 12 fil-lista marbuta hi, Għandi biex travers il intier ta 'li wieħed lista marbuta billi wieħed mill-ras għall-ewwel node, għat-tieni node, għat-tielet node, it-triq kollha sal I finalment nikseb fejn dak node jien infittxu huwa. U hekk f'dan is-sens, tfittxija fuq lista marbut huwa dejjem n. Huwa dejjem n. Huwa dejjem fil-ħin lineari. 

U għalhekk il-kodiċi li fih nimplimentaw dan, u dan huwa daqsxejn ġdida għalik guys peress li inti guys ma verament tkellem dwar jew qatt pointers dehru fil kif tfittxija permezz pointers, hekk aħna ser jimxu permezz dan ħafna, bil-mod ħafna. Allura tfittxija BOOL, id-dritt, ejja jimmaġina li rridu biex joħolqu funzjoni msejħa tfittxija li jirritorna veru jekk inti sibt valur ġewwa l-marbutin lista, u dan jirritorna falza mod ieħor. Lista star Node hija bħalissa biss il-pointer li l-ewwel punt fil-lista marbuta tiegħek. int n huwa l-valur li int tiftix għal f'dik il-lista. 

Allura star node pointer ugwali lista. Dan ifisser li aħna qed jistabbilixxu u l-ħolqien ta 'pointer għal dak l-ewwel node ġewwa tal-lista. Kulħadd miegħi? Hekk jekk konna biex tmur lura hawn, I jkollhom initialized pointer li l-punti li il-kap ta 'kwalunkwe dik il-lista hija. 

U mbagħad darba inti tikseb l isfel hawn, filwaqt pointer ma null ugwali, b'tali mod li huwa l-linja li aħna se tkun sussegwentement jaqsmu il-bqija tal-lista tagħna għaliex dak jiġri meta pointer ugwali null? Aħna nafu li aħna have-- 

UDJENZA: [inaudible] 

ANDI Peng: Eżattament, hekk aħna nafu li konna laħqu t-tmiem tal-lista, id-dritt? Jekk inti tmur lura hawn, kull node għandhom ikunu tipponta lejn ieħor node u hekk u ibqa 'sejjer hekk sakemm inti hit eventwalment l denb tal-lista marbuta tiegħek, li għandha pointer li ftit ma punt kullimkien minbarra ebda. U għalhekk inti bażikament taf li lista tiegħek għadu hemm sa sakemm pointer ma tkunx daqs nulla minħabba li ladarba tkun ugwali null, inti taf li hemm l-ebda Jittieħed aktar. 

B'tali mod li huwa l-linja li aħna qed se jkollhom it-tfittxija attwali. U jekk il-Pointer do tara dak it-tip ta 'funzjoni vleġġa hemm? Mela jekk punti pointer li n, jekk il pointer fuq n ugwali ugwali n, sabiex ifisser li jekk il pointer li int tiftix għal spezzjonijiet fuq il-aħħar ta 'kull node huwa attwalment daqs il-valur inti qed tfittex, allura inti tixtieq li jirritornaw veru. Allura bażikament, jekk int fuq node li għandu l-valur li inti qed tfittex, inti taf li inti kont qed kapaċi li jfittxu b'suċċess. 

Inkella, inti tixtieq li twaqqaf pointer tiegħek għall-node li jmiss. Dan huwa dak li dik il-linja hawnhekk qed tagħmel. Pointer ugwali pointer li jmiss. Kulħadd jara kif dan ta 'ħidma? 

U essenzjalment int ser biss travers-totalità tal-lista, resetting pointer tiegħek kull darba sakemm inti eventwalment laqat il-aħħar tal-lista. U inti taf li hemm l-ebda aktar lymph li tfittex, u allura inti tista 'tmur lura falza għax inti taf li, oh, ukoll, jekk I kont qed kapaċi li jfittxu permezz tal-intier tal-lista. Jekk f'dan l-eżempju, jekk jien ridt li tfittex l-valur ta '10, u I tibda fil-ras, u I tfittxija kollha 'l isfel, u I eventwalment ltqajna biex dan, li a pointer li l-punti li nulla, Naf li, ħażin, I raden 10 mhux fil din il-lista għaliex I ma setgħetx issib lilha. U jien fl-aħħar tal-lista. U f'liema każ inti taf Jien ser jirritornaw falza. 

Ħalli li soak fl għal ftit. Dan se jkun pjuttost importanti għall pset tiegħek. Il-loġika ta 'dan huwa sempliċi ħafna, forsi sintattikament biss jimplimentawh. You guys tixtieq li tagħmel żgur li tifhem. Kessaħ. 

OK, hekk kif irridu jkunu ddaħħal lymph, id-dritt, fi lista għaliex ftakar liema huma l-dak tal-benefiċċji li jkun hemm lista marbuta versus firxa f'termini tal-ħażna? 

UDJENZA: Huwa dinamiku, għalhekk huwa aktar faċli to-- 

ANDI Peng: Eżattament, dan huwa dinamiku, li ifisser li tista 'tespandi u tiċkien jiddependi fuq l-utent. U għalhekk, f'dan is-sens, ma kellniex bżonn iskart memorja żejda minħabba I jekk I do not know kif ħafna valuri irrid taħżen, ma jagħmilx sens għalija li toħloq firxa għaliex jekk I tixtieq li taħżen 10 valuri u I joħolqu firxa ta '1000, li ħafna ta 'memorja moħlija, allokat. C'est pourquoi irridu li tuża marbuta lista biex ikunu jistgħu dinamikament bidla jew tiċkien daqs tagħna. 

U hekk li jagħmel inserzjoni daqsxejn aktar ikkumplikata. Minħabba li aħna ma tistax saltwarjament aċċess elementi il-mod li aħna se fi skjerament. Jekk irrid li daħħal element fil-seba 'indiċi, I biss tista 'daħħal dan fil-seba 'indiċi. Fuq lista marbuta, ma pjuttost jaħdmu bħala faċilment, u hekk jekk ridna li daħħal l-waħda hawn fil-lista marbuta, viżwalment, huwa faċli ħafna biex tara. Aħna biss trid daħħalha hemm dritt, dritt fil-bidu tal-lista, dritt wara ras. 

Iżda l-mod li bih irridu jassenja mill-ġdid l-pointers huwa daqsxejn convoluted jew, loġikament, jagħmel sens, iżda inti tixtieq li tagħmel ċert li ikollok kompletament fl għaliex l-aħħar ħaġa li trid huwa li terġa 'tassenja pointer l mod li aħna qed tagħmel hawn. Jekk inti dereference l pointer minn ras għal 1, mbagħad kollha f'daqqa bqija tal-lista marbuta tiegħek tintilef minħabba int ma attwalment ħolqot xejn temporanju. Li indikat il-2. Jekk inti jassenja mill-ġdid l-pointer, allura l- bqija tal-lista tiegħek hija totalment mitlufa. Allura inti tixtieq li tkun ħafna, ferm attent hawn l-ewwel tassenja l- pointer minn kwalunkwe inti tixtieq li daħħal fis kulfejn inti trid, u mbagħad inti tista dereference-bqija tal-lista tiegħek. 

Allura dan japplika għall kull fejn inti qed tipprova ddaħħal fil. Jekk inti tixtieq li daħħal fil- ras, jekk inti tixtieq li tingħata risposta hawn, jekk inti tixtieq li daħħal fil l-aħħar, ukoll, l-aħħar I raden inti biss jkollhom l-ebda pointer, iżda inti tixtieq li tagħmel ċert li inti ma jitilfu l-bqija tal-lista tiegħek. Int dejjem tixtieq li tagħmel ċert node ġdid tiegħek hija li tipponta lejn kwalunkwe inti tixtieq li daħħal fis- u allura inti tista 'żżid l-ikkatenar fuq. Kulħadd ċara? 

Dan se jkun waħda mill-kwistjonijiet reali. Waħda mill-kwistjonijiet l-aktar importanti int ser jkollhom fuq pset tiegħek hija li inti qed tmur biex tipprova toħloq lista marbuta u affarijiet daħħal iżda mbagħad biss jitilfu l- bqija tal-lista marbuta tiegħek. U int se tkun simili, I ma nafx għaliex dan qed jiġri? U huwa uġigħ li jmorru permezz u tfittxija kollha tal pointers tiegħek. 

U I garanzija li inti fuq dan pset, kitba u tpinġija dawn in-nodi out se jkun ħafna, utli ħafna. Allura inti tista 'kollox żżomm rekord ta 'fejn pointers kollha tiegħek huma, x'inhu għaddej ħażin, fejn lymph kollha tiegħek huma, dak li għandek bżonn tagħmel biex jaċċessaw jew daħħal jew tħassar jew xi wieħed minnhom. Kulħadd tajba ma 'dak? Kessaħ. 

Mela jekk ridna li tħares lejn il-kodiċi? Oh, I do not know jekk aħna jista 'jara the-- OK, so fil-quċċata kollox huwa huwa funzjoni jismu daħħal fejn irridu li daħħal int n fil-lista marbuta. Aħna qed tmur biex jimxu permezz ta 'dan. Huwa ħafna ta 'kodiċi, lott ta' sintassi ġdida. Aħna ser tkun OK. 

Allura fil-quċċata, kull meta irridu noħolqu xi ħaġa dak li rridu nagħmlu, speċjalment jekk inti jriduhom m'għandhom ikunu maħżuna fuq il-munzell iżda fil-borġ? Immorru lil malloc, right? Allura aħna qed tmur biex joħolqu pointer. Node, pointer, ugwali ġodda malloc-daqs ta 'node għaliex irridu li node li jiġu maħluqa. Aħna rridu l-ammont ta ' memorja li node jieħu li jridu jiġu assenjati għall- ħolqien tal-node ġdid. 

U allura aħna qed tmur biex tikkontrolla biex ara jekk ugwali ġodda ugwali null. Ftakar dak li għidna? Tkun xi tkun inti malloc, dak li għandu inti dejjem tagħmel? Għandek dejjem tikkontrolla biex tara jekk dan huwa null. 

Per eżempju, jekk operattiva tiegħek sistema kienet kompletament sħiħa, jekk kellek memorja mhux aktar mill- kulħadd u inti tipprova malloc, dan se jerġa 'lura null għalik. U hekk jekk inti tipprova tagħmel użu minnha meta kien tipponta lejn null, int mhux se kapaċi għall-aċċess dik l-informazzjoni. U hekk bħala tali, ridna li jagħmlu żgur li kull meta inti qed mallocing, int dejjem verifika biex tara jekk li l-memorja mogħtija lilek huwa null. U jekk mhuwiex, allura nistgħu jimxu fuq mal-bqija tal-kodiċi tagħna. 

Allura aħna qed tmur biex initialize l node ġdid. Aħna qed tmur biex tagħmel n ġdida ugwali n. U allura aħna qed tmur biex tagħmel sett ġdid il-pointer fuq l-ġdida li null għaliex dritt issa aħna ma jridu xejn biex din għall-punt li. Aħna għandna ebda idea fejn li għaddej biex tpoġġi lilek, u mbagħad jekk irridu daħħalha fil-ras, allura nistgħu jassenja mill-ġdid l pointer lill-kap. Ma kulħadd isegwu l-loġika ta 'fejn dik jiġri? 

Kollha għandna qed tagħmel huwa ħolqien ġdid node, li jistabbilixxi l-pointer li nulla, u mbagħad jassenjaw mill-ġdid lill-kap jekk irridu jafu irridu li daħħalha fil-kap. U allura l-ras se punt lejn dak node ġdid. Kulħadd OK ma 'dak? 

Allura huwa proċess f'żewġ stadji. You ħadthom ltqajna biex tassenja ewwel tkun xi tkun qed jinħolqu. Set li pointer għall- referenza, u allura inti tista tip ta 'dereference l-ewwel pointer u punt hija lejn il-node ġdid. Kull fejn inti tixtieq li daħħal dan, li l-loġika se treġix. 

Huwa tip ta 'prodotti simili assenjazzjoni varjabbli temporanji. Ftakar, inti ħadthom ltqajna biex taċċerta ruħek li ma jitilfu l-mogħdija ta 'jekk int iskambji. Inti tixtieq tagħmel ċert li inti għandek varjabbli temporanju dak it-tip ta żżomm kont ta 'fejn dik ħaġa hija maħżuna sabiex inti ma jitlef l-ebda valur fil-kors ta 'prodotti simili messing madwar magħha. 

OK, so kodiċi se jkun hawn. You guys tagħti ħarsa wara taqsima. Se jkun hemm. 

So I raden kif ma Din tvarja jekk ridna li ddaħħal fil-nofs jew fl-aħħar? Ħadd ma jkollu idea ta 'x'inhu l- pseudocode bħala r-referenza loġiku li aħna se tieħu jekk ridna li daħħalha fil-nofs? Mela jekk ridna li daħħalha fil- ras,-nagħmlu hu li toħloq node ġdid. Waqqafna l-pointer ta 'dak node ġdid ma 'kwalunkwe ħaġa ir-ras, u mbagħad aħna waqqafna l-kap għall-node ġdid, id-dritt? Jekk ridna li daħħalha fil-nofs tal-lista, dak li għandna nagħmlu? 

UDJENZA: Ikun għadu jkun proċess simili ta 'prodotti simili assenjazzjoni pointer u imbagħad assenjazzjoni li pointer, imma rridu naraw li jillokalizza hemmhekk. 

ANDI Peng: Eżattament, so eżattament l-istess proċess ħlief int ikollhom biex jillokalizza fejn eżattament inti tixtieq li pointer ġdida li jmorru fi, hekk jekk irrid li ddaħħal fil f'nofs marbuta list-- OK, ejja ngħidu li l-lista marbuta tagħna. Jekk irridu li daħħal dan id-dritt hawn, aħna qed tmur biex jinħoloq node ġdid. Aħna qed tmur biex malloc. Aħna qed tmur biex jinħoloq node ġdid. Aħna qed tmur biex jassenja l- pointer ta 'dan node hawn. 

Iżda l-problema li hija differenti minn fejn ir-ras hija hija li aħna kien jaf eżattament fejn ir-ras hija. Kien id-dritt fl-ewwel, id-dritt? Iżda hawnhekk konna ltqajna biex iżommu kont ta 'fejn aħna qed ddaħħal dan fis. Jekk aħna qed tiddaħħal tagħna node hawn, konna ltqajna biex tiżgura li l- ta 'qabel sabiex dan node huwa dak li reassigns l pointer. Mela allura inti għandek tip ta ' iżżomm kont ta 'żewġ affarijiet. Jekk inti żżomm kont ta 'fejn dan node bħalissa ddaħħal fis. Inti ukoll għandek biex iżommu kont ta 'fejn l node preċedenti li qed tfittex fi kien ukoll hemm. Kulħadd tajba ma 'dak? KOLLOX SEW. 

Kif dwar ddaħħal fit-tarf? Jekk jien ridt li jżidu here-- jekk jien ridt li żżid node ġdid sa l-aħħar ta 'lista, kif jista I tmur dwar kif isir dan? UDJENZA: Allura bħalissa, il- aħħar wieħed indikat null. ANDI Peng: Yeah. Eżattament, għalhekk dan wieħed bħalissa huwa indikat taf, u so I raden, f'dan is-sens, huwa faċli ħafna li żżid mal-aħħar ta 'lista. Kulma għandek tagħmel huwa stabbilit dan daqs null u mbagħad boom. Hemm dritt, faċli ħafna. Sempliċi ħafna. 

Simili ħafna għall- ras, imma loġikament inti jixtiequ jagħmlu ċert li l-passi tieħu lejn tagħmel xi wieħed minn dan, int wara flimkien. Huwa faċli ħafna li, fin-nofs tal-kodiċi tiegħek, nikseb maqbuda fuq, oh, I ħadthom ltqajna tant pointers. I do not know fejn xejn hija li tipponta lejn. I lanqas biss jafu liema node jien fuq. X'qed jiġri? 

Jirrilassaw, jikkalma, tieħu nifs fil-fond. Tfassal l-lista marbuta tiegħek. Jekk inti tgħidli, naf fejn eżattament I-ħtieġa li daħħal dan in u naf eżattament kif assenjati mill-ġdid tiegħi pointers, ħafna, ħafna aktar faċli biex stampa out-- ħafna, ħafna aktar faċli biex ma jintilfu fl-bugs tal-kodiċi tiegħek. Kulħadd OK ma 'dak? KOLLOX SEW. 

So I raden kunċett li aħna ma verament tkellem dwar qabel issa, u I raden inti probabilment mhux se jiltaqgħu yet-- ħafna huwa tip ta 'concept-- avvanzat hija li għandna attwalment ikollhom data istruttura imsejħa lista marbuta doppjament. Allura kif inti guys tista 'tara, kollha għandna qed tagħmel qed joħloq ta 'valur attwali, extra pointer fuq kull wieħed lymph tagħna li jindika wkoll l-node preċedenti. Allura mhux biss għandna tagħna lymph punt għal dak li jmiss. Huma wkoll il-punt għall-ewwel waħda. Jien ser tinjora dawn iż-żewġ dritt issa. 

Mela allura inti għandek katina li tista 'timxi żewġ modi, u allura huwa daqsxejn aktar faċli li loġikament ssegwi tul. Bħal hawn, minflok iżżomm rekord ta ', oh, I għandek tkun taf li dan node huwa il-wieħed li I għandhom jassenja mill-ġdid, I tista 'biss tmur hawn u biss iġbed il-preċedenti. Imbagħad I jafu eżattament fejn jiġifieri, u allura inti ma jkollhom travers il- intier tal-lista marbuta. Huwa daqsxejn aktar faċli. 

Iżda bħala tali, inti għandek doppjament l-ammont ta 'pointers, dak l-doppju tal-ammont tal-memorja. Huwa ħafna pointers li jżommu rekord ta '. Huwa daqsxejn aktar kumplessi, imma hija daqsxejn aktar faċli għall-utent jiddependi fuq dak li qed tipprova tlesti. 

Allura dan it-tip ta 'data istruttura totalment teżisti, u l-istruttura għall huwa ħafna, ħafna sempliċi ħlief kollu int wara hi, minflok sempliċiment pointer li jmiss, inti jkollok ukoll pointer biex preċedenti. Dik hija d-differenza kienet. Kulħadd tajba ma 'dak? Kessaħ. 

Kull dritt, hekk issa jien biex verament jonfqu probabbilment bħal 15 sa 20 minuta jew il-massa tal-bqija tal-ħin fit-taqsima jitkellem dwar it-tabelli hash. Kemm inti guys qrajt spec pset5? Dritt kollox, tajjeb. Dik hija ogħla mill-50% li normalment. Orrajt. 

Allura kif inti guys se tara, int l-isfida fil pset5 huwa li jiġu implimentati dizzjunarju fejn inti tagħbija fuq 140,000 kliem li aħna nagħtuk u kontroll jespliċitaw dan fid-dawl tal-test. Aħna ser jagħtuk każwali biċċiet tal-letteratura. Aħna ser jagħtuk Il Odyssey. Aħna ser jagħtuk Il Iliad. Aħna ser jagħtuk Poteri Austin. 

U l-isfida tiegħek se jkun li jespliċitaw check kull kelma waħda fl- ta 'dawk dizzjunarji essenzjalment ma jespliċitaw tagħna. U hekk hemm ftit partijiet ta jinħoloq dan pset, ewwel inti tixtieq li tkun tista 'attwalment tagħbija il-kliem kollha fis tiegħek dizzjunarju, u allura inti tixtieq li tkun tista ' jespliċitaw check kollha kemm huma. U hekk bħala tali, int ser jeħtieġu struttura data li tista 'tagħmel dan malajr u b'mod effiċjenti u dinamiku. 

So I jissoponi l-eħfef mod biex isir dan, inti probabbilment toħloq firxa, id-dritt? L-eħfef mod ta 'ħażna huwa inti jistgħu joħolqu firxa ta '140,000 kliem u biss tpoġġihom kollha hemm u imbagħad travers lilhom mill tfittxija binarja jew minn selezzjonijiet jew not-- sorry li l-issortjar. Tista sort lilhom u mbagħad travers minnhom billi tfittxija binarju jew tfittxija eżatt lineari u biss finali l-kliem, iżda li jieħu ammont kbir ta 'memorja, u mhuwiex effiċjenti ħafna. 

U hekk aħna qed tmur biex tibda jitkellem dwar modi ta 'teħid running time tagħna aktar effiċjenti. U l-għan tagħna huwa li tikseb ħin kostanti fejn huwa kważi simili arrays, fejn ikollok aċċess istantanja. Jekk jien ridt li tfittex għal xejn, Irrid li tkun tista 'biss, boom, isibuha eżattament, u iġbed it out. U hekk struttura li fiha aħna ser tkun isir viċin ħafna li jkun kapaċi jaċċessa kostanti time, din Grail qaddis fl-ipprogrammar ta 'kostanti ħin tissejjaħ tabella hash. U hekk David imsemmi qabel il- [Inaudible] ftit fil lecture, imma aħna qed tmur biex verament adsa fil-fond din il-ġimgħa fuq biċċa li fir-rigward kif tabella hash xogħlijiet. 

Allura l-mod li hash xogħlijiet mejda, per eżempju, jekk jien ridt li jaħżen mazz ta 'kliem, a mazz ta 'kliem fil-lingwa Ingliża, I tista 'tpoġġi teoretikament banana, tuffieħ, kiwi, mango, par, u cantaloupe kollha fuq biss firxa. Huma kollha tista 'toqgħod tajjeb fi u jiġu ssib. Hija d jkun it-tip ta 'uġigħ li tfittxija permezz ta 'u aċċess, iżda l-mod aktar faċli ta 'kif isir dan huwa li nistgħu noħolqu attwalment struttura imsejħa tabella hash fejn aħna hash. We run kollha ta 'ċwievet tagħna permezz funzjoni hash, ekwazzjoni, li jixgħel lilhom kollha fis xi tip ta 'valur li allura aħna jista 'jaħżen fuq essenzjalment firxa ta 'lista marbuta. 

U hekk hawn, jekk ridna biex jaħżnu kliem Ingliż, nistgħu potenzjalment biss, jien ma jafu, dawwar l-ewwel ittri għal xi tip ta 'numru. U għalhekk, per eżempju, jekk jien ridt A sabiex ikunu sinonimi ma 'apple-- jew bl-indiċi ta '0, u B sabiex ikunu sinonimi ma '1, li jista 'jkollna 26 iskrizzjonijiet li tista 'biss jaħżen kollha tal-ittri tal- alfabett li aħna ser tibda bil. U allura jista 'jkollna tuffieħ fil-indiċi 0. Jista 'jkollna banana fil-indiċi tal 1, cantaloupe fil-indiċi ta '2, u hekk u ibqa 'sejjer hekk. U għalhekk jekk jien ridt li tfittex hash tiegħi mejda u l-aċċess tat-tuffieħ, Naf tuffieħ jibda bil A, u naf eżattament li għandu jkun u l-hash tabella li tinsab fil-indiċi 0 għaliex tal-funzjoni assenjat preċedentement. 

So I do not know, aħna programm utent fejn inti ser tingħata l-inkarigu arbitrarily-- mhux arbitrarju, ma tipprova thoughtfully think ta 'ekwazzjonijiet tajba biex ikunu jistgħu jinfirxu kollha ta 'valuri tiegħek b'mod li faċilment tista 'aċċess dan aktar tard ma bħall-ekwazzjoni li inti, lilek innifsek, jafu. Allura fis-sens jekk jien ridt li jmorru lil mango, I know, oh, li jibda bil m. Għandu jkun fil-indiċi tat-12. I ma jkollhom tfittxija permezz xejn. I know exactly-- I jistgħu biss jmorru għall l-indiċi tat-12 u iġbed dan out. 

Kulħadd ċara dwar kif funzjoni tabella hash tal jaħdem? Huwa tip ta 'ftit firxa aktar kumplessi. Li kollox huwa. KOLLOX SEW. 

So I raden we run fis din il-kwistjoni ta 'liema jiġri jekk għandek affarijiet multipli li jagħtuk l-istess indiċi? Allura ngħid funzjoni tagħna, kollox ma kien jieħu dik l-ewwel ittra u dawwar li fi rispettiv 0 permezz 25 indiċi. C'est totalment multa jekk inti biss għandek wieħed kull wieħed. Iżda t-tieni tibda li jkollhom aktar, int ser ikollhom dak li sejjaħ 'ħabta. 

Mela jekk jien nipprova daħħal midfuna ġo hash tabella li diġà għandu banana fuqha, x'inhu jiġri meta inti tipprova biex jiddaħħal li? Affarijiet ħżiena minħabba banana diġà jeżisti fi ħdan l-indiċi li inti tixtieq li jaħżen fil. Berry tip ta 'huwa simili, ah, x'għandi nagħmel? I do not know fejn imorru. Kif nista issolvi din? 

U hekk inti guys tip se ta tara nagħmlu dan ħaġa delikata fejn nistgħu tip ta 'fatt joħolqu lista marbuta arrays tagħna. U għalhekk l-eħfef mod biex jaħsbu dwar dan, kollha tabella hash hija firxa ta 'listi marbuta. U għalhekk, f'dan is-sens, għandek dan firxa sabiħa ta 'pointers, u mbagħad kull pointer fil dan il-valur, f'dak l-indiċi, jistgħu iwasslu għall-affarijiet oħra. U hekk ikollok dawn kollha separata ktajjen ġejjin off ta 'matriċi semikonduttur wieħed big. 

U hekk hawn, jekk I riedu li daħħal berry, Naf, OK, jien ser input permezz funzjoni hash tiegħi. Jien ser jispiċċaw ma 'l-indiċi ta' 1, u mbagħad jien ser ikunu jistgħu jkollhom biss subsett iżgħar ta 'din ġgant dizzjunarju 140,000 kelma. U allura nista 'tfittex biss permezz 26/01 ta 'dak. 

U hekk allura I tista 'biss daħħal berry jew qabel jew wara banana f'dan il-każ? Wara, id-dritt? U hekk int tmur jridu daħħal dan node wara banana, u għalhekk inti qed tmur biex tiddaħħal fil-denb ta 'dik il-lista marbuta. Jien se jmorru lura għal dan slide preċedenti, sabiex inti guys tista 'tara kif funzjoni hash xogħlijiet. 

Allura funzjoni hash hija din l-ekwazzjoni li int taħdem tip ta 'input tiegħek permezz biex jiksbu dak kollu indiċi inti tixtieq li tassenja din lejn. U għalhekk, f'dan l-eżempju, kollha ridna tagħmel kien jieħu l-ewwel ittra, dawran dan in indiċi, allura aħna jista 'jaħżen li fil-funzjoni hash tagħna. Kollha għandna qed tagħmel hawnhekk hija li aħna qed konverżjoni l-ewwel ittra. Allura keykey [0] huwa biss l-ewwel ittra ta 'kwalunkwe string qed ikollna, aħna qed tgħaddi fil. Aħna qed konverżjoni li biex fuq, u aħna qed jitnaqqas mill uppercase A, sabiex dak kollu li qed tagħmel qed tagħti us numru li bihom nistgħu hash valuri tagħna fuq. 

U allura aħna qed tmur biex ritorn DAQS modulus hash. Be ħafna, ferm attent għaliex, teoretikament, hawn valur hash tiegħek jista 'jkun infinita. Hija tista 'biss tmur fuq u fuq u fuq. Jista 'jkun hemm xi verament, verament valur kbir, iżda minħabba tabella hash tiegħek li inti stajt maħluqa biss għandha 26 indiċijiet, inti tixtieq li tagħmel ċert tiegħek modulusing sabiex inti ma run-- huwa l-istess ħaġa bħala queue-- tiegħek sabiex inti ma run off l qiegħ tal-funzjoni hash tiegħek. 

Inti tixtieq li wrap lura madwar bl-istess mod fl [inaudible] meta kellek bħal ħafna, ittra kbir ħafna, inti ma riedx li biex biss run off-aħħar. L-istess ħaġa hawn, inti tixtieq li tagħmel ċert ma tmurx off-aħħar mill tgeżwir madwar l-quċċata tat-tabella. Allura dan huwa biss ħafna funzjoni hash sempliċi. Dak kollu li ma kien jieħu l-ewwel ittra ta 'kwalunkwe input tagħna kien u dawwar dan in indiċi li nistgħu jitqiegħed fis-mejda hash tagħna. 

Yeah, u għalhekk kif għidt qabel, il-mod li aħna isolvu ħabtiet fil hash tagħna tabelli huma jkollhom, dak li nsejħu, ikkatenar. Mela jekk inti tipprova li daħħal multipli kliem li jibdew bl-istess ħaġa, int se jkollhom valur hash wieħed. Avokado u tuffieħ, jekk inti stajt run permezz funzjoni hash tagħna, huma ser jagħtuk l- istess numru, l-għadd ta '0. U għalhekk l-mod kif aħna issolvi din hija li nistgħu ngħidu tip ta 'jorbtuhom flimkien permezz listi marbuta. 

U hekk f'dan is-sens, inti guys tista 'tara tip ta 'kif data strutturi li aħna kont qed preċedentement ikun ingħata bħal żbib marbut lista tip ta jistgħu jiltaqgħu f'waħda. U allura inti tista 'toħloq ħafna strutturi tad-dejta aktar effiċjenti li jistgħu jieħdu ammonti akbar ta ' data, li dinamikament resize jiddependi fuq il-bżonnijiet tiegħek. Kulħadd ċara? Kulħadd tip ta 'kriterji ċari fuq dak li jiġri hawn? 

Jekk jien ridt li insert-- x'hemm frott li tibda bi, I do not know, B, minbarra berry, banana. 

UDJENZA: tut. 

ANDI Peng: tut, tut. Fejn ma tut mur hawn? Well, aħna fil-fatt ma jkunux magħżula dan s'issa, iżda teoretikament jekk ridna li jkollhom din f'ordni alfabetiku, fejn għandhom tut imorru? 

UDJENZA: [inaudible] 

ANDI Peng: Eżattament, wara hawn, id-dritt? Iżda peress li huwa diffiċli ħafna li reorder-- I raden huwa sa inti guys. You guys tista totalment jimplimentaw xi trid. Il-mod aktar effiċjenti kif isir dan forsi Ikun biex issolvi marbuta tiegħek lista fl-ordni alfabetiku, u hekk meta int ddaħħal affarijiet, inti tixtieq biex tkun żgur li daħħal fl-ordni alfabetiku b'tali mod li allura meta int jippruvaw tiftix għalihom, inti ma għandekx travers kollox. Inti taf eżattament fejn huwa, u huwa aktar faċli. 

Imma jekk inti tip ta 'għandek affarijiet b'intervall saltwarjament, int xorta se jkollhom travers anyways. U hekk jekk jien ridt li biss daħħal blackberry hawn u jien ridt li tfittxija għal dan, I know, oh, tut għandu jibda bl-indiċi ta '1, so I taf istantanjament biss tfittxija fuq 1. U allura nista tip ta ' travers il-lista marbuta sakemm nasal biex tut, u then-- yeah? 

UDJENZA: Jekk inti qed tipprova create-- I raden bħal din hija hash sempliċi ħafna funzjoni. U jekk ridna li tagħmel saffi multipli ta 'dak simili, OK, irridu biex tkun separata fi bħall l-ittri alfabetiċi u mbagħad għal darb'oħra li bħal sett ieħor ta 'ittri alfabetiċi fi ħdan dak, aħna tqegħid bħal hash mejda fit-tabella hash, jew bħal funzjoni fi ħdan funzjoni? Jew hija that-- 

ANDI Peng: Allura hash tiegħek function-- tabella hash tiegħek jista 'jkun kbir kemm inti tixtieq li. Allura f'dan is-sens, ħsibt kien faċli ħafna, ħafna sempliċi biex nagħmel bbażata biss tip fuq l-ittri ta 'l-ewwel kelma. U hekk hemm biss 26 għażliet. I tista 'biss tikseb 26 għażliet minn 0-25 għaliex dawn jistgħu biss tibda minn A sa Z. Imma Jekk int riedu li jżid, forsi, aktar kumplessità jew il-ħin aktar mgħaġġel run biex tiegħek tabella hash, inti assolutament jistgħu jagħmlu kull tip ta 'affarijiet. Inti tista 'tagħmel tiegħek ekwazzjoni li jagħtik distribuzzjoni aktar fil tiegħek kliem, allura meta inti tfittex, li għaddej biex jkun aktar mgħaġġel. 

Huwa totalment sa inti guys kif inti tixtieq li jimplimentaw dik. Jaħsbu li bħala biss bramel. Jekk jien ridt li jkollhom 26 bramel, jien ser biex issolvi l-affarijiet f'dawn is bramel. Imma jien ser ikollhom mazz ta 'għalf f'kull barmil, hekk jekk inti tixtieq li tagħmel dan aktar mgħaġġla u aktar effiċjenti, let me jkollhom mitt bramel. 

Imma mbagħad għandek biex insemmu mod biex issolvi l-affarijiet sabiex ikunu fil-barmil xierqa għandhom ikunu fil. Imma mbagħad meta inti fil-fatt trid tħares lejn dak barmil, huwa ħafna aktar malajr għaliex hemm Jittieħed inqas f'kull barmil. U għalhekk, yeah, li fil-fatt l-trick għalik guys fil pset5 hija li inti ser tkun isfida li jinħolqu biss tkun xi tkun l-aktar effiċjenti funzjoni inti tista 'taħseb li jkun kapaċi jaħżen u jiċċekkjaw dawn il-valuri. 

Totalment sa inti guys madankollu inti tixtieq li tagħmel dan, iżda li l-punt verament tajba. Li t-tip ta 'loġika inti tixtieq li tibda taħseb dwar hija, ukoll, għaliex ma nista 'tagħmel aktar bramel. U mbagħad I jkollhom tfittxija affarijiet inqas, u mbagħad forsi I għandhom funzjoni hash differenti. 

Yeah, hemm ħafna ta 'modi biex tagħmel dan pset, xi wħud huma aktar malajr minn oħrajn. Jien totalment ser biss tara kif fast kien l-aktar mgħaġġla inti guys se tkun kapaċi tikseb l-funzjonijiet tiegħek biex jaħdmu. OK, kulħadd fuq tajba Katinar u hash tabelli? Huwa fil-fatt simili sempliċi ħafna kunċett jekk inti taħseb dwarha. Kull ma huwa huwa tissepara x'ikun inputs tiegħek huma fis bramel, għażla tagħhom, u mbagħad tfittex l- jelenka li hemm assoċjati magħhom. 

Kessaħ. Kull dritt, issa għandna tip differenti ta 'struttura data li sejjaħ siġra. Ejja jmorru fuq u jitkellmu dwar tipprova li huma distintament differenti, iżda fl-istess kategorija. Essenzjalment, kollha siġra hija minflok li jorganizzaw data fil-mod lineari li t-tabella hash does-- inti jafu, huwa ltqajna top u qiegħ u allura inti tip ta 'rabta off ta it-- a siġra għandha top li inti sejħa l-għeruq, u allura weraq kollu madwaru. 

U għalhekk kull ma għandek hawn huwa biss il-node quċċata li l-punti li lymph oħra, li l-punti għal aktar lymph, u hekk u ibqa 'sejjer hekk. U għalhekk inti biss għandek fergħat qsim. Huwa biss mod differenti ta 'organizzazzjoni data, u għaliex aħna sejħa hija siġra, inti guys just-- huwa biss immudellat out tfittex bħal siġra. C'est pourquoi nagħmlu sejħa hija siġar. 

Tabella hash qisu tabella. A siġra biss qisu siġra. Kull ma huwa hija separata mod kif jiġi organizzat lymph jiddependi fuq liema bżonnijiet tiegħek. 

Allura inti għandek għerq u imbagħad inti għandek weraq. Il-mod li nistgħu partikolarment taħseb dwarha hija siġra binarju, siġra binarju huwa biss tip speċifiku ta 'siġra fejn kull node punti biss li, fil max, żewġ punti strateġiċi oħrajn. U hekk hawn ikollok distinti simetrija fil siġra tiegħek li jagħmilha aktar faċli biex it-tip ta ħarsa lejn dak valuri inti għaliex imbagħad inti għandhom dejjem xellug jew dritt. Hemm qatt simili terz xellug mill ix-xellug jew ir-raba minn fuq ix-xellug. Huwa biss għandek xellug u dritt u inti tista 'tfittex waħda minn dawn iż-żewġ. U hekk għaliex dan ikun utli? Il-mod li dan huwa utli jekk inti qed tfittex li tfittex valuri, id-dritt? Pjuttost milli timplimenta binarja tfittxija fil-firxa żball, jekk int riedu li jkunu jistgħu jdaħħlu lymph u jieħdu bogħod lymph fil-se u wkoll tippreserva l-tfittxija kapaċitajiet ta 'tiftix binarja. Allura b'dan il-mod, aħna qed tip ta ' tricking-- tiftakar meta aħna qal listi marbuta ma tistax tfittxija binarja? Aħna tip ta 'ħolqien ta' struttura data li tricks dan in-ħidma. 

U l-listi hekk minħabba marbuta huma lineari, huma biss ħolqa waħda wara l-oħra. Nistgħu tip ta 'jkollhom tip differenti ta 'pointers F'dak il-punt fin-nodi differenti li tista 'tgħinna mal-tfittxija. U hekk hawn, jekk jien ridt li jkollhom siġra tfittxija binarju, Naf li nofs tiegħi jekk 55. Jien biss ser toħloq li kif nofs tiegħi, bħala għerq tiegħi, u mbagħad jien ser ikollhom Valuri spin off ta 'dan. 

Allura hawnhekk, jekk jien ser tfittex għal il-valur ta '66, I jistgħu jibdew fi 55. Huwa 66 akbar minn 55? Iva huwa, so I know I għandha tasal tfittxija ni l pointer dritt ta 'din is-siġra. Mmur 77. OK, huwa inqas minn 66 jew akbar minn 77? Huwa inqas minn, sabiex inti tkun taf, oh, li għandu jkun l-node xellug. 

U hekk hawn aħna qed tip ta 'preservazzjoni l-affarijiet kbar dwar arrays, hekk bħall resizing dinamiku ta 'oġġetti, li kapaċi li daħħal u ħassar fil-se, mingħajr ma joqogħdu jinkwetaw dwar l-fiss ammont ta 'spazju. Aħna xorta tippreserva kollha dawk l-affarijiet mill-isbaħ filwaqt li jkunu kapaċi biex jippreservaw il-wkoll log u tfittxija ħin ta 'tfittxija binarja li konna biss qabel kapaċi tikseb frażi. 

Istruttura tad-data jibred, tip ta ' kumplessi biex jiġu implimentati, l-node. Kif tistgħu taraw, dan kollu huwa l-Struct tal-node huwa li inti għandek xellug u pointer dritt. Li kollox huwa. Allura aktar milli biss jkollhom x jew qabel. Għandek xellug jew dritt, u mbagħad inti tista 'tip ta' jorbtuhom flimkien madankollu hekk jagħżlu. 

OK, aħna qed attwalment għaddejjin ħu ftit minuti. Allura aħna qed tmur biex jmorru lura hawn. Kif għidt qabel, I tip ta 'spjega il-loġika wara kif aħna kieku tfittxija permezz ta 'dan. Aħna qed tmur biex tipprova pseudocoding dan out biex tara jekk nistgħu tip ta 'japplika l- istess loġika ta 'tfittxija binarja għal tip differenti ta 'struttura data. Jekk inti guys tixtieq li tieħu bħal koppja minuti biex biss jaħsbu dwar dan. KOLLOX SEW. Kull dritt, jien ser attwalment biss jagħtuk the-- no, aħna ser jitkellmu dwar il-pseudocode ewwel. Allura ħadd ma tridx li tagħti stab lejn dak l-ewwel ħaġa li trid tagħmel meta int bdew tiftix huwa? Jekk aħna qed infittxu il-valur ta '66, x'hemm l-ewwel ħaġa li rridu nagħmlu jekk irridu li Binarju tfittxija din is-siġra? 

UDJENZA: Inti trid tfittex dritt u jfittxu xellug u ara [inaudible] Numru akbar. 

ANDI Peng: Yeah, eżattament. Allura inti qed tmur biex tħares lejn għerq tiegħek. Hemm lottijiet ta 'modi kif inti tista' sejħa dan, in-nies node ġenitur tiegħek jgħidu. Jien inħobb ngħid għerq għaliex li huwa simili l-għerq tal-siġra. Inti qed tmur biex tħares lejn node għerq tiegħek, u int ser tara huwa 66 akbar jew inqas minn 55. U jekk huwa akbar minn, ukoll, huwa akbar minn, fejn nistgħu tixtieq tfittex? Fejn irridu li tfittex issa, id-dritt? Aħna rridu li tfittex l- nofs tal-lemin ta 'din is-siġra. 

Allura aħna għandna, konvenjenti, a pointer li l-punti lejn il-lemin. U hekk allura nistgħu stabbilit għeruq ġdida tagħna li jkun 77. Nistgħu biss jmorru kull fejn l-pointer hija li tipponta. Ukoll, oh, hawn aħna qed jibdew għal 77, u nistgħu biss tagħmel dan recursively għal darb'oħra u darb'oħra. B'dan il-mod, inti xorta ta jkollha funzjoni. Għandek mod ta 'tiftix li inti tista 'sempliċement jirrepeti aktar u aktar u aktar, jiddependi fuq fejn inti tixtieq li tfittex sakemm inti eventwalment jasal sal-valur li qed tfittex. Jagħmel sens? 

Li jien ser nuruk l-attwali kodiċi, u huwa ħafna ta 'kodiċi. Ebda ħtieġa biex skerz. Aħna ser nitkellmu permezz tiegħu. 

Attwalment, l-ebda. Dan kien biss pseudocode. OK, li kien biss il-pseudocode, li huwa kumpless daqsxejn, imma hija totalment multa. Kulħadd wara flimkien hawn? Jekk l-għerq huwa null, ritorn falza minħabba li l-mezzi inti ma jkollhomx xejn hemmhekk. 

Jekk għeruq n huwa l-valur, hekk jekk jiġri li jkun il-wieħed li qed tfittex lejn, allura int ser jirritorna veru għaliex inti taf li inti sabuha. Iżda jekk il-valur ikun anqas minn għerq ta 'n, int tmur biex tfittex ix-xellug tfal jew il-weraq tax-xellug, tkun xi tkun tixtieq li hija sejħa. U jekk il-valur ikun ikbar minn għeruq, int ser tfittex il-siġra dritt, allura biss imexxu l-funzjoni permezz ta 'riċerka ġdid. 

U jekk għeruq huwa null, li din ifisser li inti ħadthom laħqu t-tmiem? Dan ifisser li inti għandek l-ebda aktar aktar weraq li persuna tfittex, imbagħad inti taf, oh, I raden mhuwiex fil hawn għax wara stajt ħares permezz il-ħaġa sħiħa u mhuwiex hawnhekk, hija biss jista 'ma jkunx hawn. 

Does li jagħmel sens għal kulħadd? Allura huwa simili tfittxija binarja preservazzjoni il-kapaċitajiet tal-listi marbuta. Kessaħ, u għalhekk it-tieni tip ta 'struttura data inti guys tista 'tipprova timplimenta fuq pset tiegħek, inti biss għandek tagħżel metodu wieħed. Imma forsi metodu alternattiv biex il tabella hash hu dak li nsejħu a trie. 

Kollha ta 'trie huwa huwa tip speċifiku ta 'siġra li għandha valuri li jmorru lil valuri oħra. Allura minflok li jkun hemm binarja siġra fis-sens li wieħed biss ħaġa jista 'jiġbed l tnejn, inti jista' jkollhom punt ħaġa waħda li ħafna, ħafna affarijiet. Inti essenzjalment għandek arrays ġewwa ta 'li inti taħżen pointers dan il-punt arrays oħra. 

Allura l-node ta 'kif aħna se jiddefinixxu trie huwa irridu li jkollhom Boolean, kelma c, id-dritt? Allura l-node huwa Boolean bħal vera jew falza, ewwel nett fil-kap ta ' li array, dan huwa kelma? It-tieni nett, inti tixtieq li jkollok pointers għal dak kollu l-bqija ta 'dawn huma. A kumpless bit, ftit astratt, iżda I se jispjegaw dak li tfisser kull. 

Allura hawnhekk, fil-quċċata, jekk inti jkollhom firxa iddikjarat diġà, a node fejn għandek Boolean ħlas joħroġ valur maħżun fuq quddiem li jgħidlek dan huwa kelma? Huwa dan mhijiex kelma? U allura inti għandek il- bqija ta 'firxa tiegħek li attwalment ħażniet kollha tal- possibbiltajiet ta 'dak li jista' jkun. Għalhekk, per eżempju, bħall fil-quċċata għandek l-ewwel ħaġa li tgħid vera jew falza, iva jew le, dan huwa kelma. 

U allura inti għandek 0 permezz 26 tal l-ittri li inti jista 'jaħżen. Jekk jien ridt li tfittex hawn għall BAT, I tmur fil-quċċata u I tfittex B. nsib B fil tiegħi firxa, u so I know, OK, huwa B kelma? B mhijiex kelma, hekk b'hekk I għandu jżomm tiftix. I jmorru minn B, u nistenna li l- pointer li B punti lejn u nara firxa oħra ta 'informazzjoni, l-istess struttura li kellna qabel. 

U here-- oh, il-li jmiss ittra [inaudible] hija A. Allura aħna nħarsu f'dak array. Insibu-tmien valur, u allura aħna tfittex biex tara, oh, ħej, huwa li kelma, huwa B-A kelma? Mhuwiex kelma. Imxejna ltqajna biex ikompli jfittex. 

U hekk allura aħna nħarsu lejn fejn l pointer ta A punti, u hija tirreferi għall-mod ieħor fil li għandna aktar valur maħżun. U eventwalment, irridu jiksbu l B-A-T, li hija kelma. U għalhekk l-ħin li jmiss inti tfittex, int ser li jkollhom dik il-verifika ta ', iva, din il-funzjoni Boolean huwa veru. U għalhekk fis-sens aħna qed tip li jkun hemm siġra ma arrays. 

Hekk allura inti tista 'tip ta' tfittxija isfel. Pjuttost milli hashing funzjoni u assenja tal-valuri minn lista marbuta, inti tista 'sempliċement timplimenta trie li t-tfittxijiet downwords. Tassew, tassew ikkumplikata Jittieħed. Mhux faċli li wieħed jaħseb dwar għaliex jien bħal bżieq tant strutturi ta 'dejta out fi inti, imma ma kulħadd tip ta ' jifhmu kif il-loġika ta 'dan xogħlijiet? 

OK, berred. Allura B-A-T, u mbagħad int ser tfittex. Il-ħin li jmiss int ser biex tara, oh, ħej, huwa veru, b'hekk Naf li dan għandu jkun kelma. 

L-istess ħaġa għall zoo. Allura hawnhekk-ħaġa dritt issa, jekk aħna riedu tiftix għal zoo, id-dritt issa, bħalissa żoo ma jkunx kelma dizzjunarju tagħna għaliex, kif inti guys tista 'tara, l ewwel post li għandna Boolean ritorn vera hija fl-aħħar ta 'zoom. Għandna Z-O-O-M. 

U hekk hawn, aħna ma attwalment jkollhom il-kelma, żu, fil dizzjunarju tagħna għaliex din il-kaxxa verifika ma tiġix iċċekkjata. Allura l-kompjuter ma jafu li zoo hija kelma minħabba l-mod li konna maħżuna dan, biss zoom hawn fil-fatt għandu valur Boolean li kien mdawwar veru. Mela jekk irridu li daħħal il- kelma, żu, fis dizzjunarju tagħna, kif kieku aħna tmur dwar kif isir dan? What do għandna nagħmlu biex tiżgura tagħna kompjuter jaf li Z-O-O hija kelma u mhux l-ewwel kelma hija Z-O-O-M? 

UDJENZA: [inaudible] 

ANDI Peng: Eżattament, aħna tixtieq li tagħmel ċert li dan hawn, dak il-valur Boolean huwa ċċekkjati off li huwa veru. Z-O-O, allura aħna qed tmur biex jivverifikaw li, hekk nafu eżattament, ħej, żu hija kelma. Jien ser jgħidlek il- kompjuter li huwa kelma hekk li meta l-kontrolli tal-kompjuter, huwa jaf li żoo hija kelma. 

Minħabba ftakar din id-data kollha istrutturi, huwa faċli ħafna għalina ngħid, oh, BAT huwa kelma. Zoo l kelma. Zoom l kelma. Imma meta int bini tagħha, il-kompjuter m'għandha l-ebda idea. 

Allura inti għandek tgħid eżattament fuq liema punt huwa dan kelma? Fuq liema punt huwa mhux kelma? U fuq liema punt do I bżonn ta 'tiftix affarijiet, u fuq liema punt do I bżonn li jmorru jmiss? Kulħadd ċara ta 'dak? Kessaħ. 

U hekk imbagħad jiġi l problema ta 'kif kieku aħna tmur dwar ddaħħal xi ħaġa li fil-fatt ma hemm? Mela ejja biss jgħidu li rridu li daħħal il kelma, banju, fis trie tagħna. Kif inti guys tista 'tara bħal bħalissa kollha għandna issa huwa B-A-T, u din l-istruttura l-ġdida tad-data kien hemm pinta li indikat null għaliex aħna nassumu li, oh, hemm ebda kliem wara B-A-T, għaliex għandna bżonn li jżommu li affarijiet wara li T. 

Iżda l-problema tqum jekk nagħmlu inti jridu li jkollhom kelma li tiġi wara l-T. Jekk ikollok banju, int tmur jridu dritt H. U għalhekk l-mod kif aħna qed tmur biex tagħmel dan huwa aħna qed tmur biex jinħoloq node separat. Aħna ma jalloka x'ikun ammont ta 'memorja għal dan array ġdid, u aħna qed tmur biex jassenja mill-ġdid pointers. 

Aħna qed tmur biex jassenja l- H, L-ewwelnett, dan null, aħna qed tmur biex jeħles. Aħna qed tmur biex ikollhom l isfel punt H. Jekk naraw H, irridu biex tmur x'imkien ieħor. 

Fil hawn, nistgħu mbagħad tiċċekkja off iva. Jekk aħna hit H wara l-T, oh, allura nafu li din hija kelma. Il Boolean se jirritornaw veru. Kulħadd ċara dwar kif dan ġara? KOLLOX SEW. 

Allura essenzjalment, kollha ta ' dawn l-istrutturi tad-data li konna marret fuq illum, stajt marret fuqhom tassew, tassew malajr u mhux għal ħafna dettall, u li OK. Ladarba inti tibda messing magħha, inti ser tkun iżżomm kont ta 'fejn l-pointers huma, x'inhu għaddej fil tiegħek strutturi tad-dejta, eċċetera. Dawn ser ikunu utli ħafna, u huwa sa inti guys biex insemmu totalment kif inti tixtieq li jimplimentaw affarijiet. 

U għalhekk pset4, tal 5-- oh, dak li hu ħażin. Pset5 huwa misspellings. Kif għidt qabel, int ser, ladarba għal darb'oħra, download kodiċi sors minna. Hemm għaddej li jkun tlieta prinċipali affarijiet li inti ser tkun tniżżil. Int ser ikollok tniżżel dizzjunarji, kers, u testi. 

Dawk kollha affarijiet huma huma jew dizzjunarji 'kliem li irridu li inti tiċċekkja jew test ta 'informazzjoni li irridu li inti jespliċitaw check. U għalhekk il-dizzjunarji aħna nagħtuk ser li jtik kliem attwali li rridu int taħżen b'xi b'mod li l- aktar effiċjenti minn firxa. U allura l--testi huma ser ikun dak li aħna qed inti titlob li jespliċitaw jivverifika sabiex ikun żgur kollha tal-kliem hemm kliem reali. 

U għalhekk it-tliet blokki ta ' programmi li aħna ser jagħtuk huma msejħa dictionary.c, dictionary.h, u speller.c. U għalhekk kull dictionary.c ma huwa dak li qed tintalab biex jimplimentaw. Tagħbijiet kliem. Hija jespliċitaw kontrolli minnhom, u hija tiżgura li kollox huwa mdaħħal sew. 

diction.h huwa biss fajl librerija li jiddikjara dawk il-funzjonijiet kollha. U speller.c, aħna qed tmur biex jagħtuk. Inti ma għandekx bżonn li timmodifika xi ħaġa. Speller.c kollu ma huwa jieħu li, tagħbijiet li għalihom, kontrolli l-veloċità ta 'dan, testijiet l-punt ta 'referenza ta' prodotti simili kif malajr int tista 'tagħmel affarijiet. 

Huwa speller. Just ma mess miegħu, imma kun żgur li tifhem dak li qed jagħmel. Aħna nużaw funzjoni msejħa getrusage li testijiet l-prestazzjoni ta 'jespliċitaw tiegħek kontrollur. Kull ma huwa bażikament jittestjaw il- żmien ta 'kollox fil-dizzjunarju tiegħek, sabiex tagħmel żgur li int tifhem dan. Ikunu attenti biex ma mess miegħu jew affarijiet inkella mhux se jaħdmu tajjeb. 

U l-biċċa l-kbira ta 'din l-isfida hija għal inti guys biex verament timmodifika dictionary.c. Aħna ser jagħtuk 140,000 kliem fil-dizzjunarju. Aħna ser jagħtuk test fajl li għandu dawn il-kliem, u rridu li inti tkun kapaċi li jorganizzaw minnhom fis-tabella hash jew trie għaliex meta aħna nitolbuk li jespliċitaw check-- jimmaġina jekk int jespliċitaw verifika bħal Odyssey Homer. Huwa bħal dan enormi, test enormi. 

Immaġina jekk kull wieħed kelma kellek tfittex permezz ta 'firxa ta' 140,000 valuri. Li jieħu dejjem għall-magna tiegħek jiddekorri. Dan hu għaliex irridu li jorganizzaw tagħna data fl-istrutturi tad-data aktar effiċjenti bħal mejda hash jew trie. U mbagħad inti guys tista tip ta 'meta inti tfittex aċċess affarijiet aktar faċilment u aktar malajr. 

U sabiex ikunu attenti biex isolvu kolliżjonijiet. Inti qed tmur biex tikseb mazz ta 'kliem ta' dik tibda bil A. Inti qed tmur biex tikseb kliem mazz li tibda bil B. Up lilek guys kif inti tixtieq li issolvihom. Forsi hemm aktar funzjoni hash effiċjenti minn sempliċiment l-ewwel ittra ta ' xi ħaġa, u b'tali mod li sa inti guys li tip ta 'jagħmel kulma trid. 

Forsi inti trid iżżid l-ittri kollha flimkien. Forsi inti tixtieq li tixtieq tagħmel affarijiet stramb li jagħtu kont in-numru ta 'ittri, ikun x'ikun. Sa inti guys kif inti trid tagħmel. Jekk inti tixtieq li tagħmel tabella hash, jekk inti tixtieq li jippruvaw trie, totalment sa inti. I se twissi inti qabel iż-żmien li l- trie huwa tipikament ftit aktar diffiċli biss għaliex hemm ħafna aktar pointers li jżommu rekord ta '. Iżda totalment sa inti guys. Huwa ferm aktar effiċjenti f'ħafna każijiet. Inti trid verament tkun kapaċi li żżomm rekord ta 'kollha ta' pointers tiegħek. Bħall jagħmlu l-istess ħaġa li I kienet tagħmel hawn. Meta inti qed tipprova li daħħal valuri fis-tabella hash jew tħassar, kun żgur li int verament iżżomm rekord ta 'fejn kollox huwa minħabba huwa verament faċli biex jekk jien jippruvaw daħħal bħall-kelma, andy. Ejja ngħidu biss li l- reali kelma,-kelma, andy, fi lista ġgant ta 'kliem. 

Jekk I biss jiġri li jassenja mill-ġdid a ħażin pointer, oops, hemm tmur-totalità tal il-bqija tal-lista marbuta tiegħi. Issa l-unika kelma I għandhom hija andy, u issa kollha tal-kliem oħra fil- dizzjunarju ġew mitlufa. U għalhekk inti tixtieq li tagħmel żgur li int iżżomm kont ta 'kollha ta' pointers tiegħek jew inkella int ser tikseb problemi kbar fil-kodiċi tiegħek. Iġbed affarijiet out b'attenzjoni pass pass. Dan jagħmilha ħafna aktar faċli biex jaħsbu. 

U fl-aħħar, inti tixtieq li tkun tista ' test tal-prestazzjoni tiegħek tal-programm tiegħek fuq il-bord big. Jekk inti guys tieħu tħares lejn CS50 dritt issa, għandna dak li sejjaħ il-bord big. Hija l-folja tal-punteġġ mill-aktar jespliċitaw ħinijiet verifika madwar kollha ta 'CS50 dritt issa, naħseb li l-top simili 10 drabi I think tmienja minnhom huma persunal. Aħna verament irridu li inti guys li tħabbat us. 

Lkoll kienu qegħdin jippruvaw jimplimentaw il-kodiċi mgħaġġla possibbli. Irridu li inti guys jippruvaw li jikkontestaw magħna u jimplimentaw aktar malajr milli lkoll tista '. U għalhekk dan huwa verament l-ewwel darba li aħna qed inti titlob guys li jagħmlu pset li inti tista 'verament tagħmel kwalunkwe metodu trid. 

Jien dejjem ngħid, dan huwa aktar simili għal soluzzjoni tal-ħajja reali, id-dritt? I say, ħej, I ħtieġa li inti tagħmel dan. Tibni programm li ma dan għalija. Tagħmel dan madankollu trid. I biss jafu li nixtieq li malajr. C'est sfida tiegħek għal din il-ġimgħa. You guys, aħna qed tmur li jtik kompitu. Aħna ser jagħtuk sfida. U allura huwa sa inti guys li kompletament biss insemmu x'inhu l-mgħaġġel u aktar mod effiċjenti biex jimplimentaw dan. Yeah? 

UDJENZA: Are we jitħallew jekk riedu għar-riċerka modi aktar mgħaġġel tagħmel tabelli hash online, nistgħu nagħmlu li u jikkwotaw kodiċi xi ħadd ieħor? ANDI Peng: Yeah, totalment multa. Mela jekk inti guys taqra l- spec, hemm linja fil-spec li tgħid inti guys huma totalment liberi li hash riċerka funzjonijiet fuq liema huma wħud tal-funzjonijiet hash aktar malajr jiddekorri affarijiet permezz bħala Sakemm inti jiċċitaw dan il-kodiċi. Għalhekk xi nies ikollhom diġà dehret modi mgħaġġel li jagħmlu kontrolluri jespliċitaw, ta fast modi ta 'ħażna ta' informazzjoni. Totalment sa inti guys jekk inti jridux biss jieħdu dik, id-dritt? Kun żgur li int jiċċita. L-isfida hawn verament li aħna qed jippruvaw biex tittestja qed tagħmel ċert li inti taf tiegħek mod madwar pointers. Kemm inti implimentazzjoni il-funzjoni proprja hash u toħroġ bi bħal l-matematika biex tagħmel dan, inti guys tista 'riċerka x'ikun Metodi online inti guys tixtieq. Yeah? 

UDJENZA: Nistgħu jiċċitaw biss billi tuża l-[inaudible]? 

ANDI Peng: Yeah. Inti tista 'sempliċement, fil-kumment tiegħek, inti jista 'jikkwota simili, oh, meħuda minn yada, yada, yada, il-funzjoni hash. Kull min ikollu xi mistoqsijiet? Aħna fil-fatt breezed permezz sezzjoni illum. I se jkun sa hawn biex twieġeb mistoqsijiet kif ukoll. 

Ukoll, kif għidt, l-uffiċċju sigħat tonight u ta 'għada. Il spec din il-ġimgħa huwa attwalment super faċli u super qasir biex jinqara. Nissuġġerixxi tieħu ħarsa, just tinqara minn ġol-intier ta 'dan. 

U Zamyla attwalment mixjiet inti permezz ta 'kull waħda mill-funzjonijiet għandek bżonn biex jimplimentaw, u dan huwa ħafna, ċar ħafna kif jagħmlu kollox. Just tagħmel żgur li int iżżomm rekord ta 'pointers. Din hija pset sfida. 

Mhuwiex sfida għaliex bħal, oh, il-kunċetti huma daqstant aktar diffiċli, jew ikollok biex jitgħallmu tant sintassi ġdida it-triq li għamilt għall-aħħar pset. Dan pset huwa diffiċli minħabba hemm daqstant pointers, u allura huwa ħafna, faċli ħafna għal darba għandek bug fil-kodiċi tiegħek ma tkunx kapaċi biex isibu fejn dan bug hu. 

U hekk kompluta u l-fidi utter fik guys li tkun tista 'tħabbat tagħna [inaudible] spellings. I attwalment ma jkunux ebda minjiera miktub s'issa, iżda jien wasal biex jikteb mini. Għalhekk, filwaqt li int bil-miktub tiegħek, jien ser jkun miktub minjiera. Jien ser jippruvaw jagħmlu minjiera aktar mgħaġġel minn tiegħek. Ser naraw li għandu l-wieħed mgħaġġla. 

U yeah, I se tara kollha ta ' inti guys hawn nhar it-Tlieta. I se tmexxi tip bħal workshop pset. Kollha tas-sezzjonijiet dan ġimgħa huma workshops pset, sabiex inti guys jkollhom lottijiet ta 'opportunitajiet għall-għajnuna, ħinijiet tal-uffiċċju bħal dejjem, u I really bil-ħerqa li qari kollha tal-kodiċi guys tiegħek ". Għandi kwizzijiet up here jekk inti guys tixtieq li ġejjin tikseb dawk. Dak kollox.