Jason Hirschhorn: Laipni lūdzam visus uz nodaļas Seven. Mēs esam septiņi nedēļas gaitā. Un tas upcoming ceturtdiena Ir Helovīni tāpēc es esmu ietērps kā ķirbju. Es nevarēju saliekt vairāk un laiž manas kurpes, tā ka ir iemesls, kāpēc es esmu tikai valkā zeķes. Es esmu arī nav valkājot kaut ko saskaņā to, tāpēc es nevaru pieņemt to, ja tas ir novērš uzmanību, lai jums. Es atvainojos jau iepriekš par to. Jums nav nepieciešams iedomāties kas notiek. Es esmu valkājot boxers. Tātad, tas viss ir labi. 

Man ir garāks stāsts par to, kāpēc es esmu ģērbies kā ķirbju, bet es esmu gatavojas saglabātu, ka turpmāk šajā sadaļā jo es vēlos, lai sāktu. Mums ir daudz aizraujošas lietas lai iet pa šo nedēļu. Lielākā daļa no tiem ir tieši saistīti ar šo nedēļas problēmu kopums, pārrakstīšanās. Mēs ejam, lai iet pa saistīt sarakstus un hash tabulas visam nodaļā. Man šo sarakstu up katru nedēļu, sarakstu resursi jums, lai palīdzētu jums ar materiāls par šo kursu. Ja ar zaudējumiem, vai arī, ja meklē kādu vairāk informācijas, pārbaudiet viens no šie resursi. 

Atkal, pset6 ir pārrakstīšanās, šīs nedēļas PSET. Un tas arī mudina jūs, un es aicinām jūs, lai izmantotu kādu citu resursi, kas īpaši šim PSET. Jo īpaši, trīs es esmu uzskaitīti uz ekrāna - gdb, kas mēs esam bijuši pazīstami ar un, izmantojot, bet tagad ir būs ļoti noderīga šonedēļ. Tāpēc man, kas šeit. Bet, kad jūs strādājat ar C, Jums vajadzētu vienmēr izmantot gdb lai atkļūdot savas programmas. Šonedēļ arī Valgrind. Vai kāds zina, ko Valgrind dara? 

Mērķauditorija: Tā pārbauda atmiņas noplūdes? 

Jason Hirschhorn: Valgrind pārbauda atmiņas noplūdes. Tātad, ja jūs malloc kaut kas jūsu programma, jūs lūdzot atmiņu. Beigās savu programmu, jums ir rakstīt bezmaksas visu, ko esat malloced dot atmiņu atpakaļ. Ja jums nav rakstīt bez beigās un jūsu programma nāk pie secinājuma, viss automātiski jāatbrīvo. Un mazo programmu, ir nav tik liels darījumu. Bet, ja jūs esat rakstiski ilgāku darbību programma, kas nav atmest, obligāti, pēc pāris minūtēm vai pāris sekundes, tad atmiņas noplūde var kļūt milzīgs darījumu. 

Tātad pset6, cerības ir, ka Jums būs nulle atmiņas noplūde ar jūsu programma. Lai pārbaudītu atmiņas noplūdes, palaist Valgrind un tas došu jums dažas jaukas izejas izīrēšanas jūs zināt, vai vai ne viss bija bez maksas. Mēs prakse ar to vēlāk šodien, cerams. 

Visbeidzot, diff komandu. Tu izmanto, kaut ko līdzīgu tam kas pset5 ar palūrēt rīku. Ļauj jums meklēt iekšpusē. Jūs arī izmanto diff, arī par problēma noteikti spec. Bet ļauj jums salīdzināt divus failus. Jūs varētu salīdzināt bitkartes failu un info galvenes personāla risinājumu un Jūsu risinājums pset5 ja izvēlaties to izmantot. Izmaiņas ļaus jums darīt, kā labi. Jūs varat salīdzināt pareizo atbildi, lai šīs nedēļas problēma iestatīts uz jūsu atbildi un redzēt, ja tā līniju līdz, vai redzēt kur kļūdas. 

Tātad tie ir trīs labas instrumenti, kas Jums vajadzētu izmantot šo nedēļu, un noteikti pārbaudiet savu programmu ar šiem trim instrumentiem pirms pagrieziena to iekšā Atkal, kā jau es minēju katru nedēļu, ja jums ir kādas atsauksmes par mani - gan pozitīva un konstruktīva - justies brīvi doties uz mājas lapā apakšā šo slide un ievadi to tur. I really appreciate jebkuru un visas atsauksmes. Un, ja jūs varētu man īpašas lietas, kas Es varu darīt, lai uzlabotu vai ka es esmu klājas labi, ka jūs vēlētos, lai es turpināsies, es pieņemt, ka pie sirds un tiešām cenšamies uzklausīt uz jūsu atsauksmēm. Es nevaru apsolīt es esmu gatavojas darīt viss, lai gan, piemēram, valkājot Ķirbja kostīms katru nedēļu. 

Tāpēc mēs esam gatavojas pavadīt lielāko daļu sadaļā, kā jau minēju, runājot par saistīti sarakstus un hash tabulas, kas būs tieši piemērojamas Problēma noteikti šonedēļ. Saistīti saraksti mēs iet pār salīdzinoši ātri, jo mēs esam pavadījuši godīgu bitu laiks iet pār to sadaļā. Un tā mēs iegūtu taisni kodēšanas problēmas, kas saistītas sarakstiem. Un tad beigās mēs runājam par hash tabulu, un to, kā tie attiecas uz šo nedēļas problēma noteikti. 

Jūs esat redzējuši šo kodu pirms. Tas ir struktūrai, un tas tiek definējot kaut kas jauns, ko sauc mezglā. Un iekšpusē mezglā ir vesels skaitlis tieši šeit un tur ir rādītājs cits mezgls. Mēs esam redzējuši šo pirms. Tas ir nāk par pāris nedēļas tagad. Tā apvieno norādes, ko mēs esam bijuši strādā ar, un structs, kas ļauj mums apvienot divus dažādus viss vienā datu tipu. 

Tur ir daudz kas notiek uz ekrāna. Bet tas viss ir relatīvi pazīstams ar jums. Pirmajā līnijā, mēs pasludināt jaunu mezglu. Un tad iekšā, ka jaunu mezglu, es noteikti integer minētajā mezglu, lai vienu. Mēs redzam nākamajā rindiņā es daru printf komandu, bet es esmu izcelta printf komandu, jo patiešām Svarīgi ir tas līnija šeit - new_node.n. Ko nozīmē dot nozīmē? 

Mērķauditorija: Iet uz mezglu un novērtē n vērtību to. 

Jason Hirschhorn: Tas ir tieši labi. Dot nozīmē piekļūt Z daļā Šīs jaunās mezglā. Šis nākamais rindā nav ko? Michael. 

Mērķauditorija: Tas rada vēl vienu mezglu , kas norāda uz jaunu mezglu. 

Jason Hirschhorn: Tātad tas nav izveidot jaunu mezglu. Tas rada to, ko? 

Mērķauditorija: rādītājs. 

Jason Hirschhorn: rādītāju uz mezglu, kā norādīts šajā mezglā * šeit. Tāpēc tas rada rādītāju uz mezglu. Un kura mezgls tas vērsta to, Michael? 

Mērķauditorija: New mezglu? 

Jason Hirschhorn: New mezglā. Un tas norāda, ka tāpēc, ka mēs esam devis adresi jaunu mezglu. Un tagad šo līniju mēs redzam divi dažādi veidi izsakot to pašu. Un es gribēju norādīt, kā šie divas lietas ir vienādi. Pirmajā rindā, mēs dereference rādītājs. Tāpēc mēs ejam uz mezglu. Tas ir tas, ko šī zvaigzne nozīmē. Mēs esam redzējuši, ka pirms ar norādes. Iet uz šo mezglu. Kas ir iekavās. Un pēc tam piekļūt caur dot operatoram n elements šajā mezglā. 

Tāpēc, ka ir ņemot sintakse mēs redzējām tieši šeit un tagad izmantojot to ar kursoru. Protams, tas kļūst veida aizņemts, ja Jūs esat rakstiski šos iekavas - ka zvaigzne un dot. Tā kļūst nedaudz aizņemts. Tāpēc mums ir daži sintaktisko cukuru. Un šī līnija tieši šeit - ptr_node-> n. Kas dara to pašu precīzu lieta. Tātad šīs divas rindas kods ir līdzvērtīgas un darīs tieši tas pats. 

Bet es gribēju uzsvērt, kas pirms mēs ejam tālāk, lai jūs saprastu, ka tiešām šī lieta šeit ir tikai sintaktisko cukurs dereferencing rādītāju un pēc tam dodas uz n daļa no šīs struktūrai. Visi jautājumi par šo slaidu? OK. 

Tāpēc mēs esam gatavojas iet cauri pāris Darbību, ka jūs varat darīt saistītie saraksti. Saistīts saraksts, atsaukšana, ir virkne punktiem, kas norāda uz vienu no otra. Un mēs parasti sākas ar rādītāju sauc par galvu, parasti, kas norāda uz Pirmais sarakstā. Tātad pirmajā līnijā šeit, mēs ir mūsu sākotnējā L pirmās. Tā, ka lieta, ko jūs varat iedomāties - tas tekstu tieši šeit, jūs varat iedomāties, kā tikai rādītājs, mēs esam saglabāti kaut kas punkti pirmajam elementam. Un šajā saistīta sarakstā mums ir četri mezgli. Katrs mezgls ir liela kaste. Lielāka kaste iekšpusē liels kaste ir vesels skaitlis daļa. Un tad mums ir rādītājs daļu. 

Šīs kastes nav vērsta uz mēroga dēļ, cik liela ir ir vesels skaitlis, kas bytes? Cik liels tagad? Četri. Un cik liels ir rādītājs? Četri. Tik tiešām, ja mēs to izdarīt Tas mērogā abas kastes būtu tāds pats lielums. Šajā gadījumā, mēs vēlamies, lai ievietotu kaut uz saistītajā sarakstā. Tātad jūs varat redzēt šeit lejā mēs ievietojot Piecu Mēs traversa cauri saistīts saraksts, atrast, kur piecas iet, un pēc tam ievietojiet to. 

Let 's lauzt šo leju un iet mazliet lēnāk. Es esmu gatavojas, lai norādītu uz kuģa. Tāpēc mums ir mūsu mezglu pieci ka mēs esam radīti mallocs. Kāpēc visi smejas? Just kidding. OK. Tāpēc mēs esam malloced pieci. Mēs esam izveidojuši šo mezglu kaut kur citur. Mums ir tā gatava iet. Mēs sākas priekšpusē mūsu sarakstu ar diviem. Un mēs gribam, lai ievietotu ar šķirotiem veidā. 

Tātad, ja mēs redzam divas, un mēs vēlamies, lai pieciem, ko mēs darām, kad mēs redzam kaut mazāk nekā mums? Kas? Mēs vēlamies, lai ievietotu piecas uz to saistīts saraksts, saglabājot to sakārtoti. Mēs redzam numuru divi. Tātad, ko mēs darām? Marcus? 

Mērķauditorija: Zvaniet rādītāju uz nākamo mezglu. 

Jason Hirschhorn: Un kāpēc mēs ejam uz nākamo? 

Mērķauditorija: Jo tas ir blakus mezglu sarakstā. Un mēs tikai zinām, ka citu vietu. 

Jason Hirschhorn: Bet piecas ir lielāks nekā divi, jo īpaši. Jo mēs gribam, lai saglabātu to sakārtoti. Tātad pieci ir lielāks nekā divi. Tāpēc mēs pāriet uz nākamo. Un tagad mēs sasniegtu četrus. Un kas notiek, kad mēs sasniegtu četrus? 

Five ir lielāka nekā četri. Tāpēc mēs turpinām iet. Un tagad mēs esam pie sešiem. Un ko mēs redzam sešos? Jā, Carlos? 

Mērķauditorija: Seši ir lielāks par pieciem. 

Jason Hirschhorn: Six ir lielāks par pieciem. Tātad, tas ir, ja mēs gribam ievietot pieci. Tomēr, paturiet prātā, ka, ja mēs ir tikai viens rādītājs šeit - tas ir mūsu papildus rādītājs, kas ir šķērso pa sarakstu. Un mēs esam norādot uz sešiem. Mēs esam zaudējuši līdzi tam, ko nāk pirms sešiem. Tātad, ja mēs gribam, lai ievietotu kaut ko par šis saraksts turot to sakārtoti, mēs iespējams, ir nepieciešams, cik daudz norādes? 

Mērķauditorija: Two. 

Jason Hiršhorns: Two. Viens sekot pašreizējā vienu un viens, lai sekotu iepriekšējais. Tas ir tikai atsevišķi saistīts saraksts. Tas tikai iet vienā virzienā. Ja mums būtu divkārt saistīts saraksts, kurā viss bija vērsta pret lietu pēc tam, un lieta pirms tam, tad mēs nebūtu nepieciešams to darīt. Bet šajā gadījumā mēs negribam zaudēt dziesmu par to, kas bija pirms mums, ja mums ir nepieciešams, lai ievietotu piecas kaut kur vidū. Saka, mēs bijām ievietojot deviņi. Kas notiktu, ja mēs saņēmām līdz astoņām? 

Mērķauditorija: Jūs ir iegūt šo null punktu. Tā vietā, null punktu jūs ir pievienot elementu, un tad ir tas norāda uz deviņiem. 

Jason Hiršhorns: Tieši tā. Tāpēc mēs astoņi. Mēs beigs sarakstā, jo tas norāda uz null. Un tagad, tā vietā, tas norāda uz null mēs esam tas norāda uz mūsu jauno mezglu. Un mēs noteikti rādītāju Mūsu jaunā mezglu null. Vai kāds ir kādi jautājumi par ievietošanu? Ko darīt, ja man nav rūp saglabājot sarakstu sakārtoti? 

Mērķauditorija: Stick to sākumā vai beigās. 

Jason Hiršhorns: Stick to sākums vai beigas. Kuriem viens mums vajadzētu darīt? Bobby? Kāpēc beigas? 

Mērķauditorija: Tā sākums jau ir aizpildīta. 

Jason Hiršhorns: OK. Sākums jau ir aizpildīta. Kurš vēlas iebilst pret Bobby. Marcus. 

Mērķauditorija: Nu, jūs, iespējams, vēlaties stick to sākumā, jo Citādi ir, ja jūs nodot to beigās jūs ir šķērsotu visu sarakstu. 

Jason Hiršhorns: Tieši tā. Tātad, ja mēs esam domājot par runtime, runtime ievietojot beigās būtu n, lielumu šajā. Kas ir liels O runtime ievietojot sākumā? Constant laiks. Tātad, ja jums nav jārūpējas par saglabājot kaut kas sakārtoti, ir daudz labāk, lai tikai ievietot sākumā šajā sarakstā. , Un kas var izdarīt konstantu laikā. 

OK. Nākošo darbību, ir atrast, kas cits - mēs esam formulēts to, kā meklēt. Bet mēs ejam, lai apskatīt caur saistīts saraksts kādu objektu. Jums puiši ir redzējuši kodu meklēt, pirms lekciju. Bet mēs veida vienkārši darīja to ar ievietot vai vismaz ievietojot kaut kas sakārtots. Jūs meklēt, izmantojot, iet mezglā ar mezglu, līdz jūs atrast numuru, kas jūs esat meklē. Kas notiek, ja jūs sasniedzat beigu saraksta? Teikt, es esmu meklē deviņus un I beigs sarakstā. Ko mēs darām? 

Mērķauditorija: atgriezties viltus? 

Jason Hiršhorns: Atgriešanās nepatiesa. Mēs neatradām to. Ja jūs sasniedzat beigām saraksta un Jums nav atrast numuru jūs esat meklē, tas nav tur. Kādi jautājumi par atrast? Ja tas bija sakārtoti sarakstu, kādi būtu būt atšķirīgs mūsu meklēšanu? Jā. 

Mērķauditorija: Tā varētu atrast pirmo vērtību , kas ir lielāks par vienu jūs meklējat, un tad atgriezties viltus. 

Jason Hiršhorns: Tieši tā. Tātad, ja tas ir sakārtots saraksts, ja mēs nokļūt kaut kas ir lielāks nekā tas, ko mēs meklējam, mums nav nepieciešams glabāt notiek pie saraksta beigās. Mēs varam tajā brīdī atgriezties viltus tāpēc, ka mēs nebrauksim, lai atrastu to. Jautājums tagad ir, mēs esam runājuši par saglabājot saistītos sarakstus sakārtoti, turot tos nešķiroti. Tas būs kaut kas jūs esat iespējams, nāksies domāt par kad kodēšanas problēma noteikti pieci, ja izvēlēties hash tabulu ar atsevišķu Ķēžu pieeja, kas mēs runājam par vēlāk. 

Bet tas ir tā vērts, lai saglabātu sarakstu jāšķiro un tad varēs varbūt būtu ātrāku meklēšanu? Vai tas ir labāk, lai ātri ievietotu kaut pastāvīgā runtime, bet tad ir garāks meklēšanu? Tas ir tradeoff labi tur, ka jums var izlemt, kas ir vairāk piemērots Jūsu konkrēto problēmu. Un tur ne vienmēr viens absolūti pareizā atbilde. Bet tas, protams, lēmums jūs saņemsiet veikt, un, iespējams, labi, lai aizstāvētu ka, teiksim, komentāru vai diviem, kāpēc Jūs izvēlaties vienu pār otru. 

Visbeidzot, dzēšot. Mēs esam redzējuši dzēšanu. Tas ir līdzīgi kā meklēt. Mēs meklējam elementa. Saka, mēs cenšamies, lai izdzēstu seši. Tāpēc mēs atrast seši šeit. Lieta, kas mums ir, lai pārliecinātos, ka mēs darīt, ir tas, ka viss, kas vērsta uz seši - kā mēs redzam soli divus uz leju šeit - kāds ir norādot uz sešiem vajadzībām, lai izlaist sešas tagad mainīt uz kāds seši ir vērsta uz. Mēs nevēlamies, lai kādreiz bāreņu pārējo Mūsu sarakstā aizmirstot noteikt, ka iepriekšējais rādītājs. Un tad dažreiz, atkarībā no par programmu, tie būs vienkārši dzēst šo mezglu pilnībā. Dažreiz jūs vēlaties, lai atgrieztos vērtība, kas ir šajā mezglā. Tātad tas, kā dzēst darbi. Visus jautājumus par dzēst? 

Mērķauditorija: Tātad, ja jūs gatavojas, lai izdzēstu tā, jūs vienkārši izmantot bez maksas, jo iespējams, tas tika malloced? 

Jason Hiršhorns: Ja jūs vēlaties, lai atbrīvotu kaut kas ir tieši labi, un jūs malloced to. Saka, mēs vēlējāmies, lai atgrieztu šo vērtību. Mēs varētu atgriezties sešu un tad bezmaksas šis mezgls un zvans bez maksas to. Vai mēs droši vien zvanīt bez pirmā un pēc tam atgriezties seši. 

OK. Tāpēc pieņemsim pāriet uz praksi kodēšanu. Mēs ejam, lai kodu trīs funkcijas. Pirmais sauc insert_node. Tātad jums ir kods, kas man pa e-pastu jums, un ja jūs skatoties šo vēlāk Jūs varat piekļūt kodu linked.c uz CS50 mājas lapā. Bet linked.c, tur ir daži skelets kodu, kas ir jau ir rakstīts par jums. Un tad tur ir pāris funkciju lietošana jums ir nepieciešams, lai rakstītu. 

Vispirms mēs ejam rakstīt insert_node. Un ko insert_node dara IS ievieto skaitli. Un jūs dodot veselam skaitlim uz saistītajā sarakstā. Un jo īpaši, jums ir nepieciešams lai saglabātu sarakstu sakārtoti no mazākā uz lielāko. Arī jūs nevēlaties ievietot jebkādus dublikātus. Visbeidzot, kā jūs varat redzēt insert_node atgriež bool. Tātad jūs vajadzēja, lai ļautu lietotājam uzzināt, vai nav ieliktnis bija veiksmīgi atgriežoties patiess vai nepatiess. Beigās šīs programmas - un šajā posmā nav nepieciešams jāuztraucas par atbrīvojot neko. Tātad, visi jūs darāt, ir veikt veselam skaitlim un tā ievietošanas sarakstā. 

Tas ir tas, ko es esmu lūdzot jums darīt tagad. Atkal, jo linked.c, kuru jūs visiem ir, ir skelets kodu. Un jums vajadzētu redzēt uz apakšu paraugs funkciju deklarācijas. Taču, pirms došanās uz kodēšanas to C, es ļoti iesakām jums iet izmantojot pasākumus, mēs esam bijuši praktizē katru nedēļu. Mēs jau esam izgājuši cauri priekšstatu par to. Tātad jums ir kāda izpratne par to, kā tas darbojas. Bet es aicinu jūs rakstīt daži pseudocode pirms niršanas collas Un mēs gatavojamies iet pa pseudocode kā grupa. Un tad, kad jūs esat rakstiski savu pseudocode, un, kad mēs esam rakstiski mūsu pseudocode kā grupa, jūs varat iedziļināties kodēšanas to C. 

Kā galvu uz augšu, insert_node funkcija ir iespējams sarežģītākajiem un Trīs mēs esam gatavojas rakstīt, jo es pievienoti daži papildu ierobežojumus, lai Jūsu programmēšana, jo īpaši, ka jūs neesat gatavojas, lai ievietotu kādu dublikātus un ka saraksts jāpaliek šķiroti. Tāpēc tas ir ne-trivial programmas kas jums ir nepieciešams kods. Un kāpēc jūs to 6:55 minūtes, tikai, lai iegūtu darbu pie pseudocode un kodu. Un tad mēs sāksim notiek kā grupa. Atkal, ja jums ir kādi jautājumi, tikai paceliet roku, un es atnākšu apkārt. . 

Mēs arī parasti dara tām - vai man nav skaidri pateikt jums var strādāt ar cilvēkiem. Bet, protams, es ļoti iesakām jums, Ja jums ir jautājumi, uzdot kaimiņš sēž blakus jums vai pat strādāt ar kādu cits, ja vēlaties. Tas nav jābūt individuāls klusa darbība. 

Sāksim ar rakstisku dažiem pseudocode uz kuģa. Kas var dot man pirmajā rindā pseudocode par šo programmu? Šo funkciju, bet - insert_node. Alden? 

Mērķauditorija: Tātad pirmā lieta, ko es darīju bija izveidot jaunu rādītāju uz mezglu un I inicializēta tas norāda uz to pašu lieta, ka saraksts ir vērsta uz. 

Jason Hiršhorns: OK. Tātad jūs veidojat jaunu rādītāju sarakstam, nevis mezglā. 

Mērķauditorija: Tieši tā. Jā. 

Jason Hiršhorns: OK. Un tad to, ko mēs vēlamies darīt? Kas pēc tam? Kas par mezglu? Mums nav mezglu. Mums vienkārši ir vērtība. Ja mēs gribam, lai ievietotu mezglu, ko mēs jādara vispirms, pirms mēs varam pat domāt par ievietojot to? 

Mērķauditorija: Ak, piedodiet. mums ir malloc telpu mezglā. 

Jason Hiršhorns: Excellent. Darīsim - OK. Nevar panākt, ka augstas. OK. Mēs ejam, lai iet uz leju, un pēc tam mēs izmantojam divas kolonnas. Es nevaru iet, ka - OK. Izveidot jaunu mezglu. Jūs varat izveidot citu rādītāju sarakstu vai arī varat vienkārši izmantot sarakstā, jo tā pastāv. Jums nav tiešām ir nepieciešams, lai to izdarītu. 

Tātad, mēs izveidot jaunu mezglu. Lieliski. Tas ir tas, ko mēs darām pirmo reizi. Ko tālāk? 

Mērķauditorija: Pagaidiet. Mums vajadzētu izveidot jaunu mezglu tagad vai mums vajadzētu gaidīt, lai pārliecinātos, ka tur nav dublikāti mezglā sarakstā, pirms mēs to izveidot? 

Jason Hiršhorns: Labs jautājums. Pieņemsim tur, ka vēlāk, jo lielāko daļu laika mēs būsim radot jaunu mezglu. Tāpēc mēs saglabātu, ka šeit. Bet tas ir labs jautājums. Ja mēs radām, un mēs redzam, dublikātu, ko vajadzētu mēs pirms atgriešanās? 

Mērķauditorija: Free to. 

Jason Hiršhorns: Jā. Iespējams atbrīvot to. OK. Ko mēs darām, kad mēs izveido jaunu mezglu? Annie? 

Mērķauditorija: Mēs ieliekam numurs mezglu? 

Jason Hiršhorns: Tieši tā. Mēs uzdodam numuru - mēs malloc telpu. Es esmu gatavojas atstāt, ka visi par vienu līniju. Bet tev taisnība. Mēs malloc telpu, un pēc tam mēs nodot numuru collas Mēs pat varam noteikt rādītāju daļa no tā ir null. Tas ir tieši labi. Un tad ko par to pēc tam? Mēs vērsa šo attēlu uz kuģa. Tātad, ko mēs darām? 

Mērķauditorija: Mēs ejam cauri sarakstam. 

Jason Hiršhorns: Iet cauri sarakstam. OK. Un ko mēs pārbaudīt katrā mezglā. Kurt, ko mēs pārbaudīt ne katru mezglu? 

Mērķauditorija: Skat, vai n vērtība ka mezgls ir lielāks par n vērtība Mūsu mezglā. 

Jason Hiršhorns: OK. Es esmu gatavojas darīt - jā, OK. Tātad, tas ir n - Es esmu gatavojas teikt, ja vērtība ir lielāka par šo mezglu, tad ko mēs darām? 

Mērķauditorija: Nu, tad mēs ievietotu lieta, tieši pirms tā. 

Jason Hiršhorns: OK. Tātad, ja tas ir lielāks par to, tad mēs gribam, lai ievietotu. Bet mēs gribam, lai ievietotu to tieši pirms tāpēc, ka mums arī būtu jābūt sekot, tad, par to, kas bija pirms tam. Tātad ievietot iepriekš. Tāpēc mēs, iespējams, kaut ko palaiduši garām agrāk. Mēs, iespējams, ir nepieciešams saglabāt līdzi, kas notiek. Bet mēs nokļūt atpakaļ tur. Tātad, kas vērtība ir mazāka nekā? Kurt, ko mēs darām, ja vērtība ir mazāka nekā? 

Mērķauditorija: Tad jūs tikai glabāt notiek ja vien tas ir pēdējais. 

Jason Hiršhorns: Man patīk, ka. Lai iet uz nākamo mezglu. Ja vien tas ir pēdējais - mēs, iespējams pārbaudīt, ka darba uzdevumā stāvoklī. Bet jā, blakus mezglā. Un tas kļūst pārāk zems, tāpēc mēs pāriet šeit. Bet, ja - var ikviens redzēt šo? Ja mēs esam vienāds, ko mēs darām? Ja vērtība, mēs cenšamies, lai ievietotu ir vienāds ar šo mezglu vērtības? Yeah? 

Mērķauditorija: [nedzirdama]. 

Jason Hiršhorns: Jā. Ņemot vērā šo - Marcus ir taisnība. Mēs varējām varbūt izdarīt kaut kas atšķirīgs. Bet, ņemot vērā, ka mēs esam izveidojuši, šeit mums vajadzētu atbrīvot un pēc tam atgriezties. Oh boy. Ir tas, ka labāk? Kā tas ir? OK. Bezmaksas un tad ko mēs atgriešanās, [dzirdams]? OK. Vai mēs trūkst kaut ko? Tātad, ja mēs sekotu iepriekšējas mezglu? 

Mērķauditorija: Es domāju, ka tas varētu iet pēc tam izveidot jaunu mezglu. 

Jason Hiršhorns: OK. Tāpēc sākumā mēs, iespējams - jā, mēs varam izveidot rādītāju uz jaunu mezglu, piemēram, iepriekšējā mezgla rādītājs un Pašreizējā mezglā rādītājs. Tā ļauj ievietot to šeit. Izveidot pašreizējā un iepriekšējā norādes uz mezgliem. Bet, kad mēs pielāgot šīs norādes? Kur mēs to darām kodu? Jeff? 

Mērķauditorija: - vērtības apstākļi? 

Jason Hiršhorns: Kura viens īpaši? 

Mērķauditorija: Es esmu tikai sajaukt. Ja vērtība ir lielāka nekā šajā mezglā, nav tas nozīmē, ka jūs vēlaties doties uz nākamo mezglu? 

Jason Hirschhorn: Tātad, ja mūsu vērtība ir lielāka nekā vērtība šajā mezglā. 

Mērķauditorija: Jā, tad jūs vēlaties, lai iet tālāk uz leju līniju, vai ne? 

Jason Hirschhorn: Right. Tāpēc mums nav ievietot to šeit. Ja vērtība ir mazāka par šo mezglā, tad mēs ejam uz nākamo mezglu - vai tad mēs ievietot iepriekš. 

Mērķauditorija: Pagaidiet, kas ir šī mezglu un kas ir vērtība? 

Jason Hirschhorn: Labs jautājums. Vērtība par šo funkciju definīcija ir tas, ko mēs esam dota. Tā vērtība ir skaitlis, mēs esam dota. Tātad, ja vērtība ir mazāka par šo mezglā, mums ir nepieciešams laiks, lai ievietotu. Ja vērtība ir lielāka nekā šajā mezglā, mēs ejam uz nākamo mezglu. Un atpakaļ uz sākotnējo jautājumu, lai gan, ja - 

Mērķauditorija: ja vērtība ir lielāka par šo mezglu. 

Jason Hirschhorn: Un tā Ko mēs darām šeit? Salds. Tas ir pareizi. Es esmu tikai gatavojas rakstīt atjaunināt norādes. Bet jā, ar pašreizējo jūs varētu atjaunot to norāda uz nākamo. Kaut kas cits, mēs esam trūkst? Tāpēc es esmu gatavojas rakstīt šo kodu gedit. Un, kamēr es to izdarītu, jums var būt pāris minūtes, lai strādā uz kodēšanu tas C. 

Tāpēc man ir ievadi pseudocode. Quick piezīmi, pirms mēs sāktu. Mums var nebūt spējīgs pilnīgi pabeigt to visu Trīs no šīm funkcijām. Ir pareizi risinājumus tām ka es e-pastu, lai jums puiši pēc iedaļas, un tas būs publicēta CS50.net. Tāpēc es nedomāju, iesakām jums iet apskatīt sadaļās. Es aicinu jūs izmēģināt šo par savu pieder, un pēc tam izmantot šo praksi problēmas, lai pārbaudītu savas atbildes. Tie visi ir paredzēti, lai rūpīgi attiecas uz un ievērot to, kas jums jādara, par problēmu kopumu. Tāpēc es aicinu jūs praktizēt šo par savu un pēc tam izmantot šo kodu, lai pārbaudīt jūsu atbildes. Tāpēc, ka es vēlos, lai pārietu uz hash galdi kādā brīdī sadaļā. Lai mēs varētu saņemt caur to visu. Bet mēs darīsim, cik mēs varam tagad. 

OK. Ļaujiet mums sākas. Asam, kā mēs izveidot jaunu mezglu? 

Mērķauditorija: Jūs struct *. 

Jason Hirschhorn: Tātad mums ir, ka šeit. Ak, piedodiet. Jūs sakot struct *. 

Mērķauditorija: Un tad [? kind?] mezgla vai c mezglu. 

Jason Hirschhorn: OK. Es esmu gatavojas to nosaukt new_node lai mēs varētu palikt konsekventa. 

Mērķauditorija: Un jūs vēlaties, lai noteiktu, ka uz galvas, pirmo mezglu. 

Jason Hirschhorn: OK. Tāpēc tagad tas norādot to - tā tas nav izveidojusi jaunu mezglu vēl. Tas ir tikai norādot uz pirmā mezgla sarakstā. Kā es varu izveidot jaunu mezglu? Ja man ir nepieciešama vieta, lai izveidotu jaunu mezglu. Malloc. Un cik liels? 

Mērķauditorija: no struktūrai lieluma. 

Jason Hirschhorn: izmērs struktūrai. Un to, kas struktūrai sauc? 

Mērķauditorija: Mezgls? 

Jason Hirschhorn: Node. Tāpēc malloc (sizeof (mezgls)); dod mums telpu. Un tas ir līnija - viena lieta ir nepareizs šajā pozīcijā. Ir new_node rādītāju uz struct? Tas ir sugas vārds. Kas tas ir - mezglā, tieši tā. Tas ir mezglā *. Un ko mēs darām uzreiz pēc mēs malloc kaut ko, Asan? Kas ir pirmā lieta, ko mēs darām? Ko darīt, ja tas nedarbojas? 

Mērķauditorija: Ak, pārbaudiet, vai tas norāda uz mezglu? 

Jason Hirschhorn: Tieši tā. Tātad, ja jūs new_node vienāds vienāds null, ko mēs darām? Tas atgriež bool, šo funkciju. Tieši tā. Izskatās labi. Jebkas, lai pievienotu tur? Mēs pievienot lietas beigās. Bet tas līdz šim izskatās labi. Izveidot pašreizējo un iepriekšējās norādes. Michael, kā es varu darīt? 

Mērķauditorija: Jums būtu darīt mezglu *. Jūs ir veikt vienu nav par new_node bet mezgli mums jau ir. 

Jason Hirschhorn: OK. Tātad pašreizējā mezglu mēs esam par. Es aicinu šo Valūta. Labi. Mēs esam nolēmuši, mēs gribam, lai saglabātu divi, jo mums ir nepieciešams zināt kas ir pirms tā. Ko viņiem inicializēts? 

Mērķauditorija: To vērtība mūsu sarakstā. 

Jason Hirschhorn: Tātad, kas ir Pirmā lieta, mūsu sarakstā? Vai to, kā mēs zinām, kur sākumā mūsu sarakstā? 

Mērķauditorija: Vai nav pagājis funkcijā? 

Jason Hirschhorn: Right. Tas tika pieņemts tieši šeit. Tātad, ja tas ir pagājis uz funkciju, sākums saraksta, ko mums vajadzētu noteikt strāvas stiprums? 

Mērķauditorija: List. 

Jason Hirschhorn: List. Tas ir tieši labi. Tagad tas ir adresi sākums mūsu saraksta. Un ko par iepriekšējo? 

Mērķauditorija: List mīnus viens? 

Jason Hirschhorn: Ir nekas pirms tam. Tātad, ko mēs varam darīt, lai neizsaka neko? 

Mērķauditorija: Null. 

Jason Hirschhorn: Jā. Tas izklausās kā laba ideja. Perfekta. Paldies. Iet cauri sarakstam. Konstantīns, cik ilgi mēs iet cauri sarakstam? 

Mērķauditorija: kamēr mēs sasniegt null. 

Jason Hirschhorn: OK. Tātad, ja, bet, lai cilpa. Ko mēs darām? 

Mērķauditorija: Varbūt par cilpu? 

Jason Hirschhorn: Darīsim par cilpu. OK. 

Mērķauditorija: Un mēs teiksim - līdz kārtējā rādītājs nav vienāds ar nulli. 

Jason Hirschhorn: Tātad, ja mēs zinām, stāvoklis, kā mēs varam rakstīt cilpu pamatojoties off šis nosacījums. Kādu cilpas mums vajadzētu izmantot? 

Mērķauditorija: gan. 

Jason Hirschhorn: Jā. Tas padara daudz nozīmē, pamatojoties off to, ko jūs teicāt. Ja mēs vienkārši vēlamies, lai dotos uz mums tas būtu tikai zinu, ka lieta, tas padarītu jēga to darīt, kamēr cilpa. Kaut arī pašreizējais nav vienāda null, ja vērtība ir mazāka par šo mezglā. Akshar, dod man šo līniju. 

Mērķauditorija: Ja pašreizējā-> n n ir mazāks par vērtību. Vai mainīt to. Slēdzis, kas grupā. 

Jason Hirschhorn: Sorry. 

Mērķauditorija: Mainīt kronšteinu. 

Jason Hirschhorn: Tātad, ja tas ir pārsniedz vērtību. Jo tas ir mulsinoši ar komentēt iepriekš, es esmu gatavojas darīt. Bet jā. Ja mūsu vērtība ir mazāka par šo mezglā, ko mēs darām? Oh. Man ir taisnība šeit. Ievietot iepriekš. OK. Kā mēs to darām? 

Mērķauditorija: Vai tā joprojām mani? 

Jason Hirschhorn: Jā. 

Mērķauditorija: You - new_node-> nākamo. 

Jason Hirschhorn: Tātad, kas ir kas notiek, lai ir vienādi? 

Mērķauditorija: Tas būs vienāda strāvu. 

Jason Hirschhorn: Tieši tā. Un tā otra - ko vēl mums ir nepieciešams, lai atjauninātu? 

Mērķauditorija: Pārbaudiet, vai pagātnes vienāds null. 

Jason Hirschhorn: Ja prev - tāpēc, ja iepriekšējais vienāds null. 

Mērķauditorija: Tas nozīmē, ka tas notiek kļūt galvu. 

Jason Hirschhorn: Tas nozīmē tas ir kļuvis galvu. Tātad, ko mēs darām? 

Mērķauditorija: Mēs galvu vienāds new_node. 

Jason Hirschhorn: Head vienāds new_node. Un kāpēc galvu šeit, nav sarakstā? 

Mērķauditorija: Tāpēc, ka galva ir globāla mainīgais, kas ir sākuma vietā. 

Jason Hirschhorn: Sweet. OK. Un - 

Mērķauditorija: Tad jūs vēl prev-> Nākamais vienāds new_node. Un tad jūs atpakaļ taisnība. 

Jason Hirschhorn: Kur mēs noteikti new_node beigām? 

Mērķauditorija: Es gribētu - Es noteikts, ka sākumā. 

Jason Hirschhorn: Tātad, ko līnijas? 

Mērķauditorija: Pēc ja paziņojums pārbaudīt, ja tas ir zināms. 

Jason Hirschhorn: Tieši šeit? 

Mērķauditorija: es gribētu darīt new_node-> n vienāds ar vērtību. 

Jason Hirschhorn: Izklausās labi. Iespējams, tas ir jēga - mums nav ir nepieciešams zināt, ko sarakstu mēs esam par jo mēs esam tikai nodarbojas ar vienu sarakstu. Tāpēc labāk funkcija deklarācija Tas ir tikai, lai atbrīvotos no šīs pilnīgi un tikai ievietot vērtība uz galvas. Mums pat nav nepieciešams zināt ko sarakstā mēs esam iekšā Bet es turpinās to tagad tad mainīt to uz atjaunināšanu slaidus un kods. Tā, ka izskatās labi tagad. Ja vērtības - kas var darīt šo līniju? Ja - Ko mēs darām šeit, Noah. 

Mērķauditorija: ja vērtība ir lielāka nekā Valūta-> n - 

Jason Hirschhorn: Kā mēs ejam uz nākamo mezglu? 

Mērķauditorija: Valūta-> n vienāds ar new_node. 

Jason Hirschhorn: So n kāda daļa no struct? Skaitlim. Un new_node ir rādītājs uz mezglu. Tātad, kāda daļa no Augstākais mums vajadzētu atjaunināt? Ja nav n, tad kāda no otras puses? Noah, kas ir otra daļa. 

Mērķauditorija: Ak, nākamais. 

Jason Hirschhorn: Next, tieši tā. Tieši tā. Nākamais ir pareizais. Un ko vēl mums vajag atjaunināt, Noah? 

Mērķauditorija: The norādes. 

Jason Hirschhorn: So mēs atjaunināts strāvu. 

Mērķauditorija: Iepriekšējā-> nākamo. 

Jason Hirschhorn: Jā. Labi, mēs pauze. Kas var palīdzēt mums šeit? Manu, ko mums vajadzētu darīt? 

Mērķauditorija: Tev iestatīt tas ir vienāds ar Augstākais-> nākamo. Bet to, ka pirms iepriekšējās rindas. 

Jason Hirschhorn: OK. Kaut kas cits? Akshar. 

Mērķauditorija: Es nedomāju, ka tu esi paredzēts mainīt Augstākais-> nākamo. Es domāju, ka jūs domāts darīt Valūta vienāds Valūta-> blakus, lai dotos uz nākamo mezglu. 

Jason Hirschhorn: Tik žēl, ja? Uz kāda line? Šī līnija? 

Mērķauditorija: Jā. Padarīt Valūta vienāds Valūta-> nākamo. 

Jason Hirschhorn: Tātad tas ir pareizs tāpēc, ka strāva ir rādītāju uz mezglu. Un mēs gribam, lai norādītu uz nākamo mezgla, kas kļūst pašlaik norādīja uz. Valūta pati ir blakus. Bet, ja mēs atjaunināt curr.next, mēs būtu atjaunināt faktisko piezīmi pati, nevis tur, kur tas rādītājs bija vērsta. Ko par šo līniju, though. Avi? 

Mērķauditorija: Iepriekšējā-> next vienāds Valūta. 

Jason Hirschhorn: Tātad vēlreiz, ja iepriekšējais ir rādītāju uz mezglu, iepriekšēja-> next ir faktiskais rādītājs mezglu. Tāpēc tas būtu atjaunināšana Rādītājs mezglā līdz Valūta. Mēs nevēlamies, lai atjauninātu rādītājs kādā mezglā. Mēs vēlamies, lai atjauninātu iepriekšējā. Tātad, kā mēs to darām? 

Mērķauditorija: Tas vienkārši prev. 

Jason Hirschhorn: Right. Iepriekšējā ir pointers uz mezglu. Tagad mēs esam mainot to jaunu rādītāju uz mezglu. OK Ļaujiet mums virzīties uz leju. Visbeidzot, šis pēdējais nosacījums. Jeff, ko mēs darām šeit? 

Mērķauditorija: Ja vērtība ir vienāds ar Curr-> n. 

Jason Hirschhorn: Sorry. Ak, mans Dievs. Kas? Vērtība == Valūta-> n. Ko mēs darām? 

Mērķauditorija: Jūs vēlaties atbrīvot mūsu new_node, un tad jūs atgriezties viltus. 

Jason Hirschhorn: Tas ir tas, ko Līdz šim mēs esam uzrakstījuši. Vai kāds ir kaut ko pievienot pirms mēs? OK. Mēģināsim to. Kontrole var sasniegt beigām of a non-neesošu funkciju. Avi, kas notiek? 

Mērķauditorija: Vai jūs vajadzēja likt atgriešanos taisnība ārpus kamēr cilpa? 

Jason Hirschhorn: Es nezinu. Vai jūs vēlaties, lai es? 

Mērķauditorija: Nekad prātā. Nē. 

Jason Hirschhorn: Akshar? 

Mērķauditorija: Es domāju, ka jums nozīmē likts atgriezties viltus beigās un kamēr cilpa. 

Jason Hirschhorn: Tātad, ja Vai jūs vēlaties, lai tas iet? 

Mērķauditorija: Tāpat ārpus kamēr cilpa. Tātad, ja jūs izejat no kamēr cilpa, kas nozīmē ka jūs esat sasnieguši un nekas nav noticis. 

Jason Hirschhorn: OK. Tātad, ko mēs darām šeit? 

Mērķauditorija: Tu atgriezties viltus tur, kā labi. 

Jason Hirschhorn: Ak, mēs darīt to abās vietās? 

Mērķauditorija: Jā. 

Jason Hirschhorn: OK. Vai mēs ejam? Ak, mans Dievs. Piedod. Es atvainojos par ekrāna. Tas ir sava veida freaking out uz mums. Tāpēc izvēlēties iespēju. Nulle, vienu kodu, iziet no programmas. Viens ievieto kaut ko. Pieņemsim ievietot trīs. Iekļaut nebija veiksmīga. Es esmu gatavojas izdrukāt. Man nav neko. OK. Varbūt, ka bija tikai parazīts. Ievietojiet vienu. Nav veiksmīga. OK. Pieņemsim palaist caur gdb tiešām ātri lai pārbaudītu, kas notiek. 

Atcerieties gdb. / Nosaukums jūsu Programma izpaužas mūs gdb. Ir tas, ka daudz, lai rīkotos? Mirgo? Droši vien. Aizveriet acis, un veikt dažas dziļas breaths, ja jums ir apnicis skatoties uz to. Es esmu gdb. Kas ir pirmā lieta, ko es darīt gdb? Mēs esam ieguvuši, lai noskaidrotu kas notiek šeit. Paskatīsimies. Mums ir sešas minūtes, lai skaitlis to, kas notiek. Break galvenais. Un tad ko man darīt? Carlos? Palaist. OK. Pieņemsim izvēlēties iespēju. Un ko N darīt? Nākamais. Jā. 

Mērķauditorija: Vai tad jūs pieminēt - nav jūs sakāt, ka galva, tas bija inicializēts ar nulli sākumā. Bet es domāju, jūs teicāt, ka bija OK. 

Jason Hirschhorn: Iesim - aplūkosim gdb, un tad mēs brauksim atpakaļ. Bet tas izklausās kā jums jau ir dažas idejas par to, kas notiek. Tāpēc mēs vēlamies, lai ievietotu kaut ko. OK. Mēs esam ievietot. Ievadiet int. Mēs ievietot trīs. Un tad es esmu uz šīs līnijas. Kā es varu iet sākt atkļūdošanu ieliktnis zināma funkcija? Ak, mans Dievs. Tas ir daudz. Vai tas ir freaking daudz? 

Mērķauditorija: Ak, tas nomira. 

Jason Hirschhorn: Es tikko izvilka to ārā. OK. 

Mērķauditorija: Varbūt tas ir otrs gals stieples. 

Jason Hirschhorn: Wow. Tā apakšējā līnija - ko tu teici? 

Mērķauditorija: Es teicu ironija tehnisko grūtības šajā klasē. 

Jason Hirschhorn: Es zinu. Ja vien man būtu kontrole pār šo daļu. [Dzirdams] Tas izklausās lieliski. Kāpēc jūs puiši sāk domāt par tas, ko mēs varētu darīt nepareizi, un mēs būsim atpakaļ 90 sekundes. 

Avica, es esmu gatavojas lūgt jums to, kā iet iekšā insert_node atkļūdot to. Tātad, tas ir, ja mēs pēdējā left off. Kā es varu iet iekšā insert_node, Avica, pārbaudīt, kas notiek? Kas GDB komandu? Pārtraukums neņemtu mani iekšā. Vai Marquise zināt? 

Mērķauditorija: Kas? 

Jason Hirschhorn: Kas GDB komandu Es izmantoju iet iekšā šo funkciju? 

Mērķauditorija: Step? 

Jason Hirschhorn: Soli pa S. Tā ņem mani iekšā. OK. New_node mallocing dažas vietas. Tas viss izskatās tā būs. Aplūkosim new_node. Tā ieguva dažas atmiņas adresi. Pieņemsim pārbaudīt - tas ir visu pareizi. Tāpēc viss šeit šķiet strādā pareizi. 

Mērķauditorija: Kāda ir atšķirība starp P un displeju? 

Jason Hirschhorn: P apzīmē izdrukāt. Un tā jūs esat jautā, kas ir Atšķirība starp šo un šo? Šajā gadījumā nekas. Bet kopumā ir dažas atšķirības. Un jums vajadzētu meklēt, kas GDB rokasgrāmatā. Taču šajā gadījumā nekas. Mums ir tendence izmantot drukāt, lai gan, jo mums nav jādara daudz vairāk, nekā drukāt vienu vērtību. 

OK. Tātad mēs esam on line 80 mūsu kodu, Nosakot mezglu * Valūta vienāds ar sarakstu. Ļaujiet mums izdrukāt Valūta. Tas ir vienāds ar sarakstu. Salds. Gaidīt. Tas ir vienāds ar kaut ko. Tas nešķiet pareizi. Tur mēs ejam. Tas ir tāpēc, ka gdb, labi, ja tas ir līnija jūs par to vēl nav izpildīts. Tātad jums ir nepieciešams, lai faktiski rakstīt blakus izpildīt līniju pirms redzēt savus rezultātus. Tāpēc šeit mēs esam. Mēs tikko izpildīts šo līniju, iepriekšējā vienāds null. Tātad vēlreiz, ja mēs drukāt iepriekšējā mēs neredzam neko dīvainu. Bet, ja mēs faktiski izpildīt ka līniju, tad mēs redzēsim ka šī līnija strādāja. 

Tāpēc mēs esam Valūta. Tie ir gan labi. Tiesības? Tagad mēs esam uz šīs līnijas šeit. Bet Valūta nav vienāda null. Nu, ko tas Valūta vienāds? Mēs tikko redzējām to sastādīja null. Mēs drukāts to ārā. Es to izdrukāt vēlreiz. Tā ir, ka, kamēr cilpa gatavojas izpildīt? 

Mērķauditorija: Nē. 

Jason Hirschhorn: Tad, kad es drukāti, ka line, jūs redzat, mēs jumped visu ceļu uz leju, uz leju, atgriezties viltus. Un tad mēs spēsim atgriezties viltus un doties atpakaļ uz mūsu programmu un beidzot izdrukāt, kā mēs redzējām, ieliktnis nebija veiksmīga. Tātad, kāds ir kādas idejas par to, ko mums ir jādara, lai atrisinātu šo? Es esmu gatavojas gaidīt, kamēr es redzu pāris rokas iet uz augšu. Mēs neesam izpildīt to. Paturiet prātā, tas bija pirmais lieta, ko mēs darām. Es neesmu gatavojas darīt pāris. Es esmu gatavojas darīt dažas. Tāpēc, ka pāris ir divi. Es jāgaida vairāk nekā divi. 

Pirmais ievietošanas, Valūta, pēc noklusējuma ir vienāds null. Un tas cilpa tikai izpilda ja Valūta nav null. Tātad, kā es varu saņemt ap šo? Es redzu trīs rokas. Es jāgaida vairāk nekā trīs. Marcus, ko jūs domājat? 

Mērķauditorija: Nu, ja jums ir nepieciešams, lai izpildīt vairāk nekā vienu reizi, jūs vienkārši mainīt to ar do-kamēr cilpa. 

Jason Hirschhorn: OK. Vai tas atrisinātu mūsu problēmu, lai gan? 

AUDITORIJA: Tādā gadījumā, jo tas, ka saraksts ir tukšs. Tā, tad jums, iespējams, ir nepieciešams, lai pievienotu apgalvojums, ka, ja cilpa izejām tad ir jābūt beigās sarakstu, kurā brīdī jums var vienkārši ievietot to. 

Jason Hirschhorn: Man patīk, ka. Tas ir jēga. Ja cilpa izejām - jo tas būs atgriezties viltus šeit. Tātad, ja cilpas izeju, tad mēs esam pie beigu saraksta, vai varbūt sākums saraksta, ja tur nekas tā, kas ir tāds pats kā beigās. Tāpēc tagad mēs vēlamies, lai ievietotu kaut ko šeit. Tā kā tas, ka kods izskatās, Marcus? 

Mērķauditorija: Ja jūs jau got mezglu malloced, jūs varētu vienkārši pateikt new_node-> next vienāds ar null, jo tai jābūt beigās. Vai new_node-> next vienāds null. 

Jason Hirschhorn: OK. Piedodiet. New_node-> next vienāds null jo mēs esam beigās. Tas nenozīmē, ka likt to iekšā Kā mēs ieliekam to sarakstā? Tiesības. Tas ir vienkārši, nosakot to vienāds ar. Nē, kā mēs patiesībā likt to sarakstā? Kas norāda uz beigu saraksta? 

Mērķauditorija: Head. 

Jason Hirschhorn: Sorry? 

Mērķauditorija: Head ir vērsta līdz saraksta beigām. 

Jason Hirschhorn: Ja tur nekas sarakstu, galva ir vērsta uz end of sarakstā. Tā, ka būs darbs pirmās ievietošanas. Kas par to, ja ir pāris lietas sarakstā? Nekā mēs nevēlamies, lai uzstādītu dodies vienāds ar new_node. Ko mēs vēlamies darīt tur? Yeah? Droši vien iepriekšējā. Būs, kas strādā? Atgādināt, ka iepriekšējais ir tikai rādītāju uz mezglu. Un iepriekšējo ir vietējā mainīgs. Tāpēc šī līnija būs noteikt vietējās mainīgais, Iepriekšējā, kas vienāds ar vai norādot uz šo jauno mezglu. Tas faktiski nav nodot to mūsu sarakstā, though. Kā mēs ieliekam to mūsu sarakstā? Akchar? 

Mērķauditorija: Es domāju, ka jūs Pašreizējās-> nākamo. 

Jason Hirschhorn: OK. Valūta-> nākamo. Tātad vēlreiz, vienīgais iemesls, kāpēc mēs esam uz leju šeit ir, ko dara strāvas stiprums? 

Mērķauditorija: Vienāds null. 

Jason Hirschhorn: Un tā, ko notiek, ja mēs null-> tālāk? Ko mēs gatavojas saņemt? Mēs iegūt segmentāciju vaina. 

Mērķauditorija: Vai Valūta vienāds null. 

Jason Hirschhorn: Tas ir tas pats kā prev, lai gan, jo tur ir vietējās mainīgais mēs nosakot ir vienāds ar šo jauno mezglu. Iesim atpakaļ uz mūsu priekšstatu ievietot kaut ko. Saka, ka mēs esam ievietojot beigās no saraksta, lai tieši šeit. Mums ir pašreizējais rādītājs, kas ir norāda uz spēku iepriekšējo punktu kas ir vērsta uz 8. Tātad, kas mums ir nepieciešams, lai atjauninātu, Avi? 

Mērķauditorija: Iepriekšējā-> next? 

Jason Hirschhorn: Iepriekšējā-> nākamais ir tas, ko mēs vēlamies atjaunot, jo tas faktiski ievietojiet to beigu saraksta. Mums joprojām ir viens bug, lai gan, ka mēs ejam uzskriet. Kas tas tāds bug? Yeah? 

Mērķauditorija: Tas notiek, lai atgrieztos viltus šajā gadījumā? 

Jason Hirschhorn: Ak, tas ir gatavojas atgriezties viltus. Bet tur ir vēl viens bug. Tāpēc mums būs nepieciešams, lai pretī patiesai. 

Mērķauditorija: Vai iepriekšējā joprojām ir vienāds null augšpusē saraksta? 

Jason Hirschhorn: Tātad iepriekšējais vēl vienāds null pašā sākumā. Tātad, kā mēs varam iegūt vairāk nekā, ka? Yeah? 

Mērķauditorija: Es domāju, ka jūs varat darīt, pārbaudi pirms kamēr cilpa, lai redzētu, vai tas ir tukša sarakstā. 

Jason Hirschhorn: OK. Tāpēc iesim šeit. Do pārbaudi. Ja - 

Mērķauditorija: Tātad, ja galva vienāds vienāds null. 

Jason Hirschhorn: Ja galva vienāds vienāds null - kas jums pateiks mums, ja tā ir tukša sarakstā. 

Mērķauditorija: Un tad jūs do galva vienāds jauns. 

Jason Hirschhorn: Head vienāds new_node? Un ko vēl mums jādara? 

Mērķauditorija: Un tad jūs atpakaļ taisnība. 

Jason Hirschhorn: Ne gluži. Mēs esam trūkst vienu soli. 

Mērķauditorija: New_node next ir norādīt uz null. 

Jason Hirschhorn: Tieši tā, Alden. Un tad mēs varam atgriezties true. OK. Bet tas joprojām ir laba ideja darīt lietas beigās saraksta, labi? Labi. Mēs joprojām varētu faktiski nokļūt līdz saraksta beigām. Tātad tas ir kods, labi, ja mēs esam pie saraksta beigās, un ir daži lietas sarakstā? Tiesības? Tāpēc, ka mums vēl ir Marcus ideju. Mēs varētu iziet šo cilpu, jo mēs beigās sarakstā. Tāpēc mēs joprojām vēlamies, lai šī kodu šeit lejā? 

Mērķauditorija: Jā. 

Jason Hirschhorn: Jā. Un ko mums vajag, lai mainītu šo? Taisnība. Vai, ka pareizai labi visiem līdz šim? Kāds ir jebkurš - Avi, jums ir ko piebilst? 

Mērķauditorija: Nē. 

Jason Hirschhorn: OK. Tātad mēs esam veikuši pāris izmaiņas. Mēs esam padarījuši šo pārbaudi, pirms mēs devos uz tukšu sarakstu. Tāpēc mēs esam parūpējušies par tukšu sarakstu. Un šeit mēs rūpējās ievietojot kaut beigās sarakstā. Tāpēc šķiet, piemēram, šo, bet cilpas uzņemšanos aprūpe lietas starp, kaut sarakstā, ja ir lietas sarakstā. 

OK. Ļaujiet mums vadīt šo programmu vēlreiz. Nav veiksmīga. 

Mērķauditorija: Jums nav darīt to. 

Jason Hirschhorn: Ak, Man nebija darīt to. Labs punkts, Michael. Pieņemsim pievienot marku saistīts. Līnija 87, tur ir kļūda. Līnija 87. Alden, tas bija līnija jūs man iedeva. Kas ir nepareizi? 

Mērķauditorija: Ir jābūt null. 

Jason Hirschhorn: Excellent. Tieši labi. Tas būtu nulle. Veidosim vēlreiz. Sastādīt. OK. Pieņemsim ievietot trīs. Iekļaut bija veiksmīga. Let 's to izdrukāt. Ak, ja vien mēs varētu pārbaudīt. Bet mēs neesam darījuši drukāt funkcija vēl. Pieņemsim ievadiet kaut ko citu. Ko mums vajadzētu ieiet? 

Mērķauditorija: Seven. 

Jason Hirschhorn: Seven? 

Mērķauditorija: Jā. 

Jason Hirschhorn: Mums ir seg vaina. Tāpēc mums ir viens, bet mēs skaidri nevar saņemt divus. Tas ir 05:07. Lai mēs varētu atkļūdot šo trīs minūtes. Bet es esmu gatavojas atstāt mums šeit un pāriet uz hash tabulas. Bet atkal, atbildes uz šo kodu Es e-pastu to jums mazliet. Mēs esam ļoti tuvu tai. Es ļoti aicinu jūs, lai noskaidrotu kas notiek šeit un salabot. Tāpēc es e-pastu jums šo kodu, labi plus risinājums - iespējams risinājums vēlāk. Pirmais šo kodu. 

Otra lieta, ko es gribu darīt, pirms mēs apdare ir, mēs neesam atbrīvojušies neko. Tāpēc es vēlos, lai parādītu Jums to, ko Valgrind izskatās. Ja mēs palaist Valgrind robežas mūsu programmas. / saistītas. Again, saskaņā ar šo slide, mēs vajadzētu palaist Valgrind ar kaut kāda veida variants, šajā gadījumā - Noplūdes pārbaude = pilna. Tā ļauj rakstīt Valgrind - Noplūdes pārbaude = pilna. Tāpēc tas darbosies Valgrind mūsu programmā. Un tagad programma faktiski darbojas. Tātad, mēs ejam, lai palaistu to, tāpat kā pirms kaut ko iekšā Es esmu gatavojas īstenot trīs. , Kas darbojas. Es neesmu gatavojas izmēģināt, lai kaut citur, jo mēs gatavojamies iegūt seg nepatiesas šajā lietā. Tāpēc es esmu tikai gatavojas atmest. 

Un tagad jūs redzat šeit lejā noplūdes un kaudze kopsavilkums. Tās ir labas lietas, kas vēlaties pārbaudīt out. Tāpēc kaudze kopsavilkums - tā saka, lietošanas pie izejas - astoņi biti vienā blokā. Ka viens bloks ir mezglā mēs malloced. Michael, jūs teicāt, pirms mezgls ir astoņi kodumi, jo tā ir vesels skaitlis un rādītāju. Tātad tas ir mūsu mezglā. Un tad saka, ka mēs izmantojām malloc septiņas reizes, un mēs atbrīvojušies kaut sešas reizes. Bet mēs nekad sauc brīva, tāpēc man nav Nesaprotu, par ko tas runā. 

Bet pietiek pateikt, ka tad, kad jūsu programma darbojas, malloc tiek saukta dažās citās vietās, kas mums nav jāuztraucas par. Tāpēc malloc bija iespējams saukt dažās vietās. Mums nav jāuztraucas, ja. Bet tas ir patiešām mums. Šī pirmā līnija ir mums. Mēs atstājām šo bloku. Un jūs varat redzēt, ka šeit ar noplūdes kopsavilkumā. Still sasniedzams - astoņi biti vienā blokā. Tas nozīmē, ka atmiņa - mums ir noplūdis šo atmiņu. Galīgi zaudējis - kaut kas ir zaudēti par labu. Vispār, jums nav redzēt kaut ko tur. Joprojām sasniedzams parasti, ja jūs redzēsiet lietas, kur jūs vēlaties meklēt, lai redzētu, kas kods, jums būtu ir atbrīvoti, bet jūs aizmirsāt, lai atbrīvotu. 

Un tad, ja tas nav gadījums, ja mēs darījām bez visu, mēs varam pārbaudīt, ka. Pieņemsim tikai palaist programmu nevis liekot neko. Jūs redzēsiet noteikti šeit lietošanai pie izejas - nulles baiti nulles blokiem. Tas nozīmē, ka mums bija nekas pa kreisi kad šī programma izbrauc. Tātad, pirms pagrieziena pset6, palaist Valgrind un pārliecinieties, ka jums nav kāda atmiņas noplūde jūsu programmā. Ja Jums ir kādi jautājumi ar Valgrind, justies brīvi aizsniegt. Bet tas ir, kā jūs to izmantot. Ļoti vienkārši - redzēt, ja jūs ir izmanto pie izejas - kādi baiti jebkuriem blokiem. 

Tāpēc mēs strādājam pie ievietot mezglā. Man bija divas citas funkcijas šeit - drukāt mezglu un bezmaksas mezgliem. Atkal, tās ir funkcijas, kas būs labi, lai jūs varētu praksē jo tās palīdzēs jums ne tikai šīs izlases vingrinājumi, bet arī uz problēmu komplektu. Viņi kartē diezgan cieši, lai lietas jūs nāksies darīt problēma noteikti. Bet es gribu, lai pārliecinātos, ka mēs pieskarties par visu. Un hash tabulas ir arī ļoti svarīgi, lai tas, ko mēs darām sadaļā šajā nedēļa - vai problēmu kopumu. 

Tātad, mēs ejam, lai pabeigtu sadaļu runājot par hash tabulas. Ja jūs novērojat es maz hash tabulu. Tas nav tas, ko mēs runājam par, tomēr. Mēs runājam par atšķirīgu hash tabulas veidu. Un tās kodols, hash tabulas ir nekas vairāk kā masīvs plus hash funkciju. Mēs ejam runāt mazliet tikai pārliecinieties, vai visi saprot to, ko hash funkcija. Un es jums saku tagad, ka tas ir nekas vairāk par divām lietām - masīvs un hash funkciju. Un šeit ir pasākumus, izmantojot kas tas darbojas. 

Tur ir mūsu masīvs. Tur ir mūsu funkcija. Jo īpaši, hash funkciju nepieciešams darīt pāris lietas ar to. Es esmu gatavojas runāt konkrēti par šo problēmu noteikti. Tas ir iespējams, gatavojas veikt virkni. Un to, kas tas notiek, lai atgrieztos? Kādi datu tips? Alden? Jūsu hash funkciju atgriezties? Skaitlis. Tātad šis ir tas, ko hash tabula sastāv no - tabula formā masīva un hash funkciju. Kā tas darbojas? Tas darbojas trīs posmos. Mēs to atslēgu. Šajā gadījumā, mēs arī tā virkni. Mēs aicinām hash funkciju par vienu soli par atslēgu, un mēs iegūstam vērtību. 

Konkrētāk, mēs sakām mēs iegūstam skaitli. Ka vesels skaitlis, ir ļoti specifiski ierobežojumi, ko tas skaitlis varētu būt. Šajā piemērā, mūsu masīvs ir lieluma trīs. Tātad, kādi skaitļi var ka skaitlis būt. Kas ir diapazons derīgo vērtībām ka skaitlis, atgriešanās tips ar šo hash funkcija? Nulle, viens un divi. No hash funkciju punkts ir izrēķināt vietu masīvā kur mūsu galvenais notiek. Ir tikai trīs iespējas vietas šeit - nulle, viens vai divi. Tāpēc šī funkcija labāk atgriešanās nulle, viens vai divi. Daži derīgi Indice šajā masīvā. 

Un tad, atkarībā no tā, kur tas atgriežas, Jūs varat redzēt, tur masīvs atvērts Bracket vērtību. Tas ir, ja mēs ieliekam atslēgu. Tātad mēs iemest ķirbju, mēs izkļūt nulle. Pie masīva grupā 0, mēs ieliekam ķirbi. Mēs mest kaķiem, mēs izkļūt vienu. Mēs ieliekam kaķis vienā. Mēs ieliekam zirneklis. Mēs izkļūt divi. Mēs ieliekam zirnekli pie masīva grupā divi. Tas būtu tik jauki, ja tā strādāja, piemēram, ka. Bet, diemžēl, kā mēs redzēsim, tas ir nedaudz sarežģītāka. 

Pirms mēs nokļūt, kādi jautājumi par šī pamata set-up of a hash tabulu? Tas ir attēls tieši ko mēs vērsa uz kuģa. Bet, tā kā mēs izvilka to uz klāja, es neesmu gatavojas iedziļināties to tālāk. Būtībā atslēgas, maģija melnā kaste - vai šajā gadījumā, krīklis box - no hash funkcija liek tos spaiņos. Un šajā piemērā mēs esam nevis liekot vārdu. Mēs esam liekot ar to saistīto tālruni numurs nosaukuma spainī. Bet jūs varētu ļoti labi vienkārši likts nosaukums spainī. 

Tas ir tikai priekšstatu par to, kas mēs vērsa uz kuģa. Mums ir iespējamo apdraudējumu, though. Un tur ir divi īpaši slaidi, ka es gribu iet pāri. Pirmais ir aptuveni hash funkciju. Tāpēc man uzdeva jautājumu, ko padara labu hash funkciju? Es dodu divas atbildes. Pirmais ir, ka tas ir deterministisko. Saistībā ar hash funkciju, Ko tas nozīmē? Jā? 

Mērķauditorija: To var atrast indekss pastāvīgu laiku? 

Jason Hirschhorn: Ka nav tas, ko tas nozīmē. Bet tas ir labs minējums. Kāds cits ir minējums ko tas nozīmē? Ka labs hash funkcija ir deterministisko? Annie? 

Mērķauditorija: Ka atslēgu var nodibināt vienīgi vienā vietā hash tabulā. 

Jason Hirschhorn: Tas ir tieši labi. Katru reizi, kad jūs nodot ķirbju, tā vienmēr atgriež nulli. Ja jūs nodot ķirbju un jūsu hash funkcija atgriež nulli, bet ir varbūtība atgriezties kaut cits lielāks par nulli - tāpēc varbūt tā var atgriezties vienu dažkārt vai divas citas reizes - , kas nav laba hash funkciju. Tu esi tieši labi. Jūsu hash funkcija jāatgriežas pašā precīzu vesels skaitlis, šajā gadījumā, lai pats precīzu string. 

Iespējams, ka atgriež to pašu precīzu vesels skaitlis tajā pašā precīzu virknes neatkarīgi no kapitalizācijas. Bet tādā gadījumā tas joprojām deterministiskā jo vairākas lietas tiek plānots uz to pašu vērtību. Tas ir jauki. Tik ilgi, kamēr ir tikai viens izeja dotā ieguldījuma. 

OK. Otra lieta ir tā, ka atgriežas spēkā rādītājus. Mēs audzināti, ka agrāk. Šī hash funkcija - oh boy - hash funkcija būtu atgriezties spēkā rādītājus. Tā teikt - iesim atpakaļ uz šo piemēru. Mana hash funkciju skaita up burti vārda. Tas ir hash funkciju. Un atgriež ka skaitlis. Tātad, ja man ir vārdu A, tas ir gatavojas atgriezties vienu. Un tas notiek, lai izveidotu šeit. Ko darīt, ja man ar vārdu sikspārnis? Tas notiek, lai atgrieztos trīs. Kur tas bat doties? 

Tas nav piemērots. Bet tas ir kaut kur aiziet. Šī ir mana hash tabulu, galu galā, un viss ir jāiet kaut kur. Tātad, ja ir nūja doties? Jebkurš domas? Guesses? Labas guesses? 

Mērķauditorija: Zero. 

Jason Hirschhorn: Kāpēc nulle? 

Mērķauditorija: Tā kā trīs moduļa trīs ir nulle? 

Jason Hirschhorn: Three moduļa trīs ir nulle. Tas ir liels minējums, un tas ir pareizi. Tātad, šajā gadījumā tas būtu iespējams, iet uz nulli. Tik labs veids, lai nodrošinātu, ka šis hash Funkcija atgriež vienīgi spēkā indeksi tiek līdz modulēt to ar izmēru tabulā. Ja jūs modulēt neatkarīgi šo peļņu, trīs, jūs vienmēr gatavojas saņemt kaut kas starp nulli, viens un divi. Un, ja tas vienmēr atgriežas septiņi, un Jūs vienmēr modulēt, trīs, tu esi vienmēr gatavojas saņemt to pašu. 

Tāpēc tas joprojām ir deterministisko Ja jūs modulo. Bet tas nodrošinās, ka jums nekad kaut ko - nederīgs nozare. Parasti, ka moduļa vajadzētu notikt iekšpusē jūsu hash funkciju. Tātad jums nav jāuztraucas par to. Jūs vienkārši nevar nodrošināt, ka tas ir derīgs Indice. Kādi jautājumi par šo potenciāls pitfall? 

OK. Un tur mēs ejam. Nākamais potenciālu pitfall, un tas ir liels vienu. Ko darīt, ja divas atslēgas karti pašu vērtību? Tāpēc ka ir divi veidi, kā rīkoties šajā. Pirmais sauc lineāra zondēšana, kas es esmu nav iet pār. Bet jums vajadzētu būt pazīstams ar to, kā , kas darbojas un kas tas ir. 

Otrs es esmu gatavojas iet pāri jo tas ir viens, ka daudzi cilvēki, iespējams, galu galā pieņemot lēmumu izmantot savu problēmu kopumu. Protams, jums nav. Bet problēmu kopumu, daudzi cilvēki mēdz izvēlēties, lai radītu hash tabulu ar atsevišķu Virknējuma īstenot savu vārdnīcu. Tāpēc mēs esam gatavojas iet pār to, ko tas nozīmē lai radītu hash tabulu ar atsevišķa Ķēžu. 

Tāpēc man ir ķirbju. Tā atgriež nulli. Un man ķirbju šeit. Tad man ir - kas ir vēl viens Halloween tēmu lieta? 

Mērķauditorija: Candy. 

Jason Hirschhorn: Candy! Tas ir liels vienu. Man konfektes, un konfektes arī dod man nulle. Ko man darīt? Jebkuras idejas? Jo jūs visi veida zinām kāda atsevišķa virknes intervāli ir. Tātad, kādas idejas, ko darīt? Jā. 

Mērķauditorija: Liekot virkni faktiski hash tabulā. 

Jason Hirschhorn: Tātad mēs ejam izdarīt labu priekšstatu nekā šeit. OK. 

Mērķauditorija: Vai Hashtable [Dzirdams] rādītājs, kas norāda uz sākums saraksta. Un tad ir ķirbju būt pirmā vērtība šajā saistīts sarakstā un konfektes būt otrā vērtība šajā saistīts sarakstā. 

Jason Hirschhorn: OK. Marcus, tas bija izcils. Es esmu gatavojas lauzt, ka uz leju. Marcus saka nav pārrakstīt ķirbju. Tas būtu slikti. Nelieciet konfektes kaut kur citur. Mēs ejam, lai viņus gan nullei. Bet mēs ejam, lai risinātu liekot tos nullei izveidojot sarakstu nulles līmenī. Un mēs spēsim izveidot sarakstu viss, kas plānots līdz nullei. Un labākais veids, kā mēs uzzinājām, lai radītu sarakstu, kas var augt un sarauties dinamiski neatrodas cits masīvs. Tāpēc ne daudzdimensiju masīvu. Bet vienkārši izveidot saistīts saraksts. 

Tātad, ko viņš ierosināja - Es esmu gatavojas saņemt jaunu - ir izveidot masīvu ar norādes, masīvs norādes. OK. Jebkura ideja, vai mājienu, kāda veida no šīs norādes vajadzētu būt? Marcus? 

Mērķauditorija: norādes uz - 

Jason Hirschhorn: jo jūs teica saistīts saraksts, tā - 

Mērķauditorija: Mezgls norādes? 

Jason Hirschhorn: Mezgls norādes. Ja lietas mūsu saistīts saraksts ir mezgli, tad tie būtu mezglu norādes. Un ko viņi ir vienādi sākotnēji? 

Mērķauditorija: Null. 

Jason Hirschhorn: Null. Tātad tur ir mūsu tukša lieta. Ķirbju atgriežas nulles. Ko mēs darām? Staigāt mani caur to? Patiesībā, Marcus jau man iedeva. Kāds cits staigāt mani caur to. Ko mēs darām, kad mēs - Tas izskatās ļoti līdzīgi ko mēs tikai darot. Avi. 

Mērķauditorija: Es esmu gatavojas pieņemt minējums. Tātad, ja jums Candy. 

Jason Hirschhorn: Jā. Nu, mēs saņēmām ķirbi. Būsim mūsu pirmā. Mēs saņēmām ķirbju. 

Mērķauditorija: OK. Ķirbju atgriežas nulles. Tātad jūs ievietojiet to, ka. Vai tiešām jūs ielieciet to saistītajā sarakstā. 

Jason Hirschhorn: Kā mēs ielieciet to saistītajā sarakstā? 

Mērķauditorija: Ak, faktiskais sintakse? 

Jason Hirschhorn: Just staigāt - pateikt vairāk. Ko mēs darām? 

Mērķauditorija: Jūs vienkārši ievietot tā kā pirmo mezglu. 

Jason Hirschhorn: OK. Tāpēc mums ir mūsu mezglu, ķirbju. Un tagad, kā es varu ievietot to? 

Mērķauditorija: Jūs piešķirat to rādītāja. 

Jason Hirschhorn: Kurš rādītājs? 

Mērķauditorija: rādītājs ir nulle. 

Jason Hirschhorn: Tātad, ja vai tas punkts? 

Mērķauditorija: Lai null tiesības tagad. 

Jason Hirschhorn: Nu, tas norāda uz null. Bet es esmu liekot ķirbju. Tātad, kur ir tas punkts? 

Mērķauditorija: Lai ķirbju. 

Jason Hirschhorn Lai ķirbi. Tieši tā. Tāpēc tas norāda uz ķirbi. Un kur šis rādītājs ķirbju punktu? Līdz 

Mērķauditorija: Null. 

Jason Hirschhorn Lai null. Tieši tā. Tātad mēs vienkārši ievietot kaut ko uz saistītajā sarakstā. Mēs tikko uzrakstīju šo kodu, lai to izdarītu. Gandrīz mēs gandrīz got it pilnīgi ieplaisājusi. Tagad mēs ievietotu konfektes. Mūsu Candy arī iet uz nulli. Tātad, ko mēs darām ar Candy? 

Mērķauditorija: Tas ir atkarīgs no tā, vai ne mēs cenšamies, lai sakārtotu to. 

Jason Hirschhorn: Tas ir tieši labi. Tas ir atkarīgs no tā, vai Mēs cenšamies, lai sakārtotu to. Pieņemsim, ka mēs neesam gatavojas, lai sakārtotu to. 

Mērķauditorija: Nu tad, kā mēs apspriedām pirms, tas ir vienkāršākais vienkārši nodot to labi sākumā, lai rādītājs no nulles punkta līdz konfektes. 

Jason Hirschhorn: OK. Turiet par. Ļaujiet man radīt konfektes šeit. Tāpēc šis rādītājs - 

Mērķauditorija: Jā, tagad ir vērsta uz konfektes. Tad rādītāju no Candy norāda uz ķirbi. 

Jason Hirschhorn: piemēram, ka? Un teikt, mēs saņēmām citu lieta karti līdz nullei? 

Mērķauditorija: Nu, jūs vienkārši darīt to pašu? 

Jason Hirschhorn: Vai pats. Tātad šajā gadījumā, ja mums nav vēlas, lai saglabātu to sakārtoti to izklausās diezgan vienkārši. Ņemam rādītāju uz Indice ņemot vērā mūsu hash funkciju. Mums, kas norāda uz mūsu jauno mezglu. Un tad kāds tas bija vērsta iepriekš - šajā gadījumā Null, jo Otrajā gadījumā ķirbju - ka, neatkarīgi no tā, norādot uz iepriekš, mēs pievienot uz tuvāko Mūsu jaunā mezglu. Mēs ievietojot kaut sākumā. Faktiski tas ir daudz vienkāršāk, nekā cenšoties saglabāt sarakstu sakārtoti. Bet atkal, meklēšana būs vairāk sarežģī šeit. Mēs vienmēr ir iet uz beigām. 

OK. Visus jautājumus par atsevišķu Virknējuma? Kā tas darbojas? Lūdzu, pajautājiet viņiem tagad. Es tiešām gribu, lai pārliecinātos, ka jūs visi saprast pirms mēs galvu. 

Mērķauditorija: Kāpēc jūs nodot ķirbi un konfektes vienā un tajā pašā daļa hash tabulu? 

Jason Hirschhorn: Labs jautājums. Kāpēc mēs viņus pats daļa hash tabulu? Nu, šajā gadījumā mūsu hash funkcija atgriežas nulles gan no tiem. Tāpēc viņiem ir nepieciešams doties pie Indice nullei jo tas ir, ja mēs ejam uz meklēt viņiem, ja mēs kādreiz vēlas, lai tos uzmeklēt. Atkal, ar lineāro zondēšana pieeju mēs nevarētu nodot tos gan ir nulle. Bet atsevišķā ķēdes pieeja, Mēs ejam, lai viņus abus uz nulli un pēc tam izveidot sarakstu nost no nulles. 

Un mēs negribam, lai pārrakstīt ķirbju tikai par to, jo tad mēs pieņemu, ka ķirbju bija nekad nav ievietota. Ja mēs vienkārši turēt viena lieta vieta, kas varētu būt slikti. Tad nebūtu iespēja mums jebkad - Ja mēs kādreiz bija dublikātu, tad mēs vienkārši izdzēst savu sākotnējo vērtību. Tātad, tas ir iemesls, kāpēc mēs to darām šo pieeju. Vai tas ir iemesls, kāpēc mēs izvēlējāmies - bet atkal, mēs izvēlējās atsevišķu Ķēžu rādītāju pieeju, kas ir vēl daudzas citas metodes varētu izvēlēties. Tas, ka atbildi uz savu jautājumu? 

OK. Carlos. Linear zondēšana nozīmētu - ja mēs atradām sadursmes nulles līmenī, mēs izskatītos nākamajā vietas, lai redzētu, vai tas bija atvērts, un nodot to tur. Un tad mēs skatāmies nākamajā sportā un redzēt, ja tas ir atvērts, un nodot to tur. Tāpēc mēs atrast nākamo pieejamo atvērt vietas un nodot to tur. Kādi citi jautājumi? Jā, Avi. 

Mērķauditorija: Kā sekot tam, Ko jūs saprotat ar nākamo vietas? Hash galda vai saistītajā sarakstā. 

Jason Hirschhorn: lineārajiem programmēšana, nav saistīti sarakstus. Nākamais plankums uz hash tabulu. 

Mērķauditorija: OK. Tāpēc hash tabulu būtu inicializēts lielumam - piemēram skaita virknes ka jums bija ievietot? 

Jason Hirschhorn: Jūs būtu vēlas, lai būtu tiešām liels. Jā. Šeit ir priekšstatu par to, ko mēs tikai vērsa uz kuģa. Atkal, mums ir sadursmes šeit. pie 152. Un jūs redzēsiet, mēs izveidojām saistīts saraksts off no tā. Atkal, hash tabulu atsevišķu ķēžu pieeja nav viens no jums ir jāveic, lai uzstādītu problēmas seši, bet ir viens, ka daudzi skolēni mēdz lietot. Tāpēc uz šo piezīmi, parunāsim īsumā pirms mēs galvu par problēmu seši, un tad es jums dalīties ar jums stāstu. Mums ir trīs minūtes. 

Problēma noteikti seši. Jums ir četras funkcijas - slodze, pārbaudiet, izmērs un izkraut. Slodze - labi, mēs esam iet vairāk nekā slodzi tikai tagad. Mēs vērsa slodzi uz kuģa. Un mēs pat sākām kodēšanas daudz ievietojot saistītajā sarakstā. Tāpēc slodze ir ne daudz vairāk nekā tas, ko mēs esam tikko dara. 

Pārbaude ir, kad esat kaut kas piekrauts. Tas ir tas pats process, kā šī. Tās pašas pirmās divas daļas, kur mest kaut uz hash funkciju un saņemt savu vērtību. Bet tagad mēs esam ne ievietošanas. Tagad mēs meklējam to. Man ir parauga kods rakstīts, lai atrastu kaut saistītajā sarakstā. Es aicinu jūs, lai praksē to. Bet intuitīvi atrast kaut ko ir diezgan līdzīgs ievietojot kaut ko. Patiesi, mēs zīmējis atrast kaut saistītajā sarakstā, kas pārvietojas līdz kamēr jums līdz galam. Un, ja jums ir līdz galam un nevarēja atrast, tad tas nav tur. Tātad tas ir pārbaude, būtībā. 

Nākamais ir izmērs. Pieņemsim izlaist izmēru. Beidzot esat izkraut. Izkraut ir viens mēs neesam sagatavoti uz kuģa vai kodēta vēl. Bet es aicinu jūs izmēģināt kodēšanas to mūsu izlases saistīts saraksta piemērs. Bet izkraut intuitīvi ir līdzīgs free - un es domāju, ir līdzīgs, lai pārbaudītu. Izņemot tagad katru reizi, kad ejam izmantojot, jūs ne tikai pārbaudīt uz redzēt, ja jums ir jūsu vērtība tur. Bet jūs lietojat šo mezglu un atbrīvojot to būtībā. Tas ir tas, ko izkraut lūdz, lai jūs darīt. Bezmaksas visu, ko esat malloced. Tātad jūs iet cauri visam sarakstam atkal iet cauri visam hash tabula vēlreiz. Šoreiz nav pārbaudīt lai redzētu, kas tur ir. Tikai brīvi, kas ir tur. 

Un, visbeidzot, izmērs. Izmērs būtu jāīsteno. Ja jums nav ieviest izmērs - Es saku to, kā šis. Ja jums nav ieviest izmēru precīzi vienu rindiņu kodu, ieskaitot atpakaļ paziņojumu, jūs esat nepareizi dara izmēru. Tāpēc pārliecinieties lielumu, lai pilnībā dizainu punktus, jūs darāt to tieši vienā līnija koda, ietverot atgriešanās paziņojumu. 

Un nav sakravāt vēl Akchar. Ieinteresēts bebru. Es gribēju pateikt paldies puiši lai nāk uz sadaļu. Ir Happy Halloween. Šis ir mans kostīms. Es būšu valkā šo ceturtdien ja es redzu tevi pie darba laika. Un, ja jūs esat ieinteresēti par kādu vairāk fons, lai šo kostīms, jūtas brīvi, lai pārbaudītu 2011 sadaļu par stāstu par to, kāpēc es esmu valkājot ķirbju kostīms. Un tas ir skumjš stāsts. Tāpēc pārliecinieties, ka Jums ir daži audi tuvumā. Bet gan uz to, ja jums ir kāda jautājumi, es stick apkārt ārpus pēc sadaļā. Good luck par problēmu noteikti seši. Un, kā vienmēr, ja jums ir kāda jautājumi, let me know.