DOUG LLOYD: So in CS50, ons het gedek 'n baie verskillende data strukture, reg? Ons het gesien skikkings, en gekoppel lyste, en hash tabelle, en drieë, stapels en toue. Ons sal ook leer 'n bietjie oor bome en hope, maar regtig al hierdie dinge net die einde up om variasies op 'n tema. Daar is regtig hierdie soort vier basiese idees dat alles anders kan neerkom op. Skikkings, geskakelde lyste, hash tabelle, en drieë gedruk. En soos ek gesê het, is daar variasies op hulle, maar dit is mooi veel gaan om op te som alles wat ons gaan om te praat oor in hierdie klas in terme van C. Maar hoe doen hulle almal meet aan, reg? Ons het gepraat oor die voor- en nadele van elke in afsonderlike video's op hulle maar daar is 'n baie van die nommers kry gegooi rond. Daar is 'n baie algemene gedagtes kry gegooi rond. Kom ons probeer en te konsolideer dit in net een plek. Kom ons weeg die voor-teen die nadele en oorweeg wat data struktuur dalk die regte data wees struktuur vir jou spesifieke situasie, watter soort data wat jy stoor. Jy hoef nie noodwendig hoef te gebruik die super vinnige inplanting, skrap, en lookup van 'n Trie as jy regtig nie omgee invoeging en verwydering te veel. As jy net nodig het vinnig ewekansige toegang, miskien 'n skikking is beter. So laat distilleer dit. Kom ons praat oor elk van die vier groot soorte data strukture wat ons het gepraat oor, en net sien wanneer hulle goed kan wees, en wanneer hulle dalk nie so goed nie. So laat ons begin met skikkings. So inplanting, dit is soort van slegte. 

Invoeging aan die einde van 'n skikking is OK, As ons bou 'n skikking soos ons gaan. Maar as ons nodig het om te voeg elemente in die middel, dink terug aan invoeging soort, daar is 'n baie van die verskuiwing van 'n element inpas daar. En so as ons gaan om in te voeg oral, maar die einde van 'n skikking, dit is waarskynlik nie so groot. 

Net so, skrap, tensy ons verwydering van die einde van 'n skikking, is waarskynlik ook nie so 'n groot as Ons wil nie leë gapings te verlaat, wat gewoonlik doen ons nie. Ons wil 'n element te verwyder, en dan soort van te maak dit weer knus. En so die verwydering van elemente 'n skikking, ook nie so groot. 

Lookup, al is, is groot. Ons het ewetoeganklike, konstante tyd lookup. Ons sê net sewe, en ons gaan om verskeidenheid hervestiging sewe. Ons sê 20, met Go om verskeidenheid hervestiging 20. Ons hoef nie te oor Itereer. Dit is redelik goed. 

Skikkings is ook relatief maklik om te sorteer. Elke keer as ons gepraat oor 'n sortering algoritme, soos seleksie soort, invoeging soort, borrelsortering, saamsmelt sorteer, het ons altyd gebruik skikkings om dit te doen, omdat skikkings is redelik maklik om te soort, relatief tot die data strukture ons het tot dusver gesien het. 

Hulle is ook relatief klein. Daar is nie 'n baie ekstra ruimte. Jy stel net opsy presies soveel as jy nodig het om jou data te hou, en dit is pretty much dit. So hulle is redelik klein en doeltreffende op dié manier. Maar 'n ander nadeel, al is, is dat hulle vaste grootte. Ons het presies verklaar hoe groot wil ons ons verskeidenheid te wees, en ons kry net een skoot op dit. Ons kan nie groei en krimp dit. 

As ons nodig het om te groei of krimp dit, ons nodig om 'n heeltemal nuwe reeks te verklaar, kopieer al die elemente van die eerste reeks in die tweede skikking. En as ons misreken dat tyd, moet ons dit weer doen. Nie so groot. So skikkings nie gee ons die buigsaamheid veranderlike getalle elemente. 

Met 'n geskakelde lys, invoeging is redelik maklik. Ons ryg net op die voorkant. Skrap is ook redelik maklik. Ons het aan die elemente te vind. Dit behels 'n soek. 

Maar sodra jy die element het gevind jy soek, al wat jy hoef te doen is verander 'n wyser, moontlik twee as jy 'n gekoppelde list-- n dubbel geskakelde lys, rather-- en dan kan jy net vry om die knoop. Jy hoef nie te skuif alles rondom. Jy verander net twee wysers, so dit is redelik vinnig. 

Lookup is sleg al is, reg? Ten einde vir ons om 'n te vind element in 'n geskakelde lys, of een-een of dubbel gekoppel, ons moet lineêre soek nie. Ons moet begin by die begin en beweeg die einde, of begin aan die einde skuif na die begin. Ons het nie ewetoeganklike meer nie. So as ons 'n doen baie soek, miskien 'n geskakelde lys is nie heeltemal so goed vir ons. 

Hulle is ook baie moeilik om te sorteer, reg? Die enigste manier wat jy kan regtig 'n geskakelde lys te sorteer is om dit te sorteer as jy dit op te rig. Maar as jy dit sorteer as wat jy bou dit, jy nie meer die maak van vinnige invoegings nie. Jy is nie net 'tacking dinge op die voorkant. Jy het die vind regte plek om dit te sit, en dan jou te voeg raak net oor so sleg die invoeging in 'n skikking. So geskakelde lyste is nie so groot vir sortering van data. 

Hulle is ook redelik klein, grootte-wyse. Dubbel geskakelde lys effens groter as enkel geskakelde lyste, wat effens groter is as skikkings, maar dit is nie 'n groot hoeveelheid van die gemors ruimte. So as ruimte is teen 'n premie, maar nie 'n baie intense premie, hierdie dalk die regte manier om te gaan. 

Hash tafels. Invoeging in 'n hash tafel is redelik eenvoudig. Dit is 'n twee-stap proses. Eerstens moet ons ons data loop deur 'n hash funksie om 'n hash-kode te kry, en dan voeg ons die element in die hash tafel op daardie hash kode plek. 

Skrap, soortgelyk aan gekoppel lys is maklik as jy die element te vind. Jy moet dit eerste te vind, maar dan wanneer jy dit verwyder, Jy hoef net te ruil 'n paar van wysers, As jy met behulp van aparte aaneenskakeling. As jy met behulp van indringende, of as jy nie gebruik van chaining ten alle in jou hash tafel, skrap is eintlik baie maklik. Al wat jy hoef te doen, is die hash data, en dan gaan jy na die plek. En die veronderstelling dat jy dit nie doen nie enige botsings, jy sal in staat wees om baie vinnig te verwyder. 

Nou, lookup is waar dinge kry 'n bietjie meer ingewikkeld. Dit is op die gemiddelde beter as geskakelde lyste. As jy met behulp van aaneenskakeling, jy nog 'n geskakelde lys, wat beteken dat jy nog steeds die soek nadeel 'n geskakelde lys. Maar omdat jy die neem van jou gekoppel lys en verdeel dit oor 100 of 1000 of n elemente in jou hash tafel, jy geskakelde lyste is almal een nde die grootte. Hulle is almal aansienlik kleiner. Jy het n geskakelde lyste plaas een gekoppel lys van grootte n. 

En so gaan dit die werklike wêreld konstante faktor, wat oor die algemeen ons praat nie oor in die tyd kompleksiteit, is dit nie eintlik 'n verskil te maak hier. So lookup nog lineêre soek as jy die gebruik aaneenskakeling, maar die lengte van die lys jy soek deur is baie, baie kort in vergelyking. Weereens, as sortering is jou doel hier, hash tafel se waarskynlik nie die regte manier om te gaan. Net gebruik 'n verskeidenheid as sortering is regtig belangrik vir jou. 

En hulle kan die spektrum van die grootte hardloop. Dit is moeilik om te sê of 'n hash tafel is klein of groot, want dit hang af van hoe groot jou hash tafel is. As jy net gaan stoor vyf elemente in jou hash tafel, en jy het 'n hash tafel met 10.000 elemente in dit, jy waarskynlik mors 'n baie ruimte. Kontrasteer om jy kan ook het 'n baie kompakte hash tabelle, maar die kleiner jou hash tafel kry, die langer elkeen van daardie geskakelde lyste kry. En so is daar werklik geen manier om te definieer presies die grootte van 'n hash tafel, maar dit is waarskynlik veilig om te sê dit is oor die algemeen gaan groter as 'n gekoppelde wees lys die stoor van die dieselfde data, maar kleiner as 'n Trie. 

En drieë is die vierde van hierdie strukture dat ons het gepraat oor. Invoeging in 'n Trie is kompleks. Daar is 'n baie dinamiese toekenning geheue, veral aan die begin, as jy begin om te bou. Maar dit is konstante tyd. Dit is net die menslike element hier wat maak dit moeilik. Om te null pointer teëkom, malloc ruimte, daar gaan, moontlik malloc ruimte van daar weer. Die soort van intimidasie faktor van wysers in dinamiese geheuetoekenning is die hekkie om skoon te maak. Maar sodra jy dit skoongemaak, voeg kom eintlik heel eenvoudig, en dit is beslis 'n konstante tyd. 

Skrap is maklik. Al wat jy hoef te doen, is opgevolg af 'n paar wenke en vry om die knoop, so dit is redelik goed. Lookup is ook redelik vinnig. Dit is net gebaseer op die lengte van jou data. So as al jou data is vyf karakterstringe, byvoorbeeld, jy stoor vyf karakterstringe in jou Trie, dit neem slegs vyf stappe om vind wat jy soek. Vyf is net 'n konstante faktor, so weer, inplanting, skrap, en soek Hier is al konstante tyd effektief. 

Nog 'n ding is dat jou Trie is eintlik soort van reeds gesorteer, reg? Op grond van hoe ons invoeging elemente, deur te gaan letter vir letter van die sleutel, of deur syfer syfer van die sleutel, Tipies, jou Trie beland soort gesorteer as jy dit bou. Dit maak nie regtig maak sin om te dink oor die sortering in dieselfde manier waarop ons dink oor met skikkings, of geskakelde lyste, of hash tabelle. Maar in 'n sekere sin, jou Trie gesorteer soos jy gaan. 

Die nadeel, natuurlik, is dat 'n Trie vinnig raak groot. Uit elke kruising punt, kan jy have-- as jou sleutel bestaan ​​uit syfers, jy het 10 ander plekke wat jy kan gaan, wat beteken dat elke node bevat inligting oor die data wat jy wil om op te slaan op daardie node, plus 10 wenke. Wat op CS50 IDE, is 80 grepe. So dit is ten minste 80 grepe vir elke node wat jy skep, en dit is nie eens tel data. En as jou nodes is letters in plaas van syfers, nou het jy 26 wenke uit elke plek. En 26 keer 8 is waarskynlik 200 grepe, of iets soos dit. En jy het kapitaal en lowercase-- kan jy sien waar ek gaan met hierdie, reg? Jou nodes kan regtig groot, en so die Trie self, algehele, kan kry regtig groot, te. So as ruimte is op 'n hoë premie op jou stelsel, 'n Trie dalk die regte manier om nie gaan, selfs al is sy ander voordele kom in die spel. Ek is Doug Lloyd. Dit is CS50.