1 00:00:00,000 --> 00:00:03,381 >> [Muziek] 2 00:00:03,381 --> 00:00:10,626 3 00:00:10,626 --> 00:00:11,610 >> [VIDEO AFSPELEN] 4 00:00:11,610 --> 00:00:13,640 >> -Hij liegt. 5 00:00:13,640 --> 00:00:14,380 >> -Over wat? 6 00:00:14,380 --> 00:00:17,182 >> Ik weet het niet. 7 00:00:17,182 --> 00:00:19,990 >> -dus Wat weten we? 8 00:00:19,990 --> 00:00:23,145 >> -dat Op 09:15, Ray Santoya was bij de ATM. 9 00:00:23,145 --> 00:00:23,644 -Ja. 10 00:00:23,644 --> 00:00:27,030 Dus de vraag is, wat deed hij op 9:16? 11 00:00:27,030 --> 00:00:29,720 >> -Shooting De 9 millimeter naar iets. 12 00:00:29,720 --> 00:00:31,540 Misschien zag hij de sluipschutter. 13 00:00:31,540 --> 00:00:33,412 >> -of Werkte met hem. 14 00:00:33,412 --> 00:00:34,340 >> -Wacht. 15 00:00:34,340 --> 00:00:36,200 Ga terug een. 16 00:00:36,200 --> 00:00:36,975 >> -Wat zie je? 17 00:00:36,975 --> 00:00:44,400 18 00:00:44,400 --> 00:00:47,805 >> -Breng Zijn gezicht volledig scherm. 19 00:00:47,805 --> 00:00:48,680 >> -zijn Bril. 20 00:00:48,680 --> 00:00:50,060 >> -Er Is een reflectie. 21 00:00:50,060 --> 00:01:00,455 22 00:01:00,455 --> 00:01:02,280 >> -Het Is het Nuevitas honkbalteam. 23 00:01:02,280 --> 00:01:03,110 Dat is hun logo. 24 00:01:03,110 --> 00:01:05,820 >> -En Hij praat wie draagt ​​die jas. 25 00:01:05,820 --> 00:01:06,670 >> [END AFSPELEN] 26 00:01:06,670 --> 00:01:07,628 >> DAVID MALAN: Oké. 27 00:01:07,628 --> 00:01:11,210 Dit is CS50 en dit is een beetje meer van [onverstaanbaar] waarmee je bent 28 00:01:11,210 --> 00:01:12,890 ploeteren met een probleem stellen vier. 29 00:01:12,890 --> 00:01:16,606 Vandaag beginnen we met een beetje meer kijken diep op deze dingen genoemd pointers, 30 00:01:16,606 --> 00:01:18,480 die hoewel het een mooie geheimzinnige onderwerp, 31 00:01:18,480 --> 00:01:20,813 het blijkt dat het gaat de middelen zijn waarmee we 32 00:01:20,813 --> 00:01:24,320 kan beginnen met de bouw en assemblage veel meer geavanceerde programma's. 33 00:01:24,320 --> 00:01:28,150 Maar we deden het op de laatste woensdag door eerste manier van enkele claymation. 34 00:01:28,150 --> 00:01:30,190 Dus dit, herinneren, is Binky en we hem gebruikt 35 00:01:30,190 --> 00:01:33,148 om een ​​blik op een programma te nemen dat niet echt iets interessants, 36 00:01:33,148 --> 00:01:34,950 maar het deed onthullen een paar problemen. 37 00:01:34,950 --> 00:01:38,570 Dus om te beginnen vandaag, waarom hebben we niet lopen snel door een paar van deze stappen, 38 00:01:38,570 --> 00:01:41,920 proberen te destilleren in termen menselijke's precies wat er aan de hand hier 39 00:01:41,920 --> 00:01:45,410 en waarom dit is slecht, en ga dan verder en eigenlijk beginnen met de bouw iets 40 00:01:45,410 --> 00:01:46,309 met deze techniek? 41 00:01:46,309 --> 00:01:48,350 Dus deze waren de eerste twee lijnen in het programma 42 00:01:48,350 --> 00:01:51,340 en in termen van de leek, wat zijn deze twee lijnen aan het doen? 43 00:01:51,340 --> 00:01:55,600 Iemand die redelijk comfortabele met wat is verklaard op het scherm? 44 00:01:55,600 --> 00:01:58,340 45 00:01:58,340 --> 00:02:00,120 Wat zijn die twee lijnen aan het doen? 46 00:02:00,120 --> 00:02:02,070 Het is niet zo anders dan één week, 47 00:02:02,070 --> 00:02:03,611 maar er is een aantal nieuwe speciaal symbool. 48 00:02:03,611 --> 00:02:04,152 Ja? 49 00:02:04,152 --> 00:02:05,628 Terug daar. 50 00:02:05,628 --> 00:02:07,092 >> PUBLIEK: declareren pointers? 51 00:02:07,092 --> 00:02:08,050 DAVID MALAN: weer zeggen? 52 00:02:08,050 --> 00:02:08,860 PUBLIEK: declareren pointers? 53 00:02:08,860 --> 00:02:11,776 DAVID MALAN: declareren pointers en laten we verfijnen het een beetje meer. 54 00:02:11,776 --> 00:02:14,050 PUBLIEK: [onverstaanbaar] mailadres x en dan y. 55 00:02:14,050 --> 00:02:15,300 DAVID MALAN: En dan pakken. 56 00:02:15,300 --> 00:02:18,550 Dus precies wat we doen is we verklaren twee variabelen. 57 00:02:18,550 --> 00:02:21,252 Deze variabelen echter gaan van het type int ster te zijn die 58 00:02:21,252 --> 00:02:23,210 Meer specifiek betekent ze gaan slaan 59 00:02:23,210 --> 00:02:26,450 het adres van een int, respectievelijk x en y. 60 00:02:26,450 --> 00:02:27,660 Nu zijn er nog waarden? 61 00:02:27,660 --> 00:02:32,621 Zijn er werkelijke adressen in deze twee variabelen op dit moment? 62 00:02:32,621 --> 00:02:33,120 Nee. 63 00:02:33,120 --> 00:02:35,030 Het is gewoon zogenaamde garbage waarden. 64 00:02:35,030 --> 00:02:38,120 Als je niet echt wijs een variabele, wat in het RAM was 65 00:02:38,120 --> 00:02:42,224 eerder gaat vullen met nullen en die deze beide variabelen. 66 00:02:42,224 --> 00:02:44,140 Maar we weten nog niet wat ze zijn en dat 67 00:02:44,140 --> 00:02:47,060 gaat de sleutel tot waarom Binky te zijn verloor zijn hoofd vorige week. 68 00:02:47,060 --> 00:02:49,980 >> Dus dit was de claymation incarnatie van deze 69 00:02:49,980 --> 00:02:53,580 waarbij je slechts twee variabelen, kleine ronde stukjes klei, 70 00:02:53,580 --> 00:02:57,330 welke variabelen opslaan, maar de ingepakt pijlen wijzen, 71 00:02:57,330 --> 00:03:00,640 ze zijn niet echt te wijzen overal bekend. 72 00:03:00,640 --> 00:03:03,670 Dus dan hadden we deze lijn, en dit nieuw was vorige week, malloc voor het geheugen 73 00:03:03,670 --> 00:03:07,130 toewijzing, dat is gewoon een mooie manier van het vertellen van het besturingssysteem, Linux 74 00:03:07,130 --> 00:03:09,750 of Mac OS of Windows, hey, geef me wat geheugen, 75 00:03:09,750 --> 00:03:11,780 en alles wat je hoeft te vertellen het besturingssysteem 76 00:03:11,780 --> 00:03:14,699 is wat wanneer vraagt ​​het voor het geheugen. 77 00:03:14,699 --> 00:03:16,990 Het gaat niet schelen wat je gaat doen, 78 00:03:16,990 --> 00:03:19,786 maar je moet naar de operatiekamer te vertellen systeem wat door middel van malloc. 79 00:03:19,786 --> 00:03:20,286 Ja? 80 00:03:20,286 --> 00:03:21,078 >> PUBLIEK: Hoeveel? 81 00:03:21,078 --> 00:03:21,994 DAVID MALAN: Hoeveel? 82 00:03:21,994 --> 00:03:25,280 Hoeveel in bytes, enzovoort, deze weer, een gekunsteld voorbeeld, is gewoon te zeggen, 83 00:03:25,280 --> 00:03:27,360 geef me de grootte van een int. 84 00:03:27,360 --> 00:03:30,550 Nu, de grootte van een int vier bytes of 32 bits. 85 00:03:30,550 --> 00:03:32,850 Dus dit is gewoon een manier van zeggen, hey, het besturingssysteem, 86 00:03:32,850 --> 00:03:37,290 geef me vier bytes van het geheugen die ik kan gebruiken tot mijn beschikking, 87 00:03:37,290 --> 00:03:40,560 en in het bijzonder, wat doet malloc terugkeer met respect 88 00:03:40,560 --> 00:03:41,795 om dat stuk van de vier bytes? 89 00:03:41,795 --> 00:03:44,110 90 00:03:44,110 --> 00:03:44,860 PUBLIEK: Adres? 91 00:03:44,860 --> 00:03:45,901 DAVID MALAN: Het adres. 92 00:03:45,901 --> 00:03:47,580 Het adres van die brok van vier bytes. 93 00:03:47,580 --> 00:03:48,190 Precies. 94 00:03:48,190 --> 00:03:51,430 En dat is wat er uiteindelijk opgeslagen in x en dat is waarom we niet echt 95 00:03:51,430 --> 00:03:55,240 schelen wat het aantal dat adres is, of het nu OX1 of OX2 96 00:03:55,240 --> 00:03:57,110 of een cryptische hexadecimale adres. 97 00:03:57,110 --> 00:03:59,850 Wij geven alleen picturaal dat variabele x is nu 98 00:03:59,850 --> 00:04:01,630 wijst naar dat deel van het geheugen. 99 00:04:01,630 --> 00:04:05,570 Dus de pijl vertegenwoordigt een pointer of specifieker, een geheugenadres. 100 00:04:05,570 --> 00:04:09,120 Maar nogmaals, we meestal niet schelen wat die werkelijke adressen. 101 00:04:09,120 --> 00:04:11,780 Nu, deze lijn zegt wat in lekentaal? 102 00:04:11,780 --> 00:04:14,330 Star x krijgt 42 puntkomma. 103 00:04:14,330 --> 00:04:17,390 Wat betekent dit? 104 00:04:17,390 --> 00:04:18,200 Jij wilt gaan? 105 00:04:18,200 --> 00:04:20,102 Geen krassen op je nek. 106 00:04:20,102 --> 00:04:22,360 >> Doelgroep: Het adres van x op de 42. 107 00:04:22,360 --> 00:04:24,300 >> DAVID MALAN: Het adres van x op 42. 108 00:04:24,300 --> 00:04:25,190 Niet helemaal. 109 00:04:25,190 --> 00:04:28,485 Zo dichtbij, maar niet helemaal, want er is de ster die is voorvoegsel dit x. 110 00:04:28,485 --> 00:04:29,860 Dus moeten we een beetje tweaken. 111 00:04:29,860 --> 00:04:31,032 Ja? 112 00:04:31,032 --> 00:04:36,044 >> Publiek: De waarde die de wijzer x wijst naar is 42. 113 00:04:36,044 --> 00:04:36,710 DAVID MALAN: OK. 114 00:04:36,710 --> 00:04:40,840 De waarde die de wijzer x wijzend naar, laten we zeggen, zijn 42, 115 00:04:40,840 --> 00:04:44,165 of anders gezegd, de ster x zegt, ga dan naar welke adres 116 00:04:44,165 --> 00:04:48,340 is in x, of het nu 1 Oxford Straat of 33 Oxford Street 117 00:04:48,340 --> 00:04:51,850 of OX1 of OX33, ongeacht dat numeriek adres is, 118 00:04:51,850 --> 00:04:54,380 ster x is de dereferentie van x. 119 00:04:54,380 --> 00:04:57,297 Dus ga naar dat adres en zet dan het nummer 42 daar. 120 00:04:57,297 --> 00:04:59,380 Dus dat zou een gelijkwaardige manier om te zeggen dat. 121 00:04:59,380 --> 00:05:01,860 Dus dat is allemaal prima en dan we zouden het beeld vertegenwoordigen 122 00:05:01,860 --> 00:05:05,370 als volgt waar we hebben toegevoegd de 42 die brok vier 123 00:05:05,370 --> 00:05:09,370 bytes aan de rechterkant, maar Deze lijn was, waar ging het mis 124 00:05:09,370 --> 00:05:11,120 en Binky's hoofd schoot uit op dit punt, 125 00:05:11,120 --> 00:05:15,290 omdat slechte dingen gebeuren wanneer je dereference vuilnis waarden 126 00:05:15,290 --> 00:05:18,210 of je dereference ongeldig pointers, en ik zeg ongeldig 127 00:05:18,210 --> 00:05:21,020 omdat op dit punt in de verhaal, wat is de binnenkant van y? 128 00:05:21,020 --> 00:05:24,440 Wat is de waarde van de y gebaseerde over de afgelopen paar stappen? 129 00:05:24,440 --> 00:05:25,360 Ja? 130 00:05:25,360 --> 00:05:26,115 Wat is dat? 131 00:05:26,115 --> 00:05:26,990 >> Publiek: Een adres. 132 00:05:26,990 --> 00:05:28,460 DAVID MALAN: Een adres. 133 00:05:28,460 --> 00:05:31,910 Het moet een adres maar heb ik geïnitialiseerd het? 134 00:05:31,910 --> 00:05:32,800 Dus ik nog niet. 135 00:05:32,800 --> 00:05:35,430 Wat bekend is dat daar? 136 00:05:35,430 --> 00:05:37,590 Het is slechts enkele vuilnis waarde. 137 00:05:37,590 --> 00:05:41,500 Het kan elk adres nul is ten 2 miljard als je twee optredens van RAM-geheugen, 138 00:05:41,500 --> 00:05:44,289 of nul tot 4 miljard als je hebt kreeg vier gigabyte aan RAM-geheugen. 139 00:05:44,289 --> 00:05:46,080 Het is een aantal vuilnis waarde, maar het probleem is 140 00:05:46,080 --> 00:05:48,200 dat het besturingssysteem, als het je niet heeft gegeven 141 00:05:48,200 --> 00:05:51,140 dat stuk van het geheugen specifiek dat je probeert om te gaan, 142 00:05:51,140 --> 00:05:54,650 het is over het algemeen gaat om wat te veroorzaken we hebben gezien als een segmentation fault. 143 00:05:54,650 --> 00:05:57,810 Dus in feite, een van jullie die worstelde op problemen kantooruren 144 00:05:57,810 --> 00:06:00,393 of problemen die eerder over het algemeen met het proberen te achterhalen 145 00:06:00,393 --> 00:06:02,150 een segmentation fault, dat betekent over het algemeen 146 00:06:02,150 --> 00:06:05,017 je bent een deel van het aanraken geheugen dat je niet zou moeten zijn. 147 00:06:05,017 --> 00:06:07,350 Je geheugen raken dat het besturingssysteem niet 148 00:06:07,350 --> 00:06:10,450 mag je aan te raken, of het nu door te gaan te ver in de array 149 00:06:10,450 --> 00:06:12,870 of het starten van nu, of het is omdat je te raken 150 00:06:12,870 --> 00:06:14,780 geheugen dat is gewoon wat vuilnis waarde. 151 00:06:14,780 --> 00:06:18,230 >> Daarbij ster x hier soort undefined gedrag. 152 00:06:18,230 --> 00:06:22,030 Moet je nooit doen het omdat odds worden, is het programma gewoon om te crashen, 153 00:06:22,030 --> 00:06:24,050 omdat je zegt, ga naar dit adres 154 00:06:24,050 --> 00:06:27,000 en je hebt geen idee waar dat adres eigenlijk is. 155 00:06:27,000 --> 00:06:30,300 Dus het besturingssysteem is waarschijnlijk gaat uw programma crashen 156 00:06:30,300 --> 00:06:33,840 als resultaat en inderdaad, dat is wat gebeurde er Binky. 157 00:06:33,840 --> 00:06:37,210 Dus uiteindelijk, Binky vast dit probleem met dit. 158 00:06:37,210 --> 00:06:38,909 Zodat het programma zelf werd ontsierd. 159 00:06:38,909 --> 00:06:41,450 Maar als je een soort van pioniersgeest en uitvoeren van deze lijn in plaats daarvan, 160 00:06:41,450 --> 00:06:45,580 y is gelijk aan x betekent gewoon wat adres is een x, zelfs ook in y. 161 00:06:45,580 --> 00:06:48,740 >> En zo pictorially, we hebben vertegenwoordigde deze met twee pijlen 162 00:06:48,740 --> 00:06:51,570 van x en y uit te wijzen naar dezelfde plaats. 163 00:06:51,570 --> 00:06:55,760 Dus semantisch, x gelijk y omdat deze beide 164 00:06:55,760 --> 00:07:00,300 het opslaan van dezelfde adres, ergo wijzend op 42, 165 00:07:00,300 --> 00:07:04,910 en nu, als je ster zeggen y, ga dan naar het adres in y, 166 00:07:04,910 --> 00:07:06,790 Dit heeft een interessant neveneffect. 167 00:07:06,790 --> 00:07:10,320 Dus het adres in y is de hetzelfde als het adres in x. 168 00:07:10,320 --> 00:07:15,060 Dus als je zegt dat naar het adres in y en verander de waarde tot 13, 169 00:07:15,060 --> 00:07:17,140 wie anders wordt beïnvloed? 170 00:07:17,140 --> 00:07:21,100 X, punt D, om zo te zeggen, moet ook worden beïnvloed. 171 00:07:21,100 --> 00:07:24,340 >> En inderdaad, hoe Nick trok deze foto in claymation was precies dat. 172 00:07:24,340 --> 00:07:28,665 Hoewel we volgen de aanwijzer y, belandden we op dezelfde plaats, 173 00:07:28,665 --> 00:07:32,780 en dus als we waren om af te drukken out x of y's pointee, 174 00:07:32,780 --> 00:07:35,720 dan zouden we de waarde van 13 te zien. 175 00:07:35,720 --> 00:07:37,927 Nu, ik zeg pointee te zijn in overeenstemming met de video. 176 00:07:37,927 --> 00:07:39,760 Programmeurs, mijn kennis, nooit echt 177 00:07:39,760 --> 00:07:42,460 zeggen dat het woord pointee, hetgeen puntig 178 00:07:42,460 --> 00:07:44,650 op, maar voor de consistentie met de video, te realiseren 179 00:07:44,650 --> 00:07:47,520 dat is alles dat was bedoeld in die situatie. 180 00:07:47,520 --> 00:07:54,190 Zodat eventuele vragen over claymation of pointers of malloc gewoon nog niet? 181 00:07:54,190 --> 00:07:54,850 Nee? 182 00:07:54,850 --> 00:07:55,470 Prima. 183 00:07:55,470 --> 00:07:58,560 >> Dus zonder verder omhaal, laten we eens een kijkje 184 00:07:58,560 --> 00:08:00,700 naar waar dit eigenlijk al enige tijd gebruikt. 185 00:08:00,700 --> 00:08:03,580 Dus hebben we dit CS50 bibliotheek had dat heeft al deze functies. 186 00:08:03,580 --> 00:08:06,810 We hebben gebruikt getInt veel, GetString, waarschijnlijk eerder GetLongLong 187 00:08:06,810 --> 00:08:09,840 in mijn Pset één of zo, maar wat er daadwerkelijk aan de hand? 188 00:08:09,840 --> 00:08:12,920 Nou, laten we eens een snelle blik onder de motorkap van een programma dat 189 00:08:12,920 --> 00:08:17,017 inspireert Daarom geven wij u de CS50 bibliotheek, en inderdaad met ingang van vorige week, 190 00:08:17,017 --> 00:08:18,850 we begonnen met het nemen van die zijwieltjes af. 191 00:08:18,850 --> 00:08:21,080 Dus dit is nu gesorteerd een postmortem wat 192 00:08:21,080 --> 00:08:23,690 is er aan de hand in de CS50 bibliotheek, 193 00:08:23,690 --> 00:08:27,250 hoewel we nu beginnen te bewegen weg van het voor de meeste programma's. 194 00:08:27,250 --> 00:08:29,460 >> Dus dit is een programma genaamd scanf 0. 195 00:08:29,460 --> 00:08:30,510 Het is super kort. 196 00:08:30,510 --> 00:08:33,909 Het heeft alleen deze lijnen, maar introduceert een functie genaamd scanf 197 00:08:33,909 --> 00:08:36,909 dat we eigenlijk gaan zien in een moment binnen de CS50 bibliotheek 198 00:08:36,909 --> 00:08:38,600 zij het in iets andere vorm. 199 00:08:38,600 --> 00:08:41,330 Dus dit programma op lijn 16 is waarbij een variabele x. 200 00:08:41,330 --> 00:08:43,150 Dus geef me vier bytes voor een int. 201 00:08:43,150 --> 00:08:45,750 Het is verteld gebruiker, nummer kunt u, en dan 202 00:08:45,750 --> 00:08:49,010 Dit is een interessante lijn die stropdassen eigenlijk elkaar vorige week 203 00:08:49,010 --> 00:08:49,790 en dit. 204 00:08:49,790 --> 00:08:53,230 Scanf, en dan ziet het duurt een format string, net als printf, 205 00:08:53,230 --> 00:08:57,480 % i betekent een int, en dan duurt het een tweede argument dat ziet er een beetje 206 00:08:57,480 --> 00:08:58,260 funky. 207 00:08:58,260 --> 00:09:01,880 Het is ampersand x, en te herinneren, zagen we alleen deze keer vorige week. 208 00:09:01,880 --> 00:09:03,465 Wat betekent ampersand x vertegenwoordigen? 209 00:09:03,465 --> 00:09:06,210 210 00:09:06,210 --> 00:09:08,450 Wat doet ampersand doen in C? 211 00:09:08,450 --> 00:09:08,950 Ja? 212 00:09:08,950 --> 00:09:10,024 >> Doelgroep: Het adres van. 213 00:09:10,024 --> 00:09:11,190 DAVID MALAN: Het adres van. 214 00:09:11,190 --> 00:09:13,190 Dus het is het tegenovergestelde van de ster exploitant, 215 00:09:13,190 --> 00:09:17,270 terwijl de ster operator zegt, ga dan naar dit adres, de ampersand operator 216 00:09:17,270 --> 00:09:20,280 zegt figuur uit de adres van deze variabele, 217 00:09:20,280 --> 00:09:23,530 en dus dit is de sleutel, omdat scanf doel in het leven 218 00:09:23,530 --> 00:09:26,320 is het scannen van de gebruiker input van het toetsenbord, 219 00:09:26,320 --> 00:09:29,970 Afhankelijk van wat hij of zij types en lees vervolgens ingang van die gebruiker 220 00:09:29,970 --> 00:09:32,970 een variabele, maar we zag in de afgelopen twee weken 221 00:09:32,970 --> 00:09:36,080 dat swap-functie die we moeiteloos probeerde uit te voeren 222 00:09:36,080 --> 00:09:37,110 was gewoon kapot. 223 00:09:37,110 --> 00:09:42,470 Bedenk dat met de swap-functie, als we alleen maar verklaard A en B als ints, 224 00:09:42,470 --> 00:09:47,040 we hebben met succes de verwisselen twee variabelen binnenkant van swap 225 00:09:47,040 --> 00:09:50,080 net als met de melk en wat fruitsap, maar zodra swap terug, 226 00:09:50,080 --> 00:09:55,200 wat het resultaat ten opzichte tot x en y, de oorspronkelijke waarden? 227 00:09:55,200 --> 00:09:55,700 Niets. 228 00:09:55,700 --> 00:09:56,200 Ja. 229 00:09:56,200 --> 00:09:59,754 Er is niets gebeurd dat moment, omdat swaps veranderen alleen de lokale kopieën, 230 00:09:59,754 --> 00:10:01,670 dat wil zeggen, alle deze keer, wanneer we hebben 231 00:10:01,670 --> 00:10:04,010 al passeren in argumenten aan functies, we zijn 232 00:10:04,010 --> 00:10:05,939 gewoon passeren kopieën van deze argumenten. 233 00:10:05,939 --> 00:10:07,980 Je kunt doen met die wat je wilt met hen, 234 00:10:07,980 --> 00:10:10,890 maar ze gaan niet hebben Effect op de oorspronkelijke waarden. 235 00:10:10,890 --> 00:10:13,650 Dus dit is problematisch als je willen een functie als scanf hebben 236 00:10:13,650 --> 00:10:17,170 in het leven, waarvan het doel is om te scannen invoer van de gebruiker via het toetsenbord 237 00:10:17,170 --> 00:10:22,010 en vervolgens in de lege plekken vullen, om zo te spreken, dat wil zeggen, geef een variabele als x 238 00:10:22,010 --> 00:10:25,410 een waarde, want als ik tot net voorbij x om scanf, 239 00:10:25,410 --> 00:10:28,790 als je de logica van de laatste overwegen week, kan scanf doen wat het wil 240 00:10:28,790 --> 00:10:33,100 met een kopie van x, maar het kon niet permanent x veranderen, tenzij we geven 241 00:10:33,100 --> 00:10:37,120 scanf een schatkaart, om zo te zeggen, waarbij x markeert de plek, waarbij 242 00:10:37,120 --> 00:10:41,860 passeren we het adres van x zodat scanf kan er en eigenlijk verandering gaan 243 00:10:41,860 --> 00:10:42,920 de waarde van x. 244 00:10:42,920 --> 00:10:45,080 Zo ja, alle dat dit programma doet 245 00:10:45,080 --> 00:10:53,180 als ik scanf 0, in mijn bron 5m directory, maken scanf 0, 246 00:10:53,180 --> 00:10:57,730 dot slash scanf, nummer Neem 50, bedankt voor de 50. 247 00:10:57,730 --> 00:11:01,020 >> Dus het is niet zo interessant, maar wat er werkelijk gebeurt 248 00:11:01,020 --> 00:11:04,820 is dat zodra ik noem scanf hier de waarde van x 249 00:11:04,820 --> 00:11:06,410 wordt permanent gewijzigd. 250 00:11:06,410 --> 00:11:08,335 Nu, dit lijkt mooi en goed, en in feite 251 00:11:08,335 --> 00:11:11,200 lijkt alsof we niet echt nodig de CS50 bibliotheek helemaal niet meer. 252 00:11:11,200 --> 00:11:13,960 Bijvoorbeeld, laten we lopen dit hier eens te meer. 253 00:11:13,960 --> 00:11:15,750 Laat me heropenen voor een tweede. 254 00:11:15,750 --> 00:11:20,600 Laten we proberen een aantal aub en in plaats van te zeggen 50 zoals voorheen, 255 00:11:20,600 --> 00:11:22,810 laten we gewoon nee zeggen. 256 00:11:22,810 --> 00:11:24,000 OK, dat is een beetje raar. 257 00:11:24,000 --> 00:11:25,270 OK. 258 00:11:25,270 --> 00:11:28,680 En slechts enkele onzin hier. 259 00:11:28,680 --> 00:11:31,170 Dus het lijkt niet te handvat verkeerde situaties. 260 00:11:31,170 --> 00:11:33,620 Dus moeten we start minimaal het toevoegen van enkele foutcontrole 261 00:11:33,620 --> 00:11:37,460 om ervoor te zorgen dat de gebruiker getypt in een werkelijke aantal, zoals 50, 262 00:11:37,460 --> 00:11:40,720 want blijkbaar het typen van woorden wordt niet herkend als problematisch, 263 00:11:40,720 --> 00:11:42,020 maar waarschijnlijk moet zijn. 264 00:11:42,020 --> 00:11:46,450 >> Laten we eens kijken naar deze versie nu is dat mijn poging om herimplementeren GetString. 265 00:11:46,450 --> 00:11:48,437 Als scanf heeft dit alles functionaliteit ingebouwd, 266 00:11:48,437 --> 00:11:51,270 Daarom hebben we ploeteren met deze zijwieltjes zoals GetString? 267 00:11:51,270 --> 00:11:55,450 Nou, hier is misschien wel mijn eigen eenvoudige versie van GetString 268 00:11:55,450 --> 00:12:00,766 waarbij een week geleden, zou ik heb gezegd, geef me een string en noem het bufferen. 269 00:12:00,766 --> 00:12:03,390 Vandaag, ga ik gewoon beginnen zeggende char ster, die, herinneren, 270 00:12:03,390 --> 00:12:04,400 het is gewoon een synoniem. 271 00:12:04,400 --> 00:12:06,629 Het ziet er enger, maar het is precies hetzelfde. 272 00:12:06,629 --> 00:12:09,420 Dus geef me een variabele genaamd buffer dat gaat om een ​​string op te slaan, 273 00:12:09,420 --> 00:12:12,780 vertel de gebruiker snaar alsjeblieft, en dan, net als vroeger, 274 00:12:12,780 --> 00:12:17,760 laten we proberen om deze les te lenen scanf % s deze tijd en dan pas in buffer. 275 00:12:17,760 --> 00:12:19,310 Nu, een snelle sanity check. 276 00:12:19,310 --> 00:12:22,120 Waarom ben ik niet te zeggen ampersand buffer deze tijd? 277 00:12:22,120 --> 00:12:25,190 278 00:12:25,190 --> 00:12:26,625 Afleiden uit het vorige voorbeeld. 279 00:12:26,625 --> 00:12:28,000 Publiek: Char ster is een pointer. 280 00:12:28,000 --> 00:12:29,920 DAVID MALAN: Precies, want deze keer, char 281 00:12:29,920 --> 00:12:34,080 ster is al een pointer, een adres, per definitie van die ster daar. 282 00:12:34,080 --> 00:12:37,530 En als scanf verwacht een adres, volstaat gewoon om te passeren in buffer. 283 00:12:37,530 --> 00:12:39,260 Ik hoef niet te ampersand buffer zeggen. 284 00:12:39,260 --> 00:12:42,177 Voor de nieuwsgierigen, je kon zoiets als dit te doen. 285 00:12:42,177 --> 00:12:43,510 Het zou andere betekenis hebben. 286 00:12:43,510 --> 00:12:47,240 Dit zou een pointer geven u een pointer, die eigenlijk 287 00:12:47,240 --> 00:12:50,050 een geldige ding C, maar nu, laten we het simpel houden 288 00:12:50,050 --> 00:12:51,750 en houdt het verhaal consistent. 289 00:12:51,750 --> 00:12:54,100 Ik ga gewoon in passeren buffer en dat klopt. 290 00:12:54,100 --> 00:12:56,487 Het probleem is echter dit. 291 00:12:56,487 --> 00:12:58,820 Laat me gaan en uitvoeren van deze programma na de compilatie. 292 00:12:58,820 --> 00:13:00,902 Maken scanf 1. 293 00:13:00,902 --> 00:13:02,610 Verdomme, mijn compiler mijn fout te vangen. 294 00:13:02,610 --> 00:13:04,090 Geef me een seconde. 295 00:13:04,090 --> 00:13:05,460 Clang. 296 00:13:05,460 --> 00:13:06,990 Laten we zeggen dat scanf-1.c. 297 00:13:06,990 --> 00:13:10,880 298 00:13:10,880 --> 00:13:11,380 OK. 299 00:13:11,380 --> 00:13:12,720 Daar gaan we. 300 00:13:12,720 --> 00:13:14,280 Ik heb het nodig. 301 00:13:14,280 --> 00:13:16,750 CS50 ID heeft verschillende instellingen 302 00:13:16,750 --> 00:13:18,280 dat u te beschermen tegen jezelf. 303 00:13:18,280 --> 00:13:21,300 Ik moest deze door te schakelen running clang handmatig deze tijd. 304 00:13:21,300 --> 00:13:22,140 Dus touwtje alsjeblieft. 305 00:13:22,140 --> 00:13:25,560 Ik ga om te gaan en typ in mijn favoriete hello wereld. 306 00:13:25,560 --> 00:13:26,490 OK, null. 307 00:13:26,490 --> 00:13:27,700 Dat is niet wat ik typte. 308 00:13:27,700 --> 00:13:29,690 Dus het is een indicatie van iets dat verkeerd. 309 00:13:29,690 --> 00:13:33,920 Laat me ga je gang en typ in een heel lange string. 310 00:13:33,920 --> 00:13:37,210 Bedankt voor de nul en ik weet het niet als ik ga in staat zijn om het te crashen. 311 00:13:37,210 --> 00:13:40,240 Laten we proberen een beetje kopie plakken en zien of dit helpt. 312 00:13:40,240 --> 00:13:43,290 Plakt gewoon een veel van. 313 00:13:43,290 --> 00:13:47,310 Het is zeker een groter snaar dan normaal. 314 00:13:47,310 --> 00:13:51,450 Laten we gewoon echt schrijven. 315 00:13:51,450 --> 00:13:51,950 Nee. 316 00:13:51,950 --> 00:13:52,650 Verdomme. 317 00:13:52,650 --> 00:13:53,480 Opdracht niet gevonden. 318 00:13:53,480 --> 00:13:54,550 Dus dat is niet gerelateerd. 319 00:13:54,550 --> 00:13:56,440 Dat is omdat ik geplakt een aantal slechte personages, 320 00:13:56,440 --> 00:13:59,780 maar dit blijkt niet gaat werken. 321 00:13:59,780 --> 00:14:03,510 >> Laten we proberen dit eens te meer, omdat het is leuker als we eigenlijk crashen. 322 00:14:03,510 --> 00:14:09,116 Laten we dit type en nu, ik ben gaan een echt lange reeks kopiëren 323 00:14:09,116 --> 00:14:10,990 en nu laten we eens kijken of we kan dit ding crashen. 324 00:14:10,990 --> 00:14:14,235 Let op, ik weggelaten ruimten en nieuwe lijnen en puntkomma 325 00:14:14,235 --> 00:14:16,035 en alle funky karakters. 326 00:14:16,035 --> 00:14:16,535 Enter. 327 00:14:16,535 --> 00:14:21,090 328 00:14:21,090 --> 00:14:22,880 En nu het netwerk is gewoon te traag. 329 00:14:22,880 --> 00:14:27,460 Ik ingedrukt Command-V te lang duidelijk. 330 00:14:27,460 --> 00:14:28,190 Verdomme! 331 00:14:28,190 --> 00:14:29,260 Opdracht niet gevonden. 332 00:14:29,260 --> 00:14:29,780 >> OK. 333 00:14:29,780 --> 00:14:32,240 Nou, het punt is niettemin de volgende. 334 00:14:32,240 --> 00:14:36,910 Dus wat er werkelijk gaande is op bij deze verklaring aan 335 00:14:36,910 --> 00:14:39,240 van char ster buffer op lijn 16? 336 00:14:39,240 --> 00:14:41,820 Dus wat ben ik het krijgen toen ik verklaren een pointer? 337 00:14:41,820 --> 00:14:47,440 Alles wat ik krijg is een vier byte waarde genaamd buffer, maar wat erin 338 00:14:47,440 --> 00:14:49,540 op dit moment? 339 00:14:49,540 --> 00:14:50,930 Het is slechts enkele vuilnis waarde. 340 00:14:50,930 --> 00:14:54,170 Omdat elke keer dat u een variabele declareert in C, het is slechts enkele vuilnis waarde, 341 00:14:54,170 --> 00:14:56,220 en we beginnen te tocht over deze realiteit. 342 00:14:56,220 --> 00:14:59,720 Nu, als ik zeg scanf, ga naar dit adres 343 00:14:59,720 --> 00:15:01,520 en zetten wat de gebruiker types in. 344 00:15:01,520 --> 00:15:06,400 Als de gebruiker types in hello wereld, goed, waar moet ik het zeggen? 345 00:15:06,400 --> 00:15:07,750 Buffer is een vuilnisbak waarde. 346 00:15:07,750 --> 00:15:11,510 >> Dus dat is net zoiets als een pijl dat is te wijzen wie weet waar. 347 00:15:11,510 --> 00:15:13,880 Misschien is het te wijzen hier in mijn geheugen. 348 00:15:13,880 --> 00:15:16,560 En dus wanneer de gebruiker types in Hallo wereld, 349 00:15:16,560 --> 00:15:22,380 het programma probeert de zetten touwtje hello wereld backslash 0 350 00:15:22,380 --> 00:15:23,910 in dat stuk van het geheugen. 351 00:15:23,910 --> 00:15:27,070 Maar met een hoge waarschijnlijkheid, maar duidelijk niet 100% waarschijnlijkheid, 352 00:15:27,070 --> 00:15:30,440 de computer gaat vervolgens crashen het programma, omdat deze niet 353 00:15:30,440 --> 00:15:32,490 herinnering die ik zou moeten worden toegestaan ​​aan te raken. 354 00:15:32,490 --> 00:15:36,330 Dus in het kort, dit programma is gebrekkig precies die reden. 355 00:15:36,330 --> 00:15:38,070 Ik ben fundamenteel niet wat te doen? 356 00:15:38,070 --> 00:15:42,366 Welke stappen heb ik weggelaten, net als we weggelaten met eerste voorbeeld Binky's? 357 00:15:42,366 --> 00:15:42,866 Ja? 358 00:15:42,866 --> 00:15:43,710 >> PUBLIEK: toewijzing geheugen? 359 00:15:43,710 --> 00:15:45,001 >> DAVID MALAN: toewijzing geheugen. 360 00:15:45,001 --> 00:15:48,400 Ik heb eigenlijk niet toegewezen elke herinnering voor die string. 361 00:15:48,400 --> 00:15:50,270 Dus we kunnen dit oplossen in een paar manieren. 362 00:15:50,270 --> 00:15:52,700 One, kunnen we het simpel houden en in feite, nu ben je 363 00:15:52,700 --> 00:15:55,116 gaan om te beginnen met een vervaging zien van de lijnen tussen wat 364 00:15:55,116 --> 00:15:58,520 een array is, wat een string is, wat een char ster is, wat een array van chars 365 00:15:58,520 --> 00:15:59,020 is. 366 00:15:59,020 --> 00:16:02,450 Hier is een tweede voorbeeld met strijkers en kennisgeving 367 00:16:02,450 --> 00:16:05,690 alles wat ik heb gedaan op de lijn 16 is, in plaats van te zeggen 368 00:16:05,690 --> 00:16:09,530 die buffer gaat om een ​​klusje te zijn ster, een verwijzing naar een stuk van het geheugen, 369 00:16:09,530 --> 00:16:14,057 Ik ga zeer proactief te geven mezelf een buffer voor 16 tekens, 370 00:16:14,057 --> 00:16:16,390 en in feite, als je bekend bent de term buffering, 371 00:16:16,390 --> 00:16:20,570 waarschijnlijk uit de wereld van video's, wanneer een video buffering, buffering, 372 00:16:20,570 --> 00:16:21,175 buffering. 373 00:16:21,175 --> 00:16:22,550 Nou, wat is hier het verband? 374 00:16:22,550 --> 00:16:24,960 Nou, Binnenkant van YouTube en de binnenkant van videospelers 375 00:16:24,960 --> 00:16:27,200 algemeen een matrix dat is groter dan 16. 376 00:16:27,200 --> 00:16:30,340 Het kan een matrix van een omvang zijn megabyte, misschien 10 megabytes, 377 00:16:30,340 --> 00:16:34,330 en in die array heeft uw browser downloaden van een hele hoop van bytes, 378 00:16:34,330 --> 00:16:37,500 een hele hoop megabytes video en de video-speler, 379 00:16:37,500 --> 00:16:40,930 YouTube of wie dan ook is, begint het lezen van de bytes van die array, 380 00:16:40,930 --> 00:16:43,530 en elke keer zie je de woord buffering, buffering, 381 00:16:43,530 --> 00:16:46,350 dat betekent dat de speler gekregen om het einde van die matrix. 382 00:16:46,350 --> 00:16:50,430 Het netwerk is zo traag dat het niet bijgevuld de array met meer bytes 383 00:16:50,430 --> 00:16:55,610 en dus je bent bits weergeven aan de gebruiker. 384 00:16:55,610 --> 00:16:59,430 >> Dus buffer is een passende term hier in die het is gewoon een array, een stuk van het geheugen. 385 00:16:59,430 --> 00:17:02,530 En dit zal het te repareren want het blijkt 386 00:17:02,530 --> 00:17:07,410 dat je arrays kunnen behandelen alsof ze zijn adressen, hoewel buffer 387 00:17:07,410 --> 00:17:10,710 is slechts een symbool, het is een reeks tekens, buffer, 388 00:17:10,710 --> 00:17:14,760 dat is handig voor mij, de programmeur, U kunt de naam rond passeren 389 00:17:14,760 --> 00:17:17,079 alsof het een pointer, alsof het 390 00:17:17,079 --> 00:17:21,000 waren het adres van een brok geheugen voor 16 tekens. 391 00:17:21,000 --> 00:17:24,530 Dus dat is te zeggen, kan ik pas de scanf precies dat woord 392 00:17:24,530 --> 00:17:30,670 en dus nu, als ik dit programma, maken scanf 2, dot slash scanf 2, 393 00:17:30,670 --> 00:17:35,386 en typ in Hallo wereld, Enter, dat tijd-- 394 00:17:35,386 --> 00:17:37,590 >> Hmm, wat is er gebeurd? 395 00:17:37,590 --> 00:17:39,340 String alsjeblieft. 396 00:17:39,340 --> 00:17:41,430 Wat heb ik verkeerd gedaan? 397 00:17:41,430 --> 00:17:43,800 Hallo wereld, buffer. 398 00:17:43,800 --> 00:17:44,705 Hallo Wereld. 399 00:17:44,705 --> 00:17:48,201 400 00:17:48,201 --> 00:17:49,420 Ah, ik weet wat het doet. 401 00:17:49,420 --> 00:17:49,920 OK. 402 00:17:49,920 --> 00:17:51,628 Dus het is het lezen tot de eerste ruimte. 403 00:17:51,628 --> 00:17:55,680 Dus laten we cheat voor slechts een moment en zeg ik wilde alleen maar om iets te typen 404 00:17:55,680 --> 00:18:01,408 echt lang als dit is een lange zin dat één, twee, drie, vier, vijf, 405 00:18:01,408 --> 00:18:04,420 zes, zeven, acht, negen, 10, 11, 12, 13, 14, 15, 16. 406 00:18:04,420 --> 00:18:05,300 OK. 407 00:18:05,300 --> 00:18:07,600 Het is inderdaad een lange zin. 408 00:18:07,600 --> 00:18:10,710 Dus deze zin is langer dan 16 tekens 409 00:18:10,710 --> 00:18:13,670 en dus toen ik druk op Enter, wat er gaat gebeuren? 410 00:18:13,670 --> 00:18:16,940 Welnu, in dit geval de verhaal, ik had verklaard buffer 411 00:18:16,940 --> 00:18:22,190 om daadwerkelijk een array met 16 tekens klaar om te gaan. 412 00:18:22,190 --> 00:18:27,426 Zo één, twee, drie, vier, vijf, zes, zeven, acht, negen, 10, 11, 12, 13, 14, 413 00:18:27,426 --> 00:18:29,440 15, 16. 414 00:18:29,440 --> 00:18:34,410 Zo 16 tekens, en nu, toen ik lees in iets als dit is een lange 415 00:18:34,410 --> 00:18:43,950 zin, wat er gaat gebeuren is dat ik ga lezen is dit een lange 416 00:18:43,950 --> 00:18:49,660 S-E-N-t-E-N-C-E, zin. 417 00:18:49,660 --> 00:18:52,270 >> Dus dit is bewust een slechte zaak dat ik 418 00:18:52,270 --> 00:18:55,060 blijven schrijven buiten de grenzen van mijn array, 419 00:18:55,060 --> 00:18:56,660 de grenzen van mijn buffer. 420 00:18:56,660 --> 00:19:00,100 Ik zou je geluk en het programma zal blijven lopen en niet schelen, 421 00:19:00,100 --> 00:19:03,450 maar in het algemeen, dit zal inderdaad mijn programma crashen, 422 00:19:03,450 --> 00:19:06,440 en het is een bug in mijn coderen het moment dat ik stap 423 00:19:06,440 --> 00:19:08,576 de grenzen van die array, omdat ik 424 00:19:08,576 --> 00:19:10,450 weet niet of het is se gaan crashen 425 00:19:10,450 --> 00:19:12,120 of als ik ga gewoon geluk te krijgen. 426 00:19:12,120 --> 00:19:15,750 Dus dit is problematisch omdat dit geval lijkt het te werken 427 00:19:15,750 --> 00:19:20,931 en laten verleiden lot hier, ook al de IDE lijkt wel een beetje te tolereren 428 00:19:20,931 --> 00:19:21,430 van-- 429 00:19:21,430 --> 00:19:22,040 >> Daar gaan we. 430 00:19:22,040 --> 00:19:23,240 Eindelijk. 431 00:19:23,240 --> 00:19:26,470 Dus ik ben de enige die dit kan zien. 432 00:19:26,470 --> 00:19:29,630 Dus ik had net een heleboel plezier te typen een heel lange eigenlijke zin 433 00:19:29,630 --> 00:19:32,800 dat het zeker overschreden 16 bytes, omdat ik 434 00:19:32,800 --> 00:19:38,050 getypt in deze gekke lange multi-lijn uitdrukking, en dan merken wat er gebeurd is. 435 00:19:38,050 --> 00:19:41,110 Het programma probeerde af te drukken en kreeg vervolgens een segmentation fault 436 00:19:41,110 --> 00:19:44,430 en segmentatie fouten is wanneer zoiets gebeurt 437 00:19:44,430 --> 00:19:47,650 en het besturingssysteem zegt nee, niet dat het geheugen aanraakt. 438 00:19:47,650 --> 00:19:49,570 We gaan om te doden het programma geheel. 439 00:19:49,570 --> 00:19:51,180 >> Dus dit lijkt problematisch. 440 00:19:51,180 --> 00:19:54,540 Ik heb het programma waarbij verbeterd op zijn minst wat geheugen, 441 00:19:54,540 --> 00:19:58,000 maar dit lijkt te beperken de functie GetString te krijgen 442 00:19:58,000 --> 00:20:00,780 snaren van een aantal eindige lengte 16. 443 00:20:00,780 --> 00:20:04,200 Dus als je langer wilt steunen zinnen dan 16 tekens, 444 00:20:04,200 --> 00:20:04,880 wat doe je? 445 00:20:04,880 --> 00:20:07,970 Nou, je kunt verhogen maat van deze buffer tot 32 446 00:20:07,970 --> 00:20:09,190 of dat lijkt soort kort. 447 00:20:09,190 --> 00:20:12,260 Waarom doen we niet alleen te maken Het 1000 maar terug te duwen. 448 00:20:12,260 --> 00:20:17,100 Wat is de reactie van intuïtief alleen dit probleem te vermijden door het maken van 449 00:20:17,100 --> 00:20:20,660 mijn buffer groter, net als 1000 tekens? 450 00:20:20,660 --> 00:20:23,470 Door de implementatie van getString deze manier. 451 00:20:23,470 --> 00:20:27,130 Wat is goed of slecht hier? 452 00:20:27,130 --> 00:20:28,033 Ja? 453 00:20:28,033 --> 00:20:30,574 Publiek: Als je te binden een heleboel van de ruimte en je hoeft niet te gebruiken, 454 00:20:30,574 --> 00:20:33,500 dan kun je niet opnieuw toewijzen die ruimte. 455 00:20:33,500 --> 00:20:34,500 DAVID MALAN: Absoluut. 456 00:20:34,500 --> 00:20:38,480 Het is verspilling voor zover als je niet eigenlijk moeten 900 van die bytes 457 00:20:38,480 --> 00:20:41,057 en toch je vraagt 1000 in totaal toch, 458 00:20:41,057 --> 00:20:44,140 je bent gewoon consumeren meer geheugen op computer van de gebruiker dan moet je, 459 00:20:44,140 --> 00:20:45,740 en tenslotte een deel van je al bent tegengekomen 460 00:20:45,740 --> 00:20:47,620 in het leven dat als je loopt veel programma's 461 00:20:47,620 --> 00:20:50,470 en ze zijn het eten van veel geheugen, dit kan eigenlijk invloed op de prestaties 462 00:20:50,470 --> 00:20:52,220 en de ervaring van de gebruiker op de computer. 463 00:20:52,220 --> 00:20:56,090 Dus dat is een soort van een luie oplossing, zeker, en omgekeerd, 464 00:20:56,090 --> 00:21:00,140 het is niet alleen verspilling, welk probleem blijft, zelfs als ik mijn buffer 465 00:21:00,140 --> 00:21:02,100 1000? 466 00:21:02,100 --> 00:21:02,600 Ja? 467 00:21:02,600 --> 00:21:04,475 >> Publiek: De string is lengte 1001. 468 00:21:04,475 --> 00:21:05,350 DAVID MALAN: Precies. 469 00:21:05,350 --> 00:21:08,280 Als uw string lengte 1001, je precies hetzelfde probleem hebt, 470 00:21:08,280 --> 00:21:10,705 en door mijn betoog, zou ik gewoon maken het 2000 toen, 471 00:21:10,705 --> 00:21:12,830 maar je weet niet in vooraf hoe groot het zou moeten zijn, 472 00:21:12,830 --> 00:21:16,890 en toch, ik moet mijn programma te compileren voordat mensen te laten gebruiken en te downloaden 473 00:21:16,890 --> 00:21:17,390 het. 474 00:21:17,390 --> 00:21:21,490 Dus dit is precies het soort spul dat de CS50 bibliotheek probeert 475 00:21:21,490 --> 00:21:24,750 om ons te helpen met en we zullen alleen oogopslag bij enkele van de onderliggende implementatie 476 00:21:24,750 --> 00:21:29,790 hier, maar dit is CS50 dot C. Dit is het bestand dat is geweest op de CS50 IDE 477 00:21:29,790 --> 00:21:31,420 al die weken dat je hebt gebruikt. 478 00:21:31,420 --> 00:21:34,280 Het is pre-gecompileerde en je hebt automatisch gebruiken 479 00:21:34,280 --> 00:21:38,780 aard van het hebben van de dash L CS50 vlag met klank, 480 00:21:38,780 --> 00:21:42,300 maar als ik naar beneden scrollen door alle deze functies, hier is GetString, 481 00:21:42,300 --> 00:21:44,636 en alleen maar om u een te geven voorproefje van wat er gaande is, 482 00:21:44,636 --> 00:21:46,760 laten we eens een snelle blik op de relatieve complexiteit. 483 00:21:46,760 --> 00:21:48,870 Het is niet een super lang functie, maar we hebben niet 484 00:21:48,870 --> 00:21:52,530 moeten alle harde over denken hoe om te gaan over het krijgen van snaren. 485 00:21:52,530 --> 00:21:55,660 >> Dus hier is mijn buffer en ik blijkbaar initialiseren op null. 486 00:21:55,660 --> 00:21:57,990 Dit is natuurlijk het hetzelfde als char ster, 487 00:21:57,990 --> 00:22:00,585 maar ik besloot in de uitvoering van de CS50 bibliotheek 488 00:22:00,585 --> 00:22:02,460 dat als we gaan zijn volledig dynamisch, 489 00:22:02,460 --> 00:22:05,770 Ik weet niet van tevoren hoe groot van een snaar gebruikers zullen willen krijgen. 490 00:22:05,770 --> 00:22:08,140 Dus ik ga om te beginnen met slechts een lege string 491 00:22:08,140 --> 00:22:11,507 en ik ga op te bouwen zo veel geheugen Ik moet de gebruiker reeks passen 492 00:22:11,507 --> 00:22:13,340 en als ik niet genoeg, ik ga om te vragen 493 00:22:13,340 --> 00:22:15,010 het besturingssysteem voor meer geheugen. 494 00:22:15,010 --> 00:22:17,510 Ik ga hun reeks te verplaatsen in een groter stuk van het geheugen 495 00:22:17,510 --> 00:22:21,847 en ik ga los of vrij de onvoldoende groot deel van het geheugen 496 00:22:21,847 --> 00:22:23,680 en we gaan gewoon dit iteratief doen. 497 00:22:23,680 --> 00:22:25,570 >> Dus een snelle blik, Hier is gewoon een variabele 498 00:22:25,570 --> 00:22:28,780 waarmee ik ga houden de capaciteit van mijn buffer. 499 00:22:28,780 --> 00:22:30,071 Hoeveel bytes kan ik passen? 500 00:22:30,071 --> 00:22:32,070 Hier is een variabele n met die ik ga houden 501 00:22:32,070 --> 00:22:36,200 bij hoeveel bytes daadwerkelijk de buffer of de gebruiker heeft getypt. 502 00:22:36,200 --> 00:22:39,900 Als u dit niet eerder hebt gezien, je kunt opgeven dat een variabele als een int 503 00:22:39,900 --> 00:22:46,370 is niet ondertekend, die zoals de naam al doet vermoeden, betekent dat het niet-negatief, en waarom zou 504 00:22:46,370 --> 00:22:50,590 Ik ooit willen specificeren moeite dat een int is niet alleen een int, 505 00:22:50,590 --> 00:22:52,540 maar het is een unsigned int? 506 00:22:52,540 --> 00:22:55,064 Het is een niet-negatief int. 507 00:22:55,064 --> 00:22:56,355 Wat doet de [onverstaanbaar] betekenen? 508 00:22:56,355 --> 00:22:58,910 >> Publiek: Het beschrijven van een bedrag van geheugen dat kan worden [onverstaanbaar]. 509 00:22:58,910 --> 00:22:59,660 >> DAVID MALAN: Ja. 510 00:22:59,660 --> 00:23:03,710 Dus als ik zeg niet ondertekend, dit is eigenlijk waardoor je een beetje extra geheugen 511 00:23:03,710 --> 00:23:07,440 en het lijkt soort dom, maar als je hebben een beetje extra geheugen, dat 512 00:23:07,440 --> 00:23:09,940 betekent dat tweemaal zoveel waarden die u kan vertegenwoordigen, 513 00:23:09,940 --> 00:23:11,570 omdat het kan een 0 of 1. 514 00:23:11,570 --> 00:23:14,660 Dus standaard, kan een int ruwweg negatieve 2 miljard helemaal 515 00:23:14,660 --> 00:23:16,030 tot positieve 2 miljard. 516 00:23:16,030 --> 00:23:18,540 Dat zijn grote ranges, maar het is nog steeds soort verspilling 517 00:23:18,540 --> 00:23:21,280 Als je alleen de zorg over maten, die net intuïtief 518 00:23:21,280 --> 00:23:24,620 moet niet negatief zijn of positief of 0, goed dan, 519 00:23:24,620 --> 00:23:28,884 waarom bent u verspilt 2 miljard mogelijke waarden voor negatieve getallen 520 00:23:28,884 --> 00:23:30,300 als je nooit gaat om ze te gebruiken? 521 00:23:30,300 --> 00:23:35,350 Dus door te zeggen niet ondertekend, nu mijn int kan liggen tussen 0 en ongeveer 4 miljard. 522 00:23:35,350 --> 00:23:39,280 >> Dus hier is gewoon een int C om redenen zullen we niet alleen nu zo te krijgen in 523 00:23:39,280 --> 00:23:42,280 waarom is het een int plaats van een char, maar hier is 524 00:23:42,280 --> 00:23:44,630 de kern van wat er gaande op, en sommigen van jullie 525 00:23:44,630 --> 00:23:48,340 kunnen worden gebruikt, bijvoorbeeld het fgetc functie zelfs in Pset vier 526 00:23:48,340 --> 00:23:51,580 of daarna, zullen we het zien weer probleem van de vijf, 527 00:23:51,580 --> 00:23:55,410 fgetc is mooi, want zoals de naam soort, soort arcanely suggereert, 528 00:23:55,410 --> 00:23:57,940 het is een functie die krijgt een karakter en zo, 529 00:23:57,940 --> 00:24:00,690 wat is er fundamenteel anders over wat we doen in GetString 530 00:24:00,690 --> 00:24:03,110 is dat we niet gebruiken scanf dezelfde manier. 531 00:24:03,110 --> 00:24:07,550 We zijn gewoon kruipen langs stap-voor-stap dan wat de gebruiker heeft getypt, 532 00:24:07,550 --> 00:24:10,970 want we kunnen altijd wijzen één char, en zo kunnen we altijd veilig 533 00:24:10,970 --> 00:24:15,599 kijken naar een char tegelijk, en de magie begint hier gebeuren. 534 00:24:15,599 --> 00:24:17,890 Ik ga naar beneden scrollen om het midden van deze functie 535 00:24:17,890 --> 00:24:20,360 alleen maar om kort voor te stellen deze functie. 536 00:24:20,360 --> 00:24:22,670 Net als er een malloc functie, er is 537 00:24:22,670 --> 00:24:27,740 een realloc functie waarbij realloc Hiermee kunt u een stuk van het geheugen te herverdelen 538 00:24:27,740 --> 00:24:29,570 en maken het groter of kleiner. 539 00:24:29,570 --> 00:24:33,060 Zo lang verhaal kort en met een golf van mijn hand voor vandaag, 540 00:24:33,060 --> 00:24:35,620 weten dat wat GetString doet is het is een soort 541 00:24:35,620 --> 00:24:39,720 van magische wijze groeien of krimpen de buffer als gebruiker 542 00:24:39,720 --> 00:24:41,440 types in zijn of haar string. 543 00:24:41,440 --> 00:24:43,962 >> Dus als de gebruiker een korte reeks, deze code 544 00:24:43,962 --> 00:24:45,920 alleen kent genoeg geheugen om de string te passen. 545 00:24:45,920 --> 00:24:48,086 Als de gebruiker houdt het typen zoals ik deed het opnieuw en opnieuw 546 00:24:48,086 --> 00:24:50,330 en weer, goed, als het buffer aanvankelijk deze grote 547 00:24:50,330 --> 00:24:53,310 en het programma realiseert, met wacht even, ik ben uit de ruimte, 548 00:24:53,310 --> 00:24:55,410 het gaat verdubbelen de grootte van de buffer 549 00:24:55,410 --> 00:24:59,110 en dan het dubbele van de grootte van de buffer en de code die de verdubbeling doet, 550 00:24:59,110 --> 00:25:03,170 als we kijken naar het hier, het is alleen deze slimme one-liner. 551 00:25:03,170 --> 00:25:06,830 Je zou niet deze syntaxis hebben gezien voor, maar als je zegt ster gelijk, 552 00:25:06,830 --> 00:25:10,470 Dit is hetzelfde als zeggende capaciteit tijden 2. 553 00:25:10,470 --> 00:25:13,390 Dus het blijft gewoon een verdubbeling de capaciteit van de buffer 554 00:25:13,390 --> 00:25:17,480 en dan vertellen realloc te geven zich dat er veel meer geheugen. 555 00:25:17,480 --> 00:25:19,720 >> Nu, als een terzijde, is er zijn andere functies hierin 556 00:25:19,720 --> 00:25:23,680 dat we niet zullen kijken naar elk detail anders dan om te laten zien in getint, 557 00:25:23,680 --> 00:25:26,150 we gebruiken GetString in getint. 558 00:25:26,150 --> 00:25:28,192 We controleren dat het niet null, die, herinneren, 559 00:25:28,192 --> 00:25:30,400 de bijzondere waarde betekent dat er iets mis is gegaan. 560 00:25:30,400 --> 00:25:31,233 We zijn uit het geheugen. 561 00:25:31,233 --> 00:25:32,310 Beter controleren dat. 562 00:25:32,310 --> 00:25:33,710 En we terug een sentinel waarde. 563 00:25:33,710 --> 00:25:37,850 Maar ik zal zich naar de opmerkingen met betrekking tot waarom en dan gebruiken we deze neef van scanf 564 00:25:37,850 --> 00:25:42,100 riep sscanf en het blijkt dat sscanf, of touwtje scanf, 565 00:25:42,100 --> 00:25:45,310 laat u een kijkje nemen op de lijn te nemen dat de gebruiker heeft getypt en laat u 566 00:25:45,310 --> 00:25:49,610 analyseren wezen en wat ik ben hier doen is Ik zeg sscanf, 567 00:25:49,610 --> 00:25:54,440 analyseert wat de gebruiker getypt in en zorg ervoor dat% i, 568 00:25:54,440 --> 00:25:59,250 Er is een integer in, en we zullen niet krijgen vandaag precies de reden waarom is er ook 569 00:25:59,250 --> 00:26:03,760 a% c hier, maar dat in een notendop laat we detecteren of de gebruiker heeft getypt 570 00:26:03,760 --> 00:26:06,050 in iets nep na het nummer. 571 00:26:06,050 --> 00:26:11,766 Dus de reden dat getint en GetString je vertellen om opnieuw te proberen, opnieuw proberen, opnieuw proberen 572 00:26:11,766 --> 00:26:13,640 is vanwege alle dat de code die we hebben geschreven, 573 00:26:13,640 --> 00:26:17,900 Het is een beetje te kijken naar de ingang van de gebruiker om ervoor te zorgen dat het geheel numeriek 574 00:26:17,900 --> 00:26:21,700 of het is een echte drijvende puntwaarde of dergelijke, 575 00:26:21,700 --> 00:26:24,233 afhankelijk van de waarde functie die u gebruikt. 576 00:26:24,233 --> 00:26:25,060 >> Oef. 577 00:26:25,060 --> 00:26:25,710 OK. 578 00:26:25,710 --> 00:26:27,592 Dat was een mondvol maar het punt is hier 579 00:26:27,592 --> 00:26:29,550 dat de reden waarom we hadden die zijwieltjes op 580 00:26:29,550 --> 00:26:32,880 is omdat op het laagste niveau, er is gewoon zo veel dingen die 581 00:26:32,880 --> 00:26:35,674 mis kan gaan dat we wilden om preventief te behandelen 582 00:26:35,674 --> 00:26:38,090 die dingen zeker in het eerste weken van de klas, 583 00:26:38,090 --> 00:26:42,230 maar nu met Pset vier en vijf en Pset dan zul je zien dat het meer aan 584 00:26:42,230 --> 00:26:45,570 u, maar ook dat je beter in staat het oplossen van dit soort problemen 585 00:26:45,570 --> 00:26:47,180 jezelf. 586 00:26:47,180 --> 00:26:51,770 Vragen over GetString of getint? 587 00:26:51,770 --> 00:26:52,630 Ja? 588 00:26:52,630 --> 00:26:55,130 >> Publiek: Waarom zou je verdubbelen de capaciteit van de buffer 589 00:26:55,130 --> 00:26:57,630 in plaats van alleen het verhogen door het juiste bedrag? 590 00:26:57,630 --> 00:26:58,100 >> DAVID MALAN: Goede vraag. 591 00:26:58,100 --> 00:27:00,474 Waarom zouden we het dubbele van de capaciteit van de buffer in tegenstelling 592 00:27:00,474 --> 00:27:02,800 om gewoon vooruit door een constante waarde? 593 00:27:02,800 --> 00:27:03,900 Het was een ontwerp beslissing. 594 00:27:03,900 --> 00:27:08,590 We besloten omdat het de neiging om een beetje duur qua tijd om te vragen 595 00:27:08,590 --> 00:27:10,440 het besturingssysteem voor het geheugen, hebben we niet 596 00:27:10,440 --> 00:27:13,210 wilt eindigen krijgen in een situatie voor grote strings 597 00:27:13,210 --> 00:27:14,960 dat we vroegen weer OS 598 00:27:14,960 --> 00:27:17,500 en weer in snelle opeenvolging voor het geheugen. 599 00:27:17,500 --> 00:27:20,387 Dus we besloten, ietwat willekeurig maar we hopen dat redelijk, 600 00:27:20,387 --> 00:27:22,720 dat, weet je wat, laten we proberen om vooruit lopen 601 00:27:22,720 --> 00:27:25,520 en gewoon blijven verdubbelen, zodat we de hoeveelheid te minimaliseren 602 00:27:25,520 --> 00:27:29,010 we moeten malloc bellen of realloc, maar een totaal oordeel 603 00:27:29,010 --> 00:27:31,820 bellen zonder kennen wat gebruikers willen wellicht in te typen. 604 00:27:31,820 --> 00:27:33,600 Beide manieren zou kunnen zijn discutabel. 605 00:27:33,600 --> 00:27:35,430 Ongetwijfeld goed. 606 00:27:35,430 --> 00:27:39,240 >> Dus laten we een kijkje nemen op een paar andere bijwerkingen van het geheugen, 607 00:27:39,240 --> 00:27:41,610 dingen die mis kan gaan en tools die u kunt 608 00:27:41,610 --> 00:27:43,880 om dergelijke fouten te vangen. 609 00:27:43,880 --> 00:27:47,800 Het blijkt dat jullie allemaal, ook al check50 heeft niet verteld u zo veel, 610 00:27:47,800 --> 00:27:50,050 zijn schrijven buggy code sinds een week, 611 00:27:50,050 --> 00:27:53,630 zelfs als alle check50 tests verstreken, en zelfs als u en uw TF 612 00:27:53,630 --> 00:27:56,010 zijn super overtuigd dat uw code werkt zoals bedoeld. 613 00:27:56,010 --> 00:27:59,190 Uw code is buggy is of gebrekkig in dat u allen, 614 00:27:59,190 --> 00:28:02,540 het gebruik van het CS50 bibliotheek zijn lekkende geheugen. 615 00:28:02,540 --> 00:28:06,040 Je hebt gevraagd het besturingssysteem voor het geheugen in de meeste programma's 616 00:28:06,040 --> 00:28:08,850 je hebt geschreven, maar je hebt eigenlijk nooit gezien het terug. 617 00:28:08,850 --> 00:28:12,110 Je hebt GetString genoemd en getint en GetFloat, 618 00:28:12,110 --> 00:28:15,270 maar met GetString, je hebt nooit unGetString of geef genoemd 619 00:28:15,270 --> 00:28:19,890 String Back of iets dergelijks, maar we hebben gezien dat GetString doet geheugen toewijzen 620 00:28:19,890 --> 00:28:22,810 door middel van malloc of dit functie realloc, dat is gewoon 621 00:28:22,810 --> 00:28:25,670 zeer vergelijkbaar in de geest, en toch, we zijn geweest 622 00:28:25,670 --> 00:28:28,629 vraagt ​​het besturingssysteem voor geheugen en het geheugen weer 623 00:28:28,629 --> 00:28:29,670 maar nooit geven het terug. 624 00:28:29,670 --> 00:28:33,550 >> Nu, als een terzijde, blijkt dat wanneer een programma wordt afgesloten, al het geheugen 625 00:28:33,550 --> 00:28:34,870 automatisch vrijgemaakt. 626 00:28:34,870 --> 00:28:36,150 Dus het is niet een groot probleem geweest. 627 00:28:36,150 --> 00:28:38,590 Het gaat niet om het te breken IDE of langzaam dingen naar beneden, 628 00:28:38,590 --> 00:28:40,670 maar wanneer programma's doen meestal lekken geheugen 629 00:28:40,670 --> 00:28:42,170 en ze lopen voor een lange tijd. 630 00:28:42,170 --> 00:28:45,640 Als je ooit hebt gezien de stomme strandbal in Mac OS of de zandloper 631 00:28:45,640 --> 00:28:51,160 Windows waar het soort vertragen of denken of denken 632 00:28:51,160 --> 00:28:53,770 of gewoon echt begint te traag als een slak, 633 00:28:53,770 --> 00:28:56,960 het heel zou kunnen zijn het resultaat van een geheugenlek. 634 00:28:56,960 --> 00:28:59,970 De programmeurs die schreef de software die u gebruikt 635 00:28:59,970 --> 00:29:03,570 vraagt ​​het besturingssysteem voor het geheugen elke paar minuten per uur. 636 00:29:03,570 --> 00:29:05,570 Maar als je het uitvoeren van de software, zelfs als het 637 00:29:05,570 --> 00:29:08,680 geminimaliseerd in uw computer uren- of dagenlang, 638 00:29:08,680 --> 00:29:11,980 je zou kunnen vragen om meer en meer geheugen en eigenlijk nooit gebruikt 639 00:29:11,980 --> 00:29:15,180 en zo je code zou kunnen zijn, of programma's kunnen worden lekt geheugen, 640 00:29:15,180 --> 00:29:18,350 en als je begint te lekken geheugen, is er minder geheugen voor andere programma's, 641 00:29:18,350 --> 00:29:21,220 en het effect is vertragen alles naar beneden. 642 00:29:21,220 --> 00:29:23,600 >> Nu, dit is veruit een van de meest gruwelijke programma 643 00:29:23,600 --> 00:29:26,350 je kansen om te draaien in CS50 zover 644 00:29:26,350 --> 00:29:31,650 als output is nog meer esoterische dan clang of maken of één van de commando 645 00:29:31,650 --> 00:29:35,930 Online programma's die we eerder hebben uitgevoerd, maar gelukkig, ingebed in de output 646 00:29:35,930 --> 00:29:39,810 is een aantal super handige tips die zal nuttig zijn hetzij voor Pset vier zijn 647 00:29:39,810 --> 00:29:41,510 of zeker PSET vijf. 648 00:29:41,510 --> 00:29:44,250 Dus valgrind is een hulpmiddel die kunnen worden gebruikt om te kijken 649 00:29:44,250 --> 00:29:46,930 voor het geheugen lekken in uw programma. 650 00:29:46,930 --> 00:29:48,570 Het is relatief eenvoudig om te draaien. 651 00:29:48,570 --> 00:29:51,420 Je loopt valgrind en dan, zelfs al is het een beetje breedsprakig, 652 00:29:51,420 --> 00:29:54,440 dash dash lek check gelijk vol, en dan dot 653 00:29:54,440 --> 00:29:56,320 slash en de naam van het programma. 654 00:29:56,320 --> 00:30:00,010 Dus valgrind zal dan uw programma uit te voeren en aan het einde van uw programma 655 00:30:00,010 --> 00:30:02,240 runnen voordat hij stopt en geeft u een andere prompt 656 00:30:02,240 --> 00:30:04,980 het gaat om het analyseren van uw programma, terwijl het is gelopen 657 00:30:04,980 --> 00:30:07,740 en zeg je heb je lekken elke geheugen en beter nog, 658 00:30:07,740 --> 00:30:10,610 heb je geheugen aanraken niet van jou? 659 00:30:10,610 --> 00:30:13,700 Het kan niet alles te vangen, maar het is vrij goed in het vangen van de meeste dingen. 660 00:30:13,700 --> 00:30:19,700 >> Dus hier is een voorbeeld van het hebben van mijn run dit programma, met run valgrind, 661 00:30:19,700 --> 00:30:21,470 op een programma genaamd geheugen, en ik ga 662 00:30:21,470 --> 00:30:24,730 de lijnen die markeren uiteindelijk voor ons van belang. 663 00:30:24,730 --> 00:30:27,690 Dus er is nog meer afleiding dat ik van de glijbaan heeft verwijderd. 664 00:30:27,690 --> 00:30:30,930 Maar laten we eens kijken wat dit programma is in staat om ons te vertellen. 665 00:30:30,930 --> 00:30:34,800 Het is in staat om ons te vertellen dingen als ongeldig schrijven van maat 4. 666 00:30:34,800 --> 00:30:38,020 Met andere woorden, als u het geheugen aanraakt, bijzonder 4 bytes geheugen 667 00:30:38,020 --> 00:30:40,350 dat je niet zou moeten hebben, valgrind kan u vertellen dat. 668 00:30:40,350 --> 00:30:41,660 Ongeldige schrijven van maat 4. 669 00:30:41,660 --> 00:30:43,640 Je raakte vier bytes dat je niet zou moeten hebben. 670 00:30:43,640 --> 00:30:44,840 Waar heb je dat gedaan? 671 00:30:44,840 --> 00:30:45,900 Dit is de schoonheid. 672 00:30:45,900 --> 00:30:50,000 Memory dot c lijn 21 is waar je verpest en dat is waarom het nuttig. 673 00:30:50,000 --> 00:30:53,410 Net als GDB, kan het helpen u wijzen op de feitelijke fout. 674 00:30:53,410 --> 00:30:57,170 >> Nu, dit is een beetje meer uitgebreide of zelfs verwarrend. 675 00:30:57,170 --> 00:31:01,307 40 bytes in 1 blokken zijn zeker verloren in verlies record 1 van 1. 676 00:31:01,307 --> 00:31:02,140 Wat betekent dat? 677 00:31:02,140 --> 00:31:05,920 Nou, het betekent gewoon dat je vroeg 40 bytes en je nooit gaf het terug. 678 00:31:05,920 --> 00:31:08,930 Je noemde malloc of u geroepen GetString en het besturingssysteem 679 00:31:08,930 --> 00:31:12,450 gaf je 40 bytes, maar je nooit bevrijd of vrijgegeven dat het geheugen, 680 00:31:12,450 --> 00:31:15,400 en om eerlijk te zijn, we hebben nooit laten zien hoe je terug te geven geheugen. 681 00:31:15,400 --> 00:31:17,910 Blijkt dat er een super eenvoudige functie genaamd gratis. 682 00:31:17,910 --> 00:31:21,170 Neemt één argument, het ding je wilt vrij te maken of terug te geven, 683 00:31:21,170 --> 00:31:23,430 maar 40 bytes blijkbaar in dit programma 684 00:31:23,430 --> 00:31:27,300 verloren zijn gegaan in lijn 20 geheugen dot c. 685 00:31:27,300 --> 00:31:28,650 >> Dus laten we zien dit programma. 686 00:31:28,650 --> 00:31:31,020 Het is super nutteloos. 687 00:31:31,020 --> 00:31:33,980 Het toont alleen deze specifieke fout. 688 00:31:33,980 --> 00:31:34,920 Dus laten we eens een kijkje nemen. 689 00:31:34,920 --> 00:31:39,920 Hier is de belangrijkste en de belangrijkste, bericht, gesprekken een functie genaamd f en vervolgens terugkeert. 690 00:31:39,920 --> 00:31:41,550 Dus niet zo interessant. 691 00:31:41,550 --> 00:31:42,664 Wat doet f doen? 692 00:31:42,664 --> 00:31:44,330 Let op, ik heb geen moeite met een prototype. 693 00:31:44,330 --> 00:31:46,520 Ik wilde de code te houden zo klein mogelijk. 694 00:31:46,520 --> 00:31:49,530 Dus ik zet f boven de hoofd-en dat is prima, zeker, 695 00:31:49,530 --> 00:31:51,500 voor korte programma's zoals dit. 696 00:31:51,500 --> 00:31:56,910 Dus f niets terug en doet niet iets aan te nemen, maar het doet dit te doen. 697 00:31:56,910 --> 00:31:59,620 Het verklaart, net als in de Binky voorbeeld 698 00:31:59,620 --> 00:32:02,682 een pointer genaamd x dat gaat het adres van een int slaan. 699 00:32:02,682 --> 00:32:03,890 Dus dat is de linker kant. 700 00:32:03,890 --> 00:32:07,230 In het Engels, wat is de rechterzijde doen? 701 00:32:07,230 --> 00:32:09,770 Iedereen? 702 00:32:09,770 --> 00:32:13,665 Wat is dit voor ons? 703 00:32:13,665 --> 00:32:14,651 Ja? 704 00:32:14,651 --> 00:32:16,623 >> PUBLIEK: [onverstaanbaar] keer de grootte van een int 705 00:32:16,623 --> 00:32:19,175 dat is 10 keer dat [onverstaanbaar] 706 00:32:19,175 --> 00:32:20,800 DAVID MALAN: Goede en laat me samenvatten. 707 00:32:20,800 --> 00:32:25,480 Dus toewijzen voldoende ruimte voor 10 gehele getallen of 10, wat is de grootte van een int, 708 00:32:25,480 --> 00:32:29,340 Het is vier bytes, dus 10 keer 4 is 40, zodat de rechterzijde die ik heb 709 00:32:29,340 --> 00:32:33,930 gemarkeerde is geef me 40 bytes en opslaan van het adres van de eerste byte 710 00:32:33,930 --> 00:32:34,940 in x. 711 00:32:34,940 --> 00:32:38,380 En nu tot slot, en hier is waar Dit programma is buggy, wat is 712 00:32:38,380 --> 00:32:41,540 mis met lijn 21 op basis van die logica? 713 00:32:41,540 --> 00:32:45,197 714 00:32:45,197 --> 00:32:46,280 Wat is er mis met lijn 21? 715 00:32:46,280 --> 00:32:46,780 Ja? 716 00:32:46,780 --> 00:32:49,550 Publiek: Je kunt niet index in x [onverstaanbaar]. 717 00:32:49,550 --> 00:32:50,300 DAVID MALAN: Ja. 718 00:32:50,300 --> 00:32:52,270 Ik moet niet index in x als dat. 719 00:32:52,270 --> 00:32:53,850 Dus syntactisch, dat is OK. 720 00:32:53,850 --> 00:32:56,990 Wat er leuk is, net als jij kan de naam van een array te behandelen 721 00:32:56,990 --> 00:33:01,080 alsof het een pointer, eveneens kunt u een pointer te behandelen alsof het 722 00:33:01,080 --> 00:33:06,425 een array, en zo kan ik syntactisch zeggen x beugel iets, x beugel i, 723 00:33:06,425 --> 00:33:07,800 maar 10 problematisch. 724 00:33:07,800 --> 00:33:09,096 Waarom? 725 00:33:09,096 --> 00:33:10,910 >> Publiek: Omdat het niet binnen. 726 00:33:10,910 --> 00:33:12,390 >> DAVID MALAN: Het is niet binnen dat deel van het geheugen. 727 00:33:12,390 --> 00:33:15,306 Wat is de grootste waarde zou ik te zetten in die vierkante haken? 728 00:33:15,306 --> 00:33:16,870 9, 0 tot 9. 729 00:33:16,870 --> 00:33:18,160 Door nul indexeren. 730 00:33:18,160 --> 00:33:20,190 Dus 0 tot en met 9 zou fijn zijn. 731 00:33:20,190 --> 00:33:23,960 Beugel 10 is niet goed en maar, herinneren hoewel, elke keer 732 00:33:23,960 --> 00:33:27,017 Ik meen mij te proberen CS50 IDE maken crash door het intypen van valse waarden, 733 00:33:27,017 --> 00:33:29,100 het niet altijd werken, en inderdaad, je vaak 734 00:33:29,100 --> 00:33:31,460 geluk alleen omdat de besturingssysteem niet 735 00:33:31,460 --> 00:33:35,467 merken dat je ooit zo iets passeren enkele brok van geheugen, 736 00:33:35,467 --> 00:33:38,300 omdat je bleef binnen technisch uw segment, maar daarover 737 00:33:38,300 --> 00:33:40,940 in een besturingssystemen klasse, en zo iets als dit 738 00:33:40,940 --> 00:33:43,000 kan heel gemakkelijk onopgemerkt. 739 00:33:43,000 --> 00:33:48,120 Het programma gaat nooit crashen consequent maar misschien een keer in een tijdje. 740 00:33:48,120 --> 00:33:50,610 >> En zo laten we proberen valgrind Op deze, en hier is 741 00:33:50,610 --> 00:33:52,870 waar we overweldigd door de uitgang tijdelijk. 742 00:33:52,870 --> 00:34:00,810 Dus zorg geheugen valgrind lektest evenaart full dot slash geheugen. 743 00:34:00,810 --> 00:34:03,040 En hier is waarom ik beloof Dit zou overweldigen. 744 00:34:03,040 --> 00:34:05,700 Hier is wat valgrind, hier is wat een programmeur, enkele jaren geleden- 745 00:34:05,700 --> 00:34:08,469 besloten dat het een goed idee zou zijn voor de output te lijken. 746 00:34:08,469 --> 00:34:09,750 Dus laten we gevoel van deze. 747 00:34:09,750 --> 00:34:13,120 Dus helemaal aan de linker side zonder goede reden 748 00:34:13,120 --> 00:34:16,620 is het proces ID van het programma we gewoon lopen, de unieke identifier 749 00:34:16,620 --> 00:34:18,030 voor het programma dat we net liep. 750 00:34:18,030 --> 00:34:19,738 We verwijderd dat vanaf de glijbaan, maar er 751 00:34:19,738 --> 00:34:22,190 is een aantal nuttige informatie hier. 752 00:34:22,190 --> 00:34:24,684 >> Laten scrollen naar de top. 753 00:34:24,684 --> 00:34:25,600 Hier is waar we begonnen. 754 00:34:25,600 --> 00:34:27,040 Dus het is niet zo heel veel output. 755 00:34:27,040 --> 00:34:30,429 Hier is dat ongeldig schrijven van maat 4 op lijn 21. 756 00:34:30,429 --> 00:34:31,760 Nou, wat was lijn 21? 757 00:34:31,760 --> 00:34:34,500 Lijn 21 was precies Hierdoor en het zinvol 758 00:34:34,500 --> 00:34:37,290 dat ik in rechtsgeldig het schrijven van 4 bytes, want ik ben 759 00:34:37,290 --> 00:34:40,389 probeert dit integer zetten, die kan van alles zijn, 760 00:34:40,389 --> 00:34:42,370 het gebeurt gewoon te worden nul, maar ik probeer 761 00:34:42,370 --> 00:34:44,940 om het te zetten op een locatie dat hoort niet bij mij. 762 00:34:44,940 --> 00:34:50,900 Bovendien, hier beneden, 40 bytes in één blokken zijn zeker verloren in een recordtijd 1. 763 00:34:50,900 --> 00:34:56,500 Dat komt omdat als ik bel malloc hier heb ik eigenlijk nooit vrij het geheugen. 764 00:34:56,500 --> 00:34:58,140 >> Dus hoe kunnen we dit oplossen? 765 00:34:58,140 --> 00:35:02,970 Laat me gaan en een beetje veiliger en doe 9 daar en laat me hier gratis x. 766 00:35:02,970 --> 00:35:04,820 Dit is de nieuwe functie voor vandaag. 767 00:35:04,820 --> 00:35:11,520 Als ik nu opnieuw uitvoeren maken geheugen dot slash, laten we opnieuw uitvoeren valgrind op, 768 00:35:11,520 --> 00:35:14,990 maximaliseren van mijn raam en druk op Enter. 769 00:35:14,990 --> 00:35:16,900 Nu, het is goed. 770 00:35:16,900 --> 00:35:19,590 Ze begraaft het goede nieuws in al deze uitgang. 771 00:35:19,590 --> 00:35:20,810 Alle hoop blokken waren vrij. 772 00:35:20,810 --> 00:35:23,604 We zullen terug naar wat de hoop komen is, maar geen lekken mogelijk. 773 00:35:23,604 --> 00:35:25,520 Dus dit is gewoon een andere tool voor uw tool kit 774 00:35:25,520 --> 00:35:30,220 waarmee je kunt beginnen met nu vinden fouten als dat. 775 00:35:30,220 --> 00:35:34,532 >> Maar laten we eens kijken wat meer mis kan gaan hier. 776 00:35:34,532 --> 00:35:38,890 Laten we nu de overgang naar eigenlijk het oplossen van een probleem. 777 00:35:38,890 --> 00:35:42,440 Even terzijde, als dit zal verlichten beetje verwarring of spanning, 778 00:35:42,440 --> 00:35:43,430 dit is nu grappig. 779 00:35:43,430 --> 00:35:46,400 780 00:35:46,400 --> 00:35:46,900 Ja. 781 00:35:46,900 --> 00:35:49,040 Dat is vrij goed. 782 00:35:49,040 --> 00:35:50,890 Omdat pointers zijn adressen en adressen 783 00:35:50,890 --> 00:35:53,098 zijn over het algemeen volgens afspraak geschreven met hexadecimale. 784 00:35:53,098 --> 00:35:54,650 Ha, ha, dit is nu grappig. 785 00:35:54,650 --> 00:35:58,390 Hoe dan ook, dus laten we nu echter een probleem. 786 00:35:58,390 --> 00:36:00,840 Dit super geweest super laag niveau tot nu toe, 787 00:36:00,840 --> 00:36:03,950 en we kunnen werkelijk nuttig doen dingen met deze low-level details. 788 00:36:03,950 --> 00:36:06,710 >> Dus hebben we een paar weken geïntroduceerd geleden het idee van een array. 789 00:36:06,710 --> 00:36:09,177 Een array was leuk omdat het is moeilijk om schoon te maken onze code 790 00:36:09,177 --> 00:36:11,760 want als we wilden een schrijven programma met meerdere studenten 791 00:36:11,760 --> 00:36:15,270 of meerdere namen en huizen en slaapzalen en hogescholen en dat alles, 792 00:36:15,270 --> 00:36:19,430 konden we alles meer op te slaan netjes binnen een array. 793 00:36:19,430 --> 00:36:23,039 Maar stellen een nadeel van een matrix tot nu toe. 794 00:36:23,039 --> 00:36:26,080 Zelfs als je het niet zelf hebt geleden in een programma, maar instinctief, 795 00:36:26,080 --> 00:36:30,870 wat is een slechte zaak over een matrix, misschien? 796 00:36:30,870 --> 00:36:32,337 Ik hoor wat gemompel. 797 00:36:32,337 --> 00:36:34,170 Publiek: Het is moeilijk de kleur veranderd worden. 798 00:36:34,170 --> 00:36:36,128 DAVID MALAN: Het is moeilijk de kleur veranderd worden. 799 00:36:36,128 --> 00:36:38,660 U kunt de grootte niet veranderen van een array, in feite, zodanig 800 00:36:38,660 --> 00:36:43,040 in C. U kunt een andere array toe te wijzen, bewegen alles van de oude 801 00:36:43,040 --> 00:36:45,380 in de nieuwe, en nu wat extra ruimte, 802 00:36:45,380 --> 00:36:47,469 maar het is niet als een taal als Java of Python 803 00:36:47,469 --> 00:36:49,760 of elk aantal andere talen waarmee sommige van jullie 804 00:36:49,760 --> 00:36:52,070 vertrouwd zou kunnen zijn waar u kan gewoon blijven toevoegen dingen 805 00:36:52,070 --> 00:36:53,930 vervelens aan het einde van een array. 806 00:36:53,930 --> 00:36:57,880 Wanneer u een scala aan maat 6, dat de grootte is, 807 00:36:57,880 --> 00:37:01,970 en zo veel op het idee eerder een buffer van een bepaalde grootte, 808 00:37:01,970 --> 00:37:05,940 je moet raden uit de poort welke maat heb je dat wilt? 809 00:37:05,940 --> 00:37:07,880 Als u raden te groot, je verspilt ruimte. 810 00:37:07,880 --> 00:37:10,950 Als je te klein raden, u kan deze informatie niet opgeslagen, ten minste 811 00:37:10,950 --> 00:37:12,940 zonder veel meer werk. 812 00:37:12,940 --> 00:37:18,180 >> Dus vandaag, dankzij pointers, kunnen wij beginnen aan elkaar plakken van onze eigen aangepaste 813 00:37:18,180 --> 00:37:20,989 gegevensstructuren, en Eigenlijk is hier iets 814 00:37:20,989 --> 00:37:23,030 dat ziet er een beetje meer cryptische op het eerste gezicht, 815 00:37:23,030 --> 00:37:26,440 maar dit is wat we noemen een gekoppelde lijst, en de naam soort vat samen 816 00:37:26,440 --> 00:37:26,940 het. 817 00:37:26,940 --> 00:37:29,550 Het is een lijst van nummers, of in dit geval, een lijst van nummers, 818 00:37:29,550 --> 00:37:33,480 maar het kan een lijst van alles zijn, maar het is met elkaar verbonden door middel van pijlen, 819 00:37:33,480 --> 00:37:36,380 en gewoon een gok te nemen met welke techniek 820 00:37:36,380 --> 00:37:38,310 gaan we om te kunnen om samen steek, 821 00:37:38,310 --> 00:37:42,540 soort als popcorn met een draad, een gelinkte lijsten rechthoeken hier? 822 00:37:42,540 --> 00:37:43,936 Zijn nummers? 823 00:37:43,936 --> 00:37:45,560 Wat is de taal functie onderliggende? 824 00:37:45,560 --> 00:37:46,350 >> Publiek: Een wijzer. 825 00:37:46,350 --> 00:37:47,308 >> DAVID MALAN: een pointer. 826 00:37:47,308 --> 00:37:51,700 Dus elk van deze pijlen hier vertegenwoordigt een pointer of gewoon een adres. 827 00:37:51,700 --> 00:37:54,590 Dus met andere woorden, als ik wil om een ​​lijst met nummers op te slaan, 828 00:37:54,590 --> 00:37:59,040 Ik kan niet zomaar op te slaan als ik wil het vermogen om te groeien en krimpen 829 00:37:59,040 --> 00:38:00,990 mijn datastructuur in een array. 830 00:38:00,990 --> 00:38:03,000 Dus ik moet een beetje hebben meer raffinement, 831 00:38:03,000 --> 00:38:05,720 maar merken dat dit foto soort suggereert 832 00:38:05,720 --> 00:38:08,650 dat als je net hebt weinig discussies met elkaar verbinden van alles, 833 00:38:08,650 --> 00:38:13,100 Waarschijnlijk is niet zo moeilijk om ruimte te maken tussen twee van deze rechthoeken 834 00:38:13,100 --> 00:38:16,750 of twee van die knooppunten, zoals we beginnen bellen ze, in een nieuw knooppunt, 835 00:38:16,750 --> 00:38:19,547 en dan met een aantal nieuwe thread, net sloot de drie knooppunten samen, 836 00:38:19,547 --> 00:38:22,880 de eerste, de laatste en degene dat je gewoon ingevoegd in het midden. 837 00:38:22,880 --> 00:38:26,000 >> En inderdaad een gelinkte lijst, In tegenstelling tot een array dynamisch. 838 00:38:26,000 --> 00:38:27,840 Het kan groeien en het kan krimpen en jij niet 839 00:38:27,840 --> 00:38:32,434 moet weten of zorg op voorhand hoe veel gegevens die u gaat worden het opslaan, 840 00:38:32,434 --> 00:38:35,600 maar het blijkt dat we een beetje te zijn voorzichtig zijn over hoe om dit te implementeren. 841 00:38:35,600 --> 00:38:39,070 Dus laten we eerst eens kijken hoe we implementeren één van deze kleine rechthoeken. 842 00:38:39,070 --> 00:38:40,690 Het is gemakkelijk om een ​​int implementeren. 843 00:38:40,690 --> 00:38:44,000 Je zegt gewoon int n en vervolgens je krijgt 4 bytes voor een int, 844 00:38:44,000 --> 00:38:49,089 maar hoe krijg ik een int, noem het n, en dan een wijzer, laten we noemen het volgende. 845 00:38:49,089 --> 00:38:50,880 We kunnen deze noemen dingen wat we willen 846 00:38:50,880 --> 00:38:53,590 maar ik moet een aangepaste datastructuur. 847 00:38:53,590 --> 00:38:54,257 Ja? 848 00:38:54,257 --> 00:38:57,020 >> PUBLIEK: Ampersand [onverstaanbaar]. 849 00:38:57,020 --> 00:39:00,940 >> DAVID MALAN: Dus ampersand we zullen gebruiken om krijgt het adres van een knooppunt potentieel. 850 00:39:00,940 --> 00:39:02,740 Maar we nog nodig kenmerk van C teneinde 851 00:39:02,740 --> 00:39:06,700 mij de mogelijkheid te creëren geven deze gewoonte rechthoek, deze gewoonte 852 00:39:06,700 --> 00:39:08,919 variabele als je wil, in het geheugen. 853 00:39:08,919 --> 00:39:09,710 Publiek: Een struct. 854 00:39:09,710 --> 00:39:10,626 DAVID MALAN: een structuur. 855 00:39:10,626 --> 00:39:14,310 Herinneren van vorige week, we geïntroduceerd structuur, deze relatief eenvoudige trefwoord 856 00:39:14,310 --> 00:39:16,254 dat laat ons dit soort dingen te maken. 857 00:39:16,254 --> 00:39:18,420 C kwam niet met een data- structuur genaamd student. 858 00:39:18,420 --> 00:39:22,190 Het wordt geleverd met int en float en char en zodanig, maar het komt niet met een student, 859 00:39:22,190 --> 00:39:26,750 maar we kunnen een type student gegevens te maken, een student structuur, met deze syntaxis 860 00:39:26,750 --> 00:39:27,250 here. 861 00:39:27,250 --> 00:39:28,350 En je zult dit opnieuw en opnieuw te zien. 862 00:39:28,350 --> 00:39:30,426 Dus maak je geen zorgen te maken over het onthouden van de zoekwoorden, 863 00:39:30,426 --> 00:39:33,300 maar het zoekwoord dat het belangrijk is alleen het feit dat we zeiden struct 864 00:39:33,300 --> 00:39:37,590 en riep toen we student en de binnenkant van de student was een naam en een huis 865 00:39:37,590 --> 00:39:39,390 of een slaapzaal of iets dergelijks. 866 00:39:39,390 --> 00:39:41,980 >> En nu vandaag, laten we stellen dit. 867 00:39:41,980 --> 00:39:45,240 Ik heb een paar woorden toegevoegd, maar als ik wil deze rechthoek die is uit te voeren 868 00:39:45,240 --> 00:39:48,440 kreeg zowel een int en een wijzer, weet je wat, ik ben 869 00:39:48,440 --> 00:39:51,540 gaan naar een structuur genaamd knooppunt verklaren. 870 00:39:51,540 --> 00:39:55,630 Ik ben ook, de binnenkant van het, gaan zeggen dat een knooppunt, rechthoek, heeft een int 871 00:39:55,630 --> 00:39:59,730 en we noemen het n en het heeft een volgend pointer. 872 00:39:59,730 --> 00:40:02,540 En dit is een beetje breedsprakig, maar als je erover nadenkt, 873 00:40:02,540 --> 00:40:07,300 de pijlen die op de foto waren een moment geleden zijn van wat voor soort data? 874 00:40:07,300 --> 00:40:12,330 Waarbij elk van die pijlen wijst om wat voor soort data structuur? 875 00:40:12,330 --> 00:40:14,332 Het is niet alleen wijzen naar een int per se. 876 00:40:14,332 --> 00:40:16,165 Het wijst naar de geheel rechthoekig ding 877 00:40:16,165 --> 00:40:18,720 en dat rechthoekig ding, we zeiden, wordt een knooppunt genoemd. 878 00:40:18,720 --> 00:40:21,720 En dus hebben we soort hebben recursief ander zodanig definiëren 879 00:40:21,720 --> 00:40:26,270 dat een knooppunt, laten we zeggen, zal een int genaamd n bevatten 880 00:40:26,270 --> 00:40:31,070 en een wijzer genoemd volgende en de type gegevensstructuur waarin 881 00:40:31,070 --> 00:40:35,770 dat wijzer is blijkbaar zal struct node. 882 00:40:35,770 --> 00:40:41,550 >> Dus dit is hinderlijk breedsprakig en gewoon te pedant zijn, 883 00:40:41,550 --> 00:40:44,100 de reden waarom we niet kunnen alleen dit zeggen, dat eerlijk gezegd 884 00:40:44,100 --> 00:40:46,860 ziet er een stuk beter leesbaar, is omdat herinneren dat C gelezen 885 00:40:46,860 --> 00:40:48,710 dingen van boven naar beneden, van links naar rechts. 886 00:40:48,710 --> 00:40:54,120 Het is niet totdat we de puntkomma dat het zoekwoord knooppunt werkelijk bestaat. 887 00:40:54,120 --> 00:40:57,980 Dus als we willen dit soort hebben cyclische referentie binnenzijde van de data 888 00:40:57,980 --> 00:41:02,120 structuur, moeten we dit doen, waar we zeggen struct knooppunt aan de top, die 889 00:41:02,120 --> 00:41:06,770 geeft ons een langere weg te beschrijven deze ding, dan binnenkant we zeggen struct knooppunt 890 00:41:06,770 --> 00:41:09,560 en dan op het allerlaatste lijn we zeggen, oke, C, door de manier, 891 00:41:09,560 --> 00:41:12,060 alleen deze hele verdomde bellen wat een knooppunt en stoppen 892 00:41:12,060 --> 00:41:14,360 met behulp van het trefwoord structuur helemaal. 893 00:41:14,360 --> 00:41:18,030 Dus dit is gewoon een soort van een syntactische truc die uiteindelijk laat ons maken 894 00:41:18,030 --> 00:41:21,370 iets dat ziet er precies zo. 895 00:41:21,370 --> 00:41:25,010 >> Dus als we nu gaan we ervan uit kunnen uitvoering van deze zaak in C, 896 00:41:25,010 --> 00:41:28,040 hoe kunnen we eigenlijk start doorkruisen dit? 897 00:41:28,040 --> 00:41:32,360 Nou, in feite, alles wat we moeten doen is herhalen van links naar rechts en net 898 00:41:32,360 --> 00:41:35,960 soort plaatst knooppunten of knooppunten verwijderen of zoeken naar dingen waar we willen, 899 00:41:35,960 --> 00:41:39,560 maar om dit te doen, laten we gaan vooruit en maak dingen een beetje meer reëel, omdat deze 900 00:41:39,560 --> 00:41:42,560 is super laag niveau tot nu toe geweest. 901 00:41:42,560 --> 00:41:45,700 Zou iemand letterlijk als eerste zijn? 902 00:41:45,700 --> 00:41:46,200 OK. 903 00:41:46,200 --> 00:41:47,092 Kom op maximaal. 904 00:41:47,092 --> 00:41:47,800 Hoe heet je? 905 00:41:47,800 --> 00:41:48,499 >> DAVID: David. 906 00:41:48,499 --> 00:41:49,290 DAVID MALAN: David. 907 00:41:49,290 --> 00:41:49,998 Leuk je te ontmoeten. 908 00:41:49,998 --> 00:41:50,960 Ik ook. 909 00:41:50,960 --> 00:41:52,450 Prima. 910 00:41:52,450 --> 00:41:53,990 En we hebben een nummer 9. 911 00:41:53,990 --> 00:41:55,240 Niet zo goed als de eerste, misschien. 912 00:41:55,240 --> 00:41:56,430 OK, nummer 9. 913 00:41:56,430 --> 00:41:59,667 Een aantal 17, alstublieft. 914 00:41:59,667 --> 00:42:01,000 Laat me terug te gaan een beetje verder. 915 00:42:01,000 --> 00:42:03,980 Number 22, dan kunt u, en hoe zit verder terug 916 00:42:03,980 --> 00:42:06,344 als ik elke handen kan zien met al het licht of geen. 917 00:42:06,344 --> 00:42:08,010 Iemand die daar vrijwillig. 918 00:42:08,010 --> 00:42:08,968 Wilt u op de proppen komen? 919 00:42:08,968 --> 00:42:10,450 Onderarm wordt met geweld gaat omhoog. 920 00:42:10,450 --> 00:42:12,340 OK, 17. 921 00:42:12,340 --> 00:42:13,690 22. 922 00:42:13,690 --> 00:42:15,120 26 wordt naar beneden. 923 00:42:15,120 --> 00:42:18,450 Zou iemand anders willen forcefully-- Kom op maximaal. 924 00:42:18,450 --> 00:42:21,030 Een echte vrijwilliger. 925 00:42:21,030 --> 00:42:23,330 >> Dus zeer snel, als jullie kunnen regelen 926 00:42:23,330 --> 00:42:26,550 jezelf net als de knooppunten op het scherm. 927 00:42:26,550 --> 00:42:27,510 Dankjewel. 928 00:42:27,510 --> 00:42:29,234 En je zult 26. 929 00:42:29,234 --> 00:42:30,650 Oké en snelle introducties. 930 00:42:30,650 --> 00:42:32,139 Dus ik ben David en je bent ook? 931 00:42:32,139 --> 00:42:32,680 DAVID: David. 932 00:42:32,680 --> 00:42:33,721 DAVID MALAN: En u bent? 933 00:42:33,721 --> 00:42:34,229 JAKE: Jake. 934 00:42:34,229 --> 00:42:34,729 SUE: Sue. 935 00:42:34,729 --> 00:42:35,229 ALEX: Alex. 936 00:42:35,229 --> 00:42:36,475 RAPHAEL: Raphael. 937 00:42:36,475 --> 00:42:37,100 TAYLOR: Taylor. 938 00:42:37,100 --> 00:42:37,466 DAVID MALAN: Taylor. 939 00:42:37,466 --> 00:42:37,590 Excellent. 940 00:42:37,590 --> 00:42:39,810 Dus dit zijn onze vrijwilligers voor vandaag en ga je gang 941 00:42:39,810 --> 00:42:43,090 en verschuiven een beetje op die manier, en gewoon doorgaan en te houden 942 00:42:43,090 --> 00:42:47,024 houden van uw nummers als u of uw eerste teken en het gebruik van uw linkerhand, 943 00:42:47,024 --> 00:42:48,940 ga je gang en gewoon uit te voeren deze pijlen, net 944 00:42:48,940 --> 00:42:51,360 zodat uw linkerhand is letterlijk wijzend op wat je zou moeten wijzen 945 00:42:51,360 --> 00:42:54,610 bij, en geef jezelf wat ruimte, zodat kunnen we visueel zien je armen eigenlijk 946 00:42:54,610 --> 00:42:58,120 wijzen, en je kunt gewoon wijzen soort op de grond is prima. 947 00:42:58,120 --> 00:43:03,040 >> Dus hier hebben we een gelinkte lijst van één, twee, drie, vier, vijf knooppunten aanvankelijk 948 00:43:03,040 --> 00:43:05,860 en merken hebben wij deze speciale pointer aan het begin wie er 949 00:43:05,860 --> 00:43:09,770 key want we hebben om bij te houden van de gehele lengte lijst een of andere manier. 950 00:43:09,770 --> 00:43:13,590 Deze jongens, ook al zijn ze vertrokken naar rechts, rug aan rug in het geheugen, 951 00:43:13,590 --> 00:43:15,950 ze kunnen eigenlijk overal zijn in het geheugen van de computer. 952 00:43:15,950 --> 00:43:18,240 Dus deze jongens kunnen zijn staan ​​overal op het podium 953 00:43:18,240 --> 00:43:20,960 en dat is prima, zolang ze eigenlijk wijzen naar elkaar, 954 00:43:20,960 --> 00:43:22,770 maar om dingen te houden schoon en simpel, we 955 00:43:22,770 --> 00:43:25,728 ze gewoon trekken van links naar rechts, zoals , maar kunnen er grote leemten 956 00:43:25,728 --> 00:43:26,790 tussen die knooppunten. 957 00:43:26,790 --> 00:43:30,710 >> Nu, als ik wil eigenlijk voegen sommige nieuwe waarde, laten we verder gaan en doen dit. 958 00:43:30,710 --> 00:43:33,720 We hebben een kans nu een ander knooppunt kiezen. 959 00:43:33,720 --> 00:43:39,820 Zeggen laten we beginnen met mallocing 55. 960 00:43:39,820 --> 00:43:41,320 Zou iemand erg om malloc? 961 00:43:41,320 --> 00:43:42,280 Oké, kom op. 962 00:43:42,280 --> 00:43:42,992 Hoe heet je? 963 00:43:42,992 --> 00:43:43,700 RAINBOW: Regenboog. 964 00:43:43,700 --> 00:43:44,050 DAVID MALAN: Regenboog? 965 00:43:44,050 --> 00:43:44,810 Prima. 966 00:43:44,810 --> 00:43:46,600 Malloc Regenboog. 967 00:43:46,600 --> 00:43:47,450 Kom op maximaal. 968 00:43:47,450 --> 00:43:51,610 Dus nu moeten we ons afvragen algoritmisch waar we kunnen zetten 55. 969 00:43:51,610 --> 00:43:53,610 Dus alles van ons weten, natuurlijk, waar ze waarschijnlijk 970 00:43:53,610 --> 00:43:55,401 behoort als we proberen dit opgelost te houden 971 00:43:55,401 --> 00:43:58,299 en als jullie kon men rekening een stap terug zodat we niet vallen 972 00:43:58,299 --> 00:43:59,590 het podium, dat zou geweldig zijn. 973 00:43:59,590 --> 00:44:01,420 Dus eigenlijk, Rainbow, beginnen hier bij mij, 974 00:44:01,420 --> 00:44:04,200 omdat wij als de computer nu kan slechts een variabele zien op een moment. 975 00:44:04,200 --> 00:44:05,190 Als dit het eerste knooppunt. 976 00:44:05,190 --> 00:44:07,160 Merk op dat hij is niet een knooppunt, hij is gewoon een pointer, 977 00:44:07,160 --> 00:44:10,270 en dat is waarom hij is aangetrokken te zijn alleen de grootte van een pointer, niet 978 00:44:10,270 --> 00:44:11,780 zo'n volle rechthoeken. 979 00:44:11,780 --> 00:44:16,650 Dus we gaan om te controleren bij elke iteratie is 55 minder dan 9? 980 00:44:16,650 --> 00:44:17,150 Nee. 981 00:44:17,150 --> 00:44:19,060 Is 55 kleiner dan 17? 982 00:44:19,060 --> 00:44:19,720 Nee. 983 00:44:19,720 --> 00:44:20,800 Minder dan 22? 984 00:44:20,800 --> 00:44:22,020 Minder dan 26? 985 00:44:22,020 --> 00:44:23,390 Minder dan 34? 986 00:44:23,390 --> 00:44:25,890 En nu, uiteraard Regenboog behoort aan het einde. 987 00:44:25,890 --> 00:44:27,270 Dus om duidelijk te zijn, en wat was uw naam, Taylor? 988 00:44:27,270 --> 00:44:27,895 >> TAYLOR: Taylor. 989 00:44:27,895 --> 00:44:32,510 DAVID MALAN: Dus bij Taylor's linkerhand en Rainbow handen hier, 990 00:44:32,510 --> 00:44:38,324 wiens hand moet wijzen op wat in bestelling te plaatsen 55 in dit overzicht? 991 00:44:38,324 --> 00:44:39,240 Wat moeten we doen? 992 00:44:39,240 --> 00:44:39,700 Ja? 993 00:44:39,700 --> 00:44:41,140 >> PUBLIEK: hand Taylor's moet links wijzen. 994 00:44:41,140 --> 00:44:41,680 >> DAVID MALAN: Precies. 995 00:44:41,680 --> 00:44:43,800 Dus inbrengen van een knooppunt in het uiteinde van de lijst 996 00:44:43,800 --> 00:44:47,140 is vrij eenvoudig omdat Taylor net moet punt, in plaats van op de grond 997 00:44:47,140 --> 00:44:49,640 of we noemen het null, null is een soort van het ontbreken 998 00:44:49,640 --> 00:44:51,640 een pointer of een speciale nul wijzer, je bent 999 00:44:51,640 --> 00:44:53,740 ga naar punt met uw linkerhand hand op de regenboog en Rainbow, 1000 00:44:53,740 --> 00:44:55,910 Waar moet je linker waarschijnlijk de hand wijzen? 1001 00:44:55,910 --> 00:44:56,570 Naar beneden. 1002 00:44:56,570 --> 00:45:00,140 Het is niet goed als haar hand is een soort van wijzen hier of soort van off 1003 00:45:00,140 --> 00:45:00,640 welke kant op. 1004 00:45:00,640 --> 00:45:02,407 Dat zou worden overwogen een vuilnisbak waarde, 1005 00:45:02,407 --> 00:45:04,240 maar als ze wijst op sommige bekende waarde, zullen we 1006 00:45:04,240 --> 00:45:07,360 noem het nul of nul, dat is OK want we hebben een term in dit 1007 00:45:07,360 --> 00:45:09,390 en we weten dat de lijst is nu voltooid. 1008 00:45:09,390 --> 00:45:11,550 >> Dus wat is een ander relatief eenvoudig geval? 1009 00:45:11,550 --> 00:45:13,125 Kunnen we malloc 5? 1010 00:45:13,125 --> 00:45:14,010 Kom op maximaal. 1011 00:45:14,010 --> 00:45:14,782 Hoe heet je? 1012 00:45:14,782 --> 00:45:15,490 TIFFANY: Tiffany. 1013 00:45:15,490 --> 00:45:16,000 DAVID MALAN: Het spijt me? 1014 00:45:16,000 --> 00:45:16,470 TIFFANY: Tiffany. 1015 00:45:16,470 --> 00:45:16,880 DAVID MALAN: Tiffany. 1016 00:45:16,880 --> 00:45:17,110 Prima. 1017 00:45:17,110 --> 00:45:19,071 Tiffany is malloced de waarde 5. 1018 00:45:19,071 --> 00:45:19,570 Kom op maximaal. 1019 00:45:19,570 --> 00:45:23,820 Deze is relatief eenvoudig ook, maar laten we eens kijken volgorde van de operaties nu. 1020 00:45:23,820 --> 00:45:25,820 Het was vrij gemakkelijk met Taylor op het einde. 1021 00:45:25,820 --> 00:45:30,302 Nummer 5 is uiteraard minder dan 9, en dus hebben we David, hebben we Tiffany, 1022 00:45:30,302 --> 00:45:31,260 en wat is uw naam? 1023 00:45:31,260 --> 00:45:31,680 >> JAKE: Jake. 1024 00:45:31,680 --> 00:45:32,470 >> DAVID MALAN: Jake. 1025 00:45:32,470 --> 00:45:34,300 Tiffany, Jake, en David. 1026 00:45:34,300 --> 00:45:36,580 Wiens hand moet eerst worden bijgewerkt? 1027 00:45:36,580 --> 00:45:39,260 1028 00:45:39,260 --> 00:45:40,590 Wat wil je hier doen? 1029 00:45:40,590 --> 00:45:45,244 Er zijn een paar mogelijke manieren, maar er is ook een of meer verkeerde manieren. 1030 00:45:45,244 --> 00:45:46,620 >> PUBLIEK: Begin met de meest linkse. 1031 00:45:46,620 --> 00:45:47,800 >> DAVID MALAN: Begin met de meest linkse. 1032 00:45:47,800 --> 00:45:49,008 Wie is hier de meest linkse dan? 1033 00:45:49,008 --> 00:45:49,700 Publiek: First. 1034 00:45:49,700 --> 00:45:50,366 >> DAVID MALAN: OK. 1035 00:45:50,366 --> 00:45:53,781 Dus beginnen met de eerste en waar moet je wilt bijwerken David's handen zijn? 1036 00:45:53,781 --> 00:45:54,780 PUBLIEK: Naar de 5. 1037 00:45:54,780 --> 00:45:55,446 DAVID MALAN: OK. 1038 00:45:55,446 --> 00:45:59,026 Dus David, punt op vijf of Tiffany hier en nu? 1039 00:45:59,026 --> 00:46:01,072 >> PUBLIEK: Tiffany wijst op de 9? 1040 00:46:01,072 --> 00:46:04,030 DAVID MALAN: Perfect, met uitzondering van Binky's hoofd net soort viel, toch? 1041 00:46:04,030 --> 00:46:06,820 Want wat is er mis met deze foto letterlijk? 1042 00:46:06,820 --> 00:46:08,070 PUBLIEK: Niets wijst. 1043 00:46:08,070 --> 00:46:09,945 DAVID MALAN: Niets is wijzend naar Jake nu. 1044 00:46:09,945 --> 00:46:13,360 We hebben letterlijk wees 9 en 17, en we hebben letterlijk 1045 00:46:13,360 --> 00:46:18,450 lekte van dit geheugen, omdat door eerste actualisering van David's hand, dat is 1046 00:46:18,450 --> 00:46:21,660 fijn voorzover het correct wijzend op Tiffany nu, 1047 00:46:21,660 --> 00:46:25,410 maar als niemand had de vooruitziendheid te wijzen op Jake, 1048 00:46:25,410 --> 00:46:27,490 dan hebben we verloren de geheel van die lijst. 1049 00:46:27,490 --> 00:46:28,200 Dus laten we ongedaan te maken. 1050 00:46:28,200 --> 00:46:30,950 Dus dat was een goede zaak struikelen maar laten we corrigeren nu. 1051 00:46:30,950 --> 00:46:33,624 Wat moeten we eerste plaats doen? 1052 00:46:33,624 --> 00:46:34,124 Ja? 1053 00:46:34,124 --> 00:46:35,791 >> PUBLIEK: Tiffany moet wijzen op de 9? 1054 00:46:35,791 --> 00:46:37,582 DAVID MALAN: Ik kan niet krijgen die dicht bij je. 1055 00:46:37,582 --> 00:46:38,720 Wie moet wijzen op de 9? 1056 00:46:38,720 --> 00:46:39,220 >> Publiek: Tiffany. 1057 00:46:39,220 --> 00:46:39,390 >> DAVID MALAN: Oké. 1058 00:46:39,390 --> 00:46:41,200 Dus moet Tiffany eerste punt op de 9. 1059 00:46:41,200 --> 00:46:43,550 Dus Tiffany moet nemen op een identieke waarde 1060 00:46:43,550 --> 00:46:45,820 David, die lijkt redundant voor een moment, 1061 00:46:45,820 --> 00:46:48,820 maar dat komt omdat nu prima, tweede stap, kunnen we van David's hand te werken 1062 00:46:48,820 --> 00:46:52,680 te wijzen op Tiffany, en dan als we gewoon een soort van schone dingen 1063 00:46:52,680 --> 00:46:55,740 alsof dit is een soort van de lente-achtig, nu is dat een juiste plaatsing. 1064 00:46:55,740 --> 00:46:56,700 Zo uitstekend. 1065 00:46:56,700 --> 00:46:57,970 Dus nu zijn we er bijna. 1066 00:46:57,970 --> 00:47:01,075 Laten we voegen een laatste waarde als de waarde 20. 1067 00:47:01,075 --> 00:47:03,010 Als we nog een laatste vrijwilliger kon malloc? 1068 00:47:03,010 --> 00:47:04,140 Kom op maximaal. 1069 00:47:04,140 --> 00:47:06,224 Dus dit is een beetje lastig. 1070 00:47:06,224 --> 00:47:08,390 Maar echt, de code zijn we schrijven, hoewel mondeling, 1071 00:47:08,390 --> 00:47:10,610 is net als het hebben van een bos van als de omstandigheden nu, toch? 1072 00:47:10,610 --> 00:47:12,318 We hadden een aandoening controleren of het behoort 1073 00:47:12,318 --> 00:47:13,840 Aan het einde, misschien het begin. 1074 00:47:13,840 --> 00:47:15,940 We moeten een soort van lus vind de plek in het midden. 1075 00:47:15,940 --> 00:47:17,400 Dus laten we dat doen met wat is uw naam? 1076 00:47:17,400 --> 00:47:17,700 >> ERIC: Eric. 1077 00:47:17,700 --> 00:47:18,340 >> DAVID MALAN: Eric? 1078 00:47:18,340 --> 00:47:18,660 Eric. 1079 00:47:18,660 --> 00:47:19,368 Leuk je te ontmoeten. 1080 00:47:19,368 --> 00:47:20,490 Dus hebben we 20. 1081 00:47:20,490 --> 00:47:21,220 Minder dan vijf? 1082 00:47:21,220 --> 00:47:21,530 Nee. 1083 00:47:21,530 --> 00:47:22,160 Minder dan negen? 1084 00:47:22,160 --> 00:47:22,410 Nee. 1085 00:47:22,410 --> 00:47:23,050 Minder dan 17? 1086 00:47:23,050 --> 00:47:23,550 Nee. 1087 00:47:23,550 --> 00:47:23,740 OK. 1088 00:47:23,740 --> 00:47:25,701 Hij hier hoort en uw namen weer zijn? 1089 00:47:25,701 --> 00:47:26,200 SUE: Sue. 1090 00:47:26,200 --> 00:47:26,880 DAVID MALAN: Sue. 1091 00:47:26,880 --> 00:47:27,379 ALEX: Alex. 1092 00:47:27,379 --> 00:47:28,790 DAVID MALAN: Sue, Alex, en? 1093 00:47:28,790 --> 00:47:29,290 ERIC: Eric. 1094 00:47:29,290 --> 00:47:30,120 DAVID MALAN: Eric. 1095 00:47:30,120 --> 00:47:32,140 Wiens handen moeten krijgen eerste update? 1096 00:47:32,140 --> 00:47:32,930 >> Publiek: Eric. 1097 00:47:32,930 --> 00:47:33,429 OK. 1098 00:47:33,429 --> 00:47:35,200 Dus Eric's moeten wijzen naar waar? 1099 00:47:35,200 --> 00:47:35,930 Op 22. 1100 00:47:35,930 --> 00:47:36,430 Goed. 1101 00:47:36,430 --> 00:47:38,180 En nu wat is het volgende? 1102 00:47:38,180 --> 00:47:40,800 Sue kan dan wijzen op Eric en nu, als jullie gewoon 1103 00:47:40,800 --> 00:47:44,077 maak wat ruimte, die is prima visueel, nu hebben we het inbrengen gedaan. 1104 00:47:44,077 --> 00:47:47,160 Dus laten we nu eens een vraag, maar dank je wel voor onze vrijwilligers. 1105 00:47:47,160 --> 00:47:48,090 Heel goed gedaan. 1106 00:47:48,090 --> 00:47:50,831 U kunt houden die, als je wilt. 1107 00:47:50,831 --> 00:47:54,140 En we hebben een mooi afscheidscadeau als zou je elke willen een stress-bal te nemen. 1108 00:47:54,140 --> 00:47:56,030 Laat me gewoon langs deze naar beneden. 1109 00:47:56,030 --> 00:47:58,430 Dus wat is de afhaalmaaltijd van dit? 1110 00:47:58,430 --> 00:48:02,430 Dit lijkt geweldig te zijn voor zover we nu hebben 1111 00:48:02,430 --> 00:48:06,360 introduceerde alternatief voor een array niet beperkt 1112 00:48:06,360 --> 00:48:07,780 een array van een vast formaat. 1113 00:48:07,780 --> 00:48:09,380 Ze kunnen dynamisch groeien. 1114 00:48:09,380 --> 00:48:13,220 >> Maar net zoals we hebben gezien in weken verleden, nooit iets krijgen we gratis, 1115 00:48:13,220 --> 00:48:15,740 zeker als er een trade-off hier. 1116 00:48:15,740 --> 00:48:18,890 Dus met een bovenkant van een gekoppelde lijst, is deze dynamiek? 1117 00:48:18,890 --> 00:48:21,590 Dit vermogen om te groeien en eerlijk gezegd, we konden verwijderen hebben gedaan 1118 00:48:21,590 --> 00:48:23,570 en we kunnen krimpen nodig. 1119 00:48:23,570 --> 00:48:24,710 Welke prijs betalen we? 1120 00:48:24,710 --> 00:48:28,510 1121 00:48:28,510 --> 00:48:30,340 Tweemaal zoveel ruimte allereerst. 1122 00:48:30,340 --> 00:48:34,010 Als je kijkt naar de foto, niet langer ben ik het opslaan van een lijst met getallen. 1123 00:48:34,010 --> 00:48:36,740 Ik ben het opslaan van een lijst van integers plus pointers. 1124 00:48:36,740 --> 00:48:38,240 Dus ik ben een verdubbeling van de hoeveelheid ruimte. 1125 00:48:38,240 --> 00:48:40,740 Nu, misschien is dat niet zo'n big deal 4 bytes, 8 bytes, 1126 00:48:40,740 --> 00:48:43,160 maar kan zeker toevoegen voor grote datasets. 1127 00:48:43,160 --> 00:48:45,570 Wat is een ander nadeel? 1128 00:48:45,570 --> 00:48:46,070 Ja? 1129 00:48:46,070 --> 00:48:48,010 >> PUBLIEK: We moeten doorkruisen ze één voor één. 1130 00:48:48,010 --> 00:48:48,760 DAVID MALAN: Ja. 1131 00:48:48,760 --> 00:48:50,260 We moeten ze doorkruisen één voor één. 1132 00:48:50,260 --> 00:48:53,860 Weet je wat, we gaven deze super handige functie van square bracket 1133 00:48:53,860 --> 00:48:57,240 notatie, juister bekend als random access, 1134 00:48:57,240 --> 00:48:59,280 waar we gewoon kunnen springen een individueel element 1135 00:48:59,280 --> 00:49:01,470 maar nu als ik had nog steeds mijn vrijwilligers hier, 1136 00:49:01,470 --> 00:49:04,660 als ik wilde het vinden nummer 22, ik kan het gewoon niet 1137 00:49:04,660 --> 00:49:06,620 direct naar de beugel iets iets. 1138 00:49:06,620 --> 00:49:10,530 Ik heb om te kijken over de lijst, veel zoals onze zoeken voorbeelden lineair, 1139 00:49:10,530 --> 00:49:12,260 het nummer 22 vinden. 1140 00:49:12,260 --> 00:49:14,340 Dus lijken we een prijs die er voor hebben betaald. 1141 00:49:14,340 --> 00:49:16,430 Maar we kunnen toch andere problemen. 1142 00:49:16,430 --> 00:49:18,587 >> In feite, laat me introduceren slechts een paar van de visuals. 1143 00:49:18,587 --> 00:49:20,920 Dus als je naar beneden te zijn geweest Mather's Dining Hall onlangs, 1144 00:49:20,920 --> 00:49:23,320 u zult zich herinneren dat hun stapels trays als dit, 1145 00:49:23,320 --> 00:49:26,300 we geleend deze uit Annenberg voor de les. 1146 00:49:26,300 --> 00:49:28,930 Dus dit stapel trays, hoewel, representatief is eigenlijk 1147 00:49:28,930 --> 00:49:30,860 van een computer science datastructuur. 1148 00:49:30,860 --> 00:49:32,910 Er is een datastructuur in de informatica 1149 00:49:32,910 --> 00:49:38,010 bekend als een stack die erg mooi leent zich precies dit visueel. 1150 00:49:38,010 --> 00:49:41,380 Als elk van deze bakken geen lade, maar als een nummer en ik wilde 1151 00:49:41,380 --> 00:49:45,010 Voor nummers, I zou men hier beneden te zetten, 1152 00:49:45,010 --> 00:49:48,320 en ik kon nog hier neergezet, en verder stapelen nummers 1153 00:49:48,320 --> 00:49:53,180 boven elkaar, en wat potentieel behulpzaam over dit 1154 00:49:53,180 --> 00:49:55,450 is dat wat de implicatie deze gegevensstructuur? 1155 00:49:55,450 --> 00:49:58,045 Welk nummer kan ik trek eerst meest gunstig? 1156 00:49:58,045 --> 00:50:00,640 1157 00:50:00,640 --> 00:50:03,030 De meest recent een put op daar. 1158 00:50:03,030 --> 00:50:06,430 >> Dus dit is wat we zouden noemen in informatica een LIFO datastructuur. 1159 00:50:06,430 --> 00:50:08,070 Last in, first out. 1160 00:50:08,070 --> 00:50:10,800 En we zullen zien waarom het duurde niet lang dat kan nu nuttig maar zijn, 1161 00:50:10,800 --> 00:50:12,200 alleen rekening houden met de woning. 1162 00:50:12,200 --> 00:50:15,158 En het is een soort van dom als je denkt over hoe de eetzaal doet. 1163 00:50:15,158 --> 00:50:17,910 Elke keer als ze schoon en trays zet de verste die op de top, 1164 00:50:17,910 --> 00:50:22,160 je kon een eerder schoon hebben maar uiteindelijk erg vies en stoffig 1165 00:50:22,160 --> 00:50:24,360 lade op de bodem als je eigenlijk nooit 1166 00:50:24,360 --> 00:50:26,820 tot op de bodem van die stack, omdat je gewoon 1167 00:50:26,820 --> 00:50:29,380 houden invoering van de nieuwe en de schone bovenop. 1168 00:50:29,380 --> 00:50:31,840 Hetzelfde zou kunnen gebeuren in een supermarkt ook. 1169 00:50:31,840 --> 00:50:35,450 Als u een vitrine melk en elke keer CVS 1170 00:50:35,450 --> 00:50:37,610 of wie krijgt meer melk, je gewoon schuiven de melk 1171 00:50:37,610 --> 00:50:39,880 je al aan de rug en u de nieuwe voorkant, 1172 00:50:39,880 --> 00:50:43,088 je gaat naar een aantal mooie nare hebben melk aan het einde van de datastructuur, 1173 00:50:43,088 --> 00:50:46,390 omdat het altijd aan de onderkant of equivalent is het altijd achter. 1174 00:50:46,390 --> 00:50:50,407 >> Maar er is een andere manier om na te denken over voering gegevens en bijvoorbeeld deze. 1175 00:50:50,407 --> 00:50:53,490 Als je een van die mensen die graag line-up buiten Apple-winkels 1176 00:50:53,490 --> 00:50:55,610 wanneer een nieuw product komt out, bent u waarschijnlijk 1177 00:50:55,610 --> 00:50:58,780 niet met behulp van een stapel data structuur omdat u 1178 00:50:58,780 --> 00:51:03,070 zou vervreemden iedereen die is de rij om een ​​aantal nieuwe speeltje te kopen. 1179 00:51:03,070 --> 00:51:06,610 Integendeel, je bent waarschijnlijk met behulp wat voor soort data structuur 1180 00:51:06,610 --> 00:51:10,050 of wat voor soort systeem in de echte wereld? 1181 00:51:10,050 --> 00:51:13,493 Hopelijk is het een lijn, of meer goed of meer Britten-achtig, een wachtrij. 1182 00:51:13,493 --> 00:51:17,700 En het blijkt een wachtrij is ook een datastructuur in de informatica, 1183 00:51:17,700 --> 00:51:19,700 maar een wachtrij heeft een zeer anders eigendom. 1184 00:51:19,700 --> 00:51:20,820 Het is niet LIFO. 1185 00:51:20,820 --> 00:51:21,990 Last in, first out. 1186 00:51:21,990 --> 00:51:22,800 God verhoede. 1187 00:51:22,800 --> 00:51:24,280 Het FIFO plaats. 1188 00:51:24,280 --> 00:51:26,110 Als eerste erin, als eerste eruit. 1189 00:51:26,110 --> 00:51:27,970 En dat is een goede zaak voor eerlijkheid 'sake 1190 00:51:27,970 --> 00:51:30,428 zeker als je langs bent super vroeg in de ochtend. 1191 00:51:30,428 --> 00:51:33,400 Als je er eerst, u wil om eruit te komen eerst ook. 1192 00:51:33,400 --> 00:51:35,880 >> En zo al deze gegevens structuren, wachtrijen en stapels 1193 00:51:35,880 --> 00:51:39,220 en trossen van anderen, blijkt dat je kunt denken aan dit als slechts een array. 1194 00:51:39,220 --> 00:51:41,820 Dit is een matrix, misschien een vaste grootte 4, maar het zou 1195 00:51:41,820 --> 00:51:44,990 zijn wel leuk als we konden gewoon stapelen trays bijna oneindig lang als we 1196 00:51:44,990 --> 00:51:46,780 hebben dat veel trays of cijfers. 1197 00:51:46,780 --> 00:51:48,840 Dus misschien willen we gebruik maken van een gekoppelde lijst hier, 1198 00:51:48,840 --> 00:51:51,800 maar de trade-off gaat worden potentieel dat we meer geheugen nodig heeft, 1199 00:51:51,800 --> 00:51:55,930 neemt iets meer tijd, maar we kan de hoogte van de stapel niet beperken 1200 00:51:55,930 --> 00:51:59,550 net als Mather's vitrine kunnen beperken de grootte van de stack, 1201 00:51:59,550 --> 00:52:03,117 en dus deze zijn ontwerpbeslissingen of opties beschikbaar voor ons uiteindelijk. 1202 00:52:03,117 --> 00:52:04,950 Dus met deze gegevens structuren, zijn we begonnen 1203 00:52:04,950 --> 00:52:09,360 zien van nieuwe bovengrenzen potentieel van wat eerder was super snel 1204 00:52:09,360 --> 00:52:11,260 en waar we vertrekken off vandaag en waar de 1205 00:52:11,260 --> 00:52:13,200 we hopen te bereiken is op woensdag, zullen we 1206 00:52:13,200 --> 00:52:15,740 gaan kijken naar een data structuur die laat ons zoeken 1207 00:52:15,740 --> 00:52:18,260 door middel van data log eindtijd weer. 1208 00:52:18,260 --> 00:52:21,470 En we zagen dat, herinneren, in week nul en één met binaire zoeken of verdeel 1209 00:52:21,470 --> 00:52:22,180 en heers. 1210 00:52:22,180 --> 00:52:26,240 Het komt terug en beter nog, de heilige graal voor deze woensdag 1211 00:52:26,240 --> 00:52:29,510 zal komen met de gegevensstructuur die werkelijk uitgevoerd 1212 00:52:29,510 --> 00:52:32,070 of theoretisch in constante tijd, waarbij 1213 00:52:32,070 --> 00:52:34,760 het maakt niet uit hoeveel miljoenen of miljarden van de dingen 1214 00:52:34,760 --> 00:52:38,470 We hebben in de gegevensstructuur, zal neem ons constante tijd, misschien een stap 1215 00:52:38,470 --> 00:52:41,387 of twee stappen of 10 stappen, maar constante aantal stappen 1216 00:52:41,387 --> 00:52:42,970 om door middel van die gegevensstructuur. 1217 00:52:42,970 --> 00:52:46,300 Dat zal inderdaad de heilige graal zijn maar daarover woensdag. 1218 00:52:46,300 --> 00:52:49,045 Zie je dan. 1219 00:52:49,045 --> 00:52:53,704 >> [Muziek] 1220 00:52:53,704 --> 00:56:08,448