Даг LLOYD: Значи во CS50, ние сме опфатени голем број на различни структури на податоци, нели? Видовме низи, и се поврзани листи и хаш маси, и неуспешни обиди, Купишта и редици. Ние исто така ќе научат малку околу дрвја и купишта, но, навистина тие се само крајот Регистрација биде варијации на тема. Тука навистина се овие вид на четири основни идеи дека сè друго може да се сведуваат на. Низи, поврзани листи, хаш маси, и се обидува. И како што реков, има варијации на нив, но ова е прилично многу се случува да резимираме сè што ние ќе треба да се зборува за во оваа класа во однос на В. Но, како што овие сите мерка се, нели? Ние разговаравме за добрите и лошите страни на секој во одделни видеа на нив, но има голем број на броеви се фрлени околу. Има многу од општ мисли се фрлени околу. Ајде да се обидеме и да се консолидираат тоа во само едно место. Ајде да тежат добрите против лошите страни, и да се разгледа која податочна структура може да биде вистинскиот податоци структура за конкретна ситуација, без оглед на видот на податоците сте чување. Не мора да значи секогаш треба да користат супер брз вметнување, бришење, и пребарување на Trie ако навистина не се грижат за вметнување и бришење премногу. Ако ви е потребна само брзо се случајни пристап, можеби низа е подобро. Значи, да се дестилираат тоа. Ајде да зборуваме за секоја од четирите Како главни видови на структури на податоци кои ние разговаравме за, и само да се види кога тие би можеле да бидат добри, и кога тие не може да биде толку добар. Значи, да почнеме со низи. Па вметнување, тоа е вид на лошо. 

Вметнување на крајот од низата е во ред, ако градиме низа како што ние одиме. Но, ако ние треба да го вметнете елементи во средината на теренот, сетам на вметнување вид, има многу на менувањето за да ги собере на елемент во таму. И така, ако ние се случува да внесете насекаде, но на крајот на низа, што веројатно не е толку голема. 

Слично на тоа, бришење, освен ако ние сме бришење од крајот на низа, е веројатно, исто така, не е толку голема, ако ние не сакаме да се остави со празни празнини, кои обично ние не. Ние сакаме да се отстрани елементот, и тогаш вид на направи тоа Сит повторно. И така бришење елементи од низа, исто така, не е толку голема. 

Пребарување, сепак, е голема. Имаме случаен пристап, постојана време пребарување. Ние само велат седум, и одиме до низа релокација седум. Велиме 20, со Одете на Низа релокација 20. Ние не треба да iterate во пречник. Тоа е прилично добро. 

Низи се исто така релативно лесно да се најде решение. Секој пат кога ние разговаравме за сортирање алгоритам, како што се избор на вид, вметнување вид, меур вид, се спојуваат вид, ние секогаш се користи низи да го направи тоа, бидејќи низи се прилично лесно да се вид, во однос на структури на податоци ние сме виделе досега. 

Тие се исто така релативно мал. Таму не е многу на дополнителен простор. Можете само да се издвои точно колку што треба да се одржи на вашите податоци, и тоа е доста тоа многу. Па тие се прилично мали и ефикасно на тој начин. Друга лоша работа, но, сепак, е тоа што тие се фиксни во големина. Ние мора да се декларираат како точно големи сакаме нашата низа да биде, а ние само се добие еден истрел во тоа. Ние не може да расте и да се намали. 

Ако ние треба да се зголеми или да се намали, ние треба да се изјасни една сосема нова низа, копија од сите елементи на Првата низа во втората низа. А ако се погреши што време, ние треба да го направат тоа повторно. Не толку голема. Па низи не ни даваат флексибилност да имаат променлив број на елементи. 

Со поврзани листа, вметнување е прилично лесно. Ние само тактика на предниот дел. Бришење е исто така многу лесно. Ние треба да се најде на елементите. Кои вклучуваат некои пребарување. 

Но, откако ќе се најде на елементот сте во потрага за, сите што треба да направите е промена на покажувачот, евентуално две ако имаш поврзан list-- двојно поврзани листа, rather-- и можеш само да ги ослободат јазол. Вие не мора да се префрлат сè наоколу. Можете само да се промени два покажувачи, па тоа е прилично брзо. 

Пребарување е лошо иако, нели? Со цел за нас да се најде елемент во една поврзана листа, дали со единечна или двојна врска, ние треба да се линеарни тоа истражување. Ние треба да започне на почетокот и се движи до крајот, или на проектот на крајот потег на почеток. Немаме случаен пристап повеќе. Значи, ако ние сме прави многу бараат, можеби поврзана листа не е баш толку добро за нас. 

Тие се, исто така, навистина тешко да се најде, нели? Единствениот начин на кој може да се навистина вид на поврзани листа е да се најде решение за тоа како да го изгради. Но, ако го најде решение како ќе се конструкција, не си веќе со што брзо инсерции повеќе. Вие не сте само tacking работите на предниот дел. Мора да се најде на право место да го стави, а потоа вашата вметнување станува речиси толку лоша како вметнување во низа. Така поврзани листи не се толку голема за подредување на податоците. 

Тие се исто така прилично мали, со големина од-мудрец. Двојно поврзана листа малку поголеми од одделно поврзани листи, кои се малку поголеми од низи, но тоа не е огромна сума на потроши простор. Значи, ако просторот е премија, но не е навистина интензивен премија, ова може да биде вистинскиот начин да се оди. 

Хаш маси. Вметнување во хаш табелата е прилично јасна. Тоа е процес од два чекори. Прво треба да се кандидира на нашите податоци преку хеш функција да добие код хаш, а потоа се внесува елемент во хаш табелата во тоа хаш кодот локација. 

Бришење, слични на поврзани листа, е лесно кога ќе се најде на елементот. Вие треба да го најде на прво место, но тогаш кога ќе го избришете, вие само треба да се разменат неколку совети, ако сте со користење на одделни врзувањето. Ако сте со користење љубопитство, или ако не сте користење на врзувањето на сите во вашиот хаш табелата, бришење е всушност навистина лесно. Се што треба да направите е да хаш на податоци, а потоа оди на таа локација. И под претпоставка дека не се направи никакви судири, ќе бидат во можност да ги избришете многу брзо. 

Сега, пребарување е местото каде што работи добие малку посложена. Тоа е во просек подобро отколку поврзани листи. Ако сте со користење врзувањето, се уште имаат поврзани листа, што значи дека се уште имаат пребарување штета на поврзани листа. Туку затоа што сте се преземе вашата врска листа и расцепувањето над 100 или 1000 или n елементи во вашиот хаш табелата, ти си поврзани листи сите сте едно енти големината. Сите тие се значително помали. Сте n поврзани листи наместо на едно поврзани листа на големина n. 

Па така ова реалниот свет постојана фактор, што ние обично не зборуваат за во времето сложеност, всушност не се направи разлика тука. Па пребарување сеуште е линеарна пребарување ако сте користење на врзувањето, но должината на листата сте во потрага преку е многу, многу краток во споредба. Повторно, ако сортирање е вашиот цел овде, хаш табелата Веројатно не е вистинскиот начин да се оди. Само ако се користи низа сортирање е навистина важно за вас. 

И тие може да се кандидира на спектарот на големината. Тешко е да се каже дали еден хаш табелата е мал или голем, затоа што тоа навистина зависи од колку е голема вашата хаш табелата е. Ако сте само ќе треба да се чување петте елементи во вашата хаш табелата, и имаш хаш табелата со 10.000 елементи во него, ти си веројатно се губи многу простор. Контраст Можете исто така, може да се биде имаат многу компактен хаш маси, но помала вашиот хаш табелата добива, на подолг секоја од оние поврзани листи добива. И така има навистина нема начин да се дефинира точно големината на хаш табелата, но тоа е веројатно безбедно да се каже тоа е обично нема да биде поголема од поврзани листа чување на истите податоци, но помала од Trie. 

И се обидува се четврта на овие структури дека ние сме биле зборува. Внесување на некој Trie е комплексен. Има многу на динамички распределбата на меморија, особено на почетокот, како сте почнуваат да се изгради. Но, тоа е постојана време. Тоа е само човечкиот елемент тука што го прави слабо. Морале да се судрите со нулти покажувач, Примерок простор, оди таму, можеби Примерок простор од таму повторно. Вид на заплашување фактор на покажувачи во динамична алокација на меморија е пречка да се расчисти. Но, откако ќе го расчисти, вметнување всушност доаѓа прилично едноставна, и тоа сигурно не е константна време. 

Бришење е лесно. Се што треба да направите е да се движите надолу Неколку совети и бесплатно на јазол, па тоа е прилично добар. Збор е, исто така, прилично брзо. Тоа е само врз основа на должина на вашите податоци. Значи, ако сите на вашите податоци е пет жици карактер, на пример, сте чување пет ликот жици во вашиот Trie, тоа трае само пет чекори за да се најде она што го барате. Петка е само постојана фактор, па повторно, вметнување, бришење и пребарување тука се сите постојана време, ефективно. 

Друга работа е тоа што вашиот Trie е всушност вид на веќе сортирана, нели? Врз основа на тоа како ние сме вметнување на елементи, со одење буква по буква од клуч, или цифрениот страна цифрениот на клучот, Вообичаено, вашето Trie завршува се вид на подредени како што ја изгради. Тоа навистина не прави смисла да се размислува за подредување на ист начин на кој размислуваме за тоа со низи, или поврзани листи, или хаш маси. Но, во извесна смисла, вашиот Trie е сортирана, како ви одат. 

Во надолна линија, се разбира, е дека на Trie брзо станува огромна. Од секоја крстосница момент, може да have-- ако вашиот клуч се состои од бројки, имате 10 други места каде што може да оди, која значи дека секој јазол Содржи информации за податоците кои сакате да ги чувате на тој јазол, плус 10 покажувачи. Која, на CS50 ИРО, е 80 бајти. Така, тоа е најмалку 80 бајти за секој јазол што ќе се создаде, и тоа не е дури и пребројување на податоци. И ако вашиот јазли се писма, наместо на бројки, сега имате 26 совети од секоја локација. И 26 пати е 8 веројатно 200 бајти, или нешто слично. И имаш капитал а вие може lowercase-- види каде ќе одам со ова, нели? Вашиот јазли може да се навистина големите, така и на Trie себе, во целост, може се навистина голема, премногу. Значи, ако просторот е на високо премија на вашиот систем, на Trie може да не е вистинскиот начин да се оди, иако други бенефиции доаѓаат во игра. Јас сум Даг Лојд. Ова е CS50.