>> [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]