Кевин Шмид: Понекогаш, кога изградба на програма, можеби ќе сакате да се користат податочна структура позната како речник. Речник мапи клучеви, кои се обично стрингови, на вредностите, ints, карактери, покажувач на некој предмет, она што го сакаме. Тоа е исто како обичен речници таа мапа зборови преку дефиниции. 

Речници ни даваат со способност да ја запази информацијата поврзани со нешто и го гледам нагоре подоцна. Па, како да ние всушност се имплементира речник во, да речеме, C код што можеме користат во една од нашите програми? Па, постојат многу начини на кои ние би можеле да спроведат речник. 

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

За сега, да претпоставиме дека ние сакате да го користите низи како клучеви. Ајде да зборуваме за една можност, податочна структура наречена TRIE. Па тука е визуелна репрезентација на TRIE. 

Како на сликата сугерира, на TRIE е дрво структура на податоци со јазли поврзани заедно. Можеме да видиме дека таму е јасно корен јазол со некои линкови се протега до други јазли. Но она што не секој јазол се состои од? Ако претпоставиме дека ние сме чување клучеви со само букви, и ние не се грижат за капитализација, тука е дефиниција на јазол дека ќе бидат доволни. 

Објект чија тип е struct јазол има два дела наречен податоци и деца. Ние сме оставени на податоци дел како коментар да биде заменет од страна на компонента декларација кога struct јазол е инкорпорирани во C програма. Податоците дел од еден јазол може да биде Булова вредност да се укаже дали или не јазол претставува заокружување на речник клуч или тоа може да биде низа претставуваат дефиниција на зборот во речникот. 

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

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

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

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

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

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

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

Ако е така, ние треба да се најде вредноста, и на Smiley Face икона во нашата дијаграм каде зборот завршува. Ако постои нешто друго чуваат со на податоци, тогаш можеме да го вратат. На пример, клучниот зоолошка градина не е во речник, иако ние би можеле да имаат до крајот на овој клуч без некогаш притискање на нула покажувач, додека ние iterate преку TRIE. 

Ако се обидовме да се погледне до клучните бања, за вториот низа индекс минатата јазол, одговара на букви H, ќе се одржа null покажувачот. Па бања не е во речникот. И така TRIE е уникатна по тоа што на копчињата никогаш не се експлицитно се чуваат во структурата на податоци. Така како ние да вметнете нешто во TRIE? 

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

Ќе започнеме со коренот јазол повторно, следниве насоки одговара на писмата на нашиот клуч. За среќа, бевме во можност да го следат совети сите на патот до стигнавме на крајот на клучот. Од зоолошката градина е префикс на зборот зум, кој е член на речник, ние не треба да се распредели секој нов јазли. 

Можеме да менувате јазол да се покаже дека патот на карактери кои водат до тоа претставува клучен во нашата речникот. Сега, ајде да се обидеме вметнување на Клучот БАЊА во TRIE. Ќе почнеме во коренот јазол и да ги следат совети повторно. Но, во оваа ситуација, ние хит мртов заврши пред ние сме во можност да се дојде до крајот на клучот. Сега, ние ќе треба да одвои некои нови јазли ќе треба да одвои еден нов јазол за секој останатите писмо од нашите клучни. 

Во овој случај, ние само треба за алоцирање на еден нов јазол. Тогаш ние ќе треба да се направи H индекс референтни оваа нова јазол. Уште еднаш, ние може да го менува јазол укажуваат на тоа дека на патот на карактери доведува до тоа претставува Клучот во нашата речникот. Ајде да се причина за асимптотска комплексноста на нашето процедури за овие две операции. 

Ќе забележиме дека и во двата случаи на бројот на скалилата по кои нашите алгоритам траеше беше пропорционален на бројот на букви во збор. Дека е во право. Кога сакате да се погледне до зборот во TRIE вие само треба да iterate преку буквите една по една додека можете до крајот на збор или хит ќорсокак во TRIE. 

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

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

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

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

Но, овие механизми работат најдобро кога меморија пристапи се направени во компактен региони или области. И јазли на TRIE би можеле да живеат насекаде во таа грамада. Но овие се размени дека ние мора да се разгледа. 

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

А TRIE е уникатно корисни за оваа операција. Тоа е јасна да iterate преку на TRIE за секој лик на префиксот. Исто како гледам нагоре операција, ние би можеле да го следат совети карактер по карактер. Потоа, кога ќе стигнеме на крајот на префикс, ние би можеле да iterate преку останатиот дел од податочната структура бидејќи некое од копчињата за надвор овој момент имаат префикс. 

Тоа е исто така лесно да се добие листата по азбучен ред од елементи на деца низа се нареди по азбучен ред. Па се надевам дека ќе се разгледа давање обидува да се проба. Јас сум Кевин Шмид, а тоа е CS50. 

Ах, ова е почеток на опаѓање. Жал ми е. Жал. Жал. Жал. 

Штрајк четири. Јас сум надвор. Жал. Жал. Жал. Жал ми е за правење на лице кое мора да ја уредите оваа пукнам. 

Жал. Жал. Жал. Жал. 

ЗВУЧНИК 1: Добро направено. Тоа беше навистина добро направено.