[Powered by Google Translate] [Týden 4]
[David J. Malan] [Harvard University]
[To je CS50.] [CS50.TV]
>> Dobře, to je CS50, a to je začátek 4. týdnu
a to je jeden z nejpomaleji možných algoritmů třídění.
Který z nich je to, že jsme právě shlédli tam?
To bylo bublina řazení, aby velké O (n ^ 2) + součet,
a opravdu nejsme jediní, kdo v tomto světě zřejmě vědí,
co bublina sort nebo jeho hrací čas.
Opravdu, to byl rozhovor s Ericem Schmidtem z Google
a bývalý senátor Barack Obama jen před několika lety.
>> Nyní, senátor, jsi tady na Google,
a jsem rád, že předsednictví jako pohovoru.
Nyní, je těžké dostat práci jako prezident, a ty jdeš přes nástrahami teď.
Je také těžké získat práci na Google.
Máme otázky, a žádáme naše kandidáty otázky,
a tohle je od Larry Schwimmer.
Vy myslíte, že si dělám legraci? Je to přímo tady.
Jaká je nejúčinnější způsob, jak třídit milion 32-bit celé číslo?
[Smích]
No-
Je mi to líto. >> Ne, ne, ne, ne.
Myslím, že bublina druh by špatný způsob, jak jít.
>> Pojď, který mu řekl, toto?
Minulý týden jsme připomenout si pauzu od kódu, alespoň na jeden den,
a začal se zaměřením na některé vyšší úrovni myšlenek a řešení problémů obecně
v rámci vyhledávání a řazení,
a jsme zavedli něco, co jsme neměli Slap tento název minulý týden,
ale asymptotická notace, Big O, Big Omega,
a někdy Big Theta zápis, a ty byly jednoduchý způsob
popsat čas běhu algoritmů,
jak dlouho to trvá, než algoritmus spustit.
>> A vy si možná vzpomenou, že jsi mluvil o době chodu z hlediska velikosti
vstupu, který jsme obvykle nazýváme n, bez ohledu na problém může být,
, kde n je počet osob v místnosti,
počet stránek v telefonním seznamu, a začali jsme psát věci
jako O (n ^ 2) nebo O (n), nebo O (n log n),
a to i když matematika nebyla úplně fungovat tak dokonale
a to bylo n ² - n / 2 nebo něco takového
bychom místo toho jen zahodit některé z nižších řádů,
a motivace je, že opravdu chceme
druh objektivního způsobu hodnocení
výkon programů nebo výkon algoritmů
že na konci dne nemá nic společného, ​​například,
s rychlosti vašeho počítače dnes.
>> Například, pokud se rozhodnete bubliny třídění,
nebo se rozhodnete sloučit řazení nebo výběr druhu na dnešním počítači,
2 GHz počítač, a spustit jej,
a to trvá určitý počet sekund, příští rok je tu 3 GHz
nebo 4 GHz počítač, a ty by se pak tvrdit, že "Wow, můj algoritmus
je nyní dvakrát tak rychle, "když ve skutečnosti to zjevně není tento případ.
Je to jen hardware dostal rychleji, ale váš počítač
není, a tak jsme opravdu chcete vyhodit věci, jako je
násobky 2 nebo násobky 3, pokud jde o popis
jak rychle nebo jak pomalu algoritmus je a opravdu soustředit jen
na n nebo nějaký faktor této smlouvy,
část výkonu jeho jako v případě druhů z minulého týdne.
A připomínají, že s pomocí druhu korespondence
jsme byli schopni udělat mnohem lépe, než bublina řadit a výběru seřadit
a dokonce i vkládání sort.
>> Máme se na n log n, a znovu,
Připomínám, že log n obecně se odkazuje na něco, co roste
pomaleji pak n, tak n log n dosud byla dobrá
protože to bylo menší, než ² n.
Ale k dosažení n log n s řadit slučovací
co bylo základní zárodek myšlenky, že jsme museli využít
že jsme také zadlužuje zpátky v týdnu 0?
Jak jsme řešit problém řazení chytře s řadit slučovací?
Jaký byl klíčový vhled, snad?
Každý, kdo vůbec.
Dobře, pojďme o krok zpět.
Popište sloučit druh vlastními slovy.
Jak to funguje?
Dobře, budeme veslovat zpátky týdenních 0.
Dobře, jo.
[Neslyšitelné-student]
Dobře, dobře, tak jsme se rozdělili pole čísel do 2 kusy.
Jsme seřazeny každý z těchto kusů, a pak jsme sloučili je,
a my jsme viděli tuto myšlenku před braní problém, který je takhle velký
a sekání je, jak se na problém, který je to velké nebo to velké.
>> Připomeňme telefonního seznamu příklad.
Vzpomeňte si na vlastní algoritmus počítání od týdny,
tak sloučit řadit byl shrnut v tomto pseudokódu zde.
Když jste stejně n prvků, nejprve to byl zdravý rozum zkontrolovat.
Pokud n <2, pak nedělají vůbec nic
protože pokud n <2, pak n je zřejmě 0 nebo 1,
a tak pokud je to buď 0 nebo 1 nic vyřešit.
To je vše.
Váš seznam je již triviálně seřazen.
Ale jinak, pokud máte 2 nebo více prvků jít dopředu a rozdělit je
do 2 poloviny, levou a pravou.
Seřadit každé z těchto polovin, a pak sloučit seřazené poloviny.
Ale problém je, že na první pohled to pocit, jako bychom to plavit.
To je kruhová definice v tom, že pokud jsem vás požádal, abyste seřadit tyto n prvků
a vy mi říkáte, "Dobře, fajn, budeme třídit ty n / 2 a ty n / 2 prvků,"
pak moje další otázka bude "Fajn, jak si setřídit n / 2 prvků?"
>> Ale protože struktury tohoto programu,
protože tam je tento referenční případ, abych tak řekl,
tento zvláštní případ, který říká, že pokud je n <nějakou pevnou hodnotu, jako je 2 návratu ihned.
Neodpovídejte se stejným kruhovou odpověď.
Tento proces, bude tento cyklová nakonec skončí.
Když se tě zeptám "Jak tyto n prvky," a vy říkáte, "Fine, třídit tyto n / 2,"
pak řekneš: "Dobře, trochu to n / 4, n / 8, n/16,"
nakonec budete dělit dost velký počet
že budete mít jen 1 prvek doleva, na kterém místě si můžete říct,
"Tady, tady je seřazena jeden prvek."
Pak lesk tohoto algoritmu tady je odvozena od skutečnosti
, že jakmile budete mít všechny tyto jednotlivě tříděné seznamy,
z nichž všechny jsou velikosti 1, což se zdá být zbytečné,
jakmile začnete sloučení a sloučení
si vybudovat konečně jako Rob dělal ve videu konečně jsou seřazena seznam.
>> Ale tato myšlenka sahá daleko za hranice třídění.
Tam je tento nápad zakotven v tomto programu známého jako rekurze,
nápad, kterým jste program,
a vyřešit nějaký problém si říkáš,
nebo dát do souvislosti programovacích jazyků, které jsou funkce,
a za účelem vyřešení problému, můžete funkce říkáš
znovu a znovu a znovu, ale funkce
nelze volat sami nekonečně mnohokrát.
Nakonec budete muset dna, abych tak řekl,
a máte nějaké pevně základní podmínku, která říká, že
V tomto bodě přestat říkat si tak, aby celý proces
Nakonec se ve skutečnosti zastavit.
Co to vlastně znamená, aby recurse?
>> Pojďme se podívat, jestli můžeme udělat jednoduchý, triviální příklad, řekněme,
3 osoby se mnou tady na jevišti, když někdo je pohodlné.
1, pojď nahoru, 2 a 3.
Pokud 3 chtít přijít sem.
Pokud chcete postavit hned vedle mě tady v řadě, předpokládám, že problém na dosah ruky
je velmi triviální spočítat počet lidí, kteří jsou zde.
Ale upřímně řečeno, jsem unavená ze všech těchto počítání příkladů.
To bude nějakou dobu trvat, 1, 2, a tečka, tečka, tečka.
Bude to trvat věčně.
Já bych raději punt tento problém zcela pomocí-Jak se jmenujete?
Sara. >> Sara, v pořádku.
Kelly. >> Kelly a?
>> Willy. >> Willy, Sara, Kelly, a Willy.
Právě teď jsem se ptal někdo
kolik lidí je na této scéně, a já nemám ponětí.
To je opravdu dlouhý seznam, a tak místo toho budu dělat tento trik.
Jdu se zeptat na osobu vedle mě dělat většinu práce,
a jakmile se provádí dělá většinu práce
Budu dělat co nejmenší množství práce je možné, a stačí přidat 1
na jakoukoli její odpověď je, tak je to tady.
Byl jsem požádán, kolik lidí je na jevišti.
Kolik lidí je na jevišti vlevo z vás?
Ze mě zbylo? >> Dobře, ale nebudou podvádět.
To je dobře, to je pravda, ale pokud chceme, aby i nadále tuto logiku
předpokládejme, že si podobně chcete punt tento problém na levé straně vás,
takže spíše než odpovědi přímo do toho pusťte a jen projít do minusu.
Ach, kolik lidí je na levé straně mě?
Jak mnoho lidí jsou umístěny na levé?
1.
[Smích]
Dobře, tak 0, takže to, co teď Willy udělal
je, že jste se vrátil vaši odpověď tímto směrem říká 0.
Nyní, co byste měli dělat? >> 1.
Dobře, takže jste 1, takže si řekl, "Dobře, budu přidávat 1
na jakoukoli Willyho hrabě, "tak 1 + 0.
Nyní jste 1 tak, aby vaše odpověď na pravé straně je nyní-
1. >> A já bych být 2.
Dobré, takže bereš předchozí odpověď 1,
přidání minimální množství práce, kterou chcete udělat, což je +1.
Nyní máte 2, a potom mi podat které hodnota?
3, myslím, promiň, 2.
Dobré.
>> No, měli jsme 0 vlevo.
Pak jsme měli 1, a pak přidáme 2,
a teď jsi podal mi číslo 2,
a tak jsem řekl, v pořádku, 1, 3.
Tam je opravdu 3 lidé stojící vedle mě na této scéně,
takže můžeme zřejmě udělal velmi lineárně,
velmi v módě zřejmé, ale co jsme opravdu?
Vzali jsme si problém velikosti 3 původně.
Pak jsme roztřídili do problému velikosti 2,
pak problém velikosti 1, a nakonec referenční případ
Bylo to opravdu, oh, tam nikdo není,
na kterém místě Willy vrátil účinně pevně odpověď několikrát,
a druhý byl pak bublal vzhůru, bublal vzhůru, bublalo up,
a pak přidáním do tohoto jednoho dodatečného 1
Vytvořili jsme tuto základní myšlenku rekurze.
>> Nyní, v tomto případě je to opravdu vyřešit problém
jakékoli účinněji než jsme viděli doposud.
Ale přemýšlet o algoritmech jsme udělali na jevišti tak daleko.
Měli jsme 8 kusů papíru na tabuli,
na videu, kdy Sean hledal číslo 7, a co udělal opravdu?
No, on to neudělal nějaký druh rozděl a panuj.
Neudělal jakékoliv rekurze.
Spíše to právě udělal tento lineární algoritmus.
Ale když jsme zavedli myšlenku seřazena čísel na jevišti žít minulý týden
pak jsme měli tento instinkt jít do středu,
na kterém místě jsme měli menší seznam velikosti 4 nebo jiném seznamu velikosti 4,
a pak jsme měli přesně stejný problém, tak jsme opakovali, opakoval, opakoval.
Jinými slovy, recursed.
Děkuji moc se do našeho 3 dobrovolníků zde pro demonstraci rekurze s námi.
>> Pojďme se podívat, jestli nemůžeme to teď trochu konkrétnější,
řeší problém, který jsme opět mohli dělat docela snadno,
ale budeme používat jako odrazový můstek k provádění tohoto základní myšlenku.
Pokud chci spočítat součty spoustu čísel,
například, jestliže si projít v počtu 3,
Chci, aby vám hodnotu sigma 3,
takže součet 3 + 2 + 1 + 0.
Chci se dostat zpět odpověď 6,
takže budeme provádět tuto sigma funkci, to shrnutí funkce
že opět bere na vstupu, a potom vrátí shrnutí
z tohoto počtu celou cestu až na 0.
Mohli bychom to hezké jednoduše, že?
Mohli bychom to udělat s nějakým druhem smyčky struktury,
tak nechte mě jít dopředu a dostat to začalo.
>> Zahrnout stdio.h.
Dovolte mi, abych se sám do hlavní pracovat s tady.
Pojďme uložit jako sigma.c.
Pak jsem jít sem, a budu deklarovat int n,
a já budu dělat následující, zatímco uživatel nespolupracuje.
Zatímco uživatel mi nedala kladné číslo
nech mě jít napřed a přiměli je pro n = GetInt,
a dovolte mi, abych jim nějaké instrukce o tom, co dělat,
takže printf ("Positive integer prosím").
Jen něco relativně jednoduchého, jako to tak, že v době, kdy jsme narazili řádek 14
nyní máme kladné číslo pravděpodobně v n.
>> Nyní se pojďme udělat něco s tím.
Nech mě jít dopředu a počítat součty, takže int sum = sigma (n).
Sigma je jen shrnutí, takže jsem jen psát to v milovník způsobem.
Budeme prostě říkat sigma tam.
To je částka, a teď jdu vytisknout výsledek,
printf ("Součet je% d, \ n", sum).
A pak se vrátím 0 pro správnou míru.
Udělali jsme všechno, co tento program vyžaduje kromě zajímavé části,
který je skutečně realizovat sigma funkci.
>> Nechte mě jít sem dolů až na dno, a dovolte mi, abych určil funkci sigma.
Má to vzít proměnnou, která je typu integer,
a jaká data typu nechci vrátit pravděpodobně z sigma?
Int, protože chci, aby to tak, aby odpovídala mé očekávání na lince 15.
V tu nechte mě jít dopředu a provedení tohoto
v docela přímočaře.
>> Pojďme dál a říct, int sum = 0,
a teď jdu mít málo pro smyčce zde
že se to říct něco takového,
for (int i = 0; I <= číslo; i + +) součet + = i.
A pak budu vracet částku.
Jsem mohl provádět to v mnoha způsoby.
Mohl jsem použil while.
Mohl jsem přeskočil pomocí součtu proměnné, jestli jsem opravdu chtěl,
ale v krátké, jen musíme funkci, že když jsem neměl flákat prohlašuje součet je 0.
Pak se opakuje z 0 na nahoru přes čísla,
a na každé iteraci je dodává, že aktuální hodnotu součtu a vrátí součet.
>> Nyní je tu mírné optimalizace zde.
To je pravděpodobně zbytečná krok, ale budiž. To je v pořádku pro tuto chvíli.
Jsme je alespoň důkladné a bude 0 celou cestu nahoru.
Není příliš tvrdý a velice jednoduché,
ale ukazuje se, že s touto funkcí sigma máme stejnou možnost
jako jsme to udělali tady na jevišti.
Na jevišti jsme právě počítal, kolik lidí bylo vedle mě,
ale pokud bychom chtěli spočítat 3 + 2 + 1
na až do 0 bychom mohli podobně punt na funkci
že budu místo toho popisovat jako rekurzivní.
Zde pojďme se rychle zdravý rozum zkontrolovat a ujistěte se, že jsem to neudělal flákat.
>> Vím, že je tu alespoň jedna věc v tomto programu, které jsem udělal špatně.
Když jsem narazila zadejte budu se dostat jakýkoliv druh na mě ječet?
Co budu se křičel na o?
Jo, zapomněl jsem prototyp, takže jsem pomocí funkce nazývá sigma on-line 15,
ale to není prohlášen až řádku 22, tak jsem možná aktivně jít sem
a prohlásit prototyp, a řeknu int sigma (int number), a to je vše.
Je prováděna na dně.
>> Nebo jiný způsob, jak bych mohl vyřešit tento problém,
Mohl bych funkci přesunout tam, což není špatné,
ale aspoň, když jsou vaše programy začnou se dlouho, upřímně řečeno,
Myslím, že je to nějaké hodnoty vždy s hlavním nahoře
takže ve čtenáři může otevřít soubor a pak okamžitě vidět
co program dělá, aniž by museli hledat přes něj
hledá pro tuto hlavní funkci.
Pojďme dolů do mého okna terminálu zde, zkuste dělat sigma sigma dělat,
a já jsem podělal tady taky.
Implicitní prohlášení o funkce GetInt znamená, že jsem zapomněl na to, co jiného?
[Neslyšitelné-student]
Dobré, tak zřejmě častý omyl, takže pojďme dát této události zde,
cs50.h, a teď se vraťme k mému terminálovém okně.
>> Budu vymazat obrazovku, a já znovu spusťte, aby sigma.
Zdá se, že se sestavují. Dovolte mi, abych nyní spustit sigma.
Budu zadejte číslo 3, a já jsem si 6, takže není přísné kontroly,
ale alespoň se zdá, že funguje na první pohled, ale nyní pojďme to rip sebe,
a pojďme skutečně využívají myšlenku rekurze, znovu,
ve velmi jednoduchém kontextu tak, aby za pár týdnů
když začneme zkoumat milovník datových struktur, než pole
máme další nástroj v toolkitu, se kterým se
manipulovat tyto datové struktury jak uvidíme.
To je iterativní přístup, loop-založený přístup.
>> Dovolte mi, abych místo toho teď udělat.
Dovolte mi, abych místo toho řekl, že součtem počtů
dolů k 0, je opravdu to samé jako
Číslo + sigma (číslo - 1).
Jinými slovy, stejně jako na stupně I punted se každý z lidí vedle mne,
a podle pořadí držel plavit až jsme konečně svého dna na Willyho,
kdo měl vrátit pevně odpověď jako 0.
Tady jsme podobně plavit na sigma
stejná funkce jako bylo původně volal, ale klíčový vhled zde
je to, že nejsme volat sigma identicky.
Jsme neprochází v n.
Jsme jednoznačně prochází v řadě - 1,
tak o něco menší problém, o něco menší problém.
>> Bohužel, to není tak úplně řešení dosud, a než jsme se opravit
Co by mohlo být skákat tak, jak zřejmé, na některé z vás
nech mě jít napřed a znovu dělat.
Zdá se, že sestavit v pořádku.
Dovolte mi, abych znovu spustit sigma s 6.
Jejda, dovolte mi, abych znovu spusťte sigma s 6.
Viděli jsme to předtím, byť náhodně poslední době také.
Proč jsem si tento tajemnou segmentation fault? Jo.
[Neslyšitelné-student]
Není base-case, a konkrétněji, co se asi stalo?
To je příznakem jaké chování?
Řekni to trochu hlasitěji.
[Neslyšitelné-student]
Je to nekonečná smyčka efektivně, a problém s nekonečnými smyčkami
když zahrnují rekurzi v tomto případě, funkce volat sebe,
co se stane pokaždé, když zavolat funkci?
No, myslím, že zpět k tomu, jak je stanoveno v paměti v počítači.
Řekli jsme, že je to kus paměti tzv. stack, který je na dně,
a pokaždé, když budete volat funkce trochu více paměti dostane dal
na tzv. zásobníku obsahujícího tuto funkci je lokální proměnné nebo parametry,
takže pokud sigma volá sigma sigma volání volání sigma
vyzývá sigma, kde tento příběh skončí?
>> No, to nakonec překročení celková částka
paměti, že máte k dispozici k počítači.
Můžete obsadit segment, který jste měl zůstat uvnitř,
a stáhni segmentation fault, core dumpingové,
a co core dumpingové znamená, že teď máte soubor s názvem core
což je soubor obsahující nul a jedniček
že skutečně v budoucnu bude diagnosticky užitečné.
Pokud to není zřejmé na vás, kde se vaše chyba je
můžete skutečně udělat trochu forenzní analýzy, abych tak řekl,
na tento soubor core dump, která je opět jen celá parta nul a jedniček
které v podstatě představuje stav vašeho programu do paměti
v okamžiku, kdy se zřítil tímto způsobem.
>> Oprava je, že nemůžeme jen tak slepě vrátit sigma,
počet + Sigma poněkud menší problém.
Musíme mít nějaký základní věci tady,
a co by referenční případ, pravděpodobně?
[Neslyšitelné-student]
Dobře, tak dlouho, dokud je číslo kladné bychom se měli skutečně vrátí to,
nebo jinak řečeno, pokud je číslo, řekněme, <= k 0
Víš co, já půjdu napřed a vrátit 0,
podobně jako Willy udělal, a jiný, budu pokračovat
a vrátit to, takže to není, že mnohem kratší
než iterativní verze, které jsme šlehačkou jako první pomocí smyčky for,
ale všimněte si, že je to druh elegance k ní.
Namísto návratu nějaké číslo a provedení všech těchto matematiku
a přidáním věci s lokálními proměnnými
jste místo toho řekl: "Dobře, pokud je to super jednoduchý problém,
jako je číslo <0, dovolte mi, abych se ihned vrátit 0. "
>> Nebudeme se obtěžovat podporu záporná čísla,
takže budu pevný kód hodnotu 0.
Ale jinak, realizovat tuto myšlenku sčítání
všechny z těchto čísel dohromady můžete účinně vzít malý kousek
z problému, stejně jako jsme to udělali tady na jevišti,
pak pramice zbytek problému na další osoby,
, ale v tomto případě, že další osoba sami.
Je to stejně pojmenované funkce.
Jen projít to menší a menší a menší problém pokaždé,
a i když jsme se zcela formalizované věci v kódu zde
To je přesně to, co se děje v týdnu 0 se v telefonním seznamu.
To je přesně to, co se děje v posledních týdnech se Seanem
a s našimi ukázkami vyhledávání čísel.
Trvá to nějaký problém a dělení to znovu a znovu.
>> Jinými slovy, existuje způsob, jak teď překládání
tento reálný svět konstrukt, to vyšší úroveň konstrukt
z rozděl a panuj a dělat něco znovu a znovu
v kódu, takže to je něco, co budeme vidět znovu v průběhu času.
Nyní, stejně jako stranou, pokud jste nový rekurze, měli byste alespoň chápu
proč je to legrační.
Chystám se jít na google.com,
a budu hledat několik tipů a triků na rekurze, zadejte.
Řekněte osoby vedle vás, jestli se nesměje právě teď.
Měli jste na mysli rekurzi?
Měli jste na mysli-ah, tam jdeme.
Dobře, teď to zbytek každého.
Trochu Velikonoční vajíčko vložené někde v Google.
Jak stranou, jeden z článků my jsme dali na hřišti internetových stránkách
pro dnešek je jen tato síť různých algoritmů třídění,
z nichž některé jsme se podívali na minulý týden, ale to, co je hezké o této vizualizace
jak jste se snaží zabalit svou mysl kolem různých věcí souvisejících s algoritmy
víte, že můžete velmi snadno nyní začít s různými typy vstupů.
Vstupy všechny zvrátit, vstupy většinou jsou seřazena, vstupy náhodné a tak dále.
Pokud se pokusíte znovu, rozlišit tyto věci ve vaší mysli
uvědomit, že tato URL na hřišti stránkách na přednášky stránce
vám mohou pomoci důvodem přes některé z nich.
>> Dnes jsme se konečně dostat k řešení tohoto problému z chvíli zpět,
který byl, že tato odkládací funkce prostě nefunguje,
a to, co bylo zásadní problém s touto funkcí swapu,
cílem bylo opět vyměnit hodnotu zde a zde
takové, že se tak stane?
To nebylo ve skutečnosti fungovat. Proč?
Jo.
[Neslyšitelné-student]
Přesně, vysvětlení pro tento bugginess
prostě bylo proto, že když budete volat funkce v C
a ty funkce trvat argumenty, jako a, b zde,
jste kolemjdoucí v kopiích jakoukoli hodnotu jste poskytování této funkci.
Nejste poskytuje původní hodnoty sami,
takže viděl v kontextu buggyc,
buggy3.c, který vypadal trochu něco takového.
>> Připomeňme si, že jsme měli x a y inicializována na 1 a 2, resp.
Pak jsme vytisknout to, co oni byli.
Pak jsem tvrdil, že jsem byl vyměňovat je voláním swap x, y.
Ale problém byl, že odkládání pracoval,
ale pouze v rozsahu swapu fungovat sám.
Jakmile jsme narazili řádek 40 těmto vyměnili hodnoty
byly vyhozeny, a tak nic
v původní funkce byla hlavní vlastně nezměnil,
takže pokud si myslíte, že tehdy, co to vypadá, pokud jde o naší paměti
v případě, že levá strana desky představuje-
a já budu dělat moje nejlepší pro každého vidět, v případě, že levá strana tabule
představuje, řekněme, RAM, a zásobník bude růst na up tímto způsobem,
a zavoláme funkci jako hlavní, a hlavní má 2 lokální proměnné, x a y,
pojďme popsat ty, které jsou x tady, a pojďme popisovat tyto jako y tady,
a pojďme dát v hodnotách 1 a 2, tak tohle je hlavní,
a když hlavní volá swap funkce operačního systému
dává SWAP funkce vlastní pás paměti na zásobníku,
vlastní rám ve frontě, abych tak řekl.
Je také přiděluje 32 bitů pro tyto ints.
Stává se to nazvat, a b, ale to je naprosto nahodilé.
Mohlo by jich povolal, co chce, ale co se stane, když hlavní
vyzývá swap je to bere tuto 1, dá kopii tam, dá kopii tam.
>> K dispozici je 1 další lokální proměnnou v swapu, když volal, co? >> Tmp.
Tmp, tak mi dovolte dát si dalších 32 bitů zde,
a co jsem udělal v této funkci?
Řekl jsem int tmp dostane, tak má 1, tak jsem to udělal, když jsme naposledy hráli v tomto příkladu.
Pak se dostane b, takže b je 2, takže nyní to bude 2,
a nyní b dostane teplota, takže teplota je 1,
tak teď b stává toto.
To je skvělé. Fungovalo to.
Ale pak, jakmile se funkce vrátí
swapu paměti ve skutečnosti zmizí, takže to může být znovu
jinou funkci v budoucnu, a hlavní je samozřejmě zcela beze změny.
Potřebujeme způsob, jak zásadně vyřešení tohoto problému,
a dnes budeme mít konečně způsob, jak toho dosáhnout, kdy
můžeme představit něco jako ukazatel.
Ukazuje se, že můžeme vyřešit tento problém
není předáním kopie x a y
ale tím, že podstoupí v co, myslíš, na odkládací funkci?
Jo, co o adrese?
Jsme opravdu mluvil o adresách v hodně podrobně,
ale pokud to tabule představuje mého paměti počítače
bychom mohli jistě začít číslování bytů v mém RAM
a říci to je byte # 1, to je byte # 2, byte # 3,
byte # 4, byte # ... 2000000000 když mám 2 GB paměti RAM,
takže jsme mohli určitě přijít s nějakým libovolným schématu číslování
pro všechny jednotlivé byty v mé paměti počítače.
>> Co když místo toho, když jsem hovor odkládací
spíše než projít v kopiích x a y
proč bych místo předat adresu x zde,
adresa y tady, v podstatě poštovní adresa
x a y, protože pak swap, když je informován
na adresu v paměti X a Y,
pak swap, pokud jsme cvičili ho trochu,
mohl potenciálně řídit na tuto adresu, abych tak řekl,
x, a změnit číslo tam, pak cesta na adresu y,
změnit číslo tam, i když ne ve skutečnosti získat kopie těchto hodnot sám,
takže i když jsme o tom mluvili jako hlavní paměti
a toto jako bytí swapu paměti silný a nebezpečný část C
je to, že každý funkce může dotknout paměti kdekoli v počítači,
a to je silný v tom, že můžete dělat velmi efektní věci s počítačovými programy v C.
To je nebezpečné, protože můžete také zkazit velmi snadno.
Ve skutečnosti, na jeden z nejčastějších způsobů, jak programy v těchto dnech být využity
Stále je pro programátor neuvědomuje
že on nebo ona je umožnit datové
být napsán v místě v paměti, že nebyl určen.
>> Například, on nebo ona prohlašuje, pole o velikosti 10
ale pak náhodně snaží dát 11 bajtů do této matice v paměti,
a začnete dotýkat částí paměti, které již nejsou platné.
Jen pro kontextové to, někteří z vás vědí, že
software často vás vyzve k zadání sériového čísla nebo registračních klíčů,
Photoshop a Word a programy, jako je tato.
Existují trhliny, jak si někteří z vás vědí, on-line, kde můžete spustit malý program,
a voila, nic víc žádost o pořadové číslo.
Jak je to, že pracuje?
V mnoha případech se tyto věci jednoduše najít v počítačích
textové segmenty v počítači skutečných nul a jedniček
kde je tato funkce, kde je požadováno sériové číslo,
a přepsat prostor, nebo když je program spuštěn
můžete zjistit, kde je klíč skutečně uložen
pomocí něco jako debugger, a můžete bezva software tímto způsobem.
To je však neznamená, že toto je naším cílem pro další dva dny,
ale má velmi reálné následky.
Že jeden se stane zapojit krádeže softwaru,
ale je tu i kompromis celých strojů.
>> Ve skutečnosti, když webové stránky v těchto dnech jsou využívány
a ohrožena a data jsou děravý a hesla jsou ukradené
Tento velmi často souvisí se špatným řízením něčí paměti,
nebo, v případě databází, neschopnost předvídat
kontradiktorní vstup, tak o tom více v příštích týdnech,
ale teď jen plížit náhled druhu škod, které můžete udělat
tím, že zcela pochopit, jak věci fungují pod pokličku.
Pojďme o pochopení, proč je vadný
s nástrojem, který bude stále více a více užitečné
jak naše programy se složitější.
Tak daleko, když jste měli chybu v programu
jak jste odešla o ladění to?
Co vaše techniky byly tak daleko, ať už učil své TF
nebo jen samouk?
[Student] printf.
Printf, takže printf byl pravděpodobně tvůj přítel v tom, že pokud chcete vidět
co se děje uvnitř vašeho programu
stačí dát printf tady, printf tady, printf zde.
Pak jej spustíte, a dostanete spoustu věcí na obrazovce
, které můžete použít, aby pak odvodit, co se vlastně děje špatně ve vašem programu.
>> Printf má tendenci být velmi silná věc,
ale je to velmi manuální proces.
Musíte dát printf tady, printf tady,
a pokud jste to uvnitř smyčky můžete dostat 100 řádků
výstupu, který pak musí prosít přes.
Není to jako velmi uživatelsky příjemný nebo interaktivní mechanismus pro ladění programů,
ale naštěstí existuje alternativy.
Tam je program, například, volal GDB, GNU Debugger,
což je poněkud tajemný v tom, jak jej použít.
Je to trochu složitější, ale upřímně řečeno,
to je jedna z těch věcí, kde, pokud si dát v tomto týdnu a další
další hodina pochopit něco jako GDB
to vám ušetří pravděpodobně i desítky hodin v dlouhodobém horizontu,
tak s tím, dovolte mi, abych vám ukázku, jak ta věc funguje.
>> Jsem v terminálovém okně.
Nech mě jít napřed a zkompilovat tento program, buggy3.
Je to již aktuální.
Dovolte mi, abych jej spustit stejně jako jsme to udělali na chvíli zpět, a opravdu, je rozbito.
Ale proč je to? Možná jsem podělal odkládací funkci.
Možná, že je to a, b. Tak nějak nevím, pohybující se kolem nich správně.
Nech mě jít dál a dělat to.
Spíše než jen spustit buggy3 dovolte mi, abych místo spuštění tohoto programu GDB,
a já řeknu to spustit buggy3,
a budu zahrnovat příkazového řádku argumentu,-TUI,
a dáme to v budoucích problémů při spec připomenout.
A teď tato černá a bílá rozhraní objevilo se, že opět,
je trochu ohromující na první, protože tam je všechno
Informace o záruce tady, ale aspoň je tu něco povědomého.
V horní části okna je můj skutečný kód,
a když jsem procházet sem dovolte mi, abych přejděte až na samotný vrchol mého souboru,
a opravdu, tam je buggy3.c, a všimněte si, v dolní části tohoto okna
Mám GDB řádku.
>> To není stejná jako normálnímu John Harvard řádku.
To je výzva, co se děje, aby mi dovolil řídit GDB.
GDB je debugger.
Debugger je program, který vám umožní projít
provedení vašeho programu řádek po řádku po řádku,
po jak dělat, co chcete s programem,
i volání funkcí, nebo hledáte, je ještě důležitější,
Na různých proměnné hodnoty.
Pojďme dál a udělat to.
Chystám se jít dopředu a zadejte běhu na řádku gdb je,
tak zjistíte v levém dolním rohu na obrazovce jsem napsal běžet,
a já jsem stiskněte klávesu Enter, a co to bylo?
Je to doslova běžel můj program, ale já jsem dělal ne vlastně vidět hodně dál zde
proto, že jsem vlastně řekl ladicí
pozastavit v určitém okamžiku v čase.
Jen zadáním běh spustí program.
Nemám vlastně nic vidět. Nemůžu s ním manipulovat.
>> Namísto toho nechte mě to udělat.
V tomto GDB řádku, dejte mi místo zadejte pauzu, zadejte.
To není to, co jsem chtěl napsat.
Pojďme místo toho napište přestávka hlavní.
Jinými slovy, chci nastavit něco, co nazývá zarážka,
který je příhodně pojmenovaný protože to se zlomí nebo pozastavení
provádění programu na příslušném místě.
Hlavní je název mé funkce.
Všimněte si, že GDB je docela chytrý.
To přišel na to, že hlavní stane, kdo hrubě na řádku 18
z buggy3.c, a pak zjistíte zde vlevo nahoře
b + je hned vedle řádku 18.
To je mi připomněl, že jsem si nastavit zarážku na řádku 18.
Tentokrát, když jsem typ běh, budu běžet můj program
až dokud nenarazí, že zarážku,
takže program bude pauza pro mě na řádku 18.
Jdeme na to, spustit.
Nic Zdá se, že se stalo, ale s výpovědní lhůtou vlevo dole
spuštění programu, buggy3, breakpoint 1 v hlavní na řádku buggy3.c 18.
Co mohu dělat?
>> Všimněte si, můžu začít psát věci, jako je tisk,
není printf, tisk x, a nyní to je divné.
$ 1 je jen zvědavost, jak uvidíme
při každém tisku něco, co jste si nový $ hodnotu.
To je tak, že můžete se vrátit zpět na předchozí hodnoty jen v případě,
ale teď to, co na plátně mi říká, je, že hodnota x v tomto bodě příběhu
je zřejmě 134514032.
Co? Kde se to dokonce pocházet z?
[Neslyšitelné-student]
Opravdu, toto je to, co budeme říkat na odpadky hodnotu, a my jsme nemluvili o tom ještě,
ale z důvodu, že byste jí inicializovat proměnné
je samozřejmě tak, že mají nějakou hodnotu, kterou chcete je mít.
Ale úlovek je připomenout, že můžete deklarovat proměnné
jako jsem to udělal před chvílí v mém sigma například
aniž by se skutečně dává jim hodnotu.
Vzpomeňte si, co jsem udělal tady v sigma.
Prohlásil jsem n, ale jakou cenu jsem dát?
Žádné, protože jsem věděl, že v příštích několika řádků
GetInt se bude starat o problému uvedení hodnoty uvnitř n.
>> Ale v tomto bodě v příběhu řádku 11
a řádek 12 a řádek 13 a řádek 14
během těch několika řádků, co je hodnota n?
V jazyce C si prostě nevím.
Je to obecně nějaký popelářský hodnota, některé zcela náhodné číslo
, který je v podstatě zbyly z některé předchozí funkce
které proběhly, tak váš program běží
Připomínám, že funkce dostane funkce, funkce, funkce.
Všechny tyto snímky si dát na paměti, a pak ty funkce návratu,
a stejně jako jsem navrhl s gumou jejich paměť je nakonec znovu použít.
No, to jen tak se stane, že tato proměnná x v tomto programu
Zdá se, že obsahuje nějaké odpadky hodnotu jako 134514032
z nějakého předchozí funkce, ne ten, který jsem napsal.
Mohlo by to být něco, co přichází účinně s operačním systémem,
některé funkce pod kapotou.
>> Dobře, to je v pořádku, ale pojďme se teď postoupit na další řádek.
Pokud jsem typ "next" na mé GDB řádku a já stiskněte klávesu Enter,
Všimněte si, že zvýraznění se přesune dolů na řádek 19,
ale logické implikace je, že linka 18
Nyní po spuštění, takže když jsem zase psát "print x"
Měl bych teď vidět 1, a opravdu, já.
Opět, $ věci je způsob, jak GDB vám připomene
co historie tisku, že jste udělal.
Teď mě nech jít dál a vytisknout y, a opravdu, y je nějaký blázen hodnota stejně,
ale žádný velký problém, protože v souladu 19 se chystáme přidělit
hodnota 2, tak mi dovolte zadejte "next" znovu.
A teď jsme na printf řádku.
Dovolte mi, abych to tiskové x.
Dovolte mi, abych to tiskovou y. Upřímně řečeno, já začínám trochu unavený z tisku to.
Dovolte mi, abych místo toho napište "displeje X" a "displeje y,"
a teď pokaždé, když jsem zadejte příkaz v budoucnu
Budu připomněl, co je x a y, co je x a y, co je x a y.
>> Mohu také, jako vynětí půdy z produkce, typ "info locals."
Info je speciální příkaz.
Místní znamená, že mi ukazuje lokální proměnné.
Jen v případě, když zapomenu, nebo je to blázen, komplikovaná funkce
že já nebo někdo jiný napsal info obyvatelé vám řekne,
jaké jsou všechny lokální proměnné uvnitř této lokální funkce
které by vás mohly záleží, pokud chcete hrabat kolem.
Nyní, printf se chystá vykonat, tak nechte mě jít dopředu a jen typu "next".
Vzhledem k tomu, že jsme v tomto prostředí jsme ve skutečnosti viděl to
provádět sem, ale všimnete, že to začíná být trochu rozbité zde.
Povšimněme si ale, že to převažující obrazovku tam,
takže to není ideální program zde, ale to je v pořádku, protože jsem si vždycky hrabat kolem
pomocí tisku, když chci.
>> Dovolte mi, abych zadejte další zase, a nyní je tu zajímavá část.
V tomto bodě příběhu y je 2, a x je 1,
jak navrhuje tady, a znovu,
Důvod, proč se automaticky zobrazuje je nyní, protože jsem použil příkaz
Displej x a y displej, takže ve chvíli, kdy píšu další
v Teorie X a Y by se měl stát vyměnil.
Nyní již víme, že to nebude ten případ,
ale uvidíme za chvíli, jak můžeme ponořit hlouběji se zjistit, proč to je pravda.
Další, a bohužel, y je stále 2 a x je stále 1, a mohu potvrdit, jak moc.
Tisk x, y tisku.
Skutečně, žádný odkládání se skutečně stalo, takže pojďme začít to znovu.
Je zřejmé, swap je rozbité.
Pojďme místo toho napište "Spustit".
Dovolte mi říci ano, chci restartovat od začátku, zadejte.
>> Teď jsem zpátky na řádku 18.
Nyní všimnete x a y jsou odpadky hodnoty znovu.
Dále, další, další, další.
Kdybych nudit mohu také jen typ N pro další.
Můžete jej zkrátit na nejkratší možnou posloupnost znaků.
Swap je nyní rozděleny.
Pojďme ponor, takže místo psaní další,
teď budu psát krok tak, že jsem posílení uvnitř této funkce
takže mohu projít, takže jsem narazila krok a pak zadejte.
Všimněte si, že upozorňovat na skoky stanoví nižší v mém programu na řádek 36.
Tak jaké jsou lokální proměnné?
Info locals.
Nic zatím, protože jsme nedostali k této přímce,
tak pojďme dál a říkat "next".
Nyní se zdá, že mají TMP, tisk tmp.
Garbage hodnota, ne? Myslím, že ano.
Jak asi vytisknout, tiskové B, 1 a 2?
V okamžiku, jakmile jsem typ next znovu
tmp bude trvat na hodnotu 1, doufejme,
protože tmp se bude přiřazena hodnota.
>> Nyní pojďme si vytisknout, tiskové b,
ale nyní tisknout tmp, a to je opravdu 1.
Nech mě dělat dál. Nech mě dělat dál.
Dokončil jsem odkládací funkci.
Jsem stále uvnitř ní v řádku 40, tak mi dovolte tisku,
print b, a je mi jedno, co tmp je.
Vypadá to, že swap je správné, pokud jde o záměnu a a b.
Ale když jsem teď psát dál, jsem skočit zpět na řádek 25,
a samozřejmě, pokud zadám do x a y tisku
jsou stále beze změny, takže jsme ani opraven problém.
Ale diagnosticky teď možná s tímto programem GDB
jsme alespoň dostali o krok blíže k pochopení
co se děje špatně, aniž by museli vrhu náš kód tím, že printf tady,
printf zde, printf tady a pak ji spustit znovu a znovu
se snaží přijít na to, co se děje špatně.
>> Chystám se jít dopředu a ukončete z toho úplně s ukončete.
Bude to pak říct, "Quit vlastně je?" Ano.
Teď jsem zpátky v mém běžném řádku, a já jsem udělal pomocí GDB.
Jak stranou, nemusíte používat tento-Tui vlajkou.
Ve skutečnosti, pokud jej vynecháte dostanete v podstatě dolní polovinu obrazovky.
Kdybych zadejte přestávka hlavní a potom spusťte
I stále můžete spustit svůj program, ale co to bude dělat je více textově
Jen mi ukaž aktuální řádek jeden po druhém.
-Tui, textová uživatelské rozhraní,
Jen ukazuje více programu najednou, což je asi trochu koncepčně jednodušší.
Ale opravdu, mohu jen dělat dál, příští, další,
a já jdu vidět jeden řádek najednou, a pokud chci opravdu vidět, co se děje
Můžu psát seznam a uvidíte spoustu sousedních řádků.
>> Tam je video, které jsme požádali, aby se budete dívat na problém sady 3
, ve kterém Nate zahrnuje některé složitosti GDB,
a to je jedna z těch věcí, upřímně, kde někteří non-triviální procento z vás
Nikdy se nedotýkejte GDB, a že bude špatné
protože doslova skončí trávit více času v průběhu tohoto semestru
honí chyby, pak byste, pokud jste vložili do této půlhodině / hod
tento týden a příští učení se dostat pohodlně s GDB.
Printf byl tvůj přítel.
GDB by nyní měla být tvůj přítel.
>> Jakékoliv dotazy týkající se GDB?
A tady je stručný přehled některých z nejmocnějších a užitečné příkazy.
Jo. >> Lze vytisknout řetězec?
Můžete vytisknout řetězec? Absolutně.
Nemusí to být jen celá čísla.
Pokud je proměnná y je řetězec stačí zadat tisk s.
To vám ukáže, co se tento řetězec proměnná je.
[Neslyšitelné-student]
To vám dá adresu a řetězec sám.
To vám ukáže, jak.
A poslední věc, jen proto, že se jedná o dobré vědět taky.
Backtrace a rám, dovolte mi, abych se ponořit do tohoto jednoho minule,
stejný přesný program s GDB.
Nech mě jít napřed a spustit textovou verzi uživatelského rozhraní,
rozbít hlavní.
Nech mě jít napřed a znovu spustit. Tady jsem.
Teď mě nech jít příště, příště, příště, příště, příště, krok, zadejte.
>> A teď, že jsem teď v swapu záměrně, ale já na to: "Sakra, co byla hodnota x?"
Nemůžu x už.
Nemůžu y, protože to není v působnosti.
Jsou to v kontextu, ale žádný problém.
Můžu psát backtrace.
To ukazuje mi všechny funkce, které byly provedeny až do tohoto bodu v čase.
Všimněte si, že jeden na dně, hlavní, seřadí se hlavní
je na spodní straně našem obrázku zde.
Skutečnost, že swap je nad ní vedení s odkládací že nad ním v paměti tu,
a když chci vrátit na hlavní dočasně můžu říct "rám."
Jaké číslo? Hlavní je rám # 1.
Chystám se jít dopředu a říct: "frame 1."
>> Teď jsem zpátky v hlavním, a mohu tisknout x, a mohu vytisknout y,
ale nemohu vytisknout nebo b.
Ale můžu, když řeknu: "Dobře, počkejte. Kde je swap?"
Nech mě jít dál a říct, "frame 0".
Teď jsem tam, kde chci být, a jak stranou,
je tu další příkazy taky, jako když jste opravdu nudit psaní další, další, další, další,
lze obecně říci, věci jako "další 10," a že se bude pohybovat po dalších 10 řádků.
Můžete také napsat "pokračovat", když opravdu vám dost s krokovým přes to.
Pokračovat bude spusťte program bez přerušení, dokud nenarazí další zarážku,
ať už ve smyčce nebo nižší dole ve vašem programu.
>> V tomto případě se pokračuje až do konce, a program ukončen normálně.
To je ozdobný způsob, nižší proces.
Jen váš program ukončen normálně.
Více o které ve videu a ladění zasedání přijít.
To bylo hodně.
Pojďme vzít naši 5-minut přestávku tady, a vrátíme se structs a soubory.
>> Pokud jste se ponořila do tohoto týdne PSet již
budete vědět, že budeme používat v distribučním kódu,
zdrojový kód, který jsme Vám poskytli jako výchozí bod, některé nové techniky.
Zejména, jsme zavedli tento nový klíčové názvem struktura, pro konstrukci,
takže můžeme vytvořit vlastní proměnné druhů.
Zavedli jsme také pojem souboru I / O, souboru vstup a výstup,
a to je tak, že se může uložit stav
svého Scramble palubě do souboru na disku
tak, aby učební chlapi a chápu
co se děje uvnitř vašeho programu, aniž byste museli ručně hrát
desítky her shonu.
Můžeme to udělat víc automatedly.
>> Tato myšlenka struct řeší poměrně přesvědčivé problém.
Předpokládejme, že chceme zavést nějaký program
že nějak udržuje informace o studentech,
a studenti mohou mít, například, ID, název
a dům na místě, jako je Harvard, takže se jedná 3 kusy informací
Chceme udržet kolem, tak mi dovolte pokračovat a začít psát trochu program zde,
patří stdio.h.
Dovolte mi, abych to patří cs50.h.
A pak začít svůj hlavní funkci.
Nebudu obtěžovat s žádnými argumenty příkazového řádku,
a tady chci mít studenta, takže jsem chtěl říct
Student má jméno, tak jsem chtěl říct, "název řetězce."
Pak jsem chtěl říct, student také má ID, takže int id,
a student má dům, tak jsem také chtěl říct "řetězec dům."
Pak jsem si objednat to trochu čistěji takhle.
Dobře, teď mám 3 proměnné, s nimiž se představují studenta, tak "studenta."
>> A teď chci naplnit tyto hodnoty, tak nechte mě jít napřed a řekl něco jako
"Id = 123".
Jméno dostane Davida.
Řekněme, že dům dostane Mather,
a pak budu dělat něco svévolně jako printf ("% s,
jehož ID je% d, žije v% s.
A teď, co chci připojit tady, jednu po druhé?
Jméno, id, dům; return 0.
Dobře, pokud jsem to podělal někde tady
Myslím, že máme docela dobrý program, který ukládá jeden student.
Samozřejmě, že to není tak zajímavé. Co když chci mít 2 studenty?
To není velký problém. Mohu podpořit 2 lidí.
Nech mě jít napřed a zdůraznit to a jít sem dolů,
a mohu říci, "id = 456" pro někoho, jako je Rob, který žije v Kirkland.
>> Dobře, počkejte, ale nemohu volat je totéž,
a vypadá to, že budu muset kopírovat to,
tak mi dovolte říci, že se bude jednat o Davidovi proměnné,
a dovolte mi, abych některé kopie těchto pro Roba.
Zavoláme to Rob, ale to nebude fungovat hned
proto, že jsem-počkat, změňme mě ID1, name1 a house1.
Rob bude 2, 2.
Musím změnit zde, zde, zde, zde, zde, zde.
Počkejte, co Tommy? Pojďme to udělat znovu.
Samozřejmě, pokud si stále myslíte, že je to dobrý způsob, jak dělat to, není to,
takže kopírovat / vložit špatné.
Ale my jsme to vyřešil před týdnem.
>> Co bylo naše řešení, když jsme chtěli mít více instancí stejného datového typu?
[Studenti] pole.
Pole, takže zkusím vyčistit toto nahoru.
Dovolte mi, abych určitý prostor pro sebe v horní části, a dovolte mi, abych místo toho to tady.
Budeme-li si tyto lidi, a místo toho budu říkat "int id,"
a budu podporovat 3 z nás nyní.
Já řeknu "názvy řetězců," a já podporovat 3 z nás,
a pak jsem chtěl říct, "řetězec domy," a budu podporovat 3 z nás.
Nyní zde místo David dostat své vlastní lokální proměnné
můžeme zbavit těch.
Že se cítí dobře, že jsme čištění to až.
Pak mohu říci, David bude [0] a názvy [0]
a domy [0].
A pak Rob můžeme podobně ušetřit na toto téma.
Pojďme dát to sem, takže to bude libovolně bude ids [1].
On to bude jména [1],
a pak konečně domy [1].
>> Stále trochu nudné, a teď musím přijít na to,
takže řekněme "jména [0], id [0], domy [0],
a pojďme pluralize to.
IDS, IDS, IDS.
A opět, dělám to, tak znovu, jsem už uchylovat kopírovat / vložit znovu,
takže šance jsou tam jiné řešení zde.
Já si asi vyčistit to ještě výš, se smyčkou, nebo něco takového,
Takže ve zkratce, je to trochu lepší, ale stále se cítí jako
Já se uchylovat k kopírovat / vložit, ale i to, tvrdím,
není opravdu zásadně správné řešení, protože
co když někdy se rozhodneme víte co?
Bychom měli být uložení e-mailové adresy pro Davida a Rob
a všichni ostatní v tomto programu.
Měli bychom také ukládat telefonní čísla.
Měli bychom také ukládat čísla tísňového kontakt.
Máme všechny tyto kousky dat, které chcete uložit,
tak jak se vám jít o tom, že?
>> Můžete deklarovat další pole v horní části, a pak ručně přidat
e-mailová adresa [0], e-mailová adresa [1]
Davidovi a Rob a tak dále.
Ale je to opravdu jen předpoklad, z něhož tento design
že jsem pomocí čest systém vědět, že
[I] v každé z několika polí
jen tak náhodou odkazovat na stejnou osobu,
takže [0] v IDS je číslo 123,
a budu předpokládat, že jména [0]
je tatáž osoba jméno a domy [0]
je tatáž osoba dům a tak dále pro všechny z různých polí, které jsem vytvářejí.
Povšimněme si ale, že to není zásadní vazba
mezi ty 3 kusy informací, id, jméno a dům,
i když účetní jednotka se snažíme vzoru v tomto programu není pole.
Pole jsou právě tento programový způsob, jak toho dosáhnout.
Co opravdu chceme modelovat v našem programu, je osoba,
podobně jako David, člověk jako Rob uvnitř, které
nebo zapouzdření je jméno a ID a dům.
>> Můžeme nějak vyjádřit tuto myšlenku zapouzdření
kdy člověk má ID, jméno a dům
a ne se uchýlit k opravdu hack, kdy jsme jen
věřím, že konzola něco
odkazuje na stejný lidské entity v každé z těchto různorodých polí?
Můžeme skutečně udělat.
Nech mě jít nad hlavním teď, a dovolte mi, abych vytvořit svůj vlastní datový typ
pro opravdu poprvé.
Využili jsme tuto techniku ​​v Scramble,
ale tady budu pokračovat a vytvořit datový typ,
a víte co, budu to nazývat student nebo osoba,
a budu používat typedef pro definici typu.
Chystám se říct, že je to struktura,
a pak tato struktura bude typu studenta, budeme říkat,
i když je to trochu ze dne teď pro mě.
Řekneme "int id."
Řekneme "název řetězce."
Pak budeme říkat "string dům,"
tak od nynějška do konce těchto pár řádků kódu
Právě jsem učil řinčení, že existuje
datový typ kromě ints, kromě řetězců, kromě zdvojnásobí, kromě plováky.
>> Od této chvíle v časové linii 11, je nyní nový datový typ nazvaný studentů,
a teď mohu prohlásit, studentské proměnnou kdekoliv chci,
tak mi dovolte přejděte sem lidi.
Teď můžu zbavit toho, a můžu jít zpátky dolů k Davidovi tady,
a pro Davida mohu skutečně říct, že David,
můžeme doslova pojmenovat proměnné po sobě,
bude typu studenta.
To by mohlo vypadat trochu divně, ale to není všechno, že různé
od vyhlášení něco jako int nebo řetězec nebo plováku.
To jen tak se stane, být nazýván studenta nyní,
a když chci, aby něco uvnitř této struktury
Nyní mám použít nový kus syntaxe, ale je to docela jednoduché,
david.id = 123, david.name = "David" v hlavním D,
a david.house = "Mather,"
a teď mohu zbavit této věci zde.
Všimněte si, že jsme nyní předělala náš program opravdu mnohem lépe
v tom, že nyní náš program kopíruje reálný svět.
>> Tam je real-svět pojem osoby nebo studenta.
Zde máme nyní verzi C osoby nebo přesněji studenta.
Uvnitř této osoby jsou tyto rozhodující vlastnosti,
ID, název a dům, tak Rob podstatě stává totéž tady dole,
tak studenti rob, a teď rob.id = 456,
rob.name = "Rob."
Skutečnost, že proměnná se nazývá Rob je trochu nesmyslné.
Mohli jsme říkali, že je x nebo y nebo z..
Právě jsme se jmenoval to Rob být sémanticky konzistentní,
ale ve skutečnosti jméno je uvnitř této oblasti sám,
takže teď mám tohle.
To taky není cítit se jako nejlepší design v tom, že jsem pevný kódované David.
Já jsem pevný kódované Roba.
A ještě musím uchýlit k nějaké zkopírujte a vložte pokaždé Chci nové proměnné.
Navíc jsem si zřejmě měl každý z těchto proměnných jméno,
i když bych mnohem raději popisovat tyto proměnné
více druhově jako studenti.
>> Nyní můžeme sloučit myšlenky, které funguje dobře pro nás
a místo toho řekl: "Víš co, dej mi proměnnou s názvem studentů,
a pojďme se to být o velikosti 3, "takže teď můžu upřesnit to dále,
zbavit ručně deklarované David,
a mohu místo toho řekl něco jako studenty [0] zde.
Pak mohu říci, studenty [0] zde,
studenti [0] tady, a tak dále, a můžu jít kolem
a vyčistit, aby se pro Roba.
Mohl bych také jít o nyní možná přidáním smyčky
a pomocí GetString a GetInt skutečně dostat tyto hodnoty od uživatele.
Mohl bych jít o přidání konstanta, protože to je obecně špatná praxe
na pevný kód některé libovolné číslo jako 3 tady
a pak už jen na paměti, že byste měli dát více než 3 studentů v něm.
Bylo by asi bylo lepší použít # define v horní části mého souboru
a faktor, který se, tak opravdu, nechte mě jít napřed a zevšeobecnit toto.
>> Dovolte mi, abych otevřít příklad, který je mezi dnešní
Příklady předem, structs1.
To je více kompletní program, který používá # define sem
a říká, že budeme mít 3 studentů ve výchozím nastavení.
Tady jsem se prohlašuje, že třídní cenu studentů,
takže učebna studentů, a teď jsem s použitím smyčky
jen proto, aby kód trochu víc elegantní, naplnit třídu
s vstup uživatele, tak iterovat od i = 0 až na studenty, což je 3.
A pak jsem vyzve uživatele v této verzi
Co je na studenta ID, a já si to s GetInt.
Co je na jméno studenta, a pak jsem si to s GetString.
Co je na studenta dům? Chápu to s GetString.
A pak v dolní zde jsem se rozhodl změnit
jak jsem tisk těchto, a skutečně používat smyčky,
A kdo jsem já tisk?
Podle komentáři jsem tisk nikoho v Mather,
a je to tak Roba a Tommym a tak dále, vlastně Tommy je v Mather.
Tommy a David by být vytištěny v tomto případě, ale jak je to pracuje?
Neviděli jsme tuto funkci dříve, ale hádat o tom, co to dělá.
Porovná řetězce.
>> Je to trochu jiné než zřejmé, jak se srovnává řetězce, protože se ukazuje,
pokud se vrátí 0 to znamená, že řetězce jsou shodné.
Pokud se vrátí -1 to znamená, že někdo přijde abecedně dříve než ten druhý,
a je-li to vrátí 1 to znamená, že další slovo přijde abecedně
dříve než ten druhý, a můžete se podívat na internetu nebo v manuálové stránky
přesně zjistit, jakým způsobem je který, ale tohle všechno je teď dělá, je to říká
v případě, že [i]. dům se rovná "Mather"
pak jít dopředu a vytisknout tak, a tak je v Mather.
Ale tady je to něco, co jsme ještě neviděli, a vrátíme k tomu.
Nevzpomínám si, že by bylo nutné provést v některé z mých programů.
Zdarma je zřejmě odkazuje na paměti, uvolnění paměti,
ale co paměti jsem zřejmě uvolní v této smyčky ve spodní části tohoto programu?
Vypadá to, že jsem uvolnění jméno osoby
a osoba je dům, ale proč je to?
>> Ukázalo se, že ve všech těchto týdnů, které jste dosud používali GetString
jsme trochu bylo zavedení chybu v každém z vašich programů.
GetString pamětí návrhu přiděluje tak, aby se mohli vrátit k vám řetězce,
jako David, nebo Rob, a pak můžete dělat, co chcete,
s tímto řetězcem ve vašem programu, protože jsme vyhrazena paměť pro vás.
Problém je tentokrát pokaždé volat GetString
my, autoři GetString, se ptá, operační systém
aby nám trochu RAM pro tohoto řetězce.
Dejte nám trochu RAM pro tuto další řetězce.
Dejte nám trochu více paměti RAM pro tuto další řetězce.
Co jste, programátor, nikdy dělal
dává nám, že paměť zpátky,
takže pro těch několik týdnů všechny programy, které jste napsali
měli, co se nazývá paměťový skok, kterým se nadále používat
více a více paměti pokaždé, když budete volat GetString, a to je v pořádku.
Záměrně jsme se tomu, že v prvních týdnech, protože to není tak zajímavé
mít na starosti o tom, kde řetězec pochází.
Vše, co chci, je slovo, Rob se vrátil když uživatel zadá ji dovnitř
>> Ale kupředu nyní musíme začít se více důmyslný o tom.
Kdykoliv se alokovat paměť můžeme lépe nakonec předat jej zpět.
Jinak v reálném světě na vašem počítači Mac nebo PC můžete mít občas zkušené
příznaky, kde je počítač broušení k zastavení nakonec
nebo hloupý točící plážový míč právě okupuje počítač je
Celá pozornost a nemůžete dělat věci.
To lze vysvětlit tím, libovolný počet chyb, ale mezi ty případné chyby
jsou věci, tzv. úniky paměti, kdy někdo, kdo psal ten kus softwaru
Používáte nepamatoval na volné paměti
že on nebo ona požádala operační systém pro,
nepoužíváte GetString, protože to CS50 věc, ale pomocí podobné funkce
že požádat operační systém pro paměti.
Pokud vy nebo oni šroub a nikdy skutečně vrátí, že paměť
příznak, který může být, že program, zpomaluje a zpomaluje a zpomaluje
pokud si vzpomenete, volat zdarma.
>> Vrátíme se, kdy a proč byste volat zdarma,
ale pojďme toho jen dobré opatření a pokuste se spustit tento konkrétní program.
Toto bylo nazýváno structs1, zadejte.
Nech mě jít napřed a spustit structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, a vidíme Davida v Mather, Tommy je v Mather.
To je jen malý rozum zkontrolujte, zda program pracuje.
Nyní, bohužel, tento program je trochu frustrující v tom, že
Já jsem všechno, co práce, jsem napsal v 9 různých řetězců, stiskněte klávesu Enter,
Bylo mi řečeno, kdo byl v Mather, ale samozřejmě jsem věděl, kdo byl v Mather už proto, že jsem ji zadali.
Bylo by hezké, kdyby alespoň tento program je více jako databáze
a vlastně si pamatuje, co jsem napsal v
takže jsem nikdy muset zadávat tyto záznamy o studentech.
Možná je to jako registrarial systému.
>> Můžeme to udělat pomocí této techniky známé jako soubor I / O, sp vstup a výstup,
velmi obecný způsob, jak říct, kdykoliv budete chtít číst nebo zapisovat soubory
můžete to udělat s určitou sadu funkcí.
Nech mě jít napřed a otevřete tento příklad structs2.c,
která je téměř totožná, ale uvidíme, co to teď dělá.
V horní části souboru Prohlašuji třídu studentů.
Pak jsem naplnit třídy s vstup uživatele,
takže ty řádky kódu jsou přesně jako předtím.
Pak když jsem nalistujte tady vytisknout každý, kdo je v Mather libovolně jako předtím,
ale to je zajímavá nová funkce.
Tyto řádky kódu jsou nové, a oni představí tu něco,
SOUBOR, všechna velká písmena, a to má * tady stejně.
Dovolte mi přejít to tady, a * tady také.
>> Tato funkce jsme neviděli, fopen,
ale to znamená soubor otevřený, takže se pojďme prolistovat nich,
a to je něco, co se vrátíme v příštích psets,
ale tato linka zde v podstatě otevře soubor s názvem databáze,
a to konkrétně otevře jej v takovým způsobem, že to může dělat to, co k ní?
[Neslyšitelné-student]
Dobře, tak "w" prostě znamená, že to říká operační systém
otevření tohoto souboru takovým způsobem, že nemohu zapisovat.
Nechci si ho přečíst. Nechci, aby na něj jen podívají.
Chci to změnit a přidat věci potenciálně k němu,
a soubor se bude nazýván databáze.
To by mohlo být nazýván nic.
To by mohlo být database.txt. To by mohlo být. Db.
To by mohlo být slovo jako foo, ale já jsem svévolně zvolila název souboru databáze.
To je trochu rozumu kontrola, zda se vrátíme v velmi podrobně v průběhu času,
pokud fp, pro tento soubor ukazatel, není stejný NULL to znamená, že je vše v pořádku.
>> Dlouhý příběh krátký, funkce jako fopen někdy nedaří.
Možná soubor neexistuje. Možná jste z disku.
Možná nemáte oprávnění k této složce,
takže pokud fopen vrátí null něco špatného stalo.
Naopak, pokud fopen nevrátí null vše je v pořádku
a můžu začít psát do tohoto souboru.
Zde je nový trik.
To je pro smyčky, který je iterace nad každým z mých studentů,
a to vypadá tak podobné tomu, co jsme dělali předtím,
ale tato funkce je bratranec printf vyzvala fprintf pro soubor printf,
a všimněte si, že je to jiný pouze ve 2 způsoby.
Jeden, začíná f místo p,
ale pak jeho první argument je zřejmě to, co?
[Studenti] souboru. >> Je to soubor.
To, čemu se říká fp, které budeme nakonec šprýmaři odděleně, co soubor je ukazatel,
ale teď fp představuje pouze soubor, který jsem otevřel,
tak fprintf zde říká vytisknout tento návod ID do souboru, ne na obrazovce.
Vytiskněte jméno uživatele do souboru, ne na obrazovce,
dům do souboru, ne na obrazovce, a pak tady dole, samozřejmě,
zavřete soubor, a pak sem bez paměti.
>> Jediný rozdíl mezi touto verzí 2 a verze 1
je zavedení funkce fopen, a to soubor s příponou *
a tento pojem fprintf, takže se pojďme podívat, co konečný výsledek je.
Nech mě jít do mého terminálovém okně.
Dovolte mi, abych běžet structs2, zadejte.
Vypadá to, že je vše v pořádku. Pojďme spusťte structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, zadejte.
Vypadá to, že se choval stejně, ale když jsem teď dělat ls
upozornění, co soubor, je tady mezi všemi mém kódu, databáze,
takže se pojďme otevřít, gedit databáze, a podívej se na to.
Není to sexy formátů souborů.
Je to opravdu jeden kus datové linky na linku na řádek,
ale ti z vás, kteří používají aplikace Excel nebo CSV souborů, oddělených čárkou hodnoty,
Mohl jsem samozřejmě použil fprintf místo toho možná udělat něco takového
takže jsem mohl skutečně vytvořit ekvivalent souboru aplikace Excel
oddělením věci s čárkami, ne jen nové linky.
>> V tomto případě, pokud bych měl místo toho používat čárky místo nových linek
Mohl bych doslova otevřít tento soubor databáze v aplikaci Excel, pokud jsem místo, aby to vypadalo takhle.
Stručně řečeno, teď, že máme sílu psát k souborům
nyní můžeme začít přetrvávající údaje, držet to asi na disk
takže můžeme uchovávat informace kolem znovu a znovu.
Všimněte si pár dalších věcí, které jsou v současné době trochu známější.
V horní části tohoto souboru C máme typedef
protože jsme chtěli vytvořit datový typ, který představuje slovo,
tak tento typ se nazývá slovo, a uvnitř této struktury
je to trochu obsáhlejší teď.
Proč je slovo skládající se z zdánlivě pole?
Co je slovo jen intuitivně?
>> Je to pole znaků.
Je to posloupnost znaků, zády k sobě k sobě.
DOPISY ve všech uzávěrů se stane, že jsme svévolně říci, maximální délka
jakékoliv slovo ve slovníku, že jsme pomocí pro Scramble.
Proč mám 1?
Null znak.
Připomeňme, když jsme si příklad Bananagrams jsme potřebovali zvláštní hodnotu
na konci slova, aby se sledovat
, kde slova skutečně skončil, a jak problém set specifikace říká
zde jsme spojovali s dané slovo logickou hodnotu,
vlajka, abych tak řekl, true nebo false.
Našli jste toto slovo už proto, že si uvědomujeme,
Opravdu potřebujeme způsob, jak si pamatovat nejen to, co slovo je v Scramble
ale zda nebo ne vy, člověk, našli ho
takže pokud zjistíte, že slovo "jen", můžete nejen zadejte, zadejte, že, zadejte, že, zadejte
a získat 3 body, 3 body, 3 body, 3 body.
Chceme být schopni na blacklist, že slovo nastavením bool
na hodnotu true, pokud jste již našel, a tak to je důvod, proč jsme
zapouzdřeny to v této struktuře.
>> Teď, tady v Scramble tam je to jiné struct říká slovník.
Nepřítomnost zde je slovo typedef, protože v tomto případě
jsme potřebovali k zapouzdření myšlenku slovníku,
a slovník obsahuje spoustu slov,
jak vyplývá z tohoto pole, a kolik z těchto slov jsou tam?
No, ať je tato proměnná nazývá velikost říká.
Ale my to prostě potřebujeme jeden slovník.
Nepotřebujeme datový typ zvaný slovník.
Potřebujeme jen jeden z nich, tak to dopadá v C
že pokud nechcete říct typedef, stačí říct struct, pak uvnitř složených závorek
můžete dát své proměnné, pak dal jméno.
Toto je prohlašuje jeden variabilní s názvem slovník
, která vypadá takto.
Naopak, tyto řádky jsou vytváření opakovaně použitelných datovou strukturu nazvanou slovo
že můžete vytvořit více kopií, stejně jako jsme vytvořili
více kopií studentů.
>> Co to v konečném důsledku nám umožňují dělat?
Nech mě jít zpátky do, řekněme, jednodušší příklad z jednodušších časů,
a dovolte mi, abych otevřít, řekněme, compare1.c.
Problém je zde po ruce, je skutečně slupkou zpět
vrstva z řetězce a začnete off těchto školení kola
protože se ukázalo, že řetězec celou dobu
je, jak jsme slíbili v týdnu 1 opravdu jen přezdívku,
synonymum od CS50 knihovny po něčem, co vypadá trochu tajemná,
char *, a my jsme viděli tuto hvězdu před.
Viděli jsme to v rámci souborů.
>> Pojďme se nyní, proč jsme se skrýval tento detail nějakou dobu.
Zde je soubor s názvem compare1.c,
a to zřejmě žádá uživatele o 2 řetězce, s a t,
a pak se snaží porovnávat tyto řetězce pro rovnost v souladu 26,
a pokud jsou stejné, že říká: "Zadali jste totéž,"
a pokud to není rovno to říká, "Zadali jste různé věci."
Nech mě jít napřed a spustit tento program.
Nech mě jít do mého zdrojového adresáře, aby se compare1. Je sestaven v pořádku.
Dovolte mi, abych běžet compare1.
Budu přiblížíte, zadejte.
Řekni něco. HELLO.
Řeknu něco znovu. HELLO.
Rozhodně jsem neměl psát různé věci.
>> Zkusím to znovu. BYE BYE.
Rozhodně ne jiný, takže to, co se tady děje?
No, co se opravdu být porovnány v souladu 26?
[Neslyšitelné-student]
Ano, tak to ukazuje, že řetězec, datový typ, je tak trochu lež.
Řetězec je char *, ale to, co je char *?
Char *, jak se říká, je ukazatel,
a ukazatel je skutečně adresa,
částka umístění v paměti, a pokud jste náhodou zadali ve slově, jako HELLO,
stáhnout z minulých diskusí řetězců
to je jako slovo HELLO.
Pamatujte si, že slovo jako Hello může být reprezentována
jako pole znaků, jako je tento
a pak se zvláštním charakterem na konci nazývá nulový znak,
jako \ vyjadřuje,.
Co je vlastně řetězec?
Všimněte si, že toto je více kusy paměti,
a ve skutečnosti, je konec to znám pouze jednou se podíváte do celého řetězce
hledá pro speciální nulový znak.
Ale pokud je to kus paměti z mého počítače paměti,
pojďme libovolně říci, že tento řetězec prostě štěstí,
a to mám umístěn na samém počátku mého počítače RAM.
To je bajt 0, 1, 2, 3, 4, 5, 6 ...
>> Když řeknu, že něco jako GetString a já string s = GetString
co se opravdu se vrátil?
U těchto posledních několika týdnech, je to, co opravdu být uloženy v s
není tento řetězec sama o sobě, ale v tomto případě to, co je uloženo, je
číslo 0, protože to, co GetString vlastně dělá
je není fyzicky vrátí řetězec.
To není vlastně ani dělat koncepční smysl.
Co to udělá, návrat je číslo.
Toto číslo je adresa HELLO v paměti,
a řetězec je pak, když se slupkou zpět tato vrstva, řetězec ve skutečnosti neexistuje.
Je to jen zjednodušení v CS50 knihovně.
>> To je opravdu něco, co nazývá char *.
Char dává smysl, protože to, co je slovo, jako HELLO?
No, to je série znaků, řada znaků.
Char * znamená adresu charakteru,
tak co to znamená vrátit řetězec?
Pěkný, jednoduchý způsob, jak vrátit řetězec
je spíše než se snažit přijít na to, jak jsem se vrátit do 5 nebo 6 různých bajtů
dovolte mi vrátit se na adresu, která byte?
První z nich.
Jinými slovy, dovolte mi, abych vám adresu znaku v paměti.
To je to, co char * představuje, adresa jediného znaku v paměti.
Volat, že proměnné s.
Skladujte v s, že konkrétní adresu, kterou jsem svévolně řekl je 0,
jen aby to jednoduché, ale ve skutečnosti je to obecně větší počet.
>> Počkejte chvilku.
Pokud jste jen, že mi adresu prvního znaku, jak mohu vědět, co je adresa
druhého znaku, třetí, čtvrté a páté?
[Neslyšitelné-student]
Ty pouze vědět, kde na konci řetězce je prostřednictvím tohoto šikovného triku,
takže když použít něco jako printf, co printf doslova bere jako svůj argument,
připomenout, že používáme tento% s zástupný symbol, a potom předat
proměnná, která je ukládání řetězec.
Co jste opravdu absolvování je adresa prvního znaku tohoto řetězce.
Printf pak používá pro vedení nebo smyčky while obdržením této adresy,
Například, 0, tak ať mě k tomu teď,
printf ("% s \ n", s);
Když říkám printf ("% s \ n", s); to, co jsem opravdu poskytuje printf s
je adresa prvního znaku v s, což je v tomto libovolném případě je H.
>> Jak printf vědět, co přesně se má zobrazit na obrazovce?
Osoba, která provádí printf zaveden while nebo pro smyčce
, který říká, to postava rovnat speciální nulový znak?
Pokud ne, vytiskněte ji. A co tahle?
Pokud jej vytisknout, vytiskněte jej, tisknout, vytisknout.
Oh, tohle je zvláštní. Zastavte tisk a vraťte se do uživatele.
A to je doslova všechno, co se děje pod kapotou,
a to je hodně strávit v první den třídy,
ale teď je to opravdu stavebním kamenem pochopení všeho
že se děje na vnitřní straně naší paměti počítače,
a nakonec budeme dráždit Tento aparthotel s malou pomocí
od jednoho z našich přátel na Stanfordu.
>> Profesor Nick Parlante na Stanfordu učinil tento úžasný video sekvence
ze všech druhů různých jazycích, které zavedly
tento malý Claymation charakter Binky.
Hlas jste asi slyšet jen na několik sekund propašovat náhled
je to, že z Stanford profesor, a dostaneš
pouze 5 nebo 6 sekund tohoto práva nyní,
ale je to poznámka, na kterém se budeme uzavírat dnes
a začít ve středu.
Dám vám ukazatel zábava s Binkym, preview.
[♪ Music ♪] [Profesor Parlante] Ahoj, Binky.
Probuď se. Je čas na ukazatel zábavu.
[Binky] Co je to? Další informace o ukazateli?
Oh, dobrota!
>> Uvidíme se ve středu.
[CS50.TV]