1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Okay, så vi er tilbage. 3 00:00:13,120 --> 00:00:14,480 Velkommen til CS50. 4 00:00:14,480 --> 00:00:16,510 Dette er slutningen af ​​uge syv. 5 00:00:16,510 --> 00:00:20,200 Så minde om, at sidste gang, vi startede ser på lidt mere sofistikerede 6 00:00:20,200 --> 00:00:21,100 datastrukturer. 7 00:00:21,100 --> 00:00:25,110 Siden indtil nu, havde vi alle virkelig til vores rådighed var dette et array. 8 00:00:25,110 --> 00:00:29,340 >> Men før vi kassere array som ikke alt det spændende, som ganske rigtigt er det 9 00:00:29,340 --> 00:00:33,570 faktisk, hvad er nogle af de plusser denne enkle data 10 00:00:33,570 --> 00:00:34,560 struktur hidtil? 11 00:00:34,560 --> 00:00:36,110 Hvad er det god til? 12 00:00:36,110 --> 00:00:39,450 Så vidt vi har set? 13 00:00:39,450 --> 00:00:42,540 Hvad har du? 14 00:00:42,540 --> 00:00:44,028 Nothing. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [uhørlig]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Hvad er det? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [uhørlig]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1: Fast størrelse. 19 00:00:47,000 --> 00:00:51,260 OK, så hvorfor er fast størrelse godt selv? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [uhørlig]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, så det er effektivt den forstand, at du kan tildele en 22 00:00:56,240 --> 00:01:00,070 fast mængde plads, som forhåbentlig er netop så meget 23 00:01:00,070 --> 00:01:01,180 rummet som du ønsker. 24 00:01:01,180 --> 00:01:02,720 Så der kunne være absolut et plus. 25 00:01:02,720 --> 00:01:06,530 >> Hvad er en anden op side i et array? 26 00:01:06,530 --> 00:01:07,610 Ja? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [uhørlig]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: Alle - undskyld? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [uhørlig]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Alle kasserne i hukommelsen eller ved siden af ​​hinanden. 31 00:01:13,620 --> 00:01:15,220 Og det er nyttigt - hvorfor? 32 00:01:15,220 --> 00:01:15,970 Det er helt rigtigt. 33 00:01:15,970 --> 00:01:18,611 Men hvordan kan vi udnytte denne sandhed? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [uhørlig]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Præcis, vi kan holde styr på hvor alt er bare ved at vide 36 00:01:24,490 --> 00:01:28,560 én adresse, nemlig adresse første byte af denne luns af hukommelse. 37 00:01:28,560 --> 00:01:30,420 Eller i tilfælde af strengen, adressen på den første 38 00:01:30,420 --> 00:01:31,460 char i denne streng. 39 00:01:31,460 --> 00:01:33,330 Og derfra kan vi finde enden af ​​strengen. 40 00:01:33,330 --> 00:01:35,710 Vi kan finde det andet element, de tredje element, og så videre. 41 00:01:35,710 --> 00:01:38,740 >> Og så fancy måde at beskrive, at funktion er at arrays giver os 42 00:01:38,740 --> 00:01:40,020 random access. 43 00:01:40,020 --> 00:01:44,330 Blot ved hjælp af den firkantede beslag notation og et nummer, kan du springe til 44 00:01:44,330 --> 00:01:48,070 et specifikt element i array i konstant tid, store O 45 00:01:48,070 --> 00:01:49,810 af en, så at sige. 46 00:01:49,810 --> 00:01:51,080 >> Men der har været nogle ulemper. 47 00:01:51,080 --> 00:01:53,110 Hvad et array ikke meget nemt? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Hvad er det ikke god til? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [uhørlig]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Hvad er det? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [uhørlig]. 53 00:02:00,530 --> 00:02:01,460 >> SPEAKER 1: Udvidelse i størrelse. 54 00:02:01,460 --> 00:02:04,800 Så de ulemper array er præcis det modsatte af, hvad 55 00:02:04,800 --> 00:02:05,540 upsides er. 56 00:02:05,540 --> 00:02:07,610 Så en af ​​de ulemper er at det er en fast størrelse. 57 00:02:07,610 --> 00:02:09,400 Så du kan ikke rigtig dyrke det. 58 00:02:09,400 --> 00:02:13,510 Du kan omfordele en større bid af hukommelse, og derefter flytte de gamle elementer 59 00:02:13,510 --> 00:02:14,460 i det nye array. 60 00:02:14,460 --> 00:02:18,060 Og derefter fri den gamle matrix, for eksempelvis ved hjælp af malloc eller en lignende 61 00:02:18,060 --> 00:02:21,180 funktion kaldet realloc, som omfordeler hukommelse. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, som en sidebemærkning, forsøger at give dig hukommelse, der er ved siden af ​​matrix 63 00:02:25,490 --> 00:02:26,610 at du allerede har. 64 00:02:26,610 --> 00:02:28,740 Men det kan flytte ting omkring helt. 65 00:02:28,740 --> 00:02:30,710 Men kort sagt, er det dyrt, right? 66 00:02:30,710 --> 00:02:33,440 Fordi hvis du har en luns af hukommelse denne størrelse, men du virkelig vil have en 67 00:02:33,440 --> 00:02:36,710 af denne størrelse, og du ønsker at bevare de oprindelige elementer, du har 68 00:02:36,710 --> 00:02:40,510 omkring en lineær tid kopieringen der skal ske fra 69 00:02:40,510 --> 00:02:41,900 gamle array til nye. 70 00:02:41,900 --> 00:02:44,630 Og virkeligheden beder operativsystemet systemet igen og igen og 71 00:02:44,630 --> 00:02:48,340 igen for store bidder af hukommelsen kan begynde til at koste dig lidt tid så godt. 72 00:02:48,340 --> 00:02:52,250 Så det er både en velsignelse og en forbandelse i skjule den kendsgerning, at disse arrays 73 00:02:52,250 --> 00:02:53,860 er af fast størrelse. 74 00:02:53,860 --> 00:02:56,790 Men hvis vi indfører i stedet noget som dette, vi som opfordrede en sammenkædet 75 00:02:56,790 --> 00:03:00,580 liste, vi får et par upsides og et par ulemper her. 76 00:03:00,580 --> 00:03:05,780 >> Så en linket liste er simpelthen en data struktur af C structs i dette 77 00:03:05,780 --> 00:03:09,850 sagen, hvor en struct, tilbagekaldelse, er bare en beholder til en eller flere specifikke 78 00:03:09,850 --> 00:03:11,100 typer af variabler. 79 00:03:11,100 --> 00:03:16,110 I dette tilfælde gør, hvad de datatyper synes at være inde i struct der 80 00:03:16,110 --> 00:03:17,600 sidste gang vi kaldes en knude? 81 00:03:17,600 --> 00:03:19,380 Hver af disse rektangler er et knudepunkt. 82 00:03:19,380 --> 00:03:22,660 Og hver af de mindre rektangler inde i det er en datatype. 83 00:03:22,660 --> 00:03:25,300 Hvilke typer gjorde vi siger de var på mandag? 84 00:03:25,300 --> 00:03:26,478 Ja? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [uhørlig]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: En variabel og en pegepind, eller mere specifikt, en int, for n, 87 00:03:30,721 --> 00:03:32,180 og en pointer i bunden. 88 00:03:32,180 --> 00:03:35,360 Begge af dem tilfældigvis være 32 bit, på mindst på en computer som denne CS50 89 00:03:35,360 --> 00:03:37,980 Apparat, og så de er trukket lige i størrelse. 90 00:03:37,980 --> 00:03:42,260 >> Så hvad bruger markøren selvom for tilsyneladende? 91 00:03:42,260 --> 00:03:47,690 Hvorfor tilføje denne pil nu, hvor arrays var så nice og ren og enkel? 92 00:03:47,690 --> 00:03:50,460 Hvad markøren gør for os i hver af disse knudepunkter? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [uhørlig]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Præcis. 95 00:03:52,465 --> 00:03:54,120 Det fortæller dig, hvor det næste er. 96 00:03:54,120 --> 00:03:57,350 Så jeg slags bruger analogien ved hjælp af en tråd for at sortere i 97 00:03:57,350 --> 00:03:59,180 tråd disse knudepunkter sammen. 98 00:03:59,180 --> 00:04:01,760 Og det er præcis, hvad vi gør med pointere fordi hver af disse 99 00:04:01,760 --> 00:04:06,360 bidder af hukommelsen kan eller ikke kan være sammenhængende, tilbage til tilbage til tilbage 100 00:04:06,360 --> 00:04:09,500 indersiden af ​​RAM, fordi hver gang du kalder malloc siger, giv mig nok 101 00:04:09,500 --> 00:04:12,510 bytes til en ny node, kan det blive være her, eller det kan være her. 102 00:04:12,510 --> 00:04:13,120 Det kunne være her. 103 00:04:13,120 --> 00:04:13,730 Det kunne være her. 104 00:04:13,730 --> 00:04:14,640 Du skal bare ikke kender. 105 00:04:14,640 --> 00:04:17,880 >> Men at bruge pointere i adresserne på disse knudepunkter, kan du sy dem 106 00:04:17,880 --> 00:04:22,370 sammen på en måde, der ser visuelt ligesom en liste selv om disse ting er 107 00:04:22,370 --> 00:04:26,770 alle spredt ud i hele din en eller dine to eller dine fire gigabyte RAM 108 00:04:26,770 --> 00:04:28,760 indersiden af ​​din egen computer. 109 00:04:28,760 --> 00:04:33,230 >> Så negativsiden så med en linket liste er hvad? 110 00:04:33,230 --> 00:04:34,670 Hvad er en pris, vi er tilsyneladende betale? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [uhørlig]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Mere plads, right? 113 00:04:36,920 --> 00:04:39,340 Vi har i dette tilfælde, fordoblet af plads, fordi vi har gået 114 00:04:39,340 --> 00:04:43,500 fra 32 bits for hver node, for hver int, så nu 64 bit, fordi vi er nødt til at 115 00:04:43,500 --> 00:04:45,050 holde omkring en pointer så godt. 116 00:04:45,050 --> 00:04:48,860 Du får mere effektivitet, hvis din struct er større end dette simple ting. 117 00:04:48,860 --> 00:04:52,020 Hvis du rent faktisk har en studerende inde hvoraf er et par strenge for 118 00:04:52,020 --> 00:04:55,430 navn og hus, måske et id-nummer, måske nogle andre områder helt. 119 00:04:55,430 --> 00:04:59,000 >> Så hvis du har en stor nok struct, så måske prisen på pointer er 120 00:04:59,000 --> 00:05:00,010 ikke sådan en big deal. 121 00:05:00,010 --> 00:05:03,570 Det er lidt af et hjørne tilfældet i det vi opbevare sådan en simpel primitiv 122 00:05:03,570 --> 00:05:04,760 indersiden af ​​linkede liste. 123 00:05:04,760 --> 00:05:05,790 Men pointen er den samme. 124 00:05:05,790 --> 00:05:08,230 Du absolut bruge mere hukommelse, men du får 125 00:05:08,230 --> 00:05:08,990 fleksibilitet. 126 00:05:08,990 --> 00:05:12,280 Fordi nu, hvis jeg ønsker at tilføje et element i begyndelsen af ​​denne liste, 127 00:05:12,280 --> 00:05:14,340 Jeg er nødt til at afsætte en ny node. 128 00:05:14,340 --> 00:05:17,180 Og jeg er nødt til bare opdatere dem pile eller anden måde ved blot at flytte 129 00:05:17,180 --> 00:05:17,980 nogle pejlemærker omkring. 130 00:05:17,980 --> 00:05:20,580 >> Hvis jeg ønsker at indsætte noget i midten af ​​listen, behøver jeg ikke at 131 00:05:20,580 --> 00:05:24,410 skubbe alle bort, ligesom vi gjorde i ugers fortid med vores frivillige, der 132 00:05:24,410 --> 00:05:25,700 repræsenterede et array. 133 00:05:25,700 --> 00:05:29,470 Jeg kan bare tildele en ny node og så bare pege pilene i 134 00:05:29,470 --> 00:05:32,290 forskellige retninger, fordi det ikke nødt til at forblive i den faktiske 135 00:05:32,290 --> 00:05:35,670 hukommelse et sandt linje som jeg har tegnet det her på skærmen. 136 00:05:35,670 --> 00:05:38,400 >> Og så endelig, hvis du ønsker at indsætte noget i slutningen af ​​listen, er det 137 00:05:38,400 --> 00:05:39,210 endnu nemmere. 138 00:05:39,210 --> 00:05:43,320 Dette er en slags vilkårlig notation, men 34 er pointer, tage et gæt. 139 00:05:43,320 --> 00:05:46,710 Hvad er værdien af ​​sin pointer mest sandsynligvis trukket lidt ligesom en gammel 140 00:05:46,710 --> 00:05:47,700 skole antenne der? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [uhørlig]. 142 00:05:48,920 --> 00:05:49,900 >> SPEAKER 1: Det er nok null. 143 00:05:49,900 --> 00:05:52,710 Og faktisk det er en forfatters repræsentation af null. 144 00:05:52,710 --> 00:05:56,310 Og det er null, fordi du absolut brug for at vide, hvor enden af ​​en sammenkædet 145 00:05:56,310 --> 00:06:00,050 Listen er, lest du holder følgende, og følge og følge disse pile 146 00:06:00,050 --> 00:06:01,170 til nogle skrald værdi. 147 00:06:01,170 --> 00:06:06,230 Så null vil betyde, at der ikke er nogen flere knuder til højre for nummer 34, 148 00:06:06,230 --> 00:06:07,200 i dette tilfælde. 149 00:06:07,200 --> 00:06:10,270 >> Så vi foreslår, at vi kan gennemføre denne node i koden. 150 00:06:10,270 --> 00:06:12,130 Og vi har set den slags syntaks før. 151 00:06:12,130 --> 00:06:15,090 Typedef bare definerer en ny type for os, giver os et synonym som 152 00:06:15,090 --> 00:06:17,100 string var for char *. 153 00:06:17,100 --> 00:06:21,030 I dette tilfælde er det kommer til at give os stenografi notation så struct node 154 00:06:21,030 --> 00:06:24,010 kan i stedet bare skrives som knude, som er en meget renere. 155 00:06:24,010 --> 00:06:25,360 Det er en masse mindre verdslige. 156 00:06:25,360 --> 00:06:30,080 >> Inde i et knudepunkt er tilsyneladende en int kaldet n, og derefter en struct node * 157 00:06:30,080 --> 00:06:34,670 hvilket betyder præcis, hvad vi ønskede pilene til at betyde, en pointer til en anden 158 00:06:34,670 --> 00:06:36,940 node af nøjagtig samme datatype. 159 00:06:36,940 --> 00:06:40,300 Og jeg foreslår, at vi kunne gennemføre en søgefunktionen som dette, som på 160 00:06:40,300 --> 00:06:41,890 første øjekast kan virke en lille kompleks. 161 00:06:41,890 --> 00:06:43,330 Men lad os se det i sammenhæng. 162 00:06:43,330 --> 00:06:45,480 >> Lad mig gå over til apparatet her. 163 00:06:45,480 --> 00:06:48,460 Lad mig åbne en fil kaldet liste nul prik timer. 164 00:06:48,460 --> 00:06:53,950 Og at det kun indeholder definitionen vi lige set et øjeblik siden for disse data 165 00:06:53,950 --> 00:06:55,390 typen kaldet en knude. 166 00:06:55,390 --> 00:06:57,350 Så vi har lagt det ind i en prik h-fil. 167 00:06:57,350 --> 00:07:01,430 >> Og som en sidebemærkning, selv om dette program, du er ved at se, er 168 00:07:01,430 --> 00:07:05,410 ikke alle, der kompliceret, det er faktisk konvention, når du skriver et program til 169 00:07:05,410 --> 00:07:10,270 sætte ting som datatyper, til at trække konstanter sommetider inde i dit 170 00:07:10,270 --> 00:07:13,210 header fil og ikke nødvendigvis i dit C-fil, i hvert fald når din 171 00:07:13,210 --> 00:07:17,370 programmer får større og større, således at du ved hvor de skal lede både for 172 00:07:17,370 --> 00:07:20,840 dokumentation i nogle tilfælde, eller for basics som denne, de 173 00:07:20,840 --> 00:07:22,360 definition af nogle type. 174 00:07:22,360 --> 00:07:25,680 >> Hvis jeg nu åbne liste zero dot c bemærke et par ting. 175 00:07:25,680 --> 00:07:29,090 Den indeholder nogle få header-filer, de fleste som vi har set før. 176 00:07:29,090 --> 00:07:31,980 Det omfatter sin egen header fil. 177 00:07:31,980 --> 00:07:35,200 >> Og som en sidebemærkning, hvorfor der er dobbelt citater her, i modsætning til den vinkel 178 00:07:35,200 --> 00:07:38,340 beslag på den linje, der Jeg har fremhævet der? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [uhørlig]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Ja, så det er en lokal fil. 181 00:07:40,460 --> 00:07:44,300 Så hvis det er en lokal fil på din egen her på linie 15, for eksempel, du bruger 182 00:07:44,300 --> 00:07:46,570 de dobbelte citationstegn i stedet af de vinklede parenteser. 183 00:07:46,570 --> 00:07:48,270 >> Nu er det lidt interessant. 184 00:07:48,270 --> 00:07:51,830 Bemærk, at jeg har erklæret en global variabel i dette program på linie 18 185 00:07:51,830 --> 00:07:55,910 kaldes første, Ideen er dette er kommer til at være en pegepind til den første 186 00:07:55,910 --> 00:07:59,190 knude i min linkede liste, og jeg har initialiseret det til null, fordi jeg har 187 00:07:59,190 --> 00:08:02,310 ikke tildelt nogen egentlig knuder endnu. 188 00:08:02,310 --> 00:08:07,570 >> Så dette repræsenterer billedligt, hvad vi oplevede et øjeblik siden i billedet som 189 00:08:07,570 --> 00:08:10,090 at markøren på langt venstre side. 190 00:08:10,090 --> 00:08:12,260 Så lige nu er, at pointer ikke har en pil. 191 00:08:12,260 --> 00:08:14,590 Det i stedet er bare null. 192 00:08:14,590 --> 00:08:17,880 Men det repræsenterer, hvad der vil være den adressen på den første egentlige 193 00:08:17,880 --> 00:08:19,480 node i denne liste. 194 00:08:19,480 --> 00:08:22,120 Så jeg har implementeret det er en global fordi, som du kan se, alt dette 195 00:08:22,120 --> 00:08:25,310 Programmet gør i livet er at gennemføre en linket liste til mig. 196 00:08:25,310 --> 00:08:27,050 >> Nu har jeg fået et par prototyper her. 197 00:08:27,050 --> 00:08:31,190 Jeg besluttede at implementere funktioner som deletion, insertion, søgning og 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 det sidste bare at være gåtur på tværs af liste, trykning af sine elementer. 200 00:08:35,210 --> 00:08:36,750 Og nu her er min vigtigste rutine. 201 00:08:36,750 --> 00:08:39,890 Og vi vil ikke bruge for meget tid på disse, da dette er slags, forhåbentlig 202 00:08:39,890 --> 00:08:41,780 gamle hat nu. 203 00:08:41,780 --> 00:08:45,370 >> Jeg har tænkt mig at gøre følgende, mens brugeren samvirker. 204 00:08:45,370 --> 00:08:47,300 Så en, jeg kommer til at udskrive ud denne menu. 205 00:08:47,300 --> 00:08:49,420 Og jeg har formateret det som rent som jeg kunne. 206 00:08:49,420 --> 00:08:52,240 Hvis brugeren i én, der betyder de ønsker at slette noget. 207 00:08:52,240 --> 00:08:54,560 Hvis brugeren i to, der betyder de ønsker at indsætte noget. 208 00:08:54,560 --> 00:08:55,930 Og så videre. 209 00:08:55,930 --> 00:08:58,270 Jeg har tænkt mig at så spørge derefter i en kommando. 210 00:08:58,270 --> 00:08:59,300 Og så jeg har tænkt mig at bruge GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Så dette er en meget simpel menuing interface, hvor du bare nødt til at skrive 212 00:09:02,790 --> 00:09:05,270 en række kortlægning til en af disse kommandoer. 213 00:09:05,270 --> 00:09:08,730 Og nu har jeg en dejlig ren switch erklæring om, at der kommer til at tænde 214 00:09:08,730 --> 00:09:10,090 hvad brugeren skrevet i. 215 00:09:10,090 --> 00:09:12,180 Og hvis de har skrevet en, jeg vil kalde slet og bryde. 216 00:09:12,180 --> 00:09:14,380 Hvis de har skrevet to, jeg vil ringe indsætte og knække. 217 00:09:14,380 --> 00:09:16,490 >> Og nu varsel jeg har lagt hver af disse på samme linje. 218 00:09:16,490 --> 00:09:18,360 Dette er blot en stilistisk beslutning. 219 00:09:18,360 --> 00:09:20,210 Typisk har vi set noget som dette. 220 00:09:20,210 --> 00:09:23,260 Men jeg har lige besluttet, helt ærligt, mit program så mere læsbar, fordi 221 00:09:23,260 --> 00:09:25,980 Det var kun fire sager til bare liste den som dette. 222 00:09:25,980 --> 00:09:28,360 Totally legitime brug af stil. 223 00:09:28,360 --> 00:09:31,480 Og jeg har tænkt mig at gøre dette, så længe den Brugeren har ikke skrevet nul, hvilket jeg 224 00:09:31,480 --> 00:09:33,910 besluttet, vil betyde, at de ønsker at holde op. 225 00:09:33,910 --> 00:09:36,630 >> Så nu mærke til, hvad jeg kommer til at gøre her. 226 00:09:36,630 --> 00:09:38,650 Jeg har tænkt mig at befri listen tilsyneladende. 227 00:09:38,650 --> 00:09:40,230 Men mere om det om et øjeblik. 228 00:09:40,230 --> 00:09:41,640 Lad os først køre dette program. 229 00:09:41,640 --> 00:09:45,250 Så lad mig gøre en større terminal vindue, dot skråstreg liste 0. 230 00:09:45,250 --> 00:09:49,510 Jeg har tænkt mig at gå videre og indsætte ved skrive to, et tal som 50, og nu 231 00:09:49,510 --> 00:09:51,590 vil du se listen er nu 50 år. 232 00:09:51,590 --> 00:09:53,380 Og min tekst bare rulles lidt op. 233 00:09:53,380 --> 00:09:55,940 Så nu mærke indeholder listen tallet 50. 234 00:09:55,940 --> 00:09:58,220 >> Lad os gøre en anden indsats ved at tage to. 235 00:09:58,220 --> 00:10:01,630 Lad os skrive i antallet som én. 236 00:10:01,630 --> 00:10:03,940 List er nu en, efterfulgt af 50. 237 00:10:03,940 --> 00:10:06,020 Så dette er blot en tekstuel repræsentation af listen. 238 00:10:06,020 --> 00:10:10,550 Og lad os indsætte en mere antallet som nummeret 42, som er forhåbentlig 239 00:10:10,550 --> 00:10:14,620 kommer til at ende i midten, fordi dette program i bestemte former det 240 00:10:14,620 --> 00:10:16,320 elementer som den indsætter dem. 241 00:10:16,320 --> 00:10:17,220 Så der har vi det. 242 00:10:17,220 --> 00:10:20,730 Super simpelt program, der kunne absolut have brugt en array, men jeg 243 00:10:20,730 --> 00:10:23,280 tilfældigvis bruger en sammenkædet liste bare så jeg kan dynamisk 244 00:10:23,280 --> 00:10:24,610 vokse og krympe det. 245 00:10:24,610 --> 00:10:28,470 >> Så lad os tage et kig for søgning, hvis jeg køre kommandoen tre, jeg ønsker at søge 246 00:10:28,470 --> 00:10:31,040 for, siger, antallet 43.. 247 00:10:31,040 --> 00:10:34,190 Og intet var tilsyneladende fundet, fordi jeg fik tilbage ikke noget svar. 248 00:10:34,190 --> 00:10:35,010 Så lad os gøre det igen. 249 00:10:35,010 --> 00:10:35,690 Søg. 250 00:10:35,690 --> 00:10:39,520 Lad os søge efter 50, eller rettere søge for 42, har som en dejlig 251 00:10:39,520 --> 00:10:40,850 lidt subtil betydning. 252 00:10:40,850 --> 00:10:42,610 Og jeg fandt meningen med livet der. 253 00:10:42,610 --> 00:10:44,990 Number 42, hvis du ikke kender referencen, Google det. 254 00:10:44,990 --> 00:10:45,350 Ok. 255 00:10:45,350 --> 00:10:47,130 Så hvad er der dette program gjort for mig? 256 00:10:47,130 --> 00:10:50,660 Det er bare tilladt mig at indsætte dermed langt og søge efter elementer. 257 00:10:50,660 --> 00:10:53,650 >> Lad os hurtigt fremad, så at denne funktion, vi kiggede på 258 00:10:53,650 --> 00:10:55,360 på mandag som en teaser. 259 00:10:55,360 --> 00:10:59,620 Så denne funktion, hævder jeg, søgninger efter et element i listen ved først 260 00:10:59,620 --> 00:11:03,830 en, spørge brugeren, og derefter kalde GetInt at få et virkeligt int 261 00:11:03,830 --> 00:11:05,060 at du ønsker at søge efter. 262 00:11:05,060 --> 00:11:06,460 >> Så bemærke dette. 263 00:11:06,460 --> 00:11:10,690 Jeg har tænkt mig at oprette en midlertidig variabel i linie 188 kaldet pegepind - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 kunne have kaldt det noget. 266 00:11:12,440 --> 00:11:16,140 Og det er en pointer til en knude fordi jeg sagde node * der. 267 00:11:16,140 --> 00:11:19,900 Og jeg initialiserer det at være lig med først, så jeg faktisk har min 268 00:11:19,900 --> 00:11:22,860 finger, så at sige, på den meget første element på listen. 269 00:11:22,860 --> 00:11:27,460 Så hvis min højre hånd her er PTR jeg peger på de samme ting, der først 270 00:11:27,460 --> 00:11:28,670 peger på. 271 00:11:28,670 --> 00:11:31,430 >> Så nu tilbage i kode, hvad der sker næste - 272 00:11:31,430 --> 00:11:35,070 dette er en fælles paradigme når iteration over en struktur som et 273 00:11:35,070 --> 00:11:35,970 linkede liste. 274 00:11:35,970 --> 00:11:40,410 Jeg har tænkt mig at gøre følgende, mens pointer er ikke lig med null Så mens 275 00:11:40,410 --> 00:11:47,530 min finger ikke peger på nogle null værdi, hvis Markørpilen n n lig. 276 00:11:47,530 --> 00:11:52,290 Vi vil bemærke det første, at n er, hvad brugeren har indtastet pr GetInts kalder her. 277 00:11:52,290 --> 00:11:54,280 >> Og Markørpilen n betyder hvad? 278 00:11:54,280 --> 00:11:59,020 Tja, hvis vi går tilbage til det billede her, hvis jeg har en finger peger på 279 00:11:59,020 --> 00:12:02,960 at første knudepunkt indeholder ni, pil væsentligt betyder at gå til, at 280 00:12:02,960 --> 00:12:08,860 node og fange den værdi på placeringen n, i dette tilfælde, kaldet datafelt n. 281 00:12:08,860 --> 00:12:14,120 >> Som en sidebemærkning - og vi oplevede det et par uger siden, når nogen spurgte - 282 00:12:14,120 --> 00:12:18,840 denne syntaks er nyt, men det gør ikke give os kræfter, som vi 283 00:12:18,840 --> 00:12:20,040 ikke allerede har. 284 00:12:20,040 --> 00:12:25,325 Hvad var denne sætning svarer til at bruge dot notation og stjerne et par 285 00:12:25,325 --> 00:12:29,490 uger siden, da vi skrællede tilbage dette lag lidt tidligt? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [uhørlig]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Præcis, det var stjerne, og så det var stjerne dot n, med 288 00:12:38,880 --> 00:12:41,930 parenteser her, som ser, helt ærligt, jeg tror en masse 289 00:12:41,930 --> 00:12:43,320 mere kryptiske at læse. 290 00:12:43,320 --> 00:12:46,270 Men stjerne pointer, som altid, midler gå der. 291 00:12:46,270 --> 00:12:49,090 Og når du er der, hvilke data felt vil du få adgang til? 292 00:12:49,090 --> 00:12:52,730 Nå du bruge dot notation for at få adgang en structs datafelt, og jeg 293 00:12:52,730 --> 00:12:54,140 specifikt ønsker n. 294 00:12:54,140 --> 00:12:56,240 >> Helt ærligt, vil jeg hævde dette er blot sværere at læse. 295 00:12:56,240 --> 00:12:58,080 Det er sværere at huske, hvor behøver parenteserne går, 296 00:12:58,080 --> 00:12:59,030 stjerne og alt dette. 297 00:12:59,030 --> 00:13:02,150 Så verden har vedtaget nogle syntaktisk sukker, så at sige. 298 00:13:02,150 --> 00:13:04,740 Bare en sexet måde at sige, svarer det, og 299 00:13:04,740 --> 00:13:05,970 måske mere intuitiv. 300 00:13:05,970 --> 00:13:09,600 Hvis markøren er faktisk en pointer, at pil notation midler gå der og finde 301 00:13:09,600 --> 00:13:11,890 feltet i dette tilfælde kaldet n. 302 00:13:11,890 --> 00:13:13,660 >> Så hvis jeg finder det, mærke, hvad jeg gør. 303 00:13:13,660 --> 00:13:17,430 Jeg simpelthen printe ud, jeg fandt procent i, tilslutte værdien for denne int. 304 00:13:17,430 --> 00:13:20,730 Jeg kalder sove en andenplads lige at slags af pause ting på skærmen for at 305 00:13:20,730 --> 00:13:22,900 give brugeren en anden til at absorbere hvad der lige skete. 306 00:13:22,900 --> 00:13:24,290 Og så vil jeg bryde. 307 00:13:24,290 --> 00:13:26,330 Ellers hvad gør jeg? 308 00:13:26,330 --> 00:13:30,960 Jeg opdatere pointer til lige Markørpilen næste. 309 00:13:30,960 --> 00:13:35,840 >> Så bare for at være klar, det betyder at gå der, ved hjælp af min gamle skole notation. 310 00:13:35,840 --> 00:13:39,580 Så det betyder bare at gå til uanset du peger på, hvilket i den meget 311 00:13:39,580 --> 00:13:43,660 første tilfælde er jeg peger på struct med ni i den. 312 00:13:43,660 --> 00:13:44,510 Så jeg har gået der. 313 00:13:44,510 --> 00:13:47,880 Og så dot notation betyder, få værdien ved næste. 314 00:13:47,880 --> 00:13:50,470 >> Men værdien, selvom det er trukket som en smal, er bare et tal. 315 00:13:50,470 --> 00:13:51,720 Det er en numerisk adresse. 316 00:13:51,720 --> 00:13:55,670 Så dette én linje kode, uanset om skrevet som dette, jo mere kryptiske 317 00:13:55,670 --> 00:14:00,190 måde, eller som dette, den lidt mere intuitiv måde, betyder bare flytte min hånd 318 00:14:00,190 --> 00:14:03,460 fra den første knude til den næste, og derefter den næste, og derefter 319 00:14:03,460 --> 00:14:05,320 næste, og så videre. 320 00:14:05,320 --> 00:14:09,920 >> Så vi vil ikke dvæle ved den anden implementeringer af indsætte og slette 321 00:14:09,920 --> 00:14:14,030 og traversal, de to første af som er temmelig involveret. 322 00:14:14,030 --> 00:14:17,010 Og jeg tror, ​​det er ganske nemt at få tabt, når gør det verbalt. 323 00:14:17,010 --> 00:14:19,890 Men hvad vi kan gøre her er forsøge at bestemme, hvordan 324 00:14:19,890 --> 00:14:21,640 bedst at gøre dette visuelt. 325 00:14:21,640 --> 00:14:24,800 Fordi jeg vil foreslå, at hvis vi ønsker at indsætte elementer i dette 326 00:14:24,800 --> 00:14:26,680 eksisterende liste, som har fem elementer - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26 og 33 - 328 00:14:29,530 --> 00:14:33,300 hvis jeg skulle gennemføre dette i kode, jeg har brug for at overveje, hvordan man kan gå 329 00:14:33,300 --> 00:14:34,160 om at gøre dette. 330 00:14:34,160 --> 00:14:37,720 >> Og jeg vil foreslå, at tage små skridt hvorved, i dette tilfælde mener jeg, hvad er 331 00:14:37,720 --> 00:14:41,090 de mulige scenarier, som vi støde i almindelighed? 332 00:14:41,090 --> 00:14:44,120 Ved gennemførelsen af ​​skær til en sammenkædet liste, det bare sker for at være en 333 00:14:44,120 --> 00:14:46,090 specifikt eksempel på størrelse fem. 334 00:14:46,090 --> 00:14:50,420 Tja, hvis du vil indsætte et tal, gerne sige det nummer et, og 335 00:14:50,420 --> 00:14:53,380 opretholdelse sorteret orden, hvor selvfølgelig gør det nummer et behov for at 336 00:14:53,380 --> 00:14:55,686 går i denne specifikke eksempel? 337 00:14:55,686 --> 00:14:56,840 Ligesom i begyndelsen. 338 00:14:56,840 --> 00:15:00,030 >> Men hvad er interessant er, at Hvis du ønsker at indsætte en ind i dette 339 00:15:00,030 --> 00:15:04,100 liste, hvilke særlige pointer brug skal opdateres tilsyneladende? 340 00:15:04,100 --> 00:15:04,610 First. 341 00:15:04,610 --> 00:15:07,830 Så jeg vil hævde, det er den første sag at vi måske ønsker at overveje en 342 00:15:07,830 --> 00:15:11,140 scenarie involverer indsættelse på begyndelsen af ​​listen. 343 00:15:11,140 --> 00:15:15,400 >> Lad os plukker måske en så let eller endda lettere tilfælde, relativt set. 344 00:15:15,400 --> 00:15:18,110 Antag jeg ønsker at indsætte nummer 35 i sorteret rækkefølge. 345 00:15:18,110 --> 00:15:20,600 Det selvfølgelig hører derovre. 346 00:15:20,600 --> 00:15:25,320 Så hvad pointer selvfølgelig vil nødt til at blive opdateret på det scenarie? 347 00:15:25,320 --> 00:15:30,060 34 s pointer bliver ikke null men den adresse struct 348 00:15:30,060 --> 00:15:31,800 med tallet 35.. 349 00:15:31,800 --> 00:15:32,750 Så det er tilfælde to. 350 00:15:32,750 --> 00:15:36,190 Så allerede, jeg er slags kvantisere hvor meget arbejde jeg skal gøre her. 351 00:15:36,190 --> 00:15:39,880 >> Og endelig, den indlysende midterste sag er ja, i midten, hvis jeg ønsker at 352 00:15:39,880 --> 00:15:45,870 indsætte noget som siger 23, der går mellem 23 og 26, men 353 00:15:45,870 --> 00:15:48,680 nu tingene bliver lidt mere involveret, fordi det 354 00:15:48,680 --> 00:15:52,800 pointers skal ændres? 355 00:15:52,800 --> 00:15:56,680 Så 22 selvfølgelig skal ændres fordi han ikke kan pege på 26 længere. 356 00:15:56,680 --> 00:16:00,320 Han har brug for at pege på den nye node, Jeg bliver nødt til at afsætte ved at ringe 357 00:16:00,320 --> 00:16:01,770 malloc eller et tilsvarende. 358 00:16:01,770 --> 00:16:05,990 >> Men da jeg har også brug for, at nye node, 23 i dette tilfælde har til sit pointerflag 359 00:16:05,990 --> 00:16:07,870 peger på hvem? 360 00:16:07,870 --> 00:16:08,560 26.. 361 00:16:08,560 --> 00:16:10,380 Og der kommer til at være en rækkefølge af operationer her. 362 00:16:10,380 --> 00:16:13,410 Fordi hvis jeg gør det tåbeligt, og jeg for eksempel starter i begyndelsen af 363 00:16:13,410 --> 00:16:16,040 på listen, og mit mål er at indsætte 23. 364 00:16:16,040 --> 00:16:18,610 Og jeg tjekke, hører det her, nær ni? 365 00:16:18,610 --> 00:16:18,950 Nej. 366 00:16:18,950 --> 00:16:20,670 Er det hører til her, ved siden af ​​17? 367 00:16:20,670 --> 00:16:20,940 Nej. 368 00:16:20,940 --> 00:16:22,530 Betyder det hører til her siden 22? 369 00:16:22,530 --> 00:16:23,300 Ja. 370 00:16:23,300 --> 00:16:26,400 >> Nu, hvis jeg tåbelige her og ikke tænker dette igennem, jeg måske 371 00:16:26,400 --> 00:16:28,320 allokere min nye node for 23.. 372 00:16:28,320 --> 00:16:32,080 Jeg kunne opdatere markøren fra node kaldet 22, der peger 373 00:16:32,080 --> 00:16:33,080 det på den nye knudepunkt. 374 00:16:33,080 --> 00:16:36,140 Og hvad skal jeg nødt til at opdatere den nye node pointer at være? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [uhørlig]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Præcis. 377 00:16:38,385 --> 00:16:39,710 Peger på 26.. 378 00:16:39,710 --> 00:16:45,590 Men dammit hvis jeg ikke allerede opdatere 22 s pointer til at pege på denne fyr, og 379 00:16:45,590 --> 00:16:48,260 nu har jeg forældreløse, resten af listen, så at sige. 380 00:16:48,260 --> 00:16:52,140 Så rækkefølge af operationer her kommer til at være vigtige. 381 00:16:52,140 --> 00:16:55,100 >> For at gøre dette kunne jeg stjæle, sige, seks frivillige. 382 00:16:55,100 --> 00:16:57,650 Og lad os se om vi ikke kan gøre dette visuelt i stedet for code-wise. 383 00:16:57,650 --> 00:16:59,330 Og vi har nogle dejlige stress bolde til dig i dag. 384 00:16:59,330 --> 00:17:02,510 OK, hvad med en, to, i back - på enden der. 385 00:17:02,510 --> 00:17:04,530 tre, fire, begge to fyre på enden. 386 00:17:04,530 --> 00:17:05,579 Og fem, seks. 387 00:17:05,579 --> 00:17:05,839 Sure. 388 00:17:05,839 --> 00:17:06,450 Fem og seks. 389 00:17:06,450 --> 00:17:08,390 Okay og vi vil komme til jer næste gang. 390 00:17:08,390 --> 00:17:09,640 Okay, kom op. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Okay, siden du er heroppe første, vil du gerne være den akavet 393 00:17:14,819 --> 00:17:16,119 i Google Glass her? 394 00:17:16,119 --> 00:17:19,075 Okay, så OK, Glass, optage en video. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, du er god til at gå. 397 00:17:24,589 --> 00:17:27,950 >> Okay, så hvis du fyre kan komme over Her har jeg forberedt på forhånd 398 00:17:27,950 --> 00:17:30,110 nogle numre. 399 00:17:30,110 --> 00:17:31,240 Okay, kom herover. 400 00:17:31,240 --> 00:17:33,440 Og hvorfor du ikke gå lidt yderligere på den måde. 401 00:17:33,440 --> 00:17:35,520 Og lad os se, hvad er dit navn, med Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> STUDENT: Ben. 403 00:17:35,910 --> 00:17:36,230 >> SPEAKER 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, vil du være den første, bogstaveligt talt. 405 00:17:38,380 --> 00:17:40,580 Så vi vil sende dig til slutningen af ​​scenen. 406 00:17:40,580 --> 00:17:41,670 Okay, og dit navn? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, OK vil du være nummer ni. 409 00:17:44,530 --> 00:17:46,700 Så hvis du ønsker at følge Ben den måde. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, er du nødt til at være 17, som hvis jeg havde gjort dette mere 412 00:17:49,630 --> 00:17:51,260 intelligent, ville jeg have startede i den anden ende. 413 00:17:51,260 --> 00:17:52,370 Du går den vej. 414 00:17:52,370 --> 00:17:53,030 22.. 415 00:17:53,030 --> 00:17:53,670 Og du er? 416 00:17:53,670 --> 00:17:53,980 >> STUDENT: Mary. 417 00:17:53,980 --> 00:17:56,130 >> SPEAKER 1: Mary, vil du være 22. 418 00:17:56,130 --> 00:17:58,420 Og dit navn er? 419 00:17:58,420 --> 00:17:58,810 >> STUDENT: Chris. 420 00:17:58,810 --> 00:18:00,100 >> SPEAKER 1: Chris, vil du være 26. 421 00:18:00,100 --> 00:18:00,740 Og så endelig. 422 00:18:00,740 --> 00:18:01,400 >> STUDENT: Diana. 423 00:18:01,400 --> 00:18:02,670 >> SPEAKER 1: Diana, vil du være 34. 424 00:18:02,670 --> 00:18:03,920 Så du kom herover. 425 00:18:03,920 --> 00:18:06,360 >> Okay, så perfekt sorteres ordre allerede. 426 00:18:06,360 --> 00:18:09,600 Og lad os gå videre og gøre det så vi virkelig kan - 427 00:18:09,600 --> 00:18:11,720 Ben du bare slags kigge ud i ingenting der. 428 00:18:11,720 --> 00:18:15,670 OK, så lad os gå videre og skildrer dette hjælp arme, ligesom jeg var, præcist, 429 00:18:15,670 --> 00:18:16,250 hvad der foregår. 430 00:18:16,250 --> 00:18:19,540 Så gå videre og give jer en fod eller to mellem jer. 431 00:18:19,540 --> 00:18:22,900 Og gå videre og pege med den ene hånd til hvem du skal pege på 432 00:18:22,900 --> 00:18:23,470 baseret på denne. 433 00:18:23,470 --> 00:18:25,890 Og hvis du er null blot pege lige ned til gulvet. 434 00:18:25,890 --> 00:18:27,690 OK, så godt. 435 00:18:27,690 --> 00:18:32,290 >> Så nu har vi en linket liste, og lad mig foreslå, at jeg vil spille rollen som 436 00:18:32,290 --> 00:18:35,110 PTR, så jeg vil ikke genere transporterer det rundt. 437 00:18:35,110 --> 00:18:37,830 Og så - nogen dumme konvention - du kan kalde dette noget, du ønsker - 438 00:18:37,830 --> 00:18:39,800 forgænger pointer, Gæt pointer - 439 00:18:39,800 --> 00:18:43,930 det er bare det kaldenavn gav vi vores prøve kode til min venstre hånd. 440 00:18:43,930 --> 00:18:47,240 Dels at gå at være at holde styr på hvem der er hvem i 441 00:18:47,240 --> 00:18:48,400 følgende scenarier. 442 00:18:48,400 --> 00:18:52,390 >> Så formoder, først vil jeg plukke off at første eksempel at indsætte, siger 443 00:18:52,390 --> 00:18:54,330 20, på listen. 444 00:18:54,330 --> 00:18:57,160 Så jeg har tænkt mig at brug for nogen til legemliggøre nummer 20 for os. 445 00:18:57,160 --> 00:18:58,950 Så jeg er nødt til at allokere nogen fra publikum. 446 00:18:58,950 --> 00:18:59,380 Kom op. 447 00:18:59,380 --> 00:19:00,340 Hvad er dit navn? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, okay, så du skal være knudepunkt indeholdende 20. 450 00:19:05,270 --> 00:19:06,810 Okay, kom herover. 451 00:19:06,810 --> 00:19:10,025 Og selvfølgelig, hvor betyder Brian tilhører? 452 00:19:10,025 --> 00:19:12,190 Så i midten af ​​- faktisk, vent et øjeblik. 453 00:19:12,190 --> 00:19:13,420 Vi gør dette ud af orden. 454 00:19:13,420 --> 00:19:17,170 Vi gør dette til en meget hårdere end det behøver at være i første omgang. 455 00:19:17,170 --> 00:19:21,210 OK, vi kommer til gratis Brian og realloc Brian som fem. 456 00:19:21,210 --> 00:19:23,680 >> OK, så nu vil vi indsætte Brian som fem. 457 00:19:23,680 --> 00:19:25,960 Så kom herover ved siden af Ben for bare et øjeblik. 458 00:19:25,960 --> 00:19:28,250 Og du kan formentlig fortælle hvor denne historie går. 459 00:19:28,250 --> 00:19:30,500 Men lad os tænke grundigt over rækkefølgen af ​​operationer. 460 00:19:30,500 --> 00:19:32,880 Og det er netop denne visuelle der kommer til at line op 461 00:19:32,880 --> 00:19:34,080 med denne prøve kode. 462 00:19:34,080 --> 00:19:40,120 Så her har jeg PTR peger indledningsvis ikke Ben, per se, på, men uanset hvad 463 00:19:40,120 --> 00:19:43,245 værdi, han indeholder, som i dette tilfælde er - hvad er dit navn igen? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, så både Ben og jeg er peger på Jason i dette øjeblik. 466 00:19:47,350 --> 00:19:49,700 Så nu har jeg til at bestemme, hvor er Brian tilhører? 467 00:19:49,700 --> 00:19:53,500 Så det eneste, jeg har adgang til lige nu er hans n data element. 468 00:19:53,500 --> 00:19:58,280 Så jeg har tænkt mig at tjekke, er Brian mindre end Jason? 469 00:19:58,280 --> 00:19:59,770 Svaret er sandt. 470 00:19:59,770 --> 00:20:03,680 >> Så hvad nu skal ske, i den rigtige rækkefølge? 471 00:20:03,680 --> 00:20:07,120 Jeg har brug for at opdatere, hvor mange pointers i alt i denne historie? 472 00:20:07,120 --> 00:20:10,720 Hvor min hånd stadig peger på Jason og din hånd - hvis du vil 473 00:20:10,720 --> 00:20:12,930 sætte din hånd som, en slags, jeg ikke kender, et spørgsmålstegn. 474 00:20:12,930 --> 00:20:14,070 OK, godt. 475 00:20:14,070 --> 00:20:15,670 >> Okay, så du har et par kandidater. 476 00:20:15,670 --> 00:20:20,500 Enten Ben eller I eller Brian eller Jason eller alle andre, som 477 00:20:20,500 --> 00:20:21,370 pointers nødt til at ændre? 478 00:20:21,370 --> 00:20:23,260 Hvor mange i alt? 479 00:20:23,260 --> 00:20:24,080 >> OK, så to. 480 00:20:24,080 --> 00:20:27,090 Min pointer er faktisk ligegyldigt længere fordi jeg er bare midlertidig. 481 00:20:27,090 --> 00:20:31,370 Så det er disse to fyre, formentlig, både Ben og Brian. 482 00:20:31,370 --> 00:20:34,410 Så lad mig foreslå, at vi opdaterer Ben, da han er først. 483 00:20:34,410 --> 00:20:36,350 Det første element i denne liste nu kommer til at være Brian. 484 00:20:36,350 --> 00:20:38,070 Så Ben punkt Brian. 485 00:20:38,070 --> 00:20:39,320 OK, hvad nu? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Hvem bliver pegede på hvem? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [uhørlig]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK, så Brian har at pege på Jason. 490 00:20:46,180 --> 00:20:48,360 Men jeg har mistet overblikket over, at pointer? 491 00:20:48,360 --> 00:20:49,980 Må jeg ved, hvor Jason er? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [uhørlig]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: Jeg gør, da jeg er den midlertidige markøren. 494 00:20:52,620 --> 00:20:55,110 Og formentlig, jeg har ikke ændret sig at pege på den nye knudepunkt. 495 00:20:55,110 --> 00:20:58,300 Så vi kan simpelthen nødt Brian point ved hvem jeg peger på. 496 00:20:58,300 --> 00:20:59,000 Og vi er færdig. 497 00:20:59,000 --> 00:21:01,890 Så tilfælde en, indsættelse på begyndelsen af ​​listen. 498 00:21:01,890 --> 00:21:02,950 Der var to vigtige skridt. 499 00:21:02,950 --> 00:21:06,750 Én, vi nødt til at opdatere Ben, og derefter vi også nødt til at opdatere Brian. 500 00:21:06,750 --> 00:21:09,230 Og så har jeg ikke behøver at bekymre traipsing gennem resten af 501 00:21:09,230 --> 00:21:12,680 liste, fordi vi allerede fundet sit placering, fordi han tilhørte 502 00:21:12,680 --> 00:21:14,080 venstre af det første element. 503 00:21:14,080 --> 00:21:15,400 >> Okay, så temmelig ligetil. 504 00:21:15,400 --> 00:21:18,110 Faktisk føles som om vi er næsten hvilket gør dette for kompliceret. 505 00:21:18,110 --> 00:21:20,240 Så lad os nu plukke ud i slutningen af listen, se og hvor 506 00:21:20,240 --> 00:21:21,380 kompleksiteten starter. 507 00:21:21,380 --> 00:21:24,560 Så hvis nu Alloc I fra publikum. 508 00:21:24,560 --> 00:21:25,540 Nogen ønsker at spille 55? 509 00:21:25,540 --> 00:21:26,700 Okay, jeg så din hånd først. 510 00:21:26,700 --> 00:21:29,620 Kom op. 511 00:21:29,620 --> 00:21:30,030 Ja. 512 00:21:30,030 --> 00:21:31,177 Hvad er dit navn? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [uhørlig]. 514 00:21:32,310 --> 00:21:33,240 >> SPEAKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, kom op. 516 00:21:33,890 --> 00:21:35,730 Du vil være nummer 55.. 517 00:21:35,730 --> 00:21:37,820 Så du, selvfølgelig, tilhører ved slutningen af ​​listen. 518 00:21:37,820 --> 00:21:41,850 Så lad os replay simuleringen med mig være PTR for bare et øjeblik. 519 00:21:41,850 --> 00:21:44,050 Så jeg først kommer til at pege på hvad Ben peger på. 520 00:21:44,050 --> 00:21:45,900 Vi begge peger nu på Brian. 521 00:21:45,900 --> 00:21:48,420 Så 55 er ikke mindre end fem. 522 00:21:48,420 --> 00:21:52,510 Så jeg har tænkt mig at opdatere mig selv ved peger på Brians næste pointer, der 523 00:21:52,510 --> 00:21:54,450 nu er selvfølgelig Jason. 524 00:21:54,450 --> 00:21:57,310 55 ikke er mindre end ni, så Jeg har tænkt mig at opdatere PTR. 525 00:21:57,310 --> 00:21:58,890 Jeg har tænkt mig at opdatere PTR. 526 00:21:58,890 --> 00:22:02,290 Jeg har tænkt mig at opdatere PTR Jeg vil opdatere PTR. 527 00:22:02,290 --> 00:22:05,060 Og jeg har tænkt mig at - hmm, hvad er dit navn igen? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana peger naturligvis på null med sin venstre hånd. 530 00:22:09,190 --> 00:22:13,030 Så hvor kommer Habata faktisk hører klart? 531 00:22:13,030 --> 00:22:15,050 Til venstre her. 532 00:22:15,050 --> 00:22:19,460 Så hvordan kan jeg vide at sætte hende her Jeg tror, ​​jeg har skruet op. 533 00:22:19,460 --> 00:22:22,420 For hvad er PTR kunst dette tidspunkt? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Så selvom visuelt, kan vi naturligvis se alle disse 536 00:22:25,580 --> 00:22:26,610 fyre her på scenen. 537 00:22:26,610 --> 00:22:29,680 Jeg har ikke holdt styr på de tidligere person i listen. 538 00:22:29,680 --> 00:22:33,210 Jeg har ikke en finger at påpege, i dette tilfælde den node nummer 34. 539 00:22:33,210 --> 00:22:34,760 >> Så lad os faktisk begynder dette over. 540 00:22:34,760 --> 00:22:37,560 Så nu jeg faktisk har brug for en anden lokal variabel. 541 00:22:37,560 --> 00:22:40,980 Og dette er hvad du vil se i faktiske prøve C-kode, hvor som jeg går, 542 00:22:40,980 --> 00:22:45,860 når jeg opdatere min højre hånd til at pege Jason, og dermed forlader Brian bagefter, jeg 543 00:22:45,860 --> 00:22:51,440 bedre begynde at bruge min venstre hånd til opdatere, hvor jeg var, så når jeg går 544 00:22:51,440 --> 00:22:52,700 gennem denne liste - 545 00:22:52,700 --> 00:22:55,040 mere kejtet end jeg bestemt nu her visuelt - 546 00:22:55,040 --> 00:22:56,740 Jeg har tænkt mig at komme til slutningen af ​​listen. 547 00:22:56,740 --> 00:23:00,020 >> Denne hånd er stadig null, som er temmelig ubrugelig, andet end at indikere 548 00:23:00,020 --> 00:23:02,980 Jeg er helt klart i slutningen af ​​listen, men nu jeg i det mindste har denne 549 00:23:02,980 --> 00:23:08,270 forgænger pointer peger her, så nu, hvad hænder og hvilke pejlemærker brug 550 00:23:08,270 --> 00:23:10,150 skal opdateres? 551 00:23:10,150 --> 00:23:13,214 Hvis hånd vil du have omkonfigurere først? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [uhørlig]. 553 00:23:15,190 --> 00:23:16,220 >> SPEAKER 1: OK, så Dianas. 554 00:23:16,220 --> 00:23:21,110 Hvor vil du pege Dianas venstre pointer på? 555 00:23:21,110 --> 00:23:23,620 Ved 55, formentlig, således at Vi har indsat der. 556 00:23:23,620 --> 00:23:25,560 Og hvor skal 55 pointer hen? 557 00:23:25,560 --> 00:23:27,000 Ned, der repræsenterer null. 558 00:23:27,000 --> 00:23:28,890 Og mine hænder på dette tidspunkt, ikke noget, fordi de var bare 559 00:23:28,890 --> 00:23:30,070 midlertidige variabler. 560 00:23:30,070 --> 00:23:31,030 Så nu er vi færdig. 561 00:23:31,030 --> 00:23:34,650 >> Så den yderligere kompleksitet der - og det er ikke så svært at gennemføre, 562 00:23:34,650 --> 00:23:38,660 men vi har brug for en sekundær variabel at gøre sikker på, at inden jeg flytter min ret 563 00:23:38,660 --> 00:23:42,140 hånd, jeg opdatere værdien af ​​min venstre hånd, Gæt pointer i denne sag, så 564 00:23:42,140 --> 00:23:45,860 at jeg har en efterfølgende pointer at holde styr på, hvor jeg var. 565 00:23:45,860 --> 00:23:49,360 Nu som en sidebemærkning, hvis du tænker dette igennem, det føles som om det er en 566 00:23:49,360 --> 00:23:51,490 lidt irriterende at have til at holde styr på denne venstre hånd. 567 00:23:51,490 --> 00:23:54,015 >> Hvad ville en anden løsning til dette problem har været? 568 00:23:54,015 --> 00:23:56,500 Hvis du fik at redesigne de data, struktur, vi taler 569 00:23:56,500 --> 00:23:59,630 igennem lige nu? 570 00:23:59,630 --> 00:24:02,690 Hvis dette lige slags føles lidt irriterende at have, ligesom, to pointers 571 00:24:02,690 --> 00:24:08,430 går igennem listen, som kunne ellers have, i en ideel verden, vedligeholdes 572 00:24:08,430 --> 00:24:10,160 oplysninger, som vi har brug for? 573 00:24:10,160 --> 00:24:11,360 Ja? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [uhørlig]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Præcis. 577 00:24:16,150 --> 00:24:19,130 Lige så der er faktisk et interessant kim af en idé. 578 00:24:19,130 --> 00:24:22,470 Og denne idé om en tidligere pointer, peger på det forrige element. 579 00:24:22,470 --> 00:24:25,580 Hvad hvis jeg bare legemliggjort, at inde i selve listen? 580 00:24:25,580 --> 00:24:27,810 Og det vil være svært at visualisere dette uden alt papir 581 00:24:27,810 --> 00:24:28,830 falder på gulvet. 582 00:24:28,830 --> 00:24:31,860 Men formoder, at disse fyre bruges både af deres hænder til at have en tidligere 583 00:24:31,860 --> 00:24:35,950 pointer, og et næste pointer, hvorved gennemføre det, vi vil kalde en dobbelt 584 00:24:35,950 --> 00:24:36,830 linkede liste. 585 00:24:36,830 --> 00:24:41,090 Der ville tillade mig at sortere i spole tilbage, meget lettere uden mig, at 586 00:24:41,090 --> 00:24:43,800 programmør, skulle holde spore manuelt - 587 00:24:43,800 --> 00:24:44,980 virkelig manuelt - 588 00:24:44,980 --> 00:24:47,280 hvor jeg havde været tidligere i listen. 589 00:24:47,280 --> 00:24:48,110 Så vi vil ikke gøre det. 590 00:24:48,110 --> 00:24:50,950 Vi vil holde det simpelt, fordi det er vil komme til en pris, dobbelt så 591 00:24:50,950 --> 00:24:53,450 meget plads til markørerne, hvis du ønsker en anden. 592 00:24:53,450 --> 00:24:55,760 Men det er faktisk en fælles datastruktur kendt som en 593 00:24:55,760 --> 00:24:57,410 dobbelt linkede liste. 594 00:24:57,410 --> 00:25:01,310 >> Lad os gøre det sidste eksempel her og sætte disse fyre ud af deres elendighed. 595 00:25:01,310 --> 00:25:03,270 Så malloc 20.. 596 00:25:03,270 --> 00:25:05,320 Kom op fra midtergangen der. 597 00:25:05,320 --> 00:25:06,280 Okay, hvad er dit navn? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [uhørlig]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Undskyld? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [uhørlig]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK kommer på op. 603 00:25:10,230 --> 00:25:11,910 Du skal være 20. 604 00:25:11,910 --> 00:25:14,720 Du selvfølgelig kommer til at hører mellem 17 og 22.. 605 00:25:14,720 --> 00:25:16,150 Så lad mig lære min lektie. 606 00:25:16,150 --> 00:25:18,150 Jeg har tænkt mig at starte pointer peger på Brian. 607 00:25:18,150 --> 00:25:21,190 Og jeg har tænkt mig at få min venstre hånd kun opdatere til Brian som jeg flytter til 608 00:25:21,190 --> 00:25:23,600 Jason, kontrol gør 20 mindre end ni? 609 00:25:23,600 --> 00:25:24,060 Nej. 610 00:25:24,060 --> 00:25:25,430 Er 20 mindre end 17? 611 00:25:25,430 --> 00:25:25,880 Nej. 612 00:25:25,880 --> 00:25:27,450 Er 20 mindre end 22? 613 00:25:27,450 --> 00:25:28,440 Ja. 614 00:25:28,440 --> 00:25:34,070 Så hvad pointers eller hænder nødt til at ændre hvor de peger nu? 615 00:25:34,070 --> 00:25:37,070 >> Så vi kan gøre 17 peger på 20.. 616 00:25:37,070 --> 00:25:37,860 Så det er fint. 617 00:25:37,860 --> 00:25:40,080 Hvor vil vi pege markøren nu? 618 00:25:40,080 --> 00:25:41,330 Ved 22. 619 00:25:41,330 --> 00:25:45,410 Og vi ved, hvor 22 er, igen tak til min midlertidige pointer. 620 00:25:45,410 --> 00:25:46,760 Så vi er OK der. 621 00:25:46,760 --> 00:25:49,440 Så på grund af denne midlertidige opbevaring Jeg har holdt styr på, hvor alle er. 622 00:25:49,440 --> 00:25:55,055 Og nu kan du visuelt gå ind, hvor du tilhører, og nu har vi brug 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stress bolde, og en runde af bifald for 624 00:25:58,410 --> 00:25:59,770 disse fyre, hvis vi kunne. 625 00:25:59,770 --> 00:26:00,410 Pænt gjort. 626 00:26:00,410 --> 00:26:05,320 >> [Applaus] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: Okay. 628 00:26:06,330 --> 00:26:09,860 Og du kan beholde brikkerne af papir som souvenirs. 629 00:26:09,860 --> 00:26:15,930 >> Okay, så tro mig det er en masse lettere at gå gennem det med 630 00:26:15,930 --> 00:26:17,680 mennesker, end det er med konkrete kode. 631 00:26:17,680 --> 00:26:22,690 Men hvad du vil finde på bare et øjeblik nu er den samme - oh, tak. 632 00:26:22,690 --> 00:26:23,630 Tak - 633 00:26:23,630 --> 00:26:29,360 er, at du vil opdage, at de samme data struktur, en linket liste, kan faktisk 634 00:26:29,360 --> 00:26:33,200 anvendes som byggesten til endnu mere sofistikerede datastrukturer. 635 00:26:33,200 --> 00:26:37,620 >> Og indse også temaet her er, at Vi har absolut indført mere 636 00:26:37,620 --> 00:26:40,060 kompleksitet i gennemførelsen af denne algoritme. 637 00:26:40,060 --> 00:26:43,940 Indsættelse, og hvis vi gik igennem det, sletning og søgning, er lidt 638 00:26:43,940 --> 00:26:46,660 mere kompliceret, end det var med et array. 639 00:26:46,660 --> 00:26:48,040 Men vi få nogle dynamik. 640 00:26:48,040 --> 00:26:50,180 Vi får en adaptiv datastruktur. 641 00:26:50,180 --> 00:26:54,010 >> Men igen, vi betaler en pris for at have nogle yderligere kompleksitet, både i 642 00:26:54,010 --> 00:26:54,910 gennemførelse. 643 00:26:54,910 --> 00:26:56,750 Og vi er givet op random access. 644 00:26:56,750 --> 00:27:00,450 Og for at være ærlig, er der ikke nogle nice rent slide jeg kan give dig, at 645 00:27:00,450 --> 00:27:03,120 siger her, er, hvorfor en linket liste er bedre end et array. 646 00:27:03,120 --> 00:27:04,100 Og lad det blive ved det. 647 00:27:04,100 --> 00:27:07,520 Fordi temaet gentager nu, selv så meget mere i de kommende uger, er 648 00:27:07,520 --> 00:27:10,200 at der ikke er nødvendigvis et korrekt svar. 649 00:27:10,200 --> 00:27:13,830 >> Det er derfor, vi har den separate akse design for problemet sæt. 650 00:27:13,830 --> 00:27:17,700 Det vil være meget kontekstafhængige om du ønsker at bruge disse data 651 00:27:17,700 --> 00:27:21,750 struktur eller at en, og det vil afhænger af, hvad der betyder noget for dig i form 652 00:27:21,750 --> 00:27:24,620 af ressourcer og kompleksitet. 653 00:27:24,620 --> 00:27:28,830 >> Men lad mig foreslå, at de ideelle data struktur, den hellige gral, ville være 654 00:27:28,830 --> 00:27:32,200 noget, der er konstant tid, uanset hvor mange ting er 655 00:27:32,200 --> 00:27:36,940 inde i det, ville det ikke være fantastisk, hvis en datastruktur returnerede svar i 656 00:27:36,940 --> 00:27:37,920 konstant tid. 657 00:27:37,920 --> 00:27:38,330 Ja. 658 00:27:38,330 --> 00:27:40,110 Dette ord er i din enorme ordbogen. 659 00:27:40,110 --> 00:27:41,550 Eller nej, dette ord er det ikke. 660 00:27:41,550 --> 00:27:43,270 Eller sådanne problemer der. 661 00:27:43,270 --> 00:27:46,360 Jamen så lad os se om vi ikke kan i det mindste tage et skridt i retning af det. 662 00:27:46,360 --> 00:27:50,190 >> Lad mig foreslå en ny datastruktur, kan bruges til forskellige ting, 663 00:27:50,190 --> 00:27:52,260 i dette tilfælde kaldes en hash tabel. 664 00:27:52,260 --> 00:27:55,590 Og så er vi faktisk tilbage til skævede på et array, i dette tilfælde, og 665 00:27:55,590 --> 00:28:00,550 noget vilkårligt, jeg har tegnet dette hash tabel som en matrix med en slags 666 00:28:00,550 --> 00:28:02,810 to-dimensionelle række - 667 00:28:02,810 --> 00:28:05,410 eller rettere det er afbildet her som et to dimensionelle array - men det er bare 668 00:28:05,410 --> 00:28:10,770 en vifte af størrelse 26, sådan at hvis vi kalde array, bord beslag 669 00:28:10,770 --> 00:28:12,440 nul er rektanglet foroven. 670 00:28:12,440 --> 00:28:15,090 Tabel beslag 25 er rektanglet nederst. 671 00:28:15,090 --> 00:28:18,620 Og det er, hvordan jeg kunne tegne et data struktur, hvor jeg ønsker at gemme 672 00:28:18,620 --> 00:28:19,790 folks navne. 673 00:28:19,790 --> 00:28:24,370 >> Så for eksempel, og jeg vil ikke trække hele her på overhead, hvis jeg 674 00:28:24,370 --> 00:28:29,160 havde dette array, som jeg nu kommer til at kalde en hash tabel, og dette er igen 675 00:28:29,160 --> 00:28:31,360 placering nul. 676 00:28:31,360 --> 00:28:34,840 Dette her er placering én, og så videre. 677 00:28:34,840 --> 00:28:37,880 Jeg hævder, at jeg ønsker at bruge disse data struktur, af hensyn til diskussionen, 678 00:28:37,880 --> 00:28:42,600 til at gemme folks navne, Alice og Bob og Charlie og andre sådanne navne. 679 00:28:42,600 --> 00:28:46,110 Så tænk på det nu som begyndelsen af, siger, en ordbog 680 00:28:46,110 --> 00:28:47,520 med masser af ord. 681 00:28:47,520 --> 00:28:49,435 De tilfældigvis navne i vores eksempel her. 682 00:28:49,435 --> 00:28:52,560 Og det er alt for germane, måske, at gennemføre en stavekontrol, som vi 683 00:28:52,560 --> 00:28:54,400 måske for problemet sæt seks. 684 00:28:54,400 --> 00:28:59,300 >> Så hvis vi har en bred vifte af total størrelse 26 således at dette er den 25. placering 685 00:28:59,300 --> 00:29:03,390 forneden, og jeg hævder, at Alice er det første ord i ordbogen for 686 00:29:03,390 --> 00:29:07,260 navne, som jeg ønsker at indsætte i RAM, i denne datastruktur, er hvor 687 00:29:07,260 --> 00:29:12,480 instinkter fortæller dig, at Alices navn skal gå i denne array? 688 00:29:12,480 --> 00:29:13,510 >> Vi har 26 valgmuligheder. 689 00:29:13,510 --> 00:29:14,990 Hvor vi ønsker at sætte hende? 690 00:29:14,990 --> 00:29:16,200 Vi ønsker hende i konsollen nul, right? 691 00:29:16,200 --> 00:29:18,280 A for Alice, lad os kalde det nul. 692 00:29:18,280 --> 00:29:20,110 Og B vil være en, og C vil være to. 693 00:29:20,110 --> 00:29:22,600 Så vi kommer til at skrive Alices navn heroppe. 694 00:29:22,600 --> 00:29:24,890 Hvis vi derefter indsætte Bob, hans navn vil gå her. 695 00:29:24,890 --> 00:29:27,280 Charlie vil gå her. 696 00:29:27,280 --> 00:29:30,500 Og så videre ned gennem dette datastruktur. 697 00:29:30,500 --> 00:29:32,090 >> Dette er en vidunderlig datastruktur. 698 00:29:32,090 --> 00:29:32,730 Hvorfor? 699 00:29:32,730 --> 00:29:37,460 Nå, hvad er køretiden for indsætte et menneskes navn til dette 700 00:29:37,460 --> 00:29:39,850 datastruktur lige nu? 701 00:29:39,850 --> 00:29:43,702 Da denne tabel er implementeret, sandhed, som en matrix. 702 00:29:43,702 --> 00:29:44,940 Jamen det er konstant tid. 703 00:29:44,940 --> 00:29:45,800 Det er rækkefølgen af ​​én. 704 00:29:45,800 --> 00:29:46,360 Hvorfor? 705 00:29:46,360 --> 00:29:48,630 >> Jamen hvordan kan du bestemme hvor Alice hører? 706 00:29:48,630 --> 00:29:51,000 Du ser på, hvilket bogstav i hendes navn? 707 00:29:51,000 --> 00:29:51,490 Den første. 708 00:29:51,490 --> 00:29:54,350 Og du kan få der, hvis det er en streng, ved bare at kigge på snor 709 00:29:54,350 --> 00:29:55,200 beslag nul. 710 00:29:55,200 --> 00:29:57,110 Så nulte tegn i strengen. 711 00:29:57,110 --> 00:29:57,610 Det er nemt. 712 00:29:57,610 --> 00:30:00,350 Vi gjorde det i krypto overdragelse uger siden. 713 00:30:00,350 --> 00:30:05,310 Og når du ved, at Alices bogstav stort A, kan vi fratrække 714 00:30:05,310 --> 00:30:08,160 off 65 eller kapitalen A selv, der giver os nul. 715 00:30:08,160 --> 00:30:10,940 Så vi ved nu, at Alice tilhører ved placering nul. 716 00:30:10,940 --> 00:30:14,240 >> Og givet en pointer til disse data struktur af en slags, hvor lang 717 00:30:14,240 --> 00:30:18,840 det tage mig at finde sted nul i et array? 718 00:30:18,840 --> 00:30:22,080 Blot ét skridt, højre Det er konstant tid på grund af den random access vi 719 00:30:22,080 --> 00:30:23,780 foreslåede var en funktion i et array. 720 00:30:23,780 --> 00:30:28,570 Så kort sagt, regne ud, hvad indekset af Alice navn er, hvilket er i 721 00:30:28,570 --> 00:30:32,610 dette tilfælde er A, eller lad os bare løse at til nul, hvor B er en og C er 722 00:30:32,610 --> 00:30:34,900 to, regne det ud er konstant tid. 723 00:30:34,900 --> 00:30:38,510 Jeg behøver bare at se på hende første bogstav, finde ud af hvor nul er en 724 00:30:38,510 --> 00:30:40,460 array er også konstant tid. 725 00:30:40,460 --> 00:30:42,140 Så teknisk set, det er som to trin nu. 726 00:30:42,140 --> 00:30:43,330 Men det er stadig konstant. 727 00:30:43,330 --> 00:30:46,880 Så vi kalder den store O i en, så vi har indsat Alice i denne tabel i 728 00:30:46,880 --> 00:30:48,440 konstant tid. 729 00:30:48,440 --> 00:30:50,960 >> Men selvfølgelig, jeg bliver naive her, right? 730 00:30:50,960 --> 00:30:53,240 Hvad hvis der er en Aron i klassen? 731 00:30:53,240 --> 00:30:53,990 Eller Alicia? 732 00:30:53,990 --> 00:30:57,230 Eller andre navne starter med A. Hvor skal vi sætte 733 00:30:57,230 --> 00:31:00,800 denne person, right? 734 00:31:00,800 --> 00:31:03,420 Jeg mener, lige nu er der kun tre folk på bordet, så måske vi 735 00:31:03,420 --> 00:31:07,490 bør sætte Aaron ved placeringen nul en to tre. 736 00:31:07,490 --> 00:31:09,480 >> Right, jeg kunne sætte en her. 737 00:31:09,480 --> 00:31:13,350 Men så, hvis vi forsøger at indsætte David ind denne liste, er, hvor David hen? 738 00:31:13,350 --> 00:31:15,170 Nu er vores system starter bryde ned, til højre? 739 00:31:15,170 --> 00:31:19,210 Fordi nu David ender her Hvis Aaron er faktisk her. 740 00:31:19,210 --> 00:31:23,060 Og så nu hele denne idé om at have en rene data struktur, der giver os 741 00:31:23,060 --> 00:31:28,010 konstant tid insertioner er ikke længere konstant tid, fordi jeg er nødt til at 742 00:31:28,010 --> 00:31:31,240 tjek, åh, damnit, nogen er allerede på Alice placering. 743 00:31:31,240 --> 00:31:35,320 >> Lad mig sonde resten af ​​disse data struktur, på udkig efter et sted at sætte 744 00:31:35,320 --> 00:31:37,130 en som Aaron navn. 745 00:31:37,130 --> 00:31:39,390 Og så også er begyndt at tage lineær tid. 746 00:31:39,390 --> 00:31:42,710 Desuden, hvis du nu ønsker at finde den Aaron i denne datastruktur, og du 747 00:31:42,710 --> 00:31:45,430 kontrollere, og Aaron navn er ikke her. 748 00:31:45,430 --> 00:31:47,960 Ideelt set ville du bare sige Aarons ikke i datastrukturen. 749 00:31:47,960 --> 00:31:51,530 Men hvis du gør begynde at gøre plads til Aaron hvor der skulle have været en D 750 00:31:51,530 --> 00:31:55,600 eller E, kan du i værste fald nødt til at kontrollere hele datastruktur, i 751 00:31:55,600 --> 00:31:59,480 hvilket tilfælde det overdrages til noget lineær i størrelsen af ​​tabellen. 752 00:31:59,480 --> 00:32:00,920 >> Så okay, jeg løse dette. 753 00:32:00,920 --> 00:32:04,200 Problemet her er, at jeg havde 26 elementer i dette array. 754 00:32:04,200 --> 00:32:05,000 Lad mig ændre det. 755 00:32:05,000 --> 00:32:06,010 Hovsa. 756 00:32:06,010 --> 00:32:10,600 Lad mig ændre det, så hellere værende af str. 26 i alt, mærke bunden 757 00:32:10,600 --> 00:32:12,720 indeks vil skifte til n minus 1. 758 00:32:12,720 --> 00:32:16,610 Hvis 26 er tydeligvis for lille for mennesker ' navne, fordi der er tusindvis af 759 00:32:16,610 --> 00:32:20,830 navne i verden, så lad os bare gøre i 100 eller 1.000 eller 10.000. 760 00:32:20,830 --> 00:32:22,960 Lad os bare afsætte meget mere plads. 761 00:32:22,960 --> 00:32:27,230 >> Nå, der ikke nødvendigvis falder sandsynligheden for, at vi ikke vil have to 762 00:32:27,230 --> 00:32:31,510 folk med navne der starter med A, og så ville du forsøge at sætte en 763 00:32:31,510 --> 00:32:33,120 navne på placering nul stille. 764 00:32:33,120 --> 00:32:36,850 De er stadig kommer til at kollidere, hvilket betyder, at vi stadig har brug for en løsning til at sætte 765 00:32:36,850 --> 00:32:41,020 Alice og Aron og Alicia og andre navne, der starter med A steder. 766 00:32:41,020 --> 00:32:43,460 Men hvor meget af et problem er det? 767 00:32:43,460 --> 00:32:46,870 Hvad er sandsynligheden for, at du har kollisioner i et data 768 00:32:46,870 --> 00:32:48,240 struktur som denne? 769 00:32:48,240 --> 00:32:52,570 >> Nå, lad mig - vi vil komme tilbage på dette spørgsmål her. 770 00:32:52,570 --> 00:32:55,530 Og se på, hvordan vi kan løse det først. 771 00:32:55,530 --> 00:32:58,480 Lad mig trække op dette forslag her. 772 00:32:58,480 --> 00:33:02,020 Det, vi lige har beskrevet er en algoritme, en heuristisk kaldet lineær 773 00:33:02,020 --> 00:33:05,030 sondering hvorved hvis du forsøgte at indsætte noget her i disse data 774 00:33:05,030 --> 00:33:08,920 struktur, der kaldes en hash tabel, , og der er ikke plads der, du 775 00:33:08,920 --> 00:33:12,000 virkelig sonde datastruktur kontrol, er den tilgængelig? 776 00:33:12,000 --> 00:33:13,430 Er den tilgængelig er den tilgængelig? 777 00:33:13,430 --> 00:33:13,980 Er det til rådighed? 778 00:33:13,980 --> 00:33:17,550 Og når det endelig er, kan du indsætte navn, som du oprindeligt beregnet 779 00:33:17,550 --> 00:33:19,370 andre steder på det sted. 780 00:33:19,370 --> 00:33:23,360 Men i værste fald kun stedet kunne være selve bunden af ​​data 781 00:33:23,360 --> 00:33:25,090 struktur, allersidst i array. 782 00:33:25,090 --> 00:33:30,130 >> Så lineær sondering, i værste fald, overdrages til en lineær algoritme hvor 783 00:33:30,130 --> 00:33:34,500 Aron hvis han tilfældigvis skal indsættes sidst i denne datastruktur, kan han 784 00:33:34,500 --> 00:33:39,540 kollidere med denne første placering, men så ende med uheld til allersidst. 785 00:33:39,540 --> 00:33:43,940 Så dette er ikke en konstant tid hellige gral for os. 786 00:33:43,940 --> 00:33:47,650 Denne tilgang indsætte elementer i en datastruktur kaldet en hash 787 00:33:47,650 --> 00:33:52,050 tabel synes ikke at være konstant tid i det mindste ikke i det generelle tilfælde. 788 00:33:52,050 --> 00:33:54,000 Det kan udvikle sig til noget lineært. 789 00:33:54,000 --> 00:33:56,970 >> Så hvad nu hvis vi løser kollisioner noget anderledes? 790 00:33:56,970 --> 00:34:00,740 Så her er en mere sofistikeret tilgang til, hvad der er stadig 791 00:34:00,740 --> 00:34:02,800 kaldes en hash tabel. 792 00:34:02,800 --> 00:34:05,890 Og ved hash, som en sidebemærkning, hvad Jeg mener, er det indeks, 793 00:34:05,890 --> 00:34:07,070 Jeg nævnte tidligere. 794 00:34:07,070 --> 00:34:09,810 Til hash noget kan være tænkt som et verbum. 795 00:34:09,810 --> 00:34:13,690 >> Så hvis du hash Alice er et navn, en hash-funktion, så at sige, 796 00:34:13,690 --> 00:34:14,710 skal returnere et nummer. 797 00:34:14,710 --> 00:34:18,199 I dette tilfælde er nul, hvis hun hører hjemme på location nul, en, hvis hun hører hjemme på 798 00:34:18,199 --> 00:34:20,000 placering én, og så videre. 799 00:34:20,000 --> 00:34:24,360 Så mit hash-funktionen hidtil har været super enkel, kun ser på 800 00:34:24,360 --> 00:34:26,159 første bogstav i en eller andens navn. 801 00:34:26,159 --> 00:34:29,090 Men en hash-funktion tager input nogle stykke data, en 802 00:34:29,090 --> 00:34:30,210 streng, en int, uanset hvad. 803 00:34:30,210 --> 00:34:32,239 Og det spytter typisk et tal. 804 00:34:32,239 --> 00:34:35,739 Og det tal er, hvor disse data element hører til i en datastruktur 805 00:34:35,739 --> 00:34:37,800 kendt her som en hash tabel. 806 00:34:37,800 --> 00:34:41,400 >> Så bare intuitivt, det er en lidt anden sammenhæng. 807 00:34:41,400 --> 00:34:44,170 Dette faktisk hentyder til et eksempel involverer fødselsdage, hvor 808 00:34:44,170 --> 00:34:46,850 Der kan være så mange som 31 dage i måneden. 809 00:34:46,850 --> 00:34:52,239 Men hvad gjorde denne person beslutter at gøre i tilfælde af en kollision? 810 00:34:52,239 --> 00:34:55,304 Kontekst nu ved at blive, ikke en kollision mellem navne, men en kollision af fødselsdage, 811 00:34:55,304 --> 00:35:00,760 hvis to mennesker har samme fødselsdag den 2. oktober for eksempel. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [uhørlig]. 813 00:35:02,120 --> 00:35:05,010 >> SPEAKER 1: Ja, så her har vi Den gearing af hægtede lister. 814 00:35:05,010 --> 00:35:07,830 Så det ser lidt anderledes end vi trak det tidligere. 815 00:35:07,830 --> 00:35:10,790 Men vi synes at have til en matrix på venstre side. 816 00:35:10,790 --> 00:35:13,230 Det er en index, for ingen særlig grund. 817 00:35:13,230 --> 00:35:14,630 Men det er stadig et array. 818 00:35:14,630 --> 00:35:16,160 Det er en bred vifte af pegepinde. 819 00:35:16,160 --> 00:35:20,670 Og hver af disse elementer, og hvert af disse kredse eller skråstreger - skråstregen 820 00:35:20,670 --> 00:35:23,970 repræsenterer null - hver af disse pointere tilsyneladende peger på 821 00:35:23,970 --> 00:35:25,730 hvilke data struktur? 822 00:35:25,730 --> 00:35:26,890 En sammenkædet liste. 823 00:35:26,890 --> 00:35:30,530 >> Så nu har vi mulighed for at hard kode ind i vores program 824 00:35:30,530 --> 00:35:32,010 størrelsen af ​​tabellen. 825 00:35:32,010 --> 00:35:35,360 I dette tilfælde ved vi, at der er aldrig mere end 31 dage i en måned. 826 00:35:35,360 --> 00:35:38,480 Så svært kodning en værdi som 31 rimeligt i denne sammenhæng. 827 00:35:38,480 --> 00:35:42,700 I forbindelse med navne, kodning hårdt 26 er ikke urimeligt det folks 828 00:35:42,700 --> 00:35:46,340 navne kun starte med, for eksempel, alfabetet involverer A gennem Z. 829 00:35:46,340 --> 00:35:50,180 >> Vi kan proppe dem alle i disse data struktur, så længe, ​​når vi får en 830 00:35:50,180 --> 00:35:55,330 kollision, vi ikke sætte navne her vi i stedet tænker på disse celler 831 00:35:55,330 --> 00:36:00,270 ikke som strenge selv, men som henvisninger til, for eksempel, Alice. 832 00:36:00,270 --> 00:36:03,660 Og så Alice kan have en anden pointer til et andet navn, der starter med 833 00:36:03,660 --> 00:36:06,150 A. Og Bob faktisk går herovre. 834 00:36:06,150 --> 00:36:10,850 >> Og hvis der er et andet navn starter med B, ender han herovre. 835 00:36:10,850 --> 00:36:15,070 Og så hver af elementerne i dette tabel to, hvis vi designet denne a 836 00:36:15,070 --> 00:36:17,350 lidt mere behændigt - 837 00:36:17,350 --> 00:36:18,125 kommer på - 838 00:36:18,125 --> 00:36:22,950 hvis vi designet denne lidt mere dygtigt, bliver nu en adaptiv data 839 00:36:22,950 --> 00:36:27,720 struktur, hvor der er ingen hårde grænse på, hvor mange elementer, du kan indsætte 840 00:36:27,720 --> 00:36:30,700 i det, fordi hvis du har en kollision, det er fint. 841 00:36:30,700 --> 00:36:34,690 Bare gå videre og tilføje det til hvad vi så lidt siden var 842 00:36:34,690 --> 00:36:38,290 kendt som en sammenkædet liste. 843 00:36:38,290 --> 00:36:39,690 >> Jamen så lad os stoppe for bare et øjeblik. 844 00:36:39,690 --> 00:36:42,570 Hvad er sandsynligheden for en kollision i første omgang? 845 00:36:42,570 --> 00:36:45,480 Right, måske er jeg mere end tænker, måske Jeg er over Engineering Denne problem, 846 00:36:45,480 --> 00:36:46,370 fordi du ved, hvad? 847 00:36:46,370 --> 00:36:49,070 Ja, jeg kan komme op med vilkårlig eksempler fra toppen af ​​mit hoved som 848 00:36:49,070 --> 00:36:52,870 Allison og Aron, men i virkeligheden, en ensartet fordeling af 849 00:36:52,870 --> 00:36:56,990 indgange, der er nogle tilfældige indrykninger i en datastruktur, virkelig, hvad er 850 00:36:56,990 --> 00:36:58,580 sandsynligheden for en kollision? 851 00:36:58,580 --> 00:37:01,670 Nå viser sig, er det faktisk super høj. 852 00:37:01,670 --> 00:37:03,850 Lad mig generalisere dette Problemet er som dette. 853 00:37:03,850 --> 00:37:08,890 >> Så i et rum af n CS50 studerende, hvad er sandsynligheden for, at mindst 854 00:37:08,890 --> 00:37:11,010 to studerende i rummet har samme fødselsdag? 855 00:37:11,010 --> 00:37:13,346 Så der er hvad. et par hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 mennesker her, og flere hundrede mennesker derhjemme i dag. 857 00:37:16,790 --> 00:37:20,670 Så hvis du ønsker at spørge os selv, hvad der er sandsynligheden for to personer 858 00:37:20,670 --> 00:37:23,930 i dette rum har samme fødselsdag, vi kan finde ud af dette. 859 00:37:23,930 --> 00:37:26,250 Og jeg hævder faktisk er der to folk med samme fødselsdag. 860 00:37:26,250 --> 00:37:29,560 >> For eksempel er der nogen har fødselsdag i dag? 861 00:37:29,560 --> 00:37:31,340 I går? 862 00:37:31,340 --> 00:37:32,590 I morgen? 863 00:37:32,590 --> 00:37:35,980 Okay, så det føles som om jeg har tænkt mig nødt til at gøre dette 363 eller så flere 864 00:37:35,980 --> 00:37:39,500 gange til faktisk finde ud hvis vi har en kollision. 865 00:37:39,500 --> 00:37:42,350 Eller vi kunne bare gøre det matematisk snarere end kedelig 866 00:37:42,350 --> 00:37:43,200 at gøre dette. 867 00:37:43,200 --> 00:37:44,500 Og foreslå følgende. 868 00:37:44,500 --> 00:37:48,740 >> Så jeg foreslår, at vi kunne modellere sandsynligheden for to personer, der har 869 00:37:48,740 --> 00:37:55,320 samme fødselsdag som sandsynligheden for 1 minus sandsynligheden for ingen har 870 00:37:55,320 --> 00:37:56,290 den samme fødselsdag. 871 00:37:56,290 --> 00:37:59,960 Så for at få det, og det er bare det fancy måde at skrive dette, for 872 00:37:59,960 --> 00:38:03,090 første person i rummet, han eller hun kan have en af ​​de mulige 873 00:38:03,090 --> 00:38:07,370 fødselsdage antager 365 dage på året, med undskyldninger til personer med 874 00:38:07,370 --> 00:38:08,760 i februar 29 års fødselsdag. 875 00:38:08,760 --> 00:38:13,470 >> Så den første person i dette rum er gratis at have et vilkårligt antal fødselsdage 876 00:38:13,470 --> 00:38:18,280 ud af de 365 muligheder, således at vi vil gøre, at 365 divideret med 365 877 00:38:18,280 --> 00:38:18,990 der er én. 878 00:38:18,990 --> 00:38:22,700 Den næste person i rummet, hvis målet er at undgå en kollision, kan kun 879 00:38:22,700 --> 00:38:26,460 har hans eller hendes fødselsdag, hvordan mange forskellige mulige dage? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Så den anden valgperiode i dette udtryk er væsentlige at gøre det math for os 882 00:38:31,430 --> 00:38:33,460 ved at fratrække en mulig dag. 883 00:38:33,460 --> 00:38:36,390 Og derefter den næste dag, den næste dag, næste dag ned til det samlede antal 884 00:38:36,390 --> 00:38:38,100 mennesker i lokalet. 885 00:38:38,100 --> 00:38:41,290 >> Og hvis vi så overveje, hvad er så sandsynligheden ikke af alle, der har 886 00:38:41,290 --> 00:38:45,265 unikke fødselsdage, men igen 1 minus det, hvad vi får, er et udtryk 887 00:38:45,265 --> 00:38:47,810 der kan meget fancifully se sådan ud. 888 00:38:47,810 --> 00:38:50,330 Men det er mere interessant at se på visuelt. 889 00:38:50,330 --> 00:38:55,120 Dette er et diagram, hvor på x-aksen er antallet af personer i rummet, 890 00:38:55,120 --> 00:38:56,180 antallet af fødselsdage. 891 00:38:56,180 --> 00:38:59,840 På y-aksen er sandsynligheden af en kollision, mennesker to 892 00:38:59,840 --> 00:39:01,230 med samme fødselsdag. 893 00:39:01,230 --> 00:39:05,020 >> Og takeaway fra denne kurve er at så snart du kommer til at lide 40 894 00:39:05,020 --> 00:39:11,110 studerende, er du op på en 90% sandsynlighed combinatorically af to 895 00:39:11,110 --> 00:39:13,550 mennesker eller mere har den samme fødselsdag. 896 00:39:13,550 --> 00:39:18,600 Og når du kommer til at lide 58 mennesker er det næsten 100% af en chance to 897 00:39:18,600 --> 00:39:21,310 mennesker i lokalet skal have den samme fødselsdag, selvom der ikke er 898 00:39:21,310 --> 00:39:26,650 365 eller 366 mulige spande og kun 58 personer i rummet. 899 00:39:26,650 --> 00:39:29,900 Bare statistisk du sandsynligvis få kollisioner, som i kort 900 00:39:29,900 --> 00:39:31,810 motiverer denne diskussion. 901 00:39:31,810 --> 00:39:35,890 At selv om vi får fancy her, og starter med disse kæder, er vi stadig 902 00:39:35,890 --> 00:39:36,950 nødt til kollisioner. 903 00:39:36,950 --> 00:39:42,710 >> Så det rejser spørgsmålet, hvad er omkostninger ved at drive indsætninger og sletninger 904 00:39:42,710 --> 00:39:44,850 ind i en datastruktur som dette? 905 00:39:44,850 --> 00:39:46,630 Jamen så lad mig foreslå - 906 00:39:46,630 --> 00:39:51,570 og lad mig gå tilbage til skærmen i løbet af her - hvis vi har n elementer i 907 00:39:51,570 --> 00:39:56,330 liste, så hvis vi forsøger at indsætte n elementer, og vi har 908 00:39:56,330 --> 00:39:58,050 hvor mange samlede spande? 909 00:39:58,050 --> 00:40:03,450 Lad os sige 31 af total spande i tilfælde af fødselsdage. 910 00:40:03,450 --> 00:40:09,240 Hvad er den maksimale længde på en af disse kæder potentielt? 911 00:40:09,240 --> 00:40:12,670 >> Hvis der igen er 31 mulige fødselsdage i en given måned. 912 00:40:12,670 --> 00:40:14,580 Og vi bare sammenklumpning alle - 913 00:40:14,580 --> 00:40:15,580 faktisk det er en dum eksempel. 914 00:40:15,580 --> 00:40:16,960 Lad os gøre 26 i stedet. 915 00:40:16,960 --> 00:40:20,890 Så hvis faktisk har folk, hvis navne starte med A til Z, og dermed give 916 00:40:20,890 --> 00:40:22,780 us 26 muligheder. 917 00:40:22,780 --> 00:40:25,920 Og vi bruger en datastruktur som den, vi lige har set, hvor vi har 918 00:40:25,920 --> 00:40:30,210 en bred vifte af henvisninger, som hver peger på en sammenkædet liste, hvor 919 00:40:30,210 --> 00:40:32,360 første liste er alle med navnet Alice. 920 00:40:32,360 --> 00:40:35,770 Den anden liste er alle med navn, der starter med A, startende 921 00:40:35,770 --> 00:40:36,980 med B, og så videre. 922 00:40:36,980 --> 00:40:41,020 >> Hvad er den sandsynlige længden af ​​hver af disse lister, hvis vi antager en dejlig ren 923 00:40:41,020 --> 00:40:45,410 fordeling af navne A til Z hele datastruktur? 924 00:40:45,410 --> 00:40:50,210 Der er n mennesker i datastrukturen divideret med 26, hvis de er pænt 925 00:40:50,210 --> 00:40:52,110 spredt ud over hele datastruktur. 926 00:40:52,110 --> 00:40:54,970 Så længden af ​​hver af disse kæderne er n divideres med 26.. 927 00:40:54,970 --> 00:40:57,380 Men i store O-notation, hvad er det? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Hvad er det egentlig? 930 00:41:02,440 --> 00:41:04,150 Så det er egentlig bare n, right? 931 00:41:04,150 --> 00:41:06,620 Fordi vi har sagt tidligere, at ugh du dividere med 26.. 932 00:41:06,620 --> 00:41:08,710 Ja, i virkeligheden er det hurtigere. 933 00:41:08,710 --> 00:41:12,720 Men i teorien er det ikke fundamentalt alt det hurtigere. 934 00:41:12,720 --> 00:41:16,040 >> Så vi synes ikke at være så meget tættere på dette hellige gral. 935 00:41:16,040 --> 00:41:17,750 I virkeligheden er dette blot lineær tid. 936 00:41:17,750 --> 00:41:20,790 Heck, på dette punkt, hvorfor vi ikke bare bruge ét stort linkede liste? 937 00:41:20,790 --> 00:41:23,510 Hvorfor vi ikke bare bruge ét stort array til at gemme navnene på 938 00:41:23,510 --> 00:41:25,010 alle i lokalet? 939 00:41:25,010 --> 00:41:28,280 Nå, er der stadig noget overbevisende om en hash tabel? 940 00:41:28,280 --> 00:41:30,810 Er der stadig noget overbevisende om en datastruktur 941 00:41:30,810 --> 00:41:33,940 der ligner dette? 942 00:41:33,940 --> 00:41:35,182 Dette. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [uhørlig]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Right, og igen, hvis det er bare en lineær tid algoritme, og en 945 00:41:39,840 --> 00:41:42,780 lineære tid datastruktur, hvorfor jeg ikke bare gemme alles navn i en stor 946 00:41:42,780 --> 00:41:44,210 matrix, eller i en stor knyttet liste? 947 00:41:44,210 --> 00:41:47,010 Og stoppe med at lave CS så meget hårdere end det behøver at være? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Hvad er overbevisende om dette, selv selvom jeg ridset det ud? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [uhørlig]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: Indsættelser er ikke? 952 00:41:57,040 --> 00:41:58,140 Dyrt længere. 953 00:41:58,140 --> 00:42:03,390 Så indrykninger potentielt kunne stadig være konstant tid, selvom dine data 954 00:42:03,390 --> 00:42:07,910 struktur ligner det, en vifte af pegepinde, er hver især peger på 955 00:42:07,910 --> 00:42:09,550 potentielt en sammenkædet liste. 956 00:42:09,550 --> 00:42:15,220 Hvordan kunne du opnå konstant tid indsættelse af navne? 957 00:42:15,220 --> 00:42:16,280 Stik den i front, right? 958 00:42:16,280 --> 00:42:19,290 >> Hvis vi ofrer et design mål tidligere, hvor vi ønskede at holde 959 00:42:19,290 --> 00:42:22,650 alles navn, for eksempel, sorteres, eller alle numrene på scenen sorteret, 960 00:42:22,650 --> 00:42:25,020 Antag at vi har en usorteret linkede liste. 961 00:42:25,020 --> 00:42:29,960 Det koster kun os et eller to trin, gerne i tilfælde af Ben og Brian 962 00:42:29,960 --> 00:42:32,750 tidligere, at indsætte et element på begyndelsen af ​​listen. 963 00:42:32,750 --> 00:42:36,090 Så hvis vi er ligeglade om sortering alle De navne, der begynder med A eller alle 964 00:42:36,090 --> 00:42:39,660 de navne, der begynder med B, kan vi stadig opnå konstant tid indsættelse. 965 00:42:39,660 --> 00:42:43,900 Nu ser op Alice eller Bob eller hvilket som helst navn mere generelt er stadig, hvad? 966 00:42:43,900 --> 00:42:48,100 Det er stort O n divideret med 26, i ideelle tilfælde, hvor alle er ens 967 00:42:48,100 --> 00:42:51,190 distribueres, hvor der er så mange A'er som der er Zs, hvilket sandsynligvis 968 00:42:51,190 --> 00:42:52,220 urealistisk. 969 00:42:52,220 --> 00:42:53,880 Men det er stadig lineær. 970 00:42:53,880 --> 00:42:57,120 >> Men her kommer vi tilbage til det punkt af asymptotisk notation bliver 971 00:42:57,120 --> 00:42:58,600 teoretisk sandt. 972 00:42:58,600 --> 00:43:02,960 Men i den virkelige verden, hvis jeg hævder, at mit program kan gøre noget 26 gange 973 00:43:02,960 --> 00:43:06,210 hurtigere end din, hvis programmet vil du foretrækker at bruge? 974 00:43:06,210 --> 00:43:09,660 Yours eller mine, som er 26 gange hurtigere? 975 00:43:09,660 --> 00:43:14,320 Realistisk set den person, hvis er 26 gange hurtigere, selvom teoretisk 976 00:43:14,320 --> 00:43:18,790 vores algoritmer kører i samme asymptotisk køretid. 977 00:43:18,790 --> 00:43:20,940 >> Lad mig foreslå en anden opløsning helt. 978 00:43:20,940 --> 00:43:24,380 Og hvis dette ikke blæse dit sind, vi er ude af datastrukturer. 979 00:43:24,380 --> 00:43:27,420 Så dette er det en trie - 980 00:43:27,420 --> 00:43:28,520 slags dum navn. 981 00:43:28,520 --> 00:43:32,880 Den kommer fra søgninger, og ordet er stavet trie, t-r-i-e, fordi 982 00:43:32,880 --> 00:43:34,450 kursus hentning lyder som trie. 983 00:43:34,450 --> 00:43:36,580 Men det er historien af ordet trie. 984 00:43:36,580 --> 00:43:40,980 >> Så en trie er faktisk en form for træ, og det er også en spiller på det ord. 985 00:43:40,980 --> 00:43:46,330 Og selvom du ikke helt kan se det med denne visualisering, er en trie en 986 00:43:46,330 --> 00:43:50,790 træ struktureret, ligesom et stamtræ med en forfader foroven og partier 987 00:43:50,790 --> 00:43:54,530 af børnebørn og oldebørn som blade på bunden. 988 00:43:54,530 --> 00:43:58,100 Men hvert knudepunkt i en trie er en matrix. 989 00:43:58,100 --> 00:44:00,680 Og det er i et array - og lad os forsimpler et øjeblik - det er en 990 00:44:00,680 --> 00:44:04,600 array, i dette tilfælde, størrelse 26, hvor hver node igen er en vifte af størrelse 991 00:44:04,600 --> 00:44:09,000 26, hvor den nulte element i det matrix repræsenterer A, og den sidste 992 00:44:09,000 --> 00:44:11,810 element i hver sådan matrix repræsenterer Z. 993 00:44:11,810 --> 00:44:15,520 >> Så jeg foreslår altså, at disse data struktur, kendt som en trie, kan være 994 00:44:15,520 --> 00:44:17,600 anvendes også til at gemme ord. 995 00:44:17,600 --> 00:44:21,740 Vi så for et øjeblik siden, hvordan vi kunne gemme ord, eller i dette tilfælde navne, og vi 996 00:44:21,740 --> 00:44:25,440 så tidligere, hvordan vi kan gemme telefonnumre, men hvis vi fokuserer på navne eller strygere 997 00:44:25,440 --> 00:44:27,460 her mærke til, hvad der er interessant. 998 00:44:27,460 --> 00:44:32,210 Jeg hævder, at navnet Maxwell er indersiden af ​​denne datastruktur. 999 00:44:32,210 --> 00:44:33,730 Hvor ser du Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [uhørlig]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: På venstre. 1002 00:44:36,240 --> 00:44:39,910 Så hvad er interessant med disse data struktur er snarere end lagrer 1003 00:44:39,910 --> 00:44:46,200 streng M-A-X-W-E-L-L omvendt skråstreg nul, alle contiguously, hvad du gør i stedet 1004 00:44:46,200 --> 00:44:46,890 følger. 1005 00:44:46,890 --> 00:44:50,510 Hvis dette er en trie ligesom datastruktur, hver af hvis knudepunkter er igen et array, 1006 00:44:50,510 --> 00:44:54,650 og du ønsker at gemme Maxwell, skal du først indeks og så roden knudepunkt, så 1007 00:44:54,650 --> 00:44:57,810 tale, den øverste knude, ved placeringen M, til højre, så 1008 00:44:57,810 --> 00:44:59,160 groft ind mod midten. 1009 00:44:59,160 --> 00:45:03,740 Og så derfra følger du en pointer til et barn noder, så at sige. 1010 00:45:03,740 --> 00:45:06,150 Så i stamtræet forstand, du følger det nedad. 1011 00:45:06,150 --> 00:45:09,030 Og der fører dig til en anden node til venstre er der, som er 1012 00:45:09,030 --> 00:45:10,540 bare en anden array. 1013 00:45:10,540 --> 00:45:14,710 >> Og hvis du ønsker at gemme Maxwell, du finder markøren, der repræsenterer 1014 00:45:14,710 --> 00:45:16,430 En, der er denne ene her. 1015 00:45:16,430 --> 00:45:17,840 Så kan du gå videre til næste node. 1016 00:45:17,840 --> 00:45:20,100 Og bemærk - dette er grunden til billedets en lille bedrager - 1017 00:45:20,100 --> 00:45:21,990 denne knude ser super lille. 1018 00:45:21,990 --> 00:45:26,050 Men til højre for dette er Y og Z. Det er bare forfatteren har afkortet den 1019 00:45:26,050 --> 00:45:27,630 billedet, så du rent faktisk se tingene. 1020 00:45:27,630 --> 00:45:30,400 Ellers billede ville være enormt brede. 1021 00:45:30,400 --> 00:45:36,180 Så nu er du indekset i location X, så W, så E, så L, så L. Så hvad er 1022 00:45:36,180 --> 00:45:37,380 denne nysgerrighed? 1023 00:45:37,380 --> 00:45:41,250 >> Tja, hvis vi bruger denne slags nye tage på, hvordan man gemme en snor i en 1024 00:45:41,250 --> 00:45:44,500 datastruktur, du stadig nødt til at hovedsagelig afkrydse i de data, 1025 00:45:44,500 --> 00:45:47,250 struktur, et ord ender her. 1026 00:45:47,250 --> 00:45:50,830 Med andre ord, hver af disse knudepunkter en eller anden måde er nødt til at huske, at vi 1027 00:45:50,830 --> 00:45:53,500 faktisk fulgt alle disse pejlemærker og forlader lidt 1028 00:45:53,500 --> 00:45:58,370 brødkrummen nederst her på dette struktur at angive M-A-X-W-E-L-L er 1029 00:45:58,370 --> 00:46:00,230 faktisk i dette datastruktur. 1030 00:46:00,230 --> 00:46:02,040 >> Så vi kan gøre dette på følgende måde. 1031 00:46:02,040 --> 00:46:06,810 Hver af knuder i det billede, vi bare Saven har en, en vifte af størrelse 27.. 1032 00:46:06,810 --> 00:46:10,550 Og det er nu 27, fordi der i p sæt seks, Vi vil faktisk give dig en apostrof, 1033 00:46:10,550 --> 00:46:13,590 så vi kan få navne som O'Reilly og andre med apostroffer. 1034 00:46:13,590 --> 00:46:14,820 Men samme idé. 1035 00:46:14,820 --> 00:46:17,710 Hvert af disse elementer i array-point til en struct 1036 00:46:17,710 --> 00:46:19,320 knude, så bare en knude. 1037 00:46:19,320 --> 00:46:21,430 Så det er meget minder af vores linkede liste. 1038 00:46:21,430 --> 00:46:24,550 >> Og så har jeg en boolesk, som jeg vil kalde ord, som netop kommer til at være 1039 00:46:24,550 --> 00:46:29,120 tilfældet, hvis et ord ender på dette knudepunkt i træet. 1040 00:46:29,120 --> 00:46:32,870 Det effektivt repræsenterer den lille trekant oplevede vi for et øjeblik siden. 1041 00:46:32,870 --> 00:46:37,190 Så hvis et ord slutter ved dette knudepunkt i træet, vil det ord felt være sandt, 1042 00:46:37,190 --> 00:46:41,990 som er begrebsmæssigt tjekker ud, eller vi tegne denne trekant, ja der 1043 00:46:41,990 --> 00:46:44,080 er et ord her. 1044 00:46:44,080 --> 00:46:45,120 >> Så dette er en trie. 1045 00:46:45,120 --> 00:46:48,540 Og nu er spørgsmålet, hvad er dens køretid? 1046 00:46:48,540 --> 00:46:49,930 Er det store O n? 1047 00:46:49,930 --> 00:46:51,410 Er det noget andet? 1048 00:46:51,410 --> 00:46:57,330 Tja, hvis du har n navne i disse data struktur, Maxwell er blot én af 1049 00:46:57,330 --> 00:47:02,330 dem, hvad er køretiden for indsætter eller finde Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Hvad er køretid at indsætte Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Hvis der er n andre navne allerede i tabellen? 1053 00:47:11,740 --> 00:47:12,507 Ja? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [uhørlig]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Ja, det er længden af navnet, right? 1056 00:47:17,550 --> 00:47:24,420 Så M-a-x-w-e-l-l, så det føles som dette algoritme er stort O i syv. 1057 00:47:24,420 --> 00:47:26,580 Nu, selvfølgelig, navn vil variere i længde. 1058 00:47:26,580 --> 00:47:27,380 Måske er det et kort navn. 1059 00:47:27,380 --> 00:47:28,600 Måske er det en længere navn. 1060 00:47:28,600 --> 00:47:33,390 Men hvad er nøglen her, er, at det er et konstant antal. 1061 00:47:33,390 --> 00:47:36,810 Og måske er det ikke rigtig konstant, men Gud, hvis realistisk, i en 1062 00:47:36,810 --> 00:47:41,570 ordbog, er der sandsynligvis nogle grænse på antallet af bogstaver i en 1063 00:47:41,570 --> 00:47:43,820 persons navn i et bestemt land. 1064 00:47:43,820 --> 00:47:46,940 >> Og så vi kan antage, at værdi er en konstant. 1065 00:47:46,940 --> 00:47:47,750 Jeg ved ikke, hvad det er. 1066 00:47:47,750 --> 00:47:50,440 Det er sandsynligvis større end vi synes, det er. 1067 00:47:50,440 --> 00:47:52,720 Fordi der er altid nogle hjørne tilfældet med en vanvittig lange navn. 1068 00:47:52,720 --> 00:47:56,360 Så lad os kalde det k, men det er stadig en konstant formentlig, fordi hver 1069 00:47:56,360 --> 00:48:00,190 navn i verden, i det mindste i en bestemt land, er, at længde eller 1070 00:48:00,190 --> 00:48:01,780 kortere, så det er konstant. 1071 00:48:01,780 --> 00:48:04,490 Men når vi har sagt noget, er stort O i en konstant værdi, hvad er det 1072 00:48:04,490 --> 00:48:07,760 virkelig svarer til? 1073 00:48:07,760 --> 00:48:10,420 Det er virkelig det samme som siger konstant tid. 1074 00:48:10,420 --> 00:48:11,530 >> Nu er vi slags snyd, right? 1075 00:48:11,530 --> 00:48:15,340 Vi er slags udnytte noget teori her for at sige, at ja, orden k er 1076 00:48:15,340 --> 00:48:17,450 egentlig bare bestille af en, og det er konstant tid. 1077 00:48:17,450 --> 00:48:18,200 Men det virkelig er. 1078 00:48:18,200 --> 00:48:22,550 Fordi det centrale indsigt her er at hvis vi har n navne allerede i dette 1079 00:48:22,550 --> 00:48:26,010 datastruktur, og vi insert Maxwell, er den mængde tid, det tager os til 1080 00:48:26,010 --> 00:48:29,530 indsætte Maxwell overhovedet berørte ved hvor mange andre mennesker 1081 00:48:29,530 --> 00:48:31,100 er i datastrukturen? 1082 00:48:31,100 --> 00:48:31,670 Synes ikke at være. 1083 00:48:31,670 --> 00:48:36,280 Hvis jeg havde en milliard flere elementer i denne trie, og indsæt derefter Maxwell er 1084 00:48:36,280 --> 00:48:38,650 Han overhovedet påvirket? 1085 00:48:38,650 --> 00:48:39,050 Nej. 1086 00:48:39,050 --> 00:48:42,950 Og det er ulig nogen af ​​dagen data strukturer, vi har set hidtil, hvor 1087 00:48:42,950 --> 00:48:46,820 køretiden for din algoritme er helt uafhængigt af, hvor meget 1088 00:48:46,820 --> 00:48:51,430 ting er, eller ikke allerede er i denne datastruktur. 1089 00:48:51,430 --> 00:48:54,650 >> Og så med denne giver dig nu, er en mulighed for p sæt seks, hvilket vil 1090 00:48:54,650 --> 00:48:58,310 igen involvere gennemføre din egen spell checker, læsning i 150.000 1091 00:48:58,310 --> 00:49:01,050 ord, hvordan man bedst opbevarer det er ikke nødvendigvis indlysende. 1092 00:49:01,050 --> 00:49:04,030 Og selvom jeg har stræbt efter at finde den hellige gral, det gør jeg ikke 1093 00:49:04,030 --> 00:49:05,330 hævder, at en trie er. 1094 00:49:05,330 --> 00:49:09,810 I virkeligheden, kan en hash tabel udmærket vise sig at være meget mere effektivt. 1095 00:49:09,810 --> 00:49:10,830 Men de er bare - 1096 00:49:10,830 --> 00:49:14,620 det er bare én af design beslutninger bliver du nødt til at gøre. 1097 00:49:14,620 --> 00:49:18,920 >> Men at lukke lad os tage 50 eller deromkring sekunder til at tage et kig på, hvad der ligger 1098 00:49:18,920 --> 00:49:22,190 forude næste uge, og ud over vi overgangen fra denne kommandolinjen 1099 00:49:22,190 --> 00:49:26,220 verden, hvis C-programmer til tingene web baseret, og sprog som PHP og 1100 00:49:26,220 --> 00:49:30,350 JavaScript og internettet selv, protokoller som HTTP, som du har 1101 00:49:30,350 --> 00:49:32,870 taget for givet i årevis nu, og maskinskrevet fleste hver 1102 00:49:32,870 --> 00:49:34,440 dag, måske, eller set. 1103 00:49:34,440 --> 00:49:37,420 Og vi vil begynde at skrælle tilbage lag af hvad er internettet. 1104 00:49:37,420 --> 00:49:40,650 Og hvad er den kode, ligger til grund nutidens værktøjer. 1105 00:49:40,650 --> 00:49:43,230 Så 50 sekunder af denne teaser her. 1106 00:49:43,230 --> 00:49:46,570 Jeg giver dig Warriors of the Net. 1107 00:49:46,570 --> 00:49:51,370 >> [VIDEO AFSPIL] 1108 00:49:51,370 --> 00:49:56,764 >> -Han kom med et budskab. 1109 00:49:56,764 --> 00:50:00,687 Med en protokol helt hans egen. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Han kom til en verden af ​​grusomme firewalls, ufølsom routere, og farer langt 1112 00:50:19,780 --> 00:50:22,600 værre end døden. 1113 00:50:22,600 --> 00:50:23,590 Han er hurtig. 1114 00:50:23,590 --> 00:50:25,300 Han er stærk. 1115 00:50:25,300 --> 00:50:27,700 Han er TCPIP. 1116 00:50:27,700 --> 00:50:30,420 Og han har din adresse. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Warriors af nettet. 1119 00:50:34,590 --> 00:50:35,290 >> [END VIDEOAFSPILNING] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: Det er, hvordan internettet skal arbejde i næste uge. 1121 00:50:38,070 --> 00:50:40,406