1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [Musikk spilles] 3 00:00:11,137 --> 00:00:12,220 DAVID J. MALAN: All right. 4 00:00:12,220 --> 00:00:13,950 Dette er CS50. 5 00:00:13,950 --> 00:00:18,560 Dette er uke fem fortsatte, og vi har noen gode nyheter og noen dårlige nyheter. 6 00:00:18,560 --> 00:00:21,140 Så gode nyheten er at CS50 lanserer denne fredagen. 7 00:00:21,140 --> 00:00:24,430 Hvis du ønsker å bli med oss, hodet til den vanlige URL her. 8 00:00:24,430 --> 00:00:28,670 Enda bedre nyheter, ingen forelesning kommende mandag den 13.. 9 00:00:28,670 --> 00:00:31,970 Litt mindre bedre nyheter, quiz null er neste onsdag. 10 00:00:31,970 --> 00:00:33,840 Flere detaljer kan være finnes på denne nettadressen her. 11 00:00:33,840 --> 00:00:36,340 Og i løpet av de neste par dagene vi skal fylle de tomme feltene 12 00:00:36,340 --> 00:00:39,234 med hensyn til rommene at vi vil har reservert. 13 00:00:39,234 --> 00:00:41,400 Bedre nyheter er at det vil være et kurs-wide gjennomgang 14 00:00:41,400 --> 00:00:43,570 sesjon denne kommende Mandag i kveld. 15 00:00:43,570 --> 00:00:46,270 Stay tuned til kursets Nettside for plassering og detaljer. 16 00:00:46,270 --> 00:00:49,290 Seksjoner, selv om det er en ferie, vil også møte også. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Beste nyheten, foredrag neste fredag. 19 00:00:52,940 --> 00:00:56,220 Så dette er en tradisjon vi har, i henhold til pensum. 20 00:00:56,220 --> 00:00:58,100 Just-- det kommer til å bli fantastisk. 21 00:00:58,100 --> 00:01:02,510 Du vil se ting som konstant tidsdatastrukturer 22 00:01:02,510 --> 00:01:04,730 og hash tabeller og trær og prøver. 23 00:01:04,730 --> 00:01:07,150 Og vi skal snakke om bursdags problemer. 24 00:01:07,150 --> 00:01:09,440 En hel haug med ting venter neste fredag. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 OK. 27 00:01:12,200 --> 00:01:13,190 Anyhow. 28 00:01:13,190 --> 00:01:17,080 >> Så husker at vi har vært fokus på dette bildet av hva som er 29 00:01:17,080 --> 00:01:18,980 innsiden av våre datamaskinens minne. 30 00:01:18,980 --> 00:01:22,875 Så minne eller RAM er der programmene eksistere mens du kjører dem. 31 00:01:22,875 --> 00:01:25,215 Hvis du dobbeltklikker en ikonet for å kjøre noen program 32 00:01:25,215 --> 00:01:27,520 eller dobbeltklikk på et ikonet for å åpne noen fil, 33 00:01:27,520 --> 00:01:30,430 det er lastet fra hard stasjonen eller Solid State-stasjonen 34 00:01:30,430 --> 00:01:34,190 inn i RAM, Random Access Memory, der det lever til strømmen er av, 35 00:01:34,190 --> 00:01:36,700 laptop lokket lukkes, eller du avslutter programmet. 36 00:01:36,700 --> 00:01:38,960 >> Nå som minne, av som du sikkert har 37 00:01:38,960 --> 00:01:41,950 1 gigabyte i disse dager, 2 GB, eller enda mer, 38 00:01:41,950 --> 00:01:44,420 er generelt lagt ut for et gitt program 39 00:01:44,420 --> 00:01:47,170 i denne typen rektangulær konseptuell modell 40 00:01:47,170 --> 00:01:50,860 hvorved vi har stabelen på bunnen og en haug med andre ting på toppen. 41 00:01:50,860 --> 00:01:53,140 Saken på toppen vi har sett på dette bildet 42 00:01:53,140 --> 00:01:55,670 før, men aldri snakket om er den såkalte tekstsegment. 43 00:01:55,670 --> 00:01:58,419 Tekstsegment er bare en fancy måte si nuller og enere som 44 00:01:58,419 --> 00:02:01,150 komponere din faktiske kompilert program. 45 00:02:01,150 --> 00:02:03,910 >> Så når du dobbeltklikker Microsoft Word på Mac eller PC, 46 00:02:03,910 --> 00:02:08,030 eller når du kjører dot slash Mario på en Linux-datamaskin i ditt terminalvindu, 47 00:02:08,030 --> 00:02:12,460 nuller og enere som komponerer Word eller Mario lagres midlertidig 48 00:02:12,460 --> 00:02:16,610 i datamaskinens RAM i den såkalte tekstsegment for et bestemt program. 49 00:02:16,610 --> 00:02:19,080 Nedenfor som går initialisert og uinitialiserte data. 50 00:02:19,080 --> 00:02:22,655 Dette er ting som globale variabler, at vi ikke har brukt mange av, 51 00:02:22,655 --> 00:02:24,910 men noen ganger har vi hadde globale variabler 52 00:02:24,910 --> 00:02:28,819 eller statisk definert strenger som er hardkodet ord som "hallo" 53 00:02:28,819 --> 00:02:31,860 som ikke er tatt inn fra brukeren som er hardkodet inn i programmet. 54 00:02:31,860 --> 00:02:34,230 >> Nå, ned på bunnen vi har den såkalte stabelen. 55 00:02:34,230 --> 00:02:37,665 Og bunken, så langt, vi har vært bruker for hva slags formål? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 Hva er bunken blitt brukt til? 58 00:02:40,997 --> 00:02:41,160 Yeah? 59 00:02:41,160 --> 00:02:42,070 >> Målgruppe: funksjoner. 60 00:02:42,070 --> 00:02:43,320 >> DAVID J. MALAN: For funksjoner? 61 00:02:43,320 --> 00:02:44,980 I hvilken forstand for funksjoner? 62 00:02:44,980 --> 00:02:48,660 >> PUBLIKUM: Når du ringer en funksjon, den Argumentene er kopiert på stakken. 63 00:02:48,660 --> 00:02:49,660 >> DAVID J. MALAN: Nettopp. 64 00:02:49,660 --> 00:02:52,650 Når du ringer en funksjon, dens Argumentene er kopiert på stakken. 65 00:02:52,650 --> 00:02:56,330 Så noen X-eller Y-eller A-eller B at du sender inn en funksjon 66 00:02:56,330 --> 00:02:58,680 er midlertidig satt på den såkalte stabel, 67 00:02:58,680 --> 00:03:02,000 akkurat som en av Annenberg Dining Hall skuffer, og også ting 68 00:03:02,000 --> 00:03:03,190 som lokale variabler. 69 00:03:03,190 --> 00:03:06,290 Hvis foo funksjon eller swap funksjonen har lokale variabler, 70 00:03:06,290 --> 00:03:08,602 som temp, de to ende opp på stakken. 71 00:03:08,602 --> 00:03:11,560 Nå vil vi ikke snakke for mye om dem, men disse miljøvariabler 72 00:03:11,560 --> 00:03:15,690 på bunnen vi så en stund siden, da Jeg ble futzing på tastaturet en dag 73 00:03:15,690 --> 00:03:20,050 og jeg begynte å få tilgang til ting som argv 100 eller argv 1000, 74 00:03:20,050 --> 00:03:22,320 bare elements-- jeg glemmer den numbers-- men at 75 00:03:22,320 --> 00:03:24,330 skulle ikke nås av meg. 76 00:03:24,330 --> 00:03:26,581 Vi begynte å se noen funky symboler på skjermen. 77 00:03:26,581 --> 00:03:28,330 De var såkalte miljøvariabler 78 00:03:28,330 --> 00:03:32,390 som globale innstillinger for min program eller for min datamaskin, ikke 79 00:03:32,390 --> 00:03:37,090 relatert til den siste bug som vi snakket om, 80 00:03:37,090 --> 00:03:39,670 Shellshock, som har vært plager ganske mange datamaskiner. 81 00:03:39,670 --> 00:03:42,960 >> Nå til slutt, i dagens fokus Vi vil til slutt være på haugen. 82 00:03:42,960 --> 00:03:44,864 Dette er en annen del av minnet. 83 00:03:44,864 --> 00:03:47,030 Og fundamentalt alt dette minnet er de samme tingene. 84 00:03:47,030 --> 00:03:48,040 Det er den samme maskinvaren. 85 00:03:48,040 --> 00:03:49,956 Vi er bare en slags behandling av ulike klynger 86 00:03:49,956 --> 00:03:51,460 byte for ulike formål. 87 00:03:51,460 --> 00:03:56,540 Haugen er også kommer til å være der variabler og minne som du ber om 88 00:03:56,540 --> 00:03:58,810 fra operativsystemet lagres midlertidig. 89 00:03:58,810 --> 00:04:01,890 >> Men det er litt av et problem her, som i bildet innebærer. 90 00:04:01,890 --> 00:04:05,261 Vi liksom ha to skip om å kollidere. 91 00:04:05,261 --> 00:04:08,010 Fordi som du bruker mer og mer av stabelen, og som vi ser i dag 92 00:04:08,010 --> 00:04:11,800 videre, som du bruker mer og mer av haugen, sikkert dårlige ting kan skje. 93 00:04:11,800 --> 00:04:15,054 Og ja, vi kan indusere at bevisst eller ubevisst. 94 00:04:15,054 --> 00:04:16,970 Så cliffhanger siste gang var dette programmet, 95 00:04:16,970 --> 00:04:20,570 som ikke tjener noen funksjonell annet formål enn å demonstrere 96 00:04:20,570 --> 00:04:24,750 hvordan du som bad guy kan faktisk ta nytte av bugs i noens program 97 00:04:24,750 --> 00:04:28,460 og ta over et program eller en hele datasystemet eller server. 98 00:04:28,460 --> 00:04:31,660 Så bare å titte kort, du Legg merke til at hoved nederst 99 00:04:31,660 --> 00:04:34,510 tar i kommandolinjen argumenter, som per argv. 100 00:04:34,510 --> 00:04:38,480 Og den har et kall til en funksjon f, egentlig en navnløs funksjon kalt 101 00:04:38,480 --> 00:04:40,250 f, og det er forbikjøring i argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Så uansett hva ordet brukeren taster inn på ledeteksten etter dette programmets navn, 103 00:04:43,960 --> 00:04:49,310 og så denne vilkårlig funksjon opp toppen, f, tar i en streng, AKA char *, 104 00:04:49,310 --> 00:04:51,720 som vi har begynt å diskutere, og det bare kaller det "bar". 105 00:04:51,720 --> 00:04:53,310 Men vi kan kalle det noe. 106 00:04:53,310 --> 00:04:57,470 Og så erklærer inne av f, en rekke tegn 107 00:04:57,470 --> 00:04:59,930 kalt C-- 12 slike tegn. 108 00:04:59,930 --> 00:05:03,580 >> Nå, etter den historien jeg fortalte et øyeblikk siden, hvor i minnet 109 00:05:03,580 --> 00:05:06,720 er c, eller er de 12 chars kommer til å ende opp? 110 00:05:06,720 --> 00:05:07,570 Bare for å være klar. 111 00:05:07,570 --> 00:05:08,070 Yeah? 112 00:05:08,070 --> 00:05:08,590 >> PUBLIKUM: På stabelen. 113 00:05:08,590 --> 00:05:09,420 >> DAVID J. MALAN: På stabelen. 114 00:05:09,420 --> 00:05:10,720 Så c er en lokal variabel. 115 00:05:10,720 --> 00:05:14,079 Vi ber om 12 tegn eller 12 bytes. 116 00:05:14,079 --> 00:05:16,120 De kommer til å ende opp på den såkalte stabelen. 117 00:05:16,120 --> 00:05:18,530 Nå endelig er denne annen funksjon det er faktisk ganske nyttig, 118 00:05:18,530 --> 00:05:20,571 men vi har egentlig ikke brukt det selv, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 Det betyr streng kopi, men bare n bokstaver, n tegn. 121 00:05:25,200 --> 00:05:31,990 Så n tegn vil være kopiert fra bar til c. 122 00:05:31,990 --> 00:05:32,980 Og hvor mange? 123 00:05:32,980 --> 00:05:34,110 Lengden på bar. 124 00:05:34,110 --> 00:05:36,330 Så med andre ord, at én linje, strncopy, 125 00:05:36,330 --> 00:05:39,500 kommer til å kopiere effektivt bar i til c. 126 00:05:39,500 --> 00:05:42,340 >> Nå, bare for å slags forutse Moralen i denne historien, 127 00:05:42,340 --> 00:05:44,750 hva er potensielt problematisk her? 128 00:05:44,750 --> 00:05:49,710 Selv om vi sjekker lengden av bar og føre det inn i strncopy, 129 00:05:49,710 --> 00:05:53,145 hva er din gut forteller deg er fremdeles ødelagt om dette programmet? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Yeah? 132 00:05:55,220 --> 00:05:57,491 >> PUBLIKUM: Inkluderer ikke rom for nulltegn. 133 00:05:57,491 --> 00:05:59,990 DAVID J. MALAN: Inkluderer ikke rom for nulltegn. 134 00:05:59,990 --> 00:06:02,073 Potensielt, i motsetning til i tidligere praksis vi ikke engang 135 00:06:02,073 --> 00:06:04,810 har så mye som et pluss 1 til imøtekomme den null karakter. 136 00:06:04,810 --> 00:06:06,649 Men det er enda verre enn det. 137 00:06:06,649 --> 00:06:07,940 Hva annet skal vi unnlate å gjøre? 138 00:06:07,940 --> 00:06:08,432 Yeah? 139 00:06:08,432 --> 00:06:09,307 >> PUBLIKUM: [uhørbart] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 DAVID J. MALAN: Perfect. 142 00:06:16,440 --> 00:06:18,490 Vi har hardkodet 12 ganske vilkårlig. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 Det er ikke så mye problem, men faktum 145 00:06:21,330 --> 00:06:25,630 at vi ikke engang å sjekke om lengden på baren er mindre enn 12, 146 00:06:25,630 --> 00:06:28,530 i så fall kommer det til å være trygt å sette det inn i minnet 147 00:06:28,530 --> 00:06:30,260 kalt c at vi har tildelt. 148 00:06:30,260 --> 00:06:32,960 Faktisk, hvis bar er som 20 tegn lang, 149 00:06:32,960 --> 00:06:39,010 denne funksjon synes å være å kopiere 20 tegn fra bar til c, og dermed 150 00:06:39,010 --> 00:06:41,310 tar minst 8 byte at det ikke skal være. 151 00:06:41,310 --> 00:06:42,690 Det er implikasjonen her. 152 00:06:42,690 --> 00:06:44,347 >> Så kort sagt, ødelagte program. 153 00:06:44,347 --> 00:06:45,180 Ikke en så stor avtale. 154 00:06:45,180 --> 00:06:46,360 Kanskje du får en segmentering feil. 155 00:06:46,360 --> 00:06:47,651 Vi har alle hatt bugs i programmer. 156 00:06:47,651 --> 00:06:50,196 Vi alle kan ha bugs i programmer akkurat nå. 157 00:06:50,196 --> 00:06:51,320 Men hva er implikasjonen? 158 00:06:51,320 --> 00:06:54,390 Vel, her er en zoomet inn versjonen av det bildet av min datamaskinens minne. 159 00:06:54,390 --> 00:06:56,230 Dette er bunnen av bunken min. 160 00:06:56,230 --> 00:06:59,644 Og ja, helt nederst er det som er kalt forelder rutine stack, fancy måte 161 00:06:59,644 --> 00:07:00,560 å si at det viktigste. 162 00:07:00,560 --> 00:07:03,772 Slik at den som kalles funksjonen f som vi snakker om. 163 00:07:03,772 --> 00:07:05,230 Så dette er bunnen av bunken. 164 00:07:05,230 --> 00:07:06,640 Returadressen er noe nytt. 165 00:07:06,640 --> 00:07:08,810 Det har alltid vært der, alltid vært i det bildet. 166 00:07:08,810 --> 00:07:10,440 Vi kalte bare aldri oppmerksomhet til det. 167 00:07:10,440 --> 00:07:15,290 Fordi det blir slik vi c fungerer er at når en funksjonskall hverandre 168 00:07:15,290 --> 00:07:18,780 ikke bare gjør argumentene til at funksjon bli skjøvet inn på stabelen, 169 00:07:18,780 --> 00:07:22,470 ikke bare gjøre funksjonens lokale variablene bli skjøvet inn på stabelen, 170 00:07:22,470 --> 00:07:26,820 noe som kalles en returadresse også blir satt på stakken. 171 00:07:26,820 --> 00:07:33,330 Nærmere bestemt, hvis viktigste samtalene foo, da hoved sin egen adresse i minnet, okse noe, 172 00:07:33,330 --> 00:07:38,240 effektivt blir satt på stakken slik at når f er gjort utfører det 173 00:07:38,240 --> 00:07:43,630 vet hvor du skal hoppe tilbake til i teksten segmentet for å kunne fortsette å utføre. 174 00:07:43,630 --> 00:07:47,760 >> Så hvis vi er her konseptuelt, i hoved, deretter f blir kalt. 175 00:07:47,760 --> 00:07:50,200 Hvordan f vite hvem til håndkontrollen tilbake? 176 00:07:50,200 --> 00:07:52,020 Vel, denne lille brødsmule i rødt her, 177 00:07:52,020 --> 00:07:54,978 kalt returadresse, det bare sjekker, hva er det returadresse? 178 00:07:54,978 --> 00:07:57,039 Å, la meg hoppe tilbake til hoved her. 179 00:07:57,039 --> 00:07:59,080 Og det er litt av en overforenkling, 180 00:07:59,080 --> 00:08:00,750 fordi de nuller og enere for hoved er teknisk 181 00:08:00,750 --> 00:08:01,967 her oppe i tech-segmentet. 182 00:08:01,967 --> 00:08:03,800 Men det er tanken. f bare må vite hva 183 00:08:03,800 --> 00:08:06,680 til der kontroll til slutt går tilbake. 184 00:08:06,680 --> 00:08:09,790 >> Men måten datamaskiner har lenge lagt ut ting 185 00:08:09,790 --> 00:08:12,320 som lokale variabler og Argumentene er som dette. 186 00:08:12,320 --> 00:08:17,180 Så på toppen av dette bildet i blått er stabelen rammen for f, så alt 187 00:08:17,180 --> 00:08:19,630 av minnet som f spesifikt er bruker. 188 00:08:19,630 --> 00:08:22,990 Så tilsvarende, legge merke til at Baren er i dette bildet. 189 00:08:22,990 --> 00:08:23,980 Bar var sitt argument. 190 00:08:23,980 --> 00:08:27,240 Og vi hevdet at argumentene til funksjoner bli skjøvet inn på stabelen. 191 00:08:27,240 --> 00:08:29,910 Og c, er selvfølgelig også i dette bildet. 192 00:08:29,910 --> 00:08:33,520 >> Og bare for notasjonsmessig, merke øverst i venstre hjørne 193 00:08:33,520 --> 00:08:37,020 er hva som ville være c brakett 0 og så litt ned mot høyre 194 00:08:37,020 --> 00:08:38,220 er c brakett 11. 195 00:08:38,220 --> 00:08:41,240 Så med andre ord, kan du forestille deg at det er et rutenett av bytes 196 00:08:41,240 --> 00:08:44,380 Det første av disse er Øverst til venstre bunnen av som 197 00:08:44,380 --> 00:08:48,360 er den siste av disse 12 bytes. 198 00:08:48,360 --> 00:08:49,930 >> Men nå prøve å spole fremover. 199 00:08:49,930 --> 00:08:55,580 Hva er i ferd med å skje hvis vi passerer i en streng søyle som er lengre enn c? 200 00:08:55,580 --> 00:08:59,130 Og vi er ikke å sjekke om det er faktisk lengre enn 12 år. 201 00:08:59,130 --> 00:09:03,146 Som en del av dette bildet kommer til å bli overskrevet av byte 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 dot dot dot, 11, og deretter dårlig, 12, 13 til 19? 203 00:09:07,890 --> 00:09:11,820 Hva kommer til å skje her, hvis du slutte fra bestilling 204 00:09:11,820 --> 00:09:14,790 at c brakett 0 er på toppen og c brakett 11 er liksom ned 205 00:09:14,790 --> 00:09:15,812 til høyre? 206 00:09:15,812 --> 00:09:16,796 Yeah? 207 00:09:16,796 --> 00:09:19,260 >> PUBLIKUM: Vel, det kommer å overskrive char * bar. 208 00:09:19,260 --> 00:09:22,260 >> DAVID J. MALAN: Ja, det ser ut som du kommer til å overskrive char * bar. 209 00:09:22,260 --> 00:09:26,245 Og enda verre, hvis du sender i en veldig lang streng, kan du selv overskrive hva? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 Returadressen. 212 00:09:28,570 --> 00:09:31,380 Som igjen er akkurat som en brødsmule å fortelle programmet hvor 213 00:09:31,380 --> 00:09:34,060 å gå tilbake til når f gjøres å bli kalt. 214 00:09:34,060 --> 00:09:37,140 >> Så hva skurkene vanligvis gjør er hvis de kommer over et program 215 00:09:37,140 --> 00:09:41,290 at de er nysgjerrig på om er utnyttes, buggy på en slik måte 216 00:09:41,290 --> 00:09:43,550 at han eller hun kan ta nytte av at bug, 217 00:09:43,550 --> 00:09:45,720 generelt de ikke får dette riktig første gang. 218 00:09:45,720 --> 00:09:48,590 De nettopp begynner å sende, f.eks tilfeldige strenger inn i programmet, 219 00:09:48,590 --> 00:09:50,260 enten på tastaturet, eller ærlig de trolig 220 00:09:50,260 --> 00:09:52,740 skrive et lite program for å bare automatisk generere strenger, 221 00:09:52,740 --> 00:09:55,430 og begynne banging på programmet ved sender i mange forskjellige innganger 222 00:09:55,430 --> 00:09:56,340 ved forskjellige lengder. 223 00:09:56,340 --> 00:09:58,990 >> Så snart programmet krasjer, det er en fantastisk ting. 224 00:09:58,990 --> 00:10:01,020 Fordi det betyr at han eller hun har oppdaget 225 00:10:01,020 --> 00:10:02,660 det som sannsynligvis er faktisk en bug. 226 00:10:02,660 --> 00:10:05,830 Og så de kan få mer smart og begynne å fokusere mer snevert 227 00:10:05,830 --> 00:10:07,420 om hvordan du kan utnytte at bug. 228 00:10:07,420 --> 00:10:11,480 Spesielt hva han eller hun kan gjøre er å sende, i beste fall, hallo. 229 00:10:11,480 --> 00:10:12,210 Ingen big deal. 230 00:10:12,210 --> 00:10:14,750 Det er en streng som er tilstrekkelig kort. 231 00:10:14,750 --> 00:10:18,100 Men hva hvis han eller hun sender, og vi vil generalisere det som, 232 00:10:18,100 --> 00:10:20,890 angrep code-- så nuller og de som gjør ting 233 00:10:20,890 --> 00:10:25,150 som rm-rf, som fjerner alt fra harddisken eller sende spam 234 00:10:25,150 --> 00:10:27,000 eller annen måte angripe maskinen? 235 00:10:27,000 --> 00:10:29,570 >> Så hvis hver av disse bokstavene A bare representerer, 236 00:10:29,570 --> 00:10:32,380 konseptuelt, angrep, angrep, angrep, angrep, noen dårlig kode 237 00:10:32,380 --> 00:10:36,410 at noen andre skrev, men hvis den personen er smart nok 238 00:10:36,410 --> 00:10:40,790 å ikke bare inkludere alle av de RM-rfs, men også 239 00:10:40,790 --> 00:10:46,100 har hans eller hennes siste bytes være et tall som tilsvarer 240 00:10:46,100 --> 00:10:50,540 til adressen til sitt eller hennes egen angrepskode 241 00:10:50,540 --> 00:10:53,820 at han eller hun gikk i bare ved å gi det ved ledeteksten, 242 00:10:53,820 --> 00:10:58,760 du effektivt kan lure datamaskinen til merke når f er gjort utførende, 243 00:10:58,760 --> 00:11:02,400 oh, er det på tide for meg å hoppe tilbake til den røde returadresse. 244 00:11:02,400 --> 00:11:06,070 Men fordi han eller hun har en eller annen måte overlappet som returadresse 245 00:11:06,070 --> 00:11:09,602 med sitt eget nummer, og de er smarte nok 246 00:11:09,602 --> 00:11:11,560 å ha konfigurert som nummer til å referere, som du 247 00:11:11,560 --> 00:11:13,740 se i super topp venstre hjørne der, 248 00:11:13,740 --> 00:11:18,020 den faktiske adresse i datamaskinens minne om noen av deres angrep kode, 249 00:11:18,020 --> 00:11:21,740 en bad guy kan lure datamaskinen til å utføre sin egen kode. 250 00:11:21,740 --> 00:11:23,700 >> Og den koden, igjen, kan være hva som helst. 251 00:11:23,700 --> 00:11:26,120 Det er generelt kalt shell-kode, som er bare 252 00:11:26,120 --> 00:11:29,030 en måte å si at det ikke er generelt noe så enkelt som rm-rf. 253 00:11:29,030 --> 00:11:32,340 Det er faktisk noe som Bash, eller en faktisk program som gir ham 254 00:11:32,340 --> 00:11:37,230 eller hennes programmakontrollen for å utføre noe annet som de vil. 255 00:11:37,230 --> 00:11:40,210 Så kort sagt, alt dette stammer fra det enkle faktum 256 00:11:40,210 --> 00:11:44,490 at denne feilen er involvert ikke sjekker grensene for klyngen. 257 00:11:44,490 --> 00:11:47,250 Og fordi måten datamaskiner arbeid er at de 258 00:11:47,250 --> 00:11:49,430 bruke stabelen fra effektivt, konseptuelt, 259 00:11:49,430 --> 00:11:54,830 nederst på opp, men deretter elementene du skyver på stakken vokse toppen og ned, 260 00:11:54,830 --> 00:11:56,624 dette er utrolig problematisk. 261 00:11:56,624 --> 00:11:58,290 Nå finnes det måter å omgå dette. 262 00:11:58,290 --> 00:12:00,800 Og ærlig talt, det finnes språk som å omgå dette. 263 00:12:00,800 --> 00:12:03,100 Java er immune, f.eks til dette spesielle problemet. 264 00:12:03,100 --> 00:12:04,110 Fordi de ikke gi deg tips. 265 00:12:04,110 --> 00:12:05,943 De vil ikke gi deg direkte minneadresser. 266 00:12:05,943 --> 00:12:08,560 Så med denne kraften som vi har å røre noe i minnet 267 00:12:08,560 --> 00:12:11,580 vi ønsker kommer riktignok stor risiko. 268 00:12:11,580 --> 00:12:12,430 >> Så hold et øye. 269 00:12:12,430 --> 00:12:14,596 Hvis, ærlig, i månedene eller årene som kommer, når som helst 270 00:12:14,596 --> 00:12:17,740 du lese om noen utnyttelse av et program eller en server, 271 00:12:17,740 --> 00:12:22,370 Hvis du noen gang ser et snev av noe som en buffer overflow-angrep, 272 00:12:22,370 --> 00:12:25,390 eller stack overflow er en annen type for angrep, ligner i ånden, 273 00:12:25,390 --> 00:12:28,770 mye som inspirerer nettstedets nevne, hvis du vet det, 274 00:12:28,770 --> 00:12:33,170 det er alle snakker om bare fylte størrelsen noen tegn 275 00:12:33,170 --> 00:12:36,200 matrise eller noen matrise mer generelt. 276 00:12:36,200 --> 00:12:38,822 Eventuelle spørsmål, da, om dette? 277 00:12:38,822 --> 00:12:39,780 Ikke prøv dette hjemme. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> Greit. 280 00:12:42,300 --> 00:12:47,270 Så malloc så langt har vært vår nye venn i at vi kan tildele minne 281 00:12:47,270 --> 00:12:50,540 at vi ikke nødvendigvis vet i forhånd at vi ønsker slik at vi ikke har 282 00:12:50,540 --> 00:12:52,920 til hard kode inn i vårt programnummer som 12. 283 00:12:52,920 --> 00:12:55,550 Når brukeren forteller oss hvor mye data han eller hun ønsker å legge inn, 284 00:12:55,550 --> 00:12:58,000 vi kan malloc så mye minne. 285 00:12:58,000 --> 00:13:01,484 >> Så malloc det viser seg, til grad vi har brukt det, 286 00:13:01,484 --> 00:13:03,900 eksplisitt siste gang, og deretter dere har brukt det 287 00:13:03,900 --> 00:13:08,160 for getstring uvitende for flere uker, alle av malloc minne 288 00:13:08,160 --> 00:13:09,820 kommer fra den såkalte heap. 289 00:13:09,820 --> 00:13:13,852 Og dette er grunnen getstring, f.eks kan tildele minne dynamisk 290 00:13:13,852 --> 00:13:16,060 uten å vite hva du er kommer til å skrive på forhånd, 291 00:13:16,060 --> 00:13:21,520 hånd du tilbake en peker til dette minnet, og at minnet er fortsatt ditt for alltid, 292 00:13:21,520 --> 00:13:24,080 selv etter getstring avkastning. 293 00:13:24,080 --> 00:13:27,450 Fordi tilbakekalling tross alt at stack er stadig går opp og ned, 294 00:13:27,450 --> 00:13:27,950 opp og ned. 295 00:13:27,950 --> 00:13:30,230 Og så snart det går ned, betyr at en hvilken som helst minne 296 00:13:30,230 --> 00:13:33,030 denne funksjonen som brukes skal ikke brukes av noen andre. 297 00:13:33,030 --> 00:13:34,570 Det er søppel verdier nå. 298 00:13:34,570 --> 00:13:36,120 >> Men haugen er her oppe. 299 00:13:36,120 --> 00:13:39,360 Og hva er fint om malloc er at når malloc tildeler minne opp her, 300 00:13:39,360 --> 00:13:42,070 det er ikke påvirket, for meste av stabelen. 301 00:13:42,070 --> 00:13:46,000 Og så noen funksjon kan få tilgang minne som har blitt malloc'd, 302 00:13:46,000 --> 00:13:49,120 selv av en funksjon som getstring, selv etter at den er returnert. 303 00:13:49,120 --> 00:13:51,700 >> Nå er det motsatte av malloc gratis. 304 00:13:51,700 --> 00:13:53,900 Og ja, den regelen du må begynne å ta i bruk 305 00:13:53,900 --> 00:13:58,950 er noen, noen, noen gang du bruker malloc du må selv bruke gratis, til slutt, 306 00:13:58,950 --> 00:14:00,280 på den samme pekeren. 307 00:14:00,280 --> 00:14:03,289 Hele denne tiden har vi vært å skrive buggy, buggy kode, av mange grunner. 308 00:14:03,289 --> 00:14:05,580 Men en av hvilke har vært bruker CS50 biblioteket, som 309 00:14:05,580 --> 00:14:09,010 selv er bevisst buggy, lekker det minne. 310 00:14:09,010 --> 00:14:11,410 Hver gang du har kalt getstring i løpet av de siste ukene 311 00:14:11,410 --> 00:14:13,870 vi ber drifts system, Linux, for minnet. 312 00:14:13,870 --> 00:14:15,780 Og du har aldri en gang gitt det tilbake. 313 00:14:15,780 --> 00:14:17,730 Og dette er ikke, i øve, en god ting. 314 00:14:17,730 --> 00:14:20,330 >> Og Valgrind, en av de verktøy introdusert i PSet 4, 315 00:14:20,330 --> 00:14:22,900 handler om å hjelpe deg nå finne bugs sånn. 316 00:14:22,900 --> 00:14:27,060 Men heldigvis for PSet 4 du ikke trenger å bruke CS50 biblioteket eller getstring. 317 00:14:27,060 --> 00:14:31,220 Så noen bugs relatert til minnet er slutt kommer til å være din egen. 318 00:14:31,220 --> 00:14:34,060 >> Så malloc er mer enn bare fordelaktig for dette formålet. 319 00:14:34,060 --> 00:14:37,420 Vi kan faktisk nå løse fundamentalt forskjellige problemer, 320 00:14:37,420 --> 00:14:41,640 og fundamentalt løse problemer mer effektivt som per uke null løfte. 321 00:14:41,640 --> 00:14:44,720 Så langt er dette den mest sexy datastruktur vi har hatt. 322 00:14:44,720 --> 00:14:47,804 Og ved datastruktur Jeg mener en måte å konseptualisere minne 323 00:14:47,804 --> 00:14:50,720 på en måte som går utover bare å si: Dette er en int, dette er et tegn. 324 00:14:50,720 --> 00:14:52,930 Vi kan begynne å klase ting sammen. 325 00:14:52,930 --> 00:14:54,460 >> Så en rekke så ut som dette. 326 00:14:54,460 --> 00:14:57,270 Og hva var nøkkelen i omtrent en matrise er at det gir deg 327 00:14:57,270 --> 00:14:59,724 back-to-back biter av hukommelse, hvor hver av disse 328 00:14:59,724 --> 00:15:02,765 kommer til å være av samme type, int, int, int, int, eller røye, røye, sjørøye, 329 00:15:02,765 --> 00:15:03,330 røye. 330 00:15:03,330 --> 00:15:04,496 Men det er noen ulemper. 331 00:15:04,496 --> 00:15:06,570 Dette er for eksempel en matrise av størrelse seks. 332 00:15:06,570 --> 00:15:10,650 Tenk deg at du fyller denne matrisen med seks tall og da, uavhengig av hvilken grunn, 333 00:15:10,650 --> 00:15:13,187 ditt brukeren ønsker å gi du en syvende nummer. 334 00:15:13,187 --> 00:15:14,020 Hvor setter du det? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Hva er løsningen hvis du har opprettet en rekke på stakken, 337 00:15:18,990 --> 00:15:22,030 for eksempel, bare med uken to notasjon som vi innført, 338 00:15:22,030 --> 00:15:23,730 av hakeparenteser med et tall inni? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 Vel, du har seks Tallene i disse boksene. 341 00:15:27,260 --> 00:15:28,530 Hva ville instinktene dine være? 342 00:15:28,530 --> 00:15:29,973 Hvor ville du ønsker å plassere den? 343 00:15:29,973 --> 00:15:30,860 >> PUBLIKUM: [uhørbart] 344 00:15:30,860 --> 00:15:31,315 >> DAVID J. MALAN: Sorry? 345 00:15:31,315 --> 00:15:32,380 >> PUBLIKUM: Sett det på slutten. 346 00:15:32,380 --> 00:15:33,796 >> DAVID J. MALAN: Sett det på slutten. 347 00:15:33,796 --> 00:15:35,880 Så bare over til høyre, Utsiden av denne boksen. 348 00:15:35,880 --> 00:15:38,710 Som ville være fint, men det viser seg at du ikke kan gjøre det. 349 00:15:38,710 --> 00:15:41,350 Fordi hvis du ikke har bedt om for denne del av minnet, 350 00:15:41,350 --> 00:15:44,490 det kan være tilfeldig at dette brukes av en annen variabel 351 00:15:44,490 --> 00:15:45,030 helt. 352 00:15:45,030 --> 00:15:49,210 Tenk tilbake en uke eller så når vi lagt ut Zamyla og Davin og Gabes navn 353 00:15:49,210 --> 00:15:49,930 i minnet. 354 00:15:49,930 --> 00:15:51,638 De var bokstavelig talt rygg mot rygg mot rygg. 355 00:15:51,638 --> 00:15:53,550 Så vi kan ikke nødvendigvis Stol på at hva som står 356 00:15:53,550 --> 00:15:55,800 over her er tilgjengelig for meg å bruke. 357 00:15:55,800 --> 00:15:56,990 >> Så hva annet kan du gjøre? 358 00:15:56,990 --> 00:16:00,282 Vel, en gang innser du trenger en matrise av størrelse syv, 359 00:16:00,282 --> 00:16:02,490 du kan bare lage en matrise av størrelse syv deretter bruke 360 00:16:02,490 --> 00:16:05,950 en for løkke eller en stund loop, kopiere den inn i det nye utvalget, 361 00:16:05,950 --> 00:16:09,680 og deretter en eller annen måte bare bli kvitt denne matrisen eller bare slutte å bruke det. 362 00:16:09,680 --> 00:16:12,130 Men det er ikke spesielt effektiv. 363 00:16:12,130 --> 00:16:15,340 Kort sagt, gjør arrays ikke la du dynamisk endre størrelsen. 364 00:16:15,340 --> 00:16:17,900 >> Så på den ene siden du får random access, noe som er fantastisk. 365 00:16:17,900 --> 00:16:20,108 Fordi det lar oss gjøre ting som Splitt og hersk, 366 00:16:20,108 --> 00:16:23,100 binære søk, som alle vi har snakket om på skjermen her. 367 00:16:23,100 --> 00:16:24,950 Men du male selv inn i et hjørne. 368 00:16:24,950 --> 00:16:27,810 Så snart du treffer slutten av array, 369 00:16:27,810 --> 00:16:29,980 du trenger å gjøre en veldig kostbar operasjon 370 00:16:29,980 --> 00:16:33,910 eller skrive en hel haug med kode å nå håndtere det problemet. 371 00:16:33,910 --> 00:16:36,680 >> Så hva om stedet vi hadde noe som kalles en liste, 372 00:16:36,680 --> 00:16:38,820 eller en lenket liste spesielt? 373 00:16:38,820 --> 00:16:41,930 Hva om i stedet for å rektangler rygg mot rygg til rygg, 374 00:16:41,930 --> 00:16:45,730 vi har rektangler som forlater litt litt slingringsmonn i mellom dem? 375 00:16:45,730 --> 00:16:49,670 Og selv om jeg har trukket dette bilde eller tilpasset dette bildet 376 00:16:49,670 --> 00:16:54,696 fra en av tekstene her for å være tilbake til back to back veldig ryddig, i virkeligheten, 377 00:16:54,696 --> 00:16:56,820 en av disse rektangler kunne være her oppe i minnet. 378 00:16:56,820 --> 00:16:58,028 En av dem kunne være her oppe. 379 00:16:58,028 --> 00:17:00,420 En av dem kan være her oppe, over her, og så videre. 380 00:17:00,420 --> 00:17:02,910 >> Men hva om vi trakk, i dette tilfellet, piler 381 00:17:02,910 --> 00:17:05,650 som liksom knytte disse rektangler sammen? 382 00:17:05,650 --> 00:17:08,170 Faktisk har vi sett en teknisk inkarnasjonen av en pil. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 Hva har vi brukt i nyere dager som, under panseret, 385 00:17:13,710 --> 00:17:15,210 er representativ for en pil? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 En peker, ikke sant? 388 00:17:17,349 --> 00:17:19,780 >> Så hva om, i stedet for bare lagring av tall, 389 00:17:19,780 --> 00:17:23,130 som 9, 17, 22, 26, 34, hva om vi lagret ikke 390 00:17:23,130 --> 00:17:27,079 bare et tall, men en peker ved siden av hvert slikt nummer? 391 00:17:27,079 --> 00:17:30,690 Slik at mye som du ville tråden en nålen gjennom en hel haug med stoff, 392 00:17:30,690 --> 00:17:32,950 liksom binde ting sammen, kan likeledes 393 00:17:32,950 --> 00:17:35,550 vi med pekere, som inkarnert med piler her, 394 00:17:35,550 --> 00:17:38,550 slags veve sammen disse individuelle rektangler 395 00:17:38,550 --> 00:17:41,780 ved effektivt å bruke en peker ved siden av hvert nummer som 396 00:17:41,780 --> 00:17:46,065 peker på noen neste nummer, som peker mot, i sin tur, et neste nummer? 397 00:17:46,065 --> 00:17:47,940 Så med andre ord, hva hvis vi faktisk ønsket 398 00:17:47,940 --> 00:17:49,820 å gjennomføre noe sånt som dette? 399 00:17:49,820 --> 00:17:53,610 Vel dessverre, disse rektangler, i det minste den med 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 og så videre, er disse ikke lenger fine firkanter med enkle tall. 401 00:17:57,040 --> 00:17:59,960 Bunnen, rektangel under 9, for eksempel, 402 00:17:59,960 --> 00:18:04,330 representerer hva skal være en peker, 32 biter. 403 00:18:04,330 --> 00:18:09,460 Nå er jeg ikke ennå klar over noen datatype i C som gir deg ikke bare en int 404 00:18:09,460 --> 00:18:11,630 men en peker helt. 405 00:18:11,630 --> 00:18:15,020 >> Så hva er løsningen hvis vi ønsker å oppfinne vår egen svar på dette? 406 00:18:15,020 --> 00:18:15,760 Yeah? 407 00:18:15,760 --> 00:18:16,640 >> PUBLIKUM: [uhørbart] 408 00:18:16,640 --> 00:18:17,360 >> DAVID J. MALAN: Hva er det? 409 00:18:17,360 --> 00:18:17,880 >> PUBLIKUM: Ny struktur. 410 00:18:17,880 --> 00:18:19,590 >> DAVID J. MALAN: Ja, så hvorfor Kan vi ikke lage en ny struktur, 411 00:18:19,590 --> 00:18:20,920 eller i C, en struct? 412 00:18:20,920 --> 00:18:25,990 Vi har sett structs før, hvis kort, hvor vi jobbet med en student struktur 413 00:18:25,990 --> 00:18:27,780 som dette, som hadde et navn og et hus. 414 00:18:27,780 --> 00:18:31,980 I PSet tre avslapnings du brukte en hel haug med structs-- GRect og GOvals 415 00:18:31,980 --> 00:18:34,810 at Stanford opprettet for å klynge informasjonen sammen. 416 00:18:34,810 --> 00:18:38,580 Så hva om vi tar den samme ideen om søkeordene "typedef" og "struct", 417 00:18:38,580 --> 00:18:42,890 og litt til student-spesifikke ting, og utvikle dette i følgende: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- og node er bare en svært generisk informatikk 419 00:18:46,210 --> 00:18:49,980 begrep for noe i en datastruktur, en beholder i en datastruktur. 420 00:18:49,980 --> 00:18:53,900 En node jeg hevder er nødt til en int n, helt grei, 421 00:18:53,900 --> 00:18:58,810 og deretter litt mer kryptisk, denne andre linje, struct node * neste. 422 00:18:58,810 --> 00:19:01,300 Men i mindre tekniske termer, hva er det andre linjen 423 00:19:01,300 --> 00:19:02,980 kode inne i klammeparentes? 424 00:19:02,980 --> 00:19:03,737 Yeah? 425 00:19:03,737 --> 00:19:04,851 >> PUBLIKUM: [uhørbart] 426 00:19:04,851 --> 00:19:06,600 DAVID J. MALAN: A Peker til en annen node. 427 00:19:06,600 --> 00:19:09,910 Så riktignok, syntaks litt kryptisk. 428 00:19:09,910 --> 00:19:13,250 Men hvis du leser det bokstavelig talt, neste er navnet på en variabel. 429 00:19:13,250 --> 00:19:14,410 Hva er dens datatype? 430 00:19:14,410 --> 00:19:18,206 Det er litt ordrik denne gangen, men det er av type struct node *. 431 00:19:18,206 --> 00:19:22,960 Hver gang vi har sett noe stjerne, som betyr at det er en peker til den datatypen. 432 00:19:22,960 --> 00:19:26,810 Så neste er tilsynelatende en peker til en struct node. 433 00:19:26,810 --> 00:19:28,310 >> Nå, hva er en struct node? 434 00:19:28,310 --> 00:19:31,044 Vel, du merker ser dem samme ordene øverst til høyre. 435 00:19:31,044 --> 00:19:33,960 Og ja, du også se ordet "Node" her nede nederst til venstre. 436 00:19:33,960 --> 00:19:35,640 Og dette er faktisk bare en bekvemmelighet. 437 00:19:35,640 --> 00:19:39,930 Legg merke til at i vår student definisjon det er ordet "student" bare én gang. 438 00:19:39,930 --> 00:19:42,510 Og det er fordi en student Målet var ikke selv-referensiell. 439 00:19:42,510 --> 00:19:45,340 Det er ingenting inne i en student som må peke til en annen student, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 Det ville være slags rart i den virkelige verden. 442 00:19:47,630 --> 00:19:50,880 >> Men med en node i et koblet liste, ønsker vi en node 443 00:19:50,880 --> 00:19:53,970 å være referanse til en lignende gjenstand. 444 00:19:53,970 --> 00:19:57,900 Og så merke endringen her er ikke akkurat hva som er inne i klammeparentes. 445 00:19:57,900 --> 00:20:00,800 Men vi legge til ordet "node" på toppen, samt 446 00:20:00,800 --> 00:20:02,930 legge den til bunnen i stedet for "student". 447 00:20:02,930 --> 00:20:06,000 Og dette er bare en teknisk detalj slik at, igjen, din datastruktur 448 00:20:06,000 --> 00:20:11,380 kan være selvrefererende, slik at en node kan peke til en annen slik node. 449 00:20:11,380 --> 00:20:13,840 >> Så hva er dette til slutt kommer til å bety for oss? 450 00:20:13,840 --> 00:20:17,560 Vel, en, dette ting inni er innholdet i vårt node. 451 00:20:17,560 --> 00:20:19,360 Denne tingen her oppe, øverst til høyre, er bare så 452 00:20:19,360 --> 00:20:20,860 som, igjen, kan vi referere til oss selv. 453 00:20:20,860 --> 00:20:23,401 Og så den ytterste ting, selv om node er et nytt begrep, 454 00:20:23,401 --> 00:20:25,500 kanskje, er det fortsatt det samme som student og hva 455 00:20:25,500 --> 00:20:27,520 var under panseret i SPL. 456 00:20:27,520 --> 00:20:31,095 >> Så hvis vi nå ønsket å starte implementere denne lenket liste, 457 00:20:31,095 --> 00:20:33,220 hvordan kan vi oversette noe som dette å kode? 458 00:20:33,220 --> 00:20:35,350 Vel, la oss bare se en eksempel på et program som 459 00:20:35,350 --> 00:20:36,840 faktisk bruker en lenket liste. 460 00:20:36,840 --> 00:20:40,870 Blant dagens distribusjon kode er et program som heter List Zero. 461 00:20:40,870 --> 00:20:44,980 Og hvis jeg kjører dette jeg laget en super enkel GUI, grafisk brukergrensesnitt, 462 00:20:44,980 --> 00:20:46,460 men det er egentlig bare printf. 463 00:20:46,460 --> 00:20:50,930 Og nå har jeg gitt meg selv noen meny options-- Slett, Sett, Søk, 464 00:20:50,930 --> 00:20:51,750 og Traverse. 465 00:20:51,750 --> 00:20:52,630 Og sluttet. 466 00:20:52,630 --> 00:20:55,970 Dette er bare vanlige operasjoner på en datastruktur kjent som en koblingsliste. 467 00:20:55,970 --> 00:20:58,409 >> Nå Slett kommer til å slette et nummer fra listen. 468 00:20:58,409 --> 00:21:00,200 Sett inn kommer til å legge et nummer til listen. 469 00:21:00,200 --> 00:21:02,181 Søk kommer til å se for nummeret i listen. 470 00:21:02,181 --> 00:21:04,930 Og traversen er bare en fancy måte å si, gå gjennom listen, 471 00:21:04,930 --> 00:21:06,245 skrive det ut, men det er det. 472 00:21:06,245 --> 00:21:07,720 Ikke endre det på noen måte. 473 00:21:07,720 --> 00:21:08,570 >> Så la oss prøve dette. 474 00:21:08,570 --> 00:21:10,160 La oss gå videre og type 2. 475 00:21:10,160 --> 00:21:12,710 Og så kommer jeg til å sette inn nummeret, sier ni. 476 00:21:12,710 --> 00:21:13,620 Enter. 477 00:21:13,620 --> 00:21:17,480 Og nå mitt program er bare programmert til å si, er listen nå ni. 478 00:21:17,480 --> 00:21:20,190 Nå, hvis jeg går videre og setter inn igjen, la 479 00:21:20,190 --> 00:21:23,680 meg gå videre og zoome ut og skriv inn 17. 480 00:21:23,680 --> 00:21:25,770 Nå er min liste er 9, da 17. 481 00:21:25,770 --> 00:21:27,750 Hvis jeg gjør setter inn igjen, la oss hoppe over en. 482 00:21:27,750 --> 00:21:32,400 I stedet for 22, som per bildet vi har vært å se på her, la meg hoppe fremover 483 00:21:32,400 --> 00:21:34,630 og sett 26 neste. 484 00:21:34,630 --> 00:21:36,230 Så jeg kommer til å skrive 26. 485 00:21:36,230 --> 00:21:37,755 Listen er som jeg forventer. 486 00:21:37,755 --> 00:21:40,630 Men nå, bare for å se om denne koden kommer til å være fleksibel, la meg nå 487 00:21:40,630 --> 00:21:43,520 typen 22, som i det minste konseptuelt, hvis vi er 488 00:21:43,520 --> 00:21:46,520 Holder dette sortert, som er faktisk kommer til å bli nok et mål akkurat nå, 489 00:21:46,520 --> 00:21:48,690 bør gå i mellom 17 og 26. 490 00:21:48,690 --> 00:21:50,270 Så jeg trykker Enter. 491 00:21:50,270 --> 00:21:51,380 Faktisk fungerer det. 492 00:21:51,380 --> 00:21:54,950 Og så nå la meg sette inn siste, per bildet, 34. 493 00:21:54,950 --> 00:21:55,450 >> Greit. 494 00:21:55,450 --> 00:21:58,980 Så for nå la meg bestemme at Slett og Traverse og søk gjør det, 495 00:21:58,980 --> 00:21:59,760 faktisk fungerer. 496 00:21:59,760 --> 00:22:04,180 Faktisk, hvis jeg kjører søk, la oss søke etter nummeret 22, Enter. 497 00:22:04,180 --> 00:22:05,010 Det funnet 22. 498 00:22:05,010 --> 00:22:07,580 Så det er det denne Programlisten Zero gjør. 499 00:22:07,580 --> 00:22:10,230 >> Men hva som faktisk skjer på som implementerer dette? 500 00:22:10,230 --> 00:22:14,530 Vel, første jeg kan ha, og faktisk Jeg har en fil som heter list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 Og et sted der dette er linje, typedef, struct node, 503 00:22:20,690 --> 00:22:24,850 så jeg har mine klammeparentes, int n, og deretter struct-- hva var definisjonen? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Struct node neste. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Så vi trenger stjernen. 508 00:22:31,045 --> 00:22:33,420 Nå teknisk får vi inn vane med å tegne den her. 509 00:22:33,420 --> 00:22:35,670 Du kan se lærebøker og online referanser gjør det der. 510 00:22:35,670 --> 00:22:36,660 Det er tilsvarende funksjonalitet. 511 00:22:36,660 --> 00:22:37,980 Faktisk er dette en litt mer typisk. 512 00:22:37,980 --> 00:22:40,563 Men jeg skal være i samsvar med hva vi gjorde sist gang og gjøre dette. 513 00:22:40,563 --> 00:22:42,350 Og så til slutt, jeg kommer til å gjøre dette. 514 00:22:42,350 --> 00:22:45,550 >> Så i en header-fil et sted, i list0.h 515 00:22:45,550 --> 00:22:49,200 i dag er dette struct definisjon, og kanskje noen andre ting. 516 00:22:49,200 --> 00:22:52,580 I mellomtiden i list0c det er kommer til å være et par ting. 517 00:22:52,580 --> 00:22:54,740 Men vi kommer til å like starte og ikke fullføre dette. 518 00:22:54,740 --> 00:22:59,690 List0.h er en fil jeg vil ha å ta med i C-fil. 519 00:22:59,690 --> 00:23:03,910 Og så på et tidspunkt jeg er kommer til å ha int, main, ugyldig. 520 00:23:03,910 --> 00:23:06,530 Og så kommer jeg til å har noen to-do er her. 521 00:23:06,530 --> 00:23:10,620 Jeg er også tenkt å ha en prototype, som ugyldig, søk, int, 522 00:23:10,620 --> 00:23:13,610 n, er hvis formål i livet for å søke etter et element. 523 00:23:13,610 --> 00:23:18,310 Og deretter ned her jeg hevder i dagens kode, ugyldig, søk, int, n, 524 00:23:18,310 --> 00:23:21,020 ingen semikolon men åpne klammeparentes. 525 00:23:21,020 --> 00:23:25,049 Og nå vil jeg liksom søke for et element i denne listen. 526 00:23:25,049 --> 00:23:27,340 Men vi har ikke nok informasjon på skjermen ennå. 527 00:23:27,340 --> 00:23:29,800 Jeg har faktisk ikke representerte selve listen. 528 00:23:29,800 --> 00:23:33,070 Så en måte vi kunne implementere en lenket liste i et program 529 00:23:33,070 --> 00:23:37,520 er jeg slags ønsker å gjøre noe som erklærer lenket liste opp her. 530 00:23:37,520 --> 00:23:40,520 For enkelhets skyld kommer jeg til å gjøre denne globale, selv om vi generelt 531 00:23:40,520 --> 00:23:41,645 bør ikke gjøre dette for mye. 532 00:23:41,645 --> 00:23:43,260 Men det vil forenkle dette eksempel. 533 00:23:43,260 --> 00:23:45,890 Så jeg ønsker å erklære en lenket liste opp her. 534 00:23:45,890 --> 00:23:47,010 Nå, hvordan kan jeg gjøre det? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Her er bildet av en lenket liste. 537 00:23:50,750 --> 00:23:53,030 Og jeg egentlig ikke vet i øyeblikket hvordan 538 00:23:53,030 --> 00:23:56,710 Jeg kommer til å gå om å representere så mange ting med bare ett 539 00:23:56,710 --> 00:23:58,040 variabel i minnet. 540 00:23:58,040 --> 00:23:59,160 Men tenker tilbake et øyeblikk. 541 00:23:59,160 --> 00:24:00,830 Hele denne tiden vi har hatt strenger, som vi deretter 542 00:24:00,830 --> 00:24:02,913 avslørt å være matriser av tegn, som vi deretter 543 00:24:02,913 --> 00:24:05,740 avslørt å bare være en peker til det første tegnet 544 00:24:05,740 --> 00:24:08,890 i en rekke tegn som er null terminert. 545 00:24:08,890 --> 00:24:13,530 Så ved den logikken, og med dette Bildet slags seeding dine tanker, 546 00:24:13,530 --> 00:24:17,964 Hva trenger vi egentlig skrive i vår kode for å representere en lenket liste? 547 00:24:17,964 --> 00:24:21,130 Hvor mye av denne informasjonen vi trenger gjøre å fange i C-kode, vil du si? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Yeah? 550 00:24:23,154 --> 00:24:24,738 >> PUBLIKUM: Vi trenger en peker til en node. 551 00:24:24,738 --> 00:24:26,237 DAVID J. MALAN: En peker til en node. 552 00:24:26,237 --> 00:24:29,320 I særdeleshet, som node ville din instinkter være å holde en peker til? 553 00:24:29,320 --> 00:24:30,026 >> PUBLIKUM: Den første noden. 554 00:24:30,026 --> 00:24:31,942 >> DAVID J. MALAN: Yeah, trolig bare den første. 555 00:24:31,942 --> 00:24:34,030 Og legg merke til, den første node er en annen form. 556 00:24:34,030 --> 00:24:37,690 Det er bare halve størrelsen av struct, fordi det er faktisk bare en peker. 557 00:24:37,690 --> 00:24:44,650 Så hva du faktisk kan gjøre er å erklære en lenket liste for å være av typen node *. 558 00:24:44,650 --> 00:24:47,780 Og la oss bare kalle det første og initialisere den til null. 559 00:24:47,780 --> 00:24:49,910 Så null, igjen, er kommer inn i bildet her. 560 00:24:49,910 --> 00:24:53,620 Ikke bare er null brukt som som en spesiell returverdi for ting som getstring 561 00:24:53,620 --> 00:24:57,770 og malloc, er null også null pekeren, mangelen på en peker, 562 00:24:57,770 --> 00:24:58,430 hvis du vil. 563 00:24:58,430 --> 00:25:00,309 Det betyr bare ingenting er ennå her. 564 00:25:00,309 --> 00:25:02,100 Nå først, jeg kunne har kalte dette noe. 565 00:25:02,100 --> 00:25:04,200 Jeg kunne ha kalt det "liste" eller hvilket som helst antall av andre ting. 566 00:25:04,200 --> 00:25:06,960 Men jeg kaller det "første", slik at det linjer med dette bildet. 567 00:25:06,960 --> 00:25:10,280 Så akkurat som en streng kan være representert med adressen til den første byte, 568 00:25:10,280 --> 00:25:11,280 så kan en lenket liste. 569 00:25:11,280 --> 00:25:13,480 Og vi vil se andre data strukturer være representert 570 00:25:13,480 --> 00:25:16,700 med bare ett pekeren, en 32-bit pilen peker 571 00:25:16,700 --> 00:25:18,740 på det første knutepunktet i strukturen. 572 00:25:18,740 --> 00:25:20,340 >> Men la oss nå forutse et problem. 573 00:25:20,340 --> 00:25:23,230 Hvis jeg bare huske i mitt program adressen 574 00:25:23,230 --> 00:25:27,220 av den første node, den første rektangel i dette datastrukturen, 575 00:25:27,220 --> 00:25:31,760 det hadde bedre være tilfelle om gjennomføringen av resten av listen min? 576 00:25:31,760 --> 00:25:35,820 Hva er en nøkkel detalj som kommer å sikre at dette faktisk fungerer? 577 00:25:35,820 --> 00:25:39,250 Og med "faktisk fungerer" Jeg mener, omtrent som en streng, 578 00:25:39,250 --> 00:25:42,180 lar oss gå fra det første tegnet i Davin navn til den andre, 579 00:25:42,180 --> 00:25:44,755 til den tredje, til fjerde, helt til enden, 580 00:25:44,755 --> 00:25:47,880 hvordan vet vi når vi er på slutten av en lenket liste som ser slik ut? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Når det er null. 583 00:25:50,660 --> 00:25:53,640 Og jeg har representert denne typen som som elektroingeniør makt, 584 00:25:53,640 --> 00:25:56,420 med den lille jording symbol, av former. 585 00:25:56,420 --> 00:25:58,246 Men det betyr bare null i dette tilfellet. 586 00:25:58,246 --> 00:26:00,370 Du kan tegne det en rekke måter, men denne forfatteren 587 00:26:00,370 --> 00:26:02,800 skjedd å bruke dette symbolet her. 588 00:26:02,800 --> 00:26:06,260 >> Så lenge vi strenger alle disse nodene sammen, 589 00:26:06,260 --> 00:26:08,600 bare huske hvor den første er, så lenge 590 00:26:08,600 --> 00:26:11,760 som vi setter et spesielt symbol på den aller siste node i listen, 591 00:26:11,760 --> 00:26:15,130 og vi vil bruke null, fordi det er hva vi har tilgjengelig for oss, 592 00:26:15,130 --> 00:26:16,480 listen er fullstendig. 593 00:26:16,480 --> 00:26:20,190 Og selv om jeg bare gi deg en peker til det første elementet, du, programmerer, 594 00:26:20,190 --> 00:26:22,486 kan sikkert få tilgang til resten av det. 595 00:26:22,486 --> 00:26:24,360 Men la oss la ditt sinn vandre litt, 596 00:26:24,360 --> 00:26:26,140 hvis de allerede ikke er ganske wandered-- hva som er 597 00:26:26,140 --> 00:26:28,723 kommer til å være kjøretiden å finne noe i denne listen? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Pokker, det er stor O av n, som ikke er dårlig, i rettferdighet. 600 00:26:33,470 --> 00:26:34,800 Men det er lineær. 601 00:26:34,800 --> 00:26:37,980 Vi har gitt opp hva funksjonen av matriser ved å flytte mer 602 00:26:37,980 --> 00:26:43,130 mot dette bildet av dynamisk vevd sammen eller koblede noder? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Vi har gitt opp random access. 605 00:26:46,687 --> 00:26:48,770 En rekke er fint fordi matematisk alt 606 00:26:48,770 --> 00:26:50,340 er rygg mot rygg mot rygg mot rygg. 607 00:26:50,340 --> 00:26:52,370 Selv om dette bildet ser pen, og selv 608 00:26:52,370 --> 00:26:55,830 selv om det ser ut som disse nodene er pent plassert fra hverandre, i virkeligheten 609 00:26:55,830 --> 00:26:56,830 de kan være hvor som helst. 610 00:26:56,830 --> 00:27:01,590 OX1, Ox50, Ox123, Ox99, disse Nodene kan være hvor som helst. 611 00:27:01,590 --> 00:27:05,960 Fordi malloc gjør allokere minne fra haugen, men hvor som helst i haugen. 612 00:27:05,960 --> 00:27:09,080 Du trenger ikke nødvendigvis vet at det er kommer til å være tilbake til rygg mot rygg. 613 00:27:09,080 --> 00:27:12,460 Og så dette bildet i virkelighetens ikke kommer til å være ganske dette pen. 614 00:27:12,460 --> 00:27:16,140 >> Så det kommer til å ta en bit av arbeide for å implementere denne funksjonen. 615 00:27:16,140 --> 00:27:17,880 Så la oss gjennomføre søk nå. 616 00:27:17,880 --> 00:27:20,250 Og vi vil se en slags smart måte å gjøre dette på. 617 00:27:20,250 --> 00:27:24,660 Så hvis jeg er en søkefunksjon og Jeg får en variabel, heltall n 618 00:27:24,660 --> 00:27:28,490 skal se etter, jeg trenger å vite nye syntaksen for å se innsiden 619 00:27:28,490 --> 00:27:32,400 av en struktur som finnes pekte på, for å finne n. 620 00:27:32,400 --> 00:27:33,210 Så la oss gjøre dette. 621 00:27:33,210 --> 00:27:36,030 >> Så først skal jeg gå videre og erklære en node *. 622 00:27:36,030 --> 00:27:39,400 Og jeg kommer til å kalle det pekeren, bare ved konvensjonen. 623 00:27:39,400 --> 00:27:41,710 Og jeg kommer til å initialisere den til først. 624 00:27:41,710 --> 00:27:43,770 Og nå kan jeg gjøre dette på en rekke måter. 625 00:27:43,770 --> 00:27:45,436 Men jeg kommer til å ta en felles tilnærming. 626 00:27:45,436 --> 00:27:50,180 Mens pekeren er ikke lik null, og det er gyldig syntaks. 627 00:27:50,180 --> 00:27:54,550 Og det betyr bare gjøre følgende, så lenge du ikke peker på noe. 628 00:27:54,550 --> 00:27:55,800 Hva ønsker jeg å gjøre? 629 00:27:55,800 --> 00:28:01,939 >> Hvis pekeren dot n, la meg komme tilbake til det, tilsvarer equals-- hva? 630 00:28:01,939 --> 00:28:03,105 Hvilken verdi Jeg leter etter? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 Selve n som ble vedtatt i. 633 00:28:06,590 --> 00:28:09,020 Så her er en annen funksjon av C og mange språk. 634 00:28:09,020 --> 00:28:13,705 Selv om strukturen som kalles noden har en verdi n, helt legitimt 635 00:28:13,705 --> 00:28:17,530 til også å ha en lokal argument eller variabel kalt n. 636 00:28:17,530 --> 00:28:20,085 Fordi selv vi, med menneskelige øyne kan skille 637 00:28:20,085 --> 00:28:22,087 at dette n er formodentlig forskjellig fra dette n. 638 00:28:22,087 --> 00:28:23,420 Fordi syntaksen er annerledes. 639 00:28:23,420 --> 00:28:26,211 Du har fått en prikk og en peker, mens denne har ikke noe slikt. 640 00:28:26,211 --> 00:28:27,290 Så dette er OK. 641 00:28:27,290 --> 00:28:29,120 Det er OK å kalle dem de samme tingene. 642 00:28:29,120 --> 00:28:32,380 >> Hvis jeg finner du dette, er jeg kommer til å ønske å gjøre noe 643 00:28:32,380 --> 00:28:35,000 som kunngjøre at vi har funnet n. 644 00:28:35,000 --> 00:28:37,930 Og vi skal la det som en kommentere eller pseudokode. 645 00:28:37,930 --> 00:28:40,190 Else, og her er den interessante delen, hva 646 00:28:40,190 --> 00:28:47,320 ønsker jeg å gjøre hvis den aktuelle noden ikke inneholder n at jeg bryr meg om? 647 00:28:47,320 --> 00:28:50,700 Hvordan oppnår jeg følgende? 648 00:28:50,700 --> 00:28:53,710 Hvis fingeren på øyeblikket er PTR, og det er 649 00:28:53,710 --> 00:28:55,920 peker på uansett først peker på, 650 00:28:55,920 --> 00:28:59,290 hvordan flytter jeg min finger til neste node i kode? 651 00:28:59,290 --> 00:29:01,915 Vel, hva er brødsmule vi er kommer til å følge i dette tilfellet? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 PUBLIKUM: [uhørlig]. 654 00:29:04,380 --> 00:29:05,630 DAVID J. MALAN: Ja, så neste. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Så hvis jeg går tilbake til min koden her, ja, jeg er 657 00:29:09,824 --> 00:29:12,990 kommer til å gå videre og si pekeren, som er bare en midlertidig variable-- det er 658 00:29:12,990 --> 00:29:15,320 en merkelig navn, PTR, men det er akkurat som temp-- 659 00:29:15,320 --> 00:29:19,234 Jeg kommer til å sette pekeren lik uansett pekeren er-- 660 00:29:19,234 --> 00:29:22,150 og igjen, dette kommer til å bli en litt buggy for en moment-- prikk ved. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 Med andre ord, jeg kommer til å ta min finger som peker på denne noden 663 00:29:26,550 --> 00:29:31,247 her, og jeg kommer til å si, vet du hva, ta en titt på neste felt 664 00:29:31,247 --> 00:29:33,330 og beveger fingeren til hva det peker på. 665 00:29:33,330 --> 00:29:35,163 Og dette kommer til å gjenta, gjenta, gjenta. 666 00:29:35,163 --> 00:29:37,630 Men da gjør min finger slutte å gjøre noe som helst? 667 00:29:37,630 --> 00:29:40,095 Så snart det kodelinje spark i? 668 00:29:40,095 --> 00:29:40,970 PUBLIKUM: [uhørbart] 669 00:29:40,970 --> 00:29:43,060 DAVID J. MALAN: Hvis punkt mens pekeren er ikke lik null. 670 00:29:43,060 --> 00:29:44,900 På et tidspunkt min milli kommer til å peke på null 671 00:29:44,900 --> 00:29:47,070 og jeg kommer til å realisere det er slutten av denne listen. 672 00:29:47,070 --> 00:29:48,910 Nå er dette en lite hvit løgn for enkelhet. 673 00:29:48,910 --> 00:29:51,580 Det viser seg at selv om vi bare lært dette dot notasjon 674 00:29:51,580 --> 00:29:55,220 for konstruksjoner, er pekeren ikke en struct. 675 00:29:55,220 --> 00:29:56,580 PTR er hva? 676 00:29:56,580 --> 00:29:58,350 Bare for å være mer pirkete. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 Det er en peker til en node. 679 00:30:01,360 --> 00:30:03,120 Det er ikke en node i seg selv. 680 00:30:03,120 --> 00:30:06,650 Hvis jeg hadde ingen stjerne her, peker absolutely-- det er en node. 681 00:30:06,650 --> 00:30:08,650 Dette er som uke en erklæring av en variabel, 682 00:30:08,650 --> 00:30:10,120 selv om ordet "node" er nye. 683 00:30:10,120 --> 00:30:13,860 >> Men så snart vi innføre en stjerne, er det nå en peker til en node. 684 00:30:13,860 --> 00:30:17,960 Og dessverre kan du ikke bruke dot notasjon for en peker. 685 00:30:17,960 --> 00:30:21,070 Du må bruke pilen notasjon, som påfallende, 686 00:30:21,070 --> 00:30:23,470 er første gang en brikke syntaks ser intuitivt. 687 00:30:23,470 --> 00:30:25,245 Dette ser bokstavelig talt ut som en pil. 688 00:30:25,245 --> 00:30:26,370 Og så det er en god ting. 689 00:30:26,370 --> 00:30:28,995 Og her nede bokstavelig talt ser ut som en pil. 690 00:30:28,995 --> 00:30:31,870 Så jeg tror det er la-- jeg ikke tror jeg over-begå her-- jeg 691 00:30:31,870 --> 00:30:34,120 tror det er det siste nye stykke syntaks vi kommer til å se. 692 00:30:34,120 --> 00:30:36,500 Og heldigvis er det faktisk en litt mer intuitiv. 693 00:30:36,500 --> 00:30:40,090 >> Nå, for de av dere som kanskje foretrekker den gamle måten, 694 00:30:40,090 --> 00:30:42,550 du kan fortsatt bruke dot notasjon. 695 00:30:42,550 --> 00:30:45,380 Men som per mandagens samtale, må vi først 696 00:30:45,380 --> 00:30:50,530 trenger å gå dit, gå til den adresse, og deretter få tilgang til feltet. 697 00:30:50,530 --> 00:30:51,897 Så dette er også korrekt. 698 00:30:51,897 --> 00:30:53,730 Og ærlig talt, dette er en litt mer pedantisk. 699 00:30:53,730 --> 00:30:56,530 Du er bokstavelig talt si, dereferanse markøren og gå dit. 700 00:30:56,530 --> 00:30:59,320 Så grip .N, feltet kalt n. 701 00:30:59,320 --> 00:31:01,370 Men ærlig, ønsker ingen å skrive eller lese dette. 702 00:31:01,370 --> 00:31:03,620 Og så verden oppfunnet pilen notasjon, som 703 00:31:03,620 --> 00:31:06,980 er tilsvarende, identiske, det er bare syntaktisk sukker. 704 00:31:06,980 --> 00:31:10,570 Så en fancy måte å si dette ser bedre ut, eller ser enklere. 705 00:31:10,570 --> 00:31:12,296 >> Så nå er jeg kommer til å gjøre en annen ting. 706 00:31:12,296 --> 00:31:15,420 Jeg kommer til å si "break" når jeg har fant det så jeg ikke holde utkikk etter den. 707 00:31:15,420 --> 00:31:17,620 Men dette er hovedpunkt av en søkefunksjon. 708 00:31:17,620 --> 00:31:21,710 Men det er mye enklere, i ende, for ikke å gå gjennom koden. 709 00:31:21,710 --> 00:31:25,570 Dette er faktisk den formelle gjennomføringen søk i dagens distribusjons kode. 710 00:31:25,570 --> 00:31:30,530 Jeg tør si at innsatsen ikke er spesielt morsomt å gå gjennom 711 00:31:30,530 --> 00:31:33,180 visuelt, og heller ikke er slette, selv selv ved slutten av dagen 712 00:31:33,180 --> 00:31:35,460 de koker ned til ganske enkle heuristikk. 713 00:31:35,460 --> 00:31:36,330 >> Så la oss gjøre dette. 714 00:31:36,330 --> 00:31:39,250 Hvis du vil humor meg her, jeg gjorde ta med en haug med stress baller. 715 00:31:39,250 --> 00:31:40,620 Jeg tok en haug med tall. 716 00:31:40,620 --> 00:31:46,562 Og kan vi få bare noen få frivillige å representere 9, 17, 20, 22, 29, og 34? 717 00:31:46,562 --> 00:31:48,270 Så egentlig alle hvem som er her i dag. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 Det var en, to, tre, fire, fem, seks personer. 720 00:31:52,760 --> 00:31:55,740 Og jeg har blitt bedt om å Vær så god se, ingen en på baksiden hever sine hender. 721 00:31:55,740 --> 00:32:01,910 OK, en, to, tre, fire, five-- la meg laste balance-- seks. 722 00:32:01,910 --> 00:32:03,051 OK, du seks Kom opp. 723 00:32:03,051 --> 00:32:04,050 Vi trenger andre mennesker. 724 00:32:04,050 --> 00:32:05,460 Vi tok ekstra stress baller. 725 00:32:05,460 --> 00:32:08,200 Og hvis du kunne, for bare et øyeblikk, linje 726 00:32:08,200 --> 00:32:10,490 dere opp bare som dette bildet her. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> Greit. 729 00:32:15,959 --> 00:32:17,125 La oss se, hva heter du? 730 00:32:17,125 --> 00:32:17,550 >> PUBLIKUM: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> DAVID J. MALAN: Andrew, du er nummer ni. 732 00:32:18,800 --> 00:32:19,540 Hyggelig å møte deg. 733 00:32:19,540 --> 00:32:20,400 Her kan du gå. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 PUBLIKUM: Jen. 736 00:32:22,176 --> 00:32:22,662 DAVID J. MALAN: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Number 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Ja? 741 00:32:25,450 --> 00:32:26,400 >> PUBLIKUM: Jeg er Julia. 742 00:32:26,400 --> 00:32:26,980 >> DAVID J. MALAN: Julia, David. 743 00:32:26,980 --> 00:32:27,545 Nummer 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 PUBLIKUM: Christian. 746 00:32:29,340 --> 00:32:30,715 DAVID J. MALAN: Christian, David. 747 00:32:30,715 --> 00:32:31,541 Number 22. 748 00:32:31,541 --> 00:32:32,040 Og? 749 00:32:32,040 --> 00:32:32,649 >> PUBLIKUM: JP. 750 00:32:32,649 --> 00:32:33,440 DAVID J. MALAN: JP. 751 00:32:33,440 --> 00:32:34,880 Number 29. 752 00:32:34,880 --> 00:32:37,080 Så gå videre og få i-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Standby. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Har noen en markør? 760 00:32:43,682 --> 00:32:44,890 PUBLIKUM: Jeg har en Sharpie. 761 00:32:44,890 --> 00:32:45,660 DAVID J. MALAN: Du fikk en Sharpie? 762 00:32:45,660 --> 00:32:46,159 OK. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 Og er det noen som har et stykke papir? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 Lagre forelesningen. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Kom igjen. 769 00:32:55,362 --> 00:32:56,320 PUBLIKUM: Vi har fått det. 770 00:32:56,320 --> 00:32:57,600 DAVID J. MALAN: Vi fikk den? 771 00:32:57,600 --> 00:32:58,577 Greit, takk. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Here we go. 774 00:33:02,520 --> 00:33:03,582 Var dette fra deg? 775 00:33:03,582 --> 00:33:04,540 Du reddet dagen. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Så 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 Greit. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 Jeg feilstavet 29, men OK. 782 00:33:14,890 --> 00:33:15,720 Gå fremover. 783 00:33:15,720 --> 00:33:18,114 Greit, jeg skal gi deg pennen tilbake et øyeblikk. 784 00:33:18,114 --> 00:33:19,280 Så vi har disse folkene her. 785 00:33:19,280 --> 00:33:20,330 La oss ha en annen. 786 00:33:20,330 --> 00:33:23,750 Gabe, ønsker du å spille det første elementet her? 787 00:33:23,750 --> 00:33:25,705 Vi trenger deg til å peke på disse fine folk. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Så 9, 17, 20, 22, liksom over 29, og deretter 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 Har vi mister noen? 792 00:33:33,325 --> 00:33:33,950 Jeg har en 34. 793 00:33:33,950 --> 00:33:36,730 Hvor did-- OK, som ønsker å være 34? 794 00:33:36,730 --> 00:33:37,605 OK, kom igjen opp, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Greit, vil dette være vel verdt klimaks. 797 00:33:41,220 --> 00:33:41,550 Hva heter du? 798 00:33:41,550 --> 00:33:42,040 >> PUBLIKUM: Peter. 799 00:33:42,040 --> 00:33:43,456 >> DAVID J. MALAN: Peter, kom opp. 800 00:33:43,456 --> 00:33:46,810 Ok, så her er en hel haug med noder. 801 00:33:46,810 --> 00:33:49,060 Hver av dere representerer en av disse rektangler. 802 00:33:49,060 --> 00:33:51,930 Og Gabe, litt merkelig mannen ut, representerer først. 803 00:33:51,930 --> 00:33:54,850 Så hans pekeren er litt mindre på skjermen enn alle andre. 804 00:33:54,850 --> 00:33:58,120 Og i dette tilfellet, hver av venstre hendene skal enten peke ned, 805 00:33:58,120 --> 00:34:01,085 derved representerer null, slik at bare fravær av en peker, 806 00:34:01,085 --> 00:34:03,210 eller det kommer til å peke på en node ved siden av deg. 807 00:34:03,210 --> 00:34:05,440 >> Så akkurat nå hvis du pryde dere som på bildet 808 00:34:05,440 --> 00:34:07,585 her, gå videre og peker på hverandre, med Gabe 809 00:34:07,585 --> 00:34:11,030 spesielt peker på nummer 9 til å representere listen. 810 00:34:11,030 --> 00:34:14,050 OK, og nummer 34, venstre hånd skal bare peke på gulvet. 811 00:34:14,050 --> 00:34:15,750 >> OK, så dette er det lenket liste. 812 00:34:15,750 --> 00:34:17,580 Så dette er scenariet i spørsmålet. 813 00:34:17,580 --> 00:34:20,210 Og ja, dette er representativt av en klasse av problemer 814 00:34:20,210 --> 00:34:21,929 at du kan prøve å løse med kode. 815 00:34:21,929 --> 00:34:25,020 Du vil til slutt sette inn et nytt element i listen. 816 00:34:25,020 --> 00:34:27,494 I dette tilfellet skal vi prøv å sette inn nummer 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Men det kommer til å bli ulike tilfeller å vurdere. 819 00:34:30,860 --> 00:34:34,409 Og ja, dette kommer til å være en av den store bildet gatekjøkken her, er, 820 00:34:34,409 --> 00:34:35,659 hva er de forskjellige sakene. 821 00:34:35,659 --> 00:34:39,120 Hva er det annerledes hvis forholdene eller grener som programmet ditt kan ha? 822 00:34:39,120 --> 00:34:42,024 >> Vel, det nummeret du prøver å innsats, som vi vet nå å være 55, 823 00:34:42,024 --> 00:34:44,650 men hvis du ikke visste på forhånd, daresay jeg 824 00:34:44,650 --> 00:34:47,840 faller inn i minst tre mulige situasjoner. 825 00:34:47,840 --> 00:34:49,717 Der kan et nytt element være? 826 00:34:49,717 --> 00:34:51,050 PUBLIKUM: Og slutten eller midten. 827 00:34:51,050 --> 00:34:54,150 DAVID J. MALAN: På slutten, i midten, eller i begynnelsen. 828 00:34:54,150 --> 00:34:56,650 Så jeg hevder det er minst tre problemer vi må løse. 829 00:34:56,650 --> 00:34:58,691 La oss velge hva som er kanskje uten tvil den enkleste 830 00:34:58,691 --> 00:35:01,090 en, der den nye element hører i begynnelsen. 831 00:35:01,090 --> 00:35:04,040 Så jeg kommer til å ha kode ganske som søker, som jeg nettopp skrev. 832 00:35:04,040 --> 00:35:07,670 Og jeg kommer til å ha ptr, som Jeg skal representere her med min finger, 833 00:35:07,670 --> 00:35:08,370 som vanlig. 834 00:35:08,370 --> 00:35:12,430 >> Og husk, hvilken verdi gjorde vi initial ptr til? 835 00:35:12,430 --> 00:35:15,300 Så vi initialisert det til null i utgangspunktet. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Men så hva gjorde vi når vi var inne i vår søkefunksjon? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 Vi setter den lik første, som betyr ikke gjør dette. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Hvis jeg satt ptr lik første, hva skal min hånd virkelig være å peke på? 842 00:35:30,570 --> 00:35:31,070 Høyre. 843 00:35:31,070 --> 00:35:33,290 Så hvis Gabe og jeg kommer å være like verdier her, 844 00:35:33,290 --> 00:35:34,760 vi trenger både poeng på nummer ni. 845 00:35:34,760 --> 00:35:36,420 >> Så dette var begynnelsen på vår historie. 846 00:35:36,420 --> 00:35:38,700 Og nå er dette bare grei, selv om syntaksen er nytt. 847 00:35:38,700 --> 00:35:40,580 Konseptuelt dette er bare lineær søk. 848 00:35:40,580 --> 00:35:42,750 Er 55 lik 9? 849 00:35:42,750 --> 00:35:45,559 Eller rettere sagt, la oss si mindre enn 9. 850 00:35:45,559 --> 00:35:47,600 Fordi jeg prøver å finne ut hvor du skal plassere 55. 851 00:35:47,600 --> 00:35:51,270 Mindre enn 9 og mindre enn 17, mindre over 20, mindre enn 22 og mindre enn 29. 852 00:35:51,270 --> 00:35:52,510 mindre enn 34, no. 853 00:35:52,510 --> 00:35:55,080 Så nå er vi i tilfelle en av minst tre. 854 00:35:55,080 --> 00:35:59,910 >> Hvis jeg ønsker å sette inn 55 over her, hva linjer med kode behov for å få utført? 855 00:35:59,910 --> 00:36:01,890 Hvordan virker dette bildet av mennesker trenger å forandre? 856 00:36:01,890 --> 00:36:03,181 Hva gjør jeg med min venstre hånd? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 Dette bør være null i utgangspunktet, fordi jeg er på slutten av listen. 859 00:36:07,360 --> 00:36:09,318 Og hva som skal skje her med Peter, var det? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 Han åpenbart kommer til å peke på meg. 862 00:36:12,430 --> 00:36:15,580 Så jeg hevder det er minst to linjer av koden i eksempelkode fra i dag 863 00:36:15,580 --> 00:36:18,570 som kommer til å gjennomføre dette scenario med å legge 55 på halen. 864 00:36:18,570 --> 00:36:20,950 Og kan jeg få noen hop opp og bare representerer 55? 865 00:36:20,950 --> 00:36:22,200 Greit, du er den nye 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> Så nå hva om den neste scenario kommer sammen, 868 00:36:27,054 --> 00:36:29,720 og vi ønsker å sette på begynner eller leder av denne listen? 869 00:36:29,720 --> 00:36:31,100 Og hva er ditt navn, nummer 55? 870 00:36:31,100 --> 00:36:31,420 >> PUBLIKUM: Jack. 871 00:36:31,420 --> 00:36:32,295 >> DAVID J. MALAN: Jack? 872 00:36:32,295 --> 00:36:33,585 OK, hyggelig å møte deg. 873 00:36:33,585 --> 00:36:34,210 Velkommen om bord. 874 00:36:34,210 --> 00:36:36,640 Så nå skal vi sette inn, si, nummer fem. 875 00:36:36,640 --> 00:36:39,840 Her er det andre tilfellet av tre vi kom opp med før. 876 00:36:39,840 --> 00:36:43,050 Så hvis 5 tilhører i begynnelsen, la oss se hvordan vi finne det ut. 877 00:36:43,050 --> 00:36:46,310 Jeg initial min ptr pekeren til nummer 9 igjen. 878 00:36:46,310 --> 00:36:49,140 Og jeg skjønte, oh, 5 er mindre enn 9. 879 00:36:49,140 --> 00:36:50,880 Så fikse dette bilde for oss. 880 00:36:50,880 --> 00:36:54,820 Hvis hender, Gabe eller Davids or-- hva som er nummer ni navn? 881 00:36:54,820 --> 00:36:55,740 >> PUBLIKUM: Jen. 882 00:36:55,740 --> 00:36:58,406 >> DAVID J. MALAN: Jen hands-- hvilke av våre hender må endre? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, så Gabe peker på hva nå? 885 00:37:00,970 --> 00:37:01,640 På meg. 886 00:37:01,640 --> 00:37:02,750 Jeg er den nye noden. 887 00:37:02,750 --> 00:37:04,870 Så jeg vil bare slags trekk her for å se det visuelt. 888 00:37:04,870 --> 00:37:06,435 Og i mellomtiden hvilket punkt jeg gjøre det? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Fortsatt der jeg peker. 891 00:37:09,020 --> 00:37:10,000 Så det er det. 892 00:37:10,000 --> 00:37:13,717 Så bare virkelig en linje med kode rettinger dette spesielle problemet, vil det synes. 893 00:37:13,717 --> 00:37:14,800 Ok, så det er bra. 894 00:37:14,800 --> 00:37:17,580 Og kan noen være en plassholder for 5? 895 00:37:17,580 --> 00:37:18,080 Kom opp. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 Vi skal få deg neste gang. 898 00:37:21,320 --> 00:37:24,280 >> Greit, så now-- og Som en side, navnene 899 00:37:24,280 --> 00:37:28,510 Jeg gjør ikke eksplisitt omtale av retten nå, pred pekeren, forgjenger pekeren 900 00:37:28,510 --> 00:37:31,260 og ny pekeren, det er bare navnene gitt 901 00:37:31,260 --> 00:37:35,280 i eksempelkoden til pekere eller mine hender som er slags peker rundt. 902 00:37:35,280 --> 00:37:36,060 Hva heter du? 903 00:37:36,060 --> 00:37:36,700 >> PUBLIKUM: Christine. 904 00:37:36,700 --> 00:37:37,100 >> DAVID J. MALAN: Christine. 905 00:37:37,100 --> 00:37:38,090 Velkommen om bord. 906 00:37:38,090 --> 00:37:42,180 Ok, så la oss vurdere nå en litt mer irriterende scenario, 907 00:37:42,180 --> 00:37:46,350 der jeg ønsker å sette inn noe sånt som 26 inn i dette. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 Hva? 910 00:37:47,590 --> 00:37:50,510 Disse er-- bra vi har denne pennen. 911 00:37:50,510 --> 00:37:51,955 Greit, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Hvis noen kunne få en annen del av papir klar, bare i case-- all right. 914 00:37:57,570 --> 00:37:58,370 Oh, interessant. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 Vel, dette er et eksempel av et foredrag bug. 917 00:38:02,390 --> 00:38:03,894 OK, så hva heter du igjen? 918 00:38:03,894 --> 00:38:04,560 PUBLIKUM: Julia. 919 00:38:04,560 --> 00:38:07,559 DAVID J. MALAN: Julia, kan du pop ut og late som du aldri har vært der? 920 00:38:07,559 --> 00:38:09,040 OK, dette aldri skjedd. 921 00:38:09,040 --> 00:38:09,680 Takk. 922 00:38:09,680 --> 00:38:12,180 Så antar vi vil sette inn Julia inn i dette lenket liste. 923 00:38:12,180 --> 00:38:13,780 Hun er nummer 20. 924 00:38:13,780 --> 00:38:15,530 Og selvfølgelig hun er kommer til å tilhøre på 925 00:38:15,530 --> 00:38:17,521 begin-- ikke peke på noe ennå. 926 00:38:17,521 --> 00:38:20,020 Så din hånd kan slags være ned null eller noen søppel verdi. 927 00:38:20,020 --> 00:38:21,210 La oss fortelle rask historie. 928 00:38:21,210 --> 00:38:22,980 Jeg peker på nummer fem denne gangen. 929 00:38:22,980 --> 00:38:23,880 Så jeg sjekke ni. 930 00:38:23,880 --> 00:38:25,130 Så jeg sjekke 17. 931 00:38:25,130 --> 00:38:26,247 Så jeg sjekke 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 Og jeg skjønner, ooh, Julia trenger å gå før 22.. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Så hva som må skje? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 Hvis hender må endre? 938 00:38:36,910 --> 00:38:38,360 Julia, gruve, or-- hva heter du igjen? 939 00:38:38,360 --> 00:38:39,230 >> PUBLIKUM: Christian. 940 00:38:39,230 --> 00:38:40,060 >> DAVID J. MALAN: Christian eller? 941 00:38:40,060 --> 00:38:40,560 >> PUBLIKUM: Andy. 942 00:38:40,560 --> 00:38:40,905 >> DAVID J. MALAN: Andy. 943 00:38:40,905 --> 00:38:41,654 Christian eller Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Andy trenger å peke på? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Julia. 948 00:38:47,341 --> 00:38:47,840 Greit. 949 00:38:47,840 --> 00:38:48,960 Så Andy, har du lyst til å peke på Julia? 950 00:38:48,960 --> 00:38:50,120 Men vent litt. 951 00:38:50,120 --> 00:38:53,260 I historien så langt, Jeg er liksom en 952 00:38:53,260 --> 00:38:56,800 ansvaret, i den forstand at pekeren er det som er 953 00:38:56,800 --> 00:38:57,850 beveger seg gjennom listen. 954 00:38:57,850 --> 00:39:00,800 Vi kan ha et navn for Andy, men det er ingen variabel kalt Andy. 955 00:39:00,800 --> 00:39:04,320 Den eneste andre variable vi har er først, hvem representert ved Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Så dette er egentlig hvorfor dermed langt vi ikke har behov for dette. 957 00:39:07,690 --> 00:39:10,846 Men nå på skjermen er nevne igjen av Pred pekeren. 958 00:39:10,846 --> 00:39:11,970 Så la meg være mer eksplisitt. 959 00:39:11,970 --> 00:39:14,820 Hvis dette er pekeren, hadde jeg bedre få litt mer intelligent 960 00:39:14,820 --> 00:39:15,950 om min iterasjon. 961 00:39:15,950 --> 00:39:19,580 Hvis du ikke tankene mine går gjennom her igjen, peker her, peker her. 962 00:39:19,580 --> 00:39:22,500 Men la meg ha en Pred peker, forgjenger pekeren, det er 963 00:39:22,500 --> 00:39:24,740 slags peker på element jeg var bare på. 964 00:39:24,740 --> 00:39:27,330 Så når jeg går her, nå min venstre hånd oppdateringer. 965 00:39:27,330 --> 00:39:29,370 Når jeg går her min venstre hånd oppdateringer. 966 00:39:29,370 --> 00:39:33,090 Og nå har jeg ikke bare en peker til elementet som går etter Julia, 967 00:39:33,090 --> 00:39:36,300 Jeg har fortsatt en peker til Andy, elementet før. 968 00:39:36,300 --> 00:39:39,430 Så du har tilgang, i hovedsak, brødsmuler, om du vil, 969 00:39:39,430 --> 00:39:41,500 til alle de nødvendige pekere. 970 00:39:41,500 --> 00:39:43,710 >> Så hvis jeg peker på Andy og jeg er også peker 971 00:39:43,710 --> 00:39:47,105 på Christian, hvis hender skal nå være påpekt andre steder? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Så Andy kan nå peke på Julia. 974 00:39:51,960 --> 00:39:54,460 Julia kan nå peke på Christian. 975 00:39:54,460 --> 00:39:56,950 Fordi hun kan kopiere min høyre hånd pekeren. 976 00:39:56,950 --> 00:40:00,044 Og som effektivt setter deg tilbake til dette stedet her. 977 00:40:00,044 --> 00:40:02,460 Så kort sagt, selv om dette tar oss slags evig 978 00:40:02,460 --> 00:40:04,510 å faktisk oppdatere en lenket liste, skjønner 979 00:40:04,510 --> 00:40:06,580 at virksomheten er forholdsvis enkel. 980 00:40:06,580 --> 00:40:10,030 Det er av en, to, tre linjer med kode til slutt. 981 00:40:10,030 --> 00:40:12,780 Men pakket rundt dem linjer med kode formodentlig 982 00:40:12,780 --> 00:40:16,350 er litt av logikken som effektivt stiller spørsmålet, hvor er vi? 983 00:40:16,350 --> 00:40:18,970 Er vi i begynnelsen, midten eller slutten? 984 00:40:18,970 --> 00:40:21,890 >> Nå er det absolutt annen operasjonene vi kan iverksette. 985 00:40:21,890 --> 00:40:24,880 Og disse bildene her bare skildre hva vi nettopp gjorde med mennesker. 986 00:40:24,880 --> 00:40:26,080 Hva om fjerning? 987 00:40:26,080 --> 00:40:30,650 Hvis jeg vil, for eksempel, fjerne nummer 34 eller 55, 988 00:40:30,650 --> 00:40:34,680 Jeg kan ha den samme typen kode, men jeg kommer til å trenge ett eller to trinn. 989 00:40:34,680 --> 00:40:36,110 Fordi hva er nytt? 990 00:40:36,110 --> 00:40:40,460 Hvis jeg fjerner noen på slutten, som nummer 55 og deretter 34, 991 00:40:40,460 --> 00:40:42,995 hva har også å endre så jeg gjøre det? 992 00:40:42,995 --> 00:40:44,870 Jeg må ikke evict-- hva heter du igjen? 993 00:40:44,870 --> 00:40:45,380 >> PUBLIKUM: Jack. 994 00:40:45,380 --> 00:40:46,255 >> DAVID J. MALAN: Jack. 995 00:40:46,255 --> 00:40:49,770 Jeg må ikke bare evict-- gratis Jack, så bokstavelig ringe gratis Jack, eller i det minste 996 00:40:49,770 --> 00:40:53,530 pekeren der også, men nå hva som må endres med Peter? 997 00:40:53,530 --> 00:40:55,510 Hånden hans bedre start peker nedover. 998 00:40:55,510 --> 00:40:59,300 Fordi så snart jeg ringe gratis på Jack, hvis Peters fremdeles peker på Jack 999 00:40:59,300 --> 00:41:02,530 og jeg derfor holde traversering listen og få tilgang til denne pekeren, 1000 00:41:02,530 --> 00:41:05,650 det er da vår gamle venn segmentering feil kan faktisk sparke i. 1001 00:41:05,650 --> 00:41:07,860 Fordi vi har gitt minne tilbake til Jack. 1002 00:41:07,860 --> 00:41:10,760 >> Du kan bo der klønete for bare et øyeblikk. 1003 00:41:10,760 --> 00:41:13,410 Fordi vi har bare et par endelige operasjoner for å vurdere. 1004 00:41:13,410 --> 00:41:15,600 Fjerne hodet av listen, eller beginning-- og dette ens 1005 00:41:15,600 --> 00:41:16,349 litt irriterende. 1006 00:41:16,349 --> 00:41:19,640 Fordi vi må vite at Gabe er slags spesielle i dette programmet. 1007 00:41:19,640 --> 00:41:21,440 Fordi ja, har han sin egen pekeren. 1008 00:41:21,440 --> 00:41:24,860 Han er ikke bare å peke på, som er nesten alle andre her. 1009 00:41:24,860 --> 00:41:28,112 >> Så når hodet av listen er fjernet, hvis hender trenger å endre seg nå? 1010 00:41:28,112 --> 00:41:29,070 Hva heter du igjen? 1011 00:41:29,070 --> 00:41:29,450 >> PUBLIKUM: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> DAVID J. MALAN: Jeg er forferdelig ved navn, tilsynelatende. 1013 00:41:31,408 --> 00:41:34,011 Så Christine og Gabe, hvis hender må endre 1014 00:41:34,011 --> 00:41:36,510 når vi prøver å fjerne Christine, nummer fem, fra bildet? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, så la oss gjøre Gabe. 1017 00:41:38,820 --> 00:41:40,950 Gabe kommer til å peke, formodentlig, i nummer ni. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Men hva blir det neste som skal skje? 1020 00:41:44,642 --> 00:41:46,600 PUBLIKUM: Christine bør være null [uhørbart]. 1021 00:41:46,600 --> 00:41:50,244 DAVID J. MALAN: OK, vi burde kanskje make-- jeg hørt "null" et sted. 1022 00:41:50,244 --> 00:41:51,410 PUBLIKUM: Null og gratis henne. 1023 00:41:51,410 --> 00:41:51,855 DAVID J. MALAN: Null hva? 1024 00:41:51,855 --> 00:41:53,074 PUBLIKUM: Null og gratis henne. 1025 00:41:53,074 --> 00:41:54,490 DAVID J. MALAN: Null og gratis henne. 1026 00:41:54,490 --> 00:41:55,422 Så dette er veldig enkelt. 1027 00:41:55,422 --> 00:41:58,380 Og det er perfekt at du er nå liksom av å stå der, ikke tilhørighet. 1028 00:41:58,380 --> 00:42:00,430 Fordi du har vært dekoblet fra listen. 1029 00:42:00,430 --> 00:42:02,820 Du har effektivt blitt foreldreløs fra listen. 1030 00:42:02,820 --> 00:42:07,770 Og så vi hadde bedre ringe gratis nå Christine å gi den minne tilbake. 1031 00:42:07,770 --> 00:42:10,240 Ellers hver gang vi slette en node fra listen 1032 00:42:10,240 --> 00:42:14,230 vi kan være å lage en liste kortere, men faktisk ikke avtagende 1033 00:42:14,230 --> 00:42:15,096 størrelsen i minnet. 1034 00:42:15,096 --> 00:42:17,720 Og så hvis vi fortsetter å legge og legge til, legge ting til listen 1035 00:42:17,720 --> 00:42:19,280 datamaskinen min kan bli tregere og tregere og tregere, 1036 00:42:19,280 --> 00:42:21,740 fordi jeg kjører ut av minne, selv om jeg faktisk ikke 1037 00:42:21,740 --> 00:42:25,580 bruker Christines bytes minne lenger. 1038 00:42:25,580 --> 00:42:28,500 >> Så til slutt er det andre scenarier, av course-- fjerning 1039 00:42:28,500 --> 00:42:30,640 i midten, fjerning på slutten, som vi så. 1040 00:42:30,640 --> 00:42:32,348 Men jo mer interessant Utfordringen nå 1041 00:42:32,348 --> 00:42:34,770 kommer til å være å vurdere nøyaktig hva driftstiden er. 1042 00:42:34,770 --> 00:42:36,640 Så ikke bare kan du holde biter av papir, hvis, Gabe, 1043 00:42:36,640 --> 00:42:38,640 du ville ikke tankene å gi alle en stress ball. 1044 00:42:38,640 --> 00:42:42,100 Takk så mye til vår lenket liste av frivillige her, hvis du kunne. 1045 00:42:42,100 --> 00:42:45,320 >> [APPLAUSE] 1046 00:42:45,320 --> 00:42:46,700 >> DAVID J. MALAN: All right. 1047 00:42:46,700 --> 00:42:51,110 Så et par analytisk spørsmål da, hvis jeg kunne. 1048 00:42:51,110 --> 00:42:59,670 Vi har sett denne notasjonen før, Big O og omega, øvre grenser 1049 00:42:59,670 --> 00:43:02,520 og nedre grenser på kjøretid på noen algoritme. 1050 00:43:02,520 --> 00:43:04,950 Så la oss vurdere bare et par spørsmål. 1051 00:43:04,950 --> 00:43:07,090 >> En, og vi sa det før, hva er driften 1052 00:43:07,090 --> 00:43:10,647 tidspunktet for søk etter en liste i form av stor O? 1053 00:43:10,647 --> 00:43:13,480 Det finnes en øvre grense på løpe tid for å søke en lenket liste 1054 00:43:13,480 --> 00:43:16,340 som gjennomføres av våre frivillige her? 1055 00:43:16,340 --> 00:43:17,820 Det er stor O av n, lineær. 1056 00:43:17,820 --> 00:43:20,630 Fordi i verste fall elementet, slik som 55, 1057 00:43:20,630 --> 00:43:23,830 vi kan være ute etter kan være der Jack var, helt på slutten. 1058 00:43:23,830 --> 00:43:28,250 Og dessverre, i motsetning til en rekke vi kan ikke få fancy denne gangen. 1059 00:43:28,250 --> 00:43:31,820 Selv om alle våre mennesker var sortert fra små elementer, 5, 1060 00:43:31,820 --> 00:43:35,900 hele veien opp til den større del, 55, er det vanligvis en god ting. 1061 00:43:35,900 --> 00:43:38,815 Men hva gjør denne antakelsen ikke lenger tillate oss å gjøre? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 PUBLIKUM: [uhørbart] 1064 00:43:40,650 --> 00:43:40,920 DAVID J. MALAN: Si det igjen? 1065 00:43:40,920 --> 00:43:41,800 PUBLIKUM: Random access. 1066 00:43:41,800 --> 00:43:43,049 DAVID J. MALAN: Random access. 1067 00:43:43,049 --> 00:43:46,330 Og i sin tur betyr det at vi ikke kan gjøre lenger bruke svak nuller, intuisjon, 1068 00:43:46,330 --> 00:43:49,365 og selvfølgelighet å bruke binær søke og splitt og hersk. 1069 00:43:49,365 --> 00:43:51,240 For selv om vi mennesker kunne åpenbart 1070 00:43:51,240 --> 00:43:54,610 se at Andy eller Christian var omtrent i midten av listen, 1071 00:43:54,610 --> 00:43:57,670 Vi vet bare at som en datamaskin ved skimming listen 1072 00:43:57,670 --> 00:43:59,029 helt fra begynnelsen. 1073 00:43:59,029 --> 00:44:00,570 Så vi har gitt opp at random access. 1074 00:44:00,570 --> 00:44:04,380 >> Så stor O av n er nå den øvre bundet på vår søketiden. 1075 00:44:04,380 --> 00:44:07,920 Hva om omega av våre søk? 1076 00:44:07,920 --> 00:44:11,535 Hva er nedre grense på å søke for noen nummer i denne listen? 1077 00:44:11,535 --> 00:44:12,410 PUBLIKUM: [uhørbart] 1078 00:44:12,410 --> 00:44:13,040 DAVID J. MALAN: Si det igjen? 1079 00:44:13,040 --> 00:44:13,420 PUBLIKUM: One. 1080 00:44:13,420 --> 00:44:13,800 DAVID J. MALAN: One. 1081 00:44:13,800 --> 00:44:14,760 Så konstant tid. 1082 00:44:14,760 --> 00:44:17,020 I beste fall er Christine faktisk på begynnelsen av listen. 1083 00:44:17,020 --> 00:44:19,020 Og vi leter etter nummer fem, så vi fant henne. 1084 00:44:19,020 --> 00:44:19,787 Så ingen big deal. 1085 00:44:19,787 --> 00:44:22,370 Men hun er nødt til å være på begynnelsen av listen i dette tilfellet. 1086 00:44:22,370 --> 00:44:23,745 Hva med noe sånt som Slette? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 Hva om du ønsker å slette et element? 1089 00:44:26,300 --> 00:44:29,200 Hva er den øvre grensen og nedre grense om sletting av noe fra en koblet 1090 00:44:29,200 --> 00:44:29,699 listen? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 PUBLIKUM: [uhørbart] 1093 00:44:36,070 --> 00:44:36,420 DAVID J. MALAN: Si det igjen? 1094 00:44:36,420 --> 00:44:37,067 PUBLIKUM: n. 1095 00:44:37,067 --> 00:44:38,900 DAVID J. MALAN: n er faktisk den øvre grensen. 1096 00:44:38,900 --> 00:44:41,700 Fordi i verste fall vi prøver å slette Jack, som vi nettopp gjorde. 1097 00:44:41,700 --> 00:44:43,050 Han er helt på slutten. 1098 00:44:43,050 --> 00:44:45,419 Tar oss alltid, eller n skritt for å finne ham. 1099 00:44:45,419 --> 00:44:46,460 Så det er en øvre grense. 1100 00:44:46,460 --> 00:44:47,430 Det er lineær, sikkert. 1101 00:44:47,430 --> 00:44:50,970 Og den beste fall driftstid, eller nedre grenser i beste fall 1102 00:44:50,970 --> 00:44:51,975 ville være konstant tid. 1103 00:44:51,975 --> 00:44:54,600 Fordi kanskje vi prøver å slette Christine, og vi bare få heldige 1104 00:44:54,600 --> 00:44:55,558 hun er i begynnelsen. 1105 00:44:55,558 --> 00:44:56,350 Vent nå litt. 1106 00:44:56,350 --> 00:44:59,370 Gabe var også i begynnelsen, og vi måtte også oppdatere Gabe. 1107 00:44:59,370 --> 00:45:01,150 Så det var ikke bare ett trinn. 1108 00:45:01,150 --> 00:45:04,210 Så er det faktisk konstant tid, i beste fall 1109 00:45:04,210 --> 00:45:06,345 for å fjerne det minste elementet? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 Det er, selv om det kan være to, tre, eller 100 linjer med kode, 1112 00:45:10,960 --> 00:45:14,000 hvis det er samme antall linjer, ikke i noen loop, 1113 00:45:14,000 --> 00:45:16,577 og uavhengig av størrelsen av listen, absolutt. 1114 00:45:16,577 --> 00:45:18,660 Slette element på begynnelsen av listen, 1115 00:45:18,660 --> 00:45:21,940 selv om vi har å forholde seg til Gabe, er fortsatt konstant tid. 1116 00:45:21,940 --> 00:45:24,220 >> Så dette virker som en massiv skritt bakover. 1117 00:45:24,220 --> 00:45:27,000 Og hva en bortkastet tid hvis, i uke en og uke 1118 00:45:27,000 --> 00:45:30,250 null hadde vi ikke bare pseudokode, men selve koden 1119 00:45:30,250 --> 00:45:35,780 å gjennomføre noe som er log basen n, eller logg, snarere, n, base 2, 1120 00:45:35,780 --> 00:45:37,150 i form av sin driftstid. 1121 00:45:37,150 --> 00:45:40,710 Så hvorfor pokker ville vi ønsker å starte ved hjelp av noe som en lenket liste? 1122 00:45:40,710 --> 00:45:41,517 Yeah. 1123 00:45:41,517 --> 00:45:44,022 >> PUBLIKUM: Så du kan legge til elementer til matrisen. 1124 00:45:44,022 --> 00:45:46,230 DAVID J. MALAN: Så du kan legge til elementer i array. 1125 00:45:46,230 --> 00:45:47,550 Og dette er også tematisk. 1126 00:45:47,550 --> 00:45:49,740 Og vi vil fortsette å se dette, denne avveiingen, mye 1127 00:45:49,740 --> 00:45:51,573 som vi har sett en trade-off med flettingen slag. 1128 00:45:51,573 --> 00:45:54,606 Vi kunne virkelig fremskynde søke eller sortering, heller, 1129 00:45:54,606 --> 00:45:57,480 hvis vi bruke litt mer plass og har en ytterligere del av en minne 1130 00:45:57,480 --> 00:45:58,760 eller en matrise for flettingen slag. 1131 00:45:58,760 --> 00:46:01,270 Men vi bruker mer plass, men vi sparer tid. 1132 00:46:01,270 --> 00:46:04,820 I dette tilfellet er vi gi opp tid, men vi er 1133 00:46:04,820 --> 00:46:08,170 få fleksibilitet, dynamikk om du vil, 1134 00:46:08,170 --> 00:46:10,280 som er uten tvil en positiv funksjon. 1135 00:46:10,280 --> 00:46:11,520 >> Vi er også å bruke plass. 1136 00:46:11,520 --> 00:46:13,710 I hvilken forstand er en koblet liste dyrere 1137 00:46:13,710 --> 00:46:15,700 i form av plass enn en matrise? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 Hvor er den ekstra plassen kommer fra? 1140 00:46:19,920 --> 00:46:20,460 Yeah? 1141 00:46:20,460 --> 00:46:21,800 >> PUBLIKUM: [uhørlig] pekeren. 1142 00:46:21,800 --> 00:46:23,310 >> DAVID J. MALAN: Ja, vi har også pekeren. 1143 00:46:23,310 --> 00:46:25,560 Så dette er minorly irriterende i at det ikke lenger er am 1144 00:46:25,560 --> 00:46:27,780 Jeg lagrer bare en int å representere en int. 1145 00:46:27,780 --> 00:46:30,990 Jeg lagrer en int og en spisser, som også er 32 biter. 1146 00:46:30,990 --> 00:46:33,470 Så jeg bokstavelig talt en dobling hvor mye plass som er involvert. 1147 00:46:33,470 --> 00:46:36,040 Så det er en trade-off, men det er i tilfelle av int. 1148 00:46:36,040 --> 00:46:39,580 Anta at du ikke lagrer int, men antar at hver av disse rektangler 1149 00:46:39,580 --> 00:46:43,290 eller hver av disse menneskene var som representerer et ord, et engelsk ord som 1150 00:46:43,290 --> 00:46:46,430 kan være fem tegn, 10 tegn, kanskje enda mer. 1151 00:46:46,430 --> 00:46:49,940 Deretter legger bare 32 flere biter kan være mindre av en stor avtale. 1152 00:46:49,940 --> 00:46:52,160 >> Hva om hver av elevene i demonstrasjonen 1153 00:46:52,160 --> 00:46:55,107 var bokstavelig talt student structs som har navn og hus og kanskje 1154 00:46:55,107 --> 00:46:57,065 telefonnumre og Twitter håndtak og lignende. 1155 00:46:57,065 --> 00:46:59,564 Så alle feltene vi startet snakker om her om dagen, 1156 00:46:59,564 --> 00:47:02,410 mye mindre av en stor avtale som våre noder få mer interessant 1157 00:47:02,410 --> 00:47:05,972 og stor til å bruke, eh, en ekstra pekeren bare for å koble dem sammen. 1158 00:47:05,972 --> 00:47:07,180 Men ja, det er en trade-off. 1159 00:47:07,180 --> 00:47:09,560 Og ja, er koden mer kompleks, som du vil 1160 00:47:09,560 --> 00:47:11,770 se ved å tråle gjennom det bestemte eksempelet. 1161 00:47:11,770 --> 00:47:14,302 Men hva om det var noen hellige gral her. 1162 00:47:14,302 --> 00:47:17,010 Hva hvis vi ikke tar et skritt bakover, men en massiv skritt fremover 1163 00:47:17,010 --> 00:47:19,180 og implementere en data struktur via som vi 1164 00:47:19,180 --> 00:47:22,870 kan finne elementer som Jack eller Christine eller andre elementer 1165 00:47:22,870 --> 00:47:25,870 i denne matrisen i ekte konstant tid? 1166 00:47:25,870 --> 00:47:26,920 Søk er konstant. 1167 00:47:26,920 --> 00:47:28,320 Slett er konstant. 1168 00:47:28,320 --> 00:47:29,570 Sett er konstant. 1169 00:47:29,570 --> 00:47:32,260 Alle disse operasjonene er konstant. 1170 00:47:32,260 --> 00:47:33,750 Det ville være vår hellige gral. 1171 00:47:33,750 --> 00:47:36,690 Og det er der vi vil ta seg opp neste gang. 1172 00:47:36,690 --> 00:47:38,600 Se deg da. 1173 00:47:38,600 --> 00:47:39,371