DOUG Lloyd: Niin CS50, olemme katettu paljon erilaisia ​​tietorakenteita, oikea? Olemme nähneet paneelit, ja liittyy luettelot, ja hash taulukot, ja yrittää, pinot ja jonot. Otamme myös oppia hieman puista ja kasoista, mutta oikeastaan ​​nämä kaikki vain lopettaa lopulta muunnelmia teemasta. Ei todellakaan nämä eräänlainen neljä perusajatuksia että kaikki muu voi pohjimmiltaan. Taulukot, jotka liittyvät luettelot, hash taulukoita, ja yrittää. Ja kuten sanoin, siellä ovat muunnelmia niitä, mutta tämä on melko paljon menossa yhteenveto kaikki me aiomme puhua noin tässä luokassa kannalta C. Mutta miten nämä kaikki toimenpide, eikö? Olemme puhuneet eduista ja haitoista Kunkin erillisissä videoita niitä, mutta siellä on paljon numeroita saada heittää noin. Siellä on paljon yleistä ajatukset saada heittää noin. Yritetään lujittaa se vain yhteen paikkaan. Katsotaanpa punnita hyviä vastaan haittoja, ja harkita joka datarakenne voisi olla oikea tiedot rakenne teidän tilanteeseen, Riippumatta siitä, millaista tietoa olet tallentamiseen. Sinun ei välttämättä aina tarvitse Käytä huippunopea lisäys, poisto, ja lookup trie jos todella eivät välitä lisäämällä ja poistamalla liian paljon. Jos tarvitset vain nopeasti satunnainen yhteys, ehkä array on parempi. Joten distill että. Puhutaanpa kunkin neljän suurta kokonaisuutta tietorakenteiden että olemme puhuneet, ja vain nähdä, kun he voisi olla hyvä, ja kun he ehkä ole niin hyvä. Joten aloittaa paneelit. Niin lisäys, että on tavallaan huono. 

Insertio lopussa array on OK, jos me rakennamme erilaisia ​​kuin me mennä. Mutta jos meidän lisätä elementtejä keskelle, muistelen lisäys lajitella, siellä on paljon vaihtuvien sopivaksi elementti siellä. Joten jos aiomme lisätä missä tahansa mutta lopussa array, se luultavasti ei ole niin suuri. 

Samoin poistetaan, ellei olemme poistamalla lopusta array, ei luultavasti myös ei ole niin suuri, jos emme halua lähteä tyhjä aukkoja, joka yleensä emme. Haluamme poistaa elementin, ja sitten tavallaan tekevät siitä kireällä uudelleen. Ja niin poistamalla elementtejä array, myös ei niin suuri. 

Lookup on kuitenkin suuri. Meillä on random access, vakioaikaisia ​​haku. Me vain sanoa seitsemän, ja menemme array siirtäminen seitsemän. Sanomme 20, kanssa mennä array siirtäminen 20. Meillä ei tarvitse kerrata poikki. Se on aika hyvä. 

Taulukot ovat myös suhteellisen helppo lajitella. Joka kerta puhuimme lajittelu algoritmi, kuten valinta lajitella, lisäyslajittelun, kuplalajittelu, yhdistää lajitella, me aina käytetty taulukot tehdä sitä, koska taulukot ovat melko helppo lajitella, suhteessa tietorakenteiden olemme nähneet tähän mennessä. 

Ne ovat myös suhteellisen pieni. Siellä ei ole paljon ylimääräistä tilaa. Sinä vain varattu täsmälleen yhtä paljon niin sinun täytyy pitää tietosi, ja se on aika paljon se. Joten ne ovat melko pieniä ja tehokas näin. Mutta toinen haittapuoli, vaikka, on, että ne ovat kiinteitä koko. Meidän on julistaa kuinka iso haluamme array olla, ja me vain saada yksi laukaus sitä. Emme voi kasvaa ja kutista se. 

Jos meidän täytyy kasvattaa tai pienentää sitä, me tarvitse ilmoittaa kokonaan uusi joukko, kopioida kaikki elementit ensimmäinen array toiseen array. Ja jos me virheellisesti, että aika, meidän täytyy tehdä se uudelleen. Ole niin suuri. Joten paneelit eivät anna meille joustavuutta on vaihteleva määrä elementtejä. 

Kanssa linkitetty lista, Lisäys on melko helppoa. Me vain tack päälle edessä. Poisto on myös melko helppoa. Meidän täytyy löytää elementtejä. Että mukana vähän tutkimustyötä. 

Mutta kun olet löytänyt elementti etsit, sinun ei tarvitse tehdä on muuttaa osoitin, mahdollisesti kaksi jos sinulla on linkitetty list-- kaksinkertaisesti linkitetty lista, rather-- ja sitten voit vain vapauttaa solmu. Sinun ei tarvitse siirtää kaikki ympärillä. Sinä vain vaihtaa kaksi osoitinta, niin se on melko nopeasti. 

Lookup on huono, vaikka, eikö? Jotta voimme löytää elementti linkitetty lista, onko yksittäin tai kaksinkertaisesti sidottu, meidän on lineaarinen etsiä sitä. Meidän on aloitettava alusta ja Siirrä loppuun, tai aloittaa lopussa liikkeellä alkuun. Meillä ei ole random access enää. Joten jos teemme Kovan etsimisen, ehkä linkitetty lista ei ole aivan niin hyvä meille. 

Ne ovat myös todella vaikea lajitella, eikö? Vain siten voit todella lajitella linkitetty lista on lajitella se, kun rakentaa sitä. Mutta jos lajitella kun rakentaa se, et enää joten nopea insertioita enää. Et vain tacking asioita päälle edessä. Sinun täytyy löytää oikea paikka laittaa se, ja sitten lisäys tulee lähes yhtä huono kuten lisäämällä taulukkoon. Joten liity luettelot eivät ole niin suuri tietojen lajittelussa. 

Ne ovat myös melko pieni, koko-viisasta. Kaksin verroin linkitetty lista hieman suurempi kuin yksittäin liittyvät luettelot, jotka ovat hieman suurempia kuin paneelit, mutta se ei ole valtavasti hukkaan tilaa. Joten jos tilaa on niukasti, mutta ei todella voimakas palkkio, tämä voisi olla oikea tapa edetä. 

Hash taulukoita. Liittämistä osaksi hajautustaulun on melko yksinkertainen. Se on kaksivaiheinen prosessi. Ensin täytyy ajaa meidän dataa hajautusfunktio saada hash, ja sitten me aseta elementin hash pöytä että hash koodi sijainti. 

Poisto, samanlainen linkitetty lista, on helppoa kun löydät elementti. Sinun täytyy löytää se ensin, mutta sitten kun se poistetaan, sinun tarvitsee vain vaihtaa pari viitteitä, jos käytät erillistä ketjutusta. Jos käytät hyvää, tai jos et ole käyttäen ketjuttamalla ollenkaan teidän tiiviste, poisto on todella helppoa. Kaikki sinun tarvitsee vain hash data, ja sitten mennä kyseiseen sijaintiin. Ja olettaen et mitään törmäyksiä, voit poistaa hyvin nopeasti. 

Nyt haku on, jos asiat saada hieman monimutkaisempi. Se on keskimäärin parempi kuin liittyvät luettelot. Jos käytät ketjuttamalla, sinulla on vielä linkitetty lista, mikä tarkoittaa sinulla on vielä haku vahinkoon linkitetty lista. Mutta koska olet ottaen teidän sidoksissa lista ja jakamalla se yli 100 tai 1000 tai n elementtejä teidän tiiviste, olet liittyvät luettelot ovat kaikki yhtä nnen kokoa. He ovat kaikki olennaisesti pienempi. Olet n linkitettyjen listojen sijasta yhden linkitetyn listan koko on n. 

Ja niin tämä reaalimaailman vakio tekijä, joka me yleensä älä puhu ajoissa monimutkaisuus, se ei todella tehdä ero tässä. Joten haku on edelleen lineaarinen etsi jos käytät ketjuttamalla, mutta pituus luettelon etsit kautta on hyvin, hyvin lyhyt verrattuna. Jälleen, jos lajittelu on sinun Tavoitteena tässä, tiiviste: n luultavasti ole oikea tapa edetä. Vain käyttää array jos lajittelu on todella tärkeää sinulle. 

Ja ne voivat juosta kirjo koko. On vaikea sanoa, onko tiiviste on pieni tai iso, koska se todella riippuu kuinka suuri tiiviste on. Jos olet vain olemaan tallentamiseen viisi elementtiä teidän tiiviste, ja sinulla on tiiviste 10000 elementtejä se, olet todennäköisesti tuhlaa paljon tilaa. Kontrasti on voit myös on erittäin kompakti hash taulukoita, mutta pienempi teidän tiiviste saa, kauemmin jokainen näistä liittyvät luettelot saa. Ja joten ei todellakaan ole tapa määritellä täsmälleen koko hash-taulukon, mutta se on todennäköisesti turvallista sanoa se on yleensä tulee olla suurempi kuin linkitetty lista tallennettu samat tiedot,, mutta pienempi kuin trie. 

Ja yrittää ovat neljäs Näiden rakenteiden että olemme puhuneet. Insertoimalla trie on monimutkainen. Siellä on paljon dynaamisia muistin jakamista, varsinkin alussa, kun olet alkanut rakentaa. Mutta se on vakiona aika. Se on vain inhimillinen tekijä täällä, joka tekee siitä hankala. Ottavat kohdata nollaosoittimen, malloc tila, mennä sinne, mahdollisesti malloc tilaa sieltä taas. Tavallaan pelottelu tekijä osoittimet dynaamisen muistin jakamista on este poistaa. Mutta kun olet tyhjentänyt sen, lisäys tulee itse asiassa melko yksinkertainen, ja se varmasti on vakio ajan. 

Poisto on helppoa. Kaikki mitä sinun tarvitsee tehdä on navigoida alas pari viitteitä ja vapaa solmu, niin se on aika hyvä. Haku on myös melko nopeasti. Se on vain perustuu pituus tietosi. Joten jos kaikki tiedot on viisi merkkijonojen, esimerkiksi olet tallennuskapasiteetti on viisi merkkijonoja teidän trien, se kestää vain viisi askelta löytää mitä etsit. Viisi on vain vakio tekijä, joten jälleen, insertio, deleetio, ja haku Tässä ovat kaikki vakio aikaa, tehokkaasti. 

Toinen asia on, että trien on oikeastaan ​​eräänlainen jo järjestetty, eikö? Nojalla, miten olemme lisäämällä elementtejä, menemällä kirjeellä kirjeellä näppäintä tai numero kerrallaan avaimen, tyypillisesti, sinun trie päätyy Tällainen lajitella rakentaa sitä. Se ei oikeastaan ​​tekee järkevää ajatella lajittelu samalla tavoin ajattelemme sen paneelit, tai linkitettyjen listojen, tai hash taulukoita. Mutta jossain mielessä, teidän trie lajitellaan kuten mennä. 

Huonona puolena on tietenkin se, että trie tulee nopeasti valtava. Jokaisesta liitoskohta, saatat have-- jos avain koostuu numeroa, sinulla on 10 muuta paikkoja voit mennä, joka tarkoittaa, että jokainen solmu sisältää tietoa noin tiedot haluat tallentaa klo että solmu, lisättynä 10 osoittimia. , Jotka olivat CS50 IDE, on 80 tavua. Joten se on vähintään 80 tavua jokainen solmu että luot, ja että ei edes lasketa tietoja. Ja jos solmut ovat kirjeet sijasta numeroa, nyt sinulla on 26 osoittimet alkaen kaikissa paikoissa. Ja 26 kertaa 8 on todennäköisesti 200 tavua, tai jotain sellaista. Ja sinulla on pääomaa ja lowercase-- voit katso minne olen menossa tämän, eikö? Solmut voi saada todella iso, ja niin trie itse, yleinen, voi saada todella suuri, liian. Joten jos tilaa on korkea Premium järjestelmään, trie ehkä ole oikea tapa mennä, vaikka sen muut edut kuvaan. Olen Doug Lloyd. Tämä on CS50.