[Muziek] 

[VIDEO AFSPELEN] 

-Hij liegt. 

-Over wat? 

Ik weet het niet. 

-dus Wat weten we? 

-dat Op 09:15, Ray Santoya was bij de ATM. -Ja. Dus de vraag is, wat deed hij op 9:16? 

-Shooting De 9 millimeter naar iets. Misschien zag hij de sluipschutter. 

-of Werkte met hem. 

-Wacht. Ga terug een. 

-Wat zie je? 

-Breng Zijn gezicht volledig scherm. 

-zijn Bril. 

-Er Is een reflectie. 

-Het Is het Nuevitas honkbalteam. Dat is hun logo. 

-En Hij praat wie draagt ​​die jas. 

[END AFSPELEN] 

DAVID MALAN: Oké. Dit is CS50 en dit is een beetje meer van [onverstaanbaar] waarmee je bent ploeteren met een probleem stellen vier. Vandaag beginnen we met een beetje meer kijken diep op deze dingen genoemd pointers, die hoewel het een mooie geheimzinnige onderwerp, het blijkt dat het gaat de middelen zijn waarmee we kan beginnen met de bouw en assemblage veel meer geavanceerde programma's. Maar we deden het op de laatste woensdag door eerste manier van enkele claymation. Dus dit, herinneren, is Binky en we hem gebruikt om een ​​blik op een programma te nemen dat niet echt iets interessants, maar het deed onthullen een paar problemen. Dus om te beginnen vandaag, waarom hebben we niet lopen snel door een paar van deze stappen, proberen te destilleren in termen menselijke's precies wat er aan de hand hier en waarom dit is slecht, en ga dan verder en eigenlijk beginnen met de bouw iets met deze techniek? Dus deze waren de eerste twee lijnen in het programma en in termen van de leek, wat zijn deze twee lijnen aan het doen? Iemand die redelijk comfortabele met wat is verklaard op het scherm? Wat zijn die twee lijnen aan het doen? Het is niet zo anders dan één week, maar er is een aantal nieuwe speciaal symbool. Ja? Terug daar. 

PUBLIEK: declareren pointers? DAVID MALAN: weer zeggen? PUBLIEK: declareren pointers? DAVID MALAN: declareren pointers en laten we verfijnen het een beetje meer. PUBLIEK: [onverstaanbaar] mailadres x en dan y. DAVID MALAN: En dan pakken. Dus precies wat we doen is we verklaren twee variabelen. Deze variabelen echter gaan van het type int ster te zijn die Meer specifiek betekent ze gaan slaan het adres van een int, respectievelijk x en y. Nu zijn er nog waarden? Zijn er werkelijke adressen in deze twee variabelen op dit moment? Nee. Het is gewoon zogenaamde garbage waarden. Als je niet echt wijs een variabele, wat in het RAM was eerder gaat vullen met nullen en die deze beide variabelen. Maar we weten nog niet wat ze zijn en dat gaat de sleutel tot waarom Binky te zijn verloor zijn hoofd vorige week. 

Dus dit was de claymation incarnatie van deze waarbij je slechts twee variabelen, kleine ronde stukjes klei, welke variabelen opslaan, maar de ingepakt pijlen wijzen, ze zijn niet echt te wijzen overal bekend. Dus dan hadden we deze lijn, en dit nieuw was vorige week, malloc voor het geheugen toewijzing, dat is gewoon een mooie manier van het vertellen van het besturingssysteem, Linux of Mac OS of Windows, hey, geef me wat geheugen, en alles wat je hoeft te vertellen het besturingssysteem is wat wanneer vraagt ​​het voor het geheugen. Het gaat niet schelen wat je gaat doen, maar je moet naar de operatiekamer te vertellen systeem wat door middel van malloc. Ja? 

PUBLIEK: Hoeveel? DAVID MALAN: Hoeveel? Hoeveel in bytes, enzovoort, deze weer, een gekunsteld voorbeeld, is gewoon te zeggen, geef me de grootte van een int. Nu, de grootte van een int vier bytes of 32 bits. Dus dit is gewoon een manier van zeggen, hey, het besturingssysteem, geef me vier bytes van het geheugen die ik kan gebruiken tot mijn beschikking, en in het bijzonder, wat doet malloc terugkeer met respect om dat stuk van de vier bytes? PUBLIEK: Adres? DAVID MALAN: Het adres. Het adres van die brok van vier bytes. Precies. En dat is wat er uiteindelijk opgeslagen in x en dat is waarom we niet echt schelen wat het aantal dat adres is, of het nu OX1 of OX2 of een cryptische hexadecimale adres. Wij geven alleen picturaal dat variabele x is nu wijst naar dat deel van het geheugen. Dus de pijl vertegenwoordigt een pointer of specifieker, een geheugenadres. Maar nogmaals, we meestal niet schelen wat die werkelijke adressen. Nu, deze lijn zegt wat in lekentaal? Star x krijgt 42 puntkomma. Wat betekent dit? Jij wilt gaan? Geen krassen op je nek. 

Doelgroep: Het adres van x op de 42. 

DAVID MALAN: Het adres van x op 42. Niet helemaal. Zo dichtbij, maar niet helemaal, want er is de ster die is voorvoegsel dit x. Dus moeten we een beetje tweaken. Ja? 

Publiek: De waarde die de wijzer x wijst naar is 42. DAVID MALAN: OK. De waarde die de wijzer x wijzend naar, laten we zeggen, zijn 42, of anders gezegd, de ster x zegt, ga dan naar welke adres is in x, of het nu 1 Oxford Straat of 33 Oxford Street of OX1 of OX33, ongeacht dat numeriek adres is, ster x is de dereferentie van x. Dus ga naar dat adres en zet dan het nummer 42 daar. Dus dat zou een gelijkwaardige manier om te zeggen dat. Dus dat is allemaal prima en dan we zouden het beeld vertegenwoordigen als volgt waar we hebben toegevoegd de 42 die brok vier bytes aan de rechterkant, maar Deze lijn was, waar ging het mis en Binky's hoofd schoot uit op dit punt, omdat slechte dingen gebeuren wanneer je dereference vuilnis waarden of je dereference ongeldig pointers, en ik zeg ongeldig omdat op dit punt in de verhaal, wat is de binnenkant van y? Wat is de waarde van de y gebaseerde over de afgelopen paar stappen? Ja? Wat is dat? 

Publiek: Een adres. DAVID MALAN: Een adres. Het moet een adres maar heb ik geïnitialiseerd het? Dus ik nog niet. Wat bekend is dat daar? Het is slechts enkele vuilnis waarde. Het kan elk adres nul is ten 2 miljard als je twee optredens van RAM-geheugen, of nul tot 4 miljard als je hebt kreeg vier gigabyte aan RAM-geheugen. Het is een aantal vuilnis waarde, maar het probleem is dat het besturingssysteem, als het je niet heeft gegeven dat stuk van het geheugen specifiek dat je probeert om te gaan, het is over het algemeen gaat om wat te veroorzaken we hebben gezien als een segmentation fault. Dus in feite, een van jullie die worstelde op problemen kantooruren of problemen die eerder over het algemeen met het proberen te achterhalen een segmentation fault, dat betekent over het algemeen je bent een deel van het aanraken geheugen dat je niet zou moeten zijn. Je geheugen raken dat het besturingssysteem niet mag je aan te raken, of het nu door te gaan te ver in de array of het starten van nu, of het is omdat je te raken geheugen dat is gewoon wat vuilnis waarde. 

Daarbij ster x hier soort undefined gedrag. Moet je nooit doen het omdat odds worden, is het programma gewoon om te crashen, omdat je zegt, ga naar dit adres en je hebt geen idee waar dat adres eigenlijk is. Dus het besturingssysteem is waarschijnlijk gaat uw programma crashen als resultaat en inderdaad, dat is wat gebeurde er Binky. Dus uiteindelijk, Binky vast dit probleem met dit. Zodat het programma zelf werd ontsierd. Maar als je een soort van pioniersgeest en uitvoeren van deze lijn in plaats daarvan, y is gelijk aan x betekent gewoon wat adres is een x, zelfs ook in y. 

En zo pictorially, we hebben vertegenwoordigde deze met twee pijlen van x en y uit te wijzen naar dezelfde plaats. Dus semantisch, x gelijk y omdat deze beide het opslaan van dezelfde adres, ergo wijzend op 42, en nu, als je ster zeggen y, ga dan naar het adres in y, Dit heeft een interessant neveneffect. Dus het adres in y is de hetzelfde als het adres in x. Dus als je zegt dat naar het adres in y en verander de waarde tot 13, wie anders wordt beïnvloed? X, punt D, om zo te zeggen, moet ook worden beïnvloed. 

En inderdaad, hoe Nick trok deze foto in claymation was precies dat. Hoewel we volgen de aanwijzer y, belandden we op dezelfde plaats, en dus als we waren om af te drukken out x of y's pointee, dan zouden we de waarde van 13 te zien. Nu, ik zeg pointee te zijn in overeenstemming met de video. Programmeurs, mijn kennis, nooit echt zeggen dat het woord pointee, hetgeen puntig op, maar voor de consistentie met de video, te realiseren dat is alles dat was bedoeld in die situatie. Zodat eventuele vragen over claymation of pointers of malloc gewoon nog niet? Nee? Prima. 

Dus zonder verder omhaal, laten we eens een kijkje naar waar dit eigenlijk al enige tijd gebruikt. Dus hebben we dit CS50 bibliotheek had dat heeft al deze functies. We hebben gebruikt getInt veel, GetString, waarschijnlijk eerder GetLongLong in mijn Pset één of zo, maar wat er daadwerkelijk aan de hand? Nou, laten we eens een snelle blik onder de motorkap van een programma dat inspireert Daarom geven wij u de CS50 bibliotheek, en inderdaad met ingang van vorige week, we begonnen met het nemen van die zijwieltjes af. Dus dit is nu gesorteerd een postmortem wat is er aan de hand in de CS50 bibliotheek, hoewel we nu beginnen te bewegen weg van het voor de meeste programma's. 

Dus dit is een programma genaamd scanf 0. Het is super kort. Het heeft alleen deze lijnen, maar introduceert een functie genaamd scanf dat we eigenlijk gaan zien in een moment binnen de CS50 bibliotheek zij het in iets andere vorm. Dus dit programma op lijn 16 is waarbij een variabele x. Dus geef me vier bytes voor een int. Het is verteld gebruiker, nummer kunt u, en dan Dit is een interessante lijn die stropdassen eigenlijk elkaar vorige week en dit. Scanf, en dan ziet het duurt een format string, net als printf, % i betekent een int, en dan duurt het een tweede argument dat ziet er een beetje funky. Het is ampersand x, en te herinneren, zagen we alleen deze keer vorige week. Wat betekent ampersand x vertegenwoordigen? Wat doet ampersand doen in C? Ja? 

Doelgroep: Het adres van. DAVID MALAN: Het adres van. Dus het is het tegenovergestelde van de ster exploitant, terwijl de ster operator zegt, ga dan naar dit adres, de ampersand operator zegt figuur uit de adres van deze variabele, en dus dit is de sleutel, omdat scanf doel in het leven is het scannen van de gebruiker input van het toetsenbord, Afhankelijk van wat hij of zij types en lees vervolgens ingang van die gebruiker een variabele, maar we zag in de afgelopen twee weken dat swap-functie die we moeiteloos probeerde uit te voeren was gewoon kapot. Bedenk dat met de swap-functie, als we alleen maar verklaard A en B als ints, we hebben met succes de verwisselen twee variabelen binnenkant van swap net als met de melk en wat fruitsap, maar zodra swap terug, wat het resultaat ten opzichte tot x en y, de oorspronkelijke waarden? Niets. Ja. Er is niets gebeurd dat moment, omdat swaps veranderen alleen de lokale kopieën, dat wil zeggen, alle deze keer, wanneer we hebben al passeren in argumenten aan functies, we zijn gewoon passeren kopieën van deze argumenten. Je kunt doen met die wat je wilt met hen, maar ze gaan niet hebben Effect op de oorspronkelijke waarden. Dus dit is problematisch als je willen een functie als scanf hebben in het leven, waarvan het doel is om te scannen invoer van de gebruiker via het toetsenbord en vervolgens in de lege plekken vullen, om zo te spreken, dat wil zeggen, geef een variabele als x een waarde, want als ik tot net voorbij x om scanf, als je de logica van de laatste overwegen week, kan scanf doen wat het wil met een kopie van x, maar het kon niet permanent x veranderen, tenzij we geven scanf een schatkaart, om zo te zeggen, waarbij x markeert de plek, waarbij passeren we het adres van x zodat scanf kan er en eigenlijk verandering gaan de waarde van x. Zo ja, alle dat dit programma doet als ik scanf 0, in mijn bron 5m directory, maken scanf 0, dot slash scanf, nummer Neem 50, bedankt voor de 50. 

Dus het is niet zo interessant, maar wat er werkelijk gebeurt is dat zodra ik noem scanf hier de waarde van x wordt permanent gewijzigd. Nu, dit lijkt mooi en goed, en in feite lijkt alsof we niet echt nodig de CS50 bibliotheek helemaal niet meer. Bijvoorbeeld, laten we lopen dit hier eens te meer. Laat me heropenen voor een tweede. Laten we proberen een aantal aub en in plaats van te zeggen 50 zoals voorheen, laten we gewoon nee zeggen. OK, dat is een beetje raar. OK. En slechts enkele onzin hier. Dus het lijkt niet te handvat verkeerde situaties. Dus moeten we start minimaal het toevoegen van enkele foutcontrole om ervoor te zorgen dat de gebruiker getypt in een werkelijke aantal, zoals 50, want blijkbaar het typen van woorden wordt niet herkend als problematisch, maar waarschijnlijk moet zijn. 

Laten we eens kijken naar deze versie nu is dat mijn poging om herimplementeren GetString. Als scanf heeft dit alles functionaliteit ingebouwd, Daarom hebben we ploeteren met deze zijwieltjes zoals GetString? Nou, hier is misschien wel mijn eigen eenvoudige versie van GetString waarbij een week geleden, zou ik heb gezegd, geef me een string en noem het bufferen. Vandaag, ga ik gewoon beginnen zeggende char ster, die, herinneren, het is gewoon een synoniem. Het ziet er enger, maar het is precies hetzelfde. Dus geef me een variabele genaamd buffer dat gaat om een ​​string op te slaan, vertel de gebruiker snaar alsjeblieft, en dan, net als vroeger, laten we proberen om deze les te lenen scanf % s deze tijd en dan pas in buffer. Nu, een snelle sanity check. Waarom ben ik niet te zeggen ampersand buffer deze tijd? Afleiden uit het vorige voorbeeld. Publiek: Char ster is een pointer. DAVID MALAN: Precies, want deze keer, char ster is al een pointer, een adres, per definitie van die ster daar. En als scanf verwacht een adres, volstaat gewoon om te passeren in buffer. Ik hoef niet te ampersand buffer zeggen. Voor de nieuwsgierigen, je kon zoiets als dit te doen. Het zou andere betekenis hebben. Dit zou een pointer geven u een pointer, die eigenlijk een geldige ding C, maar nu, laten we het simpel houden en houdt het verhaal consistent. Ik ga gewoon in passeren buffer en dat klopt. Het probleem is echter dit. Laat me gaan en uitvoeren van deze programma na de compilatie. Maken scanf 1. Verdomme, mijn compiler mijn fout te vangen. Geef me een seconde. Clang. Laten we zeggen dat scanf-1.c. OK. Daar gaan we. Ik heb het nodig. CS50 ID heeft verschillende instellingen dat u te beschermen tegen jezelf. Ik moest deze door te schakelen running clang handmatig deze tijd. Dus touwtje alsjeblieft. Ik ga om te gaan en typ in mijn favoriete hello wereld. OK, null. Dat is niet wat ik typte. Dus het is een indicatie van iets dat verkeerd. Laat me ga je gang en typ in een heel lange string. Bedankt voor de nul en ik weet het niet als ik ga in staat zijn om het te crashen. Laten we proberen een beetje kopie plakken en zien of dit helpt. Plakt gewoon een veel van. Het is zeker een groter snaar dan normaal. Laten we gewoon echt schrijven. Nee. Verdomme. Opdracht niet gevonden. Dus dat is niet gerelateerd. Dat is omdat ik geplakt een aantal slechte personages, maar dit blijkt niet gaat werken. 

Laten we proberen dit eens te meer, omdat het is leuker als we eigenlijk crashen. Laten we dit type en nu, ik ben gaan een echt lange reeks kopiëren en nu laten we eens kijken of we kan dit ding crashen. Let op, ik weggelaten ruimten en nieuwe lijnen en puntkomma en alle funky karakters. Enter. En nu het netwerk is gewoon te traag. Ik ingedrukt Command-V te lang duidelijk. Verdomme! Opdracht niet gevonden. 

OK. Nou, het punt is niettemin de volgende. Dus wat er werkelijk gaande is op bij deze verklaring aan van char ster buffer op lijn 16? Dus wat ben ik het krijgen toen ik verklaren een pointer? Alles wat ik krijg is een vier byte waarde genaamd buffer, maar wat erin op dit moment? Het is slechts enkele vuilnis waarde. Omdat elke keer dat u een variabele declareert in C, het is slechts enkele vuilnis waarde, en we beginnen te tocht over deze realiteit. Nu, als ik zeg scanf, ga naar dit adres en zetten wat de gebruiker types in. Als de gebruiker types in hello wereld, goed, waar moet ik het zeggen? Buffer is een vuilnisbak waarde. 

Dus dat is net zoiets als een pijl dat is te wijzen wie weet waar. Misschien is het te wijzen hier in mijn geheugen. En dus wanneer de gebruiker types in Hallo wereld, het programma probeert de zetten touwtje hello wereld backslash 0 in dat stuk van het geheugen. Maar met een hoge waarschijnlijkheid, maar duidelijk niet 100% waarschijnlijkheid, de computer gaat vervolgens crashen het programma, omdat deze niet herinnering die ik zou moeten worden toegestaan ​​aan te raken. Dus in het kort, dit programma is gebrekkig precies die reden. Ik ben fundamenteel niet wat te doen? Welke stappen heb ik weggelaten, net als we weggelaten met eerste voorbeeld Binky's? Ja? 

PUBLIEK: toewijzing geheugen? 

DAVID MALAN: toewijzing geheugen. Ik heb eigenlijk niet toegewezen elke herinnering voor die string. Dus we kunnen dit oplossen in een paar manieren. One, kunnen we het simpel houden en in feite, nu ben je gaan om te beginnen met een vervaging zien van de lijnen tussen wat een array is, wat een string is, wat een char ster is, wat een array van chars is. Hier is een tweede voorbeeld met strijkers en kennisgeving alles wat ik heb gedaan op de lijn 16 is, in plaats van te zeggen die buffer gaat om een ​​klusje te zijn ster, een verwijzing naar een stuk van het geheugen, Ik ga zeer proactief te geven mezelf een buffer voor 16 tekens, en in feite, als je bekend bent de term buffering, waarschijnlijk uit de wereld van video's, wanneer een video buffering, buffering, buffering. Nou, wat is hier het verband? Nou, Binnenkant van YouTube en de binnenkant van videospelers algemeen een matrix dat is groter dan 16. Het kan een matrix van een omvang zijn megabyte, misschien 10 megabytes, en in die array heeft uw browser downloaden van een hele hoop van bytes, een hele hoop megabytes video en de video-speler, YouTube of wie dan ook is, begint het lezen van de bytes van die array, en elke keer zie je de woord buffering, buffering, dat betekent dat de speler gekregen om het einde van die matrix. Het netwerk is zo traag dat het niet bijgevuld de array met meer bytes en dus je bent bits weergeven aan de gebruiker. 

Dus buffer is een passende term hier in die het is gewoon een array, een stuk van het geheugen. En dit zal het te repareren want het blijkt dat je arrays kunnen behandelen alsof ze zijn adressen, hoewel buffer is slechts een symbool, het is een reeks tekens, buffer, dat is handig voor mij, de programmeur, U kunt de naam rond passeren alsof het een pointer, alsof het waren het adres van een brok geheugen voor 16 tekens. Dus dat is te zeggen, kan ik pas de scanf precies dat woord en dus nu, als ik dit programma, maken scanf 2, dot slash scanf 2, en typ in Hallo wereld, Enter, dat tijd-- 

Hmm, wat is er gebeurd? String alsjeblieft. Wat heb ik verkeerd gedaan? Hallo wereld, buffer. Hallo Wereld. Ah, ik weet wat het doet. OK. Dus het is het lezen tot de eerste ruimte. Dus laten we cheat voor slechts een moment en zeg ik wilde alleen maar om iets te typen echt lang als dit is een lange zin dat één, twee, drie, vier, vijf, zes, zeven, acht, negen, 10, 11, 12, 13, 14, 15, 16. OK. Het is inderdaad een lange zin. Dus deze zin is langer dan 16 tekens en dus toen ik druk op Enter, wat er gaat gebeuren? Welnu, in dit geval de verhaal, ik had verklaard buffer om daadwerkelijk een array met 16 tekens klaar om te gaan. Zo één, twee, drie, vier, vijf, zes, zeven, acht, negen, 10, 11, 12, 13, 14, 15, 16. Zo 16 tekens, en nu, toen ik lees in iets als dit is een lange zin, wat er gaat gebeuren is dat ik ga lezen is dit een lange S-E-N-t-E-N-C-E, zin. 

Dus dit is bewust een slechte zaak dat ik blijven schrijven buiten de grenzen van mijn array, de grenzen van mijn buffer. Ik zou je geluk en het programma zal blijven lopen en niet schelen, maar in het algemeen, dit zal inderdaad mijn programma crashen, en het is een bug in mijn coderen het moment dat ik stap de grenzen van die array, omdat ik weet niet of het is se gaan crashen of als ik ga gewoon geluk te krijgen. Dus dit is problematisch omdat dit geval lijkt het te werken en laten verleiden lot hier, ook al de IDE lijkt wel een beetje te tolereren van-- 

Daar gaan we. Eindelijk. Dus ik ben de enige die dit kan zien. Dus ik had net een heleboel plezier te typen een heel lange eigenlijke zin dat het zeker overschreden 16 bytes, omdat ik getypt in deze gekke lange multi-lijn uitdrukking, en dan merken wat er gebeurd is. Het programma probeerde af te drukken en kreeg vervolgens een segmentation fault en segmentatie fouten is wanneer zoiets gebeurt en het besturingssysteem zegt nee, niet dat het geheugen aanraakt. We gaan om te doden het programma geheel. 

Dus dit lijkt problematisch. Ik heb het programma waarbij verbeterd op zijn minst wat geheugen, maar dit lijkt te beperken de functie GetString te krijgen snaren van een aantal eindige lengte 16. Dus als je langer wilt steunen zinnen dan 16 tekens, wat doe je? Nou, je kunt verhogen maat van deze buffer tot 32 of dat lijkt soort kort. Waarom doen we niet alleen te maken Het 1000 maar terug te duwen. Wat is de reactie van intuïtief alleen dit probleem te vermijden door het maken van mijn buffer groter, net als 1000 tekens? Door de implementatie van getString deze manier. Wat is goed of slecht hier? Ja? Publiek: Als je te binden een heleboel van de ruimte en je hoeft niet te gebruiken, dan kun je niet opnieuw toewijzen die ruimte. DAVID MALAN: Absoluut. Het is verspilling voor zover als je niet eigenlijk moeten 900 van die bytes en toch je vraagt 1000 in totaal toch, je bent gewoon consumeren meer geheugen op computer van de gebruiker dan moet je, en tenslotte een deel van je al bent tegengekomen in het leven dat als je loopt veel programma's en ze zijn het eten van veel geheugen, dit kan eigenlijk invloed op de prestaties en de ervaring van de gebruiker op de computer. Dus dat is een soort van een luie oplossing, zeker, en omgekeerd, het is niet alleen verspilling, welk probleem blijft, zelfs als ik mijn buffer 1000? Ja? 

Publiek: De string is lengte 1001. DAVID MALAN: Precies. Als uw string lengte 1001, je precies hetzelfde probleem hebt, en door mijn betoog, zou ik gewoon maken het 2000 toen, maar je weet niet in vooraf hoe groot het zou moeten zijn, en toch, ik moet mijn programma te compileren voordat mensen te laten gebruiken en te downloaden het. Dus dit is precies het soort spul dat de CS50 bibliotheek probeert om ons te helpen met en we zullen alleen oogopslag bij enkele van de onderliggende implementatie hier, maar dit is CS50 dot C. Dit is het bestand dat is geweest op de CS50 IDE al die weken dat je hebt gebruikt. Het is pre-gecompileerde en je hebt automatisch gebruiken aard van het hebben van de dash L CS50 vlag met klank, maar als ik naar beneden scrollen door alle deze functies, hier is GetString, en alleen maar om u een te geven voorproefje van wat er gaande is, laten we eens een snelle blik op de relatieve complexiteit. Het is niet een super lang functie, maar we hebben niet moeten alle harde over denken hoe om te gaan over het krijgen van snaren. 

Dus hier is mijn buffer en ik blijkbaar initialiseren op null. Dit is natuurlijk het hetzelfde als char ster, maar ik besloot in de uitvoering van de CS50 bibliotheek dat als we gaan zijn volledig dynamisch, Ik weet niet van tevoren hoe groot van een snaar gebruikers zullen willen krijgen. Dus ik ga om te beginnen met slechts een lege string en ik ga op te bouwen zo veel geheugen Ik moet de gebruiker reeks passen en als ik niet genoeg, ik ga om te vragen het besturingssysteem voor meer geheugen. Ik ga hun reeks te verplaatsen in een groter stuk van het geheugen en ik ga los of vrij de onvoldoende groot deel van het geheugen en we gaan gewoon dit iteratief doen. 

Dus een snelle blik, Hier is gewoon een variabele waarmee ik ga houden de capaciteit van mijn buffer. Hoeveel bytes kan ik passen? Hier is een variabele n met die ik ga houden bij hoeveel bytes daadwerkelijk de buffer of de gebruiker heeft getypt. Als u dit niet eerder hebt gezien, je kunt opgeven dat een variabele als een int is niet ondertekend, die zoals de naam al doet vermoeden, betekent dat het niet-negatief, en waarom zou Ik ooit willen specificeren moeite dat een int is niet alleen een int, maar het is een unsigned int? Het is een niet-negatief int. Wat doet de [onverstaanbaar] betekenen? 

Publiek: Het beschrijven van een bedrag van geheugen dat kan worden [onverstaanbaar]. 

DAVID MALAN: Ja. Dus als ik zeg niet ondertekend, dit is eigenlijk waardoor je een beetje extra geheugen en het lijkt soort dom, maar als je hebben een beetje extra geheugen, dat betekent dat tweemaal zoveel waarden die u kan vertegenwoordigen, omdat het kan een 0 of 1. Dus standaard, kan een int ruwweg negatieve 2 miljard helemaal tot positieve 2 miljard. Dat zijn grote ranges, maar het is nog steeds soort verspilling Als je alleen de zorg over maten, die net intuïtief moet niet negatief zijn of positief of 0, goed dan, waarom bent u verspilt 2 miljard mogelijke waarden voor negatieve getallen als je nooit gaat om ze te gebruiken? Dus door te zeggen niet ondertekend, nu mijn int kan liggen tussen 0 en ongeveer 4 miljard. 

Dus hier is gewoon een int C om redenen zullen we niet alleen nu zo te krijgen in waarom is het een int plaats van een char, maar hier is de kern van wat er gaande op, en sommigen van jullie kunnen worden gebruikt, bijvoorbeeld het fgetc functie zelfs in Pset vier of daarna, zullen we het zien weer probleem van de vijf, fgetc is mooi, want zoals de naam soort, soort arcanely suggereert, het is een functie die krijgt een karakter en zo, wat is er fundamenteel anders over wat we doen in GetString is dat we niet gebruiken scanf dezelfde manier. We zijn gewoon kruipen langs stap-voor-stap dan wat de gebruiker heeft getypt, want we kunnen altijd wijzen één char, en zo kunnen we altijd veilig kijken naar een char tegelijk, en de magie begint hier gebeuren. Ik ga naar beneden scrollen om het midden van deze functie alleen maar om kort voor te stellen deze functie. Net als er een malloc functie, er is een realloc functie waarbij realloc Hiermee kunt u een stuk van het geheugen te herverdelen en maken het groter of kleiner. Zo lang verhaal kort en met een golf van mijn hand voor vandaag, weten dat wat GetString doet is het is een soort van magische wijze groeien of krimpen de buffer als gebruiker types in zijn of haar string. 

Dus als de gebruiker een korte reeks, deze code alleen kent genoeg geheugen om de string te passen. Als de gebruiker houdt het typen zoals ik deed het opnieuw en opnieuw en weer, goed, als het buffer aanvankelijk deze grote en het programma realiseert, met wacht even, ik ben uit de ruimte, het gaat verdubbelen de grootte van de buffer en dan het dubbele van de grootte van de buffer en de code die de verdubbeling doet, als we kijken naar het hier, het is alleen deze slimme one-liner. Je zou niet deze syntaxis hebben gezien voor, maar als je zegt ster gelijk, Dit is hetzelfde als zeggende capaciteit tijden 2. Dus het blijft gewoon een verdubbeling de capaciteit van de buffer en dan vertellen realloc te geven zich dat er veel meer geheugen. 

Nu, als een terzijde, is er zijn andere functies hierin dat we niet zullen kijken naar elk detail anders dan om te laten zien in getint, we gebruiken GetString in getint. We controleren dat het niet null, die, herinneren, de bijzondere waarde betekent dat er iets mis is gegaan. We zijn uit het geheugen. Beter controleren dat. En we terug een sentinel waarde. Maar ik zal zich naar de opmerkingen met betrekking tot waarom en dan gebruiken we deze neef van scanf riep sscanf en het blijkt dat sscanf, of touwtje scanf, laat u een kijkje nemen op de lijn te nemen dat de gebruiker heeft getypt en laat u analyseren wezen en wat ik ben hier doen is Ik zeg sscanf, analyseert wat de gebruiker getypt in en zorg ervoor dat% i, Er is een integer in, en we zullen niet krijgen vandaag precies de reden waarom is er ook a% c hier, maar dat in een notendop laat we detecteren of de gebruiker heeft getypt in iets nep na het nummer. Dus de reden dat getint en GetString je vertellen om opnieuw te proberen, opnieuw proberen, opnieuw proberen is vanwege alle dat de code die we hebben geschreven, Het is een beetje te kijken naar de ingang van de gebruiker om ervoor te zorgen dat het geheel numeriek of het is een echte drijvende puntwaarde of dergelijke, afhankelijk van de waarde functie die u gebruikt. 

Oef. OK. Dat was een mondvol maar het punt is hier dat de reden waarom we hadden die zijwieltjes op is omdat op het laagste niveau, er is gewoon zo veel dingen die mis kan gaan dat we wilden om preventief te behandelen die dingen zeker in het eerste weken van de klas, maar nu met Pset vier en vijf en Pset dan zul je zien dat het meer aan u, maar ook dat je beter in staat het oplossen van dit soort problemen jezelf. Vragen over GetString of getint? Ja? 

Publiek: Waarom zou je verdubbelen de capaciteit van de buffer in plaats van alleen het verhogen door het juiste bedrag? 

DAVID MALAN: Goede vraag. Waarom zouden we het dubbele van de capaciteit van de buffer in tegenstelling om gewoon vooruit door een constante waarde? Het was een ontwerp beslissing. We besloten omdat het de neiging om een beetje duur qua tijd om te vragen het besturingssysteem voor het geheugen, hebben we niet wilt eindigen krijgen in een situatie voor grote strings dat we vroegen weer OS en weer in snelle opeenvolging voor het geheugen. Dus we besloten, ietwat willekeurig maar we hopen dat redelijk, dat, weet je wat, laten we proberen om vooruit lopen en gewoon blijven verdubbelen, zodat we de hoeveelheid te minimaliseren we moeten malloc bellen of realloc, maar een totaal oordeel bellen zonder kennen wat gebruikers willen wellicht in te typen. Beide manieren zou kunnen zijn discutabel. Ongetwijfeld goed. 

Dus laten we een kijkje nemen op een paar andere bijwerkingen van het geheugen, dingen die mis kan gaan en tools die u kunt om dergelijke fouten te vangen. Het blijkt dat jullie allemaal, ook al check50 heeft niet verteld u zo veel, zijn schrijven buggy code sinds een week, zelfs als alle check50 tests verstreken, en zelfs als u en uw TF zijn super overtuigd dat uw code werkt zoals bedoeld. Uw code is buggy is of gebrekkig in dat u allen, het gebruik van het CS50 bibliotheek zijn lekkende geheugen. Je hebt gevraagd het besturingssysteem voor het geheugen in de meeste programma's je hebt geschreven, maar je hebt eigenlijk nooit gezien het terug. Je hebt GetString genoemd en getint en GetFloat, maar met GetString, je hebt nooit unGetString of geef genoemd String Back of iets dergelijks, maar we hebben gezien dat GetString doet geheugen toewijzen door middel van malloc of dit functie realloc, dat is gewoon zeer vergelijkbaar in de geest, en toch, we zijn geweest vraagt ​​het besturingssysteem voor geheugen en het geheugen weer maar nooit geven het terug. 

Nu, als een terzijde, blijkt dat wanneer een programma wordt afgesloten, al het geheugen automatisch vrijgemaakt. Dus het is niet een groot probleem geweest. Het gaat niet om het te breken IDE of langzaam dingen naar beneden, maar wanneer programma's doen meestal lekken geheugen en ze lopen voor een lange tijd. Als je ooit hebt gezien de stomme strandbal in Mac OS of de zandloper Windows waar het soort vertragen of denken of denken of gewoon echt begint te traag als een slak, het heel zou kunnen zijn het resultaat van een geheugenlek. De programmeurs die schreef de software die u gebruikt vraagt ​​het besturingssysteem voor het geheugen elke paar minuten per uur. Maar als je het uitvoeren van de software, zelfs als het geminimaliseerd in uw computer uren- of dagenlang, je zou kunnen vragen om meer en meer geheugen en eigenlijk nooit gebruikt en zo je code zou kunnen zijn, of programma's kunnen worden lekt geheugen, en als je begint te lekken geheugen, is er minder geheugen voor andere programma's, en het effect is vertragen alles naar beneden. 

Nu, dit is veruit een van de meest gruwelijke programma je kansen om te draaien in CS50 zover als output is nog meer esoterische dan clang of maken of één van de commando Online programma's die we eerder hebben uitgevoerd, maar gelukkig, ingebed in de output is een aantal super handige tips die zal nuttig zijn hetzij voor Pset vier zijn of zeker PSET vijf. Dus valgrind is een hulpmiddel die kunnen worden gebruikt om te kijken voor het geheugen lekken in uw programma. Het is relatief eenvoudig om te draaien. Je loopt valgrind en dan, zelfs al is het een beetje breedsprakig, dash dash lek check gelijk vol, en dan dot slash en de naam van het programma. Dus valgrind zal dan uw programma uit te voeren en aan het einde van uw programma runnen voordat hij stopt en geeft u een andere prompt het gaat om het analyseren van uw programma, terwijl het is gelopen en zeg je heb je lekken elke geheugen en beter nog, heb je geheugen aanraken niet van jou? Het kan niet alles te vangen, maar het is vrij goed in het vangen van de meeste dingen. 

Dus hier is een voorbeeld van het hebben van mijn run dit programma, met run valgrind, op een programma genaamd geheugen, en ik ga de lijnen die markeren uiteindelijk voor ons van belang. Dus er is nog meer afleiding dat ik van de glijbaan heeft verwijderd. Maar laten we eens kijken wat dit programma is in staat om ons te vertellen. Het is in staat om ons te vertellen dingen als ongeldig schrijven van maat 4. Met andere woorden, als u het geheugen aanraakt, bijzonder 4 bytes geheugen dat je niet zou moeten hebben, valgrind kan u vertellen dat. Ongeldige schrijven van maat 4. Je raakte vier bytes dat je niet zou moeten hebben. Waar heb je dat gedaan? Dit is de schoonheid. Memory dot c lijn 21 is waar je verpest en dat is waarom het nuttig. Net als GDB, kan het helpen u wijzen op de feitelijke fout. 

Nu, dit is een beetje meer uitgebreide of zelfs verwarrend. 40 bytes in 1 blokken zijn zeker verloren in verlies record 1 van 1. Wat betekent dat? Nou, het betekent gewoon dat je vroeg 40 bytes en je nooit gaf het terug. Je noemde malloc of u geroepen GetString en het besturingssysteem gaf je 40 bytes, maar je nooit bevrijd of vrijgegeven dat het geheugen, en om eerlijk te zijn, we hebben nooit laten zien hoe je terug te geven geheugen. Blijkt dat er een super eenvoudige functie genaamd gratis. Neemt één argument, het ding je wilt vrij te maken of terug te geven, maar 40 bytes blijkbaar in dit programma verloren zijn gegaan in lijn 20 geheugen dot c. 

Dus laten we zien dit programma. Het is super nutteloos. Het toont alleen deze specifieke fout. Dus laten we eens een kijkje nemen. Hier is de belangrijkste en de belangrijkste, bericht, gesprekken een functie genaamd f en vervolgens terugkeert. Dus niet zo interessant. Wat doet f doen? Let op, ik heb geen moeite met een prototype. Ik wilde de code te houden zo klein mogelijk. Dus ik zet f boven de hoofd-en dat is prima, zeker, voor korte programma's zoals dit. Dus f niets terug en doet niet iets aan te nemen, maar het doet dit te doen. Het verklaart, net als in de Binky voorbeeld een pointer genaamd x dat gaat het adres van een int slaan. Dus dat is de linker kant. In het Engels, wat is de rechterzijde doen? Iedereen? Wat is dit voor ons? Ja? 

PUBLIEK: [onverstaanbaar] keer de grootte van een int dat is 10 keer dat [onverstaanbaar] DAVID MALAN: Goede en laat me samenvatten. Dus toewijzen voldoende ruimte voor 10 gehele getallen of 10, wat is de grootte van een int, Het is vier bytes, dus 10 keer 4 is 40, zodat de rechterzijde die ik heb gemarkeerde is geef me 40 bytes en opslaan van het adres van de eerste byte in x. En nu tot slot, en hier is waar Dit programma is buggy, wat is mis met lijn 21 op basis van die logica? Wat is er mis met lijn 21? Ja? Publiek: Je kunt niet index in x [onverstaanbaar]. DAVID MALAN: Ja. Ik moet niet index in x als dat. Dus syntactisch, dat is OK. Wat er leuk is, net als jij kan de naam van een array te behandelen alsof het een pointer, eveneens kunt u een pointer te behandelen alsof het een array, en zo kan ik syntactisch zeggen x beugel iets, x beugel i, maar 10 problematisch. Waarom? 

Publiek: Omdat het niet binnen. 

DAVID MALAN: Het is niet binnen dat deel van het geheugen. Wat is de grootste waarde zou ik te zetten in die vierkante haken? 9, 0 tot 9. Door nul indexeren. Dus 0 tot en met 9 zou fijn zijn. Beugel 10 is niet goed en maar, herinneren hoewel, elke keer Ik meen mij te proberen CS50 IDE maken crash door het intypen van valse waarden, het niet altijd werken, en inderdaad, je vaak geluk alleen omdat de besturingssysteem niet merken dat je ooit zo iets passeren enkele brok van geheugen, omdat je bleef binnen technisch uw segment, maar daarover in een besturingssystemen klasse, en zo iets als dit kan heel gemakkelijk onopgemerkt. Het programma gaat nooit crashen consequent maar misschien een keer in een tijdje. 

En zo laten we proberen valgrind Op deze, en hier is waar we overweldigd door de uitgang tijdelijk. Dus zorg geheugen valgrind lektest evenaart full dot slash geheugen. En hier is waarom ik beloof Dit zou overweldigen. Hier is wat valgrind, hier is wat een programmeur, enkele jaren geleden- besloten dat het een goed idee zou zijn voor de output te lijken. Dus laten we gevoel van deze. Dus helemaal aan de linker side zonder goede reden is het proces ID van het programma we gewoon lopen, de unieke identifier voor het programma dat we net liep. We verwijderd dat vanaf de glijbaan, maar er is een aantal nuttige informatie hier. 

Laten scrollen naar de top. Hier is waar we begonnen. Dus het is niet zo heel veel output. Hier is dat ongeldig schrijven van maat 4 op lijn 21. Nou, wat was lijn 21? Lijn 21 was precies Hierdoor en het zinvol dat ik in rechtsgeldig het schrijven van 4 bytes, want ik ben probeert dit integer zetten, die kan van alles zijn, het gebeurt gewoon te worden nul, maar ik probeer om het te zetten op een locatie dat hoort niet bij mij. Bovendien, hier beneden, 40 bytes in één blokken zijn zeker verloren in een recordtijd 1. Dat komt omdat als ik bel malloc hier heb ik eigenlijk nooit vrij het geheugen. 

Dus hoe kunnen we dit oplossen? Laat me gaan en een beetje veiliger en doe 9 daar en laat me hier gratis x. Dit is de nieuwe functie voor vandaag. Als ik nu opnieuw uitvoeren maken geheugen dot slash, laten we opnieuw uitvoeren valgrind op, maximaliseren van mijn raam en druk op Enter. Nu, het is goed. Ze begraaft het goede nieuws in al deze uitgang. Alle hoop blokken waren vrij. We zullen terug naar wat de hoop komen is, maar geen lekken mogelijk. Dus dit is gewoon een andere tool voor uw tool kit waarmee je kunt beginnen met nu vinden fouten als dat. 

Maar laten we eens kijken wat meer mis kan gaan hier. Laten we nu de overgang naar eigenlijk het oplossen van een probleem. Even terzijde, als dit zal verlichten beetje verwarring of spanning, dit is nu grappig. Ja. Dat is vrij goed. Omdat pointers zijn adressen en adressen zijn over het algemeen volgens afspraak geschreven met hexadecimale. Ha, ha, dit is nu grappig. Hoe dan ook, dus laten we nu echter een probleem. Dit super geweest super laag niveau tot nu toe, en we kunnen werkelijk nuttig doen dingen met deze low-level details. 

Dus hebben we een paar weken geïntroduceerd geleden het idee van een array. Een array was leuk omdat het is moeilijk om schoon te maken onze code want als we wilden een schrijven programma met meerdere studenten of meerdere namen en huizen en slaapzalen en hogescholen en dat alles, konden we alles meer op te slaan netjes binnen een array. Maar stellen een nadeel van een matrix tot nu toe. Zelfs als je het niet zelf hebt geleden in een programma, maar instinctief, wat is een slechte zaak over een matrix, misschien? Ik hoor wat gemompel. Publiek: Het is moeilijk de kleur veranderd worden. DAVID MALAN: Het is moeilijk de kleur veranderd worden. U kunt de grootte niet veranderen van een array, in feite, zodanig in C. U kunt een andere array toe te wijzen, bewegen alles van de oude in de nieuwe, en nu wat extra ruimte, maar het is niet als een taal als Java of Python of elk aantal andere talen waarmee sommige van jullie vertrouwd zou kunnen zijn waar u kan gewoon blijven toevoegen dingen vervelens aan het einde van een array. Wanneer u een scala aan maat 6, dat de grootte is, en zo veel op het idee eerder een buffer van een bepaalde grootte, je moet raden uit de poort welke maat heb je dat wilt? Als u raden te groot, je verspilt ruimte. Als je te klein raden, u kan deze informatie niet opgeslagen, ten minste zonder veel meer werk. 

Dus vandaag, dankzij pointers, kunnen wij beginnen aan elkaar plakken van onze eigen aangepaste gegevensstructuren, en Eigenlijk is hier iets dat ziet er een beetje meer cryptische op het eerste gezicht, maar dit is wat we noemen een gekoppelde lijst, en de naam soort vat samen het. Het is een lijst van nummers, of in dit geval, een lijst van nummers, maar het kan een lijst van alles zijn, maar het is met elkaar verbonden door middel van pijlen, en gewoon een gok te nemen met welke techniek gaan we om te kunnen om samen steek, soort als popcorn met een draad, een gelinkte lijsten rechthoeken hier? Zijn nummers? Wat is de taal functie onderliggende? 

Publiek: Een wijzer. 

DAVID MALAN: een pointer. Dus elk van deze pijlen hier vertegenwoordigt een pointer of gewoon een adres. Dus met andere woorden, als ik wil om een ​​lijst met nummers op te slaan, Ik kan niet zomaar op te slaan als ik wil het vermogen om te groeien en krimpen mijn datastructuur in een array. Dus ik moet een beetje hebben meer raffinement, maar merken dat dit foto soort suggereert dat als je net hebt weinig discussies met elkaar verbinden van alles, Waarschijnlijk is niet zo moeilijk om ruimte te maken tussen twee van deze rechthoeken of twee van die knooppunten, zoals we beginnen bellen ze, in een nieuw knooppunt, en dan met een aantal nieuwe thread, net sloot de drie knooppunten samen, de eerste, de laatste en degene dat je gewoon ingevoegd in het midden. 

En inderdaad een gelinkte lijst, In tegenstelling tot een array dynamisch. Het kan groeien en het kan krimpen en jij niet moet weten of zorg op voorhand hoe veel gegevens die u gaat worden het opslaan, maar het blijkt dat we een beetje te zijn voorzichtig zijn over hoe om dit te implementeren. Dus laten we eerst eens kijken hoe we implementeren één van deze kleine rechthoeken. Het is gemakkelijk om een ​​int implementeren. Je zegt gewoon int n en vervolgens je krijgt 4 bytes voor een int, maar hoe krijg ik een int, noem het n, en dan een wijzer, laten we noemen het volgende. We kunnen deze noemen dingen wat we willen maar ik moet een aangepaste datastructuur. Ja? 

PUBLIEK: Ampersand [onverstaanbaar]. 

DAVID MALAN: Dus ampersand we zullen gebruiken om krijgt het adres van een knooppunt potentieel. Maar we nog nodig kenmerk van C teneinde mij de mogelijkheid te creëren geven deze gewoonte rechthoek, deze gewoonte variabele als je wil, in het geheugen. Publiek: Een struct. DAVID MALAN: een structuur. Herinneren van vorige week, we geïntroduceerd structuur, deze relatief eenvoudige trefwoord dat laat ons dit soort dingen te maken. C kwam niet met een data- structuur genaamd student. Het wordt geleverd met int en float en char en zodanig, maar het komt niet met een student, maar we kunnen een type student gegevens te maken, een student structuur, met deze syntaxis here. En je zult dit opnieuw en opnieuw te zien. Dus maak je geen zorgen te maken over het onthouden van de zoekwoorden, maar het zoekwoord dat het belangrijk is alleen het feit dat we zeiden struct en riep toen we student en de binnenkant van de student was een naam en een huis of een slaapzaal of iets dergelijks. 

En nu vandaag, laten we stellen dit. Ik heb een paar woorden toegevoegd, maar als ik wil deze rechthoek die is uit te voeren kreeg zowel een int en een wijzer, weet je wat, ik ben gaan naar een structuur genaamd knooppunt verklaren. Ik ben ook, de binnenkant van het, gaan zeggen dat een knooppunt, rechthoek, heeft een int en we noemen het n en het heeft een volgend pointer. En dit is een beetje breedsprakig, maar als je erover nadenkt, de pijlen die op de foto waren een moment geleden zijn van wat voor soort data? Waarbij elk van die pijlen wijst om wat voor soort data structuur? Het is niet alleen wijzen naar een int per se. Het wijst naar de geheel rechthoekig ding en dat rechthoekig ding, we zeiden, wordt een knooppunt genoemd. En dus hebben we soort hebben recursief ander zodanig definiëren dat een knooppunt, laten we zeggen, zal een int genaamd n bevatten en een wijzer genoemd volgende en de type gegevensstructuur waarin dat wijzer is blijkbaar zal struct node. 

Dus dit is hinderlijk breedsprakig en gewoon te pedant zijn, de reden waarom we niet kunnen alleen dit zeggen, dat eerlijk gezegd ziet er een stuk beter leesbaar, is omdat herinneren dat C gelezen dingen van boven naar beneden, van links naar rechts. Het is niet totdat we de puntkomma dat het zoekwoord knooppunt werkelijk bestaat. Dus als we willen dit soort hebben cyclische referentie binnenzijde van de data structuur, moeten we dit doen, waar we zeggen struct knooppunt aan de top, die geeft ons een langere weg te beschrijven deze ding, dan binnenkant we zeggen struct knooppunt en dan op het allerlaatste lijn we zeggen, oke, C, door de manier, alleen deze hele verdomde bellen wat een knooppunt en stoppen met behulp van het trefwoord structuur helemaal. Dus dit is gewoon een soort van een syntactische truc die uiteindelijk laat ons maken iets dat ziet er precies zo. 

Dus als we nu gaan we ervan uit kunnen uitvoering van deze zaak in C, hoe kunnen we eigenlijk start doorkruisen dit? Nou, in feite, alles wat we moeten doen is herhalen van links naar rechts en net soort plaatst knooppunten of knooppunten verwijderen of zoeken naar dingen waar we willen, maar om dit te doen, laten we gaan vooruit en maak dingen een beetje meer reëel, omdat deze is super laag niveau tot nu toe geweest. Zou iemand letterlijk als eerste zijn? OK. Kom op maximaal. Hoe heet je? 

DAVID: David. DAVID MALAN: David. Leuk je te ontmoeten. Ik ook. Prima. En we hebben een nummer 9. Niet zo goed als de eerste, misschien. OK, nummer 9. Een aantal 17, alstublieft. Laat me terug te gaan een beetje verder. Number 22, dan kunt u, en hoe zit verder terug als ik elke handen kan zien met al het licht of geen. Iemand die daar vrijwillig. Wilt u op de proppen komen? Onderarm wordt met geweld gaat omhoog. OK, 17. 22. 26 wordt naar beneden. Zou iemand anders willen forcefully-- Kom op maximaal. Een echte vrijwilliger. 

Dus zeer snel, als jullie kunnen regelen jezelf net als de knooppunten op het scherm. Dankjewel. En je zult 26. Oké en snelle introducties. Dus ik ben David en je bent ook? DAVID: David. DAVID MALAN: En u bent? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Excellent. Dus dit zijn onze vrijwilligers voor vandaag en ga je gang en verschuiven een beetje op die manier, en gewoon doorgaan en te houden houden van uw nummers als u of uw eerste teken en het gebruik van uw linkerhand, ga je gang en gewoon uit te voeren deze pijlen, net zodat uw linkerhand is letterlijk wijzend op wat je zou moeten wijzen bij, en geef jezelf wat ruimte, zodat kunnen we visueel zien je armen eigenlijk wijzen, en je kunt gewoon wijzen soort op de grond is prima. 

Dus hier hebben we een gelinkte lijst van één, twee, drie, vier, vijf knooppunten aanvankelijk en merken hebben wij deze speciale pointer aan het begin wie er key want we hebben om bij te houden van de gehele lengte lijst een of andere manier. Deze jongens, ook al zijn ze vertrokken naar rechts, rug aan rug in het geheugen, ze kunnen eigenlijk overal zijn in het geheugen van de computer. Dus deze jongens kunnen zijn staan ​​overal op het podium en dat is prima, zolang ze eigenlijk wijzen naar elkaar, maar om dingen te houden schoon en simpel, we ze gewoon trekken van links naar rechts, zoals , maar kunnen er grote leemten tussen die knooppunten. 

Nu, als ik wil eigenlijk voegen sommige nieuwe waarde, laten we verder gaan en doen dit. We hebben een kans nu een ander knooppunt kiezen. Zeggen laten we beginnen met mallocing 55. Zou iemand erg om malloc? Oké, kom op. Hoe heet je? RAINBOW: Regenboog. DAVID MALAN: Regenboog? Prima. Malloc Regenboog. Kom op maximaal. Dus nu moeten we ons afvragen algoritmisch waar we kunnen zetten 55. Dus alles van ons weten, natuurlijk, waar ze waarschijnlijk behoort als we proberen dit opgelost te houden en als jullie kon men rekening een stap terug zodat we niet vallen het podium, dat zou geweldig zijn. Dus eigenlijk, Rainbow, beginnen hier bij mij, omdat wij als de computer nu kan slechts een variabele zien op een moment. Als dit het eerste knooppunt. Merk op dat hij is niet een knooppunt, hij is gewoon een pointer, en dat is waarom hij is aangetrokken te zijn alleen de grootte van een pointer, niet zo'n volle rechthoeken. Dus we gaan om te controleren bij elke iteratie is 55 minder dan 9? Nee. Is 55 kleiner dan 17? Nee. Minder dan 22? Minder dan 26? Minder dan 34? En nu, uiteraard Regenboog behoort aan het einde. Dus om duidelijk te zijn, en wat was uw naam, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Dus bij Taylor's linkerhand en Rainbow handen hier, wiens hand moet wijzen op wat in bestelling te plaatsen 55 in dit overzicht? Wat moeten we doen? Ja? 

PUBLIEK: hand Taylor's moet links wijzen. 

DAVID MALAN: Precies. Dus inbrengen van een knooppunt in het uiteinde van de lijst is vrij eenvoudig omdat Taylor net moet punt, in plaats van op de grond of we noemen het null, null is een soort van het ontbreken een pointer of een speciale nul wijzer, je bent ga naar punt met uw linkerhand hand op de regenboog en Rainbow, Waar moet je linker waarschijnlijk de hand wijzen? Naar beneden. Het is niet goed als haar hand is een soort van wijzen hier of soort van off welke kant op. Dat zou worden overwogen een vuilnisbak waarde, maar als ze wijst op sommige bekende waarde, zullen we noem het nul of nul, dat is OK want we hebben een term in dit en we weten dat de lijst is nu voltooid. 

Dus wat is een ander relatief eenvoudig geval? Kunnen we malloc 5? Kom op maximaal. Hoe heet je? TIFFANY: Tiffany. DAVID MALAN: Het spijt me? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Prima. Tiffany is malloced de waarde 5. Kom op maximaal. Deze is relatief eenvoudig ook, maar laten we eens kijken volgorde van de operaties nu. Het was vrij gemakkelijk met Taylor op het einde. Nummer 5 is uiteraard minder dan 9, en dus hebben we David, hebben we Tiffany, en wat is uw naam? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, en David. Wiens hand moet eerst worden bijgewerkt? Wat wil je hier doen? Er zijn een paar mogelijke manieren, maar er is ook een of meer verkeerde manieren. 

PUBLIEK: Begin met de meest linkse. 

DAVID MALAN: Begin met de meest linkse. Wie is hier de meest linkse dan? Publiek: First. 

DAVID MALAN: OK. Dus beginnen met de eerste en waar moet je wilt bijwerken David's handen zijn? PUBLIEK: Naar de 5. DAVID MALAN: OK. Dus David, punt op vijf of Tiffany hier en nu? 

PUBLIEK: Tiffany wijst op de 9? DAVID MALAN: Perfect, met uitzondering van Binky's hoofd net soort viel, toch? Want wat is er mis met deze foto letterlijk? PUBLIEK: Niets wijst. DAVID MALAN: Niets is wijzend naar Jake nu. We hebben letterlijk wees 9 en 17, en we hebben letterlijk lekte van dit geheugen, omdat door eerste actualisering van David's hand, dat is fijn voorzover het correct wijzend op Tiffany nu, maar als niemand had de vooruitziendheid te wijzen op Jake, dan hebben we verloren de geheel van die lijst. Dus laten we ongedaan te maken. Dus dat was een goede zaak struikelen maar laten we corrigeren nu. Wat moeten we eerste plaats doen? Ja? 

PUBLIEK: Tiffany moet wijzen op de 9? DAVID MALAN: Ik kan niet krijgen die dicht bij je. Wie moet wijzen op de 9? 

Publiek: Tiffany. 

DAVID MALAN: Oké. Dus moet Tiffany eerste punt op de 9. Dus Tiffany moet nemen op een identieke waarde David, die lijkt redundant voor een moment, maar dat komt omdat nu prima, tweede stap, kunnen we van David's hand te werken te wijzen op Tiffany, en dan als we gewoon een soort van schone dingen alsof dit is een soort van de lente-achtig, nu is dat een juiste plaatsing. Zo uitstekend. Dus nu zijn we er bijna. Laten we voegen een laatste waarde als de waarde 20. Als we nog een laatste vrijwilliger kon malloc? Kom op maximaal. Dus dit is een beetje lastig. Maar echt, de code zijn we schrijven, hoewel mondeling, is net als het hebben van een bos van als de omstandigheden nu, toch? We hadden een aandoening controleren of het behoort Aan het einde, misschien het begin. We moeten een soort van lus vind de plek in het midden. Dus laten we dat doen met wat is uw naam? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Leuk je te ontmoeten. Dus hebben we 20. Minder dan vijf? Nee. Minder dan negen? Nee. Minder dan 17? Nee. OK. Hij hier hoort en uw namen weer zijn? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, en? ERIC: Eric. DAVID MALAN: Eric. Wiens handen moeten krijgen eerste update? 

Publiek: Eric. OK. Dus Eric's moeten wijzen naar waar? Op 22. Goed. En nu wat is het volgende? Sue kan dan wijzen op Eric en nu, als jullie gewoon maak wat ruimte, die is prima visueel, nu hebben we het inbrengen gedaan. Dus laten we nu eens een vraag, maar dank je wel voor onze vrijwilligers. Heel goed gedaan. U kunt houden die, als je wilt. En we hebben een mooi afscheidscadeau als zou je elke willen een stress-bal te nemen. Laat me gewoon langs deze naar beneden. Dus wat is de afhaalmaaltijd van dit? Dit lijkt geweldig te zijn voor zover we nu hebben introduceerde alternatief voor een array niet beperkt een array van een vast formaat. Ze kunnen dynamisch groeien. 

Maar net zoals we hebben gezien in weken verleden, nooit iets krijgen we gratis, zeker als er een trade-off hier. Dus met een bovenkant van een gekoppelde lijst, is deze dynamiek? Dit vermogen om te groeien en eerlijk gezegd, we konden verwijderen hebben gedaan en we kunnen krimpen nodig. Welke prijs betalen we? Tweemaal zoveel ruimte allereerst. Als je kijkt naar de foto, niet langer ben ik het opslaan van een lijst met getallen. Ik ben het opslaan van een lijst van integers plus pointers. Dus ik ben een verdubbeling van de hoeveelheid ruimte. Nu, misschien is dat niet zo'n big deal 4 bytes, 8 bytes, maar kan zeker toevoegen voor grote datasets. Wat is een ander nadeel? Ja? 

PUBLIEK: We moeten doorkruisen ze één voor één. DAVID MALAN: Ja. We moeten ze doorkruisen één voor één. Weet je wat, we gaven deze super handige functie van square bracket notatie, juister bekend als random access, waar we gewoon kunnen springen een individueel element maar nu als ik had nog steeds mijn vrijwilligers hier, als ik wilde het vinden nummer 22, ik kan het gewoon niet direct naar de beugel iets iets. Ik heb om te kijken over de lijst, veel zoals onze zoeken voorbeelden lineair, het nummer 22 vinden. Dus lijken we een prijs die er voor hebben betaald. Maar we kunnen toch andere problemen. 

In feite, laat me introduceren slechts een paar van de visuals. Dus als je naar beneden te zijn geweest Mather's Dining Hall onlangs, u zult zich herinneren dat hun stapels trays als dit, we geleend deze uit Annenberg voor de les. Dus dit stapel trays, hoewel, representatief is eigenlijk van een computer science datastructuur. Er is een datastructuur in de informatica bekend als een stack die erg mooi leent zich precies dit visueel. Als elk van deze bakken geen lade, maar als een nummer en ik wilde Voor nummers, I zou men hier beneden te zetten, en ik kon nog hier neergezet, en verder stapelen nummers boven elkaar, en wat potentieel behulpzaam over dit is dat wat de implicatie deze gegevensstructuur? Welk nummer kan ik trek eerst meest gunstig? De meest recent een put op daar. 

Dus dit is wat we zouden noemen in informatica een LIFO datastructuur. Last in, first out. En we zullen zien waarom het duurde niet lang dat kan nu nuttig maar zijn, alleen rekening houden met de woning. En het is een soort van dom als je denkt over hoe de eetzaal doet. Elke keer als ze schoon en trays zet de verste die op de top, je kon een eerder schoon hebben maar uiteindelijk erg vies en stoffig lade op de bodem als je eigenlijk nooit tot op de bodem van die stack, omdat je gewoon houden invoering van de nieuwe en de schone bovenop. Hetzelfde zou kunnen gebeuren in een supermarkt ook. Als u een vitrine melk en elke keer CVS of wie krijgt meer melk, je gewoon schuiven de melk je al aan de rug en u de nieuwe voorkant, je gaat naar een aantal mooie nare hebben melk aan het einde van de datastructuur, omdat het altijd aan de onderkant of equivalent is het altijd achter. 

Maar er is een andere manier om na te denken over voering gegevens en bijvoorbeeld deze. Als je een van die mensen die graag line-up buiten Apple-winkels wanneer een nieuw product komt out, bent u waarschijnlijk niet met behulp van een stapel data structuur omdat u zou vervreemden iedereen die is de rij om een ​​aantal nieuwe speeltje te kopen. Integendeel, je bent waarschijnlijk met behulp wat voor soort data structuur of wat voor soort systeem in de echte wereld? Hopelijk is het een lijn, of meer goed of meer Britten-achtig, een wachtrij. En het blijkt een wachtrij is ook een datastructuur in de informatica, maar een wachtrij heeft een zeer anders eigendom. Het is niet LIFO. Last in, first out. God verhoede. Het FIFO plaats. Als eerste erin, als eerste eruit. En dat is een goede zaak voor eerlijkheid 'sake zeker als je langs bent super vroeg in de ochtend. Als je er eerst, u wil om eruit te komen eerst ook. 

En zo al deze gegevens structuren, wachtrijen en stapels en trossen van anderen, blijkt dat je kunt denken aan dit als slechts een array. Dit is een matrix, misschien een vaste grootte 4, maar het zou zijn wel leuk als we konden gewoon stapelen trays bijna oneindig lang als we hebben dat veel trays of cijfers. Dus misschien willen we gebruik maken van een gekoppelde lijst hier, maar de trade-off gaat worden potentieel dat we meer geheugen nodig heeft, neemt iets meer tijd, maar we kan de hoogte van de stapel niet beperken net als Mather's vitrine kunnen beperken de grootte van de stack, en dus deze zijn ontwerpbeslissingen of opties beschikbaar voor ons uiteindelijk. Dus met deze gegevens structuren, zijn we begonnen zien van nieuwe bovengrenzen potentieel van wat eerder was super snel en waar we vertrekken off vandaag en waar de we hopen te bereiken is op woensdag, zullen we gaan kijken naar een data structuur die laat ons zoeken door middel van data log eindtijd weer. En we zagen dat, herinneren, in week nul en één met binaire zoeken of verdeel en heers. Het komt terug en beter nog, de heilige graal voor deze woensdag zal komen met de gegevensstructuur die werkelijk uitgevoerd of theoretisch in constante tijd, waarbij het maakt niet uit hoeveel miljoenen of miljarden van de dingen We hebben in de gegevensstructuur, zal neem ons constante tijd, misschien een stap of twee stappen of 10 stappen, maar constante aantal stappen om door middel van die gegevensstructuur. Dat zal inderdaad de heilige graal zijn maar daarover woensdag. Zie je dan. 

[Muziek]