DOUG LLOYD: Så i CS50, har vi dækket en masse forskellige datastrukturer, højre? Vi har set arrays, og forbundet lister og hash tabeller, og forsøger, stakke og køer. Vi vil også lære lidt om træer og dynger, men virkelig disse alle bare ende at blive variationer over et tema. Der er virkelig disse slags fire grundlæggende ideer at alt andet kan koges ned til. Arrays, hægtede lister, hash tabeller og forsøger. Og som jeg sagde, er der er variationer over dem, men dette er temmelig meget kommer til at opsummere alt, hvad vi kommer til at tale om i denne klasse i form af C. Men hvordan gør disse alle måle op, ikke? Vi har talt om fordele og ulemper af hver i separate videoer på dem, men der er en masse tal at blive kastet rundt. Der er en masse generel tanker blive kastet rundt. Lad os prøve og konsolidere det i ét sted. Lad os afveje fordele mod ulemperne, og overveje som datastruktur kunne være det rigtige data struktur for netop din situation, uanset hvilken type data, du opbevaring. Du behøver ikke nødvendigvis altid behøver at bruge super hurtig indsættelse, sletning, og opslag af en trie, hvis du virkelig er ligeglad indsættelse og sletning for meget. Hvis du har brug for lige hurtigt tilfældig adgang, måske et array er bedre. Så lad os destillere det. Lad os tale om hver af de fire store typer af datastrukturer at vi har talt om, og bare se, når de kunne være gode, og når de måske ikke være så god. Så lad os starte med arrays. Så indsættelse, der er slags dårlig. 

Insertion i slutningen af ​​et array er OK, hvis vi bygger et array, som vi går. Men hvis vi har brug for at indsætte elementer i midten, tænker tilbage på indsættelse sortere, der er en masse at flytte til at passe et element derinde. Og så hvis vi kommer til at indsætte overalt, men i slutningen af ​​et array, det er nok ikke så stor. 

Tilsvarende sletning, medmindre vi er sletning fra enden af ​​et array, er nok heller ikke så stor, hvis Vi ønsker ikke at efterlade tomme huller, som normalt gør vi ikke. Vi ønsker at fjerne et element, og så slags gør det lunt igen. Og så sletter elementer fra et array, heller ikke så stor. 

Opslag, er dog stor. Vi har random access, konstant tid opslag. Vi bare sige syv, og vi går til matrix udflytning syv. Vi siger 20, med gå til vifte udflytning 20. Vi behøver ikke at gentage hele. Det er temmelig godt. 

Arrays er også forholdsvis let at sortere. Hver gang vi talte om en sortering algoritme, såsom udvælgelse sortere, indsættelse sortere, boble sortere, fusionere sortere, vi altid brugt arrays til at gøre det, fordi arrays er temmelig let at Sorter forhold til de datastrukturer vi hidtil har set. 

De er også relativt lille. Der er ikke en masse ekstra plads. Du skal bare afsat nøjagtig lige så meget som du har brug for at holde dine data, og det er temmelig meget det. Så de er temmelig lille og effektivt på denne måde. Men en anden ulempe, selv om, er, at de er fastsat i størrelse. Vi er nødt til at erklære, præcis hvordan store vi ønsker, at vores array til at være, og vi får kun ét skud på det. Vi kan ikke vokse og skrumpe det. 

Hvis vi har brug for at vokse eller skrumpe det, vi nødt til at erklære en helt ny array, kopiere alle elementer i første opstilling i den anden matrix. Og hvis vi fejlberegnet, at tid, er vi nødt til at gøre det igen. Ikke så stor. Så arrays ikke giver os den fleksibilitet at have variabelt antal elementer. 

Med en sammenkædet liste, indsættelse er temmelig let. Vi har lige tack på forsiden. Sletning er også temmelig let. Vi er nødt til at finde elementerne. Det indebærer nogle søger. 

Men når du har fundet elementet du leder efter, alt hvad du behøver at gøre er at ændre en pegepind, eventuelt to, hvis du har en sammenkædet list-- en dobbelt sammenkædet liste, rather-- og så kan du bare frigøre node. Du behøver ikke at flytte alt omkring. Du skal bare ændre to pointere, så det er temmelig hurtig. 

Opslag er dårlig selv, ikke? For os at finde en element i en sammenkædet liste, om enkeltvis eller dobbelt forbundet, vi er nødt til lineær søge den. Vi er nødt til at starte ved begyndelsen og flytte enden, eller starte i slutningen farten til begyndelsen. Vi har ikke random access længere. Så hvis vi laver en masse søgning, måske en sammenkædet liste er ikke helt så godt for os. 

De er også virkelig vanskeligt at sortere, ikke? Den eneste måde du kan virkelig sortere en sammenkædet liste er at sortere det, som du konstruere den. Men hvis du sortere det som du konstruere det, er du ikke længere lave hurtige indrykninger længere. Du er ikke bare krydse ting på forsiden. Du er nødt til at finde den rigtige sted at sætte det, og så vil din indsættelse bliver omtrent lige så slemt som indsætning i et array. Så forbundne lister er ikke så stor for sortering af data. 

De er også temmelig lille, størrelse-wise. Dobbelt knyttet liste lidt større end enkeltvis hægtede lister, som er lidt større end arrays, men det er ikke en enorm mængde spildplads. Så hvis pladsen er på en præmie, men ikke en rigtig intens præmie, dette kan være den rigtige vej at gå. 

Hash tabeller. Indføring i en hashtabel er forholdsvis ligetil. Det er en to-trins proces. Først skal vi køre vores data gennem en hash-funktion for at få en hash-kode, og så vi indsætter elementet ind i hash tabellen på det hashkode placering. 

Deletion, der svarer til sammenkædet liste, er nemt, når du finder det element. Du er nødt til at finde det første, men så når du sletter den, du bare brug for at udveksle et par pointere, hvis du bruger separat kæde. Hvis du bruger sondering, eller hvis du ikke er ved hjælp af kæde overhovedet i dit hash tabel, sletning er faktisk virkelig nemt. Alt du skal gøre er at hash det data, og derefter gå til denne placering. Og forudsat du ikke gør har nogen kollisioner, vil du være i stand til at slette meget hurtigt. 

Nu opslag er, hvor tingene få lidt mere kompliceret. Det er i gennemsnit bedre end hægtede lister. Hvis du bruger kæde, du stadig har en linket liste, hvilket betyder, at du stadig har den søgning skade en sammenkædet liste. Men fordi du tager dit forbundet listen og opdele den over 100 eller 1.000 eller n elementer i dit hash tabel, er du hægtede lister er alle én n'te størrelsen. De er alle væsentligt mindre. Du har n forbundet lister i stedet af en sammenkædet liste af størrelse n. 

Og så dette virkelige verden konstant faktor, som vi generelt taler ikke om i tide kompleksitet, det rent faktisk gør en forskel her. Så opslag er stadig lineær søge, hvis du bruger kæde, men længden af ​​listen du søger gennem er meget, meget kort ved sammenligning. Igen, hvis sortering er din mål her, hash tabellens sandsynligvis ikke den rigtige vej at gå. Bare bruge et array hvis sortering er virkelig vigtigt for dig. 

Og de kan køre farveskala af størrelse. Det er svært at sige, om en hash bordet er lille eller stor, fordi det virkelig afhænger af hvor stor din hash bordet er. Hvis du kun vil være at lagre fem elementer i din hash tabellen, og du har en hash tabel med 10.000 elementer i det, du sandsynligvis spilde en masse plads. Kontrast være du også har meget kompakte hash tabeller, men mindre din hash tabel får, jo længere hver af disse forbundne lister får. Og så der er virkelig ingen måde at definere nøjagtigt størrelsen af ​​en hash tabel, men det er nok sikkert at sige, det er generelt vil være større end en sammenkædet liste lagring af samme data, men mindre end en trie. 

Og kunne er den fjerde af disse strukturer at vi har talt om. Indsættelse i en trie er kompleks. Der er en masse dynamisk hukommelse tildeling, især i begyndelsen, som du begynder at bygge. Men det er konstant tid. Det er kun det menneskelige element her, der gør det vanskeligt. At skulle støde null-pointer, malloc plads, gå der, eventuelt malloc plads derfra igen. Den slags intimidering faktor pejlemærker i dynamisk allokering af hukommelse er den hurdle at rydde. Men når du har ryddet det, indsættelse faktisk kommer ganske enkel, og det er bestemt konstant tid. 

Sletning er nemt. Alt du skal gøre er at navigere ned en par pointere og fri knudepunktet, så det er temmelig godt. Opslag er også temmelig hurtigt. Det er kun baseret på længden af ​​dine data. Så hvis alle dine data er fem tegnstrenge, for eksempel, er du lagre fem tegnstrenge i din trie, det tager kun fem trin til finde det, du leder efter. Fem er bare en konstant faktor, så igen, insertion, deletion og opslag her er alle konstant tid, effektivt. 

En anden ting er, at din trie er faktisk slags allerede sorteres, ikke? I kraft af, hvordan vi er indsætte elementer, ved at gå bogstav for bogstav af det nøgle, eller ciffer for ciffer af nøglen, typisk din Trie ender med at blive slags sorteres som du bygger det. Det betyder ikke virkelig gør mening at tænke på sortering på samme måde, vi tænker det med arrays eller hægtede lister, eller hash tabeller. Men i en vis forstand, din Trie sorteres som du går. 

Ulempen er naturligvis, at en trie hurtigt bliver stort. Fra hvert knudepunkt punkt, kan du have-- hvis din nøgle består af cifre, du har 10 andre steder, du kan gå, hvilket betyder, at hver node indeholder oplysninger om de data, du vil gemme ved dette knudepunkt, plus 10 pointere. Som på CS50 IDE, er 80 bytes. Så det er mindst 80 bytes for hver node, du opretter, Og det er ikke engang tælle data. Og hvis dine noder er bogstaver i stedet for tal, nu har du 26 pejlemærker fra hvert sted. Og 26 gange 8 er formentlig 200 byte, eller noget lignende. Og du har kapital og lowercase-- du kan se, hvor jeg har tænkt mig med dette, ikke? Dine noder kan få virkelig store og så trie selv, samlet, kan få virkelig store, også. Så hvis pladsen er på et højt præmie på dit system, en trie måske ikke den rigtige måde at gå, selvom dens andre fordele komme i spil. Jeg er Doug Lloyd. Det er CS50.