1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON Hirschhorn: Välkommen alla till avsnitt sju. 3 00:00:12,680 --> 00:00:15,040 Vi är i vecka sju av kursen. 4 00:00:15,040 --> 00:00:18,440 Och denna kommande torsdag är Halloween så jag är 5 00:00:18,440 --> 00:00:21,420 klädd som en pumpa. 6 00:00:21,420 --> 00:00:23,460 Jag kunde inte böja sig och sätta på mina skor, så det är därför jag är 7 00:00:23,460 --> 00:00:25,660 bara bära strumpor. 8 00:00:25,660 --> 00:00:29,220 Jag är dessutom inte bär något under detta, så att jag inte kan ta bort det om det är 9 00:00:29,220 --> 00:00:29,950 distraherande för dig. 10 00:00:29,950 --> 00:00:31,860 Jag ber om ursäkt för det. 11 00:00:31,860 --> 00:00:33,170 Du behöver inte att föreställa sig vad som händer. 12 00:00:33,170 --> 00:00:34,240 Jag har på mig boxare. 13 00:00:34,240 --> 00:00:36,170 Så det är allt bra. 14 00:00:36,170 --> 00:00:41,120 >> Jag har en längre historia om varför jag är klädd som en pumpa, men jag ska 15 00:00:41,120 --> 00:00:45,110 spara det för senare i det här avsnittet eftersom jag vill komma igång. 16 00:00:45,110 --> 00:00:47,720 Vi har en massa spännande saker att gå över denna vecka. 17 00:00:47,720 --> 00:00:51,810 De flesta av dem är direkt kopplade till detta veckans problem set, felstavningar. 18 00:00:51,810 --> 00:00:54,680 Vi kommer att gå över länkade listor och hashtabeller 19 00:00:54,680 --> 00:00:57,160 för hela sektionen. 20 00:00:57,160 --> 00:01:02,490 Jag sätter denna lista upp varje vecka, en förteckning över resurser för dig att hjälpa dig med 21 00:01:02,490 --> 00:01:04,120 materialet på den här kursen. 22 00:01:04,120 --> 00:01:07,600 Om det vid en förlust, eller om du letar efter något mer information, kolla in en av 23 00:01:07,600 --> 00:01:09,930 dessa resurser. 24 00:01:09,930 --> 00:01:14,530 >> Återigen är pset6 felstavningar, veckans pset. 25 00:01:14,530 --> 00:01:17,690 Och det uppmuntrar dig också, och jag uppmuntrar dig att använda något annat 26 00:01:17,690 --> 00:01:20,320 resurser speciellt för denna pset. 27 00:01:20,320 --> 00:01:23,390 I synnerhet tre jag har listade på skärmen - 28 00:01:23,390 --> 00:01:27,160 gdb, som vi har varit bekant med och använt ett tag nu, är 29 00:01:27,160 --> 00:01:29,270 kommer att vara till stor hjälp i veckan. 30 00:01:29,270 --> 00:01:30,190 Så jag lägger upp det här. 31 00:01:30,190 --> 00:01:32,910 Men när du arbetar med C, Du bör alltid använda gdb till 32 00:01:32,910 --> 00:01:34,430 felsöka dina program. 33 00:01:34,430 --> 00:01:36,660 Denna vecka Valgrind också. 34 00:01:36,660 --> 00:01:38,535 Är det någon som vet vad valgrind gör? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> PUBLIK: Den kontrollerar för minnesläckor? 37 00:01:43,890 --> 00:01:45,950 >> JASON Hirschhorn: Valgrind kontrollerar minnesläckor. 38 00:01:45,950 --> 00:01:49,970 Så om du malloc något i ditt program, du ber om minnet. 39 00:01:49,970 --> 00:01:52,920 I slutet av ditt program, måste du att skriva fritt om allt du har 40 00:01:52,920 --> 00:01:54,800 malloced att ge minnet tillbaka. 41 00:01:54,800 --> 00:01:58,420 Om du inte skriver fritt i slutet och programmet kommer till en slutsats, 42 00:01:58,420 --> 00:02:00,000 allting automatiskt friges. 43 00:02:00,000 --> 00:02:02,340 Och för små program, det är inte så stor en affär. 44 00:02:02,340 --> 00:02:05,250 Men om du skriver en längre löpning program som inte sluta, 45 00:02:05,250 --> 00:02:09,180 nödvändigtvis, i ett par minuter eller en par sekunder, sedan minnesläckor 46 00:02:09,180 --> 00:02:10,710 kan bli en stor affär. 47 00:02:10,710 --> 00:02:14,940 >> Så för pset6, är förväntningen att du kommer att ha noll minnesläckor med 48 00:02:14,940 --> 00:02:15,910 ditt program. 49 00:02:15,910 --> 00:02:18,690 För att kontrollera minnesläckor, kör valgrind och det kommer att ge dig några trevliga 50 00:02:18,690 --> 00:02:21,190 utgång så att du vet om eller allt var inte gratis. 51 00:02:21,190 --> 00:02:23,940 Vi kommer att öva med den senare i dag, förhoppningsvis. 52 00:02:23,940 --> 00:02:25,790 >> Slutligen kommandot diff. 53 00:02:25,790 --> 00:02:28,900 Du använde något som liknar det i pset5 med peek verktyget. 54 00:02:28,900 --> 00:02:30,780 Tillåtit dig att titta in. 55 00:02:30,780 --> 00:02:33,400 Du brukade också diff också, per problemet set spec. 56 00:02:33,400 --> 00:02:35,950 Men i tillåtit jämföra två filer. 57 00:02:35,950 --> 00:02:39,180 Du kan jämföra bitmappsfilen och info rubriker av en personal-lösning och 58 00:02:39,180 --> 00:02:42,200 din lösning i pset5 om du väljer att använda den. 59 00:02:42,200 --> 00:02:44,030 Diff gör att du kan göra det, liksom. 60 00:02:44,030 --> 00:02:48,620 Du kan jämföra det rätta svaret för veckans problem in på ditt svar 61 00:02:48,620 --> 00:02:52,210 och se om den är i linje eller se där felet är. 62 00:02:52,210 --> 00:02:55,870 >> Så de är tre bra verktyg som du bör använda för denna vecka, och 63 00:02:55,870 --> 00:02:58,130 definitivt kolla ditt program med dessa tre verktyg 64 00:02:58,130 --> 00:03:00,520 innan du slår i. 65 00:03:00,520 --> 00:03:04,650 Återigen, som jag har nämnt varje vecka, om du har någon feedback för mig - både 66 00:03:04,650 --> 00:03:06,470 positiva och konstruktiva - 67 00:03:06,470 --> 00:03:09,930 tveka inte att gå till webbplatsen längst ner på den här bilden 68 00:03:09,930 --> 00:03:11,270 samt ingång det där. 69 00:03:11,270 --> 00:03:13,440 Jag uppskattar verkligen alla och all feedback. 70 00:03:13,440 --> 00:03:17,360 Och om du ger mig vissa saker som Jag kan göra för att förbättra eller att jag är 71 00:03:17,360 --> 00:03:21,350 går bra att ni vill att jag ska fortsätta, jag tar det till sig och 72 00:03:21,350 --> 00:03:24,040 verkligen försöka hårt för att lyssna för din feedback. 73 00:03:24,040 --> 00:03:27,720 Jag kan inte lova att jag kommer att göra allt, men, som att bära en 74 00:03:27,720 --> 00:03:30,700 pumpa kostym varje vecka. 75 00:03:30,700 --> 00:03:34,020 >> Så vi kommer att tillbringa större delen av avsnitt, som jag nämnde, talar om 76 00:03:34,020 --> 00:03:37,240 länkade listor och hashtabeller, vilket kommer att vara direkt tillämplig på 77 00:03:37,240 --> 00:03:38,780 problem ställa denna vecka. 78 00:03:38,780 --> 00:03:42,580 Länkade listor går vi över relativt snabbt eftersom vi har tillbringat en hel del 79 00:03:42,580 --> 00:03:44,930 tid att gå över den i avsnitt. 80 00:03:44,930 --> 00:03:48,680 Och så vi kommer att få rakt in i kodningsproblem för länkade listor. 81 00:03:48,680 --> 00:03:52,740 Och sedan i slutet vi pratar om hashtabeller och hur de tillämpas på detta 82 00:03:52,740 --> 00:03:55,280 veckas problem inställd. 83 00:03:55,280 --> 00:03:57,560 >> Du har sett den här koden innan. 84 00:03:57,560 --> 00:04:02,730 Detta är en struct, och det är att definiera något nytt kallas en nod. 85 00:04:02,730 --> 00:04:10,660 Och inuti en nod där är ett heltal just här och det är en pekare till 86 00:04:10,660 --> 00:04:11,830 en annan nod. 87 00:04:11,830 --> 00:04:12,790 Vi har sett det här förut. 88 00:04:12,790 --> 00:04:14,830 Det har kommit upp för ett par veckor nu. 89 00:04:14,830 --> 00:04:18,680 Den kombinerar pekare, som vi har varit arbetar med, och structs, som tillåter 90 00:04:18,680 --> 00:04:22,079 oss att kombinera två olika saker i en datatyp. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Det finns mycket som händer på skärmen. 93 00:04:26,490 --> 00:04:30,220 Men allt det borde vara relativt bekant med dig. 94 00:04:30,220 --> 00:04:33,810 På den första raden, vi deklarera en ny nod. 95 00:04:33,810 --> 00:04:41,650 Och sedan inuti den nya noden, ställer jag heltalet i den noden till ett. 96 00:04:41,650 --> 00:04:44,950 Vi ser på nästa rad jag gör en printf kommandot, men jag har nedtonade 97 00:04:44,950 --> 00:04:48,080 kommandot printf eftersom verkligen viktig del är denna linje här - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Vad innebär pricken detta? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> PUBLIK: Gå till noden och bedöma värdet n för det. 102 00:04:57,240 --> 00:04:58,370 >> JASON Hirschhorn: Det är exakt rätt. 103 00:04:58,370 --> 00:05:03,300 Dot betyder tillgång till n delen av denna nya noden. 104 00:05:03,300 --> 00:05:05,690 Denna nästa rad gör vad? 105 00:05:05,690 --> 00:05:16,140 106 00:05:16,140 --> 00:05:17,050 Michael. 107 00:05:17,050 --> 00:05:21,910 >> PUBLIK: Det skapar en annan nod som kommer att peka till den nya noden. 108 00:05:21,910 --> 00:05:24,870 >> JASON Hirschhorn: Så det gör inte skapa en ny nod. 109 00:05:24,870 --> 00:05:26,120 Det skapar en vad? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> PUBLIK: En pekare. 112 00:05:29,300 --> 00:05:33,460 >> JASON Hirschhorn: En pekare till en nod, vilket framgår av denna nod * här. 113 00:05:33,460 --> 00:05:34,800 Så det skapar en pekare till en nod. 114 00:05:34,800 --> 00:05:37,490 Och vilken nod det pekar till Michael? 115 00:05:37,490 --> 00:05:38,440 >> PUBLIK: Ny nod? 116 00:05:38,440 --> 00:05:39,240 >> JASON Hirschhorn: Ny nod. 117 00:05:39,240 --> 00:05:43,020 Och den pekar där eftersom vi har gett den adressen till nya noden. 118 00:05:43,020 --> 00:05:45,820 Och nu i den här raden ser vi två olika sätt att 119 00:05:45,820 --> 00:05:46,910 uttrycka samma sak. 120 00:05:46,910 --> 00:05:49,650 Och jag ville påpeka hur dessa två saker är desamma. 121 00:05:49,650 --> 00:05:54,740 På första raden, vi dereference pekaren. 122 00:05:54,740 --> 00:05:55,830 Så vi går till noden. 123 00:05:55,830 --> 00:05:56,830 Det är vad denna stjärna betyder. 124 00:05:56,830 --> 00:05:57,930 Vi har sett det förut med pekare. 125 00:05:57,930 --> 00:05:59,280 Gå till den noden. 126 00:05:59,280 --> 00:06:00,370 Det är inom parentes. 127 00:06:00,370 --> 00:06:04,610 Och sedan komma åt via punktoperatorn n element i den noden. 128 00:06:04,610 --> 00:06:08,430 >> Så det tar syntaxen vi såg just här och nu 129 00:06:08,430 --> 00:06:09,670 använda den med en pekare. 130 00:06:09,670 --> 00:06:13,730 Visst, det blir lite upptagen om du skriver dessa parenteser - 131 00:06:13,730 --> 00:06:14,940 som stjärna och prick. 132 00:06:14,940 --> 00:06:16,220 Det blir lite upptagen. 133 00:06:16,220 --> 00:06:18,500 Så vi har några syntaktiska socker. 134 00:06:18,500 --> 00:06:19,920 Och denna linje här - 135 00:06:19,920 --> 00:06:21,170 ptr_node-> n. 136 00:06:21,170 --> 00:06:25,400 137 00:06:25,400 --> 00:06:28,000 Det gör exakt samma sak. 138 00:06:28,000 --> 00:06:30,840 Så dessa två rader kod är likvärdiga och kommer att göra 139 00:06:30,840 --> 00:06:31,650 exakt samma sak. 140 00:06:31,650 --> 00:06:34,210 >> Men jag ville peka dem innan vi går vidare så att du förstår 141 00:06:34,210 --> 00:06:39,000 som verkligen denna sak här är bara syntaktisk socker för dereferencing 142 00:06:39,000 --> 00:06:44,200 pekaren och sedan gå till n del av den strukt. 143 00:06:44,200 --> 00:06:45,525 Har du frågor om denna bild? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 OK. 146 00:06:54,390 --> 00:06:58,510 >> Så vi kommer att gå igenom ett par av verksamheten som du kan göra på 147 00:06:58,510 --> 00:06:59,730 länkade listor. 148 00:06:59,730 --> 00:07:05,770 En länkad lista, minns, är en serie av noder som pekar på varandra. 149 00:07:05,770 --> 00:07:12,470 Och vi börjar i allmänhet med en pekare kallad huvud, i allmänhet, punkterna som till 150 00:07:12,470 --> 00:07:14,040 den första på listan. 151 00:07:14,040 --> 00:07:18,900 Så på den första raden här, vi har vår ursprungliga L först. 152 00:07:18,900 --> 00:07:21,370 Så att man kan tänka på - detta text här kan du komma på som 153 00:07:21,370 --> 00:07:23,560 bara pekaren vi har lagrat någonstans att punkter 154 00:07:23,560 --> 00:07:24,670 till det första elementet. 155 00:07:24,670 --> 00:07:27,500 Och i denna länkade lista Vi har fyra noder. 156 00:07:27,500 --> 00:07:29,530 Varje nod är en stor låda. 157 00:07:29,530 --> 00:07:33,430 Den större rutan inne i stora box är heltalsdelen. 158 00:07:33,430 --> 00:07:37,400 Och sedan har vi en pekare del. 159 00:07:37,400 --> 00:07:39,630 >> Dessa boxar är inte dras till skala för hur stor är 160 00:07:39,630 --> 00:07:42,320 ett heltal i byte? 161 00:07:42,320 --> 00:07:43,290 Hur stor nu? 162 00:07:43,290 --> 00:07:43,710 Fyra. 163 00:07:43,710 --> 00:07:45,470 Och hur stor är en pekare? 164 00:07:45,470 --> 00:07:45,940 Fyra. 165 00:07:45,940 --> 00:07:48,180 Så egentligen, om vi skulle dra detta för att skala båda rutorna 166 00:07:48,180 --> 00:07:49,690 skulle vara av samma storlek. 167 00:07:49,690 --> 00:07:52,870 I det här fallet, vi vill infoga något i den länkade listan. 168 00:07:52,870 --> 00:07:57,190 Så du kan se här nere vi sätter in fem Vi färdas genom 169 00:07:57,190 --> 00:08:01,310 länkad lista, hitta där fem går, och sedan sätta in det. 170 00:08:01,310 --> 00:08:03,560 >> Låt oss bryta ner det och gå lite långsammare. 171 00:08:03,560 --> 00:08:05,510 Jag kommer att peka på tavlan. 172 00:08:05,510 --> 00:08:09,930 Så vi har vår nod fem som vi har skapat i mallocs. 173 00:08:09,930 --> 00:08:11,190 Varför är alla skrattar? 174 00:08:11,190 --> 00:08:12,130 Skojar bara. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Så vi har malloced fem. 177 00:08:14,820 --> 00:08:16,310 Vi har skapat denna nod någon annanstans. 178 00:08:16,310 --> 00:08:17,740 Vi ha den redo att gå. 179 00:08:17,740 --> 00:08:20,130 Vi börjar på framsidan av vår lista med två. 180 00:08:20,130 --> 00:08:22,380 Och vi vill infoga i en sorterad mode. 181 00:08:22,380 --> 00:08:27,550 >> Så om vi ser två och vi vill sätta i fem, vad gör vi när vi ser 182 00:08:27,550 --> 00:08:28,800 något mindre än oss? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 Vad? 185 00:08:33,520 --> 00:08:36,750 Vi vill infoga fem i detta länkad lista, hålla den sorteras. 186 00:08:36,750 --> 00:08:37,520 Vi ser nummer två. 187 00:08:37,520 --> 00:08:38,769 Så vad gör vi? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> PUBLIK: Kalla pekaren till nästa nod. 190 00:08:40,679 --> 00:08:42,530 >> JASON Hirschhorn: Och varför vi går till nästa? 191 00:08:42,530 --> 00:08:45,970 >> PUBLIK: För att det är den nästa nod i listan. 192 00:08:45,970 --> 00:08:48,310 Och vi vet bara att andra plats. 193 00:08:48,310 --> 00:08:50,410 >> JASON Hirschhorn: Och fem är större än två, i synnerhet. 194 00:08:50,410 --> 00:08:51,600 Eftersom vi vill hålla det sorterade. 195 00:08:51,600 --> 00:08:52,730 Så fem är större än två. 196 00:08:52,730 --> 00:08:54,460 Så vi går vidare till nästa. 197 00:08:54,460 --> 00:08:55,240 Nu når vi fyra. 198 00:08:55,240 --> 00:08:56,490 Och vad händer när vi når fyra? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Fem är större än fyra. 201 00:09:00,310 --> 00:09:01,460 Så vi hålla. 202 00:09:01,460 --> 00:09:03,110 Och nu är vi på sex. 203 00:09:03,110 --> 00:09:04,360 Och vad ser vi på sex? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Ja, Carlos? 206 00:09:09,608 --> 00:09:10,544 >> PUBLIK: Sex är större än fem. 207 00:09:10,544 --> 00:09:11,480 >> JASON Hirschhorn: Sex är som är större än fem. 208 00:09:11,480 --> 00:09:13,660 Så det är där vi vill att infoga fem. 209 00:09:13,660 --> 00:09:17,320 Men kom ihåg att om vi bara har en pekare här - 210 00:09:17,320 --> 00:09:19,840 detta är vår extra pekare som är traversera genom listan. 211 00:09:19,840 --> 00:09:21,860 Och vi pekar på sex. 212 00:09:21,860 --> 00:09:25,010 Vi har tappat koll på vad kommer före sex. 213 00:09:25,010 --> 00:09:29,130 Så om vi vill infoga något i denna lista hålla den sorteras, vi 214 00:09:29,130 --> 00:09:31,630 förmodligen behöver hur många pekare? 215 00:09:31,630 --> 00:09:32,280 >> PUBLIK: Två. 216 00:09:32,280 --> 00:09:32,920 >> JASON HIRSCHORN: Två. 217 00:09:32,920 --> 00:09:35,720 One att hålla reda på den nuvarande en och en för att hålla reda på 218 00:09:35,720 --> 00:09:37,050 den föregående. 219 00:09:37,050 --> 00:09:38,450 Detta är bara ett enskilt länkad lista. 220 00:09:38,450 --> 00:09:39,670 Den går endast en riktning. 221 00:09:39,670 --> 00:09:43,220 Om vi ​​hade en dubbelt länkad lista, där allt pekade på saken 222 00:09:43,220 --> 00:09:46,240 efter den och den saken innan det, då Vi skulle inte behöva göra det. 223 00:09:46,240 --> 00:09:49,350 Men i det här fallet vill vi inte förlora koll på vad som kom före oss i fall 224 00:09:49,350 --> 00:09:53,350 Vi måste sätta in fem någonstans i mitten. 225 00:09:53,350 --> 00:09:55,610 Säg vi sätter i nio. 226 00:09:55,610 --> 00:09:57,260 Vad skulle hända när Vi fick till åtta? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> PUBLIK: Du skulle behöva få den nollpunkten. 229 00:10:04,880 --> 00:10:07,820 Istället för att ha nollpunkten du skulle ha att lägga till ett element och sedan har 230 00:10:07,820 --> 00:10:09,216 det pekar på nio. 231 00:10:09,216 --> 00:10:09,700 >> JASON HIRSCHORN: Exakt. 232 00:10:09,700 --> 00:10:10,600 Så vi får åtta. 233 00:10:10,600 --> 00:10:13,140 Vi kommer till slutet av listan eftersom Detta pekar på null. 234 00:10:13,140 --> 00:10:16,330 Och nu, i stället för att det pekar på null vi har det peka på vår nya noden. 235 00:10:16,330 --> 00:10:19,870 Och vi sätter pekaren i vår nya noden på null. 236 00:10:19,870 --> 00:10:21,445 Är det någon som har några frågor om att sätta in? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Vad händer om jag inte bryr mig om hålla listan sorterad? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> PUBLIK: Stick det till början eller slutet. 241 00:10:34,350 --> 00:10:35,510 >> JASON HIRSCHORN: Stick den på början eller slutet. 242 00:10:35,510 --> 00:10:37,276 Vilken ska vi göra? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Varför slutet? 245 00:10:41,020 --> 00:10:43,250 >> PUBLIK: Eftersom början är redan fylld. 246 00:10:43,250 --> 00:10:43,575 >> JASON HIRSCHORN: OK. 247 00:10:43,575 --> 00:10:44,360 Början är redan fylld. 248 00:10:44,360 --> 00:10:46,090 Vem vill argumentera mot Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> PUBLIK: Tja du förmodligen vill sticka den i början eftersom 251 00:10:48,910 --> 00:10:50,140 annars om du lägger den på slutet du måste 252 00:10:50,140 --> 00:10:51,835 korsa hela listan. 253 00:10:51,835 --> 00:10:52,990 >> JASON HIRSCHORN: Exakt. 254 00:10:52,990 --> 00:10:57,970 Så om vi tänker på runtime, den runtime att infoga i slutet 255 00:10:57,970 --> 00:11:00,110 skulle vara n, storleken på denna. 256 00:11:00,110 --> 00:11:03,080 Vad är den stora O runtime för att infoga i början? 257 00:11:03,080 --> 00:11:04,170 Konstant tid. 258 00:11:04,170 --> 00:11:07,075 Så om du inte bryr sig om att hålla något som sorteras, mycket bättre att bara 259 00:11:07,075 --> 00:11:08,420 sätt in i början av denna lista. 260 00:11:08,420 --> 00:11:10,320 Och det kan göras i konstant tid. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> OK. 263 00:11:14,690 --> 00:11:18,870 Nästa funktion är att hitta, som andra - Vi har formulerat detta som sökning. 264 00:11:18,870 --> 00:11:22,470 Men vi kommer att titta igenom länkad lista för vissa objekt. 265 00:11:22,470 --> 00:11:26,000 Ni har sett kod för söka tidigare i föreläsningen. 266 00:11:26,000 --> 00:11:29,490 Men vi liksom bara gjorde det med infoga, eller åtminstone sätta in 267 00:11:29,490 --> 00:11:30,580 något sortering. 268 00:11:30,580 --> 00:11:36,350 Du ser igenom, kommer nod efter nod, tills du hittar det nummer som du 269 00:11:36,350 --> 00:11:37,780 söker. 270 00:11:37,780 --> 00:11:39,670 Vad händer om du når I slutet av listan? 271 00:11:39,670 --> 00:11:43,020 Säg Jag letar efter nio och jag nå slutet av listan. 272 00:11:43,020 --> 00:11:44,270 Vad gör vi? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> PUBLIK: Återgå falskt? 275 00:11:48,110 --> 00:11:48,690 >> JASON HIRSCHORN: returnera false. 276 00:11:48,690 --> 00:11:49,960 Vi hittade inte det. 277 00:11:49,960 --> 00:11:52,010 Om du kommer till slutet av listan och du inte hittar det nummer du är 278 00:11:52,010 --> 00:11:54,170 söker, det är inte där. 279 00:11:54,170 --> 00:11:55,420 Eventuella frågor om att hitta? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 Om detta var en sorterad lista, vad skulle vara olika för vårt sökande? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Yeah. 284 00:12:08,103 --> 00:12:10,600 >> PUBLIK: Det skulle finna det första värdet som är större än den 285 00:12:10,600 --> 00:12:12,390 du letar efter och sedan returnera false. 286 00:12:12,390 --> 00:12:13,190 >> JASON HIRSCHORN: Exakt. 287 00:12:13,190 --> 00:12:17,310 Så om det är en sorterad lista, om vi får något som är större än vad 288 00:12:17,310 --> 00:12:20,180 vi söker, behöver vi inte behöver hålla på till slutet av listan. 289 00:12:20,180 --> 00:12:24,060 Vi kan på den punkten returnera false eftersom vi inte kommer att hitta den. 290 00:12:24,060 --> 00:12:27,340 Frågan är nu, vi har pratat om hålla länkade listor sorteras, 291 00:12:27,340 --> 00:12:28,180 hålla dem osorterat. 292 00:12:28,180 --> 00:12:30,050 Det kommer att bli något du är förmodligen kommer att behöva tänka på 293 00:12:30,050 --> 00:12:34,240 vid kodning problem set fem om du välja en hashtabell med separat 294 00:12:34,240 --> 00:12:36,360 kedja synsätt, vilket Vi ska tala om senare. 295 00:12:36,360 --> 00:12:41,400 >> Men är det värt att hålla listan sorteras och sedan kunna kanske ha 296 00:12:41,400 --> 00:12:42,310 snabbare sökningar? 297 00:12:42,310 --> 00:12:47,220 Eller är det bättre att snabbt sätta in något i ständig runtime men sedan 298 00:12:47,220 --> 00:12:48,430 har längre söker? 299 00:12:48,430 --> 00:12:52,250 Det är en avvägning just där som du får bestämma vad som är lämpligare 300 00:12:52,250 --> 00:12:53,590 för ditt specifika problem. 301 00:12:53,590 --> 00:12:56,680 Och det är inte nödvändigtvis en helt rätt svar. 302 00:12:56,680 --> 00:12:59,520 Men det är verkligen ett beslut som får att göra, och förmodligen bra för att försvara 303 00:12:59,520 --> 00:13:05,270 som i, säg, en kommentar eller två varför du väljer en över den andra. 304 00:13:05,270 --> 00:13:06,490 >> Slutligen, ta bort. 305 00:13:06,490 --> 00:13:08,100 Vi har sett att ta bort. 306 00:13:08,100 --> 00:13:09,180 Det är ungefär som att söka. 307 00:13:09,180 --> 00:13:11,020 Vi letar efter elementet. 308 00:13:11,020 --> 00:13:12,390 Säg att vi försöker ta bort sex. 309 00:13:12,390 --> 00:13:14,450 Så hittar vi sex här. 310 00:13:14,450 --> 00:13:18,860 Det som vi måste se till att vi gör är att det som pekar på 311 00:13:18,860 --> 00:13:21,220 sex - som vi ser i steg två här nere - 312 00:13:21,220 --> 00:13:26,500 vad är pekar på sex behov till hoppa sex nu och ändras till 313 00:13:26,500 --> 00:13:28,160 vad sex pekar på. 314 00:13:28,160 --> 00:13:31,410 Vi vill inte någonsin överge resten av vår lista genom att glömma att ställa in det 315 00:13:31,410 --> 00:13:32,960 föregående pekaren. 316 00:13:32,960 --> 00:13:35,960 Och så ibland, beroende på programmet, de ska bara 317 00:13:35,960 --> 00:13:37,380 bort denna nod helt. 318 00:13:37,380 --> 00:13:40,135 Ibland kommer du att vilja återvända det värde som finns i denna nod. 319 00:13:40,135 --> 00:13:42,490 Så det är hur du tar bort arbeten. 320 00:13:42,490 --> 00:13:44,610 Har du frågor om ta bort? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> PUBLIK: Så om du ska ta bort det, skulle du bara använda gratis eftersom 323 00:13:53,850 --> 00:13:55,655 förmodligen var det malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON HIRSCHORN: Om du vill frigöra något som är precis rätt och du 325 00:13:57,976 --> 00:13:58,540 malloced den. 326 00:13:58,540 --> 00:14:00,410 Säg att vi ville återvända detta värde. 327 00:14:00,410 --> 00:14:04,010 Vi kan gå tillbaka sex och sedan fri denna nod och samtal är gratis på den. 328 00:14:04,010 --> 00:14:06,180 Eller vi skulle nog ringa gratis först och sedan återvända sex. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> OK. 331 00:14:11,580 --> 00:14:14,010 Så låt oss gå vidare till praktik kodning. 332 00:14:14,010 --> 00:14:16,090 Vi kommer att koda tre funktioner. 333 00:14:16,090 --> 00:14:18,260 Den första heter insert_node. 334 00:14:18,260 --> 00:14:22,170 Så du har kod som jag mailade dig, och om du tittar på det här senare 335 00:14:22,170 --> 00:14:28,020 du kan komma åt koden i linked.c på CS50 webbplats. 336 00:14:28,020 --> 00:14:30,880 Men i linked.c, det finns en del skelett kod som redan 337 00:14:30,880 --> 00:14:32,280 skrivits för dig. 338 00:14:32,280 --> 00:14:34,560 Och så finns det ett par funktioner du behöver för att skriva. 339 00:14:34,560 --> 00:14:36,380 >> Först ska vi skriva insert_node. 340 00:14:36,380 --> 00:14:39,800 Och vad insert_node gör säga infogar ett heltal. 341 00:14:39,800 --> 00:14:42,440 Och du ger heltalet in i en länkad lista. 342 00:14:42,440 --> 00:14:45,470 Och framför allt, behöver du att hålla listan sorterad 343 00:14:45,470 --> 00:14:47,650 från minsta till största. 344 00:14:47,650 --> 00:14:51,360 Dessutom behöver du inte vill in några dubbletter. 345 00:14:51,360 --> 00:14:54,600 Till sist, som ni kan se insert_node returnerar en bool. 346 00:14:54,600 --> 00:14:57,140 Så du ska låta användaren veta huruvida insatsen var eller inte 347 00:14:57,140 --> 00:15:00,800 framgångsrik genom att returnera sant eller falskt. 348 00:15:00,800 --> 00:15:02,580 I slutet av detta program - 349 00:15:02,580 --> 00:15:05,750 och för detta steg du inte behöver att oroa sig för att frigöra något. 350 00:15:05,750 --> 00:15:11,790 Så allt du gör är att ta ett heltal och sätter in det i en lista. 351 00:15:11,790 --> 00:15:13,890 >> Det är vad jag ber dig att göra nu. 352 00:15:13,890 --> 00:15:17,620 Återigen, i linked.c, som du alla har, är skelettet kod. 353 00:15:17,620 --> 00:15:20,980 Och du bör se mot botten provfunktionsdeklarationen. 354 00:15:20,980 --> 00:15:27,390 Men innan vi går in i kodning det i C, uppmanar jag dig starkt att gå 355 00:15:27,390 --> 00:15:29,330 genom de steg vi har varit tränar varje vecka. 356 00:15:29,330 --> 00:15:31,100 Vi har redan gått igenom en bild av detta. 357 00:15:31,100 --> 00:15:33,380 Så du bör ha viss förståelse om hur detta fungerar. 358 00:15:33,380 --> 00:15:36,590 Men jag vill uppmuntra dig att skriva lite pseudokod innan du dyker i. 359 00:15:36,590 --> 00:15:38,640 Och vi kommer att gå över pseudokod som en grupp. 360 00:15:38,640 --> 00:15:41,470 Och sedan när du har skrivit ditt pseudokod, och när vi har skrivit vår 361 00:15:41,470 --> 00:15:45,850 pseudokod som en grupp, kan du gå in kodning det i C. 362 00:15:45,850 --> 00:15:49,980 >> Som en heads up, det insert_node funktionen är förmodligen den svåraste av 363 00:15:49,980 --> 00:15:53,550 de tre vi ska skriva för jag lagt till några ytterligare begränsningar för 364 00:15:53,550 --> 00:15:57,190 programmeringen, särskilt att du kommer inte att sätta in något 365 00:15:57,190 --> 00:15:59,880 dubbletter och att listan bör förbli sorteras. 366 00:15:59,880 --> 00:16:02,660 Så detta är en icke-trivial program att du måste koda. 367 00:16:02,660 --> 00:16:06,470 Och varför inte ta 5-7 minuter bara för att få arbeta på 368 00:16:06,470 --> 00:16:07,640 pseudokod koden. 369 00:16:07,640 --> 00:16:09,460 Och då kommer vi börja går som en grupp. 370 00:16:09,460 --> 00:16:11,680 Återigen, om du har några frågor bara räcka upp handen och jag ska komma runt. 371 00:16:11,680 --> 00:16:15,258 372 00:16:15,258 --> 00:16:16,508 . 373 00:16:16,508 --> 00:18:28,370 374 00:18:28,370 --> 00:18:30,120 >> Vi har också i allmänhet gör dessa - 375 00:18:30,120 --> 00:18:32,070 eller jag vet inte uttryckligen säga att du kan arbeta med människor. 376 00:18:32,070 --> 00:18:36,500 Men självklart, jag rekommenderar starkt att du, om du har frågor, be 377 00:18:36,500 --> 00:18:39,840 granne sitter bredvid dig eller till och med arbeta med någon 378 00:18:39,840 --> 00:18:40,510 annars om du vill. 379 00:18:40,510 --> 00:18:42,600 Detta behöver inte vara en enskild tyst aktivitet. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Låt oss börja med att skriva några pseudokod på tavlan. 382 00:20:16,330 --> 00:20:19,395 Vem kan ge mig den första raden i pseudokod för det här programmet? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 För denna funktion, snarare - insert_node. 385 00:20:23,640 --> 00:20:29,960 386 00:20:29,960 --> 00:20:31,830 Alden? 387 00:20:31,830 --> 00:20:36,560 >> PUBLIK: Så det första jag gjorde var skapa en ny pekare till noden och jag 388 00:20:36,560 --> 00:20:41,320 initialiseras det pekar på samma sak som lista pekar på. 389 00:20:41,320 --> 00:20:41,550 >> JASON HIRSCHORN: OK. 390 00:20:41,550 --> 00:20:45,190 Så du skapar en ny pekare i listan, inte till den noden. 391 00:20:45,190 --> 00:20:45,420 >> PUBLIK: Höger. 392 00:20:45,420 --> 00:20:46,150 Yeah. 393 00:20:46,150 --> 00:20:46,540 >> JASON HIRSCHORN: OK. 394 00:20:46,540 --> 00:20:48,221 Och vad vill vi göra? 395 00:20:48,221 --> 00:20:49,163 Vad är efter det? 396 00:20:49,163 --> 00:20:50,105 Hur är det med nod? 397 00:20:50,105 --> 00:20:51,050 Vi har inte en nod. 398 00:20:51,050 --> 00:20:52,300 Vi har bara ett värde. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Om vi ​​vill infoga en nod, vad gör vi måste göra först innan vi kan till och med 401 00:20:58,890 --> 00:20:59,980 tycker om att sätta in det? 402 00:20:59,980 --> 00:21:00,820 >> PUBLIK: Åh, förlåt. 403 00:21:00,820 --> 00:21:02,160 vi måste malloc utrymme för en nod. 404 00:21:02,160 --> 00:21:02,455 >> JASON HIRSCHORN: Excellent. 405 00:21:02,455 --> 00:21:03,210 Låt oss göra - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Det går inte att nå så hög. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 OK. 410 00:21:09,897 --> 00:21:13,236 Vi kommer att gå ner, och sedan Vi använder två kolumner. 411 00:21:13,236 --> 00:21:13,732 Jag kan inte gå att - 412 00:21:13,732 --> 00:21:14,982 OK. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Skapa en ny nod. 415 00:21:25,130 --> 00:21:29,380 Du kan skapa en pekare till lista eller så kan du bara använda listan som den existerar. 416 00:21:29,380 --> 00:21:30,720 Du behöver egentligen inte göra det. 417 00:21:30,720 --> 00:21:31,750 >> Så vi skapar en ny nod. 418 00:21:31,750 --> 00:21:32,010 Bra. 419 00:21:32,010 --> 00:21:32,840 Det är vad vi ska göra först. 420 00:21:32,840 --> 00:21:34,870 Vad händer nu? 421 00:21:34,870 --> 00:21:35,080 >> PUBLIK: Vänta. 422 00:21:35,080 --> 00:21:38,330 Ska vi skapa en ny nod nu eller bör vi vänta med att se till att 423 00:21:38,330 --> 00:21:42,260 det finns inga dubbletter av noden på listan innan vi skapa den? 424 00:21:42,260 --> 00:21:43,100 >> JASON HIRSCHORN: Bra fråga. 425 00:21:43,100 --> 00:21:47,770 Låt oss hålla det för senare på grund av att merparten av den tid vi ska skapa 426 00:21:47,770 --> 00:21:48,220 en ny nod. 427 00:21:48,220 --> 00:21:49,110 Så vi ska ha det här. 428 00:21:49,110 --> 00:21:51,006 Men det är en bra fråga. 429 00:21:51,006 --> 00:21:53,250 Om vi ​​skapar den och vi hittar en dubblett, vad ska 430 00:21:53,250 --> 00:21:54,490 vi gör innan de återvänder? 431 00:21:54,490 --> 00:21:55,190 >> PUBLIK: Befria den. 432 00:21:55,190 --> 00:21:55,470 >> JASON HIRSCHORN: Ja. 433 00:21:55,470 --> 00:21:56,500 Förmodligen befria den. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Vad gör vi när vi skapa en ny nod? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> PUBLIK: Vi sätter antal i noden? 438 00:22:04,780 --> 00:22:05,140 >> JASON HIRSCHORN: Exakt. 439 00:22:05,140 --> 00:22:07,190 Vi uppskattar antalet - vi malloc utrymme. 440 00:22:07,190 --> 00:22:08,160 Jag kommer att lämna det allt som en rad. 441 00:22:08,160 --> 00:22:08,720 Men du har rätt. 442 00:22:08,720 --> 00:22:10,305 Vi malloc utrymme, och sedan Vi uppskattar antalet i. 443 00:22:10,305 --> 00:22:12,585 Vi kan till och med ställa in pekaren en del av den till null. 444 00:22:12,585 --> 00:22:13,720 Det är precis rätt. 445 00:22:13,720 --> 00:22:17,400 Och vad om efter det? 446 00:22:17,400 --> 00:22:18,490 Vi drog denna bild på tavlan. 447 00:22:18,490 --> 00:22:21,190 Så vad gör vi? 448 00:22:21,190 --> 00:22:22,680 >> PUBLIK: Vi går igenom listan. 449 00:22:22,680 --> 00:22:23,930 >> JASON HIRSCHORN: Gå igenom listan. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 OK. 452 00:22:31,100 --> 00:22:34,280 Och vad kontrollerar vi för vid varje nod. 453 00:22:34,280 --> 00:22:35,955 Kurt, vad ska vi kolla för varje nod? 454 00:22:35,955 --> 00:22:41,640 >> PUBLIK: Se om n-värdet på denna nod är större än n-värdet 455 00:22:41,640 --> 00:22:43,070 av vår nod. 456 00:22:43,070 --> 00:22:43,340 >> JASON HIRSCHORN: OK. 457 00:22:43,340 --> 00:22:44,280 Jag kommer att göra - 458 00:22:44,280 --> 00:22:45,855 Ja, OK. 459 00:22:45,855 --> 00:22:48,160 Så det är n - 460 00:22:48,160 --> 00:22:59,040 Jag kommer att säga om värdet är större än denna nod, vad gör vi? 461 00:22:59,040 --> 00:23:07,290 >> PUBLIK: Ja, då sätter vi saken rätt innan dess. 462 00:23:07,290 --> 00:23:07,970 >> JASON HIRSCHORN: OK. 463 00:23:07,970 --> 00:23:09,410 Så om det är större än det här, då vill vi att sätta in. 464 00:23:09,410 --> 00:23:14,010 Men vi vill sätta in den precis innan eftersom vi också skulle behöva vara 465 00:23:14,010 --> 00:23:16,070 hålla reda, då, av det som var innan. 466 00:23:16,070 --> 00:23:22,690 Så sätter innan. 467 00:23:22,690 --> 00:23:25,120 Så missade vi förmodligen något tidigare. 468 00:23:25,120 --> 00:23:27,770 Vi behöver antagligen vara att hålla koll på vad som händer. 469 00:23:27,770 --> 00:23:28,460 Men vi ska komma tillbaka dit. 470 00:23:28,460 --> 00:23:30,160 Så vad värdet är mindre än? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, vad gör vi om värdet är mindre än? 473 00:23:39,710 --> 00:23:43,000 >> PUBLIK: Sedan kan du bara fortsätta om det inte är den sista. 474 00:23:43,000 --> 00:23:43,550 >> JASON HIRSCHORN: Jag gillar det. 475 00:23:43,550 --> 00:23:44,800 Så gå till nästa nod. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Om det inte är den sista - 478 00:23:48,930 --> 00:23:51,100 vi förmodligen kontrollera för att i villkoren för ett tillstånd. 479 00:23:51,100 --> 00:23:54,870 Men ja, nästa nod. 480 00:23:54,870 --> 00:23:58,680 Och det börjar bli för låg, så vi ska flytta hit. 481 00:23:58,680 --> 00:24:02,030 Men om - 482 00:24:02,030 --> 00:24:03,280 alla kan se det här? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Om vi ​​är lika vad gör vi? 485 00:24:11,610 --> 00:24:15,740 Om det värde vi försöker sätta in är lika med denna nods värde? 486 00:24:15,740 --> 00:24:16,320 Yeah? 487 00:24:16,320 --> 00:24:18,400 >> PUBLIK: [OHÖRBAR]. 488 00:24:18,400 --> 00:24:18,850 >> JASON HIRSCHORN: Ja. 489 00:24:18,850 --> 00:24:19,290 Med tanke på detta - 490 00:24:19,290 --> 00:24:20,090 Marcus är rätt. 491 00:24:20,090 --> 00:24:21,330 Vi kunde kanske gjort något annat. 492 00:24:21,330 --> 00:24:25,360 Men med tanke på att vi har skapat det, här Vi bör frigöra och sedan återvända. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Är det bättre? 495 00:24:30,080 --> 00:24:31,850 Hur är det? 496 00:24:31,850 --> 00:24:33,100 OK. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Gratis och vad gör vi tillbaka, [OHÖRBAR]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 OK. 501 00:24:44,110 --> 00:24:45,360 Saknas något? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 Så vart ska vi hålla reda enligt känd nod? 504 00:24:59,650 --> 00:25:02,370 >> PUBLIK: Jag tror att det skulle gå efter att skapa en ny nod. 505 00:25:02,370 --> 00:25:02,600 >> JASON HIRSCHORN: OK. 506 00:25:02,600 --> 00:25:03,940 Så i början vi förmodligen - 507 00:25:03,940 --> 00:25:07,175 Ja, kan vi skapa en pekare till en ny nod, som en tidigare nod pekare och 508 00:25:07,175 --> 00:25:09,600 en aktuell nod pekare. 509 00:25:09,600 --> 00:25:12,640 Så låt oss sätta det här. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Skapa nuvarande och tidigare pekare till noderna. 512 00:25:26,900 --> 00:25:28,955 Men när vi justerar dessa pekare? 513 00:25:28,955 --> 00:25:30,205 Var ska vi göra det i koden? 514 00:25:30,205 --> 00:25:33,830 515 00:25:33,830 --> 00:25:34,160 Jeff? 516 00:25:34,160 --> 00:25:35,170 >> PUBLIK: - värdeförhållanden? 517 00:25:35,170 --> 00:25:36,420 >> JASON HIRSCHORN: Vilken en särskilt? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> PUBLIK: Jag är bara förvirrad. 520 00:25:40,720 --> 00:25:44,200 Om värdet är större än denna nod, inte det betyda att du vill gå 521 00:25:44,200 --> 00:25:45,320 till nästa nod? 522 00:25:45,320 --> 00:25:49,515 >> JASON Hirschhorn: Så om vårt värde är som är större än värdet på denna nod. 523 00:25:49,515 --> 00:25:52,130 >> PUBLIK: Ja, då skulle du vilja gå längre ner på linjen, eller hur? 524 00:25:52,130 --> 00:25:52,590 >> JASON Hirschhorn: Höger. 525 00:25:52,590 --> 00:25:53,840 Så vi inte sätta in den här. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Om värdet är mindre än denna nod, då vi går till nästa nod - eller då vi 528 00:26:03,240 --> 00:26:03,835 sätt in tidigare. 529 00:26:03,835 --> 00:26:05,966 >> Publik: Vänta, som är denna nod och vilken är värdet? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON Hirschhorn: Bra fråga. 532 00:26:09,280 --> 00:26:13,260 Värde per denna definition funktion är vad vi gett. 533 00:26:13,260 --> 00:26:16,910 Så värdet är det antal vi gett. 534 00:26:16,910 --> 00:26:21,120 Så om värdet är mindre än detta nod, vi behöver tid för att sätta in. 535 00:26:21,120 --> 00:26:24,575 Om värdet är större än denna nod, vi går till nästa nod. 536 00:26:24,575 --> 00:26:26,790 Och tillbaka till den ursprungliga frågan, dock, där - 537 00:26:26,790 --> 00:26:29,060 >> PUBLIK: Om värdet är större än denna nod. 538 00:26:29,060 --> 00:26:30,310 >> JASON Hirschhorn: Och så vad gör vi här? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Söt. 541 00:26:38,160 --> 00:26:38,860 Det stämmer. 542 00:26:38,860 --> 00:26:41,370 Jag ska bara skriva uppdaterings pekare. 543 00:26:41,370 --> 00:26:44,010 Men ja, med den nuvarande du vill uppdatera den till 544 00:26:44,010 --> 00:26:46,080 peka på nästa en. 545 00:26:46,080 --> 00:26:47,330 Något annat vi saknar? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Så jag ska skriva här koda in gedit. 548 00:26:54,940 --> 00:26:58,375 Och medan jag gör det, kan du ha en par minuter att arbeta med kodning 549 00:26:58,375 --> 00:28:19,240 detta i C. 550 00:28:19,240 --> 00:28:20,940 >> Så jag har ingång pseudokoden. 551 00:28:20,940 --> 00:28:22,940 En snabb anteckning innan vi sätter igång. 552 00:28:22,940 --> 00:28:25,560 Vi kanske inte kan helt avsluta detta i alla 553 00:28:25,560 --> 00:28:27,300 tre av dessa funktioner. 554 00:28:27,300 --> 00:28:30,630 Det finns korrekta lösningar på dem att jag kommer att skicka ut till er 555 00:28:30,630 --> 00:28:33,730 efter avsnitt, och det kommer finnas på CS50.net. 556 00:28:33,730 --> 00:28:35,640 Så jag inte uppmuntrar dig att gå titta på avsnitten. 557 00:28:35,640 --> 00:28:40,550 Jag uppmuntrar dig att prova dessa på äger, och sedan använda den praxis 558 00:28:40,550 --> 00:28:41,760 problem att kontrollera dina svar. 559 00:28:41,760 --> 00:28:47,070 Alla dessa har utformats för att noggrant relatera till och hålla sig till det som 560 00:28:47,070 --> 00:28:48,400 du måste göra på problemet set. 561 00:28:48,400 --> 00:28:53,820 Så jag uppmuntrar dig att öva detta på egen hand och sedan använda koden för att 562 00:28:53,820 --> 00:28:54,660 kontrollera dina svar. 563 00:28:54,660 --> 00:28:57,060 Därför att jag vill gå vidare till hash bord någon gång i sektionen. 564 00:28:57,060 --> 00:28:58,150 Så vi kanske inte få igenom det hela. 565 00:28:58,150 --> 00:28:59,960 Men vi ska göra så mycket vi kan nu. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Låt oss börja. 568 00:29:01,960 --> 00:29:04,770 Asam, hur skapar vi en ny nod? 569 00:29:04,770 --> 00:29:06,810 >> PUBLIK: Du struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON Hirschhorn: Så vi har det här uppe. 571 00:29:09,640 --> 00:29:10,040 Åh, förlåt. 572 00:29:10,040 --> 00:29:13,530 Du sa struct *. 573 00:29:13,530 --> 00:29:17,260 >> PUBLIK: Och sedan [? typ?] nod eller c-noden. 574 00:29:17,260 --> 00:29:17,780 >> JASON Hirschhorn: OK. 575 00:29:17,780 --> 00:29:19,740 Jag kommer att kalla det new_node så vi kan stanna konsekvent. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> PUBLIK: Och du vill ställa in att till huvud, den första noden. 578 00:29:33,180 --> 00:29:33,580 >> JASON Hirschhorn: OK. 579 00:29:33,580 --> 00:29:37,290 Så nu denna pekar på - så här har inte skapat en ny nod ännu. 580 00:29:37,290 --> 00:29:41,380 Detta är bara pekar på första noden i listan. 581 00:29:41,380 --> 00:29:42,630 Hur skapar jag en ny nod? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Om jag behöver utrymme för att skapa en ny nod. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 Och hur stor? 586 00:29:51,710 --> 00:30:00,390 >> Publik: Storleken på strukt. 587 00:30:00,390 --> 00:30:01,150 >> JASON Hirschhorn: Den Storleken på strukt. 588 00:30:01,150 --> 00:30:02,400 Och vad är det struct heter? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> PUBLIK: Node? 591 00:30:09,840 --> 00:30:11,640 >> JASON Hirschhorn: Node. 592 00:30:11,640 --> 00:30:17,640 Så malloc (sizeof (nod)); ger oss utrymme. 593 00:30:17,640 --> 00:30:19,740 Och är denna linje - 594 00:30:19,740 --> 00:30:21,740 en sak är fel på den här linjen. 595 00:30:21,740 --> 00:30:24,430 Är new_node en pekare till en struct? 596 00:30:24,430 --> 00:30:25,650 Det är ett generiskt namn. 597 00:30:25,650 --> 00:30:26,520 Vad är det - 598 00:30:26,520 --> 00:30:27,450 nod, exakt. 599 00:30:27,450 --> 00:30:29,340 Det är en nod *. 600 00:30:29,340 --> 00:30:33,010 Och vad gör vi direkt efter vi malloc något, Asan? 601 00:30:33,010 --> 00:30:34,476 Vad är det första vi gör? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Vad händer om det inte fungerar? 604 00:30:40,320 --> 00:30:42,430 >> PUBLIK: Åh, kolla om det pekar på noden? 605 00:30:42,430 --> 00:30:43,310 >> JASON Hirschhorn: Exakt. 606 00:30:43,310 --> 00:30:46,750 Så om du new_node lika jämlikar null, vad gör vi? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Detta returnerar en bool, denna funktion. 609 00:30:54,820 --> 00:30:57,760 Exakt. 610 00:30:57,760 --> 00:30:58,450 Ser bra ut. 611 00:30:58,450 --> 00:30:59,680 Något att lägga till där? 612 00:30:59,680 --> 00:31:00,670 Vi kommer att lägga till saker i slutet. 613 00:31:00,670 --> 00:31:03,160 Men det hittills ser bra ut. 614 00:31:03,160 --> 00:31:06,170 Skapa nuvarande och tidigare pekare. 615 00:31:06,170 --> 00:31:08,650 Michael, hur gör jag detta? 616 00:31:08,650 --> 00:31:12,810 >> PUBLIK: Du skulle ha att göra en nod *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Du skulle behöva göra en inte för new_node men för 619 00:31:25,502 --> 00:31:26,905 noder som vi redan har. 620 00:31:26,905 --> 00:31:27,230 >> JASON Hirschhorn: OK. 621 00:31:27,230 --> 00:31:29,255 Så den aktuella noden vi är på. 622 00:31:29,255 --> 00:31:30,505 Jag ringer det STRÖM. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Okej. 625 00:31:39,770 --> 00:31:41,620 Vi har bestämt att vi vill behålla två eftersom vi behöver veta 626 00:31:41,620 --> 00:31:42,870 vad som finns innan det. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Vad tror de får initieras till? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> PUBLIK: Deras värde i vår lista. 631 00:31:54,180 --> 00:31:58,090 >> JASON Hirschhorn: Så vad är det första på vår lista? 632 00:31:58,090 --> 00:32:04,050 Eller hur vet vi var början på vår lista är? 633 00:32:04,050 --> 00:32:08,015 >> PUBLIK: Är det inte gått i funktion? 634 00:32:08,015 --> 00:32:08,466 >> JASON Hirschhorn: Höger. 635 00:32:08,466 --> 00:32:09,716 Det antogs i här. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Så om det passerat in i funktion, start av listan, vad ska vi 638 00:32:18,980 --> 00:32:21,270 inställd ström lika med? 639 00:32:21,270 --> 00:32:22,110 >> PUBLIK: List. 640 00:32:22,110 --> 00:32:22,900 >> JASON Hirschhorn: List. 641 00:32:22,900 --> 00:32:24,090 Det är precis rätt. 642 00:32:24,090 --> 00:32:26,290 Nu har adressen till början på vår lista. 643 00:32:26,290 --> 00:32:28,450 Och hur är det tidigare? 644 00:32:28,450 --> 00:32:31,920 >> PUBLIK: Lista minus ett? 645 00:32:31,920 --> 00:32:32,690 >> JASON Hirschhorn: Det finns ingenting innan. 646 00:32:32,690 --> 00:32:34,580 Så vad kan vi göra för att betyda någonting? 647 00:32:34,580 --> 00:32:35,050 >> PUBLIK: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON Hirschhorn: Ja. 649 00:32:35,450 --> 00:32:37,950 Det låter som en bra idé. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Tack. 652 00:32:39,630 --> 00:32:42,850 Gå igenom listan. 653 00:32:42,850 --> 00:32:45,490 Konstantin, hur länge ska vi att gå igenom listan? 654 00:32:45,490 --> 00:32:49,010 >> PUBLIK: Tills vi når noll. 655 00:32:49,010 --> 00:32:49,390 >> JASON Hirschhorn: OK. 656 00:32:49,390 --> 00:32:50,430 Så om, samtidigt, för slinga. 657 00:32:50,430 --> 00:32:52,200 Vad gör vi? 658 00:32:52,200 --> 00:32:53,320 >> PUBLIK: Kanske en for-loop? 659 00:32:53,320 --> 00:32:53,910 >> JASON Hirschhorn: Låt oss göra en for-loop. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> PUBLIK: Och vi säger till - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 tills den aktuella pekar inte är lika med noll. 664 00:33:13,390 --> 00:33:19,160 >> JASON Hirschhorn: Så om vi känner till tillstånd, hur kan vi skriva en loop 665 00:33:19,160 --> 00:33:21,740 baserat av detta villkor. 666 00:33:21,740 --> 00:33:24,380 Vad är det för en slinga ska vi använda? 667 00:33:24,380 --> 00:33:25,260 >> PUBLIK: Medan. 668 00:33:25,260 --> 00:33:25,590 >> JASON Hirschhorn: Ja. 669 00:33:25,590 --> 00:33:27,130 Det är mer förnuftigt baserad bort av vad du sa. 670 00:33:27,130 --> 00:33:29,430 Om vi ​​vill bara gå in vi det skulle bara vet det där, skulle det göra 671 00:33:29,430 --> 00:33:31,680 meningsfullt att göra en while-slinga. 672 00:33:31,680 --> 00:33:39,880 Även om nuvarande inte är lika null, Om värdet är mindre än denna nod. 673 00:33:39,880 --> 00:33:41,650 Akshar, ge mig denna linje. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> PUBLIK: Om ström-> n n mindre än värdet. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Eller vända det. 678 00:34:03,260 --> 00:34:06,140 Slå det fäste. 679 00:34:06,140 --> 00:34:06,620 >> JASON Hirschhorn: Förlåt. 680 00:34:06,620 --> 00:34:08,760 >> PUBLIK: Byt fästet. 681 00:34:08,760 --> 00:34:10,914 >> JASON Hirschhorn: Så om det är större än värdet. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Därför att det är förvirrande med comment ovan, kommer jag att göra det. 684 00:34:22,120 --> 00:34:22,480 Men ja. 685 00:34:22,480 --> 00:34:25,125 Om vårt värde är lägre än detta nod, vad gör vi? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Jag har det här. 688 00:34:26,710 --> 00:34:27,960 Infoga tidigare. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 OK. 691 00:34:32,370 --> 00:34:33,933 Hur gör vi det? 692 00:34:33,933 --> 00:34:34,900 >> PUBLIK: Är det mig fortfarande? 693 00:34:34,900 --> 00:34:36,150 >> JASON Hirschhorn: Ja. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> PUBLIK: Du - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> nästa. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON Hirschhorn: Så vad är som kommer att vara lika? 700 00:34:50,163 --> 00:34:52,070 >> PUBLIK: Det kommer att lika stor ström. 701 00:34:52,070 --> 00:34:53,889 >> JASON Hirschhorn: Exakt. 702 00:34:53,889 --> 00:34:55,730 Och så den andra - 703 00:34:55,730 --> 00:34:56,730 vad behöver vi för att uppdatera? 704 00:34:56,730 --> 00:34:59,982 >> PUBLIK: Kontrollera om tidigare är lika med noll. 705 00:34:59,982 --> 00:35:01,870 >> JASON Hirschhorn: Om bakåt - 706 00:35:01,870 --> 00:35:03,730 så om föregående lika med noll. 707 00:35:03,730 --> 00:35:05,990 >> PUBLIK: Det betyder att det kommer att bli den huvud. 708 00:35:05,990 --> 00:35:06,780 >> JASON Hirschhorn: Det innebär det har blivit huvudet. 709 00:35:06,780 --> 00:35:07,620 Så vad gör vi? 710 00:35:07,620 --> 00:35:12,510 >> PUBLIK: Vi gör huvudet lika new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON Hirschhorn: Head lika new_node. 712 00:35:16,690 --> 00:35:20,540 Och varför gå här, inte lista? 713 00:35:20,540 --> 00:35:24,940 >> PUBLIK: Eftersom huvudet är en global variabel, som är startplatsen. 714 00:35:24,940 --> 00:35:26,190 >> JASON Hirschhorn: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 Och - 718 00:35:36,150 --> 00:35:53,796 >> PUBLIK: Då du annars prev-> nästa lika new_node. 719 00:35:53,796 --> 00:35:55,080 Och sedan återvänder sant. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON Hirschhorn: Vari vi satt new_node slut? 722 00:36:02,700 --> 00:36:04,850 >> PUBLIK: Jag skulle - 723 00:36:04,850 --> 00:36:06,180 Jag satt som i början. 724 00:36:06,180 --> 00:36:07,430 >> JASON Hirschhorn: Vad linje? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> PUBLIK: Efter if kontrollera om det är känt. 727 00:36:12,598 --> 00:36:13,057 >> JASON Hirschhorn: Här? 728 00:36:13,057 --> 00:36:18,335 >> PUBLIK: Jag skulle göra new_node-> n lika värde. 729 00:36:18,335 --> 00:36:19,585 >> JASON Hirschhorn: Låter bra. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Förmodligen är det klokt - vi gör inte måste veta vad listan är vi på 732 00:36:25,090 --> 00:36:26,280 eftersom vi endast behandlar med en lista. 733 00:36:26,280 --> 00:36:29,560 Så en bättre funktionsdeklaration för detta är bara för att bli av med 734 00:36:29,560 --> 00:36:34,360 helt och bara sätta in ett värde i huvudet. 735 00:36:34,360 --> 00:36:35,930 Vi behöver inte ens veta vilken lista som vi är i. 736 00:36:35,930 --> 00:36:39,140 Men jag kommer att hålla det för nu och sedan ändra det på att uppdatera 737 00:36:39,140 --> 00:36:42,590 bilderna och kod. 738 00:36:42,590 --> 00:36:44,980 Så det ser bra ut för nu. 739 00:36:44,980 --> 00:36:46,560 Om värde - som kan göra den här linjen? 740 00:36:46,560 --> 00:36:47,810 Om - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 vad gör vi här, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> PUBLIK: Om värdet är större än nuvarande-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON Hirschhorn: Hur vi går till nästa nod? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> PUBLIK: Curr-> n är lika med new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON Hirschhorn: Så n är vilken del av struct? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 Heltalet. 753 00:37:46,020 --> 00:37:50,420 Och new_node är en pekare till en nod. 754 00:37:50,420 --> 00:37:51,880 Så vilken del av curr ska vi uppdatera? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Om inte n, vad är den andra? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noa, vad är den andra delen. 759 00:38:22,810 --> 00:38:23,570 >> PUBLIK: Åh, nästa. 760 00:38:23,570 --> 00:38:25,645 >> JASON Hirschhorn: Next, exakt. 761 00:38:25,645 --> 00:38:26,410 Exakt. 762 00:38:26,410 --> 00:38:28,770 Nästa är den rätta. 763 00:38:28,770 --> 00:38:31,540 Och vad mer behöver vi uppdatera, Noah? 764 00:38:31,540 --> 00:38:32,840 >> PUBLIK: Den pekare. 765 00:38:32,840 --> 00:38:34,840 >> JASON Hirschhorn: Så Vi uppdaterade ström. 766 00:38:34,840 --> 00:38:36,090 >> PUBLIK: Föregående-> nästa. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON Hirschhorn: Ja. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, vi ska göra en paus. 771 00:38:58,370 --> 00:39:02,200 Vem kan hjälpa oss här? 772 00:39:02,200 --> 00:39:03,385 Manu, vad ska vi göra? 773 00:39:03,385 --> 00:39:05,615 >> PUBLIK: Du måste ställa in det motsvarar nuvarande-> nästa. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Men gör det före den tidigare linjen. 776 00:39:11,630 --> 00:39:12,880 >> JASON Hirschhorn: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Något annat? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> PUBLIK: Jag tror inte att du är tänkt att ändra nuvarande-> nästa. 781 00:39:22,680 --> 00:39:29,270 Jag tror att du tänkt att göra STRÖM jämlikar STRÖM-> nästa att gå till nästa nod. 782 00:39:29,270 --> 00:39:30,500 >> JASON Hirschhorn: Så ledsen, var? 783 00:39:30,500 --> 00:39:32,680 På vilken linje? 784 00:39:32,680 --> 00:39:33,420 Denna linje? 785 00:39:33,420 --> 00:39:33,750 >> PUBLIK: Ja. 786 00:39:33,750 --> 00:39:35,745 Gör curr lika curr-> nästa. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON Hirschhorn: Så det är rätt eftersom strömmen är en 789 00:39:43,360 --> 00:39:45,220 pekare till en nod. 790 00:39:45,220 --> 00:39:48,550 Och vi vill att det ska peka på nästa nod av vad som komma idag 791 00:39:48,550 --> 00:39:49,930 pekade. 792 00:39:49,930 --> 00:39:54,410 Curr själv har en nästa. 793 00:39:54,410 --> 00:39:58,620 Men om vi skulle uppdatera curr.next, vi skulle uppdatera den faktiska anteckning 794 00:39:58,620 --> 00:40:01,430 sig själv, inte var det pekaren pekade. 795 00:40:01,430 --> 00:40:02,680 Vad sägs om den här linjen, dock. 796 00:40:02,680 --> 00:40:05,160 797 00:40:05,160 --> 00:40:07,330 Avi? 798 00:40:07,330 --> 00:40:09,590 >> PUBLIK: Föregående-> nästa lika curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON Hirschhorn: Så återigen, är om föregående en pekare till en nod, nästa är prev-> den 801 00:40:19,440 --> 00:40:23,020 faktiska pekare i noden. 802 00:40:23,020 --> 00:40:27,190 Så detta skulle vara att uppdatera en Pekare i en nod till STRÖM. 803 00:40:27,190 --> 00:40:28,570 Vi vill inte att uppdatera en pekare i en nod. 804 00:40:28,570 --> 00:40:30,570 Vi vill uppdatera tidigare. 805 00:40:30,570 --> 00:40:31,850 Så hur gör vi det? 806 00:40:31,850 --> 00:40:34,250 >> PUBLIK: Det skulle bara vara bakåt. 807 00:40:34,250 --> 00:40:34,565 >> JASON Hirschhorn: Höger. 808 00:40:34,565 --> 00:40:35,560 Föregående är en pekare till en nod. 809 00:40:35,560 --> 00:40:38,750 Nu ska vi ändra den till en ny pekare till en nod. 810 00:40:38,750 --> 00:40:40,830 OK Låt oss flytta ner. 811 00:40:40,830 --> 00:40:41,940 Slutligen, det sistnämnda villkoret. 812 00:40:41,940 --> 00:40:44,896 Jeff, vad gör vi här? 813 00:40:44,896 --> 00:40:47,515 >> PUBLIK: Om värdet är lika med nuvarande-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON Hirschhorn: Förlåt. 816 00:40:51,300 --> 00:40:52,372 Åh herregud. 817 00:40:52,372 --> 00:40:54,330 Vad? 818 00:40:54,330 --> 00:40:55,580 Värde == curr-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Vad gör vi? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> PUBLIK: Du skulle befria vårt new_node, och sedan du skulle returnera false. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON Hirschhorn: Detta är vad vi har skrivit hittills. 825 00:41:23,460 --> 00:41:25,710 Är det någon som har något att lägga till innan vi gör? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 OK. 828 00:41:35,710 --> 00:41:36,960 Låt oss prova. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Kontroll kan nå slutet av ett icke-void funktion. 831 00:41:46,110 --> 00:41:48,310 Avi, vad som händer? 832 00:41:48,310 --> 00:41:51,380 >> PUBLIK: Ska man sätta retur sant utanför while-slingan? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON Hirschhorn: Jag vet inte. 835 00:41:54,400 --> 00:41:54,780 Vill du ha mig till? 836 00:41:54,780 --> 00:41:55,520 >> PUBLIK: Glöm det. 837 00:41:55,520 --> 00:41:56,350 Nej. 838 00:41:56,350 --> 00:41:57,180 >> JASON Hirschhorn: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> PUBLIK: Jag tror att du menade att sätta retur falskt i slutet 840 00:41:59,460 --> 00:42:02,230 av while-slingan. 841 00:42:02,230 --> 00:42:03,270 >> JASON Hirschhorn: Så där vill du att det ska gå? 842 00:42:03,270 --> 00:42:05,270 >> PUBLIK: Liksom utanför while-slingan. 843 00:42:05,270 --> 00:42:08,800 Så om du avslutar while-slinga som medel att du har nått slutet och 844 00:42:08,800 --> 00:42:09,980 ingenting har hänt. 845 00:42:09,980 --> 00:42:10,410 >> JASON Hirschhorn: OK. 846 00:42:10,410 --> 00:42:12,340 Så vad gör vi här? 847 00:42:12,340 --> 00:42:13,702 >> PUBLIK: Du returnera false där också. 848 00:42:13,702 --> 00:42:15,040 >> JASON Hirschhorn: Åh, vi göra det på båda ställena? 849 00:42:15,040 --> 00:42:15,650 >> PUBLIK: Ja. 850 00:42:15,650 --> 00:42:16,900 >> JASON Hirschhorn: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Ska vi gå? 853 00:42:26,160 --> 00:42:26,980 Åh herregud. 854 00:42:26,980 --> 00:42:27,290 Jag är ledsen. 855 00:42:27,290 --> 00:42:28,480 Jag ber om ursäkt för skärmen. 856 00:42:28,480 --> 00:42:30,530 Det är typ av freaking på oss. 857 00:42:30,530 --> 00:42:31,520 Så välj ett alternativ. 858 00:42:31,520 --> 00:42:35,260 Noll, per kod, avslutas programmet. 859 00:42:35,260 --> 00:42:36,700 Man lägger in något. 860 00:42:36,700 --> 00:42:37,990 Låt oss sätta tre. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 Insatsen var inte lyckat. 863 00:42:45,380 --> 00:42:46,500 Jag kommer att skriva ut. 864 00:42:46,500 --> 00:42:48,050 Jag har ingenting. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Kanske det var bara en lyckträff. 867 00:42:50,250 --> 00:42:52,810 Sätt i ett. 868 00:42:52,810 --> 00:42:55,770 Inte lyckat. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Låt oss gå igenom GDB riktigt snabbt för att kolla vad som händer. 871 00:43:02,400 --> 00:43:06,055 >> Minns gdb. / Namnet på din Programmet får oss in i GDB. 872 00:43:06,055 --> 00:43:07,610 Är det mycket att hantera? 873 00:43:07,610 --> 00:43:08,560 Den blinkande? 874 00:43:08,560 --> 00:43:10,400 Förmodligen. 875 00:43:10,400 --> 00:43:12,760 Blunda och ta några djupa andetag om du tröttnar 876 00:43:12,760 --> 00:43:13,580 att se på det. 877 00:43:13,580 --> 00:43:14,200 Jag är i GDB. 878 00:43:14,200 --> 00:43:15,830 Vad är det första jag gör i GDB? 879 00:43:15,830 --> 00:43:17,050 Vi måste räkna ut vad som händer här. 880 00:43:17,050 --> 00:43:17,310 Låt oss se. 881 00:43:17,310 --> 00:43:21,650 Vi har sex minuter till figur ut vad som händer. 882 00:43:21,650 --> 00:43:22,900 Break. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 Och vad ska jag göra? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Kör. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Låt oss välja ett alternativ. 889 00:43:34,160 --> 00:43:36,330 Och vad gör N göra? 890 00:43:36,330 --> 00:43:38,480 Nästa. 891 00:43:38,480 --> 00:43:38,950 Yeah. 892 00:43:38,950 --> 00:43:39,740 >> PUBLIK: Har du inte nämner - 893 00:43:39,740 --> 00:43:45,230 sa du inte att huvudet var det initialiseras till noll vid början. 894 00:43:45,230 --> 00:43:47,140 Men jag tyckte du sa att det var OK. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON Hirschhorn: Låt oss - låt oss titta i GDB, och sedan går vi tillbaka. 897 00:43:52,640 --> 00:43:54,910 Men det låter som du redan har några idéer om vad som händer. 898 00:43:54,910 --> 00:43:58,340 Så vi vill infoga något. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Vi har infoga. 901 00:44:00,150 --> 00:44:00,770 Ange en int. 902 00:44:00,770 --> 00:44:01,990 Vi kommer att sätta in tre. 903 00:44:01,990 --> 00:44:03,000 Och så är jag på den här raden. 904 00:44:03,000 --> 00:44:07,030 Hur går jag starta debugging insatsen kända funktion? 905 00:44:07,030 --> 00:44:08,280 Åh herregud. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 Det är en hel del. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Är det freaking mycket? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> PUBLIK: Åh, dog den. 912 00:44:21,680 --> 00:44:22,930 >> JASON Hirschhorn: Jag bara drog ut den. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 OK. 915 00:44:28,310 --> 00:44:29,560 >> PUBLIK: Kanske är det andra änden av kabeln. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON Hirschhorn: Wow. 918 00:44:39,470 --> 00:44:42,330 Så den nedersta raden - 919 00:44:42,330 --> 00:44:43,470 vad sa du? 920 00:44:43,470 --> 00:44:46,040 >> PUBLIK: Jag sa det ironiska i tekniska svårigheter i denna klass. 921 00:44:46,040 --> 00:44:46,410 >> JASON Hirschhorn: Jag vet. 922 00:44:46,410 --> 00:44:48,660 Om bara jag hade kontroll över den delen. 923 00:44:48,660 --> 00:44:49,910 [OHÖRBAR] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Det låter bra. 926 00:44:55,400 --> 00:44:58,680 Varför inte ni börja tänka på vad vi kunde ha gjort fel, 927 00:44:58,680 --> 00:45:01,140 och vi kommer att vara tillbaka i 90 sekunder. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, jag ska fråga dig hur man ska gå inne insert_node att felsöka den. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 Så det är där vi senast slutade. 932 00:46:31,460 --> 00:46:35,110 Hur kan jag gå in insert_node, Avica, för att undersöka vad som händer? 933 00:46:35,110 --> 00:46:36,360 Vad GDB-kommandot? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Break skulle inte ta mig in. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Har Marquise vet? 938 00:46:47,130 --> 00:46:48,240 >> PUBLIK: Vad? 939 00:46:48,240 --> 00:46:51,780 >> JASON Hirschhorn: Vad GDB-kommandot Jag använder för att gå in den här funktionen? 940 00:46:51,780 --> 00:46:52,070 >> PUBLIK: Steg? 941 00:46:52,070 --> 00:46:55,140 >> JASON Hirschhorn: Steg via S. Det tar mig inne. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing lite utrymme. 944 00:46:58,040 --> 00:46:59,120 Att allt ser ut som det kommer. 945 00:46:59,120 --> 00:47:00,370 Låt oss undersöka new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Det har lite minnesadress. 948 00:47:05,410 --> 00:47:07,440 Låt oss kolla - 949 00:47:07,440 --> 00:47:08,500 det är allt rätt. 950 00:47:08,500 --> 00:47:12,220 Så allt här verkar att arbeta på rätt sätt. 951 00:47:12,220 --> 00:47:14,530 >> PUBLIK: Vad är skillnaden mellan P och display? 952 00:47:14,530 --> 00:47:16,160 >> JASON Hirschhorn: P står för utskrift. 953 00:47:16,160 --> 00:47:19,310 Och så du frågar vad är det Skillnaden mellan det och det? 954 00:47:19,310 --> 00:47:22,330 I detta fall, ingenting. 955 00:47:22,330 --> 00:47:26,960 Men generellt finns det vissa skillnader. 956 00:47:26,960 --> 00:47:28,220 Och du bör titta i GDB manualen. 957 00:47:28,220 --> 00:47:29,560 Men i detta fall, ingenting. 958 00:47:29,560 --> 00:47:31,460 Vi tenderar att använda skriva ut, men eftersom Vi behöver inte göra mycket mer än 959 00:47:31,460 --> 00:47:33,960 skriva ut ett enskilt värde. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 Så vi är på rad 80 i vår kod, inställning nod * STRÖM lika med listan. 962 00:47:40,300 --> 00:47:42,500 Låt oss skriva ut Curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Det är lika med listan. 965 00:47:46,840 --> 00:47:48,850 Söt. 966 00:47:48,850 --> 00:47:49,340 Vänta. 967 00:47:49,340 --> 00:47:50,590 Det är lika med något. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Det verkar inte rätt. 970 00:47:56,190 --> 00:47:56,840 Så där. 971 00:47:56,840 --> 00:47:59,470 Det är för att i GDB, rätt, om det är den linje du är på det 972 00:47:59,470 --> 00:48:00,330 har inte exekveras än. 973 00:48:00,330 --> 00:48:03,100 Så du måste verkligen skriva bredvid exekvera linjen 974 00:48:03,100 --> 00:48:05,230 innan du ser resultatet. 975 00:48:05,230 --> 00:48:06,680 Så här är vi. 976 00:48:06,680 --> 00:48:09,490 Vi avrättades just denna linje, tidigare lika med noll. 977 00:48:09,490 --> 00:48:13,590 Så återigen, om vi skriver ut tidigare Vi kommer inte se något konstigt. 978 00:48:13,590 --> 00:48:18,680 Men om vi faktiskt utför det linje, sedan får vi se 979 00:48:18,680 --> 00:48:20,380 att den linjen arbetade. 980 00:48:20,380 --> 00:48:21,060 >> Så vi har curr. 981 00:48:21,060 --> 00:48:23,180 De är båda bra. 982 00:48:23,180 --> 00:48:24,010 Rätt? 983 00:48:24,010 --> 00:48:28,130 Nu är vi på den här linjen här. 984 00:48:28,130 --> 00:48:29,310 Även curr inte lika null. 985 00:48:29,310 --> 00:48:31,110 Tja, vad gör STRÖM lika? 986 00:48:31,110 --> 00:48:32,450 Vi såg bara det motsvarade noll. 987 00:48:32,450 --> 00:48:33,210 Vi skrivs ut. 988 00:48:33,210 --> 00:48:35,110 Jag ska skriva ut den igen. 989 00:48:35,110 --> 00:48:36,720 Så är att medan slinga kommer att köra? 990 00:48:36,720 --> 00:48:37,270 >> PUBLIK: Nej. 991 00:48:37,270 --> 00:48:39,790 >> JASON Hirschhorn: Så när jag skrev att linje, ser du att vi hoppade hela vägen 992 00:48:39,790 --> 00:48:41,390 ner till botten, return false. 993 00:48:41,390 --> 00:48:44,520 Och då kommer vi att returnera false och gå tillbaka till vårt program och 994 00:48:44,520 --> 00:48:48,020 så småningom skriva ut, som vi såg, insatsen var inte lyckat. 995 00:48:48,020 --> 00:48:51,010 Så, någon som har några idéer om vad vi behöver göra för att fixa detta? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Jag kommer att vänta tills jag ser ett par händer gå upp. 998 00:48:57,570 --> 00:48:58,830 Vi ville inte köra här. 999 00:48:58,830 --> 00:49:01,660 Tänk, det var den första sak som vi gjorde. 1000 00:49:01,660 --> 00:49:02,430 Jag tänker inte göra ett par. 1001 00:49:02,430 --> 00:49:03,670 Jag kommer att göra några. 1002 00:49:03,670 --> 00:49:04,830 Eftersom ett par betyder två. 1003 00:49:04,830 --> 00:49:07,620 Jag väntar på mer än två. 1004 00:49:07,620 --> 00:49:10,690 >> Den första insättnings, Curr, som standard är lika med noll. 1005 00:49:10,690 --> 00:49:14,050 Och denna slinga endast utför om curr inte är noll. 1006 00:49:14,050 --> 00:49:18,740 Så hur kan jag komma runt detta? 1007 00:49:18,740 --> 00:49:19,990 Jag ser tre händer. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Jag väntar på mer än tre. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, vad tror du? 1012 00:49:35,940 --> 00:49:37,730 >> PUBLIK: Tja, om du behöver det för att köra mer än en gång, du bara 1013 00:49:37,730 --> 00:49:39,948 ändra den till en gör-while-slinga. 1014 00:49:39,948 --> 00:49:41,250 >> JASON Hirschhorn: OK. 1015 00:49:41,250 --> 00:49:44,240 Kommer att lösa våra problem, men? 1016 00:49:44,240 --> 00:49:47,750 >> PUBLIK: I detta fall nej på grund av det faktum att den är tom. 1017 00:49:47,750 --> 00:49:52,150 Så då har du förmodligen bara behöver lägga till ett uttalande att om de slingutgångarna 1018 00:49:52,150 --> 00:49:55,312 då måste man vara i slutet av listan, då du 1019 00:49:55,312 --> 00:49:56,562 kan bara infoga det. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON Hirschhorn: Jag gillar det. 1022 00:49:59,680 --> 00:50:00,500 Det är vettigt. 1023 00:50:00,500 --> 00:50:03,390 Om slingan går ut - 1024 00:50:03,390 --> 00:50:04,800 eftersom det kommer att returnera false här. 1025 00:50:04,800 --> 00:50:08,220 Så om de slingutgångarna, då är vi på I slutet av listan, eller kanske 1026 00:50:08,220 --> 00:50:10,690 börja på en lista om det finns ingenting i den, som är densamma som i slutet. 1027 00:50:10,690 --> 00:50:12,770 Så nu vill vi sätta in något här. 1028 00:50:12,770 --> 00:50:17,380 Så hur koden ser ut, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> PUBLIK: Om du redan har noden malloced, kan du bara säga 1030 00:50:21,600 --> 00:50:25,400 new_node-> nästa lika med noll, eftersom det måste vara i slutet. 1031 00:50:25,400 --> 00:50:27,510 Eller new_node-> nästa lika med noll. 1032 00:50:27,510 --> 00:50:27,765 >> JASON Hirschhorn: OK. 1033 00:50:27,765 --> 00:50:28,190 Ursäkta. 1034 00:50:28,190 --> 00:50:35,760 New_node-> nästa lika med noll eftersom vi är i slutet. 1035 00:50:35,760 --> 00:50:36,460 Det betyder inte lägga den i. 1036 00:50:36,460 --> 00:50:37,710 Hur ska vi lägga den i listan? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Rätt. 1039 00:50:46,460 --> 00:50:47,750 Det är bara att sätta den lika med. 1040 00:50:47,750 --> 00:50:50,940 Nej hur gör vi faktiskt lägga den på listan? 1041 00:50:50,940 --> 00:50:54,170 Vad är det som pekar på slutet av listan? 1042 00:50:54,170 --> 00:50:56,090 >> PUBLIK: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON Hirschhorn: Förlåt? 1044 00:50:57,566 --> 00:50:59,440 >> PUBLIK: Head pekar till slutet av listan. 1045 00:50:59,440 --> 00:51:01,480 >> JASON Hirschhorn: Om det finns ingenting i listan, är huvudet pekar på 1046 00:51:01,480 --> 00:51:04,170 slutet av listan. 1047 00:51:04,170 --> 00:51:06,920 Så det kommer att arbeta för första insättningen. 1048 00:51:06,920 --> 00:51:09,810 Vad händer om det finns ett par saker i listan? 1049 00:51:09,810 --> 00:51:12,470 Än vi inte vill ställa head lika med new_node. 1050 00:51:12,470 --> 00:51:13,790 Vad vill vi göra där? 1051 00:51:13,790 --> 00:51:15,610 Yeah? 1052 00:51:15,610 --> 00:51:16,860 Förmodligen föregående. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Kommer det att fungera? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Minns att föregående är bara en pekare till en nod. 1057 00:51:33,050 --> 00:51:34,770 Och tidigare är en lokal variabel. 1058 00:51:34,770 --> 00:51:38,080 Så denna linje kommer att sätta en lokal variabel, tidigare, är lika med eller 1059 00:51:38,080 --> 00:51:39,380 pekar på den nya noden. 1060 00:51:39,380 --> 00:51:41,500 Det kommer faktiskt inte lägga den i vår lista, men. 1061 00:51:41,500 --> 00:51:44,330 Hur ska vi lägga den i vår lista? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> PUBLIK: Jag tror att du gör ström-> nästa. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON Hirschhorn: OK. 1066 00:51:52,550 --> 00:51:54,010 STRÖM-> nästa. 1067 00:51:54,010 --> 00:51:58,768 Så återigen, den enda anledningen till att vi är nere här är, vad betyder ström lika? 1068 00:51:58,768 --> 00:51:59,760 >> PUBLIK: Lika med noll. 1069 00:51:59,760 --> 00:52:01,790 >> JASON Hirschhorn: Och så vad händer om vi gör null-> next? 1070 00:52:01,790 --> 00:52:02,810 Vad är det vi kommer att få? 1071 00:52:02,810 --> 00:52:04,060 Vi får en segmentering fel. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> PUBLIK: Do curr lika med noll. 1074 00:52:08,880 --> 00:52:10,760 >> JASON Hirschhorn: Det är samma sak som föregående, men eftersom det finns 1075 00:52:10,760 --> 00:52:12,820 en lokal variabel vi ställer som är lika med detta nya noden. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Låt oss gå tillbaka till vår bild för att sätta in något. 1078 00:52:20,920 --> 00:52:25,500 Säg att vi sätter in i slutet av listan, så här. 1079 00:52:25,500 --> 00:52:30,010 Vi har en aktuell pekare som är pekar på null och en tidigare punkt 1080 00:52:30,010 --> 00:52:32,800 som är riktad till 8. 1081 00:52:32,800 --> 00:52:35,330 Så vad gör vi behöver uppdatera, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> PUBLIK: Tidigare-> next? 1083 00:52:36,680 --> 00:52:41,980 >> JASON Hirschhorn: Tidigare-> Nästa är vad vi vill uppdatera eftersom det 1084 00:52:41,980 --> 00:52:44,960 faktiskt kommer att sätta in den på I slutet av listan. 1085 00:52:44,960 --> 00:52:47,220 Vi har fortfarande en bugg, fast, att vi kommer att stöta på. 1086 00:52:47,220 --> 00:52:50,090 Vad är det bugg? 1087 00:52:50,090 --> 00:52:50,790 Yeah? 1088 00:52:50,790 --> 00:52:53,860 >> PUBLIK: Det kommer att återvända falskt i det här fallet? 1089 00:52:53,860 --> 00:52:56,380 >> JASON Hirschhorn: Åh, är är kommer att returnera false. 1090 00:52:56,380 --> 00:52:57,430 Men det finns en annan bugg. 1091 00:52:57,430 --> 00:52:58,930 Så vi måste sätta i gengäld sant. 1092 00:52:58,930 --> 00:53:01,370 >> PUBLIK: Har tidigare fortfarande lika null i toppen av listan? 1093 00:53:01,370 --> 00:53:03,645 >> JASON Hirschhorn: Så förra fortfarande är lika med noll i början. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Så hur kan vi komma över det? 1096 00:53:10,440 --> 00:53:10,950 Yeah? 1097 00:53:10,950 --> 00:53:15,280 >> PUBLIK: Jag tror att du kan göra en kontroll innan while-slingan för att se om det är 1098 00:53:15,280 --> 00:53:16,610 en tom lista. 1099 00:53:16,610 --> 00:53:17,000 >> JASON Hirschhorn: OK. 1100 00:53:17,000 --> 00:53:17,710 Så låt oss gå hit. 1101 00:53:17,710 --> 00:53:18,530 Gör en kontroll. 1102 00:53:18,530 --> 00:53:19,380 Om - 1103 00:53:19,380 --> 00:53:20,770 >> PUBLIK: Så om huvudet är lika med är lika med noll. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON Hirschhorn: Om huvudet är lika är lika med noll - 1106 00:53:26,320 --> 00:53:27,790 som kommer att tala om för oss om det är en tom lista. 1107 00:53:27,790 --> 00:53:31,090 >> PUBLIK: Och sedan göra huvudet lika nytt. 1108 00:53:31,090 --> 00:53:34,740 >> JASON Hirschhorn: Head lika new_node? 1109 00:53:34,740 --> 00:53:35,730 Och vad behöver vi göra? 1110 00:53:35,730 --> 00:53:37,020 >> PUBLIK: Och då du returnerar sant. 1111 00:53:37,020 --> 00:53:37,535 >> JASON Hirschhorn: Inte riktigt. 1112 00:53:37,535 --> 00:53:38,785 Vi missar ett steg. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> PUBLIK: New_node nästa måste peka på null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON Hirschhorn: Exakt, Alden. 1116 00:53:44,570 --> 00:53:46,600 Och då kan vi återvända sant. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 Men det är fortfarande en bra idé att göra saker i slutet av listan, eller hur? 1119 00:53:51,630 --> 00:53:51,950 Okej. 1120 00:53:51,950 --> 00:53:54,450 Vi fortfarande kan faktiskt få till slutet av listan. 1121 00:53:54,450 --> 00:53:57,870 Så är den här koden bra om vi är på slutet av listan och det finns några 1122 00:53:57,870 --> 00:53:59,120 saker i listan? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Rätt? 1125 00:54:02,040 --> 00:54:03,540 Eftersom vi har fortfarande Marcus idé. 1126 00:54:03,540 --> 00:54:06,870 Vi skulle kunna gå ur denna slinga, eftersom vi är i slutet av listan. 1127 00:54:06,870 --> 00:54:09,308 Så gör vi fortfarande vill ha det koden här nere? 1128 00:54:09,308 --> 00:54:10,520 >> PUBLIK: Ja. 1129 00:54:10,520 --> 00:54:11,000 >> JASON Hirschhorn: Ja. 1130 00:54:11,000 --> 00:54:14,190 Och vad behöver vi för att ändra det till? 1131 00:54:14,190 --> 00:54:15,440 Sant. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Låter det bra till alla så långt? 1134 00:54:21,640 --> 00:54:22,420 Någon som har någon - 1135 00:54:22,420 --> 00:54:23,480 Avi, har du något att tillägga? 1136 00:54:23,480 --> 00:54:23,920 >> PUBLIK: Nej. 1137 00:54:23,920 --> 00:54:25,276 >> JASON Hirschhorn: OK. 1138 00:54:25,276 --> 00:54:27,010 Så vi har gjort ett par förändringar. 1139 00:54:27,010 --> 00:54:29,540 Vi har gjort denna kontroll innan vi gick in på en tom lista. 1140 00:54:29,540 --> 00:54:31,790 Så vi har tagit hand om en tom lista. 1141 00:54:31,790 --> 00:54:35,500 Och här tog vi hand om att sätta in något i slutet av listan. 1142 00:54:35,500 --> 00:54:38,930 Så det verkar som om detta medan slinga tagande hand om saker i mellan, 1143 00:54:38,930 --> 00:54:41,920 någonstans i listan, om det är saker på listan. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Låt oss köra programmet igen. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Inte lyckat. 1148 00:54:50,755 --> 00:54:52,190 >> PUBLIK: Du gjorde inte det. 1149 00:54:52,190 --> 00:54:53,940 >> JASON Hirschhorn: Åh, Jag gjorde inte det. 1150 00:54:53,940 --> 00:54:56,250 Bra punkt, Michael. 1151 00:54:56,250 --> 00:54:57,500 Låt oss lägga en make knuten. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Linje 87 finns det ett fel. 1154 00:55:04,830 --> 00:55:05,420 Linje 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, var detta den linje du gav mig. 1156 00:55:06,600 --> 00:55:08,962 Vad är fel? 1157 00:55:08,962 --> 00:55:10,710 >> PUBLIK: Det måste vara null. 1158 00:55:10,710 --> 00:55:11,000 >> JASON Hirschhorn: Excellent. 1159 00:55:11,000 --> 00:55:11,630 Exakt rätt. 1160 00:55:11,630 --> 00:55:13,290 Det bör vara noll. 1161 00:55:13,290 --> 00:55:15,210 Låt oss göra igen. 1162 00:55:15,210 --> 00:55:17,220 Sammanställ. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Låt oss sätta tre. 1165 00:55:19,400 --> 00:55:20,570 Insatsen var framgångsrik. 1166 00:55:20,570 --> 00:55:21,660 Låt oss skriva ut den. 1167 00:55:21,660 --> 00:55:23,590 Åh, om bara vi kunde kontrollera. 1168 00:55:23,590 --> 00:55:25,500 Men vi har inte gjort det skriva ut fungerar ännu. 1169 00:55:25,500 --> 00:55:27,840 Låt oss komma in något annat. 1170 00:55:27,840 --> 00:55:29,090 Vad ska vi komma in? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> PUBLIK: Sju. 1173 00:55:31,940 --> 00:55:33,340 >> JASON Hirschhorn: Seven? 1174 00:55:33,340 --> 00:55:34,590 >> PUBLIK: Ja. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON Hirschhorn: Vi har en seg fel. 1177 00:55:39,780 --> 00:55:43,760 Så vi fick en, men vi klart kan inte få två. 1178 00:55:43,760 --> 00:55:45,690 Det är 05:07. 1179 00:55:45,690 --> 00:55:48,370 Så vi kan felsöka detta under tre minuter. 1180 00:55:48,370 --> 00:55:51,240 Men jag kommer att lämna oss här och gå vidare till hashtabeller. 1181 00:55:51,240 --> 00:55:54,290 Men återigen, svaren för denna kod Jag kommer att skicka den till dig i lite. 1182 00:55:54,290 --> 00:55:55,440 Vi är mycket nära den. 1183 00:55:55,440 --> 00:55:58,300 Jag rekommenderar varmt att du räkna ut vad som händer här och fixa det. 1184 00:55:58,300 --> 00:56:02,400 Så jag kommer att skicka dig koden som bra plus att den lösning - 1185 00:56:02,400 --> 00:56:03,670 förmodligen lösningen senare. 1186 00:56:03,670 --> 00:56:05,110 Först denna kod. 1187 00:56:05,110 --> 00:56:08,290 >> Det andra jag vill göra innan vi fullföljande är att vi har inte befriat någonting. 1188 00:56:08,290 --> 00:56:10,370 Så jag vill visa dig vad valgrind ser ut. 1189 00:56:10,370 --> 00:56:14,310 Om vi ​​kör valgrind gränser på vårt program,. / kopplat. 1190 00:56:14,310 --> 00:56:22,540 Återigen, enligt denna bild, vi bör köra valgrind med någon typ av 1191 00:56:22,540 --> 00:56:26,410 alternativ, i detta fall - Läckagekontroll = full. 1192 00:56:26,410 --> 00:56:27,660 Så låt oss skriva valgrind - Läckagekontroll = full. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Så detta kommer att köras valgrind på vårt program. 1195 00:56:35,080 --> 00:56:37,000 Och nu programmet faktiskt körs. 1196 00:56:37,000 --> 00:56:40,190 Så vi kommer att köra det precis som innan, sätta något i. 1197 00:56:40,190 --> 00:56:40,830 Jag kommer att sätta in tre. 1198 00:56:40,830 --> 00:56:41,790 Det fungerar. 1199 00:56:41,790 --> 00:56:43,202 Jag tänker inte försöka sätta in något annat för att vi ska 1200 00:56:43,202 --> 00:56:44,710 få en seg falskt i det fallet. 1201 00:56:44,710 --> 00:56:46,700 Så jag ska bara sluta. 1202 00:56:46,700 --> 00:56:50,160 >> Och nu ser här nere läcka och heap sammanfattning. 1203 00:56:50,160 --> 00:56:52,310 Dessa är de bra saker som du vill checka ut. 1204 00:56:52,310 --> 00:56:56,780 Så högen sammanfattningen - det står i bruk vid avfart - åtta byte i ett block. 1205 00:56:56,780 --> 00:56:58,370 Det ena blocket är nod vi malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, du sa innan en nod är åtta bites eftersom det har heltalet 1207 00:57:02,230 --> 00:57:02,680 och pekaren. 1208 00:57:02,680 --> 00:57:04,550 Så det är vår nod. 1209 00:57:04,550 --> 00:57:08,170 Och då säger vi använt malloc sju gånger och vi befriade 1210 00:57:08,170 --> 00:57:08,940 något sex gånger. 1211 00:57:08,940 --> 00:57:13,680 Men vi aldrig kallade fria, så jag har ingen aning om vad det talar om. 1212 00:57:13,680 --> 00:57:18,490 >> Men det räcker med att säga att när du programkörningar, är malloc som kallas 1213 00:57:18,490 --> 00:57:20,330 på vissa andra platser som vi behöver inte oroa dig. 1214 00:57:20,330 --> 00:57:22,460 Så malloc troligen kallades på vissa ställen. 1215 00:57:22,460 --> 00:57:24,480 Vi behöver inte oroa dig där. 1216 00:57:24,480 --> 00:57:26,240 Men detta är verkligen oss. 1217 00:57:26,240 --> 00:57:27,380 Denna första raden är oss. 1218 00:57:27,380 --> 00:57:28,320 Vi lämnade det blocket. 1219 00:57:28,320 --> 00:57:30,330 Och du kan se att här i läckage sammanfattning. 1220 00:57:30,330 --> 00:57:31,950 Fortfarande nås - 1221 00:57:31,950 --> 00:57:32,930 åtta byte i ett block. 1222 00:57:32,930 --> 00:57:34,100 Det innebär att minnet - 1223 00:57:34,100 --> 00:57:35,730 Vi har läckt ut att minnet. 1224 00:57:35,730 --> 00:57:37,570 Definitivt förlorade - 1225 00:57:37,570 --> 00:57:38,770 något försvinner för gott. 1226 00:57:38,770 --> 00:57:40,590 Generellt kommer du inte se något där. 1227 00:57:40,590 --> 00:57:44,780 Fortfarande nås är i allmänhet där du kommer att se saker, där du vill 1228 00:57:44,780 --> 00:57:48,900 att titta för att se vad koden ska du har befriat men du glömde att befria. 1229 00:57:48,900 --> 00:57:53,170 >> Och sedan, om så inte var fallet, om vi gjorde gratis allt, 1230 00:57:53,170 --> 00:57:54,360 vi kan kontrollera det. 1231 00:57:54,360 --> 00:57:57,330 Låt oss bara köra programmet inte att sätta in något. 1232 00:57:57,330 --> 00:57:59,800 Du ser här nere i bruk vid avfart - 1233 00:57:59,800 --> 00:58:01,310 noll byte i noll block. 1234 00:58:01,310 --> 00:58:06,310 Det betyder att vi hade ingenting kvar när programmet avslutas. 1235 00:58:06,310 --> 00:58:12,090 Så innan du slår i pset6, kör valgrind och se till att du inte har 1236 00:58:12,090 --> 00:58:15,310 något minne läckor i ditt program. 1237 00:58:15,310 --> 00:58:17,910 Om du har några frågor med valgrind, tveka inte att nå ut. 1238 00:58:17,910 --> 00:58:18,700 Men det är hur du använder den. 1239 00:58:18,700 --> 00:58:20,890 Mycket enkelt - se om du har används vid avfart - 1240 00:58:20,890 --> 00:58:22,270 några byte i några block. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Så vi arbetade på skäret nod. 1243 00:58:29,580 --> 00:58:33,840 Jag hade två andra funktioner här - skriva ut noder och fria noder. 1244 00:58:33,840 --> 00:58:37,780 Återigen, dessa är funktioner som är kommer att vara bra för dig att träna 1245 00:58:37,780 --> 00:58:40,990 eftersom de hjälper dig inte bara med dessa prov övningar men också 1246 00:58:40,990 --> 00:58:42,180 på problemet inställd. 1247 00:58:42,180 --> 00:58:44,230 De kart på ganska nära till saker du kommer att behöva göra i 1248 00:58:44,230 --> 00:58:45,010 problem set. 1249 00:58:45,010 --> 00:58:47,640 Men jag vill se till att vi rör på allting. 1250 00:58:47,640 --> 00:58:50,400 Och hashtabeller är också avgörande för vad vi gör i avsnittet här 1251 00:58:50,400 --> 00:58:51,980 vecka - eller i det problemet set. 1252 00:58:51,980 --> 00:58:55,200 >> Så vi kommer att avsluta avsnittet talar om hashtabeller. 1253 00:58:55,200 --> 00:58:58,140 Om du märker att jag gjorde en liten hashtabell. 1254 00:58:58,140 --> 00:59:00,020 Det är inte vad vi pratar om dock. 1255 00:59:00,020 --> 00:59:03,540 Vi talar om en annan typ av hash-tabeller. 1256 00:59:03,540 --> 00:59:07,300 Och i sin kärna, en hashtabell är inget annat än en 1257 00:59:07,300 --> 00:59:08,860 matris plus en hashfunktion. 1258 00:59:08,860 --> 00:59:11,150 Vi kommer att prata om lite bara för att se till att alla förstår vad en 1259 00:59:11,150 --> 00:59:12,110 hashfunktion visas. 1260 00:59:12,110 --> 00:59:15,420 Och jag säger nu att det är inget mer än två saker - 1261 00:59:15,420 --> 00:59:18,590 en matris och en hashfunktion. 1262 00:59:18,590 --> 00:59:20,716 Och här är de steg genom som det verkar. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Det är vår samling. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Det är vår uppgift. 1267 00:59:39,460 --> 00:59:43,180 I synnerhet hashfunktioner behöver göra ett par saker med detta. 1268 00:59:43,180 --> 00:59:45,040 Jag ska prata specifikt om detta problem set. 1269 00:59:45,040 --> 00:59:46,450 Det kommer förmodligen att ta i en sträng. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 Och vad kommer det att återvända? 1272 00:59:51,770 --> 00:59:52,640 Vilken datatyp? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Din hashfunktion tillbaka? 1275 00:59:55,760 --> 00:59:58,760 Ett heltal. 1276 00:59:58,760 --> 01:00:01,700 Så detta är vad hash Tabellen består av - 1277 01:00:01,700 --> 01:00:05,430 en tabell i form av matris och en hashfunktion. 1278 01:00:05,430 --> 01:00:06,010 Hur fungerar det? 1279 01:00:06,010 --> 01:00:07,300 Det fungerar i tre steg. 1280 01:00:07,300 --> 01:00:08,740 Vi ger det en nyckel. 1281 01:00:08,740 --> 01:00:11,470 I det här fallet kommer vi att ge det ett snöre. 1282 01:00:11,470 --> 01:00:18,140 Vi kallar hashfunktionen per steg ett på nyckeln och vi får ett värde. 1283 01:00:18,140 --> 01:00:20,310 >> Specifikt ska vi säga vi får ett heltal. 1284 01:00:20,310 --> 01:00:25,630 Att heltal, det finns mycket specifika gränser för vad som heltal kan vara. 1285 01:00:25,630 --> 01:00:28,880 I det här exemplet, vår array är av storlek tre. 1286 01:00:28,880 --> 01:00:32,330 Vilka siffror kan det heltal vara. 1287 01:00:32,330 --> 01:00:35,970 Vad är utbudet av giltiga värden för som heltal, returtypen av detta 1288 01:00:35,970 --> 01:00:37,220 hashfunktion? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Noll, ett och två. 1291 01:00:42,110 --> 01:00:46,060 Poängen med hashfunktionen är att räkna ut den plats i arrayen 1292 01:00:46,060 --> 01:00:47,790 där vår nyckel går. 1293 01:00:47,790 --> 01:00:51,290 Det finns bara tre möjliga platser här - 1294 01:00:51,290 --> 01:00:52,130 noll, ett eller två. 1295 01:00:52,130 --> 01:00:55,360 Så här fungerar bättre avkastning noll, ett eller två. 1296 01:00:55,360 --> 01:00:58,740 Några giltig indice i denna samling. 1297 01:00:58,740 --> 01:01:02,770 >> Och sedan beroende på var den återvänder, ni ser finns array öppen 1298 01:01:02,770 --> 01:01:03,730 bracket värdet. 1299 01:01:03,730 --> 01:01:05,800 Det är där vi sätter nyckeln. 1300 01:01:05,800 --> 01:01:11,280 Så vi kastar i pumpan, vi får ut noll. 1301 01:01:11,280 --> 01:01:15,540 Vid array fäste 0, sätter vi pumpa. 1302 01:01:15,540 --> 01:01:21,070 Vi kastar i katter, vi får ut en. 1303 01:01:21,070 --> 01:01:24,110 Vi sätter katten på en. 1304 01:01:24,110 --> 01:01:25,480 Vi lägger i spindel. 1305 01:01:25,480 --> 01:01:26,710 Vi får ut två. 1306 01:01:26,710 --> 01:01:30,200 Vi lägger spindel på array fäste två. 1307 01:01:30,200 --> 01:01:32,300 Det skulle vara så trevligt om det fungerade så. 1308 01:01:32,300 --> 01:01:35,570 Men tyvärr, så vi får se, det är lite mer komplicerat. 1309 01:01:35,570 --> 01:01:37,570 >> Innan vi kommer dit, några frågor om denna grundläggande 1310 01:01:37,570 --> 01:01:38,820 installation av en hash-tabell? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 Detta är en bild av exakt vad vi ritade på tavlan. 1313 01:01:51,940 --> 01:01:55,420 Men eftersom vi drog det på tavlan, jag tänker inte gå in på det längre. 1314 01:01:55,420 --> 01:02:00,430 I huvudsak nycklar, den magiska svarta lådan - eller i detta fall, kricka låda - av en 1315 01:02:00,430 --> 01:02:02,410 hashfunktionen sätter dem i hinkar. 1316 01:02:02,410 --> 01:02:04,690 Och i det här exemplet är vi inte sätta namnet. 1317 01:02:04,690 --> 01:02:07,880 Vi sätter den tillhörande telefon antal namn i hinken. 1318 01:02:07,880 --> 01:02:10,430 Men du kan mycket väl bara sätta namn i hinken. 1319 01:02:10,430 --> 01:02:12,950 >> Detta är bara en bild av vad Vi drog på tavlan. 1320 01:02:12,950 --> 01:02:14,460 Vi har potentiella fallgropar, dock. 1321 01:02:14,460 --> 01:02:17,470 Och det finns två särskilt diabilder som jag vill gå över. 1322 01:02:17,470 --> 01:02:20,230 Den första är om en hashfunktion. 1323 01:02:20,230 --> 01:02:22,620 Så jag ställde frågan, vad gör en bra hashfunktion? 1324 01:02:22,620 --> 01:02:24,220 Jag ger två svar. 1325 01:02:24,220 --> 01:02:26,630 Den första är att det är deterministisk. 1326 01:02:26,630 --> 01:02:29,660 Inom ramen för hashfunktioner, vad innebär det? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 Ja? 1329 01:02:39,282 --> 01:02:42,850 >> PUBLIK: Det kan hitta den index i konstant tid? 1330 01:02:42,850 --> 01:02:43,810 >> JASON Hirschhorn: Det är inte vad det betyder. 1331 01:02:43,810 --> 01:02:44,725 Men det är en bra gissning. 1332 01:02:44,725 --> 01:02:46,100 Någon annan har en gissning vad detta betyder? 1333 01:02:46,100 --> 01:02:47,780 Att en bra hashfunktion är deterministisk? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> PUBLIK: Att en nyckel endast kan kartläggas till en plats i hash-tabellen. 1336 01:02:51,680 --> 01:02:53,070 >> JASON Hirschhorn: Det är exakt rätt. 1337 01:02:53,070 --> 01:02:57,430 Varje gång du sätter på pumpa, det alltid returnerar noll. 1338 01:02:57,430 --> 01:03:01,660 Om du sätter i pumpa och ditt hash returnerar noll, men har ett 1339 01:03:01,660 --> 01:03:06,060 sannolikhet att återvända något annat större än noll - 1340 01:03:06,060 --> 01:03:09,280 så kanske det kan återvända en ibland eller två andra tillfällen - 1341 01:03:09,280 --> 01:03:11,100 som inte är en bra hashfunktion. 1342 01:03:11,100 --> 01:03:11,800 Du har helt rätt. 1343 01:03:11,800 --> 01:03:15,680 Din hashfunktion ska returnera exakt samma tal, i detta fall, för 1344 01:03:15,680 --> 01:03:17,780 exakt samma sträng. 1345 01:03:17,780 --> 01:03:22,210 >> Kanske den returnerar exakt samma heltal för samma exakta strängen 1346 01:03:22,210 --> 01:03:24,430 oavsett kapitalisering. 1347 01:03:24,430 --> 01:03:27,980 Men i så fall är det fortfarande deterministisk eftersom flera saker 1348 01:03:27,980 --> 01:03:29,350 mappas på samma värde. 1349 01:03:29,350 --> 01:03:30,170 Det är bra. 1350 01:03:30,170 --> 01:03:32,615 Så länge som det finns endast en utgång för en viss ingång. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> OK. 1353 01:03:36,350 --> 01:03:38,340 Det andra är att det returnerar giltiga index. 1354 01:03:38,340 --> 01:03:40,220 Vi tog upp det tidigare. 1355 01:03:40,220 --> 01:03:41,860 Denna hash-funktion - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 en hashfunktion bör returnera giltiga index. 1358 01:03:46,840 --> 01:03:47,740 Så säger - 1359 01:03:47,740 --> 01:03:48,990 låt oss gå tillbaka till det här exemplet. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 Min hashfunktion räknar upp bokstäverna i ordet. 1362 01:03:57,540 --> 01:03:58,380 Det är hashfunktionen. 1363 01:03:58,380 --> 01:03:59,740 Och returnerar det heltal. 1364 01:03:59,740 --> 01:04:04,280 Så om jag har ordet A, är det kommer att återvända en. 1365 01:04:04,280 --> 01:04:06,900 Och det kommer att sätta ett här. 1366 01:04:06,900 --> 01:04:09,430 Vad händer om jag lägger i ordet fladdermus? 1367 01:04:09,430 --> 01:04:11,310 Det kommer att gå tillbaka tre. 1368 01:04:11,310 --> 01:04:12,560 Vart tar bat vägen? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> Det passar inte. 1371 01:04:19,750 --> 01:04:21,000 Men det måste gå någonstans. 1372 01:04:21,000 --> 01:04:23,340 Det här är min hashtabell trots allt, och allt måste gå någonstans. 1373 01:04:23,340 --> 01:04:24,590 Så var ska bat gå? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Några tankar? 1376 01:04:28,710 --> 01:04:29,450 Gissningar? 1377 01:04:29,450 --> 01:04:30,280 Goda gissningar? 1378 01:04:30,280 --> 01:04:31,220 >> PUBLIK: Noll. 1379 01:04:31,220 --> 01:04:32,120 >> JASON Hirschhorn: Varför noll? 1380 01:04:32,120 --> 01:04:35,990 >> PUBLIK: Eftersom tre modulo tre är noll? 1381 01:04:35,990 --> 01:04:38,620 >> JASON Hirschhorn: Tre modulo tre är noll. 1382 01:04:38,620 --> 01:04:40,810 Det är en bra gissning, och det är rätt. 1383 01:04:40,810 --> 01:04:43,870 Så i det här fallet det ska förmodligen gå på noll. 1384 01:04:43,870 --> 01:04:51,080 Så ett bra sätt att se till att denna hash returnerar endast giltiga index 1385 01:04:51,080 --> 01:04:54,580 att modulo det av storleken på tabellen. 1386 01:04:54,580 --> 01:04:57,360 Om du modulo oavsett denna avkastning genom tre, du alltid kommer att få 1387 01:04:57,360 --> 01:05:00,930 någonting mellan noll, ett, och två. 1388 01:05:00,930 --> 01:05:05,160 Och om detta alltid återvänder sju, och du alltid modulo av tre, är du 1389 01:05:05,160 --> 01:05:06,030 alltid kommer att få samma sak. 1390 01:05:06,030 --> 01:05:09,270 >> Så det är fortfarande deterministiska om du modulo. 1391 01:05:09,270 --> 01:05:11,420 Men det kommer att se till att du aldrig få något - 1392 01:05:11,420 --> 01:05:12,940 en ogiltig industrin. 1393 01:05:12,940 --> 01:05:16,840 Generellt bör det modulo hända inuti din hashfunktion. 1394 01:05:16,840 --> 01:05:18,240 Så du behöver inte oroa dig för detta. 1395 01:05:18,240 --> 01:05:20,555 Du kan bara se till att detta är ett giltigt indice. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Eventuella frågor om detta potentiell fallgrop? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> OK. 1400 01:05:39,060 --> 01:05:40,290 Och där går vi. 1401 01:05:40,290 --> 01:05:42,890 Nästa potentiell fallgrop, och Detta är den stora. 1402 01:05:42,890 --> 01:05:46,880 Vad händer om två tangenter karta till samma värde? 1403 01:05:46,880 --> 01:05:49,350 Så det finns två sätt att hantera detta. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 Den första heter linjär sondering, som jag är 1406 01:05:56,020 --> 01:05:57,300 inte kommer att gå över. 1407 01:05:57,300 --> 01:06:01,120 Men du bör känna till hur som fungerar och vad det är. 1408 01:06:01,120 --> 01:06:05,610 >> Det andra jag kommer att gå över eftersom det är den som många 1409 01:06:05,610 --> 01:06:08,290 människor kommer förmodligen att hamna beslutar att använda i deras problem set. 1410 01:06:08,290 --> 01:06:09,820 Naturligtvis behöver du inte till. 1411 01:06:09,820 --> 01:06:15,280 Men om problemet set, många människor tenderar att välja att skapa en hashtabell 1412 01:06:15,280 --> 01:06:17,950 med separat chaining för att genomföra deras ordlista. 1413 01:06:17,950 --> 01:06:21,390 Så vi kommer att gå igenom vad det innebär för att skapa en hash-tabell med 1414 01:06:21,390 --> 01:06:23,890 separat kedja. 1415 01:06:23,890 --> 01:06:26,260 >> Så jag satte på pumpa. 1416 01:06:26,260 --> 01:06:29,560 Den returnerar noll. 1417 01:06:29,560 --> 01:06:31,410 Och jag satte pumpa här. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Sedan satte jag in - 1420 01:06:37,930 --> 01:06:39,922 vad är en Halloween-tema sak? 1421 01:06:39,922 --> 01:06:42,200 >> PUBLIK: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON Hirschhorn: Godis! 1423 01:06:42,770 --> 01:06:43,910 Det är en stor en. 1424 01:06:43,910 --> 01:06:47,760 Jag satte i godis, och godis ger mig också noll. 1425 01:06:47,760 --> 01:06:49,350 Vad ska jag göra? 1426 01:06:49,350 --> 01:06:51,940 Några idéer? 1427 01:06:51,940 --> 01:06:53,940 Eftersom du alla slags vet vad separat kedja är. 1428 01:06:53,940 --> 01:06:55,190 Så några idéer vad göra? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Yeah. 1431 01:06:59,110 --> 01:07:03,810 >> PUBLIK: Att sätta strängen faktiskt i hash-tabellen. 1432 01:07:03,810 --> 01:07:08,910 >> JASON Hirschhorn: Så vi ska dra bra här borta. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> PUBLIK: Har hashtable [OHÖRBAR] 1435 01:07:12,290 --> 01:07:16,640 den pekare som pekar på I början av en lista. 1436 01:07:16,640 --> 01:07:20,930 Och sedan har pumpa vara det första värdet i den länkade listan och godis vara 1437 01:07:20,930 --> 01:07:22,800 det andra värdet i den länkade listan. 1438 01:07:22,800 --> 01:07:23,420 >> JASON Hirschhorn: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, som var enastående. 1440 01:07:24,670 --> 01:07:26,160 Jag kommer att bryta ner det. 1441 01:07:26,160 --> 01:07:28,890 Marcus säger inte skriva över pumpa. 1442 01:07:28,890 --> 01:07:30,660 Det skulle vara dåligt. 1443 01:07:30,660 --> 01:07:33,640 Lägg inte godis någon annanstans. 1444 01:07:33,640 --> 01:07:35,390 Vi kommer att sätta dem båda på noll. 1445 01:07:35,390 --> 01:07:37,770 Men vi kommer att ta itu med sätta dem på noll 1446 01:07:37,770 --> 01:07:39,395 skapa en lista på noll. 1447 01:07:39,395 --> 01:07:42,430 Och vi kommer att skapa en lista med allt som mappas till noll. 1448 01:07:42,430 --> 01:07:47,960 Och det bästa sättet vi lärt oss att skapa en lista som kan växa och krympa 1449 01:07:47,960 --> 01:07:49,840 dynamiskt inte är inom annan matris. 1450 01:07:49,840 --> 01:07:51,510 Så inte en flerdimensionell array. 1451 01:07:51,510 --> 01:07:54,080 Men att bara skapa en länkad lista. 1452 01:07:54,080 --> 01:07:55,330 >> Så vad han föreslog - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Jag ska få ett nytt - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 är att skapa en array med pekare, en array av pekare. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Någon idé eller ledtråd vad typ av denna pekare bör vara? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> PUBLIK: Pekare till - 1461 01:08:27,250 --> 01:08:28,609 >> JASON Hirschhorn: Eftersom du sade en länkad lista, så - 1462 01:08:28,609 --> 01:08:29,520 >> PUBLIK: Node pekare? 1463 01:08:29,520 --> 01:08:30,670 >> JASON Hirschhorn: Node pekare. 1464 01:08:30,670 --> 01:08:32,830 Om saker i vår länkade Listan är noder då de 1465 01:08:32,830 --> 01:08:34,370 bör vara nod pekare. 1466 01:08:34,370 --> 01:08:35,939 Och vad gör de lika från början? 1467 01:08:35,939 --> 01:08:36,990 >> PUBLIK: Null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON Hirschhorn: Null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 Så det är vår tomt sak. 1471 01:08:46,080 --> 01:08:47,170 Pumpa återgår noll. 1472 01:08:47,170 --> 01:08:48,569 Vad gör vi? 1473 01:08:48,569 --> 01:08:49,609 Walk mig igenom det? 1474 01:08:49,609 --> 01:08:50,810 Egentligen Marcus gav mig redan. 1475 01:08:50,810 --> 01:08:52,439 Någon annan gå mig igenom det. 1476 01:08:52,439 --> 01:08:54,760 Vad vi gör när vi - 1477 01:08:54,760 --> 01:08:56,609 detta är mycket lik vad vi gör bara. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> PUBLIK: Jag kommer att ta en gissning. 1480 01:08:59,090 --> 01:09:01,250 Så när du får godis. 1481 01:09:01,250 --> 01:09:01,640 >> JASON Hirschhorn: Ja. 1482 01:09:01,640 --> 01:09:03,120 Nåväl, vi fick pumpa. 1483 01:09:03,120 --> 01:09:03,870 Låt oss få vår första. 1484 01:09:03,870 --> 01:09:04,324 Vi fick pumpa. 1485 01:09:04,324 --> 01:09:04,779 >> PUBLIK: OK. 1486 01:09:04,779 --> 01:09:05,880 Pumpa återgår noll. 1487 01:09:05,880 --> 01:09:08,770 Så du lägga den i det. 1488 01:09:08,770 --> 01:09:10,810 Eller faktiskt, lägger du den i den länkade listan. 1489 01:09:10,810 --> 01:09:13,550 >> JASON Hirschhorn: Hur gör vi lägga den i den länkade listan? 1490 01:09:13,550 --> 01:09:15,479 >> PUBLIK: Åh, den verkliga syntax? 1491 01:09:15,479 --> 01:09:16,240 >> JASON Hirschhorn: Bara gå - 1492 01:09:16,240 --> 01:09:16,740 säga mer. 1493 01:09:16,740 --> 01:09:19,310 Vad gör vi? 1494 01:09:19,310 --> 01:09:22,100 >> PUBLIK: Du sätter bara den som den första noden. 1495 01:09:22,100 --> 01:09:22,675 >> JASON Hirschhorn: OK. 1496 01:09:22,675 --> 01:09:29,069 Så vi har vår nod, pumpa. 1497 01:09:29,069 --> 01:09:31,560 Och nu hur ska jag sätta in det? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> PUBLIK: Du tilldelar den till pekaren. 1500 01:09:37,090 --> 01:09:37,970 >> JASON Hirschhorn: Vilken pekare? 1501 01:09:37,970 --> 01:09:39,620 >> PUBLIK: Pekaren på noll. 1502 01:09:39,620 --> 01:09:41,420 >> JASON Hirschhorn: Så där gör detta? 1503 01:09:41,420 --> 01:09:42,810 >> PUBLIK: Att null just nu. 1504 01:09:42,810 --> 01:09:43,529 >> JASON Hirschhorn: Tja, det pekar på null. 1505 01:09:43,529 --> 01:09:44,499 Men jag sätter på pumpa. 1506 01:09:44,499 --> 01:09:46,053 Så var ska den peka? 1507 01:09:46,053 --> 01:09:46,880 >> PUBLIK: Att pumpa. 1508 01:09:46,880 --> 01:09:47,399 >> JASON Hirschhorn: Att pumpa. 1509 01:09:47,399 --> 01:09:48,760 Exakt. 1510 01:09:48,760 --> 01:09:50,010 Så här pekar på pumpa. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 Och varifrån kommer denna pekare i pumpa punkt? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 Till 1515 01:09:58,340 --> 01:09:58,590 >> PUBLIK: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON Hirschhorn: Att null. 1517 01:09:59,210 --> 01:10:00,460 Exakt. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Så vi bara insatt något i den länkade listan. 1520 01:10:05,140 --> 01:10:07,210 Vi skrev bara den här koden för att göra detta. 1521 01:10:07,210 --> 01:10:09,520 Nästan vi nästan fick det helt knäckt. 1522 01:10:09,520 --> 01:10:10,790 Nu sätter vi godis. 1523 01:10:10,790 --> 01:10:13,480 Vår godis går också till noll. 1524 01:10:13,480 --> 01:10:16,100 Så vad gör vi med godis? 1525 01:10:16,100 --> 01:10:18,790 >> Publik: Det beror på om eller inte vi försöker lösa det. 1526 01:10:18,790 --> 01:10:19,640 >> JASON Hirschhorn: Det är exakt rätt. 1527 01:10:19,640 --> 01:10:21,070 Det beror på om eller inte vi försöker lösa det. 1528 01:10:21,070 --> 01:10:22,660 Låt oss anta att vi inte är kommer att sortera det. 1529 01:10:22,660 --> 01:10:24,880 >> PUBLIK: Nåväl, när vi diskuterade innan, är det enklaste att bara lägga den 1530 01:10:24,880 --> 01:10:28,590 alldeles i början så pekaren från noll poäng till godis. 1531 01:10:28,590 --> 01:10:29,020 >> JASON Hirschhorn: OK. 1532 01:10:29,020 --> 01:10:29,380 Håll ut. 1533 01:10:29,380 --> 01:10:30,630 Låt mig skapa godis här. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Så denna pekare - 1536 01:10:35,150 --> 01:10:37,590 >> PUBLIK: Ja, det borde nu peka på godis. 1537 01:10:37,590 --> 01:10:40,580 Har sedan pekaren från godis peka på pumpa. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON Hirschhorn: Gillar det? 1540 01:10:44,560 --> 01:10:47,380 Och säga att vi fick en annan sak att kartlägga till noll? 1541 01:10:47,380 --> 01:10:48,660 >> PUBLIK: Tja, du bara göra samma sak? 1542 01:10:48,660 --> 01:10:50,290 >> JASON Hirschhorn: Gör samma sak. 1543 01:10:50,290 --> 01:10:53,700 Så i det här fallet, om vi inte vill hålla det sorteras det 1544 01:10:53,700 --> 01:10:55,270 låter ganska enkel. 1545 01:10:55,270 --> 01:10:59,920 Vi tar pekaren i indice som ges av vår hashfunktion. 1546 01:10:59,920 --> 01:11:03,830 Vi har som pekar på vår nya noden. 1547 01:11:03,830 --> 01:11:07,830 Och sedan vad det pekade till tidigare - 1548 01:11:07,830 --> 01:11:10,620 i detta fall noll, i andra fallet pumpa - 1549 01:11:10,620 --> 01:11:15,310 att, oavsett vad det pekar på tidigare, vi lägger in i nästa av 1550 01:11:15,310 --> 01:11:17,810 vår nya noden. 1551 01:11:17,810 --> 01:11:19,650 Vi ska sätta in något i början. 1552 01:11:19,650 --> 01:11:22,900 I själva verket är detta en mycket enklare än försöker hålla listan sorteras. 1553 01:11:22,900 --> 01:11:25,340 Men återigen, kommer sökningen att vara mer komplicerat på här. 1554 01:11:25,340 --> 01:11:28,300 Vi kommer alltid att gå till slutet. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Eventuella frågor om separat kedja? 1557 01:11:32,750 --> 01:11:34,690 Hur det fungerar? 1558 01:11:34,690 --> 01:11:35,820 Fråga dem nu. 1559 01:11:35,820 --> 01:11:39,260 Jag vill verkligen se till att du hela förstå detta innan vi beger oss ut. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> PUBLIK: Varför sätter pumpa och godis i samma 1562 01:11:52,060 --> 01:11:54,108 del av hash-tabell? 1563 01:11:54,108 --> 01:11:55,860 >> JASON Hirschhorn: Bra fråga. 1564 01:11:55,860 --> 01:11:59,140 Varför vi sätta dem i samma del av hash-tabell? 1565 01:11:59,140 --> 01:12:03,200 Tja, i det här fallet vår hashfunktion avkastningen noll för dem båda. 1566 01:12:03,200 --> 01:12:05,310 Så de behöver gå på indice noll eftersom det är där vi ska 1567 01:12:05,310 --> 01:12:07,420 leta efter dem om vi någonsin vill slå upp dem. 1568 01:12:07,420 --> 01:12:11,750 Igen, med en linjär sondering tillvägagångssätt Vi skulle inte sätta dem båda på noll. 1569 01:12:11,750 --> 01:12:13,900 Men i den separata kedjan strategi, vi ska sätta dem båda på noll 1570 01:12:13,900 --> 01:12:16,620 och sedan skapa en lista från noll. 1571 01:12:16,620 --> 01:12:20,140 >> Och vi vill inte skriva över pumpa bara för det för då kommer vi 1572 01:12:20,140 --> 01:12:21,860 anta att pumpa var aldrig införas. 1573 01:12:21,860 --> 01:12:25,230 Om vi ​​bara hålla en sak i plats som skulle vara dåligt. 1574 01:12:25,230 --> 01:12:28,590 Då skulle det inte finnas någon chans av oss någonsin - 1575 01:12:28,590 --> 01:12:31,660 om vi någonsin haft en dubblett, då vi skulle bara radera vår initiala värdet. 1576 01:12:31,660 --> 01:12:34,090 Så det är därför vi gör detta tillvägagångssätt. 1577 01:12:34,090 --> 01:12:36,580 Eller det är därför vi valde - men återigen, vi valde separat kedja tillvägagångssätt 1578 01:12:36,580 --> 01:12:39,670 där det finns många andra metoder man kunde välja. 1579 01:12:39,670 --> 01:12:41,185 Besvarar det din fråga? 1580 01:12:41,185 --> 01:12:41,660 >> OK. 1581 01:12:41,660 --> 01:12:42,910 Carlos. 1582 01:12:42,910 --> 01:12:46,130 1583 01:12:46,130 --> 01:12:47,720 Linjär sondering skulle innebära - 1584 01:12:47,720 --> 01:12:51,913 om vi hittade en kollision på noll, vi skulle se i nästa plats för att se om 1585 01:12:51,913 --> 01:12:54,310 det var öppet och lägga den där. 1586 01:12:54,310 --> 01:12:57,320 Och då vi tittar på nästa idrott och se om det var öppet och lägga den där. 1587 01:12:57,320 --> 01:12:59,780 Så hittar vi nästa tillgängliga öppen plats och lägga den där. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Fler frågor? 1590 01:13:03,890 --> 01:13:05,370 Ja, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> Publik: Som en uppföljning till denna, vad menar du med nästa plats? 1592 01:13:07,490 --> 01:13:10,250 I hashtabell eller i en länkad lista. 1593 01:13:10,250 --> 01:13:12,100 >> JASON Hirschhorn: För linjär programmering, inga länkade listor. 1594 01:13:12,100 --> 01:13:13,400 Nästa punkt på hash-tabell. 1595 01:13:13,400 --> 01:13:13,820 >> PUBLIK: OK. 1596 01:13:13,820 --> 01:13:17,570 Så hashtabellen skulle vara initialiseras till storleken - 1597 01:13:17,570 --> 01:13:19,560 liksom antalet strängar att du sätter in? 1598 01:13:19,560 --> 01:13:22,170 >> JASON Hirschhorn: Du skulle vill att det ska bli riktigt stort. 1599 01:13:22,170 --> 01:13:23,910 Ja. 1600 01:13:23,910 --> 01:13:27,900 Här är en bild av vad vi bara drog på tavlan. 1601 01:13:27,900 --> 01:13:29,470 Återigen har vi en kollision här. 1602 01:13:29,470 --> 01:13:30,710 vid 152. 1603 01:13:30,710 --> 01:13:33,570 Och du kommer att se att vi skapade en länkad lista på det. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Igen, hashtabell separat kedja tillvägagångssätt är inte den du 1606 01:13:41,850 --> 01:13:45,590 måste ta för problem inställd sex men är en som många 1607 01:13:45,590 --> 01:13:47,100 eleverna tenderar att ta. 1608 01:13:47,100 --> 01:13:51,140 Så på Alltså, låt oss prata en kort stund innan vi beger oss ut om problemet sex, 1609 01:13:51,140 --> 01:13:52,160 och sedan ska jag dela en berättelse med dig. 1610 01:13:52,160 --> 01:13:55,120 Vi har tre minuter. 1611 01:13:55,120 --> 01:13:55,750 >> Problem set sex. 1612 01:13:55,750 --> 01:13:57,790 Du har fyra funktioner - 1613 01:13:57,790 --> 01:14:02,430 last, kontrollera, storlek, och lasta. 1614 01:14:02,430 --> 01:14:03,380 Load - 1615 01:14:03,380 --> 01:14:07,120 Tja, vi har pågått över lasten just nu. 1616 01:14:07,120 --> 01:14:09,330 Vi drog belastning på tavlan. 1617 01:14:09,330 --> 01:14:13,230 Och vi ens börjat koda en hel del föra in i en länkad lista. 1618 01:14:13,230 --> 01:14:18,020 Så belastningen är inte mycket mer än vad vi just gjort. 1619 01:14:18,020 --> 01:14:21,070 >> Check är när du har något laddad. 1620 01:14:21,070 --> 01:14:22,580 Det är samma process som denna. 1621 01:14:22,580 --> 01:14:26,845 Samma två första delarna där du kastar något i hashfunktionen 1622 01:14:26,845 --> 01:14:29,190 och få sitt värde. 1623 01:14:29,190 --> 01:14:30,700 Men nu är vi inte sätter in det. 1624 01:14:30,700 --> 01:14:33,350 Nu är vi letar efter det. 1625 01:14:33,350 --> 01:14:37,130 Jag har prov kod skriven för att hitta något i en länkad lista. 1626 01:14:37,130 --> 01:14:38,250 Jag uppmuntrar dig att träna det. 1627 01:14:38,250 --> 01:14:43,000 Men intuitivt att hitta något är ganska lik att sätta in något. 1628 01:14:43,000 --> 01:14:46,540 I själva verket drog vi en bild av att finna något i en länkad lista, flytta 1629 01:14:46,540 --> 01:14:48,910 igenom tills du kommit till slutet. 1630 01:14:48,910 --> 01:14:52,430 Och om du fick på slutet och kunde inte tycker att det är, då är det inte där. 1631 01:14:52,430 --> 01:14:55,400 Så det är kontroll, i huvudsak. 1632 01:14:55,400 --> 01:14:57,030 >> Nästa är storleken. 1633 01:14:57,030 --> 01:14:57,910 Låt oss hoppa över storlek. 1634 01:14:57,910 --> 01:15:00,040 Slutligen har du lasta. 1635 01:15:00,040 --> 01:15:02,890 Unload är något vi har inte dragit i styrelsen eller kodade ännu. 1636 01:15:02,890 --> 01:15:05,990 Men jag uppmuntrar dig att försöka koda det i vårt urval länkad lista exempel. 1637 01:15:05,990 --> 01:15:11,440 Men lasta intuitivt liknar gratis - 1638 01:15:11,440 --> 01:15:14,010 eller jag menar liknar kolla. 1639 01:15:14,010 --> 01:15:17,350 Med undantag för nu varje gång du ska igenom, du är inte bara kontrollera att 1640 01:15:17,350 --> 01:15:19,090 se om du har ditt värde där. 1641 01:15:19,090 --> 01:15:22,490 Men du tar den noden och befria det, i grunden. 1642 01:15:22,490 --> 01:15:23,610 Det är vad lasta ber dig att göra. 1643 01:15:23,610 --> 01:15:24,670 Gratis allt du har malloced. 1644 01:15:24,670 --> 01:15:27,480 Så du går igenom hela listan igen, gå igenom hela hash 1645 01:15:27,480 --> 01:15:27,760 bord igen. 1646 01:15:27,760 --> 01:15:29,240 Den här gången inte kolla för att se vad som finns där. 1647 01:15:29,240 --> 01:15:31,080 Bara frigöra vad som finns där. 1648 01:15:31,080 --> 01:15:33,260 >> Och slutligen storlek. 1649 01:15:33,260 --> 01:15:34,350 Storlek bör genomföras. 1650 01:15:34,350 --> 01:15:35,590 Om du inte genomför storlek - 1651 01:15:35,590 --> 01:15:36,250 Jag ska säga det så här. 1652 01:15:36,250 --> 01:15:39,740 Om du inte genomför storleken på exakt en rad kod, inklusive 1653 01:15:39,740 --> 01:15:43,760 tillbaka uttalandet, är du gör storlek felaktigt. 1654 01:15:43,760 --> 01:15:47,170 Så se till storlek, för full design poäng, du gör det på exakt en 1655 01:15:47,170 --> 01:15:49,970 kodrad, inklusive retur uttalande. 1656 01:15:49,970 --> 01:15:52,450 >> Och inte packa upp ännu, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Eager beaver. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 Jag ville säga tack killar för kommande avsnitt. 1660 01:16:01,300 --> 01:16:02,550 Ha en lyckliga Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Det här är min dräkt. 1663 01:16:05,960 --> 01:16:08,850 Jag kommer att ha på sig detta på torsdag Om jag ser dig på kontorstid. 1664 01:16:08,850 --> 01:16:14,640 Och om du är nyfiken på lite mer bakgrund som till denna dräkt, känner 1665 01:16:14,640 --> 01:16:19,135 fri att kolla in 2011 avsnitt för en berättelse om varför jag är 1666 01:16:19,135 --> 01:16:20,900 bär pumpa kostym. 1667 01:16:20,900 --> 01:16:23,680 Och det är en sorglig historia. 1668 01:16:23,680 --> 01:16:27,050 Så se till att du har vissa vävnader i närheten. 1669 01:16:27,050 --> 01:16:28,680 Men på det, om du har någon frågor som jag ska hålla mig runt 1670 01:16:28,680 --> 01:16:29,960 utanför efter avsnitt. 1671 01:16:29,960 --> 01:16:31,510 Lycka till på problem set sex. 1672 01:16:31,510 --> 01:16:33,540 Och som alltid, om du har någon frågor, låt mig veta. 1673 01:16:33,540 --> 01:16:35,584