[Powered by Google Translate] [Vecka 4]
[David J. Malan] [Harvard University]
[Detta är CS50.] [CS50.TV]
>> Okej, det här CS50, och detta är början på vecka 4,
och detta är en av de långsammaste möjliga sortering algoritmer.
Vilket var det att vi bara sett det?
Det var bubbla sortera, så Big O (n ^ 2) + summa,
och faktiskt är vi inte de enda i denna värld att verka för att känna
vilken bubbla sortera är eller dess gångtid.
I själva verket var detta en intervju med Eric Schmidt på Google
och tidigare senator Barack Obama för bara några år sedan.
>> Nu senator, du är här på Google,
och jag gillar att tänka på ordförandeskapet som en anställningsintervju.
Nu är det svårt att få ett jobb som president, och du går igenom stelhet nu.
Det är också svårt att få ett jobb på Google.
Vi har frågor, och vi ber våra kandidater frågor,
och detta är från Larry Schwimmer.
Ni tror att jag skojar? Det är precis här.
Vad är det mest effektiva sättet att sortera en miljon 32-bitars heltal?
[Skratt]
Väl
Jag är ledsen. >> Nej, nej, nej, nej.
Jag tror att bubblan Sortera skulle vara fel väg att gå.
>> Kom igen, som berättade honom det?
Förra veckan minns vi tog en paus från kod, åtminstone för en dag,
och började fokusera på några högre nivå idéer och problemlösning mer allmänt
i samband med sökning och sortering,
och vi introducerade något som vi inte slap detta namn på förra veckan,
men asymptotiska notation, Big O, Big Omega,
och ibland den stora Theta notation, och dessa var helt enkelt sätt
att beskriva gångtid av algoritmer,
hur mycket tid det tar för en algoritm för att köra.
>> Och du kanske minns att du pratade om gångtid i termer av storlek
av insignalen, som vi vanligtvis kallar N, vad problemet kan vara,
där n är antalet personer i rummet,
antalet sidor i en telefonbok, och vi började skriva saker
som O (n ^ 2) eller O (n) eller O (n log n),
och även när matten inte riktigt träna så perfekt
och det var n ^ - n / 2 eller något liknande
Vi skulle i stället bara kasta bort en del av de lägre ordningens termer,
och motivationen finns att vi verkligen vill ha ett
slags objektivt sätt att utvärdera
prestanda program eller utförande av algoritmer
att vid slutet av dagen har ingenting att göra, till exempel,
med hastigheten på din dator idag.
>> Till exempel, om du implementerar bubbla sortera,
eller du genomför samman sortera eller val Sortera på dagens dator,
en 2 GHz dator och du kör den,
och det tar ett visst antal sekunder, nästa år finns en 3 GHz
eller en 4 GHz dator, och du kan då hävda att "Wow, min algoritm
är nu dubbelt så snabb ", när i själva verket det är naturligtvis inte fallet.
Det är bara hårdvaran har blivit snabbare, men datorn
har inte, och så vill vi verkligen att kasta bort saker som
multiplar av 2 eller multipler av 3 när det gäller att beskriva
hur snabbt eller hur långsamt en algoritm är och egentligen bara fokusera
på n eller någon faktor därav,
lite ström därav som i fallet med slag från förra veckan.
Och minns att med hjälp av sammanslagning Sortera
vi kunde göra så mycket bättre än bubbla sortera och välja Sortera
och även införande sortera.
>> Vi kom ner till n log n, och igen,
ihåg att log n generellt refererar till något som växer
långsammare sedan n, så n log n hittills var bra
eftersom det var mindre än N ^.
Men för att uppnå n log n med merge sort
vad var det grundläggande fröet till en idé som vi var tvungna att utnyttja
att vi belånade också tillbaka i vecka 0?
Hur kunde vi ta itu med sortering problemet skickligt med merge sort?
Vad var den viktigaste insikten, kanske?
Någon alls.
Okej, låt oss ta ett steg tillbaka.
Beskriv samman Sortera med egna ord.
Hur gick det?
Okej, vi ro tillbaka till vecka 0.
Okej, ja.
[Ohörbart-student]
Okej, bra, så vi delade matris med tal i 2 delar.
Vi sorterade båda dessa delar, och sedan vi samman dem,
och vi har sett denna idé tidigare att ta ett problem som det här stora
och hugga upp den i ett problem som det här stora eller här stor.
>> Minns exemplet telefonboken.
Minns själv-räkningen algoritm från veckor sedan,
så slå ihop sortera sammanfattade denna pseudokod här.
När du gett n element, först var det förnuft kontrollera.
Om n <2 då inte göra något alls
eftersom om n <2 då n är givetvis 0 eller 1,
och så om det är antingen 0 eller 1 det finns inget att sortera.
Du är klar.
Din lista är redan trivialt sorteras.
Men annars om du har 2 eller flera element gå vidare och dela dem
i 2 halvor, vänster och höger.
Sortera varje av dessa halvor och sedan slå ihop de sorterade halvorna.
Men problemet här är att vid första anblicken detta känns som om vi punting.
Detta är en cirkulär definition att om jag bad dig att sortera dessa n element
och du säger "Okej, bra, vi sorterar de n / 2 och de N / 2 element,"
då min nästa fråga kommer att vara "Fint, hur du sorterar n / 2 element?"
>> Men på grund av strukturen av detta program,
eftersom det är denna basfallet, så att säga,
detta speciella fall som säger att om n <någon fast värde som 2 omedelbart återvända.
Svarar inte med samma cirkulära svar.
Denna process kommer detta Konjunkturberoende sluta så småningom.
Om jag ber dig "sortera dessa n element", och du säger: "Fine, sortera dessa n / 2,"
då du säger, "Fine, sortera dessa N / 4, n / 8, n/16,"
så småningom kommer du dela med ett tillräckligt stort antal
att du har bara 1 del kvar, då du kan säga,
"Här, här är en sorterad enda element."
Sedan briljans av denna algoritm upp här är att härleda från det faktum
att när du har alla dessa individuellt sorterade listor,
vilka alla är av storlek 1, som tycks vara meningslöst,
när du börjar slå samman dem och sammanfoga dem
du bygga upp slutligen som Rob gjorde i videon en slutligen sorterad lista.
>> Men denna idé sträcker sig långt utanför sortering.
Det är denna idé inbäddad i programmet kallas rekursion,
tanken där du är ett program,
och lösa vissa problem du kallar dig själv,
eller sätta i samband med programspråk du är en funktion,
och för att lösa ett problem, du funktionen kallar dig
igen och igen och igen, men du funktionen
kan inte kalla dig oändligt många gånger.
Så småningom måste du botten, så att säga,
och har en del hårdkodad bas tillstånd som säger
vid denna tidpunkt sluta kalla dig så att hela processen
Slutligen hindrar faktiskt.
Vad betyder detta egentligen till recurse?
>> Låt oss se om vi kan göra en enkel, trivialt exempel med, säg,
3 personer med mig här på scenen, om någon är bekväm.
1, kom upp, 2 och 3.
Om du 3 vill komma upp hit.
Om du vill stå bredvid mig här i en linje, antar att problemet till hands
är räkna mycket trivialt antalet personer som är här.
Men ärligt talat, jag är trött på alla dessa räknar exempel.
Detta kommer att ta tid, 1, 2, och punkt, punkt, punkt.
Det kommer att ta evigheter.
Jag vill hellre bara punt problemet helt och hållet med hjälp av, vad heter du?
Sara. >> Sara, okej.
Kelly. >> Kelly och?
>> Willy. >> Willy, Sara, Kelly, och Willy.
Just nu har jag ställt frågan av någon
hur många människor är upp på denna scen och jag har ingen aning.
Detta är en riktigt lång lista, och så istället ska jag göra detta trick.
Jag ska be personen bredvid mig att göra det mesta av arbetet,
och när hon är klar gör det mesta av arbetet
Jag ska göra den minsta mängden arbete möjligt och bara lägga 1
till vad hennes svar är, så nu kör vi.
Jag har blivit tillfrågad om hur många personer är på scenen.
Hur många personer är på scenen till vänster om dig?
Vänster om mig? >> Okej, men inte fuska.
Det är bra, det är riktigt, men om vi vill fortsätta denna logik
låt oss anta att du på samma sätt vill stakbåten detta problem till vänster om dig,
så i stället svara direkt gå vidare och bara vältra över ansvaret.
Åh, hur många människor till vänster om mig?
Hur många människor är till vänster?
1.
[Skratt]
Okej, så 0, så vad nu Willy gjort
är du tillbaka ditt svar denna riktning säger 0.
Nu, vad ska du göra? >> 1.
Okej, så du är 1, så att du säger: "Okej, jag kommer att lägga 1
till vad Willys räkna var "så 1 + 0.
Du är nu 1 så ditt svar till just nu-
1. >> Och mitt skulle vara 2.
Bra, så du tar den tidigare svar 1,
lägga den minimala mängden arbete du vill göra, vilket är en.
Du har nu 2, och du sedan ge mig vilket värde?
3, jag menar, ledsen, 2.
Bra.
>> Tja, vi hade 0 till vänster.
Sedan hade vi 1, och sedan lägger vi till 2,
och nu är du lämnar mig numret 2,
och så jag säger, okej, +1, 3.
Det finns faktiskt 3 personer som står bredvid mig på den här scenen,
så vi kunde har uppenbarligen gjort detta mycket linjärt,
mycket på det uppenbara sätt, men vad gjorde vi verkligen?
Vi tog ett problem av storlek 3 initialt.
Vi bröt sedan ner i ett problem av storlek 2,
då ett problem av storlek 1, och sedan slutligen basfallet
var verkligen, åh, det är ingen där,
varvid Willy tillbaka praktiken en hårdkodad svar ett par gånger,
och den andra bubblades sedan upp, bubblade upp, bubblade upp,
och därefter genom tillsats i detta ytterligare 1
Vi har genomfört denna grundläggande idé om rekursion.
>> Nu, i det här fallet det verkligen inte lösa ett problem
någon mer effektivt då vi har sett hittills.
Men tänk om de algoritmer vi gjort på scenen hittills.
Vi hade 8 papperslappar på tavlan,
på video när Sean letade efter numret 7, och vad gjorde han egentligen gjort?
Tja, gjorde han inte någon form av söndra och härska.
Han gjorde inte någon form av rekursion.
Snarare gjorde han just detta linjära algoritm.
Men när vi introducerade idén av sorterade siffror på scenen lever förra veckan
sedan hade vi denna instinkt att gå till mitten,
då vi hade en mindre lista med storlek 4 eller annan lista över storlek 4,
och sedan hade vi exakt samma problem, så vi upprepade upprepas upprepas.
Med andra ord, recursed vi.
Tack så mycket till våra 3 volontärer här för att visa rekursion med oss.
>> Låt oss se om vi inte kan göra det nu lite mer konkret,
lösa ett problem som vi återigen kunde göra ganska enkelt,
men vi kommer att använda det som en språngbräda för att genomföra denna grundläggande idé.
Om jag vill beräkna summan av en massa siffror,
till exempel om du passerar i nummer 3,
Jag vill ge dig värdet av Sigma 3,
så summan av 3 + 2 + 1 + 0.
Jag vill komma tillbaka svaret 6,
så vi genomföra denna sigma funktion, denna summering funktion
att återigen tar i indata och returnerar sedan summan
av detta antal hela vägen ner till 0.
Vi kan göra detta ganska enkelt, eller hur?
Vi kan göra detta med någon form av looping struktur,
så låt mig gå vidare och få detta igång.
>> Inkludera stdio.h.
Låt mig få mig in i huvud att arbeta med här.
Låt oss spara detta som sigma.c.
Sen ska jag gå in här, och jag kommer att förklara en int n,
och jag ska göra följande medan användaren inte samarbetar.
Medan användaren inte har gett mig ett positivt tal
Låt mig gå vidare och få dem för n = getInt,
och låt mig ge dem några instruktioner om vad de ska göra,
så printf ("positivt heltal please").
Bara något relativt enkelt som detta så att när vi träffar ledningen 14
Vi har nu ett positivt heltal förmodligen i n.
>> Nu ska vi göra något med den.
Låt mig gå vidare och beräkna summan, så int sum = sigma (n).
Sigma är bara summering, så jag bara skriva det på avancerad vägen.
Vi ska bara kalla det sigma där.
Det är summan, och nu ska jag skriva ut resultatet,
printf ("Summan är% d \ n", summa).
Och sedan ska jag tillbaka 0 för bra åtgärd.
Vi har gjort allt det här programmet kräver förutom den intressanta delen,
vilket är att faktiskt genomföra sigma funktion.
>> Låt mig gå ner hit till botten, och låt mig förklara funktionen Sigma.
Det måste ta en variabel som är av typen heltal,
och vad datatyp vill jag återvända förmodligen från Sigma?
Int för att jag vill att det ska matcha mina förväntningar på linje 15.
Här inne Låt mig gå vidare och genomföra detta
på ett ganska enkelt sätt.
>> Låt oss gå vidare och säga int summa = 0,
och nu ska jag gå har lite för slinga här
det kommer att säga något sådant,
for (int i = 0; I <= antal, i + +) summa + = jag.
Och då ska jag återvända summan.
Jag kunde ha genomfört detta i ett antal olika sätt.
Jag kunde ha använt en while-slinga.
Jag kunde ha hoppat med summan variabeln om jag verkligen ville,
men kort sagt, har vi bara en funktion som om jag inte goof förklarar summa är 0.
Sen itererar från 0 till upp genom numret,
och på varje iteration det tillägger att nuvarande värde till summan och återgår sedan summan.
>> Nu finns det en liten optimering här.
Detta är förmodligen en bortkastad steg, men så var det. Det är bra för nu.
Vi är åtminstone vara noggrann och gå 0 hela vägen på upp.
Inte mycket hårt och ganska enkelt,
men det visar sig att med Sigma funktion vi har samma möjligheter
som vi gjorde här på scenen.
På scen vi räknade hur många människor var bredvid mig,
men i stället om vi ville räkna antalet 3 + 2 + 1
ner till 0 vi kunde på samma sätt punt till en funktion
att jag istället beskriva som rekursiv.
Här låt oss göra en snabb förstånd kontrollera och se till att jag inte goof.
>> Jag vet att det finns minst en sak i det här programmet som jag gjorde fel.
När jag slog in kommer jag att få någon form av yelling på mig?
Vad ska jag bli skrek åt om?
Ja, jag glömde prototypen, så jag använder en funktion som kallas sigma på linje 15,
men det är inte deklarerat förrän ledningen 22, så jag bäst proaktivt gå upp här
och förklara en prototyp, och jag ska säga int sigma (int antal), och det är det.
Det genomförs i botten.
>> Eller annat sätt jag skulle kunna lösa detta,
Jag kunde flytta funktionen uppe, vilket inte är dåligt,
men åtminstone när programmen börjar bli långa, uppriktigt sagt,
Jag tror att det finns ett värde i att alltid ha stora upptill
så att du i läsaren kan öppna filen och sedan omedelbart se
vad programmet gör utan att behöva söka igenom det
söker det huvudsakliga funktion.
Låt oss gå ner till min terminalfönster här, försöka göra Sigma gör Sigma,
och jag skruvade upp här också.
Implicit deklaration av funktion getInt betyder att jag har glömt att göra vad?
[Ohörbart-student]
Bra, så uppenbarligen ett vanligt misstag, så låt oss sätta upp detta här,
cs50.h, och nu ska vi gå tillbaka till min terminalfönster.
>> Jag rensa skärmen, och jag ska köra gör Sigma.
Det verkar ha sammanställt. Låt mig nu kör sigma.
Jag skriver i nummer 3, och jag fick 6, så inte en rigorös kontroll,
men åtminstone det verkar fungera vid första anblicken, men nu ska vi slita isär,
och låt oss utnyttja faktiskt idén om rekursion, igen,
på ett mycket enkelt sammanhang så att i ett par veckor
när vi börjar utforska snyggare datastrukturer än arrayer
Vi har ett annat verktyg i verktygslådan som man kan
manipulera dessa datastrukturer som vi får se.
Detta är den iterativa tillvägagångssätt loop synsätt.
>> Låt mig i stället nu göra detta.
Låt mig i stället säga att summan av antalet
ner till 0 är egentligen samma sak som
nummer + sigma (nummer - 1).
Med andra ord, precis som på scenen jag punted till varje människor bredvid mig,
och de i sin tur hålls punting tills vi slutligen bottnade på Willy,
som var tvungen att återvända en hårdkodad svar som 0.
Här nu är vi på samma sätt punting till Sigma
samma funktion som kallades ursprungligen, men det viktigaste insikten här
är att vi inte kallar Sigma identiskt.
Vi är inte passerar i n.
Vi tydligt passerar i antal - 1,
så en något mindre problem, något mindre problem.
>> Tyvärr är detta inte riktigt en lösning ännu, och innan vi fixa
vad som kan hoppa ut så självklart på några av er
Låt mig gå vidare och köra göra.
Det verkar att sammanställa okej.
Låt mig köra Sigma med 6.
Hoppsan, låt mig köra Sigma med 6.
Vi har sett det här förut, om än oavsiktligt förra gången också.
Varför fick jag denna kryptiska segmenteringsfel? Ja.
[Ohörbart-student]
Det finns ingen basfall, och mer specifikt, vad hände antagligen?
Detta är ett symptom på vad beteende?
Säg det lite högre.
[Ohörbart-student]
Det är en oändlig slinga effektivt och problemet med oändliga slingor
när de omfattar rekursion i detta fall en funktion som kallar sig,
vad som händer varje gång du ringer en funktion?
Jo, tänker tillbaka på hur vi lade ut minnet i en dator.
Vi sade att det finns denna bit av minnet som kallas stapeln som är längst ner,
och varje gång du ringer en funktion lite mer minne får sätta
på denna så kallade stacken med den funktionen lokala variabler eller parametrar,
så om Sigma kallar sigma samtal Sigma kallar Sigma
kallar Sigma där gör denna historia slut?
>> Tja, det så småningom överskridanden den totala mängden
minne som du har tillgång till din dator.
Du överskridande det segment som du ska hålla sig inom,
och du får denna segmenteringsfel, dumpade kärna,
och vad kärnan dumpade betyder är att jag nu har en fil som heter kärna
vilket är en fil som innehåller nollor och ettor
som faktiskt i framtiden kommer att vara diagnostiskt användbar.
Om det inte är uppenbart att du var ditt fel är
kan du faktiskt göra lite kriminalteknisk analys, så att säga,
på denna kärna dumpfilen, vilket återigen bara en massa nollor och ettor
som representerar huvudsakligen läget i ditt program i minnet
det ögonblick den kraschade på detta sätt.
>> Den fixa här är att vi inte bara kan blint återvända Sigma,
Antalet + Sigma en något mindre problem.
Vi måste ha någon form av bas fallet här,
och vad bör basfallet förmodligen?
[Ohörbart-student]
Okej, så länge antalet är positivt att vi borde faktiskt returnera denna,
eller annorlunda uttryckt, om antalet är, säg, <= till 0
vet du vad, jag ska gå vidare och returnera 0,
ungefär som Willy gjorde, och annat, jag ska gå vidare
och returnera detta, så det är inte så mycket kortare
än den iterativa version som vi piskade upp först använda en for-slinga,
men märker att det finns denna typ av elegans till det.
Istället för att returnera ett visst antal och utför allt detta matte
och lägga upp saker med lokala variabler
du istället säger "Okej, om detta är en super lätt problem,
som antalet är <0, låt mig genast tillbaka 0. "
>> Vi kommer inte att bry stödja negativa tal,
så jag ska hård kod värdet 0.
Men annars, för att genomföra denna idé om att summera
alla dessa siffror tillsammans kan du effektivt ta en liten bit
ur problemet, ungefär som vi gjorde här på scenen,
då punt resten av problemet till nästa person,
men i detta fall nästa person är själv.
Det är en samma namn funktion.
Bara ge det en mindre och mindre och mindre problem varje gång,
och även om vi har inte riktigt formaliserade saker i koden här
Detta är exakt vad som händer i veckan 0 med telefonboken.
Detta är exakt vad som hände i senaste veckorna med Sean
och med våra demonstrationer för att söka efter nummer.
Det tar ett problem och dela det igen och igen.
>> Med andra ord, det finns ett sätt nu att översätta
denna verkliga världen konstruktion, denna högre nivå konstruktion
av söndra och härska och göra något och om igen
i kod, så detta är något vi kommer att se igen med tiden.
Nu, som en sidoreplik, om du är ny till rekursion bör du åtminstone förstår nu
varför detta är roligt.
Jag ska gå till google.com,
och jag kommer att söka efter några tips och tricks om rekursion skriver.
Tala om för personen bredvid dig om de inte skrattar just nu.
Menade du rekursion?
Menade du-ah, där vi går.
Okej, nu att resten av alla.
Lite påskägg inbäddad någonstans där i Google.
Som en sidoreplik, en av länkarna som vi sätter på kursens hemsida
för idag är just detta nät av olika sortering algoritmer,
av vilka vi tittade på i förra veckan, men vad är trevligt om denna visualisering
som du försöker att slå dig runt olika saker relaterade till algoritmer
vet att du kan mycket enkelt nu börja med olika typer av insatser.
Ingångarna vände alla ingångar mesta sorteras, ingångarna slumpmässigt och så vidare.
När du försöker igen, urskilja dessa saker i ditt sinne
inse att denna URL på kursens hemsida på Föreläsningar sidan
kan hjälpa dig anledning genom några av dem.
>> Idag har vi äntligen lösa detta problem från en tid tillbaka,
vilket var att denna swap funktionen fungerade bara inte,
och vad som var det grundläggande problemet med denna funktion swap,
vars mål var återigen byta ett värde här och här
så att detta händer?
Detta faktiskt inte fungerar. Varför?
Ja.
[Ohörbart-student]
Exakt, förklaringen till detta bugginess
bara var att när du ringer funktioner i C
och dessa funktioner tar argument, som a och b här,
du passerar i en kopia av det värde som du ger till den funktionen.
Du är inte tillhandahåller de ursprungliga värdena själva,
så vi såg detta i samband med buggyc,
buggy3.c, som såg lite ut så här.
>> Minns att vi hade x och y initieras till 1 och 2, respektive.
Vi skrivs sedan ut vad de var.
Jag hävdade då att jag byta dem genom att ringa byte av x, y.
Men problemet var att byta fungerade,
men bara inom ramen för swappen fungerar själv.
Så snart vi träffar ledningen 40 de bytt värden
kastades bort och så ingenting
i den ursprungliga funktionen viktigaste var faktiskt förändrats alls,
så om du tror då vad detta ser ut när det gäller vårt minne
om denna vänster sida av kortet representerar-
och jag ska göra mitt bästa för att alla ska se detta, om det vänstra sidan av brädet
representerar exempelvis ditt RAM-minne, och stapeln kommer att växa på upp detta sätt,
och vi kallar en funktion som huvud, och viktigaste har 2 lokala variabler, x och y,
låt oss beskriva dem som x här, och låt oss beskriva dessa som y här,
och låt oss sätta i värdena 1 och 2, så detta här är stora,
och när huvudsakliga anropar swap-funktionen i operativsystemet
ger swap-funktionen en egen sträng minne på stacken,
sin egen ram på stacken, så att säga.
Det fördelar också 32 bitar för dessa Ints.
Det händer att kalla dem A och B, men det är helt godtycklig.
Det kunde ha kallat dem vad det vill, men vad händer när huvud
samtal swap är det tar detta 1, sätter en kopia där sätter en kopia där.
>> Det finns 1 annan lokal variabel i swap, men kallas vad? >> Tmp.
Tmp, så låt mig ge mig ytterligare 32 bitar här,
och vad gjorde jag i den här funktionen?
Jag sa int tmp får en, så en har 1, så jag gjorde det när vi senast spelade med detta exempel.
Sedan en blir B, så b är 2, så nu blir detta 2,
och nu B får temp, så temp är 1,
så nu B blir detta.
Det är bra. Det fungerade.
Men sedan så snart som funktionen returnerar
swap minne försvinner effektivt så att den kan återanvändas
av någon annan funktion i framtiden, och viktigaste är naturligtvis helt oförändrad.
Vi behöver ett sätt att i grunden lösa detta problem,
och idag ska vi äntligen har ett sätt att göra detta innebär att
Vi kan införa något som kallas en pekare.
Det visar sig att vi kan lösa detta problem
inte genom passage i kopior av x-och y
utan genom att i vad, tror du, att byta funktion?
Ja, hur är adressen?
Vi har inte riktigt pratat om adresser i stor detalj,
men om denna tavlan är min dators minne
Vi skulle säkert börja numreringen byte i min RAM
och säga att detta är byte # 1, är detta byte # 2, byte # 3,
byte # 4, byte # ... 2 miljarder om jag har 2 gigabyte RAM-minne,
så vi kan säkert komma med några godtyckliga numreringsschema
för alla enskilda bitgrupper i datorns minne.
>> Vad händer om istället när jag pendling
snarare än pass i kopior av x-och y
varför inte jag gå istället in adressen till X här,
adress y här, i huvudsak postadress
av x och y, eftersom byta då, om han informeras
av adressen i minnet av x och y,
sedan byta om vi tränade honom lite,
Han skulle kunna köra till den adressen, så att säga,
x, och ändra antalet där, sedan köra till adressen y,
ändra antalet där, även när det inte faktiskt få kopior av dessa värden själv,
så även om vi talade om detta som främsta minne
och detta som swap minne de mäktiga och den farliga delen av C
är att varje funktion kan röra minnet någonstans i datorn,
och detta är kraftfull i att du kan göra mycket fina saker med datorprogram i C.
Detta är farligt eftersom du kan också skruva upp mycket lätt.
I själva verket, till en av de vanligaste sätten för program dessa dagar utnyttjas
fortfarande är för en programmerare inte inse
att han eller hon tillåter en data
skrivas på en plats i minnet som inte var avsett.
>> Till exempel, förklarar han eller hon en rad storlek 10
men sedan råkar försöker sätta 11 byte i den mängd minne,
och du börjar röra delar av minnet som inte längre är giltiga.
Bara för att kontextuella detta kan en del av er vet att
programvara frågar ofta du serienummer eller nycklar registrering,
Photoshop och Word och program som detta.
Det finns sprickor, som några av er vet, på nätet där du kan köra ett litet program,
och voila, inget mer begäran om ett serienummer.
Hur det fungerar?
I många fall är dessa saker är helt enkelt finna i datorerna
textsegment i datorns faktiska nollor och ettor
var är den funktionen där serienumret begärs,
och du skriver det utrymmet, eller medan programmet körs
Du kan räkna ut var nyckeln faktiskt lagras
med något som kallas en debugger, och du kan knäcka programvara på det sättet.
Detta är inte att säga att detta är vårt mål för de närmaste dagarna,
men det har mycket verkliga konsekvenser.
Att en råkar involvera stöld av mjukvara,
men det finns också äventyrande av hela maskiner.
>> Faktum är att när webbsidor dessa dagar utnyttjas
och äventyras och data läckt och lösenord stjäls
detta mycket ofta avser dålig förvaltning av ett minne,
eller, när det gäller databaser, underlåtenhet förutse
kontradiktoriskt ingång, så mer om detta under de kommande veckorna,
men nu bara en förhandstitt på den typ av skador som du kan göra
genom att inte riktigt förstå hur saker och ting fungerar under huven.
Låt oss gå om att förstå varför detta är bruten
med ett verktyg som kommer att bli mer och mer användbar
som våra program blir mer komplexa.
Hittills när du har haft en bugg i programmet
Hur har du gått om felsökning det?
Vad har din teknik varit hittills, oavsett undervisas av din TF
eller bara självlärd?
[Student] printf.
Printf så printf har förmodligen varit din vän i att om du vill se
vad som händer inne i ditt program
du sätter bara printf här, printf här printf här.
Då du kör det, och du får en hel massa saker på skärmen
som du kan använda för att sedan sluta sig till vad som faktiskt är fel i programmet.
>> Printf tenderar att vara en mycket kraftfull sak,
men det är en mycket manuell process.
Du måste sätta ett printf här, en printf här,
och om du lägger den i en slinga så kan du få 100 rader
av produktionen som du sedan måste sålla bland.
Det är inte en mycket användarvänlig och interaktiv mekanism för felsökning program,
men tack och lov finns det alternativ.
Det finns ett program, till exempel, som kallas GDB, GNU Debugger,
som är lite mystisk i hur du använder den.
Det är lite komplicerat, men ärligt talat,
Detta är en av de saker där om du in i denna och nästa vecka
den extra timme för att förstå något som GDB
det kommer att spara dig förmodligen tiotals timmar på lång sikt,
Så med det, låt mig ge er en teaser på hur det här fungerar.
>> Jag är i mitt terminalfönster.
Låt mig gå vidare och sammanställa detta program, buggy3.
Det är redan aktuell.
Låt mig köra det precis som vi gjorde för ett tag sedan, och faktiskt, det brutna.
Men varför är detta? Jag kanske skruvas upp swap-funktionen.
Kanske är det a och b. Jag är inte riktigt flytta dem runt på rätt sätt.
Låt mig gå vidare och göra det.
Snarare än att bara springa buggy3 låt mig istället köra programmet GDB,
och jag ska berätta det för att köra buggy3,
och jag ska inkludera en argumentation kommandorad,-tui,
och vi sätta detta i framtida problem på spec att påminna.
Och nu detta svartvita gränssnitt dök upp som, återigen,
är lite överväldigande i början eftersom det är allt det här
garantiinformation här nere, men åtminstone det är något bekant.
I den övre delen av fönstret är min faktiska koden,
och om jag bläddra upp här Låt mig rulla till toppen av min fil,
och faktiskt, det finns buggy3.c och meddelande längst ner i fönstret
Jag har denna GDB prompten.
>> Detta är inte samma sak som min normala John Harvard prompten.
Detta är en fråga som kommer att tillåta mig att styra GDB.
GDB är en debugger.
En debugger är ett program som låter dig gå igenom
genomförande av programmet rad för rad för rad,
vägen gör något som du vill att programmet,
även ringa funktioner eller söker, ännu viktigare,
på olika variabla värden.
Låt oss gå vidare och göra det.
Jag ska gå vidare och skriva in körning på GDB s snabba,
så märker längst ner till vänster på skärmen jag har skrivit springa,
och jag har in hit, och vad gjorde det då?
Det körde bokstavligen mitt program, men jag såg faktiskt mycket gå på här
eftersom jag inte har faktiskt sagt debugger
att pausa vid en viss tidpunkt.
Bara skriva körning kör programmet.
Jag faktiskt inte se någonting. Jag kan inte manipulera den.
>> Istället Låt mig göra det här.
Vid denna GDB prompten Låt mig istället skriver break, ange.
Det är inte vad jag menade att skriva.
Låt oss i stället skriver break.
Med andra ord vill jag ställa något som kallas en brytpunkt,
som träffande heter eftersom det kommer att bryta eller pausa
genomförande av programmet på den platsen.
Main är namnet på min funktion.
Observera att GDB är ganska smart.
Det räknat ut att huvud råkar börja ungefär vid linjen 18
av buggy3.c och sedan märker här uppe till vänster
b + ligger precis intill rad 18.
Det är påminna mig om att jag har en brytpunkt på linje 18.
Den här gången när jag skriver springa, jag ska köra mitt program
tills den träffar den brytpunkten,
så att programmet gör en paus för mig på rad 18.
Nu kör vi, spring.
Ingenting verkar ha hänt, men meddelande nere till vänster
start program buggy3, brytpunkt 1 i main på buggy3.c linje 18.
Vad kan jag göra nu?
>> Märker jag kan börja skriva saker som utskrift,
inte printf, skriva ut X, och nu det är konstigt.
$ 1 är bara en kuriositet, som vi får se
varje gång du skriver ut något du får en ny $ värde.
Det är så att du kan hänvisa till tidigare värden skull,
men nu vad utskrift säger mig är att värdet av x vid denna punkt i berättelsen
är tydligen 134.514.032.
Vad? Var kom det även komma från?
[Ohörbart-student]
I själva verket är detta vad vi kallar ett skräp värde, och vi har inte pratat om det här ännu,
men anledningen till att du initierar variabler
är uppenbarligen så att de har något värde som du vill att de ska ha.
Men fångsten ihåg att du kan deklarera variabler
som jag gjorde för en stund sedan i min sigma exempel
utan att faktiskt ge dem ett värde.
Minns vad jag gjorde över här i Sigma.
Jag förklarade n men vilket värde gav jag den?
Ingen, eftersom jag visste att under de närmaste raderna
GetInt skulle ta hand om problemet med att sätta ett värde inuti n.
>> Men vid denna punkt i berättelsen om linjen 11
och linje 12 och linje 13 och linje 14
i alla de flera rader vad är värdet på n?
I C du bara vet inte.
Det är i allmänhet lite skräp värde, några helt slumpmässigt nummer
som är kvar i huvudsak från några tidigare funktion
ha körts så ditt program körs
ihåg att funktionen blir funktionen, funktion, funktion.
Alla dessa ramar får sätta på minnet, och sedan de funktioner tillbaka,
och precis som jag föreslog med radergummi deras minne så småningom återanvänds.
Tja, det råkar vara så att denna variabel x i detta program
verkar ha innehållit något skräp värde som 134514032
från någon tidigare funktion, inte en som jag skrev.
Det kan vara något som kommer effektivt med operativsystemet,
någon funktion under huven.
>> Okej, det är bra, men låt oss nu gå vidare till nästa rad.
Om jag skriver "nästa" på min GDB snabbt och jag slog in,
märker att lyfta flyttas ner till linjen 19,
men den logiska innebörden är att linje 18
har nu avslutat köra, så om jag återigen skriver "print x"
Jag skulle nu se 1, och faktiskt, det gör jag.
Återigen är $ grejer ett sätt att GDB påminner dig
vad historia utskrifter är att du har gjort.
Låt mig gå vidare och skriva ut y, och faktiskt, y någon galen värde samt,
men no big deal eftersom i linje 19 är vi på väg att tilldela den
värdet 2, så låt mig skriva "nästa" igen.
Och nu är vi på den printf raden.
Låt mig göra tryckta x.
Låt mig göra utskriften y.. Ärligt talat, jag börjar bli lite trött att skriva detta.
Låt mig istället skriva "skärm x" och "skärm y"
och nu varje gång jag skriver ett kommando i framtiden
Jag kommer att påminnas om vad som är x och y, vad är x och y, vad är x och y.
>> Jag kan också, som en sidoreplik, skriv "info lokalbefolkningen."
Info är ett speciellt kommando.
Lokalbefolkningen betyder det visar mig de lokala variablerna.
Bara i fall jag glömmer eller det är en galen, komplicerad funktion
att jag eller någon annan skrev info lokalbefolkningen kommer att berätta
vad är alla lokala variabler inuti denna lokal funktion
som du kan bry sig om om du vill rota.
Nu printf är på väg att genomföra, så låt mig gå vidare och bara typ "nästa".
Eftersom vi är i denna miljö vi inte faktiskt ser det
exekvera här nere, men märker det börjar bli lite sargade här.
Men märker det övergripande skärmen där,
så det är inte ett perfekt program här, men det är okej eftersom jag kan alltid rota runt
med tryck om jag vill.
>> Låt mig skriva nästa gång, och nu här är den intressanta delen.
Vid denna punkt i berättelsen y är 2, och x är 1,
som föreslås här, och igen,
Anledningen till detta är automatiskt visar nu att jag använde kommandot
display X och Y visas, så nu jag skriver nästa
i teorin x och y bör bli bytas.
Nu vet vi redan att inte kommer att vara fallet,
men vi får se på ett ögonblick hur vi kan dyka djupare för att räkna ut varför det är sant.
Nästa, och tyvärr är y fortfarande 2 och x är fortfarande 1, och jag kan bekräfta så mycket.
Skriv X, tryck y.
I själva verket har ingen swapping faktiskt hände, så låt oss börja här över.
Tydligt swap är bruten.
Låt oss istället skriva "kör" igen.
Låt mig säga ja, jag vill starta om den från början anger.
>> Nu är jag tillbaka upp på rad 18.
Notera nu x och y är skräp värden igen.
Nästa, nästa, nästa, nästa.
Om jag får uttråkad jag kan också bara skriva n. för nästa.
Du kan förkorta det till kortast möjliga sekvensen av tecken.
Pendla nu bruten.
Låt oss dyka i, så istället för att skriva nästa,
nu ska jag skriva steg så att jag kliva in i denna funktion
så att jag kan gå igenom det, så jag slog steg och ange.
Observera att belysa hoppar ner lägre i mitt program till linje 36.
Nu vad är de lokala variablerna?
Info lokalbefolkningen.
Inget riktigt än eftersom vi inte har fått till den raden,
så låt oss gå vidare och säga "nästa".
Nu verkar vi ha tmp, skriva ut tmp.
Garbage värde, eller hur? Jag tror det.
Vad sägs om ut en, skriv ut B, 1 och 2?
I ett ögonblick, så fort jag skriver nästa gång
TMP kommer att ta på ett värde av 1, förhoppningsvis,
eftersom TMP kommer att tilldelas värdet av en.
>> Nu låt oss göra ut en, skriv ut B,
men nu ut tmp, och det är verkligen 1.
Låt mig göra härnäst. Låt mig göra härnäst.
Jag är klar swap-funktionen.
Jag är fortfarande inne i den i linje 40, så låt mig skriva ut en,
print b och jag bryr mig inte vad TMP är.
Det ser ut som swap är korrekt när det gäller att byta a och b.
Men om jag nu skriver nästa, hoppa jag tillbaka till rad 25,
och naturligtvis, om jag skriver i x-och skriv ut y
de är fortfarande oförändrad, så vi har inte åtgärdat problemet.
Men diagnostiskt nu kanske med detta GDB programmet
Vi har åtminstone fått ett steg närmare att förstå
vad som händer fel utan att strö vår kod genom att sätta en printf här,
printf här printf här och sedan köra det om och om igen
försöker lista ut vad som går fel.
>> Jag ska gå vidare och avsluta ur detta helt och hållet med sluta.
Det kommer att sedan säga, "Quit egentligen?" Ja.
Nu är jag tillbaka på min normala ledtexten och jag är klar med GDB.
Som en sidoreplik, behöver du inte använda den här-tui flagga.
Faktum är att om du utelämnar det får du i huvudsak den nedre halvan av skärmen.
Om jag skriver så break och sedan köra
Jag kan fortfarande köra mitt program, men vad det kommer att göra är textuellt
bara visa mig den aktuella raden en i taget.
The-TUI, text användargränssnitt,
bara visar dig mer av programmet på en gång, vilket är nog lite begreppsmässigt enklare.
Men i själva verket kan jag göra precis bredvid, nästa, nästa,
och jag kommer att se en rad i taget, och om jag verkligen vill se vad som händer
Jag kan skriva lista och se en massa närliggande linjer.
>> Det finns en video som vi har bett att du tittar på problemet sätter 3
där Nate täcker några av de invecklade GDB,
och detta är en av dessa saker, ärligt, där några icke-triviala andel av dig
kommer aldrig röra GDB, och det kommer att vara en dålig sak
eftersom bokstavligen kommer du att sluta spendera mer tid senare den här terminen
jagar insekter så skulle du om du sätter i den halvtimme / timme
denna vecka och nästa lärande att bli bekant med GDB.
Printf var din vän.
GDB bör nu vara din vän.
>> Eventuella frågor om GDB?
Och här är en snabb lista över några av de mest kraftfulla och användbara kommandon.
Ja. >> Kan du skriva ut en sträng?
Kan du skriva ut en sträng? Absolut.
Det behöver inte bara vara heltal.
Om en variabel s är en sträng skriv bara i tryck ar.
Det kommer att visa dig vad som strängvariabel är.
[Ohörbart-student]
Det kommer att ge dig adressen och strängen själv.
Det kommer att visa er båda.
Och en sista sak, bara för att de är bra att veta också.
Bakåtspårning och ram, låt mig dyka in i denna en sista gång,
exakt samma program med GDB.
Låt mig gå vidare och köra textversion användargränssnittet,
break.
Låt mig gå vidare och köra igen. Här är jag.
Nu låt mig gå nästa, nästa, nästa, nästa, nästa, steg anger.
>> Och nu antar jag nu swap medvetet, men jag är som "Fan, vad var värdet av x?"
Jag kan inte göra X längre.
Jag kan inte göra y eftersom de inte är i omfattning.
De är inte i sitt sammanhang, men inga problem.
Jag kan skriva bakåtspårning.
Det visar mig alla de funktioner som har utförts fram till denna tidpunkt.
Observera att en på botten, huvud, ställer upp med huvud
vara på undersidan av vår bild här.
Det faktum att swap är ovanför rader med swap är över det i minnet här,
och om jag vill komma tillbaka till huvudgruppen tillfälligt kan jag säga "ram".
Vilket nummer? Main är ram nummer 1.
Jag ska gå vidare och säga "ram 1."
>> Nu är jag tillbaka i main, och jag kan skriva ut X, och jag kan skriva ut y,
men jag kan inte skriva ut a eller b.
Men jag kan om jag säger, "Okej, vänta en minut. Där var swappen?"
Låt mig gå vidare och säga "ram 0."
Nu är jag tillbaka där jag vill vara, och som en sidoreplik
Det finns andra kommandon också, som om du verkligen får uttråkad skriva nästa, nästa, nästa, nästa,
Du kan generellt säga saker som "nästa 10" och som kommer att gå igenom de kommande 10 rader.
Du kan också skriva "fortsätt" när du verkligen få nog av stega igenom den.
Fortsätt att köra ditt program utan avbrott tills den träffar en annan brytpunkt,
antingen i en slinga eller längre ner i programmet.
>> I det här fallet har vi fortsatt till slutet, och programmet avslutades normalt.
Det är ett fint sätt, sämre process.
Bara ditt program avslutades normalt.
Mer om det i videon och felsökning sessioner framöver.
Det var en hel del.
Låt oss ta vår 5-minuters paus här, och vi ska återkomma med structs och filer.
>> Om du har dykt in i denna veckas pset redan
du vet att vi använder i distributionen koden,
den källkod som vi ger till dig som en startpunkt, en del nya tekniker.
I synnerhet introducerade vi den nya sökord som kallas struct för struktur,
så att vi kan skapa anpassade variabler slag.
Vi införde också begreppet fil-I / O, fil ingång och utgång,
och det är så att vi kan spara tillståndet
av din Scramble styrelsen att en fil på skiva
så att undervisningen stipendiater och jag kan förstå
vad som händer på insidan av ditt program utan att manuellt behöva spela
dussintals spel av Scramble.
Vi kan göra detta mer automatedly.
>> Denna idé om en struktur löser ett ganska övertygande problem.
Antag att vi vill genomföra något program
som håller på något sätt reda på information om studenter,
och studenter kan ha, till exempel ett ID, ett namn
och ett hus på en plats som Harvard, så dessa är 3 bitar av information
Vi vill behålla runt, så låt mig gå vidare och börja skriva ett litet program här,
omfatta stdio.h.
Låt mig göra inkludera cs50.h.
Och sedan starta min huvudsakliga funktion.
Jag kommer inte bry sig om några kommandoradsargument,
och här vill jag ha en student, så jag kommer att säga
en student har ett namn, så jag kommer att säga "sträng namn."
Sen ska jag säga en elev har också ett ID, så int id,
och en elev har ett hus, så jag också kommer att säga "sträng hus."
Då ska jag beställa dessa lite mer rent så här.
Okej, nu har jag 3 variabler som man kan representera en student, så "en student".
>> Och nu vill jag fylla dessa värden, så låt mig gå vidare och säga något i stil
"Id = 123."
Namn kommer att få David.
Låt oss säga hus kommer att få Mather,
och då ska jag göra något godtyckligt som printf ("% s,
vars ID är% d, bor i% s.
Och nu, vad jag vill koppla in här, den ena efter den andra?
Namn, ID, hus, avkastning 0.
Okej, om jag skruvas upp någonstans här
Jag tror att vi har en ganska bra program som lagrar en elev.
Naturligtvis är det inte så intressant. Vad händer om jag vill ha 2 studenter?
Det är ingen stor sak. Jag kan stödja 2 personer.
Låt mig gå vidare och belysa detta och gå ner hit,
och jag kan säga "id = 456" för någon som Rob som bor i Kirkland.
>> Okej, vänta, men jag kan inte kalla dem samma sak,
och det ser ut som jag kommer att behöva kopiera detta,
så låt mig säga att dessa kommer att vara Davids variabler,
och låt mig få lite kopior av dessa för Rob.
Vi ringer dessa Rob men detta kommer inte att fungera nu
eftersom jag har-vänta, låt oss ändra mig ID1, NAME1 och House1.
Rob blir 2, 2.
Jag måste ändra detta här, här, här, här, här, här.
Vänta, hur Tommy? Låt oss göra det igen.
Självklart om du fortfarande tror att det är ett bra sätt att göra detta, det är inte,
så kopiera / klistra dåligt.
Men vi löste en vecka sedan.
>> Vad var vår lösning när vi ville ha flera instanser av samma datatyp?
[Studenter] En array.
En array, så låt mig försöka städa upp det här.
Låt mig göra några rum för mig själv på toppen, och låt mig istället göra det här.
Vi ringer dessa människor, och i stället ska jag säga "int id,"
och jag kommer att stödja 3 av oss för nu.
Jag kommer att säga "strängnamn," och jag stöder 3 av oss,
och då ska jag säga "string hus", och jag kommer att stödja 3 av oss.
Nu här i stället för David att få sina egna lokala variabler
Vi kan bli av dem.
Det känns bra att vi städa upp detta.
Jag kan då säga David kommer att bli [0] och namn [0]
och hus [0].
Och sedan Rob vi liknande kan spara på detta.
Låt oss sätta detta här nere, så han kommer att godtyckligt bli id ​​[1].
Han kommer att bli namn [1],
och sedan slutligen, hus [1].
>> Fortfarande lite tråkiga, och nu har jag att lista ut,
så låt oss säga "namn [0], id [0], hus [0],
och låt oss pluralize här.
Ids, ids, ids.
Och igen, jag gör det, så igen, jag tillgripa redan kopiera / klistra igen,
så oddsen är att det finns en annan lösning här.
Jag kan nog städa upp ytterligare med en ögla eller något liknande,
så kort sagt, det är lite bättre men fortfarande känns
Jag tillgriper kopiera / klistra in, men även detta, jag hävdar,
är egentligen inte i grunden rätt lösning eftersom
vad händer om någon gång vi bestämmer du vad?
Vi har verkligen borde ha lagrar e-postadresser för David och Rob
och alla andra i det här programmet.
Vi bör också lagra telefonnummer.
Vi bör också lagra nödnummer kontakt.
Vi har alla dessa bitar av data som vi vill lagra,
så hur ska du gå om att göra det?
>> Du deklarerar en array upptill, och sedan manuellt lägga till
en e-postadress [0], e-postadress [1]
för David och Rob och så vidare.
Men det är egentligen bara ett antagande som ligger bakom denna konstruktion
att jag använder äran systemet att veta att
[I] i varje flera arrayer
bara så råkar hänvisa till samma person,
så [0] i ids är nummer 123,
och jag kommer att anta att namnen [0]
är samma person namn och hus [0]
är samma person hus och så vidare för alla de olika uppsättningarna som jag skapar.
Men märker att det inte finns någon grundläggande koppling
bland de 3 bitar av information, id, namn och hus,
även om företaget vi försöker modell i detta program är inte matriser.
Arrayer är just detta programmatiska sätt att göra detta.
Vad vi verkligen vill att modellera i vårt program är en person
som David, en person som Rob inuti vilken
eller inkapsling är ett namn och ID och ett hus.
>> Kan vi uttrycka något denna idé om inkapsling
där en person har ett ID, ett namn och ett hus
och inte ta till verkligen denna hacka där vi bara
lita på att fästet något
hänvisar till samma mänskliga enhet i var och en av dessa olika matriser?
Vi kan faktiskt göra detta.
Låt mig gå över huvud för nu, och låt mig skapa min egen datatyp
för riktigt första gången.
Vi använde den här tekniken i Scramble,
men här kommer jag att gå vidare och skapa en datatyp
och du vet vad, jag ska kalla det student eller person
och jag kommer att använda typedef för definiera en typ.
Jag ska säga att detta är en struktur,
och då denna struktur kommer att vara av typen elev, vi säger,
även om det är lite av den nu för mig.
Vi säger "int id."
Vi säger "sträng namn."
Då kommer vi att säga "sträng hus"
så nu i slutet av dessa få rader kod
Jag har just lärt klang att det finns
en datatyp förutom Ints, förutom strängar, förutom dubbel, förutom flyter.
>> Från och med denna tidpunkt linje 11, finns det nu en ny datatyp som kallas studenter,
och nu kan jag förklara en student variabel någonstans jag vill,
så låt mig rulla ner hit till människor.
Nu kan jag bli av med detta, och jag kan gå tillbaka till David hit,
och för David kan jag faktiskt säga att David,
Vi kan bokstavligen namnge variabeln efter mig,
kommer att vara av typen elev.
Detta kan se lite konstigt, men det är inte så annorlunda
från att förklara något som int eller en sträng eller en flottör.
Det råkar vara så att kallas elev nu
och om jag vill sätta något inuti denna struktur
Jag har nu att använda en ny bit syntax, men det är ganska enkelt,
david.id = 123, david.name = "David" i huvudstaden D,
och david.house = "Mather,"
och nu kan jag bli av med det här här.
Märker vi nu gjort om vår program verkligen ett mycket bättre sätt
i att nu vårt program speglar den verkliga världen.
>> Det finns en verklig uppfattning om en person eller en student.
Här har vi nu en C version av en person eller mer specifikt en student.
Inuti den personen är dessa relevanta egenskaper,
ID, namn och hus, så Rob blir i princip samma sak här nere,
så eleven rob, och nu rob.id = 456,
rob.name = "Rob."
Det faktum att variabeln heter Rob är typ av meningslöst.
Vi kunde ha kallat det x eller y eller z.
Vi döpte bara det Rob vara semantiskt konsekvent,
men egentligen namnet är inne i det området i sig,
så nu har jag det här.
Även detta inte känns som den bästa designen i att jag har svårt kodad David.
Jag har svårt kodad Rob.
Och jag har fortfarande att ta till vissa kopiera och klistra varje gång jag vill ha nya variabler.
Dessutom måste jag tydligen ge alla dessa variabler ett namn,
även om jag hade mycket hellre beskriva dessa variabler
mer allmänt som studerande.
>> Nu kan vi slå ihop de idéer som har arbetat bra för oss
och istället säga: "Vet du vad, ge mig en variabel som heter studenter,
och låt oss har det vara storlek 3 ", så nu kan jag förfina detta ytterligare,
bli av med manuellt deklarerade David,
och jag kan utan att säga något i stil med studenter [0] här.
Jag kan då säga studenter [0] här,
studenter [0] här, och så vidare, och jag kan gå runt
och städa upp det för Rob.
Jag kan också gå om nu kanske lägga till en slinga
och använda GetString och getInt att faktiskt få dessa värden från användaren.
Jag kunde gå om att lägga en konstant eftersom det är allmänt dålig praxis
till hårt kod några godtyckligt antal som 3 här
och sedan bara ihåg att du ska lägga mer än 3 studenter i den.
Det skulle förmodligen vara bättre att använda # define överst på min fil
och faktor som ut, så ja, låt mig gå vidare och generalisera detta.
>> Låt mig öppna upp ett exempel som är bland dagens
exempel i förväg, structs1.
Detta är en mer komplett program som använder # define upp här
och säger att vi kommer att ha 3 studenter som standard.
Här jag förklara en klass värd elever,
så ett klassrum med elever, och nu är jag använder en slinga
bara för att göra koden lite mer elegant, fylla klassen
med användarens input, så iterera från i = 0 på upp till studenter, vilket är 3.
Och då jag fråga användaren i denna version
vad är studentens id, och jag får det med getInt.
Vad är studentens namn, och då får jag det med GetString.
Vad är studentens hus? Jag får det med GetString.
Och därefter på botten här bestämde jag mig bara för att ändra
hur jag skriver ut dem och att faktiskt använda en slinga,
och som jag skriver?
Enligt kommentaren jag skriver någon i Mather,
och det är det så Rob och Tommy och så vidare-faktiskt Tommys i Mather.
Tommy och David skulle skrivas i detta fall, men hur detta fungerar?
Vi har inte sett denna funktion tidigare, men ta en gissning om vad detta innebär.
Jämför strängar.
>> Det är lite icke uppenbara hur jämförs strängar eftersom det visar sig
Om den returnerar 0 betyder strängarna är lika.
Om den returnerar en -1 betyder en kommer alfabetiskt före den andra,
och om den återvänder en som betyder den andra ord kommer alfabetiskt
innan den andra, och du kan titta på nätet eller på man-sidan
för att se exakt vilken väg som är vilken, men allt detta nu gör är det säger
om [i]. huset är lika med "Mather"
sedan gå vidare och skriva ut den och den är i Mather.
Men här är något vi inte har sett förut, och vi ska återkomma till detta.
Jag minns inte att någonsin behöva göra detta i någon av mina program.
Gratis är tydligen hänvisar till minne, frigöra minne,
men vad minnet jag befria tydligen i denna slinga längst ner i detta program?
Det ser ut som att jag frigör en persons namn
och en persons hus, men varför är det?
>> Det visar sig alla dessa veckor som du har använt GetString
Vi har typ av varit att införa en bugg i alla dina program.
GetString genom design allokerar minne så att den kan återgå till en sträng,
som David eller Rob, och du kan sedan göra vad du vill
med den strängen i ditt program eftersom vi har reserverat minne för dig.
Problemet är hela tiden varje gång du ringer getString
vi, författarna GetString, har begärt att operativsystemet
att ge oss lite RAM för denna sträng.
Ge oss lite RAM för detta nästa sträng.
Ge oss lite mer RAM-minne för nästa sträng.
Vad du är programmerare, har aldrig gjort
ger oss detta minne tillbaka,
så för dessa flera veckor alla program som du har skrivit
ha haft vad som kallas ett minne språng där de fortsätter att använda
mer och mer minne varje gång du ringer GetString, och det är bra.
Vi gör medvetet att under de första veckorna, eftersom det inte är så intressant
att oroa där strängen kommer ifrån.
Allt du vill är ordet Rob att komma tillbaka när användaren skriver in den
>> Men framåt vi nu måste börja bli mer sofistikerade om detta.
Varje gång vi allokera minne vi bättre så småningom lämna tillbaka den.
Annars i den verkliga världen på din Mac eller PC du kan ha ibland upplevt
symptom där datorn lamslagits småningom
eller dumma snurrande badboll är bara ockuperar datorns
Hela uppmärksamhet och du kan inte göra saker.
Det kan förklaras av ett antal buggar, men bland de möjliga fel
saker och ting kallas minnesläckor där någon som skrev att mjukvara
du använder inte ihåg att frigöra minne
att han eller hon frågade operativsystemet för,
inte använder GetString, eftersom det är en CS50 sak, men med liknande funktioner
som ber operativsystemet för minnet.
Om du eller de skruva upp och aldrig återvända som minne
ett symptom på det kan vara att ett program saktar och saktar och saktar ner
om du kommer ihåg att ringa gratis.
>> Vi ska återkomma till när och varför du skulle ringa gratis,
men låt oss gå vidare bara för bra åtgärd och försök köra detta program.
Detta kallades structs1 skriver.
Låt mig gå vidare och köra structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, och vi ser Davids i Mather, Tommys i Mather.
Detta är bara en liten sanity kontrollera att programmet fungerar.
Nu, tyvärr är det här programmet lite frustrerande att
Jag gjorde allt arbete, jag skrev i 9 olika strängar, tryck enter,
fick höra som var i Mather, men självklart visste jag vem som var i Mather redan eftersom jag skrev det.
Det skulle vara minst trevligt om detta program är mer som en databas
och det minns faktiskt vad jag har skrivit in
så jag aldrig mer behöver in dessa studiedokumentation.
Kanske är det som en registrarial system.
>> Vi kan göra detta med denna teknik som kallas fil I / O, fil ingång och utgång,
ett mycket allmänt sätt att säga när du vill läsa filer eller skriva filer
du kan göra detta med en viss uppsättning funktioner.
Låt mig gå vidare och öppna detta exempel structs2.c,
som är nästan identisk, men låt oss se vad det nu gör.
På toppen av filen förklarar jag en klass elever.
Jag fyller sedan klassen med användarens input,
så dessa kodrader är som exakt förr.
Sen om jag bläddra ner här jag skriver ut alla som är i Mather gillar godtyckligt tidigare,
men detta är en intressant nyhet.
Dessa rader kod är nya, och de introducerar något här,
Fil, alla mössor, och det har * i här.
Låt mig flytta hit, en * hit också.
>> Denna funktion har vi inte sett förut, fopen,
men det betyder filen öppen, så låt oss skumma igenom dessa,
och detta är något vi ska återkomma till i framtida psets,
men denna linje här öppnar huvudsak en fil som heter databas,
och det öppnar specifikt på ett sådant sätt att den kan göra vad på det?
[Ohörbart-student]
Just det, så "w" betyder bara att det talar operativsystemet
öppna filen så att jag kan skriva till den.
Jag vill inte läsa den. Jag vill inte bara titta på det.
Jag vill ändra det och lägga saker eventuellt till det,
och filen kommer att kallas databas.
Detta skulle kunna kallas något.
Detta kan vara database.txt. Detta skulle kunna vara. Db.
Detta kan vara ett ord som foo, men jag godtyckligt valde att namnge filen databasen.
Detta är en liten sanity check som vi ska återkomma till i detalj över tid,
Om fp, för fil pekare, inte lika NULL betyder allt är bra.
>> Lång historia kort, funktioner som fopen misslyckas ibland.
Kanske filen inte finns. Kanske du är ute skivutrymmet.
Kanske du inte har behörighet till mappen,
så om fopen returnerar null något dåligt hänt.
Omvänt, om fopen inte returnerar null allt är bra
och jag kan börja skriva till den här filen.
Här är ett nytt trick.
Detta är en for-slinga som är iteration över alla mina elever,
och detta ser så liknar vad vi har gjort tidigare,
men denna funktion är en kusin till printf kallas fprintf för fil printf,
och märker att det är annorlunda i bara 2 sätt.
Ett, börjar det med f istället för p,
men sedan dess första argument är tydligen vad?
[Studenter] Fil. >> Det är en fil.
Denna sak kallad fp, som vi kommer så småningom retas isär vad en fil pekare är,
men nu fp representerar helt enkelt filen som jag har öppnat,
så fprintf här säger skriva ut denna användarens ID till filen, inte på skärmen.
Skriv användarens namn till filen, inte på skärmen,
huset till filen, inte på skärmen, och sedan ner hit, naturligtvis,
stänger filen och sedan ner här gratis minnet.
>> Den enda skillnaden mellan denna version 2 och version 1
är införandet av fopen och denna fil med *
och denna föreställning om fprintf, så låt oss se vad slutresultatet är.
Låt mig gå in i min terminalfönster.
Låt mig köra structs2 skriver.
Ser ut som allt är bra. Låt oss köra structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather skriver.
Ser ut som det betedde samma sak, men om jag gör nu ls
märke till vad filen är här bland alla min kod, databas,
så låt oss öppna den, gedit i databasen och titta på det.
Det är inte den sexigaste av filformat.
Det är verkligen en del av data linje per linje per rad,
men de av er som använder Excel eller CSV-filer, kommaseparerade värden,
Jag kunde verkligen ha använt fprintf att istället kanske göra något liknande
så att jag kunde faktiskt skapa motsvarigheten till en Excel-fil
genom att separera saker med kommatecken, inte bara nya linjer.
>> I det här fallet om jag istället hade använt kommatecken istället för nya linjer
Jag kunde bokstavligen öppna databasfilen i Excel om jag istället fick det att se ut så här.
Kort sagt, nu när vi har makten att skriva till filer
Vi kan nu börja kvarstående uppgifter, hålla den runt på skiva
så att vi kan hålla information kring om och om igen.
Kallelse ett par andra saker som är nu lite mer bekant.
På toppen av detta C-fil har vi en typedef
eftersom vi ville skapa en datatyp som representerar ett ord,
så denna typ kallas ord, och inuti denna struktur
det är lite finare nu.
Varför ett ord som består av till synes en matris?
Vad är ett ord bara intuitivt?
>> Det är en mängd tecken.
Det är en följd av tecken rygg mot rygg mot rygg.
Bokstäver i versaler råkar vara vi godtyckligt säga den maximala längden
av något ord i ordlistan som vi använder för Scramble.
Varför har jag en en?
Den nolltecken.
Minns när vi gjorde Bananagrams exemplet vi behövde ett speciellt värde
vid slutet av ordet för att hålla reda
var ord som faktiskt slut och som problemet inställda specifikationen säger
Här vi umgås med ett givet ord ett booleskt värde,
en flagga, så att säga, sant eller falskt.
Har du hittat detta ord redan, eftersom vi inser
vi behöver verkligen ett sätt att minnas inte bara vad ett ord är Scramble
men om du är människa, funnit det
så att om du hittar ordet "det" man inte bara kan skriva, ange, den, in, den, skriv in
och få 3 poäng, 3 poäng, 3 poäng, 3 poäng.
Vi vill kunna svartlista ordet genom att ange en bool
till true om du har redan hittat det, och så det är därför vi
inkapslade den i denna struktur.
>> Nu här i Scramble finns här andra struct som kallas ordboken.
Frånvarande här är ordet typedef eftersom i detta fall
vi behövde för att kapsla in idén om en ordbok,
och en ordlista innehåller en massa ord,
som antyds av denna array, och hur många av dessa ord finns det?
Nåväl, vad denna variabel kallas storleken säger.
Men vi behöver bara en ordbok.
Vi behöver inte en datatyp som kallas ordbok.
Vi behöver bara en av dem, så det visar sig i C
att om du inte säger typedef, du bara säga struct så inne i klammerparenteser
du sätter dina variabler, då du sätter namnet.
Detta förklarar en variabel som heter lexikon
som ser ut så här.
Däremot är dessa linjer skapar en återanvändbar datastruktur som kallas ord
att du kan skapa flera kopior av, precis som vi skapade
flera kopior av studenter.
>> Vad kan detta i slutändan oss att göra?
Låt mig gå tillbaka till, låt oss säga, en enklare exempel från enklare tider,
och låt mig öppna upp, låt oss säga, compare1.c.
Problemet här till hands är att faktiskt dra tillbaka
lagret av en sträng och börjar ta bort dessa stödhjul
eftersom det visar sig att en sträng hela tiden
är som vi lovade i vecka 1 egentligen bara ett smeknamn,
en synonym från CS50 biblioteket för något som ser lite mer kryptisk,
char *, och vi har sett denna stjärna förut.
Vi såg det i samband med filer.
>> Låt oss nu se varför vi har gömt denna detalj under en tid nu.
Här är en fil som heter compare1.c,
och ber tydligen användaren för 2 strängar, s och t,
och sedan försöker jämföra dessa strängar för jämställdhet i linje 26,
och om de är lika står det: "Du skrev samma sak,"
och om de inte är lika står det: "Du skrev olika saker."
Låt mig gå vidare och köra programmet.
Låt mig gå in i min källa katalog, göra en compare1. Det sammanställs okej.
Låt mig köra compare1.
Jag zooma in, in.
Säg något. HELLO.
Jag ska säga något igen. HELLO.
Jag definitivt inte typ olika saker.
>> Låt mig prova detta igen. BYE BYE.
Definitivt inte annorlunda, så vad som händer här?
Tja, vad som verkligen jämförs i linje 26?
[Ohörbart-student]
Ja, så visar det sig att en sträng, datatyp är typ av en vit lögn.
En sträng är en char *, men vad är en char *?
En char *, som man säger, är en pekare,
och en pekare är effektivt en adress,
en summa plats i minnet, och om du råkar ha skrivit in ett ord som HELLO,
minns från tidigare diskussioner om strängar
Detta är som ordet HELLO.
Kom ihåg att ett ord som HELLO kan representeras
som en array av tecken som denna
och sedan med ett specialtecken i slutet kallas noll karaktär,
som \ betecknar.
Vad är egentligen en sträng?
Observera att detta är flera bitar av minne,
och i själva verket är i slutet av det enda kända när du tittar genom hela strängen
letar efter den speciella null karaktär.
Men om det är en bit av minne från min dators minne,
låt oss säga godtyckligt att strängen bara hade tur,
och det blev placerad i början av datorns RAM-minne.
Detta är bitgruppen 0, 1, 2, 3, 4, 5, 6 ...
>> När jag säger något i stil med GetString och jag string s = GetString
vad som verkligen är tillbaka?
För de senaste veckorna, är vad som verkligen lagras i s
är inte den här strängen i sig, men i detta fall vad som lagras är
numret 0 eftersom det GetString faktiskt gör
är det inte återvänder fysiskt en sträng.
Som inte ens verkligen göra konceptuella mening.
Vad den gör avkastning är ett nummer.
Det antalet är adressen HELLO i minnet,
och strängen är då, om vi skal tillbaka detta skikt, inte sträng egentligen inte existerar.
Det är bara en förenkling av CS50 biblioteket.
>> Detta är verkligen något som kallas char *.
Char vettigt eftersom det är ett ord, som HELLO?
Tja, det är en serie av tecken, en serie tecken.
Char * innebär adressen till en karaktär,
så vad innebär det att returnera en sträng?
Ett trevligt och enkelt sätt att returnera en sträng
snarare än att försöka räkna ut hur jag återvänder till 5 eller 6 olika byte
Låt mig återvända till den adress som byte?
Den första.
Med andra ord, låt mig ge er adressen till ett tecken i minnet.
Det är vad char * representerar adressen till en enda tecken i minnet.
Ring den variabeln är.
Butik i s just adress, som jag godtyckligt sagt är 0,
bara för att hålla det enkelt, men i verkligheten är det i allmänhet ett större antal.
>> Vänta lite.
Om du bara ger mig adressen till det första tecknet, hur vet jag vad adressen är
av det andra tecknet, den tredje, den fjärde och den femte?
[Ohörbart-student]
Du vet bara om slutet på strängen är genom denna behändiga trick,
så när du använder något som printf, vad printf bokstavligen tar sin argumentation,
ihåg att vi använder denna% s platshållare och sedan passera i
variabeln som är lagra en sträng.
Vad du verkligen passerar är adressen för det första tecknet i strängen.
Printf använder sedan en for-slinga eller en while-slinga vid mottagning den adressen,
till exempel 0, så låt mig göra det nu,
printf ("% s \ n" s);
När jag ringer printf ("% s \ n" s), vad jag verkligen ge printf med
är adressen för det första tecknet i s, vilken i detta fall godtyckliga är H.
>> Hur vet printf exakt vad som ska visas på skärmen?
Den person som genomfört genomförts printf en while-slinga eller en for-loop
som säger inte detta tecken lika med speciella noll karaktär?
Om inte, skriva ut den. Vad sägs om den här?
Om inte skriva ut det, skriva ut det, skriva ut det, skriva ut det.
Det här är en speciell. Stoppa utskriften och återgå till användaren.
Och det är bokstavligen allt som har hänt under huven,
och det är mycket att smälta på den första dagen av en klass,
men nu är det verkligen byggsten förståelse allt
som pågått på insidan av vår dators minne,
och så småningom kommer vi reta detta åt med lite hjälp
från en av våra vänner vid Stanford.
>> Professor Nick Parlante vid Stanford har gjort denna underbara videosekvens
från alla möjliga olika språk som infördes
denna lilla Claymation tecken Binky.
Rösten du ska höra på bara några sekunder förhandstitt
är att en Stanford professor och du får
bara 5 eller 6 sekunder av detta just nu,
men detta är tonen som vi kan sluta idag
och börja på onsdag.
Jag ger dig Pointer Kul med Binky, förhandsgranskningen.
[♪ Musik ♪] [Professor Parlante] Hej, Binky.
Vakna. Det är dags för pekaren kul.
[Binky] Vad är det? Lär dig mer om pekare?
Åh, karamell!
>> Vi kommer att se dig på onsdag.
[CS50.TV]