>> SPEAKER 1: V redu, tako da smo nazaj.
Dobrodošli na CS50.
To je konec sedem teden.
Tako opozarjajo, da je zadnji čas, smo začeli gledaš nekoliko bolj prefinjene
podatkovne strukture.
Ker do zdaj smo imeli res na razpolago je to polje.
>> Toda preden bomo, da ne zavržemo niz vse to zanimivo, kar v resnici je
dejansko je, kaj so nekateri pluse te preproste podatkov
Struktura doslej?
Kaj je dobro na to?
Kolikor smo videli?
Kaj imaš?
Nič.
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Kaj je to?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Fiksna velikost.
OK, zakaj je fiksna velikost dobra, čeprav?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: OK, tako da je učinkovit pri Občutek, ki ga lahko namenijo
fiksna količina prostora, ki upajmo Ravno toliko,
prostora, kot želite.
Tako da bi se lahko popolnoma plus.
>> Kaj je še gor stran array?
Ja?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Vsi - žal?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Vsa polja v pomnilniku ali drug poleg drugega.
In to je koristno - zakaj?
To je čisto res.
Toda, kako izkoristiti to resnico?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Točno tako, lahko spremljate kjer je vse le s poznavanjem
en naslov, in sicer naslov prvi bajt ta kos pomnilnika.
Ali v primeru niza, naslov prve
char v tem nizu.
In od tam lahko najdemo konca niza.
Mi lahko našli drugega elementa, na Tretji element, in tako naprej.
>> In tako fancy način opisovanja, da značilnost je, da nam daje nizi
random access.
Samo z uporabo kvadratni oklepaj Zapis in številko, lahko skočite na
poseben element v matriki v enakem času, big O
enega, tako rekoč.
>> Vendar je bilo nekaj slabosti.
Kaj matrika ne naredi zelo enostavno?
Kaj ni dobro?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Kaj je to?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Širitev po velikosti.
Torej Slabosti matrike so ravno nasprotno od tega, kar
upsides so.
Torej, ena od slabosti je da je fiksno velikost.
Torej vam ne morem raste.
Lahko prerazporediti večji kos pomnilnik, nato pa stare elemente
v nov niz.
In potem brezplačno stara matrika, za primer z uporabo malloc ali podobno
Funkcija se imenuje realloc, ki prerazporeja spomin.
>> Realloc, kot prahi, poskuša, da vam pomnilnika, ki je poleg niza
da že imate.
Morda pa bi premakniti stvari okoli celoti.
Ampak na kratko, da je drago, kajne?
Ker če imate kos pomnilnika te velikosti, ampak res želim eno
te velikosti, in če želite ohraniti prvotnih elementov, ki ste jih
približno linearni čas, postopek kopiranja da se mora zgoditi od
stara array nova.
In realnost sprašuje deluje znova sistema in
Še enkrat lahko začnete velike kose pomnilnika stalo nekaj časa pa tudi.
Torej je tako blagoslov in prekletstvo v prikrivajo, dejstvo, da ti nizi
so fiksne velikosti.
Ampak, če bomo namesto tega uvesti nekaj kot je ta, ki smo poklicani povezano
Seznam smo dobili nekaj upsides in nekaj slabosti tudi tukaj.
>> Tako povezani seznam je preprosto podatkov struktura sestavljena iz konstrukti C v tem
Primer, kjer struct, odpoklic, je samo Posoda za en ali več specifičnih
Vrste spremenljivk.
V tem primeru, kaj storiti, podatkovne tipe Zdi se, da znotraj struct da
Zadnjič, ko smo poklicali vozlišče?
Vsaka od teh pravokotnika je vozlišče.
In vsak od majhnih pravokotnikov notri je podatkovni tip.
Katere vrste smo rekli so bili v ponedeljek?
Ja?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: spremenljiva in kazalec, ali natančneje, int, za n
in kazalec na dnu.
Oba tistih zgodi, da se 32 bitov, pri Vsaj na računalniku, kot je ta CS50
Aparata in tako oni sestavljen tudi v velikosti.
>> Torej, kaj uporabljate kazalec čeprav navidezno?
Zakaj dodati ta puščico zdaj, ko so bili nizi tako lep in čist in preprost?
Kaj je kazalec počne za nas v vsakem od teh vozlišč?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Točno tako.
To vam pove, kje je Naslednji ena.
Tako sem nekako uporabiti analogijo uporabljate nit nekako
nit teh vozlišč skupaj.
In to je točno tisto, kar počnemo s kazalci, saj je vsaka od teh
kose pomnilnika lahko ali pa tudi ne nedeljive, back to back to back
Notranjost RAM-a, ker vsakič, ko klic malloc rekel, daj mi dovolj
bajte za novo vozlišče, bi bilo tukaj ali pa bi bilo tukaj.
Morda bi bilo tukaj.
Enostavno ne vem.
>> Vendar z uporabo kazalcev v naslovih ti vozlišča, lahko šiva jih boste
skupaj na način, ki je videti vizualno kot seznam, tudi če so te stvari
Vse širijo po vsej vaši enega ali tvoji dve ali vaše štiri gigabajte RAM
znotraj svojega računalnika.
>> Tako slaba, potem pa, povezani seznam, kaj?
Kakšna je cena smo očitno plačuje?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Več prostora, kajne?
Smo v tem primeru podvojila količino prostora, ker smo šli
od 32 bitov za vsako vozlišče, za vsako int, tako da sedaj 64 bitov, ker moramo
vodi okoli kazalec kot dobro.
Boste dobili večjo učinkovitost, če je vaša struct je večji od te preproste stvari.
Če ste dejansko imajo študenta v notranjosti od katerih je nekaj vrvi
Ime in hiša, morda številka, morda nekaj drugih področjih v celoti.
>> Torej, če imate dovolj velik struct, potem pa stroški kazalca je
ni tak big deal.
To je malo kota primeru, da bomo shranjevanje kot preprosta primitivna
Notranjost povezane seznama.
Bistvo pa je enaka.
Ste zagotovo porabi več spomin, ampak ste dobili
prilagodljivost.
Ker zdaj, če želim dodati element na začetku tega seznama
Imam dodeliti novo vozlišče.
In moram samo posodobiti tistih Puščice nekako po samo premikanje
Nekaj ​​nasvetov okoli.
>> Če hočem nekaj vstavili v Sredi seznama, nimam za
potisnite vse prahi, kot smo to storili v preteklih tednov z našim prostovoljcem, ki
predstavlja matriko.
Jaz lahko samo dodeli novo vozlišče in potem pa samo točko puščice v
različne smeri, saj ne morajo ostati v dejanski
spomin res črta, kot sem pripraviti je tu na zaslonu.
>> In nenazadnje potem, če želite vstaviti Nekaj ​​konec seznama, je
še lažje.
To je neke vrste samovoljno zapisu ampak 34 je kazalec, ugibati.
Kakšna je vrednost njenega kazalca najbolj verjetno sestavljen nekako kot stari
Šola antena tam?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Verjetno je nična.
In res, da je ena avtorja zastopanje nična.
In to je nična, ker ste popolnoma morali vedeti, kje konec povezano
Seznam je, da ne boste obdržali naslednje in sledi in po puščici
do neke smeti vrednosti.
Tako bodo null pomenilo, da ni več vozlišč na desni strani številka 34,
v tem primeru.
>> Zato predlagamo, da se lahko izvajajo To vozlišče v kodi.
In smo videli te vrste sintakse prej.
Typedef samo opredeljuje novo vrsto za nas, nam daje sinonim všeč
niz je bil za char *.
V tem primeru, se dogaja, da nam skrajšan zapis, tako da struct vozlišče
lahko namesto tega samo zapišemo kot vozlišče, ki je veliko čistejši.
To je veliko manj zgovorni.
>> Znotraj vozlišča očitno int imenujemo n, in nato struct vozlišče *
kar pomeni natanko to, kar smo želeli puščice pomeni, kazalec na drugo
vozlišče točno isto vrsto podatkov.
In predlagam, da bi morali izvajati search funkcija, kot je ta, ki je na
prvi pogled se morda zdi malo zapleteno.
Ampak kaj je to v kontekstu vidim.
>> Naj grem več na napravi tukaj.
Dovolite mi, da odprejo datoteko z imenom Seznam nič pika h.
In da vsebuje samo definicijo smo zajeli Pravkar sem videla pred nekaj trenutki za te podatke
Tip se imenuje vozlišče.
Zato smo mu, da v dot h datoteki.
>> In kot prahi, čeprav je to Program, ki si nadeja je
ni vse tako zapleteno, da je dejansko Konvencija pri pisanju programa
dal stvari, kot so podatkovne tipe, vleči konstante včasih znotraj vašega
header datoteko in ne nujno vaša C datoteka, zagotovo, ko si
Programi dobili večje in večje, tako da veste, kje iskati tako za
dokumentacijo, v nekaterih primerih, ali za osnove, kot je ta, v
opredelitev neke vrste.
>> Če bi sedaj odprl seznam ničelno piko c, opazil nekaj stvari.
Vključuje nekaj header datoteke, večino od katerih smo videli prej.
Vključuje lastno glavo datoteke.
>> In kot praha, zato da je dvojna citati tukaj, v nasprotju s kotom
oklepaja na liniji, ki Bil sem tam izpostavil?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Ja, tako da je lokalna datoteka.
Torej, če je lokalna datoteka sami tukaj na liniji 15, na primer, uporabite
dvojne navednice namesto od kotne oklepaje.
>> Zdaj je to nekako zanimivo.
Obvestilo, da sem razglasila svetovna spremenljivka v tem programu na liniji 18
imenovan, ideja pa je to bo kazalec na prvi
vozlišče v mojem povezanem seznamu, in sem INITIALIZED na nič, ker sem
ni dodeljena vsako dejansko vozlišča samo še.
>> Torej to pomeni, slikovno, kar smo videli pred nekaj trenutki na sliki kot
da kazalec na daleč levo strani.
Torej sedaj, da kazalec nima puščico.
Namesto tega je samo nična.
Ampak to pomeni, kaj se bo naslov Prvo dejansko
vozlišče na tem seznamu.
Tako sem izvajali, je svetovna ker je, kot boste videli, vse to
Program se v življenju je izvajala povezani seznam za mene.
>> Zdaj imam nekaj prototipov tukaj.
Odločil sem se za izvajanje funkcij, kot so brisanje, vstavljanje, iskanje in
prečkanje -
zadnja kot le sprehod čez Seznam, tiskanje njene elemente.
In sedaj tukaj je moja glavna rutina.
In ne bomo porabili preveč časa ti, ker je to neke vrste, upajmo
star klobuk, ki ga zdaj.
>> Jaz bom naredil naslednje, , medtem ko uporabnik sodeluje.
Torej eno, bom za tiskanje iz tega menija.
In sem ga kot formatiran gladko, kot sem lahko.
Če uporabnik vnese v enem, kar pomeni, da hočejo nekaj izbrisati.
Če uporabnik vnese v dvoje, kar pomeni, da hočejo nekaj vstavili.
In tako naprej.
Bom nato pozval nato za ukaz.
In potem bom uporabila GetInt.
>> Torej je to res preprosta menuing vmesnik, kjer boste morali vnesti
število razporejanja v enem od teh ukazov.
In zdaj imam lepo čisto stikalo Izjava, da se dogaja, da vklopite
karkoli uporabnik vtipka
In če jih vnesli eno, bom pokličite izbrisati in break.
Če jih vnesli dva, bom pokličite vstavite in break.
>> In zdaj napove, sem dal vsak teh na isti liniji.
To je samo slogovna odločitev.
Po navadi smo videli nekaj kot je ta.
Ampak tako sem se odločil, odkrito povedano, moj program je bolj berljivo, saj
je bilo le štiri primere, za samo seznam, kot je ta.
Povsem zakonito uporabo slogu.
In bom naredil to tako dolgo, dokler Uporabnik še ni natipkan nič, kar sem
odločil, bo pomenilo, da želijo prenehati.
>> Torej, zdaj opazil, kaj sem boš naredil tukaj.
Grem osvoboditi seznam očitno.
Ampak več o tem čez nekaj trenutkov.
Poglejmo najprej zagnati ta program.
Naj bo večji terminal okno, pika seznam poševnica 0.
Jaz grem naprej in ga vstavite tipkanje dva, več kot 50 let, in zdaj
boste videli seznam je zdaj 50.
In moj tekst samo pomika gor malo.
Torej sedaj opazili, seznam vsebuje Številka 50.
>> Naredimo še en vložek, ki ga ob dveh.
Kaj je tip v številu kot eno.
Seznam je zdaj eden, ki mu sledi 50.
Torej to je samo tekstovni prikaz seznama.
In kaj je vstaviti eno večjo številko, kot je številko 42, ki je upajmo
bo na koncu v sredini, saj ta program v posamezne sorte je
elementi, saj jim vložki.
Torej tam jo imamo.
Super preprost program, ki bi lahko Popolnoma so uporabili matriko, ampak sem
zgodi, da se z uporabo seznama povezano samo zato, da sem lahko dinamično
rastejo in se skrči.
>> Torej, vzemimo si za iskanje, če sem zaženete ukaz tri, hočem poiskati
za, recimo, številko 43..
In nič ni bilo očitno pokazala, ker sem dobil nazaj nobenega odgovora.
Torej, naredimo to še enkrat.
Iskanje.
Poiščimo 50, ali pa gre za iskanje za 42, kar je lepo
malo subtilen pomen.
In sem našel smisel življenja tam.
Številka 42, če ne veste, sklic, ga Google.
Vse je v redu.
Torej, kaj je ta program naredil zame?
To je samo dovoli mi, da tako vstaviti daleč in iskanje elementov.
>> Dajmo hitro naprej, nato pa se to funkcijo smo pogledal
v ponedeljek, kot teaser.
Torej to funkcijo Trdim, išče element na seznamu najprej
ena, zaradi česar uporabnika in nato kliče GetInt, da bi dobili dejanski int
, ki ga želite poiskati.
>> Potem to obvestilo.
Grem, da ustvarite začasno spremenljivko v skladu 188. imenovano kazalec -
PTR -
Lahko bi jo imenovali ničesar.
In to je kazalec na vozlišče saj sem rekel vozlišče * tam.
In jaz sem inicializacijo, da je enaka prvi, tako da sem dejansko imajo moja
prst, tako rekoč na zelo Prvi element seznama.
Torej, če je moja desna roka tu PTR sem kaže na isto stvar, ki je prvi
pokrije.
>> Torej, zdaj nazaj v kodi, kaj se zgodi naslednje -
To je skupna paradigma, ko ponavljanjem nad strukturo kot
povezani seznam.
Jaz bom pa naredil naslednje kazalec ni enaka Torej null medtem
moj prst ne kaže na neki nična vrednost, če kazalec puščica je n enak n.
Bomo opazili, prvič, da je n tisto, uporabnik vnesli v na GetInts poklical tukaj.
>> In kazalec arrow n pomeni kaj?
No, če se vrnemo na sliko tukaj, če imam s prstom kaže na
da najprej vozlišče, ki vsebuje devet, v arrow bistvu pomeni, da gre za
vozlišče in zgrabi vrednost na lokaciji n, v tem primeru podatkovno polje imenovano n.
>> Kot prahi - in smo videli to nekaj tedni, ko je nekdo vprašal -
Ta besedna zveza je nova, vendar pa ne nam dajejo pooblastila, da
ni že.
Kakšna je bila ta izraz enakovreden uporabo dot zapis in zvezda par
tedni, ko smo olupljen nazaj ta sloj malo prezgodaj?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Točno tako, to je zvezda, in potem je bil zvezda dot n, z
oklepaje tukaj, ki je videti, odkrito povedano, mislim, da je veliko
bolj skrivnosten brati.
Ampak zvezda kazalec, kot vedno, sredstvo tja.
In ko si enkrat tam, kaj podatki Polje želite dostopati?
No uporabljate dot zapis za dostop Podatkovno polje konstrukti, in jaz
posebej želimo n.
>> Odkrito povedano, bi lahko dejali, to je samo težje brati.
To je težje, da se spomnimo, kjer Ne Oklepaji iti,
zvezda in vse to.
Torej svet sprejel nekaj skladenjsko sladkorja, tako rekoč.
Samo seksi način rekel, to ustreza, in
morda bolj intuitivno.
Če kazalec je namreč kazalec, arrow zapis pomeni iti tja in ugotovili
polje v tem primeru se imenuje n.
>> Torej, če se mi zdi, da vidite, kaj počnem.
Jaz preprosto natisniti, sem našel odstotka I, priklopom na vrednost za to notr.
Kličem spat za eno sekundo, samo da se pavze stvari na zaslonu
daje uporabniku drugi, da absorbira kaj se je zgodilo.
In potem sem prekinil.
V nasprotnem primeru, kaj naj storim?
Jaz posodobiti kazalec na enak kazalec puščico.
>> Torej, samo da bo jasno, to pomeni, da gredo tam, z mojo staro šolo zapis.
Torej, to samo pomeni, da gre za karkoli si gledala, ki je v zelo
Prvi primer je, da sem gledala struct z devetimi v njem.
Tako da sem se šla.
In potem pika zapis pomeni, dobili vrednost na naslednjo.
>> Ampak vrednost, čeprav je ta pripravljen kot ozek, je samo številka.
To je številčna naslov.
Torej je to ena vrstica kode, bodisi napisan tako, bolj nejasna
Tako ali tako, nekoliko intuitiven način, samo pomeni, da se premaknete roko
od prvega vozlišče naslednjega, in nato naslednjič, nato
Naslednji, in tako naprej.
>> Tako da ne bo spuščala v drugi izvedbe vstavljanje in brisanje
in prečkanje, prva dva ki so precej vključeni.
In mislim, da je zelo enostavno priti izgubljeni, ko to počne verbalno.
Toda, kaj lahko storimo tukaj poskušali ugotoviti, kako
najbolje, da to storite vizualno.
Ker bi rad predlagal, da če bomo želite vstaviti elemente v to
Obstoječi seznam, ki Ima pet elementov -
9, 17, 22, 26 in 33 -
če bi bili, da bo izvajanje tega v kodo, da moram razmisliti, kako iti
o tem.
>> In jaz bi predlagal ob baby korake s katerim sem v tem primeru pomeni, kaj so
možne scenarije, ki smo lahko naletite na splošno?
Pri izvajanju vložek za vezano Seznam je to le zgodi, da bo
Konkreten primer velikosti pet.
No, če želite vstaviti številko, želel povedati številko ena, in
vzdrževanje urejen red, kjer Očitno pa številka ena potrebujete
gre v tem konkretnem primeru?
Rad na začetku.
>> Ampak kaj je zanimivo je, da Če želite vstaviti eno v to
Seznam je treba kaj posebnega kazalec se očitno posodablja?
Prvi.
Tako bi lahko dejali, da je to prvi primer da bomo morda želeli razmisliti,
scenarij, ki vključuje vstavitvijo začetek seznama.
>> Poglejmo Prebirati off morda tako enostavno, ali celo lažje primeru, relativno gledano.
Recimo, da želite vstaviti Številka 35 v razvrščeni vrstnem redu.
To očitno spada tja.
Torej, kaj je kazalec očitno se dogaja, da je treba posodobiti v tem scenariju?
34 je kazalec postaja ni nič vendar naslov struct
ki vsebuje številko 35.
Tako da je zadeva dva.
Torej je že, da sem nekako kvantiziranja koliko dela imam jaz tukaj.
>> In končno, očitno srednji primer je zares, v sredini, če želim
vstavite nekaj kot recimo 23, ki gre med 23 in 26, vendar
Zdaj se stvari malo bolj vključeni, ker, kaj
treba spremeniti nasvetov?
Torej 22 mora seveda treba spremeniti ker ne morejo navesti 26. anymore.
On potrebuje, da kaže na novo vozlišče, ki Jaz bom moral dodeliti s klicem
malloc ali lahko enakovredni.
>> Potem pa sem tudi, da je potrebno novo vozlišče, 23 v tem primeru, da ima kazalec
kaže na koga?
26.
In tam dogaja, da se Vrstni red operacij tukaj.
Ker če naredim to neumno, in jaz na primer začetkom na začetku
Seznam, in moj cilj je, da vstavite 23.
In sem preveriti, ali to spada Tukaj, v bližini devetih?
Število
Ali to spada sem, poleg 17?
Število
Ali spada tu zraven 22?
Da.
>> Zdaj, če sem nor sem, in ne misleč to skozi, morda sem
dodeli svojo novo vozlišče za 23 let.
Jaz bi posodobili kazalec od vozlišče se imenuje 22, kar kaže
je na novo vozlišče.
In kaj potem moram posodobiti kazalec za novo enoto je bil?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Točno tako.
Kaže na 26 let.
Ampak Hudiča, če nisem že posodobiti 22 je kazalec na točko tega tipa, in
Zdaj imam sirotam, počitka seznama, tako rekoč.
Torej, vrstni red operacij tukaj se bo pomembno.
>> Če želite to narediti, da bi lahko kradejo, recimo, šest prostovoljcev.
In da vidimo, če nam tega ne more storiti vizualno namesto kode-pametno.
In imamo kak lep stres Žoge za vas danes.
V redu, kaj pa en, dva, v nazaj - na koncu tam.
tri, štiri, oba fantje na koncu.
In pet, šest.
Prepričan.
Pet in šest.
Vse je v redu in bomo prišli da vaju naslednjič.
Vse je v redu, pridi gor.
>> Vse je v redu, ker ste tukaj prvič, bi želeli, da je eden nerodno
V Google Glass tukaj?
V redu, torej, OK, steklo, Snemanje videa.
OK, ste na dobri poti.
>> Vse je v redu, tako da, če lahko vi pridite tukaj, sem vnaprej pripravljena
nekaj številk.
Vse je v redu, pridi sem.
In zakaj ne greš malo naprej v to smer.
In poglejmo, kako ti je ime, z Google Glass?
>> ŠTUDENT: Ben.
>> SPEAKER 1: Ben?
V redu, Ben, boste prvi, dobesedno.
Torej bomo poslali na koncu stopnje.
Vse je v redu, in ti je ime?
>> ŠTUDENT: Jason.
>> SPEAKER 1: Jason, OK boste bo številka devet.
Torej, če želite slediti Ben tak način.
>> ŠTUDENT: Jill.
>> SPEAKER 1: Jill, si bo 17, ki bi, če bi to več storiti
pametno, bi moral vpis na drugem koncu.
Ti pojdi tja.
22.
In vi ste?
>> ŠTUDENT: Mary.
>> SPEAKER 1: Mary, boste 22.
In tvoje ime?
>> ŠTUDENT: Chris.
>> SPEAKER 1: Chris, boste 26.
In potem na koncu.
>> ŠTUDENT: Diana.
>> SPEAKER 1: Diana, boste 34.
Tako da pridi sem.
>> Vse je v redu, tako da odlično razporejene naročite že.
In gremo naprej in to tako da bomo lahko res -
Ben si nekako iščejo ven v nikjer ni.
OK, tako da gremo naprej in prikazujejo to z rokami, tako kot sem bil, ravno,
kaj se dogaja.
Tako da gredo naprej in da sebi stopal ali dve med seboj.
In gredo naprej in točko z eno roko na Kdor morate biti obrnjena
temelji na tem.
In če ste null samo točko naravnost na tla.
V redu, dobro.
>> Torej, zdaj imamo povezan seznam, in dovolite mi, Predlagam, da bom imel vlogo
PTR, tako da ne bo motilo da bi se to okoli.
In potem - kdo neumen konvencija - lahko pokličete to, kar hočeš -
Predhodnik kazalec, PRED kazalec -
to je samo vzdevek smo dali v naša vzorčna koda za levico.
Po drugi strani, da bodo vodenje Spremljajte kdo je kdo v
po scenarije.
>> Torej predvidevam, prvič, rad bi odtrgal off da je prvi primer vstavljanje, pravijo
20, v seznamu.
Torej bom potreboval nekoga, ki bi poosebljajo številko 20 za nas.
Tako da moram malloc nekom iz občinstva.
Pridi gor.
Kako ti je ime?
>> ŠTUDENT: Brian.
>> SPEAKER 1: Brian, vse v redu, tako da mora biti vozlišče, ki vsebuje 20.
Vse je v redu, pridi sem.
In seveda, kjer Brian ne pripada?
Torej, v sredini - pravzaprav Čakaj malo.
To delamo v okvari.
Mi smo to kar veliko težje kot ga je treba na prvi.
OK, gremo na prostem Brian in realloc Brian kot pet.
>> OK, zdaj želimo vstaviti Brian kot pet.
Torej, pridi sem zraven Ben le za trenutek.
In lahko povem, predvidoma če ta zgodba se dogaja.
Ampak kaj je dobro premisliti o Vrstni red operacij.
In to je točno to vizualna da se dogaja, da line up
s to oznako vzorca.
Torej, tukaj sem PTR sprva kaže ni na Bena, per se, ampak ne glede na
cenimo je vsebuje, kar je v tem primeru je - kaj je spet ti je ime?
>> ŠTUDENT: Jason.
>> SPEAKER 1: Jason, tako da sta Ben in jaz kaže na Jasona v tem trenutku.
Torej, zdaj moram ugotoviti, kadar Brian pripada?
Torej, edina stvar, imam dostop do Zdaj je njegov podatek n.
Torej grem preveriti, se Brian manj kot Jasona?
Odgovor je res.
>> Torej, kaj je zdaj zgodilo, v pravilnem vrstnem redu?
Moram posodobiti, koliko nasvetov skupaj v tej zgodbi?
Kje je moja roka je še vedno kaže na Jason in roko - če želite
dvigni roko, kot so, nekako sem Ne vem, vprašaj.
V redu, dobro.
>> Vse je v redu, tako da boste imeli nekaj kandidatov.
Bodisi Ben ali jaz ali Brian ali Jason ali pa vsi ostali, ki
kazalci morali spremeniti?
Koliko skupaj?
>> OK, tako da dva.
Moj kazalec sploh ni pomembno več ker sem samo začasno.
Tako da je ta dva fanta, domnevno sta Ben in Brian.
Naj predlagam, da posodobite Ben, saj je on prvi.
Prvi element tega seznama Zdaj bo Brian.
Torej Ben točka na Briana.
OK, kaj zdaj?
>> Kdo opozoril na koga?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: OK, tako da ima Brian opozoriti na Jasona.
Ampak sem izgubil skladbo tega kazalca?
Ne vem, kje je Jason?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: jaz, ker sem začasna kazalec.
In verjetno so se nisem spremenil opozoriti na novo vozlišče.
Tako bomo lahko preprosto Brian točko V kdor sem gledala.
In sva končala.
Torej velja eno, vstavljanje na začetek seznama.
Obstajali sta dve ključni koraki.
Ena moramo posodobiti ben in nato imamo tudi posodobiti Brian.
In potem mi ni treba ukvarjati traipsing skozi preostanek
seznam, ker smo že našel mesto, ker je pripadal
levo prvega elementa.
>> V redu, torej precej enostavna.
V bistvu se počuti, kot da sva skoraj bi to preveč zapleteno.
Torej, kaj je zdaj drobovja off konec seznama, in videli, če
Kompleksnost začne.
Torej, če zdaj, jaz alloc iz občinstva.
Kdo rad igral 55?
Vse je v redu, sem prvič videl svojo roko.
Pridi gor.
Ja.
Kako ti je ime?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Habata.
OK, pridi gor.
Boste številka 55.
Tako da, seveda, pripadajo na koncu seznama.
Torej, kaj je Replay simulacijo z mano da PTR za trenutek.
Tako da sem jih prej opozoriti na karkoli Ben je obrnjena.
Mi smo tako kaže zdaj na Briana.
Torej 55 ne manj kot pet.
Torej bom sam posodablja z kaže na naslednji kazalec Brianovem, ki
Zdaj je seveda Jasona.
55 ni manjša od devet, tako da Bom posodobiti PTR.
Bom posodobiti PTR Jaz bom za posodobitev PTR.
In bom - hmm, kaj je ime?
>> ŠTUDENT: Diana.
>> SPEAKER 1: Diana je poudaril, seveda, na ničelno z levico.
Torej, če ne Habata dejansko očitno pripada?
Na levi strani, tukaj.
Torej, kako naj vem, da bi jo dal tukaj Mislim, da sem zamočil.
Ker tisto, kar je PTR umetnost ta trenutek?
Null.
Torej, čeprav, vizualno, ne moremo očitno videti vse te
Fantje tukaj na odru.
Sem ne hranijo spremljali prejšnja oseba na seznamu.
Nimam s prstom kaže ven, V tem primeru je vozlišče številka 34.
>> Torej, kaj je pravzaprav začetek tega konec.
Torej, zdaj sem dejansko ne potrebujejo, Druga lokalna spremenljivka.
In to je tisto, kar boste videli v Dejanski vzorec C kodo, kjer, kot sem šel,
ko sem posodobiti svojo desno roko na točko Jason, zato je ostalo Brian zadaj, jaz
bolje začeti z mojo levo roko posodobiti, kjer sem bil, da sem lahko grem
skozi ta seznam -
bolj nerodno kot sem nameraval Zdaj tukaj vizualno -
Jaz bom priti do konec seznama.
>> Ta kombinacija je še vedno nič, kar je precej neuporabna, razen da se nakaže
Jaz sem očitno na koncu seznama, ampak zdaj vsaj imam to
Predhodnik kazalec kaže tukaj, tako da kaj zdaj roke in kaj kazalci potrebujete
treba posodobiti?
Čigava roka hočeš preoblikovati prvi?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: OK, Diane.
Kam želite poudariti Levi kazalec Dianina na?
Na 55, verjetno, da smo tam vstavi.
In kje bi 55. kazalec iti?
Navzdol, kar je nično.
In moje roke, na tej točki, ne pomembno, ker so bili samo
začasne spremenljivke.
Torej, zdaj smo storili.
>> Torej dodatno kompleksnost tam - in to ni tako težko izvajati,
vendar potrebujemo sekundarne spremenljivke, da bi Preverite, preden sem premakniti svoj prav
roko, sem posodobiti vrednost moja leva roko, PRED kazalec v tem primeru, tako
da imam zadnjo kazalec slediti, kje sem bil.
Zdaj, kot prahi, če si to mislil skozi ta občutek, kot da je
malo siten, da morajo voditi Spremljajte ta leve roke.
>> Kaj bi druga rešitev tega problema so?
Če imaš za preoblikovanje podatkov Struktura govorimo
skozi prav zdaj?
Če se to nekako zdi malo siten, da imajo, recimo, dva kazalca
tekoč skozi seznam, kdo bi lahko so v idealnem svetu, ohranja
informacije, ki jih potrebujemo?
Ja?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Točno tako.
Pravica do tam je pravzaprav zanimivo Kalčki ideje.
In ta ideja prejšnjega kazalca, kaže na prejšnji element.
Kaj pa, če sem pooseblja da Notranjost seznamu samo?
In to se dogaja, da je težko predstavljati to brez vsega papirja
padejo na tla.
Recimo, da ti fantje uporabljajo tako rokami, da ima prejšnja
kazalec, in naslednji kazalec, s čimer izvedbenih kaj bomo klic dvakrat
povezani seznam.
Ki bi mi dovolite, da nekako previjanje, veliko lažje brez mene
programer, da bi predolgo sledenje ročno -
resnično ročno -
na to, kje sem bil prej na seznamu.
Tako da ne bo naredil.
Bomo keep it simple, ker je to dogaja, da pridejo po ceni, dvakrat
veliko prostora za napotke, Če želite še enega.
Ampak to je res pogosti podatkovna struktura znana kot
dvojno povezani seznam.
>> Naredimo končno primer tukaj in dal ti fantje iz njihove bede.
Torej malloc 20.
Pridi gor iz hodnika tam.
V redu, kako ti je ime?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Oprostite?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Demeron?
OK, pridi gor.
Si je 20.
Očitno si bodo spadajo med 17. in 22..
Naj se naučijo svojo lekcijo.
Jaz bom za začetek kazalec kaže na Briana.
In jaz bom moral svojo levo roko posodobi le Brian kot sem premakniti
Jason, preverjanje pa 20 manj kot devet?
Število
Je 20 manj kot 17?
Število
Je 20 manj kot 22?
Da.
Torej, kaj kazalci ali roke, je treba spremeniti kje ste zdaj kaže?
>> Tako da lahko naredimo 17 kaže na 20..
Tako, da je v redu.
Kje želimo poudariti kazalec zdaj?
Ob 22..
In vemo, kje je 22, še enkrat hvala po mojem začasno kazalcem.
Tako da smo v redu tam.
Torej zaradi tega začasno skladiščenje Sem redno spremljali, kje so vsi.
In sedaj lahko vizualno šel v katerih vam pripada, in zdaj moramo 1, 2, 3,
4, 5, 6, 7, 8, 9 stres kroglice, in aplavz za
ti fantje, če bi lahko.
Lepo opravljeno.
>> [APLAVZ]
>> SPEAKER 1: V redu.
In lahko vodijo kosov papirja kot spominki.
>> V redu, torej, verjemite mi, da je veliko lažje prehodili, da se z
ljudje, kot pa je z dejanskim kodo.
Ampak, kaj boste našli čez nekaj trenutkov Zdaj, je isti - oh, hvala.
Hvala -
je, da boste ugotovili, da iste podatke struktura, povezani seznam, lahko dejansko
uporabi kot sestavino še sofisticirane podatkovne strukture.
>> In zavedati tudi, da je tema tukaj je, da smo absolutno uvedli več
kompleksnost v izvajanju to algoritem.
Vstavljanje, in če smo šli skozi to, brisanje in iskanje, je malo
bolj zapletena, kot to je s paleto.
Vendar pa smo pridobili nekaj dinamiko.
Smo dobili prilagodljivo strukturo podatkov.
>> Ampak še enkrat, bomo plačali ceno ob nekaterih dodatno kompleksnost, tako v
njeno izvajanje.
In smo obupal naključni dostop.
In če sem iskren, tam ni nekaj lepih čiščenje diapozitiv ga lahko dam, da
pravi, tukaj je, zakaj povezani seznam je bolje kot matrike.
In ostati pri tem.
Ker je tema ponovno pojavila že zdaj, bolj pa v prihodnjih tednih, je
da ni nujno pravilen odgovor.
>> To je razlog, zakaj imamo ločeno os zasnove za problemskih sklopov.
To bo zelo konteksta ali želite uporabljati te podatke
struktura ali da ena, in bo odvisno, kaj je pomembno za vas v smislu
virov in kompleksnosti.
>> Ampak naj predlagajo, da idealne podatki struktura, sveti gral, bi bilo
nekaj, kar je konstanten čas, ne glede na to, koliko stvari je
znotraj njega, ne da bi bilo neverjetno, če Struktura podatkov je vrnilo odgovore na
konstantna čas.
Da.
Ta beseda je v velikem slovarju.
Ali ne, ta beseda ni.
Ali vsak tak problem obstaja.
No, da vidimo, če ne moremo vsaj narediti korak v smeri, da.
>> Dovolite mi, da predlaga novo strukturo podatkov, ki se lahko uporabljajo za različne stvari,
v tem primeru se imenuje razpršene tabele.
In tako smo pravzaprav nazaj pogledoval na polju, v tem primeru, in
nekoliko arbitrarno, sem to pripraviti hash tabelo kot matriko z nekakšno
dvodimenzionalna matrika -
oziroma je to tu upodobljen kot dva dimenzionalni array - ampak to je samo
matrika velikosti 26, tako da, če pokličite array, namizni nosilec
nič je pravokotnik na vrhu.
Tabela nosilec 25 je pravokotnik na dnu.
In to je, kako lahko narišem podatkov struktura, v kateri želim shraniti
ljudi, saj imena.
>> Torej, na primer, in ne bom sestaviti Celotna stvar tukaj v zgornjem delu, če sem
je ta niz, ki sem zdaj dogaja, da klic razpršene tabele, in to je še
lokacija nič.
To tukaj je lokacija ena, in tako naprej.
Trdim, da želim, da se ti podatki uporabijo struktura, zaradi razprave
Shranjevanje imen ljudi, Alice in Bob Charlie in druga taka imena.
Tako da mislim o tem sedaj začetkov , recimo, slovarja
z veliko besedami.
Se zgodi, da bodo imena v našem primeru tukaj.
In to je vse preveč Germane, morda, da izvajanje črkovalnik, kot smo
Morda za problem nastaviti šest.
>> Torej, če imamo niz skupni velikosti 26 tako, da je to 25. mesto
na dnu, in trdim, da je Alice Prva beseda v slovarju
Imena, ki jih želim vstaviti v RAM, v to strukturo podatkov, kjer so
instinkt vam pove, da je Alice Ime mora iti v tej matriki?
>> Imamo 26 možnosti.
Kadar želimo, da bi jo dali?
Mi ji želimo v razredu nič, kajne?
Za Alice, recimo, da nič.
In B bo ena in C bosta dve.
Torej bomo napisali Alice ime tu gor.
Če bomo nato vstavite Bob njegov Ime bo šel tukaj.
Charlie bo šel tukaj.
In tako dalje navzdol skozi ta struktura podatkov.
>> To je čudovito strukturo podatkov.
Zakaj?
No, kar je čas teka vstavite ime človeškega je v to
podatkovna struktura prav zdaj?
Glede na to, da je ta tabela izvaja, resnično, kot matriko.
No to je stalen čas.
To je zaradi enega.
Zakaj?
>> No, kako ugotoviti, kjer Alice pripada?
Gledaš črko njenega imena?
Prvi.
In lahko dobite tam, če je niz, ki ga pravkar gledamo na vrvico
Nosilec nič.
Torej Ničti značaja niza.
To je enostavno.
To smo storili v CRYPTO Prirejanje tedni.
In potem, ko veš, da Alice Pismo je kapital, lahko odštejemo
off 65 ali premoženja A sam, ki nam daje nič.
Tako zdaj vemo, da Alice pripada na lokaciji nič.
>> In glede na kazalec do teh podatkov struktura, neke vrste, kako dolgo
pa vzemi me, da bi našli lokacijo nič v matriki?
Samo en korak, prav je konstanten čas zaradi bralno smo
Predlagana je bila značilnost matrike.
Torej na kratko, poskušal ugotoviti, kaj se je indeks o je ime Alice, ki je v
V tem primeru, je, ali naj samo reševanje da nič, kjer B je eden in C
dva, kipec, ki izvajajo konstanten čas.
Pravkar sem moral pogledati na svojem prvem pismu, ugotoviti, kje je nič
array je tudi stalen čas.
Tako tehnično, da je kot dveh korakih zdaj.
Ampak to je še vedno konstantna.
Zato pravimo, da je velik O enega, tako da smo jih vstavi Alice v tej tabeli, v
konstantna čas.
>> Ampak seveda, jaz pa Naivno sem, kajne?
Kaj pa, če je Aaron v razredu?
Ali Alicia?
Ali katera koli druga imena, ki se začnejo z A. Kam gremo postaviti
da oseba, kajne?
Mislim, zdaj pa je samo tri ljudje na mizi, tako da morda smo
bi dal Aaron na lokaciji nič ena dva tri.
>> Prav, bi jaz dal tukaj.
Ampak potem, če bomo poskušali vstaviti Davida v ta seznam, kjer se David iti?
Sedaj naš sistem začne lomljenje dol, kajne?
Ker zdaj David konča tukaj če Aaron je pravzaprav tukaj.
In tako zdaj ves ta zamisel o čista struktura podatkov, ki nam daje
Časovna konstanta vstavljanja ni več konstanten čas, ker moram
preveri, oh, prekleto, nekdo je že V Alice lokaciji.
>> Dovolite mi, da sonda preostanek teh podatkov struktura, ki išče mesto, da dajo
nekdo kot ime Aronovo.
In tako, da preveč se začenja da se linearno časa.
Poleg tega, če želite takoj poiskati Aaron v tej strukturi podatkov, in
preveri, in ime Aronova ni tukaj.
Idealno bi bilo, bi si rekel Aronu ne strukture podatkov.
Ampak, če vam začeli delati prostor za Aaron treba, kjer je prišlo do D
ali E, da, v najslabšem primeru, morajo preveriti celotno strukturo podatkov, v
čemer je devolves v nekaj linearna velikosti tabele.
>> Torej vse v redu, bom to popraviti.
Problem je v tem, da sem imel 26 elementov v tem polju.
Dovolite mi, da jo spremeni.
Ops.
Dovolite mi, da jo spremeni tako, da namesto počutje velikost 26 v celoti, opazili dno
Indeks se bo spremenilo na n minus 1.
Če 26 je očitno premajhen za ljudi " Imena, saj je na tisoče
Imena svetu, kaj je samo da v 100 ali 1000 ali 10.000.
Reciva, namenijo veliko več prostora.
>> No, da ne padajo nujno verjetnost, da ne bomo imeli dva
ljudje z imeni, ki se začnejo z, in tako, da boš poskusil postaviti
Imena na lokaciji nič še.
Še vedno se dogaja, da trčijo, ki pomeni, da smo še vedno potrebujejo rešitev za povišanje
Alice in Aron in Alicia in drugo Imena se začnejo z A drugje.
Toda kako veliko težavo je to?
Kakšna je verjetnost, da boste imajo trčenja v podatkovnem
struktura, kot je ta?
>> No, naj me - se bomo vrnili na to vprašanje tukaj.
In poglej, kako bi lahko rešiti najprej.
Dovolite mi, dvigni ta predlog tukaj.
Kaj smo pravkar opisali, je algoritem, hevristična imenujemo linearna
sondiranje, pri čemer, če si se potrudil, da vstavite Nekaj ​​je tukaj v teh podatkov
strukture, ki se imenuje razpršene tabele, in ni prostora tam,
resnično sonda podatkovne strukture preverjanje, ali je to na voljo?
Je ta na voljo, je to na voljo?
Je to na voljo?
In ko končno je, da vstavite ime, ki ga je prvotno namenjen
drugje na tem mestu.
Ampak v najslabšem primeru, le mesto lahko zelo dno podatkov
struktura, zelo konec niza.
>> Torej linearni sondiranje, v najslabšem primeru, devolves v linearnem algoritmu, kjer
Aaron, če se zgodi, da se vstavi zadnji V tej strukturi podatkov, morda je
zadenejo ob tej prvi lokaciji, vendar nato pa na koncu z slabe sreče na koncu.
Torej to ni konstantna Čas sveti gral za nas.
Ta pristop vstavljanje elementov v struktura podatkov se imenuje hašiš
miza ne zdi, da je konstantna čas vsaj ne v splošnem primeru.
To lahko prenesejo v nekaj linearno.
>> Pa kaj, če bomo rešili trčenj Nekoliko drugače?
Torej, tukaj je bolj prefinjene pristop, kar je še vedno
imenovane razpršene tabele.
In hašiš, kot prahi, kaj Mislim, je kazalo, da
Sem prej omenil.
Za razpršitev kaj lahko misel kot glagol.
>> Torej, če ste hash Alice je ime, hash funkcijo, če se tako izrazim,
bi se morali vrniti številko.
V tem primeru je nič, če ji pripada na lokacija nič, ena, če ji pripada na
lokacija ena, in tako naprej.
Torej moj hash funkcija je bila doslej super enostavna, samo gledaš
Prva črka v imenu nekoga drugega.
Ampak hash funkcija je kot vhod nekateri podatek,
string, int, karkoli.
In to izpljune tipično številko.
In ta številka je, če da so podatki element sodi v podatkovno strukturo
Tukaj znan kot razpršene tabele.
>> Torej samo intuitivno, to je nekoliko drugačen kontekst.
To dejansko se nanaša na primer vključujejo rojstni dnevi, kjer je
tam je lahko toliko kot 31 dni v mesecu.
Toda kaj je ta oseba odloči, da bo storiti v primeru trka?
Kontekst zdaj pa ne trk Imena, vendar trčenja na rojstne dneve,
Če dve osebi enako rojstni dan 2. oktobra, na primer.
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Ja, tukaj imamo vzvoda, povezanih seznamov.
Zato malo drugače zgleda kot smo jo narisal prej.
Ampak mi zdi, da imajo na matriko na levi strani.
To je en indeks, ne za posebnega razloga.
Vendar je še vedno polje.
To je niz kazalcev.
In vsak od teh elementov, vsak Ti krogi ali poševnico - slash
predstavlja nična - vsak od teh kazalci se očitno kaže na
kaj podatkovna struktura?
Povezani seznam.
>> Torej, zdaj imamo možnost, da Težko kodo v našem programu
velikost tabele.
V tem primeru vemo, da nikoli več kot 31 dni v mesecu.
Tako težko kodiranje vrednost, kot je 31. smiselno v tem kontekstu.
V okviru imen, težko kodiranje 26 je dopustno, da ljudje jev
Imena šele z, na primer, abeceda, ki vključuje do Z.
>> Mi lahko Natrpati jih vsi v teh podatkov Struktura dokler, ko smo dobili
trčenje, mi ne dajo imena tukaj, smo namesto da teh celic
ne kot strune sami, ampak kot kazalci, na primer, Alice.
In potem Alice še en kazalec drugo ime se začne z
A. In Bob pravzaprav gre tukaj.
>> In če je drugo ime se začne z B, je konča tukaj.
In tako vsak od elementov te Tabela dva, če smo oblikovali to
malo bolj spretno -
no -
Če smo oblikovali to malo več pametno, zdaj postane prilagodljivo podatke
struktura, kjer ni težko meja o tem, koliko elementov lahko vstavite
v tem, ker če imate trčenje, da je v redu.
Samo pojdi naprej in ga dodajte kar smo videli malo nazaj je bila
znana kot povezan seznam.
>> Pa kaj je premor za trenutek.
Kakšna je verjetnost trka Na prvem mestu?
Dobro, morda bom več razmišljal, morda Jaz sem nad inženiring ta problem,
saj veste kaj?
Ja, lahko prišli do samovoljne Primeri off vrhu moje glave, kot
Allison in Aron, ampak v resnici, saj enakomerna porazdelitev
vhodov, da je nekaj naključnih vložki v strukturo podatkov, kaj je res
Verjetnost trčenja?
No, izkaže, da je dejansko super visoka.
Dovolite mi, da posploševati to Problem je, kot je ta.
>> Torej, v sobi n CS50 študentov, kar je Verjetnost, da vsaj
dva študenta v sobi imajo isti rojstni dan?
Torej ni kaj. Nekaj ​​hund -
200, 300 ljudi tukaj in več sto ljudi doma danes.
Torej, če si hotel, da se vprašamo, kaj je verjetnost dve osebi
v tej sobi, ki ima enako rojstni dan, bomo lahko to ugotovite.
In trdim, pravzaprav obstajata dve ljudje z istim rojstni dan.
>> Na primer, ali kdo ima danes rojstni dan?
Včeraj?
Jutri?
Vse je v redu, tako da se zdi, kot da bom da ima za to 363 ali tako več
krat, da dejansko ugotovimo, če imamo trčenje.
Ali pa bi samo to matematično namesto tediously
to.
In predlaga naslednje.
>> Zato sem predlagal, da bi lahko modelirati Verjetnost dveh ljudi, ki imajo
Enako, kot rojstni dan verjetnostjo 1. minus verjetnost, da nihče, ki ima
Enako rojstni dan.
Tako, da se to, kar je samo fancy način pisanja tega, za
Prva oseba v sobi, on ali ona ima lahko eno od možnosti
rojstni dnevi ob predpostavki, 365 dni v letu, se opravičujem oseb
29. februar rojstni dan.
>> Torej prva oseba v tej sobi je prost da imajo poljubno število rojstne dneve
od 365 možnosti tako, da potrudili se bomo, da 365 deljeno z 365,
ki je ena.
Naslednji, v prostoru, če želimo se izogne ​​trčenju, lahko le
ima njegov ali njen rojstni dan o tem, kako veliko različnih možnih dni?
364.
Torej drugi mandat v tem izrazu v bistvu gre ta matematika za nas
z odštevanjem off en možen dan.
Potem Naslednji dan Naslednji dan Naslednji dan do celotnega števila
oseb v sobi.
>> In če bomo potem pa razmisli, kaj potem je verjetnost, ne pa vsakdo, ki ima
edinstvene rojstni dnevi, ampak spet 1 minus da je tisto, kar smo dobili, je izraz
da lahko zelo domišljisko videti takole.
Ampak to je bolj zanimivo pogled na vizualno.
To je graf, kjer na x-osi je število oseb v sobi,
število rojstnih dni.
Na osi y je verjetnost kakšnega trčenja, dve osebi
ob isti rojstni dan.
>> In takeaway iz te krivulje je da takoj, ko dobiš všeč 40
študente, ti si na 90% verjetnostjo combinatorically dveh
ljudje ali več, ki imajo Enako rojstni dan.
In ko prideš do 58 ljudi všeč, da je skoraj 100% priložnost dveh
ljudje v prostoru se dogaja, da imajo Enako rojstni dan, čeprav je
365 ali 366 možnih vedra in Samo 58 ljudi v sobi.
Samo statistično boste verjetno dobili trčenja, ki na kratko
motivira to razpravo.
Da tudi če bomo dobili fancy tukaj, in začeli ob teh verig, smo še vedno
dogaja, da imajo trkov.
>> Tako da se postavlja vprašanje, kaj je Stroški dela vstavljanje in brisanje
v podatkovno strukturo, kot je ta?
No naj predlagajo -
in naj se vrnem na zaslonu nad tukaj - če smo n elemente
seznam, tako da, če poskušamo vstaviti n elementi, in imamo
koliko skupno vedra?
Recimo 31 skupna vedra v primeru rojstnih dni.
Kaj je največja dolžina enega teh verig potencialno?
>> Če spet tam 31 mogoče rojstni dnevi v določenem mesecu.
In mi smo samo skupki vsakogar -
to je pravzaprav neumen primer.
Naredimo 26 namesto.
Torej, če dejansko imajo ljudje, katerih imena začnete z do Z, s čimer
nas 26 možnosti.
In smo z uporabo podatkovne strukture, kot so Tisti, ki smo pravkar videli, s katerim imamo
niz kazalcev, od katerih opozarja na povezanem seznamu, kjer je
Prvi seznam je vsakdo z imenom Alice.
Drugi list je vsak z ime se začne z, začenši
z B, in tako naprej.
>> Kakšna je verjetnost, dolžina vsakega od ti seznami če predpostavimo, lepo čist
distribucija imen prek Ž vsej strukture podatkov?
Tam je n ljudi v strukturi podatkov deljeno z 26, če oni lepo
razširila čez celotno struktura podatkov.
Torej, dolžina vsakega od teh verige je N deljeno z 26.
Ampak v veliki O zapisu, kaj je to?
Kaj je to res?
Torej je res samo n, kajne?
Ker smo rekli v preteklosti, mo, da si delimo s 26.
Da, v resnici pa je hitrejši.
Ampak v teoriji, to ni bistveno vse to hitreje.
>> Torej mi ne zdi, da je vse to veliko bližje tej sveti gral.
Dejstvo je, da je to le linearni čas.
Heck, na tej točki, zakaj ne bomo le z eno ogromno povezan seznam?
Zakaj ne bi raje uporabite ena velika polje za shranjevanje imen
vsi v sobi?
No, obstaja še vedno nekaj prepričljiv o razpršene tabele?
Ali obstaja še kaj prepričljiv o strukturi podatkov
ki je videti takole?
To.
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Ja, in še enkrat, če je le linearni čas algoritem in
linearna struktura podatki času, zakaj ne jaz samo shranite ime vsakogar, v veliki
matrika, ali v velikem povezana seznamu?
In neha CS toliko težje kot je treba?
Kaj je prepričljiv zaradi tega, čeprav čeprav sem popraskal ven?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Vstavljeno ne?
Drago več.
Torej vložki potencialno lahko še vedno konstantna čas, čeprav vaši podatki
Struktura izgleda takole, niz kazalcev, od katerih je vsaka kaže na
potencialno povezani seznam.
Kako bi lahko dosegli konstantno Čas vstavljanje imen?
Ga držijo v ospredju, kajne?
>> Če bomo žrtvovati design cilj iz prej, ko smo želeli ohraniti
ime vsakogar, na primer, razporejene, ali vse številke v fazi razporejene,
Predpostavimo, da imamo unsorted povezani seznam.
To nas stane le enega ali dva koraka, kot v primeru Ben in Brian
prej, da vstavite element pri začetek seznama.
Torej, če nam ni mar za razvrščanje vse imen, ki se začnejo z ali vse
imena se začnejo s črko B, lahko še vedno dosegli konstantno čas vstavitve.
Zdaj si gor Alice ali Boba ali katero koli ime na splošno je še kaj?
To je velik O n deljeno z 26, v idealen primer, kjer so vsi enakomerno
porazdeljena, kjer obstaja toliko je kot so Z., kar je verjetno
nerealno.
Ampak to je še vedno linearna.
>> Ampak tukaj smo prišli nazaj do točke od asimptotičnega zapis počutje
teoretično res.
Toda v resničnem svetu, če trdim, da moj program lahko storimo nekaj 26-krat
hitreje kot tvoj, katerih program, boš raje uporabljate?
Tvoje ali moje, ki je 26-krat hitreje?
Realno, oseba, ki je 26. krat hitreje, čeprav teoretično
naši algoritmi tečejo v isti asimptotska teče čas.
>> Dovolite mi, da predlagam drugačen Rešitev v celoti.
In če to ne bo razstrelil svoj um, smo iz podatkovnih struktur.
Torej to je to Trie -
nekako neumno ime.
Prihaja od dostopov in Beseda so napisane Trsta, t-r-i-e, ker
Tečaj iskanje zveni Trsta.
Ampak to je zgodovina iz besednega Trsta.
>> Torej Trie je res neke vrste drevesa, in to je tudi igra na te besede.
In čeprav ga ne morete povsem videli z vizualizacijo, Trie je
drevo strukturirane, kot družinsko drevo en prednik na vrhu in še mnogo
z vnuki in pravnuki saj ima na dnu.
Ampak vsako vozlišče v Trsta je matrika.
In to je v paleto - in naj poenostavljam za trenutek - to je
matrika, v tem primeru, velikosti 26, kjer vsako vozlišče spet je matrika velikosti
26, kjer Ničti element, ki matrika predstavlja, in nazadnje
element pri vsaki tak matrika predstavlja Z.
>> Torej predlagam torej, da so ti podatki struktura, znan kot Trsta, lahko
Uporablja se tudi za shranjevanje besede.
Smo videli pred nekaj trenutki, kako smo lahko shranite besede, ali v tem primeru imena, in smo
videl prej, kako lahko shranjujete številke, ampak, če se osredotočimo na imena ali kitah
je, da vidite, kaj je zanimivo.
Trdim, da je ime Maxwell znotraj te strukture podatkov.
Kje vidite Maxwell?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Na levi.
Torej, kaj je zanimivo s temi podatki Struktura je namesto trgovini z
Niz M-A-X-W-E-L-L nagibnica nič, vse contiguously, kaj si namesto tega
sledi.
Če je to Trie kot strukturo podatkov katerih posamična vozlišča spet matrika,
in želite shraniti Maxwell, morate najprej indeks in tako korena je vozlišče, tako
govoriti, je vrhunsko vozlišče, na lokaciji M, desno, tako
približno v sredini.
In potem od tam, sledite kazalec otroka vozlišč, tako rekoč.
Torej v smislu družinskega drevesa, jo slediti navzdol.
In da vas vodi v drugo vozlišče na levi pa, ki je
samo še en niz.
>> In potem, če želite shraniti Maxwell, boste našli kazalec, ki predstavlja
, Ki je tale.
Potem greš na naslednje vozlišče.
In obvestilo - to je razlog, zakaj je slika malo vara -
To vozlišče videti super majhen.
Toda na desni strani to Y in Z. To je samo avtor je okrnjena
slike, tako da si dejansko vidim stvari.
V nasprotnem primeru to sliko bi bilo zelo širok.
Torej, zdaj ste indeks v mestu X, nato W, potem E, nato L, nato pa L. In kaj je
to radovednost?
>> No, če smo z uporabo te vrste novo da o tem, kako shraniti niz v
struktura podatkov, morate še vedno v bistvu odkljukajo v podatkih
Struktura, da beseda konča tukaj.
Z drugimi besedami, vsak od teh vozlišč Nekako se je treba zavedati, da smo
dejansko sledi vseh teh kazalcev in puščajo le malo
Prezla na dnu je te strukture, ki označuje M-A-X-W-E-L-L je
dejansko je v tej strukturi podatkov.
>> Tako smo lahko to stori, kot sledi.
Vsaka od vozlišč v sliki smo le žaga ima eno, matrike velikosti 27.
In to je zdaj 27, ker je v p nastavite šest, bomo dejansko vam opuščaj,
tako da bomo lahko imeli imena, kot O'Reilly in druge s opuščaji.
Ampak isto idejo.
Vsak od teh elementov matrične kaže na struct
vozlišče, tako da samo vozlišče.
Tako da je to zelo spominja našega povezanega seznama.
>> In potem imam logičnim, kar bom klic besedo, ki je šele bo
Res, če beseda konča na ta vozlišče v drevesu.
To dejansko pomeni malo trikotnik smo videli pred nekaj trenutki.
Torej, če se beseda konča na tem vozlišču v drevo, da bo beseda polje bilo res,
, ki je konceptualno preverjanje off, ali smo risanje ta trikotnik, da obstaja
je tu ključna beseda.
>> Torej je to Trie.
In zdaj vprašanje je, kaj je svoj čas teče?
Je velik O n?
Ali je kaj drugega?
No, če ste n imena v teh podatkov struktura, Maxwell so le eden
jim, kaj je čas teče vstavljanje ali iskanju Maxwell?
Kaj je čas delovanja vstavljanje Maxwell?
Če je n druga imena že na mizi?
Ja?
>> ŠTUDENT: [neslišno].
>> SPEAKER 1: Ja, to je dolžina imena, kajne?
Torej M-x-w-e-l-l, da se zdi, kot to Algoritem je velik O sedem.
Zdaj je seveda ime različno dolgi.
Morda je to kratko ime.
Mogoče je daljša imena.
Toda kaj je ključ v tem, da je nespremenjeno število.
In morda to ni res konstanten, Toda Bog, če je realno, v
slovar, tam je verjetno nekaj omejitev na število črk v
Ime osebe v določeni državi.
>> In tako lahko sklepamo, da vrednost je konstantna.
Ne vem, kaj je.
Verjetno je večja od mislimo, da je.
Zato, ker je vedno nekaj kotiček Primer z noro dolgo ime.
Torej, kaj je to k poklicati, vendar je še vedno stalna verjetno, ker je vsak
ime v svetu, vsaj v predvsem država, je, da je dolžina ali
krajši, tako da je konstantna.
Toda, ko smo povedal, da je nekaj velikega O izmed konstantno vrednost, kaj je to
res enaka?
To je res ista stvar kot pravim stalno čas.
>> Zdaj smo nekako varanje, kajne?
Mi smo nekako vplivno nekaj teorije Tukaj reči, da dobro, da bi v K
res samo odredi enega, in je konstantna čas.
Vendar je res.
Ker je ključni vpogled v tem, da če smo n imena že v tem
podatkovne strukture, in mi vložek Maxwell, je čas, ki ga nas popelje
vstavite Maxwell na vseh prizadetih s tem, koliko drugih ljudi
v podatkovno strukturo?
Ne zdi, da bo.
Če bi imel milijardo več elementov za to Trie in nato vstavite Maxwell, ki je
je sploh vpliva?
Število
In to je za razliko od vseh podatkov dan strukture smo videli doslej, kjer
čas vaše algoritem teče, je popolnoma neodvisna od koliko
stvar je ali ni že V tej strukturi podatkov.
>> In tako s tem daje sedaj je Priložnost za p niz šestih, ki bo
spet vključevalo izvajanje svoje črkovalnik, branje na 150.000
besede, kako najbolje hraniti, da ni nujno očitna.
In čeprav sem hrepenela, da bi našli sveti gral, ne vem
trdijo, da je Trie.
V resnici, lahko razpršena tabela zelo dobro izkaže, da je veliko bolj učinkovito.
Ampak to so le -
to je samo ena od konstrukcijskih odločitev boste morali narediti.
>> Toda v zapiranju vzemimo 50 ali tako sekund, da si oglejte, kaj se skriva
naprej naslednji teden in naprej smo prehod od tega ukazni vrstici
svetu, če C programi na stvari spletu temelji in jeziki, kot so PHP in
JavaScript in internet sam, protokolov, kot so HTTP, ki ste
samoumevno let sedaj, in natipkana najbolje vsak
dan, morda, ali videli.
In bomo začeli lupine nazaj plasti, kaj je internet.
In kakšna je koda, ki osnovane današnji orodja.
Torej 50 sekund te teaser tukaj.
Dam ti bojevniki Net.
>> [Predvajanje videa]
>> -Prišel je s sporočilom.
S protokolom vse svoje lastne.
Prišel je v svetu krutih požarnih zidov, neskrbni usmerjevalniki, in nevarnosti daleč
hujše od smrti.
Hiter je.
On je močan.
On je TCPIP.
In ima svoj naslov.
Bojevniki Net.
>> [END predvajanje videa]
>> SPEAKER 1: To je, kako internet deluje kot naslednji teden.