[Powered by Google Translate] [Hersieningsraad] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard Universiteit]
>> [Hierdie is CS50.] [CS50.TV]
>> Hey, almal.
Welkom by die hersiening sessie vir Quiz 0, wat sal plaasvind hierdie Woensdag.
Wat gaan ons doen vanaand, ek is met 3 ander TFS,
en saam gaan ons om te gaan deur 'n oorsig van wat ons gedoen het tot dusver in die kursus.
Dit gaan nie om te wees 100% omvattende, maar dit moet gee jou 'n beter idee
van wat jy reeds het en wat jy nog nodig het om te studeer voor Woensdag.
En voel vry om jou hand op te steek met vrae as ons gaan saam,
maar hou in gedagte dat ons ook sal moet 'n bietjie van die tyd aan die einde-
as ons deur 'n paar minute te spaar op algemene vrae doen,
so hou dit in gedagte, en so gaan ons begin by die begin met Week 0.
>> [Quiz 0 Review!] [Deel 0] [Lexi Ross] Maar voordat ons dit doen Kom ons praat oor
die logistiek van die quiz.
>> [Logistiek] [Quiz vind plaas in plaas van die lesing op Woensdag 10/10]
>> [(Sien http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf vir besonderhede)] Dit is op Woensdag, Oktober 10.
>> Dit is hierdie Woensdag, en as jy gaan na hierdie URL,
wat ook toeganklik vanaf CS50.net-daar 's 'n skakel om dit te
inligting oor waar om te gaan op grond van wat jy kan sien
jou laaste naam of skool affiliasie sowel as
dit vertel oor wat presies die quiz sal dek en die tipe vrae wat jy gaan kry.
Hou in gedagte dat jy ook sal 'n kans om te hersien vir die quiz artikel,
sodat jou TFS moet gaan oor 'n paar praktyk probleme,
en dit is nog 'n goeie kans om te sien waar jy nog steeds nodig om te studeer vir die quiz.
Kom ons begin by die begin met Bits 'n 'Bytes.
Onthou om 'n bietjie is net 'n 0 of 'n 1,
en 'n greep is 'n versameling van 8 van daardie stukkies.
Kom ons kyk na hierdie versameling van stukkies reg hier.
Ons moet in staat wees om uit te vind hoeveel stukkies daar is.
Waar ons reken daar is net 8 van hulle, agt 0 of 1 eenhede.
En aangesien daar is 8 bisse, wat is 1 byte,
en laat ons skakel dit om na heksadesimaal.
Heksadesimale is base 16, en dit is redelik maklik om te sit
'n nommer in die binêre, wat is wat dit is, 'n aantal in heksadesimaal.
Alles wat ons doen, is ons kyk na die groepe van 4,
en ons sit hulle aan die toepaslike heksadesimale syfer.
Ons begin met die mees regse groep van 4, so 0011.
Dit gaan om een ​​te wees 1 en een 2, so saam wat maak 3.
En dan laat ons kyk na die ander blok van 4.
1101. Wat gaan een 1, een 4, en 'n 8.
Saam dat gaan wees 13, wat maak D.
En ons sal onthou dat ons in heksadesimaal gaan net nie 0 tot 9.
Ons gaan 0 tot F, so na 9, 10 ooreenstem met 'n,
11 B, ensovoorts waar F 15.
Hier 13 is 'n D,
so te skakel dit om na desimale alles wat ons doen is ons eintlik
Behandel elke posisie as 'n krag van 2.
Dit is een 1, een 2, nul 4s, nul 8s, 16, ensovoorts,
en dit is 'n bietjie moeilik om te bereken in jou kop, maar as ons na die volgende skyfie
Ons kan die antwoord sien.
>> In wese gaan ons oor van regs terug na links,
en ons is elke syfer vermenigvuldig deur die ooreenstemmende krag van 2.
En onthou, heksadesimaal ons dui hierdie getalle aan die begin met 0x
sodat ons nie verwar dit met 'n desimale getal.
Voortgesette op, dit is 'n ASCII-tabel,
en wat ons gebruik ASCII vir kaart van karakters numeriese waardes.
Onthou in die kriptografie pset ons het uitgebreide gebruik van die ASCII-tabel
ten einde verskillende metodes om kriptografie te gebruik,
die keiser en die Vigenère cipher, verskillende letters te omskep
in 'n string wat volgens die sleutel wat deur die gebruiker.
Kom ons kyk 'n bietjie van ASCII wiskunde.
Op soek na 'P' + 1, in karakter vorm wat sou wees Q,
en onthou dat '5 '≠ 5.
En presies hoe sou ons skakel tussen die 2 vorms?
Dit is eintlik nie te moeilik.
Ten einde 5 kry ons aftrek '0 '
want daar is 5 plekke tussen die '0 'en die '5. "
Ten einde die ander manier om te gaan ons net die 0 voeg,
so dit is soort van soos 'n gereelde rekenkunde.
Net onthou dat wanneer iets aanhalings rondom dit, dit is 'n karakter
en stem dus ooreen met 'n waarde in die ASCII-tabel.
Moving into meer algemene rekenaar wetenskap onderwerpe.
Ons het geleer wat 'n algoritme is en hoe ons dit gebruik programmering
algoritmes te implementeer.
'N paar voorbeelde van algoritmes is iets regtig eenvoudig soos
kontroleer of 'n getal ewe of onewe.
Vir daardie onthou ons mod die getal met 2 en kyk of die resultaat is 0.
As dit so is, is dit nog. Indien nie, is dit vreemd.
En dit is 'n voorbeeld van 'n baie basiese algoritme.
>> 'N bietjie van 'n meer betrokke te raak 1 is 'n binêre soek,
wat ons gaan later in die hersiening sessie.
En programmering is die term wat ons gebruik vir die neem van 'n algoritme
en die omskakeling van die rekenaar kode kan lees.
2 voorbeelde van programmering is kras,
en dit is wat ons gedoen het in Week 0.
Selfs al is ons nie eintlik nie tik die kode, dit is 'n manier van die uitvoering van
hierdie algoritme, wat die druk van die syfers 1-10,
en hier is ons dieselfde doen in die C-programmeertaal.
Dit is funksioneel ekwivalent, net in verskillende tale of sintaksis.
Ons het toe geleer het oor Boolse uitdrukkings,
en 'n boolean is 'n waarde wat waar of vals is,
en hier is dikwels Boolse uitdrukkings
binnekant van voorwaardes, so as (x ≤ 5),
Wel, ons het reeds x = 5, so dat die toestand is gaan te evalueer waar.
En as dit waar is, alles kode is onder die voorwaarde
gaan word geëvalueer deur die rekenaar, sodat string gaan om gedruk te word
standaard uitvoer, en die term toestand
verwys na alles wat binne die hakies van die IF-stelling.
Onthou al die operateurs.
Onthou dit && | | wanneer ons probeer om te kombineer 2 of meer voorwaardes,
== Nie = om te kontroleer of 2 dinge gelyk is.
Onthou dat = opdrag terwyl == is 'n booleaanse operator.
≤ ≥ en dan die finale 2 is selfverduidelikend.
'N algemene oorsig van Boole-logika hier.
En Boolse uitdrukkings is ook belangrik in loops,
wat ons gaan nou verby.
Ons het geleer ongeveer 3 tipes lusse tot dusver in CS50, terwyl en doen terwyl.
En dit is belangrik om te weet dat terwyl dit vir die meeste doeleindes
ons kan eintlik gebruik van enige tipe van die lus in die algemeen
daar is sekere tipes doeleindes of gemeenskaplike patrone
programmering wat spesifiek roep vir een van hierdie loops
wat maak dit die mees doeltreffende of elegante dit op dié manier te kodeer.
Kom ons gaan oor wat elk van hierdie loops is geneig om te word wat gebruik word vir die meeste.
>> In 'n for-lus ons oor die algemeen reeds weet hoeveel keer wil ons itereer.
Dit is wat ons in die toestand.
Want i = 0, i <10, byvoorbeeld.
Ons weet reeds dat ons wil iets 10 keer te doen.
Nou, vir 'n while lus, oor die algemeen ons nie noodwendig
weet hoeveel keer wil ons die lus om te hardloop.
Maar ons weet nie 'n soort van toestand dat ons dit wil
altyd waar of altyd vals.
Byvoorbeeld, terwyl stel.
Kom ons sê dit is 'n boolean veranderlike.
Terwyl dit is waar ons wil hê om die kode te evalueer,
so 'n bietjie meer te brei, 'n bietjie meer algemeen as 'n lus
maar 'n for-lus kan ook omgeskakel word na 'n while lus.
Ten slotte, doen terwyl loops, wat kan wees die moeilijkste na regs weg te verstaan,
word dikwels gebruik wanneer ons wil die kode om eers te evalueer
voor die eerste keer het ons die toestand.
'N algemene gebruik geval vir 'n while lus
wanneer jy wil toevoer van die gebruiker te kry, en jy weet jy wil die gebruiker te vra
vir insette ten minste een keer, maar as hulle gee jou nie goeie insette dadelik
jy wil aanhou vra totdat hulle gee jou die goeie insette.
Dit is die mees algemene gebruik van 'n while lus,
en laat ons kyk na die werklike struktuur van hierdie loops.
Hulle gewoonlik altyd geneig om hierdie patrone te volg.
>> Op die for-lus binne 3 komponente:
inisialisering, gewoonlik iets soos int i = 0 waar ek die toonbank,
toestand, waar ons wil sê dit hardloop vir loop so lank as hierdie toestand nog hou,
soos ek <10, en dan uiteindelik, update, wat is hoe ons inkrementeer
die toonbank veranderlike by elke punt in die lus.
'N algemene ding daar te sien is net i + +,
wat beteken inkrementeer i 1 elke keer.
Jy kan ook iets doen soos ek + = 2,
wat beteken dat voeg 2 i elke keer as jy gaan deur die lus.
En dan die doen dit verwys net 'n kode wat eintlik loop as deel van die lus.
En vir 'n rukkie loop, hierdie keer het ons eintlik die inisialisering buite die lus,
So byvoorbeeld, laat ons sê dat ons probeer om die dieselfde tipe van die lus om te doen soos ek nou net beskryf.
Ons sou sê int i = 0 voordat die lus begin.
Dan kan ons sê terwyl ek <10 doen dit,
so dieselfde blok van die kode as voorheen,
en hierdie keer het die update deel van die kode, byvoorbeeld, i + +,
eintlik gaan binnekant van die lus.
En ten slotte, vir 'n doen terwyl dit is soortgelyk aan die while lus,
maar ons moet onthou dat die kode sal evalueer
voor die aangesig van die toestand is nagegaan, sodat dit 'n baie meer sin maak
as jy kyk na dit in volgorde van bo na onder.
In 'n doen terwyl loop die kode evalueer voordat jy selfs kyk na die tyd toestand,
terwyl 'n while lus, dit kontroleer of dit eerste.
State en veranderlikes.
Wanneer ons wil 'n nuwe veranderlike te skep wil ons eers om dit te inisialiseer.
>> Byvoorbeeld, int bar initialisatie van die veranderlike bar,
maar dit beteken nie dit gee 'n waarde, so wat is bar se waarde nou?
Ons weet nie.
Dit kan 'n gemors waarde wat voorheen in die geheue gestoor daar wees,
en ons wil nie dat die veranderlike te gebruik
totdat ons eintlik gee dit 'n waarde,
so verklaar ons dit hier.
Dan sal ons inisialiseer 42 hieronder.
Nou, natuurlik, ons weet dit kan gedoen word op een lyn, int bar = 42.
Maar net om duidelik die verskeie stappe wat gaan op,
die verklaring en die inisialisering word afsonderlik hier gebeur.
Dit gebeur op 'n stap, en die volgende een, int Baz = bar + 1,
hierdie stelling hieronder, wat inkremente Baz, so aan die einde van hierdie kode blok
as ons die waarde van Baz te druk, dit sou wees 44
omdat ons verklaar en inisialiseer 1> bar wees nie,
en dan het ons inkrementeer dit weer met die + +.
Ons het oor hierdie mooi kortliks, maar dit is goed om te hê 'n algemene
begrip van wat drade en gebeure is.
Ons veral het dit gedoen Scratch
sodat jy kan dink van die drade as verskeie rye van die kode
loop op dieselfde tyd.
In werklikheid, is dit waarskynlik nie loop op dieselfde tyd,
maar soort van abstrak kan ons dink dat dit op daardie manier.
>> Scratch, byvoorbeeld, het ons die verskeie sprites.
Dit kan die uitvoering van verskillende-kode op dieselfde tyd.
Mens kon loop terwyl die ander iets te sê
in 'n ander deel van die skerm.
Gebeure is nog 'n manier van die skeiding van die logika
tussen die verskillende elemente van die kode,
en in Scratch ons in staat was om gebeure te simuleer met behulp van die uitsending,
en dit is eintlik wanneer ek nie wanneer ek dit hoor,
maar in wese is dit 'n manier om inligting oor te dra
van een na 'n ander sprite.
Byvoorbeeld, kan jy spel oor te stuur,
en wanneer ander sprite ontvang spel oor,
dit in 'n sekere manier reageer.
Dit is 'n belangrike model in programmering te verstaan.
Net om te gaan oor die basiese Week 0, wat ons het so ver gegaan oor,
laat ons kyk na hierdie eenvoudige C program.
Die teks kan 'n klein bietjie van hier te wees, maar ek sal dit werklik gaan oor vinnige.
Ons insluitend 2 header lêers aan die bokant, cs50.h en stdio.h.
Ons is dan die definisie van 'n konstante genoem limiet te wees 100.
Ons is dan die uitvoering van ons hooffunksie.
Aangesien ons nie command line argumente gebruik hier moet ons nietig te sit
as die argumente vir die hoof.
Ons sien int bostaande hoofdoelwitte. Dit is die terugkeer tipe, vandaar terug 0 aan die onderkant.
En ons gebruik CS50 biblioteek funksie kry int
die gebruiker om insette te vra, en ons bêre dit in hierdie veranderlike x,
sodat ons verklaar x hierbo, en ons inisialiseer met x = getint.
>> Ons dan kyk om te sien as die gebruiker het ons goeie insette.
As dit is ≥ LIMIT wil ons 'n fout kode van 1 om terug te keer en 'n fout boodskap print.
En laastens, as die gebruiker aan ons gegee het goeie insette
ons gaan om die getal te kwadreer en druk wat die resultaat.
Net om seker te maak dat diegene wat al treffer huis
jy kan sien die etikette van die verskillende dele van die kode hier.
Ek genoem konstante, header lêers.
O, int x. Maak seker om te onthou wat 'n plaaslike veranderlike is.
Dit kontrasteer dit van 'n globale veranderlike, wat ons sal praat oor
'n bietjie later in die hersiening sessie,
en ons vra die biblioteek funksie printf,
so as ons het nie die stdio.h header-lêer
sou ons nie in staat wees om te printf noem.
En ek glo dat die pyl wat hier het afgesny word verwys na die% d,
wat is 'n opmaak string in printf.
Dit sê Druk hierdie veranderlike as 'n getal,% d.
En dit is dit vir Week 0.
Lucas word nou gaan om voort te gaan.
Hey, ouens. My naam is Lucas.
Ek is 'n stage in die beste huis op kampus, Mather,
en ek gaan 'n bietjie om te praat oor Week 1 en 2,1.
[Week 1 en 2,1] [Lucas Freitas]
As Lexi het gesê, toe ons begin met die vertaling van jou kode van nuuts af aan C
een van die dinge wat ons opgemerk is dat jy kan nie net
skryf jou kode en voer dit met behulp van 'n groen vlag nie.
Eintlik, jy het 'n paar stappe om te gebruik om jou C-program te maak
word 'n uitvoerbare lêer.
Basies wat jy doen wanneer jy 'n program te skryf is dat
jy vertaal jou idee in 'n taal wat 'n vertaler kan verstaan,
So wanneer jy 'n program te skryf in C
wat jy doen is eintlik iets te skryf wat jou samesteller is gaan om te verstaan,
en dan die vertaler gaan daardie kode te vertaal
in iets wat jou rekenaar sal verstaan.
>> En die ding is, jou rekenaar is eintlik baie dom.
Jou rekenaar kan slegs verstaan ​​0'e en 1s,
so eintlik in die eerste rekenaars mense gewoonlik geprogrammeer
deur gebruik te maak van 0'e en 1s, maar nie meer nie, dank God.
Ons het nie die rye vir 0'e en 1s te memoriseer
vir 'n for-lus of vir 'n while lus en so aan.
Dit is waarom ons 'n vertaler.
Wat 'n vertaler nie, is dit basies vertaal die C-kode,
in ons geval, 'n taal wat jou rekenaar sal verstaan,
wat is die object code, en die samesteller wat ons gebruik
genoem word klang, so dit is eintlik die simbool vir die geratel.
Wanneer jy jou program, moet jy 2 dinge te doen.
Eerstens, jy het jou program saam te stel, en dan is jy gaan om jou program uit te voer.
Jou program saam te stel, jy het 'n baie van die opsies om dit te doen.
Die eerste een is kletteren program.c te doen
wat die program is die naam van jou program.
In hierdie geval kan jy sien hulle net sê "Hey, my program saamstel."
Jy nie sê: "Ek wil hê dat hierdie naam vir my program" of iets.
>> Die tweede opsie is om 'n naam te gee jou program.
Jy kan sê klang-o en dan die naam wat jy wil
die uitvoerbare lêer en dan program.c genoem word.
En jy kan dit ook doen maak program, en sien hoe in die eerste 2 gevalle
Ek het c, en in die derde een het ek net 'programme?
Ja, jy eintlik moet nie sit c wanneer jy gebruik maak.
Anders is die samesteller is eintlik van plan om op jou te skree.
En ook, ek weet nie as julle onthou,
maar 'n baie tye wat ons ook gebruik lcs50 of lm.
Wat genoem word koppel.
Dit vertel net die samesteller dat jy die biblioteke sal reg daar te gebruik,
so as jy wil cs50.h te gebruik wat jy eintlik te tik
kletteren program.c-lcs50.
As jy nie doen nie, is die vertaler nie weet
dat jy met behulp van die funksies in cs50.h.
En wanneer jy wil om jou program uit te voer jy het 2 opsies.
As jy het geratel program.c jy het nie 'n naam aan jou program.
Jy het om dit uit te voer met behulp van / a.out..
A.out is 'n standaard naam wat kletteren gee jou program as jy dit nie 'n naam.
Anders gaan jy / program. Te doen as jy 'n naam gegee het aan jou program,
en ook as jy maak program die naam wat 'n program gaan kry
is reeds gaan word geprogrammeer met dieselfde naam as die c-lêer.
Dan het ons gepraat oor die datatipes en data.
>> Basies data tipes is dieselfde ding as boksies wat hulle gebruik
waardes op te slaan, sodat datatipes is eintlik net soos pokemons.
Hulle kom in alle groottes en tipes.
Ek weet nie indien daardie analogie sin maak.
Die data grootte hang eintlik op die masjien argitektuur.
Al die data groottes dat ek gaan om hier te wys
is eintlik vir 'n 32-bis masjien, wat is die geval van ons toestel,
maar as jy eintlik die kodering van jou Mac of in 'n Windows ook
jy waarskynlik gaan 'n 64-bis masjien te hê,
so onthou dat die data groottes wat ek gaan hier om te wys
is vir die 32-bis masjien.
Die eerste een wat ons gesien het was 'n int,
wat is redelik eenvoudig.
Jy gebruik int 'n heelgetal te stoor.
Ons het ook die karakter, die char.
As jy wil 'n brief of 'n simbool te gebruik wat jy waarskynlik gaan 'n kar om te gebruik.
'N char het 1 byte, wat beteken 8 stukkies, soos Lexi gesê.
Basies het ons 'n ASCII tabel wat 256
moontlike kombinasies van 0'e en 1s,
en dan wanneer jy 'n kar dit gaan om te vertaal
die karakter wat insette jy 'n nommer wat jy het in die ASCII-tabel, soos Lexi gesê.
Ons het ook die float wat ons gebruik om desimale getalle te stoor.
As jy wil om te kies 3,14, byvoorbeeld, jy gaan 'n float te gebruik
of 'n dubbel wat meer akkuraatheid.
'N float het 4 grepe.
'N dubbel 8 grepe, so die enigste verskil is die presisie.
Ons het ook 'n lang wat gebruik word vir heelgetalle,
en jy kan sien vir 'n 32-bis masjien 'n int en 'n lang dieselfde grootte,
so dit maak nie regtig sin maak 'n lang om te gebruik in 'n 32-bis masjien.
>> Maar as jy die gebruik van 'n Mac en 64-bis masjien, eintlik 'n lang grootte 8,
so dit hang af van die argitektuur.
Vir die 32-bis masjien dit nie sin maak nie 'n lang om werklik te gebruik.
En dan 'n lang lang, aan die ander kant, het 8 grepe,
so dit is baie goed as jy wil 'n langer heelgetal te hê.
En laastens, ons het string, wat eintlik 'n char *
wat is 'n verwysing na 'n char.
Dit is baie maklik om te dink dat die grootte van die tou gaan wees soos
die aantal karakters wat jy daar,
maar eintlik is die char * self
het die grootte van 'n wyser na 'n char wat is 4 grepe.
Die grootte van 'n char * is 4 grepe.
Dit maak nie saak as jy 'n klein woord of 'n brief of iets.
Dit gaan wees 4 grepe.
Ons het ook geleer 'n bietjie oor die beslissende,
so soos jy kan sien, as jy, byvoorbeeld, 'n program wat sê
int x = 3 en dan printf ("% d", x / 2)
julle weet wat dit gaan om op die skerm te druk?
>> Iemand >> [Studente] 2.
1. >> 1, ja.
As jy dit doen 3/2 gaan om 1,5 te kry,
maar aangesien ons met behulp van 'n heelgetal dit gaan die desimale deel te ignoreer,
en jy gaan te hê 1.
As jy nie wil hê dat dit gebeur wat jy kan doen, byvoorbeeld,
is 'n float verklaar y = x.
Dan is x wat gebruik word om 3 gaan nou 3,000 in y.
En dan kan jy druk die y / 2.
Eintlik, moet ek 'n 2. daar.
Dit gaan 3.00/2.00 te doen,
en jy gaan te kry 1,5.
En ons het hierdie 0,2 f net te vra vir 2 desimale eenhede in die desimale deel.
As jy het 0,3 f dit gaan eintlik het 1,500.
As dit is 2 gaan dit wees 1,50.
Ons het ook hierdie geval hier.
As jy dit doen float x = 3,14 en dan kan jy printf x
jy gaan te kry 3,14.
En as jy dit doen x = int van x,
wat beteken behandel x as 'n int, en jy druk x nou
jy gaan te hê 3,00.
Maak dit sin?
Omdat jy eerste X te behandel as 'n heelgetal, sodat jy ignoreer die desimale deel,
en dan is jy die druk van x.
En laastens, kan jy dit ook doen,
int x = 65, en dan verklaar 'n char c = x,
en dan as jy die druk van die c wat jy eintlik gaan om te kry
A, so basies wat jy hier doen,
die vertaling van die heelgetal in die karakter,
net soos die ASCII-tabel nie.
Ons het ook gepraat oor die wiskunde operateurs.
Die meeste van hulle is redelik eenvoudig, so +, -, *, /,
en ook het ons gepraat oor die mod, wat is die res van 'n afdeling van 2 getalle.
As jy 10% 3, byvoorbeeld,
beteken dit verdeel 10 deur 3, en wat is die res?
Dit gaan wees 1, so dit is eintlik baie nuttig vir 'n baie van die programme.
Vir Vigenère en Caesar Ek is redelik seker dat almal van julle ouens gebruik mod.
Oor wiskunde operateurs, baie versigtig wees wanneer die kombinasie van * en /.
>> Byvoorbeeld, as jy dit doen (3/2) * 2 wat jy gaan kry?
[Studente] 2.
Ja, 2, want 3/2 gaan wees 1,5,
maar aangesien jy doen bewerkings tussen 2 heelgetalle
jy eintlik net gaan om te oorweeg 1,
en dan 1 * 2 gaan wees 2, so baie, baie versigtig wees
wanneer om rekenkunde met heelgetalle te doen, want
wat jy kan kry dat 2 = 3, in daardie geval.
En ook baie versigtig wees oor voorrang.
Jy moet gewoonlik hakies gebruik om seker te wees dat jy weet wat jy doen.
'N paar nuttige kortpaaie, natuurlik, die een is i + + of i + = 1
of die gebruik van + =.
Dit is dieselfde ding as i = i + 1.
Jy kan dit ook doen - of i - = 1,
wat is die dieselfde ding as i = i -1,
iets wat jy ouens gebruik 'n lot in vir loops, ten minste.
Ook, vir *, as jy gebruik * = en as jy dit doen, byvoorbeeld,
i * = 2 is dieselfde ding gesê i = i * 2,
en dieselfde ding vir die afdeling.
As jy dit doen ek / = 2 dit is die dieselfde ding as i = i / 2.
>> Nou oor funksies.
Julle ouens het geleer dat funksies is 'n baie goeie strategie om die kode te red
terwyl jy programmering, so as jy wil om dieselfde taak te verrig
in die kode weer en weer, het jy waarskynlik wil 'n funksie te gebruik
net sodat jy hoef nie te kopieer en plak die kode oor en oor weer.
Eintlik, hoof is 'n funksie, en wanneer ek wys jou die formaat van 'n funksie
jy gaan om te sien dat dit redelik voor die hand liggend.
Ons gebruik ook funksies van sommige biblioteke,
byvoorbeeld, printf, getin, wat uit die CS50 biblioteek,
en ander funksies soos toupper.
Al daardie funksies is eintlik in ander biblioteke geïmplementeer,
en wanneer jy daardie ketting lêers in die begin van jou program
jy sê kan jy gee my asseblief die kode vir daardie funksies
so ek het nie om dit te implementeer deur myself?
En jy kan ook skryf jou eie funksies, so wanneer jy begin programmering
jy besef dat biblioteke nie al die funksies wat jy nodig het.
Vir die laaste pset, byvoorbeeld, het ons geskryf het trek, scramble en soek,
en dit is baie, baie belangrik om in staat te wees om funksies uit te skryf
want hulle is nuttig, en ons gebruik dit al die tyd in die programmering,
en dit slaan 'n klomp van die kode.
Die formaat van 'n funksie is hierdie een.
Ons het terugkeer soort in die begin. Wat is die terugkeer tipe?
Dis net wanneer jou funksie gaan om terug te keer.
As jy 'n funksie, byvoorbeeld, faktoriaal,
wat gaan om 'n produk van 'n heelgetal te bereken,
seker dit gaan 'n heelgetal ook terugkeer.
Dan die opbrengs soort gaan wees int.
Printf het eintlik 'n terugkeer tipe leemte
omdat jy nie terugkeer enigiets.
Jy net die druk van dinge op die skerm
en ophou die funksie daarna.
Dan moet jy die naam van die funksie wat jy kan kies.
Jy moet 'n bietjie redelike, soos nie kies 'n naam soos xyz
of soos x2f.
Probeer om te maak 'n naam wat sin maak.
>> Byvoorbeeld, as dit is faktoriaal, sê faktoriaal.
As dit is 'n funksie wat gaan om iets te skep, noem dit trek.
En dan het ons die parameters, wat ook genoem argumente,
wat is soos die hulpbronne wat u funksie behoeftes
van jou kode om sy taak uit te voer.
As jy wil die faktore van 'n getal te bereken
waarskynlik wat jy nodig het om 'n nommer te hê om 'n faktoriale te bereken.
Een van die argumente wat jy gaan te hê is die getal self.
En dan is dit gaan om iets te doen en die waarde aan die einde terugkeer
tensy dit is 'n leemte funksie.
Kom ons kyk 'n voorbeeld.
As ek wil 'n funksie te skryf wat al die getalle in 'n verskeidenheid van heelgetalle som,
Eerste van alles, is die terugkeer soort gaan wees int
want ek het 'n skikking van heelgetalle.
En dan gaan ek die funksie naam soos sumArray te hê,
en dan is dit gaan die skikking self te neem, tot int nume,
en dan is die lengte van die skikking, sodat ek weet hoeveel nommers Ek het op te som.
Dan het ek 'n veranderlike genoem som, byvoorbeeld, om 0 te inisialiseer,
en elke keer as ek sien 'n element in die skikking wat ek moet byvoeg om dit te som, so ek het 'n for-lus.
Net soos Lexi gesê het, jy doen int i = 0, i <lengte en i + +.
En vir elke element in die skikking het ek som + = nume [i],
en dan het ek die bedrag terug, so dit is baie eenvoudig, en dit spaar 'n baie van die kode
as jy die gebruik van hierdie funksie 'n baie van die tye.
Dan het ons 'n blik op die voorwaardes.
Ons het as anders, en anders as.
Kom ons kyk wat is die verskil tussen daardie.
Neem 'n blik op hierdie 2 kodes. Wat is die verskil tussen hulle?
Die eerste een is basies die kodes wil jou vertel
indien 'n nommer +, -, of 0.
Die eerste een sê as dit is> 0 dan is dit positief.
As dit is = tot 0, dan is dit is 0, en as dit is <0, dan is dit negatief.
>> En die ander een doen indien anders as anders.
Die verskil tussen die twee is dat hierdie een eintlik gaan
kyk of> 0 <0 of = 0 drie keer,
so as jy die getal 2, byvoorbeeld, is dit gaan om hier te kom en sê
if (x> 0), en dit gaan om te sê ja, so ek druk positief.
Maar alhoewel ek weet dat dit is> 0 en dit gaan nie wees 0 of <0
Ek nog steeds gaan om dit te doen is dit 0, is dit <0,
so ek is eintlik gaan binnekant van ifs dat ek nie hoef te
omdat ek reeds weet dat dit nie gaan om enige van hierdie voorwaardes te voldoen.
Ek kan gebruik om die as, anders as, anders verklaring.
Dit sê basies as x = 0 Ek druk die positiewe.
As dit is nie, ek gaan ook toets.
As dit is 2 nie ek gaan om dit te doen.
Basies as ek het x = 2 sou jy sê
if (x> 0), ja, so print hierdie.
Nou dat ek weet dat dit is> 0 en dat dit voldoen aan die eerste as
Ek is nie eens gaan hierdie kode uit te voer.
Die kode loop vinniger, eintlik, 3 keer vinniger as jy dit gebruik.
Ons het ook geleer het oor en of.
Ek gaan nie om te gaan deur middel van hierdie, want Lexi het reeds gepraat oor hulle.
Dit is net die && | | operateur.
>> Die enigste ding wat ek sal sê, is versigtig wees wanneer jy het 3 voorwaardes.
Gebruik hakies, want dit is baie verwarrend wanneer jy 'n toestand
en 'n ander een of die ander een.
Gebruik hakies net om seker te wees dat jou omstandighede sin maak
want in daardie geval, byvoorbeeld, kan jy dink dat
dit kan die eerste toestand en die een of ander
of die 2 voorwaardes gekombineer in 'n
of die derde een, so wees versigtig.
En laastens, het ons gepraat oor die skakelaars.
'N skakelaar is baie nuttig wanneer jy 'n veranderlike.
Kom ons sê dat jy het 'n veranderlike soos n
wat kan wees 0, 1 of 2, en vir elkeen van daardie gevalle
jy gaan om 'n taak uit te voer.
Jy kan sê skakel die veranderlike, en dit dui daarop dat
die waarde is dan soos waarde1 ek gaan om dit te doen,
en dan het ek breek, wat beteken ek gaan nie om te kyk na enige van die ander gevalle
omdat ons reeds tevrede is dat
en dan waarde2 en so aan, en ek kan ook 'n standaard skakel.
Dit beteken dat as dit nie enige van die gevalle wat ek moes voldoen
dat ek gaan om iets anders te doen, maar dit is opsioneel.
Dit is al wat vir my. Nou laat ons Tommy.
Alle reg, dit gaan Week 3-ish.
Dit is 'n paar van die onderwerpe wat ons sal bedek word, crypto, omvang, skikkings, ensovoorts.
Net 'n vinnige woord op crypto. Ons gaan nie hierdie huis te hamer.
>> Ons het dit in pset 2, maar vir die quiz maak seker dat jy weet wat die verskil
tussen die keiser cipher en die Vigenère cipher,
hoe beide van diegene getalle werk en wat dit is soos om te enkripteer
en dekripteer teks met behulp van dié 2 getalle.
Onthou, die keiser cipher draai net elke karakter met dieselfde bedrag,
maak seker dat jy mod deur die aantal letters in die alfabet.
En die Vigenère cipher, aan die ander kant, roteer elke karakter
deur 'n ander bedrag, so eerder as om te sê
elke karakter geroteer deur 3 Vigenère sal roteer elke karakter
deur 'n ander bedrag afhangend op 'n aantal navraag
waar elke letter in die sleutelwoord paar verskillende bedrag
die duidelike teks te draai.
Laat ons eers praat oor die veranderlike omvang.
Daar is 2 verskillende tipes van veranderlikes.
Ons plaaslike veranderlikes, en hierdie gaan word gedefinieer
buite van die hoof of buite enige funksie of blok,
en dit sal toeganklik wees op enige plek in jou program.
As jy 'n funksie en in daardie funksie is 'n while lus
die groot globale veranderlike toeganklik is oral.
'N plaaslike veranderlike, aan die ander kant, is scoped na die plek waar dit word gedefinieer.
>> As jy 'n funksie hier, byvoorbeeld, ons het hierdie funksie g,
en binnekant van g is daar is 'n veranderlike wat hier genoem y,
en dit beteken dat dit is 'n plaaslike veranderlike.
Selfs al is hierdie veranderlike genoem word y
en hierdie veranderlike is y van hierdie 2 funksies genoem
het geen idee wat mekaar se plaaslike veranderlikes is.
Aan die ander kant, hier is ons sê int x = 5,
en dit is buite die bestek van enige funksie.
Dit is buite die bestek van die belangrikste, so dit is 'n globale veranderlike.
Dit beteken dat die binnekant van hierdie 2 funksies toe ek sê x - of x + +
Ek toegang tot dieselfde x waardeur hierdie y en y is verskillende veranderlikes.
Dit is die verskil tussen 'n globale veranderlike en 'n plaaslike veranderlike.
So ver as wat ontwerp betref, soms is dit waarskynlik 'n beter idee
te hou veranderlikes plaaslike wanneer jy moontlik kan
sedert met 'n klomp van die globale veranderlikes kan kry regtig verwarrend.
As jy 'n klomp van die funksies die wysiging van die dieselfde ding
jy dalk vergeet wat as hierdie funksie per ongeluk verander hierdie globale,
en hierdie ander funksie nie weet nie,
en dit het 'n bietjie verwarrend as jy meer kode.
Hou veranderlikes plaaslike wanneer jy moontlik kan
is net goeie ontwerp.
Skikkings, onthou, is eenvoudig lyste van die elemente van dieselfde tipe.
Binnekant van CI kan nie 'n lys soos 1, 2,0, hello.
Ons kan net nie doen nie.
>> Wanneer ons 'n skikking in C verklaar al die elemente van dieselfde soort te wees.
Hier het ek het 'n skikking van 3 heelgetalle.
Hier het ek die lengte van die skikking, maar as ek net verklaar dat dit in hierdie sintaksis
waar ek spesifiseer wat al die elemente is ek tegnies hoef nie hierdie 3.
Die samesteller is slim genoeg om uit te vind hoe groot die skikking moet wees.
Nou wanneer ek wil kry of die waarde van 'n skikking
dit is die sintaksis om dit te doen.
Dit sal eintlik die tweede element van die skikking te verander, want, onthou,
nommering begin by 0, nie op 1.
As Ek wil hê dat die waarde te lees, ek kan iets sê soos: int x = array [1].
Of as ek wil hê dat die waarde te stel, soos ek hier doen,
Ek kan sê array [1] = 4.
Daardie tyd toegang tot die elemente deur die indeks
of hul posisie of waar hulle is in die skikking,
en dat die lys begin by 0.
Ons kan ook 'n skikkings van skikkings,
en dit is 'n multi-dimensionele skikking genoem.
Wanneer ons 'n multi-dimensionele skikking
wat beteken dat ons kan iets soos rye en kolomme,
en dit is net een manier van visualisering van hierdie of te dink oor dit.
As ek 'n multi-dimensionele skikking wat beteken dat ek gaan om te begin nodig
meer as 1 indeks want as ek het 'n rooster
sê maar net wat ry jy in gee ons nie 'n nommer.
Dit is net regtig gaan om te gee vir ons 'n lys van getalle.
Kom ons sê ek het hierdie skikking hier.
Ek het 'n skikking met die naam rooster, en ek sê dit is 2 rye en 3 kolomme,
en so dit is een manier om dit te visualiseer.
As ek sê ek wil hê dat die element te kry by [1] [2]
wat beteken dat omdat hierdie rye eerste en dan kolomme
Ek gaan om te spring 1 te roei, want ek het gesê 1.
>> Dan gaan ek om te kom oor hier om te kolom 2, en ek gaan na die waarde 6.
Sin maak?
Multi-dimensionele skikkings, onthou, is tegnies net 'n verskeidenheid van skikkings.
Ons kan skikkings van skikkings van skikkings.
Ons kan hou, maar regtig 'n manier om te dink oor
hoe dit word uitgelê en wat aangaan, is om dit te visualiseer
in 'n rooster soos hierdie.
Wanneer ons skikkings funksies slaag, gaan hulle om op te tree
'n bietjie anders as ons slaag van gereelde veranderlikes funksies
soos om 'n int of 'n float.
Wanneer ons in 'n int of char of enige van hierdie ander data tipes slaag
ons het net 'n blik op as die funksie verander
die waarde van die veranderlike wat verandering gaan nie te propageer
aan die roeping funksie.
Met 'n skikking, aan die ander kant, dit sal gebeur nie.
As ek in 'n skikking na 'n funksie en daardie funksie verander sommige van die elemente,
wanneer ek terug kom na die funksie wat dit genoem
my skikking nou gaan om anders te wees, en die woordeskat vir
is skikkings deur verwysing geslaag, soos ons later sal sien.
Dit is verwant aan hoe wysers werk, waar hierdie basiese datatipes,
aan die ander kant, word geslaag deur waarde.
>> Ons kan dink dat as die maak van 'n afskrif van 'n paar veranderlike en dan wat in die kopie.
Dit maak nie saak wat ons doen met daardie veranderlike.
Die roeping funksie sal nie bewus daarvan dat dit verander.
Skikkings is net 'n bietjie anders in dié verband.
Byvoorbeeld, as ons nou net gesien het, die vernaamste is eenvoudig 'n funksie
wat kan in 2 argumente.
Die eerste argument aan die hoofprogram is argc of die getal van argumente,
en die tweede argument genoem bevat SPASIES,
en dit is die werklike waardes van daardie argumente.
Kom ons sê ek het 'n program genaamd this.c,
en ek sê maak dit, en ek gaan om dit uit te voer op die command line.
Nou te slaag in sommige argumente na my program noem dit,
Ek kon iets sê / dit is cs 50.
Dit is wat ons dink om Dawid te doen elke dag by die terminale.
Maar nou is die hooffunksie binnekant van daardie program
het hierdie waardes, so argc is 4.
Dit kan 'n bietjie verwarrend, want regtig ons net verby is cs 50.
Dit is slegs 3.
Maar onthou dat die eerste element van bevat SPASIES of die eerste argument
is die naam van die funksie self.
So dit beteken dat ons het 4 dinge hier,
en die eerste element gaan wees /..
En dit sal verteenwoordig word as 'n string.
Toe het die oorblywende elemente is wat ons na die naam van die program getik in.
Dus, net soos 'n eenkant, as ons waarskynlik het in pset 2,
onthou dat die string 50 integer 50 ≠.
Ons kan dus nie sê iets soos, 'int x = bevat SPASIES 3. "
>> Dit is nie net gaan om sin te maak, want dit is 'n string, en dit is 'n heelgetal.
So as jy wil om te skakel tussen die 2, onthou, ons gaan
het hierdie magic funksie genoem atoi.
Wat 'n string en gee die heelgetal verteenwoordig binnekant van die string.
So dit is 'n maklike fout om te maak op die quiz,
net te dink wat hierdie sal automaties die korrekte tipe.
Maar net weet dat dit altyd sal wees snare
selfs indien die string bevat slegs 'n heelgetal of 'n karakter of 'n float.
So nou, laat ons praat oor die loop van tyd.
Wanneer ons al hierdie algoritmes wat al hierdie mal dinge doen nie,
is dit werklik nuttig om die vraag te vra: "Hoe lank neem hulle?"
Ons verklaar dat met iets genoem asimptotiese notasie.
So dit beteken dat - wel, laat ons sê dat ons gee ons algoritme
regtig, regtig, werklik 'n groot inset.
Ons wil die vraag te vra, "Hoe lank gaan dit neem?
Hoeveel stappe sal dit neem ons algoritme uit te voer
as 'n funksie van die grootte van die invoer? "
Dus is die eerste manier waarop ons kan hardloop tyd beskryf is met 'n groot O.
En dit is ons ergste-geval looptyd.
So as ons wil hê om 'n skikking te sorteer, en ons gee ons algoritme om 'n skikking
dit is in dalende volgorde wanneer dit moet in stygende volgorde,
wat gaan die ergste geval.
Dit is ons bogrens in die maksimum lengte van tyd om ons algoritme sal neem.
Aan die ander kant, is dit Ω gaan die beste geval looptyd te beskryf.
So as ons 'n reeds gesorteer skikking te sorteer algoritme,
hoe lank sal dit neem om dit uit te sorteer?
En dit, dan, beskryf 'n ondergrens op loop.
So hier is net 'n paar woorde wat beskryf 'n paar algemene loop tye.
Dit is in stygende orde.
Die vinnigste hardloop tyd het ons genoem word konstant.
>> Dit beteken dat maak nie saak hoe baie elemente wat ons gee ons algoritme,
maak nie saak hoe groot ons verskeidenheid, sorteer dit
of doen wat ons doen om die skikking sal altyd dieselfde bedrag van die tyd.
Sodat ons kan verklaar dat net met 'n 1, wat 'n konstante is.
Ons het ook gekyk na logaritmiese run tyd.
So iets soos binêre soek is in werklikheid logaritmies,
waar ons die probleem in die helfte van elke keer sny
en dan dinge net hoër kry van daar af.
En as jy ooit die skryf van 'n O van enige faktoriaal algoritme,
jy waarskynlik moet nie beskou dit as jou dag werk.
Wanneer ons hardloop tye is dit belangrik om in gedagte te hou hierdie dinge.
So as ek 'n algoritme wat is O (n), en iemand anders
het 'n algoritme O (2n) is dit eintlik asimptoties ekwivalent.
So as ons dink 'n groot aantal soos eleventy miljard N:
so wanneer ons vergelyk eleventy miljard tot iets soos eleventy miljard + 3,
skielik dat 3 het nie regtig 'n groot verskil maak nie.
Dit is hoekom ons gaan om te begin met die oorweging van hierdie dinge as gelykwaardig.
So dinge soos hierdie konstantes hier, daar is 2 x hierdie, of die toevoeging van 'n 3,
dit is net konstantes, en dit gaan te laat val.
So dit is waarom alle 3 van hierdie duur tye is dieselfde as om te sê hulle is O (n).
Net so, as ons het 2 ander duur tye, laat ons sê O (n + 2n ² ³), ons kan byvoeg
+ N + 7, en dan het ons nog 'n kans wat net O (n ³).
weer, dit is dieselfde ding, omdat dit - dit is nie dieselfde nie.
Dit is dieselfde dinge nie, jammer. So dit is dieselfde, want
hierdie n ³ gaan hierdie 2n ² te oorheers.
>> Wat is nie dieselfde ding is as ons loop tye soos O (n ³) en O (n ²)
omdat dit n ³ is veel groter as hierdie n ².
So as ons eksponente, skielik begin hierdie saak,
maar wanneer ons net doen het met faktore soos ons is hier,
dan is dit gaan nie saak nie, want hulle is net gaan om uit te sak.
Kom ons neem 'n blik op sommige van die algoritmes wat ons tot dusver gesien het
en praat oor hul duur tyd.
Die eerste manier van soek na 'n nommer in 'n lys, wat ons gesien het, was 'n lineêre soektog.
En die implementering van lineêre soek is super eenvoudige.
Ons het net 'n lys, en ons gaan om te kyk na elke enkele element in die lys
totdat vind ons die getal wat ons soek.
So dit beteken dat in die ergste geval, O (n).
En die ergste geval hier kan wees indien die element
die laaste element, dan met behulp van lineêre soek ons ​​het om te kyk na elke enkele element
totdat ons by die laaste een om te weet dat dit eintlik in die lys.
Ons kan nie net gee halfpad en sê, "Dit is waarskynlik nie daar nie."
Met lineêre soek ons ​​het om te kyk na die hele ding.
Die beste geval loop tyd, aan die ander kant, is konstant
want in die beste geval die element wat ons soek, is net die eerste een in die lys.
So dit gaan ons presies 1 stap, maak nie saak hoe groot die lys is te neem
as ons is op soek vir die eerste element elke keer.
>> So wanneer jy soek, onthou, is dit nie nodig dat ons lys gesorteer word.
Omdat ons net gaan om te kyk oor elke enkele element, en dit maak nie regtig saak
watter volgorde hierdie elemente is.
'N meer intelligente soek algoritme is iets soos binêre soek.
Onthou, die implementering van binêre soek is wanneer jy gaan
hou op soek na die middel van die lys.
En omdat ons is op soek na die middel, vereis ons dat die lys is gesorteer
of anders weet ons nie waar die middel is, en ons het om te kyk oor
die hele lys om dit te vind, en dan op daardie punt het ons is net tyd mors.
So as ons 'n gesorteerde lys en ons vind die middel, ons gaan om die middel te vergelyk
die element wat ons soek.
As dit is te hoog is, dan kan ons vergeet om die regte helfte
omdat ons weet dat as ons element is reeds te hoog
en alles wat aan die regterkant van hierdie element is selfs hoër,
dan moet ons nie om daar te kyk nie.
Waar op die ander kant, as ons element te laag is,
ons weet alles aan die linkerkant van daardie element is ook te laag is,
so dit maak nie regtig sin maak om daar te kyk, óf.
Op hierdie manier, met elke stap en elke keer as ons kyk na die middelpunt van die lys,
ons gaan om ons probleem op te sny in die helfte, want skielik ons ​​weet
'n hele klomp van die nommers wat nie kan die een wat ons soek.
>> In pseudokode sou dit lyk iets soos hierdie,
en omdat ons die lys te sny in die helfte van elke enkele tyd,
ons ergste geval run tyd spronge van lynvormig tot logaritmiese.
So skielik het ons log-in stappe in om 'n element in 'n lys te vind.
Die beste geval loop die tyd, al is, is steeds konstant
want nou, laat ons net sê dat die element wat ons is op soek na
altyd die presiese middel van die oorspronklike lys.
Sodat ons kan ons lys groei so groot soos ons wil, maar as die element wat ons soek is op die middel,
dan is dit net gaan ons 1 stap te neem.
So dit is waarom ons O (log n) en Ω (1) of konstant.
Laat eintlik loop binêre soek op hierdie lys.
So laat ons sê dat ons is op soek vir die element 164.
Die eerste ding wat ons gaan doen is om die middelpunt van hierdie lys.
Dit gebeur net so dat die middelpunt is gaan om te val in tussen dié 2 getalle,
so laat ons net arbitrêr sê, elke keer as die middelpunt tussen 2 nommers val,
laat ons net rond.
Ons het net nodig het om seker te maak ons ​​doen dit elke stap van die pad.
So ons gaan te rond, en ons gaan om te sê dat 161 is die middel van ons lys.
So 161 <164, en elke element aan die linkerkant van 161
is ook <164, sodat ons weet dat dit nie gaan ons almal help
om te begin soek hier omdat die element wat ons soek kan nie daar wees nie.
So wat ons kan doen, is ons net kan vergeet dat die hele linker helfte van die lys,
en nou net van die reg van die 161 verder oorweeg.
>> So weer, dit is die middelpunt, laat ons net rond.
Nou 175 is te groot.
So ons weet dat dit nie gaan om ons te help soek hier of hier,
sodat ons kan net gooi dit weg, en uiteindelik sal ons druk op die 164.
Enige vrae oor binêre soek?
Kom ons gaan soek deur middel van 'n reeds-gesorteerde lys
om werklik die neem van 'n lys van die nommers in enige volgorde
en die maak van die lys in stygende orde.
Die eerste algoritme het ons gekyk na borrel soort genoem.
En dit sou makliker wees van die algoritmes wat ons gesien het.
Bubble soort sê dat wanneer enige 2 elemente binne-in die lys is uit plek,
wat beteken daar is 'n hoër getal aan die linkerkant van 'n laer getal,
dan moet ons gaan om dit te ruil, want dit beteken dat die lys sal wees
"Meer gesorteer" as wat dit was voor.
En ons net gaan hierdie proses weer voortgaan en weer en weer
totdat uiteindelik die elemente soort van borrel aan hulle regte plek en ons het 'n gesorteerde lys.
>> Die aanloop tyd van hierdie gaan wees O (n ²). Hoekom?
Goed, want in die ergste geval, ons gaan elke element te neem, en
ons gaan aan die einde dit te vergelyk met elke ander element in die lys.
Maar in die beste geval, ons het 'n reeds gesorteerde lys, borrel soort
net gaan om te gaan deur middel van 'n keer, sê: "Nee, ek het nie enige swaps, so ek gedoen het."
So ons het 'n beste-geval looptyd van Ω (n).
Kom ons loop borrel soort op 'n lys.
Of die eerste, laat ons net kyk na sommige pseudokode regtig vinnig.
Ons wil sê ons wil dop te hou, in elke iterasie van die lus,
hou of ons nie enige elemente verander.
Dus is die rede hiervoor is dat, ons gaan om te stop as ons nie enige elemente verruil.
So aan die begin van ons loop ons nie omgeruil enigiets, so ons sal sê dit is vals.
Nou, ons gaan om te gaan deur die lys en element vergelyk i element i + 1
en indien dit die geval is dat daar 'n groter getal aan die linkerkant van 'n kleiner getal,
dan is ons net gaan om dit te ruil.
>> En dan gaan ons om te onthou dat ons 'n element verruil.
Dit beteken dat ons ten minste 1 meer tyd nodig het om te gaan deur die lys
want die toestand waarin ons gestop is wanneer die hele lys is reeds gesorteer is,
wat beteken dat ons nie gemaak het nie enige swaps.
So dit is waarom ons toestand hier onder is 'terwyl sommige elemente is omgeruil. "
So nou, laat ons net kyk na hierdie op 'n lys.
Ek het die lys 5,0,1,6,4.
Bubble soort gaan al die pad aan die linkerkant om te begin, en dit gaan om te vergelyk
die i-elemente, so 0 i + 1, wat is element 1.
Dit gaan om te sê, goed 5> 0, maar nou 5 is aan die linkerkant,
so ek moet die 5 en die 0 om te ruil.
Toe ek ruil hulle, skielik kry ek hierdie ander lys.
Nou 5> 1, dus gaan ons hulle te ruil.
5 is nie> 6, sodat ons nie nodig om iets hier te doen.
Maar 6> 4, sodat ons nodig het om te ruil.
Weereens, ons nodig het om te loop deur die hele lys om uiteindelik ontdek
dat dit buite werking is, ruil ons hulle,
en op hierdie punt het ons nodig het om te loop deur die lys 1 meer tyd
om seker te maak dat alles in sy einde, en op hierdie punt borrel soort klaar.
'N ander algoritme vir die neem van 'n paar elemente en sorteer hulle is seleksie soort.
Die idee agter die seleksie soort is dat ons gaan om te bou aan 'n gesorteer gedeelte van die lys
1 element op 'n slag.
>> En die manier waarop ons gaan om dit te doen is deur die opbou van die linker-segment van die lys.
En basies, almal op elke stap, ons gaan die kleinste element te neem, ons het alles verlaat
wat nie is nie gesorteer, en ons gaan om dit te skuif in daardie gesorteer segment.
Dit beteken dat ons nodig het om voortdurend te vind van die minimum ongesorteerde element
en dan neem dat die minimum element en ruil dit met alles wat
mees linkse element wat nie gesorteer.
Die loop van hierdie gaan wees O (n ²) want in die ergste geval
ons nodig het om elke enkele element te vergelyk met elke ander element.
Omdat ons sê dat as ons begin by die linker helfte van die lys, moet ons
om te gaan deur die hele reg segment die kleinste element te vind.
En dan, weer, het ons nodig het om te gaan oor die hele regte segment en
hou gaan oor wat oor en oor en oor weer.
Dit gaan n ². Ons gaan 'n nodig vir lus binnekant van 'n ander vir die lus
wat daarop dui dat n ².
In die beste geval gedagte, laat ons sê ons gee dit 'n reeds gesorteerde lys;
ons eintlik doen nie enige beter as n ².
Omdat seleksie soort het geen manier om te weet dat
die minimum element is net die een wat ek toevallig om te kyk na.
Dit moet nog om seker te maak dat dit eintlik die minimum.
>> En die enigste manier om seker te maak dat dit die minimum, die gebruik van hierdie algoritme,
is om te kyk na elke enkele element weer.
So regtig, as jy dit as jy gee seleksie soort 'n reeds gesorteerde lys,
dit is nie van plan om 'n beter doen as gee dit 'n lys wat nie nog gesorteer.
By the way, as dit gebeur om die geval te wees dat daar iets is O (iets)
en die omega van iets, kan ons net meer bondig dat dit is θ van iets sê.
So as jy sien wat kom nêrens, dit is wat dit beteken net.
>> As daar iets is theta van n ², dit is beide groot O (n ²) en Ω (n ²).
So die beste geval en die ergste geval, is dit nie 'n verskil maak,
die algoritme gaan om dieselfde ding te doen elke keer.
So dit is wat pseudokode vir die seleksie soort kan lyk.
Ons is basies gaan om te sê wat ek wil om die lys te itereer
van links na regs, en by elke iterasie van die lus, ek gaan om te beweeg
die minimum element in hierdie gesorteer gedeelte van die lys.
En nadat ek daar iets beweeg, ek het nooit nodig het om te kyk weer op daardie element.
Omdat so gou as ek ruil 'n element in die linker-segment van die lys, is dit gesorteer
want ons doen alles in stygende orde deur gebruik te maak van minimums.
Daarom het ons gesê, okay, ons is by posisie i, en wat ons nodig het om te kyk al die elemente
aan die regterkant van i ten einde die minimum te vind.
Dus beteken dit dat ons wil om te kyk vanaf i + 1 aan die einde van die lys.
En nou, as die element wat ons tans is op soek na minder is as ons minimum wat tot dusver,
wat, onthou, ons die begin van die minimum af om net te wees
element wat ons is tans op, Ek sal aanvaar wat is die minimum.
As ek 'n element wat is kleiner as dié, dan ek gaan om te sê, okay,
Wel, ek het 'n nuwe minimum.
Ek gaan om te onthou waar dat die minimum was.
>> So nou, nadat ek gegaan het deur daardie regte ongesorteerde segment,
Ek kan sê ek gaan die minimum element te ruil met die element wat in posisie i.
Dit gaan my lys te bou, my gesorteer gedeelte van die lys van links na regs,
en ons nooit nodig het om te kyk na 'n element weer dit is in daardie gedeelte.
Sodra ons het dit omgeruil.
So laat loop seleksie soort op hierdie lys.
Die blou element hier is gaan na die i te wees, en die rooi element gaan aan die minimum element.
, Sodat ek al die pad begin aan die linkerkant van die lys, so op 5.
Nou moet ons die minimum ongesorteerde element te vind.
So sê ons 0 <5 so, 0 is my nuwe minimum.
>> Maar ek kan nie daar stop nie, want selfs al het ons kan erken dat 0 is die kleinste,
ons nodig het om te loop deur elke ander element van die lys om seker te maak.
So 1 is groter, 6 is groter, 4 is groter.
Dit beteken dat, ek het na te kyk na al hierdie elemente bepaal 0 is die kleinste.
So ek gaan die 5 en die 0 om te ruil.
Sodra ek ruil dat ek gaan 'n nuwe lys te kry, en ek weet dat ek nooit nodig het om te kyk weer op dat 0
want as ek verruil dit, het ek gesorteer en wat ons gedoen het.
Nou is dit net so gebeur dat die blou element weer is die 5,
en ons moet kyk na die 1, 6 en die 4 om te bepaal dat 1
is die kleinste minimum element, so ons sal ruil die 1 en die 5.
Weereens, ons nodig het om na te kyk - vergelyk die 5 tot die 6 en die 4,
en ons gaan 4 en 5 ruil, en uiteindelik, vergelyk
dié 2 getalle en ruil hulle totdat ons kry ons gesorteerde lys.
Enige vrae oor die seleksie soort?
Okay. Kom ons beweeg na die laaste onderwerp hier, en dit is rekursie.
>> Rekursie, onthou, is dit regtig meta ding waar 'n funksie
herhaaldelik oproepe self.
So op 'n sekere punt, terwyl ons fuction herhaaldelik roep self,
daar moet na 'n punt waar ons ophou vra onsself te wees.
Want as ons dit nie doen nie, dan is ons net gaan om voort te gaan om vir ewig te doen,
en ons program is nie net gaan om te beëindig.
Ons noem hierdie toestand die basis geval.
En die basis geval sê, eerder as die roep van 'n funksie weer,
Ek gaan net 'n bietjie waarde om terug te keer.
So wanneer ons 'n waarde het teruggekeer, het ons gestop roeping onsself,
en die res van die oproepe wat ons tot dusver gedoen kan ook terugkeer.
Die teenoorgestelde van die basis-geval is die rekursiewe geval.
En dit is wanneer ons wil nog 'n oproep te maak na die funksie wat ons tans is.
En ons waarskynlik, maar nie altyd nie, wil verskillende argumente te gebruik.
>> So as ons 'n funksie genoem f en f genoem 1 argument,
en ons hou net roep f (1), f (1), f (1), en dit net so gebeur dat
val die argument 1 in rekursiewe geval, ons nog nooit gaan om te stop.
Selfs as ons het 'n basis geval, ons nodig het om seker te maak dat ons uiteindelik gaan daardie basis geval te tref.
Ons nie net hou verblyf in hierdie rekursiewe geval.
In die algemeen, wanneer ons noem onsself, ons waarskynlik gaan om elke keer 'n ander argument.
Hier is 'n baie eenvoudige rekursiewe funksie.
So dit sal bereken die faktore van 'n getal.
Tot bo ons het ons basis geval.
In die geval dat n ≤ 1, het ons nie gaan om te bel faktoriaal weer.
Ons gaan om te stop, ons gaan net 'n bietjie waarde om terug te keer.
As dit nie waar is nie, dan is ons gaan ons rekursiewe saak te tref.
Kennisgewing hier dat ons net nie bel faktoriaal (n), want dit sou nie baie nuttig wees.
Ons gaan faktoriaal van iets anders om te bel.
>> En sodat jy kan sien, uiteindelik as ons verby 'n faktoriaal (5) of iets,
ons gaan om te bel faktoriaal (4) en so aan, en uiteindelik het ons gaan hierdie basis saak te tref.
So, dit lyk goed. Kom ons kyk wat gebeur wanneer ons werklik hierdie hardloop.
Dit is die stapel, en laat ons sê dat die hoof gaan om hierdie funksie te roep met 'n argument (4).
So een keer faktoriaal sien en = 4, faktoriaal self sal roep.
Nou, skielik, het ons faktoriaal (3).
So hierdie funksies gaan om aan te hou groei totdat ons uiteindelik ons ​​basis geval getref.
Op hierdie punt, die terugkeer waarde van hierdie is die terugkeer (NX die terugkeer waarde van hierdie),
die terugkeer waarde van hierdie is nx die terugkeer waarde van hierdie.
Uiteindelik moet ons n nommer om te tref.
Op die top hier, sê ons terugkeer 1.
Dit beteken dat wanneer ons terugkeer dat die getal, ons kan pop van die stapel af.
So hierdie faktoriaal (1) gedoen word.
Wanneer 1 opgawes, faktoriaal (1) opgawes, hierdie terugkeer na 1.
Die opbrengs waarde van hierdie, onthou, was nx die terugkeer waarde van hierdie.
So skielik, hierdie ou weet wat ek wil om terug te keer 2.
>> So onthou, terugkeer waarde van hierdie is net nx die terugkeer waarde hier.
So ons kan nou sê 3 x 2, en uiteindelik, hier kan ons sê
dit is net gaan wees 4 x 3 x 2.
En sodra hierdie opbrengste, kry ons af na 'n heelgetal binnekant van die belangrikste.
Enige vrae oor die rekursie?
Alles reg. So daar is meer tyd vir vrae aan die einde,
maar nou Josef gaan die oorblywende onderwerpe dek.
>> [Joseph Ong] Alle regte. So nou dat ons het gepraat oor recursions,
Kom ons praat 'n bietjie oor wat saamsmelt soort is.
Merge soort is basies 'n ander manier om 'n lys van getalle te sorteer.
En hoe dit werk is, met merge soort het jy 'n lys, en wat ons doen is
ons sê, laat ons verdeel dit in 2 helftes.
Ons sal eers hardloop saamsmelt soort weer op die linker helfte,
dan sal ons hardloop saam te smelt soort op die regter helfte,
en dit gee ons nou 2 helftes wat gesorteer word, en nou is ons gaan die helftes aan mekaar te kombineer.
Dit is 'n bietjie moeilik om te sien sonder 'n voorbeeld, so ons sal gaan deur die mosies en kyk wat gebeur.
So jy begin met hierdie lys, ons verdeel dit in 2 helftes.
Ons loop saamsmelt soort op die linker helfte.
So dit is die linker helfte, en nou hardloop hulle weer deur hierdie lys
wat geslaag het in merge soort kry, en dan kyk ons ​​weer,
aan die linkerkant van hierdie lys en ons hardloop saamsmelt soort op dit.
Nou, kry ons af na 'n lys van 2 getalle,
en nou die linker helfte is net 1 element lank, en ons kan nie
verdeel 'n lys is net 1 element in die helfte, sodat ons net sê, wanneer ons 50,
wat is net 1 element, is dit reeds gesorteer.
>> Sodra ons klaar is met dit, kan ons sien wat ons kan
skuif op na die regter helfte van hierdie lys,
en 3 is ook gesorteer, en so nou dat beide helftes van hierdie lys is gesorteer
kan ons aansluit by hierdie getalle weer saam.
So ons sien op 50 en 3; 3 is kleiner as 50, so gaan dit in die eerste en dan 50 kom.
Nou, dit gedoen, ons gaan terug na die lys en sorteer dit reg is 1/2.
42 is se eie nommer, so dit is reeds gesorteer.
So nou het ons vergelyk hierdie 2 en 3 is kleiner as 42, so wat kry in die eerste,
nou 42 kry in, en 50 kry sit.
Nou, dit is gesorteer, ons gaan al die pad terug na die top, 1337 en 15.
Wel, ons nou kyk na die linker helfte van hierdie lys, 1337 is op sigself so dit is gesorteer en dieselfde met 15.
So nou het ons kombineer hierdie 2 nommers dat die oorspronklike lys, 15 <1337 te sorteer,
so gaan dit in die eerste, dan 1337 gaan.
En nou het ons beide helftes van die oorspronklike lys gesorteer tot bo.
En al wat ons hoef te doen is kombineer.
Ons kyk na die eerste 2 nommers van hierdie lys, 3 <15, so gaan dit maar eers in die soort skikking.
15 <42, so dit gaan. Nou, 42 <1337, wat gaan.
50 <1337, so dit gaan. En let dat ons net het 2 nommers van hierdie lys af.
Sodat ons nie net afwisselend tussen die 2 lyste.
Ons is net op soek aan die begin, en ons neem die element
dit is kleiner en dan om dit in ons verskeidenheid.
Nou het ons al die helftes saamgevoeg en wat ons gedoen het.
>> Enige vrae oor saamsmelt soort? Ja?
[Studente] As dit is te verdeel in verskillende groepe, hoekom doen hulle nie net verdeel dit weer
en jy het 3 en 2 in 'n groep? [Res van die vraag onverstaanbaar]
Die rede - so die vraag is, waarom kan ons nie net saam te smelt hulle op daardie eerste stap nadat ons hulle?
Die rede waarom ons dit kan doen, begin by die mees linkse elemente van beide kante,
en dan die kleiner een en sit dit in, is dat ons weet dat hierdie
individuele lyste is in gesorteer bestellings.
So as ek is op soek na die mees linkse elemente van beide helftes,
Ek weet hulle gaan wees die kleinste elemente van die lyste.
Sodat ek kan sit dit in die kleinste element plekke van hierdie groot lys.
Aan die ander kant, as ek kyk na die 2 lyste in die tweede vlak daar,
50, 3, 42, 1337 en 15, word diegene wat nie gesorteer.
So as ek kyk, ek gaan op 50 en 1337 50 in my lys te sit.
Maar dit beteken nie regtig sin maak nie, want 3 is die kleinste element uit van al diegene.
Dus is die enigste rede waarom ons kan dit kombineer stap doen, is omdat ons lyste is reeds gesorteer.
Wat is die rede waarom ons het al die pad om te kry af na die bodem
want as ons het net 'n enkele getal, jy weet dat 'n aantal
in en van die self is reeds 'n gesorteerde lys.
>> Enige vrae? Nie?
Complexity? Wel, kan jy sien dat daar by elke stap is einde getalle,
en ons kan 'n lys in die helfte log n keer verdeel,
wat is waar ons hierdie n x log n kompleksiteit.
En jy sal sien die beste geval vir merge soort is n log n, en dit net so gebeur
dat die ergste geval, of die Ω daar is ook 'n teken n.
Iets om in gedagte te hou.
Beweeg op, laat ons gaan op 'n paar super basiese lêer I / O.
As jy kyk na Scramble, sal jy sien ons het 'n soort van die stelsel
waar jy kan skryf aan 'n log-lêer as jy lees deur middel van die kode.
Kom ons kyk hoe jy kan doen.
Wel, ons het fprintf, wat jy kan dink net so printf,
maar net die druk na 'n lêer plaas en vandaar die f aan die begin.
Hierdie soort van die kode hier, wat dit doen is, as jy dalk gesien het in Scramble,
dit gaan deur jou 2-dimensionele skikking druk uit ry deur ry wat die getalle is.
In hierdie geval, druk printf uit na jou terminale of wat ons noem die standaard uitset van artikel.
>> En nou, in hierdie geval, al wat ons hoef te doen is vervang printf met fprintf,
vertel watter lêer wat jy wil uit te druk, en in hierdie geval is dit net hou dit uit na daardie lêer
in plaas van druk dit uit na jou terminale.
Wel, dan is dit lei tot die vraag: Waar kry ons hierdie soort van die lêer uit, reg?
Ons geslaag Teken in op hierdie fprintf fuction, maar ons het geen idee waar dit vandaan kom.
Wel, vroeg in die kode, wat ons gehad het, was hierdie stuk van die kode hier,
wat sê basies dat open die lêer noem log.txt.
Wat ons doen, na wat ons het om seker te maak dat die lêer is eintlik suksesvol oopgemaak.
Sodat dit dalk nie vir verskeie redes, jy het nie genoeg spasie op jou rekenaar, byvoorbeeld.
So dit is altyd belangrik om voordat jy enige bewerkings met die lêer
dat ons kontroleer of dat die lêer is suksesvol oopgemaak.
So, wat dat 'n, dit is 'n argument te fopen, goed, kan ons 'n lêer oopmaak in baie maniere.
Wat is ons kan doen, kan ons dit slaag w, wat beteken ignoreer die lêer as dit uitgaan reeds,
Ons kan 'n 'n slaag, wat hulle voeg aan die einde van die lêer in plaas van groot,
of ons kan spesifiseer r, wat beteken, laat ons die lêer as lees-alleen oop.
Dus, as die program probeer om enige veranderinge aan te bring na die lêer,
skreeu hulle en moenie toelaat dat hulle dit doen.
Ten slotte, wanneer ons klaar is met die lêer gedoen doen bedrywighede op dit,
ons nodig het om seker te maak ons ​​maak die lêer.
En so aan die einde van jou program, jy gaan hulle weer slaag
hierdie lêer wat jy oopgemaak het, en sluit dit net.
Sodat dit is iets belangrik wat jy het om seker te maak jy doen.
Onthou So kan jy 'n lêer oop te maak, dan kan jy skryf na die lêer,
bedrywighede in die lêer doen, maar dan moet jy die lêer te sluit aan die einde.
>> Enige vrae oor die basiese lêer I / O? Ja?
[Student vraag, onverstaanbaar]
Reg hier. Die vraag is, waar hierdie log.txt lêer verskyn?
Wel, as jy net gee dit log.txt, dit skep dit in dieselfde gids as die uitvoer.
So as jy's - >> [Student vraag, onverstaanbaar]
Ja. In dieselfde lêergids, of in dieselfde gids, soos jy dit noem.
Nou geheue, stapel, en hoop.
So hoe is geheue uitgelê in die rekenaar?
Wel, kan jy jou indink geheue as 'n soort van die blok hier.
En ons het in die geheue wat die hoop vas daar, en die stapel wat daar genoem word.
En die hoop groei afwaarts en die stapel groei opwaarts.
So as Tommy genoem - O, goed, en ons het die ander 4 segmente wat ek sal kry om in 'n tweede -
Soos Tommy vroeër gesê het, jy weet hoe om sy werksaamhede noem hulself en noem mekaar?
Hulle bou hierdie soort van stapel.
Wel, as hoof oproepe cat, cat kry op die stapel geplaas.
Foo noem bar, bar kry ons sit op die stapel, en wat kry op die stapel geplaas nadat.
En as hulle terugkeer, het hulle elke geneem kry die stapel af.
Wat hou elkeen van hierdie plekke en geheue?
Wel, die top, wat is die teks segment, bevat die program self.
Sodat die masjien kode, wat is daar, wanneer jy jou program saamstel.
Volgende, 'n globale veranderlikes geïnisialiseer.
>> So jy het globale veranderlikes in jou program, en jy sê soos, a = 5,
wat kry in daardie segment, en reg onder,
u enige geïnitialiseerd globale data, wat net 'n int,
maar jy sê nie dit is gelyk aan enigiets nie.
Besef dat hierdie globale veranderlikes, sodat hulle is buite van die belangrikste.
Dus beteken dit 'n globale veranderlikes wat verklaar word, maar is nie geïnisialiseer nie.
So, wat is in die hoop? Geheue geallokeer deur malloc, wat ons sal kry in 'n bietjie.
En uiteindelik, met die stapel moet jy 'n plaaslike veranderlikes
en enige funksies wat jy kan noem in enige van hul parameters.
Die laaste ding wat jy nie regtig het om te weet wat die omgewing veranderlikes doen,
maar wanneer jy hardloop program, daar is iets wat verband hou, soos
dit is die gebruikersnaam van die persoon wat die program hardloop.
En wat gaan soort van aan die onderkant.
In terme van die geheue adresse, wat is hexadecimale waardes,
die waardes op die top begin by 0, en hulle gaan al die pad af na die bodem.
In hierdie geval, as jy op die 32-bis-stelsel,
die adres op die bodem gaan wees 0x, gevolg deur af, want dit is 32 stukkies,
wat is 8 grepe, en in hierdie geval 8 bytes ooreenstem met 8 hexadecimalen.
So af hier jy gaan hê, wil, 0xffffff, en daar het jy gaan om 0 te hê.
So, wat is verwysings? Sommige van julle mag nie gedek het hierdie artikel voor.
maar ons het gaan oor dit in die lesing, so 'n wyser is net 'n datatipe
watter winkels, in plaas van 'n soort van waarde soos 50, is dit die adres van n plek in die geheue stoor.
Soos dat "memory" [onverstaanbaar].
Dus, in hierdie geval, wat ons is, ons het 'n wyser na 'n heelgetal of 'n int *,
en dit bevat hierdie heksadesimale adres van 0xDEADBEEF.
>> So, wat ons het is nou, wyser punte op 'n sekere plek in die geheue,
en dat net 'n, die waarde 50 is op hierdie geheue plek.
Op sommige 32-bits stelsels, op alle 32-bis-stelsels, wysers neem 32 stukkies of 4 grepe.
Maar, byvoorbeeld, op 'n 64-bis-stelsel, wysers is 64 bisse.
So dit is iets wat jy sal wil hê om in gedagte te hou.
So op 'n end-bis-stelsel, 'n wyser is einde stukkies lank.
Pointers is soort van moeilik om te verteer sonder ekstra dinge,
so laat ons gaan deur middel van 'n voorbeeld van dinamiese geheuetoekenning.
Wat dinamiese geheuetoekenning vir jou doen, of wat ons noem malloc,
dit kan jy 'n soort van data buite die stel ken.
So hierdie data is 'n soort van meer permanente werk vir die duur van die program.
Want soos jy weet, as jy verklaar x binnekant van 'n funksie, en dat die funksie opbrengste,
hoef jy nie meer toegang tot die data wat wat in x gestoor is.
Wat pointers laat ons doen, is hulle laat ons geheue of winkel waardes stoor
in 'n ander segment van die geheue, naamlik die hoop.
Nou wanneer ons terugkom van die funksie, so lank as wat ons 'n wyser
na die plek in die geheue, dan is wat ons kan doen is kan ons net kyk na die waardes daar.
Kom ons kyk na 'n voorbeeld: Dit is ons geheue uitleg weer.
En ons het hierdie funksie, hoof.
Wat beteken dit is okay, so eenvoudig, reg? Int x = 5, dit is net 'n veranderlike op die stapel in die hoof.
>> Aan die ander kant, nou het ons 'n wyser wat noem die funksie giveMeThreeInts verklaar.
En so nou gaan ons in hierdie funksie en skep ons 'n nuwe stapel raam vir dit.
Maar, in hierdie stapel raam, verklaar ons int * temp,
wat in mallocs 3 heelgetalle vir ons.
So grootte van int sal ons hoeveel bytes hierdie int is,
en malloc gee ons dat baie grepe van die ruimte op die hoop.
Dus, in hierdie geval, het ons genoeg ruimte vir 3 heelgetalle,
en die hoop is daar, wat is die rede waarom ek geteken het dit hoër op.
Sodra ons gedoen het, is ons terug kom hier, jy hoef net 3 ints teruggekeer,
en dit gee die adres, in hierdie geval oor waar daardie geheue is.
En ons het pointer = skakelaar, en daar het ons net nog wyser.
Maar wat daardie funksie opbrengste is hier gestapel en verdwyn.
So temp verdwyn, maar ons het nog steeds die adres van waar
daardie 3 heelgetalle is binnekant van die hoofleiding.
So in hierdie reeks, die wysers scoped plaaslik vir die gestapel raam,
maar die geheue waarop dit betrekking het, is in die hoop.
>> Maak dit sin?
[Studente] Kan jy dit herhaal? >> [Joseph] Ja.
So as ek net 'n bietjie terug gaan, sien jy dat temp toegeken
n geheue op die hoop daar.
So wanneer hierdie funksie, giveMeThreeInts opbrengste, hierdie stapel hier gaan om te verdwyn.
En met dit enige van die veranderlikes, in hierdie geval, is dit wyser wat in gestapel raam toegeken is.
Wat gaan verdwyn nie, maar omdat ons teruggekeer temp
en ons wyser = temp, pointer nou gaan dieselfde geheue van die plek as die temp was om te wys.
So nou, selfs al het ons verloor temp, dat die plaaslike pointer,
ons nog steeds die geheue adres van die wat dit wys na die binnekant van daardie veranderlike wyser.
Vrae? Dit soort van 'n verwarrende onderwerp kan wees as julle nie gegaan het oor dit in artikel.
Ons kan jou TF, sal beslis gaan oor dit en natuurlik het ons vrae kan beantwoord
aan die einde van die hersiening sessie vir hierdie.
Maar dit is 'n soort van 'n komplekse onderwerp, en ek het meer voorbeelde wat gaan om te wys
wat jou sal help om te verduidelik wat pointers eintlik.
>> In hierdie geval, wysers is gelykstaande aan skikkings,
so ek kan net gebruik om die wyser as die dieselfde ding as 'n int skikking.
So ek kruip in 0, en die verandering van die eerste heelgetal 1,
die verandering van die tweede heelgetal 2, en die 3de heelgetal tot 3.
Sodat meer wenke. Wel, Binky onthou.
In hierdie geval het ons 'n wyser toegeken, of ons 'n wyser verklaar,
maar aanvanklik, toe ek net 'n wyser verklaar, is dit nie verwys na enige plek in die geheue.
Dis net vullis waardes binnekant van dit.
So ek het geen idee waar die wyser wys.
Dit het 'n adres wat net gevul met 0 en 1 se waar dit aanvanklik verklaar.
Ek kan niks doen met hierdie totdat ek noem malloc op dit
en dan gee dit vir my 'n bietjie ruimte op die hoop waar ek kan sit waardes binne.
Dan weer, ek weet nie wat is binnekant van die geheue.
Dus is die eerste ding wat ek hoef te doen, is kontroleer of die stelsel het genoeg geheue
gee my terug 1 heelgetal in die eerste plek, wat is die rede waarom ek om dit te doen gaan.
As wyser is van nul, wat beteken dat dit nie genoeg spasie of 'n ander fout het voorgekom,
so ek moet uitgang uit my program.
Maar as dit onsuksesvol was, nou kan ek gebruik dat wyser
en wat * pointer doen is dit volg waar die adres is
waar daardie waarde is, en dit stel dit gelyk aan 1.
So hier is ons nagaan indien daardie geheue bestaan.
>> Sodra jy weet dit bestaan, kan jy sit in dit
watter waarde wat jy wil om dit te sit in, in hierdie geval 1.
Sodra ons klaar is met dit wat jy nodig het dat pointer te bevry
want ons moet terug te kry om die stelsel wat die geheue wat jy in die eerste plek gevra vir.
Omdat die rekenaar weet nie wanneer ons klaar is met dit.
In hierdie geval het ons dit uitdruklik sê, okay, ons is gedoen met daardie geheue.
Indien 'n ander proses moet dit 'n ander program dit nodig het, voel vry om voort te gaan en neem dit.
Wat kan ons ook doen, ons kan net die adres van die plaaslike veranderlikes op die stel.
So int x is die binnekant van die gestapel raam van die belangrikste.
En wanneer ons hierdie ampersand, en operateur, wat dit doen, is
dit neem x en x is net 'n paar data in die geheue, maar dit het 'n adres.
Dit is iewers geleë is. So deur te bel & x, wat dit doen, is dit gee ons die adres van x.
Deur dit te doen, is ons wyser punt waar x is in die geheue.
Nou het ons net nie iets soos * x, ons gaan 5 terug te kry.
Die ster word genoem ontwysing dit.
Jy volg die adres en jy kry die waarde van dit wat daar gestoor word.
>> Enige vrae? Ja?
[Studente] As jy nie die 3-puntige ding doen, dit maak nog steeds stel?
Ja. As jy nie die 3-pointer ding doen, dit is nog steeds gaan om te stel,
maar Ek sal julle wys wat gebeur in 'n tweede, en sonder om dit te doen,
Dit is wat ons noem 'n geheugenlek. Jy nie die stelsel
terug sy geheue, so na 'n ruk die program gaan ophoop
geheue wat dit nie gebruik, en niks anders kan dit gebruik.
As jy al ooit gesien Firefox met 1,5 miljoen kilogrepe op jou rekenaar,
in die 'task manager, dit is wat gaan aan.
Jy het 'n geheugenlek in die program dat hulle nie die hantering van.
So hoe wyser rekenkundige werk?
Wel, pointer rekenkunde is soort van soos kruip in 'n skikking.
In hierdie geval, ek het 'n wyser, en wat ek doen is ek maak wyser punt na die eerste element
van hierdie verskeidenheid van 3 heelgetalle wat ek toegeken.
So nou wat ek doen, ster wyser verander net die eerste element in die lys.
Star pointer 1 punte hier.
So wyser is hier, pointer 1 is hier, pointer 2 is hier.
>> So voeg net 1 is dieselfde ding as die beweeg langs hierdie skikking.
Wat ons doen is, wanneer ons wyser 1 doen jy kry die adres hier,
en ten einde die waarde in hier te kry, moet jy 'n ster van die hele uitdrukking
om dit te dereference.
Dus, in hierdie geval, ek die opstel van die eerste plek in die skikking 1,
tweede plek 2 en derde plek tot 3.
Dan wat ek doen hier, is ek ons ​​wyser 1 is druk,
wat gee my net 2.
Nou is ek verhoog van pointer, so wyser gelyk aan pointer 1,
wat beweeg dit vorentoe.
En so nou as ek druk pointer 1, pointer 1 is nou 3,
wat in hierdie geval druk uit 3.
En om te vry iets, die wyser dat ek dit gee
moet dui op die begin van die skikking wat ek terug gekom van malloc.
So, in hierdie geval, as ek was 3 hier noem, sou dit nie reg wees,
want dit is in die middel van die skikking.
Ek het af te trek om te kry na die oorspronklike plek
die aanvanklike eerste plek voor ek dit kan bevry.
So, hier is 'n meer betrokke voorbeeld.
In hierdie geval, is ons die toekenning van 7 karakters in 'n karakter skikking.
>> En in hierdie geval wat ons doen is ons herhaling oor die eerste 6 van hulle,
en ons hulle tot Z.
So, int i = 0, i> 6, i + +,
So, pointer + ek sal net gee ons, in hierdie geval,
pointer pointer 1, pointer 2 3 pointer, en so aan en so voort in die lus.
Hoe dit gaan om te doen, is dit kry die adres, dereferences dit die waarde te kry,
en veranderings wat waarde tot 'n Z.
Dan aan die einde onthou dit is 'n string, reg?
Alle stringe om te eindig met die null beëindiging van karakter.
So, wat ek doen is in pointer 6 Ek het die null-terminator karakter.
En nou wat ek basies is besig hier printf implementering vir 'n string, reg?
>> So, printf toe nou dat dit die einde van 'n string bereik?
Wanneer dit treffers die null beëindiging karakter.
So, in hierdie geval, my oorspronklike wyser punte aan die begin van hierdie verskeidenheid.
Druk ek die eerste karakter uit. Ek beweeg dit oor een.
Ek druk die karakter uit. Ek skuif dit oor.
En ek hou om dit te doen totdat ek die einde bereik.
En nou sal die einde * wyser dereference en terug kry die null beëindiging van karakter.
En so het my while lus loop slegs wanneer daardie waarde is nie die null beëindiging van karakter.
So, nou het ek uitgang uit van die lus.
En so, as ek aftrek 6 van hierdie pointer,
Ek gaan al die pad na die begin terug.
Onthou, ek is om dit te doen, want ek het om te gaan na die begin om dit te bevry.
>> So, ek weet dit was 'n baie. Is daar enige vrae?
Asseblief, ja?
[Student vraag onverstaanbaar]
Kan jy sê dat harder? Jammer.
[Studente] Op die laaste slide reg voordat jy die wyser bevry,
waar jy was eintlik die verandering van die waarde van die wyser?
[Joseph] So, net hier. >> [Studente] O, okay.
[Josef] Dus, het ek 'n wyser minus minus, reg,
wat die ding terug een beweeg, en dan sal ek vry om dit,
omdat hierdie wyser gewys moet word aan die begin van die skikking.
[Studente] Maar dit sal nie nodig wees het jy gestop na daardie lyn.
[Joseph] Dus, as ek opgehou het na hierdie, sou dit oorweeg word om 'n geheugenlek,
want ek het nie die vrye loop.
[Studente] I [onverstaanbaar] na die eerste drie reëls waar jy moes pointer 1 [onverstaanbaar].
[Josef] Uh-huh. So, wat is die vraag daar?
Jammer. Nee, nee. Gaan, gaan, asseblief.
[Studente] So, is jy nie die verandering van die waarde van wysers.
Jy nie sou gehad het nie pointer minus minus te doen.
[Joseph] Ja, presies.
So, wanneer ek dit doen pointer 1 en 2 pointer,
Ek doen wyser gelyk aan pointer 1.
So, die wyser is net bly dui op die begin van die skikking.
Dit is eers wanneer ek doen plus plus dat dit stel die waarde terug binne-in die wyser,
dat dit beweeg eintlik dit saam.
Alles reg.
Nog vrae?
>> Weereens, as dit is 'n soort van die oorweldigende, sal hierdie gedek word in die sessie.
Vra jou onderrig mede oor dit, en ons vrae kan beantwoord aan die einde.
En gewoonlik ons ​​nie hou nie hierdie minus ding om te doen.
Dit het my voor om te vereis dat die dop van hoe baie ek het in die skikking geneutraliseer.
So, in die algemeen, is dit net om hoe wyser rekenkundige werk te verduidelik.
Maar wat ons gewoonlik nie hou om dit te doen, is ons graag 'n afskrif van die wyser te skep,
en dan sal ons daardie afskrif gebruik wanneer ons rond te beweeg in die tou.
So, in hierdie geval gebruik jy die kopie die hele string te druk,
maar ons het nie te doen soos wyser minus 6 of hou van hoeveel het ons verhuis in hierdie,
net omdat ons weet dat ons oorspronklike punt is nog steeds wys na die begin van die lys
en alles wat ons verander het, was hierdie kopie.
So, in die algemeen, te verander afskrifte van jou oorspronklike wyser.
Moenie probeer om soort van soos - moenie verander oorspronklike kopieë.
Probeer net afskrifte van jou oorspronklike te verander.
So, jy sien wanneer ons slaag die tou in printf
jy hoef nie 'n ster te sit in die voorkant van dit, soos ons gedoen het met al die ander dereferences, reg?
Dus, as jy druk die hele string% s verwag is 'n adres,
en in hierdie geval 'n wyser of in hierdie geval soos 'n verskeidenheid van die karakters.
>> Karakters, char * s, en skikkings is dieselfde ding.
Pointer is om karakters, en karakter skikkings is dieselfde ding.
En so, is al wat ons het om te doen slaag in die wyser.
Ons hoef nie te slaag soos * wyser of iets soos dit.
So, skikkings en wysers is dieselfde ding.
Wanneer jy iets doen soos x [y] hier vir 'n skikking,
wat dit doen onder die enjinkap is dit sê, goed, dit is 'n karakter skikking,
dit is so 'n wyser.
En so x is dieselfde ding,
en so wat dit doen nie, is dit voeg y x,
wat is die dieselfde ding as om vorentoe te beweeg in die geheue dat daar nog baie.
En nou x + y gee ons 'n soort van adres,
en ons dereference die adres of volg die pyl
na die plek waar daardie plek in die geheue is en ons kry die waarde van daardie plek in die geheue.
So, so die twee is presies dieselfde ding.
Dit is net 'n sintaktiese suiker.
Hulle doen dieselfde ding. Hulle is net verskillende syntactics vir mekaar.
>> So, wat kan verkeerd gaan met verwysings? Soos, 'n lot. Okay. So, slegte dinge.
'N paar slegte dinge wat jy kan doen nie kontroleer as jou malloc oproep terug null, reg?
In hierdie geval, ek vra die stelsel om my te gee - Wat is die getal?
Soos 2 miljard keer 4, omdat die grootte van 'n heelgetal is 4 grepe.
Ek vra dit vir soos 8 miljard grepe.
Natuurlik my rekenaar is nie van plan om in staat wees om te gee vir my dat 'n groot geheue terug.
En ons het nie kontroleer of dit is van nul, so wanneer ons probeer om dit daar te dereference -
volg die pyl na die plek waar dit gaan - ons het nie dat die geheue.
Dit is wat ons noem ontwysing 'n null-aanwijzer.
En dit veroorsaak hoofsaaklik om jou te segfault.
Dit is een van die maniere waarop jy kan segfault.
Ander slegte dinge wat jy kan doen - oh well.
Null pointer is ontwysing. Okay.
Ander slegte dinge - goed, op te los dat jy net 'n tjek daar
wat nagaan of die wyser is null
en uitgang uit die program as dit gebeur dat malloc terugkeer 'n null pointer.
Dit is die Kletskerk komiese. Mense verstaan ​​dit nou. Soort van.
>> So, geheue. En ek het oor hierdie.
Ons vra malloc in 'n lus, maar elke keer as ons 'n beroep malloc
ons verloor spoor van waar die wyser wys,
omdat ons beuken.
So, die aanvanklike oproep tot malloc gee my geheue hier.
My wyser verwysings na hierdie.
Nou, ek is nie vry om dit, so nou kan ek noem malloc weer.
Nou is dit wys hier. Nou is my geheue wys hier.
Wys oor hier. Wys oor hier.
Maar ek het verlore spoor van die adresse van al die geheue hier dat ek toegeken.
En so nou Ek het nie enige verwysing na hulle nie.
So, ek kan nie bevry buite van hierdie lus.
En so om iets soos hierdie op te los,
As jy vergeet om te vry geheue en jy kry hierdie geheugenlek,
Jy het die geheue te bevry binnekant van hierdie lus sodra jy klaar is met dit.
Wel, dit is wat gebeur. Ek weet baie van julle haat dit.
Maar nou - yay! Jy kry soos 44.000 kilogrepe.
So, jy vry om dit aan die einde van die lus,
en dit is om net te gaan bevry die geheue elke keer.
Wese, jou program nie 'n geheugenlek nie.
>> En nou iets anders wat jy kan doen, is om 'n paar geheue wat jy het gevra vir twee bevry.
In hierdie geval, jy malloc iets, jy die waarde daarvan verander.
Jy vry om dit een keer, want jy het gesê jy gedoen het met dit.
Maar dan moet ons bevry dit weer.
Dit is iets wat baie sleg is.
Dit gaan nie om aanvanklik segfault,
maar na 'n rukkie wat dit dubbel is bevry hierdie bederf jou hoop struktuur,
en jy sal 'n bietjie meer te leer oor dit as jy kies om 'n klas te neem soos CS61.
Maar in wese na 'n ruk jou rekenaar gaan om te verwar
oor watter geheue plekke is waar en waar dit gestoor -
waar die data gestoor in die geheue.
En so bevry 'n pointer twee keer 'n slegte ding wat jy nie wil hê om dit te doen.
>> Ander dinge wat kan verkeerd gaan nie met behulp van sizeof.
So, in hierdie geval jy malloc 8 grepe,
en dit is die dieselfde ding as twee heelgetalle, reg?
So, dit is heeltemal veilig, maar is dit?
Wel, as Lucas gepraat oor op verskillende platforms,
heelgetalle is van verskillende lengtes.
So, op die toestel wat jy gebruik, heelgetalle is ongeveer 4 bytes,
maar op 'n ander stelsel wat hulle kan wees 8 bytes of hulle kan 16 grepe.
So, as ek net gebruik om hierdie getal hier,
hierdie program kan werk op die toestel,
maar dit is nie genoeg geheue om te wys op 'n ander stelsel.
In hierdie geval, dit is wat die sizeof operator word gebruik vir.
Wanneer ons sizeof (int), Wat dit beteken is
dit gee ons die grootte van 'n heelgetal op die stelsel dat die program word uitgevoer.
Dus, in hierdie geval, sal sizeof (int) terugkeer 4 op iets soos die toestel,
en nou wil 4 * 2, wat 8,
wat net die bedrag van die ruimte wat nodig is vir twee heelgetalle.
Op 'n ander stelsel, as 'n int is soos 16 bytes of 8 grepe,
dit is net genoeg bytes om terug te keer daardie bedrag te stoor.
>> En laastens, structs.
Dus, as jy wou 'n sudoku-raad in geheue te stoor, kan hoe ons dit doen?
Jy mag dalk dink soos 'n veranderlike vir die eerste ding,
'n veranderlike vir die tweede ding, 'n veranderlike vir die derde ding,
'n veranderlike vir die vierde ding - sleg, reg?
So, 'n verbetering wat jy kan maak op die top van hierdie is 'n 9 x 9 skikking te maak.
Dit is goed, maar wat as jy wil ander dinge om te assosieer met die sudoku raad
soos wat die probleme van die raad is,
of, byvoorbeeld, wat jou telling is, of hoe lank dit geneem u hierdie bord op te los?
Wel, wat jy kan doen is kan jy 'n struct skep.
Wat ek basies sê is ek is die definisie van hierdie struktuur hier,
en ek is die definisie van 'n sudoku raad wat bestaan ​​uit 'n raad wat is 9 x 9.
>> En wat dit het verwysings na die naam van die vlak.
Dit het ook x en y, wat die koördinate van waar ek nou is.
Dit het ook tyd bestee [onverstaanbaar], en dit het die totale getal van beweeg wat ek tot dusver ingevoer.
En so in hierdie geval, kan ek 'n hele klomp van die data groep in net een struktuur
in plaas van om dit soos vlieg rond soos verskillende veranderlikes
dat ek kan regtig nie hou.
En dit kan ons het net mooi sintaksis vir soort verwysingsmetode verskillende dinge binnekant van hierdie struct.
Ek kan net doen board.board, en ek kry die sudoku raad terug.
Board.level, kry ek hoe moeilik dit is.
Board.x en board.y gee my die koördinate van waar ek kan wees in die raad.
En so het ek toegang tot wat ons noem die velde in die struct.
Dit definieer sudokuBoard, wat is 'n tipe wat ek het.
En nou is ons hier. Ek het 'n veranderlike genaamd "raad" van die tipe sudokuBoard.
En so nou kan ek toegang tot al die velde wat hierdie struktuur hier.
>> Enige vrae oor structs? Ja?
[Studente] Vir int x, y, verklaar jy beide op een lyn? >> [Josef] Uh-huh.
[Studente] So, jy kan net doen wat met almal van hulle?
Soos in x, y komma keer dat die totale?
[Joseph] Ja, jy kan beslis doen wat nie, maar die rede waarom ek op dieselfde lyn x en y -
en die vraag is hoekom ons kan net doen dit op dieselfde lyn?
Waarom ons nie net sit al hierdie dinge op dieselfde lyn is
x en y is verwant aan mekaar,
en dit is net stilisties meer korrek, in 'n sekere sin,
want dit is die groepering van twee dinge op dieselfde lyn
dat net soos soort van dieselfde ding.
En ek het net verdeel hierdie uitmekaar. Dit is net 'n styl ding.
Dit maak funksioneel geen verskil hoegenaamd.
Enige ander vrae op structs?
Jy kan 'n Pokédex definieer met 'n struct.
'N Pokémon het 'n nommer en dit het 'n brief, 'n eienaar, 'n soort.
En dan as jy het 'n verskeidenheid van Pokémon, kan jy maak 'n Pokédex, reg?
Okay, cool. So, vrae op structs. Dit is verwant aan structs.
>> Ten slotte, GDB. Wat beteken GDB laat jy dit doen? Dit kan jy jou program te ontfout.
En as jy nie GDB gebruik, sou ek aanbeveel kyk na die kort
en net gaan oor wat GDB is, hoe jy werk met dit, hoe jy dit kan gebruik,
en toets dit op 'n program.
En wat GDB kan jy doen is dit kan breek die [onverstaanbaar] jou program
en 'n praktiese reël.
Byvoorbeeld, ek wil breek uitvoering soos lyn 3 van my program,
en terwyl ek by lyn 3 Ek kan druk uit al die waardes wat daar is.
En so wat ons noem soos om in 'n lyn
is ons noem dit om 'n breekpunt op daardie lyn
en dan kan ons die druk van die veranderlikes in die staat van die program op daardie tydstip.
>> Ons kan uit dan is daar stap deur die program lyn-vir-lyn.
En dan kan ons kyk na die toestand van die stapel op die oomblik.
En so om te gebruik GDB, wat ons doen is noem ons kletteren op die C-lêer,
maar ons het dit die ggdb vlag te slaag.
En sodra ons klaar is met wat ons loop net gdb op die gevolglike uitvoer lêer.
En so kry jy 'n paar soos massa van die teks soos hierdie,
maar eintlik al wat jy hoef te doen is tik in die opdragte aan die begin.
Breek hoof sit 'n breekpunt by die hoof.
Lys 400 bevat 'n lys van die reëls van die kode rondom line 400.
En so in hierdie geval jy kan net rond te kyk en sê, oh,
Ek wil 'n breekpunt op line 397, wat is hierdie lyn te stel,
en dan jou program loop in daardie stap en dit gaan om te breek.
Dit gaan om te breek daar, en jy kan druk, byvoorbeeld, die waarde van lae of hoë.
En so is daar 'n klomp van die opdragte wat jy nodig het om te weet,
en hierdie skyfievertoning gaan op die webwerf,
so as jy net wil om dit te verwys of wil sit hulle op jou cheat sheets, voel vry.
>> Cool. Dit was Quiz Review 0, en ons sal hou om indien u enige vrae het.
Alles reg.
>> [Applous]
>> [CS50.TV]