[Powered by Google Translate] [Recenzia] [Quiz 0] 

[Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University] 

[To je CS50.] [CS50.TV] 

Ahoj, všetci. Vitajte na preskúmanie zasadnutí pre Quiz 0, ktorý sa koná túto stredu. Čo budeme robiť dnes večer, som s ďalšími 3 TFS, a spoločne budeme prechádzať preskúmanie toho, čo sme urobili v priebehu tak ďaleko. Nebude to byť 100% vyčerpávajúce, ale mal by vám lepšiu predstavu z toho, čo už máte, to, čo budete ešte potrebovať k štúdiu pred stredou. A neváhajte zdvihnúť ruku s otázky, ako budeme spolu, ale majte na pamäti, že budeme mať aj trochu času na konci roka ak sa dostaneme až s niekoľkými minút náhradných robiť všeobecných otázok, takže majte na pamäti, že, a tak budeme začať od začiatku s týždni 0. 

[Kvíz 0 recenziu!] [Časť 0] [Lexi Ross] Ale skôr ako my, že Poďme hovoriť o logistiky kvízu. 

[Logistics] [Quiz sa uskutoční v stredu 10/10 namiesto prednášky] 

[(Pozri http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf pre podrobnosti)] Je v stredu 10. októbra. 

To je to streda, a ak idete na túto adresu URL tu, ktorý je tiež prístupný z CS50.net-tam odkaz na to, môžete zobraziť informácie o tom, kde ísť na základe Vaše priezvisko alebo školy príslušnosť, ako aj to povie, čo presne ten kvíz bude týkať a typy otázok, ktoré budete dostať. Majte na pamäti, že budete mať tiež možnosť skontrolovať pre kvíz v sekcii, takže vaše TFS mala ísť cez niektoré problémy praxe, a to je ďalšia dobrá šanca vidieť, kde ste ešte potrebovať k štúdiu až na kvíz. Začnime na začiatku s Bytes 'n' kúsky. Nezabudnite bit je len 0 alebo 1, a byte je zbierka 8 týchto bitov. Poďme sa pozrieť na tejto kolekcie bitov tu. Mali by sme byť schopní zistiť, koľko bitov je. Ak budeme počítať, že je to len 8 z nich, osem 0 alebo 1 ks. A pretože tam je 8 bitov, to je 1 byte, a poďme previesť na šestnástkovej. Hexadecimálne je základ 16, a je to celkom jednoduché previesť číslo v binárnej, čo je to, čo to je, aby číslo v hexadecimálnej. Všetko, čo urobiť, je sa pozrieme na skupiny 4, a my ich previesť na zodpovedajúce hexadecimálne číslice. Začneme s pravým väčšina skupiny 4, tak 0011. To sa deje za jednu 1 a jeden 2, tak spoločne, že robí 3. A potom sa poďme pozrieť na ďalší blok 4. 1101. To sa deje za jeden 1, jeden 4, a jeden 8. Spoločne, že to bude 13, čo D. A budeme pamätať, že v šestnástkovej sústave nemáme len tak 0 až 9. Ideme 0 až F, takže po 9, 10, zodpovedá, 11 až B, et cetera, kde F je 15. Tu 13 je D, tak previesť na desatinné všetko, čo robíme je, že sme vlastne Ku každému pozíciu ako sila 2. To je jedna 1, jeden 2, nula 4s, nula 8s, jeden 16, et cetera, a je to trochu ťažké spočítať v hlave, ale keď pôjdeme na ďalšiu snímku môžeme vidieť odpoveď. 

V podstate budeme naproti staré doľava, a my sme vynásobí jednotlivé číslice zodpovedajúcim sila 2. A pamätajte, na hexadecimálne označíme týchto čísel 0x na začiatku takže nepleťte si to s desatinné číslo. Pokračovanie, toto je ASCII tabuľka, a to, čo používame ASCII, je mapovať z postáv do numerických hodnôt. Nezabudnite v PSet kryptografie sme rozsiahle použitie ASCII tabuľky aby bolo možné používať rôzne metódy kryptografie, Caesar a Vigenère kód, previesť rôzne listy v reťazci podľa kľúča daného užívateľom. Poďme sa pozrieť na trochu ASCII matematiky. Pri pohľade na "P" + 1, v charaktere podobe, ktorá by bola Q, a pamätajte, že '5 '≠ 5. A ako presne by sme prevádzať medzi týmito 2 formulára? Vlastne to ani nie je príliš tvrdý. Aby bolo možné získať 5 odpočítame '0 ' pretože tam sú 5 miest medzi '0 'a '5.' Aby išiel na druhú stranu sme práve pridať 0, takže je to niečo ako pravidelné aritmetiky. Len nezabudnite, že keď sa niečo má úvodzovky okolo neho, že je to postava a teda zodpovedá hodnote v tabuľke ASCII. Presun do všeobecnejších tém počítačových vied. Naučili sme sa, čo je algoritmus a ako ich používame programovanie realizovať algoritmy. Niektoré príklady algoritmov sú niečo naozaj jednoduchého, ako kontroly, či je číslo párne alebo nepárne. Za to si, sme mod na číslo 2 a skontrolujte, či výsledok je 0. Ak áno, je to ešte. Ak tomu tak nie je, je to zvláštne. A to je príklad naozaj základné algoritmus. 

Trochu viac sa zúčastňuje jeden je binárne vyhľadávanie, ktoré pôjdeme cez neskôr v prieskumnom pojednávaní. A programovanie je termín používame pre prijatie algoritmus a prevedením na kódovanie počítač môže čítať. 2 príklady programovania je Scratch, čo je to, čo sme robili v týždni 0. Aj keď nemáme vlastne zadajte von kód je spôsob, ktorým sa vykonáva tento algoritmus, ktorý tlačí čísla 1-10, a tu sme to isté v C programovací jazyk. Jedná sa o funkčne ekvivalentný, práve písané v rôznych jazykoch alebo syntaxe. Potom sme sa dozvedeli o booleovských výrazoch, a boolean je hodnota, ktorá je true alebo false, a tu mnohokrát booleovské výrazy dovnútra podmienok, tak ak (x ≤ 5), dobre, sme už nastavili x = 5, takže táto podmienka bude hodnotiť na true. A ak je to pravda, čo je kód pod podmienkou, sa bude hodnotená na počítači, tak, že reťazec sa bude vytlačený na štandardný výstup, a termín stavu odkazuje na to, čo je vo vnútri zátvoriek if. Nezabudnite všetkých operátorov. Pamätajte si, že tieto && a | |, keď sa snažíme kombinovať 2 a viac podmienok, == Nie = kontrolovať, či 2 veci sú si rovné. Pamätajte si, že = je pre priradenie vzhľadom k tomu, == je logický operátor. ≤, ≥ a potom v konečnom znení 2 sú zrejmé. Všeobecné preskúmanie booleovské logiky tu. A booleovské výrazy sú tiež dôležité v slučkách, ktoré pôjdeme preč. Naučili sme sa asi 3 typy slučiek tak ďaleko CS50, for, while, a to pri. A to je dôležité vedieť, že zatiaľ čo pre väčšinu účelov môžeme skutočne použiť akýkoľvek typ slučky všeobecne existujú určité typy účely alebo spoločných vzorov v programovaní, ktoré sa špecificky nazývajú pre jeden z týchto slučiek že aby bolo najúčinnejšie alebo elegantné kód to týmto spôsobom. Poďme čo každý z týchto slučiek má tendenciu byť použité pre najčastejšie. 

V cykle for sme všeobecne už vieme, koľkokrát chceme určiť iteráciou. To je to, čo sme v podmienke. Pre, i = 0, i <10, napríklad. My už vieme, že chceme urobiť niečo 10 krát. Teraz, po slučke while, obvykle nemáme nutne Vieš, koľkokrát chceme slučku spustiť. Ale my vieme nejakú podmienkou, že chceme, aby to byť vždy pravdivé, alebo vždy false. Napríklad, je nastavená pri. Povedzme, že je to boolean premennej. Aj keď to je pravda chceme kód na vyhodnotenie, tak trochu viac rozšíriteľný, trochu všeobecnejšie než pre sláčiky, ale každý pre slučke možno tiež previesť na slučke while. Napokon, to while, ktoré môžu byť najzložitejšie pochopiť hneď, sa často používajú, keď chceme vyhodnotiť kód prvý pred prvým sme skontrolovať stav. Bežným príkladom použitia robiť, keď slučka je, keď sa chcete dostať vstup užívateľa, a viete, že chcete požiadať užívateľa pre vstup aspoň raz, ale v prípade, že nie sú ti dobrú vstup hneď Ak chcete zachovať pýtať sa ich, kým vám dobrú vstup. To je najviac obyčajné použitie sa while, a poďme sa pozrieť na vlastné štruktúry týchto slučiek. Oni typicky vždy majú tendenciu nasledovať tieto vzory. 

Na slučky for vnútri máte 3 zložky: inicializácia, zvyčajne niečo ako int i = 0, kde i je počítadlo, stav, keď chceme povedať, spustiť tento cyklus for tak dlho, ako tento stav stále platí, ako aj <10, a potom konečne, aktualizácie, čo je, ako sme zvýšiť čítač premennú v každom bode slučky. Bežná vec vidieť, že je len i + +, čo znamená zvýšiť aj o 1 zakaždým. Dalo by sa tiež urobiť niečo podobné aj + = 2, čo znamená, pridajte 2 až i zakaždým, keď idete cez slučku. A potom to len sa odkazuje na nejaký kód, ktorý vlastne beží ako súčasť slučky. A pre sláčiky while, tentoraz sme vlastne tu inicializácii mimo slučky, tak napríklad, povedzme, že sa snažíme robiť rovnaký typ slučky, ako som práve opísal. Mali by sme povedať, int i = 0 pred slučka začne. Potom by sme mohli povedať, keď aj <10 to, takže rovnaký blok kódu ako predtým, a tentoraz aktualizácia časť kódu, napríklad, i + +, vlastne ide vnútri slučky. A konečne, pre robiť, zatiaľ čo, to je podobný while, ale musíme mať na pamäti, že kód bude hodnotiť, akonáhle pred podmienka je kontrolovaná, takže je oveľa väčší zmysel keď sa pozriete na to v poradí zhora nadol. V robiť, keď slučka kód hodnotí ešte predtým, než sa pozrieť na while stavu, vzhľadom k tomu, while, skontroluje ako prvý. Vyhlásenie a premenné. Keď chceme vytvoriť novú premennú sme najprv chcieť inicializovať. 

Napríklad, int bar inicializuje premennú bar, ale to nedáva hodnotu, takže to, čo sa nachádza bar má hodnotu teraz? Nevieme. Mohlo by to byť nejaký odpadky hodnota, ktorá bola predtým uložená v pamäti tam, a nechceme použiť túto premennú kým sme vlastne dať hodnotu, tak sme vyhlásiť ju tu. Potom sme inicializovať, aby to bolo 42 nižšie. Teraz, samozrejme, vieme, že sa to dá urobiť na jednom riadku, int bar = 42. Ale len preto, aby sa vymazať niekoľko krokov, ktoré sa dejú, vyhlásenia a inicializácia sa deje oddelene tu. To sa deje v jednom kroku, a budúci, int baz = bar + 1, toto vyhlásenie nižšie, ktoré sa zvýši baz, takže na konci tohto bloku kódu keby sme vytlačiť hodnotu baz by byť 44 pretože sme deklarovať a inicializovať ju na 1> bar, a potom sme zvýšiť ju ešte raz + +. Išli sme cez tento pekný krátko, ale je to dobré mať všeobecnú pochopenie toho, čo tém a udalosti sú. Zameriavame sa predovšetkým to urobil v Scratch, takže si môžete myslieť vlákien as niekoľkými sekvencií kódu beží v rovnakom čase. V skutočnosti, pravdepodobne nebeží súčasne, ale druh abstraktne, môžeme myslieť na to týmto spôsobom. 

V Scratch, napríklad, mali sme viac škriatkov. Môže to byť prevedenie iný kód v rovnakom čase. Jeden by mohol byť pri chôdzi druhý hovorí niečo v inej časti obrazovky. Udalosti sú ďalší spôsob, ako oddelí logiku medzi rôznymi prvkami kódu, a Scratch sme schopní simulovať udalosti pomocou vysielania, a to je vlastne, keď dostanem, nie, keď počujem, ale v podstate je to spôsob, ako odovzdávať informácie z jedného škriatka do druhého. Napríklad, môžete chcieť prenášať hru cez, a keď iný objekt sprite dostane hru cez, reaguje určitým spôsobom. Je to dôležitý model pre pochopenie pre programovanie. Stačí ísť po základnej týždňa 0, čo sme preč cez tak ďaleko, Poďme sa pozrieť na tento jednoduchý C program. Text môže byť trochu malý odtiaľ, ale ja pôjdem cez to naozaj rýchlo. Sme vrátane 2 hlavičkové súbory v hornom, cs50.h a stdio.h. Sme potom definovať konštantné názvom limity na 100. Sme potom robí náš hlavnú funkciu. Vzhľadom k tomu nemáme používať argumenty príkazového riadku tu musíme dať za neplatné ako argumenty pre hlavné. Vidíme int main vyššie. To je návratový typ, a preto vráti 0 na dne. A my sme pomocou CS50 knižnice funkcií získate int požiadať užívateľa pre vstup, a uložíme ju v tejto premennej x, tak prehlasujeme x vyššie, a inicializuje ju x = GetInt. 

Potom sme skontrolovať, či používateľ dal nám dobrý vstup. Ak je to ≥ LIMIT chceme vrátiť kód chyby 1 a vytlačí chybové hlásenie. A konečne, v prípade, že používateľ je nám dobrý vstup budeme na námestí číslo a vytlačí na to, že výsledok. Len aby sa ubezpečil, že ti všetci hit domov môžete vidieť štítky rôznych častí kódu tu. Zmienil som sa konštantná, hlavičkové súbory. Oh, int x. Uistite sa, že si uvedomiť, že je to lokálna premenná. To kontrastuje z globálne premenné, ktoré budeme hovoriť o trochu neskôr v prieskumnom pojednávaní, a my sme volaní knižničný funkcie printf, takže ak sme nezahrnula stdio.h hlavičkový súbor by sme neboli schopní zavolať printf. A ja verím, šípka, ktorá sa dostal odrezal tu ukazuje na% d, ktorý je formátovací reťazec, v printf. To hovorí, že vytlačiť túto premennú ako počet,% d A to je pre týždeň 0. Teraz Lucas sa bude aj naďalej pokračovať. Ahoj, chlapci. Moje meno je Lucas. Som v druháku v najlepšom dome na akademickej pôde, Mather, a budem hovoriť trochu o 1. týždňa a 2,1. [Týždeň 1 a 2,1!] [Lucas Freitas] Ako Lexi hovoril, keď sme začali prekladať váš kód od nuly do C jedna z vecí, ktoré sme si všimli, je, že môžete nielen napísať svoj kód a spustiť ho pomocou zelenú vlajkou už. Vlastne, budete musieť použiť niektoré kroky, aby sa váš C program stať spustiteľný súbor. V podstate to, čo robíte, keď píšete program, je to, že môžete preložiť svoj nápad do jazyka, ktorý kompilátor môže pochopiť, takže keď píšete program v C to, čo robíte je vlastne písať niečo, čo váš kompilátor bude rozumieť, a potom kompilátor bude prekladať tento kód do niečoho, že váš počítač bude rozumieť. 

A vec je, počítač je vlastne veľmi hlúpa. Váš počítač môže chápať iba 0s a 1s, takže vlastne v prvých počítačoch ľudia zvyčajne naprogramovaný pomocou 0s a 1s, ale teraz už nie, vďaka bohu. Nemáme si zapamätať sekvencie 0s a 1s pre cyklus for alebo while cyklu a tak ďalej. To je dôvod, prečo máme kompilátor. Čo kompilátor robí, je to v podstate prevádza C kód, V našom prípade, na jazyk, ktorý váš počítač bude rozumieť, , Ktorá je predmetom kód a kompilátor že používame sa nazýva zvonenie, takže to je vlastne symbol pre kovový zvuk. Ak máte svoj program, čo musíte urobiť, 2 veci. Po prvé, budete musieť kompilovať svoj program, a potom budete na spustenie programu. Ak chcete zostaviť svoj program máte veľa možností, aby tak urobili. Prvá z nich je urobiť rinčať program.c v ktorom programe je názov programu. V tomto prípade môžete vidieť, že hovoríš len "Hej, kompilovať svoj program." Vy nehovoríte "Chcem tento názov pre svoj program" alebo tak niečo. 

Druhou možnosťou je dať meno do svojho programu. Môžete povedať, že klap-o a potom názov, ktorý chcete spustiteľný súbor, ktorý bude vymenovaný ako a potom program.c. A môžete tiež urobiť, aby program, a uvidíte, ako v prvých 2 prípadoch Dal som. C, a v tretej som len programy? Jo, vlastne by nemalo. C. pri použití robiť. V opačnom prípade kompilátor bude skutočne kričať na vás. A tiež, ja neviem, či ste pamätám, ale veľa krát sme tiež použili-lcs50 alebo-lm. To sa nazýva prepojenie. Je to jednoducho hovorí kompilátora, že budete používať tieto knižnice práve tam, takže ak chcete použiť cs50.h máte skutočne písať rinčanie program.c-lcs50. Ak tak neurobíte, že kompilátor nebude vedieť , Že používate tieto funkcie v cs50.h. A keď chcete spustiť program, máte 2 možnosti. Ak ste rinčať program.c nedali ste meno k vášmu programu. Musíte ho spustiť pomocou. / A.out. A.out je štandardný názov, ktorý rinčať dáva svoj program, ak nechcete dať mu meno. Inak budete robiť. / Program, ak dal meno programu, a tiež ak ste urobiť programu názov, ktorý program dostane sa už bude naprogramovať rovnaký názov ako súbor c Potom sme sa rozprávali o dátových typoch a dát. 

V podstate dátové typy sú to isté ako malé krabičky, ktoré používajú na uloženie hodnôt, tak dátové typy sú v skutočnosti rovnako ako pokemonov. Prichádzajú vo všetkých veľkostí a typov. Neviem, či to analógia zmysel. Veľkosť dát skutočne záleží na architektúry stroja. Všetky dátové veľkosti, že budem pre zobrazenie tu sú v skutočnosti pre 32-bitové stroje, ktorý je v prípade nášho zariadenia, ale ak ste skutočne kódovanie vášho počítača Mac alebo v systéme Windows tiež Pravdepodobne budete mať 64-bit stroj, tak si pamätajte, že dátovej veľkosti, že budem pre zobrazenie tu sú pre 32-bitové stroje. Prvý z nich, že sme videli, bolo int, čo je celkom jednoduché. Môžete použiť int uložiť celé číslo. Videli sme tiež charakter, char. Ak chcete použiť písmeno alebo malý symbol budete pravdepodobne používať char. Char má 1 byte, čo znamená 8 bitov, ako Lexi povedal. V podstate máme ASCII tabuľky, ktorý má 256 Možné kombinácie 0s a 1s, a potom, keď zadáte znak, že to bude prekladať znak, ktorý vstupy ste číslo, ktoré máte v ASCII tabuľke, ako Lexi povedal. Máme aj plavák, ktorý používame na ukladanie čísla v desiatkovej sústave. Ak si chcete vybrať 3,14, napríklad, budete používať float alebo dvojité, ktorý má väčšiu presnosť. Float má 4 byty. Double má 8 bajtov, takže jediný rozdiel je presnosť. Máme tiež dlhé, že sa používa pre celé čísla, a je vidieť na 32-bitové stroje int a dlhý majú rovnakú veľkosť, tak to nemá moc zmysel používať dlho v 32-bitovej stroje. 

Ale ak používate Mac a 64-bit stroj, v skutočnosti dlhá má veľkosť 8, tak, že záleží na architektúre. Pre 32-bit stroje nemá zmysel používať dlhé naozaj. A potom dlho dlho, na druhej strane, má 8 bajtov, tak to je veľmi dobré, ak chcete mať dlhšiu celé číslo. A konečne, máme reťazec, ktorý je v skutočnosti char *, ktorý je ukazovateľ na char. Je to veľmi jednoduché si myslieť, že veľkosť reťazca bude ako Počet znakov, ktoré tam máte, ale v skutočnosti char * sama má veľkosť ukazovateľ na char, ktorý je 4 bajty. Veľkosť char * 4 byty. Nezáleží na tom, či máte malú slovo alebo písmeno alebo tak niečo. Bude to mať 4 byty. Tiež sme sa naučili trochu o obsadenie, takže ako vidíte, ak máte, napríklad, program, ktorý hovorí, že int x = 3 a potom printf ("% d", x / 2) to vy viete, čo to bude tlačiť na obrazovke? 

Niekto? >> [Študenti] 2. 1. >> 1, jo. Ak tak urobíte 3/2 to dostane 1,5, ale pretože sme použili celočíselnú to bude ignorovať desatinnú časť, a budete mať 1. Ak nechcete, aby sa to stalo, čo môžete urobiť, napríklad, je deklarovať plavák y = x. Potom x, ktoré bývali 3 sa teraz bude 3,000 v y. A potom si môžete vytlačiť y / 2. Vlastne, mal by som mať 2. tam. Bude to robiť 3.00/2.00, a budete sa dostať 1,5. A máme tento 0,2 f len požiadať o 2 desatinné jednotiek v desatinnú časť. Ak máte 0,3 f, že to bude mať skutočne 1,500. Ak je to 2 to bude 1,50. Máme aj tento prípad tu. Ak si float x = 3,14 a potom vy printf x budete sa 3,14. A ak si x = int x, čo znamená, že liečiť x ako int a tlačíte X teraz budete mať 3,00. Dává to zmysel? Pretože ste prvý liečbu x ako celé číslo, takže ste ignoroval desatinnú časť, a potom tlačíte x. A konečne, môžete si tiež urobiť to, int x = 65, a potom vyhlásiť char c = x, a potom, ak tlačíte c ste vlastne dostane , Takže v podstate to, čo tu robíš je prekladať celé číslo do charakteru, rovnako ako ASCII tabuľka robí. Hovorili sme tiež o matematických operátorov. Väčšina z nich sú celkom jednoduché, takže +, -, *, /, a tiež sa hovorí o mod, ktorý je zvyšok z delenia 2 čísla. Ak máte 10% 3, napríklad, to znamená rozdeliť 10 do 3, a to, čo je zvyšok? Bude to byť 1, takže je to vlastne veľmi užitočné pre mnoho programov. Pre Vigenère a Caesar Som si istý, že všetci z vás používa mod. O matematických operátorov, buďte veľmi opatrní pri kombinovaní * a /. 

Napríklad, ak si (3/2) * 2, čo sa vám dostane? [Študenti] 2. Jo, 2, pretože 3/2 bude 1,5, ale pretože robíte operácie medzi 2 celé čísla ste vlastne len tak, aby zvážila 1, a potom 1 * 2 bude 2, takže sa veľmi, veľmi opatrní keď robí aritmetiku s celými číslami, pretože sa môžu vyskytnúť, že 2 = 3, v tomto prípade. A tiež byť veľmi opatrní prednosť. Mali by ste zvyčajne používajú zátvorky si byť istí, že viete, čo robíte. Niektoré užitočné skratky, samozrejme, jeden je aj + + alebo i + = 1 alebo pomocou + =. To je to isté, ako robiť i = i + 1. Môžete si tiež urobiť aj - alebo aj - = 1, ktorý je to isté, ako i = i-1, Niečo, čo ste chlapci používajú veľa v cykloch for, najmenej. Tiež, pre *, ak používate * = a ak áno, napríklad, i * = 2 je to isté, ako hovorí i = i * 2, a to isté pre rozdelenie. Ak si aj / = 2 je to to isté, ako i = i / 2. 

Teraz o funkciách. Vy sa dozvedel, že funkcie sú veľmi dobrá stratégia pre uloženie kódu keď ste programovanie, takže ak chcete vykonať rovnakú úlohu v kóde znovu a znovu, pravdepodobne budete chcieť použiť funkciu len tak nemusíte kopírovať a vložiť kód znovu a znovu. Vlastne, hlavné je funkcia, a keď som vám ukázať formát funkcie budete vidieť, že to je celkom zrejmé. Používame tiež funkcie z niektorých knižníc, Napríklad, printf, Getin, ktorá je z knižnice CS50, a ďalšie funkcie, ako je toupper. Všetky tieto funkcie sú skutočne vykonávané v iných knižniciach, a keď dáte tieto postroja súbory na začiatku programu hovoríš, že môžete mi prosím dajte mi kód týchto funkcií takže nemám na ich vykonanie, sám? A môžete tiež napísať svoje vlastné funkcie, takže pri spustení programovanie Uvedomujete si, že knižnice nemajú všetky funkcie, ktoré potrebujete. V poslednom Pset, napríklad, sme písali čerpať, kódovanie, a vyhľadávanie, a je to veľmi, veľmi dôležité, aby sme boli schopní písať funkcie pretože sú užitočné, a my sme ich používať po celú dobu v programovaní, a to ušetrí veľa kódu. Formát funkcia je tento. Máme návratový typ na začiatku. Čo je návratový typ? Je to len, keď je vaša funkcia bude vracať. Ak máte funkciu, napríklad, faktoriál, , Ktorý sa chystá na výpočet faktoriálu celé číslo, Pravdepodobne to bude vrátiť celé číslo tiež. Potom návratový typ bude int. Printf vlastne má návratový typ void pretože nie ste vracať nič. Tie iba tlač veci na obrazovke a ukončenie funkcie potom. Potom máte názov funkcie, ktorá si môžete vybrať. Tie by mali byť trochu rozumný, ako nevyberajte meno ako xyz alebo ako x2f. Snažte sa, aby sa o názov, ktorý dáva zmysel. 

Napríklad, ak je to faktoriál, hovoria faktoriál. Ak je to funkcia, ktorá sa chystá na niečo nakresliť, pomenujte ju čerpať. A potom máme parametre, ktoré sú tiež nazývané argumenty, ktoré sú ako prostriedky, ktoré vaše funkcie potrebuje od kódu na plnenie svojej úlohy. Ak chcete vypočítať faktoriál čísla Pravdepodobne budete musieť mať rad pre výpočet faktoriálu. Jedným z argumentov, ktoré budete mať, je samotné číslo. A potom, že to bude niečo urobiť a vrátiť hodnotu na konci ak je to neplatné funkcie. Poďme sa pozrieť, príklad. Ak chcem napísať funkciu, ktorá spočíta všetky čísla v matici celých čísel, v prvom rade, návratový typ bude int pretože mám rad celých čísel. A potom budem mať názov funkcie, ako sumArray, a potom to bude trvať pole sám, na int nums, a potom dĺžka poľa, takže viem, koľko čísel musím zhrnúť. Potom som si inicializovať premennú s názvom čiastku, napríklad na 0, a zakaždým, keď vidím prvok v poli by som pridať do súčtu, tak som urobil pre sláčiky. Rovnako ako Lexi povedal, ty int i = 0, i <dĺžka a i + +. A pre každý prvok v poli som súčet + = nums [i], a potom som sa vrátil sumu, takže je to veľmi jednoduché, a to ušetrí veľa kódu Ak používate túto funkciu, mnohokrát. Potom sme sa pozreli na podmienkach. Ak máme, inak, a else if. Poďme sa pozrieť, aký je rozdiel medzi týmito. Pozrite sa na tieto 2 kódy. Aký je rozdiel medzi nimi? Prvý z nich, v podstate kódy chcú, aby si ak je číslo +, -, alebo 0. Prvý z nich hovorí, že ak je to> 0, potom je to pozitívne. Ak je to = 0, potom je to 0, a ak je to <0, potom je to negatívne. 

A druhý robí if, else if, else. Rozdiel medzi nimi je, že toto je vlastne bude skontrolujte, či> 0, <0 alebo = 0 trikrát, takže ak máte číslo 2, napríklad, to príde sem a povedať if (x> 0), a bude to, že áno, tak som vytlačiť pozitívne. Ale aj keď viem, že je to> 0 a nebude to na 0 alebo <0 Som stále robiť, je to 0, je to <0, takže som vlastne deje vnútri fondy, ktoré som nemusela pretože už viem, že to nebude spĺňať niektorú z týchto podmienok. Môžem použiť if, else if, else príkaz. Je to v podstate hovorí, že ak x = 0 tlačiť pozitívne. Ak tomu tak nie je, budem aj tento test. Ak to 2 nie je budem robiť to. V podstate, ak som mal x = 2 by si povedal if (x> 0), áno, tak tlačiť. Teraz, keď viem, že je to> 0, a že je spokojný prvé, ak Nie som ani ísť spustiť tento kód. Kód beží rýchlejšie, vlastne, 3 krát rýchlejšie, ak použijete tento. Tiež sme sa dozvedeli o a a alebo. Nebudem sa prejsť, pretože Lexi už hovorili o nich. Je to len o && a | | prevádzkovateľ. 

Jediné, čo poviem, je byť opatrný, keď máte 3 podmienky. Použite zátvorky, pretože je to veľmi mätúce, keď máte podmienku a ďalší jeden alebo iný. Pomocou zátvoriek len pre istotu, že vaše podmienky zmysel pretože v tomto prípade, napríklad, môžu si predstaviť, že to by mohlo byť prvá podmienka, a jeden alebo druhý alebo 2 podmienky spojené v a alebo tretej, takže stačí byť opatrný. A konečne, hovorili sme o prepínačoch. Prepínač je veľmi užitočné, keď máte premennú. Povedzme, že máte premennú ako n , Ktoré môžu byť 0, 1, alebo 2, a na každom z týchto prípadov budete na vykonanie úlohy. Môžete povedať, že prepnúť premennú, a znamená to, že hodnota potom je ako hodnota1 budem robiť to, a potom som sa zlomiť, čo znamená, že nebudem pozerať na niektorý z ostatných prípadoch pretože sme už spokojní, že prípad a potom hodnota2 a tak ďalej, a ja tiež môže mať východiskovej polohy. To znamená, že v prípade, že nespĺňa žiadny z prípadov, ktoré som mal že budem robiť niečo iné, ale to je voliteľné. To je pre mňa. Teraz sa poďme Tommy. Dobre, toto bude týždeň 3-ish. To sú niektoré z tém budeme pokrývať, crypto, rozsah, pole, et cetera. Len slovíčko na crypto. Nebudeme sa kladivom domov. 

Urobili sme to v PSet 2, ale pre kvíz uistite sa, že poznáte rozdiel medzi Caesara a Vigenère kód, ako obe z týchto šifier práce a aké to je na šifrovanie a dešifrovanie textu pomocou týchto 2 šifry. Nezabudnite, Caesarovho šifra jednoducho otočí každý znak rovnakú sumu, Vďaka, že ste mod počtom písmen v abecede. A Vigenère kód, na druhej strane, sa otáča každý znak inú sumu, takže skôr než hovoriť Každá postava otáča od 3 Vigenère bude otáčať každý znak o rôzne sumy v závislosti na určité kľúčové kde každý list na kľúčové slovo predstavuje nejaké iné množstvo otočiť jasný text. Poďme hovoriť o prvú premennú rozsahu. K dispozícii sú 2 rôzne typy premenných. Máme lokálne premenné, a tie sa bude definovať mimo hlavnej alebo mimo akúkoľvek funkciu alebo bloku, a tie budú dostupné kdekoľvek vo vašom programe. Ak máte funkciu a v tejto funkcii, je while Veľký globálne premenná je prístupná všade. Lokálne premenná, na druhej strane, je rozsahom na miesto, kde je definovaná. 

Ak máte funkciu tu napríklad, máme túto funkciu g, a vo vnútri g je premenná tu nazýva y, a to znamená, že sa jedná o lokálne premenná. Aj keď je táto premenná nazýva y a táto premenná sa nazýva Y tieto 2 funkcie nemám potuchy, čo každý iný je lokálne premenné sú. Na druhej strane, a to až tu povedať int x = 5, a to je mimo akejkoľvek funkcie. Je to mimo rámec hlavnej, takže to je globálna premenná. To znamená, že vo vnútri týchto 2 funkcií, keď poviem, x - alebo x + + Ja prístupu k rovnakému x pričom toto y, a to y sú rôzne premenné. To je rozdiel medzi globálne premenné a lokálne premenné. Pokiaľ ide o návrh sa týka, niekedy je to asi lepší nápad aby premenné lokálne, kedykoľvek si možno môžete pretože majú veľa globálnych premenných môže dostať naozaj mätúce. Ak máte veľa funkcií všetkých modifikácií to isté môžete zabudnúť čo keď je táto funkcia náhodou upravuje tento globálny, a táto iná funkcia nevie o tom, a to pekne mätúce, ako si získať viac kódu. Vedenie premenné lokálne, kedykoľvek si možno môžete je jednoducho dobrý dizajn. Matice, pamätajte, že sú jednoducho zoznamy prvkov rovnakého typu. Vnútri CI nemôže mať zoznam ako 1, 2,0, ahoj. My jednoducho nemôžeme urobiť, že. 

Keď deklarujeme pole v C všetky prvky musia byť rovnakého typu. Tu mám rad 3 celých čísel. Tu mám dĺžku poľa, ale ak som len vyhlásením v tejto syntaxi kde som určiť, aká všetky prvky sú nemám technicky potrebovať 3. Kompilátor je dosť šikovný na to, aby zistili, aký veľký by mal byť poľa. Teraz, keď chcem získať alebo nastaviť hodnotu poľa To je syntaxe k tomu, že. To bude skutočne meniť druhý prvok poľa, pretože, pamätajte, Číslovanie začína na 0, nie na 1. Ak chcem čítať túto hodnotu môžem povedať niečo ako int x = array [1]. Alebo keď chcem nastaviť túto hodnotu, ako by som tu, Môžem povedať, array [1] = 4. V tej dobe prístup k prvkom ich index alebo ich polohy, alebo kde sú v poli, a že zápis začína 0. Môžeme tiež polia polí, a to sa nazýva multi-dimenzionální pole. Keď máme multi-dimenzionální pole to znamená, že môžeme mať niečo ako riadkov a stĺpcov, a to je len jeden spôsob, ako vizualizáciu tohto alebo o tom premýšľať. Keď mám multi-dimenzionální pole, ktoré znamená, že začnem potrebovať viac ako 1 index, pretože keď budem mať mriežku Len hovorím, čo riadok ste v nedáva číslo. To je naozaj len nám dá zoznam čísel. Povedzme, že mám toto pole tu. Mám pole s názvom sieť, a ja hovorím, že tieto 2 riadky a 3 stĺpce, a tak to je jeden zo spôsobov, vizualizáciu ju. Keď poviem, že ja sa chcem dostať prvok na [1] [2] to znamená, že preto, že sa jedná o riadky a potom stĺpce Chystám sa skočiť na riadku 1, pretože som povedala 1. 

Potom budem sem prišiel do stĺpca 2, a ak budem získať hodnotu 6. Skontrolujte, zmysel? Multi-dimenzionální pole, pamätajte, sú technicky len polia polí. Môžeme mať matice polí polí. Môžeme pokračovať, ale naozaj jediný spôsob, ako premýšľať o ako je práve toto stanovené a čo sa deje, je predstaviť si to v mriežke, ako je to. Keď sme sa prejsť pole k funkciám, idú správať trochu inak, ako keď sme sa prejsť pravidelné premenné funkcií ako zložením int alebo float. Keď sme sa prejsť v int alebo char alebo niektorý z týchto iných dátových typov práve sme sa pozrieť na, ak funkcia mení hodnota tejto premennej je táto zmena nebude šíriť do volajúci funkciu. S pole, na druhej strane, sa tak stalo. Ak sa prejsť v poli na nejakú funkciu, a že funkcia mení niektoré prvky, keď som sa vrátil do funkcie, ktorá je volaná moje pole je teraz bude líšiť, a slovník pre ktoré je polia sú odovzdané formou odkazu, ako uvidíme neskôr. To sa týka ako ukazovátka práce, kde tieto základné dátové typy, na druhej strane, sú odovzdané hodnotou. 

Môžeme to brať ako vytvorenie kópie niektoré premenné a potom odovzdá v kópii. Nezáleží na tom, čo urobíme s tejto premennej. Volanie funkcie nebude vedomý toho, že došlo k zmene. Polia sú len trochu líši v tomto ohľade. Napríklad, ako sme videli, hlavné je jednoducho funkcie ktoré môžu mať v 2 argumenty. Prvý argument hlavnú funkciu je argc, alebo počet argumentov, a druhý argument sa nazýva ArGV, a tie sú skutočné hodnoty týchto argumentov. Povedzme, že mám program s názvom this.c, a hovorím, aby to, a ja budem bežať do príkazového riadku. Teraz odovzdať niektoré argumenty k môjmu programu volal toto, Mohol by som povedať niečo. / Je to sk 50. To je to, čo si predstavujeme, David robiť každý deň na termináli. Ale teraz je hlavnou funkciou vnútri tohto programu má tieto hodnoty, tak argc je 4. To by mohlo byť trochu mätúce, pretože naozaj sme len prechádzať v je cs 50. To je len 3. Ale pamätajte si, že prvý prvok ArGV alebo prvý argument je názov funkcie sám. Takže to znamená, že máme 4 veci tu, a prvý prvok bude. / toto. A to bude reprezentovaný ako reťazec. Potom Zostávajúce prvky sú tým, čo sme zadali v po názvu programu. Teda rovnako ako stranou, ako sme asi videli v PSet 2, nezabudnite, že reťazec 50 sa ≠ celočíselnú 50. Takže nemôžeme povedať niečo ako, 'int x = ArGV 3. " 

To sa jednoducho nebude dávať zmysel, pretože je to reťazec, a to je celé číslo. Takže ak chcete previesť medzi 2, pamätajte, budeme majú to kúzlo funkciu s názvom atoi. To trvá reťazec a vráti celé číslo reprezentované vnútri tohto reťazca. Tak to je chybička sa ľahko vlúdi na kvíz, si myslel, že to bude automaticky správny typ. Ale proste viem, že to bude vždy reťazca aj keď reťazec obsahuje iba celé číslo alebo znak, alebo plávať. Takže teraz poďme hovoriť o jazdné doby. Keď máme všetky tieto algoritmy, ktoré vedia všetky tieto šialené veci, sa stáva naozaj užitočné si položiť otázku, "Ako dlho trvá?" Zastupujeme že s tzv asymptotickej notácie. Takže to znamená, že - no, povedzme, že sme dať náš algoritmus niektoré naozaj, naozaj, naozaj veľký vstup. Chceme si položiť otázku, "Ako dlho to bude trvať? Koľko krokov bude trvať naše algoritmus bežať v závislosti na veľkosti vstupu? " Takže prvý spôsob, ako môžeme popísať doba chodu je s veľkým O. A toto je náš najhoršie doba dobehu. Takže ak chceme triediť pole, a dávame náš algoritmus poľa to v zostupnom poradí, kedy by malo byť vo vzostupnom poradí, že to bude najhoršie. To je naša horná hranica v maximálnu dobu náš algoritmus bude trvať. Na druhej strane, táto Ω bude popisovať najlepšom prípade chodu. Takže ak dáme už zoradené poľa na triedenie algoritmu, ako dlho bude trvať, než si vybrať to? A to, potom, popisuje dolná hranica na prevádzke. Takže tu sú len niektoré slová, ktoré popisujú niektoré bežné prevádzkovú dobu. Sú vo vzostupnom poradí. Najrýchlejší čas chodu máme sa nazýva konštanta. 

To znamená, že bez ohľadu na to, koľko prvkov dávame naše algoritmus, bez ohľadu na to, aký veľký náš pole je radenie je alebo čo robíme na poli bude vždy rovnaké množstvo času. Takže môžeme vyhlasujete, že len s 1, ktorá je konštantná. Tiež sme sa pozreli na logaritmickom behu. Takže niečo ako binárny vyhľadávania je logaritmická, kde sme skrátili problém polovica zakaždým a potom sa veci len získať vyššiu odtiaľ. A ak ste niekedy písanie O každej faktoriál algoritmu, mali by ste brať do úvahy to ako váš pracovný deň. Keď sme tieto prevádzkovú dobu je dôležité mať na pamäti tieto veci. Takže ak mám algoritmus, ktorý je O (n), a niekto iný je algoritmus O (2n) sú vlastne asymptoticky ekvivalentné. Takže ak by sme si predstaviť, n byť veľké číslo ako Eleventy miliárd: takže keď sme porovnaniu Eleventy miliardy na niečo, ako je Eleventy miliárd + 3, náhle, že 3 nie je naozaj veľký rozdiel už. To je dôvod, prečo budeme začať zvažovať tieto veci za rovnocenné. Takže veci ako tieto konštanty, je tu 2 x tento, alebo pridaním 3, to sú len konštanty, a tie sú v úmysle položiť hore. Takže to je dôvod, prečo všetky 3 z týchto dobách chodu sú rovnaké ako hovoriť, že oni to O (n). Podobne, ak máme 2 ďalší dobu chodu, povedzme O (n ³ + 2n ²), môžeme pridať + N, + 7, a potom máme ďalšiu dobu behu to je len O (n ³). Opäť sa jedná o to isté, pretože ty - to nie sú rovnaké. Jedná sa o rovnaké veci, je mi ľúto. To sú rovnaké, pretože this ³ n sa bude ovládať tento 2n ². 

Čo nie je to isté, je, ak sme bežať časy ako O (n ³) a O (n ²) pretože ³ n je oveľa väčší ako tento ² n Takže ak máme exponentmi, zrazu to začne na tom, ale keď sme len rokovania s faktormi, ako sme my tu, potom to nebude záležať, pretože sa práve chystá odísť. Poďme sa pozrieť na niektoré z algoritmov sme videli doteraz a hovoriť o ich behu. Prvý spôsob, ako sa pozerať na čísla v zozname, ktorý sme videli, bol lineárny hľadanie. A vykonávanie lineárny hľadanie je super jednoduché. Musíme len zoznam, a budeme sa pozerať na každý jednotlivý prvok v zozname kým nenájdeme číslo sme hľadali. To znamená, že v najhoršom prípade, to O (n). A v najhoršom prípade tu môže byť v prípade, že element je posledný prvok, potom pomocou lineárnej hľadanie, musíme sa pozrieť na každý element kým sa na poslednú, aby vedel, že to bolo vlastne v zozname. Nemôžeme len tak vzdal v polovici cesty a povedal: "Je to asi nie je." S lineárne hľadanie sa musíme pozrieť na celú vec. Najlepšie prípadu doba dobehu, na druhej strane, je konštantná pretože v najlepšom prípade element sme hľadali, je len prvý v zozname. Takže to bude trvať nám presne 1 krok, bez ohľadu na to, aký veľký je zoznam ak hľadáme pre prvý prvok zakaždým. 

Takže keď hľadáte, pamätajte, že nevyžaduje, aby náš zoznam byť zoradené. Vzhľadom k tomu, že sme jednoducho bude vyzerať v priebehu každého jednotlivého prvku, a to nezáleží akom poradí tieto prvky sú v Viac inteligentný vyhľadávací algoritmus je niečo ako binárny vyhľadávanie. Pamätajte si, že implementácia binárneho vyhľadávania je, keď budete Pozeraj sa na stredu zozname. A pretože sa pozeráme na stredu, požadujeme, aby tento zoznam je zoradený inak nevieme, kde uprostred je, a musíme sa pozrieť na celý zoznam nájsť, a potom na tom mieste sme len strácaš čas. Takže ak máme zoradený zoznam a nájdeme uprostred, budeme porovnávať stred na prvok, ktorého hľadáme. Ak je to príliš vysoká, potom môžeme zabudnúť na pravú polovicu pretože vieme, že ak naše element je už príliš vysoká a všetko napravo od tohto prvku je dokonca vyššia, potom nepotrebujeme hľadať tam už. Tam, kde na druhej strane, ak náš prvok je príliš nízka, vieme všetko vľavo od tohto prvku je tiež príliš nízka, tak to nemá moc zmysel sa pozrieť tam, a to buď. Týmto spôsobom, s každým krokom a zakaždým sme sa pozrieť na stredu zozname, budeme rezať náš problém v polovici, pretože zrazu vieme celá partia čísel, ktorá nemôže byť ten, ktorého hľadáme. 

V pseudokódu by vyzerať nejako takto, a pretože sme rezanie zoznam v polovici každej dobe, naše najhorších skoky Run Time z lineárne do logaritmické. Takže zrazu máme log-in krokov s cieľom nájsť element v zozname. Najlepšie-case doba dobehu, aj keď je stále konštantná pretože teraz, povedzme, že prvok hľadáme, je vždy presný stred pôvodného zoznamu. Takže môžeme pestovať našu ponuku tak veľký, ako by sme chceli, ale v prípade, že element hľadáme, je v polovici, potom je to len bude nám trvať 1 krok. Takže to je dôvod, prečo sme O (log n) a Ω (1), alebo konštantné. Poďme skutočne spustiť binárny vyhľadávania na tomto zozname. Takže povedzme, že sme hľadali prvku 164. Prvá vec, ktorú sa chystáme urobiť, je nájsť stred tohto zoznamu. To len tak sa stane, že stred bude klesať medzi týmito 2 čísla, tak nech to jednoducho ľubovoľne síce zakaždým, keď stred patrí medzi 2 čísla, povedzme, zaokrúhliť nahor. Potrebujeme len uistiť, že sme to na každom kroku na ceste. Takže budeme zaokrúhľovať, a budeme hovoriť, že 161 je uprostred nášho zoznamu. So 161 <164, a každý prvok vľavo 161 je tiež <164, takže vieme, že to nepomôže nám vôbec začať hľadať tu, pretože prvok sme hľadali nemôže byť tam. Takže to, čo môžeme urobiť, je, že sme sa jednoducho zabudnúť o tom celej ľavej polovice zoznamu, a teraz len zvážila z práva na 161 dopredu. 

Takže znova, je to stred, povedzme, zaokrúhliť nahor. Teraz 175 je príliš veľká. Tak sme viem, že to nepomôže nám hľadajú tu alebo tu, takže môžeme len hodiť to preč, a nakoniec budeme hit 164. Akékoľvek otázky týkajúce sa binárne vyhľadávanie? Poďme ďalej od vyhľadávania cez už triedenom zozname skutočne vezme zoznam čísel v ľubovoľnom poradí a poskytovanie tohto zoznamu vo vzostupnom poradí. Prvý algoritmus sme sa pozerali na hovorilo bubble sort. A to by bolo jednoduchšie z algoritmov, ktoré sme videli. Bubble sort hovorí, že keď nejaké 2 prvky vnútri zozname sú na mieste, čo znamená, že je väčší počet na ľavej strane nižšieho počtu, potom budeme vymeniť je, pretože to znamená, že zoznam bude "Viac zoradená", ako tomu bolo predtým. A my sme len tak pre pokračovanie tohto procesu znovu a znovu a znovu až nakoniec prvky druh bubliny na ich správne umiestnenie a máme zoradený zoznam. 

Beh času to bude O (n ²). Prečo? No, pretože v najhoršom prípade, budeme brať každý prvok, a budeme skončiť porovnaní s každou ďalší prvok v zozname. Ale v tom najlepšom prípade, máme už zoradený zoznam, bublina sort je len tak prejsť raz, poviem "Nie. Neurobil som žiadne swapy, tak som urobil." Takže máme Najlepšia prípadová doba chodu Ω (n). Spustí bublina triedenie v zozname. Alebo prvé, poďme sa pozrieť na niektoré pseudokódu naozaj rýchlo. Chceme, že chceme sledovať, v každej iterácii slučky, mať prehľad o tom, či sme alebo nie sme meniť žiadne prvky. Takže dôvod pre to, že budeme zastaviť, keď sme sa vymenili žiadne prvky. Takže na začiatku nášho cyklu sme sa vymenili nič, tak budeme hovoriť, že je to pravda. Teraz, budeme prechádzať zoznam a porovnajte prvok aj pre element i + 1 a ak je to tak, že je väčší počet na ľavej strane menší počet, potom sme len tak vymeniť je. 

A potom budeme pamätať, že sme vymenili prvok. To znamená, že musíme prejsť zoznam najmenej 1 viac času , Pretože tento stav, v ktorom sa zastavil je, keď je celý zoznam už zoradené, čo znamená, sme nevykonali žiadne swapy. Takže to je dôvod, prečo naše podmienka tu dole je ", zatiaľ čo niektoré prvky boli prehodenie." Takže teraz poďme sa pozrieť na to beží na zozname. Mám zoznam 5,0,1,6,4. Bubble sort je začnú celú cestu vľavo, a to bude k porovnaniu sa aj prvky, takže 0 až i + 1, čo je prvok 1. Bude to povedať, aj 5> 0, ale teraz 5 je naľavo, tak musím vymeniť 5 a 0. Keď som ich swap, zrazu som si to iný zoznam. Teraz 5> 1, takže budeme vymeniť je. 5 nie je> 6, takže nemusíte robiť nič. Ale 6> 4, takže musíme vymeniť. Znovu musíme prejsť celý zoznam nakoniec objaviť že tieto sú mimo prevádzky, vymeníme ich, a na tomto mieste musíme prejsť zoznam 1 viac času aby sa ubezpečil, že všetko, čo je v jeho poradí, a na tomto mieste bubliny radiť dokončenie. Iný algoritmus pre prijatie niektorých prvkov a ich triedenie je výber sort. Myšlienka výbere druhu je, že budeme budovať zoradená časť zoznamu 1 prvok naraz. 

A spôsob, akým budeme k tomu, že je tým, budovanie ľavej segment zoznamu. A v podstate každý - na každom kroku, budeme mať najmenší prvok sme vľavo ktorá nebola zoradená ešte, a budeme ho presunúť do tej zoradené segmentu. To znamená, že musíme neustále nájsť minimálne zmiešaný prvok a potom, že minimálny prvok a vymeniť ju s tým, čo najviac vľavo prvok, ktorý nie je zoradená. Spustiť čas to bude O (n ²), pretože v najhoršom prípade musíme porovnať každý jednotlivý prvok ku každému inému prvku. Vzhľadom k tomu, hovoríme, že ak začneme na ľavej polovici zoznamu, musíme prejsť celú pravú segmente nájsť najmenší prvok. A potom, opäť musíme ísť cez celú pravú časť a ďalej nad tým znovu a znovu a znovu. To bude mať n ². Budeme potrebovať cyklu for vnútri iné pre slučky čo naznačuje, n ². V najlepšom prípade myslenia, povedzme, že ho už zoradený zoznam; sme vlastne nerobíme nič lepšie, ako ² n Vzhľadom k tomu, Výber spôsob má žiadny spôsob, ako zistiť, že minimálny prvok je len jeden A stalo sa pozerá. To ešte potrebuje, aby sa ubezpečil, že je to skutočne minimum. 

A jediný spôsob, ako sa uistiť, že je to minimum, pomocou tohto algoritmu, je pozrieť sa na každý jednotlivý prvok znovu. Takže naozaj, ak mi ju - ak dáte výběrem Triediť už zoradený zoznam, to nebude o nič lepšie, než dávať to zoznam, ktorý nie je zoradená ešte. Mimochodom, ak sa to stane, že je pravda, že niečo je O (niečo) a omega niečoho, môžeme len povedať stručnejšie, že je to θ niečo. Takže ak uvidíte, že prísť kamkoľvek, to je to, čo to znamená len. 

Ak je niečo theta n ², je to tak veľký O (n ²) a Ω (n ²). So najlepšom prípade a najhorší prípad, to neznamená, že rozdiel, algoritmus sa chystá urobiť rovnakú vec zakaždým. Tak toto je to, čo pseudokód pre výber druhu by mohol vyzerať. Sme v podstate povedať, že chcem, aby iterácii zoznam zľava doprava, a na každé opakovanie slučky, budem sa pohybovať Minimálna prvok do tohto triedeného časti zoznamu. A raz som presunúť tam niečo, nikdy som potrebné pozrieť sa na tento prvok znovu. Vzhľadom k tomu, akonáhle som vymeniť prvok do ľavého segmentu zoznamu, je zoradená to pretože robíme všetko vo vzostupnom poradí pomocou minima. Tak sme si povedali, jo, sme na pozícii i, a musíme sa pozrieť na všetky prvky vpravo aj s cieľom nájsť minimálne. Takže to znamená, že chceme pozerať od i + 1 na koniec zoznamu. A teraz, v prípade, že prvok, ktorý sme v súčasnej dobe pri pohľade na menej než naše minimum tak ďaleko, ktoré, pamätajte, začíname minimálne off byť len bez ohľadu na element sme v súčasnej dobe, budem predpokladať, že je to minimum. Ak nájdem prvok, ktorý je menší ako to, že potom budem hovoriť, jo, dobre, som našiel novú minimálnu. Budem si pamätať kde to minimum bolo. 

Takže teraz, potom, čo som prešiel toto právo netriedeného segmentu, Môžem povedať, že som ísť vymeniť minimálne prvok s prvkom, ktorý je v polohe I. To bude vybudovať svoj zoznam, moja zoradená časť zoznamu zľava doprava, a my už nikdy musieť pozrieť na prvok znova, akonáhle je to v tejto časti. Akonáhle sme vymenili ho. Takže poďme bežať výber druhu na tomto zozname. Modrý prvok tu bude aj, a červený prvok bude minimálny prvok. Tak som spustí celú cestu vľavo od zoznamu, tak na 5. Teraz musíme nájsť minimálne zmiešaný prvok. Takže hovoríme 0 <5, takže 0 je môj nový minimum. 

Ale ja sa nemôže zastaviť tam, pretože aj keď sme si uvedomiť, že 0 je najmenší, musíme prejsť každý iný prvok zoznamu, aby sa ubezpečil. Takže 1 je väčší, 6 je väčšie, 4 je väčšia. To znamená, že potom, čo pri pohľade na všetky tieto prvky, som určuje 0 je najmenší. Takže budem prestavenie 5 a 0. Akonáhle som vymeniť to, že budem získať nový zoznam, a ja viem, že som nikdy nebudete musieť pozerať na tejto 0 znova pretože akonáhle som vymenil to, som zoradená, a sme hotoví. Teraz je len tak sa stane, že modrý prvok je opäť 5, a musíme sa pozrieť na 1, 6 a 4 určiť, že 1 je najmenší minimálny prvok, takže budeme vymeniť 1 a 5. Opäť, musíme sa pozrieť na - porovnajte 5 na 6 a 4, a budeme zameniť 4 a 5, a konečne, tieto táto 2 čísla a vymeniť ich, kým sme si naše zoradený zoznam. Akékoľvek otázky týkajúce sa výberu druhu? Dobre. Poďme k poslednému téme tu, a to je rekurzia. 

Rekurzia, pamätajte, je to naozaj meta vec, kde funkcie opakovane volá sám. Takže v určitom okamihu, kým naša fuction je opakovane volá sama, tu musí byť nejaký bod, v ktorom sme sa zastavili volať sami. Pretože ak to neurobíme, potom sme len tak, aby aj naďalej robiť navždy, a náš program sa jednoducho nebude ukončiť. Hovoríme táto podmienka referenčný prípad. A základná vec hovorí, skôr ako volanie funkcie znovu, Ja som jednoducho ísť vrátiť nejakú hodnotu. Takže akonáhle sme vrátili hodnotu, zastavili sme volať sami, a zvyšok výziev sme doteraz vytvorili môžu tiež vracať. Naproti základné veci je rekurzívny prípad. A to je, keď chceme, aby sa ďalšie volanie funkcie, že sme v súčasnej dobe palcov A my asi, aj keď nie vždy, chcete použiť rôzne argumenty. 

Takže ak máme funkciu nazvanú f a f práve volal vziať 1 argument, a my sme ďalej označovať f (1), f (1), f (1), a to len tak sa stane, že argument 1 patrí do rekurzívne prípade, my ešte nikdy nezastaví. Aj keď máme základné prípad, musíme sa uistiť, že nakoniec budeme sa zasiahnuť, že základné veci. Nechceme len držať pobyt v tomto prípade rekurzívne. Všeobecne platí, že keď si hovoríme, že sme pravdepodobne bude mať iný argument, zakaždým. Tu je naozaj jednoduchý rekurzívny funkcie. Takže to bude počítať faktoriál čísla. Hore Hore tu máme základné prípad. V prípade, že n ≤ 1, my nebudeme volať faktoriál znova. Budeme sa zastaviť; sme len tak vrátiť nejakú hodnotu. Ak to nie je pravda, potom budeme hit našej rekurzívne prípad. Všimnite si, že nie sme len volať faktoriál (n), pretože to by nebolo moc užitočné. Budeme volať faktoriál niečo iné. 

A tak môžete vidieť, prípadne či míňame faktoriál (5), alebo tak niečo, budeme volať faktoriál (4), a tak ďalej, a nakoniec budeme hit tohto základného prípadu. Tak to vyzerá dobre. Pozrime sa, čo sa stane, keď v skutočnosti spustiť tento. To je stack, a povedzme, že hlavné bude volať túto funkciu s argumentom (4). Takže akonáhle faktoriál vidí a = 4, bude faktoriál volať seba. Teraz, naraz, máme faktoriál (3). Takže tieto funkcie budú naďalej zvyšovať, až nakoniec sme narazili náš základnú vec. V tomto bode, návratová hodnota je návrat (nx návratová hodnota tohto), návratová hodnota je nx návratová hodnota tohto. Nakoniec musíme zasiahnuť určitý počet. Na vrchole tu, hovoríme návrat 1. To znamená, že akonáhle sa vrátime toto číslo, môžeme pop tohoto zásobníka. Takže táto faktoriál (1) je vykonané. Pri 1 vráti, tento faktoriál (1) priznanie, tento návrat k 1. Návratová hodnota tohto, pamätajte, bol nx vrátená hodnota tohto. Tak náhle, tento chlap vie, že by som sa chcel vrátiť 2. 

Takže si pamätajte, vráti hodnota je len nx návratová hodnota tu. Takže teraz môžeme povedať, 3 x 2, a konečne, tu môžeme povedať, je to len bude 4 x 3 x 2. A akonáhle sa vráti, dostaneme sa na jednotlivé celočíselné vnútri hlavnej. Akékoľvek otázky týkajúce sa rekurzia? Dobrá. Takže tam je viac času na otázky na konci, ale teraz Joseph bude týkať zvyšných tém. 

[Joseph Ong] Dobre. Takže teraz, že sme hovorili o rekurzia, poďme hovoriť trochu o tom, čo zlúčiť druh je. Zlúčiť druh je v podstate iný spôsob radenia zoznamu čísel. A ako to funguje, je, s radiť zlučovacie máte zoznam, a to, čo robíme, je hovoríme, poďme rozdeliť to do 2 polovice. Budeme prvý beh zlúčenie druh znovu na ľavej polovici, potom budeme spúšťať zlúčenie radenia na pravej polovici, a to nám dáva teraz 2 polovice, ktoré sú zoradené, a teraz budeme kombinovať tieto polovice spolu. Je to trochu ťažké vidieť bez príklade, takže budeme prechádzať pohyby a uvidíme, čo sa stane. Takže začnete s týmto zoznamom, rozdelili sme ho do 2 polovice. Prevádzkujeme zlúčenie radenie na ľavej polovici prvej. Tak to je ľavá polovica, a teraz sme sa spustiť je cez tento zoznam znovu ktorá je odovzdaná do druhu korešpondencie, a potom sa pozrieme, znovu, na ľavej strane tohto zoznamu, a organizujeme zlúčenie druh na ňom. Teraz, dostaneme sa do zoznamu čísel 2, a teraz ľavá polovica je len 1 prvok dlho, a my nemôžeme rozdeliť zoznam, ktorý je len 1 prvok do polovice, a tak sme len povedať, až budeme mať 50, ktorý je len 1 prvok, je to už sú zoradené. 

Akonáhle sme hotoví s tým, môžeme vidieť, že môžeme prejsť na pravej polovici tohto zoznamu, a 3 je tiež triedený, a tak teraz, že obe polovice tohto zoznamu sú zoradené môžeme spojiť tieto čísla dohromady. Tak sme sa pozrieť na 50 a 3, 3 je menší ako 50, tak to ide v prvej a potom 50 vypovedaciu Teraz, to, že urobil, sa vrátime do tohto zoznamu a zoradiť je to pravej polovici. 42 je jeho vlastné číslo, takže to už sú zoradené. Teraz teda porovnávať 2 a 3, je menšia ako 42, tak, že sa dostane dať do prvej, teraz 42 dostane dať do, a 50 dostane dať dovnútra Teraz, to je zoradená, ideme celú cestu späť na vrchol, 1337 a 15. No, sa teraz pozrieme na ľavej polovici tohto zoznamu; 1337 je samo o sebe, takže to sú zoradené a to isté s 15. Takže teraz sme sa spojiť tieto 2 čísla zoradiť, že pôvodný zoznam, 15 <1337, tak to ide v prvej, potom 1337 ide dovnútra A teraz sú zoradené obe polovice pôvodného zoznamu až hore. A všetko, čo musíme urobiť, je spojiť tieto. Pozerali sme sa na prvých 2 čísel v tomto zozname, 3 <15, tak to ide do triedenia poľa ako prvý. 15 <42, tak to ide dovnútra Teraz, 42 <1337, že ide dovnútra 50 <1337, tak to ide dovnútra a zistíte, že sme si vzal 2 čísla off tohto zoznamu. Takže sme nielen striedavo medzi 2 zoznamy. Sme len sa pozerá na začiatku, a my sme sa ujali prvok že je menší a potom uvedenie do nášho poľa. Teraz sme sa spojil všetky polovíc a sme hotoví. 

Akékoľvek otázky týkajúce sa korešpondencie druh? Áno? [Študent] Ak je to rozdelenie do rôznych skupín, prečo to jednoducho rozdeliť raz a máte 3 a 2 v skupine? [Zvyšok otázky nezrozumiteľné] Dôvod - takže otázkou je, prečo nemôžeme jednoducho zlúčiť v tom prvom kroku potom, čo sme si ich vziať? Dôvod, prečo by sme to urobiť, spustite na ľavej väčšina prvkov na oboch stranách, a potom ten menší a vložte ho do, je to, že vieme, že tieto Jednotlivé zoznamy sú v zoradené objednávky. Takže ak som pri pohľade na ľavú väčšina prvkov oboch polovíc, Ja viem, že to bude najmenšie prvky týchto zoznamov. Tak som ich dať do najmenších prvkov miestach tejto veľkej zoznamu. Na druhú stranu, keď sa na týchto 2 zoznamov v druhom stupni sa tam, 50, 3, 42, 1337 a 15, sú tie, ktoré nie sú zoradené. Takže keď sa pozriem na 50 a 1337, ja dám 50 do môjho zoznamu ako prvý. Ale to nie je naozaj zmysel, pretože 3 je najmenší prvok zo všetkých z nich. Takže jediný dôvod, prečo môžeme urobiť tento krok, kombinujúci preto, že naše zoznamy sú už zoradené. Čo je dôvod, prečo sme sa pustiť celú cestu až na dno pretože keď máme len jedno číslo, viete, že jedno číslo samo o sebe je už zoradený zoznam. 

Nejaké otázky? Nie? Zložitosť? No, vidíte, že v každom kroku je tu koniec čísla, a môžeme rozdeliť zoznam na polovice protokolu n časy, ktorá je miesto, kde sme stáhni n x n log zložitosť. A uvidíte to najlepšie prípad radiť zlúčenie je n log n, a to len tak náhodou že najhorší prípad, alebo Ω tam je tiež n log n Niečo mať na pamäti. Pohybujúce sa na, poďme na niektoré extra základný súbor I / O. Ak ste sa pozerali na Scramble, všimnete si, mali sme nejaký systém kde by ste mohli napísať do súboru denníka, ak budete čítať pomocou kódu. Pozrime sa, ako by ste mohli urobiť. No, máme fprintf, ktoré si môžete myslieť, ako len printf, ale len tlač do súboru miesto, a preto f na začiatku. Tento druh kódu sa tu, čo to robí, je, ako ste mohli vidieť v Scramble, to ide cez 2-rozmerné pole tlač z riadkoch, čo tie čísla sú. V tomto prípade, printf vypíše na terminál alebo to, čo nazývame štandardné výstupné sekcie. 

A teraz, v tomto prípade, všetko, čo musíte urobiť, je nahradiť printf s fprintf, povedať, že to, čo súbor, ktorý chcete tlačiť, a v tomto prípade to jednoducho vytlačí ju k tomuto súboru miesto tlače to na terminál. No, potom to vyvoláva otázku: Kde sa dostaneme tento druh súboru z, že jo? Sme míňali prihlásiť do tohto fprintf fuction, ale nemali sme potuchy, odkiaľ pochádza. No, čoskoro v kóde, čo sme mali, bola to kus kódu tu, ktorý v podstate hovorí, že open file volá log.txt. Čo robíme po tom je, že sme sa uistiť, že súbor je skutočne úspešne otvorený. Tak to by mohlo zlyhať z mnohých dôvodov, nemáte dostatok miesta na vašom počítači, napríklad. Takže je to vždy dôležité než to urobíte akékoľvek operácie so súborom že sme skontrolovať, či súbor bol úspešne otvorený. Takže to, čo, že, to je argument funkcie fopen, dobre, môžeme otvoriť súbor v mnohých ohľadoch. Čo môžeme urobiť, je, môžeme odovzdať w, čo znamená, že prepísať súbor, ak to vystúpi už, Môžeme odovzdať A, ktorý sa pripojí na koniec súboru namiesto prepísanie to, alebo môžeme určiť r, čo znamená, poďme otvoriť súbor len na čítanie. Takže ak sa program pokúsi vykonať zmeny v súbore, kričí na ne, a nie nechať ich robiť to. Nakoniec, keď sme hotoví s súbor, urobil tým operácie na ňom, musíme sa uistiť, že súbor zatvorte. A tak na konci programu, budete odovzdať znova Tento súbor, ktorý ste otvorili, a len zatvorte ho. Tak toto je niečo dôležité, že budete musieť uistite sa, že. Takže pamätajte si môžete otvoriť súbor, potom môžete napísať do súboru, to operácia v súbore, ale potom budete musieť uzavrieť spis na konci. 

Akékoľvek otázky o populácie vstupné /? Áno? [Študent otázka, nezrozumiteľným] Práve tu. Otázkou je, kde to log.txt súbor sa objaví? No, ak ste práve dať Log.txt, vytvorí v rovnakom adresári ako spustiteľný súbor. Takže ak Si - >> [Student otázka, nezrozumiteľným] Áno. V rovnakej zložke, alebo v rovnakom adresári, ako to nazývate. Teraz pamäť, zásobník, a haldy. Tak, ako je pamäť stanovenými v počítači? No, viete si predstaviť, pamäť ako druh tohto bloku tu. A v pamäti máme to, čo sa nazýva haldy uviazol tam, a zásobník, ktorý je tam dole. A haldy rastie smerom dole a zásobník rastie smerom nahor. Tak ako Tommy uvedené - oh, dobre, a my máme tieto iné 4 segmenty, ktoré dostanem v druhej - Ako Tommy povedal skôr, že viete, ako jeho funkcie sa nazývajú a volať navzájom? Budujú sa tento druh zásobníka rámu. No, ak sú hlavné vyzýva foo, dostane foo kladený na zásobníku. Foo volá bar, bar sa si dať do fronty, a ktorý sa dal na stack po. A ako sa vráti, každý sa dostanú nahý zásobníka. Čo každý z týchto miest a pamäť držať? No, horná, ktorá je text segment, obsahuje vlastný program. Takže strojového kódu, je to tam, akonáhle kompilovať svoj program. Ďalšie, každý inicializácii globálne premenné. 

Takže máte globálne premenné v programe, a vy hovoríte, ako, a = 5, , Ktorý sa dal v tomto segmente, a priamo pod to, Máte nejaké neinicializovaný globálne dáta, ktorá je len INT, ale nehovorte, že je to rovnaké na čokoľvek. Uvedomte si, to sú globálne premenné, takže sú mimo hlavnej. Takže to znamená, žiadne globálne premenné, ktoré sú deklarované, ale nie sú inicializované. Takže to, čo je v halde? Pamäť alokujú pomocou malloc, ktorý sa dostaneme za chvíľu. A konečne, s zásobník máte lokálne premenné a všetky funkcie, ktoré by sa dalo nazvať všetkých svojich parametrov. Posledná vec, nemáte naozaj vedieť, čo premenné prostredie urobiť, ale zakaždým, keď spustíte program, tam je niečo spojené, ako toto je užívateľské meno osoby, ktorá bežal program. A to bude trochu na dne. Pokiaľ ide o adresy pamäte, ktoré sú hexadecimálne hodnoty, hodnoty v hornom začínajú na 0, a oni idú celú cestu až na dno. V tomto prípade, ak ste na 32-bitovom systéme, adresa v dolnej časti bude 0x, nasledovaný AF, pretože to je 32 bitov, ktorá je 8 bytov, a v tomto prípade 8 bytov zodpovedá 8 hexadecimálnych číslic. Tak tu budeš mať, rád, 0xffffff, a tam budeš mať 0. Takže aké sú ukazovatele? Niektorí z vás nemusí vzťahovať to v časti pred. ale my sme sa ísť cez neho v prednáške, takže ukazovateľ je len dátový typ ktoré ukladá, namiesto nejakého druhu hodnoty, ako je 50, uloží adresu na nejaké miesto v pamäti. Ako ten pamäte [nezrozumiteľné]. Takže v tomto prípade, to, čo sme, je, že máme ukazovateľ na celé číslo alebo int *, a obsahuje túto hexadecimálne adresu 0xDEADBEEF. 

Takže to, čo máme, je, teraz sa tento ukazovateľ na nejaké miesto v pamäti, a to je len, hodnota 50 je v tomto mieste pamäti. Na niektorých 32-bitových systémoch, vo všetkých 32-bitových systémov, ukazovatele zaberajú 32 bitov alebo 4 bajty. Ale, napríklad, na 64-bitovom systéme, ukazovatele je 64 bitov. Tak to je niečo, čo budete chcieť mať na pamäti. Tak na koniec-bit systému, ukazovateľ koncové bitov. Ukazovatele sú trochu ťažko stráviteľné bez zbytočných vecí, takže sa poďme prejsť príklad dynamického prideľovania pamäte. Čo dynamické prideľovanie pamäte pre vás robí, alebo to, čo nazývame malloc, To vám umožní prideliť nejaký údajov mimo sady. Takže tieto dáta je niečo trvalejšieho pre celú dobu trvania programu. Vzhľadom k tomu, ako viete, ak ste deklarovať x vnútri funkcie, a že funkcia vracia, už nemáte prístup k dátam, ktorá bola uložená v x. Čo ukazovatele nám urobiť, je, že nám tieto pamäťové alebo obchod hodnôt v inom segmente pamäti, a to haldy. Teraz, keď sa vrátime z funkcie, tak dlho, ako máme ukazovateľ na tomto mieste v pamäti, potom to, čo môžeme urobiť, je, že sme sa len pozrieť na hodnoty tam. Poďme sa pozrieť na príklad: Toto je naša pamäť layout znovu. A my máme túto funkciu, hlavné. Čo to urobí, je - v poriadku, tak jednoduché, že jo? - Int x = 5, to je len premenná na zásobníku v main. 

Na druhú stranu, teraz deklarujeme ukazovateľ, ktorý volá funkciu giveMeThreeInts. A tak teraz pôjdeme do tejto funkcie a vytvoríme nový zásobníka rámec pre neho. Avšak v tomto zásobníku ráme, vyhlasujeme int * teplota, ktoré v celých mallocs 3 pre nás. Takže veľkosť int dá nám, koľko bytov to int je, a malloc nám dáva, že veľa bytov priestoru na halde. Takže v tomto prípade, sme vytvorili dostatočný priestor pre 3 celých čísel, a haldy je spôsob, ako sa tam, čo je dôvod, prečo som vypracovaná to vyššie. Akonáhle sme hotoví, vrátime sa sem, budete potrebovať len 3 ints vrátil, a vráti adresu, v tomto prípade viac ako kedykoľvek že pamäť je. A sme si stanovili ukazovatele = prepínač, a tam máme len ďalší ukazovateľ. Ale čo to vráti funkcia je stohovať tu a zmizne. Takže teplota zmizne, ale stále zachovať adresu, kde tie 3 čísla sú vo vnútri siete. Takže v tejto sade, ukazovateľov sú rozsahom lokálne pre skladanom rámu, ale pamäť, na ktoré sa vzťahujú sa na hromadu. 

Dává to zmysel? [Študent] Mohli by ste to zopakovať? >> [Joseph] Áno. Takže keď som sa vrátiť len trochu, uvidíte, že teplota pridelené niektoré pamäte na halde up there. Takže keď táto funkcia, giveMeThreeInts vráti, to stack tu zmizne. A s ním akékoľvek premenných, v tomto prípade, to ukazovateľ, ktorý bol rozdelený v skladanom ráme. To je zmizne, ale od tej doby sme sa vrátili temp a dali sme sa ukazovateľ = temp, ukazovateľ sa teraz bude ukazovať rovnakú pamäť na umiestnenie ako teplota bola. Takže teraz, aj keď strácame temp, že miestne ukazovatele, sme ešte udržať adresu pamäte, čo to bolo ukázal dovnútra tejto premennej ukazovatele. Otázky? To môže byť trochu mätúce tému, ak ste nešla nad ním v oddiele. Môžeme, bude váš TF určite ísť cez neho, a samozrejme budeme môcť odpovedať na otázky na konci sledovaného relácie za to. Ale to je trochu zložité témy, a mám ďalšie príklady, ktoré sa chystáte ukázať ktoré pomôžu objasniť, čo vlastne sú ukazovatele. 

V tomto prípade, ukazovatele sú ekvivalentné polí, tak som si použite tento ukazovateľ ako rovnakú vec ako int pole. Takže som indexovanie do 0, a zmeniť prvé číslo na 1, zmenou druhý číslo na 2 a 3. celé číslo 3. Takže viac na ukazovateli. No, spomínam Binky. V tomto prípade sme pridelené ukazovateľ, alebo sme deklarovali ukazovateľ, ale spočiatku, keď som vyhlásil ukazovateľ, to nie je poukazuje na kdekoľvek v pamäti. Je to len odpadky hodnoty vnútri nej. Takže nemám potuchy, kde tento ukazovateľ ukazuje. Má adresu, ktorá je len plná 0 a 1, kde bol pôvodne deklarovaný. Nemôžem nič robiť s tým, kým som volať malloc na to a potom mi to dáva málo miesta na halde, kde sa môžem obrátiť hodnoty vnútri. Potom znova, ja neviem, čo je vo vnútri tejto pamäte. Takže prvá vec, ktorú musím urobiť, je skontrolovať, či systém mal dostatok pamäte aby ma späť 1 celé číslo na prvom mieste, čo je dôvod, prečo to robím kontrolu. Ak je ukazovateľ null, to znamená, že nemá dostatok miesta alebo nejakej inej chybe, tak som mal ukončiť z môjho programu.  Ale ak sa to podarí, teraz môžem používať tento ukazovateľ a čo * ukazovateľ robí, je, že idú tam, kde je adresa tam, kde táto hodnota je, a to nastaví sa rovná 1. Tak tu, sme kontrolu, či sa pamäť existuje. 

Akonáhle budete vedieť, že existuje, môžete si dať do neho akú hodnotu chcete dať do nej, v tomto prípade 1. Akonáhle sme hotoví s ním, je potrebné uvoľniť tento ukazovateľ pretože sa musíme dostať späť do systému, ktorý pamäti, že budete požiadaní v prvom rade. Vzhľadom k tomu, že počítač nevie, kedy sme s ním urobil. V tomto prípade sme explicitne hovoriť, áno, my sme urobili s týmto pamäte. Ak nejaká iná proces potrebuje, iný program potrebuje, neváhajte ísť dopredu a vziať ju. Čo môžeme urobiť, je tiež môžeme len získať adresu lokálnych premenných na televízore. Takže int x je vnútri skladaného rámu main. A keď budeme mať túto ampersand, tento a prevádzkovateľ, čo robí, je trvá x, a x je len niektoré údaje v pamäti, ale má adresu. Je umiestnený niekde. Takže volanie a x, čo to robí, je, že nám dáva adresu x. Tým, že robíme ukazovateľ miesto, kde x je v pamäti. Teraz už len urobiť niečo ako * x, budeme si 5 späť. Hviezda sa nazýva dereferencing to. Môžete sledovať adresu a dostanete hodnotu toho tu uložené. 

Nejaké otázky? Áno? [Študent] Ak nechcete robiť 3-špicatý vec, to ešte kompiláciu? Áno. Ak nechcete robiť 3-ukazovateľ vec, je to stále bude zostavovať, ale ja ti ukážem, čo sa deje v druhej, a bez toho, že že to, čo nazývame pretečeniu pamäte. Nedávate systému späť svoju pamäť, takže po chvíli program bude hromadiť pamäti, že to nie je pomocou, a nič iné ju použiť. Ak ste niekedy videli Firefox s 1500000 kb na vašom počítači, v Správcovi úloh, že to, čo sa deje. Máte pretečeniu pamäte v programe, že nie ste manipuláciu. Tak, ako sa ukazovateľ aritmetický práce? No, ukazovateľ aritmetický je niečo ako indexovanie do poľa. V tomto prípade, mám ukazovateľ, a to, čo robím je, že som, aby ukazovateľ bod na prvý prvok tohto poľa 3 celých čísel, ktoré som pridelené. Takže teraz, čo mám robiť, star pointer len zmení prvý prvok v zozname. Hviezda ukazovateľ 1 bodov za tu. Takže ukazovateľ je tu, ukazovateľ 1 je tu, ukazovateľ 2 je tu. 

Takže len pridať 1 je to isté, ako pohybujúce sa tohto poľa. Čo máme urobiť, je, keď robíme ukazovateľ 1 dostanete adresu sem, a za účelom získať hodnotu v tú môžete dať hviezdu z celého výrazu k dereferencia to. Takže, v tomto prípade, som nastavenie prvého umiestnenia v tomto poli na hodnotu 1, druhej umiestnenie na 2, a tretie umiestnenie na 3.. Potom to, čo robím tu je mi tlačí náš ukazovateľ 1, ktorý len mi dáva 2. Teraz som zvyšovanie ukazovateľ, takže ukazovateľ rovná ukazovateľ 1, ktorý sa pohybuje dopredu. A tak teraz, keď som vytlačiť ukazovateľ 1, ukazovateľ +1 je teraz 3, čo v tomto prípade sa vytlačí 3. A aby uvoľnila niečo, ukazovateľ, že dám ju musí smerovať na začiatku poľa, ktoré som sa vrátil z malloc. Takže, v tomto prípade, ak by som mal zavolať 3 tu, by to nebolo správne, , Pretože je to v strede poľa. Musím odpočítať dostať do pôvodného umiestnenia Počiatočná prvé miesto, ako som si uvoľniť ju. Takže, tu je viac zapojiť príklad. V tomto prípade, sme prideľovanie 7 znakov pole znakov. 

A v tomto prípade to, čo robíme, je, že sme looping cez prvú 6 z nich, a my sme nastavením na Z. Takže, pre int i = 0, i> 6, i + +, Takže, ukazovateľ + i sa len nám, v tomto prípade, ukazovateľ, ukazovateľ 1, ukazovateľ +2, ukazovateľ 3, a tak ďalej a tak ďalej v slučke. Čo to urobí, je, že dostane tú adresu, dereferences to, aby si hodnoty, a zmeny, aby hodnota v Z. Potom na konci si pamätám, je reťazec, nie? Všetky reťazce majú skončiť s nulovým ukončovacie znak. Takže, čo robím, je ukazovátko 6 I dal null zakončenie znak a A teraz, čo som v podstate robil tu vykonáva printf pre reťazec, nie? 

Takže, keď to printf teraz, keď je to na konci reťazca? Keď zasiahne null ukončujúce znak. Takže, v tomto prípade, moje pôvodné ukazovateľ ukazuje na začiatku tohto poľa. Aj vytlačiť prvý znak von. Aj presunúť cez jedného. Aj vytlačiť túto postavu von. Aj pohybovať nad. A ja si to tak, kým som sa dostať na koniec. A teraz koniec * ukazovateľ bude dereferencia a dostať sa na null ukončujúci znak späť. A tak môj while beží iba v prípade, že hodnota nie je null ukončovacie znak. Tak, teraz som opustiť z tejto slučky. A tak keď som odpočítať 6 z tohto ukazovateľa, Vrátim sa celú cestu na začiatok. Nezabudnite, robím to preto, že musím ísť na začiatok, aby sa oslobodil ho. 

Takže som vedel, že to veľa. Sú nejaké otázky? Prosím, áno? [Študent otázka nezrozumiteľná] Môžete povedať, že hlasnejšie? Prepáčte. [Študent] Na poslednom snímke tesne predtým, než budete oslobodený ukazovateľ, kde sa skutočne zmene hodnoty ukazovateľa? [Joseph] Tak, tu. >> [Študent] Oh, dobre. [Joseph] Tak, mám ukazovateľ mínus mínus, vpravo, ktorý sa pohybuje na vec späť o jeden, a potom som oslobodiť to, pretože tento ukazovateľ je potrebné zdôrazniť na začiatku poľa. [Študent] Ale to by nebola potrebná, keby ste prestal po tomto riadku. [Joseph] Takže, keď som prestal po tomto, by to bolo považované za únik pamäte, pretože som nebežal zadarmo. [Študent] I [nezrozumiteľné] po prvých troch riadkoch, kde ste mali ukazovateľ 1 [nezrozumiteľné]. [Joseph] Uh-huh. Takže, čo je otázka tam? Prepáčte. Nie, nie. Choď, choď, prosím. [Študent] Takže, nie ste zmenou hodnoty ukazovateľov. Tie by sa musel urobiť ukazovateľ mínus mínus. [Joseph] Áno, presne tak. Takže, keď som si ukazovateľ 1 a ukazovateľ 2, Nerobím ukazovateľ rovná ukazovateľ 1. Takže, ukazovateľ len zostane ukazuje na začiatku poľa. Je to len vtedy, keď robím plus plus, že nastaví hodnotu späť do ukazovatele, že to vlastne pohybuje to spolu. Dobrá. Ďalšie otázky? 

Opäť platí, že ak je to druh ohromujúci, bude to zahrnuté v relácii. Opýtajte sa svojho vyučujúceho, kolegu o tom, a my môžeme odpovedať na otázky na konci. A zvyčajne sa nám nepáči to urobiť mínus vec. To je vyžadujú, aby som sledovanie toho, ako veľmi som posun v poli. Takže, všeobecne, je to len vysvetliť, ako funguje ukazovateľ aritmetické. Ale to, čo zvyčajne radi urobili je, že sme chceli vytvoriť kópiu ukazovatele, a potom budeme používať túto kópiu, keď ideme okolo v reťazci. Takže, v týchto prípadoch použiť kópie vytlačiť celý reťazec, ale nemáme robiť ako ukazovateľ mínus 6 alebo sledovať, ako veľmi sme sa presťahovali v tomto, len preto, že vieme, že náš pôvodný bod je stále poukazoval na začiatok zoznamu a všetko, čo zmenil je to kópia. Takže, všeobecne meniť kópie pôvodného ukazovateľ. Nesnažte sa nejako ako - nerob zmeniť originály. Snažiť sa zmeniť iba kópia originálu. Takže, si všimnete, keď míňame reťazec do printf nemusíte dať hviezdu pred ním, ako sme to urobili so všetkými ostatnými dereferences, že jo? Takže, ak môžete vytlačiť celý reťazec% s očakáva, že je adresa, a v tomto prípade ukazovateľ alebo v tomto prípade ako pole znakov. 

Postavy, char * s, a polia sú to isté. Ukazovateľ je znakov, a pole znakov sú to isté. A tak, všetko, čo musíte urobiť, je odovzdať ukazovateľ. Nemáme odovzdať ako * ukazovateľ alebo niečo podobné. Takže, polia a ukazovatele sú to isté. Keď robíte niečo ako x [y] sem na pole, čo to robí pod kapotou je to hovorí, jo, je to pole znakov, takže je to ukazovateľ. A tak x je to isté, a tak to, čo robí, je, že pridá y na x, ktorý je to isté, ako vpred v pamäti, že veľa. A teraz x + y nám dáva nejaký adresy, a my dereferencia adresu alebo sledovať šípku kde toto miesto v pamäti, je, a dostaneme hodnotu z tohto umiestnenia v pamäti. Takže, takže tieto dva sú presne to isté. Je to len syntaktickú cukor. Oni robia rovnakú vec. Sú to len rôzne syntactics pre seba. 

Takže, čo môže pokaziť s ukazovateľmi? Rovnako ako, veľa. Dobre. Takže, zlé veci. Niektoré zlé veci, ktoré môžete urobiť, nie sú kontroly, či vaše malloc volanie vráti null, nie? V tomto prípade, sa pýtam systém, aby mi - čo je to číslo? Ako 2000000000 krát 4, pretože veľkosť celé číslo je 4 bajty. Pýtam sa ho, ako 8000000000 bajtov. Samozrejme môj počítač sa nebude môcť dať mi toľko pamäte späť. A my sme to zistili, či ak to je null, takže keď sa snažíme dereferencia to tam - sledovať šípku na miesto, kde to bude - nemáme, že pamäť. To je to, čo nazývame dereferencing nulový ukazovateľ. A to v podstate spôsobí, že sa segfault. To je jeden zo spôsobov, ako si môžete segfault. Ďalšie zlé veci, ktoré môžete urobiť - oh dobre. To bolo dereferencing nulový ukazovateľ. Dobre. Ďalšie zlé veci - dobre, opraviť, že ste práve dal šek tam , Ktorý kontroluje, či je ukazovateľ null a ukončite z programu, ak sa to stane, že malloc vracia nulový ukazovateľ. To je xkcd komické. Ľudia pochopili to hneď. Tak nejako. 

Tak, pamäť. A išiel som nad tým. Sme volania malloc v slučke, ale zakaždým, keď hovoríme malloc strácame prehľad o tom, kde tento ukazovateľ ukazuje na, preto, že sme tresnúť ho. Takže, počiatočné volanie malloc mi dáva pamäť tu. Moje ukazovateľ ukazovatele na toto. Teraz, nemám uvoľniť, takže teraz hovorím malloc znova. Teraz to ukazuje tu. Teraz má pamäť ukazuje tu. Polohovacie tu. Polohovacie tu. Ale ja som stratil prehľad o adresách všetkých pamäti tamto, že som pridelená. A tak teraz nemám žiadny odkaz na ne už. Takže, nemôžem oslobodiť mimo tento slučky. A tak za účelom stanovenia niečo také, ak ste zabudli voľnej pamäte a získajte tento pretečeniu pamäte, Musíte uvoľniť pamäť vo vnútri tejto slučky, akonáhle budete hotoví s ním. No, to je to, čo sa stane. Viem, že veľa z vás neznášam. Ale teraz - yay! Tu získate ako 44.000 KB. Takže, vy uvoľniť, na konci slučky, a že sa to jednoducho uvoľniť pamäť zakaždým. V podstate, váš program nemá pretečeniu pamäte už. 

A teraz niečo iné, čo môžete urobiť, je uvoľniť pamäť, ktorú ste žiadal dvakrát. V tomto prípade je malloc niečo, zmeniť jeho hodnotu. Môžete uvoľniť ho raz, pretože si hovoril, že sa s tým. Ale potom sme oslobodení znovu. To je niečo, čo je dosť zlé. To nebude spočiatku segfault, ale po chvíli, čo to robí, je dvojaký uvoľnenie tomuto korumpujú svoj haldy štruktúru, a naučíte trochu viac o tom, ak sa rozhodnete vziať triedu ako CS61. Ale v podstate po chvíli váš počítač bude zmiasť o tom, čo pamäťové miesta sú tie, kde a kedy je to uložené - , Kde sú údaje uložené v pamäti. A tak uvoľnenie ukazovateľ dvakrát, je zlé, že nechcete robiť. 

Ďalšie veci, ktoré sa môžu pokaziť nepoužíva sizeof. Takže, v tomto prípade malloc 8 bajtov, a to je to isté ako dve celé čísla, nie? Tak, to je úplne bezpečné, ale je to? No, ako Lucas hovoril o na rôznych architektúrach, čísla sú rôznych dĺžok. Takže, na zariadenia, ktoré používate, čísla sú asi 4 byty, ale na nejakom inom systéme, ktoré by mohli byť 8 bajtov alebo by mohli byť 16 bytov. Takže, ak som použiť toto číslo sem, tento program by mohol pracovať na zariadenia, ale to nebude alokovať dostatok pamäte na nejakom inom systéme. V tomto prípade, je to, čo operátor sizeof sa používa. Keď zavoláme sizeof (int), čo to robí, je  to nám dáva veľkosť celé číslo v systéme, ktorý beží program. Takže, v tomto prípade, bude sizeof (int) vráti 4 na niečo také zariadenia, a teraz táto vôľa 4 * 2, čo je 8, , Ktorý je len množstvo priestoru potrebné pre dvoch celých čísel. Na inom systéme, ak int je ako 16 bajtov alebo 8 bajtov, to len tak vrátiť dostatok bytov pre uloženie túto sumu. 

A konečne, struct. Takže, ak ste chceli uložiť sudoku dosku v pamäti, možno ako to urobíme? Môžete si myslieť, zo ako premenné pre prvú vec, premenná pre druhú vec, premenná pre tretiu vec, premenná pre štvrté vec - zlý, nie? Takže, jedna zlepšenie môžete vykonať na vrchole je to, aby sa 9 x 9 poľa. To je v poriadku, ale čo keď ste chceli pridružiť aj iné veci s radou sudoku ako to, čo obtiažnosť doske je, alebo, napríklad, aké sú vaše skóre, alebo ako dlho to trvalo vám vyriešiť tento program? No, čo môžete urobiť, je, že môžete vytvoriť struct. Čo som v podstate hovorí, je, že som vymedzenie túto štruktúru tu, a ja som definovanie sudoku doska, ktorá sa skladá z dosky, ktorá je 9 x 9. 

A to, čo má, že má ukazovateľ na meno úrovne. Má tiež X a Y, ktoré sú súradnice, kde som teraz. To má tiež čas strávený [nezrozumiteľný], a to má celkový počet ťahov som zadaných doteraz. A tak v tomto prípade, môžem zoskupiť veľa dát do jediného štruktúry namiesto toho, aby ju ako lietanie okolo ako rôzne premenné že nemôžem sledovať. A to nám umožňuje mať len peknú syntax pre druh odkazovanie rôzne veci vo vnútri tohto struct. Ja si proste board.board, a mám sudoku dosku späť. Board.level, som si, ako ťažké to je. Board.x a board.y daj mi súradnice, kde by som mohol byť na doske. A tak som prístup, čo nazývame pole v struct. Toto definuje sudokuBoard, čo je typ, ktorý mám. A teraz sme tu. Mám premennú s názvom "board" typu sudokuBoard. A tak teraz môžem pristupovať všetky polia, ktorá tvorí túto štruktúru tu. 

Akékoľvek otázky structs? Áno? [Študent] Pre int x, y, ste vyhlásil obaja na jednom riadku? >> [Joseph] Uh-huh. [Študent] Takže, mohol by si urobiť so všetkými z nich? Rovnako ako v roku X, Y čiarka časy, že celkové? [Joseph] Áno, mohol by ste určite urobiť, ale dôvod, prečo som dal x a y na rovnakom riadku - a otázkou je, prečo môžeme len to na rovnakom riadku? Prečo sme len dať všetky tieto na rovnakom riadku je x a y sú vo vzájomnom vzťahu, a je to len štylisticky presnejšie, v tom zmysle, pretože je to zoskupenie dve veci na rovnakom riadku že ako druh sa vzťahujú k rovnakej veci. A ja jednoducho rozdeliť tieto od seba. Je to len štýl vec. Je funkčne nie je rozdiel vôbec. Akékoľvek ďalšie otázky týkajúce sa structs? Môžete definovať Pokédex s struct. Pokémon má svoje číslo a má list, vlastníka, typ. A potom, ak máte pole Pokémon, môžete vytvoriť Pokédex, že jo? Dobre, v pohode. Takže, otázky týkajúce sa structs. Tí, ktorí sú príbuzní k structs. 

Konečne, GDB. Čo GDB nechať urobiť? To vám umožní ladiť svoj program. A ak ste nepoužili GDB, by som odporučil sledovať krátke a len tak nad tým, čo GDB je, ako s ním pracovať, ako by ste mohli použiť, a vyskúšať na programe. A tak to, čo GDB môžete urobiť, je, že umožňuje Pozastaviť [nezrozumiteľné] až do vášho programu a praktické línie. Napríklad, chcem pozastaviť plnenie v súlade ako 3 z môjho programu, a keď som na riadku 3 môžem vytlačiť všetky hodnoty, ktoré sú tam. A tak to, čo nazývame ako zastavil v rade je nazývame uvedenie zarážku na tomto riadku a potom môžeme vytlačiť premenné na stave programu v tej dobe. 

Môžeme potom odtiaľ krokovať program riadok po riadku. A potom sme sa pozrieť na stav zásobníka v tej dobe. A tak aby bolo možné používať GDB, čo robíme, je hovoríme rinčanie na súbor C, ale musíme odovzdať-ggdb vlajkou. A akonáhle sme skončili s tým sme len spustiť gdb na výslednom výstupného súboru. A tak si trochu ako hmotnosť textu ako je tento, ale naozaj všetko, čo musíte urobiť, je zadať príkazy na začiatku. Prestávka hlavné kladie zarážku na hlavnej. Zoznam 400 uvádza riadky kódu okolo riadku 400. A tak v tomto prípade stačí sa pozrieť okolo seba a povedať, oh, Chcem nastaviť zarážku na riadku 397, ktorý je v tomto riadku, a potom sa váš program beží do tohto kroku, a to rozbije. Bude to pauze, a môžete tlačiť, napríklad, hodnota nízka alebo vysoká. A tak tam sú banda príkazy, ktoré potrebujete vedieť, a to slideshow bude stúpať na webových stránkach, takže ak si len chcete odkazovať týchto alebo ako dať ich na svoje ťaháky, neváhajte. 

Cool. To bolo Quiz Review 0, a budeme držať okolo, ak máte nejaké otázky. Dobrá. 

 [Potlesk] 

[CS50.TV]