DOUG LLOYD: Så i CS50, har vi täckt en massa olika datastrukturer, höger? Vi har sett arrayer, och länkade listor och hashtabeller, och försöker, stackar och köer. Vi kommer också att lära sig lite om träd och högar, men egentligen alla dessa bara sluta upp att vara variationer på ett tema. Det finns verkligen dessa typ av fyra grundläggande idéer att allt annat kan koka ner till. Arrayer, länkade listor, hashtabeller och försöker. Och som sagt, det är variationer på dem, men detta är ganska mycket kommer att sammanfatta allt vi ska prata om i denna klass när det gäller C. Men hur gör alla dessa mått upp, eller hur? Vi har pratat om för- och nackdelar av varje i separata videor på dem, men det finns en massa siffror få kastas runt. Det finns en hel del allmän tankar blir kastas runt. Låt oss försöka konsolidera det till ett och samma ställe. Låt oss väga proffsen mot nackdelar, och överväga vilken datastruktur kan vara rätt uppgifter struktur för just din situation, oavsett typ av data du lagrar. Du behöver inte nödvändigtvis alltid behöver använda supersnabba insertion, deletion, och uppslagning av en trie om du verkligen bryr sig inte om infoga och ta bort för mycket. Om du behöver bara snabbt slumpmässig tillgång, en array är kanske bättre. Så låt oss destillera det. Låt oss tala om var och en av de fyra stora grupper av datastrukturer att vi har pratat om, och bara se när de kan vara bra, och när de kanske inte är så bra. Så låt oss börja med arrayer. Så insättning, det är typ av dåligt. 

Insättning vid slutet av en array är OK, Om vi ​​bygger en array som vi går. Men om vi behöver sätta in element i mitten, tänker tillbaka på insättning sort, det finns en hel del att flytta för att passa en del i det. Och så om vi ska infoga helst men i slutet av en array, det är nog inte så stor. 

På samma sätt, radering, om vi är radera från slutet av en array, är förmodligen inte heller så bra om Vi vill inte lämna tomma luckor, som vanligtvis gör vi inte. Vi vill ta bort ett element, och då sorts göra det ordentligt igen. Och så ta bort element från en array, också inte så stor. 

Lookup, är dock stor. Vi har direktåtkomst, konstant tid lookup. Vi säger bara sju, och vi går till array omlokalisering sju. Vi säger 20, med gå till array omlokalisering 20. Vi behöver inte iterera över. Det är ganska bra. 

Arrayer är också relativt lätt att sortera. Varje gång vi talade om en sortering algoritm, såsom val sortera, insättningssortering, bubbelsortering, slå samman sort, vi alltid använt arrayer för att göra det, eftersom arrayer är ganska lätt att sortera, i förhållande till datastrukturerna vi har sett hittills. 

De är också relativt små. Det finns inte en hel del extra utrymme. Du bara avsätta exakt så mycket som du behöver för att hålla dina data, och det är ganska mycket det. Så de är ganska små och effektivt på detta sätt. Men en annan nackdel, men, är att de är fixerade i storlek. Vi måste förklara exakt hur stora vi vill att vår array vara, och vi får endast ett skott på det. Vi kan inte växa och krympa den. 

Om vi ​​behöver för att växa eller krympa det, vi måste förklara en helt ny array, kopiera alla delar av första uppsättningen in i den andra uppsättningen. Och om vi missbedömde att tid, vi måste göra det igen. Inte så stor. Så arrayer inte ger oss flexibilitet att ha varierande antal element. 

Med en länkad lista, insättning är ganska lätt. Vi slår bara på framsidan. Strykning är också ganska lätt. Vi måste hitta elementen. Som involverar vissa sökning. 

Men när du har hittat elementet du letar efter, allt du behöver göra är att ändra en pekare, möjligen två om du har en länkad list-- en dubbelt länkad lista, rather-- och sedan kan du bara befria noden. Du behöver inte flytta allt runt. Du ändrar bara två pekare, så det är ganska snabbt. 

Lookup är dåligt men, eller hur? För för oss att hitta en element i en länkad lista, vare sig ensamma eller dubbellänkad, Vi måste linjär söka det. Vi måste börja från början och flytta slutet, eller starta i slutet flytta till början. Vi har inte random access längre. Så om vi gör en mycket söka, kanske en länkad lista är inte ganska så bra för oss. 

De är också riktigt svårt att sortera, eller hur? Det enda sättet du kan verkligen sortera en länkad lista är att sortera det som du bygga den. Men om du sorterar det som du konstruera det, du är inte längre göra snabba insättningar längre. Du är inte bara kryss saker på framsidan. Du måste hitta rätt plats för att uttrycka det, och sedan ditt insättning blir ungefär lika illa som att sätta in i en matris. Så länkade listor är inte så bra för sortering av data. 

De är också ganska liten, storleksmässigt. Listan dubbellänkad något större än var för sig länkade listor, som är något större än arrayer, men det är inte en enorm mängd oanvänt utrymme. Så om utrymmet är begränsat, men inte riktigt intensiv premie, Detta kan vara rätt väg att gå. 

Hashtabeller. Införande i en hash-tabell är ganska enkel. Det är en tvåstegsprocess. Först måste vi driva våra data genom en hashfunktion för att få en hash-kod, och sedan in vi elementet i hashtabell vid denna hash-kod plats. 

Strykning, liknande länkad lista, Det är lätt när du hittar elementet. Du måste hitta den först, men sedan när du tar bort det, du behöver bara byta ett par pekare, Om du använder separat kedja. Om du använder sondering, eller om du inte användning kedja alls i hashtabell, Strykningen är faktiskt riktigt enkelt. Allt du behöver göra är att hasha uppgifter, och sedan gå till den platsen. Och förutsatt att du inte har några kollisioner, kommer du att kunna ta bort mycket snabbt. 

Nu är lookup där saker få lite mer komplicerat. Det är i genomsnitt bättre än länkade listor. Om du använder kedja, du fortfarande har en länkad lista, vilket innebär att du fortfarande har sök förfång en länkad lista. Men eftersom du tar din länkade lista och dela den över 100 eller 1000 eller n element i hash tabellen, är du länkade listor är alla en n: te storlek. De är alla betydligt mindre. Du har n länkade listor i stället av en länkad lista av storlek n. 

Och så denna verkliga konstant faktor, som vi vanligtvis inte tala om i tid komplexitet, det gör faktiskt en skillnad här. Så lookup är fortfarande linjär söka om du använder kedja, men längden av listan du söker igenom är mycket, mycket kort i jämförelse. Återigen, om sorteringen är ditt Målet här, hash tabellens antagligen inte rätt väg att gå. Använd bara en array om sortering är verkligen viktigt för dig. 

Och de kan köra spektrat av storlek. Det är svårt att säga om en hash tabellen är liten eller stor, eftersom det verkligen beror på hur stor din hash tabellen är. Om du bara kommer att lagra fem element i hash tabellen, och du har en hashtabell med 10.000 element i det, du förmodligen ett slöseri med utrymme. Kontrast är kan du också har mycket kompakta hashtabeller, men mindre din hash tabellen blir, ju längre var och en av dessa länkade listor blir. Och så det finns verkligen inget sätt att definiera exakt storleken på en hash-tabell, men det är nog säkert säga att det är i allmänhet kommer att bli större än en länkad lista lagrar samma uppgifter, men mindre än en trie. 

Och försök är den fjärde av dessa strukturer att vi har pratat om. Sätta in en trie är komplex. Det finns en hel del dynamiskt minnesallokering, särskilt i början, som du börjar bygga. Men det är konstant tid. Det är bara den mänskliga faktorn här som gör det knepigt. Att behöva möta nollpekare, malloc utrymme, åka dit, möjligen malloc utrymme därifrån igen. Den typ av hotelser faktor pekare i dynamisk minnesallokering är hindret för att rensa. Men när du har rensat det, insättning kommer faktiskt ganska enkelt, och det är verkligen konstant tid. 

Radering är lätt. Allt du behöver göra är att navigera ned en par pekare och gratis noden, så det är ganska bra. Lookup är också ganska fort. Det är bara baserad på längden på dina data. Så om alla dina data är fem teckensträngar, till exempel, du lagra fem teckensträngar i din trie, det tar bara fem steg till hitta det du letar efter. Fem är bara en konstant faktor, så igen, insertion, deletion och lookup här är alla konstant tid, effektivt. 

En annan sak är att din trie är faktiskt ganska redan sorterats, eller hur? På grund av hur vi är infoga element, genom att gå bokstav för bokstav för nyckel, eller siffra för siffra av nyckeln, typiskt, slutar upp att vara din trie typ av sorteras som du bygger det. Det spelar egentligen ingen gör meningsfullt att tänka på sortering på samma sätt som vi tycker om det med arrayer, eller länkade listor, eller hashtabeller. Men i någon mening, ditt trie sorteras som du går. 

Nackdelen är naturligtvis är att en trie blir snabbt stora. Från varje knutpunkt, kanske du have-- om din nyckel består av siffror, du har andra 10 platser du kan gå, som innebär att varje nod innehåller information om de data du vill spara vid denna nod, plus 10 pekare. Som på CS50 IDE, är 80 byte. Så det är åtminstone 80 byte för varje nod som du skapar, och som inte är ens räkna data. Och om dina noder är bokstäver i stället för siffror, nu har du 26 tips från varje plats. Och 26 gånger 8 är förmodligen 200 byte, eller nåt sånt. Och du har kapital och lowercase-- du kan se vart jag ska med detta, eller hur? Dina noder kan bli riktigt stora, och så trie själv, totalt sett, kan bli riktigt stora, alltför. Så om utrymmet är en hög premie på ditt system, en trie kanske inte är rätt sätt att gå, även om dess övriga förmåner spelar in. Jag är Doug Lloyd. Detta är CS50.