[Přehrávání hudby]
SPEAKER 1: V pořádku.
Všichni vítejte zpět do kategorie.
Doufám, že jste všichni úspěšně zpět z vašeho testu
z minulého týdne.
Vím, že je trochu blázen občas.
Jak jsem říkal předtím, pokud jste v rámci směrodatné odchylky,
nemáte opravdu starat o to, a to zejména pro méně pohodlné úseku.
To je o tom, kde byste měli být.
>> Pokud jste si skvěle, pak úžasné.
Sláva tobě.
A pokud máte pocit, že musíte trochu více pomoci, prosím
neváhejte oslovit z některého z TFS.
Všichni jsme tady na pomoc.
>> To je důvod, proč jsme se učit.
To je důvod, proč jsem tady každé pondělí pro vás kluci a v kanceláři hodin ve čtvrtek.
Tak neváhejte a dejte mi vědět, Pokud máte obavy o ničem
nebo v případě, že je něco v kvízu že byste opravdu chtěli řešit.
>> Takže agenda pro dnešek je vše o datových struktur.
Některé z nich jsou prostě bude jen aby se vám seznámil s těmito.
Nesmíte nikdy realizovat je v této třídě.
Některé z nich si vyzkoušíte, jako pro pravopisu pset.
>> Budete mít svůj výběr mezi stoly mřížky a pokusů.
Takže jsme určitě jít přes ty.
Bude to mít rozhodně více druhů vysoké úrovni úseku dnes, i když,
protože existuje mnoho z nich, a pokud jsme šli do podrobností implementace
na všech z nich, nebyli bychom dokonce projít spojových seznamů
a možná trochu hash tabulky.
>> Takže mějte se mnou.
Nebudeme se dělá až kódování tentokrát.
Máte-li nějaké otázky o tom nebo chcete-li vidět, že realizovat
nebo se pokusit si to pro sebe, Určitě doporučuji
bude study.cs50.net, které má příklady všech z nich.
To bude mít své powerpoints s poznámkami, které jsme
mají tendenci používat i trochou programování cvičení, především na věci,
jako propojených seznamů a binární stromy komíny a narážky.
Tak trochu na vysoké úrovni, které by mohlo být pěkné pro vás.
>> Takže s tím, budeme začít.
A také, yes-- kvízy.
Myslím si, že většina z vás, kteří jsou v moje část má své kvízy,
ale každý, kdo přijde, nebo z nějakého důvodu ne, jsou tady v přední části.
>> Tak spojových seznamů.
Vím, že tento druh jde zálohovat před kvíz.
To bylo před týdnem že jsme se dozvěděli o tom.
Ale v tomto případě, budeme jen jít trochu více do hloubky.
>> Tak proč bychom mohli vybrat spojový seznam přes pole?
Co je odlišuje?
Ano?
>> Diváků: můžete též rozšířit spojené Seznam oproti Array pevnou velikost.
SPEAKER 1: Správně.
Pole má pevnou velikost vzhledem k tomu, spojový seznam má proměnnou velikost.
Takže pokud nevíme, jak moc chceme uložit,
spojový seznam nám dává velký způsob, jak to udělat, protože my můžeme jen
přidat na jiném uzlu a přidat na jiný uzel a přidat na jiném uzlu.
Ale to, co by mohlo být trade-off?
Pamatuje si někdo na trade-off mezi poli a spojových seznamů?
Mmhmm?
>> Diváků: Musíte projít celou cestu
prostřednictvím propojeného seznamu najít prvek v seznamu.
V poli, můžete jen najít prvek.
>> SPEAKER 1: Správně.
Tak s arrays--
>> Diváků: [neslyšitelné].
>> SPEAKER 1: S polem, máme co se nazývá náhodný přístup.
Znamená to, že pokud chceme, aby to, co je někdy pátý bod seznamu
nebo pátý bod našeho pole, můžeme jen chytit ji.
Pokud je to spojový seznam, máme iterovat, že jo?
Tak přístup k prvku v pole je konstantní čas,
zatímco v propojeném seznamu, že by s největší pravděpodobností bude lineární čas, protože možná
naše prvkem je úplně na konci.
Musíme prohledat všechno.
Takže se všemi těmito údaji struktury pojedeme
se strávit trochu více času na, Jaké jsou plusy a zápory.
Když bychom mohli chtít použijte jeden přes druhého?
A to je druh větší věc odnést.
>> Takže máme tady definice uzlu.
Je to jako jeden prvek v náš spojový seznam, ne?
Takže jsme všichni obeznámeni s našimi typedef structs,
které jsme přešli v recenzi naposledy.
Bylo to v podstatě jen vytvořením jiný datový typ, který bychom mohli použít.
>> A v tomto případě, je to nějaký uzel že bude mít nějaké číslo v.
A co pak je druhá část tady?
Každý, kdo?
>> Diváků: [neslyšitelné].
>> SPEAKER 1: Jo.
Je to ukazatel na další uzel.
Takže by to mělo být skutečně tady.
To je ukazatel typu uzlu na další věc.
A to je to, co zahrnuje náš uzel.
V pohodě.
>> Dobře, tak s hledáním, jak jsme byli jen říkám, do ruky, pokud jste
bude prohledávat, Máte skutečně iterovat
prostřednictvím propojeného seznamu.
Takže pokud se díváme na počet 9 bychom začít na naší hlavě
a že nás upozorňuje na začátku našeho propojeného seznamu, ne?
A my říkáme, OK, to dělá uzel obsahovat číslo 9?
Ne?
>> V pořádku, přejděte na další jeden.
Následujte ho.
Má obsahovat číslo 9?
Ne.
Sledujte další.
>> Takže máme skutečně iterovat prostřednictvím naší propojeného seznamu.
Nemůžeme prostě jít přímo na místo, kde 9.
A pokud vy vlastně chcete vidět nějaký pseudo-kódu tam nahoře.
Máme nějakou funkci vyhledávání zde který bere in-- co to přijmout?
Co si myslíte?
Tak snadné.
Co je to?
Diváků: [neslyšitelné].
SPEAKER 1: Počet hledáme.
Je to tak?
A co by to odpovídat?
Je to ukazatel?
>> Diváků: uzel.
>> SPEAKER 1: uzel do seznamu že se díváme, je to tak?
Takže máme některé uzly jsou ukazatel zde.
To je bod, který se bude vlastně iterovat našem seznamu.
Vydali jsme se rovná seznam protože to je to
Nastavení je rovno spuštění našeho propojeného seznamu.
>> A i když to není NULL, zatímco stále máme věci v našem seznamu,
zkontrolujte, zda tento uzel má počet hledáme.
Return true.
V opačném případě, aktualizovat, ne?
>> Pokud je NULL, my ukončit naše while a return false
protože to znamená, že jsme se našli.
Má každý si, jak to funguje?
OK.
>> Tak s vložení, budete mají tři různé způsoby.
Můžete předřadit, můžete připojit a můžete vložit do roztříděný.
V tomto případě jsme dělat předřazeným.
Ví někdo, jak ty, tři případů může lišit?
>> Tak prepend znamená, že můžete dát je v přední části vašeho seznamu.
Takže by znamenalo, že bez ohledu na jaké jsou vaše uzel je, bez ohledu na to,
co je hodnota, budete aby to tady vpředu, OK?
Bude to první prvek v seznamu.
>> Pokud jej připojit, bude to jít na zadní části vašeho seznamu.
A vložit do nejrůznějších znamená, že jste dám skutečně do místa
kde se udržuje spojový seznam seřazen.
Opět, jak použít ty, a při použití
jim bude lišit v závislosti na vašem případě.
Pokud to není nutné, aby třídit, prepend inklinuje
být to, co si většina lidí použít, protože nemáte
musí projít celý seznam najít konec přidejte ji, ne?
Stačí si jen držet ji přímo.
>> Tak jsme se projít Vložení 1 právě teď.
Takže jedna věc, kterou budu Vřele doporučuji na tomto pset
je k tomu věci, jako vždy.
Je velmi důležité, abyste aktualizovat Vaše ukazatele ve správném pořadí
protože pokud je aktualizovat trochu mimo provoz,
budete skončit ztrátě části seznamu.
>> Tak například, v tomto případě jsme říká šéf jen bod 1.
Pokud se nám prostě, že bez uložení této 1,
nemáme ponětí, co 1 by měly směřovat do současnosti
proto, že jsme ztratili to, co hlavy ukázal na.
Takže jedna věc k zapamatování když děláte předřazeným
je zachránit to, co se hlava ukazuje na první,
pak přiřadit, a pak aktualizovat co váš nový uzel by měl ukazovat na.
V tomto případě, je to jediný způsob, jak to udělat.
>> Takže pokud jsme udělali to takhle kde jsme právě převelen hlavu,
ztrácíme v podstatě dotazy Celý seznam, jo?
Jeden způsob, jak to udělat, je mít 1 bod další, a pak si hlavu bod 1.
Nebo si můžete udělat něco jako dočasné uskladnění, což jsem mluvil o.
>> Ale přiřazení vlastní jméno ukazatele ve správném pořadí
bude velmi, velmi důležité, aby tento pset.
V opačném případě budete mít hash tabulky nebo pokus, který je jen bude
pouze část slova, které jste chtějí, a pak you're-- mmhmm?
Diváků: Jaký byl dočasný skladování věc, kterou mluvili?
SPEAKER 1: dočasné uskladnění.
Takže v podstatě další způsob, jak by to mohlo dělat
je uložit hlavu něčeho, jako je uložit mu dočasné proměnné.
Přiřadit ji na hodnotu 1 a aktualizovat 1 bod
na co hlava používá poukázat na.
Tímto způsobem je samozřejmě více elegantní, protože vás
Nemusíte dočasnou hodnotu, ale jen nabízí jiný způsob, jak to udělat.
A my vlastně mají nějaký kód na to.
Takže pro spojový seznam, jsme skutečně nějaký kód.
Tak Sem vložte, je to prepending.
Takže to zadá v čele.
>> Takže první věc, kterou musíte vytvořit nový uzel, samozřejmě,
a zkontrolujte, zda NULL.
Vždy dobré.
A pak je třeba přiřadit hodnoty.
Vždy, když vytvoříte nový uzel, vás Nevím, co to ukazuje na další,
takže chcete inicializovat na hodnotu NULL.
Pokud to skončí ukázal na něco, co jiného, ​​dostane přidělen a je to v pořádku.
Pokud je to první věc, v seznamu, je třeba
poukázat na NULL, protože to je konec seznamu.
>> Tak to vložit, vidíme tady se přiřadí další hodnotu naší uzlu
být co hlava, což je to, co jsme tady měli.
To je to, co jsme právě udělali.
A pak jsme přiřazení hlavy až k bodu našeho nového uzlu, protože nezapomeňte,
Nová je nějaký ukazatel na uzel, a to je přesně to, co hlava.
To je přesně důvod, proč jsme tuto šipku přístupový.
V pohodě?
Mmhmm?
>> Diváků: Musíme inicializovat novou Další NULL jako první,
nebo můžeme jen inicializovat na hlavu?
>> SPEAKER 1: New další musí být NULL začít
protože nevíte, kde to bude.
Také tento druh je stejně jako paradigma.
Můžete nastavit ji na hodnotu NULL, jen aby Ujistěte se, že všechny vaše základny jsou pokryty
než tak učiníte, že jakékoliv přeřazení jste vždy zaručeno, že to bude
ukazovat na konkrétní hodnotu proti jako hodnotu odpadky.
Vzhledem k tomu, jo, přiřadíme nové další automaticky,
ale je to více, stejně jako dobré praxe k inicializaci
tímto způsobem a pak přiřadit.
>> OK, tak dvojnásob spojových seznamů teď.
Co si myslíme?
To, co je s dvojnásobně spojené seznamy?
>> Takže v našich spojových seznamů, můžeme pohybovat pouze v jednom směru, ne?
Máme jen dál.
Můžeme jít jen dopředu.
>> S dvojnásobně spojový seznam, můžeme také přesunout zpět.
Takže máme nejen Číslo, které chceme uložit,
máme tam, kde poukazuje na další a tam, kde jsme právě přišli.
Takže to umožňuje některé lepší průchod.
>> Tak dvojnásobně spojené uzly, velmi podobné, ne?
Jediným rozdílem je teď mají další a předchozí.
To je jediný rozdíl.
>> Takže pokud bychom měli předřadit nebo append-- jsme nemají žádný kód pro tento up here--
ale pokud jste byli, aby se pokusila vložte ji na důležitou věc
je třeba, aby že jste přiřazení
jak vaše předchozí a vaše další ukazatel správně.
Takže v tomto případě byste nejen inicializovat další,
inicializaci předchozí.
Pokud jsme v čele seznamu jsme by hlava rovná nové nejen,
ale náš nový předchozí měl poukazují na hlavu, ne?
>> To je jediný rozdíl.
A pokud budete chtít více praxe s je s spojových seznamů, s vložením,
s mazáním, s vložkou do tříděného seznamu
prosím, podívejte se study.cs50.net.
Je tu spousta skvělých cvičení.
Vřele doporučuji je.
Přál bych si, abychom měli čas jít přes ně ale je tu spousta datových struktur
projít.
>> OK, tak hash tabulky.
Toto je pravděpodobně nejvíce užitečné bit pro pset
tady, protože budete mít realizaci jednoho z nich, nebo zkusit.
Moc se mi líbí hash tabulky.
Jsou to docela v pohodě.
>> Takže v podstatě to, co se stane, je hash tabulka
je, když opravdu potřebujete rychlé vkládání, mazání a vyhledávání.
To jsou věci, které jsme priorit v hash tabulce.
Mohou se dostat docela velký, ale jak uvidíme se pokusech,
tam jsou věci, které jsou mnohem větší.
>> Ale v podstatě, všechny hash Tabulka je hašovací funkce
že vám řekne, které kbelík, aby každý vašich dat, každý z vašich prvků.
Jednoduchý způsob, jak myslet na hash tabulky je, že je to jen kbelíky věcí,
že jo?
Takže když se třídění věcí podle stejně jako první písmeno svého jména,
to je něco jako hash tabulky.
>> Takže vy, kdybych skupiny je do skupin, kdo začíná jméno
se tady, nebo ten, kdo má narozeniny v lednu, únoru, březnu,
co, že je účinně vytvoření hash tabulky.
Je to jen vytváření kbelíky, že můžete třídit elementy do
takže si můžete najít je jednodušší.
Takže tímto způsobem, když jsem služeb najít jeden z vás,
Nemám na vyhledávání přes každého z vašich jmen.
Můžu být rád, oh, já vím, že Danielle má narozeniny in--
Diváků: --April.
Reproduktor 1: duben.
Tak jsem se podívat do mého duben kbelík, a s trochou štěstí
že bude pouze jeden tam a můj čas byl konstantní v tom smyslu,
vzhledem k tomu, když jsem se podívat přes spoustu lidí,
že to bude trvat mnohem déle.
Takže hash tabulky jsou opravdu jen lopaty.
Snadný způsob, jak si o nich myslíte.
>> Takže velmi důležitá věc, o hash tabulka je hašovací funkce.
Takže věci, které jsem právě mluvil, jako vaše první písmeno vašeho jména
nebo vaše narozeniny měsíc jsou to myšlenky, které
Opravdu korelaci s hashovací funkce.
Je to jen způsob, jak rozhodnout, které vědro Jsi element jde do, OK?
Takže pro tento pset, můžete se podívat na skoro žádné funkce hash chcete.
>> Nemusí to být vaše vlastní.
Tam jsou některé z nich opravdu cool out tam, že dělat všechny druhy bláznivé matematiky.
A pokud chcete, aby se vaše Kontrola pravopisu super rychlý,
Já bych určitě podívejte se do jedné z nich.
>> Ale jsou tu i jednoduchých, jako je výpočetně
součet slov, jako je každé písmeno má číslo.
Vypočtěte součet.
Který určuje kbelík.
Mají také ty jednoduché, že jsou stejně jako všechny je tady,
všechny B je tady.
Každý jeden z nich.
>> V podstatě je to jen vám řekne, které index pole Váš element by měl jít do.
Jen rozhodování o bucket-- je to všechno funkce hash.
Takže tady máme příklad, který je jen první písmeno řetězce
že jsem právě mluvil.
>> Takže máte nějaké hash, který je právě první písmeno vašeho řetězce minus,
která vám dá některé číslo mezi 0 a 25.
A to, co chcete udělat, je ujistěte se, že se jedná
velikost vašeho hash table-- kolik kbelíky jsou.
S mnoha z nich hashovací funkce, jsou
bude vracet hodnoty, které by mohly je daleko vyšší než počet segmentů
že jste skutečně v hash tabulce,
proto je třeba, aby Ujistěte se, a mod ti.
V opačném případě to bude říkat, oh, měl by být v kbelíku 5000
ale máte jen 30 kbelíky ve vašem hash tabulky.
A samozřejmě, všichni víme, že je to bude mít za následek v některých šílených chyb.
Takže se ujistěte, mod od Velikost vašeho hash tabulky.
V pohodě.
Tak kolizí.
Je každý dobrý tak daleko?
Mmhmm?
>> Diváků: Proč by to vrátit se tak masivní hodnotu?
>> SPEAKER 1: V závislosti na algoritmu že hash funkce využívá.
Některé z nich budou dělat blázen násobení.
A to je vše, jak dostat rovnoměrné rozdělení,
tak to dělají některé opravdu bláznivé věci, někdy.
To je všechno.
Ještě něco?
OK.
>> Tak kolizí.
V podstatě, jak jsem již řekl, v nejlepším případě,
jakýkoliv kbelík se dívám do je bude mít jednu věc,
takže nemám dívat na všechny, že jo?
Já vím, že buď tam, nebo je to ne, a to je to, co opravdu chceme.
Ale máme-li desítky tisíc datových bodů a méně než tento počet
lopat, budeme mít kolize, kde nakonec něco
bude muset skončit v kbelík, který již má prvek.
>> Takže otázka je, co budeme dělat v tomto případě?
Co budeme dělat?
Už jsme tam něco mít?
Máme jen vyhodit?
>> Ne.
Musíme mít na obou z nich.
Tak tak, že jsme obvykle to udělat je to, co?
Co je datová struktura jsme právě mluvili?
Diváků: spojový seznam.
SPEAKER 1: spojový seznam.
Takže teď, místo toho, každá z nich kbelíky jen mít jeden prvek,
to bude obsahovat propojený seznam prvky, které byly zatříděna do něj.
OK, to každý druh si tuto myšlenku?
Protože jsme nemohli mít pole protože nevíme, jak mnoho věcí,
se bude tam.
Spojový seznam nám umožňuje máme jen přesný počet, který
jsou zatříděna do tohoto kbelíku, ne?
>> Takže lineární sondování je v podstatě to idea--
to je jeden způsob, jak se vypořádat s bočním nárazu.
Co můžete udělat, je, pokud v tomto případ, bobulové byla zatříděna do 1
a už máme něco, co tam prostě
dál, dokud najdete na prázdnou pozici.
To je jediný způsob, jak s ní zacházet.
Druhý způsob, jak zvládnout je to s tím, co jsme právě
called-- spojené seznam se nazývá zřetězení.
>> Takže tato myšlenka funguje, pokud vaše hash tabulky si myslíte
je mnohem větší, než Vaše údaje nastavit nebo pokud vás
zkusit a minimalizovat řetězení dokud je to nezbytně nutné.
Takže jedna věc je lineární sondování samozřejmě znamená,
že vaše hash funkce není tak užitečný
protože budete skončit s použitím vaše hash funkce, dostat do bodu,
jste LINEAR sondy až do nějaké místo, které je k dispozici.
Ale teď, samozřejmě, cokoliv jiný, že skončí tam,
budete muset hledat ještě dál.
>> A je tu mnohem víc Hledání náklady, které
jde do zadání prvek v hash tabulce, ne?
A teď, když jdete a pokusit se najít berry znovu, budete to hash,
a to bude říkat, oh, podívejte se do kbelíku 1,
a to nebude v kbelíku 1, takže jste
bude muset projít přes zbytek z nich.
Tak to je někdy užitečná, ale ve většině případů,
budeme říkat, že řetězení je to, co chcete dělat.
>> Tak jsme o tom mluvili dříve.
Dostal jsem kousek před sebe.
Ale řetězení je v podstatě, že každý kbelík v hash tabulce
je jen spojový seznam.
>> Takže další způsob, nebo více technických způsobem, myslet na hash tabulky
je to, že je to jen pole spojových seznamů, které
když jste psaní slovník a vy se snažíte načíst,
myslet na to, jak pole spojových seznamů
bude to mnohem jednodušší pro vás inicializovat.
>> Diváků: Tak hash tabulka má předem určenou velikost,
jako [neslyšitelné] lopat?
>> SPEAKER 1: Správně.
Tak to má stanovený počet kbelíky, že jste determine--
které jste kluci měli klidně hrát.
To může být docela v pohodě aby viděli, co se stane,
jak si změnit počet segmentů.
Ale jo, to má nastavit počet segmentů.
Co umožňuje, aby se vešly jako mnoho prvků, jak budete potřebovat
je oddělen řetězení, kde vás spojili seznamy v každém segmentu.
To znamená, že vaše hash tabulky bude přesně velikost
že ji musí být, ne?
To je celý smysl spojových seznamů.
V pohodě.
>> Takže tam všichni v pořádku?
Dobrá.
Ah.
Co se stalo?
Opravdu teď.
Hádejte, někdo mě zabíjí.
>> OK budeme jít do pokusů, které jsou trochu blázen.
Mám rád hash tabulky.
Myslím, že jsou opravdu cool.
Pokusy jsou v pohodě, taky.
>> Takže má někdo vzpomenout, co to zkusit je?
Měli jste přešli stručně v přednášce?
Vzpomínáte si druh, jak to funguje?
Diváků: Jen jsem kývl že jsme se jít přes něj.
SPEAKER 1: Nemáme jít přes něj.
OK, jsme opravdu jít nad ní je nyní to, co říkáme.
>> Diváků: To je pro vyhledávacím stromu.
>> SPEAKER 1: Jo.
Je to získávání strom.
Úžasné.
Takže jedna věc je si všimnout je, že jsme jsou při pohledu na jednotlivé znaky
tady, že jo?
>> Takže před naší hash funkcí, jsme se dívali na slova jako celku,
a teď se díváme více na znaky, ne?
Takže máme Maxwell sem a Mendel.
Takže v podstatě try-- způsob, jak myslet o tom, že každý stupeň je zde
je řada písmen.
Takže tohle je váš kořenový uzel tady, že jo?
To má všechny znaky abeceda na začátku každého slova.
>> A to, co chcete udělat, je řekněme, OK, máme nějaké M slovo.
Jedeme se podívat na Maxwell, tak jedeme do M. a M bodů na celý
další pole, kde každý slovo, pokud tam
je slovo, které má jako druhé písmeno,
jak dlouho jak tam je to slovo, které má B jako druhé písmeno,
bude mít ukazatel bude nějaké další pole.
>> Je tu asi není slovo, které MP něco,
takže v poloze P v této pole, bylo by to prostě být NULL.
To by řekl, OK, není slovo který M následované P, OK?
Takže pokud si myslíme, že o tom, každý jeden z těchto menších věcí
je ve skutečnosti jedna z nich velké pole od A až Z.
Takže to, co by mohlo být jednou z věcí, že je tak trochu navracení zkusit?
>> Diváků: hodně paměti.
>> SPEAKER 1: Je to ton paměti, že jo?
Každý z těchto bloků zde představuje 26 míst, 26 prvků pole.
Takže se snaží dostat neuvěřitelně prostor těžké.
>> Ale oni jsou velmi rychlé.
Tak neuvěřitelně rychle, ale Opravdu prostor neefektivní.
Druh přijít který z nich chcete.
Jedná se o opravdu cool pro pset, ale oni zabírají hodně paměti,
takže si přivlastnit.
Jo?
>> Diváků: Bylo by možné nastavit vyzkoušet a pak se
Jakmile budete mít všechny údaje v něm, že jste need--
Já nevím, jestli to bude mít smysl.
Byl jsem jak se zbavit všech Znaky NULL, ale pak
nebudete moci indexu them--
>> SPEAKER 1: Stále potřebují.
>> Diváků: - stejným způsobem pokaždé.
SPEAKER 1: Jo.
Musíte se znaky NULL, aby víte-li, že to není tam slovo.
Ben se máte něco, co chcete?
OK.
Tak jo, jdeme jít trochu více
do technických podrobností za snažit a pracovat na příkladu.
>> OK, tak je to to samé.
Vzhledem k tomu, v propojeném seznamu, naše hlavní druh of-- co je to slovo, které jsem chtěl? -
jako stavební blok byl uzel.
V pokusu, máme také uzel, ale je to definováno jinak.
>> Takže máme nějaký bool, že znamená, zda slova skutečně
existuje na tomto místě, a pak máme nějaké pole here-- nebo spíše,
To je ukazatel na Pole 27 znaků.
A to je pro, v tomto případě, to 27-- Jsem si jist, všichni z vás jsou jako, počkejte,
tam je 26 písmen v abecedě.
Proč máme 27?
>> Takže v závislosti na způsob, jak realizovat to,
To je z pset, že povoleno apostrofy.
Takže to je důvod, proč navíc jeden.
Budete mít také v některých případy null terminačních
je zahrnuta jako jeden z znaky, že to nemá být,
a to je to, jak zkontrolovat, zjistit, jestli je to konec slova.
Máte-li zájem, podívejte se Kevin video na study.cs50,
jakož i Wikipedia má některé dobré zdroje tam.
>> Ale my jdeme projít jen tak o tom, jak můžete pracovat na pokus
pokud jste dal dnes.
Takže tu máme super jednoduchá tady, že má slova "BAT" a "zoom" v nich.
A jak vidíme tady, tento malý prostor zde
reprezentuje naši bool, že říká, ano, je to slovo.
A pak to má naši pole znaků, ne?
>> Tak jsme se jít přes hledání "BAT" v tomto pokusu.
Takže začít nahoře, ne?
A my víme, že b odpovídá druhý index, druhý prvek
V tomto poli, protože a b.
Takže přibližně druhý.
>> A říká, OK, v pohodě, z toho, že do další pole, protože když si vzpomeneme,
je to tak, že každý z nich ve skutečnosti obsahuje prvek.
Každý jeden z těchto polí obsahuje ukazatel, že jo?
To je důležitý rozdíl, aby se.
>> Vím, že to bude be-- snaží se opravdu těžké se dostat na poprvé,
takže i když je to druhý nebo třetí čas
a je to stále trochu ze zdánlivě obtížné,
Slibuji, že když jdete na hodinky zítra krátký znovu,
to bude asi dělat mnohem větší smysl.
To trvá hodně trávit.
Já ještě někdy jsem jako, počkej, co je to vyzkoušet?
Jak mám použít?
>> Proto jsme B v tomto případě, který je naším druhým index.
Kdybychom měli, řekněme, c nebo d nebo jiné písmeno,
musíme zmapovat to zpátky do indexu našeho pole, které, které odpovídá.
Tak bychom brát jako rchar a my jsme odečíst off mapovat do 0 do 25.
Všichni dobře, jak Mapa naše postavy?
OK.
>> Tak jdeme na druhou a my vidět, že, ano, to není NULL.
Můžeme přejít k tomuto dalšímu poli.
Tak jdeme na této další pole zde.
>> A my říkáme, OK, teď je třeba zjistit, jestli je tady.
Je null nebo to dělá vlastně vpřed?
Tak vlastně pohybuje předal v tomto poli.
A my říkáme, OK, t je náš poslední písmeno.
Tak jsme se jít do t na indexu.
A pak jsme se kupředu protože je tu ještě jeden.
A tohle říká v podstatě to, že ano, se říká, že je slovo here--
že pokud budete postupovat podle tohoto cesta, jste dorazili
na slova, která jak víme, je "bat".
Ano?
>> Diváků: Je standardní, aby toto jako index 0 a pak jakousi na 1
nebo mít na konci?
>> SPEAKER 1: Ne
Takže pokud se podíváme zpět na naší Prohlášení tady, je to bool,
tak je to jeho vlastní element v uzlu.
Takže to není součástí pole.
V pohodě.
Takže když jsme dokončit naše slovo a my jsme na tomto poli, to, co chceme dělat
je provést kontrolu na toto slovo.
A v tomto případě by to vrátit ano.
>> Takže v takovém případě, víme, že "zoo" - známe jako člověka, který "zoo" je slovo,
že jo?
Ale zkusit by zde říkají, ne, to ne.
A to bych řekl, že proto, že jsme nebyly označeny jako slovo zde.
I přesto, že můžeme přejít až do tohoto pole,
Tento pokus by řekl, že ne, zoo není ve slovníku
protože nemáme označeny jako takové.
>> Takže jeden způsob, jak to udělat that-- oh, sorry, tohle.
Takže v tomto případě, "zoo" není slovo, ale to je v našem pokusu.
Ale v tomto jednom, že bychom si to přejí představit slovo "lázně", co se stane,
je sledujeme through-- B, A, t.
Jsme v tomto poli, a jdeme hledat h.
>> V tomto případě, kdy se podívat na ukazatel na h,
to ukazuje na NULL, OK?
Takže pokud je to výslovně ukázal na jiné pole,
předpokládat, že všechny ukazatele V tomto poli se ukazuje na hodnotu null.
Takže v tomto případě, h se ukazuje na hodnotu null, takže nemůžeme nic dělat,
tak to by také vrátit false, "koupel" není tady.
Takže teď jsme vlastně jít přes
jak bychom vlastně říci, že "zoo" má v našem pokusu.
Jak můžeme vložit "zoo" do našeho pokusu?
Takže stejným způsobem, jako jsme začali náš spojový seznam, začneme u kořene.
Pokud jste na pochybách, začněte kořen z těchto věcí.
>> A budeme říkat, OK, z.
z existuje v této, a to dělá.
Takže jste se přestěhovali na váš další pole, OK?
A pak na další, říkáme, OK, to o existuje?
To dělá.
To znovu.
>> A tak se na naší další, jsme řekli, OK, "zoo" už tady existuje.
Vše, co musíme udělat, je nastavit to rovná na pravda, že je tam slovo.
Pokud jste sledoval všechno až do tohoto bodu,
je to slovo, tak jen nastavte ji na hodnotu, např.
Ano?
>> Diváků: Tak to dělá znamená, že "ba" je slovo, které také?
>> SPEAKER 1: Ne
Takže v tomto případě, "ba" bychom se dostali Zde bychom říci, je to slovo,
a stále by být.
OK?
Mmhmm?
>> Diváků: Takže jakmile je to slovo, a vy říkáte ano, pak to
bude obsahovat jít do m?
>> SPEAKER 1: Tak to má co do činění with-- jste načítá to v.
Říkáte, že "zoo" je slovo.
Když jdete do check-- jako, že chcete říct,
znamená "zoo" existují v tomto slovníku?
Jste jen bude hledat "zoo" a pak zkontrolujte, zda je to slovo.
Vy jste nikdy pohybovat až m, protože to není
to, co hledáte.
>> Pokud tedy vlastně chtěl přidat "koupel" v tomto pokusu,
budeme dělat totéž jako jsme to udělali s "zoo"
s výjimkou bychom vidět, že když jsme pokusit se dostat h, to neexistuje.
Takže si můžete myslet na to, jak se snaží pro přidání nového uzlu do propojeného seznamu
tak bychom museli přidat další jeden z těchto polí, jako tak.
A pak to, co děláme, je prostě nastavit h prvek tohoto pole ukazuje na to.
>> A pak to, co by chtěl dělat?
Přidat se rovná pravda protože je to slovo.
V pohodě.
Já vím.
Pokusy nejsou nejvíce vzrušující.
Věř mi, já vím.
>> Takže jedna věc je si uvědomit, s pokusech, Řekl jsem, že jsou velmi efektivní.
Proto jsme, viděli zabírají spoustu místa.
Jsou to trochu matoucí.
Tak proč bychom vůbec používat tyto?
Používáme tyto, protože jsou neuvěřitelně efektivní.
>> Takže pokud jste někdy hledáte up slova, jste jen
ohraničené délkou slova.
Takže pokud hledáte slovo, které je v délce pěti,
jste jen někdy muset aby u většiny pěti srovnáních, OK?
Takže je to v podstatě konstantní.
Stejně jako vkládání a vyhledávání jsou v podstatě konstantní čas.
>> Takže pokud můžete někdy něco v konstantním čase,
je to tak dobré, jak to dostane.
Nemůžete lepší než konstantní čas na tyto věci.
Tak, že je jedním z obrovské plusy pokusů.
>> Ale je to hodně prostoru.
Takže tak nějak se rozhodnout, co je pro vás důležitější.
A na dnešních počítačích, prostor, který pokus může trvat až
Možná, že nemá vliv na si, že hodně, ale možná
máte co do činění s něčím která má daleko, daleko více věcí,
a pokus prostě není rozumné.
Ano?
>> Publikum: Počkej, takže budete mít 26 písmena jednoho každého?
>> SPEAKER 1: Mmhmm.
Jo, máte 26.
Máte nějaký je slovo, značka a pak Máte 26 ukazatelů v každém jednom.
A oni point--
>> Diváků: A každý 26, že každý z nich má 26?
>> SPEAKER 1: Ano.
A to je důvod, proč, jak můžete vidět, že se rozšiřuje velmi rychle.
Dobrá.
Takže budeme se dostat do stromů, které Mám pocit, že je jednodušší a pravděpodobně
je pěkný malý odklad z pokusů tam.
Takže doufejme, že většina z vás které viděl strom.
Ne jako docela Ty mimo, které jsem
nejsou-li někdo vědět šel venku v poslední době.
Šel jsem jablko vychystávání tento víkend a oh můj bože, to bylo krásné.
Nevěděl jsem, že listy může vypadat, že dost.
>> Takže je to jen strom, ne?
Je to jen nějaký uzel, a to poukazuje na spoustu dalších uzlů.
Jak vidíte tady, je to druh opakující se téma.
Uzly ukazující uzlů je druh Podstatou mnoha datových struktur.
Záleží jen na tom, jak nechat upozornit na sebe
a jak jsme se projít skrze ně a jak
vložit věci, které určuje jejich odlišné charakteristiky.
>> Takže jen některé pojmy, který jsem používal předtím.
Tak root je to, co je na samém vrcholu.
to je místo, kde jsme se vždy začít.
Můžete si ji představit jako hlavy také.
Ale stromy, máme tendenci odkazují na to jako root.
>> Cokoliv na spodní here-- na velmi, velmi bottom--
jsou považovány za listy.
Tak to jde ruku v ruce s Celý strom věc, ne?
Listy jsou při okrajích stromu.
>> A pak máme také pár Podmínky mluvit o uzlech ve vztahu
k sobě navzájem.
Takže máme rodiče, děti a sourozenci.
Takže v tomto případě, je 3 rodič 5, 6 a 7.
Takže rodič, co je o krok výše, co jste
s odkazem na to, tak prostě jako rodokmen.
Doufejme, že je to všechno trochu trochu více intuitivní než pokusů.
>> Sourozenci jsou všechny, které mají stejná mateřská, ne?
Jsou na stejné úrovni zde.
A pak, když jsem byl říká, děti jsou jen
co je jeden krok dále uzel v otázce, OK?
V pohodě.
Tak binární strom.
Může někdo hádat, na jednom z vlastnosti binárního stromu?
>> Diváků: Max dva lístky.
>> SPEAKER 1: Správně.
Takže max dvou listů.
Takže v tomto jednom dříve, měli jsme tenhle která měla tři, ale v binárním stromu,
Máte-max dvou dětí na rodiče, že jo?
Je tu další zajímavá vlastnost.
Ví někdo, že?
Binární strom.
>> Takže binární strom bude mít vše na the-- tohle není sorted--
ale v seřazené binárního stromu, vše na pravé straně
je větší než původní, a vše, co na levé straně
je menší než rodiče.
A to byl kvíz Otázka před, tak dobré to vědět.
Takže způsob, jak definovat to, opět máme další uzel.
To vypadá velmi podobně jako co?
Dvojnásobně
>> Diváků: spojových seznamů
>> SPEAKER 1: dvojitý spojový seznam, ne?
Pokud tedy nahradit tento s předchozí a následující,
by to bylo dvojnásobně spojový seznam.
Ale v tomto případě jsme se vlastně jsou vlevo a vpravo, a je to.
Jinak je to úplně stejné.
Stále máme prvek hledáte,
a stačí dva ukazatele bude, co bude dál.
Jo, tak binární vyhledávací strom.
Pokud jsme si všimli, vše na tady je větší than--
nebo vše ihned aby tady
je větší než, všechno Zde je menší než.
>> Takže, pokud bychom měli prohledávat, by měl vypadat velmi blízko k binární vyhledávání
tady, že jo?
Kromě namísto hledání na polovinu pole,
jsme se jen při pohledu na levou straně nebo na pravé straně stromu.
Tak to je trochu jednodušší, myslím.
>> Takže pokud vaše kořen je NULL, samozřejmě je to jen falešná.
A pokud to tam je, samozřejmě, že je to pravda.
Pokud je to méně, než jsme se hledat vlevo.
Pokud je větší než hledáme právo.
Je to přesně jako binární vyhledávání, jen odlišná struktura dat
že jsme použili.
Místo pole, je to jen binární strom.
>> OK, komíny.
A také to vypadá, že my může mít trochu času.
Pokud se tak stane, jsem rád, že jít přes tohle všechno znovu.
OK, tak komíny.
Pamatuje si někdo, co stacks-- všechny charakteristiky zásobníku?
>> OK, takže většina z nás, myslím, jíst v jídelně halls--
co můžeme neradi.
Ale samozřejmě, můžete myslet na zásobníku doslova jen jako hromadu zásobníků
nebo hromadu věcí.
A co je důležité si uvědomit, že je to
something-- charakteristika že říkáme, že by-- je LIFO.
Ví někdo, co to znamená?
Mmhmm?
>> DIVÁKŮ: Poslední dovnitř, první ven.
>> SPEAKER 1: Dobře, poslední dovnitř, první ven.
Takže pokud víme, jestli jsme stohování věci up, nejjednodušší chytit off--
a snad jediné, co můžeme chytit vypne, pokud náš stack je velký enough--
je to, že horní prvek.
Takže bez ohledu byl kladen na last-- jak vidíme zde,
co byl tlačen na většině recently-- je
bude první věc, že ​​jsme pop off, OK?
>> Takže to, co tu máme, je další typedef struct.
To je opravdu jen rád rychlokurz v datové struktuře,
takže je tu spousta hozen na vás kluci.
Já vím.
Takže další Struct.
Yay pro stavby.
>> A v tomto případě, je to nějaký ukazatel na pole, které má určitou kapacitu.
Takže to představuje náš stack Zde, stejně jako naší aktuální pole
které drží naše prvků.
A pak tady máme nějaké velikosti.
>> A obvykle, chcete, aby track o tom, jak velký je váš stack
protože to, co se děje, aby můžete udělat, je, pokud víte, že velikost,
to vám umožní říci, OK, jsem na plný výkon?
Mohu přidat něco víc?
A také vám řekne, kde horní část zásobníku
tak víte, co jste může skutečně vzlétnout.
A to vlastně bude tady trochu jasnější.
>> Takže pro stisk, jednu věc, pokud máte byl vždy realizovat tlačit,
jak jsem právě řekl, vaše zásobník má omezenou velikost, je to tak?
Naše pole měl nějakou kapacitu.
Je to pole.
Je to pevné velikosti, takže je třeba, aby Ujistěte se, že nejsme uvedení více
do našeho pole, než jsme skutečně prostor pro.
>> Takže, když budete vytvářet tlak funkce, první věc, kterou udělat, je říci, OK,
mám místo ve svém stacku?
Protože když to neudělám, promiň, Nemohu uložit prvek.
Když to udělám, pak budete chtít uložit je na vrcholu zásobníku, je to tak?
>> A to je důvod, proč máme sledovat naší velikosti.
Nebudeme-li mít přehled o naší velikosti, nevíme, kam to dát.
Nevíme, jak mnoho věcí, jsou v našem poli již.
Jako samozřejmě existují způsoby, jak že možná byste mohli udělat.
Dalo by se inicializovat vše NULL a pak zkontrolujte, zda máte nejnovější verzi NULL,
ale mnohem jednodušší věc je prostě říct, OK, sledovat velikosti.
Stejně jako vím, že mám čtyři prvky v mém poli, takže další věc,
že jsme dali na, jsme bude ukládat na indexu 4.
A pak, samozřejmě, to znamená, že jste úspěšně tlačil něco
na stacku, jste chcete zvýšit velikost
takže víte, kde jste tak že můžete tlačit více věcí na.
>> Takže pokud se snažíme pop něco z hromádky,
co by mohlo být první věc, že chceme zkontrolovat?
Snažíte se vzít něco z vašeho stacku.
Jste si jistý, že je to něco v zásobníku?
Ne.
Takže to, co bychom mohli chtít zkontrolovat?
>> Diváků: [neslyšitelné].
SPEAKER 1: Zkontrolujte, zda velikost?
Velikost.
Takže chceme zkontrolovat, zda Naše velikost je větší než 0, OK?
A pokud ano, pak chceme snížit Naše velikost od 0 a vrátit to.
Proč?
>> V prvním z nich jsme byli tlačení, to tlačil nás
na velikosti a poté průběžně aktualizovaným velikosti.
V tomto případě jsme dekrementování velikost a pak ji sundal, škubání ji
z naší řady.
Proč bychom mohli udělat, že?
Takže pokud mám jednu věc na mém stacku, Co by byla moje velikost v tomto místě?
1.
>> A kde je prvek 1 uloženo?
Na co index?
Publikum: 0.
SPEAKER 1: 0.
Takže v tomto případě jsme Vždy je třeba provést sure--
místo vrácení velikost minus 1, protože jsme
víme, že naše prvek je bude uložen na 1 méně
bez ohledu na naši velikost je, toto jen se o to postarám.
Je to o něco více elegantní způsob.
A my jen decrement dotazy velikost a pak se vrátit velikost.
Mmhmm?
>> Diváků: Myslím, že jen obecně, proč by to datová struktura
být výhodné?
>> SPEAKER 1: Záleží na vašem kontextu.
Tak pro některé z teorie, pokud pracujete with-- OK,
dovolte mi, abych zjistil, jestli je prospěšné jeden která je prospěšná pro více než venku
ČS.
U komínů, kdykoliv budete potřebovat sledovat něco, co
se naposledy přidán je, když budete chtít použít zásobník.
>> A já si nemyslím, že je dobrý Příkladem, že právě teď.
Ale kdykoli poslední co je pro vás nejdůležitější,
to je, když stack bude užitečné.
Snažím se, že pokud tam je dobrý pro to.
Pokud bych myslet na dobrý příklad v další 20 minut a to se určitě říct.
>> Ale celkově, jestli je něco, jak jsem řekl, že většina, kde poslední
Nejdůležitější je, že se kde balík vstoupí do hry.
Vzhledem k tomu, fronty jsou trochu naopak.
A všechny ty malé psy.
Není to skvělé, že jo?
Mám pocit, jako bych měl jen mít zajíček videa
přímo v centru Sekce pro vás
protože se jedná o intenzivní část.
>> Tak fronta.
V podstatě fronta je jako linie.
Vy Jsem si jistý, použití této každodenní, stejně jako v našich jídelnách.
Takže musíme jít a dostat naše zásobníky, jsem
že máte čekat ve frontě Přesunutí nebo dostat své jídlo.
>> Tak tady je rozdíl je to, že toto je FIFO.
Takže pokud LIFO byla naposledy v prvním out, FIFO je first in, first out.
Tak tohle je místo, kde co si dát Na první je vaše nejdůležitější.
Takže pokud jste čekali v line-- můžete
Představte si, že jste šel do jdi na nový iPhone
a to bylo stack, kde poslední osoba v souladu ji dostal jako první,
lidé by se navzájem zabíjeli.
>> Takže FIFO, jsme všichni velmi dobře se zde v reálném světě,
a to všechno má co do činění s opravdu druh obnovovat celý tento řádek
a fronty strukturu.
Takže zatímco v zásobníku, máme tlačit a pop.
S fronty, máme Přidat do seznamu a dequeue.
Přidat do seznamu tak v podstatě znamená, dát na záda,
a Dequeue prostředky vzít off zepředu.
Takže naše datová struktura je trochu složitější.
Máme druhou věc, jak sledovat.
>> Takže bez hlavy, to je přesně to, zásobník, ne?
To je stejné konstrukce jako zásobník.
Jediné, co teď jiné je, že jsme tuto hlavu, která to, co si myslíte, že
bude sledovat?
>> Diváků: první z nich.
>> SPEAKER 1: Správně, První věc, kterou jsme dali v.
Hlava naší fronty.
Ten, kdo je v první linii.
Dobře, takže pokud uděláme zařazení do fronty.
Opět platí, že se některý z Tyto datové struktury,
protože máme co do činění s řadou, musíme zkontrolovat, jestli máme prostor.
>> To je něco jako já, říká vy, pokud otevřete soubor,
je třeba zkontrolovat na null.
S některou z těchto komínů a fronty, budete potřebovat
zjistit, jestli tam je prostor, protože jsme jednání s pevnou velikostí pole,
jak vidíme here-- 0, 1 vše až 5.
Takže to, co děláme v tomto případě je kontrola aby zjistil, jestli ještě máme prostor.
Je naše velikost menší než kapacita?
>> Pokud tomu tak je, musíme uložit na ocas a obnovujeme naši velikost.
Takže to, co je možné, že ocas je v tomto případě?
To není výslovně napsané.
Jak bychom to uložit?
Co by ocas být?
>> Takže pojďme se projít tento příklad.
Tak tohle je pole o velikosti 6, ne?
A máme teď, naše velikost je 5.
A když jsme se dát do, bude to jít do pátého indexu, ne?
Tak skladuje v ocasu.
>> Dalším způsobem, jak napsat ocas by jen naše pole v indexu velikosti, ne?
To je velikost 5.
Další věc je jít do 5.
V pohodě?
OK.
Je to poněkud složitější dostane když začneme hrát s hlavou.
Ano?
>> Diváků: Znamená to, že jsme by deklarovali pole, které
bylo pět prvků dlouhá a pak budeme přidávat na něj?
>> SPEAKER 1: Ne
Takže v tomto případě se jedná o zásobník.
To by být prohlášen za jako pole o velikosti 6.
A v tomto případě jsme stačí jedno volné místo.
>> OK, takže jedna věc je v tomto případě, je-li naše hlava je na 0,
pak stačí jej přidat na velikosti.
Ale to dostane trochu složitější protože ve skutečnosti, že
nemají snímek za to, takže budu
k tomu jedno, protože to není tak jednoduché, jakmile se
začít, jak se zbavit věcí.
A tak vzhledem k tomu, se zásobníkem si jen někdy
se starat o to, co je velikost když přidáváte něco dál,
s fronty je také nutné, aby se Ujistěte se, že vaše hlava se účtuje,
protože super věc o frontách je, že pokud nejste na plný výkon,
můžete skutečně dělat to se zalomí kolem.
>> OK, tak jeden thing-- oh, to je hrozné křída.
Jedna věc, aby zvážila, je tomu tak.
Budeme prostě pět.
OK, takže budeme tvrdí, že hlava je tady.
To je 0, 1, 2, 3, 4.
>> Hlava je tam, a prosím, věci v nich.
A chceme přidat něco, že jo?
Takže to, co potřebujeme vím, je, že hlava je vždy
bude se pohybovat sem a pak zpětné smyčky kolem, OK?
>> Tak tohle fronta má prostor, ne?
Má prostor na samém počátku, druh opak toho.
Takže to, co musíme udělat, je, že jsme je třeba vypočítat ocas.
Pokud víte, že vaše hlava nepohybuje, ocas
je jen vaše pole na index velikosti.
>> Ale ve skutečnosti, pokud používáte frontu, vaše hlava je pravděpodobně aktualizován.
Takže to, co musíte udělat, je vlastně výpočet ocas.
Takže to, co děláme, je to vzorec tu, kterou jsem tě nechat
vy myslíte o, a pak budeme o tom mluvit.
Tak tohle je kapacita.
>> Takže to bude ve skutečnosti vám, jak to udělat.
Protože v tomto případě, co?
Naše hlava je na 1, naše velikost je 4.
Pokud bychom mod, že 5, dostaneme 0, což je místo, kde bychom měli vstup za to.
>> A tak v dalším případě, kdybychom k tomu,
říkáme, OK, pojďme dequeue něco.
Jsme dequeue to.
Bereme se tento prvek, je to tak?
>> A teď naše hlava směřuje zde a chceme přidat další věci.
To je v podstatě zpět na naší linii, ne?
Fronty mohou obalit kolem pole.
To je jeden z hlavních rozdílů.
Komíny, můžete to udělat.
>> S front, můžete protože všechno, na čem záleží
je to, že víte, co byl naposledy přidán.
Vzhledem k tomu, vše se bude přidán do Tento doleva směr, v tomto případě,
a pak zabalit kolem, můžete pokračovat v zavádění nových prvků
v přední části pole protože to není opravdu
přední pole už.
Můžete myslet na začátku pole jako, kde se vaše hlava je ve skutečnosti.
>> Takže tento vzorec je, jak můžete vypočítat ocas.
Má to smysl?
OK.
OK, dequeue, a pak vy máte 10 minut
aby se mě nějaké objasňovat otázky Chcete, protože vím, že je to šílené.
>> V pořádku, takže ve stejném way-- Já nevím, jestli si kluci všimli,
ale CS je o vzory.
Věci jsou do značné míry Totéž, jen s malými vylepší.
Tak to samé zde.
Musíme zjistit, zda je skutečně mít něco v naší frontě, ne?
Říci, OK, je naše velikost větší než 0?
V pohodě.
>> Pokud se tak stane, pak se přesuneme naši hlavu, která je to, co jsem tu právě prokázal.
Aktualizujeme naši hlavu, aby se ještě jednou.
A pak jsme decrement naše Velikost a vrátí prvek.
>> Tam je mnohem konkrétnější kód na study.cs50.net,
a vřele doporučuji jít přes to, pokud budete mít čas,
i když je to jen pseudo-kódu.
A pokud vy chcete mluvit přes že se mnou jeden na jednoho, dejte mi prosím
vědět.
Já bych rád.
Datové struktury, pokud budete mít CS 124, budete
vím, že datové struktury dostat velmi legrace, a to je jen začátek.
>> Takže vím, že je to těžké.
To je v pořádku.
Bojujeme.
Stále dělám.
Takže se nemusíte příliš starat o to.
>> Ale to je v podstatě Vašimi rychlokurz v datových strukturách.
Vím, že je to hodně.
Je tu něco, co nám bych jít znovu?
Cokoliv chceme probrat?
Ano?
>> Diváků: Pro tento příklad, tak nový ocas je na 0 přes to?
SPEAKER 1: Ano.
Diváků: OK.
Takže prochází, budeš mít 1 a 4 nebo--
>> SPEAKER 1: Takže jste říkala, když chceme jít to udělat znovu?
Diváků: Jo.
Takže pokud jste se přijít na out--, kde jsou budete výpočet ocas z v tom, že?
>> SPEAKER 1: Takže ocas Byl in-- změnil jsem to.
Takže v tomto případě tady, to bylo pole se díváme, OK?
Takže máme věci v 1, 2, 3 a 4.
Takže máme naše hlava je rovna 1 na tento bod, a naše velikost je rovna 4
na tomto místě, že jo?
>> Vy všichni se shodují, že je to tak?
Takže děláme hlavu plus velikost, která nám dává 5, a pak jsme mod o 5.
Dostáváme 0, což nám říká, že 0 je kde je náš ocas, kde máme prostor.
>> Diváků: Co je čepice?
>> SPEAKER 1: kapacita.
Promiňte.
Tak to je velikost vašeho pole.
Ano?
>> Diváků: [neslyšitelné] před vrátíme prvek?
>> SPEAKER 1: Takže se pohybujeme hlavou nebo se vrátit v okamžiku, kdy?
Pokud tedy přesunout jeden, decrement velikost?
Vydrž.
Rozhodně jsem zapomněl další.
To nic.
Není jiný vzorec.
Jo, by se chcete vrátit hlava a pak ji vrátit zpět.
>> Publikum: OK, protože v tomto bod, hlava byla na 0,
a pak se chcete vrátit index 0 a pak se hlava 1?
>> SPEAKER 1: Správně.
Myslím, že je tu další vzorec něco jako tohle.
Nemám ji na vrcholu mé hlavy, jak Nechci, aby vám ten špatný.
Ale myslím, že je to naprosto v pořádku, aby řekněme, OK uložte tuto element-- cokoliv
element hlava je je-- decrement vaše velikost, pohybovat hlavou nad a návrat
co to je element.
To je naprosto v pořádku.
OK.
Mám pocit, že to není jako most-- nejste
jít pěšky odsud jako, ano, já vím pokusů.
Mám to všechno.
To je v pořádku.
Slibuji.
Ale datové struktury jsou něco, co to trvá hodně času si zvyknout.
Pravděpodobně jeden z nejtěžších věci, myslím, že v průběhu.
>> Tak to určitě má opakování a při pohledu at-- I
to opravdu nevím provázané seznamy dokud jsem udělal příliš mnoho s nimi,
stejným způsobem, že jsem to neudělal opravdu pochopit ukazatele
dokud jsem se musel učit pro dva let a dělat své vlastní psets s ním.
To vyžaduje hodně zdůraznění a času.
A nakonec, bude to trochu na tlačítko.
>> Ale do té doby, pokud máte typ porozumění na vysoké úrovni, co
Tyto dělat, jejich výhody a cons-- což je to, co
opravdu se snaží zdůraznit, zejména v úvodní kurzu.
Stejně jako, proč bychom použít zkuste přes pole?
Stejně jako to, co jsou pozitiva a zápory každého z nich?
>> A pochopení kompromisy Mezi každou z těchto struktur
je to, co je mnohem důležitější právě teď.
Zde může být jeden blázen otázka nebo dva, které je
bude vás žádat, abyste implementovat tlačit nebo realizovat pop nebo zařazení do fronty a Dequeue.
Avšak ve většině případů, že mají vyšší úroveň porozumění a více
na intuitivní pochopení je mnohem důležitější, než ve skutečnosti
budou moci k jeho provedení.
>> To by bylo opravdu úžasné, kdybyste všichni mohl jít ven a jít realizovat vyzkoušet,
ale chápeme, že to nemusí být nutně nejrozumnější věc, kterou právě teď.
Ale můžete v pset, chcete-li na, a pak budete mít praxi,
a pak možná budete opravdu pochopit.
Ano?
>> Publikum: OK, tak ty, které jsou jsme chtěl použít v pset?
Musím použít jeden z nich?
SPEAKER 1: Ano.
Takže máte na výběr.
Myslím, že v tomto případě můžeme mluvit o pset trochu
protože jsem běžel přes tyto.
Takže ve vašem pset, nemáte výběr pokusů nebo hash tabulky.
Někteří lidé se budou snažit a použití bloom filtry,
ale ty technicky nejsou správné.
Vzhledem k jejich pravděpodobnostní povahu, dávají někdy falešně pozitivní.
Jsou v pohodě pohled do, ačkoli.
Velmi doporučuji hledat na ně minimálně.
Ale máte možnost volby mezi hash tabulky a pokus.
A to bude kdy vložíte do slovníku.
>> A budete muset vybrat vaše hash funkce,
budete muset zvolit, kolik lopaty máte, a to se bude lišit.
Jako když máte více kbelíky, Možná, že to bude rychlejší.
Ale možná, že ztrácíte Spousta prostoru, který tak či onak, ačkoli.
Musíte na to přijít.
Mmhmm?
>> Diváků: Říkal jste, že před tím můžeme použít i jiné hašovací funkce,
že nemusíme vytvořit hash funkce?
>> SPEAKER 1: Ano, správně.
Takže doslova pro hash funkci, jako google "hash funkce"
a podívejte se na některé ty chladné.
Nejste Očekává se, že stavět vlastní hash funkce.
Lidé tráví svůj práce na těchto věcech.
>> Takže se nemusíte starat o budování své vlastní.
Najít jednu on-line pro začátek.
Některé z nich budete muset manipulovat trochu
aby se ujistil, návratové typy shodovat a kdo ví co ještě, takže na začátku,
Doporučil bych používat něco rychlé, že možná právě
hash na první písmeno.
A pak, až budete mít, že práce, zahrnující chladnější hash funkce.
Mmhmm?
>> Diváků: Bude zkuste být nebo efektivní, ale jen těžší, like--
>> SPEAKER 1: Takže zkusit, myslím, je intuitivně těžko realizovat
ale je velmi rychlý.
Nicméně, zabírá více místa.
Opět platí, že můžete optimalizovat obě ty různé způsoby, a existují způsoby, jak to--
Diváků: Jak jsme třídí na to?
Má matter--
>> SPEAKER 1: Takže jste se stupněm normálním způsobem.
Budeš se třídí na design.
Podle toho, jak to uděláte, budete chtít, aby ujistěte se, že je to tak elegantní, jak to může být
a tak účinný, jak to může být.
Ale pokud se rozhodnete vyzkoušet nebo hash Tabulka, tak dlouho, jak to funguje,
jsme rádi, s tím.
A pokud používáte něco, co hash na první písmeno, to je v pořádku,
Třeba jako jeho designu.
Jsme také dosáhnout bod v tomto semester--
Já nevím, jestli vás kluci noticed-- pokud jste
pset stupně klesat trochu vzhledem k designu a kdoví co ještě,
to je naprosto v pořádku.
Začíná to do bodu, kde se vaše programy jsou stále složitější.
Existuje více místa můžete zlepšit.
>> Takže je to naprosto normální.
To neznamená, že jste horší, na vašem pset.
Je to jen my je těžší na vás teď.
Takže všichni cítí to.
Jen jsem se třídí všechny vaše psets.
Vím, že každý se cítí to.
>> Takže se nemusíte obávat, že.
A pokud máte jakékoliv dotazy týkající se předchozí psets nebo způsoby, jak můžete zlepšit,
Snažím se a komentovat konkrétní místa, ale někdy je to pozdě
a já jsem unavený.
Existují i ​​jiné věci, o datové struktury?
Jsem si jistý, že kluci opravdu chceš mluvit o nich už,
ale pokud tam jsou, jsem rád, že jít přes ně, stejně jako cokoliv
z přednášky letos týden nebo minulý týden.
>> Vím, že minulý týden byl celý přezkum, tak Možná jsme přeskočil nějakou recenzi
z přednášky.
Jakékoliv další dotazy mohu odpovědět?
OK, v pořádku.
No, vy dostanete se 15 minut dříve.
>> Doufám, že to bylo částečně užitečné alespoň a já uvidíte kluci příští týden,
nebo ve čtvrtek úřední hodiny.
Existují žádosti o občerstvení na příští týden, to je věc?
Protože jsem zapomněl cukroví dnes.
A já jsem přinesl cukroví poslední týden, ale bylo to Columbus Day,
tak tam bylo tak šest lidí, kteří se měl čtyři pytle cukroví pro sebe.
Můžu přinést starburst znovu, pokud se vám líbí.
Starburst?
OK, to zní dobře.
Mají velký den, kluci.