[Prehrávanie hudby]
SPEAKER 1: V poriadku.
Všetci vitajte späť do kategórie.
Dúfam, že ste všetci úspešne späť z vášho testu
z minulého týždňa.
Viem, že je trochu blázon občas.
Ako som hovoril predtým, ak ste v rámci štandardnej odchýlky,
nemáte naozaj starať o to, a to najmä pre menej pohodlné úseku.
To je o tom, kde by ste mali byť.
>> Ak ste si skvele, potom úžasné.
Sláva tebe.
A ak máte pocit, že musíte trochu viac pomôcť, prosím
neváhajte osloviť z niektorého z TFS.
Všetci sme tu na pomoc.
>> To je dôvod, prečo sme sa učiť.
To je dôvod, prečo som tu každý pondelok pre vás chlapci a v kancelárii hodín vo štvrtok.
Tak neváhajte a dajte mi vedieť, Ak máte obavy o ničom
alebo v prípade, že je niečo v kvíze že by ste naozaj chceli riešiť.
>> Takže agenda pre dnešok je všetko o dátových štruktúr.
Niektoré z nich sú proste bude len aby sa vám zoznámil s týmito.
Nesmiete nikdy realizovať je v tejto triede.
Niektoré z nich si vyskúšate, ako pre pravopisu pset.
>> Budete mať svoj výber medzi stoly mriežky a pokusov.
Takže sme určite ísť cez tie.
Bude to mať rozhodne viac druhov vysokej úrovni úseku dnes, aj keď,
pretože existuje veľa z nich, a ak sme išli do podrobností implementácie
na všetkých z nich, neboli by sme dokonca prejsť spojových zoznamov
a možno trochu hash tabuľky.
>> Takže majte so mnou.
Nebudeme sa robí až kódovanie tentoraz.
Ak máte nejaké otázky o tom alebo ak chcete vidieť, že realizovať
alebo sa pokúsiť si to pre seba, Určite odporúčam
bude study.cs50.net, ktoré má príklady všetkých z nich.
To bude mať svoje powerpoints s poznámkami, ktoré sme
majú tendenciu používať aj trochou programovania cvičenie, predovšetkým na veci,
ako prepojených zoznamov a binárne stromy komíny a narážky.
Tak trochu na vysokej úrovni, ktoré by mohlo byť pekné pre vás.
>> Takže s tým, budeme začať.
A tiež, yes-- kvízy.
Myslím si, že väčšina z vás, ktorí sú v moja časť má svoje kvízy,
ale každý, kto príde, alebo z nejakého dôvodu nie, sú tu v prednej časti.
>> Tak spojových zoznamov.
Viem, že tento druh ide zálohovať pred kvíz.
To bolo pred týždňom že sme sa dozvedeli o tom.
Ale v tomto prípade, budeme len ísť trochu viac do hĺbky.
>> Tak prečo by sme mohli vybrať spájať zoznam cez pole?
Čo ich odlišuje?
Áno?
>> Divákov: môžete tiež rozšíriť spojené Zoznam oproti Array pevnú veľkosť.
SPEAKER 1: Správne.
Pole má pevnú veľkosť vzhľadom k tomu, spájať zoznam má premennú veľkosť.
Takže ak nevieme, ako moc chceme uložiť,
spájať zoznam nám dáva veľký spôsob, ako to urobiť, pretože my môžeme len
pridať na inom uzle a pridať na iný uzol a pridať na inom uzle.
Ale to, čo by mohlo byť trade-off?
Pamätá si niekto na trade-off medzi poľami a spojových zoznamov?
Mmhmm?
>> Divákov: Musíte prejsť celú cestu
prostredníctvom prepojeného zoznamu nájsť prvok v zozname.
V poli, môžete len nájsť prvok.
>> SPEAKER 1: Správne.
Tak s arrays--
>> Divákov: [nepočuteľné].
>> SPEAKER 1: S poľom, máme čo sa nazýva náhodný prístup.
Znamená to, že ak chceme, aby to, čo je niekedy piaty bod zoznamu
alebo piaty bod nášho pole, môžeme len chytiť ju.
Ak je to spájať zoznam, máme iterovat, že jo?
Tak prístup k prvku v pole je konštantný čas,
zatiaľ čo v prepojenom zozname, že by s najväčšou pravdepodobnosťou bude lineárny čas, pretože možno
naša prvkom je úplne na konci.
Musíme prehľadať všetko.
Takže sa všetkými týmito údajmi štruktúry pôjdeme
sa stráviť trochu viac času na, Aké sú plusy a zápory.
Keď by sme mohli chcieť použite jeden cez druhého?
A to je druh väčšia vec odniesť.
>> Takže máme tu definícia uzla.
Je to ako jeden prvok v náš spájať zoznam, nie?
Takže sme všetci oboznámení s našimi typedef structs,
ktoré sme prešli v recenzii naposledy.
Bolo to v podstate len vytvorením iný dátový typ, ktorý by sme mohli použiť.
>> A v tomto prípade, je to nejaký uzol že bude mať nejaké číslo v.
A čo potom je druhá časť tu?
Každý, kto?
>> Divákov: [nepočuteľné].
>> SPEAKER 1: Jo.
Je to ukazovateľ na ďalší uzol.
Takže by to malo byť skutočne tu.
To je ukazovateľ typu uzla na ďalšiu vec.
A to je to, čo zahŕňa náš uzol.
V pohode.
>> Dobre, tak s hľadaním, ako sme boli len hovorím, do ruky, ak ste
bude prehľadávať, Máte skutočne iterovat
prostredníctvom prepojeného zoznamu.
Takže ak sa pozeráme na počet 9 by sme začať na našej hlave
a že nás upozorňuje na začiatku nášho prepojeného zoznamu, nie?
A my hovoríme, OK, to robí uzol obsahovať číslo 9?
Nie?
>> V poriadku, prejdite na ďalší jeden.
Nasledujte ho.
Má obsahovať číslo 9?
Nie.
Sledujte ďalšie.
>> Takže máme skutočne iterovat prostredníctvom našej prepojeného zoznamu.
Nemôžeme jednoducho ísť priamo na miesto, kde 9.
A ak vy vlastne chcete vidieť nejaký pseudo-kódu tam hore.
Máme nejakú funkciu vyhľadávanie tu ktorý berie in-- čo to prijať?
Čo si myslíte?
Tak ľahké.
Čo je to?
Divákov: [nepočuteľné].
SPEAKER 1: Počet hľadáme.
Je to tak?
A čo by to odpovedať?
Je to ukazovateľ?
>> Divákov: uzol.
>> SPEAKER 1: uzol do zoznamu že sa pozeráme, je to tak?
Takže máme niektoré uzly sú ukazovateľ tu.
To je bod, ktorý sa bude vlastne iterovat našom zozname.
Vydali sme sa rovná zoznam pretože to je to
Nastavenie je rovné spustenie nášho prepojeného zoznamu.
>> A aj keď to nie je NULL, zatiaľ čo stále máme veci v našom zozname,
skontrolujte, či tento uzol má počet hľadáme.
Return true.
V opačnom prípade, aktualizovať, nie?
>> Ak je NULL, my ukončiť naše while a return false
pretože to znamená, že sme sa našli.
Má každý si, ako to funguje?
OK.
>> Tak s vloženie, budete majú tri rôzne spôsoby.
Môžete predradiť, môžete pripojiť a môžete vložiť do roztriedený.
V tomto prípade sme robiť predradeným.
Vie niekto, ako tie, tri prípadov môže líšiť?
>> Tak prepend znamená, že môžete dať je v prednej časti vášho zoznamu.
Takže by znamenalo, že bez ohľadu na aké sú vaše uzol je, bez ohľadu na to,
čo je hodnota, budete aby to tu vpredu, OK?
Bude to prvý prvok v zozname.
>> Ak ho pripojiť, bude to ísť na zadnej časti vášho zoznamu.
A vložiť do najrôznejších znamená, že ste dám skutočne do miesta
kde sa udržuje spájať zoznam zoradený.
Opäť, ako použiť ty, a pri použití
im bude líšiť v závislosti na vašom prípade.
Pokiaľ to nie je nutné, aby triediť, prepend inklinuje
byť to, čo si väčšina ľudí použiť, pretože nemáte
musí prejsť celý zoznam nájsť koniec pridajte ju, nie?
Stačí si len držať ju priamo.
>> Tak sme sa prejsť Vloženie 1 práve teraz.
Takže jedna vec, ktorú budem Vrelo odporúčam na tomto pset
je k tomu veci, ako vždy.
Je veľmi dôležité, aby ste aktualizovať Vaše ukazovatele v správnom poradí
pretože ak je aktualizovať trochu mimo prevádzku,
budete skončiť strate časti zoznamu.
>> Tak napríklad, v tomto prípade sme hovorí šéf len bod 1.
Ak sa nám jednoducho, že bez uloženia tejto 1,
nemáme poňatia, čo 1 by mali smerovať do súčasnosti
preto, že sme stratili to, čo hlavy ukázal na.
Takže jedna vec na zapamätanie keď robíte predradeným
je zachrániť to, čo sa hlava ukazuje na prvý,
potom priradiť, a potom aktualizovať čo váš nový uzol by mal ukazovať na.
V tomto prípade, je to jediný spôsob, ako to urobiť.
>> Takže ak sme urobili to takto kde sme práve prevelený hlavu,
strácame v podstate otázky Celý zoznam, jo?
Jeden spôsob, ako to urobiť, je mať 1 bod ďalší, a potom si hlavu bod 1.
Alebo si môžete urobiť niečo ako dočasné uskladnenie, čo som hovoril o.
>> Ale priradenie vlastné meno ukazovatele v správnom poradí
bude veľmi, veľmi dôležité, aby tento pset.
V opačnom prípade budete mať hash tabuľky alebo pokus, ktorý je len bude
len časť slova, ktoré ste chcú, a potom you're-- mmhmm?
Divákov: Aký bol dočasný skladovanie vec, ktorú hovorili?
SPEAKER 1: dočasné uskladnenie.
Takže v podstate ďalšie spôsob, ako by to mohlo robiť
je uložiť hlavu niečoho, ako je uložiť mu dočasné premenné.
Priradiť ju na hodnotu 1 a aktualizovať 1 bod
na čo hlava používa poukázať na.
Týmto spôsobom je samozrejme viac elegantný, pretože vás
Nemusíte dočasnú hodnotu, ale len ponúka iný spôsob, ako to urobiť.
A my vlastne majú nejaký kód na to.
Takže pre spájať zoznam, sme skutočne nejaký kód.
Tak Sem vložte, je to prepending.
Takže to zadá v čele.
>> Takže prvá vec, ktorú musíte vytvoriť nový uzol, samozrejme,
a skontrolujte, či NULL.
Vždy dobré.
A potom je treba priradiť hodnoty.
Vždy, keď vytvoríte nový uzol, vás Neviem, čo to ukazuje na ďalší,
takže chcete inicializovať na hodnotu NULL.
Ak to skončí ukázal na niečo, čo iného, ​​dostane pridelený a je to v poriadku.
Ak je to prvá vec, v zozname, je potrebné
poukázať na NULL, pretože to je koniec zoznamu.
>> Tak to vložiť, vidíme tu sa priradí ďalšiu hodnotu našej uzla
byť čo hlava, čo je to, čo sme tu mali.
To je to, čo sme práve urobili.
A potom sme priradenie hlavy až k bodu nášho nového uzla, pretože nezabudnite,
Nová je nejaký ukazovateľ na uzol, a to je presne to, čo hlava.
To je presne dôvod, prečo sme túto šípku prístupový.
V pohode?
Mmhmm?
>> Divákov: Musíme inicializovať novú Ďalšie NULL ako prvý,
alebo môžeme len inicializovať na hlavu?
>> SPEAKER 1: New ďalší musí byť NULL začať
pretože neviete, kde to bude.
Aj tento druh je rovnako ako paradigma.
Môžete nastaviť ju na hodnotu NULL, len aby Uistite sa, že všetky vaše základne sú pokryté
ako tak urobíte, že akékoľvek preradenie ste vždy zaručené, že to bude
ukazovať na konkrétnu hodnotu proti ako hodnotu odpadky.
Vzhľadom k tomu, jo, priradíme nové ďalšie automaticky,
ale je to viac, rovnako ako dobrej praxe k inicializácii
týmto spôsobom a potom priradiť.
>> OK, tak dvojnásobne spojových zoznamov teraz.
Čo si myslíme?
To, čo je s dvojnásobne spojené zoznamy?
>> Takže v našich spojových zoznamov, môžeme pohybovať len v jednom smere, nie?
Máme len ďalej.
Môžeme ísť len dopredu.
>> S dvojnásobne spájať zoznam, môžeme tiež presunúť späť.
Takže máme nielen Číslo, ktoré chceme uložiť,
máme tam, kde poukazuje na ďalšie a tam, kde sme práve prišli.
Takže to umožňuje niektoré lepšie priechod.
>> Tak dvojnásobne spojené uzly, veľmi podobné, nie?
Jediným rozdielom je teraz majú ďalšie a predchádzajúce.
To je jediný rozdiel.
>> Takže ak by sme mali predradiť alebo append-- sme nemajú žiadny kód pre tento up here--
ale ak ste boli, aby sa pokúsila vložte ju na dôležitú vec
je potrebné, aby že ste priradenie
ako vaše predchádzajúce a vaše ďalší ukazovateľ správne.
Takže v tomto prípade by ste nielen inicializovať ďalšie,
inicializáciu predchádzajúce.
Ak sme v čele zoznamu sme by hlava rovná novej nielen,
ale náš nový predchádzajúcej mal poukazujú na hlavu, nie?
>> To je jediný rozdiel.
A ak budete chcieť viac praxe s je s spojových zoznamov, s vložením,
s mazaním, s vložkou do triedeného zoznamu
prosím, pozrite sa study.cs50.net.
Je tu veľa skvelých cvičení.
Vrelo odporúčam je.
Prial by som si, aby sme mali čas ísť cez ne ale je tu veľa dátových štruktúr
prejsť.
>> OK, tak hash tabuľky.
Toto je pravdepodobne najviac užitočné bit pre pset
tu, pretože budete mať realizáciu jedného z nich, alebo skúsiť.
Moc sa mi páči hash tabuľky.
Sú to celkom v pohode.
>> Takže v podstate to, čo sa stane, je hash tabuľka
je, keď naozaj potrebujete rýchle vkladanie, mazanie a vyhľadávanie.
To sú veci, ktoré sme priorít v hash tabuľke.
Môžu sa dostať docela veľký, ale ako uvidíme sa pokusoch,
tam sú veci, ktoré sú oveľa väčšie.
>> Ale v podstate, všetky hash Tabuľka je hašovacej funkcie
že vám povie, ktoré vedro, aby každý vašich dát, každý z vašich prvkov.
Jednoduchý spôsob, ako myslieť na hash tabuľky je, že je to len vedierka vecí,
že jo?
Takže keď sa triedenie vecí podľa rovnako ako prvé písmeno svojho mena,
to je niečo ako hash tabuľky.
>> Takže vy, keby som skupiny je do skupín, kto začína meno
sa tu, alebo ten, kto má narodeniny v januári, februári, marci,
čo, že je účinne vytvorenie hash tabuľky.
Je to len vytváranie vedierka, že môžete triediť elementy do
takže si môžete nájsť je jednoduchšie.
Takže týmto spôsobom, keď som služieb nájsť jeden z vás,
Nemám na vyhľadávanie cez každého z vašich mien.
Môžem byť rád, oh, ja viem, že Danielle má narodeniny in--
Divákov: --April.
Reproduktor 1: apríl.
Tak som sa pozrieť do môjho apríl vedro, a s trochou šťastia
že bude iba jeden tam a môj čas bol konštantný v tom zmysle,
vzhľadom k tomu, keď som sa pozrieť cez veľa ľudí,
že to bude trvať oveľa dlhšie.
Takže hash tabuľky sú naozaj len lopaty.
Jednoduchý spôsob, ako si o nich myslíte.
>> Takže veľmi dôležitá vec, o hash tabuľka je hašovacej funkcie.
Takže veci, ktoré som práve hovoril, ako vaše prvé písmeno vášho mena
alebo vaše narodeniny mesiac sú to myšlienky, ktoré
Naozaj koreláciu s haš funkcie.
Je to len spôsob, ako rozhodnúť, ktoré vedro Si element ide do, OK?
Takže pre tento pset, môžete sa pozrieť na skoro žiadne funkcie hash chcete.
>> Nemusí to byť vaše vlastné.
Tam sú niektoré z nich naozaj cool out tam, že robiť všetky druhy bláznivé matematiky.
A ak chcete, aby sa vaše Kontrola pravopisu super rýchly,
Ja by som určite pozrite sa do jednej z nich.
>> Ale sú tu aj jednoduchých, ako je výpočtovo
súčet slov, ako je každé písmeno má číslo.
Vypočítajte súčet.
Ktorý určuje vedro.
Majú tiež tie jednoduché, že sú rovnako ako všetky je tu,
všetky B je tu.
Každý jeden z nich.
>> V podstate je to len vám povie, ktoré index poľa Váš element by mal ísť do.
Len rozhodovanie o bucket-- je to všetko funkcia hash.
Takže tu máme príklad, ktorý je len prvé písmeno reťazca
že som práve hovoril.
>> Takže máte nejaké hash, ktorý je práve prvé písmeno vášho reťazca mínus,
ktorá vám dá niektoré číslo medzi 0 a 25.
A to, čo chcete urobiť, je uistite sa, že sa jedná
veľkosť vášho hash table-- koľko vedierka sú.
S mnohými z nich hashovacie funkcie, sú
bude vracať hodnoty, ktoré by mohli je oveľa väčší ako počet segmentov
že ste skutočne v hash tabuľke,
preto je potrebné, aby Uistite sa, a mod tí.
V opačnom prípade to bude hovoriť, oh, mal by byť v vedre 5000
ale máte len 30 vedierka vo vašom hash tabuľky.
A samozrejme, všetci vieme, že je to bude mať za následok v niektorých šialených chýb.
Takže sa uistite, mod od Veľkosť vášho hash tabuľky.
V pohode.
Tak kolízií.
Je každý dobrý tak ďaleko?
Mmhmm?
>> Divákov: Prečo by to vrátiť sa tak masívne hodnotu?
>> SPEAKER 1: V závislosti na algoritme že hash funkcia využíva.
Niektoré z nich budú robiť blázon násobenie.
A to je všetko, ako dostať rovnomerné rozdelenie,
tak to robia niektoré naozaj bláznivé veci, niekedy.
To je všetko.
Ešte niečo?
OK.
>> Tak kolízií.
V podstate, ako som už povedal, v najlepšom prípade,
akýkoľvek vedro sa pozerám do je bude mať jednu vec,
takže nemám pozerať na všetky, že jo?
Ja viem, že buď tam, alebo je to nie, a to je to, čo naozaj chceme.
Ale ak máme desiatky tisíc dátových bodov a menej než tento počet
lopát, budeme mať kolízie, kde nakoniec niečo
bude musieť skončiť v vedierko, ktorý už má prvok.
>> Takže otázka je, čo budeme robiť v tomto prípade?
Čo budeme robiť?
Už sme tam niečo mať?
Máme len vyhodiť?
>> Nie.
Musíme mať na oboch z nich.
Tak tak, že sme zvyčajne to urobiť je to, čo?
Čo je dátová štruktúra sme práve hovorili?
Divákov: spájať zoznam.
SPEAKER 1: spájať zoznam.
Takže teraz, namiesto toho, každá z nich vedierka len mať jeden prvok,
to bude obsahovať prepojený zoznam prvky, ktoré boli zatriedená do neho.
OK, to každý druh si túto myšlienku?
Pretože sme nemohli mať pole pretože nevieme, ako veľa vecí,
sa bude tam.
Spájať zoznam nám umožňuje máme len presný počet, ktorý
sú zatriedená do tohto vedra, nie?
>> Takže lineárne sondovania je v podstate to idea--
to je jeden spôsob, ako sa vysporiadať s bočnom náraze.
Čo môžete urobiť, je, ak v tomto prípad, bobuľové bola zatriedená do 1
a už máme niečo, čo tam jednoducho
ďalej, kým nájdete na prázdnu pozíciu.
To je jediný spôsob, ako s ňou zaobchádzať.
Druhý spôsob, ako zvládnuť je to s tým, čo sme práve
called-- spojené zoznam sa nazýva zreťazenie.
>> Takže táto myšlienka funguje, ak vaše hash tabuľky si myslíte
je oveľa väčšia, než Vaše údaje nastaviť alebo ak vás
skúsiť a minimalizovať reťazenie kým je to nevyhnutne potrebné.
Takže jedna vec je lineárny sondovania samozrejme znamená,
že vaše hash funkcie nie je tak užitočný
pretože budete skončiť s použitím vaše hash funkcie, dostať do bodu,
ste LINEAR sondy až do nejaké miesto, ktoré je k dispozícii.
Ale teraz, samozrejme, čokoľvek iný, že skončí tam,
budete musieť hľadať ešte ďalej.
>> A je tu oveľa viac Hľadanie náklady, ktoré
ide do zadania prvok v hash tabuľke, nie?
A teraz, keď idete a pokúsiť sa nájsť berry znova, budete to hash,
a to bude hovoriť, oh, pozrite sa do vedra 1,
a to nebude v vedre 1, takže ste
bude musieť prejsť cez zvyšok z nich.
Tak to je niekedy užitočná, ale vo väčšine prípadov,
budeme hovoriť, že reťazenie je to, čo chcete robiť.
>> Tak sme o tom hovorili skôr.
Dostal som kúsok pred seba.
Ale reťazenie je v podstate, že každý vedierko v hash tabuľke
je len spájať zoznam.
>> Takže ďalší spôsob, alebo viac technických spôsobom, myslieť na hash tabuľky
je to, že je to len pole spojových zoznamov, ktoré
keď ste písanie slovník a vy sa snažíte načítať,
myslieť na to, ako pole spojových zoznamov
bude to oveľa jednoduchšie pre vás inicializovať.
>> Divákov: Tak hash tabuľka má vopred určenú veľkosť,
ako [nepočuteľné] lopát?
>> SPEAKER 1: Správne.
Tak to má stanovený počet vedierka, že ste determine--
ktoré ste chlapci mali pokojne hrať.
To môže byť docela v pohode aby videli, čo sa stane,
ako si zmeniť počet segmentov.
Ale jo, to má nastaviť počet segmentov.
Čo umožňuje, aby sa zmestili ako mnoho prvkov, ako budete potrebovať
je oddelený reťazenie, kde vás spojili zoznamy v každom segmente.
To znamená, že vaše hash tabuľky bude presne veľkosť
že ju musí byť, nie?
To je celý zmysel spojových zoznamov.
V pohode.
>> Takže tam všetci v poriadku?
Dobrá.
Ah.
Čo sa stalo?
Naozaj teraz.
Hádajte, niekto ma zabíja.
>> OK budeme ísť do pokusov, ktoré sú trochu blázon.
Mám rád hash tabuľky.
Myslím, že sú naozaj cool.
Pokusy sú v pohode, taky.
>> Takže má niekto spomenúť, čo to skúsiť je?
Mali ste prešli stručne v prednáške?
Spomínate si druh, ako to funguje?
Divákov: Len som kývol že sme sa ísť cez neho.
SPEAKER 1: Nemáme ísť cez neho.
OK, sme naozaj ísť nad ňou je teraz to, čo hovoríme.
>> Divákov: To je pre vyhľadávacím stromu.
>> SPEAKER 1: Jo.
Je to získavanie strom.
Úžasné.
Takže jedna vec je si všimnúť je, že sme sú pri pohľade na jednotlivé znaky
tu, že jo?
>> Takže pred našou hash funkcií, sme sa pozerali na slová ako celku,
a teraz sa pozeráme viac na znaky, nie?
Takže máme Maxwell sem a Mendel.
Takže v podstate try-- spôsob, ako myslieť o tom, že každý stupeň je tu
je rad písmen.
Takže toto je váš koreňový uzol tu, že jo?
To má všetky znaky abeceda na začiatku každého slova.
>> A to, čo chcete urobiť, je povedzme, OK, máme nejaké M slovo.
Ideme sa pozrieť na Maxwell, tak ideme do M. a M bodov na celý
ďalšie pole, kde každý slovo, ak tam
je slovo, ktoré má ako druhé písmeno,
ako dlho ako tam je to slovo, ktoré má B ako druhé písmeno,
bude mať ukazovateľ bude nejaké ďalšie pole.
>> Je tu asi nie je slovo, ktoré MP niečo,
takže v polohe P v tejto polia, bolo by to jednoducho byť NULL.
To by povedal, OK, nie je slovo ktorý M nasledované P, OK?
Takže ak si myslíme, že o tom, každý jeden z týchto menších vecí
je v skutočnosti jedna z nich veľké pole od A po Z.
Takže to, čo by mohlo byť jednou z vecí, že je tak trochu navrátení skúsiť?
>> Divákov: veľa pamäte.
>> SPEAKER 1: Je to ton pamäti, že jo?
Každý z týchto blokov tu predstavuje 26 miest, 26 prvkov poľa.
Takže sa snaží dostať neuveriteľne priestor ťažké.
>> Ale oni sú veľmi rýchle.
Tak neuveriteľne rýchlo, ale Naozaj priestor neefektívne.
Druh prísť ktorý z nich chcete.
Jedná sa o naozaj cool pre pset, ale oni zaberajú veľa pamäte,
takže si privlastniť.
Jo?
>> Divákov: Bolo by možné nastaviť vyskúšať a potom sa
Akonáhle budete mať všetky údaje v ňom, že ste need--
Ja neviem, či to bude mať zmysel.
Bol som ako sa zbaviť všetkých Znaky NULL, ale potom
nebudete môcť indexu them--
>> SPEAKER 1: Stále potrebujú.
>> Divákov: - rovnakým spôsobom zakaždým.
SPEAKER 1: Jo.
Musíte sa znaky NULL, aby ak viete, že to nie je tam slovo.
Ben sa máte niečo, čo chcete?
OK.
Tak jo, ideme ísť trochu viac
do technických podrobností za snažiť a pracovať na príklade.
>> OK, tak je to to isté.
Vzhľadom k tomu, v prepojenom zozname, naše hlavné druh of-- čo je to slovo, ktoré som chcel? -
ako stavebný blok bol uzol.
V pokuse, máme tiež uzol, ale je to definované inak.
>> Takže máme nejaký bool, že znamená, či slová skutočne
existuje na tomto mieste, a potom máme nejaké pole here-- alebo skôr,
To je ukazovateľ na Polia 27 znakov.
A to je pre, v tomto prípade, to 27-- Som si istý, všetci z vás sú ako, počkajte,
tam je 26 písmen v abecede.
Prečo máme 27?
>> Takže v závislosti na spôsob, ako realizovať to,
To je z pset, že povolené apostrofy.
Takže to je dôvod, prečo navyše jeden.
Budete mať tiež v niektorých prípady null terminačných
je zahrnutá ako jeden z znaky, že to nemá byť,
a to je to, ako skontrolovať, zistiť, či je to koniec slova.
Ak máte záujem, pozrite sa Kevin video na study.cs50,
ako aj Wikipedia má niektoré dobré zdroje tam.
>> Ale my ideme prejsť len tak o tom, ako môžete pracovať na pokus
ak ste dal dnes.
Takže tu máme super jednoduchá tu, že má slová "BAT" a "zoom" v nich.
A ako vidíme tu, tento malý priestor tu
reprezentuje našu bool, že hovorí, áno, je to slovo.
A potom to má našu pole znakov, nie?
>> Tak sme sa ísť cez hľadania "BAT" v tomto pokuse.
Takže začať hore, nie?
A my vieme, že b zodpovedá druhý index, druhý prvok
V tomto poli, pretože a b.
Takže približne druhý.
>> A hovorí, OK, v pohode, z toho, že do ďalšie pole, pretože keď si spomenieme,
je to tak, že každý z nich v skutočnosti obsahuje prvok.
Každý jeden z týchto polí obsahuje ukazovateľ, že jo?
To je dôležitý rozdiel, aby sa.
>> Viem, že to bude be-- snaží sa naozaj ťažké sa dostať na prvýkrát,
takže aj keď je to druhý alebo tretí čas
a je to stále trochu zo zdanlivo ťažké,
Sľubujem, že keď idete na hodinky zajtra krátky znova,
to bude asi robiť oveľa väčší zmysel.
To trvá veľa tráviť.
Ja ešte niekedy som ako, počkaj, čo je to vyskúšať?
Ako mám použiť?
>> Preto sme B v tomto prípade, ktorý je naším druhým index.
Keby sme mali, povedzme, c alebo d alebo iné písmeno,
musíme zmapovať to späť do indexu nášho poľa, ktoré, ktoré zodpovedá.
Tak by sme brať ako rchar a my sme odpočítať off mapovať do 0 do 25.
Všetci dobre, ako Mapa naše postavy?
OK.
>> Tak ideme na druhú a my vidieť, že, áno, to nie je NULL.
Môžeme prejsť k tomuto ďalšiemu poli.
Tak ideme na tejto ďalšie pole tu.
>> A my hovoríme, OK, teraz je potrebné zistiť, či je tu.
Je null alebo to robí vlastne vpred?
Tak vlastne pohybuje odovzdal v tomto poli.
A my hovoríme, OK, t je náš posledné písmeno.
Tak sme sa ísť do t na indexe.
A potom sme sa dopredu pretože je tu ešte jeden.
A toto hovorí v podstate to, že áno, sa hovorí, že je slovo here--
že ak budete postupovať podľa tohto cesta, ste dorazili
na slová, ktoré ako vieme, je "bat".
Áno?
>> Divákov: Je štandardné, aby toto ako index 0 a potom akúsi na 1
alebo mať na konci?
>> SPEAKER 1: Nie
Takže ak sa pozrieme späť na našej Vyhlásenie tu, je to bool,
tak je to jeho vlastný element v uzle.
Takže to nie je súčasťou poľa.
V pohode.
Takže keď sme dokončiť naše slovo a my sme na tomto poli, to, čo chceme robiť
je vykonať kontrolu na toto slovo.
A v tomto prípade by to vrátiť áno.
>> Takže v takom prípade, vieme, že "zoo" - poznáme ako človeka, ktorý "zoo" je slovo,
že jo?
Ale skúsiť by tu hovoria, nie, to nie.
A to by som povedal, že preto, že sme neboli označené ako slovo tu.
Aj napriek tomu, že môžeme prejsť až do tohto poľa,
Tento pokus by povedal, že nie, zoo nie je v slovníku
pretože nemáme označené ako také.
>> Takže jeden spôsob, ako to urobiť that-- oh, sorry, toto.
Takže v tomto prípade, "zoo" nie je slovo, ale to je v našom pokuse.
Ale v tomto jednom, že by sme si to želajú predstaviť slovo "kúpele", čo sa stane,
je sledujeme through-- B, A, t.
Sme v tomto poli, a ideme hľadať h.
>> V tomto prípade, kedy sa pozrieť na ukazovateľ na h,
to ukazuje na NULL, OK?
Takže ak je to výslovne ukázal na iné pole,
predpokladať, že všetky ukazovatele V tomto poli sa ukazuje na hodnotu null.
Takže v tomto prípade, h sa ukazuje na hodnotu null, takže nemôžeme nič robiť,
tak to by tiež vrátiť false, "kúpeľ" nie je tu.
Takže teraz sme vlastne ísť cez
ako by sme vlastne povedať, že "zoo" má v našom pokuse.
Ako môžeme vložiť "zoo" do nášho pokusu?
Takže rovnakým spôsobom, ako sme začali náš spájať zoznam, začneme pri koreni.
Ak ste na pochybách, začnite koreň z týchto vecí.
>> A budeme hovoriť, OK, z.
z existuje v tejto, a to robí.
Takže ste sa presťahovali na váš ďalší polia, OK?
A potom na ďalšie, hovoríme, OK, to o existuje?
To robí.
To znova.
>> A tak sa na našej ďalšej, sme povedali, OK, "zoo" už tu existuje.
Všetko, čo musíme urobiť, je nastaviť to rovná na pravda, že je tam slovo.
Ak ste sledoval všetko až do tohto bodu,
je to slovo, tak len nastavte ju na hodnotu, napr.
Áno?
>> Divákov: Tak to robí znamená, že "ba" je slovo, ktoré tiež?
>> SPEAKER 1: Nie
Takže v tomto prípade, "ba" by sme sa dostali Tu by sme povedať, je to slovo,
a stále by byť.
OK?
Mmhmm?
>> Divákov: Takže akonáhle je to slovo, a vy hovoríte áno, potom to
bude obsahovať ísť do m?
>> SPEAKER 1: Tak to má čo do činenia with-- ste načítava to v.
Hovoríte, že "zoo" je slovo.
Keď idete do check-- ako, že chcete povedať,
znamená "zoo" existujú v tomto slovníku?
Ste len bude hľadať "zoo" a potom skontrolujte, či je to slovo.
Vy ste nikdy pohybovať až m, pretože to nie je
to, čo hľadáte.
>> Ak teda vlastne chcel pridať "kúpeľ" v tomto pokuse,
budeme robiť to isté ako sme to urobili s "zoo"
s výnimkou by sme vidieť, že keď sme pokúsiť sa dostať h, to neexistuje.
Takže si môžete myslieť na to, ako sa snaží pre pridanie nového uzla do prepojeného zoznamu
tak by sme museli pridať ďalšie jeden z týchto polí, ako tak.
A potom to, čo robíme, je jednoducho nastaviť h prvok tohto poľa ukazuje na to.
>> A potom to, čo by chcel robiť?
Pridať sa rovná pravda pretože je to slovo.
V pohode.
Ja viem.
Pokusy nie sú najviac vzrušujúce.
Ver mi, ja viem.
>> Takže jedna vec je si uvedomiť, s pokusoch, Povedal som, že sú veľmi efektívne.
Preto sme, videli zaberajú veľa miesta.
Sú to trochu mätúce.
Tak prečo by sme vôbec používať tieto?
Používame tieto, pretože sú neuveriteľne efektívna.
>> Takže ak ste niekedy hľadáte up slová, ste len
ohraničené dĺžkou slova.
Takže ak hľadáte slovo, ktoré je v dĺžke piatich,
ste len niekedy musieť aby u väčšiny piatich porovnaniach, OK?
Takže je to v podstate konštantný.
Rovnako ako vkladanie a vyhľadávanie sú v podstate konštantné čas.
>> Takže ak môžete niekedy niečo v konštantnom čase,
je to tak dobré, ako to dostane.
Nemôžete lepší ako konštantný čas na tieto veci.
Tak, že je jedným z obrovské plusy pokusov.
>> Ale je to veľa priestoru.
Takže tak nejako sa rozhodnúť, čo je pre vás dôležitejšie.
A na dnešných počítačoch, priestor, ktorý pokus môže trvať až
Možno, že nemá vplyv na si, že veľa, ale možno
máte čo do činenia s niečím ktorá má ďaleko, ďaleko viac vecí,
a pokus jednoducho nie je rozumné.
Áno?
>> Publikum: Počkaj, takže budete mať 26 písmená jedného každého?
>> SPEAKER 1: Mmhmm.
Jo, máte 26.
Máte nejaký je slovo, značka a potom Máte 26 ukazovateľov v každom jednom.
A oni point--
>> Divákov: A každý 26, že každý z nich má 26?
>> SPEAKER 1: Áno.
A to je dôvod, prečo, ako môžete vidieť, že sa rozširuje veľmi rýchlo.
Dobrá.
Takže budeme sa dostať do stromov, ktoré Mám pocit, že je jednoduchšie a pravdepodobne
je pekný malý odklad z pokusov tam.
Takže dúfajme, že väčšina z vás ktoré videl strom.
Nie ako celkom Tie mimo, ktoré som
ak nie sú niekto vedieť šiel vonku v poslednej dobe.
Išiel som jablko vychystávanie tento víkend a oh môj bože, to bolo krásne.
Nevedel som, že listy môže vyzerať, že dosť.
>> Takže je to len strom, nie?
Je to len nejaký uzol, a to poukazuje na veľa ďalších uzlov.
Ako vidíte tu, je to druh opakujúce sa téma.
Uzly ukazujúci uzlov je druh Podstatou mnohých dátových štruktúr.
Záleží len na tom, ako nechať upozorniť na seba
a ako sme sa prejsť skrze ne a ako
vložiť veci, ktoré určuje ich odlišné charakteristiky.
>> Takže len niektoré pojmy, ktorý som používal predtým.
Tak root je to, čo je na samom vrchole.
to je miesto, kde sme sa vždy začať.
Môžete si ju predstaviť ako hlavy tiež.
Ale stromy, máme tendenciu odkazujú na to ako root.
>> Čokoľvek na spodnej here-- na veľmi, veľmi bottom--
sú považované za listy.
Tak to ide ruka v ruke s Celý strom vec, nie?
Listy sú pri okrajoch stromu.
>> A potom máme tiež pár Podmienky hovoriť o uzloch vo vzťahu
k sebe navzájom.
Takže máme rodičia, deti a súrodenci.
Takže v tomto prípade, je 3 rodič 5, 6 a 7.
Takže rodič, čo je o krok vyššie, čo ste
s odkazom na to, tak jednoducho ako rodokmeň.
Dúfajme, že je to všetko trochu trochu viac intuitívne než pokusov.
>> Súrodenci sú všetky, ktoré majú tá istá materská, nie?
Sú na rovnakej úrovni tu.
A potom, keď som bol hovorí, deti sú len
čo je jeden krok ďalej uzol v otázke, OK?
V pohode.
Tak binárny strom.
Môže niekto hádať, na jednom z vlastnosti binárneho stromu?
>> Divákov: Max dva lístky.
>> SPEAKER 1: Správne.
Takže max dvoch listov.
Takže v tomto jednom skôr, mali sme tento ktorá mala tri, ale v binárnom strome,
Máte-max dvoch detí na rodičov, že jo?
Je tu ďalší zaujímavá vlastnosť.
Vie niekto, že?
Binárny strom.
>> Takže binárny strom bude mať všetko na the-- toto nie je sorted--
ale v zoradené binárneho stromu, všetko na pravej strane
je väčšia ako pôvodná, a všetko, čo na ľavej strane
je menšia než rodičia.
A to bol kvíz Otázka pred, tak dobré to vedieť.
Takže spôsob, ako definovať to, opäť máme ďalší uzol.
To vyzerá veľmi podobne ako čo?
Dvojnásobne
>> Divákov: spojových zoznamov
>> SPEAKER 1: dvojitý spájať zoznam, nie?
Ak teda nahradiť tento s predchádzajúcou a nasledujúce,
by to bolo dvojnásobne spájať zoznam.
Ale v tomto prípade sme sa vlastne sú vľavo a vpravo, a je to.
Inak je to úplne rovnaké.
Stále máme prvok hľadáte,
a stačia dva ukazovatele bude, čo bude ďalej.
Jo, tak binárny vyhľadávací strom.
Ak sme si všimli, všetko na tu je väčší than--
alebo všetko ihneď aby tu
je väčšia než, všetko Tu je menšia ako.
>> Takže, ak by sme mali prehľadávať, by mal vyzerať veľmi blízko k binárne vyhľadávanie
tu, že jo?
Okrem namiesto hľadania na polovicu poľa,
sme sa len pri pohľade na ľavú strane alebo na pravej strane stromu.
Tak to je trochu jednoduchšie, myslím.
>> Takže ak vaša koreň je NULL, samozrejme je to len falošná.
A ak to tam je, samozrejme, že je to pravda.
Ak je to menej, než sme sa hľadať vľavo.
Ak je väčší ako hľadáme právo.
Je to presne ako binárne vyhľadávanie, len odlišná štruktúra dát
že sme použili.
Miesto poľa, je to len binárny strom.
>> OK, komíny.
A tiež to vyzerá, že my môže mať trochu času.
Ak sa tak stane, som rád, že ísť cez toto všetko znova.
OK, tak komíny.
Pamätá si niekto, čo stacks-- všetky charakteristiky zásobníka?
>> OK, takže väčšina z nás, myslím, jesť v jedálni halls--
čo môžeme neradi.
Ale samozrejme, môžete myslieť na zásobníku doslova len ako hromadu zásobníkov
alebo hromadu vecí.
A čo je dôležité si uvedomiť, že je to
something-- charakteristika že hovoríme, že by-- je LIFO.
Vie niekto, čo to znamená?
Mmhmm?
>> DIVÁKOV: Posledné dnu, prvý von.
>> SPEAKER 1: Dobre, posledný dnu, prvý von.
Takže ak vieme, či sme stohovanie veci up, najjednoduchšie chytiť off--
a snáď jediné, čo môžeme chytiť vypne, ak náš stack je veľký enough--
je to, že horný prvok.
Takže bez ohľadu bol kladený na last-- ako vidíme tu,
čo bol zatlačený na väčšine recently-- je
bude prvý vec, že ​​sme pop off, OK?
>> Takže to, čo tu máme, je ďalšie typedef struct.
To je naozaj len rád rýchlokurz v dátovej štruktúre,
takže je tu veľa hodená na vás chlapci.
Ja viem.
Takže ďalší Struct.
Yay pre stavby.
>> A v tomto prípade, je to nejaký ukazovateľ na pole, ktoré má určitú kapacitu.
Takže to predstavuje náš stack Tu, rovnako ako našej aktuálnej pole
ktoré držia naše prvkov.
A potom tu máme nejaké veľkosti.
>> A zvyčajne, chcete, aby track o tom, aký veľký je váš stack
pretože to, čo sa deje, aby môžete urobiť, je, ak viete, že veľkosť,
to vám umožní povedať, OK, som na plný výkon?
Môžem pridať niečo viac?
A tiež vám povie, kde horná časť zásobníka
tak viete, čo ste môže skutočne vzlietnuť.
A to vlastne bude tu trochu jasnejšie.
>> Takže pre stisk, jednu vec, ak máte bol vždy realizovať tlačiť,
ako som práve povedal, vaše zásobník má obmedzenú veľkosť, je to tak?
Naše pole mal nejakú kapacitu.
Je to pole.
Je to pevné veľkosti, takže je potrebné, aby Uistite sa, že nie sme uvedení viac
do nášho poľa, než sme skutočne priestor pre.
>> Takže, keď budete vytvárať tlak funkcie, prvá vec, ktorú urobiť, je povedať, OK,
mám miesto vo svojom stacku?
Pretože keď to neurobím, prepáč, Nemôžem uložiť prvok.
Keď to urobím, potom budete chcieť uložiť je na vrchole zásobníka, je to tak?
>> A to je dôvod, prečo máme sledovať našej veľkosti.
Ak nebudeme mať prehľad o našej veľkosti, nevieme, kam to dať.
Nevieme, ako veľa vecí, sú v našom poli už.
Ako samozrejme existujú spôsoby, ako že možno by ste mohli urobiť.
Dalo by sa inicializovať všetko NULL a potom skontrolujte, či máte najnovšiu verziu NULL,
ale oveľa jednoduchšie vec je jednoducho povedať, OK, sledovať veľkosti.
Rovnako ako viem, že mám štyri prvky v mojom poli, takže ďalšia vec,
že sme dali na, sme bude ukladať na indexe 4.
A potom, samozrejme, to znamená, že ste úspešne tlačil niečo
na stacku, ste chcete zvýšiť veľkosť
takže viete, kde ste tak že môžete tlačiť viac vecí na.
>> Takže ak sa snažíme pop niečo z kôpky,
čo by mohlo byť prvá vec, že chceme skontrolovať?
Snažíte sa vziať niečo z vášho stacku.
Ste si istý, že je to niečo v zásobníku?
Nie.
Takže to, čo by sme mohli chcieť skontrolovať?
>> Divákov: [nepočuteľné].
SPEAKER 1: Skontrolujte, či veľkosť?
Veľkosť.
Takže chceme skontrolovať, či Naša veľkosť je väčšia ako 0, OK?
A ak áno, potom chceme znížiť Naše veľkosť od 0 a vrátiť to.
Prečo?
>> V prvom z nich sme boli tlačenie, to tlačil nás
na veľkosti a potom priebežne aktualizovaným veľkosti.
V tomto prípade sme dekrementování veľkosť a potom ju zložil, šklbanie ju
z našej rady.
Prečo by sme mohli urobiť, že?
Takže ak mám jednu vec na mojom stacku, Čo by bola moja veľkosť v tomto mieste?
1.
>> A kde je prvok 1 uložené?
Na čo index?
Publikum: 0.
SPEAKER 1: 0.
Takže v tomto prípade sme Vždy je potrebné vykonať sure--
miesto vrátenia veľkosť mínus 1, pretože sme
vieme, že naša prvok je bude uložený na 1 menej
bez ohľadu na našu veľkosť je, toto len sa o to postarám.
Je to o niečo viac elegantný spôsob.
A my len decrement otázky veľkosť a potom sa vrátiť veľkosť.
Mmhmm?
>> Divákov: Myslím, že len všeobecne, prečo by to dátová štruktúra
byť výhodné?
>> SPEAKER 1: Záleží na vašom kontextu.
Tak pre niektoré z teórie, ak pracujete with-- OK,
dovoľte mi, aby som zistil, či je prospešné jeden ktorá je prospešná pre viac ako vonku
ČS.
U komínov, kedykoľvek budete potrebovať sledovať niečo, čo
sa naposledy pridaný je, keď budete chcieť použiť zásobník.
>> A ja si nemyslím, že je dobrý Príkladom, že práve teraz.
Ale kedykoľvek posledná čo je pre vás najdôležitejšie,
to je, keď stack bude užitočné.
Snažím sa, že ak tam je dobrý pre to.
Ak by som myslieť na dobrý príklad v ďalšej 20 minút a to sa určite povedať.
>> Ale celkovo, či je niečo, ako som povedal, že väčšina, kde posledná
Najdôležitejšie je, že sa kde balík vstúpi do hry.
Vzhľadom k tomu, fronty sú trochu naopak.
A všetky tie malé psy.
Nie je to skvelé, že jo?
Mám pocit, ako by som mal len mať zajačik videá
priamo v centre Sekcia pre vás
pretože sa jedná o intenzívny časť.
>> Tak front.
V podstate front je ako línia.
Vy Som si istý, použitie tejto každodenné, rovnako ako v našich jedálňach.
Takže musíme ísť a dostať naše zásobníky, som
že máte čakať vo fronte Presunutie alebo dostať svoje jedlo.
>> Tak tu je rozdiel je to, že toto je FIFO.
Takže ak LIFO bola naposledy v prvom out, FIFO je first in, first out.
Tak toto je miesto, kde čo si dať Na prvý je vaša najdôležitejšia.
Takže ak ste čakali v line-- môžete
Predstavte si, že ste šiel do choď na nový iPhone
a to bolo stack, kde posledná osoba v súlade ju dostal ako prvý,
ľudia by sa navzájom zabíjali.
>> Takže FIFO, sme všetci veľmi dobre sa tu v reálnom svete,
a to všetko má čo do činenia s naozaj druh obnovovať celý tento riadok
a fronty štruktúru.
Takže zatiaľ čo v zásobníku, máme tlačiť a pop.
S fronty, máme Pridať do zoznamu a dequeue.
Pridať do zoznamu tak v podstate znamená, dať na chrbát,
a Dequeue prostriedky vziať off spredu.
Takže naša dátová štruktúra je trochu zložitejšie.
Máme druhú vec, ako sledovať.
>> Takže bez hlavy, to je presne to, zásobník, nie?
To je rovnakej konštrukcie ako zásobník.
Jediné, čo teraz iné je, že sme túto hlavu, ktorá to, čo si myslíte, že
bude sledovať?
>> Divákov: prvý z nich.
>> SPEAKER 1: Správne, Prvá vec, ktorú sme dali v.
Hlava našej fronty.
Ten, kto je v prvej línii.
Dobre, takže ak urobíme zaradenie do fronty.
Opäť platí, že sa niektorý z Tieto dátové štruktúry,
pretože máme čo do činenia s radom, musíme skontrolovať, či máme priestor.
>> To je niečo ako ja, hovorí vy, ak otvoríte súbor,
je potrebné skontrolovať na null.
S niektorou z týchto komínov a fronty, budete potrebovať
zistiť, či tam je priestor, pretože sme rokovania s pevnou veľkosťou poľa,
ako vidíme here-- 0, 1 všetko až 5.
Takže to, čo robíme v tomto prípade je kontrola aby zistil, či ešte máme priestor.
Je naša veľkosť menšia ako kapacita?
>> Ak tomu tak je, musíme uložiť na chvost a obnovujeme našu veľkosť.
Takže to, čo je možné, že chvost je v tomto prípade?
To nie je výslovne napísané.
Ako by sme to uložiť?
Čo by chvost byť?
>> Takže poďme sa prejsť tento príklad.
Tak toto je pole o veľkosti 6, nie?
A máme teraz, naša veľkosť je 5.
A keď sme sa dať do, bude to ísť do piateho indexu, nie?
Tak skladuje v chvosta.
>> Ďalším spôsobom, ako napísať chvost by len naše pole v indexe veľkosti, nie?
To je veľkosť 5.
Ďalšia vec je ísť do 5.
V pohode?
OK.
Je to trochu zložitejšie dostane keď začneme hrať s hlavou.
Áno?
>> Divákov: Znamená to, že sme by deklarovali pole, ktoré
bolo päť prvkov dlhá a potom budeme pridávať na neho?
>> SPEAKER 1: Nie
Takže v tomto prípade sa jedná o zásobník.
To by byť vyhlásený za ako pole o veľkosti 6.
A v tomto prípade sme stačí jedno voľné miesto.
>> OK, takže jedna vec je v tomto prípade, ak je naša hlava je na 0,
potom stačí ho pridať na veľkosti.
Ale to dostane trochu zložitejšie pretože v skutočnosti, že
nemajú snímku za to, takže budem
k tomu jedno, pretože to nie je tak jednoduché, akonáhle sa
začať, ako sa zbaviť vecí.
A tak vzhľadom k tomu, so zásobníkom si len niekedy
sa starať o to, čo je veľkosť keď pridávate niečo ďalej,
s frontu je tiež nutné, aby sa Uistite sa, že vaša hlava sa účtuje,
pretože super vec o frontoch je, že ak nie ste na plný výkon,
môžete skutočne robiť to sa zalomia okolo.
>> OK, tak jeden thing-- oh, to je hrozné krieda.
Jedna vec, aby zvážila, je to tak.
Budeme jednoducho päť.
OK, takže budeme tvrdí, že hlava je tu.
To je 0, 1, 2, 3, 4.
>> Hlava je tam, a prosím, veci v nich.
A chceme pridať niečo, že jo?
Takže to, čo potrebujeme viem, je, že hlava je vždy
bude sa pohybovať sem a potom spätnej slučky okolo, OK?
>> Tak toto front má priestor, nie?
Má priestor na samom počiatku, druh opak toho.
Takže to, čo musíme urobiť, je, že sme je potrebné vypočítať chvost.
Ak viete, že vaše hlava nepohybuje, chvost
je len vaša poľa na index veľkosti.
>> Ale v skutočnosti, ak používate front, vaša hlava je pravdepodobne aktualizovaný.
Takže to, čo musíte urobiť, je vlastne výpočet chvost.
Takže to, čo robíme, je to vzorec tú, ktorú som ťa nechať
vy myslíte o, a potom budeme o tom hovoriť.
Tak toto je kapacita.
>> Takže to bude v skutočnosti vám, ako to urobiť.
Pretože v tomto prípade, čo?
Naša hlava je na 1, naša veľkosť je 4.
Ak by sme mod, že 5, dostaneme 0, čo je miesto, kde by sme mali vstup za to.
>> A tak v ďalšom prípade, keby sme k tomu,
hovoríme, OK, poďme dequeue niečo.
Sme dequeue to.
Berieme sa tento prvok, je to tak?
>> A teraz naša hlava smeruje tu a chceme pridať ďalšie veci.
To je v podstate späť na našej línii, nie?
Fronty môžu obaliť okolo poľa.
To je jeden z hlavných rozdielov.
Komíny, môžete to urobiť.
>> S front, môžete pretože všetko, na čom záleží
je to, že viete, čo bol naposledy pridaný.
Vzhľadom k tomu, všetko sa bude pridaný do Tento doľava smer, v tomto prípade,
a potom zabaliť okolo, môžete pokračovať v zavádzaní nových prvkov
v prednej časti poľa pretože to nie je naozaj
predné poľa už.
Môžete myslieť na začiatku pole ako, kde sa vaša hlava je v skutočnosti.
>> Takže tento vzorec je, ako môžete vypočítať chvost.
Má to zmysel?
OK.
OK, dequeue, a potom vy máte 10 minút
aby sa ma nejaké objasňovať otázky Chcete, pretože viem, že je to šialené.
>> V poriadku, takže v rovnakom way-- Ja neviem, či si chlapci všimli,
ale SK je o vzory.
Veci sú do značnej miery To isté, len s malými vylepší.
Tak to isté tu.
Musíme zistiť, či je skutočne mať niečo v našej fronte, nie?
Povedať, OK, je naša veľkosť väčšia ako 0?
V pohode.
>> Ak sa tak stane, potom sa presunieme našu hlavu, ktorá je to, čo som tu práve preukázal.
Aktualizujeme našu hlavu, aby sa ešte raz.
A potom sme decrement naše Veľkosť a vráti prvok.
>> Tam je oveľa konkrétnejšie kód na study.cs50.net,
a vrelo odporúčam ísť cez to, ak budete mať čas,
aj keď je to len pseudo-kódu.
A ak vy chcete hovoriť cez že so mnou jeden na jedného, ​​dajte mi prosím
vedieť.
Ja by som rád.
Dátové štruktúry, ak budete mať CS 124, budete
viem, že dátové štruktúry dostať veľmi sranda, a to je len začiatok.
>> Takže viem, že je to ťažké.
To je v poriadku.
Bojujeme.
Stále robím.
Takže sa nemusíte príliš starať o to.
>> Ale to je v podstate Vašimi rýchlokurz v dátových štruktúrach.
Viem, že je to veľa.
Je tu niečo, čo nám by som ísť znova?
Čokoľvek chceme prebrať?
Áno?
>> Divákov: Pre tento príklad, tak nový chvost je na 0 cez to?
SPEAKER 1: Áno.
Divákov: OK.
Takže prechádza, budeš mať 1 a 4 nebo--
>> SPEAKER 1: Takže ste hovorila, keď chceme ísť to urobiť znova?
Divákov: Jo.
Takže ak ste sa prísť na out--, kde sú budete výpočet chvost z v tom, že?
>> SPEAKER 1: Takže chvost Bol in-- zmenil som to.
Takže v tomto prípade tu, to bolo polia sa pozeráme, OK?
Takže máme veci v 1, 2, 3 a 4.
Takže máme naša hlava je rovná 1 na tento bod, a naša veľkosť je rovná 4
na tomto mieste, že jo?
>> Vy všetci sa zhodujú, že je to tak?
Takže robíme hlavu plus veľkosť, ktorá nám dáva 5, a potom sme mod o 5.
Dostávame 0, čo nám hovorí, že 0 je kde je náš chvost, kde máme priestor.
>> Divákov: Čo je čiapka?
>> SPEAKER 1: kapacita.
Prepáčte.
Tak to je veľkosť vášho poľa.
Áno?
>> Divákov: [nepočuteľné] pred vrátime prvok?
>> SPEAKER 1: Takže sa pohybujeme hlavou alebo sa vrátiť v okamihu, kedy?
Ak teda presunúť jeden, decrement veľkosť?
Vydrž.
Rozhodne som zabudol ďalšie.
To nič.
Nie je iný vzorec.
Jo, by sa chcete vrátiť hlava a potom ju vrátiť späť.
>> Publikum: OK, pretože v tomto bod, hlava bola na 0,
a potom sa chcete vrátiť index 0 a potom sa hlava 1?
>> SPEAKER 1: Správne.
Myslím, že je tu ďalší vzorec niečo ako toto.
Nemám ju na vrchole mojej hlavy, ako Nechcem, aby vám ten zlý.
Ale myslím, že je to úplne v poriadku, aby povedzme, OK uložte túto element-- čokoľvek
element hlava je je-- decrement vaše veľkosť, pohybovať hlavou nad a návrat
čo to je element.
To je úplne v poriadku.
OK.
Mám pocit, že to nie je ako most-- nie ste
ísť pešo odtiaľto ako, áno, ja viem pokusov.
Mám to všetko.
To je v poriadku.
Sľubujem.
Ale dátové štruktúry sú niečo, čo to trvá veľa času si zvyknúť.
Pravdepodobne jeden z najťažších veci, myslím, že v priebehu.
>> Tak to určite má opakovanie a pri pohľade at-- I
to naozaj neviem previazané zoznamy kým som urobil príliš veľa s nimi,
rovnakým spôsobom, že som to neurobil naozaj pochopiť ukazovatele
kým som sa musel učiť pre dvoch rokov a robiť svoje vlastné psets s ním.
To si vyžaduje veľa zdôraznenie a času.
A nakoniec, bude to trochu na tlačidlo.
>> Ale do tej doby, pokiaľ máte typ porozumenie na vysokej úrovni, čo
Tieto robiť, ich výhody a cons-- čo je to, čo
naozaj sa snažia zdôrazniť, najmä v úvodnej kurze.
Rovnako ako, prečo by sme použiť skúste cez pole?
Rovnako ako to, čo sú pozitíva a zápory každého z nich?
>> A pochopenie kompromisy Medzi každou z týchto štruktúr
je to, čo je oveľa dôležitejšie práve teraz.
Tu môže byť jeden blázon otázka alebo dva, ktoré je
bude vás žiadať, aby ste implementovať tlačiť alebo realizovať pop alebo zaradenie do fronty a Dequeue.
Avšak vo väčšine prípadov, že majú vyššiu úroveň porozumenia a viac
na intuitívne pochopenie je oveľa dôležitejšie, než v skutočnosti
budú môcť na jeho vykonanie.
>> To by bolo naozaj úžasné, keby ste všetci mohol ísť von a ísť realizovať vyskúšať,
ale chápeme, že to nemusí byť nutne najrozumnejšie vec, ktorú práve teraz.
Ale môžete v pset, ak chcete na, a potom budete mať prax,
a potom možno budete naozaj pochopiť.
Áno?
>> Publikum: OK, tak tie, ktoré sú sme chcel použiť v pset?
Musím použiť jeden z nich?
SPEAKER 1: Áno.
Takže máte na výber.
Myslím, že v tomto prípade môžeme hovoriť o pset trochu
pretože som bežal cez tieto.
Takže vo vašom pset, nemáte výber pokusov alebo hash tabuľky.
Niektorí ľudia sa budú snažiť a použitie bloom filtre,
ale tie technicky nie sú správne.
Vzhľadom na ich pravdepodobnostné charakter, dávajú niekedy falošne pozitívne.
Sú v pohode pohľad do, hoci.
Veľmi odporúčam hľadať na ne minimálne.
Ale máte možnosť voľby medzi hash tabuľky a pokus.
A to bude kedy vložíte do slovníka.
>> A budete musieť vybrať vaše hash funkcie,
budete musieť zvoliť, koľko lopaty máte, a to sa bude líšiť.
Ako keď máte viac vedierka, Možno, že to bude rýchlejšie.
Ale možno, že strácate Veľa priestoru, ktorý tak či onak, hoci.
Musíte na to prísť.
Mmhmm?
>> Divákov: Hovoril ste, že pred tým môžeme použiť aj iné hašovacej funkcie,
že nemusíme vytvoriť hash funkcie?
>> SPEAKER 1: Áno, správne.
Takže doslova pre hash funkciu, ako google "hash funkcie"
a pozrite sa na niektoré tie chladné.
Nie ste Očakáva sa, že stavať vlastné hash funkcie.
Ľudia trávia svoj práca na týchto veciach.
>> Takže sa nemusíte starať o budovanie svojej vlastnej.
Nájsť jednu on-line pre začiatok.
Niektoré z nich budete musieť manipulovať trochu
aby sa ubezpečil, návratové typy zhodovať a kto vie čo ešte, takže na začiatku,
Odporučil by som používať niečo rýchle, že možno práve
hash na prvé písmeno.
A potom, až budete mať, že práca, zahŕňajúce chladnejšie hash funkcie.
Mmhmm?
>> Divákov: Bude skúste byť alebo efektívne, ale len ťažšie, like--
>> SPEAKER 1: Takže skúsiť, myslím, je intuitívne ťažko realizovať
ale je veľmi rýchly.
Avšak, zaberá viac miesta.
Opäť platí, že môžete optimalizovať obe tie rôzne spôsoby, a existujú spôsoby, ako to--
Divákov: Ako sme triedi na to?
Má matter--
>> SPEAKER 1: Takže ste sa stupňom normálnym spôsobom.
Budeš sa triedi na dizajn.
Podľa toho, ako to urobíte, budete chcieť, aby uistite sa, že je to tak elegantné, ako to môže byť
a tak účinný, ako to môže byť.
Ale ak sa rozhodnete vyskúšať alebo hash Tabuľka, tak dlho, ako to funguje,
sme radi, s tým.
A ak používate niečo, čo hash na prvé písmeno, to je v poriadku,
Trebárs ako jeho dizajnu.
Sme tiež dosiahnuť bod v tomto semester--
Ja neviem, či vás chlapci noticed-- ak ste
pset stupňa klesať trochu vzhľadom k designu a ktovie čo ešte,
to je úplne v poriadku.
Začína to do bodu, kde sa vaše programy sú stále zložitejšie.
Existuje viac miesta môžete zlepšiť.
>> Takže je to úplne normálne.
To neznamená, že ste horšie, na vašom pset.
Je to len my je ťažšie na vás teraz.
Takže všetci cítia to.
Len som sa triedi všetky vaše psets.
Viem, že každý sa cíti to.
>> Takže sa nemusíte obávať, že.
A ak máte akékoľvek otázky týkajúce sa predchádzajúce psets alebo spôsoby, ako môžete zlepšiť,
Snažím sa a komentovať konkrétne miesta, ale niekedy je to neskoro
a ja som unavený.
Existujú aj iné veci, o dátové štruktúry?
Som si istý, že chlapci naozaj chceš hovoriť o nich už,
ale ak tam sú, som rád, že ísť cez ne, rovnako ako čokoľvek
z prednášky tento rok týždeň alebo minulý týždeň.
>> Viem, že minulý týždeň bol celý preskúmanie, tak Možno sme preskočil nejakú recenziu
z prednášky.
Akékoľvek ďalšie otázky môžem odpovedať?
OK, v poriadku.
No, vy dostanete sa 15 minút skôr.
>> Dúfam, že to bolo čiastočne užitočné aspoň a ja uvidíte chalani budúci týždeň,
alebo vo štvrtok úradné hodiny.
Existujú žiadosti o občerstvenie na budúci týždeň, to je vec?
Pretože som zabudol cukroví dnes.
A ja som priniesol cukroví posledné týždeň, ale bolo to Columbus Day,
tak tam bolo tak šesť ľudí, ktorí sa mal štyri vrecia cukroví pre seba.
Môžem priniesť starburst znova, ak sa vám páči.
Starburst?
OK, to znie dobre.
Majú veľký deň, chlapci.