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
Декларация, когда структура узел
включены в программу 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
>> Давайте внимательнее посмотрим корневого узла
в нашей схеме, которая не имеет данных

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
представляет букву B
в ключе словаря.

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
Набор символов 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
Если мы когда-либо сталкивались нулевой указатель
на должном месте в детей

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
соответствующий буквой H, будет
провели нулевой указатель.

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
Тогда мы должны будем сделать индекс 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
Если вы хотите искать слово в
синтаксического дерева нужно просто перебирать

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
как поисковая система 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
>> Синтаксического дерева однозначно полезно
Для выполнения этой операции.

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
Я Кевин Шмид, и это 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