[Powered by Google Translate] [Review] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [Dette er CS50.] [CS50.TV]
>> Hej, alle sammen.
Velkommen til revision session for Quiz 0, som finder sted denne onsdag.
Hvad vi vil gøre i aften, jeg er sammen med 3 andre TF'er,
og sammen vil vi gå gennem en gennemgang af, hvad vi har gjort i løbet hidtil.
Det kommer ikke til at være 100% dækkende, men det bør give dig en bedre idé
af, hvad du allerede har ned og hvad du stadig nødt til at studere inden onsdag.
Og velkommen til at hæve din hånd med spørgsmål, som vi skal sammen,
men husk på, at vi også vil have en lille smule tid på end-
hvis vi komme igennem med et par minutter til overs til at gøre generelle spørgsmål,
så holder det i tankerne, og så vil vi starte ved begyndelsen med uge 0.
>> [Quiz 0 anmeldelse!] [Part 0] [Lexi Ross] Men før vi gør det lad os tale om
logistikken i quizzen.
>> [Logistik] [Quiz finder sted onsdag 10/10 i stedet for foredrag]
>> [(Se http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf for detaljer)] Det er på ONSDAG 10 okt.
>> Det er denne onsdag, og hvis du går til denne webadresse her,
som også er tilgængelig fra CS50.net-der er et link til det,
du kan se oplysninger om, hvor gå ud fra
dit efternavn eller skole tilhørsforhold samt
det fortæller om præcis, hvad quizzen vil dække og de typer af spørgsmål, som du kommer til at få.
Husk, at du også vil have en chance for at gennemgå for quizzen i snit,
så dine TF'er skal gå over nogle praksis problemer,
og det er en anden god chance for at se, hvor du stadig nødt til at studere op til quizzen.
Lad os starte ved begyndelsen med Bits 'n' Bytes.
Husk lidt er blot et 0 eller et 1,
og en byte er en samling af 8 af disse bit.
Lad os se på denne samling af bits lige her.
Vi bør være i stand til at regne ud hvor mange bit der er.
Hvor vi tælle der er bare 8 af dem, otte 0 eller 1 enheder.
Og da der er 8 bit, det er 1 byte,
og lad os konvertere det til hexadecimal.
Hexadecimal er base 16, og det er ret nemt at konvertere
et tal i binær, hvilket er hvad det er, til et i hexadecimal.
Alt hvad vi gør, er vi ser på grupper af 4,
og vi konvertere dem til den relevante hexadecimale tegn.
Vi starter med det yderste højre gruppe af 4, så 0011.
Det kommer til at være en 1 og en 2, så sammen det gør 3.
Og så lad os se på den anden blok af 4.
1101. Det kommer til at være en 1, en 4, og en 8.
Sammen der kommer til at være 13, hvilket gør D.
Og vi vil huske, at i hexadecimal vi ikke bare gå 0 til 9.
Vi går 0 til F, så efter 9, 10 svarer til A,
11 til B, et cetera hvor F er 15.
Her 13 er en D,
så at konvertere det til decimal alt, hvad vi gør, er vi faktisk
behandler hver position som en potens af 2.
Det er en 1, en 2, nul 4s, nul 8s, en 16, et cetera,
og det er lidt svært at beregne i dit hoved, men hvis vi går til det næste dias
Vi kan se svaret på det.
>> Grundlæggende vil vi på tværs fra højre tilbage til venstre,
og vi multiplicere hvert ciffer ved den tilsvarende potens af 2.
Og husk, for hexadecimal vi betegne disse tal med 0x ved begyndelsen
så vi ikke forveksle det med et decimaltal.
Fortsat på, er dette en ASCII tabel,
og hvad vi bruger ASCII for at kortlægge fra karakterer til numeriske værdier.
Husk i kryptografi Pset vi gjort udstrakt brug af ASCII tabel
for at anvende forskellige metoder til kryptering,
Den Cæsar og Vigenère cifferliste, at konvertere forskellige bogstaver
i en streng ifølge den nøgle, som brugeren.
Lad os se på en lille smule af ASCII matematik.
Se på 'P' + 1, i karakter form, der vil være Q,
og husk, at '5 '≠ 5.
Og præcis hvordan ville vi konvertere mellem disse 2 former?
Det er faktisk ikke alt for hårdt.
For at få 5 vi trækker '0 '
fordi der er 5 pladser mellem '0 'og '5'.
For at gå den anden vej vi blot tilføje 0,
så det er lidt ligesom almindelig aritmetik.
Bare husk, at når noget har anførselstegn omkring det, det er et tegn
og svarer således til en værdi i ASCII tabel.
Flytning ind i mere generelle datalogiske emner.
Vi lærte, hvad en algoritme er, og hvordan vi bruger programmering
at implementere algoritmer.
Nogle eksempler på algoritmer er noget virkelig simpelt lignende
kontrollere, om et tal er lige eller ulige.
Til det husker vi at moder antallet af 2 og kontrollere, om resultatet er 0.
Hvis det er tilfældet, er det endnu. Hvis ikke, det er underligt.
Og det er et eksempel på en virkelig grundlæggende algoritme.
>> Lidt af en mere involveret man er binær søgning,
som vi vil gå over senere i gennemgangen session.
Og programmering er det udtryk, vi bruger til at tage en algoritme
og omdanne den til at kode computeren kan læse.
2 eksempler på programmering er Scratch,
hvilket er, hvad vi gjorde i uge 0.
Selvom vi egentlig ikke skrive koden ud, det er en måde at gennemføre
denne algoritme, som udskriver tallene 1-10,
og her har vi at gøre det samme i C-programmeringssproget.
Det er funktionelt tilsvarende, bare skrevet på forskellige sprog eller syntaks.
Vi derefter lærte om boolean udtryk,
og en boolean er en værdi, der er enten sand eller falsk,
og her oftentimes boolean udtryk
gå indersiden af ​​betingelser, så hvis (x ≤ 5),
godt, vi allerede sat x = 5, så denne betingelse vil evaluere til true.
Og hvis det er sandt, hvad koden er under betingelse
vil blive evalueret af computeren, således at strengen skal udskrives
til standard output, og udtrykket tilstand
refererer til, hvad der er i parentes i if-sætningen.
Husk alle operatører.
Husk det er && og | | når vi forsøger at kombinere 2 eller flere betingelser,
== Ikke = at kontrollere, om 2 ting er ens.
Husk, at = er for tildeling hvorimod == er en boolsk operator.
≤, ≥ og derefter De sidste 2 er selvforklarende.
En generel gennemgang af boolesk logik her.
Og boolske udtryk er også vigtige i loops,
som vi vil gå over nu.
Vi lærte omkring 3 typer af løkker hidtil i CS50, for mens, og gøre, mens.
Og det er vigtigt at vide, at mens det for de fleste formål
vi rent faktisk kan bruge enhver form for løkke generelt
der er visse typer af formål eller fælles mønstre
i programmeringen, der specifikt kræver en af ​​disse loops
der gør den til den mest effektive eller elegant at kode det på den måde.
Lad os gå over, hvad hver af disse sløjfer tendens til at blive anvendt til oftest.
>> I en for-løkke vi generelt allerede ved, hvor mange gange vi ønsker at gentage.
Det er, hvad vi lægger i den tilstand.
For, i = 0, i <10, f.eks.
Vi ved allerede, at vi ønsker at gøre noget 10 gange.
Nu, for et stykke tid løkke, vi generelt ikke nødvendigvis
vide, hvor mange gange vi ønsker, løkken skal køre.
Men vi kender en form for betingelse, at vi ønsker det
altid være sandt eller altid være falsk.
For eksempel er under indstilles.
Lad os sige det er en boolesk variabel.
Selvom det er sandt, vi ønsker koden til at vurdere,
så en lille smule mere strækbar, lidt mere generel end en for-løkke,
men nogen for-løkke kan også omdannes til en while-løkke.
Endelig gøre, mens løkker, som kan være den vanskeligste at forstå med det samme,
bruges ofte, når vi ønsker at evaluere kode først
før første gang vi kontrollere tilstanden.
En almindelig anvendelse tilfældet for en do while løkke
er, når du ønsker at få bruger-input, og du ved, at du vil spørge brugeren
for input mindst én gang, men hvis de ikke give dig en god indgang med det samme
du ønsker at holde beder dem indtil de giver dig den gode input.
Det er den mest almindelige brug af en do while løkke,
og lad os se på den faktiske struktur i disse sløjfer.
De har typisk altid en tendens til at følge disse mønstre.
>> På for-løkken inde du har 3 komponenter:
initialisering, typisk noget lignende int i = 0 hvor i er tælleren,
tilstand, hvor vi ønsker at sige køre denne for-løkke, så længe denne betingelse stadig holder,
ligesom jeg <10, og så endelig, opdatering, som er, hvordan vi tilvækst
tællervariablen ved hvert punkt i sløjfen.
En fælles ting at se der er bare i + +,
hvilket betyder tilvækst i med 1 hver gang.
Du kan også gøre noget lignende i + = 2,
hvilket betyder tilsættes 2 til i hver gang du går gennem løkken.
Og så gør det bare henviser til enhver kode, der rent faktisk kører som en del af sløjfen.
Og for en while-løkke, denne gang vi faktisk har initialiseringen uden for løkken,
så for eksempel, lad os sige, vi forsøger at gøre det samme type løkke, som jeg lige har beskrevet.
Vi ville sige int i = 0 før løkken begynder.
Så kunne vi sige, mens jeg <10 gør dette,
så den samme kodeblok som før,
og denne gang opdateringen del af koden, for eksempel i + +,
faktisk går inde i sløjfen.
Og endelig, for en gør stykke tid, det ligner while-løkken,
men vi skal huske, at koden vil evaluere en gang
før tilstanden er valgt, så det gør meget mere mening
hvis man ser på det i rækkefølge fra top til bund.
I en do while løkke koden vurderer, før du selv se på imens tilstand,
hvorimod en while-løkke, tjekker det første.
Erklæringer og variabler.
Når vi ønsker at skabe en ny variabel vi først ønsker at initialisere det.
>> For eksempel initialiserer int bar den variable bar,
men det gør ikke give det en værdi, så hvad er bar værdi nu?
Vi ved det ikke.
Det kunne være en garbage værdi, der tidligere er lagret i hukommelsen der,
og vi ønsker ikke at bruge denne variabel
indtil vi faktisk give det en værdi,
så vi erklære den her.
Så vi initialisere det til at være 42 nedenfor.
Nu, selvfølgelig, ved vi det kan gøres på én linje, bar int = 42.
Men bare for at være klar til flere trin, der foregår,
erklæringen og initialisering sker separat her.
Det sker på et trin, og den næste, int baz = bar + 1,
denne erklæring, at intervaller Baz, så i slutningen af ​​denne kodeblok
hvis vi skulle til at udskrive værdien af ​​baz ville det være 44
fordi vi erklære og initialisere det at være 1> bar,
og så må vi øg det en gang mere med + +.
Vi gik over denne smukke kort, men det er godt at have en generel
forståelse af, hvad tråde og begivenheder er.
Vi hovedsagelig gjorde det i Scratch,
så du kan tænke på tråde som flere sekvenser af kode
kører samtidig.
I virkeligheden er det sandsynligvis ikke kører på samme tid,
men slags abstrakt vi kan tænke på det på den måde.
>> I Scratch, for eksempel havde vi de mange sprites.
Det kunne udføre anden kode på samme tid.
Man kunne til fods, mens den anden siger noget
i en anden del af skærmen.
Events er en anden måde at udskille den logik
mellem de forskellige elementer i din kode,
og i Scratch var vi i stand til at simulere hændelser ved hjælp af Broadcast,
og det er faktisk, når jeg modtager, ikke når jeg hører,
men det væsentlige er det en måde at overføre information
fra en sprite til en anden.
For eksempel kan du ønsker at sende game over,
og når en anden sprite modtager game over,
den reagerer på en bestemt måde.
Det er en vigtig model at forstå for programmering.
Bare for at gå over den grundlæggende uge 0, hvad vi har været igennem indtil nu,
lad os se på dette enkle C-program.
Teksten kan være en smule mindre herfra, men jeg vil gå over det virkelig hurtig.
Vi herunder 2 header-filer i toppen, cs50.h og stdio.h.
Vi derefter definere en konstant kaldet grænse til at være 100.
Vi derefter implementere vores vigtigste funktion.
Da vi ikke bruger kommandolinjeargumenter her vi skal lægge ugyldig
som argumenterne for main.
Vi ser int over main. Det er returtypen, og derfor returnere 0 i bunden.
Og vi bruger CS50 biblioteksfunktion få int
at bede brugeren om input, og vi gemme det i denne variabel x,
så vi erklærer x ovenfor, og vi initialisere den med x = GetInt.
>> Vi derefter kontrollere, om brugeren har givet os gode input.
Hvis det er ≥ LIMIT vi ønsker at returnere en fejlkode på 1 og udskrive en fejlmeddelelse.
Og endelig, hvis brugeren har givet os gode input
vi kommer til at kvadratur nummer og udskrive dette resultat.
Blot for at sørge for, at de alle hit hjem
du kan se etiketterne på de forskellige dele af koden her.
Jeg nævnte konstante, header filer.
Åh, int x. Sørg for at huske, at er en lokal variabel.
Det står i kontrast det fra en global variabel, som vi taler om
lidt senere i gennemgangen session,
og vi kræver biblioteksfunktionen printf,
så hvis vi ikke havde medtaget den stdio.h header fil
ville vi ikke være i stand til at ringe printf.
Og jeg tror, ​​den pil, der blev afbrudt her peger på% d,
der er en formatering streng i printf.
Det siger udskrive denne variabel som et tal,% d.
Og det er det for uge 0.
Nu Lucas vil fortsætte.
Hej med jer. Mit navn er Lucas.
Jeg er en sophomore i det bedste hus på campus, Mather,
og jeg har tænkt mig at snakke lidt om uge 1 og 2,1.
[Uge 1 og 2,1!] [Lucas Freitas]
Da Lexi sagde, da vi begyndte at oversætte din kode fra Scratch til C
en af ​​de ting, som vi har bemærket er, at du kan ikke bare
skrive din kode og køre det ved hjælp af et grønt flag længere.
Faktisk, er du nødt til at bruge nogle skridt til at gøre din C program
blive en eksekverbar fil.
Dybest set, hvad du gør, når du skriver et program, er, at
du oversætte din idé til et sprog, som en compiler kan forstå,
så når du skriver et program i C
hvad du gør, er rent faktisk at skrive noget, som din compiler vil forstå,
og derefter compiler vil oversætte denne kode
ind i noget, som din computer vil forstå.
>> Og de ting er, din computer er faktisk meget dum.
Computeren kan kun forstå 0'er og 1'ere,
så faktisk i de første computere folk normalt programmeret
hjælp 0'er og 1-taller, men ikke længere, gudskelov.
Vi behøver ikke at huske sekvenserne for 0'er og 1'ere
for en for-løkke eller i et stykke løkke og så videre.
Det er derfor, vi har en compiler.
Hvad en compiler gør, er det dybest set oversætter C-kode,
i vores tilfælde, at et sprog, som computeren vil forstå
som er genstand kode, og den compiler, som vi benytter
kaldes klang, så det er faktisk symbolet for klang.
Når du har dit program, du skal gøre 2 ting.
Først skal du nødt til at kompilere dit program, og så er du kommer til at køre dit program.
For at kompilere dit program du har en masse muligheder for at gøre det.
Den første er at gøre Klang program.c
i hvilket program er navnet på dit program.
I dette tilfælde kan du se de er bare at sige "Hey, kompilere mit program."
Du siger ikke "Jeg ønsker dette navn til mit program" eller noget.
>> Den anden mulighed er at give et navn til dit program.
Du kan sige klang-o, og derefter det navn, du vil have
den eksekverbare fil, der skal navngives som og derefter program.c.
Og du kan også gøre lave program, og se hvordan i de første 2 tilfælde
Jeg sætter. C, og i den tredje jeg har kun programmer?
Ja, du faktisk bør ikke lægge. C. når du bruger lave.
Ellers compileren faktisk kommer til at råbe på dig.
Og også, jeg ved ikke, hvis du fyre huske,
men mange gange har vi også brugt-lcs50 eller-lm.
Det kaldes sammenkædning.
Det bare fortæller compileren, at du vil bruge disse biblioteker lige der,
så hvis du ønsker at bruge cs50.h du faktisk nødt til at skrive
klang program.c-lcs50.
Hvis du ikke gør det, er det compileren ikke kommer til at kende
at du bruger disse funktioner i cs50.h.
Og når du vil køre dit program har du 2 muligheder.
Hvis du gjorde klang program.c du ikke give et navn til dit program.
Du er nødt til at køre det med. / A.out.
A.out er et standard navn, der klang giver dit program, hvis du ikke give den et navn.
Ellers du vil gøre. / Program hvis du gav et navn til dit program,
og også hvis du lavede program det navn, et program kommer til at få
allerede vil være programmeret samme navn som den C-filen.
Så vi talte om datatyper og data.
>> Dybest set datatyper er det samme som små bokse, de bruger
til at gemme værdier, så datatyperne er faktisk ligesom pokemons.
De kommer i alle størrelser og typer.
Jeg ved ikke, om denne analogi giver mening.
Datastørrelsen faktisk afhænger af maskinens arkitektur.
Alle de data størrelser, jeg har tænkt mig at vise her
faktisk til en 32-bit maskine, hvilket er tilfældet i vort apparat,
men hvis du rent faktisk er kodning din Mac eller Windows også
sandsynligvis du vil have en 64-bit maskine,
så husk, at de data, størrelser, jeg har tænkt mig at vise her
er for 32-bit maskine.
Den første, vi så, var en int,
som er temmelig ligetil.
Du bruger int til at gemme et heltal.
Vi så også karakter, char.
Hvis du ønsker at bruge et brev eller en lille symbol du sandsynligvis vil bruge en char.
En char har 1 byte, hvilket betyder, 8 bit, som Lexi sagde.
Dybest set har vi en ASCII tabel, der har 256
mulige kombinationer af 0'er og 1-taller,
og så når du skriver en char det kommer til at oversætte
det tegn, som inputs dig et nummer, som du har i ASCII-tabellen, ligesom Lexi sagde.
Vi har også svømmeren, som vi bruger til at gemme decimaltal.
Hvis du ønsker at vælge 3,14, for eksempel, er du nødt til at bruge en flyder
eller en dobbelt, der har mere præcision.
En flyder har 4 bytes.
En dobbelt har 8 bytes, så den eneste forskel er den præcision.
Vi har også en lang som anvendes til heltal,
og du kan se for en 32-bit maskine en int og en lang har samme størrelse,
så det ikke rigtig mening at bruge en længe i en 32-bit maskine.
>> Men hvis du bruger en Mac og 64-bit maskine, faktisk en lang har str. 8,
så det virkelig afhænger af arkitekturen.
For den 32-bit maskine giver det ikke mening at bruge en lang virkelig.
Og derefter en lang lang, på den anden side har 8 byte,
så det er meget godt, hvis du vil have en længere heltal.
Og endelig har vi streng, som faktisk er en char *,
der er en pointer til en char.
Det er meget nemt at tro, at størrelsen af ​​strengen vil være ligesom
det antal tegn, som du har der,
men faktisk char * selv
har størrelsen på en markør til en char, som er 4 bytes.
Størrelsen af ​​en char * er 4 bytes.
Det betyder ikke noget, hvis du har en lille ord eller et bogstav eller noget.
Det kommer til at være 4 byte.
Vi har også lært lidt om støbning,
så du kan se, hvis du har for eksempel et program, der siger
int x = 3 og derefter printf ("% d", x / 2)
tror du fyre ved, hvad det kommer til at udskrive på skærmen?
>> Nogen? >> [Studerende] 2.
1. >> 1, ja.
Når du gør 3/2 det kommer til at få 1,5,
men da vi bruger et heltal det kommer til at ignorere den decimal del,
og du kommer til at have 1.
Hvis du ikke ønsker at det skal ske, hvad du kan gøre, for eksempel,
er erklære en float y = x.
Så x, der plejede at være 3 nu vil være 3,000 i y.
Og så kan du udskrive y / 2.
Faktisk burde jeg have en 2. derovre.
Det kommer til at gøre 3.00/2.00,
og du kommer til at få 1,5.
Og vi har denne .2 f blot at bede om 2 decimaler enheder i decimal del.
Hvis du har .3 f det kommer til at have faktisk 1,500.
Hvis det er 2 går det at være 1,50.
Vi har også denne sag her.
Hvis du gør float x = 3,14 og derefter du printf x
du kommer til at få 3,14.
Og hvis du gør x = int af x,
hvilket betyder behandle x som en int, og du udskriver x nu
du bliver nødt til 3,00.
Giver det mening?
Fordi du først er behandling af x som et heltal, så du ignorerer decimalerne,
og derefter du udskriver x.
Og endelig kan du også gøre dette,
int x = 65, og så skal du erklære en char c = x,
og derefter, hvis du udskriver c du faktisk vil få
A, så dybest set, hvad du laver her
er oversætte heltal i karakter,
ligesom ASCII tabel gør.
Vi talte også om matematik operatører.
De fleste af dem er temmelig ligetil, så +, -, *, /,
og også talte vi om mod, som er resten af ​​en division af 2 numre.
Hvis du har 10% 3, for eksempel,
det betyder dividere 10 med 3, og hvad er resten?
Det kommer til at være 1, så det er faktisk meget nyttigt for en masse af programmerne.
For Vigenère og Cæsar Jeg er ret sikker på, at alle jer fyre brugt mod.
Om matematik operatører, være meget forsigtig, når man kombinerer * og /.
>> For eksempel, (3/2), hvis du gør * 2 hvad vil du få?
[Studerende] 2.
Ja, 2, fordi 3/2 vil være 1,5,
men da du laver operationer mellem 2 heltal
du faktisk bare at overveje 1,
og derefter 1 * 2 kommer til at være 2, så vær meget forsigtige
når du laver aritmetik med heltal, fordi
du kan få det 2 = 3, i dette tilfælde.
Og også være meget forsigtige med forrang.
Du skal normalt bruge parenteser for at være sikker på, at du ved, hvad du laver.
Nogle nyttige genveje, selvfølgelig, er en jeg + + eller i + = 1
eller ved hjælp af + =.
Det er det samme som at gøre i = i + 1.
Du kan også gøre i - eller i - = 1,
hvilket er det samme som i = i -1,
Noget du fyre bruger en masse i for-løkker, i det mindste.
Også for *, hvis du bruger * = og hvis du gør, for eksempel,
i * = 2 er det samme som at sige, i = i * 2,
og det samme for division.
Hvis du gør i / = 2 det er det samme som i = i / 2.
>> Nu om funktioner.
Du fyre lærte, at funktioner er en meget god strategi at spare kode
mens du programmerer, så hvis du ønsker at udføre den samme opgave
i kode igen og igen, sandsynligvis du ønsker at bruge en funktion
bare så du ikke behøver at kopiere og indsætte koden igen og igen.
Faktisk main er en funktion, og når jeg vise dig formatet for en funktion
du vil se, at det er temmelig indlysende.
Vi bruger også funktioner fra nogle biblioteker,
for eksempel printf, GetIn, som er fra CS50 bibliotek,
og andre funktioner som toupper.
Alle disse funktioner er faktisk gennemføres i andre biblioteker,
og når du lægger dem tether filer i starten af ​​dit program
du siger kan du give mig koden til disse funktioner
så jeg ikke behøver at gennemføre dem selv?
Og du kan også skrive dine egne funktioner, så når du starter programmering
du indse, at bibliotekerne ikke har alle de funktioner, du har brug for.
For sidste Pset, for eksempel skrev vi tegne, scramble, og opslag,
og det er meget, meget vigtigt at være i stand til at skrive funktioner
fordi de er nyttige, og vi bruger dem hele tiden i programmeringen,
og det sparer en masse kode.
Formatet for en funktion er denne ene.
Vi har returtype i begyndelsen. Hvad er afkastet type?
Det er bare når din funktion kommer til at vende tilbage.
Hvis du har en funktion, for eksempel fakultet,
, der vil beregne en faktor af et helt tal,
sandsynligvis det kommer til at returnere et heltal også.
Derefter returtypen bliver int.
Printf faktisk har en returtype void
fordi du ikke vender tilbage noget.
Du er bare udskriver ting til skærmen
og afslutning af funktionen bagefter.
Så har du navnet på den funktion, som du kan vælge.
Du skal være lidt fornuftig, ligesom ikke vælger et navn som xyz
eller lignende x2f.
Prøv at gøre op et navn, der giver mening.
>> For eksempel, hvis det er factorial sige factorial.
Hvis det er en funktion, der vil trække noget, name it tegne.
Og så har vi de parametre, der også kaldes argumenter,
der er ligesom de ressourcer, din funktion skal
fra din kode til at udføre sin opgave.
Hvis du ønsker at beregne fakultet af et tal
sandsynligvis du nødt til at have et nummer til at beregne en faktorielt.
Et af de argumenter, som du kommer til at have, er selve nummeret.
Og så det kommer til at gøre noget og returnere værdien ved udgangen
medmindre det er en void funktion.
Lad os se et eksempel.
Hvis jeg ønsker at skrive en funktion, der adderer alle tallene i et array af heltal,
Først og fremmest er returtypen vil være int
fordi jeg har et array af heltal.
Og så jeg har tænkt mig at have den funktion navn som sumArray,
og så det kommer til at tage array selv, int nums,
og derefter længden af ​​array, så jeg ved, hvor mange tal, jeg er nødt til at opsummere.
Så jeg er nødt til at initialisere en variabel kaldet sum, for eksempel til 0,
og hver gang jeg ser et element i arrayet jeg skulle tilføje det til sum, så jeg gjorde en for-løkke.
Ligesom Lexi sagde, du gør int i = 0, i <længde og i + +.
Og for hvert element i arrayet jeg gjorde sum + = nums [i],
og så vendte jeg tilbage til sum, så det er meget simpelt, og det sparer en masse kode
hvis du bruger denne funktion en masse gange.
Så vi tog et kig på betingelser.
Vi har, hvis ellers, og ellers hvis.
Lad os se hvad er forskellen mellem dem.
Tag et kig på disse 2 koder. Hvad er forskellen mellem dem?
Den første har grundlæggende for de koder, vil have dig til at fortælle
om et tal er +, -, eller 0.
Den første siger, at hvis det er> 0 så er det positivt.
Hvis det er = til 0 så er det 0, og hvis det er <0 så er det negativt.
>> Og den anden gør, hvis ellers hvis, ellers.
Forskellen mellem de to er, at dette rent faktisk vil
kontrollere, om> 0, <0 eller = 0 tre gange,
så hvis du har tallet 2, for eksempel, går det at komme her og sige
if (x> 0), og det kommer til at sige ja, så jeg udskriver positive.
Men selv om jeg ved, at det er> 0 og det kommer ikke til at være 0 eller <0
Jeg vil stadig gøre, er det 0, er det <0,
så jeg faktisk går inde i hvis'er, at jeg ikke behøver at
fordi jeg allerede ved, at det ikke kommer til at tilfredsstille nogen af ​​disse betingelser.
Jeg kan bruge den, hvis ellers hvis ellers erklæring.
Det dybest set siger, at hvis x = 0 Jeg udskriver det positive.
Hvis det ikke er, vil jeg også teste dette.
Hvis det er 2 ikke jeg har tænkt mig at gøre dette.
Dybest set, hvis jeg havde x = 2 ville du sige
if (x> 0), ja, så udskrive dette.
Nu, hvor jeg ved, at det er> 0 og at det opfyldte det første, hvis
Jeg er ikke engang kommer til at køre denne kode.
Koden kører hurtigere, faktisk, 3 gange hurtigere, hvis du bruger denne.
Vi har også lært om og og eller.
Jeg har ikke tænkt mig at gå igennem dette, fordi Lexi allerede talt om dem.
Det er bare de && og | | operatør.
>> Det eneste, jeg vil sige, er at være forsigtig, når du har 3 betingelser.
Brug parenteser, fordi det er meget forvirrende, når du har en tilstand
og en anden eller andet.
Brug parenteser bare for at være sikker på, at dine betingelser giver mening
for i så fald, for eksempel, kan man forestille sig, at
det kunne være den første tilstand og den ene eller den anden
eller de 2 forhold kombineret i et og
eller den tredje, så bare være forsigtig.
Og endelig har vi talt om switche.
En switch er meget nyttigt, når du har en variabel.
Lad os sige, at du har en variabel som n
der kan være 0, 1, eller 2, og hvert af disse tilfælde
du kommer til at udføre en opgave.
Man kan sige skifte variabel, og det tyder på, at
værdien så er ligesom værdi1 jeg har tænkt mig at gøre dette,
og så vil jeg gå i stykker, hvilket betyder, at jeg har ikke tænkt mig at se på nogen af ​​de andre sager
fordi vi allerede overbevist om, at sagen
og derefter værdi2 og så videre, og jeg kan også have en standard switch.
Det betyder, hvis den ikke opfylder nogen af ​​de sager, jeg har haft
at jeg har tænkt mig at gøre noget andet, men det er valgfrit.
Det er alt for mig. Lad os nu få Tommy.
Okay, dette vil være Uge 3-ish.
Disse er nogle af de emner vi vil være der dækker, krypto, anvendelsesområde, arrays, et cetera.
Bare en hurtig bemærkning om krypto. Vi kommer ikke til at hamre dette hjem.
>> Vi gjorde det i Pset 2, men for quizzen skal du kende forskel
mellem Cæsar cipher og Vigenère cipher,
hvordan begge disse ciphers arbejde, og hvad det vil sige at kryptere
og dekryptere tekst ved hjælp af disse 2 ciphers.
Husk, at Cæsar cipher simpelthen roterer hvert tegn med samme beløb,
og sørg for du mod på antallet af bogstaver i alfabetet.
Og Vigenère cipher, på den anden side, roterer hvert tegn
med et andet beløb, end så hellere sige
Hver karakter drejes af 3 Vigenère vil rotere hvert tegn
med et andet beløb afhængig af nogle søgeord
hvor hvert bogstav i søgeordet repræsenterer nogle forskellige beløb
at rotere den klare tekst.
Lad os først tale om variabel rækkevidde.
Der findes 2 forskellige typer af variabler.
Vi har lokale variable, og de vil blive defineret
uden for hoved-eller uden for enhver funktion eller blok,
og disse vil være tilgængelige overalt i dit program.
Hvis du har en funktion, og i denne funktion er en while-løkke
den store globale variabel er tilgængelig overalt.
En lokal variabel på den anden side er virkefelt til det sted, hvor det er defineret.
>> Hvis du har en funktion her, for eksempel, har vi denne funktion g,
og inde i g er der en variabel her benævnt y,
og det betyder, at dette er en lokal variabel.
Selvom denne variabel kaldes y
og denne variabel kaldes y disse 2 funktioner
har ingen idé om, hvad hinandens lokale variabler er.
På den anden side har vi heroppe siger int x = 5,
og det er uden for enhver funktion.
Det er uden for main, så dette er en global variabel.
Det betyder, at indersiden af ​​disse 2 funktioner, når jeg siger x - eller x + +
Jeg adgang til samme x, hvorved denne y og dette y er forskellige variable.
Det er forskellen mellem en global variabel og en lokal variabel.
For så vidt angår design angår, nogle gange er det nok en bedre idé
at holde variabler lokal, når du overhovedet kan
da have en masse globale variabler kan få virkelig forvirrende.
Hvis du har en masse funktioner, alt modificere det samme
du måske glemmer, hvad hvis denne funktion ved et uheld ændrer denne globale,
og denne anden funktion ikke vide om det,
og det får temmelig forvirrende, da du får mere kode.
Holde variabler lokal, når du overhovedet kan
er bare godt design.
Arrays, husk på, er simpelthen lister over elementer af samme type.
Inde i CI kan ikke have en liste som 1, 2,0, hej.
Vi kan bare ikke gøre det.
>> Når vi erklærer en datatabel i C alle de elementer være af samme type.
Her har jeg en vifte af 3 heltal.
Her har jeg længden af ​​array, men hvis jeg bare erklære den i denne syntaks
hvor jeg specificere, hvad alle de elementer er jeg ikke teknisk brug for denne 3.
Compileren er smart nok til at regne ud hvor stor array skal være.
Nu når jeg ønsker at hente eller angive værdien af ​​et array
dette er den syntaks at gøre det.
Det vil faktisk ændre det andet element i array, fordi huske,
Nummereringen starter ved 0, ikke ved 1.
Hvis jeg ønsker at læse denne værdi jeg kan sige noget lignende int x = array [1].
Eller hvis jeg ønsker at indstille denne værdi, ligesom jeg gør her,
Jeg kan sige array [1] = 4.
Den tid adgang til elementer ved deres indeks
eller deres position eller når de er i sættet,
og denne registrering starter ved 0.
Vi kan også have arrays af arrays,
og dette kaldes en multi-dimensional array.
Når vi har en multi-dimensional matrix
det betyder, at vi kan få noget lignende rækker og kolonner,
og dette er blot én måde at visualisere denne eller tænker over det.
Når jeg har en multi-dimensional array, der betyder, at jeg har tænkt mig at begynde at brug
mere end 1 indeks, fordi hvis jeg har et gitter
bare sige, hvad rækken du er i ikke giver os et tal.
Det er virkelig bare vil give os en liste over numre.
Lad os sige, at jeg har dette array her.
Jeg har et array kaldet gitter, og jeg siger det er 2 rækker og 3 kolonner,
og så dette er en måde at visualisere det.
Når jeg siger jeg ønsker at få elementet på [1] [2]
det betyder, at fordi disse er rækkerne først og derefter kolonner
Jeg har tænkt mig at springe til række 1, da jeg sagde 1.
>> Så jeg har tænkt mig at komme herover til kolonne 2, og jeg har tænkt mig at få værdien 6.
Give mening?
Multi-dimensionelle arrays, husk, er teknisk set bare en vifte af arrays.
Vi kan have arrays af rækker af arrays.
Vi kan holde ud, men virkelig en måde at tænke på
hvordan dette bliver lagt ud, og hvad der sker, er at visualisere det
i et gitter som denne.
Når vi passerer arrays til funktioner, kommer de til at opføre sig
en lille smule anderledes, end når vi passerer regelmæssigt variabler til funktioner
ligesom passerer en int eller en float.
Når vi passerer i en int eller char eller nogen af ​​de andre datatyper
vi tog bare et kig på, hvis funktionen ændrer
værdien af ​​denne variabel, at forandring ikke kommer til at udbrede op
til den kaldende funktion.
Med et array, på den anden side vil der ske.
Hvis jeg passere i et array til en funktion, og denne funktion ændrer nogle af de elementer,
når jeg kommer tilbage til den funktion, som kaldte det
mit array vil nu være anderledes, og det ordforråd for at
er arrays sendes som reference, som vi vil se senere.
Dette hænger sammen med, hvordan pointers arbejde, hvor disse grundlæggende datatyper
På den anden side, gik der som værdi.
>> Vi kan tænke på det som at tage en kopi af nogle variable og derefter passerer i kopien.
Det er ligegyldigt, hvad vi gør med denne variabel.
Den kaldende funktion vil ikke være klar over, at det blev ændret.
Arrays er bare en lille smule anderledes i denne henseende.
For eksempel, som vi netop har set vigtigste er simpelthen en funktion
der kan tage i 2 argumenter.
Det første argument til den vigtigste funktion er argc, eller antallet af argumenter,
og det andet argument kaldes argv,
og det er de faktiske værdier af disse argumenter.
Lad os sige, at jeg har et program kaldet this.c,
og jeg siger at gøre dette, og jeg har tænkt mig at køre dette på kommandolinjen.
Nu til at passere i nogle argumenter til mit program kaldet dette,
Jeg kunne sige noget lignende. / Dette er cs 50.
Det er, hvad vi forestille David til at gøre hver dag på terminalen.
Men nu er den vigtigste funktion inde i dette program
har disse værdier, så argc er 4.
Det kan være lidt forvirrende, fordi vi virkelig er kun passerer i, er cs 50.
Det er kun 3.
Men husk, at den første del af argv eller det første argument
er navnet på selve funktionen.
Så det betyder, at vi har 4 ting her,
og det første element vil være. / dette.
Og det vil være repræsenteret som en streng.
Så de resterende elementer er, hvad vi skrev i efter navnet på programmet.
Så lige som en sidebemærkning, da vi sandsynligvis oplevede i Pset 2,
Husk, at strengen 50 er ≠ heltallet 50.
Så vi kan ikke sige noget lignende, "int x = argv 3. '
>> Det er bare ikke kommer til at give mening, fordi dette er en streng, og dette er et heltal.
Så hvis du ønsker at konvertere mellem de 2, husk, vi kommer til at
har denne magiske funktion kaldet atoi.
Det tager en streng og returnerer heltal repræsenteret indersiden af ​​denne streng.
Så det er en nem fejl at gøre på quizzen,
bare tænker, at dette automatisk vil være den korrekte type.
Men bare vide, at de altid vil være strenge
selv om strengen kun indeholder et heltal eller et tegn eller en flyder.
Så lad os nu tale om køretid.
Når vi har alle disse algoritmer, der gør alle disse skøre ting,
bliver det virkelig nyttigt at stille spørgsmålet: "Hvor længe skal de tage?"
Vi erklærer herved, med noget, der hedder asymptotisk notation.
Så det betyder, at - ja, lad os sige, at vi giver vores algoritme
nogle virkelig, virkelig, virkelig store indgang.
Vi ønsker at stille spørgsmålet: "Hvor længe kommer det til at tage?
Hvor mange skridt vil det tage vores algoritme til at køre
som en funktion af størrelsen af ​​input? "
Så den første måde vi kan beskrive køre tid er med stor O.
Og det er vores worst-case køretid.
Så hvis vi ønsker at sortere et array, og vi giver vores algoritme et array
det er i faldende rækkefølge, når det skal være i stigende orden,
der kommer til at være det værst tænkelige.
Dette er vores øvre grænse på den maksimale længde af tid vores algoritme vil tage.
På den anden side er denne Ω vil beskrive best case driftstid.
Så hvis vi giver en allerede sorteret array til en sortering algoritme,
hvor lang tid vil det tage at sortere det?
Og dette, så beskriver en nedre grænse på køretid.
Så her er blot nogle ord, der beskriver nogle fælles køretider.
Disse er i stigende rækkefølge.
Den hurtigste køretid vi har kaldes konstant.
>> Det betyder, uanset hvor mange elementer, vi giver vores algoritme,
uanset hvor stor vores array er, sortering det
eller gør, hvad vi gør til array vil altid tage den samme mængde tid.
Så vi kan repræsentere, at blot med en 1, som er en konstant.
Vi så også på logaritmisk driftstid.
Så noget lignende binær søgning er logaritmisk,
hvor vi skære problem i halvdelen hver gang
og så tingene bare komme højere derfra.
Og hvis du nogensinde skriver en O i nogen faktoriel algoritme,
du skulle vel ikke betragte dette som din dag job.
Når vi sammenligner kører gange er det vigtigt at huske på disse ting.
Så hvis jeg har en algoritme, der er O (n), og en anden
har en algoritme af O (2n) disse faktisk er asymptotisk ækvivalente.
Så hvis vi forestiller os n være et stort antal lignende eleventy mia:
så når vi sammenligner eleventy milliarder til noget som eleventy mia + 3,
pludselig, at tre ikke rigtig gøre en stor forskel længere.
Det er derfor, vi vil begynde at overveje disse ting at være ækvivalente.
Så ting som disse konstanter her, er der 2 x denne, eller tilføje en 3,
det er blot konstanter, og disse vil falde op.
Så det er derfor alle 3 af disse køre tider er det samme som at sige, at de er O (n).
Tilsvarende, hvis vi har 2 andre kørselstider, lad os sige O (n ³ + 2n ²), kan vi tilføje
+ N, + 7, og så har vi en anden driftstid, der er lige O (n ³).
Igen er dette det samme fordi disse - disse er ikke de samme.
Det er de samme ting, undskyld. Så disse er de samme, fordi
Dette n ³ vil dominere dette 2n ².
>> Hvad er ikke det samme ting er, hvis vi har kørt tider som O (n ³) og O (n ²)
fordi denne n ³ er meget større end dette n ².
Så hvis vi har eksponenter, pludseligt dette begynder at betyde noget,
men når vi er bare beskæftiger sig med faktorer, som vi er heroppe,
så det kommer ikke til at noget, fordi de bare kommer til at falde ud.
Lad os tage et kig på nogle af de algoritmer, vi har set hidtil
og tale om deres køretid.
Den første måde at se efter et nummer i en liste, som vi så, var lineær søgning.
Og gennemførelsen af ​​lineær søgning er super ligetil.
Vi har bare en liste, og vi vil se på hver enkelt element i listen
indtil vi finder det nummer, vi leder efter.
Så det vil sige, at i værste tilfælde er dette O (n).
Og værste fald her kunne være, hvis elementet er
det sidste element, og derefter ved lineær søgning, vi er nødt til at se på hvert enkelt element
indtil vi kommer til den sidste, for at vide, at det var faktisk på listen.
Vi kan ikke bare give op halvvejs og sige: "Det er nok ikke der."
Med lineær søgning, vi er nødt til at se på det hele.
The best case efterløbstid på den anden side er konstant
fordi der i bedste fald det element, vi leder efter, er blot den første i listen.
Så det kommer til at tage os præcis 1 trin, uanset hvor stor listen er
hvis vi leder efter det første element hver gang.
>> Så når du søger, husk, kræver det ikke, at vores liste være sorteret.
Fordi vi simpelthen kommer til at se ud over hvert enkelt element, og det er faktisk ligegyldigt
hvilken rækkefølge disse elementer er i.
En mere intelligent søgealgoritme er noget binær søgning.
Husk, at gennemførelsen af ​​binær søgning er, når du kommer til at
holde ser på midten af ​​listen.
Og fordi vi kigger på midten, kræver vi, at listen er sorteret
eller andet, som vi ikke ved, hvor midten er, og vi er nødt til at kigge over
hele listen for at finde den, og derefter på det tidspunkt vi bare spilder tiden.
Så hvis vi har en sorteret liste, og vi finder i midten, vil vi sammenligne den midterste
til elementet, vi leder efter.
Hvis det er for højt, så kan vi glemme den højre halvdel
fordi vi ved, at hvis vores element er allerede for høj
og alt til højre for dette element er endnu højere,
så vi behøver ikke at kigge der længere.
Hvor på den anden side, hvis vores element er for lav,
vi kender alt til venstre for denne bestanddel er også for lavt,
så det ikke rigtig mening at kigge der, enten.
Denne måde, med hvert skridt og hver gang vi ser på midten af ​​listen,
vi kommer til at skære vores problem i halvdelen, fordi vi pludselig kender
en hel masse tal, der ikke kan være den, vi leder efter.
>> I pseudokode dette ville se noget som dette,
og fordi vi skærer listen i halvdelen hver eneste gang,
vores worst-case køretid springer fra lineær til logaritmisk.
Så pludselig har vi log-in skridt for at finde et element på en liste.
Den bedste case kørende tid, er dog stadig konstant
fordi nu, lad os bare sige, at det element, vi leder efter, er
altid nøjagtigt midt i den oprindelige liste.
Så vi kan dyrke vores liste så stor som vi ønsker, men hvis element, vi leder efter, er på midten,
så er det kun kommer til at tage os 1 trin.
Så det er derfor vi er O (log n) og Ω (1) eller konstant.
Lad os faktisk køre binær søgning på denne liste.
Så lad os sige, at vi leder efter elementet 164.
Den første ting, vi skal gøre, er at finde midtpunktet af denne liste.
Det er bare sådan, at midtpunktet kommer til at falde i mellem disse 2 numre,
så lad os bare vilkårligt sige, hver gang midtpunktet falder mellem 2 numre,
lad os bare runde op.
Vi skal bare sikre, at vi gør dette hvert skridt på vejen.
Så vi kommer til at runde op, og vi vil sige, at 161 er midt i vores liste.
Så 161 <164, og hvert element til venstre for 161
er også <164, så vi ved, at det ikke kommer til at hjælpe os på alle
at begynde at kigge herover, fordi elementet, vi leder efter kan ikke være der.
Så hvad vi kan gøre, er at vi kan bare glemme alt om det hele venstre halvdel af listen,
og nu kun tage stilling til fra højre side af 161 og fremefter.
>> Så igen, det er midtpunktet, lad os bare runde op.
Nu 175 er for stor.
Så vi ved, det kommer ikke til at hjælpe os med at kigge her eller her,
så vi kan bare smide det væk, og til sidst vil vi ramt 164.
Eventuelle spørgsmål om binær søgning?
Lad os komme videre fra at søge gennem en allerede sorteret liste
til rent faktisk at tage en liste over numre i vilkårlig rækkefølge
og gøre denne liste i stigende orden.
Den første algoritme vi kiggede på blev kaldt boble slags.
Og det ville være nemmere for de algoritmer vi så.
Bubble slags siger, at når nogen 2 elementer inde listen er ud af sted,
betyder at der er et højere antal til venstre for et lavere antal,
så vi kommer til at bytte dem, fordi det betyder, at listen vil blive
"Mere sorteres" end det var før.
Og vi vil bare fortsætte denne proces igen og igen og igen
indtil sidst elementerne slags boble til deres korrekte placering, og vi har en sorteret liste.
>> Den kører tidspunktet for denne bliver O (n ²). Hvorfor?
Jo, fordi i værste fald, vi kommer til at tage ethvert element, og
vi kommer til at ende med at sammenligne den med alle andre elementer i listen.
Men i bedste fald har vi en allerede sorteret liste, boble sortere s
bare kommer til at gå igennem en gang, siger "Nope. jeg ikke gøre nogen swaps, så jeg er færdig."
Så vi har en bedste-case køretid for Ω (n).
Lad os køre boble sortere på en liste.
Eller først, lad os bare se på nogle pseudokode virkelig hurtigt.
Vi ønsker at sige, at vi ønsker at holde styr på, i hver iteration af løkken,
holde styr på, hvorvidt vi skiftede nogen elementer.
Så grunden til det er, vi kommer til at stoppe, når vi ikke har byttet nogen elementer.
Så i starten af ​​vores løkke har vi ikke byttet noget, så vi vil sige, det er falsk.
Nu er vi kommer til at gå gennem listen og sammenligne element i til element i + 1
og hvis det er tilfældet, at der er et større tal til venstre for et mindre antal,
så er vi bare kommer til at bytte dem.
>> Og så vil vi huske, at vi byttes et element.
Det betyder, at vi er nødt til at gå gennem listen mindst 1 gang
fordi den tilstand, hvor vi stoppede er, når hele listen er allerede sorteret,
hvilket betyder at vi ikke har foretaget swaps.
Så det er derfor vores tilstand hernede er "idet nogle dele er blevet byttet."
Så lad os nu bare se på dette kører på en liste.
Jeg har listen 5,0,1,6,4.
Bubble sort kommer til at starte helt til venstre, og det kommer til at sammenligne
de i-elementer, så 0 til i + 1, som er element 1.
Det kommer til at sige, godt 5> 0, men lige nu 5 er til venstre,
så jeg er nødt til at bytte om på 5 og 0.
Når jeg bytte dem, pludselig får jeg denne anden liste.
Nu 5> 1, så vil vi bytte dem.
5 er ikke> 6, så vi behøver ikke at gøre noget her.
Men 6> 4, så vi er nødt til at bytte.
Igen, vi er nødt til at løbe igennem hele listen til sidst opdage
at disse er ude af drift, vi bytte dem,
og på dette punkt er vi nødt til at køre gennem listen 1 gang
for at sikre, at alt er i sin kendelse, og på dette punkt boble slags er færdig.
En anden algoritme til at tage nogle elementer og sortering er selection art.
Ideen bag udvælgelsen art er, at vi kommer til at opbygge en sorteret del af listen
1 element ad gangen.
>> Og den måde, vi kommer til at gøre det på er ved at opbygge den venstre del af listen.
Og dybest set, hver - på hvert trin, vi kommer til at tage det mindste element vi har tilbage
som ikke er blevet sorteret endnu, og vi vil flytte den ind i den sorterede segment.
Det betyder, at vi er nødt til hele tiden at finde den mindste usorteret element
og derefter tage det mindste element og bytte den med det
venstre-mest element, der ikke er sorteret.
Den kører tidspunktet for denne bliver O (n ²), fordi i værste fald
Vi er nødt til at sammenligne hver enkelt element til hvert andet element.
Fordi vi siger, at hvis vi starter på venstre halvdel af listen, har vi brug
at gå gennem hele højre segment for at finde det mindste element.
Og så igen, vi er nødt til at gå over hele højre segment og
holde gå over det igen og igen og igen.
Det kommer til at være n ². Vi skal bruge en for-løkke inde i en anden for-løkke
hvilket tyder n ².
I bedste fald tanken, lad os sige, at vi giver det en allerede sorteret liste;
vi faktisk ikke gøre det bedre end n ².
Fordi udvælgelse sort har ingen mulighed for at vide, at
det mindste element er bare den, jeg tilfældigvis er på udkig på.
Det er stadig nødt til at sørge for, at dette faktisk er et minimum.
>> Og den eneste måde at sikre, at det er den mindste, ved hjælp af denne algoritme,
er at se på hver enkelt element igen.
Så virkelig, hvis du giver det - hvis du giver valg Arranger en allerede sorteret liste,
det kommer ikke til at gøre noget bedre end at give det en liste, der ikke er sorteret endnu.
Af den måde, at hvis det sker for at være tilfældet noget er O (noget)
og omega for noget, kan vi bare sige mere kortfattet, at det er θ af noget.
Så hvis du kan se, at komme op hvor som helst, det er hvad det betyder bare.
>> Hvis noget er theta n ², er det både store O (n ²) og Ω (n ²).
Så bedst tilfælde og værste tilfælde betyder det ikke gøre en forskel,
algoritmen vil gøre det samme hver gang.
Så dette er hvad pseudokoden for udvælgelse slags kan se ud.
Vi dybest set kommer til at sige, at jeg ønsker at gentage over listen
fra venstre mod højre, og ved hver iteration af løkken, vil jeg flytte
den mindste element i denne sorterede del af listen.
Og når jeg flytter noget der, jeg aldrig skal se på dette element igen.
Fordi så snart jeg bytte et element i den venstre del af listen, er det sorteres
fordi vi gør alt i stigende rækkefølge ved hjælp af mindstesatser.
Så vi sagde, okay, vi er i position i, og vi er nødt til at se på alle de elementer,
til højre for i for at finde den minimale.
Så det betyder, at vi ønsker at se fra i + 1 til slutningen af ​​listen.
Og nu, hvis det element, vi i øjeblikket kigger på, er mindre end vores minimum hidtil,
der, husk, vi starter minimum ud til bare være
uanset element vi i øjeblikket på, jeg vil antage, at er det mindste.
Hvis jeg finder et element, der er mindre end det, så jeg har tænkt mig at sige, okay,
godt, jeg har fundet en ny minimum.
Jeg har tænkt mig at huske, hvor det minimum var.
>> Så nu, når jeg har været igennem denne ret usorteret segment,
Jeg kan sige, jeg har tænkt mig at skifte den mindste element med det element, der er i position i.
Det kommer til at opbygge min liste, min sorteret del af listen fra venstre mod højre,
og vi ikke nogensinde nødt til at se på et element igen, når det er i denne del.
Når vi har byttet det.
Så lad os køre udvælgelse slags på denne liste.
Den blå element her vil være i, og den røde element vil være den mindste element.
Så jeg starter helt i venstre side af listen, så på 5.
Nu skal vi finde den mindste usorteret element.
Så vi siger 0 <5, så 0 er min nye minimum.
>> Men jeg kan ikke stoppe der, for selv om vi kan genkende, at 0 er den mindste,
vi er nødt til at køre gennem hver andet element på listen for at sikre.
Så 1 er større, 6 er større, 4 er større.
Det betyder, at når man ser på alle disse elementer, har jeg bestemt 0 er den mindste.
Så jeg har tænkt mig at bytte den 5 og 0.
Når jeg bytte det, jeg kommer til at få en ny liste, og jeg ved, at jeg aldrig skal se på, at 0 igen
fordi når jeg har byttet det, jeg har sorteret det, og vi er færdige.
Nu er det bare sådan, at den blå element er igen 5,
og vi er nødt til at se på 1, 6 og 4 for at fastslå, at 1
er den mindste minimum element, så vi vil bytte 1 og 5.
Igen, vi er nødt til at se på - sammenligne 5 til 6 og 4,
og vi vil bytte 4 og 5, og endelig sammenligne
disse 2 numre og bytte dem, indtil vi får vores sorteret liste.
Eventuelle spørgsmål om udvælgelse slags?
Okay. Lad os gå til den sidste emne her, og det er rekursion.
>> Rekursion, husk, er det virkelig meta ting, hvor en funktion
gentagne gange kalder sig.
Så på et tidspunkt, mens vores fuction gentagne gange kalder sig selv
skal der være et tidspunkt, hvor vi stoppe med at kalde os selv.
For hvis vi ikke gør det, så er vi bare vil fortsætte med at gøre dette for evigt,
og vores program er bare ikke kommer til at afslutte.
Vi kalder denne tilstand basisscenariet.
Og base case siger, snarere end at kalde en funktion igen,
Jeg skal bare til at returnere en vis værdi.
Så når vi har returneret en værdi, har vi standset kalde os selv,
og resten af ​​de opkald, vi har lavet indtil videre kan også vende tilbage.
Det modsatte af den oprindelige sag er den rekursive tilfældet.
Og det er, når vi ønsker at foretage et andet opkald til den funktion, at vi er i øjeblikket i.
Og vi sandsynligvis, men ikke altid, ønsker at bruge forskellige argumenter.
>> Så hvis vi har en funktion kaldet f, og f har lige ringet tager 1 argument,
og vi bare holde kalde f (1), f (1), f (1), og det bare så sker det, at
argumentet 1 falder i rekursive tilfælde, er vi stadig aldrig vil stoppe.
Selvom vi har en base sag, skal vi sørge for at i sidste ende vil vi ramme den basisscenariet.
Vi har ikke bare holde opholder sig i denne rekursive tilfælde.
Generelt, når vi kalder os selv, er vi nok nødt til en anden argumentation hver gang.
Her er en virkelig enkel rekursiv funktion.
Så dette vil beregne fakultet af et tal.
Op øverst her vi har vores base case.
I tilfælde af at n ≤ 1, vi vil ikke kalde fakultet igen.
Vi kommer til at stoppe, vi bare vil vende tilbage en vis værdi.
Hvis dette ikke er sandt, så er vi kommer til at ramme vores rekursiv sag.
Bemærk her, at vi ikke bare kalde factorial (n), fordi det ikke ville være meget nyttigt.
Vi vil kalde fakultet af noget andet.
>> Og så du kan se, i sidste ende, hvis vi passerer en fakultetværdi (5) eller noget,
vi vil kalde factorial (4) og så videre, og til sidst vil vi ramme denne basisscenariet.
Så det ser godt ud. Lad os se hvad der sker, når vi rent faktisk køre dette.
Dette er stakken, og lad os sige, at main vil kalde denne funktion med et argument (4).
Så en gang faktoriel ser og = 4, vil fakultet kalde sig selv.
Nu, pludselig har vi fakultet (3).
Så disse funktioner vil holde vokse, indtil sidst vi ramt vores base case.
På dette tidspunkt er returværdien af ​​dette afkast (nx returværdien af ​​dette),
returværdien af ​​dette er nx returværdien af ​​dette.
Til sidst skal vi ramt nogle tal.
Øverst her siger vi tilbage 1.
Det betyder, at når vi vender tilbage, at tal, kan vi pop dette fra stakken.
Så denne factorial (1) udføres.
Når 1 vender tilbage, denne faktorielle (1) afkast, denne tilbagevenden til 1.
Returværdien af ​​dette, husk, var nx returværdien af ​​dette.
Så pludselig, denne fyr ved, at jeg vil vende tilbage 2.
>> Så husk, returnere værdien af ​​dette er bare NX returværdien heroppe.
Så nu kan vi sige 3 x 2, og til sidst, her kan vi sige
dette er bare at være 4 x 3 x 2.
Og når denne vender tilbage, vi får ned til et enkelt heltal inde i main.
Eventuelle spørgsmål om rekursion?
Ok. Så der er mere tid til spørgsmål til sidst,
men nu Joseph vil dække de resterende emner.
>> [Joseph Ong] Okay. Så nu, at vi har talt om rekursioner,
lad os snakke lidt om hvad fusionere slags er.
Flet slags er dybest set en anden måde at sortere en liste over numre.
Og hvordan det virker er, med fletningen slags du har en liste, og hvad vi gør, er
vi siger, lad os splitte dette i 2 halvdele.
Vi vil først løbe fusionere slags igen på den venstre halvdel,
så vil vi køre fusionere art på den højre halvdel,
og det giver os nu 2 halvdele, der er sorteret, og nu vil vi kombinere disse halvdele sammen.
Det er lidt svært at se uden et eksempel, så vi vil gå gennem beslutningsforslag, og se hvad der sker.
Så du starte med denne liste, split vi det i 2 halvdele.
Vi kører fusionere sortere på den venstre halvdel først.
Så det er den venstre halvdel, og nu skal vi køre dem gennem denne liste igen
der bliver gået ind i fletningen slags, og så ser vi, igen,
på venstre side af denne liste, og vi kører fusionere slags på det.
Nu får vi ned til en liste med 2 numre,
og nu den venstre halvdel er kun 1 element lang, og vi kan ikke
opdele en liste, der er kun 1 element i halve, så siger vi bare, når vi har 50,
der er kun 1 element, er det allerede sorteret.
>> Når vi er færdig med det, kan vi se, at vi kan
gå videre til den højre halvdel af denne liste,
og 3 er også sorteres, og så nu, at begge halvdele af denne liste er sorteret
vi kan slutte disse tal sammen igen.
Så ser vi på 50 og 3, 3 er mindre end 50, så det går i først og derefter 50 kommer ind
Nu er der gjort, vi gå tilbage op til denne liste og sortere det er højre halvdel.
42 er det eget nummer, så det er allerede sorteret.
Så nu er vi sammenligne disse 2 og 3 er mindre end 42, så der bliver sat ind først,
nu 42 bliver sat i, og 50 bliver sat i.
Nu, det er sorteret, vi går hele vejen tilbage til toppen, 1337 og 15.
Nå, vi nu ser på den venstre halvdel af denne liste, 1337 er i sig selv så det er sorteret og samme med 15.
Så nu er vi kombinerer disse 2 numre for at sortere den oprindelige liste, 15 <1337,
så det går i først, så 1337 går i.
Og nu vi sorteret begge halvdele af den oprindelige liste op øverst.
Og alt, hvad vi skal gøre, er at kombinere disse.
Vi ser på de første 2 numre af denne liste, 3 <15, så det går i den slags arrayet først.
15 <42, så det går ind nu, 42 <1337, der går ind
50 <1337, så det går i. Og bemærke, at vi tog bare 2 numre ud af denne liste.
Så vi er ikke bare skiftevis mellem de 2 lister.
Vi leder bare efter i starten, og vi tager elementet
der er mindre og derefter sætte det ind i vores array.
Nu har vi samlet alle de halvdele og vi er færdige.
>> Eventuelle spørgsmål om fusionere slags? Ja?
[Student] Hvis det er opsplitning i forskellige grupper, hvorfor de ikke bare dele det engang
og du har 3 og 2 i en gruppe? [Resten af ​​spørgsmål uforståelig]
Årsagen - så spørgsmålet er, hvorfor kan vi ikke bare flette dem på det første skridt efter at vi har dem?
Grunden til at vi kan gøre dette, skal du starte på venstre de fleste elementer på begge sider,
og derefter tage den mindste og sætte det i, er, at vi ved, at disse
enkelte lister er i sorteret ordrer.
Så hvis jeg ser på venstre de fleste elementer af begge halvdele,
Jeg ved, at de kommer til at være de mindste dele af disse lister.
Så jeg kan sætte dem i det mindste element pletter af denne store liste.
På den anden side, hvis jeg ser på de 2 lister i det andet niveau derovre
50, 3, 42, 1337 og 15, er de ikke sorteret.
Så hvis jeg ser på 50 og 1337, vil jeg sætte 50 ind i min liste først.
Men det betyder ikke rigtig mening, fordi 3 er det mindste element ud af alle disse.
Så den eneste grund, vi kan gøre dette kombinere trin er fordi vores lister allerede er sorteret.
Det er derfor vi er nødt til at komme ned hele vejen til bunden
fordi når vi har bare et enkelt tal, du ved, at et enkelt tal
i sig selv allerede er sorteret liste.
>> Eventuelle spørgsmål? Nej?
Kompleksitet? Nå, kan du se, at der på hvert trin er der ende numre,
og vi kan opdele en liste i halvdelen log n gange,
hvilket er hvor vi får denne n x log n kompleksitet.
Og du vil se det bedste fald for fletningen slags er n log n, og det bare så sker
at den værst tænkelige, eller Ω derovre, er også n log n.
Noget at holde sig for øje.
Bevæger sig på, os gå videre til nogle super basic fil I / O. lade
Hvis du har kigget på Scramble, vil du bemærke at vi havde en slags system,
hvor man kunne skrive til en logfil, hvis du læser igennem koden.
Lad os se, hvordan du kan gøre det.
Nuvel, vi har fprintf, som du kan tænke på som bare printf,
men blot at udskrive til en fil i stedet, og dermed f i begyndelsen.
Denne form for kode op her, hvad det gør, er, som du måske har set i Scramble,
det går igennem din 2-dimensionelle række udprintning rækkevis hvad tallene er.
I dette tilfælde udskriver printf ud til din terminal eller det, vi kalder standard output af afsnittet.
>> Og nu, i dette tilfælde, er alt hvad vi har at gøre erstatte printf med fprintf,
fortælle, hvad fil, du vil udskrive til, og i dette tilfælde er det bare udskriver det til filen
i stedet for at printe det ud til din terminal.
Nå, så det rejser spørgsmålet: Hvor får vi denne form for fil fra, ikke?
Vi passerede logge på denne fprintf fuction men vi havde ingen idé om, hvor det kom fra.
Nå, tidligt i koden, hvad vi havde, var dette stykke kode herovre,
som dybest set siger, at åbne filen kalder log.txt.
Hvad vi gør efter det er vi nødt til at sørge for, at filen rent faktisk er åbnet med succes.
Så det kan mislykkes af flere årsager, og du ikke har nok plads på din computer, for eksempel.
Så det er altid vigtigt, før du gør alle operationer med filen
at vi kontrollere, om den pågældende fil blev åbnet med succes.
Så hvad at A, der er et argument for fopen, godt, vi kan åbne en fil på mange måder.
Hvad vi kan gøre er, kan vi give det w, hvilket betyder tilsidesætte filen, hvis det kommer ud allerede,
Vi kan passere en a, som de føjes til slutningen af ​​filen i stedet for tvingende det,
eller vi kan specificere r, hvilket betyder, lad os åbne filen som skrivebeskyttet.
Så hvis programmet forsøger at foretage ændringer i filen,
råber ad dem og ikke lade dem gøre det.
Endelig, når vi er færdig med filen, færdig med at gøre operationer på det,
vi nødt til at sikre, at vi lukker filen.
Og så i slutningen af ​​dit program, kan du komme til at passere dem igen
denne fil, du har åbnet, og bare lukke den.
Så det er noget vigtigt, at du er nødt til at sikre, at du gør.
Så husk du kan åbne en fil, så kan du skrive til filen,
udfører operationer i filen, men så er du nødt til at afslutte sagen i slutningen.
>> Eventuelle spørgsmål vedrørende grundlæggende filbaseret I / O? Ja?
[Student spørgsmål, uforståelig]
Lige her. Spørgsmålet er så, hvor denne Log.txt vist?
Tja, hvis du bare give det log.txt, det skaber det i samme mappe som den eksekverbare.
Så hvis Du er - >> [Student spørgsmål, uforståelig]
Ja. I den samme mappe, eller i den samme mappe. Som du kalder det
Nu hukommelse, stack, og bunke.
Så hvordan er hukommelse fastlagt i computeren?
Nå, kan du forestille dig hukommelse som en slags af denne blok her.
Og i hukommelsen har vi hvad der kaldes den bunke fast derovre, og den stak, der er dernede.
Og heap vokser nedad og stablen vokser opad.
Så som Tommy nævnte - oh, ja, og vi har disse andre 4 segmenter, som jeg vil komme til i en anden -
Som Tommy sagde tidligere, du ved, hvordan hans funktioner kalder sig og kalder hinanden?
De opbygger denne form for stakramme.
Tja, hvis de vigtigste opkald foo, bliver Foo sat på stakken.
Foo kalder bar, bar få os sætte på stakken, og der bliver lagt på stakken efter.
Og da de vender tilbage, de hver få taget fra stakken.
Hvad har hver af disse steder og hukommelse holde?
Godt, toppen, som er tekstsegment, indeholder selve programmet.
Så maskinkode, der er der, når du kompilere dit program.
Dernæst enhver startværdi globale variable.
>> Så du har globale variabler i dit program, og du siger ligesom, a = 5,
der bliver lagt i dette segment, og lige under det,
du har initialiserede globale data, som er lige int a,
men du behøver ikke sige det er lig med noget.
Indse disse er globale variabler, så de er uden for main.
Så det betyder nogen globale variabler, der angives, men er ikke initialiseret.
Så hvad der er i bunke? Memory fordeles efter malloc, som vi vil komme til i en lille smule.
Og endelig, med stakken du har nogen lokale variable
og alle funktioner man kunne kalde i nogen af ​​deres parametre.
Den sidste ting, behøver du ikke virkelig nødt til at vide, hvad de miljøvariabler gør,
men hver gang du kører programmet, der er forbundet noget, som
Dette er brugernavnet på den person, der kørte programmet.
Og det kommer til at blive slags i bunden.
I form af hukommelsesadresser, som er hexadecimale værdier,
værdierne ved det øverste begyndelse ved 0, og de går hele vejen ned til bunden.
I dette tilfælde, hvis du er på 32-bit system
adressen i bunden bliver 0x, efterfulgt af AF, fordi det er 32 bits,
som er otte bytes, og i dette tilfælde 8 byte svarer til 8 hexadecimale cifre.
Så hernede du vil have, ligesom, 0xffffff, og deroppe du vil have 0.
Så hvad er henvisninger? Nogle af jer har måske ikke dækket dette i afsnittet før.
men vi gik over det i forelæsning, så en pointer er blot en datatype
som lagrer i stedet for en form for værdi som 50, lagrer adressen på en lokation i hukommelsen.
Ligesom det minde [uforståelig].
Så i dette tilfælde, hvad vi har, er, at vi har en pegepind til et heltal eller en int *,
og den indeholder det hexadecimale adresse 0xDEADBEEF.
>> Så hvad vi har, er, nu, denne pointer peger på en placering i hukommelsen,
og det er bare en, værdien 50 er på denne hukommelsesplads.
På nogle 32-bit systemer, på alle 32-bit systemer pointers tage op 32 bits eller 4 bytes.
Men, for eksempel på en 64-bit-system, er henvisninger 64 bit.
Så det er noget, du ønsker at holde sig for øje.
Så på en ende-bit system er en pointer ende bit lang.
Pointers er slags svært at fordøje uden ekstra ting,
så lad os gå igennem et eksempel på dynamisk allokering af hukommelse.
Hvad dynamisk allokering af hukommelse gør for dig, eller hvad vi kalder malloc,
det kan du tildele en form for data uden for sættet.
Så disse data er slags mere permanent i hele programmet.
Fordi som du ved, hvis du erklærer x inde i en funktion, og at funktionen returnerer
du ikke længere har adgang til de data, der blev gemt i x.
Hvad pointers lad os gøre, er de Lad os gemme hukommelse eller lagre værdier
i et andet segment af hukommelse, nemlig heap.
Nu når vi igen ud af funktion, så længe vi har en pointer
til den pågældende placering i hukommelsen, hvad vi kan gøre så er vi bare kan se på de værdier der.
Lad os se på et eksempel: Dette er vores hukommelse layout igen.
Og vi har denne funktion, vigtigste.
Hvad det gør, er - okay, så simpelt, ikke -? Int x = 5, det er bare en variabel på stakken i main.
>> På den anden side, vi nu erklære en pointer, der kalder funktionen giveMeThreeInts.
Og så nu går vi ind i denne funktion, og vi skaber en ny stak ramme for det.
Men i denne stakramme, erklærer vi int * temp,
som i mallocs 3 heltal for os.
Så størrelse int vil give os hvor mange bytes denne int er,
og malloc giver os, at mange bytes af plads på heapen.
Så i dette tilfælde har vi skabt plads til 3 heltal,
og den bunke er vejen derop, hvilket er grunden til jeg har tegnet det højere op.
Når vi er færdige, kommer vi tilbage op her, behøver du kun 3 int'er returneret,
og det returnerer adressen, i dette tilfælde over, hvor denne hukommelse er.
Og vi sætter pointer = switch, og op der har vi bare en anden pointer.
Men hvad der returnerer funktionen er stablet her og forsvinder.
Så temp forsvinder, men vi stadig bevare adressen på hvor
disse 3 heltal er inde i elnettet.
Så i dette sæt er markørerne scoped lokalt til den stablede rammen,
men hukommelsen, de henviser til, er i dyngen.
>> Giver det mening?
[Student] Kunne du gentage det? >> [Joseph] Ja.
Så hvis jeg går tilbage bare en lille smule, kan du se at temp tildelt
noget hukommelse på heapen deroppe.
Så når denne funktion, giveMeThreeInts afkast, er denne stak her kommer til at forsvinde.
Og med det som helst af de variabler, i dette tilfælde den pointer, der blev tildelt i stablet ramme.
Det kommer til at forsvinde, men da vi vendte temp
og vi sætter pointer = temp, pointer er nu kommer til at pege samme hukommelse placering som temp var.
Så nu, selvom vi mister temp, at lokale pointer,
vi stadig bevare lageradressen af, hvad det var der peger på indersiden af ​​det variable pointer.
Spørgsmål? Det kan være lidt af en forvirrende emne, hvis du ikke har gået over det i pkt.
Vi kan, vil din TF helt sikkert gå over det, og vi kan selvfølgelig besvare spørgsmål
ved slutningen af ​​undersøgelsen session for dette.
Men det er en slags et komplekst emne, og jeg har flere eksempler på, at der kommer til at dukke op
som vil bidrage til at afklare, hvad pegepinde egentlig er.
>> I dette tilfælde er henvisninger svarer til arrays,
så jeg kan bare bruge denne pegepind som det samme som en int array.
Så jeg indeksering i 0, og ændre det første heltal til 1,
ændre den anden heltal til 2, og 3. heltal til 3.
Så mere om pegepinde. Nå, huske Binky.
I dette tilfælde har vi tildelt en pegepind, eller vi erklæret en pegepind,
men i første omgang, da jeg netop erklæret en pegepind, er det ikke peger på et vilkårligt sted i hukommelsen.
Det er bare skrald værdier indeni det.
Så jeg har ingen idé om, hvor denne pointer peger på.
Det har en adresse, som bare fyldt med 0 s og 1 s, hvor det oprindeligt blev anmeldt.
Jeg kan ikke gøre noget med dette, indtil jeg kalder malloc på det
og så det giver mig lidt plads på heapen, hvor jeg kan sætte værdier inde.
Så igen, jeg ved ikke, hvad der er inde i denne hukommelse.
Så det første jeg skal gøre er at kontrollere, om systemet havde nok hukommelse
at give mig tilbage 1 heltal i første omgang, hvilket er grunden til jeg gør dette tjek.
Hvis pointer er null, det betyder, at det ikke har nok plads eller en anden fejl opstod,
så jeg skulle afslutte ud af mit program.
Men hvis det lykkedes, nu kan jeg bruge denne pegepind
og hvad * pointer gør, er det følger hvor adressen er
hvor denne værdi er, og det sætter det lig med 1.
Så over her, vi tjekker, om at hukommelsen eksisterede.
>> Når du ved det eksisterer, kan du sætte ind i det
hvilken værdi, du ønsker at sætte ind i det, i dette tilfælde 1.
Når vi er færdig med det, skal du frigøre denne pegepind
fordi vi har brug for at komme tilbage til det system, som hukommelse, som du bad om i første omgang.
Fordi computeren ikke vide, hvornår vi er færdige med det.
I dette tilfælde er vi eksplicit at fortælle det, okay, vi er færdige med denne hukommelse.
Hvis en anden proces har brug for det, et andet program har behov for det, er du velkommen til at gå videre og tage den.
Hvad kan vi også gøre, er at vi bare kan få adressen på lokale variable på tv'et.
Så int x er inde i stablet ramme main.
Og når vi bruger dette tegnet, denne og operatør, hvad det gør, er
det tager x, og x er blot nogle data i hukommelse, men den har en adresse.
Det er placeret et eller andet sted. Så ved at ringe & x, hvad dette gør, er at det giver os adressen på x.
Ved at gøre dette, gør vi pointer pege på hvor x er i hukommelsen.
Nu skal vi bare gøre noget lignende * x, vi kommer til at få 5 tilbage.
Stjernen hedder dereferere det.
Du følger den adresse, og du får værdien af ​​det gemt der.
>> Eventuelle spørgsmål? Ja?
[Student] Hvis du ikke gør det 3-spidse ting, betyder det stadig kompilere?
Ja. Hvis du ikke gør det 3-pointer ting, er det stadig kommer til at kompilere,
men jeg vil vise dig, hvad der sker i en anden, og uden at gøre det,
det er hvad vi kalder en hukommelsesfejl. Du er ikke giver systemet
bakke sin hukommelse, så efter et stykke tid at programmet kommer til at akkumulere
hukommelse, det er ikke bruger, og intet andet kan bruge det.
Hvis du nogensinde har set Firefox med 1,5 millioner kilobyte på din computer,
i opgaven manager, er det, hvad der foregår.
Du har en hukommelsesfejl i programmet, at de ikke er håndtering.
Så hvordan gør pointer aritmetiske arbejde?
Nå, pointer Regnestykket er lidt ligesom indeksering i et array.
I dette tilfælde har jeg en pegepind, og hvad jeg gør, er jeg gøre pointer peger på det første element
af denne række af 3 heltal, som jeg har tildelt.
Så nu hvad jeg gør, stjerne pointer bare ændrer det første element i listen.
Stjerne pointer +1 point herovre.
Så pointer er herovre, pointer +1 er herovre, pointer +2 er herovre.
>> Så bare tilsætte 1 er det samme som at bevæge sig langs denne array.
Hvad vi gør, er, når vi gør pointer +1 Du får adressen herover,
og for at få værdien herind, satte man en stjerne i fra hele udtrykket
at dereference det.
Så i dette tilfælde, jeg sætte den første plads i dette array til 1,
anden placering til 2, og tredje placering til 3.
Så hvad jeg laver herovre er jeg udskriver vores pointer +1,
der bare giver mig 2.
Nu er jeg forøgelse pointer, så markøren er lig pointer +1,
der bevæger det fremad.
Og så nu, hvis jeg udskrive pointer +1, pointer +1 er nu 3,
som i dette tilfælde udskrives 3.
Og for at frigøre noget, den pointer, jeg giver det
skal pege i begyndelsen af ​​det array, som jeg fik tilbage fra malloc.
Så i dette tilfælde, hvis jeg skulle kalde 3 lige her, ville dette ikke være rigtigt,
fordi det er i midten af ​​array.
Jeg er nødt til at fratrække at komme til den oprindelige placering
den oprindelige første stedet, før jeg kan frigøre det.
Så her er en mere involveret eksempel.
I dette tilfælde er vi afsætte 7 tegn i en karakter array.
>> Og i dette tilfælde, hvad vi laver, er vi looping over den første 6 af dem,
og vi indstille dem til Z.
Så for int i = 0, i> 6, i + +,
Så pointer + jeg vil bare give os, i dette tilfælde,
pointer, pointer 1, pointer to, pointer 3, og så videre og så videre i sløjfen.
Hvad det kommer til at gøre, er det får denne adresse, dereferences det for at få den værdi,
og ændringer, som værdi til en Z.
Så i slutningen huske dette er en streng, right?
Alle strengene er nødt til at ende med nul afslutning karakter.
Så, hvad jeg gør, er i pegepinden 6 Jeg sætter null terminator karakter i.
Og nu hvad jeg dybest set laver herovre er ved at implementere printf efter en streng, ikke?
>> Så, når printf nu, når det er nået til enden af ​​en snor?
Når den rammer nul afslutning karakter.
Så i dette tilfælde. Mine oprindelige pointer peger på starten af ​​dette array
Jeg udskriver det første tegn ud. Jeg flytter den hen over en.
Jeg udskrive denne karakter ud. Jeg flytte den over.
Og jeg holde gøre dette indtil jeg når til slutningen.
Og nu enden * pointer vil dereference dette og få nul afslutning karakter tilbage.
Og så min while-løkke kører kun, når denne værdi ikke er den nul afslutning karakter.
Så, nu jeg afslutte ud af denne løkke.
Og så hvis jeg trækker 6 fra denne pointer,
Jeg går helt tilbage til begyndelsen.
Husk, jeg gør det, fordi jeg er nødt til at gå til starten for at frigøre det.
>> Så jeg ved, det var en masse. Er der nogen spørgsmål?
Please, ja?
[Student spørgsmål uforståelig]
Kan du sige det højere? Undskyld.
[Student] Den sidste slide lige før du befriet markøren,
hvor var du faktisk at ændre værdien af ​​markøren?
[Joseph] Så lige her. >> [Student] Åh, okay.
[Joseph] Så jeg har en pegepind minus minus, højre,
som bevæger ting tilbage en, og så skal jeg befri det,
fordi denne pointer skal understreges til begyndelsen af ​​array.
[Student] Men det ville ikke være nødvendig havde du stoppet efter denne linje.
[Joseph] Så hvis jeg havde stoppet efter dette, ville det blive betragtet som en hukommelsesfejl,
fordi jeg ikke køre den gratis.
[Student] I [uforståelig] efter de første tre linjer, hvor du havde pointer +1 [uforståelig].
[Joseph] Uh-huh. Så, hvad er det spørgsmål der?
Undskyld. Nej, nej. Gå, gå, tak.
[Student] Så er du ikke ændre værdien af ​​pegepinde.
Du ville ikke have haft at gøre pointer minus minus.
[Joseph] Ja, præcis.
Så når jeg gør pointer +1 og pointer +2,
Jeg laver ikke pointer lig pointer +1.
Således, markøren blot forbliver peger i begyndelsen af ​​grupperingen.
Det er kun, når jeg gør plus plus at det sætter værdi tilbage inde i markøren,
at det faktisk bevæger denne sammen.
Ok.
Flere spørgsmål?
>> Igen, hvis det er en slags overvældende, vil dette blive dækket i session.
Spørg din undervisning fyr om det, og vi kan besvare spørgsmål i slutningen.
Og normalt er vi ikke kan lide at gøre det minus ting.
Dette har at kræve mig at holde styr på, hvor meget jeg har forskudt i array.
Så generelt er det bare at forklare, hvordan pointer aritmetiske værker.
Men hvad vi normalt gerne gøre, er at vi gerne skabe en kopi af markøren,
og så vil vi bruge den kopi, når vi bevæger os rundt i strengen.
Så i disse tilfælde du bruge kopien til at udskrive hele strengen,
men vi behøver ikke at gøre som pointer minus 6 eller holde styr på, hvor meget vi flyttede i dette,
bare fordi vi ved, at vores oprindelige punkt stadig bliver peget på i starten af ​​listen
og alt, hvad vi ændrede var denne kopi.
Så generelt ændre kopier af din oprindelige pointer.
Forsøg ikke at sortere i lignende - lad være at ændre originale kopier.
Forsøger at ændre kun kopier af din original.
Så du bemærker, når vi passerer strengen i printf
du behøver ikke at sætte en stjerne foran det ligesom vi gjorde med alle de andre dereferences, right?
Så hvis du udskrive hele strengen% s forventer er en adresse,
og i dette tilfælde en pegepind eller i dette tilfælde som en række tegn.
>> Tegn, char * s, og arrays er de samme ting.
Pointer er til tegn, og tegndatatabeller er det samme.
Og så er alt, hvad vi skal gøre passere i pointer.
Vi behøver ikke at passere ind som * pegepind eller sådan noget.
Så, arrays og pointers er de samme ting.
Når du laver noget lignende x [y] herovre for et array,
hvad det gør under kølerhjelmen er det siger, okay, det er et tegn array,
så det er en pointer.
Og så x er de samme ting,
og så hvad det gør, er det tilføjer y til x,
hvilket er det samme som at bevæge sig fremad i hukommelsen så meget.
Og nu x + y giver os en slags adresse,
og vi dereference adresse eller følg pilen
hvor denne placering i hukommelsen er, og vi får værdi ud af denne placering i hukommelsen.
Så, så disse to er nøjagtig det samme.
Det er bare en syntaktisk sukker.
De gør det samme. De er bare forskellige syntactics for hinanden.
>> Så hvad kan gå galt med pointers? Ligesom en masse. Okay. Så dårlige ting.
Nogle dårlige ting, du kan gøre, er ikke at kontrollere, om din malloc kaldet returnerer null, right?
I dette tilfælde, jeg beder systemet til at give mig - hvad er det nummer?
Ligesom 2000000000 gange 4, fordi størrelsen af ​​et helt tal er fire bytes.
Jeg beder det om som 8 milliard bytes.
Selvfølgelig min computer ikke vil være i stand til at give mig så meget hukommelse tilbage.
Og vi ikke kontrollere, om dette er null, så når vi forsøger at dereference det derovre -
Følg pilen til, hvor det kommer til at - vi ikke har den hukommelse.
Det er, hvad vi kalder dereferere en null-pointer.
Og det væsentlige får dig til at segfault.
Dette er en af ​​de måder, du kan segfault.
Andre dårlige ting du kan gøre - oh well.
Det var dereferere en null-pointer. Okay.
Andre dårlige ting - godt, at fastsætte, at du bare sætte en check i der
som kontrollerer, om markøren er null
og afslutte ud af programmet, hvis det sker, at malloc returnerer en null-pointer.
Det er den xkcd tegneserie. Folk forstår det nu. Sorter af.
>> Så hukommelse. Og jeg gik over dette.
Vi kalder malloc i en løkke, men hver gang vi kalder malloc
vi at miste overblikket over, hvor denne pegepind peger på,
fordi vi clobbering det.
Så det første opkald til malloc giver mig hukommelse herovre.
Min pointer henvisninger til dette.
Nu mener jeg ikke frigøre det, så nu kalder jeg malloc igen.
Nu peger herovre. Nu er min hukommelse peger herovre.
Pege herovre. Pege herovre.
Men jeg har mistet overblikket over adresserne på hele hukommelsen herovre at jeg tildelt.
Og så nu jeg har ikke nogen henvisning til dem længere.
Så kan jeg ikke befri dem uden for dette loop.
Og så for at løse noget som dette,
hvis du glemmer at frigøre hukommelse og du får denne hukommelsesfejl,
Du er nødt til at frigøre hukommelse inde i denne løkke, når du er færdig med det.
Nå, det er hvad der sker. Jeg kender masser af du hader dette.
Men nu - yay! Du får ligesom 44.000 kilobyte.
Så, man befri den for enden af ​​løkken,
og det kommer til at bare frigøre hukommelse hver gang.
Væsentlige, er dit program ikke har en hukommelsesfejl længere.
>> Og nu noget andet, du kan gøre, er at frigøre noget hukommelse, som du har bedt om to gange.
I dette tilfælde, du malloc noget du ændre dens værdi.
Du frigøre det én gang, fordi du sagde, du var færdig med den.
Men derefter vi befriede det igen.
Det er noget, der er temmelig dårlig.
Det er ikke til at begynde segfault,
men efter et stykke tid, hvad det betyder er dobbelt frigør dette korrumperer din bunke struktur,
og du vil lære lidt mere om dette, hvis du vælger at tage en klasse som CS61.
Men det væsentlige efter et stykke tid din computer kommer til at blive forvirret
om, hvad hukommelsespladser er hvor og hvor den er gemt -
hvor data lagres i hukommelsen.
Og så frigør en pointer to gange er en dårlig ting, som du ikke ønsker at gøre.
>> Andre ting der kan gå galt er ikke bruger sizeof.
Så i dette tilfælde skal du allokere 8 byte,
og det er det samme som to heltal, right?
Så det er helt sikkert, men er det?
Nå, som Lucas talte om på forskellige arkitekturer,
heltal er af forskellig varighed.
Så på apparatet, som du bruger, er hele tal omkring 4 bytes,
men på et andet system de kunne være 8 bytes, eller de kan være 16 byte.
Så hvis jeg bare bruge dette nummer herovre,
dette program kan arbejde på apparatet,
men det kommer ikke til at allokere nok hukommelse på et andet system.
I dette tilfælde er det, hvad den sizeof operatør bruges til.
Når vi kalder sizeof (int), hvad det gør, er
det giver os størrelsen af ​​et heltal på systemet, at programmet kører.
Så i dette tilfælde vil sizeof (int) returnerer 4 på noget som apparatet,
og nu denne vilje 4 * 2, hvilket er 8,
som er lige den mængde plads er nødvendig for to heltal.
På et andet system, hvis en int er ligesom 16 byte eller 8 bytes
det bare at gå tilbage nok bytes til at gemme dette beløb.
>> Og endelig, struct.
Så hvis du ønsker at gemme en sudoku bord i hukommelsen, hvordan kunne vi gøre det?
Du tror måske, ligesom en variabel for det første,
en variabel til den anden ting, en variabel for den tredje ting,
en variabel for fjerde ting - dårlig, ikke?
Så en forbedring du kan gøre på toppen af ​​dette er at lave en 9 x 9 array.
Det er fint, men hvad nu hvis du ønsker at knytte andre ting med sudoku bestyrelse
lide, hvad det er vanskeligt at bestyrelsen er,
eller for eksempel? hvad din score er, eller hvor meget tid det har taget dig at løse dette board
Nå, hvad du kan gøre, er du kan oprette en struct.
Hvad jeg dybest set siger, er jeg definere denne struktur herovre,
og jeg definerer en sudoku bestyrelse, som består af en bestyrelse, der er 9 x 9.
>> Og hvad det har den har henvisninger til navnet på niveau.
Det har også x og y, som er koordinaterne for, hvor jeg er lige nu.
Det har også tid [uforståeligt], og det har det samlede antal træk, jeg har indlæst hidtil.
Og så i dette tilfælde, kan jeg gruppere en hel masse data ind i kun én struktur
stedet for at have det som at flyve rundt i ligesom forskellige variabler
at jeg ikke kan virkelig holde styr på.
Og det lader os har bare nice syntaks for slags referere forskellige ting inde i denne struct.
Jeg kan bare gøre board.board, og jeg får sudoku bord tilbage.
Board.level, jeg får hvor hårdt det er.
Board.x og board.y give mig koordinaterne for, hvor jeg kan være i bestyrelsen.
Og så jeg adgang til det, vi kalder felter i struct.
Dette definerer sudokuBoard, som er en type, som jeg har.
Og nu er vi her. Jeg har en variabel kaldet "board" af typen sudokuBoard.
Og så nu kan jeg få adgang til alle de felter, der udgør denne struktur herovre.
>> Eventuelle spørgsmål om struct? Ja?
[Student] For int x, y, du erklærede både på én linje? >> [Joseph] Uh-huh.
[Student] Så kunne du bare gøre det med dem alle?
Ligesom i x, y komma gange, at den samlede?
[Joseph] Ja, det kan du helt sikkert gøre det, men grunden til at jeg satte x og y på samme linje -
og spørgsmålet er, hvorfor kan vi bare gøre det på samme linie?
Hvorfor gør vi ikke bare sætte alle disse på samme linje er
x og y er relateret til hinanden,
og dette er bare stilistisk mere korrekt, i en vis forstand,
fordi det er gruppering to ting på samme linje
at lignende slags vedrører samme ting.
Og jeg har lige dele disse fra hinanden. Det er bare en stil ting.
Det funktionelt gør ingen forskel overhovedet.
Eventuelle andre spørgsmål om struct?
Du kan definere en Pokedex med en struct.
En Pokémon har et nummer og det har et brev, en ejer, en type.
Og så hvis du har en bred vifte af Pokémon, kan du gøre op en Pokedex, right?
Okay, cool. Så spørgsmål om struct. Det er relateret til struct.
>> Endelig GDB. Hvad betyder GDB lade dig gøre? Det kan du debug din program.
Og hvis du ikke har brugt GDB, ville jeg anbefalet at se den korte
og bare gå over, hvad GDB er, hvordan du arbejder med det, hvordan du kan bruge det,
og teste det på et program.
Og hvad så GDB lader dig gøre, er det lader pause [uforståelig] op dit program
og en praktisk linie.
For eksempel, vil jeg holde pause udførelse på ligesom linje 3 i mit program,
og mens jeg er på linie 3 Jeg kan udskrive alle de værdier, der er der.
Og så det, vi kalder ligesom pause i en linje
er vi kalde dette at sætte et breakpoint på denne linje
og så kan vi udskrive variabler på tilstanden af ​​programmet på det tidspunkt.
>> Vi kan så derfra gå gennem programmet linje for linje.
Og så kan vi se på tilstanden af ​​stablen på det tidspunkt.
Og så for at bruge GDB, hvad vi gør, er vi kalder Klang på C-fil,
men vi er nødt til at passere det-ggdb flag.
Og når vi er færdige med at vi bare køre gdb på den resulterende output fil.
Og så får du nogle lignende masse tekst som denne,
men virkelig alt hvad du skal gøre er at skrive i kommandoer i begyndelsen.
Break main sætter et breakpoint på main.
Liste 400 opregner de linjer kode omkring linie 400.
Og så i dette tilfælde kan du bare kigge dig omkring og sige, åh,
Jeg ønsker at indstille et breakpoint på linje 397, som er denne linje,
og derefter dit program kører ind i det trin og det kommer til at bryde.
Det kommer til pause der, og du kan printe ud, for eksempel værdien af ​​lav eller høj.
Og så er der en masse kommandoer, du har brug for at vide,
og dette diasshow vil gå op på hjemmesiden,
så hvis du blot ønsker at referere disse eller lignende lægge dem på din snyde ark, velkommen.
>> Cool. Det var Quiz anmeldelse 0, og vi vil holde sig i nærheden, hvis du har spørgsmål.
Ok.
>> [Bifald]
>> [CS50.TV]