[Powered by Google Translate] [Week 4]
[David J. Malan] [Harvard University]
[Dette er CS50.] [CS50.TV]
>> Okay, det er CS50, og dette er begyndelsen af ​​uge 4,
og dette er en af ​​de langsomste mulige sortering algoritmer.
Hvilken en var det, at vi har lige set der?
Det var boble sortere, for big O (n ^ 2) + sum,
og faktisk er vi ikke de eneste i denne verden for at synes at vide
hvilken boble slags er eller dens køretid.
Faktisk var dette et interview med Eric Schmidt fra Google
og tidligere senator Barack Obama blot et par år siden.
>> Nu, Senator, du er her hos Google,
og jeg kan lide at tænke på formandskabet som en jobsamtale.
Nu er det svært at få et job som præsident, og du går igennem strabadserne nu.
Det er også svært at få et job hos Google.
Vi har spørgsmål, og vi beder vores kandidater spørgsmål,
og denne ene er fra Larry Schwimmer.
Du fyre tror jeg laver sjov? Det er lige her.
Hvad er den mest effektive måde at sortere en million 32-bit heltal?
[Latter]
Well-
Jeg er ked af det. >> Nej, nej, nej, nej.
Jeg tror boble slags ville være den forkerte vej at gå.
>> Kom nu, der fortalte ham det?
Sidste uge husker vi tog en pause fra kode, i det mindste for en dag,
og begyndte at fokusere på nogle højere niveau ideer og problemløsning mere generelt
i forbindelse med søgning og sortering,
og vi introducerede noget, som vi ikke klaske dette navn på i sidste uge,
men asymptotisk notation, Big O, Big Omega,
og nogle gange Big Theta notation, og disse var simpelthen måder
at beskrive køretiden for algoritmer,
hvor lang tid det tager for en algoritme til at køre.
>> Og du kan huske, at du talte om den løbende tid med hensyn til størrelse
af input, som vi generelt kalder n, hvad problemet kan være,
hvor n er antallet af personer i lokalet,
antallet af sider i en telefonbog, og vi begyndte at skrive ting ud
ligesom O (n ^ 2) eller O (n) eller O (n log n),
og selv når det math ikke helt finde ud af så perfekt
og det var n ² - n / 2 eller noget i den retning
ville vi i stedet bare smide nogle af de lavere ordens led,
og motivationen er der, at vi virkelig ønsker en
slags objektiv måde at vurdere
udførelse af programmer eller udførelse af algoritmer
at ved udgangen af ​​dagen har intet at gøre, for eksempel,
med hastigheden på din computer i dag.
>> For eksempel, hvis du implementerer boble sortere
eller du implementere fusionere sortere eller udvælgelse sortere på dagens computer,
en 2 GHz computer, og du kører det,
og det tager nogle antal sekunder, næste år er der en 3 GHz
eller en 4 GHz computer, og du kan derefter hævde, at "Wow, min algoritme
er nu dobbelt så hurtigt, "når de i virkeligheden, der er naturligvis ikke tilfældet.
Det er bare hardwaren har fået hurtigere, men din computer
har ikke, og så vi virkelig ønsker at smide ting som
multipla af 2 eller multipla af 3, når det kommer til at beskrive
hvor hurtigt eller hvor langsomt en algoritme er og virkelig bare fokusere
på n eller en faktor deraf,
vis magt deraf som i tilfælde af den type fra sidste uge.
Og huske på, at med hjælp fra fletningen sort
vi var i stand til at gøre så meget bedre end boble sortere og udvælgelse sortere
og endda insertion art.
>> Vi kom ned til n log n, og igen,
minde om, at log n generelt henviser til noget, der vokser
langsommere da n, så n log n hidtil var god
fordi det var mindre end n ².
Men for at opnå n log n med fletningen sort
hvad var det grundlæggende kimen til en idé om, at vi var nødt til at udnytte
at vi også udnyttes igen i uge 0?
Hvordan kunne vi løse sortering problemet behændigt med fletningen slags?
Hvad var nøglen indsigt, måske?
Nogen overhovedet.
Okay, lad os tage et skridt tilbage.
Beskriv fusionere sortere i dine egne ord.
Hvordan virkede det?
Okay, vi ro tilbage til uge 0.
Okay, ja.
[Uhørlig-studerende]
Okay, godt, så vi delte den vifte af numre i 2 stykker.
Vi sorteres hver af disse stykker, og så har vi fusioneret dem,
og vi har set denne idé før om at tage et problem, der er så store
og hakke det op i et problem, der er så store eller dette store.
>> Recall telefonbogen eksempel.
Hent det selv-tælling algoritme fra uger siden,
så fusionere art, er blevet sammenfattet af denne pseudokode her.
Når du er givet n elementer, først var det sanity check.
Hvis n <2 så skal du ikke gøre noget som helst
for hvis n <2 så n er naturligvis 0 eller 1,
og så hvis det er enten 0 eller 1 der er ikke noget at sortere.
Du er færdig.
Din liste er allerede trivielt sorteres.
Men ellers hvis du har 2 eller flere elementer gå videre og opdele dem
i 2 halvdele,. venstre og højre
Sortere hver af disse halvdele, og derefter flette de sorterede halvdele.
Men problemet her er, at ved første øjekast dette føles som om vi punting.
Det er en cirkulær definition i, at hvis jeg har bedt dig at sortere disse n elementer
og du fortæller mig "Okay, fint, vi sortere de n / 2, og dem n / 2 elementer,"
så mit næste spørgsmål vil være "Fine, hvordan kan du sortere n / 2 elementer?"
>> Men på grund af strukturen af ​​programmet,
fordi der er denne oprindelige sag, så at sige,
dette særlige tilfælde, der siger, at hvis n er <nogle fast værdi ligesom 2 tilbage med det samme.
Må ikke reagere med det samme cirkulære svar.
Denne proces vil denne cyclicity sidst ende.
Hvis jeg spørger dig "Sort disse n elementer", og du siger, "Fint, sortere disse n / 2,"
så du siger, "Fint, sortere disse n / 4, n / 8, N/16,"
sidste ende vil du dividere med en stor nok tal
at du har kun 1 element til venstre, hvorefter du kan sige,
"Her, her er en sorteret enkelt element."
Så glans af denne algoritme op her er at udlede fra det faktum
at når du har alle disse individuelt sorterede lister,
som alle er af størrelse 1, som synes at være ubrugelig,
når du begynder at lægge dem sammen og lægge dem sammen
du opbygge endelig som Rob gjorde i videoen en endelig sorteret liste.
>> Men denne idé rækker langt ud over sortering.
Der er denne idé indlejret i dette program kaldet rekursion,
ideen, hvor du er et program,
og at løse et problem du kalder dig selv,
eller sættes i forbindelse med programmeringssprog du er en funktion,
og for at løse et problem, du funktionen kalde dig
igen og igen og igen, men du funktionen
kan ikke kalde dig uendeligt mange gange.
Til sidst er du nødt til bunden ud, så at sige,
og har nogle hard-coded basis betingelse, siger
på dette tidspunkt at kalde sig selv, således at hele processen
endelig rent faktisk stopper.
Hvad betyder det egentlig, at recurse?
>> Lad os se, om vi kan gøre en enkel, triviel eksempel med, siger,
3 personer med mig op her på scenen, hvis nogen er komfortabel.
1, kom op, 2 og 3.
Hvis du 3 ønsker at komme herop.
Hvis du ønsker at stå lige ved siden af ​​mig her i en linje, formoder, at problemet ved hånden
er meget trivielt tælle antallet af mennesker, der er her.
Men helt ærligt, jeg er træt af alle disse tælle eksempler.
Dette vil tage nogen tid, 1, 2, og prik, prik, prik.
Det kommer til at tage for evigt.
Jeg vil hellere bare punt dette problem helt ved hjælp af-hvad er dit navn?
Sara. >> Sara, all right.
Kelly. >> Kelly og?
>> Willy. >> Willy, Sara, Kelly, og Willy.
Lige nu har jeg fået stillet spørgsmålet af en person
hvor mange mennesker er op på dette tidspunkt, og jeg har ingen idé.
Dette er en virkelig lang liste, og så i stedet vil jeg gøre dette trick.
Jeg har tænkt mig at spørge personen ved siden af ​​mig at gøre det meste af arbejdet,
og når hun er færdig laver det meste af arbejdet
Jeg har tænkt mig at gøre den mindste mængde af arbejde muligt og bare tilføje 1
til, hvad hendes svar er, så here we go.
Jeg er blevet spurgt om, hvor mange mennesker er på scenen.
Hvor mange mennesker er på scenen til venstre for dig?
Den venstre af mig? >> Okay, men ikke snyde.
Det er godt, det er korrekt, men hvis vi ønsker at fortsætte denne logik
lad os antage, at du ligeledes ønsker at punt dette problem til venstre for dig,
så i stedet for svar direkte gå videre og bare give sorteper.
Åh, hvor mange mennesker er til venstre for mig?
Hvor mange mennesker er til venstre?
1.
[Latter]
Okay, så 0, så hvad nu Willy har gjort
er du har returneret dit svar denne retning siger 0.
Nu, hvad skal du så gøre? >> 1.
Okay, så du er den 1, så du siger, "Okay, jeg skal tilføje 1
at uanset Willy tælleretning var, "så 1 + 0.
Du er nu 1, så dit svar til højre er nu-
1. >> Og mine ville være 2.
Godt, så du tager den tidligere svar på 1,
tilsætte den minimale mængde arbejde, du ønsker at gøre, hvilket er +1.
Du har nu 2, og du derefter give mig hvilken værdi?
3, jeg mener, undskyld, 2.
Godt.
>> Nå, vi havde 0 til venstre.
Derefter havde vi 1 og derefter tilføjer vi 2,
og nu er du rakte mig et 2-tal,
og så jeg siger, okay, +1, 3.
Der er faktisk 3 personer stående ved siden af ​​mig på nuværende tidspunkt,
så vi kunne har naturligvis gjort det meget lineært,
meget i indlysende måde, men hvad gjorde vi virkelig gøre?
Vi tog et problem med størrelse 3. oprindeligt.
Vi derefter brød det ned til et problem af størrelse 2,
derefter et problem af størrelse 1, og derefter endelig hovedforslaget
var virkelig, oh, der er ingen der,
på hvilket tidspunkt Willy vendte faktisk en hard-coded svar et par gange,
og den anden blev derefter boblet op, boblede op, boblede op,
og derefter ved tilsætning i denne ene yderligere 1
vi har implementeret denne grundlæggende idé om rekursion.
>> Nu, i dette tilfælde det virkelig ikke løse et problem
mere effektivt, så vi har set hidtil.
Men tænk over de algoritmer vi har gjort på scenen hidtil.
Vi havde 8 stykker papir på tavlen,
på video, når Sean var på udkig efter det nummer 7, og hvad gjorde han virkelig gøre?
Tja, han ikke gøre nogen form for del og hersk.
Han gjorde ikke gøre nogen form for rekursion.
Snarere han bare gjorde det lineære algoritme.
Men da vi introducerede ideen om sorteret numre på scenen lever i sidste uge
derefter havde vi dette instinkt for at gå til midten,
på hvilket punkt vi havde en mindre liste over størrelse 4 eller anden liste over størrelse 4,
og derefter havde vi nøjagtig samme problem, så vi gentog, gentog, gentages.
Med andre ord rekursivt vi.
Mange tak til vores 3 frivillige her for at demonstrere rekursion med os.
>> Lad os se om vi ikke kan gøre det nu lidt mere konkret,
løse et problem, at vi igen kunne gøre temmelig let,
men vi vil bruge det som et springbræt til gennemførelse af denne grundtanke.
Hvis jeg ønsker at beregne summen af ​​en masse numre,
for eksempel, hvis du passerer i nummer 3
Jeg vil gerne give dig værdien af ​​sigma 3,
så summen af ​​3 + 2 + 1 + 0.
Jeg ønsker at komme tilbage svaret 6,
så vi vil gennemføre denne sigma funktion, denne summation funktion
at, igen, tager i input, og returnerer derefter summation
dette nummer hele vejen ned til 0.
Vi kunne gøre det temmelig simpelt, ikke?
Vi kunne gøre det med en vis form for looping struktur,
så lad mig gå videre og få det i gang.
>> Medtag stdio.h.
Lad mig få mig ind i main at arbejde med her.
Lad os gemme det som sigma.c.
Så jeg har tænkt mig at gå ind her, og jeg har tænkt mig at erklære en int n,
og jeg har tænkt mig at gøre følgende, mens brugeren ikke samarbejder.
Selvom brugeren ikke har givet mig et positivt tal
Lad mig gå videre og bede dem for n = GetInt,
og lad mig give dem nogle instrukser om, hvad de skal gøre,
så printf ("Positive heltal please").
Bare noget relativt simpelt som dette, så ved den tid, vi ramt linie 14
vi nu har et positivt heltal formentlig i n.
>> Lad os nu gøre noget ved det.
Lad mig gå videre og beregne summation, så int sum = sigma (n).
Sigma er bare summation, så jeg bare skrive det på amatør måde.
Vi vil bare kalde det sigma der.
Det er summen, og nu jeg har tænkt mig at udskrive resultatet,
printf ("Summen er% d, \ n", sum).
Og så vil jeg vende tilbage 0 for god foranstaltning.
Vi har gjort alt, hvad dette program kræver undtagen den interessante del,
der er rent faktisk at gennemføre den sigma-funktionen.
>> Lad mig gå ned her til bunden, og lad mig erklære funktion sigma.
Det er nødt til at tage en variabel, der er af typen heltal,
og hvad datatype ønsker jeg at vende tilbage formentlig fra sigma?
Int., fordi jeg ønsker det til at matche mine forventninger på linje 15.
Herinde lad mig gå videre og gennemføre denne
i en temmelig ligetil måde.
>> Lad os gå videre og sige int sum = 0,
og nu jeg har tænkt mig at gå har en lidt for løkke her
der kommer til at sige noget som dette,
for (int i = 0; I <= antal, i + +) sum + = i.
Og så jeg har tænkt mig at vende tilbage sum.
Jeg kunne have gennemført dette i en række forskellige måder.
Jeg kunne have brugt en while-løkke.
Jeg kunne have sprunget med sum variabel, hvis jeg virkelig ville,
men kort sagt, vi bare have en funktion, at hvis jeg ikke gjorde goof erklærer sum er 0.
Så gentages fra 0 på op gennem nummer,
og på hver iteration tilføjer den nuværende værdi for sum og derefter vender tilbage sum.
>> Nu er der er en lille optimering her.
Dette er sandsynligvis et spildt skridt, men så må det være. Det er fint for nu.
Vi er i det mindste at være grundig og går 0 hele vejen på op.
Ikke meget hårdt og temmelig ligetil,
men det viser sig, at med den sigma funktion, vi har de samme muligheder
som vi gjorde her på scenen.
På scenen har vi bare talt, hvor mange mennesker var ved siden af ​​mig,
men i stedet, hvis vi ønskede at tælle antallet 3 + 2 + 1
på ned til 0 vi kunne ligeledes punt til en funktion
at I stedet vil betegne som rekursiv.
Her lad os gøre en hurtig tilregnelighed kontrollere og sørge for jeg ikke goof.
>> Jeg ved, der er mindst én ting i dette program, som jeg gjorde forkert.
Da jeg ramte ind skal jeg få nogen form for råben på mig?
Hvad skal jeg være råbte på om?
Ja, jeg glemte prototypen, så jeg bruger en funktion kaldet sigma på linie 15,
men det er ikke erklæret indtil linie 22, så jeg bedst proaktivt gå op her
og erklære en prototype, og jeg vil sige int sigma (int tal), og det er det.
Det er implementeret i bunden.
>> Eller en anden måde jeg kunne løse dette,
Jeg kunne flytte funktionen deroppe, hvilket ikke er dårligt,
men i hvert fald når dine programmer begynder at blive lang, helt ærligt,
Jeg tror der er en vis værdi i altid at have main øverst
så du i læseren kan åbne filen og derefter straks se
hvad programmet gør uden at skulle søge igennem det
udkig efter at hovedfunktion.
Lad os gå ned til min terminal vindue her, prøve at lave sigma gøre sigma,
og jeg skruet op her også.
Implicit erklæring af funktionen GetInt betyder, at jeg har glemt at gøre, hvad ellers?
[Uhørlig-studerende]
Godt, så tilsyneladende en almindelig fejl, så lad os sætte dette op her,
cs50.h, og lad os nu gå tilbage til min terminal vindue.
>> Jeg vil rydde skærmen, og jeg vil køre lave sigma.
Det synes at have kompileret. Lad mig nu køre sigma.
Jeg vil skrive i nummer 3, og jeg fik 6, så ikke en streng kontrol,
men i det mindste ser ud til at virke ved første øjekast, men lad os nu rive det fra hinanden,
og lad os faktisk udnytter ideen om rekursion, igen,
i en meget enkel sammenhæng, således at i et par uger
når vi begynder at udforske mere avanceret datastrukturer end arrays
Vi har endnu et værktøj i værktøjskassen med til at
manipulere disse datastrukturer som vi vil se.
Dette er den iterative tilgang, løkken tilgang.
>> Lad mig i stedet nu gøre dette.
Lad mig i stedet sige, at summen af ​​antal
ned til 0 er virkelig den samme som
Antallet + sigma (nummer - 1).
Med andre ord, jeg ligesom på scenen hasard til hver af de mennesker ud for mig,
og de til gengæld holdt punting indtil vi endelig fladede ud på Willy,
der havde til at returnere en hard-coded svar ligesom 0.
Her nu er vi ligeledes punting til sigma
den samme funktion som oprindeligt blev kaldt, men den centrale indsigt her
er, at vi ikke kalder sigma ens.
Vi er ikke passerer i n.
Vi er helt klart passerer i nummer - 1,
så en lidt mindre problem, lidt mindre problem.
>> Desværre er det ikke helt en løsning endnu, og før vi retter
hvad der kan springe ud som indlysende på nogle af jer
Lad mig gå videre og kør gøre.
Det synes at kompilere okay.
Lad mig køre sigma med 6.
Whoops, lad mig køre sigma med 6.
Vi har set det før, men ved et uheld sidste gang så godt.
Hvorfor fik jeg denne kryptiske segmenteringsfejl? Yeah.
[Uhørlig-studerende]
Der er ingen base case, og mere specifikt, hvad sandsynligvis sket?
Det er et symptom på, hvad adfærd?
Sig det lidt højere.
[Uhørlig-studerende]
Det er en uendelig løkke effektivt, og problemet med uendelige løkker
når de involverer rekursion i dette tilfælde, en funktion kalder sig selv,
hvad der sker, hver gang du kalder en funktion?
Nå, tænker tilbage på, hvordan vi lagde ud hukommelsen i en computer.
Vi sagde, at der er denne luns af hukommelse kaldet stakken, der er i bunden,
og hver gang du kalder en funktion lidt mere hukommelse bliver sat
på denne såkaldte stak, der indeholder denne funktion lokale variabler eller parametre,
så hvis sigma opkald sigma opkald sigma opkald sigma
kalder sigma hvor kommer denne historie ende?
>> Godt, det i sidste ende overskridelser det samlede beløb
af hukommelse, som du har til rådighed til din computer.
Du overskridelse det segment, som du forventes at holde sig inden,
og du får denne segmentering fejl, core dumpet,
og hvad kerne dumpet betyder er, at jeg nu har en fil kaldet kerne
der er en fil, der indeholder nuller og ettaller
der faktisk i fremtiden vil være diagnostisk anvendeligt.
Hvis det ikke er indlysende for dig, hvor din bug er
du kan faktisk gøre en smule af retskemisk analyse, så at sige,
på dette core dump fil, er der, igen, bare en hel masse nuller og ettaller
der hovedsageligt repræsenterer tilstanden af ​​dit program i hukommelsen
det øjeblik det nedstyrtede på denne måde.
>> Rettelsen her er, at vi ikke bare kan blindt returnere sigma,
antallet + sigma af en lidt mindre problem.
Vi er nødt til at have en form for base case her,
og hvad skal den oprindelige sag sandsynligvis være?
[Uhørlig-studerende]
Okay, så længe antallet er positiv bør vi faktisk returnere dette,
eller sagt på en anden måde, hvis antal er, sige, <= til 0
ved du hvad, jeg vil gå videre og returnere 0,
meget gerne Willy gjorde, og andet, vil jeg gå videre
og returnere dette, så det er ikke så meget kortere
end den iterative version, som vi har pisket op først med en for-løkke,
men bemærker, at der er denne form for elegance til det.
I stedet for at returnere nogle antallet og udføre al den matematiske
og tilføje ting op med lokale variable
du i stedet sige "Okay, hvis det er et super let problem,
ligesom antallet er <0, så lad mig straks returnere 0 ".
>> Vi vil ikke gider støtte negative tal,
så jeg har tænkt mig at hårdt kode værdien 0.
Men ellers, at gennemføre denne idé om at summere
alle disse tal sammen kan du effektivt tage en lille bid
ud af problemet, vi meget gerne gjorde her på scenen,
derefter punt resten af ​​problemet til den næste person,
men i dette tilfælde den næste person selv.
Det er en identisk navngivne funktion.
Bare give det en mindre og mindre og mindre problem hver gang,
og selvom vi ikke helt har formaliserede ting i kode her
Dette er præcis, hvad der foregik i uge 0 med telefonbogen.
Dette er præcis, hvad der foregik i de seneste uger med Sean
og med vores demonstrationer af at søge efter numre.
Det tager et problem og dividere det igen og igen.
>> Med andre ord, er der en måde nu at oversætte
denne virkelige verden konstruktion, dette højere niveau konstruktion
af del og hersk og gør noget igen og igen
i kode, så dette er noget, vi vil se igen over tid.
Nu, som en sidebemærkning, hvis du er ny til rekursion, bør du i det mindste forstå nu
hvorfor det er sjovt.
Jeg har tænkt mig at gå til google.com,
og jeg har tænkt mig at søge efter nogle tips og tricks om rekursion, skal du indtaste.
Fortæl personen ved siden af ​​dig, hvis de ikke grinede lige nu.
Mente du rekursion?
Mente du-ah, der går vi.
Okay, nu er resten af ​​alle.
En lille påske æg indlejret et eller andet sted der i Google.
Som en sidebemærkning, en af ​​de links vi sætter på kursets hjemmeside
for i dag er netop denne gitter af forskellige metoder til sortering algoritmer,
hvoraf nogle vi kiggede på i sidste uge, men hvad er rart om denne visualisering
som du forsøger at pakke dit sind omkring forskellige ting i forbindelse med algoritmer
vide, at du kan meget nemt nu starte med forskellige typer input.
Indgangene alle vendt, inputtene meste sorteres, de input tilfældig og så videre.
Som du forsøger at, igen, skelne disse ting i dit sind
indse, at denne webadresse på kursets hjemmeside på Foredrag siden
kan hjælpe dig årsag gennem nogle af dem.
>> I dag får vi endelig at løse dette problem fra et stykke tid tilbage,
som var, at denne swap-funktion bare ikke virkede,
og hvad var det grundlæggende problem med denne funktion swap,
hvis formål var igen at udveksle en værdi her og her
således at dette sker?
Dette har ikke rent faktisk arbejder. Hvorfor?
Yeah.
[Uhørlig-studerende]
Præcis, forklaringen på denne bugginess
simpelthen var fordi når du kalder funktioner i C
og disse funktioner tager argumenter, som a og b her,
du passerer i kopier, uanset deres værdi, du leverer til den pågældende funktion.
Du er ikke at give de oprindelige værdier selv,
så vi så det i forbindelse med buggyc,
buggy3.c, som kiggede lidt noget som dette.
>> Minde om, at vi havde x og y initialiseres til 1 og 2, henholdsvis.
Vi derefter trykt ud af, hvad de var.
Jeg hævdede derefter, at jeg var bytte dem ved at kalde swap af x, y.
Men problemet var, at bytte bearbejdet,
men kun i omfanget af swap fungere selv.
Så snart vi ramte linie 40 dem byttet værdier
blev smidt væk, og så intet
i den oprindelige funktion main blev faktisk ændret på alle,
så hvis du tror dengang, hvad det ligner i forhold til vores hukommelse
hvis denne venstre side af brættet repræsenterer-
og jeg vil gøre mit bedste for alle at se denne-hvis denne venstre side af brættet
betegner fx din RAM, og stablen vil vokse på op på denne måde,
og vi kalder en funktion som main, og vigtigste har 2 lokale variabler, x og y,
lad os beskrive dem som x her, og lad os beskrive disse som y her,
og lad os sætte i værdierne 1 og 2, så dette her er main,
og når main kalder swap-funktion operativsystemet
giver swap-funktionen sin egen skår af hukommelse på stakken,
sin egen ramme på stakken, så at sige.
Endvidere fordeler 32 bit for disse int'er.
Det sker for at kalde dem A og B, men det er helt vilkårlig.
Det kunne have kaldt dem, hvad det vil, men hvad sker der, når main
opkald swap er det tager denne 1, sætter en kopi der sætter en kopi der.
>> Der er 1 anden lokal variabel i swap, dog kaldes hvad? >> Tmp.
Tmp, så lad mig give mig en anden 32 bits her,
og hvad gjorde jeg gøre i denne funktion?
Jeg sagde int tmp får en, så en har 1, så jeg gjorde det, da vi sidst spillede med dette eksempel.
Så en bliver b, så b er 2, så nu det bliver 2,
og nu B får temp, så temp er 1,
så nu B bliver dette.
Det er godt. Det virkede.
Men så så snart funktionen returnerer
swap hukommelse effektivt forsvinder, således at det kan genbruges
som en anden funktion i fremtiden, hoved og er naturligvis fuldstændig uændrede.
Vi har brug for en måde fundamentalt at løse dette problem,
og i dag får vi endelig en måde at gøre dette, hvorved
vi kan indføre noget, der hedder en pegepind.
Det viser sig, at vi kan løse dette problem
ikke ved at passere i kopier af x og y
men i stedet ved at passere i hvad, tror du, at swap-funktion?
Ja, hvad med adressen?
Vi har ikke rigtig talt om adresser i mange detaljer,
men hvis denne tavle er min computers hukommelse
Vi kunne godt begynde at nummerere bytes i min RAM
og sige dette er byte # 1, det er byte # 2, byte # 3,
byte # 4, byte # ... 2 milliarder, hvis jeg har 2 GB RAM,
så vi kan helt sikkert komme med nogle vilkårlig nummersystem
for alle de enkelte bytes i min computers hukommelse.
>> Hvad hvis i stedet, når jeg ringer swap
snarere end pass i kopier af x og y
hvorfor ikke jeg i stedet passere adressen på x her,
adressen på y her det væsentlige postadresse
af x og y fordi så bytte, hvis han underrettet
Den adresse i hukommelsen af ​​x og y,
så bytte, hvis vi trænet ham en lille smule,
han potentielt kunne køre til denne adresse, så at sige,
x, og ændre antallet der, så køre til adressen y,
ændre antallet der, selvom det ikke er faktisk at få kopier af disse værdier selv,
så selvom vi talte om det som værende main hukommelse
og dette som værende swap hukommelse den magtfulde og den farlige del af C
er, at enhver funktion kan røre hukommelse overalt i computeren,
og det er stærk i at du kan gøre meget smarte ting med edb-programmer i C.
Det er farligt, fordi du også kan skrue op meget let.
Faktisk er en af ​​de mest almindelige måder for programmer i disse dage udnyttes
stadig er en programmør ikke at realisere
at han eller hun er at tillade en data
at blive skrevet på et sted i hukommelsen, der ikke var tiltænkt.
>> For eksempel, erklærer han eller hun et array af størrelse 10
men så ved et uheld forsøger at sætte 11 bytes i denne vifte af hukommelse,
og du begynder at røre dele af hukommelsen, der ikke længere er gyldige.
Blot for at kontekstuelle dette, vil nogle af jer ved, at
software ofte beder dig om serienumre eller registreringsnøgler,
Photoshop og Word og programmer som dette.
Der findes revner, som nogle af jer ved, online, hvor du kan køre et lille program,
og voila, ikke mere anmodning om et serienummer.
Hvordan er det i orden?
I mange tilfælde er disse ting er simpelthen at finde i de computere
tekstsegmenter i computerens faktiske nuller og ettaller
hvor er denne funktion, hvor serienummeret er anmodet om,
og du overskriver det rum, eller mens programmet kører
du kan regne ud, hvor nøglen er faktisk gemt
bruger noget, der hedder en debugger, og du kan knække software på den måde.
Dette er ikke til at sige, at dette er vores mål for de næste par dage,
men det har meget virkelige verden forgreninger.
At man tilfældigvis involvere tyveri af software,
men der er også et kompromis af hele maskiner.
>> Faktisk hjemmesider, når disse dage udnyttes
og kompromitteret og data er lækket og passwords bliver stjålet
dette meget ofte vedrører dårlig forvaltning af ens hukommelse,
eller, i tilfælde af databaser, manglende foregribe
kontradiktorisk input, så mere om det i de kommende uger,
men for nu bare en forsmag på den slags skader, som du kan gøre
ved ikke helt forstå, hvordan tingene fungerer under hætten.
Lad os gå om at forstå, hvorfor dette er brudt
med et værktøj, der bliver mere og mere nyttigt
som vores programmer får mere kompleks.
Så langt når du har haft en fejl i dit program
hvordan har du gået om debugging det?
Hvad har dine teknikker været hidtil, uanset om undervist af din TF
eller bare selvlært?
[Student] printf.
Printf, så printf har sandsynligvis været din ven i, at hvis du ønsker at se
hvad der foregår inde i dit program
du bare sætte printf her, printf her, printf her.
Så kan du køre det, og du får en hel masse ting på skærmen
som du kan bruge til så udlede, hvad der faktisk går galt i dit program.
>> Printf tendens til at være en meget kraftfuld ting,
men det er en meget manuel proces.
Du er nødt til at sætte en printf her, en printf her,
og hvis du sætte det ind i en løkke kan du få 100 linjer
af produktionen, som du derefter nødt til at finkæmme igennem.
Det er ikke en meget brugervenlig og interaktiv mekanisme til debugging-programmer,
men heldigvis findes der alternativer.
Der er et program, for eksempel, kaldet GDB, GNU Debugger,
der er en lille mystisk i, hvordan du bruger det.
Det er en lidt kompleks, men helt ærligt,
dette er en af ​​de ting, hvor, hvis du lægger i denne og næste uge
den ekstra time til at forstå noget som GDB
det vil spare dig formentlig titusinder af timer i det lange løb,
så med det, lad mig give dig en smagsprøve på, hvordan det virker.
>> Jeg er i min terminal vindue.
Lad mig gå videre og kompilere dette program, buggy3.
Det er allerede ajour.
Lad mig køre det ligesom vi gjorde et stykke tid siden, og ja, er det brudt.
Men hvorfor er dette? Måske jeg skruet op swap-funktionen.
Måske er det a og b. Jeg er ikke helt flytte dem rundt korrekt.
Lad mig gå videre og gøre det.
I stedet for bare at køre buggy3 lad mig i stedet køre dette program GDB,
og jeg har tænkt mig at fortælle det til at køre buggy3,
og jeg har tænkt mig at inkludere en kommandolinje argument,-TUI,
og vi vil sætte dette i fremtidige problemer på spec at minde.
Og nu denne sorte og hvide brugergrænseflade dukkede op, igen,
er lidt overvældende i starten, fordi der er alt dette
garantioplysninger hernede, men i det mindste er der noget velkendt.
I toppen af ​​vinduet er mit konkrete kode
og hvis jeg rulle op her lad mig rulle til selve toppen af ​​min fil,
og ja, der er buggy3.c, og meddelelse nederst i dette vindue
Jeg har denne GDB prompt.
>> Dette er ikke det samme som min normale John Harvard prompt.
Dette er en prompt, der kommer til at tillade mig at styre GDB.
GDB er en debugger.
En debugger er et program som lader dig gå igennem
udførelsen af ​​dit program linje for linje for linje,
undervejs gør noget, du vil til programmet,
selv kalde funktioner, eller ser, endnu vigtigere,
ved forskellige variable værdier.
Lad os gå videre og gøre det.
Jeg har tænkt mig at gå videre og skrive køre på GDB er hurtig,
så mærke nederst til venstre på skærmen, jeg har indtastet løbe,
og jeg har ramt ind, og hvad gjorde det så?
Det bogstaveligt løb mit program, men jeg havde faktisk ikke se meget gå på her
fordi jeg ikke har faktisk fortalt fejlsøgeren
at holde pause på et bestemt tidspunkt.
Bare skrive run kører programmet.
Jeg kan faktisk ikke se noget. Jeg kan ikke manipulere det.
>> I stedet lad mig gøre det her.
På dette GDB prompt lad mig i stedet skrive pause, skal du indtaste.
Det er ikke hvad jeg mente at skrive.
Lad os i stedet skrive break main.
Med andre ord ønsker jeg at sætte noget, der hedder et breakpoint,
som er rammende navn, fordi det vil bryde eller pause
udførelsen af ​​dit program på det pågældende sted.
Main er navnet på min funktion.
Bemærk, at GDB er temmelig smart.
Det regnede ud, at main sker for at starte nogenlunde på linie 18
af buggy3.c, og derefter mærke her øverst til venstre
b + er ret ud til linje 18.
Det er at minde mig om, at jeg har sat et breakpoint på linje 18.
Denne gang når jeg skriver løb, vil jeg køre mit program
indtil den rammer det breakpoint,
så programmet vil pause for mig på linje 18.
Her går vi, kører.
Intet ser ud til at være sket, men varsel nederst til venstre
starter programmet, buggy3, skillepunkt 1 i main på buggy3.c linje 18.
Hvad kan jeg gøre nu?
>> Bemærk, at jeg kan begynde at skrive ting som print,
ikke printf, udskrive x, og nu, er underligt.
De $ 1 er blot en nysgerrighed, som vi vil se
hver gang du udskriver noget, man får en ny $ værdi.
Det er så du kan henvise tilbage til tidligere værdier just in case,
men for nu, hvad print fortæller mig, er, at værdien af ​​x på dette tidspunkt i historien
er tilsyneladende 134514032.
Hvad? Hvor kom det selv kommer fra?
[Uhørlig-studerende]
Faktisk er det, hvad vi vil kalde en skraldespand værdi, og vi har ikke talt om det endnu,
men grunden til, at du initialiserer variabler
er naturligvis så, at de har en vis værdi, som du vil have dem til at have.
Men fangsten huske, at du kan erklære variabler
ligesom jeg gjorde for et øjeblik siden i min sigma eksempel
uden at give dem en værdi.
Recall, hvad jeg gjorde herovre i sigma.
Jeg erklærede n, men hvilken værdi har jeg give det?
Ingen, fordi jeg vidste, at i de næste par linier
GetInt ville tage sig af problemet med at sætte en værdi inde i n.
>> Men på dette tidspunkt i historien af ​​linje 11
og linie 12 og linie 13 og linie 14
i alle de flere linjer, der er værdien af ​​n?
I C du bare ikke kender.
Det er generelt en garbage værdi, mens fuldstændig tilfældigt tal
der er tilovers hovedsagelig fra nogle tidligere funktion
er blevet kørt, så dit program kører
minde om, at funktionen får funktion, funktion, funktion.
Alle disse rammer bliver sat på hukommelsen, og derefter disse funktioner tilbage,
og ligesom jeg foreslog med viskelæderet deres hukommelse er efterhånden genbrugt.
Nå, det bare så sker det, at denne variabel x i dette program
synes at have indeholdt noget skrald værdi ligesom 134514032
fra nogle tidligere funktion. ikke en, som jeg skrev
Det kunne være noget, der kommer effektivt med operativsystemet,
en funktion under hætten.
>> Okay, det er fint, men lad os nu gå videre til den næste linje.
Hvis jeg skriver "næste" på min GDB prompt og jeg ramte ind,
bemærke, at fremhæve bevæger sig ned til linjen 19,
men den logiske konsekvens er, at ledningen 18
har nu afsluttet udføre, så hvis jeg igen skriver "print x"
Jeg vil nu se henholdsvis 1, og ja, jeg gør.
Igen $ stuff er en måde at GDB minde dig
hvad historien om udskrifter er, at du har gjort.
Lad mig nu gå videre og udskrive y, og ja, y er nogle skøre værdi samt,
men nogen big deal, fordi i linie 19 vi er ved at tildele det
værdien 2, så lad mig skrive "næste" igen.
Og nu vi er på printf linje.
Lad mig gøre print x.
Lad mig gøre print y. Helt ærligt, jeg får lidt træt af udskrivning af denne.
Lad mig i stedet skrive "skærm x" og "display y,"
og nu hver gang jeg skriver en kommando i fremtiden
Jeg vil blive mindet om, hvad der er x og y, hvad er x og y, hvad er x og y.
>> Jeg kan også, som en sidebemærkning, skriv "info locals."
Info er en speciel kommando.
Locals betyder, at det viser mig de lokale variabler.
Just in case jeg glemmer eller det er en vanvittig, kompliceret funktion
at jeg eller en anden skrev info locals vil fortælle dig
hvad er alle de lokale variabler i dette lokal funktion
at du måske bekymre sig om, hvis du ønsker at stikke rundt.
Nu printf er ved at udføre, så lad mig gå videre og bare skrive "næste".
Fordi vi er i dette miljø, vi faktisk ikke se det
eksekvere hernede, men bemærker det bliver lidt mishandlede her.
Men bemærk det er tvingende skærmen dér,
så det er ikke et perfekt program her, men det er okay, fordi jeg altid kan stikke omkring
brug af udskriftsmedier, hvis jeg vil.
>> Lad mig skrive næste gang, og nu her er den interessante del.
På dette tidspunkt i historien y er 2, og x er 1,
som foreslået her, og igen,
Grunden til dette er automatisk viser nu, er fordi jeg brugte kommandoen
display x og display y, så det øjeblik, jeg skriver næste
i teorien x og y skal blive byttet.
Nu ved vi allerede, at der ikke vil være tilfældet,
men vi vil se på et øjeblik, hvordan vi kan dykke dybere for at finde ud af hvorfor det er sandt.
Næste, og desværre, y er stadig 2 og x er stadig 1, og jeg kan bekræfte så meget.
Print x, print y.
Faktisk har ingen swapping faktisk er sket, så lad os starte dette over.
Det er klart swap er brudt.
Lad os i stedet skrive "run" igen.
Lad mig sige ja, jeg vil genstarte den fra begyndelsen, skal du indtaste.
>> Nu er jeg tilbage op på linie 18.
Nu opdager x og y er skrald værdier igen.
Next, næste dernæst næste.
Hvis jeg får keder jeg kan også bare skrive n for næste.
Du kan forkorte det til den kortest mulige sekvens af tegn.
Swap er nu brudt.
Lad os dykke i, så i stedet for at skrive næste,
nu jeg har tænkt mig at skrive trin, så at jeg stepping inde i denne funktion
så jeg kan gå igennem det, så jeg ramte trin og derefter indtaste.
Bemærk, at fremhæve hopper ned lavere i mit program til linje 36.
Nu hvad er de lokale variable?
Info lokalbefolkningen.
Intet bare endnu, fordi vi ikke har fået til den linje,
så lad os gå videre og sige "næste".
Nu synes vi at have tmp, print tmp.
Garbage værdi, right? Det tror jeg.
Hvad udskrive en, print b, 1 og 2?
I et øjeblik, så så snart jeg skriver næste gang
tmp vil tage på en værdi på 1, forhåbentlig,
fordi tmp vil blive tildeles værdien for en.
>> Nu lad os gøre udskrive en, print b,
men nu udskrive tmp, og det er faktisk 1.
Lad mig gøre næste. Lad mig gøre næste.
Jeg er færdig med swap-funktion.
Jeg er stadig inde i den på linje 40, så lad mig udskrive en,
print b, og jeg er ligeglad med, hvad tmp er.
Det ligner swap er korrekt, når det kommer til at bytte a og b..
Men hvis jeg nu skrive næste, jeg hopper tilbage til linje 25,
og selvfølgelig, hvis jeg skriver i x-og print y
de er stadig uændret, så vi har ikke løst problemet.
Men diagnostisk nu måske med denne GDB program
vi har i det mindste fået et skridt tættere på at forstå
hvad der går galt uden at skulle strøelse vores kode ved at sætte en printf her,
printf her, printf her og derefter kører det igen og igen
forsøger at finde ud af, hvad der går galt.
>> Jeg har tænkt mig at gå videre og afslutte ud af dette helt med op.
Det kommer til at så sige, "Quit alligevel?" Ja.
Nu er jeg tilbage på min normale prompt, og jeg er færdig med at bruge GDB.
Som en sidebemærkning, behøver du ikke at bruge denne-TUI flag.
Faktisk hvis du udelade det får væsentlige den nederste halvdel af skærmen.
Hvis jeg skriv derefter pause main og derefter køre
Jeg kan stadig køre mit program, men hvad den vil gøre, er mere tekstuelt
bare vise mig den aktuelle linje én ad gangen.
The-TUI, tekstuelle brugergrænseflade,
bare viser dig mere af programmet på én gang, hvilket er sandsynligvis en smule begrebsmæssigt lettere.
Men ja, jeg kan bare gøre som det næste, næste, næste,
og jeg har tænkt mig at se en linje ad gangen, og hvis jeg virkelig ønsker at se, hvad der foregår
Jeg kan skrive listen og se en hel masse tilstødende linjer.
>> Der er en video, som vi har bedt om, at du ser for problemer sæt 3
hvor Nate dækker nogle af de snørklede af GDB,
og dette er en af ​​de ting, ærligt, hvor nogle ikke-triviel procentdel af dig
vil aldrig røre GDB, og det vil være en dårlig ting
fordi bogstaveligt vil du ende med at bruge mere tid senere dette semester
jagter ned bugs så ville du hvis du lægger i denne halve time / time
denne og næste uge læring for at blive fortrolig med GDB.
Printf var din ven.
GDB skulle nu være din ven.
>> Eventuelle spørgsmål om GDB?
Og her er en hurtig liste over nogle af de mest kraftfulde og nyttige kommandoer.
Ja. >> Kan du udskrive en streng?
Kan du udskrive en streng? Absolut.
Det behøver ikke at bare være heltal.
Hvis en variabel s er en streng bare skrive på tryk s.
Det vil vise dig, hvad denne streng variabel er.
[Uhørlig-studerende]
Det vil give dig adressen og selve strengen.
Det vil vise jer begge.
Og en sidste ting, bare fordi det er godt at vide for.
Backtrace og ramme, så lad mig dykke ned i denne ene sidste gang,
samme nøjagtige program med GDB.
Lad mig gå videre og køre den tekstuelle brugergrænseflade version,
bryde main.
Lad mig gå videre og køre igen. Her er jeg.
Lad mig gå næste, næste, næste, næste, næste, step, indtaste.
>> Og nu vel er jeg nu i swap bevidst, men jeg er ligesom "Damn, hvad var værdien af ​​x?"
Jeg kan ikke gøre x længere.
Jeg kan ikke gøre y fordi de ikke er i omfang.
De er ikke i sammenhæng, men ikke noget problem.
Jeg kan skrive backtrace.
Det viser mig alle de funktioner, der er udført frem til dette tidspunkt.
Bemærk, at en på bunden, main, flugter med main
være på bunden af ​​vores billede her.
Det faktum, at swap er over det linjer op med swap værende over den i hukommelsen her,
og hvis jeg ønsker at komme tilbage til main midlertidigt jeg kan sige "frame".
Hvilket nummer? Main er ramme # 1.
Jeg har tænkt mig at gå videre og sige "frame 1".
>> Nu er jeg tilbage i main, og jeg kan udskrive x, og jeg kan udskrive y,
men jeg kan ikke udskrive en eller b..
Men jeg kan, hvis jeg siger, "Okay, vent lige lidt. Hvor var swap?"
Lad mig gå videre og sige "frame 0".
Nu er jeg tilbage, hvor jeg ønsker at være, og som en sidebemærkning,
der er andre kommandoer også gerne hvis du virkelig at kede skrive næste, næste, næste, næste,
du kan generelt sige ting som "næste 10", og der vil gå gennem de næste 10 linjer.
Du kan også skrive "fortsæt", når du virkelig få dødtrætte af at træde igennem.
Fortsæt vil køre dit program uden afbrydelse, indtil den rammer en anden breakpoint,
enten i en løkke eller sænke ned i dit program.
>> I dette tilfælde har vi fortsatte til slutningen, og programmet forlades normalt.
Dette er en fancy måde, ringere proces.
Bare dit program forlades normalt.
Mere om det i videoen og debugging sessioner til at komme.
Det var en masse.
Lad os tage vores 5-minutters pause her, og vi vil vende tilbage med struct og filer.
>> Hvis du har dykket ned denne uges Pset allerede
vil du vide, at vi bruger i fordelingen koden,
kildekoden, som vi leverer til dig som udgangspunkt, nogle nye teknikker.
Især introducerede vi den nye søgeord kaldet struct, for struktur,
så vi kan oprette tilpassede variabler slags.
Vi har også indført begrebet fil I / O, fil input og output,
og det er, så vi kan spare staten
af din Scramble bord til en fil på disk
således at de pædagogiske stipendiater og jeg kan forstå
hvad der foregår inde i dit program uden at skulle manuelt spille
snesevis af spil Scramble.
Vi kan gøre det mere automatisk at.
>> Denne idé om en struct løser en temmelig overbevisende problem.
Antag, at vi ønsker at gennemføre nogle program
at en eller anden måde holder styr på oplysninger om studerende,
og studerende kan have for eksempel et ID, et navn
og et hus på et sted som Harvard, så disse er 3 stykker af information
vi ønsker at holde rundt, så lad mig gå videre og begynde at skrive et lille program her,
omfatte stdio.h.
Lad mig gøre omfatte cs50.h.
Og derefter starte min vigtigste funktion.
Jeg gider ikke med nogen kommandolinjeargumenter,
og her vil jeg gerne have en elev, så jeg har tænkt mig at sige
en elev har et navn, så jeg har tænkt mig at sige "string navn."
Så jeg har tænkt mig at sige en studerende også har et ID, så int id,
og en elev har et hus, så jeg vil også sige "streng hus."
Så vil jeg bestille disse lidt mere rent som denne.
Okay, nu har jeg 3 variable med til at repræsentere en studerende, så "en studerende".
>> Og nu vil jeg gerne udfylde disse værdier, så lad mig gå videre og sige noget i retning af
"Id = 123".
Navnet kommer til at få David.
Lad os sige hus kommer til at få Mather,
og så jeg har tænkt mig at gøre noget vilkårligt lignende printf ("% s,
hvis ID er% d, bor i% s.
Og nu, hvad jeg ønsker at tilslutte her, den ene efter den anden?
Navn, id, hus, return 0.
Okay, medmindre jeg skruet op et eller andet sted her
Jeg tror, ​​vi har en temmelig god program, der gemmer én studerende.
Selvfølgelig er det ikke så interessant. Hvad hvis jeg ønsker at have 2 studerende?
Det er ikke nogen big deal. Jeg kan støtte 2 personer.
Lad mig gå videre og fremhæve dette og gå ned her,
og jeg kan sige "id = 456" for en som Rob, der bor i Kirkland.
>> Okay, vent, men jeg kan ikke kalde disse de samme ting,
og det ser ud som om, jeg bliver nødt til at kopiere dette,
så lad mig sige, at disse vil være Davids variabler,
og lad mig få nogle eksemplarer af disse for Rob.
Vi kalder disse Robs men dette kommer ikke til at virke nu
fordi jeg har-vent, lad os ændre mig til ID1, NAME1 og House1.
Rob vil være 2, 2.
Jeg har fået at ændre dette her, her, her, her, her, her.
Vent, hvad med Tommy? Lad os gøre det igen.
Selvfølgelig, hvis du stadig mener, det er en god måde at gøre dette, det er ikke,
så copy / paste dårligt.
Men vi løst dette for en uge siden.
>> Hvad var vores løsning, når vi ønskede at have flere forekomster af samme datatype?
[Studerende] Et array.
Et array, så lad mig prøve at rydde op.
Lad mig gøre nogle plads til mig på toppen, og lad mig i stedet gøre det her.
Vi kalder disse mennesker, og i stedet vil jeg sige "int ids",
og jeg har tænkt mig at understøtte 3 os for nu.
Jeg har tænkt mig at sige "strengnavne", og jeg vil støtte 3 af os,
og så jeg har tænkt mig at sige "streng huse," og jeg har tænkt mig at understøtte 3 af os.
Nu her i stedet for David at få sine egne lokale variable
vi kan slippe af med dem.
Det føles godt, at vi er rengøring dette op.
Jeg kan så sige David vil være [0] og navne [0]
og huse [0].
Og så Rob vi kan ligeledes spare på dette.
Lad os sætte dette ned her, så han kommer til at vilkårligt være ids [1].
Han kommer til at være navne [1],
og så endelig huse [1].
>> Stadig lidt kedelig, og nu har jeg til at finde ud af dette,
så lad os sige "navne [0], id [0], huse [0],
og lad os pluralize dette.
Ids, ids, ids.
Og igen, jeg gør det, så igen, jeg allerede ty til copy / paste igen,
så odds er der er en anden løsning her.
Jeg kan sikkert rydde op yderligere med en løkke eller sådan noget,
så kort sagt, er det lidt bedre, men stadig føles
Jeg ty til copy / paste, men selv dette, jeg hævder,
er egentlig ikke fundamentalt den rigtige løsning, fordi
hvad nu hvis engang vi beslutter du hvad?
Vi bør virkelig have været lagring e-mail adresser for David og Rob
og alle andre i dette program.
Vi bør også gemme telefonnumre.
Vi bør også gemme akutte kontaktnumre.
Vi har alle disse stykker af data, som vi ønsker at gemme,
så hvordan kan du gå om at gøre det?
>> Du erklærer en anden række i toppen, og så er du manuelt tilføje
en e-mailadresse [0], e-mail-adresse [1]
for David og Rob og så videre.
Men der er egentlig bare en underliggende antagelse dette design
at jeg bruger den ære systemet at vide, at
[I] i hvert af de adskillige arrays
bare så sker at henvise til den samme person,
så [0] i ids er nummer 123,
og jeg har tænkt mig at antage, at navne [0]
er den samme persons navn og huse [0]
er den samme person hus og så fremdeles for alle de forskellige arrays som jeg opretter.
Men bemærk, at der ikke er nogen fundamental kobling
blandt disse 3 stykker information, id, navn og hus,
selvom virksomheden, vi forsøger at model i dette program er ikke arrays.
Arrays er netop denne programmatiske måde at gøre dette.
Hvad vi virkelig ønsker at modellere i vores program er en person
ligesom David, en person som Rob inden i hvilken
eller indkapsling er et navn og id og et hus.
>> Kan vi på en måde udtryk for denne idé om indkapsling
hvorved en person har et ID, et navn og et hus
og ikke ty til virkelig dette hack, hvor vi bare
tillid til, at beslaget noget
henviser til det samme humane enhed i hver af disse forskellige arrays?
Vi kan faktisk gøre dette.
Lad mig gå over main for nu, og lad mig skabe min egen datatype
for virkelig første gang.
Vi brugte denne teknik i Scramble,
men her vil jeg gå videre og oprette en datatype,
og ved du hvad, jeg vil kalde det studerende eller person,
og jeg har tænkt mig at bruge typedef for definere en type.
Jeg har tænkt mig at sige, at dette er en struktur,
og så er denne struktur vil være af typen studerende, vil vi sige,
selvom det er en smule dateret nu for mig.
Vi vil sige "int id."
Vi vil sige "string navn."
Så vil vi sige "string hus,"
så nu ved udgangen af ​​disse få linjer kode
Jeg har netop lært Klang, at der findes
en datatype udover int'er, foruden strygere, foruden fordobler udover flåd.
>> Fra dette tidspunkt linie 11, er der nu en ny datatype kaldet studerende,
og nu kan jeg erklære en elev variabel overalt jeg ønsker,
så lad mig rulle ned her til folk.
Nu kan jeg slippe af med dette, og jeg kan gå tilbage ned til David her,
og for David jeg kan faktisk sige, at David,
Vi kan bogstaveligt talt navngive variablen efter mig selv,
vil være af typen studerende.
Det ser måske lidt underligt, men det er ikke så forskellig
fra at erklære noget som en int eller en streng eller en flyder.
Det bare så sker at blive kaldt studerende nu,
og hvis jeg ønsker at sætte noget inde i denne struktur
Jeg nu nødt til at bruge et nyt stykke syntaks, men det er temmelig ligetil,
david.id = 123, david.name = "David" i hovedstaden D,
og david.house = "Mather,"
og nu kan jeg slippe af med denne ting her.
Bemærke, at vi har nu redesignet vores program i virkelig en langt bedre måde
i det nu vores program afspejler den virkelige verden.
>> Der er en real-verden opfattelse af en person eller en studerende.
Her har vi nu en C version af en person eller mere specifikt en elev.
Inde i denne person er disse relevante egenskaber,
ID, navn og hus, så Rob væsentlige bliver det samme hernede,
så studerende røve, og nu rob.id = 456,
rob.name = "Rob".
Den omstændighed, at den variable hedder Rob er en slags meningsløs.
Vi kunne have kaldt det x eller y eller z.
Vi har lige kaldte den Rob at være semantisk konsistent,
men virkelig navnet er inde i nævnte felt selv,
så nu har jeg det.
Også dette ikke føler sig som det bedste design i, at jeg har hårdt kodet David.
Jeg har hårdt kodet Rob.
Og jeg stadig nødt til at ty til nogle kopiere og indsætte hver gang jeg vil have nye variabler.
Desuden har jeg til tilsyneladende at give hver af disse variabler et navn,
selvom jeg vil meget hellere beskrive disse variabler
mere generisk som studerende.
>> Nu kan vi fusionere de idéer, der har arbejdet godt for os
og i stedet sige: "Ved du hvad, giv mig en variabel kaldet studerende,
og lad os har det være af størrelse 3, "så nu kan jeg forfine dette yderligere,
slippe af med den manuelt erklærede David,
og jeg kan i stedet sige noget lignende studerende [0] her.
Jeg kan så sige studerende [0] her,
studerende [0] her, og så videre, og jeg kan gå rundt
og rense det op for Rob.
Jeg kunne også gå om nu måske tilføje en løkke
og ved hjælp GetString og GetInt til rent faktisk at få disse værdier fra brugeren.
Jeg kunne gå om at tilføje en konstant, fordi det er generelt dårlig praksis
til hårdt kode nogle vilkårlige tal som 3 lige her
og så bare huske, at du skal sætte højst 3 studerende i det.
Det ville nok være bedre at bruge # define øverst på min fil
og faktor, der ud, så ja, lad mig gå videre og generalisere dette.
>> Lad mig åbne et eksempel, som er blandt nutidens
eksempler på forhånd, structs1.
Dette er en mere komplet program, der bruger # define op her
og siger, at vi bliver nødt til 3 studerende som standard.
Her er jeg erklære en klasse til en værdi af studerende,
så en klasse med elever, og nu er jeg bruger en løkke
bare for at gøre koden lidt mere elegant, befolker klasse
med brugerens input, gentage så fra i = 0 på op til studerende, hvilket er 3.
Og så vil jeg bede brugeren i denne version
hvad er den studerendes ID, og ​​jeg får det med GetInt.
Hvad er elevens navn, og så får jeg det med GetString.
Hvad er den studerendes hus? Jeg får det med GetString.
Og så i bunden her jeg netop besluttet at ændre
hvordan jeg udskriver disse ud og til rent faktisk at bruge en løkke,
og som jeg udskriver?
Ifølge kommentaren jeg udskriver nogen i Mather,
og det er det så Rob og Tommy og så videre-faktisk Tommys i Mather.
Tommy og David ville blive trykt i denne sag, men hvordan er denne arbejdsmetode?
Vi har ikke set denne funktion før, men tage et gæt på, hvad dette betyder.
Sammenligner strenge.
>> Det er lidt ikke-indlysende, hvordan den sammenligner strenge, fordi det viser sig
hvis det giver 0, som betyder, at strengene er ens.
Hvis den returnerer en -1, der betyder man kommer alfabetisk før den anden,
og hvis det returnerer en det betyder, at andre ord kommer alfabetisk
før den anden, og du kan se online eller på manden side
at se præcis, hvilken vej er der, men alt dette er nu gør, er det siger
hvis [i]. hus er lig med "Mather"
derefter gå videre og printe ud så og så er i Mather.
Men her er noget, vi ikke har set før, og vi vil komme tilbage til dette.
Jeg mindes ikke nogensinde at skulle gøre dette i nogen af ​​mine programmer.
Free er tilsyneladende under henvisning til hukommelse, hvilket frigør hukommelse,
men hvad hukommelse er jeg åbenbart frigøre i denne løkke i bunden af ​​dette program?
Det ser ud som jeg befri en persons navn
og en persons hus, men hvorfor er det?
>> Det viser sig, alle disse uger, at du har brugt GetString
vi har sådan været at indføre en fejl ind i hver eneste af dine programmer.
GetString ved design tildeler hukommelse, så det kan vende tilbage til dig en streng,
ligesom David, eller Rob, og du kan derefter gøre hvad du vil
med denne streng i dit program, fordi vi har reserveret hukommelsen for dig.
Problemet er al den tid, hver gang du ringer GetString
Vi har forfatterne GetString, er blevet anmodet operativsystemet
at give os en smule af RAM til denne streng.
Giv os en smule af RAM for denne næste streng.
Giv os nogle flere RAM til dette næste streng.
Hvad du, programmøren, har aldrig gjort
giver os, at hukommelsen tilbage,
så for disse flere uger alle de programmer, du har skrevet
have haft, hvad der kaldes en hukommelse spring, hvorved de fortsætte med at bruge
mere og mere hukommelse, hver gang du ringer GetString, og det er fint.
Vi bevidst gøre det i de første uger, fordi det ikke er så interessant
at skulle bekymre sig om, hvor strengen kommer fra.
Alt du ønsker, er det ord Rob at komme tilbage, når brugeren skriver det i.
>> Men bevæger sig fremad vi nu er nødt til at begynde at få mere sofistikerede om dette.
Hver gang vi tildeler hukommelse vi bedre til sidst aflevere den tilbage.
Ellers i den virkelige verden på din Mac eller pc, du måtte have lejlighedsvis oplevet
symptomer, hvor din computer er ved at gå i stå til sidst
eller den dumme spindende badebold er bare besat computerens
Hele opmærksomhed, og du kan ikke gøre noget.
Det kan forklares med et vilkårligt antal bugs, men blandt de mulige fejl
er ting kaldes memory leaks, hvorved en person, der skrev, at stykke software
du bruger ikke huske at frigøre hukommelse
at han eller hun spurgte operativsystemet for,
ikke bruger GetString, fordi det er en CS50 ting, men ved hjælp af lignende funktioner
der spørger operativsystemet for hukommelse.
Hvis du eller de skrue op og faktisk aldrig returnere at hukommelsen
et symptom på det kan være, at et program bremser og bremser og sinker
medmindre du huske at ringe gratis.
>> Vi vil komme tilbage til, hvornår og hvorfor du ville ringe gratis,
men lad os gå videre bare for god foranstaltning, og prøve at køre dette program.
Dette blev kaldt structs1, skal du indtaste.
Lad mig gå videre og køre structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, og vi ser David i Mather, Tommys i Mather.
Dette er blot en lille tilregnelighed kontrollere, at programmet virker.
Nu desværre dette program er lidt frustrerende i det
Jeg gjorde alt det arbejde, jeg har skrevet i 9 forskellige strenge, tryk Enter,
fik at vide, der var i Mather, men naturligvis jeg vidste hvem der var i Mather allerede fordi jeg har skrevet det.
Det ville være mindst rart, hvis dette program er mere som en database
og det faktisk husker, hvad jeg har skrevet i
så jeg aldrig igen nødt til at indtaste disse studerende registreringer.
Måske er det ligesom en registrarial system.
>> Vi kan gøre dette ved at bruge denne teknik, der kendes som en fil I / O, fil input og output,
en meget generisk måde at sige enhver tid, du ønsker at læse filer eller skrive filer
du kan gøre dette med et bestemt sæt af funktioner.
Lad mig gå videre og åbne dette eksempel structs2.c,
som er næsten identisk, men lad os se hvad det nu gør.
På toppen af ​​filen I erklærer en klasse.
Jeg derefter udfylde klassen med brugerens input,
så disse linjer kode er præcis som før.
Så hvis jeg rulle ned her jeg udskriver alle, der er i Mather vilkårligt gerne før,
men dette er en interessant ny funktion.
Disse linjer kode er nye, og de indfører noget her,
Fil, alle hætter, og det har * i her.
Lad mig flytte dette herovre, a * herovre så godt.
>> Denne funktion vi ikke har set før, fopen,
men det betyder fil åben, så lad os skimme gennem disse,
og det er noget, vi vil komme tilbage til i fremtidige psets,
men denne linje her hovedsagelig åbner en fil kaldet database,
og det specifikt åbner det på en sådan måde, at det kan gøre, hvad med det?
[Uhørlig-studerende]
Højre, så "w" betyder bare den fortæller operativsystemet
åbne denne fil på en sådan måde, at jeg kan skrive til den.
Jeg ønsker ikke at læse det. Jeg ønsker ikke at bare se på det.
Jeg ønsker at ændre det og tilføje ting potentielt til det,
og filen vil blive kaldt database.
Dette kunne kaldes noget.
Dette kunne være database.txt. Dette kunne være. Db.
Dette kunne være et ord som foo, men jeg vilkårligt valgte at navngive filen databasen.
Dette er en lille tilregnelighed kontrollere, at vi vil komme tilbage til i stor detalje over tid,
hvis fp, for fil pointer, ikke er lig med NULL betyder alt er godt.
>> Lang historie kort, funktioner som fopen nogle gange mislykkes.
Måske filen findes ikke. Måske er du ud af diskplads.
Måske har du ikke har tilladelse til mappen,
så hvis fopen returnerer null noget slemt er sket.
Omvendt, hvis fopen ikke returnerer null alle er godt
og jeg kan begynde at skrive til denne fil.
Her er et nyt trick.
Dette er en for-løkke, der er iteration over hver af mine studerende,
og det ser så ligner det, vi har gjort før,
men denne funktion er en fætter af printf kaldet fprintf for filen printf,
og bemærk det er anderledes på kun 2 måder.
Én, den starter med f stedet for p,
men derefter sin første argument er tilsyneladende hvad?
[Studerende] File. >> Det er en fil.
Denne ting kaldet fp, som vi vil i sidste ende drille hinanden, hvad en fil pointer er,
men for nu fp simpelthen er den fil, som jeg har åbnet,
så fprintf her siger udskrive denne brugers ID til filen, ikke til skærmen.
Udskriv brugerens navn til filen, ikke til skærmen,
huset til filen, ikke til skærmen, og derefter ned her, naturligvis,
lukker filen, og derefter ned her gratis hukommelsen.
>> Den eneste forskel mellem denne version 2 og version 1
er indførelsen af ​​fopen og denne fil med *
og denne opfattelse af fprintf, så lad os se hvad slutresultatet er.
Lad mig gå ind i min terminal vindue.
Lad mig løbe structs2, skal du indtaste.
Ligner alt er godt. Lad os køre structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, enter.
Ligner det opførte sig det samme, men hvis jeg nu gøre ls
mærke til, hvad filen er her blandt alle min kode, database,
så lad os åbne det, gedit af database, og se på det.
Det er ikke den mest sexede af filformater.
Det er virkelig et stykke af data linie efter linie per linje,
men dem af jer, der bruger Excel eller CSV-filer, kommaseparerede værdier,
Jeg kunne helt sikkert have brugt fprintf til stedet måske gøre noget som dette
så jeg kunne faktisk skabe hvad der svarer til en Excel-fil
ved at adskille tingene med kommaer, ikke kun nye linjer.
>> I dette tilfælde, hvis jeg i stedet havde brugt kommaer i stedet for nye linjer
Jeg kunne bogstaveligt åbne denne database fil i Excel, hvis jeg i stedet gjort det ser sådan ud.
Kort sagt, at vi nu har beføjelse til at skrive til filer
Vi kan nu begynde vedvarende data, holde det rundt på disken
så vi kan holde oplysninger omkring igen og igen.
Læg mærke til et par andre ting, der er nu en smule mere velkendt.
På toppen af ​​denne C-fil vi en typedef
fordi vi ønskede at skabe en datatype, der repræsenterer et ord,
så denne type kaldes ord, og inde i denne struktur
det er lidt amatør nu.
Hvorfor er et ord, der består af tilsyneladende et array?
Hvad er et ord bare intuitivt?
>> Det er et array af tegn.
Det er en sekvens af tegn tilbage til back to back.
Bogstaver i alle hætter sker for at være vi vilkårligt sige den maksimale længde
af et ord i ordbogen, som vi benytter til Scramble.
Hvorfor har jeg en +1?
Den null-tegn.
Recall når vi gjorde Bananagrams eksempel vi har brug for en særlig værdi
ved slutningen af ​​ordet for at holde styr
hvor ord faktisk endte, og da problemet indstillede specifikationen siger
her vi forbinder med et bestemt ord en boolesk værdi,
et flag, så at sige, sandt eller falsk.
Har du fundet dette ord allerede, fordi vi indser
vi virkelig har brug for en måde at huske ikke kun, hvad et ord er i Scramble
men uanset om du, den menneskelige, har fundet det
så hvis du finder ordet "det" du kan ikke bare skrive, skal du indtaste den, indtaster, skal du indtaste
og få 3 point, 3 point, 3 point, 3 point.
Vi ønsker at være i stand til at sortliste disse ord ved at sætte en bool
til sand, hvis du allerede har fundet det, og så det er derfor vi
indkapslet den i denne struktur.
>> Nu, her nede i Scramble der er denne anden struct kaldet ordbog.
Fraværende her er ordet typedef for i dette tilfælde
vi havde brug for at indkapsle ideen om en ordbog,
og en ordbog indeholder en hel masse ord,
som det fremgår af dette array, og hvor mange af disse ord er der?
Nå, uanset denne variabel kaldet størrelse siger.
Men vi skal bare have en ordbog.
Vi har ikke brug for en datatype kaldet ordbog.
Vi skal bare have en af ​​dem, så viser det sig i C
at hvis du ikke siger typedef, du bare sige struct, så inde i de krøllede parenteser
du lægger dine variabler, så du sætte navn.
Dette er at erklære en variabel kaldet ordbog
der ser sådan ud.
I modsætning hertil er disse linier skabe en genanvendelig datastruktur kaldet ord
at du kan oprette flere kopier af, ligesom vi oprettede
flere kopier af studerende.
>> Hvad betyder dette i sidste ende tillader os at gøre?
Lad mig gå tilbage til, lad os sige, en enklere eksempel fra enklere gange,
og lad mig åbne op, lad os sige, compare1.c.
Problemet her ved hånden er faktisk skrælle
laget af en streng og begynder at tage off disse støttehjul
fordi det viser sig, at en streng al denne tid
er, som vi lovede i uge 1 egentlig bare et kaldenavn,
et synonym fra CS50 bibliotek til noget, der ser lidt mere kryptisk,
char *, og vi har set denne stjerne før.
Vi så det i forbindelse med filerne.
>> Lad os nu se, hvorfor vi har gemt denne detalje i et stykke tid nu.
Her er en fil, der hedder compare1.c,
og den tilsyneladende beder brugeren om 2 strenge, s og t,
og så det forsøger at sammenligne disse strenge for ligestilling på linje 26,
og hvis de er lige det siger: "Du har skrevet det samme,"
og hvis de ikke er lige det siger: "Du har skrevet forskellige ting."
Lad mig gå videre og køre dette program.
Lad mig gå ind i min kilde bibliotek, gøre en compare1. Det kompileret okay.
Lad mig løbe compare1.
Jeg vil zoome ind, skal du indtaste.
Sig noget. HEJ.
Jeg vil sige noget igen. HEJ.
Jeg absolut ikke skrive forskellige ting.
>> Lad mig prøve det igen. BYE BYE.
Bestemt ikke anderledes, så hvad sker der her?
Nå, hvad der virkelig bliver sammenlignet i linje 26?
[Uhørlig-studerende]
Ja, så viser det sig, at en streng, datatype, er lidt af en hvid løgn.
En streng er en char *, men hvad er en char *?
En char *, som de siger, er en pointer,
og en pointer er faktisk en adresse,
en sum placering i hukommelsen, og hvis du tilfældigvis har indtastet et ord som HELLO,
husker fra tidligere diskussioner af strenge
det er ligesom ordet HELLO.
Husk, at et ord som HELLO kan repræsenteres
som en matrix af tegn som denne
og derpå med et specielt tegn for enden kaldes nul-karakteren,
som \ betegner.
Hvad er egentlig en streng?
Bemærk, at dette er flere bidder af hukommelse,
og i virkeligheden, er enden af ​​det kun kendt når du kigger gennem hele strengen
udkig efter den særlige null-tegn.
Men hvis det er en luns af hukommelsen fra min computers hukommelse,
lad os vilkårligt sige, at denne streng lige fået heldig,
og det fik placeret i begyndelsen af ​​min computers RAM.
Dette er byte 0, 1, 2, 3, 4, 5, 6 ...
>> Når jeg siger noget som GetString og jeg gør string s = GetString
hvad der virkelig bliver returneret?
For disse sidste mange uger, er hvad der virkelig bliver gemt i s
er ikke denne streng i sig selv, men i dette tilfælde, hvad der bliver gemt, er
tallet 0 fordi hvad GetString faktisk gør
er det ikke fysisk returnere en streng.
Det gør ikke engang virkelig gøre konceptuelle mening.
Hvad det gør tilbagevenden er et tal.
Dette antal er adressen på HELLO i hukommelsen,
og snor s derefter, hvis vi skrælle dette lag, er streng ikke eksisterer i virkeligheden.
Det er kun en forenkling i CS50 biblioteket.
>> Dette er virkelig er noget, der hedder char *.
Char giver mening, fordi hvad er et ord, ligesom HELLO?
Tja, det er en serie af chars, en række tegn.
Char * betyder adressen på en karakter,
så hvad betyder det at returnere en streng?
En dejlig og enkel måde for at returnere en streng
er snarere end at forsøge at regne ud, hvordan jeg vender tilbage til 5 eller 6 forskellige byte
Lad mig vende tilbage til den adresse, som byte?
Den første.
Med andre ord, lad mig give dig adressen på en karakter i hukommelsen.
Det er, hvad char * repræsenterer, adressen på en enkelt karakter i hukommelsen.
Ring denne variabel s.
Opbevares i s at bestemt adresse, som jeg vilkårligt sagt er 0,
bare for at holde tingene enkle, men i virkeligheden er det generelt et større antal.
>> Vent et øjeblik.
Hvis du kun giver mig adressen på det første tegn, hvordan jeg ved, hvad adressen er
af det andet tegn, den tredje, den fjerde og den femte?
[Uhørlig-studerende]
Du skal kun vide, hvor slutningen af ​​strengen er ved hjælp af denne handy trick,
så når du bruger noget som printf, hvad printf bogstaveligt tager som sit argument,
minde om, at vi bruger denne% s pladsholder, og så skal du passere i
den variabel, der er lagring af en streng.
Hvad du virkelig passerer er adressen på det første tegn i denne streng.
Printf bruger derefter en for-løkke eller en while-løkke med modtagelsen af ​​adresse,
for eksempel, 0 så lad mig gøre det nu,
printf ("% s \ n", s);
Når jeg kalder printf ("% s \ n", s), hvad jeg virkelig give printf med
er adressen på det første tegn i s, som i dette vilkårlig tilfælde er H.
>> Hvordan printf vide, hvad der præcist skal vises på skærmen?
Den person, der gennemføres printf implementeret en while-løkke eller en for-løkke
der siger ikke denne karakter lig med den særlige null-tegn?
Hvis ikke, udskrive det. Hvad med denne her?
Hvis ikke udskrive det, udskrive den, udskrive den, udskrive den.
Åh, denne ene er speciel. Afbryde udskrivningen og vende tilbage til brugeren.
Og det er bogstaveligt talt alt, hvad der er sket under hætten,
og det er en masse at fordøje på den første dag i en klasse,
men for nu er det virkelig den byggesten i at forstå alt
der har stået på indersiden af ​​vores computers hukommelse,
og til sidst vil vi drille dette fra hinanden med lidt hjælp
fra en af ​​vores venner på Stanford.
>> Professor Nick Parlante på Stanford har gjort dette vidunderlige video sekvens
fra alle mulige forskellige sprog, der indførte
denne lille Claymation karakter Binky.
Stemmen du er ved at høre på blot et par sekunder smagsprøve
er, at en Stanford professor, og du får
kun 5 eller 6 sekunder af dette lige nu,
men det er den note om, hvor vi vil slutte i dag
og begynde på onsdag.
Jeg giver dig Pointer Sjov med Binky, preview.
[♪ Music ♪] [Professor Parlante] Hey, Binky.
Vågn op. Det er tid til pointer sjov.
[Binky] Hvad er det? Lær om pointers?
Oh, goody!
>> Vi vil se dig på onsdag.
[CS50.TV]