[Powered by Google Translate] [Recenze] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [To je CS50.] [CS50.TV]
>> Ahoj, všichni.
Vítejte na přezkoumání zasedání pro Quiz 0, který se koná tuto středu.
Co budeme dělat dnes večer, jsem s dalšími 3 TFS,
a společně budeme procházet přezkum toho, co jsme udělali v průběhu tak daleko.
Nebude to být 100% vyčerpávající, ale měl by vám lepší představu
z toho, co už máte, to, co budete ještě potřebovat ke studiu před středou.
A neváhejte zvednout ruku s dotazy, jak budeme spolu,
ale mějte na paměti, že budeme mít také trochu času na konci roku
pokud se dostaneme až s několika minut náhradních dělat obecných otázek,
takže mějte na paměti, že, a tak budeme začít od začátku s týdnu 0.
>> [Kvíz 0 recenzi!] [Část 0] [Lexi Ross] Ale dříve než my, že Pojďme mluvit o
logistiky kvízu.
>> [Logistics] [Quiz se uskuteční ve středu 10/10 namísto přednášky]
>> [(Viz http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf pro podrobnosti)] Je ve středu 10. října.
>> To je to středa, a pokud jdete na tuto adresu URL zde,
který je také přístupný z CS50.net-tam odkaz na to,
můžete zobrazit informace o tom, kde jít na základě
Vaše příjmení nebo školy příslušnost, jakož i
to řekne, co přesně ten kvíz bude týkat a typy otázek, které budete dostat.
Mějte na paměti, že budete mít také možnost zkontrolovat pro kvíz v sekci,
takže vaše TFS měla jít přes některé problémy praxe,
a to je další dobrá šance vidět, kde jste ještě potřebovat ke studiu až na kvíz.
Začněme na začátku s Bytes 'n' kousky.
Nezapomeňte bit je jen 0 nebo 1,
a byte je sbírka 8 těchto bitů.
Pojďme se podívat na této kolekce bitů tady.
Měli bychom být schopni zjistit, kolik bitů je.
Pokud budeme počítat, že je to jen 8 z nich, osm 0 nebo 1 ks.
A protože tam je 8 bitů, to je 1 byte,
a pojďme převést na šestnáctkové.
Hexadecimální je základ 16, a je to docela snadné převést
číslo v binární, což je to, co to je, aby číslo v hexadecimální.
Vše, co udělat, je se podíváme na skupiny 4,
a my je převést na odpovídající hexadecimální číslice.
Začneme s pravým většina skupiny 4, tak 0011.
To se děje za jednu 1 a jeden 2, tak společně, že činí 3.
A pak se pojďme podívat na další blok 4.
1101. To se děje za jeden 1, jeden 4, a jeden 8.
Společně, že to bude 13, což D.
A budeme pamatovat, že v šestnáctkové soustavě nemáme jen tak 0 až 9.
Jdeme 0 až F, takže po 9, 10, odpovídá,
11 až B, et cetera, kde F je 15.
Zde 13 je D,
tak převést na desetinné vše, co děláme je, že jsme vlastně
Ke každému pozici jako síla 2.
To je jedna 1, jeden 2, nula 4s, nula 8s, jeden 16, et cetera,
a je to trochu těžké spočítat v hlavě, ale když půjdeme na další snímek
můžeme vidět odpověď.
>> V podstatě budeme naproti zpátky doleva,
a my jsme vynásobí jednotlivé číslice odpovídajícím síla 2.
A pamatujte, na hexadecimální označíme těchto čísel 0x na začátku
takže nepleťte si to s desetinné číslo.
Pokračování, tohle je ASCII tabulka,
a to, co používáme ASCII, je mapovat z postav do numerických hodnot.
Nezapomeňte v PSet kryptografie jsme rozsáhlé použití ASCII tabulky
aby bylo možné používat různé metody kryptografie,
Caesar a Vigenère kód, převést různé dopisy
v řetězci podle klíče daného uživatelem.
Pojďme se podívat na trochu ASCII matematiky.
Při pohledu na "P" + 1, v charakteru podobě, která by byla Q,
a pamatujte, že '5 '≠ 5.
A jak přesně bychom převádět mezi těmito 2 formuláře?
Vlastně to ani není příliš tvrdý.
Aby bylo možné získat 5 odečteme '0 '
protože tam jsou 5 míst mezi '0 'a '5.'
Aby šel na druhou stranu jsme právě přidat 0,
takže je to něco jako pravidelné aritmetiky.
Jen nezapomeňte, že když se něco má uvozovky kolem něj, že je to postava
a tedy odpovídá hodnotě v tabulce ASCII.
Přesun do obecnějších témat počítačových věd.
Naučili jsme se, co je algoritmus a jak je používáme programování
realizovat algoritmy.
Některé příklady algoritmů jsou něco opravdu jednoduchého, jako
kontroly, zda je číslo sudé nebo liché.
Za to si, jsme mod na číslo 2 a zkontrolujte, zda výsledek je 0.
Pokud ano, je to ještě. Pokud tomu tak není, je to zvláštní.
A to je příklad opravdu základní algoritmus.
>> Trochu více se účastní jeden je binární vyhledávání,
které půjdeme přes později v přezkumném jednání.
A programování je termín používáme pro přijetí algoritmus
a převedením na kódování počítač může číst.
2 příklady programování je Scratch,
což je to, co jsme dělali v týdnu 0.
I když nemáme vlastně zadejte ven kód je způsob, kterým se provádí
tento algoritmus, který tiskne čísla 1-10,
a tady děláme totéž v C programovací jazyk.
Jedná se o funkčně ekvivalentní, právě psané v různých jazycích nebo syntaxe.
Pak jsme se dozvěděli o booleovských výrazech,
a boolean je hodnota, která je true nebo false,
a zde mnohdy booleovské výrazy
dovnitř podmínek, tak pokud (x ≤ 5),
dobře, jsme již nastavili x = 5, takže tato podmínka bude hodnotit na true.
A pokud je to pravda, co je kód pod podmínkou,
se bude hodnocena na počítači, tak, že řetězec se bude vytištěn
na standardní výstup, a termín stavu
odkazuje na to, co je uvnitř závorek if.
Nezapomeňte všechny operátory.
Pamatujte si, že tyto && a | |, když se snažíme kombinovat 2 a více podmínek,
== Ne = kontrolovat, zda 2 věci jsou si rovny.
Pamatujte si, že = je pro přiřazení vzhledem k tomu, == je logický operátor.
≤, ≥ a pak v konečném znění 2 jsou zřejmé.
Obecné přezkoumání booleovské logiky zde.
A booleovské výrazy jsou také důležité ve smyčkách,
které půjdeme pryč.
Naučili jsme se asi 3 typy smyček tak daleko CS50, for, while, a to při.
A to je důležité vědět, že zatímco pro většinu účelů
můžeme skutečně použít jakýkoli typ smyčky obecně
existují určité typy účely nebo společných vzorů
v programování, které se specificky nazývají pro jeden z těchto smyček
že aby bylo nejúčinnější nebo elegantní kód to tímto způsobem.
Pojďme co každý z těchto smyček má tendenci být použity pro nejčastěji.
>> V cyklu for jsme obecně již víme, kolikrát chceme iterovat.
To je to, co jsme v podmínce.
Pro, i = 0, i <10, například.
My už víme, že chceme udělat něco 10krát.
Nyní, po smyčce while, obvykle nemáme nutně
Víš, kolikrát chceme smyčku spustit.
Ale my víme nějakou podmínkou, že chceme, aby to
být vždy pravdivé, nebo vždy false.
Například, je nastavena při.
Řekněme, že je to boolean proměnné.
I když to je pravda chceme kód k vyhodnocení,
tak trochu více rozšiřitelný, trochu obecnější než pro smyčce,
ale každý pro smyčce lze také převést na smyčce while.
Konečně, to while, které mohou být nejsložitější pochopit hned,
se často používají, když chceme vyhodnotit kód první
před prvním jsme zkontrolovat stav.
Běžným příkladem použití dělat, když smyčka
je, když se chcete dostat vstup uživatele, a víte, že chcete požádat uživatele
pro vstup alespoň jednou, ale v případě, že nejsou ti dobrou vstup hned
Chcete-li zachovat ptát se jich, dokud vám dobrou vstup.
To je nejvíce obyčejné použití se while,
a pojďme se podívat na vlastní struktury těchto smyček.
Oni typicky vždy mají tendenci následovat tyto vzory.
>> Na smyčky for uvnitř máte 3 složky:
inicializace, obvykle něco jako int i = 0, kde i je počítadlo,
stav, kdy chceme říci, spustit tento cyklus for tak dlouho, jak tento stav stále platí,
jako i <10, a pak konečně, aktualizace, což je, jak jsme zvýšit
čítač proměnnou v každém bodě smyčky.
Běžná věc vidět, že je jen i + +,
což znamená zvýšit i o 1 pokaždé.
Dalo by se také udělat něco podobného i + = 2,
což znamená, přidejte 2 až i pokaždé, když jdete přes smyčku.
A pak to jen se odkazuje na nějaký kód, který vlastně běží jako součást smyčky.
A pro smyčce while, tentokrát jsme vlastně tu inicializaci mimo smyčky,
tak například, řekněme, že se snažíme dělat stejný typ smyčky, jak jsem právě popsal.
Měli bychom říci, int i = 0 před smyčka začne.
Pak bychom mohli říct, když i <10 to,
takže stejný blok kódu jako předtím,
a tentokrát aktualizace část kódu, například, i + +,
vlastně jde uvnitř smyčky.
A konečně, pro dělat, zatímco, to je podobný while,
ale musíme mít na paměti, že kód bude hodnotit, jakmile
před podmínka je kontrolována, takže je mnohem větší smysl
když se podíváte na to v pořadí shora dolů.
V dělat, když smyčka kód hodnotí ještě předtím, než se podívat na while stavu,
vzhledem k tomu, while, zkontroluje jako první.
Prohlášení a proměnné.
Když chceme vytvořit novou proměnnou jsme nejprve chtít inicializovat.
>> Například, int bar inicializuje proměnnou bar,
ale to nedává hodnotu, takže to, co se nachází bar má hodnotu teď?
Nevíme.
Mohlo by to být nějaký odpadky hodnota, která byla dříve uložena v paměti tam,
a nechceme použít tuto proměnnou
dokud jsme vlastně dát hodnotu,
tak jsme prohlásit ho zde.
Pak jsme inicializovat, aby to bylo 42 níže.
Teď, samozřejmě, víme, že to lze provést na jednom řádku, int bar = 42.
Ale jen proto, aby se vymazat několik kroků, které se dějí,
prohlášení a inicializace se děje odděleně zde.
To se děje v jednom kroku, a příští, int baz = bar + 1,
toto prohlášení níže, které se zvýší baz, takže na konci tohoto bloku kódu
kdybychom vytisknout hodnotu baz by být 44
protože jsme deklarovat a inicializovat ji na 1> bar,
a pak jsme zvýšit ji ještě jednou + +.
Šli jsme přes tento pěkný krátce, ale je to dobré mít obecnou
pochopení toho, co témat a události jsou.
Zaměřujeme se především to udělal v Scratch,
takže si můžete myslet vláken as několika sekvencí kódu
běží ve stejnou dobu.
Ve skutečnosti, pravděpodobně neběží současně,
ale druh abstraktně, můžeme myslet na to tímto způsobem.
>> V Scratch, například, měli jsme více skřítky.
Může to být provedení jiný kód ve stejnou dobu.
Jeden by mohl být při chůzi druhý říká něco
v jiné části obrazovky.
Události jsou další způsob, jak oddělí logiku
mezi různými prvky kódu,
a Scratch jsme schopni simulovat události pomocí vysílání,
a to je vlastně, když obdržím, ne, když slyším,
ale v podstatě je to způsob, jak předávat informace
z jednoho skřítka do druhého.
Například, můžete chtít přenášet hru přes,
a když jiný objekt sprite obdrží hru přes,
reaguje určitým způsobem.
Je to důležitý model pro pochopení pro programování.
Stačí jít po základní týdne 0, co jsme pryč přes tak daleko,
Pojďme se podívat na tento jednoduchý C program.
Text může být trochu malý odtud, ale já půjdu přes to opravdu rychle.
Jsme včetně 2 hlavičkové soubory v horním, cs50.h a stdio.h.
Jsme pak definovat konstantní názvem limit je 100.
Jsme pak provádí náš hlavní funkci.
Vzhledem k tomu nemáme používat argumenty příkazového řádku zde musíme dát za neplatné
jako argumenty pro hlavní.
Vidíme int main výše. To je návratový typ, a proto vrátí 0 na dně.
A my jsme pomocí CS50 knihovny funkcí získáte int
požádat uživatele pro vstup, a uložíme ji v této proměnné x,
tak prohlašujeme x výše, a inicializujeme ji x = GetInt.
>> Pak jsme zkontrolovat, zda uživatel dal nám dobrý vstup.
Pokud je to ≥ LIMIT chceme vrátit kód chyby 1 a vytiskne chybové hlášení.
A konečně, v případě, že uživatel je nám dobrý vstup
budeme na náměstí číslo a vytiskne na to, že výsledek.
Jen aby se ujistil, že ti všichni hit domů
můžete vidět popisky různých částí kódu zde.
Zmínil jsem se konstantní, hlavičkové soubory.
Oh, int x. Ujistěte se, že si uvědomit, že je to lokální proměnná.
To kontrastuje z globální proměnné, které budeme hovořit o
trochu později v přezkumném jednání,
a my jsme volání knihovní funkce printf,
takže pokud jsme nezahrnula stdio.h hlavičkový soubor
bychom nebyli schopni zavolat printf.
A já věřím, šipka, která se dostal uřízl zde ukazuje na% d,
který je formátovací řetězec, v printf.
To říká, že vytisknout tuto proměnnou jako číslo,% d.
A to je pro týden 0.
Nyní Lucas se bude i nadále pokračovat.
Ahoj, kluci. Mé jméno je Lucas.
Jsem ve druháku v nejlepším domě na akademické půdě, Mather,
a budu mluvit trochu o 1. týdne a 2,1.
[Týden 1 a 2,1!] [Lucas Freitas]
Jak Lexi říkal, když jsme začali překládat váš kód od nuly do C
jedna z věcí, které jsme si všimli, je, že můžete nejen
napsat svůj kód a spustit jej pomocí zelenou vlajkou už.
Vlastně, budete muset použít některé kroky, aby se váš C program
stát spustitelný soubor.
V podstatě to, co děláte, když píšete program, je to, že
můžete přeložit svůj nápad do jazyka, který kompilátor může pochopit,
takže když píšete program v C
to, co děláte je vlastně psát něco, co váš kompilátor bude rozumět,
a pak kompilátor bude překládat tento kód
do něčeho, že váš počítač bude rozumět.
>> A věc je, počítač je vlastně velmi hloupá.
Váš počítač může chápat pouze 0s a 1s,
takže vlastně v prvních počítačích lidé obvykle naprogramován
pomocí 0s a 1s, ale teď už ne, díky bohu.
Nemáme si zapamatovat sekvence 0s a 1s
pro cyklus for nebo while cyklu a tak dále.
To je důvod, proč máme kompilátor.
Co kompilátor dělá, je to v podstatě převádí C kód,
V našem případě, na jazyk, který váš počítač bude rozumět,
, která je předmětem kód a kompilátor že používáme
se nazývá zvonění, takže to je vlastně symbol pro kovový zvuk.
Máte-li svůj program, co musíte udělat, 2 věci.
Za prvé, budete muset kompilovat svůj program, a pak budete ke spuštění programu.
Chcete-li sestavit svůj program máte spoustu možností, aby tak učinily.
První z nich je udělat řinčet program.c
ve kterém programu je název programu.
V tomto případě můžete vidět, že říkáš jen "Hej, kompilovat svůj program."
Neříkáte "Chci tento název pro svůj program" nebo tak něco.
>> Druhou možností je dát jméno do svého programu.
Můžete říct, že klap-o a pak název, který chcete
spustitelný soubor, který bude jmenován jako a pak program.c.
A můžete také udělat, aby program, a uvidíte, jak v prvních 2 případech
Dal jsem. C, a ve třetí jsem jen programy?
Jo, vlastně by nemělo. C. při použití dělat.
V opačném případě kompilátor bude skutečně křičet na vás.
A také, já nevím, jestli jste pamatuji,
ale hodně krát jsme také použili-lcs50 nebo-lm.
To se nazývá propojení.
Je to prostě říká kompilátoru, že budete používat tyto knihovny právě tam,
takže pokud chcete použít cs50.h máte skutečně psát
řinčení program.c-lcs50.
Pokud tak neučiníte, že kompilátor nebude vědět
, že používáte tyto funkce v cs50.h.
A když chcete spustit program, máte 2 možnosti.
Pokud jste řinčet program.c nedali jste jméno k vašemu programu.
Musíte jej spustit pomocí. / A.out.
A.out je standardní název, který řinčet dává svůj program, pokud nechcete dát mu jméno.
Jinak budete dělat. / Program, pokud dal jméno programu,
a také pokud jste udělat programu název, který program dostane
se již bude naprogramovat stejný název jako soubor c.
Pak jsme si povídali o datových typech a dat.
>> V podstatě datové typy jsou totéž jako malé krabičky, které používají
k uložení hodnot, tak datové typy jsou ve skutečnosti stejně jako pokémonů.
Přicházejí ve všech velikostí a typů.
Nevím, jestli to analogie smysl.
Velikost dat skutečně záleží na architektury stroje.
Všechny datové velikosti, že budu pro zobrazení zde
jsou ve skutečnosti pro 32-bitové stroje, který je v případě našeho zařízení,
ale pokud jste skutečně kódování vašeho počítače Mac nebo v systému Windows také
Pravděpodobně budete mít 64-bit stroj,
tak si pamatujte, že datové velikosti, že budu pro zobrazení zde
jsou pro 32-bitové stroje.
První z nich, že jsme viděli, bylo int,
což je docela jednoduché.
Můžete použít int uložit celé číslo.
Viděli jsme také charakter, char.
Pokud chcete použít písmeno nebo malý symbol budete pravděpodobně používat char.
Char má 1 byte, což znamená 8 bitů, jako Lexi řekl.
V podstatě máme ASCII tabulky, který má 256
Možné kombinace 0s a 1s,
a pak, když zadáte znak, že to bude překládat
znak, který vstupy jste číslo, které máte v ASCII tabulce, jako Lexi řekl.
Máme také plovák, který používáme k ukládání čísla v desítkové soustavě.
Pokud si chcete vybrat 3,14, například, budete používat float
nebo dvojité, který má větší přesnost.
Float má 4 byty.
Double má 8 bajtů, takže jediný rozdíl je přesnost.
Máme také dlouhé, že se používá pro celá čísla,
a je vidět na 32-bitové stroje int a dlouhý mají stejnou velikost,
tak to nemá moc smysl používat dlouho v 32-bitové stroje.
>> Ale pokud používáte Mac a 64-bit stroj, ve skutečnosti dlouhá má velikost 8,
tak, že záleží na architektuře.
Pro 32-bit stroje nemá smysl používat dlouhé opravdu.
A pak dlouho dlouho, na druhé straně, má 8 bajtů,
tak to je velmi dobré, pokud chcete mít delší celé číslo.
A konečně, máme řetězec, který je ve skutečnosti char *,
který je ukazatel na char.
Je to velmi snadné si myslet, že velikost řetězce bude jako
Počet znaků, které tam máte,
ale ve skutečnosti char * sama
má velikost ukazatel na char, který je 4 bajty.
Velikost char * 4 byty.
Nezáleží na tom, jestli máte malou slovo nebo písmeno nebo tak něco.
Bude to mít 4 byty.
Také jsme se naučili trochu o obsazení,
takže jak vidíte, máte-li, například, program, který říká, že
int x = 3 a potom printf ("% d", x / 2)
to vy víte, co to bude tisknout na obrazovce?
>> Někdo? >> [Studenti] 2.
1. >> 1, jo.
Pokud tak učiníte 3/2 to dostane 1,5,
ale protože jsme použili celočíselnou to bude ignorovat desetinnou část,
a budete mít 1.
Pokud nechcete, aby se to stalo, co můžete udělat, například,
je deklarovat plovák y = x.
Pak x, které bývaly 3 se nyní bude 3,000 v y.
A pak si můžete vytisknout y / 2.
Vlastně, měl bych mít 2. tam.
Bude to dělat 3.00/2.00,
a budete se dostat 1,5.
A máme tento 0,2 f jen požádat o 2 desetinná jednotek v desetinnou část.
Máte-li 0,3 f, že to bude mít skutečně 1,500.
Pokud je to 2 to bude 1,50.
Máme také tento případ zde.
Pokud si float x = 3,14 a pak vy printf x
budete se 3,14.
A pokud si x = int x,
což znamená, že léčit x jako int a tisknete X nyní
budete mít 3,00.
Dává to smysl?
Protože jste první léčbu x jako celé číslo, takže jste ignoroval desetinnou část,
a pak tisknete x.
A konečně, můžete si také udělat to,
int x = 65, a pak prohlásit char c = x,
a pak, pokud tisknete c jste vlastně dostane
, Takže v podstatě to, co tady děláš
je překládat celé číslo do charakteru,
stejně jako ASCII tabulka dělá.
Hovořili jsme také o matematických operátorů.
Většina z nich jsou docela jednoduché, takže +, -, *, /,
a také se hovoří o mod, který je zbytek z dělení 2 čísla.
Pokud máte 10% 3, například,
to znamená rozdělit 10 do 3, a to, co je zbytek?
Bude to být 1, takže je to vlastně velmi užitečné pro mnoho programů.
Pro Vigenère a Caesar Jsem si jistý, že všichni z vás používá mod.
O matematických operátorů, buďte velmi opatrní při kombinování * a /.
>> Například, pokud si (3/2) * 2, co se vám dostane?
[Studenti] 2.
Jo, 2, protože 3/2 bude 1,5,
ale protože děláte operace mezi 2 celá čísla
jste vlastně jen tak, aby zvážila 1,
a pak 1 * 2 bude 2, takže se velmi, velmi opatrní
když dělá aritmetiku s celými čísly, protože
se mohou vyskytnout, že 2 = 3, v tomto případě.
A také být velmi opatrní přednost.
Měli byste obvykle používají závorky si být jisti, že víte, co děláte.
Některé užitečné zkratky, samozřejmě, jeden je i + + nebo i + = 1
nebo pomocí + =.
To je totéž, jako dělat i = i + 1.
Můžete si také udělat i - nebo i - = 1,
který je totéž, jako i = i-1,
Něco, co jste kluci používají hodně v cyklech for, nejméně.
Také, pro *, pokud používáte * = a pokud ano, například,
i * = 2 je totéž, jak říká i = i * 2,
a totéž pro rozdělení.
Pokud si i / = 2 je to totéž, jako i = i / 2.
>> Nyní o funkcích.
Vy se dozvěděl, že funkce jsou velmi dobrá strategie pro uložení kódu
když jste programování, takže pokud chcete provést stejný úkol
v kódu znovu a znovu, pravděpodobně budete chtít použít funkci
jen tak nemusíte kopírovat a vložit kód znovu a znovu.
Vlastně, hlavní je funkce, a když jsem vám ukázat formát funkce
budete vidět, že to je docela zřejmé.
Používáme také funkce z některých knihoven,
Například, printf, Getin, která je z knihovny CS50,
a další funkce, jako je toupper.
Všechny tyto funkce jsou skutečně prováděny v jiných knihovnách,
a když dáte tyto postroje soubory na začátku programu
říkáš, že můžete mi prosím dejte mi kód těchto funkcí
takže nemám k jejich provedení, sám?
A můžete také napsat své vlastní funkce, takže při spuštění programování
Uvědomujete si, že knihovny nemají všechny funkce, které potřebujete.
V posledním Pset, například, jsme psali čerpat, kódování, a vyhledávání,
a je to velmi, velmi důležité, abychom byli schopni psát funkce
protože jsou užitečné, a my jsme je používat po celou dobu v programování,
a to ušetří spoustu kódu.
Formát funkce je tenhle.
Máme návratový typ na začátku. Co je návratový typ?
Je to jen, když je vaše funkce bude vracet.
Pokud máte funkci, například, faktoriál,
, který se chystá k výpočtu faktoriálu celé číslo,
Pravděpodobně to bude vrátit celé číslo také.
Pak návratový typ bude int.
Printf vlastně má návratový typ void
protože nejste vracet nic.
Ty pouze tisk věci na obrazovce
a ukončení funkce poté.
Pak máte název funkce, která si můžete vybrat.
Ty by měly být trochu rozumný, jako nevybírejte jméno jako xyz
nebo jako x2f.
Snažte se, aby se o název, který dává smysl.
>> Například, pokud je to faktoriál, říkají faktoriál.
Pokud je to funkce, která se chystá na něco nakreslit, pojmenujte ji čerpat.
A pak máme parametry, které jsou také nazývány argumenty,
které jsou jako prostředky, které vaše funkce potřebuje
od kódu k plnění svého úkolu.
Pokud chcete vypočítat faktoriál čísla
Pravděpodobně budete muset mít řadu pro výpočet faktoriálu.
Jedním z argumentů, které budete mít, je samotné číslo.
A pak, že to bude něco udělat a vrátit hodnotu na konci
pokud je to neplatné funkce.
Pojďme se podívat, příklad.
Pokud chci napsat funkci, která sečte všechna čísla v matici celých čísel,
v první řadě, návratový typ bude int
protože mám řadu celých čísel.
A pak budu mít název funkce, jako sumArray,
a pak to bude trvat pole sám, na int nums,
a pak délka pole, takže vím, kolik čísel musím shrnout.
Pak jsem si inicializovat proměnnou s názvem částku, například na 0,
a pokaždé, když vidím prvek v poli bych přidat do součtu, tak jsem udělal pro smyčce.
Stejně jako Lexi řekl, ty int i = 0, i <délka a i + +.
A pro každý prvek v poli jsem součet + = nums [i],
a pak jsem se vrátil částku, takže je to velmi jednoduché, a to ušetří spoustu kódu
Pokud používáte tuto funkci, mnohokrát.
Pak jsme se podívali na podmínkách.
Máme-li, jinak, a else if.
Pojďme se podívat, jaký je rozdíl mezi těmito.
Podívejte se na tyto 2 kódy. Jaký je rozdíl mezi nimi?
První z nich, v podstatě kódy chtějí, abys
pokud je číslo +, -, nebo 0.
První z nich říká, že pokud je to> 0, pak je to pozitivní.
Pokud je to = 0, pak je to 0, a pokud je to <0, pak je to negativní.
>> A druhý dělá if, else if, else.
Rozdíl mezi nimi je, že tohle je vlastně bude
zkontrolujte, zda> 0, <0 nebo = 0 třikrát,
takže pokud máte číslo 2, například, to přijde sem a říct
if (x> 0), a bude to, že ano, tak jsem vytisknout pozitivní.
Ale i když vím, že je to> 0 a nebude to na 0 nebo <0
Jsem stále dělat, je to 0, je to <0,
takže jsem vlastně děje uvnitř fondy, které jsem nemusela
protože už vím, že to nebude splňovat některou z těchto podmínek.
Mohu použít if, else if, else příkaz.
Je to v podstatě říká, že pokud x = 0 tisknout pozitivní.
Pokud tomu tak není, budu i tento test.
Pokud to 2 není budu dělat to.
V podstatě, pokud jsem měl x = 2 bys řekl
if (x> 0), ano, tak tisknout.
Teď, když vím, že je to> 0, a že je spokojen první, pokud
Nejsem ani jít spustit tento kód.
Kód běží rychleji, vlastně, 3 krát rychleji, pokud použijete tento.
Také jsme se dozvěděli o a a nebo.
Nebudu se projít, protože Lexi už mluvili o nich.
Je to jen o && a | | provozovatel.
>> Jediné, co řeknu, je být opatrný, když máte 3 podmínky.
Použijte závorky, protože je to velmi matoucí, když máte podmínku
a další jeden nebo jiný.
Pomocí závorek jen pro jistotu, že vaše podmínky smysl
protože v tomto případě, například, mohou si představit, že
to by mohlo být první podmínka, a jeden nebo druhý
nebo 2 podmínky spojené v a
nebo třetí, takže stačí být opatrný.
A konečně, mluvili jsme o přepínačích.
Přepínač je velmi užitečné, když máte proměnnou.
Řekněme, že máte proměnnou jako n
, které mohou být 0, 1, nebo 2, a na každém z těchto případů
budete k provedení úkolu.
Můžete říct, že přepnout proměnnou, a znamená to, že
hodnota pak je jako hodnota1 budu dělat to,
a pak jsem se zlomit, což znamená, že nebudu dívat na některý z ostatních případech
protože jsme již spokojeni, že případ
a pak hodnota2 a tak dále, a já také může mít výchozí polohy.
To znamená, že v případě, že nesplňuje žádný z případů, které jsem měl
že budu dělat něco jiného, ​​ale to je volitelné.
To je pro mě. Nyní se pojďme Tommy.
Dobře, tohle bude týden 3-ish.
To jsou některá z témat budeme pokrývat, crypto, rozsah, pole, et cetera.
Jen slovíčko na crypto. Nebudeme se kladivem domů.
>> Udělali jsme to v PSet 2, ale pro kvíz ujistěte se, že znáte rozdíl
mezi Caesara a Vigenère kód,
jak obě z těchto šifer práce a jaké to je k šifrování
a dešifrování textu pomocí těchto 2 šifry.
Nezapomeňte, Caesarova šifra jednoduše otočí každý znak stejnou částku,
Díky, že jste mod počtem písmen v abecedě.
A Vigenère kód, na druhé straně, se otáčí každý znak
jinou částku, takže spíše než říkat
Každá postava otáčí od 3 Vigenère bude otáčet každý znak
o různé částky v závislosti na určité klíčové
kde každý dopis na klíčové slovo představuje nějaké jiné množství
otočit jasný text.
Pojďme mluvit o první proměnnou rozsahu.
K dispozici jsou 2 různé typy proměnných.
Máme lokální proměnné, a ty se bude definovat
mimo hlavní nebo mimo jakoukoli funkci nebo bloku,
a ty budou dostupné kdekoliv ve vašem programu.
Pokud máte funkci a v této funkci, je while
Velký globální proměnná je přístupná všude.
Lokální proměnná, na druhé straně, je rozsahem na místo, kde je definována.
>> Pokud máte funkci zde například, máme tuto funkci g,
a uvnitř g je proměnná zde nazývá y,
a to znamená, že se jedná o lokální proměnná.
I když je tato proměnná nazývá y
a tato proměnná se nazývá Y tyto 2 funkce
nemám ponětí, co každý jiný je lokální proměnné jsou.
Na druhé straně, a to až tady říci int x = 5,
a to je mimo rámec jakékoli funkce.
Je to mimo rámec hlavní, takže to je globální proměnná.
To znamená, že uvnitř těchto 2 funkcí, když řeknu, x - nebo x + +
Já přístupu k témuž x přičemž toto y, a to y jsou různé proměnné.
To je rozdíl mezi globální proměnné a lokální proměnné.
Pokud jde o návrh se týká, někdy je to asi lepší nápad
aby proměnné lokální, kdykoli si možná můžete
protože mají spoustu globálních proměnných může dostat opravdu matoucí.
Pokud máte spoustu funkcí všech modifikací totéž
můžete zapomenout co když je tato funkce náhodou upravuje tento globální,
a tato jiná funkce neví o tom,
a to pěkně matoucí, jak si získat více kódu.
Vedení proměnné lokální, kdykoli si možná můžete
je prostě dobrý design.
Matice, pamatujte, že jsou prostě seznamy prvků stejného typu.
Uvnitř CI nemůže mít seznam jako 1, 2,0, ahoj.
My prostě nemůžeme udělat, že.
>> Když deklarujeme pole v C všechny prvky musí být stejného typu.
Tady mám řadu 3 celých čísel.
Tady mám délku pole, ale pokud jsem jen prohlášením v této syntaxi
kde jsem určit, jaká všechny prvky jsou nemám technicky potřebovat 3.
Kompilátor je dost chytrý na to, aby zjistili, jak velký by měl být pole.
Teď, když chci získat nebo nastavit hodnotu pole
To je syntaxe k tomu, že.
To bude skutečně měnit druhý prvek pole, protože, pamatujte,
Číslování začíná na 0, ne na 1.
Pokud chci číst tuto hodnotu mohu říci něco jako int x = array [1].
Nebo když chci nastavit tuto hodnotu, jako bych tady,
Mohu říci, array [1] = 4.
V té době přístup k prvkům jejich index
nebo jejich polohy, nebo kde jsou v poli,
a že zápis začíná 0.
Můžeme také pole polí,
a to se nazývá multi-dimenzionální pole.
Když máme multi-dimenzionální pole
to znamená, že můžeme mít něco jako řádků a sloupců,
a to je jen jeden způsob, jak vizualizaci tohoto nebo o tom přemýšlet.
Když mám multi-dimenzionální pole, které znamená, že začnu potřebovat
více než 1 index, protože když budu mít mřížku
Jen říkám, co řádek jste v nedává číslo.
To je opravdu jen nám dá seznam čísel.
Řekněme, že mám toto pole zde.
Mám pole s názvem síť, a já říkám, že tyto 2 řádky a 3 sloupce,
a tak to je jeden ze způsobů, vizualizaci ji.
Když řeknu, že já se chci dostat prvek na [1] [2]
to znamená, že proto, že se jedná o řádky a pak sloupce
Chystám se skočit na řádku 1, protože jsem řekla 1.
>> Pak budu sem přišel do sloupce 2, a budu-li získat hodnotu 6.
Smysl?
Multi-dimenzionální pole, pamatujte, jsou technicky jen pole polí.
Můžeme mít matice polí polí.
Můžeme pokračovat, ale opravdu jediný způsob, jak přemýšlet o
jak je právě toto stanoveny a co se děje, je představit si to
v mřížce, jako je to.
Když jsme se projít pole k funkcím, jdou chovat
trochu jinak, než když jsme se projít pravidelné proměnné funkcí
jako složením int nebo float.
Když jsme se projít v int nebo char nebo některý z těchto jiných datových typů
právě jsme se podívat na, pokud funkce mění
hodnota této proměnné je tato změna nebude šířit do
volající funkci.
S pole, na druhé straně, se tak stalo.
Pokud se projít v poli na nějakou funkci, a že funkce mění některé prvky,
když jsem se vrátil do funkce, která je volána
moje pole je nyní bude lišit, a slovník pro které
je pole jsou předány formou odkazu, jak uvidíme později.
To se týká jak ukazovátka práce, kde tyto základní datové typy,
na druhé straně, jsou předány hodnotou.
>> Můžeme to brát jako vytvoření kopie některé proměnné a pak předá v kopii.
Nezáleží na tom, co uděláme s této proměnné.
Volání funkce nebude vědom toho, že došlo ke změně.
Pole jsou jen trochu liší v tomto ohledu.
Například, jak jsme viděli, hlavní je prostě funkce
které mohou mít v 2 argumenty.
První argument hlavní funkci je argc, nebo počet argumentů,
a druhý argument se nazývá argv,
a ty jsou skutečné hodnoty těchto argumentů.
Řekněme, že mám program s názvem this.c,
a říkám, aby to, a já budu běžet do příkazového řádku.
Nyní předat některé argumenty k mému programu volal toto,
Mohl bych říct něco. / Je to cs 50.
To je to, co si představujeme, David dělat každý den na terminálu.
Ale teď je hlavní funkcí uvnitř tohoto programu
má tyto hodnoty, tak argc je 4.
To by mohlo být trochu matoucí, protože opravdu jsme jen procházet v je cs 50.
To je jen 3.
Ale pamatujte si, že první prvek argv nebo první argument
je název funkce sám.
Takže to znamená, že máme 4 věci tady,
a první prvek bude. / tohle.
A to bude reprezentován jako řetězec.
Pak Zbývající prvky jsou tím, co jsme zadali v po názvu programu.
Tedy stejně jako stranou, jak jsme asi viděli v PSet 2,
nezapomeňte, že řetězec 50 se ≠ celočíselnou 50.
Takže nemůžeme říct něco jako, 'int x = argv 3. "
>> To se prostě nebude dávat smysl, protože je to řetězec, a to je celé číslo.
Takže pokud chcete převést mezi 2, pamatujte, budeme
mají to kouzlo funkci s názvem atoi.
To trvá řetězec a vrátí celé číslo reprezentované uvnitř tohoto řetězce.
Tak to je chybka se snadno vloudí na kvíz,
si myslel, že to bude automaticky správný typ.
Ale prostě vím, že to bude vždy řetězce
i když řetězec obsahuje pouze celé číslo nebo znak, nebo plavat.
Takže teď pojďme mluvit o jízdní doby.
Když máme všechny tyto algoritmy, které umí všechny tyto šílené věci,
se stává opravdu užitečné si položit otázku, "Jak dlouho trvá?"
Zastupujeme že s tzv. asymptotické notace.
Takže to znamená, že - no, řekněme, že jsme dát náš algoritmus
některé opravdu, opravdu, opravdu velký vstup.
Chceme si položit otázku, "Jak dlouho to bude trvat?
Kolik kroků bude trvat naše algoritmus běžet
v závislosti na velikosti vstupu? "
Takže první způsob, jak můžeme popsat doba chodu je s velkým O.
A tohle je náš nejhorší doba doběhu.
Takže pokud chceme třídit pole, a dáváme náš algoritmus pole
to v sestupném pořadí, kdy by mělo být ve vzestupném pořadí,
že to bude nejhorší.
To je naše horní mez v maximální dobu náš algoritmus bude trvat.
Na druhé straně, tato Ω bude popisovat nejlepším případě chodu.
Takže pokud dáme již seřazena pole na třídění algoritmu,
jak dlouho bude trvat, než se tento oříšek?
A to, pak, popisuje dolní mez na běh času.
Takže tady jsou jen některá slova, která popisují některé běžné provozní dobu.
Jsou ve vzestupném pořadí.
Nejrychlejší doba chodu máme se nazývá konstanta.
>> To znamená, že bez ohledu na to, kolik prvků jsme dát náš algoritmus,
bez ohledu na to, jak velký náš pole je řazení je
aneb co děláme na poli bude vždy stejné množství času.
Takže můžeme prohlašujete, že jen s 1, která je konstantní.
Také jsme se podívali na logaritmickém běhu.
Takže něco jako binární vyhledávání je logaritmická,
kde jsme zkrátili problém polovina pokaždé
a pak se věci jen získat vyšší odtamtud.
A pokud jste někdy psaní O každé faktoriál algoritmu,
měli byste brát v úvahu to jako váš pracovní den.
Když jsme tyto provozní dobu je důležité mít na paměti tyto věci.
Takže pokud mám algoritmus, který je O (n), a někdo jiný
je algoritmus O (2n) jsou vlastně asymptoticky ekvivalentní.
Takže pokud bychom si představit, n být velké číslo jako Eleventy miliard:
takže když jsme srovnání Eleventy miliardy na něco, jako je Eleventy miliard + 3,
náhle, že 3 není opravdu velký rozdíl už.
To je důvod, proč budeme začít zvažovat tyto věci za rovnocenné.
Takže věci jako tyto konstanty, je tu 2 x to, nebo přidáním 3,
to jsou jen konstanty, a ty jsou v úmyslu položit nahoru.
Takže to je důvod, proč všechny 3 z těchto dobách chodu jsou stejné jako říkat, že oni to O (n).
Podobně, pokud máme 2 další dobu chodu, řekněme O (n ³ + 2n ²), můžeme přidat
+ N, + 7, a pak máme další dobu běhu, který je jen O (n ³).
Ani v tomto případě je to samé, protože to - to nejsou stejné.
Jedná se o stejné věci, je mi líto. To jsou stejné, protože
Tento ³ n se bude ovládat tento 2n ².
>> Co není totéž, je-li jsme běžet časy jako O (n ³) a O (n ²)
protože ³ n je mnohem větší než tento ² n.
Takže pokud máme exponenty, najednou to začne záležet,
ale když jsme jen jednání s faktory, jako my tady,
pak to nebude záležet, protože se právě chystá odejít.
Pojďme se podívat na některé z algoritmů jsme viděli doposud
a mluvit o jejich běhu.
První způsob pohledu na čísla v seznamu, který jsme viděli, byl lineární hledání.
A provádění lineární hledání je super jednoduché.
Musíme jen seznam, a budeme se dívat na každý jednotlivý prvek v seznamu
dokud nenajdeme číslo jsme hledali.
To znamená, že v nejhorším případě, to O (n).
A v nejhorším případě zde může být v případě, že element je
poslední prvek, pak pomocí lineární hledání, musíme se podívat na každý element
dokud se na poslední, aby věděli, že to bylo vlastně v seznamu.
Nemůžeme jen tak vzdal v půli cesty a řekl: "Je to asi není."
S lineární hledání se musíme podívat na celou věc.
Nejlepší případu doba doběhu, na druhé straně, je konstantní
protože v nejlepším případě je prvek, kterého hledáme, je jen první v seznamu.
Takže to bude trvat nám přesně 1 krok, bez ohledu na to, jak velký je seznam
pokud hledáme pro první prvek pokaždé.
>> Takže když hledáte, pamatujte, že nevyžaduje, že náš seznam být seřazeny.
Vzhledem k tomu, že jsme prostě bude vypadat v průběhu každého jednotlivého prvku, a to nezáleží
jakém pořadí tyto prvky jsou v.
Více inteligentní vyhledávací algoritmus je něco jako binární vyhledávání.
Pamatujte si, že implementace binárního vyhledávání je, když jdete na
Dívej se na středu seznamu.
A protože se díváme na středu, požadujeme, aby Seznam je řazen
jinak nevíme, kde uprostřed je, a musíme se podívat na
celý seznam najít, a pak na tom místě jsme jen ztrácíš čas.
Takže pokud máme seřazený seznam a najdeme uprostřed, budeme srovnávat střed
na prvek, kterého hledáme.
Pokud je to příliš vysoká, pak můžeme zapomenout na pravou polovinu
protože víme, že když náš element je již příliš vysoká
a vše napravo od tohoto prvku je dokonce vyšší,
pak nepotřebujeme hledat tam už.
Tam, kde na druhé straně, pokud náš prvek je příliš nízká,
víme všechno vlevo od tohoto prvku je také příliš nízká,
tak to nemá moc smysl se podívat tam, a to buď.
Tímto způsobem, s každým krokem a pokaždé, když se podíváte na středu seznamu,
budeme řezat náš problém v polovině, protože najednou víme
celá parta čísel, která nemůže být ten, kterého hledáme.
>> V pseudokódu by vypadat nějak takto,
a protože jsme řezání seznam v polovině každé době,
naše nejhorších skoky Run Time z lineární do logaritmická.
Takže najednou máme log-in kroků s cílem najít element v seznamu.
Best case doba doběhu, i když je stále konstantní
protože teď, řekněme, že prvek hledáme, je
vždy přesný střed původního seznamu.
Takže můžeme pěstovat naši nabídku tak velký, jak bychom chtěli, ale pokud element hledáme, je v polovině,
pak je to jen bude nám trvat 1 krok.
Takže to je důvod, proč jsme O (log n) a Ω (1), nebo konstantní.
Pojďme skutečně spustit binární vyhledávání na tomto seznamu.
Takže řekněme, že jsme hledali prvku 164.
První věc, kterou se chystáte udělat, je najít střed tohoto seznamu.
To jen tak se stane, že střed bude klesat mezi těmito 2 čísla,
tak ať to prostě libovolně sice pokaždé, když střed spadá mezi 2 čísla,
řekněme, zaokrouhlit nahoru.
Potřebujeme jen ujistit, že jsme to na každém kroku na cestě.
Takže budeme zaokrouhlovat, a budeme říkat, že 161 je uprostřed našeho seznamu.
So 161 <164, a každý prvek vlevo 161
je také <164, takže víme, že to nepomůže nám vůbec
začít hledat tady, protože element jsme hledali nemůže být tam.
Takže to, co můžeme udělat, je, že jsme se prostě zapomenout o tom celé levé poloviny seznamu,
a nyní jen zvážila z práva na 161 kupředu.
>> Takže znovu, je to střed, řekněme, zaokrouhlit nahoru.
Nyní 175 je příliš velká.
Tak jsme vím, že to nepomůže nám hledají tady nebo tady,
takže můžeme jen hodit to pryč, a nakonec budeme hit 164.
Jakékoliv dotazy týkající se binární vyhledávání?
Pojďme dál od vyhledávání přes již tříděném seznamu
skutečně vezme seznam čísel v libovolném pořadí
a poskytování tohoto seznamu ve vzestupném pořadí.
První algoritmus jsme se dívali na říkalo bubble sort.
A to by bylo jednodušší z algoritmů, které jsme viděli.
Bubble sort říká, že když nějaké 2 prvky uvnitř seznamu jsou na místě,
což znamená, že je větší počet na levé straně nižšího počtu,
pak budeme vyměnit je, protože to znamená, že seznam bude
"Více seřazena", než tomu bylo dříve.
A my jsme jen tak pro pokračování tohoto procesu znovu a znovu a znovu
až nakonec prvky druh bubliny na jejich správné umístění a máme seřazený seznam.
>> Běh času je to bude O (n ²). Proč?
No, protože v nejhorším případě, budeme brát každý prvek, a
budeme skončit srovnání s každou další prvek v seznamu.
Ale v tom nejlepším případě, máme již seřazený seznam, bublina sort je
jen tak projít jednou, řeknu "Ne. Neudělal jsem žádné swapy, tak jsem udělal."
Takže máme nejlepší případovou doba chodu Ω (n).
Spusťme bublina třídění v seznamu.
Nebo první, pojďme se podívat na některé pseudokódu opravdu rychle.
Chceme, že chceme sledovat, v každé iteraci smyčky,
mít přehled o tom, zda jsme nebo nejsme měnit žádné prvky.
Takže důvod pro to je, budeme zastavit, když jsme se vyměnili žádné prvky.
Takže na začátku našeho cyklu jsme se vyměnili nic, tak budeme říkat, že je to pravda.
Nyní, budeme procházet seznam a porovnejte prvek i pro element i + 1
a je-li tomu tak, že je větší počet na levé straně menší počet,
pak jsme jen tak vyměnit je.
>> A pak budeme mít na paměti, že jsme vyměnili prvek.
To znamená, že musíme projít seznam alespoň 1 více času
protože stav, ve kterém jsme se zastavili je, když je celý seznam již řazeno,
což znamená, jsme neprovedli žádné swapy.
Takže to je důvod, proč naše podmínka tady dole je ", zatímco některé prvky byly prohozeny."
Takže teď pojďme se podívat na to běží na seznamu.
Mám seznam 5,0,1,6,4.
Bubble sort je začnou celou cestu vlevo, a to bude k porovnání
se i prvky, takže 0 až i + 1, což je prvek 1.
Bude to říct, i 5> 0, ale teď 5 je nalevo,
tak musím vyměnit 5 a 0.
Když jsem je swap, najednou jsem si to jiný seznam.
Nyní 5> 1, takže budeme vyměnit je.
5 není> 6, takže nemusíte dělat nic.
Ale 6> 4, takže musíme vyměnit.
Znovu musíme projít celý seznam nakonec objevit
že tyto jsou mimo provoz, vyměníme je,
a na tomto místě musíme projít seznam 1 více času
aby se ujistil, že vše, co je v jeho pořadí, a v tomto bodě bubliny řadit dokončení.
Jiný algoritmus pro přijetí některých prvků a jejich třídění je výběr sort.
Myšlenka výběru druhu je, že budeme budovat seřazena část seznamu
1 prvek najednou.
>> A jak budeme dělat, že je tím, že staví na levé segment seznamu.
A v podstatě každý - na každém kroku, budeme mít nejmenší prvek jsme vlevo
která nebyla seřazena ještě, a budeme jej přesunout do té seřazeny segmentu.
To znamená, že musíme neustále najít minimální směsný prvek
a pak, že minimální prvek a vyměnit ji, co
nejvíce vlevo prvek, který není seřazena.
Spustit čas to bude O (n ²), protože v nejhorším případě
musíme porovnat každý jednotlivý prvek ke každému jinému prvku.
Vzhledem k tomu, říkáme, že pokud začneme na levé polovině seznamu, musíme
projít celou pravou segmentu najít nejmenší prvek.
A pak, opět musíme jít přes celou pravou část a
dál nad tím znovu a znovu a znovu.
To bude mít n ². Budeme potřebovat pro smyčky uvnitř jiného pro smyčky
což naznačuje, n ².
V nejlepším případě myšlení, řekněme, že jej již seřazený seznam;
jsme vlastně neděláme nic lépe, než ² n.
Vzhledem k tomu, Výběr způsob má žádný způsob, jak zjistit, že
minimální prvek je jen jeden I stalo se dívá.
To ještě potřebuje, aby se ujistil, že je to vlastně minimum.
>> A jediný způsob, jak se ujistit, že je to minimum, pomocí tohoto algoritmu,
je podívat se na každý jednotlivý prvek znovu.
Takže opravdu, pokud mi ji - pokud dáte výběrem Třídit již seřazený seznam,
to nebude o nic lépe, než dávat to seznam, který není seřazena ještě.
Mimochodem, pokud se to stane, že je pravda, že něco je O (něco)
a omega něčeho, můžeme jen říct stručněji, že je to θ něco.
Takže pokud vidíte, že přijít kamkoliv, to je to, co to znamená jen.
>> Pokud je něco theta n ², je to tak velký O (n ²) a Ω (n ²).
Takže nejlepším případě a nejhorší případ, to neznamená, že rozdíl,
algoritmus se chystá udělat stejnou věc pokaždé.
Tak tohle je to, co pseudokód pro výběr druhu by mohl vypadat.
Jsme v podstatě říct, že chci iteraci seznam
zleva doprava, a na každé opakování smyčky, budu se pohybovat
Minimální prvek do tohoto tříděného části seznamu.
A jednou jsem přesunout tam něco, nikdy jsem třeba podívat se na tento prvek znovu.
Vzhledem k tomu, jakmile jsem vyměnit prvek do levého segmentu seznamu, je seřazena it
protože děláme všechno ve vzestupném pořadí pomocí minima.
Tak jsme si řekli, jo, jsme na pozici i, a musíme se podívat na všechny prvky
vpravo i s cílem nalézt minimální.
Takže to znamená, že chceme vypadat od i + 1 na konec seznamu.
A nyní, v případě, že prvek, který jsme v současné době při pohledu na méně než naše minimum tak daleko,
které, pamatujte, začínáme minimální off být jen
bez ohledu na element jsme v současné době, budu předpokládat, že je to minimum.
Pokud najdu prvek, který je menší než to, že pak budu říkat, jo,
dobře, jsem našel novou minimální.
Budu si pamatovat, kde který minimum bylo.
>> Takže teď, poté, co jsem prošel toto právo netříděného segmentu,
Můžu říct, že jsem jít vyměnit minimální prvek s prvkem, který je v poloze I.
To bude vybudovat svůj seznam, moje seřazena část seznamu zleva doprava,
a nemáme vůbec třeba se podívat na prvek znovu, jakmile je to v této části.
Jakmile jsme vyměnili ho.
Takže pojďme běžet výběr druhu na tomto seznamu.
Modrý prvek zde bude i, a červený prvek bude minimální prvek.
Tak jsem spustí celou cestu vlevo od seznamu, tak na 5.
Nyní musíme najít minimální směsný prvek.
Tak jsme říci, 0 <5, takže 0 je můj nový minimum.
>> Ale já se nemůže zastavit tam, protože i když jsme si uvědomit, že 0 je nejmenší,
musíme projít každý jiný prvek seznamu, aby se ujistil.
Takže 1 je větší, 6 je větší, 4 je větší.
To znamená, že po pohledu na všechny tyto prvky, jsem určuje 0 je nejmenší.
Takže budu přestavení 5 a 0.
Jakmile jsem vyměnit, že jdu si pořídit nový seznam, a já vím, že jsem nikdy nebudete muset dívat na této 0 znovu
protože jakmile jsem vyměnil to, jsem seřazena, a jsme hotovi.
Nyní je jen tak se stane, že modrý prvek je opět 5,
a musíme se podívat na 1, 6 a 4 určit, že 1
je nejmenší minimální prvek, takže budeme vyměnit 1 a 5.
Opět, musíme se podívat na - porovnejte 5 na 6 a 4,
a budeme zaměnit 4 a 5, a konečně, tyto
tato 2 čísla a vyměnit je, dokud jsme si naše seřazený seznam.
Jakékoliv dotazy týkající se výběru druhu?
Dobře. Pojďme na poslední téma zde, a že je rekurze.
>> Rekurze, pamatujte, je to opravdu meta věc, kde funkce
opakovaně volá sám.
Takže v určitém okamžiku, zatímco naše fuction je opakovaně volá sama,
zde musí být nějaký bod, ve kterém jsme se přestat volat sami.
Protože pokud to neuděláme, pak jsme jen tak, aby i nadále dělat navždy,
a náš program se prostě nebude ukončit.
Říkáme tato podmínka referenční případ.
A základní věc říká, spíše než volání funkce znovu,
Já jsem prostě jít vrátit nějakou hodnotu.
Takže jakmile jsme vrátili hodnotu, zastavili jsme volat sami,
a zbytek volání jsme doposud vytvořili mohou také vracet.
Naproti základní věci je rekurzivní případ.
A to je, když chceme, aby se další volání funkce, že jsme v současné době palců
A my asi, i když ne vždy, chcete použít různé argumenty.
>> Takže pokud máme funkci nazvanou f a f právě volal vzít 1 argument,
a my jsme dál označovat f (1), f (1), f (1), a to jen tak se stane, že
Argument 1 spadá do rekurzivní případě, my ještě nikdy nezastaví.
I když máme základní případ, musíme se ujistit, že nakonec budeme se zasáhnout, že základní věci.
Nechceme jen držet pobyt v tomto případě rekurzivní.
Obecně platí, že když jsme si říkali, že jsme pravděpodobně bude mít jiný argument, pokaždé.
Zde je opravdu jednoduchý rekurzivní funkce.
Takže to bude počítat faktoriál čísla.
Nahoru Nahoru tady máme základní případ.
V případě, že n ≤ 1, my nebudeme volat faktoriál znovu.
Budeme se zastavit; jsme jen tak vrátit nějakou hodnotu.
Pokud to není pravda, pak budeme hit naší rekurzivní případ.
Všimněte si, že nejsme jen volat faktoriál (n), protože to by nebylo moc užitečné.
Budeme volat faktoriál něco jiného.
>> A tak můžete vidět, případně jestli míjíme faktoriál (5), nebo tak něco,
budeme volat faktoriál (4), a tak dále, a nakonec budeme hit tohoto základního případu.
Tak to vypadá dobře. Podívejme se, co se stane, když ve skutečnosti spustit tento.
To je stack, a řekněme, že hlavní bude volat tuto funkci s argumentem (4).
Takže jakmile faktoriál vidí a = 4, bude faktoriál volat sebe.
Nyní, najednou, máme faktoriál (3).
Takže tyto funkce budou nadále zvyšovat, až nakonec jsme narazili náš základní věc.
V tomto bodě, návratová hodnota je návrat (nx návratová hodnota tohoto),
návratová hodnota je nx návratová hodnota tohoto.
Nakonec musíme zasáhnout určitý počet.
Na vrcholu zde, říkáme návrat 1.
To znamená, že jakmile se vrátíme toto číslo, můžeme pop to ze zásobníku.
Takže tato faktoriál (1) je provedeno.
Při 1 vrátí, tento faktoriál (1) přiznání, tento návrat k 1.
Návratová hodnota tohoto, pamatujte, byl nx návratová hodnota tohoto.
Tak náhle, tenhle chlap ví, že bych se chtěl vrátit 2.
>> Takže si pamatujte, vrátí hodnota je jen nx návratová hodnota tady.
Takže teď můžeme říci, 3 x 2, a konečně, zde můžeme říci,
je to jen bude 4 x 3 x 2.
A jakmile se vrátí, dostaneme se na jednotlivé celočíselné uvnitř hlavní.
Jakékoliv dotazy týkající se rekurze?
Dobrá. Takže tam je více času na otázky na konci,
ale nyní Joseph bude týkat zbývajících témat.
>> [Joseph Ong] Dobře. Takže teď, že jsme mluvili o rekurze,
pojďme mluvit trochu o tom, co sloučit druh je.
Sloučit druh je v podstatě jiný způsob řazení seznamu čísel.
A jak to funguje, je, s řadit slučovací máte seznam, a to, co děláme, je
říkáme, pojďme rozdělit to do 2 poloviny.
Budeme první běh sloučení druh znovu na levé polovině,
pak budeme spouštět sloučení řazení na pravé polovině,
a to nám dává nyní 2 poloviny, které jsou seřazeny, a teď budeme kombinovat tyto poloviny spolu.
Je to trochu těžké vidět bez příkladu, takže pojedeme přes pohyby a uvidíme, co se stane.
Takže začnete s tímto seznamem, rozdělili jsme jej do 2 poloviny.
Provozujeme sloučení řazení na levé polovině první.
Tak to je levá polovina, a teď jsme se spustit je přes tento seznam znovu
která je předána do druhu korespondence, a pak se podíváme, znovu,
na levé straně tohoto seznamu, a pořádáme sloučení druh na něm.
Teď, dostaneme se do seznamu čísel 2,
a teď levá polovina je jen 1 prvek dlouho, a my nemůžeme
rozdělit seznam, který je jen 1 prvek do poloviny, a tak jsme jen říct, až budeme mít 50,
který je jen 1 prvek, je to už jsou seřazena.
>> Jakmile jsme hotovi s tím, můžeme vidět, že můžeme
přejít na pravé polovině tohoto seznamu,
a 3 je také tříděn, a tak teď, že obě poloviny tohoto seznamu jsou seřazeny
můžeme spojit tato čísla dohromady.
Tak jsme se podívat na 50 a 3, 3 je menší než 50, tak to jde v první a poté 50 vypovídací
Nyní, to, že udělal, se vrátíme do tohoto seznamu a seřadit je to pravé polovině.
42 je jeho vlastní číslo, takže to už jsou seřazena.
Nyní tedy porovnávat 2 a 3, je menší než 42, tak, že se dostane dát do první,
nyní 42 dostane dát do, a 50 dostane dát dovnitř
Nyní, to je seřazena, jdeme celou cestu zpět na vrchol, 1337 a 15.
No, se nyní podíváme na levé polovině tohoto seznamu; 1337 je samo o sobě, takže to jsou seřazena a to samé s 15.
Takže teď jsme se spojit tyto 2 čísla takové, které původní seznam, 15 <1337,
tak to jde v první, pak 1337 jde dovnitř
A teď jsou seřazena obě poloviny původního seznamu až nahoru.
A vše, co musíme udělat, je spojit tyto.
Dívali jsme se na prvních 2 čísel v tomto seznamu, 3 <15, tak to jde do třídění pole jako první.
15 <42, tak to jde dovnitř Teď, 42 <1337, která vede dovnitř
50 <1337, tak to jde dovnitř a zjistíte, že jsme si vzal 2 čísla off tohoto seznamu.
Takže jsme nejen střídavě mezi 2 seznamy.
Jsme jen se dívá na začátku, a my jsme se ujali prvek
to je menší a pak uvedení do našeho pole.
Nyní jsme se spojil všechny polovin a jsme hotovi.
>> Jakékoliv dotazy týkající se korespondence druh? Ano?
[Student] Pokud je to rozdělení do různých skupin, proč to prostě rozdělit jednou
a máte 3 a 2 ve skupině? [Zbytek otázky nesrozumitelné]
Důvod - takže otázkou je, proč nemůžeme prostě sloučit je v této první fázi poté, co jsme si je vzít?
Důvodem, proč to udělat, začít na levé většina prvků na obou stranách,
a pak ten menší a vložte jej do, je to, že víme, že tyto
Jednotlivé seznamy jsou v seřazena objednávky.
Takže pokud jsem při pohledu na levou většina prvků obou polovin,
Já vím, že to bude nejmenší prvky těchto seznamů.
Tak jsem je dát do nejmenších prvků místech této velké seznamu.
Na druhou stranu, když se na těchto 2 seznamů v druhém stupni se tam,
50, 3, 42, 1337 a 15, jsou ty, které nejsou seřazeny.
Takže když se podívám na 50 a 1337, já dám 50 do mého seznamu jako první.
Ale to není opravdu smysl, protože 3 je nejmenší prvek ze všech z nich.
Takže jediný důvod, proč můžeme udělat tento krok, kombinující proto, že naše seznamy jsou již seřazeny.
Což je důvod, proč jsme se pustit celou cestu až na dno
protože když máme jen jedno číslo, víte, že jedno číslo
samo o sobě je již seřazený seznam.
>> Nějaké otázky? Ne?
Složitost? No, vidíte, že v každém kroku je tu konec čísla,
a můžeme rozdělit seznam na poloviny protokolu n časy,
která je místo, kde jsme stáhni n x n log složitost.
A uvidíte nejlepší případ řadit sloučení je n log n, a to jen tak náhodou
že nejhorší případ, nebo Ω tam je také n log n.
Něco mít na paměti.
Pohybující se na, pojďme na některé extra základního souboru I / O.
Pokud jste se dívali na Scramble, všimnete si, měli jsme nějaký systém
kde byste mohl napsat do souboru protokolu, pokud budete číst pomocí kódu.
Podívejme se, jak byste mohli udělat.
No, máme fprintf, které si můžete myslet, jak jen printf,
ale jen tisk do souboru místo, a proto f na začátku.
Tento druh kódu se zde, co to dělá, je, jak jste mohli vidět v Scramble,
jde přes 2-rozměrné pole tisk z řádcích, co ta čísla jsou.
V tomto případě, printf vypíše na terminál nebo to, co nazýváme standardní výstupní sekce.
>> A teď, v tomto případě, vše, co musíte udělat, je nahradit printf s fprintf,
říct, že to, co soubor, který chcete tisknout, a v tomto případě to prostě vytiskne ji k tomuto souboru
místo tisku to na terminál.
No, pak to vyvolává otázku: Kde se dostaneme tento druh souboru z, že jo?
Jsme míjeli přihlásit do tohoto fprintf fuction, ale neměli jsme ponětí, odkud pochází.
No, brzy v kódu, co jsme měli byl tento kus kódu tady,
který v podstatě říká, že open file volá log.txt.
Co děláme po tom je, že jsme se ujistit, že soubor je skutečně úspěšně otevřen.
Tak to by mohlo selhat z mnoha důvodů, nemáte dostatek místa na vašem počítači, například.
Takže je to vždy důležité než to uděláte jakékoli operace se souborem
že jsme zkontrolovat, zda soubor byl úspěšně otevřen.
Takže to, co, že, to je argument funkce fopen, dobře, můžeme otevřít soubor v mnoha ohledech.
Co můžeme udělat, je, můžeme předat w, což znamená, že přepsat soubor, pokud to vystoupí již,
Můžeme předat A, který se připojí na konec souboru namísto přepsání to,
nebo můžeme určit r, což znamená, pojďme otevřít soubor jen pro čtení.
Takže pokud se program pokusí provést změny v souboru,
křičí na ně a nenechte jim to.
Nakonec, když jsme hotovi s soubor, udělal tím operace na něm,
musíme se ujistit, že soubor zavřete.
A tak na konci programu, budete předat znovu
tohoto souboru, které jste otevřeli, a jen zavřete jej.
Tak tohle je něco důležité, že budete muset ujistěte se, že.
Takže pamatujte si můžete otevřít soubor, pak můžete napsat do souboru,
to operace v souboru, ale pak budete muset uzavřít spis na konci.
>> Jakékoliv dotazy týkající se základního souboru I / O? Ano?
[Student otázka, nesrozumitelným]
Právě tady. Otázkou je, kde to log.txt soubor se objeví?
No, pokud jste právě dát Log.txt, vytvoří ve stejném adresáři jako spustitelný soubor.
Takže pokud Jsi - >> [Student otázka, nesrozumitelným]
Ano. Ve stejné složce, nebo ve stejném adresáři, jak to nazýváte.
Nyní paměť, zásobník, a haldy.
Tak, jak je paměť stanovenými v počítači?
No, umíte si představit, paměť jako druh tohoto bloku zde.
A v paměti máme to, co se nazývá haldy uvízl tam, a zásobník, který je tam dole.
A haldy roste směrem dolů a zásobník roste směrem vzhůru.
Tak jako Tommy uvedeno - oh, dobře, a my máme tyto jiné 4 segmenty, které budu dostanou v druhé -
Jak Tommy řekl dříve, víte, jak jeho funkce se nazývají a volat navzájem?
Ty vytvářejí tento druh zásobníku rámu.
No, jsou-li hlavní calls foo, dostane foo kladen na zásobníku.
Foo calls bar, bar get kladen na zásobníku, a který se dal na stack po.
A pokud se vrátí, každý se dostanou svlečen zásobníku.
Co každý z těchto míst a paměť držet?
No, horní, která je text segmentu, obsahuje vlastní program.
Takže strojového kódu, je to tam, jakmile kompilaci programu.
Další, každý inicializaci globální proměnné.
>> Takže budete mít globální proměnné ve vašem programu, a vy říkáte, jako, a = 5,
, který se dal v tomto segmentu, a přímo pod to,
Máte nějaké neinicializovaná globální data, která je jen INT,
ale neříkejte, že je to stejné na cokoliv.
Uvědomte si, to jsou globální proměnné, takže jste mimo ze dne main.
Takže to znamená, žádné globální proměnné, které jsou deklarovány, ale nejsou inicializovány.
Takže to, co je v haldě? Paměť alokovány s pomocí malloc, který se dostaneme v trochu.
A konečně, s zásobník mít žádné lokální proměnné
a všechny funkce, které by se dalo nazvat všech svých parametrů.
Poslední věc, nemáte opravdu vědět, co proměnné prostředí udělat,
ale vždy, když spustíte program, tam je něco spojené, jako
toto je uživatelské jméno osoby, která běžel program.
A to bude trochu na dně.
Z hlediska paměťových adres, které jsou hexadecimální hodnoty,
hodnoty při horním začínají na 0, a oni jdou celou cestu až na dno.
V tomto případě, pokud jste na 32-bitovém systému,
adresa, na spodní části bude 0x, následovaný AF, protože to je 32 bitů,
která je 8 bajtů, a v tomto případě 8 bajtů odpovídá 8 hexadecimálních číslic.
Tak tady budeš mít, rád, 0xffffff, a tam budeš mít 0.
Takže jaké jsou ukazatele? Někteří z vás nemusí vztahovat to v části před.
ale my jsme se jít přes něj v přednášce, takže ukazatel je jen datový typ
které ukládá, místo nějakého druhu hodnoty, jako je 50, uloží adresu na nějaké místo v paměti.
Stejně jako tento paměti [nesrozumitelné].
Takže v tomto případě, to, co jsme, je, že máme ukazatel na celé číslo nebo int *,
a obsahuje tuto hexadecimální adresu 0xDEADBEEF.
>> Takže to, co máme, je, nyní se tento ukazatel na nějaké místo v paměti,
a to je jen, hodnota 50 je v tomto místě paměti.
Na některých 32-bitových systémech, ve všech 32-bitových systémech, ukazatele zabírají 32 bitů nebo 4 bajty.
Ale, například, na 64-bitovém systému, ukazatele jsou 64 bitů.
Tak to je něco, co budete chtít mít na paměti.
Tak na konec-bit systému, ukazatel koncové bitů.
Ukazatele jsou druh těžko stravitelné bez zbytečných věcí,
takže se pojďme projít příklad dynamického přidělování paměti.
Co dynamické přidělování paměti pro vás dělá, nebo to, co nazýváme malloc,
To vám umožní přidělit nějaký údajů mimo sady.
Takže tato data je něco trvalejšího pro celou dobu trvání programu.
Vzhledem k tomu, jak víte, pokud jste deklarovat x uvnitř funkce, a že funkce vrací,
již nemáte přístup k datům, který byl uskladněn v x.
Co ukazatele nám udělat, je, že nám tyto paměťové nebo obchod hodnot
v jiném segmentu paměti, a to haldy.
Nyní, jakmile se vrátíme z funkcí, tak dlouho, jak budeme mít ukazatel
na dané místo v paměti, pak to, co můžeme udělat, je, že jsme se jen podívat na hodnoty tam.
Pojďme se podívat na příklad: Toto je naše paměť layout znovu.
A my máme tuto funkci, hlavní.
Co to udělá, je - v pořádku, tak jednoduché, že jo? - Int x = 5, to je jen variabilní na zásobníku v main.
>> Na druhou stranu, teď deklarujeme ukazatel, který volá funkci giveMeThreeInts.
A tak teď půjdeme do této funkce a vytvoříme nový zásobníku rámec pro něj.
Nicméně v tomto zásobníku rámu, prohlašujeme int * teplota,
které v celých mallocs 3 pro nás.
Takže velikost z int dá nám, kolik bytů to int je,
a malloc nám dává, že mnoho bytů z místa na haldě.
Takže v tomto případě, jsme vytvořili dostatečný prostor pro 3 celých čísel,
a haldy je způsob, jak se tam, což je důvod, proč jsem vypracována to výš.
Jakmile jsme hotovi, vrátíme se sem, budete potřebovat pouze 3 ints vrátil,
a vrátí adresu, v tomto případě více než kdy že paměť je.
A jsme si stanovili ukazatele = přepínač, a tam máme jen další ukazatel.
Ale co to vrátí funkce je stohovat zde a zmizí.
Takže teplota zmizí, ale stále ještě udržet adresu kde
ty 3 čísla jsou uvnitř sítě.
Takže v této sadě, jsou ukazatele jsou rozsahem lokálně pro skládaného rámu,
ale paměť, na které se vztahují se na hromadu.
>> Dává to smysl?
[Student] Mohl byste to zopakovat? >> [Joseph] Ano.
Takže když jsem se vrátit jen trochu, uvidíte, že teplota přidělené
některé paměti na haldě up there.
Takže když tato funkce, giveMeThreeInts vrací, to stack zde zmizí.
A s ním jakékoli proměnných, v tomto případě, to ukazatel, který byl rozdělen v skládaném rámu.
, Který se chystá zmizet, ale od té doby jsme se vrátili temp
a dali jsme se ukazatel = temp, ukazatel se nyní bude ukazovat stejnou paměť umístění váhy temp was.
Takže teď, i když ztrácíme temp, že místní ukazatele,
jsme ještě udržet adresu paměti, co to bylo ukázal dovnitř té proměnné ukazatele.
Otázky? To může být trochu matoucí topic, pokud jste už nad ním v oddíle.
Můžeme, bude váš TF určitě jít přes něj, a samozřejmě budeme moci odpovědět na otázky
na konci sledovaného relace za to.
Ale to je trochu složité téma, a mám další příklady, které se chystáte ukázat
které pomohou objasnit, co vlastně jsou ukazatele.
>> V tomto případě, ukazatele odpovídají polí,
takže můžu jen použít tento ukazatel jako stejnou věc jako int pole.
Takže jsem indexování do 0, a změnit první číslo na 1,
změnou druhý číslo na 2 a 3. celé číslo 3.
Takže více na ukazateli. No, vzpomínám Binky.
V tomto případě jsme si přiděleno ukazatel, nebo jsme prohlásil ukazatel,
ale zpočátku, když jsem prohlásil ukazatel, to neodkazuje kdekoli v paměti.
Je to jen odpadky hodnoty uvnitř ní.
Takže nemám ponětí, kde tento ukazatel ukazuje.
To má adresu, která je jen plná 0 a 1, kde byl původně deklarován.
Nemůžu nic dělat s tím, dokud jsem volat malloc na to
a pak mi to dává málo místa na haldě, kde se můžu obrátit hodnoty uvnitř.
Pak znovu, nevím, co je uvnitř této paměti.
Takže první věc, kterou musím udělat, je zkontrolovat, zda systém měl dostatek paměti
aby mě zpět 1 celé číslo na prvním místě, což je důvod, proč to dělám kontrolu.
Pokud je ukazatel null, to znamená, že nemá dostatek místa nebo nějaké jiné chybě,
tak jsem měl ukončit z mého programu.
Ale pokud se to podaří, teď mohu používat tento ukazatel
a co * ukazatel dělá, je, že jdou tam, kde je adresa
tam, kde tato hodnota je, a to nastaví se rovná 1.
Tak tady, jsme kontrolu, zda se paměť existuje.
>> Jakmile budete vědět, že existuje, můžete si dát do něj
jakou hodnotu chcete dát do ní, v tomto případě 1.
Jakmile jsme hotovi s ním, je třeba uvolnit tento ukazatel
protože se musíme dostat zpět do systému, který paměti, že budete požádáni v první řadě.
Vzhledem k tomu, že počítač neví, kdy jsme s ním udělal.
V tomto případě jsme explicitně říkat, ano, my jsme udělali s tímto paměti.
Pokud nějaká jiná proces potřebuje, jiný program potřebuje, neváhejte jít dopředu a vzít ji.
Co můžeme udělat, je také můžeme jen získat adresu lokálních proměnných na televizoru.
Takže int x je uvnitř skládaného rámu main.
A když budeme mít tuto ampersand, tento a provozovatel, co dělá, je
trvá x, a x je jen některé údaje v paměti, ale má adresu.
Je umístěn někde. Takže volání a x, co to dělá, je, že nám dává adresu x.
Tím, že děláme ukazatel místo, kde x je v paměti.
Teď už jen udělat něco jako * x, budeme si 5 zpět.
Hvězda se nazývá dereferencing to.
Můžete sledovat adresu a dostanete hodnotu toho zde uložené.
>> Nějaké otázky? Ano?
[Student] Pokud nechcete dělat 3-špičatý věc, to ještě kompilaci?
Ano. Pokud nechcete dělat 3-ukazatel věc, je to stále bude sestavovat,
ale já ti ukážu, co se děje v druhé, a bez toho, že
že to, co nazýváme nevracení paměti. Nedáváte systému
zpět svou paměť, takže po chvíli program bude hromadit
paměti, že to není pomocí, a nic jiného ji použít.
Pokud jste někdy viděli Firefox s 1500000 kb na vašem počítači,
v Správci úloh, že to, co se děje.
Máte nevracení paměti v programu, že nejste manipulaci.
Tak, jak se pointerovou aritmetiku práce?
No, ukazatel aritmetika je něco jako indexování do pole.
V tomto případě, mám ukazatel, a to, co dělám je, že jsem, aby ukazatel bod na první prvek
tohoto pole 3 celých čísel, která jsem přiděleny.
Takže teď, co mám dělat, star pointer jen změní první prvek v seznamu.
Hvězda ukazatel 1 bodů za zde.
Takže ukazatel je tady, ukazatel 1 je tady, ukazatel 2 je tady.
>> Takže jen přidat 1 je totéž, jako pohybující se tohoto pole.
Co máme udělat, je, když děláme ukazatel 1 dostanete adresu sem,
a za účelem získat hodnotu v tu můžete dát hvězdu z celého výrazu
k dereference to.
Takže, v tomto případě, jsem nastavení prvního umístění v tomto poli na hodnotu 1,
druhé umístění na 2, a třetí umístění na 3..
Pak to, co dělám tady je mi tiskne náš ukazatel 1,
který jen mi dává 2.
Teď jsem zvyšování ukazatel, takže ukazatel rovná ukazatel 1,
který se pohybuje dopředu.
A tak teď, když jsem vytisknout ukazatel 1, ukazatel +1 je nyní 3,
což v tomto případě se vytiskne 3.
A aby uvolnila něco, ukazatel, že dám ji
musí směřovat na začátku pole, které jsem se vrátil z malloc.
Takže, v tomto případě, pokud bych měl zavolat 3 tady, by to nebylo správné,
, protože je to ve středu pole.
Musím odečíst dostat do původního umístění
Počáteční první místo, než jsem si uvolnit ji.
Takže, tady je více zapojit příklad.
V tomto případě, jsme přidělování 7 znaků pole znaků.
>> A v tomto případě to, co děláme, je, že jsme looping přes první 6 z nich,
a my jsme nastavením na Z.
Takže, pro int i = 0, i> 6, i + +,
Takže, ukazatel + i se jen nám, v tomto případě,
ukazatel, ukazatel 1, ukazatel +2, ukazatel 3, a tak dále a tak dále ve smyčce.
Co to udělá, je, že dostane tu adresu, dereferences to, aby si hodnoty,
a změny, aby hodnota v Z.
Pak na konci si pamatuju, je řetězec, ne?
Všechny řetězce mají skončit s nulovým ukončovací znak.
Takže, co dělám, je ukazovátko 6 I dal null zakončení znak a.
A teď, co jsem v podstatě dělal tady provádí printf pro řetězec, ne?
>> Takže, když to printf teď, když je to dosažení konce řetězce?
Když zasáhne null ukončující znak.
Takže, v tomto případě, mé původní ukazatel ukazuje na začátku tohoto pole.
I vytisknout první znak ven. I přesunout přes jednoho.
I vytisknout tuto postavu ven. I pohybovat nad.
A já si to tak, dokud jsem se dostat na konec.
A teď konec * ukazatel bude dereference a dostat se na null ukončující znak zpět.
A tak můj while běží pouze v případě, že hodnota není null ukončovací znak.
Tak, teď jsem opustit z této smyčky.
A tak když jsem odečíst 6 z tohoto ukazatele,
Vrátím se celou cestu na začátek.
Nezapomeňte, dělám to proto, že musím jít na začátek, aby se osvobodil ho.
>> Takže jsem věděl, že to hodně. Jsou nějaké dotazy?
Prosím, ano?
[Student otázka nesrozumitelná]
Můžete říct, že hlasitěji? Promiňte.
[Student] Na posledním snímku těsně předtím, než jste osvobodil ukazatel,
kde se skutečně změně hodnoty ukazatele?
[Joseph] Tak, tady. >> [Student] Oh, dobře.
[Joseph] Tak, mám ukazatel minus minus, vpravo,
který se pohybuje na věc zpět o jeden, a pak jsem osvobodit to,
protože tento ukazatel je třeba zdůraznit na začátku pole.
[Student] Ale to by nebyla nutná, kdybyste přestal po tomto řádku.
[Joseph] Takže, když jsem přestal po tomto, by to bylo považováno za únik paměti,
protože jsem neběžel zdarma.
[Student] I [nesrozumitelné] po prvních třech řádcích, kde jste měli ukazatel 1 [nesrozumitelné].
[Joseph] Uh-huh. Takže, co je otázka tam?
Promiňte. Ne, ne. Jdi, jdi, prosím.
[Student] Takže, nejste změnou hodnoty ukazatelů.
Ty by se musel udělat ukazatel minus minus.
[Joseph] Ano, přesně tak.
Takže, když jsem si ukazatel 1 a ukazatel 2,
Nedělám ukazatel rovná ukazatel 1.
Takže, ukazatel jen zůstane ukazuje na začátku pole.
Je to pouze tehdy, když dělám plus plus, že nastaví hodnotu zpět do ukazatele,
že to vlastně pohybuje to spolu.
Dobrá.
Další otázky?
>> Opět platí, že pokud je to druh ohromující, bude to zahrnuty v relaci.
Zeptejte se svého vyučujícího, kolegu o tom, a my můžeme odpovídat na otázky na konci.
A obvykle se nám nelíbí to udělat minus věc.
To je vyžadují, abych sledování toho, jak moc jsem posun v poli.
Takže, obecně, je to jen vysvětlit, jak funguje ukazatel aritmetické.
Ale to, co obvykle rádi udělali je, že jsme chtěli vytvořit kopii ukazatele,
a pak budeme používat tuto kopii, když jdeme kolem v řetězci.
Takže, v těchto případech použít kopie vytisknout celý řetězec,
ale nemáme dělat jako ukazatel minus 6 nebo sledovat, jak moc jsme se přestěhovali v tomto,
jen proto, že víme, že náš původní bod je stále poukazoval na začátek seznamu
a vše, co změnil je to kopie.
Takže, obecně měnit kopie původního ukazatel.
Nesnažte se nějak jako - nedělej změnit originály.
Snažit se změnit pouze kopie originálu.
Takže, si všimnete, když míjíme řetězec do printf
nemusíte dát hvězdu před ním jako jsme to udělali se všemi ostatními dereferences, že jo?
Takže, pokud můžete vytisknout celý řetězec% s očekává, že je adresa,
a v tomto případě ukazatel nebo v tomto případě jako pole znaků.
>> Postavy, char * s, a pole jsou totéž.
Ukazatel je znaků, a pole znaků jsou totéž.
A tak, vše, co musíte udělat, je předat ukazatel.
Nemáme předat jako * ukazatel nebo něco podobného.
Takže, pole a ukazatele jsou totéž.
Když děláte něco jako x [y] sem na pole,
co to dělá pod kapotou je to říká, jo, je to pole znaků,
takže je to ukazatel.
A tak x je totéž,
a tak to, co dělá, je, že přidá y na x,
který je totéž, jako kupředu v paměti, že mnoho.
A teď x + y nám dává nějaký adresy,
a my dereference adresu nebo sledovat šipku
kde toto místo v paměti, je, a dostaneme hodnotu z tohoto umístění v paměti.
Takže, takže tyto dva jsou přesně totéž.
Je to jen syntaktický cukr.
Oni dělají stejnou věc. Jsou to jen různé syntactics pro sebe.
>> Takže, co může pokazit s ukazateli? Stejně jako, hodně. Dobře. Takže, špatné věci.
Některé špatné věci, které můžete udělat, nejsou kontroly, zda vaše malloc volání vrátí null, ne?
V tomto případě, se ptám systém, aby mi - co je to číslo?
Jako 2000000000 krát 4, protože velikost celé číslo je 4 bajty.
Ptám se ho, jako 8000000000 bajtů.
Samozřejmě můj počítač se nebude moci dát mi tolik paměti zpátky.
A my jsme to zjistili, zda-li to je null, takže když se snažíme dereference to tam -
sledovat šipku na místo, kde to bude - nemáme, že paměť.
To je to, co nazýváme dereferencing nulový ukazatel.
A to v podstatě způsobí, že se segfault.
To je jeden ze způsobů, jak si můžete segfault.
Další špatné věci, které můžete udělat - oh dobře.
To bylo dereferencing nulový ukazatel. Dobře.
Další špatné věci - dobře, opravit, že jste právě dal šek tam
, který kontroluje, zda je ukazatel null
a ukončete z programu, pokud se to stane, že malloc vrací nulový ukazatel.
To je xkcd komické. Lidé pochopili to hned. Tak nějak.
>> Tak, paměť. A šel jsem nad tím.
Jsme volání malloc ve smyčce, ale pokaždé, když říkáme malloc
ztrácíme přehled o tom, kde tento ukazatel ukazuje na,
proto, že jsme praštit ho.
Takže, počáteční volání malloc mi dává paměť tady.
Moje ukazatel ukazatele na toto.
Teď, nemám uvolnit, takže teď říkám malloc znovu.
Teď to ukazuje tady. Nyní má paměť ukazuje tady.
Polohovací tady. Polohovací tady.
Ale já jsem ztratil přehled o adresách všech paměti támhle, že jsem přidělena.
A tak teď nemám žádný odkaz na ně už.
Takže, nemůžu osvobodit mimo tento smyčky.
A tak za účelem stanovení něco takového,
pokud jste zapomněl volné paměti a stáhni nevracení paměti,
Musíte uvolnit paměť uvnitř této smyčky, jakmile budete hotovi s ním.
No, to je to, co se stane. Vím, že spousta z vás nesnáším.
Ale teď - yay! Zde získáte jako 44.000 KB.
Takže, vy uvolnit, na konci smyčky,
a že se to prostě uvolnit paměť pokaždé.
V podstatě, váš program nemá nevracení paměti už.
>> A teď něco jiného, ​​co můžete udělat, je uvolnit paměť, kterou jste žádal dvakrát.
V tomto případě je malloc něco, změnit jeho hodnotu.
Můžete uvolnit jej jednou, protože jsi říkal, že se s tím.
Ale pak jsme osvobozeni znovu.
To je něco, co je dost špatné.
To nebude zpočátku segfault,
ale po chvíli, co to dělá, je dvojí uvolnění tomuto korumpuje svůj haldy strukturu,
a naučíte trochu víc o tom, pokud se rozhodnete vzít třídu jako CS61.
Ale v podstatě po chvíli váš počítač bude zmást
o tom, co paměťová místa jsou ta, kde a kdy je to uloženo -
, kde jsou data uložena v paměti.
A tak uvolnění ukazatel dvakrát, je špatné, že nechcete dělat.
>> Další věci, které se mohou pokazit nepoužívá sizeof.
Takže, v tomto případě malloc 8 bajtů,
a to je to samé jako dvě celá čísla, ne?
Tak, to je naprosto bezpečné, ale je to?
No, jak Lucas mluvil o na různých architekturách,
čísla jsou různých délek.
Takže, na zařízení, které používáte, čísla jsou asi 4 byty,
ale na nějakém jiném systému, které by mohly být 8 bajtů nebo může být 16 bytů.
Takže, pokud jsem použít toto číslo sem,
tento program by mohl pracovat na zařízení,
ale to nebude alokovat dostatek paměti na nějakém jiném systému.
V tomto případě, je to, co operátor sizeof se používá.
Když zavoláme sizeof (int), co to dělá, je
to nám dává velikost celé číslo v systému, který běží program.
Takže, v tomto případě, bude sizeof (int) vrátí 4 na něco takového zařízení,
a nyní tato vůle 4 * 2, což je 8,
, který je jen množství prostoru potřebné pro dvou celých čísel.
Na jiném systému, pokud int je jako 16 bajtů nebo 8 bajtů,
to jen tak vrátit dostatek bytů pro uložení tuto částku.
>> A konečně, struct.
Takže, pokud jste chtěli uložit sudoku desku v paměti, možná jak to uděláme?
Můžete si myslet, ze jako proměnné pro první věc,
proměnná pro druhou věc, proměnná pro třetí věc,
proměnná pro čtvrté věc - špatný, ne?
Takže, jedna zlepšení můžete provést na vrcholu je to, aby se 9 x 9 pole.
To je v pořádku, ale co když jste chtěli přidružit i jiné věci s radou sudoku
jako to, co obtížnost desce je,
nebo, například, jaké jsou vaše skóre, nebo jak dlouho to trvalo vám vyřešit tento program?
No, co můžete udělat, je, že můžete vytvořit struct.
Co jsem v podstatě říká, je, že jsem vymezení tuto strukturu tady,
a já jsem definování sudoku deska, která se skládá z desky, která je 9 x 9.
>> A co to má to má ukazatele na název úrovně.
Má také X a Y, které jsou souřadnice, kde jsem teď.
To má také čas strávený [nesrozumitelný], a to má celkový počet tahů jsem zadaných doposud.
A tak v tomto případě, mohu seskupit spoustu dat do jediného struktury
místo toho, aby ji jako létání kolem jako různé proměnné
že nemůžu sledovat.
A to nám umožňuje mít jen hezkou syntaxi pro druh odkazování různé věci uvnitř tohoto struct.
Já si prostě board.board, a mám sudoku desku zpět.
Board.level, jsem si, jak těžké to je.
Board.x a board.y dej mi souřadnice, kde bych mohl být na desce.
A tak jsem přístup, co nazýváme pole v struct.
Toto definuje sudokuBoard, což je typ, který mám.
A teď jsme tady. Mám proměnnou s názvem "board" typu sudokuBoard.
A tak teď můžu přistupovat všechna pole, která tvoří tuto strukturu tady.
>> Jakékoliv otázky structs? Ano?
[Student] Pro int x, y, jste prohlásil oba na jednom řádku? >> [Joseph] Uh-huh.
[Student] Takže, mohl by si udělat se všemi z nich?
Stejně jako v roce X, Y čárka časy, že celkové?
[Joseph] Ano, mohl byste určitě udělat, ale důvod, proč jsem dal x a y na stejném řádku -
a otázkou je, proč můžeme jen to na stejném řádku?
Proč jsme jen dát všechny tyto na stejném řádku je
x a y jsou ve vzájemném vztahu,
a je to jen stylisticky přesnější, v tom smyslu,
protože je to seskupení dvě věci na stejném řádku
že jako druh se vztahují ke stejné věci.
A já prostě rozdělit tyto od sebe. Je to jen styl věc.
Je funkčně není rozdíl vůbec.
Jakékoliv další otázky týkající se structs?
Můžete definovat Pokédex s struct.
Pokémon má své číslo a má dopis, vlastníka, typ.
A pak, pokud máte pole Pokémon, můžete vytvořit Pokédex, že jo?
Dobře, v pohodě. Takže, otázky týkající se structs. Ti, kteří jsou příbuzní k structs.
>> Konečně, GDB. Co GDB nechat udělat? To vám umožní ladit svůj program.
A pokud jste nepoužili GDB, bych doporučil sledovat krátké
a jen tak nad tím, co GDB je, jak s ním pracovat, jak byste mohli použít,
a vyzkoušet na programu.
A tak to, co GDB můžete udělat, je, že umožňuje Pozastavit [nesrozumitelné] až do vašeho programu
a praktické linie.
Například, chci pozastavit plnění v souladu jako 3 z mého programu,
a když jsem na řádku 3 mohu vytisknout všechny hodnoty, které jsou tam.
A tak to, co nazýváme jako zastavil v řadě
je nazýváme uvedení zarážku na tomto řádku
a pak můžeme vytisknout proměnné na stavu programu v té době.
>> Můžeme pak odtamtud krokovat program řádek po řádku.
A pak jsme se podívat na stav zásobníku v té době.
A tak aby bylo možné používat GDB, co děláme, je říkáme řinčení na soubor C,
ale musíme předat-ggdb vlajkou.
A jakmile jsme skončili s tím jsme jen spustit gdb na výsledném výstupního souboru.
A tak si trochu jako hmotnost textu jako je tento,
ale opravdu vše, co musíte udělat, je zadat příkazy na začátku.
Přestávka hlavní klade zarážku na hlavní.
Seznam 400 uvádí řádky kódu kolem řádku 400.
A tak v tomto případě stačí se podívat kolem sebe a říci, oh,
Chci nastavit zarážku na řádku 397, který je v tomto řádku,
a pak se váš program běží do tohoto kroku, a to rozbije.
Bude to pauze, a můžete tisknout, například, hodnota nízká nebo vysoká.
A tak tam jsou banda příkazy, které potřebujete vědět,
a to slideshow bude stoupat na webových stránkách,
takže pokud si jen chcete odkazovat těchto nebo jako dát je na své taháky, neváhejte.
>> Cool. To bylo Quiz Review 0, a budeme držet kolem, pokud máte nějaké otázky.
Dobrá.
>> [Potlesk]
>> [CS50.TV]