[Speel van musiek] 

[Video speel] 

-hy Lieg. 

-About Wat? 

-Ek weet nie. 

-So wat weet ons? 

-dat Op 09:15, Ray Santoya was by die OTM. -Yeah. So die vraag is, wat hy doen op 09:16? 

-Shooting Die 9 millimeter na iets. Miskien sien hy die sniper. 

-of Besig was met hom. 

-Wait. Gaan terug een. 

-Wat sien jy? 

-Bring Sy gesig vol skerm. 

-Sy bril. 

-Daar Is 'n weerspieëling. 

-Dit Is die Nuevitas baseball span. Dit is hul logo. 

-en Hy praat om wie se dra dat baadjie. 

[Einde afspeel] 

David Malan: Alle reg. Dit is CS50, en dit is 'n bietjie meer van [onhoorbaar] waarmee jy rondspeel met die probleem sit vier. Vandag het ons begin om 'n bietjie meer te kyk diep op hierdie dinge genoem wysers, wat selfs al is dit n mooi arcane onderwerp dit blyk dat dit gaan die middel wees waardeur ons kan begin bou en samestelling veel meer gesofistikeerde programme. Maar ons het dit op verlede Woensdag deur die eerste manier van sommige claymation. So hierdie, onthou, is Binky en ons het hom gebruik 'n blik op 'n program wat neem het nie regtig iets interessant, maar dit het 'n paar probleme openbaar. So om te begin vandag, hoekom het ons nie loop vinnig deur 'n paar van hierdie stappe, probeer om distilleer in terme menslike se presies wat gaan hier aan en waarom dit is sleg, en dan beweeg op en eintlik begin die bou van iets met hierdie tegniek? So dit was die eerste twee lyne in hierdie program en in leketaal, wat word hierdie twee lyne doen? Iemand wat redelik gemaklik met wat verklaar word op die skerm? Wat is hierdie twee lyne doen? Dit is nie al wat anders week een, maar daar is 'n paar nuwe spesiale simbool. Ja? Terug daar. 

GEHOOR: Verklaar riglyne? David Malan: Weer sê? GEHOOR: Verklaar riglyne? David Malan: Verklaar wysers en laat verfyn dit 'n bietjie meer. GEHOOR: [onhoorbaar] adres x en dan y. David Malan: En dan spreek. So spesifiek wat ons doen is ons verklaar twee veranderlikes. Hierdie veranderlikes, al is, gaan van die tipe int ster te wees wat meer spesifiek beteken hulle gaan om te slaan die adres van 'n int, onderskeidelik, x en y. Nou is daar enige waardes? Is daar enige werklike adresse in hierdie twee veranderlikes op hierdie punt in die tyd? Geen. Dit is net die sogenaamde vullis waardes. As jy nie eintlik wys 'n veranderlike, ongeag in RAM was voorheen gaan vul met nulle en dié beide van die veranderlikes. Maar ons weet nog nie wat hulle is en dit is gaan die sleutel tot hoekom Binky te wees verloor sy kop verlede week. 

So dit was die claymation inkarnasie van hierdie waardeur jy net twee veranderlikes, bietjie omsendbrief stukke van klei wat kan veranderlikes slaan nie, maar as die toegedraai pyle dui, hulle is nie eintlik wys om oral bekend per se. So dan het ons hierdie lyn, en dit was 'n nuwe verlede week, malloc vir die geheue toekenning, wat net 'n fancy manier van die vertel van die bedryfstelsel, Linux of Mac OS of Windows, hey, gee my 'n paar geheue, en al wat jy hoef te vertel die bedryfstelsel is wat toe vra dit vir die geheue. Dit gaan nie om te sorg wat jy gaan om dit te doen met dit, maar jy moet om die bedryfstelsel te vertel stelsel wat deur middel van malloc. Ja? 

GEHOOR: Hoeveel? David Malan: Hoeveel? Hoeveel in grepe, en so is dit weer, 'n geforseerde byvoorbeeld net sê, gee my die grootte van 'n int. Nou, die grootte van 'n int vier grepe of 32 stukkies. So dit is net 'n manier om sê, hey, bedryfstelsel, gee my vier grepe van die geheue wat ek kan gebruik tot my beskikking, en spesifiek, wat beteken malloc terugkeer met betrekking om daardie deel van vier grepe? GEHOOR: spreek? David Malan: Die adres. Die adres van daardie deel van vier grepe. Presies. En so dit is wat uiteindelik gestoor in x en dit is hoekom ons nie regtig omgee wat die nommer van daardie adres is, of dit nou OX1 of OX2 of 'n kriptiese heksadesimale adres. Ons gee net picturaal dat veranderlike x is nou wys dat die stuk van die geheue. So het die pyl verteenwoordig 'n wyser, of meer spesifiek, 'n geheue adres. Maar weereens, ons nie omgee tipies wat daardie werklike adresse. Nou, hierdie lyn sê wat in leketaal? Star x kry 42 kommapunt. Wat beteken dit? Jy wil gaan? Moenie krap jou nek. 

GEHOOR: Die adres van x is by die 42. 

David Malan: Die adres van x is op 42. Nie heeltemaal nie. So naby, maar nie heeltemal nie, want daar is die ster wat se voorvoegsel hierdie x. So moet ons 'n bietjie tweak. Ja? 

GEHOOR: Die waarde wat die wyser x dui op is 42. David Malan: OK. Die waarde wat die wyser x is verwys na, kom ons sê, sal 42, of 'n ander manier, die ster x sê, gaan na wat ookal adres is in x, of dit nou 1 Oxford Straat of 33 Oxford Street of OX1 of ox33, ongeag dat numeriese adres is star x is die dereferencing van x. So gaan na daardie adres en dan sit die getal 42 is daar. Sodat sou wees 'n ekwivalent manier om te sê nie. So dit is alles goed en dan sou ons die prentjie verteenwoordig soos volg waar ons het bygevoeg die 42 tot daardie deel van vier grepe op die regterkant, maar hierdie lyn was waar dinge skeefgeloop en Binky se kop inloer af op hierdie punt, omdat slegte dinge gebeur wanneer jy dereference vullis waardes of jy dereference ongeldig wysers, en ek sê ongeldig want op hierdie punt in die storie, wat is die binnekant van y? Wat is die waarde van y gebaseer op die afgelope paar stappe? Ja? Wat is dit? 

GEHOOR: 'n adres. David Malan: 'n adres. Dit moet 'n adres maar ek het dit geïnisialiseer? So ek nog nie. So, wat is bekend te wees daar? Dit is net 'n paar vullis waarde. Dit kan enige adres van nul te wees 2000000000 as jy twee gigs RAM, of nul tot 4 miljard as jy het het vier GB RAM. Dit is 'n paar vullis waarde maar die probleem is dat die bedryfstelsel, As dit nie vir jou gegee het wat deel van die geheue spesifiek dat jy probeer om te gaan na, dit is oor die algemeen gaan wat veroorsaak ons gesien as 'n segmentering skuld. So in werklikheid, enige van julle wat gesukkel op probleme by kantoorure of in probleme wat meer algemeen met die probeer om uit te vind 'n segmentering skuld, dit beteken dat die algemeen Jy is 'n segment van die aanraak geheue wat jy nie moet wees nie. Jy geheue raak wat die bedryfstelsel het nie toegelaat dat jy raak, of dit nou deur te gaan te ver in jou array of die begin nou, of dit is omdat jy raak geheue wat net 'n paar is vullis waarde. 

So doen star x hier soort van undefined gedrag. Jy moet nooit doen dit omdat kans is, is die program net gaan om te crash, omdat jy sê: na hierdie adres en jy het geen idee waar daardie adres eintlik is. So die bedryfstelsel is waarskynlik gaan jou program crash as 'n gevolg en inderdaad, dit is wat daar gebeur het om Binky. So uiteindelik Binky vaste hierdie probleem met hierdie. Sodat program self gebrekkig was. Maar as jy soort van vooruit en uit te voer hierdie lyn plaas, y is gelyk aan x beteken net watter adres is 'n x, sit dit ook in y. 

En so picturaal, het ons verteenwoordig dit met twee pyltjies van x en y uit wys na dieselfde plek. So semanties, x is gelyk y omdat beide van hulle is die stoor van die dieselfde adres, ergo wys op 42, en nou, wanneer jy sê ster y, gaan na die adres in y, dit het 'n interessante newe-effek. So die adres in y is die dieselfde ding as die adres in x. So as jy sê gaan na die adres in y en verander die waarde tot 13, wie anders geraak word? X is, punt D, om so te praat, moet sowel geraak word. 

En inderdaad, hoe Nick het hierdie foto in claymation was presies dit. Selfs al het ons volg die wyser y, ons beland in die dieselfde plek, en so as ons druk uit x of y se pointee, dan sou ons die waarde van 13 te sien. Nou, ek sê pointee te wees in ooreenstemming met die video. Programmeerders, om my kennis, nooit werklik sê die woord pointee, wat is skerp op, maar vir konsekwentheid met die video, besef dit is al wat dit was bedoel in daardie situasie. So enige vrae oor claymation of wenke of malloc net nog? Geen? Alles reg. 

So sonder verdere ado, laat ons neem 'n blik na waar dit het eintlik gebruik is vir 'n geruime tyd. So het ons dit CS50 biblioteek gehad Dit is het al hierdie funksies. Ons het gebruik GetInt 'n baie, GetString, waarskynlik vroeër GetLongLong in my PSet een of so, maar wat eintlik aan die gang? Wel, laat ons neem 'n vinnige blik onder die enjinkap op 'n program wat inspireer Daarom gee ons jou die CS50 biblioteek, en inderdaad as van verlede week, ons begin om diegene opleiding wiele af. So dit is nou gesorteer van 'n nadoodse van wat is aan die gang binne-in die CS50 biblioteek, selfs al het ons nou begin beweeg weg van dit vir die meeste programme. 

So, dit is 'n program genaamd scanf 0. Dit is super kort. Dit het net hierdie lyne, maar dit stel 'n funksie genoem scanf dat ons eintlik gaan om te sien in 'n oomblik binnekant van die CS50 biblioteek, al is dit in 'n effens ander vorm. So hierdie program op die lyn 16 is waarby 'n veranderlike x. So gee my vier grepe vir 'n int. Dit is al vertel gebruiker aantal asseblief, en dan dit is 'n interessante lyn wat bande eintlik saam verlede week en hierdie. Scanf, en dan sien dit neem 'n formaat string, net soos printf, % i beteken 'n int, en dan is dit neem 'n tweede argument wat lyk 'n bietjie funky. Dit is ampersand x, en om te onthou, ons net het hierdie keer die afgelope week. Wat beteken ampersand x verteenwoordig? Wat beteken ampersand doen in C? Ja? 

GEHOOR: Die adres van. David Malan: Die adres van. So dit is die teenoorgestelde van die ster-operateur, terwyl die ster operateur sê, gaan na hierdie toespraak het die ampersand operateur sê, uit te vind die adres van hierdie veranderlike, en so is dit die sleutel, want doel in die lewe se scanf is om te scan die gebruiker se insette van die sleutelbord, afhangende van wat hy of sy tipes, en lees dan insette van die gebruiker in 'n veranderlike, maar ons gesien in die afgelope twee weke dat swap funksie wat ons moeiteloos probeer om te implementeer was net gebreek. Onthou dat die ruil-funksie, as ons net verklaar A en B as SY, ons het suksesvol ruil die twee veranderlikes binne ruil net soos met die melk en PB, maar sodra swap teruggekeer, wat was die uitslag met betrekking x en y, die oorspronklike waardes? Niks nie. Ja. Niks gebeur daardie tyd, want swaps verander net sy plaaslike kopieë, wat is om te sê, al hierdie tyd, wanneer ons het is verby in argumente funksies, ons is net verby afskrifte van daardie argumente. Wat jy kan doen met dit alles wat jy wil met hulle, maar hulle gaan nie het uitwerking op die oorspronklike waardes. So dit is problematies as jy wil 'n funksie soos scanf het in die lewe, wie se doel is om te scan insette van die gebruiker se vanaf die sleutelbord en dan in die spasies in te vul, om so te spreek, dit is, gee 'n veranderlike soos x 'n waarde, want as ek net slaag x om scanf, as jy die logika van verlede oorweeg week, kan scanf doen wat dit wil met 'n afskrif van x, maar dit kon nie permanent x verander tensy ons gee scanf n skat kaart, om so te praat, waar x dui die plek, waardeur Ons slaag in die adres van x sodat scanf kan daar en eintlik verandering gaan die waarde van x. En so ja, al dat hierdie program nie en maak ek scanf 0, in my bron 5m gids, maak scanf 0, dot streep scanf, nommer asseblief 50, dankie vir die 50. 

So dit is nie al wat interessant, maar wat wel gebeur is dat so gou as ek roep scanf hier, die waarde van x word permanent verander. Nou, dit lyk mooi en goed, en in werklikheid, is dit lyk asof ons nie regtig nodig die CS50 biblioteek by al nie. Byvoorbeeld, laat loop Dit is hier weer. Laat my heropen dit vir 'n tweede. Kom ons probeer 'n aantal asseblief en in plaas van sê 50 soos tevore, laat ons net sê nie. OK, dit is 'n bietjie vreemd. OK. En net 'n paar nonsens hier. So dit lyk nie hanteer foutiewe situasies. So moet ons begin minimaal voeg 'n paar foute kontrole om seker te maak dat die gebruiker getik in 'n werklike nommer soos 50, want blykbaar tik woorde nie opgespoor as problematies, maar dit moet seker wees. 

Kom ons kyk na hierdie weergawe nou dat die my poging om reimplement GetString. As scanf het dit alles funksie gebou in, Daarom het ons rondspeel met hierdie opleiding wiele soos GetString? Wel, hier is dalk my eie eenvoudige weergawe van GetString waardeur 'n week gelede, kan ek gesê het, gee my 'n string en noem dit buffer. Vandag, ek gaan net begin sê char ster wat, onthou, dit is net sinoniem. Dit lyk vreesaanjaend, maar dit is presies dieselfde ding. So gee my 'n veranderlike genoem buffer wat gaan om 'n string te slaan, vertel die gebruiker string asseblief, en dan, net soos voorheen, Kom ons probeer om hierdie les te leen scanf % s hierdie tyd en dan slaag in buffer. Nou, 'n vinnige gesonde verstand tjek. Hoekom ek sê nie ampersand buffer hierdie tyd? Aflei uit die vorige voorbeeld. GEHOOR: Char ster is 'n wyser. David Malan: Presies, want hierdie keer, char star is reeds 'n wyser, 'n adres, per definisie van daardie sterre daar te wees. En as scanf verwag 'n adres, is dit voldoende om te slaag in net buffer. Ek het nie nodig om ampersand buffer sê. Vir die nuuskierige, kan jy iets soos dit te doen. Dit sou verskillende betekenis hê. Dit sou 'n wyser gee jou om 'n wyser, wat eintlik 'n geldige ding in C nie, maar vir nou, laat ons hou dit eenvoudig en hou die storie konsekwent. Ek gaan net om in te slaag buffer en dit is korrek. Die probleem is egter hiervan. Laat my gaan voort en hardloop hierdie program na die opstel van dit. Maak scanf 1. Damn, my samesteller se my fout vang. Gee my 'n sekonde. Klang. Kom ons sê scanf-1.c. OK. Daar gaan ons. Ek het dit nodig. CS50 ID het verskeie konfigurasie-instellings dat jy beskerm teen jouself. Ek nodig het om diegene wat deur afskakel hardloop klang hand hierdie tyd. So string asseblief. Ek gaan om voort te gaan en tik my gunsteling hello world. OK, null. Dit is nie wat ek getik het. So dit is 'n aanduiding van iets verkeerd. Laat my gaan voort en tik in 'n baie lang tou. Dankie vir die nul en ek weet nie as ek gaan in staat wees om dit te crash. Kom ons probeer 'n bietjie kopie plak en kyk of dit help. Plak net 'n baie van hierdie. Dit is beslis 'n groter string as gewoonlik. Laat ons net regtig skryf dit. Geen. Vervloek Dit. Beveel nie gevind nie. So dit is nie verband hou. Dit is omdat ek geplak 'n paar slegte karakters, maar dit blyk nie gaan om te werk. 

Kom ons probeer hierdie keer meer nie, want dit is meer pret as ons eintlik crash dit. Kom ons hierdie tipe en nou, ek is gaan 'n baie lang string kopieer En nou, laat ons kyk of ons kan hierdie ding crash. Sien ek uitgelaat ruimtes en nuwe lyne en kommapunte en al funky karakters. Betree. En nou het die netwerk is net wat stadig. Ek hou af Command-V te lank, duidelik. Vervloek Dit! Beveel nie gevind nie. 

OK. Wel, die punt is nietemin die volgende. So, wat is eintlik gaan met hierdie verklaring van char star buffer op die lyn 16? So, wat kry ek wanneer Ek verklaar 'n wyser? Al wat ek kry is 'n vier byte waarde genoem buffer, maar wat is binnekant van dit op die oomblik? Dit is net 'n paar vullis waarde. Omdat enige tyd wat jy verklaar 'n veranderlike in C, dit is net 'n paar vullis waarde en ons is besig om te reis oor hierdie werklikheid. Nou, wanneer ek sê scanf, na hierdie adres en sit ongeag die gebruiker in. As die gebruiker in hallo wêreld, wel, waar kan ek dit? Buffer is 'n gemors waarde. 

So dit is soort van soos 'n pyl dit is wys wie weet waar. Miskien is dit wys hier in my geheue. En so wanneer die gebruiker tipes in hello world, die program probeer om die plaas string hello world backslash 0 in daardie deel van die geheue. Maar met 'n hoë waarskynlikheid, maar duidelik nie 100% waarskynlikheid, die rekenaar gaan dan crash die program, want dit is nie geheue Ek moet toegelaat word om aan te raak. So in kort, hierdie program is gebrekkig vir presies daardie rede. Ek is fundamenteel nie wat doen? Watter stappe het Ek weggelaat, net soos ons weggelaat met die eerste voorbeeld Binky se? Ja? 

GEHOOR: toekenning Memory? 

David Malan: toekenning Memory. Ek het nie eintlik toegeken 'n geheue vir daardie string. So kan ons dit regmaak in 'n paar van die maniere. Een, kan ons dit eenvoudig te hou en in die feit, nou is jy gaan om te begin om 'n vervaging sien van die lyne tussen wat 'n skikking is, wat 'n string is, wat 'n char ster is, wat 'n verskeidenheid van karakters is. Hier is 'n tweede voorbeeld waarby snare en kennis al wat ek gedoen het op die lyn 16 is, in plaas van sê dat buffer gaan 'n kar wees star, 'n verwysing na 'n stuk van die geheue, Ek gaan baie proaktief te gee myself 'n buffer vir 16 karakters, en in die feit, as jy vertroud is met die term buffer, waarskynlik van die wêreld van die video's, waar 'n video is buffering, buffering, buffer. Wel, wat is hier die verband? Wel, Binne YouTube en binnekant van die video spelers algemeen is 'n skikking dit is groter as 16. Dit mag dalk 'n verskeidenheid van grootte een megabyte, miskien 10 megagrepe, en in daardie reeks nie jou browser laai 'n hele klomp van grepe, 'n hele klomp van die MB video, en die video-speler, YouTube se of wie se begin lees van die grepe uit die skikking, en enige tyd wat jy sien die woord buffering, buffering, dit beteken dat die speler het gekry om die einde van die skikking. Die netwerk is so stadig dat dit nie hervul die skikking met meer grepe en so is jy uit stukkies te vertoon aan die gebruiker. 

So buffer is 'n gepaste term hier in daardie dit is net 'n skikking, 'n stuk van die geheue. En dit sal dit regmaak omdat dit blyk dat jy skikkings kan hanteer asof hulle adresse, selfs al buffer is net 'n simbool, dit is 'n volgorde van die karakters, buffer, dit is nuttig vir my, die programmeerder, jy kan sy naam om te slaag asof dit 'n wyser, asof dit was die adres van 'n stuk van die geheue vir 16 karakters. So dit is om te sê, ek kan slaag die scanf presies wat die woord en so nou, as ek hierdie program, maak scanf 2, dot streep scanf 2, en tik in hello world, Gee dat time-- 

Hmm, wat gebeur? String asseblief. Wat het ek verkeerd gedoen? Hello world, buffer. Hello Wêreld. Ag, ek weet wat dit doen. OK. So is dit te lees totdat die eerste ruimte. So laat kul net vir 'n oomblik en sê ek wou net om iets te tik baie lang soos hierdie is 'n lang vonnis dit is een, twee, drie, vier, vyf, ses, sewe, agt, nege, 10, 11, 12, 13, 14, 15, 16. OK. Dit is inderdaad 'n lang sin. So hierdie sin is langer as 16 karakters en so toe ek druk Enter, wat gaan gebeur? Wel, in hierdie geval van die storie, het ek verklaar buffer om eintlik 'n verskeidenheid met 16 karakters gereed om te gaan. So een, twee, drie, vier, vyf, ses, sewe, agt, nege, 10, 11, 12, 13, 14, 15, 16. So 16 karakters, en nou, toe ek lees iets soos hierdie is 'n lang vonnis, wat gaan gebeur is ek gaan om te lees in hierdie is 'n lang S-E-N-T-E-N-C-E, sin. 

So dit is doelbewus 'n slegte ding wat ek hou skryf buite die grense van my skikking, buite die grense van my buffer. Ek kon kry gelukkig en die program sal aanhou loop en nie om nie, maar oor die algemeen, hierdie sal inderdaad my program crash, en dit is 'n fout in my Code Die oomblik toe ek stap buite die grense van daardie skikking, want ek weet nie of dit is noodwendig gaan crash of as ek net gaan om gelukkig te kry. So dit is problematies, want in hierdie geval, lyk dit vir werk en laat ons versoek lot hier, selfs al die IDE lyk nogal 'n bietjie duld of-- 

Daar gaan ons. Ten slotte. So ek is die enigste een wat dit kan sien nie. So ek het net 'n baie pret tik 'n baie lang werklike frase dat dit beslis oorskry 16 grepe, want ek getik in hierdie mal lang multi-line frase, en dan sien wat daar gebeur het. Die program het probeer om dit te druk en het daarna 'n segmentering skuld en segmentering foute is wanneer iets soos dit gebeur en die bedryfstelsel sê nee, kan dit nie geheue raak. Ons gaan doodmaak die program heeltemal. 

So dit lyk problematies. Ek het die program waarvolgens verbeter ten minste 'n paar geheue, maar dit wil voorkom asof beperk die funksie GetString te kry snare van 'n paar beperkte lengte 16. So as jy wil om langer te ondersteun sinne as 16 karakters, wat doen jy? Wel, jy kan verhoog die grootte van die buffer 32 of wat lyk soort van kort. Hoekom het ons nie net maak dit 1000, maar stoot terug. Wat is die reaksie van intuïtief net hierdie probleem te vermy deur my buffer groter, soos 1000 karakters? Deur die implementering van GetString hierdie manier. Wat is goed of sleg hier? Ja? GEHOOR: As jy bind 'n baie van ruimte en jy dit nie gebruik nie, dan kan jy nie meer inzetten dat die ruimte. David Malan: Absoluut. Dit is verkwistende sover as jy dit nie doen nie werklik nodig 900 van die grepe en tog is jy vra vir 1000 in totaal in elk geval, jy net beslag meer geheue op die gebruiker se rekenaar as jy nodig het om, en na alles, 'n paar van jy reeds teëgekom in die lewe dat wanneer jy hardloop baie programme en hulle is op die eet van baie van die geheue, Dit kan eintlik prestasie impak en die gebruiker se ervaring op die rekenaar. So dit is soort van 'n lui oplossing vir seker, en omgekeerd, dit is nie net verkwistende, wat die probleem nog steeds, selfs as ek my buffer 1000? Ja? 

GEHOOR: Die string is lengte 1001. David Malan: Presies. As jou string is lengte 1001, jy presies dieselfde probleem, en deur my argument, sou ek net maak dit 2000 dan maar jy weet nie in bevorder hoe groot dit moet wees, en tog, ek het nie my program saamstel voordat laat mense gebruik en aflaai Dit. So dit is presies die soort van dinge wat die CS50 biblioteek drieë om ons te help met ons sal net oogopslag op sommige van die onderliggende implementering hier, maar dit is CS50 dot C. Dit is die lêer wat al op CS50 IDE al hierdie weke dat jy het al met behulp. Dit is pre-saamgestel en jy het outomaties gebruik dit uit die aard van die wat stamp L CS50 vlag met klang, maar as ek rol af deur al hierdie funksies, hier is GetString, en net om jou 'n gee smaak van wat aangaan, Kom ons neem 'n vinnige blik op die relatiewe kompleksiteit. Dit is nie 'n super lang funksie, maar ons het nie het al hard oor te dink hoe om te gaan oor die manier waarop snare. 

So hier is my buffer en ek blykbaar inisialiseer dit null. Dit, natuurlik, is die dieselfde as char ster maar ek het besluit in die implementering van die CS50 biblioteek dat as ons gaan heeltemal dinamiese, Ek weet nie vooraf hoe groot van 'n string gebruikers gaan wil te kry. So ek gaan om te begin met net 'n leë string en ek gaan om te bou aan soveel geheue as ek nodig het om die gebruiker string pas en as ek het nie genoeg nie, ek gaan om te vra die bedryfstelsel vir meer geheue. Ek gaan om hul string beweeg in 'n groter deel van die geheue en ek gaan om vry te stel of te bevry die onvoldoende groot deel van die geheue en ons is maar net gaan hierdie iteratief te doen. 

So 'n vinnige blik, hier is net 'n veranderlike waarmee ek gaan om tred te hou van die kapasiteit van my buffer. Hoeveel grepe kan ek inpas? Hier is 'n veranderlike N met wat ek gaan hou hou van hoeveel bytes is eintlik in die buffer of dat die gebruiker getik het. As jy nie hierdie gesien het nie, moet jy kan spesifiseer dat 'n veranderlike soos 'n int is unsigned, wat soos die naam aandui, beteken dit is nie-negatief is, en hoekom sou Ek ooit wil spesifiseer pla dat 'n int is nie net 'n int, maar dit is 'n ongetekende int? Dit is 'n nie-negatiewe int. Wat beteken die [onhoorbaar] beteken? 

GEHOOR: Dit is die beskrywing van 'n bedrag geheue wat kan wees [onhoorbaar]. 

David Malan: Ja. So as ek sê unsigned, dit is eintlik gee jou 'n bietjie ekstra geheue en dit lyk soort van dom, maar as jy het 'n bietjie van 'n addisionele geheue, wat beteken dat jy twee keer soveel waardes wat jy kan verteenwoordig, want dit kan 'n 0 of 'n 1. So by verstek, kan 'n int rofweg negatiewe 2000000000 al die pad tot positiewe 2000000000. Dit is 'n groot reekse, maar dit is nog steeds soort van verkwistende as jy net omgee groottes, wat net intuïtief moet nie-negatief wees of positief of 0, goed dan, hoekom is jy mors 2000000000 moontlike waardes vir negatiewe getalle As jy nog nooit gaan om dit te gebruik? So sê unsigned, nou is my int kan tussen 0 en ongeveer 4 miljard. 

So hier is net 'n int C vir redes ons sal nie nou net as kry in waarom dit is 'n int plaas van 'n kar nie, maar hier is die kern van wat aangaan op, en 'n paar van julle kan word met behulp van, byvoorbeeld, die fgetc funksie selfs in PSet vier of daarna, sal ons dit sien weer in die probleem stel vyf fgetc is lekker, want soos die naam soort, soort van arcanely aandui, dit is 'n funksie wat kry 'n karakter en so, wat is fundamenteel verskil oor wat ons doen in GetString is ons nie die gebruik van scanf op dieselfde manier. Ons is net kruip saam stap-vir-stap oor alles wat die gebruiker getik in, want ons kan altyd Ken EEN char, en so kan ons altyd veilig kyk na een kar op 'n tyd, en die magie begin hier gebeur nie. Ek gaan om af te gaan na die middel van hierdie funksie net kortliks hierdie funksie. Baie soos daar is 'n malloc funksie, daar is 'n realloc funksie waar realloc Kom jy 'n stuk van die geheue hertoeken en maak dit groter of kleiner. So lang storie kort en met 'n golf van my hand vir vandag, weet dat wat GetString doen, is dit soort van mettertyd groei of krimp die buffer van die gebruiker tipes in sy of haar string. 

So as die gebruiker 'n kort string, hierdie kode net genoeg ken geheue om die string te pas. As die gebruiker hou tik soos ek gedoen het dit weer en weer en weer, goed, indien die buffer se aanvanklik hierdie groot en die program besef, om wag 'n minuut, ek is uit die ruimte, dit gaan verdubbel die grootte van die buffer en dan dubbel die grootte van die buffer en die kode wat die verdubbeling doen, As ons kyk na dit hier, dis Net hierdie slim one-liner. Jy kan nie hierdie sintaksis gesien voor, maar as jy sê star gelykes, dit is dieselfde ding as sê kapasiteit keer 2. So dit hou net verdubbel die kapasiteit van die buffer en dan vertel realloc te gee self wat veel meer geheue. 

Nou, as 'n eenkant, is daar ander funksies in hier dat ons nie sal kyk na enige detail anders as om te wys in GetInt, ons gebruik GetString in GetInt. Ons maak seker dat dit nie null, wat, onthou, is die spesiale waarde wat beteken iets verkeerd geloop het. Ons is uit die geheue. Beter check vir daardie. En ons terugkeer 'n brandwag waarde. Maar ek sal stel om die kommentaar te waarom en dan gebruik ons ​​hierdie neef van scanf genoem sscanf en dit blyk dat sscanf, of string scanf, Kom jy 'n blik op die lyn te neem dat die gebruiker in getik het en jou laat ontleed dit in wese en wat ek is doen hier Ek sê sscanf, ontleed ongeag die gebruiker getik in en maak seker% i, daar is 'n heelgetal in dit, en ons sal nie kry in vandag presies die rede waarom daar is ook 'n% c hier nie, maar dat in 'n neutedop laat ons op te spoor indien die gebruiker getik iets valse na die nommer. So die rede dat GetInt en GetString jou vertel om weer te probeer, weer probeer, probeer weer is as gevolg van al wat die kode wat ons geskryf het, Dit is soort van kyk na die invoer van die gebruiker se om seker te maak dit is heeltemal numeriese of dit is 'n werklike swaai punt waarde of die wil, afhangende van watter waarde funksioneer wat jy gebruik. 

Sjoe. OK. Dit was 'n mondvol maar die punt hier is dat die rede waarom ons moes diegene opleiding wiele op is omdat op die laagste vlak, daar is net so baie dinge wat kan verkeerd gaan dat ons wou om preemptively hanteer daardie dinge beslis in die vroegste weke van die klas, maar nou met PSet vier en vyf en PSet buite sal jy sien dat dit is meer aan jy maar ook jy meer in staat van die oplossing van die soort probleme jouself. Enige vrae oor GetString of GetInt? Ja? 

GEHOOR: Hoekom sou jy dubbel die kapasiteit van die buffer eerder as om net te verhoog dit deur die presiese bedrag? 

David Malan: Goeie vraag. Hoekom sal ons dubbel die kapasiteit van die buffer in teenstelling net om dit te verhoog deur sommige konstante waarde? Dit was 'n ontwerp besluit. Ons het net besluit dat omdat dit geneig is om wees 'n bietjie duur time-wyse te vra die bedryfstelsel vir die geheue, het ons nie wil eindig om in 'n situasie vir die groot snare dat ons vra weer en weer die OS en weer en weer in vinnige opvolging vir die geheue. So het ons net besluit, ietwat arbitrêr maar ons hoop redelik, dat jy weet wat, laat ons probeer om onsself voor te kry en hou net verdubbel dit so dat ons die bedrag van die tye te verminder ons moet malloc bel of realloc, maar 'n totale oordeel noem in die afwesigheid van die wete wat gebruikers dalk wil om te tik in. Beide maniere kan wees onseker. Waarskynlik goed. 

So laat ons neem 'n blik op 'n paar ander newe-effekte van die geheue, dinge wat verkeerd kan gaan en gereedskap wat jy kan gebruik om hierdie soort van foute te vang. Dit blyk uit almal van julle, selfs al check50 het nie gesê jy soveel, is skryf karretjie kode sedert week een, selfs al check50 toetse geslaag het, en selfs as jy en jou TF super vol vertroue dat jou kode werk soos bedoel. Jou kode karretjie is of gebrekkig dat julle almal, in die gebruik van die CS50 biblioteek, is lekkende geheue. Jy het gevra die bedryfstelsel vir die geheue in die meeste van die programme jy geskryf het, maar jy het nooit werklik gegee dit terug. Jy het GetString genoem en GetInt en GetFloat, maar met GetString, jy het nooit unGetString of Gee genoem String Terug of die wil, maar ons het gesien dat GetString bewillig geheue by wyse van malloc of hierdie funksie realloc, wat net baie soortgelyk in die gees, en tog, ons het nie vra die bedryfstelsel vir geheue en geheue weer en weer maar nooit gee dit terug. 

Nou, as 'n eenkant, dit blyk dat wanneer 'n program verlaat, al die geheue outomaties bevry. So dit is nie 'n groot deal nie. Dit gaan nie om die breek IDE of stadige dinge af, maar wanneer programme te doen algemeen lek geheue en hulle is hardloop vir 'n lang tyd. As jy nog ooit gesien het die dom bietjie strand bal in Mac OS of die uurglas op Windows waar dit is soort van stadiger of dink of denke of net regtig begin te stadig om 'n crawl, dit baie moontlik kan wees die gevolg van 'n geheue lek. Die programmeerders wat geskryf het die sagteware wat jy gebruik vra die bedryfstelsel vir geheue elke paar minute, elke uur. Maar as jy die bestuur van die sagteware, selfs al is dit geminimaliseer in jou rekenaar vir ure of dae op die einde, jy kan vra vir meer en meer geheue en nooit eintlik gebruik dit en so jou kode kan wees, of programme kan lek geheue, en as jy begin om geheue lek, is daar minder geheue vir ander programme, en die effek is om stadig alles neer. 

Nou, dit is by verre een van die mees gruwelike programme sal jy geleenthede uit te voer in CS50 sover as sy produksie is selfs meer esoteriese as klang of maak of enige van die opdrag line programme ons reeds hardloop, maar Gelukkig, ingebed in sy produksie is 'n paar super nuttige wenke wat sal nuttig óf vir PSet vier wees of beslis PSet vyf. So valgrind is 'n instrument wat gebruik kan word om te kyk vir die geheue lekkasies in jou program. Dit is relatief maklik om te hardloop. Jy hardloop valgrind en dan, selfs al is dit 'n bietjie verbose, Dash Dash lek tjek gelyk vol, en dan dot streep en die naam van jou program. So valgrind sal dan jou program loop en aan die einde van jou program hardloop voordat dit gesluit en gee jou nog n vinnige, dit gaan om te analiseer jou program, terwyl dit loop en vertel het jy lek 'n geheue en nog beter, het jy die geheue raak wat nie aan jou behoort? Dit kan nie alles vang, maar dit is redelik goed op te vang die meeste dinge. 

So hier is 'n voorbeeld van my wat run hierdie program, met run valgrind, op 'n program genaamd geheue, en ek gaan om die lyne wat beklemtoon uiteindelik van belang is vir ons. So is daar nog meer afleiding dat ek van die skyfie het verwyder. Maar laat ons sien net wat hierdie program in staat is om ons te vertel. Dit is in staat om van ons te vertel dinge soos ongeldig skryf van grootte 4. Met ander woorde, as jy die geheue te raak, spesifiek 4 grepe van die geheue dat jy nie moet hê, valgrind kan jou vertel dat. Ongeldig skryf van grootte 4. Jy aangeraak vier grepe dat jy nie moet hê. Waar het jy dit doen? Dit is die skoonheid. Memory dot c lyn 21 is waar jy verfrommeld en dit is hoekom dit nuttig. Baie soos GDB, kan dit help wys jou by die werklike fout. 

Nou, hierdie een is 'n bietjie meer verbose, indien nie verwarrend. 40 grepe in 1 blokke is beslis verlore in die verlies rekord 1 van 1. Wat beteken dit? Wel, dit beteken net jy gevra 40 grepe en jy nooit het dit terug. Jy genoem malloc of julle geroep GetString en die bedryfstelsel het jy 40 grepe, maar jy nooit bevry of vrygestel wat die geheue, en om eerlik te wees, het ons nooit wys hoe om terug te gee geheue. Blyk daar is 'n super eenvoudige funksie genoem gratis. Neem een ​​argument, die ding jy wil bevry of terug te gee, maar 40 grepe, blykbaar, in hierdie program verlore geraak het op reël 20 geheue dot c. 

So laat ons sien hierdie program. Dit is super nutteloos. Dit demonstreer net hierdie spesifieke fout. So laat ons neem 'n blik. Hier is die hoof en belangrikste, kennisgewing, oproepe 'n funksie genoem f en dan terugkeer. So nie al wat interessant. Wat beteken f doen? Sien ek het nie die moeite met 'n prototipe. Ek wou die kode hou as minimale as moontlik. So ek het f bo hoof- en dit is goed, seker, vir 'n kort programme soos hierdie. So f niks terug te keer en doen niks te neem nie, maar dit doen nie. Dit verklaar, baie soos in die Binky byvoorbeeld 'n wyser genoem x wat gaan na die adres van 'n int stoor. So wat is die linkerkant. In Engels, wat is die regs doen? Iemand? Wat doen dit vir ons? Ja? 

GEHOOR: [onhoorbaar] keer die grootte van 'n int wat 10 keer [onhoorbaar] David Malan: Goeie en laat my op te som. So ken genoeg ruimte vir 10 heelgetalle of 10, wat is die grootte van 'n int, dit is vier grepe, so 10 keer 4 is 40 sodat regterkant dat ek gemerkte is gee my 40 grepe en stoor die adres van die eerste byte in x. En nou laastens, en hier is waar hierdie program is karretjie, wat is verkeerd met lyn 21 wat gebaseer is op daardie logika? Wat is verkeerd met 'n lyn 21? Ja? GEHOOR: Jy kan nie indeks in x [onhoorbaar]. David Malan: Ja. Ek moet nie indeks in x soos dit. So sintakties, dit is OK. Wat is lekker is, baie soos jy kan die naam van 'n skikking te behandel asof dit 'n wyser, insgelyks kan jy 'n wyser te behandel asof dit 'n skikking, en sodat ek kan sintakties sê x bracket iets x bracket i, maar die 10 is problematies. Hoekom? 

GEHOOR: Want dit is nie binne. 

David Malan: Dit is nie binne-in dat deel van die geheue. Wat is die grootste waarde wat ek moet word om in daardie vierkantige hakies? 9, 0 tot 9. As gevolg van nul kruip. So 0 tot 9 sal goed wees. Bracket 10 is nie goed nie en maar onthou al is, elke keer Dit lyk asof ek probeer om CS50 IDE maak crash deur te tik in valse waardes, dit nie altyd saam, en inderdaad, jy dikwels kry gelukkig net omdat die bedryfstelsel nie sien dat jy ooit so iets slaag sommige stuk van die geheue, omdat jy gebly binne tegnies jou segment, maar meer oor dit in 'n bedryfstelsels klas, en so iets soos hierdie kon baie maklik gaan ongemerk. Jou program gaan nooit crash konsekwent maar miskien een keer in 'n rukkie. 

En so kom ons probeer valgrind Op hierdie, en hier is waar ons sal oorweldig kry deur die uitset oomblik. So maak geheue valgrind lek tjek gelyk volle dot streep geheue. En hier is die rede waarom ek belowe dit sou oorweldig. Hier is wat valgrind, hier is wat 'n programmeerder, 'n paar jaar gelede- besluit om dit 'n goeie idee sou wees vir die produksie te lyk. So laat sin maak van hierdie. So al die pad van die linker span vir geen goeie rede is die proses van die program ID ons net loop, die unieke identifiseerder vir die program het ons net gehardloop. Ons verwyder dat vanaf die skyfie, maar daar is 'n paar nuttige inligting in hier. 

Kom ons blaai tot die heel boonste. Hier is waar ons begin het. So dit is nie alles wat veel uitset. Hier is wat ongeldig skryf grootte 4 op die lyn 21. Wel, wat was line 21? Line 21 was presies hierdie en dit maak sin dat ek in geldiglik skryf 4 grepe omdat ek probeer om hierdie heelgetal sit, wat kan enigiets wees, dit gebeur net te wees nul, maar ek probeer om dit te sit op 'n plek wat behoort nie aan my nie. Verder, hier, 40 grepe in een blokke is beslis verlore in 'n rekordtyd 1. Dit is omdat wanneer ek noem malloc hier, ek het nooit werklik vry om die geheue. 

So hoe kan ons dit regmaak? Laat my gaan voort en 'n bietjie veiliger en doen 9 daar en laat my hier gratis x. Dit is die nuwe funksie vir vandag. As ek nou tik maak geheue dot streep laat hardloop weer valgrind op dit, maksimeer my venster en druk Enter. Nou, dit is goed. Hulle begrawe die goeie nuus in al hierdie uitset. Alle hoop blokke was vry. Ons sal terug na wat die hoop kom is, maar geen lekkasies is moontlik. So dit is net nog 'n instrument vir jou tool kit waarmee jy kan begin om vind nou foute soos dit. 

Maar laat ons sien wat meer kan hier verkeerd gaan. Kom ons oorgang nou eintlik 'n probleem oplos. As 'n eenkant, as dit sal 'n verlig bietjie van verwarring of spanning, dit is nou snaaks. Ja. Dit is redelik goed. Omdat pointers is adresse en adresse is oor die algemeen deur konvensie geskryf met heksadesimale. Ha, ha, dit is nou snaaks. Anyhow, so laat nou eintlik 'n probleem op te los. Dit het super was, super lae-vlak tot dusver, en ons kan werklik nuttig te doen dinge met hierdie lae-vlak besonderhede. 

Sodat ons 'n paar weke bekend gestel gelede het die idee van 'n skikking. 'N skikking was lekker, want dit is moeilik om skoon te maak ons ​​kode want as ons wou 'n skrywe program met verskeie studente of veelvuldige name en huise en slaapsale en kolleges en al van dat, kon ons alles meer te stoor skoon binnekant van 'n skikking. Maar voor een nadeel van 'n skikking wat tot dusver. Selfs as jy dit nie self gely het in 'n program, net instinktief, Wat is 'n slegte ding oor 'n skikking, miskien? Ek hoor dat sommige geruise. GEHOOR: Dit is moeilik om die grootte te verander. David Malan: Dit is moeilik om die grootte te verander. Jy kan die grootte verander nie van 'n skikking, in werklikheid, per se in C. Jy kan 'n skikking te ken, beweeg alles van die ou een in die nuwe, en nou het 'n paar ekstra ruimte, maar dit is nie soos 'n taal soos Java of Python of enige aantal ander tale waarmee sommige van julle vertroud te wees waar jy kan net bly die toevoeging van dinge vervelens tot die einde van 'n skikking. Wanneer jy 'n verskeidenheid van grootte 6, wat die grootte is, en so baie soos die idee vroeër 'n buffer van 'n sekere grootte, jy het om te raai uit die hek watter grootte jy wil hê dit moet wees? As jy dink te groot, jy mors ruimte. As jy te klein dink jy kan daardie data stoor nie, ten minste sonder 'n baie meer werk. 

So vandag, te danke aan wysers, ons kan begin stik saam ons eie persoonlike data strukture, en in Trouens, hier is iets wat lyk 'n bietjie meer kriptiese met die eerste oogopslag, maar dit is wat ons noem 'n gekoppelde sal lys, en sy naam van 'n opsomming van die soort Dit. Dit is 'n lys van die nommers, of in hierdie geval, 'n lys van getalle, maar dit kan 'n lys van alles wees nie, maar dit gekoppel saam deur middel van pyle, en net 'n raaiskoot te neem met wat tegniek gaan ons in staat wees om om saam te steek, soort van soos springmielies met 'n draad, 'n geskakelde lyste reghoeke hier? Die getalle? Wat is die taal funksie onderliggende? 

GEHOOR: 'n wyser. 

David Malan: 'n wyser. So elkeen van hierdie pyle hier verteenwoordig 'n wyser of net 'n adres. So met ander woorde, as ek wil om 'n lys van die nommers te slaan, Ek kan nie net stoor dit as ek wil die vermoë om te groei en krimp my data struktuur in 'n skikking. So ek moet 'n bietjie het meer gesofistikeerd, maar sien dat hierdie prentjie soort dui dat as jy net het bietjie drade die koppeling van alles, is waarskynlik nie so moeilik om plek te maak tussen twee van die reghoeke of twee van daardie nodusse, soos ons sal begin hulle roep, sit in 'n nuwe node, en dan met 'n paar nuwe draad, net sloot die drie nodes saam die eerste een, die laaste een, en die een dat jy net plaas in die middel. 

En inderdaad 'n geskakelde lys, anders 'n skikking, is dinamies. Dit kan groei en dit kan krimp en jy doen nie moet weet of omgee vooraf hoe veel data jy gaan word berging, maar dit blyk ons ​​het 'n klein om te wees versigtig wees oor hoe om dit te implementeer. So eers laat dink oor hoe ons te implementeer een van hierdie kleintjies reghoeke. Dit is maklik om 'n int implementeer. Jy sê net int N en dan jy 4 grepe vir 'n int, maar hoe kry ek 'n int, noem dit n, en dan 'n wyser, kom ons noem dit die volgende. Ons kon hierdie skakel dinge wat ons wil niks maar ek het 'n persoonlike data struktuur. Ja? 

GEHOOR: Ampersand [onhoorbaar]. 

David Malan: So ampersand ons sal gebruik om kry die adres van 'n node potensieel. Maar ons mekaar nodig kenmerk van C in orde my die vermoë om te skep gee hierdie gebruik reghoek, hierdie gewoonte veranderlike as jy wil, in die geheue. GEHOOR: 'n struct. David Malan: 'n struct. Onthou van verlede week, het ons ' struct, hierdie relatief eenvoudige navraag waarmee ons dinge soos hierdie te maak. C het nie kom met 'n data struktuur genaamd student. Dit kom met int en float en char en so, maar dit kom nie met student, maar ons kan 'n tipe student data te skep, 'n student struktuur, met hierdie sintaksis hier. En jy sal dit weer en weer te sien. So moenie bekommerd wees oor memorisering die sleutelwoorde, maar die term wat belangrik is, is Net die feit dat ons gesê struct en dan genoem ons student en binne van die student was 'n naam en 'n huis of 'n dorm of die wil. 

En so nou vandag, laat ons voor hierdie. Ek het 'n paar woorde bygevoeg, maar as ek wil hierdie reghoek dis implementeer het beide 'n int en 'n wyser, jy weet wat, ek is gaan 'n struct genoem node te verklaar. Ek is ook binnekant van dit, gaan om te sê dat 'n knoop, hierdie reghoek, het 'n int en ons sal dit noem N en dit het 'n volgende wyser. En dit is 'n bietjie verbose, maar as jy daaroor dink, die pyle wat in die prentjie was 'n oomblik gelede is van watter tipe data? Waar elkeen van die pyle wys om watter tipe data struktuur? Dit is nie wys net 'n int per se. Dit verwys na die hele ding reghoekige en dat vierkantige ding, het ons gesê, is 'n knoop genoem. En so het ons soort te rekursief hierdie so te definieer dat 'n knoop, sal ons sê, sal 'n int genoem N bevat en 'n wyser genoem volgende en die tipe data struktuur wat dat wyser punte is blykbaar gaan struct node wees. 

So dit is lastig verbose en net om pedanties wees, die rede waarom ons nie kan nie net dit sê, wat eerlik lyk 'n baie meer leesbaar, is omdat onthou dat C gelees dinge bo na onder, links na regs. Dit is nie totdat ons die kommapunt dat die navraag node werklik bestaan. So as ons wil hierdie soort van het sikliese verwysing binnekant van die data struktuur, ons het om dit te doen, waar ons sê struct node by die top, wat gee ons 'n langer manier om te beskryf hierdie ding, dan binnekant ons sê struct node, en dan op die heel laaste reël ons sê, alles reg, C, op die pad, net hierdie hele damn bel ding wat 'n node en stop gebruik van die term struct geheel en al. So dit is net soort van 'n sintaktiese truuk wat uiteindelik laat ons skep iets wat lyk presies soos hierdie. 

So as ons nou aanvaar ons kan implementeer hierdie ding in C, hoe kan ons eintlik begin dwars dit? Wel, in werklikheid, al wat ons moet doen, is Itereer van links na regs en net soort voeg nodes of nodes verwyder of soek vir dinge waar ons wil, maar om dit te doen, laat ons gaan voort en maak dinge 'n bietjie meer real, want dit het super lae-vlak tot dusver. Sou iemand letterlik wil eerste te wees? OK. Kom up. Wat is jou naam? 

DAVID: David. David Malan: David. Bly te kenne. Ek ook. Alles reg. En ons moet 'n nommer 9. Nie so goed soos die eerste, miskien. OK, nommer 9. 'N Aantal 17, asseblief. Laat my terug te gaan 'n bietjie verder. Nommer 22, asseblief, en hoe oor verder terug as ek hande kan sien met al die ligte of geen. Iemand wat net daar vrywillig. Wil jy om te kom? Jou voorarm is geweld opgaan. OK, 17. 22. 26 neerdaal. Sou enige iemand anders wil forcefully-- Kom up. 'N werklike vrywilliger. 

So baie vinnig, as julle ouens kan reël julle net soos die nodes op die skerm. Dankie. En jy sal wees 26. Alle regte en vinnige inleidings. So ek is David en jy is ook? DAVID: David. David Malan: En jy is? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. David Malan: Taylor. Uitstekend. So dit is ons vrywilligers vir vandag en gaan voort en skuif 'n bietjie op die manier, en net voort te gaan en hou hou jou nommers as jy is of jou eerste teken en die gebruik van jou linkerhand, gaan voort en net implementeer hierdie pyle, net sodat jou linkerhand is letterlik wys op alles wat jy behoort te wys op, en gee jouself 'n ruimte sodat kan ons visueel sien jou arms eintlik wys, en jy kan net wys soort van op die grond is goed. 

So hier het ons 'n geskakelde lys van een, twee, drie, vier, vyf nodes aanvanklik, en sien ons het hierdie spesiale wyser aan die begin wie se sleutel, want ons het om tred te hou van die hele lengte lys een of ander manier. Hierdie ouens, selfs al is hulle weg na regs, rug aan rug in die geheue, hulle kan eintlik enige plek wees in die geheue van die rekenaar. So hierdie ouens kan wees staan ​​op enige plek op die stadium en dit is goed, so lank as wat hulle is eintlik wys na mekaar maar om dinge te hou skoon en eenvoudig, sal ons hulle net teken links na regs soos hierdie, maar daar kon wees massiewe gapings tussen diegene nodes. 

Nou, as ek wil eintlik voeg 'n paar nuwe waarde, laat ons gaan voort en doen dit. Ons het 'n geleentheid nou na 'n ander node te kies. Sê laat begin met mallocing 55. Sal iemand omgee om malloc? OK, kom op op. Wat is jou naam? RAINBOW: Rainbow. David Malan: Rainbow? Alles reg. Malloc Rainbow. Kom up. So nou het ons onsself afvra algoritmies waar ons kan sit 55. So ons almal weet, natuurlik, waar sy waarskynlik behoort as ons probeer hierdie gesorteer te hou en as jy kan 'n mens neem ouens stap terug sodat ons val nie af nie die stadium, sou groot wees. So eintlik, Rainbow, begin hier met my omdat ons as die rekenaar nou kan slegs een veranderlike op 'n tyd. So as dit is die eerste knoop. Let hy is nie 'n knoop, hy is net 'n wyser, en dit is die rede waarom hy getrek te wees net die grootte van 'n wyser, nie een van daardie volle reghoeke. So ons gaan om te kyk na elke iterasie is 55 minder as 9? Geen. Is 55 minder as 17? Geen. Minder as 22? Minder as 26? Minder as 34? En so nou, natuurlik Rainbow behoort aan die einde. So duidelik wees, en wat was jou naam, Taylor? 

TAYLOR: Taylor. David Malan: So onder Taylor se linkerhand en Rainbow se hande hier, wie se hand moet wys na wat in bestel te voeg 55 in die lys? Wat moet ons doen? Ja? 

GEHOOR: hand Taylor se moet links wys. 

David Malan: Presies. So 'n knoop te voeg in die einde van die lys is eenvoudig omdat Taylor net het om te wys, in plaas van op die grond of ons sal dit noem nul, null is 'n soort van die afwesigheid van 'n wyser of 'n spesiale nul pointer, jy gaan wys met jou linker hand op Rainbow en dan Rainbow, Waar moet jou linkerhand hand waarskynlik wys? Down. Dit is nie goed as haar hand is 'n soort daarop te wys hier of soort van enige af watter manier. Wat oorweeg sou word 'n gemors waarde maar as sy wys na 'n bekende waarde, sal ons noem dit zero of null, dis OK want ons het 'n term wat in hierdie en ons weet die lys is nou afgehandel. 

So, wat is 'n ander relatief eenvoudige saak? Kan ons malloc 5? Kom up. Wat is jou naam? TIFFANY: Tiffany. David Malan: Ek is jammer? TIFFANY: Tiffany. David Malan: Tiffany. Alles reg. Tiffany is malloced met die waarde 5. Kom up. Hierdie een is relatief maklik ook, maar Kom ons kyk volgorde van bewerkings nou. Dit was redelik maklik met Taylor aan die einde. Nommer 5 is natuurlik minder as 9, en so het ons David, ons het Tiffany, en wat was jou naam? 

JAKE: Jake. 

David Malan: Jake. Tiffany, Jake, en Dawid. Wie se hand moet eerste opgedateer? Wat wil jy hier doen? Daar is 'n paar moontlike maniere, maar daar is ook een of meer verkeerde maniere. 

GEHOOR: Begin met linker. 

David Malan: Begin met die linker. Wie is hier die linker dan? GEHOOR: Eerste. 

David Malan: OK. So begin met die eerste en waar het jy wil werk David se hande te wees? GEHOOR: Teen die 5. David Malan: OK. So David, punt vyf of Tiffany hier, en nou? 

GEHOOR: Tiffany wys na die 9? David Malan: Perfect, behalwe Binky se hoof net soort van afgeval, reg? Want wat is verkeerd met hierdie foto letterlik? GEHOOR: Niks wys. David Malan: Niks is verwys na Jake nou. Ons het letterlik gelaat 9 en 17, en ons het letterlik uitgelek al hierdie geheue, want deur eerste opdatering David se hand, dit is fyn sover dit korrek wys op Tiffany nou, maar as niemand het die versiendheid om te wys op Jake, dan het ons verloor die geheel van die lys. So laat ongedaan te maak. So dit was 'n goeie ding om te reis oor maar laat regstel nou. Wat moet ons in die eerste plaas te doen? Ja? 

GEHOOR: Tiffany moet wys op die 9? David Malan: Ek kan nie kry wat naby aan jou. Wie moet wys op die 9? 

GEHOOR: Tiffany. 

David Malan: Alle reg. So moet Tiffany eerste punt op die 9. So Tiffany moet neem op 'n identiese waarde Dawid, wat blyk oorbodig vir 'n oomblik, maar dit is omdat nou fyn, tweede stap, kan ons Dawid se hand te werk om te wys op Tiffany, en dan as ons net soort van skoon dinge asof dit 'n soort van die lente-agtige, nou is dit 'n korrekte inplanting. So uitstekend. So nou het ons is amper daar. Kom ons voeg 'n laaste waarde soos die waarde 20. As ons 'n laaste vrywilliger kan malloc? Kom up. So hierdie een is 'n bietjie meer moeilik. Maar regtig, die kode ons skryf, al is dit mondelings, is net soos 'n klomp van as toestande nou, reg? Ons het 'n toestand seker te maak dat dit behoort aan die einde, miskien die begin. Ons moet 'n soort van lus om vind die plek in die middel. So laat doen met wat is jou naam? 

ERIC: Eric. 

David Malan: Eric? Eric. Bly te kenne. So het ons 20. Minder as vyf? Geen. Minder as nege? Geen. Minder as 17? Geen. OK. Hy hier hoort en julle name weer is? SUE: Sue. David Malan: Sue. ALEX: Alex. David Malan: Sue, Alex, en? ERIC: Eric. David Malan: Eric. Wie se hande nodig het om ontslae eerste opgedateer? 

GEHOOR: Eric. OK. So Eric se moet wys na waar? Op 22. Goed. Maar nou, wat is volgende? Sue kan dan wys op Eric en nou, as jy ouens net maak 'n paar kamer, wat is goed visueel, nou is ons het die invoeging gedoen. So laat nou oorweeg om 'n vraag, maar baie dankie vir ons vrywilligers. Baie goed gedoen. Jy kan hou dié, as jy wil. En ons het 'n pragtige afskeidsgeskenk as sou jy elke graag 'n stress bal. Laat my net te slaag dit neer. So, wat is die afhaal van hierdie? Dit lyk ongelooflik om te wees sover ons nou lei 'n alternatief vir 'n skikking wat nie so is beperk om 'n verskeidenheid van 'n vaste grootte. Hulle kan dinamiese groei. 

Maar net soos ons gesien het in weke verlede, nooit iets kry ons gratis, soos sekerlik is daar 'n trade-off hier. So met 'n onderstebo van 'n gekoppelde lys, is dit dinamika? Hierdie vermoë om te groei en eerlik, ons kon delete gedoen en ons kan krimp as dit nodig is. Wat is die prys ons betaal? Twee keer soveel ruimte, die eerste van alles. As jy kyk na die prentjie, nie meer ek stoor 'n lys van heelgetalle. Ek is 'n lys van die stoor heelgetalle plus wenke. So ek verdubbel die bedrag van die ruimte. Nou, miskien is dit nie so ' 'n groot deal 4 grepe, 8 grepe, maar dit kan beslis voeg vir groot datastelle. Wat is 'n ander nadeel? Ja? 

GEHOOR: Ons moet deurkruis hulle een-vir-een. David Malan: Ja. Ons moet hulle deurkruis een-vir-een. Jy weet wat, ons het vir hierdie super gerieflike kenmerk van vierkante bracket notasie, meer behoorlik bekend as ewetoeganklike, waar ons net kan spring om 'n individu element maar nou as ek nog my vrywilligers hier as ek wou die vind nommer 22, ek kan net nie spring na bracket iets iets. Ek het om te kyk oor die lys, baie soos ons soek voorbeelde lineêr, om die nommer 22 vind. So lyk ons ​​'n prys daar betaal het. Maar ons kan tog ander probleme op te los. 

In werklikheid, laat my stel net 'n paar van die visuele. So as jy af te gewees het Mather se Eetsaal onlangs, jy sal onthou dat hul stapels bak soos hierdie, ons geleen hierdie uit Annenberg voor die klas. So hierdie stapel bak, al is, verteenwoordigend eintlik van 'n rekenaar wetenskap data struktuur. Daar is 'n datastruktuur in Rekenaarwetenskap bekend as 'n stapel wat baie mooi leen hom presies hierdie visuele. So as elk van hierdie bak is nie 'n skinkbord maar soos 'n nommer en ek wou om getalle op te slaan, ek kan 'n mens af hier sit, en ek kon nog hier sit, en gaan voort stapel getalle op die top van mekaar, en wat is potensieel nuttige oor hierdie is dat die implikasie wat is van hierdie data struktuur? Watter getal kan ek trek uit eerste mees gerieflik? Die mees onlangs een put daar. 

So dit is wat ons sou noem in rekenaarwetenskap n LIFO data struktuur. Laaste in, eerste uit. En ons sal sien voor lank waarom wat kan nou nuttig, maar wees vir, Dink maar aan die eiendom. En dit is soort van dom as jy dink oor hoe die eetsaal doen dit. Elke keer as hulle skoon bak en sit die verste kinders bo-op, jy kan 'n voorheen skoon het maar uiteindelik baie vuil en stowwerige skinkbord aan die onderkant As jy nog nooit werklik kry aan die onderkant van die stapel, omdat jy net hou om die nuwe en die skones op die top van dit. Dieselfde ding kan gebeur in 'n supermark ook. As jy 'n vertoonkas melk en elke keer CVS of wie kry meer melk, jy net stoot die melk jy reeds aan die agterkant en jy sit die nuwes aan die voorkant, jy gaan 'n paar mooi nare het melk aan die einde van die data struktuur, want dit is altyd aan die onderkant of in dieselfde dit is altyd aan die agterkant. 

Maar daar is 'n ander manier om te dink oor voering data en byvoorbeeld hierdie. As jy een van daardie mense wat daarvan hou te reël om buite Apple winkels wanneer 'n nuwe produk kom uit, het jy waarskynlik is nie met behulp van 'n stapel data struktuur, want jy sou vervreem almal wat voering 'n paar nuwe speelding te koop. Inteendeel, is jy waarskynlik die gebruik van watter soort data struktuur of watter soort stelsel in die werklike wêreld? Hopelik is dit 'n lyn, of meer behoorlik of meer Britse-agtige, 'n tou. En dit blyk 'n tou is ook 'n data struktuur in rekenaarwetenskap, maar 'n tou het 'n baie verskillende eiendom. Dit is nie LIFO. Laaste in, eerste uit. God verbied. Dit is in plaas EIEU. Eerste in, eerste uit. En dit is 'n goeie ding vir regverdigheid wille beslis wanneer jy voering is up super vroeg in die oggend. As jy eerste daar kry, moet jy wil uitkom eerste sowel. 

En so al hierdie data strukture, toue en stapels en trosse van ander, blyk jy kan dink dit as net 'n skikking. Dit is 'n skikking, miskien 'n vaste grootte 4, maar dit wil soort van lekker wees as ons kon net hoop bak byna oneindig lank as ons het dat baie bak of nommers. So miskien wil ons gebruik 'n geskakelde lys hier maar die trade-off gaan wees potensieel dat ons meer geheue nodig het, neem 'n bietjie meer tyd, maar ons moenie die hoogte van die stapel nie beperk, baie soos Mather se vertoonkas kan beperk die grootte van die stapel, en so dit is ontwerp besluite of opsies wat beskikbaar is vir ons uiteindelik. So met hierdie data strukture, het ons begin sien nuwe bogrense potensieel op wat voorheen was super vinnig en waar ons sal laat af vandag en waar ons sal hoop om te kry is op Woensdag, sal ons begin om te kyk na 'n data struktuur wat laat ons soek deur data in log eindtyd weer. En ons sien dat, onthou, in week nul en een met binêre soek of deel en oorwin. Dit kom terug en nog beter, die heilige graal vir hierdie Woensdag sal wees om te kom met die data struktuur wat werklik loop of teoreties in konstante tyd waardeur dit maak nie saak hoeveel miljoene of biljoene dinge ons het in die data struktuur, sal dit neem ons konstante tyd, miskien 'n stap of twee stappe of 10 stappe, maar konstante getalle stappe om te soek deur die data-struktuur. Dit sal inderdaad die heilige graal wees maar meer oor dit op Woensdag. Sien ya dan. 

[Speel van musiek]