1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> Кевин Шмид: Понекогаш, кога изградба на
програма, можеби ќе сакате да се користат

3
00:00:10,890 --> 00:00:13,190
податочна структура позната како речник.

4
00:00:13,190 --> 00:00:17,960
Речник мапи клучеви, кои се
обично стрингови, на вредностите, ints,

5
00:00:17,960 --> 00:00:21,900
карактери, покажувач на некој предмет,
она што го сакаме.

6
00:00:21,900 --> 00:00:26,510
Тоа е исто како обичен речници
таа мапа зборови преку дефиниции.

7
00:00:26,510 --> 00:00:29,440
>> Речници ни даваат со
способност да ја запази информацијата

8
00:00:29,440 --> 00:00:32,750
поврзани со нешто
и го гледам нагоре подоцна.

9
00:00:32,750 --> 00:00:36,620
Па, како да ние всушност се имплементира
речник во, да речеме, C код што можеме

10
00:00:36,620 --> 00:00:38,460
користат во една од нашите програми?

11
00:00:38,460 --> 00:00:41,790
Па, постојат многу начини на кои
ние би можеле да спроведат речник.

12
00:00:41,790 --> 00:00:45,930
>> За едно, ние може да се користи низа која ние
динамички ре-големина или ние може да се користи

13
00:00:45,930 --> 00:00:49,150
поврзана листа, хаш табелата
или бинарно дрво.

14
00:00:49,150 --> 00:00:52,250
Но, она што ние го избираме, ние треба да
да се сетат на ефикасноста и

15
00:00:52,250 --> 00:00:54,300
ефикасноста на спроведувањето.

16
00:00:54,300 --> 00:00:57,930
Ние треба да се размислува за алгоритам се користи
да се вметне и гледам нагоре предмети во

17
00:00:57,930 --> 00:00:59,120
нашите податоци структура.

18
00:00:59,120 --> 00:01:03,060
>> За сега, да претпоставиме дека ние
сакате да го користите низи како клучеви.

19
00:01:03,060 --> 00:01:07,290
Ајде да зборуваме за една можност,
податочна структура наречена TRIE.

20
00:01:07,290 --> 00:01:11,210
Па тука е визуелна репрезентација
на TRIE.

21
00:01:11,210 --> 00:01:14,590
>> Како на сликата сугерира, на TRIE
е дрво структура на податоци со

22
00:01:14,590 --> 00:01:16,050
јазли поврзани заедно.

23
00:01:16,050 --> 00:01:19,420
Можеме да видиме дека таму е јасно корен
јазол со некои линкови се протега до

24
00:01:19,420 --> 00:01:20,500
други јазли.

25
00:01:20,500 --> 00:01:23,040
Но она што не секој јазол се состои од?

26
00:01:23,040 --> 00:01:26,700
Ако претпоставиме дека ние сме чување клучеви
со само букви, и

27
00:01:26,700 --> 00:01:30,150
ние не се грижат за капитализација,
тука е дефиниција на јазол дека

28
00:01:30,150 --> 00:01:31,100
ќе бидат доволни.

29
00:01:31,100 --> 00:01:34,130
>> Објект чија тип е struct
јазол има два дела

30
00:01:34,130 --> 00:01:35,740
наречен податоци и деца.

31
00:01:35,740 --> 00:01:39,200
Ние сме оставени на податоци дел како коментар
да биде заменет од страна на компонента

32
00:01:39,200 --> 00:01:43,190
декларација кога struct јазол е
инкорпорирани во C програма.

33
00:01:43,190 --> 00:01:47,040
Податоците дел од еден јазол може да биде
Булова вредност да се укаже дали или

34
00:01:47,040 --> 00:01:51,160
не јазол претставува заокружување
на речник клуч или тоа може да биде

35
00:01:51,160 --> 00:01:54,240
низа претставуваат дефиниција
на зборот во речникот.

36
00:01:54,240 --> 00:01:58,870
>> Ќе искористиме лице смешковци за да се покаже
кога податоци е присутен во јазол.

37
00:01:58,870 --> 00:02:02,310
Постојат 26 елементи во нашата
деца низа, еден индекс

38
00:02:02,310 --> 00:02:03,690
на буква.

39
00:02:03,690 --> 00:02:06,570
Ќе видиме значењето
на овој наскоро.

40
00:02:06,570 --> 00:02:10,759
>> Ајде да добие одблизу на root јазол
во нашата дијаграм, кој нема податоци

41
00:02:10,759 --> 00:02:14,740
поврзани со него, како што е наведено од страна на
отсуство на лицето смешковци во

42
00:02:14,740 --> 00:02:16,110
дел со податоци.

43
00:02:16,110 --> 00:02:19,910
Стрелките се протега од делови на
низа на децата претставуваат не-јазол

44
00:02:19,910 --> 00:02:21,640
покажувачи на други јазли.

45
00:02:21,640 --> 00:02:25,500
На пример, на стрелката се протега од
вториот елемент на деца

46
00:02:25,500 --> 00:02:28,400
претставува буквата Б
во клучна речникот.

47
00:02:28,400 --> 00:02:31,920
И во поголемите дијаграм
ние го етикета со Б

48
00:02:31,920 --> 00:02:35,810
>> Имајте на ум дека во поголемите дијаграм, кога ние
подготви покажувач до друг јазол, таа

49
00:02:35,810 --> 00:02:39,100
не е важно каде стрела
ги исполнува дека друг јазол.

50
00:02:39,100 --> 00:02:43,850
Нашиот примерок речник TRIE содржи
два збора, кои и зум.

51
00:02:43,850 --> 00:02:47,040
Ајде да одиме преку примерот на
угледување на податоци за клучот.

52
00:02:47,040 --> 00:02:50,800
>> Да претпоставиме дека сакаме да се погледне до
соодветна вредност за клучните бања.

53
00:02:50,800 --> 00:02:53,610
Ние ќе започнеме нашата Побарајте
во коренот јазол.

54
00:02:53,610 --> 00:02:57,870
Тогаш ние ќе се ја првата буква од нашата
клуч, Б, и да се најде соодветната

55
00:02:57,870 --> 00:03:00,020
место во нашите деца низа.

56
00:03:00,020 --> 00:03:04,490
Забележите дека постојат точно 26 места
во низа, по еден за секоја буква од

57
00:03:04,490 --> 00:03:05,330
азбука.

58
00:03:05,330 --> 00:03:08,800
И ќе имаме спотови претставуваат
букви од азбуката во ред.

59
00:03:08,800 --> 00:03:13,960
>> Ние ќе се погледне на вториот индекс тогаш,
индекс на еден, за B. Во принцип, ако ние

60
00:03:13,960 --> 00:03:17,990
има некои буква C ние
може да се утврди соодветната место

61
00:03:17,990 --> 00:03:21,520
кај децата низа користите
пресметка вака.

62
00:03:21,520 --> 00:03:25,140
Ние може да се користат поголеми деца
низа ако сакаме да им понуди Побарајте од

63
00:03:25,140 --> 00:03:28,380
копчињата со поширок спектар на карактери,
како што целиот

64
00:03:28,380 --> 00:03:29,880
ASCII карактери.

65
00:03:29,880 --> 00:03:32,630
>> Во овој случај, на покажувачот
во нашите деца низа на

66
00:03:32,630 --> 00:03:34,320
индекс на еден не е нула.

67
00:03:34,320 --> 00:03:36,600
Па ние ќе продолжам да го барам
до клучните бања.

68
00:03:36,600 --> 00:03:40,130
Ако некогаш се сретнал null покажувачот
на соодветна самото место кај децата

69
00:03:40,130 --> 00:03:43,230
низа, додека ние поминува јазли,
тогаш ќе мора да се каже дека ние

70
00:03:43,230 --> 00:03:45,630
не можев да најдам ништо за тој клуч.

71
00:03:45,630 --> 00:03:49,370
>> Сега, ние ќе преземе второто писмо на
нашите клучни, А, и да продолжи по

72
00:03:49,370 --> 00:03:52,400
покажувачи во овој начин, додека ние
стигне до крајот на нашиот клуч.

73
00:03:52,400 --> 00:03:56,530
Ако стигнуваме до крајот на клуч без
притискање на сите мртви краеви, нула покажувачи,

74
00:03:56,530 --> 00:03:59,730
како што е случајот овде, тогаш ние само
мора да се провери уште една работа.

75
00:03:59,730 --> 00:04:02,110
Е овој клуч всушност
во речникот?

76
00:04:02,110 --> 00:04:07,660
>> Ако е така, ние треба да се најде вредноста, и на
Smiley Face икона во нашата дијаграм каде

77
00:04:07,660 --> 00:04:08,750
зборот завршува.

78
00:04:08,750 --> 00:04:12,270
Ако постои нешто друго чуваат со
на податоци, тогаш можеме да го вратат.

79
00:04:12,270 --> 00:04:16,500
На пример, клучниот зоолошка градина не е во
речник, иако ние би можеле да имаат

80
00:04:16,500 --> 00:04:19,810
до крајот на овој клуч без некогаш
притискање на нула покажувач, додека ние

81
00:04:19,810 --> 00:04:21,089
iterate преку TRIE.

82
00:04:21,089 --> 00:04:25,436
>> Ако се обидовме да се погледне до клучните бања,
за вториот низа индекс минатата јазол,

83
00:04:25,436 --> 00:04:28,750
одговара на букви H, ќе
се одржа null покажувачот.

84
00:04:28,750 --> 00:04:31,120
Па бања не е во речникот.

85
00:04:31,120 --> 00:04:34,800
И така TRIE е уникатна по тоа што на копчињата
никогаш не се експлицитно се чуваат во

86
00:04:34,800 --> 00:04:36,650
структурата на податоци.

87
00:04:36,650 --> 00:04:38,810
Така како ние да вметнете нешто
во TRIE?

88
00:04:38,810 --> 00:04:41,780
>> Ајде да вметнете клучните
зоолошката градина во нашите TRIE.

89
00:04:41,780 --> 00:04:46,120
Се сеќавам дека се соочуваат со смешковци во еден јазол
би можеле да одговараат во кодот на едноставен

90
00:04:46,120 --> 00:04:50,170
Булова вредност да се покаже дека зоолошката градина
е во речникот Или тоа би можело

91
00:04:50,170 --> 00:04:53,710
одговараат на повеќе информации што ние
сакаат да се дружат со клучните зоолошката градина,

92
00:04:53,710 --> 00:04:56,860
како дефиниција на
збор или нешто друго.

93
00:04:56,860 --> 00:05:00,350
На некој начин, процесот за да вметнете
нешто во TRIE е сличен на

94
00:05:00,350 --> 00:05:02,060
угледување нешто во TRIE.

95
00:05:02,060 --> 00:05:05,720
>> Ќе започнеме со коренот јазол повторно,
следниве насоки одговара на

96
00:05:05,720 --> 00:05:07,990
писмата на нашиот клуч.

97
00:05:07,990 --> 00:05:11,310
За среќа, бевме во можност да го следат совети
сите на патот до стигнавме

98
00:05:11,310 --> 00:05:12,770
на крајот на клучот.

99
00:05:12,770 --> 00:05:16,480
Од зоолошката градина е префикс на зборот
зум, кој е член на

100
00:05:16,480 --> 00:05:19,440
речник, ние не треба да се
распредели секој нов јазли.

101
00:05:19,440 --> 00:05:23,140
>> Можеме да менувате јазол да се покаже дека
патот на карактери кои водат до

102
00:05:23,140 --> 00:05:25,360
тоа претставува клучен во нашата речникот.

103
00:05:25,360 --> 00:05:28,630
Сега, ајде да се обидеме вметнување на
Клучот БАЊА во TRIE.

104
00:05:28,630 --> 00:05:32,260
Ќе почнеме во коренот јазол
и да ги следат совети повторно.

105
00:05:32,260 --> 00:05:35,620
Но, во оваа ситуација, ние хит мртов
заврши пред ние сме во можност да се дојде до

106
00:05:35,620 --> 00:05:36,940
крајот на клучот.

107
00:05:36,940 --> 00:05:40,980
Сега, ние ќе треба да одвои некои нови
јазли ќе треба да одвои еден нов

108
00:05:40,980 --> 00:05:43,660
јазол за секој останатите
писмо од нашите клучни.

109
00:05:43,660 --> 00:05:46,740
>> Во овој случај, ние само треба
за алоцирање на еден нов јазол.

110
00:05:46,740 --> 00:05:50,590
Тогаш ние ќе треба да се направи H индекс
референтни оваа нова јазол.

111
00:05:50,590 --> 00:05:54,070
Уште еднаш, ние може да го менува јазол
укажуваат на тоа дека на патот на карактери

112
00:05:54,070 --> 00:05:57,120
доведува до тоа претставува
Клучот во нашата речникот.

113
00:05:57,120 --> 00:06:00,730
Ајде да се причина за асимптотска
комплексноста на нашето процедури за овие

114
00:06:00,730 --> 00:06:02,110
две операции.

115
00:06:02,110 --> 00:06:06,420
>> Ќе забележиме дека и во двата случаи на бројот
на скалилата по кои нашите алгоритам траеше беше

116
00:06:06,420 --> 00:06:09,470
пропорционален на бројот на
букви во збор.

117
00:06:09,470 --> 00:06:10,220
Дека е во право.

118
00:06:10,220 --> 00:06:13,470
Кога сакате да се погледне до зборот во
TRIE вие само треба да iterate преку

119
00:06:13,470 --> 00:06:17,100
буквите една по една додека можете
до крајот на збор или

120
00:06:17,100 --> 00:06:19,060
хит ќорсокак во TRIE.

121
00:06:19,060 --> 00:06:22,470
>> И кога сакате да вметнете клучните
вредност пар во TRIE употребувајќи го

122
00:06:22,470 --> 00:06:26,250
постапка што се дискутира, во најлош случај
ќе имаш доделување на нов јазол

123
00:06:26,250 --> 00:06:27,550
за секоја буква.

124
00:06:27,550 --> 00:06:31,290
И ние ќе се претпостави дека распределбата
е постојана време операција.

125
00:06:31,290 --> 00:06:35,850
Значи, ако ние се претпостави дека клучот должина е
граничи со фиксен постојано, и

126
00:06:35,850 --> 00:06:39,400
вметнување и гледам нагоре се постојани
Времето операции за TRIE.

127
00:06:39,400 --> 00:06:42,930
>> Ако ние не го прават овој претпоставката дека
Должината на клучот се граничи со фиксна

128
00:06:42,930 --> 00:06:46,650
константа, тогаш вметнување и гледам нагоре,
во најлош случај, линеарна во

129
00:06:46,650 --> 00:06:48,240
Должината на клучот.

130
00:06:48,240 --> 00:06:51,800
Забележи дека бројот на предмети зачувани
во TRIE не влијае на погледот

131
00:06:51,800 --> 00:06:52,820
или вметнување време.

132
00:06:52,820 --> 00:06:55,360
Тоа е само погодени од
Должината на клучот.

133
00:06:55,360 --> 00:06:59,300
>> Спротивно на тоа, додавање на записи, да речеме,
хеш табелата има тенденција да се направи

134
00:06:59,300 --> 00:07:01,250
иднина се погледне до побавно.

135
00:07:01,250 --> 00:07:04,520
Иако ова можеби звучи привлечен на прв,
ние треба да имајте на ум дека

136
00:07:04,520 --> 00:07:08,740
поволни асимптотска комплексноста не прави
значи дека во практиката податоци

137
00:07:08,740 --> 00:07:11,410
структура е нужно
надвор од срам.

138
00:07:11,410 --> 00:07:15,860
Ние, исто така, мора да сметаат дека да се складира
збор во TRIE ни треба, во најлош

139
00:07:15,860 --> 00:07:19,700
случај, бројот на јазли пропорционална
на должината на самиот збор.

140
00:07:19,700 --> 00:07:21,880
>> Се обидува имаат тенденција да користат многу простор.

141
00:07:21,880 --> 00:07:25,620
Тоа е во контраст со хаш табелата,
каде што ние треба само еден нов јазол на

142
00:07:25,620 --> 00:07:27,940
складирање на некои клучни вредност пар.

143
00:07:27,940 --> 00:07:31,370
Сега, пак во теорија, голем простор
потрошувачка не изгледа како голема

144
00:07:31,370 --> 00:07:34,620
справи, особено со оглед дека модерните
компјутерите имаат гигабајти и

145
00:07:34,620 --> 00:07:36,180
гигабајти на меморија.

146
00:07:36,180 --> 00:07:39,200
Но излегува дека ние се уште имаат
да се грижите за употребата на меморијата и

147
00:07:39,200 --> 00:07:42,540
организација за доброто на
перформанси, бидејќи современите компјутери

148
00:07:42,540 --> 00:07:46,960
имаат механизми во место под
качулка да се забрза мемориски пристап.

149
00:07:46,960 --> 00:07:51,180
>> Но, овие механизми работат најдобро кога
меморија пристапи се направени во компактен

150
00:07:51,180 --> 00:07:52,810
региони или области.

151
00:07:52,810 --> 00:07:55,910
И јазли на TRIE би можеле да живеат
насекаде во таа грамада.

152
00:07:55,910 --> 00:07:58,390
Но овие се размени
дека ние мора да се разгледа.

153
00:07:58,390 --> 00:08:01,440
>> Се сеќавам дека, кога изборот на податоците за
структура за одредена задача, ние

154
00:08:01,440 --> 00:08:04,420
треба да размислува за она што видови на
операции податочна структура треба да

155
00:08:04,420 --> 00:08:07,140
поддршка и колку перформанси
на секоја од овие

156
00:08:07,140 --> 00:08:09,080
операции работи за нас.

157
00:08:09,080 --> 00:08:11,300
Овие активности може дури
се прошири подалеку од само

158
00:08:11,300 --> 00:08:13,430
основните изглед и вметнување.

159
00:08:13,430 --> 00:08:17,010
Да претпоставиме дека сакаме да се спроведе еден вид
на авто-комплетна функционалност, многу

160
00:08:17,010 --> 00:08:18,890
како Google пребарувач не.

161
00:08:18,890 --> 00:08:22,210
Тоа е, се врати сите клучеви и
потенцијално вредности кои

162
00:08:22,210 --> 00:08:24,130
имаат дадено префикс.

163
00:08:24,130 --> 00:08:27,050
>> А TRIE е уникатно корисни
за оваа операција.

164
00:08:27,050 --> 00:08:29,890
Тоа е јасна да iterate преку
на TRIE за секој лик на

165
00:08:29,890 --> 00:08:30,950
префиксот.

166
00:08:30,950 --> 00:08:33,559
Исто како гледам нагоре операција,
ние би можеле да го следат совети

167
00:08:33,559 --> 00:08:35,400
карактер по карактер.

168
00:08:35,400 --> 00:08:38,659
Потоа, кога ќе стигнеме на крајот на
префикс, ние би можеле да iterate преку

169
00:08:38,659 --> 00:08:42,049
останатиот дел од податочната структура
бидејќи некое од копчињата за надвор

170
00:08:42,049 --> 00:08:43,980
овој момент имаат префикс.

171
00:08:43,980 --> 00:08:47,670
>> Тоа е исто така лесно да се добие листата
по азбучен ред од

172
00:08:47,670 --> 00:08:50,970
елементи на деца низа
се нареди по азбучен ред.

173
00:08:50,970 --> 00:08:54,420
Па се надевам дека ќе се разгледа
давање обидува да се проба.

174
00:08:54,420 --> 00:08:56,085
Јас сум Кевин Шмид, а тоа е CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ах, ова е почеток
на опаѓање.

177
00:09:00,790 --> 00:09:01,350
Жал ми е.

178
00:09:01,350 --> 00:09:01,870
Жал.

179
00:09:01,870 --> 00:09:02,480
Жал.

180
00:09:02,480 --> 00:09:03,130
Жал.

181
00:09:03,130 --> 00:09:03,950
>> Штрајк четири.

182
00:09:03,950 --> 00:09:04,360
Јас сум надвор.

183
00:09:04,360 --> 00:09:05,280
Жал.

184
00:09:05,280 --> 00:09:06,500
Жал.

185
00:09:06,500 --> 00:09:07,490
Жал.

186
00:09:07,490 --> 00:09:12,352
Жал ми е за правење на лице кое
мора да ја уредите оваа пукнам.

187
00:09:12,352 --> 00:09:13,280
>> Жал.

188
00:09:13,280 --> 00:09:13,880
Жал.

189
00:09:13,880 --> 00:09:15,080
Жал.

190
00:09:15,080 --> 00:09:15,680
Жал.

191
00:09:15,680 --> 00:09:16,280
>> ЗВУЧНИК 1: Добро направено.

192
00:09:16,280 --> 00:09:17,530
Тоа беше навистина добро направено.

193
00:09:17,530 --> 00:09:18,430