[Musiikki soi]
>> DAVID MALAN: Tämä on CS50.
Ja tämä on sekä alku ja end-- kuten literally-- lähes loppuun
viikon kuusi.
>> Ajattelin jakaa hieman hauskaa tosiasia.
Olen vetänyt tämän ylös viimeisen lukukauden tietoja asetettu.
Muistatte ehkä, että pyydämme teitä jokaisessa p set muodossa, jos olet katsonut verkossa
tai jos olet osallistunut henkilökohtaisesti.
Ja tässä on tiedot.
Joten tänään oli hyvin ennustettavissa.
Mutta halusimme viettää hieman aikaa kanssasi kuitenkin.
Haluaisiko kukaan arveluihin, miksi tämä kuvaaja on niin jaggy, ylös alas, ylös alas,
niin johdonmukaisesti?
Mitä kukin huiput ja kaukalot ovat?
>> Yleisö: [kuulumaton]
DAVID MALAN: Todellakin.
Ja lisää hauskasti, Jumala varjelkoon, pidämme yksi luento perjantaina
alussa lukukauden, sitähän me nähdä tapahtuvan.
Joten tänään, me osallistumme vähän Lisätietoa tietorakenteita.
Ja antaa sinulle enemmän kiinteää mielenterveyden mallin ongelmia viisi,
joka on nyt pois.
Kirjoitusvirheitä, jossa, me käden tekstitiedosto noin 100000
plus Englanti sanoja, ja olet menossa on
selvittää, miten taitavasti ladata niitä muistiin, RAM, käyttäen joitakin tietoja
rakenne valintasi.
>> Nyt yksi tällaisten tietojen rakennetta voitaisiin olla, mutta luultavasti ei pitäisi olla,
melko yksinkertainen linkitetty lista, jonka otimme käyttöön viime kerralla.
Ja linkitetty lista oli ainakin yksi etu verrattuna array.
Mikä on yksi etu linkitetty lista luultavasti?
>> Yleisö: lisäys.
>> DAVID MALAN: lisäys.
Mitä tarkoitat?
>> Yleisö: missä tahansa Lista [kuultavissa].
>> DAVID MALAN: Hyvä.
Joten voit lisätä elementti missä Haluatko keskellä lista
ilman shuffle mitään, jonka solmimme, meidän lajittelu
keskusteluja, ei ole välttämättä hyvä asia,
koska se vie aikaa itse liikkumaan kaikki nämä ihmiset vasemmalle tai oikealle.
Ja niin on linkitetty lista, voit vain jakaa kanssa malloc, uusi solmu,
ja sitten päivittää pari pointers-- kaksi, kolme toimintaa max--
ja pystymme korttipaikkaan joku kaikkialle listaan.
>> Mitä muuta oli edullinen noin linkitetyn listan?
Joo?
>> Yleisö: [kuulumaton]
DAVID MALAN: Perfect.
Perfect.
Se on todella dynaaminen.
Ja että et ole syyllistyneet, etukäteen, jossain määrämittaisiksi
kimpale muistia, kuin olisit sen kanssa array, ylösalaisin joista
on, että voit jakaa solmut vain kysyntä käyttäen siten vain niin paljon tilaa
kuin todella tarvitset.
Toisin array, saatat vahingossa jakaa liian vähän.
Ja sitten se vain menee olla kipua niskassa
kohdentaa uudelleen uuteen isompi joukko, kopioida kaikki yli, vapaa vanha array,
ja sitten siirtyä yrityksestäsi.
Tai pahempaa, saatat jakaa tavalla enemmän muistia kuin todella tarvitset,
ja niin olet menossa on hyvin harvaan asutuilla array, niin sanotusti.
>> Joten liittyy luettelo, antaa sinulle nämä edut dynaamisuus ja joustavuus
kanssa lisäyksiä ja poistoja.
Mutta varmasti on oltava maksettu hinta.
Itse asiassa, yksi teemoista tutkitaan tietokilpailu nolla
oli pari kompromisseja olemme nähneet tähän mennessä.
Joten mitä maksettu hinta tai haittapuoli linkitetyn listan?
Joo.
>> Yleisö: Ei random access.
>> DAVID MALAN: o random access.
Mutta kuka välittää?
Random access ei kuulosta pakottavia.
>> Yleisö: [kuulumaton]
DAVID MALAN: Aivan.
Jos haluat olla tietty algorithm--
ja haluaisin todella ehdottaa Binäärihaku erityisesti, joka
on yksi olemme käyttäneet melko bit-- Jos sinulla ei ole satunnainen pääsy,
et voi tehdä näin yksinkertainen aritmeettinen löytää kuin keskimmäinen elementti
ja hyppää oikeutta siihen.
Voit sen sijaan on aloitettava ensimmäisestä elementti ja lineaarisesti etsi vasemmalta
oikealle, jos haluat löytää keski tai muita tekijöitä.
>> Yleisö: Se varmaan vie enemmän muistia.
>> DAVID MALAN: vaatii paljon muistia.
Missä on täydentävä maksaa tulevat muistiin?
>> Yleisö: [kuulumaton]
DAVID MALAN: Aivan.
Tässä tapauksessa täällä, meillä oli linkitetty lista kokonaislukuja,
ja silti me kaksinkertaistaa muistin määrä
Tarvitsemme mukaan myös niiden tallentamista viitteitä.
Nyt vähemmän iso juttu kuin sinun structs saada suurempi
ja olet ei tallenneta numero vaan ehkä opiskelija tai jokin muu esine.
Mutta kohta varmasti pysyy.
Ja niin useita toimintoja linkitettyihin luettelot kutsuttiin
oli iso O n- lineaarinen.
Asiat kuten asettamisen tai haku tai poistetaan, jos elementti
sattui olemaan aivan lopussa lista onko se lajitellaan tai ei.
>> Joskus saatat saada onnekas ja niin alarajat näiden toimintojen
voi olla vakio aikaa, jos olet aina katsot ensimmäinen elementti,
esimerkiksi.
Mutta loppujen lopuksi, me lupasimme saavuttaa Graalin
tietorakenteita, tai Joissakin approksimaatio,
Poiketen vakioaikaisia.
Voisimmeko löytää osia tai lisätä elementtejä tai poistaa elementit listasta?
Tulemme näkemään varsin pian.
Ja käy ilmi, että yksi mekanismien olemme
aio alkaa käyttää tänään, vuotuinen käyttö p asettaa viisi,
on oikeastaan ​​aika tuttu.
Esimerkiksi, jos tämä on nippu tentti kirjoja, joista kukin
on opiskelijan ensimmäinen ja sukunimi sitä,
ja minä noutaa ne lopussa tentti,
ja he ovat kaikki melko paljon satunnaisessa järjestyksessä,
ja haluamme edetä lajittelu näitä kokeita niin, että kun arvostellaan
se on vain paljon helpompaa ja nopeampi luovuttamaan ne takaisin ulos
opiskelijoille aakkosjärjestyksessä.
Mitä vaistosi olla varten kasa tentit näin?
>> No, jos olet kuten minä, olet voisi nähdä, että tämä on m,
joten aion tavallaan toteuttaa tämä, jos tämä on minun taulukko tai minun kerroksessa, jossa
Olen leviää asioita out-- tai minun array really--
Saatan laittaa kaikki Ms siellä.
Oh.
Tässä A., joten saatan laittaa Kuten täällä.
Oh.
Tässä toinen A. Aion laittaa, että tänne.
Tässä Z. Tässä on toinen M. Ja niin Voisin alkaa tehdä kasoittain näin.
Ja sitten ehkä menisin myöhemmin ja tavallaan hyvin nitpicky-ly Lajittele
yksittäiset paalut.
Mutta kohta on haluan tarkastella otossa, että olen kädellä
ja haluaisin tehdä joitakin lasketaan Päätös perustuu siihen, että tulo.
Jos se alkaa, laita se tuonne.
Jos se alkaa Z, laita se päälle siellä, ja kaikkea siltä väliltä.
>> Joten tämä on tekniikka, joka on yleisesti tunnettu hashing-- H-A-S-H--
mikä tarkoittaa yleensä ottaen niin tulo ja käyttää sitä panos laskea
arvo, yleensä määrä, ja että numero on indeksinä varastointi
kontti, kuten array.
Eli toisin sanoen, voisin olla tiivistefunktiota, kuten minä päähäni,
että jos näen jonkun nimi, joka alkaa,
Aion kartan nollaan päähäni.
Ja jos näen jonkun kanssa Z, olen menossa kartta, 25 päähäni
ja sitten laittaa sen osaksi viimeksi eniten kasaan.
>> Nyt, jos ajattelee ei aivoni mutta C-ohjelma, mitä numeroita voisi
voit luottaa saavuttaa saman tuloksen?
Toisin sanoen, jos oli ASCII-merkki,
miten voit määrittää mitä ämpäri laittaa sen?
Et luultavasti halua laita se ämpäriin 65, joka
olisi sama kuin tuolla ilman hyvää syytä.
Missä haluat laittaa kannalta sen ASCII-arvo?
Missä haluat tehdä sen ASCII arvo keksiä älykkäämpiä ämpäri
laittaa sen?
>> Yleisö: Miinus A.
>> DAVID MALAN: Joo.
Joten miinus tai miinus erityisesti 65, jos se on
pääoman A. Tai 98, jos se on pieniä.
Ja jotta voisimme hyvin yksinkertaisesti ja hyvin laskennallisesti,
laittaa jotain sankoon niin.
Joten se kääntyy pois me itse tehdä Tämän samoin vaikka tietokilpailuja.
>> Niin saatatte muistaa sinua ympyröity sinun opetus kaverin nimi kannessa.
Ja TF: n nimet järjestettiin näihin sarakkeisiin aakkosjärjestyksessä
hyvin, uskokaa tai älkää, kun kaikki 80 plus meistä
sai yhdessä muiden yö palkkaluokkaan, viimeinen askel lajitteluun prosessi
on hash tietokilpailuja isoon tilaa lattian [äänetön]
ja antaa kaikkien tietokilpailuja ulos täsmälleen siinä järjestyksessä niiden TF: n
nimet kannessa, koska niin se on paljon helpompaa meille
etsiä läpi käyttäen lineaarista etsiä tai jonkinlainen nokkeluutta
varten TF löytää hänen tai oppilaidensa tietokilpailuja.
>> Joten tämä ajatus hashing että näet on
melko voimakas on oikeastaan ​​aika arkipäiväinen ja erittäin intuitiivinen,
paljon kuin ehkä jakaa ja Conquer oli viikolla nolla.
I nopeasti eteenpäin hackathon pari vuotta sitten.
Tämä oli Zamyla ja pari muu henkilöstö tervehdys opiskelijoita
kuin he tulivat.
Ja meillä oli koko joukko taitto pöydät siellä nimilappuja.
Ja meillä oli nimilappuja järjestäytyneen kanssa kuten Kuten tuolla
ja ZS tuolla.
Ja niin yksi TF: iä erittäin taitavasti Kirjoitin tämän, koska ohjeet
päivä.
Ja viikolla 12 lukukauden tämän kaikki oli täysin järkevä ja kaikille
tiesi, mitä tehdä.
Mutta milloin olet jonossa samalla tavalla,
olet täytäntöönpanosta Sama ajatus on hash.
Joten virallistaa sitä vähän.
Tässä on joukko.
Se vetää hieman Laaja vain kuvata, visuaalisesti,
että voisimme laittaa jouset jotain tällaista.
Ja tämä joukko on selvästi koko 26 yhteensä.
Ja asia on nimeltään pöytä mielivaltaisesti.
Mutta tämä on vain taiteilijan luovutuksia mitä hajautustaulun voisi olla.
>> Niin hash table nyt on menossa olla korkeampi tietorakennetta.
Lopussa päivä olemme tulleet, että olet
voi toteuttaa tiiviste, joka on paljon, kuten check-in line
klo hackathon paljon kuin tämä taulukko käyttää lajitteluun tenttikirjat.
Mutta tiiviste on tavallaan tämä korkean tason
käsite, joka voisi käyttää array alla huppu toteuttaa se,
tai se voisi käyttää pituus luettelosta, tai jopa ehkä joitakin muita tietorakenteita.
Ja nyt se on theme-- ottaminen jotkut näistä keskeisistä aineosista
kuten array ja tämä rakennus Estä nyt on pitkä lista
ja nähdä, mitä muuta voimme rakentaa päälle ne, kuten ainesosat
osaksi resepti, tehdä enemmän ja enemmän mielenkiintoista ja hyödyllistä lopulliset tulokset.
>> Joten tiiviste voisimme toteuttaa sen
muistiin kuvallisesti näin, mutta Kuinka se voisi todella olla koodattu ylös?
No, ehkä yksinkertaisesti on tämä.
Jos kapasiteettia kaikilla lippikset, on vain Joissakin constant-- esimerkiksi 26,
26 kirjainta alphabet-- Saatan soittaa minun muuttuvan pöytä,
ja voisin väittää, että aion laita char tähtiä siellä, tai merkkijono.
Niin se on niin yksinkertaista kuin tämä, jos halua toteuttaa hash table.
Ja vielä, tämä on oikeastaan ​​vain joukko.
Mutta jälleen kerran, hash pöytä on nyt mitä me will
soita abstrakti tietotyyppi, joka on juuri eräänlainen käsitteellinen kerrospukeutuminen päälle
jotain arkisempi nyt haluaisin array.
>> Nyt, miten menemme noin ongelmien ratkaisemiseen?
No, aikaisemmin minulla oli ylellisyyttä ottaa tarpeeksi pöytätilaa täällä
niin että voisin laittaa tietokilpailuja tahansa halusin.
Niin voisi mennä täällä.
ZS voisi mennä täällä.
MS voisi mennä täällä.
Ja sitten minulla oli ylimääräistä tilaa.
Mutta tämä on vähän huijata oikeus nyt, koska tämä taulukko, jos olen todella
ajatellut sitä array, on vain tulee olemaan noin kiinteä koko.
>> Joten teknisesti, jos vedän jopa toisen opiskelijan tietokilpailu
ja katso, oi, tämä henkilö nimi alkaa myös,
Olen sellainen halua laittaa sen sinne.
Mutta heti kun laitoin sen sinne, jos Tämän taulukon todellakin edustaa joukko,
Aion olla ensisijaisia ​​tai clobbering kuka tämä opiskelijan tietokilpailu on.
Oikea?
Jos tämä on joukko, vain yksi asia voi mennä kussakin näistä soluista tai elementtejä.
Ja niin olen sellainen on poimia ja valita.
>> Nyt aikaisemmin olen sellainen huijattu ja teki tämän tai I
vain sellainen pinottu ne toistensa päälle.
Mutta se ei tule lentää koodin.
Joten jos voisin laittaa Toinen opiskelija, jonka nimi
on jos kaikki mitä oli on tämä käytettävissä pöytätilaa?
Ja olen käyttänyt kolme lähtö ja se Näyttää siltä, ​​että on vain muutama muu.
Mitä voisit tehdä?
Yleisö: [kuulumaton]
DAVID MALAN: Joo.
Ehkä haluan vain pitää asiat yksinkertaisina.
Oikea?
Se ei sovi, jos haluan laittaa sen.
Joten aion laittaa sen teknisesti jossa B menisi.
Nyt tietenkin olen alkanut maalata itseni nurkkaan.
Jos saan opiskelija jonka nimi on todella B,
Nyt B aiotaan siirtää hieman eteenpäin, niin voisi tapahtua, juu,
jos tämä on B, nyt se on mennä tänne.
>> Ja niin tämä hyvin nopeasti voisi muodostua ongelmalliseksi,
mutta se on tekniikka, joka todella kutsutaan lineaarinen tunnustelun
jolloin juuri harkita array olla pitkin linjaa.
Ja juuri sellainen anturi tai tarkastaa jokaisen saatavilla elementin
etsii käytettävissä paikan päällä.
Ja heti kun huomaat yksi, voit pudottaa sen sinne.
>> Nyt hinta on nyt maksettu Tämän ratkaisu on mitä?
Meillä on kiinteä koko array, ja kun asetan nimet
siihen, ainakin aluksi, mitä käyntiaika lisäys
laskemisesta opiskelijoiden tietokilpailuja oikeaan kauhat?
Big O mitä?
>> Yleisö: n.
DAVID MALAN: Kuulin ison O n.
Ei pidä paikkaansa.
Mutta me kiusata toisistaan miksi vain hetken.
Mitä muuta se voisi olla?
>> Yleisö: [kuulumaton]
DAVID MALAN: Ja anna minun tehdä se visuaalisesti.
Joten Oletetaan tämä on kirjain S.
>> Yleisö: Se on yksi.
DAVID MALAN: Se on yksi.
Oikea?
Tämä on joukko, joka tarkoittaa, että olemme random access.
Ja jos ajattelemme tämän nollaksi ja tämä 25,
ja ymmärrämme, että Voi, tässä on minun tulo S,
Voin varmasti muuntaa S, ASCII-merkki,
vastaavaksi määräksi nollan ja 25
ja sitten heti laita se minne se kuuluu.
>> Mutta tietenkin, heti kun pääsen toinen henkilö jonka nimi on A tai B tai C
lopulta, jos olen käyttänyt lineaarinen hyvää minun ratkaisu,
käyntiaika lisäys pahimmassa tapauksessa
on todella menossa hajauttaa, mitä?
Ja en kuullut sitä täällä oikein varhain.
Yleisö: [kuulumaton]
DAVID MALAN: Niin se on n todellakin kerran sinulla on riittävän suuri tietokokonaisuus.
Niin, toisaalta, jos matriisisi on tarpeeksi iso
ja tietosi on niukkaa riitä, saat tämän kauniin vakioaikaisia.
Mutta heti kun alkaa yhä enemmän ja enemmän elementtejä,
ja juuri tilastollisesti saat enemmän ihmisiä kirjaimella
Nimensä tai kirjain B, se olisi voinut olla
hajauttaa joksikin lineaarinen.
Joten ei ole aivan täydellinen.
Joten me voisimme tehdä paremmin?
>> No, mikä oli meidän ratkaisu ennen kun me
haluavat olla enemmän dynamiikkaa kuin jotain array sallittua?
Yleisö: [kuulumaton]
DAVID MALAN: Mitä me esitellä?
Joo.
Joten linkitetty lista.
No, katsotaanpa mitä liittyy lista voisi tehdä meille sijaan.
No, minäpä ehdotan, että piirtää kuvaa seuraavasti.
Nyt tämä on erilainen kuva esimerkki
peräisin eri tekstiä, itse asiassa, että on todellisuudessa käyttävät taulukon koko 31.
Ja tämä kirjailija yksinkertaisesti päätti hash jouset
ei perustu henkilön nimet, vaan perustuu niiden syntymäpäiviä.
Riippumatta kuukauden, he tajunnut jos olet syntynyt ensimmäinen kuukausi
tai 31. kuukausi, kirjailija tulee hash perustuu tähän arvoon,
levittämiseksi nimiä ulos vähän enemmän kuin vain 26 paikkoja voisi mahdollistaa.
Ja ehkä se on hieman yhtenäisempi kuin menossa aakkosina,
koska tietenkin on luultavasti enemmän ihmisiä maailmassa nimet
jotka alkavat kuin varmasti joitakin muita aakkosten kirjainta.
Joten ehkä tämä on hieman yhtenäisempi, olettaen
tasainen jakauma vauvojen yli kuukausi.
>> Mutta, tietenkin, tämä on vielä epätäydellinen.
Oikea?
Meillä oli törmäyksiä.
Useita ihmisiä tässä tietorakenne ovat edelleen
joilla on sama syntymäaika ainakin olet riippumatta kuukaudessa.
Mutta mitä on kirjailija tehnyt?
No, näyttää siltä, ​​että meillä on joukko vasemmalla puolella piirretty pystysuunnassa,
mutta se on vain taiteilijan luovutuksia.
Sillä ei ole väliä mihin suuntaan piirtää array, se on silti array.
Mikä on tämä joukko ilmeisesti?
>> Yleisö: linkitetty lista.
>> DAVID MALAN: Joo.
Se näyttää siltä kuin se on joukko linkitetty lista.
Joten jälleen, että tässä vaiheessa järjestä käyttää näitä tietorakenteiden nyt
ainesosina lisää mielenkiintoisia ratkaisuja,
voit ehdottomasti ottaa perusoikeuksien, kuten array,
ja sitten ottaa jotain lisää mielenkiintoinen kuten linkitetyn listan
ja jopa yhdistää ne vielä mielenkiintoisempaa tietorakenne.
Ja todellakin, tämäkin olisi kutsua tiiviste,
jolloin matriisi on todella tiiviste,
mutta että tiiviste on ketjut, niin sanotusti,
joka voi kasvaa tai kutistua perusteella alkioiden lukumäärä, jonka haluat lisätä.
>> Nyt, vastaavasti, mikä on käyntiaika nyt?
Jos haluan lisätä joku jonka syntymäpäivä on 31. lokakuuta
mistä hän mennä?
Selvä.
Alareunaan, jossa lukee 31.
Ja se on täydellinen.
Se oli jatkuvaa aikaa.
Mutta mitä jos me löytää joku muu jonka syntymäpäivä on, katsotaanpa,
Lokakuu, marraskuu, 31 joulukuu?
Missä hän aikoo mennä?
Sama juttu.
Kaksivaiheinen kuitenkin.
Se on jatkuvaa, vaikka ei ole sitä?
Selvä.
Tällä hetkellä se on.
Mutta yleisessä tapauksessa, enemmän ihmisiä lisäämme,
toden- näköisesti, olemme menossa saada enemmän ja enemmän törmäyksiä.
>> Nyt tämä on vähän parempi, koska se on teknisesti
Nyt ketjut voisi olla Pahimmassa tapauksessa kuinka kauan?
Jos asetan n ihmiset tähän lisää hienostunut tietorakenne, n ihmiset,
pahimmassa tapauksessa se tulee olemaan n.
Miksi?
>> Yleisö: Koska jos kaikki on sama syntymäpäivä,
he tulevat olemaan yksi rivi.
DAVID MALAN: Perfect.
Se saattaa olla hieman keinotekoinen, mutta todella pahimmassa tapauksessa
jos kaikilla on sama syntymäpäivä, antanut tulot sinulla on,
olet menossa on massiivisesti pitkä ketju.
Ja niin, voisi kutsua tiiviste, mutta oikeastaan ​​se on
vain massiivinen linkitetyn listan kanssa paljon hukkaan tilaa.
Mutta yleensä, jos oletamme, että ainakin syntymäpäivät ovat uniform--
ja se ei todennäköisesti ole.
Teen että ylös.
Mutta jos oletamme, sillä vuoksi keskustelu
että ne ovat, niin teoriassa, jos tämä on pystysuora edustus
array, hyvin sitten toivottavasti olet menossa ketjuja, jotka ovat, tiedät,
suunnilleen sama pituus, jossa kukin Näiden edustaa kuukauden päivää.
>> Nyt jos on 31 päivää kuukaudessa, kun taas se tarkoittaa, että minun käyntiaika todella
on iso O n yli 31, mikä tuntuu paremmalta kuin lineaarinen.
Mutta mikä oli yksi sitoumukset pari viikkoa
sitten kun se tuli ilmaisemiseen ajoaika algoritmi?
Vain vain katsoa korkean asteen termi.
Oikea?
31 on ehdottomasti hyödyllistä.
Mutta tämä on silti iso O n.
Mutta yksi teemoista Ongelman asettaa viisi
tulee olla tunnustavat, että ehdottomasti,
asymptoottisesti, teoreettisesti tämä tietorakenne
ei ole parempi kuin vain yksi massiivinen linkitetty lista.
Ja todellakin, pahimmassa tapauksessa, tämä tiiviste voisi siirtää tuohon.
>> Mutta todellisessa maailmassa, jossa meille ihmisille että omat Macit tai PC tai mitä tahansa
ja ovat käynnissä reaalimaailman ohjelmisto reaalimaailman data,
mikä algoritmi aiotte mieluummin?
Joka kestää pää vaiheiden tai joka kestää n jaettuna 31 vaiheet
löytää joitakin osa tiedoista tai etsiä joitakin tietoja?
Tarkoitan, ehdottomasti 31 merkkeihin ero todellisessa maailmassa.
Se on 31 kertaa nopeampi.
Ja me ihmiset olemme varmasti menossa arvostaa sitä.
>> Joten ymmärtää kahtiajako siellä välillä todella
puhumme asioista teoreettisesti ja asymptoottisesti joka varmasti
on arvoa olemme nähneet, mutta todellisessa maailmassa,
Jos välität vain tekemällä ihmisen onnelliseksi yleisiä tuloa,
saatat hyvinkin haluta hyväksyä että, kyllä, tämä on lineaarinen,
mutta se on 31 kertaa nopeampi kuin lineaarinen voisi olla.
Ja vielä parempaa, meillä ei vain tarvitse tehdä jotain mielivaltaista, kuten syntymäpäivä,
voisimme viettää hieman enemmän aikaa ja nokkeluutta
ja miettiä, mitä voisimme tehdä, annetaan henkilön nimi ja ehkä
niiden syntymäaika yhdistää nämä ainesosat selvittää jotain
että on todella enemmän yhtenäinen ja vähemmän jaggy,
niin sanotusti kuin tämä kuva Tällä hetkellä ehdottaa, että se voisi olla.
Miten voisimme toteuttaa tämän koodin?
No, minäpä ehdotan, että vain lainata syntaksin me olet
käytetty pari kertaa näin pitkälle.
Ja aion määritellä solmu, joka taas
on yleisnimi vain joitakin kontti joidenkin tietojen rakenne.
Aion ehdottaa, että merkkijono on menossa sinne.
Mutta me aiomme aloitat ne apupyörät pois nyt.
>> Ei enää CS50 kirjasto todella, jos et halua
käyttää sitä oman lopullisen hanke, joka on hieno,
mutta nyt olemme menossa vetämään takaisin verho ja sanovat, että se on vain char tähti.
Joten sana siellä tulee olemaan henkilön nimestä.
Ja nyt minulla on linkki Tässä seuraavalle solmulle
niin, että nämä ovat kukin solmuista
ketjussa, mahdollisesti, linkitetyn listan.
>> Ja nyt miten voin julistaa tiiviste itse?
Miten julistan koko rakenne?
No, oikeastaan, aivan kuten käytin osoitin vain ensimmäinen osa listasta
ennen, samalla voin vain sanoa Tarvitsen vain joukko osoittimia
toteuttaa tätä koko tiiviste.
Aion olla array kutsutaan pöydän tiiviste.
Se tulee olla koko kapasiteetin.
Se, miten monta elementtiä mahtuu siihen.
Ja jokainen niistä tässä array tulee olemaan solmu tähti.
Miksi?
No, kohti tätä kuvaa, mitä olen täytäntöönpanosta tiiviste kuin
tehokkaasti alussa on vain Tämän array että olemme vetää pystysuoraan,
jokainen jonka neliöt edustaa osoitin.
Että ne, jotka ovat viiltää niiden kautta ovat vain null.
Ja ne, jotka ovat nuolet menossa oikeaan
ovat todellisia viitteitä todellinen solmuja, ergo alku liittyy luettelo.
>> Joten tässä sitten on, kuinka voisimme toteuttaa tiiviste, joka
toteuttaa erillinen ketjutus.
Nyt me voisimme tehdä paremmin?
Okei Lupasin viime kerralla, että voisimme saavuttaa vakioaikaisia.
Ja olen sellainen annoin sinulle vakio aikaa täällä,
mutta sanoi sitten ei oikeastaan vakio aikaa, koska se on edelleen
riippuvainen koko useita tekijöitä
olet kautta ne tietorakenteen.
Mutta kai me teimme tämän.
Anna minun mennä takaisin ruudun tänne.
Saanen myös heijastaa tätä täällä, kirkas näyttö, ja kai tein tämän.
Kai halusin lisätä nimen Daven on minun tietorakenne.
>> Joten haluan lisätä merkkijono Daven osaksi tietorakennetta.
Mitä jos en käytä tiiviste, mutta käytän
jotain, joka on enemmän puumainen kuten sukupuu, jossa
sinulla on root top ja sitten solmut ja lehdet
jotka menevät alaspäin ja ulospäin.
Oletetaan sitten, että minä haluat lisätä Daven n
siitä, mitä on tällä hetkellä tyhjä lista.
Aion tehdä seuraavaa: olen luomassa solmuun tässä perheessä
puumainen tietorakenne, joka näyttää vähän kuin tämä, joista kukin
suorakaide on, sanokaamme, nyt 26 elementtiä sitä.
Ja kukin soluista Tässä joukko on menossa
edustamaan kirjeen aakkoset.
>> Erityisesti aion kohdella tämä on, sitten B, sitten C, sitten D,
tämä yksi täällä.
Joten tämä tulee tehokkaasti edustaa kirjain D.
Vaan lisätä kaikki Daven n nimeä en täytyy tehdä hieman enemmän.
Joten olen ensin menossa hash, niin sanotusti.
Olen menossa katsomaan ensimmäinen kirjain vuonna Daven n, joka on ilmeisesti D,
ja aion jakaa solmu, joka näyttää
kuten this-- iso suorakulmio iso mahtuakseen koko aakkoset.
>> Nyt D on tehty.
Nyt A. D-A-V-E-N on tavoite.
Joten nyt, mitä aion tehdä, on tämä.
Heti kun aloin D huomautus ei ole osoitin siellä.
Se on roskaa arvot tällä hetkellä, tai voisin alustaa sen nollaamaan.
Mutta haluan pysyä menossa tämä ajatus rakentaa puun.
Sallikaa minun jakaa toinen näistä solmuja, jotka on 26 elementtejä sitä.
>> Ja tiedätkö mitä?
Jos tämä on vain solmu muistiin, että Olen luotu malloc käyttäen struct
kuten tulemme pian nähdä, Aion tehdä this--
Aion piirretään nuoli asia, joka edusti D alas
tähän uuteen solmuun.
Ja nyt, ensimmäistä seuraavaksi kirje Daven nimi,
V-- D-A-V-- aion mennä eteenpäin ja vetää toisen solmun näin,
jolloin, V-elementit tässä, joka me piirtää instance-- oho.
Emme vetää siellä.
Se tulee menemään täällä.
>> Sitten me aiomme pitävät tätä V.
Ja sitten täällä aiomme indeksi alas V mitä me harkitsemme E.
Ja sitten täältä me tulemme go on yksi näistä solmuista täällä.
Ja nyt meillä on kysymys vastata.
Minun täytyy jotenkin osoittaa, että olemme lopussa merkkijonon Daven.
Joten voisin vain jättää sitä null.
>> Mutta mitä jos meillä on Daven n Koko nimi myös, mikä
on, kuten olemme sanoneet, Davenport?
Joten mitä jos Daven on todella alimerkkijono,
etuliite paljon pidempi jono?
Emme voi vain pysyvästi sano mitään ei tapahdu
mennä sinne, koska emme voineet älä laita sana kuten Davenport
tähän tietorakenne
>> Joten mitä voisimme tehdä sen sijaan on rinnastaa nämä elementit
niin ehkä on kaksi Sisällä niistä.
Yksi on osoitin, todellakin, kuten olen tehnyt.
Joten jokainen näistä laatikoista ei ole vain yksi solu.
Mutta mitä jos alkuun one-- pohja oman
olemaan nolla, koska ei ole Davenport vielä.
Mitä jos ylin On joitakin erityisiä arvoa?
Ja se tulee olemaan hieman vaikea tehdä se tämän koon.
Mutta kai se on vain valintamerkki.
Tarkista.
D-A-V-E-N on merkkijono Tässä tietorakenne.
>> Samaan aikaan, jos minulla olisi enemmän tilaa täällä, voisin tehdä P-O-R-T,
ja voisin laittaa Mistä solmun että on T-kirjain aivan lopussa.
Joten tämä on massiivisesti monimutkainen näköinen tietorakenne.
Ja minun käsiala ei tietenkään auta.
Mutta jos halusin lisätä jotain muu, miettiä, mitä tekisimme.
Jos haluaisimme asetti Daavidin, olimme noudattaa samaa logiikkaa, D-A-V,
mutta nyt haluaisin huomauttaa seuraavassa elementti ei E, vaan I D.
Joten siellä tulee olemaan lisää solmuja tässä puussa.
Aiomme olla puhelu malloc enemmän.
Mutta en halua tehdä täydellinen sotku tätä kuvaa.
Joten sen sijaan tarkastellaan yhdessä joka on ollut esiformuloituja
Nytkin ei piste, piste, pisteitä, mutta vain lyhennettynä paneelit.
Mutta kukin solmuista tässä puussa täällä
edustaa samaa thing-- array Ray koosta 26.
>> Tai jos haluamme olla todella oikea nyt, mitä
Jos jonkun nimi heittomerkki, katsotaanpa
olettaa, että jokainen solmu todella on kuten 27 indeksit se, ei vain 26.
Joten tämä nyt tulee olemaan data rakennetta kutsutaan trie-- T-R-I-E.
Trien, joka on oletettavasti historiallisesti nokkela nimi puu
optimoituna haku, joka tietenkin,
kirjoitetaan I-E, joten se on trie.
Mutta se on historiaa trien.
>> Joten trie on tämä puumainen tiedot rakenne kuten sukupuu
että lopulta käyttäytyy niin.
Ja tässä on vain yksi esimerkki koko joukko muita ihmisten nimet.
Mutta kysymys nyt käsillä on mitä on
saimme ottamalla käyttöön luultavasti enemmän monimutkainen tietorakenne, ja yksi,
rehellisesti, joka käyttää paljon muistia.
>> Sillä vaikka, Tällä hetkellä olen vain
käyttäen D's osoitin ja Ja V ja Es: n ja NS,
En tuhlaa pahus paljon muistia.
Mutta missä vietän yhden resurssin, Minulla on tapana tehdä saada takaisin toiseen.
Joten jos vietän enemmän tilaa, mikä on luultavasti toivoa?
Että vietän vähemmän mitä?
Yleisö: Vähemmän aikaa.
DAVID MALAN: Time.
Nyt miksi se mahtaa olla?
No, mikä on lisäys ajan, mitattuna iso O nyt
nimen, kuten Daven tai Davenport tai David?
No, Daven oli viisi vaihetta.
Davenport olisi yhdeksän vaiheet, niin se olisi muutaman askeleen.
David olisi viisi askelta samoin.
Joten ne ovat konkreettisia numeroita, mutta varmasti siellä on
yläraja pituus jonkun nimi.
Ja todellakin, että ongelma sarjaa viiden erittely,
aiomme ehdottaa että se on jotain
joka on 40-joidenkin outoa merkkiä.
>> Realistisesti, kukaan ei ole äärettömän pitkä nimi,
joka on sanoa, että pituus nimi tai merkkijonon pituuden voisimme
on tietty tila rakenne on luultavasti mitä?
Se on vakio.
Oikea?
Se voi olla iso vakio kuten 40-jotain, mutta se on vakio.
Ja se ei ole riippuvuutta, kuinka monta muut nimet ovat tässä tietorakenne.
Toisin sanoen, jos I halusi nyt lisätä
Colton tai Gabriel tai Rob tai Zamyla tai Alison tai Belinda tai muita nimiä
Sen henkilöstön tähän tiedot rakenne, on käyntiaika
lisäämällä muita nimiä olemaan ollenkaan vaikuttanut
kuinka monet muut tekijät ovat datarakenteessa jo?
Se ei ole.
Oikea?
Koska olemme tehokkaasti käyttäen Tämän monikerroksinen tiiviste.
Ja ajoaika Jonkin näistä toimista
ei ole riippuvainen siitä lukumäärästä elementtejä, jotka ovat tietorakenteen
tai jotka ovat lopulta menossa olla tietorakenteen,
mutta pituudesta, mitä erityisesti?
>> Merkkijono on Lisätään, joka ei tee
Tämän asymptoottisesti vakio time-- iso O yhden.
Ja rehellisesti, juuri reaalimaailmassa, tämä
tarkoittaa lisäämällä Daven nimi vie kuten viisi askelta, tai Davenport yhdeksän
vaiheet, tai David viisi vaihetta.
Se on tosi pieni käynnissä kertaa.
Ja todellakin, se on hyvin hyvä asia, varsinkin kun
se ei ole riippuvainen koko elementtien määrä siellä.
Joten miten voisimme toteuttaa tämän Tällainen rakenne koodin?
Se on hieman enemmän monimutkainen, mutta silti se on
vain soveltaminen perusrakenneosia.
Aion uudelleen meille solmu seuraavasti:
bool kutsui word-- ja tämän voisi kutsua mitään.
Mutta bool edustaa mitä piirsin niin valintamerkki.
Kyllä.
Tämä on loppuun merkkijonon Tässä tietorakenne.
>> Ja, tietenkin, solmu tähti siellä viittaa lapsiin.
Ja todellakin, aivan kuten sukupuu, voit
harkitsisi solmut joita roikkui
pohjan joidenkin vanhemman elementti olla lapsia.
Ja niin lapset on menossa olla joukko 27, 27 yksi
vain vointia heittomerkki.
Aiomme järjestää on erikoistapaus, joka.
Joten voit olla tiettyjä nimet heittomerkit.
Ehkä jopa Yhdysviivalla mennä sinne, mutta sinun
nähdä p set 5 me vain välitä kirjeistä ja heittomerkit.
>> Ja sitten miten te edustatte tietorakenne itse?
Miten te edustatte root Tämän trie, niin sanoakseni?
No, aivan kuten linkitetyn listan, voit täytyy osoitin ensimmäiseen elementtiin.
Kanssa trie sinun tarvitsee vain yhden osoitin juuri tämän trie.
Ja sieltä voit hash tiesi alas syvemmälle ja syvemmälle
joka toinen solmun rakenteessa.
Joten yksinkertaisesti tämän voi me edustamme, että struct.
>> Nyt Meanwhile-- Voi kysymys.
>> Yleisö: Mikä bool sana?
>> DAVID MALAN: Bool sana on juuri tämä C inkarnaatio
mitä kuvasin tähän kohtaan täällä, kun
Aloitin jakamalla kunkin array elementtejä kahteen osaan.
Yksi on osoitin seuraavaan solmuun.
Muiden on oltava jotain valintaruutu
sanoa kyllä, siellä Sana Daven että loppuu tähän,
koska emme halua, tällä hetkellä, Dave.
>> Vaikka Dave tulee olemaan oikeutettu sana, hän ei ole trie
vielä.
Ja D ei ole sana.
Ja D-ei ole sana tai nimi.
Joten valintamerkki osoittaa vain, kun olet
osuma tämä solmu on edellinen polku merkkiä
todella merkkijono, joka olet lisännyt.
Niin, että kaikki bool siellä tekee meille.
>> Muita kysymyksiä yrittää?
Joo.
>> Yleisö: Mikä on päällekkäisyyttä?
Mitä jos sinulla on Dave ja Daven?
DAVID MALAN: Perfect.
Mitä jos sinulla on Dave ja Daven?
Jos siis lisätä, sanovat lempinimi, varten David-- Dave-- D-V-E?
Tämä on oikeastaan ​​erittäin yksinkertainen.
Joten me vain vie neljä vaihetta.
D-A-V-E. Ja mitä minun täytyy tehdä, kun osuin että neljäs solmu?
Juuri menossa tarkistaa.
Olemme jo hyvä mennä.
Tehty.
Neljä vaihetta.
Vakioaikaisia ​​asymptoottisesti.
Ja nyt olemme ilmoittaneet, että molemmat Dave ja Daven ovat merkkijonoja rakenteen.
Joten ei ole ongelma.
Ja huomaa, miten läsnäolo on Daven ei selvinnyt
ottaa enempää aikaa tai vähemmän aikaa Dave ja päinvastoin.
>> Joten mitä muuta voimme nyt tehdä?
Olemme käyttäneet tätä metafora ennen tarjottimia edustaa jotain.
Mutta näyttää siltä, ​​että pino tarjottimet on oikeastaan
demonstratiivinen toisen abstraktien tietojen type-- korkeamman tason datarakenteen
että lopussa päivä on juuri kuten array tai linkitetty lista
tai jotain arkisempi.
Mutta se on enemmän mielenkiintoista käsitteellinen käsite.
Pino, kuten nämä Lokeroiden täällä Mather,
kutsutaan yleensä vain that-- pino.
>> Ja tämän tyyppisen tietorakenteen sinulla on kaksi operations--
sinulla on yksi nimeltään push lisäämällä jotain pino,
kuin laittaisi toiseen lokeroon takaisin pinon päälle.
Ja sitten pop, mikä tarkoittaa, ottaa päällimmäinen lokero pois.
Mutta mitä näppäintä noin pino on, että se sai tämän utelias ominaisuus.
Kuten ruokasali henkilökunta järjestämällä tarjottimet seuraavan aterian,
mitä tulee olemaan totta, miten opiskelijat
vuorovaikutuksessa tämän datan rakenne?
Yleisö: He aikovat pop kertaluonteinen.
DAVID MALAN: He aikovat pop kertaluonteinen, toivottavasti alkuun.
Muuten se on vain typerää mennä pohjaan.
Oikea?
Tietorakenne ei oikeastaan ​​salli voit napata pohjalevy ainakin
helposti.
Joten on tämä kummallinen omaisuutta pino
että viimeinen erä on olemaan ensimmäinen ulos.
Ja tietotekniikan tutkijoita soittaa Tämän LIFO-- last in, first out.
Ja se todella ei ole mielenkiintoisia sovelluksia.
Se ei ole välttämättä yhtä selvää kuin jotkut toiset, mutta se voi todellakin olla hyödyllistä,
ja se voi todellakin toteuttaa pari eri tavoin.
>> Niin yksi, ja itse asiassa, anna minua ei sukeltaa tuohon.
Tehdään tämä sijaan.
Katsotaanpa yksi, joka on melkein Sama idea, mutta se on vähän oikeudenmukaisempaa.
Oikea?
Jos olet yksi näistä fani poikia tai tytöt, jotka todella tykkää Applen tuotteita
ja heräsin klo 03:00 riviin jossain myymälässä
saada uusinta iPhone, sinun ehkä jonottivat näin.
>> Nyt jonossa on erittäin tarkoituksella nimetty.
Se on linja, koska siellä Joissakin oikeudenmukaisuus sitä.
Oikea?
Se olisi eräänlainen imi, jos olet sai siellä ensin Apple Storessa
mutta olet tehokkaasti alimmainen lokero koska Applen työntekijöille sitten
pop viimeinen henkilö, joka itse saanut linjassa.
Niin pinot ja jonot, vaikka toiminnallisesti ne ovat eräänlainen same--
se on vain tämä kokoelma resursseja, jotka on
tulee kasvamaan ja shrink-- siellä Tämän oikeudenmukaisuuden näkökulma siihen,
ainakin todellisessa maailmassa, jossa toiminnot liikut
ovat täysin erilaiset.
Stack-- jono rather-- sanotaan
kaksi operaatiota: n jono ja d jono.
Tai voit soittaa heille mikä tahansa joukko asioita.
Mutta haluat vain kaapata ajatus, että yksi on lisännyt
ja yksi on lopulta vähentämällä.
>> Nyt alla huppu, sekä pino ja jono voitaisiin toteuttaa miten?
Emme aio mennä koodi sitä, koska korkeamman tason
Ajatus on tavallaan selvempi.
Tarkoitan, mitä ihmiset tekevät?
Jos minä olen ensimmäinen henkilö Apple Tallentaa ja tämä on etuovi,
Tiedätkö, aion seistä täällä.
Ja seuraavan henkilön menossa seistä täällä.
Niin mitä tietorakenne otollisia jonossa?
>> Yleisö: jono.
DAVID MALAN: No, jono.
Toki.
Mitä muuta?
>> Yleisö: linkitetty lista.
>> DAVID MALAN: liittyy Listassa voisi toteuttaa.
Ja linkitetty lista on mukavaa, koska silloin se voi kasvaa mielivaltaisesti pitkiä verrattuna
että on joitakin kiinteitä numero ihmisiä myymälässä.
Mutta ehkä kiinteä määrä paikkoja on oikeutettua.
Koska jos ne vain ovat, kuten 20 iPhonet ensimmäisenä päivänä, ehkä
ne tarvitsee vain taulukon koko 20 edustaa jonoa, joka
on vain sanoa nyt, kun alamme keskustella näistä että suurempia ongelmia,
voit toteuttaa sen vuonna monin tavoin.
Ja on luultavasti juuri menossa olla kaupan pois ja ajallisesti
tai vain oman koodin monimutkaisuutta.
>> Entä pino?
No, pino, olemme nähneet liian voisi vain olla näitä lokeroita.
Ja voisitte toteuttaa tämän array.
Mutta jossain vaiheessa jos käytät array, mitä tulee tapahtumaan lokerot
yrität laittaa alas?
Selvä.
Olet vain menossa voi mennä niin korkea.
Ja mielestäni Mather he todella upotettu että aukko.
Niin tosiaan, se on melkein kuten Mather käyttää
joukko kiinteitä koko, koska voit vain
sovittaa niin monta lokeroa että aukko seinä alhaalla ihmisten polvet.
Ja jotta voisi olla sanotaan olevan taulukon,
mutta voisimme varmasti toteuttaa että yleisemmin linkitetty lista.
>> No, entä toinen tietorakenne?
Saanen vetää yksi muu visuaalinen täällä.
Jotain Entäs tämä yksi täällä?
Miksi se voisi olla hyödyllistä ole jotain niin hieno kuin trie, joka
näimme oli näitä hyvin laaja solmuja, joista kukin on joukko?
Mutta mitä jos teemme jotain enemmän yksinkertaisesti, kuten vanha koulu sukupuu,
joiden kunkin solmun täällä on vain numeron tallentamisesta.
Sen sijaan, että nimi tai jälkeläinen on vain numeron tallentamisesta näin.
>> No, slangia, jota käytämme tietorakenteita on sekä yrittää
ja puita, missä trien, jälleen, on vain yksi, jonka solmut ovat paneelit,
on silti mitä voisi käyttää vuodesta alakoulussa
kun olet tehnyt perhe tree-- lehdet ja juuren
puun ja lapset vanhemman ja sisarukset sen.
Ja voisimme toteuttaa puu, esimerkiksi, niin yksinkertaisesti kuin tämä.
Puu, jos se solmu, yksi Näissä piireissä että on useita,
se ei tule olla yksi osoitin, mutta kaksi.
Ja heti kun lisäät toinen osoitin, sinun
voi itse nyt tehdä sort kaksiulotteisten tietojen
rakenteet muistissa.
Paljon kuin kaksiulotteinen array, voit
on eräänlainen kaksiulotteinen liittyvät luettelot mutta niitä
jotka noudattavat kaavaa jossa ei ole sykliä.
Se on todella puu yhdellä isovanhempi tapa tänne ja sitten
jotkut vanhemmat ja lapset ja lapsenlapset ja lastenlastenlapset.
ja niin edelleen.
>> Mutta mitä todella siisti tästä liikaa, vain kiusaa sinua vähän koodia,
Recall rekursio alkaen jonkin aikaa takaisin, jolloin
voit kirjoittaa funktio, joka kutsuu itseään.
Tämä on kaunis tilaisuus toteuttaa jotain
kuten rekursio, koska pitävät tätä.
>> Tämä on puu.
Ja olen ollut vähän anaali miten Laitoin kokonaislukuja kadulle.
Niin paljon, että sillä on erityinen name-- binäärihakupuu.
Nyt olemme kuulleet binary etsiä, mutta voit
työskennellä taaksepäin tämä asia nimi?
Mikä on malli miten Lisätään kokonaisluvut tähän puuhun?
Se ei ole mielivaltaista.
Siellä on joitakin kuvio.
Joo.
>> Yleisö: Pienempiä vasemmalla.
>> DAVID MALAN: Joo.
Pienempiä ovat vasemmalla.
Isompiakin ovat oikealla.
Niin että totena on vanhempi on suurempi kuin sen vasen lapsi,
mutta vähemmän kuin sen oikea lapsi.
Ja että yksin on jopa rekursiivinen sanallinen määritelmä
koska voit hakea että Samaa logiikkaa jokaiseen solmuun
ja se vain pohjat ulos, pohja tapauksessa, jos
tulee, kun osut yksi lehtiä, niin sanotusti,
jos lomaa ei ole lapsia vielä.
>> Nyt miten voisit löytää numeron 44?
Voisitte aloittaa juuresta ja sanoa, hm.
55 ei ole 44 Niin haluan mennä oikealle tai haluanko mennä vasemmalle?
No, ilmeisesti haluat mennä vasemmalle.
Ja niin se on aivan kuin puhelin Varaa esimerkiksi binäärihaku
yleisemmin.
Mutta me sen täytäntöönpanosta nyt hieman enemmän dynaamisesti
kuin array voisi sallia.
Ja itse asiassa, jos haluat katsoa klo koodi, ensi silmäyksellä varma.
Se näyttää koko joukko viivoja.
Mutta se on todella helppo käyttää.
Jos haluat toteuttaa toiminnon nimeltään Hae joiden tarkoitus elämässä
on etsiä arvon kuten N, kokonaisluku,
ja olet läpäissyt yhden pointer-- osoitin solmuun juuret,
Pikemminkin tuon puun, josta voit käyttää kaikkea muuta,
huomaa, miten suoraviivaisesti voit toteuttaa logiikkaa.
Jos puu on null, ilmeisesti se ei ole siellä.
Toivotaan vain return false.
Oikea?
Jos toisaalta se mitään, siellä ole mitään.
>> Muuten, jos n on pienempi kuin puu nuoli n- nyt nuoli n,
muistaa esittelimme Super lyhyesti toinen päivä,
ja että vain sitä de-viite osoitin ja katsoa kentän kutsutaan n.
Niin se tarkoittaa mennä sinne ja katsokaa kenttä kutsutaan n.
Joten jos n, arvo olet antanut, on vähemmän kuin arvo puissa kokonaisluku,
Minne haluat mennä?
Vasemmalle.
>> Niin huomaa rekursio.
En returning-- ole totta.
Ei vääriä.
Olen palaamassa riippumatta vastaus on peräisin kutsu itseäni, kulkee
n uudelleen, joka on tarpeeton, mutta mitä hieman erilainen nyt?
Miten minä tehdä ongelman pienempiä?
Olen ohimennen toisena argumentti, ei puun juurta,
mutta vasen lapsi tässä tapauksessa.
Joten olen ohimennen vasen lapsi.
>> Samaan aikaan, jos n on suurempi kuin solmu Olen tällä hetkellä katsot,
Etsin oikealla puolella.
Else, jos puu ei ole nolla, ja Jos elementti ei vasemmalle
ja se ei ole oikea, mikä on ihanan tapauksessa?
Olemme todella löytyy solmun kysymys, ja niin palaamme totta.
>> Joten olemme juuri naarmuja pintaan nyt joitakin näistä tietorakenteita.
Ongelmatilanteissa asettaa viisi sinua will tutkia näitä vielä entisestään,
ja sinulle annetaan suunnittelua valinta, miten edetä tästä.
Mitä haluaisin tehdä päätelmiä on vain 30 sekunnin teaser
mitä odottaa ensi viikolla ja sen jälkeen.
>> Kuten me begin-- onneksi saatat think-- meidän siirtyminen hitaasti
maailmasta C ja alempi tason toteutuksen yksityiskohdat,
maailmaan, jossa voimme ottaa varten myöntää, että joku muu on vihdoin
täytäntöön nämä tiedot rakenteet meille,
ja alamme ymmärtää reaalimaailman täytäntöönpanosäädöksillä
Web-pohjaisten ohjelmien ja sivustot yleisemmin
ja myös erittäin turvallisuus vaikutuksia, että olemme vain
alkanut raapia pintaa.
Tässä on mitä odottaa meitä vuonna lähipäivinä.
>> [VIDEOTOISTOSTA]
>> -Hän Tuli viestin kanssa, protokollan kaikkia omia.
Hän tuli maailmaan julma palomuurit, piittaamaton reitittimet,
ja vaaroista paljon pahempi kuin kuolema.
Hän on nopea.
Hän on vahva.
Hän on TCP / IP, ja hänellä on osoitteesi.
"Warriors of the Net".
[END VIDEOTOISTOSTA]
DAVID MALAN: Tulossa ensi viikolla.
Nähdään sitten.
[VIDEOTOISTOSTA]
-Ja Nyt, "Deep Thoughts" by Daven Farnham.
-David Aina alkaa luentoja, "Okei."
Miksi ei, "Tässä on ratkaisu Tämän viikon Harjoitus "
tai "Annamme kaikille teille?"
[Nauraa]
[END VIDEOTOISTOSTA]