Даг Ллоид: Дакле, у ЦС50 смо покривени много различитих структура података, jel tako? Видели смо низова, и повезан листе, и хасх табеле, и покушава, гомила и редови. Такође ћемо научити нешто о дрвећу и гомиле, али заиста то све само крај сеттле буде варијације на тему. Заиста је ово врста четири основна идеја да је све остало може да се своде на. Арраис, повезане листе, хасх табеле, и покушава. И као што сам рекао, тамо су варијације на њима, али ово је прилично много ће се сумирати Све ћемо да причамо абоут у овој класи у смислу Ц. Али како то све мере, зар не? Разговарали смо о предностима и недостацима сваког у одвојеним видео на њима, али има доста бројева изабацују около. Има много опште мисли изабацују около. Хајде да пробамо и консолидовати је на једном месту. Хајде да вагати предности у односу на Затвореници, и узети у обзир која структура података може бити прави подаци структура за вашу одређену ситуацију, какав год да си чување података. Не мора увек треба да користити супер брзи уметање, брисање, и ИП адресу од Трие ако заиста не маре за уметање и брисање превише. Ако вам је потребна само брзо случајно приступ, можда низ је боље. Дакле, хајде да дестилирати то. Хајде да причамо о свакој од четири Главне врсте структура података да смо разговарали о, и Само погледајте кад би било добро, и кад не би било тако добро. Почнимо са низовима. Дакле убацивање, то је некако лоше. 

Постављање на крају низа је у реду, ако градимо низ како идемо. Али ако треба да убаците елемената у средини, Сетите се уметања врста, постоји много преласка да стане елемент тамо. И тако, ако ћемо да убаците било где, али крај низа, то је вероватно није толико велика. 

Слично томе, брисање, осим ако смо брисање од краја низа, је вероватно и није тако велика ако не желимо да оставим празне празнине, који обично не знамо. Желимо да уклоните елемент, и онда некако би се поново фино. И тако брисање елемената из низ, такође није тако велика. 

Проналажење, иако је сјајно. Имамо случајан приступ, константа време ИП адресу. Само реци седам, и идемо да арраи пресељења седам. Кажемо 20, са иди на Арраи пресељење 20. Ми не морамо да преко поновити. То је прилично добро. 

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

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

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

Са повезане листе, убацивање је прилично лако. Само прикаци на фронту. Брисање је такође прилично лако. Морамо да нађемо елементе. То укључује неке претраживање. 

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

Проналажење је лоше, зар не? Да би нам да пронађу елемент повезане листе, да ли појединачно или двоструко повезана, морамо да линеарна претрагу га. Морамо да почнемо од почетка и померите крај, или да почне крајем покрету на почетак. Ми више не морају случајан приступ. Дакле, ако Радимо много трагања, можда повезане листе није толико добро за нас. 

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

Такође су прилично мали, величина-мудар. Двоструко повезана листа благо већи од појединачно повезаних листи, које су мало веће од низова, али није огромна количина изгубљеног простора. Дакле, ако је простор на премије, али не стварно интензивно премија, ово може бити прави начин да се иде. 

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

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

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

И то у реалном свету константа фактор, који смо генерално не причају о сложености у временском га, не заправо чине овде разлику. Дакле ИП адресу и даље линеарна тражење ако користите уланцавање, али због дужине листе сте у потрази кроз је врло, врло кратко у поређењу. Опет, ако је ваш сортирање циљ овде, хасх сто је вероватно није прави пут којим треба ићи. Довољно је користити низ ако сортирање је заиста важно за вас. 

И они могу покренути скалу величине. Тешко је рећи да ли је Дисперзија сто је мали или велики, јер то стварно зависи колика ти хасх сто је. Ако само идете да се складиштење пет елемената у вашем хасх табели, и имате хасх табелу са 10.000 елементе у њој, вероватно губимо пуно простора. Цонтраст вам такође може да буде имају веома компактне хасх табеле, али је мањи ваш хеш табеле добија, дуже сваки од тих повезаних листи добија. И тако заиста не постоји начин да се дефинише управо величине хеш табели, али вероватно је безбедно рећи да генерално је ће бити већи него повезан Листа чување исте податке, али мање од Трие. 

И настоји су четврти од ових структура да смо причали. Убацивање у Трие је сложен. Има доста динамичан алокација меморије, нарочито на почетку, како ви почињу да граде. Али то је константа време. То је само људски елемент овде да чини незгодно. Имајући у сусрет Нулл Поинтер, маллоц простор, иди тамо, вероватно маллоц простор одатле поново. Врста застрашивања фактор показивачи у динамичку расподелу меморије је препрека да обришете. Али када сте спашава ситуацију, убацивање заправо долази прилично једноставан, и сигурно је константа време. 

Брисање је лако. Све што треба да урадите је смер наниже Неколико показивача и слободног чвора, тако да је то прилично добро. Проналажење је такође прилично брзо. То је само на основу Дужина ваших података. Дакле, ако све ваше податке је пет низови карактера, На пример, ви чување пет низови карактера у вашем Трие, потребно је само пет корака до пронађете оно што тражите. Пет је само константа фактор, тако Опет, уметање, брисање, и ИП адресу Овде су све време константан, ефикасно. 

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

Лоша страна је, наравно, да Трие брзо постаје огроман. Из сваке тачке споја, могао би бих-- ако је ваш кључ састоји од цифара, имате 10 других места можете ићи, која значи да сваком чвору садржи информације о подацима желите да сачувате у том чвору, плус 10 показивачима. Који, на ЦС50 ИДЕ, је 80 бајта. Дакле, то је најмање 80 бајтова за сваки чвор који сте креирали, и то не рачунајући чак и податке. И ако су чворови писма уместо цифара, Сада имате 26 савете из свакој локацији. И 26 пута 8 је вероватно 200 бајтова, или тако нешто. И имате капитал и ловерцасе-- вам могу видим где идем са овим, зар не? Ваши чворови могу се стварно велика, и тако Трие Сама, све у свему, могу се заиста велики, превише. Дакле, ако је простор високог премија на вашем систему, трие можда није прави начин да се го, иако њени друге бенефиције ступају на сцену. Ја сам Доуг Лојд. Ово је ЦС50.