1 00:00:00,000 --> 00:00:03,423 >> [Speel van musiek] 2 00:00:03,423 --> 00:00:05,380 3 00:00:05,380 --> 00:00:08,210 >> ANDI Peng: Welkom by week 6 van artikel. 4 00:00:08,210 --> 00:00:11,620 Ons afgewyk van ons standaard artikel tyd van Dinsdag 5 00:00:11,620 --> 00:00:14,130 middag om hierdie pragtige Sondag oggend. 6 00:00:14,130 --> 00:00:17,330 Dankie vir almal wat saam met my vandag, maar ernstig, 7 00:00:17,330 --> 00:00:18,170 'n ronde van die applous. 8 00:00:18,170 --> 00:00:20,600 >> Dit is 'n mooi groot poging. 9 00:00:20,600 --> 00:00:23,600 Ek het amper nie eens maak dit up in die tyd, maar dit was OK. 10 00:00:23,600 --> 00:00:27,520 So ek weet dat julle almal het dit net gemaak om die quiz. 11 00:00:27,520 --> 00:00:30,370 Eerste van alles, welkom om die ander kant van daardie. 12 00:00:30,370 --> 00:00:32,917 >> Tweedens, sal ons daaroor praat. 13 00:00:32,917 --> 00:00:34,000 Ons sal praat oor die quiz. 14 00:00:34,000 --> 00:00:35,700 Ons sal praat oor hoe jy doen in die klas. 15 00:00:35,700 --> 00:00:36,550 Jy sal goed wees. 16 00:00:36,550 --> 00:00:39,080 Ek het jou vasvrae vir jy aan die einde van hier, 17 00:00:39,080 --> 00:00:42,120 so as jy ouens wil neem 'n blik op dit, heeltemal fyn. 18 00:00:42,120 --> 00:00:46,590 >> So vinnig voor ons begin, die agenda vir vandag is soos volg. 19 00:00:46,590 --> 00:00:48,430 Soos jy kan sien, is ons basies vinnige vuur 20 00:00:48,430 --> 00:00:52,120 deur 'n hele klomp van die data strukture regtig, regtig, regtig vinnig. 21 00:00:52,120 --> 00:00:54,380 So as sodanig, sal dit nie wees nie super interaktiewe vandag. 22 00:00:54,380 --> 00:00:59,620 Dit sal net my soort skree dinge wat jy, en as ek verwar jy, 23 00:00:59,620 --> 00:01:02,680 as ek gaan te vinnig, laat my weet. 24 00:01:02,680 --> 00:01:05,200 Hulle is net verskillende data strukture, en as deel 25 00:01:05,200 --> 00:01:07,070 jou pset vir hierdie komende week, sal jy 26 00:01:07,070 --> 00:01:10,340 word gevra om een ​​van hulle te implementeer, miskien twee van them-- twee van hulle 27 00:01:10,340 --> 00:01:12,319 in jou pset. 28 00:01:12,319 --> 00:01:14,610 OK, so ek is net gaan om te begin met 'n paar aankondigings. 29 00:01:14,610 --> 00:01:19,070 Ons gaan oor stapels en toue meer diepte as wat ons voor die quiz gedoen het. 30 00:01:19,070 --> 00:01:20,990 Ons sal gaan oor gekoppelde lys weer, weer, 31 00:01:20,990 --> 00:01:23,899 meer in diepte as wat ons moes voor die quiz. 32 00:01:23,899 --> 00:01:26,440 En dan sal ons praat oor hash tafels, bome en drieë, wat 33 00:01:26,440 --> 00:01:28,890 is almal mooi wat nodig is vir jou pset. 34 00:01:28,890 --> 00:01:32,925 En dan sal ons gaan oor 'n paar nuttige wenke vir pset5. 35 00:01:32,925 --> 00:01:37,360 >> OK, so quiz 0. 36 00:01:37,360 --> 00:01:41,090 Die gemiddelde was 'n 58%. 37 00:01:41,090 --> 00:01:45,370 Dit was baie laag is, en so julle ouens al het baie, baie goed in ooreenstemming 38 00:01:45,370 --> 00:01:46,510 met daardie. 39 00:01:46,510 --> 00:01:49,970 >> Pretty much, reël is as jy binne 'n standaardafwyking van die gemiddelde 40 00:01:49,970 --> 00:01:52,990 veral omdat ons in 'n minder gemaklike artikel, jy is heeltemal fyn. 41 00:01:52,990 --> 00:01:54,120 Jy is op die regte spoor. 42 00:01:54,120 --> 00:01:55,190 Die lewe is goed. 43 00:01:55,190 --> 00:01:58,952 >> Ek weet dit is scary om te dink dat Ek het soos 'n 40% op hierdie quiz. 44 00:01:58,952 --> 00:02:00,160 Ek gaan hierdie klas misluk. 45 00:02:00,160 --> 00:02:02,243 Ek belowe jou, jy is nie gaan aan die klas misluk. 46 00:02:02,243 --> 00:02:03,680 Jy is heeltemal fyn. 47 00:02:03,680 --> 00:02:06,850 >> Vir dié van julle wat oor het die gemiddelde, indrukwekkend, indrukwekkend, 48 00:02:06,850 --> 00:02:08,780 soos, ernstig goed gedoen. 49 00:02:08,780 --> 00:02:09,689 Ek het hulle met my. 50 00:02:09,689 --> 00:02:11,730 Voel vry om te kom kry hulle aan die einde van afdeling. 51 00:02:11,730 --> 00:02:14,520 Laat my weet as jy enige het kwessies, vrae saam met hulle. 52 00:02:14,520 --> 00:02:17,204 As ons jou telling verkeerd is, laat ons weet. 53 00:02:17,204 --> 00:02:21,240 >> OK, so pset5, dit is 'n baie vreemde week vir Yale in die sin 54 00:02:21,240 --> 00:02:24,240 dat ons pset is te danke Woensdag middag insluitend 55 00:02:24,240 --> 00:02:27,317 die laat dag, so dit is eintlik teoreties gevolg Dinsdag middag. 56 00:02:27,317 --> 00:02:29,150 Waarskynlik niemand klaar op Dinsdag middag. 57 00:02:29,150 --> 00:02:30,830 Dit is heeltemal fyn. 58 00:02:30,830 --> 00:02:33,700 Ons gaan kantoorure het vanaand asook Maandag nag. 59 00:02:33,700 --> 00:02:36,810 En al die afdelings sal hierdie week eintlik verander in werkswinkels, 60 00:02:36,810 --> 00:02:38,800 so voel vry om te pop in enige artikel wat jy wil, 61 00:02:38,800 --> 00:02:42,810 en hulle sal soort van mini-pset wees werkswinkels vir hulp op daardie. 62 00:02:42,810 --> 00:02:45,620 So as sodanig, dit is die enigste artikel waar ons leer materiaal. 63 00:02:45,620 --> 00:02:49,220 Al die ander afdelings sal fokus uitsluitlik op hulp vir die pset. 64 00:02:49,220 --> 00:02:50,146 Ja? 65 00:02:50,146 --> 00:02:52,000 >> GEHOOR: Waar is kantoorure? 66 00:02:52,000 --> 00:02:56,120 >> ANDI Peng: Kantoor ure tonight-- oh, goeie vraag. 67 00:02:56,120 --> 00:03:00,580 Ek dink kantoorure vanaand is in Teal of by Commons. 68 00:03:00,580 --> 00:03:02,984 As jy online CS50 kyk en jy gaan na kantoorure, 69 00:03:02,984 --> 00:03:05,650 daar moet 'n skedule wees dat vertel jou waar almal van hulle is. 70 00:03:05,650 --> 00:03:07,954 >> Ek weet nie vanaand of môre is teal, 71 00:03:07,954 --> 00:03:10,120 en ek dink ons ​​kan hê commons vir die ander aand. 72 00:03:10,120 --> 00:03:11,020 Ek is nie seker nie. 73 00:03:11,020 --> 00:03:11,700 Goeie vraag. 74 00:03:11,700 --> 00:03:14,430 Kyk op CS50. 75 00:03:14,430 --> 00:03:18,780 >> Cool, enige vrae oor die skedule vir die volgende drie dae soos? 76 00:03:18,780 --> 00:03:21,690 Ek belowe julle ouens soos David gesê dit is die top van die berg. 77 00:03:21,690 --> 00:03:23,050 Julle is amper daar. 78 00:03:23,050 --> 00:03:24,644 Net drie dae. 79 00:03:24,644 --> 00:03:26,310 Kry daar, en dan sal ons almal kom neer. 80 00:03:26,310 --> 00:03:28,114 Ons sal 'n mooi CS-vry te breek nie. 81 00:03:28,114 --> 00:03:28,780 Ons sal terug te kom. 82 00:03:28,780 --> 00:03:30,779 Ons sal duik in web ontwikkeling en ontwikkeling, 83 00:03:30,779 --> 00:03:35,150 dinge wat baie pret in vergelyking sommige van die ander psets. 84 00:03:35,150 --> 00:03:37,974 En dit sal chill wees, en ons sal baie pret hê. 85 00:03:37,974 --> 00:03:38,890 Ons sal meer lekkergoed. 86 00:03:38,890 --> 00:03:39,730 Jammer vir lekkergoed. 87 00:03:39,730 --> 00:03:40,945 Ek het vergeet lekkergoed. 88 00:03:40,945 --> 00:03:43,310 Dit was 'n rowwe oggend. 89 00:03:43,310 --> 00:03:46,340 So julle ouens is amper daar, en ek is baie trots op julle. 90 00:03:46,340 --> 00:03:49,570 >> OK, so stapels. 91 00:03:49,570 --> 00:03:53,331 Wie was lief vir die vraag oor Jack en sy klere aan die quiz? 92 00:03:53,331 --> 00:03:53,830 Niemand? 93 00:03:53,830 --> 00:03:56,500 OK, dit is goed. 94 00:03:56,500 --> 00:04:00,200 >> So in wese as wat jy kan prentjie Jack, hierdie man hier, 95 00:04:00,200 --> 00:04:03,350 lief vir die klere te neem uit die top van die stapel, 96 00:04:03,350 --> 00:04:05,750 en hy sit dit terug op die stapel nadat hy gedoen het. 97 00:04:05,750 --> 00:04:07,600 So op hierdie manier, het hy nooit blyk te wees om 98 00:04:07,600 --> 00:04:10,090 aan die onderkant van die stapel in sy klere. 99 00:04:10,090 --> 00:04:12,600 So hierdie soort beskryf die basiese data struktuur 100 00:04:12,600 --> 00:04:16,610 van hoe 'n stapel geïmplementeer word. 101 00:04:16,610 --> 00:04:20,060 >> Wese, dink aan 'n stapel as enige stapel van voorwerpe 102 00:04:20,060 --> 00:04:24,900 waar jy dinge op die top, en hulle dan pop julle uit die top. 103 00:04:24,900 --> 00:04:28,600 So LIFO is die akroniem ons graag om use-- Laaste in, eerste uit. 104 00:04:28,600 --> 00:04:32,480 En so duur in die top van die stapel is die eerste een wat kom uit. 105 00:04:32,480 --> 00:04:34,260 En so het die twee terme ons graag assosieer 106 00:04:34,260 --> 00:04:36,190 met wat push en pop genoem. 107 00:04:36,190 --> 00:04:39,790 Wanneer jy iets op die druk stapel, en jy dit pop back-up. 108 00:04:39,790 --> 00:04:43,422 >> En so het ek dink dit is soort van 'n abstrakte konsep vir dié van julle 109 00:04:43,422 --> 00:04:45,630 wat wil om te sien soos 'n werklike implementering van hierdie 110 00:04:45,630 --> 00:04:46,740 in die werklike wêreld. 111 00:04:46,740 --> 00:04:50,170 Hoeveel van julle het 'n opstel geskryf Miskien soos 'n uur voor dit te wyte, 112 00:04:50,170 --> 00:04:54,510 en jy per ongeluk geskrap 'n groot stuk van dit, soos per ongeluk? 113 00:04:54,510 --> 00:04:58,560 En dan wat beheer te doen ons gebruik om dit terug te sit? 114 00:04:58,560 --> 00:05:00,030 Beheer-Z, ja? 115 00:05:00,030 --> 00:05:03,640 Beheer-Z, sodat die bedrag van die tye wat beheer-Z my lewe gered het, 116 00:05:03,640 --> 00:05:08,820 het my gat gered, elke keer dit is geïmplementeer deur 'n stapel. 117 00:05:08,820 --> 00:05:13,020 >> Wese al die inligting dit is op jou Word dokument, 118 00:05:13,020 --> 00:05:15,080 dit word gestoot en inloer wil. 119 00:05:15,080 --> 00:05:19,460 En so in wese wanneer jy enigiets verwyder, jy pop back-up. 120 00:05:19,460 --> 00:05:22,820 En dan as jy dit nodig het weer op, jy stoot dit, en dit is wat beheer-C nie. 121 00:05:22,820 --> 00:05:26,770 En so die werklike wêreld funksie van hoe eenvoudige data struktuur 122 00:05:26,770 --> 00:05:28,690 kan help met jou alledaagse lewe. 123 00:05:28,690 --> 00:05:31,710 124 00:05:31,710 --> 00:05:40,150 >> So 'n struct is die pad wat ons eintlik skep 'n stapel. 125 00:05:40,150 --> 00:05:44,720 Ons tik definieer struct, en dan ons noem dit stapel aan die onderkant. 126 00:05:44,720 --> 00:05:47,440 En binne die stapel, ons het twee parameters 127 00:05:47,440 --> 00:05:51,580 wat kan ons in wese te manipuleer, so ons het char star snare kapasiteit. 128 00:05:51,580 --> 00:05:55,150 >> Al wat dit doen skep 'n skikking 129 00:05:55,150 --> 00:05:58,835 dat ons kan stoor wat jy wil waarin ons sy kapasiteit kan bepaal. 130 00:05:58,835 --> 00:06:01,990 Kapasiteit is net die maksimum bedrag van items wat ons in hierdie reeks kan sit. 131 00:06:01,990 --> 00:06:05,660 int grootte is die toonbank wat hou hou van hoeveel items is tans 132 00:06:05,660 --> 00:06:07,850 in die stapel. 133 00:06:07,850 --> 00:06:11,860 So dan kan ons hou van, A, beide hoe groot die werklike stapel is, 134 00:06:11,860 --> 00:06:14,850 en, B, hoeveel van daardie stapel ons gevul omdat ons wil nie 135 00:06:14,850 --> 00:06:18,800 om oor oorloop wat ons kapasiteit is. 136 00:06:18,800 --> 00:06:24,340 >> So byvoorbeeld, hierdie pragtige vraag was op jou quiz. 137 00:06:24,340 --> 00:06:28,160 Wese hoe doen ons stoot op die top van 'n stapel. 138 00:06:28,160 --> 00:06:28,830 Eenvoudig. 139 00:06:28,830 --> 00:06:30,621 As jy kyk na dit, ons sal loop deur middel van hierdie. 140 00:06:30,621 --> 00:06:32,640 As [onhoorbaar] size-- Onthou, wanneer jy 141 00:06:32,640 --> 00:06:35,300 wil enige toegang parameter binne 'n struct, 142 00:06:35,300 --> 00:06:40,320 jy die naam van die struct.parameter. 143 00:06:40,320 --> 00:06:42,720 >> In hierdie geval, is s die naam van ons stapel. 144 00:06:42,720 --> 00:06:46,230 Ons wil die grootte toegang dit, so ons doen s.size. 145 00:06:46,230 --> 00:06:50,280 So solank die grootte is nie gelyk aan kapasiteit of so lank 146 00:06:50,280 --> 00:06:52,940 as dit is minder as kapasiteit, óf sou hier werk. 147 00:06:52,940 --> 00:06:57,180 >> Jy wil om toegang tot die binnekant van jou stapel, so s.strings, 148 00:06:57,180 --> 00:07:00,790 en jy gaan om dit te sit nuwe nommer wat jy wil plaas in daar. 149 00:07:00,790 --> 00:07:05,030 Laat ons net sê ons wil voeg int N op die stapel, 150 00:07:05,030 --> 00:07:08,905 ons kon s.strings te doen, hakies, s.size gelyk n. 151 00:07:08,905 --> 00:07:11,030 Omdat grootte is waar ons tans in die stapel 152 00:07:11,030 --> 00:07:14,590 as ons gaan om te stoot dit op, ons het net toegang 153 00:07:14,590 --> 00:07:17,370 waar die grootte is, die huidige volheid van die stapel, 154 00:07:17,370 --> 00:07:21,729 en ons stoot die int N op dit. 155 00:07:21,729 --> 00:07:24,770 En dan wil ons seker maak dat ons is ook die verhoog grootte van die N, 156 00:07:24,770 --> 00:07:27,436 sodat ons kan hou van wat ons het 'n ekstra ding by die stapel. 157 00:07:27,436 --> 00:07:29,660 Nou het ons 'n groter grootte. 158 00:07:29,660 --> 00:07:33,196 Is dit hier sin maak om almal, hoe logies dit werk? 159 00:07:33,196 --> 00:07:34,160 Dit was soort van 'n vinnige. 160 00:07:34,160 --> 00:07:39,535 161 00:07:39,535 --> 00:07:42,160 GEHOOR: Kan jy gaan oor die s.stringss.strings [s.size] weer? 162 00:07:42,160 --> 00:07:45,808 ANDI Peng: Seker, so wat doen s.size ons tans te gee? 163 00:07:45,808 --> 00:07:47,440 GEHOOR: Dis die huidige grootte. 164 00:07:47,440 --> 00:07:50,890 ANDI Peng: Presies, so die huidige indeks wat ons grootte is op, 165 00:07:50,890 --> 00:07:57,780 en so wil ons die nuwe heelgetal sit wat ons wil voeg in s.size. 166 00:07:57,780 --> 00:07:58,760 Maak wat sin maak? 167 00:07:58,760 --> 00:08:01,110 Omdat s.strings, alles wat is die naam van die skikking. 168 00:08:01,110 --> 00:08:03,510 Al wat dit is, is toegang tot die verskeidenheid binne ons struct, 169 00:08:03,510 --> 00:08:06,030 en so as ons wil plaas n in daardie indeks 170 00:08:06,030 --> 00:08:09,651 kan ons net toegang tot dit die gebruik van hakies s.size. 171 00:08:09,651 --> 00:08:10,150 Koel. 172 00:08:10,150 --> 00:08:13,580 173 00:08:13,580 --> 00:08:18,916 >> Alle reg, pop, ek pseudokode dit uit vir julle nie, maar soortgelyke konsep. 174 00:08:18,916 --> 00:08:19,790 Maak wat sin maak? 175 00:08:19,790 --> 00:08:22,310 As die grootte is groter as nul, dan moet jy 176 00:08:22,310 --> 00:08:25,350 weet dat jy iets wil neem uit, want as die grootte is nie 177 00:08:25,350 --> 00:08:27,620 groter as nul, dan moet jy het niks in die stapel. 178 00:08:27,620 --> 00:08:29,840 >> So jy wil net om uit te voer hierdie kode, kan dit slegs 179 00:08:29,840 --> 00:08:32,320 pop as daar is iets om te pop. 180 00:08:32,320 --> 00:08:35,830 So as die grootte is groter as 0, ons minus die grootte. 181 00:08:35,830 --> 00:08:40,020 Ons decrement die grootte en dan terug alles wat binnekant van dit, want 182 00:08:40,020 --> 00:08:42,710 deur die knal, ons wil toegang ongeag gestoor 183 00:08:42,710 --> 00:08:45,694 in die indeks van die top van die stapel. 184 00:08:45,694 --> 00:08:46,610 Alles sin maak? 185 00:08:46,610 --> 00:08:49,693 As ek gemaak julle skryf dit uit, sou julle in staat wees om dit uit te skryf? 186 00:08:49,693 --> 00:08:52,029 187 00:08:52,029 --> 00:08:53,570 OK, julle ouens kan speel met dit. 188 00:08:53,570 --> 00:08:55,252 Geen bekommernisse as jy dit nie kry nie. 189 00:08:55,252 --> 00:08:57,460 Ons het nie tyd om kode hê dit vandag, want ons het 190 00:08:57,460 --> 00:08:59,959 het 'n baie van hierdie strukture om deur te gaan, maar in wese 191 00:08:59,959 --> 00:09:02,214 pseudokode, baie, baie soortgelyk aan te stoot. 192 00:09:02,214 --> 00:09:03,380 Volg net langs die logika. 193 00:09:03,380 --> 00:09:06,092 Maak seker dat jy toegang tot al die eienskappe van jou struct korrek. 194 00:09:06,092 --> 00:09:06,574 Ja? 195 00:09:06,574 --> 00:09:09,282 >> GEHOOR: Sal hierdie skyfies en hierdie hele ding wees vandag-ish? 196 00:09:09,282 --> 00:09:11,586 ANDI Peng: Altyd, yep. 197 00:09:11,586 --> 00:09:13,710 Ek gaan om te probeer om te sit hierdie up soos 'n uur daarna. 198 00:09:13,710 --> 00:09:16,626 Ek sal e-pos Dawid sal Dawid probeer om sit dit op soos 'n uur nadat die. 199 00:09:16,626 --> 00:09:20,040 200 00:09:20,040 --> 00:09:25,470 >> OK, so dan skuif ons in hierdie ander pragtige data struktuur genaamd 'n tou. 201 00:09:25,470 --> 00:09:30,140 As julle ouens hier kan sien, 'n ry, vir die Britse onder ons, 202 00:09:30,140 --> 00:09:32,010 al is dit is 'n lyn. 203 00:09:32,010 --> 00:09:34,680 So anders as wat jy dink 'n stapel is, 204 00:09:34,680 --> 00:09:37,750 'n tou is presies wat logies jy dink dit is. 205 00:09:37,750 --> 00:09:41,914 Dit is gehou deur die reëls van die EIEU, wat is die eerste in, eerste uit. 206 00:09:41,914 --> 00:09:43,705 As jy die eerste een in die lyn, is jy 207 00:09:43,705 --> 00:09:46,230 die eerste een wat kom uit die lyn. 208 00:09:46,230 --> 00:09:49,680 >> So, wat ons graag noem dit is dequeueing en enqueueing. 209 00:09:49,680 --> 00:09:52,380 As ons iets wil voeg ons ry, ons enqueue. 210 00:09:52,380 --> 00:09:55,690 As ons wil dequeue, of neem iets weg, ons dequeue. 211 00:09:55,690 --> 00:10:03,350 >> So dieselfde sin dat ons soort skep vaste grootte elemente wat ons 212 00:10:03,350 --> 00:10:06,500 kan sekere stoor dinge, maar ons kan ook 213 00:10:06,500 --> 00:10:10,100 verander waar ons plaas parameters binnekant van hulle 214 00:10:10,100 --> 00:10:13,140 gebaseer op watter tipe funksie wat ons wil. 215 00:10:13,140 --> 00:10:16,700 So stapels, ons wou die laaste een, N om die eerste een uit wees. 216 00:10:16,700 --> 00:10:19,800 Tou is ons wil die eerste ding in die eerste ding uit te wees. 217 00:10:19,800 --> 00:10:22,510 218 00:10:22,510 --> 00:10:26,710 >> So die struct-tipe definieer, soos jy kan sien, 219 00:10:26,710 --> 00:10:29,470 dit is 'n bietjie anders van wat die stapel was 220 00:10:29,470 --> 00:10:33,120 want nie net het ons om aan te hou spoor van waar die grootte tans, 221 00:10:33,120 --> 00:10:37,420 ons wil ook om tred te hou van die kop te hou asook waar ons tans is. 222 00:10:37,420 --> 00:10:39,580 So ek dink dit is makliker as ek teken dit op. 223 00:10:39,580 --> 00:10:53,270 So laat dink ons ​​het 'n tou het, so kom ons sê die hoof is reg hier. 224 00:10:53,270 --> 00:10:55,811 225 00:10:55,811 --> 00:10:58,310 Die hoof van die lyn, laat net sê dit is daar op die oomblik, 226 00:10:58,310 --> 00:11:01,809 en ons wil voeg iets in die tou. 227 00:11:01,809 --> 00:11:04,350 Ek gaan grootte wese roep is dieselfde ding as stert, 228 00:11:04,350 --> 00:11:06,314 die einde van waar jou tou is. 229 00:11:06,314 --> 00:11:07,730 Laat ons net sê grootte is reg hier. 230 00:11:07,730 --> 00:11:14,380 231 00:11:14,380 --> 00:11:18,400 >> So hoe kry mens feasibly voeg iets in 'n tou? 232 00:11:18,400 --> 00:11:21,000 233 00:11:21,000 --> 00:11:24,130 Wat indeks wil ons plaas waar ons wil voeg in. 234 00:11:24,130 --> 00:11:29,320 As dit is die begin van jou ry en dit is die einde van dit 235 00:11:29,320 --> 00:11:31,860 of die grootte van dit, waar ons doen wil die volgende voorwerp voeg? 236 00:11:31,860 --> 00:11:32,920 >> GEHOOR: [onhoorbaar] 237 00:11:32,920 --> 00:11:35,920 ANDI Peng: Presies, wat jy wil byvoeg dit afhangende het jy geskryf. 238 00:11:35,920 --> 00:11:37,840 Óf dit is leeg, of dat is leeg. 239 00:11:37,840 --> 00:11:42,630 So jy wil om dit waarskynlik voeg hier, want as die grootte is-- 240 00:11:42,630 --> 00:11:50,540 As dit is al vol, jy wil om dit reg hier by te voeg, reg? 241 00:11:50,540 --> 00:11:57,150 >> En so is dit, terwyl baie, baie eenvoudige, nie heeltemal altyd korrek 242 00:11:57,150 --> 00:12:00,690 omdat die belangrikste verskil tussen 'n tou en 'n stapel 243 00:12:00,690 --> 00:12:04,350 is dat die tou kan eintlik gemanipuleer 244 00:12:04,350 --> 00:12:06,980 sodat die hoof veranderinge afhangende van waar jy wil 245 00:12:06,980 --> 00:12:08,650 die begin van jou cue om te begin. 246 00:12:08,650 --> 00:12:11,900 En as 'n gevolg, jou stert ook gaan verander. 247 00:12:11,900 --> 00:12:14,770 En so 'n blik op hierdie kode nou. 248 00:12:14,770 --> 00:12:18,620 As julle ouens is ook gevra om skryf uit op die quiz, enqueue. 249 00:12:18,620 --> 00:12:22,580 Miskien sal ons deur die rede waarom praat was die antwoord wat dit was. 250 00:12:22,580 --> 00:12:26,790 >> Ek kon nie heeltemal inpas hierdie lyn op een, maar in wese hierdie stuk van die kode 251 00:12:26,790 --> 00:12:29,030 moet wees op een lyn. 252 00:12:29,030 --> 00:12:30,140 Spandeer soos 30 sekondes. 253 00:12:30,140 --> 00:12:33,000 Neem 'n blik, en sien waarom dit is die manier waarop dit is. 254 00:12:33,000 --> 00:12:50,030 255 00:12:50,030 --> 00:12:55,420 >> Baie, baie soortgelyk struct, baie, baie soortgelyke struktuur as die vorige 256 00:12:55,420 --> 00:12:58,090 stapel behalwe vir miskien een lyn van kode. 257 00:12:58,090 --> 00:13:01,190 En dat 'n mens reël van die kode bepaal die funksie. 258 00:13:01,190 --> 00:13:03,900 En dit is werklik 'n onderskeid 'n tou van 'n stapel. 259 00:13:03,900 --> 00:13:18,510 260 00:13:18,510 --> 00:13:22,010 >> Iemand wil hê om 'n steek te neem om te verduidelik waarom jy het 261 00:13:22,010 --> 00:13:24,980 het hierdie ingewikkelde ding hier? 262 00:13:24,980 --> 00:13:27,845 Ons sien die terugkeer van ons wonderlike vriend modulus. 263 00:13:27,845 --> 00:13:31,020 As julle ouens gou sal kom om te erken in programmering, 264 00:13:31,020 --> 00:13:34,910 byna elke keer as jy iets nodig het te draai om enigiets, 265 00:13:34,910 --> 00:13:36,850 modulus gaan die manier om dit te doen. 266 00:13:36,850 --> 00:13:40,510 So weet dat nie almal wil om te probeer verduidelik dat die lyn van die kode? 267 00:13:40,510 --> 00:13:44,060 268 00:13:44,060 --> 00:13:47,507 Ja, al die antwoorde is aanvaar en welkom. 269 00:13:47,507 --> 00:13:48,840 GEHOOR: Is jy met my praat? 270 00:13:48,840 --> 00:13:49,506 ANDI Peng: Ja. 271 00:13:49,506 --> 00:13:56,200 GEHOOR: O, nee jammer. 272 00:13:56,200 --> 00:14:00,250 ANDI Peng: OK, so laat loop deur hierdie kode. 273 00:14:00,250 --> 00:14:03,642 So wanneer jy probeer om iets by te voeg op 'n tou, 274 00:14:03,642 --> 00:14:08,510 in die pragtige geval dat die hoof gebeur om hier te wees, is dit baie maklik vir ons 275 00:14:08,510 --> 00:14:10,960 om net na die einde voeg iets, reg? 276 00:14:10,960 --> 00:14:14,690 Maar die hele punt van 'n tou is dat die hoof eintlik kan dinamiese 277 00:14:14,690 --> 00:14:17,280 verander, afhangende van waar ons wil die begin van ons q te wees, 278 00:14:17,280 --> 00:14:19,880 en as sodanig, die stert ook gaan verander. 279 00:14:19,880 --> 00:14:31,100 >> En so dink dat dit nie die was ry nie, maar eerder dit was die tou. 280 00:14:31,100 --> 00:14:37,900 281 00:14:37,900 --> 00:14:39,330 Kom ons sê die hoof is reg hier. 282 00:14:39,330 --> 00:14:54,900 283 00:14:54,900 --> 00:14:56,980 Kom ons sê die tou lyk soos hierdie. 284 00:14:56,980 --> 00:15:00,190 As ons wou skuif waar die begin van die lyn is, 285 00:15:00,190 --> 00:15:03,400 Kom ons sê ons verskuif hoof hierdie manier en groottes hier. 286 00:15:03,400 --> 00:15:07,100 >> Nou wil ons iets om by te voeg hierdie ry, maar as julle kan sien, 287 00:15:07,100 --> 00:15:11,150 dit is nie so eenvoudig soos om net te voeg alles wat na die grootte 288 00:15:11,150 --> 00:15:13,630 want dan uit loop ons perke van ons werklike skikking. 289 00:15:13,630 --> 00:15:16,190 Waar ons wil regtig voeg is hier. 290 00:15:16,190 --> 00:15:18,610 Dit is die skoonheid van 'n tou is dat ons, visueel dit 291 00:15:18,610 --> 00:15:22,380 lyk soos die lyn gaan soos hierdie, maar wanneer gestoor in 'n data struktuur, 292 00:15:22,380 --> 00:15:29,370 hulle gee dit as 'n siklus soos. 293 00:15:29,370 --> 00:15:32,360 Dit vou soort rondom aan die voorkant van die dieselfde manier 294 00:15:32,360 --> 00:15:34,780 dat 'n lyn kan ook draai rondom afhangende waar jy 295 00:15:34,780 --> 00:15:36,279 wil begin van die lyn te wees. 296 00:15:36,279 --> 00:15:38,630 En so as ons 'n kyk hier, laat ons 297 00:15:38,630 --> 00:15:40,880 sê ons wil 'n te skep funksie genoem enqueue. 298 00:15:40,880 --> 00:15:43,980 Ons wou int N add in daardie q. 299 00:15:43,980 --> 00:15:49,250 As q.size q-- ons sal noem dat ons data structure-- as ons queue.size nie 300 00:15:49,250 --> 00:15:52,520 gelyk aan kapasiteit of indien dit is minder as kapasiteit, 301 00:15:52,520 --> 00:15:55,120 q.strings is die skikking in ons q. 302 00:15:55,120 --> 00:15:58,380 Ons gaan sit wat gelyk is aan q.heads, 303 00:15:58,380 --> 00:16:02,730 wat is reg hier, plus q.size modulus deur die kapasiteit, wat 304 00:16:02,730 --> 00:16:04,290 draai ons terug hier rond. 305 00:16:04,290 --> 00:16:08,040 >> So in hierdie voorbeeld, indeks van die kop is 1, reg? 306 00:16:08,040 --> 00:16:11,480 Die indeks van grootte is 0, 1, 2, 3, 4. 307 00:16:11,480 --> 00:16:19,500 So kan ons 1 plus 4 modulus doen deur ons kapasiteit wat is 5. 308 00:16:19,500 --> 00:16:20,920 Wat beteken dit vir ons? 309 00:16:20,920 --> 00:16:23,270 Wat is die indeks wat kom uit hierdie? 310 00:16:23,270 --> 00:16:24,080 >> GEHOOR: 0. 311 00:16:24,080 --> 00:16:27,870 >> ANDI Peng: 0, wat gebeur na regs hier te wees, 312 00:16:27,870 --> 00:16:30,640 en so het ons wil in staat wees in te voeg in hier. 313 00:16:30,640 --> 00:16:34,730 En so hierdie vergelyking hier soort van net werk met enige nommers 314 00:16:34,730 --> 00:16:36,750 afhangende van waar jou kop en jou maat is. 315 00:16:36,750 --> 00:16:38,541 As jy weet wat die dinge is, jy weet 316 00:16:38,541 --> 00:16:43,170 presies waar jy wil plaas alles wat na jou tou. 317 00:16:43,170 --> 00:16:44,640 Maak dit sin om almal? 318 00:16:44,640 --> 00:16:48,560 >> Ek weet van 'n brein soort teaser veral aangesien hierdie 319 00:16:48,560 --> 00:16:50,512 gekom het in die nasleep van jou quiz. 320 00:16:50,512 --> 00:16:52,220 Maar hopelik almal nou kan verstaan 321 00:16:52,220 --> 00:16:57,800 waarom hierdie oplossing of hierdie funksie is die manier waarop dit is. 322 00:16:57,800 --> 00:16:59,840 Enigiemand 'n bietjie onduidelik op daardie? 323 00:16:59,840 --> 00:17:03,471 324 00:17:03,471 --> 00:17:03,970 OK. 325 00:17:03,970 --> 00:17:07,109 326 00:17:07,109 --> 00:17:09,970 >> En so nou, as jy wou dequeue, hierdie 327 00:17:09,970 --> 00:17:15,240 is waar ons hoof sal wees verskuif want as ons dequeue, 328 00:17:15,240 --> 00:17:17,030 Ons neem nie af aan die einde van die q. 329 00:17:17,030 --> 00:17:19,130 Ons wil die kop te neem, reg? 330 00:17:19,130 --> 00:17:24,260 So as 'n gevolg hiervan, is die hoof van plan te verander, en dit is hoekom wanneer jy enqueue, 331 00:17:24,260 --> 00:17:26,800 jy het om tred te hou waar jou kop en jou maat 332 00:17:26,800 --> 00:17:29,450 is om in staat wees om in te voeg in die regte posisie. 333 00:17:29,450 --> 00:17:32,740 >> En so wanneer jy dequeue, Ek pseudokode dit ook. 334 00:17:32,740 --> 00:17:35,480 Voel vry om as jy wil om te probeer kodering dit uit. 335 00:17:35,480 --> 00:17:36,980 Jy wil die kop te skuif, reg? 336 00:17:36,980 --> 00:17:39,320 As ek wou dequeue, ek sou die kop te skuif oor. 337 00:17:39,320 --> 00:17:40,800 Dit sal die hoof wees. 338 00:17:40,800 --> 00:17:45,617 >> En ons huidige grootte sou trek omdat ons nie meer 339 00:17:45,617 --> 00:17:46,950 het vier elemente in die skikking. 340 00:17:46,950 --> 00:17:51,370 Ons het net drie, en dan wil ons om terug te keer alles binne gestoor 341 00:17:51,370 --> 00:17:56,260 van die kop, want ons wil om dit te neem waarde uit so baie soortgelyk aan die stapel. 342 00:17:56,260 --> 00:17:58,010 Net jy neem uit 'n ander plek, 343 00:17:58,010 --> 00:18:01,770 en jy het om jou muis toewys om ander plek as 'n gevolg. 344 00:18:01,770 --> 00:18:03,890 Logies, almal volg? 345 00:18:03,890 --> 00:18:05,690 Groot. 346 00:18:05,690 --> 00:18:10,156 >> OK, so ons gaan 'n bietjie praat meer in diepte oor geskakelde lyste 347 00:18:10,156 --> 00:18:13,280 omdat hulle baie, baie waardevol sal wees vir jou in die loop van hierdie week se 348 00:18:13,280 --> 00:18:14,964 psets. 349 00:18:14,964 --> 00:18:17,130 Geskakelde lyste, as julle ouens kan onthou, al is hulle 350 00:18:17,130 --> 00:18:22,570 is nodes wat nodes van sekere waardes van beide 'n waarde en 'n wyser 351 00:18:22,570 --> 00:18:26,290 wat saam gekoppel deur diegene wenke. 352 00:18:26,290 --> 00:18:29,880 En so het die struct oor hoe Ons skep 'n node hier is ons 353 00:18:29,880 --> 00:18:33,569 het int N, wat ook al die waarde in 'n winkel of string N 354 00:18:33,569 --> 00:18:35,610 of wat ook al jy wil dit noem, die char star n. 355 00:18:35,610 --> 00:18:41,482 Struct node ster, wat die wyser wat jy wil hê in elke knoop, 356 00:18:41,482 --> 00:18:43,690 jy gaan wat wyser punt teenoor die volgende. 357 00:18:43,690 --> 00:18:48,207 358 00:18:48,207 --> 00:18:50,040 Jy sal die kop het van 'n geskakelde lys dis 359 00:18:50,040 --> 00:18:53,140 gaan om te wys op die res van die waardes so aan en so voort 360 00:18:53,140 --> 00:18:55,290 totdat jy uiteindelik die einde. 361 00:18:55,290 --> 00:18:58,040 En dit is net die laaste node gaan 'n wyser nie. 362 00:18:58,040 --> 00:18:59,952 Dit gaan om te wys op null, en dit is wanneer 363 00:18:59,952 --> 00:19:01,910 jy weet jy het druk op die einde van jou geskakelde lys 364 00:19:01,910 --> 00:19:04,076 is wanneer jou laaste wyser nie wys nie. 365 00:19:04,076 --> 00:19:06,670 366 00:19:06,670 --> 00:19:10,990 >> So ons gaan 'n bietjie meer in te gaan diepte oor hoe 'n mens sou moontlik 367 00:19:10,990 --> 00:19:12,400 soek 'n geskakelde lys. 368 00:19:12,400 --> 00:19:15,460 Onthou wat is 'n paar van die nadele van die geskakelde lyste 369 00:19:15,460 --> 00:19:19,340 verse 'n skikking rakende navrae. 370 00:19:19,340 --> 00:19:22,565 'N skikking kan jy binêre soek, maar Hoekom kan jy dit nie doen nie in 'n geskakelde lys? 371 00:19:22,565 --> 00:19:26,834 372 00:19:26,834 --> 00:19:30,320 >> GEHOOR: Omdat hulle almal is verbind, maar jy hoef nie heeltemal weet waar 373 00:19:30,320 --> 00:19:31,330 [Onhoorbaar]. 374 00:19:31,330 --> 00:19:34,600 >> ANDI Peng: Ja, presies so onthou dat die glans van 'n verskeidenheid 375 00:19:34,600 --> 00:19:37,190 was die feit dat ons moes ewetoeganklike geheue waar 376 00:19:37,190 --> 00:19:41,580 as ek wou die waarde van indeks ses, ek kon net sê indeks ses 377 00:19:41,580 --> 00:19:42,407 gee my daardie waarde. 378 00:19:42,407 --> 00:19:45,240 En dit is omdat skikkings gesorteer in 'n aangrensende ruimte van die geheue 379 00:19:45,240 --> 00:19:48,020 in een plek, terwyl soort geskakelde lyste 380 00:19:48,020 --> 00:19:52,820 is lukraak afgewissel rondom, en die enigste manier waarop jy kan 'n mens vind 381 00:19:52,820 --> 00:19:56,890 is deur middel van 'n wyser wat jou vertel Die adres van waar dat die volgende node is. 382 00:19:56,890 --> 00:20:00,290 >> En so as 'n gevolg, die enigste manier om te soek deur 'n geskakelde lys 383 00:20:00,290 --> 00:20:01,560 lineêr search. 384 00:20:01,560 --> 00:20:05,890 Want ek weet nie presies waar die 12de waarde in die geskakelde lys is, 385 00:20:05,890 --> 00:20:08,780 Ek het na die geheel deurkruis van daardie geskakelde lys een 386 00:20:08,780 --> 00:20:12,450 een van die hoof na die eerste knoop, na die tweede node, na die derde knoop, 387 00:20:12,450 --> 00:20:17,690 al die pad af totdat ek uiteindelik om waar daardie node Ek soek is. 388 00:20:17,690 --> 00:20:22,110 En so in hierdie sin, soek op 'n geskakelde lys is altyd n. 389 00:20:22,110 --> 00:20:23,040 Dit is altyd n. 390 00:20:23,040 --> 00:20:25,690 Dit is altyd in lineêre tyd. 391 00:20:25,690 --> 00:20:28,470 >> En so die kode in wat voer ons hierdie, en dit 392 00:20:28,470 --> 00:20:32,620 is 'n bietjie nuut vir julle omdat julle ouens het nie regtig gepraat oor of ooit 393 00:20:32,620 --> 00:20:35,000 gesien wenke oor hoe om soek deur wysers, 394 00:20:35,000 --> 00:20:37,670 so ons sal loop deur hierdie baie, baie stadig. 395 00:20:37,670 --> 00:20:40,200 So Bool search, regs, laat dink ons ​​wil 396 00:20:40,200 --> 00:20:42,820 om 'n funksie genoem te skep soek dat ware terug 397 00:20:42,820 --> 00:20:46,820 as jy 'n waarde in die verband gevind lys, en is dit terug valse anders. 398 00:20:46,820 --> 00:20:50,030 Node star lys is tans net die wyser 399 00:20:50,030 --> 00:20:52,960 om die eerste item in jou geskakelde lys. 400 00:20:52,960 --> 00:20:56,700 int N is die waarde wat jy soek in die lys. 401 00:20:56,700 --> 00:20:58,770 >> So node star wyser gelyk lys. 402 00:20:58,770 --> 00:21:00,970 Dit beteken dat ons die opstel is en die skep van 'n wyser 403 00:21:00,970 --> 00:21:03,592 dat die eerste node binnekant van die lys. 404 00:21:03,592 --> 00:21:04,300 Almal met my? 405 00:21:04,300 --> 00:21:06,530 So as ons was om te gaan terug hier, sou ek 406 00:21:06,530 --> 00:21:13,850 geïnisialiseer 'n wyser wat verwys na die hoof van alles wat die lys is. 407 00:21:13,850 --> 00:21:18,600 >> En dan wanneer jy hier kom neer, terwyl wyser nie gelyk nul, 408 00:21:18,600 --> 00:21:22,160 sodat die lus in wat ons is gaan dan wees kameelkoei 409 00:21:22,160 --> 00:21:25,940 die res van ons lys, want wat gebeur wanneer wyser gelyk null? 410 00:21:25,940 --> 00:21:27,550 Ons weet dat ons have-- 411 00:21:27,550 --> 00:21:28,450 >> GEHOOR: [onhoorbaar] 412 00:21:28,450 --> 00:21:31,491 >> ANDI Peng: Presies, so ons weet dat ons het die einde van die lys bereik, reg? 413 00:21:31,491 --> 00:21:34,470 As jy hier gaan terug, elke node moet op 'n ander node 414 00:21:34,470 --> 00:21:36,550 en so aan en so voort totdat jy uiteindelik getref 415 00:21:36,550 --> 00:21:41,589 die stert van jou geskakelde lys, wat 'n wyser het wat net 416 00:21:41,589 --> 00:21:43,130 nêrens anders as geen punt. 417 00:21:43,130 --> 00:21:47,510 En sodat jy basies weet dat jou lys is daar nog steeds 418 00:21:47,510 --> 00:21:50,900 totdat wyser nie gelyk null want sodra dit gelyk nul, 419 00:21:50,900 --> 00:21:53,310 jy weet dat daar is geen dinge meer. 420 00:21:53,310 --> 00:21:56,930 >> Dit is dus die lus in wat ons is gaan na die werklike soek het. 421 00:21:56,930 --> 00:22:01,690 En as die pointer-- sien jy dat die soort van pyl funksie daar? 422 00:22:01,690 --> 00:22:06,930 So as wyser punte N, as die wyser op n gelyk gelyk N, 423 00:22:06,930 --> 00:22:09,180 so dit beteken dat indien die wyser dat jy 424 00:22:09,180 --> 00:22:13,420 soek vir die einde van elke node is eintlik gelyk aan die waarde 425 00:22:13,420 --> 00:22:15,990 jy soek, dan jy wil om waar te keer. 426 00:22:15,990 --> 00:22:19,280 So basies, as jy op 'n node wat het die waarde wat jy soek, 427 00:22:19,280 --> 00:22:23,550 jy weet dat jy is in staat wees om suksesvol te soek. 428 00:22:23,550 --> 00:22:27,150 >> Andersins, jy wil in te stel jou muis na die volgende knoop. 429 00:22:27,150 --> 00:22:28,850 Dit is wat die lyn hier doen. 430 00:22:28,850 --> 00:22:31,750 Wyser gelyk wyser volgende. 431 00:22:31,750 --> 00:22:33,360 Almal sien hoe dit werk? 432 00:22:33,360 --> 00:22:36,580 >> En in wese gaan jy net deurkruis die geheel van die lys, 433 00:22:36,580 --> 00:22:41,920 Herstel jou muis elke keer tot jy uiteindelik getref die einde van die lys. 434 00:22:41,920 --> 00:22:45,030 En jy weet dat daar geen meer nodes om te soek deur, 435 00:22:45,030 --> 00:22:47,999 en dan kan jy terug valse omdat julle weet dat, oh, goed, 436 00:22:47,999 --> 00:22:50,540 as ek in staat om te soek gewees het deur die geheel van die lys. 437 00:22:50,540 --> 00:22:54,530 As in hierdie voorbeeld, as ek wou om te kyk vir die waarde van 10, 438 00:22:54,530 --> 00:22:57,250 en ek begin by die hoof en Ek soek al die pad af, 439 00:22:57,250 --> 00:23:00,550 en ek het uiteindelik na hierdie, wat 'n wyser wat verwys na nul 440 00:23:00,550 --> 00:23:04,415 Ek weet dat, crap, ek dink 10 is nie in hierdie lys, want ek kon dit nie vind nie. 441 00:23:04,415 --> 00:23:06,520 En ek is aan die einde van die lys. 442 00:23:06,520 --> 00:23:11,040 En in watter geval jy weet Ek gaan valse terugkeer. 443 00:23:11,040 --> 00:23:12,900 >> Laat dit week in vir 'n bietjie. 444 00:23:12,900 --> 00:23:17,350 Dit sal mooi wees belangrik vir jou pset. 445 00:23:17,350 --> 00:23:21,140 Die logika van dit is baie eenvoudig, miskien sintakties net die uitvoering daarvan. 446 00:23:21,140 --> 00:23:23,365 Julle wil maak seker dat jy verstaan. 447 00:23:23,365 --> 00:23:25,870 448 00:23:25,870 --> 00:23:27,650 Koel. 449 00:23:27,650 --> 00:23:32,560 >> OK, so hoe sou ons invoeging nodes, regs, 450 00:23:32,560 --> 00:23:35,380 in 'n lys want onthou wat die wat van die voordele 451 00:23:35,380 --> 00:23:39,230 van 'n geskakelde lys versus 'n skikking in terme van die stoor? 452 00:23:39,230 --> 00:23:41,110 >> GEHOOR: Dis dinamiese, sodat dit makliker is aan- 453 00:23:41,110 --> 00:23:43,180 >> ANDI Peng: Presies, so dit is dinamiese, wat 454 00:23:43,180 --> 00:23:46,880 beteken dat dit kan uitbrei en krimp afhangende van die gebruiker se behoeftes. 455 00:23:46,880 --> 00:23:56,570 En so, in hierdie sin, ons hoef nie onnodige geheue mors, want ek 456 00:23:56,570 --> 00:24:00,850 as ek nie weet hoeveel waardes Ek wil op te slaan, is dit nie sin maak vir my 457 00:24:00,850 --> 00:24:04,310 om 'n skikking te skep, omdat as ek wil 10 waardes te stoor 458 00:24:04,310 --> 00:24:08,380 en Ek skep 'n skikking van 1000, wat 'n baie vermors geheue, toegeken. 459 00:24:08,380 --> 00:24:11,180 Dit is hoekom ons wil gebruik om 'n verband lys in staat wees om dinamies 460 00:24:11,180 --> 00:24:13,860 verander of krimp ons grootte. 461 00:24:13,860 --> 00:24:17,040 >> En so wat maak invoeging 'n bietjie meer ingewikkeld. 462 00:24:17,040 --> 00:24:20,810 Aangesien ons kan nie lukraak toegang elemente die manier waarop ons 'n skikking sou van. 463 00:24:20,810 --> 00:24:24,270 As ek wil 'n element te voeg in die sewende indeks 464 00:24:24,270 --> 00:24:26,930 Ek kan dit net voeg in die sewende indeks. 465 00:24:26,930 --> 00:24:30,020 Op 'n geskakelde lys, is dit nie baie werk so maklik, 466 00:24:30,020 --> 00:24:34,947 en so as ons wou voeg die een wat hier in die geskakelde lys, 467 00:24:34,947 --> 00:24:36,280 visueel, dit is baie maklik om te sien. 468 00:24:36,280 --> 00:24:39,363 Ons wil net om dit reg daar te plaas, reg aan die begin van die lys, 469 00:24:39,363 --> 00:24:40,840 reg na kop. 470 00:24:40,840 --> 00:24:44,579 >> Maar die manier waarop ons moet toewys die wysers is 'n bietjie gekronkelde 471 00:24:44,579 --> 00:24:47,620 of, logies, maak dit sin, maar jy wil om seker te maak dat jy dit het 472 00:24:47,620 --> 00:24:50,250 heeltemal af, omdat die laaste ding wat jy wil 473 00:24:50,250 --> 00:24:52,990 is om 'n wyser toewys die manier wat ons hier doen. 474 00:24:52,990 --> 00:24:58,170 As jy die dereference verwysing van kop tot 1, 475 00:24:58,170 --> 00:25:01,086 dan is almal van 'n skielike die res van jou geskakelde lys 476 00:25:01,086 --> 00:25:04,680 verlore, want jy het nie eintlik het 'n tydelike enigiets. 477 00:25:04,680 --> 00:25:06,220 Dit is gewys op die 2. 478 00:25:06,220 --> 00:25:10,080 As jy die wyser, dan is die toewys res van jou lys is totaal verlore. 479 00:25:10,080 --> 00:25:13,310 So jy wil wees baie, baie versigtig hier 480 00:25:13,310 --> 00:25:17,010 eerste toewys die wyser van alles wat jy 481 00:25:17,010 --> 00:25:20,150 wil plaas in waar jy wil, en dan sal jy 482 00:25:20,150 --> 00:25:22,710 kan dereference die res van jou lys. 483 00:25:22,710 --> 00:25:25,250 >> So dit geld vir waar jy probeer om te voeg in. 484 00:25:25,250 --> 00:25:27,520 As jy wil te voeg by die kop, as jy hier wil beantwoord, 485 00:25:27,520 --> 00:25:29,455 as jy wil voeg by die einde, goed, die einde Ek 486 00:25:29,455 --> 00:25:30,910 dink jy wil net het geen wyser, maar jy 487 00:25:30,910 --> 00:25:33,830 wil seker maak dat jy dit nie doen nie verloor die res van jou lys. 488 00:25:33,830 --> 00:25:36,640 Jy wil altyd om seker te maak jou nuwe node wys 489 00:25:36,640 --> 00:25:39,330 teenoor alles wat jy wil voeg in, 490 00:25:39,330 --> 00:25:42,170 en dan kan jy voeg die aaneenskakeling op. 491 00:25:42,170 --> 00:25:43,330 Almal duidelik? 492 00:25:43,330 --> 00:25:45,427 >> Dit gaan wees een van die werklike kwessies. 493 00:25:45,427 --> 00:25:48,010 Een van die mees belangrike kwessies jy gaan op jou pset 494 00:25:48,010 --> 00:25:51,340 is dat jy gaan om te probeer om te skep 'n geskakelde lys en voeg dinge 495 00:25:51,340 --> 00:25:53,340 maar dan net verloor die res van jou geskakelde lys. 496 00:25:53,340 --> 00:25:54,900 En jy gaan om te wees soos ek weet nie hoekom dit gebeur? 497 00:25:54,900 --> 00:25:58,040 En dit is 'n pyn om te gaan deur en soek al jou wenke. 498 00:25:58,040 --> 00:26:02,100 >> En ek waarborg jou op hierdie pset, skryf en teken hierdie nodes uit 499 00:26:02,100 --> 00:26:03,344 sal baie, baie nuttig. 500 00:26:03,344 --> 00:26:06,010 So kan jy heeltemal tred te hou van waar al jou wenke is, 501 00:26:06,010 --> 00:26:08,540 wat verkeerd gaan, waar al jou nodes is, 502 00:26:08,540 --> 00:26:12,660 wat jy nodig het om te doen om toegang te verkry of voeg of te verwyder of enige van hulle. 503 00:26:12,660 --> 00:26:14,550 Almal goed met dit? 504 00:26:14,550 --> 00:26:15,050 Koel. 505 00:26:15,050 --> 00:26:19,300 506 00:26:19,300 --> 00:26:22,600 >> So as ons wou om te kyk na die kode? 507 00:26:22,600 --> 00:26:24,470 O, ek weet nie of ons kan the-- OK sien, so 508 00:26:24,470 --> 00:26:27,940 by die top al is dit is 'n funksie vernoem insetsel waar ons wil 509 00:26:27,940 --> 00:26:31,365 om int N voeg in die geskakelde lys. 510 00:26:31,365 --> 00:26:32,740 Ons gaan om te loop deur middel van hierdie. 511 00:26:32,740 --> 00:26:34,770 Dit is 'n baie van die kode, 'n baie nuwe sintaksis. 512 00:26:34,770 --> 00:26:36,220 Ons sal OK wees. 513 00:26:36,220 --> 00:26:39,120 >> So by die top, wanneer Ons wil niks te skep 514 00:26:39,120 --> 00:26:42,380 wat doen wat ons moet doen, veral as jy dit wil nie gestoor word op die stapel 515 00:26:42,380 --> 00:26:43,920 maar in die hoop? 516 00:26:43,920 --> 00:26:45,460 Ons gaan na 'n malloc, reg? 517 00:26:45,460 --> 00:26:48,240 So ons gaan 'n wyser skep. 518 00:26:48,240 --> 00:26:52,074 Knoop, pointer, nuwe gelykes malloc die grootte van 'n node 519 00:26:52,074 --> 00:26:53,740 omdat ons wil hê dat die node geskep. 520 00:26:53,740 --> 00:26:56,720 Ons wil hê dat die bedrag van geheue wat 'n node neem 521 00:26:56,720 --> 00:26:59,300 word toegeken vir die skepping van die nuwe knoop. 522 00:26:59,300 --> 00:27:02,270 >> En dan gaan ons kyk na sien as nuwe gelykes gelyk null. 523 00:27:02,270 --> 00:27:03,370 Onthou wat ons gesê het? 524 00:27:03,370 --> 00:27:06,470 Wat jy ook al malloc, wat moet jy altyd doen? 525 00:27:06,470 --> 00:27:09,490 Jy moet altyd kyk om te sien of wat null. 526 00:27:09,490 --> 00:27:13,620 >> Byvoorbeeld, as jou bedryfstelsel stelsel is heeltemal vol, 527 00:27:13,620 --> 00:27:17,060 as jy het nie meer geheue almal en jy probeer om malloc, 528 00:27:17,060 --> 00:27:18,410 dit sou null vir jou terug. 529 00:27:18,410 --> 00:27:21,094 En so as jy probeer om dit te gebruik toe dit wys na nul 530 00:27:21,094 --> 00:27:23,260 jy gaan nie in staat om toegang tot die inligting. 531 00:27:23,260 --> 00:27:27,010 En so as sodanig, ons wou maak seker dat wanneer jy mallocing, 532 00:27:27,010 --> 00:27:30,500 Jy is altyd om te kyk of dat die geheue wat aan jou gegee is null. 533 00:27:30,500 --> 00:27:33,670 En as dit is nie, dan kan ons beweeg met die res van ons kode. 534 00:27:33,670 --> 00:27:36,140 >> So ons gaan inisialiseer die nuwe knoop. 535 00:27:36,140 --> 00:27:39,050 Ons gaan om te doen nuwe N gelyk n. 536 00:27:39,050 --> 00:27:42,390 En dan gaan ons doen stel nuwe die wyser op die nuwe 537 00:27:42,390 --> 00:27:46,900 om null want nou is ons nie wil niks vir dit om te wys. 538 00:27:46,900 --> 00:27:48,755 Ons het geen idee waar dit gaan jy, 539 00:27:48,755 --> 00:27:50,630 en dan as ons wil plaas dit op die kop, 540 00:27:50,630 --> 00:27:53,820 dan kan ons toewys die wyser na die kop. 541 00:27:53,820 --> 00:27:58,530 Maak almal volg die logika waar wat gebeur? 542 00:27:58,530 --> 00:28:02,502 >> Al wat ons doen is die skep van 'n nuwe knoop, die opstel van die wyser na nul 543 00:28:02,502 --> 00:28:04,210 en dan gehou indiensneming dit aan die hoof as ons 544 00:28:04,210 --> 00:28:06,320 weet ons dit wil voeg by die kop. 545 00:28:06,320 --> 00:28:09,420 En dan is die hoof gaan wys na nuwe knoop. 546 00:28:09,420 --> 00:28:11,060 Almal is ok met dit? 547 00:28:11,060 --> 00:28:12,380 >> So dit is 'n twee-stap proses. 548 00:28:12,380 --> 00:28:14,760 Jy het die eerste assign alles wat jy skep. 549 00:28:14,760 --> 00:28:18,260 Stel dat wyser na die verwys, en dan moet jy 550 00:28:18,260 --> 00:28:21,400 kan soort van dereference die eerste wyser 551 00:28:21,400 --> 00:28:22,972 en wys dit na die nuwe knoop. 552 00:28:22,972 --> 00:28:25,680 Waar jy wil om dit te plaas, daardie logika gaan ware te hou. 553 00:28:25,680 --> 00:28:27,530 >> Dit is soort van soos die toeken tydelike veranderlikes. 554 00:28:27,530 --> 00:28:28,700 Onthou, jy het om seker te maak dat jy 555 00:28:28,700 --> 00:28:30,346 moenie die spoor van as jy uitruiling verloor nie. 556 00:28:30,346 --> 00:28:33,470 Jy wil om seker te maak dat jy 'n tydelike veranderlike wat soort van hou 557 00:28:33,470 --> 00:28:35,620 spoor van waar daardie ding gestoor sodat jy 558 00:28:35,620 --> 00:28:41,190 nie enige waarde verloor nie in die kursus van soos die rond met dit. 559 00:28:41,190 --> 00:28:42,710 >> OK, so-kode sal hier wees. 560 00:28:42,710 --> 00:28:45,020 Julle neem 'n blik na artikel. 561 00:28:45,020 --> 00:28:48,060 Dit sal daar wees. 562 00:28:48,060 --> 00:28:50,280 >> So ek dink hoe werk hierdie verskil as ons wou 563 00:28:50,280 --> 00:28:52,300 in te voeg in die middel of aan die einde? 564 00:28:52,300 --> 00:28:57,892 Is daar iemand het 'n idee van wat die pseudokode as die logiese verwysing 565 00:28:57,892 --> 00:29:00,350 dat ons sal neem as ons wou om dit te plaas in die middel? 566 00:29:00,350 --> 00:29:03,391 So as ons dit wou voeg by die kop, al wat ons doen, is 'n nuwe knoop. 567 00:29:03,391 --> 00:29:06,311 Ons stel die wyser van daardie nuwe node om ongeag die kop, 568 00:29:06,311 --> 00:29:08,310 en dan het ons die hoof om die nuwe node, reg? 569 00:29:08,310 --> 00:29:11,560 As ons wou dit voeg in die middel van die lys, wat sou ons moet doen? 570 00:29:11,560 --> 00:29:14,108 571 00:29:14,108 --> 00:29:16,110 >> GEHOOR: sou dit nog steeds 'n soortgelyke proses 572 00:29:16,110 --> 00:29:19,114 van soos die toeken wyser en dan toeken wat pointer, 573 00:29:19,114 --> 00:29:20,530 maar ons wil hê om daar te spoor. 574 00:29:20,530 --> 00:29:23,560 >> ANDI Peng: Presies, so presies dieselfde proses, behalwe jy 575 00:29:23,560 --> 00:29:27,820 het presies waar jy op te spoor wil hê dat die nuwe wyser in te gaan, 576 00:29:27,820 --> 00:29:44,790 so as ek wil voeg in die middel van gekoppelde list-- OK, 577 00:29:44,790 --> 00:29:46,370 Kom ons sê dit is ons geskakelde lys. 578 00:29:46,370 --> 00:29:49,500 As ons wil hê om dit reg hier te plaas, ons gaan 'n nuwe node skep. 579 00:29:49,500 --> 00:29:50,520 Ons gaan malloc. 580 00:29:50,520 --> 00:29:52,220 Ons gaan 'n nuwe node skep. 581 00:29:52,220 --> 00:29:55,940 Ons gaan die toewys wyser van hierdie node hier. 582 00:29:55,940 --> 00:29:58,335 >> Maar die probleem wat verskil van waar die kop is 583 00:29:58,335 --> 00:30:00,490 is dat ons presies geweet waar die kop is. 584 00:30:00,490 --> 00:30:01,930 Dit was reg by die eerste, reg? 585 00:30:01,930 --> 00:30:04,870 Maar hier het ons 'om tred te hou van waar ons dit in te voeg. 586 00:30:04,870 --> 00:30:07,930 As ons die inbring ons node hier, ons het 587 00:30:07,930 --> 00:30:12,270 om seker te maak dat die een vorige hierdie node 588 00:30:12,270 --> 00:30:14,172 is die een wat die wyser reassigns. 589 00:30:14,172 --> 00:30:16,380 So dan moet jy soort hou van twee dinge. 590 00:30:16,380 --> 00:30:19,420 As jy hou van waar hierdie hou node tans invoeging in. 591 00:30:19,420 --> 00:30:23,280 Jy moet ook op hoogte van waar hou die vorige node wat jy kyk na 592 00:30:23,280 --> 00:30:24,340 was ook daar. 593 00:30:24,340 --> 00:30:25,830 Almal goed met dit? 594 00:30:25,830 --> 00:30:26,500 OK. 595 00:30:26,500 --> 00:30:28,000 >> Hoe gaan in die einde? 596 00:30:28,000 --> 00:30:34,220 As ek dit wou voeg here-- as ek wou om 'n nuwe node by te voeg tot die einde van 'n lys, 597 00:30:34,220 --> 00:30:37,009 hoe kan ek gaan om dit te doen? 598 00:30:37,009 --> 00:30:39,300 GEHOOR: So tans die laaste een se wys na nul. 599 00:30:39,300 --> 00:30:40,960 ANDI Peng: Ja. 600 00:30:40,960 --> 00:30:43,560 Presies, so hierdie een tans daarop om te weet, 601 00:30:43,560 --> 00:30:46,720 en so dink ek, in hierdie sin, is dit baie maklik om by te voeg tot die einde van 'n lys. 602 00:30:46,720 --> 00:30:51,810 Al wat jy hoef te doen, is sit dit gelyk aan nul en dan boom. 603 00:30:51,810 --> 00:30:53,070 Reg daar, baie maklik. 604 00:30:53,070 --> 00:30:53,960 Baie eenvoudig. 605 00:30:53,960 --> 00:30:56,430 >> Baie soortgelyk aan die kop, maar logies jy 606 00:30:56,430 --> 00:30:59,690 wil seker maak dat die stappe neem jy die rigting van enige van dit te doen, 607 00:30:59,690 --> 00:31:01,500 jy die volgende saam. 608 00:31:01,500 --> 00:31:04,420 Dit is baie maklik om te, in die middel van die kode, kry gevang op, 609 00:31:04,420 --> 00:31:05,671 oh, ek het so baie verwysings. 610 00:31:05,671 --> 00:31:07,461 Ek weet nie waar enigiets wat dui op. 611 00:31:07,461 --> 00:31:09,170 Ek weet nie eens wat node Ek is. 612 00:31:09,170 --> 00:31:11,490 Wat gaan aan? 613 00:31:11,490 --> 00:31:13,620 >> Ontspan, kalmeer, neem 'n diep asem. 614 00:31:13,620 --> 00:31:15,530 Teken jou geskakelde lys. 615 00:31:15,530 --> 00:31:18,800 As jy sê, ek weet presies waar Ek het nodig om hierdie plaas in 616 00:31:18,800 --> 00:31:22,970 en ek weet presies hoe om toewys my wysers, baie, baie makliker om te beeld 617 00:31:22,970 --> 00:31:27,200 out-- baie, baie makliker om nie verdwaal in die foute van die kode. 618 00:31:27,200 --> 00:31:29,410 Almal is ok met dit? 619 00:31:29,410 --> 00:31:31,380 OK. 620 00:31:31,380 --> 00:31:35,120 >> So ek dink 'n konsep wat ons het nie regtig gepraat oor voor nou, 621 00:31:35,120 --> 00:31:38,131 en ek dink jy waarskynlik sal nie veel teëkom yet-- 622 00:31:38,131 --> 00:31:40,880 dit is soort van 'n gevorderde concept-- is dat ons eintlik 'n data 623 00:31:40,880 --> 00:31:43,900 struktuur bekend as 'n dubbel geskakelde lys. 624 00:31:43,900 --> 00:31:46,390 So as julle kan sien, Al wat ons doen is die skep van 625 00:31:46,390 --> 00:31:50,400 'n werklike waarde, 'n ekstra wyser op elkeen van ons nodes 626 00:31:50,400 --> 00:31:52,660 wat ook dui op die vorige node. 627 00:31:52,660 --> 00:31:58,170 So nie net ons het ons nodes dui op die volgende een. 628 00:31:58,170 --> 00:32:01,430 Hulle wys ook aan die vorige een. 629 00:32:01,430 --> 00:32:04,310 Ek gaan om te ignoreer hierdie twee nou. 630 00:32:04,310 --> 00:32:06,740 >> So dan het jy 'n ketting wat kan beide maniere beweeg, 631 00:32:06,740 --> 00:32:09,630 en dan is dit 'n bietjie makliker logies volg saam. 632 00:32:09,630 --> 00:32:11,896 Soos hier, in plaas van dop van, o, ek 633 00:32:11,896 --> 00:32:14,520 moet weet dat hierdie node is die een wat ek het om te toewys, 634 00:32:14,520 --> 00:32:17,532 Ek kan net gaan hier en net trek die vorige. 635 00:32:17,532 --> 00:32:19,490 Dan weet ek presies waar dit is, en dan sal jy 636 00:32:19,490 --> 00:32:21,130 nie aan die deurkruis geheel van die geskakelde lys. 637 00:32:21,130 --> 00:32:22,180 Dit is 'n bietjie makliker te maak. 638 00:32:22,180 --> 00:32:24,960 >> Maar as sodanig, dubbel jy die bedrag van die wysers, 639 00:32:24,960 --> 00:32:26,960 dit is dubbel die bedrag van die geheue. 640 00:32:26,960 --> 00:32:28,950 Dit is 'n baie van wysers om tred te hou. 641 00:32:28,950 --> 00:32:32,140 Dit is 'n bietjie meer ingewikkeld, maar dit is 'n bietjie meer gebruikersvriendelik afhangende 642 00:32:32,140 --> 00:32:34,080 op wat jy probeer om te bereik. 643 00:32:34,080 --> 00:32:36,910 >> So hierdie tipe van data struktuur heeltemal bestaan, 644 00:32:36,910 --> 00:32:40,280 en die struktuur vir baie, baie eenvoudige behalwe al wat jy het, is, 645 00:32:40,280 --> 00:32:43,850 in plaas van net 'n verwysing na die volgende, jy het ook 'n verwysing na die vorige. 646 00:32:43,850 --> 00:32:45,940 Dit is al wat die verskil was. 647 00:32:45,940 --> 00:32:47,740 Almal goed met dit? 648 00:32:47,740 --> 00:32:48,240 Koel. 649 00:32:48,240 --> 00:32:50,940 650 00:32:50,940 --> 00:32:53,280 >> Alle reg, sodat nou is ek om werklik waarskynlik spandeer 651 00:32:53,280 --> 00:32:56,870 soos 15 tot 20 minute of die grootste deel van die res van die tyd in artikel 652 00:32:56,870 --> 00:32:58,360 praat oor hash tabelle. 653 00:32:58,360 --> 00:33:02,590 Hoeveel van julle ouens pset5 spec gelees het? 654 00:33:02,590 --> 00:33:03,620 Alle reg, goed. 655 00:33:03,620 --> 00:33:06,160 Dit is hoër as die 50% van normaal. 656 00:33:06,160 --> 00:33:07,560 Dit is OK. 657 00:33:07,560 --> 00:33:10,345 >> So as julle sal sien, jy uitdaging in pset5 658 00:33:10,345 --> 00:33:16,790 sal wees om 'n woordeboek te implementeer waar jy laai meer as 140,000 woorde 659 00:33:16,790 --> 00:33:20,610 dat ons vir u en speltoets dit teen alle van die teks. 660 00:33:20,610 --> 00:33:22,580 Ons gee jou ewekansige stukke van die letterkunde. 661 00:33:22,580 --> 00:33:23,520 Ons gee jou die Odyssey. 662 00:33:23,520 --> 00:33:24,561 Ons gee jou die Ilias. 663 00:33:24,561 --> 00:33:26,350 Ons gee jou Austin Powers. 664 00:33:26,350 --> 00:33:28,220 >> En jou uitdaging sal wees om check spel 665 00:33:28,220 --> 00:33:31,760 elke enkele woord in alle van daardie woordeboeke 666 00:33:31,760 --> 00:33:34,960 wese met ons speltoetser. 667 00:33:34,960 --> 00:33:38,620 En dus is daar 'n paar dele van die skep van hierdie pset, 668 00:33:38,620 --> 00:33:41,970 die eerste wat jy wil wees staat is om werklik te laai 669 00:33:41,970 --> 00:33:43,970 al die woorde in jou woordeboek, en dan moet jy 670 00:33:43,970 --> 00:33:45,530 wil in staat wees om speltoets almal van hulle. 671 00:33:45,530 --> 00:33:48,780 En so as sodanig, jy gaan om te vereis 'n datastruktuur dat dit vinnig kan doen 672 00:33:48,780 --> 00:33:50,790 en doeltreffend en dinamiese. 673 00:33:50,790 --> 00:33:52,900 >> So ek dink die maklikste manier om dit te doen, moet jy 674 00:33:52,900 --> 00:33:55,010 sou waarskynlik Skep 'n skikking, reg? 675 00:33:55,010 --> 00:33:58,910 Die maklikste manier van die stoor is jy kan 'n verskeidenheid van 140,000 woorde te skep 676 00:33:58,910 --> 00:34:03,400 en net hulle almal te plaas daar en dan deurkruis hulle deur die binêre soek 677 00:34:03,400 --> 00:34:06,780 of deur keuses of not-- jammer dit is sorteer. 678 00:34:06,780 --> 00:34:10,729 Jy kan sorteer hulle en dan deurkruis hulle deur binêre soek, of net lineêre soek 679 00:34:10,729 --> 00:34:13,730 en net finale die woorde nie, maar dat neem 'n groot hoeveelheid van die geheue, 680 00:34:13,730 --> 00:34:15,190 en dit is nie baie doeltreffend nie. 681 00:34:15,190 --> 00:34:18,350 >> En so gaan ons begin praat oor maniere om 682 00:34:18,350 --> 00:34:20,110 ons hardloop tyd meer doeltreffend. 683 00:34:20,110 --> 00:34:23,190 En ons doel is om te kry konstante tyd waar 684 00:34:23,190 --> 00:34:25,810 Dit is amper soos skikkings, waar jy oombliklike toegang. 685 00:34:25,810 --> 00:34:28,560 As ek wou om te soek vir enigiets, Ek wil in staat wees om net, 686 00:34:28,560 --> 00:34:30,810 boom, vind dit presies, en trek dit uit. 687 00:34:30,810 --> 00:34:34,100 En so 'n struktuur waarin ons sal raak baie geheg 688 00:34:34,100 --> 00:34:37,569 in staat wees om toegang te verkry tot voortdurende tyd, hierdie heilige graal 689 00:34:37,569 --> 00:34:41,370 in programmering van konstante tyd word 'n hash tafel. 690 00:34:41,370 --> 00:34:45,370 En so het Dawid voorheen genoem die [Onhoorbaar] 'n bietjie in lesing 691 00:34:45,370 --> 00:34:49,100 maar ons gaan om werklik duik in diep hierdie week 692 00:34:49,100 --> 00:34:51,780 op 'n stuk wat betrekking is hoe 'n hash tafel werk. 693 00:34:51,780 --> 00:34:53,949 >> So die manier waarop 'n gemors tabel werk, byvoorbeeld, 694 00:34:53,949 --> 00:35:00,230 As ek wou 'n klomp van die woorde te stoor, 'n n klomp van die woorde in die Engelse taal, 695 00:35:00,230 --> 00:35:02,940 Ek kon teoreties sit piesang, appel, kiwi, mango, paar, 696 00:35:02,940 --> 00:35:04,980 en spanspek almal op net 'n skikking. 697 00:35:04,980 --> 00:35:07,044 Hulle kon almal pas in en word vind. 698 00:35:07,044 --> 00:35:09,210 Dit sou soort van 'n pyn wees om soek deur en toegang, 699 00:35:09,210 --> 00:35:12,920 maar die makliker manier om dit te doen is dat ons eintlik kan skep 'n struktuur 700 00:35:12,920 --> 00:35:15,680 bekend as 'n hash tafel waar ons hash. 701 00:35:15,680 --> 00:35:19,880 Ons loop al ons sleutels deur 'n hash funksie, 'n vergelyking, 702 00:35:19,880 --> 00:35:22,600 wat draai hulle almal in 'n soort van 'n waarde 703 00:35:22,600 --> 00:35:28,740 wat dan kan ons slaan op in wese 'n verskeidenheid van geskakelde lys. 704 00:35:28,740 --> 00:35:32,570 >> En so hier, as ons wou om Engelse woorde te slaan, 705 00:35:32,570 --> 00:35:37,250 ons kon potensieel net, ek doen nie weet, draai al die eerste letters 706 00:35:37,250 --> 00:35:39,630 in 'n soort van 'n aantal. 707 00:35:39,630 --> 00:35:43,140 En so, byvoorbeeld, as ek wou A tot sinoniem met apple-- wees 708 00:35:43,140 --> 00:35:47,460 of met die indeks van 0, en B sinoniem met 1 te wees, 709 00:35:47,460 --> 00:35:51,030 kan ons 26 inskrywings wat kan net stoor 710 00:35:51,030 --> 00:35:53,610 al die letters van die alfabet dat ons sal begin met. 711 00:35:53,610 --> 00:35:56,130 En dan kan ons ' appel op die indeks van 0. 712 00:35:56,130 --> 00:35:59,160 Ons kan piesang het by die indeks van 1, spanspek by die indeks van 2, 713 00:35:59,160 --> 00:36:00,540 en so aan en so voort. 714 00:36:00,540 --> 00:36:04,460 En dus as ek wou om te soek my hash tafel en toegang appel, 715 00:36:04,460 --> 00:36:07,560 Ek weet appel begin met 'n A, en ek weet presies 716 00:36:07,560 --> 00:36:10,860 dat dit moet wees en die hash tafel by indeks 0 omdat 717 00:36:10,860 --> 00:36:13,620 van die funksie voorheen toegeken. 718 00:36:13,620 --> 00:36:16,572 >> So ek weet nie, ons is 'n gebruiker program waar 719 00:36:16,572 --> 00:36:18,780 jy sal aangekla word arbitrarily-- nie arbitrêr, 720 00:36:18,780 --> 00:36:22,530 met die probeer om denkend dink goeie vergelykings 721 00:36:22,530 --> 00:36:25,460 in staat wees om te versprei uit al jou waardes 722 00:36:25,460 --> 00:36:29,370 in 'n manier wat hulle kan maklik toegang dit later met soos 'n vergelyking 723 00:36:29,370 --> 00:36:31,130 dat jy, jouself, te leer ken. 724 00:36:31,130 --> 00:36:35,210 So in die sin as ek wou om te gaan na mango, weet ek, o, dit begin met m. 725 00:36:35,210 --> 00:36:37,134 Dit moet by die indeks van 12. 726 00:36:37,134 --> 00:36:38,800 Ek hoef nie te soek deur enigiets. 727 00:36:38,800 --> 00:36:42,080 Ek weet exactly-- ek kon net gaan die indeks van 12 en trek dat uit. 728 00:36:42,080 --> 00:36:45,520 >> Almal duidelik hoe 'n funksie hash tafel se werk? 729 00:36:45,520 --> 00:36:48,380 Dit is soort van net 'n meer komplekse skikking. 730 00:36:48,380 --> 00:36:50,010 Dit is al wat dit is. 731 00:36:50,010 --> 00:36:51,630 OK. 732 00:36:51,630 --> 00:36:57,690 >> So ek dink ons ​​loop in hierdie kwessie van wat 733 00:36:57,690 --> 00:37:06,390 gebeur as jy meer dinge wat gee jou dieselfde indeks? 734 00:37:06,390 --> 00:37:10,570 So sê ons funksie, al is dit gedoen het, was dat die eerste letter 735 00:37:10,570 --> 00:37:14,490 en draai dit in 'n onderskeie 0 deur 25 indeks. 736 00:37:14,490 --> 00:37:17,137 Dit is heeltemal fyn, indien jy het net een van elk. 737 00:37:17,137 --> 00:37:18,970 Maar die tweede jy begin met meer, is jy 738 00:37:18,970 --> 00:37:20,910 gaan hê wat 'n botsing genoem. 739 00:37:20,910 --> 00:37:25,580 >> So as ek probeer om in te voeg in 'n hash begrawe tafel wat reeds piesang op dit, 740 00:37:25,580 --> 00:37:27,870 wat gaan gebeur wanneer jy probeer om in te voeg dit? 741 00:37:27,870 --> 00:37:30,930 Slegte dinge omdat piesang reeds binne die indeks bestaan 742 00:37:30,930 --> 00:37:33,800 wat jy wil om dit te stoor in. 743 00:37:33,800 --> 00:37:35,560 Berry soort is soos, ah, wat moet ek doen? 744 00:37:35,560 --> 00:37:37,080 Ek weet nie waar om te gaan. 745 00:37:37,080 --> 00:37:38,410 Hoe kan ek hierdie los? 746 00:37:38,410 --> 00:37:41,150 >> En so julle ouens sal soort sien ons doen dit moeilike ding 747 00:37:41,150 --> 00:37:44,810 waar ons kan soort van eintlik skep geskakelde lys in ons skikkings. 748 00:37:44,810 --> 00:37:46,840 En so het die maklikste manier om te dink oor hierdie, 749 00:37:46,840 --> 00:37:50,830 al hash tabel is 'n verskeidenheid van geskakelde lyste. 750 00:37:50,830 --> 00:37:55,670 En so, in die sin dat, jy het hierdie pragtige verskeidenheid van wenke, 751 00:37:55,670 --> 00:37:58,740 en dan elke wyser in wat waarde, in die indeks, 752 00:37:58,740 --> 00:38:00,740 kan eintlik verwys na ander dinge. 753 00:38:00,740 --> 00:38:05,720 En so het jy al hierdie afsonderlike kettings af kom een ​​groot verskeidenheid. 754 00:38:05,720 --> 00:38:07,960 >> En so hier, as ek wou berry voeg, 755 00:38:07,960 --> 00:38:11,220 Ek weet nie, OK, ek gaan om insette dit deur my hash funksie. 756 00:38:11,220 --> 00:38:15,070 Ek gaan om te eindig met die indeks van 1, en dan gaan ek in staat wees om 757 00:38:15,070 --> 00:38:20,410 net 'n kleiner subset van hierdie reuse 140,000 woord woordeboek. 758 00:38:20,410 --> 00:38:24,220 En dan kan ek net kyk deur 1/26 van daardie. 759 00:38:24,220 --> 00:38:27,910 >> En so kan ek net voeg berry voor of na piesang 760 00:38:27,910 --> 00:38:28,820 in hierdie geval? 761 00:38:28,820 --> 00:38:29,700 Na, reg? 762 00:38:29,700 --> 00:38:33,920 En so gaan jy wil voeg hierdie node na piesang, 763 00:38:33,920 --> 00:38:36,667 en so gaan jy voeg aan die stert van die geskakelde lys. 764 00:38:36,667 --> 00:38:38,500 Ek gaan om terug te gaan hierdie vorige skyfie, 765 00:38:38,500 --> 00:38:40,680 sodat jy kan sien hoe ouens hash funksie werk. 766 00:38:40,680 --> 00:38:43,980 >> So hash funksie is hierdie vergelyking dat jy 'n soort van jou insette 767 00:38:43,980 --> 00:38:46,940 deur na kry wat indeks jy wil dit na toewys. 768 00:38:46,940 --> 00:38:51,130 En so, in hierdie voorbeeld, al wat ons wou om te doen, was om die eerste brief, 769 00:38:51,130 --> 00:38:55,890 draai wat in 'n indeks, dan sal ons kan stoor wat in ons hash funksie. 770 00:38:55,890 --> 00:39:00,160 Al wat ons hier doen, is ons omskepping van die eerste brief. 771 00:39:00,160 --> 00:39:04,770 So keykey [0] is net die eerste letter van watter string ons het nie, 772 00:39:04,770 --> 00:39:05,720 ons verby in. 773 00:39:05,720 --> 00:39:09,740 Ons omskakeling wat na die boonste en ons trek deur hoofletters A, 774 00:39:09,740 --> 00:39:11,740 so al wat doen gee ons 'n aantal 775 00:39:11,740 --> 00:39:13,670 waarop ons ons waardes hash op. 776 00:39:13,670 --> 00:39:16,550 >> En dan gaan ons terugkeer hash modulus grootte. 777 00:39:16,550 --> 00:39:19,340 Wees baie, baie versigtig want, teoreties, hier 778 00:39:19,340 --> 00:39:21,870 jou hash waarde kan wees oneindig. 779 00:39:21,870 --> 00:39:23,660 Dit kon net gaan op en op en op. 780 00:39:23,660 --> 00:39:26,080 Dit kan regtig 'n paar, regtig groot waarde, 781 00:39:26,080 --> 00:39:29,849 maar omdat jou hash tafel wat jy gemaak het net 26 indekse, 782 00:39:29,849 --> 00:39:31,890 jy wil om seker te maak jou modulusing sodat jy 783 00:39:31,890 --> 00:39:33,848 nie run-- dit is dieselfde ding as jou queue-- 784 00:39:33,848 --> 00:39:36,320 sodat jy nie afloop van die onderkant van jou hash funksie. 785 00:39:36,320 --> 00:39:39,210 >> Jy wil dit om te draai terug op dieselfde manier in [onhoorbaar] wanneer 786 00:39:39,210 --> 00:39:41,750 jy moes soos 'n baie, baie groot brief jy 787 00:39:41,750 --> 00:39:43,740 wou nie dat net loop af die einde. 788 00:39:43,740 --> 00:39:46,948 Dieselfde ding hier, wil jy om seker te maak dit nie afloop van die einde deur die wikkel 789 00:39:46,948 --> 00:39:48,330 om na die top van die tafel. 790 00:39:48,330 --> 00:39:50,530 So dit is net 'n baie eenvoudige hash funksie. 791 00:39:50,530 --> 00:39:56,570 Al wat gedoen het, was die eerste letter van wat ook al ons insette was 792 00:39:56,570 --> 00:40:01,660 en draai wat in 'n indeks wat ons kon in ons hash tafel. 793 00:40:01,660 --> 00:40:05,450 >> Ja, en so soos ek gesê het, die manier waarop ons botsings te los 794 00:40:05,450 --> 00:40:09,330 in ons hash tabelle word met, wat ons noem, chaining. 795 00:40:09,330 --> 00:40:13,860 So as jy probeer om in te voeg verskeie woorde wat begin met die dieselfde ding, 796 00:40:13,860 --> 00:40:16,145 jy gaan een hash waarde het. 797 00:40:16,145 --> 00:40:18,770 Avokado en appel, as jy het voer dit deur ons hash funksie, 798 00:40:18,770 --> 00:40:21,450 gaan jy die gee dieselfde nommer, die aantal 0. 799 00:40:21,450 --> 00:40:24,550 En so het die manier waarop ons los dit dat ons kan eintlik soort van hulle te skakel 800 00:40:24,550 --> 00:40:27,010 saam via geskakelde lyste. 801 00:40:27,010 --> 00:40:29,600 >> En so in hierdie sin, julle ouens kan sien soort 802 00:40:29,600 --> 00:40:32,640 hoe data strukture wat ons het al voorheen die opstel 803 00:40:32,640 --> 00:40:35,870 soos 'n rosyntjie geskakelde lys soort saam kan kom in een. 804 00:40:35,870 --> 00:40:38,860 En dan kan jy ver te skep meer doeltreffende data strukture 805 00:40:38,860 --> 00:40:43,350 wat kan groter hoeveelhede hanteer data, wat dinamiese grootte afhangende 806 00:40:43,350 --> 00:40:44,870 op jou behoeftes. 807 00:40:44,870 --> 00:40:45,620 Almal duidelik? 808 00:40:45,620 --> 00:40:47,580 Almal soort duidelik op wat hier gebeur? 809 00:40:47,580 --> 00:40:52,110 >> As ek wou insert-- wat is 'n vrugte wat begin met, ek weet nie, 810 00:40:52,110 --> 00:40:54,726 B, behalwe berry, piesang. 811 00:40:54,726 --> 00:40:55,710 >> GEHOOR: Blackberry. 812 00:40:55,710 --> 00:40:57,910 >> ANDI Peng: Blackberry, Blackberry. 813 00:40:57,910 --> 00:41:00,530 Waar kom blackberry gaan hier? 814 00:41:00,530 --> 00:41:04,251 Wel, ons het eintlik nie gesorteer hierdie nie, maar teoreties 815 00:41:04,251 --> 00:41:06,250 as ons wou dit hê in alfabetiese volgorde, 816 00:41:06,250 --> 00:41:07,944 waar moet BlackBerry gaan? 817 00:41:07,944 --> 00:41:09,210 >> GEHOOR: [onhoorbaar] 818 00:41:09,210 --> 00:41:11,100 >> ANDI Peng: Presies, na hier, reg? 819 00:41:11,100 --> 00:41:14,950 Maar aangesien dit is baie moeilik om reorder-- Ek dink dit is aan julle. 820 00:41:14,950 --> 00:41:17,920 Julle kan heeltemal implementeer wat jy wil. 821 00:41:17,920 --> 00:41:20,730 Die meer doeltreffende manier van hierdie dalk doen 822 00:41:20,730 --> 00:41:24,570 sou wees om te sorteer jou gekoppelde lys in alfabetiese volgorde, 823 00:41:24,570 --> 00:41:26,520 en so wanneer jy invoeging dinge wat jy wil 824 00:41:26,520 --> 00:41:28,632 om seker te wees om hulle te voeg in alfabetiese volgorde 825 00:41:28,632 --> 00:41:30,590 sodat dan wanneer jy probeer om hulle te soek, 826 00:41:30,590 --> 00:41:32,410 jy hoef nie alles te deurkruis. 827 00:41:32,410 --> 00:41:35,290 Jy weet presies waar dit is, en dit is makliker. 828 00:41:35,290 --> 00:41:39,100 >> Maar as jy soort van het dinge lukraak afgewissel, 829 00:41:39,100 --> 00:41:41,420 jy nog gaan hê om dit anyways deurkruis. 830 00:41:41,420 --> 00:41:44,990 En so as ek wou net voeg BlackBerry hier 831 00:41:44,990 --> 00:41:47,470 en ek wou om te soek na dit weet ek, o, BlackBerry 832 00:41:47,470 --> 00:41:52,012 moet begin met die indeks van 1, so ek weet onmiddellik net soek op 1. 833 00:41:52,012 --> 00:41:53,970 En dan kan ek soort van deurkruis die geskakelde lys 834 00:41:53,970 --> 00:41:56,120 totdat ek kry Blackberry, en then-- ja? 835 00:41:56,120 --> 00:41:59,550 >> GEHOOR: As jy probeer om create-- Ek dink dit is soos 'n baie eenvoudige hash 836 00:41:59,550 --> 00:42:00,050 funksie. 837 00:42:00,050 --> 00:42:02,835 En as ons wou doen verskeie lae van daardie wil, 838 00:42:02,835 --> 00:42:05,870 OK, ons wil skei in soos al die alfabetiese letters 839 00:42:05,870 --> 00:42:09,040 en dan weer na 'n ander stel graag alfabetiese letters in daardie, 840 00:42:09,040 --> 00:42:11,715 Ons sit soos 'n hash tafel binne 'n hash tafel, 841 00:42:11,715 --> 00:42:13,256 of soos 'n funksie binne 'n funksie? 842 00:42:13,256 --> 00:42:14,880 Of is that-- 843 00:42:14,880 --> 00:42:17,510 >> ANDI Peng: So jou hash function-- jou hash tafel 844 00:42:17,510 --> 00:42:19,360 kan so groot wees as jy dit wil hê. 845 00:42:19,360 --> 00:42:21,930 So in hierdie sin, het ek gedink dit was baie maklik, baie 846 00:42:21,930 --> 00:42:25,320 eenvoudig vir my om net soort gebaseer op die letters van die eerste woord. 847 00:42:25,320 --> 00:42:28,690 En so is daar net 26 opsies. 848 00:42:28,690 --> 00:42:32,650 Ek kan net 26 opsies uit 0-25, want hulle kan net 849 00:42:32,650 --> 00:42:36,510 begin van A tot Z. Maar as jy wou om by te voeg, miskien, meer kompleksiteit 850 00:42:36,510 --> 00:42:39,260 of vinniger te hardloop tyd om jou hash tafel, jy absoluut 851 00:42:39,260 --> 00:42:40,760 kan allerhande dinge te doen. 852 00:42:40,760 --> 00:42:43,330 Jy kan jou eie te maak vergelyking wat gee jou 853 00:42:43,330 --> 00:42:48,000 meer verspreiding in jou woorde, dan wanneer jy soek, 854 00:42:48,000 --> 00:42:49,300 dit gaan vinniger. 855 00:42:49,300 --> 00:42:52,100 >> Dit is heeltemal aan jou ouens hoe jy wil om te implementeer nie. 856 00:42:52,100 --> 00:42:55,140 Dink aan dit as net emmers. 857 00:42:55,140 --> 00:42:57,376 As ek wou hê 26 emmers, ek gaan 858 00:42:57,376 --> 00:42:59,420 dinge in die emmers te sorteer. 859 00:42:59,420 --> 00:43:02,980 Maar ek gaan 'n klomp het dinge in elke emmer, 860 00:43:02,980 --> 00:43:05,890 so as jy wil om dit te maak vinniger en meer doeltreffende, 861 00:43:05,890 --> 00:43:07,190 laat my 'n honderd emmers. 862 00:43:07,190 --> 00:43:09,290 >> Maar dan moet jy om uit te vind 'n manier om dinge te sorteer sodat hulle 863 00:43:09,290 --> 00:43:11,040 in die regte emmer hulle behoort te wees in. 864 00:43:11,040 --> 00:43:13,331 Maar dan wanneer jy eintlik wil om te kyk na die emmer, 865 00:43:13,331 --> 00:43:16,410 dit is 'n baie vinniger, want daar is minder dinge in elke emmer. 866 00:43:16,410 --> 00:43:20,250 En so, ja, dit is eintlik die truuk vir julle in pset5 867 00:43:20,250 --> 00:43:22,360 is dat jy sal wees uitgedaag om net te skep 868 00:43:22,360 --> 00:43:26,170 alles wat die mees doeltreffende funksie wat jy kan dink om te wees 869 00:43:26,170 --> 00:43:28,520 in staat wees om op te slaan en gaan hierdie waardes. 870 00:43:28,520 --> 00:43:30,840 >> Heeltemal aan julle ouens maar jy wil om dit te doen, 871 00:43:30,840 --> 00:43:32,229 maar dit is 'n baie goeie punt. 872 00:43:32,229 --> 00:43:34,520 Dat die soort van logika wat jy wil begin dink oor 873 00:43:34,520 --> 00:43:37,236 is, wel, hoekom nie ek nie meer emmers. 874 00:43:37,236 --> 00:43:39,527 En dan moet ek soek minder dinge, en dan miskien is ek 875 00:43:39,527 --> 00:43:41,640 'n ander hash funksie. 876 00:43:41,640 --> 00:43:45,500 >> Ja, daar is 'n baie maniere om dit te doen pset, sommige is vinniger as ander. 877 00:43:45,500 --> 00:43:50,630 Ek is heeltemal gaan net sien hoe vinnige was die vinnigste julle sal 878 00:43:50,630 --> 00:43:55,170 in staat wees om jou funksies om te werk. 879 00:43:55,170 --> 00:43:58,176 OK, almal goed op aaneenskakeling en hash tabelle? 880 00:43:58,176 --> 00:44:00,800 Dit is eintlik soos 'n baie eenvoudige konsep as jy daaroor dink. 881 00:44:00,800 --> 00:44:05,160 Al wat dit is, is alles wat skei u insette is in emmers, 882 00:44:05,160 --> 00:44:10,670 sorteer hulle, en dan soek die lyste wat daar in verband met. 883 00:44:10,670 --> 00:44:11,852 >> Koel. 884 00:44:11,852 --> 00:44:18,160 Alle reg, nou het ons 'n ander soort van data struktuur wat is bekend as 'n boom. 885 00:44:18,160 --> 00:44:20,850 Kom ons gaan op en praat oor drieë wat duidelik verskillende, 886 00:44:20,850 --> 00:44:22,330 maar in dieselfde kategorie. 887 00:44:22,330 --> 00:44:29,010 Wese, al 'n boom is in plaas organiseer data in die lineêre manier 888 00:44:29,010 --> 00:44:32,560 dat 'n hash tafel does-- jy weet, is dit 'n top en 'n onderkant 889 00:44:32,560 --> 00:44:37,900 en dan sal jy soort skakel af van it-- n boom het 'n top wat jy die wortel noem, 890 00:44:37,900 --> 00:44:40,220 en dan is dit het blare al rondom dit. 891 00:44:40,220 --> 00:44:42,390 >> En so al wat jy hier het is net die top node 892 00:44:42,390 --> 00:44:45,980 wat verwys na ander nodes dat punte meer nodes, en so aan en so voort. 893 00:44:45,980 --> 00:44:48,130 En so moet jy net verdeel takke. 894 00:44:48,130 --> 00:44:53,255 Dit is net 'n ander manier van organisering data, en omdat ons noem dit 'n boom, 895 00:44:53,255 --> 00:44:56,270 julle ouens just-- dit is net gemodelleer uit om te kyk soos 'n boom. 896 00:44:56,270 --> 00:44:57,670 Dit is hoekom ons noem dit bome. 897 00:44:57,670 --> 00:44:59,370 >> Hash tafel lyk soos 'n tafel. 898 00:44:59,370 --> 00:45:01,310 'N boom lyk net soos 'n boom. 899 00:45:01,310 --> 00:45:03,300 Al wat dit is, is 'n afsonderlike manier van organisering nodes 900 00:45:03,300 --> 00:45:06,020 afhangende van wat jou behoeftes is. 901 00:45:06,020 --> 00:45:11,810 >> So jy het 'n wortel en dan moet jy die blare. 902 00:45:11,810 --> 00:45:15,380 Die manier wat ons kan veral dink oor dit is 'n binêre boom 903 00:45:15,380 --> 00:45:18,150 'n binêre boom is net 'n spesifieke tipe van 'n boom 904 00:45:18,150 --> 00:45:22,450 waar elke knoop net punte om op max, twee ander nodes. 905 00:45:22,450 --> 00:45:25,434 En so hier het jy duidelike het simmetrie in jou boom 906 00:45:25,434 --> 00:45:28,600 wat maak dit makliker om te soort van kyk op watter waardes jy want dan is jy 907 00:45:28,600 --> 00:45:30,150 het altyd 'n links of 'n reg. 908 00:45:30,150 --> 00:45:33,150 Daar is nooit soos 'n links derde van links of 'n vierde van links. 909 00:45:33,150 --> 00:45:36,358 Dis net jy het 'n linker en 'n reg en jy kan soek een van die twee. 910 00:45:36,358 --> 00:45:38,980 En so hoekom is dit nuttig? 911 00:45:38,980 --> 00:45:40,980 Die manier waarop dit is bruikbaar is as jy op soek is 912 00:45:40,980 --> 00:45:42,890 om te soek deur waardes, reg? 913 00:45:42,890 --> 00:45:45,640 Eerder as die implementering van binêre soek in 'n fout skikking, 914 00:45:45,640 --> 00:45:49,260 as jy wou in staat wees om nodes voeg en neem nodes weg by wil en ook 915 00:45:49,260 --> 00:45:52,185 die behoud van die search vermoëns van binêre soek. 916 00:45:52,185 --> 00:45:54,560 So op hierdie manier, ons is soort van tricking-- onthou wanneer ons 917 00:45:54,560 --> 00:45:56,530 gesê geskakelde lyste kan nie binêre soek? 918 00:45:56,530 --> 00:46:01,700 Ons soort van die skep van 'n datastruktuur dat truuks wat in werkende. 919 00:46:01,700 --> 00:46:05,034 >> En so, want gekoppel lyste is lineêre, hulle het net 'n skakel een na die ander. 920 00:46:05,034 --> 00:46:06,950 Ons kan soort van het ander soort van wysers 921 00:46:06,950 --> 00:46:09,408 daardie punt om verskillende nodes wat ons kan help met die soektog. 922 00:46:09,408 --> 00:46:12,590 En so hier, as ek wou 'n binêre soekboom, 923 00:46:12,590 --> 00:46:14,090 Ek weet dat my middel as 55. 924 00:46:14,090 --> 00:46:18,280 Ek gaan net om te skep wat as my middel, as my wortel, 925 00:46:18,280 --> 00:46:20,770 en dan gaan ek het waardes spin af van dit. 926 00:46:20,770 --> 00:46:25,610 >> So hier, as ek gaan om te soek na die waarde van 66, kan ek begin by 55. 927 00:46:25,610 --> 00:46:27,310 Dit is 66 groter as 55? 928 00:46:27,310 --> 00:46:30,970 Ja, dit is nie, so ek weet ek moe soek i n die regte wyser van hierdie boom. 929 00:46:30,970 --> 00:46:32,440 Ek gaan na 77. 930 00:46:32,440 --> 00:46:35,367 OK, is 66 minder as of groter as 77? 931 00:46:35,367 --> 00:46:37,950 Dit is minder as, sodat jy weet, o, wat aan die linkerkant node wees. 932 00:46:37,950 --> 00:46:41,410 >> En so hier is ons soort van die behoud van al die groot dinge oor skikkings, 933 00:46:41,410 --> 00:46:44,420 so soos dinamiese resizing voorwerpe, wat 934 00:46:44,420 --> 00:46:49,530 in staat wees om in te voeg en te verwyder word nie, sonder om te bekommer oor die vaste 935 00:46:49,530 --> 00:46:50,370 bedrag van die ruimte. 936 00:46:50,370 --> 00:46:52,820 Ons het nog steeds al te bewaar daardie wonderlike dinge 937 00:46:52,820 --> 00:46:57,140 terwyl dit ook in staat is om die behoud van teken en soek tyd van binêre soek 938 00:46:57,140 --> 00:47:00,450 dat ons voorheen net in staat wees om 'n frase te kry. 939 00:47:00,450 --> 00:47:06,310 >> Cool data struktuur, soort komplekse te implementeer, die knoop. 940 00:47:06,310 --> 00:47:08,311 Soos jy kan sien, al is dit is die struct van die node 941 00:47:08,311 --> 00:47:10,143 is dat jy 'n links en 'n reg wyser. 942 00:47:10,143 --> 00:47:11,044 Dit is al wat dit is. 943 00:47:11,044 --> 00:47:12,960 So eerder as om net met 'n x of 'n vorige. 944 00:47:12,960 --> 00:47:15,920 Jy het 'n linker-of die reg, en dan jy kan soort skakel hulle saam 945 00:47:15,920 --> 00:47:16,836 maar jy so verkies. 946 00:47:16,836 --> 00:47:21,080 947 00:47:21,080 --> 00:47:24,270 >> OK, ons is eintlik gaan net 'n paar minute. 948 00:47:24,270 --> 00:47:25,790 So ons gaan hier terug te gaan. 949 00:47:25,790 --> 00:47:28,270 Soos ek gesê het voorheen, Ek soort van verduidelik 950 00:47:28,270 --> 00:47:31,520 die logika agter hoe ons sou soek deur middel van hierdie. 951 00:47:31,520 --> 00:47:33,860 Ons gaan om te probeer pseudocoding dit uit te sien 952 00:47:33,860 --> 00:47:38,000 as ons soort kan aansoek doen die dieselfde logika van binêre soek 953 00:47:38,000 --> 00:47:40,055 om 'n ander tipe van data-struktuur. 954 00:47:40,055 --> 00:47:45,049 As jy ouens wil neem soos 'n paar minute om net te dink oor hierdie. 955 00:47:45,049 --> 00:48:45,927 956 00:48:45,927 --> 00:48:46,925 OK. 957 00:48:46,925 --> 00:48:51,407 Alle reg, ek gaan eintlik net gee jy nie the--, 958 00:48:51,407 --> 00:48:52,990 ons oor die pseudokode sal praat eerste. 959 00:48:52,990 --> 00:48:56,580 So nie almal wil om 'n steek op te gee wat 960 00:48:56,580 --> 00:49:02,100 die eerste ding wat jy wil doen wanneer jy begin soek is? 961 00:49:02,100 --> 00:49:04,460 As ons soek die waarde van 66, wat is 962 00:49:04,460 --> 00:49:07,940 die eerste ding wat ons wil doen as ons wil binêre soek hierdie boom? 963 00:49:07,940 --> 00:49:10,760 >> GEHOOR: Jy wil na regs kyk en kyk links en sien [onhoorbaar] 964 00:49:10,760 --> 00:49:11,230 groter aantal. 965 00:49:11,230 --> 00:49:12,271 >> ANDI Peng: Ja, presies. 966 00:49:12,271 --> 00:49:15,350 So jy gaan om te kyk na jou wortel. 967 00:49:15,350 --> 00:49:18,180 Daar is baie maniere wat jy kan noem dit jou ouers node mense sê. 968 00:49:18,180 --> 00:49:21,317 Ek hou daarvan om te sê, want die wortel dit is soos die wortel van die boom. 969 00:49:21,317 --> 00:49:23,400 Jy gaan om te kyk na jou wortel node, en jy is 970 00:49:23,400 --> 00:49:26,940 gaan om te sien is 66 groter as of minder as 55. 971 00:49:26,940 --> 00:49:30,360 En as dit is groter as, wel, dit is groter as, waar ons wil om te kyk? 972 00:49:30,360 --> 00:49:32,000 Waar wil ons soek nou, reg? 973 00:49:32,000 --> 00:49:34,340 Ons wil die soek regter helfte van die boom. 974 00:49:34,340 --> 00:49:38,390 >> So ons het, gerieflik, 'n wyser wat verwys na die reg. 975 00:49:38,390 --> 00:49:44,325 En so kan ons dan stel ons nuwe wortel te wees 77. 976 00:49:44,325 --> 00:49:46,450 Ons kan net gaan na waar die wyser wys. 977 00:49:46,450 --> 00:49:49,100 Wel, o, hier ons begin op 77, en ons kan net 978 00:49:49,100 --> 00:49:51,172 doen dit rekursief weer en weer. 979 00:49:51,172 --> 00:49:52,880 Op hierdie manier, jy soort van 'n funksie. 980 00:49:52,880 --> 00:49:57,430 Jy het 'n manier dat jy soek kan net herhaal oor en oor en oor, 981 00:49:57,430 --> 00:50:02,720 afhangende van waar jy wil om te kyk totdat jy uiteindelik kry om die waarde 982 00:50:02,720 --> 00:50:04,730 dat jy soek. 983 00:50:04,730 --> 00:50:05,230 Maak sin? 984 00:50:05,230 --> 00:50:07,800 >> Ek is op die punt om te wys jy die werklike kode, en dit is 'n baie van die kode. 985 00:50:07,800 --> 00:50:08,674 Geen behoefte om freak uit. 986 00:50:08,674 --> 00:50:09,910 Ons sal praat deur dit. 987 00:50:09,910 --> 00:50:13,410 988 00:50:13,410 --> 00:50:14,020 >> Eintlik, no. 989 00:50:14,020 --> 00:50:15,061 Dit was net pseudokode. 990 00:50:15,061 --> 00:50:17,860 OK, dit was net die pseudokode, wat is 'n bietjie kompleks, 991 00:50:17,860 --> 00:50:19,751 maar dit is heeltemal fyn. 992 00:50:19,751 --> 00:50:21,000 Almal volgende saam hier? 993 00:50:21,000 --> 00:50:24,260 As die wortel is van nul, terugkeer valse want dit beteken 994 00:50:24,260 --> 00:50:26,850 jy hoef nie eens iets het daar. 995 00:50:26,850 --> 00:50:31,376 >> As wortel N is die waarde, so as dit gebeur met die een wat jy soek by wees, 996 00:50:31,376 --> 00:50:34,000 dan is jy gaan om ware terugkeer want jy weet jy dit gevind. 997 00:50:34,000 --> 00:50:36,250 Maar as die waarde minder as wortel van N, jy is 998 00:50:36,250 --> 00:50:38,332 gaan aan die linkerkant soek kind of links blaar, 999 00:50:38,332 --> 00:50:39,540 alles wat jy wil om dit te noem. 1000 00:50:39,540 --> 00:50:41,750 En as die waarde is groter as wortel, jy gaan die regte boom soek, 1001 00:50:41,750 --> 00:50:44,610 dan net die funksie hardloop deur 'n soektog weer. 1002 00:50:44,610 --> 00:50:48,037 >> En as die wortel is van nul, dat die beteken jy aan die einde bereik het? 1003 00:50:48,037 --> 00:50:50,120 Dit beteken dat jy het geen meer meer blare te soek, 1004 00:50:50,120 --> 00:50:52,230 dan weet jy, o, ek dink dit is nie hier 1005 00:50:52,230 --> 00:50:55,063 want nadat ek kyk deur die hele ding en dit is nie hier nie, 1006 00:50:55,063 --> 00:50:56,930 dit mag dalk net nie hier wees nie. 1007 00:50:56,930 --> 00:50:58,350 >> Maak dit sin om almal? 1008 00:50:58,350 --> 00:51:03,230 So dit is soos binêre soek behoud die vermoëns van geskakelde lyste. 1009 00:51:03,230 --> 00:51:09,200 Cool, en so die tweede tipe datastruktuur julle ouens 1010 00:51:09,200 --> 00:51:13,180 kan probeer om die uitvoering van jou pset, jy het net een metode te kies. 1011 00:51:13,180 --> 00:51:19,430 Maar miskien 'n alternatiewe metode om die hash tafel is wat ons 'n Trie noem. 1012 00:51:19,430 --> 00:51:24,080 >> Al wat 'n Trie is 'n spesifieke tipe boom wat 1013 00:51:24,080 --> 00:51:28,600 het waardes wat na ander waardes. 1014 00:51:28,600 --> 00:51:31,450 So in plaas van om 'n binêre boom in die sin dat slegs een 1015 00:51:31,450 --> 00:51:35,940 ding kan wys twee kan jy een ding punt om baie, baie dinge. 1016 00:51:35,940 --> 00:51:39,450 Jy het in wese skikkings binnekant van wat jy slaan 1017 00:51:39,450 --> 00:51:41,790 wysers wat na ander skikkings. 1018 00:51:41,790 --> 00:51:45,210 1019 00:51:45,210 --> 00:51:49,460 >> So die knoop van hoe ons sou 'n Trie definieer 1020 00:51:49,460 --> 00:51:52,590 is ons wil 'n te hê Boole, c woord, reg? 1021 00:51:52,590 --> 00:51:54,920 So die knoop is Boole soos ware of vals, 1022 00:51:54,920 --> 00:51:58,490 eerste van alles aan die hoof van dat skikking, is dit 'n woord? 1023 00:51:58,490 --> 00:52:03,620 Tweedens, wil jy wenke het om ongeag die res van hulle is. 1024 00:52:03,620 --> 00:52:07,470 'N bietjie kompleks, 'n bietjie abstrakte, maar Ek sal wat dit alles beteken verduidelik. 1025 00:52:07,470 --> 00:52:13,800 >> So hier, by die top, as jy het 'n verskeidenheid verklaar reeds 1026 00:52:13,800 --> 00:52:17,040 'n knoop waar jy 'n Boole waarde gestoor aan die voorkant 1027 00:52:17,040 --> 00:52:19,490 wat vertel jy is dit 'n woord? 1028 00:52:19,490 --> 00:52:20,520 Is dit nie 'n woord? 1029 00:52:20,520 --> 00:52:23,240 En dan moet jy die res van jou skikking wat 1030 00:52:23,240 --> 00:52:26,040 eintlik slaan al die moontlikhede van wat dit kan wees. 1031 00:52:26,040 --> 00:52:28,660 So, byvoorbeeld, soos by die top jy 1032 00:52:28,660 --> 00:52:32,140 die eerste ding wat waar of sê valse, ja of nee, dit is 'n woord. 1033 00:52:32,140 --> 00:52:38,130 >> En dan moet jy 0 deur 26 van die letters wat jy kan stoor. 1034 00:52:38,130 --> 00:52:42,790 As ek wou hier soek vir kolf, ek gaan na die top 1035 00:52:42,790 --> 00:52:49,200 en ek kyk vir B. Ek B vind in my skikking, en so ek weet, OK, is B 'n woord? 1036 00:52:49,200 --> 00:52:53,010 B is nie 'n woord, so dus Ek moet soek hou. 1037 00:52:53,010 --> 00:52:56,410 Ek gaan van B, en ek kyk na die wyser dat B dui op 1038 00:52:56,410 --> 00:53:00,900 en ek sien 'n ander verskeidenheid van inligting, dieselfde struktuur wat ons voorheen gehad het. 1039 00:53:00,900 --> 00:53:05,240 >> En here-- oh, die volgende brief [onhoorbaar] is A. 1040 00:53:05,240 --> 00:53:07,210 So ons kyk in daardie skikking. 1041 00:53:07,210 --> 00:53:10,860 Ons vind die agtste waarde en dan kyk ons ​​om te sien, o, 1042 00:53:10,860 --> 00:53:12,840 hey, is dat 'n woord, is B-A 'n woord? 1043 00:53:12,840 --> 00:53:13,807 Dit is nie 'n woord. 1044 00:53:13,807 --> 00:53:14,890 Ons het om te hou soek. 1045 00:53:14,890 --> 00:53:17,850 >> En so dan kyk ons ​​na waar die wyser van 'n punte, 1046 00:53:17,850 --> 00:53:21,130 en dit dui op 'n ander manier in wat ons het meer waarde gestoor. 1047 00:53:21,130 --> 00:53:24,150 En uiteindelik, kry ons B-A-T, wat is 'n woord. 1048 00:53:24,150 --> 00:53:25,970 En so het die volgende keer jy kyk, jy gaan 1049 00:53:25,970 --> 00:53:30,850 dat die tjek van, ja het, hierdie Boole-funksie is waar. 1050 00:53:30,850 --> 00:53:35,450 En so in die sin is ons soort van 'n boom met skikkings. 1051 00:53:35,450 --> 00:53:39,890 >> So dan kan jy soort soek down. 1052 00:53:39,890 --> 00:53:43,650 Eerder as 'n funksie en hashing toeken waardes gekoppel lys 1053 00:53:43,650 --> 00:53:49,190 jy kan net implementeer Trie dat downwords soek. 1054 00:53:49,190 --> 00:53:50,850 Regtig, regtig ingewikkeld dinge. 1055 00:53:50,850 --> 00:53:54,060 Nie maklik om te dink oor, want ek is soos ' spoeg so baie data strukture uit 1056 00:53:54,060 --> 00:53:58,710 na jou, maar doen almal soort verstaan ​​hoe die logika van hierdie werk? 1057 00:53:58,710 --> 00:54:01,920 >> OK, cool. 1058 00:54:01,920 --> 00:54:05,600 So B-A-T, en dan jy gaan soek. 1059 00:54:05,600 --> 00:54:07,940 Die volgende keer wat jy gaan om te sien, o, hey, dit is waar, 1060 00:54:07,940 --> 00:54:09,273 dus ek weet dit moet 'n woord te wees. 1061 00:54:09,273 --> 00:54:12,030 1062 00:54:12,030 --> 00:54:13,770 >> Dieselfde ding vir dieretuin. 1063 00:54:13,770 --> 00:54:17,960 So hier is die ding nou, as ons wou soek dieretuin, reg nou, 1064 00:54:17,960 --> 00:54:20,780 tans dieretuin is nie 'n woord in ons woordeboek 1065 00:54:20,780 --> 00:54:25,300 want soos julle kan sien, die eerste plek dat ons 'n Boole 1066 00:54:25,300 --> 00:54:28,590 terugkeer waar is aan die einde van zoom. 1067 00:54:28,590 --> 00:54:30,430 Ons het Z-O-O-M. 1068 00:54:30,430 --> 00:54:33,900 >> En so hier het ons nie eintlik die woord, dieretuin, in ons woordeboek 1069 00:54:33,900 --> 00:54:36,070 want dit boks is nie nagegaan. 1070 00:54:36,070 --> 00:54:39,540 So die rekenaar nie weet dat dieretuin is 'n woord 1071 00:54:39,540 --> 00:54:42,430 omdat die pad wat ons het gestoor is, slegs 'n zoom hier 1072 00:54:42,430 --> 00:54:44,920 het eintlik 'n Boolese waarde dit is gedraai waar. 1073 00:54:44,920 --> 00:54:49,380 So as ons wil hê dat die plaas woord dieretuin, in ons woordeboek, 1074 00:54:49,380 --> 00:54:51,770 hoe sou ons gaan oor om dit te doen? 1075 00:54:51,770 --> 00:54:55,960 Wat moet ons doen om seker te maak ons rekenaar weet dat Z-O-O is 'n woord 1076 00:54:55,960 --> 00:54:58,130 en nie die eerste woord is Z-O-O-M? 1077 00:54:58,130 --> 00:54:59,360 >> GEHOOR: [onhoorbaar] 1078 00:54:59,360 --> 00:55:01,450 >> ANDI Peng: Presies, ons wil seker maak dat dit 1079 00:55:01,450 --> 00:55:07,890 hier dat Boole waarde is nagegaan af dat dit is waar. 1080 00:55:07,890 --> 00:55:13,297 Z-O-O, dan gaan ons seker maak dat, sodat ons presies weet, hey, dieretuin is 'n woord. 1081 00:55:13,297 --> 00:55:15,380 Ek gaan die vertel rekenaar wat dit is 'n woord so 1082 00:55:15,380 --> 00:55:18,000 dat wanneer die rekenaar tjeks, dit weet dat dieretuin is 'n woord. 1083 00:55:18,000 --> 00:55:21,269 >> Want onthou al hierdie data strukture, dit is baie maklik vir ons 1084 00:55:21,269 --> 00:55:22,310 om te sê, o, kolf is 'n woord. 1085 00:55:22,310 --> 00:55:22,851 Zoo is 'n woord. 1086 00:55:22,851 --> 00:55:23,611 Klik is 'n woord. 1087 00:55:23,611 --> 00:55:25,860 Maar wanneer jy die bou van dit, die rekenaar het geen idee nie. 1088 00:55:25,860 --> 00:55:28,619 >> So moet jy dit presies vertel op watter punt is dit 'n woord? 1089 00:55:28,619 --> 00:55:29,910 Op watter punt is dit nie 'n woord? 1090 00:55:29,910 --> 00:55:31,784 En op watter punt het ek nodig het om dinge te soek, 1091 00:55:31,784 --> 00:55:34,000 en op watter punt moet ek volgende gaan? 1092 00:55:34,000 --> 00:55:37,010 Almal duidelik van dit? 1093 00:55:37,010 --> 00:55:39,540 Koel. 1094 00:55:39,540 --> 00:55:42,530 >> En so dan kom die probleem van hoe sou ons 1095 00:55:42,530 --> 00:55:45,560 gaan invoeging iets dit is eintlik nie daar? 1096 00:55:45,560 --> 00:55:49,090 So laat ons net sê ons wil voeg die woord, bad, in ons Trie. 1097 00:55:49,090 --> 00:55:53,589 As julle ouens kan sien soos wat tans Al wat ons nou het, is B-A-T, 1098 00:55:53,589 --> 00:55:55,630 en hierdie nuwe data struktuur Daar was 'n pint wat 1099 00:55:55,630 --> 00:55:59,740 wys na nul, want ons aanvaar dat O, daar is geen woorde na B-A-T, 1100 00:55:59,740 --> 00:56:02,530 Daarom het ons nodig om te hou met dinge daarna T. 1101 00:56:02,530 --> 00:56:06,581 >> Maar die probleem ontstaan ​​as ons wat jy doen wil 'n woord wat kom na het 1102 00:56:06,581 --> 00:56:07,080 die T se. 1103 00:56:07,080 --> 00:56:09,500 As jy 'n bad, jy is gaan 'n H reg wil hê. 1104 00:56:09,500 --> 00:56:13,290 En so het die manier waarop ons gaan om dit te doen is ons gaan 'n aparte node skep. 1105 00:56:13,290 --> 00:56:16,840 Ons is nie net die bedrag toeken geheue vir hierdie nuwe skikking, 1106 00:56:16,840 --> 00:56:20,720 en ons gaan pointers toewys. 1107 00:56:20,720 --> 00:56:22,947 >> Ons gaan die toewys H, Eerste van alles, dit null, 1108 00:56:22,947 --> 00:56:24,030 ons gaan om ontslae te raak van. 1109 00:56:24,030 --> 00:56:26,590 Ons gaan hê die H punt afwaarts. 1110 00:56:26,590 --> 00:56:30,600 As ons sien 'n H, ons wil dit om te gaan na 'n ander plek. 1111 00:56:30,600 --> 00:56:33,910 >> In hier, kan ons dan seker ja af. 1112 00:56:33,910 --> 00:56:38,170 As ons 'n H getref nadat die T, o, dan weet ons dat dit 'n woord. 1113 00:56:38,170 --> 00:56:41,110 Die Boole gaan ware terugkeer. 1114 00:56:41,110 --> 00:56:42,950 Almal duidelik oor hoe dit gebeur het? 1115 00:56:42,950 --> 00:56:45,110 OK. 1116 00:56:45,110 --> 00:56:47,214 >> So in wese, al hierdie data strukture 1117 00:56:47,214 --> 00:56:50,130 dat ons oor vandag gegaan het, ek het regtig, regtig vinnig gegaan oor hulle 1118 00:56:50,130 --> 00:56:52,192 en nie in te veel detail, en dit is OK. 1119 00:56:52,192 --> 00:56:53,900 Sodra jy begin geknoei met dit, sal jy 1120 00:56:53,900 --> 00:56:55,733 dop van waar al die wysers is, 1121 00:56:55,733 --> 00:56:58,060 wat gaan aan in jou data strukture, ensovoorts. 1122 00:56:58,060 --> 00:56:59,810 Hulle sal baie nuttig wees, en dit is aan jou 1123 00:56:59,810 --> 00:57:03,890 ouens heeltemal uit te vind hoe jy wil om dinge te implementeer. 1124 00:57:03,890 --> 00:57:07,650 >> En so pset4 van 5-- O, dit is verkeerd. 1125 00:57:07,650 --> 00:57:10,140 Pset5 is spelfoute. 1126 00:57:10,140 --> 00:57:13,710 Soos ek gesê het, gaan jy, sodra weer, laai bronkode van ons. 1127 00:57:13,710 --> 00:57:16,210 Daar gaan drie hoof wees dinge wat jy sal laai. 1128 00:57:16,210 --> 00:57:18,470 Jy sal woordeboeke aflaai, kers, en tekste. 1129 00:57:18,470 --> 00:57:21,660 >> Al daardie dinge is, is óf woordeboeke woorde 1130 00:57:21,660 --> 00:57:25,190 dat ons wil hê jy om te kyk of toets van die inligting 1131 00:57:25,190 --> 00:57:26,930 dat ons wil hê jy moet check spel. 1132 00:57:26,930 --> 00:57:29,670 En so het die woordeboeke ons gee jou gaan 1133 00:57:29,670 --> 00:57:34,870 om jou werklike woorde wat ons wil gee jy een of ander manier te stoor in 'n manier wat 1134 00:57:34,870 --> 00:57:36,530 meer doeltreffend as 'n skikking. 1135 00:57:36,530 --> 00:57:38,470 En dan is die tekste gaan wees wat ons is 1136 00:57:38,470 --> 00:57:43,900 vra jou om te spel om seker te al die woorde daar werklike woorde. 1137 00:57:43,900 --> 00:57:47,970 >> En so het die drie blokke van programme wat ons sal gee jou 1138 00:57:47,970 --> 00:57:51,130 is dictionary.c genoem, dictionary.h en speller.c. 1139 00:57:51,130 --> 00:57:56,500 En so sal die hele dictionary.c doen is wat jy gevra word om te implementeer. 1140 00:57:56,500 --> 00:57:57,880 Dit laai woorde. 1141 00:57:57,880 --> 00:58:02,000 Dit spel tjeks hulle, en dit maak seker dat alles behoorlik ingesit. 1142 00:58:02,000 --> 00:58:05,180 >> diction.h is net 'n biblioteek lêer wat verklaar al die funksies. 1143 00:58:05,180 --> 00:58:07,650 En speller.c, ons gaan om jou te gee. 1144 00:58:07,650 --> 00:58:09,290 Jy hoef nie aan enige van dit te verander. 1145 00:58:09,290 --> 00:58:14,290 Alle speller.c doen is neem, vragte dit gaan die spoed van dit, 1146 00:58:14,290 --> 00:58:19,190 toets die maatstaf van soos hoe vinnig jy kan om dinge te doen. 1147 00:58:19,190 --> 00:58:20,410 >> Dit is 'n speller. 1148 00:58:20,410 --> 00:58:23,920 Net doen nie gemors met dit, maar maak seker jy verstaan ​​wat dit doen. 1149 00:58:23,920 --> 00:58:28,090 Ons gebruik 'n funksie genoem getrusage dat toets van die prestasie van jou spel 1150 00:58:28,090 --> 00:58:28,590 checker. 1151 00:58:28,590 --> 00:58:32,200 Al wat dit doen is basies die toets van die tyd van alles wat in jou woordeboek, 1152 00:58:32,200 --> 00:58:33,680 so maak seker jy verstaan ​​dit. 1153 00:58:33,680 --> 00:58:36,660 Wees versigtig om nie gemors met dit of anders sal dinge nie behoorlik uit te voer. 1154 00:58:36,660 --> 00:58:39,740 1155 00:58:39,740 --> 00:58:44,170 >> En die grootste deel van hierdie uitdaging is vir julle ouens om werklik dictionary.c verander. 1156 00:58:44,170 --> 00:58:48,526 Ons gaan om jou te gee 140,000 woorde in 'n woordeboek. 1157 00:58:48,526 --> 00:58:50,900 Ons gaan jou 'n SMS te gee lêer wat daardie woorde het, 1158 00:58:50,900 --> 00:58:54,840 en ons wil hê jy moet in staat wees om te organiseer hulle in 'n hash tafel of 'n Trie 1159 00:58:54,840 --> 00:58:58,140 want as ons vra om te spel check-- dink as jy spel 1160 00:58:58,140 --> 00:59:00,690 kontrole soos Homer se Odyssey. 1161 00:59:00,690 --> 00:59:03,010 Dit is soos die groot, groot toets. 1162 00:59:03,010 --> 00:59:05,190 >> Stel jou voor dat elke enkele woord wat jy het om te kyk 1163 00:59:05,190 --> 00:59:08,100 deur 'n verskeidenheid van 140,000 waardes. 1164 00:59:08,100 --> 00:59:10,350 Dit sou vir ewig vir jou rekenaar uit te voer. 1165 00:59:10,350 --> 00:59:14,490 Dit is hoekom ons wil hê dat ons organiseer data in meer doeltreffende data strukture 1166 00:59:14,490 --> 00:59:17,270 soos 'n hash tafel of 'n Trie. 1167 00:59:17,270 --> 00:59:20,700 En dan moet jy ouens kan soort wanneer jy toegang soek 1168 00:59:20,700 --> 00:59:22,570 dinge makliker en vinniger. 1169 00:59:22,570 --> 00:59:24,934 >> En so wees versigtig om botsings te los. 1170 00:59:24,934 --> 00:59:27,350 Jy gaan 'n klomp te kry woorde van wat begin met A. 1171 00:59:27,350 --> 00:59:29,957 Jy gaan 'n klomp woorde kry wat begin met B. Tot jy 1172 00:59:29,957 --> 00:59:31,290 ouens hoe jy wil om dit te los. 1173 00:59:31,290 --> 00:59:34,144 Miskien is daar meer doeltreffende hash funksie 1174 00:59:34,144 --> 00:59:36,810 as net die eerste letter van iets, en so dit is aan jou 1175 00:59:36,810 --> 00:59:38,190 ouens soort doen wat jy wil. 1176 00:59:38,190 --> 00:59:40,148 >> Miskien het jy wil byvoeg al die letters saam. 1177 00:59:40,148 --> 00:59:43,410 Miskien wil jy graag doen vreemde dinge om die aantal letters rekening 1178 00:59:43,410 --> 00:59:43,970 wat ook al. 1179 00:59:43,970 --> 00:59:45,386 Tot julle hoe jy wil om dit te doen. 1180 00:59:45,386 --> 00:59:49,262 As jy wil 'n hash tafel doen, as jy wil 'n Trie probeer, heeltemal aan jou. 1181 00:59:49,262 --> 00:59:52,470 Ek sal julle voor te waarsku van die tyd dat die Trie is tipies 'n bietjie meer moeilik 1182 00:59:52,470 --> 00:59:54,520 net omdat daar 'n baie meer wenke om tred te hou. 1183 00:59:54,520 --> 00:59:55,645 Maar heeltemal aan julle. 1184 00:59:55,645 --> 00:59:58,742 Dit is veel meer doeltreffende in die meeste gevalle. 1185 00:59:58,742 --> 01:00:01,450 Jy wil regtig in staat wees om aan te hou spoor van al jou wenke. 1186 01:00:01,450 --> 01:00:03,850 Soos dieselfde ding doen dat ek hier doen. 1187 01:00:03,850 --> 01:00:06,871 Wanneer jy probeer om in te voeg waardes in 'n hash tafel of te verwyder, 1188 01:00:06,871 --> 01:00:08,620 maak seker dat jy regtig dop 1189 01:00:08,620 --> 01:00:11,860 van waar alles is omdat dit is baie maklik vir as ek 1190 01:00:11,860 --> 01:00:14,727 probeer om in te voeg soos die woord, Andy. 1191 01:00:14,727 --> 01:00:16,810 Laat ons net sê dit is 'n werklike woord die woord, Andy, 1192 01:00:16,810 --> 01:00:19,640 in 'n reuse lys van A woorde. 1193 01:00:19,640 --> 01:00:22,450 >> As ek net gebeur om toewys 'n wyser verkeerd is, oops, 1194 01:00:22,450 --> 01:00:24,940 daar gaan die geheel van die res van my geskakelde lys. 1195 01:00:24,940 --> 01:00:26,897 Nou is die enigste woord wat ek het, is Andy, en nou 1196 01:00:26,897 --> 01:00:29,230 al die ander woorde in die woordeboek het verlore gegaan. 1197 01:00:29,230 --> 01:00:31,370 En so jy wil om seker te maak jy hou van al jou wenke 1198 01:00:31,370 --> 01:00:33,661 of anders wat jy gaan kry groot probleme in jou kode. 1199 01:00:33,661 --> 01:00:35,840 Teken dinge uit versigtig stap vir stap. 1200 01:00:35,840 --> 01:00:37,870 Dit maak dit 'n baie makliker om te dink. 1201 01:00:37,870 --> 01:00:40,910 >> En laastens, wil jy in staat wees om toets jou prestasie van jou program 1202 01:00:40,910 --> 01:00:41,618 op die groot bord. 1203 01:00:41,618 --> 01:00:43,710 As jy ouens neem 'n kyk na CS50 nou, 1204 01:00:43,710 --> 01:00:45,210 ons het wat is bekend as die groot bord. 1205 01:00:45,210 --> 01:00:50,200 Dit is die telkaart van die vinnigste spellingscontrole keer oor al CS50 1206 01:00:50,200 --> 01:00:55,720 nou, ek dink die top 10 soos Soms dink ek agt van hulle is die personeel. 1207 01:00:55,720 --> 01:00:57,960 Ons wil regtig julle ouens om ons te klop. 1208 01:00:57,960 --> 01:01:00,870 >> Almal van ons het probeer om te implementeer die vinnigste kode as moontlik. 1209 01:01:00,870 --> 01:01:04,880 Ons wil julle ouens om te probeer om uit te daag ons en implementeer vinniger as ons almal 1210 01:01:04,880 --> 01:01:05,550 kan. 1211 01:01:05,550 --> 01:01:07,970 En so dit is regtig die eerste keer dat ons 1212 01:01:07,970 --> 01:01:12,680 vra julle om 'n pset doen jy kan regtig nie in watter metode 1213 01:01:12,680 --> 01:01:13,760 jy wil. 1214 01:01:13,760 --> 01:01:17,730 >> Ek sê altyd, dit is meer verwant om 'n werklike oplossing, reg? 1215 01:01:17,730 --> 01:01:19,550 Ek sê, hey, ek het jou nodig om dit te doen. 1216 01:01:19,550 --> 01:01:21,380 Bou 'n program wat dit doen vir my. 1217 01:01:21,380 --> 01:01:22,630 Doen dit egter jy wil. 1218 01:01:22,630 --> 01:01:24,271 Ek weet net dat ek wil om te vas. 1219 01:01:24,271 --> 01:01:25,770 Dit is jou uitdaging vir hierdie week. 1220 01:01:25,770 --> 01:01:27,531 Julle ouens, ons gaan om jou 'n taak gee. 1221 01:01:27,531 --> 01:01:29,030 Ons gaan jou 'n uitdaging gee. 1222 01:01:29,030 --> 01:01:31,559 En dan is dit aan julle ouens heeltemal net uitvind 1223 01:01:31,559 --> 01:01:34,100 wat is die vinnigste en mees doeltreffende manier om dit te implementeer. 1224 01:01:34,100 --> 01:01:34,600 Ja? 1225 01:01:34,600 --> 01:01:37,476 >> GEHOOR: Is ons toegelaat om as wou vinniger maniere te vors 1226 01:01:37,476 --> 01:01:40,821 om hash tabelle aanlyn te doen, kan ons doen dit en noem kode iemand anders se? 1227 01:01:40,821 --> 01:01:42,070 ANDI Peng: Ja, heeltemal fyn. 1228 01:01:42,070 --> 01:01:44,320 So as jy lees die ouens spec, is daar 'n lyn 1229 01:01:44,320 --> 01:01:48,310 in die spec dat jy ouens sê is heeltemal gratis om hash navorsing 1230 01:01:48,310 --> 01:01:51,070 funksies op wat is 'n paar van die vinniger hash funksies 1231 01:01:51,070 --> 01:01:54,720 om dinge loop deur as Solank as wat jy daardie kode noem. 1232 01:01:54,720 --> 01:01:57,220 So 'n paar mense reeds uitgepluis vinnige maniere 1233 01:01:57,220 --> 01:02:00,250 doen speltoetsers, van 'n vinnige maniere van die stoor inligting. 1234 01:02:00,250 --> 01:02:02,750 Heeltemal aan julle ouens as jy wil net neem, reg? 1235 01:02:02,750 --> 01:02:04,045 Maak seker dat jy met verwysing na. 1236 01:02:04,045 --> 01:02:06,170 Die uitdaging hier regtig dat ons probeer om te toets 1237 01:02:06,170 --> 01:02:09,750 maak seker dat jy weet jou pad om wenke. 1238 01:02:09,750 --> 01:02:12,700 So ver as jy die uitvoering van die werklike hash funksie 1239 01:02:12,700 --> 01:02:15,070 en kom met soos die wiskunde om dit te doen, 1240 01:02:15,070 --> 01:02:17,570 julle ouens kan navorsing wat ookal metodes aanlyn jy ouens wil. 1241 01:02:17,570 --> 01:02:17,996 Ja? 1242 01:02:17,996 --> 01:02:19,700 >> GEHOOR: Kan ons noem net deur die gebruik van die [onhoorbaar]? 1243 01:02:19,700 --> 01:02:20,120 >> ANDI Peng: Ja. 1244 01:02:20,120 --> 01:02:22,328 Jy kan net in jou kommentaar, jy kan noem soos, ag, 1245 01:02:22,328 --> 01:02:26,127 geneem uit yada, yada, yada, hash funksie. 1246 01:02:26,127 --> 01:02:27,210 Enigiemand enige vrae? 1247 01:02:27,210 --> 01:02:29,694 Ons het eintlik breezed deur artikel vandag. 1248 01:02:29,694 --> 01:02:31,610 Ek sal hier wees om vrae te beantwoord as well. 1249 01:02:31,610 --> 01:02:36,570 >> Ook, soos ek gesê het, kantoor uur vanaand en môre. 1250 01:02:36,570 --> 01:02:40,307 Die spec hierdie week is eintlik super maklik en super kort om te lees. 1251 01:02:40,307 --> 01:02:43,140 Ek sou voorstel om 'n blik, net lees deur die geheel van dit. 1252 01:02:43,140 --> 01:02:45,730 >> En Zamyla eintlik loop jy deur elk van die funksies 1253 01:02:45,730 --> 01:02:49,796 wat jy nodig het om te implementeer, en dit is dus baie, baie duidelik hoe om alles te doen. 1254 01:02:49,796 --> 01:02:51,920 Net om seker te maak jy dop van wysers. 1255 01:02:51,920 --> 01:02:53,650 Dit is 'n baie uitdagende pset. 1256 01:02:53,650 --> 01:02:56,744 >> Dit is nie 'n uitdaging, want soos, O, die konsepte is soveel meer 1257 01:02:56,744 --> 01:02:59,160 moeilik, of jy het om te leer soveel nuwe sintaksis die pad 1258 01:02:59,160 --> 01:03:00,650 wat jy gedoen het vir die laaste pset. 1259 01:03:00,650 --> 01:03:03,320 Dit is moeilik, want pset daar is so baie wysers, 1260 01:03:03,320 --> 01:03:06,980 en dan is dit baie, baie maklik om te keer jy het 'n fout in jou kode nie in staat wees 1261 01:03:06,980 --> 01:03:08,315 om uit te vind waar daardie fout is. 1262 01:03:08,315 --> 01:03:13,200 >> En so volledig en volslae geloof in julle ouens in staat wees om ons [onhoorbaar] klop 1263 01:03:13,200 --> 01:03:13,700 spellings. 1264 01:03:13,700 --> 01:03:16,640 Ek het eintlik nie enige skriftelike myn nie, maar ek is op die punt om my te skryf. 1265 01:03:16,640 --> 01:03:19,070 Dus, terwyl jy skryf joune is, sal ek skryf myne. 1266 01:03:19,070 --> 01:03:21,070 Ek gaan om te probeer om te maak my vinniger as joune. 1267 01:03:21,070 --> 01:03:23,940 Ons sal sien wat die vinnigste een. 1268 01:03:23,940 --> 01:03:27,340 >> En ja, ek sal al sien julle ouens hier op Dinsdag. 1269 01:03:27,340 --> 01:03:29,510 Ek sal 'n soort soos 'n pset werkswinkel loop. 1270 01:03:29,510 --> 01:03:32,640 Al die afdelings van hierdie week is pset werkswinkels, 1271 01:03:32,640 --> 01:03:36,690 so julle ouens het baie van die geleenthede vir hulp, kantoorure soos altyd, 1272 01:03:36,690 --> 01:03:41,330 en Ek het regtig uitsien na lees al jou ouens se kode. 1273 01:03:41,330 --> 01:03:44,160 Ek het vasvrae hier as jy ouens wil kom kry wat. 1274 01:03:44,160 --> 01:03:45,880 Dit is al. 1275 01:03:45,880 --> 01:03:48,180