1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON HIRSCHHORN: Welkom iedereen aan de afdeling Seven. 3 00:00:12,680 --> 00:00:15,040 We zijn in week zeven van de cursus. 4 00:00:15,040 --> 00:00:18,440 En dat aanstaande donderdag is Halloween dus ik ben 5 00:00:18,440 --> 00:00:21,420 verkleed als een pompoen. 6 00:00:21,420 --> 00:00:23,460 Ik kon niet bukken en op mijn schoenen, dus dat is waarom ik ben 7 00:00:23,460 --> 00:00:25,660 alleen het dragen van sokken. 8 00:00:25,660 --> 00:00:29,220 Ik ben ook niet dragen van iets onder dit, dus ik kan niet het opstijgen als het 9 00:00:29,220 --> 00:00:29,950 afleidend aan u. 10 00:00:29,950 --> 00:00:31,860 Ik verontschuldig me bij voorbaat voor. 11 00:00:31,860 --> 00:00:33,170 U hoeft niet voor te stellen wat er gaande is. 12 00:00:33,170 --> 00:00:34,240 Ik draag boxers. 13 00:00:34,240 --> 00:00:36,170 Dus het is allemaal goed. 14 00:00:36,170 --> 00:00:41,120 >> Ik heb een langer verhaal over waarom ik gekleed als een pompoen, maar ik ga 15 00:00:41,120 --> 00:00:45,110 bewaren voor later in deze paragraaf want ik wil aan de slag. 16 00:00:45,110 --> 00:00:47,720 We hebben een heleboel spannende dingen te gaan over deze week. 17 00:00:47,720 --> 00:00:51,810 De meesten van hen hebben rechtstreeks betrekking op dit probleem set week, spelfouten. 18 00:00:51,810 --> 00:00:54,680 We gaan gaan over verbonden lijsten en hash tabellen 19 00:00:54,680 --> 00:00:57,160 Voor het volledige overzicht. 20 00:00:57,160 --> 00:01:02,490 Ik heb deze lijst elke week, een lijst van middelen voor u om u te helpen met 21 00:01:02,490 --> 00:01:04,120 het materiaal op deze cursus. 22 00:01:04,120 --> 00:01:07,600 Als bij een verlies of als op zoek naar een aantal meer informatie, kijk op een van 23 00:01:07,600 --> 00:01:09,930 deze middelen. 24 00:01:09,930 --> 00:01:14,530 >> Nogmaals, pset6 is spelfouten, PSET van deze week. 25 00:01:14,530 --> 00:01:17,690 En het stimuleert je ook, en ik u aanmoedigen, om een ​​aantal andere gebruiken 26 00:01:17,690 --> 00:01:20,320 middelen die specifiek voor deze PSET. 27 00:01:20,320 --> 00:01:23,390 Met name de drie heb ik up op het scherm weergegeven - 28 00:01:23,390 --> 00:01:27,160 gdb, die we bekend met zijn geweest en gebruikt voor een tijdje nu, is 29 00:01:27,160 --> 00:01:29,270 gaat zeer nuttige week. 30 00:01:29,270 --> 00:01:30,190 Dus heb ik dat hier. 31 00:01:30,190 --> 00:01:32,910 Maar als je werkt met C, je moet altijd gebruiken gdb aan 32 00:01:32,910 --> 00:01:34,430 debuggen uw programma's. 33 00:01:34,430 --> 00:01:36,660 Deze week ook Valgrind. 34 00:01:36,660 --> 00:01:38,535 Weet iemand wat valgrind doet? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> Publiek: Er wordt gecontroleerd of memory leaks? 37 00:01:43,890 --> 00:01:45,950 >> JASON HIRSCHHORN: Valgrind controles voor memory leaks. 38 00:01:45,950 --> 00:01:49,970 Dus als je malloc iets in uw programma, bent u vragen om het geheugen. 39 00:01:49,970 --> 00:01:52,920 Aan het einde van je programma, je hebt te schrijven gratis op alles wat je hebt 40 00:01:52,920 --> 00:01:54,800 malloced om het geheugen terug te geven. 41 00:01:54,800 --> 00:01:58,420 Als je niet schrijven gratis aan het eind en uw programma komt tot een conclusie, 42 00:01:58,420 --> 00:02:00,000 alles automatisch worden bevrijd. 43 00:02:00,000 --> 00:02:02,340 En voor kleine programma's, het is niet zo'n groot probleem. 44 00:02:02,340 --> 00:02:05,250 Maar als je het schrijven van een langer lopende programma dat niet stoppen, 45 00:02:05,250 --> 00:02:09,180 se, in een paar minuten of een paar seconden, dan is het geheugen lekt 46 00:02:09,180 --> 00:02:10,710 kan een enorme deal geworden. 47 00:02:10,710 --> 00:02:14,940 >> Dus voor pset6, de verwachting is dat je zult nul geheugenlekken hebben met 48 00:02:14,940 --> 00:02:15,910 uw programma. 49 00:02:15,910 --> 00:02:18,690 Om te controleren of het geheugen lekken, lopen valgrind en het zal u geven een aantal leuke 50 00:02:18,690 --> 00:02:21,190 uitgang te laten weten of of niet alles was gratis. 51 00:02:21,190 --> 00:02:23,940 We zullen later oefenen met het vandaag, hopelijk. 52 00:02:23,940 --> 00:02:25,790 >> Ten slotte is de diff commando. 53 00:02:25,790 --> 00:02:28,900 Je iets wat lijkt op het gebruikt in pset5 met de peek tool. 54 00:02:28,900 --> 00:02:30,780 Mag je naar binnen te kijken. 55 00:02:30,780 --> 00:02:33,400 Je gebruikt ook diff ook, per het probleem te stellen spec. 56 00:02:33,400 --> 00:02:35,950 Maar je mag vergelijken van twee bestanden. 57 00:02:35,950 --> 00:02:39,180 Je kon de bitmap-bestand en vergelijk info headers van een staf-oplossing en 58 00:02:39,180 --> 00:02:42,200 uw oplossing in pset5 als je ervoor kiest om het te gebruiken. 59 00:02:42,200 --> 00:02:44,030 Diff zal u toelaten om dat te doen, ook. 60 00:02:44,030 --> 00:02:48,620 Je kunt het vergelijken het juiste antwoord voor probleem van deze week in te stellen om uw antwoord 61 00:02:48,620 --> 00:02:52,210 en zien of het lijnen of zie waar de fouten. 62 00:02:52,210 --> 00:02:55,870 >> Dus dat zijn drie goede tools die u moet gebruiken voor deze week, en 63 00:02:55,870 --> 00:02:58,130 zeker check je programma met deze drie instrumenten 64 00:02:58,130 --> 00:03:00,520 voordat u het in 65 00:03:00,520 --> 00:03:04,650 Nogmaals, als ik elke week heb genoemd, Als u feedback heeft voor mij - zowel 66 00:03:04,650 --> 00:03:06,470 positieve en constructieve - 67 00:03:06,470 --> 00:03:09,930 voel je vrij om naar de website onderaan deze dia 68 00:03:09,930 --> 00:03:11,270 en voer het daar. 69 00:03:11,270 --> 00:03:13,440 Ik elke waardeer en alle feedback. 70 00:03:13,440 --> 00:03:17,360 En als je me specifieke dingen die Ik kan doen om te verbeteren of dat ik ben 71 00:03:17,360 --> 00:03:21,350 goed te doen dat je zou willen dat ik blijven, neem ik dat ter harte en 72 00:03:21,350 --> 00:03:24,040 echt hun best om te luisteren aan uw feedback. 73 00:03:24,040 --> 00:03:27,720 Ik kan niet beloven dat ik ga doen alles, hoewel, als het dragen van een 74 00:03:27,720 --> 00:03:30,700 pompoen kostuum elke week. 75 00:03:30,700 --> 00:03:34,020 >> Dus gaan we het grootste deel van de te besteden sectie, zoals ik al zei, het over 76 00:03:34,020 --> 00:03:37,240 gelinkte lijsten en hash tabellen, die zal direct van toepassing op de te 77 00:03:37,240 --> 00:03:38,780 probleem stelt u deze week. 78 00:03:38,780 --> 00:03:42,580 Gelinkte lijsten we over relatief gaan snel omdat we een eerlijke beetje hebt besteed 79 00:03:42,580 --> 00:03:44,930 van tijd gaan over het in sectie. 80 00:03:44,930 --> 00:03:48,680 En dus gaan we rechtstreeks naar het krijgen coderen problemen voor gelinkte lijsten. 81 00:03:48,680 --> 00:03:52,740 En dan aan het eind zullen we praten over hash tabellen en hoe ze van toepassing op deze 82 00:03:52,740 --> 00:03:55,280 probleem week in te stellen. 83 00:03:55,280 --> 00:03:57,560 >> Je hebt deze code eerder gezien. 84 00:03:57,560 --> 00:04:02,730 Dit is een structuur, en definieert iets nieuws wordt een knooppunt genoemd. 85 00:04:02,730 --> 00:04:10,660 En in een knooppunt is een integer hier en daar is een pointer naar 86 00:04:10,660 --> 00:04:11,830 ander knooppunt. 87 00:04:11,830 --> 00:04:12,790 We hebben dit eerder gezien. 88 00:04:12,790 --> 00:04:14,830 Dit komt al voor een paar weken nu. 89 00:04:14,830 --> 00:04:18,680 Het combineert pointers, die we geweest zijn werken met, en structs, waardoor 90 00:04:18,680 --> 00:04:22,079 wij twee combineren dingen in een datatype. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Er is veel gaande op het scherm. 93 00:04:26,490 --> 00:04:30,220 Maar al het moet relatief zijn vertrouwd zijn met je. 94 00:04:30,220 --> 00:04:33,810 Op de eerste regel, we verklaren een nieuw knooppunt. 95 00:04:33,810 --> 00:04:41,650 En dan binnen dat nieuwe knooppunt, ik het gehele getal in dat knooppunt een. 96 00:04:41,650 --> 00:04:44,950 We zien op de volgende regel ik een doe printf commando, maar ik heb grijs 97 00:04:44,950 --> 00:04:48,080 de printf commando omdat het echt belangrijk deel is deze lijn hier - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Wat betekent de stip betekenen? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> PUBLIEK: Ga naar het knooppunt en beoordelen van de n-waarde voor. 102 00:04:57,240 --> 00:04:58,370 >> JASON HIRSCHHORN: Dat is precies goed. 103 00:04:58,370 --> 00:05:03,300 Dot betekent toegang tot de n deel deze nieuwe knooppunt. 104 00:05:03,300 --> 00:05:05,690 Deze volgende regel doet wat? 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 >> Publiek: Het creëert een ander knooppunt die naar het nieuwe knooppunt. 108 00:05:21,910 --> 00:05:24,870 >> JASON HIRSCHHORN: het doet dus niet maak een nieuw knooppunt. 109 00:05:24,870 --> 00:05:26,120 Het creëert een wat? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> PUBLIEK: Een pointer. 112 00:05:29,300 --> 00:05:33,460 >> JASON HIRSCHHORN: Een pointer naar een knooppunt, zoals aangegeven door dit knooppunt * hier. 113 00:05:33,460 --> 00:05:34,800 Dus creëert een pointer naar een knooppunt. 114 00:05:34,800 --> 00:05:37,490 En welke node wordt deze naar tot, Michael? 115 00:05:37,490 --> 00:05:38,440 >> PUBLIEK: Nieuw knooppunt? 116 00:05:38,440 --> 00:05:39,240 >> JASON HIRSCHHORN: Nieuw knooppunt. 117 00:05:39,240 --> 00:05:43,020 En het wijst er omdat we hebben gegeven het adres van de nieuwe node. 118 00:05:43,020 --> 00:05:45,820 En nu in deze lijn zien we twee verschillende manieren 119 00:05:45,820 --> 00:05:46,910 uiting van hetzelfde. 120 00:05:46,910 --> 00:05:49,650 En ik wilde erop wijzen hoe deze twee dingen zijn hetzelfde. 121 00:05:49,650 --> 00:05:54,740 In de eerste regel, dereferentie we de aanwijzer. 122 00:05:54,740 --> 00:05:55,830 Dus gaan we naar het knooppunt. 123 00:05:55,830 --> 00:05:56,830 Dat is wat deze ster betekent. 124 00:05:56,830 --> 00:05:57,930 We hebben gezien dat voordat met pointers. 125 00:05:57,930 --> 00:05:59,280 Ga naar dat knooppunt. 126 00:05:59,280 --> 00:06:00,370 Dat is tussen haakjes. 127 00:06:00,370 --> 00:06:04,610 En dan toegang via de puntoperator de n element van dat knooppunt. 128 00:06:04,610 --> 00:06:08,430 >> Dus dat is het nemen van de syntaxis we hier en nu zag 129 00:06:08,430 --> 00:06:09,670 internetten met een pointer. 130 00:06:09,670 --> 00:06:13,730 Natuurlijk, het wordt een beetje druk als je bent het schrijven van die haakjes - 131 00:06:13,730 --> 00:06:14,940 die ster en dat stip. 132 00:06:14,940 --> 00:06:16,220 Het wordt een beetje druk. 133 00:06:16,220 --> 00:06:18,500 Zodat we een aantal syntactische suiker. 134 00:06:18,500 --> 00:06:19,920 En deze lijn hier - 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 Dat doet precies hetzelfde. 138 00:06:28,000 --> 00:06:30,840 Dus die twee regels code zijn gelijkwaardig en zal doen 139 00:06:30,840 --> 00:06:31,650 precies hetzelfde. 140 00:06:31,650 --> 00:06:34,210 >> Maar ik wilde wijzen die vóór we verder gaan, zodat je begrijpt 141 00:06:34,210 --> 00:06:39,000 die echt dit ding hier is alleen syntactische suiker voor dereferentie 142 00:06:39,000 --> 00:06:44,200 de aanwijzer en vervolgens naar n de deel van die structuur. 143 00:06:44,200 --> 00:06:45,525 Heeft u vragen over deze dia? 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 >> Dus we gaan om te gaan door een paar van de activiteiten die u kunt doen 147 00:06:58,510 --> 00:06:59,730 gelinkte lijsten. 148 00:06:59,730 --> 00:07:05,770 Een gelinkte lijst, rappel, is een serie van knooppunten die naar elkaar. 149 00:07:05,770 --> 00:07:12,470 En we beginnen meestal met een wijzer genoemd hoofd algemeen die verwijst naar 150 00:07:12,470 --> 00:07:14,040 het eerste wat in de lijst. 151 00:07:14,040 --> 00:07:18,900 Dus op de eerste lijn hier, we eerst onze oorspronkelijke L. 152 00:07:18,900 --> 00:07:21,370 Zodat wat je maar kunt bedenken - dit tekst hier je kunt bedenken als 153 00:07:21,370 --> 00:07:23,560 alleen de pointer die we hebben opgeslagen ergens dat punten 154 00:07:23,560 --> 00:07:24,670 het eerste element. 155 00:07:24,670 --> 00:07:27,500 En in deze gelinkte lijst hebben we vier knooppunten. 156 00:07:27,500 --> 00:07:29,530 Elk knooppunt is een grote doos. 157 00:07:29,530 --> 00:07:33,430 De grotere doos in de grote box is het gehele deel. 158 00:07:33,430 --> 00:07:37,400 En dan hebben we een pointer deel. 159 00:07:37,400 --> 00:07:39,630 >> Deze dozen zijn niet op schaal want hoe groot is 160 00:07:39,630 --> 00:07:42,320 een geheel getal bytes? 161 00:07:42,320 --> 00:07:43,290 Hoe nu groot? 162 00:07:43,290 --> 00:07:43,710 Four. 163 00:07:43,710 --> 00:07:45,470 En hoe groot is een pointer? 164 00:07:45,470 --> 00:07:45,940 Four. 165 00:07:45,940 --> 00:07:48,180 Dus echt, als we trekken Deze beide vakken schaal 166 00:07:48,180 --> 00:07:49,690 zou dezelfde grootte. 167 00:07:49,690 --> 00:07:52,870 In dit geval willen we voegen iets in de gelinkte lijst. 168 00:07:52,870 --> 00:07:57,190 Zo kunt u hier beneden zien we het invoegen vijf We doorkruisen via de 169 00:07:57,190 --> 00:08:01,310 gelinkte lijst, vinden waar vijf gaat, en steek deze vervolgens. 170 00:08:01,310 --> 00:08:03,560 >> Laten we breken die naar beneden en gaan een beetje langzamer. 171 00:08:03,560 --> 00:08:05,510 Ik ga om te wijzen op het bord. 172 00:08:05,510 --> 00:08:09,930 Dus hebben we onze knooppunt vijf die we hebben gemaakt in mallocs. 173 00:08:09,930 --> 00:08:11,190 Waarom is iedereen lachen? 174 00:08:11,190 --> 00:08:12,130 Grapje. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Dus we hebben malloced vijf. 177 00:08:14,820 --> 00:08:16,310 We hebben dit knooppunt gemaakt ergens anders. 178 00:08:16,310 --> 00:08:17,740 We hebben het klaar om te gaan. 179 00:08:17,740 --> 00:08:20,130 We beginnen bij de voorzijde van onze lijst met twee. 180 00:08:20,130 --> 00:08:22,380 En we willen invoegen in een gesorteerde manier. 181 00:08:22,380 --> 00:08:27,550 >> Dus als we zien twee en we willen zetten in vijf, wat doen we als we zien doen 182 00:08:27,550 --> 00:08:28,800 iets minder dan wij? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 Wat? 185 00:08:33,520 --> 00:08:36,750 We willen invoegen vijf in deze gelinkte lijst, waardoor het opgelost. 186 00:08:36,750 --> 00:08:37,520 We zien nummer twee. 187 00:08:37,520 --> 00:08:38,769 Dus wat doen we? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> PUBLIEK: Bel de wijzer naar het volgende knooppunt. 190 00:08:40,679 --> 00:08:42,530 >> JASON HIRSCHHORN: En waarom doen gaan we naar de volgende? 191 00:08:42,530 --> 00:08:45,970 >> Publiek: Omdat het de volgende knooppunt in de lijst. 192 00:08:45,970 --> 00:08:48,310 En we weten alleen dat een andere locatie. 193 00:08:48,310 --> 00:08:50,410 >> JASON HIRSCHHORN: En vijf is groter dan twee, in het bijzonder. 194 00:08:50,410 --> 00:08:51,600 Omdat we willen het gesorteerde houden. 195 00:08:51,600 --> 00:08:52,730 Dus vijf groter is dan twee. 196 00:08:52,730 --> 00:08:54,460 Dus gaan we over naar de volgende. 197 00:08:54,460 --> 00:08:55,240 En nu komen we bij vier. 198 00:08:55,240 --> 00:08:56,490 En wat gebeurt er als we vier bereiken? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Vijf is groter dan vier. 201 00:09:00,310 --> 00:09:01,460 Dus houden we gaan. 202 00:09:01,460 --> 00:09:03,110 En nu zijn we om zes uur. 203 00:09:03,110 --> 00:09:04,360 En wat zien we om zes uur? 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 >> PUBLIEK: Zes is groter dan vijf. 207 00:09:10,544 --> 00:09:11,480 >> JASON HIRSCHHORN: Six is groter dan vijf. 208 00:09:11,480 --> 00:09:13,660 Dus dat is waar we willen in te voegen vijf. 209 00:09:13,660 --> 00:09:17,320 Houd er echter rekening mee dat als we slechts een wijzer hier - 210 00:09:17,320 --> 00:09:19,840 dit is onze extra pointer dat is doorkruist door de lijst. 211 00:09:19,840 --> 00:09:21,860 En we wijzen op zes. 212 00:09:21,860 --> 00:09:25,010 We hebben verloren spoor van wat komt voor zes. 213 00:09:25,010 --> 00:09:29,130 Dus als we iets willen in voegen deze lijst houden van het te regelen, we 214 00:09:29,130 --> 00:09:31,630 waarschijnlijk hoeveel pointers? 215 00:09:31,630 --> 00:09:32,280 >> PUBLIEK: Twee. 216 00:09:32,280 --> 00:09:32,920 >> JASON Hirschorn: Two. 217 00:09:32,920 --> 00:09:35,720 Een te houden van de huidige te houden een en een bij te houden 218 00:09:35,720 --> 00:09:37,050 de vorige. 219 00:09:37,050 --> 00:09:38,450 Dit is slechts een enkelvoudig gelinkte lijst. 220 00:09:38,450 --> 00:09:39,670 Het gaat slechts een richting. 221 00:09:39,670 --> 00:09:43,220 Als we een dubbel gelinkte lijst, waar alles wees naar het ding 222 00:09:43,220 --> 00:09:46,240 na het en het ding voor, dan zouden we niet nodig om dat te doen. 223 00:09:46,240 --> 00:09:49,350 Maar in dit geval willen we niet verliezen bij wat voor ons kwamen in geval 224 00:09:49,350 --> 00:09:53,350 we moeten vijf ergens invoegen in het midden. 225 00:09:53,350 --> 00:09:55,610 Zeggen dat we het plaatsen van negen. 226 00:09:55,610 --> 00:09:57,260 Wat zou er gebeuren als we tot acht? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> PUBLIEK: Je zou krijgen dat nulpunt. 229 00:10:04,880 --> 00:10:07,820 In plaats van nulpunt zou je om een ​​element toe te voegen en dan hebben 230 00:10:07,820 --> 00:10:09,216 het wijzen op negen. 231 00:10:09,216 --> 00:10:09,700 >> JASON Hirschorn: Precies. 232 00:10:09,700 --> 00:10:10,600 Dus krijgen we acht. 233 00:10:10,600 --> 00:10:13,140 We bereiken het einde van de lijst omdat dit wijst op null. 234 00:10:13,140 --> 00:10:16,330 En nu, in plaats van het hebben van het wijzen op null we hebben het naar onze nieuwe knooppunt. 235 00:10:16,330 --> 00:10:19,870 En we stellen de aanwijzer in onze nieuwe knooppunt op null. 236 00:10:19,870 --> 00:10:21,445 Heeft iemand enig vragen over het invoegen? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Wat als ik niet schelen het bijhouden van de lijst gesorteerd? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> PUBLIEK: Plak het op de het begin of het einde. 241 00:10:34,350 --> 00:10:35,510 >> JASON Hirschorn: Stick it in het begin of het einde. 242 00:10:35,510 --> 00:10:37,276 Welke moeten we doen? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Waarom het einde? 245 00:10:41,020 --> 00:10:43,250 >> PUBLIEK: Omdat het begin is al ingevuld. 246 00:10:43,250 --> 00:10:43,575 >> JASON Hirschorn: OK. 247 00:10:43,575 --> 00:10:44,360 Het begin is al ingevuld. 248 00:10:44,360 --> 00:10:46,090 Wie wil om te betogen tegen Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> PUBLIEK: Nou wil je waarschijnlijk plak het in het begin, omdat 251 00:10:48,910 --> 00:10:50,140 anders als je het op het einde je zou moeten 252 00:10:50,140 --> 00:10:51,835 doorkruisen de hele lijst. 253 00:10:51,835 --> 00:10:52,990 >> JASON Hirschorn: Precies. 254 00:10:52,990 --> 00:10:57,970 Dus als we denken over runtime, de looptijd van inbrengen eind 255 00:10:57,970 --> 00:11:00,110 n zou zijn, de grootte van deze. 256 00:11:00,110 --> 00:11:03,080 Wat is het grote O runtime van het plaatsen van begin? 257 00:11:03,080 --> 00:11:04,170 Constante tijd. 258 00:11:04,170 --> 00:11:07,075 Dus als je niet de zorg over het houden van iets gesorteerd, veel beter om gewoon 259 00:11:07,075 --> 00:11:08,420 Steek aan het begin van deze lijst. 260 00:11:08,420 --> 00:11:10,320 En dat kan worden gedaan in constante tijd. 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 Volgende handeling is te vinden, die andere - we hebben dit geformuleerd als zoekopdracht. 264 00:11:18,870 --> 00:11:22,470 Maar we gaan kijken door de gekoppelde lijst voor een object. 265 00:11:22,470 --> 00:11:26,000 Jullie zijn code gezien voor zoeken voordat in collegezaal. 266 00:11:26,000 --> 00:11:29,490 Maar we soort net deed het met invoegen, althans invoegen 267 00:11:29,490 --> 00:11:30,580 iets gesorteerd. 268 00:11:30,580 --> 00:11:36,350 Je kijkt door, gaan knoop door knoop, totdat u het nummer dat u vindt 269 00:11:36,350 --> 00:11:37,780 zoekt. 270 00:11:37,780 --> 00:11:39,670 Wat gebeurt er als je te bereiken het einde van de lijst? 271 00:11:39,670 --> 00:11:43,020 Zeggen dat ik ben op zoek naar negen en ik bereiken het einde van de lijst. 272 00:11:43,020 --> 00:11:44,270 Wat doen wij? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> PUBLIEK: return false? 275 00:11:48,110 --> 00:11:48,690 >> JASON Hirschorn: return false. 276 00:11:48,690 --> 00:11:49,960 We vonden het niet. 277 00:11:49,960 --> 00:11:52,010 Als je het einde van de lijst te bereiken en je hebt het nummer je niet vinden 278 00:11:52,010 --> 00:11:54,170 op zoek naar, het is niet daar. 279 00:11:54,170 --> 00:11:55,420 Heeft u vragen over vinden? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 Als dit een gesorteerde lijst, wat zou anders onze zoeken? 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 >> Publiek: Het zou de eerste waarde te vinden dat is groter dan de 285 00:12:10,600 --> 00:12:12,390 u zoekt en dan terug vals. 286 00:12:12,390 --> 00:12:13,190 >> JASON Hirschorn: Precies. 287 00:12:13,190 --> 00:12:17,310 Dus als het een gesorteerde lijst, als we naar iets dat groter is dan 288 00:12:17,310 --> 00:12:20,180 we zoeken, hoeven we niet te steeds naar het einde van de lijst. 289 00:12:20,180 --> 00:12:24,060 We kunnen op dat punt return false omdat we niet van plan om het te vinden. 290 00:12:24,060 --> 00:12:27,340 De vraag is nu, we hebben gesproken over het houden van gelinkte lijsten gesorteerd, 291 00:12:27,340 --> 00:12:28,180 houden ze ongesorteerd. 292 00:12:28,180 --> 00:12:30,050 Dat gaat iets wat je wel waarschijnlijk zal moeten nadenken over 293 00:12:30,050 --> 00:12:34,240 bij het coderen probleem van de vijf als je kies een hash table met aparte 294 00:12:34,240 --> 00:12:36,360 chaining benadering, die we later wel over. 295 00:12:36,360 --> 00:12:41,400 >> Maar is het de moeite waard om de lijst te houden gesorteerd en vervolgens in staat zijn om misschien hebben 296 00:12:41,400 --> 00:12:42,310 sneller zoekopdrachten? 297 00:12:42,310 --> 00:12:47,220 Of is het beter om snel in te voegen iets in constante runtime maar dan 298 00:12:47,220 --> 00:12:48,430 hebben langere zoeken? 299 00:12:48,430 --> 00:12:52,250 Dat is een afweging daar dat je krijgen om te beslissen wat is meer geschikt 300 00:12:52,250 --> 00:12:53,590 voor uw specifieke probleem. 301 00:12:53,590 --> 00:12:56,680 En er is niet per se een helemaal gelijk antwoord. 302 00:12:56,680 --> 00:12:59,520 Maar het is zeker een beslissing die je krijgt maken en waarschijnlijk goed te verdedigen 303 00:12:59,520 --> 00:13:05,270 dat in, zeg, een opmerking of twee waarom je kiest een over de ander. 304 00:13:05,270 --> 00:13:06,490 >> Tenslotte verwijderen. 305 00:13:06,490 --> 00:13:08,100 We hebben gezien verwijderen. 306 00:13:08,100 --> 00:13:09,180 Het is vergelijkbaar met het zoeken. 307 00:13:09,180 --> 00:13:11,020 We kijken voor het element. 308 00:13:11,020 --> 00:13:12,390 Zeggen dat we proberen te verwijderen zes. 309 00:13:12,390 --> 00:13:14,450 Dus vinden we zes hier. 310 00:13:14,450 --> 00:13:18,860 Het ding dat we moeten zorgen dat we te maken doen, is dat wat wijst naar 311 00:13:18,860 --> 00:13:21,220 zes - zoals we zien in stap twee hier beneden - 312 00:13:21,220 --> 00:13:26,500 wat wijst naar zes behoeften skip zes nu en worden veranderd in 313 00:13:26,500 --> 00:13:28,160 wat zes wijst. 314 00:13:28,160 --> 00:13:31,410 We willen niet de rest van steeds verweesde onze lijst door te vergeten om dat te stellen 315 00:13:31,410 --> 00:13:32,960 vorige pointer. 316 00:13:32,960 --> 00:13:35,960 En dan soms, afhankelijk op het programma, zullen ze gewoon 317 00:13:35,960 --> 00:13:37,380 dit knooppunt geheel te verwijderen. 318 00:13:37,380 --> 00:13:40,135 Soms wil je terug de waarde die in dit knooppunt. 319 00:13:40,135 --> 00:13:42,490 Dus dat is hoe het verwijderen werkt. 320 00:13:42,490 --> 00:13:44,610 Heeft u vragen over verwijderen? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> PUBLIEK: Dus als u gaat verwijderen , zou je gewoon gratis te gebruiken, omdat 323 00:13:53,850 --> 00:13:55,655 vermoedelijk was het malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON Hirschorn: Als u wilt vrijmaken iets dat is precies goed en je 325 00:13:57,976 --> 00:13:58,540 malloced het. 326 00:13:58,540 --> 00:14:00,410 Zeggen dat we wilden deze waarde terug te keren. 327 00:14:00,410 --> 00:14:04,010 We zouden terugkeren zes en dan vrij dit knooppunt en oproep gratis op. 328 00:14:04,010 --> 00:14:06,180 Of we zouden waarschijnlijk gratis bellen eerste en dan terug zes. 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 Dus laten we verder gaan om te oefenen codering. 332 00:14:14,010 --> 00:14:16,090 We gaan drie functies coderen. 333 00:14:16,090 --> 00:14:18,260 De eerste heet insert_node. 334 00:14:18,260 --> 00:14:22,170 Dus je hebt code die ik je gemaild, en als je dit ziet later 335 00:14:22,170 --> 00:14:28,020 kunt u de code in linked.c de CS50 website. 336 00:14:28,020 --> 00:14:30,880 Maar in linked.c, is er een aantal skelet code die al 337 00:14:30,880 --> 00:14:32,280 geschreven voor jou. 338 00:14:32,280 --> 00:14:34,560 En dan is er nog een paar functies je nodig hebt om te schrijven. 339 00:14:34,560 --> 00:14:36,380 >> Eerst gaan we schrijven insert_node. 340 00:14:36,380 --> 00:14:39,800 En wat doet insert_node wil zeggen voegt een geheel getal. 341 00:14:39,800 --> 00:14:42,440 En je geeft de integer in een gelinkte lijst. 342 00:14:42,440 --> 00:14:45,470 En in het bijzonder, moet u aan de lijst gesorteerd houden 343 00:14:45,470 --> 00:14:47,650 van klein naar groot. 344 00:14:47,650 --> 00:14:51,360 Ook hoeft u niet wilt steek geen duplicaten. 345 00:14:51,360 --> 00:14:54,600 Tot slot, zoals je kunt zien insert_node retourneert een bool. 346 00:14:54,600 --> 00:14:57,140 Dus jij moet de gebruiker te laten weten of het inzetstuk is 347 00:14:57,140 --> 00:15:00,800 succesvol door terug te keren waar of onwaar. 348 00:15:00,800 --> 00:15:02,580 Na afloop van dit programma - 349 00:15:02,580 --> 00:15:05,750 en voor deze fase je niet nodig hebt te maken over alles vrijmaken. 350 00:15:05,750 --> 00:15:11,790 Dus alles wat je doet is het nemen van een geheel getal en deze in een lijst. 351 00:15:11,790 --> 00:15:13,890 >> Dat is wat ik vraag je nu moet doen. 352 00:15:13,890 --> 00:15:17,620 Nogmaals, in de linked.c, die u allemaal hebben, is het skelet code. 353 00:15:17,620 --> 00:15:20,980 En je moet zien naar de bodem het monster functie verklaring. 354 00:15:20,980 --> 00:15:27,390 Echter, voordat je in het coderen in C, ik je ten zeerste aanmoedigen om te gaan 355 00:15:27,390 --> 00:15:29,330 door de stappen die we geweest zijn oefenen elke week. 356 00:15:29,330 --> 00:15:31,100 We hebben al meegemaakt een foto van deze. 357 00:15:31,100 --> 00:15:33,380 Dus je moet enig begrip hebben van hoe dit werkt. 358 00:15:33,380 --> 00:15:36,590 Maar ik wil u aanmoedigen om te schrijven sommige pseudocode voor de duik inch 359 00:15:36,590 --> 00:15:38,640 En we gaan over pseudocode als groep. 360 00:15:38,640 --> 00:15:41,470 En dan als je eenmaal hebt geschreven uw pseudocode, en zodra we hebben geschreven onze 361 00:15:41,470 --> 00:15:45,850 pseudocode als een groep, kunt u gaan in het coderen in C. 362 00:15:45,850 --> 00:15:49,980 >> Als een heads-up, de insert_node functie is waarschijnlijk de lastigste van 363 00:15:49,980 --> 00:15:53,550 de drie we gaan schrijven omdat ik additionele eisen toegevoegd 364 00:15:53,550 --> 00:15:57,190 de programmering, in het bijzonder dat je bent niet van plan om in te voegen 365 00:15:57,190 --> 00:15:59,880 duplicaten en dat de lijst moet gesorteerde blijven. 366 00:15:59,880 --> 00:16:02,660 Dus dit is een niet-triviale programma die je nodig hebt om te coderen. 367 00:16:02,660 --> 00:16:06,470 En waarom ga je niet vijf naar zeven minuten alleen maar om te werken aan de 368 00:16:06,470 --> 00:16:07,640 pseudocode en de code. 369 00:16:07,640 --> 00:16:09,460 En dan gaan we beginnen gaan als een groep. 370 00:16:09,460 --> 00:16:11,680 Nogmaals, als je gewoon vragen hebt steek je hand en ik zal rond komen. 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 >> We hebben ook over het algemeen doen deze - 375 00:18:30,120 --> 00:18:32,070 of ik niet expliciet je zegt kan werken met mensen. 376 00:18:32,070 --> 00:18:36,500 Maar het is duidelijk, ik u sterk aan te moedigen, als u vragen hebt, om de vragen 377 00:18:36,500 --> 00:18:39,840 buurman naast je zit of zelfs werken met iemand 378 00:18:39,840 --> 00:18:40,510 anders als u wilt. 379 00:18:40,510 --> 00:18:42,600 Dit hoeft niet aan een individu zijn stille activiteit. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Laten we beginnen met het schrijven van een aantal pseudocode op het bord. 382 00:20:16,330 --> 00:20:19,395 Wie kan mij de eerste regel van geven pseudocode voor dit programma? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 Voor deze functie nogal - 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 >> PUBLIEK: Dus het eerste wat ik deed was maak een nieuwe verwijzing naar het knooppunt en ik 388 00:20:36,560 --> 00:20:41,320 geïnitialiseerd is die naar dezelfde ding die lijst wijst. 389 00:20:41,320 --> 00:20:41,550 >> JASON Hirschorn: OK. 390 00:20:41,550 --> 00:20:45,190 Dus je bent een nieuwe pointer aan de lijst, niet naar het knooppunt. 391 00:20:45,190 --> 00:20:45,420 >> PUBLIEK: Juist. 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 En wat willen we doen? 395 00:20:48,221 --> 00:20:49,163 Wat is er daarna? 396 00:20:49,163 --> 00:20:50,105 Hoe zit het met de knoop? 397 00:20:50,105 --> 00:20:51,050 We hebben geen knooppunt. 398 00:20:51,050 --> 00:20:52,300 We hebben slechts een waarde. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Willen we een knoop in te voegen, wat doen we eerst moeten doen voordat we kunnen zelfs 401 00:20:58,890 --> 00:20:59,980 denken over het plaatsen van het? 402 00:20:59,980 --> 00:21:00,820 >> PUBLIEK: Oh, sorry. 403 00:21:00,820 --> 00:21:02,160 we moeten ruimte malloc voor een knooppunt. 404 00:21:02,160 --> 00:21:02,455 >> JASON Hirschorn: Excellent. 405 00:21:02,455 --> 00:21:03,210 Laten we het doen - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Kan die hoge niet bereiken. 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 We gaan naar beneden te gaan, en vervolgens we gebruiken twee kolommen. 411 00:21:13,236 --> 00:21:13,732 Ik kan niet gaan, dat - 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 Maak een nieuw knooppunt. 415 00:21:25,130 --> 00:21:29,380 U kunt een andere wijzer maken naar de lijst of u kunt gewoon gebruik maken van de lijst als het bestaat. 416 00:21:29,380 --> 00:21:30,720 Je hoeft niet echt nodig om dat te doen. 417 00:21:30,720 --> 00:21:31,750 >> Zo creëren we een nieuw knooppunt. 418 00:21:31,750 --> 00:21:32,010 Geweldig. 419 00:21:32,010 --> 00:21:32,840 Dat is wat we eerst doen. 420 00:21:32,840 --> 00:21:34,870 Wat is het volgende? 421 00:21:34,870 --> 00:21:35,080 >> PUBLIEK: Wacht. 422 00:21:35,080 --> 00:21:38,330 Moeten we een nieuw knooppunt nu of moeten we wachten om ervoor te zorgen dat 423 00:21:38,330 --> 00:21:42,260 er is geen duplicaten van het knooppunt op de lijst voordat we creëren het? 424 00:21:42,260 --> 00:21:43,100 >> JASON Hirschorn: Goede vraag. 425 00:21:43,100 --> 00:21:47,770 Laten we stellen dat voor later, omdat de meerderheid van de tijd zullen we creëren 426 00:21:47,770 --> 00:21:48,220 een nieuw knooppunt. 427 00:21:48,220 --> 00:21:49,110 Dus we zullen hier te houden dat. 428 00:21:49,110 --> 00:21:51,006 Maar dat is een goede vraag. 429 00:21:51,006 --> 00:21:53,250 Als we creëren het en vinden we een duplicaat, wat moet 430 00:21:53,250 --> 00:21:54,490 we eerder terug doen? 431 00:21:54,490 --> 00:21:55,190 >> PUBLIEK: Bevrijd het. 432 00:21:55,190 --> 00:21:55,470 >> JASON Hirschorn: Yeah. 433 00:21:55,470 --> 00:21:56,500 Waarschijnlijk bevrijden. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Wat doen we nadat we maak een nieuw knooppunt? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> PUBLIEK: We zetten de nummer in de knoop? 438 00:22:04,780 --> 00:22:05,140 >> JASON Hirschorn: Precies. 439 00:22:05,140 --> 00:22:07,190 We zetten het nummer - we malloc ruimte. 440 00:22:07,190 --> 00:22:08,160 Ik ga laat dat allen als een regel. 441 00:22:08,160 --> 00:22:08,720 Maar je hebt gelijk. 442 00:22:08,720 --> 00:22:10,305 We malloc ruimte, en vervolgens we het aantal inch 443 00:22:10,305 --> 00:22:12,585 We kunnen zelfs stellen de aanwijzer deel ervan op null. 444 00:22:12,585 --> 00:22:13,720 Zo is het precies. 445 00:22:13,720 --> 00:22:17,400 En hoe zit het dan daarna? 446 00:22:17,400 --> 00:22:18,490 We trokken deze foto op het bord. 447 00:22:18,490 --> 00:22:21,190 Dus wat doen we? 448 00:22:21,190 --> 00:22:22,680 >> PUBLIEK: We gaan door de lijst. 449 00:22:22,680 --> 00:22:23,930 >> JASON Hirschorn: Ga door de lijst. 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 En wat doen we controleren op elk knooppunt. 453 00:22:34,280 --> 00:22:35,955 Kurt, wat doen we controleren gedurende elk knooppunt? 454 00:22:35,955 --> 00:22:41,640 >> PUBLIEK: Kijk of de n-waarde van dat knooppunt groter is dan de aangegeven waarde 455 00:22:41,640 --> 00:22:43,070 onze knooppunt. 456 00:22:43,070 --> 00:22:43,340 >> JASON Hirschorn: OK. 457 00:22:43,340 --> 00:22:44,280 Ik ga doen - 458 00:22:44,280 --> 00:22:45,855 ja, OK. 459 00:22:45,855 --> 00:22:48,160 Dus het is n - 460 00:22:48,160 --> 00:22:59,040 Ik ga zeggen als de waarde groter is dan dit knooppunt, wat doen we dan? 461 00:22:59,040 --> 00:23:07,290 >> PUBLIEK: Nou, dan voegen we het ding vlak voor dat. 462 00:23:07,290 --> 00:23:07,970 >> JASON Hirschorn: OK. 463 00:23:07,970 --> 00:23:09,410 Dus als het groter is dan deze, dan willen we voegen. 464 00:23:09,410 --> 00:23:14,010 Maar we willen het invoegen vlak voor omdat we ook zouden moeten 465 00:23:14,010 --> 00:23:16,070 bijhouden, dan, van wat vroeger was. 466 00:23:16,070 --> 00:23:22,690 Dus invoegen voor. 467 00:23:22,690 --> 00:23:25,120 Dus we waarschijnlijk iets gemist eerder. 468 00:23:25,120 --> 00:23:27,770 We moeten waarschijnlijk worden houden houden van wat er gaande is. 469 00:23:27,770 --> 00:23:28,460 Maar we zullen er terug te krijgen. 470 00:23:28,460 --> 00:23:30,160 Dus wat waarde lager is dan? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, wat doen we als waarde kleiner dan? 473 00:23:39,710 --> 00:23:43,000 >> PUBLIEK: Dan moet je gewoon blijven gaan tenzij het de laatste. 474 00:23:43,000 --> 00:23:43,550 >> JASON Hirschorn: Dat vind ik leuk. 475 00:23:43,550 --> 00:23:44,800 Dus ga naar het volgende knooppunt. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Tenzij het de laatste - 478 00:23:48,930 --> 00:23:51,100 we waarschijnlijk controleren op dat in de voorwaarden van een aandoening. 479 00:23:51,100 --> 00:23:54,870 Maar ja, volgende knoop. 480 00:23:54,870 --> 00:23:58,680 En dat wordt te laag, dus we zullen hier te verplaatsen. 481 00:23:58,680 --> 00:24:02,030 Maar als - 482 00:24:02,030 --> 00:24:03,280 kan iedereen dit zien? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Als we gelijk wat doen we? 485 00:24:11,610 --> 00:24:15,740 Als de waarde we proberen in te voegen is gelijk aan de waarde van dit knooppunt? 486 00:24:15,740 --> 00:24:16,320 Yeah? 487 00:24:16,320 --> 00:24:18,400 >> PUBLIEK: [onverstaanbaar]. 488 00:24:18,400 --> 00:24:18,850 >> JASON Hirschorn: Yeah. 489 00:24:18,850 --> 00:24:19,290 Gezien deze - 490 00:24:19,290 --> 00:24:20,090 Marcus heeft gelijk. 491 00:24:20,090 --> 00:24:21,330 We konden misschien hebben gedaan iets anders. 492 00:24:21,330 --> 00:24:25,360 Maar gezien het feit dat we het hebben gemaakt, hier we moeten bevrijden en dan terug. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Is dat beter? 495 00:24:30,080 --> 00:24:31,850 Hoe is dat? 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 en dan wat doen we terugkeren, [onverstaanbaar]? 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 Missen we iets? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 Waar gaan we bijhouden van de voorafgaande knoop? 504 00:24:59,650 --> 00:25:02,370 >> Publiek: Ik denk dat het zou gaan na een nieuwe node. 505 00:25:02,370 --> 00:25:02,600 >> JASON Hirschorn: OK. 506 00:25:02,600 --> 00:25:03,940 Dus aan het begin We zullen waarschijnlijk - 507 00:25:03,940 --> 00:25:07,175 ja, we kunnen een pointer te creëren om een ​​nieuwe knooppunt, als een vorig knooppunt pointer en 508 00:25:07,175 --> 00:25:09,600 een huidige knooppunt pointer. 509 00:25:09,600 --> 00:25:12,640 Dus laten we dat hier invoegen. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Maak huidige en vorige verwijzingen naar de knooppunten. 512 00:25:26,900 --> 00:25:28,955 Maar toen we die pointers aanpassen? 513 00:25:28,955 --> 00:25:30,205 Waar doen we dat in de code? 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 >> PUBLIEK: - voorwaarden waarde? 517 00:25:35,170 --> 00:25:36,420 >> JASON Hirschorn: Welke een in het bijzonder? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> Publiek: Ik ben gewoon in de war. 520 00:25:40,720 --> 00:25:44,200 Als de waarde groter is dan dit knooppunt, betekent dat dan niet dat je wilt gaan 521 00:25:44,200 --> 00:25:45,320 naar het volgende knooppunt? 522 00:25:45,320 --> 00:25:49,515 >> JASON HIRSCHHORN: Dus als onze waarde is groter dan de waarde van deze knoop. 523 00:25:49,515 --> 00:25:52,130 >> PUBLIEK: Ja, dan zou je willen ga verder naar beneden de lijn, toch? 524 00:25:52,130 --> 00:25:52,590 >> JASON HIRSCHHORN: Juist. 525 00:25:52,590 --> 00:25:53,840 Zodat we niet plaatsen het hier. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Als waarde dan dit knooppunt, dan gaan we naar de volgende knoop - of dan we 528 00:26:03,240 --> 00:26:03,835 invoegen voor. 529 00:26:03,835 --> 00:26:05,966 >> PUBLIEK: Wacht, wat is dit knooppunt en dat is de waarde? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON HIRSCHHORN: Goede vraag. 532 00:26:09,280 --> 00:26:13,260 Waarde per deze functie definitie is wat we krijgen. 533 00:26:13,260 --> 00:26:16,910 Dus waarde is het aantal ons gegeven. 534 00:26:16,910 --> 00:26:21,120 Als de waarde minder is dan de knooppunt, tijd om in te voegen moeten we. 535 00:26:21,120 --> 00:26:24,575 Als de waarde groter is dan dit knooppunt, gaan we naar het volgende knooppunt. 536 00:26:24,575 --> 00:26:26,790 En terug naar de oorspronkelijke vraag, hoewel, waar - 537 00:26:26,790 --> 00:26:29,060 >> PUBLIEK: Als de waarde groter is dan dit knooppunt. 538 00:26:29,060 --> 00:26:30,310 >> JASON HIRSCHHORN: En zo wat doen we hier doen? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Sweet. 541 00:26:38,160 --> 00:26:38,860 Dat is juist. 542 00:26:38,860 --> 00:26:41,370 Ik ben gewoon gaan schrijven Update pointers. 543 00:26:41,370 --> 00:26:44,010 Maar ja, met de huidige zou je het updaten om 544 00:26:44,010 --> 00:26:46,080 verwijzen naar de volgende. 545 00:26:46,080 --> 00:26:47,330 Alles wat we mist? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Dus ga ik dit typ coderen in gedit. 548 00:26:54,940 --> 00:26:58,375 En terwijl ik dit doen, kunt u een hebt paar minuten om te werken aan de codering 549 00:26:58,375 --> 00:28:19,240 dit in C. 550 00:28:19,240 --> 00:28:20,940 >> Dus ik heb de ingang van de pseudocode. 551 00:28:20,940 --> 00:28:22,940 Een korte opmerking voordat we beginnen. 552 00:28:22,940 --> 00:28:25,560 We kunnen niet in staat om volledig te afmaken in alle 553 00:28:25,560 --> 00:28:27,300 drie van deze functies. 554 00:28:27,300 --> 00:28:30,630 Er is juiste oplossing te dat ik zal een e-mail naar jullie 555 00:28:30,630 --> 00:28:33,730 na sectie, en het zal worden geplaatst op CS50.net. 556 00:28:33,730 --> 00:28:35,640 Dus ik hoef je niet aan te moedigen om gaan kijken naar de secties. 557 00:28:35,640 --> 00:28:40,550 Ik moedig u aan om deze te proberen op uw bezitten, en gebruik vervolgens de de praktijk 558 00:28:40,550 --> 00:28:41,760 problemen om je antwoorden te controleren. 559 00:28:41,760 --> 00:28:47,070 Deze zijn allemaal ontworpen om nauw betreffen en zich aan welke 560 00:28:47,070 --> 00:28:48,400 je hoeft te doen aan het probleem set. 561 00:28:48,400 --> 00:28:53,820 Dus ik hoef u aanraden om dit te oefenen op uw eigen en gebruik vervolgens de code te 562 00:28:53,820 --> 00:28:54,660 Controleer uw antwoorden. 563 00:28:54,660 --> 00:28:57,060 Omdat ik wil overgaan tot hash tabellen op een bepaald punt in de sectie. 564 00:28:57,060 --> 00:28:58,150 Dus we kunnen niet door dit alles. 565 00:28:58,150 --> 00:28:59,960 Maar we zullen zo veel we kunnen nu doen. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Laten we beginnen. 568 00:29:01,960 --> 00:29:04,770 Asam, hoe creëren we een nieuw knooppunt? 569 00:29:04,770 --> 00:29:06,810 >> PUBLIEK: U hoeft struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON HIRSCHHORN: Dus we hebben dat hier. 571 00:29:09,640 --> 00:29:10,040 Oh, sorry. 572 00:29:10,040 --> 00:29:13,530 U zei struct *. 573 00:29:13,530 --> 00:29:17,260 >> PUBLIEK: En dan [? soort?] knoop of c knooppunt. 574 00:29:17,260 --> 00:29:17,780 >> JASON HIRSCHHORN: OK. 575 00:29:17,780 --> 00:29:19,740 Ik ga noemen new_node zodat we kunnen blijven consistent. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> PUBLIEK: En u wilt dat instellen aan het hoofd, het eerste knooppunt. 578 00:29:33,180 --> 00:29:33,580 >> JASON HIRSCHHORN: OK. 579 00:29:33,580 --> 00:29:37,290 Dus nu deze wijst naar - dus dit heeft een nieuw knooppunt nog niet gemaakt. 580 00:29:37,290 --> 00:29:41,380 Dit is gewoon te wijzen op de eerste knooppunt in de lijst. 581 00:29:41,380 --> 00:29:42,630 Hoe maak ik een nieuw knooppunt? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Als ik de ruimte om een ​​nieuw knooppunt te maken. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 En hoe groot? 586 00:29:51,710 --> 00:30:00,390 >> Publiek: De grootte van de structuur. 587 00:30:00,390 --> 00:30:01,150 >> JASON HIRSCHHORN: De grootte van de structuur. 588 00:30:01,150 --> 00:30:02,400 En wat is de structuur genoemd? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> PUBLIEK: Node? 591 00:30:09,840 --> 00:30:11,640 >> JASON HIRSCHHORN: Node. 592 00:30:11,640 --> 00:30:17,640 Dus malloc (sizeof (node)); geeft ons de ruimte. 593 00:30:17,640 --> 00:30:19,740 En is deze lijn - 594 00:30:19,740 --> 00:30:21,740 een ding is onjuist op deze lijn. 595 00:30:21,740 --> 00:30:24,430 Is new_node een pointer naar een struct? 596 00:30:24,430 --> 00:30:25,650 Dat is een algemene naam. 597 00:30:25,650 --> 00:30:26,520 Wat is het - 598 00:30:26,520 --> 00:30:27,450 knooppunt, precies. 599 00:30:27,450 --> 00:30:29,340 Het is een knooppunt *. 600 00:30:29,340 --> 00:30:33,010 En wat doen we direct na we malloc iets, Asan? 601 00:30:33,010 --> 00:30:34,476 Wat is het eerste wat we doen? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Wat als het niet werkt? 604 00:30:40,320 --> 00:30:42,430 >> PUBLIEK: Oh, controleer dan of het wijst op het knooppunt? 605 00:30:42,430 --> 00:30:43,310 >> JASON HIRSCHHORN: Precies. 606 00:30:43,310 --> 00:30:46,750 Dus als je new_node gelijk gelijken null, wat doen we? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Dit geeft een bool, deze functie. 609 00:30:54,820 --> 00:30:57,760 Precies. 610 00:30:57,760 --> 00:30:58,450 Ziet er goed uit. 611 00:30:58,450 --> 00:30:59,680 Alles om er toe te voegen? 612 00:30:59,680 --> 00:31:00,670 We zullen dingen toe te voegen aan het eind. 613 00:31:00,670 --> 00:31:03,160 Maar dat tot nu toe ziet er goed uit. 614 00:31:03,160 --> 00:31:06,170 Maak huidige en vorige pointers. 615 00:31:06,170 --> 00:31:08,650 Michael, hoe doe ik dit? 616 00:31:08,650 --> 00:31:12,810 >> PUBLIEK: U zou hebben om een ​​knooppunt te doen *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Je zou men niet maken voor new_node maar voor de 619 00:31:25,502 --> 00:31:26,905 nodes we al hebben. 620 00:31:26,905 --> 00:31:27,230 >> JASON HIRSCHHORN: OK. 621 00:31:27,230 --> 00:31:29,255 Zodat we het huidige knooppunt bent. 622 00:31:29,255 --> 00:31:30,505 Ik zal die curr bellen. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Oke. 625 00:31:39,770 --> 00:31:41,620 We hebben besloten dat we willen houden twee omdat we moeten weten 626 00:31:41,620 --> 00:31:42,870 wat is voordat het. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Wat krijgen ze geïnitialiseerd? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> PUBLIEK: Hun waarde in onze lijst. 631 00:31:54,180 --> 00:31:58,090 >> JASON HIRSCHHORN: Dus wat is de eerste wat op onze lijst? 632 00:31:58,090 --> 00:32:04,050 Of hoe weten we waar de begin van onze lijst is? 633 00:32:04,050 --> 00:32:08,015 >> PUBLIEK: Is het niet voorbij in de functie? 634 00:32:08,015 --> 00:32:08,466 >> JASON HIRSCHHORN: Juist. 635 00:32:08,466 --> 00:32:09,716 Het werd doorgegeven in hier. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Dus als het doorgegeven aan de functie, de start van de lijst, wat moeten we 638 00:32:18,980 --> 00:32:21,270 ingesteld stroom gelijk aan? 639 00:32:21,270 --> 00:32:22,110 >> PUBLIEK: List. 640 00:32:22,110 --> 00:32:22,900 >> JASON HIRSCHHORN: List. 641 00:32:22,900 --> 00:32:24,090 Zo is het precies. 642 00:32:24,090 --> 00:32:26,290 Nu heeft het adres het begin van onze lijst. 643 00:32:26,290 --> 00:32:28,450 En hoe zit het met de vorige? 644 00:32:28,450 --> 00:32:31,920 >> PUBLIEK: Lijst min een? 645 00:32:31,920 --> 00:32:32,690 >> JASON HIRSCHHORN: Er is niets ervoor. 646 00:32:32,690 --> 00:32:34,580 Dus wat kunnen we doen om niets te betekenen? 647 00:32:34,580 --> 00:32:35,050 >> PUBLIEK: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON HIRSCHHORN: Yeah. 649 00:32:35,450 --> 00:32:37,950 Dat klinkt als een goed idee. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Dank u. 652 00:32:39,630 --> 00:32:42,850 Ga door de lijst. 653 00:32:42,850 --> 00:32:45,490 Constantijn, hoe lang gaan we om door de lijst? 654 00:32:45,490 --> 00:32:49,010 >> PUBLIEK: totdat we bij nul. 655 00:32:49,010 --> 00:32:49,390 >> JASON HIRSCHHORN: OK. 656 00:32:49,390 --> 00:32:50,430 Dus als, terwijl, voor loop. 657 00:32:50,430 --> 00:32:52,200 Wat doen wij? 658 00:32:52,200 --> 00:32:53,320 >> PUBLIEK: Misschien een lus? 659 00:32:53,320 --> 00:32:53,910 >> JASON HIRSCHHORN: Laten we doen een lus. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> Publiek: En wij zeggen - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 totdat de huidige wijzer is niet gelijk aan nul. 664 00:33:13,390 --> 00:33:19,160 >> JASON HIRSCHHORN: Dus als we weten dat de staat, hoe kunnen we schrijven een lus 665 00:33:19,160 --> 00:33:21,740 gebaseerd off die voorwaarde. 666 00:33:21,740 --> 00:33:24,380 Wat voor een lus moeten we gebruiken? 667 00:33:24,380 --> 00:33:25,260 >> PUBLIEK: Hoewel. 668 00:33:25,260 --> 00:33:25,590 >> JASON HIRSCHHORN: Yeah. 669 00:33:25,590 --> 00:33:27,130 Dat heeft meer zin gebaseerd af van wat je zei. 670 00:33:27,130 --> 00:33:29,430 Als we willen gewoon naar we gaan het zou weet alleen dat ding, zou het 671 00:33:29,430 --> 00:33:31,680 zinvol om een ​​while lus doen. 672 00:33:31,680 --> 00:33:39,880 Terwijl de huidige is niet gelijk aan nul, als de waarde lager is dan dit knooppunt. 673 00:33:39,880 --> 00:33:41,650 Akshar, geef mij deze lijn. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> PUBLIEK: Als de huidige-> n n minder dan waarde. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Of omgekeerd dat. 678 00:34:03,260 --> 00:34:06,140 Schakel die beugel. 679 00:34:06,140 --> 00:34:06,620 >> JASON HIRSCHHORN: Sorry. 680 00:34:06,620 --> 00:34:08,760 >> PUBLIEK: Verander de beugel. 681 00:34:08,760 --> 00:34:10,914 >> JASON HIRSCHHORN: Dus als het groter dan waarde. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Want dat is verwarrend met de comment hierboven, ga ik dat doen. 684 00:34:22,120 --> 00:34:22,480 Maar ja. 685 00:34:22,480 --> 00:34:25,125 Als onze waarde lager is dan deze knooppunt, wat doen we? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Ik heb het hier. 688 00:34:26,710 --> 00:34:27,960 Invoegen voor. 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 Hoe doen we dat? 692 00:34:33,933 --> 00:34:34,900 >> PUBLIEK: Is het nog me? 693 00:34:34,900 --> 00:34:36,150 >> JASON HIRSCHHORN: Yeah. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> PUBLIEK: U - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> volgende. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON HIRSCHHORN: Dus wat is dat gaat gelijk? 700 00:34:50,163 --> 00:34:52,070 >> Publiek: Het gaat gelijk stroom. 701 00:34:52,070 --> 00:34:53,889 >> JASON HIRSCHHORN: Precies. 702 00:34:53,889 --> 00:34:55,730 En dus is de andere - 703 00:34:55,730 --> 00:34:56,730 wat hebben we nodig om te werken? 704 00:34:56,730 --> 00:34:59,982 >> PUBLIEK: Controleer of verleden gelijk nul. 705 00:34:59,982 --> 00:35:01,870 >> JASON HIRSCHHORN: als vorige - 706 00:35:01,870 --> 00:35:03,730 dus als vorige gelijk nul. 707 00:35:03,730 --> 00:35:05,990 >> PUBLIEK: Dat betekent dat het gaat het hoofd worden. 708 00:35:05,990 --> 00:35:06,780 >> JASON HIRSCHHORN: Dat betekent het is geworden het hoofd. 709 00:35:06,780 --> 00:35:07,620 Dus wat doen we dan? 710 00:35:07,620 --> 00:35:12,510 >> PUBLIEK: Wij doen hoofd gelijk new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON HIRSCHHORN: Hoofd gelijk new_node. 712 00:35:16,690 --> 00:35:20,540 En waarom hier het hoofd, geen lijst? 713 00:35:20,540 --> 00:35:24,940 >> PUBLIEK: Omdat hoofd is een wereldwijde variabele, die de startplaats. 714 00:35:24,940 --> 00:35:26,190 >> JASON HIRSCHHORN: Zoet. 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 En - 718 00:35:36,150 --> 00:35:53,796 >> PUBLIEK: Dan heb je anders vorige-> volgende evenaart new_node. 719 00:35:53,796 --> 00:35:55,080 En dan terugkeren waar je. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON HIRSCHHORN: Waar doen we new_node einde? 722 00:36:02,700 --> 00:36:04,850 >> Publiek: Ik zou - 723 00:36:04,850 --> 00:36:06,180 Ik dat in het begin. 724 00:36:06,180 --> 00:36:07,430 >> JASON HIRSCHHORN: Dus welke lijn? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> PUBLIEK: Na de instructie if controleren of het bekend is. 727 00:36:12,598 --> 00:36:13,057 >> JASON HIRSCHHORN: Right here? 728 00:36:13,057 --> 00:36:18,335 >> PUBLIEK: ik zou doen new_node-> n is gelijk aan de waarde. 729 00:36:18,335 --> 00:36:19,585 >> JASON HIRSCHHORN: Klinkt goed. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Waarschijnlijk is het logisch - dat doen we niet moet weten wat lijst we op 732 00:36:25,090 --> 00:36:26,280 omdat we alleen te maken met een lijst. 733 00:36:26,280 --> 00:36:29,560 Dus een betere functie verklaring voor dit is gewoon om zich te ontdoen van deze 734 00:36:29,560 --> 00:36:34,360 geheel en plaatst u gewoon een waarde in het hoofd. 735 00:36:34,360 --> 00:36:35,930 We hoeven niet eens te weten wat lijst we binnen 736 00:36:35,930 --> 00:36:39,140 Maar ik zal het blijven voor nu en dan veranderen bij het updaten 737 00:36:39,140 --> 00:36:42,590 de dia's en code. 738 00:36:42,590 --> 00:36:44,980 Dus dat ziet er goed uit voor nu. 739 00:36:44,980 --> 00:36:46,560 Als de waarde - die deze lijn kan doen? 740 00:36:46,560 --> 00:36:47,810 Als - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 wat doen wij hier doen, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> PUBLIEK: Als de waarde groter is dan curr-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON HIRSCHHORN: Hoe gaan we naar de volgende knoop? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> PUBLIEK: Curr-> n gelijk aan new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON HIRSCHHORN: Dus n is welk deel van de structuur? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 De integer. 753 00:37:46,020 --> 00:37:50,420 En new_node is een pointer naar een knooppunt. 754 00:37:50,420 --> 00:37:51,880 Dus welk deel van curr moeten we updaten? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Zo niet n, wat is dan het andere deel? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noah, wat is het andere deel. 759 00:38:22,810 --> 00:38:23,570 >> PUBLIEK: Oh, de volgende. 760 00:38:23,570 --> 00:38:25,645 >> JASON HIRSCHHORN: Next, precies. 761 00:38:25,645 --> 00:38:26,410 Precies. 762 00:38:26,410 --> 00:38:28,770 Vervolgens is de juiste is. 763 00:38:28,770 --> 00:38:31,540 En wat hebben we nodig bij te werken, Noah? 764 00:38:31,540 --> 00:38:32,840 >> Publiek: De wijzers. 765 00:38:32,840 --> 00:38:34,840 >> JASON HIRSCHHORN: Dus we bijgewerkt stroom. 766 00:38:34,840 --> 00:38:36,090 >> PUBLIEK: Vorige-> volgende. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON HIRSCHHORN: Yeah. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, we pauzeren. 771 00:38:58,370 --> 00:39:02,200 Wie kan ons helpen hier? 772 00:39:02,200 --> 00:39:03,385 Manu, wat moeten we doen? 773 00:39:03,385 --> 00:39:05,615 >> PUBLIEK: Je moet instellen het gelijk aan curr-> volgende. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Maar dat doen voordat de vorige regel. 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 Iets anders? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> Publiek: Ik denk niet dat je bent bedoeld om curr-> volgende veranderen. 781 00:39:22,680 --> 00:39:29,270 Ik denk dat je bedoeld om curr gelijken doen curr-> Volgende om naar het volgende knooppunt. 782 00:39:29,270 --> 00:39:30,500 >> JASON HIRSCHHORN: Het spijt me, waar? 783 00:39:30,500 --> 00:39:32,680 Op welke lijn? 784 00:39:32,680 --> 00:39:33,420 Deze lijn? 785 00:39:33,420 --> 00:39:33,750 >> PUBLIEK: Ja. 786 00:39:33,750 --> 00:39:35,745 Maak curr gelijk curr-> volgende. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON HIRSCHHORN: Dus dat klopt omdat de huidige is een 789 00:39:43,360 --> 00:39:45,220 pointer naar een knooppunt. 790 00:39:45,220 --> 00:39:48,550 En we willen dat het wijzen op de volgende knooppunt van wat krijgt momenteel 791 00:39:48,550 --> 00:39:49,930 wees. 792 00:39:49,930 --> 00:39:54,410 Curr zelf heeft een volgende. 793 00:39:54,410 --> 00:39:58,620 Maar als we curr.next updaten, we zou het bijwerken van de eigenlijke noot 794 00:39:58,620 --> 00:40:01,430 zelf, niet waar wijzer wees. 795 00:40:01,430 --> 00:40:02,680 Hoe zit het met deze lijn, dat wel. 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 >> PUBLIEK: Vorige-> volgende evenaart curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON HIRSCHHORN: Dus nogmaals, als vorige is een pointer naar een knooppunt, vorige-> volgende is de 801 00:40:19,440 --> 00:40:23,020 werkelijke aanwijzer in het knooppunt. 802 00:40:23,020 --> 00:40:27,190 Dus dit zou het bijwerken van een aanwijzer in een knoop te curr. 803 00:40:27,190 --> 00:40:28,570 We willen niet werken een pointer in een knoop. 804 00:40:28,570 --> 00:40:30,570 We willen updaten vorige. 805 00:40:30,570 --> 00:40:31,850 Dus hoe kunnen we dat doen? 806 00:40:31,850 --> 00:40:34,250 >> Publiek: Het zou gewoon vorige. 807 00:40:34,250 --> 00:40:34,565 >> JASON HIRSCHHORN: Juist. 808 00:40:34,565 --> 00:40:35,560 Vorig is een pointer naar een knooppunt. 809 00:40:35,560 --> 00:40:38,750 Nu zijn we het omzetten naar een nieuwe pointer naar een knooppunt. 810 00:40:38,750 --> 00:40:40,830 OK Laten we naar beneden gaan. 811 00:40:40,830 --> 00:40:41,940 Tot slot is deze laatste voorwaarde. 812 00:40:41,940 --> 00:40:44,896 Jeff, wat doen we hier doen? 813 00:40:44,896 --> 00:40:47,515 >> PUBLIEK: Als de waarde gelijk aan curr-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON HIRSCHHORN: Sorry. 816 00:40:51,300 --> 00:40:52,372 Oh mijn god. 817 00:40:52,372 --> 00:40:54,330 Wat? 818 00:40:54,330 --> 00:40:55,580 Value == curr-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Wat doen wij? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> PUBLIEK: Je zou onze new_node bevrijden, en dan zou je valse terugkeren. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON HIRSCHHORN: Dit is wat we tot nu toe geschreven. 825 00:41:23,460 --> 00:41:25,710 Heeft iemand iets toe te voegen voordat we te maken? 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 Laten we het proberen. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Controle kan het einde te bereiken van een niet-lege functie. 831 00:41:46,110 --> 00:41:48,310 Avi, wat gebeurt er? 832 00:41:48,310 --> 00:41:51,380 >> PUBLIEK: Bent u verondersteld om rendement te zetten ware buiten de while loop? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON HIRSCHHORN: Ik weet het niet. 835 00:41:54,400 --> 00:41:54,780 Wil je dat ik aan? 836 00:41:54,780 --> 00:41:55,520 >> PUBLIEK: Never mind. 837 00:41:55,520 --> 00:41:56,350 Nee. 838 00:41:56,350 --> 00:41:57,180 >> JASON HIRSCHHORN: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> Publiek: Ik denk dat je bedoeld om zet return valse aan het eind 840 00:41:59,460 --> 00:42:02,230 van de while-lus. 841 00:42:02,230 --> 00:42:03,270 >> JASON HIRSCHHORN: Dus waar wil je het gaan? 842 00:42:03,270 --> 00:42:05,270 >> PUBLIEK: Net buiten de while lus. 843 00:42:05,270 --> 00:42:08,800 Dus als je de while lus die middelen te verlaten dat je het einde hebt bereikt en 844 00:42:08,800 --> 00:42:09,980 niets is gebeurd. 845 00:42:09,980 --> 00:42:10,410 >> JASON HIRSCHHORN: OK. 846 00:42:10,410 --> 00:42:12,340 Dus wat doen we hier? 847 00:42:12,340 --> 00:42:13,702 >> PUBLIEK: U return false daar ook. 848 00:42:13,702 --> 00:42:15,040 >> JASON HIRSCHHORN: Oh, we doe het in beide plaatsen? 849 00:42:15,040 --> 00:42:15,650 >> PUBLIEK: 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 Moeten we gaan? 853 00:42:26,160 --> 00:42:26,980 Oh mijn god. 854 00:42:26,980 --> 00:42:27,290 Het spijt me. 855 00:42:27,290 --> 00:42:28,480 Ik verontschuldig me voor het scherm. 856 00:42:28,480 --> 00:42:30,530 Het is een soort van freaken op ons. 857 00:42:30,530 --> 00:42:31,520 Dus kies een optie. 858 00:42:31,520 --> 00:42:35,260 Nul, volgens de code, stopt het programma. 859 00:42:35,260 --> 00:42:36,700 Men voegt iets. 860 00:42:36,700 --> 00:42:37,990 Laten we drie plaatsen. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 De insert is mislukt. 863 00:42:45,380 --> 00:42:46,500 Ik ga om uit te printen. 864 00:42:46,500 --> 00:42:48,050 Ik heb helemaal niets. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Misschien dat was gewoon een toevalstreffer. 867 00:42:50,250 --> 00:42:52,810 Plaats een. 868 00:42:52,810 --> 00:42:55,770 Niet succesvol. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Laten we lopen door GDB heel snel om te controleren wat er gaande is. 871 00:43:02,400 --> 00:43:06,055 >> Vergeet gdb. / De naam van uw programma brengt ons in GDB. 872 00:43:06,055 --> 00:43:07,610 Is dat een veel te hanteren? 873 00:43:07,610 --> 00:43:08,560 De knipperende? 874 00:43:08,560 --> 00:43:10,400 Waarschijnlijk. 875 00:43:10,400 --> 00:43:12,760 Sluit je ogen en haal een paar keer diep ademt als je moe 876 00:43:12,760 --> 00:43:13,580 naar te kijken. 877 00:43:13,580 --> 00:43:14,200 Ik ben in GDB. 878 00:43:14,200 --> 00:43:15,830 Wat is het eerste wat ik doe in GDB? 879 00:43:15,830 --> 00:43:17,050 We moeten uitzoeken wat hier aan de hand. 880 00:43:17,050 --> 00:43:17,310 Laten we eens kijken. 881 00:43:17,310 --> 00:43:21,650 We hebben zes minuten figuur te komen wat er gaande is. 882 00:43:21,650 --> 00:43:22,900 Breken belangrijkste. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 En wat moet ik doen? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Run. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Laten we kiezen voor een optie. 889 00:43:34,160 --> 00:43:36,330 En wat doet N doen? 890 00:43:36,330 --> 00:43:38,480 Volgende. 891 00:43:38,480 --> 00:43:38,950 Yeah. 892 00:43:38,950 --> 00:43:39,740 >> PUBLIEK: Heb je niet vergeten - 893 00:43:39,740 --> 00:43:45,230 heb je niet zeggen dat de kop, het was geïnitialiseerd op nul bij het begin. 894 00:43:45,230 --> 00:43:47,140 Maar ik dacht dat je zei dat was OK. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON HIRSCHHORN: Laten we gaan - laten we eens kijken in GDB, en dan gaan we terug. 897 00:43:52,640 --> 00:43:54,910 Maar het klinkt alsof je al hebt een aantal ideeën over wat er gaande is. 898 00:43:54,910 --> 00:43:58,340 Dus we willen iets in te voegen. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Wij voegen. 901 00:44:00,150 --> 00:44:00,770 Vul een int. 902 00:44:00,770 --> 00:44:01,990 We zullen drie plaatsen. 903 00:44:01,990 --> 00:44:03,000 En dan ben ik op deze lijn. 904 00:44:03,000 --> 00:44:07,030 Hoe ga ik beginnen met debuggen de insert bekende functie? 905 00:44:07,030 --> 00:44:08,280 Oh mijn god. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 Dat is veel. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Wordt dat freaking out veel? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> PUBLIEK: Oh, het stierf. 912 00:44:21,680 --> 00:44:22,930 >> JASON HIRSCHHORN: Ik heb net trok het uit. 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 >> PUBLIEK: Misschien is het de andere uiteinde van de draad. 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 Dus de onderste regel - 919 00:44:42,330 --> 00:44:43,470 wat zeg je? 920 00:44:43,470 --> 00:44:46,040 >> Publiek: Ik zei dat de ironie van technische moeilijkheden in deze klasse. 921 00:44:46,040 --> 00:44:46,410 >> JASON HIRSCHHORN: Ik weet het. 922 00:44:46,410 --> 00:44:48,660 Als ik had controle over dat deel. 923 00:44:48,660 --> 00:44:49,910 [Onverstaanbaar] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Dat klinkt geweldig. 926 00:44:55,400 --> 00:44:58,680 Waarom gaan jullie niet gaan nadenken over wat we konden verkeerd hebben gedaan, 927 00:44:58,680 --> 00:45:01,140 en we zullen terug in 90 seconden. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, ga ik je vragen hoe om te gaan binnen insert_node te debuggen. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 Dus dit is waar we het laatst gebleven was. 932 00:46:31,460 --> 00:46:35,110 Hoe kan ik naar binnen insert_node, Avica, om te onderzoeken wat er aan de hand? 933 00:46:35,110 --> 00:46:36,360 Wat GDB commando? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Break zou me niet binnen. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Heeft Marquise weten? 938 00:46:47,130 --> 00:46:48,240 >> PUBLIEK: Wat? 939 00:46:48,240 --> 00:46:51,780 >> JASON HIRSCHHORN: Wat GDB commando Ik gebruik te gaan binnen deze functie? 940 00:46:51,780 --> 00:46:52,070 >> PUBLIEK: Step? 941 00:46:52,070 --> 00:46:55,140 >> JASON HIRSCHHORN: Stap via S. Dat binnenkant kost me. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing wat ruimte. 944 00:46:58,040 --> 00:46:59,120 Dat alles lijkt op haar gaan. 945 00:46:59,120 --> 00:47:00,370 Laten we eens onderzoeken new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Het kreeg een aantal geheugen adres. 948 00:47:05,410 --> 00:47:07,440 Laten we eens kijken - 949 00:47:07,440 --> 00:47:08,500 dat is allemaal correct. 950 00:47:08,500 --> 00:47:12,220 Dus alles lijkt hier correct werken. 951 00:47:12,220 --> 00:47:14,530 >> Publiek: Wat is het verschil tussen P en scherm? 952 00:47:14,530 --> 00:47:16,160 >> JASON HIRSCHHORN: P staat voor print. 953 00:47:16,160 --> 00:47:19,310 En dus je vraagt ​​wat is de verschil tussen dat en dit? 954 00:47:19,310 --> 00:47:22,330 In dit geval niets. 955 00:47:22,330 --> 00:47:26,960 Meestal zijn er wel enkele verschillen. 956 00:47:26,960 --> 00:47:28,220 En moet je kijken in het GDB handleiding. 957 00:47:28,220 --> 00:47:29,560 Maar in dit geval niets. 958 00:47:29,560 --> 00:47:31,460 We hebben de neiging om afdruk te gebruiken, maar, omdat we hoeven niet veel meer doen dan 959 00:47:31,460 --> 00:47:33,960 afdrukken van een enkele waarde. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 Dus we zijn op lijn 80 van onze code, het instellen van knooppunt * curr gelijk aan lijst. 962 00:47:40,300 --> 00:47:42,500 Laten we uitprinten curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Het is gelijk aan de lijst. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Wacht. 967 00:47:49,340 --> 00:47:50,590 Het is gelijk iets. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Dat lijkt niet juist. 970 00:47:56,190 --> 00:47:56,840 Daar gaan we. 971 00:47:56,840 --> 00:47:59,470 Het is omdat in GDB, rechts, indien het is de lijn je op het 972 00:47:59,470 --> 00:48:00,330 is nog niet uitgevoerd. 973 00:48:00,330 --> 00:48:03,100 Dus je moet eigenlijk typen naast de lijn uit te voeren 974 00:48:03,100 --> 00:48:05,230 voordat het zien van de resultaten. 975 00:48:05,230 --> 00:48:06,680 Dus hier zijn we. 976 00:48:06,680 --> 00:48:09,490 We hebben net deze lijn uitgevoerd, vorige gelijk aan null. 977 00:48:09,490 --> 00:48:13,590 Dus nogmaals, als we drukken vorige zullen we niet zien iets vreemds. 978 00:48:13,590 --> 00:48:18,680 Maar als we daadwerkelijk uit te voeren dat lijn, dan zullen we zien 979 00:48:18,680 --> 00:48:20,380 dat die lijn gewerkt. 980 00:48:20,380 --> 00:48:21,060 >> Dus we hebben curr. 981 00:48:21,060 --> 00:48:23,180 Dat zijn allebei goed. 982 00:48:23,180 --> 00:48:24,010 Rechts? 983 00:48:24,010 --> 00:48:28,130 Nu zijn we op deze lijn hier. 984 00:48:28,130 --> 00:48:29,310 Terwijl curr is niet gelijk aan nul. 985 00:48:29,310 --> 00:48:31,110 Nou, wat doet curr gelijk? 986 00:48:31,110 --> 00:48:32,450 We zagen het gewoon geëvenaard null. 987 00:48:32,450 --> 00:48:33,210 We uitgeprint. 988 00:48:33,210 --> 00:48:35,110 Ik zal het er weer uit te printen. 989 00:48:35,110 --> 00:48:36,720 Zo is dat, terwijl lus gaan voeren? 990 00:48:36,720 --> 00:48:37,270 >> PUBLIEK: Nee 991 00:48:37,270 --> 00:48:39,790 >> JASON HIRSCHHORN: Zodat wanneer ik typte lijn, zie je sprongen we de hele weg 992 00:48:39,790 --> 00:48:41,390 tot op de bodem, return false. 993 00:48:41,390 --> 00:48:44,520 En dan gaan we return false en ga terug naar ons programma en 994 00:48:44,520 --> 00:48:48,020 uiteindelijk uit te printen, zoals we zagen, de insert was niet succesvol. 995 00:48:48,020 --> 00:48:51,010 Dus, iemand enig idee over wat we moeten doen om dit op te lossen? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Ik ga wachten tot ik zie een paar handen gaan omhoog. 998 00:48:57,570 --> 00:48:58,830 We hebben dit niet uitvoeren. 999 00:48:58,830 --> 00:49:01,660 Houd in gedachten, dit was de eerste wat we aan het doen waren. 1000 00:49:01,660 --> 00:49:02,430 Ik ben niet van plan om een ​​paar te doen. 1001 00:49:02,430 --> 00:49:03,670 Ik ga een paar doen. 1002 00:49:03,670 --> 00:49:04,830 Omdat een paar betekent twee. 1003 00:49:04,830 --> 00:49:07,620 Ik wacht op meer dan twee. 1004 00:49:07,620 --> 00:49:10,690 >> De eerste insertie, curr, standaard is gelijk aan null. 1005 00:49:10,690 --> 00:49:14,050 En alleen deze lus voert als curr is niet nul. 1006 00:49:14,050 --> 00:49:18,740 Dus hoe kan ik rond dit? 1007 00:49:18,740 --> 00:49:19,990 Ik zie drie handen. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Ik wacht op meer dan drie. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, wat denk je? 1012 00:49:35,940 --> 00:49:37,730 >> PUBLIEK: Nou, als je het nodig hebt om voeren meer dan eens, je gewoon 1013 00:49:37,730 --> 00:49:39,948 veranderen in een do-while lus. 1014 00:49:39,948 --> 00:49:41,250 >> JASON HIRSCHHORN: OK. 1015 00:49:41,250 --> 00:49:44,240 Zal dat ons probleem op te lossen, hoewel? 1016 00:49:44,240 --> 00:49:47,750 >> PUBLIEK: In dit geval is geen gevolg van het feit dat de lijst leeg. 1017 00:49:47,750 --> 00:49:52,150 Dus dan heb je waarschijnlijk gewoon moet toevoegen een verklaring dat als de lus uitgangen 1018 00:49:52,150 --> 00:49:55,312 dan moet je op het einde van de lijst, op welk punt je 1019 00:49:55,312 --> 00:49:56,562 kan gewoon invoegen. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON HIRSCHHORN: Dat vind ik leuk. 1022 00:49:59,680 --> 00:50:00,500 Dat klinkt logisch. 1023 00:50:00,500 --> 00:50:03,390 Als de lus verlaat - 1024 00:50:03,390 --> 00:50:04,800 want het zal hier return false. 1025 00:50:04,800 --> 00:50:08,220 Dus als de lus verlaat, dan zijn we op het einde van de lijst, of misschien de 1026 00:50:08,220 --> 00:50:10,690 starten van een lijst als er niets in het, wat hetzelfde is als het einde. 1027 00:50:10,690 --> 00:50:12,770 Dus nu willen we voegen hier iets. 1028 00:50:12,770 --> 00:50:17,380 Dus hoe die code kijken, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> PUBLIEK: Als je al het knooppunt malloced, kon je gewoon zeggen 1030 00:50:21,600 --> 00:50:25,400 new_node-> volgende is gelijk nul, omdat het moet eind. 1031 00:50:25,400 --> 00:50:27,510 Of new_node-> volgende gelijk nul. 1032 00:50:27,510 --> 00:50:27,765 >> JASON HIRSCHHORN: OK. 1033 00:50:27,765 --> 00:50:28,190 Sorry. 1034 00:50:28,190 --> 00:50:35,760 New_node-> volgende evenaart null want we zijn aan het einde. 1035 00:50:35,760 --> 00:50:36,460 Dat plaatst hem nog niet binnen 1036 00:50:36,460 --> 00:50:37,710 Hoe zetten we het in de lijst? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Rechts. 1039 00:50:46,460 --> 00:50:47,750 Dat is gewoon de oprichting ervan gelijk aan. 1040 00:50:47,750 --> 00:50:50,940 Geen hoe kunnen we eigenlijk zet het in de lijst? 1041 00:50:50,940 --> 00:50:54,170 Wat wijst naar de einde van de lijst? 1042 00:50:54,170 --> 00:50:56,090 >> PUBLIEK: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON HIRSCHHORN: Sorry? 1044 00:50:57,566 --> 00:50:59,440 >> PUBLIEK: Hoofd wijst aan het einde van de lijst. 1045 00:50:59,440 --> 00:51:01,480 >> JASON HIRSCHHORN: Als er niets in de lijst, wordt het hoofd wijst naar de 1046 00:51:01,480 --> 00:51:04,170 einde van de lijst. 1047 00:51:04,170 --> 00:51:06,920 Dus dat zal werken voor de eerste plaatsing. 1048 00:51:06,920 --> 00:51:09,810 Hoe zit het als er een paar dingen in de lijst? 1049 00:51:09,810 --> 00:51:12,470 Dan we willen niet instellen ga gelijk aan new_node. 1050 00:51:12,470 --> 00:51:13,790 Wat willen we daar doen? 1051 00:51:13,790 --> 00:51:15,610 Yeah? 1052 00:51:15,610 --> 00:51:16,860 Waarschijnlijk vorige. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Zal dat werken? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Bedenk dat vorige is gewoon een pointer naar een knooppunt. 1057 00:51:33,050 --> 00:51:34,770 En eerdere is een lokale variabele. 1058 00:51:34,770 --> 00:51:38,080 Dus deze lijn zal een lokale variabele in te stellen, previous gelijk aan of 1059 00:51:38,080 --> 00:51:39,380 dat naar het nieuwe knooppunt. 1060 00:51:39,380 --> 00:51:41,500 Dat zal niet echt zet het in onze lijst, dat wel. 1061 00:51:41,500 --> 00:51:44,330 Hoe kunnen we het in onze lijst? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> Publiek: Ik denk dat je do huidige-> volgende. 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 curr-> volgende. 1067 00:51:54,010 --> 00:51:58,768 Dus nogmaals, de enige reden waarom we naar beneden hier is, wat doet stroom gelijk? 1068 00:51:58,768 --> 00:51:59,760 >> PUBLIEK: Is gelijk aan null. 1069 00:51:59,760 --> 00:52:01,790 >> JASON HIRSCHHORN: En wat gebeurt er als we dat doen null-> volgende? 1070 00:52:01,790 --> 00:52:02,810 Wat doen we gaan krijgen? 1071 00:52:02,810 --> 00:52:04,060 We zullen een segmentation fault krijgen. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> PUBLIEK: Do curr gelijk aan null. 1074 00:52:08,880 --> 00:52:10,760 >> JASON HIRSCHHORN: Dat is hetzelfde als vorige, hoewel, omdat er 1075 00:52:10,760 --> 00:52:12,820 een lokale variabele we bent instelling gelijk aan deze nieuwe knoop. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Laten we teruggaan naar onze foto van het plaatsen van iets. 1078 00:52:20,920 --> 00:52:25,500 Zeggen dat we het invoegen aan het einde van de lijst, dus hier. 1079 00:52:25,500 --> 00:52:30,010 We hebben een actuele pointer dat is wijzend op null en een vorig punt 1080 00:52:30,010 --> 00:52:32,800 die wijst naar 8. 1081 00:52:32,800 --> 00:52:35,330 Dus wat hebben we nodig om te werken, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> PUBLIEK: Vorige-> volgende? 1083 00:52:36,680 --> 00:52:41,980 >> JASON HIRSCHHORN: Vorige-> volgende is wat we willen werken, want dat 1084 00:52:41,980 --> 00:52:44,960 daadwerkelijk plaatst u deze op het einde van de lijst. 1085 00:52:44,960 --> 00:52:47,220 We hebben nog steeds een bug, hoewel, dat we gaan tegenkomen. 1086 00:52:47,220 --> 00:52:50,090 Wat is dat fout? 1087 00:52:50,090 --> 00:52:50,790 Yeah? 1088 00:52:50,790 --> 00:52:53,860 >> PUBLIEK: Het gaat om terug te keren vals in dit geval? 1089 00:52:53,860 --> 00:52:56,380 >> JASON HIRSCHHORN: Oh, is wordt gaan return false. 1090 00:52:56,380 --> 00:52:57,430 Maar er is nog een bug. 1091 00:52:57,430 --> 00:52:58,930 Dus we moeten in ruil daarvoor trouw aan zetten. 1092 00:52:58,930 --> 00:53:01,370 >> PUBLIEK: Heeft vorige nog steeds gelijk null aan de top van de lijst? 1093 00:53:01,370 --> 00:53:03,645 >> JASON HIRSCHHORN: Dus vorige stilstaand gelijk aan nul aan het begin. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Dus hoe kunnen we meer dan dat? 1096 00:53:10,440 --> 00:53:10,950 Yeah? 1097 00:53:10,950 --> 00:53:15,280 >> Publiek: Ik denk dat je een controle te doen voordat de while lus om te zien of het 1098 00:53:15,280 --> 00:53:16,610 een lege lijst. 1099 00:53:16,610 --> 00:53:17,000 >> JASON HIRSCHHORN: OK. 1100 00:53:17,000 --> 00:53:17,710 Dus laten we gaan hier. 1101 00:53:17,710 --> 00:53:18,530 Doe een cheque. 1102 00:53:18,530 --> 00:53:19,380 Als - 1103 00:53:19,380 --> 00:53:20,770 >> PUBLIEK: Dus als hoofd gelijk gelijk aan null. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON HIRSCHHORN: Als hoofd gelijk gelijk aan null - 1106 00:53:26,320 --> 00:53:27,790 dat zal ons vertellen of het een lege lijst. 1107 00:53:27,790 --> 00:53:31,090 >> PUBLIEK: En dan heb je do hoofd is gelijk aan nieuw. 1108 00:53:31,090 --> 00:53:34,740 >> JASON HIRSCHHORN: Hoofd gelijk new_node? 1109 00:53:34,740 --> 00:53:35,730 En wat moeten we doen? 1110 00:53:35,730 --> 00:53:37,020 >> PUBLIEK: En dan heb je echt terug. 1111 00:53:37,020 --> 00:53:37,535 >> JASON HIRSCHHORN: Niet helemaal. 1112 00:53:37,535 --> 00:53:38,785 We missen een stap. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> PUBLIEK: new_node volgende moet wijzen op null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON HIRSCHHORN: Precies, Alden. 1116 00:53:44,570 --> 00:53:46,600 En dan kunnen we echt terug. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 Maar het is nog steeds een goed idee om dingen te doen aan het einde van de lijst, toch? 1119 00:53:51,630 --> 00:53:51,950 Oke. 1120 00:53:51,950 --> 00:53:54,450 We zouden eigenlijk nog wel krijgen aan het einde van de lijst. 1121 00:53:54,450 --> 00:53:57,870 Dus is deze code prima als we op de het einde van de lijst en er zijn enkele 1122 00:53:57,870 --> 00:53:59,120 dingen in de lijst? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Rechts? 1125 00:54:02,040 --> 00:54:03,540 Want we hebben nog idee Marcus. 1126 00:54:03,540 --> 00:54:06,870 We zouden deze lus te verlaten, omdat we zijn aan het einde van de lijst. 1127 00:54:06,870 --> 00:54:09,308 Dus doen we nog steeds dit willen coderen hier beneden? 1128 00:54:09,308 --> 00:54:10,520 >> PUBLIEK: Ja. 1129 00:54:10,520 --> 00:54:11,000 >> JASON HIRSCHHORN: Yeah. 1130 00:54:11,000 --> 00:54:14,190 En wat hebben we nodig om dit te veranderen naar? 1131 00:54:14,190 --> 00:54:15,440 True. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Klinkt dat goed iedereen tot nu toe? 1134 00:54:21,640 --> 00:54:22,420 Iemand enig - 1135 00:54:22,420 --> 00:54:23,480 Avi, doe je iets toevoegen? 1136 00:54:23,480 --> 00:54:23,920 >> PUBLIEK: Nee 1137 00:54:23,920 --> 00:54:25,276 >> JASON HIRSCHHORN: OK. 1138 00:54:25,276 --> 00:54:27,010 Dus we hebben een paar wijzigingen. 1139 00:54:27,010 --> 00:54:29,540 We hebben deze controle gedaan voordat we ging voor een lege lijst. 1140 00:54:29,540 --> 00:54:31,790 Dus we hebben gezorgd een lege lijst. 1141 00:54:31,790 --> 00:54:35,500 En hier hebben we de zorg van het plaatsen van iets aan het einde van de lijst. 1142 00:54:35,500 --> 00:54:38,930 Dus het lijkt erop dat deze while lus nemen verzorgen van de dingen in tussen, 1143 00:54:38,930 --> 00:54:41,920 ergens in de lijst als er zijn dingen in de lijst. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Laten we dit programma opnieuw uit te voeren. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Niet succesvol. 1148 00:54:50,755 --> 00:54:52,190 >> PUBLIEK: U heeft het niet gehaald. 1149 00:54:52,190 --> 00:54:53,940 >> JASON HIRSCHHORN: Oh, Ik heb het niet gehaald. 1150 00:54:53,940 --> 00:54:56,250 Goed punt, Michael. 1151 00:54:56,250 --> 00:54:57,500 Laten we eerst nog te maken met elkaar verbonden. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Lijn 87 is er een fout. 1154 00:55:04,830 --> 00:55:05,420 Lijn 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, dit was de lijn die je me gaf. 1156 00:55:06,600 --> 00:55:08,962 Wat is er mis? 1157 00:55:08,962 --> 00:55:10,710 >> Publiek: Het moet op null. 1158 00:55:10,710 --> 00:55:11,000 >> JASON HIRSCHHORN: Excellent. 1159 00:55:11,000 --> 00:55:11,630 Precies goed. 1160 00:55:11,630 --> 00:55:13,290 Het moet nul zijn. 1161 00:55:13,290 --> 00:55:15,210 Laten we weer. 1162 00:55:15,210 --> 00:55:17,220 Samen te stellen. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Laten we drie plaatsen. 1165 00:55:19,400 --> 00:55:20,570 De insert is geslaagd. 1166 00:55:20,570 --> 00:55:21,660 Laten printen. 1167 00:55:21,660 --> 00:55:23,590 O, als we konden controleren. 1168 00:55:23,590 --> 00:55:25,500 Maar we hebben niet gedaan afdrukken nog functie. 1169 00:55:25,500 --> 00:55:27,840 Laten we iets anders gaan. 1170 00:55:27,840 --> 00:55:29,090 Wat moeten we voeren? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> PUBLIEK: Zeven. 1173 00:55:31,940 --> 00:55:33,340 >> JASON HIRSCHHORN: Seven? 1174 00:55:33,340 --> 00:55:34,590 >> PUBLIEK: Ja. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON HIRSCHHORN: We hebben een seg fout. 1177 00:55:39,780 --> 00:55:43,760 Dus we hebben een, maar we duidelijk kan niet twee. 1178 00:55:43,760 --> 00:55:45,690 Het is 05:07. 1179 00:55:45,690 --> 00:55:48,370 Dus we konden deze debug gedurende drie minuten. 1180 00:55:48,370 --> 00:55:51,240 Maar ik ga om ons hier te vertrekken en gaan naar tabellen hash. 1181 00:55:51,240 --> 00:55:54,290 Maar nogmaals, de antwoorden voor deze code Ik zal het e-mail naar u in een beetje. 1182 00:55:54,290 --> 00:55:55,440 We zijn erg dicht bij. 1183 00:55:55,440 --> 00:55:58,300 Ik je ten zeerste aan te moedigen om erachter te komen wat er hier op en zet het vast. 1184 00:55:58,300 --> 00:56:02,400 Dus ik zal u e-mail de code als goed plus de oplossing - 1185 00:56:02,400 --> 00:56:03,670 waarschijnlijk de oplossing later. 1186 00:56:03,670 --> 00:56:05,110 Eerst deze code. 1187 00:56:05,110 --> 00:56:08,290 >> Het andere wat ik wil doen voordat we afwerking is we hebben niets bevrijd. 1188 00:56:08,290 --> 00:56:10,370 Dus ik wil je laten zien wat valgrind eruit ziet. 1189 00:56:10,370 --> 00:56:14,310 Als we lopen valgrind grenzen op ons programma. / gekoppeld. 1190 00:56:14,310 --> 00:56:22,540 Ook volgens deze dia, we moet valgrind lopen met een soort van 1191 00:56:22,540 --> 00:56:26,410 Geef in dit geval - Lek-check = vol. 1192 00:56:26,410 --> 00:56:27,660 Dus laten we schrijven valgrind - Lek-check = vol. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Dus dit zal valgrind draaien op ons programma. 1195 00:56:35,080 --> 00:56:37,000 En nu het programma daadwerkelijk wordt uitgevoerd. 1196 00:56:37,000 --> 00:56:40,190 Dus we gaan om het uit te voeren, net als vóór, zet iets in 1197 00:56:40,190 --> 00:56:40,830 Ik ga in drie zetten. 1198 00:56:40,830 --> 00:56:41,790 Dat werkt. 1199 00:56:41,790 --> 00:56:43,202 Ik ga niet proberen iets te zetten anders want we gaan naar 1200 00:56:43,202 --> 00:56:44,710 krijgen een seg vals in dat geval. 1201 00:56:44,710 --> 00:56:46,700 Dus ik ga gewoon om te stoppen. 1202 00:56:46,700 --> 00:56:50,160 >> En nu zie je beneden lekken en heap samenvatting. 1203 00:56:50,160 --> 00:56:52,310 Dit zijn de goede dingen die u wilt controleren. 1204 00:56:52,310 --> 00:56:56,780 Dus de hoop samenvatting - het zegt, in gebruik bij afslag - acht bits in een blok. 1205 00:56:56,780 --> 00:56:58,370 Dat een blok is de knooppunt we malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, je zei eerder een knooppunt is acht beten omdat het de integer 1207 00:57:02,230 --> 00:57:02,680 en de aanwijzer. 1208 00:57:02,680 --> 00:57:04,550 Dus dat is onze knooppunt. 1209 00:57:04,550 --> 00:57:08,170 En dan staat we gebruikten malloc zeven keer en we bevrijd 1210 00:57:08,170 --> 00:57:08,940 iets zes keer. 1211 00:57:08,940 --> 00:57:13,680 Maar we nooit vrij heet, dus ik heb geen idee wat dit is het over. 1212 00:57:13,680 --> 00:57:18,490 >> Maar het volstaat te zeggen dat wanneer uw programma wordt uitgevoerd, wordt malloc geroepen 1213 00:57:18,490 --> 00:57:20,330 in sommige andere plaatsen die we geen zorgen te maken over. 1214 00:57:20,330 --> 00:57:22,460 Dus malloc werd waarschijnlijk genoemd op sommige plaatsen. 1215 00:57:22,460 --> 00:57:24,480 We hebben geen zorgen te maken waar. 1216 00:57:24,480 --> 00:57:26,240 Maar dit is echt ons. 1217 00:57:26,240 --> 00:57:27,380 Deze eerste lijn is met ons. 1218 00:57:27,380 --> 00:57:28,320 We vertrokken dat blok. 1219 00:57:28,320 --> 00:57:30,330 En je kunt zien dat hier in het lek samenvatting. 1220 00:57:30,330 --> 00:57:31,950 Nog steeds bereikbaar - 1221 00:57:31,950 --> 00:57:32,930 acht bits in een blok. 1222 00:57:32,930 --> 00:57:34,100 Dit betekent dat het geheugen - 1223 00:57:34,100 --> 00:57:35,730 we hebben dat geheugen gelekt. 1224 00:57:35,730 --> 00:57:37,570 Zeker verloren - 1225 00:57:37,570 --> 00:57:38,770 iets voorgoed verloren is gegaan. 1226 00:57:38,770 --> 00:57:40,590 Over het algemeen zul je niet zie niets daar. 1227 00:57:40,590 --> 00:57:44,780 Nog steeds bereikbaar is over het algemeen waar je zult dingen zien, waar je wilt 1228 00:57:44,780 --> 00:57:48,900 te kijken om te zien welke code je moet hebben bevrijd, maar je vergat te bevrijden. 1229 00:57:48,900 --> 00:57:53,170 >> En als dit niet het geval was, als we dat alles gratis, 1230 00:57:53,170 --> 00:57:54,360 we kunnen controleren dat. 1231 00:57:54,360 --> 00:57:57,330 Laten we gewoon het programma uit te voeren niet zetten in iets. 1232 00:57:57,330 --> 00:57:59,800 Je zult zien hier in gebruik bij afslag - 1233 00:57:59,800 --> 00:58:01,310 nul bytes nul blokken. 1234 00:58:01,310 --> 00:58:06,310 Dat betekent dat we hadden niets meer wanneer dit programma verlaten. 1235 00:58:06,310 --> 00:58:12,090 Dus voordat u in pset6, lopen valgrind en zorg ervoor dat u niet hoeft 1236 00:58:12,090 --> 00:58:15,310 alle vormen van geheugen lekken in uw programma. 1237 00:58:15,310 --> 00:58:17,910 Als u vragen heeft met valgrind, voel je vrij om uit te reiken. 1238 00:58:17,910 --> 00:58:18,700 Maar dit is hoe je het gebruikt. 1239 00:58:18,700 --> 00:58:20,890 Heel eenvoudig - kijk of je in gebruik hebben bij afslag - 1240 00:58:20,890 --> 00:58:22,270 elke bytes alle blokken. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Dus we waren bezig met insert knooppunt. 1243 00:58:29,580 --> 00:58:33,840 Ik had twee andere functies hier - afdrukken knooppunten en vrije knopen. 1244 00:58:33,840 --> 00:58:37,780 Nogmaals, dit zijn functies die goed te zijn voor u om te oefenen 1245 00:58:37,780 --> 00:58:40,990 omdat ze je niet alleen helpen met deze steekproef oefeningen, maar ook 1246 00:58:40,990 --> 00:58:42,180 het probleem stellen. 1247 00:58:42,180 --> 00:58:44,230 Ze kaart op vrij nauw om dingen je gaat moeten doen in de 1248 00:58:44,230 --> 00:58:45,010 probleem stellen. 1249 00:58:45,010 --> 00:58:47,640 Maar ik wil ervoor zorgen dat we ingaan op alles. 1250 00:58:47,640 --> 00:58:50,400 En hash tabellen zijn ook van cruciaal belang om wat we doen in deze sectie 1251 00:58:50,400 --> 00:58:51,980 week - of het probleem set. 1252 00:58:51,980 --> 00:58:55,200 >> Dus we gaan naar de sectie afmaken praten over hash tables. 1253 00:58:55,200 --> 00:58:58,140 Als u merkt dat ik een beetje hash table. 1254 00:58:58,140 --> 00:59:00,020 Dat is niet waar we het over, echter. 1255 00:59:00,020 --> 00:59:03,540 We hebben het over een andere type hash tabellen. 1256 00:59:03,540 --> 00:59:07,300 En in de kern, een hash table is niets meer dan een 1257 00:59:07,300 --> 00:59:08,860 serie plus een hash-functie. 1258 00:59:08,860 --> 00:59:11,150 We gaan voor een beetje te praten alleen maar om zorgen dat iedereen begrijpt wat een 1259 00:59:11,150 --> 00:59:12,110 hash-functie is. 1260 00:59:12,110 --> 00:59:15,420 En ik zeg je nu dat het niets meer dan twee dingen - 1261 00:59:15,420 --> 00:59:18,590 een array en een hash-functie. 1262 00:59:18,590 --> 00:59:20,716 En hier zijn de stappen door waarin deze actief is. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Er is ons aanbod. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Daar is onze functie. 1267 00:59:39,460 --> 00:59:43,180 Met name moet hash functies doe een paar dingen met dit. 1268 00:59:43,180 --> 00:59:45,040 Ik ga specifiek hebben over dit probleem te stellen. 1269 00:59:45,040 --> 00:59:46,450 Het gaat waarschijnlijk nemen in een string. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 En wat gaat het om terug te keren? 1272 00:59:51,770 --> 00:59:52,640 Welke gegevens soort? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Uw hash-functie terug te keren? 1275 00:59:55,760 --> 00:59:58,760 Een geheel getal. 1276 00:59:58,760 --> 01:00:01,700 Dus dit is wat de hash tabel bestaat uit - 1277 01:00:01,700 --> 01:00:05,430 een tafel in de vorm van een matrix en een hash-functie. 1278 01:00:05,430 --> 01:00:06,010 Hoe het werkt? 1279 01:00:06,010 --> 01:00:07,300 Het werkt in drie stappen. 1280 01:00:07,300 --> 01:00:08,740 Wij geven het een sleutel. 1281 01:00:08,740 --> 01:00:11,470 In dit geval, zullen we het een string. 1282 01:00:11,470 --> 01:00:18,140 We noemen de hash-functie per stap een op de sleutel en we krijgen een waarde. 1283 01:00:18,140 --> 01:00:20,310 >> Concreet zullen we zeggen krijgen we een integer. 1284 01:00:20,310 --> 01:00:25,630 Dat integer, kunnen de zeer specifieke grenzen aan wat dat getal kan zijn. 1285 01:00:25,630 --> 01:00:28,880 In dit voorbeeld ons aanbod is van grote drie. 1286 01:00:28,880 --> 01:00:32,330 Wat nummers die geheel getal zijn. 1287 01:00:32,330 --> 01:00:35,970 Wat is het bereik van geldige waarden voor dat integer, de return type van deze 1288 01:00:35,970 --> 01:00:37,220 hash-functie? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Nul, een en twee. 1291 01:00:42,110 --> 01:00:46,060 Het punt van de hash-functie is achterhalen van de plaats in de array 1292 01:00:46,060 --> 01:00:47,790 waar onze sleutel gaat. 1293 01:00:47,790 --> 01:00:51,290 Er zijn slechts drie mogelijke plaatsen hier - 1294 01:00:51,290 --> 01:00:52,130 nul, een of twee. 1295 01:00:52,130 --> 01:00:55,360 Dus deze functie beter rendement nul, een of twee. 1296 01:00:55,360 --> 01:00:58,740 Sommige geldig indice in deze array. 1297 01:00:58,740 --> 01:01:02,770 >> En afhankelijk van waar het terugkeert, je kunt er matrix zien geopend 1298 01:01:02,770 --> 01:01:03,730 beugel de waarde. 1299 01:01:03,730 --> 01:01:05,800 Dat is waar we de sleutel. 1300 01:01:05,800 --> 01:01:11,280 Dus we gooien in de pompoen, we uit nul. 1301 01:01:11,280 --> 01:01:15,540 Bij serie beugel 0, hebben we pompoen. 1302 01:01:15,540 --> 01:01:21,070 We gooien bij katten, we uit een. 1303 01:01:21,070 --> 01:01:24,110 We zetten kat in een. 1304 01:01:24,110 --> 01:01:25,480 We zetten in spin. 1305 01:01:25,480 --> 01:01:26,710 We stappen uit twee. 1306 01:01:26,710 --> 01:01:30,200 We zetten spin in serie beugel twee. 1307 01:01:30,200 --> 01:01:32,300 Het zou zo mooi zijn als het werkte als dat. 1308 01:01:32,300 --> 01:01:35,570 Maar helaas, zoals we zullen zien, het is een beetje ingewikkelder. 1309 01:01:35,570 --> 01:01:37,570 >> Voordat we er, welke vragen over deze fundamentele 1310 01:01:37,570 --> 01:01:38,820 set-up van een hash table? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 Dit is een afbeelding precies wat we trokken op het bord. 1313 01:01:51,940 --> 01:01:55,420 Maar omdat we trokken het op het bord, ik ga niet verder in te gaan. 1314 01:01:55,420 --> 01:02:00,430 Wezen toetsen, de magische zwarte doos - of in dit geval, blauwgroen box - van een 1315 01:02:00,430 --> 01:02:02,410 hash-functie zet ze in emmers. 1316 01:02:02,410 --> 01:02:04,690 En in dit voorbeeld zijn we niet zetten de naam. 1317 01:02:04,690 --> 01:02:07,880 We zetten de bijbehorende telefoon nummer van de naam in de emmer. 1318 01:02:07,880 --> 01:02:10,430 Maar je kon heel goed alleen zet de naam in de emmer. 1319 01:02:10,430 --> 01:02:12,950 >> Dit is slechts een beeld van wat stelden we op het bord. 1320 01:02:12,950 --> 01:02:14,460 We hebben mogelijke valkuilen, dat wel. 1321 01:02:14,460 --> 01:02:17,470 Er zijn twee name dia's die ik wil gaan over. 1322 01:02:17,470 --> 01:02:20,230 De eerste is om een hash-functie. 1323 01:02:20,230 --> 01:02:22,620 Dus vroeg ik de vraag, wat maakt een goede hash-functie? 1324 01:02:22,620 --> 01:02:24,220 Ik geef twee antwoorden. 1325 01:02:24,220 --> 01:02:26,630 De eerste is dat het deterministisch. 1326 01:02:26,630 --> 01:02:29,660 In het kader van hashfuncties, wat betekent dit? 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 >> Publiek: Het kan u de index in constante tijd? 1330 01:02:42,850 --> 01:02:43,810 >> JASON HIRSCHHORN: Dat is niet wat het betekent. 1331 01:02:43,810 --> 01:02:44,725 Maar dat is een goede gok. 1332 01:02:44,725 --> 01:02:46,100 Iemand anders nog een gok wat dit inhoudt? 1333 01:02:46,100 --> 01:02:47,780 Dat een goede hash-functie deterministisch? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> PUBLIEK: Dat een toets slechts een kaart kan worden gebracht om een ​​plaats in de hash tabel. 1336 01:02:51,680 --> 01:02:53,070 >> JASON HIRSCHHORN: Dat is precies goed. 1337 01:02:53,070 --> 01:02:57,430 Elke keer als je in pompoen, het altijd nul terug. 1338 01:02:57,430 --> 01:03:01,660 Als je in pompoen en je hash functie geeft nul, maar heeft een 1339 01:03:01,660 --> 01:03:06,060 kans op terugkeer iets anders groter dan nul - 1340 01:03:06,060 --> 01:03:09,280 dus misschien kan het een soms terug of twee andere keren - 1341 01:03:09,280 --> 01:03:11,100 dat geen goede hashfunctie. 1342 01:03:11,100 --> 01:03:11,800 Je hebt helemaal gelijk. 1343 01:03:11,800 --> 01:03:15,680 Uw hash-functie moet de terugkeer van de exact dezelfde integer, in dit geval, voor 1344 01:03:15,680 --> 01:03:17,780 exact dezelfde string. 1345 01:03:17,780 --> 01:03:22,210 >> Misschien geeft het exact dezelfde integer voor exact dezelfde snaar 1346 01:03:22,210 --> 01:03:24,430 ongeacht de kapitalisatie. 1347 01:03:24,430 --> 01:03:27,980 Maar in dat geval is het nog steeds deterministische omdat meerdere dingen 1348 01:03:27,980 --> 01:03:29,350 worden afgebeeld op dezelfde waarde. 1349 01:03:29,350 --> 01:03:30,170 Dat is prima. 1350 01:03:30,170 --> 01:03:32,615 Zolang er slechts een output voor een bepaald ingangssignaal. 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 Het tweede ding is dat het retourneert geldig indices. 1354 01:03:38,340 --> 01:03:40,220 We opgevoed dat eerder. 1355 01:03:40,220 --> 01:03:41,860 Deze hash-functie - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 een hash-functie moet terug geldig indices. 1358 01:03:46,840 --> 01:03:47,740 Dat zeggen - 1359 01:03:47,740 --> 01:03:48,990 laten we terugkeren naar dit voorbeeld gaan. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 Mijn hash-functie telt de letters in het woord. 1362 01:03:57,540 --> 01:03:58,380 Dat is de hash-functie. 1363 01:03:58,380 --> 01:03:59,740 En geeft dat integer. 1364 01:03:59,740 --> 01:04:04,280 Dus als ik het woord A, het is gaat naar een terug te keren. 1365 01:04:04,280 --> 01:04:06,900 En het gaat om een ​​recht hier te zetten. 1366 01:04:06,900 --> 01:04:09,430 Wat als ik in het woord vleermuis? 1367 01:04:09,430 --> 01:04:11,310 Het gaat om drie terugkeren. 1368 01:04:11,310 --> 01:04:12,560 Waar komt knuppel heen? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> Het past niet. 1371 01:04:19,750 --> 01:04:21,000 Maar het moet ergens heen. 1372 01:04:21,000 --> 01:04:23,340 Dit is mijn hash table immers, en alles moet ergens heen. 1373 01:04:23,340 --> 01:04:24,590 Dus waar moet bat gaan? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Elke gedachten? 1376 01:04:28,710 --> 01:04:29,450 Gissingen? 1377 01:04:29,450 --> 01:04:30,280 Goede schattingen? 1378 01:04:30,280 --> 01:04:31,220 >> PUBLIEK: Zero. 1379 01:04:31,220 --> 01:04:32,120 >> JASON HIRSCHHORN: Waarom nul? 1380 01:04:32,120 --> 01:04:35,990 >> PUBLIEK: Omdat drie modulo drie nul is? 1381 01:04:35,990 --> 01:04:38,620 >> JASON HIRSCHHORN: Drie modulo drie nul is. 1382 01:04:38,620 --> 01:04:40,810 Dat is een grote gok, en dat klopt. 1383 01:04:40,810 --> 01:04:43,870 Dus in dit geval moet waarschijnlijk gaan op nul. 1384 01:04:43,870 --> 01:04:51,080 Dus een goede manier om ervoor te zorgen dat deze hash functie geeft alleen geldig indices wordt 1385 01:04:51,080 --> 01:04:54,580 het modulo door de grootte van de tabel. 1386 01:04:54,580 --> 01:04:57,360 Als je modulo wat dit rendement door drie, je bent altijd gaat krijgen 1387 01:04:57,360 --> 01:05:00,930 iets tussen nul, een en twee. 1388 01:05:00,930 --> 01:05:05,160 En als dit altijd terugkeert zeven, en je altijd modulo door drie, je bent 1389 01:05:05,160 --> 01:05:06,030 altijd naar hetzelfde te krijgen. 1390 01:05:06,030 --> 01:05:09,270 >> Dus het is nog steeds deterministische als je modulo. 1391 01:05:09,270 --> 01:05:11,420 Maar dat zal ervoor zorgen dat u nooit iets te krijgen - 1392 01:05:11,420 --> 01:05:12,940 een ongeldige industrie. 1393 01:05:12,940 --> 01:05:16,840 In het algemeen moet dat modulo gebeuren in je hash-functie. 1394 01:05:16,840 --> 01:05:18,240 Dus je hoeft geen zorgen te maken over dit. 1395 01:05:18,240 --> 01:05:20,555 Je kan het gewoon ervoor zorgen dat dit is een geldige indice. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Heeft u vragen over dit potentiële valkuil? 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 En daar gaan we. 1401 01:05:40,290 --> 01:05:42,890 Volgende potentiële valkuil, en dit is de grote. 1402 01:05:42,890 --> 01:05:46,880 Wat gebeurt er als twee sleutels kaart op dezelfde waarde? 1403 01:05:46,880 --> 01:05:49,350 Dus zijn er twee manieren om dit te behandelen. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 De eerste wordt lineair genoemd sonderen, dat ben ik 1406 01:05:56,020 --> 01:05:57,300 niet van plan om over te gaan. 1407 01:05:57,300 --> 01:06:01,120 Maar je moet bekend zijn met hoe dat werkt en wat dat is. 1408 01:06:01,120 --> 01:06:05,610 >> De tweede ga ik om over te gaan want dat is degene die vele 1409 01:06:05,610 --> 01:06:08,290 mensen zullen waarschijnlijk uiteindelijk beslissen om te gebruiken in hun probleem set. 1410 01:06:08,290 --> 01:06:09,820 Natuurlijk hoef je niet hoeft te doen. 1411 01:06:09,820 --> 01:06:15,280 Maar voor het probleem set, veel mensen de neiging om te kiezen voor een hash tabel te maken 1412 01:06:15,280 --> 01:06:17,950 met aparte chaining te implementeren hun woordenboek. 1413 01:06:17,950 --> 01:06:21,390 Dus we gaan te gaan over wat het betekent een hash tabel met 1414 01:06:21,390 --> 01:06:23,890 aparte chaining. 1415 01:06:23,890 --> 01:06:26,260 >> Dus ik zet in pompoen. 1416 01:06:26,260 --> 01:06:29,560 Het nul terug. 1417 01:06:29,560 --> 01:06:31,410 En ik zet hier pompoen. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Dan zet ik in - 1420 01:06:37,930 --> 01:06:39,922 Wat is een ander Halloween-thema-ding? 1421 01:06:39,922 --> 01:06:42,200 >> PUBLIEK: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON HIRSCHHORN: Candy! 1423 01:06:42,770 --> 01:06:43,910 Dat is een geweldig. 1424 01:06:43,910 --> 01:06:47,760 Ik heb in snoep en snoep geeft me ook nihil. 1425 01:06:47,760 --> 01:06:49,350 Wat moet ik doen? 1426 01:06:49,350 --> 01:06:51,940 Het even welke ideeën? 1427 01:06:51,940 --> 01:06:53,940 Omdat je alle soort van weten wat aparte chaining is. 1428 01:06:53,940 --> 01:06:55,190 Dus enig idee wat te doen? 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 >> PUBLIEK: Aanbrengen van de snaar eigenlijk in de hash tabel. 1432 01:07:03,810 --> 01:07:08,910 >> JASON HIRSCHHORN: Dus we gaan trekken het goede idee hier. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> PUBLIEK: Laat de hash [Onverstaanbaar] 1435 01:07:12,290 --> 01:07:16,640 de pointer die verwijst naar het begin van een lijst. 1436 01:07:16,640 --> 01:07:20,930 En dan hebben pompoen zijn de eerste waarde in dat gelinkte lijst en snoep zijn 1437 01:07:20,930 --> 01:07:22,800 de tweede waarde in dat gelinkte lijst. 1438 01:07:22,800 --> 01:07:23,420 >> JASON HIRSCHHORN: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, die was uitstekend. 1440 01:07:24,670 --> 01:07:26,160 Ik ga breken die naar beneden. 1441 01:07:26,160 --> 01:07:28,890 Marcus zegt niet overschrijven pompoen. 1442 01:07:28,890 --> 01:07:30,660 Dat zou slecht zijn. 1443 01:07:30,660 --> 01:07:33,640 Doe geen snoep ergens anders. 1444 01:07:33,640 --> 01:07:35,390 We gaan ze allebei op nul gezet. 1445 01:07:35,390 --> 01:07:37,770 Maar we gaan om te gaan met waardoor ze op nul door 1446 01:07:37,770 --> 01:07:39,395 creëren van een lijst op nul. 1447 01:07:39,395 --> 01:07:42,430 En we gaan een lijst maken alles wat toegewezen aan nul. 1448 01:07:42,430 --> 01:07:47,960 En de beste manier leerden we creëren een lijst die kan groeien en krimpen 1449 01:07:47,960 --> 01:07:49,840 dynamisch niet binnen andere array. 1450 01:07:49,840 --> 01:07:51,510 Dus geen multi-dimensionale array. 1451 01:07:51,510 --> 01:07:54,080 Maar om gewoon een gelinkte lijst. 1452 01:07:54,080 --> 01:07:55,330 >> Dus wat hij voorgesteld - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Ik ga een nieuwe krijgen - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 is het creëren van een array met pointers, een array van pointers. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Enig idee of hint wat het type van deze aanwijzingen moeten zijn? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> PUBLIEK: Pointers naar - 1461 01:08:27,250 --> 01:08:28,609 >> JASON HIRSCHHORN: Omdat je zei een gelinkte lijst, dus - 1462 01:08:28,609 --> 01:08:29,520 >> PUBLIEK: Node pointers? 1463 01:08:29,520 --> 01:08:30,670 >> JASON HIRSCHHORN: Node pointers. 1464 01:08:30,670 --> 01:08:32,830 Als de dingen in ons verbonden lijst zijn knooppunten dan ze 1465 01:08:32,830 --> 01:08:34,370 moet knooppunt pointers. 1466 01:08:34,370 --> 01:08:35,939 En wat doen ze in eerste instantie gelijk? 1467 01:08:35,939 --> 01:08:36,990 >> PUBLIEK: 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 Er is dus onze lege ding. 1471 01:08:46,080 --> 01:08:47,170 Pompoen rendement nul. 1472 01:08:47,170 --> 01:08:48,569 Wat doen wij? 1473 01:08:48,569 --> 01:08:49,609 Loop me er doorheen? 1474 01:08:49,609 --> 01:08:50,810 Eigenlijk, Marcus gaf me reeds. 1475 01:08:50,810 --> 01:08:52,439 Iemand anders lopen me er doorheen. 1476 01:08:52,439 --> 01:08:54,760 Wat we doen als we - 1477 01:08:54,760 --> 01:08:56,609 Dit lijkt sterk op wat we net deden. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> Publiek: Ik ga een gok te nemen. 1480 01:08:59,090 --> 01:09:01,250 Dus als je snoep. 1481 01:09:01,250 --> 01:09:01,640 >> JASON HIRSCHHORN: Yeah. 1482 01:09:01,640 --> 01:09:03,120 Wel, we hebben pompoen. 1483 01:09:03,120 --> 01:09:03,870 Laten we onze eerste. 1484 01:09:03,870 --> 01:09:04,324 We kregen pompoen. 1485 01:09:04,324 --> 01:09:04,779 >> Publiek: OK. 1486 01:09:04,779 --> 01:09:05,880 Pompoen rendement nul. 1487 01:09:05,880 --> 01:09:08,770 Zodat u deze in dat. 1488 01:09:08,770 --> 01:09:10,810 Of eigenlijk, je zet het in de gelinkte lijst. 1489 01:09:10,810 --> 01:09:13,550 >> JASON HIRSCHHORN: Hoe doen we zet het in de gelinkte lijst? 1490 01:09:13,550 --> 01:09:15,479 >> PUBLIEK: Oh, de werkelijke syntax? 1491 01:09:15,479 --> 01:09:16,240 >> JASON HIRSCHHORN: Gewoon lopen - 1492 01:09:16,240 --> 01:09:16,740 meer zeggen. 1493 01:09:16,740 --> 01:09:19,310 Wat doen wij? 1494 01:09:19,310 --> 01:09:22,100 >> PUBLIEK: U voegt gewoon als het eerste knooppunt. 1495 01:09:22,100 --> 01:09:22,675 >> JASON HIRSCHHORN: OK. 1496 01:09:22,675 --> 01:09:29,069 Dus hebben we onze knooppunt, pompoen. 1497 01:09:29,069 --> 01:09:31,560 En nu hoe plaats ik het? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> PUBLIEK: U wijst het naar de aanwijzer. 1500 01:09:37,090 --> 01:09:37,970 >> JASON HIRSCHHORN: Welke wijzer? 1501 01:09:37,970 --> 01:09:39,620 >> Publiek: De wijzer op nul. 1502 01:09:39,620 --> 01:09:41,420 >> JASON HIRSCHHORN: Dus waar doet dit punt? 1503 01:09:41,420 --> 01:09:42,810 >> PUBLIEK: Om nu meteen null. 1504 01:09:42,810 --> 01:09:43,529 >> JASON HIRSCHHORN: Nou, het wijzend op null. 1505 01:09:43,529 --> 01:09:44,499 Maar ik zet in pompoen. 1506 01:09:44,499 --> 01:09:46,053 Dus waar zou ze moeten aanduiden? 1507 01:09:46,053 --> 01:09:46,880 >> PUBLIEK: Om pompoen. 1508 01:09:46,880 --> 01:09:47,399 >> JASON HIRSCHHORN: Om pompoen. 1509 01:09:47,399 --> 01:09:48,760 Precies. 1510 01:09:48,760 --> 01:09:50,010 Dus dit wijst op pompoen. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 En waar komt deze pointer in pompoen punt? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 Aan 1515 01:09:58,340 --> 01:09:58,590 >> PUBLIEK: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON HIRSCHHORN: op null. 1517 01:09:59,210 --> 01:10:00,460 Precies. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Dus we gewoon iets ingebracht in de gelinkte lijst. 1520 01:10:05,140 --> 01:10:07,210 We schreven deze code om dit te doen. 1521 01:10:07,210 --> 01:10:09,520 Bijna kregen we het bijna volledig gekraakt. 1522 01:10:09,520 --> 01:10:10,790 Nu voegen we snoep. 1523 01:10:10,790 --> 01:10:13,480 Onze snoep gaat ook naar nul. 1524 01:10:13,480 --> 01:10:16,100 Dus wat doen we met snoep? 1525 01:10:16,100 --> 01:10:18,790 >> Publiek: Het hangt af van de vraag of niet we proberen te sorteren. 1526 01:10:18,790 --> 01:10:19,640 >> JASON HIRSCHHORN: Dat is precies goed. 1527 01:10:19,640 --> 01:10:21,070 Het hangt af van het al dan niet we proberen te sorteren. 1528 01:10:21,070 --> 01:10:22,660 Laten we aannemen dat we niet gaan om het te sorteren. 1529 01:10:22,660 --> 01:10:24,880 >> PUBLIEK: Nou dan, zoals we besproken voor, het eenvoudigste gewoon om het te zetten 1530 01:10:24,880 --> 01:10:28,590 meteen aan het begin zodat de wijzer van nul punten op snoep. 1531 01:10:28,590 --> 01:10:29,020 >> JASON HIRSCHHORN: OK. 1532 01:10:29,020 --> 01:10:29,380 Wacht even. 1533 01:10:29,380 --> 01:10:30,630 Laat me snoep maken hier. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Dus deze pointer - 1536 01:10:35,150 --> 01:10:37,590 >> PUBLIEK: Ja, moet nu worden gewezen op snoep. 1537 01:10:37,590 --> 01:10:40,580 Dan hebben de wijzer van candy wijs pompoen. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON HIRSCHHORN: Net als dat? 1540 01:10:44,560 --> 01:10:47,380 En zeggen dat we een andere kregen ding naar de kaart op nul? 1541 01:10:47,380 --> 01:10:48,660 >> PUBLIEK: Nou, je gewoon hetzelfde doen? 1542 01:10:48,660 --> 01:10:50,290 >> JASON HIRSCHHORN: Doe hetzelfde. 1543 01:10:50,290 --> 01:10:53,700 Dus in dit geval, als we niet willen houden loste het 1544 01:10:53,700 --> 01:10:55,270 klinkt nogal eenvoudig. 1545 01:10:55,270 --> 01:10:59,920 We nemen de aanwijzer in de indice gegeven door onze hash-functie. 1546 01:10:59,920 --> 01:11:03,830 We hebben dat punt aan onze nieuwe knooppunt. 1547 01:11:03,830 --> 01:11:07,830 En dan wat het aanwees eerder - 1548 01:11:07,830 --> 01:11:10,620 in dit geval nul, in het tweede geval pompoen - 1549 01:11:10,620 --> 01:11:15,310 dat, wat het ook wijst naar eerder, voegen we in het volgende van 1550 01:11:15,310 --> 01:11:17,810 onze nieuwe knooppunt. 1551 01:11:17,810 --> 01:11:19,650 We zijn het invoegen iets in het begin. 1552 01:11:19,650 --> 01:11:22,900 In feite is dit een stuk eenvoudiger dan proberen om de gesorteerde lijst te houden. 1553 01:11:22,900 --> 01:11:25,340 Maar nogmaals, het zoeken zal zijn meer hier ingewikkeld over. 1554 01:11:25,340 --> 01:11:28,300 We zullen altijd moeten gaan tot het einde. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Heeft u vragen over aparte chaining? 1557 01:11:32,750 --> 01:11:34,690 Hoe dat werkt? 1558 01:11:34,690 --> 01:11:35,820 Vraag ze nu. 1559 01:11:35,820 --> 01:11:39,260 Ik wil heel graag dat je alles maken begrijpen voordat we het hoofd uit. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> PUBLIEK: Waarom zet je pompoen en snoep in dezelfde 1562 01:11:52,060 --> 01:11:54,108 deel van de hash table? 1563 01:11:54,108 --> 01:11:55,860 >> JASON HIRSCHHORN: Goede vraag. 1564 01:11:55,860 --> 01:11:59,140 Waarom hebben we ze in dezelfde deel van de hash table? 1565 01:11:59,140 --> 01:12:03,200 Nou, in dit geval onze hash-functie rendement nul voor hen beiden. 1566 01:12:03,200 --> 01:12:05,310 Dus moeten ze gaan op indice nul want dat is waar we gaan 1567 01:12:05,310 --> 01:12:07,420 kijk voor hen als we ooit willen ze opzoeken. 1568 01:12:07,420 --> 01:12:11,750 Opnieuw met een lineaire indringende benadering we zouden hen niet er zowel op nul. 1569 01:12:11,750 --> 01:12:13,900 Maar in de aparte ketenbenadering, we gaan ze allebei op nul zetten 1570 01:12:13,900 --> 01:12:16,620 en maak vervolgens een lijst af van nul. 1571 01:12:16,620 --> 01:12:20,140 >> En we willen niet pompoen overschrijven gewoon voor dat want dan gaan we 1572 01:12:20,140 --> 01:12:21,860 veronderstellen dat pompoen was nooit geplaatst. 1573 01:12:21,860 --> 01:12:25,230 Als we gewoon blijven een ding in de locatie die slecht zou zijn. 1574 01:12:25,230 --> 01:12:28,590 Dan zou er geen kans van ons ooit - 1575 01:12:28,590 --> 01:12:31,660 als we ooit een duplicaat gehad, toen we zou gewoon wissen onze initiële waarde. 1576 01:12:31,660 --> 01:12:34,090 Dus dat is de reden waarom we doen deze aanpak. 1577 01:12:34,090 --> 01:12:36,580 Of dat is waarom we kozen - maar nogmaals, we koos voor de aparte chaining aanpak, 1578 01:12:36,580 --> 01:12:39,670 waarvan er vele andere benaderingen men kon kiezen. 1579 01:12:39,670 --> 01:12:41,185 Is dat een antwoord op je vraag? 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 Lineaire indringende zou inhouden - 1584 01:12:47,720 --> 01:12:51,913 als we vonden een botsing op nul, we zou er in de volgende plek om te zien of 1585 01:12:51,913 --> 01:12:54,310 het was open en zet het daar. 1586 01:12:54,310 --> 01:12:57,320 En dan kijken we in de volgende sport en zien of dat was open en zet het daar. 1587 01:12:57,320 --> 01:12:59,780 Dus vinden we de volgende beschikbare open plek en zet het daar. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Andere vragen? 1590 01:13:03,890 --> 01:13:05,370 Ja, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> PUBLIEK: Als vervolg op dat, wat bedoel je met volgende plek? 1592 01:13:07,490 --> 01:13:10,250 In de hash tabel of in een gekoppelde lijst. 1593 01:13:10,250 --> 01:13:12,100 >> JASON HIRSCHHORN: Voor lineaire programmering, geen gelinkte lijsten. 1594 01:13:12,100 --> 01:13:13,400 De volgende plek op de hash table. 1595 01:13:13,400 --> 01:13:13,820 >> Publiek: OK. 1596 01:13:13,820 --> 01:13:17,570 Dus de hash table zou zijn geïnitialiseerd om de grootte - 1597 01:13:17,570 --> 01:13:19,560 zoals het aantal snaren dat je het invoegen? 1598 01:13:19,560 --> 01:13:22,170 >> JASON HIRSCHHORN: U zou wil dat het echt groot zijn. 1599 01:13:22,170 --> 01:13:23,910 Ja. 1600 01:13:23,910 --> 01:13:27,900 Hier is een foto van wat we net trok op het bord. 1601 01:13:27,900 --> 01:13:29,470 Nogmaals, we hebben een botsing hier. 1602 01:13:29,470 --> 01:13:30,710 bij 152. 1603 01:13:30,710 --> 01:13:33,570 En je zult zien hebben we een gelinkte lijst van af. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Nogmaals, de hash table aparte chaining aanpak is niet degene die je 1606 01:13:41,850 --> 01:13:45,590 moeten nemen voor problemen stellen zes maar een die veel 1607 01:13:45,590 --> 01:13:47,100 studenten hebben de neiging zich te nemen. 1608 01:13:47,100 --> 01:13:51,140 Dus op deze nota, laten we even praten voordat we uit over probleem zes, 1609 01:13:51,140 --> 01:13:52,160 en dan zal ik een verhaal met u delen. 1610 01:13:52,160 --> 01:13:55,120 We hebben drie minuten. 1611 01:13:55,120 --> 01:13:55,750 >> Probleem ingesteld zes. 1612 01:13:55,750 --> 01:13:57,790 Je hebt vier functies - 1613 01:13:57,790 --> 01:14:02,430 belasting, controleren, grootte en lossen. 1614 01:14:02,430 --> 01:14:03,380 Belasting - 1615 01:14:03,380 --> 01:14:07,120 goed, we zijn gaan over belasting zojuist. 1616 01:14:07,120 --> 01:14:09,330 We trokken belasting op het bord. 1617 01:14:09,330 --> 01:14:13,230 En we zelfs begonnen met het coderen van een veel ingevoegd in een gelinkte lijst. 1618 01:14:13,230 --> 01:14:18,020 Dus belasting niet meer dan wat we net gedaan. 1619 01:14:18,020 --> 01:14:21,070 >> Check is als je eenmaal hebt iets geladen. 1620 01:14:21,070 --> 01:14:22,580 Het is hetzelfde proces als dit. 1621 01:14:22,580 --> 01:14:26,845 Dezelfde eerste twee delen waar je gooit iets in de hash-functie 1622 01:14:26,845 --> 01:14:29,190 en krijg de waarde ervan. 1623 01:14:29,190 --> 01:14:30,700 Maar nu zijn we niet te laden. 1624 01:14:30,700 --> 01:14:33,350 Nu zijn we op zoek naar het. 1625 01:14:33,350 --> 01:14:37,130 Ik heb voorbeeldcode geschreven voor het vinden van iets in een gelinkte lijst. 1626 01:14:37,130 --> 01:14:38,250 Ik moedig u aan om te oefenen dat. 1627 01:14:38,250 --> 01:14:43,000 Maar intuïtief vinden van iets wordt redelijk vergelijkbaar met het invoegen van iets. 1628 01:14:43,000 --> 01:14:46,540 Inderdaad, trok we een beeld van het vinden iets in een gelinkte lijst, bewegen 1629 01:14:46,540 --> 01:14:48,910 door tot dat je aan het einde. 1630 01:14:48,910 --> 01:14:52,430 En als je echt naar het einde en kon niet vinden, dan is het er niet. 1631 01:14:52,430 --> 01:14:55,400 Dus dat is controle, in wezen. 1632 01:14:55,400 --> 01:14:57,030 >> Vervolgens is de grootte. 1633 01:14:57,030 --> 01:14:57,910 Laten we overslaan grootte. 1634 01:14:57,910 --> 01:15:00,040 Tenslotte moet je uitladen. 1635 01:15:00,040 --> 01:15:02,890 Unload is degene die we hebben niet getekend op het bord of nog gecodeerd. 1636 01:15:02,890 --> 01:15:05,990 Maar ik moedig u aan om te proberen het coderen in onze steekproef gelinkte lijst voorbeeld. 1637 01:15:05,990 --> 01:15:11,440 Maar lossen intuïtief lijkt vrij - 1638 01:15:11,440 --> 01:15:14,010 of ik bedoel is vergelijkbaar met controleren. 1639 01:15:14,010 --> 01:15:17,350 Behalve voor nu elke keer dat je gaat door, je bent niet alleen controleren om 1640 01:15:17,350 --> 01:15:19,090 zien of u er uw waarde. 1641 01:15:19,090 --> 01:15:22,490 Maar je neemt dat knooppunt en vrijmaken van het wezen. 1642 01:15:22,490 --> 01:15:23,610 Dat is wat lossen vraagt ​​je te doen. 1643 01:15:23,610 --> 01:15:24,670 Gratis alles wat je hebt malloced. 1644 01:15:24,670 --> 01:15:27,480 Dus je gaat door de hele lijst weer, gaan door de hele hash 1645 01:15:27,480 --> 01:15:27,760 opnieuw tafel. 1646 01:15:27,760 --> 01:15:29,240 Deze keer niet controleren om te zien wat er staat. 1647 01:15:29,240 --> 01:15:31,080 Gewoon gratis wat er staat. 1648 01:15:31,080 --> 01:15:33,260 >> En tenslotte grootte. 1649 01:15:33,260 --> 01:15:34,350 Maat zal worden uitgevoerd. 1650 01:15:34,350 --> 01:15:35,590 Als je niet implementeren grootte - 1651 01:15:35,590 --> 01:15:36,250 Ik zeg het als dit. 1652 01:15:36,250 --> 01:15:39,740 Als je niet implementeren grootte in precies een regel code, waaronder de 1653 01:15:39,740 --> 01:15:43,760 terug statement, je bent verkeerd doet grootte. 1654 01:15:43,760 --> 01:15:47,170 Dus zorg ervoor dat de grootte, voor volledige ontwerp punten, je doet het in precies een 1655 01:15:47,170 --> 01:15:49,970 regel code, met inbegrip de return statement. 1656 01:15:49,970 --> 01:15:52,450 >> En nog niet inpakken, 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 Ik wilde zeggen dank je wel jongens voor zijn komst naar sectie. 1660 01:16:01,300 --> 01:16:02,550 Hebben een Happy Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Dit is mijn kostuum. 1663 01:16:05,960 --> 01:16:08,850 Ik zal het dragen van dit op donderdag als ik zie je op kantooruren. 1664 01:16:08,850 --> 01:16:14,640 En als je nieuwsgierig bent wat meer bent achtergrond als om dit kostuum, voel 1665 01:16:14,640 --> 01:16:19,135 vrij om te controleren 2011 deel voor een verhaal over waarom ik ben 1666 01:16:19,135 --> 01:16:20,900 het dragen van de pompoen kostuum. 1667 01:16:20,900 --> 01:16:23,680 En het is een triest verhaal. 1668 01:16:23,680 --> 01:16:27,050 Dus zorg ervoor dat je sommige weefsels in de buurt. 1669 01:16:27,050 --> 01:16:28,680 Maar op dat, als u een vragen die ik zal blijven hangen 1670 01:16:28,680 --> 01:16:29,960 buiten na sectie. 1671 01:16:29,960 --> 01:16:31,510 Veel succes op probleem ingesteld zes. 1672 01:16:31,510 --> 01:16:33,540 En zoals altijd, als u een vragen, laat het me weten. 1673 01:16:33,540 --> 01:16:35,584