JASON Hirschhorn: Merħba kulħadd lit-Taqsima tal Seven. Aħna fil-ġimgħa seba tal-kors. U dan il-ħamis li jmiss huwa Halloween so I am dressed up bħal qara. I ma setax jitgħawġu u mqiegħda fuq żraben tiegħi, b'tali mod li għalhekk jien biss liebes kalzetti. Jien ukoll ma liebes xejn taħt dan, so I ma tistax teħodha off jekk huwa jfixkluh lilek. I ruhna bil-quddiem għal dak. Inti ma għandekx bżonn li wieħed jimmaġina x'inhu għaddej. I am liebes boxers. Allura dan kollu tajba. 

I jkollhom storja itwal dwar għaliex jien dressed bħala qara, imma jien ser ħlief li, għal aktar tard f'din it-taqsima minħabba I do jridu li tibda. Għandna ħafna affarijiet eċċitanti li jmorru fuq din il-ġimgħa. Ħafna minnhom huma relatati direttament ma 'din ġimgħa problema sett, misspellings. Aħna ser jkunu għaddejjin fuq marbut listi u tabelli hash għas-sezzjoni kollha. Nressaq din il-lista up kull ġimgħa, lista ta ' riżorsi għalik biex jgħinek ma ' l-materjal fuq dan il-kors. Jekk b'telf jew jekk tfittex xi aktar informazzjoni, check out waħda ta ' dawn ir-riżorsi. 

Għal darb'oħra, pset6 huwa misspellings, din il-ġimgħa pset. U tinkoraġġixxi wkoll li inti, u I ninkoraġġukom, tuża xi oħra riżorsi speċifikament għal dan pset. B'mod partikolari, it-tliet stajt elenkati fuq l-iskrin - GDB, li aħna kont qed familjari ma u kienu jużaw għal filwaqt li issa, huwa se jkun ferm utli din il-ġimgħa. So I iqiegħed dak up here. Imma meta inti qed jaħdmu ma 'C, għandek dejjem tuża GDB li debug programmi tiegħek. Din il-ġimgħa valgrind wkoll. Ħadd ma jaf dak valgrind ma? 

UDJENZA: Huwa jagħmel verifiki għat-tnixxija memorja? 

JASON Hirschhorn: Valgrind kontrolli għal tnixxijiet memorja. Mela jekk inti xi ħaġa malloc fil tiegħek programm, int tistaqsi għall-memorja. Fl-aħħar tal-programm tiegħek, inti għandek li tikteb b'xejn fuq kollox inti ħadthom malloced biex jagħtu l-memorja lura. Jekk inti ma jiktbu jinħelsu fi tmiem u programm tiegħek tasal għal konklużjoni, kollox se awtomatikament jinħelsu. U għall-programmi żgħar, huwa mhux li big deal. Imma jekk int bil-miktub ta 'running itwal programm li ma nieqaf, bilfors, fi ftit minuti jew ftit sekondi, mbagħad memorja tnixxijiet tista 'ssir jittrattaw enormi. 

Allura għal pset6, l-aspettattiva hija li ser ikollok tnixxijiet memorja żero ma program tiegħek. Sabiex jikkontrolla għal tnixxijiet memorja, valgrind run u dan ser jagħtuk xi sbieħ output kiri taf jekk jew ma kollox kien b'xejn. Aħna ser prattika magħha aktar tard illum, nisperaw. 

Fl-aħħarnett, il-kmand diff. Inti użati xi ħaġa simili għal dan fil pset5 bl-għodda Peek. Permess li inti tfittex ġewwa. Inti wkoll użat diff, wisq, per il-problema sett spec. Iżda fil permessi li inti iqabblu żewġ fajls. Inti tista 'tqabbel l-fajl Bitmap u headers informazzjoni ta 'soluzzjoni staff u soluzzjoni tiegħek fil pset5 jekk inti għażlet li tagħmel użu minnha. Diff se jippermetti li inti tagħmel dan, ukoll. Tista 'tqabbel l-risposta korretta għall- problema din il-ġimgħa stabbiliti biex it-tweġiba tiegħek u ara jekk linji up jew tara fejn l-iżbalji huma. 

Għalhekk dawn huma tliet għodod tajba li għandek tuża għal din il-ġimgħa, u definittivament check program tiegħek ma 'dawn it-tliet għodod qabel ma ddawwar hija pulzieri Għal darb'oħra, kif semmejt kull ġimgħa, jekk għandek xi feedback għalija - kemm pożittiv u kostruttiv - tħossok liberu li ras għall-website fil-qiegħ ta 'din slide u input hemmhekk. I verament japprezzaw kwalunkwe u kollha feedback. U jekk inti tagħti me affarijiet speċifiċi li I tista 'tagħmel biex itejbu jew li jien tagħmel sew li inti tixtieq lili biex tkompli, I jieħdu dik għall-qalb u verament jippruvaw diffiċli biex jisimgħu għal feedback tiegħek. I ma tistax wegħda jien ser tagħmel kollox, għalkemm, simili liebes qara kostum kull ġimgħa. 

Allura aħna ser jonfqu l-massa ta ' taqsima, kif semmejt, jitkellem dwar listi marbuta u tabelli hash, li se jkunu applikabbli direttament għall- problema jistabbilixxu din il-ġimgħa. Listi marbuta aħna ser jmorru fuq relattivament malajr għaliex aħna ħadthom jintefqu ftit ġust ta 'żmien għaddej fuqha fit-taqsima. U hekk aħna ser nikseb straight fil- kodifikazzjoni problemi għal listi marbuta. U mbagħad fl-aħħar aħna ser nitkellmu dwar hash tabelli u kif japplikaw għal dan problema ġimgħa stabbiliti. 

Inti stajt tidher dan il-kodiċi qabel. Din hija Struct, u qed jiddefinixxi xi ħaġa ġdida imsejħa node. U ġewwa node hemm huwa integer dritt hawn u hemm pointer li node ieħor. Rajna dan qabel. Dan ġie ġejjin up għall- ftit ġimgħat issa. Din tikkombina pointers, li aħna kont qed li jaħdmu ma ', u structs, li jippermettu ahna jgħaqqdu żewġ differenti affarijiet in tip ta 'dejta wieħed. 

Hemm ħafna għaddej fuq l-iskrin. Iżda kollha ta 'dan għandu jkun relattivament familjari miegħek. Fuq l-ewwel linja, aħna tiddikjara node ġdid. U mbagħad ġewwa dak node ġdid, I sett n-numru sħiħ f'dak node għal wieħed. Li naraw fuq il-linja li jmiss qed nagħmel printf kmand, imma stajt grayed out il-kmand printf għaliex il-verament parti importanti hija din il-linja hawnhekk - new_node.n. X'tagħmel l-dot jfisser? 

UDJENZA: Mur fil-node u tevalwa l-valur n għaliha. 

JASON Hirschhorn: C'est eżattament id-dritt. Dot ifisser aċċess għall-parti n ta 'dan node ġdid. Din il-linja li jmiss ma 'dak? Michael. 

UDJENZA: Hija toħloq node ieħor li se jindika l-node ġdid. 

JASON Hirschhorn: Allura dan ma joħolqu node ġdid. Hija toħloq liema? 

UDJENZA: A pointer. 

JASON Hirschhorn: A pointer għal node, kif indikat minn din node * hawnhekk. Allura din toħloq pointer għal node. U li node huwa li tipponta li, Michael? 

UDJENZA: node New? 

JASON Hirschhorn: node Ġdid. U huwa tipponta hemm għaliex konna tatha l-indirizz ta 'node ġdid. U issa f'dan il-linja naraw żewġ modi differenti ta ' jesprimu l-istess ħaġa. U jien ridt li jiġi mfakkar kif dawn żewġ affarijiet huma l-istess. Fl-ewwel linja, aħna dereference il-pointer. Allura aħna mur l-node. Dak hu li dan il stilla jfisser. Rajna li qabel ma pointers. Tmur f'dak node. Li fil-parentesi. U mbagħad ikollhom aċċess permezz ta 'l-operatur dot l-element n ta 'dik node. 

Allura li huwa tieħu s-sintassi rajna dritt hawn u issa jużawha ma 'pointer. Of course, jiġrilha tip ta 'busy jekk int bil-miktub dawk parentesi - li star u li dot. Jiġrilha ftit busy. Allura aħna għandna xi zokkor sintatttiku. U din il-linja dritt hawn - ptr_node-> n. Li ma l-istess ħaġa eżatt. Allura dawn iż-żewġ linji ta 'kodiċi huma ekwivalenti u se tagħmel l-istess ħaġa eżatt. 

Imma jien ridt li jiġi dawk qabel immorru xi ulterjuri sabiex inti tifhem li verament dan il-ħaġa dritt hawn huwa biss zokkor sintattika għall dereferencing il-pointer u mbagħad tmur il-parti n ta 'dak Struct. Xi mistoqsijiet dwar dan slide? OK. 

Allura aħna qed tmur biex jmorru permezz ta 'koppja ta 'operazzjonijiet li inti tista' tagħmel fuq listi marbuta. Lista marbuta, recall, hija serje ta lymph dan il-punt ma 'xulxin. U aħna ġeneralment tibda bil-pointer imsejħa ras, ġeneralment, li l-punti li l-ewwel ħaġa fil-lista. Allura fuq l-ewwel linja hawn, aħna ikollhom L oriġinali tagħna ewwel. Allura li ħaġa inti tista 'taħseb - dan test dritt hawn inti tista 'taħseb kif biss il-pointer konna maħżuna x'imkien li l-punti l-ewwel element. U f'dan il-lista marbuta għandna erba 'nodes. Kull node huwa kaxxa big. Il-kaxxa akbar ġewwa l-big kaxxa hija l-parti numru sħiħ. U allura għandna parti pointer. 

Dawn il-kaxxi ma jkunux tfasslu sabiex iskala għaliex kemm hu kbir huwa integer fl bytes? Kif big issa? Erbgħa. U kemm hu kbir l-pointer? Erbgħa. Allura verament, jekk konna biex tiġbed din l-iskala żewġ kaxxi tkun l-istess daqs. F'dan il-każ, irridu li daħħal xi ħaġa fil-lista marbuta. Allura tista 'tara stabbiliti hawn aħna qed ddaħħal ħamsa Aħna travers permezz tal- lista marbuta, isibu fejn ħamsa tmur, u mbagħad daħħal dan. 

Ejja break li jistabbilixxi u jmorru ftit aktar bil-mod. Jien ser punt li l-bord. Allura aħna għandna node tagħna ħamsa li ħloqna fil mallocs. Għaliex kulħadd laughing? Just kidding. OK. Allura aħna ħadthom malloced ħamsa. Imxejna ħolqot din node x'imkien ieħor. Aħna għandna hija lesta li tmur. Nibdew fuq quddiem tal- lista tagħna ma 'żewġ. U rridu li daħħal b'mod Issortjati. 

Allura jekk naraw tnejn u aħna tixtieq li tqiegħed ħamsa, dak li nagħmlu meta naraw xi ħaġa inqas minn us? What? Aħna rridu li daħħal ħamsa fis dan lista marbuta, iż-żamma magħżula. Naraw numru tnejn. Allura dak li nagħmlu? Marcus? 

UDJENZA: Sejħa tal-pointer l-node li jmiss. 

JASON Hirschhorn: U għaliex do immorru għal dak li jmiss? 

UDJENZA: Għaliex dan huwa l- node li jmiss fil-lista. U aħna biss nafu li post ieħor. 

JASON Hirschhorn: U ħamsa akbar minn tnejn, b'mod partikolari. Għaliex irridu li jżommha Issortjati. Allura ħamsa aktar minn tnejn. Allura aħna jimxu fuq dak li jmiss. U issa aħna jilħqu erbgħa. U x'jiġri meta aħna jilħqu erba? 

Ta 'ħames huwa akbar minn erba'. Allura aħna jibqgħu għaddejjin. U issa aħna qed fuq sitt. U dak li naraw fuq sitt? Iva, Carlos? 

UDJENZA: Six jkun iktar minn ħamsa. 

JASON Hirschhorn: Six huwa iktar minn ħamsa. Allura dak fejn irridu li daħħal ħamsa. Madankollu, wieħed iżomm f'moħħu li jekk irridu jkollhom biss pointer wieħed hawn - dan huwa pointer extra tagħna li l- traversat permezz tal-lista. U aħna qed tipponta lejn sitta. Aħna tilfu rekord ta 'dak jasal quddiem sitta. Mela jekk irridu li daħħal xi ħaġa fis din il-lista iżommha magħżula, aħna probabilment ikollok bżonn kemm pointers? 

UDJENZA: Two. 

JASON HIRSCHORN: Two. Wieħed li jżommu rekord tal-kurrent wieħed u waħda biex iżommu kont ta ' qabilha. Din hija biss lista marbuta weħidhom. Huwa biss tmur f'direzzjoni waħda. Jekk kellna lista marbuta doppjament, fejn kollox kien li tipponta lejn il-ħaġa wara dan u l-ħaġa qabel dan, allura aħna ma bżonn tagħmel dan. Iżda f'dan il-każ aħna ma jridux jitilfu rekord ta 'dak daħlu qabel magħna fil-każ għandna bżonn li daħħal ħamsa x'imkien fin-nofs. Say konna ddaħħal disa. X'jiġri meta aħna ltqajna biex tmienja? 

UDJENZA: Youd għandek tikseb dak il-punt null. Minflok ma jkollhom punt null youd iżidu element u mbagħad ikollhom huwa punt għal disgħa. 

JASON HIRSCHORN: Eżattament. Allura aħna nikseb tmienja. Aħna jilħqu l-aħħar tal-lista għaliex din hija li tipponta lejn null. U issa, minflok li dan il-punt li null aħna għandna hija punt għal node ġdid tagħna. U aħna waqqafna l-pointer fil- node ġdid tagħna għall null. Ħadd ma jkollu xi mistoqsijiet dwar ddaħħal? X'jiġri jekk I ma jimpurtahom dwar li l-lista magħżula? 

UDJENZA: Stick fil- bidu jew fl-aħħar. 

JASON HIRSCHORN: Stick fi il-bidu jew fit-tmiem. Liema wieħed għandu nagħmlu? Bobby? Għaliex l-aħħar? 

UDJENZA: Minħabba l-bidu hija diġà mimlija. 

JASON HIRSCHORN: OK. Il-bidu hija diġà mimlija. Min jixtieq li jargumentaw kontra Bobby. Marcus. 

UDJENZA: Well inti probabilment tixtieq li stick fil-bidu minħabba inkella jekk inti tpoġġi fil- l-aħħar inti d jkollhom travers l-lista sħiħa. 

JASON HIRSCHORN: Eżattament. Allura jekk aħna qed jaħsbu dwar runtime, il- runtime ta 'ddaħħal fl-aħħar Ikun n, id-daqs ta 'dan. X'hemm-runtime O kbira ta ddaħħal fil-bidu? Ta 'żmien kostanti. Mela jekk inti ma jimpurtahom dwar iż-żamma xi ħaġa magħżula, ħafna aħjar għal ftit daħħal fil-bidu ta 'din il-lista. U li jista 'jsir fil-ħin kostanti. 

OK. Operazzjoni li jmiss hu li ssib, li oħrajn - konna ifformulati dan bħala search. Iżda aħna qed tmur biex tħares permezz tal- lista marbuta għal xi oġġett. Inti guys raw kodiċi għall tfittxija qabel fil-lecture. Iżda aħna xorta ta 'biss ma kien ma daħħal, jew għall-inqas ddaħħal xi ħaġa magħżula. Inti tfittex permezz, node jmorru minn node, sakemm issib in-numru li int tfittex. X'jiġri jekk inti tilħaq l-aħħar tal-lista? Say I infittex disa u I jilħqu l-aħħar tal-lista. Dak li nagħmlu? 

UDJENZA: Ritorn falza? 

JASON HIRSCHORN: Ritorn falza. Aħna ma jsibuha. Jekk inti jilħqu t-tmiem tal-lista u inti ma issib in-numru int tfittex, mhuwiex fil hemmhekk. Xi mistoqsijiet dwar issibha? Jekk dan kien lista ssortjat, dak li jkun differenti għal tiftix tagħna? Yeah. 

UDJENZA: Huwa se ssib l-ewwel valur dan huwa akbar minn dik qed tfittex għal u mbagħad jirritornaw falza. 

JASON HIRSCHORN: Eżattament. Mela jekk huwa lista ssortjat, jekk irridu jiksbu xi ħaġa li akbar minn dak aħna qed tfittex għal, aħna ma bżonn li jibqgħu għaddejjin sa l-aħħar tal-lista. Nistgħu f'dak il-punt ritorn foloz għaliex aħna qed mhux se jsibuha. Il-mistoqsija issa, konna tkellimna dwar żamma listi marbuta magħżula, żommhom mhux magħżul. Li għaddej biex tkun xi ħaġa int probabbilment se jkollhom biex jaħsbu dwar meta problema kodifikazzjoni sett ħames jekk inti jagħżlu tabella hash ma separata approċċ ikkatenar, li aħna ser nitkellmu dwar aktar tard. 

Imma huwa worth it li jżomm il-lista Issortjati u mbagħad tkun kapaċi li forsi jkollhom tfittxijiet aktar malajr? Jew hija aħjar biex malajr daħħal xi ħaġa fil runtime kostanti iżda mbagħad jkollhom itwal tiftix? Li l-tradeoff hemm dritt li inti jiksbu li jiddeċiedu liema huwa aktar xieraq għall-problema speċifika tiegħek. U hemm mhux neċessarjament waħda tweġiba assolutament dritt. Iżda huwa ċertament deċiżjoni ikollok li jagħmlu, u probabbilment tajba biex tiddefendi li, ngħidu aħna, kumment jew tnejn għaliex għażilt wieħed fuq l-ieħor. 

Fl-aħħarnett, it-tħassir. Rajna tħassir. Dan huwa simili għall-tiftix. Aħna nħarsu għall-element. Say aħna qed tipprova tneħħi sitta. Allura insibu sitt dritt hawn. Il-ħaġa li għandna biex niżguraw tagħmel huwa li tkun xi tkun hija li tipponta lejn sitt - kif naraw fil-pass żewġ down hawn - tkun xi tkun li tindika li sitt jeħtieġ li skip sitt issa u jiġu mibdula sabiex tkun xi sitt snin hija li tipponta lejn. Aħna ma rridux li qatt orfni il-bqija ta ' lista tagħna billi jinsa li tistabbilixxi li pointer preċedenti. U mbagħad kultant, jiddependi dwar il-programm, dawn ser biss jitħassar dan node kompletament. Kultant tkun taf tixtieq li jirritornaw il-valur li f'dan node. Allura li kif xogħlijiet tħassar. Kwalunkwe mistoqsijiet dwar iħassru? 

UDJENZA: Mela jekk int ser tħassar dan, kieku inti biss użu ħieles minħabba preżumibbilment kien malloced? 

JASON HIRSCHORN: Jekk inti tixtieq li jillibera xi ħaġa li eżattament id-dritt u int malloced dan. Say ridna li jirritornaw dan il-valur. Aħna jista 'jirritorna sitt u mbagħad ħielsa dan node u mingħajr sejħa fuqha. Jew aħna'd probabbilment sejħa ħielsa ewwel u mbagħad jirritornaw sitta. 

OK. Mela ejja jimxu fuq il-prattika kodifikazzjoni. Aħna qed tmur għall-kodiċi tliet funzjonijiet. L-ewwel wieħed huwa msejjaħ insert_node. Hekk ikollok kodiċi li I emailed inti, u jekk inti qed jaraw dan aktar tard inti tista 'aċċess l-kodiċi fl linked.c fuq il-websajt CS50. Iżda fil linked.c, hemm xi kodiċi iskeletru li l-diġà ġew miktuba għalik. U allura hemm funzjonijiet koppja għandek bżonn biex tikteb. 

L-ewwel aħna qed tmur biex jiktbu insert_node. U dak insert_node ma jiġifieri inserzjonijiet integer. U int tagħti n-numru sħiħ fil-lista marbuta. U b'mod partikolari, għandek bżonn li l-lista magħżula mill-iżgħar sa l-akbar. Ukoll, inti ma tridx li daħħal xi duplikati. Finalment, kif tista 'tara insert_node jirritorna bool. Allura int suppost li tikri l-utent isir jaf jekk l-inserzjoni kienx jew le suċċess billi jirritorna vera jew falza. Fit-tmiem ta 'dan il-programm - u għal dan l-istadju inti m'għandekx bżonn għalfejn tinkwieta dwar ħelsien xejn. Allura kollha qed tagħmel qed tieħu integer u ddaħħal fis lista. 

Dan huwa dak li jien inti titlob sabiex tagħmel issa. Għal darb'oħra, fil-linked.c, li inti kollha għandhom, huwa l-kodiċi iskeletru. U inti għandek tara lejn il-qiegħ id-dikjarazzjoni funzjoni kampjun. Madankollu, qabel ma nidħlu kodifikazzjoni li fis-C, I ħafna ninkoraġġukom biex tmur permezz tal-passi aħna kont qed prattikanti kull ġimgħa. Imxejna diġà għaddew minn stampa ta 'dan. Allura għandu jkollok xi għarfien ta 'kif taħdem din. Imma nixtieq ninkoraġġukom biex jiktbu xi pseudocode qabel għadis pulzieri U aħna qed tmur biex jmorru fuq pseudocode bħala grupp. U allura ladarba inti stajt bil-miktub tiegħek pseudocode, u ladarba aħna ħadthom bil-miktub tagħna pseudocode bħala grupp, tista ' jmorru fil-kodifika fil C. 

Bħala kapijiet up, il-funzjoni insert_node huwa probabbilment l-trickiest ta ' it-tliet aħna qed tmur biex jiktbu minħabba I żied xi restrizzjonijiet addizzjonali biex programmazzjoni tiegħek, b'mod partikolari li int mhux ser tiddaħħal kwalunkwe duplikati u li l-lista għandhom jibqgħu Issortjati. Allura dan huwa programm mhux trivjali li għandek bżonn għall-kodiċi. U għaliex ma inti tieħu 5-7 minuti biss biex tikseb jaħdmu fuq il- pseudocode u l-kodiċi. U allura aħna se tibda jmorru bħala grupp. Għal darb'oħra, jekk għandek xi mistoqsijiet biss jgħollu naħa tiegħek u jien ser jidħlu madwar. . 

Aħna wkoll ġeneralment do dawn - jew I ma jgħidu b'mod espliċitu inti jistgħu jaħdmu ma 'nies. Imma ovvjament, I ħafna ninkoraġġukom, jekk għandek mistoqsijiet, li titlob lill- neighbor seduta li jmiss lilek jew saħansitra jaħdmu ma 'xi ħadd inkella jekk trid. Dan ma għandhom ikunu individwu attività siekta. 

Nibdew bl miktub xi pseudocode fuq il-bord. Min jista 'jagħti lili l-ewwel linja ta' pseudocode għal dan il-programm? Għal din il-funzjoni, pjuttost - insert_node. Alden? 

UDJENZA: Allura l-ewwel ħaġa I ma kien joħolqu pointer ġdida lill-node u I initialized li tipponta lejn l-istess ħaġa li lista hija li tipponta lejn. 

JASON HIRSCHORN: OK. Allura int ħolqien ta 'pointer ġdida mal-lista, li ma l-node. 

UDJENZA: Dritt. Yeah. 

JASON HIRSCHORN: OK. U allura dak li rridu nagħmlu? X'hemm wara li? Dak dwar il-node? Aħna ma jkollhom node. Aħna biss għandhom valur. Jekk irridu li daħħal node, liema do we bżonn tagħmel l-ewwel qabel nistgħu saħansitra jaħsbu dwar ddaħħal dan? 

UDJENZA: Oh, sorry. għandna bżonn li malloc spazju għal node. 

JASON HIRSCHORN: Eċċellenti. Ejja nagħmlu - OK. Ma jistgħux jilħqu dik għolja. OK. Aħna qed tmur biex jinżlu, u mbagħad aħna qed jużaw żewġ kolonni. I ma tistax tmur li - OK. Oħloq node ġdid. Tista 'toħloq pointer ieħor għall-lista jew tista 'biss tuża lista kif jeżisti. Inti ma verament bżonn tagħmel dan. 

Allura aħna joħolqu node ġdid. Great. Dak hu li nagħmlu l-ewwel. Xi jmiss? 

UDJENZA: Stenna. Jekk noħolqu node ġdid issa jew għandna nistennew biex tiżgura li M'hemm l-ebda duplikati tal-node fuq il-lista qabel we joħolqu dan? 

JASON HIRSCHORN: Good kwistjoni. Ejja tiddeċiedi li għal aktar tard minħabba li l- maġġoranza tal-ħin aħna ser tkun ħolqien a node ġdid. Allura aħna ser iżommu dan hawn. Iżda li l-mistoqsija tajba. Jekk aħna joħolqu dan u nsibu kopja, liema għandhom nagħmlu qabel jirritornaw? 

UDJENZA: Free dan. 

JASON HIRSCHORN: Yeah. Probabbilment ħielsa it. OK. Dak li nagħmlu wara we joħolqu node ġdid? Annie? 

UDJENZA: Aħna tpoġġi l- numru fil-node? 

JASON HIRSCHORN: Eżattament. Aħna tpoġġi l-għadd - aħna malloc ispazju. Jien ser jitlaq minn dak kollha bħala linja waħda. Imma int dritt. Aħna malloc ispazju, u mbagħad nitfgħu l-għadd pulzieri Nistgħu anke tistabbilixxi l-pointer parti minnha null. Dan huwa eżattament id-dritt. U mbagħad xi ngħidu dwar wara li? Fassalna din l-istampa fuq il-bord. Allura dak li nagħmlu? 

UDJENZA: Immorru permezz tal-lista. 

JASON HIRSCHORN: Mur permezz tal-lista. OK. U dak li aħna jiċċekkja għal f'kull node. Kurt, liema do we check għall f'kull node? 

UDJENZA: Ara jekk il-valur n ta ' li node huwa akbar mill-valur n ta node tagħna. 

JASON HIRSCHORN: OK. Jien ser tagħmel - yeah, OK. Allura huwa n - Jien se ngħid jekk il-valur ikun akbar minn dan node, allura dak li nagħmlu? 

UDJENZA: Well, allura aħna daħħal il-ħaġa dritt qabel dik. 

JASON HIRSCHORN: OK. Mela jekk huwa akbar minn dan, imbagħad irridu daħħal. Imma irridu li daħħalha dritt qabel għaliex aħna wkoll bżonn li tkun iżżomm rekord, imbagħad, ta 'dak li kien qabel. Allura daħħal qabel. Allura aħna probabbilment qbiżt xi ħaġa aktar kmieni. Għandna probabbli jkollha tiġi żamma kont ta 'x'inhu għaddej. Iżda aħna ser terġa 'lura hemmhekk. Allura liema valur ikun anqas minn? Kurt, dak li nagħmlu jekk valur ikun anqas minn? 

UDJENZA: Imbagħad inti biss iżommu għaddejjin sakemm huwa l-aħħar wieħed. 

JASON HIRSCHORN: I bħal dik. Allura jmorru għall-node li jmiss. Sakemm huwa l-aħħar wieħed - aħna qed probabbilment verifika għal dik fit-termini ta 'kundizzjoni. Iżda yeah, node jmiss. U li jkollna baxx wisq, hekk aħna ser jimxu hawn. Iżda jekk - jista kulħadd tara dan? Jekk aħna qed ugwali dak li nagħmlu? Jekk il-valur aħna qed jippruvaw li daħħal huwa ugwali għall-valur din node ta? Yeah? 

UDJENZA: [inaudible]. 

JASON HIRSCHORN: Yeah. Minħabba dan - Marcus huwa dritt. Stajna forsi jsir xi ħaġa differenti. Iżda peress li ħloqna dan, hawnhekk għandna ħielsa u mbagħad jirritornaw. Oh boy. Huwa li aħjar? Kif jgħid li? OK. Libera u imbagħad dak do we ritorn, [inaudible]? OK. Are we xi ħaġa nieqsa? Għalhekk, fejn huma aħna iżżomm rekord tal-node qabel? 

UDJENZA: Naħseb li tmur wara jinħoloq node ġdid. 

JASON HIRSCHORN: OK. Allura fil-bidu aħna ser probabbilment - yeah, nistgħu noħolqu pointer għal ġdida node, bħal pointer node qabel u pointer node kurrenti. Mela ejja daħħal dik hawn. Oħloq kurrenti u preċedenti indikaturi għall-lymph. Imma meta nistgħu jaġġustaw dawk pointers? Fejn nistgħu nagħmlu li fil-kodiċi? Jeff? 

UDJENZA: - kondizzjonijiet ta 'valur? 

JASON HIRSCHORN: Liema wieħed in partikolari? 

UDJENZA: Jien biss konfuż. Jekk valur ikun ikbar minn dan node, ma jfissirx li inti tixtieq li tmur l-node li jmiss? 

JASON Hirschhorn: Mela jekk valur tagħna huwa akbar mill-valur ta 'dan node. 

UDJENZA: Yeah, imbagħad youd tixtieq li jmorru aktar 'l isfel il-linja, id-dritt? 

JASON Hirschhorn: Dritt. Allura aħna ma daħħalha hawnhekk. Jekk valur ikun anqas minn dan node, allura immorru l-node li jmiss - jew allura aħna daħħal qabel. 

UDJENZA: Stenna, li huwa dan node u li valur? 

JASON Hirschhorn: Good kwistjoni. Valur għal kull din id-definizzjoni funzjoni huwa dak li aħna qed jingħataw. Allura valur huwa n-numru aħna qed partikolari. Allura jekk il-valur ikun anqas minn dan node, għandna bżonn żmien biex tiddaħħal. Jekk valur ikun ikbar minn dan node, immorru l-node li jmiss. U lura għall-mistoqsija oriġinali, għalkemm, meta - 

UDJENZA: Jekk valur ikun ikbar minn dan node. 

JASON Hirschhorn: U hekk dak li nagħmlu hawnhekk? Sweet. Dan huwa korrett. Jien biss ser jikteb aġġornament pointers. Iżda iva, ma 'dak attwali inti jaġġornah li punt għal dak li jmiss. Xi ħaġa oħra li aħna qed jitilfu? Hekk jien ser għal dan it-tip kodiċi fis gedit. U filwaqt li jien tagħmel dan, inti jista 'jkollhom ftit aktar minuti biex jaħdmu fuq kodifikazzjoni dan C. 

So I jkollhom input l pseudocode. A quick nota qabel we tibda. Aħna jista 'ma jkunx kapaċi jintegraw kompletament jintemm dan fl- tlieta minn dawn il-funzjonijiet. Hemm soluzzjonijiet korretta għalihom li jien se email lilek guys wara it-taqsima, u se jiġu stazzjonati fuq CS50.net. So I ma ninkoraġġukom biex jmorru tħares lejn is-sezzjonijiet. I ninkoraġġukom biex tipprova dawn fuq tiegħek stess, u mbagħad jużaw l-prattika problemi biex jiċċekkjaw it-tweġibiet tiegħek. Dawn kollha ġew imfassla biex mill-qrib jirrigwardaw u jaderixxu għal dak għandek tagħmel fuq is-sett problema. So I do jinkoraġġixxu li inti prattika dan fuq tiegħek u mbagħad jużaw il-kodiċi li jiċċekkjaw it-tweġibiet tiegħek. Minħabba I do jridu jimxu fuq hash tabelli f'xi punt fit-taqsima. Allura aħna ma jistgħu jiksbu permezz tagħha kollha. Iżda aħna ser nagħmlu kemm nistgħu issa. 

OK. Let us tibda. ASAM, kif nistgħu joħolqu node ġdid? 

UDJENZA: Inti ma Istituzzjonjijiet *. 

JASON Hirschhorn: Allura aħna jkollu dik up here. Oh, sorry. You kienu jgħidu Struct *. 

UDJENZA: U mbagħad [? tip?] node jew c node. 

JASON Hirschhorn: OK. Jien ser sejħa hija new_node hekk nistgħu nibqgħu konsistenti. 

UDJENZA: U inti tixtieq li twaqqaf dik ras, l-ewwel node. 

JASON Hirschhorn: OK. Hekk issa dan li tipponta lejn - sabiex dan ma ħoloqx node ġdid għadu. Dan huwa biss li tipponta lejn l- ewwel node fil-lista. Kif nista jinħoloq node ġdid? I Jekk bżonn l-ispazju li jinħoloq node ġdid. Malloc. U kemm hu kbir? 

UDJENZA: Id-daqs tal-Struct. 

JASON Hirschhorn: Il- daqs tal-Struct. U x'inhu l-Istituzzjonjijiet imsejħa? 

UDJENZA: Node? 

JASON Hirschhorn: Node. Allura malloc (sizeof (node)); jagħtina l-ispazju. U hija din il-linja - Ħaġa waħda hija żbaljata fuq din il-linja. Huwa new_node pointer għal Istituzzjonjijiet? Li l-isem ġeneriku. X'inhu - node, eżattament. Huwa node *. U dak li nagħmlu dritt wara aħna malloc xi ħaġa, Asan? X'inhu l-ewwel ħaġa li nagħmlu? X'jiġri jekk din ma taħdimx? 

UDJENZA: Oh, tivverifika jekk jinnota l-node? 

JASON Hirschhorn: Eżattament. Mela jekk inti new_node ugwali ugwali null, dak li nagħmlu? Dan jirritorna bool, din il-funzjoni. Eżattament. Jidher tajjeb. Xejn biex iżżid hemmhekk? Aħna ser iżżid l-affarijiet fl-aħħar. Iżda li s'issa jidher tajjeb. Oħloq pointers kurrenti u preċedenti. Michael, kif nista 'nagħmlu dan? 

UDJENZA: Int tkun tagħmel node *. Youd għandek tagħmel wieħed ma għall new_node iżda għall- lymph diġà għandna. 

JASON Hirschhorn: OK. Allura l-node attwali aħna qed fuq. I ser sejħa li Curr. Kull dritt. Imxejna ddeċidew irridu li jżomm tnejn għaliex għandna bżonn inkunu nafu x'hemm quddiemha. What do huma jiksbu initialized li? 

UDJENZA: il-valur tagħhom fil-lista tagħna. 

JASON Hirschhorn: Allura x'inhi l- ewwel ħaġa fuq lista tagħna? Jew kif nafu fejn il- bidu tal-lista tagħna hu? 

UDJENZA: Hux għadda fil-funzjoni? 

JASON Hirschhorn: Dritt. Hija kienet għaddiet dritt hawn. Mela jekk huwa għadda fil-funzjoni, il- bidu tal-lista, dak li għandna sett attwali ugwali għal? 

UDJENZA: Lista. 

JASON Hirschhorn: Lista. Dan huwa eżattament id-dritt. Issa l-indirizz ta ' il-bidu tal-lista tagħna. U xi ngħidu dwar preċedenti? 

UDJENZA: Lista nieqes wieħed? 

JASON Hirschhorn: Hemm xejn quddiemha. Allura x'nistgħu nagħmlu biex turi xejn? 

UDJENZA: Null. 

JASON Hirschhorn: Yeah. Li tinstema 'bħala idea tajba. Perfect. Grazzi. Mur permezz tal-lista. Constantine, kemm ser nieħdu jgħaddu mill-lista? 

UDJENZA: Sa Nilħqu null. 

JASON Hirschhorn: OK. Hekk jekk, filwaqt li, għall-loop. X'inhuma nagħmlu? 

UDJENZA: Forsi għal loop? 

JASON Hirschhorn: Ejja nagħmlu għal loop. OK. 

UDJENZA: U aħna ngħidu - sakemm il-pointer attwali mhuwiex ugwali għal null. 

JASON Hirschhorn: Mela jekk nafu l- kundizzjoni, kif nistgħu jiktbu loop bbażata off din il-kundizzjoni. Liema tip ta 'linja għandu nużaw? 

UDJENZA: Filwaqt. 

JASON Hirschhorn: Yeah. Li jagħmel sens aktar ibbażati off ta 'dak li qal. Jekk aħna biss tixtieq li tmur fis aħna li kieku biss jafu li ħaġa, ikun jagħmel sens li jagħmlu filwaqt li loop. Filwaqt attwali ma null ma jkunux ugwali, jekk il-valur ikun anqas minn dan node. Akshar, agħti lili din il-linja. 

UDJENZA: Jekk kurrent> 'n n inqas mill-valur. Jew ireġġa 'dik. Jaqilbu li bracket. 

JASON Hirschhorn: Jiddispjacini. 

UDJENZA: Ibdel il-bracket. 

JASON Hirschhorn: Mela jekk huwa akbar mill-valur. Għaliex dak konfuża mal- tikkummenta fuq, jien ser tagħmel dan. Imma iva. Jekk valur tagħna hija inqas minn din node, dak li nagħmlu? Oh. I jkollhom dan id-dritt hawn. Daħħal qabel. OK. Kif nistgħu nagħmlu dan? 

UDJENZA: Ikun għadu me? 

JASON Hirschhorn: Yeah. 

UDJENZA: You - new_node-> jmiss. 

JASON Hirschhorn: Allura x'hemm li ser ugwali? 

UDJENZA: Huwa ser kurrent ugwali. 

JASON Hirschhorn: Eżattament. U hekk l-oħra - x'iktar do we bżonn li taġġorna? 

UDJENZA: Iċċekkja jekk fil-passat ugwali null. 

JASON Hirschhorn: Jekk prev - hekk jekk prev ugwali null. 

UDJENZA: Dan ifisser li għaddej biex isiru l-kap. 

JASON Hirschhorn: Dan ifisser huwa sar-ras. Mela allura dak li nagħmlu? 

UDJENZA: We do head ugwali new_node. 

JASON Hirschhorn: Head ugwali new_node. U għaliex ras hawn, ma lista? 

UDJENZA: Minħabba ras huwa globali varjabbli, li huwa l-post tal-bidu. 

JASON Hirschhorn: Sweet. OK. U - 

UDJENZA: Imbagħad inti inkella prev-> jmiss ugwali new_node. U allura inti tirritorna veru. 

JASON Hirschhorn: Fejn do aħna waqqafna aħħar new_node? 

UDJENZA: Nixtieq - I stabbilit li fil-bidu. 

JASON Hirschhorn: Allura dak line? 

UDJENZA: Wara l-dikjarazzjoni jekk verifika jekk huwa magħruf. 

JASON Hirschhorn: Dritt hawn? 

UDJENZA: I d tagħmel new_node-> n ugwali valur. 

JASON Hirschhorn: Ħsejjes tajba. Probabbilment jagħmel sens - aħna ma bżonn tkun taf liema lista li aħna qed dwar għaliex aħna qed jittratta biss flimkien ma 'lista waħda. Allura dikjarazzjoni funzjoni aħjar għall- dan huwa biss biex teħles minn dan kollox u biss daħħal valur fis-kap. Aħna lanqas biss bżonn tkun taf dak lista aħna qed pulzieri Imma jien se jżommha għal issa u imbagħad bidla fuq l-aġġornament l-pjastri u kodiċi. Allura li jidher tajjeb għal issa. Jekk il-valur - li tista 'tagħmel din il-linja? Jekk - dak li nagħmlu hawnhekk, Noah. 

UDJENZA: Jekk valur ikun ikbar minn Curr-> n - 

JASON Hirschhorn: Kif do immorru l-node li jmiss? 

UDJENZA: Curr-> n hija daqs new_node. 

JASON Hirschhorn: Allura n hija liema parti tal-Istituzzjonjijiet? N-numru sħiħ. U new_node huwa pointer għal node. Allura liema parti tal Curr għandu aħna aġġornament? Jekk le n, allura x'inhu l-parti l-oħra? Noah, x'inhu l-parti l-oħra. 

UDJENZA: Oh, li jmiss. 

JASON Hirschhorn: Sussegwentement, eżattament. Eżattament. Li jmiss hija waħda tajba. U x'iktar do we bżonn biex taġġorna, Noah? 

UDJENZA: Il-pointers. 

JASON Hirschhorn: So aħna kurrenti aġġornata. 

UDJENZA: Prev-> jmiss. 

JASON Hirschhorn: Yeah. OK, aħna ser nieqaf. Li jistgħu jgħinu us out here? Manu, dak li għandu nagħmlu? 

UDJENZA: You ħadthom ltqajna biex jistabbilixxu huwa ugwali għall-Curr> jmiss. Iżda tagħmel dan qabel il-linja ta 'qabel. 

JASON Hirschhorn: OK. Xi ħaġa oħra? Akshar. 

UDJENZA: Ma naħsibx li int maħsuba biex ibiddlu-Curr> jmiss. I think int maħsuba biex tagħmel ugwali Curr Curr-> jmiss biex tmur fil-node li jmiss. 

JASON Hirschhorn: So sorry, fejn? Fuq liema linja? Din il-linja? 

UDJENZA: Yeah. Kun Curr ugwali Curr-> jmiss. 

JASON Hirschhorn: Allura dak korretta għaliex attwali hija pointer li node. U irridu li punt għall-ieħor node ta 'dak li jkollna bħalissa indikat. Curr nnifisha għandha jmiss. Imma jekk konna biex taġġorna curr.next, aħna ikun aġġornament n-nota attwali innifsu, ma fejn dan pointer kienet tipponta. What about din il-linja, għalkemm. Avi? 

UDJENZA: Prev-> jmiss ugwali Curr. 

JASON Hirschhorn: Għalhekk għal darb'oħra, jekk prev hija pointer għal node, prev-> jmiss huwa l- pointer attwali fil-node. Allura dan ikun aġġornament a pointer fil-node biex Curr. Aħna ma rridux li taġġorna a pointer fil-node. Aħna rridu li taġġorna qabel. Allura kif nistgħu nagħmlu? 

UDJENZA: Ikun biss tkun prev. 

JASON Hirschhorn: Dritt. Prev huwa pointer għal node. Issa aħna qed jinbidlu għal pointer ġdid għal node. OK Let us jinżel 'l isfel. Finalment, din l-aħħar kundizzjoni. Jeff, dak li nagħmlu hawnhekk? 

UDJENZA: Jekk valur huwa daqs Curr-> n. 

JASON Hirschhorn: Jiddispjacini. Oh my goodness. What? Valur == Curr-> n. Dak li nagħmlu? 

UDJENZA: Youd ħielsa new_node tagħna, u mbagħad youd ritorn foloz. 

JASON Hirschhorn: Dan huwa dak aħna bil-miktub s'issa. Ħadd ma jkollhom xejn li żżid qabel nagħmlu? OK. Ejja nippruvaw dan. Kontroll jista 'jilħaq it-tmiem ta 'funzjoni mhux null. Avi, x'inhu għaddej? 

UDJENZA: Inti suppost li tpoġġi ritorn vera barra mill-linja waqt? 

JASON Hirschhorn: I do not know. Tixtieq lili li? 

UDJENZA: Never mind. Nru. 

JASON Hirschhorn: Akshar? 

UDJENZA: Naħseb li inti maħsuba biex jitqiegħdu falza 'ritorn fi tmiem tal-linja waqt. 

JASON Hirschhorn: Għalhekk, fejn tridu li tmur? 

UDJENZA: Bħall barra l-linja waqt. Mela jekk inti ħruġ tal-loop filwaqt li mezzi li inti stajt laħqu l-aħħar u ġara xejn. 

JASON Hirschhorn: OK. Allura dak li nagħmlu fil hawn? 

UDJENZA: You ritorn foloz hemm ukoll. 

JASON Hirschhorn: Oh, aħna tagħmel dan fiż-żewġ postijiet? 

UDJENZA: Yeah. 

JASON Hirschhorn: OK. Jekk immorru? Oh my goodness. Jien sorry. I ruhna ghall-iskrin. Huwa tip ta 'freaking fuqna. Hekk jagħżlu għażla. Żero, kull l-kodiċi, quits-programm. Wieħed inserts xi ħaġa. Ejja daħħal tlieta. L-inserit ma kienx ta 'suċċess. Jien ser jistampa. I ma jkollhom xejn. OK. Forsi li kien biss fluke. Daħħal wieħed. Mhux suċċess. OK. Ejja run permezz GDB verament malajr check out dak li qed jiġri. 

Ftakar GDB. / L-isem tal tiegħek Programm gets lilna fis GDB. Hija li ħafna biex jimmaniġġaw? Il jteptep? Probabbilment. Qrib l-għajnejn tiegħek u tieħu xi fond nifsijiet jekk ikollok għajjien ta 'tħares lejn dan. Jien fil GDB. X'inhu l-ewwel ħaġa I do fil GDB? Imxejna ltqajna biex insemmu x'inhu għaddej hawn. Ejja ara. Illum għandna sitt minuta sa figura out x'inhu għaddej. Break prinċipali. U allura x'għandi nagħmel? Carlos? Run. OK. Ejja jagħżlu għażla. U liema ma N tagħmel? Next. Yeah. 

UDJENZA: Ma inti ssemmi - ma inti tgħid li l-kap, kien initialized għall null fil-bidu. Imma ħsibt inti qal li kien OK. 

JASON Hirschhorn: Ejja ħa mmorru - ejja nħarsu fil GDB, u mbagħad aħna ser imorru lura. Iżda ħsejjes simili diġà għandek xi ideat dwar dak li għaddej. Allura aħna tixtieq li daħħal xi ħaġa. OK. Aħna daħħal. Jekk jogħġbok jidħlu int. Aħna ser daħħal tlieta. U mbagħad jien fuq din il-linja. Kif nista tmur tibda debugging l-inserzjoni magħruf funzjoni? Oh my goodness. Li l-lott. Huwa li freaking ħafna? 

UDJENZA: Oh, huwa miet. 

JASON Hirschhorn: I biss jinġibed out. OK. 

UDJENZA: Forsi huwa l- tarf l-ieħor tal-wajer. 

JASON Hirschhorn: Ara naqra. Allura l-linja tal-qiegħ - dak did you say? 

UDJENZA: I qal li l-ironija ta 'teknika diffikultajiet f'din il-klassi. 

JASON Hirschhorn: I know. Jekk biss kelli kontroll fuq dik il-parti. [Inaudible] Li ħsejjes kbar. Għaliex ma inti guys tibda taħseb dwar dak li aħna seta 'jsir ħażin, u se nkunu lura f'90 sekonda. 

Avica, jien ser jistaqsu kif imorru għalik insert_node ġewwa biex debug dan. Allura dan huwa fejn aħna l-aħħar jitħalla 'off. Kif nista mur ġewwa insert_node, Avica, li jeżamina x'inhu għaddej? What GDB kmand? Break ma tieħu me ġewwa. Does Marquise taf? 

UDJENZA: What? 

JASON Hirschhorn: What kmand GDB I jużaw biex tmur ġewwa din il-funzjoni? 

UDJENZA: Pass? 

JASON Hirschhorn: Pass via S. Li jieħu me ġewwa. OK. New_node mallocing xi spazju. Li kollha qisu għaddej tagħha. Ejja teżamina new_node. Hija ltqajna xi indirizz memorja. Ejja check - li hija kollha korretti. Hekk kollox hawnhekk jidher li tkun qed taħdem b'mod korrett. 

UDJENZA: X'hemm differenza bejn P u display? 

JASON Hirschhorn: P stands għall-istampar. U għalhekk inti qed tistaqsi x'inhu l- differenza bejn dan u dan? F'dan il-każ, xejn. Iżda ġeneralment hemm xi differenzi. U inti għandek tfittex fil-manwal GDB. Iżda f'dan il-każ, xejn. Aħna għandhom tendenza li jużaw print, għalkemm, minħabba aħna ma bżonn tagħmel ħafna aktar minn print valur wieħed. 

OK. Allura aħna fuq il-linja 80 tal-kodiċi tagħna, iffissar node * Curr ugwali għal lista. Let us jistampa Curr. Huwa ugwali lista. Sweet. Stenna. Hija ugwali xi ħaġa. Dan ma jidhirx dritt. Hemm immorru. Huwa minħabba fl GDB, id-dritt, jekk huwa l-linja int fuqha ma jkunx esegwit s'issa. Għalhekk ikollok bżonn li fil-fatt tip jmiss biex tesegwixxi l-linja qabel jaraw riżultati tagħha. Allura aħna qegħdin hawn. Aħna biss esegwiti din il-linja, ugwali preċedenti null. Għalhekk għal darb'oħra, jekk aħna jistampaw preċedenti aħna mhux se tara xejn stramb. Imma jekk aħna fil-fatt tesegwixxi dik linja, allura se naraw li dik il-linja maħduma. 

Allura aħna għandna Curr. Dawk huma t-tnejn tajbin. Dritt? Issa aħna qed dwar din il-linja dritt hawn. Filwaqt Curr ma null ugwali. Well, dak ma Curr ugwali? Aħna biss raw dan laħaq null. Aħna stampat it out. I ser ipprintjaha ġdid. Għalhekk hija li filwaqt li loop ser tesegwixxi? 

UDJENZA: Le 

JASON Hirschhorn: Allura meta I ittajpjat li line, tara aħna qabża-triq kollha sal-qiegħ, ritorn foloz. U allura aħna qed tmur biex jirritornaw falza u mur lura għall-programm tagħna u eventwalment jistampa, bħal rajna, l-inserzjoni ma kienx ta 'suċċess. Allura, xi ħadd xi ideat dwar dak għandna bżonn tagħmel biex jiffissaw dan? Jien ser tistenna sakemm nara koppja ta 'l-idejn go up. Aħna ma teżegwixxi dan. Wieħed iżomm f'moħħu, dan kien l-ewwel ħaġa li kienu qed jagħmlu. Jien mhux se jagħmlu koppja. Jien ser tagħmel ftit. Għaliex koppja ifisser tnejn. I ser stenna għal aktar minn tnejn. 

L-ewwel inserzjoni, Curr, b'mankanza ugwali null. U dan loop tesegwixxi biss jekk Curr ma huwiex null. Allura kif nista 'nikseb madwar dan? Nara tliet idejn. I ser stenna għal aktar minn tlieta. Marcus, x'taħseb? 

UDJENZA: Well, jekk għandek bżonn li tesegwixxi aktar minn darba, inti biss bidla li loop do-waqt. 

JASON Hirschhorn: OK. Li se ssolvi l-problema tagħna, għalkemm? 

UDJENZA: F'dan il-każ l-ebda minħabba il-fatt li l-lista tkun vojta. Mela allura inti probabilment biss bżonn li jiżdiedu dikjarazzjoni li jekk il-ħruġ loop imbagħad inti għandek tkun fl-aħħar ta ' il-lista, f'liema punt inti tista 'biss daħħalha. 

JASON Hirschhorn: I bħal dik. Li jagħmel sens. Jekk il-loop ħruġ - għaliex dan ser jirritorna falza hawn. Allura jekk il-ħruġ loop, allura aħna qed fuq l-aħħar tal-lista, jew forsi l- bidu ta 'lista jekk ikun hemm xejn fil- dan, li hija l-istess bħall-aħħar. Allura issa irridu li daħħal xi ħaġa hawn. Allura kif ma dan il-kodiċi tfittex, Marcus? 

UDJENZA: Jekk inti diġà ltqajna l-node malloced, inti tista 'biss jgħidu new_node-> jmiss ugwali null minħabba għandu jkun fl-aħħar. Jew new_node> jmiss ugwali null. 

JASON Hirschhorn: OK. Jiddispjacini. New_node-> jmiss ugwali null għaliex aħna qed fl-aħħar. Dan ma tqiegħed lilha pulzieri Kif nistgħu poġġih fil-lista? Dritt. Li jinsab biss li dan ikun iffissat daqs. Nru kif do we attwalment poġġih fil-lista? X'hemm tipponta lejn il- aħħar tal-lista? 

UDJENZA: Kap. 

JASON Hirschhorn: Jiddispjacini? 

UDJENZA: Head hija li tipponta sa l-aħħar tal-lista. 

JASON Hirschhorn: Jekk hemm xejn fil- il-lista, ras hija li tipponta lejn l- aħħar tal-lista. Allura li ser taħdem għall- ewwel inserzjoni. What about jekk hemm koppja affarijiet fil-lista? Minn aħna ma rridux li jistabbilixxu ras ugwali għal new_node. What do rridu nagħmlu hemmhekk? Yeah? Probabbilment preċedenti. Se dan ix-xogħol? Ifakkar li qabel huwa biss pointer għal node. U preċedenti hija varjabbli lokali. Allura din il-linja se tistabbilixxi varjabbli lokali, preċedenti, daqs jew tipponta lejn dan node ġdid. Li mhux se attwalment poġġih fil-lista tagħna, għalkemm. Kif nistgħu poġġih fil-lista tagħna? Akchar? 

UDJENZA: Naħseb li inti do-> attwali li jmiss. 

JASON Hirschhorn: OK. Curr-> jmiss. Għalhekk għal darb'oħra, l-unika raġuni aħna qed down hawnhekk huwa, dak ma kurrent ugwali? 

UDJENZA: Ugwali null. 

JASON Hirschhorn: U iva, liema jiġri jekk nagħmlu null-> jmiss? What do we se tikseb? Aħna ser jiksbu tort segmentazzjoni. 

UDJENZA: Do Curr ugwali null. 

JASON Hirschhorn: Dik hija l-istess ħaġa bħala prev, għalkemm, għaliex hemm varjabbli lokali aħna qed jistabbilixxu daqs dan node ġdid. Ejja ħa mmorru lura għall-istampa tagħna ta 'ddaħħal xi ħaġa. Say aħna qed tiddaħħal fl-aħħar tal-lista, hekk dritt hawn. Għandna pointer kurrenti li l- tipponta lejn null u punt preċedenti thats tipponta lejn 8. Allura dak li għandna bżonn biex taġġorna, Avi? 

UDJENZA: Preċedenti-> jmiss? 

JASON Hirschhorn: Preċedenti-> jmiss huwa dak irridu li taġġorna minħabba li fil-fatt se daħħalha fil l-aħħar tal-lista. Għad għandna bug waħda, għalkemm, li aħna qed tmur jiddekorri fil. X'hemm li bug? Yeah? 

UDJENZA: Huwa ser jirritorna falza f'dan il-każ? 

JASON Hirschhorn: Oh, huwa qed ser jirritornaw falza. Iżda hemm ieħor bug. Allura aħna ser bżonn biex tistabbilixxi ritorn veru. 

UDJENZA: Does preċedenti xorta ugwali null fil-quċċata tal-lista? 

JASON Hirschhorn: għadu So preċedenti ugwali null fil-bidu nett. Allura kif nistgħu tikseb aktar minn dak? Yeah? 

UDJENZA: Naħseb li inti tista 'tagħmel verifika qabel il-loop filwaqt biex tara jekk huwa lista vojta. 

JASON Hirschhorn: OK. Mela ejja mur hawn. Tagħmel verifika. Jekk - 

UDJENZA: Mela jekk head ugwali ugwali null. 

JASON Hirschhorn: Jekk ras ugwali ugwali null - li ser jgħidulna jekk huwa lista vojta. 

UDJENZA: U allura inti tagħmel ras ugwali ġdid. 

JASON Hirschhorn: Head ugwali new_node? U x'iktar do we bżonn tagħmel? 

UDJENZA: U mbagħad inti tirritorna veru. 

JASON Hirschhorn: Mhux pjuttost. Aħna nieqsa pass wieħed. 

UDJENZA: New_node jmiss għandu jindika null. 

JASON Hirschhorn: Eżattament, Alden. U allura aħna jistgħu jirritornaw veru. OK. Iżda huwa għadu idea tajba li tagħmel affarijiet fl-aħħar tal-lista, id-dritt? Kull dritt. Aħna xorta tista 'attwalment tikseb sa l-aħħar tal-lista. Allura dan huwa kodiċi multa jekk aħna qed fil- tmiem tal-lista u hemm xi affarijiet fil-lista? Dritt? Għaliex aħna xorta jkollhom idea Marcus tal. Aħna jista ħruġ dan loop minħabba aħna qed fl-aħħar tal-lista. Allura aħna xorta jixtiequ dan kodiċi down hawn? 

UDJENZA: Iva. 

JASON Hirschhorn: Yeah. U dak li għandna bżonn għall-bidla dan? Veru. Ma li tajba ħoss għal kulħadd s'issa? Kulmin xi - Avi, do ikollok xi ħaġa li żżid? 

UDJENZA: Le 

JASON Hirschhorn: OK. Allura aħna ħadna ftit bidliet. Aħna ħadna din il-verifika qabel we marru għal-lista vojta. Allura aħna ħadt kura ta 'lista vojta. U hawn aħna ħadu kura ta ddaħħal xi ħaġa fl-aħħar tal-lista. Għalhekk jidher bħal din teħid loop filwaqt li kura ta 'affarijiet fl bejn, x'imkien fil-lista jekk ikun hemm huma affarijiet fil-lista. 

OK. Let us run dan il-programm mill-ġdid. Mhux suċċess. 

UDJENZA: Inti ma jagħmluhiex. 

JASON Hirschhorn: Oh, I ma tagħmel dan. Punt tajjeb, Michael. Ejja żid make marbuta. Line 87 hemm żball. Linja 87. Alden, din kienet l-linja int tajt lili. X'hemm ħażin? 

UDJENZA: Għandu jkun li null. 

JASON Hirschhorn: Eċċellenti. Eżattament id-dritt. Għandu jkun null. Ejja jagħmlu mill-ġdid. Jikkompilaw. OK. Ejja daħħal tlieta. L-inserit kienet ta 'suċċess. Ejja ipprintjaha. Oh, jekk biss nistgħu check. Iżda aħna ma jsir l- print funzjoni s'issa. Ejja jidħol xi ħaġa oħra. X'għandu aħna jidħol? 

UDJENZA: Seven. 

JASON Hirschhorn: Seven? 

UDJENZA: Iva. 

JASON Hirschhorn: Għandna tort seg. Allura aħna ltqajna wieħed, iżda aħna b'mod ċar ma tistax tikseb tnejn. Huwa 05:07. Allura nistgħu debug dan għal tliet minuti. Imma jien ser leave us here u jimxu fuq hash tabelli. Iżda għal darb'oħra, it-tweġibiet għal dan il-kodiċi I se email lilek fi ftit. Aħna viċin ħafna dan. I ħafna ninkoraġġukom biex insemmu x'inhu għaddej hawn u tiffissa lilha. So I ser email inti dan il-kodiċi bħala ukoll plus-soluzzjoni - Probabbilment is-soluzzjoni aktar tard. Ewwel dan il-kodiċi. 

Il-ħaġa oħra I trid tagħmel qabel we finitura huwa aħna ma meħlusa xejn. So I nuruk dak valgrind Dehra. Jekk aħna run konfini valgrind dwar il-programm tagħna,. / marbut. Għal darb'oħra, skond din slide, aħna għandhom jimxu valgrind ma 'xi tip ta' għażla, f'dan il-każ - Leakage-check = sħiħa. Mela ejja ikteb valgrind - Leakage-check = sħiħa. Allura dan se jimxu valgrind dwar il-programm tagħna. U issa l-programm attwalment runs. Allura aħna qed tmur biex jimxu eżatt bħal qabel, xi ħaġa pulzieri Jien ser jitqiegħdu fi tliet. Li xogħlijiet. Jien mhux ser tipprova tpoġġi fil xi ħaġa inkella għaliex aħna qed tmur biex jiksbu falza seg f'dak il-każ. Hekk jien biss se nieqaf. 

U issa tara down hawn tnixxija u sommarju borġ. Dawn huma l-affarijiet tajbin li inti tixtieq li check out. Allura l-sommarju borġ - huwa jgħid, fl-użu fil-ħruġ - tmien bytes blokka waħda. Dan blokka waħda hija l- node we malloced. Michael, inti qal qabel node huwa tmienja fil- gdim minħabba li għandha l-eqreb numru sħiħ u l-pointer. Allura dak node tagħna. U allura jgħid aħna użati malloc seba 'darbiet u aħna meħlusa xi ħaġa sitt darbiet. Imma aħna qatt imsejħa ħielsa, so I ma jkollhom ebda idea dak li dan qed jitkellem dwar. 

Iżda huwa biżżejjed li jingħad li meta tiegħek runs programm, malloc qed jissejjaħ f'xi postijiet oħra li aħna ma bżonn ninkwetaw dwar. Allura malloc kien probabbilment imsejħa f'xi postijiet. Aħna ma bżonn ninkwetaw fejn. Iżda dan huwa verament us. Dan l-ewwel linja hija us. Aħna ħallew dik blokk. U tista 'tara li hawn fis-sommarju nixxija. Still jista 'jintlaħaq - tmien bytes fir blokka waħda. Dan ifisser li l-memorja - aħna nixxew li l-memorja. Żgur mitlufa - xi ħaġa hija mitlufa għall-tajba. Ġeneralment, inti mhux ser tara xejn hemm. Still jista 'jintlaħaq huwa ġeneralment fejn int ser tara l-affarijiet, fejn inti taf jridu tfittex biex tara dak kodiċi għandek ħelsithom imma inti nesa biex ħielsa. 

U mbagħad jekk dan ma kienx il-każ, jekk aħna ma kollox ħielsa, nistgħu jivverifikaw li. Ejja biss run-programm mhux qed ipoġġu fil-xejn. Int ser ikollok tara stabbiliti hawn fl-użu fil-ħruġ - żero bytes fir żero blokki. Dan ifisser kellna xejn xellug meta dan il-programm ħareġ. Allura qabel ma ddawwar fil pset6, run valgrind u aċċerta ruħek li ma jkollhomx kwalunkwe memorja tnixxijiet fil-programm tiegħek. Jekk għandek xi mistoqsijiet valgrind, tħossok liberu li jilħqu. Iżda dan huwa kif tużah. Sempliċi ħafna - ara jekk inti ikollhom fl-użu fil-ħruġ - xi bytes fi kwalunkwe blokki. 

Allura aħna kienu qed jaħdmu fuq daħħal node. I kellu żewġ funzjonijiet l-oħra hawn - jistampaw lymph nodes u ħielsa. Għal darb'oħra, dawn huma funzjonijiet li huma se jkun tajjeb għalik għall-prattika minħabba li dawn se jgħinuk mhux biss ma dawn l-eżerċizzji kampjun iżda wkoll fuq il-problema sett. Huma mappa fuq pretty qrib affarijiet int ser ikollhom jagħmlu fil- problema stabbiliti. Imma I do jixtiequ jagħmlu ċert we touch fuq kollox. U tabelli hash huma wkoll kruċjali biex dak li aħna qed tagħmel fit-taqsima dan ġimgħa - jew fis-sett problema. 

Allura aħna qed tmur biex jintemm it-taqsima jitkellem dwar tabelli hash. Jekk tinnota I għamel tabella hash ftit. Dan mhuwiex dak li aħna qed jitkellem dwar, madankollu. Aħna qed nitkellmu dwar differenti tip ta 'tabelli hash. U fil-qalba, tabella hash tiegħu huwa xejn aktar minn array plus funzjoni hash. Aħna qed tmur biex jitkellmu għal ftit biss biex kun żgur kulħadd jifhem dak funzjoni hash huwa. U jien tghidlek issa li huwa xejn aktar minn żewġ affarijiet - firxa u funzjoni hash. U hawn huma l-passi permezz li din topera. 

Hemm firxa tagħna. Hemm funzjoni tagħna. B'mod partikolari, il-funzjonijiet hash bżonn jagħmlu ftit affarijiet ma 'dan. Jien ser jitkellmu speċifikament dwar din il-problema stabbiliti. Huwa probabbilment se tieħu fi string. U dak li huwa għaddej biex tirritorna? Liema tip ta 'data? Alden? Funzjoni hash Your ritorn? Integer. Allura dan huwa dak li l-hash tabella jikkonsisti - tabella fil-forma ta 'firxa u funzjoni hash. Kif taħdem? Hija taħdem fi tliet passi. Nagħtu ewlieni. F'dan il-każ, aħna ser tagħtiha a string. Aħna nsejħu l-funzjoni hash kull pass fuq iċ-ċavetta u nikbru valur. 

Speċifikament, aħna ser ngħidu irridu jiksbu numru sħiħ. Li numru sħiħ, hemm huma speċifiċi ħafna limiti għal dak li integer jista 'jkun. F'dan l-eżempju, firxa tagħna hija ta 'daqs tlieta. Allura dak numri jista 'dan integer jkun. X'inhu l-firxa ta 'valuri validi għall- li numru sħiħ, it-tip ritorn ta 'dan hash funzjoni? Żero, wieħed u tnejn. Il-punt tal-funzjoni hash huwa li insemmu l-post fil-firxa fejn ewlieni tagħna huwa għaddej. Hemm tliet possibbli biss postijiet hawn - żero, wieħed, jew tnejn. Allura din il-funzjoni aħjar ritorn żero, wieħed, jew tnejn. Xi indice valida f'dan array. 

U mbagħad jiddependi fuq fejn jirritorna, tistgħu taraw hemm firxa miftuħa jibbrakitjaw il-valur. Li meta aħna tpoġġi l-ċavetta. Allura aħna tarmi l-qara ħamra, we toħroġ żero. Fl array bracket 0, npoġġux qara. Aħna tarmi qtates, aħna toħroġ wieħed. Npoġġux qattus fil waħda. Nitfgħu fl-brimba. Aħna toħroġ tnejn. Npoġġux spider fuq firxa bracket tnejn. Ikun hekk sbieħ jekk maħduma bħal dik. Iżda sfortunatament, kif Ser naraw, huwa daqsxejn aktar ikkumplikata. 

Qabel ma nikbru hemm, xi mistoqsijiet dwar dan bażiku set-up ta 'tabella hash? Din hija immaġni ta 'eżattament dak li aħna ġibdet fuq il-bord. Iżda peress li aħna ħarġitu fuq il-bord, I am not se jmorru fis dan aktar. Essenzjalment keys, il-kaxxa s-sewda magic - jew f'dan il-każ, il-kaxxa Teal - ta ' funzjoni hash ipoġġihom fi bramel. U f'dan eżempju aħna qed mhux qed ipoġġu l-isem. Aħna qed tqegħid-telefon assoċjati numru ta 'l-isem fil-barmil. Imma int tista 'faċilment biss tpoġġi l-isem fil-barmil. 

Dan huwa biss stampa ta 'dak fassalna fuq il-bord. Għandna ostakoli potenzjali, għalkemm. U hemm żewġ partikolarment slides li nixtieq li jmorru fuq. L-ewwel wieħed huwa dwar funzjoni hash. So I staqsa l-mistoqsija, dak li jagħmel funzjoni hash tajba? I jagħti żewġ tweġibiet. L-ewwel hija li huwa deterministic. Fil-kuntest tal-funzjonijiet hash, dak li jfisser dan? Iva? 

UDJENZA: Hija tista 'ssib l- indiċi fil-ħin kostanti? 

JASON Hirschhorn: Li ma jkunx dak li jfisser. Imma dak raden tajba. Ħaddieħor jkollhom raden din xi tfisser? Li funzjoni hash tajba huwa deterministic? Annie? 

UDJENZA: Li ċavetta jistgħu jiġu assoċjati biss għal post wieħed fit-tabella hash. 

JASON Hirschhorn: C'est eżattament id-dritt. Kull darba li inti tpoġġi fil-qara ħamra, dejjem jirritorna żero. Jekk inti tpoġġi fil qara u hash tiegħek funzjoni lura żero iżda għandha probabbiltà li jirritornaw xi ħaġa inkella ogħla minn żero - hekk forsi din tista 'tirritorna wieħed xi kultant jew darbtejn oħra - li mhix funzjoni hash tajba. Inti eżattament id-dritt. Funzjoni hash tiegħek għandu jirritorna l- istess numru sħiħ eżatt, f'dan il-każ, għall- l-istess sekwenza eżatta. 

Forsi dan jirritorna l-istess numru sħiħ eżatt għall-istess sekwenza eżatta irrispettivament mill-kapitalizzazzjoni. Iżda f'dak il-każ huwa għadu deterministic minħabba affarijiet multipli huma mapping fuq l-istess valur. Li l-multa. Sakemm ikun hemm biss wieħed output għal dħul partikolari. 

OK. It-tieni ħaġa hija li prospetti indiċi validi. Aħna aġġornati li qabel. Din il-funzjoni hash - oh boy - funzjoni hash għandu ritorn indiċi validi. Allura ngħid - ejja mmorru lura għall dan l-eżempju. Funzjoni hash tiegħi tgħodd up l-ittri fil-kelma. Dik hija l-funzjoni hash. U prospetti li integer. Hekk jekk Għandi l-kelma A, huwa ser jirritorna wieħed. U li għaddej biex jitqiegħdu A dritt hawn. X'jiġri jekk nressaq fil-BAT kelma? Huwa ser jirritorna tlieta. Fejn ma BAT imorru? 

Hija ma jinstallax. Iżda jeħtieġ li tmur x'imkien. Dan huwa tabella hash tiegħi wara kollox, u kollox jeħtieġ li tmur x'imkien. Għalhekk, fejn għandhom BAT imorru? Kwalunkwe ħsibijiet? Guesses? Guesses Tajba? 

UDJENZA: Zero. 

JASON Hirschhorn: Għaliex żero? 

UDJENZA: Minħabba tlieta modulo tliet huwa żero? 

JASON Hirschhorn: Three modulo tlieta huwa żero. Dan huwa raden kbir, u li l-korretta. Allura f'dan il-każ dan għandu probabbilment tmur għal żero. Allura mod tajjeb biex jiżguraw li dan hash funzjoni lura biss indiċi validi huwa li modulo lilha mill-daqs tat-tabella. Jekk inti modulo kwalunkwe dan denunzji tlieta, int dejjem se tikseb xi ħaġa bejn żero, wieħed u tnejn. U jekk dan dejjem jirritorna sebgħa, u inti dejjem modulo minn tlieta, int dejjem se tikseb l-istess ħaġa. 

Allura huwa għadu deterministic jekk inti modulo. Iżda dan se jiżgura li inti qatt ma tikseb xi ħaġa - industrija invalidu. Ġeneralment, li modulo għandu jseħħ ġewwa funzjoni hash tiegħek. Allura inti m'għandekx bżonn ninkwetaw dwar dan. Inti biss tista 'tiżgura li dan huwa indice valida. Kwalunkwe mistoqsijiet dwar dan iżvantaġġ potenzjali? 

OK. U hemm immorru. Sussegwentement iżvantaġġ potenzjali, u dan huwa l-waħda kbira. X'jiġri jekk żewġ ċwievet mappa l-istess valur? Allura hemm żewġ modi biex jimmaniġġjaw dan. L-ewwel wieħed huwa msejjaħ lineari probing, li jien mhux se jmorru fuq. Iżda inti għandek tkun familjari mal-mod kif li jiffunzjona u dak li hu. 

It-tieni wieħed I vais jmorru fuq għaliex dik hija l-waħda li ħafna nies probabbilment se jispiċċaw tiddeċiedi għall-użu fil-sett problema tagħhom. Of course, inti ma għandekx. Iżda għall-problema sett, ħafna nies għandhom tendenza li jagħżlu li tinħoloq tabella hash ma 'chaining separati li jimplimentaw dizzjunarju tagħhom. Allura aħna qed tmur biex jmorru fuq xi tfisser biex tinħoloq tabella hash ma chaining separat. 

So I jitqiegħdu fil-qara. Dan jirritorna żero. U nressaq qara hawn. Imbagħad nressaq fil - x'hemm ħaġa oħra Halloween themed? 

UDJENZA: Candy. 

JASON Hirschhorn: Candy! Li l-waħda kbira. Nressaq fl-kandju, u candy wkoll tagħti me żero. What do I do? Xi ideat? Għaliex inti kull tip ta 'know dak chaining separata. Allura xi ideat dak li tagħmel? Yeah. 

UDJENZA: Inpoġġu l-sekwenza attwalment fit-tabella hash. 

JASON Hirschhorn: Allura aħna qed tmur biex jiġbed l-idea tajba hawn. OK. 

UDJENZA: Ittieħdu l-hashtable [Inaudible] l-pointer li l-punti li il-bidu ta 'lista. U mbagħad jkunu qara tkun l-ewwel valur f'dik il-lista marbuta u candy jkun it-tieni valur f'dik il-lista marbuta. 

JASON Hirschhorn: OK. Marcus, li kien pendenti. Jien ser jiksru dak isfel. Marcus huwa qal ma jissostitwixxu qara. Dan ikun ħażin. Tpoġġix kandju x'imkien ieħor. Aħna ser jpoġġuhom tnejn għal żero. Iżda aħna qed tmur biex jittrattaw jqiegħduhom fuq żero billi ħolqien ta 'lista fuq iż-żero. U aħna qed tmur biex joħolqu lista ta ' dak kollu li fassal għal żero. U l-aħjar mod aħna tgħallimna biex joħolqu lista li tista 'tikber u tiċkien dinamikament mhux fi array ieħor. Allura ma 'firxa multi-dimensjonali. Iżda li biss joħolqu lista marbuta. 

Allura dak li hu propost - Jien ser tikseb ġdida - hija toħloq firxa ma pointers, firxa ta 'indikaturi. OK. Kull idea jew ħjiel dak it-tip ta 'dan pointers għandu jkun? Marcus? 

UDJENZA: Pointers għal - 

JASON Hirschhorn: Għaliex inti qal lista marbuta, sabiex - 

UDJENZA: Node pointers? 

JASON Hirschhorn: node pointers. Jekk l-affarijiet fil marbut tagħna lista huma lymph allura dawn għandu jkun node pointers. U liema do ugwali inizjalment? 

UDJENZA: Null. 

JASON Hirschhorn: Null. Allura hemm ħaġa vojta tagħna. Prospetti Qara żero. Dak li nagħmlu? Walk me permezz ta 'dan? Attwalment, Marcus diġà tatni. Xi ħadd ieħor jimxu lili permezz tiegħu. Dak li nagħmlu meta aħna - dan jistenna simili ħafna għal dak li konna biss tagħmel. Avi. 

UDJENZA: Jien ser tieħu raden. Allura meta ikollok kandju. 

JASON Hirschhorn: Yeah. Well, aħna ltqajna qara. Ejja nneħħu l-ewwel wieħed tagħna. Sirna qara. 

UDJENZA: OK. Prospetti Qara żero. Allura inti tpoġġi f'dak. Jew fil-fatt, inti poġġih fil-lista marbuta. 

JASON Hirschhorn: Kif do we poġġih fil-lista marbuta? 

UDJENZA: Oh, il-sintassi attwali? 

JASON Hirschhorn: Just walk - say aktar. Dak li nagħmlu? 

UDJENZA: Inti biss daħħal bħala l-ewwel node. 

JASON Hirschhorn: OK. Allura aħna għandna node tagħna, qara. U issa kif nista daħħal dan? 

UDJENZA: You tassenja lill-pointer. 

JASON Hirschhorn: Liema pointer? 

UDJENZA: Il-pointer fuq iż-żero. 

JASON Hirschhorn: Għalhekk, fejn ma dan il-punt? 

UDJENZA: Biex null dritt issa. 

JASON Hirschhorn: Well, huwa tipponta lejn null. Imma jien tqegħid fil qara. Għalhekk, fejn għandhom it punt? 

UDJENZA: Biex qara. 

JASON Hirschhorn: Biex qara. Eżattament. Allura dan jindika qara. U fejn ma dan pointer fil-punt qara? Biex 

UDJENZA: Null. 

JASON Hirschhorn: Biex null. Eżattament. Allura aħna biss jiddaħħal xi ħaġa fil-lista marbuta. Aħna biss kiteb dan il-kodiċi li jagħmlu dan. Kważi aħna kważi ltqajna kompletament maqsuma. Issa aħna daħħal kandju. Kandju tagħna wkoll tmur għal żero. Allura dak li nagħmlu ma kandju? 

UDJENZA: Hija tiddependi fuq jekk jew mhux aħna qed tipprova sort. 

JASON Hirschhorn: C'est eżattament id-dritt. Hija tiddependi fuq jekk jew le aħna qed tipprova sort. Ejja nassumu aħna mhux qed se sort. 

UDJENZA: Well imbagħad, kif iddiskutejna qabel, huwa aktar sempliċi biss biex tqiegħed lilha dritt fil-bidu sabiex l-pointer minn żero jindika kandju. 

JASON Hirschhorn: OK. Żomm fuq. Let me joħolqu kandju dritt hawn. Allura dan pointer - 

UDJENZA: Yeah, għandu issa tkun tipponta lejn kandju. Imbagħad għandna l-pointer minn punt kandju għall-qara. 

JASON Hirschhorn: Bħal dak? U jgħidu aħna ltqajna ieħor ħaġa li Mappa għal żero? 

UDJENZA: Well, inti biss jagħmlu l-istess ħaġa? 

JASON Hirschhorn: Jagħmlu l-istess ħaġa. Allura f'dan il-każ, jekk aħna ma tixtieq li jżommha magħżula hija ħsejjes pjuttost sempliċi. Nieħdu l-pointer fil-indice mogħti mill-funzjoni hash tagħna. Għandna dak il-punt għall-node ġdid tagħna. U allura dak kollu li kien tipponta li preċedentement - f'dan null każ, fil- tieni każ qara - li, irrispettivament huwa tipponta lejn qabel, aħna żid fil-li jmiss ta ' node ġdid tagħna. Aħna qed ddaħħal xi ħaġa fil-bidu. Fil-fatt dan huwa ħafna aktar sempliċi milli jippruvaw iżommu l-lista magħżula. Iżda għal darb'oħra, tiftix se tkun aktar ikkumplikat hawn. Aħna ser dejjem ikollhom imorru għall-aħħar. 

OK. Xi mistoqsijiet dwar chaining separat? Kif li jaħdem? Jekk jogħġbok staqsi minnhom issa. I really tixtieq tagħmel żgur li inti kollha jifhmu dan qabel we ras. 

UDJENZA: Għaliex inti tpoġġi qara u candy fl-istess parti tat-tabella hash? 

JASON Hirschhorn: Good kwistjoni. Għaliex aħna tpoġġihom fl-istess parti tat-tabella hash? Ukoll, f'dan il-każ il-funzjoni hash tagħna prospetti żero għal tnejn minnhom. Sabiex ikunu jeħtieġu li jmorru fuq iż-żero indice għaliex dan huwa fejn aħna qed tmur biex tfittex għalihom jekk aħna qatt tixtieq tfittex iwettquhom. Għal darb'oħra, ma 'approċċ lineari probing aħna mhux se jpoġġuhom tnejn għal żero. Iżda fl-approċċ katina separata, aħna qed tmur biex ipoġġihom kemm żero u mbagħad toħloq lista off ta 'żero. 

U ma rridux li jissostitwixxu qara sempliċement għal dak għaliex allura aħna ser jassumi li qara kienet qatt mdaħħal. Jekk aħna biss iżommu ħaġa waħda fil- post li tkun ħażina. Imbagħad ikun hemm l-ebda ċans minna qatt - jekk aħna qatt kellhom duplikat, allura aħna kien biss iħassar valur inizjali tagħna. Allura hu għalhekk li aħna nagħmlu dan l-approċċ. Jew hu għalhekk li għażilna - iżda għal darb'oħra, aħna għażlet l-approċċ chaining separata, li hemm approċċi oħra ħafna wieħed jista 'jagħżel. Does li iwieġeb il-mistoqsija tiegħek? 

OK. Carlos. Linear probing ikun jinvolvi - jekk sibna ħabta fuq iż-żero, aħna look fil-post li jmiss biex tara jekk kien miftuħ u poġġih hemmhekk. U allura aħna nħarsu fl-isport li jmiss u jekk tara li kien miftuħ u poġġih hemmhekk. Hekk insibu l disponibbli li jmiss spot miftuħa u poġġih hemmhekk. Kwalunkwe mistoqsijiet oħra? Yeah, Avi. 

UDJENZA: Bħala segwitu għal dan, liema taħseb jfisser minn post li jmiss? Fit-tabella hash jew f'lista marbuta. 

JASON Hirschhorn: Għal lineari programmazzjoni, l-ebda listi marbuta. Il-post li jmiss fuq il-mejda hash. 

UDJENZA: OK. Allura l-tabella hash tkun initialized għad-daqs - bħall-għadd ta 'spag li inti kienu ddaħħal? 

JASON Hirschhorn: You kieku jixtiequ li din tkun verament kbar. Iva. Hawnhekk hija stampa ta 'dak li aħna biss ġibdet fuq il-bord. Għal darb'oħra, aħna għandna ħabta dritt hawn. fi 152. U tkun taf tara ħloqna lista marbuta off ta 'dan. Għal darb'oħra, it-tabella hash chaining separata l-approċċ mhuwiex l-waħda inti għandek tieħu għall-problemi stabbiliti sitt iżda huwa wieħed li ħafna istudenti għandhom tendenza li jieħdu. Allura fuq din in-nota, ejjew nitkellmu fil-qosor qabel we ras dwar il-problema sitt, u mbagħad I ser jaqsmu storja miegħek. Għandna tliet minuti. 

Problema stabbiliti sitt. Inti għandek erba 'funzjonijiet - tagħbija, kontroll, id-daqs, u jħottu. Tagħbija - ukoll, aħna kont qed tmur fuq tagħbija biss issa. Fassalna tagħbija fuq il-bord. U aħna anke bdew kodifikazzjoni ħafna ddaħħal f'lista marbuta. Allura tagħbija mhuwiex ħafna aktar minn dak li aħna stajt biss qed tagħmel. 

Verifika ladarba inti għandek xi ħaġa mgħobbija. Huwa l-istess proċess bħal dan. L-istess ewwel żewġ partijiet fejn inti tarmi xi ħaġa fil-funzjoni hash u jiksbu valur tagħha. Imma issa aħna mhux ddaħħalha. Issa aħna qed tfittex għaliha. Għandi kodiċi tal-kampjun bil-miktub għall-konstatazzjoni xi ħaġa f'lista marbuta. I ninkoraġġukom biex prattika li. Iżda intuwittivament konstatazzjoni xi ħaġa pjuttost simili għal ddaħħal xi ħaġa. Tabilħaqq, aħna taw stampa ta 'sejba xi ħaġa f'lista marbuta, li jiċċaqalqu permezz sakemm inti ltqajna l-aħħar. U jekk inti ltqajna l-aħħar u ma setax jsibuha, allura huwa ma jkunx hemm. Allura dak kontroll, essenzjalment. 

Li jmiss huwa d-daqs. Ejja skip daqs. Fl-aħħarnett għandek jħottu. Jħottu hija waħda aħna ma mfassla fuq il-bord jew kodifikati s'issa. Imma I ninkoraġġukom biex tipprova kodifikazzjoni huwa fil-kampjun eżempju tagħna lista marbuta. Iżda jħottu intuwittivament huwa simili għal free - jew I medja hija simili biex jiċċekkjaw. Ħlief għal issa kull darba li inti qed tmur permezz, int mhux sempliċiment verifika biex ara jekk ikollok valur tiegħek hemmhekk. Imma int qed tieħu dak node u ħelsuha, essenzjalment. Dak hu li jħottu jitlob li inti tagħmel. Free kollox inti ħadthom malloced. Allura inti qed tmur permezz tal-lista kollha għal darb'oħra, għaddejjin mill-hash kollu tabella darb'oħra. Din id-darba ma tivverifika biex tara x'hemm hemmhekk. Just ħielsa x'hemm hemmhekk. 

U finalment daqs. Daqs għandhom jiġu implimentati. Jekk inti ma timplimenta d-daqs - I ser jgħidu dan bħal dan. Jekk inti ma timplimenta d-daqs eżattament linja waħda tal-kodiċi inkluż il- jirritornaw id-dikjarazzjoni, inti tagħmel daqs żbaljat. Sabiex tagħmel ċert daqs, għal full-disinn punti, int tagħmel dan fil eżattament waħda linja tal-kodiċi, inkluż l-istqarrija tar-ritorn. 

U ma pakkett up għadhom, Akchar. Kastur ħerqana. I riedu jgħidu grazzi guys biex jaslu għal taqsima. Jkollhom Halloween Happy. Dan huwa kostum tiegħi. I ser tkun liebes dan nhar il-Ħamis jekk nara inti fil-ħinijiet uffiċċju. U jekk int kurjuż dwar xi wħud aktar isfond dwar dan il-kostum, tħossok liberu li check out taqsima 2011 għal storja dwar l-għaliex jien liebes il-kostum qara. U din hija storja diqa. Sabiex tagħmel ċert li jkollok f'xi tessuti fil-qrib. Imma fuq dan, jekk għandek xi mistoqsijiet I ser twaħħal madwar barra wara taqsima. Xorti tajba dwar il-problema stabbiliti sitt. U kif dejjem, jekk għandek xi mistoqsijiet, let me know.