1 00:00:00,000 --> 00:00:03,381 >> [Speel van musiek] 2 00:00:03,381 --> 00:00:10,626 3 00:00:10,626 --> 00:00:11,610 >> [Video speel] 4 00:00:11,610 --> 00:00:13,640 >> -hy Lieg. 5 00:00:13,640 --> 00:00:14,380 >> -About Wat? 6 00:00:14,380 --> 00:00:17,182 >> -Ek weet nie. 7 00:00:17,182 --> 00:00:19,990 >> -So wat weet ons? 8 00:00:19,990 --> 00:00:23,145 >> -dat Op 09:15, Ray Santoya was by die OTM. 9 00:00:23,145 --> 00:00:23,644 -Yeah. 10 00:00:23,644 --> 00:00:27,030 So die vraag is, wat hy doen op 09:16? 11 00:00:27,030 --> 00:00:29,720 >> -Shooting Die 9 millimeter na iets. 12 00:00:29,720 --> 00:00:31,540 Miskien sien hy die sniper. 13 00:00:31,540 --> 00:00:33,412 >> -of Besig was met hom. 14 00:00:33,412 --> 00:00:34,340 >> -Wait. 15 00:00:34,340 --> 00:00:36,200 Gaan terug een. 16 00:00:36,200 --> 00:00:36,975 >> -Wat sien jy? 17 00:00:36,975 --> 00:00:44,400 18 00:00:44,400 --> 00:00:47,805 >> -Bring Sy gesig vol skerm. 19 00:00:47,805 --> 00:00:48,680 >> -Sy bril. 20 00:00:48,680 --> 00:00:50,060 >> -Daar Is 'n weerspieëling. 21 00:00:50,060 --> 00:01:00,455 22 00:01:00,455 --> 00:01:02,280 >> -Dit Is die Nuevitas baseball span. 23 00:01:02,280 --> 00:01:03,110 Dit is hul logo. 24 00:01:03,110 --> 00:01:05,820 >> -en Hy praat om wie se dra dat baadjie. 25 00:01:05,820 --> 00:01:06,670 >> [Einde afspeel] 26 00:01:06,670 --> 00:01:07,628 >> David Malan: Alle reg. 27 00:01:07,628 --> 00:01:11,210 Dit is CS50, en dit is 'n bietjie meer van [onhoorbaar] waarmee jy 28 00:01:11,210 --> 00:01:12,890 rondspeel met die probleem sit vier. 29 00:01:12,890 --> 00:01:16,606 Vandag het ons begin om 'n bietjie meer te kyk diep op hierdie dinge genoem wysers, 30 00:01:16,606 --> 00:01:18,480 wat selfs al is dit n mooi arcane onderwerp 31 00:01:18,480 --> 00:01:20,813 dit blyk dat dit gaan die middel wees waardeur ons 32 00:01:20,813 --> 00:01:24,320 kan begin bou en samestelling veel meer gesofistikeerde programme. 33 00:01:24,320 --> 00:01:28,150 Maar ons het dit op verlede Woensdag deur die eerste manier van sommige claymation. 34 00:01:28,150 --> 00:01:30,190 So hierdie, onthou, is Binky en ons het hom gebruik 35 00:01:30,190 --> 00:01:33,148 'n blik op 'n program wat neem het nie regtig iets interessant, 36 00:01:33,148 --> 00:01:34,950 maar dit het 'n paar probleme openbaar. 37 00:01:34,950 --> 00:01:38,570 So om te begin vandag, hoekom het ons nie loop vinnig deur 'n paar van hierdie stappe, 38 00:01:38,570 --> 00:01:41,920 probeer om distilleer in terme menslike se presies wat gaan hier aan 39 00:01:41,920 --> 00:01:45,410 en waarom dit is sleg, en dan beweeg op en eintlik begin die bou van iets 40 00:01:45,410 --> 00:01:46,309 met hierdie tegniek? 41 00:01:46,309 --> 00:01:48,350 So dit was die eerste twee lyne in hierdie program 42 00:01:48,350 --> 00:01:51,340 en in leketaal, wat word hierdie twee lyne doen? 43 00:01:51,340 --> 00:01:55,600 Iemand wat redelik gemaklik met wat verklaar word op die skerm? 44 00:01:55,600 --> 00:01:58,340 45 00:01:58,340 --> 00:02:00,120 Wat is hierdie twee lyne doen? 46 00:02:00,120 --> 00:02:02,070 Dit is nie al wat anders week een, 47 00:02:02,070 --> 00:02:03,611 maar daar is 'n paar nuwe spesiale simbool. 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 >> GEHOOR: Verklaar riglyne? 51 00:02:07,092 --> 00:02:08,050 David Malan: Weer sê? 52 00:02:08,050 --> 00:02:08,860 GEHOOR: Verklaar riglyne? 53 00:02:08,860 --> 00:02:11,776 David Malan: Verklaar wysers en laat verfyn dit 'n bietjie meer. 54 00:02:11,776 --> 00:02:14,050 GEHOOR: [onhoorbaar] adres x en dan y. 55 00:02:14,050 --> 00:02:15,300 David Malan: En dan spreek. 56 00:02:15,300 --> 00:02:18,550 So spesifiek wat ons doen is ons verklaar twee veranderlikes. 57 00:02:18,550 --> 00:02:21,252 Hierdie veranderlikes, al is, gaan van die tipe int ster te wees wat 58 00:02:21,252 --> 00:02:23,210 meer spesifiek beteken hulle gaan om te slaan 59 00:02:23,210 --> 00:02:26,450 die adres van 'n int, onderskeidelik, x en y. 60 00:02:26,450 --> 00:02:27,660 Nou is daar enige waardes? 61 00:02:27,660 --> 00:02:32,621 Is daar enige werklike adresse in hierdie twee veranderlikes op hierdie punt in die tyd? 62 00:02:32,621 --> 00:02:33,120 Geen. 63 00:02:33,120 --> 00:02:35,030 Dit is net die sogenaamde vullis waardes. 64 00:02:35,030 --> 00:02:38,120 As jy nie eintlik wys 'n veranderlike, ongeag in RAM was 65 00:02:38,120 --> 00:02:42,224 voorheen gaan vul met nulle en dié beide van die veranderlikes. 66 00:02:42,224 --> 00:02:44,140 Maar ons weet nog nie wat hulle is en dit is 67 00:02:44,140 --> 00:02:47,060 gaan die sleutel tot hoekom Binky te wees verloor sy kop verlede week. 68 00:02:47,060 --> 00:02:49,980 >> So dit was die claymation inkarnasie van hierdie 69 00:02:49,980 --> 00:02:53,580 waardeur jy net twee veranderlikes, bietjie omsendbrief stukke van klei 70 00:02:53,580 --> 00:02:57,330 wat kan veranderlikes slaan nie, maar as die toegedraai pyle dui, 71 00:02:57,330 --> 00:03:00,640 hulle is nie eintlik wys om oral bekend per se. 72 00:03:00,640 --> 00:03:03,670 So dan het ons hierdie lyn, en dit was 'n nuwe verlede week, malloc vir die geheue 73 00:03:03,670 --> 00:03:07,130 toekenning, wat net 'n fancy manier van die vertel van die bedryfstelsel, Linux 74 00:03:07,130 --> 00:03:09,750 of Mac OS of Windows, hey, gee my 'n paar geheue, 75 00:03:09,750 --> 00:03:11,780 en al wat jy hoef te vertel die bedryfstelsel 76 00:03:11,780 --> 00:03:14,699 is wat toe vra dit vir die geheue. 77 00:03:14,699 --> 00:03:16,990 Dit gaan nie om te sorg wat jy gaan om dit te doen met dit, 78 00:03:16,990 --> 00:03:19,786 maar jy moet om die bedryfstelsel te vertel stelsel wat deur middel van malloc. 79 00:03:19,786 --> 00:03:20,286 Ja? 80 00:03:20,286 --> 00:03:21,078 >> GEHOOR: Hoeveel? 81 00:03:21,078 --> 00:03:21,994 David Malan: Hoeveel? 82 00:03:21,994 --> 00:03:25,280 Hoeveel in grepe, en so is dit weer, 'n geforseerde byvoorbeeld net sê, 83 00:03:25,280 --> 00:03:27,360 gee my die grootte van 'n int. 84 00:03:27,360 --> 00:03:30,550 Nou, die grootte van 'n int vier grepe of 32 stukkies. 85 00:03:30,550 --> 00:03:32,850 So dit is net 'n manier om sê, hey, bedryfstelsel, 86 00:03:32,850 --> 00:03:37,290 gee my vier grepe van die geheue wat ek kan gebruik tot my beskikking, 87 00:03:37,290 --> 00:03:40,560 en spesifiek, wat beteken malloc terugkeer met betrekking 88 00:03:40,560 --> 00:03:41,795 om daardie deel van vier grepe? 89 00:03:41,795 --> 00:03:44,110 90 00:03:44,110 --> 00:03:44,860 GEHOOR: spreek? 91 00:03:44,860 --> 00:03:45,901 David Malan: Die adres. 92 00:03:45,901 --> 00:03:47,580 Die adres van daardie deel van vier grepe. 93 00:03:47,580 --> 00:03:48,190 Presies. 94 00:03:48,190 --> 00:03:51,430 En so dit is wat uiteindelik gestoor in x en dit is hoekom ons nie regtig 95 00:03:51,430 --> 00:03:55,240 omgee wat die nommer van daardie adres is, of dit nou OX1 of OX2 96 00:03:55,240 --> 00:03:57,110 of 'n kriptiese heksadesimale adres. 97 00:03:57,110 --> 00:03:59,850 Ons gee net picturaal dat veranderlike x is nou 98 00:03:59,850 --> 00:04:01,630 wys dat die stuk van die geheue. 99 00:04:01,630 --> 00:04:05,570 So het die pyl verteenwoordig 'n wyser, of meer spesifiek, 'n geheue adres. 100 00:04:05,570 --> 00:04:09,120 Maar weereens, ons nie omgee tipies wat daardie werklike adresse. 101 00:04:09,120 --> 00:04:11,780 Nou, hierdie lyn sê wat in leketaal? 102 00:04:11,780 --> 00:04:14,330 Star x kry 42 kommapunt. 103 00:04:14,330 --> 00:04:17,390 Wat beteken dit? 104 00:04:17,390 --> 00:04:18,200 Jy wil gaan? 105 00:04:18,200 --> 00:04:20,102 Moenie krap jou nek. 106 00:04:20,102 --> 00:04:22,360 >> GEHOOR: Die adres van x is by die 42. 107 00:04:22,360 --> 00:04:24,300 >> David Malan: Die adres van x is op 42. 108 00:04:24,300 --> 00:04:25,190 Nie heeltemaal nie. 109 00:04:25,190 --> 00:04:28,485 So naby, maar nie heeltemal nie, want daar is die ster wat se voorvoegsel hierdie x. 110 00:04:28,485 --> 00:04:29,860 So moet ons 'n bietjie tweak. 111 00:04:29,860 --> 00:04:31,032 Ja? 112 00:04:31,032 --> 00:04:36,044 >> GEHOOR: Die waarde wat die wyser x dui op is 42. 113 00:04:36,044 --> 00:04:36,710 David Malan: OK. 114 00:04:36,710 --> 00:04:40,840 Die waarde wat die wyser x is verwys na, kom ons sê, sal 42, 115 00:04:40,840 --> 00:04:44,165 of 'n ander manier, die ster x sê, gaan na wat ookal adres 116 00:04:44,165 --> 00:04:48,340 is in x, of dit nou 1 Oxford Straat of 33 Oxford Street 117 00:04:48,340 --> 00:04:51,850 of OX1 of ox33, ongeag dat numeriese adres is 118 00:04:51,850 --> 00:04:54,380 star x is die dereferencing van x. 119 00:04:54,380 --> 00:04:57,297 So gaan na daardie adres en dan sit die getal 42 is daar. 120 00:04:57,297 --> 00:04:59,380 Sodat sou wees 'n ekwivalent manier om te sê nie. 121 00:04:59,380 --> 00:05:01,860 So dit is alles goed en dan sou ons die prentjie verteenwoordig 122 00:05:01,860 --> 00:05:05,370 soos volg waar ons het bygevoeg die 42 tot daardie deel van vier 123 00:05:05,370 --> 00:05:09,370 grepe op die regterkant, maar hierdie lyn was waar dinge skeefgeloop 124 00:05:09,370 --> 00:05:11,120 en Binky se kop inloer af op hierdie punt, 125 00:05:11,120 --> 00:05:15,290 omdat slegte dinge gebeur wanneer jy dereference vullis waardes 126 00:05:15,290 --> 00:05:18,210 of jy dereference ongeldig wysers, en ek sê ongeldig 127 00:05:18,210 --> 00:05:21,020 want op hierdie punt in die storie, wat is die binnekant van y? 128 00:05:21,020 --> 00:05:24,440 Wat is die waarde van y gebaseer op die afgelope paar stappe? 129 00:05:24,440 --> 00:05:25,360 Ja? 130 00:05:25,360 --> 00:05:26,115 Wat is dit? 131 00:05:26,115 --> 00:05:26,990 >> GEHOOR: 'n adres. 132 00:05:26,990 --> 00:05:28,460 David Malan: 'n adres. 133 00:05:28,460 --> 00:05:31,910 Dit moet 'n adres maar ek het dit geïnisialiseer? 134 00:05:31,910 --> 00:05:32,800 So ek nog nie. 135 00:05:32,800 --> 00:05:35,430 So, wat is bekend te wees daar? 136 00:05:35,430 --> 00:05:37,590 Dit is net 'n paar vullis waarde. 137 00:05:37,590 --> 00:05:41,500 Dit kan enige adres van nul te wees 2000000000 as jy twee gigs RAM, 138 00:05:41,500 --> 00:05:44,289 of nul tot 4 miljard as jy het het vier GB RAM. 139 00:05:44,289 --> 00:05:46,080 Dit is 'n paar vullis waarde maar die probleem is 140 00:05:46,080 --> 00:05:48,200 dat die bedryfstelsel, As dit nie vir jou gegee het 141 00:05:48,200 --> 00:05:51,140 wat deel van die geheue spesifiek dat jy probeer om te gaan na, 142 00:05:51,140 --> 00:05:54,650 dit is oor die algemeen gaan wat veroorsaak ons gesien as 'n segmentering skuld. 143 00:05:54,650 --> 00:05:57,810 So in werklikheid, enige van julle wat gesukkel op probleme by kantoorure 144 00:05:57,810 --> 00:06:00,393 of in probleme wat meer algemeen met die probeer om uit te vind 145 00:06:00,393 --> 00:06:02,150 'n segmentering skuld, dit beteken dat die algemeen 146 00:06:02,150 --> 00:06:05,017 Jy is 'n segment van die aanraak geheue wat jy nie moet wees nie. 147 00:06:05,017 --> 00:06:07,350 Jy geheue raak wat die bedryfstelsel het nie 148 00:06:07,350 --> 00:06:10,450 toegelaat dat jy raak, of dit nou deur te gaan te ver in jou array 149 00:06:10,450 --> 00:06:12,870 of die begin nou, of dit is omdat jy raak 150 00:06:12,870 --> 00:06:14,780 geheue wat net 'n paar is vullis waarde. 151 00:06:14,780 --> 00:06:18,230 >> So doen star x hier soort van undefined gedrag. 152 00:06:18,230 --> 00:06:22,030 Jy moet nooit doen dit omdat kans is, is die program net gaan om te crash, 153 00:06:22,030 --> 00:06:24,050 omdat jy sê: na hierdie adres 154 00:06:24,050 --> 00:06:27,000 en jy het geen idee waar daardie adres eintlik is. 155 00:06:27,000 --> 00:06:30,300 So die bedryfstelsel is waarskynlik gaan jou program crash 156 00:06:30,300 --> 00:06:33,840 as 'n gevolg en inderdaad, dit is wat daar gebeur het om Binky. 157 00:06:33,840 --> 00:06:37,210 So uiteindelik Binky vaste hierdie probleem met hierdie. 158 00:06:37,210 --> 00:06:38,909 Sodat program self gebrekkig was. 159 00:06:38,909 --> 00:06:41,450 Maar as jy soort van vooruit en uit te voer hierdie lyn plaas, 160 00:06:41,450 --> 00:06:45,580 y is gelyk aan x beteken net watter adres is 'n x, sit dit ook in y. 161 00:06:45,580 --> 00:06:48,740 >> En so picturaal, het ons verteenwoordig dit met twee pyltjies 162 00:06:48,740 --> 00:06:51,570 van x en y uit wys na dieselfde plek. 163 00:06:51,570 --> 00:06:55,760 So semanties, x is gelyk y omdat beide van hulle 164 00:06:55,760 --> 00:07:00,300 is die stoor van die dieselfde adres, ergo wys op 42, 165 00:07:00,300 --> 00:07:04,910 en nou, wanneer jy sê ster y, gaan na die adres in y, 166 00:07:04,910 --> 00:07:06,790 dit het 'n interessante newe-effek. 167 00:07:06,790 --> 00:07:10,320 So die adres in y is die dieselfde ding as die adres in x. 168 00:07:10,320 --> 00:07:15,060 So as jy sê gaan na die adres in y en verander die waarde tot 13, 169 00:07:15,060 --> 00:07:17,140 wie anders geraak word? 170 00:07:17,140 --> 00:07:21,100 X is, punt D, om so te praat, moet sowel geraak word. 171 00:07:21,100 --> 00:07:24,340 >> En inderdaad, hoe Nick het hierdie foto in claymation was presies dit. 172 00:07:24,340 --> 00:07:28,665 Selfs al het ons volg die wyser y, ons beland in die dieselfde plek, 173 00:07:28,665 --> 00:07:32,780 en so as ons druk uit x of y se pointee, 174 00:07:32,780 --> 00:07:35,720 dan sou ons die waarde van 13 te sien. 175 00:07:35,720 --> 00:07:37,927 Nou, ek sê pointee te wees in ooreenstemming met die video. 176 00:07:37,927 --> 00:07:39,760 Programmeerders, om my kennis, nooit werklik 177 00:07:39,760 --> 00:07:42,460 sê die woord pointee, wat is skerp 178 00:07:42,460 --> 00:07:44,650 op, maar vir konsekwentheid met die video, besef 179 00:07:44,650 --> 00:07:47,520 dit is al wat dit was bedoel in daardie situasie. 180 00:07:47,520 --> 00:07:54,190 So enige vrae oor claymation of wenke of malloc net nog? 181 00:07:54,190 --> 00:07:54,850 Geen? 182 00:07:54,850 --> 00:07:55,470 Alles reg. 183 00:07:55,470 --> 00:07:58,560 >> So sonder verdere ado, laat ons neem 'n blik 184 00:07:58,560 --> 00:08:00,700 na waar dit het eintlik gebruik is vir 'n geruime tyd. 185 00:08:00,700 --> 00:08:03,580 So het ons dit CS50 biblioteek gehad Dit is het al hierdie funksies. 186 00:08:03,580 --> 00:08:06,810 Ons het gebruik GetInt 'n baie, GetString, waarskynlik vroeër GetLongLong 187 00:08:06,810 --> 00:08:09,840 in my PSet een of so, maar wat eintlik aan die gang? 188 00:08:09,840 --> 00:08:12,920 Wel, laat ons neem 'n vinnige blik onder die enjinkap op 'n program wat 189 00:08:12,920 --> 00:08:17,017 inspireer Daarom gee ons jou die CS50 biblioteek, en inderdaad as van verlede week, 190 00:08:17,017 --> 00:08:18,850 ons begin om diegene opleiding wiele af. 191 00:08:18,850 --> 00:08:21,080 So dit is nou gesorteer van 'n nadoodse van wat 192 00:08:21,080 --> 00:08:23,690 is aan die gang binne-in die CS50 biblioteek, 193 00:08:23,690 --> 00:08:27,250 selfs al het ons nou begin beweeg weg van dit vir die meeste programme. 194 00:08:27,250 --> 00:08:29,460 >> So, dit is 'n program genaamd scanf 0. 195 00:08:29,460 --> 00:08:30,510 Dit is super kort. 196 00:08:30,510 --> 00:08:33,909 Dit het net hierdie lyne, maar dit stel 'n funksie genoem scanf 197 00:08:33,909 --> 00:08:36,909 dat ons eintlik gaan om te sien in 'n oomblik binnekant van die CS50 biblioteek, 198 00:08:36,909 --> 00:08:38,600 al is dit in 'n effens ander vorm. 199 00:08:38,600 --> 00:08:41,330 So hierdie program op die lyn 16 is waarby 'n veranderlike x. 200 00:08:41,330 --> 00:08:43,150 So gee my vier grepe vir 'n int. 201 00:08:43,150 --> 00:08:45,750 Dit is al vertel gebruiker aantal asseblief, en dan 202 00:08:45,750 --> 00:08:49,010 dit is 'n interessante lyn wat bande eintlik saam verlede week 203 00:08:49,010 --> 00:08:49,790 en hierdie. 204 00:08:49,790 --> 00:08:53,230 Scanf, en dan sien dit neem 'n formaat string, net soos printf, 205 00:08:53,230 --> 00:08:57,480 % i beteken 'n int, en dan is dit neem 'n tweede argument wat lyk 'n bietjie 206 00:08:57,480 --> 00:08:58,260 funky. 207 00:08:58,260 --> 00:09:01,880 Dit is ampersand x, en om te onthou, ons net het hierdie keer die afgelope week. 208 00:09:01,880 --> 00:09:03,465 Wat beteken ampersand x verteenwoordig? 209 00:09:03,465 --> 00:09:06,210 210 00:09:06,210 --> 00:09:08,450 Wat beteken ampersand doen in C? 211 00:09:08,450 --> 00:09:08,950 Ja? 212 00:09:08,950 --> 00:09:10,024 >> GEHOOR: Die adres van. 213 00:09:10,024 --> 00:09:11,190 David Malan: Die adres van. 214 00:09:11,190 --> 00:09:13,190 So dit is die teenoorgestelde van die ster-operateur, 215 00:09:13,190 --> 00:09:17,270 terwyl die ster operateur sê, gaan na hierdie toespraak het die ampersand operateur 216 00:09:17,270 --> 00:09:20,280 sê, uit te vind die adres van hierdie veranderlike, 217 00:09:20,280 --> 00:09:23,530 en so is dit die sleutel, want doel in die lewe se scanf 218 00:09:23,530 --> 00:09:26,320 is om te scan die gebruiker se insette van die sleutelbord, 219 00:09:26,320 --> 00:09:29,970 afhangende van wat hy of sy tipes, en lees dan insette van die gebruiker 220 00:09:29,970 --> 00:09:32,970 in 'n veranderlike, maar ons gesien in die afgelope twee weke 221 00:09:32,970 --> 00:09:36,080 dat swap funksie wat ons moeiteloos probeer om te implementeer 222 00:09:36,080 --> 00:09:37,110 was net gebreek. 223 00:09:37,110 --> 00:09:42,470 Onthou dat die ruil-funksie, as ons net verklaar A en B as SY, 224 00:09:42,470 --> 00:09:47,040 ons het suksesvol ruil die twee veranderlikes binne ruil 225 00:09:47,040 --> 00:09:50,080 net soos met die melk en PB, maar sodra swap teruggekeer, 226 00:09:50,080 --> 00:09:55,200 wat was die uitslag met betrekking x en y, die oorspronklike waardes? 227 00:09:55,200 --> 00:09:55,700 Niks nie. 228 00:09:55,700 --> 00:09:56,200 Ja. 229 00:09:56,200 --> 00:09:59,754 Niks gebeur daardie tyd, want swaps verander net sy plaaslike kopieë, 230 00:09:59,754 --> 00:10:01,670 wat is om te sê, al hierdie tyd, wanneer ons het 231 00:10:01,670 --> 00:10:04,010 is verby in argumente funksies, ons is 232 00:10:04,010 --> 00:10:05,939 net verby afskrifte van daardie argumente. 233 00:10:05,939 --> 00:10:07,980 Wat jy kan doen met dit alles wat jy wil met hulle, 234 00:10:07,980 --> 00:10:10,890 maar hulle gaan nie het uitwerking op die oorspronklike waardes. 235 00:10:10,890 --> 00:10:13,650 So dit is problematies as jy wil 'n funksie soos scanf het 236 00:10:13,650 --> 00:10:17,170 in die lewe, wie se doel is om te scan insette van die gebruiker se vanaf die sleutelbord 237 00:10:17,170 --> 00:10:22,010 en dan in die spasies in te vul, om so te spreek, dit is, gee 'n veranderlike soos x 238 00:10:22,010 --> 00:10:25,410 'n waarde, want as ek net slaag x om scanf, 239 00:10:25,410 --> 00:10:28,790 as jy die logika van verlede oorweeg week, kan scanf doen wat dit wil 240 00:10:28,790 --> 00:10:33,100 met 'n afskrif van x, maar dit kon nie permanent x verander tensy ons gee 241 00:10:33,100 --> 00:10:37,120 scanf n skat kaart, om so te praat, waar x dui die plek, waardeur 242 00:10:37,120 --> 00:10:41,860 Ons slaag in die adres van x sodat scanf kan daar en eintlik verandering gaan 243 00:10:41,860 --> 00:10:42,920 die waarde van x. 244 00:10:42,920 --> 00:10:45,080 En so ja, al dat hierdie program nie 245 00:10:45,080 --> 00:10:53,180 en maak ek scanf 0, in my bron 5m gids, maak scanf 0, 246 00:10:53,180 --> 00:10:57,730 dot streep scanf, nommer asseblief 50, dankie vir die 50. 247 00:10:57,730 --> 00:11:01,020 >> So dit is nie al wat interessant, maar wat wel gebeur 248 00:11:01,020 --> 00:11:04,820 is dat so gou as ek roep scanf hier, die waarde van x 249 00:11:04,820 --> 00:11:06,410 word permanent verander. 250 00:11:06,410 --> 00:11:08,335 Nou, dit lyk mooi en goed, en in werklikheid, is dit 251 00:11:08,335 --> 00:11:11,200 lyk asof ons nie regtig nodig die CS50 biblioteek by al nie. 252 00:11:11,200 --> 00:11:13,960 Byvoorbeeld, laat loop Dit is hier weer. 253 00:11:13,960 --> 00:11:15,750 Laat my heropen dit vir 'n tweede. 254 00:11:15,750 --> 00:11:20,600 Kom ons probeer 'n aantal asseblief en in plaas van sê 50 soos tevore, 255 00:11:20,600 --> 00:11:22,810 laat ons net sê nie. 256 00:11:22,810 --> 00:11:24,000 OK, dit is 'n bietjie vreemd. 257 00:11:24,000 --> 00:11:25,270 OK. 258 00:11:25,270 --> 00:11:28,680 En net 'n paar nonsens hier. 259 00:11:28,680 --> 00:11:31,170 So dit lyk nie hanteer foutiewe situasies. 260 00:11:31,170 --> 00:11:33,620 So moet ons begin minimaal voeg 'n paar foute kontrole 261 00:11:33,620 --> 00:11:37,460 om seker te maak dat die gebruiker getik in 'n werklike nommer soos 50, 262 00:11:37,460 --> 00:11:40,720 want blykbaar tik woorde nie opgespoor as problematies, 263 00:11:40,720 --> 00:11:42,020 maar dit moet seker wees. 264 00:11:42,020 --> 00:11:46,450 >> Kom ons kyk na hierdie weergawe nou dat die my poging om reimplement GetString. 265 00:11:46,450 --> 00:11:48,437 As scanf het dit alles funksie gebou in, 266 00:11:48,437 --> 00:11:51,270 Daarom het ons rondspeel met hierdie opleiding wiele soos GetString? 267 00:11:51,270 --> 00:11:55,450 Wel, hier is dalk my eie eenvoudige weergawe van GetString 268 00:11:55,450 --> 00:12:00,766 waardeur 'n week gelede, kan ek gesê het, gee my 'n string en noem dit buffer. 269 00:12:00,766 --> 00:12:03,390 Vandag, ek gaan net begin sê char ster wat, onthou, 270 00:12:03,390 --> 00:12:04,400 dit is net sinoniem. 271 00:12:04,400 --> 00:12:06,629 Dit lyk vreesaanjaend, maar dit is presies dieselfde ding. 272 00:12:06,629 --> 00:12:09,420 So gee my 'n veranderlike genoem buffer wat gaan om 'n string te slaan, 273 00:12:09,420 --> 00:12:12,780 vertel die gebruiker string asseblief, en dan, net soos voorheen, 274 00:12:12,780 --> 00:12:17,760 Kom ons probeer om hierdie les te leen scanf % s hierdie tyd en dan slaag in buffer. 275 00:12:17,760 --> 00:12:19,310 Nou, 'n vinnige gesonde verstand tjek. 276 00:12:19,310 --> 00:12:22,120 Hoekom ek sê nie ampersand buffer hierdie tyd? 277 00:12:22,120 --> 00:12:25,190 278 00:12:25,190 --> 00:12:26,625 Aflei uit die vorige voorbeeld. 279 00:12:26,625 --> 00:12:28,000 GEHOOR: Char ster is 'n wyser. 280 00:12:28,000 --> 00:12:29,920 David Malan: Presies, want hierdie keer, char 281 00:12:29,920 --> 00:12:34,080 star is reeds 'n wyser, 'n adres, per definisie van daardie sterre daar te wees. 282 00:12:34,080 --> 00:12:37,530 En as scanf verwag 'n adres, is dit voldoende om te slaag in net buffer. 283 00:12:37,530 --> 00:12:39,260 Ek het nie nodig om ampersand buffer sê. 284 00:12:39,260 --> 00:12:42,177 Vir die nuuskierige, kan jy iets soos dit te doen. 285 00:12:42,177 --> 00:12:43,510 Dit sou verskillende betekenis hê. 286 00:12:43,510 --> 00:12:47,240 Dit sou 'n wyser gee jou om 'n wyser, wat eintlik 287 00:12:47,240 --> 00:12:50,050 'n geldige ding in C nie, maar vir nou, laat ons hou dit eenvoudig 288 00:12:50,050 --> 00:12:51,750 en hou die storie konsekwent. 289 00:12:51,750 --> 00:12:54,100 Ek gaan net om in te slaag buffer en dit is korrek. 290 00:12:54,100 --> 00:12:56,487 Die probleem is egter hiervan. 291 00:12:56,487 --> 00:12:58,820 Laat my gaan voort en hardloop hierdie program na die opstel van dit. 292 00:12:58,820 --> 00:13:00,902 Maak scanf 1. 293 00:13:00,902 --> 00:13:02,610 Damn, my samesteller se my fout vang. 294 00:13:02,610 --> 00:13:04,090 Gee my 'n sekonde. 295 00:13:04,090 --> 00:13:05,460 Klang. 296 00:13:05,460 --> 00:13:06,990 Kom ons sê 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 ons. 300 00:13:12,720 --> 00:13:14,280 Ek het dit nodig. 301 00:13:14,280 --> 00:13:16,750 CS50 ID het verskeie konfigurasie-instellings 302 00:13:16,750 --> 00:13:18,280 dat jy beskerm teen jouself. 303 00:13:18,280 --> 00:13:21,300 Ek nodig het om diegene wat deur afskakel hardloop klang hand hierdie tyd. 304 00:13:21,300 --> 00:13:22,140 So string asseblief. 305 00:13:22,140 --> 00:13:25,560 Ek gaan om voort te gaan en tik my gunsteling hello world. 306 00:13:25,560 --> 00:13:26,490 OK, null. 307 00:13:26,490 --> 00:13:27,700 Dit is nie wat ek getik het. 308 00:13:27,700 --> 00:13:29,690 So dit is 'n aanduiding van iets verkeerd. 309 00:13:29,690 --> 00:13:33,920 Laat my gaan voort en tik in 'n baie lang tou. 310 00:13:33,920 --> 00:13:37,210 Dankie vir die nul en ek weet nie as ek gaan in staat wees om dit te crash. 311 00:13:37,210 --> 00:13:40,240 Kom ons probeer 'n bietjie kopie plak en kyk of dit help. 312 00:13:40,240 --> 00:13:43,290 Plak net 'n baie van hierdie. 313 00:13:43,290 --> 00:13:47,310 Dit is beslis 'n groter string as gewoonlik. 314 00:13:47,310 --> 00:13:51,450 Laat ons net regtig skryf dit. 315 00:13:51,450 --> 00:13:51,950 Geen. 316 00:13:51,950 --> 00:13:52,650 Vervloek Dit. 317 00:13:52,650 --> 00:13:53,480 Beveel nie gevind nie. 318 00:13:53,480 --> 00:13:54,550 So dit is nie verband hou. 319 00:13:54,550 --> 00:13:56,440 Dit is omdat ek geplak 'n paar slegte karakters, 320 00:13:56,440 --> 00:13:59,780 maar dit blyk nie gaan om te werk. 321 00:13:59,780 --> 00:14:03,510 >> Kom ons probeer hierdie keer meer nie, want dit is meer pret as ons eintlik crash dit. 322 00:14:03,510 --> 00:14:09,116 Kom ons hierdie tipe en nou, ek is gaan 'n baie lang string kopieer 323 00:14:09,116 --> 00:14:10,990 En nou, laat ons kyk of ons kan hierdie ding crash. 324 00:14:10,990 --> 00:14:14,235 Sien ek uitgelaat ruimtes en nuwe lyne en kommapunte 325 00:14:14,235 --> 00:14:16,035 en al funky karakters. 326 00:14:16,035 --> 00:14:16,535 Betree. 327 00:14:16,535 --> 00:14:21,090 328 00:14:21,090 --> 00:14:22,880 En nou het die netwerk is net wat stadig. 329 00:14:22,880 --> 00:14:27,460 Ek hou af Command-V te lank, duidelik. 330 00:14:27,460 --> 00:14:28,190 Vervloek Dit! 331 00:14:28,190 --> 00:14:29,260 Beveel nie gevind nie. 332 00:14:29,260 --> 00:14:29,780 >> OK. 333 00:14:29,780 --> 00:14:32,240 Wel, die punt is nietemin die volgende. 334 00:14:32,240 --> 00:14:36,910 So, wat is eintlik gaan met hierdie verklaring 335 00:14:36,910 --> 00:14:39,240 van char star buffer op die lyn 16? 336 00:14:39,240 --> 00:14:41,820 So, wat kry ek wanneer Ek verklaar 'n wyser? 337 00:14:41,820 --> 00:14:47,440 Al wat ek kry is 'n vier byte waarde genoem buffer, maar wat is binnekant van dit 338 00:14:47,440 --> 00:14:49,540 op die oomblik? 339 00:14:49,540 --> 00:14:50,930 Dit is net 'n paar vullis waarde. 340 00:14:50,930 --> 00:14:54,170 Omdat enige tyd wat jy verklaar 'n veranderlike in C, dit is net 'n paar vullis waarde 341 00:14:54,170 --> 00:14:56,220 en ons is besig om te reis oor hierdie werklikheid. 342 00:14:56,220 --> 00:14:59,720 Nou, wanneer ek sê scanf, na hierdie adres 343 00:14:59,720 --> 00:15:01,520 en sit ongeag die gebruiker in. 344 00:15:01,520 --> 00:15:06,400 As die gebruiker in hallo wêreld, wel, waar kan ek dit? 345 00:15:06,400 --> 00:15:07,750 Buffer is 'n gemors waarde. 346 00:15:07,750 --> 00:15:11,510 >> So dit is soort van soos 'n pyl dit is wys wie weet waar. 347 00:15:11,510 --> 00:15:13,880 Miskien is dit wys hier in my geheue. 348 00:15:13,880 --> 00:15:16,560 En so wanneer die gebruiker tipes in hello world, 349 00:15:16,560 --> 00:15:22,380 die program probeer om die plaas string hello world backslash 0 350 00:15:22,380 --> 00:15:23,910 in daardie deel van die geheue. 351 00:15:23,910 --> 00:15:27,070 Maar met 'n hoë waarskynlikheid, maar duidelik nie 100% waarskynlikheid, 352 00:15:27,070 --> 00:15:30,440 die rekenaar gaan dan crash die program, want dit is nie 353 00:15:30,440 --> 00:15:32,490 geheue Ek moet toegelaat word om aan te raak. 354 00:15:32,490 --> 00:15:36,330 So in kort, hierdie program is gebrekkig vir presies daardie rede. 355 00:15:36,330 --> 00:15:38,070 Ek is fundamenteel nie wat doen? 356 00:15:38,070 --> 00:15:42,366 Watter stappe het Ek weggelaat, net soos ons weggelaat met die eerste voorbeeld Binky se? 357 00:15:42,366 --> 00:15:42,866 Ja? 358 00:15:42,866 --> 00:15:43,710 >> GEHOOR: toekenning Memory? 359 00:15:43,710 --> 00:15:45,001 >> David Malan: toekenning Memory. 360 00:15:45,001 --> 00:15:48,400 Ek het nie eintlik toegeken 'n geheue vir daardie string. 361 00:15:48,400 --> 00:15:50,270 So kan ons dit regmaak in 'n paar van die maniere. 362 00:15:50,270 --> 00:15:52,700 Een, kan ons dit eenvoudig te hou en in die feit, nou is jy 363 00:15:52,700 --> 00:15:55,116 gaan om te begin om 'n vervaging sien van die lyne tussen wat 364 00:15:55,116 --> 00:15:58,520 'n skikking is, wat 'n string is, wat 'n char ster is, wat 'n verskeidenheid van karakters 365 00:15:58,520 --> 00:15:59,020 is. 366 00:15:59,020 --> 00:16:02,450 Hier is 'n tweede voorbeeld waarby snare en kennis 367 00:16:02,450 --> 00:16:05,690 al wat ek gedoen het op die lyn 16 is, in plaas van sê 368 00:16:05,690 --> 00:16:09,530 dat buffer gaan 'n kar wees star, 'n verwysing na 'n stuk van die geheue, 369 00:16:09,530 --> 00:16:14,057 Ek gaan baie proaktief te gee myself 'n buffer vir 16 karakters, 370 00:16:14,057 --> 00:16:16,390 en in die feit, as jy vertroud is met die term buffer, 371 00:16:16,390 --> 00:16:20,570 waarskynlik van die wêreld van die video's, waar 'n video is buffering, buffering, 372 00:16:20,570 --> 00:16:21,175 buffer. 373 00:16:21,175 --> 00:16:22,550 Wel, wat is hier die verband? 374 00:16:22,550 --> 00:16:24,960 Wel, Binne YouTube en binnekant van die video spelers 375 00:16:24,960 --> 00:16:27,200 algemeen is 'n skikking dit is groter as 16. 376 00:16:27,200 --> 00:16:30,340 Dit mag dalk 'n verskeidenheid van grootte een megabyte, miskien 10 megagrepe, 377 00:16:30,340 --> 00:16:34,330 en in daardie reeks nie jou browser laai 'n hele klomp van grepe, 378 00:16:34,330 --> 00:16:37,500 'n hele klomp van die MB video, en die video-speler, 379 00:16:37,500 --> 00:16:40,930 YouTube se of wie se begin lees van die grepe uit die skikking, 380 00:16:40,930 --> 00:16:43,530 en enige tyd wat jy sien die woord buffering, buffering, 381 00:16:43,530 --> 00:16:46,350 dit beteken dat die speler het gekry om die einde van die skikking. 382 00:16:46,350 --> 00:16:50,430 Die netwerk is so stadig dat dit nie hervul die skikking met meer grepe 383 00:16:50,430 --> 00:16:55,610 en so is jy uit stukkies te vertoon aan die gebruiker. 384 00:16:55,610 --> 00:16:59,430 >> So buffer is 'n gepaste term hier in daardie dit is net 'n skikking, 'n stuk van die geheue. 385 00:16:59,430 --> 00:17:02,530 En dit sal dit regmaak omdat dit blyk 386 00:17:02,530 --> 00:17:07,410 dat jy skikkings kan hanteer asof hulle adresse, selfs al buffer 387 00:17:07,410 --> 00:17:10,710 is net 'n simbool, dit is 'n volgorde van die karakters, buffer, 388 00:17:10,710 --> 00:17:14,760 dit is nuttig vir my, die programmeerder, jy kan sy naam om te slaag 389 00:17:14,760 --> 00:17:17,079 asof dit 'n wyser, asof dit 390 00:17:17,079 --> 00:17:21,000 was die adres van 'n stuk van die geheue vir 16 karakters. 391 00:17:21,000 --> 00:17:24,530 So dit is om te sê, ek kan slaag die scanf presies wat die woord 392 00:17:24,530 --> 00:17:30,670 en so nou, as ek hierdie program, maak scanf 2, dot streep scanf 2, 393 00:17:30,670 --> 00:17:35,386 en tik in hello world, Gee dat time-- 394 00:17:35,386 --> 00:17:37,590 >> Hmm, wat gebeur? 395 00:17:37,590 --> 00:17:39,340 String asseblief. 396 00:17:39,340 --> 00:17:41,430 Wat het ek verkeerd gedoen? 397 00:17:41,430 --> 00:17:43,800 Hello world, buffer. 398 00:17:43,800 --> 00:17:44,705 Hello Wêreld. 399 00:17:44,705 --> 00:17:48,201 400 00:17:48,201 --> 00:17:49,420 Ag, ek weet wat dit doen. 401 00:17:49,420 --> 00:17:49,920 OK. 402 00:17:49,920 --> 00:17:51,628 So is dit te lees totdat die eerste ruimte. 403 00:17:51,628 --> 00:17:55,680 So laat kul net vir 'n oomblik en sê ek wou net om iets te tik 404 00:17:55,680 --> 00:18:01,408 baie lang soos hierdie is 'n lang vonnis dit is een, twee, drie, vier, vyf, 405 00:18:01,408 --> 00:18:04,420 ses, sewe, agt, nege, 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 Dit is inderdaad 'n lang sin. 408 00:18:07,600 --> 00:18:10,710 So hierdie sin is langer as 16 karakters 409 00:18:10,710 --> 00:18:13,670 en so toe ek druk Enter, wat gaan gebeur? 410 00:18:13,670 --> 00:18:16,940 Wel, in hierdie geval van die storie, het ek verklaar buffer 411 00:18:16,940 --> 00:18:22,190 om eintlik 'n verskeidenheid met 16 karakters gereed om te gaan. 412 00:18:22,190 --> 00:18:27,426 So een, twee, drie, vier, vyf, ses, sewe, agt, nege, 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 So 16 karakters, en nou, toe ek lees iets soos hierdie is 'n lang 415 00:18:34,410 --> 00:18:43,950 vonnis, wat gaan gebeur is ek gaan om te lees in hierdie is 'n lang 416 00:18:43,950 --> 00:18:49,660 S-E-N-T-E-N-C-E, sin. 417 00:18:49,660 --> 00:18:52,270 >> So dit is doelbewus 'n slegte ding wat ek 418 00:18:52,270 --> 00:18:55,060 hou skryf buite die grense van my skikking, 419 00:18:55,060 --> 00:18:56,660 buite die grense van my buffer. 420 00:18:56,660 --> 00:19:00,100 Ek kon kry gelukkig en die program sal aanhou loop en nie om nie, 421 00:19:00,100 --> 00:19:03,450 maar oor die algemeen, hierdie sal inderdaad my program crash, 422 00:19:03,450 --> 00:19:06,440 en dit is 'n fout in my Code Die oomblik toe ek stap 423 00:19:06,440 --> 00:19:08,576 buite die grense van daardie skikking, want ek 424 00:19:08,576 --> 00:19:10,450 weet nie of dit is noodwendig gaan crash 425 00:19:10,450 --> 00:19:12,120 of as ek net gaan om gelukkig te kry. 426 00:19:12,120 --> 00:19:15,750 So dit is problematies, want in hierdie geval, lyk dit vir werk 427 00:19:15,750 --> 00:19:20,931 en laat ons versoek lot hier, selfs al die IDE lyk nogal 'n bietjie duld 428 00:19:20,931 --> 00:19:21,430 of-- 429 00:19:21,430 --> 00:19:22,040 >> Daar gaan ons. 430 00:19:22,040 --> 00:19:23,240 Ten slotte. 431 00:19:23,240 --> 00:19:26,470 So ek is die enigste een wat dit kan sien nie. 432 00:19:26,470 --> 00:19:29,630 So ek het net 'n baie pret tik 'n baie lang werklike frase 433 00:19:29,630 --> 00:19:32,800 dat dit beslis oorskry 16 grepe, want ek 434 00:19:32,800 --> 00:19:38,050 getik in hierdie mal lang multi-line frase, en dan sien wat daar gebeur het. 435 00:19:38,050 --> 00:19:41,110 Die program het probeer om dit te druk en het daarna 'n segmentering skuld 436 00:19:41,110 --> 00:19:44,430 en segmentering foute is wanneer iets soos dit gebeur 437 00:19:44,430 --> 00:19:47,650 en die bedryfstelsel sê nee, kan dit nie geheue raak. 438 00:19:47,650 --> 00:19:49,570 Ons gaan doodmaak die program heeltemal. 439 00:19:49,570 --> 00:19:51,180 >> So dit lyk problematies. 440 00:19:51,180 --> 00:19:54,540 Ek het die program waarvolgens verbeter ten minste 'n paar geheue, 441 00:19:54,540 --> 00:19:58,000 maar dit wil voorkom asof beperk die funksie GetString te kry 442 00:19:58,000 --> 00:20:00,780 snare van 'n paar beperkte lengte 16. 443 00:20:00,780 --> 00:20:04,200 So as jy wil om langer te ondersteun sinne as 16 karakters, 444 00:20:04,200 --> 00:20:04,880 wat doen jy? 445 00:20:04,880 --> 00:20:07,970 Wel, jy kan verhoog die grootte van die buffer 32 446 00:20:07,970 --> 00:20:09,190 of wat lyk soort van kort. 447 00:20:09,190 --> 00:20:12,260 Hoekom het ons nie net maak dit 1000, maar stoot terug. 448 00:20:12,260 --> 00:20:17,100 Wat is die reaksie van intuïtief net hierdie probleem te vermy deur 449 00:20:17,100 --> 00:20:20,660 my buffer groter, soos 1000 karakters? 450 00:20:20,660 --> 00:20:23,470 Deur die implementering van GetString hierdie manier. 451 00:20:23,470 --> 00:20:27,130 Wat is goed of sleg hier? 452 00:20:27,130 --> 00:20:28,033 Ja? 453 00:20:28,033 --> 00:20:30,574 GEHOOR: As jy bind 'n baie van ruimte en jy dit nie gebruik nie, 454 00:20:30,574 --> 00:20:33,500 dan kan jy nie meer inzetten dat die ruimte. 455 00:20:33,500 --> 00:20:34,500 David Malan: Absoluut. 456 00:20:34,500 --> 00:20:38,480 Dit is verkwistende sover as jy dit nie doen nie werklik nodig 900 van die grepe 457 00:20:38,480 --> 00:20:41,057 en tog is jy vra vir 1000 in totaal in elk geval, 458 00:20:41,057 --> 00:20:44,140 jy net beslag meer geheue op die gebruiker se rekenaar as jy nodig het om, 459 00:20:44,140 --> 00:20:45,740 en na alles, 'n paar van jy reeds teëgekom 460 00:20:45,740 --> 00:20:47,620 in die lewe dat wanneer jy hardloop baie programme 461 00:20:47,620 --> 00:20:50,470 en hulle is op die eet van baie van die geheue, Dit kan eintlik prestasie impak 462 00:20:50,470 --> 00:20:52,220 en die gebruiker se ervaring op die rekenaar. 463 00:20:52,220 --> 00:20:56,090 So dit is soort van 'n lui oplossing vir seker, en omgekeerd, 464 00:20:56,090 --> 00:21:00,140 dit is nie net verkwistende, wat die probleem nog steeds, selfs as ek my 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 >> GEHOOR: Die string is lengte 1001. 468 00:21:04,475 --> 00:21:05,350 David Malan: Presies. 469 00:21:05,350 --> 00:21:08,280 As jou string is lengte 1001, jy presies dieselfde probleem, 470 00:21:08,280 --> 00:21:10,705 en deur my argument, sou ek net maak dit 2000 dan 471 00:21:10,705 --> 00:21:12,830 maar jy weet nie in bevorder hoe groot dit moet wees, 472 00:21:12,830 --> 00:21:16,890 en tog, ek het nie my program saamstel voordat laat mense gebruik en aflaai 473 00:21:16,890 --> 00:21:17,390 Dit. 474 00:21:17,390 --> 00:21:21,490 So dit is presies die soort van dinge wat die CS50 biblioteek drieë 475 00:21:21,490 --> 00:21:24,750 om ons te help met ons sal net oogopslag op sommige van die onderliggende implementering 476 00:21:24,750 --> 00:21:29,790 hier, maar dit is CS50 dot C. Dit is die lêer wat al op CS50 IDE 477 00:21:29,790 --> 00:21:31,420 al hierdie weke dat jy het al met behulp. 478 00:21:31,420 --> 00:21:34,280 Dit is pre-saamgestel en jy het outomaties gebruik dit 479 00:21:34,280 --> 00:21:38,780 uit die aard van die wat stamp L CS50 vlag met klang, 480 00:21:38,780 --> 00:21:42,300 maar as ek rol af deur al hierdie funksies, hier is GetString, 481 00:21:42,300 --> 00:21:44,636 en net om jou 'n gee smaak van wat aangaan, 482 00:21:44,636 --> 00:21:46,760 Kom ons neem 'n vinnige blik op die relatiewe kompleksiteit. 483 00:21:46,760 --> 00:21:48,870 Dit is nie 'n super lang funksie, maar ons het nie 484 00:21:48,870 --> 00:21:52,530 het al hard oor te dink hoe om te gaan oor die manier waarop snare. 485 00:21:52,530 --> 00:21:55,660 >> So hier is my buffer en ek blykbaar inisialiseer dit null. 486 00:21:55,660 --> 00:21:57,990 Dit, natuurlik, is die dieselfde as char ster 487 00:21:57,990 --> 00:22:00,585 maar ek het besluit in die implementering van die CS50 biblioteek 488 00:22:00,585 --> 00:22:02,460 dat as ons gaan heeltemal dinamiese, 489 00:22:02,460 --> 00:22:05,770 Ek weet nie vooraf hoe groot van 'n string gebruikers gaan wil te kry. 490 00:22:05,770 --> 00:22:08,140 So ek gaan om te begin met net 'n leë string 491 00:22:08,140 --> 00:22:11,507 en ek gaan om te bou aan soveel geheue as ek nodig het om die gebruiker string pas 492 00:22:11,507 --> 00:22:13,340 en as ek het nie genoeg nie, ek gaan om te vra 493 00:22:13,340 --> 00:22:15,010 die bedryfstelsel vir meer geheue. 494 00:22:15,010 --> 00:22:17,510 Ek gaan om hul string beweeg in 'n groter deel van die geheue 495 00:22:17,510 --> 00:22:21,847 en ek gaan om vry te stel of te bevry die onvoldoende groot deel van die geheue 496 00:22:21,847 --> 00:22:23,680 en ons is maar net gaan hierdie iteratief te doen. 497 00:22:23,680 --> 00:22:25,570 >> So 'n vinnige blik, hier is net 'n veranderlike 498 00:22:25,570 --> 00:22:28,780 waarmee ek gaan om tred te hou van die kapasiteit van my buffer. 499 00:22:28,780 --> 00:22:30,071 Hoeveel grepe kan ek inpas? 500 00:22:30,071 --> 00:22:32,070 Hier is 'n veranderlike N met wat ek gaan hou 501 00:22:32,070 --> 00:22:36,200 hou van hoeveel bytes is eintlik in die buffer of dat die gebruiker getik het. 502 00:22:36,200 --> 00:22:39,900 As jy nie hierdie gesien het nie, moet jy kan spesifiseer dat 'n veranderlike soos 'n int 503 00:22:39,900 --> 00:22:46,370 is unsigned, wat soos die naam aandui, beteken dit is nie-negatief is, en hoekom sou 504 00:22:46,370 --> 00:22:50,590 Ek ooit wil spesifiseer pla dat 'n int is nie net 'n int, 505 00:22:50,590 --> 00:22:52,540 maar dit is 'n ongetekende int? 506 00:22:52,540 --> 00:22:55,064 Dit is 'n nie-negatiewe int. 507 00:22:55,064 --> 00:22:56,355 Wat beteken die [onhoorbaar] beteken? 508 00:22:56,355 --> 00:22:58,910 >> GEHOOR: Dit is die beskrywing van 'n bedrag geheue wat kan wees [onhoorbaar]. 509 00:22:58,910 --> 00:22:59,660 >> David Malan: Ja. 510 00:22:59,660 --> 00:23:03,710 So as ek sê unsigned, dit is eintlik gee jou 'n bietjie ekstra geheue 511 00:23:03,710 --> 00:23:07,440 en dit lyk soort van dom, maar as jy het 'n bietjie van 'n addisionele geheue, wat 512 00:23:07,440 --> 00:23:09,940 beteken dat jy twee keer soveel waardes wat jy kan verteenwoordig, 513 00:23:09,940 --> 00:23:11,570 want dit kan 'n 0 of 'n 1. 514 00:23:11,570 --> 00:23:14,660 So by verstek, kan 'n int rofweg negatiewe 2000000000 al die pad 515 00:23:14,660 --> 00:23:16,030 tot positiewe 2000000000. 516 00:23:16,030 --> 00:23:18,540 Dit is 'n groot reekse, maar dit is nog steeds soort van verkwistende 517 00:23:18,540 --> 00:23:21,280 as jy net omgee groottes, wat net intuïtief 518 00:23:21,280 --> 00:23:24,620 moet nie-negatief wees of positief of 0, goed dan, 519 00:23:24,620 --> 00:23:28,884 hoekom is jy mors 2000000000 moontlike waardes vir negatiewe getalle 520 00:23:28,884 --> 00:23:30,300 As jy nog nooit gaan om dit te gebruik? 521 00:23:30,300 --> 00:23:35,350 So sê unsigned, nou is my int kan tussen 0 en ongeveer 4 miljard. 522 00:23:35,350 --> 00:23:39,280 >> So hier is net 'n int C vir redes ons sal nie nou net as kry in 523 00:23:39,280 --> 00:23:42,280 waarom dit is 'n int plaas van 'n kar nie, maar hier is 524 00:23:42,280 --> 00:23:44,630 die kern van wat aangaan op, en 'n paar van julle 525 00:23:44,630 --> 00:23:48,340 kan word met behulp van, byvoorbeeld, die fgetc funksie selfs in PSet vier 526 00:23:48,340 --> 00:23:51,580 of daarna, sal ons dit sien weer in die probleem stel vyf 527 00:23:51,580 --> 00:23:55,410 fgetc is lekker, want soos die naam soort, soort van arcanely aandui, 528 00:23:55,410 --> 00:23:57,940 dit is 'n funksie wat kry 'n karakter en so, 529 00:23:57,940 --> 00:24:00,690 wat is fundamenteel verskil oor wat ons doen in GetString 530 00:24:00,690 --> 00:24:03,110 is ons nie die gebruik van scanf op dieselfde manier. 531 00:24:03,110 --> 00:24:07,550 Ons is net kruip saam stap-vir-stap oor alles wat die gebruiker getik in, 532 00:24:07,550 --> 00:24:10,970 want ons kan altyd Ken EEN char, en so kan ons altyd veilig 533 00:24:10,970 --> 00:24:15,599 kyk na een kar op 'n tyd, en die magie begin hier gebeur nie. 534 00:24:15,599 --> 00:24:17,890 Ek gaan om af te gaan na die middel van hierdie funksie 535 00:24:17,890 --> 00:24:20,360 net kortliks hierdie funksie. 536 00:24:20,360 --> 00:24:22,670 Baie soos daar is 'n malloc funksie, daar is 537 00:24:22,670 --> 00:24:27,740 'n realloc funksie waar realloc Kom jy 'n stuk van die geheue hertoeken 538 00:24:27,740 --> 00:24:29,570 en maak dit groter of kleiner. 539 00:24:29,570 --> 00:24:33,060 So lang storie kort en met 'n golf van my hand vir vandag, 540 00:24:33,060 --> 00:24:35,620 weet dat wat GetString doen, is dit soort 541 00:24:35,620 --> 00:24:39,720 van mettertyd groei of krimp die buffer van die gebruiker 542 00:24:39,720 --> 00:24:41,440 tipes in sy of haar string. 543 00:24:41,440 --> 00:24:43,962 >> So as die gebruiker 'n kort string, hierdie kode 544 00:24:43,962 --> 00:24:45,920 net genoeg ken geheue om die string te pas. 545 00:24:45,920 --> 00:24:48,086 As die gebruiker hou tik soos ek gedoen het dit weer en weer 546 00:24:48,086 --> 00:24:50,330 en weer, goed, indien die buffer se aanvanklik hierdie groot 547 00:24:50,330 --> 00:24:53,310 en die program besef, om wag 'n minuut, ek is uit die ruimte, 548 00:24:53,310 --> 00:24:55,410 dit gaan verdubbel die grootte van die buffer 549 00:24:55,410 --> 00:24:59,110 en dan dubbel die grootte van die buffer en die kode wat die verdubbeling doen, 550 00:24:59,110 --> 00:25:03,170 As ons kyk na dit hier, dis Net hierdie slim one-liner. 551 00:25:03,170 --> 00:25:06,830 Jy kan nie hierdie sintaksis gesien voor, maar as jy sê star gelykes, 552 00:25:06,830 --> 00:25:10,470 dit is dieselfde ding as sê kapasiteit keer 2. 553 00:25:10,470 --> 00:25:13,390 So dit hou net verdubbel die kapasiteit van die buffer 554 00:25:13,390 --> 00:25:17,480 en dan vertel realloc te gee self wat veel meer geheue. 555 00:25:17,480 --> 00:25:19,720 >> Nou, as 'n eenkant, is daar ander funksies in hier 556 00:25:19,720 --> 00:25:23,680 dat ons nie sal kyk na enige detail anders as om te wys in GetInt, 557 00:25:23,680 --> 00:25:26,150 ons gebruik GetString in GetInt. 558 00:25:26,150 --> 00:25:28,192 Ons maak seker dat dit nie null, wat, onthou, 559 00:25:28,192 --> 00:25:30,400 is die spesiale waarde wat beteken iets verkeerd geloop het. 560 00:25:30,400 --> 00:25:31,233 Ons is uit die geheue. 561 00:25:31,233 --> 00:25:32,310 Beter check vir daardie. 562 00:25:32,310 --> 00:25:33,710 En ons terugkeer 'n brandwag waarde. 563 00:25:33,710 --> 00:25:37,850 Maar ek sal stel om die kommentaar te waarom en dan gebruik ons ​​hierdie neef van scanf 564 00:25:37,850 --> 00:25:42,100 genoem sscanf en dit blyk dat sscanf, of string scanf, 565 00:25:42,100 --> 00:25:45,310 Kom jy 'n blik op die lyn te neem dat die gebruiker in getik het en jou laat 566 00:25:45,310 --> 00:25:49,610 ontleed dit in wese en wat ek is doen hier Ek sê sscanf, 567 00:25:49,610 --> 00:25:54,440 ontleed ongeag die gebruiker getik in en maak seker% i, 568 00:25:54,440 --> 00:25:59,250 daar is 'n heelgetal in dit, en ons sal nie kry in vandag presies die rede waarom daar is ook 569 00:25:59,250 --> 00:26:03,760 'n% c hier nie, maar dat in 'n neutedop laat ons op te spoor indien die gebruiker getik 570 00:26:03,760 --> 00:26:06,050 iets valse na die nommer. 571 00:26:06,050 --> 00:26:11,766 So die rede dat GetInt en GetString jou vertel om weer te probeer, weer probeer, probeer weer 572 00:26:11,766 --> 00:26:13,640 is as gevolg van al wat die kode wat ons geskryf het, 573 00:26:13,640 --> 00:26:17,900 Dit is soort van kyk na die invoer van die gebruiker se om seker te maak dit is heeltemal numeriese 574 00:26:17,900 --> 00:26:21,700 of dit is 'n werklike swaai punt waarde of die wil, 575 00:26:21,700 --> 00:26:24,233 afhangende van watter waarde funksioneer wat jy gebruik. 576 00:26:24,233 --> 00:26:25,060 >> Sjoe. 577 00:26:25,060 --> 00:26:25,710 OK. 578 00:26:25,710 --> 00:26:27,592 Dit was 'n mondvol maar die punt hier is 579 00:26:27,592 --> 00:26:29,550 dat die rede waarom ons moes diegene opleiding wiele op 580 00:26:29,550 --> 00:26:32,880 is omdat op die laagste vlak, daar is net so baie dinge wat 581 00:26:32,880 --> 00:26:35,674 kan verkeerd gaan dat ons wou om preemptively hanteer 582 00:26:35,674 --> 00:26:38,090 daardie dinge beslis in die vroegste weke van die klas, 583 00:26:38,090 --> 00:26:42,230 maar nou met PSet vier en vyf en PSet buite sal jy sien dat dit is meer aan 584 00:26:42,230 --> 00:26:45,570 jy maar ook jy meer in staat van die oplossing van die soort probleme 585 00:26:45,570 --> 00:26:47,180 jouself. 586 00:26:47,180 --> 00:26:51,770 Enige vrae oor GetString of GetInt? 587 00:26:51,770 --> 00:26:52,630 Ja? 588 00:26:52,630 --> 00:26:55,130 >> GEHOOR: Hoekom sou jy dubbel die kapasiteit van die buffer 589 00:26:55,130 --> 00:26:57,630 eerder as om net te verhoog dit deur die presiese bedrag? 590 00:26:57,630 --> 00:26:58,100 >> David Malan: Goeie vraag. 591 00:26:58,100 --> 00:27:00,474 Hoekom sal ons dubbel die kapasiteit van die buffer in teenstelling 592 00:27:00,474 --> 00:27:02,800 net om dit te verhoog deur sommige konstante waarde? 593 00:27:02,800 --> 00:27:03,900 Dit was 'n ontwerp besluit. 594 00:27:03,900 --> 00:27:08,590 Ons het net besluit dat omdat dit geneig is om wees 'n bietjie duur time-wyse te vra 595 00:27:08,590 --> 00:27:10,440 die bedryfstelsel vir die geheue, het ons nie 596 00:27:10,440 --> 00:27:13,210 wil eindig om in 'n situasie vir die groot snare 597 00:27:13,210 --> 00:27:14,960 dat ons vra weer en weer die OS 598 00:27:14,960 --> 00:27:17,500 en weer en weer in vinnige opvolging vir die geheue. 599 00:27:17,500 --> 00:27:20,387 So het ons net besluit, ietwat arbitrêr maar ons hoop redelik, 600 00:27:20,387 --> 00:27:22,720 dat jy weet wat, laat ons probeer om onsself voor te kry 601 00:27:22,720 --> 00:27:25,520 en hou net verdubbel dit so dat ons die bedrag van die tye te verminder 602 00:27:25,520 --> 00:27:29,010 ons moet malloc bel of realloc, maar 'n totale oordeel 603 00:27:29,010 --> 00:27:31,820 noem in die afwesigheid van die wete wat gebruikers dalk wil om te tik in. 604 00:27:31,820 --> 00:27:33,600 Beide maniere kan wees onseker. 605 00:27:33,600 --> 00:27:35,430 Waarskynlik goed. 606 00:27:35,430 --> 00:27:39,240 >> So laat ons neem 'n blik op 'n paar ander newe-effekte van die geheue, 607 00:27:39,240 --> 00:27:41,610 dinge wat verkeerd kan gaan en gereedskap wat jy kan 608 00:27:41,610 --> 00:27:43,880 gebruik om hierdie soort van foute te vang. 609 00:27:43,880 --> 00:27:47,800 Dit blyk uit almal van julle, selfs al check50 het nie gesê jy soveel, 610 00:27:47,800 --> 00:27:50,050 is skryf karretjie kode sedert week een, 611 00:27:50,050 --> 00:27:53,630 selfs al check50 toetse geslaag het, en selfs as jy en jou TF 612 00:27:53,630 --> 00:27:56,010 super vol vertroue dat jou kode werk soos bedoel. 613 00:27:56,010 --> 00:27:59,190 Jou kode karretjie is of gebrekkig dat julle almal, 614 00:27:59,190 --> 00:28:02,540 in die gebruik van die CS50 biblioteek, is lekkende geheue. 615 00:28:02,540 --> 00:28:06,040 Jy het gevra die bedryfstelsel vir die geheue in die meeste van die programme 616 00:28:06,040 --> 00:28:08,850 jy geskryf het, maar jy het nooit werklik gegee dit terug. 617 00:28:08,850 --> 00:28:12,110 Jy het GetString genoem en GetInt en GetFloat, 618 00:28:12,110 --> 00:28:15,270 maar met GetString, jy het nooit unGetString of Gee genoem 619 00:28:15,270 --> 00:28:19,890 String Terug of die wil, maar ons het gesien dat GetString bewillig geheue 620 00:28:19,890 --> 00:28:22,810 by wyse van malloc of hierdie funksie realloc, wat net 621 00:28:22,810 --> 00:28:25,670 baie soortgelyk in die gees, en tog, ons het nie 622 00:28:25,670 --> 00:28:28,629 vra die bedryfstelsel vir geheue en geheue weer en weer 623 00:28:28,629 --> 00:28:29,670 maar nooit gee dit terug. 624 00:28:29,670 --> 00:28:33,550 >> Nou, as 'n eenkant, dit blyk dat wanneer 'n program verlaat, al die geheue 625 00:28:33,550 --> 00:28:34,870 outomaties bevry. 626 00:28:34,870 --> 00:28:36,150 So dit is nie 'n groot deal nie. 627 00:28:36,150 --> 00:28:38,590 Dit gaan nie om die breek IDE of stadige dinge af, 628 00:28:38,590 --> 00:28:40,670 maar wanneer programme te doen algemeen lek geheue 629 00:28:40,670 --> 00:28:42,170 en hulle is hardloop vir 'n lang tyd. 630 00:28:42,170 --> 00:28:45,640 As jy nog ooit gesien het die dom bietjie strand bal in Mac OS of die uurglas 631 00:28:45,640 --> 00:28:51,160 op Windows waar dit is soort van stadiger of dink of denke 632 00:28:51,160 --> 00:28:53,770 of net regtig begin te stadig om 'n crawl, 633 00:28:53,770 --> 00:28:56,960 dit baie moontlik kan wees die gevolg van 'n geheue lek. 634 00:28:56,960 --> 00:28:59,970 Die programmeerders wat geskryf het die sagteware wat jy gebruik 635 00:28:59,970 --> 00:29:03,570 vra die bedryfstelsel vir geheue elke paar minute, elke uur. 636 00:29:03,570 --> 00:29:05,570 Maar as jy die bestuur van die sagteware, selfs al is dit 637 00:29:05,570 --> 00:29:08,680 geminimaliseer in jou rekenaar vir ure of dae op die einde, 638 00:29:08,680 --> 00:29:11,980 jy kan vra vir meer en meer geheue en nooit eintlik gebruik dit 639 00:29:11,980 --> 00:29:15,180 en so jou kode kan wees, of programme kan lek geheue, 640 00:29:15,180 --> 00:29:18,350 en as jy begin om geheue lek, is daar minder geheue vir ander programme, 641 00:29:18,350 --> 00:29:21,220 en die effek is om stadig alles neer. 642 00:29:21,220 --> 00:29:23,600 >> Nou, dit is by verre een van die mees gruwelike programme 643 00:29:23,600 --> 00:29:26,350 sal jy geleenthede uit te voer in CS50 sover 644 00:29:26,350 --> 00:29:31,650 as sy produksie is selfs meer esoteriese as klang of maak of enige van die opdrag 645 00:29:31,650 --> 00:29:35,930 line programme ons reeds hardloop, maar Gelukkig, ingebed in sy produksie 646 00:29:35,930 --> 00:29:39,810 is 'n paar super nuttige wenke wat sal nuttig óf vir PSet vier wees 647 00:29:39,810 --> 00:29:41,510 of beslis PSet vyf. 648 00:29:41,510 --> 00:29:44,250 So valgrind is 'n instrument wat gebruik kan word om te kyk 649 00:29:44,250 --> 00:29:46,930 vir die geheue lekkasies in jou program. 650 00:29:46,930 --> 00:29:48,570 Dit is relatief maklik om te hardloop. 651 00:29:48,570 --> 00:29:51,420 Jy hardloop valgrind en dan, selfs al is dit 'n bietjie verbose, 652 00:29:51,420 --> 00:29:54,440 Dash Dash lek tjek gelyk vol, en dan dot 653 00:29:54,440 --> 00:29:56,320 streep en die naam van jou program. 654 00:29:56,320 --> 00:30:00,010 So valgrind sal dan jou program loop en aan die einde van jou program 655 00:30:00,010 --> 00:30:02,240 hardloop voordat dit gesluit en gee jou nog n vinnige, 656 00:30:02,240 --> 00:30:04,980 dit gaan om te analiseer jou program, terwyl dit loop 657 00:30:04,980 --> 00:30:07,740 en vertel het jy lek 'n geheue en nog beter, 658 00:30:07,740 --> 00:30:10,610 het jy die geheue raak wat nie aan jou behoort? 659 00:30:10,610 --> 00:30:13,700 Dit kan nie alles vang, maar dit is redelik goed op te vang die meeste dinge. 660 00:30:13,700 --> 00:30:19,700 >> So hier is 'n voorbeeld van my wat run hierdie program, met run valgrind, 661 00:30:19,700 --> 00:30:21,470 op 'n program genaamd geheue, en ek gaan 662 00:30:21,470 --> 00:30:24,730 om die lyne wat beklemtoon uiteindelik van belang is vir ons. 663 00:30:24,730 --> 00:30:27,690 So is daar nog meer afleiding dat ek van die skyfie het verwyder. 664 00:30:27,690 --> 00:30:30,930 Maar laat ons sien net wat hierdie program in staat is om ons te vertel. 665 00:30:30,930 --> 00:30:34,800 Dit is in staat om van ons te vertel dinge soos ongeldig skryf van grootte 4. 666 00:30:34,800 --> 00:30:38,020 Met ander woorde, as jy die geheue te raak, spesifiek 4 grepe van die geheue 667 00:30:38,020 --> 00:30:40,350 dat jy nie moet hê, valgrind kan jou vertel dat. 668 00:30:40,350 --> 00:30:41,660 Ongeldig skryf van grootte 4. 669 00:30:41,660 --> 00:30:43,640 Jy aangeraak vier grepe dat jy nie moet hê. 670 00:30:43,640 --> 00:30:44,840 Waar het jy dit doen? 671 00:30:44,840 --> 00:30:45,900 Dit is die skoonheid. 672 00:30:45,900 --> 00:30:50,000 Memory dot c lyn 21 is waar jy verfrommeld en dit is hoekom dit nuttig. 673 00:30:50,000 --> 00:30:53,410 Baie soos GDB, kan dit help wys jou by die werklike fout. 674 00:30:53,410 --> 00:30:57,170 >> Nou, hierdie een is 'n bietjie meer verbose, indien nie verwarrend. 675 00:30:57,170 --> 00:31:01,307 40 grepe in 1 blokke is beslis verlore in die verlies rekord 1 van 1. 676 00:31:01,307 --> 00:31:02,140 Wat beteken dit? 677 00:31:02,140 --> 00:31:05,920 Wel, dit beteken net jy gevra 40 grepe en jy nooit het dit terug. 678 00:31:05,920 --> 00:31:08,930 Jy genoem malloc of julle geroep GetString en die bedryfstelsel 679 00:31:08,930 --> 00:31:12,450 het jy 40 grepe, maar jy nooit bevry of vrygestel wat die geheue, 680 00:31:12,450 --> 00:31:15,400 en om eerlik te wees, het ons nooit wys hoe om terug te gee geheue. 681 00:31:15,400 --> 00:31:17,910 Blyk daar is 'n super eenvoudige funksie genoem gratis. 682 00:31:17,910 --> 00:31:21,170 Neem een ​​argument, die ding jy wil bevry of terug te gee, 683 00:31:21,170 --> 00:31:23,430 maar 40 grepe, blykbaar, in hierdie program 684 00:31:23,430 --> 00:31:27,300 verlore geraak het op reël 20 geheue dot c. 685 00:31:27,300 --> 00:31:28,650 >> So laat ons sien hierdie program. 686 00:31:28,650 --> 00:31:31,020 Dit is super nutteloos. 687 00:31:31,020 --> 00:31:33,980 Dit demonstreer net hierdie spesifieke fout. 688 00:31:33,980 --> 00:31:34,920 So laat ons neem 'n blik. 689 00:31:34,920 --> 00:31:39,920 Hier is die hoof en belangrikste, kennisgewing, oproepe 'n funksie genoem f en dan terugkeer. 690 00:31:39,920 --> 00:31:41,550 So nie al wat interessant. 691 00:31:41,550 --> 00:31:42,664 Wat beteken f doen? 692 00:31:42,664 --> 00:31:44,330 Sien ek het nie die moeite met 'n prototipe. 693 00:31:44,330 --> 00:31:46,520 Ek wou die kode hou as minimale as moontlik. 694 00:31:46,520 --> 00:31:49,530 So ek het f bo hoof- en dit is goed, seker, 695 00:31:49,530 --> 00:31:51,500 vir 'n kort programme soos hierdie. 696 00:31:51,500 --> 00:31:56,910 So f niks terug te keer en doen niks te neem nie, maar dit doen nie. 697 00:31:56,910 --> 00:31:59,620 Dit verklaar, baie soos in die Binky byvoorbeeld 698 00:31:59,620 --> 00:32:02,682 'n wyser genoem x wat gaan na die adres van 'n int stoor. 699 00:32:02,682 --> 00:32:03,890 So wat is die linkerkant. 700 00:32:03,890 --> 00:32:07,230 In Engels, wat is die regs doen? 701 00:32:07,230 --> 00:32:09,770 Iemand? 702 00:32:09,770 --> 00:32:13,665 Wat doen dit vir ons? 703 00:32:13,665 --> 00:32:14,651 Ja? 704 00:32:14,651 --> 00:32:16,623 >> GEHOOR: [onhoorbaar] keer die grootte van 'n int 705 00:32:16,623 --> 00:32:19,175 wat 10 keer [onhoorbaar] 706 00:32:19,175 --> 00:32:20,800 David Malan: Goeie en laat my op te som. 707 00:32:20,800 --> 00:32:25,480 So ken genoeg ruimte vir 10 heelgetalle of 10, wat is die grootte van 'n int, 708 00:32:25,480 --> 00:32:29,340 dit is vier grepe, so 10 keer 4 is 40 sodat regterkant dat ek 709 00:32:29,340 --> 00:32:33,930 gemerkte is gee my 40 grepe en stoor die adres van die eerste byte 710 00:32:33,930 --> 00:32:34,940 in x. 711 00:32:34,940 --> 00:32:38,380 En nou laastens, en hier is waar hierdie program is karretjie, wat is 712 00:32:38,380 --> 00:32:41,540 verkeerd met lyn 21 wat gebaseer is op daardie logika? 713 00:32:41,540 --> 00:32:45,197 714 00:32:45,197 --> 00:32:46,280 Wat is verkeerd met 'n lyn 21? 715 00:32:46,280 --> 00:32:46,780 Ja? 716 00:32:46,780 --> 00:32:49,550 GEHOOR: Jy kan nie indeks in x [onhoorbaar]. 717 00:32:49,550 --> 00:32:50,300 David Malan: Ja. 718 00:32:50,300 --> 00:32:52,270 Ek moet nie indeks in x soos dit. 719 00:32:52,270 --> 00:32:53,850 So sintakties, dit is OK. 720 00:32:53,850 --> 00:32:56,990 Wat is lekker is, baie soos jy kan die naam van 'n skikking te behandel 721 00:32:56,990 --> 00:33:01,080 asof dit 'n wyser, insgelyks kan jy 'n wyser te behandel asof dit 722 00:33:01,080 --> 00:33:06,425 'n skikking, en sodat ek kan sintakties sê x bracket iets x bracket i, 723 00:33:06,425 --> 00:33:07,800 maar die 10 is problematies. 724 00:33:07,800 --> 00:33:09,096 Hoekom? 725 00:33:09,096 --> 00:33:10,910 >> GEHOOR: Want dit is nie binne. 726 00:33:10,910 --> 00:33:12,390 >> David Malan: Dit is nie binne-in dat deel van die geheue. 727 00:33:12,390 --> 00:33:15,306 Wat is die grootste waarde wat ek moet word om in daardie vierkantige hakies? 728 00:33:15,306 --> 00:33:16,870 9, 0 tot 9. 729 00:33:16,870 --> 00:33:18,160 As gevolg van nul kruip. 730 00:33:18,160 --> 00:33:20,190 So 0 tot 9 sal goed wees. 731 00:33:20,190 --> 00:33:23,960 Bracket 10 is nie goed nie en maar onthou al is, elke keer 732 00:33:23,960 --> 00:33:27,017 Dit lyk asof ek probeer om CS50 IDE maak crash deur te tik in valse waardes, 733 00:33:27,017 --> 00:33:29,100 dit nie altyd saam, en inderdaad, jy dikwels 734 00:33:29,100 --> 00:33:31,460 kry gelukkig net omdat die bedryfstelsel nie 735 00:33:31,460 --> 00:33:35,467 sien dat jy ooit so iets slaag sommige stuk van die geheue, 736 00:33:35,467 --> 00:33:38,300 omdat jy gebly binne tegnies jou segment, maar meer oor dit 737 00:33:38,300 --> 00:33:40,940 in 'n bedryfstelsels klas, en so iets soos hierdie 738 00:33:40,940 --> 00:33:43,000 kon baie maklik gaan ongemerk. 739 00:33:43,000 --> 00:33:48,120 Jou program gaan nooit crash konsekwent maar miskien een keer in 'n rukkie. 740 00:33:48,120 --> 00:33:50,610 >> En so kom ons probeer valgrind Op hierdie, en hier is 741 00:33:50,610 --> 00:33:52,870 waar ons sal oorweldig kry deur die uitset oomblik. 742 00:33:52,870 --> 00:34:00,810 So maak geheue valgrind lek tjek gelyk volle dot streep geheue. 743 00:34:00,810 --> 00:34:03,040 En hier is die rede waarom ek belowe dit sou oorweldig. 744 00:34:03,040 --> 00:34:05,700 Hier is wat valgrind, hier is wat 'n programmeerder, 'n paar jaar gelede- 745 00:34:05,700 --> 00:34:08,469 besluit om dit 'n goeie idee sou wees vir die produksie te lyk. 746 00:34:08,469 --> 00:34:09,750 So laat sin maak van hierdie. 747 00:34:09,750 --> 00:34:13,120 So al die pad van die linker span vir geen goeie rede 748 00:34:13,120 --> 00:34:16,620 is die proses van die program ID ons net loop, die unieke identifiseerder 749 00:34:16,620 --> 00:34:18,030 vir die program het ons net gehardloop. 750 00:34:18,030 --> 00:34:19,738 Ons verwyder dat vanaf die skyfie, maar daar 751 00:34:19,738 --> 00:34:22,190 is 'n paar nuttige inligting in hier. 752 00:34:22,190 --> 00:34:24,684 >> Kom ons blaai tot die heel boonste. 753 00:34:24,684 --> 00:34:25,600 Hier is waar ons begin het. 754 00:34:25,600 --> 00:34:27,040 So dit is nie alles wat veel uitset. 755 00:34:27,040 --> 00:34:30,429 Hier is wat ongeldig skryf grootte 4 op die lyn 21. 756 00:34:30,429 --> 00:34:31,760 Wel, wat was line 21? 757 00:34:31,760 --> 00:34:34,500 Line 21 was presies hierdie en dit maak sin 758 00:34:34,500 --> 00:34:37,290 dat ek in geldiglik skryf 4 grepe omdat ek 759 00:34:37,290 --> 00:34:40,389 probeer om hierdie heelgetal sit, wat kan enigiets wees, 760 00:34:40,389 --> 00:34:42,370 dit gebeur net te wees nul, maar ek probeer 761 00:34:42,370 --> 00:34:44,940 om dit te sit op 'n plek wat behoort nie aan my nie. 762 00:34:44,940 --> 00:34:50,900 Verder, hier, 40 grepe in een blokke is beslis verlore in 'n rekordtyd 1. 763 00:34:50,900 --> 00:34:56,500 Dit is omdat wanneer ek noem malloc hier, ek het nooit werklik vry om die geheue. 764 00:34:56,500 --> 00:34:58,140 >> So hoe kan ons dit regmaak? 765 00:34:58,140 --> 00:35:02,970 Laat my gaan voort en 'n bietjie veiliger en doen 9 daar en laat my hier gratis x. 766 00:35:02,970 --> 00:35:04,820 Dit is die nuwe funksie vir vandag. 767 00:35:04,820 --> 00:35:11,520 As ek nou tik maak geheue dot streep laat hardloop weer valgrind op dit, 768 00:35:11,520 --> 00:35:14,990 maksimeer my venster en druk Enter. 769 00:35:14,990 --> 00:35:16,900 Nou, dit is goed. 770 00:35:16,900 --> 00:35:19,590 Hulle begrawe die goeie nuus in al hierdie uitset. 771 00:35:19,590 --> 00:35:20,810 Alle hoop blokke was vry. 772 00:35:20,810 --> 00:35:23,604 Ons sal terug na wat die hoop kom is, maar geen lekkasies is moontlik. 773 00:35:23,604 --> 00:35:25,520 So dit is net nog 'n instrument vir jou tool kit 774 00:35:25,520 --> 00:35:30,220 waarmee jy kan begin om vind nou foute soos dit. 775 00:35:30,220 --> 00:35:34,532 >> Maar laat ons sien wat meer kan hier verkeerd gaan. 776 00:35:34,532 --> 00:35:38,890 Kom ons oorgang nou eintlik 'n probleem oplos. 777 00:35:38,890 --> 00:35:42,440 As 'n eenkant, as dit sal 'n verlig bietjie van verwarring of spanning, 778 00:35:42,440 --> 00:35:43,430 dit is nou snaaks. 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 Dit is redelik goed. 782 00:35:49,040 --> 00:35:50,890 Omdat pointers is adresse en adresse 783 00:35:50,890 --> 00:35:53,098 is oor die algemeen deur konvensie geskryf met heksadesimale. 784 00:35:53,098 --> 00:35:54,650 Ha, ha, dit is nou snaaks. 785 00:35:54,650 --> 00:35:58,390 Anyhow, so laat nou eintlik 'n probleem op te los. 786 00:35:58,390 --> 00:36:00,840 Dit het super was, super lae-vlak tot dusver, 787 00:36:00,840 --> 00:36:03,950 en ons kan werklik nuttig te doen dinge met hierdie lae-vlak besonderhede. 788 00:36:03,950 --> 00:36:06,710 >> Sodat ons 'n paar weke bekend gestel gelede het die idee van 'n skikking. 789 00:36:06,710 --> 00:36:09,177 'N skikking was lekker, want dit is moeilik om skoon te maak ons ​​kode 790 00:36:09,177 --> 00:36:11,760 want as ons wou 'n skrywe program met verskeie studente 791 00:36:11,760 --> 00:36:15,270 of veelvuldige name en huise en slaapsale en kolleges en al van dat, 792 00:36:15,270 --> 00:36:19,430 kon ons alles meer te stoor skoon binnekant van 'n skikking. 793 00:36:19,430 --> 00:36:23,039 Maar voor een nadeel van 'n skikking wat tot dusver. 794 00:36:23,039 --> 00:36:26,080 Selfs as jy dit nie self gely het in 'n program, net instinktief, 795 00:36:26,080 --> 00:36:30,870 Wat is 'n slegte ding oor 'n skikking, miskien? 796 00:36:30,870 --> 00:36:32,337 Ek hoor dat sommige geruise. 797 00:36:32,337 --> 00:36:34,170 GEHOOR: Dit is moeilik om die grootte te verander. 798 00:36:34,170 --> 00:36:36,128 David Malan: Dit is moeilik om die grootte te verander. 799 00:36:36,128 --> 00:36:38,660 Jy kan die grootte verander nie van 'n skikking, in werklikheid, per se 800 00:36:38,660 --> 00:36:43,040 in C. Jy kan 'n skikking te ken, beweeg alles van die ou een 801 00:36:43,040 --> 00:36:45,380 in die nuwe, en nou het 'n paar ekstra ruimte, 802 00:36:45,380 --> 00:36:47,469 maar dit is nie soos 'n taal soos Java of Python 803 00:36:47,469 --> 00:36:49,760 of enige aantal ander tale waarmee sommige van julle 804 00:36:49,760 --> 00:36:52,070 vertroud te wees waar jy kan net bly die toevoeging van dinge 805 00:36:52,070 --> 00:36:53,930 vervelens tot die einde van 'n skikking. 806 00:36:53,930 --> 00:36:57,880 Wanneer jy 'n verskeidenheid van grootte 6, wat die grootte is, 807 00:36:57,880 --> 00:37:01,970 en so baie soos die idee vroeër 'n buffer van 'n sekere grootte, 808 00:37:01,970 --> 00:37:05,940 jy het om te raai uit die hek watter grootte jy wil hê dit moet wees? 809 00:37:05,940 --> 00:37:07,880 As jy dink te groot, jy mors ruimte. 810 00:37:07,880 --> 00:37:10,950 As jy te klein dink jy kan daardie data stoor nie, ten minste 811 00:37:10,950 --> 00:37:12,940 sonder 'n baie meer werk. 812 00:37:12,940 --> 00:37:18,180 >> So vandag, te danke aan wysers, ons kan begin stik saam ons eie persoonlike 813 00:37:18,180 --> 00:37:20,989 data strukture, en in Trouens, hier is iets 814 00:37:20,989 --> 00:37:23,030 wat lyk 'n bietjie meer kriptiese met die eerste oogopslag, 815 00:37:23,030 --> 00:37:26,440 maar dit is wat ons noem 'n gekoppelde sal lys, en sy naam van 'n opsomming van die soort 816 00:37:26,440 --> 00:37:26,940 Dit. 817 00:37:26,940 --> 00:37:29,550 Dit is 'n lys van die nommers, of in hierdie geval, 'n lys van getalle, 818 00:37:29,550 --> 00:37:33,480 maar dit kan 'n lys van alles wees nie, maar dit gekoppel saam deur middel van pyle, 819 00:37:33,480 --> 00:37:36,380 en net 'n raaiskoot te neem met wat tegniek 820 00:37:36,380 --> 00:37:38,310 gaan ons in staat wees om om saam te steek, 821 00:37:38,310 --> 00:37:42,540 soort van soos springmielies met 'n draad, 'n geskakelde lyste reghoeke hier? 822 00:37:42,540 --> 00:37:43,936 Die getalle? 823 00:37:43,936 --> 00:37:45,560 Wat is die taal funksie onderliggende? 824 00:37:45,560 --> 00:37:46,350 >> GEHOOR: 'n wyser. 825 00:37:46,350 --> 00:37:47,308 >> David Malan: 'n wyser. 826 00:37:47,308 --> 00:37:51,700 So elkeen van hierdie pyle hier verteenwoordig 'n wyser of net 'n adres. 827 00:37:51,700 --> 00:37:54,590 So met ander woorde, as ek wil om 'n lys van die nommers te slaan, 828 00:37:54,590 --> 00:37:59,040 Ek kan nie net stoor dit as ek wil die vermoë om te groei en krimp 829 00:37:59,040 --> 00:38:00,990 my data struktuur in 'n skikking. 830 00:38:00,990 --> 00:38:03,000 So ek moet 'n bietjie het meer gesofistikeerd, 831 00:38:03,000 --> 00:38:05,720 maar sien dat hierdie prentjie soort dui 832 00:38:05,720 --> 00:38:08,650 dat as jy net het bietjie drade die koppeling van alles, 833 00:38:08,650 --> 00:38:13,100 is waarskynlik nie so moeilik om plek te maak tussen twee van die reghoeke 834 00:38:13,100 --> 00:38:16,750 of twee van daardie nodusse, soos ons sal begin hulle roep, sit in 'n nuwe node, 835 00:38:16,750 --> 00:38:19,547 en dan met 'n paar nuwe draad, net sloot die drie nodes saam 836 00:38:19,547 --> 00:38:22,880 die eerste een, die laaste een, en die een dat jy net plaas in die middel. 837 00:38:22,880 --> 00:38:26,000 >> En inderdaad 'n geskakelde lys, anders 'n skikking, is dinamies. 838 00:38:26,000 --> 00:38:27,840 Dit kan groei en dit kan krimp en jy doen nie 839 00:38:27,840 --> 00:38:32,434 moet weet of omgee vooraf hoe veel data jy gaan word berging, 840 00:38:32,434 --> 00:38:35,600 maar dit blyk ons ​​het 'n klein om te wees versigtig wees oor hoe om dit te implementeer. 841 00:38:35,600 --> 00:38:39,070 So eers laat dink oor hoe ons te implementeer een van hierdie kleintjies reghoeke. 842 00:38:39,070 --> 00:38:40,690 Dit is maklik om 'n int implementeer. 843 00:38:40,690 --> 00:38:44,000 Jy sê net int N en dan jy 4 grepe vir 'n int, 844 00:38:44,000 --> 00:38:49,089 maar hoe kry ek 'n int, noem dit n, en dan 'n wyser, kom ons noem dit die volgende. 845 00:38:49,089 --> 00:38:50,880 Ons kon hierdie skakel dinge wat ons wil niks 846 00:38:50,880 --> 00:38:53,590 maar ek het 'n persoonlike data struktuur. 847 00:38:53,590 --> 00:38:54,257 Ja? 848 00:38:54,257 --> 00:38:57,020 >> GEHOOR: Ampersand [onhoorbaar]. 849 00:38:57,020 --> 00:39:00,940 >> David Malan: So ampersand ons sal gebruik om kry die adres van 'n node potensieel. 850 00:39:00,940 --> 00:39:02,740 Maar ons mekaar nodig kenmerk van C in orde 851 00:39:02,740 --> 00:39:06,700 my die vermoë om te skep gee hierdie gebruik reghoek, hierdie gewoonte 852 00:39:06,700 --> 00:39:08,919 veranderlike as jy wil, in die geheue. 853 00:39:08,919 --> 00:39:09,710 GEHOOR: 'n struct. 854 00:39:09,710 --> 00:39:10,626 David Malan: 'n struct. 855 00:39:10,626 --> 00:39:14,310 Onthou van verlede week, het ons ' struct, hierdie relatief eenvoudige navraag 856 00:39:14,310 --> 00:39:16,254 waarmee ons dinge soos hierdie te maak. 857 00:39:16,254 --> 00:39:18,420 C het nie kom met 'n data struktuur genaamd student. 858 00:39:18,420 --> 00:39:22,190 Dit kom met int en float en char en so, maar dit kom nie met student, 859 00:39:22,190 --> 00:39:26,750 maar ons kan 'n tipe student data te skep, 'n student struktuur, met hierdie sintaksis 860 00:39:26,750 --> 00:39:27,250 hier. 861 00:39:27,250 --> 00:39:28,350 En jy sal dit weer en weer te sien. 862 00:39:28,350 --> 00:39:30,426 So moenie bekommerd wees oor memorisering die sleutelwoorde, 863 00:39:30,426 --> 00:39:33,300 maar die term wat belangrik is, is Net die feit dat ons gesê struct 864 00:39:33,300 --> 00:39:37,590 en dan genoem ons student en binne van die student was 'n naam en 'n huis 865 00:39:37,590 --> 00:39:39,390 of 'n dorm of die wil. 866 00:39:39,390 --> 00:39:41,980 >> En so nou vandag, laat ons voor hierdie. 867 00:39:41,980 --> 00:39:45,240 Ek het 'n paar woorde bygevoeg, maar as ek wil hierdie reghoek dis implementeer 868 00:39:45,240 --> 00:39:48,440 het beide 'n int en 'n wyser, jy weet wat, ek is 869 00:39:48,440 --> 00:39:51,540 gaan 'n struct genoem node te verklaar. 870 00:39:51,540 --> 00:39:55,630 Ek is ook binnekant van dit, gaan om te sê dat 'n knoop, hierdie reghoek, het 'n int 871 00:39:55,630 --> 00:39:59,730 en ons sal dit noem N en dit het 'n volgende wyser. 872 00:39:59,730 --> 00:40:02,540 En dit is 'n bietjie verbose, maar as jy daaroor dink, 873 00:40:02,540 --> 00:40:07,300 die pyle wat in die prentjie was 'n oomblik gelede is van watter tipe data? 874 00:40:07,300 --> 00:40:12,330 Waar elkeen van die pyle wys om watter tipe data struktuur? 875 00:40:12,330 --> 00:40:14,332 Dit is nie wys net 'n int per se. 876 00:40:14,332 --> 00:40:16,165 Dit verwys na die hele ding reghoekige 877 00:40:16,165 --> 00:40:18,720 en dat vierkantige ding, het ons gesê, is 'n knoop genoem. 878 00:40:18,720 --> 00:40:21,720 En so het ons soort te rekursief hierdie so te definieer 879 00:40:21,720 --> 00:40:26,270 dat 'n knoop, sal ons sê, sal 'n int genoem N bevat 880 00:40:26,270 --> 00:40:31,070 en 'n wyser genoem volgende en die tipe data struktuur wat 881 00:40:31,070 --> 00:40:35,770 dat wyser punte is blykbaar gaan struct node wees. 882 00:40:35,770 --> 00:40:41,550 >> So dit is lastig verbose en net om pedanties wees, 883 00:40:41,550 --> 00:40:44,100 die rede waarom ons nie kan nie net dit sê, wat eerlik 884 00:40:44,100 --> 00:40:46,860 lyk 'n baie meer leesbaar, is omdat onthou dat C gelees 885 00:40:46,860 --> 00:40:48,710 dinge bo na onder, links na regs. 886 00:40:48,710 --> 00:40:54,120 Dit is nie totdat ons die kommapunt dat die navraag node werklik bestaan. 887 00:40:54,120 --> 00:40:57,980 So as ons wil hierdie soort van het sikliese verwysing binnekant van die data 888 00:40:57,980 --> 00:41:02,120 struktuur, ons het om dit te doen, waar ons sê struct node by die top, wat 889 00:41:02,120 --> 00:41:06,770 gee ons 'n langer manier om te beskryf hierdie ding, dan binnekant ons sê struct node, 890 00:41:06,770 --> 00:41:09,560 en dan op die heel laaste reël ons sê, alles reg, C, op die pad, 891 00:41:09,560 --> 00:41:12,060 net hierdie hele damn bel ding wat 'n node en stop 892 00:41:12,060 --> 00:41:14,360 gebruik van die term struct geheel en al. 893 00:41:14,360 --> 00:41:18,030 So dit is net soort van 'n sintaktiese truuk wat uiteindelik laat ons skep 894 00:41:18,030 --> 00:41:21,370 iets wat lyk presies soos hierdie. 895 00:41:21,370 --> 00:41:25,010 >> So as ons nou aanvaar ons kan implementeer hierdie ding in C, 896 00:41:25,010 --> 00:41:28,040 hoe kan ons eintlik begin dwars dit? 897 00:41:28,040 --> 00:41:32,360 Wel, in werklikheid, al wat ons moet doen, is Itereer van links na regs en net 898 00:41:32,360 --> 00:41:35,960 soort voeg nodes of nodes verwyder of soek vir dinge waar ons wil, 899 00:41:35,960 --> 00:41:39,560 maar om dit te doen, laat ons gaan voort en maak dinge 'n bietjie meer real, want dit 900 00:41:39,560 --> 00:41:42,560 het super lae-vlak tot dusver. 901 00:41:42,560 --> 00:41:45,700 Sou iemand letterlik wil eerste te wees? 902 00:41:45,700 --> 00:41:46,200 OK. 903 00:41:46,200 --> 00:41:47,092 Kom up. 904 00:41:47,092 --> 00:41:47,800 Wat is jou naam? 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 Bly te kenne. 908 00:41:49,998 --> 00:41:50,960 Ek ook. 909 00:41:50,960 --> 00:41:52,450 Alles reg. 910 00:41:52,450 --> 00:41:53,990 En ons moet 'n nommer 9. 911 00:41:53,990 --> 00:41:55,240 Nie so goed soos die eerste, miskien. 912 00:41:55,240 --> 00:41:56,430 OK, nommer 9. 913 00:41:56,430 --> 00:41:59,667 'N Aantal 17, asseblief. 914 00:41:59,667 --> 00:42:01,000 Laat my terug te gaan 'n bietjie verder. 915 00:42:01,000 --> 00:42:03,980 Nommer 22, asseblief, en hoe oor verder terug 916 00:42:03,980 --> 00:42:06,344 as ek hande kan sien met al die ligte of geen. 917 00:42:06,344 --> 00:42:08,010 Iemand wat net daar vrywillig. 918 00:42:08,010 --> 00:42:08,968 Wil jy om te kom? 919 00:42:08,968 --> 00:42:10,450 Jou voorarm is geweld opgaan. 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 neerdaal. 923 00:42:15,120 --> 00:42:18,450 Sou enige iemand anders wil forcefully-- Kom up. 924 00:42:18,450 --> 00:42:21,030 'N werklike vrywilliger. 925 00:42:21,030 --> 00:42:23,330 >> So baie vinnig, as julle ouens kan reël 926 00:42:23,330 --> 00:42:26,550 julle net soos die nodes op die skerm. 927 00:42:26,550 --> 00:42:27,510 Dankie. 928 00:42:27,510 --> 00:42:29,234 En jy sal wees 26. 929 00:42:29,234 --> 00:42:30,650 Alle regte en vinnige inleidings. 930 00:42:30,650 --> 00:42:32,139 So ek is David en jy is ook? 931 00:42:32,139 --> 00:42:32,680 DAVID: David. 932 00:42:32,680 --> 00:42:33,721 David Malan: En jy is? 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 Uitstekend. 940 00:42:37,590 --> 00:42:39,810 So dit is ons vrywilligers vir vandag en gaan voort 941 00:42:39,810 --> 00:42:43,090 en skuif 'n bietjie op die manier, en net voort te gaan en hou 942 00:42:43,090 --> 00:42:47,024 hou jou nommers as jy is of jou eerste teken en die gebruik van jou linkerhand, 943 00:42:47,024 --> 00:42:48,940 gaan voort en net implementeer hierdie pyle, net 944 00:42:48,940 --> 00:42:51,360 sodat jou linkerhand is letterlik wys op alles wat jy behoort te wys 945 00:42:51,360 --> 00:42:54,610 op, en gee jouself 'n ruimte sodat kan ons visueel sien jou arms eintlik 946 00:42:54,610 --> 00:42:58,120 wys, en jy kan net wys soort van op die grond is goed. 947 00:42:58,120 --> 00:43:03,040 >> So hier het ons 'n geskakelde lys van een, twee, drie, vier, vyf nodes aanvanklik, 948 00:43:03,040 --> 00:43:05,860 en sien ons het hierdie spesiale wyser aan die begin wie se 949 00:43:05,860 --> 00:43:09,770 sleutel, want ons het om tred te hou van die hele lengte lys een of ander manier. 950 00:43:09,770 --> 00:43:13,590 Hierdie ouens, selfs al is hulle weg na regs, rug aan rug in die geheue, 951 00:43:13,590 --> 00:43:15,950 hulle kan eintlik enige plek wees in die geheue van die rekenaar. 952 00:43:15,950 --> 00:43:18,240 So hierdie ouens kan wees staan ​​op enige plek op die stadium 953 00:43:18,240 --> 00:43:20,960 en dit is goed, so lank as wat hulle is eintlik wys na mekaar 954 00:43:20,960 --> 00:43:22,770 maar om dinge te hou skoon en eenvoudig, sal ons 955 00:43:22,770 --> 00:43:25,728 hulle net teken links na regs soos hierdie, maar daar kon wees massiewe gapings 956 00:43:25,728 --> 00:43:26,790 tussen diegene nodes. 957 00:43:26,790 --> 00:43:30,710 >> Nou, as ek wil eintlik voeg 'n paar nuwe waarde, laat ons gaan voort en doen dit. 958 00:43:30,710 --> 00:43:33,720 Ons het 'n geleentheid nou na 'n ander node te kies. 959 00:43:33,720 --> 00:43:39,820 Sê laat begin met mallocing 55. 960 00:43:39,820 --> 00:43:41,320 Sal iemand omgee om malloc? 961 00:43:41,320 --> 00:43:42,280 OK, kom op op. 962 00:43:42,280 --> 00:43:42,992 Wat is jou naam? 963 00:43:42,992 --> 00:43:43,700 RAINBOW: Rainbow. 964 00:43:43,700 --> 00:43:44,050 David Malan: Rainbow? 965 00:43:44,050 --> 00:43:44,810 Alles reg. 966 00:43:44,810 --> 00:43:46,600 Malloc Rainbow. 967 00:43:46,600 --> 00:43:47,450 Kom up. 968 00:43:47,450 --> 00:43:51,610 So nou het ons onsself afvra algoritmies waar ons kan sit 55. 969 00:43:51,610 --> 00:43:53,610 So ons almal weet, natuurlik, waar sy waarskynlik 970 00:43:53,610 --> 00:43:55,401 behoort as ons probeer hierdie gesorteer te hou 971 00:43:55,401 --> 00:43:58,299 en as jy kan 'n mens neem ouens stap terug sodat ons val nie af nie 972 00:43:58,299 --> 00:43:59,590 die stadium, sou groot wees. 973 00:43:59,590 --> 00:44:01,420 So eintlik, Rainbow, begin hier met my 974 00:44:01,420 --> 00:44:04,200 omdat ons as die rekenaar nou kan slegs een veranderlike op 'n tyd. 975 00:44:04,200 --> 00:44:05,190 So as dit is die eerste knoop. 976 00:44:05,190 --> 00:44:07,160 Let hy is nie 'n knoop, hy is net 'n wyser, 977 00:44:07,160 --> 00:44:10,270 en dit is die rede waarom hy getrek te wees net die grootte van 'n wyser, nie 978 00:44:10,270 --> 00:44:11,780 een van daardie volle reghoeke. 979 00:44:11,780 --> 00:44:16,650 So ons gaan om te kyk na elke iterasie is 55 minder as 9? 980 00:44:16,650 --> 00:44:17,150 Geen. 981 00:44:17,150 --> 00:44:19,060 Is 55 minder as 17? 982 00:44:19,060 --> 00:44:19,720 Geen. 983 00:44:19,720 --> 00:44:20,800 Minder as 22? 984 00:44:20,800 --> 00:44:22,020 Minder as 26? 985 00:44:22,020 --> 00:44:23,390 Minder as 34? 986 00:44:23,390 --> 00:44:25,890 En so nou, natuurlik Rainbow behoort aan die einde. 987 00:44:25,890 --> 00:44:27,270 So duidelik wees, en wat was jou naam, Taylor? 988 00:44:27,270 --> 00:44:27,895 >> TAYLOR: Taylor. 989 00:44:27,895 --> 00:44:32,510 David Malan: So onder Taylor se linkerhand en Rainbow se hande hier, 990 00:44:32,510 --> 00:44:38,324 wie se hand moet wys na wat in bestel te voeg 55 in die lys? 991 00:44:38,324 --> 00:44:39,240 Wat moet ons doen? 992 00:44:39,240 --> 00:44:39,700 Ja? 993 00:44:39,700 --> 00:44:41,140 >> GEHOOR: hand Taylor se moet links wys. 994 00:44:41,140 --> 00:44:41,680 >> David Malan: Presies. 995 00:44:41,680 --> 00:44:43,800 So 'n knoop te voeg in die einde van die lys 996 00:44:43,800 --> 00:44:47,140 is eenvoudig omdat Taylor net het om te wys, in plaas van op die grond 997 00:44:47,140 --> 00:44:49,640 of ons sal dit noem nul, null is 'n soort van die afwesigheid 998 00:44:49,640 --> 00:44:51,640 van 'n wyser of 'n spesiale nul pointer, jy 999 00:44:51,640 --> 00:44:53,740 gaan wys met jou linker hand op Rainbow en dan Rainbow, 1000 00:44:53,740 --> 00:44:55,910 Waar moet jou linkerhand hand waarskynlik wys? 1001 00:44:55,910 --> 00:44:56,570 Down. 1002 00:44:56,570 --> 00:45:00,140 Dit is nie goed as haar hand is 'n soort daarop te wys hier of soort van enige af 1003 00:45:00,140 --> 00:45:00,640 watter manier. 1004 00:45:00,640 --> 00:45:02,407 Wat oorweeg sou word 'n gemors waarde 1005 00:45:02,407 --> 00:45:04,240 maar as sy wys na 'n bekende waarde, sal ons 1006 00:45:04,240 --> 00:45:07,360 noem dit zero of null, dis OK want ons het 'n term wat in hierdie 1007 00:45:07,360 --> 00:45:09,390 en ons weet die lys is nou afgehandel. 1008 00:45:09,390 --> 00:45:11,550 >> So, wat is 'n ander relatief eenvoudige saak? 1009 00:45:11,550 --> 00:45:13,125 Kan ons malloc 5? 1010 00:45:13,125 --> 00:45:14,010 Kom up. 1011 00:45:14,010 --> 00:45:14,782 Wat is jou naam? 1012 00:45:14,782 --> 00:45:15,490 TIFFANY: Tiffany. 1013 00:45:15,490 --> 00:45:16,000 David Malan: Ek is jammer? 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 Alles reg. 1017 00:45:17,110 --> 00:45:19,071 Tiffany is malloced met die waarde 5. 1018 00:45:19,071 --> 00:45:19,570 Kom up. 1019 00:45:19,570 --> 00:45:23,820 Hierdie een is relatief maklik ook, maar Kom ons kyk volgorde van bewerkings nou. 1020 00:45:23,820 --> 00:45:25,820 Dit was redelik maklik met Taylor aan die einde. 1021 00:45:25,820 --> 00:45:30,302 Nommer 5 is natuurlik minder as 9, en so het ons David, ons het Tiffany, 1022 00:45:30,302 --> 00:45:31,260 en wat was jou 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 Dawid. 1026 00:45:34,300 --> 00:45:36,580 Wie se hand moet eerste opgedateer? 1027 00:45:36,580 --> 00:45:39,260 1028 00:45:39,260 --> 00:45:40,590 Wat wil jy hier doen? 1029 00:45:40,590 --> 00:45:45,244 Daar is 'n paar moontlike maniere, maar daar is ook een of meer verkeerde maniere. 1030 00:45:45,244 --> 00:45:46,620 >> GEHOOR: Begin met linker. 1031 00:45:46,620 --> 00:45:47,800 >> David Malan: Begin met die linker. 1032 00:45:47,800 --> 00:45:49,008 Wie is hier die linker dan? 1033 00:45:49,008 --> 00:45:49,700 GEHOOR: Eerste. 1034 00:45:49,700 --> 00:45:50,366 >> David Malan: OK. 1035 00:45:50,366 --> 00:45:53,781 So begin met die eerste en waar het jy wil werk David se hande te wees? 1036 00:45:53,781 --> 00:45:54,780 GEHOOR: Teen die 5. 1037 00:45:54,780 --> 00:45:55,446 David Malan: OK. 1038 00:45:55,446 --> 00:45:59,026 So David, punt vyf of Tiffany hier, en nou? 1039 00:45:59,026 --> 00:46:01,072 >> GEHOOR: Tiffany wys na die 9? 1040 00:46:01,072 --> 00:46:04,030 David Malan: Perfect, behalwe Binky se hoof net soort van afgeval, reg? 1041 00:46:04,030 --> 00:46:06,820 Want wat is verkeerd met hierdie foto letterlik? 1042 00:46:06,820 --> 00:46:08,070 GEHOOR: Niks wys. 1043 00:46:08,070 --> 00:46:09,945 David Malan: Niks is verwys na Jake nou. 1044 00:46:09,945 --> 00:46:13,360 Ons het letterlik gelaat 9 en 17, en ons het letterlik 1045 00:46:13,360 --> 00:46:18,450 uitgelek al hierdie geheue, want deur eerste opdatering David se hand, dit is 1046 00:46:18,450 --> 00:46:21,660 fyn sover dit korrek wys op Tiffany nou, 1047 00:46:21,660 --> 00:46:25,410 maar as niemand het die versiendheid om te wys op Jake, 1048 00:46:25,410 --> 00:46:27,490 dan het ons verloor die geheel van die lys. 1049 00:46:27,490 --> 00:46:28,200 So laat ongedaan te maak. 1050 00:46:28,200 --> 00:46:30,950 So dit was 'n goeie ding om te reis oor maar laat regstel nou. 1051 00:46:30,950 --> 00:46:33,624 Wat moet ons in die eerste plaas te doen? 1052 00:46:33,624 --> 00:46:34,124 Ja? 1053 00:46:34,124 --> 00:46:35,791 >> GEHOOR: Tiffany moet wys op die 9? 1054 00:46:35,791 --> 00:46:37,582 David Malan: Ek kan nie kry wat naby aan jou. 1055 00:46:37,582 --> 00:46:38,720 Wie moet wys op die 9? 1056 00:46:38,720 --> 00:46:39,220 >> GEHOOR: Tiffany. 1057 00:46:39,220 --> 00:46:39,390 >> David Malan: Alle reg. 1058 00:46:39,390 --> 00:46:41,200 So moet Tiffany eerste punt op die 9. 1059 00:46:41,200 --> 00:46:43,550 So Tiffany moet neem op 'n identiese waarde 1060 00:46:43,550 --> 00:46:45,820 Dawid, wat blyk oorbodig vir 'n oomblik, 1061 00:46:45,820 --> 00:46:48,820 maar dit is omdat nou fyn, tweede stap, kan ons Dawid se hand te werk 1062 00:46:48,820 --> 00:46:52,680 om te wys op Tiffany, en dan as ons net soort van skoon dinge 1063 00:46:52,680 --> 00:46:55,740 asof dit 'n soort van die lente-agtige, nou is dit 'n korrekte inplanting. 1064 00:46:55,740 --> 00:46:56,700 So uitstekend. 1065 00:46:56,700 --> 00:46:57,970 So nou het ons is amper daar. 1066 00:46:57,970 --> 00:47:01,075 Kom ons voeg 'n laaste waarde soos die waarde 20. 1067 00:47:01,075 --> 00:47:03,010 As ons 'n laaste vrywilliger kan malloc? 1068 00:47:03,010 --> 00:47:04,140 Kom up. 1069 00:47:04,140 --> 00:47:06,224 So hierdie een is 'n bietjie meer moeilik. 1070 00:47:06,224 --> 00:47:08,390 Maar regtig, die kode ons skryf, al is dit mondelings, 1071 00:47:08,390 --> 00:47:10,610 is net soos 'n klomp van as toestande nou, reg? 1072 00:47:10,610 --> 00:47:12,318 Ons het 'n toestand seker te maak dat dit behoort 1073 00:47:12,318 --> 00:47:13,840 aan die einde, miskien die begin. 1074 00:47:13,840 --> 00:47:15,940 Ons moet 'n soort van lus om vind die plek in die middel. 1075 00:47:15,940 --> 00:47:17,400 So laat doen met wat is jou 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 Bly te kenne. 1080 00:47:19,368 --> 00:47:20,490 So het ons 20. 1081 00:47:20,490 --> 00:47:21,220 Minder as vyf? 1082 00:47:21,220 --> 00:47:21,530 Geen. 1083 00:47:21,530 --> 00:47:22,160 Minder as nege? 1084 00:47:22,160 --> 00:47:22,410 Geen. 1085 00:47:22,410 --> 00:47:23,050 Minder as 17? 1086 00:47:23,050 --> 00:47:23,550 Geen. 1087 00:47:23,550 --> 00:47:23,740 OK. 1088 00:47:23,740 --> 00:47:25,701 Hy hier hoort en julle name weer is? 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 Wie se hande nodig het om ontslae eerste opgedateer? 1096 00:47:32,140 --> 00:47:32,930 >> GEHOOR: Eric. 1097 00:47:32,930 --> 00:47:33,429 OK. 1098 00:47:33,429 --> 00:47:35,200 So Eric se moet wys na 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 Maar nou, wat is volgende? 1102 00:47:38,180 --> 00:47:40,800 Sue kan dan wys op Eric en nou, as jy ouens net 1103 00:47:40,800 --> 00:47:44,077 maak 'n paar kamer, wat is goed visueel, nou is ons het die invoeging gedoen. 1104 00:47:44,077 --> 00:47:47,160 So laat nou oorweeg om 'n vraag, maar baie dankie vir ons vrywilligers. 1105 00:47:47,160 --> 00:47:48,090 Baie goed gedoen. 1106 00:47:48,090 --> 00:47:50,831 Jy kan hou dié, as jy wil. 1107 00:47:50,831 --> 00:47:54,140 En ons het 'n pragtige afskeidsgeskenk as sou jy elke graag 'n stress bal. 1108 00:47:54,140 --> 00:47:56,030 Laat my net te slaag dit neer. 1109 00:47:56,030 --> 00:47:58,430 So, wat is die afhaal van hierdie? 1110 00:47:58,430 --> 00:48:02,430 Dit lyk ongelooflik om te wees sover ons nou 1111 00:48:02,430 --> 00:48:06,360 lei 'n alternatief vir 'n skikking wat nie so is beperk 1112 00:48:06,360 --> 00:48:07,780 om 'n verskeidenheid van 'n vaste grootte. 1113 00:48:07,780 --> 00:48:09,380 Hulle kan dinamiese groei. 1114 00:48:09,380 --> 00:48:13,220 >> Maar net soos ons gesien het in weke verlede, nooit iets kry ons gratis, 1115 00:48:13,220 --> 00:48:15,740 soos sekerlik is daar 'n trade-off hier. 1116 00:48:15,740 --> 00:48:18,890 So met 'n onderstebo van 'n gekoppelde lys, is dit dinamika? 1117 00:48:18,890 --> 00:48:21,590 Hierdie vermoë om te groei en eerlik, ons kon delete gedoen 1118 00:48:21,590 --> 00:48:23,570 en ons kan krimp as dit nodig is. 1119 00:48:23,570 --> 00:48:24,710 Wat is die prys ons betaal? 1120 00:48:24,710 --> 00:48:28,510 1121 00:48:28,510 --> 00:48:30,340 Twee keer soveel ruimte, die eerste van alles. 1122 00:48:30,340 --> 00:48:34,010 As jy kyk na die prentjie, nie meer ek stoor 'n lys van heelgetalle. 1123 00:48:34,010 --> 00:48:36,740 Ek is 'n lys van die stoor heelgetalle plus wenke. 1124 00:48:36,740 --> 00:48:38,240 So ek verdubbel die bedrag van die ruimte. 1125 00:48:38,240 --> 00:48:40,740 Nou, miskien is dit nie so ' 'n groot deal 4 grepe, 8 grepe, 1126 00:48:40,740 --> 00:48:43,160 maar dit kan beslis voeg vir groot datastelle. 1127 00:48:43,160 --> 00:48:45,570 Wat is 'n ander nadeel? 1128 00:48:45,570 --> 00:48:46,070 Ja? 1129 00:48:46,070 --> 00:48:48,010 >> GEHOOR: Ons moet deurkruis hulle een-vir-een. 1130 00:48:48,010 --> 00:48:48,760 David Malan: Ja. 1131 00:48:48,760 --> 00:48:50,260 Ons moet hulle deurkruis een-vir-een. 1132 00:48:50,260 --> 00:48:53,860 Jy weet wat, ons het vir hierdie super gerieflike kenmerk van vierkante bracket 1133 00:48:53,860 --> 00:48:57,240 notasie, meer behoorlik bekend as ewetoeganklike, 1134 00:48:57,240 --> 00:48:59,280 waar ons net kan spring om 'n individu element 1135 00:48:59,280 --> 00:49:01,470 maar nou as ek nog my vrywilligers hier 1136 00:49:01,470 --> 00:49:04,660 as ek wou die vind nommer 22, ek kan net nie 1137 00:49:04,660 --> 00:49:06,620 spring na bracket iets iets. 1138 00:49:06,620 --> 00:49:10,530 Ek het om te kyk oor die lys, baie soos ons soek voorbeelde lineêr, 1139 00:49:10,530 --> 00:49:12,260 om die nommer 22 vind. 1140 00:49:12,260 --> 00:49:14,340 So lyk ons ​​'n prys daar betaal het. 1141 00:49:14,340 --> 00:49:16,430 Maar ons kan tog ander probleme op te los. 1142 00:49:16,430 --> 00:49:18,587 >> In werklikheid, laat my stel net 'n paar van die visuele. 1143 00:49:18,587 --> 00:49:20,920 So as jy af te gewees het Mather se Eetsaal onlangs, 1144 00:49:20,920 --> 00:49:23,320 jy sal onthou dat hul stapels bak soos hierdie, 1145 00:49:23,320 --> 00:49:26,300 ons geleen hierdie uit Annenberg voor die klas. 1146 00:49:26,300 --> 00:49:28,930 So hierdie stapel bak, al is, verteenwoordigend eintlik 1147 00:49:28,930 --> 00:49:30,860 van 'n rekenaar wetenskap data struktuur. 1148 00:49:30,860 --> 00:49:32,910 Daar is 'n datastruktuur in Rekenaarwetenskap 1149 00:49:32,910 --> 00:49:38,010 bekend as 'n stapel wat baie mooi leen hom presies hierdie visuele. 1150 00:49:38,010 --> 00:49:41,380 So as elk van hierdie bak is nie 'n skinkbord maar soos 'n nommer en ek wou 1151 00:49:41,380 --> 00:49:45,010 om getalle op te slaan, ek kan 'n mens af hier sit, 1152 00:49:45,010 --> 00:49:48,320 en ek kon nog hier sit, en gaan voort stapel getalle 1153 00:49:48,320 --> 00:49:53,180 op die top van mekaar, en wat is potensieel nuttige oor hierdie 1154 00:49:53,180 --> 00:49:55,450 is dat die implikasie wat is van hierdie data struktuur? 1155 00:49:55,450 --> 00:49:58,045 Watter getal kan ek trek uit eerste mees gerieflik? 1156 00:49:58,045 --> 00:50:00,640 1157 00:50:00,640 --> 00:50:03,030 Die mees onlangs een put daar. 1158 00:50:03,030 --> 00:50:06,430 >> So dit is wat ons sou noem in rekenaarwetenskap n LIFO data struktuur. 1159 00:50:06,430 --> 00:50:08,070 Laaste in, eerste uit. 1160 00:50:08,070 --> 00:50:10,800 En ons sal sien voor lank waarom wat kan nou nuttig, maar wees vir, 1161 00:50:10,800 --> 00:50:12,200 Dink maar aan die eiendom. 1162 00:50:12,200 --> 00:50:15,158 En dit is soort van dom as jy dink oor hoe die eetsaal doen dit. 1163 00:50:15,158 --> 00:50:17,910 Elke keer as hulle skoon bak en sit die verste kinders bo-op, 1164 00:50:17,910 --> 00:50:22,160 jy kan 'n voorheen skoon het maar uiteindelik baie vuil en stowwerige 1165 00:50:22,160 --> 00:50:24,360 skinkbord aan die onderkant As jy nog nooit werklik 1166 00:50:24,360 --> 00:50:26,820 kry aan die onderkant van die stapel, omdat jy net 1167 00:50:26,820 --> 00:50:29,380 hou om die nuwe en die skones op die top van dit. 1168 00:50:29,380 --> 00:50:31,840 Dieselfde ding kan gebeur in 'n supermark ook. 1169 00:50:31,840 --> 00:50:35,450 As jy 'n vertoonkas melk en elke keer CVS 1170 00:50:35,450 --> 00:50:37,610 of wie kry meer melk, jy net stoot die melk 1171 00:50:37,610 --> 00:50:39,880 jy reeds aan die agterkant en jy sit die nuwes aan die voorkant, 1172 00:50:39,880 --> 00:50:43,088 jy gaan 'n paar mooi nare het melk aan die einde van die data struktuur, 1173 00:50:43,088 --> 00:50:46,390 want dit is altyd aan die onderkant of in dieselfde dit is altyd aan die agterkant. 1174 00:50:46,390 --> 00:50:50,407 >> Maar daar is 'n ander manier om te dink oor voering data en byvoorbeeld hierdie. 1175 00:50:50,407 --> 00:50:53,490 As jy een van daardie mense wat daarvan hou te reël om buite Apple winkels 1176 00:50:53,490 --> 00:50:55,610 wanneer 'n nuwe produk kom uit, het jy waarskynlik is 1177 00:50:55,610 --> 00:50:58,780 nie met behulp van 'n stapel data struktuur, want jy 1178 00:50:58,780 --> 00:51:03,070 sou vervreem almal wat voering 'n paar nuwe speelding te koop. 1179 00:51:03,070 --> 00:51:06,610 Inteendeel, is jy waarskynlik die gebruik van watter soort data struktuur 1180 00:51:06,610 --> 00:51:10,050 of watter soort stelsel in die werklike wêreld? 1181 00:51:10,050 --> 00:51:13,493 Hopelik is dit 'n lyn, of meer behoorlik of meer Britse-agtige, 'n tou. 1182 00:51:13,493 --> 00:51:17,700 En dit blyk 'n tou is ook 'n data struktuur in rekenaarwetenskap, 1183 00:51:17,700 --> 00:51:19,700 maar 'n tou het 'n baie verskillende eiendom. 1184 00:51:19,700 --> 00:51:20,820 Dit is nie LIFO. 1185 00:51:20,820 --> 00:51:21,990 Laaste in, eerste uit. 1186 00:51:21,990 --> 00:51:22,800 God verbied. 1187 00:51:22,800 --> 00:51:24,280 Dit is in plaas EIEU. 1188 00:51:24,280 --> 00:51:26,110 Eerste in, eerste uit. 1189 00:51:26,110 --> 00:51:27,970 En dit is 'n goeie ding vir regverdigheid wille 1190 00:51:27,970 --> 00:51:30,428 beslis wanneer jy voering is up super vroeg in die oggend. 1191 00:51:30,428 --> 00:51:33,400 As jy eerste daar kry, moet jy wil uitkom eerste sowel. 1192 00:51:33,400 --> 00:51:35,880 >> En so al hierdie data strukture, toue en stapels 1193 00:51:35,880 --> 00:51:39,220 en trosse van ander, blyk jy kan dink dit as net 'n skikking. 1194 00:51:39,220 --> 00:51:41,820 Dit is 'n skikking, miskien 'n vaste grootte 4, maar dit wil 1195 00:51:41,820 --> 00:51:44,990 soort van lekker wees as ons kon net hoop bak byna oneindig lank as ons 1196 00:51:44,990 --> 00:51:46,780 het dat baie bak of nommers. 1197 00:51:46,780 --> 00:51:48,840 So miskien wil ons gebruik 'n geskakelde lys hier 1198 00:51:48,840 --> 00:51:51,800 maar die trade-off gaan wees potensieel dat ons meer geheue nodig het, 1199 00:51:51,800 --> 00:51:55,930 neem 'n bietjie meer tyd, maar ons moenie die hoogte van die stapel nie beperk, 1200 00:51:55,930 --> 00:51:59,550 baie soos Mather se vertoonkas kan beperk die grootte van die stapel, 1201 00:51:59,550 --> 00:52:03,117 en so dit is ontwerp besluite of opsies wat beskikbaar is vir ons uiteindelik. 1202 00:52:03,117 --> 00:52:04,950 So met hierdie data strukture, het ons begin 1203 00:52:04,950 --> 00:52:09,360 sien nuwe bogrense potensieel op wat voorheen was super vinnig 1204 00:52:09,360 --> 00:52:11,260 en waar ons sal laat af vandag en waar 1205 00:52:11,260 --> 00:52:13,200 ons sal hoop om te kry is op Woensdag, sal ons 1206 00:52:13,200 --> 00:52:15,740 begin om te kyk na 'n data struktuur wat laat ons soek 1207 00:52:15,740 --> 00:52:18,260 deur data in log eindtyd weer. 1208 00:52:18,260 --> 00:52:21,470 En ons sien dat, onthou, in week nul en een met binêre soek of deel 1209 00:52:21,470 --> 00:52:22,180 en oorwin. 1210 00:52:22,180 --> 00:52:26,240 Dit kom terug en nog beter, die heilige graal vir hierdie Woensdag 1211 00:52:26,240 --> 00:52:29,510 sal wees om te kom met die data struktuur wat werklik loop 1212 00:52:29,510 --> 00:52:32,070 of teoreties in konstante tyd waardeur 1213 00:52:32,070 --> 00:52:34,760 dit maak nie saak hoeveel miljoene of biljoene dinge 1214 00:52:34,760 --> 00:52:38,470 ons het in die data struktuur, sal dit neem ons konstante tyd, miskien 'n stap 1215 00:52:38,470 --> 00:52:41,387 of twee stappe of 10 stappe, maar konstante getalle stappe 1216 00:52:41,387 --> 00:52:42,970 om te soek deur die data-struktuur. 1217 00:52:42,970 --> 00:52:46,300 Dit sal inderdaad die heilige graal wees maar meer oor dit op Woensdag. 1218 00:52:46,300 --> 00:52:49,045 Sien ya dan. 1219 00:52:49,045 --> 00:52:53,704 >> [Speel van musiek] 1220 00:52:53,704 --> 00:56:08,448