1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Musikken afspilles] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Dette er CS50. 5 00:00:14,010 --> 00:00:18,090 Og det er både begyndelsen og end-- ligesom literally-- næsten enden 6 00:00:18,090 --> 00:00:18,825 af uge seks. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Jeg troede, jeg ville dele en lidt af en sjov kendsgerning. 9 00:00:22,640 --> 00:00:25,370 Jeg har trukket det op fra en data forløbne semesters indstillet. 10 00:00:25,370 --> 00:00:29,710 Du husker måske, at vi beder dig om hver p sæt formular, hvis du har set online 11 00:00:29,710 --> 00:00:31,580 eller hvis du har deltaget i person. 12 00:00:31,580 --> 00:00:33,020 Og her er dataene. 13 00:00:33,020 --> 00:00:34,710 Så i dag var meget forudsigelig. 14 00:00:34,710 --> 00:00:37,126 Men vi ønskede at tilbringe en smule af tid sammen med dig alligevel. 15 00:00:37,126 --> 00:00:40,599 Ville nogen gerne formodninger hvorfor dette graf er så jaggy, op ned, op ned, 16 00:00:40,599 --> 00:00:41,265 så konsekvent? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Hvad gør hver af toppene og trug repræsentere? 19 00:00:45,130 --> 00:00:46,005 >> PUBLIKUM: [uhørligt] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Ja. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Og mere underholdende, gud forbyde det, vi holder et foredrag på en fredag 24 00:00:55,480 --> 00:00:58,960 i begyndelsen af ​​semestret, det er, hvad vi ser ske. 25 00:00:58,960 --> 00:01:03,430 Så i dag, vi deltager i en lidt mere om datastrukturer. 26 00:01:03,430 --> 00:01:06,660 Og for at give dig mere af en solid mental model for problemer på fem, 27 00:01:06,660 --> 00:01:07,450 der er nu ude. 28 00:01:07,450 --> 00:01:10,817 Stavefejl, hvor, vil vi hånd du en tekstfil omkring 100.000 29 00:01:10,817 --> 00:01:12,650 plus engelske ord, og du er nødt til 30 00:01:12,650 --> 00:01:17,770 at finde ud af, hvordan man behændigt indlæse dem ind i hukommelsen, i RAM, ved hjælp af nogle data 31 00:01:17,770 --> 00:01:19,330 opbygning af dit valg. 32 00:01:19,330 --> 00:01:22,470 >> Nu en sådan datastruktur kunne være, men burde nok ikke være, 33 00:01:22,470 --> 00:01:25,630 den ret forsimplede linkede liste, som vi introducerede sidste gang. 34 00:01:25,630 --> 00:01:29,220 Og en sammenkædet liste havde mindst en fordel i forhold til et array. 35 00:01:29,220 --> 00:01:32,096 Hvad der er en fordel ved en sammenkædet liste velsagtens? 36 00:01:32,096 --> 00:01:32,950 >> PUBLIKUM: Indsættelse. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Indsættelse. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Hvad mener du med det? 40 00:01:35,196 --> 00:01:37,872 >> PUBLIKUM: Anywhere sammen listen [uhørligt]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: God. 42 00:01:38,770 --> 00:01:42,090 Så du kan indsætte et element, hvor du ønsker i midten af ​​listen 43 00:01:42,090 --> 00:01:45,490 uden at blande noget, som vi konkluderede i vores sortering 44 00:01:45,490 --> 00:01:47,630 diskussioner, er ikke nødvendigvis en god ting, 45 00:01:47,630 --> 00:01:51,200 fordi det tager tid at faktisk bevæge alle disse mennesker til venstre eller højre. 46 00:01:51,200 --> 00:01:55,540 Og så med en linket liste, kan du bare tildele med malloc en ny node, 47 00:01:55,540 --> 00:01:58,385 og derefter opdatere et par pointers-- to, tre operationer max-- 48 00:01:58,385 --> 00:02:01,480 og vi er i stand til slot nogen i overalt i en liste. 49 00:02:01,480 --> 00:02:03,550 >> Hvad der ellers var fordelagtig om en sammenkædet liste? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Ja? 52 00:02:05,659 --> 00:02:06,534 >> PUBLIKUM: [uhørligt] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Det er virkelig dynamisk. 58 00:02:12,070 --> 00:02:15,100 Og at du ikke begå, i forvejen, til nogle faste størrelse 59 00:02:15,100 --> 00:02:18,750 luns af hukommelse, ligesom du ville have til med et array, opadrettede som 60 00:02:18,750 --> 00:02:22,455 er, at du kan tildele knuder kun på efterspørgsel og dermed kun bruger så meget plads 61 00:02:22,455 --> 00:02:23,330 som du rent faktisk har brug for. 62 00:02:23,330 --> 00:02:26,830 I modsætning til et array, kan du uheld tildele for lidt. 63 00:02:26,830 --> 00:02:28,871 Og så er det bare at gå at være en smerte i nakken 64 00:02:28,871 --> 00:02:32,440 at omfordele en ny større array, kopiere alt i, befri den gamle array, 65 00:02:32,440 --> 00:02:33,990 og derefter flytte om din virksomhed. 66 00:02:33,990 --> 00:02:37,479 Eller endnu værre, kan du tildele måde mere hukommelse end du rent faktisk har brug for, 67 00:02:37,479 --> 00:02:40,520 og så du kommer til at have en meget tyndt befolkede array, så at sige. 68 00:02:40,520 --> 00:02:44,350 >> Så en sammenkædet liste giver dig disse fordele ved dynamik og fleksibilitet 69 00:02:44,350 --> 00:02:46,080 med indsætninger og sletninger. 70 00:02:46,080 --> 00:02:48,000 Men sikkert skal der være en pris betalt. 71 00:02:48,000 --> 00:02:50,000 Faktisk er en af ​​de temaer udforskes på quiz nul 72 00:02:50,000 --> 00:02:52,430 var et par af de afvejninger vi har set hidtil. 73 00:02:52,430 --> 00:02:56,161 Så hvad er en pris, der betales eller en Ulempen ved en linket liste? 74 00:02:56,161 --> 00:02:56,660 Ja. 75 00:02:56,660 --> 00:02:57,560 >> PUBLIKUM: Ingen random access. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Ingen random access. 77 00:02:58,809 --> 00:02:59,540 Men hvem bekymrer sig? 78 00:02:59,540 --> 00:03:01,546 Random access lyder ikke overbevisende. 79 00:03:01,546 --> 00:03:02,421 >> PUBLIKUM: [uhørligt] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Præcis. 82 00:03:05,740 --> 00:03:07,580 Hvis du vil have en vis algorithm-- 83 00:03:07,580 --> 00:03:10,170 og lad mig faktisk foreslå søgning binær især som 84 00:03:10,170 --> 00:03:12,600 er en vi har brugt en hel bit-- hvis du ikke har random access, 85 00:03:12,600 --> 00:03:15,516 du kan ikke gøre det simple aritmetiske finde ligesom den midterste element 86 00:03:15,516 --> 00:03:16,530 og hoppe ret til det. 87 00:03:16,530 --> 00:03:20,239 Du i stedet nødt til at starte på det første element og lineært søge fra venstre 88 00:03:20,239 --> 00:03:22,780 til højre, hvis du ønsker at finde midten eller noget andet grundstof. 89 00:03:22,780 --> 00:03:24,410 >> PUBLIKUM: Det tager nok mere hukommelse. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: Tager mere hukommelse. 91 00:03:25,040 --> 00:03:27,464 Hvor er det ekstra koste kommer fra i hukommelsen? 92 00:03:27,464 --> 00:03:28,339 >> PUBLIKUM: [uhørligt] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Præcis. 95 00:03:33,440 --> 00:03:35,679 I dette tilfælde her, havde vi en sammenkædet liste for heltal, 96 00:03:35,679 --> 00:03:37,470 og alligevel er vi fordobling mængden af ​​hukommelse 97 00:03:37,470 --> 00:03:39,680 vi har brug for ved også at opbevare disse pejlemærker. 98 00:03:39,680 --> 00:03:42,090 Nu mindre af en big deal som dine structs får større 99 00:03:42,090 --> 00:03:45,320 og du lagre ikke et nummer, men måske en studerende eller en anden genstand. 100 00:03:45,320 --> 00:03:46,880 Men punktet bestemt tilbage. 101 00:03:46,880 --> 00:03:49,421 Og så en række af de aktioner, om hægtede lister blev kaldt 102 00:03:49,421 --> 00:03:50,570 var store O n- lineær. 103 00:03:50,570 --> 00:03:54,730 Ting som indsættelse eller søg eller sletning i tilfælde et element 104 00:03:54,730 --> 00:03:57,720 tilfældigvis i slutningen af listen uanset om det er sorteret eller ej. 105 00:03:57,720 --> 00:04:01,167 >> Nogle gange kan du få heldig og i så nedre grænser på disse operationer 106 00:04:01,167 --> 00:04:04,250 kunne også være konstant tid, hvis du er altid kigger på det første element, 107 00:04:04,250 --> 00:04:05,070 f.eks. 108 00:04:05,070 --> 00:04:09,360 Men i sidste ende, vi lovede at opnå den hellige gral 109 00:04:09,360 --> 00:04:12,630 datastrukturer, eller vis tilnærmelse deraf 110 00:04:12,630 --> 00:04:14,290 ved konstant tid. 111 00:04:14,290 --> 00:04:17,579 Kan vi finde elementer eller tilføje elementer eller fjerne elementer fra en liste? 112 00:04:17,579 --> 00:04:19,059 Vi skal se meget snart. 113 00:04:19,059 --> 00:04:21,100 Og det viser sig, at en af de mekanismer, vi er 114 00:04:21,100 --> 00:04:23,464 vil begynde at bruge i dag, årlige forbrug i p sæt fem, 115 00:04:23,464 --> 00:04:24,630 er faktisk temmelig bekendt. 116 00:04:24,630 --> 00:04:27,430 For eksempel, hvis dette er en flok eksamensspørgsmål bøger, som hver 117 00:04:27,430 --> 00:04:29,660 har en elevs første navn og efternavn på den, 118 00:04:29,660 --> 00:04:31,820 og jeg hente dem fra ved slutningen af ​​en eksamen, 119 00:04:31,820 --> 00:04:33,746 og de er alle temmelig meget i en tilfældig rækkefølge, 120 00:04:33,746 --> 00:04:36,370 og vi ønsker at gå om sortering disse eksamener, så engang sorteres 121 00:04:36,370 --> 00:04:38,661 det er bare meget nemmere og hurtigere at udlevere dem ud igen 122 00:04:38,661 --> 00:04:40,030 til studerende alfabetisk. 123 00:04:40,030 --> 00:04:42,770 Hvad ville dine instinkter være for en bunke af eksamener som denne? 124 00:04:42,770 --> 00:04:45,019 >> Tja, hvis du er ligesom mig, du kunne se, at dette er m, 125 00:04:45,019 --> 00:04:48,505 så jeg har tænkt mig at slags sætte det i, hvis dette er mit bord eller min etage, hvor 126 00:04:48,505 --> 00:04:50,650 Jeg sprede tingene out-- eller min opstilling really-- 127 00:04:50,650 --> 00:04:52,210 Jeg kunne sætte alle MS i der. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Her er en A. Så jeg måske sætte Som herovre. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Her er en anden A. Jeg har tænkt mig at sætte det herovre. 132 00:04:57,980 --> 00:05:02,490 Her er en Z. Her er en anden M. Og så Jeg kunne begynde at gøre bunker som denne. 133 00:05:02,490 --> 00:05:06,620 Og så måske jeg vil gå i senere og sortering af meget nitpicky-ly slags 134 00:05:06,620 --> 00:05:07,710 de enkelte pæle. 135 00:05:07,710 --> 00:05:11,300 Men pointen er, at jeg ville se ved indgangen, at jeg er handed 136 00:05:11,300 --> 00:05:14,016 og jeg ville gøre nogle beregnede beslutning baseret på denne indgang. 137 00:05:14,016 --> 00:05:15,640 Hvis den begynder med A, sætte det derovre. 138 00:05:15,640 --> 00:05:18,980 Hvis den begynder med Z, sætte det over der, og alt derimellem. 139 00:05:18,980 --> 00:05:22,730 >> Så dette er en teknik, der er almindeligt kendt som hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 hvilket generelt betyder at tage som input og bruge dette input til at beregne 141 00:05:26,550 --> 00:05:30,940 en værdi, der generelt er et tal, og at nummer er indekset i et lager 142 00:05:30,940 --> 00:05:32,260 beholder, som et array. 143 00:05:32,260 --> 00:05:35,490 Så med andre ord, kunne jeg have en hash-funktionen, som jeg gør i mit hoved, 144 00:05:35,490 --> 00:05:37,940 at hvis jeg ser nogen er navn, der starter med A, 145 00:05:37,940 --> 00:05:40,190 Jeg har tænkt mig at kortlægge det til nul i mit hoved. 146 00:05:40,190 --> 00:05:44,160 Og hvis jeg ser en person med Z, jeg er kommer til kort, der til 25 i mit hoved 147 00:05:44,160 --> 00:05:46,220 og derefter sætte det ind sidste mest bunken. 148 00:05:46,220 --> 00:05:50,990 >> Nu, hvis du tænker over ikke min hjerne men et C-program, hvilke numre kunne 149 00:05:50,990 --> 00:05:53,170 du stole på at opnå det samme resultat? 150 00:05:53,170 --> 00:05:55,594 Med andre ord, hvis du havde ASCII A, 151 00:05:55,594 --> 00:05:57,510 hvordan kan du bestemme hvad spand at sætte det i? 152 00:05:57,510 --> 00:05:59,801 Du har sandsynligvis ikke ønsker at sætte det ind i spand 65, som 153 00:05:59,801 --> 00:06:01,840 ville være ligesom derovre uden god grund. 154 00:06:01,840 --> 00:06:04,320 Hvor vil du sætte A i form af dens ASCII værdi? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Hvor vil du gøre for at dens ASCII værdi at komme op med en smartere spand 157 00:06:08,920 --> 00:06:09,480 at sætte det i? 158 00:06:09,480 --> 00:06:10,206 >> PUBLIKUM: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Ja. 160 00:06:10,956 --> 00:06:13,190 Så minus A eller minus specifikt 65, hvis det er 161 00:06:13,190 --> 00:06:18,240 en kapital A. Eller 98, hvis det er et lille et. 162 00:06:18,240 --> 00:06:21,300 Og så ville tillade os at, meget enkelt og meget aritmetisk 163 00:06:21,300 --> 00:06:23,260 sætte noget i en spand som. 164 00:06:23,260 --> 00:06:26,010 Så det viser sig, vi rent faktisk gør det så godt selv med quizzer. 165 00:06:26,010 --> 00:06:29,051 >> Så du kan huske du kredsede din undervisning fyrs navn på omslaget. 166 00:06:29,051 --> 00:06:32,270 Og TF navne var organiseret i disse kolonner alfabetisk, 167 00:06:32,270 --> 00:06:34,400 godt, tro det eller ej, når alle 80 plus os 168 00:06:34,400 --> 00:06:37,800 fik sammen den anden aften til lønklasse, det sidste trin i vores grading proces 169 00:06:37,800 --> 00:06:41,830 er at hash quizzer ind i en stor rum etage på [uhørligt] 170 00:06:41,830 --> 00:06:45,110 og lægge alles quizzer ud i nøjagtig den rækkefølge, deres TF s 171 00:06:45,110 --> 00:06:47,700 navne på dækslet, da så er det meget lettere for os 172 00:06:47,700 --> 00:06:51,290 at søge gennem at anvendelse af lineær søge eller anden form for klogskab 173 00:06:51,290 --> 00:06:54,050 til TF at finde hans eller hendes studerendes quizzer. 174 00:06:54,050 --> 00:06:56,060 >> Så denne idé om hashing at du vil se, er 175 00:06:56,060 --> 00:07:00,520 ganske stærke er faktisk temmelig banal og meget intuitiv, 176 00:07:00,520 --> 00:07:03,000 ligesom måske opdele og erobring var i uge nul. 177 00:07:03,000 --> 00:07:05,250 Jeg hurtigt frem til hackathon et par år siden. 178 00:07:05,250 --> 00:07:08,040 Dette var Zamyla og et par andre ansatte hilsen studerende 179 00:07:08,040 --> 00:07:09,030 som de kom ind. 180 00:07:09,030 --> 00:07:12,680 Og vi havde en hel bunke af foldning tabeller der med navneskilte. 181 00:07:12,680 --> 00:07:15,380 Og vi havde navneskilte organiseret med ligesom Som derovre 182 00:07:15,380 --> 00:07:16,690 og Zs derovre. 183 00:07:16,690 --> 00:07:20,350 Og så en af ​​TFS meget behændigt skrev dette som instruktioner 184 00:07:20,350 --> 00:07:21,030 for dagen. 185 00:07:21,030 --> 00:07:24,480 Og i uge 12 af semestret dette alle gav god mening, og alle 186 00:07:24,480 --> 00:07:25,310 vidste, hvad de skal gøre. 187 00:07:25,310 --> 00:07:27,900 Men når du har kø på samme måde, 188 00:07:27,900 --> 00:07:30,272 du gennemføre samme forestilling om en hash. 189 00:07:30,272 --> 00:07:31,730 Så lad os formalisere det en lille smule. 190 00:07:31,730 --> 00:07:32,890 Her er et array. 191 00:07:32,890 --> 00:07:36,820 Det er udarbejdet til at være lidt bred bare at skildre, visuelt, 192 00:07:36,820 --> 00:07:38,920 at vi kan sætte strenge i noget som dette. 193 00:07:38,920 --> 00:07:41,970 Og dette array er tydeligt af størrelse 26 total. 194 00:07:41,970 --> 00:07:43,935 Og de ting kaldes tabel vilkårligt. 195 00:07:43,935 --> 00:07:48,930 Men dette er blot en kunstners gengivelse af, hvad en hash tabel kan være. 196 00:07:48,930 --> 00:07:52,799 >> Så en hashtabel nu kommer til at være et højere niveau datastruktur. 197 00:07:52,799 --> 00:07:54,840 Ved slutningen af ​​dagen vi er ved at se, at du 198 00:07:54,840 --> 00:07:58,700 kan gennemføre en hash tabel, som er meget ligesom check-in-line 199 00:07:58,700 --> 00:08:02,059 ved en hackathon meget som denne Tabellen, der anvendes til sortering eksamen bøger. 200 00:08:02,059 --> 00:08:03,850 Men en hash tabel er art af det høje 201 00:08:03,850 --> 00:08:08,250 koncept, der kunne bruge et array under hætten til at gennemføre den, 202 00:08:08,250 --> 00:08:11,890 eller det kunne bruge en liste længde, eller endog måske nogle andre datastrukturer. 203 00:08:11,890 --> 00:08:15,590 Og nu det er den theme-- udtagning nogle af disse grundlæggende ingredienser 204 00:08:15,590 --> 00:08:18,310 som en matrix, og denne bygning blokere nu en liste længde 205 00:08:18,310 --> 00:08:21,740 og se, hvad vi ellers kan bygge på toppen af ​​dem, ligesom ingredienser 206 00:08:21,740 --> 00:08:26,550 i en opskrift, så mere og mere interessante og nyttige endelige resultater. 207 00:08:26,550 --> 00:08:28,680 >> Så med hash tabellen vi måske gennemføre den 208 00:08:28,680 --> 00:08:32,540 i hukommelsen billedligt som denne, men hvordan kan det faktisk være kodet op? 209 00:08:32,540 --> 00:08:33,789 Nå, måske så enkelt er det. 210 00:08:33,789 --> 00:08:38,270 Hvis kapacitet i alle kasketter, er bare nogle constant-- for eksempel 26, 211 00:08:38,270 --> 00:08:42,030 for 26 bogstaver i det alphabet-- Jeg kunne kalde min variabel bord, 212 00:08:42,030 --> 00:08:45,630 og jeg kunne påstå, at jeg har tænkt mig at sætte char stjerner derinde, eller snor. 213 00:08:45,630 --> 00:08:49,880 Så det er så simpelt som dette, hvis du ønsker at gennemføre en hash tabel. 214 00:08:49,880 --> 00:08:51,490 Og dog, det er virkelig bare et array. 215 00:08:51,490 --> 00:08:53,198 Men igen, en hash Tabellen er nu, hvad vi får 216 00:08:53,198 --> 00:08:57,470 kalder en abstrakt datatype, der er bare sortering af en begrebsmæssig lagdeling på toppen 217 00:08:57,470 --> 00:09:00,780 af noget mere prosaisk Nu vil et array. 218 00:09:00,780 --> 00:09:02,960 >> Nu, hvordan gør vi gå om at løse problemer? 219 00:09:02,960 --> 00:09:06,980 Tja, tidligere havde jeg den luksus for at have nok bordplads her 220 00:09:06,980 --> 00:09:09,460 så jeg kunne sætte quizzer overalt jeg ønskede. 221 00:09:09,460 --> 00:09:10,620 Så kan gå her. 222 00:09:10,620 --> 00:09:12,100 Zs kan gå her. 223 00:09:12,100 --> 00:09:13,230 Ms kan gå her. 224 00:09:13,230 --> 00:09:14,740 Og så havde jeg nogle ekstra plads. 225 00:09:14,740 --> 00:09:18,740 Men det er lidt af en snyde ret nu, fordi denne tabel, hvis jeg virkelig 226 00:09:18,740 --> 00:09:22,720 tænkte på det som et array, er bare kommer til at være af en vis fast størrelse. 227 00:09:22,720 --> 00:09:25,380 >> Så teknisk set, hvis jeg trækker op en anden elevs quiz 228 00:09:25,380 --> 00:09:28,490 og se, åh, denne persons navn starter med et A også, 229 00:09:28,490 --> 00:09:30,980 Jeg slags ønsker at sætte det der. 230 00:09:30,980 --> 00:09:34,740 Men så snart jeg sætte det der, hvis denne tabel faktisk udgør et array, 231 00:09:34,740 --> 00:09:37,840 Jeg har tænkt mig at være tvingende eller clobbering hvem denne studerendes quiz er. 232 00:09:37,840 --> 00:09:38,340 Right? 233 00:09:38,340 --> 00:09:41,972 Hvis dette er et array, kun én ting kan gå i hver af disse celler eller elementer. 234 00:09:41,972 --> 00:09:43,680 Og så jeg har slags at vælge og vrage. 235 00:09:43,680 --> 00:09:45,735 >> Nu jeg tidligere slags snydt og gjorde dette eller jeg 236 00:09:45,735 --> 00:09:47,526 lige slags stablet dem over hinanden. 237 00:09:47,526 --> 00:09:49,170 Men det kommer ikke til at flyve i koden. 238 00:09:49,170 --> 00:09:52,260 Så hvor kan jeg sætte anden elev, hvis navn 239 00:09:52,260 --> 00:09:54,964 er A, hvis alt havde jeg er dette tilgængelig tabel plads? 240 00:09:54,964 --> 00:09:57,880 Og jeg har brugt tre slots og det ser ud der er bare et par andre. 241 00:09:57,880 --> 00:09:58,959 Hvad kunne du gøre? 242 00:09:58,959 --> 00:09:59,834 PUBLIKUM: [uhørligt] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Ja. 245 00:10:01,315 --> 00:10:02,370 Måske lad os bare holde det simpelt. 246 00:10:02,370 --> 00:10:02,660 Right? 247 00:10:02,660 --> 00:10:04,243 Det passer ikke, hvor jeg ønsker at sætte det. 248 00:10:04,243 --> 00:10:07,450 Så jeg har tænkt mig at sætte det teknisk hvor B ville gå. 249 00:10:07,450 --> 00:10:09,932 Nu, selvfølgelig, er jeg begyndt at male mig op i et hjørne. 250 00:10:09,932 --> 00:10:11,890 Hvis jeg kommer til en elev hvis navn er faktisk B, 251 00:10:11,890 --> 00:10:14,840 nu B vil blive flyttet lidt fremad, som kunne ske, jep, 252 00:10:14,840 --> 00:10:17,530 hvis dette er et B, nu er det at gå her. 253 00:10:17,530 --> 00:10:20,180 >> Og så dette meget hurtigt kan blive problematisk, 254 00:10:20,180 --> 00:10:23,850 men det er en teknik, der faktisk betegnes som lineær probing, 255 00:10:23,850 --> 00:10:26,650 hvorved du lige overveje din array til at være langs linien. 256 00:10:26,650 --> 00:10:29,680 Og du bare slags sonde eller inspicere hver tilgængelig element 257 00:10:29,680 --> 00:10:31,360 på udkig efter en ledig plet. 258 00:10:31,360 --> 00:10:34,010 Og så snart du finder en, du skulle tabe det derinde. 259 00:10:34,010 --> 00:10:38,390 >> Nu, idet den betalte pris nu denne løsning er hvad? 260 00:10:38,390 --> 00:10:41,300 Vi har en fast størrelse array, og når jeg sætter navne 261 00:10:41,300 --> 00:10:44,059 i det mindste i begyndelsen, hvad er køretiden for indsættelse 262 00:10:44,059 --> 00:10:46,350 for at sætte de studerende quizzer i de rigtige spande? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O i hvad? 265 00:10:50,002 --> 00:10:51,147 >> PUBLIKUM: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Jeg hørte store O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Ikke sandt. 269 00:10:54,300 --> 00:10:56,490 Men vi vil drille hinanden hvorfor i bare et øjeblik. 270 00:10:56,490 --> 00:10:57,702 Hvad ellers kunne det være? 271 00:10:57,702 --> 00:10:58,755 >> PUBLIKUM: [uhørligt] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Og lad mig gøre det visuelt. 273 00:11:00,380 --> 00:11:04,720 Så formoder, det er bogstavet S. 274 00:11:04,720 --> 00:11:05,604 >> PUBLIKUM: Det er én. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Det er én. 276 00:11:06,520 --> 00:11:06,710 Right? 277 00:11:06,710 --> 00:11:08,950 Dette er et array, som betyder, at vi har random access. 278 00:11:08,950 --> 00:11:11,790 Og hvis vi tænker på dette som nul og dette som 25, 279 00:11:11,790 --> 00:11:13,800 og vi indser, at, åh, her er mit input S, 280 00:11:13,800 --> 00:11:16,350 Jeg kan helt sikkert konvertere S, en ASCII-tegn, 281 00:11:16,350 --> 00:11:18,540 til et tilsvarende antal mellem nul og 25 282 00:11:18,540 --> 00:11:20,910 og derefter straks sætte det, hvor det hører hjemme. 283 00:11:20,910 --> 00:11:26,120 >> Men selvfølgelig, så snart jeg kommer til anden person, der er navn er A, B eller C 284 00:11:26,120 --> 00:11:29,300 til sidst, hvis jeg har brugt den lineær sondering som min løsning, 285 00:11:29,300 --> 00:11:31,360 køretiden for indsættelse i værste fald 286 00:11:31,360 --> 00:11:33,120 rent faktisk vil udvikle sig til hvad? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Og jeg hørte det her korrekt tidligt. 289 00:11:36,045 --> 00:11:36,920 PUBLIKUM: [uhørligt] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Så det er n faktisk en gang du har et tilstrækkeligt stort datasæt. 291 00:11:41,620 --> 00:11:44,410 Så på den ene side, hvis dit array er stor nok 292 00:11:44,410 --> 00:11:48,287 og dine data er sparsomme nok, du få denne smukke konstant tid. 293 00:11:48,287 --> 00:11:50,620 Men så snart du begynder at få flere og flere elementer, 294 00:11:50,620 --> 00:11:53,200 og bare statistisk får du flere mennesker med bogstavet 295 00:11:53,200 --> 00:11:56,030 A som deres navn eller bogstavet B, det kunne potentielt 296 00:11:56,030 --> 00:11:57,900 udvikle sig til noget mere lineær. 297 00:11:57,900 --> 00:11:59,640 Så ikke helt perfekt. 298 00:11:59,640 --> 00:12:00,690 Så kunne vi gøre bedre? 299 00:12:00,690 --> 00:12:03,210 >> Nå, hvad var vores løsning før, når vi 300 00:12:03,210 --> 00:12:06,820 ønsker at have mere dynamik end noget som et array tilladt? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 PUBLIKUM: [uhørligt] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Hvad gjorde vi præsentere? 304 00:12:10,030 --> 00:12:10,530 Ja. 305 00:12:10,530 --> 00:12:11,430 Så en sammenkædet liste. 306 00:12:11,430 --> 00:12:14,430 Nå, lad os se, hvad en sammenkædet Listen kan gøre for os i stedet. 307 00:12:14,430 --> 00:12:17,630 Nå, lad mig foreslå, at vi tegne billedet som følger. 308 00:12:17,630 --> 00:12:19,620 Nu er det en anden billede fra et eksempel 309 00:12:19,620 --> 00:12:24,750 fra en anden tekst, faktisk, at er faktisk ved hjælp af en vifte af størrelse 31. 310 00:12:24,750 --> 00:12:28,220 Og denne forfatter simpelthen besluttede at hash strings 311 00:12:28,220 --> 00:12:32,430 ikke er baseret på personens navn, men baseret på deres fødselsdage. 312 00:12:32,430 --> 00:12:35,680 Uafhængigt af den måned, de regnede hvis du er født den første i en måned 313 00:12:35,680 --> 00:12:39,580 eller den 31. i en måned, forfatteren vil hash baseret på denne værdi, 314 00:12:39,580 --> 00:12:44,154 således at sprede navne en smule mere end blot 26 spots kunne give. 315 00:12:44,154 --> 00:12:47,320 Og måske er det en smule mere ensartet end at gå med alfabetiske bogstaver, 316 00:12:47,320 --> 00:12:50,236 fordi selvfølgelig er der sandsynligvis flere mennesker i verden med navne 317 00:12:50,236 --> 00:12:54,020 at starte med A end sikkert nogle andre bogstaver i alfabetet. 318 00:12:54,020 --> 00:12:56,380 Så måske det er lidt mere ensartet, antager 319 00:12:56,380 --> 00:12:58,640 en ensartet fordeling babyer over en måned. 320 00:12:58,640 --> 00:12:59,990 >> Men, selvfølgelig, det er stadig ufuldkommen. 321 00:12:59,990 --> 00:13:00,370 Right? 322 00:13:00,370 --> 00:13:01,370 Vi skal have kollisioner. 323 00:13:01,370 --> 00:13:04,680 Flere mennesker i denne datastruktur er stadig 324 00:13:04,680 --> 00:13:08,432 har den samme fødselsdato mindst du er uanset måned. 325 00:13:08,432 --> 00:13:09,640 Men hvad har forfatteren gjort? 326 00:13:09,640 --> 00:13:13,427 Tja, det ser ud til vi har en array på den venstre side trukket vertikalt, 327 00:13:13,427 --> 00:13:15,010 men det er bare en kunstners gengivelse. 328 00:13:15,010 --> 00:13:18,009 Det er ligegyldigt, hvilken retning du tegne et array, er det stadig et array. 329 00:13:18,009 --> 00:13:20,225 Hvad er dette en række tilsyneladende? 330 00:13:20,225 --> 00:13:21,500 >> PUBLIKUM: Linked listen. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Ja. 332 00:13:21,650 --> 00:13:23,490 Det ligner det er en vifte af linkede liste. 333 00:13:23,490 --> 00:13:26,490 Så igen, at dette punkt i form anvende disse datastrukturer nu 334 00:13:26,490 --> 00:13:28,550 som ingredienser til mere interessante løsninger, 335 00:13:28,550 --> 00:13:30,862 du kan absolut tage en grundlæggende som et array, 336 00:13:30,862 --> 00:13:33,320 og derefter tage noget mere interessant som en sammenkædet liste 337 00:13:33,320 --> 00:13:36,660 og endda kombinere dem til et endnu mere interessant datastruktur. 338 00:13:36,660 --> 00:13:39,630 Og ja, dette også ville kaldes en hash tabel, 339 00:13:39,630 --> 00:13:42,610 hvorved array er virkelig hash tabellen, 340 00:13:42,610 --> 00:13:45,600 men at hash bordet har kæder, så at sige, 341 00:13:45,600 --> 00:13:50,220 der kan vokse eller skrumpe baseret på Antallet af elementer, du vil indsætte. 342 00:13:50,220 --> 00:13:52,990 >> Nu derfor, hvad er køretiden nu? 343 00:13:52,990 --> 00:13:58,030 Hvis jeg ønsker at indsætte nogen hvis fødselsdag er den 31. oktober 344 00:13:58,030 --> 00:13:59,040 hvor er han eller hun gå? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Ok. 347 00:14:01,030 --> 00:14:02,819 Nederst, hvor der står 31. 348 00:14:02,819 --> 00:14:03,610 Og det er perfekt. 349 00:14:03,610 --> 00:14:05,060 Det var konstant tid. 350 00:14:05,060 --> 00:14:08,760 Men hvad nu, hvis vi finder en anden hvis fødselsdag er, lad os se, 351 00:14:08,760 --> 00:14:10,950 Oktober, november, 31. December? 352 00:14:10,950 --> 00:14:12,790 Hvor er han eller hun kommer til at gå? 353 00:14:12,790 --> 00:14:13,290 Samme ting. 354 00:14:13,290 --> 00:14:13,970 To skridt selv. 355 00:14:13,970 --> 00:14:15,303 Det er konstant dog er det ikke? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Ok. 358 00:14:16,860 --> 00:14:17,840 I øjeblikket er det. 359 00:14:17,840 --> 00:14:20,570 Men i det generelle tilfælde, jo flere mennesker, vi tilføjer, 360 00:14:20,570 --> 00:14:23,790 probalistisk, vil vi for at få flere og flere kollisioner. 361 00:14:23,790 --> 00:14:26,820 >> Nu er det en lille bedre, fordi teknisk 362 00:14:26,820 --> 00:14:34,580 nu er mine kæder kunne være i værste fald hvor længe? 363 00:14:34,580 --> 00:14:38,890 Hvis jeg indsætter n folk ind i denne mere sofistikeret datastruktur, n mennesker, 364 00:14:38,890 --> 00:14:41,080 i værste fald kommer til at være n. 365 00:14:41,080 --> 00:14:41,815 Hvorfor? 366 00:14:41,815 --> 00:14:43,332 >> PUBLIKUM: Fordi hvis alle har samme fødselsdag, 367 00:14:43,332 --> 00:14:44,545 de kommer til at være en linje. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Det kan være en smule konstruerede, men virkelig i værste fald 370 00:14:47,480 --> 00:14:50,117 hvis alle har samme fødselsdag, givet de indgange, du har, 371 00:14:50,117 --> 00:14:51,950 du kommer til at have en massivt lang kæde. 372 00:14:51,950 --> 00:14:54,241 Og så kan du kalde det en hash tabellen, men det er virkelig 373 00:14:54,241 --> 00:14:56,810 blot en massiv forbundet liste med en hel masse spildplads. 374 00:14:56,810 --> 00:15:00,460 Men generelt, hvis vi antager, at mindst fødselsdage er uniform-- 375 00:15:00,460 --> 00:15:01,750 og er det sandsynligvis ikke. 376 00:15:01,750 --> 00:15:02,587 Jeg gør det op. 377 00:15:02,587 --> 00:15:04,420 Men hvis vi antager, for af hensyn til diskussion 378 00:15:04,420 --> 00:15:07,717 at de er, så i teorien, hvis dette er den lodrette repræsentation 379 00:15:07,717 --> 00:15:11,050 af array, ja så forhåbentlig er du vil få kæder, der er, du kender, 380 00:15:11,050 --> 00:15:15,880 omtrent den samme længde, hvor hver af disse repræsenterer en dag i måneden. 381 00:15:15,880 --> 00:15:19,930 >> Nu, hvis der er 31 dage i måneden, det betyder min køretid virkelig 382 00:15:19,930 --> 00:15:25,230 er stor O n over 31, som føles bedre end lineær. 383 00:15:25,230 --> 00:15:27,950 Men hvad var en af ​​vores forpligtelser et par uger 384 00:15:27,950 --> 00:15:31,145 siden, når det kom til at udtrykke køretiden for en algoritme? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Bare kun se på den høje orden sigt. 387 00:15:35,190 --> 00:15:35,690 Right? 388 00:15:35,690 --> 00:15:37,400 31 er absolut nyttige. 389 00:15:37,400 --> 00:15:39,610 Men det er stadig big O n. 390 00:15:39,610 --> 00:15:41,730 Men en af ​​de temaer, af problem sæt fem 391 00:15:41,730 --> 00:15:43,950 vil være til anerkender, at absolut, 392 00:15:43,950 --> 00:15:47,320 asymptotisk, teoretisk denne datastruktur 393 00:15:47,320 --> 00:15:50,470 er ikke bedre end bare en massiv linkede liste. 394 00:15:50,470 --> 00:15:53,550 Og ja, i værste fald, dette hash tabel kan udvikle sig til det. 395 00:15:53,550 --> 00:15:57,620 >> Men i den virkelige verden, med os mennesker at egne Mac eller pc eller hvad 396 00:15:57,620 --> 00:16:01,240 og kører virkelige verden software på virkelige verden data 397 00:16:01,240 --> 00:16:03,260 hvilken algoritme vil du foretrække? 398 00:16:03,260 --> 00:16:09,180 Den ene, der tager de endelige skridt eller den en, der tager n divideret med 31 trin 399 00:16:09,180 --> 00:16:12,900 at finde nogle stykke af data, eller at slå op nogle oplysninger? 400 00:16:12,900 --> 00:16:16,580 Jeg mener, absolut de 31 mærker en forskel i den virkelige verden. 401 00:16:16,580 --> 00:16:18,540 Det er 31 gange hurtigere. 402 00:16:18,540 --> 00:16:20,880 Og vi mennesker er helt sikkert vil forstå, at. 403 00:16:20,880 --> 00:16:23,004 >> Så indser dikotomien der mellem faktisk 404 00:16:23,004 --> 00:16:25,920 taler om ting, teoretisk og asymptotisk som definitivt 405 00:16:25,920 --> 00:16:28,760 har værdi som vi har set, men i den virkelige verden, 406 00:16:28,760 --> 00:16:32,930 hvis du interesserer bare gøre human glad for generelle input, 407 00:16:32,930 --> 00:16:36,010 du kan meget vel ønsker at acceptere den kendsgerning, at ja, det er lineær, 408 00:16:36,010 --> 00:16:38,360 men det er 31 gange hurtigere end lineær kunne være. 409 00:16:38,360 --> 00:16:41,610 Og bedre endnu, vi ikke bare nødt til at gøre noget vilkårlig som en fødselsdato, 410 00:16:41,610 --> 00:16:44,030 vi kunne bruge lidt mere tid og dygtighed 411 00:16:44,030 --> 00:16:47,140 og tænke over, hvad vi kan gøre, givet en persons navn og måske 412 00:16:47,140 --> 00:16:50,130 deres fødselsdato at kombinere de ingredienser til at finde ud af noget 413 00:16:50,130 --> 00:16:52,720 der er virkelig mere ensartet og mindre jaggy, 414 00:16:52,720 --> 00:16:56,250 så at sige end dette billede i øjeblikket tyder det kunne være. 415 00:16:56,250 --> 00:16:57,750 Hvordan kunne vi gennemføre dette i koden? 416 00:16:57,750 --> 00:17:00,280 Nå, lad mig foreslå, at vi bare låne nogle syntaks vi har 417 00:17:00,280 --> 00:17:01,799 brugt et par gange hidtil. 418 00:17:01,799 --> 00:17:03,590 Og jeg har tænkt mig at definere en knude, som igen 419 00:17:03,590 --> 00:17:06,812 er en generisk betegnelse for blot nogle container for nogle datastruktur. 420 00:17:06,812 --> 00:17:09,020 Jeg har tænkt mig at foreslå, at en streng går derind. 421 00:17:09,020 --> 00:17:11,369 Men vi kommer til at begynde at tage dem uddannelse hjul off nu. 422 00:17:11,369 --> 00:17:13,230 >> Ikke mere CS50 bibliotek virkelig, medmindre du ønsker 423 00:17:13,230 --> 00:17:15,230 at bruge det til din endelige projekt, hvilket er fint, 424 00:17:15,230 --> 00:17:18,569 men nu vil vi trække sig tilbage gardin og siger, det er bare en char stjerne. 425 00:17:18,569 --> 00:17:22,069 Så ordet der vil være personens navn pågældende. 426 00:17:22,069 --> 00:17:25,079 Og nu har jeg et link her til den næste node 427 00:17:25,079 --> 00:17:28,170 således at disse repræsenterer hvert af knudepunkterne 428 00:17:28,170 --> 00:17:30,950 i kæden potentielt af en sammenkædet liste. 429 00:17:30,950 --> 00:17:34,090 >> Og nu, hvordan gør jeg erklærer hash tabellen selv? 430 00:17:34,090 --> 00:17:36,660 Hvordan kan jeg erklære hele denne struktur? 431 00:17:36,660 --> 00:17:40,960 Nå, virkelig, ligesom jeg brugte en pointer til blot det første element i en liste 432 00:17:40,960 --> 00:17:44,510 før, ligeledes kan jeg bare sige Jeg skal bare have en masse pointers 433 00:17:44,510 --> 00:17:46,270 at gennemføre hele denne hash tabel. 434 00:17:46,270 --> 00:17:49,484 Jeg har tænkt mig at have et array kaldet bord til hash tabellen. 435 00:17:49,484 --> 00:17:50,900 Det kommer til at være på størrelse kapacitet. 436 00:17:50,900 --> 00:17:52,525 Det er, hvor mange elementer kan passe ind i det. 437 00:17:52,525 --> 00:17:56,180 Og hver af disse elementer i dette array vil være en node stjerne. 438 00:17:56,180 --> 00:17:56,810 Hvorfor? 439 00:17:56,810 --> 00:18:00,160 Nå, per dette billede, hvad jeg gennemførelse af hash tabellen som 440 00:18:00,160 --> 00:18:04,330 effektivt i starten er bare dette array, som vi har trukket vertikalt, 441 00:18:04,330 --> 00:18:06,820 hver af hvis firkanter betegner en pointer. 442 00:18:06,820 --> 00:18:09,170 At dem, der har skråstreger gennem dem er lige nul. 443 00:18:09,170 --> 00:18:11,410 Og dem, der har pile der går til højre 444 00:18:11,410 --> 00:18:16,140 er faktiske henvisninger til faktiske noder, ergo starten på en sammenkædet liste. 445 00:18:16,140 --> 00:18:19,050 >> Så her er så, hvordan vi kan gennemføre en hash tabel, 446 00:18:19,050 --> 00:18:21,580 implementerer særskilt chaining. 447 00:18:21,580 --> 00:18:22,840 Nu kan vi gøre bedre? 448 00:18:22,840 --> 00:18:25,632 Okay jeg lovede sidste gang, vi kunne opnå konstant tid. 449 00:18:25,632 --> 00:18:27,381 Og jeg slags gav dig konstant tid her, 450 00:18:27,381 --> 00:18:29,850 men så sagde ikke rigtig konstant tid, fordi det er stadig 451 00:18:29,850 --> 00:18:31,890 afhængig af den totale antallet af elementer 452 00:18:31,890 --> 00:18:34,500 du indtaster ind datastrukturen. 453 00:18:34,500 --> 00:18:35,980 Men formoder, at vi gjorde dette. 454 00:18:35,980 --> 00:18:39,550 Lad mig gå tilbage til skærmen herovre. 455 00:18:39,550 --> 00:18:44,520 Lad mig også projicere det op her, klar skærmen, og formoder jeg gjorde dette. 456 00:18:44,520 --> 00:18:49,300 Antag jeg ønskede at indsætte navnet Daven i ind i min datastruktur. 457 00:18:49,300 --> 00:18:52,100 >> Så jeg ønsker at indsætte en streng Daven i datastrukturen. 458 00:18:52,100 --> 00:18:54,370 Hvad hvis jeg ikke bruger en hash tabellen, men jeg bruger 459 00:18:54,370 --> 00:18:56,980 noget, der er mere trælignende ligesom et stamtræ, hvor 460 00:18:56,980 --> 00:18:59,670 du har nogle rod på toppen og derefter knudepunkter og blade 461 00:18:59,670 --> 00:19:01,440 at gå nedad og udad. 462 00:19:01,440 --> 00:19:04,450 Antag derefter, at jeg vil indsætte Daven s 463 00:19:04,450 --> 00:19:06,430 i, hvad der er i øjeblikket en tom liste. 464 00:19:06,430 --> 00:19:09,780 Jeg har tænkt mig at gøre følgende: Jeg er vil skabe et knudepunkt i denne familie 465 00:19:09,780 --> 00:19:15,170 trælignende datastruktur, der ser lidt ligesom dette, som hver 466 00:19:15,170 --> 00:19:19,640 rektangler har, lad os sige, for nu 26 elementer i det. 467 00:19:19,640 --> 00:19:21,650 Og hver af cellerne i dette array går 468 00:19:21,650 --> 00:19:23,470 at repræsentere bogstav i et alfabet. 469 00:19:23,470 --> 00:19:28,190 >> Konkret vil jeg behandle dette er A, så B, og C, og D, 470 00:19:28,190 --> 00:19:29,310 denne ene her. 471 00:19:29,310 --> 00:19:32,940 Så det kommer til at effektivt repræsenterer bogstavet D. 472 00:19:32,940 --> 00:19:36,040 Men at indsætte alle Daven s navn, jeg er nødt til at gøre lidt mere. 473 00:19:36,040 --> 00:19:37,840 Så jeg først kommer til hash, så at sige. 474 00:19:37,840 --> 00:19:41,049 Jeg har tænkt mig at kigge på det første bogstav i Daven s hvilket naturligvis er en D, 475 00:19:41,049 --> 00:19:42,840 og jeg har tænkt mig at tildele en knude, der ser 476 00:19:42,840 --> 00:19:45,570 ligesom denne-- en stor rektangel big nok til at passe til hele alfabetet. 477 00:19:45,570 --> 00:19:47,140 >> Nu D er færdig. 478 00:19:47,140 --> 00:19:49,720 Nu A. D-A-V-E-N er målet. 479 00:19:49,720 --> 00:19:51,220 Så nu, hvad jeg har tænkt mig at gøre, er dette. 480 00:19:51,220 --> 00:19:54,027 Så snart jeg begyndte D varsel der er ingen pointer der. 481 00:19:54,027 --> 00:19:56,860 Det er skrald værdier i øjeblikket, eller jeg kunne initialisere den til null. 482 00:19:56,860 --> 00:19:59,630 Men lad mig holde i gang med denne idé om at bygge et træ. 483 00:19:59,630 --> 00:20:04,260 Lad mig tildele endnu en af ​​disse noder, der har 26 elementer i det. 484 00:20:04,260 --> 00:20:05,150 >> Og ved du hvad? 485 00:20:05,150 --> 00:20:09,130 Hvis dette er bare en knude i hukommelsen som Jeg oprettede med malloc, ved hjælp af en struct 486 00:20:09,130 --> 00:20:11,240 som vi snart vil se, Jeg har tænkt mig at gøre denne-- 487 00:20:11,240 --> 00:20:14,450 Jeg har tænkt mig at tegne en pil fra de ting, der repræsenterede D ned 488 00:20:14,450 --> 00:20:15,860 til denne nye knudepunkt. 489 00:20:15,860 --> 00:20:19,240 Og nu, først den næste brev i Daven navn, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- Jeg har tænkt mig at gå videre og tegne en anden node som dette, 491 00:20:24,150 --> 00:20:30,150 hvorved V elementer her, som vi vil trække for instance-- hovsa. 492 00:20:30,150 --> 00:20:31,020 Vi vil ikke trække der. 493 00:20:31,020 --> 00:20:31,936 Det kommer til at gå her. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Så vi kommer til at anser dette for at være V. 496 00:20:35,712 --> 00:20:44,920 Og derefter ned her vi kommer til indeks ned fra V ind i, hvad vi vil overveje E. 497 00:20:44,920 --> 00:20:50,100 Og så herfra vil vi gå have en af ​​disse knudepunkter her. 498 00:20:50,100 --> 00:20:52,930 Og nu har vi et spørgsmål at besvare. 499 00:20:52,930 --> 00:20:57,840 Jeg har brug for en eller anden måde viser, at vi er ved enden af ​​strengen Daven. 500 00:20:57,840 --> 00:20:59,490 Så jeg kunne bare lade det null. 501 00:20:59,490 --> 00:21:02,670 >> Men hvad hvis vi har Daven s fulde navn også, som 502 00:21:02,670 --> 00:21:04,280 er, som vi har sagt, Davenport? 503 00:21:04,280 --> 00:21:06,970 Så hvad nu hvis Daven er faktisk en understreng, 504 00:21:06,970 --> 00:21:08,960 et præfiks af en meget længere snor? 505 00:21:08,960 --> 00:21:11,450 Vi kan ikke bare permanent siger ingenting kommer 506 00:21:11,450 --> 00:21:14,410 at gå der, fordi vi kunne aldrig indsætte et ord ligesom Davenport 507 00:21:14,410 --> 00:21:15,840 i denne datastruktur 508 00:21:15,840 --> 00:21:19,560 >> Så hvad vi kunne gøre i stedet er behandle hvert af disse elementer 509 00:21:19,560 --> 00:21:22,170 som måske har to elementer inde i dem. 510 00:21:22,170 --> 00:21:24,810 Den ene er en pointer, ja, som jeg har gjort. 511 00:21:24,810 --> 00:21:27,100 Så hver af disse kasser er ikke blot en celle. 512 00:21:27,100 --> 00:21:29,855 Men hvad nu, hvis top en-- bunden ens 513 00:21:29,855 --> 00:21:32,230 kommer til at være nul, fordi der er ingen Davenport endnu. 514 00:21:32,230 --> 00:21:34,197 Hvad hvis den øverste er nogle særlige værdi? 515 00:21:34,197 --> 00:21:36,530 Og det kommer til at være lidt svært at tegne det denne størrelse. 516 00:21:36,530 --> 00:21:38,130 Men formoder, det er bare et flueben. 517 00:21:38,130 --> 00:21:38,920 Tjek. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N er en streng i denne datastruktur. 519 00:21:44,230 --> 00:21:48,350 >> I mellemtiden, hvis jeg havde mere plads her, jeg kunne gøre P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 og jeg kunne sætte check i knudepunktet der har bogstavet T til allersidst. 521 00:21:52,650 --> 00:21:55,460 Så dette er et massivt kompleks udseende datastruktur. 522 00:21:55,460 --> 00:21:57,210 Og min håndskrift bestemt ikke hjælpe. 523 00:21:57,210 --> 00:22:00,043 Men hvis jeg ønskede at indsætte noget andet, overveje, hvad vi ville gøre. 524 00:22:00,043 --> 00:22:03,370 Hvis vi ønskede at sætte David i, vi ville følge den samme logik, D-A-V, 525 00:22:03,370 --> 00:22:08,802 men nu vil jeg gerne i den næste element ikke fra E, men fra I til D. 526 00:22:08,802 --> 00:22:10,760 Så der vil være flere knuder i træet. 527 00:22:10,760 --> 00:22:12,325 Vi kommer til at have opkald malloc mere. 528 00:22:12,325 --> 00:22:14,700 Men jeg ønsker ikke at lave en komplet rod af dette billede. 529 00:22:14,700 --> 00:22:17,710 Så lad os i stedet se på en der er blevet præ-formuleret 530 00:22:17,710 --> 00:22:21,810 som dette med ikke dot, dot, prikker, men blot forkortede arrays. 531 00:22:21,810 --> 00:22:23,950 Men hver af knudepunkterne i dette træ op her 532 00:22:23,950 --> 00:22:26,700 repræsenterer den samme thing-- et array Ray størrelse 26. 533 00:22:26,700 --> 00:22:28,860 >> Eller hvis vi ønsker at være virkelig ordentlig nu, hvad 534 00:22:28,860 --> 00:22:30,790 hvis en persons navn som en apostrof, lad os 535 00:22:30,790 --> 00:22:35,560 antager, at hvert knudepunkt har faktisk ligesom 27 indekser i den, ikke bare 26. 536 00:22:35,560 --> 00:22:42,020 Så det nu kommer til at være en data struktur, der kaldes en trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 En trie, som er angiveligt historisk set et smart navn til et træ 538 00:22:46,120 --> 00:22:49,040 der er optimeret til hentning, hvilket naturligvis, 539 00:22:49,040 --> 00:22:50,870 staves med et I-E, så det er trie. 540 00:22:50,870 --> 00:22:52,710 Men det er historien om trie. 541 00:22:52,710 --> 00:22:55,860 >> Så en trie er dette træ-lignende data struktur som et stamtræ 542 00:22:55,860 --> 00:22:57,510 der i sidste ende opfører sig sådan. 543 00:22:57,510 --> 00:23:00,890 Og her er bare endnu et eksempel på en hel masse andre folks navne. 544 00:23:00,890 --> 00:23:03,540 Men spørgsmålet er nu ved hånden er det har 545 00:23:03,540 --> 00:23:08,070 vi opnået ved at indføre velsagtens en mere kompliceret datastruktur, og en, 546 00:23:08,070 --> 00:23:09,870 helt ærligt, der bruger en masse hukommelse. 547 00:23:09,870 --> 00:23:11,703 >> Fordi selvom, i det øjeblik, jeg er kun 548 00:23:11,703 --> 00:23:15,050 ved hjælp af D's pointer og A og V og Es og Ns, 549 00:23:15,050 --> 00:23:16,700 Jeg spilder en dælen af ​​meget hukommelse. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Men hvor jeg tilbringer en ressource, Jeg har tendens til at gøre vinde tilbage en anden. 552 00:23:22,660 --> 00:23:26,020 Så hvis jeg bruger mere plads, hvad er sandsynligvis det håb? 553 00:23:26,020 --> 00:23:27,407 At jeg bruger mindre hvad? 554 00:23:27,407 --> 00:23:28,240 PUBLIKUM: Mindre tid. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Time. 556 00:23:28,990 --> 00:23:30,320 Nu hvorfor kan det være? 557 00:23:30,320 --> 00:23:33,880 Nå, hvad er indsættelsen tid, i form af store O nu 558 00:23:33,880 --> 00:23:37,660 af et navn som Daven eller Davenport eller David? 559 00:23:37,660 --> 00:23:39,340 Nå, Daven var fem trin. 560 00:23:39,340 --> 00:23:42,350 Davenport ville være ni trin, så det ville være et par flere trin. 561 00:23:42,350 --> 00:23:44,250 David ville være fem skridt så godt. 562 00:23:44,250 --> 00:23:47,230 Så dem er konkrete tal, men mon der er 563 00:23:47,230 --> 00:23:49,550 en øvre grænse for længden af ​​en persons navn. 564 00:23:49,550 --> 00:23:52,240 Og ja, i det problem sæt af fem specifikation 565 00:23:52,240 --> 00:23:54,050 vi kommer til at foreslå at det er noget 566 00:23:54,050 --> 00:23:55,470 der er 40-nogle-ulige tegn. 567 00:23:55,470 --> 00:23:58,180 >> Realistisk set ingen har en uendelig lang navn, 568 00:23:58,180 --> 00:24:01,542 hvilket vil sige, at længden af ​​en navn eller længden af ​​en streng vi måske 569 00:24:01,542 --> 00:24:03,750 har visse tilstand struktur er det nok? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Det er konstant. 572 00:24:06,250 --> 00:24:06,430 Right? 573 00:24:06,430 --> 00:24:09,310 Det kan være en stor konstant ligesom 40 noget, men det er konstant. 574 00:24:09,310 --> 00:24:13,752 Og det har ingen afhængighed af hvor mange andre navne er i denne datastruktur. 575 00:24:13,752 --> 00:24:15,460 Med andre ord, hvis I ville nu indsætte 576 00:24:15,460 --> 00:24:20,540 Colton eller Gabriel eller Rob eller Zamyla eller Alison eller Belinda eller andre navne 577 00:24:20,540 --> 00:24:23,940 fra personalet i disse data struktur, er køretiden 578 00:24:23,940 --> 00:24:26,750 indsætte andre navne vil være på alle påvirket 579 00:24:26,750 --> 00:24:30,220 ved hvor mange andre elementer er i data, der allerede struktur? 580 00:24:30,220 --> 00:24:31,040 Det er det ikke. 581 00:24:31,040 --> 00:24:31,540 Right? 582 00:24:31,540 --> 00:24:36,150 Fordi vi er effektivt ved hjælp af denne multi-lag hashtabel. 583 00:24:36,150 --> 00:24:38,280 Og køretiden for nogen af ​​disse operationer 584 00:24:38,280 --> 00:24:41,510 afhænger ikke af antallet af elementer, der er i datastrukturen 585 00:24:41,510 --> 00:24:43,090 eller som i sidste ende går at være i datastrukturen, 586 00:24:43,090 --> 00:24:44,714 men af ​​længden af ​​hvad der specifikt? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Strengen er indsat, hvilket gør 589 00:24:49,200 --> 00:24:52,580 dette asymptotisk konstant time-- store O i én. 590 00:24:52,580 --> 00:24:54,720 Og helt ærligt, bare i den virkelige verden, det 591 00:24:54,720 --> 00:24:58,380 betyder indsættelse Daven navn tager ligesom fem trin, eller Davenport ni 592 00:24:58,380 --> 00:25:00,100 trin eller David fem trin. 593 00:25:00,100 --> 00:25:03,071 Det er temmelig darn små køretider. 594 00:25:03,071 --> 00:25:05,320 Og, ja, det er en meget god ting, især når 595 00:25:05,320 --> 00:25:08,126 det er ikke afhængig af den totale antallet af elementer i der. 596 00:25:08,126 --> 00:25:10,500 Så hvordan kan vi gennemfører dette form for struktur i koden? 597 00:25:10,500 --> 00:25:12,900 Det er lidt mere kompleks, men det er stadig 598 00:25:12,900 --> 00:25:15,050 blot en anvendelse af grundlæggende byggesten. 599 00:25:15,050 --> 00:25:17,830 Jeg har tænkt mig at omdefinere os node på følgende måde: 600 00:25:17,830 --> 00:25:21,100 bool kaldet word-- og dette kunne kaldes noget. 601 00:25:21,100 --> 00:25:23,970 Men bool repræsenterer hvad jeg tegnede som en markering. 602 00:25:23,970 --> 00:25:24,490 Ja. 603 00:25:24,490 --> 00:25:26,720 Dette er afslutningen af ​​en streng i denne datastruktur. 604 00:25:26,720 --> 00:25:30,702 >> Og naturligvis knudepunktet stjerne der henviser til børn. 605 00:25:30,702 --> 00:25:32,410 Og, ja, ligesom et stamtræ, du 606 00:25:32,410 --> 00:25:34,370 ville overveje knudepunkterne der hænger ud 607 00:25:34,370 --> 00:25:36,920 af bunden af ​​nogle forælder element til at være børn. 608 00:25:36,920 --> 00:25:40,510 Og så børnene kommer til at være en vifte af 27 den 27. ene 609 00:25:40,510 --> 00:25:41,680 bare at være for apostrof. 610 00:25:41,680 --> 00:25:43,390 Vi kommer til at sortere af særtilfælde det. 611 00:25:43,390 --> 00:25:45,400 Så du kan have en vis navne med apostrof. 612 00:25:45,400 --> 00:25:47,399 Måske endda bindestreg bør gå derind, men du vil 613 00:25:47,399 --> 00:25:50,330 se i p sæt 5 vi kun pleje om bogstaver og apostroffer. 614 00:25:50,330 --> 00:25:52,990 >> Og så hvordan gør du repræsenterer datastrukturen selv? 615 00:25:52,990 --> 00:25:56,454 Hvordan du repræsenterer roden af denne trie, så at sige? 616 00:25:56,454 --> 00:25:59,620 Nå, bare gerne med en linket liste, du brug for en pointer til det første element. 617 00:25:59,620 --> 00:26:04,270 Med en trie du bare har brug for en pointer til roden af ​​denne trie. 618 00:26:04,270 --> 00:26:07,290 Og derfra kan du hash din vej ned dybere og dybere 619 00:26:07,290 --> 00:26:10,460 til hver andet knudepunkt i strukturen. 620 00:26:10,460 --> 00:26:13,440 Så blot med denne dåse vi repræsenterer, at struct. 621 00:26:13,440 --> 00:26:15,877 >> Nu Meanwhile-- Åh, spørgsmål. 622 00:26:15,877 --> 00:26:17,220 >> PUBLIKUM: Hvad er bool ord? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool ord er netop dette C inkarnation 624 00:26:20,490 --> 00:26:22,920 af hvad jeg beskrev i denne ramme, når 625 00:26:22,920 --> 00:26:26,000 Jeg begyndte at opdele hver af de array-elementer i to stykker. 626 00:26:26,000 --> 00:26:27,600 Den ene er en pointer til den næste node. 627 00:26:27,600 --> 00:26:30,280 Den anden skal være noget som et afkrydsningsfelt 628 00:26:30,280 --> 00:26:33,770 til at sige ja, der er en Ordet Daven der ender her, 629 00:26:33,770 --> 00:26:35,610 fordi vi ikke ønsker, i øjeblikket, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Selvom Dave vil være en legitime ord, han er ikke i trie 631 00:26:39,320 --> 00:26:39,830 endnu. 632 00:26:39,830 --> 00:26:40,950 Og D er ikke et ord. 633 00:26:40,950 --> 00:26:42,770 Og D-A er ikke et ord eller et navn. 634 00:26:42,770 --> 00:26:45,020 Så markeringen angiver kun, når du 635 00:26:45,020 --> 00:26:48,190 ramt dette knudepunkt er tidligere sti tegn 636 00:26:48,190 --> 00:26:50,700 faktisk en streng, som du har indsat. 637 00:26:50,700 --> 00:26:53,660 Så det er alle de bool der gør for os. 638 00:26:53,660 --> 00:26:55,500 >> Alle andre spørgsmål om forsøg? 639 00:26:55,500 --> 00:26:56,215 Ja. 640 00:26:56,215 --> 00:26:58,035 >> PUBLIKUM: Hvad er overlap? 641 00:26:58,035 --> 00:26:59,945 Hvad hvis du har en Dave og en Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Hvad hvis du har en Dave og en Daven? 644 00:27:02,580 --> 00:27:06,240 Så hvis vi indsætter, siger et kaldenavn, for David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Dette er faktisk super enkel. 647 00:27:08,700 --> 00:27:10,325 Så vi kun kommer til at tage fire trin. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Og hvad skal jeg gøre, når jeg ramte det fjerde node? 650 00:27:15,847 --> 00:27:16,680 Bare for at kontrollere. 651 00:27:16,680 --> 00:27:18,000 Vi er allerede gode til at gå. 652 00:27:18,000 --> 00:27:18,840 Udført. 653 00:27:18,840 --> 00:27:19,750 Fire trin. 654 00:27:19,750 --> 00:27:21,590 Konstant tid asymptotisk. 655 00:27:21,590 --> 00:27:26,300 Og nu har vi angivet, at både Dave og Daven er strenge i strukturen. 656 00:27:26,300 --> 00:27:27,710 Så ikke et problem. 657 00:27:27,710 --> 00:27:30,200 Og bemærk, hvordan tilstedeværelsen af Daven ikke gøre det 658 00:27:30,200 --> 00:27:34,750 tage noget mere tid eller mindre tid for Dave og vice versa. 659 00:27:34,750 --> 00:27:36,000 >> Så hvad andet kan vi nu gøre? 660 00:27:36,000 --> 00:27:40,680 Vi har brugt denne metafor før bakker repræsenterer noget. 661 00:27:40,680 --> 00:27:43,380 Men det viser sig, at en stablen af ​​bakker er faktisk 662 00:27:43,380 --> 00:27:47,187 demonstrative af en anden abstrakt data Motortype- et højere niveau datastruktur 663 00:27:47,187 --> 00:27:49,770 at der ved udgangen af ​​dagen er bare som en matrix eller en sammenkædet liste 664 00:27:49,770 --> 00:27:50,970 eller noget mere prosaisk. 665 00:27:50,970 --> 00:27:53,270 Men det er en mere interessant konceptuelle koncept. 666 00:27:53,270 --> 00:27:56,440 En stak, som disse bakker her i Mather, 667 00:27:56,440 --> 00:27:58,750 kaldes generelt bare at-- en stak. 668 00:27:58,750 --> 00:28:02,540 >> Og i denne type datastruktur du har to operations-- 669 00:28:02,540 --> 00:28:05,880 du har en kaldet fremstød for tilføje noget til stakken, 670 00:28:05,880 --> 00:28:08,320 som at sætte en anden bakke tilbage på toppen af ​​stakken. 671 00:28:08,320 --> 00:28:11,350 Og derefter pop, hvilket betyder, at du tage den øverste bakke off. 672 00:28:11,350 --> 00:28:16,210 Men hvad er nøglen omkring en stak, er, at det har fået denne besynderlige egenskab. 673 00:28:16,210 --> 00:28:19,560 Som den spisesal personale er omarrangere bakker til det næste måltid, 674 00:28:19,560 --> 00:28:21,380 hvad der kommer til at være sandt om, hvordan de studerende 675 00:28:21,380 --> 00:28:22,856 interagere med denne datastruktur? 676 00:28:22,856 --> 00:28:24,480 PUBLIKUM: De kommer til at poppe en off. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: De kommer til at poppe en off, forhåbentlig toppen. 678 00:28:26,550 --> 00:28:28,910 Ellers er det bare lidt dum at gå hele vejen til bunden. 679 00:28:28,910 --> 00:28:29,070 Right? 680 00:28:29,070 --> 00:28:31,620 Datastrukturen ikke rigtig tillade dig at få fat den nederste bakke i det mindste 681 00:28:31,620 --> 00:28:32,520 let. 682 00:28:32,520 --> 00:28:35,040 Så der er denne besynderlige ejendom til en stak 683 00:28:35,040 --> 00:28:39,730 at det sidste element i er vil være den første ud. 684 00:28:39,730 --> 00:28:43,400 Og dataloger kalder dette LIFO-- vare ind, først ud. 685 00:28:43,400 --> 00:28:45,540 Og det faktisk har interessante anvendelser. 686 00:28:45,540 --> 00:28:50,090 Det er ikke nødvendigvis så indlysende, som nogle andre, men det kan faktisk være nyttigt, 687 00:28:50,090 --> 00:28:54,040 og det kan faktisk implementeres i et par forskellige måder. 688 00:28:54,040 --> 00:28:58,550 >> Så en, og faktisk, lad mig ikke at dykke ned i det. 689 00:28:58,550 --> 00:28:59,860 Lad os gøre det i stedet. 690 00:28:59,860 --> 00:29:03,700 Lad os se på en, der er næsten samme idé, men det er lidt mere retfærdig. 691 00:29:03,700 --> 00:29:04,200 Right? 692 00:29:04,200 --> 00:29:07,560 Hvis du er en af ​​disse fan drenge eller piger, der virkelig kan lide Apples produkter 693 00:29:07,560 --> 00:29:10,130 og du vågnede op på 3:00 at line op på nogle butik 694 00:29:10,130 --> 00:29:14,150 at få det nyeste iPhone, du kunne have kø som denne. 695 00:29:14,150 --> 00:29:15,800 >> Nu er en kø er meget bevidst navngivet. 696 00:29:15,800 --> 00:29:18,190 Det er en linje, fordi der er nogle retfærdighed til det. 697 00:29:18,190 --> 00:29:18,690 Right? 698 00:29:18,690 --> 00:29:21,690 Det ville suges slags, hvis du har fik der først på Apple Store 699 00:29:21,690 --> 00:29:25,700 men du er faktisk det nederste bakke, fordi Apple ansatte derefter 700 00:29:25,700 --> 00:29:28,189 pop den sidste person, der faktisk fik i linje. 701 00:29:28,189 --> 00:29:31,230 Så stakke og køer, selv om der funktionelt de er slags af same-- 702 00:29:31,230 --> 00:29:33,105 det er bare denne samling af ressourcer, som er 703 00:29:33,105 --> 00:29:36,210 kommer til at vokse og shrink-- der er denne fairness aspekt til det, 704 00:29:36,210 --> 00:29:39,634 i det mindste i den virkelige verden, hvor operationerne du motionerer 705 00:29:39,634 --> 00:29:40,800 er fundamentalt forskellige. 706 00:29:40,800 --> 00:29:43,360 En stack-- en kø rather-- siges at have 707 00:29:43,360 --> 00:29:45,320 to operationer: n kø og d kø. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Eller du kan ringe til dem en række ting. 710 00:29:48,090 --> 00:29:50,770 Men du blot ønsker at fange det begreb, at man tilføjer 711 00:29:50,770 --> 00:29:53,230 og man er i sidste ende at subtrahere. 712 00:29:53,230 --> 00:29:58,840 >> Nu under hætten, både stakken og en kø kan gennemføres hvordan? 713 00:29:58,840 --> 00:30:01,390 Vi vil ikke gå ind i koden for det, fordi det højere niveau 714 00:30:01,390 --> 00:30:03,387 Ideen er slags mere indlysende. 715 00:30:03,387 --> 00:30:04,470 Jeg mener, hvad gør mennesker gør? 716 00:30:04,470 --> 00:30:07,030 Hvis jeg er den første person på Apple Opbevar og det er hoveddøren, 717 00:30:07,030 --> 00:30:08,130 du ved, jeg har tænkt mig at stå her. 718 00:30:08,130 --> 00:30:09,750 Og den næste person kommer til at stå her. 719 00:30:09,750 --> 00:30:11,500 Og den næste person kommer til at stå her. 720 00:30:11,500 --> 00:30:13,792 Så hvad datastruktur egner sig til en kø? 721 00:30:13,792 --> 00:30:14,542 >> PUBLIKUM: En kø. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Tja, en kø. 723 00:30:15,667 --> 00:30:16,390 Sure. 724 00:30:16,390 --> 00:30:16,920 Hvad ellers? 725 00:30:16,920 --> 00:30:17,600 >> PUBLIKUM: En linkede liste. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: Et sammenkædet liste, du kunne gennemføre. 727 00:30:18,990 --> 00:30:22,500 Og en linket liste er rart, fordi så det kan vokse vilkårligt længe i modsætning 728 00:30:22,500 --> 00:30:24,880 at have nogle fast antal af mennesker i butikken. 729 00:30:24,880 --> 00:30:27,030 Men måske et fast antal steder er legitim. 730 00:30:27,030 --> 00:30:30,350 Fordi hvis de kun har ligesom 20 Iphones på den første dag, måske 731 00:30:30,350 --> 00:30:33,930 de kun behøver en vifte af størrelse 20 til at repræsentere den kø, som 732 00:30:33,930 --> 00:30:37,070 er kun at sige nu, når vi begynder at tale om disse problemer højere niveau, 733 00:30:37,070 --> 00:30:38,890 du kan gennemføre det i en række forskellige måder. 734 00:30:38,890 --> 00:30:42,030 Og der er nok bare at gå til være en afvejning i tid og rum 735 00:30:42,030 --> 00:30:43,950 eller bare i din egen kode kompleksitet. 736 00:30:43,950 --> 00:30:45,380 >> Hvad med en stak? 737 00:30:45,380 --> 00:30:48,190 Tja, en stak, har vi set alt for kunne bare være disse bakker. 738 00:30:48,190 --> 00:30:50,007 Og man kunne gennemføre denne et array. 739 00:30:50,007 --> 00:30:53,090 Men på et tidspunkt, hvis du bruger et array, hvad der vil ske med bakkerne 740 00:30:53,090 --> 00:30:54,173 du forsøger at lægge ned? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Ok. 743 00:30:55,670 --> 00:30:57,490 Du vil kun være i stand til at gå så højt. 744 00:30:57,490 --> 00:31:00,156 Og jeg tror i Mather, de er faktisk forsænket i denne åbning. 745 00:31:00,156 --> 00:31:01,950 Så ja, det er næsten ligesom Mather bruger 746 00:31:01,950 --> 00:31:03,783 en matrix af fast størrelse, fordi du kun kan 747 00:31:03,783 --> 00:31:08,302 passer så mange bakker i, at åbningen i muren ned under folks knæ. 748 00:31:08,302 --> 00:31:10,010 Og så der kan være siges at være et array, 749 00:31:10,010 --> 00:31:14,300 men vi kunne sikkert gennemføre denne mere generelt med en linket liste. 750 00:31:14,300 --> 00:31:16,390 >> Nå, hvad en anden datastruktur? 751 00:31:16,390 --> 00:31:18,760 Lad mig trække op en anden visuel her. 752 00:31:18,760 --> 00:31:24,710 Noget som hvordan omkring denne ene her? 753 00:31:24,710 --> 00:31:28,920 Hvorfor kan det være nyttigt at have ikke noget så fancy som en trie, som 754 00:31:28,920 --> 00:31:32,370 vi så haft disse meget brede knudepunkter, som hver er i en array? 755 00:31:32,370 --> 00:31:35,740 Men hvad nu, hvis vi gør noget mere simpelthen, som en gammel skole stamtræ, 756 00:31:35,740 --> 00:31:38,110 hver af hvis knudepunkter her blot lagre et nummer. 757 00:31:38,110 --> 00:31:42,180 I stedet for et navn eller en efterkommer er bare at lagre et nummer som dette. 758 00:31:42,180 --> 00:31:45,250 >> Nå, den jargon, vi bruger i datastrukturer er begge forsøg 759 00:31:45,250 --> 00:31:49,510 og træer, hvor en trie igen, er blot én, hvis knudepunkter er arrays, 760 00:31:49,510 --> 00:31:51,680 er stadig, hvad man kunne bruge fra folkeskolen 761 00:31:51,680 --> 00:31:53,860 når du har lavet en familie tree-- blade og roden 762 00:31:53,860 --> 00:31:57,250 af træet og børn af forælder og søskende deraf. 763 00:31:57,250 --> 00:32:03,670 Og vi kan gennemføre et træ, for eksempel så enkelt som dette. 764 00:32:03,670 --> 00:32:07,420 Et træ, hvis det som et knudepunkt, en af disse kredse, der har et nummer 765 00:32:07,420 --> 00:32:09,947 det kommer ikke til at have en pointer, men to. 766 00:32:09,947 --> 00:32:11,780 Og så snart du tilføjer en anden pointer, du 767 00:32:11,780 --> 00:32:13,905 kan faktisk nu gøre slags af to-dimensionelle data 768 00:32:13,905 --> 00:32:14,780 strukturer i hukommelsen. 769 00:32:14,780 --> 00:32:16,660 Ligesom en todimensional array, kan du 770 00:32:16,660 --> 00:32:18,904 har form af to-dimensionelle hægtede lister, men dem 771 00:32:18,904 --> 00:32:20,820 at følge et mønster hvor der er ingen cykler. 772 00:32:20,820 --> 00:32:24,487 Det er virkelig et træ med en bedsteforælder vej op her og derefter 773 00:32:24,487 --> 00:32:27,320 nogle forældre og børn, og børnebørn og oldebørn. 774 00:32:27,320 --> 00:32:28,370 og så videre. 775 00:32:28,370 --> 00:32:32,390 >> Men hvad er virkelig sirlige om dette også, bare for at drille dig en smule kode med, 776 00:32:32,390 --> 00:32:35,370 tilbagekaldelse rekursion fra et stykke tid tilbage, hvorved 777 00:32:35,370 --> 00:32:38,220 du skriver en funktion, der kalder sig selv. 778 00:32:38,220 --> 00:32:41,140 Dette er en smuk lejlighed at implementere noget 779 00:32:41,140 --> 00:32:42,920 ligesom rekursion, fordi overveje dette. 780 00:32:42,920 --> 00:32:43,860 >> Dette er et træ. 781 00:32:43,860 --> 00:32:48,040 Og jeg har været lidt anal med hvordan Jeg sætter heltal på gaden. 782 00:32:48,040 --> 00:32:51,020 Så meget, at det har en særlig name-- en binær søgning træ. 783 00:32:51,020 --> 00:32:53,460 Nu har vi hørt om binær at søge, men kan du 784 00:32:53,460 --> 00:32:55,180 arbejde baglæns fra denne ting navn? 785 00:32:55,180 --> 00:32:59,280 Hvad er det mønster af, hvordan jeg indsættes heltal i dette træ? 786 00:32:59,280 --> 00:33:00,696 Det er ikke vilkårlig. 787 00:33:00,696 --> 00:33:01,570 Der er nogle mønster. 788 00:33:01,570 --> 00:33:02,090 Ja. 789 00:33:02,090 --> 00:33:03,370 >> PUBLIKUM: Mindre dem til venstre. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Ja. 791 00:33:03,690 --> 00:33:05,062 Mindre er på venstre. 792 00:33:05,062 --> 00:33:06,270 Større virksomheder er på rette. 793 00:33:06,270 --> 00:33:12,940 Sådan at en sand erklæring er en forælder er større end dens venstre barn, 794 00:33:12,940 --> 00:33:14,850 men mindre end dens højre barn. 795 00:33:14,850 --> 00:33:17,750 Og det alene er endda en rekursive verbal definition 796 00:33:17,750 --> 00:33:20,500 fordi du kan anvende denne samme logik til hver node 797 00:33:20,500 --> 00:33:23,080 og det kun bunde ud, en base tilfældet, hvis du 798 00:33:23,080 --> 00:33:25,740 vil, når du rammer en af bladene, så at sige, 799 00:33:25,740 --> 00:33:28,580 hvor en orlov har ingen børn yderligere. 800 00:33:28,580 --> 00:33:30,614 >> Nu, hvordan kan du finde nummeret 44? 801 00:33:30,614 --> 00:33:32,280 Du ville starte ved roden og sige, hm. 802 00:33:32,280 --> 00:33:35,690 55 er ikke 44 Så gør jeg ønsker at gå ret eller skal jeg ønsker at gå tilbage? 803 00:33:35,690 --> 00:33:37,190 Nå, selvfølgelig, du ønsker at gå til venstre. 804 00:33:37,190 --> 00:33:40,060 Og så er det bare ligesom telefonen Bogen eksempel i binær søgning 805 00:33:40,060 --> 00:33:41,099 mere generelt. 806 00:33:41,099 --> 00:33:43,390 Men vi gennemføre den nu lidt mere dynamisk 807 00:33:43,390 --> 00:33:45,339 end et array kunne give. 808 00:33:45,339 --> 00:33:48,130 Og i virkeligheden, hvis du ønsker at se på den kode, ved første øjekast sikker. 809 00:33:48,130 --> 00:33:49,671 Det ligner en hel masse linjer. 810 00:33:49,671 --> 00:33:51,220 Men det er smukt enkle. 811 00:33:51,220 --> 00:33:54,490 Hvis du ønsker at gennemføre en funktion kaldet søgning hvis formål i livet 812 00:33:54,490 --> 00:33:57,290 er at søge efter en værdi ligesom n, et helt tal, 813 00:33:57,290 --> 00:34:01,756 og du er gået i en en pointer-- en pointer til knudepunktet af rødder, 814 00:34:01,756 --> 00:34:04,380 snarere af det træ, hvorfra du kan få adgang til alt det andet, 815 00:34:04,380 --> 00:34:08,850 mærke til, hvor ligefremt du kan gennemføre logikken. 816 00:34:08,850 --> 00:34:10,880 Hvis træet er null, selvfølgelig er det ikke der. 817 00:34:10,880 --> 00:34:11,880 Lad os bare return false. 818 00:34:11,880 --> 00:34:12,000 Right? 819 00:34:12,000 --> 00:34:14,040 Hvis du aflevere det ingenting, der er ikke noget der. 820 00:34:14,040 --> 00:34:17,900 >> Else, hvis n er mindre end træ pil n- nu arrow n, 821 00:34:17,900 --> 00:34:20,670 husker vi indførte super kort den anden dag, 822 00:34:20,670 --> 00:34:25,100 og det betyder bare de-reference pointer og se på det område, der kaldes n. 823 00:34:25,100 --> 00:34:27,690 Så betyder det, gå der og se felt, der kaldes n. 824 00:34:27,690 --> 00:34:33,810 Så hvis n, den værdi, du er givet, er mindre end værdien i træerne heltal, 825 00:34:33,810 --> 00:34:35,449 Hvor vil du hen? 826 00:34:35,449 --> 00:34:36,389 Til venstre. 827 00:34:36,389 --> 00:34:37,780 >> Så mærke rekursionen. 828 00:34:37,780 --> 00:34:39,860 Jeg returning-- ikke sandt. 829 00:34:39,860 --> 00:34:40,989 Ikke falsk. 830 00:34:40,989 --> 00:34:45,670 Jeg tilbage uanset svaret er fra et kald til mig selv, der passerer 831 00:34:45,670 --> 00:34:50,100 en n igen, hvilket er overflødig men hvad er lidt anderledes nu? 832 00:34:50,100 --> 00:34:51,989 Hvordan skal jeg gøre problemet mindre? 833 00:34:51,989 --> 00:34:54,920 Jeg passerer ind som den anden argument, ikke roden af ​​træet, 834 00:34:54,920 --> 00:34:59,616 men den venstre barn i dette tilfælde. 835 00:34:59,616 --> 00:35:00,990 Så jeg passerer i venstre barn. 836 00:35:00,990 --> 00:35:04,720 >> I mellemtiden, hvis n er større end node Jeg er i øjeblikket kigger på, 837 00:35:04,720 --> 00:35:06,690 Jeg søger den højre side. 838 00:35:06,690 --> 00:35:10,880 Else, hvis træet ikke er nul, og Hvis elementet ikke er til venstre 839 00:35:10,880 --> 00:35:13,240 og det er ikke til højre, hvad er vidunderligt tilfældet? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Vi har faktisk fundet node i spørgsmål, og så vender vi tilbage sandt. 842 00:35:18,440 --> 00:35:21,490 >> Så vi har lige kradset i overfladen nu nogle af disse datastrukturer. 843 00:35:21,490 --> 00:35:24,370 I problem sæt fem du vil udforske disse endnu videre, 844 00:35:24,370 --> 00:35:27,250 og du vil blive givet dit design valg af, hvordan man kan gå om dette. 845 00:35:27,250 --> 00:35:30,250 Hvad jeg gerne vil slutte på er bare en 30 sekunders teaser 846 00:35:30,250 --> 00:35:32,080 af, hvad der venter i næste uge og videre. 847 00:35:32,080 --> 00:35:35,390 >> Som vi begin-- heldigvis du måske tror-- langsomt vores overgang 848 00:35:35,390 --> 00:35:38,680 fra en verden af ​​C og lavere implementering niveau detaljer, 849 00:35:38,680 --> 00:35:42,090 til en verden, hvor vi kan tage for givet, at en anden har endelig 850 00:35:42,090 --> 00:35:44,010 gennemført disse data strukturer for os, 851 00:35:44,010 --> 00:35:47,570 og vi vil begynde at forstå virkelige verden betyder, at gennemføre 852 00:35:47,570 --> 00:35:50,560 web-baserede programmer, og websites mere generelt 853 00:35:50,560 --> 00:35:52,910 og også meget sikkerhed konsekvenser, vi har kun 854 00:35:52,910 --> 00:35:54,850 begyndt at ridse overfladen på. 855 00:35:54,850 --> 00:35:57,320 Her er hvad der venter os i de kommende dage. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PLAYBACK] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Han Kom med et budskab, med en protokol alle hans egen. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Han kom til en verden af ​​grusom firewalls, ufølsom routere, 861 00:36:30,894 --> 00:36:33,368 og farer langt værre end døden. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Han er hurtig. 864 00:36:36,236 --> 00:36:37,980 Han er stærk. 865 00:36:37,980 --> 00:36:42,830 Han er TCP / IP, og han har fået din adresse. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors den i nettet." 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Kommer i næste uge. 870 00:36:50,910 --> 00:36:51,880 Vi vil se dig derefter. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO PLAYBACK] 873 00:36:56,060 --> 00:36:59,240 -Og Nu, "dybe tanker" af Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Starter altid forelæsninger med "All right." 876 00:37:05,820 --> 00:37:08,750 Hvorfor ikke: "Her er løsningen til denne uges problem sæt " 877 00:37:08,750 --> 00:37:12,180 eller "Vi giver jer alle et A?" 878 00:37:12,180 --> 00:37:13,380 [LAUGHING] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO PLAYBACK]