[Powered by Google Translate] [Week 4] [David J. Malan] [Harvard University] [Dit is CS50.] [CS50.TV] Oke, dit is CS50, en dit is het begin van week 4, en dit is een van de laagst mogelijke sorteeralgoritmen. Welke was het dat we er gewoon gekeken? Dat was bubble sort, om grote O (n ^ 2) + sum, en inderdaad we zijn niet de enigen in deze wereld lijken te weten wat bubble sort is of de looptijd. Inderdaad, dit was een interview met Eric Schmidt van Google en voormalig senator Barack Obama slechts een paar jaar geleden. Nu, Senator, je bent hier bij Google, en ik wil graag van het voorzitterschap te zien als een sollicitatiegesprek. Nu, het is moeilijk om een ​​baan te krijgen als president, en je gaat door de ontberingen nu. Het is ook moeilijk om een ​​baan bij Google. Wij hebben vragen, en we vragen onze kandidaten vragen, en deze is van Larry Schwimmer. Jullie denken dat ik een grapje maak? Het is hier. Wat is de meest efficiënte manier om een ​​miljoen 32-bit integers te sorteren? [Gelach] Goed Het spijt me. >> Nee, nee, nee, nee. Ik denk dat de bubble sort zou de verkeerde weg te gaan. Kom op, die hem vertelde dat? Vorige week herinneren namen we een pauze van code, ten minste voor een dag, en begon zich richt op een hoger niveau ideeën en het oplossen van problemen meer in het algemeen in de context van het zoeken en sorteren, en introduceerden wij iets dat we niet deze naam klap op vorige week, maar asymptotische notatie, de Big O, de Big Omega, en soms de Big Theta notatie, en deze waren gewoon manieren van het beschrijven van de looptijd van algoritmen, hoeveel tijd het duurt voor een algoritme om te draaien. En je kunt dat je sprak over de looptijd herinneren in termen van de omvang van de input, die over het algemeen noemen we n, wat het probleem ook mag zijn, waarbij n het aantal mensen in de kamer, het aantal pagina's in een telefoonboek, en we begonnen om dingen te schrijven zoals O (n ^ 2) of O (n) of O (n log n), en zelfs wanneer de wiskunde niet helemaal uit te werken zo perfect en het was n ² - n / 2 of iets dergelijks We zouden in plaats daarvan gewoon weggooien enkele van de lagere orde termen, en de motivatie er is dat we echt een soort objectieve manier van evalueren de prestaties van programma's of het uitvoeren van algoritmen dat aan het eind van de dag heeft niets bijvoorbeeld met de snelheid van uw computer vandaag. Bijvoorbeeld, als u de uitvoering van bubble sort, of u de uitvoering van samenvoegen sorteren of selectie sorteren op de computer van vandaag, een 2 GHz computer, en je het draait, en het duurt even aantal seconden, volgend jaar is er een 3 GHz of een 4 GHz computer, en je zou dan beweren dat "Wow, mijn algoritme is nu twee keer zo snel, "terwijl in werkelijkheid die duidelijk niet het geval. Het is gewoon de hardware heeft gekregen sneller, maar uw computer nog niet, en dus hebben we echt willen weggooien zaken als veelvouden van 2 of veelvouden van 3 als het gaat om beschrijven hoe snel of hoe traag een algoritme is en eigenlijk alleen maar focussen n on of een factor daarvan, wat kracht daarvan, zoals in het geval van de soorten van vorige week. En herinneren dat met de hulp van merge sort we waren in staat om te doen zo veel beter dan bubble sort en selectie sorteren en zelfs insertion sort. We gingen aan n log n, en opnieuw, herinneren eraan dat log n het algemeen verwijst naar iets dat groeit langzamer dan n, dus n log n tot nu toe was goed want het was minder dan n ². Maar om te bereiken n n inloggen met merge sort wat was de basis kiem van een idee dat we hadden om gebruik te maken dat we ook weer ingezet in week 0? Hoe hebben we slim aanpakken van de sorteer-probleem met merge sort? Wat was de belangrijkste inzicht, misschien? Wie dan ook. Oke, laten we een stap terug. Beschrijf samenvoegen sorteren in je eigen woorden. Hoe is het? Oke, we komen terug roeien naar week 0. Oke, ja. [Onverstaanbaar-student] Oke, goed, dus hebben we de reeks van getallen in 2 stukken. Wij gesorteerd elk van deze stukken, en dan hebben we samengevoegd hen, en we hebben gezien dit idee voor het nemen van een probleem dat is dit grote en hakken op in een probleem dat is dit groot of zo groot. Roep het telefoonboek voorbeeld. Herinneren aan de self-telling algoritme van weken geleden, dus samenvoegen sorteren werd samengevat in de pseudocode hier. Als je n elementen gegeven, eerst was het gezond verstand te controleren. Als n <2 doe het dan niet helemaal niets want als n <2 is n duidelijk 0 of 1, en dus als het 0 of 1 is er niets om te sorteren. Je bent klaar. Uw lijst is al triviaal gesorteerd. Maar voor de rest als je 2 of meer elementen hebben ga je gang en verdeel ze in 2 helften, links en rechts. Sorteer elk van deze helften en vervolgens samenvoegen gesorteerd helften. Maar het probleem hier is dat op het eerste gezicht dit voelt alsof we punteren. Dit is een ronde definitie in dat als ik je gevraagd heb om deze n elementen sorteren en je zegt me dat 'Oke, prima, we sorteren de n / 2 en die n / 2 elementen, " dan is mijn volgende vraag gaat worden "Fine, hoe ga je de n / 2 elementen sorteren?" Maar vanwege de structuur van dit programma, want er is dit referentiemodel, om zo te zeggen, dit speciale geval, dat zegt dat als n is > Sara, oke. Kelly. >> Kelly en? Willy. >> Willy, Sara, Kelly, en Willy. Op dit moment heb ik de vraag gesteld door iemand hoeveel mensen er op dit moment, en ik heb geen idee. Dit is echt een lange lijst, en dus in plaats daarvan ga ik deze truc te doen. Ik ga naar de persoon naast me het grootste deel van het werk te doen stellen, en zodra ze klaar is doet het meeste werk Ik ga naar de minste hoeveelheid werk mogelijk te doen en gewoon voeg 1 aan wat haar antwoord is, dus hier gaan we. Ik ben gevraagd hoeveel mensen er op het podium. Hoeveel mensen zijn op het podium aan de linkerkant van je? Links van mij? >> Oke, maar speel niet vals. Dat is goed, dat klopt, maar als we willen deze logica verder laten we aannemen dat je net wilt om weg te schoppen dit probleem aan de linkerkant van je, dus in plaats van direct antwoord te gaan en gewoon afschuiven. O, hoeveel mensen zijn aan de linkerkant van mij? Hoeveel mensen zijn aan de linkerkant? 1. [Gelach] Oke, dus 0, dus wat nu Willy heeft gedaan wordt u terug uw antwoord deze richting te zeggen 0. Nu, wat moet je doen? >> 1. Oke, dus je bent de 1, dus u zegt: "Oke, ik ga naar 1 toe te voegen naar wat Willy's tellen was, "zo 1 + 0. Je bent nu 1, zodat uw antwoord aan de rechterkant is nu- 1. >> En de mijne zou zijn 2. Goed, dus je neemt het vorige antwoord van 1, het toevoegen van de minimale hoeveelheid werk die je wilt doen, dat is +1. Je hebt nu 2, en je vervolgens met de hand me welke waarde? 3, ik bedoel, sorry, 2. Goed. Nou, we hebben 0 naar links. Dan hadden we 1, en dan voegen we 2, en nu ben je gaf me het nummer 2, en dus ik zeg, oke, +1, 3. Er zijn inderdaad 3 personen die naast mij op het podium, dus we konden natuurlijk gedaan hebben dit zeer lineair, heel veel in de voor de hand liggende manier, maar wat hebben we eigenlijk doen? We namen een probleem van maat 3 in eerste instantie. Daarna brak het naar beneden in een probleem van maat 2, dan is een probleem van de grootte 1, en dan uiteindelijk het nulalternatief was echt, oh, er is niemand daar, op welk punt Willy terug in feite een hard-gecodeerde antwoord een paar keer, en de tweede werd vervolgens omhoog borrelen, borrelen, borrelen, en vervolgens door toevoeging van deze extra 1 we hebben geïmplementeerd dit basisidee van recursie. Nu in dit geval niet echt een probleem oplossen elke effectiever dan hebben we tot nu toe gezien. Maar denk over de algoritmen die we gedaan hebben op het podium tot nu toe. We 8 stukjes papier had op het bord, op video toen Sean was op zoek naar het nummer 7, en wat deed hij echt doen? Nou, heeft hij niet te doen elke vorm van verdeel en heers. Hij deed het niet elke vorm van recursie. In plaats van dat hij net deed deze lineaire algoritme. Maar als we het idee van gesorteerd nummers op het podium introduceerde leven vorige week toen hadden we dit instinct van het gaan naar het midden, op welk punt hadden we een kleine lijst van maat 4 of een andere lijst van grootte 4, en dan hebben we precies hetzelfde probleem hadden, dus we herhalen, herhalen, herhalen. Met andere woorden, we recursed. Hartelijk dank aan onze 3 vrijwilligers hier voor het aantonen van recursie met ons. Laten we eens kijken of we kunnen nu niet maken dit een beetje meer concreet, het oplossen van een probleem dat we weer konden vrij gemakkelijk te doen, maar we zullen het gebruiken als een opstapje naar de uitvoering van dit basisidee. Als ik wil de som van een aantal getallen te berekenen, bijvoorbeeld, als je pas in het nummer 3, Ik wil u de waarde van sigma 3, zodat de som van 3 + 2 + 1 + 0. Ik wil terug te krijgen het antwoord 6, dus we zullen implementeren deze sigma functie, deze optelfunctie dat nog eens,, neemt in input, en vervolgens terug de sommatie van dat aantal helemaal naar beneden naar 0. We kunnen dit doen vrij eenvoudig, toch? We kunnen dit doen met een soort van looping structuur, dus laat me ga je gang en krijg deze gestart. Inclusief stdio.h. Laat me mezelf in de belangrijkste om mee te werken hier. Laten we dit opslaan als sigma.c. Dan ga ik naar binnen hier, en ik ga naar een int n verklaren, en ik ga het volgende doen terwijl de gebruiker niet meewerkt. Terwijl de gebruiker heeft gegeven mij een positief getal laat me ga je gang en vraagt ​​hen voor n = GetInt, en laat mij hen wat instructies over wat te doen, dus printf ("positief geheel getal please"). Gewoon iets relatief simpels als dit zodat tegen de tijd dat we lijn 14 geraakt hebben we nu een positief geheel getal vermoedelijk in n. Nu gaan we iets mee doen. Laat me ga je gang en berekenen de sommatie, dus int som = sigma (n). Sigma is gewoon sommatie, dus ik ben gewoon te schrijven op de liefhebber manier. We noemen het gewoon sigma daar. Dat is de som, en nu ga ik het afdrukken van het resultaat, printf ("De som is% d \ n", som). En dan zal ik terug 0 voor een goede maatregel. We hebben alles gedaan wat dit programma vereist met uitzondering van het interessante deel, die is om daadwerkelijk uitvoering van de sigma-functie. Laat me hier naar beneden naar de bodem, en laat me verklaren functie sigma. Het moet een variabele die is van het type integer te nemen, en welke data type wil ik vermoedelijk terugkeren van sigma? Int, want ik wil het aan mijn verwachtingen op lijn 15. Hierin laat me gaan en uitvoering van deze in een mooie eenvoudige manier. Laten we verder gaan en zeggen: int som = 0, en nu ga ik naar hier een beetje for-lus dat gaat om iets als dit te zeggen, for (int i = 0; I <= aantal; i + +) som + = i. En dan ga ik som terug te keren. Ik zou hebben dit in een aantal manieren. Ik kon een while-lus. Ik had overgeslagen met behulp van de som variabele als ik echt zou willen, maar in het kort, we hoeven alleen maar een functie, dat als ik niet goof verklaart som is 0. Dan herhaalt zich van 0 op omhoog door het aantal, en op elke iteratie voegt dat de huidige waarde voor som en keert dan terug som. Nu, er is een lichte optimalisatie hier. Dit is waarschijnlijk een verspilde stap, maar het zij zo. Dat is prima voor nu. We zijn in ieder geval zijn grondige en gaan 0 helemaal naar boven. Niet erg hard en vrij eenvoudig, maar het blijkt dat met de sigma functie die we dezelfde kans hebben zoals we hier deden op het podium. Op het podium hebben we net geteld hoeveel mensen er naast me, maar in plaats daarvan als we wilden het nummer 3 + 2 + 1 tellen op tot 0 we konden net punter om een ​​functie te dat ik in plaats daarvan omschrijven als recursieve. Hier laten we het doen een snelle geestelijke gezondheid te controleren en zorg ervoor dat ik niet goof. Ik weet dat er in ieder geval een ding in dit programma, dat heb ik verkeerd gedaan. Als ik druk op enter ga ik elke vorm van schreeuwen tegen mij te krijgen? Wat ga ik worden uitgescholden over? Ja, ik vergat het prototype, dus ik ben een functie genaamd sigma on line 15 gebruikt, maar het is niet verklaard tot lijn 22, dus ik best proactief hier naar boven en verklaren een prototype, en ik zal zeggen int sigma (int getal), en dat is het. Het is uitgevoerd aan de onderkant. Of een andere manier kon ik dit oplossen, Ik kon bewegen de functie daar, dat is niet slecht, maar in ieder geval als je programma's beginnen te krijgen lang, eerlijk gezegd, Ik denk dat er enige waarde in altijd met de belangrijkste aan de top zodat je in de lezer kan het bestand openen en dan meteen zien wat het programma doet zonder te zoeken door middel van het op zoek naar die hoofdfunctie. Laten we hier beneden naar mijn terminal-venster, kunt u proberen om sigma maken sigma, en ik verpest hier ook. Impliciete verklaring van de functie GetInt betekent dat ik ben vergeten om wat anders te doen? [Onverstaanbaar-student] Goed, dus blijkbaar een veel voorkomende fout, dus laten we hier zet deze omhoog, cs50.h, en nu laten we terug gaan naar mijn terminal venster. Ik zal het scherm op, en ik zal opnieuw uit te voeren maken sigma. Het lijkt te zijn samengesteld. Laat me nu sigma uit te voeren. Ik typ in het nummer 3, en ik heb wel 6, dus niet een rigoureuze controle, maar in ieder geval lijkt te werken op het eerste gezicht, maar nu laten we rippen uit elkaar, en laten we maken gebruik van eigenlijk het idee van recursie, nogmaals, in een zeer eenvoudige context zodat in een enkele weken wanneer we beginnen met het verkennen liefhebber datastructuren dan arrays hebben we een ander hulpmiddel in de toolkit waarmee manipuleren die datastructuren zoals we zullen zien. Dit is de iteratieve aanpak, de loop-gebaseerde aanpak. In plaats daarvan laat ik nu doen. Laat ik in plaats daarvan zeggen dat de som van het aantal op tot 0 is echt hetzelfde als nummer + sigma (nummer - 1). Met andere woorden, net zoals op het podium sta punted aan elk van de mensen naast me, en zij op hun beurt hielden punteren tot we uiteindelijk een dieptepunt van Willy, die had een hard-gecodeerde antwoord graag 0 terug te keren. Hier nu zijn we net punteren naar sigma dezelfde functie als werd oorspronkelijk genoemd, maar de sleutel inzicht hier is dat we niet sigma belt identiek. We zijn niet passeren in n. We zijn duidelijk voorbij in aantal - 1, dus een iets kleinere probleem iets kleiner probleem. Helaas is dit niet echt een oplossing nog vast en voordat we wat kan worden springen als voor de hand liggend bij een aantal van u laat me gaan en herhaling te maken. Het lijkt te compileren oke. Laat me sigma opnieuw uit te voeren met 6. Oeps, laat me sigma opnieuw uit te voeren met 6. We hebben dit eerder gezien, zij het per ongeluk vorige keer ook. Waarom heb ik deze cryptische segmentation fault? Ja. [Onverstaanbaar-student] Er is geen base case, en meer specifiek, wat waarschijnlijk is er gebeurd? Dit is een symptoom van wat gedrag? Zeg het een beetje luider. [Onverstaanbaar-student] Het is een oneindige lus effectief, en het probleem met oneindige lussen wanneer recursie betrokken in dit geval een functie die zichzelf, wat er gebeurt elke keer als je belt een functie? Nou, terugdenken aan hoe we aangelegd het geheugen in een computer. We gezegd dat er dit stuk genoemd geheugen stack dat onderaan en elke keer als je belt een functie een beetje meer geheugen wordt gezet Op deze zogenaamde stapel met die functie lokale variabelen of parameters, dus als sigma belt sigma gesprekken sigma belt sigma  noemt sigma waar komt dit verhaal eindigen? Nou, het uiteindelijk overschrijdingen het totale bedrag van het geheugen dat u beschikbaar hebben op uw computer. U overspoeld het segment dat je moet blijven binnen, en u deze segmentatie fout te krijgen, core dumped, en wat core dumped betekent is dat ik nu een bestand genaamd kern hebben Dit is een bestand met nullen en enen die daadwerkelijk in de toekomst zal zijn diagnostisch nuttig. Als het niet voor de hand om u waar uw bug is je kunt eigenlijk doen een beetje van forensische analyse, om zo te zeggen, op deze core dump file, wat, nogmaals, is gewoon een hele hoop van nullen en enen dat vertegenwoordigt in wezen de staat van uw programma in het geheugen Momenteel crashte op deze manier. De oplossing hier is dat we niet zomaar blindelings terugkeren sigma, + het aantal sigma een iets kleiner probleem. We moeten een soort van base case hier hebben, en wat moet de base case waarschijnlijk? [Onverstaanbaar-student] Oke, dus zolang het aantal positieve is dat we moeten eigenlijk terug dit, of anders gezegd, als getal, bijvoorbeeld <= aan 0 weet je wat, ik vooruit ga en terug 0, net als Willy deed, en anders ga ik om verder te gaan en terug te keren dit, dus het is niet zo veel korter dan de iteratieve versie die we opgezweept het eerste gebruik van een for-lus, maar merkt dat er dit soort van elegantie aan. In plaats van een getal en het uitvoeren van alle deze wiskunde en het toevoegen van dingen met lokale variabelen je in plaats daarvan te zeggen: "Oke, als dit een super eenvoudig probleem, zoals het aantal is <0, laat me onmiddellijk 0 terug te keren. " We gaan niet aan de ondersteuning van negatieve getallen moeite, dus ik ga hard code de waarde 0. Maar voor de rest, om dit idee van het optellen te implementeren al deze getallen bij elkaar kun je effectief neem een ​​hapje uit van het probleem, net als wij deden hier op het podium, dan punter de rest van het probleem naar de volgende persoon, maar in dit geval de volgende persoon zelf. Het is een identiek genaamd functie. Net voorbij het een kleiner en kleiner probleem telkens en ook al hebben we niet helemaal geformaliseerd dingen in de code hier in dit is precies wat er gaande was in week 0 met het telefoonboek. Dit is precies wat er gaande was in afgelopen weken met Sean en met onze demonstraties van het zoeken naar nummers. Het nemen van een probleem en te delen opnieuw en opnieuw. Met andere woorden, er is een manier om nu te vertalen deze echte wereld construct, dit hogere niveau constructie van verdeel en heers en iets te doen opnieuw en opnieuw in de code, dus dit is iets wat we zullen weer te zien in de tijd. Nu, als een terzijde, als je nieuw bent bij recursie moet je op zijn minst begrijpen nu waarom dit grappig. Ik ga naar google.com, en ik ga op zoek naar een aantal tips en trucs over recursie, in te voeren. Vertel de persoon naast je als ze niet lachen op dit moment. Bedoelde u recursie? Bedoelde u-ah, daar gaan we. Oke, nu dat is de rest van iedereen. Een beetje Paasei er ergens ingebed in Google. Even terzijde, een van de links die we op de website van de cursus voor vandaag is juist dit raster van verschillende sorteren algoritmen, waarvan sommige hebben we gekeken naar vorige week, maar wat er leuk is aan deze visualisatie als je probeert om je geest wrap rond diverse zaken gerelateerd aan de algoritmen weten dat u nu heel eenvoudig beginnen met verschillende soorten ingangen. De ingangen alle omgekeerd ingangen meestal gesorteerd, de ingangen willekeurige enzovoort. Als je probeert om, opnieuw, te onderscheiden die dingen in je geest beseffen dat deze URL op de website van de cursus op de Lectures pagina kan je helpen reden door een aantal van deze. Vandaag hebben we eindelijk om dit probleem op te lossen terug van een tijdje, en dat was dat deze swap functie gewoon niet werken, en wat was het fundamentele probleem met deze functie swap, waarvan het doel was wederom een ​​waarde wisselen hier en hier zodanig dat dit gebeurt? Deze niet echt werken. Waarom? Ja. [Onverstaanbaar-student] Precies, de verklaring voor deze bugginess simpelweg omdat wanneer u belt functies in C en die functies te nemen argumenten, zoals a en b hier, u passeert in kopieën van welke waarde u het verstrekken van die functie. U bent niet verstrekken van de oorspronkelijke waarden zelf, dus we zagen dit in het kader van buggyc, buggy3.c, die een beetje zoiets als dit zag. Herinneren dat we x en y geïnitialiseerd op 1 en 2 respectievelijk. Vervolgens hebben we uitgeprint wat ze waren. Vervolgens heb ik beweerde dat ik ze wisselen door te bellen naar swap van x, y. Maar het probleem was dat de swapping werkte, maar alleen in het kader van de swap functioneren zelf. Zodra we raken lijn 40 die verwisseld waarden werden weggegooid, en dus niets in de oorspronkelijke functie belangrijkste was eigenlijk helemaal veranderd, dus als je denkt dat toen over hoe dit eruit ziet in termen van ons geheugen als dit linkerkant van het bord staat voor- en ik zal mijn best doen voor iedereen om te zien-als dit linkerkant van het bord vertegenwoordigt, zeg, uw RAM-geheugen, en de stapel gaat over opgroeien op deze manier, en we noemen een functie als hoofd-, en de belangrijkste heeft 2 lokale variabelen, x en y, laten we hier beschrijven die als x, en laten we deze hier beschrijven als y, en laten we in de waarden 1 en 2, dus dit hier de belangrijkste is, en als belangrijkste noemt de swap-functie van het besturingssysteem geeft de swap-functie zijn eigen baan van het geheugen op de stack, zijn eigen frame op de stapel, om zo te zeggen. Het wijst ook 32 bits voor deze ints. Het overkomt noemen ze a en b, maar dat is volkomen willekeurig. Het zou hen geroepen heb wat het wil, maar wat gebeurt er als de belangrijkste oproepen swap is duurt dit 1, plaatst een kopie daar, plaatst een kopie daar. Er is 1 andere lokale variabele in ruil, hoewel, genoemd wat? >> Tmp. Tmp, dus laat me mezelf nog een 32 bits hier, en wat heb ik gedaan in deze functie? Ik zei int tmp krijgt een, dus een heeft 1, dus ik deed dit toen we voor het laatst gespeeld met dit voorbeeld. Dan krijgt a b, dus b is 2, dus nu dit wordt 2, en nu b krijgt temp, dus temp is 1, dus nu b wordt dit. Dat is geweldig. Het werkte. Maar zodra de functie terugkeert swap geheugen verdwijnt effectief, zodat het kan worden hergebruikt door een andere functie in de toekomst en voornaamste is uiteraard volledig ongewijzigd. We moeten een manier fundamenteel oplossen van dit probleem, en vandaag gaan we eindelijk een manier om dit te doen, waarbij we kunnen introduceren iets genaamd een pointer. Het blijkt dat we dit probleem oplossen niet door het passeren van de kopieën van x-en y- maar in plaats daarvan door het passeren in wat, denk je, denk om de swap-functie? Ja, hoe zit het met het adres? We hebben nog niet echt gesproken over adressen in veel detail, maar als dit bord is mijn computer het geheugen We kunnen zeker gaan nummeren van de bytes in mijn RAM-geheugen en zeggen dat dit byte # 1, is dit byte # 2, # 3 byte, byte # 4, byte # ... 2 miljard als ik 2 gigabyte aan RAM-geheugen, dus we konden zeker komen met een aantal willekeurige nummering voor elke individuele bytes in het geheugen van de computer wordt. Wat als in plaats daarvan als ik roep swap in plaats van pas in kopieën van x-en y- waarom niet ik in plaats daarvan geschiedde in het adres van x hier, het adres van y hier in wezen het postadres van x en y want dan ruilen, als hij op de hoogte het adres in het geheugen van x en y, dan ruilen, als we getraind hem een ​​beetje, hij zou kunnen rijden naar dat adres, om zo te zeggen, x, en verander het getal daar, dan rijden naar het adres van y, daar verandert het nummer, zelfs wanneer niet daadwerkelijk krijgen kopieën van die waarden zelf, dus ook al hadden we het over dit als de belangrijkste geheugen van en dit als swap geheugen van de machtigen en de gevaarlijke deel van C is dat elke functie kan het geheugen raken overal in de computer, en dit is krachtig in dat je heel fancy dingen doen met computerprogramma's in C. Dit is gevaarlijk, want je kunt ook verpesten heel gemakkelijk. In feite een van de meest gebruikte manieren programma's tegenwoordig worden benut nog steeds voor een programmeur niet te realiseren dat hij of zij is waardoor een data geschreven worden op een locatie in het geheugen, dat niet de bedoeling was. Bijvoorbeeld, hij of zij verklaart een array van maat 10 maar dan per ongeluk probeert tot 11 bytes gebracht die array van het geheugen, en je begint te raken delen van het geheugen die niet meer geldig zijn. Gewoon om contextuele dit, kunnen sommige van jullie weten dat software vraagt ​​vaak u voor serienummers of registratie sleutels, Photoshop en Word en programma's als dit. Er bestaan ​​scheuren, zoals sommigen van jullie weten, waar je online kan een beetje programma uit te voeren, en voila, niet meer verzoek om een ​​serienummer. Hoe wordt dat het werken? In veel gevallen zijn deze dingen zijn gewoon te vinden in de computers tekstsegmenten in werkelijke van de computer nullen en enen waar is die functie waar het serienummer wordt gevraagd, en u overschrijven die ruimte, of terwijl het programma loopt je kunt achterhalen waar de sleutel is werkelijk opgeslagen met behulp van iets genaamd een debugger, en je kunt software op die manier te kraken. Dit wil niet dat dit onze doelstelling zeggen voor de komende paar dagen, maar het heeft zeer reële-wereld vertakkingen. Dat men er met betrekking diefstal van software, maar er is ook een compromis van complete machines. In feite, als websites deze dagen worden benut en gecompromitteerd en data wordt gelekt en wachtwoorden worden gestolen dit zeer vaak betrekking op slecht beheer van het geheugen, of, in het geval van databases, het niet anticiperen hoor en wederhoor ingang, zodat er meer op dat er in de komende weken, maar voor nu slechts een sneak preview van de soort schade die u kunt doen door niet helemaal begrijpen hoe dingen werken onder de kap. Laten we gaan over het begrijpen waarom dit is gebroken met een instrument dat zal meer en meer nuttige als onze programma's steeds complexer. Tot nu toe als je hebt gehad een bug in uw programma hoe ben je gek over debuggen het? Wat heb je technieken tot nu toe, of geleerd door uw TF of gewoon autodidact? [Student] Printf. Printf, dus printf is waarschijnlijk je vriend in dat als u wilt zien wat is er aan de binnenkant van uw programma zet je gewoon printf hier, printf hier, printf hier. Dan moet je het draait, en je krijgt een heleboel dingen op het scherm die u kunt gebruiken om vervolgens af te leiden wat er werkelijk mis gaat in uw programma. Printf heeft de neiging om een ​​zeer krachtig ding, maar het is een zeer handmatig proces. Je moet hier zet een printf, een printf hier, en als je het binnen zetten van een lus je zou kunnen krijgen 100 lijnen van de output die je dan moeten uitpluizen. Het is niet een erg gebruiksvriendelijk of interactieve mechanisme voor debuggen van programma's, maar gelukkig bestaat er alternatieven. Er is een programma, bijvoorbeeld, genaamd GDB, de GNU Debugger, dat is een beetje geheimzinnig in de manier waarop je het gebruikt. Het is een beetje ingewikkeld, maar eerlijk gezegd, dit is een van die dingen waar als je in deze en volgende week de extra uren om zoiets als GDB begrijpen het bespaart u waarschijnlijk tientallen uren op de lange termijn, dus met dat, laat me je een teaser van hoe dit ding werkt. Ik ben in mijn terminal-venster. Laat me gaan, en slaat deze programma buggy3. Het is al up-to-date. Laat ik voer het uit, net als wij deden een tijdje terug, en inderdaad, het is gebroken. Maar waarom is dit? Misschien heb ik het verpest de swap-functie. Misschien is het een en b. Ik ben niet helemaal verplaatsen ze rond correct. Laat me ga je gang en doen. In plaats van alleen buggy3 draaien Laat me maar dit programma GDB te voeren, en ik ga om het te vertellen aan buggy3 lopen, en ik ga een command line argument-tui omvatten, en wij zetten dit in de toekomst problemen op spec te herinneren. En nu dit zwart-wit-interface dook dat, nogmaals, is een beetje overweldigend op het eerste, want er is dit allemaal informatie over de garantie hier beneden, maar in ieder geval is er iets bekend. In de bovenkant van het venster is mijn werkelijke code, en als ik ga hier laat mij gaat u naar de top van mijn dossier, en inderdaad, er is buggy3.c, en kennisgeving aan de onderkant van dit venster Ik heb deze GDB prompt. Dit is niet hetzelfde als mijn normale John Harvard prompt. Dit is een aanwijzing dat gaat mij toe om GDB te controleren. GDB is een debugger. Een debugger is een programma waarmee u door uitvoering van uw programma regel voor regel voor regel, langs de weg doen wat je wilt het programma, zelfs belfuncties, of op zoek, nog belangrijker, op verschillende variabele waarden. Laten we verder gaan en dit doen. Ik ga om verder te gaan en in run typ bij GDB's prompt, dus merken in de linkerbenedenhoek van het scherm heb ik getypt lopen, en ik heb druk op enter, en wat deed dat te doen? Het liep letterlijk mijn programma, maar ik heb niet echt veel zien gaan hier want ik heb niet echt verteld de debugger om te pauzeren op een bepaald moment in de tijd. Gewoon typen run loopt het programma. Ik denk niet echt zien niets. Ik kan het niet manipuleren. In plaats daarvan laat mij dit doen. Op dit GDB prompt laat me in plaats daarvan breuk typen, in te voeren. Dat is niet wat ik bedoelde te typen. Laten we in plaats daarvan typ pauze belangrijkste. Met andere woorden, ik wil zoiets als een breekpunt in te stellen, die treffend wordt genoemd omdat het zal breken of te pauzeren uitvoering van uw programma op die bepaalde plaats. Belangrijkste is de naam van mijn functie. Merk op dat GDB is behoorlijk slim. Het bedacht dat de belangrijkste gebeurt er met ongeveer beginnen bij regel 18 van buggy3.c, en dan hier op te merken in de linkerbovenhoek b + ligt direct naast lijn 18. Dat is me eraan herinneren dat ik een breekpunt op lijn 18. Deze keer als ik run wilt typen, ik ga mijn programma uit te voeren tot het hits dat breekpunt, zodat het programma wordt onderbroken voor mij op lijn 18. Daar gaan we, uit te voeren. Niets lijkt te zijn gebeurd, maar een termijn van ten linksonder start programma, buggy3, breekpunt 1 in de belangrijkste bij buggy3.c lijn 18. Wat kan ik nu doen? Merk op dat ik kan beginnen met het typen zaken als print, niet printf, print x, en nu dat is vreemd. De $ 1 is gewoon een nieuwsgierigheid, zoals we zullen zien telkens als u print iets krijg je een nieuwe $ waarde. Dat is, zodat u kunt terug te verwijzen naar de vorige waarden voor het geval dat, maar voor nu wat druk wordt me te vertellen is dat de waarde van x op dit punt in het verhaal kennelijk 134514032. Wat? Waar kwam dat zelfs vandaan? [Onverstaanbaar-student] Inderdaad, dit is wat we noemen een vuilnis waarde, en we hebben niet gesproken over dit nog niet, maar de reden dat je variabelen te initialiseren is natuurlijk zo dat ze enige waarde die je wilt dat ze te hebben. Maar de vangst is te herinneren dat u de variabelen declareren zoals ik deed een ogenblik geleden in mijn sigma voorbeeld zonder dat het geven van een waarde. Herinneren wat ik deed hier over in sigma. Ik verklaarde n, maar welke waarde heb ik geven? Geen, omdat ik wist dat er in de volgende paar regels GetInt zou zorgen voor het probleem van toe te kennen binnenkant van n. Maar op dit punt in het verhaal van lijn 11 en lijn 12 en lijn 13 en lijn 14 gedurende al die verschillende lijnen wat is de waarde van n? In C je weet het gewoon niet. Het is over het algemeen wat vuilnis waarde, sommige volledig willekeurig getal dat is overgebleven in hoofdzaak uit een aantal eerdere functie te zijn uitgevoerd, zodat uw programma draait herinneren eraan dat de functie-functie, de functie, de functie krijgt. Al deze frames te krijgen op het geheugen, en dan die functies terug, en net zoals ik suggereerde met de gum hun geheugen uiteindelijk wordt hergebruikt. Nou, het is gewoon zo gebeurt het dat deze variabele x in dit programma lijkt te hebben bevat een aantal vuilnis waarde als 134514032 van sommige vorige functie, niet een die ik geschreven heb. Het kan iets die effectief geleverd met het besturingssysteem, een functie onder de kap. Oke, dat is prima, maar laten we nu verder te gaan naar de volgende regel. Als ik typ "volgende" bij mijn GDB prompt en ik druk op enter, merkt dat de aandacht verplaatst naar lijn 19, maar de logische implicatie is dat lijn 18 is nu klaar uitvoeren, dus als ik weer typ "print x" Ik zou nu zie 1, en inderdaad, dat doe ik. Nogmaals, de $ spul is een manier van GDB u eraan te herinneren wat de geschiedenis van de prints zijn die je gedaan hebt. Laat me nu ga je gang en uit te printen y, en inderdaad, y wat gekke prijs ook, maar geen groot probleem, omdat in lijn 19 zijn we op het punt om het toe te wijzen de waarde 2, dus laat me weer typ "next". En nu we het toch over de printf lijn. Laat mij afdruk x. Laat mij afdrukken y. Eerlijk gezegd, ik word een beetje moe van het drukken dit. Laat mij in plaats daarvan "scherm x" en "display y ', typt u en nu elke keer als ik typ een opdracht in de toekomst Ik zal herinnerd worden aan wat x en y, wat is x en y, wat is x en y. Ik kan ook, als een terzijde, type in "info lokale bevolking." Info is een speciaal commando. Locals betekent dat het toont me de lokale variabelen. Voor het geval ik het vergeet of dit is een gekke, gecompliceerde functie dat ik of iemand anders heeft geschreven info lokale bevolking zal u vertellen wat zijn alle lokale variabelen binnen deze lokale functie die u zou kunnen schelen als je wilt rondneuzen. Nu, printf staat op het punt uit te voeren, dus laat me ga je gang en typ je gewoon "volgende". Omdat we in deze omgeving dat we niet echt zien van het hier uit te voeren naar beneden, maar let op het wordt hier een beetje verminkte. Maar let op het is het scherm zijn er dwingende, dus het is niet een perfect programma hier, maar dat is oke, want ik kan altijd rond te snuffelen met behulp van druk als ik dat wil. Laat me typ de volgende weer, en nu hier is het interessante deel. Op dit punt in het verhaal y is 2, en x 1, zoals voorgesteld hier, en opnieuw, De reden dat dit automatisch weergeven van nu is, want ik gebruik het commando scherm x en y scherm, dus het moment dat ik typ volgende in theorie X en Y moeten worden verwisseld. Nu, we weten al dat niet gaat het geval zijn, maar we zullen zien in een moment hoe we dieper om erachter te komen waarom dat is waar. Volgende helaas en, y is nog steeds 2 en x is nog steeds 1, en ik kan bevestigen zo veel. Print x, print y. Inderdaad, geen swapping eigenlijk is gebeurd, dus laten we beginnen dit over. Het is duidelijk dat swap is gebroken. Laten we in plaats daarvan "run" weer te typen. Laat ik zeggen ja, ik wil het opnieuw vanaf het begin, in te voeren. Nu ben ik een back-up op regel 18. Let nu op x en y zijn weer vuilnis waarden. Volgende, volgende, volgende, volgende. Als ik me verveel ik kan ook gewoon type N voor de volgende. U kunt afkorten aan de kortst mogelijke reeks tekens. Swap is nu gebroken. Laten we duiken in, dus in plaats van te typen volgende, nu ga ik naar stap typen zodat ik ga naar binnen stappen van deze functie zodat ik kan er doorheen lopen, dus ik raakte stap en voer. Merk op dat de aandacht springt naar beneden lager in mijn programma op lijn 36. Nu, wat zijn de lokale variabelen? Info lokale bevolking. Niets gewoon nog niet omdat we niet hebben gekregen om die lijn, dus laten we verder gaan en zeggen: "volgende". Nu lijken we tmp, print tmp hebben. Garbage waarde, toch? Ik denk het wel. Hoe zit het met het afdrukken van een, print b, 1 en 2? In een moment, zodra ik typ volgende weer tmp gaat nemen op een waarde van 1, hopelijk, omdat tmp zal worden toegewezen aan de waarde van een. Nu gaan we een-, print-b te drukken, maar nu afdrukken tmp, en het is inderdaad 1. Laat mij gaan doen. Laat mij gaan doen. Ik ben klaar met de swap-functie. Ik ben binnen nog steeds van het in lijn 40, dus laat me het afdrukken van een, afdrukken b, en kan me niet schelen wat tmp is. Het lijkt erop dat swap is correct als het gaat om swapping a en b. Maar als ik nu naast typen, ik ga terug naar regel 25, en natuurlijk, als ik typ in x en druk y ze zijn nog steeds onveranderd, dus we hebben niet het probleem opgelost. Maar diagnostisch nu misschien met deze GDB programma we hebben in ieder geval gekregen een stap dichter bij het begrijpen wat is er mis zonder strooisel onze code door er een printf hier, printf hier, printf hier en dan loopt het opnieuw en opnieuw proberen te achterhalen wat er fout gaat. Ik ga om verder te gaan en uit te stoppen met dit geheel met stoppen. Het zal dan zeggen, "Quit eigenlijk?" Ja. Nu ben ik terug op mijn normale prompt, en ik ben klaar met behulp van GDB. Even terzijde, heb je niet nodig om deze-tui vlag. In feite, als je het weg laten je in wezen de onderste helft van het scherm. Als ik typ pauze belangrijkste en voer Ik kan nog steeds lopen mijn programma, maar wat het zal doen, is meer tekstueel gewoon laat me de huidige regel een voor een. De-tui, tekstuele gebruikersinterface, gewoon laat u meer van het programma in een keer, dat is waarschijnlijk een beetje conceptueel eenvoudiger. Maar inderdaad, ik kan gewoon gaan doen, volgende, volgende, en ik ga om een ​​lijn te zien in een tijd, en als ik echt wil zien wat er aan de hand Ik kan typen lijst en zie een hele hoop van naburige lijnen. Er is een video die we hebben gevraagd dat u pas op voor probleem sets 3 waarin Nate dekt een deel van de fijne kneepjes van het GDB, en dit is een van die dingen, eerlijk, waar een aantal niet-triviale percentage van je zal nooit aan GDB, en dat zal een slechte zaak want letterlijk zul je uiteindelijk meer tijd besteden aan later dit semester jagen bugs dan zou je als je in dat half uur / uur deze en volgende week leren om comfortabel te krijgen met GDB. Printf was je vriend. GDB moet nu je vriend. Eventuele vragen over GDB? En hier is een korte lijst van enkele van de meest krachtige en nuttige commando's. Ja. >> Kunt u een string? Kunt u een string? Absoluut. Het hoeft niet alleen gehele getallen. Als een variabele s is een string typ je gewoon in print s. Het zal je laten zien wat die string variabele is. [Onverstaanbaar-student] Het geeft je het adres en de string zelf. Het zal u tonen beide. En een laatste ding, alleen maar omdat deze zijn goed om te weten. Backtrace en frame, laat mij duiken in deze nog een laatste keer, exact dezelfde programma met GDB. Laat me ga je gang en laat de tekstuele gebruikersinterface versie, breken belangrijkste. Laat me ga je gang en start opnieuw. Hier ben ik. Laat me nu gaan volgende, volgende, volgende, volgende, volgende, stap, in te voeren. En nu veronderstel dat ik nu bewust in ruil, maar ik heb zoiets van "Damn, wat was de waarde van x? ' Ik kan niet meer doen x. Ik kan het niet y, omdat ze niet in omvang. Ze zijn niet in de juiste context, maar geen probleem. Ik kan typen backtrace. Dat toont mij alle functies die zijn uitgevoerd tot dit punt in de tijd. Merk op dat de een op de bodem hoofdzaak samenvalt met belangrijkste wezen op de bodem van onze foto hier. Het feit dat swap is boven het lijnen met swap wordt boven in het geheugen hier, en als ik wil terug tijdelijk naar hoofd kan ik zeggen "frame". Welk nummer? Belangrijkste is frame # 1. Ik ga om verder te gaan en te zeggen "frame 1." Nu ben ik terug in de belangrijkste, en ik kan printen x, en ik kan afdrukken y, maar ik kan niet afdrukken op a of b. Maar ik kan als ik zeg, "Oke, wacht even. Waar was de swap?" Laat me ga je gang en zeg "frame 0." Nu ben ik terug waar ik wil zijn, en als een terzijde, er zijn andere commando's ook, alsof je echt vervelen typen volgende, volgende, volgende, volgende, kunt u over het algemeen dingen zeggen als "next 10," en dat zal u door de volgende 10 regels. U kunt ook schrijven "continue" als je echt beu stappen doorheen. Ga verder zal lopen uw programma zonder onderbreking totdat hij raakt een andere breekpunt, hetzij in een lus of lager in uw programma. In dit geval bleef het einde, en het programma verlaten normaal. Dit is een mooie manier om, inferieure proces. Gewoon het programma verlaten normaal. Meer daarover in de video en bij het debuggen sessies te komen. Dat was veel. Laten we hier nemen onze 5-minuten pauze, en we zullen terug met structs en bestanden. Als u dook PSET deze week al zult u weten dat we gebruiken in de verdeelsleutel, de broncode die wij aan u als uitgangspunt, een aantal nieuwe technieken. In het bijzonder, introduceerden we dit nieuwe zoekwoord genaamd struct, voor structuur, zodat wij aangepaste variabelen van soorten. We hebben ook introduceerde de notie van file I / O, invoer-en uitvoerbestanden, en dit is, zodat we kunnen besparen de staat van uw Scramble bord naar een bestand op schijf zodat het onderwijs jongens en ik kan begrijpen wat is er aan de binnenkant van uw programma zonder handmatig te spelen tientallen games van Scramble. We kunnen dit doen meer automatedly. Dit idee van een struct lost een vrij dwingende probleem. Stel dat we willen wat programma uit te voeren dat houdt een of andere manier spoor van informatie over studenten, en studenten zou kunnen hebben, bijvoorbeeld een ID, een naam en een huis op een plek als Harvard, dus deze zijn 3 stukjes informatie we willen rond houden, dus laat me ga je gang en beginnen met het schrijven van een klein programma hier, onder meer stdio.h. Laat mij het doen zijn cs50.h. En dan beginnen mijn belangrijkste functie. Ik zal niet de moeite met een command line argumenten, en hier wil ik een student, dus ik ga zeggen een student heeft een naam, dus ik ga zeggen "string naam." Dan ga ik zeggen dat een student ook een ID heeft, dus int id, en een student heeft een huis, dus ik ben ook gaan zeggen "string huis." Dan zal ik deze bestellen een beetje schoner als dit. Oke, nu heb ik 3 variabelen waarmee een student te vertegenwoordigen, dus "een student." En nu wil ik deze waarden te bevolken, dus laat me ga je gang en zeg iets als "Id = 123." Naam gaat David te krijgen. Laten we zeggen dat huis gaat Mather krijgen, en dan ga ik iets doen willekeurig zoals printf ("% s, waarvan de ID is% d, woont in% s. En nu, wat wil ik de stekker in hier, de een na de andere? Naam, id, huis, return 0. Oke, tenzij ik het verpest hier ergens Ik denk dat we een vrij goed programma dat een student opgeslagen. Natuurlijk, dit is niet zo interessant. Wat als ik wil 2 studenten hebben? Dat is geen big deal. Ik kan ondersteunen 2 personen. Laat me gaan en te markeren dit en hier naar beneden gaan, en ik kan "id = 456" zeggen voor iemand als Rob woont in Kirkland. Oke, wacht, maar ik kan niet bellen deze hetzelfde, en het lijkt erop dat ik ga te hebben om deze te kopiëren, zo wil ik zeggen dat deze zullen Davids variabelen, en laat me een aantal kopieën van deze te krijgen voor Rob. We noemen deze Rob, maar dit is niet van plan om te werken nu want ik heb-wacht, laten we mij veranderen in ID1, naam1 en House1. Rob zal zijn 2, 2. Ik heb om dit te veranderen hier, hier, hier, hier, hier, hier. Wacht, hoe zit het met Tommy? Laten we dit weer. Natuurlijk, als je nog steeds denkt dat dit een goede manier om dit te doen, het is niet, dus kopiëren / plakken slecht. Maar we losten dit een week geleden. Wat was onze oplossing toen we wilden meerdere exemplaren van hetzelfde gegevenstype hebben? [Studenten] Een array. Een array, dus laat me proberen om dit op te ruimen. Laat me wat ruimte voor mezelf aan de top, en laat me in plaats daarvan dit hier doen. We noemen deze mensen, en in plaats daarvan ik ga zeggen: "int id," en ik ga tot en met 3 van ons te steunen voor nu. Ik ga zeggen "string namen," en ik zal steunen 3 van ons, en dan ga ik om te zeggen "string huizen," en ik ga tot en met 3 van ons te steunen. Nu in hier in plaats van David om zijn eigen lokale variabelen kunnen we te ontdoen van die. Dat voelt goed dat we dit opruimen. Ik kan dan zeggen David gaat worden [0] en namen [0] en huizen [0]. Rob en we kunnen eveneens besparen op deze. Laten we dit hier beneden, dus hij gaat willekeurig zijn ids [1]. Hij gaat zijn namen [1], en tenslotte huizen [1]. Nog steeds een beetje vervelend, en nu heb ik om dit uit, dus laten we zeggen "namen [0], id [0], huizen [0], en laten we meervoudig maken dit. Ids, ids, ids. En nogmaals, ik doe het, dus nogmaals, ik ben al toevlucht te kopiëren / plakken weer, dus kansen zijn er hier een andere oplossing. Ik kan waarschijnlijk dit opruimen verder met een lus of iets dergelijks, Dus in het kort, het is een beetje beter, maar nog steeds voelt als Ik ben toevlucht te kopiëren / plakken, maar zelfs dit, ik beweer, is niet echt fundamenteel de juiste oplossing, omdat wat als we besluiten ergens weet je wat? We hebben echt had moeten opslaan van e-mailadressen voor David en Rob en iedereen in dit programma. We moeten ook telefoonnummers. We moeten ook slaan nood telefoonnummers. We hebben al deze stukjes data die we willen opslaan, dus hoe ga je over om dat te doen? U verklaart een andere array op de top, en dan moet je handmatig toevoegen Een e-mailadres [0], e-mailadres [1] David en Rob enzovoort. Maar er is eigenlijk alleen maar een veronderstelling die ten grondslag liggen dit ontwerp dat ik met behulp van de honor-systeem om te weten dat [I] in elk van de verschillende arrays gewoon zo gebeurt om te verwijzen naar dezelfde persoon, dus [0] in ids is nummer 123, en ik ga die namen aannemen [0] is dezelfde persoon de naam en huizen [0] is dezelfde persoon huis enzovoort voor alle verschillende arrays die ik maak. Maar let erop dat er geen fundamentele koppeling onder die drie stukjes informatie, id, naam en huis, hoewel de entiteit we te modelleren proberen in dit programma is niet arrays. Arrays zijn alleen deze programmatische manier om dit te doen. Wat we echt willen modelleren in ons programma is een persoon als David, een persoon als Rob binnenkant van die of inkapselen is een naam en ID en een huis. Kunnen we een of andere manier uitdrukken dit idee van inkapseling waarbij een persoon heeft een ID, een naam en een huis en niet hun toevlucht tot echt deze hack waarbij we gewoon vertrouwen dat beugel iets verwijst naar dezelfde menselijke entiteit in elk van deze verschillende arrays? We kunnen dit doen. Laat me boven hoofd gaan voor nu, en laat mij mijn eigen data type voor echt de eerste keer. We gebruikten deze techniek in Scramble, maar hier ga ik verder te gaan en een data type te maken, en weet je wat, ik ga noemen student of persoon, en ik ga gebruiken typedef voor definiëren een type. Ik ga zeggen dat dit is een structuur, en dan deze structuur gaat worden van het type student, zullen we zeggen, ook al is het nu een beetje gedateerd voor mij. We zeggen "int id." We zeggen "string naam." Dan zullen we zeggen "string huis" dus nu aan het einde van deze paar regels code Ik heb net geleerd clang dat er sprake is een gegevenstype naast ints, naast strijkers, naast verdubbelt, naast praalwagens. Vanaf dit moment in de tijd lijn 11, is er nu een nieuw gegevenstype genoemd studenten, en nu kan ik verklaren een student variabele waar ik wil, dus laat me ga hier naar mensen. Nu kan ik te ontdoen van deze, en ik kan terug naar beneden naar David hier, en voor David kan ik eigenlijk zeggen dat David, kunnen we de variabele letterlijk vernoemen mezelf, gaat worden van het type student. Dit ziet er misschien een beetje raar, maar dit is niet zo heel verschillend uit verklaren iets als een int of een string of een float. Het gebeurt gewoon zo genoemd te worden studenten nu, en als ik iets wil zetten binnen van deze structuur Ik heb nu een nieuw stuk van de syntaxis te gebruiken, maar het is vrij eenvoudig, david.id = 123, david.name = "David" in de hoofdstad van D, en david.house = "Mather," en nu kan ik hier te ontdoen van dit spul. Merk op dat we nu onze vernieuwde programma in echt een veel betere manier in dat nu ons programma weerspiegelt de echte wereld. Er is een real-world notie van een persoon of een student. Hier hebben we nu een C-versie van een persoon of meer specifiek een student. Binnenkant van die persoon zijn deze relevante kenmerken, ID, naam en huis, dus Rob wordt in wezen hetzelfde hier beneden, zodat studenten rob, en nu rob.id = 456, rob.name = "Rob." Het feit dat de variabele heet Rob soort is zinloos. We konden noemen het x-of y-of z. We noemden het Rob te zijn semantisch consistent, maar echt de naam is binnenkant van dat veld zelf, dus nu heb ik dit. Dit betekent ook niet het gevoel dat het beste ontwerp in dat ik hard heb gecodeerd David. Ik heb hard gecodeerd Rob. En ik heb nog een beroep doen op een aantal kopieer-en elke keer als ik wil nieuwe variabelen plakken. Bovendien, ik moet blijkbaar geven elk van deze variabelen een naam, hoewel ik zou veel liever beschrijven deze variabelen  meer in het algemeen als studenten. Nu kunnen we samenvoegen de ideeën die zijn goed voor ons werken en in plaats daarvan zeggen: "Weet je wat, geef me een variabele genaamd studenten, en laten we hebben het van grootte 3, "dus nu kan ik dit verder te verfijnen, zich te ontdoen van de handmatig verklaarde David, en ik kan in plaats daarvan iets zeggen als studenten [0] hier. Ik kan dan zeggen studenten [0] hier, studenten [0] hier, enzovoort, en ik kan gaan rond en schoon dat voor Rob. Ik zou ook gaan over het nu misschien het toevoegen van een lus en het gebruik van GetString en GetInt om daadwerkelijk deze waarden te krijgen van de gebruiker. Ik zou kunnen gaan over het toevoegen van een constante, want dit is over het algemeen een slechte gewoonte naar de harde code een aantal willekeurig aantal als 3 hier en dan gewoon onthouden dat je moet niet meer dan 3 studenten in te stoppen. Het zou waarschijnlijk beter zijn om # gebruik te definiëren aan de bovenkant van mijn dossier en factor die uit zo, inderdaad, laat me ga je gang en generaliseren dit. Laat me open te stellen een voorbeeld dat is onder de huidige voorbeelden vooraf structs1. Dit is een compleet programma dat gebruik maakt van # hier definiëren up en zegt dat we gaan 3 studenten hebben standaard. Hier ben ik waarbij een klasse ter waarde van studenten, dus een klaslokaal van studenten, en nu ben ik met behulp van een lus alleen maar om de code een beetje meer elegante, bevolken de klas met input van de gebruiker, dus herhalen van i = 0 op maximaal studenten, dat is 3. En dan heb ik de gebruiker vragen in deze versie  wat is de student-ID, en ik krijg het met GetInt. Wat is de student de naam, en dan krijg ik het met GetString. Wat is de student het huis? Ik krijg het met GetString. En dan aan de onderkant ik hier net besloten om te veranderen hoe ik deze af te drukken en om daadwerkelijk gebruik maken van een lus, En wie ben ik afdrukken? Volgens de opmerking die ik heb afgedrukt iedereen in Mather, en dat is het dus Rob en Tommy enzovoort-eigenlijk Tommy's in Mather. Tommy en David zou worden afgedrukt in dit geval, maar hoe wordt dit werkt? We hebben niet gezien deze functie voor, maar neem een ​​gok wat dit doet. Vergelijkt strings. Het is een beetje niet-duidelijk hoe het strings vergelijkt want het blijkt als het resultaat 0, dat betekent dat de snaren zijn gelijk. Als het weer een -1 dat betekent een komt alfabetisch vóór de andere, en als het terugkeert +1 dat betekent dat de andere woord komt alfabetisch voor de andere, en je kunt kijken online of in de man pagina om precies te zien welke kant is dat, maar dit alles wordt nu aan het doen is het zegt als de [i]. woning is gelijk aan "Mather" dan ga je gang en ga zo maar uit te printen en zo is in Mather. Maar hier is iets wat we niet eerder hebben gezien, en we zullen terugkeren naar dit. Ik kan me niet herinneren ooit te hebben om dit te doen in een van mijn programma's. Gratis is blijkbaar verwijst naar het geheugen, het vrijmaken van geheugen, maar wat geheugen ben ik blijkbaar te bevrijden in deze lus aan de onderkant van dit programma? Het lijkt alsof ik het vrijmaken van iemands naam en een persoon het huis, maar waarom is dat? Het blijkt al die weken dat u geweest bent GetString met behulp van we hebben soort van is de invoering van een bug in elke een van uw programma's. GetString het ontwerp geheugen toewijst, zodat het kan terugkeren naar je een string, als David, of Rob, en je kunt dan doen wat je wilt met die string in je programma, want we hebben het geheugen voor u gereserveerd. Het probleem is al die tijd elke keer als je belt getString wij, de auteurs van GetString, zijn gevraagd het besturingssysteem om ons een beetje van RAM voor deze string. Geef ons een beetje van RAM voor deze volgende string. Geef ons wat meer RAM-geheugen voor deze volgende string. Wat u, de programmeur, nog nooit gedaan geeft ons dat het geheugen terug, dus voor deze enkele weken alle programma's die u hebt geschreven hebben gehad wat een geheugen sprong genoemd waarbij ze blijven gebruiken meer en meer geheugen elke keer als je belt GetString, en dat is prima. We hebben bewust doen dat in de eerste weken, want het is niet zo interessant om zorgen te maken over waar de string vandaan komt. Alles wat je wilt is het woord Rob om terug te komen wanneer de gebruiker het erin Maar vooruit hebben we nu om te beginnen om meer geavanceerde hierover. Elke keer dat we geheugen toewijzen we beter uiteindelijk geef het terug. Anders in de echte wereld op je Mac of PC die u zou kunnen hebben af ​​en toe ervaren symptomen waar de computer is tot stilstand uiteindelijk of de domme draaiende strandbal is gewoon het bezetten van de computer volledige aandacht en je kunt geen dingen doen. Dat kan worden verklaard door een aantal bugs, maar onder hen mogelijke bugs worden dingen genoemd geheugenlekken waarbij iemand die schreef dat stukje software die u gebruikt niet herinneren om geheugen vrij te dat hij of zij gevraagd het besturingssysteem voor, niet gebruikt GetString, want dat is een CS50 ding, maar met behulp van soortgelijke functies dat het besturingssysteem voor het geheugen vragen. Als u of ze verpesten en eigenlijk nooit terug te keren dat het geheugen een symptoom van dat kan zijn dat een programma vertraagt ​​en vertraagt ​​en vertraagt tenzij je nog te bellen gratis. We komen terug naar wanneer en waarom je zou kunnen noemen gratis, maar laten we gaan gewoon voor een goede maatregel en probeer het uitvoeren van dit bijzondere programma. Dit werd genoemd structs1, in te voeren. Laat me ga je gang en lopen structs1, 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, en we zien Davids in Mather, Tommy's in Mather. Dit is slechts een kleine sanity check dat het programma werkt. Nu, helaas, is dit programma een beetje frustrerend in die Ik wist al dat werk, ik typte in 9 verschillende strings, druk op enter, werd verteld, die was in Mather, maar natuurlijk wist ik wie was al in Mather, omdat ik getypt. Het zou in ieder geval mooi zijn als dit programma is meer als een database en het herinnert eigenlijk wat ik heb getypt in dus ik nooit meer in te voeren deze student records. Misschien is het als een registrarial systeem. We kunnen dit doen met behulp van deze techniek die bekend staat als file I / O, invoer-en uitvoerbestanden, een zeer algemene manier om te zeggen wanneer u bestanden wilt lezen of bestanden weg te schrijven U kunt dit doen met een bepaalde set van functies. Laat me gaan en open dit voorbeeld structs2.c, dat is bijna identiek, maar laten we eens kijken wat het nu doet. Aan het begin van het bestand Ik verklaar een klas van leerlingen. Vervolgens heb ik bevolken de klasse met input van de gebruiker, dus die regels code zijn precies als vroeger. En als ik naar beneden scrollen hier druk ik iedereen die in Mather willekeurig als voorheen, maar dit is een interessante nieuwe functie. Deze regels code zijn nieuw, en ze introduceren hier iets, FILE, alle doppen, en het heeft * hier ook. Laat me dit bewegen over hier, een * hier ook. Deze functie hebben we nog niet eerder gezien, fopen, maar het bestand open betekent, dus de magere laat door middel van deze, en dit is iets wat we weer terug te komen in de toekomst psets, maar deze lijn hier opent in wezen een bestand met de naam database, en opent het bijzonder zodanig dat het kan wat te doen? [Onverstaanbaar-student] Juist, dus "w" gewoon betekent dat het het besturingssysteem te vertellen open dit bestand op een zodanige wijze dat ik kan schrijven. Ik wil niet om het te lezen. Ik wil niet alleen kijken naar het. Ik wil om het te veranderen en mogelijk toe te voegen materiaal aan, en het bestand zal worden genoemd database. Dit kan worden genoemd niets. Dit kan database.txt. Dit kan. Db. Dit kan een woord als foo zijn, maar ik willekeurig gekozen om de file database te noemen. Dit is een beetje sanity check dat we terugkomen om in detail na verloop van tijd, indien fp, voor bestands pointer, is niet gelijk aan NULL, dat betekent dat alles in orde is. Lang verhaal kort, functies als fopen soms niet. Misschien is het bestand niet bestaat. Misschien bent u op schijfruimte. Misschien heb je geen rechten om deze map, dus als fopen null retourneert iets ergs gebeurd. Omgekeerd, als fopen niet terugkeert null alles in orde is en ik kan beginnen met het schrijven naar dit bestand. Hier is een nieuwe truc. Dit is een lus die is itereren over elk van mijn leerlingen, en dit ziet er zo vergelijkbaar met wat we al eerder gedaan, maar deze functie is een neef van printf fprintf riep op tot bestand printf, en let op het is anders in slechts 2 manieren. , Start het met f plaats van p, maar dan is het eerste argument is blijkbaar wat? [Studenten] File. >> Het is een bestand. Dit ding heet fp, die we uiteindelijk plagen elkaar wat een bestands pointer is, maar voor nu fp vertegenwoordigt enkel het bestand dat ik heb geopend, dus fprintf hier zegt print deze gebruiker ID van het dossier, niet op het scherm. Print de gebruiker de naam van het bestand, niet op het scherm, het huis naar het bestand niet op het scherm, en vervolgens naar beneden hier, uiteraard, sluit het bestand, en dan naar beneden hier gratis het geheugen. Het enige verschil tussen deze versie 2 en versie 1 is de introductie van fopen en dit bestand met * en dit idee van fprintf, dus laten we eens kijken wat het eindresultaat is. Laat me gaan in mijn terminal-venster. Laat me lopen structs2, in te voeren. Het lijkt erop dat alles in orde is. Laten we herhaling structs2. 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, in te voeren. Het lijkt alsof het gedroeg zich hetzelfde, maar als ik nu doe ls merken wat bestand is hier onder al mijn code, database, dus laten we open dat, gedit van database, en kijk naar dat. Het is niet de meest sexy van bestandsindelingen. Het is echt een stukje van gegevens regel per regel per regel, maar degenen onder u die gebruik maken van Excel-of CSV-bestanden, door komma's gescheiden waarden, Ik zou zeker fprintf hebben gebruikt in plaats misschien iets doen als dit zodat ik kon eigenlijk maken het equivalent van een Excel-bestand door het scheiden van dingen met komma's, niet alleen nieuwe lijnen. In dit geval, als ik had gebruikt in plaats komma's in plaats van nieuwe lijnen Ik kon deze database bestand letterlijk te openen in Excel of ik in plaats daarvan maakte het er als volgt uitzien. Kortom, nu we de macht hebben om te schrijven naar bestanden kunnen we nu beginnen aanhoudende gegevens, het houden van het rond op de disc zodat wij zorgen ervoor dat informatie rond opnieuw en opnieuw. Let op een paar andere dingen die nu een beetje meer vertrouwd. Bovenaan dit bestand C we een typedef want we wilden een gegevenstype dat een woord vertegenwoordigt te maken, dus dit type heet woord, en de binnenkant van deze structuur het is een beetje liefhebber nu. Waarom is een woord dat is samengesteld van blijkbaar een array? Wat is een woord net intuïtief? Het is een array van karakters. Het is een reeks tekens rug aan rug aan rug. BRIEVEN in alle caps gebeurt te zijn we willekeurig zeggen dat de maximale lengte van een woord in het woordenboek dat we gebruiken voor Scramble. Waarom heb ik een +1? De nul karakter. Denk aan toen we de Bananagrams voorbeeld hebben we een speciale waarde die nodig is aan het einde van het woord in te houden waar woorden feitelijk heeft beëindigd, en het probleem set specificatie zegt hier zijn we associëren met een bepaald woord een booleaanse waarde, een vlag, om zo te zeggen, waar of onwaar. Heeft u ook dit woord al, omdat we ons realiseren we echt behoefte aan een manier van herinneren niet alleen wat een woord is in Scramble maar of u, de mens, heb het gevonden zodat als je vindt het woord "het" kun je niet alleen de typen, in te voeren, het, voer, de, voert u en krijgt 3 punten, 3 punten, 3 punten, 3 punten. We willen in staat zijn om dat woord blacklist door het instellen van een bool op true wanneer u al gevonden, en dus dat is waarom we ingekapseld in deze structuur. Nu, hier in Scramble is er die andere struct genaamd woordenboek. Hier afwezig is het woord typedef omdat in dit geval moesten we het idee van een woordenboek in te kapselen, en een woordenboek bevat een hele hoop woorden, zoals gesuggereerd in deze array, en hoeveel van die woorden zijn er? Nou, wat deze variabele genaamd omvang zegt. Maar we hoeven alleen maar een woordenboek. Wij hebben geen behoefte aan een gegevenstype genoemd dictionary. We hoeven alleen maar een van hen, zo blijkt in C dat als je niet zeggen typedef, alleen jij struct zeggen, dan is binnen de accolades je je variabelen, dan zet je de naam. Dit is te verklaren een variabele genaamd woordenboek dat ziet er zo uit. Daarentegen zijn deze lijnen creëren van een herbruikbare gegevens structuur genaamd woord dat u kunt meerdere kopieën van, net als wij geschapen meerdere exemplaren van studenten. Wat betekent dit uiteindelijk kunnen we doen? Laat me gaan terug in, laten we zeggen, een eenvoudiger voorbeeld van eenvoudiger tijden, en laat me open te stellen, laten we zeggen, compare1.c. Het probleem hier bij de hand is om daadwerkelijk schillen terug de laag van een string en beginnen opstijgen deze zijwieltjes omdat gebleken is dat een reeks al die tijd is zoals we beloofd in week 1 eigenlijk gewoon een bijnaam, een synoniem van de CS50 bibliotheek voor iets dat ziet er een beetje meer cryptische, char *, en we hebben gezien deze ster voor. We zagen het in de context van bestanden. Laten we nu zien waarom we zijn ondergedoken dit detail enige tijd. Hier is een bestand met de naam compare1.c, en vraagt ​​de gebruiker kennelijk 2 strings, s en t, en dan probeert die strings te vergelijken voor gelijkheid in de lijn 26, en als ze gelijk het zegt: "Je hebt getypt hetzelfde," en als ze niet gelijk zijn het zegt: "Je hebt getypt verschillende dingen." Laat me ga je gang en uitvoeren van dit programma. Laat me gaan in mijn bron directory, maak een compare1. Het is goed samengesteld. Laat me lopen compare1. Ik zal inzoomen, in te voeren. Zeg iets. HELLO. Ik zal weer iets zeggen. HELLO. Ik zeker niet typen verschillende dingen. Laat ik nog eens proberen. BYE BYE. Zeker niet anders, dus wat is er hier aan de hand? Nou, wat er echt wordt vergeleken in lijn 26? [Onverstaanbaar-student] Ja, dus het blijkt dat een string, data type, is een soort van een leugentje om bestwil. Een string is een char *, maar wat is een char *? Een char *, zoals ze zeggen, is een pointer, en een pointer is in feite een adres, een bedrag locatie in het geheugen, en als je toevallig hebt getypt in een woord als HELLO, herinneren uit het verleden discussies van strings dit is zoals het woord HELLO. Vergeet niet dat een woord als HELLO kan worden weergegeven als een array van karakters zoals deze en vervolgens met een speciaal teken op het einde wel de nul-karakter, als de \ duidt. Wat is eigenlijk een string? Merk op dat dit meerdere delen van het geheugen, en in feite, is het einde van het pas gekend wanneer je kijkt door de hele reeks op zoek naar de speciale nul karakter. Maar als dit is een stuk van het geheugen uit het geheugen van mijn computer, laten we willekeurig zeggen dat deze string gewoon geluk hebben, en het werd geplaatst aan het begin van RAM-geheugen van mijn computer. Dit byte 0, 1, 2, 3, 4, 5, 6 ... Als ik zeg iets als GetString en ik doe string s = GetString wat er echt wordt teruggestuurd? Voor deze laatste paar weken, wat is er eigenlijk wordt opgeslagen in s niet per se deze string, maar in dit geval wat is opgeslagen het getal 0, want wat GetString eigenlijk doet is het niet fysiek terug een string. Dat heeft niet eens echt conceptuele zin. Wat het doet terugkeer is een nummer. Dat aantal is het adres van HELLO in het geheugen, en string s dan, als we schillen terug deze laag, is string niet echt bestaat. Het is slechts een vereenvoudiging van de CS50 bibliotheek. Dit is echt iets genaamd char *. Char is logisch, want wat is een woord, zoals HELLO? Nou, het is een serie van tekens, een reeks tekens. Char * betekent het adres van een karakter, dus wat betekent het om een ​​string terug te keren? Een leuke, eenvoudige manier om terug te keren een string is in plaats van te proberen om erachter te komen hoe ik terug naar 5 of 6 verschillende bytes laat mij terugkeren naar het adres van die byte? De eerste. Met andere woorden, laat me je het adres van een personage in het geheugen. Dat char * staat, het adres van een teken in het geheugen. Bel die variabele s. Bewaren in s die bepaalde adres, dat willekeurig zei ik 0 is, alleen maar om het simpel te houden, maar in werkelijkheid is het over het algemeen een groter aantal. Wacht eens even. Als je alleen geeft me het adres van het eerste teken, hoe kan ik weten wat het adres is het tweede teken, de derde, de vierde en de vijfde? [Onverstaanbaar-student] Je hoeft alleen weet waar het einde van de string is door middel van deze handige truc, dus als je iets als printf, wat printf letterlijk neemt als argument, herinneren dat we deze% s tijdelijke aanduiding te gebruiken, en dan pas in de variabele dat is het opslaan van een string. Wat je echt voorbij is het adres van het eerste teken van die string. Printf gebruikt dan een for-lus of een while-lus na ontvangst van dat adres, bijvoorbeeld 0, dus laat mij nu dit, printf ("% s \ n", s); Toen ik noem printf ("% s \ n", s); wat ik echt het verstrekken van printf met is het adres van het eerste teken in s, in dit geval willekeurig H. Hoe printf weet wat er precies om weer te geven op het scherm? De persoon die geïmplementeerd printf implementeerde een while-lus of een for-lus dat zegt heeft dit karakter gelijk zijn aan de speciale null karakter? Zo niet, print het uit. Wat dacht je van deze? Zo niet af te drukken, printen, afdrukken, afdrukken. Oh, deze is speciaal. Stop met afdrukken en terug te keren naar de gebruiker. En dat is letterlijk alles wat er gebeurt onder de motorkap, en dat is veel te verteren in de eerste dag van een klasse, maar voor nu is het echt de bouwsteen van begrip alles dat er aan de hand aan de binnenkant van het geheugen van onze computer, en uiteindelijk zullen we plagen Dit apart met een beetje hulp van een van onze vrienden aan de Stanford. Professor Nick Parlante aan de Stanford heeft gedaan dit prachtige video-opname uit allerlei verschillende talen die geïntroduceerd deze kleine Claymation karakter Binky. De stem die je gaat horen in slechts een paar seconden sneak preview is dat van een Stanford professor, en je krijgt slechts 5 of 6 seconden van dit recht nu, maar dit is de noot waarop we concluderen vandaag en beginnen op woensdag. Ik geef je Pointer Plezier met Binky, de preview. [♪ ♪ Music] [Professor Parlante] Hey, Binky. Wakker worden. Het is tijd voor pointer plezier. [Binky] Wat is dat? Meer informatie over pointers? Oh, goody! We zullen je op woensdag. [CS50.TV]