1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: All right, så vi er tilbake. 3 00:00:13,120 --> 00:00:14,480 Velkommen til CS50. 4 00:00:14,480 --> 00:00:16,510 Dette er slutten av uke syv. 5 00:00:16,510 --> 00:00:20,200 Så husker at sist gang, begynte vi sett på litt mer sofistikert 6 00:00:20,200 --> 00:00:21,100 datastrukturer. 7 00:00:21,100 --> 00:00:25,110 Siden frem til nå, alt vi hadde egentlig til rådighet var dette en matrise. 8 00:00:25,110 --> 00:00:29,340 >> Men før vi forkaste matrisen som ikke alle som interessant, som faktisk er det 9 00:00:29,340 --> 00:00:33,570 faktisk er, hva er noen av de positive til denne enkle data 10 00:00:33,570 --> 00:00:34,560 struktur så langt? 11 00:00:34,560 --> 00:00:36,110 Hva er det gode på? 12 00:00:36,110 --> 00:00:39,450 Så langt som vi har sett? 13 00:00:39,450 --> 00:00:42,540 Hva har du? 14 00:00:42,540 --> 00:00:44,028 Ingenting. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [uhørlig]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Hva 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 bra skjønt? 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 effektiv i den forstand at du kan tildele en 22 00:00:56,240 --> 00:01:00,070 fast beløp på plass, som forhåpentligvis er nettopp så mye 23 00:01:00,070 --> 00:01:01,180 plass som du vil. 24 00:01:01,180 --> 00:01:02,720 Så det kan være absolutt et pluss. 25 00:01:02,720 --> 00:01:06,530 >> Hva er en annen opp side av en matrise? 26 00:01:06,530 --> 00:01:07,610 Yeah? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [uhørlig]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: All the - beklager? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [uhørlig]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Alle boksene i minnet eller ved siden av hverandre. 31 00:01:13,620 --> 00:01:15,220 Og det er nyttig - hvorfor? 32 00:01:15,220 --> 00:01:15,970 Det er helt sant. 33 00:01:15,970 --> 00:01:18,611 Men hvordan kan vi utnytte at sannheten? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [uhørlig]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Akkurat, kan vi holde styr på der alt er bare ved å vite 36 00:01:24,490 --> 00:01:28,560 en adresse, nemlig den adresse i første byte av at mengde minne. 37 00:01:28,560 --> 00:01:30,420 Eller i tilfelle av strengen, adressen til den første 38 00:01:30,420 --> 00:01:31,460 røye i strengen. 39 00:01:31,460 --> 00:01:33,330 Og derfra kan vi finne slutten av strengen. 40 00:01:33,330 --> 00:01:35,710 Vi kan finne det andre elementet, den tredje element, og så videre. 41 00:01:35,710 --> 00:01:38,740 >> Og så fancy måte å beskrive at funksjonen er at arrays gi oss 42 00:01:38,740 --> 00:01:40,020 random access. 43 00:01:40,020 --> 00:01:44,330 Bare ved hjelp av hakeparentes notasjon og et nummer, kan du hoppe til 44 00:01:44,330 --> 00:01:48,070 et spesifikt element i matrisen i konstant tid, big O 45 00:01:48,070 --> 00:01:49,810 av en, så å si. 46 00:01:49,810 --> 00:01:51,080 >> Men det har vært noen ulemper. 47 00:01:51,080 --> 00:01:53,110 Hva en rekke ikke veldig lett? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Hva er det ikke god på? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [uhørlig]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Hva 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: Utvidelse i størrelse. 54 00:02:01,460 --> 00:02:04,800 Så ulempene i matrisen er nettopp det motsatte av hva 55 00:02:04,800 --> 00:02:05,540 oppsider er. 56 00:02:05,540 --> 00:02:07,610 Så en av ulempene er at det er en fast størrelse. 57 00:02:07,610 --> 00:02:09,400 Så du kan egentlig ikke vokse det. 58 00:02:09,400 --> 00:02:13,510 Du kan omdisponere en større del av minnet, og deretter flytte de gamle elementene 59 00:02:13,510 --> 00:02:14,460 inn det nye utvalget. 60 00:02:14,460 --> 00:02:18,060 Og så fri den gamle array, for eksempel, ved å bruke malloc eller en lignende 61 00:02:18,060 --> 00:02:21,180 funksjon kalt realloc, som reallocates minne. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, som en side, prøver å gi deg minne som er ved siden av rekken 63 00:02:25,490 --> 00:02:26,610 som du allerede har. 64 00:02:26,610 --> 00:02:28,740 Men det kan flytte ting rundt helt. 65 00:02:28,740 --> 00:02:30,710 Men kort sagt, det er dyrt, ikke sant? 66 00:02:30,710 --> 00:02:33,440 Fordi hvis du har en mengde minne om denne størrelsen, men du virkelig vil ha en 67 00:02:33,440 --> 00:02:36,710 av denne størrelsen, og du ønsker å bevare de opprinnelige elementene, må du 68 00:02:36,710 --> 00:02:40,510 omtrent en lineær tid kopieringen som må skje fra 69 00:02:40,510 --> 00:02:41,900 gamle array til nye. 70 00:02:41,900 --> 00:02:44,630 Og virkeligheten ber operativsystemet systemet igjen og igjen og 71 00:02:44,630 --> 00:02:48,340 igjen for store biter av minne kan starte til å koste deg litt tid også. 72 00:02:48,340 --> 00:02:52,250 Så det er både en velsignelse og en forbannelse i skjule det faktum at disse arrays 73 00:02:52,250 --> 00:02:53,860 er av fast størrelse. 74 00:02:53,860 --> 00:02:56,790 Men hvis vi innfører i stedet noe som dette, som vi kalte en koblet 75 00:02:56,790 --> 00:03:00,580 liste, får vi noen oppsider og noen downsides her også. 76 00:03:00,580 --> 00:03:05,780 >> Så en lenket liste er bare en data Strukturen består av C structs i dette 77 00:03:05,780 --> 00:03:09,850 tilfelle, hvor en struct, husker, er bare en beholder for en eller flere bestemte 78 00:03:09,850 --> 00:03:11,100 typer variabler. 79 00:03:11,100 --> 00:03:16,110 I dette tilfellet, hva gjør de datatyper synes å være inne i struct som 80 00:03:16,110 --> 00:03:17,600 siste gang vi kalte en node? 81 00:03:17,600 --> 00:03:19,380 Hver av disse rektangler er en node. 82 00:03:19,380 --> 00:03:22,660 Og hver av de mindre rektanglene innsiden av det er en datatype. 83 00:03:22,660 --> 00:03:25,300 Hvilke typer vi si de var på mandag? 84 00:03:25,300 --> 00:03:26,478 Yeah? 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 peker, eller mer spesifikt, en int, for n, 87 00:03:30,721 --> 00:03:32,180 og en peker på bunnen. 88 00:03:32,180 --> 00:03:35,360 Begge disse tilfeldigvis er 32 biter, ved minst på en datamaskin som dette CS50 89 00:03:35,360 --> 00:03:37,980 Apparatet, og slik at de er trukket like i størrelse. 90 00:03:37,980 --> 00:03:42,260 >> Så hva bruker pekeren selv for tilsynelatende? 91 00:03:42,260 --> 00:03:47,690 Hvorfor legge denne pilen nå når arrays var så fint og rent og enkelt? 92 00:03:47,690 --> 00:03:50,460 Hva er pekeren gjør for oss i hver av disse nodene? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [uhørlig]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Nettopp. 95 00:03:52,465 --> 00:03:54,120 Det forteller deg hvor den neste er. 96 00:03:54,120 --> 00:03:57,350 Så jeg liksom bruke analogien ved hjelp av en tråd å sortere av 97 00:03:57,350 --> 00:03:59,180 træ disse nodene sammen. 98 00:03:59,180 --> 00:04:01,760 Og det er akkurat det vi gjør med pekere fordi hver av disse 99 00:04:01,760 --> 00:04:06,360 biter av hukommelsen kan eller ikke kan være sammenhengende, rygg mot rygg mot rygg 100 00:04:06,360 --> 00:04:09,500 innsiden av RAM, fordi hver gang du kalle malloc sier, gi meg nok 101 00:04:09,500 --> 00:04:12,510 byte for en ny node, kan det være her eller det kan være her. 102 00:04:12,510 --> 00:04:13,120 Det kan være her. 103 00:04:13,120 --> 00:04:13,730 Det kan være her. 104 00:04:13,730 --> 00:04:14,640 Du vet bare ikke. 105 00:04:14,640 --> 00:04:17,880 >> Men ved hjelp av pekere i adressene til disse nodene, kan du sy dem 106 00:04:17,880 --> 00:04:22,370 sammen på en måte som ser visuelt som en liste, selv om disse tingene er 107 00:04:22,370 --> 00:04:26,770 spredt ut i hele ett eller dine to eller dine fire gigabyte RAM 108 00:04:26,770 --> 00:04:28,760 innsiden av din egen datamaskin. 109 00:04:28,760 --> 00:04:33,230 >> Så nedsiden, da, en lenket liste er hva? 110 00:04:33,230 --> 00:04:34,670 Hva er en pris vi er tilsynelatende å betale? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [uhørlig]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Mer plass, ikke sant? 113 00:04:36,920 --> 00:04:39,340 Vi har, i dette tilfellet, doblet mengde plass fordi vi har gått 114 00:04:39,340 --> 00:04:43,500 fra 32 bits for hver node, for hver int, så nå 64 bits fordi vi må 115 00:04:43,500 --> 00:04:45,050 holde rundt en peker også. 116 00:04:45,050 --> 00:04:48,860 Du får mer effektivitet hvis struct er større enn dette enkle ting. 117 00:04:48,860 --> 00:04:52,020 Hvis du faktisk har en student inne av disse er et par strenger for 118 00:04:52,020 --> 00:04:55,430 navn og hus, kanskje et ID-nummer, kanskje noen andre felt helt. 119 00:04:55,430 --> 00:04:59,000 >> Så hvis du har en stor nok struct, så kanskje kostnadene for pekeren er 120 00:04:59,000 --> 00:05:00,010 ikke en så big deal. 121 00:05:00,010 --> 00:05:03,570 Dette er en bit av et hjørne i tilfelle at vi lagre en så enkel primitiv 122 00:05:03,570 --> 00:05:04,760 innsiden av lenket liste. 123 00:05:04,760 --> 00:05:05,790 Men her er den samme. 124 00:05:05,790 --> 00:05:08,230 Du definitivt bruke mer minne, men du får 125 00:05:08,230 --> 00:05:08,990 fleksibilitet. 126 00:05:08,990 --> 00:05:12,280 Fordi nå hvis jeg ønsker å legge til et element i begynnelsen av denne listen, 127 00:05:12,280 --> 00:05:14,340 Jeg har til å tildele en ny node. 128 00:05:14,340 --> 00:05:17,180 Og jeg må bare oppdatere dem piler eller annen måte ved å bare flytte 129 00:05:17,180 --> 00:05:17,980 noen tips rundt. 130 00:05:17,980 --> 00:05:20,580 >> Hvis jeg ønsker å sette noe inn i midten av listen, trenger jeg ikke å 131 00:05:20,580 --> 00:05:24,410 presse alle til side som vi gjorde i ukers fortiden med våre frivillige som 132 00:05:24,410 --> 00:05:25,700 representerte en matrise. 133 00:05:25,700 --> 00:05:29,470 Jeg kan bare tildele en ny node og så bare peke pilene i 134 00:05:29,470 --> 00:05:32,290 forskjellige retninger fordi det gjør ikke må forbli i selve 135 00:05:32,290 --> 00:05:35,670 minne en sann linje som jeg har tegnet det her på skjermen. 136 00:05:35,670 --> 00:05:38,400 >> Og så til slutt, hvis du vil sette inn noe ved slutten av listen, er det 137 00:05:38,400 --> 00:05:39,210 enda enklere. 138 00:05:39,210 --> 00:05:43,320 Dette er liksom vilkårlig notasjon, men 34 er pekeren, ta en gjetning. 139 00:05:43,320 --> 00:05:46,710 Hva er verdien av sin pekeren mest sannsynlig trukket liksom som 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 sannsynligvis null. 143 00:05:49,900 --> 00:05:52,710 Og ja det er en forfatters representasjon av null. 144 00:05:52,710 --> 00:05:56,310 Og det er null fordi du absolutt behov for å vite hvor enden av en koblet 145 00:05:56,310 --> 00:06:00,050 listen er, så du holder følgende og følge og følge disse pilene 146 00:06:00,050 --> 00:06:01,170 til noen søppel verdi. 147 00:06:01,170 --> 00:06:06,230 Så null vil markere at det er ingen flere noder til høyre for tallet 34, 148 00:06:06,230 --> 00:06:07,200 i dette tilfellet. 149 00:06:07,200 --> 00:06:10,270 >> Så vi foreslår at vi kan implementere denne noden i koden. 150 00:06:10,270 --> 00:06:12,130 Og vi har sett denne typen av syntaksen før. 151 00:06:12,130 --> 00:06:15,090 Typedef definerer bare en ny type for oss, gir oss et synonym som 152 00:06:15,090 --> 00:06:17,100 streng var for røye *. 153 00:06:17,100 --> 00:06:21,030 I dette tilfellet, det kommer til å gi oss korte notasjonen slik at struct node 154 00:06:21,030 --> 00:06:24,010 kan i stedet bare skrives som node, som er mye renere. 155 00:06:24,010 --> 00:06:25,360 Det er mye mindre detaljert. 156 00:06:25,360 --> 00:06:30,080 >> Innsiden av en node er tilsynelatende en int kalt n, og deretter en struct node * 157 00:06:30,080 --> 00:06:34,670 som betyr nøyaktig hva vi ønsket pilene til å bety, en peker til en annen 158 00:06:34,670 --> 00:06:36,940 node av nøyaktig samme datatype. 159 00:06:36,940 --> 00:06:40,300 Og jeg foreslår at vi kunne gjennomføre en Søkefunksjonen som dette, som på 160 00:06:40,300 --> 00:06:41,890 første øyekast kan virke litt komplisert. 161 00:06:41,890 --> 00:06:43,330 Men la oss se det i sammenheng. 162 00:06:43,330 --> 00:06:45,480 >> La meg gå over til apparatet her. 163 00:06:45,480 --> 00:06:48,460 La meg åpne opp en fil som heter liste null dot h. 164 00:06:48,460 --> 00:06:53,950 Og som bare inneholder definisjonen vi bare så en stund siden for disse dataene 165 00:06:53,950 --> 00:06:55,390 typen kalles en node. 166 00:06:55,390 --> 00:06:57,350 Så vi har satt det inn i en prikk h-fil. 167 00:06:57,350 --> 00:07:01,430 >> Og som en side, selv om dette program som du er i ferd med å se er 168 00:07:01,430 --> 00:07:05,410 ikke så komplisert, det er faktisk konvensjonen når du skriver et program for å 169 00:07:05,410 --> 00:07:10,270 sette ting som datatyper, for å trekke konstanter noen ganger, inne i ditt 170 00:07:10,270 --> 00:07:13,210 header-fil og ikke nødvendigvis i C-fil, sikkert når 171 00:07:13,210 --> 00:07:17,370 programmer får større og større, slik at du vet hvor du skal lete både for 172 00:07:17,370 --> 00:07:20,840 dokumentasjon i noen tilfeller, eller for grunnleggende som dette, de 173 00:07:20,840 --> 00:07:22,360 definisjon av noen type. 174 00:07:22,360 --> 00:07:25,680 >> Hvis jeg nå åpner opp liste null dot c, merke noen ting. 175 00:07:25,680 --> 00:07:29,090 Den inneholder noen header-filer, de fleste som vi har sett før. 176 00:07:29,090 --> 00:07:31,980 Det inkluderer en egen header-fil. 177 00:07:31,980 --> 00:07:35,200 >> Og som en side, hvorfor det er dobbelt sitater her, i motsetning til vinkelen 178 00:07:35,200 --> 00:07:38,340 brakettene på linjen som Jeg har merket det? 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å linje 15, for eksempel, bruker du 182 00:07:44,300 --> 00:07:46,570 de doble anførselstegn i stedet av de vinklede braketter. 183 00:07:46,570 --> 00:07:48,270 >> Nå er dette ganske interessant. 184 00:07:48,270 --> 00:07:51,830 Legg merke til at jeg har erklært en global variabel i dette programmet på linje 18 185 00:07:51,830 --> 00:07:55,910 ringte først, er ideen er dette kommer til å være en peker til den første 186 00:07:55,910 --> 00:07:59,190 node i min lenket liste, og jeg har initialisert det til null, fordi jeg har 187 00:07:59,190 --> 00:08:02,310 ikke tildelt noen faktiske noder ennå. 188 00:08:02,310 --> 00:08:07,570 >> Så dette representerer, billedlig, hva vi så et øyeblikk siden i bildet som 189 00:08:07,570 --> 00:08:10,090 at pekeren på langt venstre side. 190 00:08:10,090 --> 00:08:12,260 Så akkurat nå, som peker ikke har en pil. 191 00:08:12,260 --> 00:08:14,590 Det er i stedet bare null. 192 00:08:14,590 --> 00:08:17,880 Men det viser hva som vil være den adressen til den første faktiske 193 00:08:17,880 --> 00:08:19,480 node i denne listen. 194 00:08:19,480 --> 00:08:22,120 Så jeg har implementert det er en global fordi, som du ser, alt dette 195 00:08:22,120 --> 00:08:25,310 Programmet i livet er å implementere en lenket liste for meg. 196 00:08:25,310 --> 00:08:27,050 >> Nå har jeg fått noen prototyper her. 197 00:08:27,050 --> 00:08:31,190 Jeg bestemte meg for å implementere funksjoner som sletting, innsetting, søking og 198 00:08:31,190 --> 00:08:31,740 traversering - 199 00:08:31,740 --> 00:08:35,210 den siste bare å være spasertur over liste, skrive ut dens elementer. 200 00:08:35,210 --> 00:08:36,750 Og nå her er min viktigste rutine. 201 00:08:36,750 --> 00:08:39,890 Og vi vil ikke bruke for mye tid på disse siden dette er liksom, forhåpentligvis 202 00:08:39,890 --> 00:08:41,780 gammelt hat nå. 203 00:08:41,780 --> 00:08:45,370 >> Jeg kommer til å gjøre følgende, mens brukeren samarbeider. 204 00:08:45,370 --> 00:08:47,300 Så en, kommer jeg til å skrive ut ut denne menyen. 205 00:08:47,300 --> 00:08:49,420 Og jeg har formatert den som en ren, så jeg kunne. 206 00:08:49,420 --> 00:08:52,240 Hvis brukeren skriver i ett, betyr det at de ønsker å slette noe. 207 00:08:52,240 --> 00:08:54,560 Hvis brukeren skriver i to, det betyr de ønsker å sette inn noe. 208 00:08:54,560 --> 00:08:55,930 Og så videre. 209 00:08:55,930 --> 00:08:58,270 Jeg skal da be deretter for en kommando. 210 00:08:58,270 --> 00:08:59,300 Og så jeg kommer til å bruke GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Så dette er en veldig enkel menuing grensesnitt der du bare trenger å skrive 212 00:09:02,790 --> 00:09:05,270 et nummer til en kartlegging av disse kommandoene. 213 00:09:05,270 --> 00:09:08,730 Og nå har jeg en fin clean switch uttalelse som kommer til å slå på 214 00:09:08,730 --> 00:09:10,090 hva brukeren har skrevet i. 215 00:09:10,090 --> 00:09:12,180 Og hvis de skrev en, vil jeg ringe slette og bryte. 216 00:09:12,180 --> 00:09:14,380 Hvis de har skrevet to, vil jeg ringe inn og bryte. 217 00:09:14,380 --> 00:09:16,490 >> Og nå merker jeg har satt hver av disse på samme linje. 218 00:09:16,490 --> 00:09:18,360 Dette er bare en stilistisk avgjørelse. 219 00:09:18,360 --> 00:09:20,210 Vanligvis vi har sett noe som dette. 220 00:09:20,210 --> 00:09:23,260 Men jeg bare bestemte meg, ærlig, mitt program så mer lesbar fordi 221 00:09:23,260 --> 00:09:25,980 det var bare fire saker til bare liste det slik. 222 00:09:25,980 --> 00:09:28,360 Helt legitim bruk av stilen. 223 00:09:28,360 --> 00:09:31,480 Og jeg kommer til å gjøre dette så lenge Brukeren har ikke skrevet null, som jeg 224 00:09:31,480 --> 00:09:33,910 besluttet vil bety at de ønsker å slutte. 225 00:09:33,910 --> 00:09:36,630 >> Så nå merke til hva jeg er kommer til å gjøre her. 226 00:09:36,630 --> 00:09:38,650 Jeg kommer til å frigjøre listen tilsynelatende. 227 00:09:38,650 --> 00:09:40,230 Men mer om det i løpet av et øyeblikk. 228 00:09:40,230 --> 00:09:41,640 La oss først kjøre dette programmet. 229 00:09:41,640 --> 00:09:45,250 Så la meg gjøre en større terminal vindu, dot slash liste 0. 230 00:09:45,250 --> 00:09:49,510 Jeg kommer til å gå videre og sette inn med to typing, et tall som 50, og nå 231 00:09:49,510 --> 00:09:51,590 du vil se listen er nå 50. 232 00:09:51,590 --> 00:09:53,380 Og teksten min bare rullet opp litt. 233 00:09:53,380 --> 00:09:55,940 Så nå merke listen inneholder nummer 50. 234 00:09:55,940 --> 00:09:58,220 >> La oss gjøre en annen innsats ved å ta to. 235 00:09:58,220 --> 00:10:01,630 La oss skrive inn nummeret som en. 236 00:10:01,630 --> 00:10:03,940 Listen er nå en, etterfulgt av 50. 237 00:10:03,940 --> 00:10:06,020 Så dette er bare en tekstlig representasjon av listen. 238 00:10:06,020 --> 00:10:10,550 Og la oss sette inn en flere antall som tallet 42, som er forhåpentligvis 239 00:10:10,550 --> 00:10:14,620 kommer til å ende opp i midten, fordi dette programmet i spesielle former det 240 00:10:14,620 --> 00:10:16,320 elementer som det setter 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 enkelt program som kunne absolutt ha brukt en matrise, men jeg 243 00:10:20,730 --> 00:10:23,280 måtte bruke en lenket 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å la oss ta en titt for søk, hvis jeg kjøre kommandoen tre, jeg ønsker å søke 246 00:10:28,470 --> 00:10:31,040 for, si, nummer 43. 247 00:10:31,040 --> 00:10:34,190 Og ingenting ble tydeligvis funnet, fordi jeg fikk tilbake noe svar. 248 00:10:34,190 --> 00:10:35,010 Så la oss gjøre dette igjen. 249 00:10:35,010 --> 00:10:35,690 Søke. 250 00:10:35,690 --> 00:10:39,520 La oss søke for 50, eller snarere søke henholdsvis 42, som har en fin 251 00:10:39,520 --> 00:10:40,850 lite subtil betydning. 252 00:10:40,850 --> 00:10:42,610 Og jeg fant meningen med livet der. 253 00:10:42,610 --> 00:10:44,990 Number 42, hvis du ikke vet referansen, Google det. 254 00:10:44,990 --> 00:10:45,350 OK. 255 00:10:45,350 --> 00:10:47,130 Så hva har dette programmet gjort for meg? 256 00:10:47,130 --> 00:10:50,660 Det er bare tillatt meg å sette dermed langt og søk etter elementer. 257 00:10:50,660 --> 00:10:53,650 >> La oss spole fremover, da, for å den funksjonen vi kikket 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 funksjonen, hevder jeg, søker etter et element i listen ved første 260 00:10:59,620 --> 00:11:03,830 en, spørre brukeren og deretter ringer GetInt å få en faktisk int 261 00:11:03,830 --> 00:11:05,060 du vil søke etter. 262 00:11:05,060 --> 00:11:06,460 >> Deretter merke til dette. 263 00:11:06,460 --> 00:11:10,690 Jeg kommer til å lage en midlertidig variabel på linje 188 som heter spisser - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 kunne ha kalt det noe. 266 00:11:12,440 --> 00:11:16,140 Og det er en peker til en node fordi jeg sa node * der. 267 00:11:16,140 --> 00:11:19,900 Og jeg klargjør den til å være lik først, slik at jeg effektivt har min 268 00:11:19,900 --> 00:11:22,860 finger, så å si, på den meget første element av listen. 269 00:11:22,860 --> 00:11:27,460 Så hvis min høyre hånd her er PTR jeg er peker på det samme som første 270 00:11:27,460 --> 00:11:28,670 peker på. 271 00:11:28,670 --> 00:11:31,430 >> Så nå tilbake i kode, hva som skjer videre - 272 00:11:31,430 --> 00:11:35,070 dette er en vanlig paradigme ved gjentakelse over en struktur som en 273 00:11:35,070 --> 00:11:35,970 lenket liste. 274 00:11:35,970 --> 00:11:40,410 Jeg kommer til å gjøre følgende mens pekeren er ikke lik null Så mens 275 00:11:40,410 --> 00:11:47,530 min finger peker ikke på noen null verdi, hvis Pekerpilen n er lik n. 276 00:11:47,530 --> 00:11:52,290 Vi vil merke først at n er hva brukeren har skrevet i per GetInts ringe her. 277 00:11:52,290 --> 00:11:54,280 >> Og Pekerpilen n betyr det? 278 00:11:54,280 --> 00:11:59,020 Vel, hvis vi går tilbake til bildet her, hvis jeg har en finger peker på 279 00:11:59,020 --> 00:12:02,960 at første noden som inneholder ni, pil betyr i hovedsak gå til det 280 00:12:02,960 --> 00:12:08,860 node og ta tak i verdien på plasseringen n, I dette tilfellet kalles datafeltet n. 281 00:12:08,860 --> 00:12:14,120 >> Som en side - og vi så denne et par uker siden, da noen spurte - 282 00:12:14,120 --> 00:12:18,840 denne syntaksen er nytt, men det gjør ikke gi oss krefter som vi 283 00:12:18,840 --> 00:12:20,040 ikke allerede har. 284 00:12:20,040 --> 00:12:25,325 Hva var dette uttrykket tilsvarer å bruke dot notasjon og stjerne et par 285 00:12:25,325 --> 00:12:29,490 uker siden da vi skrelles tilbake dette laget litt for tidlig? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [uhørlig]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Akkurat, var det stjerne, og da var det stjerners dot n, med 288 00:12:38,880 --> 00:12:41,930 parentes her, som ser, ærlig, tror jeg mye 289 00:12:41,930 --> 00:12:43,320 mer kryptisk å lese. 290 00:12:43,320 --> 00:12:46,270 Men stjerners pekeren, som alltid, betyr gå dit. 291 00:12:46,270 --> 00:12:49,090 Og når du er der, hvilke data Feltet vil du få tilgang til? 292 00:12:49,090 --> 00:12:52,730 Vel du bruker dot notasjon for å få tilgang en structs data-feltet, og jeg 293 00:12:52,730 --> 00:12:54,140 ønsker spesielt n. 294 00:12:54,140 --> 00:12:56,240 >> Ærlig, vil jeg hevde dette er bare vanskeligere å lese. 295 00:12:56,240 --> 00:12:58,080 Det er vanskeligere å huske hvor trenger parentesene går, jo 296 00:12:58,080 --> 00:12:59,030 stjerners og alt det. 297 00:12:59,030 --> 00:13:02,150 Så verden vedtatt noen syntaktisk sukker, så å si. 298 00:13:02,150 --> 00:13:04,740 Bare en sexy måte å si: Dette er tilsvarende, og 299 00:13:04,740 --> 00:13:05,970 kanskje mer intuitivt. 300 00:13:05,970 --> 00:13:09,600 Hvis pekeren er faktisk en pekeren, arrow notasjon del gå dit og finne 301 00:13:09,600 --> 00:13:11,890 feltet i dette tilfelle kalles n. 302 00:13:11,890 --> 00:13:13,660 >> Så hvis jeg finner den, legge merke til hva jeg gjør. 303 00:13:13,660 --> 00:13:17,430 Jeg ganske enkelt skrive ut, fant jeg prosent i, plugge i verdien for den int. 304 00:13:17,430 --> 00:13:20,730 Jeg kaller sove i ett sekund bare for å kind av pause ting på skjermen for å 305 00:13:20,730 --> 00:13:22,900 gi brukeren en annen for å absorbere hva skjedde. 306 00:13:22,900 --> 00:13:24,290 Og da jeg bryte. 307 00:13:24,290 --> 00:13:26,330 Ellers hva gjør jeg? 308 00:13:26,330 --> 00:13:30,960 Jeg oppdaterer pekeren til lik Pekerpilen neste. 309 00:13:30,960 --> 00:13:35,840 >> Så bare for å være klar, betyr dette gå der, ved hjelp av min gamle skolen notasjon. 310 00:13:35,840 --> 00:13:39,580 Så dette betyr bare å gå til uansett du peker på, som i svært 311 00:13:39,580 --> 00:13:43,660 første tilfellet er jeg peker på struct med ni i den. 312 00:13:43,660 --> 00:13:44,510 Så jeg har gått der. 313 00:13:44,510 --> 00:13:47,880 Og så dot notasjon betyr, få verdien på neste. 314 00:13:47,880 --> 00:13:50,470 >> Men verdien, selv om den er trukket som en smal, er bare et tall. 315 00:13:50,470 --> 00:13:51,720 Det er en numerisk adresse. 316 00:13:51,720 --> 00:13:55,670 Så man denne linjen med kode, enten skrevet som dette, jo mer kryptisk 317 00:13:55,670 --> 00:14:00,190 måte, eller som dette, de litt mer intuitiv måte, betyr bare flytte hånden min 318 00:14:00,190 --> 00:14:03,460 fra den første noden til den neste, og deretter den neste, og deretter 319 00:14:03,460 --> 00:14:05,320 neste, og så videre. 320 00:14:05,320 --> 00:14:09,920 >> Så vi vil ikke dvele ved den andre implementeringer av sette inn og slette 321 00:14:09,920 --> 00:14:14,030 og traversering, de første to av som er ganske involvert. 322 00:14:14,030 --> 00:14:17,010 Og jeg tror det er ganske lett å få tapt når du gjør det verbalt. 323 00:14:17,010 --> 00:14:19,890 Men hva vi kan gjøre her er prøve for å bestemme hvordan 324 00:14:19,890 --> 00:14:21,640 best å gjøre dette visuelt. 325 00:14:21,640 --> 00:14:24,800 Fordi jeg ville foreslå at hvis vi vil sette inn 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 gjennomføre dette i kode, jeg trenger å vurdere hvordan du skal gå 329 00:14:33,300 --> 00:14:34,160 om du gjør dette. 330 00:14:34,160 --> 00:14:37,720 >> Og jeg vil foreslå å ta små steg der, i dette tilfellet jeg mener, hva er 331 00:14:37,720 --> 00:14:41,090 de mulige scenarier som vi kan støte på generelt? 332 00:14:41,090 --> 00:14:44,120 Ved implementering av innsatsen for en koblet listen, så skjer dette bare å være en 333 00:14:44,120 --> 00:14:46,090 spesifikt eksempel på størrelse fem. 334 00:14:46,090 --> 00:14:50,420 Vel, hvis du vil sette inn et tall, liker si nummer én, og 335 00:14:50,420 --> 00:14:53,380 opprettholde sortert rekkefølge, der åpenbart gjør nummer én må 336 00:14:53,380 --> 00:14:55,686 gå i denne konkrete eksempel? 337 00:14:55,686 --> 00:14:56,840 Som i begynnelsen. 338 00:14:56,840 --> 00:15:00,030 >> Men det som er interessant er det at Hvis du ønsker å sette et inn i dette 339 00:15:00,030 --> 00:15:04,100 liste, må det spesielle pekeren å bli oppdatert tilsynelatende? 340 00:15:04,100 --> 00:15:04,610 Først. 341 00:15:04,610 --> 00:15:07,830 Så jeg vil hevde at dette er den første saken at vi kanskje vil vurdere, en 342 00:15:07,830 --> 00:15:11,140 scenario som involverer innsetting på begynnelsen av listen. 343 00:15:11,140 --> 00:15:15,400 >> La oss plukke ut kanskje en så enkel eller lettere fall relativt sett. 344 00:15:15,400 --> 00:15:18,110 Anta ønsker jeg å sette inn nummer 35 i sortert rekkefølge. 345 00:15:18,110 --> 00:15:20,600 Det hører selvsagt der borte. 346 00:15:20,600 --> 00:15:25,320 Så hva pekeren åpenbart kommer til å må oppdateres i det scenarioet? 347 00:15:25,320 --> 00:15:30,060 34 er pekeren blir ikke null men adressen til struct 348 00:15:30,060 --> 00:15:31,800 inneholder nummer 35. 349 00:15:31,800 --> 00:15:32,750 Så det er tilfelle to. 350 00:15:32,750 --> 00:15:36,190 Så allerede, jeg er liksom kvantisering hvor mye arbeid jeg må gjøre her. 351 00:15:36,190 --> 00:15:39,880 >> Og til slutt, er det opplagte midt saken faktisk, i midten, hvis jeg vil 352 00:15:39,880 --> 00:15:45,870 sette inn noe sånt som 23 si, som går mellom 23 til og 26, men 353 00:15:45,870 --> 00:15:48,680 nå ting blir litt mer involvert fordi det 354 00:15:48,680 --> 00:15:52,800 pekere må endres? 355 00:15:52,800 --> 00:15:56,680 Så 22 må åpenbart må endres fordi han ikke kan vise til 26 lenger. 356 00:15:56,680 --> 00:16:00,320 Han trenger å peke på den nye noden som Jeg må fordele ved å ringe 357 00:16:00,320 --> 00:16:01,770 malloc eller noe tilsvarende. 358 00:16:01,770 --> 00:16:05,990 >> Men så må jeg også at ny node, 23 i dette tilfellet, å ha sin pekeren 359 00:16:05,990 --> 00:16:07,870 peker på hvem? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 Og det kommer til å bli en rekkefølgen av operasjoner her. 362 00:16:10,380 --> 00:16:13,410 For hvis jeg gjør dette tåpelig, og jeg for eksempel start ved begynnelsen av 363 00:16:13,410 --> 00:16:16,040 listen, og målet mitt er å sette inn 23. 364 00:16:16,040 --> 00:16:18,610 Og jeg sjekke, hører det her, nær ni? 365 00:16:18,610 --> 00:16:18,950 Nei. 366 00:16:18,950 --> 00:16:20,670 Hører det her, ved siden av 17? 367 00:16:20,670 --> 00:16:20,940 Nei. 368 00:16:20,940 --> 00:16:22,530 Betyr det hører hjemme her ved siden av 22? 369 00:16:22,530 --> 00:16:23,300 Ja. 370 00:16:23,300 --> 00:16:26,400 >> Nå hvis jeg er tåpelig her, og ikke tenker dette gjennom, kanskje jeg 371 00:16:26,400 --> 00:16:28,320 tildele min nye node for 23. 372 00:16:28,320 --> 00:16:32,080 Jeg kan oppdatere pekeren fra noden som kalles 22, peker 373 00:16:32,080 --> 00:16:33,080 det ved den nye noden. 374 00:16:33,080 --> 00:16:36,140 Og hva må jeg oppdatere den nye nodens pekeren å 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: Nettopp. 377 00:16:38,385 --> 00:16:39,710 Peker på 26.. 378 00:16:39,710 --> 00:16:45,590 Men faen om jeg ikke allerede oppdaterer 22 er pekeren å peke på denne fyren, og 379 00:16:45,590 --> 00:16:48,260 nå har jeg foreldreløse, resten av listen, så å si. 380 00:16:48,260 --> 00:16:52,140 Så rekkefølgen av operasjoner her kommer til å være viktig. 381 00:16:52,140 --> 00:16:55,100 >> For å gjøre dette kan jeg stjele, si, seks frivillige. 382 00:16:55,100 --> 00:16:57,650 Og la oss se om vi ikke kan gjøre dette visuelt i stedet for kode-messig. 383 00:16:57,650 --> 00:16:59,330 Og vi har noen herlige stresset baller for deg i dag. 384 00:16:59,330 --> 00:17:02,510 OK, hva med en, to, i tilbake - på slutten der. 385 00:17:02,510 --> 00:17:04,530 tre, fire, begge to gutta på slutten. 386 00:17:04,530 --> 00:17:05,579 Og fem, seks. 387 00:17:05,579 --> 00:17:05,839 Jada. 388 00:17:05,839 --> 00:17:06,450 Fem og seks. 389 00:17:06,450 --> 00:17:08,390 Greit og vi vil komme til dere neste gang. 390 00:17:08,390 --> 00:17:09,640 Greit, kom igjen opp. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Greit, siden du er her oppe først, ønsker du å være en klønete 393 00:17:14,819 --> 00:17:16,119 i Google Glass her? 394 00:17:16,119 --> 00:17:19,075 Ok, så, OK, Glass, spille inn 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 å gå. 397 00:17:24,589 --> 00:17:27,950 >> Ok, så hvis dere kan komme over her har jeg forberedt på forhånd 398 00:17:27,950 --> 00:17:30,110 noen tall. 399 00:17:30,110 --> 00:17:31,240 Greit, kom på over her. 400 00:17:31,240 --> 00:17:33,440 Og hvorfor ikke du går litt videre på den måten. 401 00:17:33,440 --> 00:17:35,520 Og la oss se, hva heter du, 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, bokstavelig talt. 405 00:17:38,380 --> 00:17:40,580 Så vi kommer til å sende deg til slutten av den scene. 406 00:17:40,580 --> 00:17:41,670 Greit, og navnet ditt? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, OK du vil bli nummer ni. 409 00:17:44,530 --> 00:17:46,700 Så hvis du ønsker å følge Ben på den måten. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, du kommer til å være 17, som hvis jeg hadde gjort dette mer 412 00:17:49,630 --> 00:17:51,260 intelligent, ville jeg ha startet i den andre enden. 413 00:17:51,260 --> 00:17:52,370 Du går den veien. 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 navnet ditt 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å til slutt. 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 kommer på over her. 425 00:18:03,920 --> 00:18:06,360 >> All right, så perfekt sortert bestille allerede. 426 00:18:06,360 --> 00:18:09,600 Og la oss gå videre og gjøre dette slik at vi virkelig kan - 427 00:18:09,600 --> 00:18:11,720 Ben du er bare slags jakt ut i intet der. 428 00:18:11,720 --> 00:18:15,670 OK, så la oss gå videre og skildre dette bruker armene, mye som jeg var, akkurat, 429 00:18:15,670 --> 00:18:16,250 hva som skjer. 430 00:18:16,250 --> 00:18:19,540 Så gå videre og gi dere en fot eller to mellom dere. 431 00:18:19,540 --> 00:18:22,900 Og gå videre og peker med den ene hånden til hvem du skal peke på 432 00:18:22,900 --> 00:18:23,470 basert på dette. 433 00:18:23,470 --> 00:18:25,890 Og hvis du er null bare peke rett ned til gulvet. 434 00:18:25,890 --> 00:18:27,690 OK, så bra. 435 00:18:27,690 --> 00:18:32,290 >> Så nå har vi en lenket liste, og la meg foreslår at jeg skal spille rollen som 436 00:18:32,290 --> 00:18:35,110 PTR, så jeg vil ikke bry bærer dette rundt. 437 00:18:35,110 --> 00:18:37,830 Og så - noen dum konvensjonen - du kan kalle dette noe du vil - 438 00:18:37,830 --> 00:18:39,800 forgjenger pekeren, Pred spisser - 439 00:18:39,800 --> 00:18:43,930 det er bare kallenavnet vi ga i vår eksempelkode til min venstre hånd. 440 00:18:43,930 --> 00:18:47,240 Den andre hånden som kommer til å være å holde styr på hvem som er hvem i 441 00:18:47,240 --> 00:18:48,400 følge scenarier. 442 00:18:48,400 --> 00:18:52,390 >> Så vel, først vil jeg rykke ut det første eksempel på å sette inn, sier 443 00:18:52,390 --> 00:18:54,330 20, inn i listen. 444 00:18:54,330 --> 00:18:57,160 Så jeg kommer til å trenge noen til legemliggjøre nummer 20 for oss. 445 00:18:57,160 --> 00:18:58,950 Så jeg trenger å malloc noen fra publikum. 446 00:18:58,950 --> 00:18:59,380 Kom opp. 447 00:18:59,380 --> 00:19:00,340 Hva heter du? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, all right, slik at du skal være den noden som inneholder 20. 450 00:19:05,270 --> 00:19:06,810 Greit, kom på over her. 451 00:19:06,810 --> 00:19:10,025 Og selvsagt, der hører Brian? 452 00:19:10,025 --> 00:19:12,190 Så, i midten av - faktisk vent litt. 453 00:19:12,190 --> 00:19:13,420 Vi gjør dette ut av drift. 454 00:19:13,420 --> 00:19:17,170 Vi gjør dette mye vanskeligere enn den trenger å være først. 455 00:19:17,170 --> 00:19:21,210 OK, vi skal til gratis Brian og realloc Brian som fem. 456 00:19:21,210 --> 00:19:23,680 >> OK, så nå ønsker vi å sette inn Brian som fem. 457 00:19:23,680 --> 00:19:25,960 Så kom igjen over her ved siden av Ben for bare et øyeblikk. 458 00:19:25,960 --> 00:19:28,250 Og du kan antagelig fortelle hvor denne historien går. 459 00:19:28,250 --> 00:19:30,500 Men la oss tenke nøye rekkefølgen av operasjoner. 460 00:19:30,500 --> 00:19:32,880 Og det er nettopp denne visuelle som kommer til å stille opp 461 00:19:32,880 --> 00:19:34,080 med at eksempelkode. 462 00:19:34,080 --> 00:19:40,120 Så her har jeg PTR peker innledningsvis ikke på Ben, per se, men uansett hvilken 463 00:19:40,120 --> 00:19:43,245 setter han inneholder, som i dette tilfellet er - hva heter du igjen? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> 1 SPEAKER: Jason, slik at både Ben og jeg er peker på Jason i dette øyeblikk. 466 00:19:47,350 --> 00:19:49,700 Så nå må jeg bestemme, hvor hører Brian? 467 00:19:49,700 --> 00:19:53,500 Så det eneste jeg har tilgang til akkurat nå er hans n data element. 468 00:19:53,500 --> 00:19:58,280 Så jeg kommer til å sjekke, er Brian mindre enn Jason? 469 00:19:58,280 --> 00:19:59,770 Svaret er sant. 470 00:19:59,770 --> 00:20:03,680 >> Så hva må nå skje, i riktig rekkefølge? 471 00:20:03,680 --> 00:20:07,120 Jeg trenger å oppdatere hvor mange pekere totalt i denne historien? 472 00:20:07,120 --> 00:20:10,720 Hvor min hånd er fremdeles peker på Jason, og hånden din - hvis du vil 473 00:20:10,720 --> 00:20:12,930 legg din hånd som, liksom, jeg vet ikke, et spørsmålstegn. 474 00:20:12,930 --> 00:20:14,070 OK, bra. 475 00:20:14,070 --> 00:20:15,670 >> Ok, så du har noen få kandidater. 476 00:20:15,670 --> 00:20:20,500 Enten Ben eller jeg eller Brian eller Jason eller alle andre, som 477 00:20:20,500 --> 00:20:21,370 pekere må endre? 478 00:20:21,370 --> 00:20:23,260 Hvor mange totalt? 479 00:20:23,260 --> 00:20:24,080 >> OK, så to. 480 00:20:24,080 --> 00:20:27,090 Min pekeren spiller egentlig ingen rolle lenger fordi jeg er bare midlertidig. 481 00:20:27,090 --> 00:20:31,370 Så det er disse to gutta, formodentlig, både Ben og Brian. 482 00:20:31,370 --> 00:20:34,410 Så la meg foreslå at vi oppdaterer Ben, siden han er først. 483 00:20:34,410 --> 00:20:36,350 Det første elementet i denne liste nå kommer til å være Brian. 484 00:20:36,350 --> 00:20:38,070 Så Ben punktet Brian. 485 00:20:38,070 --> 00:20:39,320 OK, hva nå? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Hvem blir pekt 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 å peke på Jason. 490 00:20:46,180 --> 00:20:48,360 Men har jeg mistet oversikten over at pekeren? 491 00:20:48,360 --> 00:20:49,980 Vet jeg 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 gjør, siden jeg er den midlertidige pekeren. 494 00:20:52,620 --> 00:20:55,110 Og antagelig har jeg ikke endret å peke på den nye noden. 495 00:20:55,110 --> 00:20:58,300 Så vi kan rett og slett ha Brian point på hvem jeg peker på. 496 00:20:58,300 --> 00:20:59,000 Og vi er ferdige. 497 00:20:59,000 --> 00:21:01,890 Så fall en, innsetting på begynnelsen av listen. 498 00:21:01,890 --> 00:21:02,950 Det var to viktige skritt. 499 00:21:02,950 --> 00:21:06,750 One, må vi oppdatere Ben, og deretter vi må også oppdatere Brian. 500 00:21:06,750 --> 00:21:09,230 Og så jeg ikke trenger å bry seg traipsing gjennom resten av 501 00:21:09,230 --> 00:21:12,680 liste, fordi vi allerede funnet sin plassering, fordi han tilhørte den 502 00:21:12,680 --> 00:21:14,080 venstre for det første element. 503 00:21:14,080 --> 00:21:15,400 >> Greit, så ganske grei. 504 00:21:15,400 --> 00:21:18,110 Faktisk føles som vi er nesten gjør dette for komplisert. 505 00:21:18,110 --> 00:21:20,240 Så la oss nå nappe av enden av listen, og se hvor 506 00:21:20,240 --> 00:21:21,380 kompleksiteten starter. 507 00:21:21,380 --> 00:21:24,560 Så hvis nå, Alloc jeg fra publikum. 508 00:21:24,560 --> 00:21:25,540 Alle som ønsker å spille 55? 509 00:21:25,540 --> 00:21:26,700 Greit, jeg så hånden først. 510 00:21:26,700 --> 00:21:29,620 Kom opp. 511 00:21:29,620 --> 00:21:30,030 Yeah. 512 00:21:30,030 --> 00:21:31,177 Hva heter du? 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 igjen opp. 516 00:21:33,890 --> 00:21:35,730 Du vil være nummer 55 år. 517 00:21:35,730 --> 00:21:37,820 Så du, selvfølgelig, tilhører ved enden av listen. 518 00:21:37,820 --> 00:21:41,850 Så la oss spille av simulering med meg være PTR for bare et øyeblikk. 519 00:21:41,850 --> 00:21:44,050 Så jeg først kommer til å peke på hva Ben peker på. 520 00:21:44,050 --> 00:21:45,900 Vi er begge peker nå på Brian. 521 00:21:45,900 --> 00:21:48,420 Så 55 er ikke mindre enn fem. 522 00:21:48,420 --> 00:21:52,510 Så jeg kommer til å oppdatere meg selv ved peker til Brians neste pekeren, som 523 00:21:52,510 --> 00:21:54,450 nå er selvfølgelig Jason. 524 00:21:54,450 --> 00:21:57,310 55 er ikke mindre enn ni, så Jeg kommer til å oppdatere PTR. 525 00:21:57,310 --> 00:21:58,890 Jeg kommer til å oppdatere PTR. 526 00:21:58,890 --> 00:22:02,290 Jeg kommer til å oppdatere PTR Jeg kommer til å oppdatere PTR. 527 00:22:02,290 --> 00:22:05,060 Og jeg kommer til å - hmm, hva er navnet ditt igjen? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana peker, selvfølgelig, 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 vet jeg å sette henne her Jeg tror jeg har skrudd opp. 533 00:22:19,460 --> 00:22:22,420 Fordi det er PTR kunst dette øyeblikket i tid? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Så selv om, visuelt, kan vi selvsagt se alle disse 536 00:22:25,580 --> 00:22:26,610 Gutta her på scenen. 537 00:22:26,610 --> 00:22:29,680 Jeg har ikke holdt orden på den forrige person i listen. 538 00:22:29,680 --> 00:22:33,210 Jeg har ikke en finger peker ut, I dette tilfellet noden nummer 34. 539 00:22:33,210 --> 00:22:34,760 >> Så la oss faktisk starte dette over. 540 00:22:34,760 --> 00:22:37,560 Så nå er jeg faktisk trenger en annen lokal variabel. 541 00:22:37,560 --> 00:22:40,980 Og dette er hva du vil se i Selve prøven C-kode, der som jeg går, 542 00:22:40,980 --> 00:22:45,860 når jeg oppdaterer min høyre hånd til å peke Jason, og dermed forlate Brian bak, jeg 543 00:22:45,860 --> 00:22:51,440 bedre begynne å bruke min venstre hånd til oppdatere hvor jeg var, slik at når jeg går 544 00:22:51,440 --> 00:22:52,700 gjennom denne listen - 545 00:22:52,700 --> 00:22:55,040 mer klønete enn jeg ment nå her visuelt - 546 00:22:55,040 --> 00:22:56,740 Jeg kommer til å komme til slutten av listen. 547 00:22:56,740 --> 00:23:00,020 >> Denne hånden er fortsatt null, noe som er ganske ubrukelig, annet enn for å indikere 548 00:23:00,020 --> 00:23:02,980 Jeg er tydelig på slutten av listen, men nå i hvert fall jeg ha denne 549 00:23:02,980 --> 00:23:08,270 forgjenger pekeren peker her, så nå hva hender og hva pekere trenger 550 00:23:08,270 --> 00:23:10,150 å bli oppdatert? 551 00:23:10,150 --> 00:23:13,214 Hvis hånd vil du å konfigurere først? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [uhørlig]. 553 00:23:15,190 --> 00:23:16,220 >> 1 SPEAKER: OK, så Dianas. 554 00:23:16,220 --> 00:23:21,110 Hvor vil du peke Dianas venstre peker på? 555 00:23:21,110 --> 00:23:23,620 55 at, formodentlig slik at vi har satt inn der. 556 00:23:23,620 --> 00:23:25,560 Og hvor skal 55 pekeren gå? 557 00:23:25,560 --> 00:23:27,000 Down, som representerer null. 558 00:23:27,000 --> 00:23:28,890 Og hendene mine, på dette punktet, ikke saken 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å nå er vi ferdige. 561 00:23:31,030 --> 00:23:34,650 >> Så den ekstra kompleksitet der - og det er ikke så vanskelig å implementere, 562 00:23:34,650 --> 00:23:38,660 men vi trenger en sekundær variabel å gjøre sikker på at før jeg flytter min høyre 563 00:23:38,660 --> 00:23:42,140 hånd, oppdaterer jeg verdien av min venstre hånd, pred pekeren i dette tilfellet, så 564 00:23:42,140 --> 00:23:45,860 at jeg har en etterfølgende pekeren å holde styr på hvor jeg var. 565 00:23:45,860 --> 00:23:49,360 Nå som en side, hvis du tenker på dette gjennom, føles dette som om det er en 566 00:23:49,360 --> 00:23:51,490 Litt irriterende å måtte holde spore av denne venstre hånd. 567 00:23:51,490 --> 00:23:54,015 >> Hva ville en annen løsning på dette problemet har vært? 568 00:23:54,015 --> 00:23:56,500 Hvis du fikk til å omstrukturere dataene strukturen vi snakker 569 00:23:56,500 --> 00:23:59,630 gjennom akkurat nå? 570 00:23:59,630 --> 00:24:02,690 Hvis dette bare slags føles litt irriterende å ha, som, to pekere 571 00:24:02,690 --> 00:24:08,430 gå gjennom listen, kan hvem andre har, i en ideell verden, opprettholdes 572 00:24:08,430 --> 00:24:10,160 informasjon som vi trenger? 573 00:24:10,160 --> 00:24:11,360 Yeah? 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: Nettopp. 577 00:24:16,150 --> 00:24:19,130 Høyre, så det er faktisk en interessant spiren til en idé. 578 00:24:19,130 --> 00:24:22,470 Og denne ideen om en tidligere peker, peker på den forrige element. 579 00:24:22,470 --> 00:24:25,580 Hva om jeg bare nedfelt at innsiden av selve listen? 580 00:24:25,580 --> 00:24:27,810 Og det kommer til å være vanskelig å visualisere dette uten alt papiret 581 00:24:27,810 --> 00:24:28,830 falle ned på gulvet. 582 00:24:28,830 --> 00:24:31,860 Men anta at disse gutta brukte både av sine hender til å ha en tidligere 583 00:24:31,860 --> 00:24:35,950 pekeren, og en neste peker, og dermed gjennomføre det vi kaller en dobbelt 584 00:24:35,950 --> 00:24:36,830 lenket liste. 585 00:24:36,830 --> 00:24:41,090 Som ville tillate meg å sortere av spole tilbake, mye lettere uten meg, 586 00:24:41,090 --> 00:24:43,800 programmerer, måtte holde spore manuelt - 587 00:24:43,800 --> 00:24:44,980 virkelig manuelt - 588 00:24:44,980 --> 00:24:47,280 på hvor jeg hadde vært tidligere i listen. 589 00:24:47,280 --> 00:24:48,110 Så vi vil ikke gjøre det. 590 00:24:48,110 --> 00:24:50,950 Vi vil holde det enkelt fordi det er kommer til å komme til en pris, dobbelt så 591 00:24:50,950 --> 00:24:53,450 mye plass for pekere, Hvis du vil ha en ny en. 592 00:24:53,450 --> 00:24:55,760 Men det er faktisk en felles datastruktur kjent som en 593 00:24:55,760 --> 00:24:57,410 dobbelt lenket liste. 594 00:24:57,410 --> 00:25:01,310 >> La oss gjøre det siste eksempel her og sette disse gutta ut av sin elendighet. 595 00:25:01,310 --> 00:25:03,270 Så 20 malloc. 596 00:25:03,270 --> 00:25:05,320 Kom opp fra midtgangen der. 597 00:25:05,320 --> 00:25:06,280 Ok, hva heter du? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [uhørlig]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Sorry? 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 tennes opp. 603 00:25:10,230 --> 00:25:11,910 Du skal være 20. 604 00:25:11,910 --> 00:25:14,720 Du åpenbart kommer til å tilhøre mellom 17 og 22. 605 00:25:14,720 --> 00:25:16,150 Så la meg lære min lekse. 606 00:25:16,150 --> 00:25:18,150 Jeg kommer til å starte pekeren peker på Brian. 607 00:25:18,150 --> 00:25:21,190 Og jeg kommer til å ha min venstre hånd bare oppdatere til Brian som jeg flytter til 608 00:25:21,190 --> 00:25:23,600 Jason, kontroll gjør 20 mindre enn ni? 609 00:25:23,600 --> 00:25:24,060 Nei. 610 00:25:24,060 --> 00:25:25,430 Er 20 mindre enn 17? 611 00:25:25,430 --> 00:25:25,880 Nei. 612 00:25:25,880 --> 00:25:27,450 Er 20 mindre enn 22? 613 00:25:27,450 --> 00:25:28,440 Ja. 614 00:25:28,440 --> 00:25:34,070 Så hva pekere eller hender må endre hvor de peker nå? 615 00:25:34,070 --> 00:25:37,070 >> Så vi kan gjøre 17 peker 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 ønsker vi å peke pekeren nå? 618 00:25:40,080 --> 00:25:41,330 På 22. 619 00:25:41,330 --> 00:25:45,410 Og vi vet hvor 22 er, igjen takk til min midlertidige pekeren. 620 00:25:45,410 --> 00:25:46,760 Så vi er OK der. 621 00:25:46,760 --> 00:25:49,440 Det på grunn av denne mellomlagring Jeg har holdt styr på hvor alle er. 622 00:25:49,440 --> 00:25:55,055 Og nå kan du visuelt gå inn der du tilhører, og nå trenger vi en, to, tre, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stress baller, og en runde med applaus for 624 00:25:58,410 --> 00:25:59,770 disse gutta, hvis vi kunne. 625 00:25:59,770 --> 00:26:00,410 Pent gjort. 626 00:26:00,410 --> 00:26:05,320 >> [APPLAUSE] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: All right. 628 00:26:06,330 --> 00:26:09,860 Og du kan holde bitene av papir som minner. 629 00:26:09,860 --> 00:26:15,930 >> All right, så stol på meg det er mye lettere å gå gjennom det med 630 00:26:15,930 --> 00:26:17,680 mennesker enn det er med selve koden. 631 00:26:17,680 --> 00:26:22,690 Men hva du finner på bare et øyeblikk nå, er det samme - jo takk. 632 00:26:22,690 --> 00:26:23,630 Takk - 633 00:26:23,630 --> 00:26:29,360 er at du vil finne at de samme dataene struktur, en lenket liste, kan faktisk 634 00:26:29,360 --> 00:26:33,200 anvendes som en byggesten for enda mer sofistikerte datastrukturer. 635 00:26:33,200 --> 00:26:37,620 >> Og innse for temaet her er at vi har absolutt innført mer 636 00:26:37,620 --> 00:26:40,060 kompleksiteten i gjennomføringen av denne algoritmen. 637 00:26:40,060 --> 00:26:43,940 Innsetting, og hvis vi gikk gjennom det, sletting og søking, er litt 638 00:26:43,940 --> 00:26:46,660 mer komplisert enn det ble med en matrise. 639 00:26:46,660 --> 00:26:48,040 Men vi få litt dynamikk. 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 igjen, vi betaler en pris for å ha noen ytterligere kompleksitet, både 642 00:26:54,010 --> 00:26:54,910 implementere det. 643 00:26:54,910 --> 00:26:56,750 Og vi gitt opp random access. 644 00:26:56,750 --> 00:27:00,450 Og for å være ærlig, det er ikke noe hyggelig rengjøre lysbilde jeg kan gi deg at 645 00:27:00,450 --> 00:27:03,120 sier her er hvorfor en lenket liste er bedre enn en matrise. 646 00:27:03,120 --> 00:27:04,100 Og la det bli med det. 647 00:27:04,100 --> 00:27:07,520 Fordi temaet repeterte nå, selv mer i de kommende ukene, er 648 00:27:07,520 --> 00:27:10,200 at det ikke nødvendigvis et korrekt svar. 649 00:27:10,200 --> 00:27:13,830 >> Dette er grunnen til at vi har egen akse av design for oppgavesett. 650 00:27:13,830 --> 00:27:17,700 Det vil være svært kontekstavhengig om du vil bruke disse dataene 651 00:27:17,700 --> 00:27:21,750 struktur, eller at man, og det vil avhenge av hva som er viktig for deg i form 652 00:27:21,750 --> 00:27:24,620 av ressurser og kompleksitet. 653 00:27:24,620 --> 00:27:28,830 >> Men la meg foreslå at de ideelle data struktur, den hellige gral, ville være 654 00:27:28,830 --> 00:27:32,200 noe som er konstant tid, uavhengig av hvor mye ting er 655 00:27:32,200 --> 00:27:36,940 inni den, ville ikke det være fantastisk hvis en datastruktur returnert svarene 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 ordet er i stor ordbok. 659 00:27:40,110 --> 00:27:41,550 Eller nei, dette er ikke ordet. 660 00:27:41,550 --> 00:27:43,270 Eller noe slikt problem der. 661 00:27:43,270 --> 00:27:46,360 Vel la oss se om vi kan ikke minst ta et skritt mot dette. 662 00:27:46,360 --> 00:27:50,190 >> La meg foreslå en ny datastruktur som kan brukes til forskjellige ting, 663 00:27:50,190 --> 00:27:52,260 i dette tilfelle kalles en hash tabell. 664 00:27:52,260 --> 00:27:55,590 Og så er vi faktisk tilbake til skotter ved en matrise, i dette tilfellet, og 665 00:27:55,590 --> 00:28:00,550 noe tilfeldig, jeg har tatt dette hash table som en matrise med en slags 666 00:28:00,550 --> 00:28:02,810 todimensjonal matrise - 667 00:28:02,810 --> 00:28:05,410 eller rettere sagt den er avbildet her som en to dimensjonal array - men dette er bare 668 00:28:05,410 --> 00:28:10,770 en matrise av størrelse 26, slik at hvis vi kaller matrisen, bord brakett 669 00:28:10,770 --> 00:28:12,440 null er rektangelet på toppen. 670 00:28:12,440 --> 00:28:15,090 Bordbrakett 25 er rektangelet nederst. 671 00:28:15,090 --> 00:28:18,620 Og dette er hvordan jeg kunne trekke en data struktur der jeg ønsker å lagre 672 00:28:18,620 --> 00:28:19,790 folks navn. 673 00:28:19,790 --> 00:28:24,370 >> Så for eksempel, og jeg vil ikke trekke hele greia her på overhead, hvis jeg 674 00:28:24,370 --> 00:28:29,160 hadde denne tabellen, som jeg nå kommer til å kalle en hash bord, og dette er igjen 675 00:28:29,160 --> 00:28:31,360 plassering null. 676 00:28:31,360 --> 00:28:34,840 Dette her er beliggenheten en, og så videre. 677 00:28:34,840 --> 00:28:37,880 Jeg påstår at jeg ønsker å bruke disse dataene struktur, av hensyn til diskusjonen, 678 00:28:37,880 --> 00:28:42,600 for å lagre folks navn, Alice og Bob og Charlie og andre slike navn. 679 00:28:42,600 --> 00:28:46,110 Så tenk på dette nå som begynnelsen av, sier en ordbok 680 00:28:46,110 --> 00:28:47,520 med mange ord. 681 00:28:47,520 --> 00:28:49,435 De måtte være navn i vårt eksempel her. 682 00:28:49,435 --> 00:28:52,560 Og dette er alt for germane, kanskje, å gjennomføre en stavekontroll, som vi 683 00:28:52,560 --> 00:28:54,400 kanskje for problem satt seks. 684 00:28:54,400 --> 00:28:59,300 >> Så hvis vi har en rekke total størrelse 26 slik at dette er den 25. plassering 685 00:28:59,300 --> 00:29:03,390 på bunnen, og jeg hevder at Alice er det første ordet i ordlisten av 686 00:29:03,390 --> 00:29:07,260 navnene som jeg ønsker å sette inn i RAM, inn i denne datastruktur, hvor er 687 00:29:07,260 --> 00:29:12,480 instinkter som forteller deg at Alices Navnet bør gå i denne tabellen? 688 00:29:12,480 --> 00:29:13,510 >> Vi har 26 alternativer. 689 00:29:13,510 --> 00:29:14,990 Hvor vi ønsker å sette henne? 690 00:29:14,990 --> 00:29:16,200 Vi ønsker henne i braketten null, ikke sant? 691 00:29:16,200 --> 00:29:18,280 En for Alice, la oss kalle det null. 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 å skrive Alice navn her oppe. 694 00:29:22,600 --> 00:29:24,890 Hvis vi deretter sette Bob, hans Navnet 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 igjennom dette datastruktur. 697 00:29:30,500 --> 00:29:32,090 >> Dette er en fantastisk datastruktur. 698 00:29:32,090 --> 00:29:32,730 Hvorfor? 699 00:29:32,730 --> 00:29:37,460 Vel hva er kjøretiden til sette inn et menneskes navn inn i denne 700 00:29:37,460 --> 00:29:39,850 datastruktur akkurat nå? 701 00:29:39,850 --> 00:29:43,702 Gitt at denne tabellen er implementert, virkelig, som en matrise. 702 00:29:43,702 --> 00:29:44,940 Vel det er konstant tid. 703 00:29:44,940 --> 00:29:45,800 Det er rekkefølgen på en. 704 00:29:45,800 --> 00:29:46,360 Hvorfor? 705 00:29:46,360 --> 00:29:48,630 >> Vel hvordan kan du bestemme hvor Alice tilhører? 706 00:29:48,630 --> 00:29:51,000 Du ser på hvilken bokstav i navnet hennes? 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å det, hvis det er en streng, bare ved å se på streng 709 00:29:54,350 --> 00:29:55,200 brakett null. 710 00:29:55,200 --> 00:29:57,110 Så zeroth tegnet i strengen. 711 00:29:57,110 --> 00:29:57,610 Det er lett. 712 00:29:57,610 --> 00:30:00,350 Vi gjorde det i krypto oppdrag uker siden. 713 00:30:00,350 --> 00:30:05,310 Og så når du vet at Alice Brevet er hovedstaden A, kan vi trekke 714 00:30:05,310 --> 00:30:08,160 off 65 eller formue A selv, som gir oss null. 715 00:30:08,160 --> 00:30:10,940 Så nå vet vi at Alice tilhører ved plassering null. 716 00:30:10,940 --> 00:30:14,240 >> Og gitt en peker til disse dataene struktur, av noe slag, hvor lenge varer 717 00:30:14,240 --> 00:30:18,840 det tar meg å finne sted null i en matrise? 718 00:30:18,840 --> 00:30:22,080 Bare ett skritt, akkurat det er konstant tid på grunn av tilfeldig tilgang vi 719 00:30:22,080 --> 00:30:23,780 foreslått var en funksjon av en matrise. 720 00:30:23,780 --> 00:30:28,570 Så kort sagt, å finne ut hva indeksen av Alice navn er, som er i 721 00:30:28,570 --> 00:30:32,610 dette tilfellet er A, eller la oss bare løse at til null, hvor B er en-og C er 722 00:30:32,610 --> 00:30:34,900 to, finne det ut er konstant tid. 723 00:30:34,900 --> 00:30:38,510 Jeg må bare se på sitt første brev, finne ut hvor null er en 724 00:30:38,510 --> 00:30:40,460 matrise er også konstant tid. 725 00:30:40,460 --> 00:30:42,140 Så teknisk sett det er som to skritt nå. 726 00:30:42,140 --> 00:30:43,330 Men det er fortsatt konstant. 727 00:30:43,330 --> 00:30:46,880 Så vi kaller den store O av en, så har vi satt Alice inn i denne tabellen 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 blir naiv her, ikke sant? 730 00:30:50,960 --> 00:30:53,240 Hva hvis det 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 noen andre navn som starter med A. Hvor skal vi sette 733 00:30:57,230 --> 00:31:00,800 som person, ikke sant? 734 00:31:00,800 --> 00:31:03,420 Jeg mener, akkurat nå er det bare tre folk på bordet, så kanskje vi 735 00:31:03,420 --> 00:31:07,490 bør sette Aaron på stedet null en to tre. 736 00:31:07,490 --> 00:31:09,480 >> Høyre, kunne jeg sette A her. 737 00:31:09,480 --> 00:31:13,350 Men så, hvis vi prøver å sette inn David inn denne listen, betyr hvor David reise? 738 00:31:13,350 --> 00:31:15,170 Nå systemet vårt begynner å bryte ned, ikke sant? 739 00:31:15,170 --> 00:31:19,210 Fordi nå David havner her hvis Aaron er faktisk her. 740 00:31:19,210 --> 00:31:23,060 Og så nå dette hele ideen om å ha en ren datastruktur som gir oss 741 00:31:23,060 --> 00:31:28,010 konstant tid innsettinger er ikke lenger konstant tid, fordi jeg må 742 00:31:28,010 --> 00:31:31,240 sjekk, oh, damnit, er noen allerede på Alice beliggenhet. 743 00:31:31,240 --> 00:31:35,320 >> La meg undersøke resten av disse dataene struktur, på jakt etter et sted å sette 744 00:31:35,320 --> 00:31:37,130 noen som Aaron navn. 745 00:31:37,130 --> 00:31:39,390 Og så vil også den starter å ta lineær tid. 746 00:31:39,390 --> 00:31:42,710 Dessuten, hvis du nå ønsker å finne den Aaron i dette datastruktur, og du 747 00:31:42,710 --> 00:31:45,430 sjekk, og Aaron navn er ikke her. 748 00:31:45,430 --> 00:31:47,960 Ideelt sett ville du bare si Arons ikke i datastrukturen. 749 00:31:47,960 --> 00:31:51,530 Men hvis du begynner å lage rom for Aaron der det skulle ha vært en D 750 00:31:51,530 --> 00:31:55,600 eller en E, du, verste fall må sjekke hele datastruktur, i 751 00:31:55,600 --> 00:31:59,480 og da er det tilfaller til noe lineær i størrelsen av bordet. 752 00:31:59,480 --> 00:32:00,920 >> Så all right, jeg skal fikse dette. 753 00:32:00,920 --> 00:32:04,200 Problemet her er at jeg hadde 26 elementer i denne tabellen. 754 00:32:04,200 --> 00:32:05,000 La meg endre det. 755 00:32:05,000 --> 00:32:06,010 Uff da. 756 00:32:06,010 --> 00:32:10,600 La meg endre det slik at heller være av størrelse 26 totalt, merker bunnen 757 00:32:10,600 --> 00:32:12,720 indeks kommer til å endre til n minus en. 758 00:32:12,720 --> 00:32:16,610 Hvis 26 er helt klart for lite for mennesker ' navn, fordi det er tusenvis av 759 00:32:16,610 --> 00:32:20,830 navnene i verden, la oss bare gjøre i 100 eller 1000 eller 10000. 760 00:32:20,830 --> 00:32:22,960 La oss bare bevilge mye mer plass. 761 00:32:22,960 --> 00:32:27,230 >> Vel som ikke nødvendigvis redusere sannsynligheten for at vi ikke vil ha to 762 00:32:27,230 --> 00:32:31,510 folk med navn som starter med A, og så, skulle du prøve å sette en 763 00:32:31,510 --> 00:32:33,120 navn på stedet null fortsatt. 764 00:32:33,120 --> 00:32:36,850 De er fortsatt kommer til å kollidere, noe som betyr at vi fortsatt trenger en løsning å sette 765 00:32:36,850 --> 00:32:41,020 Alice og Aron og Alicia og andre navn som starter med A andre steder. 766 00:32:41,020 --> 00:32:43,460 Men hvor mye av et problem er dette? 767 00:32:43,460 --> 00:32:46,870 Hva er sannsynligheten for at du har kollisjoner i en data 768 00:32:46,870 --> 00:32:48,240 struktur som dette? 769 00:32:48,240 --> 00:32:52,570 >> Vel, la meg - vi vil komme tilbake på det spørsmålet 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 La meg trekke opp dette forslaget her. 772 00:32:58,480 --> 00:33:02,020 Hva vi nettopp beskrev er en algoritme, en heuristisk kalt lineær 773 00:33:02,020 --> 00:33:05,030 sondering der, hvis du prøvde å sette inn noe her i disse dataene 774 00:33:05,030 --> 00:33:08,920 struktur, som kalles en hash tabell, og det er ikke plass der, du 775 00:33:08,920 --> 00:33:12,000 virkelig sondere datastruktur kontroll, er dette tilgjengelig? 776 00:33:12,000 --> 00:33:13,430 Dette Tilgjengelig er dette tilgjengelig? 777 00:33:13,430 --> 00:33:13,980 Er dette tilgjengelig? 778 00:33:13,980 --> 00:33:17,550 Og når det endelig er, setter du den nevne at du opprinnelig ment 779 00:33:17,550 --> 00:33:19,370 andre steder på den plasseringen. 780 00:33:19,370 --> 00:33:23,360 Men i verste fall, den eneste flekk kan være den aller bunnen av data 781 00:33:23,360 --> 00:33:25,090 struktur, helt på slutten av tabellen. 782 00:33:25,090 --> 00:33:30,130 >> Så lineær sondering, i verste fall, tilfaller i en lineær algoritme hvor 783 00:33:30,130 --> 00:33:34,500 Aaron, hvis han tilfeldigvis settes inn sist i denne datastruktur, kanskje han 784 00:33:34,500 --> 00:33:39,540 kolliderer med denne første plasseringen, men deretter avslutte med uflaks helt på slutten. 785 00:33:39,540 --> 00:33:43,940 Så dette er ikke en konstant tid hellige gral for oss. 786 00:33:43,940 --> 00:33:47,650 Denne tilnærmingen av å sette inn elementer inn en datastruktur kalt en hash 787 00:33:47,650 --> 00:33:52,050 tabell ser ikke ut til å være konstant tid i det minste ikke i det generelle tilfellet. 788 00:33:52,050 --> 00:33:54,000 Det kan tilfalle til noe lineær. 789 00:33:54,000 --> 00:33:56,970 >> Så hva om vi løse kollisjoner noe annerledes? 790 00:33:56,970 --> 00:34:00,740 Så her er en mer sofistikert tilnærming til hva som fortsatt er 791 00:34:00,740 --> 00:34:02,800 kalles en hash table. 792 00:34:02,800 --> 00:34:05,890 Og etter hasj, som en side, hva Jeg mener er den indeksen som 793 00:34:05,890 --> 00:34:07,070 Jeg refererte til tidligere. 794 00:34:07,070 --> 00:34:09,810 Til hasj noe kan være tenkt som et verb. 795 00:34:09,810 --> 00:34:13,690 >> Så hvis du hash Alice er et navn, en hash-funksjon, så å si, 796 00:34:13,690 --> 00:34:14,710 skal returnere et tall. 797 00:34:14,710 --> 00:34:18,199 I dette tilfelle er null hvis hun hører til null beliggenhet, en hvis hun hører på 798 00:34:18,199 --> 00:34:20,000 sted en, og så videre. 799 00:34:20,000 --> 00:34:24,360 Så min hash-funksjon så langt har vært super enkelt, bare å se på 800 00:34:24,360 --> 00:34:26,159 første bokstaven i noens navn. 801 00:34:26,159 --> 00:34:29,090 Men en hash-funksjon tar som innspill noen stykke data, en 802 00:34:29,090 --> 00:34:30,210 string, en int, uansett. 803 00:34:30,210 --> 00:34:32,239 Og den spytter ut vanligvis et tall. 804 00:34:32,239 --> 00:34:35,739 Og at antallet er der at data element hører hjemme i en datastruktur 805 00:34:35,739 --> 00:34:37,800 kjent her som en hash table. 806 00:34:37,800 --> 00:34:41,400 >> Så bare intuitivt, er dette en litt annen sammenheng. 807 00:34:41,400 --> 00:34:44,170 Dette faktisk henviser til et eksempel involverer bursdager, der 808 00:34:44,170 --> 00:34:46,850 det kan være så mange som 31 dager i måneden. 809 00:34:46,850 --> 00:34:52,239 Men hva gjorde denne personen bestemmer seg for å gjøre i tilfelle av en kollisjon? 810 00:34:52,239 --> 00:34:55,304 Kontekst nå være, ikke en kollisjon mellom navn, men en kollisjon på fødselsdager, 811 00:34:55,304 --> 00:35:00,760 hvis to mennesker har samme bursdag på 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 utnytte av lenkede lister. 814 00:35:05,010 --> 00:35:07,830 Så det ser litt annerledes enn vi trakk det tidligere. 815 00:35:07,830 --> 00:35:10,790 Men vi ser ut til å ha til en matrise på den venstre side. 816 00:35:10,790 --> 00:35:13,230 Det er en indeks, for ingen spesiell grunn. 817 00:35:13,230 --> 00:35:14,630 Men det er fortsatt en matrise. 818 00:35:14,630 --> 00:35:16,160 Det er en rekke pekere. 819 00:35:16,160 --> 00:35:20,670 Og hver av disse elementer, og hver av disse sirklene eller skråstreker - skråstreken 820 00:35:20,670 --> 00:35:23,970 representerer null - hver av disse pekere er tilsynelatende peker til 821 00:35:23,970 --> 00:35:25,730 hva datastruktur? 822 00:35:25,730 --> 00:35:26,890 En lenket liste. 823 00:35:26,890 --> 00:35:30,530 >> Så nå har vi muligheten til å hardt kode i vårt program 824 00:35:30,530 --> 00:35:32,010 størrelsen av bordet. 825 00:35:32,010 --> 00:35:35,360 I dette tilfellet vet vi at det er aldri mer enn 31 dager i en måned. 826 00:35:35,360 --> 00:35:38,480 Så vanskelig koding en verdi som 31 er rimelig i denne sammenheng. 827 00:35:38,480 --> 00:35:42,700 I sammenheng med navn, hard koding 26 er ikke urimelig det folks 828 00:35:42,700 --> 00:35:46,340 bare navn begynner med, for eksempel, alfabetet involverer A til Z. 829 00:35:46,340 --> 00:35:50,180 >> Vi kan stappe dem alle i at data struktur så lenge, når vi får en 830 00:35:50,180 --> 00:35:55,330 kollisjon, kan vi ikke sette navnene her, vi i stedet tenker på disse cellene 831 00:35:55,330 --> 00:36:00,270 ikke som strengene selv, men som pekere til, for eksempel, Alice. 832 00:36:00,270 --> 00:36:03,660 Og så Alice kan ha en annen pekeren til et annet navn som starter med 833 00:36:03,660 --> 00:36:06,150 A. Og Bob faktisk går over her. 834 00:36:06,150 --> 00:36:10,850 >> Og hvis det er et annet navn som starter med B, ender han opp over her. 835 00:36:10,850 --> 00:36:15,070 Og slik at hver av delene av denne tabell to, hvis vi utviklet dette til en 836 00:36:15,070 --> 00:36:17,350 litt mer smart - 837 00:36:17,350 --> 00:36:18,125 come on - 838 00:36:18,125 --> 00:36:22,950 hvis vi laget denne litt mer smart, blir nå en adaptiv data 839 00:36:22,950 --> 00:36:27,720 struktur, hvor det er ingen hard grense av hvor mange elementer du kan sette inn 840 00:36:27,720 --> 00:36:30,700 inn i det fordi hvis du har en kollisjon, er det fint. 841 00:36:30,700 --> 00:36:34,690 Bare gå videre og legge den til hva vi så litt siden var 842 00:36:34,690 --> 00:36:38,290 kjent som en lenket liste. 843 00:36:38,290 --> 00:36:39,690 >> Vel la oss stoppe opp et lite øyeblikk. 844 00:36:39,690 --> 00:36:42,570 Hva er sannsynligheten for en kollisjon i første omgang? 845 00:36:42,570 --> 00:36:45,480 Høyre, kanskje jeg å tenke over, kanskje Jeg er over Engineering Dette problemet, 846 00:36:45,480 --> 00:36:46,370 fordi du vet hva? 847 00:36:46,370 --> 00:36:49,070 Ja, jeg kan komme opp med vilkårlig eksempler av toppen av hodet mitt som 848 00:36:49,070 --> 00:36:52,870 Allison og Aron, men i virkeligheten, gitt en jevn fordeling av 849 00:36:52,870 --> 00:36:56,990 innganger, som er noen tilfeldige innsettinger inn i en datastruktur, hva er egentlig 850 00:36:56,990 --> 00:36:58,580 sannsynligheten for en kollisjon? 851 00:36:58,580 --> 00:37:01,670 Vel viser seg, er det faktisk super høy. 852 00:37:01,670 --> 00:37:03,850 La meg generalisere dette Problemet er som dette. 853 00:37:03,850 --> 00:37:08,890 >> Så på et rom av n CS50 studenter, hva er sannsynligheten for at minst 854 00:37:08,890 --> 00:37:11,010 to studenter i rommet har samme bursdag? 855 00:37:11,010 --> 00:37:13,346 Så det er hva. noen hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 mennesker her og flere hundre folk hjemme i dag. 857 00:37:16,790 --> 00:37:20,670 Så hvis du ønsker å spørre oss selv hva som er sannsynligheten for to personer 858 00:37:20,670 --> 00:37:23,930 i dette rommet som har samme bursdag, vi kan finne ut av dette. 859 00:37:23,930 --> 00:37:26,250 Og jeg hevder faktisk det er to personer med samme fødselsdag. 860 00:37:26,250 --> 00:37:29,560 >> For eksempel er det noen som har bursdag 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 All right, så det føles som jeg kommer til å gjøre dette 363 eller så mer 864 00:37:35,980 --> 00:37:39,500 ganger for å faktisk finne ut hvis vi har en kollisjon. 865 00:37:39,500 --> 00:37:42,350 Eller vi kan bare gjøre dette matematisk snarere enn ordinært 866 00:37:42,350 --> 00:37:43,200 gjør dette. 867 00:37:43,200 --> 00:37:44,500 Og foreslår følgende. 868 00:37:44,500 --> 00:37:48,740 >> Så jeg foreslår at vi kunne modellere Sannsynligheten for to mennesker som har det 869 00:37:48,740 --> 00:37:55,320 samme fødselsdag som sannsynligheten for en minus sannsynligheten for at ingen har 870 00:37:55,320 --> 00:37:56,290 samme fødselsdag. 871 00:37:56,290 --> 00:37:59,960 Så for å få dette, og dette er bare fancy måte å skrive dette, for 872 00:37:59,960 --> 00:38:03,090 første personen i rommet, han eller hun kan ha en hvilken som helst en av de mulige 873 00:38:03,090 --> 00:38:07,370 bursdager forutsatt 365 dager i året, med unnskyldninger til personer med 874 00:38:07,370 --> 00:38:08,760 februar 29 bursdag. 875 00:38:08,760 --> 00:38:13,470 >> Så den første personen i dette rommet er gratis å ha en rekke bursdager 876 00:38:13,470 --> 00:38:18,280 ut av den 365, slik at mulighetene vi vil gjøre at 365 delt på 365, 877 00:38:18,280 --> 00:38:18,990 som er en. 878 00:38:18,990 --> 00:38:22,700 Den neste personen i rommet, hvis målet er å unngå en kollisjon, kan bare 879 00:38:22,700 --> 00:38:26,460 har hans eller hennes bursdag på hvordan mange forskjellige mulige dager? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Så det andre leddet i dette uttrykket er hovedsak gjør at regnestykket for oss 882 00:38:31,430 --> 00:38:33,460 ved å trekke ut en mulig dag. 883 00:38:33,460 --> 00:38:36,390 Og så den neste dag, neste dag, Neste dag ned til det totale antallet 884 00:38:36,390 --> 00:38:38,100 av mennesker i rommet. 885 00:38:38,100 --> 00:38:41,290 >> Og hvis vi da vurdere, hva er da sannsynligheten ikke fra alle har 886 00:38:41,290 --> 00:38:45,265 unike bursdager, men igjen en minus det, hva vi får er et uttrykk 887 00:38:45,265 --> 00:38:47,810 som kan veldig fancifully se slik ut. 888 00:38:47,810 --> 00:38:50,330 Men det er mer interessant å se på visuelt. 889 00:38:50,330 --> 00:38:55,120 Dette er et diagram der på x-aksen er antall personer i rommet, 890 00:38:55,120 --> 00:38:56,180 antall fødselsdager. 891 00:38:56,180 --> 00:38:59,840 På y-aksen er sannsynligheten av en kollisjon, to personer 892 00:38:59,840 --> 00:39:01,230 har samme fødselsdag. 893 00:39:01,230 --> 00:39:05,020 >> Og takeaway fra denne kurven er at så snart du kommer til å like 40 894 00:39:05,020 --> 00:39:11,110 studenter, er du opp i en 90% sannsynlighet combinatorically av to 895 00:39:11,110 --> 00:39:13,550 personer eller mer har samme fødselsdag. 896 00:39:13,550 --> 00:39:18,600 Og når du kommer til å like 58 mennesker er det nesten 100% av en sjanse de to 897 00:39:18,600 --> 00:39:21,310 personer i rommet skal ha samme fødselsdag, selv om det er 898 00:39:21,310 --> 00:39:26,650 365 eller 366 mulige bøtter, og bare 58 personer i rommet. 899 00:39:26,650 --> 00:39:29,900 Bare statistisk du sannsynligvis til å få kollisjoner, som kort fortalt 900 00:39:29,900 --> 00:39:31,810 motiverer denne diskusjonen. 901 00:39:31,810 --> 00:39:35,890 At selv om vi får fancy her, og begynner å ha disse kjedene, er vi fremdeles 902 00:39:35,890 --> 00:39:36,950 nødt til kollisjoner. 903 00:39:36,950 --> 00:39:42,710 >> Så det ber spørsmålet, hva er kostnadene ved å gjøre innsettinger og slettinger 904 00:39:42,710 --> 00:39:44,850 inn i en datastruktur som dette? 905 00:39:44,850 --> 00:39:46,630 Vel la meg foreslå - 906 00:39:46,630 --> 00:39:51,570 og la meg gå tilbake til skjermen over her - hvis vi har n elementer i 907 00:39:51,570 --> 00:39:56,330 liste, så hvis vi prøver å sette inn n elementer, og vi har 908 00:39:56,330 --> 00:39:58,050 hvor mange totalt bøtter? 909 00:39:58,050 --> 00:40:03,450 La oss si 31 totalt bøtter i tilfelle av fødselsdager. 910 00:40:03,450 --> 00:40:09,240 Hva er den maksimale lengden på en av disse kjedene potensielt? 911 00:40:09,240 --> 00:40:12,670 >> Hvis det er det altså 31 mulige bursdager i en gitt måned. 912 00:40:12,670 --> 00:40:14,580 Og vi er bare klumper 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 La oss gjøre 26 i stedet. 915 00:40:16,960 --> 00:40:20,890 Så hvis faktisk har folk som har navn starter med A til Z, og dermed gi 916 00:40:20,890 --> 00:40:22,780 oss 26 muligheter. 917 00:40:22,780 --> 00:40:25,920 Og vi bruker en datastruktur som den vi nettopp så, hvor vi har 918 00:40:25,920 --> 00:40:30,210 en rekke pekere, hvorav hver enkelt peker på en lenket liste der 919 00:40:30,210 --> 00:40:32,360 første listen er alle med navnet Alice. 920 00:40:32,360 --> 00:40:35,770 Den andre listen er alle med navn som starter med A, fra 921 00:40:35,770 --> 00:40:36,980 med B, og så videre. 922 00:40:36,980 --> 00:40:41,020 >> Hva den sannsynlige lengden av hvert disse listene hvis vi antar en fin ren 923 00:40:41,020 --> 00:40:45,410 fordeling av navnene A til Z på tvers av hele datastrukturen? 924 00:40:45,410 --> 00:40:50,210 Det er n mennesker i datastruktur delt på 26, hvis de er pent 925 00:40:50,210 --> 00:40:52,110 spredt ut langs hele datastruktur. 926 00:40:52,110 --> 00:40:54,970 Slik at lengden av hver av disse kjedene er n delt på 26. 927 00:40:54,970 --> 00:40:57,380 Men i store O notasjon, hva er det? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Hva er det egentlig? 930 00:41:02,440 --> 00:41:04,150 Så det er egentlig bare n, ikke sant? 931 00:41:04,150 --> 00:41:06,620 Fordi vi har sagt i det siste, at ugh du deler med 26. 932 00:41:06,620 --> 00:41:08,710 Ja, i virkeligheten er det raskere. 933 00:41:08,710 --> 00:41:12,720 Men i teorien, det er ikke fundamentalt alt raskere. 934 00:41:12,720 --> 00:41:16,040 >> Slik at vi ikke ser ut til å være så mye nærmere dette hellige gral. 935 00:41:16,040 --> 00:41:17,750 Faktisk er dette bare lineær tid. 936 00:41:17,750 --> 00:41:20,790 Heck, på dette punktet, hvorfor gjør ikke vi bare bruke en stor lenket liste? 937 00:41:20,790 --> 00:41:23,510 Hvorfor kan ikke vi bare bruke en stor array til å lagre navnene 938 00:41:23,510 --> 00:41:25,010 alle i rommet? 939 00:41:25,010 --> 00:41:28,280 Vel, er det fortsatt noe overbevisende om en hash table? 940 00:41:28,280 --> 00:41:30,810 Er det fortsatt noe overbevisende om en datastruktur 941 00:41:30,810 --> 00:41:33,940 som ser ut som 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: Høyre, og igjen hvis det er bare en lineær tid algoritme, og en 945 00:41:39,840 --> 00:41:42,780 lineær tid datastruktur, hvorfor gjør ikke jeg bare lagre alles navn i en stor 946 00:41:42,780 --> 00:41:44,210 matrise, eller i en stor lenket liste? 947 00:41:44,210 --> 00:41:47,010 Og slutte å lage CS så mye vanskeligere enn den trenger å være? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Hva er overbevisende om dette, selv selv om jeg klødde det ut? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [uhørlig]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: Innsettinger ikke? 952 00:41:57,040 --> 00:41:58,140 Dyrt lenger. 953 00:41:58,140 --> 00:42:03,390 Så innsettinger potensielt kunne fortsatt være konstant tid, selv om dataene 954 00:42:03,390 --> 00:42:07,910 Strukturen ser ut som dette, en rekke pekere er hver av hvilke peker mot 955 00:42:07,910 --> 00:42:09,550 potensielt en lenket liste. 956 00:42:09,550 --> 00:42:15,220 Hvordan kan du oppnå konstant tid innsetting av navn? 957 00:42:15,220 --> 00:42:16,280 Stikke den i fronten, ikke sant? 958 00:42:16,280 --> 00:42:19,290 >> Hvis vi ofrer et design mål fra tidligere, hvor vi ønsket å holde 959 00:42:19,290 --> 00:42:22,650 alles navn, for eksempel, sorteres eller alle av tallene på scenen sortert, 960 00:42:22,650 --> 00:42:25,020 anta at vi har en usortert lenket liste. 961 00:42:25,020 --> 00:42:29,960 Det koster bare oss ett eller to trinn, som i tilfellet med Ben og Brian 962 00:42:29,960 --> 00:42:32,750 tidligere, for å sette inn et element på begynnelsen av listen. 963 00:42:32,750 --> 00:42:36,090 Så hvis vi ikke bryr seg om sortering alle av de navn som starter med A eller alle 964 00:42:36,090 --> 00:42:39,660 navnene som begynner på B, kan vi likevel oppnå konstant tid innsetting. 965 00:42:39,660 --> 00:42:43,900 Nå ser opp Alice eller Bob eller navn mer generelt er fortsatt hva? 966 00:42:43,900 --> 00:42:48,100 Det er stor O n delt på 26, i ideell sak der alle er jevnt 967 00:42:48,100 --> 00:42:51,190 distribuert, hvor det er så mange As som det er Z, som sannsynligvis 968 00:42:51,190 --> 00:42:52,220 urealistisk. 969 00:42:52,220 --> 00:42:53,880 Men det er fortsatt lineær. 970 00:42:53,880 --> 00:42:57,120 >> Men her kommer vi tilbake til det punktet av asymptotisk notasjon være 971 00:42:57,120 --> 00:42:58,600 teoretisk sant. 972 00:42:58,600 --> 00:43:02,960 Men i den virkelige verden, hvis hevder jeg at mitt program kan gjøre noe 26 ganger 973 00:43:02,960 --> 00:43:06,210 raskere enn din, hvis program skal du foretrekker å bruke? 974 00:43:06,210 --> 00:43:09,660 Yours eller mine, som er 26 ganger raskere? 975 00:43:09,660 --> 00:43:14,320 Realistisk, er den personen som 26 ganger raskere, selv om det teoretisk 976 00:43:14,320 --> 00:43:18,790 at algoritmene løpe i samme asymptotisk kjøretid. 977 00:43:18,790 --> 00:43:20,940 >> La meg foreslå en annen løsning helt. 978 00:43:20,940 --> 00:43:24,380 Og hvis dette ikke blåse ditt sinn, vi er ute av 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 dumt navn. 981 00:43:28,520 --> 00:43:32,880 Det kommer fra uttak, og ordet er stavet trie, t-r-i-e, på grunn av 982 00:43:32,880 --> 00:43:34,450 Kurset henting høres ut som trie. 983 00:43:34,450 --> 00:43:36,580 Men det er historie av ordet trie. 984 00:43:36,580 --> 00:43:40,980 >> Så en trie er faktisk noen slags tre, og det er også en spiller på det ordet. 985 00:43:40,980 --> 00:43:46,330 Og selv om du ikke helt kan se det med denne visualiseringen, er et en trie 986 00:43:46,330 --> 00:43:50,790 tre strukturert, som en familie tre med en stamfar på toppen og masse 987 00:43:50,790 --> 00:43:54,530 av barnebarn og oldebarn som blader på bunnen. 988 00:43:54,530 --> 00:43:58,100 Men hver node i et trie er en matrise. 989 00:43:58,100 --> 00:44:00,680 Og det er i en matrise - og la oss oversimplify for et øyeblikk - det er en 990 00:44:00,680 --> 00:44:04,600 matrise, i dette tilfellet, av størrelse 26, hvor hver node er igjen en matrise av størrelse 991 00:44:04,600 --> 00:44:09,000 26, hvor zeroth element i det matrise Å representerer, og den siste 992 00:44:09,000 --> 00:44:11,810 element i hvert slikt matrise representerer Z. 993 00:44:11,810 --> 00:44:15,520 >> Så jeg foreslår da at disse dataene struktur, kjent som en trie, kan bli 994 00:44:15,520 --> 00:44:17,600 brukes også til å lagre ord. 995 00:44:17,600 --> 00:44:21,740 Vi så et øyeblikk siden hvor vi kunne lagre ord, eller i dette tilfellet navnene, og vi 996 00:44:21,740 --> 00:44:25,440 så tidligere hvordan vi kan lagre numre, men hvis vi fokuserer på navn eller strenger 997 00:44:25,440 --> 00:44:27,460 her, legge merke til hva som er interessant. 998 00:44:27,460 --> 00:44:32,210 Jeg hevder at navnet Maxwell er innsiden av 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å hva er interessant med disse dataene Strukturen er stedet lagre det 1003 00:44:39,910 --> 00:44:46,200 streng M-A-X-W-E-L-L skråstrek null, alt contiguously, hva du i stedet gjøre 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 som datastruktur hver av nodene som er igjen en matrise, 1006 00:44:50,510 --> 00:44:54,650 og du vil lagre Maxwell, må du først indeks og så root sin node, så 1007 00:44:54,650 --> 00:44:57,810 å snakke, den øverste node, ved plassering M, til høyre, så 1008 00:44:57,810 --> 00:44:59,160 omtrent i midten. 1009 00:44:59,160 --> 00:45:03,740 Og derfra, følger du en pekeren til et barn noder, så å si. 1010 00:45:03,740 --> 00:45:06,150 Så i ditt tre forstand, du følger den nedover. 1011 00:45:06,150 --> 00:45:09,030 Og som fører deg til en annen node til venstre der, som er 1012 00:45:09,030 --> 00:45:10,540 bare en annen array. 1013 00:45:10,540 --> 00:45:14,710 >> Og så hvis du ønsker å lagre Maxwell, du finner pekeren som representerer 1014 00:45:14,710 --> 00:45:16,430 A, er hvor denne her. 1015 00:45:16,430 --> 00:45:17,840 Så går du til neste node. 1016 00:45:17,840 --> 00:45:20,100 Og legg merke til - dette er grunnen til at bildets litt villedende - 1017 00:45:20,100 --> 00:45:21,990 denne noden ser super bittesmå. 1018 00:45:21,990 --> 00:45:26,050 Men til høyre for denne er Y og Z. Det er bare forfatteren har avkortet den 1019 00:45:26,050 --> 00:45:27,630 bilde, slik at du faktisk se ting. 1020 00:45:27,630 --> 00:45:30,400 Ellers er dette bildet ville være enormt stort. 1021 00:45:30,400 --> 00:45:36,180 Så nå indeksen i sted X, deretter W, så E, deretter L, da L. Så hva er 1022 00:45:36,180 --> 00:45:37,380 denne nysgjerrigheten? 1023 00:45:37,380 --> 00:45:41,250 >> Vel, hvis vi bruker denne typen ny ta om hvordan du lagrer en streng i en 1024 00:45:41,250 --> 00:45:44,500 datastruktur, du fortsatt trenger å hovedsak krysse av i data 1025 00:45:44,500 --> 00:45:47,250 struktur som et ord slutter her. 1026 00:45:47,250 --> 00:45:50,830 Med andre ord, hver av disse nodene en eller annen måte må huske på at vi 1027 00:45:50,830 --> 00:45:53,500 faktisk fulgt alle disse pekerne og drar litt 1028 00:45:53,500 --> 00:45:58,370 brød smule på bunnen av dette her for å indikere hvilken 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 gjøre dette på følgende måte. 1031 00:46:02,040 --> 00:46:06,810 Hver av nodene i bildet vi bare Sagen har en, en rekke størrelse 27. 1032 00:46:06,810 --> 00:46:10,550 Og det er nå 27, fordi i p satt seks, vi vil faktisk gi deg en apostrof, 1033 00:46:10,550 --> 00:46:13,590 slik at vi kan ha navn som O'Reilly og andre med apostrofer. 1034 00:46:13,590 --> 00:46:14,820 Men samme idé. 1035 00:46:14,820 --> 00:46:17,710 Hvert av disse elementer i array-peker til en struct 1036 00:46:17,710 --> 00:46:19,320 node, så bare en node. 1037 00:46:19,320 --> 00:46:21,430 Så dette er veldig minner av vår lenket liste. 1038 00:46:21,430 --> 00:46:24,550 >> Og så har jeg en boolsk, som jeg vil ringe ordet, som bare kommer til å være 1039 00:46:24,550 --> 00:46:29,120 sant hvis et ord slutter på dette node i treet. 1040 00:46:29,120 --> 00:46:32,870 Det representerer effektivt den lille trekant vi så for et øyeblikk siden. 1041 00:46:32,870 --> 00:46:37,190 Så hvis et ord slutter på at node i treet, vil det ordet feltet være sant, 1042 00:46:37,190 --> 00:46:41,990 som er konseptuelt krysse av, eller vi trekker denne trekanten, ja det 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 nå er spørsmålet, hva er kjøretiden? 1046 00:46:48,540 --> 00:46:49,930 Er det stort O av n? 1047 00:46:49,930 --> 00:46:51,410 Er det noe annet? 1048 00:46:51,410 --> 00:46:57,330 Vel, hvis du har n navnene på disse dataene struktur, Maxwell blir bare én av 1049 00:46:57,330 --> 00:47:02,330 dem, hva er kjøretiden til innsetting eller finne Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Hva er kjøretiden med å sette Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Hvis det er n andre navn allerede i tabellen? 1053 00:47:11,740 --> 00:47:12,507 Yeah? 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 lengden av navnet, ikke sant? 1056 00:47:17,550 --> 00:47:24,420 Så M-en-x-w-e-l-l så det føles som dette algoritmen er big O på syv. 1057 00:47:24,420 --> 00:47:26,580 Nå, selvfølgelig, navnet vil variere i lengde. 1058 00:47:26,580 --> 00:47:27,380 Kanskje det er et kort navn. 1059 00:47:27,380 --> 00:47:28,600 Kanskje det er en lengre navn. 1060 00:47:28,600 --> 00:47:33,390 Men det som er viktig her er at det er et konstant tall. 1061 00:47:33,390 --> 00:47:36,810 Og kanskje det er egentlig ikke konstant, men gud, hvis realistisk, i en 1062 00:47:36,810 --> 00:47:41,570 ordbok, er det sannsynligvis noen grense på antallet bokstaver i en 1063 00:47:41,570 --> 00:47:43,820 personens navn i et bestemt land. 1064 00:47:43,820 --> 00:47:46,940 >> Og så kan vi anta at Verdien er en konstant. 1065 00:47:46,940 --> 00:47:47,750 Jeg vet ikke hva det er. 1066 00:47:47,750 --> 00:47:50,440 Det er trolig større enn vi tror det er. 1067 00:47:50,440 --> 00:47:52,720 Fordi det er alltid noen hjørne tilfelle med en gal langt navn. 1068 00:47:52,720 --> 00:47:56,360 Så la oss kalle det k, men det er fortsatt et konstant formodentlig, fordi hver 1069 00:47:56,360 --> 00:48:00,190 navn i verden, i hvert fall i en bestemt land, er at lengden eller 1070 00:48:00,190 --> 00:48:01,780 kortere, slik at den er konstant. 1071 00:48:01,780 --> 00:48:04,490 Men når vi har sagt noe er stort O av en konstant verdi, hva er det 1072 00:48:04,490 --> 00:48:07,760 egentlig tilsvarer? 1073 00:48:07,760 --> 00:48:10,420 Det er egentlig det samme som å si konstant tid. 1074 00:48:10,420 --> 00:48:11,530 >> Nå er vi litt juks, ikke sant? 1075 00:48:11,530 --> 00:48:15,340 Vi er på en måte å utnytte noen teori her å si at vel, er rekkefølgen på k 1076 00:48:15,340 --> 00:48:17,450 egentlig bare bestille ett, og det er konstant tid. 1077 00:48:17,450 --> 00:48:18,200 Men det er virkelig. 1078 00:48:18,200 --> 00:48:22,550 Fordi det her er viktig innsikt at Hvis vi har observert N navnene allerede i denne 1079 00:48:22,550 --> 00:48:26,010 datastruktur, og vi insert Maxwell, er hvor lang tid det tar oss til 1080 00:48:26,010 --> 00:48:29,530 Sett Maxwell i det hele tatt berørte av hvor mange andre mennesker 1081 00:48:29,530 --> 00:48:31,100 er i datastruktur? 1082 00:48:31,100 --> 00:48:31,670 Synes ikke å være. 1083 00:48:31,670 --> 00:48:36,280 Hvis jeg hadde en milliard flere elementer i denne trie, og deretter sette Maxwell, er 1084 00:48:36,280 --> 00:48:38,650 han i det hele tatt berørt? 1085 00:48:38,650 --> 00:48:39,050 Nei. 1086 00:48:39,050 --> 00:48:42,950 Og det er i motsetning til noen av dagen data strukturer vi har sett så langt, hvor 1087 00:48:42,950 --> 00:48:46,820 kjøretiden til algoritmen din er helt uavhengig av hvor mye 1088 00:48:46,820 --> 00:48:51,430 ting er eller ikke allerede ved at datastrukturen. 1089 00:48:51,430 --> 00:48:54,650 >> Og så med dette gir deg er nå en mulighet for p seks sett, som vil 1090 00:48:54,650 --> 00:48:58,310 igjen innebære å implementere din egen stavekontroll, lesing i 150.000 1091 00:48:58,310 --> 00:49:01,050 ord, hvordan best å lagre det er ikke nødvendigvis åpenbar. 1092 00:49:01,050 --> 00:49:04,030 Og selv om jeg har håpet på å finne den hellige gral, vet jeg ikke 1093 00:49:04,030 --> 00:49:05,330 hevder at en trie er. 1094 00:49:05,330 --> 00:49:09,810 Faktisk en hash tabell kan godt vise seg å være mye mer effektiv. 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 av design beslutninger du må gjøre. 1097 00:49:14,620 --> 00:49:18,920 >> Men i avsluttende la oss ta 50 eller så sekunder for å ta en titt på hva som ligger 1098 00:49:18,920 --> 00:49:22,190 videre neste uke og utover vi overgang fra denne kommandolinjen 1099 00:49:22,190 --> 00:49:26,220 verden hvis C programmer til ting web basert og språk som PHP og 1100 00:49:26,220 --> 00:49:30,350 JavaScript og selve Internett, protokoller som HTTP, som du har satt 1101 00:49:30,350 --> 00:49:32,870 tatt for gitt i årevis nå, og skrevet de fleste hver 1102 00:49:32,870 --> 00:49:34,440 dag, kanskje, eller sett. 1103 00:49:34,440 --> 00:49:37,420 Og vi begynner å skrelle tilbake lag av hva er internett. 1104 00:49:37,420 --> 00:49:40,650 Og hva er koden som ligger til grunn for dagens verktøy. 1105 00:49:40,650 --> 00:49:43,230 Så 50 sekunder av denne teaseren her. 1106 00:49:43,230 --> 00:49:46,570 Jeg gir deg Warriors of the Net. 1107 00:49:46,570 --> 00:49:51,370 >> [VIDEOAVSPILLING] 1108 00:49:51,370 --> 00:49:56,764 >> -Han kom med et budskap. 1109 00:49:56,764 --> 00:50:00,687 Med en protokoll all sin egen. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Han kom til en verden av grusom brannmurer, uncaring rutere, og farer langt 1112 00:50:19,780 --> 00:50:22,600 verre enn døden. 1113 00:50:22,600 --> 00:50:23,590 Han er rask. 1114 00:50:23,590 --> 00:50:25,300 Han er sterk. 1115 00:50:25,300 --> 00:50:27,700 Han er TCPIP. 1116 00:50:27,700 --> 00:50:30,420 Og han har adressen din. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Warriors of Net. 1119 00:50:34,590 --> 00:50:35,290 >> [END VIDEOAVSPILLING] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: Det er hvordan internett skal arbeide med neste uke. 1121 00:50:38,070 --> 00:50:40,406