[Powered by Google Translate] [Omtale] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [Dette er CS50.] [CS50.TV]
>> Hei, alle sammen.
Velkommen til gjennomgangen økt for 0 Quiz, som finner sted på onsdag.
Hva vi skal gjøre i kveld, jeg med 3 andre TFS,
og sammen skal vi gå gjennom en gjennomgang av hva vi har gjort i løpet så langt.
Det kommer ikke til å være 100% omfattende, men det bør gi deg en bedre idé
av hva du allerede har ned og hva du fortsatt trenger å studere før onsdag.
Og gjerne heve hånden med spørsmål som vi skal sammen,
men husk at vi vil også ha en liten bit av tid på slutten-
hvis vi får gjennom med et par minutter til overs til å gjøre generelle spørsmål,
så hold det i tankene, så vi kommer til å starte i begynnelsen med uke 0.
>> [Quiz 0 anmeldelse!] [Part 0] [Lexi Ross] Men før vi gjør det la oss snakke om
logistikken av quizen.
>> [Logistikk] [Quiz foregår onsdag 10/10 i stedet for forelesning]
>> [(Se http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf for detaljer)] Det er onsdag 10 oktober.
>> Det er denne onsdagen, og hvis du går til denne nettadressen her,
som også er tilgjengelig fra CS50.net-det er en link til det-
Du kan se informasjon om hvor du skal dra på grunnlag av
etternavnet ditt eller skolen tilknytning samt
det forteller om nøyaktig hva quiz vil dekke og hvilke typer spørsmål som du kommer til å få.
Husk at du også har en sjanse til å gjennomgå for quiz i seksjonen,
slik at TFS skal gå over noen praksis problemer,
og det er en annen god sjanse til å se hvor du fortsatt trenger å studere opp for quiz.
La oss begynne med begynnelsen med Bits 'n' Bytes.
Husk litt er bare en 0 eller 1,
og en byte er en samling av 8 av disse bitene.
La oss se på denne samlingen av biter her.
Vi burde være i stand til å finne ut hvor mange biter det er.
Der vi teller det er bare 8 av dem, åtte 0 eller 1 stk.
Og siden det er 8 bits, det er en byte,
og la oss konvertere den til heksadesimal.
Heksadesimal er base 16, og det er ganske enkelt å konvertere
et tall i binær, som er hva som er, til en rekke i heksadesimal.
Alt vi gjør er vi ser på grupper på 4,
og vi konvertere dem til riktig heksadesimale siffer.
Vi starter med lengst til høyre gruppe 4, så 0011.
Det kommer til å bli en 1 og en 2, så sammen som gjør tre.
Og så la oss se på den andre blokken av fire.
1101. Det kommer til å bli en 1, en 4, og en 8.
Sammen som kommer til å være 13, noe som gjør D.
Og vi vil huske at i heksadesimal vi ikke bare gå 0 til 9.
Vi går fra 0 til F, så etter 9, 10 tilsvarer en,
11 til B, et cetera der F er 15 år.
Her 13 er en D,
så å konvertere den til desimal alt vi gjør er vi faktisk
behandle hver posisjon som en effekt på 2.
Det er en 1, en 2, null 4s, null 8s, en 16, et cetera,
og det er litt vanskelig å beregne i hodet ditt, men hvis vi går til neste lysbilde
Vi kan se svaret på det.
>> I hovedsak skal vi over fra helt tilbake til venstre,
og vi multiplisere hvert siffer ved tilsvarende effekt på 2.
Og husk, for heksadesimal betegne vi disse tallene med 0x i begynnelsen
så vi ikke forveksles med et desimaltall.
Fortsetter på, er dette en ASCII-tabellen,
og hva vi bruker ASCII for å kartlegge fra tegn til numeriske verdier.
Husk i kryptografi pset vi gjorde utstrakt bruk av ASCII-tabellen
for å bruke ulike metoder for kryptografi,
Caesar og Vigenère siffer, for å konvertere forskjellige bokstaver
i en streng i henhold til nøkkel gitt av brukeren.
La oss se på en liten bit av ASCII matematikk.
Ser på "P" + 1, i karakter form som ville være Q,
og husk at '5 '≠ 5.
Og hvordan akkurat ville vi konvertere mellom disse to formene?
Det er faktisk ikke så vanskelig.
For å få 5 vi trekker '0 '
fordi det er 5 steder mellom '0 'og '5.'
For å gå den andre veien vi bare legge til 0,
så det er liksom som vanlig aritmetikk.
Bare husk at når noe har anførselstegn rundt det det er et tegn
og tilsvarer dermed en verdi i ASCII-tabellen.
Flytte inn mer generelle informatikk emner.
Vi lærte hva en algoritme er og hvordan vi bruker programmering
å gjennomføre algoritmer.
Noen eksempler på algoritmer er noe veldig enkelt som
sjekke om et tall er partall eller oddetall.
For at vi husker mod tallet med 2 og sjekk om resultatet er 0.
I så fall er det enda. Hvis ikke, er det merkelig.
Og det er et eksempel på en virkelig grunnleggende algoritme.
>> En liten bit av en mer involvert man er binært søk,
som vi vil gå over senere i anmeldelsen økten.
Og programmering er betegnelsen vi bruker for å ta en algoritme
og konvertere den til kode på datamaskinen kan lese.
2 eksempler på programmering er Scratch,
som er hva vi gjorde i uke 0.
Selv om vi ikke egentlig skriver ut koden er det en måte å implementere
denne algoritmen, som skriver tallene 1-10,
og her gjør vi det samme i C programmeringsspråk.
Dette er funksjonelt likeverdig, bare skrevet på forskjellige språk eller syntaks.
Vi har lært om boolske uttrykk,
og en boolean er en verdi som er enten sant eller usant,
og her ofte boolske uttrykk
gå inn på vilkårene, så hvis (x ≤ 5),
vel, vi allerede satt x = 5, slik at tilstanden kommer til å vurdere å true.
Og hvis det er sant, er det koden under forutsetning
kommer til å bli vurdert av datamaskinen, er at strengen skal skrives ut
til standard ut, og begrepet tilstand
refererer til det som er i parentes hvis setningen.
Husk alle operatørene.
Husk det er && og | | når vi prøver å kombinere to eller flere forhold,
== Ikke = for å sjekke om to ting er like.
Husk at = er for tildeling mens == er en boolsk operator.
≤, ≥ og deretter den endelige to er selvforklarende.
En generell gjennomgang av boolsk logikk her.
Og boolske uttrykk er også viktig i sløyfer,
som vi vil gå over nå.
Vi har lært om tre typer sløyfer så langt i CS50, for, while, og gjøre mens.
Og det er viktig å vite at mens for de fleste formål
Vi kan faktisk bruke hvilken som helst type løkke generelt
er det visse typer av formål eller felles mønstre
i programmering som spesifikt kaller for en av disse loopene
som gjør den til den mest effektive eller elegant å kode det på den måten.
La oss gå over hva hver av disse løkker tendens til å bli brukt for oftest.
>> I en for løkke generelt vi allerede vet hvor mange ganger vi ønsker å veksle.
Det er hva vi legger i den tilstanden.
For, i = 0, I <10, for eksempel.
Vi vet allerede at vi ønsker å gjøre noe 10 ganger.
Nå, for en stund løkke, generelt vi ikke nødvendigvis
vet hvor mange ganger vi vil at loopen skal kjøres.
Men vi vet en slags tilstand som vi vil ha det til
alltid være sant eller alltid være falsk.
For eksempel, er mens angitt.
La oss si at det er en boolsk variabel.
Mens det er sant vi ønsker koden for å evaluere,
så litt mer utvidbar, litt mer generell enn en for loop,
men noen for loop kan også bli konvertert til en stund loop.
Endelig gjør mens sløyfer, som kan være den vanskeligste å forstå med en gang,
brukes ofte når vi ønsker å evaluere koden først
før den første gangen sjekker vi tilstanden.
En vanlig bruk tilfelle for en gjøre mens sløyfe
er når du ønsker å få brukerens input, og du vet at du vil be brukeren
for innspill minst en gang, men hvis de ikke gi deg gode innspill med en gang
du ønsker å fortsette å spørre dem før de gir deg gode innspill.
Det er den mest vanlige bruken av en gjøre mens loop,
og la oss se på selve strukturen av disse loopene.
De vanligvis pleier alltid å følge disse mønstrene.
>> På for-løkken inne har du tre komponenter:
initialisering, typisk noe som int i = 0 hvor jeg er telleren,
tilstand, der vi ønsker å si kjøre dette for loop så lenge denne tilstanden gjelder fremdeles,
som jeg <10, og så til slutt, oppdatering, som er hvordan vi øke
tellervariabelen ved hvert punkt i sløyfen.
En vanlig ting å se det er bare i + +,
som betyr inkrementere jeg med 1 hver gang.
Du kan også gjøre noe sånt i + = 2,
som betyr legge 2 til jeg hver gang du går gjennom løkken.
Og så gjør dette refererer bare til noen kode som faktisk kjører som en del av loopen.
Og for en stund loop, denne gangen vi faktisk har initialisering utenfor løkken,
så for eksempel, la oss si at vi prøver å gjøre samme type løkke som jeg nettopp beskrev.
Vi vil si int i = 0 før løkken begynner.
Da kunne vi si mens jeg <10 gjør dette,
så samme blokk med kode som før,
og denne gangen oppdateringen del av koden, for eksempel, i + +,
faktisk går inne i sløyfen.
Og til slutt, for en gjøre mens, det ligner mens loop,
men vi må huske at koden vil vurdere en gang
før tilstanden er sjekket, så det gjør mye mer fornuftig
hvis du ser på det i rekkefølge fra topp til bunn.
I en gjøre mens sløyfe koden evaluerer før du selv se på mens condition,
mens en stund loop, sjekker den først.
Uttalelser og variabler.
Når vi ønsker å opprette en ny variabel vi først ønsker å initialisere den.
>> For eksempel, initialiseres int bar variabelen bar,
men det gir ikke det en verdi, så hva er bar verdi nå?
Vi vet ikke.
Det kan være noen søppel verdi som tidligere var lagret i minnet der,
og vi ønsker ikke å bruke den variabelen
før vi faktisk gi den en verdi,
så vi erklærer det her.
Deretter vi initialisere det å være 42 under.
Nå, selvfølgelig, vet vi at dette kan gjøres på én linje, int bar = 42.
Men bare for å være fjerne flere trinn som skjer,
erklæringen og initialisering skjer separat her.
Det skjer på ett trinn, og den neste, int baz = bar + 1,
denne uttalelsen nedenfor, som øker baz, så på slutten av denne koden blokken
hvis vi skulle skrive verdien av baz det ville være 44
fordi vi erklærer og initialisere det å være en> bar,
og da vi øke det enda en gang med + +.
Vi gikk over denne ganske kort, men det er godt å ha en generell
forståelse av hva tråder og hendelser er.
Vi hovedsakelig gjorde dette i Scratch,
slik at du kan tenke på tråder som flere sekvenser av kode
kjører på samme tid.
I virkeligheten, er det sannsynligvis ikke kjører på samme tid,
men slags abstrakt vi kan tenke på det på den måten.
>> I Scratch, for eksempel, hadde vi flere sprites.
Det kan være å utføre annen kode samtidig.
Man kunne være gange mens den andre er å si noe
i en annen del av skjermen.
Arrangementer er en annen måte for å skille ut logikken
mellom ulike elementer av koden din,
og i Scratch kunne vi simulere hendelser ved hjelp av Broadcast,
og det er faktisk når jeg mottar, ikke når jeg hører,
men i hovedsak er det en måte å overføre informasjon
fra en sprite til annen.
For eksempel kan det være lurt å overføre game over,
og når en annen sprite mottar game over,
den reagerer på en bestemt måte.
Det er en viktig modell for å forstå for programmering.
Bare for å gå over den grunnleggende uke 0, hva vi har gått over så langt,
la oss se på dette enkle C program.
Teksten kan være litt lite herfra, men jeg skal gå over det virkelig rask.
Vi inkludert 2 header filer på toppen, cs50.h og stdio.h.
Vi så definere en konstant kalt grense for å være 100.
Vi så implementere vår viktigste funksjon.
Siden vi ikke bruker kommandolinjeargumenter her vi må sette ugyldig
som argumenter for main.
Vi ser int over main. Det er returtypen, derav returnere 0 nederst.
Og vi bruker CS50 biblioteket funksjon får int
å spørre brukeren om inndata, og vi lagre den i denne variabelen x,
så vi erklærer x ovenfor, og vi starte den med x = GetInt.
>> Vi så sjekk for å se om brukeren ga oss gode innspill.
Hvis det er ≥ LIMIT vi ønsker å returnere en feilkode på en og skrive ut en feilmelding.
Og til slutt, hvis brukeren har gitt oss gode innspill
vi kommer til torget nummeret og skrive ut resultatet.
Bare for å være sikker på at de alle hit hjem
du kan se etikettene på ulike deler av koden her.
Jeg nevnte konstant, header filer.
Oh, int x. Sørg for å huske det er en lokal variabel.
Som står i kontrast det fra en global variabel, som vi vil snakke om
litt senere i anmeldelsen økten,
og vi ringer bibliotek funksjon printf,
så hvis vi ikke hadde tatt den stdio.h topptekstfilen
vi ville ikke være i stand til å ringe printf.
Og jeg tror pilen som fikk kuttet av her peker til% d,
som er en formatering streng i printf.
Det sier skrive ut denne variabelen som et tall,% d.
Og det er det for uke 0.
Nå Lucas kommer til å fortsette.
Hei, folkens. Mitt navn er Lucas.
Jeg er en sophomore i beste hus på campus, Mather,
og jeg kommer til å snakke litt om uke 1 og 2,1.
[Uke 1 og 2,1!] [Lucas Freitas]
Som Lexi sa, da vi startet å oversette koden fra Scratch til C
en av de tingene som vi la merke er at du kan ikke bare
skrive kode og kjøre den med et grønt flagg lenger.
Egentlig må du bruke noen skritt for å gjøre din C-program
bli en kjørbar fil.
I utgangspunktet hva du gjør når du skriver et program er at
du oversette din idé til et språk som en kompilator kan forstå,
så når du skriver et program i C
hva du gjør er faktisk å skrive noe som kompilatoren kommer til å forstå,
og deretter kompilatoren skal oversette denne koden
til noe som datamaskinen forstår.
>> Og ting er, er datamaskinen faktisk veldig dumt.
Datamaskinen kan bare forstå 0'er og 1'ere,
så faktisk i de første datamaskinene folk vanligvis programmert
hjelp 0'er og 1'ere, men ikke lenger, takk Gud.
Vi trenger ikke å memorere sekvenser for 0'er og 1'ere
for en for sløyfe eller en stund løkke og så videre.
Det er derfor vi har en kompilator.
Hva en kompilator gjør er det i utgangspunktet oversetter C-kode,
i vårt tilfelle, til et språk som datamaskinen vil forstå,
som er gjenstand koden, og kompilatoren at vi bruker
kalles clang, så dette er faktisk symbolet for clang.
Når du har programmet, må du gjøre to ting.
Først må du kompilere programmet, og du kommer til å kjøre programmet.
Å kompilere programmet du har en rekke alternativer for å gjøre det.
Den første er å gjøre clang program.c
i hvilket program er navnet på programmet.
I dette tilfellet kan du se de bare si "Hei, kompilere programmet mitt."
Du sier ikke "Jeg vil dette navnet for mitt program" eller noe.
>> Det andre alternativet er å gi et navn til programmet.
Du kan si clang-o og deretter navnet du vil
den kjørbare filen til å bli navngitt som og deretter program.c.
Og du kan også gjør programmet, og se hvordan de første to tilfellene
Jeg satt. C, og i den tredje bare jeg har programmer?
Ja, du faktisk ikke bør sette. C når du bruker gjør.
Ellers kompilatoren er faktisk kommer til å kjefte på deg.
Og også, jeg vet ikke om dere husker,
men mange ganger vi også brukt-lcs50 eller-lm.
Som kalles linking.
Det forteller bare kompilatoren som du vil bruke disse bibliotekene der,
så hvis du ønsker å bruke cs50.h du faktisk nødt til å skrive
clang program.c-lcs50.
Hvis du ikke gjør det, er kompilatoren ikke kommer til å vite
at du bruker disse funksjonene i cs50.h.
Og når du ønsker å kjøre programmet du har 2 alternativer.
Hvis du gjorde clang program.c du ikke gi et navn til programmet.
Du må kjøre den bruker. / A.out.
A.out er en standard navn som klang gir programmet hvis du ikke gi den et navn.
Ellers kommer du til å gjøre. / Program hvis du ga et navn til programmet,
og også hvis du gjorde programmet navnet at et program skal få
er allerede kommer til å bli programmert samme navn som c-fil.
Da vi snakket om datatyper og data.
>> I utgangspunktet datatyper er det samme som små bokser de bruker
å lagre verdier, så datatyper er faktisk akkurat som Pokemons.
De kommer i alle størrelser og typer.
Jeg vet ikke om det analogi er fornuftig.
Datastørrelsen avhenger faktisk på maskinen arkitektur.
Alle data størrelser som jeg kommer til å vise her
er faktisk for et 32-bits maskin, som er tilfellet med apparatet vårt
men hvis du faktisk koding din Mac eller en Windows også
du sannsynligvis kommer til å ha en 64-bits maskin,
så husk at dataene størrelser som jeg kommer til å vise her
er for 32-bits maskin.
Den første som vi så var en int,
som er ganske grei.
Du bruker int til å lagre et heltall.
Vi så også tegnet, røye.
Hvis du ønsker å bruke en bokstav eller et lite symbol du sannsynligvis kommer til å bruke en røye.
En røye har 1 byte, noe som betyr 8 bits, som Lexi sa.
I utgangspunktet har vi en ASCII-tabellen som har 256
mulige kombinasjoner av 0'er og 1'ere,
og når du skriver en røye det kommer til å oversette
tegnet som innganger du et nummer som du har i ASCII-tabellen, som Lexi sa.
Vi har også flyte, som vi bruker til å lagre desimaltall.
Hvis du ønsker å velge 3.14, for eksempel, du kommer til å bruke en flåte
eller en dobbel som har mer presisjon.
En flottør har 4 bytes.
En dobbel har 8 byte, så den eneste forskjellen er presisjonen.
Vi har også en lang som brukes for heltall,
og du kan se for en 32-bits maskin en int og en lang har samme størrelse,
så det gjør ikke egentlig fornuftig å bruke en lang i en 32-bits maskin.
>> Men hvis du bruker en Mac og 64-bits maskin, faktisk en lang har størrelse 8,
så det er egentlig avhengig av arkitektur.
For 32-bits maskin det ikke fornuftig å bruke en lang egentlig.
Og deretter en lang lang, på den annen side, har 8 byte,
så det er veldig bra hvis du vil ha en lengre heltall.
Og til slutt har vi streng, som faktisk er en char *,
som er en peker til en char.
Det er veldig lett å tenke at størrelsen på strengen skal være like
antall tegn som du har det,
men faktisk char * seg
har størrelsen på en peker til en char, som er 4 byte.
Størrelsen på en char * er 4 byte.
Det spiller ingen rolle om du har et lite ord eller en bokstav eller noe.
Det kommer til å være 4 byte.
Vi har også lært litt om støping,
slik som du kan se, hvis du har, for eksempel, et program som sier
int x = 3 og deretter printf ("% d", x / 2)
vet dere hva det kommer til å skrive ut på skjermen?
>> Noen? >> [Studenter] 2.
1. >> 1, ja.
Når du gjør 3/2 det kommer til å få 1,5,
men siden vi bruker et heltall det kommer til å ignorere desimaldel,
og du kommer til å ha en.
Hvis du ikke vil at det skal skje hva du kan gjøre, for eksempel,
er erklærer en flåte y = x.
Så x som pleide å være 3 er nå kommer til å være 3.000 i y.
Og så kan du skrive ut y / 2.
Egentlig bør jeg ha en 2. der borte.
Det kommer til å gjøre 3.00/2.00,
og du kommer til å få 1,5.
Og vi har denne .2 f bare for å be om 2 desimaler enheter i desimaldelen.
Hvis du har 0,3 f det kommer til å ha faktisk 1.500.
Hvis det er to det kommer til å være 1,50.
Vi har også denne saken her.
Hvis du gjør float x = 3,14 og deretter du printf x
du kommer til å få 3,14.
Og hvis du gjør x = int av x,
noe som betyr behandle x som en int, og du skriver ut x nå
du kommer til å ha 3,00.
Gjør det fornuftig?
Fordi du først å behandle x som et heltall, slik at du ignorerer desimaldelen,
og da er du skriver x.
Og til slutt, kan du også gjøre dette,
int x = 65, og deretter erklære en char c = x,
og hvis du skriver ut c du faktisk kommer til å få
A, så i utgangspunktet hva du gjør her
er å oversette heltall inn i karakteren,
akkurat som ASCII tabellen.
Vi snakket også om baneoperatører.
De fleste av dem er ganske grei, så +, -, *, /,
og også vi snakket om mod, som er resten av en divisjon av to tall.
Hvis du har 10% 3, for eksempel,
det betyr dele 10 med 3, og hva er resten?
Det kommer til å være 1, så det er faktisk veldig nyttig for mange av programmene.
For Vigenère og Caesar er jeg ganske sikker på at alle dere brukte mod.
Om baneoperatører, være svært forsiktig med å kombinere * og /.
>> For eksempel, hvis du gjør (3/2) * 2 hva har du tenkt å bli?
[Studenter] 2.
Ja, 2, fordi tre halvdel kommer til å være 1,5,
men siden du gjør operasjoner mellom to heltall
du faktisk bare kommer til å vurdere en,
og deretter 1 * 2 kommer til å bli to, så vær veldig forsiktig
når du gjør regning med heltall fordi
du kan få den 2 = 3, i så fall.
Og også være svært forsiktig med forrang.
Du bør vanligvis bruke parenteser for å være sikker på at du vet hva du gjør.
Noen nyttige snarveier, selvfølgelig, er en jeg + + eller i + = 1
eller bruke + =.
Det er det samme som å gjøre i = i + 1.
Du kan også gjøre i - eller i - = 1,
som er det samme som i = i -1,
noe dere bruker mye i for looper, minst.
Også for *, hvis du bruker * =, og hvis du gjør det, for eksempel,
i * = 2 er det samme som å si i = i * 2,
og det samme for divisjonen.
Hvis du gjør i / = 2 er det samme som i = i / 2.
>> Nå om funksjoner.
Dere lærte at funksjonene er en veldig god strategi for å spare kode
mens du programmerer, så hvis du ønsker å utføre den samme oppgaven
i koden igjen og igjen, sannsynligvis du vil bruke en funksjon
bare så du ikke trenger å kopiere og lime inn koden igjen og igjen.
Egentlig er det viktigste en funksjon, og når jeg vise deg formatet av en funksjon
du kommer til å se at det er ganske åpenbart.
Vi bruker også funksjoner fra enkelte bibliotekene,
for eksempel, printf, Getin, som er fra CS50 biblioteket,
og andre funksjoner som toupper.
Alle disse funksjonene faktisk blir gjennomført i andre bibliotek,
og når du setter dem tjore filer i begynnelsen av programmet
du sier kan du gi meg koden for disse funksjonene
så jeg ikke trenger å implementere dem selv?
Og du kan også skrive dine egne funksjoner, så når du starter programmering
du skjønner at bibliotekene ikke har alle funksjonene du trenger.
For den siste pset, for eksempel, skrev vi tegne, krafse, og oppslag,
og det er veldig, veldig viktig å være i stand til å skrive funksjoner
fordi de er nyttige, og vi bruker dem hele tiden i programmering,
og det sparer mye kode.
Formatet på en funksjon er dette en.
Vi har returtype i begynnelsen. Hva er avkastningen type?
Det er bare når funksjonen kommer til å returnere.
Hvis du har en funksjon, for eksempel, fakultet,
som kommer til å beregne en fakultet av et heltall,
sannsynligvis det kommer til å returnere et heltall også.
Da returtypen kommer til å være int.
Printf har faktisk en retur-type ugyldig
fordi du ikke er tilbake noe.
Du er bare skriver ting på skjermen
og avslutte funksjonen etterpå.
Da har du navnet på funksjonen som du kan velge.
Du bør være litt fornuftig, som ikke velger et navn som xyz
eller som x2f.
Prøv å gjøre opp et navn som gir mening.
>> For eksempel, hvis det er faktoriell, sier fakultet.
Hvis det er en funksjon som kommer til å tegne noe, name it tegne.
Og så har vi de parametrene, som også kalles argumenter,
som er som de ressurser som din funksjon trenger
fra koden din for å utføre sin oppgave.
Hvis du ønsker å beregne fakultet til et tall
sannsynligvis må du ha et nummer for å beregne en fakultet.
Et av argumentene som du kommer til å ha er selve nummeret.
Og så det kommer til å gjøre noe og returnere verdien på slutten
med mindre det er et tomrom funksjon.
La oss se et eksempel.
Hvis jeg ønsker å skrive en funksjon som summerer alle tallene i en matrise av heltall,
først av alt, er returtypen skal være int
fordi jeg har en rekke heltall.
Og så skal jeg ha funksjonen navn som sumArray,
og så det kommer til å ta array selv, til int nums,
og deretter lengden av tabellen, så jeg vet hvor mange tall jeg må oppsummere.
Da må jeg initialisere en variabel kalt sum, for eksempel, til 0,
og hver gang jeg ser et element i matrisen jeg bør legge det til summen, så jeg gjorde en for-løkke.
Akkurat som Lexi sa, du int i = 0, i <lengde og i + +.
Og for hvert element i matrisen gjorde jeg sum + = nums [i],
og da jeg kom tilbake summen, så det er veldig enkelt, og det sparer mye kode
hvis du bruker denne funksjonen en rekke ganger.
Så tok vi en titt på forholdene.
Vi har if, else, og ellers hvis.
La oss se hva som er forskjellen mellom disse.
Ta en titt på disse to kodene. Hva er forskjellen mellom dem?
Den første har-i utgangspunktet kodene du ønsker å fortelle
om et tall er +, -, eller 0.
Den første sier at hvis det er> 0, så det er positivt.
Hvis det er = til 0 så er det 0, og hvis det er <0 så er det negativt.
>> Og den andre gjør if, else if, else.
Forskjellen mellom de to er at dette faktisk kommer til å
sjekke om> 0, <0 eller = 0 tre ganger,
så hvis du har nummer 2, for eksempel, kommer det til å komme hit og si
if (x> 0), og det kommer til å si ja, så jeg skriver ut positivt.
Men selv om jeg vet at det er> 0, og det er ikke til å være 0 eller <0
Jeg er fortsatt kommer til å gjøre er det 0, er det <0,
så jeg faktisk kommer inne i IFS at jeg ikke måtte
fordi jeg vet allerede at det ikke kommer til å tilfredsstille noen av disse forholdene.
Jeg kan bruke if, else if, else statement.
Det sier i utgangspunktet hvis x = 0 Jeg skriver det positive.
Hvis det ikke er det, kommer jeg til å også teste dette.
Hvis det er to ikke jeg kommer til å gjøre dette.
I utgangspunktet hvis jeg hadde x = 2 du ville si
if (x> 0), ja, så skrive ut denne.
Nå som jeg vet at det er> 0 og at det tilfredsstilte først hvis
Jeg er ikke engang kommer til å kjøre denne koden.
Koden kjøres fortere, faktisk, tre ganger raskere hvis du bruker dette.
Vi har også lært om og og eller.
Jeg kommer ikke til å gå gjennom dette fordi Lexi allerede snakket om dem.
Det er bare de && og | | operatøren.
>> Det eneste jeg vil si er å være forsiktig når du har 3 tilstander.
Bruke parenteser fordi det er veldig forvirrende når du har en tilstand
og en annen eller et annet,.
Bruke parenteser bare for å være sikker på at dine betingelser fornuftig
fordi i så fall, for eksempel, kan du forestille deg at
det kan være den første tilstand og den ene eller andre
eller de 2 forholdene kombinert i en og
eller den tredje, så bare være forsiktig.
Og til slutt, vi snakket om brytere.
En bryter er svært nyttig når du har en variabel.
La oss si at du har en variabel som n
som kan være 0, 1, eller 2, og for hver av disse tilfellene
du kommer til å utføre en oppgave.
Du kan si slå variabelen, og det indikerer at
verdien er da like verdi1 jeg kommer til å gjøre dette,
og da jeg bryte, noe som betyr jeg ikke kommer til å se på noen av de andre sakene
fordi vi allerede fornøyd med at saken
og deretter verdi2 og så videre, og jeg kan også ha en standard bryter.
Det betyr at hvis det ikke tilfredsstiller noen av de sakene som jeg hadde
at jeg kommer til å gjøre noe annet, men det er valgfritt.
Det er alt for meg. Nå la oss ha Tommy.
Greit, dette kommer til å bli Uke 3-ish.
Dette er noen av temaene som vil bli dekket, krypto, omfang, arrays, et cetera.
Bare en rask ord på krypto. Vi kommer ikke til å hamre dette hjemme.
>> Vi gjorde dette i pset 2, men for quiz sørg for at du vet forskjellen
mellom Caesar cipher og Vigenère chiffer,
hvordan begge disse ciphers arbeid og hva det er som å kryptere
og dekryptere tekst ved hjelp av disse to chifre.
Husk, roterer Caesar cipher bare hvert tegn med samme beløp,
gjør at du mod med antall bokstaver i alfabetet.
Og Vigenère chiffer, derimot, roterer hvert tegn
av et annet beløp, så i stedet for å si
Hver karakter roteres ved 3 Vigenère vil rotere hver karakter
av et annet beløp avhengig noen søkeord
hvor hver bokstav i søkeordet representerer noen annet beløp
å rotere klartekst ved.
La oss først snakke om variabel omfang.
Det er 2 forskjellige typer variabler.
Vi har lokale variabler, og disse kommer til å bli definert
utenfor viktigste eller utenfor enhver funksjon eller blokk,
og disse vil være tilgjengelig hvor som helst i programmet.
Hvis du har en funksjon og at funksjonen er en stund loop
den store globale variabelen er tilgjengelig overalt.
En lokal variabel, på den annen side, er scoped til stedet hvor det er definert.
>> Hvis du har en funksjon her, for eksempel, har vi denne funksjonen g,
og innsiden av g det er en variabel her kalt y,
og det betyr at dette er en lokal variabel.
Selv om denne variabelen kalles y
og denne variabelen kalles y disse to funksjonene
aner ikke hva hverandres lokale variabler er.
På den annen side, opp her vi si int x = 5,
og dette er utenfor enhver funksjon.
Det er utenfor rammen av main, så dette er en global variabel.
Det betyr at innsiden av disse to funksjonene når jeg sier x - eller x + +
Jeg tilgang til samme x der dette y og dette y er forskjellige variabler.
Det er forskjellen mellom en global variabel og en lokal variabel.
Så langt som design er bekymret, noen ganger er det sannsynligvis en bedre idé
å holde variabler lokale når du muligens kan
siden har en haug av globale variable kan bli veldig forvirrende.
Hvis du har en haug med funksjoner all endre samme
du kan glemme hva hvis denne funksjonen ved et uhell endrer denne globale,
og denne andre funksjonen ikke vet om det,
og det får ganske forvirrende som du får mer kode.
Holde variabler lokale når du muligens kan
er bare god design.
Matriser, husk, er bare lister over elementer av samme type.
Innsiden av CI kan ikke ha en liste som 1, 2,0, hallo.
Vi kan bare ikke gjøre det.
>> Når vi erklærer en matrise i C alle elementene må være av samme type.
Her har jeg en rekke 3 heltall.
Her har jeg lengden på tabellen, men hvis jeg bare erklære det i denne syntaksen
hvor jeg spesifisere hva alle elementene er jeg ikke teknisk trenger dette 3.
Kompilatoren er smart nok til å finne ut hvor stor matrise skal være.
Nå når jeg ønsker å få eller sette verdien av en matrise
Dette er syntaksen som skal gjøre det.
Dette vil faktisk endre andre element i matrisen fordi, huske,
nummerering starter på 0, ikke i en.
Hvis jeg ønsker å lese denne verdien jeg kan si noe sånt som int x = array [1].
Eller hvis jeg ønsker å sette denne verdien, som jeg gjør her,
Jeg kan si array [1] = 4.
Den tiden tilgang elementer ved deres indeks
eller deres posisjon eller hvor de er i matrisen,
og at oppføringen starter på 0.
Vi kan også ha matriser med arrays,
og dette kalles en multi-dimensjonal array.
Når vi har en multi-dimensjonal array
det betyr at vi kan ha noe som rader og kolonner,
og dette er bare en måte å visualisere dette eller tenke på det.
Når jeg har en multi-dimensjonal array som betyr at jeg kommer til å starte trenger
mer enn 1 indeksen fordi om jeg har et rutenett
bare si hva raden du er i ikke gir oss et tall.
Det er egentlig bare kommer til å gi oss en liste med tall.
La oss si at jeg denne tabellen her.
Jeg har en array kalt rutenett, og jeg sier det er to rader og tre kolonner,
og så dette er en måte å visualisere det.
Når jeg sier jeg vil få elementet på [1] [2]
det betyr at fordi disse er rader først og deretter kolonner
Jeg kommer til å hoppe til rad 1 siden jeg sa en.
>> Så jeg kommer til å komme over her til kolonne 2, og jeg kommer til å få verdien 6.
Fornuftig?
Multi-dimensjonale arrays, husk, er teknisk bare en rekke arrays.
Vi kan ha matriser av matriser av arrays.
Vi kan holde det gående, men egentlig en måte å tenke på
hvordan dette blir lagt ut og hva som skjer, er å visualisere det
i et rutenett som dette.
Når vi passerer arrays til funksjoner, de kommer til å oppføre seg
litt annerledes enn når vi passerer regelmessig variabler til funksjoner
som passerer en int eller en flåte.
Når vi passerer i en int eller røye eller noen av disse andre datatyper
vi bare tok en titt på om funksjonen modifiserer
verdien av variabelen at endringen ikke kommer til å forplante seg opp
til å kalle funksjonen.
Med en matrise, på den annen side, vil det skje.
Hvis jeg passerer i en matrise til noen funksjon, og at funksjonen endrer noen av elementene,
når jeg kommer tilbake til den funksjonen som kalte det
min matrise er nå kommer til å være annerledes, og ordforrådet for at
er arrays er vedtatt av referanse, som vi skal se senere.
Dette er relatert til hvordan pekere arbeid, der disse grunnleggende datatyper
på den annen side er vedtatt av verdi.
>> Vi kan tenke på det som å lage en kopi av noen variable og deretter passerer i kopien.
Det spiller ingen rolle hva vi gjør med den variabelen.
Den ringer funksjonen vil ikke være klar over at den ble endret.
Arrays er bare litt annerledes i den forbindelse.
For eksempel, som vi nettopp så, er det viktigste bare en funksjon
som kan ta i 2 argumenter.
Det første argumentet til den viktigste funksjonen er argc, eller antall argumenter,
og det andre argumentet kalles argv,
og de er de faktiske verdiene av disse argumentene.
La oss si jeg har et program som heter this.c,
og jeg sier at dette, og jeg kommer til å kjøre dette på kommandolinjen.
Nå for å passere i noen argumenter mitt program kalt dette,
Jeg kan si noe sånt som. / Dette er cs 50.
Dette er hva vi forestille David å gjøre hver dag på terminalen.
Men nå den viktigste funksjonen innsiden av det programmet
har disse verdiene, så argc er 4.
Det kan være litt forvirrende fordi vi virkelig er bare passerer i er CS 50.
Det er bare tre.
Men husk at det første elementet i argv eller det første argumentet
er navnet på selve funksjonen.
Så det betyr at vi har fire ting her,
og det første elementet skal være. / dette.
Og dette vil være representert som en streng.
Da de gjenværende elementene er hva vi skrev i etter navnet på programmet.
Så akkurat som en side, som vi trolig så i pset 2,
husk at strengen 50 er ≠ heltallet 50.
Så vi kan ikke si noe sånt som "int x = argv 3.
>> Det er bare ikke til å være fornuftig, fordi dette er en streng, og dette er et heltall.
Så hvis du ønsker å konvertere mellom de 2, husk, vi kommer til å
har denne magisk funksjon kalt atoi.
Som tar en streng og returnerer heltall representert innsiden av strengen.
Så det er en enkel feil å gjøre på quiz,
bare tenker at dette vil automatisk være riktig type.
Men bare vet at disse vil alltid være strenger
selv om strengen inneholder bare et heltall eller et tegn eller en flåte.
Så nå la oss snakke om kjøretid.
Når vi har alle disse algoritmene som gjør alle disse sprø tingene,
det blir veldig nyttig å stille spørsmålet: "Hvor lang tid tar de?"
Vi representerer det med noe som kalles asymptotisk notasjon.
Så dette betyr at - vel, la oss si at vi gir vår algoritme
noen virkelig, virkelig, virkelig stor inngang.
Vi ønsker å stille spørsmålet: "Hvor lenge går det å ta?
Hvor mange skritt vil det ta vår algoritme for å kjøre
som en funksjon av størrelsen på input? "
Så den første måten vi kan beskrive kjøre tid er med stor O.
Og dette er vår verste fall kjører tid.
Så hvis vi ønsker å sortere en tabell, og vi gir vår algoritme en rekke
som er i synkende rekkefølge når det skal være i stigende rekkefølge,
som kommer til å være den verste tilfelle.
Dette er vår øvre grense i den maksimale lengden av vår tid algoritme vil ta.
På den annen side er denne Ω skal beskrive beste tilfelle kjøretid.
Så hvis vi gir en allerede sortert array til en sortering algoritme,
hvor lang tid vil det ta å sortere det?
Og dette, da, beskriver en nedre grense på kjøretid.
Så her er bare noen ord som beskriver noen vanlige kjører ganger.
Disse er i stigende rekkefølge.
Den raskeste kjøretid vi har kalles konstant.
>> Det betyr at uansett hvor mange elementer vi gi våre algoritme,
uansett hvor stor vår rekke er, sortere det
eller gjør hva vi gjør til matrisen vil alltid ta like lang tid.
Så vi kan representere at bare med en 1, som er en konstant.
Vi så også på logaritmisk kjøring.
Så noe som binære søk er logaritmisk,
der vi kuttet problemet i halvparten hver gang
og deretter ting bare få høyere derfra.
Og hvis du noen gang å skrive en O av noen faktoriell algoritme,
du sannsynligvis ikke bør vurdere dette som dagen din jobb.
Når vi sammenligner kjøretider er det viktig å huske på disse tingene.
Så hvis jeg har en algoritme som er O (n), og noen andre
har en algoritme for O (2n) disse er faktisk asymptotisk tilsvarende.
Så hvis vi forestille n å være et stort antall som eleventy milliarder:
så når vi sammenligner eleventy milliarder til noe sånt eleventy milliarder + 3,
plutselig at tre ikke gjør virkelig en stor forskjell lenger.
Det er derfor vi kommer til å starte vurderer disse tingene for å være likeverdige.
Så ting som disse konstantene her, det er 2 x dette, eller legge til en 3,
disse er bare konstanter, og disse kommer til å slippe opp.
Så det er derfor alle 3 av disse kjøre ganger er de samme som sier de er O (n).
Tilsvarende, hvis vi har 2 andre kjøre ganger, la oss si O (n ³ + 2n ²), kan vi legge
+ N, + 7, og så har vi en annen kjøring det er bare O (n ³).
igjen, disse er det samme fordi disse - disse er ikke det samme.
Dette er de samme tingene, beklager. Så disse er de samme, fordi
dette n ³ kommer til å dominere denne 2n ².
>> Hva er ikke det samme er hvis vi har kjørt ganger som O (n ³) og O (n ²)
fordi dette n ³ er mye større enn dette n ².
Så hvis vi har eksponenter, plutselig dette begynner å rolle,
men når vi bare håndtere faktorer som vi er her oppe,
så det kommer ikke til å gjøre noe, fordi de bare kommer til å droppe ut.
La oss ta en titt på noen av de algoritmene vi har sett så langt
og snakke om sin kjøring.
Den første måten å se etter et nummer i en liste, som vi så, var lineær søk.
Og gjennomføring av lineær søk er super enkelt.
Vi har en liste, og vi kommer til å se på hvert enkelt element i listen
før vi finner nummeret vi leter etter.
Så det betyr at i verste fall, denne O (n).
Og verste tilfelle her kan være hvis elementet er
det siste elementet, deretter bruke lineær søk vi må se på hvert enkelt element
før vi kommer til den siste for å vite at det var faktisk på listen.
Vi kan ikke bare gi opp halvveis og si: "Det er nok ikke der."
Med lineær søk må vi se på hele greia.
Best-case gangtid, på den annen side, er konstant
fordi det i beste fall elementet vi leter etter er bare den første i listen.
Så det kommer til å ta oss nøyaktig ett trinn, uansett hvor stor den listen er
hvis vi leter etter det første elementet hver gang.
>> Så når du søker, husk, krever det ikke at vår liste skal sorteres.
Fordi vi bare kommer til å se over hver eneste element, og det spiller ingen rolle
hvilken rekkefølge disse elementene er i.
En mer intelligent søk algoritmen er noe som binære søk.
Husk at gjennomføringen av binære søk når du skal
holde utkikk på midten av listen.
Og fordi vi ser på midten, krever vi at listen er sortert
eller annet vi ikke vet hvor midten er, og vi må se over
hele listen for å finne den, og deretter på det punktet er vi bare kaster bort tiden.
Så hvis vi har en sortert liste, og vi finner midten, vi kommer til å sammenligne midten
til elementet vi leter etter.
Hvis det er for høyt, så kan vi glemme den høyre halvdelen
fordi vi vet at om vårt element er allerede for høy
og alt til høyre for dette elementet er enda høyere,
så vi trenger ikke å se det lenger.
Hvor på den annen side, hvis vår element er for lav,
vi vet alt til venstre for at elementet er også for lav,
så det gjør ikke egentlig fornuftig å se det, heller.
Denne måten, med hvert skritt og hver gang vi ser på midtpunktet av listen,
vi kommer til å kutte vårt problem i halvparten fordi vi plutselig vite
en hel haug med tall som ikke kan være den vi leter etter.
>> I pseudokode dette ville se noe som dette,
og fordi vi kutte listen i halvparten hver eneste gang,
våre worst-case kjøretidsberegninger hopper fra lineær til logaritmisk.
Så plutselig har vi log-in skritt for å finne et element i en liste.
Den beste fall kjører tid, men er fortsatt konstant
fordi nå, la oss bare si at elementet vi leter etter er
alltid den nøyaktige midten av den opprinnelige listen.
Så vi kan øke vår liste så stor som vi ønsker, men hvis elementet vi leter etter er på midten,
så er det bare kommer til å ta oss en trinn.
Så det er derfor vi er O (log n) og Ω (1) eller konstant.
La oss faktisk kjøre binært søk på denne listen.
Så la oss si at vi leter etter elementet 164.
Det første vi skal gjøre er å finne midtpunktet av denne listen.
Det bare så skjer at midtpunktet kommer til å falle i mellom disse to tallene,
så la oss bare vilkårlig si, hver gang midtpunktet faller mellom to tall,
la oss bare runde opp.
Vi trenger bare å sørge for at vi gjør dette hvert steg på veien.
Så vi kommer til å runde opp, og vi kommer til å si at 161 er midt i vår liste.
Så 161 <164, og hvert element til venstre for 161
er også <164, så vi vet at det ikke kommer til å hjelpe oss i det hele tatt
å begynne å se over her fordi elementet vi leter etter kan ikke være der.
Så hva vi kan gjøre er at vi kan bare glemme at hele venstre halvdel av listen,
og nå bare vurdere fra høyre side av 161 framover.
>> Så igjen, dette er midtpunktet, la oss bare runde opp.
Nå 175 er for stor.
Så vi vet at det ikke kommer til å hjelpe oss ser her eller her,
så vi kan bare kaste det bort, og til slutt vil vi treffer 164.
Eventuelle spørsmål om binære søk?
La oss gå videre fra å søke gjennom et allerede sortert liste
å faktisk ta en liste med tall i hvilken som helst rekkefølge
og gjør den listen i stigende rekkefølge.
Den første algoritmen vi så på ble kalt boble slag.
Og dette ville være enklere av algoritmer vi så.
Boble slags sier at når noen 2 elementer inne i listen er malplassert,
betyr at det er et høyere tall til venstre for et lavere antall,
så vi kommer til å bytte dem, fordi det betyr at listen vil bli
"Mer sortert" enn det var før.
Og vi bare kommer til å fortsette denne prosessen igjen og igjen og igjen
før slutt elementene slags boble til riktig sted og vi har en sortert liste.
>> Kjøretiden for denne kommer til å være O (n ²). Hvorfor?
Vel, fordi i verste fall, vi kommer til å ta hvert element, og
vi kommer til å ende opp med å sammenligne den med alle andre element i listen.
Men i beste fall har vi en allerede sortert liste, boble sortere er
bare kommer til å gå gjennom en gang, sier "Nope. jeg ikke gjøre noen bytter, så jeg er ferdig."
Så vi har et best-case kjøretid på Ω (n).
La oss kjøre boble sortere på en liste.
Eller først, la oss bare se på noen pseudokode veldig raskt.
Vi ønsker å si at vi ønsker å holde styr på, i alle iterasjon av loopen,
holde styr på hvorvidt vi endret noen elementer.
Så grunnen til det er at vi kommer til å stoppe når vi ikke har byttet noen elementer.
Så ved starten av løkken vår har vi ikke byttet noe, så vi får si det er falsk.
Nå skal vi gå gjennom listen og sammenligne element i å element i + 1
og hvis det er slik at det er et større antall til venstre for et mindre tall,
så vi bare kommer til å bytte dem.
>> Og så skal vi huske at vi byttet et element.
Det betyr at vi trenger å gå gjennom listen minst 1 gang
fordi tilstanden der vi stoppet er når hele listen er allerede sortert,
som betyr at vi ikke har gjort noen bytter.
Så det er derfor vår tilstand her nede er "mens noen elementer har blitt byttet.
Så nå la oss bare se på dette som kjører på en liste.
Jeg har listen 5,0,1,6,4.
Bubble sortere skal starte helt på venstre, og det kommer til å sammenligne
The I elementene, så 0 til i + 1, som er elementet 1.
Det kommer til å si, vel 5> 0, men akkurat nå 5 er til venstre,
så jeg trenger å bytte 5 og 0.
Når jeg bytte dem, plutselig får jeg denne annen liste.
Nå 5> 1, så vi kommer til å bytte dem.
5 er ikke> 6, så vi trenger ikke å gjøre noe her.
Men 6> 4, så vi trenger å bytte.
Igjen må vi kjøre gjennom hele listen til slutt oppdage
at disse er ute av drift, bytte vi dem,
og på dette punktet må vi kjøre gjennom listen en gang til
å sørge for at alt er i orden sin, og på dette punktet boble slags er ferdig.
En annen algoritme for å ta noen elementer og sortere dem er valg slag.
Ideen bak utvalget typen er at vi kommer til å bygge opp en sortert del av listen
1 element om gangen.
>> Og måten vi skal gjøre det på er ved å bygge opp den venstre delen av listen.
Og i utgangspunktet, hver - på hvert trinn, vi kommer til å ta den minste elementet vi har igjen
som ikke har blitt sortert ennå, og vi kommer til å flytte den inn i det sortert segmentet.
Det betyr at vi må kontinuerlig finne minimum usortert element
og deretter ta det minimum element og bytte det med hva
venstre-mest element som ikke er sortert.
Den kjører tid dette kommer til å være O (n ²) fordi i verste fall
vi trenger å sammenligne hver enkelt element til alle andre element.
Fordi vi sier at hvis vi starter på venstre halvdel av listen, må vi
å gå gjennom hele høyre segment å finne det minste elementet.
Og så, igjen, må vi gå over hele høyre segment og
holde gå over at over og over og over igjen.
Det kommer til å være n ². Vi kommer til å trenge en for løkke inne i en annen for loop
noe som antyder n ².
I beste fall tanken, la oss si at vi gir den en allerede sortert liste;
vi faktisk ikke gjøre noe bedre enn n ².
Fordi utvalget slags har ingen måte å vite at
minimum element er bare den jeg tilfeldigvis være å se på.
Det må likevel sørge for at dette faktisk er et minimum.
>> Og den eneste måten å sørge for at det er minimum, ved hjelp av denne algoritmen,
er å se på hvert enkelt element på nytt.
Så egentlig, hvis du gir den - hvis du gir utvalget sortere en allerede sortert liste,
det er ikke til å gjøre noe bedre enn å gi det en liste som ikke er sortert ennå.
Forresten, hvis det skjer for å være tilfelle at noe er O (noe)
og omega for noe, kan vi bare si mer konsist at det er θ av noe.
Så hvis du ser at kommer opp hvor som helst, det er hva det betyr bare.
>> Hvis noe er theta av n ², er det både store O (n ²) og Ω (n ²).
Så best case og worst case, betyr det ikke gjøre en forskjell,
algoritmen kommer til å gjøre det samme hver gang.
Så dette er hva pseudokode for valg slags kunne se ut.
Vi er i utgangspunktet tenkt å si at jeg ønsker å iterere over listen
fra venstre til høyre, og på hver iterasjon av loopen, jeg kommer til å flytte
minimum elementet inn dette sortert del av listen.
Og når jeg flytter noe der, jeg trenger aldri å se på dette elementet på nytt.
Fordi så snart jeg bytte et element i den venstre delen av listen, er det sortert
fordi vi gjør alt i stigende rekkefølge ved hjelp av minimumskrav.
Så vi sa, ok, vi i posisjon i, og vi trenger å se på alle elementene
til høyre for i i for å finne den minste.
Så det betyr at vi ønsker å se fra i + 1 til slutten av listen.
Og nå, hvis elementet som vi for tiden ser på er mindre enn minimum vår så langt,
som, husk, vi starter minimum av å bare være
uansett element vi er nå på, jeg vil anta det er minimum.
Hvis jeg finner et element som er mindre enn det, så jeg kommer til å si, ok,
vel, jeg har funnet en ny minimum.
Jeg kommer til å huske hvor det minimum var.
>> Så nå, når jeg har gått gjennom det høyre usortert segment,
Jeg kan si jeg kommer til å bytte den minste element med elementet som er i posisjon i.
Det kommer til å bygge opp min liste, min sortert del av listen fra venstre til høyre,
og vi ikke trenger å se på et element på nytt når den er i den delen.
Når vi har byttet den.
Så la oss kjøre utvalg sortere på denne listen.
Den blå element her kommer til å bli i, og den røde element kommer til å være det minste elementet.
Så jeg begynner helt til venstre på listen, så på 5.
Nå må vi finne minimum usortert element.
Så vi sier 0 <5, så 0 er min nye minimum.
>> Men jeg kan ikke stoppe der, for selv om vi kan gjenkjenne at 0 er den minste,
vi trenger å kjøre gjennom alle andre element i listen for å være sikker.
Så en er større, er 6 større, er 4 større.
Det betyr at etter å se på alle disse elementene, har jeg bestemt 0 er den minste.
Så jeg kommer til å bytte 5 og 0.
Når jeg bytte det, kommer jeg til å få en ny liste, og jeg vet at jeg aldri trenger å se på at 0 igjen
fordi når jeg har byttet den, har jeg sortert det og vi er ferdige.
Nå er det bare så skjer at den blå element er igjen 5,
og vi trenger å se på 1, 6 og 4 for å fastslå at en
er den minste minimum element, slik at vi vil bytte 1 og 5.
Igjen må vi se på - sammenligne 5 til 6 og 4,
og vi kommer til å bytte 4 og 5, og til slutt, sammenligne
de to tallene og bytte dem inntil vi får vår sortert liste.
Eventuelle spørsmål om valg sort?
Okay. La oss flytte til det siste temaet her, og det er rekursjon.
>> Rekursjon, husk, dette er virkelig meta ting der en funksjon
gjentatte ganger kaller seg.
Så på et tidspunkt, mens vår fuction er gjentatte ganger kaller seg,
det må være et tidspunkt der vi slutte å kalle oss selv.
Fordi hvis vi ikke gjør det, så vi bare kommer til å fortsette å gjøre dette for alltid,
og vårt program er bare ikke til å si opp.
Vi kaller denne tilstanden base case.
Og basen saken sier, snarere enn å ringe en funksjon igjen,
Jeg bare kommer til å returnere noen verdi.
Så når vi har kommet tilbake en verdi, har vi sluttet å ringe oss,
og resten av samtalene vi har gjort så langt kan også returnere.
Det motsatte av basen saken er den rekursive tilfelle.
Og dette er når vi ønsker å foreta et nytt anrop til funksjonen som vi er nå i.
Og vi sannsynligvis, men ikke alltid, vil bruke forskjellige argumenter.
>> Så hvis vi har en funksjon som heter f, og f bare kalt ta en argument,
og vi bare holde ringer f (1), f (1), f (1), og det bare så skjer at
argumentet en faller i rekursiv tilfelle, vi likevel aldri kommer til å stoppe.
Selv om vi har en base case, må vi sørge for at vi til slutt kommer til å treffe base case.
Vi har ikke bare holde bor i dette rekursive tilfellet.
Vanligvis, når vi kaller oss, vi sannsynligvis kommer til å ha en annen argument hver gang.
Her er en veldig enkel rekursiv funksjon.
Så dette vil beregne fakultet til et tall.
Opp toppen her vi har vår base case.
I tilfelle at n ≤ 1, vi kommer ikke til å ringe fakultet igjen.
Vi kommer til å stoppe, vi bare kommer til å returnere noen verdi.
Hvis dette ikke er sant, så vi kommer til å treffe våre rekursiv tilfelle.
Legg merke til her at vi ikke bare kalle fakultet (n), fordi det ikke ville være svært nyttig.
Vi kommer til å kalle fakultet av noe annet.
>> Og så kan du se, til slutt hvis vi passerer en faktorielt (5) eller noe,
vi kommer til å kalle fakultet (4) og så videre, og til slutt skal vi treffe denne base case.
Så dette ser bra ut. La oss se hva som skjer når vi faktisk kjøre dette.
Dette er bunken, og la oss si at main kommer til å kalle denne funksjonen med et argument (4).
Så når fakultet ser og = 4, vil fakultet kalle seg.
Nå, plutselig, har vi fakultet (3).
Så disse funksjonene skal vokse inntil vi til slutt traff vår base case.
På dette punktet, er returverdien av dette avkastningen (nx returverdien av dette),
returverdien av dette er nx returverdien av dette.
Til slutt må vi treffe noen tall.
På toppen her, sier vi tilbake en.
Det betyr at når vi kommer tilbake det nummeret, kan vi pop dette av stabelen.
Så dette fakultet (1) er gjort.
Når en er tilbake, denne faktorielle (1) returer, denne avkastningen til en.
Returverdien av dette, husk, var nx returverdien av dette.
Så plutselig, vet denne fyren som jeg ønsker å gå tilbake to.
>> Så husk, tilbake verdien av dette er bare nx returverdien opp her.
Så nå kan vi si 3 x 2, og til slutt, her kan vi si
dette er bare kommer til å være 4 x 3 x 2.
Og når dette kommer tilbake, får vi ned til en enkelt heltall innsiden av main.
Eventuelle spørsmål om rekursjon?
OK. Så det er mer tid til spørsmål på slutten,
men nå Joseph vil dekke de resterende emnene.
>> [Joseph Ong] Greit. Så nå som vi har snakket om rekursjoner,
la oss snakke litt om hva fusjonere slags er.
Flette sort er i utgangspunktet en annen måte å sortere en liste med tall.
Og hvordan det fungerer er, med fletting typen du har en liste, og det vi gjør er
vi sier, la oss dele dette inn i to halvdeler.
Vi vil først kjøre flette sortere igjen på venstre halvdel,
så får vi kjøre flette slag på høyre halvdel,
og det gir oss nå 2 halvdeler som er sortert, og nå skal vi kombinere disse halvdelene sammen.
Det er litt vanskelig å se uten et eksempel, så vi vil gå gjennom bevegelser og se hva som skjer.
Så du begynner med denne listen, vi delt det inn i to halvdeler.
Vi kjører flette slag på venstre halvdel først.
Så det er den venstre halvdelen, og nå har vi kjørt dem gjennom denne listen igjen
som blir ført inn fusjonere sortere, og vi ser igjen,
på venstre side av denne listen og kjøre vi flette sorter på den.
Nå får vi ned til en liste over 2 tall,
og nå den venstre halvdelen er bare 1 element lang, og vi kan ikke
dele en liste som er bare 1 element i halv, så vi bare si, når vi har 50,
som er bare 1 element, er det allerede sortert.
>> Når vi er ferdige med det, kan vi se at vi kan
gå videre til høyre halvdel av denne listen,
og 3 er også sortert, og så nå at begge halvdelene av denne listen er sortert
Vi kan delta i disse tallene sammen.
Så vi ser på 50 og 3, 3 er mindre enn 50, så det går i første og deretter 50 kommer inn
Nå er det gjort, vi går tilbake til den listen og sortere det er høyre halvdel.
42 er det egne tall, så det er allerede sortert.
Så nå er vi sammenligne disse 2 og 3 er mindre enn 42, så det blir satt inn først,
nå 42 blir satt inn, og 50 blir satt i.
Nå, det er sortert, går vi helt tilbake til toppen, 1337 og 15.
Vel, vi nå ser på den venstre halvdelen av denne listen, 1337 er i seg selv så det er sortert og samme med 15.
Så nå har vi kombinere disse to tallene å sortere det opprinnelige listen, 15 <1337,
så det går i først, deretter 1337 går i.
Og nå har vi sortert begge halvdelene av den opprinnelige listen opp toppen.
Og alt vi trenger å gjøre er å kombinere disse.
Vi ser på de 2 første numrene til denne listen, 3 <15, så det går inn i slags matrise først.
15 <42, så det går i. Nå, 42 <1337, som går i.
50 <1337, så det går i. Og legg merke til at vi bare tok 2 tall ut av denne listen.
Slik at vi ikke bare vekslende mellom de 2 listene.
Vi ser bare i begynnelsen, og vi tar elementet
det er mindre og deretter sette det inn matrise vår.
Nå har vi slått sammen alle halvdeler og vi er ferdige.
>> Eventuelle spørsmål om utskriftsfletting sort? Ja?
[Student] Hvis det er splitting i ulike grupper, hvorfor ikke de bare dele det en gang
og du har 3 og 2 i en gruppe? [Resten av spørsmålet uforståelig]
Grunnen - så spørsmålet er, hvorfor kan vi ikke bare slå dem på det første skrittet etter at vi har dem?
Grunnen til at vi kan gjøre dette, starter på venstre de fleste elementer på begge sider,
og deretter ta den mindre og sette det inn, er at vi vet at disse
enkelte listene er i sortert bestillinger.
Så hvis jeg ser på lengst til venstre elementer av begge omganger,
Jeg vet at de kommer til å være de minste elementene i disse listene.
Så jeg kan sette dem inn i de minste element flekker av denne store listen.
På den annen side, hvis jeg ser på de to listene i det andre nivået der borte,
50, 3, 42, 1337 og 15, er de som ikke sorteres.
Så hvis jeg ser på 50 og 1337, kommer jeg til å sette 50 inn liste min første.
Men det gjør ikke egentlig fornuftig, fordi 3 er det minste elementet ut av alle disse.
Så den eneste grunnen til at vi kan gjøre dette kombinere trinnet er fordi våre lister er allerede sortert.
Som er grunnen til at vi må få ned hele veien til bunnen
fordi når vi har bare et enkelt tall, vet du at et enkelt tall
i seg selv er allerede en sortert liste.
>> Eventuelle spørsmål? Nei?
Kompleksitet? Vel, kan du se at på hvert trinn er det slutt tall,
og vi kan dele en liste i halvparten log n ganger,
som er der vi får dette n x log n kompleksitet.
Og du vil se den beste saken for flettingen sort er n log n, og det bare så skjer
at verste fall, eller Ω der borte, er også n log n.
Noe å huske på.
Flytte på, la oss gå videre til noen super grunnleggende fil I / O.
Hvis du har sett på Scramble, vil du legge merke vi hadde noen form for system
hvor du kan skrive til en loggfil hvis du leser gjennom koden.
La oss se hvordan du kan gjøre det.
Vel, vi har fprintf, som du kan tenke på som bare printf,
men bare skrive til en fil i stedet, og dermed f i begynnelsen.
Denne typen kode her oppe, hva den gjør er, som du kanskje har sett i Scramble,
det går gjennom to-dimensjonal array utskrift ut rad for rad hva tallene er.
I dette tilfellet, skriver printf ut til terminalen eller hva vi kaller standard utgang av delen.
>> Og nå, i dette tilfellet, er alt vi trenger å gjøre bytte printf med fprintf,
fortelle den hva filen du vil skrive ut på, og i dette tilfellet bare det skrives det ut til at filen
stedet for å skrive den ut til terminalen.
Vel, da ber spørsmålet: Hvor får vi denne typen fil fra, ikke sant?
Vi passerte logge på denne fprintf fuction men vi hadde ingen anelse om hvor det kom fra.
Vel, tidlig i koden, hva vi hadde var denne del av koden over her,
som sier i utgangspunktet at åpne filen kaller log.txt.
Hva vi gjør etter det er vi nødt til å sørge for at filen faktisk åpnet vellykket.
Så det kan mislykkes av flere grunner, du har ikke nok plass på datamaskinen, for eksempel.
Så det er alltid viktig før du gjør noen operasjoner med filen
at vi sjekker om filen ble åpnet vellykket.
Så hva det en, er at et argument til fopen, vel, kan vi åpne en fil på mange måter.
Hva vi kan gjøre er, kan vi gi det w, noe som betyr overstyre filen hvis det kommer allerede,
Vi kan passere en a, som de føyer til slutten av filen i stedet tilsidesette den,
eller vi kan spesifisere r, noe som betyr, la oss åpne filen som skrivebeskyttet.
Så hvis programmet forsøker å gjøre noen endringer i filen,
kjefte på dem og ikke la dem gjøre det.
Til slutt, når vi er ferdig med filen, gjort gjør operasjoner på det,
Vi må sørge for at vi lukke filen.
Og så på slutten av programmet, skal du passere dem igjen
denne filen som du åpnet, og bare lukke den.
Så dette er noe viktig som du må sørge for at du gjør.
Så husk at du kan åpne en fil, så kan du skrive til filen,
gjøre operasjoner i filen, men da må du lukke filen på slutten.
>> Eventuelle spørsmål om grunnleggende fil I / O? Ja?
[Student spørsmål, uforståelig]
Akkurat her. Spørsmålet er, der gjør dette Log.txt vises?
Vel, hvis du bare gi den log.txt, skaper det den i samme katalog som den kjørbare.
Så hvis du har kommet - >> [Student spørsmål, uforståelig]
Ja. I samme mappe, eller i samme katalog, som du kaller det.
Nå minne, stack, og heap.
Så hvordan er minne lagt ut i datamaskinen?
Vel, du kan forestille minne som liksom denne blokken her.
Og i minnet har vi det som kalles haug fast der, og stakken som er der nede.
Og haugen vokser nedover og stakken vokser oppover.
Så som Tommy nevnt - oh, vel, og vi har disse andre 4 segmenter som jeg vil komme til i et sekund -
Som Tommy sa tidligere, vet du hvordan hans funksjoner selv ringe og ringe hverandre?
De bygger opp denne typen stabelen ramme.
Vel, hvis viktigste samtaler foo, blir foo satt på stakken.
Foo kaller bar, bar få oss sette på stakken, og som blir satt på bunken etter.
Og som de kommer tilbake, de hver får tatt av stabelen.
Hva holder hver av disse stedene og minne gjøre?
Vel, inneholder toppen, som er den tekstsegment, selve programmet.
Så maskinkode, som er der når du kompilere programmet.
Neste, noen initialisert globale variabler.
>> Så du har globale variabler i programmet, og si at du liker, a = 5,
som blir satt i det segmentet, og rett under det,
du har noen uinitialiserte globale data, som er int bare en,
men du ikke si det er lik noe.
Innse disse er globale variabler, så de er utenfor viktigste.
Så dette betyr noen globale variabler som deklareres, men er ikke initialisert.
Så hva er i haugen? Minnebruken bruker malloc, som vi vil komme til i en liten bit.
Og til slutt, med bunken har du noen lokale variabler
og eventuelle funksjoner du kan ringe inn noen av sine parametere.
Det siste, trenger du egentlig ikke trenger å vite hva miljøvariabler gjøre,
men når du kjører programmet, det er noe forbundet, som
Dette er brukernavnet til personen som kjørte programmet.
Og det kommer til å være slags nederst.
I form av minneadresser, som er heksadesimalverdier,
verdiene øverst start på 0, og de går hele veien ned til bunnen.
I dette tilfellet, hvis du er på 32-bit system,
adressen nederst kommer til å være 0x, etterfulgt av af, fordi det er 32 biter,
som er 8 byte, og i dette tilfellet 8 byte tilsvarer åtte heksadesimale sifre.
Så her nede du kommer til å ha, liker, 0xffffff, og der oppe du kommer til å ha 0.
Så hva er pekere? Noen av dere har kanskje ikke dekket dette i avsnittet før.
men vi gikk over den i foredraget, så en peker er bare en datatype
hvilke butikker, i stedet for noen slags verdi som 50 lagrer den adressen til noen sted i minnet.
Sånn minne [uforståelig].
Så i dette tilfellet, hva vi har er, har vi en peker til et heltall eller en int *,
og den inneholder denne heksadesimale adressen 0xDEADBEEF.
>> Så det vi har er nå, dette peker på noen sted i minnet,
og det er bare en, er verdien 50 på denne minneplassen.
På noen 32-bits systemer, på alle 32-bits systemer, pekere ta opp 32 biter eller 4 byte.
Men, for eksempel på en 64-bits system, pekere er 64 bits.
Så det er noe du ønsker å huske på.
Så på en slutt-bit system, er en peker kantskjær lang.
Pekere er slags vanskelig å fordøye uten ekstra ting,
så la oss gå gjennom et eksempel på dynamisk minne allokering.
Hva dynamisk minne allokering gjør for deg, eller hva vi kaller malloc,
den lar deg fordele noen form for data utenfor settet.
Så disse opplysninger er slags mer permanent for varigheten av programmet.
Fordi som du vet, hvis du deklarerer x innsiden av en funksjon, og at funksjonen returnerer,
du ikke lenger har tilgang til dataene som ble lagret i x.
Hva pekere la oss gjøre er de la oss lagre minne eller lagre verdier
i en annen del av minnet, nemlig haugen.
Nå når vi går tilbake ut av funksjon, så lenge vi har en peker
til det stedet i minnet, så hva vi kan gjøre er at vi kan bare se på verdiene der.
La oss se på et eksempel: Dette er vår hukommelse layout igjen.
Og vi har denne funksjonen, main.
Hva den gjør er - okay, så enkelt, ikke sant? - Int x = 5, det er bare en variabel på stabelen i hovedvinduet.
>> På den annen side, nå er vi erklærer en peker som kaller funksjonen giveMeThreeInts.
Og så nå går vi inn i denne funksjonen, og vi oppretter en ny bunke ramme for det.
Men i denne bunken ramme, erklærer vi int * temp,
som i mallocs 3 heltall for oss.
Så størrelsen på int vil gi oss hvor mange byte denne int er,
og malloc gir oss at mange byte av plass på haugen.
Så i dette tilfellet, har vi skapt nok plass til tre heltall,
og haugen er veien opp dit, og det er derfor jeg har trukket den høyere opp.
Når vi er ferdig, vi kommer tilbake hit, trenger du bare tre ints tilbake,
og den returnerer adressen, i dette tilfellet over hvor at minnet er.
Og vi setter pekeren = bryteren, og der oppe har vi bare en annen pekeren.
Men hva som fungerer avkastning er stablet her og forsvinner.
Så temp forsvinner, men vi fortsatt opprettholde adressen der
de tre heltall er inne i strømnettet.
Så i dette settet, pekere er scoped lokalt for stablet ramme,
men minnet som de henviser er i haugen.
>> Gjør det fornuftig?
[Student] Kan du gjenta det? >> [Joseph] Ja.
Så hvis jeg går tilbake bare en liten bit, ser du at temp tildelt
noe minne på haugen der oppe.
Så når denne funksjonen, giveMeThreeInts avkastning, er denne bunken her kommer til å forsvinne.
Og med det noen av variablene, i dette tilfellet, denne pekeren som ble tildelt i stablet ramme.
Som kommer til å forsvinne, men siden vi returnerte temp
og vi setter pekeren = temp, peker nå går til å peke i samme minne plassering som temp var.
Så nå, selv om vi mister temp, at lokal pekeren,
vi fortsatt beholde minnet adressen på hva det var som peker til innsiden av den variabelen pekeren.
Spørsmål? Det kan være slag av en forvirrende emnet hvis du ikke har gått over det i snitt.
Vi kan, vil TF definitivt gå over det og selvfølgelig kan vi svare på spørsmål
ved slutten av gjennomgangen sesjon for dette.
Men dette er liksom et komplekst tema, og jeg har flere eksempler som kommer til å dukke opp
som vil bidra til å avklare hva pekere faktisk er.
>> I dette tilfellet, pekere er tilsvarer matriser,
så jeg kan bare bruke denne pekeren som det samme som en int array.
Så jeg indeksering inn 0, og endre den første heltall til 1,
endre andre heltall til 2, og den tredje heltall til 3.
Så mer på pekere. Vel, husker Binky.
I dette tilfellet har vi tildelt en peker, eller vi erklært en peker,
men i utgangspunktet, når jeg nettopp erklært en peker, det er ikke peker til hvor som helst i minnet.
Det er bare søppel tall inne i den.
Så jeg har ingen anelse om hvor denne pekeren peker til.
Den har en adresse som er bare fylt med 0 og 1-ere der den opprinnelig ble erklært.
Jeg kan ikke gjøre noe med dette før jeg kaller malloc på det
og da det gir meg en liten plass på haugen hvor jeg kan sette verdier inne.
Så igjen, jeg vet ikke hva som er på innsiden av dette minnet.
Så det første jeg må gjøre er å sjekke om systemet hadde nok minne
å gi meg tilbake en heltall i første omgang, og det er derfor jeg gjør dette sjekk.
Hvis pekeren er null, betyr det at det ikke har nok plass eller annen feil har oppstått,
så jeg skal gå ut av programmet mitt.
Men hvis det lyktes, nå kan jeg bruke den peker
og hva * pekeren gjør er det følger hvor adressen er
hvor denne verdien er, og det setter den lik en.
Så over her, vi sjekker om det minnet eksisterte.
>> Når du vet det finnes, kan du sette inn i den
hvilken verdi du ønsker å legge i det, i dette tilfellet en.
Når vi er ferdig med det, må du frigjøre at pekeren
fordi vi trenger å komme tilbake til det systemet som minnet som du ba om i første omgang.
Fordi datamaskinen ikke vet når vi er ferdig med det.
I dette tilfellet er vi eksplisitt forteller det, ok, vi er ferdige med dette minnet.
Hvis en annen prosess trenger det, et annet program trenger det, gjerne gå videre og ta den.
Hva vi kan også gjøre er at vi kan bare få adressen lokale variabler på settet.
Så int x er innenfor stablet rammen av main.
Og når vi bruker denne ampersand, dette og operatør, hva den gjør er
det tar x, og x er bare noen data i minnet, men det har en adresse.
Det ligger et sted. Så ved å ringe & x, hva dette betyr er det gir oss adressen x.
Ved å gjøre dette, gjør vi pekeren peker til hvor x er i minnet.
Nå er vi bare gjøre noe sånt * x, vi kommer til å få 5 tilbake.
Stjernen kalles dereferencing det.
Du følger den adressen og du får verdien av det som er lagret der.
>> Eventuelle spørsmål? Ja?
[Student] Hvis du ikke gjør det 3-spiss ting, gjør det likevel kompilere?
Ja. Hvis du ikke gjør det 3-pekeren ting, er det fortsatt kommer til å kompilere,
men jeg skal vise deg hva som skjer i et sekund, og uten å gjøre det,
det er hva vi kaller en minnelekkasje. Du ikke gir systemet
tilbake sin hukommelse, så etter en stund programmet kommer til å akkumulere
minne som det ikke er bruk, og ingenting annet kan bruke den.
Hvis du noensinne har sett Firefox med 1,5 millioner kilobyte på datamaskinen,
i oppgaven manager, det er hva som skjer.
Du har en minnelekkasje i programmet at de ikke håndterer.
Så hvordan pekeren aritmetiske arbeid?
Vel, er pekeren aritmetiske liksom som indeksering inn i en matrise.
I dette tilfellet har jeg en peker, og hva jeg gjør er jeg gjør pekeren peker til det første elementet
av denne matrisen av 3 heltall som jeg har tildelt.
Så nå hva jeg gjør, endrer stjerne pekeren bare det første elementet i listen.
Stjerners pekeren en poeng over her.
Så pekeren er over her, er pekeren en over her, er pekeren to over her.
>> Så bare legge en er det samme som å flytte langs denne matrisen.
Hva vi gjør er, når vi gjør pekeren en du få adressen over her,
og for å få verdien her, legger du en stjerne i fra hele uttrykket
å dereferanse det.
Så, i dette tilfellet, jeg sette første beliggenhet i dette matrise til 1,
andre beliggenhet til 2, og tredje sted til 3.
Så hva jeg gjør over her er jeg skrive vår pekeren +1,
som gir meg to.
Nå er jeg inkrementering pekeren, så peker tilsvarer pekeren +1,
som beveger den frem.
Og så nå hvis jeg skriver ut pekeren +1, er pekeren en nå 3,
som i dette tilfelle skrives ut 3.
Og for å frigjøre noe, pekeren at jeg gir det
må peke på begynnelsen av tabellen som jeg kom tilbake fra malloc.
Så, i dette tilfellet, hvis jeg skulle ringe tre her, ville dette ikke være riktig,
fordi den er i midten av matrisen.
Jeg må trekke for å komme til den opprinnelige plasseringen
den innledende første sted før jeg kan få det løs.
Så, her er en mer involvert eksempel.
I dette tilfellet, vi fordele 7 tegn i et tegn array.
>> Og i dette tilfellet hva vi gjør er at vi looping over den første 6 av dem,
og vi setter dem til Z.
Så, for int i = 0, i> 6, i + +,
Så peker + jeg vil bare gi oss, i dette tilfellet,
pekeren, en pekeren, 2 pekeren, 3 pekeren, og så videre og så videre i loop.
Hva det kommer til å gjøre er det blir den adressen, dereferences det å få verdien,
og endringer som verdi til en Z.
Deretter på slutten huske dette er en streng, ikke sant?
Alle strenger må slutte med null avslutning karakter.
Så, det jeg gjør er i peker 6 la jeg null terminator tegnet i.
Og nå hva jeg egentlig gjør her borte gjennomfører printf for en streng, ikke sant?
>> Så, når printf nå når det har nådd slutten av en streng?
Når den treffer null avslutte tegn.
Så, i dette tilfellet, min opprinnelige peker til begynnelsen av denne tabellen.
Jeg skriver inn det første tegnet ut. Jeg flytter den over ett.
Jeg skriver det tegnet ut. Jeg flytter den over.
Og jeg holder på til jeg når slutten.
Og nå til slutt * pekeren vil dereference dette og få null avslutte tegn tilbake.
Og så min mens loop kjører bare når denne verdien ikke er null avslutte tegn.
Så nå er jeg gå ut av denne loopen.
Og så hvis jeg trekker 6 fra denne pekeren,
Jeg går tilbake helt til begynnelsen.
Husk, jeg gjør dette fordi jeg må gå til begynnelsen for å frigjøre den.
>> Så, jeg vet det var mye. Er det noen spørsmål?
Vær så snill, ja?
[Student spørsmålet uforståelig]
Kan du si at høyere? Unnskyld.
[Student] På det siste lysbildet rett før du frigjort pekeren,
hvor ble du faktisk endre verdien av pekeren?
[Joseph] Så akkurat her. >> [Student] Oh, okay.
[Joseph] Så har jeg en peker minus minus, høyre,
som flytter ting tilbake en, og da jeg frigjøre det,
fordi denne pekeren har å bli henvist til begynnelsen av tabellen.
[Student] Men det ville ikke være nødvendig hvis du hadde stoppet etter den linjen.
[Joseph] Så hvis jeg hadde stoppet etter dette, ville dette bli betraktet som en minnelekkasje,
fordi jeg ikke kjøre gratis.
[Student] I [uforståelig] etter de tre første linjene der du hadde markøren en [uforståelig].
[Joseph] Uh-huh. Så, hva er spørsmålet der?
Unnskyld. Nei, nei. Gå, gå, takk.
[Student] Så, er du ikke endre verdien av pekere.
Du ville ikke ha hatt å gjøre pekeren minus minus.
[Joseph] Ja, akkurat.
Så, når jeg gjør pekeren en og peker +2,
Jeg er ikke gjør pekeren lik pekeren +1.
Så pekeren bare forblir peker på begynnelsen av tabellen.
Det er bare når jeg gjør pluss pluss at det setter verdien tilbake inne pekeren,
at den beveger seg faktisk dette sammen.
OK.
Flere spørsmål?
>> Igjen, hvis dette er slags overveldende, vil dette bli dekket i økten.
Spør din undervisning stipendiat om det, og vi kan svare på spørsmål på slutten.
Og vanligvis vi ikke liker å gjøre dette minus ting.
Dette må kreve meg å holde styr på hvor mye jeg har forskjøvet i tabellen.
Så, generelt, er dette bare for å forklare hvordan pekeren aritmetiske fungerer.
Men hva vi vanligvis liker å gjøre er vi ønsker å lage en kopi av pekeren,
og så får vi bruke dette eksemplaret når vi flytter rundt i strengen.
Så, i disse tilfelle du bruker kopien til å skrive ut hele strengen,
men vi trenger ikke å gjøre som peker minus 6 eller holde styr på hvor mye vi flyttet i dette,
bare fordi vi vet at vår opprinnelige punktet er fortsatt pekt på begynnelsen av listen
og alt som vi endret var denne kopien.
Så generelt, endre kopier av den opprinnelige pekeren.
Ikke prøv å sortere av som - ikke endre originale kopier.
Prøver å endre bare kopier av originalen.
Så, du merker når vi passerer strengen til printf
du trenger ikke å sette en stjerne foran det som vi gjorde med alle de andre dereferences, ikke sant?
Så hvis du skriver ut hele strengen% s forventer er en adresse,
og i dette tilfellet en peker eller i dette tilfellet som en rekke tegn.
>> Tegn, char * s, og arrayer er det samme.
Pointer er å tegn, og tegn arrays er det samme.
Og så, er pass alt vi trenger å gjøre i pekeren.
Vi trenger ikke å passere i like * pekeren eller noe sånt.
Så, arrays og pekere er det samme.
Når du gjør noe sånt x [y] over her for en matrise,
hva det gjør under panseret er det å si, ok, det er et tegn array,
så det er en peker.
Og så x er det samme,
og så hva den gjør er det legger y til x,
som er det samme som å flytte frem i minnet så mye.
Og nå x + y gir oss en slags adresse,
og vi dereferanse adressen eller følg pilen
hvor den plasseringen i minnet er og vi får verdi ut av det sted i minnet.
Så, så disse to er akkurat det samme.
Det er bare en syntaktisk sukker.
De gjør det samme. De er bare forskjellige syntactics for hverandre.
>> Så, hva kan gå galt med pekere? Som, mye. Okay. Så dårlige ting.
Noen dårlige ting du kan gjøre er ikke å sjekke om din malloc kallet returnerer null, ikke sant?
I dette tilfellet, ber jeg om systemet for å gi meg - hva er det nummeret?
Som 2 milliarder ganger 4, fordi størrelsen av et heltall er 4 byte.
Jeg ber den for som 8 milliarder bytes.
Selvfølgelig min datamaskin ikke kommer til å være i stand til å gi meg så mye minne tilbake.
Og vi fikk ikke sjekke om dette er null, så når vi prøver å dereference det der -
følge pilen til hvor det kommer til å - vi har ikke det minnet.
Dette er hva vi kaller dereferencing en nullpeker.
Og dette fører i hovedsak å segfault.
Dette er en av måtene du kan segfault.
Andre dårlige ting du kan gjøre - nåvel.
Det var dereferencing en nullpeker. Okay.
Andre dårlige ting - vel, for å fikse at du bare sette en sjekk der
som sjekker om pekeren er null
og gå ut av programmet hvis det skjer at malloc returnerer en nullpeker.
Det er xkcd komisk. Folk forstår det nå. Liksom.
>> Så, minne. Og jeg gikk over dette.
Vi kaller malloc i en loop, men hver gang vi kaller malloc
vi mister oversikten over hvor denne pekeren peker til,
fordi vi clobbering det.
Så gir den første telefonsamtalen til malloc meg minne over her.
Min pekeren pekere til dette.
Nå, jeg vet ikke frigjøre det, så nå er jeg kaller malloc igjen.
Nå er det peker over her. Nå er min hukommelse peker over her.
Peker over her. Peker over her.
Men jeg har mistet oversikten over adressene til alle minnet over her at jeg tildelt.
Og så nå er jeg ikke har noen referanse til dem lenger.
Så, jeg kan ikke fri dem utenfor denne sløyfen.
Og så for å fikse noe som dette,
Hvis du glemmer å frigjøre minne, og du får denne minnelekkasje,
Du må frigjøre minne innsiden av denne sløyfen når du er ferdig med det.
Vel, dette er hva som skjer. Jeg vet hater mange av dere dette.
Men nå - yay! Du får som 44000 kilobyte.
Så frigjøre deg det på slutten av loopen,
og det kommer til å bare frigjøre minne hver gang.
Hovedsak, ikke programmet ikke har en minnelekkasje lenger.
>> Og nå noe annet du kan gjøre er å frigjøre minne som du har bedt om to ganger.
I dette tilfellet, du malloc noe, endrer du verdien.
Du frigjøre det en gang fordi du sa at du var ferdig med den.
Men da vi frigjort det igjen.
Dette er noe som er ganske ille.
Det kommer ikke til å begynne med segfault,
men etter en stund hva dette betyr er dobbelt frigjøre dette ødelegger din heap struktur,
og du vil lære litt mer om dette hvis du velger å ta en klasse som CS61.
Men i hovedsak etter en stund datamaskinen kommer til å bli forvirret
om hva minneplasser er der og hvor det er lagret -
hvor data er lagret i minnet.
Og så frigjør en peker er dobbelt en dårlig ting som du ikke ønsker å gjøre.
>> Andre ting som kan gå galt er å ikke bruke sizeof.
Så, i dette tilfellet malloc du 8 byte,
og det er det samme som to heltall, ikke sant?
Så, det er helt trygt, men er det?
Vel, som Lucas snakket om på ulike arkitekturer,
heltall er av forskjellige lengder.
Så, på apparatet du bruker, heltall er ca 4 bytes,
men på en annen system kan de være 8 byte, eller de kan være 16 bytes.
Så, hvis jeg bare bruke dette nummeret over her,
dette programmet kan fungere på apparatet,
men det er ikke til å allokere nok minne på noen andre system.
I dette tilfellet er dette hva sizeof operatør brukes til.
Når vi kaller sizeof (int), hva dette betyr er
det gir oss størrelsen av et heltall på systemet at programmet kjøres.
Så, i dette tilfellet, vil sizeof (int) returnere 4 på noe sånt apparatet,
og nå dette vil 4 * 2, som er 8,
som er bare mengden plass nødvendig for to heltall.
På et annet system, hvis en int er som 16 byte eller 8 byte,
det er bare kommer til å returnere nok byte til å lagre dette beløpet.
>> Og til slutt, structs.
Så, hvis du ønsket å lagre en sudoku bord i minnet, kan hvordan vi gjør dette?
Du tenker kanskje som en variabel for det første,
en variabel for andre ting, en variabel for tredje tingen,
en variabel for fjerde ting - dårlig, ikke sant?
Så, er en forbedring du kan gjøre på toppen av dette for å gjøre en 9 x 9 matrise.
Det er fint, men hva om du ønsket å knytte andre ting med sudoku styret
liker det vanskeligheten av styret er,
eller, for eksempel, hva poengsummen din er, eller hvor mye tid det har tatt å løse dette brettet?
Vel, hva du kan gjøre er at du kan lage en struct.
Det jeg egentlig sier er jeg definere denne strukturen over her,
og jeg definere en sudoku styre som består av et styre som er 9 x 9.
>> Og hva det har det har pekere til navnet på nivået.
Det har også x og y, som er koordinatene for hvor jeg er akkurat nå.
Det har også tid brukt [uforståelig], og det har det totale antallet trekk jeg har lagt inn så langt.
Og så i dette tilfellet, kan jeg gruppere en hel haug med data til bare én struktur
i stedet for å ha det som flyr rundt i som ulike variabler
at jeg ikke kan virkelig holde styr på.
Og dette lar oss har bare gode syntaks for slags henvisning forskjellige ting innsiden av denne struct.
Jeg kan bare gjøre board.board, og jeg får sudoku styret tilbake.
Board.level, får jeg hvor tøft det er.
Board.x og board.y gi meg koordinatene for hvor jeg kan være i styret.
Og så jeg tilgang hva vi kaller felt i struct.
Dette definerer sudokuBoard, som er en type som jeg har.
Og nå er vi her. Jeg har en variabel kalt "bord" av typen sudokuBoard.
Og så nå kan jeg få tilgang til alle feltene som utgjør denne strukturen over her.
>> Eventuelle spørsmål om structs? Ja?
[Student] For int x, y, erklærte dere begge på én linje? >> [Joseph] Uh-huh.
[Student] Så kan du bare gjøre det med dem alle?
Som i X, Y komma ganger at totalt?
[Joseph] Ja, du kan definitivt gjøre det, men grunnen til at jeg satte x og y på samme linje -
og spørsmålet er hvorfor kan vi bare gjøre dette på samme linje?
Hvorfor vi ikke bare sette alle disse på samme linje er
x og y er relatert til hverandre,
og dette er bare stilistisk mer korrekt, på en måte,
fordi det er gruppering to ting på samme linje
som liker slags forholde seg til det samme.
Og jeg bare dele disse fra hverandre. Det er bare en stil ting.
Det gjør funksjonelt ingen forskjell overhodet.
Andre spørsmål om structs?
Du kan definere en Pokédex med en struct.
En Pokémon har et nummer og det har en bokstav, en eier, en type.
Og så hvis du har en rekke Pokémon, kan du lage et Pokédex, ikke sant?
Ok, kult. Så, spørsmål om structs. De er knyttet til structs.
>> Til slutt, GDB. Hva lar GDB du gjøre? Den lar deg feilsøke programmet.
Og hvis du ikke har brukt GDB, ville jeg anbefalt å se den korte
og bare gå over hva GDB er, hvordan du arbeider med det, hvordan du kan bruke det,
og teste den på et program.
Og så hva GDB lar deg gjøre det lar pause [uforståelig] opp programmet
og en praktisk linje.
For eksempel, jeg ønsker å ta en pause kjøring på som linje 3 av mitt program,
og mens jeg er på linje 3 Jeg kan skrive ut alle verdiene som er der.
Og så hva vi kaller som pause i en linje
er kaller vi dette å sette et stoppunkt på den linjen
og så kan vi skrive ut variabler på tilstanden til programmet på den tiden.
>> Vi kan da derfra gå gjennom programmet linje for linje.
Og så kan vi se på tilstanden av stabelen på den tiden.
Og så for å bruke GDB, det vi gjør er vi kaller clang på C-filen,
men vi må passere den-ggdb flagget.
Og når vi er ferdige med det vi bare kjøre gdb på den resulterende filen.
Og så får du noen som massen av tekst som dette,
men egentlig alt du trenger å gjøre er å skrive inn kommandoer i begynnelsen.
Break viktigste setter et stoppunkt på main.
Liste 400 viser linjer med kode rundt linje 400.
Og så i dette tilfellet kan du bare se deg rundt og si, oh,
Jeg ønsker å sette et stoppunkt på linje 397, som er denne linjen,
og deretter programmet går inn i det trinnet og det kommer til å bryte.
Det kommer til å ta en pause der, og du kan skrive ut, for eksempel verdien av lav eller høy.
Og så er det en haug med kommandoene du trenger å vite,
og denne lysbildefremvisning vil gå opp på nettstedet,
så hvis du bare ønsker å referere disse eller liker sette dem på jukse ark, gjerne.
>> Cool. Det var Quiz omtale 0, og vi vil holde rundt hvis du har spørsmål.
OK.
>> [Applaus]
>> [CS50.TV]