[Musiikki soi] SPEAKER 1: Selvä. Kaikki tervetulleita takaisin osiosta. Toivottavasti kaikki ovat onnistuneesti toipunut tietokilpailun viime viikolla. Tiedän, että se on hieman hullu joskus. Kuten sanoin aiemmin, jos olet sisällä keskihajonta, eivät oikeastaan ​​välitä siitä, erityisesti ja vähemmän mukava jakso. Se siitä, missä sinun pitäisi olla. Jos teit suurta, niin mahtava. Kunnia teille. Ja jos tuntuu tarvitset hieman enemmän apua, ole hyvä rohkeasti päästä ulos tahansa TF: iä. Olemme kaikki täällä auttamassa. 

Siksi me opetamme. Siksi olen täällä joka maanantai sinulle kaverit ja virka torstaisin. Joten ota rohkeasti kertoa minulle jos olet huolissasi mitään tai jos on mitään tietokilpailu että haluat todella puuttua. 

Joten tämän päivän esityslistaa on kaikki noin tietorakenteita. Jotkut näistä ovat vain olemaan juuri saada sinut perehdytetään näitä. Et voi koskaan toteuttaa niitä tässä luokassa. Jotkut heistä tulet, kuten oman oikeinkirjoitusopas PSET. 

Sinulla on valintasi välillä hash taulukoita ja yrittää. Niin me varmasti menee yli ne. Se tulee olemaan varmasti enemmän laatuaan korkean tason jakso tänään, vaikka, koska siellä on paljon niitä, ja jos menimme toteutuksen yksityiskohdat kaikkia näitä, emme jopa saada läpi liittyvät luettelot ja ehkä hieman hash taulukoita. 

Niin vastaa minulle. Emme aio olla tekemässä niin paljon koodaus tällä kertaa. Jos sinulla on kysyttävää siitä tai haluat nähdä sen täytäntöön tai kokeile itse, Olen ehdottomasti suositella menossa study.cs50.net, joka on esimerkkejä kaikista näistä. Se täytyy minun PowerPoint kanssa toteaa, että me taipumus käyttää sekä joitakin ohjelmointi harjoituksia, erityisesti asioita kuten liittyvät luettelot ja binary Puut pinot ja vihjeitä. Joten hieman korkealla tasolla, mikä Voisi olla kiva teitä. 

Niin, että, me päästä alkuun. Ja myös, yes-- tietokilpailuja. Luulen, että useimmat teistä, jotka ovat Oma osio on tietokilpailuja, mutta joku tulee sisään tai jostain syystä ei, he ovat täällä edessä. 

Joten liittyvät luettelot. Tiedän tällainen menee takaisin ennen tietokilpailun. Se oli viikko ennen että olemme oppineet tästä. Mutta tässä tapauksessa, me vain Mene vähän enemmän syvyyttä. 

Joten miksi ehkä päätämme linkitetty lista yli array? Mikä erottaa ne? Kyllä? 

Yleisö: Voit laajentaa sidoksissa luetella vs. array: n kiinteä koko. SPEAKER 1: Oikea. Array on kiinteä koko taas linkitetty lista on vaihteleva koko. Joten jos emme tiedä miten paljon haluamme säilyttää, linkitetty lista antaa meille suuri tapa tehdä se, koska voimme vain lisätä toisen solmun ja lisäyksiä toinen solmu ja lisätä toiseen solmuun. Mutta mikä voisi olla kompromissi? Muistaako kukaan vaihtokauppa välillä paneelit ja liittyvät luettelot? Mmhmm? 

Yleisö: Sinun käydä läpi koko matkan kautta linkitetty lista löytää elementti luettelosta. Array, voit vain löytää elementti. 

SPEAKER 1: Oikea. Joten arrays-- 

Yleisö: [kuulumaton]. 

SPEAKER 1: Kun paneelit, meillä on mitä kutsutaan random access. Tarkoittaa, että jos me haluamme sitä, mitä on koskaan viidennen pisteen lista tai viides kohta meidän array, voimme vain napata se. Jos se on linkitetty lista, meillä on kerrata läpi, eikö? Joten pääsy elementin array on vakio aika, taas linkitetty lista se olisi todennäköisesti lineaarisen ajan, koska ehkä Meidän elementti on aina lopussa. Meidän täytyy etsiä kaikkea. Joten kaikki nämä tiedot rakenteet olemme menossa olla menoja hieman enemmän aikaa, mitä plussia ja negatiivit. Kun ehkä haluamme käyttää yksi yli muiden? Ja se on eräänlainen isompi asia ottaa pois. 

Joten meillä on täällä määritelmä solmun. Se on kuin yksi osa meidän linkitetty lista, eikö? Joten me kaikki tunnemme meidän typedef structs, josta menimme ohi tarkastelun viime kerralla. Se oli lähinnä vain luoda toinen tietotyyppi, että voisimme käyttää. 

Ja tässä tapauksessa, se on jonkin verran solmussa että pitää jotkut kokonaisluku. Ja mitä sitten on toinen osa täällä? Kukaan? 

Yleisö: [kuulumaton]. 

SPEAKER 1: Joo. Se on osoitin seuraavaan solmuun. Joten tämä pitäisi oikeastaan ​​olla täällä. Tämä on osoitin tyyppiä solmu seuraavaan asia. Ja sitähän he kattaa meidän solmu. Cool. 

Okei, joten haulla, koska olimme vain sanomalla ennen käsin, jos olet menossa etsiä, olet todella kerrata kautta linkitetty lista. Joten jos etsit numero 9, meillä alkaisi meidän pään ja joka osoittaa meille alussa meidän linkitetty lista, eikö? Ja me sanomme, OK, ei tämä solmu sisältää numero 9? Ei? 

Okei, siirry seuraavaan. Seuraa sitä. Sisältääkö se numero 9? Ei. Seuraa seuraavaan. 

Joten meidän on todella kerrata kautta linkitetty lista. Emme voi vain mennä suoraan jossa 9 on. Ja jos te todella haluavat nähdä joitakin pseudo-koodin sinne. Meillä on joitakin hakutoiminto täällä joka vie in-- mitä se aikoo ryhtyä? Mitä mieltä olet? Niin helppo. Mikä tämä on? Yleisö: [kuulumaton]. SPEAKER 1: numero etsimme. Oikea? Ja mitä tämä vastaa? Se on osoitin? 

Yleisö: solmu. 

SPEAKER 1: solmun listaan että me tarkastelemme, eikö? Joten meillä on joitakin solmut ovat osoittimen täällä. Tämä on seikka, joka tulee todella kerrata kautta listallamme. Asetimme se sama listata koska se on vain jossa se on yhtä suuri kuin alkaa meidän linkitetty lista. 

Ja vaikka se ei ole nolla, kun taas meillä on vielä asioita listallamme, tarkista, että solmulla on numero etsimme. Return true. Muuten, päivittää sitä, eikö? 

Jos se on tyhjä, me poistu meidän while-silmukka ja return false koska se tarkoittaa, että emme ole löytäneet sitä. Onko kaikki saavat miten se toimii? OK. 

Joten ollen sinun on kolme eri tapaa. Voit liittää alkuun, voit liittää ja voit lisätä lajitelma. Tässä tapauksessa olemme aikoo tehdä prepend. Tietääkö kukaan miten nämä kolmessa tapauksessa saattaa vaihdella? 

Niin prepend tarkoittaa, että laitat se edessä listasi. Niin se tarkoittaisi, että ei väliä mitä solmu on, ei väliä mitä arvo on, olet menossa laittaa se täällä edessä, OK? Se tulee olemaan ensimmäinen elementti luettelosta. 

Jos liität sen, se tulee mennä takaisin listasi. Ja työnnä lajitelma tarkoittaa olet aio laittaa itse siihen paikkaan jos se pitää linkitetty lista järjestetty. Jälleen, miten käytät ne ja kun käytät ne vaihtelevat teidän tapauksessa. Jos se ei tarvitse lajitellaan, prepend yleensä olla mitä useimmat ihmiset käyttää, koska et täytyy käydä läpi koko lista löytää lopulta lisätä sen, eikö? Voit vain kiinni se oikein. 

Joten me menemme läpi lisäys 1 juuri nyt. Niin yksi asia, että aion Suosittelemme tätä PSET on kiinnittää asioita, kuten aina. On hyvin tärkeää, että päivität sinun viitteitä oikeassa järjestyksessä koska jos ne ajan tasalle hieman epäkunnossa, aiot päätyä menettää osia listasi. 

Niin esimerkiksi tässä tapauksessa olemme kertoo pää vain pisteen 1. Jos me vain tehdä tallentamatta tähän 1, meillä ei ole aavistustakaan, mitä 1 pitäisi osoittaa nyt koska olemme menettäneet mitä pää huomautti. Niin yksi asia muistaa kun olet tekemässä prepend on pelastaa mitä pää osoittaa ensin, sitten siirtää sen, ja sitten päivittää mitä uusi solmu pitäisi osoittaa. Tässä tapauksessa tämä on yksi tapa tehdä se. 

Joten jos olisimme tehneet sen tällä tavalla jos me vain osoittaa uudelleen pää, menetämme pohjimmiltaan meidän Koko lista, eikö? Yksi tapa tehdä se on saada 1 pisteen seuraava, ja sitten on pää kohta 1. Tai voit tehdä ikään kuin väliaikainen varastointi, joka puhuin. 

Mutta uudelleen kohdentamisesta sinun osoittimet oikeassa järjestyksessä tulee olemaan hyvin, hyvin tärkeää, että tämä PSET. Muuten, olet menossa on hash pöytä tai kokeilla, joka on juuri olemaan vain osa sanoista haluavat ja sitten you're-- mmhmm? Yleisö: Mikä oli väliaikainen varastointi asia puhuit? SPEAKER 1: väliaikainen varastointi. Joten periaatteessa toisen Tavallaan voisi tehdä tämän on tallentaa johtaja jotain, kuten säilytä se väliaikainen muuttuja. Määrittää sen 1 ja sitten päivittää 1 kohtaan mihin tahansa pään käytetään osoittamaan. Tällä tavalla on ilmeisesti enemmän tyylikäs, koska olet ei tarvita tilapäisen arvon, mutta vain tarjoamalla toinen tapa tehdä se. Ja emme oikeastaan ​​ole Joissakin koodi tähän. Joten linkitetty lista, me todella on koodia. Niin laita tänne, tämä on prepending. Joten tämä tulee sen kärjessä. 

Joten ensimmäinen asia, sinun täytyy Luo uusi solmu, tietenkin, ja tarkista NULL. Aina hyvä. Ja sitten sinun täytyy määrittää arvot. Aina kun luot uuden solmun, et en tiedä mitä se on suunnattu seuraavaan, joten haluat alustaa sen null. Jos se ei päädy osoittaa jotain muuten, se saa antaa uudelleen ja se on hieno. Jos se on ensimmäinen asia luettelossa, se tarvitsee osoittamaan NULL koska se listan loppuun. 

Niin sitten lisätä sitä, näemme täällä määrität seuraavan arvon meidän solmun olla mitä pää on, joka on mitä meillä oli täällä. Sitähän me juuri teimme. Ja sitten me määrittämällä pään pisteeseen meidän uusi solmu, koska muistan, Uutta on joissakin osoitin solmuun, ja se on juuri sitä, mitä pää on. Juuri siksi me on tämä nuoli accessor. Cool? Mmhmm? 

Yleisö: Onko meillä alustaa uusia vieressä NULL ensin, vai voimmeko vain alustaa sen pää? 

SPEAKER 1: Uusi Seuraava täytyy olla NULL aloittaa koska et tiedä jos se tulee olemaan. Myös tämä on tavallaan Aivan kuten paradigma. Asetat sen yhtä NULL vain tehdä Varmista, että kaikki perusteet kuuluvat ennen kuin teet mitään siirtämisellä jotta olet aina varmaa, että se tulee osoittavan erityistä arvoa vs. kuin roskat arvo. Sillä, joo, asetamme uusi ensi automaattisesti, mutta se on enemmän aivan kuten hyviä käytäntöjä sen alustamiseen tällä tavalla ja sitten siirtää. 

OK, joten kaksinkertaisesti sidottu luetteloiden nyt. Mitä ajattelet? Mikä on erilaista kanssa kaksinkertaisesti liittyvät luettelot? 

Joten meidän linkitettyjen listojen, voimme liikkua vain yhteen suuntaan, eikö? Meillä on vain seuraava. Emme voi vain mennä eteenpäin. 

Kanssa kaksin verroin linkitetty lista, Voimme myös liikkua taaksepäin. Joten emme ole vain numero, jonka haluamme säilyttää, meillä kun se viittaa seuraavaan ja jos me vain tuli. Joten tämä mahdollistaa jotkut paremmin läpikäyminen. 

Joten kaksinkertaisesti sidottu solmuja, hyvin samankaltainen, eikö? Ainoa ero on nyt meillä on seuraava ja edellinen. Se on ainoa ero. 

Joten jos me liittää alkuun tai append-- me ei ole mitään koodia tähän asti here-- mutta jos olit yrittää aseta se, tärkeintä on sinun täytyy tehdä että olet osoitetaan sekä edellisen ja Seuraava osoitin oikein. Joten tässä tapauksessa sinun ei vain alustaa seuraavan, alustat edellinen. Jos olemme kärjessä listan, me olisi paitsi pää yhdenvertaisen uusia, mutta meidän uutta edellinen pitäisi viittaavat päähän, eikö? 

Se on ainoa ero. Ja jos haluat enemmän käytännön kanssa Näiden kanssa liittyvät luettelot, jossa asennat kanssa poistamalla, Insert osaksi valikoituja lista, tutustu study.cs50.net. On joukko suuria harjoituksia. Olen erittäin suositella niitä. Toivon, että meillä oli aikaa käydä niitä läpi mutta siellä on paljon tietorakenteita päästä läpi. 

OK, niin hash taulukoita. Tämä on luultavasti hyödyllinen vähän oman PSET täällä, koska aiot olla täytäntöön yksi näistä, tai yrittää. Pidän todella hash taulukoita. Ne ovat aika siistiä. 

Joten periaatteessa mitä tapahtuu, on tiiviste on, kun me todella tarvitsemme pikaista lisäys, poisto ja haku. Nämä ovat asioita, joita olemme priorisoinnin hajautustaulua. He voivat saada melko suuri, mutta kuten näemme kanssa yrittää, on olemassa asioita, jotka ovat paljon suurempia. 

Mutta pohjimmiltaan, kaikki hash pöytä on hash-funktio joka kertoo mikä ämpäri laittaa jokaisen tietosi, jokainen teidän osia. Yksinkertainen tapa ajatella hajautustaulun on, että se on vain ämpärillistä asioita, oikeassa? Joten kun olet lajittelu asioita kuten ensimmäisen kirjaimen nimensä, se on ikään kuin hajautustaulun. 

Joten jos olisin ryhmään te on ryhmiin kuka nimi alkaa kanssa tänne, tai kuka syntymäpäivä on tammi-, helmi-, maalis-, mitä tahansa, joka on tosiasiallisesti luodaan tiiviste. Se on vain luoda kauhat voit lajitella elementit jotta voit löytää ne helpommin. Joten tällä tavalla, kun tarvitsen löytää yksi teistä, Minulla ei ole etsiä läpi jokaisen teidän nimiä. En voi olla kuin, oh, tiedän että Danielle syntymäpäivä on in-- Yleisö: --April. SPEAKER 1: huhtikuussa. Joten odotan minun huhtikuu ämpäri, ja tuurilla, hän tulee olemaan ainoa siellä ja aikani oli vakio siinä mielessä, katsoo, että jos minun täytyy katsoa läpi koko joukko ihmisiä, se vie paljon kauemmin. Niin hash taulukot ovat oikeastaan ​​vain kauhat. Helppo tapa ajatella niitä. 

Joten erittäin tärkeä asia tiiviste on hash funktio. Niin mitä minä juuri puhui, kuten ensimmäinen kirjain ETUNIMESSÄSI tai syntymäpäivä kuukausi, nämä ovat ajatuksia, jotka todella korreloivat hajautusfunktio. Se on vain tapa päättää, mitkä ämpäri olisit elementti menee, OK? Joten tämä PSET, voit etsiä melko paljon mitään tiivistefunktiota haluat. 

Ei tarvitse olla oma. On joitakin todella hienoja niistä ulos siellä tehdä kaikenlaisia ​​hulluja matematiikka. Ja jos haluat tehdä oikoluku huippunopea, Haluan ehdottomasti tutkia yksi niistä. 

Mutta on myös yksinkertaiset, kuten laskentatehoa summa sanoja, kuten jokainen kirjain on useita. Laske summa. Joka määrittää ämpäri. Niillä on myös helppo niitä, jotka ovat aivan kuin kaikki on täällä, kaikki B: n täällä. Yksi näistä. 

Periaatteessa se vain kertoo, mitä taulukkoindeksin sinun elementti pitäisi mennä. Vain päättää bucket-- se on kaikki hash-funktio on. Joten tässä meillä on esimerkki, joka on vain ensimmäinen kirjain merkkijono että olin juuri puhu. 

Joten sinulla on joitakin hash, joka on juuri ensimmäinen kirjain merkkijono miinus, joka antaa sinulle numero välillä 0 ja 25. Ja mitä haluat tehdä, on Varmista, että tämä on kokoa hash table-- kuinka monta kauhat olemassa. Monet näistä hajautusfunktioita, he menossa palaamassa arvoja, jotka pitää olla reilusti määrä kauhat että sinulla todella on teidän tiiviste, joten sinun täytyy tehdä varma ja mod ne. Muuten, se tulee sanoa, Voi, se olisi ämpäri 5000 mutta sinulla on vain 30 kauhat teidän tiiviste. Ja tietysti me kaikki tiedämme, että on menossa aiheuttaa joitakin hulluja virheitä. Joten varmista mod mukaan kokoa tiiviste. Cool. Niin törmäyksiä. On kaikille hyvä tähän mennessä? Mmhmm? 

Yleisö: Miksi se palauttaa tällaisen massiivisen arvo? 

SPEAKER 1: Riippuen algoritmi että hash funktio käyttää. Jotkut heistä tekevät hullu kertominen. Ja se kaikki noin saada tasainen jakautuminen, joten he tekevät joitakin todella hulluja asioita joskus. Siinä kaikki. Entä muuta? OK. 

Niin törmäyksiä. Periaatteessa, kuten sanoin aiemmin, parhaassa tapauksessa, mitään ämpäri katson on menossa on yksi asia, joten minun ei tarvitse katsoa ollenkaan, eikö? En myöskään tiedä, se on olemassa tai se on ei, ja sitähän me todella haluamme. Mutta jos meillä on kymmeniä tuhansia mittauspisteiden ja pienempi kuin määrä kauhat, me aiomme olla yhteentörmäyksiä, joissa lopulta jotain joutuu päätyä ämpäri, joka on jo elementti. 

Joten kysymys on, mitä teemme tässä tapauksessa? Mitä teemme? Meillä on jo jotain siellä? Me vain heittää sen pois? 

Ei. Meidän täytyy pitää molemmat. Niin samalla tavalla kuin me tyypillisesti tee, joka on mitä? Mikä on tietorakenne me juuri puhuneet? Yleisö: linkitetty lista. SPEAKER 1: linkitetty lista. Niin nyt, sen sijaan, että kukin näistä kauhat vain ottaa yksi osa, se tulee sisältämään liittyy luettelo elementtejä, jotka olivat hajauttamat siihen. OK, ei kaikille sellaista saada tuon ajatuksen? Koska emme voineet olla array sillä emme tiedä, kuinka paljon tulevat olemaan siellä. Linkitetyn listan avulla voimme on vain tarkka määrä, joka hajautetaan tuohon ämpäri, eikö? 

Niin lineaarinen luotaa on pohjimmiltaan tämä idea-- se on yksi tapa käsitellä törmäyksen. Mitä voit tehdä on, jos tässä tapauksessa, marja hashed osaksi 1 ja meillä on jo jotain siellä, et vain pitää käynnissä kunnes löydät tyhjä paikka. Se on yksi tapa käsitellä sitä. Toinen tapa käsitellä se on mitä me juuri called-- liittyvät lista on nimeltään ketjutus. 

Joten tämä idea toimii, jos teidän tiiviste luulet on paljon suurempi kuin tietueesi tai jos haluavat yrittää minimoida ketjuttamalla kunnes se on ehdottoman välttämätöntä. Niin yksi asia on lineaarinen luotaa tarkoittaa luonnollisesti että tiivistefunktio ei ole aivan yhtä hyödyllinen koska aiot päätyä käyttämään teidän tiivistefunktiota, saada piste, voit lineaarinen koetin alas jotkut paikka, joka on käytettävissä. Mutta nyt, tietenkin, mitään muuta, joka päätyy sinne, olet menossa on etsi entisestään alas. 

Ja siellä on paljon enemmän Haku kustannuksella että menee syöttämällä elementti teidän tiiviste nyt, eikö? Ja nyt kun menet ja yrittää löytää Berry taas, olet menossa hash se, ja se aikoo sanoa, Oi, katso ämpäri 1, ja se ei tule olemaan ämpäri 1, niin olet täytyy kulkea läpi näitä muita. Joten se on joskus hyödyllistä, mutta useimmissa tapauksissa, aiomme sanoa, että ketjutus on mitä haluat tehdä. 

Joten puhuimme aiemmin. Sain hieman ennen itseäni. Mutta ketjutus on periaatteessa, että Jokaisen segmentin teidän tiiviste on vain linkitetty lista. 

Joten muulla tavoin tai enemmän teknisiä tapa, ajatella hajautustaulun on, että se on vain joukko linkitettyjä listoja, jotka Kun olet kirjoittanut sanakirja ja yrität ladata sitä, Tarkoitan sitä joukko liittyvät luettelot se on paljon helpompaa voit alustaa. 

Yleisö: Niin tiiviste on kooltaan ennalta määrätty, kuten [kuultavissa] kauhat? 

SPEAKER 1: Oikea. Joten sillä on tietty määrä kauhat, että olet determine-- jonka te pitäisi vapaasti pelata. Se voi olla melko viileä mitä tapahtuu kuin muutat useita kauhoja. Mutta joo, se on asettaa useita kauhoja. Mitä voit sovittaa niin monia elementtejä kuin tarvitset on tämä erillinen ketjutus missä ovat sidoksissa luettelot kunkin ämpäri. Tämän tarkoittaa, että tiiviste on täsmälleen koko että tarvitset sitä olla, eikö? Se idea liittyy luetteloita. Cool. 

Joten kaikki OK siellä? Selvä. Ah. Mitä juuri tapahtui? Todella nyt. Arvaa joku tappaa minut. 

OK aiomme mennä yrittää, jotka ovat vähän hullu. Pidän hash taulukoita. Minusta he todella siistiä. Yrittää ovat viileä, too. 

Joten ei kukaan muista, mitä kokeilla on? Olisit mennyt yli se lyhyesti luennolla? Muistatko sellainen miten se toimii? Yleisö: Olen vain nyökkää että me ei mennä sen yli. SPEAKER 1: Emme mene sen yli. OK, olemme todella menossa Yli se nyt on, mitä sanomme. 

Yleisö: Se for haku puu. 

SPEAKER 1: Joo. Se haku puu. Mahtava. Niin yksi asia huomata tässä on se, että me etsivät yksittäisiä merkkejä täällä, eikö? 

Joten ennen meidän hajautusfunktio, me katsoivat sanoja kokonaisuutena, ja nyt etsimme lisää hahmoja, eikö? Joten meillä on Maxwell tänne ja Mendel. Joten periaatteessa try-- tapa ajatella tässä on, että jokainen taso täällä on joukko kirjaimia. Joten tämä on juurisolmu täällä, eikö? Tämä on kaikki kirjaimet kirjaimille alussa jokaisen sanan. 

Ja mitä haluat tehdä, on sanoa, OK, meillä on joitakin M sana. Aiomme etsiä Maxwell, joten menemme M. ja M-pistettä koko muu joukko, jossa jokainen sana, niin kauan kuin on olemassa on sana, joka on koska toinen kirjain, niin kauan kuin siellä on sana, joka on B toinen kirjain, se on osoitin menossa joitakin ensi array. 

Ei luultavasti ole Sana, joka MP jotain, Joten P-asentoon tässä array, se olisi vain NULL. Se sanoisi, OK, ei ole sana joka on M seurasi P, OK? Joten jos ajattelemme sitä, kukin yksi näistä pienemmistä asioista on itse asiassa yksi näistä suurten taulukoiden välille Z. Joten mikä voisi olla yksi niistä asioista, joka on eräänlainen epäkohta kokeilla? 

Yleisö: paljon muistia. 

SPEAKER 1: Se on ton muistin, eikö? Jokainen näistä lohkojen tässä edustaa 26 paikkaa, 26 alkiotaulukon. Joten yrittää saada uskomattoman tilaa raskas. 

Mutta ne ovat erittäin nopeita. Niin uskomattoman nopea, mutta todella tilaa tehoton. Sellainen täytyy selvittää ulos, mitä haluat. Nämä ovat todella hienoja teidän PSET, mutta ne vievät paljon muistia, joten käyt kauppaa pois. Joo? 

Yleisö: Olisiko mahdollista perustaa kokeilla ja sitten Kun sinulla on kaikki tiedot siihen, että te need-- En tiedä, jos se olisi järkevää. Olin päästä eroon kaikista Null-merkit, mutta sitten et voi indeksoida them-- 

SPEAKER 1: Tarvitset silti niitä. 

YLEISÖ: - samalla tavalla joka kerta. SPEAKER 1: Joo. Tarvitset NULL merkkiä antaa te tiedätte, jos siellä ei ole sana siellä. Ben Oliko sinulla jotain haluat? OK. Okei, joten olemme menossa mennä hieman enemmän osaksi teknisiä yksityiskohtia takana yrittää ja työskennellä läpi esimerkki. 

OK, joten tämä on sama asia. Ottaa huomioon, linkitetty lista, tärkein jollaisia ​​of-- mitä sana haluan? - kuten rakennuspalikka oli solmu. Vuonna kokeilla, meillä on myös solmu, mutta se on määritelty eri tavoin. 

Joten meillä on joitakin bool että edustaa onko sana todella olemassa tässä paikassa, ja sitten meillä on joukko here-- tai pikemminkin, tämä on osoitin joukko 27 merkkiä. Ja tämä on, tässä tapauksessa, tämä 27-- Olen varma, että kaikki teistä ovat kuin, odota, on 26 kirjainta aakkosissa. Miksi meillä on 27? 

Joten riippuen tavalla toteuttaa tämän, tämä on peräisin PSET että sallittu heittomerkit. Joten siksi ylimääräistä yksi. Sinulla on myös joissakin tapauksissa null terminaattori on sisällytetty yhdeksi merkkejä, että se saa olla, ja se, miten ne tarkistaa katso jos se on sanan lopussa. Jos olet kiinnostunut, tutustu Kevinin video study.cs50, sekä Wikipediassa on joitakin hyviä resursseja siellä. 

Mutta aiomme käydä läpi vain eräänlainen miten voit työskennellä läpi yrittää jos olet antanut yhden. Meillä on siis erittäin yksinkertainen täällä, että on ilmaisu "bat" ja "Zoom" niihin. Ja kuten näemme täällä, Tässä vähän tilaa täällä edustaa meidän bool että sanoo, kyllä, tämä on sana. Ja sitten tämä on meidän paneelit merkkiä, eikö? 

Joten aiomme käydä läpi löytää "bat" tässä yrittää. Joten alkaa huipulla, eikö? Ja me tiedämme, että b vastaa Toinen indeksi, toinen elementti tässä array, koska a ja b. Joten noin toinen. 

Ja se sanoo, OK, viileä, seuraa, että otetaan Seuraava array, sillä jos muistamme, se ei ole, että jokainen näistä sisältää todella elementti. Jokainen näistä paneelit sisältää osoittimen, eikö? Se on tärkeä ero tehdä. 

Tiedän, että tämä on menossa be-- yrittää ovat todella vaikea päästä ensimmäistä kertaa, joten vaikka tämä on toisen tai kolmannen kerran ja se on vielä sellainen näennäisestä vaikeaa, Lupaan jos menet katsella lyhyt jälleen huomenna, se luultavasti tehdä paljon enemmän järkeä. Se vie paljon sulattaa. Olen edelleen joskus olen kuten, odota, mitä kokeilla? Miten käytän tätä? 

Olemme siis B tässä tapauksessa joka on meidän toinen indeksi. Jos meillä olisi vaikkapa C tai d tai mikä tahansa muu kirjain, meidän täytyy kartoittaa, että takaisin indeksiin meidän array että vastaa. Joten me ryhtyisimme kuten rchar ja me vain vähennä pois kartoittamaan se 0-25. Kaikki hyvä miten me kartta meidän merkkiä? OK. 

Joten menemme toinen ja me nähdä, että, kyllä, se ei ole NULL. Voimme siirtyä tähän seuraavaan array. Joten menemme tähän seuraavaan array täällä. 

Ja me sanomme, OK, nyt me täytyy nähdä, jos on täällä. On null tai tekee sen tosiasiallisesti liikkua eteenpäin? Joten todella liikkuu eteenpäin tässä array. Ja me sanomme, OK, t on meidän viimeinen kirjain. Joten menemme t-indeksi. Ja sitten siirrymme eteenpäin koska siellä on toinen. Ja tämä toinen sanoo periaatteessa, että kyllä, se sanoo, että on sana here-- että jos et noudata tätä polku, olet saapunut klo sana, jonka tiedämme olevan "lepakko". Kyllä? 

Yleisö: Onko standardi on, että kuten indeksi 0 ja sitten on eräänlainen 1 tai olla lopussa? 

SPEAKER 1: Ei. Joten jos me katsomme taaksepäin meidän ilmoitus täällä, se on bool, niin se on sen oma elementti omassa solmussa. Joten se ei ole osa array. Cool. Joten kun päätämme sanan ja olemme Tämän array, mitä haluamme tehdä on tehdä tarkistus on tämä sana. Ja tässä tapauksessa, se palaisi kyllä. 

Niin Komitea suosittelee, että me tiedämme, että "eläintarha" - Tiedämme ihmisinä että "eläintarha" on sana, oikeassa? Mutta eivät yritä täällä olisi sanoa, ei, se ei ole. Ja se sanoisi, että koska me eivät ole nimenneet sitä sanaa täällä. Vaikka emme voi kulkea kautta tähän array, tämä yrittää sanoa, että ei, eläintarha ei ole sanakirjaa koska meillä ei nimennyt sen sellaiseksi. 

Joten yksi tapa tehdä that-- Anteeksi, tämä yksi. Joten tässä tapauksessa, "eläintarha" ei ole sana, mutta se on meidän yrittää. Mutta tässä yksi, että haluamme sitä käyttöön sana "sauna", mitä tapahtuu on me seuraamme through-- b, t. Olemme tässä array, ja menemme etsimään h. 

Tässä tapauksessa, kun katsokaa osoitin h, se osoittaa NULL, OK? Joten jos se on nimenomaisesti viittaa toiseen array, oletat, että kaikki osoittimet Tässä array osoittavat nollaamaan. Joten tässä tapauksessa, h osoittaa nollaamaan joten emme voi tehdä mitään, niin se myös palauttaa väärä, "kylpy" ei ole täällä. Joten nyt olemme todella menossa läpi miten me oikeastaan ​​sanoa että "eläintarha" on meidän yrittää. Miten voimme lisätä "eläintarha" meidän kokeilla? Niin samalla tavalla, että aloitimme meidän linkitetty lista, aloitamme juureen. Jos olet epävarma, alkavat juuri näitä asioita. 

Ja me sanomme, OK, z. z olemassa tässä, ja se tekee. Joten olet siirtyessään seuraava array, OK? Ja sitten seuraava, sanomme, OK, ei o olemassa? Se tekee. Tämä taas. 

Ja niin meidän seuraava, olemme sanoneet, OK, "eläintarha" on jo olemassa täällä. Kaikki meidän täytyy tehdä, on asettaa tämän yhdenvertaisen on totta, että on olemassa sana siellä. Jos olisit seurannut kaiken jopa ennen tätä hetkeä, se sana, niin juuri aseta se yhtä tällaista. Kyllä? 

Yleisö: Niin tekee, että tarkoittaa, että "ba" on sana myös? 

SPEAKER 1: Ei. Joten tässä tapauksessa, "ba" saisimme täällä, sanoisimme on se sana, ja se olisi silti mitään. OK? Mmhmm? 

Yleisö: Niin kun se on sana ja sanot kyllä, niin se sisältää mennä m? 

SPEAKER 1: Eli tämä on tekemistä with-- lataat tämän. Sanot "eläintarha" on sana. Kun menet check-- kuten, että haluat sanoa, ei "eläintarha" olemassa tässä sanakirjassa? Olet vain menossa etsimään "eläintarha" ja sitten tarkistaa, jos se on sana. Et koskaan tule liikkumaan läpi m, koska se ei ole mitä etsit. 

Joten jos me todella halusimme lisätä "kylpy" tähän kokeilla, tekisimme saman asian kuten teimme "eläintarha" paitsi näkisimme, että kun me yrittää saada h, sitä ei ole olemassa. Voit siis ajatella tätä yrittää lisätä uuden solmun linkitetyn listan, joten meidän olisi lisätä toisen yksi näistä paneelit, kuten niin. Ja mitä sitten teemme, me vain asettaa h osa tätä array osoittaa tämän. 

Ja sitten mitä haluamme tehdä täällä? Lisää se yhtä totta koska se on sana. Cool. Tiedän. Yrittää eivät ole kaikkein jännittävä. Luota minuun, tiedän. 

Niin yksi asia on ymmärrettävä kanssa yrittää, Sanoin, ne ovat hyvin tehokkaita. Joten olemme nähneet ne vievät ton tilaa. He jotenkin hämmentävää. Joten miksi emme koskaan käyttää näitä? Käytämme näitä, koska he uskomattoman tehokas. 

Joten jos olet koskaan etsimässä ylös sana, olet vain jota rajoittavat pituus sana. Joten jos etsit sana, joka on pituudeltaan viisi, olet vain koskaan menossa on tehdä korkeintaan viisi vertailuja, OK? Niin se tekee periaatteessa vakio. Kuten paikoilleen ja haku ovat periaatteessa vakio aikaa. 

Joten jos et voi koskaan saada jotain vakioaikavälein, joka on yhtä hyvä kuin sen saa. Et voi saada parempaa kuin vakio aikaa näitä asioita. Niin että on yksi valtava ansioita yrittää. 

Mutta se on paljon tilaa. Joten sinulla sellainen on päätettävä mikä on sinulle tärkeää. Ja nykypäivän tietokoneissa, tila, joka yrittää saattaa kestää jopa ehkä ei vaikuta teille, että paljon, mutta ehkä olet tekemisissä jotain joka on paljon, paljon enemmän asioita, ja yritä ei ole järkevää. Kyllä? 

Yleisö: Odota, niin sinulla on 26 kirjaimet joka ikinen? 

SPEAKER 1: mmhmm. Joo, olet 26. Sinulla on joitakin on sana merkki ja sitten Sinulla on 26 viitteitä jokainen. Ja he point-- 

Yleisö: Ja jokainen 26, heillä kummallakin on 26? 

SPEAKER 1: Kyllä. Ja siksi, kuin pystyt katso, se laajenee melko nopeasti. Selvä. Joten aiomme päästä puita, jotka Tunnen on helpompaa ja luultavasti olla mukava pieni armonaikaa alkaen yrittää siellä. Joten toivottavasti useimmat teistä nähnyt puun ennen. Ei niinku ihan ulkopuolella olevat, jotka minä en tiedä, jos joku meni ulkona äskettäin. Kävin omena poiminta tänä viikonloppuna, ja Jestas, se oli kaunis. En tiennyt lehdet voisi näyttää, että aika. 

Joten tämä on vain puu, eikö? Se on vain joku solmu, ja se viittaa joukko muita solmuja. Kuten näette täällä, tämä on eräänlainen toistuva teema. Solmut osoittava solmut on eräänlainen pohjimmiltaan monien tietorakenteita. Se vain riippuu siitä, miten me ne viittaavat toisiinsa ja miten me kulkea niiden kautta, ja miten me aseta asioita, joka määrittää niiden ominaisuudet ovat erilaiset. 

Joten vain joitakin terminologiaa, jota olen käyttänyt aiemmin. Niin juuri on mitä on huipulla. se missä olemme aina aloittaa. Voit ajatella sitä päätä myös. Mutta puita, meillä on taipumus kutsuvat sitä juuri. 

Mitään alareunassa here-- aivan, erittäin bottom-- pidetään lehtiä. Niin se menee yhdessä koko puun juttu, eikö? Lehdet ovat reunoilla teidän puu. 

Ja sitten meillä on myös pari Ehdot puhua solmuja suhteessa toisiinsa. Joten meillä on vanhempi, lapset ja sisarukset. Joten tässä tapauksessa, 3 on vanhempi 5, 6 ja 7. Joten vanhempi on mitä on yhden askeleen edellä mitä olet viitaten, niin juuri kuten sukupuu. Toivottavasti tämä on kaikki hieman hieman enemmän intuitiivinen kuin yrittää. 

Sisarukset ovat kaikki, jotka ovat sama vanhempi, eikö? He ovat samalla tasolla täällä. Ja sitten, kun olin sanomalla, lapset ovat vain mikä on yksi askel alla -solmu, OK? Cool. Joten binääripuu. Voiko kukaan arvata yksi ominaisuudet binääripuun? 

Yleisö: Max kaksi lehteä. 

SPEAKER 1: Oikea. Joten max kaksi lehteä. Joten tässä yksi ennen, meillä oli tämä yksi että oli kolme, mutta binaarisen puun, sinulla on max kaksi lasta vanhempi, eikö? On toinenkin mielenkiintoinen ominaisuus. Tietääkö kukaan, että? Binääripuu. 

Joten binääripuu on kaikki on the-- tämä ei ole sorted-- mutta lajiteltu binääripuun, kaiken oikealla on suurempi kuin vanhemman, ja kaikki vasemmalla on vähemmän kuin vanhempi. Ja että on ollut tietokilpailu kysymys ennen, niin hyvä tietää. Joten miten me määrittelemme tämän, taas, meillä on toinen solmu. Tämä näyttää hyvin samankaltainen kuin mitä? Kaksin verroin 

Yleisö: Linked luettelot 

SPEAKER 1: kaksinkertainen linkitetty lista, eikö? Joten jos me korvata tämän edellisen ja seuraavan, tämä olisi kaksin verroin linkitetty lista. Mutta tässä tapauksessa, me oikeastaan on vasen ja oikea ja se on siinä. Muuten, se on täsmälleen sama. Meillä on edelleen elementin etsit, ja sinulla on vain kaksi osoitinta menossa mitä seuraavaksi. Joo, niin binäärihakupuu. Jos huomaamme, kaiken täällä on enemmän than-- tai kaiken heti on täällä on suurempi kuin, kaikki tässä alle. 

Joten jos me etsiä, se pitäisi näyttää melkein binäärihaku täällä, eikö? Paitsi sijaan etsivät klo puoli array, Olemme vain katsomalla joko vasen puolella tai oikealla puolella puu. Joten se saa hieman yksinkertaisempi, luulen. 

Joten jos juuri on NULL, ilmeisesti se on vain väärä. Ja jos se on olemassa, ilmeisesti se on totta. Jos se on alle, haemme vasemmalle. Jos se on suurempi kuin, haemme oikeutta. Se on aivan kuin binäärihaku, vain eri tietorakenne että käytämme. Sen sijaan, array, se on vain binääripuu. 

OK, pinot. Ja myös näyttää siltä, ​​että me saattaa olla hieman aikaa. Jos teemme niin, olen onnellinen mennä minkä tahansa tämän uudelleen. OK, niin pärjää. Muistaako kukaan mitä stacks-- mitään ominaisuuksia pino? 

OK, joten useimmat meistä, luulen, syödä ruokailu halls-- niin paljon kuin emme haluaisi. Mutta tietenkin, voit ajatella pino kirjaimellisesti aivan kuten pino tarjottimia tai pino asioita. Ja mikä on tärkeää on ymmärrettävä, että se on something-- ominaisuus että me kutsumme sitä by-- on LIFO. Onko kukaan tiedä, mitä se tarkoittaa? Mmhmm? 

Yleisö: last in, first out. 

SPEAKER 1: Oikea, last in, first out. Joten jos me tiedämme, jos olemme pinoaminen asioita ylös, helpointa napata off-- ja ehkä ainoa asia, jota emme voi napata pois, jos meidän pino on iso enough-- on, että top elementti. Joten mitä laitettiin last-- kuten näemme täällä, mikä oli ajanut useimmissa recently-- on olemaan ensimmäinen asia, että me kupsahtaa, OK? 

Joten mitä meillä täällä on toinen typedef struct. Tämä on todella aivan kuten pikakurssin tietorakenne, joten siellä on paljon heitetään sinua kaverit. Tiedän. Niin vielä toinen struct. Yay rakenteita. 

Ja tässä tapauksessa, se on jonkin verran osoitin array, joka on jonkin verran kapasiteettia. Joten tämä on meidän pino täällä, kuten meidän todellinen array että pitelee meidän elementtejä. Ja sitten täällä on joitakin koko. 

Ja tyypillisesti, jotka haluat säilyttää Seuraa kuinka suuri pino on koska mitä se tulee sallia voit tehdä on, jos tiedät koon, sen avulla voit sanoa, OK, olen teholla? Voinko lisätä mitään muuta? Ja se kertoo myös jossa ylin stäkistäsi on niin tiedät mitä voi itse ottaa pois. Ja se todella tulee olla hieman selvempi täällä. 

Joten push, yksi asia, jos olivat koskaan toteuttaa push, kuten juuri kerroin, sinun pino on rajoitettu koko, eikö? Meidän joukko oli jonkin verran kapasiteettia. Se jono. Se on kiinteä koko, joten meidän täytyy varmista, että emme ole entistä enemmän meidän array kuin me todella on tilaa. 

Joten kun luot push toiminto, ensimmäinen asia mitä tehdä, on sanoa, OK, minulla on tilaa minun pino? Koska jos en, anteeksi, En voi tallentaa elementti. Jos en, niin haluat tallentaa se on pinon päällä, eikö? 

Ja siksi olemme seurata meidän kokoa. Jos emme seurata meidän kokoa, emme tiedä, mihin se. Emme tiedä, kuinka paljon ovat meidän array jo. Kuten ilmeisesti on olemassa keinoja että ehkä sinä voisit tehdä sen. Voisit alustaa kaiken NULL ja sitten tarkistaa uusimmat NULL, mutta paljon helpompi asia on juuri sanoa, OK, seurata koko. Kuten Tiedän, että olen neljä elementtiä minun array, niin seuraava asia että laitamme, olemme aiotaan säilyttää indeksillä 4. Ja sitten, tietenkin, tämä tarkoittaa, että olet onnistuneesti ajanut jotain päälle pinoon, mutta et haluavat lisätä kokoa jotta tiedät missä olet niin että voit työntää enemmän asioita. 

Joten jos yritämme pop jotain pois pinosta, mikä voisi olla ensimmäinen asia että haluamme tarkistaa? Yrität ottaa jotain pois teidän pinoon. Oletko varma, että siellä on jotain teidän pinoon? Ei. Mikä siis haluamme tarkistaa? 

Yleisö: [kuulumaton]. SPEAKER 1: Tarkista koko? Koko. Joten haluamme tarkistaa, onko Meidän koko on suurempi kuin 0, OK? Ja jos on, niin me haluamme vähentää meidän kokoa 0 ja palata siihen. Miksi? 

Ensimmäisessä vaihtoehdossa olimme työntää, me työnnetään se päälle koko ja sitten päivitetään koko. Tässä tapauksessa olemme decrementing koko ja sitten ottaa se pois, nyppiminen se meidän array. Miksi voisimme tehdä? Joten jos minulla on yksi asia minun pino, mikä olisi minun kokoa tässä vaiheessa? 1. 

Ja missä on elementti 1 tallennetaan? Mitä indeksi? Yleisö: 0. SPEAKER 1: 0. Joten tässä tapauksessa, me aina täytyy tehdä sure-- sijaan palaavat koko miinus 1, koska me tietää, että tekijä on menossa säilytettävä 1 vähemmän mitä meidän koko on, tämä vain hoitaa homman. Se on hieman enemmän tyylikäs tavalla. Ja me vain dekrementoidaan meidän koon ja palata sitten koko. Mmhmm? 

Yleisö: Luulen vain yleisesti, Miksi näin tietorakenne olla hyödyllistä? 

SPEAKER 1: Se riippuu yhteydessä. Joten joidenkin teoriaa, jos olet työskennellyt with-- OK, anna minun nähdä, jos siellä on hyödyllistä yksi että on hyödyllistä enemmän kuin ulkopuolella CS. Pinot, aina kun tarvitset seurata jotain, on viimeksi lisätty on kun olet menossa haluavat käyttää pinon. 

Ja en voi ajatella hyvä Esimerkkinä juuri nyt. Mutta aina viimeisimmän asia on tärkeintä sinulle, se kun pino tulee olemaan hyötyä. Yritän ajatella, jos siellä on hyvä tähän. Jos ajattelen hyvä esimerkki seuraavassa 20 minuuttia, aion ehdottomasti kertoa. 

Mutta kaiken kaikkiaan, jos on jotain, kuten sanoin useimmat, jossa viimeisin on tärkeintä, että on jossa pino tulee pelata. Ottaa huomioon, että jonot ovat tavallaan päinvastainen. Ja kaikki pikku koirat. Eikö tämä suuri, eikö? Tunnen pitäisi vain pupu video aivan keskellä osio te koska tämä on voimakas kohta. 

Niin jono. Periaatteessa jono on kuin viiva. Te varmasti käyttää tätä jokapäiväistä, aivan kuten meidän ruokasalia. Joten meidän täytyy mennä ja saada meidän tarjottimet, olen että sinulla on jonottaa pyyhkäistä tai saada ruokaa. 

Joten ero täällä on, että tämä on FIFO. Joten jos LIFO viimeksi vuonna, ensin out, FIFO on first in, first out. Joten tämä on silloin, mitä laitat ensimmäisessä on tärkein. Joten jos odottivat vuonna line-- voitte Kuvittele, jos meni mene saada uusi iPhone ja se oli pino jossa viimeinen henkilö linjassa sai sen ensin, ihmiset tappavat toisiaan. 

Joten FIFO, olemme kaikki hyvin tuttuja kanssa todellisessa maailmassa täällä, ja se kaikki on tekemistä itse Tällainen uudestaan ​​tämän koko linjan ja jonotuksen rakenne. Joten taas pino, meillä on push ja pop. Kanssa jonoon, meillä on enqueue ja dequeue. Joten enqueue tarkoittaa periaatteessa laita se päälle takaisin, ja dequeue keinot toteuttaa pois edestä. Joten meidän tietorakenne on hieman monimutkaisempi. Meillä on toinen asia pitää kirjaa. 

Joten ilman päätä, tämä Juuri pino, eikö? Tämä on sama rakenne kuin pino. Ainoa asia erilainen nyt on meidän on tämä pää, joka mitä luulet aikoo seurata? 

Yleisö: ensimmäinen. 

SPEAKER 1: Oikea, Ensimmäinen asia, että panemme. Vetäjänä jonossa. Kuka on ensimmäisenä jonossa. Okei, joten jos teemme enqueue. Jälleen, joilla on jokin Näiden tietorakenteita, koska olemme tekemisissä array, Meidän täytyy tarkistaa, jos meillä on tilaa. 

Tämä on ikään kuin kertasin te, jos avaat tiedoston, sinun täytyy tarkistaa null. Mitään näistä pinot ja jonot, tarvitset onko siellä tilaa, koska olemme kyseessä on kiinteä koko array, kuten näemme here-- 0, 1 kaikki jopa 5. Joten mitä me teemme tässä tapauksessa on tarkistaa nähdä, jos meillä on vielä tilaa. On meidän koko pienempi kuin kapasiteetti? 

Jos näin on, meidän täytyy säilyttää se hännän ja päivitämme koko. Joten mikä voisi häntä olla tässä tapauksessa? Se ei ole erikseen kirjoitettu ulos. Miten me tallentaa sen? Mikä olisi hännän olla? 

Joten kävele tässä esimerkissä. Joten tämä on taulukon koko 6, eikö? Ja meillä on juuri nyt, meidän koko on 5. Ja kun panemme sen, se tulee mennä viidenteen indeksi, eikö? Joten säilytä häntää. 

Toinen tapa kirjoittaa häntä olisi vain meidän array indeksi koko, eikö? Tämä on koko 5. Seuraava asia on menossa mennä 5. Cool? OK. Se saa hieman monimutkaisempi kun alamme Messing kanssa pää. Kyllä? 

Yleisö: Tarkoittaako tämä sitä, että me olisi todennut array, joka oli viisi elementtiä pitkä ja Sitten me lisäämme sen päälle? 

SPEAKER 1: Ei. Joten tässä tapauksessa, tämä on pino. Tämä olisi julistettava koska taulukon koko 6. Ja tässä tapauksessa, me on vain yksi välilyönti vasemmalle. 

OK, niin yksi asia on tässä tapauksessa, jos meidän pää on 0, Sitten me vain voi lisätä sitä kokoa. Mutta se saa hieman hankalampaa koska itse asiassa, ne ei ole dia tähän, joten aion vetää yhteen, koska se ei ole aivan näin yksinkertainen, kun olet alkaa päästä eroon asioita. Joten taas pinon olet aina vain murehtia, mitä kokoa on kun lisäät jotain, jossa jono sinun täytyy myös tehdä Varmista, että pää on osuus, koska cool juttu jonoja on, että jos et ole kapasiteettia, voit itse tehdä sen kietoa. 

OK, joten yksi thing-- oh, tämä on kauheaa liitu. Yksi asia harkita tapaus. Me vain tehdä viisi. OK, joten me aiomme sanoa pää on täällä. Tämä on 0, 1, 2, 3, 4. 

Pää on siellä, ja ole hyvä, mitä niissä on. Ja haluamme lisätä jotain, eikö? Niin asia, että meidän täytyy tietää, että pää on aina Siirrymme tällä tavalla ja sitten silmukka takaisin noin, OK? 

Joten tässä jonossa on tilaa, eikö? Se on tila alusta, eräänlainen vastakohta. Joten mitä meidän täytyy tehdä, on meillä täytyy laskea häntää. Jos tiedät, että pää ei ole liikkunut, häntää on vain sinun array indeksi koon. 

Mutta todellisuudessa, jos käytät jono, pää on todennäköisesti päivitetään. Joten mitä sinun tarvitsee tehdä, on oikeastaan ​​laskea häntä. Joten mitä teemme, on tämä kaava täällä, jotka aion antaa teille kaverit ajattelevat, ja niin me puhumme siitä. Joten tämä on kapasiteettia. 

Joten tämä todella antaa sinulle tapa tehdä se. Koska tässä tapauksessa, mitä? Meidän pää on 1, meidän koko on 4. Jos me mod että 5, saamme 0, mikä on kun meidän pitäisi syöttää sitä. 

Niin sitten seuraavassa tapauksessa jos tekisimme tämän, sanomme, OK, katsotaanpa dequeue jotain. Me dequeue tätä. Otamme tämä elementti, eikö? 

Ja nyt meidän pää osoittaa täällä, ja haluamme lisätä toinen juttu. Tämä on pohjimmiltaan takaisin meidän linja, eikö? Jonot voi kietoa array. Se on yksi tärkeimmistä eroista. Pinot, et voi tehdä tätä. 

Kanssa jonot, voit koska kaikki asiat on, että tiedät mitä oli viimeksi lisätty. Koska kaikki on menossa lisätä Tämän vasemmalle suuntaan, tässä tapauksessa, ja sitten kietoa, voit jatketaan ottamalla uusia elementtejä edessä array koska se ei ole oikeastaan edessä array enää. Voit ajatella alusta array missä päätäsi todella on. 

Joten tämä kaava on, miten voit laskea häntä. Onko se järkevää? OK. OK, dequeue, ja sitten teillä 10 minuuttia kysyä minulta mitään tarkentavia kysymyksiä haluat, koska tiedän, että se on hullua. 

Okei, joten samassa way-- En tiedä, jos te huomanneet, mutta CS on kyse kuvioita. Asiat ovat melko sama, vain pieniä parannuksia. Niin sama juttu täällä. Meidän täytyy tarkistaa, jos me itse on jotain meidän jonossa, eikö? Sanovat, OK, on ​​meidän koko suurempi kuin 0? Cool. 

Jos teemme, sitten siirrymme meidän pään, joka minä juuri osoittanut täällä. Päivitämme pää olla yksi enemmän. Ja sitten me dekrementoidaan meidän kokoa ja palauttaa elementin. 

Siellä on paljon enemmän konkreettisia koodi study.cs50.net, ja olen erittäin suositella menossa sen kautta, jos sinulla on aikaa, vaikka se on vain pseudo-koodin. Ja jos kaverit haluavat puhua kautta että minun kanssani one, kerro minulle tietää. Olen mielelläni. Tietorakenteita, jos otat CS 124, luultavasti tietää, että tietorakenteita saada hyvin hauskaa ja tämä on vasta alkamassa. 

Tiedän siis, se on vaikeaa. Se on OK. Kamppailemme. En vieläkään. Joten älä murehdi liikaa sitä. 

Mutta se on pohjimmiltaan sinun pikakurssin tietorakenteita. Tiedän, että se on paljon. Onko mitään, me haluaisin mennä uudestaan? Mitä me haluamme puhua kautta? Kyllä? 

Yleisö: Tästä esimerkiksi niin Uuden häntä on 0 kyseisenä? SPEAKER 1: Kyllä. Yleisö: OK. Niin sitten menee läpi, sinun on 1 plus 4 or-- 

SPEAKER 1: Niin sanoitte, kun haluamme mennä tekemään tätä uudelleen? Yleisö: Joo. Joten jos olit miettiminen out-- missä voit laskettaessa hännän että? 

SPEAKER 1: Niin hännän oli in-- muutin tähän. Joten tässä esimerkissä täällä, tämä oli array me tarkastelemme, OK? Joten meillä on asiat 1, 2, 3, ja 4. Joten meillä on pää on 1 klo Tässä vaiheessa, ja meidän koko vastaa 4 tässä vaiheessa, eikö? 

Te kaikki samaa mieltä siitä, että näin on? Joten emme päätä plus koko, joka antaa meille 5, ja sitten me mod 5. Saamme 0, joka kertoo meille, että 0 on missä on häntä, jossa meillä on tilaa. 

Yleisö: Mikä korkki? 

SPEAKER 1: kapasiteettia. Anteeksi. Tämä on siis kokoa array. Kyllä? 

Yleisö: [kuulumaton] ennen palaamme elementti? 

SPEAKER 1: Eli siirrymme pää tai palauttaa hetki? Joten jos siirrymme yhden, dekrementoidaan koko? Pidä kiinni. Olen ehdottomasti unohdin toiseen. Ei se haittaa. Ei ole toista kaavaa. Joo, mitä haluaisi palata pää ja sen jälkeen takaisin. 

Yleisö: OK, koska tässä kohta, pää oli 0, ja sitten haluat palata indeksi 0 ja sitten tehdä pään 1? 

SPEAKER 1: Oikea. Mielestäni on olemassa toinen kaava ikään kuin tämä. Minulla ei ole sen päällä päähäni En halua antaa sinulle väärä. Mutta mielestäni se on täysin voimassa sanoa, OK, säilytä tämä element-- riippumatta pää n elementti is-- dekrementoidaan sinun koon, siirrä pään yli, ja paluu mitä se elementti on. Se on täysin pätevä. OK. Minusta tuntuu, tämä ei ole kuten most-- et ole kävelen pois täältä kuten, kyllä, tiedän yrittää. Sain sen kaiken. Ei se mitään. Lupaan. Mutta tietorakenteita ovat jotain, se vie paljon aikaa tottua. Luultavasti yksi vaikeimmista asioita, luulen, että kurssin. 

Joten se varmasti vie toistoa ja etsivät at-- I ei oikein tiedä linkitettyjen listojen kunnes tein liian paljon heidän kanssaan, samalla tavalla, etten todella ymmärtää osoittimet kunnes olen joutunut opettamaan sitä kaksi vuotta ja tehdä omaa psets kanssa. Se vie paljon toistoa ja aikaa. Ja lopulta se tavallaan klikkaa. 

Mutta sillä välin, jos sinulla on sellainen korkean tason ymmärrystä siitä, mitä nämä tekevät, niiden etuja ja cons-- joka on mitä me todella yleensä korostavat, varsinkin intro kurssin. Kuten, miksi käytämme kokeile yli array? Kuten, mitkä ovat positiivisia ja negatiivit, kumpaa näistä? 

Ja ymmärtää kompromisseja kunkin näistä rakenteista on mitä on paljon tärkeämpää juuri nyt. Siellä voi olla yksi hullu kysymys tai kaksi, joka on pyydämme teitä toteuttaa push tai toteuttaa pop tai enqueue ja dequeue. Mutta suurin osa, jolla se korkeampaa ymmärrystä ja enemmän on intuitiivinen käsitys on tärkeämpää kuin itse pysty toteuttamaan sitä. 

Se olisi todella mahtavaa, jos te kaikki voisi mennä ulos ja mennä toteuttamaan kokeilla, mutta ymmärrämme se ei välttämättä järkevin asia juuri nyt. Mutta voit omassa PSET, jos haluat sen, ja sitten saat käytännössä ja sitten ehkä sinun todella ymmärtää se. Kyllä? 

Yleisö: OK, niin mitkä ovat Meidän tarkoitus käyttää PSET? Tarvitseeko minun käyttää yksi heistä? SPEAKER 1: Kyllä. Joten sinulla on valintasi. Oletan tässä tapauksessa voimme puhua PSET hieman koska juoksin läpi näitä. Joten teidän PSET, sinulla on valinta yrittää tai hash taulukoita. Jotkut ihmiset yrittävät ja käyttää kukinta suodattimet, mutta ne eivät varsinaisesti ole oikeita. Koska niiden todennäköisyyspohjainen luonteen, ne antavat vääriä positiivisia joskus. He viileä tutkia, vaikka. Suosittelen näköinen niitä ainakin. Mutta sinulla on valinnanvaraa välinen tiiviste ja kokeilla. Ja se tulee olemaan, jos lataat oman sanakirjan. 

Ja sinun täytyy valita teidän hajautusfunktio, sinun täytyy valita, kuinka monta kauhat sinulla on, ja se vaihtelee. Kuten jos sinulla on enemmän kauhat, Ehkä se ajaa nopeammin. Mutta ehkä sinä tuhlaat paljon tilaa, että tapa, vaikka. Sinun täytyy tajuta se. Mmhmm? 

Yleisö: Sanoit aiemmin, että voimme käyttää muita hash toimintoja, että emme tarvitse luoda hajautusfunktio? 

SPEAKER 1: Kyllä, aivan. Joten kirjaimellisesti oman hajautusfunktio, Google "hajautusfunktio" ja etsiä hienoja niistä. Et ole odotettavissa rakentaa oma hash toimintoja. Ihmiset viettävät teesiä näitä asioita. 

Joten älä ole huolissasi rakentaa oma. Etsi yksi verkossa aloittaa. Jotkut heistä joudut manipuloida hieman varmistaa paluun tyypit täsmää ja vaikka mitä, niin alussa, Voisin suositella käyttäen jotain helppoa, että ehkä juuri hajautustaulu- ensimmäistä kirjainta. Ja sitten kun sinulla on, että työ-, sisällyttämällä jäähdytin hajautusfunktio. Mmhmm? 

Yleisö: Olisiko yrittää olla tai tehokas, mutta vain vaikeampi, like-- 

SPEAKER 1: Niin kokeilla, luulen, on intuitiivisesti vaikea toteuttaa mutta on erittäin nopea. Kuitenkin vie enemmän tilaa. Jälleen, voit optimoida nämä molemmat vuonna eri tavoin ja on olemassa keinoja to-- Yleisö: Miten me arvostellaan tätä? Onko se matter-- 

SPEAKER 1: Eli olet arvostellaan normaalilla tavalla. Olet menossa arvostellaan suunnitteluun. Miten tahansa tehdä, haluatko varmista, että se on yhtä tyylikäs kuin se voi olla ja niin tehokas kuin se voi olla. Mutta jos haluat kokeilla tai hash taulukko, niin kauan kuin se toimii, olemme tyytyväisiä, että. Ja jos käytät jotain että hash ensimmäistä kirjainta, se on hieno, kuten ehkä kuten suunnittelu-viisas. Olemme myös päästä kohta tässä semester-- En tiedä, jos kaverit noticed-- jos olet PSET laadut laskevan hieman koska suunnittelu ja vaikka mitä, se on täysin hieno. Se on tulossa pisteeseen, jossa sinun ohjelmat monimutkaistuvat. On enemmän paikkoja voit parantaa. 

Joten se on täysin normaalia. Se ei ole, että olet huonommin teidän PSET. Se on vain Meitä kovemmin sinua nyt. Joten jokainen tunne sitä. Minä vain arvostellaan kaikki psets. Tiedän, jokainen tunne sitä. 

Joten älä olla huolissaan siitä. Ja jos sinulla on kysyttävää ennen psets tai miten voit parantaa, Yritän ja kommentoida erityisiä paikkoja, mutta joskus se on myöhäistä ja saan väsynyt. Onko muita asioita noin tietorakenteita? Olen varma, että kaverit eivät todellakaan halua puhua niitä enää, mutta jos on, olen onnellinen mennä niiden yli, samoin kuin mitään luento viime viikko tai viime viikolla. 

Tiedän, viime viikolla oli kaikki tarkastelu, joten olemme ehkä ohitetaan joitakin arvostelu alkaen luento. Muita kysymyksiä voin vastata? OK, kaikki hyvin. No, te ulos 15 minuuttia etuajassa. 

Toivon, että tämä oli semi-hyödyllinen ainakin, ja minä näen teidät ensi viikolla, ja torstain virka. Onko pyytää välipalat ensi viikolla, se juttu? Koska unohdin karkkia tänään. Ja minä toin karkkia viimeksi viikko, mutta se oli Columbus Day, joten ei ollut kuin kuusi henkilöä, jotka oli neljä pussia karkkia itselleen. Voin tuoda starbursts uudelleen, jos haluat. Starbursts? OK, kuulostaa hyvältä. On suuri päivä, kaverit.