DOUG LLOYD: Dus in CS50, we hebben bedekt veel verschillende gegevensstructuren toch? We hebben gezien arrays, en gekoppeld lijsten en hash tabellen, en probeert, stacks en wachtrijen. We zullen ook leren een beetje over bomen en hopen, maar echt deze allemaal eindigen up zijn variaties op een thema. Er zijn echt deze soort van vier basisideeën dat alles anders kan neerkomen op. Arrays, gelinkte lijsten, hash tabellen en probeert. En zoals ik al zei, is er zijn variaties daarop, maar dit is vrij veel gaan samenvatten alles wat we gaan praten over in deze klasse in termen van C. Maar hoe deze all maatregel, toch? We hebben gesproken over de voors en tegens elk in afzonderlijke video op hen maar er is een heleboel nummers getting gegooid rond. Er is veel van de algemene gedachten krijgen gegooid rond. Laten we proberen te consolideren het in slechts een plaats. Laten we wegen de voors tegen de nadelen, en te overwegen welke gegevensstructuur misschien de juiste gegevens zijn structuur voor uw specifieke situatie, ongeacht de aard van de gegevens u opslaan. Je hoeft niet altijd nodig om gebruik maken van de supersnelle insertie, deletie, en opzoeken van een trie als je echt niet de zorg over het plaatsen en verwijderen te veel. Als je hoeft alleen maar snel willekeurige toegang, misschien een array is beter. Dus laten we destilleren dat. Laten we praten over elk van de vier belangrijke soorten datastructuren dat we hebben gesproken over, en gewoon zien als ze goed zou kunnen zijn, en wanneer ze misschien niet zo goed. Dus laten we beginnen met arrays. Zo inbrengen, dat is een soort van slecht. 

Insertie aan het einde van een array OK, Als we bouwen een array als we verder gaan. Maar als we nodig hebben om in te voegen elementen in het midden, denk terug aan het inbrengen sorteren, er is veel van een verschuiving naar een element passen daar. En dus als we gaan voegen overal, maar het einde van een array, dat is waarschijnlijk niet zo groot. 

Ook verwijderen, tenzij we zijn verwijderen van het einde van een array, is waarschijnlijk ook niet zo groot als we willen niet lege gaten te verlaten, die meestal doen we niet. We willen een element te verwijderen, en Vervolgens soort maken het weer knus. En zo het verwijderen van elementen uit een array, ook niet zo groot. 

Opzoeken, is echter groot. We hebben random access, constante tijd opzoeken. Wij zeggen slechts zeven, en we gaan array verhuizing zeven. Wij zeggen 20, met go aan scala verhuizing 20. We hoeven niet over herhalen. Dat is vrij goed. 

Arrays zijn ook relatief gemakkelijk te sorteren. Elke keer als we gesproken over een sorteer- algoritme, zoals de selectie sorteren, insertion sort, bubble sort, samenvoegen sorteren, we altijd gebruikt arrays om het te doen, omdat arrays zijn vrij gemakkelijk te sorteren opzichte van de datastructuren we tot nu toe gezien. 

Ze zijn ook relatief klein. Er is niet veel extra ruimte. Je zet gewoon opzij precies evenveel als je nodig hebt om uw gegevens te houden, en dat is vrij veel. Dus ze zijn vrij klein en efficiënt op die manier. Maar een ander nadeel, hoewel, is dat ze vast formaat. We moeten precies aangeven hoe groot willen we ons aanbod te zijn, en we krijgen slechts één schot op het. We kunnen niet groeien en krimpen. 

Als we nodig hebben om te groeien of krimpen, we moet een geheel nieuwe array te verklaren, kopieer alle elementen van de eerste array in de tweede reeks. En als we dat misrekend tijd moeten we het opnieuw doen. Niet zo groot. Dus arrays niet geven ons de flexibiliteit variabele aantallen elementen. 

Met een gekoppelde lijst, inbrengen is vrij eenvoudig. We overstag net op de voorkant. Verwijdering is ook vrij eenvoudig. We moeten de elementen vinden. Dat betrekken wat zoeken. 

Maar als je eenmaal het element hebt gevonden je zoekt, alles wat je hoeft te doen is verandering een pointer, misschien twee als je een gekoppelde list-- een dubbel gelinkte lijst, rather-- en dan kun je gewoon gratis de node. Je hoeft niet te verschuiven alles rond. Je verandert slechts twee pointers, dus dat is vrij snel. 

Lookup is slecht maar, toch? Om ons te vinden een element in een gekoppelde lijst, of enkelvoudig of dubbel gebonden, we moeten lineair doorzoeken. We moeten beginnen bij het begin en bewegen het einde of begin aan het einde verhuizing aan het begin. We hebben geen random access meer. Dus als we een doen veel zoeken, misschien een gekoppelde lijst is niet helemaal zo goed voor ons. 

Ze zijn ook erg moeilijk om te sorteren, toch? De enige manier waarop je kunt echt afstand een gelinkte lijst is om het te sorteren zoals u het construeren. Maar als je het te sorteren zoals u construeren, u niet meer bent het maken van snelle inserties meer. Je bent niet zomaar overstag dingen op de voorkant. Je moet het vinden juiste plek om het te zetten, en dan uw inlassing wordt ongeveer net zo slecht het invoegen in een array. Dus gelinkte lijsten zijn niet zo geweldig voor het sorteren van data. 

Ze zijn ook vrij klein, size-wise. Dubbel gelinkte lijst lichtjes groter dan afzonderlijk gelinkte lijsten, die iets groter zijn dan arrays, maar het is niet een enorme hoeveelheid verspilde ruimte. Dus als de ruimte is op een premie, maar niet echt een intense premie, dit zou de juiste weg te gaan. 

Hash tabellen. Inbrengen in een hash table is vrij eenvoudig. Het is een proces van twee stappen. Eerst moeten we onze data lopen door een hash-functie om een ​​hash-code te krijgen, en steek we het element in de hash table op die hash-code locatie. 

Deletie, vergelijkbaar met gekoppelde lijst, is makkelijk als je eenmaal het element te vinden. Je moet het eerst vinden, maar dan als je het verwijdert, je hoeft alleen maar uit te wisselen een paar pointers, als je met behulp aparte chaining. Als u gebruik maakt indringende, of als je niet gebruik chaining helemaal in de hash tabel, verwijdering is eigenlijk heel eenvoudig. Het enige wat u hoeft te doen is de hash data, en ga vervolgens naar die locatie. En ervan uitgaande dat je niet nog botsingen, zult u in staat om zeer snel te verwijderen. 

Nu, lookup is waar dingen een beetje ingewikkelder. Het is gemiddeld beter dan gelinkte lijsten. Als u gebruik maakt chaining, je nog steeds een gelinkte lijst, wat betekent dat u nog steeds de search nadele van een gekoppelde lijst. Maar omdat je het nemen van uw gekoppelde lijst en het splitsen van het over 100 of 1000 of n elementen in uw hash tafel, je bent gelinkte lijsten zijn allen één n de grootte. Ze zijn allemaal aanzienlijk kleiner. Je hebt n gelinkte lijsten plaats van een gelinkte lijst van grootte n. 

En dus is deze real-world constante factor, die over het algemeen we praat niet over in de tijd complexiteit, is het doet eigenlijk een verschil maken hier. Dus lookup is nog steeds lineair zoeken als je gebruik chaining, maar de lengte van de lijst Je zoekt is zeer, zeer korte vergelijking. Nogmaals, als sortering uw doel hier, hash tafel waarschijnlijk niet de juiste manier om te gaan. Gewoon gebruik maken van een array als sorteren is echt belangrijk voor je. 

En ze kunnen het gamma van grootte uit te voeren. Het is moeilijk te zeggen of een hash table is klein of groot, want het is echt afhankelijk van hoe groot uw hash tafel is. Als je alleen gaat worden opslaan vijf elementen in de hash-tabel, en je hebt een hash table met 10.000 elementen erin, bent u waarschijnlijk verspilt veel ruimte. Contrast dat u kunt ook hebben zeer compact hash tabellen, maar de kleinere uw hash tafel krijgt, hoe langer elk van deze verbonden lijsten krijgt. En dus er is echt geen manier om te bepalen precies grootte van een hash-tabel, maar het is waarschijnlijk veilig te zeggen dat het over het algemeen naar groter dan gekoppeld worden lijst opslaan van dezelfde gegevens, maar kleiner dan een trie. 

En probeert de vierde Deze structuren dat we het over. Invoegen in een trie is complex. Er is veel van dynamische toewijzing van het geheugen, vooral in het begin, als je begint te bouwen. Maar het is een constante tijd. Het is alleen de menselijke factor hier, dat maakt het lastig. Hoeven null pointer tegenkomen, malloc ruimte, er naartoe te gaan, misschien malloc ruimte vanaf daar opnieuw. Het soort intimidatie factor wijzers in dynamisch geheugen toewijzing is de hindernis te ontruimen. Maar als je eenmaal hebt gewist, insertie komt eigenlijk heel simpel, en het is zeker constante tijd. 

Verwijdering is eenvoudig. Het enige wat u hoeft te doen is te navigeren in een paar pointers en gratis het knooppunt, dus dat is vrij goed. Lookup is ook vrij snel. Het is alleen op basis van de lengte van uw gegevens. Dus als al uw gegevens vijf tekenreeksen, bijvoorbeeld, je bent het opslaan van vijf tekenreeksen in uw trie, het duurt slechts vijf stappen vinden wat je zoekt. Vijf is gewoon een constante factor, dus weer, insertie, deletie en lookup hier zijn alle constante tijd, effectief. 

Een ander ding is dat uw trie is eigenlijk wel al naargelang, toch? Op grond van de manier waarop we invoegen van elementen, door te gaan letter voor letter van de toets of cijfer voor cijfer van de sleutel, typisch, uw trie eindigt in soort naargelang als je bouwen. Het maakt eigenlijk niet maakt zin om na te denken over het sorteren op dezelfde manier waarop we denken over met arrays of gelinkte lijsten, of hash tabellen. Maar in zekere zin, je trie wordt gesorteerd als je gaat. 

Het nadeel is natuurlijk dat een trie snel wordt enorm. Vanuit elk knooppunt, zou je have-- als uw sleutel bestaat uit cijfers, heb je 10 andere plekken waar je kunt gaan, wat betekent dat elk knooppunt bevat informatie over de gegevens die u wilt opslaan op dat knooppunt, plus 10 pointers. Die op CS50 IDE, is 80 bytes. Dus is ten minste 80 bytes elk knooppunt die u maakt, en dat is niet eens tellen data. En als je knooppunten letters in plaats van cijfers, nu heb je 26 pointers vanaf elke locatie. En 26 tijden 8 waarschijnlijk 200 bytes, of iets dergelijks. En je hebt het kapitaal en lowercase-- u kunt zien waar ik ga met deze, toch? Uw knooppunten kan echt groot, en zo de Trie zelf, algemeen, kan krijgen heel groot, ook. Als de ruimte is op een hoog premie op uw systeem, een trie zou de juiste manier om niet gaan, ook al zijn andere voordelen in het spel komen. Ik ben Doug Lloyd. Dit is CS50.