>> SPEAKER 1: Rendben, így visszatértek.
Üdvözöljük a CS50.
Ez a vége a hét hét.
Így emlékszem, hogy az utolsó alkalom, elkezdtük néztem kicsit bonyolultabb
adatszerkezeteket.
Mivel eddig minden volt igazán a rendelkezésünkre álló volt ez, egy tömbben.
>> De mielőtt dobja a tömb nem minden érdekes, ami valóban az
valójában, mik az pluses az egyszerű adatok
struktúra eddig?
Mi ez az jó?
Amennyire láttuk?
Mi van?
Semmi.
>> DIÁK: [hangtalan].
>> SPEAKER 1: Mi ez?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Rögzített méret.
OK, miért is jó, bár fix méret?
>> DIÁK: [hangtalan].
>> SPEAKER 1: OK, így hatékony az értelemben, hogy lehet lefoglalni a
rögzített méretű tárterület, amely remélhetőleg pontosan annyi
hely, amit akar.
Ahhoz, hogy lehet, hogy teljesen egy plusz.
>> Mi a másik fejjel a tömb?
Igen?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Az összes - Tessék?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Minden a dobozokat a memóriában vagy egymás mellett.
És ez hasznos - miért?
Ez teljesen igaz.
De hogyan tudjuk kihasználni ezt az igazságot?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Pontosan tudjuk nyomon követni ahol minden csak azáltal, hogy ismerik
egy címet, azaz a címét a első byte, hogy a darab a memóriát.
Illetve abban az esetben a húr, a cím az első
char-ben, hogy a húr.
És ott találunk a végén a húr.
Megtalálhatjuk a második elem, a harmadik elem, és így tovább.
>> És így a divatos módon írja le, hogy jellemzője, hogy tömbök nekünk
véletlen elérésű.
Csak használja a szögletes zárójel jelölést, és egy számot, akkor ugorhat
egy adott elem a tömbben állandó időben, nagy O
az egyik, hogy úgy mondjam.
>> De van itt egy kis árnyoldalai.
Amit egy sor nem túl könnyen?
Mi ez az nem jó?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Mi ez?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Táguló méretű.
Így a hátrányai a tömb éppen az ellenkezője annak, amit a
upsides van.
Tehát az egyik hátránya az, hogy ez egy fix méretű.
Így nem igazán nő meg.
Lehet átcsoportosítása nagyobb darab memória, majd távolítsa el a régi elemeket
az új tömb.
És akkor szabad a régi tömb, a Például, segítségével malloc vagy hasonló
nevű függvényt realloc, amely átcsoportosítása memória.
>> Realloc, mint félre, megpróbálja, hogy az Ön memória a következő lépés, hogy a tömb
, hogy már van.
De lehet mozgatni a dolgokat körül teljesen.
De röviden, ez drága, ugye?
Mert ha van egy darab memória ezt a méretet, de szeretné egy
Az ilyen méretű, és szeretné megőrizni Az eredeti elemek, akkor
nagyjából lineáris idő másolási folyamat hogy kell történni
régi tömb az új.
És a valóság azt kéri a működési rendszer újra és újra és
Ismét nagy darabokban a memóriát lehet kezdeni kerülni egy kis időt is.
Tehát egyszerre áldás és átok álcázzák, az a tény, hogy ezek a tömbök
, fix méretű.
De ha be helyette valami mint ez, amit úgynevezett kapcsolt
lista, akkor kap egy pár upsides és néhány hátrányai itt is.
>> Tehát egy láncolt lista egyszerűen egy adat szerkezetét alkotják C struktúrákat ebben
esetben, amikor egy struct, visszahívás, csak egy tartályt, egy vagy több meghatározott
típusú változók.
Ebben az esetben mit az adattípusok úgy tűnik, hogy a belső struktúra, amely
utoljára hívott egy csomópont?
Minden ilyen téglalapok egy csomópont.
És az egyes kisebb téglalapok belül ez az adat típusát.
Milyen mondtunk voltak hétfőn?
Igen?
>> DIÁK: [hangtalan].
>> SPEAKER 1: A változó, és a mutató, vagy Pontosabban, egy int, n,
és egy mutatót az alján.
E két történetesen 32 bit, a legalább egy számítógép, mint a CS50
Készülékhez, és így ők húzott egyaránt méretű.
>> Tehát mi a mutató noha a látszólag?
Miért ezt az most, amikor a nyíl tömbök voltak olyan szép és tiszta és egyszerű?
Mi a mutatót tesz az minket minden ilyen csomópont?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Pontosan.
Azt mondja, hogy hol a következőt.
Szóval fajta használat az analógia egy szál egyfajta
menet ezek a csomópontok egymáshoz.
És pontosan ez az, amit mi csinálunk az pointerek, mert minden egyes ilyen
darabokat a memória lehet vagy nem lehet összefüggő, háttal vissza
belső RAM-mal, mert minden egyes alkalommal, amikor hívja malloc mondván ad nekem elég
byte egy új csomópont, akkor lehet, hogy hogy itt, vagy lehet, hogy itt.
Lehet, hogy itt.
Csak nem tudom.
>> De a mutatók a címét azokat a csomópontokat, akkor öltés őket
együtt oly módon, hogy úgy néz ki, vizuálisan mint egy lista, még ha ezek a dolgok
minden szét az egész egy- a kettő vagy a négy gigabájt RAM
belül a saját számítógépén.
>> Tehát a hátránya, akkor a A láncolt lista, mi?
Mi az ára vagyunk látszólag fizet?
>> DIÁK: [hangtalan].
>> SPEAKER 1: több hely, nem igaz?
Már ebben az esetben, az összeg megduplázódott a tér, mert mi már elment
32 bit minden csomópont minden egyes int, így most 64 bites, mert meg kell
folyamatosan mintegy mutató is.
Kapsz hatékonyabb, ha a struktúra nagyobb, mint ez az egyszerű dolog.
Ha valóban van egy tanuló belül , amely egy pár húrok
név és a ház, talán egy azonosító számot, esetleg más területeken összesen.
>> Tehát, ha van egy elég nagy struct, akkor talán a költségek a mutató
nem olyan nagy dolog.
Ez egy kicsit a sarokban eset, hogy mi tárolása ilyen egyszerű primitív
belül a láncolt lista.
De a lényeg ugyanaz.
Te határozottan kiadások több memória, de akkor már
rugalmasság.
Mert most, ha azt akarom, hogy egy elemet elején ez a lista,
Van hozzá egy új csomópontot.
És azt kell csak frissíteni az nyilak valahogy csak mozog
Egyes mutatók körül.
>> Ha szeretné szúrni valamit a közepén a lista, nem kell
tolja félre mindenki, ahogy tettük hét múlt a mi önkéntesek, akik
képviselte tömb.
Én csak ki egy új csomópontot és akkor csak pont a nyilak
különböző irányokba, mert nem kell maradniuk a tényleges
memória egy igazi sort, amit húzott itt a képernyőn.
>> És akkor végül, ha azt szeretnénk beszúrni valamit a végén a lista, ez
még könnyebb.
Ez a fajta önkényes jelölés, de 34 a mutató, hogy egy kitalálni.
Mi az értéke a legtöbb mutató valószínű húzott valami, mint egy régi
iskola antenna ott?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Talán null.
És valóban, ez az egyik szerző képviselete null.
És ez null, mert teljesen tudniuk kell, hol a végén egy kapcsolt
lista, nehogy tartani a következő, és következő és az azt követő A nyilak
néhány szemetet értéket.
Így null fogja jelenti, hogy nincs több csomópont jobbra szám 34,
ebben az esetben.
>> Ezért javaslom, hogy végre ez a csomópont kódot.
És láttunk ilyen A szintaxis előtt.
Typedef csak definiál egy új típusú bennünket, ad nekünk egy szinonimája, mint a
szöveg volt char *.
Ebben az esetben, ez lesz, hogy nekünk rövidítéseket, hogy a struktúra csomópont
ehelyett csak írható fel csomópont, ami sokkal tisztább.
Ez egy sokkal kevésbé bőbeszédű.
>> Belsejében egy csomópont látszólag egy int nevezett n, majd a struct csomópont *
ami azt jelenti, hogy pontosan mit akarunk a nyilak azt jelenti, egy mutatót egy másik
csomópont pontosan ugyanolyan típusú adatokat.
És azt javaslom, hogy mi is végre egy keresési funkció, mint ez, ami a
Első pillantásra úgy tűnhet, egy kicsit bonyolult.
De nézzük, hogy összefüggésben.
>> Hadd menjek át a készülék itt.
Hadd nyit egy fájlt a lista nulla pont h.
És, hogy csak azokat a definíció is Most láttam egy pillanatra ezelőtt ez az adat
típusú úgynevezett csomópont.
Így már fel, hogy egy pont h fájlt.
>> És mint félre, bár ez a program, fogsz látni,
egyáltalán nem olyan bonyolult, hogy ez valóban egyezmény írásakor a program
a dolgokat, mint a adattípusok, hogy húzza állandók néha belül a
header fájlt, és nem feltétlenül a a C fájlt, természetesen, amikor a
programok egyre nagyobbak, így a tudja, hol kell keresni mind a
dokumentáció egyes esetekben, vagy az alapok, mint ez, a
meghatározása bizonyos típusú.
>> Ha most nyit lista nulla pont c, észre néhány dolgot.
Ez magában foglalja a pár header fájl, a legtöbb amely már látott.
Ez magában foglalja a saját header file.
>> És mint félre, miért ez kétszeres idézetek itt, szemben a szög
zárójelben a vonalon, hogy Már kiemelt ott?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Igen, tehát ez egy helyi fájl.
Tehát, ha ez egy helyi fájl a saját itt on line 15, például, használja
Az idézőjelek helyett A szögletes zárójelben szerepel.
>> Most ez elég érdekes.
Figyeljük meg, hogy én már kijelentette, a globális változó a program on-line 18
hívott először, az ötlet is, hogy ez lesz a mutató az első
node a láncolt lista, és én inicializálni, hogy nulla, mert én már
nem osztják tényleges csomópontok csak még.
>> Tehát ez azt jelenti, képszerűen, amit látta, hogy egy perce a képet
hogy mutató a távoli bal oldalon.
Tehát most, hogy a mutató nem rendelkezik egy nyíl.
Ez inkább csak null.
De ez jelenti, hogy mi lesz a címét az első tényleges
node ebben a listában.
Így megadtam azt a globális mert, mint látni fogod, mindez
program nem az életben végre egy láncolt lista számomra.
>> Most már van egy pár prototípus itt.
Úgy döntöttem, hogy végre funkciók, mint a törlés, beillesztés, keresés, és a
bejárása -
Az utóbbi csak, hogy séta a lista kinyomtatásával elemei.
És most itt van a fő rutin.
És nem túl sok időt töltenek a Ezen mivel ez a fajta, remélhetőleg
öreg már.
>> Fogok csinálni a következő, miközben a felhasználó együttműködik.
Tehát az egyik, megyek nyomtatni ki ebben a menüben.
És én ezt alakítottuk tisztán, ahogy csak tudtam.
Ha a felhasználó az egyik, ami azt jelenti, akarnak törölni valamit.
Ha a felhasználó két, azt jelenti, hogy akarnak szúrni valamit.
És így tovább.
Megyek, majd gyors majd a parancs.
És akkor fogom használni getInt.
>> Tehát ez egy nagyon egyszerű menuing felület, ahol csak be kell gépelni
Számos leképezés egy olyan parancsokat.
És most van egy szép tiszta switch nyilatkozat arról, hogy fog bekapcsolni
, amit a felhasználó beírt szöveg
És ha megadtunk, én hívás törléséhez és szünet.
Ha két gépelt, én hívja be, és szünet.
>> És most észre tettem minden Ezek ugyanabban a sorban.
Ez csak egy stilisztikai döntést.
Általában láttunk valamit , mint ez.
De úgy döntöttem, őszintén szólva, a programom látszott olvashatóbb, mert
hogy csak négy esetben csak a lista, mint ez.
Teljesen jogszerű használatát a stílus.
És én fogom csinálni, amíg a felhasználó még nem írta nulla, ami azt
úgy döntött, akkor azt jelenti, hogy ki akar lépni.
>> Szóval most észre, amit én fog itt csinálni.
Megyek, hogy kiszabadítsa a lista nyilvánvalóan.
De még az, hogy csak egy pillanatra.
Nézzük először a program futtatásához.
Hadd tegyek egy nagyobb terminál ablak, pont slash listán 0.
Én megyek előre, és helyezze a gépelés két, több mint 50, és most
látni fogja a lista most már 50..
És a szöveg csak görgetni egy kicsit.
Tehát most észre a lista a 50-es.
>> Csináljunk egy betétet, hogy két.
Nézzük írja be a számot, mint egy.
Lista ma már az egyik, majd a 50.
Tehát ez csak egy szöveges megjelenítése a lista.
És nézzünk be még egy szám, mint száma 42, ami remélhetőleg
lesz, hogy a végén a közepén, mert a ezt a programot, a különböző fajtájú is
elemeket, mint betétek azokat.
Tehát ott van rá.
Szuper egyszerű programot, amely Teljesen használt egy tömb, de
történetesen egy láncolt lista csak azért, hogy dinamikusan
növekszik, és csökken az.
>> Szóval vessünk egy pillantást a keresést, ha indítási parancs három akarok keresni
, mondjuk, a 43-as.
És semmi sem úgy tűnik találtak, mert kaptam vissza semmi válasz.
Szóval ezt újra.
Keresés.
Keressünk 50, vagy inkább keressen 42, amely egy szép
kis finom értelme.
És megtaláltam az élet értelmét is.
Number 42, ha nem tudod A referencia, a Google is.
Rendben van.
Tehát mi ezt a programot tett velem?
Ez csak lehetővé tette számomra, hogy helyezze így messze keressen elemekkel.
>> Nézzük gyors előre, aztán, hogy ezt a funkciót is nézett
hétfőn a teaser.
Tehát ezt a funkciót, azt állítom, keres egy elemet a listában első
egy, a felhasználó megkérdezése, majd a hívás GetInt hogy tényleges int
hogy szeretne keresni.
>> Aztán észre.
Megyek, hogy hozzon létre egy ideiglenes változót sorban 188 nevű mutató -
PTR -
volna nevezte semmit.
És ez egy mutató egy csomópont mert azt mondtam, node * ott.
És én inicializálása, hogy egyenlő először úgy, hogy hatékonyan van a
ujj, hogy úgy mondjam, a nagyon első elemét a lista.
Tehát, ha a jobb kezem itt van PTR vagyok mutatott ugyanaz a dolog, hogy az első
néz.
>> Tehát most vissza kódot, mi történik ezután -
ez egy közös paradigma amikor iterációjával egy szerkezet, mint a
láncolt lista.
Fogok csinálni a következő, míg mutató nem egyenlő null Tehát miközben
az ujjam nem mutat valami null érték, ha a mutató nyíl n értéke n.
Majd észre először, hogy n, amit a felhasználó beírt egy GetInts hívás itt.
>> És a mutató nyíl n mit jelent?
Nos, ha visszamegyünk a kép itt, ha van egy ujjal mutatva
hogy az első csomópont, amely kilenc, a arrow lényegében azt jelenti, megy, hogy a
csomópont és megragad a érték helyre n Ebben az esetben, az adatmező nevezett n.
>> Mint félre -, és láttuk ezt néhány héttel ezelőtt, amikor valaki megkérdezte -
Ez a szintaxis az új, de nem nekünk hatáskörrel, hogy
nem volt már.
Mi volt ez a mondat egyenértékű a dot jelölés és a csillag egy pár
héttel ezelőtt, amikor hámozott vissza ez a réteg egy kicsit korán?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Pontosan ez volt a csillag, és akkor volt csillag dot N, ahol
zárójelek itt, ami úgy néz ki, őszintén szólva, azt gondolom, hogy sok
több rejtélyes olvasni.
De csillag mutató, mint mindig, azt jelenti, ott.
És ha már ott van, hogy milyen adatok mezőt akarsz elérni?
Jól használja a pont jelölést eléréséhez a struktúrákat adatmező, és
az a célunk n.
>> Őszintén szólva, azt állítják, ez a csak nehezebb olvasni.
Ez nehezebb emlékezni, ahol nem a zárójelek megy, a
csillag, és minden adott.
Így a világ elfogadott bizonyos szintaktikai cukrot, hogy úgy mondjam.
Csak egy szexi szóval, ez egyenértékű azzal, és
talán intuitív.
Ha a mutató valóban mutató, az nyíl jelölés azt jelenti, menj oda, és megtalálni
területen ebben az esetben az úgynevezett n.
>> Tehát, ha látom, hogy figyeld meg, mit tegyek.
Egyszerűen nyomtassa ki, találtam százalék i, csatlakoztatása az értéket, hogy az int.
Hívom aludni egy másodpercig csak ilyen szünet dolgokat a képernyőn, hogy
hogy a felhasználó egy másik, hogy felszívja mi történt.
Aztán szünet.
Egyébként, mit tegyek?
Én frissíteni mutató egyenlő mutató nyílra.
>> Szóval, csak hogy tisztázzuk, ez azt jelenti, menj ott, a régi iskola jelölést.
Tehát ez csak azt jelenti, hogy megy, hogy bármilyen akkor mutatott, ami az igen
első esetben én mutat A struct kilenc benne.
Úgyhogy elment oda.
És akkor a pont jelölés azt jelenti, hogy kap az érték a jövő.
>> De az érték, annak ellenére, hogy húzott mint egy szűk, csak egy szám.
Ez egy numerikus cím.
Tehát ez egy sort, hogy a írt, mint ez, a több rejtélyes
módon, vagy mint ez a valamivel több intuitív módon, csak azt jelenti, mozog a kezem
az első csomópontból a következő egy, majd a következő, majd a
következő egy, és így tovább.
>> Így nem tér ki a többi implementáció beszúrni és törölni
és bejárás, az első két amely meglehetősen szó.
És azt hiszem, ez elég könnyű, hogy elveszett, amikor csinálja verbálisan.
De mit tehetünk itt próbálja meghatározni, hogyan
legjobb, ha ezt vizuálisan.
Mert azt javaslom, hogy ha szeretné szúrni elemeket ebbe
meglévő listához, amely öt elem -
9, 17, 22, 26 és 33 -
ha én fogja végrehajtani ezt kódot, azt kell vizsgálni, hogy hogyan megy
körülbelül ezt.
>> És azt javaslom, apró lépésekben amely ebben az esetben úgy értem, mit
A lehetséges forgatókönyvek, amit ütközhet általában?
Végrehajtása során betét kapcsolt lista, ez csak történik, hogy a
specifikus példája a méret az öt.
Nos, ha azt szeretnénk beszúrni egy számot, mint mondjuk az első számú, és
fenntartása rendezetten, ahol nyilván nem az első számú kell
megy a konkrét példát?
, Mint az elején.
>> De mi érdekes van, hogy a Ha szeretnénk beszúrni egy ebbe
lista, milyen különleges mutató szüksége frissíteni kell látszólag?
Első.
Szóval azt állítják, hogy ez az első eset amit érdemes megfontolni, a
forgatókönyv bevonásával behelyezése a a lista elején.
>> Nézzük tép ki talán egy olyan egyszerű, vagy akár könnyebb eset, viszonylag szerény.
Tegyük fel, hogy szeretné szúrni a szám 35 rendezetten.
Nyilvánvalóan tartozik oda.
Tehát mi mutató nyilván fog frissíteni kell, hogy a forgatókönyv?
34 a mutató egyre nem null de a címét a struct
amely a 35-ös szám.
Szóval ez esetben kettő.
Így már, én vagyok a fajta kvantálás mennyi munkát kell tennem itt.
>> És végül, a nyilvánvaló középső eset sőt, a közepén, ha azt akarom, hogy
be valamit, mint mondjuk 23, hogy megy a 23 és a 26, de
Most a dolgok egy kicsit részt azért, mert mi
mutatókat kell változtatni?
Tehát 22 nyilvánvalóan meg kell változtatni mert nem pont 26. többé.
Azt kell, hogy pont az új csomópont Majd meg kell kiosztani hívja
malloc, vagy valami hasonló.
>> De akkor azt is kell, hogy az új csomópont, 23 ebben az esetben, hogy a mutató
mutatott kinek?
26..
És ott lesz a műveletek sorrendjét itt.
Mert ha ezt ostobán, és például kezdő elején
a listán, és a célom az, hogy helyezze 23..
És megnézem, nem is tartozik Itt, közel kilenc?
Nem.
Vajon ide tartoznak, mellette 17?
Nem.
Nem tartozik ide mellé 22?
Igen.
>> Most, ha én vagyok bolond itt, és nem gondoltam ez a, talán
osztják az új csomópont a 23.
Lehet, hogy frissíteni a mutatót a csomópont neve 22, rámutatva
ez az új csomópontot.
És akkor mit kell frissíteni Az új csomópont mutató lenni?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Pontosan.
Mutatva a 26.
De a fenébe, ha nem már frissíteni 22 a mutató, hogy pont ezt a fickót, és
most már árva, a többi A lista, hogy úgy mondjam.
Így műveletek sorrendjét itt lesz fontos.
>> Ehhez tudtam lopni, mondjuk, hat önkéntes.
És nézzük meg, ha nem tudjuk ezt vizuálisan helyett code-bölcs.
És van néhány szép stressz golyó van ma.
OK, mi egy, két, a vissza - a végén ott.
három, négy, mindketten srácok a végén.
És öt, hat.
Persze.
Öt és hat.
Rendben, és mi jön nektek legközelebb.
Rendben, gyere fel.
>> Rendben, ha már itt az első, szeretné, hogy az egyik ügyetlenül
a Google Glass itt?
Rendben, tehát, OK, Üveg, videofelvétel.
OK, te jó menni.
>> Rendben, ha tudtok jönni Itt már előre elkészített
néhány számot.
Rendben, gyere ide.
És miért nem megy egy kicsit továbbá, hogy így.
És lássuk, mi a neved, A Google Glass?
>> DIÁK: Ben.
>> SPEAKER 1: Ben?
OK, Ben, akkor lesz az első, a szó szoros értelmében.
Így fogunk küldeni hogy a végén a szakaszban.
Rendben, és a neved?
>> DIÁK: Jason.
>> SPEAKER 1: Jason, OK azt is megtudhatod legyen kilences szám.
Tehát, ha szeretné követni Ben így.
>> DIÁK: Jill.
>> SPEAKER 1: Jill, te leszel 17, amely, ha én csináltam volna ezt jobban,
intelligens, szerettem volna kezdődött a másik végén.
Te menj arra.
22..
És te?
>> DIÁK: Mary.
>> SPEAKER 1: Mary, akkor 22.
És a neve?
>> DIÁK: Chris.
>> SPEAKER 1: Chris, akkor 26.
És akkor végül.
>> DIÁK: Diana.
>> SPEAKER 1: Diana, akkor 34.
Szóval gyere ide.
>> Rendben, tökéletes sorrendje érdekében már.
És menjünk előre, és ezt , hogy mi is valójában -
Ben te csak ilyen keres ki a semmiből ott.
OK, menjünk előre, és ábrázolja a a fegyverek, ugyanúgy, mint én, pontosan,
mi folyik itt.
Így megy előre, és hogy a magatok gyalog vagy két magatok között.
És megy előre, és pont egy kézzel aki ha kell mutat
ennek alapján.
És ha null csak pont egyenesen a földre.
OK, így a jó.
>> Tehát most van egy láncolt lista, és hagyd, hogy javasolja, hogy fogok játszani
PTR, így nem zavarja hordozó körül.
És akkor - valaki hülye egyezmény - hívhatja ezt, amit akarsz -
elődje mutató, pred mutató -
ez csak a beceneve adtunk a a minta kódot a bal kezét.
Másrészt, hogy fog tartani követni, hogy ki kicsoda a
következő forgatókönyvek.
>> Tegyük fel, hogy először is azt akarom, hogy tépni le hogy az első példa a behelyezése, mondjuk
20. a listán.
Szóval lesz szüksége, hogy valaki testesítik meg a 20-as számú számunkra.
Szóval kell valaki malloc a közönség.
Gyere fel.
Mi a neve?
>> DIÁK: Brian.
>> SPEAKER 1: Brian, rendben, így kell lennie a csomópont, amely 20.
Rendben, gyere ide.
És természetesen, ahol Brian nem tartozik?
Tehát, a közepén - valójában, várj egy percet.
Mi ezt elromlott.
Mi, hogy ez egy sokkal nehezebb mint azt kell először.
OK, fogunk szabad Brian és realloc Brian öt.
>> OK, így most már a beszúrni kívánt Brian öt.
Úgyhogy gyere ide mellé Ben egy pillanatra.
És akkor valószínűleg mondani ahol ez a történet lesz.
De nézzük alaposan gondolja át, a műveletek sorrendjét.
És pontosan ez a vizuális hogy fog sorban
azzal a minta kódot.
Tehát itt már PTR mutató kezdetben Ben nem önmagában, hanem bármilyen
értékeljük azt tartalmaz, ami ebben az esetben az, - mi is a neved?
>> DIÁK: Jason.
>> SPEAKER 1: Jason, így mindkét Ben és én mutatott Jason ebben a pillanatban.
Így most azt kell meghatározni, hol Brian tartozik?
Tehát az egyetlen dolog, amit férhetnek hozzá most az ő n adat elemet.
Így fogom ellenőrizni, a Brian kevesebb, mint Jason?
A válasz igaz.
>> Tehát mi most meg kell történnie, a helyes sorrendben?
Meg kell frissíteni, hogy hány mutatók összesen ebben a történetben?
Ahol a kezem még mindig mutat Jason, és a kezét -, ha azt szeretné, hogy
tegye a kezét, mint a, fajta, én Nem tudom, a kérdőjel.
OK, jó.
>> Rendben, akkor néhány jelöltet.
Vagy Ben vagy én, vagy Brian, vagy Jason vagy bárki más, ami
mutatókat kell változtatni?
Hányan vannak összesen?
>> OK, így kettő.
My mutató nem igazán számít már mert én vagyok csak átmeneti.
Tehát ez a két fickó, feltehetően, a Ben és Brian.
Hadd javaslom, hogy frissítse Ben, mivel ő az első.
Az első elem a lista most lesz Brian.
Így Ben pont Brian.
OK, most mi lesz?
>> Ki lesz mutatott kinek?
>> DIÁK: [hangtalan].
>> SPEAKER 1: OK, így Brian pont a Jason.
De én elvesztettem a fonalat, hogy a mutató?
Nem tudom, hol van Jason?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Én, mert én vagyok az ideiglenes pointer.
És feltehetőleg már nem változott pont az új csomópontot.
Tehát egyszerűen Brian pont at aki vagyok mutatva.
És kész.
Tehát ha az egyik, beillesztés a a lista elején.
Két fontos lépés.
Egy, meg kell frissíteni Ben, majd mi is frissíteni Brian.
És akkor nem kell bajlódnia traipsing keresztül a többi
lista, mert már megtalálta a hely, mert tartozott a
maradt az első elemet.
>> Rendben, elég egyértelmű.
Sőt, úgy érzi, már majdnem hogy ez túl bonyolult.
Szóval már tépni le a végén A lista, és hol
összetettsége elindul.
Tehát, ha most én alloc a közönség.
Bárki, aki szeretne játszani 55?
Rendben, láttam a kezét először.
Gyere fel.
Igen.
Mi a neve?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Habata.
OK, gyere fel.
Te leszel a szám 55.
Szóval, persze, tartozik végén a listán.
Szóval visszajátszani a szimulációt velem hogy a PTR egy pillanatra.
Szóval először fog mutatni bármi Ben mutatott.
Mindketten mutat most Brian.
Tehát 55 nem kevesebb, mint öt.
Így fogom frissíteni magam mutatott Brian következő mutató, aki
Most természetesen Jason.
55 nem kevesebb, mint kilenc, így Fogom frissíteni PTR.
Fogom frissíteni PTR Fogok frissíteni PTR.
És fogok - hmm, mi a neve?
>> DIÁK: Diana.
>> SPEAKER 1: Diana mutat, persze, A null a bal kezével.
Szóval, ha nem Habata valójában tartozik tisztán?
Balra, itt.
Szóval, honnan tudom, hogy őt itt Azt hiszem, elrontottam.
Mert ami PTR művészet ebben a pillanatban?
Null.
Tehát még akkor is, vizuálisan, tudjuk természetesen az összes ilyen
srácok itt a színpadon.
Én nem tartom számon az előző személy a listán.
Nincs egy ujjal rámutatva, ebben az esetben a csomópont a 34.
>> Szóval tényleg kezd túl rajta.
Szóval most tényleg nem kell Egy másik helyi változót.
És ez az, amit látni fogja a tényleges minta C kód, ahol, ahogy megy,
amikor frissíteni a jobb kezem, hogy pont Jason, így hagyva maga mögött Brian, én
Jobb lenne, ha a bal kezemet, hogy frissítés, ahol voltam, hogy amint megyek
át ezt a listát -
több ügyetlenül, mint akartam most itt vizuálisan -
Megyek, hogy a a lista végén.
>> Ez a kéz még mindig nulla, ami elég haszontalan, kivéve, hogy jelzi
Én egyértelműen az a lista végén, de most legalább már ezt
elődje mutató pointer van, így most mi kéz és milyen mutatókat kell
frissíteni kell?
Kinek a keze akarsz átalakítására az első?
>> DIÁK: [hangtalan].
>> SPEAKER 1: OK, Diana.
Hol szeretne mutatni Diana bal mutató at?
A 55., feltehetően úgy, hogy már be oda.
És ha kell, 55 mutató menni?
Le, ami null.
És a kezem, ezen a ponton, nem számít, mert ők csak
ideiglenes változókat.
Tehát most végeztünk.
>> Így a további komplexitás ott - és ez nem olyan nehéz végrehajtani,
de szükségünk van egy másodlagos változó, hogy a meg arról, hogy mielőtt mozgatni a jobb
viszont tudom frissíteni az érték a bal kéz, pred mutató ebben az esetben, így
hogy van egy hátsó mutató nyomon követni, hogy hol vagyok.
Most, mint egy félre, ha azt gondolva, ez keresztül, ez olyan, mintha egy
kicsit bosszantó, hogy meg kell tartani nyomon a bal kezét.
>> Mi lenne más megoldást erre a problémára volna?
Ha megvan átalakítása az adatok szerkezet beszélünk
a most?
Ha ez csak egyfajta érzi, egy kicsit bosszantó, hogy, mint a két mutató
megy át a listát, ki más van, egy ideális világban, fenn
információt, amire szükségünk van?
Igen?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Pontosan.
Jobb így valójában egy érdekes csírája egy ötletem.
És ez az ötlet, a korábbi mutató, mutatott az előző elem.
Mi van, ha én csak testet öltött, hogy belül a lista is?
És ez lesz nehéz elképzelni ez nem az összes papírt
alá a földre.
De tegyük fel, hogy ezek a srácok egyaránt használható a kezüket, hogy a korábbi
mutató, és a következő mutató, ami végrehajtási mit fogunk hívni kétszeresen
láncolt lista.
Ez lehetővé tenné, hogy valahogy vissza, sokkal könnyebben nélkülem, a
programozó, kelljen tartani pálya kézzel -
igazán kézzel -
hogy hol voltam korábban a listán.
Így nem fogja megtenni.
Tartjuk, hogy egyszerű, mert ez fog jönni az ára, kétszer
sok helyet a mutató, ha egy második.
De ez valóban közös adatstruktúra néven
kétszeresen láncolt lista.
>> Csináljuk az utolsó példa itt, és tegye ezek a srácok ki a nyomor.
Így malloc 20.
Gyere fel Az ott folyosón.
Rendben, mi a neve?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Tessék?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Demeron?
OK gyere fel.
Te leszel 20.
Nyilvánvalóan lesz tartoznak, 17 és 22.
Hadd tanuljanak a leckét.
Fogom kezdeni mutató mutatott Brian.
És megyek, hogy a bal oldali csak frissíteni Brian, ahogy mozog a
Jason, ellenőrzés nem 20 kevesebb, mint kilenc?
Nem.
20 kevesebb, mint 17?
Nem.
20 kevesebb, mint 22?
Igen.
Tehát mi mutatók vagy kézzel kell változtatni ahol ők mutatnak most?
>> Így nem tehetünk 17 mutat 20.
Szóval ez rendben van.
Hol akarunk mutatni a mutatót most?
22.
És tudjuk, hol 22, újra köszönöm az én ideiglenes mutató.
Így rendben vagyunk ott.
Tehát azért, mert az átmeneti tárolás Én folyamatosan követni, ahol mindenki.
És most már vizuálisan menni, ahol tartozol, és most van szükségünk az 1., 2., 3.,
4, 5, 6, 7, 8, 9 stressz labda, és a tapsot
ezek a srácok, ha tudnánk.
Szép munka.
>> [Taps]
>> SPEAKER 1: Rendben.
És lehet, hogy a darab A papír emlékei.
>> Rendben,, hidd el nekem, hogy ez egy nagyon könnyebb séta, hogy a
az emberek, mint azt a tényleges kódot.
De mit talál egy pillanat most, hogy ugyanaz - oh, köszönöm.
Köszönöm -
az, hogy rájössz, hogy ugyanazokat az adatokat szerkezet, a láncolt lista, akkor valójában
lehet használni, mint egy építőelem, hogy még jobban kifinomult adatstruktúrák.
>> És észre is a téma az, hogy már teljesen be több
komplexitás a végrehajtási az algoritmus.
Beillesztése, és ha ment keresztül, törlés és keresés, egy kicsit
bonyolultabb, mint amilyennek volt egy sor.
De szert dinamizmus.
Kapunk adaptív adatstruktúra.
>> De ismétlem, fizetünk az ára némi tovább bonyolítaná, mind a
végrehajtó.
És mi feladta véletlen hozzáférésű.
És hogy őszinte legyek, nincs valami jó tiszta dia tudok adni, hogy
Itt az áll, ezért a láncolt lista jobb, mint egy tömb.
És ennyiben.
Mivel a téma reoccurring most, még inkább a következő hetekben, a
hogy nem feltétlenül a helyes válasz.
>> Ezért van külön tengelyen A design probléma határozza.
Ez nagyon környezetfüggő hogy szeretnénk-e használni ezeket az adatokat
szerkezet vagy hogy az egyik, és ez lesz attól függ, hogy mit számít az Ön szempontjából
az erőforrások és a komplexitás.
>> De hadd javasoljuk, hogy az ideális az adatok szerkezet, a Szent Grál lenne
valamit, ami állandó az időben, függetlenül attól, hogy mennyi a cucc
benne, nem lenne csodálatos, ha a adatstruktúra vissza válaszok
állandó idő.
Igen.
Ez a szó a nagy szótárban.
Vagy nem, ez a szó nem.
Vagy az ilyen probléma.
Nos, nézzük meg, ha nem tudjuk, legalább egy lépést felé, hogy a.
>> Hadd javaslat új adatszerkezet, amely lehet használni a különböző dolgokat,
ebben az esetben úgynevezett hash tábla.
És így, hogy tényleg vissza pillantva egy sor, a jelen esetben, és a
némileg önkényesen, már húzott ezt hash tábla, mint egy tömböt egyfajta
kétdimenziós tömb -
vagy inkább ez látható itt a két dimenziós tömb -, de ez csak
egy sor mérete 26, oly módon, hogy ha mi hívja a tömb, asztali tartó
nulla a téglalapot a tetején.
Asztali tartó 25 a téglalap az alján.
És így talán rajzolni adat szerkezet, amelyben szeretnék tárolni
emberek nevét.
>> Így például, és nem fogom felhívni a egész dolog itt a felső, ha
volt ez a tömb, amit én most megyek hívja a hash tábla, és ez újra
hely nulla.
Ez itt a hely egy, és így tovább.
Azt állítom, hogy szeretném használni ezeket az adatokat szerkezet, a vita kedvéért,
tárolására emberek nevét, Alice és Bob Charlie és egyéb ilyen neveket.
Így gondolom, ez most, mint a kezdet , mondjuk, a szótár
sok szó.
Történetesen neveket a példánkban itt.
És ez nagyon is illenek, talán, hogy megvalósítása a helyesírás-ellenőrző, hiszen
esetlegesen a probléma meg hat.
>> Tehát, ha van egy sor teljes méret 26 úgy, hogy ez az a 25. helyen
az alján, és azt állítják, hogy Alice Az első szó a szótárban
neveket akarok szúrni RAM, ebbe adatstruktúra, hol
ösztönök mondom, hogy Alice név kell menni ebben a tömbben?
>> Van 26 opció.
Ahol szeretnénk tenni vele?
Azt akarom, hogy a konzol nulla, igaz?
A Alice, hívjuk, hogy nulla.
És lesz az egyik B, és C lesz két.
Így fogunk írni Alice nevét itt.
Ha majd helyezze Bob, a név megy itt.
Charlie megy itt.
És így tovább lefelé ez az adat struktúrát.
>> Ez egy csodálatos adatstruktúra.
Miért?
Nos, mi a futási ideje behelyezése ember nevét ebbe a
adatstruktúra most?
Tekintettel arra, hogy ez a tábla megvalósul, Valóban, mint egy tömb.
Hát ez konstans id.
Ez sorrendben az egyik.
Miért?
>> Nos, hogyan lehet megállapítani, ahol Alice tartozik?
Akkor nézd meg melyik betű a nevét?
Az első.
És akkor oda, ha ez egy string, hogy csak nézte szöveg
konzol nulla.
Így a nulladik jellegét a húr.
Ez könnyű.
Mi volt, hogy a titkosítási feladat hete.
És majd ha egyszer tudja, hogy Alice betű tőkének, tudjuk kivonni
off 65 vagy a tőke A saját maga, hogy ad nekünk nulla.
Tehát most már tudjuk, hogy Alice tartozik a helyszínen nulla.
>> És mivel a mutatót az adatok szerkezet, valamilyen, mennyi ideig tart
akkor vigyél találni helyre nullára tömb?
Csak egy lépés, igaz ez konstans id azért, mert a véletlen elérésű mi
tervezett volt jellemző egy tömb.
Tehát röviden, kitalálni, mi az index Alice neve, amely, a
Ebben az esetben egy, vagy nézzük csak megoldani hogy a nullára, ahol B jelentése egy és C jelentése
két, kitalálni, hogy ki állandó idő.
Csak meg kell nézni az első betű, kitalálni, ahol a nulla egy
tömb is konstans id.
Szóval technikailag ez mint két lépést most.
De ez még mindig állandó.
Így hívják azt a nagy O egy, így már be Alice ebbe táblázat
állandó idő.
>> De persze én vagyok, hogy naiv, igaz?
Mi van, ha van egy Aaron az osztályban?
Vagy Alicia?
Vagy bármely más kezdődő nevek A. Hová megyünk, hogy
a személy, nem igaz?
Úgy értem, most már csak három az emberek az asztalra, így talán
meg kell oldania Aaron a helyszínen nulla egy kettő három.
>> Igen, tudtam hogy egy itt.
De aztán, ha megpróbáljuk beilleszteni a David ez a lista, hol David menni?
Most a rendszer elindul törés le, ugye?
Mert most David végül itt ha Aaron valóban itt.
És most ez az egész ötlet, hogy a tiszta adatszerkezet, amely ad nekünk
konstans idő beszúrások már nem állandó idő, mert muszáj
ellenőrzés, ó, fenébe, valaki már Alice helyét.
>> Hadd szonda a többi az adatok szerkezet, keres egy helyet, hogy
valaki, mint Aaron nevét.
És így is kezd hogy lineáris időt.
Sőt, ha most akarja találni a Aaron ebben adatstruktúra, és
ellenőrzés, és Aaron neve nincs itt.
Ideális esetben, akkor csak annyit, Aaron nem az adatszerkezetet.
De ha elkezd teret Aaron, ahol kellett volna a D
vagy E, akkor a legrosszabb esetben is ellenőrizni az egész adatstruktúra, a
az esetben hárul valami lineáris a méret az asztal.
>> Szóval minden rendben, én hozom a.
A probléma itt az, hogy volt 26 elemek ebben a tömbben.
Hadd változtatni.
Hoppá.
Hadd megváltoztatnunk, hogy elég, hogy a méret 26 összesen észre az alsó
index meg fog változni, hogy n mínusz 1.
Ha a 26 túlságosan kicsi az ember " nevet, mert van több ezer
nevét a világ, nézzük csak, hogy 100 vagy 1000 vagy 10000.
Nézzük csak lefoglalni sokkal több helyet.
>> Nos, ez nem feltétlenül csökken a valószínűsége, hogy nem lesz két
emberek kezdődő nevek A, és igen, akkor is megpróbálom, hogy egy
nevű helyen lévő nulla is.
Ők még mindig tart összeütközik, ami azt jelenti, hogy továbbra is szükség van a megoldás, hogy terjesszen
Alice és Áron és Alicia és más kezdődő nevek A máshol.
De milyen nagy probléma ez?
Mi a valószínűsége, hogy van ütközés adat
szerkezet, mint ez?
>> Nos, hadd - visszajövünk erre a kérdésre itt.
És nézd meg, hogy mi is oldja meg először.
Hadd húzza fel a javaslat itt.
Amit most leírt egy algoritmus, A heurisztikus nevű lineáris
szondázás amely, ha megpróbálta beilleszteni valami itt az adatok
szerkezet, amely az úgynevezett hash tábla, és nincs helye ott,
igazán szonda az adatstruktúra ellenőrzés, ez elérhető?
Vajon ez elérhető ez elérhető?
Ez elérhető?
És amikor végül az, hogy helyezze be a név, amelyet eredetileg
máshol az adott helyen.
De a legrosszabb esetben az egyetlen helyszínen lehet a legalján az adatok
szerkezet, a legvégén a tömbben.
>> Tehát lineáris szondázás, a legrosszabb esetben, hárul lineáris algoritmus, ahol
Áron ha történetesen be utolsó ebben adatstruktúra, talán
ütköznek az első helyen, de majd a végén a balszerencse a legvégén.
Tehát ez nem egy konstans idő szent grál számunkra.
Ez a megközelítés a behelyezése elemek egy adatstruktúra úgynevezett hash
táblázat nem úgy tűnik, hogy állandó idő legalábbis nem az általános esetben.
Ez ruházni valami lineáris.
>> Mi van, ha elhatározzuk ütközések Kicsit másképp?
Tehát itt egy kifinomultabb megközelítés, mi még mindig
úgynevezett hash tábla.
És hash, Mellesleg, mit Úgy értem, az index
Utaltam korábban.
A hash valami lehet úgy, mint egy ige.
>> Tehát, ha hash Alice egy név, a hash függvényt, hogy úgy mondjam,
vissza kell adnia egy számot.
Ebben az esetben nulla, ha tartozik a elhelyezkedés nulla, egy, ha ő tartozik a
helyen egy, és így tovább.
Szóval a hash függvényt eddig volt szuper egyszerű, csak nézte a
első betűje valaki nevét.
De egy hash függvényt veszi input néhány adat, a
string, int, mindegy.
És kiköpi általában egy számot.
És ez a szám az, ahol az adatok elem tartozik egy adatstruktúra
ismert itt, mint egy hash tábla.
>> Tehát csak ösztönösen, hogy ez a kicsit más kontextusban.
Ez valójában utal egy példa beleértve születésnapok, ahol
nem lehet kevesebb, mint 31 nap a hónapban.
De mi ez a személy úgy dönt, hogy teendő az ütközés?
Context már lenni, nem ütközése nevek, de az ütközést a születésnapok,
ha két ember azonos születésnapját Az október 2., például.
>> DIÁK: [hangtalan].
>> SPEAKER 1: Igen, itt van bevonását a kapcsolt listák.
Tehát úgy néz ki, egy kicsit másképp , mint ahogy azt korábban felhívta.
De úgy tűnik, hogy egy tömb a bal oldalon.
Ez az egyik index nélkül különösebb oka.
De ez még mindig egy tömb.
Ez egy sor mutató.
És minden egyes ilyen elemek mindegyike Ezekben a körökben vagy perjel - a perjel
képviselő null - mindegyik pointerek látszólag mutat
milyen adatokat szerkezet?
A láncolt lista.
>> Tehát most már képesek kemény kódot a programunk
a méret a táblázat.
Ebben az esetben tudjuk, soha nem több mint 31 nap egy hónapban.
Olyan nehéz, mint a kódolás értéke 31 ésszerű ebben az összefüggésben.
Keretében a nevek, kemény kódolás 26 nem ésszerűtlen emberek
csak megnevezések kezdődik, például, Az ábécé érintő át Z.
>> Tudjuk teletölteni őket be, hogy az adatok struktúra amíg, ha kap egy
ütközés, akkor ne tegye a neveket itt, azt gondolom, ahelyett, hogy ezen sejtek
nem vonósok magukat, de mutatókat, például, Alice.
És akkor Alice még egy mutató másik karakterrel kezdődő
A. És Bob valóban megy itt.
>> És ha van egy másik karakterrel kezdődő A B-ben végül ide.
És így az egyes elemeket a asztal két, ha tervezte ezt a
kicsit ügyesen -
gyerünk -
ha tervezte ezt egy kicsit ügyesen, most lesz egy adaptív adat
szerkezet, ahol nincs hard limit hogy hány elemet lehet beilleszteni
bele, mert ha van ütközés, ez rendben van.
Csak megy előre, és hozzáfűzi, hogy amit láttunk egy kicsit ezelőtt még
úgynevezett láncolt lista.
>> Nos, nézzük szünetet egy pillanatra.
Mi a valószínűsége, hogy egy ütközés az első helyen?
Rendben, lehet, hogy én mint gondoltam, talán Túl vagyok mérnöki ezt a problémát,
mert tudod, mit?
Igen, jöhet akár tetszőleges példák le a fejem tetején, mint a
Allison és Aaron, de a valóságban, adott egyenletes eloszlását
bemenet, hogy van néhány véletlenszerű betoldások egy adatstruktúra, ami igazán
a valószínűsége, hogy egy ütközés?
Nos kiderült, valójában szuper magas.
Hadd általánosítani ezt probléma, mint ez.
>> Tehát egy szoba n CS50 diákok, mi a valószínűsége, hogy legalább
két diák a szobában ugyanaz a születésnapja?
Tehát van mit. néhány hund -
200, 300 ember van itt, és számos száz ember otthon ma.
Tehát, ha akarta, hogy megkérdezzük magunktól, mi a valószínűsége, hogy két ember
ebben a szobában, azonos születésnapja, akkor ezt meg.
És azt állítják, valóban van két emberek azonos születésnapját.
>> Például valaki, aki van születésnapja ma?
Tegnap?
Holnap?
Rendben, olyan érzés, mintha megyek hogy kell ezt 363 vagy több olyan
alkalommal valóban kitalálni ha van egy ütközés.
Vagy csak ezt matematikailag nem unalmasan
ezt.
És javaslatot tesz a következő.
>> Tehát azt javaslom, hogy mi is modellezni valószínűsége a két ember, amelyek a
ugyanaz, mint a születésnapja valószínűsége 1 mínusz a valószínűsége, ha senkinek nincs
ugyanaz születésnapját.
Tehát, hogy ezt, és ez még csak a divatos módon írom ezt, mert a
első, aki a szobában, ő lehet bármilyen egyik lehetséges
Születésnap feltételezve 365 nap az évben, Elnézést kérek, hogy személyek
A február 29. születésnapját.
>> Tehát az első, aki ebben a szobában ingyenes hogy tetszőleges számú születésnapok
ki a 365 lehetőség, hogy a fogjuk csinálni, hogy 365 osztva 365,
amely az egyik.
A következő személy a szobában, ha a cél hogy elkerülje az ütközést, csak akkor
hogy ő születésnapja, hogyan különböző lehetséges napig?
364.
Tehát a második tag ez a kifejezés lényegében ezzel, hogy a matematika a számunkra
levonjuk le egy lehetséges nap.
, Majd a következő napon, a következő napon, a Másnap le a teljes számát
Az ember a szobában.
>> És ha akkor úgy, akkor mi a valószínűsége, nem a velük
egyedi születésnapok, de megint 1 mínusz hogy, amit kap egy kifejezés
, ami nagyon fancifully néz ki.
De ez sokkal érdekesebb nézni vizuálisan.
Ez egy olyan grafikon, ahol az x-tengely a száma, akik a szobában, a
számú születésnapokat.
Az y-tengelyen a valószínűsége, Egy ütközés, két ember
azonos születésnapját.
>> És a elvihető ez a görbe hogy amint kapsz, mint 40
diákok, akkor akár egy 90%-os valószínűséggel combinatorically két
ember, vagy több kellene ugyanaz születésnapját.
És ha egyszer eljut tetszik 58 ember számára közel 100%-a egy esélyt a két
ember a szobában megy, hogy a ugyanaz születésnapja, bár ott van
365 vagy 366 lehetséges vödör, és csak 58 ember a szobában.
Csak statisztikailag akkor valószínű, hogy kap ütközések, ami rövid
motiválja ezt a vitát.
Ez még akkor is, ha kap képzelet itt, és indul, amelyek ezeket a láncokat, mi még mindig
megy, hogy ütközések.
>> Ahhoz, hogy felveti a kérdést, hogy mi az a költsége a beszúrások és törlések
egy adat struktúra, mint ez?
Hát hadd javaslom -
és hadd menjek vissza a képernyő fölött Itt - ha még n elemek
listán, így ha próbálunk beilleszteni n eleme, és mi
összesen hány vödör?
Mondjuk 31 teljes vödör abban az esetben, születésnapok.
Mi a maximális hossza egy E láncok potenciálisan?
>> Ha ismét van 31 lehetséges születésnapja egy adott hónapban.
És mi csak összecsomósodása mindenki számára -
valójában ez egy hülye példa.
Csináljuk 26 helyett.
Tehát ha valóban az emberek, akiknek a neve Először A-tól Z-ig, ezáltal
us 26-lehetőségeket.
És mi egy adatstruktúra, mint a az, amit most láttam, ahol van
egy sor mutatók, amelyek mindegyike rámutat, hogy a láncolt lista, ahol a
első lista mindenki a neve Alice.
A második lista minden a karakterrel kezdődő A, kezdve
B-vel, és így tovább.
>> Mi várható hossza egyenként ezeket a listákat, ha azt feltételezzük, a szép tiszta
eloszlása ​​név A-tól Z-ig az egész adatstruktúra?
Van n ember a adatstruktúra osztva 26, ha ők szépen
szét az egész adatstruktúra.
Így a hossza minden egyes ilyen láncok n osztva 26.
De nagy O jelölés, mi ez?
Mi ez valójában?
Szóval ez tényleg csak n, igaz?
Mert már azt mondta a múltban, hogy pfuj akkor osszuk 26.
Igen, valójában gyorsabb.
De elméletileg ez nem alapvetően minden gyorsabb.
>> Tehát nem úgy tűnik, hogy olyan sokat közelebb a szent grál.
Valójában ez csak lineáris időben.
Heck, ezen a ponton, miért nem vagyunk csak használ egy hatalmas láncolt lista?
Miért nem csak használ egy nagy tömb tárolja a nevét
mindenki a szobában?
Nos, van még valami, vonzó egy hash tábla?
Van még valami meggyőző körülbelül egy adatstruktúra
hogy néz ki?
Ezt.
>> DIÁK: [hangtalan].
>> SPEAKER 1: Igen, és újra, ha ez csak a lineáris idő algoritmus, és a
lineáris idő adatstruktúra, miért nem csak tárolja mindenki nevét egy nagy
tömb, vagy egy nagy láncolt lista?
És ne tegyenek CS sokkal nehezebb mint amilyennek lennie kellene?
Mi vonzó ebben, még bár karcos ki?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Inszerciók nem?
Drága többé.
Így beszúrások potenciálisan még mindig állandó idő, akkor is, ha az adatok
szerkezet úgy néz ki, mint ez, egy sor mutatók, amelyek mindegyike mutat
potenciálisan láncolt lista.
Hogyan lehetne elérni állandó idő beillesztése a nevek?
Dobd az első, ugye?
>> Ha áldozatot design gól korábban, ahol szerettünk volna, hogy
mindenki nevét, például a válogatott, vagy az összes számot a színpadon sorrendje,
Feltételezzük, hogy van egy rendezetlen láncolt lista.
Ez csak a költségek számunkra egy vagy két lépésben, mint abban az esetben, Ben és Brian
korábban, hogy helyezzen be egy elemet a a lista elején.
Tehát, ha nem érdekel szétválogatja A kezdődő nevek A vagy az összes
A kezdődő nevek B, még mindig érdekében állandó idő behelyezés.
Most felnézett Alice vagy Bob vagy név általában még mit?
Ez elég nagy O n osztva 26, a Ideális esetben, ha mindenki egységesen
elosztott, ahol van annyi A. mint ahány Z, ami valószínűleg
irreális.
De ez még mindig lineáris.
>> De itt, mi jön vissza a pont aszimptotikus jelölés, hogy
elméletileg igaz.
De a valóságban, ha azt állítom, hogy a program nem valami 26-szer
gyorsabb, mint a tiéd, amelynek programjában fogsz, hogy inkább a?
Tiéd, vagy az enyém, ami 26-szer gyorsabb?
Reálisan a személy, akinek a 26 szer gyorsabb, még ha elméletileg
az algoritmusok futnak ugyanabban aszimptotikus futási ideje.
>> Hadd javasolni egy másik megoldás összesen.
És ha ez nem fúj a fejedben, kifutunk az adatszerkezeteket.
Szóval ez az a Trie -
milyen hülye név.
Jön a lekérdezések, és a szó van írva Trie t-r-i-e, mert az
Természetesen visszakeresés hangzik Trie.
De ez a történelem a szó Trie.
>> Tehát egy Trie valóban valamilyen fa, és ez is egy játék a szó.
És annak ellenére, hogy nem igazán látom ezzel a megjelenítés, a Trie egy
fa struktúrájú, mint a családfa egyik őse a tetején, és még sok
Az unokák és dédunokák a levelek alján.
De minden csomópont egy Trie egy tömb.
És ez egy sor - és gyerünk leegyszerűsíti egy pillanatra - ez egy
tömb, ebben az esetben, a méret 26, ahol a minden csomópont ismét tömb mérete
26, ahol a nulladik eleme, hogy Egy tömb képvisel, és az utolsó
elem minden ilyen array képvisel Z.
>> Tehát azt javaslom tehát, hogy ezek az adatok szerkezet, úgynevezett Trie, lehet
is használják tárolására szavakat.
Láttunk egy perce, hogy hogyan tudnánk tárolni szavakkal, vagy ebben az esetben nevek, és mi
korábban láttuk, hogyan lehet tárolni számokat, de ha arra összpontosítunk nevű vagy húrok
itt, észre, mi az érdekes.
Azt állítom, hogy a név Maxwell belsejében ez adatstruktúra.
Hol látod Maxwell?
>> DIÁK: [hangtalan].
>> SPEAKER 1: a bal oldalon.
Szóval, mi az érdekes az ezen adatok struktúra nem tárolja a
húr M-A-X-W-E-L-L backslash zérus, minden folyamatosak, mit csinál helyette
követi.
Ha ez egy Trie mint adatszerkezet, Minden amelynek csomópont ismét egy tömb,
és szeretné tárolni Maxwell, először index, így a gyökér csomópontot, így
beszélni, a legfelső csomópont, a helyszínen M, igaz, így
nagyjából a közepén.
Aztán onnan, kövesse a mutató egy gyermek csomópontok, hogy úgy mondjam.
Így a családfa értelemben kövesse lefelé.
És, hogy a vezető, hogy egy másik csomópont a bal oldalon van, ami
csak egy tömb.
>> És aztán, ha szeretné tárolni Maxwell, megtalálja a mutató, amely képviseli
A, amely az ezt itt.
Akkor menj a következő csomópontra.
És vegyük észre - ez az, amiért a kép egy kicsit megtévesztő -
ez a csomópont meg szuper apró.
De ahhoz, hogy a megfelelő e jelentése Y és Z. Ez csak a szerző a csonka
képet úgy, hogy valójában látni a dolgokat.
Egyébként ezt a képet lenne rendkívül széles.
Tehát most már index a helyre X, akkor W, E, majd L, majd L. Akkor mi
a kíváncsiság?
>> Nos, ha már ezt a fajta új hogy, hogyan kell tárolni a string a
adatstruktúra, még mindig szükség van, hogy lényegében ellenőrizze le az adatok
szerkezet egy szót itt ér véget.
Más szóval, minden egyes ilyen csomópontok valahogy meg kell emlékezni, hogy mi
tulajdonképpen követi az összes ilyen mutatók és így egy kicsit
morzsát alján itt ezen szerkezet, hogy jelezze M-A-X-W-E-L-L
sőt ez az adat struktúrában.
>> Így lehet, hogy ezt a következő.
Minden csomópont a képen már csak látta az egyik, egy sor mérete 27.
És ez most 27, mert o meg hat, akkor tényleg kapsz egy aposztróf,
így lehet nevek, mint O'Reilly és mások aposztróf.
De ugyanezt a gondolatot.
Minden egyes ilyen elemek array pont egy struct
csomópont, így csak egy csomópont.
Tehát ez nagyon emlékeztet a mi kapcsolt lista.
>> És akkor van egy logikai, amit majd hívás szó, ami csak lesz
igaz, ha a szó véget ér ezen a levél a fában.
Hatékonyan képviseli a kis háromszög láttunk egy perce.
Tehát, ha egy szót ér véget, hogy a csomópont fa, ez a szó a területen lesz igaz,
amely fogalmilag ki ellenőrzi, vagy mi ez a rajz háromszög, igen ott
szó itt.
>> Tehát ez egy Trie.
És most az a kérdés, hogy mi az a működési idő?
Ez nagy O n?
Van valami más?
Nos, ha még n nevek az adatok szerkezet, Maxwell, hogy csak az egyik
nekik, mi a futási ideje behelyezése vagy találni Maxwell?
Mi a működési idő beillesztése Maxwell?
Ha van n más nevek már az asztalra?
Igen?
>> DIÁK: [hangtalan].
>> SPEAKER 1: Igen, ez a hosszúság a név, ugye?
Tehát a-M-X-W-E-L-l, így úgy érzi, mint ez algoritmus nagy O hét.
Most, természetesen, a név hossza változó.
Lehet, hogy egy rövid nevet.
Lehet, hogy ez egy hosszabb nevet.
De mi a legfontosabb az, hogy ez egy állandó szám.
És lehet, hogy nem is állandó, De Isten, ha reálisan, a
szótár, ott valószínűleg néhány határ A betűk száma a
személy nevét az adott országban.
>> És így feltételezhetjük, hogy értéke egy konstans.
Nem tudom, mi az.
Ez valószínűleg nagyobb, mint azt hiszem, ez az.
Mert mindig van néhány sarok esetében egy őrült hosszú név.
Így nevezzük k, de ez még mindig egy állandó feltehetően, mert minden
név a világon, legalábbis egy adott országban, hogy a hosszú vagy
rövidebb, így állandó.
De amikor már mondott valamit, nagy O konstans érték, mi az
tényleg megfelel?
Ez tényleg ugyanaz azt mondta konstans id.
>> Most már olyan csalás, nem?
Mi olyan kihasználva néhány elmélet itt, azt mondani, hogy jó, sorrendje k
valójában csak annak az egy, és ez állandó időben.
De ez tényleg az.
Mivel a kulcs itt az, hogy betekintést ha még n neveket már a
adatstruktúra és betét Maxwell, az az összeg, időt vesz igénybe, hogy
be Maxwell egyáltalán érintett hogy milyen sokan
vannak az adatstruktúra?
Nem úgy tűnik, hogy.
Ha lenne egy milliárd több elemet erre Trie, majd helyezze Maxwell, a
ő egyáltalán érinti?
Nem.
És ez semmihez sem a nap adatok struktúrák láttunk eddig, ahol a
futási idejét az algoritmus teljesen független, hogy mennyi
cucc, vagy még nincs az, hogy az adatok szerkezetét.
>> És így ezzel nyújt Önnek most egy lehetőséget p szett hat, amely
Ismét járnak végrehajtási saját helyesírás-ellenőrző, olvasás 150000
szóval, hogyan lehet a legjobban tárolni, hogy nem feltétlenül nyilvánvaló.
És bár én törekedtem megtalálni a Szent Grál, én nem
azt állítják, hogy a Trie van.
Tény, hogy a hash tábla lehet nagyon jól bizonyítani, hogy sokkal hatékonyabb.
De ezek csak -
ez csak egy a tervezési döntések akkor meg kell tenni.
>> De a záró vegyük 50, vagy úgy másodperc, hogy egy kandikál, mi van
előre, a jövő héten, és azon túl is átmeneti ebből a parancssorból
világ, ha a C programok dolgokat web alapú és nyelvek, mint a PHP és a
JavaScript és az interneten is, protokollokat, mint a HTTP, amely akkor már
magától értetődőnek évek most, és gépelt legtöbb minden
nap, talán, vagy látott.
És kezdjük, hogy húzza vissza a réteg, ami az interneten.
És mi az a kód, amely alapja a mai eszközök.
Így 50 másodperc a teaser itt.
Adok Warriors a Net.
>> [VIDEÓ LEJÁTSZÁS]
>> -Jött egy üzenet.
A protokoll minden saját.
Azért jött, hogy a világ kegyetlen tűzfalak, nemtörődöm routerek, és a veszélyek sokkal
rosszabb, mint a halál.
Ő gyors.
Ő erős.
Ő TCPIP.
És van a címét.
Warriors a Net.
>> [END VIDEÓ LEJÁTSZÁS]
>> SPEAKER 1: Így az internet kell dolgozni a jövő héten.