[Powered by Google Translate] [§ 6] [Další Komfortní] [Rob Bowden] [Harvard University] [To je CS50.] [CS50.TV] 

Můžeme zamířit do naší sekce otázek. Poslal jsem adresu URL pro prostor před. Začátek úseku otázek říct: zřejmě nejsem úplně unsick-je velmi jednoduchá otázka toho jen to, co je Valgrind? Co valgrind dělat? Každý, kdo chce říkat, co valgrind dělá? [Student] Kontrola memory leaks. Jo, valgrind je obecný paměti checker. To, na konci, vám řekne, pokud máte nějaké úniky paměti, což je většinou to, co jsme používat jej pro, protože pokud chcete dobře v problému sadě nebo chcete-li dostat na velkou tabuli, musíte mít žádné úniky paměti vůbec, a v případě, že máte nevracení paměti, že nemůžete najít, Také mějte na paměti, že vždy, když otevřete soubor a pokud nechcete zavřít, to je k nevracení paměti. 

Mnoho lidí, kteří hledají nějakou uzel že nejste uvolnění když ve skutečnosti, že neuzavřela slovník hned v prvním kroku. Také vám řekne, jestli máte nějaké neplatné čte nebo píše, což znamená, že pokud se pokusíte a nastavte hodnotu že je za konec haldy a není náhodou seg poruchy ale valgrind ji chytne, jako byste měli být skutečně psát tam, a proto byste rozhodně neměli mít žádné z nich jeden. Jak použít Valgrind? Jak použít Valgrind? 

Je to obecná otázka na druh spustit a podívat se na výstupu. Výstup je zaplaven mnohokrát. K dispozici je také zábavné chyby, kde, pokud máte nějaké hrozně špatnou věc děje ve smyčce, pak to bude nakonec říkat, "Way příliš mnoho chyb. Chystám se přestat počítat teď. " Je to v podstatě textová výstup, který budete muset analyzovat. Na konci, bude to vám žádné úniky paměti, že máte, kolik bloků, které mohou být užitečné, protože pokud je to jeden blok unfreed, pak je to obvykle snazší najít než 1000 bloků unfreed. 1000 bloky unfreed pravděpodobně znamená, že nejste uvolnění propojené seznamy odpovídajícím způsobem, nebo tak něco. To je Valgrind. 

Nyní máme naši sekci otázek, které nemusíte stahovat. Můžete kliknout na mé jméno a vytáhněte je do prostoru. Nyní klikněte na mně. Revize 1 bude zásobník, který děláme jako první. Revize 2 bude fronta, a Revize 3 bude jednotlivě propojený seznam. Rozjezd s naší zásobníku. Jak se říká, že tady, zásobník je jedním z nejzákladnějších, Základní datové struktury informatiky. Velmi Typický příklad je stoh přihrádek v jídelně. Je to v podstatě vždy, když se zavádí do zásobníku, někdo říct, "Oh, jako hromada zásobníků." Můžete stohovat zásobníky se. Pak, když jdete na vytáhnout zásobník, první zásobník, který je dostat vytáhl je poslední, který byl uveden na stack. Stack i-jako to říká tady- máme segmentu paměti s názvem stack. A proč se tomu říká stack? 

Vzhledem k tomu, jako zásobníku datové struktury, to tlačí a objeví zásobníku rámečky na zásobníku, kde stack rámy jsou jako zvláštní volání funkce. A jako hromada, budete mít vždy vrátit z volání funkce dříve, než můžete dostat dolů do nižších zásobníku snímků znovu. Nemůžete mít hlavní hovoru foo blokování hovorů a bar vrátíte do hlavního přímo. Je to vždycky dodržet správný zásobník tlačí a praskání. Obě operace, jak jsem řekl, jsou tlak a pop. Ti jsou univerzální pojmy. Měli byste vědět, push a pop z hlediska komíny bez ohledu na to, co. Uvidíme fronty jsou trochu odlišné. To není opravdu univerzální termín, ale tlak a pop jsou univerzální pro komíny. Push jen dát na stack. Pop je sundat zásobníku. A zde vidíme máme typedef struct stoh, takže máme char ** řetězce. Nenechte se bojí žádnými **. To bude skončit pole řetězců nebo pole ukazatelů na znaky, kde ukazatele na znaky bývají řetězce. Nemusí to být řetězce, ale tady, oni budou mít řetězce. 

Máme pole řetězců. Máme velikost, která představuje, kolik prvky jsou v současné době na frontě, a pak máme kapacitu, což je, kolik prvků může být na zásobníku. Výkon by měl začít jako něco větší než 1, ale velikost bude začít jako 0. Nyní, tam jsou v podstatě tři různé způsoby, jak můžete myslet zásobníku. No, tam jsou pravděpodobně více, ale dva hlavní způsoby jsou můžete implementovat pomocí pole, nebo můžete implementovat pomocí spojového seznamu. Propojené seznamy jsou trochu triviální, aby se stohy z. Je velmi snadné, aby se stoh pomocí propojených seznamů, takže tady, budeme dělat hromadu pomocí matice, a pak pomocí polí, je tu také dva způsoby, jak si můžete myslet o tom. Předtím, když jsem řekl, máme kapacitu zásobníku, takže se vejde prvek na zásobníku. 

Jediný způsob, že by se mohlo stát, je, jakmile hit 10 prvků, pak jste udělal. Možná víte, že tam je horní hranice 10 věcí na světě že už nikdy nebudete muset více než 10 věcí, na vašeho stacku, V takovém případě můžete mít horní mez na velikosti vašeho stacku. Nebo můžete mít svůj stack být nespoutaný, ale pokud děláte pole, to znamená, že pokaždé trefíte 10 prvků, pak budete muset růst na 20 prvků, a když trefíte 20 prvků, budete muset pěstovat své pole na 30 prvků nebo 40 prvků. Budeš muset zvýšit kapacitu, což je to, co budeme dělat. Pokaždé jsme dosáhli maximální velikosti našeho stacku, když jsme se tlačit něco jiného na, budeme muset zvýšit kapacitu. Zde jsme tlačit prohlášeny za bool push (char * str). Char * str je řetězec, který jsme tlačí do fronty, a bool jen říká, jestli se nám to podařilo, nebo nepodařilo. 

Jak můžeme selhat? Jaká je pouze okolnost, že si můžete myslet kde bychom potřebovali vrátit false? Jo. [Student] Pokud je to plné a my jsme s použitím skákal implementace. Jo, tak jak definujeme-on odpověděl pokud je to plné a my jsme s použitím ohraničená implementace. Pak budeme určitě vrátí false. Jakmile jsme narazili 10 věcí v poli, můžeme nevejde 11, tak jsme se vrátit false. Co když to je neomezený? Jo. Pokud nemůžete rozbalit pole z nějakého důvodu. Jo, takže paměť je omezený zdroj, a nakonec, pokud budeme tlačit věci do fronty znovu a znovu, budeme se snažit a přidělit větší pole, aby se vešly větší kapacita, a malloc nebo co jsme pomocí se bude vracet false. No, bude malloc vrátí null. 

Pamatujte si, že pokaždé jste někdy volat malloc, měli byste být kontrola, zda je vrací null, jinak že je správnost odpočet. Protože chceme mít neomezenou stack, jediný případ, budeme se vracet false, je když se budeme snažit zvýšení kapacity a malloc nebo cokoliv vrátí false. Pak pop neakceptuje žádné argumenty, a vrátí řetězec, který je na vrcholu zásobníku. Ať už to bylo naposledy tlačil do fronty je to, co pop se vrací, a také ji odstraní ze zásobníku. A všimněte si, že se vrátí hodnotu null, pokud není nic na stacku. Je vždy možné, že zásobník je prázdný. V Javě, pokud jste zvyklí na to, nebo jiných jazyků, snaží se pop z prázdného zásobníku může způsobit výjimku nebo tak něco. 

Ale v C, null je tak trochu z mnoha případů, jak vyřizujeme tyto problémy. Vracet null je, jak budeme znamenat, že zásobník je prázdný. Připravili jsme kód, který bude testovat svůj stack funkčnost, provádět tlačit a pop. To nebude mnoho kódu. Budu-vlastně, než to uděláme, náznak, náznak- pokud jste ho ještě neviděli, malloc není jediná funkce, , která přiděluje paměť na haldě pro vás. Existuje rodina Alloc funkcí. První z nich je malloc, který jste zvyklí. Pak je tu calloc, který dělá to samé jako malloc, ale to bude nulu vše za vás. Pokud jste někdy chtěli nastavit vše na nulu po mallocing něco měli byste se právě používá calloc v první řadě místo psaní pro smyčce propadl se na celý blok paměti. 

Realloc je jako malloc a má spoustu zvláštních případech, ale v podstatě to, co dělá, je realloc to trvá ukazatel, který již byla přidělena. Realloc je funkce, kterou chcete platit pozornost zde. To trvá ukazatel, který již vrátil z malloc. Řekněme, že jste požádat malloc ukazatel na 10 bajtů. Později si uvědomíte, že jste chtěli 20 bajtů, takže volat realloc na tomto ukazateli s 20 bajtů, a realloc automaticky zkopírovat vše, co pro vás. Pokud jste právě volal malloc znovu, jako bych měl blok 10 bajtů. Teď potřebuji blok 20 bytů, takže když jsem malloc 20 bajtů, pak musím ručně zkopírovat do 10 bajtů z prvních věcí, do druhé věci a pak bez první věc. Realloc se bude zabývat, že pro vás. 

Všimněte si, že podpis bude void *, který je jen vrací ukazatel na blok paměti, pak void * ptr. Můžete si myslet void * jako obecný ukazatel. Obecně platí, že nikdy řešit void *, ale malloc vrací void *, a pak je to jen použít jako to vlastně bude char *. Předchozí void *, který byl vrácen malloc nyní bude předán realloc, a pak se velikost je nový počet bajtů, které chcete přidělit, takže vaše nová kapacita. Dám vám pár minut, a to v našem prostoru. Začněte s revize 1. Zastavím tě po snad o dost času provést Push, a pak ti dám další přestávku dělat pop. Ale to opravdu není tolik kód vůbec. Nejvíce kód je pravděpodobně rozšiřuje věci, rozšíření kapacity. Dobře, žádný tlak, aby se úplně hotový, ale tak dlouho, jak se cítíte, jako že jste na správné cestě, to je dobrý. 

Má někdo nějaký kód se cítí dobře s mým vytažení? Jo, budu, ale má někdo nějaké kód, který jsem si vytáhnout nahoru? Dobře, můžete začít, uložit ji, ať je to cokoli? Vždycky zapomenu, že krok. Dobře, při pohledu na tlak, chceš vysvětlit svůj kód? [Student] Za prvé, jsem zvětšil velikost. Myslím, že bych snad měla mít, že-stejně, jsem zvětšil velikost, a vidím, jestli je to méně, než je kapacita. A pokud je to méně, než je kapacita, přidám do pole, že již máme. A pokud to není, jsem vynásobte kapacitu 2, a já přerozdělit řetězce pole, aby něco s větší kapacitou velikosti nyní. A pak, pokud se to nepodaří, řeknu uživatele a vrátí false, a pokud je to v pořádku, pak jsem dal řetězec v novém místě. 

[Rob B.] Také si všimněte, že jsme použili pěkný bitovou operátor zde vynásobit 2. Nezapomeňte, posun doleva se vždycky se vynásobí 2. Právo posun je rozdělen 2 tak dlouho, jak si vzpomenete, že to znamená, vydělte 2 jako v celé číslo děleno 2. To by mohlo zkrátit na 1 zde nebo tam. Ale posun doleva o 1 je vždycky třeba vynásobit 2, pokud přetečení hranice na celé číslo, a pak to nebude. Strana komentář. Rád dělám-to nebude měnit kódování jakýmkoliv způsobem, ale já bych něco takového dělat. Je to vlastně bude dělat to mírně delší. Možná to není ideální případ pro zobrazení této, ale já bych segmentu do těchto bloků- v pořádku, pokud tuto možnost, pokud se stane, a pak budu dělat něco, a pak se provádí funkce. Nepotřebuju, aby potom přejděte oči celou cestu dolů funkci vidět, co se stane po ostatnímu. Je to v případě, že pokud se stane, a pak jsem se vrátit. To také má pěkný výhodu všeho, nad tento rámec je nyní posunula ještě jednou doleva. Já už třeba, pokud jste někdy v blízkosti směšně dlouhý vedení, pak ty 4 bytů mohou pomoci, a také více vlevo je něco, méně ohromen se cítili, kdyby chtěli, v pořádku, musím si pamatovat Jsem v současné době v cyklu while uvnitř z jiného uvnitř smyčky for. Kdekoliv si můžete udělat toto daňové přiznání okamžitě, jsem něco jako. Je zcela volitelné a není v žádném případě očekávat. 

[Student] Měl by být velikost - v nepovede stavu? Poruchám podmínka je zde jsme nedokázali realloc, takže ano. Všimněte si, jak v nevyhovění stavu, pravděpodobně, pokud jsme volní věci později, budeme vždycky selhání bez ohledu na to, kolikrát se snažíme tlačit něco. Pokud budeme neustále tlačí, držíme increment velikosti, i když jsme se, že uvedení nic do zásobníku. Obvykle nemáme zvýšíte velikost až poté, co jsme úspěšně ji na zásobníku. Udělali bychom to, řekněme, buď tady a tady. A pak místo toho řekl s.size ≤ kapacitu, je to méně, než kapacita, jen proto, že jsme se přestěhovali, kde bylo všechno. 

A pamatujte, jediné místo, které bychom mohli případně vrátit false je tady, kde realloc vrátil null, a pokud jste náhodou na paměti standardní chyby, Možná byste mohli zvážit tento případ, kdy chcete vytisknout standardní chybu, tak fprintf stderr, ne jen tisknout přímo na standardní výstup. Opět, to není očekávání, ale pokud je to chyba, zadejte printf, pak budete chtít, aby se vytisklo na standardní chybový místo standardní výstup. 

Každý, kdo má něco jiného všimnout? Ano. [Student] Můžeš jít přes [neslyšitelnou]? [Rob B.] Ano, skutečná binariness to, nebo jen to, co to je? [Student] Takže vynásobte ji 2? [Rob B.] Jo, v podstatě. V binárním zemi, vždy máme sadu číslic. Přesun tento levé do 1 podstatě vloží jej sem na pravé straně. Zpět na toto, jen připomenutí, že vše, co v binární je síla 2, tak to představuje 2 na 0, to 2 na 1, to 2 na 2. Vložením 0 na pravé straně hned, jen jsme posun již všechno. Co se tehdy 2 k 0 je nyní 2 k 1, je 2 na 2. Na pravé straně, které jsme vložen je nutně bude 0, který dává smysl. Pokud jste někdy násobit číslo 2, nebude to skončit lichý, tak 2 k 0 místě by měla být 0, a to je to, co jsem napůl varoval předtím, je, pokud to náhodou posunout za počet bitů v celé číslo, pak 1 skončí až bude pryč. To je jediná starost, pokud se stalo, že se jednání s opravdu velkými kapacitami. Ale v tomto bodě, pak máte co do činění s řadou miliard věcí, které se nemusí vejít do paměti stejně. 

Nyní se dostaneme k popu, který je ještě jednodušší. Dalo by se to udělat jako, pokud jste náhodou pop spoustu, a teď jsi na poloviční kapacitu znovu. Dalo by se realloc zmenšit množství paměti máte, ale nemusíte se bát, že, takže jen realloc případ bude rostoucí paměti, nikdy zmenšuje paměť, která se chystá udělat pop super snadné. Nyní fronty, které se chystáte být jako komíny, ale pořadí, které budete mít věci se obrátí. Typický příklad fronty je linka, takže myslím, že pokud jste byli English, bych řekl, typický příklad fronty je fronta. Tak jako čáry, pokud jste první člověk v souladu, vy očekávat, že bude první osoba z řady. Pokud jste poslední osoba v souladu, se bude poslední, kdo opravit. Říkáme, že FIFO vzorec, vzhledem k tomu, zásobník byl LIFO vzorec. Tato slova jsou velmi univerzální. 

Stejně jako zásobníky a na rozdíl od polí, fronty obvykle neumožňují přístup k prvkům ve středu. Zde, zásobník, máme tlak a pop. Zde jsme náhodou volali jim Zařadí a dequeue. Také jsem slyšel jen posun a unshift. Slyšel jsem lidi říkat tlak a pop také použít do front. Slyšel jsem vložit, odstranit, tak tlačit a pop, když mluvíte o komíny, se tlačí a objevovat. Pokud mluvíte o front, můžete vybrat slova, která chcete použít pro vložení a vyjmutí, a tam je žádný konsensus o tom, co by mělo být nazýván. Ale tady máme Zařadí a dequeue. Nyní, struct vypadá téměř shodný s zásobníku struct. Ale musíme sledovat hlavy. Myslím, že to říká tady, ale proč potřebujeme hlavu? Prototypy jsou v podstatě totožné s tlačit a pop. Můžete si ji představit jako push a pop. Jediný rozdíl je pop se vrací-místo posledního, to se vrací jako první. 2, 1, 3, 4, nebo něco. A tady je začátek. Naše fronta je zcela plná, takže to čtyři elementy v něm. Konec naší fronty je v současné době 2, a teď jdeme vložit něco jiného. 

Když chceme vložit, aby něco jiného, ​​co jsme udělali pro zásobníku verzi je, že jsme rozšířili naši blok paměti. V čem je problém s tím? [Student] Přesunete 2. Co jsem říkal o konci fronty, to nedává smysl, že začneme na 1, pak chceme Dequeue 1, pak Dequeue 3, pak Dequeue 4, pak Dequeue 2, pak dequeue tuhle. Nemůžeme použít realloc teď, nebo přinejmenším, budete muset použít realloc jiným způsobem. Ale pravděpodobně by neměl používat realloc. Budete muset ručně zkopírovat svou paměť. 

Existují dvě funkce pro kopírování paměti. Je tu memcopy a memmove. Já jsem v současné době čtení manuálové stránky vidět, který z nich budete chtít použít. Dobře, memcopy, rozdíl je že memcopy a memmove, jeden se stará o věci správně kam kopírování do oblasti, která se stane překrývat oblast kopírujete z. Memcopy nezpracovává ji. Memmove dělá. Můžete myslet na problém jako- řekněme, že chci kopírovat toho chlapa, tito čtyři s tímhle chlapem přes. Na konci, co pole by měl vypadat Po kopírování je 2, 1, 2, 1, 3, 4, a pak některé věci na konci. To je však závisí na pořadí, ve kterém se vlastně kopírovat, protože pokud se neberou v úvahu skutečnost, že region jsme kopírování do překrývá ten jsme kopírování, pak bychom mohli udělat jako začátek tady, zkopírujte 2 do místa chceme jít, pak se přesunout naše ukazatele vpřed. 

Teď budeme mít tady a tady, a teď chceme kopírovat tenhle chlap nad tímhle chlápkem a přesunout naše ukazatele vpřed. Co budeme nakonec dostat je 2, 1, 2, 1, 2, 1 místo odpovídající 2, 1, 2, 1, 3, 4, protože 2, 1 přehlasovala původní 3, 4. Memmove úchyty, které správně. V tomto případě, v podstatě jen vždy memmove protože zpracovává správně. To obvykle neprovádí žádné horší. Myšlenka je místo od začátku a kopírování tímto způsobem jako jsme právě udělali tady, začíná od konce, a kopíruje, a v tomto případě, můžete mít nikdy problém. Neexistuje žádný výkon ztracena. Vždy používejte memmove. Nikdy starosti memcopy. A to je místo, kde budete muset zvlášť memmove zabalené-kolem část vaší frontě. Žádné starosti, pokud není zcela hotový. To je obtížnější, než zásobník, tlačení, a pop. 

Každý, kdo má jakýkoli kód, který jsme mohli pracovat s? I když úplně neúplné? [Student] Jo, je to úplně neúplné, ačkoli. Zcela neúplný je v pořádku, tak dlouho, jak budeme-můžete uložit revizi? Zapomněl jsem, že každý jednotlivý čas. Dobře, ignoruje, co se stane, když potřebujeme změnit velikost věci. Zcela ignorovat Resize. Vysvětlete tento kód. Jsem kontrolu v první řadě v případě, že je velikost menší než kopie první řadě a pak po tom, mám vložit-beru hlavu + velikost, a mohu ujistit, že se zalomí kolem kapacita pole, a mám vložit nový řetězec na této pozici. Pak jsem zvětšit velikost a vrátí true. 

[Rob B.] To je určitě jeden z těch případů, kdy budete chtít používat mod. Jakékoliv případě, kdy jste si obal kolem, pokud si myslíte, že obal kolem, bezprostřední myšlenka by měla být mod. Jako rychlý optimalizace / váš kód jeden řádek kratší, Všimněte si, že řádek bezprostředně po tohohle je pouze velikost + +, takže je sloučit, aby do tohoto řádku, velikost + +. Teď tady máme případ kde nemáme dostatek paměti, takže jsme se zvýšit naše kapacity 2. Myslím, že byste mohli mít stejný problém tady, ale můžeme ignorovat to teď, kde, pokud se vám nepodařilo zvýšit svou schopnost, pak budete chtít snížit kapacitu 2 znovu. Další krátká poznámka je, stejně jako vy můžete udělat + =, můžete také udělat << =. Téměř vše může jít před rovná, + =, | =, & =, << =. Char * new je náš nový blok paměti. Oh, tady. 

Co si lidé myslí o typu našeho nového bloku paměti? [Student] To by mělo být char **. Myšlení zpět k našemu struct sem, Řetězce je to, co jsme přerozdělení. Děláme celou novou dynamické úložiště pro prvky ve frontě. Co budeme se zařazování na seznam řetězců je to, co jsme mallocing teď, a tak nové bude char **. Je to bude pole řetězců. Tak co je tomu v případě, který se budeme vracet false? [Student] Měli bychom dělat char *? [Rob B.] Ano, dobrý nápad. [Student] Co to bylo? [Rob B.] Chtěli jsme udělat velikost char *, protože jsme již- To by ve skutečnosti bylo velmi velký problém, protože sizeof (char) bude 1. Sizeof char * bude 4, takže hodně krát, když máte co do činění s ints, máte tendenci se dostat pryč s ním, protože velikost int a velikosti int * na 32-bitovém systému se bude totéž. Ale tady, sizeof (char) a sizeof (char *) jsou nyní bude totéž. 

Co je okolnost, kdy se vrátíme false? [Student] Nové je null. Jo, když nový je null, vracíme false, a já jdu hodit tady- [Student] [neslyšitelné] [Rob B.] Jo, to je v pořádku. Dalo by se buď udělat 2 krát kapacity nebo kapacity shift 1 a pak jen nastavit to sem, nebo co. Uděláme to, jak jsme to. Kapacita >> = 1. A už nikdy muset obávat, že 1 je místo protože jsi odešel posunuty o 1, takže se 1 místo je nutně 0, tak správně řazení o 1, jste stále bude v pořádku. [Student] Potřebujete si udělat před návratem? [Rob B.] Ano, to je absolutně žádný smysl. 

Nyní předpokládejme, že budeme nakonec vrací hodnotu true do konce. Způsob, jakým budeme dělat tyto memmoves, musíme být opatrní s tím, jak děláme. Má někdo nějaké návrhy na to, jak děláme? Tady je náš start. Je samozřejmé, chceme od začátku znovu a kopírování věcí v odtamtud, 1, 3, 4, 2. Jak to děláte, že? Za prvé, musím se podívat na manuálové stránce pro memmove znovu. Memmove, pořadí argumentů je vždy důležité. Chceme, aby naše cíle první, zdroj druhý, velikost třetí. Existuje mnoho funkcí, které zvrátí zdroj a cíl. Destinace, zdroj bývá konzistentní poněkud. Move, co je to vrací? Vrací ukazatel na místo určení, z jakéhokoliv důvodu budete chtít, že. Jsem si obrázek přečíst, ale chceme přestěhovat do našeho cíle. 

Co je naším cílem bude? [Student] Nové. [Rob B.] Ano, a kde jsme kopírování? První věc, kterou kopírujete, je to 1, 3, 4. Co je-to 1, 3, 4. Jaká je adresa tohoto 1? Jaká je adresa tohoto 1? [Student] [neslyšitelné] [Rob B.] Head + adresa prvního prvku. Jak se dostat na první prvek v poli? [Student] Queue. [Rob B.] Ano, q.strings. Pamatujte si, že zde, naše hlava je 1. Látat to. Jen si myslím, že je to jako mávnutím kouzelného proutku, Zde, naše hlava je 1. Chystám se změnit můj barvu taky. A tady je řetězce. To, můžeme buď napsat to stejně jako my tady s hlavami + q.strings. Mnoho lidí také zapisovat a q.strings [hlava]. To není opravdu nic méně efektivní. Můžete si myslet, ze to, jak jste se dereferencing ji a pak se dostat adresu, ale kompilátor bude překládat, co jsme měli předtím tak, q.strings + hlava. Ať tak či onak si chcete myslet na to. 

A kolik bytů si chceme kopírovat? [Student] Kapacita - hlava. Kapacita - hlava. A pak můžete vždy zapsat příklad zjistit, jestli je to pravda. [Student] Je třeba rozdělit do 2 pak. Jo, takže myslím, že bychom mohli použít velikost. Stále máme velikost je- pomocí velikosti, musíme velikost stejnou jako 4. Naše velikost je 4. Naše hlava je 1. Chceme zkopírovat tyto 3 prvky. To je příčetnost zkontrolujte, zda velikost - hlava je správně 3. A přichází sem, jak jsme řekli dříve, pokud jsme použili kapacitu, pak bychom museli dělit 2 proto, že jsme už stalo naší schopnosti, a tak místo toho, budeme používat velikost. Že kopií, které porce. Nyní musíme zkopírovat druhou část, část, která je nalevo od začátku. 

To bude memmove do jaké pozici? [Student] Plus velikost - hlava. Ano, tak jsme již zkopírováno ve velikosti - hlava bajtů, a tak tam, kde chceme zkopírovat zbývající bajtů je nový a pak velikost minus stejně, počet bytů jsme již zkopírováno a. A pak, kde jsme kopírování? [Student] Q.strings [0]. [Rob B.] Ano, q.strings. Můžeme buď udělat a q.strings [0]. To je výrazně méně časté než tohle. Pokud to jen bude 0, pak budete tendenci vidět q.strings. To je místo, kde jsme kopírování. Kolik bytů nám zbývá zkopírovat? >> [Student] 10. Právo. [Student] Ještě musíme vynásobit 5 - 10 krát větší než velikost bajtů nebo tak něco? Jo, tak to je místo, kde-co přesně se kopírování? [Student] [neslyšitelné] Jaký je typ věci jsme kopírování? [Student] [neslyšitelné] Jo, takže char * s, že jsme kopírování, nevíme, kde ty jsou zasílány z. No, kde to ukázal, jako struny, skončíme to tlačil do fronty nebo enqueuing do fronty. Pokud ty jsou zasílány z, nemáme ponětí. Potřebujeme jen sledovat char * s sami. Nechceme kopírovat velikosti - hlava bytů. Chceme kopírovat velikosti - hlava char * s, takže budeme násobit tím sizeof (char *). Stejná sem, hlava * sizeof (char *). 

[Student] Co [neslyšitelné]? Toto právo tady? [Student] Ne, pod tím je velikost - hlava. [Rob B.] Toto právo tady? Ukazatel aritmetika. Jak ukazatel aritmetický bude fungovat, je automaticky násobí podle velikosti typu, že máme co do činění s. Stejně jako tady, nový + (velikost - hlava) je přesně ekvivalentní a nové [velikost - hlava] dokud očekáváme, že se pracovat správně, protože pokud máme co do činění s int pole, pak nemáme index int- nebo jestli je to z velikosti 5 a chcete 4. prvek, pak jsme index do int array [4]. Ty nedělej-[4] * velikost int. , Který zpracovává automaticky, a tento případ Je doslova ekvivalentní, takže držák syntaxe je jen tak být přeměněn na to co nejdříve zkompilovat. To je něco, co musíte být opatrní, aby Při přidávání velikost - hlava Přidáváte ne jeden bajt. Jste přidáním jednoho char *, což může být jeden bytů nebo cokoliv. 

Další otázky? Dobře, Dequeue bude jednodušší. Dám vám chvilku realizovat. Oh, a myslím, že to je stejná situace, kdy co enqueue případě, pokud budeme enqueuing null, Možná chceme zvládnout, možná nemáme. Budeme to dělat znovu tady, ale stejně jako naše zásobníku případě. Pokud budeme Zařadí null, mohli bychom chtít ignorovat. Každý, kdo má nějaký kód, který jsem si vytáhnout nahoru? [Student] Mám jen Dequeue. Verze 2 je, že-v pořádku. Chcete-li vysvětlit? [Student] Za prvé, musíte se ujistěte, že je něco, co ve frontě a že velikost klesá o 1. Musíte to udělat, a pak se vrátíte hlavu a pak přesunout hlavu 1. Dobře, tak tam je rohová případ, musíme vzít v úvahu. Jo. [Student] Pokud je vaše hlava je na poslední prvek, pak nechcete hlava bodu mimo pole. 

Jo, takže jakmile hlava udeří konec našeho pole, když jsme dequeue, by naše hlava se modded zpět na 0. Bohužel, nemůžeme to, že v jednom kroku. Myslím, že tak, jak jsem si asi stanovit, že je to bude char *, co se vracíme, bez ohledu na vaše jméno proměnné chce být. Pak chceme mod hlavu o naší schopnosti a pak se vrátit ret. Hodně lidí tady by se mohly do- To je případ-Budeš vidět lidi dělat, když se hlava je větší než kapacita, to hlavou - kapacita. A to je právě pracuje kolem toho, co mod je. Vedoucí mod = kapacita je mnohem čistší z obalu kolem, než-li hlava větší než kapacita hlavou - kapacita. 

Otázky? Dobře, poslední věc, kterou jsme si nechali je náš propojený seznam. Ty by mohly být použity na některé propojené seznamu chování, pokud jste souvisí seznamy ve vašich hash tabulkách, pokud jste hash tabulky. Vřele doporučuji dělat hash tabulky. Možná jste již udělali trie, ale pokusy jsou těžší. Teoreticky, jsou asymptoticky lepší. Ale stačí se podívat na velkou tabuli, a snaží se nikdy dělat lépe, a zabírají více paměti. Vše o snaží skončí bytí horší pro další práci. Je to to, co David Malan řešením je vždy Je vždycky příspěvků jeho trie roztoku, a podíváme se, kde v současné době je. Co bylo, že v rámci, David J? Je to # 18, tak, že to není příliš špatný, a že to bude jeden z nejlepších snaží si můžete myslet nebo jeden z nejlepších snaží o trie. Je to dokonce ani jeho originální řešení? Mám pocit, že trie řešení mají tendenci být více v tomto rozsahu použití RAM. 

Jděte dolů až na samý vrchol, a RAM využití je v jednotlivých číslic. Jděte dolů ke dnu, a pak začnete vidět pokusí kde dostanete naprosto masivní paměti RAM, a pokusy jsou obtížnější. Ne zcela stojí za to, ale vzdělávací zkušenosti, pokud jste jeden. Poslední věc, kterou je náš propojený seznam, a tyto tři věci, komíny, fronty, a propojené seznamy, budoucí věc, kterou kdy udělal v informatice Předpokládejme, že jste obeznámeni s těmito věcmi. Jsou to jen natolik zásadní pro všechno. 

Souvisí seznamy, a tady jsme singly spojový seznam se bude naše realizace. Co jednotlivě spojeny znamená ve srovnání s dvojnásobně spojené? Ano. [Student] To jen ukazuje na další ukazatele, spíše než na ukazatele, jako ten předcházející je i ten, za ní. Jo, tak v formátu obrazu, co jsem to udělal? Mám dvě věci. Mám obraz a obraz. V obrazu formátu, naše jednotlivě propojené seznamy, nevyhnutelně, máme nějaký ukazatel na hlavu našeho seznamu, a pak v našem seznamu, budeme muset ukazatele, a možná tento bodů na hodnotu null. Je to něco jako tvůj typický výkres singly propojeného seznamu. Dvojnásobně spojový seznam, můžete jít zpět. Kdybych vám žádný uzel v seznamu, můžete nutně dostat do jiné uzel v seznamu, pokud se jedná o dvojnásobně spojový seznam. Ale když jsem vám třetí uzel v seznamu a je to jednotlivě propojený seznam, žádný způsob, jak jste někdy dostane do první a druhé uzlů. A je tu výhody a detriments, a jeden zřejmý je vám zaberou více velikosti, a vy budete muset sledovat, kde se tyto věci směřují nyní. Ale my jsme jen o singly spojené. 

Pár věcí budeme muset realizovat. Vaše typedef struct node, int i: struct node * next; uzel. To typedef by měla být vypálena do vaší mysli. Quiz 1 by měl být rád dát typedef propojeného seznamu uzlu, a vy byste měli být schopni okamžitě čmárat, že se bez přemýšlení o tom. Myslím, že pár otázek, proč potřebujeme struct sem? Proč nemůže říci uzlu *? [Student] [neslyšitelné] Jo. Jediná věc, která definuje uzel jako věc je typedef sám. Ale jak tohoto bodu, když jsme trochu rozebrat pomocí této definice struct uzel, jsme neskončili naší typedef dosud, takže od té doby typedef nebylo dokončeno, uzel neexistuje. Ale struct uzel se, a tento uzel ve zde, to by mohlo také být nazýváno něco jiného. To by mohlo být nazýván n. Mohlo by to být nazýván provázaný seznam uzlu. Mohlo by to být jen něco. Ale to struct node potřebuje být nazýván totéž jako tento struct uzel. Co říkáte to má také být tady, a aby také odpovídá na druhý bod na otázky což je důvod, proč, mnohokrát, když vidíte structs a typedefs z structs, uvidíte anonymní structs, kde budete jen vidět typedef struct, provádění struct, slovník, nebo cokoliv jiného. 

Proč tady se musíme říci uzel? Proč to nemůže být anonymní struct? Je to skoro stejná odpověď. [Student] Musíte se na ni odvolávat v rámci struct. Jo, v struct, musíte se odkazovat na struct sám. Pokud nedáte struct jméno, pokud je to anonymní struct, nemůžete na něj odkazují. A v neposlední řadě, by toto vše mělo být poněkud přímočaré, a oni by vám měly pomoci si uvědomit, pokud píšete to stanoví že děláte něco špatně, pokud tyto druhy věcí nedávají smysl. V neposlední řadě, proč to musí být struct uzel *? Proč to nemůže být jen struct uzel dál? [Student] Ukazatel na další struct. To nevyhnutelně to, co chceme. Proč by se to nikdy nestane struct uzel dál? Proč to musí být struct node * next? Jo. [Student] Je to jako nekonečné smyčce. Jo. [Student] byl by to pořád v jednom. Jo, jen si na to, jak bychom to velikost nebo tak něco. Velikost struct je v podstatě + nebo - někteří vzor zde nebo tam. Je to v podstatě bude součet velikostí věcí v struct. To tady, aniž by se cokoliv změnilo, jeho velikost je bude snadné. Velikost struct uzel bude velikost i + velikosti vedle. Velikost i bude 4. Velikost příštího roku se bude 4. Velikost struct uzel bude 8. Pokud nemáme k *, myslel sizeof, pak sizeof (i) bude 4. Velikost struct uzel vedle bude velikost i + velikost struct uzel další + Velikost i + velikosti struct uzel další. Bylo by nekonečná rekurze uzlů. Z tohoto důvodu je to, jak věci mají být. 

Opět, rozhodně zapamatovat, že, nebo alespoň pochopit natolik, že je možné být schopen Důvodem tím, co by to mělo vypadat. Věci budeme chtít realizovat. Pokud délka seznamu- můžete podvádět a udržet kolem globální délka nebo tak něco, ale my nebudeme dělat, že. Budeme počítat délku seznamu. Máme obsahuje, tak, že je v podstatě jako vyhledávání, takže máme propojený seznam celých čísel zjistit, jestli to číslo je v připojeném seznamu. Prepend bude pro vložení na začátku seznamu. Append bude vkládat na konci. Insert_sorted bude vložit do tříděného pozici v seznamu. Insert_sorted druh předpokládá, že jste nikdy nepoužívali předřazený nebo připojený ve špatných cestách. 

Insert_sorted když jste provádění insert_sorted- Řekněme, že máme propojený seznam. To je to, co v současné době vypadá, 2, 4, 5. Chci vložit 3, tak dlouho, jak seznam sám je již řazeno, je snadné zjistit, kde 3 patří. Začínám na 2. Dobře, 3 je větší než 2, takže chci jít dál. Oh, 4 je příliš velký, takže vím, že 3 je jít mezi 2 a 4, a já musím opravit ukazatele a všechno to okolo. Ale pokud bychom neměli striktně používat insert_sorted, Líbí řekněme, že jsem předřadit 6, pak můj propojený seznam se stane tohle. To teď nemá smysl, tak pro insert_sorted, můžete jen předpokládat, že seznam je seřazen, i když operace existují které mohou způsobit, že se nebude seřazena, a to je to. Najít užitečné vložka-tak to jsou hlavní věci, které budete muset provést. 

Pro tuto chvíli, se chvíli dělat délku a obsahuje, a ty by měla být relativně rychle. Blíží zavírací doba, takže někdo něco pro délku nebo obsahuje? Chystají se být téměř totožné. [Student] Délka. Pojďme se podívat, revize. Dobře. Chcete-li vysvětlit? [Student] Právě jsem vytvořit ukazatel uzel a inicializovat ji jako první, což je naše globální proměnné, a pak jsem zkontrolovat, jestli je to null a tak jsem se nedostal seg chybu a vrátit 0, pokud tomu tak je. Jinak jsem průchozí, sledování v rámci celé číslo kolikrát jsem vstoupil na další prvek seznamu a ve stejném operace inkrementu rovněž přístup, že skutečný prvek, a pak jsem neustále, aby zkontrolovat, zda je to null, a, pokud je to nula, potom se přeruší a jen vrací počet prvků jsem přístupné. 

[Rob B.] Má někdo nějaké připomínky na cokoli? To vypadá dobře správnost moudrý. [Student] Já si nemyslím, že je třeba uzel == null. Jo, takže pokud uzel == null return 0. Ale pokud uzel == null pak-oh, je správnost problém. Bylo to jen vracíte i, ale to není v působnosti teď. Potřebujete k tomu jen int i, takže i = 0. Ale pokud uzel je null, pak jsem se ještě bude 0, a budeme se vrátit 0, takže tento případ je totožný. Dalším společným věc je mít k dispozici prohlášení uzlu uvnitř smyčky for. Dalo by se říci, oh, no. Pojďme držet to jako tohle. Asi bych dal int i = 0 zde, pak uzel * node = první zde. A to je asi, jak-jak se zbavit teď. Toto je pravděpodobně, jak bych napsal. Dalo by se také, při pohledu na něj takhle. To je pro smyčky struktury tady by měla být téměř stejně přirozené pro vás jako pro int i = 0 i je menší než délka pole i + +. Pokud to, jak se iterovat přes pole, to je to, jak jste iteraci propojeného seznamu. 

To by mělo být druhou přirozeností, v určitém okamžiku. S tím na mysli, to bude téměř to samé. Budeš chtít iteraci propojenou seznam. Pokud uzel-Nemám ponětí, co je hodnota nazývá. Uzlu i. Pokud je hodnota v tomto uzlu = i vrátit true, a to je vše. Všimněte si, že jediný způsob, jak se někdy vrátí false je-li nám iterovat přes celý propojeného seznamu a nikdy vrátit true, tak to je to, co to dělá. Jako vedlejší poznámku, budeme pravděpodobně nebude mít připojit nebo předřadit. 

Rychlé poslední poznámka. Pokud vidíte klíčového slova static, takže řekněme static int count = 0, a uděláme počet + +, můžete v podstatě si ji představit jako globální proměnné, i když jsem právě řekl, to není, jak budeme realizovat délku. Dělám to tady, a pak počítat + +. Každý způsob, jak můžeme zadat uzel do naší propojeného seznamu jsme navýšením naše počet. Bod je to, co statické klíčové slovo znamená. Pokud jsem měl int count = 0, že by normální stará globální proměnná. Co static int count znamená, že se jedná o globální proměnnou tohoto souboru. Je nemožné, aby nějaký jiný soubor, Líbí myslet PSet 5, pokud jste začali. Máte oba speller.c, a máte dictionary.c, a pokud jste právě deklarovat věc globální, pak nic speller.c lze přistupovat dictionary.c a naopak. Globální proměnné jsou přístupné jakékoliv. Oddíl C, ale statické proměnné jsou přístupné pouze v rámci samotného souboru, tak uvnitř spell checker nebo uvnitř dictionary.c, tohle je o tom, jak bych deklarovat svou proměnnou pro velikost mého pole nebo velikost mého počtu slov ve slovníku. Vzhledem k tomu, nechci deklarovat globální proměnné, že někdo má přístup k, Opravdu jen o to pro své vlastní účely. 

Dobrou věc, o to je také celé jméno kolize věci. Pokud nějaký jiný soubor se pokusí použít globální proměnnou s názvem znaků, věci jdou velmi, velmi špatné, tak to pěkně drží věci bezpečné, a jen vy můžete přistupovat, a nikdo jiný nemůže, a pokud někdo jiný deklaruje globální proměnnou s názvem počítat, pak to nebude v rozporu s vaší statické proměnné s názvem znaků. To je to, co statické je. Je soubor globální proměnná. 

Otázky týkající se něco? All set. Bye. [CS50.TV]