>> DAVID Malan: Dobre.
Vitajte späť CS50.
To je začiatok 8 týždňov.
A pripomínajú, že problém sada 5 skončila s trochou výzvu.
Takže za predpokladu, že späť všetky svoje výučby Fellows a CA fotografie
v súbore card.raw, máte nárok sa teraz nájsť všetkých tých ľudí, a
jeden šťastný výherca bude chodiť domov s jedným z týchto vecí, skok pohyb
zariadenie, ktoré môžete použiť pre konečné projekty, napríklad.
>> To každý rok, vedie k trochu děsivost.
A tak to, čo som myslel, že to je podiel s vami o niektoré poznámky, ktoré majú
išiel tam a späť cez zamestnanci zoznam neskoro.
Napríklad práve včera večer, citácie koniec citátu, z jedného z pracovníkov
členovia, "musel som študentský klepanie na moje dvere vyfotiť so mnou.
Stalkeri, vravím. "Zacala dosť opisná a potom sme sa presťahovali
na, tak hodinu neskôr, "som mal Študent na mňa čaká po bode
a mal všetky naše mená a fotografie na niektorých listov papiera. "v poriadku.
Organizovaná tak, ale nie všetko strašidelné ešte.
>> Tak, "ja som bol mimo mesta tento víkend, a keď som sa vrátil, bol tam jeden v
môj
spálne. "[smiech]
DAVID Malan: Ďalšie citácie z pracovníkov člen "študent prišiel do môjho domu na
Somerville pri 4 hodín ráno. "Ďalšie personál, "Dostal som do hotela v San
Francisco a študent čakal na ma v hale s tromi DSLR. "
Typ fotoaparátu.
"Ja nie som ani na zamestnanca tomto semestri, ale študent sa vlámal do môjho domu tento
ráno a zaznamenal celú vec so sklom Google. "A potom konečne,
"Najmenej 12 ľudí bolo dychtivo čaká na mňa, keď som sa dostal z môjho
limo, a potom som
prebudil. "Dobre.
Takže medzi fotografiami, ako môžete spomínam, je tento chlapík tu, kto ste
Možno viete, ako Milo Banana, ktorý žije s Lauren Carvalho, naše hlavy
vyučovanie Fellow.
Milo Milo, poď sem chlapče.
Milo.
Nezabúdajme, že má na sebe Google Glass, takže my vám ukážeme všetko po ňom.
Tak to je Milo, ak chcete vyfotografovať sa s ním neskôr.
Ak by ste chceli dať pozor na divákov tam.
OK.
To je dobré zábery.
No, Milo Banana.
Oh, nerobte to.
>> [Smiech]
>> OK.
Takže jedným slovom, potom o tom, čo je pred nami, pretože ako začneme prechodu,
tento týždeň konkrétne z C na v prostredí príkazového riadku na PHP a
JavaScript a SQL a HTML a CSS v web-based prostredie, budeme
vybavenie vám všetky viac vedomostí pre
prípadné konečné projektov.
Za týmto účelom je ihrisko má Tradícia organizovania seminárov, ktoré
sú na tangenciálny témy k predmetu.
Veľmi o programovaní a vývoj aplikácií a tak ďalej, ale
nemusí byť nutne preskúmaná Kurz vlastné osnovy.
>> Takže ak by vás mohli zaujímať v jednom alebo viac z tohtoročných seminárov,
zaregistrujte sa na cs50.net/seminar.
Tam sú staršie semináre na cs50.net/seminars.
A na zozname zatiaľ pre tento rok Amazing Web Apps sú s Ruby on
Koľajnice, ktorá je alternatívou jazyk PHP.
Matematická lingvistika.
Úvod do IOS, ktorý je platformy, ktorá je použitá pre iPhone a
iPad rozvoja.
JavaScript pre Web Apps, budeme pokrývať , Ale v tomto seminári, pôjdete
do väčších detailov.
>> Leap Motion, takže budeme vlastne majú niektoré našich priateľov z Leap Motion,
spoločnosť sama, pridajte sa k nám.
Zajtra, v skutočnosti, aby praktický seminár, ak je
vás zaujímajú.
Meteor.js, alternatívne metódy pre pomocou JavaScriptu nie je v prehliadači,
ale na serveri.
Node.js, ktorý je veľmi V tomto duchu tiež.
Elegantný Android dizajn.
Android je veľmi populárna alternatíva na iOS a Windows Phone
a ďalšie mobilné platformy.
A Web Security Aktívna obrana.
>> Takže v skutočnosti, ak si prajete zapojiť sa do tohto, dovoľte mi, aby som
aby na vedomie.
Sme veľmi radi, že Naši priatelia na skok
Pohyb, ktorý je spustenie -
tento prístroj naozaj len prišiel pred niekoľkými mesiacmi -
milostivo daroval 30 týchto zariadení do triedy pre čo najväčší počet študentov, je-li
by ste chceli požičať hardvér na konci semestra a používať ho pre
Skutočná konečná projektu.
Oni podporujú veľké množstvo jazykov.
Žiadny z nich C, žiadny z nich PHP, takže realizovať jeden alebo viac z týchto seminárov
by mohlo byť zaujímavé.
A všetky z nich bude natočený v prípade, že nie ste schopní
zúčastniť osobne.
Harmonogram bude oznámené prostredníctvom email ako spevniť izby.
>> A napokon, ak idete na projects.cs.50.net, to je webová stránka
udržiavame každý rok, pozývame ľudia z komunity, fakulty,
odbory, zamestnanci a obaja na vonkajšej strane na CS50
navrhnúť projektové nápady.
Veci sú predmetom záujmu skupiny študentov.
Veci záujmu oddelenia.
Takže sa zase tam, ak budete bojovať s neistotou, pokiaľ ide o to, čo
sami chceli riešiť.
>> Takže poslednej dobe sme zaviedli pravdepodobne zložitejšie dátové štruktúry, ako my by sme
vidieť v minulých týždňoch.
Radi by sme sa s použitím polí dosť šťastne ako užitočná, ak
zjednodušujúce dátové štruktúry.
Potom sme zaviedli nich, ktoré Samozrejme sú spojené zoznamy.
A to, čo bolo jednou z motiváciou pre zavedenie tejto dátovej štruktúry?
Jo?
Čo je to?
>> Divákov: Dynamická veľkosť.
>> DAVID Malan: Dynamická veľkosť.
Takže zatiaľ čo v poli, musíte poznať jeho veľkosť zálohy, ak
prideliť ju.
V spájať zoznam, nemusíte vedieť, že.
Môžete len malloc, alebo všeobecnejšie, prideliť ďalšie
uzol, aby som tak povedal, kedykoľvek Chcem vložiť ďalšie dáta.
A uzol nie je vopred význam.
Je to len všeobecný termín, ktorý popisuje nejaký druh kontajnera, ktorý sme
použitie v našej dátovej štruktúry pre ukladanie niektoré Predmetom záujmu, ktorý je v tomto
prípade sa stalo, že celé čísla.
>> Ale je tu vždy kompromisom.
Tak sme si dynamické veľkosti dát štruktúra, ale akú cenu platíme?
Čo je to nevýhoda previazaných zoznamov?
Jo?
>> DIVÁKOV: vyžaduje viac pamäte.
>> DAVID Malan: To si vyžaduje viac pamäť, ako presne?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Presne tak.
Takže teraz sme ukazovatele nástupu do prídavné pamäti, že sme predtým
nepotreboval, pretože výhoda z poľa, samozrejme, je to, že
všetko je súvislé späť sa chrbtom k sebe, čo
vám dáva náhodný prístup.
Pretože len pomocou hranatou zátvorkou notácie, alebo viac technicky ukazovateľ
aritmetický, veľmi jednoduché sčítanie, môžete pristupovať k akýmkoľvek
prvky v konštantnom čase.
A v skutočnosti, to je niečo napovedalo ďalšie cena, ktorú platíme s
spájať zoznam.
>> Čo sa stane s dobou chodu niečo ako hľadať, keď chcem
nájsť nejakú hodnotu a vnútro prepojeného zoznamu?
Čo mi beží čas stáť?
Veľký O n
Ak je to triedené?
Čo v prípade, že dátová štruktúra je triediť?
Môžem robiť lepšie ako veľké O z n pre vyhľadávanie?
Nie, pretože v najhoršom prípade by to mohlo veľmi dobre byť triedené, ale počet
hľadáte by mohla byť veľká.
To by mohlo byť číslo 100, ktorá Môže sa stať, že všetky
ako na konci.
A pretože môžete pristupovať iba viazané Zoznam v tomto prevedení by
spôsob jeho prvého uzla, ste ešte trochu smolu.
Musíte prejsť celú vec od začiatku až do konca, aby bolo možné nájsť
že veľké hodnoty ako 100.
Alebo zistiť, či je to ani tam.
>> Takže môžeme robiť to, čo algoritmus v dátovom štruktúra, ktorá vyzerá takto?
Nemôžeme urobiť binárne vyhľadávanie, pretože binárne hľadanie vyžaduje, aby sme mali
náhodný prístup.
Mohli by sme vyskočiť z miesta na umiestnenie bez nutnosti sledovať
Tieto strúhanka vo forme všetkých týchto ukazovateľov.
>> Teraz, ako sme to realizovať?
No, či pôjdeme na obrazovku tu, ak je môžeme rýchlo implementujeme tieto dáta
štruktúra -
môj rukopis to nie je všetko, že skvelé tu, ale skúsime to.
Takže typedef struct, a čo som chcete volať tú vec tu?
Uzol.
Takže budem sa nám začalo.
A teraz, čo je potrebné, aby sa vo vnútri dátová štruktúra pre ktoré samostatne
komunikačné zoznam?
Koľko pole?
>> Tak dva.
Jedným z nich je celkom jednoduché.
Tak int n
A tak by sme mohli nazývať n čo chceme, ale mal by byť int, či sme
vykonávanie spájať zoznam pre ints.
A teraz, čo robí druhá poľa musí byť?
Struct node *.
Takže keď som to struct uzol * a potom som Môžete volať aj to, čo chcem,
ale len aby bolo jasno, zavolám je ďalší, ako sme robili.
A potom som zavriem zložené zátvorky.
>> A teraz, ako minule, Dal som uzol dole.
Ale keď som dokladá, že toto je uzol, prečo som sa obťažovať, že je tak
verbose tu deklarovať struct uzol * ďalšie, na rozdiel od
len na uzle * ďalšie?
Jo?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Presne tak.
Presne tak.
Pretože C naozaj vás doslova a vidí iba definíciu uzla
cesta sem, nemôžete odkazovať sa na to tu.
Takže máme tento druh preemptivní Vyhlásenie tu, čo je síce
viac verbose.
Struct uzol, to znamená, že môžeme teraz pristupovať
vnútri dátové štruktúry.
>> A ako stranou, pretože to je stáva trochu subjektívne teraz,
hviezda technicky možné ísť sem, to môže ísť sem, môže
dokonca ísť v stredu.
Sme prijala v štýle príručke pre Samozrejme, že konvencie uvedenie
hviezda vedľa údajov typu, ktorý je v tomto prípade,
by struct uzol.
Ale realizovať v mnohých učebniciach a on-line odkazy, môžete skutočne
vidieť, že na druhej strane.
Ale len si uvedomiť, že ako bude v skutočnosti práce a vy by ste mali byť jednoducho
konzistentné.
>> Dobrá.
Tak to bolo naše vyhlásenie of struct uzla.
Ale potom sme začali robiť viac sofistikované veci.
Napríklad sme sa rozhodli zaviesť niečo ako tabuľky hash.
Takže tu je hash tabuľka veľkosti n, indexované od 0 vľavo hore na n
mínus 1 vľavo dole.
To by mohlo byť hash tabuľka na čokoľvek.
Ale to, čo veľa vecí sme sa hovoriť o použitie hash tabuľku?
Uloženie čo?
>> Mená.
Mohli by sme mená ako sme minule.
A naozaj, môžete uložiť čokoľvek.
A uvidíme to znova PHP a JavaScriptu.
Hash tabuľky je pekný druh Swiss Armádny nôž, ktorý vám umožní ukladať
skoro čo chcete vo vnútri je to tým, že združí kľúče s hodnotami.
Klávesy s hodnotami.
>> Teraz v tomto jednoduchom prípade, naše Kľúče sú len čísla.
Sme vykonávanie hash tabuľka ako pole.
A tak sú kľúče 0, 1, 2, a tak ďalej.
A tak my, ako ľudia, rozhodla posledná týždeň, že viete, čo, keď sme
bude ukladať mená, jednoducho ľubovoľne, ale celkom rozumne,
Predpokladám, že Alice, názov, bude len byť indexované do 0.
A Bob, názov B, budú indexované do 1, a tak ďalej.
Takže sme museli mapovanie medzi vstupmi, ktoré sú reťazca a hash
umiestnenia, ktoré sú čísla.
>> Tak, že proces je všeobecne známy ako hašovacej funkcie, a môžete skutočne
implementovať v kóde.
Ak by som chcel implementovať funkcie hash že robí presne to, čo sme
práve popísal, od minule, by som mohol deklarovať funkciu, ktorá berie ako
vstup napríklad -
a ideme na to na to Obrazovka sem.
Ak by som chcel realizovať hash funkcie, mohol by som povedať,
niečo také.
>> Bude to vrátiť int.
Bude to nazvať hash, a to bude akceptovať ako argument
reťazec, alebo to môže byť vhodnejšie teraz, a hovoriť char *, budeme hovoriť to.
A potom táto funkcia má čo do činenia, nakoniec sa vrátiť int.
Teraz, ako to robí, ktoré by mohli nie je tak jasné.
Idem na vykonanie tohto bez Forma kontroly chýb práve teraz.
Idem len slepo hovoriť, vráti čo je na držiaku s 0, mínus,
povedzme, kapitál bodkočiarkou.
>> Totálne rozbité.
Nie je to dokonalé, pretože jeden, čo keď to je null?
Zlé veci sa bude diať.
Po druhé, čo keď je prvé písmeno v tejto meno nie je veľké písmeno?
To nie je dopadne z vrtov.
To by mohlo byť malé písmeno alebo nie list vôbec.
Takže absolútne priestor pre zlepšenie tu, ale to je základná myšlienka.
>> Čo sme popísali v minulom týždni verbálne len proces mapovania Alicu
0 a Bob sa 1 môže byť vyjadrená iste formulaically ako C
funkcie tu.
Zavolal znovu hash, vezme reťazec ako vstup, a potom nejako robí niečo
s týmto vstup na výrobu výstupu.
Nie na rozdiel od našej čiernej skrinky popis že sme dlho urobiť.
Neviem, ako by to mohlo byť pracuje pod kapotou.
>> Pre problémové sady 6, jeden z problémov, je pre vás rozhodnúť, čo
Váš hashovacie funkcia môže byť?
Čo bude vo vnútri, že čierna box, a pravdepodobne, bude to
trochu zaujímavejšie než to, a rozhodne náchylnejšie k chybám
kontroly, ako je táto konkrétna implementácia.
>> Ale problémy môžu nastať, že jo?
Ak máme dátová štruktúra, ako je táto jeden, čo je jedným z problémov
môžete naraziť na priebehu času vloženie stále viac a viac mien na
hash tabuľky?
Získate kolízie, nie?
Čo keď máte Alice a Árona, dvaja ľudia, ktorých mená sa stalo
začať?
To vyvoláva otázku, kde sa dal druhý taký názov?
>> No, možno naivne, jednoducho dať kde Bob patrí, ale potom Bob
druh skrutkované, ak sa pokúsite vložte svoje meno a ďalšie
nie je miesto pre neho.
Takže môžete dať Bob, kde Charlie je, a môžete si to predstaviť veľmi rýchlo
prevedie do trochu neporiadok.
Niečo lineárne na konci, kde sa stačí hľadať na celú vec
Hľadám Alice alebo Bob alebo Aaron a Charlie.
>> Tak namiesto toho navrhuje, namiesto toho, aby len lineárne snímanie pre priestranstva
a plopping mená tam sme navrhla milovník prístup.
Hash tabuľky realizované stále s rad indexov, ale dátový typ
tieto indexy teraz boli ukazovatele.
Ukazovatele k čomu?
Ukazovatele na lineárnymi zoznamy.
>> Vzhľadom k tomu, pripomínajú, že spájať zoznam je naozaj len ukazovateľ na uzol, a
uzol má ďalšie pole, a že uzol má ďalšie pole, a tak ďalej.
Takže teraz môžete myslieť na tomto poli na ľavá strana tabuľky hash ako
čo vedie k prepojeného zoznamu.
Výhodou je, ak máte kolízie medzi Alicou a Áronovi:
Čo robíte s druhý taký človek?
Môžete len pripojiť ho, aby koniec, alebo dokonca na začiatku
tohto prepojeného zoznamu.
>> A vlastne, povedzme, cez rezance že len druhý.
Ak by najväčší zmysel?
Ak vložím Alicu a ona končí Na prvom mieste, potom sa snažím, aby
vložiť Aaron meno, a tam je samozrejme kolízie, mal som
ho na začiatku prepojeného zoznamu?
To je v tomto prvom mieste, alebo na konci?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: OK.
Počul som, že na začiatku.
Preto sa už na začiatku?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: OK.
Je to podľa abecedy, tak to je pekné.
To je dobrá vlastnosť.
To vám ušetrí mi čas potenciálne.
To mi nedovolí robiť binárne vyhľadávanie, ale ja by aspoň byť schopný vymaniť sa
zo slučky, keď si uvedomujem, no, ja som cesta minulosti sa Aaron by v tomto
radené prepojeného zoznamu.
Nemám strácať čas hľadaním až do konca.
Tak to je rozumné.
Prečo inak by mohlo chcete vložiť kolízie názov na
na začiatku zoznamu?
Čo je to?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Mohlo by to trvať dlho dostať sa na koniec zoznamu.
A v skutočnosti, dlhšie a dlhšie.
Čím viac mien, ktoré vložíte začiatok, dlhšia než
reťaz dostane.
Čím dlhšie tú, ktorá súvisí Zoznam je dostane.
Takže ste naozaj len strácaš čas.
Možno, že ste na tom lepšie udržiavať konštantný Čas vloženia, veľký O z 1,
tým, že vždy dávať narážajúce na názov počiatok prepojeného zoznamu,
a nie toľko znepokojujúce o triedení.
>> Aký je najlepší odpoveď?
Je to jasné.
To druh závisí na tom, čo distribúcie je to, čo je vzor
mená vkladáte.
To nemusí byť nutne jasná odpoveď.
Ale tu je opäť design príležitosť.
>> Tak sme potom sa pozrel na tú vec, ktorá je naozaj iná veľká príležitosť
pre p-set 6.
A uvedomiť si, ak ste tak už neurobili, Zamyla sa ponorí do oboch z nich, hashovacie
tabuľky a snaží sa, vo viacerých detailu.
A video návod je vložené do p-set spec.
To bol trie -
T-R-I-E. A čo bolo zaujímavé, bolo to, že čas prevádzky
Nie je potrebné hľadať mená, ako je Maxwell Minule bol veľký O čoho?
Čo je to?
>> Divákov: počet písmen.
>> DAVID Malan: počet písmen.
Počul som dve veci.
Počet písmen a konštantnom čase.
Takže poďme sa, že ako prvý.
Počet písmen.
No, to dátová štruktúra, odvolanie, je ako strom, rodokmeň, každý z
ktorých uzly sú tvorené poli.
A tie polia sú odkazy na iné takéto uzly, či iné podobné
poľa vo stromu.
>> Takže ak by sme chceli potom určujú či Maxwell je tu, mohol by som ísť
na prvé pole, na samom vrchole strom, tzv koreň, horná časť
trie a postupujte ukazovateľ m, potom ukazovateľ, potom x,
w, e, l, l
A potom, keď vidím nejaký špeciálny symbol, označený tu ako trojuholník.
V kóde uvidíte, že navrhne, aby si implementovaný ako bool, len hovorím áno
alebo nie, slovo, tu zastaví.
>> No, raz sme išli do M-A-X-W-E-L-L, pocit, sedem, možno
osem keď ideme jeden okolo nej osem kroky na nájdenie Maxwell.
Alebo povedzme, že K. Ale spomínam posledný čas, som tvrdil, že v prípade, že je
realisticky maximálna dĺžka na slovo, rovnako ako 40-niektoré-nepárne znaky,
Maximálna dĺžka znamená, konštantnú hodnotu.
Takže naozaj, áno, je to technicky veľký O 8 alebo 7, alebo naozaj veľký O K. Ale
v prípade, že je konečný limit na to, čo K môže byť, že je konštantná.
A tak je to veľký O z 1 na konci dňa.
>> Nie je v reálnom svete.
Nie, keď skutočne začať sledovať vaše hodiny, ako váš program beží.
Je to úplne to bude trochu pomalší než skutočne konštantná
čas na jeden krok.
Bude to sedem alebo osem stupňov, ale stále je to oveľa, oveľa lepšie
než algoritmu, ako je veľký O N, ktorý závisí na veľkosti, čo je v
dátové štruktúry.
>> Všimnite si, že tu je hore, môžeme vložiť miliónkrát viac mien do tohto
dátová štruktúra, ale koľko krokov to bude trvať nám nájsť
Maxwell v tomto prípade?
Žiadne.
On je nedotknutá.
A k dnešnému dňu, nemyslím si, že sme videli, príklad dátovej štruktúry alebo
algoritmus, ktorý bol úplne ovplyvnená vonkajšie
správanie, ako je to.
Ale to nemôže byť úžasné.
To nemôže byť jediným riešením pre p-set
>> A to nie.
To nie je nevyhnutne dáta Štruktúra by ste mali tiahnuť k,
pretože rovnako ako tabuľky hash, kompromis.
Čo je to cena, ktorú zaplatíte tu?
Pamäť.
Myslím, že je to otrasné množstvo pamäti.
A môžete tak celkom vidieť tu, pretože autor obrázku
samozrejme skrátený všetkých polí a my nevidíme veľa a je
Hostely a C je a Q je a Y je a Z je v týchto poliach.
Ale sú tam.
>> Každý z týchto uzlov je celý súbor niektorých 26 alebo viac bytov, z ktorých každá
čo predstavuje list.
27 V našom prípade, tak, že môže podporovať apostrofy v sade problém.
Tak to dátová štruktúra je naozaj, naozaj hustý a široký.
A to samo o sebe by mohlo skončiť spomaľuje veci dole, alebo aspoň vás to stálo
oveľa viac priestoru.
Ale znova, môžeme vyvodiť porovnanie tu.
>> Spomínam si na chvíľu späť, sme dosiahli oveľa viac vzrušujúce doba chodu pri triedení
keď použijeme zlúčenie druh, ale cena sme zaplatili dosiahnuť n log n o zlúčení
druh vyžaduje, aby trávime viac aký zdroj?
Viac priestoru.
Potrebovali sme sekundárne maticu kopírovať ľudí do, rovnako ako
sme tu na javisku.
Takže znova, žiadne jasné víťaza, ale len subjektívne konštrukcie
rozhodnutie byť robený.
>> Dobrá.
Takže ako na to?
Každý, kto spoznať, ktoré D-Hall?
OK.
Takže tri z nás.
Mather dom.
Tak to je pre stolovanie Mather je.
Stavím sa, že všetky jedálne majú hromady zásobníkov, ako je tento.
A to je skutočne reprezentatívna o niečo, čo sme
zrejme už videli.
Nazvali sme ju doslova hromadu.
A stack, pokiaľ ide o váš pamäti počítača, je miesto, kde prejde dáta
zatiaľ čo funkcia volaná.
>> Napríklad, aké druhy vecí ísť na zásobníku s ohľadom na
Rozloženie pamäte sme diskutovali v týždňoch minulých?
Čo je to?
>> DIVÁKOV: Volanie funkcie.
>> DAVID Malan: Ospravedlňujem sa.
>> DIVÁKOV: Volanie funkcie.
>> DAVID Malan: Volanie funkcie, ale konkrétne, čo je vo vnútri každého
tie rámy?
Aké veci?
Jo.
Takže lokálne premenné.
Kedykoľvek sme potrebovali nejakú miestne úložisko, ako argument, alebo int I, alebo int
temp, alebo čokoľvek miestnej premenná, boli sme
uvedenie, že na zásobníku.
A hovoríme, že stack, pretože tohto vrstvenie myšlienky.
Len trochu zhoduje s realitou, Koncept tohto rozhodnutia.
>> Ale ukazuje sa, že zásobník možno tiež pozerať ako na dátové štruktúry,
Alternatívou k poľu, alternatívne do prepojeného zoznamu.
Niečo koncepčne zaujímavejšie že môže byť stále
realizovaný pomocou niektoré z tých, veci, ale je to iný typ
dátová štruktúra podporu, naozaj, iba dve operácie.
Ale môžete pridať na milovník funkcie než tie.
Ale to sú základy -
tlačiť a pop.
>> A nápad s hromadou je, že keď som sú tu, s alebo bez Annenberg
vedel, zásobník od vedľa s číslom 9 na ňom.
Takže len int.
A ja chcem, aby sa zasadila to na dátach štruktúra, ktorá v súčasnej dobe je prázdny.
Zoberme si to v spodnej časti zásobníka.
Ja by som tlačiť toto číslo 9 na stack, a teraz je to tu.
>> Ale zaujímavá vec o zásobníku je, že keď som chcel, aby sa zasadila
niektoré ďalšie hodnoty, ako 17, a tlačím to do zásobníka, budem robiť
iba intuitívne vec, ja som jednoducho ísť Aby som to presne tam, kde ľudia
by mať tendenciu dať na povrch.
Ale čo je zaujímavé, teraz je, ako sa dostanem na 9?
Viete, ja nie bez nejakej námahy.
>> Takže to, čo je na tom zaujímavé zásobník, ktorý je zo svojej podstaty
Je to štruktúra dát LIFO.
Silly spôsob, ako popisovať posledný dnu, prvý von.
Takže posledné číslo V tejto dobe bolo 17 rokov.
Takže keď chcem niečo pop off zo zásobníka, môže to byť iba 17.
Takže je povinný poriadok pôsobenia u nás, kde je posledná položka
musí byť v prvej von.
Preto je skratka, LIFO.
>> Tak prečo by to mohlo byť užitočné?
Sú ich kontexty, v ktorých by si Chcete dátovú štruktúru, ako je tento?
No, je to určite užitočné, vnútri počítača.
Takže operačné systémy jednoznačne použiť Druh údajovej štruktúry pre komíny.
Budeme tiež vidieť rovnakú myšlienku pokiaľ ide o webové stránky.
Takže tento týždeň a budúci týždeň a ďalej, a ako začať vykonávať web
stránky v jazyku HTML s názvom, môžete vlastne používať dátovú štruktúru, ako je
to, či stránka je v správnom formáte.
Vzhľadom k tomu, uvidíme všetky webové stránky postupujte podľa určitá hierarchia, odsadenie
, Že sa na konci dňa, sa stromová štruktúra pod kapotou.
Tak o tom viac v len trochu.
>> Ale teraz, poďme navrhnúť pre Moment, ako by sme mohli ísť o
predstavuje to, čo je stoh?
Dovoľte mi navrhnúť, že by sme realizovať zásobník s kódom, ako je tento.
Takže zásobník bude mať vnútri nej dve veci, polia, tzv vaničky,
len aby bol v súlade s demo.
A každá z položiek v tomto poli bude typu int.
A kapacita je pravdepodobne to, čo?
Pretože som nepísal úplná definícia tu.
>> Je to asi maximum Veľkosť poľa.
A je to asi deklarovaný ako ostrý definovať v hornej časti súboru, niektoré
druh konštantný ako vyplýva z samotná kapitalizácie.
Takže niekde kapacita je definovaná ako maximálnu možnú veľkosť.
Medzitým, vnútri dátové štruktúry známy ako zásobník sa bude
byť celé číslo len známy jednoducho ako veľkosť.
>> Takže ak by som mal reprezentovať to teraz obrazovo, predpokladajme, že tento
Celá čierna skrinka predstavuje svoj stack.
Vnútri nej sú dve premenné.
Takže budem čerpať Prvý je napríklad veľkosť.
A druhá idem kresliť ako pole.
>> Ale len preto, aby sa veci riadne, Normálne by som nakresliť poľa ako
, Ale je to celkom pekný ak budeme zodpovedať skutočnosti, alebo
odpovedať mentálny model.
Dovoľte mi teda namiesto toho vypracovať poľa vertikálne, čo je len opäť
umelec stvárnenie.
Nezáleží na tom, čo to je pod kapotou.
A povieme, že v predvolenom nastavení kapacita bude tri.
Takže to bude miesto 0, to bude namiesto 1, toto
bude miesto 2.
>> Keby som podplatiť s dôrazom loptou, by niekto chcel prísť a spustiť
palubu tu na chvíľu?
OK, videl vaša ruka ako prvý.
Poď hore.
Dobrá.
Takže myslím, že je Steven.
Poď hore.
Dobrá.
>> Ale predpokladajme, že teraz sme sa vrátiť a počiatočné stav sveta, kde som
práve vyhlásil stack, a to bude mať kapacitu tri.
Ale veľkosť nebola stanovená.
Zásobníky nebola stanovená.
Takže pár otázok ako prvý.
A dovoľte mi, aby som vám mikrofón, takže môžete podieľať sa aktívnejšie na to.
>> Takže to, čo je vnútri veľkosti v túto chvíľu včas, ak všetko, čo som urobil, je
vyhlásený stoh jeden riadok kódu?
>> STEVEN: Moc nie.
>> DAVID Malan: OK, nič moc.
Vieme, čo je vo vnútri veľkosti, vieme, čo je vo vnútri
tohto poľa Si tu prvýkrát?
>> STEVEN: Len náhodný kód, nie?
Just -
>> DAVID Malan: Jo, ja idem hovoria kód, ale náhodne -
>> STEVEN: Veci.
>> DAVID Malan: Veci, ako je náhodné
>> STEVEN: bity.
>> DAVID Malan: Bity, že jo?
Takže odpadky hodnoty, nie?
Takže permutácie 0 a 1 je.
Zvyšky predchádzajúcich zvyklostí tejto pamäte.
A naozaj neviem, čo sa hodnoty sú, takže väčšinou je nakresliť
ako otázniky.
>> Takže prvá vec, že ​​sme pravdepodobne bude chcieť, aby to tu -
a dovoľte mi, aby som toto pole vnútri odtiaľ názov - zásobníky.
Čo by sme mali pravdepodobne inicializovať veľkostí, ak chceme
začať používať túto stack?
>> STEVEN: Zásobník je pod 3.
>> DAVID Malan: Tak OK.
Aby bolo jasno, je deklarovaný výkon inde tri.
A to je to, čo som používal alokovať pole.
Veľkosť sa bude odkazovať na to, koľko zásobníky sú v súčasnej dobe na zásobníku.
>> STEVEN: Zero.
>> DAVID Malan: Tak to musí byť nula.
Takže choďte do toho a s akýmkoľvek prstom, nakresliť nulu veľkosti.
Dobrá.
Takže teraz, čo je vo vnútri tohto tu, nevieme.
Sú to naozaj len odpadky hodnoty.
Takže by sme mohli čerpať otázniky, ale Skúsme udržať doska čistá teraz
pretože nezáleží na tom, čo tam je.
Nepotrebujeme k inicializácii poľa k ničomu, pretože ak vieme, že
veľkosť zásobníka je nula, no, nesmie byť pri pohľade na niečo v
Toto pole tak na tento bod v čase.
>> Takže teraz, predpokladám, že tlačím číslo 9 do zásobníka.
Ako by sme mali aktualizovať dátovú štruktúru Vnútri tejto čiernej skrinky?
Aké hodnoty je potrebné zmeniť?
>> STEVEN: V -
veľkosť?
>> DAVID Malan: OK.
Veľkosť by mala byť čo?
>> STEVEN: Veľkosť by bol jeden.
>> DAVID Malan: OK.
Takže veľkosť by sa mala stať jedným.
Takže si môžete urobiť v pár ohľadoch.
Dovoľte mi, aby som vám teraz vaša Prst je guma.
Dobrá.
Tak teraz je prst kefu.
Dobrá.
A teraz, čo ešte sa musí zmeniť, Je zrejmé, že v dátovej štruktúre?
>> STEVEN: Ideme od zdola až 9.
>> DAVID Malan: 9.
OK, dobre.
Takže ešte nezáleží, čo je v umiestnenie jeden alebo dva, pretože sú
odpadky hodnoty, ale nemali by sme sa obťažovať hľadá tam, pretože veľkosť je
nám hovorí, že iba prvý prvok je vlastne legitímna.
Takže teraz tlačím 17 na zozname.
Čo sa stane obrázku?
>> STEVEN: Takže veľkosť sa chystá ísť na dva.
>> DAVID Malan: OK.
Ste guma -
oops.
Ste gumu.
>> STEVEN: Eraser.
>> DAVID Malan: Si kefu.
>> STEVEN: Brush.
>> DAVID Malan: OK.
A čo ešte?
>> STEVEN: A potom sme -
>> DAVID Malan: Usilovali sme 17.
>> STEVEN: Držíme 17 na vrchole, a preto -
>> DAVID Malan: OK, dobre.
>> STEVEN - klesnúť dole.
>> DAVID Malan: Dobre.
Začína to byť jednoduché.
Nebudem, ktoré vám pomôžu tentokrát.
Zatlačte 22.
>> STEVEN: Hotovo.
Štát gumu.
Stávam sa štetcom.
A potom dávam 22.
>> DAVID Malan: 22.
Výborný.
Takže ešte raz.
Ja som teraz bude tlačiť do zásobníka 26.
>> STEVEN: Ooh.
Ach bože.
Naozaj ma zaskočila.
>> DAVID Malan: To snáď nie pozri tento rok?
>> STEVEN: Nevidel som to blíži.
Mohli by sme znova počiatočná kapacita?
>> DAVID Malan: To je dobrá otázka.
Takže sme trochu maľoval seba v rohu tu.
Tam naozaj nie je dobrý pozor Steven pretože sme pridelené toto pole
staticky, aby som tak povedal, vnútri z dátovej štruktúry.
A my sme v podstate pevne zakódovaný sa, že je veľkosť tri.
Takže naozaj nemôžeme prerozdelia ju.
>> Mohli by sme, keby sme išli naspäť, sme obnovovaný zásobníky sa ukazovateľ, ktorý
sme potom pomocou malloc do ruky pamäti.
Pretože ak máme pamäť, z haldy pomocou malloc, sme
by potom uvoľniť ho.
Ale skôr, než ju uvoľní, mohli by sme prerozdeliť väčší kus pamäti,
aktualizovať ukazovateľ, a tak ďalej.
Ale teraz je to naozaj najlepšie, čo môžeme urobiť.
Stlačte a pop sa pravdepodobne bude majú uviesť niektoré chyby.
>> Tak napríklad, naše realizácie Push by sa mohol vrátiť bool, ktorá
predtým vrátil pravda, pravda, pravda.
Ale štvrtý čas, bude to mať vrátiť false, napríklad.
Dobrá.
Veľmi dobre.
Blahoželáme.
Získali ste stresu loptu dnes.
>> [APPLAUSE]
>> STEVEN: Ďakujem.
>> DAVID Malan: Ďakujem.
OK, tak to sa zdá byť moc o krok vpred, nie?
Popísali sme túto dátovú štruktúru.
Bolo to pôsobivé, nie?
Operačné systémy páčiť.
Zrejme na webe môžete využívať toto, a ďalších aplikácií stále.
Ale to, čo hlúpe obmedzenia, že sme späť na triedenie v týždni dva limity
kde sme pevnú veľkosť poľa.
>> Takže tam sú naozaj pár spôsoby, ako by sme mohli vyriešiť.
Mohli by sme dynamicky alokovať pole, nie ťažké kódovanie ako som
hotoví, ale znova, ktorým to, aby bolo jasno, ako
niečo také.
Int * zásobníky, nerozhoduje na objeme ešte.
Ale keď som vyhlásil stoh inde v mojom kóde, mohol by som potom volania malloc,
získať adresu kusom pamäť, a ja som mohol priradiť
že adresa zásobníkov.
>> A potom, pretože je to len kus pamäť, mohol by som aj naďalej používať námestí
držiak zápis obvyklým spôsobom.
Vzhľadom k tomu znova, je tu nejako to funkčným ekvivalentom polí a
kúsky pamäti, ktoré prichádzajú späť z malloc.
Môžeme správať ako ostatní pomocou ukazovateľa aritmetický alebo
hranatá zátvorka notácie.
Takže to je jeden prístup.
>> Ale ako inak by sme mohli zaviesť tento rovnaké dátové štruktúry, prípadne?
Je to tak?
Mám pocit, že práve to vyriešil problém ako pred týždňom.
Čo bolo riešenie tohto problému že Steven narazil?
Takže spojové zoznamy, vpravo.
>> Ak je problém, že maľujeme sami do rohu prideľovanie
dopredu príliš málo pamäti, že potom sa nejako riešiť, no,
prečo nie len zabrániť tomu, aby vydá dohromady?
Prečo nie len vyhlásiť zásobníky sa ukazovateľ na uzol, ergo spájať zoznam,
a potom jednoducho prideliť nové uzly zakaždým, keď Steven potrebné, aby sa zmestili
číslo do dátovej štruktúry.
>> Takže obraz by mal zmeniť.
To nebude tak čisté a ako jednoduché, ako len polia troch ints.
Teraz to bude ukazovateľ na struct, a to struct sa chystá
majú int a ďalšie ukazovateľ.
Je to povedie prostredníctvom tohto ukazovateľa iné takéto struct na
ďalší taký struct.
Takže fotka by v skutočnosti dostať trochu Messier.
A boli by sme šípky viazanie všetko dohromady.
>> Ale to je v poriadku, že jo, pretože Videli sme, ako to urobiť.
A akonáhle sa dostanete pohodlne vykonáva niečo ako prepojený
zoznam, ktorý budete musieť robiť, keď rozhodnete hash tabuľku s
oddelené zreťazenie pre p-set 6, môžete ho použiť ako stavebný blok, alebo
prísada, alebo Scratch hovoriť, postup, niečo, čo dáte, vám
vytvorili svoj vlastný kúsok skladačky ktoré potom môžete znovu použiť.
Takže kompromisy, ale možné riešenia že sme vlastne nevideli.
>> Takže docela často, vidíte to každý rok alebo dva, keď Apple vydal
niečo nové, a všetci blázni line up mimo Apple
uložiť ku kúpe ich marginálne prejsť na hardvér.
Hovorím to, je to v poriadku, pretože Som jeden z tých ľudí.
Takže, aké dátové štruktúry môže predstavovať túto skutočnosť?
>> No, povedzme, že front, linka.
Takže Briti to nazval typicky front rovnako, takže je to pekné meno.
A dve operácie, ktoré fronty musí podporovať budeme volať Zaradí
prevádzka a dequeue prevádzka, ktoré sú si podobné
duch tlačiť a pop.
Je to len trochu líši konvencie, čo hovoríme nich.
Ale enqueue niečo znamená pridať alebo vložiť do dátovej štruktúry.
Dequeue znamená odstrániť.
Ale vzhľadom k tomu, zásobník bol dátový LIFO štruktúra, fronta je prvá,
Prvý z dátovej štruktúry.
>> Ak ste prvý človek v rade, budete prvá osoba, ktorá sa
z radu a kúpiť si nový prístroj.
Predstavte si, ako naštvaný títo ľudia by ak Apple namiesto toho používal balík pre
inštancie, na vykonanie vychystávanie do vašej novú hračku.
Takže fronty zmysel, určite, a my môžeme myslieť na všetky druhy
aplikácie, pravdepodobne pre front, zvlášť keď chcete spravodlivosť.
Takže, ako môžeme realizovať tieto ako dátové štruktúry?
>> Navrhujem, že by sme mohli musíte urobiť to takto.
Takže budem teraz mať čísla.
Takže budeme držať to jednoduchý, a nie nutne hovoriť, pokiaľ ide o zásobníkov.
Len čísla, ktoré ľudia dostali.
Kapacita bude opäť upevnite Celkový počet osôb, ktoré môžu byť v
tento riadok ako troch alebo bez ohľadu na iná hodnota.
>> Ale navrhujem, že musím sledovať nielen veľkosťou
fronta, koľko vecí v ňom.
Takže veľkosť je aktuálna veľkosť, kapacita je maximálna veľkosť.
Len raz, nomenklatúra konvencií.
Prečo potrebujem ďalšie int vnútri z frontu, ako sledovať, kto je v
prednej línie?
Prečo musím k tomu, že v tomto prípade?
>> No, ako sa tento obrázok sa zmení?
Mohol by som opätovne využiť väčšinu obrázku.
Nechaj ma ísť napred a vymazať to, čo je tu.
Dáme to ľahko iné meno tu.
Poďme sa zbaviť 17, zbavme na 9, poďme sa zbaviť 3.
A dodajme ešte jednu vec.
Navrhujem, že musím sledovať predné zoznamu, ktorý je práve
Bude tiež int.
A budeme držať to jednoduchý.
Nie spájať zoznam teraz.
>> Budeme sa priznať, že budeme Narazí tohto limitu.
Ale čo ja chcem vidieť sa stalo tentoraz?
Tak, že som do toho pustite a prvý osoba je v súlade, a
je to číslo 9..
Máme stres gule.
Môžem ukradnúť, povedzme, dva alebo tri ľudí?
Jedna, dva, tri?
Poď hore.
Právo spredu, pretože urobíme tohle rýchlo.
>> Každý z vás sa teraz bude fan chalan vo fronte na Apple.
Nebudete dostávať Apple hardvér Na konci tohto hoci.
Dobrá.
Takže ty si číslo 9, ty si číslo 17, číslo 22.
Tie sú ľubovoľné čísla, ako je Študent ID alebo ktovie čo ešte.
A za chvíľu, začnime začať pridávať veci.
A ja budem bežať dosku tu tentoraz.
>> Takže v tomto prípade som si inicializuje predné byť -
Vlastne som naozaj nestarám, čo predná časť je, pretože veľkosť je nula.
Takže to môže byť aj len byť otáznik.
To všetko sú otázniky.
Takže teraz začneme skutočne vidieť niektoré ľudia čakajú, až v obchode.
>> Takže ak číslo 9, ty si prvý, tam v 5 hodín ráno, choďte do toho a line up,
alebo v noci.
OK.
Takže teraz 9 je tu.
Takže 9 je v prednej časti zoznamu.
Takže budem pokračovať a aktualizovať Veľkosť tohto aktuálnych dát
štruktúru, ktorá nie je už 0, ale na 1.
Chystám sa dať na 9 Predné zoznamu.
Nechaj ma ísť dopredu a prepínať obrazovky takže vidíme okolo nás tu.
>> A teraz čo chcem dať na prednej strane?
Budem sledovať, že predné fronty hneď
je v mieste 0.
Pretože to, čo sa bude diať nabudúce?
No, predpokladám, teraz som enqueue 17 tiež.
Tak hop v rade tam.
A opäť, typ dverí Obchod sa tu bude.
Takže teraz som pridal 17.
A aj keď títo chlapci sú blokovania obrazovka, to je v poriadku,
pretože vidíme to tu.
Prepáčte.
>> DIVÁKOV: Môžeme sa pohybovať -
>> DAVID Malan: Nie, to je v poriadku.
Je to obrovská tam.
Takže 17 je teraz vo vnútri fronty.
Musím aktualizovať, ktorá Pole teraz keď?
OK, určite veľkosti.
A čo predné?
OK, no.
Predné by sa nemalo meniť, pretože na rozdiel od zásobníka, sme
chcete zachovať spravodlivosť.
Takže ak 9 prišiel prvý, chceme 9 , Že je prvý z radu
do obchodu.
>> V skutočnosti, nech sa na to.
Než vložíme 22, poďme choďte do toho a dequeue 9.
Ako sa voláte?
>> Divákov: Jake.
>> DAVID Malan: Jake sa deje byť dequeued teraz.
Takže ste si na prechádzku do obchodu.
A predstierať, že obchod je tamto.
Takže teraz, čo je potrebné - dit-dit-dit!
Čo by sa stalo teraz?
Návrh rozhodnutia.
Takže nie je zlý inštinkt, ale - čo sa to voláte?
>> DIVÁKOV: David.
>> DAVID Malan: David.
Takže to, čo Dávid urobil?
Snažil sa nejako opraviť údaje štruktúra a pohyb od jeho umiestnenia
v bývalom mieste Jake.
A to je v poriadku, ak sme ochotní prijať, že ako
implementačný detail.
Ale najprv poďme aktualizovať dáta štruktúru, ako to robíme.
Pretože som nepáčil nápad všetkých ľudia posun v tomto odbore.
>> Nie je to veľký problém, ak David robí s jeden krok, ale opäť si spomeniem na
keď sme mali osem dobrovoľníkov na etapa a urobili sme ako vloženie
triedenie, kde sme museli začať pohybujúce sa všetci okolo.
To má drahá, že jo?
To ma krčiť sa o veľké O n, veľký O n na druhú znova.
Nie je to pocit, ideálny výsledok.
>> Takže povedzme, aktualizovať to.
Takže veľkosť fronty nie je 2.
Je to teraz jednoducho jedno.
Ale teraz môžem aktualizovať niečo Nechcel som aktualizovať skôr,
Predné zoznamu.
Mohol by som povedať, je, že namiesto 1?
Takže teraz máme odpadky hodnoty tu odpadky hodnota tu a David v
Uprostred tohto odpadu.
Ale štruktúra dát je stále neporušená.
>> A v skutočnosti som ani potreba zmeniť Jake je bývalý číslo
9, pretože koho to zaujíma.
Mám dostatok informácií, teraz v veľkosť, že viem, je tu ešte jedna osoba
Táto fronta.
A viem, že táto osoba je v mieste 1, nie 0.
Nepočítam.
1. tak i
Takže dátová štruktúra je ešte OK.
>> No, čo sa stane ďalej?
Poďme enqueue -
Ako sa voláte?
>> Divákov: Callen.
>> DAVID Malan: Callen.
Poďme si enqueue Callen a 22 je teraz vo fronte.
Takže teraz, čo sa musí zmeniť, tu?
Predné nebude zmeniť, samozrejme.
Veľkosť sa zmení na 2 znova.
A 22 skončí tu, 9 je stále prítomná, ale je to skutočne
odpadky hodnota sa.
Je to len pozostatok minulosti Jake.
>> Takže teraz, čo sa stane, keď Aj dequeue Davide?
Jedna posledná operácia, dequeue David.
Mohli by sme sa posunúť, ale navrhujem, poďme čo najmenej práce, ako je to možné.
Teraz môj dátová štruktúra ide späť vo veľkosti 2-1.
Ale fronty Teraz sa 2.
Nepotrebujem, aby tieto čísla zmeniť ešte nie, pretože sú
len nezmyselné hodnoty.
>> Ale teraz, čo sa stane?
Dajme tomu, že som enqueue, 26?
Mám pocit, že patrím sem.
Takže som bol enqueued.
Tak nejako som sem patrím.
A aj keď to nie je úplne vážim vizuálne na javisku,
pretože máme dostatok priestoru, mal by som nemožno tu stojím, prečo?
>> DIVÁKOV: Si mimo hraciu plochu.
>> DAVID Malan: Správne.
Som mimo medze.
Som indexované za hranice tohto poľa.
Mal by som byť v jednom z tri možné lokality.
Tak, kde je najprirodzenejší ísť?
Navrhujem, aby sme pákové týždeň jeden trik.
Operátor modulo, percento.
Pretože som stál pri technicky miesto 3, ale mám 3 mod kapacity,
takže 3, znak percenta, 3 -
Kapacita je 3.
Čo je to?
Čo je to zvyšok po delíte 3 od 3?
0.
>> Tak, že ma stavia sa Jake, čo je vlastne dobre.
Takže teraz vykonávania z toho, čo sa deje na
byť trochu bolí hlava.
Je to naozaj len jeden riadok bolesti hlavy, kódu.
Ale aspon teraz je tu odpadky hodnotu, ale je tu to dva
legitímne ints tu.
A tvrdím, že teraz sme urobili presne to, čo musíme urobiť, tak dlho, kým
zmeníme to, čo Jake hodnota mala byť 26.
>> Teraz máme dostatok informácií, stále zachovanie integrity
tejto dátovej štruktúry.
Sme stále trochu smolu, keď sme Chcem vložiť štyri alebo viac celkom
prvky, ale môžem sa aspon pekne efektívne využitie tejto konštanty
čas, v skutočnosti.
Nechcem sa starať o radenie všetci, pretože sklon Davida bolo.
>> Akékoľvek otázky týkajúce sa komínov alebo to front?
>> DIVÁKOV: Je dôvod, prečo Potrebujete veľkosť, takže viete,
kde má človek?
>> DAVID Malan: Presne tak.
Musím poznať veľkosť poľa pretože musím presne vedieť, ako
mnoho z týchto hodnôt sú legitímne, a aby nájdem, kam umiestniť
ďalšia osoba.
Presne tak.
Veľkosť je -
Vlastne sme nemali aktualizovať to ešte.
Pridal som sám na 26 rokov.
Veľkosť je teraz, nie jeden, ale dva.
Takže teraz to naozaj pomáha mi nájsť hlava zoznamu, ktorý nie je 0, nie je
1, ale je 2..
Na prednej strane zoznamu je naozaj číslo 22.
Vzhľadom k tomu prišiel ako prvý, a tak by povolené do obchodu predo mnou,
aj keď vizuálne stojím bližšie k obchodu.
>> V poriadku?
Potlesk pre týchto ľudí a necháme ich odtiaľ.
>> [APPLAUSE]
>> DAVID Malan: Nemohol som nechať budete mať zásobník.
Mohli sme vidieť, čo sa stane, keď chcete, ale možno tiež nie.
Dobrá.
Tak čo teraz čo z toho plynie?
No, dovoľte mi navrhnúť, aby tam niekoľko ďalších dátových štruktúr by sme mohli
začať pridávať do nášho náradia, ktoré v skutočnosti je úplne, úplne relevantné
sme sa ponoriť do vecí webe.
Čo zase má nejaké spojenie na stromy vo forme
niečo ako DOM, dokument objektový model.
Ale uvidíme viac že onedlho.
>> Dovoľte mi navrhnúť, z definície, že sme zavolajte strom teraz, čo by ste mohli vedieť, ako
viac rodokmeni, kde nejaký predok na
Korene stromu.
Patriarchálnej alebo matriarchát na samom vrchole stromu.
Bez svojho manžela, v tomto prípade.
Ale teraz máme, čo budeme nazývať Deti, ktoré sú uzly, ktoré visia
z ľavej alebo pravej dieťa dieťa, šípky, ako je znázornené tu.
>> Inými slovami, v stromovej štruktúre dát v počítači, strom má nulu
alebo viac uzlov.
Ak má aspoň jeden uzol, tomu sa hovorí koreň.
Sú to veci, ktoré vizuálne čerpáme na vrchole.
A to uzol, ako každý iný uzol, môže majú nulový, jeden, alebo dva, alebo tri,
alebo ako veľa detí dátová štruktúra podporuje.
V tomto prípade, koreň, skladovanie hodnoty jedna, má dve deti, 2 a 3,
takže sme zvyčajne vyžadujú dva ľavej Dieťa a 3 právo dieťa.
>> A potom, keď sa dostaneme až 5, 6, a 7, 6 by sa dalo nazvať prostredné dieťa.
Pokiaľ máte štyri deti, to bude mätúce.
Tak sme sa prestať používať tento druh o zástupcu ústne.
Ale je to naozaj len rodokmeň.
A listy sú tu uzlov, ktoré samy o sebe nemajú žiadne deti.
Visí na dno stromu.
>> Takže, ako môžeme realizovať strom, ktorý má len dve deti maximálne?
Nazveme to binárny strom.
Bi opäť znamená dva, v tomto Rovnako tak ako s binárny.
A tak to môže mať nula, jedna, alebo maximálne dve deti.
>> Ja navrhujem, aby sme realizovať uzol pre túto štruktúru s int n,
a potom dva ukazovatele, jeden s názvom vľavo, jeden volal pravdu.
Ale to sú len pekné ľubovoľné konvencie.
A čo je pekné teraz, najmä pokiaľ druh bojoval s koncepčne
rekurzia, alebo si myslel, že to nie je naozaj riešenie pre čokoľvek,
najmä ak by spustiť z pamäte.
Teraz, keď hovoríme o dátach štruktúry a algoritmy, ktoré umožňujú
nás prejsť a manipulovať s nimi, Ukazuje sa, že rekurzia je späť
oveľa presvedčivejšie ak nie je krásny spôsob.
>> Takže to navrhujem, je implementácia z funkcie Hľadať.
Vzhľadom k tomu, dva vstupy -
tak, že ju ako čierna skrinka.
Vzhľadom k tomu, dva vstupy, n, int a ukazovateľ na strom, ukazovateľ na
uzol, alebo naozaj koreň stromu, som Tvrdenie, že táto funkcia môže vrátiť
true alebo false, že hodnota n je vnútri tohto stromu.
>> Čo je vo vnútri tejto čiernej skrinky?
No, štyri vetvy.
Prvá len kontroluje.
Je-li strom je null, stačí sa vrátiť false.
Pokiaľ nie je žiadny uzol, n nie, tam žiadne číslo, len return false.
Ak však, n, hodnota, ktorú hľadáte pre, je menšia než stromu šípky n, a
Len aby bolo jasno, čo to znamená, keď Píšem strom a potom kliknite na šípku
notácie, n?
Presne tak.
To znamená, že dereferencia ukazovateľ tzv strom.
Choďte tam, a potom sa vo vnútri, ktoré uzol a získať jeho pole s názvom n
A potom porovnávajú skutočné n, ktorý bol prešiel do vyhľadávacieho proti nemu.
>> Takže, ak n je menšia ako hodnota n v uzle stromu sám, dobre,
čo to znamená?
To znamená, že nič na prvý pohľad.
Je to tak?
Rovnako ako keď máte rad hodnoty, mali by ste chceli použiť binárne
vyhľadávanie ako formu predelu a panuj.
Ale to, čo sme predpoklad, je potrebné, aby pre binárne hľadanie práce vôbec
v telefónnom zozname a skôr príklady?
>> Ako majú byť triedené.
Takže poďme upresniť definíciu stromu tu nesmie byť len strom, ktorý môže
mať ľubovoľný počet detí.
Nie je to len binárny strom, ktorý môže sú 0, 1, 2 alebo maximálne.
Ale ako binárny vyhľadávací strom, alebo BST ktorý je len ozdobný spôsob, ako hovoriť
binárny strom, tak, že každý uzol je vľavo dieťa, ak je prítomný, je
menej než uzla.
A každý uzol má pravdu dieťa ak je k dispozícii, je väčšia
než samotný uzol.
>> Takže inými slovami, ak vás k tomu strom sa, všetky čísla sú
starostlivo vyvážiť, ako je to tak, že ak Máte 55 ako root, môže ísť 33
po jeho ľavej strane, pretože to je menej ako 55 rokov.
77 môže ísť po jeho pravej strane, pretože je to viac ako 55 rokov.
Ale teraz nevšimol, rovnakú definíciu, Je to rekurzívne definície ústne,
musí požiadať o 33.
33 ľavá dieťa musí byť menšie než to, a 33 na pravej dieťa, 44, musí byť
väčšie než to.
>> Tak to je strom binárneho vyhľadávania, a Navrhujem, s použitím trochu
rekurzia, môžeme teraz nájsť n
Takže pokiaľ je n menšie ako hodnotu n, ktorá je aktuálny uzol, ja idem
dopredu a punt, aby som tak povedal, a len vrátiť bez ohľadu na odpoveď na
vyhľadávanie na n stromu je ľavá dieťa.
Všimnite si, opäť, táto funkcia len očakáva uzla STAR,
ukazovateľ na uzol.
Tak určite som si len urobiť strom Šípka vľavo, čo povedie
Prechod k inému uzlu.
Ale čo je to uzol?
>> No, podľa tohto vyhlásenia, vľavo je len ukazovateľ, takže stačí
znamená, že som okolo na vyhľadávacie funkcie iný ukazovateľ, a to
ktorý reprezentuje Moja ľavá dieťaťa strom.
Takže v tomto prípade, ukazovateľ 33, ak je To je náš výber vstupu Zatiaľ, ak
n je väčšie ako hodnotu n na aktuálny uzol v strome, potom som
ísť dopredu a pramice v druhej smer a len povedať, vôbec sa mi nepáči
vedieť, či je táto hodnota n je v stromovej štruktúre ale viem, že ak je to, že je to po mojej
právo vetva, aby som tak povedal.
Dovoľte mi teda volanie rekurzívne prehľadávať, vykonaním n znovu, ale odovzdaním
ukazovateľ na mojej pravej dieťa.
>> Inými slovami, keď som v súčasnej dobe 55 a hľadám pre 99, ja viem, že 99
je väčší ako 55, takže presne ako som roztrhol týždne telefónneho zoznamu rokmi a my
išiel doprava, podobne ako sme ísť tu.
A ja neviem, či je to na mojej pravici dieťa, a to nie je, 77 existuje, ale
Viem, že je v tomto smere.
Takže hovorím hľadanie na pravom dieťa, 77, a nechajte vyhľadávacie postavu z
ak existuje 99 v tomto ľubovoľná Príkladom je v skutočnosti tam.
>> Inak, čo je posledný prípad?
Je-li strom je null jeden prípad.
Ak n je menšia než je aktuálna uzol je hodnota je iný prípad.
Ak n je väčšie ako aktuálny uzla hodnota je tretí prípad.
Čo je štvrtý a posledný prípad?
Myslím, že sme z prípadov, nie?
To tak, že n je aktuálny uzol, že som na.
>> Takže keď som hľadal 55 v tomto bode v príbehu, že pobočka
strom sa vráti true.
Takže to, čo je zaujímavé, je, že sme v skutočnosti, na rozdiel od minulosti týždňov, sme trochu
na dva základné prípady.
A oni nemajú byť všetko v hornej časti.
Horný je základný prípad, pretože v prípade, že Strom je null, nič robiť.
Stačí sa vrátiť pevný kódované hodnota false.
>> Spodná vetva je trochu predvolené, pričom keď sme skontrolovať
null, sme skontrolovať, či má byť vľavo, ale to by nemalo byť, máme
kontroluje, či by mal byť správne, ale nemali by byť zrejmé, že musí byť
tam, kde sme.
To je základná vec.
Takže tam sú dve rekurzívne prípady obložené tam uprostred.
Ale ja som mohol napísať to v ľubovoľnom poradí.
Len som myslel, že to trochu prišlo prirodzené najprv skontrolujte, či prípadné chyby,
potom sa pozrite doľava, potom sa hneď, potom Predpokladám, že ste na uzle
ste vlastne hľadáte.
>> Tak prečo by to mohlo byť užitočné?
Tak to dopadá -
a dovoľte mi prejsť na ukážku tu je to na webe.
Chystáme sa začať používať nie programovací jazyk na prvý, ale
značkovací jazyk.
Značkovací jazyk je ten, ktorý je svojim duchom podobať programovanie
jazyk, ale to vám nedáva schopnosť vyjadriť sám seba logicky.
To vám dáva možnosť vyjadriť sám seba štrukturálne.
>> Kam chceš dať niečo na stránke, webová stránka?
Akú farbu chceš, aby sa to?
Aké písmo chceš, aby sa to?
Aké slová sa vlastne Chcete na webovej stránke?
Takže je to značkovací jazyk.
Ale potom sme si veľmi rýchlo zavádzať JavaScript, ktorý je plnohodnotným
programovací jazyk.
Veľmi podobný vo vzhľade syntakticky na C, ale bude to mať nejaký
pekné, silnejšie, užívateľsky prívetivé funkcie.
>> A jeden z frustrácie na to bod v semestri, je, že budeme
čoskoro realizovať pravopisu v ďaleko menej riadkov kódu pomocou iné jazyky
ako C sám umožňuje, ale z dôvodu ich Čoskoro budeme rozumieť.
Bude to prvá takáto webová stránka.
To bude úplne nezaujatý, Prvý robíme.
To sa jednoducho povedať, hello world.
Ale ak ste nikdy nevideli pred, to je HTML,
HyperText Markup Language.
>> Ak pôjdete do určitej menu v takmer akýkoľvek prehliadač na akejkoľvek webovej stránky, na
internet, môžete vidieť HTML že niektorí ľudia písali
vytvoriť túto webovú stránku.
A to asi nevyzerá ako krátky alebo čistý, pretože to.
Ale bude nasledovať vzor z nich otvorené zátvorky a lomítka a
písmená a potenciálne čísla.
>> Myslel som, že vám ukážku z toho, čo budete môcť robiť
po užití CS50.
Nechaj ma ísť do cs.harvard.edu / rob, našej vlastnej Roba Bowdenová domovskú stránku.
Urobil to pre nás.
Takže budete čoskoro môcť urobiť.
A tiež to, čo ste počuli dnes ráno -
to, čo si počul dnes ráno -
>> [HAMSTER DANCE MUSIC]
>> - Budeš mať možnosť, aby sa to.
To nás čaká v stredu.
Uvidíme sa potom.
>> [HAMSTER DANCE MUSIC]
DAVID Malan: Na ďalší CS50 -