>> SPEAKER 1: Okei, joten olemme takaisin.
Tervetuloa CS50.
Tämä on viikon lopussa seitsemän.
Joten muistaa, että viime kerralla, aloimme katsot hieman kehittyneempiä
tietorakenteita.
Koska tähän asti, kaikki olimme todella käytössämme oli tämä, array.
>> Mutta ennen kuin hävitä array ei kovin kiinnostavaa, joka todellakin se
itse asiassa on, mitkä ovat joitakin plussia tämän yksinkertaisia ​​tietoja
rakenne toistaiseksi?
Mitä se hyvä?
Sikäli kuin olemme nähneet?
Mitä sinulla on?
Mitään.
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Mikä tuo on?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Kiinteä koko.
OK, niin miksi on kiinteä koko hyvä vaikka?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: OK, joten se on tehokas mielessä, että voit jakaa
kiinteä määrä tilaa, mikä toivottavasti Juuri niin paljon
tilaa kuin haluat.
Niin, että voisi olla aivan plus.
>> Mikä on toinen jopa puolella array?
Niin?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Kaikki - anteeksi?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Kaikki laatikot muistiin tai vierekkäin.
Ja se on hyödyllistä - miksi?
Se on aivan totta.
Mutta miten voimme hyödyntää tätä totuutta?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Aivan, voimme seurata jossa kaikki on vain tuntemalla
yksi osoite, eli osoite, ensimmäinen tavu, että kimpale muisti.
Tai jos merkkijono, osoite, ensimmäinen
nieriää, että merkkijono.
Ja sieltä voimme löytää merkkijonon loppuun.
Voimme löytää toinen elementti, Kolmas elementti, ja niin edelleen.
>> Ja niin hieno tapa kuvata, että piirre on, että ryhmät antavat meille
random access.
Vain käyttämällä hakasulkeen merkintä ja numero, voit hypätä
tietty alkio jatkuvassa aikaa, iso O
yhden, niin sanoakseni.
>> Mutta siellä on ollut joitakin haittoja.
Mikä joukko ei tee kovin helposti?
Mitä se ole hyvä?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Mikä tuo on?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Toiminnan laajentaminen koko.
Joten haittoja array ovat juuri päinvastoin
puolensa ovat.
Joten yksi haittoja on että se on kiinteä koko.
Joten et voi todella kasvattaa sitä.
Voit jakaa uudelleen isompi kimpale muistiin, ja sitten siirtyä vanhan elementtejä
uuteen array.
Ja sitten vapaa vanha array varten Esimerkiksi käyttämällä malloc tai vastaavalla
toiminto nimeltään realloc, joka allokoi uudelleen muistiin.
>> Realloc, kuten syrjään, yrittää antaa sinulle muisti, joka on vieressä array
että sinulla on jo.
Mutta se saattaa viedä asioita noin kokonaan.
Mutta lyhyesti sanottuna se on kallista, eikö?
Koska jos sinulla on kimpale muisti Tässä koko, mutta todella haluat yhden
Tämän koon, ja haluat säilyttää alkuperäinen elementtejä, sinulla on
karkeasti lineaarisen ajan kopiointi prosessi että täytyy tapahtua kohteesta
vanha array uusia.
Ja todellisuus kysyy toiminta järjestelmä uudelleen ja uudelleen ja
jälleen suurissa erissä muistia voi alkaa maksaa sinulle aikaa.
Joten se on sekä siunaus että kirous naamioida, että nämä ryhmät
ovat kiinteä koko.
Mutta jos otamme käyttöön sen sijaan jotain näin, jota kutsutaan linkitetyn
lista, saamme muutaman upsides ja muutamia haittoja täällä hyvin.
>> Joten linkitetty lista on yksinkertaisesti tietoa rakenne koostuu C structs tässä
tapauksessa, jossa struct, muistaa, on vain säiliön yhden tai useamman erityisen
tyyppisiä muuttujia.
Tässä tapauksessa, mitä tietotyyppejä näyttävät olevan sisällä struct että
Edellisen kerran soitimme solmu?
Kukin näistä suorakaiteen on solmu.
Ja kukin pienempi suorakulmio sisällä se on tietotyyppi.
Millaisia ​​Sanoimmeko he olivat maanantaina?
Niin?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: vaihteleva ja osoitin tai tarkemmin, int, N,
ja osoitin alareunassa.
Molemmat noista sattuvat olemaan 32 bittiä kello ainakin tietokoneen kuin tämä CS50
Laite, ja niin he laadittu tasapuolisesti koko.
>> Joten mitä käytät osoitinta joskin ilmeisesti?
Miksi lisätä tämän nuoli nyt, kun ryhmät olivat niin mukava ja puhdas ja yksinkertainen?
Mitä osoitin tekemässä Meille jokainen näistä solmuista?
>> Opiskelija: [kuultavissa].
>> Kaiutin 1: Aivan.
Se kertoo, missä seuraava on.
Joten minä tavallaan käyttää vertausta käyttäen lanka tavallaan
pujota nämä solmut yhdessä.
Ja se on juuri sitä, mitä olemme tekemässä osoittimet, koska jokainen näistä
paloina muisti saattaa olla vierekkäisiä, takaisin takaisin takaisin
sisällä RAM, koska joka kerta kun soita malloc sanoen, anna minulle tarpeeksi
tavua uusi solmu, se saattaa olla tässä tai se voi olla täällä.
Se voi olla täällä.
Et vain tiedä.
>> Mutta käyttämällä viitteitä osoitteet solmut, voit ompele
yhteen tavalla, joka näyttää visuaalisesti kuten lista, vaikka nämä asiat ovat
kaikki levittää koko yksi tai teidän kaksi tai neljä gigatavua RAM-muistia
sisällä oman tietokoneen.
>> Joten haittapuoli, sitten on linkitetty lista on mitä?
Mikä hinta olemme ilmeisesti maksaa?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Enemmän tilaa, eikö?
Olemme tässä tapauksessa kaksinkertaistunut määrä tilaa, koska olemme käyneet
32 bittiä jokaisen solmun jokaisen int, joten nyt 64 bittiä, koska meidän on
pitää noin osoitin samoin.
Saat lisää tehokkuutta, jos struct on suurempi kuin tämä yksinkertainen asia.
Jos sinulla todella on opiskelija sisällä josta on pari merkkijonojen
nimi ja talon, ehkä henkilötunnus, ehkä jotkut muut alat yhteensä.
>> Joten jos sinulla on riittävän suuri struct, sitten ehkä kustannukset osoittimen
ei niin iso juttu.
Tämä on hieman nurkkaan tapauksessa, että olemme tallentaa niin yksinkertainen primitiivinen
sisällä linkitetty lista.
Mutta kohta on sama.
Olet varmasti menoja enemmän muistiin, mutta saatko
joustavuus.
Koska nyt jos haluan lisätä elementin alussa luettelon
Minun täytyy myöntää uuden solmun.
Ja minun täytyy vain päivittää niitä nuolet jotenkin vain siirtämällä
joitakin viitteitä ympäri.
>> Jos haluan lisätä jotain osaksi listan keskeltä, en tarvitse
työntää kaikki sivuun, kuten teimme viikon aiemmin meidän vapaaehtoisille, jotka
edustettuna jono.
Voin vain jakaa uusi solmu ja Sitten vain pisteen nuolet
eri suuntiin, koska se ei ole on edelleen todellinen
muistin todellinen kaltainen rivi Olen laatinut se tässä näytössä.
>> Ja sitten lopuksi, jos haluat lisätä jotain listan loppuun, se
vieläkin helpompaa.
Tämä on tavallaan mielivaltainen merkintätapa, mutta 34: n osoitin, ota arvaus.
Mikä on arvo sen osoittimen kaikkein todennäköisesti tehdä tavallaan kuin vanha
koulun antenni siellä?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Se on luultavasti null.
Ja todellakin, että on yksi tekijän edustus null.
Ja se on nolla, koska olet täysin täytyy tietää, missä lopussa linkitetyn
lista on, ettet pidä seuraavat ja jälkeen ja sen jälkeen nämä nuolet
noin roskat arvoa.
Joten null tulee merkitsemään, että ei ole useamman solmun oikealla numero 34,
tässä tapauksessa.
>> Niin ehdotamme, että voimme toteuttaa tämä solmu koodi.
Ja olemme nähneet tällaista syntaksin ennen.
Typedef vain määritellään uusi tyyppi meitä, antaa meille synonyymi kuten
string oli char *.
Tässä tapauksessa se tulee antaa meille pika merkintätapa jotta struct solmu
voi sen sijaan vain olla kirjoitettu solmu, joka on paljon puhtaampaa.
Se on paljon vähemmän monisanainen.
>> Sisällä solmu on ilmeisesti int Kutsutaan, ja sitten struct solmu *
mikä tarkoittaa juuri sitä, mitä halusimme nuolet tarkoittaa, osoitin toiseen
solmu täsmälleen samaa tietotyyppiä.
Ja ehdotan, että voisimme toteuttaa hakutoiminto, kuten tämä, joka on
Ensi silmäyksellä saattaa tuntua hieman monimutkainen.
Mutta katsotaanpa sen yhteydessä.
>> Anna minun mennä yli laitteen täällä.
Saanen avata tiedosto nimeltä lista nolla piste h.
Ja joka sisältää vain määritelmän me Näin juuri hetki sitten tämän tiedon
tyyppi nimeltään solmu.
Joten kokosimme että otetaan piste h-tiedosto.
>> Ja syrjään, vaikka tämä ohjelma, joka olet tulleet on
ole kovin monimutkainen, se on todellakin yleissopimus kun kirjoitat ohjelman
laittaa asioita, kuten tietotyyppejä, vetää vakiot joskus, sisäpuolelle
otsikkotiedoston eikä välttämättä kaikki C-tiedosto, varmasti kun
ohjelmat saavat suurempia, jotta et tiedä mistä etsiä sekä
asiakirjat joissakin tapauksissa, tai perusasiat, kuten tämä,
määritelmä joidenkin tyyppi.
>> Jos minä nyt avata luettelon nolla piste c, huomaat muutamia asioita.
Se sisältää muutamia header-tiedostot, useimmat jonka olemme nähneet aiemmin.
Se sisältää omat header-tiedosto.
>> Ja syrjään, miksi se on kaksinkertainen lainaukset tässä, toisin kuin kulma
suluissa linjalla, että Olen korostanut siellä?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Joo niin se on paikallinen tiedosto.
Joten jos se on paikallinen tiedosto oman täällä linjalla 15, joka esimerkiksi käytät
lainausmerkit sijaan ja kulma suluissa.
>> Nyt tämä on tavallaan mielenkiintoinen.
Huomaa, että olen ilmoittanut maailmanlaajuisen muuttuja tässä ohjelmassa on line 18
soittaa ensin, idea on tämä olemaan osoitin ensimmäiseen
solmun minun linkitetty lista, ja olen alustetaan se null, koska olen
ei myönnetty mitään todellista solmut vielä.
>> Joten tämä merkitsee, kuvallisesti, mitä me näki hetki sitten kuva
että osoitin pitkälle vasen puoli.
Joten nyt, että osoitin ei ole nuolta.
Se sen sijaan on vain nolla.
Mutta se edustaa mitä tulee osoite ensimmäinen varsinainen
solmu tässä luettelossa.
Joten olen lisännyt sen on maailmanlaajuinen koska, kuten näet, kaikki tämä
Ohjelma ei elämässä on toteuttaa linkitetyn listan minulle.
>> Nyt olen saanut muutamia prototyyppejä täällä.
Päätin toteuttaa ominaisuuksia, kuten poisto, lisäys, etsiminen ja
läpikäyminen -
viimeksi vain on kävellä koko lista, tulostaa sen osat.
Ja nyt tässä on minun tärkein rutiinia.
Ja me ei viettää liian paljon aikaa Näiden koska tämä on tavallaan, toivottavasti
vanha juttu jo.
>> Aion tehdä seuraavat kun käyttäjä tekee yhteistyötä.
Joten, aion tulostaa pois tästä valikosta.
Ja olen alustettu sitä siististi kuin pystyin.
Jos käyttäjä on yksi, joka tarkoittaa he haluavat poistaa jotain.
Jos käyttäjä on kaksi, se tarkoittaa, että he haluavat lisätä jotain.
Ja niin edelleen.
Aion kehottaa sitten sitten komento.
Ja sitten aion käyttää GetInt.
>> Joten tämä on todella yksinkertainen menuing käyttöliittymä, jossa voit vain kirjoittaa
numero kartoitus yhteen nämä komennot.
Ja nyt minulla on mukava puhdas kytkin ilmoitus, että menee päälle
riippumatta käyttäjän kirjoitetaan sisään
Ja jos ne kirjoitetaan yhteen, minä soittaa poistaa ja rikkoa.
Jos ne kirjoitetaan kaksi, minä soittaa lisätä ja rikkoa.
>> Ja nyt huomaan koonneet jokaisen Näiden samalla linjalla.
Tämä on vain tyylillinen päätös.
Yleensä olemme nähneet jotain näin.
Mutta minä vain päättänyt, suoraan sanottuna, minun ohjelma näytti enemmän luettavissa koska
se oli vain neljä tapauksissa vain luettelo sen näin.
Täysin laillinen käyttö tyyliin.
Ja aion tehdä tätä niin kauan kuin Käyttäjä ei ole kirjoittanut nolla, jota
päätti tarkoittaa he haluavat lopettaa.
>> Joten nyt huomaa, mitä olen aikoo tehdä täällä.
Aion vapauttaa lista ilmeisesti.
Mutta siitä lisää vain hetken.
Katsotaanpa ensin suorittaa tämän ohjelman.
Joten haluan tehdä isompi terminaali ikkuna, piste slash listan 0.
Aion mennä eteenpäin ja kytkennässä kirjoittamalla kaksi, numero kuin 50, ja nyt
näet listan on nyt 50.
Ja minun tekstiä vain vierittää ylös hieman.
Joten nyt huomaa luettelo sisältää numero 50.
>> Tehdään toinen insert ottamalla kaksi.
Katsotaanpa kirjoittaa numeron kuin yksi.
Luettelo on nyt yksi, sen jälkeen 50.
Joten tämä on vain teksti-edustus luettelon.
Ja antaa lisätä yhden numeron kuten numero 42, joka on toivottavasti
ehdi keskellä, koska Tämän ohjelman erityisesti lajittelee sen
osia, koska se lisää ne.
Joten siellä meillä on.
Super yksinkertainen ohjelma, joka voisi ehdottomasti ovat käyttäneet erilaisia, mutta
sattuvat olemaan avulla linkitetty lista vain niin voin dynaamisesti
kasvaa ja kutista se.
>> Joten katsomaan hakuun, jos olen suorita komento kolme, haluan etsiä
varten, sanovat, numero 43.
Ja mitään ei ilmeisesti löytynyt, koska sain takaisin mitään vastausta.
Joten tämä uudelleen.
Etsi.
Katsotaanpa etsi 50, tai pikemminkin etsiä 42, joka on mukava
pikku hienovarainen merkitys.
Ja löysin elämän tarkoitus on.
Numero 42, jos et tiedä viittaus, googlettaa.
Selvä.
Joten mitä on tämä ohjelma tehnyt minulle?
Se vain saa minut lisätä näin mennessä ja etsiä elementtejä.
>> Katsotaan eteenpäin, niin, että jotka toimivat me vilkaisi
maanantain teaser.
Joten tämä toiminto, väitän, etsii elementti luettelossa ensimmäisenä
yksi, kehotukset käyttäjä ja sitten soittaa GetInt saada todellista int
että haluat etsiä.
>> Sitten huomaa tätä.
Aion luoda väliaikainen muuttuja linjassa 188 nimeltään osoitin -
PTR -
voinut soittaa se mitään.
Ja se on osoitin solmuun koska sanoin solmu * siellä.
Ja olen alustaa sen olevan yhtä suuri Ensimmäinen niin että minä tehokkaasti minun
sormella, niin sanoakseni, on hyvin Ensimmäinen osa luettelon.
Joten jos oikea käteni tässä PTR olen osoittaen sama asia, että ensimmäinen
on suunnattu.
>> Joten nyt takaisin koodi, mitä tapahtuu seuraavaksi -
Tämä on yhteinen paradigma iteroidessaan yli tapaisen
linkitetty lista.
Aion tee alla osoitin ei ole sama null Joten vaikka
minun sormi ei osoita joitakin null arvo, jos osoitin nuoli n on n.
Me huomaat ensin, että n on mitä käyttäjän kirjoitetaan kohti GetInts soittaa täällä.
>> Ja osoitin nuoli n tarkoittaa mitä?
No jos palaamme kuvan tänne, jos minulla on sormella osoittaen
että ensimmäinen solmu, joka sisältää yhdeksän, nuoli tarkoittaa sitä mennä, että
solmu ja napata arvo paikassa n, Tässä tapauksessa tietoja kentän Kutsutaan.
>> Sivuhuomautuksena - ja näimme pari viikkoa sitten, kun joku kysyi -
Tämä syntaksi on uusi, mutta se ei antaa meille voimia, jotka me
ei vielä ole.
Mikä oli tämä lause vastaa käyttäen dot merkintä ja tähti pari
viikkoa sitten, kun me vedetään pois Tämän kerroksen hieman ennenaikaisesti?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Aivan, se oli tähti, ja niin se oli tähti dot n kanssa
Suluissa täällä, joka näyttää, rehellisesti, mielestäni paljon
enemmän arvoituksellinen lukea.
Mutta tähden osoitin, kuten aina, keinoin mennä sinne.
Ja kun olet siellä, mitä tietoja kenttään haluat käyttää?
No käytät piste merkintätapa käyttää structs tietokenttä, ja minä
nimenomaan haluavat n.
>> Suoraan sanottuna, Väitän tätä on vain vaikeampi lukea.
Se on vaikeampi muistaa missä älä suluissa mennä,
tähti ja kaikki tämä.
Joten maailman hyväksynyt joitakin syntaktisia sokeria, niin sanoakseni.
Vain seksikäs tapa sanoa, tämä vastaa, ja
ehkä enemmän intuitiivinen.
Jos osoitin on todellakin osoitin, nuoli notaatio keinoin mennä sinne ja löytää
kenttään tässä tapauksessa Kutsutaan.
>> Joten jos löydän sen, huomaa, mitä teen.
Olen yksinkertaisesti tulostaa, löysin prosenttia i, kytkemällä arvon kyseiselle int.
Kehotan nukkua yhden sekunnin juuri sellaista tauon asioita näytön
antaa käyttäjälle toisen imeä mitä juuri tapahtui.
Ja sitten tauko.
Muuten, mitä teen?
Päivitän osoitin yhtä osoitin nuolta.
>> Joten vain tehdä selväksi, tämä tarkoittaa mennä siellä käyttäen my old-school merkintätapa.
Joten tämä tarkoittaa vain mennä mihin tahansa olet osoittaen, joka hyvin
Ensimmäinen tapaus on olen osoittaen struct yhdeksän siinä.
Joten olen mennyt sinne.
Ja sitten piste merkintä tarkoittaa, saada arvo seuraavaksi.
>> Mutta arvo, vaikka se on laadittu niin kapea, on vain numero.
Se on numeerinen osoite.
Joten tämä yksi rivi koodia, onko kirjoitettu näin, enemmän arvoituksellinen
tavalla, tai näin, hieman intuitiivinen tapa, tarkoittaa vain sitä, vedä kättäni
ensimmäisestä solmusta seuraavaan, ja sitten seuraavaksi, ja sitten
seuraava, ja niin edelleen.
>> Joten emme vatvoa muiden toteutuksia lisätä ja poistaa
ja läpikäynti, kaksi ensimmäistä jotka ovat melko mukana.
Ja mielestäni se on melko helppo saada menetetään, kun tekee sen suullisesti.
Mutta mitä voimme tehdä tässä yrittää selvittää, miten
kannattaa tehdä visuaalisesti.
Koska ehdotan, että jos me haluat lisätä osat tähän
olemassa lista, joka on viisi elementtiä -
9, 17, 22, 26, ja 33 -
jos olisin menossa toteuttaa tämän koodi, minun täytyy miettiä, miten mennä
noin näin.
>> Ja ehdotan ottaen pienin askelin jolloin tässä tapauksessa tarkoitan, mitä
mahdollisia skenaarioita, että me saattaa kohdata yleensä?
Kun toteutetaan lisäosa linkitetyn lista, tämä vain sattuu olemaan
Erityisenä esimerkkinä koko viisi.
No jos haluat lisätä numeron, kuten sanovat numero yksi, ja
ylläpitäminen lajitellaan järjestyksessä, jossa ilmeisesti ei numero yksi on
mennä tässä konkreettisen esimerkin?
Kuten alussa.
>> Mutta mikä on mielenkiintoista on, että Jos haluat lisätä yhden tähän
lista, mitä erityisiä osoitin tarvitsee päivitetään ilmeisesti?
First.
Joten Väitän, tämä on ensimmäinen tapaus että kannattaa harkita,
skenaario, johon asetat at listan alkuun.
>> Katsotaanpa nyppiä pois ehkä yhtä helppoa tai jopa helpompaa tapauksessa suhteellisesti.
Oletetaan Haluan lisätä numero 35 lajitellaan järjestyksessä.
Se ilmeisesti kuuluu sinne.
Joten mitä osoitin ilmeisesti on menossa on saatettava ajan tasalle, että skenaario?
34: n osoitin tulossa ole nolla mutta osoite struct
sisältää numeron 35.
Niin, että tapauksessa kaksi.
Joten jo, olen tavallaan quantizing kuinka paljon työtä minun täytyy tehdä täällä.
>> Ja lopuksi, ilmeinen keskellä kyseessä on todellakin, keskellä, jos haluan
laita jotain sanoa 23, joka menee välillä 23 ja 26, mutta
nyt asiat saavat hieman enemmän mukana, koska mitä
viitteitä tarvitse muuttaa?
Joten 22 on ilmeisesti syytä muuttaa koska hän ei voi osoittaa 26 enää.
Hän tarvitsee osoittamaan uuteen solmuun Minun täytyy myöntää soittamalla
malloc tai jokin vastaava.
>> Mutta sitten on myös, että uusi solmu, 23 tässä tapauksessa, että sen osoitin
osoittaen kenelle?
26.
Ja siellä tulee olemaan Jotta toiminnan täällä.
Koska jos teen tämän tyhmästi, ja minä esimerkiksi alku alussa
lista, ja minun tavoite on lisätä 23.
Ja voin tarkistaa, se kuuluu täällä, lähellä yhdeksän?
Ei.
Onko se kuulu tänne, vieressä 17?
Ei.
Onko se kuuluu tässä vieressä 22?
Kyllä.
>> Nyt jos olen tyhmä täällä, eikä ajattelu tämä läpi, voisin
jakaa minun uusi solmu 23.
Saatan päivittää osoitinta solmu nimeltään 22, osoittaen
se on uusi solmu.
Ja sitten mitä minun täytyy päivittää Uuden solmun osoitin olla?
>> Opiskelija: [kuultavissa].
>> Kaiutin 1: Aivan.
Osoittaen 26.
Mutta dammit jos en jo päivittää 22: n osoitin kohtaan tätä kaveria, ja
nyt minulla on orpoja, loput luettelon, niin sanoakseni.
Joten jotta toiminnan täällä tulee olemaan tärkeä.
>> Voit tehdä tämän voisin varastaa, eli kuusi vapaaehtoista.
Ja katsotaanpa jos emme voi tehdä tätä visuaalisesti sijasta code-viisas.
Ja meillä on ihania stressiä pallot sinulle tänään.
OK, miten yksi, kaksi, vuonna takaisin - on lopulta kyse.
kolme, neljä, molemmat kaverit loppuun.
Ja viisi, kuusi.
Toki.
Viisi ja kuusi.
Hyvä ja tulemme ja te seuraavan kerran.
Okei, tule ylös.
>> Okei, koska olet täällä ensin, haluaisit olla yksi hankalasti
Google Glass täällä?
Okei, niin, OK, Glass, tallentaa videota.
OK, olet hyvä mennä.
>> Okei, joten jos te voi tulla täällä, olen valmis etukäteen
joitakin numeroita.
Okei, tule tänne.
Ja miksi et mene hieman lisäksi, että tapa.
Ja katsotaanpa, mikä on nimesi, Google Glass?
>> Opiskelija: Ben.
>> SPEAKER 1: Ben?
OK, Ben, sinun tulee ensin, kirjaimellisesti.
Joten aiomme lähettää sinulle loppuun vaiheessa.
Kunnossa, ja sinun nimesi on?
>> Opiskelija: Jason.
>> SPEAKER 1: Jason, OK voit ll olla numero yhdeksän.
Joten jos haluat seurata Ben niin.
>> Opiskelija: Jill.
>> SPEAKER 1: Jill, aiot olla 17, jonka olisin tehnyt tämän enemmän
älykkäästi, olisin alkoi toisessa päässä.
Et mennä näin.
22.
Ja sinä olet?
>> Opiskelija: Mary.
>> SPEAKER 1: Mary, olet 22.
Ja sinun nimesi on?
>> Opiskelija: Chris.
>> SPEAKER 1: Chris, olet 26.
Ja sitten lopuksi.
>> Opiskelija: Diana.
>> SPEAKER 1: Diana, voit olla 34.
Niin tulet tänne.
>> Okei, niin täydellinen lajiteltu tilata jo.
Ja mennään eteenpäin ja tehdä tämän jotta voimme todella -
Ben olet juuri sellainen näköinen ulos tyhjästä siellä.
OK, joten mennään eteenpäin ja kuvata tämän käyttää aseita, aivan kuten olin tarkalleen,
mitä tapahtuu.
Joten mene eteenpäin ja antaa itsellenne jalka tai kaksi keskenänne.
Ja mennä eteenpäin ja kohta yhdellä kädellä kuka sinun pitäisi osoittaen
perustuu tähän.
Ja jos olet null vain pisteen suoraan alas lattialle.
OK, niin hyvä.
>> Joten nyt meillä on linkitetty lista, ja haluan ehdottaa, että minä näytellä
PTR, joten en viitsi kuljettaa tämän ympäri.
Ja sitten - joku tyhmä yleissopimus - voit soittaa tähän mitä haluat -
edeltäjä osoitin, pred osoitin -
se on vain lempinimi annoimme meidän näyte koodin vasempaan käteeni.
Toisaalta, jotka aiotaan pitää seurata, kuka on kuka
seuraavissa tilanteissa.
>> Niin kai, ensin haluan nyppiä pois että ensimmäinen esimerkki asennat sanoa
20 listaan.
Joten aion tarvitsevat jonkun ilmentävät numero 20 meille.
Joten minun täytyy malloc joku yleisöltä.
Tule ylös.
Mikä sinun nimesi on?
>> Opiskelija: Brian.
>> SPEAKER 1: Brian, kaikki hyvin, joten on solmu, joka sisälsi 20.
Okei, tule tänne.
Ja tietenkin, jos ei Brian kuuluu?
Niin, keskellä - itse asiassa, Hetkinen.
Teemme tämän epäkunnossa.
Teemme tämän paljon vaikeampaa kuin se tarvitsee ensin.
OK, aiomme ilmaiseksi Brian ja realloc Brian viisi.
>> OK, joten nyt haluamme lisätä Brian viisi.
Joten tule tänne vieressä Ben vain hetken.
Ja voit luultavasti kertoa jos tämä tarina on menossa.
Mutta katsotaanpa miettiä tarkasti Jotta toiminnan.
Ja se on juuri tämä visuaalinen että menee riviin
kanssa, että näytteen koodi.
Joten tässä olen PTR osoittaa aluksi ole Ben, sinänsä, mutta mitä tahansa
Arvostamme hän on, joka tässä tapauksessa on - mitä sinun nimesi olikaan?
>> Opiskelija: Jason.
>> SPEAKER 1: Jason, joten molemmat Ben ja minä osoittaen Jason tällä hetkellä.
Joten nyt minun täytyy selvittää, mistä Brian kuuluvat?
Joten ainoa asia on pääsy nyt on hänen n tieto.
Joten aion tarkistaa, on Brian alle Jason?
Vastaus on totta.
>> Joten mitä nyt täytyy tapahtua, oikeassa järjestyksessä?
Minun täytyy päivittää kuinka monta viitteitä yhteensä tässä tarinassa?
Jos käteni on vielä suunnattu Jason ja kätesi - jos haluat
laita kättä kuin, tavallaan, I tiedä, kysymysmerkki.
OK, hyvä.
>> Okei, niin olet muutamia ehdokkaita.
Joko Ben tai I tai Brian tai Jason tai kaikki muutkin, jotka
viitteitä täytyy muuttaa?
Kuinka monta yhteensä?
>> OK, niin kaksi.
Oma osoitin ei ole oikeastaan ​​väliä enää koska olen vain väliaikainen.
Joten se on nämä kaksi kaveria, oletettavasti, sekä Ben ja Brian.
Joten haluaisin ehdottaa, että päivitämme Ben, koska hän on ensimmäinen.
Ensimmäinen osa tästä luettelosta nyt olemaan Brian.
Niin Ben piste Brian.
OK, mitä nyt?
>> Kuka saa osoitti kenelle?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: OK niin Brian on kohtaan on Jason.
Mutta minä olen menettänyt seurata, että osoitin?
Tiedän missä Jason on?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: teen, koska olen tilapäinen osoitin.
Ja oletettavasti, en ole muuttunut kohtaan on uusi solmu.
Joten voimme yksinkertaisesti Brian kohta klo kuka olen osoittaen.
Ja olemme tehneet.
Joten jos yksi, lisäys on listan alussa.
Siellä oli kaksi pääasiallista vaihetta.
Yksi, meillä on päivittää Ben, ja sitten meillä on myös päivittää Brian.
Ja sitten ei tarvitse vaivata traipsing läpi loput
lista, koska meillä on jo löytänyt sijainti, koska hän kuului
jätti ensimmäisen elementin.
>> Okei, joten melko suoraviivaista.
Itse asiassa tuntuu olemme melkein joten tämä liian monimutkainen.
Joten nyt nyppiä pois loppuun luettelon, ja katso,
monimutkaisuus alkaa.
Joten jos nyt olen alloc yleisöltä.
Jokainen haluaa pelata 55?
Okei, olen nähnyt kätesi ensin.
Tule ylös.
Joo.
Mikä sinun nimesi on?
>> Opiskelija: [kuultavissa].
>> Kaiutin 1: Habata.
OK, tule ylös.
Sinulta numero 55.
Joten te, tietenkin, kuuluvat lopussa luettelosta.
Joten toistaa simulointi kanssani on PTR vain hetken.
Joten olen ensin menossa osoitat mitä Ben on suunnattu.
Olemme molemmat osoittaa nyt Brian.
Joten 55 on vähintään viisi.
Joten aion päivittää itseäni osoittaa Brian seuraava osoitin, joka
Nyt on tietenkin Jason.
55 on vähintään yhdeksän, joten Aion päivittää PTR.
Aion päivittää PTR Olen menossa päivittää PTR.
Ja aion - hmm, mitä nimesi uudelleen?
>> Opiskelija: Diana.
>> SPEAKER 1: Diana osoittaa, tietenkin, klo null vasemmalla kädellään.
Joten miten Habata todella kuuluvat selkeästi?
Vasemmalle, täällä.
Joten mistä tiedän laittaa hänet tänne Mielestäni olen mokannut.
Sillä mitä PTR taidetta tällä hetkellä?
Null.
Joten vaikka visuaalisesti, voimme tietenkin nähdä kaikki nämä
kaverit täällä lavalla.
En ole pidetty kirjaa edellisen henkilö luettelosta.
Minulla ei ole sormi pois, Tässä tapauksessa solmu numero 34.
>> Joten todella alkaa tämän yli.
Joten nyt en oikeastaan ​​tarvitse Toinen paikallinen muuttuja.
Ja tämä on mitä näet vuonna todellinen näyte C-koodia, jos sillä minä menen,
kun päivitän oikean käteni kohtaan Jason, mikä jättää Brian takana, I
parempi alkaa käyttää minun vasen käsi päivittää missä olin, niin että menen
läpi tämä luettelo -
enemmän hankalasti kuin aioin nyt täällä visuaalisesti -
Aion päästä luettelon loppuun.
>> Tämä käsi on edelleen nolla, mikä on melko hyödytön, muut kuin osoittamaan
Olen selvästi listan loppuun, mutta nyt ainakin minulla on tämä
edeltäjä osoitin osoittelee täällä, joten mitä nyt kädet ja mitä viitteitä tarvitsevat
päivitetään?
Jonka käsi haluat määrittää uudelleen ensimmäisen?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: OK, niin Dianan.
Minne haluat viitata Dianan vasen osoitin?
Klo 55, oletettavasti, jotta olemme asetettu siellä.
Ja missä olisi 55 osoitinta mennä?
Alas, mikä null.
Ja käteni, tässä vaiheessa ei väliä, koska ne olivat vain
tilapäinen muuttujia.
Joten nyt olemme tehneet.
>> Joten lisää monimutkaisuutta - ja paljon se ei ole niin vaikea toteuttaa,
mutta meidän toissijainen muuttuja tehdä Varmista, että ennen kuin voin siirtää oikealle
käsi, kun päivitän arvo minun vasen käsi, pred osoitin tässä tapauksessa, joten
että olen jäljessä osoitin seurata missä olin.
Nyt kun syrjään, jos olet ajatellut tätä kautta, tämä tuntuu se
hieman harmittaa on pidettävä seurata tämän vasemman käden.
>> Mikä olisi toinen ratkaisu Tähän ongelmaan on ollut?
Jos sinulla suunnitella uudelleen tietoja rakenne puhumme
läpi juuri nyt?
Jos tämä juuri sellainen tuntuu hieman ärsyttävää on, kuten, kaksi osoitinta
läpi listan, kuka muu voisi ovat, täydellisessä maailmassa, ylläpidetään
tietoa, että me tarvitsemme?
Niin?
>> Opiskelija: [kuultavissa].
>> Kaiutin 1: Aivan.
Oikealle niin siellä on todella mielenkiintoinen alkiot idea.
Ja tämä ajatus aiemmin osoitin, osoittaen edelliseen elementtiin.
Mitä jos vain kirjattu, että sisällä listan itse?
Ja se tulee olemaan vaikea visualisoida Tämän ilman kaikkia paperi
putoaa lattialle.
Mutta oletetaan, että nämä kaverit käyttää sekä heidän kätensä ovat aiemmin
osoitin, ja seuraavaksi osoitin, mikä toteuta me kutsumme kaksin verroin
linkitetty lista.
Joka sallisi minun tavallaan taaksepäin, paljon helpommin ilman minua,
ohjelmoija, joiden pitää seurata manuaalisesti -
todella manuaalisesti -
, missä olin ollut aikaisemmin luettelossa.
Joten emme tee sitä.
Me pitää se yksinkertainen, koska se on menossa on hintansa, kaksi kertaa
paljon tilaa viitteitä, jos haluat toinen.
Mutta se on todellakin yhteistä data rakenne tunnetaan
kaksinkertaisesti linkitetty lista.
>> Tehdään lopullinen esimerkki tästä ja laita nämä kaverit pois kurjuudesta.
Joten malloc 20.
Tule ylös käytävällä siellä.
Okei, mikä on nimesi?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Anteeksi?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Demeron?
OK tulla ylös.
Sinulla on 20.
Olet ilmeisesti menossa kuuluvat 17-22.
Joten haluan oppia minun oppitunti.
Aion aloittaa osoitin osoittaen Brian.
Ja aion olla minun vasen käsi vain päivittää Brian kuin muutan
Jason, tarkkailun tekee 20 vähemmän kuin yhdeksän?
Ei.
On 20 vähemmän kuin 17?
Ei.
On 20 alle 22?
Kyllä.
Joten mitä viitteitä tai käsissä tarvitse muuttaa jos he osoittavat nyt?
>> Joten voimme tehdä 17 osoittaen 20.
Niin se on hieno.
Missä haluamme tuoda osoitin nyt?
22.
Ja me tiedämme, missä 22 on jälleen kiitos minun tilapäinen osoitin.
Joten olemme OK siellä.
Joten koska tämä väliaikainen varastointi Olen pitänyt kirjaa, jossa jokainen on.
Ja nyt voit visuaalisesti mennä, jos kuulut, ja nyt tarvitaan 1, 2, 3,
4, 5, 6, 7, 8, 9 stressi pallot, ja aplodit
nämä kaverit, jos voisimme.
Hienosti tehty.
>> [APPLAUSE]
>> SPEAKER 1: Okei.
Ja saatat pitää kappaletta paperimääriä muistoesineitä.
>> Okei, niin, luota minuun se on paljon helpompi kulkea, että
ihmisillä kuin se on itse koodi.
Mutta mitä löydät vain hetken nyt, että sama - Voi kiitos.
Kiitos -
on, että huomaat, että samoja tietoja rakenne, linkitetty lista, voi todella
käyttää rakennuspalikka entistä kehittyneempiä tietorakenteita.
>> Ja ymmärtää liian teema on, että olemme ehdottomasti käyttöön lisää
monimutkaisuuden huomioon ottamista Tämän algoritmin.
Paikoilleen, ja jos kävimme läpi sitä, poisto ja etsimistä, on hieman
monimutkaisempi kuin se oli kanssa array.
Mutta saamme dynaamisuus.
Saamme mukautuva tietorakenne.
>> Mutta jälleen kerran, me maksamme hintaa ottaa joitakin lisää monimutkaisuutta, sekä
sen toteuttamisesta.
Ja me luopuneet random access.
Ja ollakseni rehellinen, siellä ei ole kivoja Puhdista slide Voin kertoa teille, että
sanoo tässä on, miksi linkitetty lista on parempi kuin joukko.
Ja jättää asian siihen.
Koska teema toistuisi nyt, vaikka enemmän lähiviikkoina, on
että siellä ei ole välttämättä oikea vastaus.
>> Siksi meillä on erillinen akseli muotoilun ongelma sarjaa.
Se on hyvin tilannekohtainen haluatko käyttää näitä tietoja
rakenteen tai että yksi, ja se riippuu siitä, mitä asioita sinulle kannalta
resurssien ja monimutkaisuus.
>> Mutta saanen ehdottaa, että ihanteellinen tiedot rakenne, pyhä Graal, olisi
jotain, joka on vakiona aika, riippumatta siitä, kuinka paljon tavaraa on
sen sisällä, eikö olisi mahtavaa, jos tietorakenne palasi vastauksia
vakioaikaisia.
Kyllä.
Tämä sana on teidän valtava sanakirja.
Tai no, tämä sana ei ole.
Tai tällaisia ​​ongelmia siellä.
No katsotaanpa emme voi ainakin ottaa askel kohti sitä.
>> Saanen ehdottaa uutta tietoa rakenne voidaan käyttää eri asioita,
tässä tapauksessa kutsutaan tiiviste.
Ja niin olemme todella takaisin vilkuillen klo array, tässä tapauksessa, ja
jokseenkin mielivaltaisesti, olen laatinut tämän hash taulukon array eräänlainen
kaksiulotteinen array -
tai pikemminkin se on kuvattu täällä kaksi ulotteinen array - mutta tämä on vain
taulukon koko 26, niin että jos me soita array, pöytä kiinnike
nolla on suorakulmion yläosassa.
Pöytäkiinnikkeen 25 on suorakulmion alareunassa.
Ja näin voisin piirtää tiedot rakennetta, jossa haluan tallentaa
ihmisten nimet.
>> Joten esimerkiksi, enkä piirtää Koko juttu täällä yläpuolella, jos olen
oli tämä joukko, jonka minä lähden nyt soittaa hash table, ja tämä on jälleen
sijainti nolla.
Tämä tässä on paikka yksi, ja niin edelleen.
Väitän, että haluan käyttää tätä tietoa rakenne, vuoksi keskustelua,
tallentaa ihmisten nimet, Alice ja Bob ja Charlie ja muita nimiä.
Joten ajatella tätä nyt alkuja vaikkapa sanakirja
jossa on paljon sanoja.
Ne sattuvat olemaan nimet meidän esimerkki tästä.
Ja tämä on aivan liian germane, kenties täytäntöön oikoluku, kuten me
ehkä ongelmien asetettu kuusi.
>> Joten jos meillä on joukko Koko 26 niin, että tämä on 25. sijainti
alareunassa, ja väitän, että Alice on ensimmäinen sana sanakirja
nimiä, jotka haluan lisätä RAM-muistiin, tähän tietorakenne, jossa ovat
vaistot kertoo, että Alicen nimi pitäisi mennä tässä array?
>> Meillä on 26 vaihtoehtoa.
Jos haluamme laittaa hänet?
Haluamme hänet kiinnike nolla, eikö?
Alice, kutsukaamme että nolla.
Ja B on yksi, ja C on kaksi.
Joten aiomme kirjoittaa Alicen nimi täällä.
Jos me aseta Bob, hänen nimi menee täällä.
Charlie menee täällä.
Ja niin edelleen alas Tämä tietorakenne.
>> Tämä on ihana tietorakenne.
Miksi?
No mitä on käyntiaika lisäämällä ihmisen nimi tähän
tietorakenne juuri nyt?
Koska tämä taulukko on toteutettu, todella, kuten array.
No se on jatkuvasti ajan.
Se on järjestyksessä yksi.
Miksi?
>> No miten voit määrittää jossa Alice kuuluu?
Näytät joka kirjaimen nimensä?
Ensimmäinen.
Ja voit päästä sinne, jos se on merkkijono, vain katsomalla merkkijono
kiinnike nolla.
Joten zeroth luonnetta merkkijono.
Se on helppoa.
Teimme että Crypto toimeksianto viikkoa sitten.
Ja sitten kun tiedät, että Alicen kirjain Capital, voimme vähentää
pois 65 tai pääoman itse, joka antaa meille nolla.
Joten nyt tiedämme, että Alice kuuluu paikassa nolla.
>> Ja koska osoitin näitä tietoja rakenne, jonkinlainen, kuinka kauan
se vie minut löytää paikka nollaan array?
Vain yksi askel, oikea Se on vakiona aika koska random access me
Ehdotettu oli ominaisuus array.
Joten lyhyt, kuvauksen, mitä indeksi Alicen nimi on, joka on vuonna
Tässä tapauksessa on, tai haluan vain ratkaista että nolla, jossa B on yksi-ja C on
kaksi, miettiminen, että ulos on vakio ajan.
Minun täytyy vain katsoa hänen ensimmäinen kirjain, mietitään, jossa nolla on
matriisi on myös jatkuvasti aikaa.
Joten teknisesti se on kuten kaksi vaihetta nyt.
Mutta se on silti jatkuvasti.
Joten me kutsumme että iso O yhden, joten olemme Lisätään Alice tähän taulukkoon
vakioaikaisia.
>> Mutta tietenkin olen nyt naiivi täällä, eikö?
Mitä jos Aaron luokassa?
Tai Alicia?
Tai muu nimet alkavat A. Jos aiomme laittaa
että henkilö, eikö?
Siis, nyt siellä on vain kolme ihmiset pöydälle, joten ehkä me
pitäisi laittaa Aaron paikassa nolla yksi kaksi kolme.
>> Oikea, voisin laittaa tänne.
Mutta sitten, jos yritämme lisätä Davidin Tässä lista, jossa ei David mennä?
Nyt meidän järjestelmä alkaa murtua alas, oikealle?
Koska nyt David päätyy tänne jos Aaron on itse asiassa täällä.
Ja nyt tämä koko ajatus ottaa puhdasta tietoa rakenne, joka antaa meille
vakioaikaisia ​​lisäyksiä ei ole enää vakioaikaisia, koska minun täytyy
Tarkista, oh, perkele, joku on jo Alice sijainti.
>> Saanen koetin loput tästä tiedot rakenne, etsivät paikka laittaa
joku Aaronin nimi.
Ja niin sekin alkaa ottaa lineaarista aikaa.
Lisäksi, jos nyt haluat löytää Aaron tässä tietorakenne, ja sinä
tarkista, ja Aaronin nimi ei ole täällä.
Parasta olisi vain sanoa Aaronin ei tietorakenne.
Mutta jos et alkaa tehdä tilaa Aaron jossa olisi pitänyt D
tai E, voit pahimmassa tapauksessa täytyy tarkistaa koko tietorakenne, vuonna
jolloin se lankeaa jotain lineaarista pöydän koko.
>> Niin okei, minä korjata.
Ongelmana tässä on se, että minulla oli 26 elementtejä tässä array.
Anna minun muuttaa sitä.
Oho.
Saanen muuttaa sitä niin, että melko hyvinvointia koko 26 yhteensä, huomaa pohjassa
indeksin tulee vaihtaa n miinus 1.
Jos 26 on selvästi liian pieni ihmisille " nimiä, koska siellä on tuhansia
nimet maailmassa, haluan vain tehdä 100 tai 1000 tai 10000.
Haluan vain jakaa paljon enemmän tilaa.
>> No se ei välttämättä vähene todennäköisyys, että meillä ei ole kahta
ihmiset nimet alkavat, ja niin, olit menossa yrittää laittaa
nimet paikassa nolla edelleen.
He vielä törmäävät, joka tarkoittaa tarvitsemme vielä ratkaisu laittaa
Alice ja Aaron ja Alicia ja muut nimet alkavat muualla.
Mutta kuinka suuri ongelma tämä on?
Mikä todennäköisyys, että olet on törmäyksiä tiedot
rakenne näin?
>> No, minäpä - Palaamme tähän kysymykseen täällä.
Ja katsokaa kuinka voisimme ratkaista se ensin.
Saanen vetää tätä ehdotusta täällä.
Mitä me vain kuvattu on algoritmi, heuristista kutsutaan lineaarinen
hyvää siitä, että jos olet yrittänyt lisätä jotain täällä tiedot
rakenne, jota kutsutaan hash table, ja ei ole tilaa siellä,
todella koetin tietorakenne tarkkailun, on tämä käytettävissä?
Onko tämä Saatavilla on tämä käytettävissä?
Onko tämä saatavilla?
Ja kun se vihdoin on, asetat nimi, joka alun perin
muualla kyseisessä paikassa.
Mutta pahimmassa tapauksessa vain paikalla saattaa olla hyvin pohjaan tietoja
rakenne, aivan lopussa array.
>> Joten lineaarinen luotaa, pahimmassa tapauksessa lankeaa lineaarinen algoritmi, jossa
Aaron, jos hän sattuu lisätään viime Tässä tietorakenne, hän voisi
törmäävät tämä ensimmäinen paikka, mutta sitten lopulta huono tuuri aivan lopussa.
Joten tämä ei ole pysyvä aika pyhä Graal meille.
Tämä lähestymistapa lisäämällä elementtejä tietojen rakennetta kutsutaan hash
taulukko ei näytä olevan vakioaikavälein ainakaan yleisessä tapauksessa.
Se voi siirtää joksikin lineaarinen.
>> Joten mitä jos päätämme törmäykset hieman eri tavalla?
Joten tässä on kehittyneempi lähestymistapa mitä vielä
kutsutaan tiiviste.
Ja hash, kuten syrjään, mitä Siis on indeksi, joka
Aiemmin viittasin.
Hash jotain voi olla mielletään verbi.
>> Joten jos hash Alicen nimi, hash funktio, niin sanotusti,
tulee palauttaa numeron.
Tässä tapauksessa on nolla, jos hän kuuluu osoitteessa sijainti nolla, yksi, jos hän kuuluu osoitteessa
sijainti yksi, ja niin edelleen.
Joten minun hash-toiminto on ollut toistaiseksi Super yksinkertainen, vain katsomalla
ensimmäinen kirjain jonkun nimen.
Mutta hajautusfunktio vie niin input palan tietoja,
string, int riippumatta.
Ja se sylkee tyypillisesti useita.
Ja että määrä on silloin, että tiedot elementti kuuluu tietorakenne
tunnetaan täällä tiiviste.
>> Joten intuitiivisesti, tämä on hieman eri yhteydessä.
Tämä itse asiassa viittaa esimerkiksi joihin syntymäpäivät, jossa
saattaa olla niin monta kuin 31 päivää kuussa.
Mutta mitä tämä henkilö päättää tehdä törmäystilanteessa?
Yhteydessä nyt, ei törmäys nimiä, mutta törmäys syntymäpäivistä,
jos kaksi ihmistä on sama syntymäpäivä on 2. lokakuun esimerkiksi.
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Joo, joten tässä meillä on hankittua linkitetyt.
Niin se näyttää hieman eri tavalla kuin olemme tehneet jo aiemmin.
Mutta me näytämme on array vasemmalla puolella.
Se on yksi indeksi, ilman erityistä syytä.
Mutta se on silti array.
Se on joukko osoittimia.
Ja jokainen näistä seikoista, kukin Näissä piireissä tai viiltää - slash
edustavat null - jokainen viitteitä on ilmeisesti osoittaa
mitä tietoja rakenne?
Linkitetty lista.
>> Joten nyt meillä on mahdollisuus kova koodi ohjelmaamme
pöydän koko.
Tässä tapauksessa tiedämme, että koskaan enintään 31 päivää kuukaudessa.
Niin kova koodaus arvo kuin 31 kohtuullisia yhteydessä.
Yhteydessä nimet, kova koodaus 26 ei ole kohtuuton, sen kansan
nimet vain aloittaa, esimerkiksi aakkoset johon Z.
>> Voimme ahtaa ne kaikki, että tiedot rakennetta niin kauan kuin, kun saamme
törmäys, emme laita nimiä täällä, me sen sijaan ajatella näiden solujen
ei niin jouset itse, mutta osoittimia, esimerkiksi Alice.
Ja sitten Alice voi olla toinen osoitin toiseen alkavan nimen
A. Ja Bob todella menee tänne.
>> Ja jos siellä on toinen nimi alkaa B, hän päätyy tänne.
Ja niin jokainen osia taulukossa kaksi, jos suunniteltu tätä
hieman enemmän taitavasti -
tulla -
jos olemme suunnitelleet tätä hieman taitavasti, tulee nyt mukautuva tiedot
rakenne, jossa ei ole ehdoton raja kuinka monta elementtiä voit lisätä
siihen, koska jos sinulla on törmäys, se käy hyvin.
Vain mennä eteenpäin ja liittää sen mitä näimme vähän sitten oli
tunnetaan linkitetty lista.
>> No katsotaanpa tauon vain hetken.
Mikä on todennäköisyys törmäyksen ensimmäinen paikka?
Oikea, ehkä olen yli ajattelu, ehkä Olen yli Engineering tätä ongelmaa,
koska tiedät mitä?
Kyllä, voin keksiä mielivaltaisia esimerkkejä päältä pääni, kuten
Allison ja Aaron, mutta todellisuudessa Annettu tasaisen jakautumisen
tuloa, että on joitakin satunnaisia ​​lisäyksiä osaksi tietorakenne, mitä todella on
todennäköisyys törmäyksen?
No kääntyy pois, se on itse asiassa Super High.
Minäpä yleistää tätä Ongelmana on, kuten tässä.
>> Joten huoneessa n CS50 opiskelijoita, mitä todennäköisyys, että ainakin
kaksi opiskelijaa huoneessa on sama syntymäpäivä?
Joten ei mitä. muutaman hund -
200, 300 ihmistä täällä ja useita sata ihmistä kotona tänään.
Joten jos halusi kysyä itseltämme, mitä on todennäköisyys kaksi ihmistä
tässä huoneessa, jolla on sama syntymäpäivä, Voimme selvittää tämän.
Ja väitän todella olemassa kaksi ihmisiä, joilla on sama syntymäpäivä.
>> Esimerkiksi, ei kukaan on syntymäpäivä tänään?
Eilen?
Huomenna?
Okei, joten se tuntuu aion täytyy tehdä tämä 363 tai niin enemmän
kertaa todella selvittää jos meillä on törmäys.
Tai voisimme vain tehdä tämän matemaattisesti eikä ikävän
näin.
Ja ehdottaa seuraavaa.
>> Joten ehdotan, että voisimme mallintaa todennäköisyys kaksi ihmistä, joilla
sama syntymäpäivä kuin todennäköisyydellä 1 miinus todennäköisyys ei ole sellainen, jossa
sama syntymäpäivä.
Niin saat tämän, ja tämä on vain fancy tapa kirjoittaa tätä, sillä
Ensimmäinen henkilö huoneessa, hän voi olla mikä tahansa yksi mahdollinen
synttärit olettaen 365 päivää vuodessa, pyydän anteeksi henkilöiden
29 helmikuu syntymäpäivä.
>> Joten ensimmäinen henkilö tässä huoneessa on ilmainen olla minkä tahansa määrän synttärit
ulos 365 mahdollisuudet niin, että teemme sen 365 jaettuna 365,
, joka on yksi.
Seuraava henkilö huoneessa, jos tavoite on välttää törmäys, voi vain
on hänen syntymäpäivänsä, miten monia mahdollisia päivää?
364.
Joten toinen termi tämä ilmaus on lähinnä tekee, että matematiikka meille
vähentämällä pois yksi mahdollinen päivä.
Ja sitten seuraavana päivänä, seuraavana päivänä, Seuraavana päivänä alas kokonaismäärä
ihmisiä huoneeseen.
>> Ja jos me sitten harkita, mikä sitten on todennäköisyys ei ulottaa kaikkien
ainutlaatuinen syntymäpäivät, mutta jälleen 1 miinus että, mitä saamme on ilmaus
että voi hyvin fancifully näyttää tältä.
Mutta se on mielenkiintoisempaa tarkastella visuaalisesti.
Tämä on kaavio, jossa x-akseli on ihmisten määrä huoneessa,
määrä syntymäpäiviä.
Y-akselilla on todennäköisyys Törmäyksen kaksi ihmistä
jolla on sama syntymäpäivä.
>> Ja takeaway tämä kaari että heti kun saat pitävän 40
opiskelijat, olet ylös 90% todennäköisyydellä combinatorically kahden
henkilöä tai enemmän ottaa sama syntymäpäivä.
Ja kun saat pitävän 58 ihmistä on lähes 100%: n mahdollisuus kahden
ihmisiä huoneeseen ovat menossa sama syntymäpäivä, vaikka siellä
365 tai 366 mahdollista kauhat ja vain 58 henkilöä huoneessa.
Vain tilastollisesti olet todennäköisesti saada törmäykset, jotka lyhyellä
motivoi tätä keskustelua.
Että vaikka saamme fancy täällä, ja alkaa ottaa näitä ketjuja, olemme yhä
menossa on törmäyksiä.
>> Joten Tässä herääkin kysymys, mikä on aiheutuvia kustannuksia lisäykset ja poistot
osaksi tietorakenne näin?
No saanen ehdottaa -
ja anna minun mennä takaisin ruudun yli täällä - jos meillä on n elementtejä
lista, joten jos yritämme lisätä n alkiota, ja meillä on
kuinka monta yhteensä kauhat?
Sanotaan 31 yhteensä kauhat tapauksessa syntymäpäiviä.
Mitä enimmäispituus yksi Näiden ketjujen mahdollisesti?
>> Jos taas on olemassa 31 mahdollista syntymäpäivät tiettynä kuukautena.
Ja me vain paakkuuntuu kaikille -
Oikeastaan ​​se on tyhmä esimerkki.
Tehdään 26. sijaan.
Joten jos todella on ihmisiä, joiden nimet aloittaa-Z, mikä antaa
us 26 mahdollisuuksia.
Ja me tietorakenteen kuten yksi me vain näki, jolloin meillä on
joukko osoittimia, joista jokainen pistettä linkitetty lista, jossa
Ensimmäinen luettelo on kaikille nimellä Alice.
Toisessa luettelossa on jokaisen kanssa alkavan nimen, joka alkaa
B ja niin edelleen.
>> Mikä on todennäköisesti pituus kunkin nämä luettelot jos oletamme nice clean
jakelu nimet AZ koko tietorakenne?
On n ihmisiä tietorakenne jaettuna 26, jos ne ovat kauniisti
hajallaan koko tietorakenne.
Joten pituus kunkin näistä ketjut on n jaettu 26.
Mutta iso O merkintä, mikä se on?
Mikä on todella?
Joten se on oikeastaan ​​vain n, eikö?
Koska olemme sanoneet aiemmin, että hyi jaat 26.
Kyllä, todellisuudessa se on nopeampi.
Mutta teoriassa, se ei ole pohjimmiltaan kaikki nopeammin.
>> Joten meillä ei tunnu olevan kovin paljon lähempänä tätä pyhä Graal.
Itse asiassa tämä on vain lineaarista aikaa.
Pahus, tässä vaiheessa, miksi emme käyttää vain yhtä valtava linkitetty lista?
Miksi emme vain käytä yhtä suuri array tallentaa nimiä
jokainen huone?
No, on siellä vielä jotain pakottavia noin tiiviste?
Onko vielä jotain pakottavia noin tietorakenne
joka näyttää tältä?
Tämä.
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Oikea, ja uudelleen, jos se on vain lineaarinen algoritmi, ja
lineaarisen ajan tietorakenne, miksi en vain tallentaa jokaisen nimen iso
array, tai iso linkitetty lista?
Ja lopettamaan CS niin paljon vaikeampaa kuin sen pitäisi olla?
Mikä on vakuuttava tästä, vaikka vaikka en naarmuuntunut sitä?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Lisäykset eivät ole?
Kallis enää.
Joten lisäyksiä mahdollisesti voisi vielä olla jatkuvaa aikaa, vaikka tietosi
rakenne näyttää tältä, joukko osoittimia, joista kukin on suunnattu
mahdollisesti linkitetty lista.
Miten voit saavuttaa jatkuvasti kerran asennus nimiä?
Kiinni se etu, oikea?
>> Jos uhraamme suunnittelu maalin aikaisemmin, jos halusimme säilyttää
kaikkien nimet, esimerkiksi lajitellaan, tai kaikki numerot lavalla lajitellaan,
Oletetaan, että meillä on lajittelemattoman linkitetty lista.
Se vain maksaa meille yksi tai kaksi vaihetta, kuten tapauksessa Ben ja Brian
aikaisemmin, lisätä elementin listan alkuun.
Joten jos emme välitä lajittelu kaikki nimet alkavat tai kaikki
nimet alkavat B, voimme silti saavuttamiseksi vakioaikaisia ​​paikoilleen.
Nyt etsii Alice tai Bob tai nimi yleisemmin on vielä mitä?
Se on iso O n jaettuna 26, vuonna ihanteellinen tapaus, jossa kaikki ovat tasaisesti
jaetaan, missä on niin paljon n kuin on Z: n, joka on luultavasti
epärealistinen.
Mutta se on silti lineaarinen.
>> Mutta täällä, palaamme kohta ja asymptoottinen merkintä on
teoriassa totta.
Mutta todellisessa maailmassa, jos väitän, että minun ohjelma voi tehdä jotain 26 kertaa
nopeammin kuin omasi, jonka ohjelma aiotte mieluummin käyttää?
Sinun tai minun, joka on 26 kertaa nopeampi?
Realistisesti, henkilö, jonka on 26 kertaa nopeammin, vaikka teoriassa
algoritmit käyttää samoissa asymptoottinen ajoaika.
>> Saanen ehdottaa eri ratkaisu kokonaan.
Ja jos tämä ei puhaltaa mieltäsi, olemme ulkona tietorakenteita.
Joten tämä on se trie -
Tällainen tyhmä nimi.
Se tulee noudon ja sana on kirjoitettu trie, t-r-i-e, koska
Tietenkin haku kuulostaa trie.
Mutta se on historiaa sanan trie.
>> Joten trie on todellakin jonkinlainen puu, ja se on myös pelata kyseistä sanaa.
Ja vaikka et oikein näe sitä tämän visualisointi, triestä on
puun rakenne, kuten sukupuun yksi kantaisä yläosassa ja paljon
ja lapsenlapset ja lapsenlapset kuten lehdet pohjassa.
Mutta jokainen solmu triestä on jono.
Ja se on array - ja lähdetään pelkistettyjen hetkeksi - se on
array, tässä tapauksessa, koon 26, jossa jokainen solmu taas on taulukon koko
26, jossa zeroth tekijä, että array edustaa, ja viime
elementti jokaisessa tällaisessa array edustaa Z.
>> Joten ehdotan, niin, että nämä tiedot rakenne, joka tunnetaan trie, voi olla
käytetään myös tallentaa sanat.
Näimme hetki sitten, miten voisimme säilyttää sanoja, tai tässä tapauksessa nimiä, ja me
näki aikaisemmin kuinka voimme tallentaa numeroita, mutta jos keskitymme nimiä tai jouset
täällä, huomaa, mitä mielenkiintoista.
Väitän, että nimi Maxwell on sisällä tämän datarakenteen.
Missä näet Maxwell?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Vasemmalla.
Joten mitä mielenkiintoista tässä tiedot rakenne on kuin myymälä
string M-A-X-W-E-L-L kenoviivan nolla, kaikki contiguously, mitä sen sijaan tehdä
seuraa.
Jos tämä on trie kuten tietojen rakenteesta, kukin jonka solmut on jälleen array,
ja haluat tallentaa Maxwell, ensin indeksi ja niin juuri solmun, joten
puhua, ylin solmu, paikassa M, oikea, joten
karkeasti keskelle.
Ja sitten sieltä, voit seurata osoitin lapsisolmuilleen, niin sanoakseni.
Joten sukupuun mielessä, voit seurata sitä alaspäin.
Ja jotka johtavat sinut toiseen solmuun Vasemmalla, joka on
vain toinen joukko.
>> Ja sitten jos haluat tallentaa Maxwell, löydät osoittimen, joka edustaa
, Joka on tämä yksi täällä.
Sitten menet seuraavaan solmuun.
Ja ilmoitus - siksi kuvan hieman pettää -
tämä solmu näyttää erittäin pieniä.
Mutta tämän oikealla puolella on Y ja Z. Se on vain tekijä on katkaistu
kuvaa niin, että olet itse nähdä asiat.
Muuten tämä kuva olisi erittäin laaja.
Nyt voit indeksinä sijainti X, niin W, sitten E, niin L, sitten L. Mikä sitten
tämä uteliaisuus?
>> No, jos käytät tällaisia ​​uusia ottaa tallentamisesta merkkijono
tietorakenne, sinun pitää vielä olennaisesti ruksata tiedoissa
rakenne, joka sana loppuu tähän.
Toisin sanoen jokainen näistä solmuista jotenkin muistaa, että meillä
oikeastaan ​​seurannut kaikki nämä viitteet ja lähtevät hieman
leivän sisus alareunassa täällä tämän rakenne osoittaa M-A-X-W-E-L-L on
todellakin tässä tietorakenne.
>> Joten voisimme tehdä tämän seuraavasti.
Jokainen solmut kuvan me vain Sahassa on yksi, joukko koko 27.
Ja se on nyt 27, koska p asetettu kuusi, me todella antaa sinulle pilkullisilla
jotta voimme olla nimiä, kuten O'Reilly ja toiset heittomerkit.
Mutta sama ajatus.
Jokainen niistä on array pistettä struct
solmu, joten vain solmu.
Joten tämä on hyvin mieleen meidän linkitetyn listan.
>> Ja sitten minulla on totuusarvo, joissa pääsen soittaa sana, joka on vain olemaan
true, jos sana päättyy tämän solmu puussa.
Se tehokkaasti edustaa hieman kolmio näimme hetki sitten.
Joten jos sana päättyy, että solmun puu, että sana alalla on totta,
joka on käsitteellisesti tarkkailun pois, tai olemme piirustus tämän kolmion, kyllä ​​siellä
on sana täällä.
>> Joten tämä on trie.
Ja nyt kysymys on, mitä on sen käyntiaika?
Onko se iso O n?
Onko se jotain muuta?
No, jos olet n nimiä tällä tiedot rakenne, Maxwell on vain yksi
heille, mitä on käyntiaika lisäämällä tai löytää Maxwell?
Mitä käyntiaika lisäämällä Maxwell?
Jos on olemassa n muut nimet jo pöytään?
Niin?
>> Opiskelija: [kuultavissa].
>> SPEAKER 1: Joo, se on pituus nimen, eikö?
Niin M--x-w-e-l-l niin se tuntuu tämä algoritmi on iso O seitsemän.
Nyt, tietenkin, nimi pituus vaihtelee.
Ehkä se on lyhyt nimi.
Ehkä se on pidempi nimi.
Mutta mitä Tärkeintä tässä on, että se jatkuva numero.
Ja ehkä se ei oikeastaan ​​ole vakio, mutta Jumala, jos realistisesti, vuonna
sanakirja, on luultavasti joitakin raja on kirjainten määrä
henkilön nimi tietyssä maassa.
>> Ja niin voimme olettaa, että -arvo on vakio.
En tiedä mitä se on.
Se on luultavasti suurempi kuin mielestämme se on.
Koska aina on joku nurkka tapauksessa hullu pitkä nimi.
Joten kutsua k, mutta se on silti jatkuva oletettavasti koska jokainen
nimi maailmassa, ainakin erityisesti maa, että pituus tai
lyhyempi, joten se on vakiona.
Mutta kun olemme sanoneet jotain on iso O vakioarvo, mikä tuo
todella vastaa?
Se on todella sama asia sanoneen vakioaikaisia.
>> Nyt olemme tavallaan huijausta, eikö?
Olemme eräänlainen hyödyntämällä teoriaa täällä sanoa, että hyvin, järjestys k on
oikeastaan ​​vain tilata yhden, ja se on jatkuvasti ajan.
Mutta se todella on.
Koska keskeinen oivallus on, että jos meillä on n nimet jo tässä
tietorakenne, ja lisäämme Maxwell, on paljon aikaa se vie meidät
aseta Maxwell lainkaan vaikutusta kuinka monet muut ihmiset
ovat tietorakenne?
Ei näytä olevan.
Jos olisin miljardia enemmän elementtejä tähän trie ja aseta Maxwell, on
hän lainkaan vaikutusta?
Ei.
Ja se on kuin mikään päivän tiedot rakenteet olemme nähneet tähän mennessä, jos
käyntiaika algoritmisi on täysin riippumaton siitä, kuinka paljon
tavaraa on tai ei ole jo siitä, että tietorakenne.
>> Ja niin tämä tarjoaa sinulle nyt mahdollisuuden p set kuusi, joka
jälleen mukana täytäntöön omia oikoluku, lukeminen 150000
sanoen, miten parhaiten säilyttää, että ei välttämättä ole selvä.
Ja vaikka olen pyrkinyt löytämään Graalin malja, en
väittävät, että trie on.
Itse asiassa, tiiviste voi hyvin osoittautua paljon tehokkaampaa.
Mutta ne ovat vain -
se on vain yksi suunnittelun päätöksiä joudut tekemään.
>> Mutta sulkemalla Otetaanpa 50 tai niin sekunnin kurkistaa, mitä on
eteenpäin ensi viikolla ja sen jälkeen me siirtyminen Tämän komentoriviltä
maailmassa, jos C-ohjelmien asioita web perusteella ja kuten PHP ja
JavaScript ja internet itse, protokollia, kuten HTTP, jonka olet
itsestäänselvyytenä vuosia nyt, ja kirjoittanut melkein joka
päivä, ehkä, tai nähnyt.
Ja alamme Taitat kerroksia, mikä on internet.
Ja mikä on koodi, joka taustalla nykypäivän työkaluja.
Joten 50 sekuntia tämän teaser täällä.
Annan sinulle Warriors of Net.
>> [VIDEOTOISTOSTA]
>> -Hän tuli viesti.
Koskevan pöytäkirjan kaikkia omia.
Hän tuli maailmaan julma palomuurit, piittaamaton reitittimet ja vaarat kaukana
pahempaa kuin kuolema.
Hän on nopea.
Hän on vahva.
Hän on TCPIP.
Ja hänellä on osoitteesi.
Warriors of the Net.
>> [END VIDEOTOISTOSTA]
>> SPEAKER 1: Näin internet on toimia ensi viikolla.