>> JASON HIRSCHHORN: Tervetuloa kaikille to jakso Seven.
Olemme viikolla seitsemän kurssin.
Ja tämän tulevan torstai on Halloween joten olen
pukeutui kuin kurpitsa.
En voinut kumartua ja laittaa kenkäni, joten siksi olen
vain yllään sukat.
En myöskään ole päällään mitään alle Tämän, joten en voi ottaa sen pois, jos se on
häiritsevät sinua.
Pahoittelen jo etukäteen, että.
Sinun ei tarvitse kuvitella mitä on tekeillä.
Olen pukeutunut nyrkkeilijät.
Niin se kaikki hyvä.
>> Minulla on enää tarinan siitä, miksi olen pukeutunut kurpitsa, mutta aion
paitsi että myöhemmin tässä jaksossa koska en halua päästä alkuun.
Meillä on paljon jännittäviä asioita mennä yli tällä viikolla.
Useimmat niistä liittyvät suoraan tähän viikon ongelma asettaa, kirjoitusvirheet.
Aiomme olla menossa yli sidoksissa luettelot ja hash taulukoita
koko jakso.
Laitoin tämän luettelon jopa viikoittain, luettelo resursseja voit auttaa sinua
materiaali tällä kurssilla.
Jos tappiolla tai jos etsit jotain Lisätietoja tarkistaa yksi
näitä resursseja.
>> Jälleen pset6 on kirjoitusvirheet, tämän viikon PSET.
Ja se myös kannustaa sinua, ja minä rohkaista teitä, käyttää jotain muuta
resursseja nimenomaan tätä PSET.
Erityisesti kolme olen listattu ruudulla -
GDB, jotka olemme olleet tuttuja ja käyttänyt jo jonkin aikaa, on
tulee olemaan erittäin hyödyllistä tällä viikolla.
Joten laitoin tämän tänne.
Mutta kun olet työskennellyt C, sinun tulisi aina käyttää gdb
debug-ohjelmia.
Tällä viikolla myös Valgrind.
Tietääkö kukaan, mitä valgrind tekee?
>> Yleisö: Se tarkistaa muistivuodot?
>> JASON HIRSCHHORN: Valgrind tarkastukset muistivuodot.
Joten jos malloc jotain teidän ohjelma, pyydät muistia.
Lopussa oman ohjelman, olet kirjoittaa vapaa kaikesta olet
malloced antaa muistin takaisin.
Jos et kirjoita vapaa lopussa ja ohjelma tulee johtopäätökseen,
kaiken automaattisesti vapautetaan.
Ja pieniä ohjelmia, se on ei niin iso juttu.
Mutta jos olet kirjoittamassa enää käynnissä ohjelma, joka ei lopeta,
väistämättä, pari minuuttia tai Muutaman sekunnin jälkeen muistivuotoja
voi tulla valtavan paljon.
>> Joten pset6, odotus on, että sinulla on nolla muistivuotokuvioista kanssa
ohjelma.
Voit tarkistaa muistivuodot, suorita valgrind ja sillä saat muutamia kivoja
tuotos voit tietää, onko tai ei kaikki oli ilmaista.
Me harjoitella sitä myöhemmin tänään, toivottavasti.
>> Lopuksi Vertaa-komennon.
Käytit jotain vastaavaa se vuonna pset5 kanssa kurkistaa työkalu.
Ansiosta voit katsoa sisälle.
Voit myös käyttää JM Myös per Harjoitus spec.
Mutta salli sinun vertailla kaksi tiedostoa.
Voisit verrata bittikarttatiedoston ja info otsikot henkilöstön ratkaisun ja
teidän ratkaisu pset5 jos päätitte käyttää sitä.
Ero avulla voit tehdä samoin.
Voit vertailla oikea vastaus tämän viikon ongelma asetettu vastauksesi
ja katso jos se on linjassa tai katso missä virheet ovat.
>> Joten ne ovat kolme hyvää työkaluja, sinun tulisi käyttää tällä viikolla, ja
ehdottomasti tarkistaa oman ohjelman nämä kolme työkalua
ennen kuin laitat sen sisään
Jälleen, kuten olen maininnut joka viikko, jos sinulla on palautetta minulle - sekä
myönteistä ja rakentavaa -
vapaasti suunnata verkkosivuilla alareunassa tämän dian
ja syöttää sen sinne.
Olen todella kiitollinen kaikista ja kaikki palaute.
Ja jos annat minulle tiettyjä asioita, joita En voi tehdä parantaakseen tai että olen
menee hyvin, että haluat minut jatkaa, otan että sydän-ja
todella yrittää kovasti kuunnella palautteeseen.
En voi luvata aion tehdä kaiken, vaikka, kuten yllään
kurpitsa puku joka viikko.
>> Joten aiomme viettää suurimman osan jakso, kuten mainitsin, puhumme
liittyvät luettelot ja hash taulukoita, jotka on suoraan sovellettavissa
Harjoitus tällä viikolla.
Linkitetyt menemme yli suhteellisen nopeasti, koska olemme käyttäneet melkoisesti
aikaa menee yli sen osassa.
Ja niin me saamme suoraan koodaus ongelmia linkitettyjä listoja.
Ja sitten lopussa me puhumme hash taulukoita ja miten niitä sovelletaan tälle
viikon ongelma asetettu.
>> Olet nähnyt tämän koodin ennen.
Tämä on struct, ja se määritellään jotain uutta kutsutaan solmu.
Ja sisällä solmu on kokonaisluku täällä ja siellä on osoitin
toisen solmun.
Olemme nähneet tämän ennenkin.
Tämä on tulossa varten parin viikon ajan.
Siinä yhdistyvät osoittimia, jotka olemme olleet kanssa, ja structs, joiden avulla
meitä yhdistää kaksi eri asiat yhdeksi tietotyyppi.
>> Siellä on paljon meneillään ruudulla.
Mutta kaikki se olisi suhteellisen tuttu sinulle.
Ensimmäisellä rivillä, me julistaa uuden solmun.
Ja sitten sisällä että uusi solmu, otan kokonaisluvun, että solmu yhteen.
Näemme seuraavalla rivillä teen printf-komento, mutta olen harmaana
printf-komento, koska todella Tärkeä osa on tätä linjaa täällä -
new_node.n.
Mitä piste tarkoittaa?
>> Yleisö: Mene solmu ja arvioitava n arvoa sille.
>> JASON HIRSCHHORN: Tuo Aivan oikein.
Piste tarkoittaa pääsyn n osa Tämän uuden solmun.
Tämä seuraava rivi tekee mitä?
Michael.
>> Yleisö: Se luo toisen solmun , jotka viittaavat siihen, että uusi solmu.
>> JASON HIRSCHHORN: niin se ei luoda uusi solmu.
Se luo mitä?
>> Yleisö: osoitin.
>> JASON HIRSCHHORN: osoitin solmuun, kuten tämän solmun * täällä.
Niin se luo osoitin solmuun.
Ja mikä solmu on se osoittaa to, Michael?
>> Yleisö: Uusi solmu?
>> JASON HIRSCHHORN: Uusi solmu.
Ja se on suunnattu siellä, koska olemme antanut sen osoitteen uuteen solmuun.
Ja nyt tätä linjaa näemme kaksi erilaista tapaa
saman asian ilmaisemiseksi.
Ja halusin osoittaa, miten nämä kaksi asiaa ovat samat.
Ensimmäisellä rivillä, me dereference osoitin.
Joten menemme solmuun.
Sitähän tämä tähti merkitsee.
Olemme nähneet, että ennen osoittimet.
Mene, että solmu.
Se on suluissa.
Ja sitten käyttää kautta dot operaattorin n elementti, että solmu.
>> Niin, että kun syntaksin näimme tässä ja nyt
käytät sitä osoitin.
Tietenkin se saa aika kiireinen, jos olet kirjoittamassa nämä suluissa -
että tähti ja piste.
Se saa hieman kiireinen.
Joten meillä on joitakin syntaktisia sokeria.
Ja tämä linja täällä -
ptr_node-> n.
Joka tekee täsmälleen sama asia.
Joten nämä kaksi riviä koodia ovat vastaava ja tekee
täsmälleen sama asia.
>> Mutta halusin tuoda ne pois ennen menemme eteenpäin niin ymmärrät
että todella tämä asia täällä on vain syntaktista sokeria dereferencing
osoitinta ja sitten menee n osa tätä struct.
Kysyttävää slide?
OK.
>> Joten aiomme käydä läpi pari Toiminnan että voit tehdä
linkitettyjä listoja.
Linkitetty lista, muistaa, on sarja solmuja, jotka viittaavat toisiinsa.
Ja me yleensä alkavat osoitin kutsutaan pää, yleensä, joka osoittaa
ensimmäinen asia luetteloon.
Niin ensimmäisellä rivillä täällä, me on meidän alkuperäinen L ensin.
Niin, että mitä voit ajatella - tämä tekstiä täällä voit ajatella niin
vain osoitin olemme tallennettu jostain, että pisteitä
sen ensimmäiseen osaan.
Ja tässä linkitetty lista meillä on neljä solmua.
Jokainen solmu on iso laatikko.
Suurempi laatikko sisällä iso laatikko on kokonaisluku osa.
Ja sitten meillä on osoitin osa.
>> Nämä laatikot eivät vetoa mittakaavassa sillä kuinka suuri on
kokonaisluku tavuina?
Kuinka suuri nyt?
Neljä.
Ja kuinka suuri on osoitin?
Neljä.
Siis todella, jos me piirtää Tässä mittakaavassa sekä laatikot
olisi sama koko.
Tässä tapauksessa haluamme lisätä jotain osaksi linkitetty lista.
Voit siis nähdä täällä olemme asetat viisi Ajamme läpi
linkitetty lista, löytää jossa viisi menee, ja aseta se.
>> Katsotaanpa katkaisseen alas ja mennä hieman hitaammin.
Aion osoittaa aluksella.
Joten meillä on solmu viisi, että olemme luotu mallocs.
Miksi kaikki nauraa?
Vain leikkiä.
OK.
Joten olemme malloced viisi.
Olemme luoneet tämän solmun jossain muualla.
Meillä on valmis menemään.
Aloitamme edessä lista, jossa on kaksi.
Ja haluamme lisätä vuonna lajitellun tavalla.
>> Joten jos näemme kaksi ja haluamme laittaa viidessä, mitä teemme kun näemme
jotain vähemmän kuin me?
Mitä?
Haluamme lisätä viisi tähän linkitetty lista, pitää se lajitellaan.
Näemme numero kaksi.
Joten mitä me teemme?
Marcus?
>> Yleisö: Soita osoitin seuraavalle solmulle.
>> JASON HIRSCHHORN: Ja miksi menemme seuraavaan?
>> Yleisö: Koska se on Seuraavan solmun luettelosta.
Ja tiedämme vain, että muuhun paikkaan.
>> JASON HIRSCHHORN: Ja viisi on suurempi kuin kaksi, erityisesti.
Koska haluamme pitää sen lajiteltua.
Joten viisi on suurempi kuin kaksi.
Joten siirrymme seuraavaan.
Ja nyt pääsemme neljä.
Ja mitä tapahtuu, kun pääsemme neljä?
>> Viisi on enemmän kuin neljä.
Joten meidän pitää käynnissä.
Ja nyt olemme kuusi.
Ja mitä näemme kuusi?
Kyllä, Carlos?
>> Yleisö: Kuusi on suurempi kuin viisi.
>> JASON HIRSCHHORN: Kuusi on on suurempi kuin viisi.
Niin, että jos haluamme lisätä viisi.
Kuitenkin pitää muistaa, että jos me vain yksi osoitin täällä -
tämä on meidän ylimääräinen osoitin, joka on liikkumisesta listan läpi.
Ja me osoittaa kuuteen.
Olemme menettäneet tuntuman siihen, mitä tulee ennen kuutta.
Joten jos haluamme lisätä jotain osaksi Tämän luettelon pitämällä se lajitellaan, me
luultavasti kuinka monta viitteitä?
>> Yleisö: Kaksi.
>> JASON HIRSCHORN: Two.
Yksi seurata nykyisen yhden ja seurata
edellinen.
Tämä on vain yksin linkitetty lista.
Se vain menee yhteen suuntaan.
Jos meillä olisi kaksin verroin linkitetty lista, jossa kaikki oli osoittaa asia
sen jälkeen ja asia ennen sitä, niin meidän ei tarvitse tehdä sitä.
Mutta tässä tapauksessa emme halua menettää Seuraa mitä tuli ennen meitä, jos
meidän täytyy lisätä viisi jonnekin keskellä.
Sano olimme lisäämällä yhdeksän.
Mitä tapahtuisi, jos saimme kahdeksan?
>> Yleisö: Sinun täytyy saada, että nollakohta.
Sen sijaan, että nollakohta sinun on lisätä osa ja sitten on
se kohta yhdeksän.
>> JASON HIRSCHORN: Aivan.
Joten saamme kahdeksan.
Pääsemme listan loppuun, koska tämä osoittaa nollaamaan.
Ja nyt, sen sijaan, että se osoittaa null meillä on kohta meidän uuteen solmuun.
Ja asetamme osoittimen Meidän uusi solmu nollaamaan.
Onko kellään mitään kysyttävää noin lisäämällä?
Mitä jos en välitä pitämään luetteloa järjestetty?
>> Yleisö: Kiinni se alussa tai lopussa.
>> JASON HIRSCHORN: Stick sitä alkuun tai loppuun.
Kumpi meidän pitäisi tehdä?
Bobby?
Miksi loppuun?
>> Yleisö: Koska alku on jo täynnä.
>> JASON HIRSCHORN: OK.
Alussa on jo täynnä.
Kuka haluaa väittää vastaan ​​Bobby.
Marcus.
>> Yleisö: No varmaan haluat laitan sen alussa, koska
muuten jos laitat sen Lopulta sinun täytyisi
kulkea koko luettelo.
>> JASON HIRSCHORN: Aivan.
Jos siis olet ajatellut runtime, runtime lisäämällä lopussa
Olisi n, koko.
Mikä on iso O runtime lisäämällä alussa?
Vakioaikaisia.
Joten jos et välitä pitää jotain lajiteltu, paljon parempi vain
aseta alussa tästä luettelosta.
Ja että voidaan tehdä vakioaikaisia.
>> OK.
Seuraava toimenpide on löytää, mitkä muut - olemme muotoiltu tätä hakua.
Mutta aiomme käydä läpi linkitetty lista joillekin esine.
Olette nähneet koodi etsi ennen luentosalissa.
Mutta me tavallaan vain teki sen lisätä, tai ainakin lisäämällä
jotain lajiteltu.
Näytät läpi, menee solmuun solmu, kunnes löydät numeron, että olet
etsivät.
Mitä tapahtuu, jos tulet listan loppuun?
Sano Etsin yhdeksän ja minä päästä listan loppuun.
Mitä teemme?
>> Yleisö: Return väärä?
>> JASON HIRSCHORN: return false.
Emme löytäneet sitä.
Jos saavutat listan loppuun ja et löytänyt numeron olet
etsii, se ei ole siellä.
Kysyttävää löytää?
Jos tämä oli lajitellun listan, mitä olisi olla erilainen meidän etsimistä?
Joo.
>> Yleisö: Se löytäisi ensimmäinen arvo joka on suurempi kuin yksi
etsit ja palaa sitten vääriä.
>> JASON HIRSCHORN: Aivan.
Joten jos se lajitellun luettelon, jos saamme jotain, joka on suurempi kuin mitä
etsimme, emme tarvitse jatkakaa listan loppuun.
Voimme tässä vaiheessa return false koska emme tule löytämään sitä.
Kysymys kuuluu nyt, olemme puhuneet pitäminen liittyvät luettelot lajitellaan,
pitää ne lajittelemattoman.
Se tulee olemaan jotain et luultavasti täytyy miettiä
kun koodaus ongelma asettaa viisi, jos Valitse tiiviste erillisellä
ketjuttamalla lähestymistapaa, joka me puhumme myöhemmin.
>> Mutta onko se sen arvoista pitää luetteloa lajitellaan ja sitten voi ehkä olla
nopeammin hakuja?
Vai onko parempi lisäämään nopeasti jotain jatkuvassa runtime mutta sitten
on enää etsimistä?
Se on kompromissi oikeassa, että olet saat päättää, mikä on sopivampi
teidän erityinen ongelma.
Ja siellä ei ole välttämättä yhtä aivan oikea vastaus.
Mutta se on varmasti päätöstä saat tehdä, ja luultavasti hyvä puolustamaan
että vaikkapa kommentin tai kaksi miksi valitsit yksi yli muiden.
>> Lopuksi, poistaminen.
Olemme nähneet poistamalla.
Se muistuttaa hakemisen.
Etsimme elementin.
Sano yritämme poistaa kuusi.
Joten löydämme kuusi täällä.
Asia, että meidän täytyy varmistaa, että meillä tehdä, on, että mitä tahansa osoittaa
kuusi - kuten näemme vaiheessa kaksi tänne -
mitä on osoittaa kuusi tarpeet skip kuusi nyt ja muutettava
mitä kuusi viittaa.
Emme halua koskaan orpo muualla lista unohtamalla asettaa, että
edellinen osoitin.
Ja sitten joskus riippuen ohjelmasta, he vain
poistaa tämän solmun kokonaan.
Joskus sinun kannattaa palata arvo, joka on tässä solmussa.
Niin, että miten poistaa toimii.
Kysyttävää poistaa?
>> Yleisö: Joten jos aiot poistaa se, voisitteko käyttää ilmaiseksi, koska
oletettavasti se on malloced?
>> JASON HIRSCHORN: Jos haluat vapauttaa jotain, joka on täsmälleen oikeassa ja sinä
malloced se.
Sano halusimme palata tähän arvoon.
Voisimme palata kuusi ja sitten vapaasti tämän solmun ja puhelu ilmaiseksi sitä.
Tai olisimme luultavasti soita ilmaiseksi ensin ja palata sitten kuusi.
>> OK.
Joten siirtyä harjoitella koodausta.
Aiomme koodin kolme toimintoja.
Ensimmäinen on nimeltään insert_node.
Joten sinulla on koodi, että olen lähettänyt sinulle, ja jos olet katsomassa tätä myöhemmin
voit käyttää koodin linked.c on CS50 verkkosivuilla.
Mutta linked.c, on joitakin luuranko koodia, joka on jo
on kirjoitettu sinulle.
Ja sitten on pari toimintoja sinun täytyy kirjoittaa.
>> Ensimmäinen aiomme kirjoittaa insert_node.
Ja mitä insert_node tekee IS lisää kokonaisluku.
Ja annat kokonaisluku osaksi linkitetty lista.
Ja erityisesti, tarvitset pitää luetteloa järjestetty
pienimmästä suurimpaan.
Lisäksi et halua laita mitään kaksoiskappaleet.
Lopuksi, kuten näette insert_node palauttaa bool.
Joten sinun pitäisi antaa käyttäjä tietää vai ei insertti oli
onnistunut palauttamalla tosi tai epätosi.
Lopussa tämän ohjelman -
ja tässä vaiheessa et tarvitse huolehtia vapauttaa mitään.
Joten kaikki mitä teet on ottaen kokonaisluku ja asettamalla sen luetteloon.
>> Tämä on mitä pyydän sinua tekemään nyt.
Jälleen linked.c, johon kaikilla on, on luuranko koodi.
Ja sinun pitäisi nähdä pohjaa kohti mallifunktio ilmoituksen.
Kuitenkin ennen kuin menee koodausta se C, olen erittäin rohkaista teitä menemään
läpi vaiheet olemme olleet harjoitellaan viikoittain.
Olemme jo käyneet läpi kuva tästä.
Joten sinulla pitäisi olla jonkinlainen käsitys miten tämä toimii.
Mutta haluan kannustaa sinua kirjoittamaan Joissakin pseudokoodina ennen sukellusta sisään
Ja me aiomme mennä yli pseudokoodina ryhmänä.
Ja sitten kun olet kirjoittanut pseudokoodina, ja kun olemme kirjoitettu meidän
pseudokoodina ryhmänä, voit mennä koodaus se C.
>> Koska heads up, insert_node toiminto on luultavasti hankalin ja
kolme aiomme kirjoittaa, koska olen lisätty joitakin uusia rajoituksia
ohjelmointi, erityisesti et aio lisätä mitään
toistoja ja että luettelon pitäisi pysyä lajitellut.
Joten tämä on ei-triviaali ohjelma että tarvitset koodin.
Ja miksi et ota viisi vaille seitsemän minuuttia vain saada työtä
pseudokoodina ja koodin.
Ja sitten alamme menossa ryhmänä.
Jälleen, jos sinulla on kysyttävää, nostamaan käden ja tulen ympärille.
.
>> Olemme myös yleensä tehdä näitä -
tai en nimenomaisesti sano voi työskennellä ihmisten kanssa.
Mutta ilmeisesti olen erittäin rohkaista teitä, jos sinulla on kysymyksiä, kysyä
naapuri istuu vieressäsi tai jopa työskennellä jonkun kanssa
muuta, jos haluat.
Tämä ei tarvitse olla yksittäisiä hiljainen toiminta.
>> Aloitetaan kirjallisesti joitakin pseudokoodina taululle.
Kuka voi antaa minulle ensimmäinen rivi pseudokoodi tätä ohjelmaa?
Tätä toimintoa varten pikemminkin - insert_node.
Alden?
>> Yleisö: Joten ensimmäinen asia tein oli luoda uuden osoittimen solmuun ja minä
alustetaan se osoittaa samaan asia, että lista on osoittaa.
>> JASON HIRSCHORN: OK.
Joten luot uuden osoittimen luetteloon, ei solmuun.
>> Yleisö: Oikea.
Joo.
>> JASON HIRSCHORN: OK.
Ja sitten mitä haluamme tehdä?
Mitä sen jälkeen?
Entä solmu?
Meillä ei ole solmu.
Meillä on vain arvo.
Jos haluamme lisätä solmuun, mitä me täytyy tehdä ensin ennen kuin voimme edes
mieti asetat sen?
>> Yleisö: Anteeksi.
meidän täytyy malloc tilaa solmulle.
>> JASON HIRSCHORN: Erinomainen.
Tehdään -
OK.
Ei pääse, että korkea.
OK.
Aiomme mennä alas, ja sitten käytämme kaksi saraketta.
En voi mennä, että -
OK.
Luo uusi solmu.
Voit luoda toisen osoitin listaan tai voit käyttää valikosta, sillä se on olemassa.
Sinun ei todellakaan tarvitse tehdä.
>> Joten luomme uuden solmun.
Suuri.
Sitähän me teemme ensin.
Mitä seuraavaksi?
>> Yleisö: Odota.
Pitäisikö meidän luoda uusi solmu nyt tai odotammeko varmistaa, että
ei ole kopioita solmun luetteloon ennen luomme sen?
>> JASON HIRSCHORN: Hyvä kysymys.
Katsotaanpa pidä, että myöhemmin, koska Suurimman osan ajasta luomme
uusi solmu.
Joten me jatkamme että täällä.
Mutta se on hyvä kysymys.
Jos luomme sen ja löydämme kaksoiskappale, mitä pitäisi
teemme ennen paluutaan?
>> Yleisö: Vapauta se.
>> JASON HIRSCHORN: Joo.
Luultavasti vapauttaa sitä.
OK.
Mitä teemme, kun olemme luoda uuden solmun?
Annie?
>> Yleisö: Laitoimme numero solmussa?
>> JASON HIRSCHORN: Aivan.
Laitoimme numero - me malloc tilaa.
Aion lähteä, että kaikki yhdellä rivillä.
Mutta olet oikeassa.
Me malloc tilaa, ja sitten laitamme numero tuumaa
Voimme jopa asettaa osoittimen osa sitä nollaksi.
Se on aivan oikein.
Ja sitten entä sen jälkeen?
Laadimme tätä kuvaa taululle.
Joten mitä me teemme?
>> Yleisö: Käymme läpi listan.
>> JASON HIRSCHORN: Käy läpi listan.
OK.
Ja mitä me tarkistaa kussakin solmussa.
Kurt, mitä me tarkistaa varten kussakin solmussa?
>> Yleisö: Katso onko n arvo , että solmu on suurempi kuin n-arvo
meidän solmun.
>> JASON HIRSCHORN: OK.
Aion tehdä -
joo, OK.
Joten se on n -
Aion sanoa, jos arvo on suurempi kuin tämän solmun, niin mitä me teemme?
>> Yleisö: No, sitten lisätään asia juuri ennen sitä.
>> JASON HIRSCHORN: OK.
Joten jos se on suurempi kuin tämä, Sitten haluamme lisätä.
Mutta haluamme lisää se juuri ennen koska meillä on myös olisi oltava
pitää kirjaa sitten mitä oli ennen.
Niin laita ennen.
Joten meillä on todennäköisesti jäänyt jotain aiemmin.
Emme todennäköisesti tarvitse pitää seurata, mitä on tekeillä.
Mutta me palaamme sinne.
Joten mikä arvo on pienempi kuin?
Kurt, mitä teemme, jos -arvo on pienempi kuin?
>> Yleisö: Sitten vain pitää käynnissä ellei se viimeinen.
>> JASON HIRSCHORN: Pidän siitä.
Niin mene seuraavaan solmuun.
Ellei se viimeinen -
me varmaan tarkistaa, että in kannalta kunnossa.
Mutta joo, seuraavaan solmuun.
Ja se on tulossa liian alhainen, joten jatkamme matkaa tänne.
Mutta jos -
Voivatko kaikki nähdä tämän?
Jos olemme yhtä, mitä teemme?
Jos arvo yritämme lisätä on yhtä suuri kuin tämä solmun arvo?
Joo?
>> Yleisö: [kuultavissa].
>> JASON HIRSCHORN: Joo.
Ottaen huomioon tämän -
Marcus on oikeassa.
Olisimme voineet ehkä tehdä jotain erilaista.
Mutta koska olemme luoneet sitä, tässä meidän pitäisi vapauttaa ja palata sitten.
Oh boy.
Onko nyt parempi?
Kuinka niin?
OK.
Ilmainen ja mitä sitten me palata, [äänetön]?
OK.
Puuttuuko jotain?
Missä siis olemme pitää kirjaa Tekniikan solmun?
>> Yleisö: Minusta se menisi jälkeen luodaan uusi solmu.
>> JASON HIRSCHORN: OK.
Joten alussa me luultavasti -
joo, voimme luoda osoittimen uuteen solmu, kuten edellisen solmun osoitin ja
nykyinen solmu osoitin.
Joten lisätä että täällä.
Luo nykyisen ja edellisen osoittimet solmuihin.
Mutta kun me muuttaa niitä viitteitä?
Mistä me tehdä sen koodin?
Jeff?
>> Yleisö: - arvo olosuhteissa?
>> JASON HIRSCHORN: Mikä erityisesti yksi?
>> Yleisö: Olen vain hämmentynyt.
Jos arvo on suurempi kuin tämän solmun, ei se tarkoita, että haluat mennä
seuraavalle solmulle?
>> JASON HIRSCHHORN: Joten jos meidän arvo on suurempi kuin arvo tämän solmun.
>> Yleisö: Joo, niin sinun haluaisi pidemmälle ruodussa, eikö?
>> JASON HIRSCHHORN: Oikea.
Joten emme aseta se täällä.
Jos arvo on pienempi kuin tämä solmu, niin menemme seuraavaan solmuun - tai sitten
aseta ennen.
>> Yleisö: Odota, joka on tämä solmu ja mikä on arvo?
>> JASON HIRSCHHORN: Hyvä kysymys.
Arvo per tätä toimintoa määritelmä on mitä meille on annettu.
Joten arvo on numero meille annetaan.
Joten, jos arvo on pienempi kuin tämä solmu, me tarvitsemme aikaa lisätä.
Jos arvo on suurempi kuin tämän solmun, menemme seuraavaan solmuun.
Ja takaisin alkuperäiseen kysymykseen, kuitenkin silloin, kun -
>> Yleisö: Jos arvo on suurempi kuin tähän solmuun.
>> JASON HIRSCHHORN: Ja niin mitä me teemme täällä?
Makea.
Se on totta.
Olen juuri menossa kirjoittaa päivitys viitteitä.
Mutta kyllä, jossa nykyinen voisitte päivittää sen
viittaavat seuraavaan.
Jotain muuta puuttuu?
Joten aion kirjoittaa tämän koodi gedit.
Ja vaikka en tee tätä, voit olla pari minuuttia työskennellä koodaus
Tämän C.
>> Joten minulla on tulo pseudokoodina.
Nopea huomautus ennen kuin aloitamme.
Meillä ei ehkä pysty täysin lopettaa tämän kaikissa
kolme näistä toiminnoista.
On oikein niihin ratkaisuja että aion lähettää ulos te
jakson jälkeen, ja se julkaistaan ​​CS50.net.
Joten en rohkaista teitä mennä katsomaan kohdat.
Kehotan sinua kokeilemaan näitä teidän omistaa, ja sitten käyttää käytäntö
ongelmia tarkistaa vastauksesi.
Nämä ovat kaikki suunniteltu tarkasti liittyvät ja noudattaa mitä
sinun täytyy tehdä ongelman asetettu.
Joten en rohkaista voit harjoitella tätä oman ja sitten käyttää koodia
tarkistaa vastauksesi.
Koska en halua siirtyä hash pöydät jossain vaiheessa osiossa.
Joten emme ehkä saa läpi kaiken.
Mutta me teemme niin paljon voimme nyt.
>> OK.
Aloitetaanpa.
Asam, miten luomme uuden solmun?
>> Yleisö: Sinun suunnittelijan mahdollista *.
>> JASON HIRSCHHORN: Joten me on, että täällä.
Anteeksi.
Sanoitte struct *.
>> Yleisö: Ja sitten [? kind?] solmu-tai c-solmuun.
>> JASON HIRSCHHORN: OK.
Aion kutsua sitä new_node jotta voimme pysyä johdonmukaisesti.
>> Yleisö: Ja haluat määrittää, että pään, ensimmäinen solmu.
>> JASON HIRSCHHORN: OK.
Joten nyt tämä osoittaa - joten tämä ei ole luonut uuden solmun vielä.
Tämä on vain osoittaa ensimmäinen solmu listassa.
Miten luon uuden solmun?
Jos tarvitsen tilaa luoda uuden solmun.
Malloc.
Ja kuinka iso?
>> Yleisö: koko struct.
>> JASON HIRSCHHORN: koko struct.
Ja mitä struct kutsutaan?
>> Yleisö: Node?
>> JASON HIRSCHHORN: Node.
Joten malloc (sizeof (solmu)); antaa meille tilaa.
Ja on tämän linjan -
yksi asia on väärä tällä linjalla.
Onko new_node osoitin struct?
Se on yleisnimi.
Mikä se on -
solmu, tarkalleen.
Se solmu *.
Ja mitä me teemme heti me malloc jotain, Asan?
Mikä on ensimmäinen asia, mitä teemme?
Mitä jos se ei toimi?
>> Yleisö: Voi, tarkista, onko se viittaa solmuun?
>> JASON HIRSCHHORN: Aivan.
Joten jos new_node vastaa tasavertaisina null, mitä me teemme?
Tämä palauttaa bool, tätä toimintoa.
Täsmälleen.
Näyttää hyvältä.
Jotain lisättävää siellä?
Me lisäämme asioita lopussa.
Mutta toistaiseksi näyttää hyvältä.
Luo nykyisiä ja aikaisempia viitteitä.
Michael, miten voin tehdä tämän?
>> Yleisö: Olisitte tehdä solmu *.
Sinun täytyy tehdä yksi ei varten new_node mutta
solmut meillä jo on.
>> JASON HIRSCHHORN: OK.
Joten nykyinen solmu olemme.
Soitan että As.
Selvä.
Olemme päättäneet haluamme pitää kaksi, koska meidän täytyy tietää
mitä ennen sitä.
Mitä he saavat alustetaan?
>> Yleisö: Niiden arvo listallamme.
>> JASON HIRSCHHORN: Joten mikä on Ensimmäinen asia listallamme?
Vai mistä me tiedämme, missä alussa lista on?
>> Yleisö: Eikö ole läpäissyt osaksi toiminto?
>> JASON HIRSCHHORN: Oikea.
Se hyväksyttiin täällä.
Joten jos se siirtyi toiminto, aloittaa listan, mitä meidän pitäisi
set on yhtä suuri?
>> Yleisö: List.
>> JASON HIRSCHHORN: List.
Se on aivan oikein.
Nyt se on osoite alussa listalta.
Entä edellinen?
>> Yleisö: List miinus yksi?
>> JASON HIRSCHHORN: Ei mitään ennen sitä.
Mitä siis voimme tehdä merkitsevän mitään?
>> Yleisö: Null.
>> JASON HIRSCHHORN: Joo.
Kuulostaa hyvä idea.
Täydellinen.
Kiitos.
Käydä listan läpi.
Constantine, kuinka kauan aiomme käydä läpi listan?
>> Yleisö: kunnes pääsemme null.
>> JASON HIRSCHHORN: OK.
Joten jos, vaikka, silmukka.
Mitä me teemme?
>> Yleisö: Ehkä silmukka?
>> JASON HIRSCHHORN: Tehdään silmukka.
OK.
>> Yleisö: Ja me sanoa -
kunnes osoittimen ei ole yhtä kuin nolla.
>> JASON HIRSCHHORN: Eli jos tiedämme ehto, miten voimme kirjoittaa silmukka
perustuu pois tämän edellytyksen.
Millainen silmukan meidän pitäisi käyttää?
>> Yleisö: Vaikka.
>> JASON HIRSCHHORN: Joo.
Että on järkevämpää perustuu pois mitä sanoit.
Jos me vain haluamme mennä meidän se olisi vain tietää, että asia, se tekisi
järkevää tehdä samalla silmukka.
Vaikka nykyinen ei ole yhtä null, Jos arvo on pienempi kuin tähän solmuun.
Akshar, anna minulle tätä linjaa.
>> Yleisö: Jos nykyinen-> n n alle arvon.
Tai kumota tämä.
Kytke tässä haarukassa.
>> JASON HIRSCHHORN: Anteeksi.
>> Yleisö: Muuta kiinnike.
>> JASON HIRSCHHORN: Joten jos se on on suurempi kuin arvo.
Koska se on hämmentävää kommentti edellä, aion tehdä sen.
Mutta kyllä.
Jos meidän arvo on pienempi kuin tämän solmu, mitä me teemme?
Oh.
Minulla on se täällä.
Aseta ennen.
OK.
Miten me sen teemme?
>> Yleisö: Onko se vielä minut?
>> JASON HIRSCHHORN: Joo.
>> Yleisö: You -
new_node-> seuraava.
>> JASON HIRSCHHORN: Mikä siis että menossa tasa-arvoisia?
>> Yleisö: Se tulee samansuuruinen virta.
>> JASON HIRSCHHORN: Aivan.
Ja niin muut -
mitä muuta meidän täytyy päivittää?
>> Yleisö: Tarkista jos aiemmat vastaa null.
>> JASON HIRSCHHORN: Jos aiemmat -
joten jos aiemmat vastaa null.
>> Yleisö: Se tarkoittaa se menee tulla päähän.
>> JASON HIRSCHHORN: Tämä tarkoittaa se on tullut pää.
Joten mitä sitten teemme?
>> Yleisö: Emme pää vastaa new_node.
>> JASON HIRSCHHORN: Head vastaa new_node.
Ja miksi pää täällä, ei luetella?
>> Yleisö: Koska pää on maailmanlaajuinen muuttuja, joka on lähtö-paikka.
>> JASON HIRSCHHORN: Makea.
OK.
Ja -
>> Yleisö: Sitten et muuta prev-> Seuraavan vastaa new_node.
Ja sitten palaat totta.
>> JASON HIRSCHHORN: Minne asetamme new_node lopussa?
>> Yleisö: Haluaisin -
Asetin että alussa.
>> JASON HIRSCHHORN: Mikä linja?
>> Yleisö: Kun jos ilmoitus tarkistaa, jos se on tiedossa.
>> JASON HIRSCHHORN: Juuri täällä?
>> Yleisö: Tekisin new_node-> n vastaa arvoa.
>> JASON HIRSCHHORN: Kuulostaa hyvältä.
Luultavasti se on järkevää - emme täytyy tietää, mitä luetteloon olemme
koska olemme ainoastaan ​​kauppaa yksi lista.
Joten parempi toiminta ilmoitus tämä on vain päästä eroon tästä
kokonaan ja vain lisätä arvo osaksi päähän.
Emme edes tarvitse tietää mitä lista olemme tuumaa
Mutta aion pitää sen nyt ja vaihda se heti päivittää
dioja ja koodin.
Niin että näyttää hyvältä nyt.
Jos arvo - kuka voi tehdä tätä linjaa?
Jos -
mitä me teemme täällä, Noah.
>> Yleisö: Jos arvo on suurempi kuin As-> n -
>> JASON HIRSCHHORN: Miten menemme seuraavaan solmuun?
>> Yleisö: Curr-> n on yhtä new_node.
>> JASON HIRSCHHORN: So n on mikä osa struct?
Kokonaisluku.
Ja new_node on osoitin solmuun.
Joten mikä osa As meidän pitäisi päivittää?
Jos ei n, niin mitä muuta osaa?
Nooa, mitä toinen osa.
>> Yleisö: Voi, seuraavaksi.
>> JASON HIRSCHHORN: Seuraava, tarkalleen.
Täsmälleen.
Seuraava on oikea.
Ja mitä muuta me tarvitsemme päivittää, Noah?
>> Yleisö: viitteitä.
>> JASON HIRSCHHORN: So uusimme nykyinen.
>> Yleisö: Ed-> seuraava.
>> JASON HIRSCHHORN: Joo.
OK, me tauko.
Kuka voi auttaa meitä tässä?
Manu, mitä meidän pitäisi tehdä?
>> Yleisö: Sinun täytyy asettaa se sama As-> seuraava.
Mutta tehdä se ennen edellisen rivin.
>> JASON HIRSCHHORN: OK.
Mitään muuta?
Akshar.
>> Yleisö: En usko, että olet tarkoitus muuttaa As-> seuraava.
Taidat tarkoitus tehdä As tasavertaisina As-> vieressä siirtyä seuraavaan solmuun.
>> JASON HIRSCHHORN: Anteeksi, missä?
Millä line?
Tämä linja?
>> Yleisö: Joo.
Tee As vastaa As-> seuraava.
>> JASON HIRSCHHORN: Niin, että oikein koska nykyinen on
osoitin solmuun.
Ja haluamme sen osoittamaan seuraavaan solmu, mitä on tulossa tällä hetkellä
huomautti.
As itse on seuraava.
Mutta jos me päivittää curr.next, me olisi päivittää todellinen huomautuksen
itse, ei silloin, kun se osoitin oli osoittaa.
Entä tämän linjan, vaikka.
Avi?
>> Yleisö: Ed-> seuraava vastaa As.
>> JASON HIRSCHHORN: Joten jälleen, jos edell on osoitin solmuun, prev-> seuraava on
Varsinainen osoitin solmuun.
Joten tämä olisi päivittää osoitin solmun As.
Emme halua päivittää osoitin solmuun.
Haluamme päivittää edelliseen.
Joten miten me sen teemme?
>> Yleisö: Se olisi vain aiemmat.
>> JASON HIRSCHHORN: Oikea.
Edeltävä on osoitin solmuun.
Nyt me muutumme sen uuden osoittimen solmuun.
OK Siirtykäämme alas.
Lopuksi, tämä viimeinen ehto.
Jeff, mitä me teemme täällä?
>> Yleisö: Jos arvo on yhtä As-> n.
>> JASON HIRSCHHORN: Anteeksi.
Hyvänen aika.
Mitä?
Arvo == As-> n.
Mitä teemme?
>> Yleisö: Sinun vapauttavat new_node, ja silloin kyllä ​​return false.
>> JASON HIRSCHHORN: Tämä on mitä olemme kirjoittaneet toistaiseksi.
Onko kellään mitään lisätä ennen kuin teemme?
OK.
Kokeillaan.
Määräysvalta voi päästä loppuun ei-mitätön toiminto.
Avi, mitä on tekeillä?
>> Yleisö: Oletko tarkoitus panna paluun totta ulkopuolella kun silmukka?
>> JASON HIRSCHHORN: En tiedä.
Haluatko minun?
>> Yleisö: Älä välitä.
Ei.
>> JASON HIRSCHHORN: Akshar?
>> Yleisö: mielestäni sinun tarkoitus laittaa paluu false lopussa
ja samalla silmukka.
>> JASON HIRSCHHORN: Missä haluat sen mennä?
>> Yleisö: Like ulkopuolella kun silmukka.
Joten jos poistut samalla silmukka, joka avulla kun olet saavuttanut loppuun ja
mitään ei tapahtunut.
>> JASON HIRSCHHORN: OK.
Joten mitä me teemme täällä?
>> Yleisö: You return false siellä hyvin.
>> JASON HIRSCHHORN: Voi, me tee se molemmissa paikoissa?
>> Yleisö: Joo.
>> JASON HIRSCHHORN: OK.
Pitäisikö meidän mennä?
Hyvänen aika.
Olen pahoillani.
Pahoittelen näytön.
Se on tavallaan ihan sekaisin meitä.
Joten valitse vaihtoehto.
Nolla, per koodi, sulkeutuu ohjelma.
Yksi lisää jotain.
Katsotaanpa aseta kolme.
Insertti ei onnistunut.
Aion tulostaa.
Minulla ei ole mitään.
OK.
Ehkä se oli vain onnenpotku.
Aseta yksi.
Ei onnistunut.
OK.
Katsotaan läpi GDB todella nopeasti tarkistaa, mitä on tekeillä.
>> Muista GDB. / Nimi ohjelma saa meidät GDB.
Onko se paljon käsitellä?
Vilkkuu?
Luultavasti.
Sulje silmäsi ja kestää jonkin syvään Hengitä jos väsyt
tarkastella sitä.
Olen GDB.
Mikä on ensimmäinen asia, joka minun tehdä GDB?
Meidän täytyy selvittää mitä täällä tapahtuu.
Katsotaanpa.
Meillä on kuusi minuuttia luku mitä on tekeillä.
Rikkoa tärkein.
Ja mitä sitten teen?
Carlos?
Suorita.
OK.
Valitaan vaihtoehto.
Ja mitä N tehdä?
Seuraava.
Joo.
>> Yleisö: Etkö mainitse -
et sanonut, että pää, se oli alustetaan nolla alussa.
Mutta Sanoit että oli OK.
>> JASON HIRSCHHORN: Mennään - Katsotaanpa vuonna GDB, ja sitten menemme takaisin.
Mutta se kuulostaa sinulla on jo joitakin ajatuksia siitä, mitä on tekeillä.
Joten haluamme lisätä jotain.
OK.
Olemme lisätä.
Kirjoita int.
Laitamme kolme.
Ja sitten olen tällä linjalla.
Miten voin mennä aloittaa virheenkorjaus insertti tunnettu toiminto?
Hyvänen aika.
Se on paljon.
On, että sekosin paljon?
>> Yleisö: Voi, se kuoli.
>> JASON HIRSCHHORN: Kuvittelin veti sen ulos.
OK.
>> Yleisö: Ehkä se on toinen pää lanka.
>> JASON HIRSCHHORN: Vau.
Joten bottom line -
mitä sanoit?
>> Yleisö: Sanoin ironia teknisten vaikeuksia tässä luokassa.
>> JASON HIRSCHHORN: Tiedän.
Jos vain minulla oli valvoa, että osa.
[Äänetön]
Kuulostaa hyvältä.
Miksi et kaverit alkaa miettiä mitä olisimme voineet tehdä väärin,
ja tulemme takaisin 90 sekunnissa.
>> Avica, aion kysyä, miten mennä sisällä insert_node debug sitä.
Joten tämä on silloin, kun viimeksi jäi.
Miten voin mennä sisälle insert_node, Avica, tutkia, mitä on tekeillä?
Mitä GDB komento?
Tauko ei ottaisi minut sisälle.
Onko Marquise tietää?
>> Yleisö: Mitä?
>> JASON HIRSCHHORN: Mitä GDB komento Käytän mennä sisälle tätä toimintoa?
>> Yleisö: Step?
>> JASON HIRSCHHORN: Step kautta S. Se vie minut sisälle.
OK.
New_node mallocing tilaa.
Että kaikki näyttää sen menossa.
Tutkitaanpa new_node.
Se sai muistia osoite.
Katsotaan tarkistaa -
että on kaikki oikein.
Joten kaikki täällä tuntuu toimivan oikein.
>> Yleisö: Mitä eroa välillä P ja näyttö?
>> JASON HIRSCHHORN: P tarkoittaa tulosta.
Ja niin kysyt mitä erosta ja tämä?
Tässä tapauksessa mitään.
Mutta yleensä on olemassa joitakin eroja.
Ja sinun pitäisi katsoa GDB käsikirja.
Mutta tässä tapauksessa, ei mitään.
Meillä on tapana käyttää tulosta, mutta koska meidän ei tarvitse tehdä paljon enemmän kuin
tulostaa yksi arvo.
>> OK.
Joten olemme verkossa 80 meidän koodia, jossa solmu * As yhtä listaan.
Olkaamme tulostaa As.
Se on yhtä kuin lista.
Makea.
Odota.
Se vastaa jotain.
Tämä ei tunnu oikealta.
Siellä mennään.
Se johtuu vuonna GDB, oikealle, jos se viiva olet sitä
ei ole toteutettu vielä.
Joten sinun täytyy itse kirjoittaa vieressä suorittaa linja
ennen nähdä sen tulokset.
Joten tässä me olemme.
Olemme juuri suoritettua tätä linjaa, edellinen vastaa null.
Joten taas, jos me painamme edellinen emme tule näkemään mitään outoa.
Mutta jos me todella toimeksiannosta sen line, niin näemme
että linja toimi.
>> Joten meillä on As.
Nuo ovat molemmat hyviä.
Oikea?
Nyt olemme tätä linjaa täällä.
Vaikka As ei ole sama null.
No, mitä As tasa-arvoisia?
Me vain näki sen sivunnut null.
Me painettu sitä.
Minä tulostaa sen uudelleen.
Niin on, että kun silmukka menossa toteuttaa?
>> Yleisö: Ei.
>> JASON HIRSCHHORN: Eli kun olen kirjoittanut, että line, näet hyppäsimme koko matkan
pohjaan, return false.
Ja sitten me aiomme palauttaa false ja mene takaisin meidän ohjelmaan ja
lopulta tulostaa, kuten näimme, insertti ei onnistunut.
Joten, kellään mitään ideoita siitä, mitä meidän täytyy tehdä asian korjaamiseksi?
Aion odottaa kunnes näen pari kädet nousevat.
Emme suorita tämä.
Pidä mielessä, tämä oli ensimmäinen asia olimme tekemässä.
En aio tehdä pari.
Aion tehdä muutamia.
Koska pari tarkoittaa kahta.
Odotan enemmän kuin kaksi.
>> Ensimmäinen lisäys, As, oletuksena on yhtä kuin nolla.
Ja tämä silmukka pannaan täytäntöön ainoastaan jos As ei ole nolla.
Joten miten saan kiertää tämän?
Näen kolme kättä.
Odotan enemmän kuin kolme.
Marcus, mitä luulet?
>> Yleisö: No, jos tarvitset sitä suorittaa useammin kuin kerran, juuri
muuttaa sen do-while-silmukka.
>> JASON HIRSCHHORN: OK.
Onko tämä ratkaista ongelmamme, vaikka?
>> Yleisö: Tässä tapauksessa ei, koska että lista on tyhjä.
Joten sinulla todennäköisesti tarvitsee vain lisätä maininta siitä, että jos silmukka uloskäynnit
Sitten sinun täytyy olla lopussa luettelossa, jolloin sinun
voi vain lisätä sitä.
>> JASON HIRSCHHORN: Pidän siitä.
Siinä on järkeä.
Jos silmukka poistuu -
koska se tulee palauttaa false täällä.
Joten jos silmukka poistuu, niin me olemme listan loppuun, tai ehkä
alkuun lista, jos ei ole mitään, se, mikä on sama kuin lopussa.
Joten nyt haluamme lisätä jotain.
Joten miten se koodi näyttää, Marcus?
>> Yleisö: Jos olet jo saanut solmun malloced, voit vain sanoa
new_node-> seuraava vastaa null koska sen täytyy olla lopussa.
Tai new_node-> seuraava vastaa null.
>> JASON HIRSCHHORN: OK.
Anteeksi.
New_node-> next vastaa null koska olemme lopussa.
Tämä ei laita se sisään
Miten me laittaa sen listan?
Oikea.
Se on vain asettamalla se sama.
Ei miten me oikeastaan laita se lista?
Mitä osoittaa listan loppuun?
>> Yleisö: Head.
>> JASON HIRSCHHORN: Anteeksi?
>> Yleisö: Head osoittaa loppuun luettelon.
>> JASON HIRSCHHORN: Jos ei mitään lista, pää on osoittaa
luettelon loppuun.
Niin että saat työtä ensin paikoilleen.
Entä jos on pari asioita luettelossa?
Kuin emme halua asettaa suunnata yhtä new_node.
Mitä haluamme tehdä siellä?
Joo?
Luultavasti edellinen.
Onko tämä toimii?
Muista, että edellinen on vain osoitin solmuun.
Ja edellinen on paikallinen muuttuja.
Joten tämä linja asettaa paikallinen muuttuja, edellinen, yhtä suuri tai
osoittavat tähän uuteen solmuun.
Se ei oikeastaan ​​laittaa sen listallamme, vaikka.
Miten me laittaa se lista?
Akchar?
>> Yleisö: Mielestäni sinun do nykyinen-> seuraava.
>> JASON HIRSCHHORN: OK.
As-> seuraava.
Joten jälleen, ainoa syy olemme alas tässä on, mitä nykyinen tasa-arvoisia?
>> Yleisö: Yhtä null.
>> JASON HIRSCHHORN: Ja niin mitä tapahtuu, jos teemme null-> seuraavaksi?
Mitä menossa?
Saamme segmentointi vika.
>> Yleisö: Do As vastaa null.
>> JASON HIRSCHHORN: Se on sama asia kuten edell, vaikka, koska siellä on
paikallinen muuttuja olemme arvostelemassa yhtä suuri kuin tämä uusi solmu.
Mennään takaisin meidän kuva lisäämällä jotain.
Sano olemme työntämällä lopussa luettelon, niin täällä.
Meillä on osoittimen, joka on osoittaa null ja edelliseen kohtaan
joka osoittaa 8.
Joten mitä meidän täytyy päivittää, Avi?
>> Yleisö: Edellinen-> seuraavaksi?
>> JASON HIRSCHHORN: Edellinen-> seuraava on mitä haluamme päivittää koska
todella aseta se luettelon loppuun.
Meillä on vielä yksi vika, vaikka, että aiomme törmätä.
Mikä tämä bugi?
Joo?
>> Yleisö: Se tulee palauttaa false tässä tapauksessa?
>> JASON HIRSCHHORN: Voi, on on aio palata vääriä.
Mutta on toinenkin bugi.
Joten meidän täytyy laittaa vastineeksi totta.
>> Yleisö: Onko edellinen edelleen samanlaiset nollamuotoja listan kärjessä?
>> JASON HIRSCHHORN: So edellinen vielä vastaa null aivan alussa.
Joten kuinka voimme päästä yli siitä?
Joo?
>> Yleisö: Mielestäni voit tehdä tarkastus ennen kun silmukka nähdä, jos se on
tyhjä lista.
>> JASON HIRSCHHORN: OK.
Joten mennään täällä.
Tehdä tarkastus.
Jos -
>> Yleisö: Joten jos pää vastaa yhtä kuin nolla.
>> JASON HIRSCHHORN: Jos pää vastaa yhtä kuin nolla -
että saat kertoa meille, jos se on tyhjä lista.
>> Yleisö: Ja sitten tehdä pää vastaa uutta.
>> JASON HIRSCHHORN: Head vastaa new_node?
Ja mitä muuta meidän täytyy tehdä?
>> Yleisö: Ja sitten palaat totta.
>> JASON HIRSCHHORN: Ei aivan.
Puuttuu yksi askel.
>> Yleisö: New_node seuraava on viitata null.
>> JASON HIRSCHHORN: Aivan, Alden.
Ja sitten voimme palata totta.
OK.
Mutta se on silti hyvä idea tehdä asioita lopussa listan, eikö?
Selvä.
Meillä on vielä ehkä itse saada loppuun luettelon.
Joten tämä koodi hienoa, jos me olemme luettelon loppuun ja joitakin
asioita luettelossa?
Oikea?
Koska meillä on vielä Marcus idea.
Voisimme poistua tämän silmukan, koska me olemme listan loppuun.
Joten me silti halua tätä koodin tänne?
>> Yleisö: Kyllä.
>> JASON HIRSCHHORN: Joo.
Ja mitä meidän täytyy muuttaa tätä?
Totta.
Kuulostaako hyvältä kaikille tähän mennessä?
Kellään mitään -
Avi, onko sinulla jotain lisättävää?
>> Yleisö: Ei.
>> JASON HIRSCHHORN: OK.
Joten olemme tehneet pari muutoksia.
Olemme tehneet tämän valintaruudun ennen kuin mentiin tyhjän listan.
Niinpä olemme ottaneet huolta tyhjän listan.
Ja tässä me hoiti lisäämällä jotain listan loppuun.
Joten näyttää siltä että kun silmukka ottaen hoitaa asioita välillä,
jossain luetteloon, jos ovat asioita luettelossa.
>> OK.
Olkaamme suorittaa tämän ohjelman uudelleen.
Ei onnistunut.
>> Yleisö: Et tehnyt sitä.
>> JASON HIRSCHHORN: Oh, En tehnyt sitä.
Hyvä pointti, Michael.
Katsotaanpa lisätä make toisiinsa.
Linja 87 on virhe.
Linja 87.
Alden, tämä oli linjan annoit minulle.
Mikä hätänä?
>> Yleisö: Sen täytyy olla null.
>> JASON HIRSCHHORN: Erinomainen.
Aivan oikein.
Sen pitäisi olla tyhjä.
Tehdään uudestaan.
Koota.
OK.
Katsotaanpa aseta kolme.
Insertti oli onnistunut.
Katsotaanpa tulostaa sen.
Voi, kunpa voisimme tarkistaa.
Mutta emme ole tehneet tulostaa toiminto vielä.
Katsotaanpa tulla jotain muuta.
Mitä meidän pitäisi tehdä?
>> Yleisö: Seitsemän.
>> JASON HIRSCHHORN: Seven?
>> Yleisö: Kyllä.
>> JASON HIRSCHHORN: Meillä on seg vika.
Joten saimme yhden, mutta olemme selvästi ei voi saada kaksi.
Se on 05:07.
Jotta voisimme debug kolme minuuttia.
Mutta aion jättää meidät täällä ja siirtyä hash taulukoita.
Mutta jälleen kerran, vastauksia tämän koodin Aion lähettää sen sinulle vähän.
Olemme hyvin lähellä sitä.
Olen erittäin rohkaista teitä selvittää mitä täällä tapahtuu ja korjata sen.
Joten saat sähköpostiviestin, tämän koodin hyvin plus ratkaisu -
luultavasti ratkaisu myöhemmin.
Aluksi tämä koodi.
>> Toiseksi haluan tehdä ennen kuin Viimeistely on emme ole vapautettu mitään.
Joten haluan näyttää mitä valgrind näyttää.
Jos otamme valgrind rajoja ohjelmastamme,. / linkitetty.
Jälleen mukaan tämän dian, me pitäisi ajaa valgrind jonkinlaisella
vaihtoehto, tässä tapauksessa - Vuoto-check = täynnä.
Joten kirjoittaa valgrind - Vuoto-check = täynnä.
Joten tämä jatkuu valgrind ohjelmastamme.
Ja nyt ohjelma todella toimii.
Joten aiomme käyttää sitä aivan kuten ennen, laittaa jotain sisään
Aion laittaa kolme.
Joka toimii.
En aio yrittää laittaa jotain muu, koska aiomme
saada seg väärä tässä tapauksessa.
Joten olen juuri menossa lopettaa.
>> Ja nyt näet täällä vuotaa ja läjä yhteenveto.
Nämä ovat hyviä asioita, joita haluat tarkistaa.
Joten kasaan yhteenveto - sanotaan, käytössä Exit - kahdeksan tavua yhdessä lohkossa.
Että yksi lohko on solmu me malloced.
Michael, sanoit ennen solmu on kahdeksan puremat, koska se on kokonaisluku
ja osoitin.
Niin, että meidän solmu.
Ja sitten se sanoo käytimme malloc seitsemän kertaa ja me vapautti
jotain kuusi kertaa.
Mutta emme koskaan kutsutaan vapaaksi, joten minulla ei ole aavistustakaan, mitä tämä puhuu.
>> Mutta riittää kun sanon, että kun Ohjelma toimii, malloc on kutsuttu
Joissakin muissa paikoissa, että me ei tarvitse murehtia.
Joten malloc oli luultavasti nimeltään paikoin.
Meidän ei tarvitse huolehtia, jos.
Mutta tämä on todella meille.
Tämä ensimmäinen rivi on meille.
Jätimme että lohko.
Ja voit nähdä, että täällä Vuotoalttiiseen yhteenveto.
Edelleen tavoitettavissa -
kahdeksan tavua yhdessä lohkossa.
Tämä tarkoittaa, että muisti -
olemme vuotanut että muisti.
Menettänyt lopullisesti -
jotain on menetetty lopullisesti.
Yleensä, et nähdä mitään siellä.
Silti tavoitettavissa on yleensä silloin näet asioita, missä sinun kannattaa
katsomme, mitä koodia sinun pitäisi vapauttanut mutta unohdit vapauttaa.
>> Ja sitten jos tämä ei pidä paikkaansa, jos teimme ilmaiseksi kaiken,
voimme tarkistaa, että.
Katsotaanpa vain ajaa ohjelman ei hoida mitään.
Näet täällä käytössä exit -
nolla tavua nolla lohkot.
Se tarkoittaa, että ei ollut mitään jäljellä kun tämä ohjelma lähtenyt.
Joten ennen kääntymistä pset6, ajaa valgrind ja varmista, että sinulla ei ole
mitään muistivuotoja omassa ohjelmassa.
Jos sinulla on kysyttävää kanssa valgrind, rohkeasti tavoittaa.
Mutta tämä on, miten käytät sitä.
Hyvin yksinkertainen - katso jos on käytössä exit -
mitään bytes missään lohkoja.
>> Joten me työskentelimme insert solmuun.
Minulla oli kaksi muita toimintoja täällä - tulostaa solmut ja vapaa solmut.
Jälleen, nämä ovat toimintoja, jotka ovat olemaan hyvä voit harjoitella
koska ne auttavat sinua ei vain Näiden näyte harjoituksia, mutta myös
ongelmasta asetettu.
He kartta melko tiiviisti asioita olet menossa täytyy tehdä
Harjoitus.
Mutta haluan olla varma kosketamme kaikesta.
Ja hash taulukot ovat myös ratkaisevia mitä teemme osassa tässä
viikko - tai ongelman asetettu.
>> Joten aiomme lopettaa osio puhumme hash taulukoita.
Jos huomaat tein pikku tiiviste.
Se ei ole sitä mitä me puhumme noin kuitenkin.
Puhumme eri tyyppi hash taulukoita.
Ja sen ytimessä, tiiviste ei ole mitään muuta kuin
array plus hajautusfunktio.
Aiomme puhua vähän vain Varmista jokainen ymmärtää, mitä
hash funktio on.
Ja minä kerron teille nyt, että se on mitään muuta kuin kaksi asiaa -
array ja hajautusfunktio.
Ja tässä ovat vaiheet läpi jota tämä toimii.
>> On meidän array.
On meidän tehtävämme.
Erityisesti hash-toimintoja on tehdä pari asiaa tähän.
Aion puhua erityisesti tästä ongelmasta asetettu.
Se on luultavasti menossa toteuttaa merkkijono.
Ja mitä se aio palata?
Mitä tietoja tyyppi?
Alden?
Sinun hajautusfunktio palata?
Kokonaisluku.
Joten tämä on mitä hash Taulukko koostuu -
taulukon muodossa array ja hash-funktiota.
Miten se toimii?
Se toimii kolmessa vaiheessa.
Annamme sille avaimen.
Tässä tapauksessa annamme sen merkkijono.
Vaadimme hajautusfunktio askelta kohti yksi keskeisistä ja saamme arvon.
>> Erityisesti me sanomme saamme kokonaisluku.
Että kokonaisluku, on erittäin konkreettisia rajansa, että kokonaisluku voi olla.
Tässä esimerkissä meidän array on kooltaan kolme.
Niin mitä numeroita voi että kokonaisluku olla.
Mikä on monia päteviä arvoja että kokonaisluku, palautuva tämän
hajautusfunktio?
Nolla, yksi ja kaksi.
Piste hash tehtävänä on selvittää paikka array
missä avain on menossa.
On vain kolme mahdollista paikkoja täällä -
nolla, yksi tai kaksi.
Joten tämä toiminto paremman tuoton nolla, yksi tai kaksi.
Jotkut voimassa Indice tässä array.
>> Ja sitten riippuen siitä, missä se palaa, näette array auki
teline arvo.
Se kun laitoimme näppäintä.
Joten me heittää kurpitsa, pääsemme pois nolla.
Klo array kiinnike 0, laitamme kurpitsa.
Heitämme kissoilla, saamme yhden.
Laitoimme kissan yhdessä.
Laitamme hämähäkki.
Saamme kaksi.
Laitoimme hämähäkki array kiinnike kaksi.
Olisi niin mukavaa, jos se toimi niin.
Mutta valitettavasti, kuten tulemme näkemään, se on hieman monimutkaisempi.
>> Ennen kuin pääsemme sinne, kysyttävää tästä perus
set-up of hajautustaulun?
Tämä kuva on täsmälleen mitä me kiinnitti taululle.
Mutta koska me veti sen hallituksessa, I aio mennä sitä pidemmälle.
Pohjimmiltaan avaimet, magiaa musta laatikko - tai tässä tapauksessa, turkoosi laatikko - of
hajautusfunktio laittaa ne kauhat.
Ja tässä esimerkissä olemme ei hoida nimeä.
Laitamme liittyy puhelimen määrä nimen ämpäri.
Mutta voit hyvin juuri laita nimi ämpäri.
>> Tämä on vain kuva siitä, mitä me veti taululle.
Meillä on karikot, vaikka.
Ja siellä on kaksi erityisesti liukuu, että haluan mennä yli.
Ensimmäinen on noin hash-funktio.
Kysyin kysymyksen, mitä tekee hyvän hajautusfunktio?
Annan kaksi vastausta.
Ensimmäinen on se, että se on deterministinen.
Yhteydessä hash toimintoja, Mitä tämä tarkoittaa?
Kyllä?
>> Yleisö: Se voi löytää index jatkuvassa aikaa?
>> JASON HIRSCHHORN: Tämä ei ole sitä mitä se tarkoittaa.
Mutta se on hyvä arvaus.
Kukaan muu ole arvaus mitä tämä tarkoittaa?
Että hyvä hajautusfunktio on deterministinen?
Annie?
>> Yleisö: Tuo avain voidaan kartoittaa yhteen paikkaan tiiviste.
>> JASON HIRSCHHORN: Tuo Aivan oikein.
Joka kerta kun laittaa kurpitsa, se palauttaa aina nolla.
Jos laitat kurpitsan ja hash funktio palauttaa nolla, mutta on
todennäköisyys palata jotain muu suurempi kuin nolla -
joten ehkä se voi palauttaa yhden joskus tai kaksi muuta kertaa -
joka ei ole hyvä hash-funktio.
Olet aivan oikeassa.
Sinun hash funktio palauttaa täsmälleen sama kokonaisluku, tässä tapauksessa, sillä
täsmälleen sama merkkijono.
>> Ehkä se palaa täsmälleen sama kokonaisluku varten täsmälleen sama merkkijono
riippumatta arvo.
Mutta tässä tapauksessa se on edelleen deterministinen koska useita asioita
mapataan sama arvo.
Se on hyvä.
Niin kauan kuin on vain yksi lähtö annetulle tulolle.
>> OK.
Toinen asia on, että se palauttaa voimassa indeksit.
Me esille, että aikaisemmin.
Tämä hajautusfunktio -
oh boy -
hajautusfunktio olisi palata voimassa indeksit.
Sano -
mennään takaisin tähän esimerkkiin.
Oma hajautusfunktio laskee ylös kirjaimet sana.
Se hajautusfunktio.
Ja kannattavuus kokonaisluku.
Joten jos minulla on sana, se on aio palata yhteen.
Ja se tulee laittaa täällä.
Mitä jos laitan sanan lepakko?
Se tulee palauttaa kolme.
Mistä bat mennä?
>> Se ei sovi.
Mutta se on mentävä jonnekin.
Tämä on minun hajautustaulun kun kaikki, ja kaiken pitää mennä jonnekin.
Joten missä pitäisi bat mennä?
Mitään ajatuksia?
Arvauksia?
Hyvä arvauksia?
>> Yleisö: Zero.
>> JASON HIRSCHHORN: Miksi nolla?
>> Yleisö: Koska kolme modulo kolme on nolla?
>> JASON HIRSCHHORN: Three modulo kolme on nolla.
Se on suuri arvaus, ja se on oikein.
Joten tässä tapauksessa se olisi luultavasti mennä nolla.
Joten hyvä tapa varmistaa, että tämä hash funktio palauttaa vain voimassa indeksien
modulo sen pöydän koko.
Jos modulo mitä tämän tuottoa kolme, olet aina menossa
jotain välillä nolla, yksi ja kaksi.
Ja jos tämä palaa aina seitsemän, ja aina modulo kolme, olet
aina menossa sama asia.
>> Joten se on vielä deterministinen jos modulo.
Mutta se varmistaa, että sinulla koskaan saada jotain -
kelpaa teollisuudelle.
Yleensä että modulo pitäisi tapahtua sisällä hajautusfunktio.
Joten sinun ei tarvitse huolestua.
Et vain voi varmistaa, että tämä on voimassa Indice.
Kysyttävää tästä potentiaali sudenkuoppa?
>> OK.
Ja siellä mennään.
Seuraava potentiaalinen sudenkuoppa, ja tämä on iso.
Mitä jos kaksi avainta kartta sama arvo?
Joten on olemassa kaksi tapaa käsitellä tätä.
Ensimmäinen on nimeltään lineaarinen hyvää, jonka minä olen
ei mennä yli.
Mutta sinun pitäisi olla perehtynyt miten joka toimii ja mitä se on.
>> Toinen aion mennä yli koska se on yksi että monet
ihmiset luultavasti lopulta päättää käyttää heidän ongelmansa asetettu.
Tietenkin, sinun ei tarvitse.
Mutta ongelma asetettu, monet ihmiset valitsevat yleensä luoda tiiviste
erillisellä ketjutus toteuttaa heidän sanakirja.
Joten aiomme mennä yli, mitä se tarkoittaa luoda hash taulukon
erillinen ketjutus.
>> Joten laitoin kurpitsa.
Se palauttaa nolla.
Ja laitoin kurpitsan täällä.
Sitten laitoin -
mitä toinen Halloween-teemalla juttu?
>> Yleisö: Candy.
>> JASON HIRSCHHORN: Candy!
Se on suuri.
Laitoin karkkia ja karkkia antaa minulle myös nolla.
Mitä teen?
Onko ideoita?
Koska te kaikki tavallaan tietävät mitä erillinen ketjutus on.
Joten mitään ideoita mitä tehdä?
Joo.
>> Yleisö: Putting merkkijono todella tiiviste.
>> JASON HIRSCHHORN: Niin aiomme piirtää hyvä idea tänne.
OK.
>> Yleisö: Onko hashtable [Äänetön]
osoitin, joka osoittaa alussa lista.
Ja sitten on kurpitsa olla ensimmäinen arvo että linkitetty lista ja karkkia olla
toinen arvo kyseisessä linkitetty lista.
>> JASON HIRSCHHORN: OK.
Marcus, joka oli erinomainen.
Aion rikkoa että alas.
Marcus sanoo ei korvata kurpitsan.
Se olisi huono.
Älä laita karkkia jossain muualla.
Aiomme laittaa ne molemmat nollassa.
Mutta aiomme käsitellä tekee heidät nolla
laatimalla luettelo nolla.
Ja aiomme luoda luettelon kaiken, kartoitettu nollaan.
Ja paras tapa opimme luoda lista, joka voi kasvaa ja kutistua
dynaamisesti ei kuulu toinen array.
Joten ei moniulotteinen array.
Mutta vain luoda linkitetyn listan.
>> Joten mitä hän ehdotti -
Aion saada uusi -
on luoda array osoittimia, joukko osoittimia.
OK.
Idea tai vihje, mitä tyyppiä Tämän viitteitä pitäisi olla?
Marcus?
>> Yleisö: Osoittimet -
>> JASON HIRSCHHORN: Koska sinä sanoi linkitetty lista, joten -
>> Yleisö: Node viitteitä?
>> JASON HIRSCHHORN: Node viitteitä.
Jos asiat meidän sidoksissa luettelossa ovat solmut sitten he
pitäisi olla solmu viitteitä.
Ja mitä he equal aluksi?
>> Yleisö: Null.
>> JASON HIRSCHHORN: Null.
Joten ei meidän tyhjä juttu.
Kurpitsa palaa nolla.
Mitä teemme?
Kävellä minua läpi?
Oikeastaan, Marcus jo antoi minulle.
Joku muu kävellä minua läpi.
Mitä me teemme, kun me -
tämä näyttää hyvin samankaltainen mitä olimme juuri tekemässä.
Avi.
>> Yleisö: Aion arvata.
Joten kun saat karkkia.
>> JASON HIRSCHHORN: Joo.
No, saimme kurpitsa.
Mennään meidän ensimmäinen.
Saimme kurpitsa.
>> Yleisö: OK.
Kurpitsa palaa nolla.
Niin laitat sen siihen.
Tai oikeastaan, laitat sen vuonna linkitetty lista.
>> JASON HIRSCHHORN: Miten me laita se linkitetty lista?
>> Yleisö: Voi, todellinen syntaksi?
>> JASON HIRSCHHORN: Vain kävellä -
sanoa enemmän.
Mitä teemme?
>> Yleisö: Sinä vain lisätä että se on ensimmäinen solmu.
>> JASON HIRSCHHORN: OK.
Joten meillä on solmu, kurpitsa.
Ja nyt, miten voin asettaa sen?
>> Yleisö: Voit määrittää sen osoittimen.
>> JASON HIRSCHHORN: Mikä osoitin?
>> Yleisö: osoitin nollaan.
>> JASON HIRSCHHORN: Missä ei tässä vaiheessa?
>> Yleisö: nollaamaan juuri nyt.
>> JASON HIRSCHHORN: No, se osoittaa null.
Mutta olen ottamassa kurpitsa.
Joten missä on se kohta?
>> Yleisö: kurpitsan.
>> JASON HIRSCHHORN: To kurpitsa.
Täsmälleen.
Joten tämä viittaa kurpitsan.
Ja jos tämä osoitin kurpitsa vaiheessa?
Jos haluat
>> Yleisö: Null.
>> JASON HIRSCHHORN: NULL.
Täsmälleen.
Joten me vain lisätään jotain osaksi linkitetty lista.
Me vain kirjoitti tämän koodin tehdä tämän.
Lähes me melkein sain sen täysin säröillä.
Nyt lisäämme karkkia.
Meidän karkkia myös menee nollaan.
Joten mitä teemme karkkia?
>> Yleisö: Se riippuu siitä, onko ei me yritetään järjestää sitä.
>> JASON HIRSCHHORN: Tuo Aivan oikein.
Se riippuu siitä, onko vai ei Yritämme järjestää sen.
Oletetaan, emme ole menossa lajitella.
>> Yleisö: No sitten, kun me keskustelimme ennen, se on yksinkertaisin vain laittaa se
heti alussa niin osoitin nollasta pistettä karkkia.
>> JASON HIRSCHHORN: OK.
Pidä kiinni.
Saanen luoda karkkia täällä.
Joten tämä osoitin -
>> Yleisö: Joo, pitäisi nyt osoittavan karkkia.
Sitten osoitinta karkkia kohta kurpitsa.
>> JASON HIRSCHHORN: Näinkö?
Ja sanoa saimme toisen asia kartta nollaan?
>> Yleisö: No, sinä vain tehdä sama asia?
>> JASON HIRSCHHORN: Tee sama asia.
Joten tässä tapauksessa, jos emme haluamme pitää sen lajitellaan se
kuulostaa melko yksinkertainen.
Otamme osoitin Indice antama meidän hajautusfunktio.
Meillä on tältä osin meidän uuteen solmuun.
Ja sitten mitä se oli suunnattu aiemmin -
Tässä tapauksessa null, vuonna Toisessa tapauksessa kurpitsa -
että, mikä sen osoittaa aiemmin, lisäämme seuraavaan ja
meidän uusi solmu.
Olemme laittamalla jotain alussa.
Itse asiassa tämä on paljon yksinkertaisempi kuin yrittää pitää luetteloa järjestetty.
Mutta jälleen kerran, haku on monimutkaisempia täällä.
Me aina mennä loppuun.
>> OK.
Kysyttävää erillinen ketjutus?
Miten se toimii?
Pyydä heitä nyt.
En todellakaan halua varmista, että kaikki ymmärtää tämä ennen kuin pää pois.
>> Yleisö: Miksi laitat kurpitsan ja karkkia samaan
osa tiiviste?
>> JASON HIRSCHHORN: Hyvä kysymys.
Miksi me panemme ne samaan osa tiiviste?
No, tässä tapauksessa meidän hajautusfunktio palaa nolla molemmille.
Joten ne täytyy mennä Indice nolla koska sinne olemme menossa
etsiä niitä, jos me koskaan halua etsiä niitä.
Jälleen kerran lineaarinen luotaa lähestymistapa emme laita ne molemmat nollassa.
Mutta erillisessä lähestymistavan ohella aiomme laittaa ne molemmat nollassa
ja sitten luoda listan pois nolla.
>> Emmekä halua korvata kurpitsan yksinkertaisesti, että koska sitten me
olettaa, että kurpitsa oli koskaan lisätä.
Jos me vain pitää yksi asia paikkaan, joka olisi huono.
Sitten ei olisi mahdollisuus meistä koskaan -
jos meillä koskaan ollut kahtena sitten olisi vain pyyhkiä alkuperäisestä arvosta.
Joten siksi me teemme tätä lähestymistapaa.
Tai siksi valitsimme - mutta jälleen kerran, me valitsi erillinen ketjutus lähestymistapaa,
joka on olemassa monia muita lähestymistapoja voisi valita.
Vastaako tuo kysymykseesi?
>> OK.
Carlos.
Lineaarinen luotaa kuuluisi -
jos löysimme törmäys nolla, me näyttäisi seuraavan paikka nähdä, jos
se oli auki ja laittaa sen sinne.
Ja sitten katsomme ensi urheilun ja katso jos se oli auki ja laittaa sen sinne.
Joten löydämme seuraavan käytettävissä avoin paikka ja laittaa sen sinne.
Muuta kysyttävää?
Joo, Avi.
>> Yleisö: Koska jatkoa, että mitä tarkoitat ensi paikalla?
Hash taulukon tai linkitetyn listan.
>> JASON HIRSCHHORN: For lineaarinen ohjelmointia, ei liity luetteloita.
Seuraavan paikalla tiiviste.
>> Yleisö: OK.
Joten tiiviste olisi alustetaan koko -
kuten määrä jouset että olit lisäämällä?
>> JASON HIRSCHHORN: Olisitte haluat sen olevan todella iso.
Kyllä.
Tässä on kuva siitä, mitä me vain piirsi taululle.
Jälleen meillä törmäyksen täällä.
klo 152.
Ja näet loimme linkitetty lista pois siitä.
Jälleen tiiviste erillinen ketjutus lähestymistapa ei ole yksi sinun
on otettava ongelmiin asetettu kuusi, mutta on yksi, joka on paljon
opiskelijat taipumus ottaa.
Joten muistiossa Puhutaanpa lyhyesti ennen kuin pää pois noin ongelma kuusi,
ja sitten Jaan teille tarinan.
Meillä on kolme minuuttia.
>> Harjoitus kuusi.
Sinulla on neljä toimintoa -
kuormitus, tarkista, koko ja purkaa.
Kuormitus -
No, olemme menossa Ylikuormitus juuri nyt.
Me kiinnitti kuormitus aluksella.
Ja me edes aloitettu koodaus paljon lisäämällä osaksi linkitetty lista.
Joten kuormitus ei ole paljon enemmän kuin mitä olemme juuri tehneet.
>> Check on kun olet jotain ladattu.
Se on sama prosessi kuin tämä.
Sama kaksi ensimmäistä osaa, jossa heität jotain osaksi hajautusfunktio
ja saada sen arvo.
Mutta nyt emme asetat sen.
Nyt etsimme sitä.
Olen mallikoodi kirjoitettu löytämiseen jotain linkitetty lista.
Kannustan teitä harjoitella sitä.
Mutta intuitiivisesti löytää jotain melko samanlainen kuin lisäämällä jotain.
Todellakin, me piirsi kuvan löytää jotain linkitetty lista, liikkuvat
kautta, kunnes pääsi loppuun.
Ja jos sinulla loppuun eikä voinut löytää sen, niin se ei ole siellä.
Niin, että tarkastus, lähinnä.
>> Seuraava on koko.
Hypätään koko.
Lopulta olet purkaa.
Kevennys on yksi emme ole laadittu taululle tai koodattu vielä.
Mutta kehotan teitä kokeilemaan koodaus sitä meidän näyte linkitetty lista esimerkki.
Mutta purkaa intuitiivisesti on samanlainen kuin vapaa -
tai Tarkoitan on samanlainen tarkistaa.
Paitsi nyt joka kerta olet menossa kautta, et ole vain tarkkailun
katso jos sinulla on arvoa siellä.
Mutta olet ottaen, että solmu ja vapauttaa se lähinnä.
Sitähän purkaa pyytää sinua tekemään.
Vapaa kaiken, mitä olet malloced.
Joten olet menossa läpi koko lista jälleen läpi koko hash
taulukko uudelleen.
Tällä kertaa eivät tarkista nähdä mitä siellä.
Vain vapauttaa mitä siellä.
>> Ja lopuksi koko.
Koko olisi pantava täytäntöön.
Jos et toteuttaa koko -
Sanon sen näin.
Jos et toteuttaa koko täsmälleen yhtä riviä koodia lukien
palata selvitys, olet tekee koko väärin.
Joten varmista koko, täydellinen suunnittelu pistettä, teet sen tasan
rivi koodia, mukaan lukien return-lausetta.
>> Ja älä pakata vielä, Akchar.
Eager Beaver.
Halusin sanoa kiitos kaverit tulit osassa.
On Happy Halloween.
Tämä on minun puku.
Tulen päällään tämä torstaina jos näen sinut virka.
Ja jos olet utelias lisää pohjalla kuin tähän puku, tuntuu
vapaasti tarkistaa 2011 osiossa varten tarina miksi olen
yllään kurpitsa puku.
Ja se on surullinen tarina.
Joten varmista, että sinulla on nenäliinoja lähistöllä.
Mutta että, jos sinulla on kysymykset Jään
ulkopuolella jakson jälkeen.
Onnea ongelma asetettu kuusi.
Ja kuten aina, jos sinulla on kysymyksiä, haluaisin tietää.