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
Речник мапе кључеви, који су
обично ниске, на вредности, интс,

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
Па како да заправо спроводе
речник у, рецимо, Ц кода који можемо

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
Хајде да причамо о једној могућности,
структура података зове трие.

20
00:01:07,290 --> 00:01:11,210
Дакле, овде је визуелни приказ
од Трие.

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

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
>> Објекат чији је тип струцт
чвор има два дела

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
Декларација кад струцт чвор је
инкорпорирана у Ц програму.

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
>> Хајде да изблиза кореновог чвора
у нашем дијаграму, која нема података

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
Наш узорак речник садржи трие
две речи, да и зум.

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
>> Ми ћемо погледати на други индекс тада,
индекс један, за Б. У принципу, ако

60
00:03:13,960 --> 00:03:17,990
има неки алфабетски знак Ц ми
може да одреди одговарајућу место

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
АСЦИИ скуп знакова.

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
Ако се икада срели нулл показивач
на одговарајућем месту у деце

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
>> Ако је тако, требало би наћи неку вредност, добро
Галерија икона лице у нашем дијаграму где

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
поновити кроз трие.

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

83
00:04:25,436 --> 00:04:28,750
одговара слова Х, би
су одржали нулл показивач.

84
00:04:28,750 --> 00:04:31,120
Дакле, купање није у речнику.

85
00:04:31,120 --> 00:04:34,800
И тако трие је јединствен по томе тастера
се никада експлицитно чувају у

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

87
00:04:36,650 --> 00:04:38,810
Па како да убаците нешто
у трие?

88
00:04:38,810 --> 00:04:41,780
>> Хајде да ставите кључ
Зоолошки врт у нашој трие.

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
На неки начин, процес за уметање
нешто у ТРИЕ је сличан

94
00:05:00,350 --> 00:05:02,060
гледајући нешто у трие.

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
Сада, хајде да покушамо убацивања
кључ КУПАТИЛА у трие.

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
Онда ћемо морати да направи индекс Х
референтне овај нови чвор.

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
Када желите да потражите реч у
трие само треба да вршите итерацију кроз

119
00:06:13,470 --> 00:06:17,100
слова један по један док не било
до краја речи или

120
00:06:17,100 --> 00:06:19,060
ћорсокак у трие.

121
00:06:19,060 --> 00:06:22,470
>> А када желите да уметнете кључ
вредност пар у трие користећи

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
уметање и потражити су константа
време операције за трие.

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
Приметимо да је број ставки чувају
у трие не утиче на изглед горе

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
Такође морамо узети у обзир да је за складиштење
реч у трие морамо, у најгорем

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
И чворови у трие могао бораве
било где у тој гомили.

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
као Гоогле претраживач ради.

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
>> Трие је јединствено користан
за ову операцију.

164
00:08:27,050 --> 00:08:29,890
То је једноставно да вршите итерацију кроз
трие за сваки карактер

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
Онда, када смо стигли на крај
префикс, могли би поновити кроз

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
Ја сам Кевин Шмид, а то је ЦС50.

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