[Powered by Google Translate] [Část 6: Méně pohodlné]
[Nate Hardison] [Harvard University]
[To je CS50.] [CS50.TV]
Dobrá. Vítejte v sekci 6.
Tento týden, budeme mluvit o datových struktur v sekci,
především proto, že tento týden je problém nastavit na spellr
se celá parta jinou datovou strukturu průzkumu.
Existuje spoustu různých způsobů, jak můžete jít s tímto problémem set,
a čím více datových struktur víte o, tím více cool věcí, které můžete udělat.
>> Tak pojďme začít. Nejprve budeme mluvit o komíny,
zásobníku a fronty datové struktury, které budeme mluvit o.
Komíny a fronty jsou opravdu užitečné, když začneme mluvit o grafy,
které nebudeme dělat tolik teď.
Ale jsou opravdu dobré pochopit jednu z velkých základních datových struktur CS.
Popis ve specifikaci problému set,
pokud jste vytáhněte ji nahoru, hovoří o tom, komíny jako blízký
hromada jídelních podnosů, že máte v jídelně v jídelnách
kde, kdy jídelna zaměstnanců přijde a dá si jídelní podnosy z poté, co jsem vyčistit je,
oni vyrovnají jim jeden na druhého.
A pak, když děti přijdou do dostat jídlo,
vytahují zásobníky mimo nejprve vrchní, pak jeden pod ním, pak jeden dole, že.
Takže ve skutečnosti, první zásobník, který jídelní personál položil je poslední, který se vzlétlo.
Ten poslední, že jídelna zaměstnanci kladen na je první, který se vzlétlo k večeři.
V problému setu je spec, které si můžete stáhnout, pokud jste tak již neučinili,
Hovoříme-li o modelování zásobníku dat STRUKTURA pomocí tohoto druhu struct.
>> Takže to, co jsme se sem dostali, je to podobné tomu, co bylo uvedeno v přednášce,
výjimkou v přednášce jsme se prezentovali to s ints jako protiklad k char * s.
To bude zásobník, který ukládá, co?
Daniel? Co jsme uchovávání v tomto zásobníku?
[Daniel] Strings? >> Jsme ukládání řetězce v tomto zásobníku, přesně.
Vše je třeba mít k vytvoření zásobníku je pole
určité kapacity, která je v tomto případě,
kapacita bude ve všech velkých písmenech, protože je to konstanta.
A pak navíc k poli, vše musíme sledovat je aktuální velikost pole.
Jedna věc k poznámce, že je to docela fajn
je to, že jsme vytvoření skládaného datovou strukturu na vrcholu jiné struktury dat, pole.
Existují různé způsoby, jak implementovat stohy.
Budeme to dělat ještě dost, ale doufejme, že poté, co dělal na odkazovaných seznam problémů,
uvidíte, jak si můžete snadno implementovat balík na vrcholu propojeného seznamu stejně.
Ale teď, budeme držet pole.
Takže znovu, vše, co potřebujete, je pole a my stačí sledovat velikost pole.
[Sam] Omlouvám se, proč je to, že jste říkal, že stack je na vrchol řetězců?
Pro mě se zdá, že řetězce jsou v zásobníku.
[Hardison] Jo. Jsme vytváření, bereme naše pole datové struktury -
To je velká otázka. Takže otázka je, proč, pro lidi, kteří sledují tento on-line,
proč říkáme, že zásobník je na vrcholu řetězce,
protože tady to vypadá, jako jsou řetězce uvnitř zásobníku?
Což je naprosto případ.
To, co jsem měl na mysli, že máme maticový datovou strukturu.
Máme celou řadu char * s, toto pole řetězců,
a budeme přidávat k tomu, aby k vytvoření skládaný datovou strukturu.
>> Takže stack je poněkud složitější než pole.
Můžeme použít pole postavit stack.
Tak to je, kde můžeme říci, že zásobník je postaven na vrcholu pole.
Stejně tak, jak jsem řekl dříve, můžeme vybudovat zásobník na vrcholu propojeného seznamu.
Místo toho, aby pomocí pole držet naše prvky,
bychom mohli použít propojeného seznamu držet naše prvky a vytvořit stoh kolem toho.
Pojďme projít pár příkladů, při pohledu na nějaký kód,
vidět, co se vlastně děje.
Na levé straně, jsem hodil dolů, co to stack struct bude vypadat v paměti
pokud kapacita byla # definován být čtyři.
Máme naše čtyři prvek char * pole.
Máme řetězce [0], struny [1], struny [2], struny [3],
a pak, že poslední prostor pro naši velikost celé číslo.
Má to smysl? Dobře.
To je to, co se stane, když to, co mám dělat, na pravé straně,
který bude můj kód, je jen vyhlásit struct, skládaný struct volal s.
To je to, co dostaneme. Stanoví tento stopu v paměti.
První otázka je, co je obsahem tohoto zásobníku struct?
Právě teď nejsme nic, ale nejsou úplně nic.
Jsou tento druh odpadu. Nemáme tušení, co je v nich.
Když jsme prohlásit zásobník s, jsme jen házení, že se na vrcholu paměti.
Je to něco jako vyhlášení int i, a ne jeho inicializaci.
Ty nevíš, co je to tam. Můžete si přečíst, co je tam,
ale to nemusí být super užitečné.
Jedna věc, kterou chcete, aby se vždy pamatujte na to, je inicializovat, co je třeba inicializovat.
V tomto případě, budeme inicializovat velikost nula,
protože je to dopadne jako pro nás velmi důležité.
Mohli bychom pokračovat a inicializaci všech ukazatelů, všechny char * s,
se, že některé pochopitelné hodnota, pravděpodobně null.
Ale není to úplně nutné, uděláme to.
>> Nyní, dva hlavní operace komíny jsou?
Kdokoliv pamatuju z přednášky, co dělat s komíny? Ano?
[Stella] Stiskem a praskání? Přesně >>.
Tlačení a praskání jsou dvě hlavní operace na komíny.
A co tlačit dělat? >> Klade něco na vrcholu
ze zásobníku, a pak praskla vezme ho.
[Hardison] Přesně tak. Takže tlačí tlačí něco na vrcholu zásobníku.
Je to jako v jídelně zaměstnanců uvedení jídelní podnos na pult.
A objevovat bere jídelní podnos pryč zásobníku.
Pojďme projít pár příkladů toho, co se stane
když jsme se tlačit věci do zásobníku.
Pokud bychom měli tlačit na řetězec "ahoj" na naše zásobníku,
To je to, co naše schéma by vypadat jako teď.
Podívejte se, co se stane?
Usilovali jsme do prvního prvku naší řetězce pole
a my zvýšil naše velikost počet na 1.
Takže pokud se podíváme na rozdíl mezi dvěma skluzavkami, zde byla 0, tady je před stisknutím.
Zde je po stisku.
Před push, po stisknutí.
A teď máme jeden prvek v našem zásobníku.
Je to řetězec "ahoj", a to je vše.
Všechno ostatní v poli, v našem řetězcích poli, je stále odpadky.
Jsme není inicializována to.
Řekněme, že jsme se tlačit další řetězec do našeho zásobníku.
Budeme tlačit "svět" v této době.
Takže vidíte, "world" tady je na vrcholu "hello",
a velikosti znaků sahá až do 2.
Nyní můžeme tlačit "CS50", a že to jít na vrcholu znovu.
Když se vrátíme, můžete vidět, jak se tlačí věci na vrcholu zásobníku.
A teď se dostáváme k popu.
Když jsme vyskočila něco z fronty, co se stalo?
Každý Vidíte ten rozdíl? Je to docela jemné.
[Student] velikost. >> Jo, její velikost.
>> Co jiného by jste očekávali změnit?
[Student] Řetězce, taky. Právo >>. Řetězce taky.
Ukazuje se, že když děláte to takhle,
protože nejsme kopírování prvků do našeho zásobníku,
jsme vlastně nemusíme dělat nic, my můžeme jen použít velikost
sledovat počtu věcí v našem poli
takže když jsme pop, znovu jsme právě decrement svoji velikost až 1.
Není potřeba, aby skutečně jít a přepsat cokoliv.
Druh funky.
Ukazuje se, že jsme obvykle jen nechat věci sám, protože je to méně práce pro nás udělat.
Pokud nemáme jít zpět a přepsat něco, tak proč to?
Takže když jsme se pop dvakrát pryč zásobníku, vše, co dělá, je decrement do velikosti několikrát.
A opět, je to jen proto, že nejsme kopírování věci do našeho stacku.
Ano? Mluvte.
[Student, nesrozumitelné] >> A co se stane pak, když budete tlačit zase něco?
Když stisknete zase něco, kde to jde?
Pokud to půjde, Basile? Do >> řetězců [1]? Právo >>.
Proč to jít do řetězce [3]?
[Basil] Vzhledem k tomu, že zapomněl, že tam bylo něco v řetězci [1] a [2]?
[Hardison] Přesně tak. Naše zásobník, v podstatě, "zapomněl", že to držel na cokoliv
v řetězci [1] nebo řetězce [2], takže když jsme se tlačit "Woot",
to jen vezme, že do elementu v řetězci [1].
Jsou nějaké otázky, na tom, jak to funguje, na základní úrovni?
[Sam] Tak to není dynamický žádným způsobem, pokud jde o výši
nebo, pokud jde o velikosti zásobníku?
[Hardison] Přesně tak. To je - šlo o to, že to není dynamicky growning stack.
To je zásobník, který může obsahovat, nanejvýš čtyři * char s, nejvýše čtyři věci.
Pokud bychom měli zkusit a tlačit pětiny věc, co si myslíte, že by se mělo stát?
[Studenti, nesrozumitelné]
[Hardison] Přesně tak. Existuje celá řada věcí, které by se mohlo stát.
To by mohlo seg poruchy, závislosti na tom, co jsme byli -
jak přesně jsme realizaci back-end.
Mohlo by to přepsat. To by mohlo mít, že buffer overflow, že jsme mluvili o ve třídě.
Jaký by měl být nejzřejmější věc, která by mohla být přepsána
pokud jsme se snažili tlačit další věc na našem zásobníku?
Takže vy jste zmínil přetečení vyrovnávací paměti.
Co by mohlo být to, co by si psal přes nebo dupl na
pokud bychom přetekl náhodou, že se snaží tlačit další věc?
[Daniel, nesrozumitelné] >> Možná.
Ale zpočátku, může, co se stalo? Co když jsme se snažili tlačit čtvrtiny věc?
To by mohlo přepsat velikost, alespoň s tímto paměťovým schématu, které jsme dostali.
>> Ve specifikaci problému set, což je to, co budeme se provádí dnes,
co chceš udělat, je jen vrátí false.
Naše Push metoda bude vracet booleovskou hodnotu,
a že boolean hodnota bude true, pokud tlak uspěje
false, pokud nemůžeme prosazovat nic víc, protože zásobník je plný.
Projděme trochou uvedeného kodexu teď.
Tady je náš stisk funkce.
Naše tlak funkce pro soustavu bude trvat v řetězci, aby na zásobníku.
Bude to vrátí hodnotu true, pokud řetězec byl úspěšně tlačil
na stack a false jinak.
Nějaké návrhy na to, co by mohlo být dobrý první věc tady?
[Sam] Pokud velikost odpovídá kapacitu pak vrátí false?
[Hardison] Bingo. Dobrá práce.
Pokud je velikost kapacity, budeme se vrátit false.
Nemůžeme dát něco více v našem zásobníku.
V opačném případě budeme chtít dát něco na vrcholu zásobníku.
Co je to "vrchol zásobníku," původně?
[Daniel] Velikost 0? Velikost >> 0.
Co je vrchol zásobníku po tu jedna věc, kterou v zásobníku? Missy, víš?
[Missy] One. Velikost >> je, přesně tak. Ty držet přidání do velikosti,
a pokaždé, když jste uvedení v novém prvku v indexu velikost v poli.
Můžeme to udělat s tímto druhem jedné vložky, pokud to dává smysl.
Takže máme naše struny nabídku, budeme přistupovat na velikosti indexu,
a my jsme jen tak uložit naše char * tam.
Všimněte si, jak tam je žádný řetězec kopírování tu děje,
no dynamické přidělování paměti?
A pak Missy přinesl to, co teď musíme udělat,
protože jsme uložili řetězec na příslušném místě v poli,
a ona řekla, že jsme museli zvýšit velikost jednoho tak, že jsme připraveni na další Push.
Takže, co můžeme udělat, aby se s.size + +.
V tomto bodě, jsme tlačeni do našeho pole. Co je poslední věc, kterou musíme udělat?
[Student] Vrací true. >> Vrací true.
Takže je to docela jednoduché, docela jednoduchý kód. Ne moc.
Jakmile omotal hlavu kolem, jak stack funguje,
to je docela snadno implementovat.
>> Nyní, další část z toho se objevovat řetězec pryč zásobníku.
Já ti dám si kluci nějaký čas pracovat na tomto trochu.
Je to skoro podstatě opak toho, co jsme udělali tady v Push.
To, co jsem udělal, je vlastně - oops.
Jsem nastartoval až spotřebiče tady, a ve spotřebiči,
Já jsem vytáhl problém nastavit 5 specifikaci.
Pokud bychom přiblížíte tady, můžeme vidět jsem na cdn.cs50.net/2012/fall/psets/pset5.pdf.
Už jste stáhli tento kód, který je zde umístěn, section6.zip?
Dobrá. Pokud jste tak dosud neučinily, aby to, že právě teď, opravdu rychle.
Udělám to v mém terminálovém okně.
Vlastně jsem to udělal tady. Jo.
Ano, Sam? >> Mám otázku o tom, proč jste říkal, že s.string 's držáky na velikosti = str?
Co je to str? Je vymezen někde před, nebo - oh, v char * str?
[Hardison] Ano, přesně tak. To byl argument. >> Oh, dobře. Promiňte.
[Hardison] Jsme určující řetězec, aby se zasadila palců
Další otázka, která by mohla přijít, že jsme se opravdu mluvit o zde byla
jsme se za samozřejmé, že jsme měli tuto proměnnou s názvem s
, který byl v rozsahu a přístupné pro nás.
Vzali jsme za samozřejmé, že s je tento stack struct.
Takže ohlédnutí za touto Push kód,
můžete vidět, že děláme věci s tímto řetězcem, který dostal prošel v
ale pak najednou, že jsme přístup k s.size, stejně jako tam, kde se s pocházejí?
V kódu, který se budeme dívat na v sekci archivu
a pak věci, které budete dělat ve svém problému zapadne,
jsme udělali náš stack struct globální proměnné
takže můžeme mít k němu přístup na všech našich různých funkcích
aniž byste museli ručně projít kolem a předat jej odkazem,
dělat všechny tyhle věci k ní.
Jsme prostě podvádí trochu, chcete-li, aby se věci hezčí.
A to je něco, co tady děláme, protože je to pro zábavu, je to jednodušší.
Často, uvidíte lidé to v případě, že má jednu velkou datovou strukturu
, který je provozován na v rámci jejich programu.
>> Vraťme se k zařízení.
Bylo všichni úspěšně získat section6.zip?
Všichni rozbalte jej pomocí Rozbalte section6.zip?
Pojedete-li do sekce 6 adresáře -
aah, všude možně -
a seznam toho, co je tady, vidíte, že máte tři různé. C soubory.
Máte frontu, SLL, což je singly-linked list, a zásobník.
Pokud otevřete stack.c,
můžete vidět, že máme tuto struct definované pro nás,
Přesný struct, že jsme právě mluvili ze sklíčka.
Máme naše globální proměnné pro zásobník,
jsme dostali náš Push funkci,
a pak jsme dostali náš pop funkci.
Dám kód pro zatlačte zpátky na snímku zde,
ale to, co bych chtěl vy udělat, je, jak nejlépe své schopnosti,
jít a provádět pop funkci.
Jakmile jste implementovali, můžete kompilovat to s make stoh,
a spusťte výsledné zásobníku spustitelný,
a že poběží celý tohoto zkušebního předpisu tady to je v main.
A hlavní stará skutečně dělat push a pop hovory
a ujistěte se, že všechno jde přes všechny práva.
To také inicializuje velikost zásobníku tady
takže nemusíte mít strach o inicializaci, že.
Můžete předpokládat, že to bylo správně inicializován
v okamžiku, kdy jste k němu měly přístup do pop funkci.
Dává to smysl?
Tak jdeme na to. Tam je tlak kód.
Dám ti kluci 5 nebo 10 minut.
A pokud máte nějaké dotazy v mezidobí, když jste kódování,
zeptejte se nahlas.
Takže pokud se dostanete do problematickým bodem, zeptejte se.
Dejte mi vědět, ať všichni ostatní vědět.
Práce se svým sousedem taky.
[Daniel] Zrovna provádění pop teď? Jen >> pop.
I když můžete zkopírovat provádění Push, pokud chcete
tak, že testování bude fungovat.
Vzhledem k tomu, že je obtížné testovat věci dostat do -
nebo, je obtížné testovat objevovat věci z hromady, pokud tam není něco v zásobníku začít.
>> Co je pop měl být vracející? Prvek z horní části zásobníku.
Má to dostat prvek pryč horní části zásobníku
a pak dekrementace velikost zásobníku,
a teď jste ztratili prvek na vrcholu.
A pak se vrátíte prvek na vrcholu.
[Student, nesrozumitelným]
[Hardison] Takže co se stane, pokud to uděláte? [Student, nesrozumitelným]
Co se skončí událost je budete pravděpodobně přístup buď
prvek, který nebyl inicializován ještě, takže výpočet
, kde se poslední prvek je vypnutý.
Takže tady, pokud si všimnete, v Push, jsme přístup řetězce na s.size prvku
protože je to nový index.
Je to nový vrchol zásobníku.
Vzhledem k tomu, pop, s.size bude příští prostor,
prostor, který je v horní části všech prvků ve stohu.
Takže na nejvyšší element není v s.size,
ale, že je to pod ní.
>> Další věc, kterou udělat, když se - v popu,
je si třeba decrement velikosti.
Pokud si pamatujete zpět do naší malé diagramu tady,
Opravdu, jediná věc, která jsme viděli děje, když my jsme volali pop
bylo, že tato velikost klesla, první 2, pak 1.
Pak, když jsme se tlačil nový prvek na, by to jít na na správném místě.
[Basil] Pokud s.size je 2, pak není to jít na prvku 2,
a pak budeš chtít pop ten element off?
Takže pokud bychom šli do - >> Tak se pojďme podívat na to znovu.
Pokud je to náš zásobník na tomto místě
a nazýváme pop,
na které index je na nejvyšší element?
[Basil] Na 2, ale bude to pop 3. Právo >>.
Tak to je, kde je naše velikost 3, ale chceme, aby pop prvek na indexu 2.
Je to tak typické druh off by ten, který máte s nulovou indexování polí.
Takže vy chcete pop třetí prvek, ale třetí prvek není na indexu 3.
A důvod, proč nemáme dělat, že mínus 1, když jsme tlačení
je, protože právě teď, zjistíte, že na nejvyšší prvek,
pokud bychom měli tlačit něco jiného na stacku v tomto bodě,
budeme chtít tlačit na indexu 3.
A to jen tak se stane, že velikost a indexy zarovnány, když tlačí.
>> Kdo má pracovní zásobníku implementace?
Máte pracovní stack jeden. Máte pop pracovat ještě?
[Daniel] Ano. Myslím, že ano.
Program >> funguje a není seg chybující, je to vytisknout?
Má to vytisknout "úspěch" při spuštění?
Jo. Udělejte zásobník, spusťte jej, pokud se vytiskne "úspěch" a nejde boom,
pak vše je dobré.
Dobrá. Pojďme k přístroji opravdu rychle,
a projdeme to.
Podíváme-li se na to, co se tady děje s pop,
Daniel, co bylo první věc, kterou udělal?
[Daniel] Pokud s.size je větší než 0.
[Hardison] Dobře. A proč jsi to udělal, že?
[Daniel] Ujistěte se, že tam bylo něco uvnitř zásobníku.
[Hardison] Právo. Chcete-li otestovat, aby se ujistil, že s.size je větší než 0;
jinak, co chceš, aby se stalo?
[Daniel] Return null? Návrat >> null, přesně.
Takže pokud s.size je větší než 0. Tak co budeme dělat?
Co budeme dělat, když zásobník není prázdný?
[Stella] Zde decrement velikost? Ty >> decrement velikosti, v pořádku.
Tak jak jsi to udělal, že? >> S.size--.
[Hardison] Great. A pak to, co jsi udělal?
[Stella] A pak jsem řekl: return s.string [s.size].
[Hardison] Great.
V opačném případě se vrátíte null. Ano, Sam?
[Sam] Proč to nemusí být s.size + 1?
[Hardison] Plus 1? Jo >>. >> Mám to.
[Sam] Myslel jsem, že proto, že jste s 1 ven,
pak budete vracet není ten, že požádal.
[Hardison] A to bylo přesně to, co jsme mluvili o této celé problematice 0 indexů.
Takže když jsme přibližování tady.
Podíváme-li se na toho chlapa tady, můžete vidět, že když jsme pop,
jsme objevovat prvek na indexu 2.
>> Tak jsme snížit svoji velikost jako první, pak je naše velikost odpovídá náš index.
Pokud nemáme decrement velikosti, potom musíme udělat velikosti -1 a pak útlum.
Great. Všechny dobré?
Jakékoliv dotazy na to?
Existuje celá řada různých způsobů, jak napsat to stejně.
Ve skutečnosti, můžeme udělat ještě něco - co můžeme udělat, je jednořádkový.
Můžeme udělat jeden řádek návrat.
Takže můžeme skutečně decrement předtím, než jsme se vrátit tím, že.
Takže uvedení - před s.size.
To dělá linka opravdu hustá.
V případě, že rozdíl mezi -. S velikostí a s.size--
je, že tento postfix - říkají, že postfix, protože - přichází po s.size--
Znamená to, že s.size je vyhodnocena pro účely zjištění indexu
jak je to v současné době, kdy se provádí tento řádek,
a pak - se stane po řádku se provede.
Po prvek na s.size indexu je přístupná.
A to není to, co chceme, protože chceme, aby úbytek se stane první.
Othewise, budeme přistupovat k pole, efektivně, mimo meze.
Budeme přistupovat k prvku nad ten, který jsme vlastně chcete otevřít.
Jo, Sam? >> Je to rychlejší, nebo použít méně RAM, aby se v jedné řadě, nebo ne?
[Hardison] Upřímně řečeno, to opravdu záleží.
[Sam, nesrozumitelné] >> Jo, to záleží na okolnostech. Můžete to udělat kompilátoru triky
získat kompilátor uznat, že většinou, jsem si představit.
>> Tak jsme se již zmínil něco málo o této věci optimalizace kompilátoru
že si můžete dělat při sestavování,
a to je to věc, která kompilátor mohl zjistit,
jako oh, hey, možná bych mohl udělat to všechno v jedné operaci,
jak protichůdný k načítání velikost proměnné od RAM,
dekrementování to, ukládání zpátky, a pak se načítání je zpět
zpracovat zbytek této operace.
Ale obvykle, ne, to není ten druh věci
, co se děje, aby se váš program výrazně rychlejší.
Nějaké další otázky týkající se sad?
>> Takže tlačení a praskání. Pokud jste kluci chtějí vyzkoušet hackerský vydání,
co jsme udělali v hackerské vydání je skutečně pryč
a dělal to stack roste dynamicky.
Úkolem je především tady v tlačné funkci,
přijít na to, jak udělat, aby pole rostou
jak si udržet tlačit více a více prvků na do zásobníku.
Je to vlastně není moc doplňkový kód.
Jen volání - musíte mít na paměti, aby se volání malloc tam správně,
a pak zjistit, kdy budete volat realloc.
To je zábavné problém, pokud máte zájem.
>> Ale v současné době, pojďme dál, a pojďme mluvit o frontách.
Procházejte zde.
Fronta je blízko sourozenec zásobníku.
Takže v zásobníku, byly věci, které dal v poslední
byly první věci, a pak být načtena.
Máme to poslední dovnitř, první ven, nebo LIFO, objednávání.
Vzhledem k tomu, ve frontě, jak byste očekávali od okamžiku, kdy jste stál ve frontě,
první osoba se dostat do souladu, první věc, dostat se do fronty,
je první věc, která se dostane načíst z fronty.
Fronty jsou také často používá, když máme co do činění s grafy,
jako bychom mluvili o stručně s komíny,
a fronty jsou také užitečné pro spoustu dalších věcí.
Jedna věc, která přijde často se snaží udržovat, například,
seřazený seznam prvků.
A můžete to udělat pomocí pole. Můžete udržovat seřazený seznam věcí v matici,
ale tam, kde to dostane složité je pak budete mít vždy najít
vhodné místo pro vložení další věc.
Takže pokud máte řadu čísel, 1 až 10,
a pak chcete rozšířit, že na všechna čísla 1 až 100,
a vy jste stále tato čísla v náhodném pořadí a snaží se udržet vše
seřazeny, jak si projít, můžete skončit museli udělat hodně řazení.
U některých typů front a některých typů podkladových datových struktur,
můžete skutečně udržet poměrně jednoduchý.
Nemáte něco přidat a pak přeorganizovat celá věc pokaždé.
Ani budete muset udělat hodně posunutí vnitřních prvků kolem.
Když se podíváme na frontě, uvidíte, že - také v queue.c v úseku -
struct, že jsme stejně vám je opravdu podobný struct, že jsme vám dal na stack.
>> Je tu ještě jedna výjimka z tohoto, a že jedna výjimka
je to, že máme tuto dodatečnou integer s názvem hlava,
a hlava je zde pro sledování hlavy fronty,
nebo první prvek v řadě.
S hromadou, jsme byli schopni sledovat prvku, který jsme měli k načtení,
nebo horní části zásobníku, používat jen velikost,
vzhledem k tomu, s fronty, jsme se museli vypořádat s opačných koncích.
Snažíme křižovat věci na konci, ale pak se vrátí věci z přední strany.
Takže účinně, s hlavou, máme index na začátku fronty,
a velikost nám dává index konec fronty
takže můžeme získat věci z hlavy a přidat věci k ocasu.
Vzhledem k tomu, s komínem, jsme byli vždy jen se jedná o vrchol zásobníku.
Nikdy jsme neměli přístup na dno zásobníku.
Jsme jen přidal věci nahoru a vzal věci pryč z horní
takže jsme nepotřebovali, že další pole uvnitř naší struct.
Znamená to, že obecně smysl?
Dobrá. Ano, Charlotte? [Charlotte, nesrozumitelným]
[Hardison] To je velká otázka, a to ten, který přišel v přednášce.
Možná procházel několika příkladech ukážeme, proč
nechceme používat struny [0] jako hlavu fronty.
>> Tak si představte, že máme frontu, budeme říkat, že fronty.
Na začátku, když jsme právě instanci to,
když jsme právě oznamoval, jsme není inicializována nic.
Je to všechno smetí. Takže samozřejmě chceme, aby se ujistil, že inicializujeme
jak velikost a hlavy pole na 0, něco rozumné.
Mohli bychom také pokračovat a hodnotu null z prvků v našem frontě.
A aby se tento diagram fit, zjistíte, že se naše fronty může mít pouze tři prvky;
vzhledem k tomu, naše stack mohl držet čtyři, může naše fronty jen držet tři.
A to jen proto, aby se diagram fit.
První věc, která se zde děje je, že jsme Zařadí řetězec "ahoj".
A stejně jako jsme to udělali s zásobníku, nic hrozně tu jiný,
hodíme řetězce na na struny [0] a vložili naše velikost o 1.
My Zařadí "bye", dostane se na sebe.
Takže to vypadá jako hromada z podstatné části.
Začali jsme tady, nový prvek, nový prvek, velikost udržuje jít nahoru.
Co se stane v tomto okamžiku, kdy chceme, aby dequeue něco?
Chceme-li dequeue, která je prvek, který chceme dequeue?
[Basil] Strings [0]. >> Zero. Přesně tak, Basil.
Chceme se zbavit prvního řetězce, toto jeden, "hi".
Takže to, co je další věc, která se změnilo?
Všimněte si, když jsme vyskočila něco z fronty, jen jsme změnili velikost,
ale tady, máme pár věcí, které se mění.
Nejen, že se velikost změny, ale hlava změny.
Toto se vrací do bodu Charlotte starší:
proč máme tento hlavu stejně?
Má to smysl teď, Charlotte? >> Druh.
[Hardison] Druh? Takže to, co se stalo, když jsme dequeued?
Co hlava to, že nyní je zajímavé?
[Charlotte] No, protože se to změnilo - v pořádku. Aha.
Vzhledem k tomu, hlava - kde hlava směřuje ke změnám, pokud jde o umístění.
Je to už není vždy nula index jeden. >> Jo, přesně tak.
Co se stalo, bylo-li dequeueing vysokou prvek
byla dokončena a my jsme neměli tuto hlavu pole
protože jsme byli vždy volat tento řetězec na 0 indexu hlava naší fronty,
pak bychom museli posunout zbytek fronty dolů.
Museli bychom se posunout "bye" od z řetězce [1] na řetězce [0].
A řetězce [2] se stanoví na řetězce [1].
A budeme muset udělat pro celý seznam prvků,
celá řada prvků.
A když to děláme s řadou, která se opravdu nákladné.
Tak tady, to není velký problém. Musíme jen tři prvky v našem poli.
Ale kdybychom měli frontu tisíc prvků nebo milion prvky,
a pak všichni najednou, začneme dělat spoustu Dequeue volá všechny ve smyčce,
věci opravdu zpomalit, protože přesouvá všechno dolů neustále.
Víte, posunout o 1, posun o 1, posun o 1, posun o 1.
Místo toho, my používáme tuto hlavu, říkáme, že "ukazatel", i když to není opravdu ukazatel
v pravém slova smyslu, není to ukazatel typu.
Není to int * nebo char * nebo něco podobného.
Ale je to ukazovat nebo označující hlavu naší fronty. Jo?
>> [Student] Jak Dequeue vědět jen pop off, co je v čele?
[Hardison] Jak Dequeue vědět, jak se pop off, co je v čele? Právo >> jo.
>> Co je to při pohledu na to jen, co hlava pole je nastaven na.
Takže v tomto prvním případě, když se podíváme tady,
Naše hlava je 0, index 0. Právo >>.
[Hardison] Tak to jen říká, že v pořádku, dobře, prvek na indexu 0, řetězec "ahoj",
je prvek v čele naší fronty.
Takže budeme dequeue toho chlapa.
A to bude prvek, který se vrátil do volajícímu.
Ano, Saad? Takže >> hlava v podstatě nastaví - kde budete indexovat?
To je začátek toho? Jo >>. Dobře >>.
[Hardison] To stát nový začátek pro naše pole.
Takže když dequeue něco, vše, co musíte udělat, je přístup k prvku na indexu q.head,
a že bude prvek, který chcete dequeue.
Máte také decrement velikosti.
Uvidíme se za chvilku, kdy se věci trochu složitější s tím.
My dequeue, a teď, když se Zařadí znovu,
kde máme Zařadí?
Pokud se další prvek jít v naší frontě?
Řekněme, že chceme Zařadí řetězec "CS".
Do kterého index to půjde? [Studenti] Řetězce [2]. Dva >>.
Proč 2 a ne 0?
[Basil] Vzhledem k tomu, nyní hlava je 1, tak, že je jako na začátku seznamu?
[Hardison] Právo. A co označuje konec seznamu?
Co jsme pomocí naznačovat konec naší fronty?
Hlava je hlava naší fronty, začátek našeho fronty.
Jaký je konec našeho fronty? [Studenti] Velikost. Velikost >> přesně.
Takže naše nové prvky jít na velikosti, a prvky, které se vzlétnout sundat na hlavu.
Když jsme Zařadí další prvek, jsme dávat jej do velikosti.
[Student] Než dáte, že v když, velikost byla 1, ne?
[Hardison] Právo. Tak není zcela na velikosti. Velikost +, ne 1, ale + hlava.
Protože jsme posunul všechno za hlavu částky.
Tak tady, teď máme fronty velikosti 1, která začíná na indexu 1.
Ocas je index 2. Ano?
>> [Student] Co se stane, když se Dequeue řetězce [0], a sloty Řetězce "v paměti
Jen si vyprázdnila, v podstatě, nebo jen zapomněli?
[Hardison] Jo. V tomto smyslu, my jsme jen zapomenout je.
Pokud bychom byli ukládání kopií nich -
mnoho datových struktur se často ukládat své vlastní kopie prvků
tak, že osoba řídící datové struktury nemá na starosti
o tom, kde všechny ty ukazatele budou.
Datová struktura má na všechno, má na všech kopií,
aby se ujistil, že vše trvá přiměřeně.
Nicméně v tomto případě, tyto datové struktury jen pro jednoduchost
nejsou zhotovování kopií něco, co jsme ukládáním v nich.
[Student] Tak je to kontinuální pole -? Ano >>.
Pokud se podíváme zpět na to, co definice byla této struktury, je.
Je to jen standardní pole, jako když jste viděli,
pole * char s.
Znamená to, že -? >> Jo, jen jsem přemýšlel,
pokud budete nakonec dojdou paměti, do určité míry,
Máte-li všechny tyto prázdné místa ve vašem poli?
[Hardison] Jo, to je dobrá připomínka.
>> Podíváme-li se na to, co se stalo dnes v tomto bodě,
jsme zaplnila naše fronty, jak to vypadá.
Ale my jsme opravdu naplněna naše fronty
protože máme frontu, která má velikost 2, ale začíná na indexu 1,
protože to je místo, kde naše hlava je ukazatel.
Stejně jako jsi říkal, že prvek v řetězci [0], na indexu 0, je ve skutečnosti neexistuje.
Není to v naší frontě už.
Jen jsme se neobtěžoval jít a přepsat ho, když jsme dequeued to.
Takže i když to vypadá, že jsme k vyčerpání paměti, opravdu ne.
To místo je k dispozici pro nás používat.
Vhodné chování, pokud bychom měli vyzkoušet a první Dequeue něco
jako "bye", že by se pop bye off.
Nyní naše fronta začíná na indexu 2 a je o velikosti 1.
A teď, když se snažíme a Zařadí zase něco, řekněme 50,
50 by měla jít v tomto místě v indexu 0
protože je to stále k dispozici pro nás. Ano, Saad?
[Saad] Stává se to automaticky?
[Hardison] Nestává se zcela automaticky. Musíte si to spočítejte
aby to fungovalo, ale v podstatě to, co jsme udělali je, že jsme právě omotal kolem.
[Saad] A je to v pořádku, pokud to má díru uprostřed toho?
[Hardison] Je-li můžeme matematický fungovat správně.
>> A ukázalo se, že to vlastně není tak těžké udělat s mod operátora.
Tak jako jsme to udělali s Caesarem a další věci crypto,
pomocí mod, můžeme dělat věci zabalit kolem a jít dál
kolem a dokola a dokola s naší frontě,
vedení, které hlava ukazatel pohybuje.
Si všimnout, že velikost je vždy v počtu prvků ve skutečnosti v fronty.
A je to jen hlava ukazatel, který udržuje vystřídat.
Podíváme-li se na to, co se tady stalo, pokud bychom se vrátit na začátek,
a vy se jen dívat, co se děje na hlavu
když jsme Zařadí něco, nic se nestalo, aby na hlavě.
Když jsme ve frontě něco jiného, ​​nic se nestalo, aby na hlavě.
Hned jak jsme dequeued něco, hlava se zvedne o jednu.
My ve frontě něco, nic se nestane do hlavy.
Když jsme dequeue něco, hlava najednou dostane zvýšen.
Když jsme Zařadí něco, nic se nestane do hlavy.
>> Co by se stalo v tomto bodě, pokud bychom měli dequeue zase něco?
Jakékoliv myšlenky? Co by se stalo do hlavy?
Co by se mělo stát na hlavě
pokud bychom měli dequeue něco jiného?
Hlava teď je na indexu 2,
, což znamená, že hlava frontě řetězce [2].
[Student] Která vrací 0? Je >> by se měla vrátit do 0. To by zabalit zpět kolem, přesně.
Zatím pokaždé, když jsme říkali Dequeue, jsme byli přidání jednoho do hlavy,
přidat jeden do hlavy, přidat jeden do hlavy, přidat jeden do hlavy.
Jakmile že hlava ukazatel dostane na poslední index v našem poli,
pak musíme zabalit zpět k začátku, jít zpátky do 0.
[Charlotte] Co určuje kapacitu fronty v zásobníku?
[Hardison] V tomto případě, právě jsme používali # definovaný konstantní. Dobře >>.
[Hardison] V aktuální. Souboru c, můžete jít a špína se to trochu
a učinit z něj tak velký, nebo tak málo, jak chcete.
[Charlotte] Takže, když děláte to fronty, jak si udělat počítač vědět
jak velký chcete stack být?
[Hardison] To je velká otázka.
Existuje několik způsobů, jak. Jedním z nich je právě definovat dopředu
a říkají, že toto bude fronta, která má 4 prvky nebo 50 prvků nebo 10000.
Druhým způsobem je dělat to, co lidé hackerů vydání dělají
a vytvářet funkce, aby se vaše fronty dynamicky roste, protože stále více se věci zní a.
>> [Charlotte] Tak, aby šel s první možností, co syntaxe se používá
říci programu, co je velikost fronty?
[Hardison] Ah. Takže pojďme se dostat z toho.
Jsem stále v stack.c zde, tak jsem jen tak procházet až na vrchol zde.
Vidíte toto právo tady? To je # define kapacitu 10.
A to je téměř přesně stejné syntaxe, které máme k frontě.
Kromě ve frontě, máme extra struct pole zde.
[Charlotte] Oh, myslel jsem, že kapacita znamená kapacitu pro řetězce.
[Hardison] Ah. >> To, že je to maximální délka slova. >> Mám to.
Jo. Kapacita zde - to je skvělý bod.
A to je něco, co je složité
protože to, co jsme vykazovat zde je řada * char s.
Pole ukazatelů.
To je pole znaků.
To je asi to, co jste viděli, když jste prohlásil své vyrovnávací paměti pro soubor I / O,
když jste byli vytvoření řetězce ručně na zásobníku.
Avšak to, co tu máme, je řada char * s.
Takže je to pole ukazatelů.
Vlastně, když se přiblížíte ven a podíváme se na to, co se tady děje
v prezentaci, můžete vidět, že skutečné prvky, znaková data
není uložen v matici sám.
Co je uložena v našem poli zde jsou odkazy k charakteru dat.
Dobře. Takže jsme viděli, jak se velikost fronty je stejně jako u zásobníku,
velikost vždy dodrží počet prvků v současné době v řadě.
Po provedení 2 enqueues, velikost je 2.
Po provedení Dequeue velikost je nyní 1.
Po provedení další Zařadí velikost zpět na 2.
Takže velikost rozhodně dodrží počet prvků ve frontě,
a pak se hlava jen udržuje na kole.
To jde od 0-1-2, 0-1-2, 0-1-2.
A pokaždé, když říkáme Dequeue, dostane hlava ukazatel zvýšen na další index.
A v případě, že hlava je asi jít přes, to tvoří zpět kolem 0.
Takže s tím, my můžeme psát Dequeue funkci.
A budeme opustit Zařadí funkci pro vy realizovat místo.
>> Když jsme dequeue prvek z naší fronty,
Co byla první věc, která Daniel udělal, když jsme začali psát pop funkci pro komíny?
Nech mě slyšet od někoho, kdo se nemluví ještě.
Pojďme se podívat, Saad, pamatuješ si, co Daniel udělal jako první věc, když on psal pop?
[Saad] Tam byl, bylo to - >> Zkusil něco.
[Saad] Pokud je velikost větší než 0. Přesně >>.
A co to bylo testování?
[Saad] To bylo testování, jestli tam je něco uvnitř pole.
[Hardison] Jo. Přesně tak. Takže nemůžete pop nic z fronty, pokud je prázdná.
Stejně tak, nemůžete dequeue nic z fronty, pokud je prázdná.
Co je první věc, kterou bychom měli udělat v naší Dequeue funkci tady, myslíš?
[Saad] Pokud velikost je větší než 0? Jo >>.
V tomto případě, jsem vlastně jen testovány, zda je 0.
Pokud je 0, můžeme se vrátit null.
Ale přesně stejná logika.
A budeme pokračovat s tím.
Pokud je velikost není 0, kde je prvek, který chceme dequeue?
[Saad] V čele? Přesně >>.
Můžeme jen vytáhnout první prvek v naší frontě
přístupem prvek v čele.
Nic blázen.
Po tom, co bychom měli udělat? Co se musí stát?
Jaká byla další věc, která jsme si povídali o v Dequeue?
Dvě věci se stalo, protože naše fronta změnila.
[Daniel] Zmenšení velikosti. >> Máme pro snížení velikosti, a zvýšit hlavu? Přesně tak.
Chcete-li zvýšit hlavu, nemůžeme slepě zvýšit hlavu, vzpomenout.
Nemůžeme prostě queue.head + +.
Musíme také tento mod od kapacity.
A proč mod o kapacitu, Stella?
[Stella] Vzhledem k tomu, že má obtékat kolem. Přesně >>.
My mod o kapacitu, protože má zabalit zpět k 0.
Takže teď, v tomto okamžiku, můžeme udělat to, co řekl Daniel.
Můžeme decrement velikost.
A pak můžeme jen vrátit prvek, který byl v horní části fronty.
Vypadá to trochu drsný na prvním místě. Můžete mít otázku. Je nám líto?
>> [Sam] Proč to nejprve na začátek fronty? Pokud to jde?
[Hardison] Pochází ze čtvrté řady na dně.
Poté, co jsme testovat, aby se ujistil, že naše fronta není prázdná,
jsme vytáhnout char * Nejdříve jsme vytáhněte prvek, který sedí v čele indexu
našeho pole, z našeho řetězce pole, >> a volat, že první?
[Hardison] A říkáme, že jako první. Jo.
Stačí navázat na to, že důvod, proč si myslíte, že jsme to museli udělat, že?
[Sam] Každý první právě vrací q.strings [q.head]? Jo >>.
Vzhledem k tomu, >> děláme tato výměna q.head s mod funkcí,
a neexistuje žádný způsob, jak to udělat, aby v rámci zpětného line také.
[Hardison] Přesně tak. Jste na místě. Sam zcela na místě.
Důvod, proč jsme museli vytáhnout první prvek v našem frontě a uložit jej do proměnné
Je tomu tak proto tento řádek, kde jsme právě q.head,
je tu mod provozovatel tam není něco, co můžeme udělat,
a jsou to projeví na hlavě bez - v jedné linii.
Takže jsme vlastně muset vytáhnout první prvek, pak nastavte hlavu,
upravit velikost, a pak se vrátit na prvek, který jsme vytaženo.
A to je něco, co uvidíme přijít později
spojené seznamy, jak hrajeme si s nimi.
Často, když jste uvolnění nebo odstranění propojených seznamů
musíte mít na paměti další prvek, další ukazatel propojeného seznamu
Před likvidací té současné.
Protože jinak byste zahodit informace o tom, co zbylo v seznamu.
Nyní, když jdete do svého zařízení, můžete otevřít queue.c--x z toho.
Takže když jsem otevřít queue.c, dovolte mi, abych zoom sem,
uvidíte, že máte podobně vypadající soubor.
Podobné vypadající soubor na to, co jsme měli dříve s stack.c.
Máme naše struct pro frontu definovanou stejně jako jsme viděli na snímcích.
>> Máme Zařadí funkci, která je pro vás udělat.
A máme Dequeue funkci zde.
Dequeue funkce v souboru je implementováno,
ale já ji zpět až na PowerPoint, takže můžete zadat do, pokud budete chtít.
Takže pro dalších 5 minut nebo tak, vy pracovat na Zařadí
což je téměř pravým opakem Dequeue.
Nemusíte upravit hlavu, když jste enqueueing, ale to, co máte nastavit?
Velikost. Takže když enqueue, hlava zůstává nedotčený, dostane změní velikost.
Ale to se trochu - budete muset pohrát s tou mod
přijít na to, co přesně index nový prvek by měl být vložen na.
Takže ti dám si kluci trochu, dal dequeue zpátky na snímku,
a jak vy máte otázky, křičet ven tak, že můžeme
všichni mluví o nich jako o skupině.
Také, s velikosti ne - když upravíte velikost, můžete vždy jen -
máte k mod velikost vůbec? [Daniel] No >> Nemusíte se mod velikosti, vpravo.
Vzhledem k tomu, velikost bude vždy, pokud Jsi - za předpokladu, že jste správu věcí správně,
velikost bude vždy mezi 0 a 3.
Kde máte na mod, když děláte Zařadí?
[Student] Pouze pro hlavu. Pouze >> pro hlavu, přesně.
A proč máte na mod vůbec Zařadí?
Pokud je situace, ve které budete muset mod?
[Student] Pokud máte věci v mezerách, jako na prostor 1 a 2,
a pak třeba přidat něco na 0.
[Hardison] Jo, přesně tak. Takže pokud vaše hlava je ukazatel na samém konci,
nebo je-li vaše velikost a vaše hlava je větší, nebo spíše, bude obtékat kolem fronty.
>> Takže v této situaci, že jsme dostali tady na snímku právě teď,
když chci Zařadí něco hned teď,
chceme Zařadí něco na indexu 0.
Takže, když se podíváte na místo, kde 50 jde, a já říkám Zařadí 50,
to jde tam na dně. Jde v indexu 0.
To nahradí 'ahoj', která již byla dequeued.
[Daniel] Copak o to postará v Dequeue už?
Proč to dělat něco s hlavou v Zařadí?
[Hardison] Oh, takže nejste modifikovat hlavu, omlouvám se.
Ale musíte použít operátor modulo, když jste přístupu
prvek, který chcete Zařadí když jste přístupu
další prvek ve vašem frontě.
[Basil] Já jsem to neudělal, a já jsem dostal "úspěch" na tam.
[Daniel] Oh, jsem pochopil, co říkáte.
[Hardison] Takže didn't - jste právě udělal na q.size?
[Basil] Jo. Právě jsem změnil strany, neudělal jsem nic s hlavou.
[Hardison] Nemusíte vlastně muset resetovat hlavu za něco,
ale když se index do řetězce pole,
máte skutečně jít dopředu a vypočítat, kde další prvek je,
protože proutí zásobníku, další prvek ve vašem zásobníku byl vždy
na indexu odpovídající velikosti.
Podíváme-li se zpátky na naší funkci zásobníku tlačítkem,
můžeme vždy plonk v našem novém prvku přímo na indexu velikosti.
Vzhledem k tomu, s fronty, to nemůžeme udělat, že
protože pokud jsme na tuto situaci,
pokud budeme ve frontě 50 naše nová řetězec by jít přímo na struny [1]
které nechceme dělat.
Chceme mít nový řetězec jít na indexu 0.
>> Má někdo - ano? [Student] Mám otázku, ale to opravdu není příbuzný.
Co to znamená, když někdo prostě zavolá něco jako Pred ukazatel?
Co je to za jméno zkratka pro? Vím, že je to jen jméno.
[Hardison] Pred ukazatel? Pojďme se podívat,. V jaké souvislosti?
[Student] To bylo pro vložku. Mohu vás požádat později, pokud budete chtít
protože to není opravdu souvisí, ale já jsem prostě -
[Hardison] Od vlož kód Davida z přednášky?
Můžeme vytáhnout, že a mluvit o tom.
Budeme o tom mluvit dál, jakmile se dostaneme do propojených seznamů.
>> Takže to opravdu rychle podívat na to, co enqueue funkce vypadá.
Jaká byla první věc, že ​​lidé se snažil udělat v Zařadí řadě? Do této fronty?
Podobně jako to, co jste udělal pro zásobníku tlačí.
Co jsi udělal, Stella?
[Stella, nesrozumitelným]
[Hardison] Přesně tak. Pokud (q.size == KAPACITY) -
Musím dát své závorky na správném místě - vrátí false.
Zvětšit trochu. Dobře.
Teď, co je další věc, že ​​jsme museli udělat?
Stejně jako u zásobníku, a vloží na správném místě.
A tak to, co bylo tím pravým místem pro vložení že?
S zásobníku bylo index velikosti, s tím, že to není tak.
[Daniel] Mám q.head--nebo - >> q.strings? >> Jo.
q.strings [q.head + q.size mod KAPACITA]?
[Hardison] jsme pravděpodobně chtít, aby závorek tento
tak, že jsme získali příslušnou přednost, a tak to cleart všem.
A nastavit, aby stejné? Chcete-li >> str? Chcete-li >> str. Great.
A teď, co je to poslední věc, kterou musíme udělat?
Stejně jako jsme to dělali v zásobníku. Přírůstek >> velikost? Přírůstek >> velikosti.
Boom. A pak, protože startovací kódu se právě vrátil false ve výchozím nastavení,
chceme změnit na hodnotu true, pokud vše půjde až do konce a je vše v pořádku.
Dobrá. To je hodně informací o oddílu.
Nejsme zcela u konce. Chceme mluvit opravdu rychle o singly propojených seznamů.
Dám to tak můžeme vrátit se k němu později.
Ale pojďme zpět k naší prezentaci za pár více snímků.
Takže enqueue je TODO, teď jsme to.
>> Nyní se pojďme podívat na singly propojených seznamů.
Mluvili jsme o nich trochu víc v přednášce.
Kolik z vás viděl demo, kde jsme měli lidi
neobratně ukázal na sebe a držení čísla? >> Byl jsem v tom.
>> Co vy na to? Bylo to, doufejme, že demystifikovat tyto trochu?
S seznamu, se ukazuje, že se zabýváme tohoto typu, který budeme nazývat uzel.
Vzhledem k tomu, s fronty a zásobníku jsme měli structs, že bychom hovorovou frontu v zásobníku,
jsme měli tyto nové fronty v zásobníku typů,
Zde je seznam opravdu jen skládá banda uzlů.
Stejným způsobem, že řetězce jsou jen banda znaků všech seřazených vedle sebe.
Spojový seznam je jen uzel a další uzel a další uzel a jiný uzel.
A spíše než rozbíjet všechny uzly dohromady a jejich uložení souvisle
všechny přímo vedle sebe v paměti,
má tuto další ukazatel nám umožňuje ukládat uzly Kdykoli je to, v náhodném pořadí.
A pak druh drátu je všechny dohromady bodu od jednoho k druhému.
>> A co bylo velkou výhodou, že to mělo přes pole?
Přes ukládání všeho souvisle jen přilepená vedle sebe?
Pamatuješ si? Jo? >> Dynamické přidělování paměti?
>> Dynamické přidělování paměti, v jakém smyslu?
[Student] V tomto můžete mít takže je větší a nemusíte se pohybovat celou řadu?
[Hardison] Přesně tak. Takže s pole, pokud chcete, aby nový prvek do středu,
budete muset přesunout vše proto, aby prostor.
A jak jsme si povídala s fronty,
to je důvod, proč jsme udržet, že hlava ukazatel,
tak, že nejsme neustále mění věci.
Vzhledem k tomu, že se dostane drahé, pokud máte velkou pole
a jste neustále dělat tyto náhodné vložení.
Vzhledem k tomu, s přehledem, vše, co musíte udělat, je hodit to na nový uzel,
nastavit ukazatele, a máte hotovo.
Co naštve o to?
Kromě skutečnosti, že je to není tak jednoduché pracovat jako s polem? Jo?
[Daniel] No, myslím, že je to mnohem těžší přístup specifický prvek v připojeném seznamu?
[Hardison] Nemůžeš jen tak skočit do libovolného prvku v polovině svého propojeného seznamu.
Jak se vám to muset udělat místo? >> Musíte krok celou věc.
[Hardison] Jo. Musíte projít jeden po druhém, jeden po druhém.
Je to obrovská - to je bolest.
Co je to druhé - je tu další pád na to.
[Basil] Nemůžete jít dopředu a dozadu? Musíte jít jedním směrem?
[Hardison] Jo. Tak jak to budeme řešit, že někdy?
[Basil] Dvakrát-propojených seznamů? Přesně >>. K dispozici jsou dvojnásobně propojené seznamy.
Tam jsou také - sorry?
>> [Sam] Je to stejné jako s použitím PRED věc, že ​​-
Právě jsem si vzpomněla, není to, co pred věc je?
Není to mezi dvojnásobně a singly?
[Hardison] Pojďme se podívat na to, co přesně dělá.
Tak jdeme na to. Zde je seznam kódu.
Zde máme predptr, tady. Je to to, co jsi mluvil?
Takže to byl - on osvobození seznam a snaží se uložit ukazatel na ni.
To není o dvojnásob, jednotlivě propojené-listy.
Můžeme mluvit více o tom později, protože to se mluví o uvolnění seznam
a chci ukázat některé další věci jako první.
ale je to jen - je to pamatovat hodnotu PTR
[Student] Oh, to je předcházejících ukazatel? Jo >>.
Takže pak můžeme zvýšit PTR sám předtím, než jsme pak zdarma to, co predptr je.
Protože nemůžeme bez ptr a pak volat ptr = ptr další, ne?
To by bylo špatné.
Tak uvidíme, zpět na toho chlapa.
>> Další špatná věc, o seznamech je, že vzhledem k tomu, s řadou
budeme muset všechny prvky samy o sobě naskládané vedle sebe,
Zde jsme také zavedli tento ukazatel.
Takže je tu další kus paměti, že jsme museli použít
pro každý prvek, který jsme uskladnění v našem seznamu.
Dostaneme pružnost, ale to přijde v ceně.
Dodává se s tímto časovým náklady,
a je dodáván s tímto paměťovým náklady příliš.
Čas v tom smyslu, že nyní musíme projít každý prvek v poli
najít ten u indexu 10, nebo že by byli index 10 v poli.
>> Jen opravdu rychle, když jsme diagram z těchto seznamů,
obvykle se držet na hlavě seznamu nebo první ukazatel seznamu
a vědomí, že to je pravda, ukazatel.
Je to jen 4 bajty. Není to skutečný uzel sám.
Takže vidíte, že to nemá žádnou hodnotu int v tom, žádný další ukazatel v něm.
Je to doslova jen ukazatel.
Bude to upozornit na něco, co je skutečné uzel struct.
[Sam] Ukazatel nazývá uzel? >> To je - není. To je ukazatel na něco typu uzlu.
Je ukazatel na uzlu struct. >> Oh, dobře.
Diagram vlevo, kódu napravo.
Můžeme nastavit na null, což je dobrý způsob, jak začít.
Když diagram, ty buď napsat, že za neplatné, nebo si dát čáru přes to takhle.
>> Jedním z nejjednodušších způsobů, jak pracovat se seznamy,
a žádáme vás, že i předřadit a připojit vidět rozdíly mezi těmito dvěma,
ale předřadí je rozhodně jednodušší.
Když začátek řádku, to je místo, kde si - když prepend (7),
jdete a vytvořit uzlu struct
a nastavit první poukázat na to, protože teď, protože jsme prepended to,
to bude na začátku seznamu.
Pokud se předřazeného (3), která vytváří další uzel, ale nyní 3 přichází do 7..
Takže jsme v podstatě tlačí věci do našeho seznamu.
Nyní můžete vidět, že prepend, někdy lidé říkají, že tlačit,
proto, že jste tlačí nový prvek do seznamu.
Je také snadné odstranit v čele seznamu.
Takže lidé budou často volají, že pop.
A tímto způsobem, lze emulovat balík pomocí spojového seznamu.
Jejda. Je nám líto, teď se dostáváme do append. Takže tady máme prepended (7), nyní jsme prepend (3).
Pokud bychom prepended něco jiného na tomto seznamu, pokud bychom prepended (4),
pak budeme mít 4 a pak 3 a pak 7.
Takže pak bychom mohli pop a odstranit 4, odstranit 3, odstraňte 7.
Často více intuitivní způsob, jak přemýšlet o tom to je s append.
Takže jsem diagramu, co by to vypadalo s připojit zde.
Zde připojen (7) nemá vypadat jinak
protože tam je jen jeden prvek v seznamu.
A připojením (3) vloží to na konci.
Možná si můžete prohlédnout hned teď trik s append
je, že od té doby jsme jen vědět, kde na začátku seznamu je,
připojit do seznamu musíte projít celou cestu v seznamu
se dostat do konce, zastavte, a pak budovat svůj uzel a plonk všechno dolů.
Zapojte všechny věci nahoru.
Takže s Prepend, jak jsme právě projela to opravdu rychle,
když předřadit do seznamu, je to poměrně jednoduché.
>> Uděláte si nový uzel, zahrnovat některé dynamické přidělování paměti.
Takže tady děláme uzlu struct pomocí malloc.
Takže malloc jsme použili proto, že to zrušil paměť pro nás pro pozdější
protože nechceme, aby to - chceme, aby tento paměti přetrvávat po dlouhou dobu.
A my jsme si ukazatel na místo v paměti, že jsme právě přidělené.
Používáme velikosti uzlu, nemáme sečíst pole.
Nechceme ručně generovat počet bajtů,
místo toho jsme použít sizeof, takže víme, že získání odpovídající počet bajtů.
Snažíme se o to, aby testování, že naše malloc volání bylo úspěšné.
To je něco, co chcete dělat v obecně.
Na moderních strojích, vyčerpání paměti není něco, co je snadné
pokud jste přidělení spoustu věcí a dělat obrovský seznam,
ale pokud stavíte věci pro, řekněme, jako iPhone nebo Android,
nemáte mají omezené prostředky paměti, zvláště pokud děláte něco intenzivní.
Takže je to dobré se dostat do praxe.
>> Všimněte si, že jsem použil několik různých funkcí zde
, když jste viděli, že jsou trochu nové.
Takže fprintf je stejně jako printf
kromě svého prvního argumentu je potok, který chcete vytisknout.
V tomto případě, že chceme vytisknout na standardní chybový řetězec
, který je odlišný od standardního outstream.
Implicitně se objeví na stejném místě.
To také vytiskne na terminál, ale můžete -
použití těchto příkazů jste se dozvěděli o tom, o přesměrování techniky
jste se dozvěděli o ve videu Tommyho pro problémové sadu 4, můžete nasměrovat ji
do různých oblastí, pak ukončete, tady, ukončí svůj program.
Je to v podstatě jako návrat z hlavní,
kromě používáme výjezd, protože zde návrat nebude dělat nic.
Nejsme v hlavní, tak vrací neukončí program, jako chceme.
Tak jsme se použít funkci ukončení a dát mu chybový kód.
Pak zde máme nastaven nový uzel hodnotového pole, jeho i pole se rovná i, a pak jsme zapojte ho.
Vydali jsme nový uzel je další ukazatel aby ukazoval na první,
a pak první budou nyní na tento nový uzel.
Tyto první řádky kódu, jsme vlastně stavět nový uzel.
Ne poslední dva řádky této funkce, ale ty první.
Můžete si skutečně vytáhnout do funkce, do pomocnou funkci.
To je často to, co dělám je, že jsem ji vytáhnout do funkce,
Říkám to něco jako uzel sestavení,
a že udržuje prepend funkce docela malá, je to jen 3 řádky pak.
I volat na mé funkce uzlu sestavení, a pak jsem drát všechno nahoru.
>> Poslední věc, já vám chci ukázat,
a nechám tě udělat append a to všechno na vlastní pěst,
je, jak iterovat přes seznam.
Existuje spoustu různých způsobů, jak přecházet přes seznam.
V tomto případě se budeme najít délku seznamu.
Takže začneme s délkou = 0.
To je velmi podobné psaní strlen pro řetězec.
To je to, co chci ukázat, to pro smyčku tady.
Vypadá to trochu funky, to není obvyklé int i = 0, i <cokoliv, i + +.
Místo toho je to inicializace naši proměnnou n být začátek seznamu.
A pak, když naše iterator proměnná není null, budeme pokračovat.
To je proto, že podle konvence, bude konec našeho seznamu je null.
A pak přírůstek, spíše než dělat + +,
spojový seznam ekvivalent + + je n = n-> další.
>> Dám vám vyplnit mezery zde, protože jsme mimo čas.
Ale mějte na paměti, až budete pracovat na svých spellr psets.
Propojené seznamy, pokud jste provádění hash tabulky,
určitě přijde velmi vhod.
A má tento idiom pro smyčce nad věcí bude život mnohem jednodušší, snad.
Jakékoliv dotazy, rychle?
[Sam] Budete posílat vyplněný SLL a sc?
[Hardison] Jo. Budu posílat vyplněné diapozitivů a vyplněný SLL stoh a queue.cs.
[CS50.TV]