[Powered by Google Translate] [Časť 6: Menej pohodlné]
[Nate Hardison] [Harvard University]
[To je CS50.] [CS50.TV]
Dobrá. Vitajte v sekcii 6.
Tento týždeň, budeme hovoriť o dátových štruktúr v sekcii,
predovšetkým preto, že tento týždeň je problém nastaviť na spellr
sa celá partia inú dátovú štruktúru prieskumu.
Existuje veľa rôznych spôsobov, ako môžete ísť s týmto problémom set,
a čím viac dátových štruktúr viete o, tým viac cool vecí, ktoré môžete urobiť.
>> Tak poďme začať. Najprv budeme hovoriť o komíny,
zásobníka a fronty dátové štruktúry, ktoré budeme hovoriť o
Komíny a fronty sú naozaj užitočné, keď začneme hovoriť o grafy,
ktoré nebudeme robiť toľko teraz.
Ale sú naozaj dobré pochopiť jednu z veľkých základných dátových štruktúr SK.
Popis v špecifikácii problému set,
ak ste vytiahnite ju hore, hovorí o tom, komíny ako blízky
hromada jedálnych podnosov, že máte v jedálni v jedálňach
kde, kedy jedáleň zamestnancov príde a dá si jedálenský podnosy z potom, čo som vyčistiť je,
oni vyrovnajú im jeden na druhého.
A potom, keď deti prídu do dostať jedlo,
vyťahujú zásobníky off, prvý vrchol jeden, potom jeden pod ním, potom jeden pod tým.
Takže v skutočnosti, prvý zásobník, ktorý jedálenský personál položil je posledný, ktorý sa vzlietlo.
Ten posledný, že jedáleň zamestnanci kladený na je prvý, ktorý sa vzlietlo na večeru.
V problému setu je spec, ktoré si môžete stiahnuť, ak ste tak už neurobili,
Ak hovoríme o modelovanie zásobníka dát ŠTRUKTÚRA pomocou tohto druhu struct.
>> Takže to, čo sme sa sem dostali, je to podobné tomu, čo bolo uvedené v prednáške,
výnimkou v prednáške sme sa prezentovali to s ints ako protiklad k char * s
To bude zásobník, ktorý ukladá, čo?
Daniel? Čo sme uchovávanie v tomto zásobníku?
[Daniel] Strings? >> Sme ukladanie reťazca v tomto zásobníku, presne.
Všetko, čo je potrebné, aby sa za účelom vytvorenia zásobníka je pole
určitej kapacity, ktorá je v tomto prípade,
kapacita bude vo všetkých veľkých písmenách, pretože je to konštanta.
A potom okrem poľa, všetko musíme sledovať je aktuálna veľkosť poľa.
Jedna vec k poznámke, že je to celkom fajn
je to, že sme vytvorenie skladaného dátovú štruktúru na vrchole iné štruktúry dát, polia.
Existujú rôzne spôsoby, ako implementovať stohy.
Budeme to robiť ešte dosť, ale dúfajme, že potom, čo robil na odkazovaných zoznam problémov,
uvidíte, ako si môžete ľahko implementovať balík na vrchole prepojeného zoznamu rovnako.
Ale teraz, budeme držať poľa.
Takže znova, všetko, čo potrebujete, je pole a my stačí sledovať veľkosť poľa.
[Sam] Ospravedlňujem sa, prečo je to, že ste hovoril, že stack je na vrchol reťazcov?
Pre mňa sa zdá, že reťazce sú v zásobníku.
[Hardison] Jo. Sme vytváranie, berieme naše pole dátové štruktúry -
To je veľká otázka. Takže otázka je, prečo, pre ľudí, ktorí sledujú tento on-line,
prečo hovoríme, že zásobník je na vrchole reťazca,
pretože tu to vyzerá, ako sú reťazce vo vnútri zásobníka?
Čo je úplne prípad.
To, čo som mal na mysli, že máme maticový dátovú štruktúru.
Máme celý rad char * s, toto pole reťazcov,
a budeme pridať do, že za účelom vytvorenia skladaný dátové štruktúry.
>> Takže stack je trochu zložitejšie ako pole.
Môžeme použiť pole postaviť stack.
Tak to je, kde môžeme povedať, že zásobník je postavený na vrchole poľa.
Rovnako tak, ako som povedal predtým, môžeme vybudovať zásobník na vrchole prepojeného zoznamu.
Namiesto toho, aby pomocou poľa držať naše prvky,
by sme mohli použiť prepojeného zoznamu držať naše prvky a vytvoriť stoh okolo toho.
Poďme prejsť pár príkladov, pri pohľade na nejaký kód,
vidieť, čo sa vlastne deje.
Na ľavej strane, som hodil dolu, čo to stack struct bude vyzerať v pamäti
ak kapacita bola # definovaný byť štyri.
Máme naše štyri prvok char * pole.
Máme reťazca [0], struny [1], struny [2], struny [3],
a potom, že posledný priestor pre našu veľkosť celé číslo.
Má to zmysel? Dobre.
To je to, čo sa stane, keď to, čo mám robiť, na pravej strane,
ktorý bude môj kód, je len vyhlásiť struct, skladaný struct volal s
To je to, čo dostaneme. Stanovuje tento stopu v pamäti.
Prvá otázka je, čo je obsahom tohto zásobníka struct?
Práve teraz nie sme nič, ale nie sú úplne nič.
Sú tento druh odpadu. Nemáme tušenie, čo je v nich.
Keď sme vyhlásiť zásobník s, sme len hádzanie, že sa na vrchole pamäte.
Je to niečo ako vyhlásenie int i, a nie jeho inicializácii.
Ty nevieš, čo je to tam. Môžete si prečítať, čo je tam,
ale to nemusí byť super užitočné.
Jedna vec, ktorú chcete, aby sa vždy pamätajte na to, je inicializovať, čo je potrebné inicializovať.
V tomto prípade, budeme inicializovať veľkosť nula,
pretože je to dopadne ako pre nás veľmi dôležité.
Mohli by sme pokračovať a inicializácii všetkých ukazovateľov, všetky char * s,
sa, že niektoré pochopiteľné hodnota, pravdepodobne null.
Ale nie je to úplne nevyhnutné, urobíme to.
>> Teraz, dva hlavné operácie komíny sú?
Ktokoľvek pamätám z prednášky, čo robiť s komíny? Áno?
[Stella] Stlačením a praskanie? Presne >>.
Tlačenie a praskanie sú dve hlavné operácie na komíny.
A čo tlačiť robiť? >> Kladie niečo na vrchole
zo zásobníka, a potom praskla vezme ho.
[Hardison] Presne tak. Takže tlačí tlačí niečo na vrchole zásobníka.
Je to ako v jedálni zamestnancov uvedenie jedálenský podnos na pult.
A objavovať berie jedálenský podnos preč zásobníka.
Poďme prejsť pár príkladov toho, čo sa stane
keď sme sa tlačiť veci do zásobníka.
Ak by sme mali tlačiť na reťazec "ahoj" na naše zásobníka,
To je to, čo naša schéma by vyzerať ako teraz.
Pozrite sa, čo sa stane?
Usilovali sme do prvého prvku našej reťazca pole
a my zvýšil naše veľkosť počet na 1.
Takže ak sa pozrieme na rozdiel medzi dvoma šmykľavkami, tu bola 0, tu je pred stlačením.
Tu je po stlačení.
Pred push, po stlačení.
A teraz máme jeden prvok v našom zásobníku.
Je to reťazec "ahoj", a to je všetko.
Všetko ostatné v poli, v našom reťazcoch poli, je stále odpadky.
Sme nie je inicializovaná to.
Povedzme, že sme sa tlačiť ďalšie reťazec do nášho zásobníka.
Budeme tlačiť "svet" v tejto dobe.
Takže vidíte, "world" tu je na vrchole "hello",
a veľkosti znakov siaha až do 2.
Teraz môžeme tlačiť "CS50", a že to ísť na vrchole znova.
Keď sa vrátime, môžete vidieť, ako sa tlačí veci na vrchole zásobníka.
A teraz sa dostávame k popu.
Keď sme vyskočila niečo z frontu, čo sa stalo?
Každý Vidíte ten rozdiel? Je to celkom jemné.
[Študent] veľkosť. >> Jo, jej veľkosť.
>> Čo iné by ste očakávali zmeniť?
[Študent] Reťazce, taky. Právo >>. Reťazce taky.
Ukazuje sa, že keď robíte to takto,
pretože nie sme kopírovanie prvkov do nášho zásobníka,
sme vlastne nemusíme robiť nič, my môžeme len použiť veľkosť
sledovať počtu vecí v našom poli
takže keď sme pop, znovu sme práve decrement svoju veľkosť až 1.
Nie je potrebné, aby skutočne ísť a prepísať čokoľvek.
Druh funky.
Ukazuje sa, že sme zvyčajne len nechať veci sám, pretože je to menej práce pre nás urobiť.
Ak nemáme ísť späť a prepísať niečo, tak prečo to?
Takže keď sme sa pop dvakrát preč zásobníka, všetko, čo robí, je decrement do veľkosti niekoľkokrát.
A opäť, je to len preto, že nie sme kopírovanie veci do nášho stacku.
Áno? Hovorte.
[Študent, nezrozumiteľné] >> A čo sa stane potom, keď budete tlačiť zase niečo?
Keď stlačíte zase niečo, kde to ide?
Ak to pôjde, Basile? Do >> reťazcov [1]? Právo >>.
Prečo to ísť do reťazca [3]?
[Basil] Vzhľadom k tomu, že zabudol, že tam bolo niečo v reťazci [1] a [2]?
[Hardison] Presne tak. Naše zásobník, v podstate, "zabudol", že to držal na čokoľvek
v reťazci [1] alebo reťazca [2], takže keď sme sa tlačiť "Woot",
to len vezme, že do elementu v reťazci [1].
Sú nejaké otázky, na tom, ako to funguje, na základnej úrovni?
[Sam] Tak to nie je dynamický žiadnym spôsobom, pokiaľ ide o výšku
alebo z hľadiska veľkosti zásobníka?
[Hardison] Presne tak. To je - išlo o to, že to nie je dynamicky growning stack.
To je zásobník, ktorý môže obsahovať, nanajvýš štyri * char s, najviac štyri veci.
Ak by sme mali skúsiť a tlačiť pätiny vec, čo si myslíte, že by sa malo stať?
[Študenti, nezrozumiteľné]
[Hardison] Presne tak. Existuje celá rada vecí, ktoré by sa mohlo stať.
To by mohlo seg poruchy, závislosti na tom, čo sme boli -
ako presne sme realizáciu back-end.
Mohlo by to prepísať. To by mohlo mať, že buffer overflow, že sme hovorili o v triede.
Aký by mal byť najzrejmejšie vec, ktorá by mohla byť prepísané
ak sme sa snažili tlačiť ďalšia vec na našom zásobníku?
Takže vy ste spomenul pretečeniu vyrovnávacej pamäte.
Čo by mohlo byť to, čo by si písal cez alebo dupol na
ak by sme pretiekol náhodou, že sa snaží tlačiť ďalšia vec?
[Daniel, nezrozumiteľné] >> Možno.
Ale spočiatku, môže, čo sa stalo? Čo keď sme sa snažili tlačiť štvrtiny vec?
To by mohlo prepísať veľkosť, aspoň s týmto pamäťovým schémy, ktoré sme dostali.
>> V špecifikácii problému set, čo je to, čo budeme sa vykonáva dnes,
čo chceš urobiť, je len vráti false.
Naša Push metóda bude vracať boolovská,
a že boolean hodnota bude true, ak tlak uspeje
false, ak nemôžeme presadzovať nič viac, pretože zásobník je plný.
Prejdime trochou uvedeného kódexu teraz.
Tu je náš stlačenie funkcie.
Naša tlak funkcia pre sústavu bude trvať v reťazci, aby na zásobníku.
Bude to vráti hodnotu true, ak reťazec bol úspešne tlačil
na stack a false inak.
Nejaké návrhy na to, čo by mohlo byť dobrý prvá vec tu?
[Sam] Ak veľkosť zodpovedá kapacitu potom vráti false?
[Hardison] Bingo. Dobrá práce.
Ak je veľkosť kapacity, budeme sa vrátiť false.
Nemôžeme dať niečo viac v našom zásobníku.
V opačnom prípade budeme chcieť dať niečo na vrchole zásobníka.
Čo je to "vrchol zásobníka," pôvodne?
[Daniel] Veľkosť 0? Veľkosť >> 0.
Čo je vrchol zásobníka po tu jedna vec, ktorú v zásobníku? Missy, vieš?
[Missy] One. Veľkosť >> je, presne tak. Tie držať pridanie do veľkosti,
a zakaždým, keď ste uvedení v novom prvku v indexe veľkosť v poli.
Môžeme to urobiť s týmto druhom jednej vložky, pokiaľ to dáva zmysel.
Takže máme naše struny ponuku, budeme pristupovať na veľkosti indexu,
a my sme len tak uložiť naše char * tam.
Všimnite si, ako tam je žiadny reťazec kopírovanie tu deje,
no dynamické prideľovanie pamäti?
A potom Missy priniesol to, čo teraz musíme urobiť,
pretože sme uložili reťazec na príslušnom mieste v poli,
a ona povedala, že sme museli zvýšiť veľkosť jedného tak, že sme pripravení na ďalšie Push.
Takže, čo môžeme urobiť, aby sa s.size + +.
V tomto bode, sme tlačení do nášho poľa. Čo je posledná vec, ktorú musíme urobiť?
[Študent] Vracia true. >> Vracia true.
Takže je to celkom jednoduché, celkom jednoduchý kód. Nie moc.
Akonáhle omotal hlavu okolo, ako stack funguje,
to je docela ľahko implementovať.
>> Teraz, ďalšia časť z toho sa objavovať reťazec preč zásobníka.
Ja ti dám si chalani nejaký čas pracovať na tomto trochu.
Je to skoro podstate opak toho, čo sme urobili tu v Push.
To, čo som urobil, je vlastne - oops.
Som naštartoval až spotrebiče tu, a v spotrebiči,
Ja som vytiahol problém nastaviť 5 špecifikáciu.
Ak by sme priblížite tu, môžeme vidieť som na cdn.cs50.net/2012/fall/psets/pset5.pdf.
Už ste stiahli tento kód, ktorý je tu umiestnený, section6.zip?
Dobrá. Ak ste tak ešte neurobili, aby to, že práve teraz, naozaj rýchlo.
Urobím to v mojom terminálovom okne.
Vlastne som to urobil tu. Jo.
Áno, Sam? >> Mám otázku o tom, prečo ste hovoril, že s.string 's držiakmi na veľkosti = str?
Čo je to str? Je vymedzený niekde pred, alebo - oh, v char * str?
[Hardison] Áno, presne tak. To bol argument. >> Oh, dobre. Prepáčte.
[Hardison] Sme určujúce reťazec, aby sa zasadila palcov
Ďalšia otázka, ktorá by mohla prísť, že sme sa naozaj hovoriť o tu bola
sme sa za samozrejmé, že sme mali túto premennú s názvom s
, Ktorý bol v rozsahu a prístupné pre nás.
Vzali sme za samozrejmé, že s je tento stack struct.
Takže ohliadnutie za touto Push kód,
môžete vidieť, že robíme veci s týmto reťazcom, ktorý dostal prešiel v
ale potom zrazu, že sme prístup k s.size, rovnako ako tam, kde sa s pochádzajú?
V kóde, ktorý sa budeme pozerať na v sekcii archíve
a potom veci, ktoré budete robiť vo svojom probléme zapadne,
sme urobili náš stack struct globálne premenné
takže môžeme mať k nemu prístup na všetkých našich rôznych funkciách
bez toho aby ste museli ručne prejsť okolo a odovzdať ho odkazom,
robiť všetky tieto veci k nej.
Sme jednoducho podvádza trochu, ak chcete, aby sa veci krajšie.
A to je niečo, čo tu robíme, pretože je to pre zábavu, je to jednoduchšie.
Často, uvidíte ľudia to v prípade, že má jednu veľkú dátovú štruktúru
, Ktorý je prevádzkovaný na v rámci ich programu.
>> Vráťme sa k zariadeniu.
Bolo všetci úspešne získať section6.zip?
Všetci rozbaľte ho pomocou Rozbaľte section6.zip?
Ak pôjdete do sekcie 6 adresára -
Aah, všade možne -
a zoznam toho, čo je tu, vidíte, že máte tri rôzne. C súbory.
Máte front, SLL, čo je single-linked list, a zásobník.
Ak otvoríte stack.c,
môžete vidieť, že máme túto struct definované pre nás,
Presný struct, že sme práve hovorili zo sklíčka.
Máme naše globálne premenné pre zásobník,
sme dostali náš Push funkciu,
a potom sme dostali náš pop funkciu.
Dám kód pre zatlačte späť na snímke tu,
ale to, čo by som chcel vy urobiť, je, ako najlepšie svoje schopnosti,
ísť a robiť pop funkciu.
Akonáhle ste implementovali, môžete kompilovať to s make stoh,
a spustite výsledné zásobníka spustiteľný,
a že pobeží celý tohto skúšobného predpisu tu to je v main.
A hlavné stará skutočne robiť push a pop hovory
a uistite sa, že všetko ide cez všetky práva.
To tiež inicializuje veľkosť zásobníku tu
takže nemusíte mať strach o inicializácii, že.
Môžete predpokladať, že to bolo správne inicializovaný
v okamihu, keď ste k nemu mali prístup do pop funkciu.
Dáva to zmysel?
Tak ideme na to. Tam je tlak kód.
Dám ti chlapci 5 alebo 10 minút.
A ak máte nejaké otázky v medziobdobí, keď ste kódovanie,
Spýtajte sa nahlas.
Takže ak sa dostanete do problematickým bodom, opýtajte sa.
Dajte mi vedieť, nech všetci ostatní vedieť.
Práca so svojím susedom taky.
[Daniel] Zrovna vykonávanie pop teraz? Len >> pop.
Aj keď môžete skopírovať vykonávanie Push, ak chcete
tak, že testovanie bude fungovať.
Vzhľadom k tomu, že je ťažké testovať veci dostať do -
alebo, je ťažké testovať objavovať veci z hromady, ak tam nie je niečo v zásobníku začať.
>> Čo je pop mal byť vracajúci? Prvok z hornej časti zásobníka.
Má to dostať prvok preč hornej časti zásobníka
a potom dekrementace veľkosť zásobníku,
a teraz ste stratili prvok na vrchole.
A potom sa vrátite prvok na vrchole.
[Študent, nezrozumiteľným]
[Hardison] Takže čo sa stane, ak to urobíte? [Študent, nezrozumiteľným]
Čo sa skončí udalosť je budete pravdepodobne prístup buď
prvok, ktorý nebol inicializovaný ešte, takže výpočet
, Kde sa posledný prvok je vypnutý.
Takže tu, ak si všimnete, v Push, sme prístup reťazca na s.size prvku
pretože je to nový index.
Je to nový vrchol zásobníka.
Vzhľadom k tomu, pop, s.size bude budúci priestor,
priestor, ktorý je v hornej časti všetkých prvkov v stohu.
Takže na najvyššej element nie je v s.size,
ale, že je to pod ňou.
>> Ďalšia vec, ktorú urobiť, keď sa - v popu,
je si treba decrement veľkosti.
Ak si pamätáte späť do našej malej diagramu tu,
Naozaj, jediná vec, ktorá sme videli deje, keď my sme volali pop
bolo, že táto veľkosť klesla, prvé 2, potom 1.
Potom, keď sme sa tlačil nový prvok na, by to ísť na na správnom mieste.
[Basil] Ak s.size je 2, potom nie je to ísť na prvku 2,
a potom budeš chcieť pop ten element off?
Takže ak by sme išli do - >> Tak sa poďme pozrieť na to znova.
Pokiaľ je to náš zásobník na tomto mieste
a nazývame pop,
na ktoré index je na najvyššej element?
[Basil] Na 2, ale bude to pop 3. Právo >>.
Tak to je, kde je naša veľkosť 3, ale chceme, aby pop prvok na indexe 2.
Je to tak typické druh off by ten, ktorý máte s nulovou indexovanie polí.
Takže vy chcete pop tretí prvok, ale tretí prvok nie je na indexe 3.
A dôvod, prečo nemáme robiť, že mínus 1, keď sme tlačenie
je, pretože práve teraz, zistíte, že na najvyššej prvok,
ak by sme mali tlačiť niečo iné na stacku v tomto bode,
budeme chcieť tlačiť na indexe 3.
A to len tak sa stane, že veľkosť a indexy zarovnané, keď tlačí.
>> Kto má pracovný zásobníka implementácie?
Máte pracovné stack jeden. Máte pop pracovať ešte?
[Daniel] Áno. Myslím, že áno.
Program >> funguje a nie je seg chyba, je to vytlačiť?
Má to vytlačiť "úspech" pri spustení?
Jo. Urobte zásobník, spustite ho, ak sa vytlačí "úspech" a nejde boom,
potom všetko je dobré.
Dobrá. Poďme k prístroju naozaj rýchlo,
a prejdeme to.
Ak sa pozrieme na to, čo sa tu deje s pop,
Daniel, čo bolo prvá vec, ktorú urobil?
[Daniel] Ak s.size je väčšia ako 0.
[Hardison] Dobre. A prečo si to urobil, že?
[Daniel] Uistite sa, že tam bolo niečo vo vnútri zásobníka.
[Hardison] Právo. Ak chcete otestovať, aby sa ubezpečil, že s.size je väčšia ako 0;
inak, čo chceš, aby sa stalo?
[Daniel] Return null? Návrat >> null, presne.
Takže ak s.size je väčšia ako 0. Tak čo budeme robiť?
Čo budeme robiť, keď zásobník nie je prázdny?
[Stella] Tu decrement veľkosť? Tie >> decrement veľkosti, v poriadku.
Tak ako si to urobil, že? >> S.size--.
[Hardison] Great. A potom to, čo si urobil?
[Stella] A potom som povedal: return s.string [s.size].
[Hardison] Great.
V opačnom prípade sa vrátite null. Áno, Sam?
[Sam] Prečo to nemusí byť s.size + 1?
[Hardison] Plus 1? Jo >>. >> Mám to.
[Sam] Myslel som, že preto, že ste s 1 von,
potom budete vracať nie je ten, že požiadal.
[Hardison] A to bolo presne to, čo sme hovorili o tejto celej problematike 0 indexov.
Takže keď sme približovania tu.
Ak sa pozrieme na toho chlapa tu, môžete vidieť, že keď sme pop,
sme objavovať prvok na indexe 2.
>> Tak sme znížiť svoju veľkosť ako prvý, potom je naša veľkosť zodpovedá náš index.
Ak nemáme decrement veľkosti, potom musíme urobiť veľkosti -1 a potom útlm.
Great. Všetky dobré?
Akékoľvek otázky na to?
Existuje celý rad rôznych spôsobov, ako napísať to rovnako.
V skutočnosti, môžeme urobiť ešte niečo - čo môžeme urobiť, je jednoriadkový.
Môžeme urobiť jeden riadok návrat.
Takže môžeme skutočne decrement predtým, než sme sa vrátiť tým, že.
Takže uvedenie - pred s.size.
To robí linka naozaj hustá.
V prípade, že rozdiel medzi -. S veľkosťou a s.size--
je, že tento postfix - hovoria, že postfix, pretože - prichádza po s.size--
Znamená to, že s.size je vyhodnotená na účely zistenia indexu
ako je to v súčasnej dobe, kedy sa vykonáva tento riadok,
a potom - sa stane po riadku sa vykoná.
Po prvok na s.size indexu je prístupná.
A to nie je to, čo chceme, pretože chceme, aby úbytok sa stane prvý.
Othewise, budeme pristupovať k polia, efektívne, mimo medze.
Budeme pristupovať k prvku nad ten, ktorý sme vlastne chcete otvoriť.
Jo, Sam? >> Je to rýchlejšie, alebo použiť menej RAM, aby sa v jednej rade, alebo nie?
[Hardison] Úprimne povedané, to naozaj záleží.
[Sam, nezrozumiteľné] >> Jo, to záleží na okolnostiach. Môžete to urobiť kompilátora triky
získať kompilátor uznať, že väčšinou, som si predstaviť.
>> Tak sme sa už zmienil niečo málo o tejto veci optimalizácie kompilátora
že si môžete robiť pri zostavovaní,
a to je to vec, ktorá kompilátor mohol zistiť,
ako oh, hey, možno by som mohol urobiť to všetko v jednej operácii,
ako protichodný k načítanie veľkosť premennej od RAM,
dekrementování to, ukladanie späť, a potom sa načítanie je späť
spracovať zvyšok tejto operácie.
Ale zvyčajne, nie, to nie je ten druh veci
, Čo sa deje, aby sa váš program výrazne rýchlejší.
Nejaké ďalšie otázky týkajúce sa sad?
>> Takže tlačenie a praskanie. Ak ste chalani chcú vyskúšať hackerské vydania,
čo sme urobili v hackerské vydanie je skutočne preč
a robil to stack rastie dynamicky.
Úlohou je predovšetkým tu v tlačnej funkciu,
prísť na to, ako urobiť, aby pole rastú
ako si udržať tlačiť viac a viac prvkov na do zásobníka.
Je to vlastne nie je moc doplnkový kód.
Len volanie - musíte mať na pamäti dostať volania malloc tam správne,
a potom zistiť, kedy budete volať realloc.
To je zábavné problém, ak máte záujem.
>> Ale v súčasnej dobe, poďme ďalej, a poďme hovoriť o frontoch.
Prechádzajte tu.
Fronta je blízko súrodenec zásobníka.
Takže v zásobníku, boli veci, ktoré dal v poslednej
boli prvé veci, a potom byť načítaná.
Máme to posledné dovnútra, prvý von, alebo LIFO, objednávanie.
Vzhľadom k tomu, vo fronte, ako by ste očakávali od okamihu, kedy ste stál vo fronte,
prvá osoba, ktorá sa v súlade, prvá vec, dostať sa do fronty,
je prvá vec, ktorá sa dostane načítať z frontu.
Fronty sú tiež často používa, keď máme čo do činenia s grafmi,
ako by sme hovorili o stručne s komíny,
a fronty sú tiež užitočné pre veľa ďalších vecí.
Jedna vec, ktorá príde často sa snaží udržiavať, napríklad,
zoradený zoznam prvkov.
A môžete to urobiť pomocou poľa. Môžete udržiavať zoradený zoznam vecí v matici,
ale tam, kde to dostane zložité je potom budete mať vždy nájsť
vhodné miesto pre vloženie ďalšia vec.
Takže ak máte rad čísel, 1 až 10,
a potom chcete rozšíriť, že na všetky čísla 1 až 100,
a vy ste stále tieto čísla v náhodnom poradí a snaží sa udržať všetko
zoradené, ako si prejsť, môžete skončiť museli urobiť veľa radenie.
U niektorých typov front a niektorých typov podkladových dátových štruktúr,
môžete skutočne udržať pomerne jednoduchý.
Nemáte niečo pridať a potom preorganizovať celá vec zakaždým.
Ani budete musieť urobiť veľa posunutie vnútorných prvkov okolo.
Keď sa pozrieme na fronte, uvidíte, že - aj v queue.c v úseku -
struct, že sme rovnako vám je naozaj podobný struct, že sme vám dal na stack.
>> Je tu ešte jedna výnimka z tohto, a že jedna výnimka
je to, že máme túto dodatočnú integer s názvom hlava,
a hlava je tu pre sledovanie hlavy frontu,
alebo prvý prvok v rade.
S hromadou, sme boli schopní sledovať prvku, ktorý sme mali k načítaniu,
alebo hornej časti zásobníka, používať len veľkosť,
vzhľadom k tomu, s frontu, sme sa museli vysporiadať s opačných koncoch.
Snažíme križovať veci na konci, ale potom sa vrátia veci z prednej strany.
Takže účinne, s hlavou, máme index na začiatku fronty,
a veľkosť nám index na konci fronty
takže môžeme získať veci z hlavy a pridať veci k chvostu.
Vzhľadom k tomu, s komínom, sme boli vždy len zaoberajúca sa v hornej časti zásobníka.
Nikdy sme nemali prístup na dno zásobníka.
My len pridané veci na vrchole a sa veci preč z hornej
takže sme nepotrebovali, že ďalšie pole vnútri našej struct.
Znamená to, že všeobecne zmysel?
Dobrá. Áno, Charlotte? [Charlotte, nezrozumiteľným]
[Hardison] To je veľká otázka, a to ten, ktorý prišiel v prednáške.
Možno prechádzal niekoľkých príkladoch ukážeme, prečo
nechceme používať struny [0] ako hlavu frontu.
>> Tak si predstavte, že máme front, budeme hovoriť, že fronty.
Na začiatku, keď sme práve inštanciu to,
keď sme práve oznamoval, sme nie je inicializovaná nič.
Je to všetko smeti. Takže samozrejme chceme, aby sa ubezpečil, že inicializuje
ako veľkosť a hlavy poľa na 0, niečo rozumné.
Mohli by sme tiež pokračovať a hodnotu null z prvkov v našom fronte.
A aby sa tento diagram fit, zistíte, že sa naše fronty môže mať iba tri prvky;
vzhľadom k tomu, naše stack mohol držať štyri, môže naša frontu len držať tri.
A to len preto, aby sa diagram fit.
Prvá vec, ktorá sa tu deje je, že sme Zaradí reťazec "ahoj".
A rovnako ako sme to urobili s zásobníka, nič hrozne tu iný,
hodíme reťazca na na struny [0] a vložili naše veľkosť o 1.
My Zaradí "bye", dostane sa na seba.
Takže to vyzerá ako hromada z podstatnej časti.
Začali sme tu, nový prvok, nový prvok, veľkosť udržuje ísť hore.
Čo sa stane v tomto okamihu, kedy chceme, aby dequeue niečo?
Ak chceme dequeue, ktorá je prvok, ktorý chceme dequeue?
[Basil] Strings [0]. >> Zero. Presne tak, Basil.
Chceme sa zbaviť prvého reťazca, toto jeden, "hi".
Takže to, čo je ďalšia vec, ktorá sa zmenilo?
Všimnite si, keď sme vyskočila niečo z frontu, len sme zmenili veľkosť,
ale tu, máme pár vecí, ktoré sa menia.
Nielen, že sa veľkosť zmeny, ale hlava zmeny.
Toto sa vracia do bodu Charlotte staršie:
prečo máme tento hlavu rovnako?
Má to zmysel teraz, Charlotte? >> Druh.
[Hardison] Druh? Takže to, čo sa stalo, keď sme dequeued?
Čo hlava to, že teraz je zaujímavé?
[Charlotte] No, pretože sa to zmenilo - v poriadku. Aha.
Vzhľadom k tomu, hlava - kde hlava smeruje k zmenám, pokiaľ ide o umiestnenie.
Je to už nie je vždy nula index jeden. >> Jo, presne tak.
Čo sa stalo, ak bolo dequeueing vysokú prvok
bola dokončená a my sme nemali túto hlavu poľa
pretože sme boli vždy volať tento reťazec na 0 indexu hlava našej frontu,
potom by sme museli posunúť zvyšok frontu dole.
Museli by sme sa posunúť "bye" od z reťazca [1] na reťazce [0].
A reťazca [2] sa stanovuje na reťazce [1].
A budeme musieť urobiť pre celý zoznam prvkov,
celý rad prvkov.
A keď to robíme s radom, ktorá sa naozaj nákladné.
Tak tu, to nie je veľký problém. Musíme len tri prvky v našom poli.
Ale keby sme mali front tisíc prvkov alebo milión prvky,
a potom všetci naraz, začneme robiť veľa Dequeue volá všetky v slučke,
veci naozaj spomaliť, pretože presúva všetko dolu neustále.
Viete, posunúť o 1, posun o 1, posun o 1, posun o 1.
Miesto toho, my používame túto hlavu, hovoríme, že "ukazovateľ", aj keď to nie je naozaj ukazovateľ
v pravom slova zmysle, nie je to ukazovateľ typu.
Nie je to int * alebo char * alebo niečo podobné.
Ale je to ukazovať alebo označujúci hlavu našej frontu. Jo?
>> [Študent] Ako Dequeue vedieť len pop off, čo je v čele?
[Hardison] Ako Dequeue vedieť, ako sa pop off, čo je v čele? Právo >> jo.
>> Čo je to pri pohľade na to len, čo hlava pole je nastavený na.
Takže v tomto prvom prípade, keď sa pozrieme tu,
Naša hlava je 0, index 0. Právo >>.
[Hardison] Tak to len hovorí, že v poriadku, dobre, prvok na indexe 0, reťazec "ahoj",
je prvok v čele našej frontu.
Takže budeme dequeue toho chlapa.
A to bude prvok, ktorý sa vrátil do volajúcemu.
Áno, Saad? Takže >> hlava v podstate nastaví - kde budete indexovať?
To je začiatok toho? Jo >>. Dobre >>.
[Hardison] To stáť nový začiatok pre naše pole.
Takže keď dequeue niečo, všetko, čo musíte urobiť, je prístup k prvku na indexe q.head,
a že bude prvok, ktorý chcete dequeue.
Máte tiež decrement veľkosti.
Uvidíme sa za chvíľku, kedy sa veci trochu zložitejšie s tým.
My dequeue, a teraz, keď sa Zaradí znova,
kde máme Zaradí?
Ak sa ďalší prvok ísť v našej fronte?
Povedzme, že chceme, aby Zaradí reťazec "SK".
Do ktorého index to pôjde? [Študenti] Reťazce [2]. Dva >>.
Prečo 2 a nie 0?
[Basil] Vzhľadom k tomu, teraz hlava je 1, tak, že je ako na začiatku zoznamu?
[Hardison] Právo. A čo označuje koniec zoznamu?
Čo sme pomocou naznačovať koniec našej fronty?
Hlava je hlava našej fronty, začiatok nášho fronty.
Aký je koniec nášho fronty? [Študenti] Veľkosť. Veľkosť >> presne.
Takže naše nové prvky ísť na veľkosti, a prvky, ktoré sa vzlietnuť zložiť na hlavu.
Keď sme Zaradí ďalší prvok, sme dávať ho do veľkosti.
[Študent] Než dáte, že v keď, veľkosť bola 1, nie?
[Hardison] Právo. Tak nie je úplne na veľkosti. Veľkosť +, nie 1, ale + hlava.
Pretože sme posunul všetko za hlavu čiastky.
Tak tu, teraz máme fronty veľkosti 1, ktorá začína na indexe 1.
Chvost je index 2. Áno?
>> [Študent] Čo sa stane, keď sa Dequeue reťazca [0], a sloty Reťazce "v pamäti
Len si vyprázdnila, v podstate, alebo len zabudli?
[Hardison] Jo. V tomto zmysle, my sme len zabudnúť je.
Ak by sme boli ukladanie kópií nich -
veľa dátových štruktúr sa často ukladať svoje vlastné kópie prvkov
tak, že osoba riadiaca dátové štruktúry nemá na starosti
o tom, kde všetky tie ukazovatele budú.
Dátová štruktúra má na všetko, má na všetkých kópií,
aby sa ubezpečil, že všetko trvá primerane.
Avšak v tomto prípade, tieto dátové štruktúry len pre jednoduchosť
nie sú zhotovovanie kópií niečo, čo sme ukladaním v nich.
[Študent] Tak je to kontinuálna pole -? Áno >>.
Ak sa pozrieme späť na to, čo definícia bola tejto štruktúry, je.
Je to len štandardné pole, ako keď ste videli,
poľa * char s
Znamená to, že -? >> Jo, len som premýšľal,
ak budete nakoniec dôjdu pamäte, do určitej miery,
Ak máte všetky tieto prázdne miesta vo vašom poli?
[Hardison] Jo, to je dobrá pripomienka.
>> Ak sa pozrieme na to, čo sa stalo dnes v tomto bode,
sme zaplnila naše frontu, ako to vyzerá.
Ale my sme naozaj naplnená naša fronty
pretože máme front, ktorá má veľkosť 2, ale začína na indexe 1,
pretože to je miesto, kde naša hlava je ukazovateľ.
Rovnako ako si hovoril, že prvok v reťazci [0], na indexe 0, je v skutočnosti neexistuje.
Nie je to v našej fronte už.
Len sme sa neobťažoval ísť a prepísať ho, keď sme dequeued to.
Takže aj keď to vyzerá, že sme k vyčerpaniu pamäte, naozaj nie.
To miesto je k dispozícii pre nás používať.
Vhodné správanie, ak by sme mali vyskúšať a prvý Dequeue niečo
ako "bye", že by sa pop bye off.
Teraz naša fronta začína na indexe 2 a je o veľkosti 1.
A teraz, keď sa snažíme a Zaradí zase niečo, povedzme 50,
50 by mala ísť v tomto mieste v indexe 0
pretože je to stále k dispozícii pre nás. Áno, Saad?
[Saad] Stáva sa to automaticky?
[Hardison] Nestáva sa úplne automaticky. Musíte si to spočítajte
aby to fungovalo, ale v podstate to, čo sme urobili je, že sme práve omotal okolo.
[Saad] A je to v poriadku, ak to má dieru uprostred toho?
[Hardison] Ak môžeme matematický fungovať správne.
>> A ukázalo sa, že to vlastne nie je tak ťažké urobiť s mod operátora.
Tak ako sme to urobili s Caesarom a ďalšie veci crypto,
pomocou mod, môžeme robiť veci zabaliť okolo a ísť ďalej
okolo a dokola a dokola s našou fronte,
vedenie, ktoré hlava ukazovateľ pohybuje.
Si všimnúť, že veľkosť je vždy v počte prvkov v skutočnosti v fronty.
A je to len hlava ukazovateľ, ktorý udržuje vystriedať.
Ak sa pozrieme na to, čo sa tu stalo, ak by sme sa vrátiť na začiatok,
a vy sa len pozerať, čo sa deje na hlavu
keď sme Zaradí niečo, nič sa nestalo, aby na hlave.
Keď sme vo fronte niečo iné, nič sa nestalo, aby na hlave.
Hneď ako sme dequeued niečo, hlava sa zdvihne o jednu.
My vo fronte niečo, nič sa nestane do hlavy.
Keď sme dequeue niečo, hlava zrazu dostane zvýšený.
Keď sme Zaradí niečo, nič sa nestane do hlavy.
>> Čo by sa stalo v tomto bode, ak by sme mali dequeue zase niečo?
Akékoľvek myšlienky? Čo by sa stalo do hlavy?
Čo by sa malo stať na hlave
ak by sme mali dequeue niečo iné?
Hlava teraz je na indexe 2,
, Čo znamená, že hlava fronte reťazca [2].
[Študent] Ktorá vracia 0? Je >> by sa mala vrátiť do 0. To by zabaliť späť okolo, presne.
Zatiaľ zakaždým, keď sme hovorili Dequeue, sme boli pridanie jedného do hlavy,
pridať jeden do hlavy, pridať jeden do hlavy, pridať jeden do hlavy.
Akonáhle že hlava ukazovateľ dostane na posledný index v našom poli,
potom musíme zabaliť späť k začiatku, ísť späť do 0.
[Charlotte] Čo určuje kapacitu fronty v zásobníku?
[Hardison] V tomto prípade, práve sme používali # definovaný konštantný. Dobre >>.
[Hardison] V aktuálnej. Súboru c, môžete ísť a špina sa to trochu
a urobiť z neho taký veľký, alebo tak málo, ako chcete.
[Charlotte] Takže, keď robíte to frontu, ako si urobiť počítač vedieť
aký veľký chcete stack byť?
[Hardison] To je veľká otázka.
Existuje niekoľko spôsobov, ako. Jedným z nich je práve definovať dopredu
a hovoria, že toto bude fronta, ktorá má 4 prvky alebo 50 prvkov alebo 10000.
Druhým spôsobom je robiť to, čo ľudia hackerov vydanie robia
a vytvárať funkcie, aby sa vaše frontu dynamicky rastie, pretože stále viac sa veci znie a
>> [Charlotte] Tak, aby šiel s prvou možnosťou, čo syntax sa používa
povedať programu, čo je veľkosť fronty?
[Hardison] Ah. Takže poďme sa dostať z toho.
Som stále v stack.c tu, tak som len tak prechádzať až na vrchol tu.
Vidíte toto právo tu? To je # define kapacitu 10.
A to je takmer presne rovnaké syntaxe, ktoré máme k fronte.
Okrem vo fronte, máme extra struct poľa tu.
[Charlotte] Oh, myslel som, že kapacita znamená kapacitu pre reťazce.
[Hardison] Ah. >> To, že je to maximálna dĺžka slova. >> Mám to.
Jo. Kapacita tu - to je skvelý bod.
A to je niečo, čo je zložité
pretože to, čo sme vykazovať tu je rada * char s
Pole ukazovateľov.
To je pole znakov.
To je asi to, čo ste videli, keď ste vyhlásil svoje vyrovnávacej pamäte pre súbor I / O,
keď ste boli vytvorenie reťazca ručne na zásobníku.
Avšak to, čo tu máme, je rad char * s
Takže je to pole ukazovateľov.
Vlastne, keď sa priblížite von a pozrieme sa na to, čo sa tu deje
v prezentácii, môžete vidieť, že skutočné prvky, posunková dáta
nie je uložený v matici sám.
Čo je uložená v našom poli tu sú odkazy k charakteru dát.
Dobre. Takže sme videli, ako veľkosť frontu je rovnako ako u zásobníka,
veľkosť vždy dodrží počet prvkov v súčasnej dobe v rade.
Po vykonaní 2 enqueues, veľkosť je 2.
Po vykonaní Dequeue veľkosť je teraz 1.
Po vykonaní ďalšie Zaradí veľkosť späť na 2.
Takže veľkosť rozhodne dodrží počet prvkov vo fronte,
a potom sa hlava len udržuje na bicykli.
To ide od 0-1-2, 0-1-2, 0-1-2.
A zakaždým, keď hovoríme Dequeue, dostane hlava ukazovateľ zvýšil na ďalšie index.
A ak hlava je asi ísť cez, to tvorí späť okolo 0.
Takže s tým, my môžeme písať Dequeue funkciu.
A budeme opustiť Zaradí funkciu pre vy realizovať miesto.
>> Keď sme dequeue prvok z našej frontu,
Čo bola prvá vec, ktorá Daniel urobil, keď sme začali písať pop funkciu pre komíny?
Nechaj ma počuť od niekoho, kto sa nehovorí ešte.
Poďme sa pozrieť, Saad, pamätáš si, čo Daniel urobil ako prvú vec, keď on písal pop?
[Saad] Tam bol, bolo to - >> Skúsil niečo.
[Saad] Ak je veľkosť väčšia ako 0. Presne >>.
A čo to bolo testovanie?
[Saad] To bolo testovanie, či tam je niečo vnútri poľa.
[Hardison] Jo. Presne tak. Takže nemôžete pop nič z fronty, ak je prázdna.
Rovnako tak, nemôžete dequeue nič z fronty, ak je prázdna.
Čo je prvá vec, ktorú by sme mali urobiť v našej Dequeue funkciu tu, myslíš?
[Saad] Ak veľkosť je väčšia ako 0? Jo >>.
V tomto prípade, som vlastne len testované, či je 0.
Ak je 0, môžeme sa vrátiť null.
Ale presne rovnaká logika.
A budeme pokračovať s tým.
Ak je veľkosť nie je 0, kde je prvok, ktorý chceme dequeue?
[Saad] V čele? Presne >>.
Môžeme len vytiahnuť prvý prvok v našej fronte
prístupom prvok v čele.
Nič blázon.
Po tom, čo by sme mali urobiť? Čo sa musí stať?
Aká bola ďalšia vec, ktorá sme sa rozprávali o v Dequeue?
Dve veci sa stalo, pretože naše fronta zmenila.
[Daniel] Zmenšenie veľkosti. >> Máme pre zníženie veľkosti, a zvýšiť hlavu? Presne tak.
Pre zvýšenie hlavu, nemôžeme slepo zvýšiť hlavu, zapamätať.
Nemôžeme jednoducho queue.head + +.
Musíme tiež tento mod od kapacity.
A prečo mod o kapacitu, Stella?
[Stella] Vzhľadom k tomu, že má obtekať okolo. Presne >>.
My mod o kapacitu, pretože má zabaliť späť k 0.
Takže teraz, v tomto okamihu, môžeme urobiť to, čo povedal Daniel.
Môžeme decrement veľkosť.
A potom môžeme len vrátiť prvok, ktorý bol v hornej časti frontu.
Vyzerá to trochu drsný na prvom mieste. Môžete mať otázku. Je nám ľúto?
>> [Sam] Prečo to najprv na začiatok fronty? Pokiaľ to ide?
[Hardison] Pochádza zo štvrtej série na dne.
Potom, čo sme testovať, aby sa ubezpečil, že naša fronta nie je prázdna,
sme vytiahnuť char * Najskôr sme vytiahnite prvok, ktorý sedí v čele indexu
nášho poľa, z nášho reťazca poľa, >> a volať, že prvý?
[Hardison] A hovoríme, že ako prvý. Jo.
Stačí nadviazať na to, že dôvod, prečo si myslíte, že sme to museli urobiť, že?
[Sam] Každý prvý práve vracia q.strings [q.head]? Jo >>.
Vzhľadom k tomu, >> robíme táto výmena q.head s mod funkcií,
a neexistuje žiadny spôsob, ako to urobiť, aby v rámci spätného line tiež.
[Hardison] Presne tak. Ste na mieste. Sam úplne na mieste.
Dôvod, prečo sme museli vytiahnuť prvý prvok v našom fronte a uložiť ho do premennej
Je tomu tak preto tento riadok, kde sme práve q.head,
je tu mod prevádzkovateľ tam nie je niečo, čo môžeme urobiť,
a sú to prejaví na hlave bez - v jednej línii.
Takže sme vlastne musieť vytiahnuť prvý prvok, potom nastavte hlavu,
upraviť veľkosť, a potom sa vrátiť na prvok, ktorý sme vytiahnuté.
A to je niečo, čo uvidíme prísť neskôr
spojené zoznamy, ako hráme si s nimi.
Často, keď ste uvoľnenie alebo odstránenie prepojených zoznamov
musíte mať na pamäti ďalší prvok, ďalšie ukazovateľ prepojeného zoznamu
Pred likvidáciou tej súčasnej.
Pretože inak by ste zahodiť informácie o tom, čo zostalo v zozname.
Teraz, keď idete do svojho zariadenia, môžete otvoriť queue.c--x z toho.
Takže keď som otvoriť queue.c, dovoľte mi, aby som zoom sem,
uvidíte, že máte podobne vyzerajúci súbor.
Podobné vyzerajúci súbor na to, čo sme mali predtým s stack.c.
Máme naše struct pre front definovanú rovnako ako sme videli na snímkach.
>> Máme Zaradí funkciu, ktorá je pre vás urobiť.
A máme Dequeue funkciu tu.
Dequeue funkcie v súbore je implementované,
ale ja ju späť až na PowerPoint, takže môžete zadať do, ak budete chcieť.
Takže pre ďalších 5 minút alebo tak, vy pracovať na Zaradí
čo je takmer pravým opakom Dequeue.
Nemusíte upraviť hlavu, keď ste enqueueing, ale to, čo máte nastaviť?
Veľkosť. Takže keď enqueue, hlava zostáva nedotknutý, dostane zmení veľkosť.
Ale to sa trochu - budete musieť pohrať s tou mod
prísť na to, čo presne index nový prvok by mal byť vložený na.
Takže ti dám si chalani trochu, dal dequeue späť na snímke,
a ako vy máte otázky, kričať von tak, že môžeme
všetci hovoria o nich ako o skupine.
Tiež, s veľkosťou nie - keď upravíte veľkosť, môžete vždy len -
máte k mod veľkosť vôbec? [Daniel] No >> Nemusíte sa mod veľkosti, vpravo.
Vzhľadom k tomu, veľkosť bude vždy, ak Si - za predpokladu, že ste správu vecí správne,
veľkosť bude vždy medzi 0 a 3.
Kde máte na mod, keď robíte Zaradí?
[Študent] Iba pre hlavu. Iba >> pre hlavu, presne.
A prečo máte na mod vôbec Zaradí?
Ak je situácia, v ktorej budete musieť mod?
[Študent] Ak máte veci v medzerách, ako na priestor 1 a 2,
a potom treba pridať niečo na 0.
[Hardison] Jo, presne tak. Takže ak vaša hlava je ukazovateľ na samom konci,
alebo ak je vaša veľkosť a vaša hlava je väčšia, alebo skôr, bude obtekať okolo frontu.
>> Takže v tejto situácii, že sme dostali tu na snímke práve teraz,
keď chcem Zaradí niečo hneď teraz,
chceme Zaradí niečo na indexe 0.
Takže, keď sa pozriete na miesto, kde 50 ide, a ja hovorím Zaradí 50,
to ide tam na dne. Ide v indexe 0.
To nahradí 'ahoj', ktorá už bola dequeued.
[Daniel] Copak o to postará v Dequeue už?
Prečo to robiť niečo s hlavou v Zaradí?
[Hardison] Oh, takže nie ste modifikovať hlavu, ospravedlňujem sa.
Ale musíte použiť operátor modulo, keď ste prístupu
prvok, ktorý chcete Zaradí keď ste prístupu
ďalší prvok vo vašom fronte.
[Basil] Ja som to neurobil, a ja som dostal "úspech" na tam.
[Daniel] Oh, som pochopil, čo hovoríte.
[Hardison] Takže didn'ti - ste práve urobil na q.size?
[Basil] Jo. Práve som zmenil strany, neurobil som nič s hlavou.
[Hardison] Nemusíte vlastne musieť resetovať hlavu za niečo,
ale keď sa index do reťazca poľa,
máte skutočne ísť dopredu a vypočítať, kde ďalší prvok je,
pretože prútia zásobníka, ďalší prvok vo vašom zásobníka bol vždy
na indexe zodpovedajúcej veľkosti.
Ak sa pozrieme späť na našej funkciu zásobníka tlačidlom,
môžeme vždy plonk v našom novom prvku priamo na indexe veľkosti.
Vzhľadom k tomu, s fronty, to nemôžeme urobiť, že
pretože ak sme na túto situáciu,
ak budeme vo fronte 50 naša nová reťazec by ísť priamo na struny [1]
ktoré nechceme robiť.
Chceme mať nový reťazec ísť na indexe 0.
>> Má niekto - áno? [Študent] Mám otázku, ale to naozaj nie je príbuzný.
Čo to znamená, keď niekto jednoducho zavolá niečo ako Pred ukazovateľ?
Čo je to za meno skratka pre? Viem, že je to len meno.
[Hardison] Pred ukazovateľ? Poďme sa pozrieť,. V akej súvislosti?
[Študent] To bolo pre vložku. Môžem vás požiadať neskôr, ak budete chcieť
pretože to nie je naozaj súvisí, ale ja som jednoducho -
[Hardison] Od vložiť kód Davida z prednášky?
Môžeme vytiahnuť, že a hovoriť o tom.
Budeme o tom hovoriť ďalej, akonáhle sa dostaneme do prepojených zoznamov.
>> Takže to naozaj rýchlo pozrieť na to, čo enqueue funkcie vyzerá.
Aká bola prvá vec, že ​​ľudia sa snažil urobiť v Zaradí rade? Do tejto fronty?
Podobne ako to, čo ste urobil pre zásobníka tlačí.
Čo si urobil, Stella?
[Stella, nezrozumiteľným]
[Hardison] Presne tak. Ak (q.size == kapacita) -
Musím dať svoje zátvorky na správnom mieste - vráti false.
Zväčšiť trochu. Dobre.
Teraz, čo je ďalšia vec, ktorú by sme mali urobiť?
Rovnako ako u zásobníka, a vloží na správnom mieste.
A tak to, čo bolo tým pravým miestom pre vloženie že?
S zásobníka bolo index veľkosti, s tým, že to nie je tak.
[Daniel] Mám q.head--alebo - >> q.strings? >> Jo.
q.strings [q.head + q.size mod KAPACITA]?
[Hardison] sme pravdepodobne chcieť, aby zátvoriek tento
tak, že sme získali príslušnú prednosť, a tak to cleart všetkým.
A nastaviť, aby rovnaké? Ak chcete >> str? Ak chcete >> str Great.
A teraz, čo je to posledná vec, ktorú musíme urobiť?
Rovnako ako sme to robili v zásobníku. Prírastok >> veľkosť? Prírastok >> veľkosti.
Boom. A potom, pretože štartovací kódu sa práve vrátil false v predvolenom nastavení,
chceme zmeniť na hodnotu true, ak všetko pôjde až do konca a je všetko v poriadku.
Dobrá. To je veľa informácií o oddielu.
Nie sme úplne na konci. Chceme hovoriť naozaj rýchlo o single prepojených zoznamov.
Dám to tak môžeme vrátiť sa k nemu neskôr.
Ale poďme späť k našej prezentácii za pár viac snímok.
Takže enqueue je TODO, teraz sme to.
>> Teraz sa poďme pozrieť na singly prepojených zoznamov.
Hovorili sme o nich trochu viac v prednáške.
Koľko z vás videl demo, kde sme mali ľudí
neobratne ukázal na seba a držanie čísla? >> Bol som v tom.
>> Čo vy na to? Bolo to, dúfajme, že demystifikovať tieto trochu?
S zoznamu, sa ukazuje, že sa zaoberáme tohto typu, ktorý budeme nazývať uzol.
Vzhľadom k tomu, s fronty a zásobníka sme mali structs, že by sme hovorovú front v zásobníku,
sme mali tieto nové fronty v zásobníku typov,
Tu je zoznam naozaj len skladá banda uzlov.
Rovnakým spôsobom, že reťazce sú rovnako banda znakov všetkých zoradených vedľa seba.
Spájať zoznam je len uzol a ďalšie uzol a ďalšie uzol a iný uzol.
A skôr než rozbíjať všetky uzly dohromady a ich uloženie súvisle
všetky priamo vedľa seba v pamäti,
má túto ďalší ukazovateľ nám umožňuje ukladať uzly Kedykoľvek je to, v náhodnom poradí.
A potom druh drôtu je všetky dohromady bodu od jedného k druhému.
>> A čo bolo veľkou výhodou, že to malo cez pole?
Cez ukladanie všetkého súvisle len prilepené vedľa seba?
Pamätáš si? Jo? >> Dynamické prideľovanie pamäti?
>> Dynamické prideľovanie pamäte, v akom zmysle?
[Študent] V tomto môžete mať takže je väčšia a nemusíte sa pohybovať celý rad?
[Hardison] Presne tak. Takže s poľa, ak chcete, aby nový prvok do stredu,
budete musieť presunúť všetko preto, aby priestor.
A ako sme sa rozprávala s frontu,
to je dôvod, prečo sme udržať, že hlava ukazovateľ,
tak, že nie sme neustále mení veci.
Vzhľadom k tomu, že sa dostane drahé, ak máte veľkú poľa
a ste neustále robiť tieto náhodné vloženie.
Vzhľadom k tomu, s prehľadom, všetko, čo musíte urobiť, je hodiť to na nový uzol,
nastaviť ukazovatele, a máte hotovo.
Čo naštve o to?
Okrem skutočnosti, že je to nie je tak jednoduché pracovať ako s poľom? Jo?
[Daniel] No, myslím, že je to oveľa ťažšie prístup špecifický prvok v pripojenom zozname?
[Hardison] Nemôžeš len tak skočiť do ľubovoľného prvku v polovici svojho prepojeného zoznamu.
Ako sa vám to musieť urobiť miesto? >> Musíte krok celú vec.
[Hardison] Jo. Musíte prejsť jeden po druhom, jeden po druhom.
Je to obrovská - to je bolesť.
Čo je to druhé - je tu ďalší pád na to.
[Basil] Nemôžete ísť dopredu a dozadu? Musíte ísť jedným smerom?
[Hardison] Jo. Tak ako to budeme riešiť, že niekedy?
[Basil] Dvakrát-prepojených zoznamov? Presne >>. K dispozícii sú dvojnásobne prepojené zoznamy.
Tam sú tiež - sorry?
>> [Sam] Je to rovnaké ako s použitím PRED vec, že ​​-
Práve som si spomenula, nie je to, čo pred vec je?
Nie je to medzi dvojnásobne a single?
[Hardison] Poďme sa pozrieť na to, čo presne robí.
Tak ideme na to. Tu je zoznam kódu.
Tu máme predptr, tu. Je to to, čo si hovoril?
Takže to bol - on oslobodenie zoznam a snaží sa uložiť ukazovateľ na ňu.
To nie je o dvojnásobne, jednotlivo prepojené-listy.
Môžeme hovoriť viac o tom neskôr, pretože to sa hovorí o uvoľnení zoznam
a chcem ukázať niektoré ďalšie veci ako prvý.
ale je to len - je to pamätať hodnotu PTR
[Študent] Oh, to je predchádzajúcich ukazovateľ? Jo >>.
Takže potom môžeme zvýšiť PTR sám predtým, než sme potom zadarmo to, čo predptr je.
Pretože nemôžeme bez ptr a potom volať ptr = ptr ďalšie, nie?
To by bolo zlé.
Tak uvidíme, späť na toho chlapa.
>> Ďalšie zlá vec, o zoznamoch je, že vzhľadom na to, s radom
budeme musieť všetky prvky samy o sebe naskladané vedľa seba,
Tu sme tiež zaviedli tento ukazovateľ.
Takže je tu ďalší kus pamäti, že sme museli použiť
pre každý prvok, ktorý sme uskladnenie v našom zozname.
Dostaneme pružnosť, ale to príde v cene.
Dodáva sa s týmto časovým náklady,
a je dodávaný s týmto pamäťovým náklady príliš.
Čas v tom zmysle, že teraz musíme prejsť každý prvok v poli
nájsť ten u indexu 10, alebo že by boli index 10 v poli.
>> Len naozaj rýchlo, keď sme diagram z týchto zoznamov,
zvyčajne sa držať na hlave zoznamu alebo prvý ukazovateľ zoznamu
a vedomie, že to je pravda, ukazovateľ.
Je to len 4 bajty. Nie je to skutočný uzol sám.
Takže vidíte, že to nemá žiadnu hodnotu int v tom, žiadny ďalší ukazovateľ v ňom.
Je to doslova len ukazovateľ.
Bude to upozorniť na niečo, čo je skutočné uzol struct.
[Sam] Ukazovateľ nazýva uzol? >> To je - nie je. To je ukazovateľ na niečo typu uzla.
Je ukazovateľ na uzla struct. >> Oh, dobre.
Diagram vľavo, kódu napravo.
Môžeme nastaviť na null, čo je dobrý spôsob, ako začať.
Keď diagram, ty buď napísať, že za neplatné, alebo si dať čiaru cez to takto.
>> Jedným z najjednoduchších spôsobov, ako pracovať so zoznamami,
a žiadame vás, že aj predradiť a pripojiť vidieť rozdiely medzi týmito dvoma,
ale predradník je rozhodne jednoduchšie.
Keď začiatok riadku, to je miesto, kde si - keď prepend (7),
idete a vytvoriť uzla struct
a nastaviť prvý poukázať na to, pretože teraz, pretože sme prepended to,
to bude na začiatku zoznamu.
Ak sa predradeného (3), ktorá vytvára ďalší uzol, ale teraz 3 prichádza do 7..
Takže sme v podstate tlačí veci do nášho zoznamu.
Teraz môžete vidieť, že prepend, niekedy ľudia hovoria, že tlačiť,
preto, že ste tlačí nový prvok do zoznamu.
Je tiež ľahké odstrániť v čele zoznamu.
Takže ľudia budú často volajú, že pop.
A týmto spôsobom, je možné emulovať balík pomocou spojovaceho zoznamu.
Jejda. Je nám ľúto, teraz sa dostávame do append. Takže tu máme prepended (7), teraz sme prepend (3).
Ak by sme prepended niečo iné na tomto zozname, ak by sme prepended (4),
potom budeme mať 4 a potom 3 a potom 7.
Takže potom by sme mohli pop a odstrániť 4, odstrániť 3, odstráňte 7.
Často viac intuitívne spôsob, ako premýšľať o tom to je s append.
Takže som diagramu, čo by to vyzeralo s pripojiť tu.
Tu pripojený (7) nemá vyzerať inak
pretože tam je len jeden prvok v zozname.
A pripojením (3) vloží to na konci.
Možno si môžete prezrieť hneď teraz trik s append
je, že od tej doby sme len vedieť, kde na začiatku zoznamu je,
pripojiť do zoznamu musíte prejsť celú cestu v zozname
sa dostať do konca, zastavte, a potom budovať svoj uzol a plonk všetko dole.
Zapojte všetky veci hore.
Takže s Prepend, ako sme práve prešla to naozaj rýchlo,
keď predradiť do zoznamu, je to pomerne jednoduché.
>> Urobíte si nový uzol, zahŕňať niektoré dynamické prideľovanie pamäte.
Takže tu robíme uzla struct pomocou malloc.
Takže malloc sme použili preto, že to zrušil pamäť pre nás pre neskoršie
pretože nechceme, aby to - chceme, aby tento pamäti pretrvávať po dlhú dobu.
A my sme si ukazovateľ na miesto v pamäti, že sme práve pridelené.
Používame veľkosti uzla, nemáme sčítať poľa.
Nechceme ručne generovať počet bajtov,
namiesto toho sme použiť sizeof, takže vieme, že získanie zodpovedajúci počet bajtov.
Snažíme sa o to, aby testovanie, že naše malloc volanie bolo úspešné.
To je niečo, čo chcete robiť v všeobecne.
Na moderných strojoch, vyčerpania pamäte nie je niečo, čo je ľahké
ak ste pridelenie veľa vecí a robiť obrovský zoznam,
ale ak staviate veci pre, povedzme, ako iPhone alebo Android,
nemáte majú obmedzené prostriedky pamäti, najmä ak robíte niečo intenzívne.
Takže je to dobré sa dostať do praxe.
>> Všimnite si, že som použil niekoľko rôznych funkcií tu
, Keď ste videli, že sú trochu nové.
Takže fprintf je rovnako ako printf
okrem svojho prvého argumentu je potok, ktorý chcete vytlačiť.
V tomto prípade, že chceme vytlačiť na štandardný chybový reťazec
, Ktorý je odlišný od štandardného outstream.
Implicitne sa objaví na rovnakom mieste.
To tiež vytlačí na terminál, ale môžete -
použitie týchto príkazov ste sa dozvedeli o tom, o presmerovanie techniky
ste sa dozvedeli o vo videu Tommyho pre problémové sadu 4, môžete nasmerovať ju
do rôznych oblastí, potom ukončite, tu, ukončí svoj program.
Je to v podstate ako návrat z hlavnej,
okrem používame výjazd, pretože tu návrat nebude robiť nič.
Nie sme v hlavnej, tak vracia neukončí program, ako chceme.
Tak sme sa použiť funkciu ukončenia a dať mu chybový kód.
Potom tu máme nastavený nový uzol hodnotového poľa, jeho i pole sa rovná aj, a potom sme zapojte ho.
Vydali sme nový uzol je ďalší ukazovateľ aby ukazoval na prvý,
a potom prvý budú teraz na tento nový uzol.
Tieto prvé riadky kódu, sme vlastne stavať nový uzol.
Nie posledné dva riadky tejto funkcie, ale tie prvé.
Môžete si skutočne vytiahnuť do funkcie, do pomocnú funkciu.
To je často to, čo robím je, že som ju vytiahnuť do funkcie,
Hovorím to niečo ako uzol zostavenie,
a že udržiava prepend funkcie celkom malá, je to len 3 riadky potom.
Aj volať na mojej funkcie uzla zostavenie, a potom som drôt všetko hore.
>> Posledná vec, ja vám chcem ukázať,
a nechám ťa urobiť append a to všetko na vlastnú päsť,
je, ako určiť iteráciou cez zoznam.
Existuje veľa rôznych spôsobov, ako prechádzať cez zoznam.
V tomto prípade sa budeme nájsť dĺžku zoznamu.
Takže začneme s dĺžkou = 0.
To je veľmi podobné písanie strlen pre reťazec.
To je to, čo chcem ukázať, to pre slučku tu.
Vyzerá to trochu funky, to nie je obvyklé int i = 0, i <čokoľvek, i + +.
Namiesto toho je to inicializácia našu premennú n byť začiatok zoznamu.
A potom, keď naše Iterator premenná nie je null, budeme pokračovať.
To je preto, že podľa konvencie, bude koniec nášho zoznamu je null.
A potom prírastok, skôr než robiť + +,
spájať zoznam ekvivalent + + je n = n-> ďalšie.
>> Dám vám vyplniť medzery tu, pretože sme mimo čas.
Ale majte na pamäti, až budete pracovať na svojich spellr psets.
Prepojené zoznamy, ak ste vykonávanie hash tabuľky,
určite príde veľmi vhod.
A má tento idiom pre sláčiky nad vecou bude život oveľa jednoduchší, snáď.
Akékoľvek otázky, rýchlo?
[Sam] Budete posielať vyplnený SLL a sc?
[Hardison] Jo. Budem posielať vyplnené diapozitívov a vyplnený SLL stoh a queue.cs.
[CS50.TV]