[MUSIK SPELA] 

[VIDEOAVSPELNING] 

-Han Ljuger. 

-Om vad? 

-Jag Vet inte. 

-Så Vad vet vi? 

-Det Vid 09:15, Ray Santoya var på ATM. -Ja. Så frågan är, vad gjorde han på 9:16? 

-Shooting 9 millimeter på något. Han kanske såg prickskytt. 

-Eller Arbetade med honom. 

-Vänta. Gå tillbaka en. 

-Vad ser du? 

-Ta Hans ansikte upp helskärmsläge. 

His glasögon. 

-Det Finns en reflektion. 

-Det Är Nuevitas basebollag. Det är deras logotyp. 

-Och Han pratar med vem bär den där jackan. 

[END SPELA] 

DAVID MALAN: Okej. Detta är CS50 och det är lite mer av [OHÖRBAR] som du är syssla med problem set fyra. Idag börjar vi titta lite mer djupt på dessa saker som kallas pekare, vilket även om det är en ganska svårbegripliga ämne, det visar sig att det kommer att vara det medel genom vilket vi kan börja bygga och montering mycket mer sofistikerade program. Men vi gjorde det på förra onsdagen medelst någon claymation först. Så det här, minns, är Binky och vi använde honom att ta en titt på ett program som egentligen inte göra något intressant, men det gjorde avslöja några problem. Så för att börja idag, varför inte vi gå snabbt igenom några av dessa steg, försöka destillera i mänskliga villkor exakt vad som händer här och varför det är dåligt, och sedan gå vidare och faktiskt börja bygga något med denna teknik? Så dessa var de första två rader i detta program och i lekmannaspråk, vad Dessa två linjer gör? Någon som är någorlunda bekväma med vad som anges på skärmen? Vilka är dessa två linjer gör? Det är inte alla som skiljer sig från vecka ett, men det finns några nya speciell symbol. Yeah? Tillbaka dit. 

PUBLIK: Deklarera pekare? DAVID MALAN: Säg igen? PUBLIK: Deklarera pekare? DAVID MALAN: Deklarera pekare och låt oss förfina det lite mer. PUBLIK: [OHÖRBAR] adress x och sedan y. DAVID MALAN: Och sedan ta itu med. Så specifikt vad vi gör är vi deklarerar två variabler. Dessa variabler, dock går att vara av typen int stjärna, som mer specifikt innebär de kommer att lagra adressen till en int, respektive, x och y. Nu finns det några värden? Finns det några konkreta adresser i dessa två variabler vid denna tidpunkt? Nej. Det är bara så kallade skräp värden. Om du faktiskt inte tilldela en variabel, oavsett var i RAM tidigare kommer att fyllas med nollor och ettor båda av dessa variabler. Men vi vet ännu inte vad de är och det är kommer att vara nyckeln till varför Binky tappat huvudet förra veckan. 

Så det här var claymation inkarnationen av denna där du har bara två variabler, små runda bitar av lera, som kan lagra variabler, men som de insvept pilarna antyder, de är faktiskt inte peka till någonstans känt i sig. Så då hade vi denna linje, och detta var nya förra veckan, malloc för minne tilldelning, som ligger bara ett fint sätt att tala om för operativsystemet, Linux eller Mac OS eller Windows, hej, ge mig lite minne, och allt du behöver för att berätta operativsystemet är vad när ber den för minnet. Det kommer inte att bry sig om vad du kommer att göra med det, men du behöver tala om för operativsystemet systemet vad genom malloc. Yeah? 

PUBLIK: Hur mycket? DAVID MALAN: Hur mycket? Hur mycket i byte, och så, denna, återigen, en krystat exempel bara säga, ge mig storleken på en int. Nu, storleken på en int är fyra bitgrupper eller 32 bitar. Så det här är bara ett sätt att säger, hej, operativsystem, ge mig fyra byte minne att jag kan använda till mitt förfogande, och specifikt, vad gör malloc avkastning med respekt till den del av fyra byte? PUBLIK: Adress? DAVID MALAN: Adressen. Adressen till den del av fyra byte. Exakt. Och så det är vad som lagras i slutändan ix och det är därför vi inte riktigt bry sig om vad antalet som adress är, oavsett om det är OX1 eller OX2 eller några kryptiska hexadecimal adress. Vi bryr oss bara pictorially att denna variabel x är nu pekar på att bit av minnet. Så att pilen representerar en pekare, eller mer specifikt, en minnesadress. Men återigen, vi vanligtvis inte bryr vad de faktiska adresser är. Nu, säger denna linje vad i lekmannaspråk? Star x får 42 semikolon. Vad betyder det här? You wanna go? Repa inte halsen. 

PUBLIK: Adressen till x är vid 42. 

DAVID MALAN: Adressen till x är vid 42. Inte riktigt. Så nära, men inte riktigt, eftersom det finns stjärnan som är prefixing denna x. Så vi måste justera lite. Yeah? 

Publik: Det värde som pointer x pekar på är 42. DAVID MALAN: OK. Värdet som pekaren x är pekar på, låt oss säga, ska vara 42, eller annorlunda uttryckt, stjärnan x säger, gå till valfri adress är i x, oavsett om det är ett Oxford Gata eller 33 Oxford Street eller OX1 eller ox33, oavsett att numerisk adress är, stjärna x är Återgång för x. Så gå till den adressen och då uppskattar antalet 42 där. Så det skulle vara en likvärdigt sätt att säga det. Så det är allt bra och sedan Vi skulle representera bilden på följande sätt där vi har lagt 42 till den del av fyra bytes på den högra sidan, men denna linje var där saker gick snett och Binky huvud poppade av vid denna punkt, eftersom dåliga saker hända när du dereference sopor värden eller om du dereference ogiltigt pekare, och jag säger ogiltig eftersom det vid denna punkt i historia, vad som finns i y? Vad är värdet av y baserad på de senaste stegen? Yeah? Vad är det? 

Publik: En adress. DAVID MALAN: En adress. Det bör vara en adress men har jag initierat det? Så jag har inte ännu. Så vad som är känt för att vara där? Det är bara några sopor värde. Det kan vara vilken adress som helst från noll till 2000000000 om du har två gig RAM, eller noll till 4 miljarder om du har fick fyra gigabyte RAM-minne. Det är en del skräp värde, men problemet är att operativsystemet, om det inte har gett dig att bit av minnet specifikt att du försöker att gå till, det är allmänt kommer att orsaka vad vi har sett som en segmentering fel. Så i själva verket, någon av er som har kämpade på problem på kontorstid eller problem som är mer i allmänhet med att försöka räkna ut en segmentering fel, som i allmänhet innebär du rör vid en del av minne som du inte bör vara. Du röra minne som operativsystemet har inte tillåtit dig att röra, oavsett om det är genom att gå för långt i din samling eller starta nu, om Det är för att du vidrör minne som bara är några skräp värde. 

Så gör stjärniga x här är sorts odefinierat beteende. Du ska aldrig göra det eftersom odds är, är programmet bara kommer att krascha, eftersom du säger, gå till denna adress och du har ingen aning om den adressen faktiskt är. Så operativsystemet är sannolikt kommer att krascha ditt program som ett resultat och faktiskt, det är vad som hände där till Binky. Så i slutändan, Binky fast Detta problem med detta. Så att själva programmet var felaktig. Men om du typ av gå framåt och verkställa denna linje istället, y är lika med x betyder bara vad adress är ett x, också lägga den i y. 

Och så pictorially, vi har representerade här med två pilar från x och y från pekar till samma plats. Så semantiskt är x lika till y eftersom båda dessa lagrar samma adress, ergo pekar på 42, och nu, när du säger stjärnan y, gå till adressen i y, Detta har en intressant bieffekt. Så adressen i y är samma sak som adressen i x. Så om du säger gå till adressen i y och ändra värdet till 13, vem påverkas? X, punkt D, så att säga, bör påverkas också. 

Och faktiskt, hur Nick drog denna bild i claymation var just detta. Även om vi följer pekaren y, vi hamnade på samma plats, och så om vi skulle skriva ut ut x eller y är pointee, då skulle vi se värdet av 13. Nu säger jag pointee vara förenlig med videon. Programmerare, till min kunskap, aldrig säga ordet pointee, det som är spetsig på, men för konsekvensens med videon, inse det är allt som var menas i den situationen. Så några frågor om claymation eller pekare eller malloc ännu? Nej? Okej. 

Så utan vidare ADO, låt oss ta en titt på om detta har faktiskt använts under en längre tid. Så vi har haft denna CS50 bibliotek som har fått alla dessa funktioner. Vi har använt getInt en hel del, getString, förmodligen GetLongLong tidigare i min PSET ett eller så, men vad som faktiskt pågått? Nåväl, låt oss ta en snabb titt under huven på ett program som inspirerar därför vi ger dig CS50 bibliotek, och även som i förra veckan, Vi började ta dem utbildning hjul off. Så det här är nu sorteras av en postmortem av vad har pågått inne i CS50 biblioteket trots att vi nu kommer att börja röra sig bort från det för de flesta program. 

Så det här är ett program som kallas scanf 0. Det är super kort. Det har bara dessa linjer, men det introducerar en funktion kallad scanf att vi faktiskt kommer att se i en stund inne i CS50 biblioteket om än i en något annorlunda form. Så det här programmet på rad 16 är att förklara en variabel x. Så ge mig fyra byte för en int. Det har varit träffande användaren, antal snälla, och sedan detta är en intressant linje som faktiskt binder samman förra veckan och det här. Scanf, och sedan märker att det tar formatsträng, precis som printf, % i innebär en int, och sedan tar det en andra argument som ser lite funky. Det är et-tecken x, och att återkalla, Vi såg bara denna gång förra veckan. Vad-tecken x representerar? Vad gör ampersand i C? Yeah? 

PUBLIK: Adressen till. DAVID MALAN: Adressen till. Så det är motsatsen av stjärnan operatör, medan stjärnan operatören säger, gå till denna adress, et-tecknet operatören säger, räkna ut adress denna variabel, och så detta är nyckeln, eftersom scanf syfte i livet är att skanna användarens input från tangentbordet, beroende på vad han eller hon typer och sedan läsa att användarens input in i en variabel, men vi såg under de senaste två veckorna att denna swap funktion som vi försökte enkelt att genomföra var bara bruten. Minns att med växlingsfunktionen, om vi bara förklarade A och B som Ints, vi framgångsrikt byta två variabler inuti swap precis som med mjölk och EGT, men så snart swap tillbaka, vad blev resultatet när det gäller till x och y, de ursprungliga värdena? Ingenting. Yeah. Ingenting hände den tiden, eftersom swappar bara ändra sina lokala kopior, det vill säga, alla den här gången, när vi har varit passerar argument till funktioner, vi är bara passerar kopior av dessa argument. Du kan göra med det vad du vill med dem, men de kommer att ha någon effekt på de ursprungliga värdena. Så detta är problematiskt om du vill ha en funktion som scanf i livet, är vars syfte är att skanna användarens input från tangentbordet och sedan fylla i tomrummen, så att tala, dvs ge en variabel som X ett värde, för om jag var att bara passera x scanf, om du anser att logiken i sista vecka, kan scanf göra vad det vill med en kopia av x, men den kunde inte permanent ändra x om vi inte ger scanf en skattkarta, så att säga, där x markerar fläcken, varvid vi passerar in adressen till x så att scanf kan åka dit och faktiskt förändring värdet på x. Och så ja, alla att detta program inte om jag gör scanf 0, i min källa 5m katalog, gör scanf 0, dot slash scanf, antal vänligen 50, tack för 50. 

Så det är inte så intressant, men vad som verkligen händer är att så fort som jag kallar scanf här, värdet på x är permanent ändras. Nu verkar nice och bra, och i själva verket, det verkar som om vi inte verkligen behöver den CS50 biblioteket alls längre. Till exempel, låt oss köra denna gång mer här. Låt mig återuppta det för en sekund. Låt oss prova ett antal vänligen och istället för att säga 50 som förut, låt oss bara säga nej. OK, det är lite konstigt. OK. Och bara några dumheter här. Så det verkar inte hantera felaktiga situationer. Så vi behöver minimalt start att lägga till några felkontroll att se till att användaren har skrev i ett verkliga antalet som 50, eftersom det tydligen skriva ord inte detekteras som problematiska, men det förmodligen bör vara. 

Låt oss titta på denna version nu som är mitt försök att reimplement getString. Om scanf har allt detta funktionalitet inbyggd, Varför har vi syssla med dessa utbildning hjul som getString? Tja, här är kanske mitt eget enkel version av getString varigenom en vecka sedan, kunde jag ha sagt, ge mig en sträng och kallar det buffert. Idag kommer jag att bara börja säger röding stjärna, som minns, det är bara synonyma. Det ser skrämmande men det är exakt samma sak. Så ge mig en variabel som heter buffert som kommer att lagra en sträng, tala om för användaren strängen snälla, och sedan, precis som tidigare, låt oss försöka låna den här lektionen scanf % s denna gång och sedan passera i buffert. Nu, en snabb kontroll förstånd. Varför får jag inte säga -tecken buffert den här gången? Sluta från föregående exempel. PUBLIK: Char stjärnan är en pekare. DAVID MALAN: Exakt, eftersom den här gången, röding stjärna är redan en pekare, en adress, per definition av stjärnan vara där. Och om scanf förväntar sig en adress, räcker det bara att passera i buffert. Jag behöver inte säga ampersand buffert. För den nyfikne, du kan göra något sånt här. Det skulle ha olika innebörd. Detta skulle ge dig en pekare till en pekare, som är faktiskt en giltig sak i C, men för nu, låt oss hålla det enkelt och hålla historien konsekvent. Jag kommer bara att passera buffert och det är korrekt. Problemet är dock redan. Låt mig gå vidare och köra program efter att kompilera det. Gör scanf 1. Fan det, min kompilator fånga mitt fel. Ge mig en sekund. Klang. Låt oss säga att scanf-1.c. OK. Det går vi. Jag behöver det. CS50-ID har olika konfigurationsinställningar som skyddar dig mot dig själv. Jag behövde för att inaktivera dem genom kör clang manuellt den här gången. Så sträng snälla. Jag kommer att gå vidare och skriva i min favorit hallå världen. OK, null. Det är inte vad jag skrev. Så det är ett tecken på något att ha fel. Låt mig gå vidare och skriva i en riktigt lång sträng. Tack för noll och jag vet inte om jag kommer att kunna krascha den. Låt oss prova lite kopia klistra och se om det hjälper. Bara klistra in en hel del av detta. Det är definitivt en större sträng än vanligt. Låt oss bara verkligen skriva det. Nej. Jäklar. Command not found. Så det är orelaterade. Det beror på att jag klistrade några dåliga tecken, men det visar sig inte kommer att fungera. 

Låt oss försöka detta en gång till, eftersom Det är roligare om vi faktiskt kraschar det. Låt oss skriva detta och nu är jag kommer att kopiera en riktigt lång sträng och nu ska vi se om vi kan krascha den här saken. Märker jag utelämnade utrymmen och nya linjer och semikolon och alla funky tecken. Enter. Och nu nätverket är bara att vara långsam. Jag höll ner Kommando-V för länge, uppenbarligen. Jäklar! Command not found. 

OK. Tja, är poängen ändå följande. Så vad som verkligen händer på detta uttalande röding stjärna buffert på linjen 16? Så vad jag får när jag deklarerar en pekare? Allt jag får är en fyra byte värde kallas buffert, men vad som finns inuti det just nu? Det är bara några sopor värde. Eftersom varje gång du deklarerar en variabel i C, är det bara några sopor värde, och vi börjar resa över denna verklighet. Nu, när jag berättar scanf, gå till denna adress och satte oavsett användaren skriver i. Om användaren skriver i hello värld, ja, var kan jag uttrycka det? Buffert är ett skräp värde. 

Så det är ungefär som en pil som är pekar vem vet var. Kanske det pekar rätt här i mitt minne. Och så när användaren typer i hallå världen, Programmet försöker sätta sträng hello world backslash 0 i denna bit av minne. Men med stor sannolikhet, men uppenbarligen inte 100% sannolikhet, datorn kommer att sedan krascha programmet eftersom detta inte är minne jag bör tillåtas att röra. Så kort sagt, är det här programmet bristfälliga för just den anledningen. Jag i grunden inte gör vad? Vilka åtgärder har jag utelämnat, precis som Vi utelämnade med Binky första exempel? Yeah? 

PUBLIK: Memory allocation? 

DAVID MALAN: Memory tilldelning. Jag har faktiskt inte tilldelats något minne för den raden. Så vi kan fixa detta i ett par olika sätt. En, kan vi hålla det enkelt och i själva verket, nu är du kommer att börja se en oskärpa av linjerna mellan vad en array är, vad en sträng är, vad en röding stjärna är, vad en rad tecken är. Här är ett andra exempel involverar strängar och varsel allt jag har gjort på nätet 16 är, istället för att säga denna buffert kommer att bli en röding stjärna, en pekare till en bit av minne, Jag ska mycket proaktivt ge själv en buffert för 16 tecken, och i själva verket, om du är bekant med termen buffring, troligen från världen av videos, där en video är buffring, buffring, buffring. Nå, vad är kopplingen här? Tja, Insidan av YouTube och insidan av videospelare i allmänhet är en array som är större än 16. Det kan vara en rad storlek en megabyte, kanske 10 megabyte, och in i den matris gör din webbläsare ladda ner en massa byte, en massa megabyte video och videospelare, YouTubes eller vem är, startar läsning av byte från denna matris, och varje gång du ser det ord buffring, buffring, som innebär att spelaren har kommit till slutet av denna uppsättning. Nätet är så långsam att den inte har fyllas arrayen med fler bytes och så du är ute bitar att visa för användaren. 

Så buffert är en apt term här genom att det är bara en uppsättning, en bit av minne. Och detta kommer att fixa det eftersom det visar sig att du kan behandla matriser som om De är adresser, även om buffert är bara en symbol, det är en sekvens av tecken, buffert, det är nyttigt för mig, programmeraren, du kan skicka sitt namn runt som om det vore en pekare, som om det var adressen till en bit minne för 16 tecken. Så det är att säga, kan jag passera den scanf exakt det ordet och så nu, om jag gör det här programmet, göra scanf 2, pricka snedstreck scanf 2, och skriv in hallå världen, Ange att time-- 

Hmm, vad hände? String vänligen. Vad gjorde jag för fel? Hej världen, buffert. Hej världen. Ah, jag vet vad den gör. OK. Så det är att läsa upp tills det första utrymmet. Så låt oss fuska för bara en stund och säga att jag ville bara skriva något riktigt långt som detta är en lång mening det är ett, två, tre, fyra, fem, sex, sju, åtta, nio, 10, 11, 12, 13, 14, 15, 16. OK. Det är verkligen en lång mening. Så här meningen är längre än 16 tecken och så när jag slog in, vad som kommer att hända? Jo, i detta fall av historia, jag hade förklarat buffert att faktiskt vara en matris med 16 tecken redo att gå. Så en, två, tre, fyra, fem, sex, sju, åtta, nio, tio, elva, tolv, tretton, 14, 15, 16. Så 16 tecken, och nu, när jag läs i något sånt här är en lång mening, vad som kommer att hända är att jag kommer att läsa i detta är en lång S-E-N-T-E-N-C-E, mening. 

Så detta är medvetet en dålig sak som jag fortsätta skriva bortom gränserna för min array, bortom gränserna för min buffert. Jag kunde ha tur och programmet kommer att hålla på löpning och inte bryr sig, men generellt sett, denna kommer verkligen krascha mitt program, och det är en bugg i min koda det ögonblick jag steg bortom gränserna av den matris, eftersom jag vet inte om det är nödvändigtvis kommer att krascha eller om jag bara kommer att få tur. Så detta är problematiskt eftersom det i det här fallet, det verkar fungera och låt oss fresta öde här, även om IDE verkar tolerera ganska lite of-- 

Det går vi. Slutligen. Så jag är den enda som kan se detta. Så jag hade bara en massa roligt att skriva en riktigt lång faktiska fras att det verkligen överträffat 16 bytes, eftersom jag skrivit i denna galna lång multi-line fras, och sedan märker vad som hände. Programmet försökte skriva ut det och sedan fick en segmentering fel och segmente fel är när något sådant här händer och operativsystemet säger nej, kan inte röra det minnet. Vi kommer att döda programmet helt och hållet. 

Så detta verkar problematiskt. Jag har förbättrat programmet vari åtminstone ha en del minne, men detta förefaller begränsa funktionen getString att få strängar av någon ändlig längd 16. Så om du vill stödja längre meningar än 16 tecken, Vad gör du? Tja, kan du öka Storleken på denna buffert till 32 eller som verkar slags kort. Varför inte vi bara göra det 1000 men skjuta tillbaka. Vad är svaret intuitivt av bara undvika detta problem genom att göra min buffert större, liksom 1000 tecken? Genom att implementera getString detta sätt. Vad som är bra eller dåligt här? Yeah? PUBLIK: Om du binda upp en hel del utrymme och du inte använder den, då du inte kan omfördela det utrymmet. DAVID MALAN: Absolut. Det är slöseri mån om du inte faktiskt behöver 900 av dessa bytes och ändå du ber om 1000 totalt i alla fall, du bara förbrukar mer minne på användarens dator än vad du behöver, och trots allt, en del av Du har redan stött i livet att när du är kör massor av program och de äter upp massor av minne, detta kan faktiskt påverka prestanda och användarens upplevelse på datorn. Så det är lite av en lat lösning, säker, och omvänt, Det är inte bara slöseri, vilket problem fortfarande, även om jag gör min buffert 1000? Yeah? 

PUBLIK: Strängen är längden 1001. DAVID MALAN: Exakt. Om din sträng är längd 1001, du har exakt samma problem, och genom min argumentation, skulle jag just då göra det 2000, men du vet inte in förväg hur stor den ska vara, och ändå, måste jag kompilera mitt program innan du låter människor använder och nedladdning Det. Så det här är precis den typ av saker som de CS50 biblioteket försöker att hjälpa oss med och vi ska bara blick på några av de underliggande genomförandet här, men detta är CS50 dot C. Denna är den filen som har varit på CS50 IDE alla dessa veckor som du har använt. Det är förkompilerade och du har använt det automatiskt som på grund av att ha dash L CS50 flagga med klang, men om jag bläddra ner genom alla dessa funktioner, här är getString, och bara för att ge dig en smakprov på vad som händer, låt oss ta en snabb titt på den relativa komplexiteten. Det är inte en super lång funktion, men vi gjorde inte måste tänka alla hårt om hur man ska gå om att få strängar. 

Så här är min buffert och jag tydligen initiera den till noll. Detta, naturligtvis, är den Samma sak som röding stjärna, men jag bestämde mig i genomförandet av CS50 biblioteket att om vi ska vara helt dynamisk, Jag vet inte i förväg hur stor av en sträng användare kommer att vilja få. Så jag kommer att börja med bara en tom sträng och jag kommer att bygga upp så mycket minne som jag behöver för att passa användaren strängen och om jag inte har nog, kommer jag att be operativsystemet för mer minne. Jag kommer att flytta sin sträng till en större bit av minne och jag kommer att frigöra eller befria otillräckligt stor del av minnet och vi ska bara att göra detta iterativt. 

Så en snabb blick, här är bara en variabel som jag kommer att hålla koll av kapaciteten i min buffert. Hur många bytes kan jag passar? Här är en variabel n med som jag kommer att hålla koll på hur många bytes är faktiskt i bufferten eller att användaren har skrivit. Om du inte har sett det här förut, du kan ange att en variabel som ett int är osignerad, vilket som namnet antyder, innebär att det är icke-negativt, och varför skulle Jag någonsin vill bry specificerar att en int är inte bara en int, men det är en osignerad int? Det är ett icke-negativt int. Vad gör [OHÖRBAR] detta? 

PUBLIK: Det beskriver ett belopp av minne som kan vara [OHÖRBAR]. 

DAVID MALAN: Ja. Så om jag säger osignerade, är detta faktiskt ger dig en bit av extra minne och det verkar slags dumt, men om du har en bit av extra minne, att innebär att du har dubbelt så många värden du kan representera, eftersom det kan vara en 0 eller en 1. Så som standard, kan en int vara ungefär negativa 2000000000 hela vägen upp till positiv 2 miljarder. De är stora intervall, men det är fortfarande slags slöseri om du bara bryr sig om storlekar som just intuitivt bör vara icke-negativa eller positivt eller 0, ja då, varför är du slösar 2000000000 möjliga värden för negativa tal om du aldrig kommer att använda dem? Så genom att säga osignerade, nu min int kan vara mellan 0 och cirka 4 miljarder. 

Så här är bara en int C skäl vi kommer inte att komma in just nu som varför det är en int i stället av en röding, men här är kontentan av vad som händer på, och några av er kanske använder, till exempel, den fgetc funktion även i PSET fyra eller senare, vi får se det igen i problemet set fem, fgetc är trevligt eftersom som namnet sorts föreslår slags arcanely, Det är en funktion som får en karaktär och så, vad är fundamentalt annorlunda om vad vi gör i getString är att vi inte använder scanf på samma sätt. Vi är bara kryper längs steg-för-steg över vad användaren har skrivit in, eftersom vi kan alltid tilldela en röding, och så kan vi alltid säkert titta på en röding i taget, och magin börjar hända här. Jag kommer att rulla ner till mitt i denna funktion bara för att presentera kortfattat denna funktion. Ungefär som det finns en malloc funktion, det finns en realloc funktion där realloc låter dig omfördela en del av minne och gör det större eller mindre. Så lång historia kort och med en våg av min hand för idag, vet att det som getString gör är det är typ av magiskt växer eller krympande bufferten som användaren typer i hans eller hennes sträng. 

Så om användaren skriver ett kort sträng, denna kod endast allokerar tillräckligt minne för att passa strängen. Om användaren håller skriva som jag gjorde det igen och igen och igen, väl, om buffertens början denna stora och programmet inser, att vänta en minut, jag är ute i rymden, det kommer att fördubbla storleken på bufferten och sedan fördubbla storleken på bufferten koden som gör fördubbling, Om vi ​​tittar på det här, det är just detta smarta one-liner. Du kanske inte har sett denna syntax innan, men om du säger stjärnan är lika, Detta är samma sak som säga kapacitets gånger 2. Så det blir bara en fördubbling kapaciteten av bufferten och sedan träffande realloc att ge sig om att mycket mer minne. 

Nu, som en sidoreplik, det är andra funktioner i här att vi inte kommer att undersöka detalj annat än att visa i getInt, vi använder getString i getInt. Vi kontrollerar att det inte är null, som minns, är det särskilt värde som betyder något gick fel. Vi är slut på minne. Bättre kontrollera det. Och vi återvänder en vaktpost värde. Men jag ska skjuta till kommentarerna beträffande varför och sedan använder vi denna kusin scanf kallas sscanf och det visar sig att sscanf eller sträng scanf, låter dig ta en titt på den linje som användaren har skrivit in och låt dig analysera det i huvudsak och vad jag gör här är jag säger sscanf, analysera vad användaren har skrivs in och se till att% i, Det är ett heltal i det, och vi kommer inte komma in i dag exakt varför det finns också en% c här, men att det i ett nötskal tillåter oss att detektera om användaren har matat in i något falska efter numret. Så anledningen till att getInt och getString berätta för dig att försöka igen, försöka igen, försök igen är på grund av alla den koden vi har skrivit, det är typ att titta på användarens input i att se till att det är helt numerisk eller det är en verklig flytande punktvärde eller liknande, beroende på vilket värde fungera du använder. 

Whew. OK. Det var en munsbit men poängen här är att anledningen till att vi hade dessa stödhjulen på beror på den lägsta nivån, Det finns bara så många saker som kan gå fel att vi ville ha att preemptively hantera dessa saker säkerligen i tidigaste veckor för klassen men nu med PSET fyra och PSET fem och bortom ser du att det är mer åt dig men också du är mer kapabel att lösa dessa typer av problem själv. Har du frågor om getString eller getInt? Yeah? 

PUBLIK: Varför skulle du dubbla kapaciteten av bufferten snarare än att bara öka det genom det exakta beloppet? 

DAVID MALAN: Bra fråga. Varför skulle vi fördubbla kapaciteten av bufferten i motsats att bara utöka av någon konstant värde? Det var ett beslut design. Vi har just beslutat att eftersom det tenderar att vara lite dyrt tidsmässigt att fråga operativsystemet för minne, gjorde vi inte vill sluta få in en situation för stora strängar att vi bad OS och om igen och om och om igen i snabb följd för minnet. Så vi just beslutat, något godtyckligt men vi hoppas rimligen, att du vet vad, låt oss försöka få framför oss och bara hålla fördubbling det så att vi minimera mängden gånger Vi måste ringa malloc eller realloc, men en total bedömning ring i avsaknad av att veta vad användarna kanske vill skriva in. Båda sätten kan vara diskutabelt. Förmodligen bra. 

Så låt oss ta en titt på ett par andra biverkningar av minne, saker som kan gå fel och verktyg som du kan använda för att fånga dessa typer av misstag. Det visar sig er alla, även om check50 har inte sagt så mycket, har skrivit buggy kod eftersom vecka ett, även om alla check50 tester är passerat, och även om du och din TF är super säkra på att koden fungerar som det är tänkt. Koden har buggy eller brister på att ni alla, vid användning av CS50 biblioteket har läcker minne. Du har begärt att operativsystemet för minne i de flesta program du har skrivit, men du har aldrig gett det tillbaka. Du har kallat getString och getInt och getFloat, men med getString, du har aldrig kallas unGetString eller Ge String Bakåt eller liknande, men vi har sett att getString inte allokera minne genom malloc eller detta funktions realloc, som är bara mycket i samma anda, och ändå har vi varit frågar operativsystemet för minne och minne och om igen men aldrig ge det tillbaka. 

Nu, som en sidoreplik, visar det sig att när ett program avslutas, allt minne automatiskt befrias. Så det har inte varit en stor affär. Det kommer inte att bryta IDE eller sakta ner saker, men när programmen gör läcker generellt minne och de kör under en lång tid. Om du någonsin har sett dumma lilla badboll i Mac OS eller timglaset Windows där det är typ av bromsa eller tänker eller tänkande eller bara verkligen börjar att sakta till en genomsökning, det mycket skulle kunna vara resultatet av en minnesläcka. Programmerarna som skrev programvaran du använder be operativsystem för minne med några minuters mellanrum, varje timme. Men om du kör mjukvara, även om det är minimeras i din dator timmar eller dagar i sträck, du kanske att begära mer och mer minne och aldrig faktiskt använder det och så din kod kan vara, eller program kan läcka minne, och om du börjar läcka minne, det finns mindre minne för andra program, och effekten är att sakta ned allt. 

Nu är detta absolut en av de mest avskyvärda programmen du kommer att ha möjligheter att köra i CS50 mån som dess utgång är ännu mer esoteriska än klang: s eller göra eller någon av kommandot linje program vi har körs innan men tack och lov, inbäddat i sin produktion är några super användbara tips som kommer att vara användbart antingen för PSET fyra eller säkert PInstallera fem. Så valgrind är ett verktyg som kan användas för att leta för minnesläckor i ditt program. Det är relativt enkelt att köra. Du kör valgrind och då, även även om det är lite mångordig, streck streck läckagekontroll lika fullt, och sedan dot snedstreck och namnet på ditt program. Så valgrind kommer sedan köra ditt program och i slutet av ditt program kör innan det avslutas och ger dig en annan snabb, det kommer att analysera din program samtidigt som det har varit igång och berätta gjorde du läcker något minne och ännu bättre, har du trycker minne som inte tillhörde dig? Det kan inte fånga allt, men det är ganska bra på att fånga det mesta. 

Så här är ett exempel på min har körts detta program har körts valgrind, om ett program som kallas minne, och jag kommer att lyfta fram de linjer som är i slutändan av intresse för oss. Så det finns ännu fler distraktioner att jag har tagit bort från bilden. Men låt oss bara se vad detta Programmet är i stånd att berätta. Det är kapabel att berätta saker som ogiltiga skrivning av storlek 4. Med andra ord, om du rör minnet, specifikt 4 byte minne att du inte ska ha, valgrind kan berätta för er att. Ogiltig skrivning av storlek 4. Du berörde fyra byte att du inte ska ha. Var gjorde du det? Detta är skönheten. Minnes dot c linje 21 är där du skruvas upp och det är därför det är bra. Ungefär som GDB, kan det hjälpa pekar du på själva felet. 

Nu är det här en lite mer verbose, om inte förvirrande. 40 byte i 1 block är definitivt förlorade i förlust rekord 1 av 1. Vad betyder det? Tja, det betyder bara att du bad om 40 bytes och du aldrig gav det tillbaka. Du ringde malloc eller så kallade GetString och operativsystemet gav dig 40 bytes, men du aldrig frigörs eller utsläppt att minnet, och för att vara rättvis, har vi aldrig visa hur du ge tillbaka minnet. Det visade sig att det finns en super enkel funktion kallade fria. Tar ett argument, saken du vill frigöra eller ge tillbaka, men 40 bytes, tydligen, i detta program har förlorat på rad 20 av minnet dot c. 

Så låt oss se det här programmet. Det är super värdelös. Det visar bara denna speciella fel. Så låt oss ta en titt. Här är huvud och huvud, meddelande, samtal en funktion som kallas f och sedan tillbaka. Så inte så intressant. Vad f göra? Märker jag inte brydde sig med en prototyp. Jag ville hålla koden så liten som möjligt. Så jag satte f över huvud- och det är bra, säkert, för korta program som detta. Så f inte tillbaka något och gör inte ta något, men det gör det. Den förklarar, ungefär som i Binky exempel en pekare som heter x som händer att lagra adressen för en int. Så det är den vänstra sidan. På engelska, vad är det höger sida gör? Någon? Vad är detta gör för oss? Yeah? 

PUBLIK: [OHÖRBAR] gånger större än en int vilket är 10 gånger högre än [OHÖRBAR] DAVID MALAN: Bra och låt mig sammanfatta. Så allokera tillräckligt med utrymme för 10 heltal eller 10, vad är storleken på en int, Det är fyra byte, så 10 gånger 4 är 40, så att höger sida som jag har markerade är ge mig 40 byte och lagra adressen hos den första bitgruppen in x. Och nu slutligen, och här är där detta program är buggig, vad är fel med linje 21 baserat på denna logik? Vad är det för fel med linje 21? Yeah? PUBLIK: Du kan inte index till x [OHÖRBAR]. DAVID MALAN: Ja. Jag borde inte index till x så. Så syntaktiskt, det är OK. Vad är trevligt är mycket som du kan behandla namnet på en matris som om det är en pekare, på samma sätt kan du behandla en pekare som om det är en matris, och så jag kan syntaktiskt säger x fäste något, x fäste i, men 10 är problematisk. Varför? 

PUBLIK: Eftersom det är inte inne. 

DAVID MALAN: Det är inte inuti den del av minnet. Vad är det största värdet jag skulle att lägga i dessa hakparenteser? 9, 0 till 9. På grund av noll indexering. Så 0 till 9 skulle vara bra. Konsol 10 är inte bra och men minns dock, varje gång Jag verkar försöka göra CS50 IDE krasch genom att skriva in falska värden, det är inte alltid samarbeta, och faktiskt, du ofta tur bara för att operativsystem inte märker att du aldrig så lite passera någon bit av minnet, eftersom du bott inom tekniskt din segment, men mer om det i ett operativsystem klass, och så ungefär så här kan mycket lätt gå oupptäckt. Ditt program kommer aldrig att krascha konsekvent men kanske en gång i ett tag. 

Och så låt oss försöka valgrind på detta, och här är där vi får överväldigad av utsignalen momentant. Så gör minnes valgrind läckagekontroll lika fullt prick snedstreck minne. Och här är varför jag lovar Detta skulle överväldiga. Här är vad valgrind, här är vad en programmerare, några år sedan- beslutade att det skulle vara en bra idé för utgången att se ut. Så låt oss att förstå detta. Så hela vägen till vänster sida utan goda skäl är process-ID för programmet vi bara köra, unik identifierare för det program som vi bara sprang. Vi utgår det från bilden, men det är användbar information här. 

Låt oss bläddra upp till den absoluta toppen. Här är där vi började. Så det är inte så mycket utgång. Här är det ogiltiga skriv storlek 4 på rad 21. Nå, vad var ledningen 21? Linje 21 var exakt detta och det är vettigt att jag är i giltigt skriver 4 byte eftersom jag är försöker sätta detta heltal, vilket kan vara allt, Det råkar bara vara noll, men jag försöker för att uttrycka det på ett ställe som inte tillhör mig. Dessutom, här nere, 40 byte i en block definitivt förlorade på rekordtid 1. Det beror på när jag ringer malloc här, jag faktiskt aldrig frigöra minnet. 

Så hur kan vi fixa det här? Låt mig gå vidare och vara lite säkrare och gör 9 där och låt mig här fri x. Detta är den nya funktionen för idag. Om jag nu köra göra minnes dot snedstreck, låt oss köra valgrind på det igen, maximera mitt fönster och tryck på Retur. Nu är det bra. De begrava de goda nyheterna i allt detta utgång. Alla heap block var gratis. Vi ska återkomma till vad högen är, men inga läckage kan inträffa. Så det här är bara en annan verktyg för din verktygslåda med vilken du kan börja hitta nu fel som. 

Men låt oss se vad mer kan gå fel här. Låt oss övergång nu faktiskt lösa ett problem. Som en sidoreplik, om detta kommer att befria en lite förvirring eller spänning, detta är nu roligt. Yeah. Det är ganska bra. Eftersom pekare är adresser och adresser är i allmänhet av konvention skriven med hexadecimal. Ha, är ha denna roliga nu. Hur som helst, så låt oss nu faktiskt lösa ett problem. Detta har varit super, super låg-nivå hittills, och vi kan faktiskt göra nytta saker med dessa uppgifter på låg nivå. 

Så vi introducerade några veckor sedan begreppet en array. En array var trevligt eftersom det är svårt att städa upp vår kod eftersom om vi ville skriva en program med flera elever eller flera namn och hus och sovsalar och högskolor och allt detta, vi kunde lagra allt mer rent insidan av en matris. Men föreslå en nackdel av en array hittills. Även om du inte har lidit det själv i ett program, bara instinktivt, vad är en dålig sak om en array, kanske? Jag hör några mummel. PUBLIK: Det är svårt för att ändra storlek. DAVID MALAN: Det är svårt för att ändra storlek. Du kan inte ändra storlek av en array, i själva verket, i och för sig i C. Du kan tilldela en annan array, flytta allt från gamla i det nya, och nu ha lite extra utrymme, men det är inte som en språk som Java eller Python eller valfritt antal andra språk med vilket en del av er kan känna när du kan bara fortsätta att lägga till saker till leda till slutet av en array. När du har en rad storlek 6, som är dess storlek, och så mycket som idén tidigare med en buffert av en viss storlek, du måste gissa ut ur porten Vilken storlek vill du att det ska vara? Om du gissar för stort, du slösar utrymme. Om du gissar för liten, du kan inte lagra dessa uppgifter, åtminstone utan en mycket mer arbete. 

Så idag, tack vare pekare, vi kan börja sy ihop våra egna datastrukturer, och Faktum är att här är något som ser lite mer kryptiskt vid första anblicken, men detta är vad vi kallar en länkad lista, och dess namn slags sammanfattar Det. Det är en lista med tal, eller det här fallet, en lista med tal, men det kan vara en lista över vad som helst, men det är sammanlänkade med hjälp av pilar, och bara ta en gissning med vilken teknik kommer vi att kunna att sy ihop, ungefär som popcorn med en tråd, en länkad listor rektanglar här? Dess siffror? Vad är det underliggande språket funktionen? 

Publik: En pekare. 

DAVID MALAN: En pekare. Så var och en av dessa pilar här representerar en pekare eller bara en adress. Så med andra ord, om jag vill att lagra en lista med tal, Jag kan inte bara lagra den om jag vill förmågan att växa och krympa min datastruktur i en array. Så jag måste ha lite mer sofistikerade, men märker att detta bild slags antyder att om du bara har små trådar ansluter allt tillsammans, förmodligen är inte så svårt att göra utrymme i mellan två av dessa rektanglar eller två av dessa noder, som vi kommer att börja kalla dem, sätta i en ny nod, och sedan med några nya tråd, bara dike tre noder tillsammans, den första en, den sista, och en att du bara infogas i mitten. 

Och faktiskt en länkad lista, till skillnad från en array, är dynamisk. Den kan växa och det kan krympa och du inte måste veta eller vård i förväg hur mycket data du kommer att lagra, men det visar sig att vi måste vara lite försiktiga med hur att genomföra detta. Så låt oss först fundera över hur vi genomför en av dessa små rektanglar. Det är lätt att genomföra en int. Du säger bara int n och sedan du får 4 byte för en int, men hur får jag en int, kalla det n, och sedan en pekare, låt oss kalla det nästa. Vi skulle kunna kalla dessa saker vad vi vill men jag behöver en egen datastruktur. Yeah? 

PUBLIK: Ampersand [OHÖRBAR]. 

DAVID MALAN: Så ampersand vi använder för att få adressen för en nod potentiellt. Men vi behöver en annan funktion i C i syfte att ge mig möjlighet att skapa denna sed rektangel, denna sed variabel om ni så vill, i minnet. PUBLIK: En struct. DAVID MALAN: En struct. Minns från förra veckan införde vi struct, denna relativt enkla sökord som låter oss göra sånt här. C kom inte med en data struktur som kallas elev. Den levereras med int och float och röding och sådan, men det kommer inte med elev, men vi kan skapa en typ elev uppgifter, en student struktur, med denna syntax här. Och du kommer att se det här igen och igen. Så du behöver inte oroa dig memorera sökord, men det sökord som är viktigt är bara det faktum att vi sade struct och sedan vi kallade den studerande och inne av studenterna var ett namn och ett hus eller en student eller liknande. 

Och så nu idag, låt oss föreslå detta. Jag har lagt till några ord, men om jag vill att genomföra denna rektangel som är fick både en int och en pekare, vet du vad, jag är kommer att deklarera en struct som kallas nod. Jag är också, inne i det, kommer att säga att en nod, denna rektangel har en int och vi kallar det n och den har en nästa pekare. Och detta är lite mångordig, men om man tänker på det, pilarna som fanns i bilden en stund sedan är vad datatyp? Om var och en av dessa pilar pekar vilken typ av datastruktur? Det är inte pekar bara en int i sig. Det pekar på hela rektangulär sak och att rektangulära sak, vi sade, kallas en nod. Och så vi slags måste rekursivt definiera detta en sådan att en nod, ska vi säga, kommer att innehålla en int kallas n och en pekare som heter nästa och typ av datastruktur, till vilken att pekaren poäng är uppenbarligen kommer att bli struct nod. 

Så detta är irriterande mångordig och bara vara pedantisk, anledningen till att vi inte kan bara säga detta, som uppriktigt sagt ser mycket mer lättläst, beror återkallande att C läsa saker uppifrån och ned, från vänster till höger. Det är inte förrän vi får semikolon att sökordet noden faktiskt existerar. Så om vi vill ha denna typ av cyklisk referens insidan av uppgifter struktur, vi måste göra detta, där vi säger struct nod vid topp, som ger oss en längre sätt att beskriva detta sak, sedan inuti vi säger struct nod, och sedan i sista raden vi säger, okej, C, förresten, bara kalla hela denna jävla sak en nod och stoppa med hjälp av nyckelordet struct helt och hållet. Så det här är bara en slags syntaktisk trick som i slutändan låter oss skapa något som ser ut precis som detta. 

Så om vi antar nu att vi kan genomföra den här saken i C, hur gör vi faktiskt börja traversera denna? Tja, i själva verket är allt vi har att göra iterera från vänster till höger och bara typ av infoga noder eller ta bort noder eller söka efter saker var vi vill, men för att göra detta, låt oss gå vidare och göra saker lite mer verklig eftersom detta har varit super låg nivå hittills. Skulle någon bokstavligen vilja vara först? OK. Kom upp. Vad heter du? 

David: David. DAVID MALAN: David. Trevligt att träffas. Jag med. Okej. Och vi behöver ett nummer 9. Inte lika bra som första, kanske. OK, nummer 9. Ett antal 17, tack. Låt mig gå tillbaka lite längre. Number 22, snälla, och vad sägs om längre tillbaka Om jag kan se alla händer med allt det ljus eller ingen. Någon som frivilligt direkt. Vill du komma upp? Din underarm med kraft går upp. OK, 17. 22. 26 kommer ner. Skulle någon annan vilja forcefully-- Kom upp. En verklig volontär. 

Så mycket snabbt, om ni kunde ordna er precis som noderna på skärmen. Tack. Och du kommer att bli 26. Okej och snabba introduktioner. Så jag är David och du är också? David: David. DAVID MALAN: Och du är? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Utmärkt. Så dessa är våra volontärer för idag och gå vidare och flytta lite på det sättet, och bara gå vidare och hålla hålla dina siffror som du är eller din första tecknet och med vänster hand, gå vidare och bara genomföra dessa pilar, precis så att din vänstra hand är bokstavligen pekar på vad du ska peka på, och ge dig själv lite utrymme så att vi kan visuellt se dina armar faktiskt pekar, och du kan bara peka typ av på botten är bra. 

Så här har vi en länkad lista med en, två, tre, fyra, fem noder i början, och märker att vi har denna speciella pekaren i början som är nyckel eftersom vi måste hålla koll listan hela längden på något sätt. Dessa killar, även om de är kvar till höger, rygg mot rygg i minnet, de faktiskt kan vara var som helst i datorns minne. Så dessa killar kan vara står någonstans på scenen och det är bra, så länge de är faktiskt pekar på varandra, men att hålla saker ren och enkel, vi ska bara dra dem från vänster till höger som detta, men det kan finnas stora luckor i mellan dessa noder. 

Nu, om jag vill faktiskt sätta några nytt värde, låt oss gå vidare och göra det. Vi har en möjlighet nu att välja en annan nod. Säg låt oss börja med mallocing 55. Skulle någon emot att malloc? OK, kom upp. Vad heter du? RAINBOW: Rainbow. DAVID MALAN: Rainbow? Okej. Malloc Rainbow. Kom upp. Så nu måste vi fråga oss algoritm där vi kan sätta 55. Så vi alla vet, naturligtvis, där hon förmodligen hör om vi försöker att hålla denna sorteras och om ni kunde ta en ett steg tillbaka så att vi inte faller bort scenen, det skulle vara bra. Så egentligen, Rainbow, börja om här med mig, eftersom vi som datorn nu kan bara se en variabel i taget. Så om detta är den första noden. Lägg märke till att han inte är en nod, Han är bara en pekare, och det är därför han dras till vara bara storleken på en pekare, inte en av de fullständiga rektanglar. Så vi kommer att kontrollera vid varje iteration är 55 mindre än 9? Nej. Är 55 mindre än 17? Nej. Mindre än 22? Mindre än 26? Mindre än 34? Och så nu, självklart Rainbow hör i slutet. Så för att vara tydlig, och vad var ditt namn, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Så bland Taylors vänster hand och Rainbow händer här, vars hand måste peka på det som i För att sätta in 55 i listan? Vad behöver vi göra? Yeah? 

Publik: Taylors handen måste peka åt vänster. 

DAVID MALAN: Exakt. Så du sätter en nod i slutet av listan är ganska enkelt eftersom Taylor bara måste peka, i stället för på marken eller ska vi kalla det noll, null är typ av frånvaron av en pekare eller en speciell noll pekare, du är kommer att peka med vänster handen på Rainbow och sedan Rainbow, där ska din vänstra handen förmodligen peka? Ner. Det är inte bra om hennes hand är typ pekar ut här eller typ av någon vilken väg. Det skulle anses en soptunna värde, men om hon pekar på några kända värdet, vi ska kalla det noll eller noll, det är OK eftersom vi har en löptid på detta och vi vet att listan är klar. 

Så vad är en annan relativt enkelt fall? Kan vi malloc 5? Kom upp. Vad heter du? Tiffany: Tiffany. DAVID MALAN: Jag är ledsen? Tiffany: Tiffany. DAVID MALAN: Tiffany. Okej. Tiffany har malloced med värdet 5. Kom upp. Detta är relativt lätt också, men låt oss betrakta order av verksamheten nu. Det var ganska lätt med Taylor i slutet. Nummer 5 är naturligtvis mindre än 9, och så vi har David, vi har Tiffany, och vad var ditt namn? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, och David. Vars hand bör uppdateras först? Vad vill du göra här? Det finns ett par olika sätt, men det finns också en eller flera fel sätt. 

PUBLIK: Börja med längst till vänster. 

DAVID MALAN: Börja med längst till vänster. Vem är längst till vänster här då? PUBLIK: First. 

DAVID MALAN: OK. Så börja med först och där gör du vill uppdatera Davids händer att vara? PUBLIK: Mot 5. DAVID MALAN: OK. Så David, peka på fem eller Tiffany här och nu? 

PUBLIK: Tiffany pekar på 9? DAVID MALAN: Perfekt, utom Binky s chef bara typ av föll, eller hur? För vad är det för fel med den här bilden bokstavligen? PUBLIK: Ingenting pekar. DAVID MALAN: Ingenting är pekar på Jake nu. Vi har bokstavligen föräldralösa 9 och 17, och vi har bokstavligen läckt ut av detta minne, eftersom de genom uppdatering Davids hand först, det är bra eftersom den är korrekt pekar på Tiffany nu, men om ingen hade framsyntheten att peka på Jake, då vi har förlorat helheten av denna förteckning. Så låt oss ångra. Så det var en bra sak att snubbla över men låt oss korrigera nu. Vad ska vi göra först i stället? Yeah? 

PUBLIK: Tiffany bör peka på 9? DAVID MALAN: Jag kan inte få det nära dig. Vem ska peka på 9? 

PUBLIK: Tiffany. 

DAVID MALAN: Okej. Så Tiffany bör första punkten på 9. Så Tiffany bör ta på en identisk värde David, som verkar redundant för en stund, men det är bra för nu, andra steg, kan vi uppdatera David hand att peka på Tiffany, och sedan om vi bara typ av ren upp saker som om det är typ av vårlikt, nu som är en korrekt isättning. Så utmärkt. Så nu är vi nästan där. Låt oss sätta en slutlig värde som värdet 20. Om vi ​​kunde malloc en slutlig volontär? Kom upp. Så här är lite mer besvärlig. Men egentligen, koden är vi skrift, om än verbalt, är precis som att ha ett gäng av om förhållandena nu, eller hur? Vi hade en beskaffenhet kontrollera om det hör i slutet, kanske början. Vi behöver någon form av slinga för att hitta plats i mitten. Så låt oss göra det med vad heter du? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Trevligt att träffas. Så vi har 20. Mindre än fem? Nej. Mindre än nio? Nej. Mindre än 17? Nej. OK. Han hör hemma här och ditt namn igen är? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, och? ERIC: Eric. DAVID MALAN: Eric. Vars händer måste uppdateras först? 

PUBLIK: Eric. OK. Så Eric bör peka på där? Vid 22. God. Och nu vad händer nu? Sue kan peka på Eric och nu, om ni bara göra vissa rum, vilket är bra visuellt, nu har vi gjort insättningen. Så låt oss nu behandla ett ärende, men Tack så mycket för våra volontärer. Väldigt bra gjort. Du kan behålla dem, om du vill. Och vi har en härlig avskedsgåva om du skulle varje vilja ta en stressboll. Låt mig bara passera ner det. Så vad är takeaway av detta? Detta verkar vara fantastiskt mån vi har nu introducerade ett alternativ till en matris som inte är så begränsad till en matris av någon fast storlek. De kan växa dynamiskt. 

Men mycket som vi har sett i veckor förflutna, vi aldrig få något gratis, som säkerligen finns det en avvägning här. Så med en uppåtsidan av en länkad listan, är denna dynamik? Denna förmåga att växa och uppriktigt sagt, Vi kunde ha gjort delete och vi kunde krympa efter behov. Vilket pris betalar vi? Dubbelt så mycket utrymme, i första hand. Om du tittar på bilden, inte längre jag lagra en lista av heltal. Jag lagrar en lista över heltal plus pekare. Så jag fördubbla mängden utrymme. Nu kanske det är inte en sådan en big deal 4 bytes, 8 byte, men det kan säkert lägga för stora datamängder. Vad är en annan nackdel? Yeah? 

PUBLIK: Vi måste korsa dem en i taget. DAVID MALAN: Ja. Vi måste korsa dem en i taget. Vet du vad, vi gav upp denna super praktisk funktion av hakparentes notation, mer korrekt känd som random access, där vi bara kan hoppa till ett enskilt element men nu om jag fortfarande hade mina volontärer här, om jag ville hitta nummer 22, jag kan inte bara hoppa till konsolen något något. Jag måste se över listan, mycket som våra Söka exempel linjärt, att hitta numret 22. Så vi tycks ha betalat ett pris där. Men vi kan ändå lösa andra problem. 

I själva verket, låt mig presentera bara ett par bilder. Så om du har varit ner till Mathers Dining Hall nyligen, du ihåg att deras staplar av tråg som denna, vi lånat dessa från Annenberg innan klassen. Så här stapeln av brickor, dock, är representativ faktiskt av en datavetenskap datastruktur. Det finns en datastruktur i datavetenskap känd som en stapel som mycket snyggt lämpar sig för just denna visuella. Så om vart och ett av dessa fack är inte en fack men som ett nummer och jag ville att lagra siffror, jag skulle kunna sätta en här nere, och jag kunde sätta en annan här nere, och fortsätter att stapla siffror ovanpå varandra, och vad som är potentiellt användbart om detta är att det är underförstått av denna datastruktur? Vilka nummer kan jag dra ut först lämpligast? Den senast ett sätta på det. 

Så det här är vad vi skulle kalla in datavetenskap en LIFO datastruktur. Sist in, först ut. Och vi får se snart varför som kan vara användbara, men för nu, bara betrakta fastigheten. Och det är typ av dum om du tror om hur matsalen gör det. Varje gång de rena fack och sätta de färskaste som på toppen, du kan ha en tidigare ren men så småningom mycket smutsiga och dammiga fack längst ner om du aldrig faktiskt gå till botten av det stack, eftersom du bara hålla sätta nya och de rena ovanpå det. Samma sak kan hända i en stormarknad också. Om du har en monter av mjölk och varje gång CVS eller vem blir mer mjölk, du bara shove mjölk du redan har på baksidan och du sätter de nya framsidan, du kommer att ha några ganska otäck mjölk i slutet av datastrukturen, eftersom det alltid är i botten eller ekvivalent det är alltid längst bak. 

Men det finns ett annat sätt att tänka på rada upp data och till exempel, detta. Om du är en av dem som gillar att rada upp utanför Apples butiker när en ny produkt kommer ut, är du förmodligen inte använder en bunt uppgifter struktur eftersom du skulle stöta bort alla andra som är kö för att köpa några nya leksak. Snarare är du antagligen att använda vilken typ av datastruktur eller vilken typ av system i den verkliga världen? Förhoppningsvis är det en linje, eller mer korrekt eller mer brittisk-liknande, en kö. Och det visar sig en kö är också en datastruktur i datavetenskap, men en kö har en mycket annan egenskap. Det är inte LIFO. Sist in, först ut. Gud förbjude. Det är i stället FIFO. Först in först ut. Och det är en bra sak för rättvisa skull säkert när du foder upp super tidigt på morgonen. Om du får det första, du vill komma ut först också. 

Och så alla dessa uppgifter strukturer, köer och travar och klasar av andra, visar sig att du kan tänka på detta som bara en array. Detta är en array, kanske en fast storlek 4, men det skulle vara typ av trevligt om vi bara kunde stapla brickor nästan oändligt högt om vi ha så många brickor eller siffror. Så kanske vi vill använder en länkad lista här, men en kompromiss kommer att vara potentiellt att vi behöver mer minne, tar lite mer tid, men vi begränsar inte höjden på stapeln, ungefär som Mather: s monter kan begränsa storleken på stapeln, och så dessa är designbeslut eller alternativ för oss i slutändan. Så med dessa uppgifter strukturer, har vi börjat se nya övre gränser potentiellt på det som tidigare var supersnabb och där vi lämnar ledig idag och där vi hoppas att få är på onsdag, vi ska börja titta på en data struktur som låter oss söka genom uppgifter i logg sluttid igen. Och vi såg det, minns vecka noll och en med binär sökning eller dela och erövra. Det kommer tillbaka och ännu bättre, den heliga graal för denna onsdag kommer att vara att komma med datastruktur som löper riktigt eller teoretiskt i konstant tid, varigenom det spelar ingen roll hur många miljoner eller miljarder saker Vi har i datastrukturen, kommer det ta oss konstant tid, kanske ett steg eller två steg eller 10 steg, men konstant antal steg att söka igenom den datastruktur. Det verkligen kommer att vara den heliga graal men mer om det på onsdag. Se ya då. 

[MUSIK SPELA]