[Powered by Google Translate] [Recension] [Frågesport 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [Detta är CS50.] [CS50.TV]
>> Hej, alla.
Välkommen till översyn sessionen för Quiz 0, vilket sker på onsdag.
Vad vi ska göra ikväll, jag med 3 andra TF,
och tillsammans ska vi gå igenom en översyn av vad vi har gjort i kursen hittills.
Det kommer inte att vara 100% heltäckande, men det bör ge dig en bättre uppfattning
vad du redan har ner och vad du fortfarande behöver studera innan onsdag.
Och gärna upp handen med frågor som vi kommer tillsammans,
men tänk på att vi också kommer att ha lite tid i slutet,
om vi får igenom med några minuter till godo, för att göra allmänna frågor,
så håll detta i åtanke, och så ska vi börja från början med vecka 0.
>> [Quiz 0 recension!] [Del 0] [Lexi Ross] Men innan vi gör det ska vi prata om
logistiken för testet.
>> [Logistik] [Quiz sker på onsdag 10/10 i stället för föreläsning]
>> [(Se http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf för detaljer)] Det är på onsdag 10 OKTOBER.
>> Det är denna onsdag, och om du går till denna URL här,
som också nås från CS50.net-det finns en länk till den-
Du kan se information om vart man vänder sig utifrån
ditt efternamn eller skola tillhörighet samt
Det berättar om exakt vad testet kommer att täcka och vilka typer av frågor som du kommer att få.
Tänk på att du också kommer att ha en chans att granska för frågesporten i snitt,
så att dina TF bör gå över några praktiska problem,
och det är en annan bra chans att se var du fortfarande behöver studera upp för testet.
Låt oss börja från början med bitar 'n' byte.
Kom ihåg att en bit är bara en 0 eller en 1,
och ett byte är en samling av 8 av dessa bitar.
Låt oss titta på denna samling av bitar här.
Vi borde kunna räkna ut hur många bitar som finns.
Där vi räknar det finns bara 8 av dem, åtta 0 eller 1 enheter.
Och eftersom det finns 8 bitar, det är 1 byte,
och låt oss omvandla den till hexadecimalt.
Hexadecimal är basen 16, och det är ganska enkelt att konvertera
ett tal i binär, vilket är vad det är, till ett nummer i hexadecimalt.
Allt vi gör är att vi tittar på grupper av 4,
och vi konvertera dem till rätt hexadecimala siffran.
Vi börjar med längst till höger grupp 4, så 0011.
Det kommer att bli en 1 och en 2, så tillsammans som gör 3.
Och låt oss titta på det andra blocket av 4.
1101. Det kommer att bli en 1, en 4, och en 8.
Tillsammans som kommer att vara 13, vilket gör D
Och vi kommer ihåg att i hexadecimal vi inte bara gå 0 till 9.
Vi går 0 till F, så efter 9, 10 motsvarar en,
11 till B, et cetera där F är 15.
Här 13 är ett D,
så att omvandla det till decimal allt vi gör är att vi faktiskt
behandla varje position som en effekt av 2.
Det är en 1, en 2, noll 4S, noll 8s, en 16, et cetera,
och det är lite svårt att beräkna i huvudet, men om vi går till nästa bild
kan vi se svaret på den.
>> I huvudsak ska vi över från höger till vänster,
och vi multiplicera varje siffra med motsvarande makt 2.
Och kom ihåg, för hexadecimala vi beteckna dessa siffror med 0x i början
så vi blanda inte ihop det med ett decimaltal.
Fortsätter, är det en ASCII tabell,
och vad vi använder ASCII för är att kartlägga från tecken till numeriska värden.
Tänk på kryptografi pset vi gjort omfattande användning av ASCII tabellen
För att använda olika metoder för kryptografi,
Caesar och Vigenère chiffer, konvertera olika bokstäver
i en sträng enligt nyckeln ges av användaren.
Låt oss titta på lite ASCII matematik.
Titta på "P" + 1, karaktär form som skulle vara Q,
och kom ihåg att '5 '≠ 5.
Och hur exakt skulle vi konvertera mellan dessa 2 formerna?
Det är faktiskt inte så svårt.
För att få 5 vi subtrahera '0 '
eftersom det finns 5 platser mellan '0 'och 5. "
För att gå åt andra hållet vi bara lägga till 0,
så det är ungefär som vanligt aritmetik.
Kom bara ihåg att när något har citattecken runt det är det ett tecken
och således motsvarar ett värde i ASCII-tabellen.
Flytta till mer allmänna ämnen datavetenskap.
Vi lärde mig vad en algoritm är och hur vi använder programmering
att implementera algoritmer.
Några exempel på algoritmer är något riktigt enkelt som
kontrollera huruvida ett antal är jämnt eller udda.
För att minns vi mod antalet med 2 och kontrollera om resultatet är 0.
Om så är fallet, är det ännu. Om inte, är det konstigt.
Och det är ett exempel på en riktigt basic algoritm.
>> En liten bit av en mer engagerade en är binär sökning,
som vi ska gå över senare i recensionen sessionen.
Och programmering är den term vi använder för att ta en algoritm
och omvandla den till koda datorn kan läsa.
2 exempel på programmering är Scratch,
vilket är vad vi gjorde i vecka 0.
Även om vi inte egentligen skriver ut koden är det ett sätt att genomföra
denna algoritm, som skriver siffrorna 1-10,
och här gör vi samma sak i programmeringsspråket C.
Dessa är funktionellt likvärdig, just skrivit på olika språk eller syntax.
Vi lärde då om booleska uttryck,
och ett booleskt är ett värde som är antingen sant eller falskt,
och här ofta booleska uttryck
gå in villkor, så om (x ≤ 5),
bra, satte vi redan x = 5, så att villkoret kommer att utvärderas till sant.
Och om det är sant, är vad koden under villkoret
kommer att utvärderas av datorn, så att strängen ska skrivas
till standard ut, och termen tillstånd
hänvisar till vad som är inom parentes i if.
Tänk alla operatörer.
Kom ihåg att det är && och | | när vi försöker kombinera 2 eller fler villkor,
== Inte = att kontrollera om 2 saker är lika.
Kom ihåg att = är för tilldelning medan == är ett booleskt operatör.
≤, ≥ och sedan sista 2 är självförklarande.
En allmän översyn av boolesk logik här.
Och booleska uttryck är också viktiga i slingor,
som vi ska gå över nu.
Vi lärde oss om 3 typer av slingor hittills i CS50, för, medan och göra medan.
Och det är viktigt att veta att medan de flesta ändamål
Vi kan faktiskt använda någon typ av loop allmänhet
Det finns vissa typer av ändamål eller gemensamma mönster
i programmering som specifikt kräver en av dessa slingor
som gör den till den mest effektiva eller elegant att koda det på det sättet.
Låt oss gå igenom vad var och en av dessa slingor tenderar att användas för oftast.
>> I en for-slinga vi i allmänhet redan vet hur många gånger vi vill iterera.
Det är vad vi lägger i tillståndet.
För i = 0, i <10, till exempel.
Vi vet redan att vi vill göra något 10 gånger.
Nu, för en while-slinga, i allmänhet vi inte nödvändigtvis
vet hur många gånger vi vill att slingan ska köras.
Men vi vet något slags förutsättning att vi vill att det ska
alltid vara sant eller alltid vara falskt.
Exempelvis när inställd.
Låt oss säga att det är en boolesk variabel.
Även om det är sant att vi vill att koden för att utvärdera,
så lite mer töjbart lite mer generell än en for-slinga,
men någon för slingan kan också omvandlas till en while-slinga.
Slutligen göra medan slingor, som kan vara den svåraste att förstå direkt,
används ofta när vi vill utvärdera först koden
före första gången vi kontrollera tillståndet.
En vanlig användning för en göra medan slinga
är när du vill få indata, och du vet att du vill fråga användaren
för inmatning åtminstone en gång, men om de inte ger dig bra ingång direkt
du vill hålla ber dem tills de ger dig goda ingången.
Det är den vanligaste användningen av en gör while-slinga,
och låt oss titta på den konkreta utformningen av dessa slingor.
De oftast alltid tenderar att följa dessa mönster.
>> På for-slingan inuti du har 3 komponenter:
initiering, vanligtvis något som int i = 0 där i är räknaren,
tillstånd, där vi vill säga köra detta för slingan så länge detta tillstånd fortfarande innehar,
som jag <10, och slutligen, uppdatera, vilket är hur vi öka
räknarvariabeln vid varje punkt i slingan.
En vanlig sak att se det är bara jag + +,
vilket innebär öka i med 1 varje gång.
Du kan också göra något som jag + = 2,
vilket innebär tillsätt 2 till I varje gång du går genom öglan.
Och sedan göra detta bara avser varje kod som faktiskt körs som en del av slingan.
Och för en while-slinga, denna gång har vi faktiskt initieringen utanför slingan,
så till exempel, låt oss säga att vi försöker göra samma typ av loop som jag just beskrivit.
Vi skulle säga int i = 0 innan loopen börjar.
Då skulle vi kunna säga medan jag <10 gör detta,
så samma block av kod som tidigare,
och den här gången uppdateringen del av koden, till exempel i + +,
faktiskt går in i slingan.
Och slutligen, för en göra medan, är det liknar while-slingan,
men vi måste komma ihåg att koden kommer att utvärdera en gång
innan tillståndet kontrolleras, så det är mycket mer känsla
om man tittar på det i ordning uppifrån och ned.
I en göra medan slinga koden utvärderar innan du ens titta på medan du kondition,
medan en while-slinga, kontrollerar den först.
Uttalanden och variabler.
När vi vill skapa en ny variabel som vi vill först initiera den.
>> Till exempel initierar int bar den rörliga baren,
men det ger den ett värde, så vad är bar värde nu?
Vi vet inte.
Det kan vara något skräp värde som tidigare lagrats i minnet där,
och vi vill inte använda denna variabel
tills vi ger faktiskt ett värde,
så vi förklara den här.
Då vi initiera det är 42 nedan.
Nu, naturligtvis, vet vi att detta kan ske på en rad, int bar = 42.
Men bara att rensa flera steg som pågår,
deklarationen och initiering händer separat här.
Det händer på ett steg, och nästa, int Baz = bar + 1,
detta uttalande nedan, att steg Baz, så i slutet av denna kodblock
om vi skulle skriva ut värdet av baz skulle det vara 44
eftersom vi förklara och initiera att det 1> bar,
och då vi öka den igen med + +.
Vi gick över denna vackra kort, men det är bra att ha en allmän
förståelse för vad trådar och händelser är.
Vi gjorde främst detta i Scratch,
så du kan tänka på trådar som flera sekvenser av kod
körs samtidigt.
I själva verket är det förmodligen inte är igång samtidigt,
men typ av abstrakt kan vi tänka på det på det sättet.
>> I Scratch, till exempel, hade vi flera sprites.
Det skulle kunna exekvera annan kod på samma gång.
Man kan gå medan den andra säger något
i en annan del av skärmen.
Evenemang är ett annat sätt att separera ut logiken
mellan olika delar av din kod,
och i Scratch kunde vi simulera händelser med Broadcast,
och det är faktiskt när jag får, inte när jag hör,
men i huvudsak är det ett sätt att överföra information
från en sprite till en annan.
Till exempel kanske du vill sända game over,
och när en annan sprite får game over,
den svarar på ett visst sätt.
Det är en viktig modell för att förstå för programmering.
Bara att gå över den grundläggande Vecka 0, vad vi har gått över så långt,
låt oss titta på detta enkla C-program.
Texten kan vara lite små härifrån, men jag ska gå igenom det riktigt snabbt.
Vi inklusive 2 huvudfiler överst, cs50.h och stdio.h.
Vi sedan definiera en konstant kallad gräns till 100.
Vi sedan genomföra vår huvuduppgift.
Eftersom vi inte använder kommandoradsargument här vi måste sätta ogiltig
som argument för stora.
Vi ser int ovan huvud. Det är returtyp, därför återvänder 0 i botten.
Och vi använder CS50 biblioteksfunktion få int
att uppmana användaren för inmatning, och lagrar vi det i denna variabeln x,
så vi förklarar X ovan, och vi initiera den med x = getInt.
>> Vi kontrollerar sedan att se om användaren gav oss bra ingång.
Om det är ≥ begränsar vi vill returnera en felkod av 1 och skriva ut ett felmeddelande.
Och slutligen, om användaren har gett oss bra ingång
vi kommer att förena numret och skriva ut resultatet.
Bara för att se till att de alla hit hem
kan du se märken hos olika delar av koden här.
Jag nämnde konstant, header-filer.
Åh, int x. Se till att komma ihåg att det är en lokal variabel.
Som kontrasterar det från en global variabel som vi pratar om
lite senare i recensionen sessionen,
och vi kallar biblioteket funktionen printf,
så om vi inte hade inkluderat stdio.h sidhuvudfilen
Vi skulle inte kunna ringa printf.
Och jag tror pilen som fick avskurna här pekar på% d,
som är en formatering sträng i printf.
Det säger skriva ut denna variabel som ett tal,% d.
Och det är det för vecka 0.
Nu Lucas kommer att fortsätta.
Hej, grabbar. Mitt namn är Lucas.
Jag är en andraårsstuderande i bästa huset på campus, Mather,
och jag ska prata lite om vecka 1 och 2,1.
[Vecka 1 och 2,1!] [Lucas Freitas]
Som Lexi sa, när vi började översätta koden från Scratch till C
en av de saker som vi märkt är att du kan inte bara
skriv din kod och köra den med en grön flagga längre.
Egentligen måste du använda några steg för att göra din C-program
bli en körbar fil.
I grund och botten vad du gör när du skriver ett program är att
du översätter din idé till ett språk som en kompilator kan förstå,
så när du skriver ett program i C
vad du gör är faktiskt skriva något som din kompilator kommer att förstå,
och därefter kompilatorn kommer att omsätta denna kod
till något som datorn förstår.
>> Och saken är, är din dator faktiskt mycket dum.
Datorn kan bara förstå 0s och 1s,
så faktiskt i de första datorerna folk programmeras vanligtvis
med 0 och 1, men inte längre, tack och lov.
Vi behöver inte memorera sekvenserna för 0 och 1
för en for-slinga eller en while-slinga och så vidare.
Det är därför vi har en kompilator.
Vad en kompilator gör är det i grunden översätter C-kod,
i vårt fall, till ett språk som datorn förstår,
som är föremål kod och kompilatorn att vi använder
heter klang, så detta är verkligen en symbol för klang.
När du har ditt program, måste du göra 2 saker.
Först måste du kompilera ditt program, och då du kommer att köra ditt program.
För att kompilera ditt program har du många alternativ att göra det.
Den första är att göra klang program.c
i vilket program är namnet på ditt program.
I det här fallet kan du se de bara säger "Hej, kompilera mitt program."
Du säger inte "Jag vill ha det här namnet mitt program" eller något.
>> Det andra alternativet är att ge ett namn till ditt program.
Du kan säga klang-o och sedan namnet som du vill
den körbara filen som ska namnges som sedan program.c.
Och du kan också göra att program och se hur de första 2 fall
Jag satte. C, och i den tredje jag har bara program?
Ja, du faktiskt inte ska lägga. C. när du använder gör.
Annars kompilatorn faktiskt kommer att skrika på dig.
Och även jag vet inte om ni minns,
men många gånger vi använt-lcs50 eller-LM.
Det kallas länkning.
Den talar bara kompilatorn att du kommer att använda dessa bibliotek där,
så om du vill använda cs50.h du faktiskt skriva
klang program.c-lcs50.
Om du inte gör det, är kompilatorn kommer inte att veta
att du använder dessa funktioner i cs50.h.
Och när du vill köra ditt program har du 2 alternativ.
Om du gjorde klang program.c du inte namnge ditt program.
Du måste köra det med. / A.out.
A.out är en standard namn som klang ger ditt program om du inte ge den ett namn.
Annars du kommer att göra. / Program om du gav ett namn till ditt program,
och även om du gjorde programmet det namn som ett program kommer att få
redan kommer att programmeras med samma namn som C-fil.
Sen pratade vi om datatyper och data.
>> I grund och botten datatyper är samma sak som små lådor som de använder
att lagra värden, så datatyper är faktiskt precis som Pokemons.
De finns i alla storlekar och typer.
Jag vet inte om det analogi är vettigt.
Uppgifterna storlek beror faktiskt på maskinens arkitektur.
Alla data storlekar som jag kommer att visa här
är faktiskt för en 32-bitars maskin, vilket är fallet med vår apparat,
men om du faktiskt koda din Mac eller Windows också
förmodligen du kommer att ha en 64-bitars maskin,
så kom ihåg att data storlekar som jag kommer att visa här
är för 32-bitars maskin.
Den första som vi såg var en int,
vilket är ganska enkelt.
Du använder int för att lagra ett heltal.
Vi såg också karaktär, röding.
Om du vill använda en bokstav eller en liten symbol som du förmodligen kommer att använda en röding.
En kol har 1 byte, vilket innebär 8 bitar, som Lexi sa.
I grund och botten har vi en ASCII tabell som har 256
möjliga kombinationer av 0 och 1,
och sedan när du skriver en röding det kommer att översätta
det tecken som ingångarna ett nummer som du har i ASCII tabellen, som Lexi sa.
Vi har också flottören, som vi använder för att lagra decimaltal.
Om du vill välja 3,14, till exempel, kommer du att använda en flottör
eller en dubbel som har större precision.
En flottör har 4 byte.
En dubbel har 8 byte, så den enda skillnaden är precisionen.
Vi har också en lång som används för heltal,
och du kan se en 32-bitars maskin en int och en lång har samma storlek,
så det inte verkligen göra meningsfullt att använda en lång i en 32-bitars maskin.
>> Men om du använder en Mac och 64-bitars maskin, faktiskt en länge har storlek 8,
så det beror egentligen på arkitekturen.
För 32-bitars maskin det inte är vettigt att använda en lång verkligen.
Och därefter en lång lång, å andra sidan, har 8 byte,
så det är mycket bra om du vill ha en längre heltal.
Och slutligen har vi sträng, som egentligen är en char *,
vilket är en pekare till en char.
Det är väldigt lätt att tro att storleken på strängen kommer att vara som
antalet tecken som du har där,
men faktiskt char * själva
har storleken på en pekare till en kol, vilket är 4 byte.
Storleken på en char * är 4 byte.
Det spelar ingen roll om du har ett litet ord eller en bokstav eller något.
Det kommer att bli 4 byte.
Vi lärde oss också lite om gjutning,
så du kan se om du har till exempel ett program som säger
int x = 3 och sedan printf ("% d", x / 2)
Vet ni vad det kommer att skrivas ut på skärmen?
>> Någon? >> [Studenter] 2.
1. >> 1, ja.
När du gör 3/2 att det kommer att bli 1,5,
men eftersom vi använder ett heltal det kommer att ignorera decimal delen,
och du kommer att ha 1.
Om du inte vill att det ska hända vad du kan göra, till exempel,
är förklara en flottör y = x.
Då x som brukade vara 3 kommer nu att bli 3,000 i y..
Och sedan kan du skriva y / 2.
Egentligen borde jag ha en 2. borta.
Det kommer att göra 3.00/2.00,
och du kommer att få 1,5.
Och vi har den här .2 f bara för att be om 2 decimaler enheter i decimaldelen.
Om du har 0,3 f det kommer att faktiskt har 1,500.
Om det är 2 kommer det att bli 1,50.
Vi har också det här fallet här.
Om du gör float x = 3,14 och sedan printf X
du kommer att få 3,14.
Och om du gör x = int av x,
vilket innebär behandla x som en int och du skriver ut X nu
du kommer att ha 3,00.
Verkar det vettigt?
Eftersom du först behandla x som ett heltal, så att du ignorerar decimaldelen,
och då du skriver x.
Och slutligen, kan du också göra detta,
int x = 65, och sedan du deklarerar en char c = x,
och sedan om du skriver ut c du faktiskt kommer att få
A, så i princip vad du gör här
är att översätta heltal i karaktären,
precis som ASCII tabellen gör.
Vi pratade också om matematiska operatörer.
De flesta av dem är ganska enkel, så +, -, *, /,
och även vi pratade om mod, som är resten av en division av 2 siffror.
Om du har 10% 3, till exempel,
det betyder dela 10 med 3, och vad är resten?
Det kommer att vara 1, så det är faktiskt mycket användbar för många av programmen.
För Vigenère och Caesar är jag ganska säker på att alla ni använt mod.
Om Math operatörer, vara mycket försiktig när du kombinerar * och /.
>> Till exempel, om du gör (3/2) * 2 vad ska du bli?
[Studenter] 2.
Ja, 2, beror 3/2 kommer att vara 1,5,
men eftersom du gör verksamheten mellan 2 heltal
du faktiskt bara att överväga 1,
och sedan 1 * 2 kommer att bli 2, så mycket, mycket försiktig
när man gör aritmetiska med heltal eftersom
du kan få att 2 = 3, i så fall.
Och också vara mycket försiktig företräde.
Du bör vanligtvis använda parenteser för att vara säker på att du vet vad du gör.
Några användbara genvägar, naturligtvis, är en i + + eller i + = 1
eller med + =.
Det är samma sak som att göra i = i + 1.
Du kan också göra i - eller i - = 1,
vilket är samma sak som i = i -1,
något ni använder mycket i för slingor, åtminstone.
Även för * om du använder * = och om du gör, till exempel,
i * = 2 är samma sak som att säga i = I * 2,
och samma sak för division.
Om du gör jag / = 2 är det samma sak som i = i / 2.
>> Nu om funktioner.
Ni fick veta att funktioner är en mycket bra strategi för att spara kod
medan du programmerar, så om du vill utföra samma uppgift
i kod och om igen, förmodligen du vill använda en funktion
bara så du behöver inte kopiera och klistra in koden om och om igen.
Egentligen är främsta funktion, och när jag visar dig formatet för en funktion
du kommer att se att det är ganska uppenbart.
Vi använder också funktioner från vissa bibliotek,
exempelvis printf, GetIn, vilket är från CS50 biblioteket,
och andra funktioner som toupper.
Alla dessa funktioner faktiskt implementeras i andra bibliotek,
och när du sätter dem begränsningsremmar filer i början av ditt program
du säger kan du ge mig koden för dessa funktioner
så jag behöver inte genomföra dem själv?
Och du kan också skriva egna funktioner, så när du börja programmera
du inser att biblioteken inte har alla de funktioner som du behöver.
För den sista pset, till exempel, skrev vi drar, scramble och lookup,
och det är mycket, mycket viktigt att kunna skriva funktioner
eftersom de är användbara, och vi använder dem hela tiden i programmering,
och det sparar mycket kod.
Formatet för en funktion är här.
Vi har returtyp i början. Vad är returtyp?
Det är bara när funktionen kommer att återvända.
Om du har en funktion, till exempel, faktoriella,
som kommer att beräkna en fakulteten av ett heltal,
förmodligen kommer att återvända ett heltal också.
Sedan returtyp kommer att vara int.
Printf faktiskt har ett tomrum returtyp
eftersom du inte returnera någonting.
Du är bara skriva saker på skärmen
och avsluta funktionen efteråt.
Då har du namnet på den funktion som du kan välja.
Du bör vara lite rimligt, liksom inte välja ett namn som xyz
eller liknande x2f.
Försök att göra upp ett namn som är vettigt.
>> Till exempel, om det är faktoriell, säger fakulteten.
Om det är en funktion som kommer att rita något, namnge den dra.
Och sedan har vi de parametrar, som också kallas argument,
som är som de resurser som din funktion behöver
från din kod för att utföra sitt uppdrag.
Om du vill beräkna fakulteten av ett antal
förmodligen måste du ha ett nummer för att beräkna en faktoriell.
Ett av de argument som du kommer att ha är numret själv.
Och då det kommer att göra något och returnera värdet vid slutet
om det inte är ett tomrum funktion.
Låt oss se ett exempel.
Om jag vill skriva en funktion som summerar alla nummer i en array av heltal,
först och främst är returtyp kommer att vara int
eftersom jag har en mängd av heltal.
Och då ska jag ha funktionen namn som sumArray,
och då det kommer att ta arrayen själv, int nums,
och sedan längden på arrayen så jag vet hur många nummer jag summera.
Då måste jag initiera en variabel som heter summa, till exempel till 0,
och varje gång jag ser ett element i arrayen jag lägga till summan, så jag gjorde en for-slinga.
Precis som Lexi sa, du int i = 0, i <längd och i + +.
Och för varje element i arrayen jag summa + = nums [i],
och sedan jag återvände summan, så det är väldigt enkelt, och det sparar mycket kod
om du använder denna funktion många gånger.
Sedan tog vi en titt på förhållanden.
Vi har om annat, och annan om.
Låt oss se vad är skillnaden mellan dem.
Ta en titt på dessa 2 koder. Vad är skillnaden mellan dem?
Den första har i stort sett endast koderna vill att du ska berätta
Om ett nummer är +, - eller 0.
Den första säger att om det är> 0 så är det positivt.
Om det är = till 0 så är det 0, och om det är <0 så är det negativt.
>> Och den andra är att göra om, annars om, annars.
Skillnaden mellan de två är att detta faktiskt kommer att
kontrollera om> 0, <0 eller = 0 tre gånger,
så om du har numret 2, till exempel, kommer det att komma hit och säga
if (x> 0), och det kommer att säga ja, så jag skriver ut positivt.
Men även om jag vet att det är> 0 och det kommer inte att bli 0 eller <0
Jag fortfarande tänker göra det 0, det är <0,
så jag faktiskt kommer in för IFS att jag inte behövde
eftersom jag redan vet att det inte kommer att tillfredsställa något av dessa villkor.
Jag kan använda om else if, else.
Det säger i princip om x = 0 jag skriver ut det positiva.
Om det inte, jag ska också testa detta.
Om det är 2 inte jag kommer att göra detta.
I grund och botten om jag hade x = 2 du skulle säga
if (x> 0), ja, så skriv ut.
Nu när jag vet att det är> 0 och att den uppfyllt det första om
Jag är inte ens kommer att köra denna kod.
Koden körs snabbare, faktiskt, 3 gånger snabbare om du använder det.
Vi lärde också om och och eller.
Jag tänker inte gå igenom detta eftersom Lexi redan pratat om dem.
Det är bara de && och | | operatör.
>> Det enda jag säger är att vara försiktig när du har 3 villkor.
Använd parenteser eftersom det är mycket förvirrande när du har ett tillstånd
och en annan eller en annan.
Använd parenteser bara för att vara säker på att dina villkor vettigt
eftersom i det fallet till exempel, kan du tänka dig att
det kan vara det första villkoret och den ena eller den andra
eller 2 villkor kombineras i en och
eller den tredje, så bara vara försiktig.
Och slutligen, talade vi om växlar.
En switch är mycket användbart när du har en variabel.
Låt oss säga att du har en variabel som n
som kan vara 0, 1, eller 2, och för varje av dessa fall
du kommer att utföra en uppgift.
Du kan säga byta variabeln, och det tyder på att
Värdet är då som värde1 jag ska göra detta,
och då jag sönder, vilket innebär att jag inte kommer att titta på någon av de andra fallen
eftersom vi nöjda redan det fallet
och sedan värde2 och så vidare, och jag kan också ha en standard brytare.
Det innebär att om det inte uppfyller något av de fall som jag hade
att jag ska göra något annat, men det är valfritt.
Det var allt för mig. Nu ska vi ha Tommy.
Okej, detta kommer att bli vecka 3-ish.
Dessa är några av de ämnen som vi kommer att täcker, crypto, omfattning, matriser, et cetera.
Bara en snabb ord om krypto. Vi kommer inte att hamra detta hem.
>> Vi gjorde detta i pset 2, men för testet att du vet skillnaden
mellan Caesar chiffer och Vigenère chiffer,
hur båda dessa chiffer arbete och hur det är att kryptera
och dekryptera text med dessa 2 chiffer.
Kom ihåg roterar Caesar chiffer helt enkelt varje tecken med samma belopp,
vilket gör att du mod med antalet bokstäver i alfabetet.
Och Vigenère chiffret, å andra sidan, roterar varje tecken
med ett annat belopp, så istället för att säga
Varje tecken roteras 3 Vigenère kommer att rotera varje tecken
med ett annat belopp beror på några sökord
där varje bokstav i sökordet representerar några olika belopp
att rotera klartext genom.
Låt oss först tala om varierande omfattning.
Det finns 2 olika typer av variabler.
Vi har lokala variabler, och dessa kommer att definieras
utanför huvud-eller utanför någon funktion eller block,
och dessa kommer att vara tillgänglig var som helst i ditt program.
Om du har en funktion och den funktionen är en while-slinga
den stora globala variabeln är tillgänglig överallt.
En lokal variabel, å andra sidan, är scoped till den plats där den är definierad.
>> Om du har en funktion här, till exempel, har vi denna funktion g
och insidan av g finns en variabel här kallad y,
och det betyder att det är en lokal variabel.
Även om denna variabel kallas y
och denna variabel kallas y dessa 2 funktioner
har ingen aning om vad varandras lokala variabler.
Å andra sidan, här uppe säger vi int x = 5,
och detta är utanför någon funktion.
Det är utanför viktigaste, så detta är en global variabel.
Det innebär att insidan av dessa 2 funktioner när jag säger x - eller x + +
Jag åtkomst samma x varvid denna y och denna y är olika variabler.
Det är skillnaden mellan en global variabel och en lokal variabel.
När det gäller utformningen är berörda, ibland är det nog en bättre idé
att hålla variabler lokal när du möjligen kan
sedan med ett gäng globala variabler kan bli riktigt förvirrande.
Om du har ett gäng funktioner alla modifiera samma sak
du kan glömma vad om funktionen av misstag ändrar denna globala,
och denna andra funktion inte vet om det,
och det blir ganska förvirrande när du får mer kod.
Hålla variabler lokal när du möjligen kan
är bara bra design.
Arrays, kom ihåg, är helt enkelt listor av element av samma typ.
Inne i CI kan inte ha en lista som 1, 2,0, hej.
Vi kan bara inte göra det.
>> När vi förklarar en array i C alla element måste vara av samma typ.
Här har jag en rad 3 heltal.
Här har jag längden på arrayen, men om jag bara förklara det i denna syntax
där jag ange vilka alla element är jag inte tekniskt behöver detta 3.
Kompilatorn är smart nog att räkna ut hur stor matrisen ska vara.
Nu när jag vill hämta eller ange värdet för en matris
Detta är syntaxen att göra det.
Detta kommer faktiskt att ändra det andra element i arrayen eftersom, kom ihåg,
numreringen börjar vid 0, inte 1.
Om jag vill läsa det värdet kan jag säga något i stil med int x = array [1].
Eller om jag vill ställa in det värde, som jag gör här,
Jag kan säga array [1] = 4.
Den tiden tillgång element av deras index
eller sin ställning eller om de är i arrayen,
och att noteringen inleds på 0.
Vi kan också ha arrayer av arrayer,
och detta kallas en flerdimensionell matris.
När vi har en flerdimensionell array
det innebär att vi kan ha något som rader och kolumner,
och detta är bara ett sätt att visualisera detta eller tänker på det.
När jag har en flerdimensionell array som innebär att jag tänker börja behöver
mer än 1 index eftersom om jag har ett rutnät
bara säga vad rad du är i ger oss inte ett nummer.
Det är verkligen bara kommer att ge oss en lista med tal.
Låt oss säga att jag har denna matris här.
Jag har en array med namnet nätet, och jag säger det är 2 rader och 3 kolumner,
och så detta är ett sätt att visualisera det.
När jag säger att jag vill få elementet vid [1] [2]
det betyder att eftersom dessa är rader först och sedan kolumner
Jag ska hoppa till rad 1 eftersom jag sa 1.
>> Sen ska jag komma hit till kolumn 2, och jag kommer att få värdet 6.
Vettigt?
Flerdimensionella arrayer, kom ihåg, är tekniskt bara en rad matriser.
Vi kan ha arrayer av arrayer av arrayer.
Vi kan fortsätta, men egentligen ett sätt att tänka
hur detta läggs ut och vad som händer är att visualisera det
i ett rutnät som denna.
När vi passerar arrayer till funktioner, kommer de att bete sig
lite annorlunda än när vi passerar regelbundet variabler till funktioner
som passerar en int eller en flottör.
När vi passerar i en int eller char eller något av dessa andra datatyper
Vi tog bara en titt på om funktionen ändrar
värdet på den variabeln att förändring inte kommer att propagera upp
till den anropande funktionen.
Med en matris, på den andra sidan kommer att hända.
Om jag passerar i en matris till någon funktion och att funktionen ändrar några av elementen,
när jag kommer tillbaka till den funktion som kallade det
min grupp kommer nu att vara annorlunda, och ordförråd för att
är arrayer passeras genom hänvisning som vi kommer att se senare.
Detta är relaterat till hur pekare arbete, där dessa grundläggande datatyper,
å andra sidan, är förbi värde.
>> Vi kan tänka oss det som att göra en kopia av något variabel och sedan passerar i kopian.
Det spelar ingen roll vad vi gör med den variabeln.
Anropsfunktionen kommer inte att vara medvetna om att det har ändrats.
Arrayer är bara lite annorlunda i detta avseende.
Till exempel, som vi just sett, är huvudsakliga helt enkelt en funktion
som kan ta i 2 argument.
Det första argumentet till huvudsakliga funktion är argc eller antal argument,
och det andra argumentet kallas argv,
och de är de verkliga värdena för dessa argument.
Låt oss säga att jag har ett program som heter this.c,
och jag säger att detta, och jag kommer att köra detta på kommandoraden.
Nu passerar i vissa argument för mitt program kallade detta,
Jag skulle kunna säga något i stil med. / Det är CS 50.
Detta är vad vi föreställer David för att göra varje dag vid terminalen.
Men nu huvudfunktion insidan av programmet
har dessa värden, så argc är 4.
Det kan vara lite förvirrande eftersom egentligen vi bara passerar i är CS 50.
Det är bara 3.
Men kom ihåg att den första delen av argv eller det första argumentet
är namnet på själva funktionen.
Så det innebär att vi har 4 saker här,
och det första elementet kommer att bli. / det.
Och detta kommer att representeras som en sträng.
Sedan de återstående elementen är vad vi skrev i efter namnet på programmet.
Så precis som en sidoreplik, som vi förmodligen såg i pset 2,
kom ihåg att strängen 50 är ≠ heltalet 50.
Så vi kan inte säga något i stil med 'int x = argv 3. "
>> Det bara inte kommer att vara meningsfullt, eftersom detta är en sträng, och detta är ett heltal.
Så om du vill konvertera mellan 2, kom ihåg, vi ska
har denna magiska funktion som kallas Atoi.
Det tar en sträng och returnerar heltalet representerade inuti den strängen.
Så det är ett enkelt misstag att göra på frågesport,
bara tänka att detta automatiskt blir rätt typ.
Men bara vet att de alltid kommer att vara strängar
även om strängen innehåller endast ett heltal eller ett tecken eller en flottör.
Så nu ska vi prata om körtid.
När vi har alla dessa algoritmer som gör alla dessa galna saker,
blir det verkligen bra att ställa frågan: "Hur länge de tar?"
Vi representerar det med något som kallas asymptotisk notation.
Så detta innebär att - ja, låt oss säga att vi ger vår algoritm
några riktigt, riktigt, riktigt stora ingång.
Vi vill ställa frågan, "Hur länge kommer det att ta?
Hur många steg tar det vår algoritm för att köra
som en funktion av storleken av insignalen? "
Så den första sättet vi kan beskriva drifttid är med stor O.
Och detta är vår värsta gångtid.
Så om vi vill sortera en array, och vi ger vår algoritm en matris
Det är i fallande ordning när det borde vara i stigande ordning,
det kommer att bli det värsta fallet.
Detta är vår övre gräns i den maximala tid vår algoritm kommer att ta.
Å andra sidan är denna Ω kommer att beskriva bästa fall gångtid.
Så om vi ger en redan sorterade arrayen till en sortering algoritm,
Hur lång tid tar det att sortera det?
Och detta då beskriver en nedre gräns på gångtid.
Så här är bara några ord som beskriver några vanliga gångtider.
Dessa är i stigande ordning.
Den snabbaste gångtid har vi kallas konstant.
>> Det innebär oavsett hur många element som vi ger vår algoritm,
oavsett hur stor vår array är, sortering
eller göra vad vi gör på arrayen kommer alltid ta lika lång tid.
Så vi kan representera att bara med en 1, vilket är en konstant.
Vi har också tittat på logaritmisk körning.
Så något liknande binär sökning är logaritmisk,
där vi skär problemet i halv varje gång
och sedan saker får bara högre därifrån.
Och om du någonsin skriver en O någon fakulteten algoritm,
du antagligen inte bör överväga detta som ditt vanliga jobb.
När vi jämför gångtider är det viktigt att komma ihåg dessa saker.
Så om jag har en algoritm som är O (n), och någon annan
har en algoritm av O (2n) dessa är faktiskt asymptotiskt ekvivalenta.
Så om vi föreställer n att vara ett stort antal som eleventy miljarder:
så när vi jämför eleventy miljarder till något liknande eleventy miljarder + 3,
plötsligt att tre inte gör verkligen en stor skillnad längre.
Det är därför vi ska börja överväga dessa saker vara likvärdiga.
Så saker som dessa konstanter här, det finns 2 x detta, eller lägga till en 3,
dessa är bara konstanter, och dessa kommer att falla upp.
Så det är därför alla 3 av dessa kör tider är detsamma som att säga att de är O (n).
Likaså om vi har 2 andra körtider, låt oss säga O (n ³ + 2n ²), kan vi lägga
+ N, + 7, och sedan har vi en annan körning det är bara O (n ³).
Återigen, detta är samma sak eftersom dessa - det är inte samma sak.
Det är samma saker, tyvärr. Så dessa är samma eftersom
Detta N ^ kommer att dominera denna 2n ².
>> Vad är inte samma sak är om vi har kört tider som O (n ³) och O (n ²)
eftersom detta N ^ är mycket större än den här N ^.
Så om vi har exponenter, plötsligt detta börjar roll,
men när vi bara göra med faktorer som vi är här uppe,
då det inte kommer spela någon roll eftersom de bara kommer att falla ut.
Låt oss ta en titt på några av de algoritmer vi har sett hittills
och tala om sin körning.
Det första sättet att leta efter ett nummer i en lista, som vi såg, var linjär sökning.
Och genomförandet av linjär sökning är super enkelt.
Vi har bara en lista, och vi kommer att titta på varje enskilt element i listan
tills vi hittar numret vi letar efter.
Så det betyder att i värsta fall, denna O (n).
Och det värsta fallet här skulle vara om elementet är
det sista elementet, sedan använda linjär sökning vi måste titta på varje enskilt element
tills vi kommer till den sista för att veta att det var faktiskt i listan.
Vi kan inte bara ge upp halvvägs och säger: "Det är nog inte där."
Med linjär sökning måste vi titta på det hela.
Bästa fall gångtid, å andra sidan, är konstant
eftersom det i bästa fall elementet vi letar efter är bara den första i listan.
Så det kommer att ta oss exakt 1 steg, oavsett hur stor listan är
Om vi ​​letar efter det första elementet varje gång.
>> Så när du söker, kom ihåg, behöver den inte att vår lista ska sorteras.
Eftersom vi bara kommer att se över varenda del, och det spelar egentligen ingen roll
vilken ordning dessa delar är i.
En mer intelligent sökalgoritm är något som binär sökning.
Kom ihåg att genomförandet av binär sökning när du ska
hålla ser i mitten av listan.
Och eftersom vi tittar på mitten, kräver vi att listan är sorterad
annars vet vi inte var mitten är, och vi måste se över
hela listan för att hitta den och sedan på den punkten vi bara slösar bort tid.
Så om vi har en sorterad lista och vi hitta mitten, kommer vi att jämföra i mitten
till elementet som vi letar efter.
Om det är för högt, då kan vi glömma den högra halvan
eftersom vi vet att om vi element är redan för hög
och allt till höger om detta element är ännu högre,
vi behöver inte leta där längre.
När å andra sidan, om vi element är för låg,
Vi vet allt till vänster om denna beståndsdel är också för låg,
så det inte verkligen göra meningsfullt att titta där heller.
På detta sätt, med varje steg och varje gång vi tittar på mittpunkten av listan,
vi kommer att minska vår problem i halv eftersom vi plötsligt känner
en hel massa siffror som inte kan den vi letar efter.
>> I pseudokod skulle se ut ungefär så här,
och eftersom vi skär listan i halv varenda gång,
våra värsta fall körtid hoppar från linjär till logaritmisk.
Så plötsligt har vi logga in steg för att finna ett element i en lista.
Det bästa fall gångtid är dock fortfarande konstant
för nu, låt oss bara säga att elementet vi letar efter är
alltid exakt mitten av ursprungliga listan.
Så vi kan växa vår lista så stor som vi vill, men om elementet vi letar efter är i mitten,
då är det bara att ta oss 1 steg.
Så det är därför vi är O (log n) och Ω (1) eller konstant.
Låt oss verkligen köra binär sökning på denna lista.
Så låt oss säga att vi letar efter elementet 164.
Det första vi ska göra är att hitta mittpunkten av denna lista.
Det råkar vara så att mittpunkten kommer att falla mellan dessa 2 siffror,
så låt oss bara godtyckligt säga varje gång mittpunkten ligger mellan 2 tal,
Låt oss bara runda upp.
Vi behöver bara se till att vi gör detta varje steg på vägen.
Så vi kommer att runda upp, och vi kommer att säga att 161 är i mitten av vår lista.
Så 161 <164, och varje element till vänster om 161
är också <164, så vi vet att det inte kommer att hjälpa oss på alla
att börja leta på här eftersom elementet vi letar efter kan inte vara där.
Så vad vi kan göra är att vi bara kan glömma att hela vänstra halvan av listan,
och nu bara tänka på rätt 161 och framåt.
>> Så återigen, detta är mittpunkten, låt oss bara runda upp.
Nu 175 är för stort.
Så vi vet att det inte kommer att hjälpa oss ser här eller här,
så att vi kan bara kasta bort det, och så småningom kommer vi träffa 164.
Eventuella frågor om binärsökning?
Låt oss gå vidare från att söka igenom en redan sorterad lista
att faktiskt ta en lista med tal i valfri ordning
och göra denna förteckning i stigande ordning.
Den första algoritmen som vi tittat på hette bubbla sortera.
Och detta skulle vara enklare om de algoritmer vi såg.
Bubble Sortera säger att när någon 2 element inuti listan är på sin plats,
vilket innebär att det finns ett högre antal till vänster om ett lägre antal,
då ska vi byta dem, eftersom det innebär att listan blir
"Mer sorteras" än det var innan.
Och vi ska bara fortsätta denna process igen och igen och igen
tills slutligen elementen typ av bubbla till rätt plats och vi har en sorterad lista.
>> Körtiden för denna kommer att vara O (n ²). Varför?
Jo, för i värsta fall kommer vi att ta varje element, och
vi kommer att hamna jämföra det med alla andra element i listan.
Men i bästa fall har vi en redan sorterad lista, bubbla sortera är
bara att gå igenom en gång, säger "Nej. Jag gjorde några byten, så jag är klar."
Så vi har en bästa fall gångtid Ω (n).
Låt oss köra bubbla sortera på en lista.
Eller första, låt oss bara titta på några pseudokod verkligen snabbt.
Vi vill säga att vi vill hålla reda på, i varje iteration av slingan,
hålla reda på huruvida vi ändrat några element.
Så anledningen till detta är, vi kommer att sluta när vi inte har bytt några element.
Så i början av vår slinga har vi inte bytt någonting, så vi ska säga att det är falskt.
Nu ska vi gå igenom listan och jämföra inslag i till elementet i + 1
och om det är så att det finns ett större antal till vänster om ett mindre antal,
då vi ska bara byta dem.
>> Och då ska vi komma ihåg att vi bytte ett element.
Det betyder att vi måste gå igenom listan minst 1 gång
eftersom villkoret som vi slutade är när hela listan är redan sorterad,
vilket innebär att vi inte har gjort några swappar.
Så det är därför vårt tillstånd här nere är "samtidigt som vissa delar har bytts."
Så nu ska vi bara titta på detta körs på en lista.
Jag har en lista 5,0,1,6,4.
Bubble Sortera kommer att börja hela vägen till vänster, och det kommer att jämföra
The I elementen, så 0 till i + 1, vilket är elementet 1.
Det kommer att säga, väl 5> 0, men just nu 5 är till vänster,
så jag måste byta 5 och 0.
När jag byta dem, plötsligt får jag denna annorlunda lista.
Nu 5> 1, så vi kommer att byta dem.
5 är inte> 6, så vi behöver inte göra någonting här.
Men 6> 4, så vi måste byta.
Återigen måste vi gå igenom hela listan så småningom upptäcka
att dessa är i ordning, vi byter dem,
och på denna punkt måste vi gå igenom listan 1 gång
att se till att allt är i sin ordning, och på denna punkt bubbla typ är klar.
En annan algoritm för att ta några element och sortera dem är val Sortera.
Tanken bakom val Sortera är att vi ska bygga upp en sorterad del av listan
1 element vid en tidpunkt.
>> Och hur vi ska göra det är genom att bygga upp den vänstra segmentet i listan.
Och i princip varje - på varje steg, vi kommer att ta det minsta elementet vi har kvar
som inte har sorterats ännu, och vi kommer att flytta den till den sorterade segmentet.
Det innebär att vi måste hela tiden hitta den minsta osorterade elementet
och sedan ta det minsta elementet och byta den med vad
vänstra delen som inte är sorterad.
Den kör tid detta kommer att bli O (n ²) eftersom det i värsta fall
vi behöver jämföra varje enskilt element till varje annat element.
Eftersom vi säger att om vi startar på den vänstra halvan av listan, behöver vi
att gå igenom hela högra segmentet att hitta det minsta elementet.
Och sedan återigen måste vi gå över hela högra segmentet och
fortsätta över den om och om och om igen.
Det kommer att vara n ². Vi kommer att behöva en for-slinga inuti en annan för slinga
vilket tyder N ^.
I bästa fall tanken, låt oss säga att vi ger det en redan sorterad lista;
vi faktiskt inte gör något bättre än n ².
Eftersom val sortera har inget sätt att veta att
den minsta delen är bara en jag råkar vara att titta på.
Det behöver fortfarande se till att detta faktiskt är ett minimum.
>> Och det enda sättet att se till att det är minst använda denna algoritm,
är att titta på varje enskilt element igen.
Så egentligen, om du ger det - om du ger val Sortera en redan sorterad lista,
det kommer inte att göra något bättre än att ge det en lista som inte är sorterad ännu.
Förresten, om det råkar vara så att något är O (något)
och omega av något, kan vi bara säga mer koncist att det är θ något.
Så om du ser att komma någonstans, det är vad som just betyder.
>> Om något är theta n ², är det både stora O (n ²) och Ω (n ²).
Så bästa fall och värsta fall gör det inte någon skillnad,
algoritmen kommer att göra samma sak varje gång.
Så detta är vad pseudokod för val Sortera skulle kunna se ut.
Vi i grund och botten kommer att säga att jag vill att iterera över listan
från vänster till höger, och vid varje iteration av slingan, jag ska flytta
minsta elementet i detta sorteras delen av listan.
Och när jag flyttar något där, jag behöver aldrig titta på det elementet igen.
Eftersom så fort jag byter en del i den vänstra segmentet av listan, det sorteras
eftersom vi gör allt i stigande ordning med hjälp av minimum.
Så vi sa okej, vi är i position i, och vi måste titta på alla element
till höger om jag för att finna den minsta.
Så det betyder att vi vill titta på i + 1 till slutet av listan.
Och nu, om elementet som vi för närvarande tittar på är mindre än vår lägsta hittills,
som kom ihåg, vi börjar den minsta av att bara vara
oavsett elementet vi närvarande, jag antar att det är det minsta.
Om jag hittar ett element som är mindre än det, då kommer jag att säga, okej,
Jo, jag har hittat en ny minimum.
Jag ska komma ihåg var den lägsta var.
>> Så nu, när jag har gått igenom denna rätt osorterat segmentet,
Jag kan säga att jag kommer att byta den minsta elementet med element som är på plats i.
Det kommer att bygga upp min lista, min sorterade delen av listan från vänster till höger,
och vi inte någonsin behöver titta på ett element igen när det är i denna del.
När vi har bytt det.
Så låt oss köra val Sortera på denna lista.
Den blå delen här kommer att bli jag, och den röda delen kommer att vara det minsta elementet.
Så jag börjar helt till vänster i listan, så vid 5.
Nu måste vi hitta minsta osorterade elementet.
Så vi säger 0 <5, så 0 är min nya miniminivån.
>> Men jag kan inte stanna där, för även om vi kan erkänna att 0 är den minsta,
vi behöver gå igenom alla andra element i listan för att se.
Så 1 är större, är 6 större, är 4 större.
Det innebär att när du tittar på alla dessa element har jag fastställt 0 är den minsta.
Så jag kommer att byta 5 och 0.
När jag byter det, jag kommer att få en ny lista, och jag vet att jag aldrig behöver titta på det 0 igen
eftersom när jag har bytt det, jag sorteras det och vi är klara.
Nu är det råkar vara så att den blå delen är återigen 5,
och vi måste titta på 1, 6 och 4 för att fastställa att 1
är den minsta minsta elementet, så vi byta 1 och 5.
Återigen måste vi titta på - jämför 5 till 6 och 4,
och vi kommer att byta 4 och 5, och slutligen, jämför
dessa 2 siffror och byta dem tills vi får vår sorterad lista.
Eventuella frågor om val Sortera?
Okej. Låt oss gå till den sista frågan här, och det är rekursion.
>> Rekursion, kom ihåg, detta är verkligen meta sak där en funktion
upprepade gånger kallar sig.
Så någon gång, medan vår fuction upprepade gånger kallar sig,
måste det finnas någon punkt där vi sluta ringa oss.
För om vi inte gör det, då vi bara kommer att fortsätta att göra detta för evigt,
och vårt program är bara inte att avsluta.
Vi kallar detta tillstånd basfallet.
Och basfallet säger, snarare än att ringa en funktion igen,
Jag ska bara returnera något värde.
Så när vi har återvänt till ett värde har vi slutat kalla oss själva,
och resten av de samtal vi har gjort hittills kan också återvända.
Motsatsen till basfallet är den rekursiva fallet.
Och det är när vi vill ringa ett annat samtal till den funktion som vi nu i.
Och vi förmodligen, men inte alltid, vill använda olika argument.
>> Så om vi har en funktion som kallas f och f bara kallas ta 1 argument,
och vi håller bara ringa f (1), f (1), f (1), och det råkar vara så att
argumentet 1 faller in rekursiv fall, vi ändå aldrig kommer att sluta.
Även om vi har en bas fall måste vi se till att så småningom ska vi träffa den basfall.
Vi vill inte bara hålla vistas i denna rekursiva fallet.
Generellt när vi kallar oss, vi kommer förmodligen att ha olika argument varje gång.
Här är en riktigt enkel rekursiv funktion.
Så det här kommer att beräkna fakulteten av ett tal.
Uppe här har vi vår bas fallet.
I det fall att n ≤ 1, vi kommer inte att ringa faktoriell igen.
Vi kommer att sluta, vi ska bara returnera något värde.
Om detta inte är sant, så ska vi träffa vår rekursiva fallet.
Notera här att vi inte bara kallar fakultet (n), eftersom det inte skulle vara till stor hjälp.
Vi kommer att kalla fakulteten av något annat.
>> Och så att du kan se, så småningom om vi passerar en faktoriell (5) eller något,
vi kommer att ringa faktoriell (4) och så vidare, och så småningom kommer vi att träffa Detta basfall.
Så här ser bra ut. Låt oss se vad som händer när vi faktiskt köra.
Detta är stacken, och låt oss säga att främsta kommer att kalla denna funktion med ett argument (4).
Så när faktoriell ser och = 4, kommer fakulteten kalla sig.
Nu, plötsligt har vi faktoriell (3).
Så dessa funktioner kommer att fortsätta växa tills slutligen vi träffar vår basfallet.
Vid denna punkt, är returvärdet av detta avkastningen (nx returvärdet av detta),
returvärdet av detta är nx returvärdet av detta.
Så småningom måste vi träffa några nummer.
På toppen här, säger vi tillbaka 1.
Det innebär att när vi tillbaka det numret kan vi pop detta utanför stapeln.
Så denna fakultet (1) görs.
När 1 återvänder, detta faktorförsök (1) avkastning, denna återgång till 1.
Avkastningen värdet av detta, kom ihåg, var nx returvärdet av detta.
Så plötsligt vet den här killen som jag vill återvända 2.
>> Så kom ihåg, returnera värdet av detta är bara nx returvärdet här uppe.
Så nu kan vi säga 3 x 2, och slutligen, här kan vi säga
detta bara kommer att vara 4 x 3 x 2.
Och när detta avkastning, får vi ner till en enda heltal inuti huvud.
Eventuella frågor om rekursion?
Okej. Så det finns mer tid för frågor i slutet,
men nu Josef kommer att täcka de återstående ämnena.
>> [Joseph Ong] Okej. Så nu när vi har pratat om rekursioner,
Låt oss prata lite om vad samman slag är.
Merge Sortera är i grunden ett annat sätt att sortera en lista med tal.
Och hur det fungerar är, med merge sort du har en lista, och vad vi gör är
vi säger, låt oss dela detta till 2 halvor.
Vi kommer först köra samman Sortera igen på den vänstra halvan,
då skall vi köra ihop Sortera på den högra halvan,
och det ger oss nu 2 halvor som sorteras, och nu ska vi kombinera dessa halvorna.
Det är lite svårt att se utan ett exempel, så går vi igenom hela proceduren och se vad som händer.
Så du börjar med den här listan, vi dela den i 2 halvor.
Vi kör samman Sortera på vänster halv först.
Så det är den vänstra halvan, och nu kör vi dem genom den här listan igen
som får skickas in sammanslagning sortera och vi ser återigen
på vänster sida av denna lista, och vi kör ihop Sortera på den.
Nu får vi ner till en lista med 2 siffror,
och nu den vänstra halvan är bara 1 del långa, och vi kan inte
dela en lista som är endast 1 element i halv, så vi bara säga, när vi har 50,
vilket är bara 1 del, det är redan sorterade.
>> När vi är klara med det, kan vi se att vi kan
gå vidare till den högra halvan av listan,
och 3 är också sorteras och så nu att båda halvorna av denna lista sorteras
Vi kan ansluta sig till dessa siffror tillsammans igen.
Så vi ser på 50 och 3, 3 är mindre än 50, så det går in först och därefter 50 kommer in
Nu är det gjort, vi gå upp till den listan och sortera det är rätt halv.
42 är dess eget nummer, så det är redan sorterade.
Så nu har vi jämföra dessa 2 och 3 är mindre än 42, så får ställas på första,
nu 42 får sätta in, och 50 får sätta in
Nu, det är sorterade går vi hela vägen tillbaka till toppen, 1337 och 15.
Tja, vi ser nu på den vänstra halvan av denna lista, 1337 är i sig så det är sorterade och samma med 15.
Så nu vi kombinera dessa 2 siffror för att sortera den ursprungliga listan, 15 <1337,
så det går i först, sedan 1337 går in
Och nu har vi sorterade båda halvorna av den ursprungliga listan uppe.
Och allt vi behöver göra är att kombinera dessa.
Vi tittar på de första 2 siffrorna i denna förteckning, 3 <15, så det går in i typ arrayen först.
15 <42, så det går i. Nu, 42 <1337, som går in
50 <1337, så det går in och märker att vi bara tog 2 nummer av denna lista.
Så vi är bara växlar mellan de 2 listorna.
Vi söker bara i början, och vi tar elementet
Det är mindre och sedan sätta det i vårt utbud.
Nu har vi samman alla halvor och vi är klara.
>> Har du frågor om samman slag? Ja?
[Student] Om det är att dela in i olika grupper, varför de inte dela bara en gång
och du har 3 och 2 i en grupp? [Övriga frågor obegriplig]
Anledningen - så frågan är, varför kan vi inte bara ihop dem på det första steget efter att vi har dem?
Anledningen till att vi kan göra detta, starta vid den vänstra element på båda sidor,
och sedan ta den mindre och placera den i, är att vi vet att dessa
enskilda listor i sorterade order.
Så om jag tittar på den vänstra delarna av båda halvorna,
Jag vet att de kommer att vara de minsta delarna av dessa listor.
Så jag kan sätta dem i det minsta elementet fläckar av denna stora lista.
Å andra sidan, om jag tittar på de 2 listorna i den andra nivån där borta,
50, 3, 42, 1337 och 15, är de inte sorteras.
Så om jag tittar på 50 och 1337, kommer jag att lägga 50 i min lista först.
Men det gör inte riktigt mening, eftersom 3 är den minsta delen av alla av dem.
Så det enda skälet till att vi kan göra detta kombinerar steg är att våra listor redan är sorterade.
Det är därför vi måste få ner hela vägen till botten
för när vi bara har ett enda nummer, du vet att ett enda nummer
i och för sig är redan en sorterad lista.
>> Några frågor? Nej?
Komplexitet? Tja, kan du se att i varje steg finns end nummer,
och vi kan dela en lista i halva log n gånger,
som är där vi får denna n x log n komplexitet.
Och du kommer att se det bästa fallet för sammanslagning slag är n log n, och det råkar vara så
att det värsta fallet, eller Ω borta, är också n log n.
Något att tänka på.
Går vidare, låt oss gå vidare till några super grundläggande fil-I / O.
Om du tittat på Scramble, kommer du att märka att vi hade någon form av system
där du kan skriva till en loggfil om du läser igenom koden.
Låt oss se hur du kan göra det.
Tja, vi har fprintf, som du kan tänka på som bara printf,
men bara skriver ut till en fil i stället, och därmed f i början.
Denna typ av kod här uppe, vad den gör är, som ni kanske har sett i Scramble,
det går igenom din 2-dimensionell array utskrift av rad för rad vad siffrorna är.
I det här fallet, printf skriver ut till din terminal eller vad vi kallar standard ut av avsnitt.
>> Och nu, i det här fallet är allt vi har att göra ersätta printf med fprintf,
tala om vad fil du vill skriva ut till, och i det här fallet bara skriver ut det till den filen
istället för att skriva ut det till din terminal.
Nå, då väcker frågan: Var ska vi få denna typ av fil från, eller hur?
Vi passerade logga in på denna fprintf fuction men vi hade ingen aning om var den kom ifrån.
Jo, i början av koden, vad vi hade var denna bit av kod här borta,
som i princip säger att öppna filen kallar log.txt.
Vad vi gör när det är vi måste se till att filen faktiskt öppnas framgångsrikt.
Så det kan misslyckas av flera anledningar, du har inte tillräckligt med utrymme på din dator, till exempel.
Så det är alltid viktigt innan du gör någon verksamhet med filen
att vi kontrollera om den filen öppnades framgångsrikt.
Så vad om att en, det är ett argument till fopen, ja, vi kan öppna en fil på många sätt.
Vad vi kan göra är, kan vi ge det w, vilket innebär åsidosätta filen om det kommer ut redan,
Vi kan skicka en en, som de lägga till i slutet av filen i stället för tvingande det,
eller så kan vi specificera r, vilket betyder, låt oss öppna filen som skrivskyddad.
Så om programmet försöker göra några ändringar i filen,
skrika på dem och inte låta dem göra det.
Slutligen, när vi är klara med filen, gjort gjort operationer på det,
Vi måste se till att vi stänger filen.
Och så i slutet av ditt program, du kommer att passera dem igen
denna fil som du öppnade, och bara stänga den.
Så detta är något viktigt som du måste se till att du gör det.
Så kom ihåg att du kan öppna en fil, kan du skriva till filen,
göra verksamheten i filen, men då måste man stänga filen i slutet.
>> Eventuella frågor om grundläggande fil-I / O? Ja?
[Student fråga, obegripligt]
Just här. Frågan är inte om detta log.txt fil visas?
Tja, om du bara ger den log.txt skapas den i samma katalog som den körbara.
Så om Du är - >> [Student fråga, obegripligt]
Ja. I samma mapp, eller i samma katalog, som du kallar det.
Nu minne, stack och heap.
Så hur är minnet som anges i datorn?
Tja, du kan tänka minne som en slags detta block här.
Och i minnet har vi vad som kallas högen fastnat borta, och stapeln som är där nere.
Och högen växer nedåt och stapeln växer uppåt.
Så som Tommy nämnde - Åh, ja, och vi har dessa andra 4 segment som jag kommer till i en andra -
Som Tommy sa tidigare, vet du hur hans funktioner kallar sig och ringa varandra?
De bygger upp denna typ av stack ram.
Tja, om viktiga samtal foo, blir foo sätta på stacken.
Foo kallar bar, bar få oss sätta på stacken, och som får sätta på stacken efter.
Och när de återvänder, var de får tas bort från stacken.
Vad gör håller alla dessa platser och minne?
Tja, innehåller den övre, som är den text segmentet själva programmet.
Så maskinkod, som finns där när du kompilerar programmet.
Därefter varje initierad globala variabler.
>> Så du har globala variabler i ditt program, och du säger som en = 5,
som får placeras i detta segment, och rätt under det,
du har oinitierade globala data, som just är int a,
men du säger inte att det är lika med någonting.
Inse detta är globala variabler, så de är utanför huvud.
Så detta betyder alla globala variabler som deklarerats men inte initierats.
Så vad som finns i högen? Minne fördelas med hjälp av malloc, som vi kommer till i en liten bit.
Och slutligen, med stapeln du har lokala variabler
och alla funktioner du kan ringa i någon av deras parametrar.
Det sista, behöver du inte verkligen måste veta vad miljövariabler gör,
men när du kör programmet, det är något samband, liksom
Detta är användarnamnet på den person som körde programmet.
Och det kommer att bli typ av nedtill.
I termer av minnesadresser, som är hexadecimala värden,
värdena på toppen start på 0, och de går hela vägen ner till botten.
I detta fall, om du är på 32-bitars system,
adressen längst ner kommer att bli 0x följt av af, eftersom det är 32 bitar,
vilket är 8 bitgrupper, och i detta fall 8 bitgrupper motsvarar 8 hexadecimala siffror.
Så här nere du kommer att få, liksom, 0xFFFFFF och upp där du kommer att ha 0.
Så vad är pekare? Några av er kanske inte har täckt detta i avsnittet innan.
men vi gick över den i föreläsning, så en pekare är bara en datatyp
vilka butiker, i stället för någon form av värde som 50, lagrar den adressen för en viss plats i minnet.
Precis som minne [obegripliga].
Så i det här fallet, det vi har är, har vi en pekare till ett heltal eller en int *,
och den innehåller det hexadecimala adressen för 0xDEADBEEF.
>> Så vad vi har är nu, denna pekare pekar på en viss plats i minnet,
och det är bara en, är värdet 50 på den här minnesplats.
På vissa 32-bitars system, på alla 32-bitars system, pekare tar upp 32 bitar eller 4 byte.
Men till exempel på en 64-bitars system, pekare är 64 bitar.
Så det är något du kommer att vilja ha i åtanke.
Så på ett ände-bitars system, är en pekare end bitar lång.
Pekare är typ av svårt att smälta utan extra saker,
så låt oss gå igenom ett exempel på dynamisk minnesallokering.
Vilka dynamisk minnesallokering gör för dig, eller vad vi kallar malloc,
det kan du fördela någon form av data utanför apparaten.
Så denna data är typ av mer permanent för programmets löptid.
För som du vet, om du deklarerar X inuti en funktion, och som returnerar funktion,
du inte längre har tillgång till de data som lagrats i x.
Vilka pekare låt oss göra är att de låter oss lagra minne eller lagra värden
i ett annat segment av minnet, nämligen högen.
Nu när vi återvänder ur funktion, så länge vi har en pekare
till den platsen i minnet, vad vi kan göra är att vi bara kan titta på de värden där.
Låt oss titta på ett exempel: Det här är vårt minne layout igen.
Och vi har denna funktion, huvud.
Vad den gör är - okej, så enkelt, eller hur -? Int x = 5, det är bara en variabel på stacken i main.
>> Å andra sidan, nu har vi deklarera en pekare som anropar funktionen giveMeThreeInts.
Och så nu går vi in ​​i denna funktion och vi skapar en ny bunt ram för den.
Men i denna stack ram, förklarar vi int * temp,
som i mallocs 3 heltal för oss.
Så storleken på int kommer att ge oss hur många byte här int är,
och malloc ger oss att många byte utrymme på högen.
Så i det här fallet har vi skapat tillräckligt med utrymme för 3 heltal,
och högen är vägen upp där, det är därför jag har ritat det högre upp.
När vi är klara, vi kommer tillbaka hit, behöver du bara 3 Ints tillbaka,
och den returnerar adressen, i detta fall över var att minnet är.
Och vi satt pekare = switch och upp där vi har bara en annan pekare.
Men vad det returnerar funktionen staplas här och försvinner.
Så temp försvinner, men vi har fortfarande behålla adressen där
dessa 3 heltal är inuti elnätet.
Så i denna uppsättning, kommer pekarna är scoped lokalt för staplade ramen,
men minnet som de avser är i högen.
>> Verkar det vettigt?
[Student] Kan du upprepa det? >> [Joseph] Ja.
Så om jag går tillbaka bara lite, ser du att temp tilldelade
viss minnet på högen uppe.
Så när denna funktion giveMeThreeInts returer, detta stack här kommer att försvinna.
Och med det någon av variablerna, i detta fall, denna pekare som tilldelats i staplade ram.
Som kommer att försvinna, men eftersom vi återvände temp
och vi satt pekare = temp, pekare är nu att peka på samma minne av plats som temp var.
Så nu, även om vi förlorar temp, det lokala pekare,
Vi har fortfarande kvar minnesadressen vad det pekar på insidan av denna variabel pekare.
Frågor? Det kan vara lite av en förvirrande ämne om du inte har gått över den i avsnitt.
Vi kan, kommer din TF definitivt gå över den och naturligtvis kan vi svara på frågor
I slutet av översynen sessionen för detta.
Men detta är en slags komplext ämne, och jag har fler exempel som kommer att visa upp
som hjälper klargöra vad pekare faktiskt är.
>> I detta fall, pekare motsvarar matriser,
så jag kan bara använda denna pekare som samma sak som en int array.
Så jag indexera in 0 och ändra den första heltalet till 1,
ändra andra heltalet till 2, och den 3: e heltal till 3.
Så mer på pekare. Tja, minns Binky.
I det här fallet har vi tilldelas en pekare, eller vi förklarade en pekare,
men först, när jag bara förklarade en pekare, det pekar inte till någonstans i minnet.
Det är bara skräp värden i den.
Så jag har ingen aning om var denna pekare pekar på.
Den har en adress som bara är fylld med 0 s och 1 s där det ursprungligen deklarerade.
Jag kan inte göra någonting med det här tills jag kallar malloc på det
och då det ger mig lite utrymme på högen där jag kan sätta värden på insidan.
Då igen, jag vet inte vad som finns inuti detta minne.
Så det första jag måste göra är att kontrollera om systemet hade tillräckligt med minne
att ge mig tillbaka 1 heltal i första hand, vilket är varför jag gör denna kontroll.
Om pekaren är noll, innebär det att det inte har tillräckligt med utrymme eller något annat fel uppstod,
så jag skulle gå ut ur mitt program.
Men om det lyckades, nu kan jag använda det pekare
och vad * pekare gör det följer där adressen är
där detta värde är, och det sätter det lika med 1.
Så här borta, vi kontrollerar om minnet fanns.
>> När du vet det finns, kan du sätta i det
vilket värde du vill lägga in den, i det här fallet 1.
När vi är klara med det, måste du frigöra den pekare
eftersom vi måste gå tillbaka till det system som minne som du bad om i första hand.
Eftersom datorn inte vet när vi är klara med det.
I det här fallet är vi uttryckligen säger det, okej, vi gjort med detta minne.
Om någon annan process behöver det, något annat program behöver det, gärna gå vidare och ta den.
Vad vi kan också göra är att vi bara kan få adressen till lokala variabler på apparaten.
Så int x är innanför staplade ramen viktigaste.
Och när vi använder denna ampersand, detta och operatör, vad den gör är
det tar x, och x är bara några data i minnet, men det har en adress.
Det ligger någonstans. Så genom att ringa & X, vad detta innebär är att det ger oss adressen till x.
Genom att göra detta, vi gör pekare pekar på där x är i minnet.
Nu har vi bara inte något som * x, vi kommer att få 5 tillbaka.
Stjärnan heter dereferencing det.
Du följer adressen och du får värdet av den lagrade där.
>> Några frågor? Ja?
[Student] Om du inte gör det 3-spetsiga sak, inte kompilera det fortfarande?
Ja. Om du inte gör det 3-pekaren sak, det kommer fortfarande att sammanställa,
men jag ska visa dig vad som händer i en sekund och utan att göra det,
Det är vad vi kallar en minnesläcka. Du ger inte systemet
tillbaka sitt minne, så efter ett tag att programmet kommer att ackumulera
minne att det inte är med, och ingenting annat kan använda den.
Om du någonsin sett Firefox med 1,5 miljoner kilobyte på datorn,
i Aktivitetshanteraren, det är vad som händer.
Du har en minnesläcka i programmet som de inte hanterar.
Så hur fungerar pekaren aritmetiska arbete?
Tja, pekare aritmetik ungefär som indexering i en matris.
I det här fallet har jag en pekare, och vad jag gör är att jag gör pekare pekar på det första elementet
denna uppsättning av 3 heltal som jag har tilldelats.
Så nu vad jag gör, ändrar stjärna pekare bara det första elementet i listan.
Star pointer en poäng här.
Så pekaren är över här, pekaren en hit, är pekaren 2 här.
>> Så bara lägga 1 är samma sak som att flytta längs denna rad.
Vad vi gör är att när vi gör pekaren en får du adressen hit,
och för att få värdet i här sätter du en stjärna i från hela uttrycket
att avreferera det.
Så i det här fallet, jag sätta den första platsen i denna matris till 1,
andra plats till 2, och den tredje plats till 3.
Sen vad jag gör här borta är jag skriver vår pekare +1,
vilket ger mig bara 2.
Nu är jag inkrementera pekare, så pekare lika pekare +1,
som flyttar den framåt.
Och så nu om jag skriver ut pekare +1, är pekare ett nu 3,
som i detta fall skriver ut 3.
Och för att fritt någonting, pekaren att jag ger det
måste peka i början av kedjan som jag kom tillbaka från malloc.
Så i det här fallet, om jag skulle ringa 3 här, skulle detta inte vara rätt,
eftersom det är i mitten av matrisen.
Jag måste subtrahera för att komma till den ursprungliga platsen
den initiala första plats innan jag kan befria det.
Så, här är en mer engagerad exempel.
I det här fallet, vi fördela 7 tecken i en karaktär array.
>> Och i detta fall vad vi gör är att vi looping över de första 6 av dem,
och vi sätta dem till Z.
Så, för int i = 0, i> 6, i + +,
Så, pekare + jag kommer bara ge oss, i detta fall,
pekare, +1 pekare, +2 pekare, pekare +3 och så vidare och så vidare i slingan.
Vad det kommer att göra är att det blir den adressen, dereferences den för att få värdet,
och förändringar som värde till ett Z.
Sedan i slutet ihåg detta är en sträng, eller hur?
Alla strängar måste sluta med noll avslutande karaktär.
Så vad jag gör är i pekare 6 Jag lade null terminator tecknet i.
Och nu vad jag i grund och botten ska göra hit genomför printf efter en sträng, eller hur?
>> Så, när printf nu när det är nått slutet av en sträng?
När den träffar noll avslutande karaktär.
Så i detta fall min ursprungliga pekaren pekar på början av denna uppsättning.
Jag skriver ut det första tecknet ut. Jag flyttar den över en.
Jag skriver ut det tecknet ut. Jag flyttar den över.
Och jag fortsätter att göra det tills jag kommer till slutet.
Och nu i slutet * pekaren dereference detta och få noll avslutande tecknet tillbaka.
Och så min while-slinga körs endast när värdet inte är null avslutande tecken.
Så nu har jag avslutar ur denna slinga.
Och så om jag subtraherar 6 från denna pekare,
Jag går tillbaka ända till början.
Kom ihåg, jag gör det här för att jag måste gå till början för att frigöra det.
>> Så, jag vet att det var en hel del. Finns det några frågor?
Snälla, ja?
[Student fråga obegriplig]
Kan du säga det högre? Ursäkta.
[Student] På den sista bilden till höger innan du befriade pekaren,
var var du ändrar faktiskt värdet av pekaren?
[Josef] Så här. >> [Student] Åh, okej.
[Josef] Så jag har en pekare minus minus, höger,
som flyttar sak tillbaka en, och sedan jag befria det,
eftersom denna pekare måste pekade på början av arrayen.
[Student] Men det skulle behövas hade du slutade efter den linjen.
[Josef] Så om jag hade slutat efter detta skulle detta betraktas som en minnesläcka,
eftersom jag inte kör gratis.
[Student] I [obegripliga] efter de första tre raderna där du hade pekare en [obegripliga].
[Joseph] Uh-huh. Så, vad är frågan där?
Ursäkta. Nej, nej. Gå, gå, snälla.
[Student] Så ändrar du inte värdet av pekare.
Du skulle inte ha behövt göra pekare minus minus.
[Josef] Ja, exakt.
Så när jag gör pekare +1 och pekare 2,
Jag gör pekare lika pekare +1.
Så pekaren bara förblir pekar på början av arrayen.
Det är bara när jag gör plus plus att det sätter värdet tillbaka in pekaren,
att det rör sig faktiskt detta tillsammans.
Okej.
Fler frågor?
>> Återigen, om detta är typ av överväldigande, kommer detta att behandlas i sessionen.
Fråga din undervisning karl om det, och vi kan svara på frågor i slutet.
Och brukar vi gillar inte att göra det minus sak.
Detta måste tvinga mig att hålla koll på hur mycket jag har offset i arrayen.
Så i allmänhet, detta är bara för att förklara hur fungerar pekaren aritmetiska.
Men vad vi brukar vilja göra är att vi vill skapa en kopia av pekaren,
och sedan kommer vi att använda kopian när vi ska flytta runt i strängen.
Så i dessa fall du använder kopian för att skriva ut hela strängen,
men vi behöver inte göra som pekare minus 6 eller hålla koll på hur mycket vi flyttade detta,
bara för att vi vet att vår ursprungliga punkten fortfarande pekar på början av listan
och allt som vi ändrade var denna kopia.
Så i allmänhet, ändra kopior av din ursprungliga pekaren.
Försök inte att sortera av liknande - inte ändra original.
Försöker ändra bara kopior av originalet.
Så märker du när vi passerar strängen i printf
du behöver inte sätta en stjärna framför det som vi gjorde med alla andra dereferences, eller hur?
Så, om du skriver ut hela strängen% s förväntar är en adress,
och i detta fall en pekare eller i detta fall som en uppsättning tecken.
>> Tecken, char * s, och arrayer är samma sak.
Pointer är att tecken och tecken arrayer är samma sak.
Och så är klara allt vi behöver göra i pekaren.
Vi behöver inte gå in som * pekare eller något liknande.
Så arrayer och pekare är samma sak.
När du gör något som x [y] hit för en matris,
vad den gör under huven är det säger, okej, det är ett tecken array,
så det är en pekare.
Och så x är samma sak,
och så vad den gör är det tillför y till x,
vilket är samma sak som att flytta framåt i minnet så mycket.
Och nu x + y ger oss någon form av adress,
och vi dereference adressen eller följ pilen
där den platsen i minnet är och vi får det värde ur den platsen i minnet.
Så, så dessa två är exakt samma sak.
Det är bara en syntaktisk socker.
De gör samma sak. De är bara olika syntactics för varandra.
>> Så, vad kan gå fel med pekare? Liksom, en hel del. Okej. Så dåliga saker.
Vissa dåliga saker du kan göra är att inte kontrollera om din malloc samtal returnerar null, eller hur?
I det här fallet, jag ber systemet att ge mig - vad är det numret?
Som 2 miljarder gånger 4, eftersom storleken på ett heltal är 4 byte.
Jag ber den för som 8 miljarder byte.
Naturligtvis min dator inte kommer att kunna ge mig så mycket minne tillbaka.
Och vi inte kontrollera om det är null, så när vi försöker dereference det där -
Följ pilen till där det kommer att - vi har inte det minnet.
Detta är vad vi kallar dereferencing en null-pekare.
Och detta orsakar i huvudsak att du segmenteringsfel.
Detta är ett av de sätt du kan segmenteringsfel.
Andra dåliga saker du kan göra - jaha.
Det var dereferencing en null-pekare. Okej.
Andra dåliga saker - ja, att fixa att du bara sätta en kontroll i det
som kontrollerar om pekaren är null
och avsluta ur programmet om det händer att malloc returnerar en null-pekare.
Det är xkcd komiska. Folk förstår det nu. Sortera på.
>> Så, minne. Och jag gick över detta.
Vi kallar malloc i en slinga, men varje gång vi kallar malloc
vi förlorar reda på var denna pekare pekar på,
eftersom vi dunkardags det.
Så ger det första samtalet till malloc mig minnet hit.
Min pekaren pekare till detta.
Nu har jag inte frigöra det, så nu kallar jag malloc igen.
Nu pekar hit. Nu mitt minne pekar hit.
Pekar hit. Pekar hit.
Men jag har förlorat kontakten med adresserna till allt minne hit som jag tilldelats.
Och så nu har jag inte någon hänvisning till dem längre.
Så kan jag befria dem inte utanför denna slinga.
Och så för att fixa något sådant,
om du glömmer att frigöra minne och du får denna minnesläcka,
Du måste frigöra minne inuti denna slinga när du är klar med det.
Tja, detta är vad som händer. Jag vet massor av du hatar det här.
Men nu - yay! Du får som 44.000 kilobyte.
Så befria dig det i slutet av slingan,
och det kommer att bara frigöra minne varje gång.
I huvudsak har programmet inte en minnesläcka längre.
>> Och nu något annat du kan göra är frigöra minne som du har bett om två gånger.
I det här fallet kan du malloc något, ändrar du dess värde.
Du frigöra det en gång för att du sa att du var klar med den.
Men sedan vi befriade det igen.
Detta är något som är ganska dålig.
Det kommer inte att initialt segmenteringsfel,
men efter ett tag Vad detta innebär är dubbelt frigör detta korrumperar din hög struktur,
och du får lära dig lite mer om detta om du väljer att ta en klass som CS61.
Men i huvudsak efter ett tag din dator kommer att bli förvirrad
om vilka minnesplatser är där och var den finns -
där data lagras i minnet.
Och så frigör en pekare två gånger är en dålig sak som du inte vill göra.
>> Andra saker som kan gå fel är att inte använda sizeof.
Så i detta fall du malloc 8 byte,
och det är samma sak som två heltal, eller hur?
Så, det är helt säkert, men är det?
Tja, som Lucas talade om på olika arkitekturer,
heltal är av olika längder.
Så, på den apparat som du använder, heltal är ca 4 byte,
men på något annat system de kan vara 8 byte eller de kan vara 16 byte.
Så om jag bara använder detta nummer här,
detta program kan fungera på apparaten,
men det kommer inte att fördela tillräckligt med minne på något annat system.
I det här fallet är det vad sizeof operatören används till.
När vi kallar sizeof (int), vad detta innebär är
det ger oss stor ett heltal på systemet som programmet körs.
Så i detta fall kommer sizeof (int) returnera 4 på något som apparaten,
och nu denna vilja 4 * 2, vilket är 8,
vilket är precis den mängd utrymme som krävs för två heltal.
På ett annat system, om en int är som 16 byte eller 8 byte,
det är bara att gå tillbaka tillräckligt byte för att lagra detta belopp.
>> Och slutligen, structs.
Så om du ville spara en sudoku styrelse i minnet, hur kan vi göra detta?
Du kanske tänker på som en variabel för det första,
en variabel för andra sak, en variabel för den tredje sak,
en variabel för det fjärde sak - dåligt, eller hur?
Så, en förbättring kan du göra på toppen av detta för att göra en 9 x 9 matris.
Det är bra, men vad händer om du ville att andra saker med sudoku styrelse
gillar vad svårigheten i styrelsen är,
eller, till exempel, vad din poäng är, eller hur mycket tid det har tagit dig att lösa detta forum?
Tja, vad du kan göra är att du kan skapa en struktur.
Vad jag i grunden säger är att jag definierar denna struktur här,
och jag definierar en sudoku styrelse som består av en styrelse som är 9 x 9.
>> Och vad den har den har pekare till namnet på nivån.
Det har också x och y, som är koordinaterna för där jag är just nu.
Det har också tid [obegriplig], och det har det totala antalet drag som jag har registrerats hittills.
Och så i det här fallet kan jag gruppera en massa data i endast en struktur
istället för att ha det som flyger runt i likhet olika variabler
att jag inte kan riktigt hålla reda på.
Och det låter oss har bara trevligt syntax för slags hänvisningar olika saker inuti denna struct.
Jag kan bara göra board.board, och jag får sudoku styrelsen tillbaka.
Board.level får jag hur svårt det är.
Board.x och board.y ge mig koordinaterna för där jag kan vara i styrelsen.
Och så jag åt det vi kallar fält i struct.
Detta definierar sudokuBoard, som är en typ som jag har.
Och nu är vi här. Jag har en variabel som heter "board" av typen sudokuBoard.
Och så nu jag kan komma åt alla fält som utgör denna struktur här.
>> Har du frågor om structs? Ja?
[Student] För int x, y, förklarade ni båda på en rad? >> [Joseph] Uh-huh.
[Student] Så kan du göra just det med alla?
Liksom i x, y kommatecken gånger totalt?
[Josef] Ja, kan du definitivt göra det, men anledningen till att jag satte x och y på samma rad -
och frågan är varför kan vi bara göra det på samma linje?
Varför inte vi bara sätta alla dessa på samma linje är
x och y är relaterade till varandra,
och detta är bara stilistiskt mer korrekt, i en mening,
eftersom det är gruppering två saker på samma linje
som gillar typ av rör samma sak.
Och jag dela just dessa isär. Det är bara en stil sak.
Det gör funktionellt ingen skillnad alls.
Alla andra frågor om structs?
Du kan definiera en Pokédex med struct.
En Pokémon har ett nummer och det har ett brev, en ägare, en typ.
Och sedan om du har en mängd Pokémon, kan du göra en Pokédex, eller hur?
Okej, coolt. Så frågor om structs. Det är relaterade till structs.
>> Slutligen, GDB. Vad låter GDB du göra? Det låter dig felsöka ditt program.
Och om du inte har använt GDB, skulle jag rekommenderar att titta på korta
och bara gå över vad GDB är, hur du arbetar med det, hur du kan använda den,
och testa den på ett program.
Och så vad GDB kan du göra det låter pausa [obegripliga] upp ditt program
och en praktisk linje.
Till exempel vill jag pausa utförande på som linje 3 i mitt program,
och medan jag är på linje 3 Jag kan skriva ut alla värden som finns där.
Och så vad vi kallar som pausa i en linje
är kallar vi detta sätta en brytpunkt på den linjen
och då kan vi skriva ut variabler på tillståndet i programmet vid den tiden.
>> Vi kan sedan därifrån gå igenom programmet rad för rad.
Och då kan vi titta på tillståndet i stacken på tiden.
Och så för att kunna använda GDB, vad vi gör är att vi kallar klang på C-filen,
men vi måste passera den-ggdb flaggan.
Och när vi är klara med att vi bara köra gdb på den resulterande utdatafilen.
Och så får du lite liknande massa text som denna,
men egentligen allt du behöver göra är att skriva in kommandon i början.
Break sätter en brytpunkt på huvud.
Lista 400 listar kodrader runt linjen 400.
Och så i det här fallet kan du bara titta runt och säga, Åh,
Jag vill ställa en brytpunkt på rad 397, vilket är denna linje,
och sedan ditt program körs i det steget och det kommer att bryta.
Det kommer att pausa det, och du kan skriva ut, till exempel värdet av låg eller hög.
Och så finns det en massa kommandon du behöver veta,
och det här bildspelet kommer att gå upp på hemsidan,
så om du bara vill referera dessa eller liknande sätta dem på din fuska lakan, gärna.
>> Cool. Det var Quiz Recension 0, och vi kommer stanna kvar om du har några frågor.
Okej.
>> [Applåder]
>> [CS50.TV]