[Powered by Google Translate] [Uke 4]
[David J. Malan] [Harvard University]
[Dette er CS50.] [CS50.TV]
>> Greit, dette er CS50, og dette er starten på uke 4,
og dette er en av de langsomste mulige sortering algoritmer.
Som var det at vi bare så det?
Det var boble sortere, for stor O (n ^ 2) + sum,
og faktisk vi er ikke de eneste i denne verden for å synes å vite
hva boble typen er eller dets kjøretid.
Dette var faktisk et intervju med Eric Schmidt fra Google
og tidligere senator Barack Obama bare noen få år siden.
>> Nå Senator, du er her på Google,
og jeg liker å tenke på formannskapet som et jobbintervju.
Nå er det vanskelig å få en jobb som president, og du går gjennom påkjenningene nå.
Det er også vanskelig å få en jobb hos Google.
Vi har spørsmål, og vi ber våre kandidater spørsmål,
og dette er fra Larry Schwimmer.
Dere tror jeg tuller? Det er rett her.
Hva er den mest effektive måten å sortere en million 32-bit heltall?
[Latter]
Godt
Jeg beklager. >> Nei, nei, nei, nei.
Jeg tror boblen slag ville være feil vei å gå.
>> Kom igjen, som fortalte ham dette?
Forrige uke husker vi tok en pause fra kode, i hvert fall for en dag,
og begynte å fokusere på noen høyere nivå ideer og problemløsning mer generelt
i sammenheng med søking og sortering,
og vi introdusert noe som vi ikke klapse dette navnet på forrige uke,
men asymptotisk notasjon, Big O, the Big Omega,
og noen ganger Big Theta notasjon, og disse var bare måter
å beskrive kjøretiden til algoritmer,
hvor mye tid det tar for en algoritme for å kjøre.
>> Og du husker kanskje at du snakket om kjøretiden i forhold til størrelsen
av input, som vi vanligvis kaller n, hva problemet kan være,
der n er antall personer i rommet,
antall sider i en telefonbok, og vi begynte å skrive ting ut
som O (n ^ 2) eller O (n) eller O (n log n),
og selv når regnestykket ikke helt fungerer så perfekt
og det var n ² - n / 2 eller noe sånt
Vi vil i stedet bare kaste bort noen av de lavere ordens ledd,
og motivasjonen er det at vi virkelig ønsker en
slags objektiv måte å vurdere
ytelsen til programmer eller ytelsen av algoritmer
at på slutten av dagen har ingenting å gjøre, for eksempel,
med hastigheten på datamaskinen i dag.
>> For eksempel, hvis du implementerer boble sortere,
eller du implementere flette sortere eller valg sorterer på dagens datamaskin,
en 2 GHz datamaskin, og du kjører den,
og det tar noen flere sekunder, neste år er det en 3 GHz
eller en 4 GHz datamaskin, og du kan da hevde at "Wow, min algoritme
er nå dobbelt så fort ", når det i realiteten det er åpenbart ikke tilfelle.
Det er bare maskinvaren har fått raskere, men datamaskinen
har ikke, og slik at vi virkelig ønsker å kaste bort ting som
multipler av 2 eller multipler av 3 når det gjelder å beskrive
hvor fort eller hvor sakte en algoritme er og egentlig bare fokusere
på n eller noen faktor av disse,
noe strøm derav som i tilfelle av slag fra siste uke.
Og husker at med hjelp av flettingen slag
vi var i stand til å gjøre så mye bedre enn boble sortere og utvalg sorter
og selv innsetting slag.
>> Vi kom ned til n log n, og igjen,
huske at log n vanligvis refererer til noe som vokser
saktere da n, så n log n så langt var bra
fordi det var mindre enn n ².
Men for å oppnå n log n med fletting slags
hva var den grunnleggende kimen til en idé om at vi måtte utnytte
at vi også leveraged tilbake i uke 0?
Hvordan gjorde vi takle sortering problemet cleverly med fletting slags?
Hva var nøkkelen innsikt, kanskje?
Noen i det hele tatt.
Ok, la oss ta et skritt tilbake.
Beskriv flette sortere i dine egne ord.
Hvordan fungerte det?
Ok, vi ro tilbake til uken 0.
Ok, ja.
[Uhørlig-student]
Ok, bra, så vi delte rekke tall i 2 deler.
Vi sortert hver av disse bitene, og da vi fusjonerte dem,
og vi har sett denne ideen før å ta et problem som er så stor
og hakking den opp i et problem som er så stor eller så stor.
>> Husker telefonboken eksempel.
Husker selv-telling algoritme fra uker siden,
så flette sort ble oppsummert av denne pseudokode her.
Når du får n elementer, først det var sunn fornuft sjekk.
Hvis n <2 så ikke gjør noe i det hele tatt
fordi hvis n <2 deretter n er åpenbart 0 eller 1,
og så hvis det er enten 0 eller 1 er det ingenting å sortere.
Du er ferdig.
Listen er allerede trivially sortert.
Men ellers hvis du har to eller flere elementer gå videre og dele dem
i 2 halvdeler, venstre og høyre.
Sortere hver av disse halvdeler, og deretter flette sortert halvdeler.
Men problemet her er at ved første øyekast dette føles som om vi punting.
Dette er en sirkulær definisjon i at hvis jeg har bedt deg om å sortere disse n elementer
og du forteller meg "All right, fine, vil vi sortere de n / 2 og de n / 2 elementer,"
så mitt neste spørsmål kommer til å være "Fine, hvordan du sortere n / 2 elementer?"
>> Men på grunn av strukturen av dette programmet,
fordi det er denne base case, så å si,
dette spesielle tilfellet som sier at hvis n er <noen fast verdi som 2 tilbake umiddelbart.
Ikke svar med det samme sirkulære svar.
Denne prosessen, vil dette syklisitet slutt ende.
Hvis jeg spør deg "Sorter disse n elementer", og sier du, "Fine, sortere disse n / 2,"
så du sier, "Fine, sort disse n / 4, n / 8, n/16,"
til slutt vil du dele med en stor nok antall
at du vil ha bare 1 element venstre, og da kan du si,
"Her, her er en sortert enkelt element."
Da glans av denne algoritmen opp her er å komme fra det faktum
at når du har alle disse individuelt sorterte lister,
som alle er av størrelse 1, som synes å være ubrukelig,
når du begynner å flette dem og flette dem
du bygge opp til slutt som Rob gjorde i videoen en endelig sortert liste.
>> Men denne ideen strekker seg langt utover sortering.
Det er denne ideen som er innebygd i dette programmet kjent som rekursjon,
ideen der du er et program,
og for å løse noen problemer du kaller deg selv,
eller sette i sammenheng med programmeringsspråk du er en funksjon,
og for å løse et problem, du funksjonen kaller deg selv
igjen og igjen og igjen, men du funksjonen
kan ikke kalle deg uendelig mange ganger.
Til slutt må du bunnen ut, så å si,
og har noen hardkodet basen tilstand som sier
på dette punktet slutte å kalle deg selv slik at hele prosessen
endelig stopper faktisk.
Hva betyr dette egentlig, å Recurse?
>> La oss se, hvis vi kan gjøre en enkel, trivielt eksempel med, sier
3 personer med meg her oppe på scenen, hvis noen er komfortable.
1, kom opp, 2 og 3.
Hvis du tre ønsker å komme opp her.
Hvis du ønsker å stå rett ved siden av meg her i en linje, antar at problemet for hånden
er telle svært trivially antall personer som er her.
Men ærlig, jeg er lei av alle disse telling eksempler.
Dette kommer til å ta litt tid, 1, 2, og prikk, prikk, prikk.
Det kommer til å ta en evighet.
Jeg vil heller bare punt dette problemet helt ved hjelp av-hva heter du?
Sara. >> Sara, all right.
Kelly. >> Kelly og?
>> Willy. >> Willy, Sara, Kelly, og Willy.
Akkurat nå har jeg blitt bedt om spørsmålet av noen
hvor mange mennesker er oppe på dette stadiet, og jeg har ingen anelse.
Dette er en veldig lang liste, og så i stedet jeg kommer til å gjøre dette trikset.
Jeg kommer til å be personen ved siden av meg å gjøre det meste av arbeidet,
og når hun er ferdig gjør det meste av arbeidet
Jeg kommer til å gjøre minst mulig arbeid mulig og bare legge en
til hva hennes svar er, så her vi går.
Jeg har blitt spurt om hvor mange personer som er på scenen.
Hvor mange mennesker er på scenen til venstre for deg?
Venstre for meg? >> Ok, men ikke jukse.
Det er bra, det er riktig, men hvis vi ønsker å fortsette denne logikken
la oss anta at du på samme måte vil punt dette problemet til venstre for deg,
så heller enn svar direkte gå videre og bare overlate oppgaven.
Å, hvor mange mennesker er til venstre for meg?
Hvor mange mennesker er til venstre?
1.
[Latter]
Ok, så 0, så hva nå Willy har gjort
er du har returnert svaret denne retningen sier 0.
Nå, hva skal du gjøre? >> 1.
Ok, så du er en, så sier du, "All right, jeg kommer til å legge en
til hva Willy telling var, "så 1 + 0.
Du er nå en så svaret på akkurat nå er-
1. >> Og mine ville være 2.
Bra, så du tar det forrige svaret på 1,
legge minimalt med arbeid du ønsker å gjøre, som er en.
Du har nå to, og du deretter gi meg hvilken verdi?
3, mener jeg, beklager, 2.
Bra.
>> Vel, vi hadde 0 til venstre.
Da vi hadde en, og så legger vi til 2,
og nå er du levere meg nummer 2,
og så jeg sier, ok, +1, 3.
Det er faktisk tre mennesker som står ved siden av meg på dette stadiet,
slik at vi kunne ha åpenbart gjort dette veldig lineært,
veldig mye i det åpenbare mote, men hva gjorde vi egentlig gjøre?
Vi tok et problem av størrelse 3 i utgangspunktet.
Vi brøt det ned i et problem med størrelse 2,
deretter et problem av størrelse 1, og deretter endelig base case
var virkelig, oh, det er ingen der,
på hvilket punkt Willy returnerte effektivt en hardkodet svar et par ganger,
og den andre ble deretter boblet opp, boblet opp, boblet opp,
og deretter ved å legge i denne ytterligere 1
Vi har implementert denne grunnleggende ideen om rekursjon.
>> Nå, i dette tilfellet det ikke virkelig løse et problem
noe mer effektivt da vi har sett så langt.
Men tenk om algoritmer vi har gjort på scenen så langt.
Vi hadde 8 stykker av papir på tavla,
på video når Sean var på utkikk etter nummer 7, og hva gjorde han egentlig gjøre?
Vel, han gjorde ikke gjøre noen form for splitt og hersk.
Han gjorde ikke noen form for rekursjon.
Heller han bare gjorde dette lineære algoritme.
Men da vi introduserte ideen om sortert tall på scenen leve forrige uke
da vi hadde dette instinktet for å gå til midten,
på hvilket punkt vi hadde en mindre liste av størrelse 4 eller en annen liste over størrelse 4,
og da vi hadde nøyaktig samme problem, så vi gjentok, gjentatt, gjentatt.
Med andre ord, recursed vi.
Tusen takk til våre 3 frivillige her for å demonstrere rekursjon med oss.
>> La oss se om vi ikke kan gjøre dette nå litt mer konkret,
løse et problem som igjen vi kunne gjøre ganske enkelt,
men vi vil bruke det som et springbrett til å implementere denne grunnleggende ideen.
Hvis jeg ønsker å beregne summering av en haug med tall,
for eksempel, hvis du passerer i nummer 3,
Jeg ønsker å gi deg verdien av sigma 3,
slik at summen av 3 + 2 + 1 + 0.
Jeg ønsker å komme tilbake svaret 6,
så vi vil implementere denne sigma funksjonen, denne oppsummeringen funksjonen
som, igjen, tar i inngang, og deretter returnerer summering
av dette nummeret hele veien ned til 0.
Vi kunne gjøre dette ganske enkelt, ikke sant?
Vi kunne gjøre dette med en slags looping struktur,
så la meg gå videre og få dette i gang.
>> Inkluder stdio.h.
La meg komme meg inn viktigste å jobbe med her.
La oss lagre dette som sigma.c.
Så jeg kommer til å gå inn her, og jeg kommer til å erklære en int n,
og jeg kommer til å gjøre følgende mens brukeren ikke samarbeider.
Mens brukeren ikke har gitt meg et positivt tall
la meg gå videre og be dem for n = GetInt,
og la meg gi dem noen instruksjoner om hva du skal gjøre,
så printf ("Positiv heltall please").
Bare noe relativt enkelt som dette slik at etter den tid traff vi linje 14
Vi har nå et positivt heltall antagelig i n.
>> Nå la oss gjøre noe med det.
La meg gå videre og beregne summering, så int sum = sigma (n).
Sigma er bare summering, så jeg bare skrive det i mer avansert måte.
Vi vil bare kalle det sigma der.
Det er summen, og nå skal jeg skrive ut resultatet,
printf ("Summen er% d \ n", sum).
Og så skal jeg tilbake 0 for godt mål.
Vi har gjort alt som dette programmet krever unntatt den interessante delen,
som er å faktisk implementere sigma funksjonen.
>> La meg gå ned hit til bunnen, og la meg erklære funksjon sigma.
Det er nødt til å ta en variabel som er av typen heltall,
og hva datatype ønsker jeg å returnere antagelig fra sigma?
Int, fordi jeg vil at den skal matche mine forventninger på linje 15.
Her la meg gå videre og gjennomføre dette
i en ganske grei måte.
>> La oss gå videre og si int sum = 0,
og nå skal jeg gå har litt for loop her
som kommer til å si noe sånt som dette,
for (int i = 0; I <= antall; i + +) sum + = i.
Og så skal jeg komme tilbake summen.
Jeg kunne ha gjennomført dette i en rekke måter.
Jeg kunne ha brukt en stund loop.
Jeg kunne ha hoppet med summen variabel hvis jeg virkelig ville,
men kort sagt, vi bare har en funksjon som hvis jeg ikke tabbe erklærer sum er 0.
Så det itererer fra 0 på opp gjennom antall,
og på hver iterasjon legger det at dagens verdi til sum og deretter returnerer sum.
>> Nå er det en liten optimalisering her.
Dette er trolig en bortkastet trinn, men det får så være. Det er greit for nå.
Vi er minst å være grundig og gå 0 hele veien videre opp.
Ikke veldig hardt og ganske grei,
men det viser seg at med sigma-funksjonen har vi samme mulighet
som vi gjorde her på scenen.
På scenen vi bare telles hvor mange som var ved siden av meg,
men i stedet hvis vi ønsket å telle antall 3 + 2 + 1
ned til 0 kunne vi likeledes punt til en funksjon
at jeg vil i stedet beskrive som rekursiv.
Her la oss sjekke en rask sunn fornuft gjør og sørge for at jeg ikke tabbe.
>> Jeg vet det er minst én ting i dette programmet at jeg gjorde feil.
Da jeg traff inn kommer jeg til å få noen form for roping på meg?
Hva skal jeg bli skreket til om?
Ja, jeg glemte prototypen, så jeg bruker en funksjon kalt sigma på linje 15,
men det er ikke erklært før linje 22, så jeg best proaktivt gå opp her
og erklære en prototype, og jeg vil si int sigma (int tall), og det er det.
Det er implementert i bunnen.
>> Eller en annen måte jeg kunne løse dette,
Jeg kunne flytte funksjonen der oppe, som ikke er dårlig,
men minst når programmene dine begynner å bli lang, ærlig,
Jeg tror det er noen verdi i å alltid ha hoved øverst
slik at du i leseren kan åpne filen og deretter umiddelbart se
hva programmet gjør uten å måtte søke gjennom det
på jakt etter den viktigste funksjonen.
La oss gå ned til min terminal-vinduet her, kan du prøve å lage sigma gjør sigma,
og jeg skrudd opp her også.
Implisitt deklarasjon av funksjon GetInt betyr at jeg har glemt å gjøre hva annet?
[Uhørlig-student]
Bra, så tilsynelatende en vanlig feil, så la oss sette dette opp her,
cs50.h, og nå la oss gå tilbake til min terminal-vinduet.
>> Jeg vil tømme skjermen, og jeg skal kjøre lage sigma.
Det synes å ha utarbeidet. La meg nå kjøre sigma.
Jeg skal skrive inn nummer 3, og jeg fikk 6, så ikke en streng sjekk,
men minst det synes å bli arbeider ved første øyekast, men la oss nå rive den fra hverandre,
og la oss utnytte faktisk ideen av rekursjon, igjen,
på en svært enkel sammenheng slik at om noen ukers tid
når vi begynner å utforske mer avansert datastrukturer enn arrays
Vi har et annet verktøy i verktøykasse med å
manipulere disse datastrukturer som vi skal se.
Dette er iterativ tilnærming, loopen tilnærming.
>> La meg i stedet nå gjøre dette.
La meg i stedet si at summering av tall
ned til 0 er virkelig det samme som
nummer + sigma (antall - 1).
Med andre ord, akkurat som på scenen punted jeg til hver av folk ved siden av meg,
og de i sin tur holdt punting før vi endelig bunnet ut på Willy,
som måtte returnere en hardkodet svar som 0.
Her nå er vi på samme måte punting til sigma
samme funksjon som egentlig heter, men nøkkelen innsikt her
er at vi ikke kaller sigma likt.
Vi er ikke bestått i n.
Vi er tydelig passerer i antall - 1,
så en litt mindre problem, litt mindre problem.
>> Dessverre er dette ikke helt en løsning ennå, og før vi fikse
hva som kan hoppe ut så opplagt at noen av dere
la meg gå videre og kjøre gjør.
Det synes å kompilere greit.
La meg kjøre sigma med 6.
Whoops, la meg kjøre sigma med 6.
Vi har sett dette før, om enn utilsiktet sist gang også.
Hvorfor fikk jeg denne kryptiske segmentering feil? Ja.
[Uhørlig-student]
Det er ingen base case, og mer spesifikt, hva kan ha skjedd?
Dette er et symptom på hva slags atferd?
Si det litt høyere.
[Uhørlig-student]
Det er en uendelig loop effektivt, og problemet med uendelige løkker
når de involverer rekursjon i dette tilfellet, en funksjon ringer selv,
hva skjer hver gang du ringer en funksjon?
Vel, tenker tilbake til hvordan vi lagt ut minnet i en datamaskin.
Vi sa at det er denne del av minnet som kalles stabelen som er på bunnen,
og hver gang du ringer en funksjon litt mer minne blir satt
på denne såkalte stack inneholder som fungerer lokale variabler eller parametere,
så hvis sigma kaller sigma samtaler sigma kaller sigma
kaller sigma hvor kommer denne historien ende?
>> Vel, det til slutt overskridelsene den totale mengden
minne som du har tilgjengelig til datamaskinen.
Du overkjørt segmentet som du er ment å holde seg innenfor,
og du får dette segmentering feil, dumpet kjerne,
og hva kjernen dumpet betyr er at jeg nå har en fil som heter kjerne
som er en fil som inneholder nuller og enere
som faktisk i fremtiden vil være nyttig diagnostisk.
Hvis det ikke er åpenbart for deg hvor feilen er
du kan faktisk gjøre litt av rettsmedisinske analyser, så å si,
på denne kjernen dump filen, som er igjen, bare en hel haug med nuller og enere
som representerer i hovedsak staten programmet i minnet
i det øyeblikket den krasjet på denne måten.
>> Reparasjonen her er at vi kan ikke bare blindt returnere sigma,
tallet + sigma av en litt mindre problem.
Vi trenger å ha noen form for base case her,
og hva bør base case sannsynligvis være?
[Uhørlig-student]
Ok, så lenge antallet er positivt vi skal faktisk tilbake dette,
eller sagt på en annen måte, hvis tall er, sier <= til 0
vet du hva, jeg skal gå videre og returnere 0,
mye som Willy gjorde, og annet, jeg kommer til å gå videre
og returnere dette, så det er ikke så mye kortere
enn iterativ versjon som vi pisket opp først med en for loop,
men merker at det er denne typen eleganse til det.
I stedet for å returnere en tall og utføre alt dette regnestykket
og legge opp ting med lokale variabler
du i stedet sier "Ok, hvis dette er en super enkelt problem,
som antall er <0, la meg straks tilbake 0 ".
>> Vi kommer ikke til å bry støtte negative tall,
så jeg kommer til hardt kode verdien 0..
Men ellers, for å gjennomføre denne ideen summere
alle disse tallene sammen du effektivt kan ta en liten matbit
ut av problemet, mye som vi gjorde her på scenen,
deretter punt resten av problemet til neste person,
men i dette tilfellet den neste person er selv.
Det er en identisk navn funksjon.
Bare gi det en mindre og mindre og mindre problem hver gang,
og selv om vi ikke har helt formaliserte ting i koden her
Dette er nøyaktig hva som skjer i uke 0 med telefonboken.
Dette er akkurat hva som skjer i de siste ukene med Sean
og med våre demonstrasjoner for å søke etter tall.
Det tar et problem, og dele det igjen og igjen.
>> Med andre ord, det er en måte nå med å oversette
denne virkelige verden konstruere, dette høyere nivå konstruere
av splitt og hersk og gjør noe igjen og igjen
i kode, så dette er noe vi vil se igjen over tid.
Nå, som en side, hvis du er ny på rekursjon du bør i det minste forstå nå
hvorfor dette er morsomt.
Jeg kommer til å gå til google.com,
og jeg kommer til å søke etter noen tips og triks på rekursjon, skriver.
Fortelle personen ved siden av deg hvis de ikke var ler akkurat nå.
Mente du rekursjon?
Mente du-ah, der vi går.
Ok, nå som resten av alle.
En liten påske egg innebygd sted der i Google.
Som en side, en av lenkene vi legger på kursets hjemmeside
for i dag er bare dette rutenettet av ulike sortering algoritmer,
noen som vi så på i forrige uke, men hva er fint om dette visualisering
som du prøver å vikle tankene dine rundt ulike ting knyttet til algoritmer
vet at du kan veldig lett nå starte med ulike typer innganger.
Inngangene alle reversert, inngangene meste sortert, inngangene tilfeldig og så videre.
Som du prøver å igjen, skille disse tingene i tankene dine
innse at denne nettadressen på kurset hjemmeside på Forelesninger siden
kan hjelpe deg grunn gjennom noen av disse.
>> I dag har vi endelig får til å løse dette problemet fra en stund tilbake,
som var at denne swap funksjonen bare ikke fungerte,
og hva var det fundamentale problemet med denne funksjonen swap,
målet som var igjen, for å utveksle en verdi her og her
slik at dette skjer?
Dette gjorde ikke faktisk fungerer. Hvorfor?
Ja.
[Uhørlig-student]
Nøyaktig, forklaringen på dette bugginess
bare var fordi når du ringer funksjoner i C
og disse funksjoner tar argumenter, som a og b her,
du passerer i kopier av hvilken verdi du gir til denne funksjonen.
Du er ikke å gi de opprinnelige verdiene selv,
så vi så dette i sammenheng med buggyc,
buggy3.c, som så litt noe sånt som dette.
>> Husker at vi hadde x og y initialisert til 1 og 2, henholdsvis.
Vi deretter skrives ut hva de var.
Jeg deretter hevdet at jeg var å bytte dem ved å kalle swap av x, y.
Men problemet var at bytte arbeidet,
men bare i omfanget av swap fungere selv.
Så snart vi traff linje 40 de byttet verdier
ble kastet bort, og så ingenting
i den opprinnelige funksjon viktigste var faktisk endret i det hele tatt,
så hvis du tenker tilbake da om hva dette ser ut i form av hukommelsen vår
dersom venstre side av brettet representerer-
og jeg skal gjøre mitt beste for at alle kan se dette-hvis dette venstre side av brettet
representerer, sier RAM, og stakken kommer til å vokse på opp på denne måten,
og vi kaller en funksjon som main, og viktigste har 2 lokale variabler, x og y,
la oss beskrive de som x her, og la oss beskrive disse som y her,
og la oss sette inn verdiene 1 og 2, så dette her er viktigste,
og når viktigste kaller swap-funksjonen i operativsystemet
gir swap-funksjonen sin egen skjærer minne på stakken,
sin egen ramme på stakken, så å si.
Det tildeler også 32 bits for disse ints.
Det skjer for å kalle dem a og b, men det er helt vilkårlig.
Det kunne ha kalt dem hva det vil, men hva skjer når main
samtaler swap er det tar dette 1, setter en kopi der, setter en kopi der.
>> Det er en annen lokal variabel i swap, men heter hva? >> Tmp.
Tmp, så la meg gi meg en annen 32 biter her,
og hva gjorde jeg i denne funksjonen?
Jeg sa int tmp får en, så en har en, så jeg gjorde dette da vi sist spilte med dette eksempelet.
Deretter en får b, så b er 2, så nå blir dette 2,
og nå b får temp, så temp er 1,
så nå b blir dette.
Det er flott. Det fungerte.
Men deretter så snart funksjonen returnerer
swap minne forsvinner effektivt, slik at det kan brukes på nytt
av en annen funksjon i fremtiden, og viktigste er selvsagt helt uforandret.
Vi trenger en måte fundamentalt løse dette problemet,
og i dag skal vi endelig ha en måte å gjøre dette der
Vi kan innføre noe som kalles en peker.
Det viser seg at vi kan løse dette problemet
ikke ved å passere i kopier av x og y
men i stedet ved å passere i det, tror du, til swap-funksjonen?
Ja, hva med adresse?
Vi har egentlig ikke snakket om adresser i mye detalj,
men hvis dette tavle representerer mitt datamaskinens minne
Vi kunne sikkert begynne nummereringen bytes i RAM min
og si dette er byte # 1, er denne byte # 2, byte # 3,
byte # 4, byte # ... 2000000000 hvis jeg har 2 GB RAM,
slik at vi kunne sikkert komme opp med noen vilkårlig nummerering ordning
for alle de individuelle bytes i datamaskinens minne.
>> Hva om stedet når jeg kaller swap
stedet for å passere på kopier av x og y
hvorfor ikke jeg i stedet passere i adressen x her,
adressen til y her, i hovedsak den postadresse
av x og y fordi da bytte, hvis han er informert
av adressen i minnet av x og y,
deretter bytte, hvis vi trent ham litt,
han kunne potensielt kjøre til den adressen, så å si,
x, og endre antall der, og deretter kjøre til adressen y,
endre antall der, selv mens faktisk ikke får kopier av disse verdiene selv,
så selv om vi snakket om dette som viktigste minne
og dette som swap minne den kraftige og farlige delen av C
er at hvilken som helst funksjon kan røre minnet overalt i datamaskinen,
og dette er kraftig i at du kan gjøre veldig fancy ting med dataprogrammer i C.
Dette er farlig fordi du kan også skru opp veldig enkelt.
Faktisk, for å en av de vanligste måtene for programmer disse dager utnyttes
fortsatt er for en programmerer ikke å innse
at han eller hun er slik en data
å være skrevet på et sted i minnet som ikke er beregnet.
>> For eksempel, erklærer han eller hun en rekke størrelse 10
men da prøver uhell å sette 11 bytes inn i den rekke minne,
og du begynner å berøre deler av minnet som ikke lenger er gyldige.
Bare for å kontekstuell dette, kan noen av dere vet at
programvaren ber ofte for serienumre eller registrering nøkler,
Photoshop og Word og programmer som dette.
Det finnes sprekker, som noen av dere vet, på nettet hvor du kan kjøre et lite program,
og voila, ikke mer forespørsel om et serienummer.
Hvordan er det å jobbe?
I mange tilfeller er disse tingene er ganske enkelt å finne i datamaskiner
tekst segmenter i datamaskinens faktiske nuller og enere
hvor er den funksjonen hvor serienummeret er forespurt,
og du overskrive den plassen, eller mens programmet kjører
du kan finne ut hvor nøkkelen er faktisk lagret
bruke noe som kalles en debugger, og du kan knekke programvare på den måten.
Dette er ikke å si at dette er vårt mål for de neste par dagene,
men det har svært reelle konsekvenser.
At man tilfeldigvis omfatte tyveri av programvare,
men det er også kompromiss av hele maskiner.
>> Faktisk, når nettsteder i disse dager er utnyttet
og kompromittert og data lekkasje og passord er stjålet
dette svært ofte knyttet til dårlig styring av ens minne,
eller, i tilfelle av databaser, unnlatelse forutse
motstandere inngang, så mer om det i ukene som kommer,
men for nå bare en sniktitt på hva slags skade du kan gjøre
ved ikke helt forstå hvordan ting fungerer under panseret.
La oss gå om å forstå hvorfor dette er brutt
med et verktøy som vil bli mer og mer nyttige
som våre programmer får mer komplisert.
Så langt når du har hatt en feil i programmet
hvordan har dere gått feilsøkt?
Hva har dine teknikker vært så langt, enten undervist av TF din
eller bare selvlært?
[Student] printf.
Printf, så printf har trolig vært din venn i at hvis du ønsker å se
hva som skjer på innsiden av programmet
du bare sette printf her, printf her, printf her.
Så du kjører den, og du får en hel haug med ting på skjermen
som du kan bruke til da utlede hva som faktisk går galt i programmet.
>> Printf en tendens til å være en veldig mektig ting,
men det er en svært manuell prosess.
Du må sette en printf her, en printf her,
og hvis du setter den inne i en løkke du kan få 100 linjer
av produksjonen som du deretter å sile gjennom.
Det er ikke en veldig brukervennlig eller interaktive mekanisme for debugging programmer,
men heldigvis finnes det alternativer.
Det er et program, for eksempel, heter GDB, GNU Debugger,
som er en liten uforståelige i hvordan du bruker den.
Det er litt komplisert, men ærlig,
dette er en av de tingene der hvis du putter i denne uken og neste
den ekstra timen til å forstå noe som GDB
det vil spare deg sannsynligvis flere titalls timer i det lange løp,
Så med det, la meg gi deg en teaser på hvordan dette ting fungerer.
>> Jeg er i min terminal-vinduet.
La meg gå videre og kompilere programmet, buggy3.
Det er allerede oppdatert.
La meg kjøre den akkurat som vi gjorde en stund tilbake, og faktisk er det brutt.
Men hvorfor er dette? Kanskje jeg skrudd opp swap-funksjon.
Kanskje det er a og b. Jeg er ikke helt flytte dem rundt riktig.
La meg gå videre og gjøre dette.
Snarere enn å bare kjøre buggy3 la meg i stedet kjøre dette programmet GDB,
og jeg kommer til å fortelle den til å kjøre buggy3,
og jeg kommer til å inkludere en kommandolinje argument,-tui,
og vi vil sette dette i fremtidige problemer på spec å minne.
Og nå svart og hvitt grensesnitt dukket opp som, igjen,
er litt overveldende i starten, fordi det er alt dette
garantiinformasjon her nede, men minst det er noe kjent.
I toppen av vinduet er min faktiske koden,
og hvis jeg blar opp her la meg bla til toppen av filen min,
og ja, det er buggy3.c, og legg merke til nederst i dette vinduet
Jeg har denne GDB ledeteksten.
>> Dette er ikke det samme som min normale John Harvard spørsmål.
Dette er et spørsmål som kommer til å tillate meg å kontrollere GDB.
GDB er et feilsøkingsverktøy.
En debugger er et program som lar deg gå gjennom
gjennomføring av programmet linje for linje for linje,
underveis gjør noe du vil programmet,
selv ringe funksjoner, eller ser, enda viktigere,
på ulike variable verdier.
La oss gå videre og gjøre dette.
Jeg kommer til å gå videre og skrive kjøre på GDB prompt,
så merker nederst til venstre på skjermen jeg har skrevet løpe,
og jeg har truffet inn, og hva gjorde det gjøre?
Det bokstavelig talt kjørte mitt program, men jeg gjorde ikke faktisk se mye gå på her
fordi jeg har faktisk ikke fortalt debugger
til pause på et bestemt tidspunkt.
Bare å skrive løp kjører programmet.
Jeg vet faktisk ikke se noe. Jeg kan ikke manipulere det.
>> I stedet la meg gjøre dette.
På dette GDB spørsmål la meg isteden skrive pause, inn.
Det er ikke det jeg mente å skrive.
La oss isteden skrive pause viktigste.
Med andre ord, jeg vil sette noe som kalles et stoppunkt,
som er treffende navn fordi det vil bryte eller pause
gjennomføring av programmet på det aktuelle stedet.
Viktigste er navnet på funksjonen min.
Legg merke til at GDB er ganske smart.
Det regnet ut at main skjer for å starte omtrent på linje 18
av buggy3.c, og deretter legge merke til her øverst til venstre
b + er rett ved siden av linje 18.
Det er minner meg om at jeg har satt et stoppunkt på linje 18.
Denne gangen når jeg skriver løp, jeg kommer til å kjøre mitt program
inntil den treffer den stoppunkt,
så vil programmet pause for meg på linje 18.
Here we go, kjøre.
Ingenting ser ut til å ha skjedd, men varsel nederst til venstre
starter programmet, buggy3, stoppunkt 1 i hovedvinduet til buggy3.c linje 18.
Hva kan jeg gjøre nå?
>> Merker jeg kan begynne å skrive ting som print,
ikke printf, print x, og nå er det rart.
$ 1 er bare en kuriositet, som vi skal se
hver gang du skriver ut noe du får en ny $ verdi.
Det er slik at du kan se tilbake på tidligere verdier i tilfelle,
men for nå hva print forteller meg er at verdien av x på dette punktet i historien
er tilsynelatende 134514032.
Hva? Hvor ble det selv kommer fra?
[Uhørlig-student]
Faktisk, dette er hva vi kaller en søppel verdi, og vi har ikke snakket om dette ennå,
men grunnen til at du initialisere variabler
er åpenbart at de har noen verdi som du vil de skal ha.
Men fangsten er huske at du kan erklære variabler
som jeg gjorde et øyeblikk siden i min sigma eksempel
uten egentlig å gi dem en verdi.
Huske hva jeg gjorde over her i sigma.
Jeg erklærte n, men hvilken verdi har jeg gi det?
Ingen, fordi jeg visste at i de neste par linjer
GetInt ville ta seg av problemet med å sette en verdi på innsiden av n.
>> Men på dette punktet i historien om linje 11
og linje 12 og linje 13 og linje 14
gjennom de flere linjer hva er verdien av n?
I C bare du ikke vet.
Det er generelt litt søppel verdi, noen helt tilfeldige tall
som er igjen i hovedsak fra noen tidligere funksjon
etter å ha blitt kjørt, slik som programmet kjører
huske at funksjonen blir funksjon, funksjon, funksjon.
Alle disse rammene blir satt på minnet, og de returnerer,
og akkurat som jeg foreslo med viskelæret deres minne er slutt gjenbrukes.
Vel, det bare skjer, slik at denne variabelen x i dette programmet
synes å ha inneholdt noen søppel verdi som 134514032
fra noen tidligere funksjon, ikke en som jeg skrev.
Det kan være noe som kommer effektivt med operativsystemet,
noen funksjon under panseret.
>> Ok, det er greit, men la oss nå gå videre til neste linje.
Hvis jeg skriver "neste" på min GDB spørsmål, og jeg traff inn,
merke til at uthevingen trekk ned til linje 19,
men den logiske konsekvensen er at linje 18
er nå ferdig utfører, så hvis jeg igjen skrive "print x"
Jeg skal nå se en, og faktisk, det gjør jeg.
Igjen er $ ting en måte GDB minner deg
hva historien utskrifter er at du har gjort.
Nå la meg gå videre og skrive ut y, og faktisk er y noen sprø verdi så vel,
men ikke så farlig fordi i linje 19 er vi i ferd med å tildele det
verdien 2, så la meg skrive "neste" igjen.
Og nå er vi på printf linje.
La meg gjøre print x.
La meg gjøre print y. Oppriktig, jeg får litt lei av å skrive ut dette.
La meg i stedet skrive "skjerm x" og "display y,"
og nå hver gang jeg skriver en kommando i fremtiden
Jeg vil bli minnet på hva som er x og y, hva er x og y, hva er x og y.
>> Jeg kan også, som en side, skriv inn "info lokalbefolkningen."
Info er en spesiell kommando.
Lokalbefolkningen betyr det viser meg de lokale variabler.
Bare i tilfelle jeg glemmer eller er dette en gal, komplisert funksjon
at jeg eller noen andre skrev info lokalbefolkningen vil fortelle deg
hva er alle lokale variabler inne denne lokale funksjonen
som du kanskje bryr seg om hvis du ønsker å rote rundt.
Nå er printf om å utføre, så la meg gå videre og bare skrive "neste".
Fordi vi er i dette miljøet vi ikke egentlig se det
utføre her nede, men merker det blir litt mangled her.
Men merker det overordnede skjermen der,
så det er ikke en perfekt program her, men det er greit fordi jeg alltid kan rote rundt
ved hjelp av print hvis jeg vil.
>> La meg skrive neste gang, og nå her er den interessante delen.
På dette punktet i historien y er 2, og x er 1,
som foreslått her, og igjen,
Årsaken til dette er automatisk visning nå er fordi jeg brukte kommandoen
Displayet x og Y vises, så det øyeblikket jeg skriver neste
i teorien x og y skal bli byttet.
Nå vet vi allerede at ikke kommer til å være tilfelle,
men vi får se i et øyeblikk hvor vi kan dykke dypere for å finne ut hvorfor det er sant.
Neste, og dessverre er y fortsatt 2 og x er fortsatt en, og jeg kan bekrefte så mye.
Print x, print y.
Faktisk har ingen bytte faktisk skjedde, så la oss starte dette over.
Klart swap er brutt.
La oss isteden skrive "run" igjen.
La meg si ja, jeg vil starte det fra begynnelsen, skriver.
>> Nå er jeg tilbake opp på linje 18.
Nå legge merke x og y er søppel verdiene igjen.
Neste, neste, neste, neste.
Hvis jeg får lei jeg kan også bare skrive n for neste.
Du kan forkorte det til kortest mulig sekvens av tegn.
Swap er nå brutt.
La oss dykke i, så i stedet for å skrive neste,
nå skal jeg til å skrive trinn, slik at jeg stepping innsiden av denne funksjonen
slik at jeg kan gå gjennom det, så jeg traff trinn og deretter inn.
Legg merke til at de fremhever hopper ned lavere i mitt program til linje 36.
Nå hva er de lokale variabler?
Info lokalbefolkningen.
Ingenting ennå fordi vi ikke har fått til den linjen,
så la oss gå videre og si "Next".
Nå synes vi å ha tmp, print tmp.
Søppel verdi, ikke sant? Jeg tror det.
Hva med ut en, print b, 1 og 2?
I et øyeblikk, så snart jeg skriver neste gang
tmp kommer til å ta på en verdi på 1, forhåpentligvis,
fordi tmp kommer til å bli tildelt verdien av en.
>> Nå la oss gjøre ut en, print b,
men nå ut tmp, og det er faktisk en.
La meg gjøre videre. La meg gjøre videre.
Jeg er ferdig med swap-funksjonen.
Jeg er fortsatt inne i den på linje 40, så la meg skrive en,
print b, og jeg bryr meg ikke hva tmp er.
Det ser ut som swap er riktig når det gjelder å bytte a og b.
Men hvis jeg nå skrive neste, jeg hoppe tilbake til linje 25,
og selvfølgelig, hvis jeg skriver i x og print y
de er fortsatt uendret, så vi har ikke løst problemet.
Men diagnostisk nå kanskje med denne GDB program
Vi har i det minste fått ett skritt nærmere å forstå
hva som går galt uten å søppel vår kode ved å sette en printf her,
printf her, printf her og deretter kjøre den igjen og igjen
prøver å finne ut hva som går galt.
>> Jeg kommer til å gå videre og avslutte ut av dette helt med å slutte.
Det kommer til å så si: "Quit likevel?" Ja.
Nå er jeg tilbake på mitt normale spørsmål, og jeg er ferdig med GDB.
Som en side, trenger du ikke å bruke denne-tui flagg.
Faktisk, hvis du utelater det du får i hovedsak den nederste halvdelen av skjermen.
Hvis jeg skriver pause viktigste og deretter kjøre
Jeg kan fremdeles kjøre mitt program, men hva det vil gjøre er mer ordrett
bare vise meg den aktuelle linjen, ett om gangen.
The-tui, tekstlig brukergrensesnitt,
bare viser deg mer av programmet på en gang, noe som er nok litt konseptuelt enklere.
Men faktisk, jeg kan bare gjøre neste, neste, neste,
og jeg kommer til å se en linje av gangen, og hvis jeg virkelig ønsker å se hva som skjer
Jeg kan skrive listen og se en hel haug med nabokommunene linjer.
>> Det er en video som vi har bedt om at du ser for problem sett 3
der Nate dekker noen av vanskelighetene med GDB,
og dette er en av de tingene, ærlig, der noen ikke-triviell andel av dere
vil aldri røre GDB, og som vil være en dårlig ting
fordi bokstavelig vil du ende opp med å tilbringe mer tid senere dette semesteret
jakte ned bugs så du ville gjort hvis du satt i det halv time / time
denne uken og neste læring å bli komfortabel med GDB.
Printf var din venn.
GDB skal nå være din venn.
>> Eventuelle spørsmål om GDB?
Og her er en rask liste over noen av de mest kraftfulle og nyttige kommandoer.
Ja. >> Kan du skrive ut en streng?
Kan du skrive ut en streng? Absolutt.
Det trenger ikke å bare være heltall.
Hvis en variabel s er en streng skriver du bare inn i print s.
Den vil vise deg hva som strengvariabel er.
[Uhørlig-student]
Det vil gi deg adresse og selve strengen.
Den vil vise deg begge deler.
Og en siste ting, bare fordi disse er godt å vite også.
Backtrace og ramme, la meg dykke inn i dette siste gang,
nøyaktig samme program med GDB.
La meg gå videre og kjøre den tekstlige brukergrensesnitt versjon,
bryte viktigste.
La meg gå videre og kjøre igjen. Her er jeg.
Nå la meg gå neste, neste, neste, neste, neste, step, skriver.
>> Og nå antar jeg er nå i swap bevisst, men jeg liker "Damn, hva var verdien av x?"
Jeg kan ikke gjøre x lenger.
Jeg kan ikke gjøre y fordi de ikke er i omfang.
De er ikke i sammenheng, men ikke noe problem.
Jeg kan skrive tilbakesporing.
Som viser meg alle de funksjonene som har utført opp til dette tidspunktet.
Legg merke til at en på bunnen, viktigste, på linje med hoved
være på bunnen av bildet her.
Det faktum at swap er over det på linje med swap være over den i minnet her,
og hvis jeg ønsker å komme tilbake til hovedsiden midlertidig jeg kan si "frame".
Hvilket nummer? Viktigste er rammen # 1.
Jeg kommer til å gå foran og si "frame 1".
>> Nå er jeg tilbake i viktigste, og jeg kan skrive ut x, og jeg kan skrive ut y,
men jeg kan ikke skrive ut en eller b.
Men jeg kan hvis jeg sier: "OK, vent litt. Hvor var swap?"
La meg gå videre og si "frame 0".
Nå er jeg tilbake der jeg ønsker å være, og som en side,
det er andre kommandoer også, som om du virkelig får lei skrive neste, neste, neste, neste,
du kan generelt si ting som "neste 10", og som vil gå gjennom de neste 10 linjene.
Du kan også skrive "fortsett" når du virkelig får lei stepping gjennom den.
Fortsett vil kjøre programmet uten avbrudd til den treffer en annen stoppunkt,
enten i en sløyfe eller senke ned i programmet.
>> I dette tilfellet fortsatte vi til slutten, og programmet gått som normalt.
Dette er en fancy måte, dårligere prosess.
Bare programmet gått som normalt.
Mer om det i videoen og i debugging økter fremover.
Det var mye.
La oss ta vår 5-minutters pause her, og vi vil komme tilbake med structs og filer.
>> Hvis du har dykket inn i denne ukens pset allerede
du vet at vi bruker i fordelingen koden,
kildekoden som vi leverer til deg som et utgangspunkt, noen nye teknikker.
Spesielt introduserte vi denne nye nøkkelordet kalt struct, for struktur,
slik at vi kan lage tilpassede variabler sorterer.
Vi har også innført begrepet fil I / O, fil inngang og utgang,
og dette er, slik at vi kan spare staten
av Scramble bord til en fil på disk
slik at undervisningen stipendiater og jeg kan forstå
hva som skjer på innsiden av programmet uten å måtte manuelt spille
dusinvis av spill av Scramble.
Vi kan gjøre dette mer automatedly.
>> Denne ideen om en struct løser en ganske overbevisende problem.
Anta at vi ønsker å gjennomføre noen program
som holder liksom styr på informasjon om studenter,
og studenter kan ha, for eksempel en ID, et navn
og et hus på et sted som Harvard, så disse er 3 stykker av informasjon
Vi ønsker å holde rundt, så la meg gå videre og begynne å skrive et lite program her,
inkludere stdio.h.
La meg gjøre inkludere cs50.h.
Og deretter starte min viktigste funksjon.
Jeg vil ikke bry deg med noen kommandolinjeargumenter,
og her jeg vil ha en student, så jeg kommer til å si
en student har et navn, så jeg kommer til å si "string navn."
Så jeg kommer til å si en student har også en ID, så int id,
og en student har et hus, så jeg også kommer til å si "string hus."
Så jeg skal bestille disse litt mer renslig som dette.
Ok, nå har jeg tre variabler som å representere en student, så "en student."
>> Og nå vil jeg fylle disse verdiene, så la meg gå videre og si noe sånt
"Id = 123".
Navnet kommer til å bli David.
La oss si huset kommer til å få Mather,
og da kommer jeg til å gjøre noe vilkårlig som printf ("% s,
hvis ID er% d, bor i% s.
Og nå, hva jeg ønsker å plugge inn her, den ene etter den andre?
Navn, id, hus, return 0.
Ok, med mindre jeg skrudd opp et sted her
Jeg tror vi har en ganske god program som lagrer én student.
Selvfølgelig, dette er ikke alle som interessant. Hva om jeg ønsker å ha to studenter?
Det er ingen big deal. Jeg kan støtte 2 personer.
La meg gå videre og markere dette og gå ned her,
og jeg kan si "id = 456" for en som Rob som bor i Kirkland.
>> Ok, vent, men jeg kan ikke kalle disse den samme,
og det ser ut som jeg er nødt til å kopiere dette,
så la meg si at disse vil være Davids variabler,
og la meg få noen eksemplarer av disse for Rob.
Vi vil kalle disse Rob, men dette er ikke til å fungere nå
fordi jeg har-vent, la oss endre meg til ID1, navn1 og House1.
Rob vil være 2, 2.
Jeg har fått til å endre dette her, her, her, her, her, her.
Vent, hva om Tommy? La oss gjøre dette igjen.
Selvfølgelig hvis du fortsatt tror dette er en god måte å gjøre dette på, er det ikke,
så kopiere / lime dårlig.
Men vi løste dette for en uke siden.
>> Hva var vår løsning når vi ønsket å ha flere forekomster av samme datatype?
[Studenter] En rekke.
En matrise, så la meg prøve å rydde opp.
La meg gjøre noen plass for meg selv på toppen, og la meg i stedet gjøre dette her.
Vi vil kalle disse menneskene, og i stedet skal jeg si "int IDer,"
og jeg kommer til å støtte tre av oss for nå.
Jeg kommer til å si "strengnavn," så skal jeg støtte 3 av oss,
og da kommer jeg til å si "streng hus," og jeg kommer til å støtte tre av oss.
Nå i her i stedet for David få sine egne lokale variabler
Vi kan bli kvitt dem.
Det føles bra at vi rengjøring dette opp.
Da kan jeg si David kommer til å være [0] og navn [0]
og hus [0].
Og så Rob vi kan tilsvarende spare på dette.
La oss sette dette ned her, så han kommer til å vilkårlig være ids [1].
Han kommer til å være navn [1],
og deretter til slutt, hus [1].
>> Fortsatt litt kjedelig, og nå må jeg finne ut av dette,
så la oss si "navn [0], id [0], hus [0],
og la oss pluralize dette.
Ids, IDS, IDer.
Og igjen, jeg gjør det, så igjen, jeg er allerede ty til å kopiere / lime igjen,
så oddsen er det er en annen løsning her.
Jeg kan sikkert rydde opp videre med en sløyfe eller noe sånt,
så kort sagt, er det litt bedre, men fortsatt føles som
Jeg ty til å kopiere / lime, men selv dette, hevder jeg,
er egentlig ikke fundamentalt riktig løsning fordi
hva om en gang vi bestemmer vet du hva?
Vi virkelig burde ha blitt lagring e-postadresser for David og Rob
og alle andre i dette programmet.
Vi bør også lagre telefonnumre.
Vi bør også lagre nødtelefon tall.
Vi har alle disse delene av data som vi ønsker å lagre,
så hvordan kan du gå om du gjør det?
>> Du erklærer en annen rekke på toppen, og deretter manuelt legge
en e-postadresse [0], e-postadresse [1]
for David og Rob og så videre.
Men det er egentlig bare en antagelse bak denne designen
at jeg bruker ære systemet å vite at
[I] i hver av de flere matriser
bare så skjer for å referere til den samme personen,
så [0] i ids er nummer 123,
og jeg kommer til å anta at navnene [0]
er den samme personens navn og hus [0]
er den samme person hus og så videre for alle de ulike matriser som jeg skaper.
Men merker at det er ingen fundamental sammenheng
blant de tre biter av informasjon, id, navn og hus,
selv om foretaket vi prøver å modellere i dette programmet er ikke arrays.
Arrays er nettopp dette programmatiske måte å gjøre dette.
Hva vi egentlig ønsker å modellere i vårt program er en person
som David, en person som Rob innsiden av som
eller innkapsle er et navn og ID og et hus.
>> Kan vi noe uttrykke denne ideen om innkapsling
hvor en person har en ID, et navn og et hus
og ikke ty til virkelig dette hack der vi bare
stole på at braketten noe
refererer til samme menneskelige enhet i hver av disse uensartede arrays?
Vi kan faktisk gjøre dette.
La meg gå over main for nå, og la meg lage min egen datatype
for egentlig første gang.
Vi brukte denne teknikken i Scramble,
men her jeg kommer til å gå videre og lage en datatype,
og vet du hva, jeg kommer til å kalle det student eller person,
og jeg kommer til å bruke typedef for definere en type.
Jeg kommer til å si at dette er en struktur,
og så denne strukturen kommer til å være av typen student, vil vi si,
selv om det er litt datert nå for meg.
Vi vil si "int id."
Vi vil si "string navn."
Så får vi si "string huset,"
så nå i slutten av disse få linjer med kode
Jeg har nettopp lært clang at det eksisterer
en datatype foruten ints, foruten strenger, foruten dobler, foruten flyter.
>> Som i dette øyeblikk i tid linje 11, er det nå en ny datatype kalt studenter,
og nå kan jeg erklære en student variabel hvor jeg vil,
så la meg bla nedover her til folk.
Nå kan jeg bli kvitt dette, og jeg kan gå tilbake til David her,
og for David kan jeg faktisk si at David,
Vi kan bokstavelig talt kalle variabelen etter meg selv,
kommer til å være av typen student.
Dette kan se litt rart, men dette er ikke så forskjellig
fra å erklære noe som int eller en streng eller en flåte.
Det bare så skjer for å bli kalt student nå,
og hvis jeg ønsker å sette noe på innsiden av denne strukturen
Jeg har nå å bruke et nytt stykke av syntaks, men det er ganske grei,
david.id = 123, david.name = "David" i hovedstaden D,
og david.house = "Mather,"
og nå kan jeg bli kvitt denne ting her.
Merker vi nå har redesignet vårt program i virkelig en mye bedre måte
i at nå vårt program gjenspeiler den virkelige verden.
>> Det er en reell oppfatningen av en person eller en student.
Her har vi nå en C-versjon av en person eller mer spesifikt en student.
Innsiden av den personen er disse relevante egenskaper,
ID, navn og hus, så Rob blir i hovedsak de samme her nede,
så student rob, og nå rob.id = 456,
rob.name = "Rob".
Det faktum at variabelen kalles Rob er liksom meningsløst.
Vi kunne ha kalt det x eller y eller z.
Vi kalte det Rob å være semantisk konsekvent,
men egentlig navnet er inne i feltet selv,
så nå har jeg denne.
Dette også føles ikke som den beste designen i at jeg har hardkodet David.
Jeg har hardkodet Rob.
Og jeg har fortsatt å ty til noen kopier og lim hver gang jeg vil ha nye variabler.
Videre har jeg til tilsynelatende gi hver av disse variablene et navn,
selv om jeg vil mye heller beskrive disse variablene
mer generelt som studenter.
>> Nå kan vi slå sammen ideene som har jobbet godt for oss
og i stedet si: "Vet du hva, gi meg en variabel kalt studenter,
og la oss være det har med størrelse 3, "så nå jeg kan gjøre dette videre,
bli kvitt den manuelt erklærte David,
og jeg kan i stedet si noe sånt studenter [0] her.
Da kan jeg si studenter [0] her,
studenter [0] her, og så videre, og jeg kan gå rundt
og rydde opp for Rob.
Jeg kan også gå om nå kanskje legge en sløyfe
og bruke GetString og GetInt å faktisk få disse verdiene fra brukeren.
Jeg kunne gå om å legge en konstant fordi dette er generelt dårlig praksis
til hardt kode noen vilkårlig antall som 3 her
og så bare husk at du bør sette mer enn 3 studenter i den.
Det ville trolig være bedre å bruke # define på toppen av filen min
og faktor det ut, så ja, la meg gå videre og generalisere dette.
>> La meg åpne opp et eksempel som er blant dagens
eksempler på forhånd, structs1.
Dette er en mer komplett program som bruker # define opp her
og sier at vi kommer til å ha tre studenter som standard.
Her jeg erklære en klasse verdt av studenter,
så et klasserom med elever, og nå er jeg bruke en løkke
bare for å gjøre koden litt mer elegant, fylle klassen
med brukerens input, så iterate fra i = 0 på opp til studenter, som er tre.
Og da jeg be brukeren i denne versjonen
hva er studentens ID, og ​​jeg får det med GetInt.
Hva er studentens navn, og da får jeg den med GetString.
Hva er studentens huset? Jeg får det med GetString.
Og så nederst her bare jeg besluttet å endre
hvordan jeg skriver disse ut og å faktisk bruke en loop,
og hvem er jeg skriver ut?
Ifølge kommentaren jeg skriver noen i Mather,
og det er det så Rob og Tommy og så videre-faktisk Tommy i Mather.
Tommy og David ville bli trykt i dette tilfellet, men hvordan er dette fungerer?
Vi har ikke sett denne funksjonen før, men ta en gjetning på hva dette betyr.
Sammenligner strenger.
>> Det er litt ikke-innlysende hvordan det sammenligner strenger fordi det viser seg
hvis den gir 0 som betyr at strengene er like.
Hvis den gir en -1 som betyr en kommer alfabetisk før den andre,
og hvis det returnerer en som betyr at den andre ord kommer alfabetisk
før den andre, og du kan se på nettet eller på mannen siden
for å se nøyaktig hvilken vei som er, men alt dette er nå gjør er det å si
hvis [i]. huset er lik "Mather"
deretter gå videre og skrive ut så og så er i Mather.
Men her er noe vi ikke har sett før, og vi vil komme tilbake til dette.
Jeg kan ikke huske noen gang å måtte gjøre dette i noen av mine programmer.
Gratis er tilsynelatende refererer til minnet, frigjør minne,
men hva minne er jeg tydeligvis frigjør i denne sløyfen nederst i dette programmet?
Det ser ut som jeg befri en persons navn
og en person i huset, men hvorfor er det?
>> Det viser seg alle disse ukene du har brukt GetString
Vi har slags vært innføre en bug i hver eneste en av dine programmer.
GetString av design tildeler minne slik at den kan gå tilbake til deg en streng,
som David, eller Rob, og du kan deretter gjøre hva du vil
med strengen i programmet fordi vi har reservert minne for deg.
Problemet er hele tiden hver gang du ringer GetString
vi, forfatterne av GetString, har vært å spørre operativsystemet
å gi oss en bit av RAM for denne strengen.
Gi oss litt av RAM for dette neste streng.
Gi oss litt mer RAM for dette neste streng.
Hva du, programmerer, har aldri gjort
er å gi oss at hukommelsen tilbake,
så for disse flere uker alle programmene du har skrevet
har hatt det som kalles en minne sprang der de fortsette å bruke
mer og mer minne hver gang du ringer GetString, og det er fint.
Vi bevisst gjøre det i de første ukene fordi det ikke er så interessant
å måtte bekymre deg om hvor strengen kommer fra.
Alt du ønsker er ordet Rob å komme tilbake når brukeren skriver det i.
>> Men fremover vi nå må begynne å få mer sofistikerte om dette.
Hver gang vi allokere minne vi bedre til slutt levere det tilbake.
Ellers i den virkelige verden på din Mac eller PC kan du ha behov opplevd
symptomer der datamaskinen er sliping til å stoppe opp etter hvert
eller dum spinnende badeball er bare opptar datamaskinens
Hele oppmerksomhet og du kan ikke gjøre ting.
Som kan forklares av en rekke bugs, men blant de mulige feilene
er ting som kalles minnelekkasjer der noen som skrev at stykke programvare
du bruker ikke huske å frigjøre minne
at han eller hun spurte operativsystemet for,
ikke bruker GetString, fordi det er en CS50 ting, men med lignende funksjoner
som spør operativsystemet for minne.
Hvis du eller de skru opp og aldri komme tilbake som minne
et symptom på at kan være at et program bremser og bremser og bremser ned
med mindre du huske å ringe gratis.
>> Vi vil komme tilbake til når og hvorfor du vil ringe gratis,
men la oss gå videre bare for godt mål, og prøve å kjøre dette programmet.
Dette ble kalt structs1, skriver.
La meg gå videre og kjøre structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, og vi ser Davids i Mather, Tommy i Mather.
Dette er bare et lite sunn fornuft sjekk at programmet fungerer.
Nå, dessverre, er dette programmet litt frustrerende i det
Jeg gjorde alt det arbeidet, skrev jeg i 9 forskjellige strenger, trykk enter,
ble fortalt som var i Mather, men åpenbart jeg visste hvem var i Mather allerede fordi jeg skrev den.
Det ville være minst fint om dette programmet er mer som en database
og det husker faktisk hva jeg har skrevet i
så jeg aldri igjen å legge inn disse studentene poster.
Kanskje det er som en registrarial system.
>> Vi kan gjøre dette ved hjelp av denne teknikken kalles fil I / O, fil inngang og utgang,
en svært generisk måte å si når du ønsker å lese filer eller skrive filer
du kan gjøre dette med et bestemt sett av funksjoner.
La meg gå videre og åpne dette eksempelet structs2.c,
som er nesten identisk, men la oss se hva den nå gjør.
På toppen av filen erklærer jeg en klasse av studenter.
Jeg så fylle den klassen med brukerens input,
så disse linjene med kode er akkurat som før.
Så hvis jeg ruller nedover her skriver jeg ut alle som er i Mather vilkårlig som før,
men dette er en interessant ny funksjon.
Disse linjene med kode er ny, og introdusere de noe her,
Fil, alle caps, og det har * i her også.
La meg flytte dette over her, en * over her også.
>> Denne funksjonen har vi ikke sett før, fopen,
men det betyr fil åpen, så la oss skumme gjennom disse,
og dette er noe vi vil komme tilbake til i fremtidige psets,
men denne linjen her åpner egentlig en fil som heter database,
og det åpner spesielt det på en slik måte at det kan gjøre det til det?
[Uhørlig-student]
Høyre, så "w" betyr bare det forteller operativsystemet
åpne denne filen på en slik måte at jeg kan skrive til den.
Jeg ønsker ikke å lese den. Jeg ønsker ikke å bare se på det.
Jeg ønsker å endre den og legge ting potensielt til det,
og filen kommer til å bli kalt database.
Dette kan kalles noe.
Dette kan være database.txt. Dette kan være. Db.
Dette kan være et ord som foo, men jeg vilkårlig valgte å navngi filen database.
Dette er en liten sunn fornuft sjekk at vi vil komme tilbake til i stor detalj over tid,
Hvis fp, for filpekeren, ikke lik NULL som betyr alt er vel.
>> Lang historie kort, funksjoner som fopen noen ganger mislykkes.
Kanskje filen ikke eksisterer. Kanskje du er ute av diskplass.
Kanskje du ikke har tillatelse til denne mappen,
så hvis fopen returnerer null noe dårlig skjedde.
Derimot, hvis fopen ikke returnerer null alt er bra
og jeg kan begynne å skrive til denne filen.
Her er et nytt triks.
Dette er en for løkke som er iterating over hver av mine studenter,
og dette ser så likt det vi har gjort før,
men denne funksjonen er en fetter av printf kalt fprintf for fil printf,
og merker det er annerledes i bare 2 måter.
One, begynner det med f stedet for p,
men da er det første argumentet er tilsynelatende hva?
[Studenter] File. >> Det er en fil.
Denne tingen kalt fp, som vi vil til slutt erte hverandre hva en filpekeren er,
men for nå fp representerer bare filen som jeg har åpnet,
så fprintf her sier skrive denne brukerens ID til filen, ikke til skjermen.
Skriv ut brukerens navn til filen, ikke til skjermen,
huset til filen, ikke til skjermen, og deretter ned her, selvsagt,
lukke filen, og deretter ned her gratis minnet.
>> Den eneste forskjellen mellom denne versjon 2 og 1
er innføring av fopen og denne filen med *
og denne oppfatningen av fprintf, så la oss se hva sluttresultatet er.
La meg gå inn i min terminal-vinduet.
La meg kjøre structs2, skriver.
Ser ut som alt er bra. La oss kjøre structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, skriver.
Ser ut som det oppførte det samme, men hvis jeg gjør nå ls
merke til hva filen er her blant alle koden min, database,
så la oss åpne det, gedit av databasen, og se på det.
Det er ikke den mest sexy av filformater.
Det er virkelig en del av data linje per linje per linje,
men de av dere som bruker Excel eller CSV-filer, kommaseparert verdier,
Jeg kunne sikkert ha brukt fprintf til stedet kanskje gjøre noe som dette
slik at jeg kunne faktisk lage tilsvarende en Excel-fil
ved å skille ting med komma, ikke bare nye linjer.
>> I dette tilfellet hvis jeg hadde i stedet brukt komma i stedet for nye linjer
Jeg kunne bokstavelig talt åpne denne databasen i Excel hvis jeg i stedet gjorde det ser slik ut.
Kort sagt, nå som vi har makt til å skrive til filer
Vi kan nå begynne vedvarende data, holde den rundt på plate
slik at vi kan holde informasjon rundt igjen og igjen.
Merke til et par andre ting som er nå litt mer kjent.
På toppen av dette C-filen har vi en typedef
fordi vi ønsket å lage en datatype som representerer et ord,
så denne typen kalles ord, og innsiden av denne strukturen
det er litt mer avansert nå.
Hvorfor er et ord består av tilsynelatende en array?
Hva er et ord bare intuitivt?
>> Det er en rekke tegn.
Det er en rekke tegn rygg mot rygg mot rygg.
Alle store bokstaver skjer for å være vi vilkårlig si maksimal lengde
av hvilket som helst ord i ordboken som vi bruker for Scramble.
Hvorfor har jeg en en?
Null karakter.
Husker når vi gjorde Bananagrams eksempel vi trengte en spesiell verdi
på slutten av ordet for å holde styr
hvor ordene faktisk avsluttet, og som oppgavesettet spesifikasjonen sier
her vi assosiere med et gitt ord en boolsk verdi,
et flagg, så å si, sant eller usant.
Har du funnet dette ordet allerede, fordi vi innser
vi virkelig trenger en måte å huske ikke bare hva et ord er i Scramble
men hvorvidt du, menneske, har funnet det
slik at hvis du finner ordet "the" du kan ikke bare skrive, skriver, det, enter,, skriver
og få 3 poeng, 3 poeng, 3 poeng, 3 poeng.
Vi ønsker å være i stand til å svarteliste det ordet ved å sette en bool
til true hvis du allerede har funnet den, og så det er derfor vi
innkapslet det i denne strukturen.
>> Nå, her nede i Scramble det er denne andre struct kalt ordbok.
Fraværende her er ordet typedef fordi i dette tilfellet
vi trengte å kapsle ideen om en ordbok,
og en ordbok inneholder en hel haug med ord,
som følger av denne matrisen, og hvor mange av disse ordene er det?
Vel, uansett hva dette variabel kalt størrelsen sier.
Men vi trenger bare en ordbok.
Vi trenger ikke en datatype som heter ordbok.
Vi trenger bare en av dem, så det viser seg i C
at hvis du ikke sier typedef, du bare si struct, så inne i klammeparentes
du sette variabler, så du satte navnet.
Dette er å erklære en variabel kalt ordbok
som ser slik ut.
Derimot, er disse linjene skaper en gjenbrukbar datastruktur kalt ordet
at du kan lage flere kopier av, akkurat som vi opprettet
flere kopier av studenter.
>> Hva betyr dette i siste instans tillate oss å gjøre?
La meg gå tilbake til, la oss si, en enklere eksempel fra enklere tider,
og la meg åpne opp, la oss si, compare1.c.
Problemet her på hånden er å faktisk skrelle tilbake
laget av en streng og begynne å ta av disse opplæring hjul
fordi det viser seg at en streng hele tiden
er som vi lovet i uke 1 egentlig bare et kallenavn,
et synonym fra CS50 bibliotek for noe som ser litt mer kryptisk,
char *, og vi har sett denne stjernen før.
Vi så det i sammenheng med filer.
>> La oss nå se hvorfor vi har gjemt denne detaljen i noen tid nå.
Her er en fil som heter compare1.c,
og den ber tilsynelatende brukeren for 2 strenger, s og t,
og da er det prøver å sammenligne de strenger for likestilling i linje 26,
og hvis de er like står det: "Du skrev det samme,"
og hvis de ikke er like står det: "Du har skrevet forskjellige ting."
La meg gå videre og kjøre dette programmet.
La meg gå inn i min kilde katalog, lage en compare1. Det samlet greit.
La meg kjøre compare1.
Jeg zoome inn, inn.
Si noe. HELLO.
Jeg vil si noe nytt. HELLO.
Jeg definitivt ikke skrive forskjellige ting.
>> La meg prøve dette igjen. BYE BYE.
Definitivt ikke annerledes, så hva er det som skjer her?
Vel, er det som virkelig blir sammenlignet på linje 26?
[Uhørlig-student]
Ja, så det viser seg at en streng, datatype, er en slags hvit løgn.
En streng er en char *, men hva er en char *?
En char *, som de sier, er en peker,
og en peker er effektivt en adresse,
en sum sted i minnet, og hvis du tilfeldigvis har skrevet inn et ord som HELLO,
husker fra tidligere diskusjoner strenger
dette er som ordet HELLO.
Husk at et ord som HELLO kan representeres
som en rekke tegn som dette
og deretter med en spesiell karakter ved enden kalles null karakter,
som \ betegner.
Hva er egentlig en streng?
Legg merke til at dette er flere biter av minne,
og faktisk er slutten av det eneste kjente når du ser gjennom hele strengen
på jakt etter den spesielle null karakter.
Men hvis dette er en del av minne fra min datamaskinens minne,
la oss vilkårlig si at denne strengen bare hadde flaks,
og det fikk plassert helt i begynnelsen av min datamaskinens RAM.
Dette er 0 byte, 1, 2, 3, 4, 5, 6 ...
>> Når jeg sier noe sånt som GetString og jeg streng s = GetString
hva som virkelig blir returnert?
For disse siste ukene, er det som virkelig blir lagret i s
er ikke denne strengen per se, men i dette tilfellet hva som blir lagret, er
tallet 0 fordi det GetString faktisk gjør
er det ikke tilbake fysisk en streng.
Som ikke engang virkelig gjøre konseptuelle forstand.
Hva det retur er et tall.
At antallet er adressen HELLO i minnet,
og streng s da, hvis vi skrelle tilbake dette laget, ikke streng egentlig ikke eksisterer.
Det er bare en forenkling i CS50 biblioteket.
>> Dette er virkelig noe som heter char *.
Char er fornuftig fordi det er et ord, som HELLO?
Vel, det er en rekke tegn, en rekke tegn.
Char * betyr adressen til en karakter,
så hva betyr det å returnere en streng?
En fin og enkel måte å returnere en streng
er heller enn å prøve å finne ut hvordan jeg kommer tilbake til 5 eller 6 forskjellige byte
la meg gå tilbake til adressen som byte?
Den første.
Med andre ord, la meg gi deg adressen til en karakter i minnet.
Det er det char * representerer, er adressen til en enkelt tegn i minnet.
Ring den variabelen s.
Butikk i s den aktuelle adressen, som jeg vilkårlig sagt er 0,
bare for å holde ting enkelt, men i virkeligheten er det generelt et større antall.
>> Vent litt.
Hvis du bare gi meg adressen til det første tegnet, hvordan vet jeg hva adressen er
for neste tegn, den tredje, fjerde og femte?
[Uhørlig-student]
Du bare vet hvor slutten av strengen er ved hjelp av denne praktiske triks,
så når du bruker noe som printf, hva printf tar bokstavelig talt som argument sin,
husker at vi bruker denne% s plassholder, og du passerer i
variabelen som er å lagre en streng.
Hva du egentlig passerer er adressen til den første tegnet strengen.
Printf bruker deretter en for loop eller en stund loop ved mottak som adresse,
for eksempel, 0, så la meg gjøre dette nå,
printf ("% s \ n", s);
Når jeg ringer printf ("% s \ n", s), hva jeg egentlig gi printf med
er adressen for det første tegnet i s, som i dette tilfellet er vilkårlig H.
>> Hvordan vet printf hva som skal vises på skjermen?
Personen som gjennomføres printf implementert en stund løkke eller en for loop
som sier ikke lik denne karakteren den spesielle null karakter?
Hvis ikke, skrive det ut. Hva med denne?
Hvis ikke skrive det, skrive det ut, skrive det ut, skrive det ut.
Å, dette er en spesiell. Stopp trykkteknikker og gå tilbake til brukeren.
Og det er bokstavelig talt alt som har skjedd under panseret,
og det er mye å fordøye i den første dagen av en klasse,
men for nå er det virkelig byggestein forstå alt
som har pågått på innsiden av våre datamaskinens minne,
og til slutt vil vi erte dette fra hverandre med litt hjelp
fra en av våre venner på Stanford.
>> Professor Nick Parlante ved Stanford har gjort denne fantastiske videosekvens
fra alle slags forskjellige språk som introduserte
denne lille Claymation karakter Binky.
Stemmen du er i ferd å høre på bare noen få andre sniktitt
er at av en Stanford professor, og du får
bare 5 eller 6 sekunder av dette akkurat nå,
men dette er notatet som vi vil konkludere i dag
og begynne på onsdag.
Jeg gir deg Pointer Moro med Binky, forhåndsvisningen.
[♪ Music ♪] [Professor Parlante] Hei, Binky.
Våkn opp. Det er tid for pekeren moro.
[Binky] Hva er det? Lær om pekere?
Oh, goody!
>> Vi vil se deg på onsdag.
[CS50.TV]