DAVID MALAN: Okej, välkommen tillbaka. Detta är CS50. Detta är början på vecka sju. Så det har varit ett tag, så jag tänkte att vi skulle ta en virvlande tur av var vi slutade och där vi är nu på väg. 

Så denna sak här kan ha orsakade viss ångest i början. Men förhoppningsvis, du börjar anpassa sig till vad det betecknar här - stjärna som representerar en pekare, som är precis vad, i mer lekmannaspråk? Så det är en adress. 

Så det är adressen till något i minnet. Och vi började skära ner lagren ett par veckor sedan, saker gillar GetString och andra sådana funktioner hela denna tid har återvänt adresser saker i minnet, såsom adress för det första tecknet i viss sekvens. 

Så vi introducerade också Valgrind, vilket du börjar att använda för detta problem ställa, i synnerhet för nästa Problemet satt liksom. Och Valgrind gör vad för oss? Den kontrollerar för minnesläckor, och det kontrollerar också för missbruk av minnet. 

Det kan, med viss sannolikhet, upptäcka om din kod kommer att beröra minne att det borde helt enkelt inte. Så inte nödvändigtvis en läcka, men om du går utöver gränserna för vissa array, och du kör faktiskt valgrind och framkalla detta beteende medan Valgrind körs i ditt program är kör inne i den, får du meddelanden som detta - "ogiltigt skriver om storlek 4, "där, minns ett par veckor innebar sedan att jag hade av misstag gillar på en int för långt utanför gränserna för en array. Och så storlek 4 betyder här storleken av just int. 

Så ta trygghet i det faktum att valgrind s produktion, formatet för den, är bara avskyvärda. Det är verkligen svårt att se igenom röran för den intressanta informationen. Så vad vi har gjort här är bara utdrag några av de par mer intressanta linjer. Men inser att 80% av valgrind s produktionen kommer att vara lite av en distraktion. 

Bara leta efter mönster som dessa - ogiltig rätt, ogiltig läsa, 40 byte och några antal block är definitivt förlorade, sökord som. Och vad kommer du förhoppningsvis se en viss typ av spår av vilken funktion misstag är faktiskt i. I det här fallet, i vilken linje min kod var felet tydligen? 

26 i en fil som kallas memory.c, som var exemplet vi spelade med vid den tidpunkten. Så det är nog inte i malloc. Det var nog i min kod istället. Så vi får se detta igen och igen innan lång. 

Så scanf, kom detta upp i en par blanketter hittills. Vi såg sscanf kortfattat. Det var något som ett antal du dök in i din förberedelserna för frågesport. Och scanf är faktiskt vad CS50 Biblioteket har använt under huva för ganska länge för att få input från användaren. 

Till exempel, om jag flyttar över till CS50 apparaten här, låt mig öppna upp en exempel idag som heter scanf-0.c Och det är super enkelt. Det är bara några få rader kod. Men det visar verkligen hur getInt har arbetat hela denna tid. 

I detta program här, i linje 16 , Märker att jag deklarera en int. Så inga pekare, inget magiskt där, bara en int. Sedan i linje 17, meddelar jag användaren för ett antal, tack. Sedan i slutet av 18, jag använder scanf här. Och jag specificerade, ungefär som printf, att jag väntar citat unquote procent i. 

Så procent i, naturligtvis, betecknar en int. Men märker vad den andra argument till scanf är. Hur skulle du beskriva den andra argument efter kommatecknet? Vad är det? 

Det är den adress x. Så detta är användbart eftersom genom att tillhandahålla scanf med adressen till x, vad att ge den funktionen att göra? Inte bara åka dit, men också göra det? 

Gör en ändring till den. Eftersom du kan åka dit, det är typ av som en karta till en plats i minnet. Och så länge du ger scanf, eller någon funktion med en sådan karta, som Funktionen kan åka dit, och inte bara titta på värdet, men det kan också ändra detta värde, vilket är användbart om syftet i livet med scanf är att skanna inmatning från användaren, särskilt från tangentbordet. Och f betecknar formaterade, precis som printf, betecknar f ett formaterat sträng som du vill skriva ut. 

Så kort sagt, denna linje 18 bara säger, försöker läsa ett int från användarens tangentbord och förvara den inne i x, vid oavsett adress x råkar leva på. Och sedan slutligen, linje 19 bara säger, tack för int, i det här fallet. 

Så låt mig gå vidare och göra det. Så gör scanf 0. Låt mig gå vidare och zooma in Jag ska gå och köra med prickar slash scanf 0. Number, snälla? 50. Tack för 50. Så det är ganska enkelt. 

Nu vad gör inte? Det gör inte en hel massa av felkontroll. Till exempel, om jag inte samarbetar, och jag skriver inte på ett nummer, men istället skriver jag något som "hej" det är bara slags märkligt. Och så en av de saker de CS50 Biblioteket har gjort för oss för några tiden är att reprompting och reprompting. 

Den retry frasen minns var i cs50.c, och det är anledningen till att getInt i den CS50 biblioteket är faktiskt en hel gäng rader lång, eftersom vi är kontroll för dumma saker som denna. Har användaren inte ge oss, i själva verket, en int? Har han eller hon ge oss något som en alfabetisk bokstav? Om så, vill vi att upptäcka det och skrika på dem. 

Men det blir mer intressant i nästa exempel. Om jag går till scanf-1 c, är vad en sak som ändras radikalt i nästa exempel? Jag använder char *, naturligtvis, istället för int. 

Så det här är intressant, eftersom char *, minns, är egentligen bara Samma sak som sträng. Så det känns som det kanske detta är en super enkel implementering av GetString. Men jag har skalat tillbaka lagret av CS50 biblioteket, så jag är kallar denna char * nu. Så låt oss se var, om någonstans, vi går fel. 

Linje 17 - Jag säger det igen, ge mig något, i detta fall en sträng. Och sedan i nästa rad, kallar jag scanf, igen, ge det ett format kod, men denna gång procent s. Och så den här gången, jag är ge den buffert. 

Nu märker, jag inte använder et-tecknet. Men varför är det förmodligen OK här? För vad är bufferten redan? Det är redan en pekare. Det är redan en adress. 

Och låt oss detta ord "förvirra," låt mig bara kalla det s, till exempel för enkelhet. Men jag har kallat den buffert eftersom allmänhet, i programmering, om du har en bit av minnet, som en sträng egentligen bara är, kan man kalla det en buffert. Det är en plats att lagra information. 

Liknar saker som YouTube, då de är buffring, så att säga, att bara betyder det att ladda ner bitar från Internet och lagra dem i en lokal array, en lokal del av minnet så att du kan titta på det senare utan det hoppar eller hänger på du under uppspelning. 

Så det finns ett problem här men, eftersom jag säger scanf, förvänta sig en strängen från användaren. Här är adressen till en bit av minnet. Sätt den strängen där. Varför är det bundet ge oss problem, men? 

Vad är det? Får jag komma den del av minnet? Du vet, jag vet inte. Eftersom har buffert initierats till någonting? Inte riktigt. Och så det är vad vi har ringt ett skräp värde, vilket är inte ett formellt ord. Det betyder bara att vi har ingen aning om vad bitar är inne på de fyra byte som Jag har tilldelats som buffert. 

Jag har inte kallat malloc. Jag har definitivt inte kallas GetString. Så vem vet vad som faktiskt insidan av buffert? Och ändå säger scanf blint, dit och ange vad användaren skrivit. 

Så vad är sannolikt att orsaka i vår kod, om vi kör det? Förmodligen en segfault. Kanske inte, men förmodligen en segfault. Och jag säger kanske inte eftersom det ibland du gör, ibland du får inte en segfault. Ibland får man bara tur, men det ändå kommer att vara en bugg i vårt program. 

Så låt mig gå vidare och sammanställa detta. Jag kommer att göra det enligt den gamla skolan. Så klang dash 0, scanf-1, scanf-1.c, Enter. Oops, för gammal skola. Låt oss se. Vart tog jag vägen? Åh, char * buffert. Åh, tack - Spara, OK - mycket gamla skolan. Okej, det har varit ett tag. 

Så jag har bara sparat filen efter vilket gör att tillfälliga ändra en stund sedan. Och nu har jag sammanställt det manuellt med Clang. Och nu ska jag gå vidare och kör scanf-1, Enter. String vänligen. Jag ska skriva in "hej." 

Och nu, här där, uppriktigt sagt, printf kan är lite irriterande. Det är faktiskt inte kommer att segfault i detta fall. Printf är lite speciell eftersom det är så super vanligt att huvudsak printf gör oss en tjänst och inse, det är inte en giltig pekare. Låt mig ta det på mig att bara skriva ut anges i parentes null, även men det är inte nödvändigtvis vad vi själva förväntat. 

Så vi kan inte riktigt lätt framkalla en segfault med detta, men tydligt detta är inte det beteende som jag ville. Så vad är den enkla lösningen? Tja, i scanf-2, låt mig föreslå att stället för att faktiskt bara allokera en char *, låt mig vara lite smartare om detta, och låt mig allokera buffert som en sekvens av 16 tecken. 

Så jag kan göra detta på ett par olika sätt. Jag skulle absolut använda malloc. Men jag kan gå tillbaka till vecka två när Jag behövde bara en massa tecken. Det är bara en array. Så låt mig i stället omdefiniera buffert att vara en matris med 16 tecken. 

Och nu, när jag passerar buffert - och detta är något vi inte prata om i vecka två - men du kan behandla en array som även om det är en adress. Tekniskt, som vi har sett, de är lite annorlunda. Men scanf inget emot om du klarar det namnet på en matris, eftersom det Klang kommer att göra för oss är i huvudsak behandla namnet på den matris som adressen för den bit av 16 byte. 

Så det här är bättre. Detta innebär nu att jag kan förhoppningsvis gör följande. Låt mig zooma ut för ett ögonblick och gör att scanf-2, sammanställs OK. Nu låt mig göra fick slash scanf-2. String vänligen. "Hej." Och det verkade fungera den här gången. 

Men kan någon föreslå ett scenario där det kanske inte fortfarande fungerar? Yeah? Något längre än 16 tecken. Och faktiskt, kan vi vara lite mer exakt. Något längre än 15 tecken, eftersom vi verkligen behöver för att hålla i minnet att vi behöver att backslash noll implicit i slutet av strängen, vilket är en åt sidan scanf kommer typiskt ta hand om för oss. 

Så låt mig göra något liknande - Ibland kan vi bara lämna det så. OK, så vi har nu inducerad vår segmentering fel. Varför? Eftersom jag skrev till mer än 15 tecken, och så vi har faktiskt rörd minne som jag faktiskt bör inte ha. 

Så vad är egentligen lösningen här? Tja, vad händer om vi behöver en längre sträng? Tja, gör vi det kanske 32 bytes. Tja, tänk om det inte är länge nog? Vad sägs om 64 byte? Tänk om det inte är länge nog? Vad sägs om 128 eller 200 byte? Vad är egentligen lösningen här i allmänna fallet, om vi inte vet i förhand vad användaren kommer att skriva? 

Det är bara typ av en stor smärta i röven, att vara ärlig, vilket är anledningen till den CS50 biblioteket har några dussin rader kod som kollektivt genomföra GetString sträng på ett sätt som vi inte måste veta i förväg vad Användaren kommer att skriva. I synnerhet om man ser tillbaka på cs50.c från två veckor sedan, kommer du att se att GetString gör faktiskt inte använda scanf på detta sätt. Snarare, läser den ett tecken åt gången. 

Eftersom den ena fina läser ett tecken är att vi kan garantera oss att alltid ha minst en röding. Jag kan bara förklara en röding, och sedan ta dessa verkligt baby steg till strax Läs ett tecken in på en tiden från tangentbordet. Och sedan, vad du ser GetString gör är varje gång det tar slut, säga, 16 byte minne, använder den malloc, eller en kusin därav, att allokera mer minne, kopierar den gamla minnet i den nya, och sedan krypa tillsammans, att få ett tecken i tiden, och när det tar slut i det bit av minnet, kastar bort det, grabs en större bit av minnet, kopierar gamla till nya, och upprepar. Och det är verkligen en smärta att faktiskt genomföra något så enkelt som få input från en användare. 

Så du kan använda scanf. Du kan använda andra liknande funktioner. Och en hel del läroböcker och nätet exempel gör, men de är alla sårbara för problem som detta. Och slutligen, få en segfault är typ av irriterande. Det är inte bra för användaren. 

Men i värsta fall, vad gör det lägger grunden din kod vid risk? Något slags angrepp, potentiellt. Vi pratade om en sådan attack - överfyllda bunten. Men i allmänhet, om du får spilla en buffert, som vi gjorde en par veckor sedan, med bara skriva mer än "hej" på stacken, du kan faktiskt ta över, potentiellt, en dator, eller åtminstone komma på data som tillhör inte dig. 

Så kort sagt, det är därför vi har dessa stödhjul. Men nu börjar vi att ta bort dem, eftersom våra program inte längre behöver, nödvändigtvis, inmatning från användaren. Men i fallet med problem som sex, din inmatning kommer från en enorm ordlistefilen med 150 några udda tusen ord. 

Så du inte behöver oroa dig användarens godtyckliga indata. Vi kommer att ge dig några antaganden om den filen. Eventuella frågor om pekare eller scanf eller användarens input i allmänhet? 

Okej, så en snabb titt och sedan på en släpande ämne från två veckor sedan. Och det var denna föreställning om en struct. Inte att - denna föreställning om en struct, vilket var vad? Vad gjorde struct göra för oss? 

Define - ledsen? Definiera en variabel typ. Så sortera om. Vi är faktiskt kombinera två ämnen. Så med typedef, minns att vi kan deklarera en typ av vår egen, som en synonym, liksom sträng för char *. Men med hjälp av typedef och struct, kan vi skapa verkligt egna datastrukturer. 

Till exempel, om jag går tillbaka in i gedit här för bara ett ögonblick, och jag går vidare och göra något liknande, låt mig sparar detta som, låt oss säga, structs.c tillfälligt, jag ska bara att gå vidare och inkludera standardio.h, int main tomrum. Och sedan i här, antar att jag vill ha att skriva ett program som lagrar flera studenter från flera hus, till exempel. Så det är som en registrarial databas av något slag. 

Så om jag behöver namnet en student, jag kanske göra något liknande char * namn, och jag ska göra något liknande - faktiskt, låt oss använda CS50 biblioteket för bara en stund för att göra detta till en lite enklare, så att vi kan låna de dussintals rader kod. Och låt oss bara hålla det enkelt. Vi ska hålla det sträng, och nu getString. 

Så jag hävdar nu att jag har sparat namnet av någon elev, och hus vissa studerande, helt enkelt med hjälp av variabler som vi gjorde, och i vecka ett. Men antar att jag nu vill stödja flera studenter. Okej, så min instinkt är att göra string namn2, blir GetString, sträng house2 blir GetString. Och då vår tredje elev, låt oss göra NAME3 GetString. 

Okej, så det är förhoppningsvis slående dig som ett slags dum, eftersom denna process är egentligen aldrig kommer att sluta, och det kommer bara att gör min kod ser värre och värre och värre. Men vi löste det också i vecka två. Vad var vår relativt ren lösning när vi hade flera variabler av samma datatyp som alla är relaterade, men Vi ville inte att denna fruktansvärda röran av liknande namn variabler? Vad gjorde vi i stället? 

Så jag tror att jag hörde ett par ställen. Vi hade en matris. Om du vill ha flera instanser av något, varför inte vi rengöra alla upp och bara säga, ge mig array kallas namn? 

Och för nu, låt oss hårt kod 3. Och sedan ge mig en annan array kallas hus, och låt mig för nu hårt kod 3. Och jag har massivt städas upp förstöra som jag nyss skapat. Nu har jag fortfarande svårt kodad 3, men även 3 kunde dynamiskt komma från användare eller argv, eller liknande. Så detta är redan renare. 

Men vad är irriterande med detta är att Nu är även ett namn på något sätt fundamentalt kopplad till en students hus - det är en elev som jag verkligen vill representera - Jag har nu två arrayer som är parallella i den meningen att de är de samma storlek och namn konsol 0 förmodligen kartor till hus konsol 0, och namn på konsolen 1 kartor till hus bracket 1. Med andra ord, den studerande bor i det huset, och att andra studerande bor i det andra huset. Men visst kan detta vara gjort ännu renare. 

Tja, det kan i själva verket. Och låt mig gå vidare och öppna upp structs.h, och du kommer se denna idé här. Lägg märke till att jag har använt typedef, som ni hänvisade till för en stund sedan att förklara vår egen datatyp. Men jag använder också denna andra sökord kallas struct som ger mig en ny datastruktur. 

Och denna datastruktur jag hävdar går att ha två saker inuti det - en sträng som heter namn, och en sträng som kallas hus. Och namnet jag ska ge till denna datastruktur kommer att kallas student. Jag skulle kunna kalla det vad jag vill, men detta göra semantiskt meningsfullt för mig i mitt sinne. 

Så nu, om jag öppnar upp en bättre version av det program jag började skriva det, låt mig rulla till toppen. Och det finns några fler rader kod här, men låt mig fokusera för det ögonblick på en. Jag har förklarat en konstant kallade studenter och hårdkodade 3 för nu. Men nu, märker hur ren min kod börjar komma. 

I linje 22, förklarar jag samling av studenter. Och märker att studenten är tydligen nu en datatyp. Eftersom på toppen av denna fil, märker Jag har bland annat varit sidhuvudfilen att jag drog upp nyss. Och att header-fil helt enkelt hade denna definition av en elev. 

Så nu har jag skapat min egna uppgifter typ att författarna C år sedan inte tänka på i förväg. Men inga problem. Jag kan göra det själv. Så detta är en array kallas studenter, vars samtliga medlemmar är en student struktur. Och jag vill ha tre av dem i arrayen. 

Och nu, vad gör resten av detta program göra? Jag behövde något lite godtyckligt. Så från nätet 24 och framåt, Jag iterera från 0 till 3. Jag frågar då användaren för studentens namn. Och då jag använder getString som förut. Då frågar jag för elevens huset, och jag använder getString som tidigare. 

Men varsel - något nytt bit syntax - Jag kan fortfarande index till det i: te studerande, men hur får jag på de specifika uppgifter fält inne i struct? Tja, vad är uppenbarligen ny bit av syntax? Det är bara pricken operatören. 

Vi har inte riktigt sett det här förut. Du har sett det i pset fem om du har dök redan med bitmap-filer. Men pricken betyder precis innanför detta struct eller flera fält, ger prick namn, eller ge mig dot hus. Det innebär att gå in i struct och få dessa särskilda områden. 

Vad gör resten av det här programmet? Det är inte så sexigt. Observera att jag iterera från 0 till 3 igen, och jag skapar helt enkelt en engelsk fras som så och så är i en sådan och ett sådant hus, passerar i prick namn från den i: te student och deras huset också. 

Och sedan sist, nu ska vi börja för att få anal om detta, nu när vi är bekant med vad malloc och andra funktioner har varit gör hela tiden. Varför måste jag befria både namn och hus, även om jag inte ringa malloc? 

GetString gjorde. Och det var den smutsiga lilla hemlighet för flera veckor, men GetString har läckt minne hela placera hela terminen hittills. Och Valgrand kommer slutligen avslöja detta för oss. 

Men det är inte en stor sak, eftersom jag vet att jag kan helt enkelt frigöra namnet och huset, men tekniskt sett, att vara super, super säker, ska jag vara gör vissa felkontroll här. Vilka är dina instinkter säger dig? Vad bör jag kontrollera om innan jag gratis Vad är en string, aka som en char *? 

Jag borde verkligen kontrollera om eleverna fäste i prick namn inte lika null. Sedan ska det vara OK att gå vidare och gratis som pekare, och samma eller det andra en också. Om eleverna fäste i dot hus är inte lika med noll, detta nu kommer att skydda mot hörnet fall där GetString returnerar något som null. Och vi såg en stund sedan, printf kommer skydda oss här uppe genom att bara säga null, vilket går att se konstigt. Men åtminstone det inte kommer segfault, som vi har sett. 

Nåväl, låt mig göra en sak här. structs-0 är lite av en dum program eftersom jag in alla dessa data, och sedan det förlorat när programmet avslutas. Men låt mig gå vidare och göra det. Låt mig göra terminalen fönstret lite större. Låt mig göra structs-1, vilket är en ny version av detta. 

Jag kommer in i en liten bit. Och låt mig nu kör prick snedstreck structs-1. Studentens namn - David Mather, låt oss göra Rob Kirkland, låt oss göra Lauren Leverett. Vad är intressant nu är varsel - och jag vet att bara detta eftersom Jag skrev programmet - det finns en fil nu på min nuvarande katalog som heter students.csv. Några av er kanske har sett dessa i den verkliga världen. 

Vad är en CSV-fil? Kommaavgränsade värden. Det är ungefär som en fattig mans version av en Excel-fil. Det är en tabell med rader och kolumner som du kan öppna i ett program som Excel, eller siffror på en Mac. 

Och om jag öppnar den här filen här på gedit, varsel - och siffrorna är inte där. Det är bara gedit berätta mig radnummer. Tillkännagivande om den första raden i detta filen är David och Mather. Nästa rad är Rob kommatecken Kirkland. Och den tredje raden är Lauren kommatecken Leverett. 

Så vad har jag skapat? Jag har nu skrivit ett C-program som effektivt kan generera kalkylblad som kan öppnas i en program som Excel. Inte så övertygande en datamängd, men om du har mycket större bitar av data som du verkligen vill manipulera och göra grafer av och liknande, är detta kanske en sätt att skapa dessa uppgifter. Dessutom CSVs är faktiskt super gemensamma bara för lagring av enkel data - Yahoo Finance, till exempel, om du får aktiekurser via deras så kallade API, gratis tjänst som låter dig få aktuell up-to-the-date lager offerter för företagen, de ge tillbaka data i super enkel CSV-format. 

Så hur har vi det? Väl att märka, de flesta av programmets nästan samma. Men märker här nere, snarare än utskrift eleverna ute på linje 35 framåt, hävdar jag att jag sparar den studenter till disk, så sparar en fil. 

Så märker jag att förklara en FIL * - nu, är denna typ av en anomali i C. Av någon anledning är FILE versaler, vilket är inte som de flesta andra datatyper i C. Men detta är en inbyggd datatyp, FILE *. Och jag förklara en pekare till en fil, är hur du kan tänka på det. 

fopen betyder öppen fil. Vilken fil vill du öppna? Jag vill öppna en fil som jag kommer godtyckligt ringa students.csv. Jag skulle kalla det vad jag vill. 

Och sedan ta en gissning. Vad innebär det andra argumentet till fopen betyda förmodligen? Höger, w för write, kunde vara r för läsning. Det finns en för append om du vill lägga till rader och inte skriva över det hela. 

Men jag vill bara skapa den här filen en gång, så jag ska använda citat unquote w. Och jag vet att det bara från att ha läst dokumentationen, eller man-sidan. Om filen inte är null - med andra ord, Om något gick fel där - låt mig iterera över studenter från 0 till 3. 

Och nu märker att det är något någonsin så något annorlunda kring linjen 41 här. Det är inte printf. Det är fprintf för filen printf. Så det kommer att skriva till fil. Vilken fil? Den vars pekare du anger som det första argumentet. 

Då kan vi ange ett format sträng. Då kan vi ange vilken sträng som vi vill plug in för den första procent s, och sedan en annan variabel eller den andra procent s. Då kan vi avsluta ärendet med fclose. Än jag frigöra minne som förut, men Jag ska gå tillbaka in och lägga vissa kontroller för null. 

Och det är det. fopen, fprintf ger fclose mig förmåga att skapa textfiler. Nu ser du i problem set fem, som innebär bilder, ska du använda binära filer i stället. Men i grunden är idén densamma, även om de funktioner du se är lite annorlunda. 

Så virvlande tur, men du kommer att få alltför bekant med fil I/O-- ingång och utgång - med pset fem. Och några frågor om första grunderna här? Yeah? 

Vad händer om du försöker att frigöra ett null-värde? Jag tror, ​​om inte gratis har blivit en lite mer användarvänliga, kan du potentiellt segfault. Förbi det null är dåligt eftersom jag inte tro gratis stör att kontrollera dig, eftersom det skulle kunna vara ett slöseri tid för den att göra sig till alla i världen. Bra fråga, men. 

Okej, så denna typ av får oss till ett intressant ämne. Temat för problemet set fem är kriminalteknik. Åtminstone det är en del av problemet set. Forensics hänvisar i allmänhet till återvinning av information som kan eller kanske inte har tagits bort avsiktligt. Och så jag trodde jag skulle ge dig en snabb smakprov på vad som verkligen händer alla denna gång under huven på din dator. 

Till exempel, om du har insidan av din bärbara eller stationära dator en hårddisk, det är antingen en mekanisk enhet som faktiskt snurrar - det finns cirkulära saker som kallas Platters som helt ser ut som vad jag bara hade upp på skärmen här, men detta är allt gamla skolan. Detta är en tre-och en halv tum hårddisk. Och tre och en halv inches hänvisar i med den saken när du installerar det i en dator. 

Många av er i era laptops nu har solid-state-enheter eller SSD, som inte har några rörliga delar. De är mer som RAM och mindre som Dessa mekaniska anordningar. Men idéerna är fortfarande samma, säkerligen de rör att problemet satt fem. 

Och om du tycker om nu en hårddisk föreställer att vara en cirkel, som Jag ska göra som det här. När du skapar en fil på din dator, oavsett om det är en SSD, eller i detta fall, en äldre skola hårddisk, den filen innefattar flera bitar. Låt oss säga att det är det här 0 och 1, en hel massa av 0 och 1. Så detta är hela min hårddisk. Detta är uppenbarligen en ganska stor fil. Och det använder upp 0s och 1s vid den del av den fysiska diskens. 

Nå, vad är det fysiska delen? Jo, visar det sig att på en hårddisk, åtminstone av denna typ, det finns dessa små små magnetiska partiklar. Och de har i huvudsak norr och sydpoler till dem, så att om du vända ett av dessa magnetiska partiklar detta sätt kan man säga att det är som representerar en 1. Och om det är upp och ner söderut till norr, kan man säga att det är representerar en 0. 

Så i den verkliga fysiska världen, är det hur man kan representera något i binära tillståndet av 0 och en 1. Så det är allt en fil. Det finns en hel drös med magnetisk partiklar som är deras på detta sätt eller detta sätt, vilket skapar mönster av 0 och 1. 

Men det visar sig när du sparar en fil, viss information sparas separat. Så det här är ett litet bord, en katalog, så att säga. Och jag ska kalla denna kolumn namn, och Jag ringer denna kolumn plats. 

Och jag ska säga, antar detta är mitt CV. Min resume.doc lagras vid plats, låt oss säga 123. Jag går alltid för det numret. Men det räcker att säga att precis som i RAM, kan du ta en hårddisk det är en gigabyte eller 200 gigabyte eller en terabyte, och du kan antal alla byte. Du kan numrera alla bitar av 8 bitar. 

Så vi säger att detta är plats 123. Så här katalogen insidan av mitt operativsystem Systemet kommer ihåg att min CV är på plats 123. Men det blir intressant när du raderar en fil. 

Så till exempel - och tack och lov, har de flesta av världens fångas på detta - vad händer när du drar en fil till din Mac OS Papperskorgen eller din Windows Papperskorgen? Vad är syftet med att göra det? Det är självklart att bli av med filen, men vad gör handlingen att dra och släppa in papperskorgen eller din Recycle Bin göra på en dator? 

Absolut ingenting, egentligen. Det är precis som en mapp. Det är en särskild mapp, för att vara säker. Men tar inte bort det faktiskt filen? 

Tja, nej, eftersom vissa av er förmodligen ha varit som, åh fan, det gjorde du inte menar att göra det. Så du dubbelklicka på Papperskorgen eller Papperskorgen. Du har petade runt och du har återhämtat filen bara genom att dra den av där. Så klart, det är inte nödvändigtvis radera det. 

OK, du är smartare än så. Du vet att bara dra den till Papperskorgen eller Papperskorgen betyder inte du tömma papperskorgen. Så du gå upp till menyn, och du säger Töm papperskorgen eller Töm papperskorgen. Vad händer då? 

Ja, så det tas bort mer så. Men allt som händer är detta. Datorn glömmer där resume.doc var. 

Men vad har inte förändrats tydligen på bilden? Bitarna är 0 och 1 som jag hävdar är på platsen för några fysiska aspekten av hårdvaran. De är fortfarande där. Det är bara att datorn har glömt vad de är. 

Så det är i huvudsak befriade filens bitar så att de kan återanvändas. Men inte förrän du skapar fler filer, och fler filer och mer filer probabilistiskt, de 0s och 1s, dessa magnetiska partiklar, får återanvändas, upp eller med rätt sida upp, för andra filer, 0 och 1. 

Så du har detta tidsfönster. Och det är inte för förutsägbar längd, egentligen. Det beror på storleken på din hårddisk kör och hur många filer du har och hur snabbt du göra nya. Men det är det här fönstret för tid under som att filen är fortfarande helt ersättningsgilla. 

Så om du använder någonsin program som McAfee eller Norton att försöka återvinna uppgifter, är allt de gör försöker återvinna denna så kallade katalogen räkna ut var filen fanns. Och ibland Norton och kommer att säga, filen är 93% återvinningsbart. Tja, vad betyder det? Det betyder bara att någon annan fil tillfällighet slutade med, säg, dessa bitar ur din ursprungliga filen. 

Så vad är egentligen inblandade att återskapa data? Tja, om du inte har något som Norton förinstallerat på datorn, det bästa du kan ibland göra är att titta på hela hårddisken söker mönster av bitar. Och ett av de teman som problem set fem är att du kommer att söka motsvarande en hårddisk, en rättsmedicinsk bilden av ett compact flash-kort från en digitalkamera, söka efter 0s och 1s som normalt, med hög sannolikhet, företräda start av en JPEG-bild. 

Och ni kan återställa dessa bilder genom antar, om jag ser detta mönster av bitar på rättsmedicinska bilden, med hög sannolikhet, som markerar början av en JPEG. Och om jag ser samma mönster igen, som markerar förmodligen starten av annat JPEG, och en annan JPEG, och annat JPEG. Och detta är typiskt hur Data Recovery fungerar. Vad är trevligt om JPEG är trots filformatet i sig är något komplex, i början av varje sådan filen är faktiskt ganska identifierbar och enkel, som ni kommer att se, om du har inte redan. 

Så låt oss ta en närmare titt under huven till exakt vad som har varit pågår, och vad dessa 0s och 1s är, för att ge dig lite mer av en sammanhanget för denna utmaning. 

[VIDEO SPELA] 

-Om din dator lagrar mest av dess permanenta uppgifter. För att göra detta, reser data från RAM tillsammans med programvara signaler som talar hårddisken hur man lagrar dessa data. De hårda drivkretsar översätta dessa signaler till spänning fluktuationer. Dessa, i sin tur, kontrollera hårddiskens rörliga delar, några av de få rörliga delar kvar i modern dator. 

Några av de signaler styr en motor som snurrar metall-belagda skivorna. Dina uppgifter lagras i själva verket på dessa fat. Andra signaler flytta läs / skriv huvuden att läsa eller skriva data på skivorna. Denna maskin så precisa att en människa håret kunde inte ens passera mellan huvuden och snurrande skivorna. Ändå fungerar det på fantastiska hastigheter. 

[END VIDEOAVSPELNING] 

DAVID MALAN: Zooma in lite djupare nu på vad som är faktiskt på dessa fat. 

[VIDEO SPELA] 

-Låt oss titta på vad vi just såg i slow motion. När en kort puls av el är skickas till läs / skrivhuvudet, om flips på en liten elektromagnetisk för en bråkdel av en sekund. Magneten skapar ett fält, vilket ändrar polaritet av en liten, liten del av metallpartiklar som päls varje tallrik yta. 

Ett mönster serie av dessa små, laddade-up områden på disken representerar en enda bit av data i det binära talet system som används av datorer. Nu, om ström sänds ett sätt genom läs / skriv huvudet, området är polariserat i en riktning. Om ström sänds i motsatt riktning, den polarisering är omvänd. 

Hur du får data från hårddisken? Bara vända processen. Så det är partiklarna på disken att få strömmen i läs / skrivhuvudet rör sig. Sätt ihop miljontals dessa magnetiserade segment, och du har en fil. 

Nu, bitar av en enda fil kan vara utspridda över ett enhetens skivorna, ungefär som röran av papper på skrivbordet. Så en särskild extra fil håller koll av där allt är. Önskar du inte att du hade nåt sånt? 

[END VIDEOAVSPELNING] 

DAVID MALAN: OK, förmodligen inte. Så hur många av er killar växte upp med dessa? OK, så det är färre och färre händer varje år. Men jag är glad att du är minst bekant med dem, eftersom detta och vår egen bok demo, tyvärr, dör en mycket långsam död här i förtrolighet. 

Men detta är vad jag, åtminstone, tillbaka i gymnasiet, använde användning för säkerhetskopior. Och det var fantastiskt, eftersom du kunde lagra 1.4 megabyte på denna speciella skivan. Och detta var den höga tätheten versionen, såsom indikeras av HD, som har menande före dagens HD-videor. 

Standard densiteten var 800 kilobyte. Och innan det fanns 400-kilobyte diskar. Och innan dess fanns det 5 och 1/4 tums disketter, som var riktigt diskett, och lite bredare och högre än dessa saker här. Men du kan faktiskt se den så kallade floppy aspekt av dessa diskar. 

Och funktionellt, är de faktiskt ganska lik hårddiskar på minst denna typ. Återigen, SSDs i nyare datorer fungerar lite annorlunda. Men om du flyttar den lilla metall flik, Du kan faktiskt se en liten kaka, eller tallrik. 

Det är inte metall som den här. Detta är faktiskt lite billigare plastmaterial. Och du kan typ av vicka. Och du har trully bara torkas av vissa antalet bitar eller magnetiska partiklar från denna skiva. 

Så tack och lov, det finns inget på det. Om den saken är i vägen - och täcker dina ögon och de av din granne - du kan bara typ av drag här Hela skidan iväg så där. Men det finns en liten fjäder, så att medveten om det med dina ögon. Så nu har du verkligen en diskett. 

Och vad är anmärkningsvärt om detta är att i så mycket som detta är en småskalig representation av en större hårddisk, dessa saker är super, super enkelt. Om du nyper botten med det, nu när att metall sak är avstängd, och skal dem öppna, är allt som finns två stycken filt och den så kallade diskett med en bit metall på insidan. 

Och där går hälften av min diskens innehåll. Det går en annan halva av dem. Men det är allt som snurrar inuti av datorn i förr. 

Och återigen, att sätta detta i perspektiv, hur stort är det mesta av din hårddiskar dessa dagar? 500 gigabyte, en terabyte, kanske i en stationär dator, 2 terabyte, 3 terabyte, 4 terabyte, eller hur? Detta är en megabyte, ge eller ta, som inte ens kan passa en typisk MP3 längre dessa dagar, eller några liknande musikfil. 

Så en liten souvenir för dig idag, och också att hjälpa kontextualisera vad Vi kommer att ta för givet nu i problem som fem. Så de är din att behålla. Så låt mig övergång till där blir spendera nästa pset liksom. Så vi har nu satt den här sidan för - åh, ett par meddelanden snabbt. 

Denna fredag, om du vill gå CS50 för lunch, gå till det vanliga stället, cs50.net/rsvp. Och slutprojekt - så per kursplanen, har vi lagt upp slutprojekt specifikationen redan. Inse att det inte betyder det beror särskilt snart. Det har publicerats, egentligen, bara för att få ni tänker på det. Och faktiskt, en super betydande procentandel av er kommer att ta itu med slutarbeten på material som vi har inte ens fått i klassen, men kommer så tidigt som nästa vecka. 

Observera dock att den spec kräver några olika komponenter i slutprojekt. Den första, i ett par veckor, är en pre-förslag, en ganska casual e-post till din TF för att berätta för honom eller vad du är tänka på för ditt projekt, med inget åtagande. Förslaget kommer att vara din engagemang, ordstäv, här, är detta vad Jag skulle vilja göra för mitt projekt. Vad tycker du? För stor? För liten? Är det hanterbart? Och du ser spec för mer information. 

Par veckor efter det är statusen Rapporten, som är en liknande tillfällig e-post till din TF att säga precis hur långt efter du är i din sista projektets genomförande, följt av den CS50 Hackathon som alla är inbjudna, vilket kommer att vara en händelse från 20:00 på en kväll till 07:00 AM nästa morgon. Pizza, som jag kanske har nämnt i veckan noll, vara til serveras vid 9:00, Kinesisk mat på 1:00 AM. Och om du fortfarande vaken klockan 5:00, Vi tar dig till IHOP för frukost. 

Så Hackathon är en av de mer minnesvärda upplevelser i klassen. Då genomförandet beror, och då den kulminerande CS50 Fair. Mer information om alla dessa under de kommande veckorna. 

Men låt oss gå tillbaka till något old school - igen, en array. Så en array var trevligt, eftersom det löser problem som vi såg bara en stund sedan med studerande strukturer få en lite ur kontroll om vi vill ha eleven en, student två, Studenten tre, student dot dot dot, några godtyckligt antal studenter. 

Så arrayer, för några veckor sedan, svepte in och löste alla våra problem med inte att veta i förväg hur många saker av något slag som vi kanske vill. Och vi har sett att structs kan hjälpa oss ytterligare organisera vår kod och hålla begreppsmässigt likartade variabler, t.ex. en namn och ett hus, tillsammans, så att vi kan behandla dem som en enhet, insida av vilka det finns mindre bitar. 

Men arrayer har vissa nackdelar. Vilka är några av de nackdelar vi har stött med arrayer hittills? Vad är det? Fast storlek - så även om du kanske kunna allokera minne för ett array, när du vet hur många studenter du har, hur många tecken du har från användaren, när du har tilldelats arrayen, har du typ av målade själv i ett hörn. 

Eftersom du inte kan infoga nya element i mitten av en array. Du kan inte sätta in fler element vid slutet av en array. Verkligen, du måste ta till att skapa en helt ny array, som vi har diskuterat, kopiera det gamla till det nya. Och återigen, är att huvudvärken som GetString erbjudanden med för dig. 

Men återigen, kan du inte ens sätta något i mitten av uppsättningen Om räntan inte är helt fylld. Till exempel, om denna array här av storlek sex har bara fem saker i den, Tja, kan du bara please något på änden. Men vad händer om du vill infoga något in i mitten av den array, även om det kan ha fem av sex saker i den? 

Nå, vad vi gör när vi hade alla av våra frivilliga på scenen i veckor tidigare? Om vi ​​ville sätta någon här, antingen dessa människor hur man flyttar detta sätt, eller dessa människor hur man flyttar detta sätt, och det blev dyrt. Vid förflyttningen av människor inne i en array hamnade lägga upp och kostnadsberäkning oss tid, alltså mycket av vår n kvadrat rinnande tider som insättning sortera, för Exempelvis, i värsta fall. Så arrayer är bra, men du måste vet i förväg hur stor du vill ha dem. 

Så OK, här är en lösning. Om jag inte vet i förväg hur många elever jag kan ha, och jag vet en gång Jag bestämmer, men jag fastnade med att många studenter, varför gör inte jag bara alltid fördela dubbelt så mycket utrymme så jag tror jag behöver? Är det inte en rimlig lösning? 

Realistiskt, jag tror inte att vi är kommer att behöva mer än 50 platser i en matris för en medelstor klass, så låt oss bara runda upp. Jag ska göra 100 slots i min samling, precis så att vi kan definitivt få Antalet elever jag förväntar vara i någon medelstor klass. Så varför inte bara runda upp och fördela mer minne, typiskt, för en samling än du tror att du ens behöver? Vad är det här enkla stift till den idén? 

Du är bara slöseri med minne. Bokstavligen varje program du skriver sedan är kanske använder dubbelt så mycket minne som du behöver faktiskt. Och det bara inte känns som en särskilt elegant lösning. Dessutom minskar det bara sannolikheten för ett problem. Om du råkar ha en populär kurs en termin och du har 101 studenter, är programmet fortfarande grunden inför samma fråga. 

Så tack och lov, det finns en lösning på denna annons alla våra problem i form av datastrukturer som mer komplex än de som vi har sett hittills. Detta, hävdar jag, är en länkad lista. Detta är en lista med tal - 9, 17, 22, 26, och 34 - som har länkats samman genom av vad jag har ritat som pilar. 

Med andra ord, om jag ville representera en matris, kunde jag göra ungefär så här. Och jag ska sätta detta på overhead på bara ett ögonblick. Jag kunde göra - hej, okej. Stand by. Ny dator här, klart - okej. 

Så om jag har dessa siffror i rad - 9, 17, 22, 26, 24 - inte nödvändigtvis i skala. Okej, så här är min samling - oh my god. Okej, så här är min samling. Herregud. 

[SKRATT] 

DAVID MALAN: Pretend. Det är för mycket ansträngning för att gå tillbaka och fixa det, så det - 26. Så vi har denna samling av 9, 17, 22, 26, och 34. För de av er kan se pinsamt misstag jag gjorde precis, det är det. 

Så jag hävdar att detta är en mycket effektiv lösning. Jag har tilldelats lika många ints som Jag behöver - ett, två, tre, fyra, fem eller sex - och jag har sedan lagrat numren insidan av denna matris. Men anta, då vill jag att infoga ett värde som nummer 8? Tja, inte var det går? Anta att jag vill infoga ett antal som 20. Tja, inte var det går? Någonstans där i mitten, eller antalet 35 måste gå någonstans i slutet. Men jag är allt ut i rymden. 

Och så detta är en grundläggande utmaning av matriser det betyder är lösningen. Jag hävdade en stund sedan, getString löser detta problem. Om du vill infoga en sjätte nummer in i denna matris, vilka är åtminstone en lösning du kan falla tillbaka på för säker, precis som vi gör med GetString? Vad är det? 

Tja, göra det större är lättare sagt än gjort. Vi kan inte nödvändigtvis göra arrayen större, men vad kan vi göra? Gör en ny array som är större, av storlek 6, eller kanske storlek 10, om vi vill att få ett försprång på saker, och sedan kopiera den gamla arrayen i den nya, och sedan frigöra den gamla matrisen. 

Men vad är det gångtid nu i den processen? Det är stort O n, eftersom kopiering kommer att kosta dig några enheter tid, så inte så perfekt om vi måste allokera en ny array, som kommer att konsumera dubbelt så mycket minnet tillfälligt. Kopiera gammalt till nytt - Jag menar, det är bara en huvudvärk, som är, återigen, varför vi skrev GetString för dig. 

Så vad kan vi göra i stället? Tja, tänk om vår datastruktur faktiskt har luckor i det? Antag att jag slappna av mitt mål att ha sammanhängande bitar av minnet, där 9 är rätt bredvid 17, vilket är precis intill 22, och så vidare. 

Och antar att 9 kan vara över här i RAM och 17 kan vara över här i RAM, och 22 kan vara över här i RAM. Med andra ord, jag behöver inte dem även tillbaka till tillbaka längre. Jag måste bara något trä en nål genom alla dessa siffror, eller varje av dessa noder, som vi kallar rektanglar som jag har ritat dem, ihåg hur man får till den sista sådan nod från det första. 

Så vad är programmering konstruktion Vi har sett ganska nyligen som jag kan genomföra denna tråd, eller dras här, som jag kan genomföra dessa pilar? Så pekare, eller hur? Om jag inte allokera bara en int, men en nod - och genom nod, menar jag bara behållare. Och visuellt, menar jag en rektangel. Så en nod behöver tydligen att innehålla två värden - int själv, och sedan, underförstådda som genom den nedre halvan av rektangeln, tillräckligt med utrymme för en int. 

Så bara tänka framåt här, hur stor är denna nod, detta container i fråga? Hur många bytes för int? Förmodligen 4, om det är samma som vanligt. Och sedan hur många bytes för pekaren? 4. Så här containern, eller denna nod, är kommer att vara en 8-byte struktur. Åh, och det är ett lyckligt sammanträffande att Vi introducerade just denna föreställning om en struct, eller en C-struktur. 

Så jag hävdar att jag vill ta ett steg mot detta mer sofistikerade Genomförandet av en lista med tal, en länkad lista med siffror, måste jag göra en lite mer tänkande fram och förklarar inte bara en int, men en struct att jag ringer, konventionellt här, nod. Vi kan kalla det vad vi vill ha, men nod kommer att vara tematiskt i en hel av de saker vi börja titta på nu. 

Insidan av den noden är en int n. Och sedan denna syntax, lite konstig vid första anblicken - struct node * nästa. Väl bildmässigt, vad är det? Det är den nedre halvan av rektangeln som vi såg bara en stund sedan. 

Men varför säger jag struct node * i motsats till bara nod *? För om det pekaren pekar på en annan nod, det är bara adressen för en nod. Det är i linje med vad vi har diskuteras om pekare hittills. Men varför, om jag hävdar denna struktur är kallas nod, måste jag säga struct nod inne här? 

Exakt. Det blir liksom en dum verklighet C. Den typedef, så att säga, har inte hänt ännu. C är SUPER bokstavlig. Den läser din kod topp till botten, vänster till höger. Och tills den träffar den semikolon på bottom line, gissa vad som inte existera som en datatyp? Node, citationstecken unquote nod. 

Men på grund av den mer utförliga förklaring jag gjorde på första raden - typedef struct node - eftersom det kom först, innan klammerparenteser, som är ungefär som pre-utbilda klang som du vet vad, ge mig en struct kallas struct node. Ärligt talat, jag gillar inte kalla saker struct node, struct node alla hela min kod. Men jag ska bara använda den en gång, strax innanför, så att jag kan effektivt skapa ett slags cirkulär referens, inte en pekare till mig själv per se, men en pekare till en annan av identisk typ. 

Så visar det sig att på en datastruktur så här, det finns ett fåtal verksamheter som kan vara av intresse för oss. Vi kanske vill infoga in i en lista som denna. Vi kanske vill ta bort från en lista som denna. Vi kanske vill söka i listan för en värde, eller mer generellt, travers. Och travers är bara ett finare sätt att säger start till vänster och flytta alla vägen till höger. 

Och varsel, även med denna något mer sofistikerade datastruktur, låt jag föreslår att vi kan låna några av idéer de senaste två veckorna och implementera en funktion som kallas söka så här. Det kommer att returnera sant eller falskt, vilket indikerar, ja eller nej, n är i listan. Dess andra argumentet är en pekare till själva listan, så en pekare till en nod. 

Allt jag ska gör sedan är deklarera en temporär variabel. Vi kallar det ptr av konvention, för pekaren. Och jag tilldelar det lika med början av listan. 

Och nu märker while-slingan. Så länge pekaren är inte lika till null, jag ska kolla. Är Pilpekaren n lika med n som antogs i? Och vänta en minut - ny bit syntax. Vad är pil helt plötsligt? Yeah? 

Exakt. Så medan några minuter sedan, använde vi dot notation för att komma åt något inne i en struct, om variabeln du har inte den struct själv, men en pekare till en struct, tack och lov, en bit av syntax som äntligen gör intuitiv känsla. Pilen betyder att följa pekaren, som våra pilar betyder vanligen bildmässigt, och gå på datafält inuti. Så pil är samma sak som prick, men du använda det när du har en pekare. 

Så bara för att sammanfatta då, om n fältet insidan av struct kallas pekaren lika lika n, return true. Annars denna linje här - pekare lika pekare nästa. Så vad detta gör, varsel, är om jag är för närvarande pekar på struct innehållande 9, och 9 är inte antalet Jag letar efter - antar jag letar för n är lika med 50 - Jag kommer att uppdatera min tillfälliga pekare att inte peka på denna nod längre, men pekaren pilen bredvid, vilket kommer att sätta mig upp hit. 

Nu insåg jag är en virvelvind introduktion. På onsdag ska vi faktiskt göra detta med vissa människor och med lite mer kod i en långsammare takt. Men inse, gör vi nu våra data strukturer mer komplex så att vår algoritmer kan få mer effektiva, vilket kommer att vara nödvändiga för pset sex, när vi laddar in, igen, de 150.000 ord, men måste göra det effektivt, och helst skapa en program som körs för våra användare inte linjär, inte i n kvadrat, men i konstant tid, i den ideala. 

Vi ses på onsdag. 

Speak: Vid nästa CS50, David glömmer sin basfallet. 

DAVID MALAN: Och det är hur du skickar textmeddelanden med C. Vad - 

[Blandat TEXTMEDDELANDE Meddelandeljud]