[Powered by Google Translate] [Rishikimi] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lukas Freitas, Joseph Ong] [Universiteti i Harvardit]
>> [Kjo është CS50.] [CS50.TV]
>> Hey, të gjithë.
Mirë se vini në seancën e shqyrtimit për Quiz 0, e cila po zhvillohet këtë të mërkurën.
Ajo që ne jemi duke shkuar për të bërë sonte, unë jam me 3 TFS tjera,
dhe së bashku ne do të kalojnë nëpër një rishikim të asaj që kemi bërë gjatë deri më tani.
Kjo nuk do të jetë 100% të plotë, por kjo duhet të ju jap një ide më të mirë
të asaj që ju tashmë keni atë poshtë dhe ju ende nevojë për të studiuar përpara se të mërkurën.
Dhe të ndjehen të lirë për të ngritur dorën tuaj me pyetje si ne jemi duke shkuar së bashku,
por mbani në mend se ne do të ketë gjithashtu një pak kohë në fund-
në qoftë se ne të merrni me me pak minuta për të këmbimit, për të bërë pyetje të përgjithshme,
kështu që të mbajë këtë në mendje, dhe kështu që ne jemi duke shkuar për të filluar në fillim me Javës 0.
>> [Quiz 0 Shqyrtim!] [Pjesa 0] [Lexi Ross] Por, para se të bëjmë që le të flasim për
logjistike të quiz.
>> [Logjistika] [Quiz zhvillohet të mërkurën 10/10 në vend të ligjërimit]
>> [(Shih http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf për detaje)] Kjo është në e mërkurë, 10 Tet.
>> Se kjo e mërkurë, dhe në qoftë se ju shkoni në këtë URL këtu,
e cila është gjithashtu të arritshme nga CS50.net-nuk ka një lidhje me të,
ju mund të shihni informacion në lidhje ku të shkoni në bazë të
Emri juaj e fundit, ose përkatësia shkolla, si dhe
ajo tregon se pikërisht çfarë quiz do të mbulojë dhe llojet e pyetjeve që ju jeni do të merrni.
Mbani në mend se ju do të keni një shans për të shqyrtuar për quiz në nenin,
kështu TFS tuaja duhet të shkojnë mbi disa probleme praktike,
dhe kjo është një tjetër shans të mirë për të parë se ku ju ende nevojë për të studiuar për quiz.
Le të fillojë në fillim me Bytes 'N' copa.
Kujtohet një pak është vetëm një 0 ose një 1,
dhe një bajt është një koleksion prej 8 bit të këtyre.
Le të shikojmë në këtë koleksion të bit drejtë këtu.
Ne duhet të jetë në gjendje të kuptoj se sa bit janë.
Ku ne numërimin e ka vetëm 8 prej tyre, tetë 0 ose 1 njësi.
Dhe pasi ka 8 bit, se edhe 1 byte,
dhe le të kthyer atë në heksadecimal.
Hexadecimal është bazë 16, dhe kjo është goxha e lehtë për t'u kthyer
një numër në binar, e cila është ajo që është, në një numër në heksadecimal.
Të gjithë ne bëjmë është që ne të shikojmë në grupe prej 4,
dhe ne shnderrimin e tyre për shifra e duhur heksadecimal.
Ne fillim me grupin e djathtë më i 4, kështu që 0011.
Që do të jetë një 1 dhe një 2, kështu bashku që bën 3.
Dhe pastaj le të shohim në bllokun tjetër 4.
1101. Që do të jetë një 1, një 4, dhe një 8.
Së bashku që do të jetë 13, i cili bën D.
Dhe ne do të kujtojmë se në heksadecimal ne nuk shkojnë vetëm nëpër 0 9.
Ne do të shkojmë nëpër F 0, kështu që pas 9, 10 i korrespondon një,
11 B, e të tjera, ku F është 15.
Këtu 13 është një D,
mënyrë për të kthyer atë në decimal të gjithë ne bëjmë është që ne të vërtetë
trajtojnë çdo pozicion si një fuqi prej 2.
Kjo është një 1, 2 një, zero 4s, zero 8s, një 16, më tej,
dhe kjo është pak e vështirë për të llogaritur në kokën tuaj, por nëse ne do të shkojmë në rrëshqitje tjetër
ne mund të shohim përgjigje për këtë.
>> Në thelb ne jemi duke shkuar në të gjithë nga e djathta në të majtë mbrapa,
dhe ne jemi shumëzuar çdo shifër nga fuqia e 2 korresponduese.
Dhe mbani mend, per heksadecimal kemi treguar këto numra me 0x në fillim
kështu që ne nuk e ngatërruar atë me një numër decimal.
Vazhduar më, kjo është një Tabela ASCII,
dhe atë që ne i përdorim ASCII është për të hartë nga personazhet me vlerat numerike.
Kujtohet në pset kriptografisë kemi bërë përdorimin e gjerë të tabelën ASCII
në mënyrë që të përdorin metoda të ndryshme të cryptography,
the Cezari dhe shifër Vigenere, për të kthyer letra të ndryshme
në një varg sipas kyç të dhënë nga ana e përdoruesit.
Le të shikojmë në pak matematikë ASCII.
Kërkim në 'P' + 1, në formën e karakterit që do të jetë Q,
dhe mos harroni se '5 '≠ 5.
Dhe pikërisht si do të konvertohet në mes të atyre që ne 2 forma?
Kjo nuk është në të vërtetë shumë e vështirë.
Në mënyrë që të merrni 5 zbresim '0 '
sepse ka 5 vende mes të '0 'dhe '5'.
Në mënyrë për të shkuar në mënyrë tjetër, ne shtoni vetëm 0,
kështu që kjo është lloj i si aritmetike të rregullt.
Vetëm mos harroni se kur diçka ka citate rreth tij kjo është një karakter
dhe kështu i korrespondon një vlerë në tabelën ASCII.
Lëvizur në shumë tema të përgjithshme shkencave kompjuterike.
Ne kemi mësuar se çfarë është një algoritmi është dhe se si ne e përdorin programimit
për zbatimin e algoritme.
Disa shembuj të algoritmeve janë diçka të vërtetë të thjeshtë si
kontrolluar nëse një numër është edhe apo i rastësishëm.
Për këtë kujtojmë ne mod me numrin 2 dhe kontrolloni nëse rezultati është 0.
Nëse është kështu, ajo është edhe më. Nëse jo, kjo është e çuditshme.
Dhe kjo është një shembull i një algoritmi të vërtetë themelore.
>> A pak e një më të përfshirë është kërkimi binar,
të cilat ne do të shkoj për më vonë në seancën e shqyrtimit.
Dhe programimi është term që ne përdorim për të marrë një algoritmi
dhe konvertimin atë për kodin kompjuterin mund të lexoni.
2 shembuj të programimit është zeroja,
cila është ajo që ne e bëmë në Javën 0.
Edhe pse ne fakt nuk shkruani kodin nga kjo është një mënyrë e zbatimit të
kjo algoritmi, e cila është e shtypje numrat 1-10,
dhe këtu ne bëjmë të njëjtën gjë në gjuhën e programimit C.
Këto janë funksionalisht të barasvlershme, të shkruara vetëm në gjuhë të ndryshme ose sintaksor.
Ne pastaj mësuar për shprehje boolean,
dhe një Boolean është një vlerë që është ose e vërtetë apo e rreme,
dhe shprehje boolean këtu shpesh
shkoni brenda kushteve, kështu që nëse (x ≤ 5),
mirë, ne kemi vendosur tashmë x = 5, në mënyrë që gjendja do të vlerësojë të vërtetë.
Dhe nëse kjo është e vërtetë, pavarësisht Kodi është nën kusht
do të vlerësohet nga kompjuteri, në mënyrë që vargu do të jenë të shtypura
të prodhimit standarde, dhe gjendjen afat
i referohet çdo gjë që është brenda kllapa e deklaratës nëse.
Mbani mend të gjithë operatorët.
Të ruaj të && dhe ajo e | | kur ne jemi duke u përpjekur për të kombinuar 2 ose më shumë kushte,
== = Jo për të kontrolluar nëse 2 gjëra janë të barabartë.
Mos harroni se është për caktimin = == ndërsa është një operator Boolean.
≤, ≥ dhe pastaj 2 finale janë vetë-shpjeguese.
Një shqyrtim i përgjithshëm i logjika Boolean këtu.
Dhe shprehje boolean janë gjithashtu të rëndësishme në sythe,
të cilat ne do të shkoj për tani.
Ne mësuam rreth 3 llojet e sythe deri tani në CS50, për, ndërsa, dhe të bëjë duke.
Dhe është e rëndësishme të dini se ndërsa për shumicën e qëllimeve
ne fakt mund të përdorni çdo lloj lak në përgjithësi
ka lloje të caktuara të përbashkëta qëllime apo modelet
në programimin që në mënyrë specifike për të thirrur një nga këto sythe
që e bëjnë atë më efikas të kodit apo elegante atë në atë mënyrë.
Le të shkojnë mbi atë që secili nga këto sythe tendencë të përdoren për më shpesh.
>> Në një për lak ne përgjithësi tashmë e dimë se sa herë që ne duam të iterate.
Kjo është ajo që ne kemi vënë në gjendje.
Sepse, i = 0, i <10, për shembull.
Ne tashmë e dimë që ne duam të bëjmë diçka 10 herë.
Tani, për një lak, ndërsa, në përgjithësi ne nuk domosdoshmërisht
e di se sa herë ne duam lak për të kandiduar.
Por ne e dimë disa lloj kusht që ne duam që ajo të
të jetë gjithmonë e vërtetë apo e rreme të jetë gjithmonë.
Për shembull, ndërsa është vendosur.
Le të themi se është një ndryshore boolean.
Ndërkohë që është e vërtetë që ne duam kodin për të vlerësuar,
kështu që një pak më të zgjeruar, një pak më të përgjithshme se një për lak,
por çdo për lak gjithashtu mund të konvertohet në një lak, ndërsa.
Së fundi, bëni ndërsa unazore, të cilat mund të jetë trickiest për të kuptuar menjëherë,
janë përdorur shpesh kur ne duam të vlerësojmë kodin parë
para herë të parë ne kontrolloni gjendjen.
Një rast i zakonshëm për një përdorim bëni ndërsa lak
është kur ju doni të merrni të dhëna përdoruesi, dhe ju e dini që ju doni të kërkoni përdoruesit
për kontributin paktën një herë, por nëse ata nuk ju japin kontribut të mirë menjëherë
ju doni të mbani duke u kërkuar atyre derisa ata të ju jap të dhëna të mira.
Kjo është përdorimi më të zakonshme të një të bëjë, ndërsa loop,
dhe le të shikojmë në strukturën aktuale të këtyre unazore.
Ata zakonisht gjithmonë kanë tendencë për të ndjekur këto modele.
>> Në lak për brenda ju keni 3 komponentë:
initialization, zakonisht diçka si int i = 0, ku i është kundër,
kusht, ku ne duam të themi drejtuar këtë për lak për sa kohë që kjo gjendje ende mban,
Ashtu si unë <10, dhe pastaj në fund, përditësim, e cila është se si ne rritje
variabli counter në çdo pikë në lak.
Një gjë e përbashkët për të parë nuk është vetëm i + +,
që do të thotë shtim i nga 1 në çdo kohë.
Ju gjithashtu mund të bëjë diçka si unë + = 2,
që do të thotë shtoni 2 me i çdo herë ju shkoni nëpër lak.
Dhe pastaj e bëjnë këtë vetëm referohet çdo kod që aktualisht drejton si pjesë e lak.
Dhe për një lak, ndërsa, këtë herë ne fakt kemi inicializimit jashtë lak,
kështu për shembull, le të thonë se ne jemi duke u përpjekur për të bërë të njëjtin lloj të lak si unë përshkruar vetëm.
Ne do të thonë int i = 0 para se të fillon lak.
Atëherë ne mund të themi, ndërsa i <10 ta bëjë këtë,
kështu që blloku i njëjtë i kodit si më parë,
dhe këtë herë pjesë e përditësimi i kodit, për shembull, i + +,
në fakt shkon brenda lak.
Dhe së fundi, për një të bëjë, ndërsa, është e ngjashme me lak, ndërsa,
por ne duhet të kujtojmë se kodi do të vlerësojë herë
para se gjendja është e kontrolluar, kështu që ka kuptim shumë më tepër
në qoftë se ju shikoni në atë në mënyrë të krye e deri në fund.
Në një të bëjë ndërsa kodi lak vlerëson ju edhe para se të shikojmë në gjendjen, ndërsa,
ndërsa një lak, ndërsa, ajo kontrollon parë.
Deklaratat dhe variablave.
Kur ne duam të krijojmë një variabël i ri ne së pari duam të inicializoj atë.
>> Për shembull, bar int initializes bar ndryshueshme,
por kjo nuk do t'i jepte një vlerë, kështu që çfarë është vlera e bar e tani?
Ne nuk e dimë.
Kjo mund të jetë disa vlera plehrash që ishte ruajtur më parë në kujtesën atje,
dhe ne nuk duam që të përdorin këtë variabël
deri sa ne fakt jepte një vlerë,
kështu që ne deklaroj këtu.
Pastaj ne nisja që ajo të jetë 42 më poshtë.
Tani, sigurisht, ne e dimë kjo mund të bëhet në një linjë, bar int = 42.
Por vetëm të jetë i qartë hapat e shumta që janë në vazhdim e sipër,
deklarata dhe initialization ndodhin veçmas këtu.
Kjo ndodh në një hap, dhe një tjetër, int Baz = bar + 1,
kjo deklaratë më poshtë, që Baz increments, kështu që në fund të këtij blloku kodi
në qoftë se ne do të shtypura vlerën e Baz ajo do të jetë 44
sepse ne deklarojë dhe nisja atë të jetë 1 bar>,
dhe pastaj ne rritje atë një herë më shumë me + +.
Ne shkuam mbi këtë shkurtimisht bukur, por është mirë që të ketë një të përgjithshme
të kuptuarit e asaj që temat dhe ngjarjet janë.
Ne kryesisht e bëri këtë në Scratch,
kështu që ju mund të mendoni për temat si sekuenca të shumta të kodit
drejtimin në të njëjtën kohë.
Në fakt, ajo ndoshta nuk është drejtimin në të njëjtën kohë,
por lloj abstrakte ne mund të mendoni për atë në këtë mënyrë.
>> Në Scratch, për shembull, kishim sprites shumta.
Kjo mund të jetë ekzekutuar kod të ndryshme në të njëjtën kohë.
Një mund të jetë në këmbë ndërsa tjetri është duke thënë diçka
në një pjesë të ndryshme të ekran.
Ngjarje janë një mënyrë tjetër e ndan nga logjika
mes elementeve të ndryshme të kodit tuaj,
dhe në Scratch ne ishim në gjendje për të simuluar ngjarjet duke përdorur Broadcast,
dhe kjo është në fakt kur kam marrë, jo kur dëgjoj,
por në thelb kjo është një mënyrë për të transmetuar informacion
nga një sprite në një tjetër.
Për shembull, ju mund të dëshironi të transmetojë lojë gjatë,
dhe kur një tjetër lojë sprite merr mbi,
ai i përgjigjet në një mënyrë të caktuar.
Kjo është një model i rëndësishëm për të kuptuar për programimin.
Vetëm për të shkuar gjatë javës bazë 0, çka kemi shkuar mbi deri tani,
le të shohim në këtë program C thjeshtë.
Teksti mund të jetë pak më i vogël nga këtu, por unë do të shkoj mbi atë të vërtetë të shpejtë.
Ne jemi përfshirë 2 fotografi header në të, cs50.h lartë dhe stdio.h.
Ne jemi pastaj përcaktimin një limit konstant quajtur të jenë 100.
Ne jemi pas zbatimit funksioni ynë kryesor.
Që ne nuk e përdorim argumente command line këtu kemi nevojë për të vënë pavlefshme
si argumente për kryesor.
Ne e shohim më sipër int kryesore. Kjo është lloj kthimi, prandaj kthehen 0 në fund.
Dhe ne jemi duke përdorur funksionin e bibliotekës CS50 merrni int
të kërkojë nga shfrytëzuesi për input, dhe ne dyqan atë në këtë x ndryshueshme,
kështu që ne të deklarojë x lart, dhe ne nisja me x = GetInt.
>> Ne atëherë kontrolloni për të parë nëse përdoruesi na dha kontribut të mirë.
Nëse kjo është LIMIT ≥ ne duam të kthehen një kod gabimi prej 1 dhe printoni një mesazh gabimi.
Dhe së fundi, në qoftë se përdoruesi na ka dhënë kontribut të mirë
ne jemi duke shkuar në sheshin e numrit dhe të shtypura jashtë në këtë rezultat.
Vetëm për të siguruar që ata të gjithë në shtëpi hit
ju mund të shihni etiketat e pjesëve të ndryshme të kodit këtu.
Kam përmendur të vazhdueshme, fotografi header.
Oh, int x. Sigurohuni që të mbani mend se është një variabël lokale.
Kjo kontraston atë nga një ndryshore globale, të cilat ne do të flasim për
pak më vonë në seancën e shqyrtimit,
dhe ne jemi të thirrur funksionin e bibliotekës printf,
kështu që nëse ne nuk e kishte përfshirë file header stdio.h
ne nuk do të jetë në gjendje të thërrasë printf.
Dhe unë besoj se shigjeta që u shfaros këtu është vënë në% d,
cila është një varg formatimit në printf.
Ajo thotë se të shtypura nga ky variabël si një numër,% d.
Dhe kjo është ajo për të Javës 0.
Tani Lucas do të vazhdojë.
Hej, djema. Emri im është Lukas.
Unë jam një i paedukuar mjaft në shtëpinë më të mirë në kampus, Mather,
dhe unë jam duke shkuar për të folur pak për Javën e 1 dhe 2,1.
[Java 1 dhe 2.1!] [Lucas Freitas]
Si Lexi u thënë, kur kemi filluar përkthimin kodin tuaj nga e para në C
një nga gjërat që kemi vërejtur është se ju nuk mund vetëm të
shkruani kodin tuaj dhe drejtuar atë duke përdorur një flamur të gjelbër më.
Në fakt, ju duhet të përdorni disa hapa për të bërë programin tuaj C
të bëhet një file e ekzekutueshme.
Në thelb ajo që ju bëni kur jeni të shkruar një program është se
ju përkthejnë idenë tuaj në një gjuhë që një përpilues mund ta kuptojnë,
kështu që kur ju jeni duke shkruar një program në C
çfarë jeni duke bërë në fakt është shkruar diçka që përpiluesit juaj është duke shkuar për të kuptuar,
dhe pastaj përpiluesit do të përkthejnë atë kod
në diçka që kompjuteri juaj do të kuptojnë.
>> Dhe gjëja është, kompjuteri juaj është në të vërtetë shumë e memec.
Kompjuteri juaj mund të kuptojë vetëm 0s dhe 1s,
kështu që në të vërtetë në kompjuterët e parë njerëzit programuar zakonisht
përdorur 0s dhe 1s, por jo më, falënderoj Perëndinë.
Ne nuk duhet të mësuar përmendësh sekuenca për 0s dhe 1s
për një për lak ose për një lak kohë dhe kështu me radhë.
Kjo është arsyeja pse ne kemi një përpilues.
Çfarë është një përpilues nuk është ajo në thelb përkthehet kodin C,
në rastin tonë, në një gjuhë që kompjuteri juaj do të kuptojnë,
cila është kodi objekt, dhe përpiluesit se ne jeni përdorur
quhet tingëllimë, kështu që kjo është në të vërtetë simbol për tingëllimë.
Kur ju keni programin tuaj, ju duhet të bëni 2 gjëra.
Së pari, ju duhet të hartojnë programin tuaj, dhe pastaj ju do të jeni të drejtuar programin tuaj.
Për të hartuar programin tuaj ju keni shumë opsione për të bërë kështu.
I pari është për të bërë programi tingëllimë
në të cilat programi është emri i programit tuaj.
Në këtë rast ju mund të shihni se ata janë vetëm duke thënë "Hej, hartojnë programin tim."
Ju nuk jeni i thënë: "Unë dua këtë emër për programin tim" ose diçka.
>> Mundësia e dytë është duke i dhënë një emër për programin tuaj.
Ju mund të them tingëllimë-o dhe pastaj emrin që ju dëshironi
file e ekzekutueshme për të quajtur si dhe pastaj programi.
Dhe ju gjithashtu mund të bëjë të bëjë programin, dhe të shohim se si ne 2 rastet e para
Kam vënë. C, dhe në një të tretën unë vetëm kanë programe?
Yeah, ju vërtetë nuk duhet të vënë. C kur ju përdorni bëni.
Përndryshe përpiluesi është në të vërtetë do të çirrem në ju.
Dhe gjithashtu, unë nuk e di nëse ju djema mbani mend,
por shumë herë kemi përdorur edhe lcs50-ose-LM.
Kjo është quajtur lidh.
Ajo thjesht tregon përpilues që ju do të përdorni ato biblioteka të drejtë atje,
kështu që nëse ju doni të përdorni cs50.h ju në të vërtetë duhet të tipit
tingëllimë programi-lcs50.
Nëse ju nuk e bëni këtë, përpiluesit nuk do të dinë
se ju jeni duke përdorur ato funksione në cs50.h.
Dhe kur ju doni të drejtuar programin tuaj ju keni 2 opsione.
Nëse ju e bëri programi tingëllimë ju nuk keni dhënë një emër të programit tuaj.
Ju keni për të drejtuar atë duke përdorur. A.out /.
A.out është një emër standard që tingëllimë jep programin tuaj nëse ju nuk jepte një emër.
Përndryshe ju do të jeni për të bërë. Program / në qoftë se ju dha një emër për programin tuaj,
dhe në qoftë se ju ka bërë emrin e programit që një program do të merrni
tashmë do të jetë i programuar të njëjtin emër si file c.
Pastaj kemi biseduar rreth llojeve të të dhënave dhe të dhënave.
>> Në thelb lloje të të dhënave janë e njëjta gjë si kuti të vogla që ata përdorin
për të ruajtur vlerat, kështu lloje të të dhënave në të vërtetë janë vetëm si Pokémons.
Ata vijnë në të gjitha madhësive dhe llojeve.
Unë nuk e di nëse kjo analogji e bën kuptim.
Madhësia e të dhënave në fakt varet nga arkitekturën makinë.
Të gjitha madhësive të dhënat që unë jam duke shkuar për të treguar këtu
janë në të vërtetë për një makinë 32-bit, e cila është rasti i aparatit tonë,
por në qoftë se ju në të vërtetë janë coding Mac tuaj ose në një Windows gjithashtu
ndoshta ju jeni do të ketë një makinë 64-bit,
kështu që mos harroni se madhësive të dhënat që unë jam duke shkuar për të treguar këtu
janë për makinë 32-bit.
I pari që pamë ishte një int,
e cila është shumë e thjeshtë.
Ju përdorni int për të ruajtur një numër të plotë.
Ne gjithashtu pa karakter, i char.
Nëse ju doni të përdorni një letër apo një simbol pak ju jeni me siguri do të përdorin një char.
Një char ka 1 bajt, që do të thotë 8 bit, si Lexi tha.
Në thelb ne kemi një Tabela ASCII që ka 256
kombinimet e mundshme të 0s dhe 1s,
dhe pastaj kur ju shkruani një char ajo do të përkthehet
karakteri që ju inputet një numër që ju keni në tabelën ASCII, si Lexi tha.
Ne gjithashtu kemi noton, të cilat ne i përdorim për të ruajtur numrat decimal.
Nëse ju doni të zgjidhni 3,14, për shembull, ju jeni do të përdorin një noton
ose një të dyfishtë që ka më shumë saktësi.
Një noton ka 4 bytes.
Një dyfishtë ka 8 bytes, kështu që i vetmi ndryshim është saktësi.
Ne gjithashtu kemi një kohë të gjatë që është përdorur për integers,
dhe ju mund të shikoni për një makinë 32-bit një int dhe një kohë të kenë të njëjtën madhësi,
kështu që nuk ka të vërtetë të bëjë kuptim për të përdorur një kohë të gjatë në një makinë 32-bit.
>> Por në qoftë se ju jeni duke përdorur një makinë Mac dhe 64-bit, në të vërtetë një kohë të gjatë ka madhësi 8,
kështu që me të vërtetë varet nga arkitekturës.
Për makinë 32-bit kjo nuk ka kuptim për të përdorur një kohë të gjatë me të vërtetë.
Dhe pastaj një kohë të gjatë, në anën tjetër, ka 8 bytes,
kështu që është shumë e mirë në qoftë se ju dëshironi që të ketë një numër i plotë më të gjatë.
Dhe së fundi, ne kemi varg, e cila është në fakt një * char,
cila është një akrep tek një shkrumb.
Është shumë e lehtë të mendoni se madhësia e vargut do të jetë si
Numri i karaktereve që ju keni atje,
por në fakt * char vetë
ka madhësinë e një pointer në një char, i cili është 4 bytes.
Madhësia e një * char është 4 bytes.
Kjo nuk ka rëndësi në qoftë se ju keni një fjalë të vogël ose një letër apo ndonjë gjë.
Ajo do të jetë 4 bytes.
Ne gjithashtu mësuar pak në lidhje me hedh,
në mënyrë që ju mund të shihni, nëse keni, për shembull, një program që thotë
int x = 3 dhe pastaj printf ("% d", x / 2)
bëni ju djema e di se çfarë ajo do të shtypura në ekran?
>> Dikush? >> [Studentët] 2.
1. >> 1, vërtet.
Kur ju bëni 3/2 ajo do të marrë 1,5,
por që ne jemi duke përdorur një numër të plotë se kjo do të injorojë pjesën decimal,
dhe ju jeni do të ketë 1.
Nëse ju nuk dëshironi që kjo të ndodhë atë që ju mund të bëni, për shembull,
është shpallë një noton y = x.
Pastaj x që përdoret për të jetë 3 është tani do të jetë në y 3.000.
Dhe pastaj ju mund të shtypura y / 2.
Në fakt, unë duhet të ketë një 2. atje.
Ajo do të bëjë 3.00/2.00,
dhe ju jeni duke shkuar për të marrë 1.5.
Dhe ne e kemi këtë f .2 vetëm për të kërkuar 2 njësi dhjetore në pjesën dhjetore.
Nëse ju keni 0,3 f ajo do të ketë në fakt 1,500.
Nëse kjo është 2 ajo do të jetë 1.50.
Ne gjithashtu kemi me këtë rast këtu.
Nëse ju bëni noton x = 3.14 dhe pastaj ju x printf
ju jeni do të marrë 3.14.
Dhe në qoftë se ju bëni x = int i X,
që do të thotë trajtojnë si një int x dhe ju të shtypura x tani
ju jeni do të ketë 3,00.
Bën që të bëjnë kuptim?
Sepse ju jeni të parë trajtimin x si një numër të plotë, kështu që ju jeni duke injoruar pjesën decimal,
dhe pastaj ju jeni shtypjen x.
Dhe së fundi, ju gjithashtu mund të bëjë këtë,
int x = 65, dhe pastaj ju të deklarojë një char c = x,
dhe pastaj, nëse keni shkruar c ju jeni të vërtetë do të merrni
A, kështu që në thelb ajo që ju jeni duke bërë këtu
është përkthyer numër i plotë në karakter,
ashtu si Tabela ASCII bën.
Ne gjithashtu biseduam për operatorët matematike.
Shumica e tyre janë mjaft të drejtpërdrejtë, kështu +, -, *, /,
dhe gjithashtu kemi biseduar për mod, e cila është pjesa e ndarjes së 2 numrave.
Nëse ju keni 10% 3, për shembull,
kjo do të thotë ndarje 10 me 3, dhe çka është pjesa tjetër?
Ajo do të jetë 1, kështu që kjo është në fakt shumë i dobishëm për një shumë të programeve.
Për Vigenere dhe Cezarit Unë jam goxha i sigurt se të gjithë ju djema përdorur mod.
Rreth operatorët matematike, të jenë shumë të kujdesshëm kur të kombinuar dhe / *.
>> Për shembull, nëse ju bëni (3/2) * 2 se çfarë po ju do të merrni?
[Studentët] 2.
Po, 2, sepse 3/2 është do të jetë 1.5,
por pasi që ju jeni duke bërë operacionet mes 2 integers
ju jeni në të vërtetë vetëm do të marrin në konsideratë 1,
dhe pastaj 1 * 2 do të jetë 2, në mënyrë që të jenë shumë, shumë të kujdesshëm
kur bën aritmetike me integers, sepse
ju mund të merrni se 2 = 3, në këtë rast.
Dhe gjithashtu të jenë shumë të kujdesshëm në lidhje me përparësisë.
Ju duhet të zakonisht përdorin kllapa të jetë i sigurt se ju e dini se çfarë jeni duke bërë.
Disa shkurtesa të dobishme, sigurisht, një është i + + ose + i = 1
ose duke përdorur + =.
Kjo është e njëjta gjë si bëjnë i = i + 1.
Ju gjithashtu mund të bëjë i - ose i - = 1,
cila është gjë njëjtë si I = I -1,
diçka djema përdorni një shumë në për sythe, të paktën.
Gjithashtu, për *, në qoftë se ju përdorni * = dhe nëse ju bëni, për shembull,
i * = 2 është e njëjta gjë si duke thënë se i = i * 2,
dhe e njëjta gjë për ndarje.
Nëse ju bëni i / = 2 kjo është e njëjta gjë si i = i / 2.
>> Tani në lidhje me funksionet.
Ju djema janë mësuar që funksionon një strategji shumë e mirë për të ruajtur kodin
ndërsa ju jeni programimit, kështu që nëse ju dëshironi për të kryer të njëjtën detyrë
në kodin përsëri dhe përsëri, ndoshta ju doni të përdorni një funksion
vetëm kështu që ju nuk keni për të kopjoni dhe ngjisni kodin pushim.
Aktualisht, kryesore është një funksion, dhe kur unë të ju tregojnë formatin e një funksioni
ju do të jeni për të parë se kjo është shumë e qartë.
Ne gjithashtu përdorin funksionet nga disa biblioteka,
për shembull, printf, GetIn, i cili është nga biblioteka CS50,
dhe funksione të tjera si toupper.
Të gjitha këto funksione janë zbatuar aktualisht në biblioteka të tjera,
dhe kur ju vënë ato fotografi litar në fillim të programit tuaj
ju jeni duke thënë mund të ju lutem jepni kodin për këto funksione
kështu që unë nuk kam për t'i zbatuar ato me veten?
Dhe ju gjithashtu mund të shkruani funksionet tuaja, kështu që kur ju filloni programimit
ti e kupton se biblioteka nuk kanë të gjitha funksionet që ju duhet.
Për pset e fundit, për shembull, kemi shkruar barazim, rrahje, dhe lookup,
dhe kjo është shumë, shumë e rëndësishme që të jenë në gjendje të shkruani funksionet
sepse ata janë të dobishme, dhe ne i përdorim ato gjatë gjithë kohës në programimin,
dhe ajo kursen një shumë të kodit.
Formati i një funksioni është kjo një.
Ne kemi llojin e kthimit në fillim. Çfarë është lloji kthimi?
Kjo është vetëm kur funksioni juaj do të kthehen.
Nëse ju keni një funksion, për shembull, faktoriale,
që do të llogaritur një faktorial i një numër i plotë,
ndoshta ajo do të kthehet edhe një numër të plotë.
Pastaj lloji kthimi do të jetë int.
Printf në fakt ka një zbrazëti lloj të kthimit
sepse ju nuk jeni kthyer asgjë.
Ju jeni vetëm shtypjen gjëra në ekran
dhe ndalohet pirja e duhanit funksionin më pas.
Atëherë ju keni emrin e funksionit që ju mund të zgjidhni.
Ju duhet të jetë pak më të arsyeshme, si mos zgjidhni një emër si xyz
ose si x2f.
Të përpiqet të bëjë një emër që ka kuptim.
>> Për shembull, në qoftë se është faktorial, faktoriale thonë.
Në qoftë se kjo është një funksion që do të nxjerrë diçka, atë emër barazim.
Dhe pastaj ne kemi parametra, të cilat janë quajtur edhe argumente,
të cilat janë si burimet që funksioni juaj ka nevojë për
nga kodin tuaj për të kryer detyrën e saj.
Nëse ju doni për të llogaritur faktoriale e një numri të
ndoshta ju duhet të keni një numër për të llogaritur një faktoriale.
Një nga argumentet që ju jeni do të ketë është numri vetë.
Dhe pastaj ajo do të bëjë diçka dhe kthimin e vlerës në fund
përveç nëse kjo është një funksion i pavlefshëm.
Le të shohim një shembull.
Nëse unë dua të shkruaj një funksion që përmbledh të gjitha numrat në një rrjet të integers,
para së gjithash, lloji kthimi do të jetë int
sepse unë kam një rrjet të integers.
Dhe atëherë unë jam do të ketë emrin e funksionit si sumArray,
dhe pastaj ajo do të marrë array vetë, për të nums int,
dhe pastaj gjatësia e array kështu që unë e di se sa numra kam për të përmbledhur.
Atëherë unë duhet të nisja një shumë të ndryshueshme të quajtur, për shembull, për 0,
dhe çdo herë që unë shoh një element në grup unë duhet të shtoni atë në shumës, kështu që kam bërë një për lak.
Ashtu si Lexi tha, ju bëni int i = 0, i <gjatësia dhe i + +.
Dhe për çdo element në grup që kam bërë shuma + = nums [i],
dhe atëherë unë u kthye shuma, kështu që është shumë e thjeshtë, dhe kjo kursen një shumë të kodit
në qoftë se ju jeni duke përdorur këtë një funksion shumë herë.
Pastaj kemi marrë një vështrim në kushte.
Ne kemi, nëse tjetër, dhe tjetër në qoftë se.
Le të shohim se çfarë është dallimi në mes të atyre.
Hidhni një sy në këto 2 kodeve. Çfarë është dallimi në mes tyre?
I pari ka-thelb kodet duan që ju të tregoni
nëse një numër është +, -, ose 0.
I pari thotë se në qoftë se është> 0 atëherë kjo është pozitive.
Nëse kjo është = 0, atëherë ajo që është 0, dhe nëse kjo është <0, atëherë kjo është negative.
>> Dhe tjetra është duke bërë, nëse, nëse tjetër, tjetër.
Dallimi në mes të dy është se kjo është në të vërtetë do të
kontrolloni nëse> 0, 0 <ose = 0 tri herë,
kështu që nëse ju keni numrin 2, për shembull, do të vijnë këtu dhe të thonë
if (x> 0), dhe kjo do të thotë po, kështu që unë të shtypura pozitive.
Por edhe pse unë e di se është e> 0 dhe ajo nuk do të jetë 0 apo <0
Unë jam ende duke shkuar për të bërë është 0, është ajo <0,
kështu që unë jam në të vërtetë duke shkuar brenda VJ se unë nuk duhet të
sepse unë tashmë e di se ai nuk do të plotësojë ndonjë nga këto kushte.
Unë mund të përdorni në qoftë se, në qoftë tjetër, tjetër deklaratë.
Ajo në thelb thotë se nëse x = 0 Unë të shtypura pozitive.
Nëse nuk është, unë jam duke shkuar për të provuar këtë.
Nëse kjo është 2 unë nuk jam duke shkuar për të bërë këtë.
Në thelb, nëse unë kam për x = 2 ju do të thoni
if (x> 0), po, kështu Printo këtë.
Tani që unë e di se është e> 0 dhe se të kënaqur të parë nëse
Unë nuk jam edhe do të drejtuar këtë kod.
Kodi i shkon më shpejt, në fakt, 3 herë më të shpejtë në qoftë se ju përdorni këtë.
Ne gjithashtu mësuar rreth dhe dhe ose.
Unë nuk jam duke shkuar për të shkuar nëpër këtë, sepse tashmë Lexi folur rreth tyre.
Kjo është vetëm && dhe | | operatorit.
>> E vetmja gjë që unë do të them është të jenë të kujdesshëm kur ju keni 3 kushte.
Përdorni kllapa sepse ajo është shumë konfuze kur ju keni një kusht
dhe një tjetër apo një tjetër.
Përdorni kllapa vetëm për t'u siguruar se kushtet tuaja kuptim
sepse në këtë rast, për shembull, ju mund të imagjinojmë se
kjo mund të jetë kusht i parë dhe një ose tjetër
ose 2 kushtet e kombinuara në një dhe
ose një e treta, kështu që vetëm të jenë të kujdesshëm.
Dhe së fundi, kemi biseduar për ndizet.
Një switch është shumë e dobishme kur ju keni një ndryshore.
Le të thonë se ju keni një variabël si n
që mund të jetë 0, 1, ose 2, dhe për secili prej këtyre rasteve
ju do të jeni për të kryer një detyrë.
Ju mund të them kaloni ndryshore, dhe kjo tregon se
vlera atëherë është si value1 unë jam duke shkuar për të bërë këtë,
dhe pastaj kam të thyer, që do të thotë unë nuk jam duke shkuar për të parë ndonjë nga rastet e tjera
sepse ne të kënaqur tashmë se rasti
dhe pastaj value2 dhe kështu me radhë, dhe unë gjithashtu mund të ketë një kaloni default.
Që do të thotë në qoftë se ajo nuk i plotëson asnjë nga rastet që kam pasur
që unë jam duke shkuar për të bërë diçka tjetër, por kjo është fakultative.
Kjo është e gjitha për mua. Tani le të kemi Tomi.
Të gjithë të drejtë, kjo do të jetë Java 3-ish.
Këto janë disa nga temat që ne do të mbulojnë, kripto, fushëveprimi, vargjeve, e të tjera.
Vetëm një fjalë shpejtë në kripto. Ne nuk jemi duke shkuar për të arritur këtë shtëpi.
>> Ne e bëmë këtë në pset 2, por për quiz sigurohuni që ju e dini dallimin
mes shifër Cezarit dhe shifër Vigenere,
si dy nga ato punë shifra dhe çfarë është si për të encrypt
decrypt dhe tekst duke përdorur ato 2 shifra.
Mos harroni, shifër Cezari thjesht rrotullohet çdo karakter me të njëjtën sasi,
duke u siguruar që ju mod me numrin e shkronjave në alfabet.
Dhe shifër Vigenere, në anën tjetër, rrotullohet çdo karakter
me një sasi të ndryshme, kështu që në vend se duke thënë
çdo karakter qarkullojnë nga 3 Vigenere do të rrotullohen çdo karakter
me një sasi të ndryshme në varësi të disa fjalen
ku çdo letër në fjalë paraqet një sasi të ndryshme
të rrotullohen tekstin e qartë nga.
Le të flasim së pari në lidhje me qëllimin e ndryshueshme.
Ka 2 lloje të ndryshme të variablave.
Ne kemi variablave lokale, dhe këto do të jenë të përcaktuara
jashtë kryesore ose jashtë çdo funksion apo bllok,
dhe këto do të jenë të qasshme kudo në programin tuaj.
Nëse ju keni një funksion dhe në këtë funksion është një lak, ndërsa
ndryshueshme madh global është i arritshëm kudo.
Një variabël lokale, nga ana tjetër, është scoped në vendin ku është përcaktuar.
>> Nëse ju keni një funksion këtu, për shembull, kemi këtë funksion g,
dhe brenda g nuk është një ndryshore të quajtur y këtu,
dhe kjo do të thotë se kjo është një variabël lokale.
Edhe pse kjo është e ndryshueshme quajtur y
dhe kjo është e ndryshueshme quajtur y këto 2 funksione
nuk kanë asnjë ide se çfarë variabla njëri tjetrit lokale janë.
Nga ana tjetër, deri këtu themi int x = 5,
dhe kjo është jashtë fushës së çdo funksioni.
Kjo është jashtë fushëveprimit të kryesore, kështu që kjo është një ndryshore globale.
Kjo do të thotë se brenda këtyre 2 funksioneve kur them x - x ose + +
Unë jam hyrë në të njëjtën ku x y këtë dhe kjo y janë variabla të ndryshme.
Kjo është diferenca midis një ndryshore globale dhe një variabël lokale.
Sa i përket dizajnit është i shqetësuar, nganjëherë kjo është ndoshta një ide e mirë
për të mbajtur variablave lokale kurdo që ju ndoshta mund
pasi ka një bandë e variablave globale mund të merrni të vërtetë konfuze.
Nëse ju keni një bandë e funksioneve të gjitha modifikimit të njëjtën gjë
ju mund të harrojmë çfarë nëse ky funksion aksidentalisht modifikon këtë global,
dhe kjo funksion tjetër nuk e di për këtë,
dhe ajo ka marrë mjaft konfuze si ju të merrni kodin më shumë.
Mbajtja variablat lokale kurdo që ju ndoshta mund
është dizajn vetëm mirë.
Vargjeve, mos harroni, janë thjesht listat e elementeve të të njëjtit lloj.
Brenda CI nuk mund të ketë një listë si 1, 2.0, hello.
Ne thjesht nuk mund ta bëjë këtë.
>> Kur ne të deklarojë një koleksion në C të gjitha elementet duhet të jenë të të njëjtit lloj.
Këtu unë kam një rrjet të integers 3.
Këtu unë kam gjatësinë e vektorit, por në qoftë se unë jam vetëm duke deklaruar se në këtë sintaksë
ku unë të specifikojë se çfarë të gjitha elementet janë teknikisht unë nuk nevojë për këtë 3.
Përpiluesi është mjaft i zgjuar që të kuptoj se sa e madhe duhet të jetë array.
Tani kur unë dua të të marrë ose të vendosni vlerën e një grup
kjo është sintaksë për të bërë këtë.
Kjo në fakt do të ndryshojë elementin e dytë të grup, sepse, mos harroni,
Numërimi fillon në 0, jo në 1.
Në qoftë se unë dua të lexuar se vlera që unë mund të them diçka si int x = array [1].
Ose në qoftë se unë dua të vendosur atë vlerë, si unë jam duke bërë këtu,
Unë mund të them array [1] = 4.
Kjo kohë hyrë elemente nga indeksin e tyre
apo pozicioni i tyre ose kur ata janë në grup,
dhe që fillon në listë 0.
Ne gjithashtu mund të ketë vargjeve të vargjeve,
dhe kjo quhet një rrjet multi-dimensionale.
Kur ne kemi një rrjet multi-dimensionale
që do të thotë që ne mund të kemi diçka si rreshtave dhe kolonave,
dhe kjo është vetëm një mënyrë për të visualizing këtë apo duke menduar për të.
Kur unë kam një rrjet multi-dimensionale do të thotë se unë jam duke shkuar për të filluar nevojë
më shumë se 1 index sepse në qoftë se unë kam një rrjet
vetëm duke thënë se çfarë rresht ju jeni në nuk na jep një numër.
Kjo është me të vërtetë vetëm do të na japin një listë të numrave.
Le të thonë se unë kam këtë grup këtu.
Unë kam një koleksion të quajtur rrjetit, dhe unë jam duke thënë se ajo e 2 rreshtave dhe kolonave 3,
dhe kështu që kjo është një mënyrë për të visualizing atë.
Kur them unë dua të të marrë elementin në [1] [2]
që do të thotë se për shkak se këto janë rreshtat e parë dhe pastaj shtylla
Unë jam duke shkuar për të hidhen në rresht 1 viti kam thënë: 1.
>> Atëherë unë jam duke shkuar për të ardhur këtu për kolonën 2, dhe unë jam duke shkuar për të marrë vlerën 6.
Kuptim?
Multi-dimensionale vargjeve, mos harroni, teknikisht janë vetëm një grup i vargjeve.
Ne mund të kemi vargjeve të vargjeve të vargjeve.
Ne mund të mbajë, por me të vërtetë një mënyrë për të menduar për
se si kjo është duke u hedhur jashtë dhe çfarë po ndodh është që të kujtoj atë
në një rrjet si kjo.
Kur ne të kalojë vargjeve të funksioneve, ata do të sillen
pak ndryshe se kur ne të kalojë variablave të rregullta për funksionet
si kalon një int apo noton.
Kur ne të kalojë në një lloje int ose char apo ndonjë nga këto të dhëna të tjera
ne vetëm mori një vështrim në qoftë se funksioni modifikon
Vlera e kësaj variable se ndryshimi nuk do të shumoj deri
te funksionit quajtur.
Me një grup, në anën tjetër, që do të ndodhë.
Nëse unë të kalojë në një grup me disa funksion dhe se funksioni i ndryshon disa nga elementet,
kur unë të kthehem deri në funksionin që quhet it
grup im është tani do të jenë të ndryshme, dhe fjalori për se
vargjeve është kalojnë duke iu referuar, siç do të shohim më vonë.
Kjo është e lidhur me punën si pointers, ku këto lloje themelore të të dhënave,
në anën tjetër, janë miratuar nga vlera.
>> Ne mund të mendoj se si të bërë një kopje të disa ndryshore dhe pastaj kalon në kopje.
Kjo nuk ka rëndësi se çfarë të bëjmë me atë variabël.
Funksioni thirrje nuk do të jenë të vetëdijshëm se ajo është ndryshuar.
Vargjeve janë vetëm pak të ndryshme në këtë drejtim.
Për shembull, si ne vetëm e pa, kryesore është thjesht një funksion
që mund të marrë në 2 argumente.
Argumenti i parë në funksion kryesor është argc, ose numri i argumenteve,
dhe Argumenti i dytë është quajtur argv,
dhe ata janë vlerat reale të këtyre argumenteve.
Le të thonë se unë kam një program të quajtur this.c,
dhe unë them të bëjë këtë, dhe unë jam duke shkuar për të drejtuar këtë në rreshtin e komandave.
Tani të kalojë në disa argumente të programit tim quhet kjo,
Unë mund të them diçka të tillë. / Cs kjo është 50.
Kjo është ajo që ne imagjinojmë Davidi për të bërë çdo ditë në terminal.
Por tani brenda kryesore funksioni i këtij programi
ka këto vlera, kështu argc është 4.
Kjo mund të jetë pak konfuze, sepse me të vërtetë ne jemi që i kalojnë në është cs 50.
Kjo është vetëm 3.
Por mos harroni se elementi i parë i argv ose Argumenti i parë
është emri i funksionit vetë.
Kështu që do të thotë se ne kemi 4 gjëra këtu,
dhe elementi i parë do të jetë. / këtë.
Dhe kjo do të përfaqësohet si një varg.
Pastaj elementet e mbetura janë ato që ne pas shtypur në emër të programit.
Pra, ashtu si një mënjanë, si ne ndoshta pa në pset 2,
mos harroni se vargu 50 është ≠ në 50 integer.
Pra, ne nuk mund të themi diçka si, "int x = argv 3. '
>> Kjo është jo vetëm do të bëjë kuptim, sepse ky është një varg, dhe kjo është një numër të plotë.
Pra, nëse ju doni të konvertohet në mes të 2, mbani mend, ne do të
kanë këtë funksion magjike quajtur atoi.
Që merr një varg dhe kthehet integer përfaqësuar brenda atij vargut.
Pra, kjo është një gabim i lehtë për të bërë në quiz,
vetëm duke menduar se kjo automatikisht do të jetë lloji i saktë.
Por vetëm e di se këto do të jetë gjithmonë vargjet
edhe nëse vargu përmban vetëm një numër të plotë apo një karakter ose një noton.
Pra, tani le të flasim në lidhje me kandidimin kohë.
Kur ne kemi të gjitha këto algoritme që bëjnë të gjitha këto gjëra të çmendur,
ajo bëhet me të vërtetë të dobishme për pyetjen, "Sa kohë që ata marrin?"
Ne përfaqësojmë se me diçka të quajtur simbol asymptotic.
Pra, kjo do të thotë se - mirë, le të themi japim algorithm tonë
disa të dhëna të vërtetë, të vërtetë, të vërtetë e madhe.
Ne duam të shtrojmë pyetjen, "Si është ajo kohë do të marrë?
Sa hapa do të marrë algorithm tonë për të kandiduar
si një funksion i madhësisë së input? "
Pra, rruga e parë që ne mund të përshkruajnë kohë të kandidojë është me e madhe O.
Dhe kjo është koha më e keqe-rastin tonë running.
Pra, nëse ne duam të zgjidhim një rrjet, dhe ne japim algorithm tonë një grup
kjo është në rend zbritës, kur ajo duhet të jetë në mënyrë ngjitje,
që do të jetë rasti më i keq.
Kjo is sipërme ynë lidhur në gjatësinë maksimale të kohës algorithm tonë do të marrë.
Nga ana tjetër, kjo Ω do të përshkruajë të mirë-rasti kohë running.
Pra, nëse ne japim një sërë renditura tashmë në një algoritmi klasifikim,
sa kohë do të marrë për të zgjidhur atë?
Dhe kjo, atëherë, përshkruan një ulët i detyruar në drejtimin kohë.
Pra, këtu janë vetëm disa fjalë që përshkruajnë disa herë përbashkëta running.
Këto janë në ngjitje qëllim.
Kohën më të shpejtë running kemi quhet konstante.
>> Kjo do të thotë pa marrë parasysh se sa shumë elementeve ne japin algorithm tonë,
pa marrë parasysh sa e madhe array ynë është, sorting atë
ose duke bërë çdo gjë që ne jemi duke bërë në grup gjithmonë do të marrë të njëjtën sasi kohe.
Pra, ne mund të përfaqësojë që vetëm me një 1, e cila është një konstante.
Ne gjithashtu shikuar në kohë të kandidojë logaritmike.
Pra, diçka si kërkim binar është logaritmike,
ku ne prerë problemin në gjysmën e kohës çdo
dhe pastaj gjërat vetëm të merrni më të larta nga atje.
Dhe në qoftë se ju jeni me shkrim ndonjëherë një O i çdo algorithm faktoriale,
ju ndoshta nuk duhet të konsiderojë këtë si puna juaj ditë.
Kur krahasojmë herë running është e rëndësishme për të mbajtur në mend këto gjëra.
Pra, nëse unë kam një algoritmi që është O (n), dhe dikush tjetër
ka një algoritmi e O (2n) këto janë në të vërtetë asymptotically ekuivalente.
Pra, nëse ne e imagjinojmë n të jetë një numër i madh si eleventy miliardë:
kështu që kur ne jemi krahasuar eleventy miliardë për diçka si eleventy + 3 miliardë,
papritmas se 3 nuk ka të vërtetë të bëjë një ndryshim të madh më.
Kjo është arsyeja pse ne jemi duke shkuar për të filluar duke pasur parasysh këto gjëra të jenë të barabartë.
Pra, gjëra të tilla si këto kosntanta këtu, ka 2 x kjo, ose duke shtuar një 3,
këto janë vetëm konstante, dhe këto do të bjerë deri.
Pra, kjo është arsyeja pse të gjitha këto 3 herë drejtuara janë të njëjta si duke thënë se ata janë të O (n).
Në mënyrë të ngjashme, në qoftë se ne kemi 2 herë të tjera të kandiduar, le të themi O (n ³ + 2n ²), ne mund të shtoni
+ N, 7 +, dhe pastaj ne kemi një tjetër kohë të drejtuar kjo është vetëm o (³ n).
përsëri, këto janë e njëjta gjë, sepse këto - këto nuk janë të njëjta.
Këto janë të njëjtat gjëra, më vjen keq. Pra, këto janë të njëjta, sepse
this ³ n do të dominojnë këtë ² 2n.
>> Çfarë nuk është e njëjta gjë është nëse ne kemi drejtuar herë si O ³ (n) dhe O (n ²)
sepse ky ³ n është shumë më i madh se ky ² n.
Pra, nëse kemi eksponentët, papritmas kjo fillon në materie,
por kur ne jemi vetëm që kanë të bëjnë me faktorët si ne jemi deri këtu,
atëherë ajo nuk do të marrë parasysh për shkak se ata janë vetëm do të bjerë jashtë.
Le të marrin një vështrim në disa nga algoritme që kemi parë deri më tani
dhe bisedoni për kohën e tyre të kandidojë.
Mënyra e parë e kërkuar për një numër në një listë, që e pamë, ishte kërkim linear.
Dhe zbatimi i kërkimit lineare është super i hapur.
Ne vetëm kemi një listë dhe ne do të shikojmë në çdo element të vetme në listë
deri ne gjeni numrin ne jemi duke kërkuar për të.
Kështu që do të thotë se në rastin më të keq, kjo O (n).
Dhe rasti më i keq mund të jetë këtu nëse elementi është
elementi i fundit, pastaj duke përdorur search lineare ne duhet të shikojmë në çdo element të vetme
deri sa të kemi në të fundit në mënyrë që të dini se kjo ishte në fakt në listë.
Ne nuk mund të jap vetëm deri në gjysmë të rrugës dhe të thonë: "Kjo nuk është ndoshta atje."
Me kërkimin linear ne duhet të shikojmë në të gjithë gjë.
Të mirë-rasti kohë në punë, në anën tjetër, është konstante
sepse në rastin më të mirë elementi ne jemi duke kërkuar për të është vetëm i pari në listë.
Kështu që ajo do të marrë saktësisht të na hapin 1, pa marrë parasysh sa i madh lista është
në qoftë se ne jemi duke kërkuar për elementin e parë çdo kohë.
>> Kështu që kur ju kërkoni, mos harroni, kjo nuk kërkon që lista jonë të ndahen.
Sepse ne jemi thjesht do të shikoni mbi çdo elementi të vetëm, dhe kjo nuk ka rëndësi
atë mënyrë që ato elemente janë të in
Një algoritëm më inteligjente kërkimi është diçka si kërkim dyor.
Mos harroni, zbatimi i kërkimit binar është kur ju do të jeni
mbajtur në kërkim në mes të listës.
Dhe për shkak se ne jemi duke kërkuar në mes, ne kërkojmë që lista të renditura sipas
apo tjetër ne nuk e dimë ku e mesme është, dhe ne duhet të shikojmë mbi
krejt Listen për të gjetur atë, dhe pastaj në atë moment ne jemi vetëm humbur kohë.
Pra, nëse ne kemi një listë të renditura dhe të gjejmë e mesme, ne jemi duke shkuar për të krahasuar mes
në elementin ne jemi duke kërkuar për të.
Në qoftë se kjo është shumë e lartë, atëherë ne mund të harrojmë gjysmën e duhur
sepse ne e dimë se në qoftë se elementi ynë është tashmë shumë i lartë
dhe çdo gjë në të djathtë të këtij elementi është edhe më e lartë,
atëherë ne nuk kemi nevojë të shohim më aty.
Ku në anën tjetër, në qoftë se elementi ynë është shumë i ulët,
ne e dimë se gjithçka në të majtë të atij elementi është gjithashtu shumë i ulët,
kështu që nuk ka të vërtetë ka kuptim për të parë atje, ose.
Në këtë mënyrë, me çdo hap dhe çdo kohë ne shikojmë në mesin e listës,
ne jemi duke shkuar për të prerë problemin tonë në gjysmën sepse papritmas ne e dimë
një bandë e tërë e numrave që nuk mund të jetë një ne jemi duke kërkuar për të.
>> Në pseudokod kjo do të dukej diçka si kjo,
dhe për shkak se ne jemi prerja listën në gjysmën e kohës çdo të vetme,
hedhje keq rastin tonë kohë të drejtuar nga lineare për logaritmike.
Pra, ne kemi papritmas log-në hapat në mënyrë që të gjejnë një element në një listë.
Të mirë-rasti Ora drejtimin, megjithatë, është ende e vazhdueshme
sepse tani, le të them vetëm se elementi ne jemi duke kërkuar për të është
gjithmonë e mesme e saktë nga lista origjinale.
Kështu që ne mund të rritet listën tonë aq i madh sa ne duam, por në qoftë se elementi ne jemi duke kërkuar për të është në mes,
atëherë ajo është vetëm do të marrë na hap 1.
Kështu që është pse ne je O (log n) dhe Ω (1) ose konstante.
Le të vërtetë të drejtuar kërkim dyor në këtë listë.
Pra, le të themi se ne jemi duke kërkuar për elementin 164.
Gjëja e parë që ne do të bëjmë është të gjeni midpoint e kësaj liste.
Kjo ndodh pikërisht kështu që midpoint do të bien në mes këtyre 2 numra,
kështu që le të vetëm në mënyrë arbitrare të them, çdo herë midpoint bie në mes të 2 numrave,
le të vetëm të rrumbullakosë më lart.
Ne vetëm duhet të sigurohemi që ne bëjmë këtë në çdo hap të rrugës.
Pra, ne jemi duke shkuar për të rrumbullakosë më lart, dhe ne jemi duke shkuar për të thonë se 161 është e mesme e listës sonë.
Pra 161 <164, dhe çdo element të majtë të 161
është gjithashtu <164, kështu që ne e dimë se kjo nuk do të na ndihmojë në të gjitha
të fillojmë të shikojmë gjatë këtu, sepse elementi ne jemi duke kërkuar për nuk mund të jetë atje.
Pra, çfarë mund të bëjmë është që ne vetëm mund të harrojmë për atë gjysmën e tërë e majtë të listës,
dhe tani e konsiderojnë vetëm nga e drejta e tutje 161.
>> Pra, përsëri, kjo është midpoint, le të vetëm të rrumbullakosë më lart.
Tani 175 është shumë e madhe.
Kështu që ne e dimë se nuk do të na ndihmojë të kërkoni këtu apo këtu,
kështu që ne mund të hedhin vetëm që larg, dhe në fund ne do të goditur 164.
Çdo pyetje në kërkim binar?
Le të lëvizin nga të kërkoni përmes një listë tashmë renditura
që në fakt të marrë një listë të numrave në çdo mënyrë
dhe duke e bërë këtë listë në ngjitje qëllim.
Algorithm parë kemi shikuar në u quajt lloj flluskë.
Dhe kjo do të jetë më e thjeshtë e algoritmeve pamë.
Lloj Bubble thotë se kur çdo 2 elemente brenda listës janë jashtë vendit,
që do të thotë se ka një numër të lartë të majtë e një numri më të ulët,
atëherë ne do të bie në ujdi tyre, sepse kjo do të thotë se lista do të jetë
"Më shumë renditura" se sa ishte më parë.
Dhe ne jemi vetëm do të vazhdojë këtë proces përsëri dhe përsëri dhe përsëri
deri në fund lloj elementet e flluskë për vendndodhjen e tyre të saktë dhe ne kemi një listë të renditura.
>> Ora drejtuar kjo do të jetë O (n ²). Pse?
E pra, sepse në rastin më të keq, ne jemi duke shkuar për të marrë çdo element, dhe
ne jemi duke shkuar për t'i dhënë fund krahasuar atë me çdo element tjetër në listë.
Por në rastin më të mirë, ne kemi një listë të renditura tashmë, lloj flluskë e
vetëm do të kalojnë nëpër një herë, thonë: "Jo. Unë nuk e ka bërë asnjë këmbime, kështu që unë jam bërë."
Pra, ne kemi një kohë të mirë-rasti drejtimin e Ω (n).
Le të drejtuar lloj flluskë në një listë.
Ose së pari, le të vetëm shikoni në disa pseudokod vërtetë shpejt.
Ne duam të themi ne duam të mbajnë gjurmët e, në çdo ripërsëritje e lak,
mbajnë gjurmët e nëse ne nuk ndryshoi ndonjë elemente.
Pra, arsyeja për këtë është, ne jemi duke shkuar për të ndaluar, kur ne nuk kemi swapped ndonjë elemente.
Pra, në fillim të lak tonë, ne nuk kemi swapped asgjë, kështu që ne do të themi se është e rreme.
Tani, ne jemi duke shkuar për të shkuar nëpër lista dhe krahasoni element I te elementi i + 1
dhe në qoftë se ajo është e vërtetë se ka një numër të madh të majtë e një numri më të vogël,
atëherë ne jemi vetëm do të bie në ujdi tyre.
>> Dhe pastaj ne jemi duke shkuar për të mos harroni se ne swapped një element.
Kjo do të thotë se ne kemi nevojë për të shkuar nëpër lista të paktën 1 më shumë kohë
sepse gjendja në të cilën u ndal, ne është kur lista e tërë është renditur tashmë,
që do të thotë ne nuk kemi bërë ndonjë këmbime.
Pra, kjo është arsyeja pse gjendja jonë këtu poshtë është ', ndërsa disa elemente janë swapped ".
Pra, tani le të shohim vetëm në këtë kandidon për një listë.
Kam listën 5,0,1,6,4.
Lloj flluskoj do të fillojë gjatë gjithë rrugës në të majtë, dhe ajo do të të krahasuar
elementet i, në mënyrë që të i 0 + 1, e cila është elementi 1.
Kjo do të thotë, edhe 5> 0, por tani 5 është në të majtë,
kështu që unë duhet të bie në ujdi 5 dhe 0.
Kur unë të bie në ujdi tyre, papritmas kam marrë këtë listë të ndryshme.
Tani 5> 1, kështu që ne jemi duke shkuar për të bie në ujdi tyre.
5 nuk është i> 6, kështu që ne nuk duhet të bëjmë asgjë këtu.
Por 6> 4, kështu që ne duhet të bie në ujdi.
Përsëri, ne kemi nevojë për të drejtuar nëpër lista të tërë për të zbuluar përfundimisht
se këto janë jashtë funksionit, ne bie në ujdi tyre,
dhe në këtë pikë ne kemi nevojë për të drejtuar nëpër lista kohë 1 më shumë
për t'u siguruar se çdo gjë është në rregull të tij, dhe në këtë lloj flluskë pikë ka mbaruar.
Një algorithm të ndryshme për të marrë disa elemente dhe zgjidhja e tyre është një lloj përzgjedhje.
Ideja prapa përzgjedhjes lloj është që ne jemi duke shkuar për të ndërtuar një pjesë të renditura të listës
1 element në një kohë.
>> Dhe mënyrën se si ne jemi duke shkuar për të bërë këtë është duke ndërtuar segmentin e majtë të listës.
Dhe në thelb, çdo - në çdo hap, ne jemi duke shkuar për të marrë elementin më të vogël që kemi lënë
që nuk është renditur ende, dhe ne jemi duke shkuar për të lëvizur atë në këtë segment renditura.
Kjo do të thotë ne kemi nevojë të vazhdueshme të gjetur elementin minimal Unsorted
dhe pastaj të marrë atë element minimal dhe shkëmbim atë me çfarëdo
la-shumica element që nuk zgjidhet.
Ora drejtuar nga kjo do të jetë O (n ²), sepse në rastin më të keq
ne kemi nevojë për të krahasuar çdo element të vetme për çdo element tjetër.
Sepse ne jemi duke thënë se në qoftë se ne të fillojë në gjysmën e majtë të listës, ne kemi nevojë
për të shkuar nëpër tërë segmentin e duhur për të gjetur elementin më të vogël.
Dhe pastaj, përsëri, ne kemi nevojë për të shkuar mbi të gjithë segmentin e duhur dhe
do të mbajë mbi atë mbi dhe mbi dhe mbi përsëri.
Kjo do të jetë ² n. Ne do të duhet një për brenda loop e një tjetër për lak
e cila sugjeron ² n.
Në rastin më të mirë mendimi, le të themi se t'i jepte një listë të renditura tashmë;
ne fakt nuk e bëjmë ndonjë të mirë se n ².
Sepse lloj përzgjedhje ka asnjë mënyrë për të ditur se
elementi minimale është vetëm 1 Unë të ndodhë që të jetë në kërkim në.
Ajo ende ka nevojë për t'u siguruar që kjo është në të vërtetë minimale.
>> Dhe mënyra e vetme për t'u siguruar se ajo është minimale, duke përdorur këtë algorithm,
është që të shikojmë në çdo element të vetme përsëri.
Pra me të vërtetë, në qoftë se ju jepni atë - nëse ju jepni lloj përzgjedhje një listë të renditura tashmë,
ajo nuk do të bëjë ndonjë të mirë se duke i dhënë asaj një listë që nuk është renditura ende.
Nga rruga, nëse kjo ndodh të jetë rasti se diçka është O (diçka)
dhe omega e diçka, ne vetëm mund të them më shumë shkurtimisht se është θ diçka.
Pra, nëse ju shihni se të vijë deri diku, kjo është ajo që vetëm do të thotë.
>> Nëse diçka është theta të n ², ajo është edhe e madhe O (n ²) dhe Ω (n ²).
Kështu rastin më të mirë dhe rastin më të keq, kjo nuk ka të bëjë një ndryshim,
algorithm do të bëjë të njëjtën gjë çdo kohë.
Pra, kjo është ajo që pseudokod për lloj përzgjedhjes mund të duken si.
Ne jemi në thelb do të thotë se unë dua të iterate mbi listën
nga e majta në të djathtë, dhe në çdo ripërsëritje e lak, unë jam duke shkuar për të lëvizur
elementi minimal në këtë pjesë të renditura të listës.
Dhe një herë unë të lëvizë diçka atje, unë kurrë nuk duhet të shikoni në atë element përsëri.
Sepse sa më shpejt që unë të bie në ujdi një element për segmentin e majtë të listës, është e renditura
sepse ne jemi duke bërë gjithçka në ngjitje urdhër duke përdorur minimume.
Kështu thamë, në rregull, ne jemi në pozitë që unë, dhe ne duhet të shikojmë në të gjitha elementet e
për të drejtën e unë në mënyrë që të gjeni minimum.
Pra, kjo do të thotë që ne duam të shohim nga i + 1 në fund të listës.
Dhe tani, në qoftë se elementi që ne jemi duke kërkuar në është më pak se minimumi tonë deri më tani,
i cili, mos harroni, ne jemi duke filluar off minimale për jetë vetëm
çfarëdo elementi ne jemi aktualisht në, unë do të supozojmë se kjo është minimale.
Nëse unë gjej një element që është më e vogël se ajo, atëherë unë jam duke shkuar për të thënë, në rregull,
mirë, unë kam gjetur një minimum të ri.
Unë jam duke shkuar për të kujtuar se ku ishte minimale.
>> Deri tani, një herë unë kam kaluar nëpër këtë segment të drejtë Unsorted,
Unë mund të them se unë jam duke shkuar për shkëmbim elementin minimal me element që është në pozitë unë.
Kjo do të ndërtojnë listën time, pjesa ime renditura nga lista nga e majta në të djathtë,
dhe ne kurrë nuk duhet të shikoni në një element përsëri pasi ajo është në atë pjesë.
Pasi ne kemi swapped atë.
Pra, le të kandidojë lloj përzgjedhje në këtë listë.
Elementi blu këtu do të jetë i dhe elementi kuqe do të jetë elementi minimale.
Kështu që i fillon të gjitha rrugën në të majtë të listës, kështu që në 5.
Tani ne kemi nevojë për të gjetur element minimal Unsorted.
Pra, ne themi 0 <5, kështu që është minimale 0 tim të ri.
>> Por unë nuk mund të ndalet aty, sepse edhe pse ne mund të pranojmë se 0 është më i vogël,
ne kemi nevojë për të drejtuar nëpër çdo element tjetër të listës për t'u siguruar.
Pra, 1 është më e madhe, 6 është më e madhe, 4 është më e madhe.
Kjo do të thotë se pas duke kërkuar në të gjitha këto elemente, unë kam vendosur 0 është më i vogël.
Kështu që unë jam duke shkuar për të bie në ujdi 5 dhe 0.
Sapo kam shkëmbim që, unë jam duke shkuar për të marrë një listë të re, dhe unë e di se unë kurrë nuk duhet të shohim në atë përsëri 0
sepse sapo kam swapped atë, unë kam renditur atë dhe ne jemi duke bërë.
Tani ai vetëm kështu ndodh që elementi blu është përsëri 5,
dhe ne duhet të shikojmë në 1, 6 dhe 4 për të përcaktuar se 1
është elementi më i vogël minimale, kështu që ne do të bie në ujdi 1 dhe 5.
Përsëri, ne duhet të shikojmë në - krahasojmë 5 të 6 dhe 4,
dhe ne jemi duke shkuar për të bie në ujdi 4 dhe 5, dhe më në fund, krahasuar
ato 2 numra dhe shkëmbim ato deri sa të kemi listën tonë renditura.
Çdo pyetje në lloj përzgjedhje?
Rregull. Le të shkojë në temën e kaluar këtu, dhe kjo është recursion.
>> Recursion, mos harroni, kjo është me të vërtetë gjë e meta ku një funksion
përsëritur quan veten.
Pra, në një farë pike, ndërsa fuction jonë është vazhdimisht e quan veten,
ka nevojë të ketë disa pika në të cilën ne të ndaluar duke e quajtur veten.
Sepse nëse ne nuk e bëjmë këtë, atëherë ne jemi vetëm do të vazhdojë të bëjë këtë përgjithmonë,
dhe programi ynë nuk është vetëm do të përfundojë.
Ne e quajmë këtë kusht rasti bazë.
Dhe rasti baza thotë, në vend se duke e quajtur një funksion përsëri,
Unë jam vetëm duke shkuar për të kthyer disa vlera.
Pra, një herë ne kemi kthyer një vlerë, e kemi ndalur duke e quajtur veten,
dhe pjesa tjetër e thirrjeve ne kemi bërë deri më tani mund të kthehen.
E kundërta e rastit bazë është rasti rekursive.
Dhe kjo është kur ne duam të bërë një tjetër telefonatë në funksion që ne jemi aktualisht in
Dhe ne me siguri, edhe pse jo gjithmonë, duan të përdorin argumente të ndryshme.
>> Pra, nëse kemi një funksion të quajtur f, f dhe vetëm e quajti të marrë 1 argument,
dhe ne vetëm mbajtur thirrje f (1), F (1), F (1), dhe kjo vetëm ndodh në mënyrë që
Argumenti 1 bie në rast gjithkund rekursive, ne nuk jeni ende do të ndalet.
Edhe në qoftë se ne kemi një bazë rast, ne duhet të sigurohemi që përfundimisht ne jemi duke shkuar për të goditur atë rast bazë.
Ne nuk mbajnë vetëm duke qëndruar në këtë rast gjithkund rekursive.
Në përgjithësi, kur ne e quajmë veten, ne jemi ndoshta do të ketë një argument të ndryshme çdo herë.
Këtu është një funksion recursive të vërtetë të thjeshtë.
Pra, kjo do të llogaritur faktoriale e një numri.
Deri krye këtu kemi rastin tonë bazë.
Në rast se n ≤ 1, ne nuk jemi duke shkuar për të thirrur faktoriale përsëri.
Ne jemi duke shkuar për të ndaluar, ne jemi vetëm do të kthehen disa vlera.
Nëse kjo nuk është e vërtetë, atëherë ne jemi duke shkuar për të goditur rastin tonë rekursive.
Vini re këtu se ne nuk jemi vetëm duke e quajtur faktorial (n), sepse kjo nuk do të jetë shumë e dobishme.
Ne jemi duke shkuar për të thirrur faktoriale për diçka tjetër.
>> Dhe kështu ju mund të shihni, përfundimisht nëse ne të kalojë një diçka faktoriale (5) ose,
ne jemi duke shkuar për të thirrur faktoriale (4) dhe kështu me radhë, dhe në fund ne jemi duke shkuar për të goditur këtë rast bazë.
Pra, kjo duket e mirë. Le të shohim se çfarë ndodh kur ne fakt drejtuar këtë.
Kjo është rafte, dhe le të thonë se kryesore do të thërrasë këtë funksion me një argument (4).
Pra, një herë faktoriale sheh dhe = 4, faktoriale do të thërrasë veten.
Tani, papritmas, ne kemi faktorial (3).
Pra, këto funksione do të vazhdojë të rritet deri në fund ne goditi rastin tonë bazë.
Në këtë pikë, vlera kthimi i kësaj është kthimi (NX vlera kthimi i kësaj),
vlera kthimi i kësaj është NX vlera kthimi i kësaj.
Përfundimisht ne kemi nevojë për të goditur disa numër.
Në krye këtu, themi kthim 1.
Kjo do të thotë se një herë ne të kthehemi këtë numër, ne mund të pop këtë off rafte.
Kështu kjo faktorial (1) është e bërë.
Kur kthehet 1, kjo faktoriale (1) kthimet, kjo kthimit të 1.
Vlera e kthimit të kësaj, mos harroni, ishte NX vlera kthimi i kësaj.
Pra papritmas, ky djalë e di që unë dua të kthehen 2.
>> Pra mbani mend, kthehet vlera e kjo është vetëm NX vlera e kthimit deri këtu.
Kështu që tani ne mund të themi 3 x 2, dhe më në fund, këtu mund të themi
kjo është vetëm do të jetë 4 x 3 x 2.
Dhe një herë këtë kthim, ne kemi marrë deri në një të vetme brenda integer e kryesore.
Çdo pyetje në recursion?
Dakord. Pra, nuk ka më shumë kohë për pyetjet në fund,
por tani Jozefi do të mbulojë temat e mbetura.
>> [Joseph Ong] All right. Pra, tani që ne kemi biseduar rreth recursions,
le të flasim pak për atë lloj bashkojë është.
Merge lloj thelb është një tjetër mënyrë për klasifikim një listë të numrave.
Dhe si funksionon ai është, me lloj Merge ju keni një listë, dhe çfarë bëjmë ne është
themi, le të ndahet në 2 gjysmave këtë.
Ne do të kandidojë parë bashkojë lloj përsëri në gjysmën e majtë,
atëherë ne do të kandidojë bashkojë lloj në gjysmën e djathtë,
dhe që na jep tani 2 gjysmave të cilat janë të renditura, dhe tani ne jemi duke shkuar për të kombinuar ato gjysmave së bashku.
Është pak e vështirë për të parë pa një shembull, kështu që ne do të shkojnë nëpër mocionet dhe shikoni se çfarë ndodh.
Pra, ju filloni me këtë listë, ne ndarë atë në 2 gjysmave.
Ne drejtuar bashkojë lloj në gjysmën e majtë të parë.
Pra, kjo është gjysma e majtë, dhe tani ne drejtuar atyre përmes kësaj liste përsëri
e cila merr kaluar në lloj shkrihen, dhe pastaj shohim, përsëri,
në anën e majtë të kësaj liste dhe ne të drejtuar lloj bashkojë në të.
Tani, ne të merrni poshtë për një listë të numrave 2,
dhe tani gjysma e majtë është vetëm 1 element të gjatë, dhe ne nuk mund të
ndarë një listë që është vetëm 1 element në gjysmë, kështu që ne vetëm të themi, pasi ne kemi 50,
e cila është vetëm 1 element, është renditur tashmë.
>> Pasi ne jemi bërë me këtë, ne mund të shohim se ne mund
lëvizin për në gjysmën e djathtë të kësaj liste,
dhe 3 është renditur gjithashtu, dhe kështu që tani që të dy gjysmave të kësaj liste janë të renditura
ne mund të bashkohen këto numra përsëri së bashku.
Kështu që ne shikojmë në 50 dhe 3; 3 është më i vogël se 50, kështu që ajo shkon në të parë dhe pastaj 50 vjen in
Tani, kjo është bërë, ne kthehemi deri në atë listë dhe kjo është lloj gjysmë të drejtë.
42 është numri atë të vetë, kështu që është renditur tashmë.
Deri tani ne krahasojmë këto 2 dhe 3 është më i vogël se 42, kështu që merr vënë në të parë,
tani 42 merr të vënë në, dhe 50 merr vënë in
Tani, që është renditur, ne do të shkojmë të gjithë rrugën prapa në krye, 1337 dhe 15.
E pra, ne tani shohim në gjysmën e majtë të kësaj liste, 1337 është në vetvete kështu që është e renditura dhe të njëjta me 15.
Deri tani ne kombinojnë këto 2 numra për të zgjidhur se lista origjinale, 15 <1337,
kështu që ajo shkon në vend të parë, pastaj shkon 1337 in
Dhe tani ne dy gjysmave të renditura të listës origjinale deri të lartë.
Dhe të gjithë ne duhet të bëni është të kombinohen këto.
Ne shohim në numrat 2 e parë të kësaj liste, 3 <15, kështu që ajo shkon në rrjet renditjes parë.
15 <42, kështu që ajo shkon in Tani, 42 <1337, që shkon in
50 <1337, kështu që ajo shkon in Dhe vini re se ne vetëm mori 2 numra off e kësaj liste.
Pra, ne nuk jemi vetëm alternuara mes 2 listave.
Ne jemi vetëm në kërkim në fillim, dhe ne jemi duke marrë elementin
kjo është më e vogël dhe pastaj të vënë atë në grup tonë.
Tani ne kemi shkrirë të gjitha gjysmave dhe ne jemi duke bërë.
>> Ndonjë pyetje rreth bashkojë lloj? Po?
[Student] Nëse kjo është ndarja në grupe të ndryshme, pse nuk e ata vetëm të ndarë një herë
dhe ju keni 3 dhe 2 në një grup? [Pjesa tjetër e pakuptueshëm pyetje]
Arsyeja - kështu që pyetja është, pse nuk mund t'i bashkojë ato vetëm në atë hapin e parë pasi kemi ato?
Arsyeja që ne mund ta bëjmë këtë, të fillojë në të majtë më të elementeve të të dy palëve,
dhe pastaj të marrë atë të vogël dhe e vënë atë në, është se ne e dimë se këto
Listat individuale janë të renditura në urdhërat.
Pra, nëse unë jam duke kërkuar në të majtë shumicën e elementeve të të dy gjysmave,
Unë e di se ata do të jenë elementet më të vogla të këtyre listave.
Kështu që unë mund të vënë ato në pika të vogla të këtij elementi listë të madhe.
Nga ana tjetër, në qoftë se unë shoh në këto 2 listave në nivelin e dytë mbi atje,
50, 3, 42, 1337 dhe 15, ata që nuk janë të renditura.
Pra, nëse unë shoh në 50 dhe 1337, unë jam duke shkuar për të vënë 50 në listën time të parë.
Por kjo nuk ka të vërtetë ka kuptim, sepse 3 është elementi më i vogël nga gjithë ata.
Pra, arsyeja e vetme që mund të bëjmë këtë hap kombinuar është për shkak se listat tona janë të renditura tashmë.
Cila është arsyeja pse ne kemi për të marrë poshtë të gjitha rrugën në fund
sepse kur kemi vetëm një numër të vetme, ju e dini se një numër të vetme
në vetvete është tashmë një listë të renditura.
>> Çdo pyetje? Jo?
Kompleksiteti? E pra, ju mund të shihni se në çdo hap ka numra në fund,
dhe ne mund të ndajnë një listë në log gjysmë n herë,
i cili është ku ne kemi marrë këtë log x n n kompleksitetit.
Dhe ju do të shihni në rastin më të mirë për lloj Merge është n log n, dhe kjo ndodh pikërisht kështu
se rasti më i keq, ose Ω atje, edhe n log n.
Diçka për të mbajtur në mendje.
Moving on, le të shkojnë në ndonjë skedar super themelor I / O.
Nëse keni shikuar në Scramble, ju do të vëreni kemi pasur një lloj të sistemit
ku ju mund të shkruani në një log file në qoftë se ju lexoni me anë të kodit.
Le të shohim se si ju mund ta bëni këtë.
E pra, ne kemi fprintf, të cilat ju mund të mendoni vetëm si printf,
por vetëm shtypjen në një skedar në vend, dhe kështu f në fillim.
Ky lloj i kodit deri këtu, ajo nuk është, si ju mund të keni parë në Scramble,
ajo shkon përmes 2-dimensionale array printim tuaj nga rresht nga rresht se çfarë janë numrat.
Në këtë rast, printf printime jashtë për terminalin tuaj ose atë që ne e quajmë prodhimi standard seksion.
>> Dhe tani, në këtë rast, të gjithë ne duhet të bëni është të zëvendësojë printf me fprintf,
tregoni se çfarë ju doni fotografi të shkruar për të, dhe në këtë rast vetëm ajo printon atë për këtë dosje
në vend të shtypjes atë për terminalin tuaj.
E pra, atëherë kjo ngre pyetjen: Ku nuk kemi marrë këtë lloj të dosjes nga, apo jo?
Kemi kaluar hyni te kete fuction fprintf por ne nuk kishte asnjë ide se ku ai erdhi nga.
E pra, në fillim të kodit, ajo që ne kishim ishte kjo copë e kodit gjatë këtu,
e cila në thelb thotë se hapur fotografi quan log.txt.
Çfarë bëjmë ne pas kësaj është që ne duhet të bëni të sigurtë që skedari hapet vërtetë sukses.
Pra, ajo mund të dështojnë për arsye të shumta, ju nuk keni hapësirë ​​të mjaftueshme në kompjuterin tuaj, për shembull.
Kështu që është gjithmonë e rëndësishme para se të bëni ndonjë operacione me dosjen
që ne të kontrolloni nëse kjo dosje u hap me sukses.
Pra, çfarë se një, kjo është një argument për fopen, mirë, ne mund të hapur një skedë në shumë mënyra.
Ajo që ne mund të bëjmë është, që ne mund të kalojë atë w, që do të thotë të pranoj dosjen në qoftë se ajo del tashmë,
Ne mund të kalojë një A, që ata append në fund të file në vend mbizotërues atë,
ose ne mund të specifikojë r, që do të thotë, le të hapë dosjen si read-only.
Pra, nëse programi përpiqet të bëjë ndonjë ndryshim në dosjen,
bërtas me ta dhe nuk le ta bëjë atë.
Së fundi, pasi ne jemi bërë me dosjen, bërë duke bërë operacione në të,
ne kemi nevojë për të siguruar që ne të mbyllë dosjen.
Dhe kështu në fund të programit tuaj, ju do të kalojnë ato përsëri
Vlerësoni këtë fotografi që keni hapur, dhe vetëm afër atë.
Pra, kjo është diçka e rëndësishme që ju duhet të bëni të sigurtë që ju bëni.
Pra, mos harroni ju mund të hapur një skedar, atëherë ju mund të shkruani në dosjen,
të bëjë operacione në dosjen, por pastaj ju duhet të mbyllë dosjen në fund.
>> Çdo pyetje në dosjen themelor I / O? Po?
[Pyetja Student, pakuptueshëm]
Të drejtë këtu. Pyetja është, ku e bën këtë fotografi log.txt duket?
E pra, nëse ju vetëm t'i jepte log.txt, ajo krijon atë në të njëjtën directory si ekzekutues.
Pra, nëse you're - >> [Pyetja Student, pakuptueshëm]
Po. Në të njëjtën dosje, ose në të njëjtën directory si ju e quani atë.
Tani, kujtesës rafte, dhe tog.
Pra, si është e kujtesës hedhur në kompjuter?
E pra, ju mund të imagjinoni kujtimin e këtij lloj si bllok këtu.
Dhe në kujtim ne kemi atë që quhet sasi mbërthyer atje, dhe rafte që është atje poshtë.
Dhe grumbull rritet në rënie dhe rafte rritet lart.
Pra, si Tommy përmendur - oh, mirë, dhe ne kemi këto të tjerë 4 segmente të cilat unë do të marrë në një të dytë -
Siç Tommy tha më parë, ju e dini se si funksionet e tij e quajnë veten e tyre dhe e quajnë njëri-tjetrin?
Ata ndërtojnë këtë lloj të kornizës rafte.
E pra, në qoftë se thirrjet kryesore foo, foo merr vënë në rafte.
Foo quan bar, bar të marrë të vënë në rafte, dhe që merr vënë në rafte pas.
Dhe, ndërsa ata të kthehen, ata çdo të marrë marrë off rafte.
Çfarë secilin nga këto vende dhe memorie të mbajë?
Mirë, të lartë, e cila është segmenti teksti, përmban programi vetë.
Pra në kodin e makinës, që është atje, sapo ju të hartojnë programin tuaj.
Tjetra, çdo initialized variablave globale.
>> Pra, ju keni variablave globale në programin tuaj, dhe ju thoni si, a = 5,
që merr vënë në atë segment, nën dhe të drejtën që,
keni ndonjë dhënat uninitialized globale, e cila është vetëm int a,
por ju nuk e thonë se kjo është e barabartë me asgjë.
Realizuar këto janë variabla globale, kështu që ata janë jashtë kryesore.
Pra, kjo do të thotë çdo ndryshore globale që janë shpallur, por nuk janë initialized.
Pra, çfarë është në tog? Memory ndarë përdorur malloc, të cilat ne do të merrni në një pak.
Dhe së fundi, me rafte keni ndonjë variablave lokale
dhe çdo funksionet që ju mund të telefononi në ndonjë nga parametrat e tyre.
Gjëja e fundit, ju nuk mund të vërtetë duhet të dini se çfarë të bëjë mjedis të ndryshueshëm,
por sa herë që ju të drejtuar programin, nuk është diçka e lidhur, si
kjo është emrin e personit i cili u zhvillua të programit.
Dhe kjo do të jetë lloj i në fund.
Në kushtet e adresave kujtesës, të cilat janë vlerat hexadecimal,
vlerat në fillim të lartë në 0, dhe ata të shkojnë të gjithë rrugën poshtë në fund.
Në këtë rast, në qoftë se ju jeni në sistemin 32-bit,
adresa në fund do të jetë 0x, e ndjekur nga af, sepse kjo është 32 bit,
e cila është 8 bytes, dhe në këtë rast 8 bytes korrespondon me 8 numra heksadecimal.
Pra, këtu poshtë ju jeni do të ketë, si, 0xffffff, dhe deri atje ju jeni do të ketë 0.
Pra cilat janë pointers? Disa prej jush nuk mund të ketë mbuluar këtë në seksionin e parë.
por ne nuk shkoni mbi atë në leksion, kështu që një akrep është vetëm një lloj të dhënave
cilat dyqane, në vend të një lloj të vlerës si 50, ajo ruan adresën e lokacionit disa në kujtesë.
Si kjo kujtim [pakuptueshëm].
Pra, në këtë rast, ajo që ne kemi është, ne kemi një tregues për një numër të plotë apo * int,
dhe ajo përmban këtë adresë hexadecimal e 0xDEADBEEF.
>> Kështu që ajo që ne kemi është, tani, kjo tregon treguesin në disa vend në kujtesë,
dhe kjo është vetëm një, vlera 50 është në këtë vend kujtesës.
Në disa 32-bit sistemeve, në të gjitha 32-bit sistemeve, pointers marrë bit 32 ose 4 bytes.
Por, për shembull, në një sistem të 64-bit, 64 bit janë pointers.
Pra, kjo është diçka që ju do të dëshironi që të mbani në mend.
Pra, në një sistem të fund-bit, një akrep është bit në fund gjatë.
Pointers janë lloj i vështirë për të tretet, pa gjëra ekstra,
kështu që le të kalojnë nëpër një shembull të alokimit kujtesës dinamike.
Çfarë alokimi dinamike memorie bën për ju, apo atë që ne e quajmë malloc,
kjo ju lejon të akordojë një lloj të të dhënave jashtë e caktuar.
Pra, kjo është lloj i të dhënave më të përhershëm për kohëzgjatjen e programit.
Sepse siç e dini, nëse ju deklaroj X brenda një funksion, dhe se kthimi funksion,
ju nuk keni qasje në të dhënat që është ruajtur në x.
Çfarë pointers le të bëjmë është se ata le të ruajë vlerat e kujtesës ose dyqan
në një segment të ndryshme të memories, përkatësisht grumbull.
Tani sapo kthehemi nga funksioni, për aq kohë sa ne kemi një tregues
në atë vend në kujtesë, atëherë çfarë mund të bëjmë është që ne vetëm mund të shikoni në vlerat atje.
Le të shikojmë një shembull: Kjo është paraqitjen tonë kujtesës përsëri.
Dhe ne e kemi këtë funksion, kryesore.
Çfarë ajo nuk është - në rregull, në mënyrë të thjeshtë, apo jo? - Int x = 5, kjo është vetëm një ndryshore në rafte në kryesore.
>> Nga ana tjetër, tani ne deklarojë një tregues i cili e quan giveMeThreeInts funksion.
Dhe kështu që tani ne do të shkojmë në këtë funksion dhe ne të krijojë një kornizë të re rafte për të.
Megjithatë, në këtë kuadër rafte, ne deklarojmë int temp *,
e cila në mallocs 3 integers për ne.
Kështu madhësia e int do të na japë sa bytes ky është int,
dhe malloc na jep se bytes shumë hapësirë ​​në tog.
Pra, në këtë rast, ne kemi krijuar hapësirë ​​të mjaftueshme për 3 integers,
dhe tog është rruga deri atje, e cila është arsyeja pse unë kam tërhequr atë lartë deri.
Pasi ne jemi bërë, ne kemi ardhur përsëri deri këtu, ju duhet vetëm 3 ints kthye,
dhe kjo e kthen adresën, në këtë rast mbi ku se kujtesa është.
Dhe ne kemi ngritur akrep kaloni =, dhe atje kemi vetëm tregues tjetër.
Por ajo që kthimet funksion është bërë pirg këtu dhe zhduket.
Pra temp zhduket, por ne ende mbajnë adresën e ku
ato 3 integers janë në brendësi të mbetet.
Pra, në këtë grup, pointers janë scoped në nivel lokal për kuadër bërë pirg,
por kujtesës në të cilën ata i referohen është në tog.
>> Bën që të bëjnë kuptim?
[Student] Mund të ju përsëris se? >> [Jozefi] Po.
Pra, nëse unë kthehem vetëm pak, ju shihni se temp ndarë
disa kujtesës në grumbull deri atje.
Pra, kur ky funksion, giveMeThreeInts Kthim, kjo rafte këtu do të zhduket.
Dhe me atë ndonjë të variablave, në këtë rast, ky tregues që është ndarë në kuadër bërë pirg.
Kjo do të zhduket, por që ne u kthye Temp
dhe ne kemi vendosur treguesin = temp, akrep po tani do të vinte në kujtesën njëjtin vend si temp ishte.
Deri tani, edhe pse kemi humbur temp, që akrep lokale,
ne ende ruajnë adresën e kujtesës së asaj që është treguar në brendësi të kësaj akrep ndryshueshme.
Pyetje? Kjo mund të jetë lloj i një temë konfuze në qoftë se ju nuk keni shkuar mbi atë në seksionin.
Ne mund, TF tuaj patjetër do të shkojnë mbi atë dhe sigurisht ne mund të përgjigjem pyetjeve
në fund të seancës shqyrtim për këtë.
Por kjo është lloj i një teme komplekse, dhe kam shumë shembuj që do të shfaqen
që do t'ju ndihmojë të qartësuar se çfarë në të vërtetë janë pointers.
>> Në këtë rast, pointers janë ekuivalente me vargjeve,
kështu që unë mund të përdorni vetëm këtë tregues si të njëjtën gjë si një grup int.
Kështu që unë jam indeksimin në 0, dhe ndryshimin integer parë të 1,
ndryshimin integer dytë tek 2, dhe integer 3 tek 3.
Pra, më shumë në pointers. E pra, kujtoj Binky.
Në këtë rast ne kemi ndarë një tregues, ose ne shpalli një tregues,
por fillimisht, kur unë sapo shpalli një tregues, kjo nuk është vënë për të kudo në kujtesë.
Kjo është vetëm vlerat e plehrave në brendësi të saj.
Kështu që unë nuk kam asnjë ide se ku ky tregues është treguar për të.
Ajo ka një adresë e cila është e mbushur vetëm me të 0 dhe 1 e ku u shpall fillimisht.
Unë nuk mund të bëjë asgjë me këtë deri sa unë e quaj malloc në atë
dhe pastaj kjo më jep një hapësirë ​​të vogël në grumbull, ku unë mund të vënë vlerat brenda.
Pastaj përsëri, unë nuk e di se çfarë është në brendësi të kësaj memorie.
Pra, gjëja e parë që unë duhet të bëni është të kontrolloni nëse sistemi kishte kujtesë të mjaftueshme
të më jepni Prapa 1 integer në vendin e parë, e cila është arsyeja pse unë jam duke bërë këtë kontroll.
Nëse akrep është null, që do të thotë se ajo nuk kishte hapësirë ​​të mjaftueshme apo ndonjë gabim tjetër ndodhur,
kështu që unë duhet të dalë jashtë programit tim.
Por në qoftë se ai e bëri sukses, tani unë mund të përdorin atë treguesin
dhe çfarë treguesin * nuk është ajo ndjek kur adresa është
ku se vlera është, dhe ajo vendos të barabartë me 1.
Kështu gjatë këtu, ne jemi duke kontrolluar në qoftë se kujtesa ekzistuar.
>> Pasi ju e dini se ekziston, ju mund të vënë në atë
çfarë vlera që ju dëshironi për të vënë në atë, në këtë rast 1.
Pasi ne jemi bërë me atë, ju keni nevojë për të liruar atë treguesin
sepse ne kemi nevojë për të marrë përsëri në sistemin që kujtesës që keni kërkuar në vendin e parë.
Sepse kompjuteri nuk e di se kur ne jemi bërë me të.
Në këtë rast ne jemi duke thënë në mënyrë eksplicite atë, në rregull, ne jemi bërë me atë memorie.
Nëse disa proces tjetër ka nevojë për atë, disa program tjetër ka nevojë për atë, të ndjehen të lirë për të shkuar përpara dhe për të marrë atë.
Ajo që ne mund të bëjmë është që ne mund të merrni vetëm adresën e variablave lokale në grup.
Pra, int x është brenda kornizës së bërë pirg kryesor.
Dhe kur ne e përdorim këtë simbol, kjo dhe operator, atë që nuk është
ajo merr x dhe x është vetëm disa të dhëna në kujtesë, por ajo ka një adresë.
Është e vendosur diku. Pra, duke e quajtur & x, çka kjo nuk është ajo na jep adresën e x.
Duke bërë këtë, ne jemi duke e bërë pikë akrep ku x është në kujtesë.
Tani ne thjesht nuk diçka si * x, ne jemi duke shkuar për të marrë 5 shpinën.
Ylli është quajtur dereferencing atë.
Ju ndiqni adresën dhe që ju të merrni vlerën e saj ruajtur atje.
>> Çdo pyetje? Po?
[Student] Nëse ju nuk e bëni gjënë e 3-mprehtë, e bën atë akoma përpilojë?
Po. Nëse ju nuk e bëni gjënë e 3-akrep, ajo ende do të hartojë,
por unë do të ju tregojnë se çfarë ndodh në një të dytë, dhe pa bërë që,
kjo është ajo që ne e quajmë një rrjedhje kujtim. Ju nuk jeni i dhënë të sistemit
mbështesë kujtesën e saj, kështu që pas një kohë programi do të grumbullohen
kujtesës që nuk është përdorur, dhe asgjë tjetër mund ta përdorni atë.
Nëse e keni parë ndonjëherë me Firefox 1.5 milion kilobytes në kompjuterin tuaj,
në detyrën e menaxherit, kjo është ajo që po ndodh.
Ju keni një rrjedhje kujtesës në programin që ata nuk janë të trajtimit.
Pra, si e bën punën treguesin aritmetike?
E pra, aritmetike akrep është lloj i indeksimit si në një rrjet.
Në këtë rast, unë kam një tregues, dhe atë që unë kam bërë është bërë pikë tregues për elementin e parë
të këtij grup prej 3 integers që unë kam ndarë.
Deri tani çfarë të bëj, akrep yll ndryshon vetëm elementin e parë në listë.
Star treguesin 1 pikë mbi këtu.
Pra, tregues është mbi këtu, akrep 1 është mbi këtu, akrep 2 është këtu.
>> Pra, vetëm duke shtuar 1 është e njëjta gjë si lëviz përgjatë këtij grup.
Ajo që ne bëjmë është, kur ne bëjmë treguesin 1 ju të merrni adresën gjatë këtu,
dhe në mënyrë që të merrni vlerën në këtu, ju vënë një yll në tërë nga shprehjes
të dereference atë.
Pra, në këtë rast, unë jam duke vendin e parë në këtë grup në 1,
vend të dytë për 2, dhe vendin e tretë me 3.
Atëherë çfarë unë jam duke bërë këtu është se unë jam shtypjen treguesin tonë +1,
të cilat vetëm më jep 2.
Tani unë jam bën rritjen treguesin, kështu treguesin e barabartë me treguesin +1,
që lëviz atë përpara.
Dhe kështu që tani, nëse unë të shtypura nga treguesin +1, akrep +1 tani është 3,
e cila në këtë rast printime nga 3.
Dhe në mënyrë që diçka të lirë, tregues që unë jap atë
duhet të vënë në fillim të array që kam marrë prapa nga malloc.
Pra, në këtë rast, në qoftë se unë do të thërrasë 3 të drejtë këtu, kjo nuk do të jetë e drejtë,
sepse kjo është në mes të grup.
Unë duhet të zbres për të marrë në lokacionin origjinal
spot fillestare të parë para se unë mund të lirë atë.
Pra, këtu është një shembull më shumë të përfshira.
Në këtë rast, ne jemi të shpërndarjes 7 shkronja në një grup karakter.
>> Dhe në këtë rast ajo që ne po bëjmë është që ne jemi duke looping mbi 6 e parë të tyre,
dhe ne jemi të vendosur ato në Z.
Pra, për int i = 0, i> 6, i + +,
Pra, akrep + i vetëm do të na japë, në këtë rast,
akrep, akrep +1, akrep +2, +3 akrep, dhe kështu me radhë e kështu me radhë në lak.
Atë që do të bëjë është ajo merr atë adresë, dereferences atë për të marrë vlerën,
dhe ndryshimet që vlera në Z.
Pastaj, në fund mos harroni kjo është një varg, apo jo?
Të gjitha vargjet duhet të përfundojë me karakter null ndërprerjen.
Pra, ajo që unë bëj është në treguesin 6 kam vënë karakterin null Terminator in
Dhe tani ajo që unë jam duke bërë në thelb mbi këtu është zbatuar printf për një varg, e drejtë?
>> Pra, kur nuk printf tani kur është arritur fundin e një varg?
Kur ajo hits karakterin null pavlefshme.
Pra, në këtë rast, pika origjinale e mi treguesin në fillim të këtij grup.
Unë shtypura karakterin e parë jashtë. Unë lëvizur atë mbi një.
Unë të shtypura atë karakterin jashtë. Unë lëvizin atë përsipër.
Dhe unë të vazhdojmë të bëjmë këtë deri sa unë të arritur në fund.
Dhe tani në fund * treguesin do dereference këtë dhe për të marrë karakterin null pavlefshme mbrapa.
Dhe kështu, ndërsa loop im shkon vetëm kur kjo vlerë nuk është karakteri null ndërprerjen.
Pra, tani unë dalje nga ky lak.
Dhe kështu që nëse unë zbres 6 nga ky akrep,
Unë kthehem të gjithë rrugën në fillim.
Mos harroni, unë jam duke bërë këtë, sepse unë kam për të shkuar në fillim në mënyrë të lirë atë.
>> Pra, unë e di se ishte shumë. A ka ndonjë pyetje?
Ju lutem, po?
[Pyetja Student pakuptueshëm]
Mund të ju them se fort? Më vjen keq.
[Student] Në slide fundit drejtë para se të liruar në treguesin,
ku janë në fakt ndryshimin e vlerës së akrep?
[Joseph] Pra, të drejtë këtu. >> [Student] Oh, në rregull.
[Joseph] Pra, unë kam një tregues minus minus, djathtas,
i cili lëviz prapa një gjë, dhe pastaj kam liruar atë,
sepse ky tregues duhet të theksohet në fillim të array.
[Student] Por kjo nuk do të jetë e nevojshme që ju kishte ndalur pas atë linjë.
[Joseph] Pra, në qoftë se unë kishte ndalur pas kësaj, kjo do të konsiderohet si një rrjedhje kujtim,
sepse nuk e kam drejtuar pa pagesë.
[Student] I [pakuptueshëm] pas tre linjave të para, ku keni pasur treguesin 1 [] pakuptueshëm.
[Joseph] Uh-huh. Pra, çfarë është pyetja atje?
Më vjen keq. Jo, jo. Shkoni, shkoni, ju lutem.
[Student] Pra, ju nuk jeni duke ndryshuar vlerën e pointers.
Ju nuk do të kishte pasur të bëjë treguesin minus minus.
[Joseph] Po, pikërisht.
Pra, kur të bëj treguesin 1 dhe 2 treguesin,
Unë nuk jam duke bërë treguesin e barabartë me treguesin +1.
Pra, tregues qëndron vetëm duke treguar në fillim të array.
Kjo është vetëm kur të bëj plus plus se ajo përcakton vlerën kthehet brenda treguesin,
se në fakt ajo lëviz këtë së bashku.
Dakord.
Më shumë pyetje?
>> Përsëri, në qoftë se kjo është lloj i madhe, kjo do të mbulohet në seancë.
Pyetni shokët tuaj të mësimdhënies rreth saj, dhe ne mund të përgjigjem pyetjeve në fund.
Dhe zakonisht ne nuk doja të bëj këtë gjë minus.
Kjo duhet të kërkojë mua mbajtja e sa kam kompensuar në rrjet.
Pra, në përgjithësi, kjo është vetëm për të shpjeguar se si punon aritmetike pointer.
Por ajo që ne zakonisht të doja të bëni është që ne si për të krijuar një kopje të kursorit,
dhe pastaj ne do të përdorim atë kopje kur ne jemi duke lëvizur rreth në varg.
Pra, në këto rast se ju përdorni kopje të shtypur të gjithë tekstin,
por ne nuk duhet të bëjmë ashtu si treguesin minus 6 ose mbajnë gjurmët e sa kemi lëvizur në këtë,
vetëm për shkak se ne e dimë se pika jonë origjinal është theksuar ende në fillim të listës
dhe të gjitha që ne ndryshohet ishte kjo kopje.
Pra, në përgjithësi, ndryshojnë kopje të treguesin tuaj origjinal.
Mos u mundoni të lloj si - don 't ndryshoj kopje origjinale.
Duke u përpjekur për të ndryshuar vetëm kopjet origjinale të juaj.
Pra, ju vëreni kur ne të kalojë në vargun printf
ju nuk keni për të vënë një yll në frontin e saj si ne e bëmë me të gjitha dereferences tjera, apo jo?
Pra, nëse ju të shtypura nga tërë vargu% s pret është një adresë,
dhe në këtë rast një akrep ose në këtë rast si një grup të karaktereve.
>> Karaktere, char * s, dhe vargjeve janë e njëjta gjë.
Tregues është që të karaktereve, dhe vargjeve karakter janë e njëjta gjë.
Dhe kështu, të gjithë ne duhet të bëni është të kalojë në treguesin.
Ne nuk duhet të kalojë në si treguesin * ose diçka të tillë.
Pra, vargjeve dhe pointers janë e njëjta gjë.
Kur ju jeni duke bërë diçka si x [y] mbi këtu për një grup,
ajo që është bërë nën kapuç është ajo e thënë, në rregull, kjo është një grup karakter,
kështu që kjo është një akrep.
Dhe kështu x janë e njëjta gjë,
dhe kështu atë që bën është ajo shton y me x,
e cila është e njëjta gjë si lëvizur përpara në kujtesë se shumë.
Dhe tani x + y na jep një lloj adresë,
dhe ne dereference adresën ose ndiqni arrow
ku se lokacioni në kujtesë është dhe ne kemi marrë vlerën nga ky vend në kujtesë.
Pra, kështu që këto dy janë saktësisht e njëjta gjë.
Kjo është vetëm një sheqer sintaksore.
Ata bëjnë të njëjtën gjë. Ata janë vetëm syntactics të ndryshme për njëri-tjetrin.
>> Pra, çfarë mund të shkojnë keq me pointers? Ashtu si, shumë. Rregull. Pra, gjëra të këqija.
Disa gjëra të këqija që ju mund të bëni nuk janë kontrolluar nëse thirrja juaj malloc kthen null, apo jo?
Në këtë rast, unë jam duke kërkuar për të dhënë sistemin mua - çfarë është ky numër?
Ashtu si 2 miliardë herë 4, sepse madhësia e një numër të plotë është 4 bytes.
Unë jam duke kërkuar atë për të si 8000000000 bytes.
Sigurisht që kompjuteri im nuk do të jetë në gjendje të më jepni atë përsëri shumë e kujtesës.
Dhe ne nuk e kontrolloni nëse kjo është null, kështu që kur ne të përpiqemi për të dereference atë mbi atje -
ndiqni arrow ku ajo do të - ne nuk kemi atë memorie.
Kjo është ajo që ne e quajmë dereferencing një tregues null.
Dhe kjo në thelb ju bën të segfault.
Kjo është një nga mënyrat që ju mund segfault.
Gjëra të tjera të këqija që ju mund të bëni - oh mirë.
Kjo ishte një tregues dereferencing null. Rregull.
Gjëra të tjera të këqija - mirë, për të rregulluar që ju vetëm vënë një kontroll në atje
që kontrollon nëse kursori është i pavlefshëm
dhe dalin nga programi nëse ndodh që malloc kthen një tregues null.
Kjo është komik RockSonte. Njerëzit e kuptojnë atë tani. Lloj të.
>> Pra, memorie. Dhe unë shkova mbi këtë.
Ne jemi duke bërë thirrje malloc në një lak, por çdo herë që ne e quajmë malloc
ne jemi duke humbur gjurmët e ku ky tregues është treguar,
sepse ne jemi clobbering atë.
Pra, thirrja fillestare për malloc jep memorie gjatë këtu.
Pointers mia tregues për këtë.
Tani, unë nuk e liruar atë, kështu që tani unë e quaj malloc përsëri.
Tani ajo pikë gjatë këtu. Tani kujtesa ime është vënë mbi këtu.
Vënë këtu. Vënë këtu.
Por unë kam humbur gjurmët e adresave të të gjithë kujtesën e gjatë këtu që unë ndarë.
Dhe kështu që tani unë nuk kam asnjë referencë ndaj tyre më.
Pra, unë nuk mund të lirë ata jashtë këtë lak.
Dhe kështu, në mënyrë për të rregulluar diçka si kjo,
në qoftë se ju harroni të kujtesës të lirë dhe që ju të merrni këtë rrjedhje kujtesës,
Ju keni për të liruar kujtesës brenda këtij lak një herë ju jeni bërë me të.
E pra, kjo është ajo që ndodh. Unë e di shumë prej jush urrejnë këtë.
Por tani - yay! Ju merrni si 44.000 kilobytes.
Pra, ju liruar atë në fund të lak,
dhe që do të vetëm të lirë e kujtesës çdo kohë.
Në thelb, programi juaj nuk ka një rrjedhje kujtim më.
>> Dhe tani diçka tjetër që ju mund të bëni është liruar disa kujtesës që ju keni kërkuar për të dy.
Në këtë rast, ju malloc diçka, ju të ndryshojë vlerën e saj.
Ju liruar një herë sepse ju tha se ju janë bërë me të.
Por atëherë ne liruar atë përsëri.
Kjo është diçka që është shumë e keqe.
Kjo nuk do të fillimisht segfault,
por pas një kohe ajo që kjo nuk është e dyfishtë liruar Kjo korrupton strukturën tuaj tog,
dhe ju do të mësoni pak më shumë në lidhje me këtë në qoftë se ju zgjidhni për të marrë një klasë si CS61.
Por në thelb pas një, ndërsa kompjuteri juaj është duke shkuar për të marrë hutuar
për atë që vendet ku janë kujtesës dhe ku është e ruajtur -
ku të dhënat është ruajtur në kujtesë.
Dhe kështu duke liruar një tregues dy herë është një gjë e keqe që ju nuk dëshironi të bëni.
>> Gjëra të tjera që mund të shkojnë keq nuk është përdorur sizeof.
Pra, në këtë rast ju malloc 8 bytes,
dhe kjo është e njëjta gjë si dy integers, apo jo?
Pra, kjo është krejtësisht e sigurt, por është ajo?
E pra, si Lucas biseduar rreth në arkitektura të ndryshme,
integers janë të gjatesite e ndryshme.
Pra, në aplikim që ju jeni duke përdorur, integers janë rreth 4 bytes,
por në ndonjë sistem tjetër që ata mund të jenë 8 byte ose ata mund të jenë 16 bytes.
Pra, në qoftë se unë vetëm përdorin këtë numër gjatë këtu,
ky program mund të punojnë në aplikim,
por kjo nuk do të siguroj kujtesë të mjaftueshme në ndonjë sistem tjetër.
Në këtë rast, kjo është ajo që operatori sizeof është përdorur për të.
Kur ne e quajmë sizeof (int), atë që kjo nuk është
kjo na jep përmasat e një numër të plotë në sistemin që programi është i rrjedhshëm.
Pra, në këtë rast, sizeof (int) do të kthehet në diçka si 4 të pajisjes,
dhe tani kjo 4 vullneti * 2, i cili është 8,
e cila është vetëm sasia e hapësirës së nevojshme për dy integers.
Në një sistem tjetër, nëse një int është si 16 ose 8 bytes bytes,
ajo vetëm do të kthehen bytes mjaftueshme për të ruajtur atë sasi.
>> Dhe së fundi, structs.
Pra, në qoftë se ju të kërkuar për të ruajtur një bord sudoku në kujtesë, si mund ta bëjmë këtë?
Ju mund të mendoni e si një variabël për gjëja e parë,
një ndryshore për gjë të dytë, një variabël për gjë të tretë,
një ndryshore për gjë katërt - e keqe, apo jo?
Pra, një përmirësim ju mund të bëni në krye të kësaj është të bëjë një 9 x 9 koleksion.
Kjo është në rregull, por çka nëse do të donit që të lidhen gjëra të tjera me bordin sudoku
si ajo vështirësia e bordit është,
ose, për shembull, se çfarë rezultati juaj është, ose se sa kohë është marrë ju për të zgjidhur këtë bord?
E pra, çfarë mund të bëni është që ju mund të krijoni një struct.
Ajo që unë jam duke thënë është në thelb unë jam përcaktimin e kësaj strukture gjatë këtu,
dhe unë jam duke përcaktuar një bord sudoku i cili përbëhet nga një bord që është 9 x 9.
>> Dhe atë që ka ajo ka pointers në emër të nivelit.
Ajo gjithashtu ka X dhe Y, të cilat janë koordinatat e ku jam unë tani.
Ajo gjithashtu ka kaluar koha [pakuptueshëm], dhe ajo ka numrin e përgjithshëm të lëviz kam futur deri tani.
Dhe kështu në këtë rast, unë mund të grupojnë një bandë e tërë e të dhënave në vetëm një strukturë
në vend që atë si fluturon rreth në si variabla të ndryshme
se unë nuk mund të vërtetë të mbajnë gjurmët e.
Dhe kjo na lejon të kemi vetëm një sintaksë të këndshme për lloj referenca gjëra të ndryshme në brendësi të këtij struct.
Unë vetëm mund të bëjë board.board, dhe unë të marrë bordit sudoku mbrapa.
Board.level, unë të marrë se sa vështirë është.
Board.x dhe board.y jepni koordinatat e ku unë mund të jetë në bord.
Dhe kështu që unë jam duke hyrë në atë që ne e quajmë fushat në struct.
Kjo përcakton sudokuBoard, e cila është një lloj që kam.
Dhe tani ne jemi këtu. Unë kam një ndryshore të quajtur "bordi" e sudokuBoard tipit.
Dhe kështu që tani unë mund të përdorni të gjitha fushat që përbëjnë këtë strukturë mbi këtu.
>> Çdo pyetje në lidhje me structs? Po?
[Student] Për int x, y, ju deklaruar të dy në një rresht? >> [Joseph] Uh-huh.
[Student] Pra, mund ta bëni vetëm se me të gjithë ata?
Ashtu si në x, y presje herë që në total?
[Joseph] Po, ju mund të patjetër të bëni këtë, por arsyeja që unë vënë x dhe y në të njëjtën linjë -
dhe pyetja është pse ne vetëm mund ta bëjë këtë në të njëjtën linjë?
Pse nuk kemi vetëm të vënë të gjitha këto në të njëjtën linjë është
x dhe y janë të lidhura me njëri-tjetrin,
dhe kjo është vetëm stilistikisht më të saktë, në një kuptim,
sepse ajo është grupuar dy gjëra në të njëjtën linjë
një lloj si të bëjnë të njëjtën gjë.
Dhe unë vetëm këto ndarë veç e veç. Kjo është vetëm një gjë e stil.
Kjo funksionalisht bën asnjë ndryshim whatsoever.
Çdo pyetje të tjera në structs?
Ju mund përcaktojnë një Pokedex me një struct.
Një Pokemon ka një numër të dhe ajo ka një letër, një pronar, një tip.
Dhe pastaj, nëse ju keni një rrjet të Pokemon, ju mund të bëni një Pokedex, e drejtë?
Mirë, cool. Pra, pyetjet mbi structs. Ata janë të lidhur me structs.
>> Së fundi, GDB. Çfarë do të ju lejojnë të bëni Gdb? Kjo ju lejon të korrigjoj programin tuaj.
Dhe në qoftë se ju nuk e keni përdorur gdb, unë do të rekomanduar shikuar shkurtër
dhe vetëm duke shkuar mbi atë Gdb është, se si ju punoni me atë, se si ju mund ta përdorni atë,
dhe provë atë në një program.
Dhe kështu ajo Gdb ju lejon të bëni është ajo lejon pauzë [] deri pakuptueshëm programin tuaj
dhe një linjë praktike.
Për shembull, unë dua të ekzekutimit në pushim si linjë 3 të programit tim,
dhe, ndërsa unë jam në linjë 3 Unë mund të shtypura nga të gjitha vlerat që janë atje.
Dhe kështu që ajo që ne e quajmë si heshti në një linjë
po ne e quajmë këtë vënë një breakpoint në atë linjë
dhe pastaj ne mund të shtypura nga variablat në gjendjen e programit në atë kohë.
>> Ne mund të pastaj nga atje hap përmes programit line-nga-line.
Dhe atëherë ne mund të shikojmë në gjendjen e rafte në atë kohë.
Dhe kështu në mënyrë që të përdorni GDB, atë që ne bëjmë është që ne e quajmë tingulli në dosjen C,
por ne duhet të kalojë atë-ggdb flamurin.
Dhe një herë ne jemi bërë me atë ne vetëm të kandidojë gdb në dosjen rezultojë.
Dhe kështu që ju të merrni disa masë si të tekstit si kjo,
por me të vërtetë të gjithë ju duhet të bëni është të shkruani në komandat në fillim.
Pushim kryesore vë një breakpoint në kryesore.
Lista e 400 liston rreshta të kodit rreth linjës 400.
Dhe kështu në këtë rast ju mund të shikoni përreth dhe thonë, oh,
Unë dua të vendosur një breakpoint në linjë 397, e cila është kjo linjë,
dhe pastaj programi juaj shkon në atë hap dhe ajo do të thyejnë.
Ajo do të pauzë atje, dhe ju mund të shtypura jashtë, për shembull, vlera e të ulët apo të lartë.
Dhe kështu që nuk janë një bandë e komandave që ju duhet të dini,
dhe kjo do slideshow të shkojnë deri në faqen e internetit,
kështu që nëse ju vetëm dëshironi të referimit këto apo si të vënë ato në fletë tuaj mashtrojnë, mos ngurroni.
>> Cool. Kjo ishte Quiz Rishikimi 0, dhe ne do të rrinë përreth nëse keni ndonjë pyetje.
Dakord.
>> [Duartrokitje]
>> [CS50.TV]