1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON Hirsch: Welkom almal na die artikel sewe. 3 00:00:12,680 --> 00:00:15,040 Ons is in week sewe van die kursus. 4 00:00:15,040 --> 00:00:18,440 En hierdie komende Donderdag is Halloween so ek 5 00:00:18,440 --> 00:00:21,420 geklee soos 'n pampoen. 6 00:00:21,420 --> 00:00:23,460 Ek kon nie buig oor en sit op my skoene, so dit is waarom ek 7 00:00:23,460 --> 00:00:25,660 net dra sokkies. 8 00:00:25,660 --> 00:00:29,220 Ek is ook nie die dra van enige iets onder hierdie, so ek kan dit nie af as dit 9 00:00:29,220 --> 00:00:29,950 afleidende na jou toe. 10 00:00:29,950 --> 00:00:31,860 Ek vra om verskoning by voorbaat vir wat. 11 00:00:31,860 --> 00:00:33,170 Jy hoef nie te dink wat gaan aan. 12 00:00:33,170 --> 00:00:34,240 Ek dra boksers. 13 00:00:34,240 --> 00:00:36,170 So dit is alles goed. 14 00:00:36,170 --> 00:00:41,120 >> Ek het 'n langer storie oor hoekom ek geklee as 'n pampoen, maar ek gaan 15 00:00:41,120 --> 00:00:45,110 behalwe dat vir later in hierdie afdeling omdat ek nie wil hê om te begin. 16 00:00:45,110 --> 00:00:47,720 Ons het 'n baie opwindende dinge om te gaan oor hierdie week. 17 00:00:47,720 --> 00:00:51,810 Die meeste van hulle hou regstreeks verband met hierdie week se probleem stel, spelfoute. 18 00:00:51,810 --> 00:00:54,680 Ons gaan te wees gaan oor gekoppel lyste en hash tabelle 19 00:00:54,680 --> 00:00:57,160 vir die hele afdeling. 20 00:00:57,160 --> 00:01:02,490 Ek het hierdie lys word elke week, 'n lys van hulpbronne vir jou om jou te help met 21 00:01:02,490 --> 00:01:04,120 Die materiaal op hierdie kursus. 22 00:01:04,120 --> 00:01:07,600 As teen 'n verlies of soek vir 'n paar meer inligting, kyk uit een van 23 00:01:07,600 --> 00:01:09,930 hierdie hulpbronne. 24 00:01:09,930 --> 00:01:14,530 >> Weereens, pset6 is spelfoute, hierdie week se pset. 25 00:01:14,530 --> 00:01:17,690 En dit moedig jou ook, en ek jou aan te moedig, 'n ander te gebruik 26 00:01:17,690 --> 00:01:20,320 hulpbronne spesifiek vir hierdie pset. 27 00:01:20,320 --> 00:01:23,390 In die besonder, die drie Ek het gelys op die skerm - 28 00:01:23,390 --> 00:01:27,160 gdb, wat ons het is vertroud met en is gebruik vir 'n rukkie nou, is 29 00:01:27,160 --> 00:01:29,270 gaan baie nuttig wees om hierdie week. 30 00:01:29,270 --> 00:01:30,190 So ek sit dit hier. 31 00:01:30,190 --> 00:01:32,910 Maar wanneer jy werk met C, jy moet altyd gebruik word gdb te 32 00:01:32,910 --> 00:01:34,430 ontfout jou programme. 33 00:01:34,430 --> 00:01:36,660 Hierdie week het ook valgrind. 34 00:01:36,660 --> 00:01:38,535 Het enige iemand weet wat valgrind doen? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> Publiek: Dit gaan vir die geheue lekkasies? 37 00:01:43,890 --> 00:01:45,950 >> JASON Hirsch: Valgrind tjeks vir die geheue lekkasies. 38 00:01:45,950 --> 00:01:49,970 So as jy malloc iets in jou program, jy vra vir die geheue. 39 00:01:49,970 --> 00:01:52,920 Aan die einde van die program, moet jy vry om te skryf oor alles wat jy het 40 00:01:52,920 --> 00:01:54,800 malloced die geheue terug te gee. 41 00:01:54,800 --> 00:01:58,420 As jy nie vrye skryf nie aan die einde en jou program kom tot 'n gevolgtrekking, 42 00:01:58,420 --> 00:02:00,000 Alles sal outomaties bevry word. 43 00:02:00,000 --> 00:02:02,340 En vir klein programme, is dit nie so 'n groot deal. 44 00:02:02,340 --> 00:02:05,250 Maar as jy 'n langer loop skryf program wat nie ophou, 45 00:02:05,250 --> 00:02:09,180 noodwendig nie, in 'n paar minute of 'n paar sekondes, dan die geheue lekkasies 46 00:02:09,180 --> 00:02:10,710 kan 'n groot deal word. 47 00:02:10,710 --> 00:02:14,940 >> So vir pset6, is die verwagting dat jy sal hê nul geheue lekkasies met 48 00:02:14,940 --> 00:02:15,910 jou program. 49 00:02:15,910 --> 00:02:18,690 Om seker te maak vir die geheue lekkasies, hardloop valgrind en dit sal vir jou 'n paar mooi 50 00:02:18,690 --> 00:02:21,190 uitset om jou te laat weet of of nie alles gratis. 51 00:02:21,190 --> 00:02:23,940 Ons sal later oefen met dit Vandag, hopelik. 52 00:02:23,940 --> 00:02:25,790 >> Ten slotte, die verskil opdrag. 53 00:02:25,790 --> 00:02:28,900 Jy gebruik word om iets soortgelyk aan dit in pset5 met die blik instrument. 54 00:02:28,900 --> 00:02:30,780 Toegelaat om jou te binne te kyk. 55 00:02:30,780 --> 00:02:33,400 Jy kan ook gebruik word verskil ook per die probleem gestel spec. 56 00:02:33,400 --> 00:02:35,950 Maar in jou toegelaat het om te vergelyk twee lêers. 57 00:02:35,950 --> 00:02:39,180 Jy kan die bitmap lêer en te vergelyk info kop van 'n personeellid oplossing en 58 00:02:39,180 --> 00:02:42,200 jou oplossing in pset5 indien jy gekies het om dit te gebruik. 59 00:02:42,200 --> 00:02:44,030 Verskil sal toelaat om te doen, as well. 60 00:02:44,030 --> 00:02:48,620 Jy kan die korrekte antwoord vergelyk hierdie week se probleem stel om jou antwoord 61 00:02:48,620 --> 00:02:52,210 en kyk of dit in lyn is of sien waar die foute is. 62 00:02:52,210 --> 00:02:55,870 >> So dit is drie goeie gereedskap wat wat jy moet gebruik vir hierdie week, en 63 00:02:55,870 --> 00:02:58,130 beslis check jou program met hierdie drie gereedskap 64 00:02:58,130 --> 00:03:00,520 voordat hy dit in 65 00:03:00,520 --> 00:03:04,650 Weereens, as ek elke week genoem het, Indien u enige terugvoer vir my - beide 66 00:03:04,650 --> 00:03:06,470 positiewe en opbouende - 67 00:03:06,470 --> 00:03:09,930 voel vry om aan die hoof van die webwerf aan die onderkant van hierdie skyfie 68 00:03:09,930 --> 00:03:11,270 en insette dit daar. 69 00:03:11,270 --> 00:03:13,440 Ek het regtig nie waardeer en al die terugvoer. 70 00:03:13,440 --> 00:03:17,360 En as jy my spesifieke dinge wat Ek kan doen om te verbeter of dat ek 71 00:03:17,360 --> 00:03:21,350 om goed te doen wat jy vir my wil voort te gaan, ek neem aan dat dit die hart en 72 00:03:21,350 --> 00:03:24,040 probeer regtig hard om te luister om jou terugvoer. 73 00:03:24,040 --> 00:03:27,720 Ek kan nie belowe ek gaan doen alles, al is, soos die dra van 'n 74 00:03:27,720 --> 00:03:30,700 pampoen kostuum elke week. 75 00:03:30,700 --> 00:03:34,020 >> So gaan ons die grootste deel van die te spandeer artikel, soos ek genoem het, praat oor 76 00:03:34,020 --> 00:03:37,240 geskakelde lyste en hash tabelle, wat sal direk van toepassing is op die wees 77 00:03:37,240 --> 00:03:38,780 probleem stel hierdie week. 78 00:03:38,780 --> 00:03:42,580 Geskakelde lyste sal ons gaan oor relatief vinnig, want ons het 'n eerlike bietjie bestee 79 00:03:42,580 --> 00:03:44,930 van die tyd gaan oor dit in artikel. 80 00:03:44,930 --> 00:03:48,680 En so sal ons kry reguit in die kodering probleme gekoppel lyste. 81 00:03:48,680 --> 00:03:52,740 En dan aan die einde sal ons praat oor hash tabelle en hoe dit van toepassing is op hierdie 82 00:03:52,740 --> 00:03:55,280 week se probleem stel. 83 00:03:55,280 --> 00:03:57,560 >> Jy het hierdie kode gesien het nie. 84 00:03:57,560 --> 00:04:02,730 Dit is 'n struct, en dit is die definisie iets nuuts genoem 'n knoop. 85 00:04:02,730 --> 00:04:10,660 En binne-in 'n knoop is daar 'n heelgetal hier en daar is 'n verwysing na 86 00:04:10,660 --> 00:04:11,830 ander rekenaars. 87 00:04:11,830 --> 00:04:12,790 Ons het dit gesien voor. 88 00:04:12,790 --> 00:04:14,830 Dit is te kom vir 'n paar weke nou. 89 00:04:14,830 --> 00:04:18,680 Dit kombineer wysers, wat ons al werk met, en structs, wat toelaat 90 00:04:18,680 --> 00:04:22,079 ons twee verskillende te kombineer dinge in een data tipe. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Daar is 'n baie gaan op die skerm. 93 00:04:26,490 --> 00:04:30,220 Maar dit alles moet relatief wees vertroud is met jou. 94 00:04:30,220 --> 00:04:33,810 Op die eerste lyn, ons verklaar 'n nuwe knoop. 95 00:04:33,810 --> 00:04:41,650 En dan binne daardie nuwe knoop, ek Die heelgetal in die knoop teen een. 96 00:04:41,650 --> 00:04:44,950 Ons sien op die volgende reël ek doen 'n printf opdrag, maar ek het vergrys 97 00:04:44,950 --> 00:04:48,080 die printf bevel omdat die werklik belangrike deel is hierdie lyn hier - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Wat beteken die dot beteken? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> Publiek: Gaan na die knoop en bepaal die waarde vir n dit. 102 00:04:57,240 --> 00:04:58,370 >> JASON Hirsch: Dis presies reg. 103 00:04:58,370 --> 00:05:03,300 Dot beteken toegang tot die n deel van hierdie nuwe knoop. 104 00:05:03,300 --> 00:05:05,690 Hierdie volgende lyn doen 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: Dit skep 'n ander node wat verwys na die nuwe knoop. 108 00:05:21,910 --> 00:05:24,870 >> JASON Hirsch: So is dit nie Skep 'n nuwe node. 109 00:05:24,870 --> 00:05:26,120 Dit skep 'n wat? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> Publiek: 'n wyser. 112 00:05:29,300 --> 00:05:33,460 >> JASON Hirsch: 'n verwysing na 'n knoop, soos aangedui deur die knoop * hier. 113 00:05:33,460 --> 00:05:34,800 So skep dit 'n verwysing na 'n knoop. 114 00:05:34,800 --> 00:05:37,490 En wat knoop is dit wys te, Michael? 115 00:05:37,490 --> 00:05:38,440 >> Publiek: New knoop? 116 00:05:38,440 --> 00:05:39,240 >> JASON Hirsch: New knoop. 117 00:05:39,240 --> 00:05:43,020 En dit is daar wys, want ons het gee dit die adres van die nuwe knoop. 118 00:05:43,020 --> 00:05:45,820 En nou in hierdie lyn wat ons sien twee verskillende maniere 119 00:05:45,820 --> 00:05:46,910 uitdrukking van die dieselfde ding. 120 00:05:46,910 --> 00:05:49,650 En ek wou om uit te wys hoe hierdie twee dinge is dieselfde. 121 00:05:49,650 --> 00:05:54,740 In die eerste lyn, ons dereference die wyser. 122 00:05:54,740 --> 00:05:55,830 So gaan ons na die knoop. 123 00:05:55,830 --> 00:05:56,830 Dit is wat hierdie ster beteken. 124 00:05:56,830 --> 00:05:57,930 Ons het gesien dat voor met wysers. 125 00:05:57,930 --> 00:05:59,280 Gaan na daardie knoop. 126 00:05:59,280 --> 00:06:00,370 Dit is in hakies. 127 00:06:00,370 --> 00:06:04,610 En dan toegang via die dot operateur die n element van die knoop. 128 00:06:04,610 --> 00:06:08,430 >> So dit is die neem van die sintaksis sien ons hier en nou 129 00:06:08,430 --> 00:06:09,670 gebruik dit met 'n muis. 130 00:06:09,670 --> 00:06:13,730 Natuurlik, dit kry soort van besig as jy skryf die hakies - 131 00:06:13,730 --> 00:06:14,940 dat die ster en dat dot. 132 00:06:14,940 --> 00:06:16,220 Dit raak 'n bietjie besig. 133 00:06:16,220 --> 00:06:18,500 So ons het 'n paar sintaktiese suiker. 134 00:06:18,500 --> 00:06:19,920 En hierdie lyn 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 Dit beteken presies dieselfde ding. 138 00:06:28,000 --> 00:06:30,840 So hierdie twee reëls van die kode is ekwivalent en sal doen 139 00:06:30,840 --> 00:06:31,650 presies dieselfde ding. 140 00:06:31,650 --> 00:06:34,210 >> Maar ek wou diegene uit te wys voordat ons verder gaan, sodat jy verstaan 141 00:06:34,210 --> 00:06:39,000 wat regtig die ding hier is net sintaktiese suiker vir ontwysing 142 00:06:39,000 --> 00:06:44,200 die wyser en dan gaan die n deel van daardie struct. 143 00:06:44,200 --> 00:06:45,525 Enige vrae oor hierdie skuif? 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 >> So ons gaan om te gaan deur 'n paar van bedrywighede wat jy op kan doen 147 00:06:58,510 --> 00:06:59,730 geskakelde lyste. 148 00:06:59,730 --> 00:07:05,770 'N geskakelde lys, onthou, is 'n reeks nodes wat na mekaar. 149 00:07:05,770 --> 00:07:12,470 En ons in die algemeen begin met 'n verwysing genoem hoof, oor die algemeen, wat verwys na 150 00:07:12,470 --> 00:07:14,040 Die eerste ding wat in die lys. 151 00:07:14,040 --> 00:07:18,900 So op die eerste lyn hier, ons het ons oorspronklike L eerste. 152 00:07:18,900 --> 00:07:21,370 So die ding wat jy kan dink - dit teks hier wat jy kan dink as 153 00:07:21,370 --> 00:07:23,560 net die wyser het ons gestoor êrens dat punte 154 00:07:23,560 --> 00:07:24,670 na die eerste element. 155 00:07:24,670 --> 00:07:27,500 En in hierdie verband lys Ons het vier knope. 156 00:07:27,500 --> 00:07:29,530 Elke node is 'n groot boks. 157 00:07:29,530 --> 00:07:33,430 Die groter boks binne-in die groot box is die heeltallige deel. 158 00:07:33,430 --> 00:07:37,400 En dan het ons 'n wyser deel. 159 00:07:37,400 --> 00:07:39,630 >> Hierdie bokse is nie gevestig op skaal, want hoe groot is 160 00:07:39,630 --> 00:07:42,320 'n heelgetal in grepe? 161 00:07:42,320 --> 00:07:43,290 Hoe nou groot? 162 00:07:43,290 --> 00:07:43,710 Vier. 163 00:07:43,710 --> 00:07:45,470 En hoe groot is 'n muis? 164 00:07:45,470 --> 00:07:45,940 Vier. 165 00:07:45,940 --> 00:07:48,180 So regtig, as ons te trek hierdie bokse beide op die skaal 166 00:07:48,180 --> 00:07:49,690 sou dieselfde grootte wees. 167 00:07:49,690 --> 00:07:52,870 In hierdie geval, ons wil voeg iets in die lys. 168 00:07:52,870 --> 00:07:57,190 Sodat jy kan sien hier is ons inbring Vyf Ons deurkruis deur die 169 00:07:57,190 --> 00:08:01,310 gekoppel lys vind waar vyf gaan, en dan plaas dit. 170 00:08:01,310 --> 00:08:03,560 >> Kom ons breek dat af en gaan 'n bietjie stadiger. 171 00:08:03,560 --> 00:08:05,510 Ek gaan om te wys op die bord. 172 00:08:05,510 --> 00:08:09,930 So het ons ons node vyf wat ons geskep het in mallocs. 173 00:08:09,930 --> 00:08:11,190 Hoekom is almal lag? 174 00:08:11,190 --> 00:08:12,130 Net 'n grap. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Dus het ons malloced vyf. 177 00:08:14,820 --> 00:08:16,310 Ons het hierdie knoop iewers anders. 178 00:08:16,310 --> 00:08:17,740 Ons is gereed om te gaan. 179 00:08:17,740 --> 00:08:20,130 Ons begin by die voorkant van ons lys met twee. 180 00:08:20,130 --> 00:08:22,380 En ons wil in te voeg in 'n gesorteerde mode. 181 00:08:22,380 --> 00:08:27,550 >> So as ons sien twee en ons wil om te sit vyf, wat doen ons wanneer ons sien 182 00:08:27,550 --> 00:08:28,800 iets minder as ons? 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 Ons wil in te voeg vyf in hierdie gekoppel lys, hou dit gesorteer. 186 00:08:36,750 --> 00:08:37,520 Ons sien nommer twee. 187 00:08:37,520 --> 00:08:38,769 So, wat doen ons? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> Publiek: Bel die wyser na die volgende knoop. 190 00:08:40,679 --> 00:08:42,530 >> JASON Hirsch: En hoekom doen ons gaan na die volgende een? 191 00:08:42,530 --> 00:08:45,970 >> Publiek: Want dit is die volgende nodus in die lys. 192 00:08:45,970 --> 00:08:48,310 En ons weet net dat ander plek. 193 00:08:48,310 --> 00:08:50,410 >> JASON Hirsch: En vyf groter as twee, in die besonder. 194 00:08:50,410 --> 00:08:51,600 Omdat ons wil dit gesorteer te hou. 195 00:08:51,600 --> 00:08:52,730 So vyf is groter as twee. 196 00:08:52,730 --> 00:08:54,460 So het ons beweeg na die volgende een. 197 00:08:54,460 --> 00:08:55,240 En nou kom ons vier. 198 00:08:55,240 --> 00:08:56,490 En wat gebeur wanneer ons vier bereik? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Vyf is groter as vier. 201 00:09:00,310 --> 00:09:01,460 So ons gaan hou. 202 00:09:01,460 --> 00:09:03,110 En nou is ons op ses. 203 00:09:03,110 --> 00:09:04,360 En wat sien ons op ses? 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: Ses is groter as vyf. 207 00:09:10,544 --> 00:09:11,480 >> JASON Hirsch: Ses is groter as vyf. 208 00:09:11,480 --> 00:09:13,660 So dit is waar ons wil te voeg vyf. 209 00:09:13,660 --> 00:09:17,320 Hou egter in gedagte dat indien ons het net een wyser hier - 210 00:09:17,320 --> 00:09:19,840 dit is ons ekstra wyser wat dwars deur die lys. 211 00:09:19,840 --> 00:09:21,860 En ons wys na ses. 212 00:09:21,860 --> 00:09:25,010 Ons het spoor verloor van wat kom voor ses. 213 00:09:25,010 --> 00:09:29,130 So as ons iets wil voeg in hierdie lys om dit gesorteer ons 214 00:09:29,130 --> 00:09:31,630 waarskynlik hoeveel riglyne? 215 00:09:31,630 --> 00:09:32,280 >> Publiek: Twee. 216 00:09:32,280 --> 00:09:32,920 >> JASON HIRSCHORN: Twee. 217 00:09:32,920 --> 00:09:35,720 Een baan van die huidige te hou een en tred te hou met 218 00:09:35,720 --> 00:09:37,050 die vorige een. 219 00:09:37,050 --> 00:09:38,450 Dit is net 'n enkel gekoppel lys. 220 00:09:38,450 --> 00:09:39,670 Dit gaan net een rigting. 221 00:09:39,670 --> 00:09:43,220 As ons 'n dubbel gekoppel lys, waar alles wys na die ding 222 00:09:43,220 --> 00:09:46,240 nadat dit en die ding voordat dit dan sou ons nie nodig het om dit te doen. 223 00:09:46,240 --> 00:09:49,350 Maar in hierdie geval het ons nie wil verloor spoor van wat voor ons gekom het in die geval 224 00:09:49,350 --> 00:09:53,350 Ons moet vyf iewers te voeg in die middel. 225 00:09:53,350 --> 00:09:55,610 Sê ons is die inbring van nege. 226 00:09:55,610 --> 00:09:57,260 Wat sou gebeur wanneer ons het tot agt? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> Publiek: Jy wil hê om te kry dat die nul punt. 229 00:10:04,880 --> 00:10:07,820 In plaas van om nul punt wat jy wil hê 'n element te voeg en dan 230 00:10:07,820 --> 00:10:09,216 dit verwys na nege. 231 00:10:09,216 --> 00:10:09,700 >> JASON HIRSCHORN: Presies. 232 00:10:09,700 --> 00:10:10,600 So kry ons agt. 233 00:10:10,600 --> 00:10:13,140 Ons bereik die einde van die lys, want dit is wys om null. 234 00:10:13,140 --> 00:10:16,330 En nou, in plaas van om dit te wys null ons het dit verwys na ons nuwe knoop. 235 00:10:16,330 --> 00:10:19,870 En ons het die wyser in ons nuwe node te null. 236 00:10:19,870 --> 00:10:21,445 Het enige iemand enige vrae oor die inbring? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Wat as ek nie omgee vir hou die lys gesorteer? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> Publiek: Hou dit by die begin of die einde. 241 00:10:34,350 --> 00:10:35,510 >> JASON HIRSCHORN: Plak dit op die begin of die einde. 242 00:10:35,510 --> 00:10:37,276 Watter een moet ons doen? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Hoekom die einde? 245 00:10:41,020 --> 00:10:43,250 >> Publiek: Omdat die begin is reeds gevul. 246 00:10:43,250 --> 00:10:43,575 >> JASON HIRSCHORN: OK. 247 00:10:43,575 --> 00:10:44,360 Die begin is reeds gevul. 248 00:10:44,360 --> 00:10:46,090 Wie wil om te argumenteer teen Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> Publiek: Wel, jy waarskynlik wil hou dit aan die begin, want 251 00:10:48,910 --> 00:10:50,140 anders as jy sit dit op die einde wat jy wil hê om te 252 00:10:50,140 --> 00:10:51,835 deurkruis die hele lys. 253 00:10:51,835 --> 00:10:52,990 >> JASON HIRSCHORN: Presies. 254 00:10:52,990 --> 00:10:57,970 So as ons dink oor runtime, die runtime van die plaas aan die einde 255 00:10:57,970 --> 00:11:00,110 sou n wees, die grootte van hierdie. 256 00:11:00,110 --> 00:11:03,080 Wat is die groot O looptyd van die plaas aan die begin? 257 00:11:03,080 --> 00:11:04,170 Konstante tyd. 258 00:11:04,170 --> 00:11:07,075 So as jy nie omgee oor die behoud van iets gesorteer, veel beter om net te 259 00:11:07,075 --> 00:11:08,420 voeg aan die begin van die lys. 260 00:11:08,420 --> 00:11:10,320 En dit kan in konstante tyd gedoen word. 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 operasie vind wat ander - Ons het hierdie geformuleer as soek. 264 00:11:18,870 --> 00:11:22,470 Maar ons gaan om te kyk deur die gekoppel lys vir 'n paar voorwerp. 265 00:11:22,470 --> 00:11:26,000 Julle het gesien kode vir soek voor in lesing. 266 00:11:26,000 --> 00:11:29,490 Maar ons soort het dit net met voeg, of ten minste inbring 267 00:11:29,490 --> 00:11:30,580 iets gesorteer. 268 00:11:30,580 --> 00:11:36,350 Jy kyk deur, gaan knoop deur knoop, totdat jy die nommer wat jy 269 00:11:36,350 --> 00:11:37,780 soek. 270 00:11:37,780 --> 00:11:39,670 Wat gebeur as jy bereik die einde van die lys? 271 00:11:39,670 --> 00:11:43,020 Sê ek is op soek na nege en ek bereik die einde van die lys. 272 00:11:43,020 --> 00:11:44,270 Wat doen ons? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> Publiek: Terug vals? 275 00:11:48,110 --> 00:11:48,690 >> JASON HIRSCHORN: Terug onwaar. 276 00:11:48,690 --> 00:11:49,960 Ons het dit nie vind nie. 277 00:11:49,960 --> 00:11:52,010 As jy aan die einde van die lys en jy het nie die nommer wat jy is 278 00:11:52,010 --> 00:11:54,170 soek, dit is nie daar in. 279 00:11:54,170 --> 00:11:55,420 Enige vrae oor kry? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 As dit was 'n gesorteerde lys, wat sou wees anders vir ons soek? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Ja. 284 00:12:08,103 --> 00:12:10,600 >> Publiek: Dit sal die eerste waarde vind dit is groter as die een wat 285 00:12:10,600 --> 00:12:12,390 jy soek en dan terug onwaar. 286 00:12:12,390 --> 00:12:13,190 >> JASON HIRSCHORN: Presies. 287 00:12:13,190 --> 00:12:17,310 So as dit is 'n gesorteerde lys, as ons kry om te iets wat groter is as wat 288 00:12:17,310 --> 00:12:20,180 ons soek, moet ons nie te hou gaan aan die einde van die lys. 289 00:12:20,180 --> 00:12:24,060 Ons kan op daardie punt terug valse want ons gaan nie om dit te vind. 290 00:12:24,060 --> 00:12:27,340 Die vraag is nou, ons het gepraat oor hou verband lyste gesorteer, 291 00:12:27,340 --> 00:12:28,180 hou hulle ongesorteerde. 292 00:12:28,180 --> 00:12:30,050 Dit gaan iets wat jy moet wees waarskynlik gaan hê om te dink oor 293 00:12:30,050 --> 00:12:34,240 wanneer kodering probleem stel vyf as jy kies 'n hash tafel met aparte 294 00:12:34,240 --> 00:12:36,360 chaining benadering, wat Ons sal later praat. 295 00:12:36,360 --> 00:12:41,400 >> Maar is dit die moeite werd om die lys te hou gesorteer en dan in staat wees om dalk het 296 00:12:41,400 --> 00:12:42,310 vinniger soektogte? 297 00:12:42,310 --> 00:12:47,220 Of is dit beter om vinnig te voeg iets in konstante runtime maar dan 298 00:12:47,220 --> 00:12:48,430 langer op soek? 299 00:12:48,430 --> 00:12:52,250 Dit is 'n nadeel reg daar dat jy kry om te besluit wat is meer gepas 300 00:12:52,250 --> 00:12:53,590 vir jou spesifieke probleem. 301 00:12:53,590 --> 00:12:56,680 En daar is nie noodwendig 'n absoluut reg antwoord. 302 00:12:56,680 --> 00:12:59,520 Maar dit is beslis 'n besluit wat jy kry te maak, en waarskynlik goed te verdedig 303 00:12:59,520 --> 00:13:05,270 wat in, sê, 'n opmerking of twee waarom jy het een oor die ander. 304 00:13:05,270 --> 00:13:06,490 >> Ten slotte, die verwydering. 305 00:13:06,490 --> 00:13:08,100 Ons het gesien hoe die verwydering. 306 00:13:08,100 --> 00:13:09,180 Dit is soortgelyk aan die soek. 307 00:13:09,180 --> 00:13:11,020 Ons kyk vir die element. 308 00:13:11,020 --> 00:13:12,390 Sê dat ons probeer om te verwyder van ses. 309 00:13:12,390 --> 00:13:14,450 So vind ons ses reg hier. 310 00:13:14,450 --> 00:13:18,860 Die ding wat ons het om seker te maak ons doen, is dat alles wat dui op 311 00:13:18,860 --> 00:13:21,220 ses - soos ons sien in stap twee hier - 312 00:13:21,220 --> 00:13:26,500 alles is wys tot ses behoeftes te slaan ses nou en word verander na 313 00:13:26,500 --> 00:13:28,160 net ses wys na. 314 00:13:28,160 --> 00:13:31,410 Ons wil nie om ooit die res van Orphan ons lys deur te vergeet om dit te stel 315 00:13:31,410 --> 00:13:32,960 vorige wyser. 316 00:13:32,960 --> 00:13:35,960 En dan soms, afhangende op die program, sal hulle net 317 00:13:35,960 --> 00:13:37,380 skrap hierdie knoop heeltemal. 318 00:13:37,380 --> 00:13:40,135 Soms sal jy wil om terug te keer die waarde wat in hierdie knoop. 319 00:13:40,135 --> 00:13:42,490 So dit is hoe die verwydering van werke. 320 00:13:42,490 --> 00:13:44,610 Enige vrae oor skrap? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> Publiek: So as jy gaan om te verwyder dit was, sou jy net gebruik vry omdat 323 00:13:53,850 --> 00:13:55,655 vermoedelik was dit malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON HIRSCHORN: As jy wil vry iets wat is presies reg, en jy 325 00:13:57,976 --> 00:13:58,540 malloced dit. 326 00:13:58,540 --> 00:14:00,410 Sê ons wou hierdie waarde om terug te keer. 327 00:14:00,410 --> 00:14:04,010 Ons kan terugkeer ses en dan gratis hierdie knoop en oproep gratis op dit. 328 00:14:04,010 --> 00:14:06,180 Of ons sou waarskynlik vry bel eerste en dan terug te keer ses. 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 So laat ons beweeg om te oefen kodering. 332 00:14:14,010 --> 00:14:16,090 Ons gaan drie funksies te kode. 333 00:14:16,090 --> 00:14:18,260 Die eerste een is insert_node genoem. 334 00:14:18,260 --> 00:14:22,170 So jy het kode wat ek per e-pos wat jy, en As jy hierdie is kyk later 335 00:14:22,170 --> 00:14:28,020 jy kan die kode toegang in linked.c op die CS50 webwerf. 336 00:14:28,020 --> 00:14:30,880 Maar in linked.c, daar is 'n paar geraamte kode wat reeds 337 00:14:30,880 --> 00:14:32,280 geskryf is vir jou. 338 00:14:32,280 --> 00:14:34,560 En dan is daar 'n paar funksies wat jy nodig het om te skryf. 339 00:14:34,560 --> 00:14:36,380 >> Eerste ons gaan skryf insert_node. 340 00:14:36,380 --> 00:14:39,800 En wat doen insert_node IS voeg 'n heelgetal. 341 00:14:39,800 --> 00:14:42,440 En jy gee die heelgetal in 'n geskakelde lys. 342 00:14:42,440 --> 00:14:45,470 En in die besonder, moet jy die lys gesorteer te hou 343 00:14:45,470 --> 00:14:47,650 van die kleinste tot die grootste. 344 00:14:47,650 --> 00:14:51,360 Ook, het jy nie wil Voeg enige duplikate. 345 00:14:51,360 --> 00:14:54,600 Ten slotte, as jy kan sien insert_node gee 'n Bool. 346 00:14:54,600 --> 00:14:57,140 So jy veronderstel is om jou te laat die gebruiker weet of die insetsel was 347 00:14:57,140 --> 00:15:00,800 suksesvolle deur die terugkeer waar of vals is. 348 00:15:00,800 --> 00:15:02,580 Aan die einde van hierdie program - 349 00:15:02,580 --> 00:15:05,750 en vir hierdie stadium het jy nie nodig bekommerd te wees oor die vrylating van enigiets. 350 00:15:05,750 --> 00:15:11,790 So al wat jy doen, is om 'n heelgetal en jy dit op 'n lys. 351 00:15:11,790 --> 00:15:13,890 >> Dit is wat ek vra jou nou te doen. 352 00:15:13,890 --> 00:15:17,620 Weereens, in die linked.c, wat jy al het, is die geraamte kode. 353 00:15:17,620 --> 00:15:20,980 En jy moet sien aan die onderkant die funksie voorbeeld verklaring. 354 00:15:20,980 --> 00:15:27,390 Maar voor hy in die kodering dit in C, ek raai u aan om te gaan 355 00:15:27,390 --> 00:15:29,330 deur die stappe wat ons het al oefen elke week. 356 00:15:29,330 --> 00:15:31,100 Ons het reeds deurgedring 'n foto van hierdie. 357 00:15:31,100 --> 00:15:33,380 So moet jy n mate van begrip het van hoe dit werk. 358 00:15:33,380 --> 00:15:36,590 Maar ek wil jou aanmoedig om te skryf sommige pseudokode voor duik in 359 00:15:36,590 --> 00:15:38,640 En ons gaan om te gaan pseudokode as 'n groep. 360 00:15:38,640 --> 00:15:41,470 En dan keer jy geskryf het jou pseudokode, en sodra ons geskryf ons 361 00:15:41,470 --> 00:15:45,850 pseudokode as 'n groep, kan jy gaan in die kodering in C. 362 00:15:45,850 --> 00:15:49,980 >> As 'n kop, die insert_node funksie is waarskynlik die moeilijkste van 363 00:15:49,980 --> 00:15:53,550 die drie ons gaan om te skryf, want ek bygevoeg 'n paar ekstra beperkinge te 364 00:15:53,550 --> 00:15:57,190 jou ontwikkeling, in die besonder wat jy is nie van plan om enige te voeg 365 00:15:57,190 --> 00:15:59,880 duplikate en dat die lys gesorteer moet bly. 366 00:15:59,880 --> 00:16:02,660 So dit is 'n nie-triviale program wat jy nodig het om te kode. 367 00:16:02,660 --> 00:16:06,470 En hoekom neem jy nie 06:55 minute net om die werk op die 368 00:16:06,470 --> 00:16:07,640 pseudokode en die kode. 369 00:16:07,640 --> 00:16:09,460 En dan sal ons begin gaan as 'n groep. 370 00:16:09,460 --> 00:16:11,680 Weereens, as jy enige vrae het net verhoog jou hand en ek sal bykom. 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 >> Ons het ook oor die algemeen doen hierdie - 375 00:18:30,120 --> 00:18:32,070 of ek uitdruklik sê nie dat jy met mense kan werk. 376 00:18:32,070 --> 00:18:36,500 Maar natuurlik, ek raai u aan, As jy vrae het, vra die 377 00:18:36,500 --> 00:18:39,840 naaste wat langs jou sit of selfs werk met iemand 378 00:18:39,840 --> 00:18:40,510 anders as jy wil. 379 00:18:40,510 --> 00:18:42,600 Dit hoef nie aan 'n individu wees stil aktiwiteit. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Kom ons begin met die skryf van 'n pseudokode op die bord. 382 00:20:16,330 --> 00:20:19,395 Wie kan my die eerste reël van die pseudokode vir hierdie program? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 Vir hierdie funksie, eerder - 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: So die eerste ding wat ek gedoen het, was skep 'n nuwe wyser na die knoop en ek 388 00:20:36,560 --> 00:20:41,320 geïnisialiseer dit verwys na dieselfde ding dat die lys is wat verwys na. 389 00:20:41,320 --> 00:20:41,550 >> JASON HIRSCHORN: OK. 390 00:20:41,550 --> 00:20:45,190 So jy skep 'n nuwe wyser aan die lys, nie aan die knoop. 391 00:20:45,190 --> 00:20:45,420 >> Publiek: Right. 392 00:20:45,420 --> 00:20:46,150 Ja. 393 00:20:46,150 --> 00:20:46,540 >> JASON HIRSCHORN: OK. 394 00:20:46,540 --> 00:20:48,221 En dan wat ons wil doen? 395 00:20:48,221 --> 00:20:49,163 Wat se nadat dit? 396 00:20:49,163 --> 00:20:50,105 Wat van die knoop? 397 00:20:50,105 --> 00:20:51,050 Ons het nie 'n knoop nie. 398 00:20:51,050 --> 00:20:52,300 Ons het net 'n waarde. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 As ons wil 'n knoop te voeg, wat doen ons moet jy eers doen voordat ons kan selfs 401 00:20:58,890 --> 00:20:59,980 dink oor die inbring nie? 402 00:20:59,980 --> 00:21:00,820 >> Publiek: Ag, jammer. 403 00:21:00,820 --> 00:21:02,160 ons nodig het om ruimte te malloc vir 'n knoop. 404 00:21:02,160 --> 00:21:02,455 >> JASON HIRSCHORN: Uitstekende. 405 00:21:02,455 --> 00:21:03,210 Kom ons doen - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Kan bereik nie dat 'n hoë. 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 Ons gaan om af te gaan, en dan ons gebruik twee kolomme. 411 00:21:13,236 --> 00:21:13,732 Ek kan nie 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 Skep 'n nuwe node. 415 00:21:25,130 --> 00:21:29,380 Jy kan 'n ander wyser skep om 'n lys of jy kan net gebruik lys as dit bestaan. 416 00:21:29,380 --> 00:21:30,720 Jy nie regtig nodig om dit te doen. 417 00:21:30,720 --> 00:21:31,750 >> So skep ons 'n nuwe knoop. 418 00:21:31,750 --> 00:21:32,010 Groot. 419 00:21:32,010 --> 00:21:32,840 Dit is wat ons doen eerste. 420 00:21:32,840 --> 00:21:34,870 Wat is volgende? 421 00:21:34,870 --> 00:21:35,080 >> Publiek: Wag. 422 00:21:35,080 --> 00:21:38,330 Indien ons 'n nuwe node nou of moet ons wag om seker te maak dat 423 00:21:38,330 --> 00:21:42,260 daar is geen duplikate van die node op die lys voordat ons dit skep? 424 00:21:42,260 --> 00:21:43,100 >> JASON HIRSCHORN: Goeie vraag. 425 00:21:43,100 --> 00:21:47,770 Kom ons hou dit vir later, want die meerderheid van die tyd wat ons sal skep 426 00:21:47,770 --> 00:21:48,220 'n nuwe knoop. 427 00:21:48,220 --> 00:21:49,110 So sal ons hier te hou nie. 428 00:21:49,110 --> 00:21:51,006 Maar dit is 'n goeie vraag. 429 00:21:51,006 --> 00:21:53,250 As ons dit geskep het en ons vind 'n duplikaat, wat moet 430 00:21:53,250 --> 00:21:54,490 ons doen voordat hy terugkeer? 431 00:21:54,490 --> 00:21:55,190 >> Publiek: vry om dit. 432 00:21:55,190 --> 00:21:55,470 >> JASON HIRSCHORN: Ja. 433 00:21:55,470 --> 00:21:56,500 Waarskynlik bevry nie. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Wat doen ons na ons Skep 'n nuwe node? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> Publiek: Ons het die nommer in die knoop? 438 00:22:04,780 --> 00:22:05,140 >> JASON HIRSCHORN: Presies. 439 00:22:05,140 --> 00:22:07,190 Ons het die nommer - ons malloc ruimte. 440 00:22:07,190 --> 00:22:08,160 Ek is van plan om dit te verlaat al as 'n reël. 441 00:22:08,160 --> 00:22:08,720 Maar jy is reg. 442 00:22:08,720 --> 00:22:10,305 Ons malloc ruimte, en dan Ons het die nommer in 443 00:22:10,305 --> 00:22:12,585 Ons kan selfs die wyser deel van dit te null. 444 00:22:12,585 --> 00:22:13,720 Dit is presies reg. 445 00:22:13,720 --> 00:22:17,400 En wat dan van daarna? 446 00:22:17,400 --> 00:22:18,490 Ons het hierdie foto op die bord. 447 00:22:18,490 --> 00:22:21,190 So, wat doen ons? 448 00:22:21,190 --> 00:22:22,680 >> Publiek: Ons gaan deur die lys. 449 00:22:22,680 --> 00:22:23,930 >> JASON HIRSCHORN: Gaan deur die lys. 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 kyk ons ​​vir by elke node. 453 00:22:34,280 --> 00:22:35,955 Kurt, wat doen ons kyk vir ten elke knoop? 454 00:22:35,955 --> 00:22:41,640 >> Publiek: Kyk of die n waarde van dat node is groter as die n waarde 455 00:22:41,640 --> 00:22:43,070 van ons node. 456 00:22:43,070 --> 00:22:43,340 >> JASON HIRSCHORN: OK. 457 00:22:43,340 --> 00:22:44,280 Ek gaan om te doen - 458 00:22:44,280 --> 00:22:45,855 ja, OK. 459 00:22:45,855 --> 00:22:48,160 So dit is n - 460 00:22:48,160 --> 00:22:59,040 Ek gaan om te sê as waarde is groter as dit knoop, dan wat doen ons? 461 00:22:59,040 --> 00:23:07,290 >> Publiek: Wel, dan moet ons voeg die ding reg voor dit. 462 00:23:07,290 --> 00:23:07,970 >> JASON HIRSCHORN: OK. 463 00:23:07,970 --> 00:23:09,410 So as dit is groter as dit, dan wil ons in te voeg. 464 00:23:09,410 --> 00:23:14,010 Maar ons wil om dit te sit reg voor omdat ons ook nodig sou wees 465 00:23:14,010 --> 00:23:16,070 dop, dan, van wat tevore was. 466 00:23:16,070 --> 00:23:22,690 So voeg voor. 467 00:23:22,690 --> 00:23:25,120 Dus het ons waarskynlik iets gemis Vroeër op. 468 00:23:25,120 --> 00:23:27,770 Ons het waarskynlik moet word hou spoor van wat aangaan. 469 00:23:27,770 --> 00:23:28,460 Maar ons sal terug te kry daar. 470 00:23:28,460 --> 00:23:30,160 So watter waarde is minder as? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, wat doen ons as waarde is minder as? 473 00:23:39,710 --> 00:23:43,000 >> Publiek: Dan moet jy hou net gaan tensy dit is die laaste een. 474 00:23:43,000 --> 00:23:43,550 >> JASON HIRSCHORN: Ek hou daarvan. 475 00:23:43,550 --> 00:23:44,800 So gaan na die volgende knoop. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Tensy dit is die laaste een - 478 00:23:48,930 --> 00:23:51,100 ons is waarskynlik die nagaan vir daardie in die terme van 'n toestand. 479 00:23:51,100 --> 00:23:54,870 Maar ja, die volgende knoop. 480 00:23:54,870 --> 00:23:58,680 En dit is steeds te laag is, so ons sal hier te beweeg. 481 00:23:58,680 --> 00:24:02,030 Maar as - 482 00:24:02,030 --> 00:24:03,280 kan almal sien dit? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 As ons gelyke wat doen ons? 485 00:24:11,610 --> 00:24:15,740 Indien die waarde wat ons probeer om te voeg is gelyk aan die knoop se waarde? 486 00:24:15,740 --> 00:24:16,320 Ja? 487 00:24:16,320 --> 00:24:18,400 >> Publiek: [onhoorbaar]. 488 00:24:18,400 --> 00:24:18,850 >> JASON HIRSCHORN: Ja. 489 00:24:18,850 --> 00:24:19,290 Gegewe hierdie - 490 00:24:19,290 --> 00:24:20,090 Marcus is reg. 491 00:24:20,090 --> 00:24:21,330 Ons kon dalk gedoen iets anders. 492 00:24:21,330 --> 00:24:25,360 Maar gegewe dat ons het dit geskep, hier ons moet vry en dan terug te keer. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Is dit beter? 495 00:24:30,080 --> 00:24:31,850 Hoe is dit? 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 ons terugkeer, [onhoorbaar]? 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 Is ons ontbreek enigiets? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 So waar gaan ons die dop van die vorige knoop? 504 00:24:59,650 --> 00:25:02,370 >> Publiek: Ek dink dit sou gaan na 'n nuwe knoop. 505 00:25:02,370 --> 00:25:02,600 >> JASON HIRSCHORN: OK. 506 00:25:02,600 --> 00:25:03,940 So aan die begin Ons sal waarskynlik - 507 00:25:03,940 --> 00:25:07,175 Ja, ons kan 'n wyser skep van 'n nuwe knoop, soos 'n vorige node wyser en 508 00:25:07,175 --> 00:25:09,600 'n knoop wyser. 509 00:25:09,600 --> 00:25:12,640 So laat se plaas dit hier. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Skep huidige en vorige verwysings na die nodes. 512 00:25:26,900 --> 00:25:28,955 Maar toe ons die wysers pas? 513 00:25:28,955 --> 00:25:30,205 Waar doen ons dit in die kode? 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: - waarde toestande? 517 00:25:35,170 --> 00:25:36,420 >> JASON HIRSCHORN: Watter een in die besonder? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> Publiek: Ek is net verwar. 520 00:25:40,720 --> 00:25:44,200 As waarde is groter as die knoop, nie dat beteken dat jy wil gaan 521 00:25:44,200 --> 00:25:45,320 na die volgende knoop? 522 00:25:45,320 --> 00:25:49,515 >> JASON Hirsch: So as ons waarde is groter as die waarde van hierdie knoop. 523 00:25:49,515 --> 00:25:52,130 >> Publiek: Ja, dan moet jy graag wil hê om gaan verder in die ry nie, reg? 524 00:25:52,130 --> 00:25:52,590 >> JASON Hirsch: Right. 525 00:25:52,590 --> 00:25:53,840 Sodat ons nie hier plaas dit nie. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 As waarde is minder as die knoop, dan Ons gaan na die volgende knoop - of dan 528 00:26:03,240 --> 00:26:03,835 voeg voor. 529 00:26:03,835 --> 00:26:05,966 >> Publiek: Wag, wat hierdie knoop en wat is waarde? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON Hirsch: Goeie vraag. 532 00:26:09,280 --> 00:26:13,260 Waarde per hierdie funksie definisie is wat ons gegee. 533 00:26:13,260 --> 00:26:16,910 So waarde is die getal wat ons gegee. 534 00:26:16,910 --> 00:26:21,120 Dus, as die waarde is minder as dit knoop, moet ons tyd in te voeg. 535 00:26:21,120 --> 00:26:24,575 As waarde is groter as die knoop, Ons gaan na die volgende knoop. 536 00:26:24,575 --> 00:26:26,790 En terug na die oorspronklike vraag, al is, waar - 537 00:26:26,790 --> 00:26:29,060 >> Publiek: As waarde is groter as hierdie knoop. 538 00:26:29,060 --> 00:26:30,310 >> JASON Hirsch: En so wat doen ons hier doen? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Soet. 541 00:26:38,160 --> 00:26:38,860 Dit is korrek. 542 00:26:38,860 --> 00:26:41,370 Ek gaan net om te skryf update wysers. 543 00:26:41,370 --> 00:26:44,010 Maar ja, met die huidige een jy sal dit werk na 544 00:26:44,010 --> 00:26:46,080 verwys na die volgende een. 545 00:26:46,080 --> 00:26:47,330 Enigiets anders wat ons mis? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 So ek gaan om dit te tik kode in gedit. 548 00:26:54,940 --> 00:26:58,375 En terwyl ek dit doen, kan jy 'n paar minute om te werk aan kodering 549 00:26:58,375 --> 00:28:19,240 dit in C. 550 00:28:19,240 --> 00:28:20,940 >> So ek het die invoer van die pseudokode. 551 00:28:20,940 --> 00:28:22,940 'N vinnige nota voordat ons begin. 552 00:28:22,940 --> 00:28:25,560 Ons kan nie in staat om heeltemal klaar is met hierdie in alle 553 00:28:25,560 --> 00:28:27,300 drie van hierdie funksies. 554 00:28:27,300 --> 00:28:30,630 Daar is korrekte oplossings aan hulle dat ek sal e-pos aan u ouens 555 00:28:30,630 --> 00:28:33,730 na artikel, en dit sal op CS50.net gepos. 556 00:28:33,730 --> 00:28:35,640 So ek moedig jou nie gaan kyk na die artikels. 557 00:28:35,640 --> 00:28:40,550 Ek moedig jou om dit te probeer op jou besit, en gebruik dan die praktyk 558 00:28:40,550 --> 00:28:41,760 probleme jou antwoorde te kontroleer. 559 00:28:41,760 --> 00:28:47,070 Hierdie is almal ontwerp om te werk nou verband hou en vas te hou wat 560 00:28:47,070 --> 00:28:48,400 jy hoef te doen oor die probleem stel. 561 00:28:48,400 --> 00:28:53,820 So ek u aanmoedig om dit te oefen op jou eie en gebruik dan die kode 562 00:28:53,820 --> 00:28:54,660 kontroleer jou antwoorde. 563 00:28:54,660 --> 00:28:57,060 Omdat ek nie wil hê om aan te beweeg om hash tafels op 'n sekere punt in die artikel. 564 00:28:57,060 --> 00:28:58,150 So ons kan dit nie kry deur dit alles. 565 00:28:58,150 --> 00:28:59,960 Maar ons sal nou soveel ons kan doen. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Kom ons begin. 568 00:29:01,960 --> 00:29:04,770 ASAM, hoe skep ons 'n nuwe knoop? 569 00:29:04,770 --> 00:29:06,810 >> Publiek: Jy struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON Hirsch: So ons het dat hier. 571 00:29:09,640 --> 00:29:10,040 O, jammer. 572 00:29:10,040 --> 00:29:13,530 Jy het gesê struct *. 573 00:29:13,530 --> 00:29:17,260 >> Publiek: En dan [? soort?] knoop of c knoop. 574 00:29:17,260 --> 00:29:17,780 >> JASON Hirsch: OK. 575 00:29:17,780 --> 00:29:19,740 Ek gaan om dit te noem new_node sodat ons kan bly konsekwent. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> Publiek: En jy wil om dit te stel aan die hoof, die eerste knoop. 578 00:29:33,180 --> 00:29:33,580 >> JASON Hirsch: OK. 579 00:29:33,580 --> 00:29:37,290 So nou is dit wys om - so dit het nie 'n nuwe node geskep het nie. 580 00:29:37,290 --> 00:29:41,380 Dit is net te wys op die eerste nodus in die lys. 581 00:29:41,380 --> 00:29:42,630 Hoe kan ek 'n nuwe knoop? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 As ek moet ruimte 'n nuwe node te skep. 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: Die grootte van die struct. 587 00:30:00,390 --> 00:30:01,150 >> JASON Hirsch: Die grootte van die struct. 588 00:30:01,150 --> 00:30:02,400 En wat is die struct genoem? 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 Hirsch: Node. 592 00:30:11,640 --> 00:30:17,640 So malloc (sizeof (nodig)); gee ons die ruimte. 593 00:30:17,640 --> 00:30:19,740 En is hierdie lyn - 594 00:30:19,740 --> 00:30:21,740 een ding is verkeerd op hierdie lyn. 595 00:30:21,740 --> 00:30:24,430 Is new_node 'n verwysing na 'n struct? 596 00:30:24,430 --> 00:30:25,650 Dit is 'n generiese naam. 597 00:30:25,650 --> 00:30:26,520 Wat is dit - 598 00:30:26,520 --> 00:30:27,450 knoop, presies. 599 00:30:27,450 --> 00:30:29,340 Dit is 'n knoop *. 600 00:30:29,340 --> 00:30:33,010 En wat doen ons reg na ons malloc iets Asan? 601 00:30:33,010 --> 00:30:34,476 Wat is die eerste ding wat ons doen? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Wat as dit nie werk nie? 604 00:30:40,320 --> 00:30:42,430 >> Publiek: Ag, kyk of dit wys na die knoop? 605 00:30:42,430 --> 00:30:43,310 >> JASON Hirsch: Presies. 606 00:30:43,310 --> 00:30:46,750 So as jy new_node gelyk gelykes nul, wat doen ons? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Dit gee 'n Bool, hierdie funksie. 609 00:30:54,820 --> 00:30:57,760 Presies. 610 00:30:57,760 --> 00:30:58,450 Lyk goed. 611 00:30:58,450 --> 00:30:59,680 Enigiets om daar te voeg? 612 00:30:59,680 --> 00:31:00,670 Ons sal dinge aan die einde voeg. 613 00:31:00,670 --> 00:31:03,160 Maar dat so ver lyk goed. 614 00:31:03,160 --> 00:31:06,170 Skep huidige en vorige wysers. 615 00:31:06,170 --> 00:31:08,650 Michael, hoe doen ek dit? 616 00:31:08,650 --> 00:31:12,810 >> Publiek: Jy wil hê 'n knoop te doen *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Jy wil hê om een ​​te maak nie vir new_node maar vir die 619 00:31:25,502 --> 00:31:26,905 nodes ons reeds het. 620 00:31:26,905 --> 00:31:27,230 >> JASON Hirsch: OK. 621 00:31:27,230 --> 00:31:29,255 So het die knoop ons op. 622 00:31:29,255 --> 00:31:30,505 Ek bel dat Kur. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Alle regte. 625 00:31:39,770 --> 00:31:41,620 Ons het besluit ons wil hou twee, want ons moet weet 626 00:31:41,620 --> 00:31:42,870 Wat is voordat dit. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Wat kry hulle geïnisialiseer om? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> Publiek: die waarde daarvan in ons lys. 631 00:31:54,180 --> 00:31:58,090 >> JASON Hirsch: So, wat is die eerste ding op die lys? 632 00:31:58,090 --> 00:32:04,050 Of hoe weet ons waar die begin van ons lys is? 633 00:32:04,050 --> 00:32:08,015 >> Publiek: Is dit nie geslaag in die funksie? 634 00:32:08,015 --> 00:32:08,466 >> JASON Hirsch: Right. 635 00:32:08,466 --> 00:32:09,716 Dit is in hier verby. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 So as dit geslaag het in die funksie, die die begin van die lys, wat moet ons 638 00:32:18,980 --> 00:32:21,270 Stel huidige gelyk aan? 639 00:32:21,270 --> 00:32:22,110 >> Publiek: List. 640 00:32:22,110 --> 00:32:22,900 >> JASON Hirsch: Lys. 641 00:32:22,900 --> 00:32:24,090 Dit is presies reg. 642 00:32:24,090 --> 00:32:26,290 Nou het dit die adres van die begin van die lys. 643 00:32:26,290 --> 00:32:28,450 En wat van die vorige? 644 00:32:28,450 --> 00:32:31,920 >> Publiek: Lys minus een? 645 00:32:31,920 --> 00:32:32,690 >> JASON Hirsch: Daar is niks voor dit. 646 00:32:32,690 --> 00:32:34,580 So wat kan ons niks doen nie, om aan te dui? 647 00:32:34,580 --> 00:32:35,050 >> Publiek: null. 648 00:32:35,050 --> 00:32:35,450 >> JASON Hirsch: Ja. 649 00:32:35,450 --> 00:32:37,950 Dit klink soos 'n goeie idee. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Dankie. 652 00:32:39,630 --> 00:32:42,850 Gaan deur die lys. 653 00:32:42,850 --> 00:32:45,490 Konstantyn, hoe lank gaan ons om te gaan deur die lys? 654 00:32:45,490 --> 00:32:49,010 >> Publiek: totdat ons null. 655 00:32:49,010 --> 00:32:49,390 >> JASON Hirsch: OK. 656 00:32:49,390 --> 00:32:50,430 So as ons, terwyl, vir lus. 657 00:32:50,430 --> 00:32:52,200 Wat doen ons? 658 00:32:52,200 --> 00:32:53,320 >> Publiek: Miskien is 'n lus vir? 659 00:32:53,320 --> 00:32:53,910 >> JASON Hirsch: Kom ons doen 'n lus vir. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> Publiek: En ons sê vir - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 totdat die huidige wyser is nie gelyk aan nul. 664 00:33:13,390 --> 00:33:19,160 >> JASON Hirsch: So as ons weet wat die toestand is, hoe kan ons skryf 'n lus 665 00:33:19,160 --> 00:33:21,740 gebaseer af die toestand. 666 00:33:21,740 --> 00:33:24,380 Watter soort van 'n lus moet ons gebruik? 667 00:33:24,380 --> 00:33:25,260 >> Publiek: Terwyl. 668 00:33:25,260 --> 00:33:25,590 >> JASON Hirsch: Ja. 669 00:33:25,590 --> 00:33:27,130 Dit maak meer sin gebaseer af van wat jy gesê het. 670 00:33:27,130 --> 00:33:29,430 As ons wil net om te gaan in ons sou dit weet net dat die ding, sou dit maak 671 00:33:29,430 --> 00:33:31,680 sin 'n rukkie lus om te doen. 672 00:33:31,680 --> 00:33:39,880 Terwyl die huidige nie gelyk nul, As waarde is minder as die knoop. 673 00:33:39,880 --> 00:33:41,650 Akshar, gee my daardie lyn. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> Publiek: As die huidige-> n n minder as waarde. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Of reverse nie. 678 00:34:03,260 --> 00:34:06,140 Skakel dat bracket. 679 00:34:06,140 --> 00:34:06,620 >> JASON Hirsch: Jammer. 680 00:34:06,620 --> 00:34:08,760 >> Publiek: Verander die bracket. 681 00:34:08,760 --> 00:34:10,914 >> JASON Hirsch: So as dit groter as waarde. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Want dit is verwarrend met die kommentaar hierbo, ek gaan om dit te doen. 684 00:34:22,120 --> 00:34:22,480 Maar ja. 685 00:34:22,480 --> 00:34:25,125 As ons waarde is minder as dit knoop, wat doen ons? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Ek het dit hier. 688 00:34:26,710 --> 00:34:27,960 Voeg tevore. 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 ons dit? 692 00:34:33,933 --> 00:34:34,900 >> Publiek: Is dit nog steeds vir my? 693 00:34:34,900 --> 00:34:36,150 >> JASON Hirsch: Ja. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> Publiek: Jy - 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 Hirsch: So, wat is wat gaan gelyk? 700 00:34:50,163 --> 00:34:52,070 >> Publiek: Dit gaan gelyk huidige. 701 00:34:52,070 --> 00:34:53,889 >> JASON Hirsch: Presies. 702 00:34:53,889 --> 00:34:55,730 En so het die ander - 703 00:34:55,730 --> 00:34:56,730 Wat anders moet ons te werk? 704 00:34:56,730 --> 00:34:59,982 >> Publiek: Kyk of gelyk afgelope null. 705 00:34:59,982 --> 00:35:01,870 >> JASON Hirsch: As Vorige - 706 00:35:01,870 --> 00:35:03,730 so as vorige gelyk aan nul. 707 00:35:03,730 --> 00:35:05,990 >> Publiek: Dit beteken dit gaan aan die hoof geword. 708 00:35:05,990 --> 00:35:06,780 >> JASON Hirsch: Dit beteken dit is nou die hoof. 709 00:35:06,780 --> 00:35:07,620 So dan wat doen ons? 710 00:35:07,620 --> 00:35:12,510 >> Publiek: Ons doen hoof gelyk new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON Hirsch: Hoof gelyk new_node. 712 00:35:16,690 --> 00:35:20,540 En hoekom kop hier, nie die lys? 713 00:35:20,540 --> 00:35:24,940 >> Publiek: Omdat kop is 'n globale veranderlike, wat is die beginpunt. 714 00:35:24,940 --> 00:35:26,190 >> JASON Hirsch: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 En - 718 00:35:36,150 --> 00:35:53,796 >> Publiek: dan doen jy anders prev-> volgende gelyk new_node. 719 00:35:53,796 --> 00:35:55,080 En dan moet jy weer waar. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON Hirsch: Waar Ons stel new_node einde? 722 00:36:02,700 --> 00:36:04,850 >> Publiek: Ek sou - 723 00:36:04,850 --> 00:36:06,180 Ek stel dat aan die begin. 724 00:36:06,180 --> 00:36:07,430 >> JASON Hirsch: So watter lyn? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> Publiek: Na afloop van die if-stelling seker te maak dat dit bekend is. 727 00:36:12,598 --> 00:36:13,057 >> JASON Hirsch: Right hier? 728 00:36:13,057 --> 00:36:18,335 >> Publiek: ek wil doen new_node-> n gelyk aan waarde. 729 00:36:18,335 --> 00:36:19,585 >> JASON Hirsch: Klink goed. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Waarskynlik maak dit sin - ons doen nie nodig het om te weet wat die lys is ons op 732 00:36:25,090 --> 00:36:26,280 omdat ons net die hantering met 'n lys. 733 00:36:26,280 --> 00:36:29,560 So 'n beter funksie verklaring vir dit is net om ontslae te raak van hierdie 734 00:36:29,560 --> 00:36:34,360 geheel en voeg net 'n waarde in die kop. 735 00:36:34,360 --> 00:36:35,930 Ons het nie eens nodig om te weet wat lys ons is in 736 00:36:35,930 --> 00:36:39,140 Maar ek sal dit hou vir nou en dan verander dit op die opdatering 737 00:36:39,140 --> 00:36:42,590 die skyfies en kode. 738 00:36:42,590 --> 00:36:44,980 So wat goed lyk vir nou. 739 00:36:44,980 --> 00:36:46,560 As waarde - wat hierdie lyn kan doen? 740 00:36:46,560 --> 00:36:47,810 Indien - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 wat doen ons hier doen, Noag. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> Publiek: As waarde is groter as Kur-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON Hirsch: Hoe doen Ons gaan na die volgende knoop? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> Publiek: Kur-> n is gelyk aan new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON Hirsch: So n ' wat deel van die struct? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 Die heelgetal. 753 00:37:46,020 --> 00:37:50,420 En new_node is 'n verwysing na 'n knoop. 754 00:37:50,420 --> 00:37:51,880 So, wat deel uitmaak van Kur moet ons werk? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Indien nie n, dan wat is die ander deel? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noag, wat is die ander deel. 759 00:38:22,810 --> 00:38:23,570 >> Publiek: Ag, die volgende. 760 00:38:23,570 --> 00:38:25,645 >> JASON Hirsch: Volgende, presies. 761 00:38:25,645 --> 00:38:26,410 Presies. 762 00:38:26,410 --> 00:38:28,770 Volgende is die regte een. 763 00:38:28,770 --> 00:38:31,540 En wat anders het ons nodig te werk, Noag? 764 00:38:31,540 --> 00:38:32,840 >> Publiek: Die wysers. 765 00:38:32,840 --> 00:38:34,840 >> JASON Hirsch: So ons by die huidige. 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 Hirsch: Ja. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, ons sal breek. 771 00:38:58,370 --> 00:39:02,200 Wat ons kan help hier? 772 00:39:02,200 --> 00:39:03,385 Manu, wat moet ons doen? 773 00:39:03,385 --> 00:39:05,615 >> Publiek: Jy het om te stel dit gelyk aan Kur-> volgende. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Maar dit doen voordat die vorige lyn. 776 00:39:11,630 --> 00:39:12,880 >> JASON Hirsch: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Enigiets anders? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> Publiek: Ek dink nie jy bedoel Kur-> te verander volgende. 781 00:39:22,680 --> 00:39:29,270 Ek dink jy bedoel Kur gelykes te doen Kur-> volgende om te gaan na die volgende knoop. 782 00:39:29,270 --> 00:39:30,500 >> JASON Hirsch: So jammer, waar? 783 00:39:30,500 --> 00:39:32,680 Op watter lyn? 784 00:39:32,680 --> 00:39:33,420 Hierdie lyn? 785 00:39:33,420 --> 00:39:33,750 >> Publiek: Ja. 786 00:39:33,750 --> 00:39:35,745 Maak Kur gelyk Kur-> volgende. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON Hirsch: So dit is korrek omdat die huidige is 'n 789 00:39:43,360 --> 00:39:45,220 wyser na 'n knoop. 790 00:39:45,220 --> 00:39:48,550 En ons wil om dit te wys op die volgende knoop van wat tans kry 791 00:39:48,550 --> 00:39:49,930 wys na. 792 00:39:49,930 --> 00:39:54,410 Kur self het 'n volgende. 793 00:39:54,410 --> 00:39:58,620 Maar as ons curr.next te werk, het ons sou opdatering word om die werklike noot 794 00:39:58,620 --> 00:40:01,430 self, nie waar hierdie wyser is wys. 795 00:40:01,430 --> 00:40:02,680 Wat van hierdie lyn, al is. 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-> langs gelyk Kur. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON Hirsch: So weer, as vorige is 'n wyser na 'n knoop, vorige-> Volgende is die 801 00:40:19,440 --> 00:40:23,020 werklike wyser in die knoop. 802 00:40:23,020 --> 00:40:27,190 So dit sal die opdatering word om 'n aanwijzer in 'n knoop te Kur. 803 00:40:27,190 --> 00:40:28,570 Ons wil nie te werk 'n wyser in 'n knoop. 804 00:40:28,570 --> 00:40:30,570 Ons wil om te werk vorige. 805 00:40:30,570 --> 00:40:31,850 So, hoe kan ons dit doen? 806 00:40:31,850 --> 00:40:34,250 >> Publiek: Dit sou net prev word. 807 00:40:34,250 --> 00:40:34,565 >> JASON Hirsch: Right. 808 00:40:34,565 --> 00:40:35,560 Vorige is 'n verwysing na 'n knoop. 809 00:40:35,560 --> 00:40:38,750 Nou is ons om dit te verander na 'n nuwe wyser na 'n knoop. 810 00:40:38,750 --> 00:40:40,830 OK Kom ons af beweeg. 811 00:40:40,830 --> 00:40:41,940 Ten slotte, hierdie laaste toestand. 812 00:40:41,940 --> 00:40:44,896 Jeff, wat doen ons hier doen? 813 00:40:44,896 --> 00:40:47,515 >> Publiek: As waarde is gelyk aan Kur-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON Hirsch: Jammer. 816 00:40:51,300 --> 00:40:52,372 Ag, my goedheid. 817 00:40:52,372 --> 00:40:54,330 Wat? 818 00:40:54,330 --> 00:40:55,580 Waarde == Kur-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Wat doen ons? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> Publiek: Jy wil bevry ons new_node, en dan sal jy terugkeer onwaar. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON Hirsch: Dit is wat wat ons tot dusver geskryf. 825 00:41:23,460 --> 00:41:25,710 Het enige iemand iets te voeg voordat ons? 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 Kom ons probeer dit. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Beheer kan die einde bereik van 'n nie-leemte funksie. 831 00:41:46,110 --> 00:41:48,310 Avi, wat gaan aan? 832 00:41:48,310 --> 00:41:51,380 >> Publiek: Is jy veronderstel terugkeer te sit ware buite die lus? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON Hirsch: Ek weet nie. 835 00:41:54,400 --> 00:41:54,780 Wil jy my te? 836 00:41:54,780 --> 00:41:55,520 >> Publiek: Toemaar. 837 00:41:55,520 --> 00:41:56,350 No 838 00:41:56,350 --> 00:41:57,180 >> JASON Hirsch: akshar? 839 00:41:57,180 --> 00:41:59,460 >> Publiek: Ek dink jy bedoel om te sit terugkeer valse aan die einde 840 00:41:59,460 --> 00:42:02,230 van die lus. 841 00:42:02,230 --> 00:42:03,270 >> JASON Hirsch: So waar wil jy dit om te gaan? 842 00:42:03,270 --> 00:42:05,270 >> Publiek: Hou buite die lus. 843 00:42:05,270 --> 00:42:08,800 So as jy die uitgang van die tyd lus wat beteken wat jy aan die einde gekom en 844 00:42:08,800 --> 00:42:09,980 niks gebeur het. 845 00:42:09,980 --> 00:42:10,410 >> JASON Hirsch: OK. 846 00:42:10,410 --> 00:42:12,340 So, wat doen ons hier? 847 00:42:12,340 --> 00:42:13,702 >> Publiek: Jy terugkeer valse is daar ook. 848 00:42:13,702 --> 00:42:15,040 >> JASON Hirsch: Ag, het ons doen dit in beide plekke? 849 00:42:15,040 --> 00:42:15,650 >> Publiek: Ja. 850 00:42:15,650 --> 00:42:16,900 >> JASON Hirsch: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Moet ons gaan? 853 00:42:26,160 --> 00:42:26,980 Ag, my goedheid. 854 00:42:26,980 --> 00:42:27,290 Ek is jammer. 855 00:42:27,290 --> 00:42:28,480 Ek vra om verskoning vir die skerm. 856 00:42:28,480 --> 00:42:30,530 Dit is soort van uitgefreakt oor ons. 857 00:42:30,530 --> 00:42:31,520 So kies 'n opsie. 858 00:42:31,520 --> 00:42:35,260 Zero, per die kode, verlaat die program. 859 00:42:35,260 --> 00:42:36,700 Een voeg iets. 860 00:42:36,700 --> 00:42:37,990 Kom ons voeg drie. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 Die insetsel was nie suksesvol nie. 863 00:42:45,380 --> 00:42:46,500 Ek gaan om uit te druk. 864 00:42:46,500 --> 00:42:48,050 Ek het niks nie. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Miskien was dit net 'n gelukskoot. 867 00:42:50,250 --> 00:42:52,810 Voeg een. 868 00:42:52,810 --> 00:42:55,770 Nie suksesvol nie. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Kom ons loop deur GDB regtig vinnig om te kyk na wat aangaan. 871 00:43:02,400 --> 00:43:06,055 >> Onthou gdb. / Die naam van jou program kry ons in GDB. 872 00:43:06,055 --> 00:43:07,610 Is dit 'n baie om te hanteer? 873 00:43:07,610 --> 00:43:08,560 Die flikker? 874 00:43:08,560 --> 00:43:10,400 Waarskynlik. 875 00:43:10,400 --> 00:43:12,760 Maak jou oë toe en neem 'n diep blaas as jy moeg 876 00:43:12,760 --> 00:43:13,580 om daarna te kyk. 877 00:43:13,580 --> 00:43:14,200 Ek is in GDB. 878 00:43:14,200 --> 00:43:15,830 Wat is die eerste ding wat ek doen in GDB? 879 00:43:15,830 --> 00:43:17,050 Ons het om uit te vind wat gaan hier aan. 880 00:43:17,050 --> 00:43:17,310 Kom ons kyk. 881 00:43:17,310 --> 00:43:21,650 Ons het ses minute na figuur uit te vind wat gaan aan. 882 00:43:21,650 --> 00:43:22,900 Breek hoof. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 En dan wat doen ek? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Begin. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Kom ons kies 'n opsie. 889 00:43:34,160 --> 00:43:36,330 En wat beteken N doen? 890 00:43:36,330 --> 00:43:38,480 Volgende. 891 00:43:38,480 --> 00:43:38,950 Ja. 892 00:43:38,950 --> 00:43:39,740 >> Publiek: Het jy nie noem - 893 00:43:39,740 --> 00:43:45,230 Het jy nie gesê dat die hoof, was dit geïnisialiseer te null aan die begin. 894 00:43:45,230 --> 00:43:47,140 Maar ek het gedink jy het gesê dit was OK. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON Hirsch: Kom ons gaan - kom ons kyk in GDB, en dan sal ons terug te gaan. 897 00:43:52,640 --> 00:43:54,910 Maar dit klink asof jy reeds 'n paar idees oor wat aangaan. 898 00:43:54,910 --> 00:43:58,340 So wil ons iets te voeg. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Ons het plaas. 901 00:44:00,150 --> 00:44:00,770 Tik 'n int. 902 00:44:00,770 --> 00:44:01,990 Ons sal voeg drie. 903 00:44:01,990 --> 00:44:03,000 En dan is ek op hierdie lyn. 904 00:44:03,000 --> 00:44:07,030 Hoe gaan ek begin debugging die insetsel bekend funksie? 905 00:44:07,030 --> 00:44:08,280 Ag, my goedheid. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 Dit is 'n baie. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Is dit uitgefreakt 'n baie? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> Publiek: O, dit is dood. 912 00:44:21,680 --> 00:44:22,930 >> JASON Hirsch: Ek het net trek dit 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: Miskien is dit die ander kant van die draad. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON Hirsch: Wow. 918 00:44:39,470 --> 00:44:42,330 So het die onderste lyn - 919 00:44:42,330 --> 00:44:43,470 wat het jy gesê? 920 00:44:43,470 --> 00:44:46,040 >> Publiek: Ek het die ironie van die tegniese probleme in hierdie klas. 921 00:44:46,040 --> 00:44:46,410 >> JASON Hirsch: Ek weet. 922 00:44:46,410 --> 00:44:48,660 As ek maar net beheer oor die deel. 923 00:44:48,660 --> 00:44:49,910 [Onhoorbaar] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Dit klink great. 926 00:44:55,400 --> 00:44:58,680 Hoekom nie julle ouens begin nie dink oor wat ons kan verkeerd gedoen het, 927 00:44:58,680 --> 00:45:01,140 en ons sal in 90 sekondes. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, ek gaan om te vra hoe om te gaan binne insert_node dit te ontfout. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 So dit is waar ons gebly het. 932 00:46:31,460 --> 00:46:35,110 Hoe kan ek gaan binne insert_node, Avica, te ondersoek wat gaan aan? 933 00:46:35,110 --> 00:46:36,360 Wat GDB opdrag? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Breek nie sou neem my binnekant. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Maak Marquise ken? 938 00:46:47,130 --> 00:46:48,240 >> Publiek: Wat? 939 00:46:48,240 --> 00:46:51,780 >> JASON Hirsch: Wat GDB opdrag Ek gebruik om te gaan binne hierdie funksie? 940 00:46:51,780 --> 00:46:52,070 >> Publiek: Stap? 941 00:46:52,070 --> 00:46:55,140 >> JASON Hirsch: Stap via S. Dit neem my binnekant. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing ruimte. 944 00:46:58,040 --> 00:46:59,120 Dat al lyk sy gaan. 945 00:46:59,120 --> 00:47:00,370 Kom ons ondersoek new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Dit het 'n paar geheue adres. 948 00:47:05,410 --> 00:47:07,440 Kom ons kyk - 949 00:47:07,440 --> 00:47:08,500 dit is alles reg. 950 00:47:08,500 --> 00:47:12,220 So alles hier lyk word korrek werk. 951 00:47:12,220 --> 00:47:14,530 >> Publiek: Wat is die verskil tussen P en vertoon? 952 00:47:14,530 --> 00:47:16,160 >> JASON Hirsch: P staan ​​vir die gedrukte media. 953 00:47:16,160 --> 00:47:19,310 En so jy vra wat is die verskil tussen dit en dit? 954 00:47:19,310 --> 00:47:22,330 In hierdie geval, niks. 955 00:47:22,330 --> 00:47:26,960 Maar oor die algemeen is daar 'n paar verskille. 956 00:47:26,960 --> 00:47:28,220 En jy moet kyk in die GDB handleiding. 957 00:47:28,220 --> 00:47:29,560 Maar in hierdie geval, niks. 958 00:47:29,560 --> 00:47:31,460 Ons is geneig om druk te gebruik nie, want hoef ons nie veel meer as om te doen 959 00:47:31,460 --> 00:47:33,960 druk 'n enkele waarde. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 So ons is op die lyn 80 van ons kode, opstel knoop * Kur gelyk aan lys. 962 00:47:40,300 --> 00:47:42,500 Kom ons druk Kur. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Dit is gelyk aan die lys. 965 00:47:46,840 --> 00:47:48,850 Soet. 966 00:47:48,850 --> 00:47:49,340 Wag nie. 967 00:47:49,340 --> 00:47:50,590 Dit is gelykstaande aan iets. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Dit beteken nie reg lyk. 970 00:47:56,190 --> 00:47:56,840 Daar gaan ons. 971 00:47:56,840 --> 00:47:59,470 Dit is omdat in GDB, regs, indien dit is die lyn wat jy op dit 972 00:47:59,470 --> 00:48:00,330 het nie uitgevoer nie. 973 00:48:00,330 --> 00:48:03,100 Sodat jy nodig het om werklik te tik volgende die lyn uit te voer 974 00:48:03,100 --> 00:48:05,230 voor sien sy resultate. 975 00:48:05,230 --> 00:48:06,680 So hier is ons. 976 00:48:06,680 --> 00:48:09,490 Ons het net uitgevoer hierdie lyn, vorige gelyk aan nul. 977 00:48:09,490 --> 00:48:13,590 So weer, as ons druk vorige sal ons nie sien nie vreemd. 978 00:48:13,590 --> 00:48:18,680 Maar as ons eintlik voer wat lyn, dan sal ons sien 979 00:48:18,680 --> 00:48:20,380 dat die lyn gewerk. 980 00:48:20,380 --> 00:48:21,060 >> So ons het Kur. 981 00:48:21,060 --> 00:48:23,180 Dit is beide goed. 982 00:48:23,180 --> 00:48:24,010 Reg? 983 00:48:24,010 --> 00:48:28,130 Nou is ons op hierdie lyn hier. 984 00:48:28,130 --> 00:48:29,310 Terwyl Kur nie gelyk null. 985 00:48:29,310 --> 00:48:31,110 Wel, wat doen Kur gelyk? 986 00:48:31,110 --> 00:48:32,450 Ons het net het dit geëwenaar null. 987 00:48:32,450 --> 00:48:33,210 Ons het dit gedruk word. 988 00:48:33,210 --> 00:48:35,110 Ek sal dit druk weer. 989 00:48:35,110 --> 00:48:36,720 So is dat terwyl lus gaan uit te voer? 990 00:48:36,720 --> 00:48:37,270 >> Publiek: No 991 00:48:37,270 --> 00:48:39,790 >> JASON Hirsch: So dat wanneer ek getik lyn, jy sien ons gespring al die pad 992 00:48:39,790 --> 00:48:41,390 af na die onderkant, terugkeer onwaar. 993 00:48:41,390 --> 00:48:44,520 En dan gaan ons valse om terug te keer en gaan terug na ons program en 994 00:48:44,520 --> 00:48:48,020 uiteindelik druk, soos ons gesien het, die insetsel was nie suksesvol nie. 995 00:48:48,020 --> 00:48:51,010 So, enigiemand enige idees oor wat ons nodig het om te doen dit op te los? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Ek gaan om te wag totdat ek sien 'n paar hande optrek. 998 00:48:57,570 --> 00:48:58,830 Ons het nie uit te voer nie. 999 00:48:58,830 --> 00:49:01,660 Hou in gedagte, dit was die eerste ding wat ons doen. 1000 00:49:01,660 --> 00:49:02,430 Ek gaan nie 'n paar om te doen. 1001 00:49:02,430 --> 00:49:03,670 Ek gaan 'n paar om te doen. 1002 00:49:03,670 --> 00:49:04,830 Omdat 'n paar beteken twee. 1003 00:49:04,830 --> 00:49:07,620 Ek sal wag vir meer as twee. 1004 00:49:07,620 --> 00:49:10,690 >> Die eerste plasing, Kur, by verstek gelyk aan nul. 1005 00:49:10,690 --> 00:49:14,050 En dit loop net voer As Kur is nie null. 1006 00:49:14,050 --> 00:49:18,740 So hoe kan ek kry om dit? 1007 00:49:18,740 --> 00:49:19,990 Ek sien drie hande. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Ek sal wag vir meer as drie. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, wat dink jy? 1012 00:49:35,940 --> 00:49:37,730 >> Publiek: Wel, as jy nodig het om dit te voer meer as een keer, jy het net 1013 00:49:37,730 --> 00:49:39,948 verander dit na 'n do-while lus. 1014 00:49:39,948 --> 00:49:41,250 >> JASON Hirsch: OK. 1015 00:49:41,250 --> 00:49:44,240 Sal dit los ons probleem, al is? 1016 00:49:44,240 --> 00:49:47,750 >> Publiek: In hierdie geval nie as gevolg van die feit dat die lys is leeg. 1017 00:49:47,750 --> 00:49:52,150 So dan is jy waarskynlik net nodig om by te voeg 'n verklaring dat indien die lus uitgange 1018 00:49:52,150 --> 00:49:55,312 dan moet jy aan die einde van die lys, op watter punt jy 1019 00:49:55,312 --> 00:49:56,562 kan net plaas dit. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON Hirsch: Ek hou daarvan. 1022 00:49:59,680 --> 00:50:00,500 Dit maak sin. 1023 00:50:00,500 --> 00:50:03,390 As die lus verlaat - 1024 00:50:03,390 --> 00:50:04,800 want dit sal terugkeer valse hier. 1025 00:50:04,800 --> 00:50:08,220 Dus, as die lus uitgange, dan is ons op die einde van die lys, of dalk die 1026 00:50:08,220 --> 00:50:10,690 die begin van 'n lys indien daar is niks in dit, wat dieselfde is as die einde. 1027 00:50:10,690 --> 00:50:12,770 So nou wil ons in te voeg iets hier. 1028 00:50:12,770 --> 00:50:17,380 So hoe die kode kyk, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> Publiek: As jy reeds 'die knoop malloced, kan jy net sê 1030 00:50:21,600 --> 00:50:25,400 new_node-> langs gelyk aan nul, omdat dit het tot aan die einde. 1031 00:50:25,400 --> 00:50:27,510 Of new_node-> langs gelyk aan nul. 1032 00:50:27,510 --> 00:50:27,765 >> JASON Hirsch: OK. 1033 00:50:27,765 --> 00:50:28,190 Jammer. 1034 00:50:28,190 --> 00:50:35,760 New_node-> langs gelyk aan nul want ons is aan die einde. 1035 00:50:35,760 --> 00:50:36,460 Dit beteken nie sit dit in 1036 00:50:36,460 --> 00:50:37,710 Hoe kan ons dit in die lys? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Right. 1039 00:50:46,460 --> 00:50:47,750 Dit is net die opstel van dit gelyk aan. 1040 00:50:47,750 --> 00:50:50,940 Nee Hoe doen ons eintlik sit dit in die lys? 1041 00:50:50,940 --> 00:50:54,170 Wat is verwys na die einde van die lys? 1042 00:50:54,170 --> 00:50:56,090 >> Publiek: Hoof. 1043 00:50:56,090 --> 00:50:57,566 >> JASON Hirsch: Jammer? 1044 00:50:57,566 --> 00:50:59,440 >> Publiek: Hoof wys aan die einde van die lys. 1045 00:50:59,440 --> 00:51:01,480 >> JASON Hirsch: As daar is niks in die lys, is die hoof te wys op die 1046 00:51:01,480 --> 00:51:04,170 einde van die lys. 1047 00:51:04,170 --> 00:51:06,920 So dit sal werk vir die Eerste plasing. 1048 00:51:06,920 --> 00:51:09,810 Wat van as daar is 'n paar dinge in die lys? 1049 00:51:09,810 --> 00:51:12,470 As ons wil nie te stel kop gelyk aan new_node. 1050 00:51:12,470 --> 00:51:13,790 Wat wil ons doen? 1051 00:51:13,790 --> 00:51:15,610 Ja? 1052 00:51:15,610 --> 00:51:16,860 Waarskynlik vorige. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Sal dit werk? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Onthou dat die vorige is net 'n verwysing na 'n knoop. 1057 00:51:33,050 --> 00:51:34,770 En die vorige is 'n plaaslike veranderlike. 1058 00:51:34,770 --> 00:51:38,080 So hierdie lyn sal 'n plaaslike veranderlike, vorige, gelyk aan of 1059 00:51:38,080 --> 00:51:39,380 wys na die nuwe knoop. 1060 00:51:39,380 --> 00:51:41,500 Dit sal eintlik nie sit dit in ons lys, al is. 1061 00:51:41,500 --> 00:51:44,330 Hoe kan ons dit in ons lys? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> Publiek: Ek dink jy Moenie huidige-> volgende. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON Hirsch: OK. 1066 00:51:52,550 --> 00:51:54,010 Kur-> volgende. 1067 00:51:54,010 --> 00:51:58,768 So weer, die enigste rede waarom ons af hier is, wat beteken huidige gelyk? 1068 00:51:58,768 --> 00:51:59,760 >> Publiek: Is gelyk aan nul. 1069 00:51:59,760 --> 00:52:01,790 >> JASON Hirsch: En ja, wat gebeur as ons dit doen nul-> volgende? 1070 00:52:01,790 --> 00:52:02,810 Wat gaan ons doen te kry? 1071 00:52:02,810 --> 00:52:04,060 Ons sal 'n segmentering skuld. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> Publiek: Do Kur gelyk aan nul. 1074 00:52:08,880 --> 00:52:10,760 >> JASON Hirsch: Dit is dieselfde ding as vorige, al is, want daar is 1075 00:52:10,760 --> 00:52:12,820 'n plaaslike veranderlike ons die opstel gelyk aan die nuwe knoop. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Kom ons gaan terug na ons foto van die plaas iets. 1078 00:52:20,920 --> 00:52:25,500 Sê ons inbring teen die einde van die lys, so reg hier. 1079 00:52:25,500 --> 00:52:30,010 Ons het 'n huidige wyser wat wys na nul en 'n vorige punt 1080 00:52:30,010 --> 00:52:32,800 dit is wys om 8. 1081 00:52:32,800 --> 00:52:35,330 So wat doen ons nodig het om te werk, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> Publiek: Vorige-> volgende? 1083 00:52:36,680 --> 00:52:41,980 >> JASON Hirsch: Vorige-> volgende is wat ons wil om te werk, want dit 1084 00:52:41,980 --> 00:52:44,960 eintlik plaas dit op die einde van die lys. 1085 00:52:44,960 --> 00:52:47,220 Ons het nog 'n fout, al is, dat ons gaan om te loop in. 1086 00:52:47,220 --> 00:52:50,090 Wat is dat die fout? 1087 00:52:50,090 --> 00:52:50,790 Ja? 1088 00:52:50,790 --> 00:52:53,860 >> Publiek: Dit gaan om terug te keer valse in hierdie geval? 1089 00:52:53,860 --> 00:52:56,380 >> JASON Hirsch: O, is word gaan valse om terug te keer. 1090 00:52:56,380 --> 00:52:57,430 Maar daar is nog 'n fout. 1091 00:52:57,430 --> 00:52:58,930 So ons sal moet sit in ruil waar. 1092 00:52:58,930 --> 00:53:01,370 >> Publiek: vorige steeds gelyk Maak nul aan die bokant van die lys? 1093 00:53:01,370 --> 00:53:03,645 >> JASON Hirsch: So vorige steeds gelyk aan nul aan die begin. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 So, hoe kan ons oor dit? 1096 00:53:10,440 --> 00:53:10,950 Ja? 1097 00:53:10,950 --> 00:53:15,280 >> Publiek: Ek dink jy kan 'n tjek te doen voor die tyd loop om te sien of dit is 1098 00:53:15,280 --> 00:53:16,610 'n leë lys. 1099 00:53:16,610 --> 00:53:17,000 >> JASON Hirsch: OK. 1100 00:53:17,000 --> 00:53:17,710 So laat ons gaan hier. 1101 00:53:17,710 --> 00:53:18,530 Doen 'n tjek. 1102 00:53:18,530 --> 00:53:19,380 Indien - 1103 00:53:19,380 --> 00:53:20,770 >> Publiek: So as hoof gelyk is gelyk aan nul. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON Hirsch: As hoof gelyk is gelyk aan nul - 1106 00:53:26,320 --> 00:53:27,790 wat sal ons sê of dit is 'n leë lys. 1107 00:53:27,790 --> 00:53:31,090 >> Publiek: En dan is jy doen hoof gelyk aan nuwe. 1108 00:53:31,090 --> 00:53:34,740 >> JASON Hirsch: Hoof gelyk new_node? 1109 00:53:34,740 --> 00:53:35,730 En wat anders moet ons doen? 1110 00:53:35,730 --> 00:53:37,020 >> Publiek: En dan is jy terug waar. 1111 00:53:37,020 --> 00:53:37,535 >> JASON Hirsch: Nie heeltemal nie. 1112 00:53:37,535 --> 00:53:38,785 Ons ontbreek een stap. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> Publiek: New_node volgende het om aan te dui null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON Hirsch: Presies, Alden. 1116 00:53:44,570 --> 00:53:46,600 En dan kan ons terug waar. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 Maar dit is nog steeds 'n goeie idee om dinge te doen aan die einde van die lys, reg? 1119 00:53:51,630 --> 00:53:51,950 Alle regte. 1120 00:53:51,950 --> 00:53:54,450 Ons het nog steeds kan kry eintlik aan die einde van die lys. 1121 00:53:54,450 --> 00:53:57,870 So is hierdie kode fyn as ons by die einde van die lys en daar is 'n paar 1122 00:53:57,870 --> 00:53:59,120 dinge in die lys? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Reg? 1125 00:54:02,040 --> 00:54:03,540 Omdat ons nog Marcus se idee. 1126 00:54:03,540 --> 00:54:06,870 Ons kan dit loop verlaat omdat ons is aan die einde van die lys. 1127 00:54:06,870 --> 00:54:09,308 So het ons nog wil hierdie kodeer hier? 1128 00:54:09,308 --> 00:54:10,520 >> Gehoor: Ja. 1129 00:54:10,520 --> 00:54:11,000 >> JASON Hirsch: Ja. 1130 00:54:11,000 --> 00:54:14,190 En wat moet ons dit te verander? 1131 00:54:14,190 --> 00:54:15,440 Waar. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Klink goed vir almal so ver? 1134 00:54:21,640 --> 00:54:22,420 Enigiemand enige - 1135 00:54:22,420 --> 00:54:23,480 Avi, het jy iets om by te voeg? 1136 00:54:23,480 --> 00:54:23,920 >> Publiek: No 1137 00:54:23,920 --> 00:54:25,276 >> JASON Hirsch: OK. 1138 00:54:25,276 --> 00:54:27,010 Dus het ons het 'n paar veranderinge. 1139 00:54:27,010 --> 00:54:29,540 Ons het die tjek gemaak voordat ons het in 'n leë lys. 1140 00:54:29,540 --> 00:54:31,790 So het ons sorg geneem het van 'n leë lys. 1141 00:54:31,790 --> 00:54:35,500 En hier is ons het sorg van die plaas iets aan die einde van die lys. 1142 00:54:35,500 --> 00:54:38,930 So lyk dit soos hierdie, terwyl lus neem sorg van die dinge in tussen, 1143 00:54:38,930 --> 00:54:41,920 iewers in die lys as daar is dinge in die lys. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Laat ons hierdie program weer. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Nie suksesvol nie. 1148 00:54:50,755 --> 00:54:52,190 >> Publiek: Jy het dit nie. 1149 00:54:52,190 --> 00:54:53,940 >> JASON Hirsch: Ag, Ek het dit nie. 1150 00:54:53,940 --> 00:54:56,250 Goeie punt, Michael. 1151 00:54:56,250 --> 00:54:57,500 Kom ons voeg 'n make gekoppel. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Line 87 is daar 'n fout. 1154 00:55:04,830 --> 00:55:05,420 Line 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, dit was die lyn wat jy my gegee het. 1156 00:55:06,600 --> 00:55:08,962 Wat is verkeerd? 1157 00:55:08,962 --> 00:55:10,710 >> Publiek: Dit het te wees van nul. 1158 00:55:10,710 --> 00:55:11,000 >> JASON Hirsch: Uitstekende. 1159 00:55:11,000 --> 00:55:11,630 Presies reg. 1160 00:55:11,630 --> 00:55:13,290 Dit moet nul wees. 1161 00:55:13,290 --> 00:55:15,210 Kom ons maak weer. 1162 00:55:15,210 --> 00:55:17,220 Stel. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Kom ons voeg drie. 1165 00:55:19,400 --> 00:55:20,570 Die insetsel was suksesvol. 1166 00:55:20,570 --> 00:55:21,660 Kom ons druk dit uit. 1167 00:55:21,660 --> 00:55:23,590 Ag, as ons maar net kon gaan. 1168 00:55:23,590 --> 00:55:25,500 Maar ons het nie gedoen word om die druk funksie nie. 1169 00:55:25,500 --> 00:55:27,840 Kom ons tree iets anders. 1170 00:55:27,840 --> 00:55:29,090 Wat moet ons in? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> Publiek: Sewe. 1173 00:55:31,940 --> 00:55:33,340 >> JASON Hirsch: Sewe? 1174 00:55:33,340 --> 00:55:34,590 >> Gehoor: Ja. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON Hirsch: Ons het 'n seg skuld. 1177 00:55:39,780 --> 00:55:43,760 So het ons een nie, maar ons kan duidelik kan nie twee. 1178 00:55:43,760 --> 00:55:45,690 Dit is 05:07. 1179 00:55:45,690 --> 00:55:48,370 Sodat ons kan ontfout hierdie vir drie minute. 1180 00:55:48,370 --> 00:55:51,240 Maar Ek gaan vir ons om hier te verlaat en skuif op tafels te hash. 1181 00:55:51,240 --> 00:55:54,290 Maar weereens, die antwoorde vir hierdie kode Ek sal dit per e-pos aan jou in 'n bietjie. 1182 00:55:54,290 --> 00:55:55,440 Ons is baie naby aan dit. 1183 00:55:55,440 --> 00:55:58,300 Ek raai u aan om uit te vind wat gaan hier aan en dit reg te stel. 1184 00:55:58,300 --> 00:56:02,400 So ek sal e-pos wat jy hierdie kode as goed plus die oplossing - 1185 00:56:02,400 --> 00:56:03,670 waarskynlik die oplossing later. 1186 00:56:03,670 --> 00:56:05,110 Eerste hierdie kode. 1187 00:56:05,110 --> 00:56:08,290 >> Die ander ding wat ek wil doen voordat ons afwerking is ons niks bevry. 1188 00:56:08,290 --> 00:56:10,370 So ek wil om te wys wat valgrind lyk. 1189 00:56:10,370 --> 00:56:14,310 As ons hardloop valgrind grense op ons program. / gekoppel. 1190 00:56:14,310 --> 00:56:22,540 Weereens, volgens hierdie skuif, het ons moet valgrind hardloop met 'n soort van 1191 00:56:22,540 --> 00:56:26,410 opsie, in hierdie geval - Lek-check = vol. 1192 00:56:26,410 --> 00:56:27,660 So laat skryf valgrind - Lek-check = vol. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 So dit sal loop valgrind op ons program. 1195 00:56:35,080 --> 00:56:37,000 En nou het die program loop eintlik. 1196 00:56:37,000 --> 00:56:40,190 So ons gaan om dit te doen, net soos voor, sit iets in 1197 00:56:40,190 --> 00:56:40,830 Ek gaan sit in drie. 1198 00:56:40,830 --> 00:56:41,790 Dit werk. 1199 00:56:41,790 --> 00:56:43,202 Ek gaan nie om te probeer om te sit in iets anders, want ons gaan 1200 00:56:43,202 --> 00:56:44,710 'n seg valse in daardie geval. 1201 00:56:44,710 --> 00:56:46,700 So ek gaan net om op te hou. 1202 00:56:46,700 --> 00:56:50,160 >> En nou sien jy hier lek en hoop opsomming. 1203 00:56:50,160 --> 00:56:52,310 Dit is die goeie dinge wat jy wil om te kyk na. 1204 00:56:52,310 --> 00:56:56,780 So het die hoop opsomming - dit sê, in gebruik uitgang - agt grepe in een blok. 1205 00:56:56,780 --> 00:56:58,370 Dat een blok is die node ons malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, jy het gesê voor 'n knoop is agt byt, want dit het die heelgetal 1207 00:57:02,230 --> 00:57:02,680 en die wyser. 1208 00:57:02,680 --> 00:57:04,550 So dit is ons node. 1209 00:57:04,550 --> 00:57:08,170 En dan sê dit wat ons gebruik malloc sewe keer en ons bevry 1210 00:57:08,170 --> 00:57:08,940 iets ses keer. 1211 00:57:08,940 --> 00:57:13,680 Maar ons nooit vry genoem, so ek het geen idee wat dit praat. 1212 00:57:13,680 --> 00:57:18,490 >> Maar is dit voldoende om te sê dat wanneer jou program lopies, is malloc genoem 1213 00:57:18,490 --> 00:57:20,330 in 'n paar ander plekke wat ons hoef nie te bekommer nie. 1214 00:57:20,330 --> 00:57:22,460 So malloc is waarskynlik genoem in sommige plekke. 1215 00:57:22,460 --> 00:57:24,480 Ons hoef nie bekommerd wees oor waar. 1216 00:57:24,480 --> 00:57:26,240 Maar dit is regtig ons. 1217 00:57:26,240 --> 00:57:27,380 Die eerste reël is ons. 1218 00:57:27,380 --> 00:57:28,320 Ons het daardie blok. 1219 00:57:28,320 --> 00:57:30,330 En jy kan sien dat hier in die lek opsomming. 1220 00:57:30,330 --> 00:57:31,950 Nog beskikbaar - 1221 00:57:31,950 --> 00:57:32,930 agt grepe in een blok. 1222 00:57:32,930 --> 00:57:34,100 Dit beteken dat die geheue - 1223 00:57:34,100 --> 00:57:35,730 Ons het uitgelek dat die geheue. 1224 00:57:35,730 --> 00:57:37,570 Beslis verloor - 1225 00:57:37,570 --> 00:57:38,770 iets is verlore vir die goeie. 1226 00:57:38,770 --> 00:57:40,590 Die algemeen, sal jy nie sien nie daar nie. 1227 00:57:40,590 --> 00:57:44,780 Nog beskikbaar is oor die algemeen waar sal jy sien dinge, waar jy wil 1228 00:57:44,780 --> 00:57:48,900 om te kyk om te sien wat kode wat jy moet het bevry, maar jy het vergeet om te bevry. 1229 00:57:48,900 --> 00:57:53,170 >> En dan as dit nie die geval was, As ons het vrye alles, 1230 00:57:53,170 --> 00:57:54,360 ons kan seker maak dat. 1231 00:57:54,360 --> 00:57:57,330 Laat ons net die program nie om in enigiets. 1232 00:57:57,330 --> 00:57:59,800 Jy sal sien hier in gebruik by die uitgang - 1233 00:57:59,800 --> 00:58:01,310 nul grepe in nul blokke. 1234 00:58:01,310 --> 00:58:06,310 Dit beteken dat ons het niks oorgehad wanneer hierdie program opgewonde. 1235 00:58:06,310 --> 00:58:12,090 So voor die draai in pset6, hardloop valgrind en maak seker jy het nie 1236 00:58:12,090 --> 00:58:15,310 enige geheue lekkasies in jou program. 1237 00:58:15,310 --> 00:58:17,910 As jy enige vrae het met valgrind, voel vry om uit te reik. 1238 00:58:17,910 --> 00:58:18,700 Maar dit is hoe jy dit gebruik. 1239 00:58:18,700 --> 00:58:20,890 Baie eenvoudig - kyk of jy het in gebruik by die uitgang - 1240 00:58:20,890 --> 00:58:22,270 enige grepe in enige blokke. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> So het ons gewerk het op insetsel knoop. 1243 00:58:29,580 --> 00:58:33,840 Ek het twee ander funksies hier - druk nodes en vrye nodes. 1244 00:58:33,840 --> 00:58:37,780 Weereens, dit is funksies wat goed gaan wees vir jou om te oefen 1245 00:58:37,780 --> 00:58:40,990 want hulle sal jou help om nie net met hierdie monster oefeninge, maar ook 1246 00:58:40,990 --> 00:58:42,180 op die probleem gestel. 1247 00:58:42,180 --> 00:58:44,230 Hulle kaart op nou mooi dinge jy gaan hê om te doen in die 1248 00:58:44,230 --> 00:58:45,010 probleem stel. 1249 00:58:45,010 --> 00:58:47,640 Maar ek wil om seker te maak raak ons ​​aan alles. 1250 00:58:47,640 --> 00:58:50,400 En hash tabelle is ook belangrik om te wat ons doen in artikel hierdie 1251 00:58:50,400 --> 00:58:51,980 week - of in die probleem stel. 1252 00:58:51,980 --> 00:58:55,200 >> So ons gaan die artikel te voltooi praat oor hash tabelle. 1253 00:58:55,200 --> 00:58:58,140 As jy sien ek 'n bietjie hash tafel. 1254 00:58:58,140 --> 00:59:00,020 Dit is nie wat ons praat oor, egter. 1255 00:59:00,020 --> 00:59:03,540 Ons praat oor 'n ander tipe hash tabelle. 1256 00:59:03,540 --> 00:59:07,300 En in sy kern, 'n hash tafel is niks meer as 'n 1257 00:59:07,300 --> 00:59:08,860 verskeidenheid plus 'n hash funksie. 1258 00:59:08,860 --> 00:59:11,150 Ons gaan om te praat vir 'n bietjie net om te maak seker dat almal verstaan ​​wat 'n 1259 00:59:11,150 --> 00:59:12,110 hash funksie is. 1260 00:59:12,110 --> 00:59:15,420 En ek vertel jou nou dat dit niks meer as twee dinge - 1261 00:59:15,420 --> 00:59:18,590 'n skikking en 'n hash funksie. 1262 00:59:18,590 --> 00:59:20,716 En hier is die stappe deur wat hierdie bedryf. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Daar is ons verskeidenheid. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Daar is ons funksie. 1267 00:59:39,460 --> 00:59:43,180 In die besonder, hash funksies nodig het om te doen 'n paar van die dinge wat met hierdie. 1268 00:59:43,180 --> 00:59:45,040 Ek gaan spesifiek praat oor hierdie probleem stel. 1269 00:59:45,040 --> 00:59:46,450 Dit is waarskynlik gaan om te neem in 'n string. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 En wat gaan dit om terug te keer? 1272 00:59:51,770 --> 00:59:52,640 Watter tipe data? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Jou hash funksie terugkeer? 1275 00:59:55,760 --> 00:59:58,760 'N heelgetal. 1276 00:59:58,760 --> 01:00:01,700 So dit is wat die hash tabel bestaan ​​uit - 1277 01:00:01,700 --> 01:00:05,430 'n tafel in die vorm van 'n skikking en 'n hash funksie. 1278 01:00:05,430 --> 01:00:06,010 Hoe werk dit? 1279 01:00:06,010 --> 01:00:07,300 Dit werk in drie stappe. 1280 01:00:07,300 --> 01:00:08,740 Ons gee dit 'n sleutel. 1281 01:00:08,740 --> 01:00:11,470 In hierdie geval, sal ons gee dit 'n string. 1282 01:00:11,470 --> 01:00:18,140 Ons noem die hash funksie per stap een op die sleutel en ons kry 'n waarde. 1283 01:00:18,140 --> 01:00:20,310 >> Spesifiek, sal ons sê kry ons 'n heelgetal. 1284 01:00:20,310 --> 01:00:25,630 Dit heelgetal is, is daar baie spesifieke grense aan wat daardie heelgetal wees. 1285 01:00:25,630 --> 01:00:28,880 In hierdie voorbeeld, ons verskeidenheid is van die grootte drie. 1286 01:00:28,880 --> 01:00:32,330 So, wat getalle kan daardie getal is. 1287 01:00:32,330 --> 01:00:35,970 Wat is die omvang van geldige waardes vir dat heelgetal, die terugkeer van hierdie soort 1288 01:00:35,970 --> 01:00:37,220 hash funksie? 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 Die punt van die hash funksie is om te uit te vind die plek in die skikking 1292 01:00:46,060 --> 01:00:47,790 waar ons die sleutel gaan. 1293 01:00:47,790 --> 01:00:51,290 Daar is slegs drie moontlike plekke hier - 1294 01:00:51,290 --> 01:00:52,130 nul, een, of twee. 1295 01:00:52,130 --> 01:00:55,360 So hierdie funksie beter opbrengs nul, een, of twee. 1296 01:00:55,360 --> 01:00:58,740 Sommige geldig indice in hierdie reeks. 1297 01:00:58,740 --> 01:01:02,770 >> En dan, afhangende van waar dit terugkeer, jy kan sien daar verskeidenheid oop 1298 01:01:02,770 --> 01:01:03,730 in hakies die waarde. 1299 01:01:03,730 --> 01:01:05,800 Dit is waar ons die sleutel. 1300 01:01:05,800 --> 01:01:11,280 So ons gooi in die pampoen, ons uit nul. 1301 01:01:11,280 --> 01:01:15,540 Op verskeidenheid bracket 0, ons sit pampoen. 1302 01:01:15,540 --> 01:01:21,070 Ons gooi in katte, ons kry een. 1303 01:01:21,070 --> 01:01:24,110 Ons het die kat aan die een. 1304 01:01:24,110 --> 01:01:25,480 Ons sit in spin. 1305 01:01:25,480 --> 01:01:26,710 Ons kry twee. 1306 01:01:26,710 --> 01:01:30,200 Ons sit spin op verskeidenheid bracket twee. 1307 01:01:30,200 --> 01:01:32,300 Dit sou so lekker wees as dit het gewerk soos dit. 1308 01:01:32,300 --> 01:01:35,570 Maar helaas, soos ons sal sien, dit is 'n bietjie meer ingewikkeld. 1309 01:01:35,570 --> 01:01:37,570 >> Voordat ons daar enige vrae oor hierdie basiese 1310 01:01:37,570 --> 01:01:38,820 opstel van 'n hash tafel? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 Dit is 'n beeld van presies wat ons het op die bord. 1313 01:01:51,940 --> 01:01:55,420 Maar omdat ons getrek het dit op die raad, ek gaan nie te gaan in dit verder. 1314 01:01:55,420 --> 01:02:00,430 In wese sleutels, die magic black box - of in hierdie geval, teal box - van 'n 1315 01:02:00,430 --> 01:02:02,410 hash funksie sit hulle in emmers. 1316 01:02:02,410 --> 01:02:04,690 En in hierdie voorbeeld ons nie om die naam. 1317 01:02:04,690 --> 01:02:07,880 Ons is besig om die verband selfoon nommer van die naam in die emmer. 1318 01:02:07,880 --> 01:02:10,430 Maar jy kan baie goed net het die naam in die emmer. 1319 01:02:10,430 --> 01:02:12,950 >> Dit is net 'n prentjie van wat Ons het op die bord. 1320 01:02:12,950 --> 01:02:14,460 Ons het slaggate, al is. 1321 01:02:14,460 --> 01:02:17,470 En daar is twee in die besonder skyfies wat ek wil om te gaan. 1322 01:02:17,470 --> 01:02:20,230 Die eerste een is oor die 'n hash funksie. 1323 01:02:20,230 --> 01:02:22,620 So ek vra die vraag, wat maak 'n goeie hash funksie? 1324 01:02:22,620 --> 01:02:24,220 Ek gee twee antwoorde. 1325 01:02:24,220 --> 01:02:26,630 Die eerste is dat dit deterministies. 1326 01:02:26,630 --> 01:02:29,660 In die konteks van hash funksies, wat beteken 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: Dit kan die indeks in konstante tyd? 1330 01:02:42,850 --> 01:02:43,810 >> JASON Hirsch: Dit is nie wat dit beteken nie. 1331 01:02:43,810 --> 01:02:44,725 Maar dit is 'n goeie raaiskoot. 1332 01:02:44,725 --> 01:02:46,100 Enigiemand anders het 'n raaiskoot na wat dit beteken? 1333 01:02:46,100 --> 01:02:47,780 Dat 'n goeie hash funksie is deterministiese? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> Publiek: dat 'n belangrike net gekarteer kan word op een plek in die hash tafel. 1336 01:02:51,680 --> 01:02:53,070 >> JASON Hirsch: Dis presies reg. 1337 01:02:53,070 --> 01:02:57,430 Elke keer as jy in die pampoen, dit is altyd terug nul. 1338 01:02:57,430 --> 01:03:01,660 As jy in die pampoen en jou hash funksie gee terug nul, maar het 'n 1339 01:03:01,660 --> 01:03:06,060 waarskynlikheid van die terugkeer van iets anders groter as nul - 1340 01:03:06,060 --> 01:03:09,280 so miskien kan dit weer een soms of twee ander tye - 1341 01:03:09,280 --> 01:03:11,100 dit is nie 'n goeie hash funksie. 1342 01:03:11,100 --> 01:03:11,800 Jy is presies reg. 1343 01:03:11,800 --> 01:03:15,680 Jou hash funksie moet terugkeer om die presies dieselfde getal, in hierdie geval, vir 1344 01:03:15,680 --> 01:03:17,780 presies dieselfde string. 1345 01:03:17,780 --> 01:03:22,210 >> Miskien is dit terug presies dieselfde heelgetal vir presies dieselfde string 1346 01:03:22,210 --> 01:03:24,430 ongeag van hoofletters. 1347 01:03:24,430 --> 01:03:27,980 Maar in daardie geval is dit steeds deterministiese omdat verskeie dinge 1348 01:03:27,980 --> 01:03:29,350 is gekarteer op die dieselfde waarde. 1349 01:03:29,350 --> 01:03:30,170 Dit is fyn. 1350 01:03:30,170 --> 01:03:32,615 Solank as wat daar is net een uitset vir 'n gegewe insette. 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 Die tweede ding is dat dit terugkeer geldig indekse. 1354 01:03:38,340 --> 01:03:40,220 Ons het tot wat vroeër. 1355 01:03:40,220 --> 01:03:41,860 Dit hash funksie - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 'n hash funksie moet terugkeer geldig indekse. 1358 01:03:46,840 --> 01:03:47,740 So sê - 1359 01:03:47,740 --> 01:03:48,990 laat se terug na hierdie voorbeeld gaan. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 My hash funksie tel tot die letters in die woord. 1362 01:03:57,540 --> 01:03:58,380 Dit is die hash funksie. 1363 01:03:58,380 --> 01:03:59,740 En opbrengste wat heelgetal. 1364 01:03:59,740 --> 01:04:04,280 So as ek die woord A, dit is gaan een om terug te keer. 1365 01:04:04,280 --> 01:04:06,900 En dit gaan 'n reg te stel hier. 1366 01:04:06,900 --> 01:04:09,430 Wat as ek in die woord kolf? 1367 01:04:09,430 --> 01:04:11,310 Dit gaan om terug te keer drie. 1368 01:04:11,310 --> 01:04:12,560 Waar kom kolf gaan? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> Dit pas nie. 1371 01:04:19,750 --> 01:04:21,000 Maar dit moet iewers te gaan. 1372 01:04:21,000 --> 01:04:23,340 Dit is my hash tafel na alles, en alles moet iewers te gaan. 1373 01:04:23,340 --> 01:04:24,590 So waar moet kolf gaan? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Enige gedagtes? 1376 01:04:28,710 --> 01:04:29,450 Raai? 1377 01:04:29,450 --> 01:04:30,280 Goeie raai? 1378 01:04:30,280 --> 01:04:31,220 >> Publiek: Zero. 1379 01:04:31,220 --> 01:04:32,120 >> JASON Hirsch: Hoekom nul? 1380 01:04:32,120 --> 01:04:35,990 >> Publiek: Omdat drie modulo drie nul? 1381 01:04:35,990 --> 01:04:38,620 >> JASON Hirsch: Drie modulo drie is nul. 1382 01:04:38,620 --> 01:04:40,810 Dit is 'n groot raaiskoot, en dat die inligting korrek is. 1383 01:04:40,810 --> 01:04:43,870 So in hierdie geval is dit moet waarskynlik gaan op nul. 1384 01:04:43,870 --> 01:04:51,080 So 'n goeie manier om te verseker dat hierdie hash funksie gee slegs geldig indekse word 1385 01:04:51,080 --> 01:04:54,580 om dit te modulo deur die grootte van die tafel. 1386 01:04:54,580 --> 01:04:57,360 As jy modulo net hierdie opgawes deur drie, gaan jy altyd te kry 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 as dit altyd terug sewe en jy altyd modulo deur drie, is jy 1389 01:05:05,160 --> 01:05:06,030 altyd dieselfde ding te kry. 1390 01:05:06,030 --> 01:05:09,270 >> So dit is nog steeds deterministiese As jy modulo. 1391 01:05:09,270 --> 01:05:11,420 Maar wat sal verseker dat jy nooit iets kry - 1392 01:05:11,420 --> 01:05:12,940 'n ongeldig bedryf. 1393 01:05:12,940 --> 01:05:16,840 Die algemeen, wat moet gebeur modulo binne-in jou hash funksie. 1394 01:05:16,840 --> 01:05:18,240 So jy hoef nie te bekommerd oor hierdie. 1395 01:05:18,240 --> 01:05:20,555 Jy kan net verseker dat dit is 'n geldige indice. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Enige vrae oor hierdie potensiële slaggat? 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 ons. 1401 01:05:40,290 --> 01:05:42,890 Volgende potensiële slaggat, en dit is die groot een. 1402 01:05:42,890 --> 01:05:46,880 Wat as twee sleutels kaart dieselfde waarde? 1403 01:05:46,880 --> 01:05:49,350 So is daar twee maniere om dit te hanteer. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 Die eerste een is lineêr genoem indringende, wat ek 1406 01:05:56,020 --> 01:05:57,300 gaan nie oor te gaan. 1407 01:05:57,300 --> 01:06:01,120 Maar jy moet vertroud wees met hoe wat werk en wat dit is. 1408 01:06:01,120 --> 01:06:05,610 >> Die tweede een gaan ek om oor te gaan want dit is die een wat baie 1409 01:06:05,610 --> 01:06:08,290 mense sal waarskynlik uiteindelik besluit te gebruik in hul probleem stel. 1410 01:06:08,290 --> 01:06:09,820 Natuurlik, jy hoef nie. 1411 01:06:09,820 --> 01:06:15,280 Maar vir die probleem stel, baie mense geneig om te kies 'n hash tafel te skep 1412 01:06:15,280 --> 01:06:17,950 met aparte aaneenskakeling te implementeer hul woordeboek. 1413 01:06:17,950 --> 01:06:21,390 So ons gaan om te gaan oor wat dit beteken 'n gemors tafel te skep met 1414 01:06:21,390 --> 01:06:23,890 afsonderlike aaneenskakeling. 1415 01:06:23,890 --> 01:06:26,260 >> So het ek in die pampoen. 1416 01:06:26,260 --> 01:06:29,560 Dit gee nul. 1417 01:06:29,560 --> 01:06:31,410 En ek sit hier pampoen. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Toe ek in die - 1420 01:06:37,930 --> 01:06:39,922 Wat is 'n ander Halloween-tema ding? 1421 01:06:39,922 --> 01:06:42,200 >> Publiek: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON Hirsch: Candy! 1423 01:06:42,770 --> 01:06:43,910 Dit is 'n groot een. 1424 01:06:43,910 --> 01:06:47,760 Ek het in lekkergoed, en lekkergoed gee my ook nul. 1425 01:06:47,760 --> 01:06:49,350 Wat moet ek doen? 1426 01:06:49,350 --> 01:06:51,940 Enige idees? 1427 01:06:51,940 --> 01:06:53,940 Omdat jy al die soort van weet wat afsonderlike aaneenskakeling is. 1428 01:06:53,940 --> 01:06:55,190 So enige idees wat om te doen? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Ja. 1431 01:06:59,110 --> 01:07:03,810 >> Publiek: Om die string eintlik in die hash tafel. 1432 01:07:03,810 --> 01:07:08,910 >> JASON Hirsch: So ons gaan teken die goeie idee hier. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> Publiek: Het die hashtable [Onhoorbaar] 1435 01:07:12,290 --> 01:07:16,640 die wyser wat verwys na die begin van 'n lys. 1436 01:07:16,640 --> 01:07:20,930 En dan het die pampoen die eerste waarde in wat gekoppel lys en lekkergoed 1437 01:07:20,930 --> 01:07:22,800 die tweede waarde wat gekoppel lys. 1438 01:07:22,800 --> 01:07:23,420 >> JASON Hirsch: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, wat was uitstaande. 1440 01:07:24,670 --> 01:07:26,160 Ek is van plan om dit af te breek. 1441 01:07:26,160 --> 01:07:28,890 Marcus sê nie oorskryf pampoen. 1442 01:07:28,890 --> 01:07:30,660 Dit sou sleg wees. 1443 01:07:30,660 --> 01:07:33,640 Moenie lekkergoed iewers anders. 1444 01:07:33,640 --> 01:07:35,390 Ons gaan hulle te sit sowel by nul. 1445 01:07:35,390 --> 01:07:37,770 Maar ons gaan om te gaan met om hulle by zero deur 1446 01:07:37,770 --> 01:07:39,395 skep 'n lys op nul. 1447 01:07:39,395 --> 01:07:42,430 En ons gaan 'n lys van te skep alles wat gekarteer is aan nul. 1448 01:07:42,430 --> 01:07:47,960 En die beste manier waarop ons geleer het om te skep 'n lys wat kan groei en krimp 1449 01:07:47,960 --> 01:07:49,840 dinamies is nie binne 'n ander skikking. 1450 01:07:49,840 --> 01:07:51,510 So nie 'n multi-dimensionele skikking. 1451 01:07:51,510 --> 01:07:54,080 Maar om net 'n geskakelde lys. 1452 01:07:54,080 --> 01:07:55,330 >> So, wat hy voorgestel het - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Ek gaan 'n nuwe te kry - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 is die skep van 'n skikking met wysers, 'n verskeidenheid van wysers. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Enige idee of wenk wat die tipe van hierdie wenke moet wees? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> Publiek: Pointers - 1461 01:08:27,250 --> 01:08:28,609 >> JASON Hirsch: Omdat jy het gesê 'n geskakelde lys, so - 1462 01:08:28,609 --> 01:08:29,520 >> Publiek: Node riglyne? 1463 01:08:29,520 --> 01:08:30,670 >> JASON Hirsch: Node wysers. 1464 01:08:30,670 --> 01:08:32,830 As die dinge in ons verbind lys is nodes dan is hulle 1465 01:08:32,830 --> 01:08:34,370 moet knoop wysers. 1466 01:08:34,370 --> 01:08:35,939 En wat doen hulle aanvanklik gelyk? 1467 01:08:35,939 --> 01:08:36,990 >> Publiek: null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON Hirsch: null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 So daar is ons leë ding. 1471 01:08:46,080 --> 01:08:47,170 Pampoen opbrengste nul. 1472 01:08:47,170 --> 01:08:48,569 Wat doen ons? 1473 01:08:48,569 --> 01:08:49,609 Loop my deur dit? 1474 01:08:49,609 --> 01:08:50,810 Eintlik, Marcus my al gegee het. 1475 01:08:50,810 --> 01:08:52,439 Iemand anders loop my deur dit. 1476 01:08:52,439 --> 01:08:54,760 Wat doen ons wanneer ons - 1477 01:08:54,760 --> 01:08:56,609 dit lyk baie soortgelyk aan wat ons net doen. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> Publiek: Ek gaan 'n raaiskoot te neem. 1480 01:08:59,090 --> 01:09:01,250 So wanneer jy lekkergoed. 1481 01:09:01,250 --> 01:09:01,640 >> JASON Hirsch: Ja. 1482 01:09:01,640 --> 01:09:03,120 Wel, ons het pampoen. 1483 01:09:03,120 --> 01:09:03,870 Kom ons kry ons eerste een. 1484 01:09:03,870 --> 01:09:04,324 Ons het pampoen. 1485 01:09:04,324 --> 01:09:04,779 >> Publiek: OK. 1486 01:09:04,779 --> 01:09:05,880 Pampoen opbrengste nul. 1487 01:09:05,880 --> 01:09:08,770 So jy sit dit in daardie. 1488 01:09:08,770 --> 01:09:10,810 Of eintlik, jy sit dit in die geskakelde lys. 1489 01:09:10,810 --> 01:09:13,550 >> JASON Hirsch: Hoe doen ons sit dit in die geskakelde lys? 1490 01:09:13,550 --> 01:09:15,479 >> Publiek: O, die werklike sintaksis? 1491 01:09:15,479 --> 01:09:16,240 >> JASON Hirsch: Slegs loop - 1492 01:09:16,240 --> 01:09:16,740 sê meer. 1493 01:09:16,740 --> 01:09:19,310 Wat doen ons? 1494 01:09:19,310 --> 01:09:22,100 >> Publiek: Jy voeg net dit as die eerste knoop. 1495 01:09:22,100 --> 01:09:22,675 >> JASON Hirsch: OK. 1496 01:09:22,675 --> 01:09:29,069 So het ons ons node, pampoen. 1497 01:09:29,069 --> 01:09:31,560 En nou hoe kan ek voeg dit? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> Publiek: Jy ken dit aan die wyser. 1500 01:09:37,090 --> 01:09:37,970 >> JASON Hirsch: Watter wyser? 1501 01:09:37,970 --> 01:09:39,620 >> Publiek: Die wyser op nul. 1502 01:09:39,620 --> 01:09:41,420 >> JASON Hirsch: So waar doen hierdie punt? 1503 01:09:41,420 --> 01:09:42,810 >> Publiek: Om nou van nul. 1504 01:09:42,810 --> 01:09:43,529 >> JASON Hirsch: Wel, dit is wys om null. 1505 01:09:43,529 --> 01:09:44,499 Maar ek is om in die pampoen. 1506 01:09:44,499 --> 01:09:46,053 So waar moet dit wys? 1507 01:09:46,053 --> 01:09:46,880 >> Publiek: Om pampoen. 1508 01:09:46,880 --> 01:09:47,399 >> JASON Hirsch: Om pampoen. 1509 01:09:47,399 --> 01:09:48,760 Presies. 1510 01:09:48,760 --> 01:09:50,010 So dui dit op pampoen. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 En waar doen dit wyser in die pampoen punt? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 Om 1515 01:09:58,340 --> 01:09:58,590 >> Publiek: null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON Hirsch: Om null. 1517 01:09:59,210 --> 01:10:00,460 Presies. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 So het ons net ingevoeg iets in die lys. 1520 01:10:05,140 --> 01:10:07,210 Ons het net hierdie kode het om dit te doen. 1521 01:10:07,210 --> 01:10:09,520 Byna ons amper het dit heeltemal gekraak. 1522 01:10:09,520 --> 01:10:10,790 Nou voeg ons lekkergoed. 1523 01:10:10,790 --> 01:10:13,480 Ons lekkergoed gaan ook aan nul. 1524 01:10:13,480 --> 01:10:16,100 So, wat doen ons met lekkergoed? 1525 01:10:16,100 --> 01:10:18,790 >> Publiek: Dit hang af van die vraag of nie ons probeer om dit uit te sorteer. 1526 01:10:18,790 --> 01:10:19,640 >> JASON Hirsch: Dis presies reg. 1527 01:10:19,640 --> 01:10:21,070 Dit hang af van die vraag of Ons probeer om dit uit te sorteer. 1528 01:10:21,070 --> 01:10:22,660 Kom ons aanvaar dat ons nie gaan om dit te sorteer. 1529 01:10:22,660 --> 01:10:24,880 >> Publiek: Wel, dan, as ons bespreek voor, is dit die eenvoudigste net om dit te sit 1530 01:10:24,880 --> 01:10:28,590 reg aan die begin so die wyser van nul punte te lekkergoed. 1531 01:10:28,590 --> 01:10:29,020 >> JASON Hirsch: OK. 1532 01:10:29,020 --> 01:10:29,380 Hou op. 1533 01:10:29,380 --> 01:10:30,630 Laat my skep lekkergoed reg hier. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 So dit wyser - 1536 01:10:35,150 --> 01:10:37,590 >> Publiek: Ja, nou moet word verwys na lekkergoed. 1537 01:10:37,590 --> 01:10:40,580 Toe het die verwysing van lekkergoed punt pampoen. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON Hirsch: Soos wat? 1540 01:10:44,560 --> 01:10:47,380 En sê ons het 'n ander ding te karteer aan nul? 1541 01:10:47,380 --> 01:10:48,660 >> Publiek: Wel, jy moet net doen dieselfde ding? 1542 01:10:48,660 --> 01:10:50,290 >> JASON Hirsch: Doen dieselfde ding. 1543 01:10:50,290 --> 01:10:53,700 So in hierdie geval, as ons dit nie doen nie wil hou dit gesorteer is dit 1544 01:10:53,700 --> 01:10:55,270 klink eerder eenvoudig. 1545 01:10:55,270 --> 01:10:59,920 Ons neem die wyser in die indice gegee deur ons hash funksie. 1546 01:10:59,920 --> 01:11:03,830 Ons het die punt om ons nuwe knoop. 1547 01:11:03,830 --> 01:11:07,830 En dan ook al dit was wys voorheen - 1548 01:11:07,830 --> 01:11:10,620 In hierdie geval nul, in die tweede geval pampoen - 1549 01:11:10,620 --> 01:11:15,310 dat alles wat dit is wys om Voorheen het ons by te voeg in die volgende van 1550 01:11:15,310 --> 01:11:17,810 ons nuwe knoop. 1551 01:11:17,810 --> 01:11:19,650 Ons is die inbring van iets in die begin. 1552 01:11:19,650 --> 01:11:22,900 In werklikheid is dit 'n baie makliker as probeer om die lys gesorteer te hou. 1553 01:11:22,900 --> 01:11:25,340 Maar weereens, sal soek wees meer ingewikkeld hier. 1554 01:11:25,340 --> 01:11:28,300 Ons sal altyd het om te gaan tot die einde. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Enige vrae oor afsonderlike aaneenskakeling? 1557 01:11:32,750 --> 01:11:34,690 Hoe dit werk? 1558 01:11:34,690 --> 01:11:35,820 Vra hulle asseblief nou. 1559 01:11:35,820 --> 01:11:39,260 Ek wil regtig om te maak seker dat jy al verstaan ​​voordat ons kop uit. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> Publiek: Hoekom dink jy sit pampoen en lekkergoed in dieselfde 1562 01:11:52,060 --> 01:11:54,108 deel van die hash tafel? 1563 01:11:54,108 --> 01:11:55,860 >> JASON Hirsch: Goeie vraag. 1564 01:11:55,860 --> 01:11:59,140 Hoekom moet ons hulle in dieselfde deel van die hash tafel? 1565 01:11:59,140 --> 01:12:03,200 Wel, in hierdie geval ons hash funksie opbrengste nul vir beide van hulle. 1566 01:12:03,200 --> 01:12:05,310 So wat hulle nodig het om te gaan op indice nul want dit is waar ons gaan 1567 01:12:05,310 --> 01:12:07,420 kyk vir hulle as ons ooit hulle wil kyk. 1568 01:12:07,420 --> 01:12:11,750 Weereens, met 'n lineêre indringende benadering sou ons nie sit hulle albei op nul. 1569 01:12:11,750 --> 01:12:13,900 Maar in die afsonderlike ketting benadering, ons gaan hulle te sit sowel by zero 1570 01:12:13,900 --> 01:12:16,620 en dan 'n lys af van nul. 1571 01:12:16,620 --> 01:12:20,140 >> En ons wil nie pampoen te vervang eenvoudig vir dat, omdat dan sal ons 1572 01:12:20,140 --> 01:12:21,860 aanvaar dat pampoen was nooit plaas. 1573 01:12:21,860 --> 01:12:25,230 As ons net een ding hou in die plek wat sleg sou wees. 1574 01:12:25,230 --> 01:12:28,590 Dan sou daar geen kans van ons ooit - 1575 01:12:28,590 --> 01:12:31,660 As ons ooit 'n duplikaat het, dan het ons wil net vee ons aanvanklike waarde. 1576 01:12:31,660 --> 01:12:34,090 So dit is hoekom ons doen hierdie benadering. 1577 01:12:34,090 --> 01:12:36,580 Of dit is hoekom ons gekies het - maar weer, ons verkies om die afsonderlike aaneenskakeling benadering, 1578 01:12:36,580 --> 01:12:39,670 waarin daar is baie ander benaderings 'n mens kan kies. 1579 01:12:39,670 --> 01:12:41,185 Maak dit jou 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 Lineêre indringende sou betrek - 1584 01:12:47,720 --> 01:12:51,913 As ons 'n botsing op nul, ons sou lyk in die volgende plek om te sien of 1585 01:12:51,913 --> 01:12:54,310 dit was oop en sit dit daar. 1586 01:12:54,310 --> 01:12:57,320 En dan kyk ons ​​in die volgende sport en sien of dit was oop en sit dit daar. 1587 01:12:57,320 --> 01:12:59,780 So vind ons die volgende beskikbare oop plek en sit dit daar. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Enige ander vrae? 1590 01:13:03,890 --> 01:13:05,370 Ja, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> Publiek: As 'n opvolg op dat, wat bedoel jy deur die volgende plek? 1592 01:13:07,490 --> 01:13:10,250 In die hash tafel of in 'n geskakelde lys. 1593 01:13:10,250 --> 01:13:12,100 >> JASON Hirsch: Vir lineêre ontwikkeling, geen geskakelde lyste. 1594 01:13:12,100 --> 01:13:13,400 Die volgende plek op die hash tafel. 1595 01:13:13,400 --> 01:13:13,820 >> Publiek: OK. 1596 01:13:13,820 --> 01:13:17,570 So het die hash tafel sou wees geïnisialiseer met die grootte - 1597 01:13:17,570 --> 01:13:19,560 soos die aantal snare dat jy inbring? 1598 01:13:19,560 --> 01:13:22,170 >> JASON Hirsch: Jy sou dit wil wees baie groot. 1599 01:13:22,170 --> 01:13:23,910 Ja. 1600 01:13:23,910 --> 01:13:27,900 Hier is 'n prentjie van wat ons net getrek op die bord. 1601 01:13:27,900 --> 01:13:29,470 Weereens, ons het 'n botsing reg hier. 1602 01:13:29,470 --> 01:13:30,710 by 152. 1603 01:13:30,710 --> 01:13:33,570 En jy sal sien ons ' 'n geskakelde lys van dit af. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Weereens, die hash tafel aparte aaneenskakeling benadering is nie die een wat jy 1606 01:13:41,850 --> 01:13:45,590 moet neem vir probleme soos ses, maar is een wat 'n baie 1607 01:13:45,590 --> 01:13:47,100 studente is geneig om te neem. 1608 01:13:47,100 --> 01:13:51,140 So op daardie noot, laat ons praat kortliks voordat ons kop uit oor die probleem ses, 1609 01:13:51,140 --> 01:13:52,160 en dan sal ek 'n storie met jou deel. 1610 01:13:52,160 --> 01:13:55,120 Ons het drie minute. 1611 01:13:55,120 --> 01:13:55,750 >> Probleem stel ses. 1612 01:13:55,750 --> 01:13:57,790 Jy het vier funksies - 1613 01:13:57,790 --> 01:14:02,430 vrag, kyk, die grootte en aflaai. 1614 01:14:02,430 --> 01:14:03,380 Vrag - 1615 01:14:03,380 --> 01:14:07,120 Wel, ons het al baie oor load nou net. 1616 01:14:07,120 --> 01:14:09,330 Ons het las op die bord. 1617 01:14:09,330 --> 01:14:13,230 En ons het selfs begin kodering 'n baie inbring in 'n geskakelde lys. 1618 01:14:13,230 --> 01:14:18,020 So vrag is nie veel meer as wat ons nou net gedoen het. 1619 01:14:18,020 --> 01:14:21,070 >> Check is wanneer jy iets gelaai. 1620 01:14:21,070 --> 01:14:22,580 Dit is dieselfde proses soos hierdie. 1621 01:14:22,580 --> 01:14:26,845 Dieselfde eerste twee dele waar jy gooi iets in die hash funksie 1622 01:14:26,845 --> 01:14:29,190 en kry die waarde daarvan. 1623 01:14:29,190 --> 01:14:30,700 Maar nou is ons nie die inbring nie. 1624 01:14:30,700 --> 01:14:33,350 Nou is ons op soek na dit. 1625 01:14:33,350 --> 01:14:37,130 Ek het die voorbeeld kode geskryf vir die vind van iets in 'n geskakelde lys. 1626 01:14:37,130 --> 01:14:38,250 Ek moedig julle wat om te oefen. 1627 01:14:38,250 --> 01:14:43,000 Maar intuïtief vind iets redelik soortgelyk aan die inbring iets. 1628 01:14:43,000 --> 01:14:46,540 Trouens, ons het 'n foto van die vind van iets in 'n geskakelde lys, beweeg 1629 01:14:46,540 --> 01:14:48,910 deur totdat jy aan die einde. 1630 01:14:48,910 --> 01:14:52,430 En as jy het aan die einde en kon nie vind nie, dan is dit nie daar nie. 1631 01:14:52,430 --> 01:14:55,400 So dit is tjek, wese. 1632 01:14:55,400 --> 01:14:57,030 >> Volgende is die grootte. 1633 01:14:57,030 --> 01:14:57,910 Kom ons slaan grootte. 1634 01:14:57,910 --> 01:15:00,040 Ten slotte het jy los. 1635 01:15:00,040 --> 01:15:02,890 Los is een wat ons het nie getrek op die bord of gekodeer nie. 1636 01:15:02,890 --> 01:15:05,990 Maar ek u aanmoedig om te probeer om die kodering dit in ons voorbeeld gekoppel lys voorbeeld. 1637 01:15:05,990 --> 01:15:11,440 Maar los intuïtief is soortgelyk aan gratis - 1638 01:15:11,440 --> 01:15:14,010 of ek bedoel is soortgelyk aan gaan. 1639 01:15:14,010 --> 01:15:17,350 Behalwe vir nou elke keer as jy gaan deur, is jy nie net om toe te 1640 01:15:17,350 --> 01:15:19,090 sien as jy jou waarde daar. 1641 01:15:19,090 --> 01:15:22,490 Maar jy neem dat knoop en bevry het, in wese. 1642 01:15:22,490 --> 01:15:23,610 Dit is wat, aflaai vra om te doen. 1643 01:15:23,610 --> 01:15:24,670 Gratis alles wat jy het malloced. 1644 01:15:24,670 --> 01:15:27,480 So jy gaan deur die hele lys weer, gaan deur die hele hash 1645 01:15:27,480 --> 01:15:27,760 tabel weer. 1646 01:15:27,760 --> 01:15:29,240 Hierdie keer kyk nie om te sien wat daar is. 1647 01:15:29,240 --> 01:15:31,080 Net bevry wat daar is. 1648 01:15:31,080 --> 01:15:33,260 >> En uiteindelik grootte. 1649 01:15:33,260 --> 01:15:34,350 Grootte moet geïmplementeer word. 1650 01:15:34,350 --> 01:15:35,590 As jy nie die grootte te implementeer nie - 1651 01:15:35,590 --> 01:15:36,250 Ek sal sê dit soos hierdie. 1652 01:15:36,250 --> 01:15:39,740 As jy nie die grootte presies implementeer nie een lyn van kode, insluitend die 1653 01:15:39,740 --> 01:15:43,760 terug verklaring, jy is doen grootte verkeerd. 1654 01:15:43,760 --> 01:15:47,170 So maak seker dat die grootte, vir 'n volledige ontwerp punte, jy doen dit in presies een 1655 01:15:47,170 --> 01:15:49,970 lyn van kode, insluitend die terugkeer verklaring. 1656 01:15:49,970 --> 01:15:52,450 >> En moenie pak nog nie op, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Gretig bever. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 Ek wou dankie ouens te sê vir die komende artikel. 1660 01:16:01,300 --> 01:16:02,550 Het jy 'n Happy Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Dit is my kostuum. 1663 01:16:05,960 --> 01:16:08,850 Ek sal dra hierdie op Donderdag As ek sien jy op kantoorure. 1664 01:16:08,850 --> 01:16:14,640 En as jy nuuskierig is oor 'n paar meer agtergrond tot hierdie kostuum, voel 1665 01:16:14,640 --> 01:16:19,135 vry om te check 2011 artikel vir 'n storie oor hoekom ek 1666 01:16:19,135 --> 01:16:20,900 dra die pampoen kostuum. 1667 01:16:20,900 --> 01:16:23,680 En dit is 'n hartseer storie. 1668 01:16:23,680 --> 01:16:27,050 So maak seker dat jy Sommige weefsel in die buurt. 1669 01:16:27,050 --> 01:16:28,680 Maar op daardie, indien u enige vrae wat ek sal rondom stok 1670 01:16:28,680 --> 01:16:29,960 buite na artikel. 1671 01:16:29,960 --> 01:16:31,510 Sterkte met die probleem sit ses. 1672 01:16:31,510 --> 01:16:33,540 En soos altyd, indien u enige vrae, laat my weet. 1673 01:16:33,540 --> 01:16:35,584