DOUG LLOYD: Så i CS50, har vi dekket en rekke forskjellige datastrukturer, ikke sant? Vi har sett arrays, og knyttes lister og hash tabeller, og prøver, stabler og køer. Vi vil også lære litt om trær og hauger, men egentlig alle disse bare ende opp som variasjoner over et tema. Det virkelig er disse form av fire grunnleggende ideer at alt annet kan koke ned til. Arrays, lenkede lister, hash tabeller og prøver. Og som jeg sa, det er variasjoner på dem, men dette er ganske mye kommer til å oppsummere alt vi kommer til å snakke om i denne klassen når det gjelder C. Men hvordan gjør alle disse måler opp, ikke sant? Vi har snakket om fordeler og ulemper av hver i separate videoer på dem, men det er mye av tall å bli kastet rundt. Det er mye av generell tanker å bli kastet rundt. La oss prøve og konsolidere den inn i bare ett sted. La oss veie fordeler mot cons, og vurdere som datastruktur kan være det riktige data struktur for din situasjon, uansett hva slags data du lagrer. Du trenger ikke nødvendigvis alltid trenger å bruke super rask innsetting, sletting, og oppslag av en trie hvis du virkelig ikke bryr seg om å sette inn og slette for mye. Hvis du bare trenger raskt tilfeldig tilgang til, kanskje en matrise er bedre. Så la oss destillere det. La oss snakke om hver av de fire store typer datastrukturer at vi har snakket om, og bare se når de kan være bra, og når de ikke kan være så bra. Så la oss starte med arrays. Så innsetting, er den slags dårlig. 

Innsetting i enden av en matrise er OK, hvis vi bygger en matrise som vi går. Men hvis vi trenger å sette inn elementer i midten, tenker tilbake til innsetting sortere, det er mye av skiftende for å passe et element i det. Og så hvis vi kommer til å sette inn hvor som helst, men i enden av en matrise, det er nok ikke så stor. 

Tilsvarende sletting, med mindre vi er sletting fra enden av en matrise, er trolig heller ikke så stor hvis vi ønsker ikke å la tomme hull, som vanligvis vi ikke. Vi ønsker å fjerne et element, og da liksom gjøre det tett igjen. Og så slette elementer fra en matrise, heller ikke så stor. 

Oppslag, skjønt, er stor. Vi har random access, konstant tid oppslag. Vi bare si syv, og vi går å rekke flytting sju. Vi sier 20, med farten til matrise flytting 20. Vi har for å iterere over. Det er ganske bra. 

Arrays er også relativt enkelt å sortere. Hver gang vi snakket om en sortering algoritme, slik som valg sort, innsetting sortere, boble sortere, flette sortere, vi alltid brukt matriser til å gjøre det, fordi arrays er ganske lett å sort, i forhold til datastrukturene vi har sett så langt. 

De er også forholdsvis liten. Det er ikke mye ekstra plass. Du bare satt akkurat så mye som du trenger for å holde dine data, og det er ganske mye det. Så de er ganske små og effektiv på den måten. Men en annen ulempe, skjønt, er at de er løst i størrelse. Vi må erklære nøyaktig hvordan big vi ønsker vår rekke å være, og vi får bare ett skudd på den. Vi kan ikke vokse og krympe det. 

Hvis vi trenger å vokse eller krympe det, vi trenger å erklære en helt ny rekke, kopiere alle elementene i den første rekke inn i den andre matrisen. Og hvis vi feilberegnet at tid, må vi gjøre det igjen. Ikke så stor. Så arrays ikke gir oss fleksibilitet å ha variable antall elementer. 

Med en lenket liste, innsetting er ganske enkelt. Vi tack bare på forsiden. Sletting er også ganske lett. Vi må finne elementene. Som involverer noen søker. 

Men når du har funnet elementet du leter etter, alt du trenger å gjøre er å endre en peker, muligens to hvis du har en koblet list-- en dobbelt lenket liste, rather-- og da kan du bare frigjøre node. Du trenger ikke å skifte alt rundt. Du bare endre to pekere, så det er ganske rask. 

Oppslag er dårlig skjønt, ikke sant? For at vi skal finne en element i en lenket liste, enten enkeltvis eller dobbelt koblet, vi må lineær søke den. Vi må begynne på begynnelsen og flytte til slutt, eller starte i slutten farten til begynnelsen. Vi har ikke random access lenger. Så hvis vi gjør en Mange søker, kanskje en lenket liste er ikke ganske så bra for oss. 

De er også veldig vanskelig å sortere, ikke sant? Den eneste måten du kan virkelig sortere en lenket liste er å sortere det som du konstruere den. Men hvis du sortere det som du konstruere det, er du ikke lenger gjøre raske innsett lenger. Du er ikke bare overvinne ting på forsiden. Du må finne den rett sted for å si det, og deretter din innsetting blir omtrent like ille som du setter inn i en matrise. Så lenkede lister er ikke så stor for å sortere data. 

De er også ganske liten, størrelse-messig. Dobbelt lenket liste litt større enn enkeltvis lenkede lister, som er litt større enn arrays, men det er ikke en enorm mengde bortkastet plass. Så hvis plassen er på en premie, men ikke en veldig intens premie, dette kan være den rette veien å gå. 

Hash tabeller. Innsetting i en hash table er ganske grei. Det er en to-trinns prosess. Først må vi kjøre våre data gjennom en hash-funksjon for å få en hash-kode, og deretter vi sett elementet inn i hash table på at hash-kode plassering. 

Sletting, ligner lenket liste, er lett når du finner elementet. Du må finne det først, men så når du sletter den, du trenger bare å utveksle et par tips, hvis du bruker separat kjeding. Hvis du bruker sondering, eller hvis du ikke bruker kjeding i det hele tatt i hash table, sletting er faktisk veldig enkelt. Alt du trenger å gjøre er hasj den data, og deretter gå til stedet. Og forutsatt at du ikke gjør det har noen kollisjoner, vil du være i stand til å slette svært raskt. 

Nå er oppslag hvor ting få litt mer komplisert. Det er i gjennomsnitt bedre enn lenkede lister. Hvis du bruker kjeding, du har fortsatt en lenket liste, som betyr at du fortsatt har søk skade en lenket liste. Men fordi du tar din linket liste og dele det over 100 eller 1000 eller n elementer i hash table, er du lenkede lister er alle ett NTH størrelsen. De er alle vesentlig mindre. Du har n knyttet lister i stedet av én lenket liste av størrelse n. 

Og så dette real-world konstant faktor, som vi vanligvis ikke snakke om i tide kompleksitet, det gjør faktisk en forskjell her. Så oppslag er fortsatt lineær søke hvis du bruker kjeding, men lengden av listen du søker gjennom er veldig, veldig kort i sammenligning. Igjen, hvis sorteringen er din Målet her, hash tabellen sannsynligvis ikke den rette veien å gå. Bare bruk en matrise hvis sortering er virkelig viktig for deg. 

Og de kan kjøre gamut av størrelsen. Det er vanskelig å si om en hash table er liten eller stor, fordi det er egentlig avhengig av hvor stor hash table er. Hvis du bare skal lagre fem elementer i hash table, og du har en hash table med 10.000 elementer i det, er du sannsynligvis kaste bort mye plass. Kontrast til at du kan også har veldig kompakte hash tabeller, men mindre din hash table blir, jo lenger hver av disse lenkede lister blir. Og så det er egentlig ingen måte å definere nøyaktig størrelsen på en nøkkeltabell, men det er nok trygt å si at det er generelt kommer til å bli større enn en koblet listen lagrer de samme data, men mindre enn en trie. 

Og prøver er den fjerde av disse strukturene at vi har snakket om. Sette inn en trie er kompleks. Det er mye av dynamisk minnetildeling, særlig i begynnelsen, som du begynner å bygge. Men det er konstant tid. Det er bare det menneskelige element her som gjør det vanskelig. Å måtte møte nullpeker, malloc plass, går det, muligens malloc plass derfra igjen. Den slags trusler faktor på pekere i dynamisk minne allokering er hinderet for å fjerne. Men når du har ryddet det, innsetting kommer faktisk ganske enkelt, og det absolutt er konstant tid. 

Sletting er enkelt. Alt du trenger å gjøre er å navigere ned en par pekere og gratis noden, så det er ganske bra. Oppslag er også ganske fort. Det er bare basert på den lengden av dine data. Så hvis alle dine data er fem tegnstrenger, for eksempel, du lagrer five tegnstrenger i din trie, det tar bare fem trinn til finne det du leter etter. Five er bare en konstant faktor, så igjen, innsetting, sletting, og oppslag her er alle konstant tid, effektivt. 

En annen ting er at din trie er faktisk slags allerede sortert, ikke sant? I kraft av hvordan vi er sette inn elementer, ved å gå bokstav for bokstav i tasten eller tall for tall av nøkkelen, vanligvis ender opp som din trie slags sortert som du bygger den. Det gjør egentlig ikke gjør fornuftig å tenke på sortering på samme måte som vi tenker på det med matriser, eller lenkede lister, eller hash tabeller. Men på en måte, din trie er sortert som du går. 

Ulempen er selvfølgelig at en trie raskt blir enorme. Fra hvert knutepunkt, kanskje du have-- hvis nøkkelen består av tall, du har 10 andre steder du kan gå, som betyr at hver node inneholder informasjon om dataene du ønsker å lagre på at node, pluss 10 pekere. Som på CS50 IDE, er 80 byte. Så det er minst 80 byte for hver node som du oppretter, og det er ikke engang telle data. Og hvis nodene er bokstaver i stedet for tall, nå har du 26 tips fra hvert sted. Og 26 ganger 8 er trolig 200 byte, eller noe sånt. Og du har kapital og lowercase-- du kan se hvor jeg kommer med dette, ikke sant? Dine noder kan bli virkelig stor, og slik at trie selv, samlet, kan får virkelig stor, også. Så hvis plass er på et høyt premie på systemet, en trie er kanskje ikke den rette måten å gå, selv om de andre fordelene spiller inn. Jeg er Doug Lloyd. Dette er CS50.