Дъг LLOYD: Така че в CS50, ние сме обхванати много различни структури от данни, нали? Виждали сме масиви, и свързана списъци и хеш таблици, и се опитва, стекове и опашки. Ние също така ще научите малко около дървета и грамади, но наистина те просто свърши сметка е вариации по темата. Там наистина са тези вид четири основни идеи че всичко друго може да се свеждат до. Масиви, свързани списъци, хеш таблици и опит. И както казах, има са вариации на тях, но това е доста много ще обобщим всичко, което ще говорим около в този клас по отношение на C. Но как всички тези мерки се, нали? Ние говорихме за плюсовете и минусите на всеки в отделни клипове на тях, но има много номера Първи хвърлен наоколо. Има много неща, на обща размисли получаване хвърлени наоколо. Нека се опитаме и да консолидира то в само едно място. Нека да претеглят плюсовете срещу недостатъците, и да обмислят които структурата на данните може да бъде правилният данни структура за вашия конкретен случай, без значение какъв вид данни, което приберете. Не е задължително винаги трябва да използвате супер бързо вмъкване, изтриване, и справка за синтактично дърво, ако наистина не се грижи за вмъкване и изтриване твърде много. Ако имате нужда просто бързо случайна достъп, може би е по-добре масив. Така че нека да дестилират това. Нека поговорим за всеки един от четиримата основните видове структури от данни че сме говорили за и Просто вижте, когато те могат да бъдат добри, и когато не може да бъде толкова добър. Така че нека да започнем с масиви. Така вмъкване, че е нещо лошо. 

Включване в края на масив е ОК, ако ние строим масив като отидем. Но ако трябва да поставите елементи в средата, мисля, обратно на вмъкване сортиране, има много на изместване за да се поберат един елемент там. И така, ако ще да вмъкнете навсякъде, но в края на масив, че вероятно не е толкова голяма. 

По същия начин, заличаване, освен ако не сме изтриване от края на масив, е може би също не е толкова голяма, ако ние не искаме да оставим празни пропуски, които обикновено не го правим. Искаме да премахнете елемент, и След това нещо да го плътно отново. И така изтриване на елементи от масив, също не е толкова голяма. 

Търсене, обаче, е страхотно. Имаме произволен достъп, константно време за справка. Ние просто кажем, седем, и да отидем да масив преместване седем. Ние казваме, 20, с Отиди на масив преместване 20. Ние не трябва да превъртите цяла. Това е доста добър. 

Масивите са също сравнително лесно да се справи. Всеки път, когато говорихме за сортиране алгоритъм, като избор на сортиране, сортиране чрез вмъкване, метод на мехурчето, се слеят сортиране, ние винаги се използва масиви да го направя, защото масиви са доста лесни за вид, по отношение на структурите от данни сме виждали досега. 

Освен това те са сравнително малко. Там не е много допълнително пространство. Ти просто да отмени точно толкова, колкото е необходимо, за да държат вашите данни, и това е доста го много. Така че те са доста малки и ефективно по този начин. Но друг недостатък, обаче, е, че те са фиксирани по размер. Ние трябва да декларират как точно голяма искаме нашия масив да бъде, а ние само се получи един изстрел в него. Ние не може да расте и да го свие. 

Ако имаме нужда да расте или да го свие, ние трябва да декларират изцяло нов масив, копирате всички елементи на Първият масив във втория масив. И ако ние неправилно оцени, че време, ние трябва да го направя отново. Не е толкова голяма. Така масиви не ни дават гъвкавост да има променлива брой елементи. 

С свързан списък, вмъкване е доста лесно. Ние просто халс върху предната част. Заличаване също е доста лесно. Трябва да намерим елементите. Това включва известно търсене. 

Но след като веднъж сте открили елемента което търсите, всичко, което трябва да направите, е промяна на показалеца, вероятно две, ако имате свързан с двойно list-- свързан списък, rather-- и след това може просто да освободи възела. Вие не трябва да се смени всичко наоколо. Можете просто смяна два указатели, така че това е доста бързо. 

Търсене е лошо все пак, нали? За да можем да намерим елемент в свързан списък, независимо дали поотделно или двойно свързан, ние трябва да линеен го търси. Ние трябва да започнем от самото начало и преместете края, или да започне в края на ход в началото. Ние не разполагаме с произволен достъп вече. Така че, ако ние сме прави Много от търсенето, може би свързан списък не е чак толкова добро за нас. 

Освен това те са наистина трудно да се справи, нали? Единственият начин можете Наистина сортирате свързан списък е да го оправи, докато го построи. Но ако го оправи, колкото го изгради, вече не сте правене на бързи вмъквания вече. Вие не сте просто лепнали неща, върху предната част. Трябва да се намери на точното място, за да го сложи, и след това си вмъкване става въпрос само за толкова зле, като вкарате в масив. Така свързани списъци не са толкова голямо, за сортиране на данни. 

Освен това те са доста малки, размер-мъдър. Двойно свързан списък леко по-голям от поединично свързани списъци, които са малко по-голям от масиви, но това не е огромно количество губи пространство. Така че, ако пространството е ограничено, но Не наистина интензивна премия, това може да е правилният начин да отида. 

Hash маси. Включване в хеш таблица е сравнително лесно. Това е процес на два етапа. Първо трябва да се изпълнява нашите данни през хеш функция, за да получите кода, хашиш, и тогава поставете елемент в хеш таблица в този хеш код населено място. 

Заличаване, подобен на свързан списък, е лесно, след като се намери елемента. Трябва да го намеря на първо място, но тогава, когато не го изтриете, просто трябва да се обменят Няколко указатели, ако използвате отделна верижното. Ако използвате сондиране, или ако не сте използване на верижното изобщо в хеш таблица, заличаване всъщност е много лесно. Всичко, което трябва да направите, е хеш на данни, и след това отидете на това място. И ако приемем, че не правим имате някакви сблъсъци, ще можете да изтриете много бързо. 

Сега, за справка е мястото, където нещата да се получи малко по-сложно. Това е средно по-добре от свързани списъци. Ако използвате верижното, вие все още имате свързан списък, което означава, че все още имат Търсене в ущърб свързан списък. Но тъй като сте като вашия свързана списък и го разделя над 100 или 1000 или п елементи в хеш таблица, вие сте свързани списъци са един тото размера. Всички те са значително по-малък. Вие сте п свързани списъци, вместо на един свързан списък на размера п. 

И така, това в реалния свят постоянно фактор, който ние по принцип не говоря за в сложността време, то всъщност не правят разлика тук. Така че все още е линейна за справка търсите, ако използвате верижното, но дължината на списъка можете да започнете да търсите чрез е много, много кратък в сравнение. Отново, ако сортиране е вашият цел тук, хеш-таблица на Вероятно не е правилният начин да отида. Просто използвайте масив ако сортиране е наистина важно за вас. 

И те могат да стартирате гама от размери. Трудно е да се каже дали един хеш таблица е малка или голяма, защото това наистина зависи от колко голям си хеш таблица е. Ако сте само ще трябва да се съхраняват пет метални елементи в хеш таблица, и имате хеш таблица с 10,000 елементи в него, вие вероятно губите много място. Контраст, че си също може да има много компактни хеш таблици, но по-малкия си хеш таблицата получава, колкото по-дълго всеки от тези свързани списъци получава. И така, там наистина няма начин да се определи точно с размерите на хеш таблица, но това е може би безопасна да се каже, че е по принцип щеше да бъде по-голям от една свързана списък съхраняване на едни и същи данни, но по-малка от Trie. 

И се опитва са четвъртият на тези структури че ние сме били говориш. Поставяне в синтактично дърво е сложна. Има една много динамична заделяне на памет, особено в началото, като сте се започне да се строи. Но това е константно време. Това е само човешкия елемент ето, че го прави труден. Като взе да срещнете нулев указател, изчистване пространство, отидете там, евентуално изчистване пространство от там отново. Сортът за сплашване фактор указатели в динамично разпределение на паметта е препятствие, за да изчистите. Но след като веднъж сте го прочисти, вмъкване всъщност идва съвсем проста, и то със сигурност е константно време. 

Заличаване е лесно. Всичко, което трябва да направите е да се движите надолу по Няколко указатели и безплатно възела, така че това е доста добър. Търсене също е доста бърз. Тя се основава само на Дължина на вашите данни. Така че, ако всички от данните ви е пет буквени поредици, Например, можете да започнете съхраняване пет символни низове в твоята синтактично дърво, отнема само пет стъпки към намерите това, което търсите. Five е само на постоянен фактор, така че отново, вмъкване, изтриване, и за справка тук всички са константно време, ефективно. 

Друго нещо е, че си е синтактично дърво всъщност вид вече подредени, нали? По силата на това как сме вмъкване на елементи, като отидете буква по буква на ключ, или цифра по цифра на ключа, Обикновено, вашият Trie озовава вид, сортирани като сте го построили. Тя не наистина прави смисъл да се мисли за сортиране по същия начин, по който мислим за то с масиви или свързани списъци, или хеш таблици. Но в известен смисъл, си Trie се сортират като отидеш. 

Недостатъкът, разбира се, е, че синтактично дърво бързо се превръща в огромен. От всяко кръстовище точка, може да се have-- ако вашият ключ се състои от цифри, имате 10 други места можете да отидете, които означава, че всеки възел съдържа информация за данните, които искате да съхранявате в този възел, плюс 10 указатели. Което, на CS50 IDE, е 80 байта. Така че това е най-малко 80 байта за всеки възел, който създавате, И това не е дори да броим данни. И ако ви възли са букви вместо цифри, Сега имате 26 показалки от всяко населено място. И 26 пъти 8 е може би 200 байта, или нещо подобно. И вие имате капитал и вие може да lowercase-- виж къде отивам с това, нали? Вашите възли, може да получите наистина голям, така и на Trie себе си, като цяло, може да получите наистина голям, прекалено. Така че, ако пространството е висока премия на вашата система, синтактично дърво може да не е правилният начин да се отида, въпреки че други ползи да влезе в игра. Аз съм Дъг Лойд. Това е CS50.