>> DAVID Malan V redu.
Dobrodošli nazaj v CS50.
To je začetek 8. tednu.
In opozarjajo, da problem set 5 končalo z malo izziv.
Torej, ob predpostavki, da izterja vse vaše poučevanje Fellows in fotografije CA
v datoteki card.raw, ste upravičeni za zdaj našli vse te ljudi, in
en srečen zmagovalec bo hodil domov z enim od teh stvari, skok predlog
Naprava, ki jo lahko uporabite za končno projekti, na primer.
>> To, vsako leto vodi malo creepiness.
Pa kaj sem mislil, da sem naredil, je delež z vami nekaj opomb, ki imajo
šli naprej in nazaj Seznam osebja prepozno.
Na primer, samo sinoči citatom citata iz ene osebja
člani, "sem imel študentsko trkanje na moja vrata, da posnamete fotografijo z mano.
Zalezovalci, vam povem. "Začelo precej opisna in potem smo se preselili
na, uro ali tako kasneje, "Imel sem Študent me čaka po oddelku
in je imel vse naše imena in fotografije na nekaj listov papirja. "Vse je v redu.
Tako organizirana, vendar ne vse to grozljivo še ni.
>> Potem, "sem bil iz mesta ta vikend, in ko sem se vrnil, je bil eden od
moja
spalnica. "[SMEH]
DAVID Malan: Naslednji citat iz osebja član, "študent prišel v mojo hišo na
Somerville ob 4:00 zjutraj. "Next Osebje, "sem prišel do mojega hotela v San
Francisco in študent je čakala me je v preddverju s tremi dslr. "
Vrsta fotoaparata.
"Nisem niti za zaposlene ta semester, ampak študent je vlomil v mojo hišo to
zjutraj in posnel celotno stvar z Google Glass. "In potem končno,
"Vsaj 12 ljudi, ki so nestrpno čaka za mene, ko sem prišel iz mojega
limuzina, nato pa sem
zbudil. "V redu.
Torej med slikami, kot si lahko spomnim, je ta človek tukaj, kdo ste
Morda veste, kot Milo Banana, ki živi z Lauren Carvalho, naše glave
poučevanje člana.
Milo, Milo, pridi sem fant.
Milo.
Misli si, on je nosil Google steklo, tako da vam bomo pokazali vse to potem.
Torej, to je Milo, če bi želeli slikati z njim kasneje.
Če želite, da pazi na občinstvo tam.
OK.
To je dober posnetek.
No, Milo Banana.
Oh, ne delaj tega.
>> [SMEH]
>> OK.
Torej besedo, potem o tem, kaj je pred nami, saj, kot smo začeli prehod,
ta teden posebej od C pri ukazni vrstici okolja v PHP, in
JavaScript ter SQL in HTML in CSS v okolje spleta, bomo
vam opremljanje z vsemi Več znanja za
potencialnih končnih projektov.
V ta namen so, seveda ima tradicija seminarjev, ki
so na dotikajo teme v teku.
Zelo povezana z načrtovanjem in Razvoj app in tako naprej, vendar
ni nujno proučiti Tečaj lastne učni načrt.
>> Torej, če vas bo morda zanima ena ali več od letošnjih seminarjev,
registrirati na cs50.net/seminar.
Obstajajo starejši seminarji ob cs50.net/seminars.
In na roster doslej za to leto so Amazing Web Apps z Ruby na
Tirnice, ki je alternativa jezik za PHP.
Computational Linguistics.
Uvod v iOS, ki je platforma, ki se uporabljajo za iPhone in
iPad razvoj.
Javascript za Web Apps bomo zajema da, vendar v tem seminarju, boš šel
bolj v podrobnosti.
>> Predlog preskok, tako da bomo dejansko imeli nekaj naših prijateljev iz Leap Motion,
družba sama, se nam pridružite.
Jutri, v resnici, da zagotovi hands-on seminarju, če
, ki vas zanimajo.
Meteor.js, alternativna tehnika uporabljajo JavaScript ni v brskalniku
ampak na strežniku.
Node.js, ki je zelo v tej smeri, kot tudi.
Tanko Android dizajn.
Android pa zelo priljubljena alternativa za iOS in Windows Phone
in druge mobilne platforme.
In Web Security Active Defense.
>> Torej, v bistvu, če bi želeli da se vključijo v to, kaj mi
zapomnite si to.
Zelo smo veseli, da rečemo, da Naši prijatelji Prestopna
Predlog, ki je ob zagonu -
ta naprava res samo prišel pred nekaj meseci -
je milostno daroval 30 takih naprav v razredu za toliko študentov, če
bi radi, da se zadolži strojne opreme proti koncu semestra in jo uporabite za
Dejanski končni projekt.
Jih podpirajo več jezikov.
Nobena od njih C, nobena od njih PHP, tako dosego enega ali več od teh seminarjev
lahko izkaže interesa.
In vse od njih bo posnet v V primeru, da ne boste mogli
udeležiti osebno.
Načrt je napovedal preko email, kot smo strdi sobe.
>> In nenazadnje, če greš na projects.cs.50.net, to je spletna stran
trdimo, da je vsako leto povabimo ljudje iz skupnosti, fakultete,
oddelki, osebje, in obe v zunanji CS50 do
predlagala projektne ideje.
Stvari, ki so v interesu študentskih skupin.
Stvari, ki so v interesu službe.
Torej, ne pa tam, če ste se borijo z negotovostjo glede tega, kaj
si želi lotiti.
>> Torej zadnjič, ko smo uvedli verjetno bolj zapletena struktura podatkov, kot sva
videli v zadnjih tednih.
Mi bi bili z uporabo nizov precej srečno kot koristno, če
poenostavljeno strukturo podatkov.
Potem smo uvedli ti, ki Seveda so povezane sezname.
In tisto, kar je bil eden od motivov za uveljavitvijo te podatkovne strukture?
Ja?
Kaj je to?
>> PUBLIKA: Dynamic velikost.
>> DAVID Malan: Dynamic velikost.
Torej, medtem ko je v polju, morate vem, njeno velikost predplačila, kadar
jo dodeli.
V povezano seznamu, pa ne vedeti, da.
Lahko samo malloc, ali bolj na splošno, dodeli dodatna
vozlišče, tako rekoč kadarkoli želite vnesti več podatkov.
In vozlišče ni vnaprej določen pomen.
To je samo splošen izraz, ki opisuje nekakšen posodi, ki smo
uporabo v našem podatkovne strukture za shranjevanje nekatere element interesa, ki v tem
primer zgodi, da bo cela.
>> Ampak tam je vedno kompromis.
Tako smo dobili dinamične velikosti podatkov strukture, ampak kakšno ceno bomo plačali?
Kaj je slaba stran povezanih seznamov?
Ja?
>> PUBLIKA: zahteva več pomnilnika.
>> DAVID Malan: To zahteva več spomin, kako točno?
>> PUBLIKA: [neslišno].
>> DAVID Malan: Točno tako.
Torej, zdaj smo kazalci prevzemu Dodatni spomin, da smo v preteklosti
ni potrebno, ker prednost v matriki, seveda, da
vse je stikata, nazaj nazaj na hrbtu, ki
vam naključni dostop.
Ker samo z uporabo kvadratnega nosilec Zapis, ali bolj tehnično kazalec
aritmetika, zelo preprost dodatek, lahko dostopate do katere koli
elementi v enakem času.
In v resnici, da je nekako namiguje na še cena, ki smo si plačal z
povezani seznam.
>> Kaj se zgodi, da v času poteka nekaj podobnega Search, če želim
našli nekaj vrednosti in notranjost v povezanem seznamu?
Kaj mi teče čas postali?
Big O n.
Če je to urejeno za?
Kaj pa, če je struktura podatkov razporejene?
Lahko naredim bolje kot velika O n za iskanje?
Ne, ker v najslabšem primeru bi lahko bilo zelo dobro rešiti, število
iščete lahko velik.
Morda je številka 100, ki se lahko zgodi, da bo vse
Tako na koncu.
In zato, ker lahko le dostop povezano Seznam v tem izvajanju, ki jih
način svojega prvega vozlišča, si Še vedno nekako od sreče.
Moraš prečkala celotno stvar od prve do zadnje, da bi našli
da je velika vrednost kot 100..
Ali ugotoviti, če je to sploh ne obstaja.
>> Torej ne moremo storiti kaj algoritem v podatkovnem struktura, ki je videti takole?
Tega ne moremo narediti binarno iskanje, saj binarno iskanje potrebno, da smo imeli
random access.
Mi lahko samo preskok od lokacije do mesto brez nadaljnje
ti krušnih drobtin v obliki vseh teh kazalcev.
>> Zdaj, kako smo izvajati to?
No, če gremo na zaslonu tukaj, če bomo lahko hitro reimplement te podatke
strukturo -
moj rokopis še ni vse, da je super tukaj, ampak bomo poskušali.
Torej typedef struct, in kaj sem želite poklicati to stvar tukaj gor?
Vozlišče.
Tako da bom naju začel.
In zdaj, kaj mora biti znotraj Struktura podatkov za to posamezno
povezani seznam?
Koliko polja?
>> Torej dva.
Ena je zelo enostavno.
Torej, int n.
In lahko rečemo n karkoli hočemo, vendar mora biti int, če smo
izvajanje povezan seznam za ints.
In kaj zdaj počne drugega polja morajo biti?
Struct vozlišče *.
Torej, če naredim struct vozlišče *, potem pa sem To lahko pokličete tudi kar hočem,
ampak samo, da je jasno, bom poklicala je naslednji korak, saj smo počeli.
In potem bom zaprem zavite oklepaje.
>> In zdaj, kot zadnjič, Sem dal vozlišče tukaj.
Ampak, če sem to razglasitvi je kot vozlišče, zakaj se sploh trudim, da tako
verbose tukaj razglasitvi Struct vozlišče * naslednji, v nasprotju
na samo vozlišče * naslednji?
Ja?
>> PUBLIKA: [neslišno].
>> DAVID Malan: Točno tako.
Točno tako.
Ker C res vas popelje dobesedno in vidi le opredelitev vozlišča
Tako sem dol, ne smeš Če ga želite videti tukaj.
Torej imamo te vrste preemptive Izjava tukaj, ki je sicer
bolj verbose.
Struct vozlišča, kar pomeni, da sedaj lahko dostopate do
znotraj strukture podatkov.
>> In stran, ker je to postane malo bolj subjektivna zdaj,
zvezda lahko tehnično iti tukaj, da lahko gredo tu, lahko pa
celo iti v sredini.
Sprejeli smo v slogu priročnika za Tečaj, konvencija dajanje
zvezda tik podatkov vrste, ki je v tem primeru
bi struct vozlišče.
Ampak uresničiti v veliko učbenikov in spletne reference, boste morda celo
ga vidimo na drugi strani.
Ampak samo zavedati, da bo tako dejansko delo in bi morali biti zgolj
dosledna.
>> Vse je v redu.
Tako da je bila naša izjava od struct vozlišča.
Ampak potem smo začeli delaš več prefinjene stvari.
Na primer, smo se odločili, da uvedejo nekaj podobnega hash tabelo.
Torej, tukaj je razpršena tabela velikosti n, indeksirane od 0 na vrhu levo do n
minus 1 na dnu levo.
To bi lahko hash miza za karkoli.
Ampak kaj vrste stvari nismo govorili o uporabi razpršene tabele za?
Shranjevanje kaj?
>> Imena.
Mi lahko storite imena, kot so sva zadnjič.
In res, lahko shranite ničesar.
In bomo to spet videli v PHP in JavaScript.
Razpršene tabele je lepo nekakšen švicarski Nož, ki vam omogoča, da shranite
precej karkoli hočeš v notranjosti je s povezovanjem ključe z vrednostmi.
Tipke z vrednostmi.
>> Zdaj v tem preprostem primeru, naša Tipke so samo številke.
Mi izvajanje hash miza kot niz.
In tako so tipke 0, 1, 2, in tako naprej.
In tako mi, kot ljudje, odločila zadnja teden, da veš kaj, če smo
bo trgovina imen, kaj je samo samovoljno, ampak precej razumno,
Predvidevam, da Alice, ime, bo samo indeksirane v 0.
Bob, ime B, bo indeksirana v 1, in tako naprej.
Tako smo imeli preslikavo med vhodi, ki so nizi in razpršitve
Mesta, ki so številke.
>> Tako se ta postopek splošno znana kot hash funkcija, in lahko resnično
je v kodi izvajati.
Če bi želel izvajati funkcijo razpršitve da počne točno to, kar smo
pravkar opisal v zadnjem času, morda sem razglasi funkcijo, ki bo, kot je
vhod na primer -
in dajmo to narediti na tem Zaslon tukaj.
Če bi želel izvajati hašiš funkcijo, bi lahko rekel
kaj takega.
>> To se dogaja, da se vrnete int.
To se dogaja, da se imenuje hašiš, in to je bodo sprejeti kot argument
niz, ali smo lahko bolj pravilno zdaj, in pravijo, char *, bomo pa s poklicati.
In potem vse to funkcijo mora storiti, na koncu se vrne int.
Zdaj, kako to počne, da bi lahko Ne bodi tako jasna.
Jaz grem za izvajanje tega brez Oblika preverjanja napake zdaj.
Grem na slepo reči, vrnitev vse, kar je v nosilcem S 0, minus,
recimo, kapital podpičjem.
>> Popolnoma zlomljen.
To ni popoln, saj eno, kaj pa če je ničen?
Slabe stvari se bo zgodilo.
Dva, kaj če prva črka v tem Ime ni začetnico?
To ne bo obrniti iz vrtin.
Morda bi bilo male črke ali ne, pismo sploh.
Torej povsem dovolj prostora za izboljšave tukaj ampak to je osnovna ideja.
>> Kaj smo ustno opisal zadnji teden samo proces kartiranje Alice v
0 in Bob 1, se lahko izrazi Vsekakor bolj formulaically kot C
deluje tukaj.
Je znova poklical hašiš, je niz kot vložek, nato pa nekako ne nekaj
s tem input za proizvodnjo izhod.
Ni za razliko od naše črne opis box da smo dolgo storili.
Ne vem, kako bi to lahko bilo delajo pod pokrovom.
>> Problematičnega set 6, enega izmed izzivov je za vas, da odloči, kaj
bo vaš hash funkcija je?
Kaj se dogaja, da se notranjost da črna polje, in verjetno, da bo
malo bolj zanimivo, kot je ta, in vsekakor bolj nagnjeni k napakam
preverjanje, kot to predvsem izvajanje.
>> Vendar težave lahko nastopijo, kajne?
Če imamo podatkovno strukturo, kot je to ena, kar je eden od problemov
lahko vodijo v daljšem časovnem obdobju, kot ga vstavite več imen v
razpršene tabele?
Dobiš trčenja, kajne?
Kaj pa, če imate Alice in Arona, dve osebi, katerih imena se je zgodilo
za začetek?
To Zastavlja se vprašanje, kjer ste dal drugo takšno ime?
>> No, morda naivno pravkar dal kjer Bob pripada, potem pa je Bob
vrsta zajebali, če boste poskušali vstavite svoje ime zraven in
ni prostora za njega.
Tako da boste morda dal Boba, kjer je Charlie, in si lahko predstavljate to zelo hitro
decentralizacijo v malo nered.
Nekaj ​​linearno na koncu, kjer ste samo treba iskati celotno stvar
išče Alice in Bob ali Aaron ali Charlie.
>> Torej, namesto da smo predlagali, namesto samo linearno sondiranje za odprte prostore
in plopping imena Tam smo Predlog Ljubitelj pristop.
Hash tabela izvajajo še z matrika indeksov, vendar podatkovni tip
ti indeksi zdaj so bili kazalci.
Kazalci na kaj?
Kazalci, povezanih seznamov.
>> Ker opozarjata, da je povezani seznam res samo kazalec na vozlišče in
vozlišče ima naslednje polje, in da vozlišča Ima naslednje polje, in tako naprej.
Tako lahko sedaj razmišljati o tem polju na Leva stran od razpršilne tabele kot
vodi v povezano seznamu.
Prednost, ki je, če dobiš trčenje med Alice in Aronu
kaj storiti z Druga taka oseba?
Pravkar ste mu priložite ali ji Konec ali celo začetek
tega povezanega seznama.
>> In pravzaprav, kaj je samo testenin preko da za sekundo.
Kjer bi bila najbolj smiselna?
Če sem vstavil Alice in ona pristane na prvo mesto, potem pa skušam
vstaviti ime Aronovi, in tam Očitno trčenje, naj dam
ga v začetku iz povezanega seznama?
To je v tistem prvem mestu, ali na koncu?
>> PUBLIKA: [neslišno].
>> DAVID Malan: OK.
Slišal sem, začenja.
Zakaj na začetku?
>> PUBLIKA: [neslišno].
>> DAVID Malan: OK.
To je po abecedi, tako da je lepo.
To je dobra lastnost.
To mi bo prihranilo nekaj časa potencialno.
To ne bo pustila narediti binarno iskanje, vendar sem bi vsaj lahko izbruhnejo
iz zanke, če se zavedam, no, jaz sem pot preteklosti so Aaron bi bilo v ta
razporejene seznam povezano.
Nimam izgubljati svoj čas iščejo vse do konca.
Tako da je razumno.
Zakaj bi si želeli, da vstavite trka na ime
začetek seznama?
Kaj je to?
>> PUBLIKA: [neslišno].
>> DAVID Malan: To lahko traja dolgo časa da se na koncu seznama.
In v resnici, daljša.
Več imen, ki jih vstavite začnete z, več, da
veriga bo dobil.
Več vezana Seznam bo dobil.
Torej ste res samo zapravljaš svoj čas.
Morda ste bolje ohranja konstantna čas vstavitve, velik O od 1,
z vedno dajanje trka na ime začetek povezano seznama
in ne skrbi toliko, o razvrščanju.
>> Kaj je najboljši odgovor?
To je jasno.
Nekako je odvisno, kaj distribucija, kaj vzorec
imen vstavljate.
To ni nujno Očiten odgovor.
Ampak tukaj, še enkrat, je Oblikovanje priložnost.
>> Tako smo nato pogledal na to stvar, ki je res druga velika priložnost
za p-set 6.
In zavedaš, če tega še niste storili, Zamyla potopi v oboje, zgoščevalne
mize in poizkusih podrobneje.
In video potopis vgrajeni v p-set spec.
To je Trie -
T-R-I-E. In kaj je bilo zanimivo to je bil, da čas teče
o iskanju imena, kot so Maxwell Zadnjič, ko je bil velik O česa?
Kaj je to?
>> PUBLIKA: število črk.
>> DAVID Malan: Število črk.
Slišal sem dve stvari.
Število pisem in konstantno časa.
Torej gremo s tem prvi.
Število črkami.
No, ta struktura podatkov, odpoklic, je kot drevo, družinsko drevo, vsak od
katerih vozlišča sestavljajo nizi.
In ti nizi so kazalci druga takšna vozlišča ali drugih kot
polja v drevesu.
>> Torej, če smo želeli ugotoviti, nato ali je Maxwell tukaj, jaz bi šel
do prvega niza, na sam vrh drevo, tako imenovani root vrh
Trie in sledite m kazalec, Nato kazalec, potem x,
w, e, l, l.
In potem, ko sem videl nekaj posebnega simbola tukaj označen kot trikotnik.
V kodi boste videli, predlagamo, da izvaja kot bool, samo rekel ja
ali ne, beseda ustavi tukaj.
>> No, ko smo šli na M-A-X-W-E-L-L, počuti kot sedem, morda
osem, če gremo eno mimo njega, osem koraki, da bi našli Maxwell.
Ali pa recimo ji K. pokličite Toda spomnimo zadnje Tokrat sem trdil, da če obstaja
realno največja dolžina na beseda, kot je 40-nekaj-ak znakov,
maksimalna dolžina pomeni konstanta.
Torej res, ja, to je tehnično veliki O z dne 8. ali 7, ali res veliki O iz K. But
če je končna kapa o tem, kaj K lahko, da je konstantna.
In tako je velik O od 1 v konec dneva.
>> Ne v resničnem svetu.
Ne, ko ste dejansko začnete gledal ura kot delovanje vašega programa.
To je absolutno bo nekoliko počasneje kot resnično konstanten
Čas z enim korakom.
To se dogaja, da je sedem ali osem korakov, pa še to je veliko, veliko bolje
kot algoritem kot veliki O n tem je odvisna od velikosti, kaj je v
struktura podatkov.
>> Obvestilo glavo tu lahko vstavite milijon imen v tem
podatkovne strukture, ampak koliko več korakov se dogaja, da nas bo najti
Maxwell v tem primeru?
Jih ni.
On je nespremenjena.
In do sedaj, ne verjamem, da smo videli Primer podatkovno strukturo ali
Algoritem, ki je bila v celoti vpliva zunanjih
vedenja, kot je ta.
Ampak to ne more biti neverjetno.
To ne more biti edina rešitev za p-set
>> In to ni.
To ni nujno podatkov Struktura morate gravitirajo,
ker je tako kot hash tabele, kompromis.
Kakšna je cena, ki jo plača tukaj?
Spomin.
Mislim, da je to grozna količino pomnilnika.
In ne moreš kar vidim tukaj, ker avtor te slike
Očitno okrnjena vsi nizi, in ne bomo videli veliko je in
B-jev in C ter Q in Y-ov in Z je v teh nizi.
Ampak oni so tam.
>> Vsaka od teh vozlišč je cela vrsta nekaterih 26 ali več bajtov, v vsaki
kar predstavlja pismo.
27 v našem primeru, tako da se lahko podpre opuščaji na problem nizu.
Torej je to podatkovna struktura je res, res gosto in široko.
In da sam morda na koncu upočasnjuje stvari navzdol, ali vsaj stanejo
Veliko več prostora.
Ampak spet, lahko črpamo primerjave tukaj.
>> Spomnimo se nekaj časa nazaj, smo dosegli veliko bolj razburljivo tekmovanje v teku časa s sortiranjem
ko smo uporabi zlivanjem, ampak cena smo plačali za doseganje n log n za spajanje
sortiranje zahteva, da smo preživeli več kaj sredstev?
Več prostora.
Potrebovali smo sekundarni array kopiranje ljudi v, tako kot
smo tukaj na odru.
Torej, še enkrat, ni jasnih zmagovalcev, ampak samo subjektivna zasnova
Odločitve je treba opraviti.
>> Vse je v redu.
Torej, kaj pa je to?
Vsakdo, ki priznavajo D-Hall?
OK.
Torej tri od nas.
Mather House.
Torej, to je za jedilnico Mather je.
Stavim, da so vsi jedilnici imajo skladovnice pladnjev, kot je ta.
In to je pravzaprav predstavnik nečesa, kar smo jih
očitno že videli.
Poklicali smo ga dobesedno kup.
In kup, v smislu vašega računalnika spomin, je, če gre podatki
medtem ko so funkcije se imenuje.
>> Na primer, kakšne stvari gredo na stack v zvezi z
Postavitev spomin smo razpravljali V zadnjih tednih?
Kaj je to?
>> PUBLIKA: Klici funkcij.
>> DAVID Malan: Žal mi je.
>> PUBLIKA: Klici funkcij.
>> DAVID Malan: Klici funkcij, vendar Natančneje, katero je znotraj vsakega
te okvirje?
Katere vrste stvari?
Ja.
Tako lokalne spremenljivke.
Kadarkoli smo potrebovali nekaj lokalno shranjevanje, kot argument, ali int I, ali int
temp, ali karkoli lokalnih spremenljivka, smo bili
dajanje da na sklad.
In mi je kup pokličete, ker te ideje plastenje.
Nekako tekmah z realnostjo, Pogodbe koncept.
>> Vendar pa se izkaže, da sklad lahko tudi treba obravnavati kot strukturo podatkov
Alternativa matriko, alternativa v povezano seznamu.
Nekaj ​​konceptualno bolj zanimivo da lahko še vedno
izvaja z uporabo enega od tistih stvari, ampak to je drugačen tip
podatkovna struktura podpira, res, le dve operacije.
Lahko pa dodate na Ljubitelj funkcij, kot ti.
Ampak to so osnove -
potiskanje in pop.
>> In ideja z dimnika je, da če sem je tu, z ali brez Annenberg
vedoč, pladenj od soseda s številko 9 na njem.
Torej, samo int.
In hočem, da potisne na podatkih struktura, ki je trenutno prazna.
Razmislite o tem na dnu dimnika.
Jaz bi potisnite to številko 9 na kup, in zdaj je tam.
>> Ampak zanimiva stvar dimnika je, da če bi zdaj rad potiskanje
nekatere druge vrednosti, kot so 17 in porinem to na kupu, bom naredil
samo intuitivno stvar, grem da bi ga tam, kjer smo ljudje
bi se nagiba k temu, da dajo na vrhu.
Ampak kaj je zanimivo zdaj je, kako pridem ob 9h?
Veš, jaz ne bi nekaj truda.
>> Torej, kaj je zanimivo stack, ki so po svoji zasnovi,
to je podatkovna struktura LIFO.
Neumno način opisovanja zadnji noter, prvi ven.
Torej, zadnja številka v V tem času je bilo 17.
Torej, če želim, da pop nekaj off iz dimnika, je lahko le 17.
Torej je obvezna red Operacije tukaj, kjer je zadnji element
v mora biti prva izpadla.
Zato kratica, LIFO.
>> Torej, zakaj bi bilo to koristno?
So njihovi konteksti, v kateri ste jo želijo podatkovno strukturo, kot je ta?
No, to je gotovo koristno notranjost računalnika.
Torej operacijski sistemi jasno uporabljajo to vrsta podatkovne strukture za kupe.
Bomo videli tudi isto idejo ko gre za spletne strani.
Torej ta teden in naslednji teden in naprej, in kot ste začeti izvajati spletu
Strani v jeziku, ki se imenuje HTML, lahko dejansko uporabljajo podatkovne strukture, kot
to, da ugotovi, če stran je pravilno oblikovano.
Ker bomo videli vse spletne strani, sledite neke vrste hierarhijo, zamik
da bo ob koncu dneva, se drevesna struktura pod pokrovom.
Torej, več o tem v samo nekaj.
>> Ampak za zdaj, kaj je predlagala za Trenutek, kako bi lahko šel okoli
predstavlja, kaj stack?
Dovolite mi, da predlagam, da izvajajo sklad s kodo, kot je ta.
Torej sklad bo imel notri Dve stvari, matrike, ki se imenuje pladnji,
samo, da je v skladu z demo.
In vsaka od postavk v tej matriki se bo tip int.
In zmogljivosti, je verjetno, kaj?
Ker še nikoli nisem napisal Celotna definicija tukaj.
>> To je verjetno največji velikost matrike.
In to je verjetno deklariran kot ostra določiti na vrhu datoteke, nekateri
nekako konstantna kot je vsebovano v Zgolj kapitalizacija.
Torej nekje zmogljivost je opredeljena kot največjo možno velikost.
Medtem, znotraj strukture podatkov znan kot dimnik tam bo
je celo samo znan preprosto kot velikosti.
>> Torej, če bi bil jaz, da predstavlja ta sedaj slikovno, pa domnevam, da je to
celoti črna skrinjica predstavlja moj kup.
Znotraj tega je dve spremenljivki.
Torej bom pripraviti Prva je velikost.
In druga bom pripraviti kot niz.
>> Ampak samo, da se stvari urejene, običajno bi rišem matriko kot
to je pa res super če ustrezajo realnosti, ali
ujemajo z duševno model.
Naj namesto sestaviti niz navpično, kar je prav, še enkrat,
umetnikova izročitev.
Sploh ni pomembno, kakšna je je pod pokrovom.
In bomo rekli, da je privzeto kapaciteta se bo tri.
Torej bo to mesto 0, to bo mesto 1, to
bo lokacija 2.
>> Če sem podkupil s stres žogo, bi nekdo rad prišel gor in teče
vkrcati tukaj za trenutek?
OK, prvič videl roko.
Pridi gor.
Vse je v redu.
Torej menim, da je Steven.
Pridi gor.
Vse je v redu.
>> Recimo, zdaj smo nazaj na začetno država na svetu, kjer sem
Pravkar prijavljeni kup, in to je bo zmogljivost tri.
Toda velikost še ni bila ugotovljena.
Še ni bila določena pladnji.
Torej nekaj vprašanj prvi.
In naj ti dam mikrofon, tako da lahko sodelujejo bolj dejavno v tem.
>> Torej, kaj je v velikosti v tem trenutku V času, če je vse, kar sem naredil, je
prijavljeni kup z ena vrstica kode?
>> STEVEN: Ne veliko.
>> DAVID Malan: OK, ni veliko.
Ali vemo, kaj je v velikosti, Ne vemo, kaj je notri
te matrike tukaj?
>> STEVEN: Samo naključno kodo, kajne?
Samo -
>> DAVID Malan: Ja, bom je koda poklicati, ampak naključno -
>> STEVEN: Stvari.
>> DAVID Malan: Stvari, kot naključno
>> STEVEN: Biti.
>> DAVID Malan: Biti, kajne?
Torej smeti vrednosti, kajne?
Torej permutacije 0 in 1 je.
Ostanki prejšnjih običajih to pomnilnika.
In ne bomo zares vedeli, kaj se vrednosti so, tako da smo ponavadi narisati
kot vprašaji.
>> Torej prva stvar, ki smo menda dogaja, da želijo narediti tukaj -
in dovolite mi, da to področje v notranjosti od tod ime - pladnji.
Kaj bomo predvidoma inicializacijo velikosti, da če želimo
začnete uporabljati to kup?
>> STEVEN: Nik je pod 3.
>> DAVID Malan: Torej, v redu.
Da bo jasno, se razglasi zmogljivost drugje kot tri.
In to je tisto, kar sem uporabljal tudi dodeliti niz.
Velikost se dogaja, da se nanašajo na koliko Pladnji so trenutno na kupu.
>> STEVEN: Zero.
>> DAVID Malan: Torej bi bilo nič.
Tako da gredo naprej in z vsakim prstom, narisati nič v velikosti.
Vse je v redu.
Torej, zdaj, kaj je notri tega tukaj, ne vemo.
To so res samo smeti vrednosti.
Torej bi lahko potegnemo vprałaje, vendar Pustimo svet čisto za zdaj
saj ni važno kaj je tam.
Mi ne potrebujemo za inicializacijo niz z ničemer, kajti če vemo, da
velikost svežnju nič, dobro smo se ne sme gledaš kaj v
To polje je na vsak način ta trenutek.
>> Torej sedaj Predvidevam, da bom pritisnil številka 9 na kupu.
Kako bi morali posodobiti podatkovno strukturo notranjost te črne škatle?
Katere vrednote je treba spremeniti?
>> STEVEN: V -
velikost?
>> DAVID Malan: OK.
Velikost morala postati kaj?
>> STEVEN: Velikost bi bila ena.
>> DAVID Malan: OK.
Tako da bi postali ena velikost.
Torej, lahko to storite v nekaj načinov.
Naj ti dam, zdaj si Prst je radirka.
Vse je v redu.
Potem je zdaj vaš prst je čopič.
Vse je v redu.
In sedaj, kaj se mora spremeniti, Očitno je, da strukture podatkov?
>> STEVEN: Gremo od spodaj do 9.
>> DAVID Malan: 9.
V redu, dobro.
Torej še vedno ni važno, kaj je na lokaciji enega ali dva, ker so
Smetarska vrednosti, vendar ne smemo ukvarjati si tam, ker velikost je
nam povedali, da je samo prvi element je dejansko legitimno.
Torej, zdaj bom pritisnil 17 na seznamu.
Kaj se zgodi s to sliko?
>> STEVEN: Torej, velikost pa je šla na dva.
>> DAVID Malan: OK.
Ste radirka -
Ups.
Ste radirko.
>> STEVEN: radirka.
>> DAVID Malan: Ti si krtačo.
>> STEVEN: Čopič.
>> DAVID Malan: OK.
In kaj še?
>> STEVEN: In potem -
>> DAVID Malan: Zavzeli smo se 17.
>> STEVEN: Držimo 17 na vrhu, tako da -
>> DAVID Malan: V redu, dobro.
>> STEVEN: - ga spustite navzdol.
>> DAVID Malan V redu.
To je vse enostavno.
Ne bom vam pomagala ta čas.
Push 22.
>> STEVEN: Končano.
Postati radirko.
Jaz sem postal krtačo.
In potem sem dajanje 22.
>> DAVID Malan: 22.
Odlično.
Torej, še enkrat.
Zdaj sem bom za potiskanje na kupu 26.
>> STEVEN: Ooh.
Oh, bog.
Res si me preseneti.
>> DAVID Malan: Nisi videli prihajati?
>> STEVEN: Nisem videl tega prihaja.
Bi lahko ponovno začetna zmogljivost?
>> DAVID Malan: To je dobro vprašanje.
Torej smo nekako naslikal sebe v kotu tukaj.
Res ni dober ven Stevenom ker smo dodeljen ta niz
statično, tako rekoč, v notranjosti podatkovne strukture.
In smo v bistvu težko kodirane , da je velikost tri.
Torej, ne moremo zares prerazporediti.
>> Lahko bi, če bi šli nazaj, smo na novo pladnji, da je kazalec, ki
smo nato malloc za ročno spomin.
Ker če imamo spomin iz kup prek funkcije malloc smo
bi ga rešil.
Toda preden je osvoboditev, smo lahko prerazporediti večji kos pomnilnika,
posodabljanje kazalca, in tako naprej.
Toda za zdaj je to res najboljše, kar lahko naredimo.
Push in pop sta verjetno bo da so za signaliziranje nekatere napake.
>> Tako, na primer, naša izvedba za lahko potisni vrne bool ki
prej vrnil res, res, res.
Ampak četrti čas, da se dogaja, da imajo vrne false, npr.
Vse je v redu.
Zelo dobro opravljeno.
Čestitam.
Ste zaslužili svoj stres žogo danes.
>> [APLAVZ]
>> STEVEN: Hvala.
>> DAVID Malan: Hvala.
OK, tako da se zdi, da ni veliko za korak naprej, a ne?
Opisali smo to strukturo podatkov.
To je bil prepričljiv, kajne?
Operacijski sistemi všeč.
Očitno lahko spletni uporabi tega in druge aplikacije še vedno.
Ampak kaj neumnega omejitev, ki smo nazaj na neke v tednu dvema skrajnostma
kjer smo določena zaporedja velikosti.
>> Torej so dejansko nekaj načini, kako bi lahko rešili to.
Mi lahko dinamično dodeli niz, ni jih težko kodiranje, kot sem
narediti tukaj, ampak ponovno izjavlja to, samo, da bo jasno, kot je
kaj takega.
Int * pladnji, ne odločajo o zmogljivosti še ni.
Toda, ko sem razglasila Sveženj drugje v mojem kodo, sem lahko potem pokličete malloc,
dobite naslov na kos spomin, in sem lahko dodeli
da je naslov na pladnjih.
>> In potem, ker je samo kos spomin, sem lahko še naprej uporabljajo kvadrat
Nosilec zapis na običajen način.
Ker še enkrat, tam je nekako to funkcionalni ekvivalent nizi in
kose pomnilnika, ki prihajajo nazaj od funkcije malloc.
Mi lahko privoščite eno kot drugo uporabo kazalca aritmetično ali
oglati oklepaj zapis.
Tako da je en pristop.
>> Ampak kako pa bi lahko izvajanje tega enako strukturo podatkov, morda?
Kajne?
Počutim se, kot smo pravkar rešili to problem kot pred tednom dni.
Kaj je rešitev za ta problem da Steven naletela?
Torej povezani seznam, prav.
>> Če problem je, da smo slikarstva sami v kotu z dodelitvijo
vnaprej premalo pomnilnika, ki smo Nato so se nekako ukvarjajo z, no,
zakaj ne samo, da bi se izognili izda skupaj?
Zakaj ne razglasi pladnji za kazalec na vozlišče, ergo povezan seznam,
in nato preprosto dodelijo nove vozlišč vsakič Steven potrebno, da se prilega
število v podatkovno strukturo.
>> Tako da bi slika morala spremeniti.
To ne bo tako čista in kot enostavno, kot le niz treh ints.
Zdaj se dogaja, da se kazalec struct, in da struct bo
imajo int in naslednjo kazalec.
To bo vodilo preko tega kazalca drugi taki struct, da
še ena taka struct.
Torej slika bi dejansko dobili malo Messier.
In mi bi bili puščice vezavo vse skupaj.
>> Ampak to je v redu, kajne, saj smo videli, kako to storiti.
In ko boste dobili udobno izvedbenih nekaj podobnega povezano
Seznam, ki jih boste morali narediti, če odločijo za izvajanje razpršene tabele s
Veriženje za p-set 6, lahko jo uporabite kot gradnik, ali
sestavina ali nič rekoč Postopek, nekaj, kar si dal, vas
ustvarili svoj kos sestavljanke da lahko potem znova.
Torej kompromisi, vendar potencialne rešitve da smo dejansko videli.
>> Tako pogosto, vidiš to vsak leto ali dve, ko Apple za javnost
nekaj novega, in vsi nori ljudje line up zunaj Apple
shranite za nakup njihovega obrobnega nadgraditi na strojni opremi.
Jaz pravim, da je v redu, ker Jaz sem eden tistih ljudi.
Torej, kakšne podatkovne strukture lahko predstavlja to realnost?
>> No, pa je čakalna vrsta, linija pokličite.
Torej bi Britanci poimenovali po navadi Čakalna vrsta nekako, tako da je lepo ime.
In dve operaciji, da čakalne vrste podpirali bomo klic enqueue
Delovanje in dequeue delovanje, ki so podobne
duh push in pop.
To je nekako drugačna Konvencija, kaj kličeš ti.
Ampak enqueue kaj pomeni, da dodate ali vstaviti za podatkovno strukturo.
Da dequeue pomeni, da ga odstranite.
Toda medtem ko je bil kup podatkov LIFO struktura, čakalna vrsta je prvi,
Prvi od strukture podatkov.
>> Če ste prva oseba, ki je v skladu, da bo prva oseba, da bi dobili
iz linije in kupite novo napravo.
Predstavljajte si, kako razburjen bi ti ljudje če Apple namesto dimnika, za
na primer, za izvajanje picking up vaše nove igrače.
Torej čakalne vrste smisla, vsekakor, in lahko razmišljamo o vseh mogočih
aplikacije, verjetno, za čakalne vrste, še posebej, če hočeš pravičnost.
Torej, kako bi lahko izvajanje teh kot podatkovne strukture?
>> No, jaz predlagam, da bi lahko morajo to storiti v to smer.
Torej bom zdaj številk.
Tako da bomo naj bo enostavno in ne nujno govori v smislu pladnje.
Samo številke, ki ljudje gotten.
Kapaciteta se bo, še enkrat, določi Skupno število oseb, ki so lahko v
ta vrstica, kot tri ali koli druga vrednost.
>> Ampak jaz predlagam, da moram slediti ne le velikosti
Čakalna vrsta, koliko so stvari v njem.
Torej velikost je sedanja velikost, zmogljivost je največja velikost.
Samo enkrat, nomenklatura po dogovoru.
Zakaj potrebujemo dodatno int znotraj o vrsti slediti, kdo je v
sprednji strani linije?
Zakaj moram to narediti v tem primeru?
>> No, kako je to slika se bo spremenilo?
Verjetno lahko ponovno najbolj te slike.
Dovolite mi, da gredo naprej in izbrisati, kaj je tukaj.
Mi bomo to lahko nekoliko drugačno ime tu gor.
Znebimo od 17, znebimo od 9, dajmo se znebite 3.
In dodajmo še eno stvar.
Predlagam, da moram slediti sprednja stran, ki je prav
bo int tudi.
In bomo keep it simple.
Ne povezani seznam za zdaj.
>> Bomo priznati, da bomo Naleteli proti tej meji.
Ampak, kaj hočem videti zgodilo tokrat?
Tako, da sem šel naprej in prvi oseba, ki prihaja v liniji, in
to je številka 9.
Imamo stres kroglice.
Lahko kradem, recimo, dveh ali treh ljudi?
Ena, dva, tri?
Pridi gor.
Desno od spredaj, ker bomo, da je to eden hitro.
>> Vsak od vas se sedaj dogaja, da se ventilator fant v vrsti na Apple.
Ne boste prejemali Apple strojne opreme Na koncu tega, čeprav.
Vse je v redu.
Torej ste številko 9, si Številka 17, številka 22.
To so poljubne številke, kot študent ID-ji ali drugih malenkosti.
In čez nekaj trenutkov, začnimo za začetek dodajanja stvari.
In bom teči krovu tukaj ta čas.
>> Torej, v tem primeru, sem inicializiran spredaj, da -
Pravzaprav sploh ne zanima, kaj spredaj je, saj znaša nič.
Torej je to lahko tudi samo biti vprašaj.
To so vsi vprašljiva.
Torej, zdaj bomo začeli dejansko videli nekaj ljudje podloga v trgovini.
>> Torej, če številka 9, ti si prvi tam ob 5:00, pojdi naprej in line up,
ali večer prej.
OK.
Torej, zdaj 9 je tukaj.
Torej 9 na sprednjem seznama.
Tako da sem šel naprej in posodobiti Velikost tekočih podatkov
strukture, da ne bo več 0, ampak na 1.
Bom dal na 9. sprednja stran.
Dovolite mi, da gredo naprej in preklopite zaslon Tako lahko vidimo, mimo nas tukaj.
>> In zdaj kaj hočem dati na sprednji strani?
Grem slediti, da sprednji vrsti zdaj
je na mestu 0..
Ker, kaj se bo zgodilo naslednje?
No, recimo, zdaj sem enqueue 17 kot tudi.
Torej hop v skladu tam.
In spet, nekako vratih Trgovina je, da bo tu.
Torej, zdaj sem dodal 17.
In čeprav so ti fantje blokiranje zaslon, da je v redu,
saj ga lahko vidite tukaj gor.
Žal mi je.
>> PUBLIKA: Mi lahko premikate -
>> DAVID Malan: Ne, to je v redu.
To je velik tam gor.
Torej 17 je sedaj znotraj vrste.
Moram posodobiti, ki Polja sedaj, čeprav?
OK, vsekakor velikost.
Kaj pa spredaj?
OK, ne.
Spredaj se ne sme spremeniti, ker za razliko od dimnika, smo
želijo ohraniti pravičnost.
Torej, če 9 prišel prvi, želimo 9 da je treba najprej iz vrste
in v trgovini.
>> Dejstvo je, da vidimo, da je.
Preden smo vstaviti 22, dajmo iti naprej in dequeue 9.
Kaj ti je že ime?
>> PUBLIKA: Jake.
>> DAVID Malan: Jake se dogaja se dequeued zdaj.
Tako da boste dobili, da hodi v trgovino.
In se pretvarjamo, da trgovina je tam.
Torej, kaj zdaj potrebuje - dit-dit-dit!
Kaj se mora zgoditi zdaj?
Odločitev oblikovanje.
Torej ni slab nagon, ampak - Kako ti je ime?
>> PUBLIKA: David.
>> DAVID Malan: David.
Torej, kaj je David storil?
Poskušal je nekako popraviti podatke struktura in premik od svojega mesta
v Jakov nekdanji lokaciji.
In to je v redu, če smo pripravljeni sprejeti dejstvo, da so
podrobno izvajanje.
Ampak najprej, kaj je posodobiti podatke strukturo, preden to storimo.
Ker nisem všeč zamisel, da vse ljudje premikajo v tej vrstici.
>> To ni nič takega, če je David to počne z en korak, vendar še enkrat, mislim nazaj
ko smo imeli osem prostovoljcev na oder in smo naredili tako kot vstavljanje
razvrščanje, kjer smo morali začeti gibljejo vse okoli.
Da imam drago, kajne?
To me klečeplastvo o velikem O n, big O n znova na kvadrat.
To ni občutek, kot idealen rezultat.
>> Zato naj samo posodobiti to.
Torej velikost čakalne vrste ni več 2.
To je zdaj samo 1.
Ampak jaz lahko sedaj posodobite nekaj Nisem posodobiti prej,
sprednja stran.
Jaz lahko samo povem, je, da je lokacija 1?
Torej, zdaj imamo smeti vrednosti tukaj Smetarsko vrednost tukaj, in David v
Sredi te smeti.
Ampak struktura podatkov je nedotaknjena.
>> In v resnici sploh ne potrebujete spremenite Jaku nekdanjo številko
9, ker koga briga.
Nimam dovolj informacij, je zdaj v velikost, da vem, da je ena oseba v
To čakalne vrste.
In vem, da je ta oseba je na lokaciji 1, ne 0.
Jaz se ne upošteva.
Torej 1, kot tudi.
Torej podatkovna struktura je še vedno v redu.
>> No, kaj se zgodi potem?
Debatni enqueue -
Kako ti je ime?
>> PUBLIKA: Callen.
>> DAVID Malan: Callen.
Oglejmo enqueue je Callen, in 22 je zdaj na vrsti.
Torej, zdaj, kaj je tu spremenilo?
Spredaj je ne bo spremeniti, seveda.
Velikost se bo spremenilo, da je 2. znova.
In 22 konča tukaj, 9 je še vedno prisotna, ampak to je dejansko
Smetarsko vrednost zdaj.
To je samo ostanek Jake preteklosti.
>> Torej, zdaj, kaj se zgodi, če Jaz dequeue Davida?
Še zadnja operacija, dequeue David.
Mi lahko premika, ampak jaz predlagam lets ' storite tako malo dela, kot je mogoče.
Zdaj moja struktura podatkov gre nazaj v velikosti 2-1.
Ampak sprednji vrsti zdaj postane 2.
Ni mi treba spremeniti te številke samo še, ker oni
le smeti vrednosti.
>> Toda zdaj, kaj se zgodi?
Recimo, da sem enqueue sam, 26?
Počutim se, kot da spadam sem.
Torej sem se enqueued.
Tako sem nekako spadam sem.
In čeprav ti niso čisto cenim to vidno na odru,
ker imamo dovolj prostora, da bi moral ne bi stal tukaj, zakaj?
>> PUBLIKA: Ti si izven igrišča.
>> DAVID Malan: Right.
Sem izven igrišča.
Sem indeksira preko mejá te matrike.
Res bi morala biti v eni od tri možne lokacije.
Zdaj, ko je najbolj naravna iti?
Predlagam, da vzvodom teden en trik.
Operater mod, odstotek.
Ker sem tehnično znašal mesto 3, ampak jaz 3 mod zmogljivosti,
tako 3, znak za odstotek, 3 -
kapaciteta je 3.
Kaj je to?
Kaj je ostalo pri si delimo 3 za 3?
0.
>> Tako, da me postavi so bili Jake je bil, kar je pravzaprav dobro.
Torej, zdaj je izvajanje to stvar, ki se dogaja, da
biti malo glavobol.
To je res samo ena vrstica glavobola, kode.
Ampak zdaj vsaj obstaja smeti Vrednost tu, vendar pa je dva
zakonite ints tukaj.
In trdim, da zdaj smo storili kaj moramo tako dolgo, dokler ne
smo spremenili, kaj Jake vrednost naj bi bila 26.
>> Zdaj imamo dovolj podatkov, še da se ohrani celovitost
te strukture podatkov.
Še vedno smo nekako od sreče, ko smo želite vstaviti štiri ali več skupaj
Elementi, ampak lahko bi vsaj precej učinkovita uporaba ta konstanta
čas, v resnici.
Nimam skrbeti za prestavljanje vsakdo, kot naklona Davidove bil.
>> Vsa vprašanja o skladih, ali je ta vrsta?
>> PUBLIKA: Je razlog, zakaj morate velikosti, tako da boste vedeli,
kjer je imela oseba?
>> DAVID Malan: Točno tako.
Moram vedeti, velikost matrike ker moram, kako natančno vedeti
mnogi od teh vrednosti so legitimne, in da najdem, kam
Naslednja oseba.
Točno tako.
Velikost je -
pravzaprav nismo posodobili to še ni.
Sam sem dodal na 26 let.
Velikost je sedaj, ne 1, vendar 2.
Torej, zdaj je to res mi pomaga najti glava seznama, ki ni 0, ne
1, vendar pa je 2.
Sprednja stran je dejansko število 22.
Ker je prišel v prvo, zato je treba dovoljeno v trgovini pred menoj,
čeprav vizualno stojim bližje trgovini.
>> Vse v redu?
Aplavz za te fante in jih bom pustil ven.
>> [APLAVZ]
>> DAVID Malan: Jaz bi pustil boste obdržali pladenj.
Smo lahko videli, kaj se zgodi, če hočeš, pa morda ne.
Vse je v redu.
Torej, kaj zdaj pa nam preostane?
No, naj predlagajo, da obstaja Nekaj ​​drugih podatkovne strukture smo lahko
začnete tako, da naše orodje kit, ki bo dejansko zelo, zelo pomembno, saj je
smo se potopite v spletnem stvari.
Ki je spet, ima nekakšno povezavo drevesom v obliki
nekaj, kar se imenuje DOM, dokument objektni model.
Ampak bomo videli več da je pred dolgo.
>> Dovolite mi, da predlagam definitionally, da smo pokličite drevo zdaj kaj znate, kot
bolj družinsko drevo, kjer si nekaj prednika na
Korenine drevesa.
Patriarhalna ali Matriarchs na samem vrhu drevesa.
Brez njihovega zakonca, v tem primeru.
Vendar imamo zdaj, kaj bomo klic otroci, ki so vozlišča, ki visi
off levi otroka ali desno otroka, puščice, kot je prikazano tukaj.
>> Z drugimi besedami, v podatkovno strukturo drevo v računalniku, drevo ima ničlo
ali več vozlišč.
Če ima vsaj eno vozlišča ki se imenuje koren.
To so stvari, ki vizualno potegnemo na vrhu.
In to vozlišče, kot katera koli druga vozlišča, lahko imeli nič, ena ali dve ali tri,
ali glede na število otrok Struktura podatkov podpira.
V tem primeru je koren, shranjevanje vrednost ena, ima dva otroka, 2 in 3,
Tako smo na splošno imenujemo 2 levo otrok in 3 pravico otrok.
>> Potem, ko smo dobili do 5, 6, in 7, 6 bi lahko imenovali srednji otrok.
Če imate štiri otroke, postane zmedeno.
Zato smo prenehali uporabljati to vrsto za bližnjico verbalno.
Ampak to je res samo družinsko drevo.
In listi tukaj so vozlišča, ki sami nimajo otrok.
So visi off dno drevesa.
>> Torej, kako bi lahko izvajala drevo, ki Ima le dva otroka, maksimalno?
Mi bomo to binarno drevo klic.
Bi spet pomeni dve, v tem tako, kot je z binarno.
Tako ima lahko nič, ena, ali dva otroka najvišja.
>> Bom predlagam, da izvajajo vozlišče Za te strukture z int n,
in potem dva kazalci, ena se imenuje levo, ena imenovana pravica.
Ampak to so samo lepo samovoljne konvencij.
In kaj je lepo zdaj, še posebej, če vrsta boril s konceptualno
rekurzija, ali misli, da ni bilo res rešitev za vse,
še posebej, če bi lahko zmanjka pomnilnika.
Zdaj, ko govorimo o podatkih strukture in algoritmi, ki omogočajo
nam prečkanje in manipulirati z njimi, Izkazalo se je, da je rekurzija vrne v
veliko bolj prepričljiv če ne lep način.
>> Torej, to predlagam, je izvajanje za funkcijo iskanje.
Glede na to, dva vhoda -
tako da mislim, da je to črno škatlo.
Glede na to, dva vhoda, n, int, in kazalec na drevo, kazalec
vozlišče, ali res koren drevesa, sem Trditev, da je to funkcija vrne
resnična ali neresnična, da je vrednost n je znotraj tega drevesa.
>> Kaj je v te črne skrinjice?
No, štiri podružnice.
Prvi pravkar preverja.
Če drevo je nična, samo vrne false.
Če ni vozel, ni n ni več, samo vrne false.
Če temu, n, vrednost iščete , da je manj kot drevo puščice n, in
samo, da bo jasno, kaj pomeni, ko Pišem drevo in nato puščico
zapis, n?
Točno tako.
To pomeni, da ciljne datoteke Kazalec se imenuje drevo.
Pojdi tja, nato pa dobil v notranjosti, ki vozlišče in dobila polje z imenom n.
In nato primerjati dejansko n, da je prešla v Search proti njej.
>> Torej, če je n manjša od vrednosti n V drevesu samega vozlišča, dobro,
Kaj to pomeni?
To ne pomeni nič, na prvi pogled.
Kajne?
Tako kot če imate niz Vrednosti, boste morda želeli uporabiti binarno
iskanje kot obliko razkoraka in vladaj.
Ampak kaj predpostavka pa moramo narediti za binarno iskanje za delo na vseh
v imeniku in prejšnji primeri?
>> Kako se urejeno.
Torej, kaj je natančnejše opredelitve drevesa Tu ni prav drevo, ki lahko
ima poljubno število otrok.
Ne samo binarno drevo, ki lahko ima 0, 1, 2 ali maksimalno.
Ampak kot dvojiškega drevesa, ali BST, ki je samo fancy način rekel
binarno drevo, tako da vsako vozlišče je levo otrok, če je prisoten, je
manj kot vozlišče.
Vsako vozlišče in pravica otrok, če je prisoten, je večja
kot vozlišče sama.
>> Torej, z drugimi besedami, če ste bili, da pripravijo drevo ven, vse številke so
skrbno uravnotežene, tako da, če imate 55 kot root, 33 more iti
na njegovi levi, ker je manj kot 55 let.
77 se lahko obrnejo na svoje pravice, ker to je več kot 55 let.
Toda zdaj opazil, enako opredelitev, to je rekurzivna definicija verbalno,
zaprositi za 33.
33 na levi Otrok mora biti manjša od njega, in 33 pravica otrok, 44, mora biti
večja od njega.
>> Torej je to binarno iskalno drevo, in I predlaga uporabo malo
rekurzija, bomo lahko sedaj najdete n.
Torej, če je n manj kot vrednost n, ki je trenutno vozlišče, jaz grem
naprej in punt, tako rekoč, in samo vrne kar je odgovor na
iskanje n o levo otrok drevesa.
Spet opazili, ta funkcija samo pričakuje, da bo vozlišče Zvezda,
kazalec na vozlišče.
Torej, zagotovo sem lahko samo naredi drevo puščica levo, ki bo vodila
mi drugo vozlišče.
Ampak kaj je to vozlišče?
>> No, glede na to izjavo, levo je samo kazalec, tako da le
pomeni, da sem prehod na funkcijo iskanja drugačen kazalec, in sicer
tista, ki predstavlja Moja leva otroka drevo.
Torej v tem primeru kazalec 33, če to je naš vložek vzorec Medtem, če
n je večja od vrednosti n na trenutno vozlišče v drevesu, potem pa sem
dogaja, da gredo naprej in punt v drugo Smer in samo reči, jaz ne
ve, če ta vrednost je n v drevesu vem pa, če je to, to je moja dol
Pravica podružnica, tako rekoč.
Torej, naj me pokliče rekurzivno iskanje, spet spustimo n, vendar gre v
kazalec na moji desni otroka.
>> Z drugimi besedami, če sem trenutno na 55 in iščem 99, vem, da je 99
je več kot 55 let, tako kot sem strgal tedni imenika nazaj in mi
šel desno, podobno smo šli tukaj.
In ne vem, če je na moji desni otrok, in to ne, 77 je tam, ampak
Vem, da je v tej smeri.
Zato sem poklical iskanje na moji desni otroka 77, in pustite iskanje razbrati iz
pa če je 99 v tem samovoljno Primer je dejansko tam.
>> Else, kaj je končni primeru?
Če drevo je nična, je en primer.
Če je n manj kot tok vozlišča vrednost je še en primer.
Če je n večji od toka vrednost vozlišča je tretji primer.
Kaj je četrti in zadnji primer?
Mislim, da smo iz primerov, kajne?
Zato mora biti, da je n v trenutno vozlišče, da sem naprej.
>> Torej, če sem iskal 55 let na tej točki v zgodbi, ki veje
Drevo bi spet res.
Torej, kaj je zanimivo, je, da smo pravzaprav, za razliko od preteklih tednih smo nekako
za dve bazne primerov.
In ti ne bi bilo treba Vse bo na vrhu.
Vrhu je osnovna ker če Drevo je nična, ni nič narediti.
Pravkar vrnil težko kodirane vrednost false.
>> Spodnji veja je nekako privzeto, pri čemer se, če smo preveriti
null, smo preverili, če je treba levo, vendar to ne bi smelo biti, ki smo jih
preveri, če bi bilo prav, vendar ne sme biti jasno, da mora biti
tam, kjer smo.
To je osnovni primer.
Torej je dve rekurzivni primeri je stisnjena v sredini.
Vendar bi jaz napisal to v poljubnem vrstnem redu.
Mislil sem, da je nekako zdelo naravno najprej preverite morebitne napake,
nato pa preverite v levo, nato pa preverite desno, nato Predvidevam, da ste na vozlišču
ste dejansko iščejo.
>> Torej, zakaj bi bilo to koristno?
Tako se izkaže -
in mi skočil na teaser tu se je v spletu.
Bomo začeli uporabljati ne programski jezik na prvi, ampak
označevalni jezik.
Pa tista, ki je označevalni jezik pisane v duhu programiranja
jezika, vendar pa ne dam sposobnost, da sami logično izraziti.
To samo vam daje možnost, da izraziti sebe strukturno.
>> Kam želite dati nekaj na strani, spletna stran?
Kakšno barvo želite, da bi ga?
Kaj velikost pisave hočeš narediti to?
Kaj besede, kajne dejansko želim na spletni strani?
Tako da je označevalni jezik.
Ampak potem bomo zelo hitro uvesti JavaScript, ki je polnopravni
programskega jezika.
Zelo podobno skladenjsko po videzu do C, vendar pa boste morali nekaj
lepo, močnejši, bolj uporabniku prijazne funkcije.
>> In ena od frustracij na to točka v semestru je, da bomo
Kmalu izvajati Speller v veliko manj vrstic kode, ki uporabljajo druge jezike
kot C sama po sebi dovoljuje, vendar razlog je bomo kmalu razumeli.
To bo prva tovrstna spletna stran.
To bo popolnoma underwhelming, Prva naredimo.
To bo preprosto reči, zdravo svet.
Ampak, če še nikoli niste videli prej, to je HTML
HyperText Markup Language.
>> Če greš v neke menija v Najbolj koli brskalnik, na kateri koli spletni strani na
internet, lahko vidite HTML da nekateri ljudje pisal
ustvariti to spletno stran.
In verjetno ne izgleda kot kratek ali kot lepo, kot je ta.
Vendar pa bo sledila vzorcu teh odprte konzole in poševnice in
črke in potencialno številke.
>> Mislila sem, da vam teaser o tem, kaj boste mogli storiti
po zaužitju CS50.
Naj grem na cs.harvard.edu / rob, naše lastne Rob Bowden je domača stran.
On to je za nas.
Tako da boste kmalu lahko storim.
In tudi, kaj ste slišali Zjutraj -
kaj ste slišali danes zjutraj -
>> [HAMSTER DANCE MUSIC]
>> - Boš lahko, da je to.
To nas čaka v sredo.
Vam bomo videli potem.
>> [HAMSTER DANCE MUSIC]
DAVID Malan: Na naslednjem CS50 -