1
00:00:00,000 --> 00:00:03,423
>> [Играет музыка]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Пэн: Добро пожаловать в неделю 6 раздела.

4
00:00:08,210 --> 00:00:11,620
Мы отклонились от нашего стандарта
раздел время во вторник

5
00:00:11,620 --> 00:00:14,130
днем, чтобы этот прекрасный воскресенье утром.

6
00:00:14,130 --> 00:00:17,330
Спасибо за всем, что
присоединился ко мне сегодня, но серьезно,

7
00:00:17,330 --> 00:00:18,170
аплодисменты.

8
00:00:18,170 --> 00:00:20,600
>> Это довольно большое усилие.

9
00:00:20,600 --> 00:00:23,600
Я почти не даже сделать его
в то время, но это было в порядке.

10
00:00:23,600 --> 00:00:27,520
Так что я знаю, что все вы
только что сделали его в викторине.

11
00:00:27,520 --> 00:00:30,370
Прежде всего, добро пожаловать в
оборотная сторона этого.

12
00:00:30,370 --> 00:00:32,917
>> Во-вторых, мы поговорим об этом.

13
00:00:32,917 --> 00:00:34,000
Мы поговорим о викторине.

14
00:00:34,000 --> 00:00:35,700
Мы поговорим о том, как
Вы делаете в классе.

15
00:00:35,700 --> 00:00:36,550
Вам будет хорошо.

16
00:00:36,550 --> 00:00:39,080
У меня есть свои викторины для
Вы в конце здесь,

17
00:00:39,080 --> 00:00:42,120
так что если вы, ребята, хотите, чтобы принять
Взгляд на него, совершенно нормально.

18
00:00:42,120 --> 00:00:46,590
>> Так быстро прежде чем мы начнем, то
Повестка дня на сегодня выглядит следующим образом.

19
00:00:46,590 --> 00:00:48,430
Как вы можете видеть, мы
в основном быстрое увольнение

20
00:00:48,430 --> 00:00:52,120
через целую кучу структур данных
действительно, действительно, действительно быстро.

21
00:00:52,120 --> 00:00:54,380
Так как таковое, оно не будет
супер интерактивная сегодня.

22
00:00:54,380 --> 00:00:59,620
Это будет просто мне вроде кричать
вещи, которые вы, и если я путаю вас,

23
00:00:59,620 --> 00:01:02,680
если я иду слишком быстро, дайте мне знать.

24
00:01:02,680 --> 00:01:05,200
Они просто различные данные
структуры, а также в рамках

25
00:01:05,200 --> 00:01:07,070
Вашей PSET для этого
Предстоящая неделя, вы будете

26
00:01:07,070 --> 00:01:10,340
будет предложено реализовать один из них,
возможно, два из them-- два из них

27
00:01:10,340 --> 00:01:12,319
в PSET.

28
00:01:12,319 --> 00:01:14,610
ОК, так что я просто хочу, чтобы
начать с некоторых объявлений.

29
00:01:14,610 --> 00:01:19,070
Мы пойдем по стеков и очередей в более
Глубина, чем то, что мы делали раньше викторины.

30
00:01:19,070 --> 00:01:20,990
Мы пойдем по связаны
список снова, снова,

31
00:01:20,990 --> 00:01:23,899
более подробно, чем то, что
мы имели до викторины.

32
00:01:23,899 --> 00:01:26,440
И тогда мы будем говорить о хеш
столы, деревья и пытается, которые

33
00:01:26,440 --> 00:01:28,890
все довольно необходимо для вашего PSET.

34
00:01:28,890 --> 00:01:32,925
И тогда мы будем идти над некоторыми
Полезные советы для pset5.

35
00:01:32,925 --> 00:01:37,360
>> Итак, викторина 0.

36
00:01:37,360 --> 00:01:41,090
Средняя был 58%.

37
00:01:41,090 --> 00:01:45,370
Это была очень низкой, и так вы, ребята, все
сделал очень, очень хорошо в соответствии

38
00:01:45,370 --> 00:01:46,510
с этим.

39
00:01:46,510 --> 00:01:49,970
>> Довольно много, правило, если вы
в стандартном отклонении от среднего

40
00:01:49,970 --> 00:01:52,990
особенно, так как мы находимся в менее
удобные раздел, вы совершенно нормально.

41
00:01:52,990 --> 00:01:54,120
Вы на верном пути.

42
00:01:54,120 --> 00:01:55,190
Жизнь хороша.

43
00:01:55,190 --> 00:01:58,952
>> Я знаю, что это страшно думать, что
Я получил, как 40% на этом конкурсе.

44
00:01:58,952 --> 00:02:00,160
Я собираюсь на провал этого класса.

45
00:02:00,160 --> 00:02:02,243
Я обещаю вам, вы не
происходит сбой класс.

46
00:02:02,243 --> 00:02:03,680
Ты совершенно нормально.

47
00:02:03,680 --> 00:02:06,850
>> Для тех из вас, кто получил более
среднее, впечатляет, впечатляет,

48
00:02:06,850 --> 00:02:08,780
как серьезно хорошо сделано.

49
00:02:08,780 --> 00:02:09,689
Я их со мной.

50
00:02:09,689 --> 00:02:11,730
Не стесняйтесь, получить их
В конце раздела.

51
00:02:11,730 --> 00:02:14,520
Позвольте мне знать, если у вас есть
вопросы, вопросы с ними.

52
00:02:14,520 --> 00:02:17,204
Если мы добавим ваш счет
так, дайте нам знать.

53
00:02:17,204 --> 00:02:21,240
>> Итак, pset5, это действительно
странно неделю Йельском университете в смысле

54
00:02:21,240 --> 00:02:24,240
что наша PSET связано
В среду в полдень в том числе

55
00:02:24,240 --> 00:02:27,317
конце дня, так что на самом деле
Теоретически из-за вторник в полдень.

56
00:02:27,317 --> 00:02:29,150
Наверное, никто не закончил
на вторник в полдень.

57
00:02:29,150 --> 00:02:30,830
Это совершенно нормально.

58
00:02:30,830 --> 00:02:33,700
Мы собираемся, чтобы иметь приемные часы
сегодня, а также в понедельник вечером.

59
00:02:33,700 --> 00:02:36,810
И все разделы этой неделе будет
фактически превратился в мастерских,

60
00:02:36,810 --> 00:02:38,800
так что не стесняйтесь поп
любое сечение хотите,

61
00:02:38,800 --> 00:02:42,810
и они будут своего рода мини-PSET
семинары для помощи в этом.

62
00:02:42,810 --> 00:02:45,620
Так как таковое, это единственный раздел,
где мы учебный материал.

63
00:02:45,620 --> 00:02:49,220
Все другие разделы будут фокусировки
исключительно на помощь для PSET.

64
00:02:49,220 --> 00:02:50,146
Да?

65
00:02:50,146 --> 00:02:52,000
>> АУДИТОРИЯ: Где рабочие часы?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Пэн: Часы
tonight-- о, хороший вопрос.

67
00:02:56,120 --> 00:03:00,580
Я думаю, что сегодня вечером офис часов
в Teal или общин.

68
00:03:00,580 --> 00:03:02,984
Если вы посмотрите онлайн CS50
и вы идете к офисной часов,

69
00:03:02,984 --> 00:03:05,650
должен быть график, что
говорит вам, где все из них.

70
00:03:05,650 --> 00:03:07,954
>> Я знаю, как сегодня
или завтра чирок,

71
00:03:07,954 --> 00:03:10,120
и я думаю, что мы, возможно,
фонда для другой ночи.

72
00:03:10,120 --> 00:03:11,020
Я не уверен.

73
00:03:11,020 --> 00:03:11,700
Хороший вопрос.

74
00:03:11,700 --> 00:03:14,430
Проверьте CS50.

75
00:03:14,430 --> 00:03:18,780
>> Прохладные, любые вопросы, касающиеся
График на следующий, как три дня?

76
00:03:18,780 --> 00:03:21,690
Я обещаю вам, ребята, как Давида
сказал, что это вершина холма.

77
00:03:21,690 --> 00:03:23,050
Вы, ребята, почти нет.

78
00:03:23,050 --> 00:03:24,644
Всего три более дней.

79
00:03:24,644 --> 00:03:26,310
Получить там, а затем мы все сойдет.

80
00:03:26,310 --> 00:03:28,114
Мы будем иметь хороший CS-бесплатный перерыв.

81
00:03:28,114 --> 00:03:28,780
Добро пожаловать назад.

82
00:03:28,780 --> 00:03:30,779
Мы в сети нырять
программирование и разработка,

83
00:03:30,779 --> 00:03:35,150
вещи, которые очень весело сравнению
в некоторых других psets.

84
00:03:35,150 --> 00:03:37,974
И это будет холод и
мы будем иметь много веселья.

85
00:03:37,974 --> 00:03:38,890
Мы будем иметь больше конфет.

86
00:03:38,890 --> 00:03:39,730
К сожалению для конфет.

87
00:03:39,730 --> 00:03:40,945
Я забыл конфеты.

88
00:03:40,945 --> 00:03:43,310
Это был грубый утром.

89
00:03:43,310 --> 00:03:46,340
Таким образом, вы, ребята, почти там,
и я очень горжусь вами, ребята.

90
00:03:46,340 --> 00:03:49,570
>> ОК, так что стеки.

91
00:03:49,570 --> 00:03:53,331
Кто любил вопрос о Джеке
и его одежда на викторине?

92
00:03:53,331 --> 00:03:53,830
Никто?

93
00:03:53,830 --> 00:03:56,500
ОК, это нормально.

94
00:03:56,500 --> 00:04:00,200
>> Так по существу, как вы можете
фото Джек, этот парень здесь,

95
00:04:00,200 --> 00:04:03,350
любит принимать одежду
из верхней части стека,

96
00:04:03,350 --> 00:04:05,750
и он кладет его обратно на
стек после того как он сделал.

97
00:04:05,750 --> 00:04:07,600
Так что в этом пути, он никогда
кажется, становится

98
00:04:07,600 --> 00:04:10,090
в нижней части
укладывают в его одежде.

99
00:04:10,090 --> 00:04:12,600
Так что это своего рода описывает
основная структура данных

100
00:04:12,600 --> 00:04:16,610
как стек реализован.

101
00:04:16,610 --> 00:04:20,060
>> По сути, думать о
стек, как любой стек объектов

102
00:04:20,060 --> 00:04:24,900
где вы положили вещи на вершине, и
то вы поп их сверху.

103
00:04:24,900 --> 00:04:28,600
Так ЛИФО является аббревиатурой нам нравится
чтобы use-- Последнее вошел, первым вышел.

104
00:04:28,600 --> 00:04:32,480
И так, чтобы продолжаться в верхней части
стек первым, который выходит.

105
00:04:32,480 --> 00:04:34,260
И так два члена
мы хотели бы связать

106
00:04:34,260 --> 00:04:36,190
с, что называется толчок и поп-музыки.

107
00:04:36,190 --> 00:04:39,790
Когда вы нажимаете на то
стек, и вы поп его обратно.

108
00:04:39,790 --> 00:04:43,422
>> И поэтому я думаю, это своего рода
абстрактное понятие для тех из вас,

109
00:04:43,422 --> 00:04:45,630
кто хочет видеть, как
практическая реализация

110
00:04:45,630 --> 00:04:46,740
в реальном мире.

111
00:04:46,740 --> 00:04:50,170
Как многие из вас написали эссе
может быть, как час, прежде чем он был из-за,

112
00:04:50,170 --> 00:04:54,510
и вы случайно удалили огромный
кусок ней, как случайно?

113
00:04:54,510 --> 00:04:58,560
И тогда то, что управление делаю
мы используем, чтобы положить его обратно?

114
00:04:58,560 --> 00:05:00,030
Control-Z, да?

115
00:05:00,030 --> 00:05:03,640
Control-Z, так что количество времени
что Control-Z спас мою жизнь,

116
00:05:03,640 --> 00:05:08,820
спас мою задницу, каждый раз,
который реализуется через стек.

117
00:05:08,820 --> 00:05:13,020
>> По существу вся информация
что на вашем документе Word,

118
00:05:13,020 --> 00:05:15,080
он получает толкнул и выскочил на волю.

119
00:05:15,080 --> 00:05:19,460
И так всякий раз, когда вам существенно
удалить что-нибудь, вы поп его обратно.

120
00:05:19,460 --> 00:05:22,820
И потом, если вам это нужно снова, вам
толкать его, что это то, что Ctrl + C делает.

121
00:05:22,820 --> 00:05:26,770
И так реальный мир функция
о том, как простой структуры данных

122
00:05:26,770 --> 00:05:28,690
может помочь с вашей повседневной жизни.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Таким образом, структура является способом, которым
мы на самом деле создать стек.

125
00:05:40,150 --> 00:05:44,720
Набираем определить-структуру, а затем
мы называем это стек на дне.

126
00:05:44,720 --> 00:05:47,440
И в стеке,
у нас есть два параметра

127
00:05:47,440 --> 00:05:51,580
что мы можем по существу манипулировать,
так что мы должны сЬаг звезды строк мощности.

128
00:05:51,580 --> 00:05:55,150
>> Все, что он делает
создает массив

129
00:05:55,150 --> 00:05:58,835
что мы можем хранить все, что вы хотите
которые мы можем определить его емкость.

130
00:05:58,835 --> 00:06:01,990
Емкость находится всего макс количество
предметы можно положить в этом массиве.

131
00:06:01,990 --> 00:06:05,660
Размер INT это счетчик, который держит
отслеживать, сколько элементов в настоящее время

132
00:06:05,660 --> 00:06:07,850
в стеке.

133
00:06:07,850 --> 00:06:11,860
Итак, мы можем отслеживать, А,
и, как большая фактическая стек,

134
00:06:11,860 --> 00:06:14,850
и, В, сколько этого стека
мы заполнили, потому что мы не хотим,

135
00:06:14,850 --> 00:06:18,800
переполнение над тем, что наши возможности.

136
00:06:18,800 --> 00:06:24,340
>> Так, например, этот прекрасный
Вопрос был на викторине.

137
00:06:24,340 --> 00:06:28,160
По сути, как мы толкать
на верх стека.

138
00:06:28,160 --> 00:06:28,830
Довольно просто.

139
00:06:28,830 --> 00:06:30,621
Если вы посмотрите на него,
мы будем идти через это.

140
00:06:30,621 --> 00:06:32,640
Если [неразборчиво] размер--
помните, когда вы

141
00:06:32,640 --> 00:06:35,300
хотите получить доступ к любой
Параметр в структуры,

142
00:06:35,300 --> 00:06:40,320
вы имя struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> В этом случае, с вне
имя нашего стека.

144
00:06:42,720 --> 00:06:46,230
Мы хотим, чтобы открыть размер
это, поэтому мы делаем s.size.

145
00:06:46,230 --> 00:06:50,280
Так что, пока размер не
равна мощности или до тех пор,

146
00:06:50,280 --> 00:06:52,940
а это меньше, чем емкость,
либо будет работать здесь.

147
00:06:52,940 --> 00:06:57,180
>> Вы хотите получить доступ к внутренней
вашего стека, так s.strings,

148
00:06:57,180 --> 00:07:00,790
и вы собираетесь положить, что новый номер
что вы хотите вставить в там.

149
00:07:00,790 --> 00:07:05,030
Давайте просто скажем, мы хотим, чтобы
вставьте Int N в стек,

150
00:07:05,030 --> 00:07:08,905
мы могли бы сделать s.strings,
кронштейны, s.size равен п.

151
00:07:08,905 --> 00:07:11,030
Потому что размер где мы
в настоящее время в стеке

152
00:07:11,030 --> 00:07:14,590
если мы собираемся, чтобы подтолкнуть
это, мы просто доступ

153
00:07:14,590 --> 00:07:17,370
там, где размер, тем
ток полнота стека,

154
00:07:17,370 --> 00:07:21,729
и мы нажимаем Int N на него.

155
00:07:21,729 --> 00:07:24,770
А потом мы хотим, чтобы убедиться, что
мы также увеличивая размер п,

156
00:07:24,770 --> 00:07:27,436
так что мы можем отслеживать мы в
добавили дополнительный предмет в стек.

157
00:07:27,436 --> 00:07:29,660
Теперь у нас есть больший размер.

158
00:07:29,660 --> 00:07:33,196
Значит ли это, здесь смысл
все, как логически это работает?

159
00:07:33,196 --> 00:07:34,160
Это был своего рода быстро.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
АУДИТОРИЯ: Можете ли вы перейти
в s.stringss.strings [s.size] еще раз?

162
00:07:42,160 --> 00:07:45,808
ANDI Пэн: Конечно, так, что делает
s.size настоящее время нам дает?

163
00:07:45,808 --> 00:07:47,440
АУДИТОРИЯ: Это текущий размер.

164
00:07:47,440 --> 00:07:50,890
ANDI Пэн: Ровно, поэтому
текущий индекс, что наш размер на,

165
00:07:50,890 --> 00:07:57,780
и поэтому мы хотим, чтобы поставить новый целое число
что мы хотим, чтобы вставить в s.size.

166
00:07:57,780 --> 00:07:58,760
Имеет ли это смысл?

167
00:07:58,760 --> 00:08:01,110
Потому s.strings, все, что
это является имя массива.

168
00:08:01,110 --> 00:08:03,510
Все это обращается к
Массив в нашей структуры,

169
00:08:03,510 --> 00:08:06,030
и поэтому, если мы хотим, чтобы
разместить п в этом индексе,

170
00:08:06,030 --> 00:08:09,651
мы можем просто открыть его
с помощью кронштейнов s.size.

171
00:08:09,651 --> 00:08:10,150
Круто.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Ладно, поп, я псевдокод его
для вас, ребята, но аналогичной концепции.

174
00:08:18,916 --> 00:08:19,790
Имеет ли это смысл?

175
00:08:19,790 --> 00:08:22,310
Если размер больше,
нуля, то вы

176
00:08:22,310 --> 00:08:25,350
знаю, что вы хотите взять что-то
из-за, если размер не

177
00:08:25,350 --> 00:08:27,620
больше нуля, то вы
не имеют ничего в стеке.

178
00:08:27,620 --> 00:08:29,840
>> Итак, вы хотите только выполнять
этот код, он может только

179
00:08:29,840 --> 00:08:32,320
поп, если есть что-то, чтобы поп-музыки.

180
00:08:32,320 --> 00:08:35,830
Таким образом, если размер больше
чем 0, то минус размер.

181
00:08:35,830 --> 00:08:40,020
Мы уменьшаем размер, а затем вернуться
все, что внутри него, потому что

182
00:08:40,020 --> 00:08:42,710
суя, мы хотим, чтобы
Доступ все, что хранится

183
00:08:42,710 --> 00:08:45,694
в индексе вершины стека.

184
00:08:45,694 --> 00:08:46,610
Все смысл?

185
00:08:46,610 --> 00:08:49,693
Если бы я сделал, вы, ребята написать это,
вы, ребята, будет иметь возможность записать его?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
ОК, вы, ребята, можете поиграть с ним.

188
00:08:53,570 --> 00:08:55,252
Не беспокойтесь, если вы не получите его.

189
00:08:55,252 --> 00:08:57,460
Мы не успели закодировать
это сегодня, потому что мы

190
00:08:57,460 --> 00:08:59,959
есть много этих структур
чтобы пройти, но по существу

191
00:08:59,959 --> 00:09:02,214
псевдокод, очень, очень похожи, чтобы подтолкнуть.

192
00:09:02,214 --> 00:09:03,380
Просто следуйте вдоль логики.

193
00:09:03,380 --> 00:09:06,092
Убедитесь, что вы обращаетесь все
особенности вашей структуры правильно.

194
00:09:06,092 --> 00:09:06,574
Да?

195
00:09:06,574 --> 00:09:09,282
>> АУДИТОРИЯ: Будут ли эти слайды и
Вся эта вещь будет до сегодня-иш?

196
00:09:09,282 --> 00:09:11,586
ANDI Пэн: Всегда, да.

197
00:09:11,586 --> 00:09:13,710
Я собираюсь попробовать поставить
это до, как через час после.

198
00:09:13,710 --> 00:09:16,626
Я электронной почте Давида, Дэвид будет пытаться
положить его, как через час после этого.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> ОК, так что потом мы перейдем в этот другой
прекрасный структура данных, называемая очередь.

201
00:09:25,470 --> 00:09:30,140
Как вы, ребята, можете посмотреть здесь, А
Очередь, для англичан среди нас,

202
00:09:30,140 --> 00:09:32,010
Все это представляет собой линию.

203
00:09:32,010 --> 00:09:34,680
Так вопреки тому, что
Вы думаете, что стек,

204
00:09:34,680 --> 00:09:37,750
очередь именно то, что
логически вы думаете.

205
00:09:37,750 --> 00:09:41,914
Он проводится по правилам FIFO,
который является первым вошел, первым вышел.

206
00:09:41,914 --> 00:09:43,705
Если вы первый
один в линии, вы

207
00:09:43,705 --> 00:09:46,230
первое, что
выходит из линии.

208
00:09:46,230 --> 00:09:49,680
>> Итак, что мы хотели бы назвать это
в освобождении пакета из очереди и enqueueing.

209
00:09:49,680 --> 00:09:52,380
Если мы хотим что-то добавить
в нашей очереди, мы в очередь.

210
00:09:52,380 --> 00:09:55,690
Если мы хотим, чтобы из очереди, или взять
то прочь, мы из очереди.

211
00:09:55,690 --> 00:10:03,350
>> Так же смысл, что мы вроде
создания элементов фиксированного размера, что мы

212
00:10:03,350 --> 00:10:06,500
может хранить определенное
вещи, но мы можем также

213
00:10:06,500 --> 00:10:10,100
изменить, где мы размещения
Параметры внутри них

214
00:10:10,100 --> 00:10:13,140
на основе того, какой тип
Функциональность мы хотим.

215
00:10:13,140 --> 00:10:16,700
Так стеков, мы хотели последний
Один из них, N, чтобы быть первым из.

216
00:10:16,700 --> 00:10:19,800
Очередь мы хотим первое
и быть первое, что.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Так в структуры типа
определить, как вы можете видеть,

219
00:10:26,710 --> 00:10:29,470
это немного отличается
от того, что стэк

220
00:10:29,470 --> 00:10:33,120
потому что мы не только должны иметь
трек, где в настоящее время размер,

221
00:10:33,120 --> 00:10:37,420
мы также хотим, чтобы отслеживать голову
как и где мы в настоящее время.

222
00:10:37,420 --> 00:10:39,580
Так что я думаю, что это проще
если я рисую это.

223
00:10:39,580 --> 00:10:53,270
Итак, давайте представим, что у нас есть очередь,
так скажем, голова прямо здесь.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Глава линии, давайте
просто сказать, что это в настоящее время,

226
00:10:58,310 --> 00:11:01,809
и мы хотим, чтобы вставить
то в очереди.

227
00:11:01,809 --> 00:11:04,350
Я собираюсь позвонить размер существенно
это то же самое, как хвост,

228
00:11:04,350 --> 00:11:06,314
конец, где ваш очереди.

229
00:11:06,314 --> 00:11:07,730
Давайте просто скажем, размер прямо здесь.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Так как же реально
вставить что-то в очереди?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Что индекс мы хотим разместить
где мы хотим вставить в.

234
00:11:24,130 --> 00:11:29,320
Если это начало вашей
очереди, и это в конце его

235
00:11:29,320 --> 00:11:31,860
или размер его, где мы
Чтобы добавить следующий объект?

236
00:11:31,860 --> 00:11:32,920
>> АУДИТОРИЯ: [неразборчиво]

237
00:11:32,920 --> 00:11:35,920
ANDI Пэн: Ровно, вы хотите, чтобы добавить
это в зависимости от вы написали это.

238
00:11:35,920 --> 00:11:37,840
Либо это пустой или пустой.

239
00:11:37,840 --> 00:11:42,630
Итак, вы хотите, чтобы добавить его, вероятно,
здесь, потому что, если размер is--

240
00:11:42,630 --> 00:11:50,540
если они все полны, вы хотите
чтобы добавить его прямо здесь, прямо?

241
00:11:50,540 --> 00:11:57,150
>> И так вот, в то время как очень, очень
просто, не совсем всегда правильно

242
00:11:57,150 --> 00:12:00,690
потому что основное различие
между очереди и стека

243
00:12:00,690 --> 00:12:04,350
является то, что очередь может
на самом деле манипулировать

244
00:12:04,350 --> 00:12:06,980
так что изменения главные
в зависимости от того, где вы хотите

245
00:12:06,980 --> 00:12:08,650
начало вашего кия, чтобы начать.

246
00:12:08,650 --> 00:12:11,900
И в результате, твой хвост
Также изменится.

247
00:12:11,900 --> 00:12:14,770
И так взглянуть на
этот код прямо сейчас.

248
00:12:14,770 --> 00:12:18,620
Как вы, ребята, было также предложено
написать на викторине, поставить в очередь.

249
00:12:18,620 --> 00:12:22,580
Может быть, мы поговорим через почему
ответ был, что это было.

250
00:12:22,580 --> 00:12:26,790
>> Я не мог соответствовать этой линии на один,
но по сути это кусок кода

251
00:12:26,790 --> 00:12:29,030
должны находиться на одной линии.

252
00:12:29,030 --> 00:12:30,140
Проведите как 30 секунд.

253
00:12:30,140 --> 00:12:33,000
Взгляните, и понять, почему
это путь, что это.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Очень, очень похожи структура, очень, очень
Подобная структура, как и предыдущий

256
00:12:55,420 --> 00:12:58,090
стек для, возможно, за исключением того,
одной строки кода.

257
00:12:58,090 --> 00:13:01,190
И, что одной строки кода
определяет функциональность.

258
00:13:01,190 --> 00:13:03,900
И это действительно отличает
очередь из стопки.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Кто-нибудь хочет принять удар
на объяснение, почему вы

261
00:13:22,010 --> 00:13:24,980
получил эту сложную вещь в здесь?

262
00:13:24,980 --> 00:13:27,845
Мы видим возвращение нашего
замечательный друг модуль.

263
00:13:27,845 --> 00:13:31,020
Как вы, ребята, скоро придет
признать в программировании,

264
00:13:31,020 --> 00:13:34,910
почти в любое время нужно что-то
обернуть вокруг ничего,

265
00:13:34,910 --> 00:13:36,850
модуль будет путь, чтобы сделать это.

266
00:13:36,850 --> 00:13:40,510
Так, зная, что, кто-нибудь хочет
попробовать объясняя, что строки кода?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Да, все ответы
принимаются и одобряются.

269
00:13:47,507 --> 00:13:48,840
АУДИТОРИЯ: Вы говорите мне?

270
00:13:48,840 --> 00:13:49,506
ANDI Пэн: Да.

271
00:13:49,506 --> 00:13:56,200
АУДИТОРИЯ: О, нет извините.

272
00:13:56,200 --> 00:14:00,250
ANDI Пэн: ОК, так что давайте
ходить через этот код.

273
00:14:00,250 --> 00:14:03,642
Поэтому, когда вы пытаетесь
что-то добавить на очереди,

274
00:14:03,642 --> 00:14:08,510
в прекрасном случае, что глава случается
чтобы быть здесь, это очень легко для нас

275
00:14:08,510 --> 00:14:10,960
просто идти до конца
вставить что-то, верно?

276
00:14:10,960 --> 00:14:14,690
Но вся суть в очереди
что глава может на самом деле динамически

277
00:14:14,690 --> 00:14:17,280
меняться в зависимости от где
хотите начало нашего ц быть,

278
00:14:17,280 --> 00:14:19,880
и, как таковой, хвост
Также изменится.

279
00:14:19,880 --> 00:14:31,100
>> И так представить, что это не было
очереди, а это было очереди.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Скажем, голова прямо здесь.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Скажем, наша очередь посмотрел, как это.

284
00:14:56,980 --> 00:15:00,190
Если бы мы хотели, чтобы переложить, где
начало линии,

285
00:15:00,190 --> 00:15:03,400
давайте говорить, что мы перешли голову
таким образом, и здесь размеры.

286
00:15:03,400 --> 00:15:07,100
>> Теперь мы хотим, чтобы добавить что-то
эта очередь, но, как вы, ребята, можете видеть,

287
00:15:07,100 --> 00:15:11,150
это не так просто, как просто
добавить все, что после размера

288
00:15:11,150 --> 00:15:13,630
потому что тогда мы бежим из
Границы нашего фактического массива.

289
00:15:13,630 --> 00:15:16,190
Где мы хотим, чтобы действительно добавить здесь.

290
00:15:16,190 --> 00:15:18,610
Это красота очереди
является то, что для нас, визуально

291
00:15:18,610 --> 00:15:22,380
Похоже, что линия идет, как это,
но при хранении в структуре данных,

292
00:15:22,380 --> 00:15:29,370
они дают его в качестве как цикл.

293
00:15:29,370 --> 00:15:32,360
Это своего рода обтекает
к фронту таким же образом

294
00:15:32,360 --> 00:15:34,780
что линия может также обернуть
вокруг в зависимости от везде, где вас

295
00:15:34,780 --> 00:15:36,279
хочу начале строки, чтобы быть.

296
00:15:36,279 --> 00:15:38,630
И поэтому, если мы берем
искать здесь, давайте

297
00:15:38,630 --> 00:15:40,880
что мы хотим, чтобы создать
Функция называется Добавляет.

298
00:15:40,880 --> 00:15:43,980
Мы хотели, чтобы добавить Int N в этой д.

299
00:15:43,980 --> 00:15:49,250
Если q.size q-- мы называем это наши данные
structure-- если наша queue.size не

300
00:15:49,250 --> 00:15:52,520
равно мощности или если
это меньше, чем емкость,

301
00:15:52,520 --> 00:15:55,120
q.strings это массив в нашей ц.

302
00:15:55,120 --> 00:15:58,380
Мы собираемся установить
что равно q.heads,

303
00:15:58,380 --> 00:16:02,730
что прямо здесь, плюс q.size
Модуль емкостью, которая

304
00:16:02,730 --> 00:16:04,290
обернуть нас здесь.

305
00:16:04,290 --> 00:16:08,040
>> Таким образом, в этом примере, индекс
главы 1, верно?

306
00:16:08,040 --> 00:16:11,480
Индекс размера 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Таким образом, мы можем сделать 1 плюс 4 модуля
нашей способности, которая 5.

308
00:16:19,500 --> 00:16:20,920
Что это нам дает?

309
00:16:20,920 --> 00:16:23,270
Что такое индекс, который
выходит из этого?

310
00:16:23,270 --> 00:16:24,080
>> АУДИТОРИЯ: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Пэн: 0,
бывает здесь,

312
00:16:27,870 --> 00:16:30,640
и поэтому мы хотим, чтобы иметь возможность
вставить в прямо здесь.

313
00:16:30,640 --> 00:16:34,730
И так это уравнение здесь вид
просто работает с любыми номерами

314
00:16:34,730 --> 00:16:36,750
в зависимости от того, где ваш
голова и ваш размер есть.

315
00:16:36,750 --> 00:16:38,541
Если вы знаете, что те,
вещи, вы знаете,

316
00:16:38,541 --> 00:16:43,170
именно там, где вы хотите вставить
все, что после очереди.

317
00:16:43,170 --> 00:16:44,640
Имеет ли это смысл для всех?

318
00:16:44,640 --> 00:16:48,560
>> Я знаю, вроде мозга
тизер особенно, так как это

319
00:16:48,560 --> 00:16:50,512
пришли в после вашего теста.

320
00:16:50,512 --> 00:16:52,220
Но, надеюсь, все
Теперь можно понять

321
00:16:52,220 --> 00:16:57,800
Поэтому это решение или это
функция так, что это такое.

322
00:16:57,800 --> 00:16:59,840
Любой немного неясно по этому поводу?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ХОРОШО.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> И вот теперь, если вы
хотел из очереди, это

327
00:17:09,970 --> 00:17:15,240
где наша голова будет переход
потому что, если мы должны были из очереди,

328
00:17:15,240 --> 00:17:17,030
мы не снять конец д.

329
00:17:17,030 --> 00:17:19,130
Мы хотим, чтобы с головы, верно?

330
00:17:19,130 --> 00:17:24,260
Так что в итоге, голова изменится,
и поэтому, когда вы в очередь,

331
00:17:24,260 --> 00:17:26,800
Вы должны следить за
где ваша голова и ваш размер

332
00:17:26,800 --> 00:17:29,450
должны иметь возможность вставить
в правильное положение.

333
00:17:29,450 --> 00:17:32,740
>> И поэтому, когда вы из очереди,
Я также псевдокод его.

334
00:17:32,740 --> 00:17:35,480
Не стесняйтесь, если вы хотите
попытаться кодирования это.

335
00:17:35,480 --> 00:17:36,980
Вы хотите, чтобы переместить голову, верно?

336
00:17:36,980 --> 00:17:39,320
Если бы я хотел, чтобы из очереди, я
будет двигаться голову над.

337
00:17:39,320 --> 00:17:40,800
Это будет голова.

338
00:17:40,800 --> 00:17:45,617
>> И наша текущий размер будет
вычесть, потому что мы больше не

339
00:17:45,617 --> 00:17:46,950
четыре элемента в матрице.

340
00:17:46,950 --> 00:17:51,370
У нас есть только три, а потом мы хотим
вернуться все было хранить внутри

341
00:17:51,370 --> 00:17:56,260
главы, потому что мы хотим, чтобы это
Значение так, очень похожа на стек.

342
00:17:56,260 --> 00:17:58,010
Просто вы принимаете
из другого места,

343
00:17:58,010 --> 00:18:01,770
и у вас есть, чтобы передать свою указатель
в другом месте в качестве результата.

344
00:18:01,770 --> 00:18:03,890
Логично, каждый следовать?

345
00:18:03,890 --> 00:18:05,690
Отлично.

346
00:18:05,690 --> 00:18:10,156
>> ОК, так что мы собираемся немного поговорить
более подробно о связанных списков

347
00:18:10,156 --> 00:18:13,280
потому что они очень, очень ценный
для вас в ходе этой неделе

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Связанные списки, как вы, ребята,
помню, они все

350
00:18:17,130 --> 00:18:22,570
являются узлами, которые узлы уверен
значения как значения и указатель

351
00:18:22,570 --> 00:18:26,290
которые связаны друг с другом
по этим указателям.

352
00:18:26,290 --> 00:18:29,880
И поэтому от того, как структура
мы создаем узел здесь мы

353
00:18:29,880 --> 00:18:33,569
есть Int N, который является то, что
значение в магазине или струнного п

354
00:18:33,569 --> 00:18:35,610
или что вы хотите, чтобы
это называют, полукокс звезда н.

355
00:18:35,610 --> 00:18:41,482
Структура, узел звезда, которая является указателем
что вы хотите, чтобы в каждом узле,

356
00:18:41,482 --> 00:18:43,690
Вы будете иметь, что
точка указатель к следующему.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Вы будете иметь голову
из связанного списка, что это

359
00:18:50,040 --> 00:18:53,140
собирается указывают на остальной
значения так далее, и так далее

360
00:18:53,140 --> 00:18:55,290
пока вы в конечном итоге не дойдете до конца.

361
00:18:55,290 --> 00:18:58,040
И это последний узел просто
происходит, чтобы не иметь указатель.

362
00:18:58,040 --> 00:18:59,952
Это будет указывать на
NULL, и что, когда

363
00:18:59,952 --> 00:19:01,910
вы знаете, что ударил
конец вашей связанного списка

364
00:19:01,910 --> 00:19:04,076
когда ваш последний указатель
не указывает ни на что.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Так что мы собираемся идти немного больше в
Глубина о том, как одно, возможно,

367
00:19:10,990 --> 00:19:12,400
поиск связанный список.

368
00:19:12,400 --> 00:19:15,460
Помните, что некоторые из
Недостатками связанных списков

369
00:19:15,460 --> 00:19:19,340
стихи массив относительно поисков.

370
00:19:19,340 --> 00:19:22,565
Массив можно бинарный поиск, но
почему вы не можете сделать это в связанном списке?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> АУДИТОРИЯ: Потому что они все связаны,
но вы совершенно не знаю, где

373
00:19:30,320 --> 00:19:31,330
[Неразборчиво].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Пэн: Да, именно так помню
что блеск массива

375
00:19:34,600 --> 00:19:37,190
было то, что у нас было
оперативное запоминающее устройство, где

376
00:19:37,190 --> 00:19:41,580
если бы я хотел значение из индекса
шесть, я мог просто сказать индекс шесть,

377
00:19:41,580 --> 00:19:42,407
дайте мне это значение.

378
00:19:42,407 --> 00:19:45,240
И это потому, что массивы сортируются
в непрерывном пространстве памяти

379
00:19:45,240 --> 00:19:48,020
в одном месте, в то время как
вид связанных списков

380
00:19:48,020 --> 00:19:52,820
случайно перемежаются всему,
и единственный способ вы можете найти один

381
00:19:52,820 --> 00:19:56,890
через указатель, который говорит вам,
адрес, где, что в следующем узел.

382
00:19:56,890 --> 00:20:00,290
>> И так, в результате, единственный способ
искать в связанном списке

383
00:20:00,290 --> 00:20:01,560
это линейный поиск.

384
00:20:01,560 --> 00:20:05,890
Потому что я точно не знаю, где
12-й значение в связанном списке,

385
00:20:05,890 --> 00:20:08,780
Я должен пройти полноту
этого связанный список одного

386
00:20:08,780 --> 00:20:12,450
один от головы до первого узла,
ко второму узлу, третьему узлу,

387
00:20:12,450 --> 00:20:17,690
весь путь вниз, пока я, наконец, не получают
где этот узел, я смотрю на это.

388
00:20:17,690 --> 00:20:22,110
И поэтому в этом смысле, поиск
на связанный список всегда п.

389
00:20:22,110 --> 00:20:23,040
Это всегда п.

390
00:20:23,040 --> 00:20:25,690
Это всегда в линейном времени.

391
00:20:25,690 --> 00:20:28,470
>> И поэтому код, в котором
мы реализуем это, и это

392
00:20:28,470 --> 00:20:32,620
немного нового для вас, ребята, так как вы
Ребята на самом деле не говорил о или когда-либо

393
00:20:32,620 --> 00:20:35,000
просмотрено указатели в том, как
поиск с помощью указателей,

394
00:20:35,000 --> 00:20:37,670
таким образом, мы будем идти через
это очень, очень медленно.

395
00:20:37,670 --> 00:20:40,200
Так поиск логический, право,
давайте представим, что мы хотим

396
00:20:40,200 --> 00:20:42,820
создать функцию с именем
Поиск, который возвращает истинное

397
00:20:42,820 --> 00:20:46,820
если вы нашли значение внутри связанный
список, и возвращает ложное в противном случае.

398
00:20:46,820 --> 00:20:50,030
Узел звезда список
В настоящее время только указатель

399
00:20:50,030 --> 00:20:52,960
к первому пункту в вашем связанного списка.

400
00:20:52,960 --> 00:20:56,700
INT п значение, что вы
поиск в этом списке.

401
00:20:56,700 --> 00:20:58,770
>> Так узел звезда указатель равен список.

402
00:20:58,770 --> 00:21:00,970
Это означает, что мы устанавливаем
и создание указатель

403
00:21:00,970 --> 00:21:03,592
к этому первому узлу внутри списка.

404
00:21:03,592 --> 00:21:04,300
Все со мной?

405
00:21:04,300 --> 00:21:06,530
Так что, если мы должны были пойти
сюда, я бы

406
00:21:06,530 --> 00:21:13,850
инициализации указатель, который указывает на
глава независимо, что список.

407
00:21:13,850 --> 00:21:18,600
>> И то, как только вы получите здесь,
в то время как указатель не равен нулю,

408
00:21:18,600 --> 00:21:22,160
так что это петля, в которой мы
будет впоследствии прохождения

409
00:21:22,160 --> 00:21:25,940
остальные нашем списке, потому что то, что
происходит, когда указатель равен NULL?

410
00:21:25,940 --> 00:21:27,550
Мы знаем, что have--

411
00:21:27,550 --> 00:21:28,450
>> АУДИТОРИЯ: [неразборчиво]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Пэн: Ровно, поэтому мы знаем, что
мы достигли конца списка, верно?

413
00:21:31,491 --> 00:21:34,470
Если вы идете сюда, каждый узел
должен быть направлен на другой узел

414
00:21:34,470 --> 00:21:36,550
и так далее и тому подобное
пока вы не нажмете в конечном итоге

415
00:21:36,550 --> 00:21:41,589
хвост вашего связанного списка,
который имеет указатель, который просто

416
00:21:41,589 --> 00:21:43,130
не указывают, чем в любом другом нет.

417
00:21:43,130 --> 00:21:47,510
И так вы знаете, что в основном
Ваш список есть еще до

418
00:21:47,510 --> 00:21:50,900
до указателя не делает не равны
нуль, потому что когда-то он равен нулю,

419
00:21:50,900 --> 00:21:53,310
Вы знаете, что нет больше материала.

420
00:21:53,310 --> 00:21:56,930
>> Так что это петля, в которой мы
будет иметь реальную поиска.

421
00:21:56,930 --> 00:22:01,690
И если pointer-- вы видите
что вид функции стрелка там?

422
00:22:01,690 --> 00:22:06,930
Так что, если указатель указывает п, если
указатель на п равен равен п,

423
00:22:06,930 --> 00:22:09,180
так, что означает, что если
указатель, что вы

424
00:22:09,180 --> 00:22:13,420
поиске на конце каждого
узел фактически равно значению

425
00:22:13,420 --> 00:22:15,990
Вы ищете, то
Вы хотите, чтобы вернуться правда.

426
00:22:15,990 --> 00:22:19,280
Так в основном, если вы находитесь на узле, который
имеет значение, что вы ищете,

427
00:22:19,280 --> 00:22:23,550
Вы знаете, что вы были
в состоянии успешно искать.

428
00:22:23,550 --> 00:22:27,150
>> В противном случае, вы хотите установить
указатель на следующий узел.

429
00:22:27,150 --> 00:22:28,850
Это то, что эта линия здесь делает.

430
00:22:28,850 --> 00:22:31,750
Указатель равна указатель рядом.

431
00:22:31,750 --> 00:22:33,360
Все видеть, как это работает?

432
00:22:33,360 --> 00:22:36,580
>> И по существу, вы собираетесь просто
пройти полноту списка,

433
00:22:36,580 --> 00:22:41,920
сброс указатель каждый раз до
Вы в конечном счете попал в конце списка.

434
00:22:41,920 --> 00:22:45,030
И вы не знаете, что есть не
больше узлов для поиска по,

435
00:22:45,030 --> 00:22:47,999
а затем вы можете вернуться ложным
потому что вы знаете, что, ну, хорошо,

436
00:22:47,999 --> 00:22:50,540
если я был в состоянии искать
через полностью списка.

437
00:22:50,540 --> 00:22:54,530
Если в этом примере, если бы я хотел
искать значения 10,

438
00:22:54,530 --> 00:22:57,250
и я начинаю в голове, и
Я ищу всю дорогу вниз,

439
00:22:57,250 --> 00:23:00,550
и я в конце концов получил на это, что
указатель, который указывает на NULL,

440
00:23:00,550 --> 00:23:04,415
Я знаю, что, дерьмо, я думаю, 10 не находится в
этот список, потому что я не мог найти его.

441
00:23:04,415 --> 00:23:06,520
И я в конце списка.

442
00:23:06,520 --> 00:23:11,040
И в этом случае вы знаете,
Я собираюсь вернуться ложным.

443
00:23:11,040 --> 00:23:12,900
>> Пусть это замочить в для немного.

444
00:23:12,900 --> 00:23:17,350
Это будет довольно
важно для вашего PSET.

445
00:23:17,350 --> 00:23:21,140
Логика очень проста, возможно
синтаксически только его реализации.

446
00:23:21,140 --> 00:23:23,365
Вы, ребята, хотите, чтобы
Убедитесь, что вы понимаете.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Круто.

449
00:23:27,650 --> 00:23:32,560
>> Итак, как мы бы
вставки узлов, право,

450
00:23:32,560 --> 00:23:35,380
в списке, потому что помню,
каковы то, что преимущества

451
00:23:35,380 --> 00:23:39,230
иметь связанный список против
массив с точки зрения хранения?

452
00:23:39,230 --> 00:23:41,110
>> АУДИТОРИЯ: Это динамичный,
так легче, целью которых

453
00:23:41,110 --> 00:23:43,180
>> ANDI Пэн: Ровно,
так что это динамичный, который

454
00:23:43,180 --> 00:23:46,880
означает, что он может расширяться и сжиматься
в зависимости от потребностей пользователя.

455
00:23:46,880 --> 00:23:56,570
И так, в этом смысле, мы не должны
тратить ненужного память, потому что я

456
00:23:56,570 --> 00:24:00,850
если я не знаю, сколько я хочу значения
в магазине, это не имеет смысла для меня

457
00:24:00,850 --> 00:24:04,310
создать массив, потому что
если я хочу, чтобы хранить 10 значений

458
00:24:04,310 --> 00:24:08,380
и создать массив 1000, это
много впустую память, выделено.

459
00:24:08,380 --> 00:24:11,180
Вот почему мы хотим использовать связанный
Список, чтобы иметь возможность динамически

460
00:24:11,180 --> 00:24:13,860
изменить или уменьшить размер нашей.

461
00:24:13,860 --> 00:24:17,040
>> И так, что делает вставку
немного более сложным.

462
00:24:17,040 --> 00:24:20,810
Поскольку мы не можем произвольно обращаться к элементам
так, что мы массива.

463
00:24:20,810 --> 00:24:24,270
Если я хочу, чтобы вставить элемент
в седьмой индекса,

464
00:24:24,270 --> 00:24:26,930
Я просто не могу вставить
в седьмой индекса.

465
00:24:26,930 --> 00:24:30,020
На связанном списке, это не
довольно легко работать, как,

466
00:24:30,020 --> 00:24:34,947
и поэтому, если мы хотели, чтобы вставить
один здесь, в связанном списке,

467
00:24:34,947 --> 00:24:36,280
визуально, это очень легко увидеть.

468
00:24:36,280 --> 00:24:39,363
Мы просто хотим, чтобы вставить его прямо там,
в самом начале списка,

469
00:24:39,363 --> 00:24:40,840
сразу после головы.

470
00:24:40,840 --> 00:24:44,579
>> Но то, каким образом мы должны переназначить
указатели это немного запутанным

471
00:24:44,579 --> 00:24:47,620
или, по логике, это имеет смысл, но
Вы хотите, чтобы убедиться, что у вас есть

472
00:24:47,620 --> 00:24:50,250
полностью вниз, потому что
последнее, что вы хотите

473
00:24:50,250 --> 00:24:52,990
это переназначить указки
так, что мы здесь делаем.

474
00:24:52,990 --> 00:24:58,170
Если вы разыменовать
указатель с головы до 1,

475
00:24:58,170 --> 00:25:01,086
то все вдруг
остальная часть вашего связанного списка

476
00:25:01,086 --> 00:25:04,680
теряется, потому что у вас есть на самом деле не
создано временное ничего.

477
00:25:04,680 --> 00:25:06,220
Вот указал на 2.

478
00:25:06,220 --> 00:25:10,080
При передаче указателя, то
Остальные свой список полностью потеряны.

479
00:25:10,080 --> 00:25:13,310
Итак, вы хотите быть
очень, очень осторожны

480
00:25:13,310 --> 00:25:17,010
сначала назначить
Указатель с какой вам

481
00:25:17,010 --> 00:25:20,150
вставить в там, где
Вы хотите, и тогда вы

482
00:25:20,150 --> 00:25:22,710
может разыменовать остальной список.

483
00:25:22,710 --> 00:25:25,250
>> Таким образом, это относится и к везде, где
Вы пытаетесь вставить в.

484
00:25:25,250 --> 00:25:27,520
Если вы хотите, чтобы вставить на
голова, если вы хотите, чтобы ответить здесь,

485
00:25:27,520 --> 00:25:29,455
если вы хотите вставить в
конец, ну, конец я

486
00:25:29,455 --> 00:25:30,910
думаю, вы бы просто
нет указатель, но вы

487
00:25:30,910 --> 00:25:33,830
хотите, чтобы убедиться, что вы не
потерять остальные вашего списка.

488
00:25:33,830 --> 00:25:36,640
Вы всегда хотите, чтобы убедиться,
Ваш новый узел указывая

489
00:25:36,640 --> 00:25:39,330
к все, что вы
вставить в,

490
00:25:39,330 --> 00:25:42,170
а затем вы можете добавить цепочку дальше.

491
00:25:42,170 --> 00:25:43,330
Все ясно?

492
00:25:43,330 --> 00:25:45,427
>> Это будет
один из реальных проблем.

493
00:25:45,427 --> 00:25:48,010
Один из самых главных вопросов
Вы будете иметь на вашем PSET

494
00:25:48,010 --> 00:25:51,340
является то, что вы собираетесь, чтобы попытаться создать
связанный список и добавить вещи,

495
00:25:51,340 --> 00:25:53,340
но потом просто потерять
остальная часть вашего связанного списка.

496
00:25:53,340 --> 00:25:54,900
И вы будете, как я
Не знаю, почему это происходит?

497
00:25:54,900 --> 00:25:58,040
И это боль, чтобы пройти через
и искать все ваши указатели.

498
00:25:58,040 --> 00:26:02,100
>> И я гарантирую вам на этом PSET,
писать и рисовать эти узлы из

499
00:26:02,100 --> 00:26:03,344
будет очень, очень полезно.

500
00:26:03,344 --> 00:26:06,010
Таким образом, вы можете полностью отслеживать
где все ваши указатели,

501
00:26:06,010 --> 00:26:08,540
что происходит не так,
где все ваши узлы,

502
00:26:08,540 --> 00:26:12,660
то, что вы должны сделать, чтобы получить доступ к или
вставить или удалить или любого из них.

503
00:26:12,660 --> 00:26:14,550
Все хорошо с этим?

504
00:26:14,550 --> 00:26:15,050
Круто.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Так что, если мы хотели посмотреть на код?

507
00:26:22,600 --> 00:26:24,470
О, я не знаю, если мы
можно увидеть the-- OK, так

508
00:26:24,470 --> 00:26:27,940
в верхней все это является функцией
имени вставка, где мы хотим

509
00:26:27,940 --> 00:26:31,365
вставить Int N в связанном списке.

510
00:26:31,365 --> 00:26:32,740
Мы собираемся пройти через это.

511
00:26:32,740 --> 00:26:34,770
Это много кода, много нового синтаксиса.

512
00:26:34,770 --> 00:26:36,220
Мы в порядке.

513
00:26:36,220 --> 00:26:39,120
>> Так на вершине, когда
мы хотим, чтобы создать что-нибудь

514
00:26:39,120 --> 00:26:42,380
что нам нужно сделать, особенно если вы
Хотите его нельзя хранить в стеке

515
00:26:42,380 --> 00:26:43,920
но в куче?

516
00:26:43,920 --> 00:26:45,460
Мы идем в таНос, верно?

517
00:26:45,460 --> 00:26:48,240
Итак, мы собираемся создать указатель.

518
00:26:48,240 --> 00:26:52,074
Узел, указатель, новые равно
таНос размер узла

519
00:26:52,074 --> 00:26:53,740
потому что мы хотим, что узел будет создан.

520
00:26:53,740 --> 00:26:56,720
Мы хотим, чтобы количество
памяти, что узел занимает

521
00:26:56,720 --> 00:26:59,300
чтобы быть отведено для
Создание нового узла.

522
00:26:59,300 --> 00:27:02,270
>> А потом мы собираемся, чтобы проверить,
увидеть, если новые равно равна нулю.

523
00:27:02,270 --> 00:27:03,370
Помните, что мы говорили?

524
00:27:03,370 --> 00:27:06,470
Что бы вы ни таНос,
Что необходимо всегда делать?

525
00:27:06,470 --> 00:27:09,490
Вы всегда должны проверить, чтобы увидеть
или нет, что это NULL.

526
00:27:09,490 --> 00:27:13,620
>> Например, если ваша операционная
система была полностью заполнена,

527
00:27:13,620 --> 00:27:17,060
если вы не имели больше памяти на
все, и вы пытаетесь таНос,

528
00:27:17,060 --> 00:27:18,410
это вернется NULL для вас.

529
00:27:18,410 --> 00:27:21,094
И поэтому, если вы пытаетесь использовать его
когда он был направлен на нуль,

530
00:27:21,094 --> 00:27:23,260
вы не собираетесь, чтобы в состоянии
для доступа к этой информации.

531
00:27:23,260 --> 00:27:27,010
И так, как, например, мы хотели сделать
Убедитесь, что всякий раз, когда вы mallocing,

532
00:27:27,010 --> 00:27:30,500
Вы всегда проверять, если
что память дано вам является недействительным.

533
00:27:30,500 --> 00:27:33,670
А если это не так, то мы можем двигаться
на с остальной частью нашего кода.

534
00:27:33,670 --> 00:27:36,140
>> Итак, мы собираемся, чтобы
инициализировать новый узел.

535
00:27:36,140 --> 00:27:39,050
Мы собираемся сделать новый п равен п.

536
00:27:39,050 --> 00:27:42,390
И тогда мы будем делать
установить новый указатель на новый

537
00:27:42,390 --> 00:27:46,900
в нуль, потому что сейчас мы не
хочу что-нибудь для того, чтобы указать на.

538
00:27:46,900 --> 00:27:48,755
Мы не имеем ни малейшего понятия где
он собирается поставить вас,

539
00:27:48,755 --> 00:27:50,630
а затем, если мы хотим, чтобы
вставьте его в голове,

540
00:27:50,630 --> 00:27:53,820
то мы можем передать
указатель на голову.

541
00:27:53,820 --> 00:27:58,530
Все следовать логике ли
где, что происходит?

542
00:27:58,530 --> 00:28:02,502
>> Все, что мы делаем, создавая новый
узел, установив указатель на NULL,

543
00:28:02,502 --> 00:28:04,210
а затем переназначение
это в голове, если мы

544
00:28:04,210 --> 00:28:06,320
знаю, что мы хотим, чтобы вставить его в голову.

545
00:28:06,320 --> 00:28:09,420
А потом голова будет
указывают на то нового узла.

546
00:28:09,420 --> 00:28:11,060
Все в порядке с этим?

547
00:28:11,060 --> 00:28:12,380
>> Так что это двухступенчатый процесс.

548
00:28:12,380 --> 00:28:14,760
Вы должны сначала назначить
все, что вы создаёте.

549
00:28:14,760 --> 00:28:18,260
Установлено, что указатель на
справка, а затем вам

550
00:28:18,260 --> 00:28:21,400
может рода разыменования
первый указатель

551
00:28:21,400 --> 00:28:22,972
и указать его к новому узлу.

552
00:28:22,972 --> 00:28:25,680
Где вы хотите, чтобы вставить его,
что логика собирается провести верно.

553
00:28:25,680 --> 00:28:27,530
>> Это вроде как присвоение
временные переменные.

554
00:28:27,530 --> 00:28:28,700
Помните, у вас есть
чтобы убедиться, что вас

555
00:28:28,700 --> 00:28:30,346
не терять, если вы подкачки.

556
00:28:30,346 --> 00:28:33,470
Вы хотите, чтобы убедиться, что у вас есть
временная переменная, что вид сохраняет

557
00:28:33,470 --> 00:28:35,620
трек где этой вещи
хранится, так что вы

558
00:28:35,620 --> 00:28:41,190
не теряют любое значение в ходе
из, как возиться с ним.

559
00:28:41,190 --> 00:28:42,710
>> ОК, так что код будет здесь.

560
00:28:42,710 --> 00:28:45,020
Вы, ребята, взгляните после раздела.

561
00:28:45,020 --> 00:28:48,060
Это будет там.

562
00:28:48,060 --> 00:28:50,280
>> Так что я думаю, как делает
это отличается, если мы хотели

563
00:28:50,280 --> 00:28:52,300
вставить в середине или в конце?

564
00:28:52,300 --> 00:28:57,892
Кто-нибудь есть идея о том, что это
псевдокод, как логическое ссылкой

565
00:28:57,892 --> 00:29:00,350
что мы бы хотели, если мы
чтобы вставить его в середине?

566
00:29:00,350 --> 00:29:03,391
Так что, если мы хотели, чтобы вставить ее на
голова, все, что мы сделать, это создать новый узел.

567
00:29:03,391 --> 00:29:06,311
Мы устанавливаем указатель, что
Новый узел какой голове,

568
00:29:06,311 --> 00:29:08,310
а затем мы устанавливаем голову
с новым узлом, правильно?

569
00:29:08,310 --> 00:29:11,560
Если бы мы хотели, чтобы вставить его в середине
из списка, что бы мы должны делать?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> АУДИТОРИЯ: Это будет по-прежнему
быть аналогичный процесс

572
00:29:16,110 --> 00:29:19,114
из, как присвоение и указатель
то назначение этого указателя,

573
00:29:19,114 --> 00:29:20,530
но мы должны найти там.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Пэн: Ровно, так точно
тот же самый процесс, кроме вас

575
00:29:23,560 --> 00:29:27,820
должны найти, где именно вы
хочу, чтобы новый указатель, чтобы пойти в,

576
00:29:27,820 --> 00:29:44,790
так что если я хочу, чтобы вставить в
середина связаны list-- ОК,

577
00:29:44,790 --> 00:29:46,370
давайте говорить, что наш связанный список.

578
00:29:46,370 --> 00:29:49,500
Если мы хотим, чтобы вставить ее прямо здесь,
мы собираемся создать новый узел.

579
00:29:49,500 --> 00:29:50,520
Мы собираемся таНос.

580
00:29:50,520 --> 00:29:52,220
Мы собираемся создать новый узел.

581
00:29:52,220 --> 00:29:55,940
Мы собираемся назначить
указатель этого узла здесь.

582
00:29:55,940 --> 00:29:58,335
>> Но проблема, которая отличается
откуда голова

583
00:29:58,335 --> 00:30:00,490
является то, что мы точно знали,
где голова.

584
00:30:00,490 --> 00:30:01,930
Это было прямо на первой, не так ли?

585
00:30:01,930 --> 00:30:04,870
Но здесь мы должны отслеживать
где мы вставив его в.

586
00:30:04,870 --> 00:30:07,930
Если мы вставляем наш
узел здесь, у нас есть

587
00:30:07,930 --> 00:30:12,270
чтобы убедиться, что
одним предыдущая к этому узлу

588
00:30:12,270 --> 00:30:14,172
это тот, который присваивает указатель.

589
00:30:14,172 --> 00:30:16,380
Итак, вы должны вид
отслеживать две вещи.

590
00:30:16,380 --> 00:30:19,420
Если вам отслеживать, где это
узел в настоящее время вставки в.

591
00:30:19,420 --> 00:30:23,280
Вы также должны отслеживать, где
предыдущий узел, который вы смотрите на

592
00:30:23,280 --> 00:30:24,340
Также там.

593
00:30:24,340 --> 00:30:25,830
Все хорошо с этим?

594
00:30:25,830 --> 00:30:26,500
ХОРОШО.

595
00:30:26,500 --> 00:30:28,000
>> Как насчет вставки в конце концов?

596
00:30:28,000 --> 00:30:34,220
Если бы я хотел, чтобы добавить его here-- если я хотел
чтобы добавить новый узел в конец списка,

597
00:30:34,220 --> 00:30:37,009
как я мог бы идти о том, что делать?

598
00:30:37,009 --> 00:30:39,300
АУДИТОРИЯ: Так себе, то
последний указали на нуль.

599
00:30:39,300 --> 00:30:40,960
ANDI Пэн: Да.

600
00:30:40,960 --> 00:30:43,560
Точно, так что это одно
В настоящее время отмечается знать,

601
00:30:43,560 --> 00:30:46,720
и поэтому я думаю, в этом смысле, это
очень легко добавить к концу списка.

602
00:30:46,720 --> 00:30:51,810
Все, что вам нужно сделать, это установить его
равен нулю, а затем бум.

603
00:30:51,810 --> 00:30:53,070
Прямо там, очень легко.

604
00:30:53,070 --> 00:30:53,960
Очень просто.

605
00:30:53,960 --> 00:30:56,430
>> Очень похож на
голову, но логически вас

606
00:30:56,430 --> 00:30:59,690
хотите, чтобы убедиться, что шаги,
вы берете к делать все это,

607
00:30:59,690 --> 00:31:01,500
вы следуете.

608
00:31:01,500 --> 00:31:04,420
Это очень легко, в середине
ваш код, увязнуть в,

609
00:31:04,420 --> 00:31:05,671
ой, у меня так много указателей.

610
00:31:05,671 --> 00:31:07,461
Я не знаю, где
что-либо, указывая на.

611
00:31:07,461 --> 00:31:09,170
Я даже не знаю, какой узел я на.

612
00:31:09,170 --> 00:31:11,490
Что происходит?

613
00:31:11,490 --> 00:31:13,620
>> Расслабьтесь, успокойтесь, сделайте глубокий вдох.

614
00:31:13,620 --> 00:31:15,530
Нарисуйте свой связанный список.

615
00:31:15,530 --> 00:31:18,800
Если вы говорите, я знать, где именно
Мне нужно вставить это в

616
00:31:18,800 --> 00:31:22,970
и я точно знаю, как передать мой
указатели, гораздо, гораздо легче представить

617
00:31:22,970 --> 00:31:27,200
out-- гораздо проще не
заблудиться в багов в коде.

618
00:31:27,200 --> 00:31:29,410
Все в порядке с этим?

619
00:31:29,410 --> 00:31:31,380
ХОРОШО.

620
00:31:31,380 --> 00:31:35,120
>> Поэтому я думаю, понятие, что мы не
действительно говорили о до сих пор,

621
00:31:35,120 --> 00:31:38,131
и я думаю, вы, вероятно,
не встретите много yet--

622
00:31:38,131 --> 00:31:40,880
это своего рода передовой concept--
является то, что мы на самом деле есть данные

623
00:31:40,880 --> 00:31:43,900
Структура называется вдвойне связанный список.

624
00:31:43,900 --> 00:31:46,390
Итак, как вы, ребята, можете видеть,
все, что мы делаем, создавая

625
00:31:46,390 --> 00:31:50,400
фактическое значение, дополнительный
указатель на каждый из наших узлов

626
00:31:50,400 --> 00:31:52,660
что также указывает на предыдущий узел.

627
00:31:52,660 --> 00:31:58,170
Так мы не только имеем нашу
узлы указывают на следующий.

628
00:31:58,170 --> 00:32:01,430
Они также указывают на предыдущий.

629
00:32:01,430 --> 00:32:04,310
Я собираюсь игнорировать эти два прямо сейчас.

630
00:32:04,310 --> 00:32:06,740
>> Итак у вас есть цепочка
что может двигаться в обоих направлениях,

631
00:32:06,740 --> 00:32:09,630
и тогда это немного легче
логически следовать.

632
00:32:09,630 --> 00:32:11,896
Как здесь, а
отслеживания, о, я

633
00:32:11,896 --> 00:32:14,520
должны знать, что этот узел
тот, который я должен передать,

634
00:32:14,520 --> 00:32:17,532
Я могу просто пойти здесь и
просто вытащить предыдущий.

635
00:32:17,532 --> 00:32:19,490
Тогда я точно знаю, где
то есть, а потом вас

636
00:32:19,490 --> 00:32:21,130
не должны пересекать
Совокупность связанного списка.

637
00:32:21,130 --> 00:32:22,180
Это немного легче.

638
00:32:22,180 --> 00:32:24,960
>> Но таким образом, вы должны вдвойне
количество указателей,

639
00:32:24,960 --> 00:32:26,960
это в два раза больше памяти.

640
00:32:26,960 --> 00:32:28,950
Это много указателей, чтобы отслеживать.

641
00:32:28,950 --> 00:32:32,140
Это немного более сложным, но это
немного более дружественным к пользователю в зависимости

642
00:32:32,140 --> 00:32:34,080
о том, что вы пытаетесь достичь.

643
00:32:34,080 --> 00:32:36,910
>> Таким образом, это тип данных,
Структура полностью существует,

644
00:32:36,910 --> 00:32:40,280
и структура для очень, очень
просто, за исключением все, что вы имея это,

645
00:32:40,280 --> 00:32:43,850
а не просто указатель на следующий,
у вас также есть указатель на предыдущий.

646
00:32:43,850 --> 00:32:45,940
Вот и вся разница была.

647
00:32:45,940 --> 00:32:47,740
Все хорошо с этим?

648
00:32:47,740 --> 00:32:48,240
Круто.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Ладно, так что теперь я
действительно потратить, наверное,

651
00:32:53,280 --> 00:32:56,870
как от 15 до 20 минут или навалом
в остальное время в разделе

652
00:32:56,870 --> 00:32:58,360
говорить о хеш-таблицах.

653
00:32:58,360 --> 00:33:02,590
Как многие из вас, ребята,
прочитал pset5 спецификации?

654
00:33:02,590 --> 00:33:03,620
Ладно, хорошо.

655
00:33:03,620 --> 00:33:06,160
Это выше, чем 50%, как правило.

656
00:33:06,160 --> 00:33:07,560
Это нормально.

657
00:33:07,560 --> 00:33:10,345
>> Итак, как вы, ребята, увидите,
Вы задача в pset5

658
00:33:10,345 --> 00:33:16,790
будет реализовать словарь
где вы загрузить более 140000 слов

659
00:33:16,790 --> 00:33:20,610
что мы даем вам и проверка орфографии
это против всего текста.

660
00:33:20,610 --> 00:33:22,580
Мы дадим вам случайных
шт литературы.

661
00:33:22,580 --> 00:33:23,520
Мы дадим вам Одиссея.

662
00:33:23,520 --> 00:33:24,561
Мы дадим вам Илиаду.

663
00:33:24,561 --> 00:33:26,350
Мы дадим вам Остин Пауэрс.

664
00:33:26,350 --> 00:33:28,220
>> И ваша задача
будет проверка орфографии

665
00:33:28,220 --> 00:33:31,760
каждое слово всего
из тех словарей

666
00:33:31,760 --> 00:33:34,960
по существу, с нашей орфографии.

667
00:33:34,960 --> 00:33:38,620
И так есть несколько частей
создания этой PSET,

668
00:33:38,620 --> 00:33:41,970
Сначала вы хотите быть
в состоянии фактически загрузить

669
00:33:41,970 --> 00:33:43,970
все слова в ваш
словарь, а затем вам

670
00:33:43,970 --> 00:33:45,530
хочу, чтобы иметь возможность
орфографии и все из них.

671
00:33:45,530 --> 00:33:48,780
И так, как, например, вы собираетесь требовать
структура данных, которая может сделать это быстро

672
00:33:48,780 --> 00:33:50,790
и эффективно и динамично.

673
00:33:50,790 --> 00:33:52,900
>> Поэтому я полагаю, самый простой
способ сделать это, вам

674
00:33:52,900 --> 00:33:55,010
вероятно создать массив, верно?

675
00:33:55,010 --> 00:33:58,910
Самый простой способ хранения вас
можно создать массив 140000 слов

676
00:33:58,910 --> 00:34:03,400
и просто разместить их там, и все
затем пройти их бинарного поиска

677
00:34:03,400 --> 00:34:06,780
или выборов или не--
жаль, что это сортировка.

678
00:34:06,780 --> 00:34:10,729
Вы можете сортировать их, а затем пройти их
двоичный поиск или просто линейный поиск

679
00:34:10,729 --> 00:34:13,730
и только окончательные слова, но
занимает огромное количество памяти,

680
00:34:13,730 --> 00:34:15,190
и это не очень эффективно.

681
00:34:15,190 --> 00:34:18,350
>> И таким образом мы собираемся начать
говорить о способах изготовления

682
00:34:18,350 --> 00:34:20,110
наша продолжительность более эффективным.

683
00:34:20,110 --> 00:34:23,190
И наша цель, чтобы получить
постоянная времени, где

684
00:34:23,190 --> 00:34:25,810
это почти как массивы, где
у вас есть мгновенный доступ.

685
00:34:25,810 --> 00:34:28,560
Если бы я хотел, чтобы искать что-нибудь,
Я хочу, чтобы иметь возможность просто,

686
00:34:28,560 --> 00:34:30,810
бум, найти его точно, и вытащить его.

687
00:34:30,810 --> 00:34:34,100
И так структура, в которой
мы будем становится очень близко

688
00:34:34,100 --> 00:34:37,569
чтобы быть в состоянии получить доступ к постоянным
Время, это Святой Грааль

689
00:34:37,569 --> 00:34:41,370
в программировании постоянного
время называется хеш-таблицы.

690
00:34:41,370 --> 00:34:45,370
И так Дэвид упоминалось ранее
[Неразборчиво] немного в лекции,

691
00:34:45,370 --> 00:34:49,100
но мы собираемся, чтобы действительно
погружение в глубокий этой неделе

692
00:34:49,100 --> 00:34:51,780
на кусок, который относительно
как хэш-таблица работает.

693
00:34:51,780 --> 00:34:53,949
>> Так образом, что хэш
таблица работы, например,

694
00:34:53,949 --> 00:35:00,230
если бы я хотел, чтобы сохранить кучу словами,
куча слов в английском языке,

695
00:35:00,230 --> 00:35:02,940
Я теоретически может поместить
банан, яблоко, киви, манго, пара,

696
00:35:02,940 --> 00:35:04,980
и дыня все только на массиве.

697
00:35:04,980 --> 00:35:07,044
Все они могли вписаться и быть найти.

698
00:35:07,044 --> 00:35:09,210
Это было бы своего рода боли
поиск и доступ через,

699
00:35:09,210 --> 00:35:12,920
но простой способ сделать это состоит в
что мы можем создать на самом деле структура

700
00:35:12,920 --> 00:35:15,680
называется хеш-таблица, где мы хэш.

701
00:35:15,680 --> 00:35:19,880
Мы бежим все наши ключи через
хэш-функция, уравнение,

702
00:35:19,880 --> 00:35:22,600
Получается, что их все в
какая-то ценность

703
00:35:22,600 --> 00:35:28,740
что тогда мы можем хранить на
существу массив связанного списка.

704
00:35:28,740 --> 00:35:32,570
>> И вот, если мы хотим
для хранения английские слова,

705
00:35:32,570 --> 00:35:37,250
мы могли потенциально просто, я не
знаете, превратить все первые буквы

706
00:35:37,250 --> 00:35:39,630
в какой-то номер.

707
00:35:39,630 --> 00:35:43,140
И поэтому, например, если бы я хотел
А быть синонимом apple--

708
00:35:43,140 --> 00:35:47,460
или с индексом 0, а
В синонимом 1,

709
00:35:47,460 --> 00:35:51,030
мы можем иметь 26 записей
что может просто хранить

710
00:35:51,030 --> 00:35:53,610
все буквы
алфавит, что мы начнем с.

711
00:35:53,610 --> 00:35:56,130
И тогда мы можем иметь
яблоко на индексом 0.

712
00:35:56,130 --> 00:35:59,160
Мы можем иметь банан индекса
1, дыня в индексе 2,

713
00:35:59,160 --> 00:36:00,540
и так далее и тому подобное.

714
00:36:00,540 --> 00:36:04,460
И таким образом, если я хотел, чтобы поиск
мой хэш-таблица и доступ яблоко,

715
00:36:04,460 --> 00:36:07,560
Я знаю, яблоко начинается с
Л-и я точно знаю,

716
00:36:07,560 --> 00:36:10,860
что она должна быть и хэш
Таблица с индексом 0, потому что

717
00:36:10,860 --> 00:36:13,620
функции, присвоенные.

718
00:36:13,620 --> 00:36:16,572
>> Так что я не знаю, мы
программа пользователя, где

719
00:36:16,572 --> 00:36:18,780
Вы будете платить с
arbitrarily-- не произвольно,

720
00:36:18,780 --> 00:36:22,530
в попытке задумчиво
думать о хорошем уравнений

721
00:36:22,530 --> 00:36:25,460
чтобы иметь возможность распространяться
все ваши значений

722
00:36:25,460 --> 00:36:29,370
таким образом, они могут легко получить доступ к
это позже с как уравнения

723
00:36:29,370 --> 00:36:31,130
что вы, сами, знаете.

724
00:36:31,130 --> 00:36:35,210
Таким образом, в смысле, если я хотел, чтобы перейти к
манго, я знаю, о, это начинается с м.

725
00:36:35,210 --> 00:36:37,134
Она должна быть в индексе 12.

726
00:36:37,134 --> 00:36:38,800
Я не придется искать во всем.

727
00:36:38,800 --> 00:36:42,080
Я знаю, exactly-- я мог бы просто пойти в
индекс 12 и тянуть это.

728
00:36:42,080 --> 00:36:45,520
>> Все ясно, как
Функция Hash Table работает?

729
00:36:45,520 --> 00:36:48,380
Это своего рода просто более сложный массив.

730
00:36:48,380 --> 00:36:50,010
Это все, что есть.

731
00:36:50,010 --> 00:36:51,630
ХОРОШО.

732
00:36:51,630 --> 00:36:57,690
>> Так что я думаю, что мы столкнулись с
этот вопрос, что

733
00:36:57,690 --> 00:37:06,390
произойдет, если у вас есть несколько вещей,
которые дают вам тот же индекс?

734
00:37:06,390 --> 00:37:10,570
Так сказать, нашу функцию, все это
сделал считать, что первое письмо

735
00:37:10,570 --> 00:37:14,490
и превратить это в
Соответствующий 0 до 25 Индекс.

736
00:37:14,490 --> 00:37:17,137
Это совершенно нормально, если
есть только один из каждого.

737
00:37:17,137 --> 00:37:18,970
Но второй вы начинаете
имеющие более, вы

738
00:37:18,970 --> 00:37:20,910
будет иметь то, что называется столкновение.

739
00:37:20,910 --> 00:37:25,580
>> Так что, если я пытаюсь вставить похоронить в хэш
таблица, уже банан на нем,

740
00:37:25,580 --> 00:37:27,870
что произойдет, когда
Вы пытаетесь вставить, что?

741
00:37:27,870 --> 00:37:30,930
Плохие вещи, потому что банан
уже существует в индексе

742
00:37:30,930 --> 00:37:33,800
что вы хотите, чтобы хранить его в.

743
00:37:33,800 --> 00:37:35,560
Берри рода, как, ах, что же мне делать?

744
00:37:35,560 --> 00:37:37,080
Я не знаю, куда идти.

745
00:37:37,080 --> 00:37:38,410
Как решить эту проблему?

746
00:37:38,410 --> 00:37:41,150
>> И так вы, ребята, будет своего рода
видеть, что мы делаем это сложная вещь

747
00:37:41,150 --> 00:37:44,810
где мы можем на самом деле вид
создать связанный список в наших массивов.

748
00:37:44,810 --> 00:37:46,840
И так самый простой способ
думать об этом,

749
00:37:46,840 --> 00:37:50,830
все хэш-таблицы является
массив связанных списков.

750
00:37:50,830 --> 00:37:55,670
И так, в этом смысле, у вас есть
Этот красивый массив указателей,

751
00:37:55,670 --> 00:37:58,740
а затем каждый указатель в
что значение, в этом индексе,

752
00:37:58,740 --> 00:38:00,740
может на самом деле указывать на другие вещи.

753
00:38:00,740 --> 00:38:05,720
И так у вас есть все эти отдельные
цепи сходит одном большом массиве.

754
00:38:05,720 --> 00:38:07,960
>> И вот, если я
хотел вставить ягоду,

755
00:38:07,960 --> 00:38:11,220
Я знаю, ладно, я собираюсь ввести
это через мой хэш-функции.

756
00:38:11,220 --> 00:38:15,070
Я собираюсь закончить с индексом
1, а затем я собираюсь быть в состоянии иметь

757
00:38:15,070 --> 00:38:20,410
просто меньше подмножество этого
гигант словарь 140,000 слово.

758
00:38:20,410 --> 00:38:24,220
И тогда я могу просто посмотреть
через 1/26, что.

759
00:38:24,220 --> 00:38:27,910
>> И так, то я могу просто вставить
ягоды либо до, либо после того, как банан

760
00:38:27,910 --> 00:38:28,820
в этом случае?

761
00:38:28,820 --> 00:38:29,700
После, правда?

762
00:38:29,700 --> 00:38:33,920
И так вы будете хотеть, чтобы
вставить этот узел после банана,

763
00:38:33,920 --> 00:38:36,667
и таким образом Вы собираетесь вставить
в хвосте этой связанного списка.

764
00:38:36,667 --> 00:38:38,500
Я собираюсь вернуться
в этом предыдущем слайде,

765
00:38:38,500 --> 00:38:40,680
так что вы, ребята, можете увидеть, как
Хэш функция работает.

766
00:38:40,680 --> 00:38:43,980
>> Так хэш функция это уравнение
что вы работаете вид вашего входа

767
00:38:43,980 --> 00:38:46,940
через, чтобы получить все индекс
Вы хотите, чтобы назначить его к.

768
00:38:46,940 --> 00:38:51,130
И так, в этом примере, все мы хотели
нужно было взять первую букву,

769
00:38:51,130 --> 00:38:55,890
свою очередь, что в индекс, то
может хранить, что в нашей хэш-функции.

770
00:38:55,890 --> 00:39:00,160
Все, что мы делаем здесь мы
преобразовании первую букву.

771
00:39:00,160 --> 00:39:04,770
Так KeyKey [0] только первая буква
всего, что строка мы с,

772
00:39:04,770 --> 00:39:05,720
мы передаем в.

773
00:39:05,720 --> 00:39:09,740
Мы преобразования, что верхний и
мы вычитая заглавными А,

774
00:39:09,740 --> 00:39:11,740
поэтому все, что делает
дает нам ряд

775
00:39:11,740 --> 00:39:13,670
в которых мы можем хэш наши ценности на.

776
00:39:13,670 --> 00:39:16,550
>> А потом мы собираемся
вернуться хэш модуль РАЗМЕР.

777
00:39:16,550 --> 00:39:19,340
Будьте очень, очень осторожны,
потому, теоретически, здесь

778
00:39:19,340 --> 00:39:21,870
Ваш хэш-значение может быть бесконечным.

779
00:39:21,870 --> 00:39:23,660
Это может быть просто пойти дальше и дальше и дальше.

780
00:39:23,660 --> 00:39:26,080
Это может быть некоторые действительно,
действительно большое значение,

781
00:39:26,080 --> 00:39:29,849
а потому, что ваш хэш-таблицы, что
Вы создали только имеет 26 индексов,

782
00:39:29,849 --> 00:39:31,890
Вы хотите, чтобы убедиться, что ваш
modulusing, так что вы

783
00:39:31,890 --> 00:39:33,848
не run-- это то же самое
что в качестве queue--

784
00:39:33,848 --> 00:39:36,320
так что вы не сошли с
Дно Вашей хэш-функции.

785
00:39:36,320 --> 00:39:39,210
>> Вы хотите, чтобы обернуть его назад вокруг
так же, как в [неразборчиво], когда

786
00:39:39,210 --> 00:39:41,750
у вас, как очень,
очень большая буква, вы

787
00:39:41,750 --> 00:39:43,740
не хочу, чтобы
просто бежать конец.

788
00:39:43,740 --> 00:39:46,948
То же самое здесь, вы хотите, чтобы убедиться, что
он не работает с конца, накладываясь

789
00:39:46,948 --> 00:39:48,330
вокруг верхней части таблицы.

790
00:39:48,330 --> 00:39:50,530
Так что это просто очень
просто хэш функция.

791
00:39:50,530 --> 00:39:56,570
Все, что сделал первый взять
Письмо какой нашем входе был

792
00:39:56,570 --> 00:40:01,660
и превратить это в индекс,
мы могли бы поставить в нашу хэш-таблицы.

793
00:40:01,660 --> 00:40:05,450
>> Да, и так, как я сказал раньше,
так, что мы разрешения коллизий

794
00:40:05,450 --> 00:40:09,330
в нашей хэш таблицы, имеющие,
что мы называем, цепочки.

795
00:40:09,330 --> 00:40:13,860
Так что, если вы пытаетесь вставить несколько
слова, которые начинаются с той же вещи,

796
00:40:13,860 --> 00:40:16,145
Вы будете иметь один хэш-значение.

797
00:40:16,145 --> 00:40:18,770
Авокадо и яблоко, если у Вас есть
запустить его через нашу хэш-функции,

798
00:40:18,770 --> 00:40:21,450
собираются, чтобы дать вам
такое же количество, количество 0.

799
00:40:21,450 --> 00:40:24,550
И так как мы решить это
что мы можем на самом деле вид связать их

800
00:40:24,550 --> 00:40:27,010
вместе с помощью связанных списков.

801
00:40:27,010 --> 00:40:29,600
>> И поэтому в этом смысле,
вы, ребята, можете увидеть вид

802
00:40:29,600 --> 00:40:32,640
как структуры данных,
мы были настройки, ранее

803
00:40:32,640 --> 00:40:35,870
как изюм связаны список рода
из можете прийти вместе в один.

804
00:40:35,870 --> 00:40:38,860
И тогда вы можете создать еще
более эффективные структуры данных

805
00:40:38,860 --> 00:40:43,350
которые могут обрабатывать большие объемы
Данные, которые динамически изменять размер в зависимости

806
00:40:43,350 --> 00:40:44,870
от ваших потребностей.

807
00:40:44,870 --> 00:40:45,620
Все ясно?

808
00:40:45,620 --> 00:40:47,580
Все вроде ясно,
на то, что происходит здесь?

809
00:40:47,580 --> 00:40:52,110
>> Если бы я хотел, чтобы insert--, что это
фрукты, который начинается с, я не знаю

810
00:40:52,110 --> 00:40:54,726
B, кроме ягод, банан.

811
00:40:54,726 --> 00:40:55,710
>> АУДИТОРИЯ: Ежевика.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Пэн: Blackberry, ежевика.

813
00:40:57,910 --> 00:41:00,530
Где ежевики идти сюда?

814
00:41:00,530 --> 00:41:04,251
Ну, мы на самом деле не сортируются
это еще, но теоретически

815
00:41:04,251 --> 00:41:06,250
если бы мы хотели, чтобы это
в алфавитном порядке,

816
00:41:06,250 --> 00:41:07,944
где должны BlackBerry идти?

817
00:41:07,944 --> 00:41:09,210
>> АУДИТОРИЯ: [неразборчиво]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Пэн: Ровно, после здесь, верно?

819
00:41:11,100 --> 00:41:14,950
Но так как это очень сложно
reorder-- Я думаю, это до вас, ребята.

820
00:41:14,950 --> 00:41:17,920
Вы, ребята, можете полностью
осуществить все, что вы хотите.

821
00:41:17,920 --> 00:41:20,730
Чем больше эффективный способ
делать это, возможно,

822
00:41:20,730 --> 00:41:24,570
будет сортировать ваш связан
список в алфавитном порядке,

823
00:41:24,570 --> 00:41:26,520
и поэтому, когда вы
вставки вещи, вы хотите

824
00:41:26,520 --> 00:41:28,632
чтобы убедиться, что вставить их
в алфавитном порядке

825
00:41:28,632 --> 00:41:30,590
так что потом, когда вы
пытаются искать их,

826
00:41:30,590 --> 00:41:32,410
Вы не должны пройти все.

827
00:41:32,410 --> 00:41:35,290
Вы точно знаете, где
она есть, и это проще.

828
00:41:35,290 --> 00:41:39,100
>> Но если вы вроде есть
вещи перемежаются случайно,

829
00:41:39,100 --> 00:41:41,420
Вы по-прежнему будете иметь
пройти его в любом случае.

830
00:41:41,420 --> 00:41:44,990
И поэтому, если я хотел, чтобы просто
вставьте ежевики здесь

831
00:41:44,990 --> 00:41:47,470
и я хотел, чтобы искать
это, знаю, ох, ежевика

832
00:41:47,470 --> 00:41:52,012
должны начать с индексом 1, так что я
знаю, мгновенно просто искать на 1.

833
00:41:52,012 --> 00:41:53,970
И тогда я могу рода
пройти связанный список

834
00:41:53,970 --> 00:41:56,120
пока я не получить к BlackBerry,
и then-- да?

835
00:41:56,120 --> 00:41:59,550
>> АУДИТОРИЯ: Если вы пытаетесь create--
Я думаю, как это очень простой хэш

836
00:41:59,550 --> 00:42:00,050
функция.

837
00:42:00,050 --> 00:42:02,835
И если мы хотим, чтобы сделать
несколько слоев, что, как,

838
00:42:02,835 --> 00:42:05,870
ОК, мы хотим, чтобы отделить в
как и все алфавитно

839
00:42:05,870 --> 00:42:09,040
а потом снова хотел другой набор
из букв алфавита в течение, что,

840
00:42:09,040 --> 00:42:11,715
мы положить как хэш
таблица в хэш-таблице,

841
00:42:11,715 --> 00:42:13,256
или как функции внутри функции?

842
00:42:13,256 --> 00:42:14,880
Или that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Пэн: Так ваш хэш
function-- свой хэш-таблицу

844
00:42:17,510 --> 00:42:19,360
может быть как большой, как вы хотите.

845
00:42:19,360 --> 00:42:21,930
Таким образом, в этом смысле, я думал,
это было очень легко, очень

846
00:42:21,930 --> 00:42:25,320
просто для меня, чтобы просто вроде основе
на буквы первого слова.

847
00:42:25,320 --> 00:42:28,690
И так есть только 26 вариантов.

848
00:42:28,690 --> 00:42:32,650
Я могу получить только 26 вариантов из
0 до 25, потому что они могут только

849
00:42:32,650 --> 00:42:36,510
начать от А до Z. Но если вы хотите
добавить, пожалуй, больше сложности

850
00:42:36,510 --> 00:42:39,260
или быстрее бежать к вашему времени
хеш-таблица, вы абсолютно

851
00:42:39,260 --> 00:42:40,760
может сделать все виды вещей.

852
00:42:40,760 --> 00:42:43,330
Вы можете сделать свой собственный
Уравнение, которое дает вам

853
00:42:43,330 --> 00:42:48,000
более рассылки в
слов, то при поиске,

854
00:42:48,000 --> 00:42:49,300
это будет быстрее.

855
00:42:49,300 --> 00:42:52,100
>> Это полностью зависит от вас, ребята
как вы хотите, чтобы осуществить это.

856
00:42:52,100 --> 00:42:55,140
Думайте об этом как только ведрами.

857
00:42:55,140 --> 00:42:57,376
Если бы я хотел, чтобы иметь
26 ведра, я собираюсь

858
00:42:57,376 --> 00:42:59,420
сортировать вещи в этих ведрах.

859
00:42:59,420 --> 00:43:02,980
Но я собираюсь иметь кучу
вещи в каждом ведре,

860
00:43:02,980 --> 00:43:05,890
так что если вы хотите, чтобы сделать его
быстрее и эффективнее,

861
00:43:05,890 --> 00:43:07,190
дайте мне сто ведер.

862
00:43:07,190 --> 00:43:09,290
>> Но тогда вы должны выяснить
способ сортировки вещи так, чтобы они

863
00:43:09,290 --> 00:43:11,040
в надлежащем ведро они должны быть в.

864
00:43:11,040 --> 00:43:13,331
Но потом, когда вы на самом деле
хочу посмотреть на этого ведра,

865
00:43:13,331 --> 00:43:16,410
это намного быстрее, потому что есть
меньше вещи в каждом ведре.

866
00:43:16,410 --> 00:43:20,250
И так, да, это на самом деле
трюк для вас, ребята в pset5

867
00:43:20,250 --> 00:43:22,360
является то, что вы будете
вызов просто создать

868
00:43:22,360 --> 00:43:26,170
все, что является наиболее эффективным
Функция Вы можете думать, чтобы быть

869
00:43:26,170 --> 00:43:28,520
возможность хранения и проверки этих значений.

870
00:43:28,520 --> 00:43:30,840
>> Всего до вас, ребята
Однако вы хотите, чтобы это сделать,

871
00:43:30,840 --> 00:43:32,229
но это действительно хорошая точка.

872
00:43:32,229 --> 00:43:34,520
То, что такая логика вы
хочу, чтобы начать думать о

873
00:43:34,520 --> 00:43:37,236
, ну, почему я не сделать больше ведра.

874
00:43:37,236 --> 00:43:39,527
И тогда я должен искать
меньше вещей, и тогда, возможно, я

875
00:43:39,527 --> 00:43:41,640
имеют различную хэш-функцию.

876
00:43:41,640 --> 00:43:45,500
>> Да, есть много способов сделать это
PSET, некоторые быстрее, чем другие.

877
00:43:45,500 --> 00:43:50,630
Я полностью собираюсь просто посмотреть, как
быстро стал самым быстрым вы, ребята,

878
00:43:50,630 --> 00:43:55,170
быть в состоянии получить ваши функции на работу.

879
00:43:55,170 --> 00:43:58,176
ОК, все хорошо на
Иерархии серверов и хэш-таблицы?

880
00:43:58,176 --> 00:44:00,800
Это на самом деле, как очень простой
понятие, если вы думаете об этом.

881
00:44:00,800 --> 00:44:05,160
Все это является разделение все
Ваши входы в ведра,

882
00:44:05,160 --> 00:44:10,670
сортируя их, а затем ищут в
список, что там связано с.

883
00:44:10,670 --> 00:44:11,852
>> Круто.

884
00:44:11,852 --> 00:44:18,160
Ладно, теперь у нас есть разного рода
структуры данных, которая называется деревом.

885
00:44:18,160 --> 00:44:20,850
Давайте идти дальше и говорить о попытках
которые существенно отличаются,

886
00:44:20,850 --> 00:44:22,330
но в той же категории.

887
00:44:22,330 --> 00:44:29,010
По сути, все дерево вместо этого
организации данных в линейном образом

888
00:44:29,010 --> 00:44:32,560
что хэш-таблица does-- вас
Знаете, он получил верх и низ

889
00:44:32,560 --> 00:44:37,900
а затем вы вроде ссылаются прочь it-- в
Дерево имеет верхний, что вы называете корень,

890
00:44:37,900 --> 00:44:40,220
и то он имеет листья все вокруг него.

891
00:44:40,220 --> 00:44:42,390
>> А так все у вас здесь
это только верхний узел

892
00:44:42,390 --> 00:44:45,980
который указывает на другие узлы, что точки
чтобы более узлов, и так далее и тому подобное.

893
00:44:45,980 --> 00:44:48,130
И так вы просто расщепление ветвей.

894
00:44:48,130 --> 00:44:53,255
Это просто другой способ организации
Данные, и потому что мы называем это дерево,

895
00:44:53,255 --> 00:44:56,270
вы, ребята, просто-- это просто
моделируется, чтобы смотреть, как дерево.

896
00:44:56,270 --> 00:44:57,670
Вот почему мы называем его деревья.

897
00:44:57,670 --> 00:44:59,370
>> Хэш таблица выглядит как таблица.

898
00:44:59,370 --> 00:45:01,310
Дерево выглядит как дерево.

899
00:45:01,310 --> 00:45:03,300
Все это является отдельным
способ организации узлов

900
00:45:03,300 --> 00:45:06,020
в зависимости от того, что ваши потребности.

901
00:45:06,020 --> 00:45:11,810
>> Так у вас есть корни и
то у вас есть листья.

902
00:45:11,810 --> 00:45:15,380
Таким образом, что мы можем особенно
думаю о нем бинарное дерево,

903
00:45:15,380 --> 00:45:18,150
бинарное дерево просто
Конкретный тип дерева

904
00:45:18,150 --> 00:45:22,450
где каждый узел только точки
чтобы, при макс, два других узлов.

905
00:45:22,450 --> 00:45:25,434
И вот у вас есть отличный
Симметрия в дереве

906
00:45:25,434 --> 00:45:28,600
что делает его легче своего рода выглядеть
на какие ценности вы, потому что тогда вы

907
00:45:28,600 --> 00:45:30,150
всегда слева или право.

908
00:45:30,150 --> 00:45:33,150
Там никогда не как левой трети от
левая или четвертый слева.

909
00:45:33,150 --> 00:45:36,358
Это просто у вас есть левый и правый
и вы можете искать либо из этих двух.

910
00:45:36,358 --> 00:45:38,980
И так, почему это полезно?

911
00:45:38,980 --> 00:45:40,980
Таким образом, что это
полезна, если вы ищете

912
00:45:40,980 --> 00:45:42,890
искать через значения, верно?

913
00:45:42,890 --> 00:45:45,640
Вместо реализации двоичный
поиск в массиве ошибок,

914
00:45:45,640 --> 00:45:49,260
если вы хотите, чтобы иметь возможность вставить узлы
и забрать узлы по желанию, а также

915
00:45:49,260 --> 00:45:52,185
сохранить поиск
мощности двоичного поиска.

916
00:45:52,185 --> 00:45:54,560
Таким образом, в этом случае, мы вроде
tricking-- помню, когда мы

917
00:45:54,560 --> 00:45:56,530
сказал связанные списки не могут бинарный поиск?

918
00:45:56,530 --> 00:46:01,700
Мы вроде создания структуры данных
что приемы, которые в рабочее.

919
00:46:01,700 --> 00:46:05,034
>> И это потому, что связанные списки являются линейными,
они только ссылаются один за другим.

920
00:46:05,034 --> 00:46:06,950
Мы можем иметь вид
разного рода указателей

921
00:46:06,950 --> 00:46:09,408
которые указывают на разных узлах
что может помочь нам в поиске.

922
00:46:09,408 --> 00:46:12,590
И вот, если бы я хотел, чтобы
есть дерево двоичного поиска,

923
00:46:12,590 --> 00:46:14,090
Я знаю, что моего середине, если 55 лет.

924
00:46:14,090 --> 00:46:18,280
Я просто хочу, чтобы создать что
как мой середине, как мой корень,

925
00:46:18,280 --> 00:46:20,770
и тогда я буду иметь
Значения выделении из него.

926
00:46:20,770 --> 00:46:25,610
>> Так вот, если я собираюсь искать
значение 66, я могу начать в 55 лет.

927
00:46:25,610 --> 00:46:27,310
Это больше, чем 66 55?

928
00:46:27,310 --> 00:46:30,970
Да, это, так что я знаю, что я муз поиск
я н право указатель этого дерева.

929
00:46:30,970 --> 00:46:32,440
Я иду до 77.

930
00:46:32,440 --> 00:46:35,367
ОК, это меньше, чем 66 или больше, чем 77?

931
00:46:35,367 --> 00:46:37,950
Это меньше, чем, так что вы знаете, о,
который должен быть слева узел.

932
00:46:37,950 --> 00:46:41,410
>> И вот мы вроде сохранения
все великие вещи о массивах,

933
00:46:41,410 --> 00:46:44,420
так как динамическое изменение размера
объектов, будучи

934
00:46:44,420 --> 00:46:49,530
возможность вставлять и удалять по желанию,
без того, чтобы беспокоиться о фиксированной

935
00:46:49,530 --> 00:46:50,370
объем пространства.

936
00:46:50,370 --> 00:46:52,820
Мы по-прежнему сохраняют все
эти замечательные вещи

937
00:46:52,820 --> 00:46:57,140
в то же время быть в состоянии сохранить
войти и поиск время бинарного поиска

938
00:46:57,140 --> 00:47:00,450
что мы были только ранее
возможность получить фразу.

939
00:47:00,450 --> 00:47:06,310
>> Прохладный структура данных, вроде
Комплекс для реализации, узел.

940
00:47:06,310 --> 00:47:08,311
Как вы можете видеть, все это
это структура узла

941
00:47:08,311 --> 00:47:10,143
является то, что у вас есть левый
и право указателем.

942
00:47:10,143 --> 00:47:11,044
Это все, что есть.

943
00:47:11,044 --> 00:47:12,960
Таким образом, вместо просто
имеющий х или предыдущий.

944
00:47:12,960 --> 00:47:15,920
Вы должны налево или направо, а затем
Вы можете вид связать их вместе

945
00:47:15,920 --> 00:47:16,836
Однако вы того пожелаете.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> Хорошо, мы на самом деле происходит
просто взять несколько минут.

948
00:47:24,270 --> 00:47:25,790
Итак, мы собираемся, чтобы вернуться сюда.

949
00:47:25,790 --> 00:47:28,270
Как я уже говорил,
Я вроде пояснил

950
00:47:28,270 --> 00:47:31,520
логика, как мы
будет искать через это.

951
00:47:31,520 --> 00:47:33,860
Мы собираемся, чтобы попытаться
pseudocoding этот, чтобы увидеть

952
00:47:33,860 --> 00:47:38,000
если мы можем рода применить
Та же логика бинарного поиска

953
00:47:38,000 --> 00:47:40,055
на другой тип структуры данных.

954
00:47:40,055 --> 00:47:45,049
Если вы, ребята, хотите, чтобы принять как пара
минут, чтобы просто думать об этом.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ХОРОШО.

957
00:48:46,925 --> 00:48:51,407
Ладно, я собираюсь
на самом деле просто не даст вам the-- нет,

958
00:48:51,407 --> 00:48:52,990
мы будем говорить о псевдокоде первым.

959
00:48:52,990 --> 00:48:56,580
Так кто-нибудь хочет
дать удар на то, что

960
00:48:56,580 --> 00:49:02,100
первое, что вы хотите делать, когда
Вы начинаете поиск по?

961
00:49:02,100 --> 00:49:04,460
Если мы ищем
значение 66, что

962
00:49:04,460 --> 00:49:07,940
Первое, что мы хотим делать, если
мы хотим, чтобы этот бинарный поиск дерево?

963
00:49:07,940 --> 00:49:10,760
>> АУДИТОРИЯ: Вы хотите, чтобы смотреть прямо
и посмотрите налево и увидите [неразборчиво]

964
00:49:10,760 --> 00:49:11,230
большее число.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Пэн: Да, именно так.

966
00:49:12,271 --> 00:49:15,350
Таким образом, вы будете смотреть на корне.

967
00:49:15,350 --> 00:49:18,180
Там много способов вы можете позвонить
это, ваши родитель узла люди говорят.

968
00:49:18,180 --> 00:49:21,317
Я хотел бы сказать, потому что корень
это как корень дерева.

969
00:49:21,317 --> 00:49:23,400
Вы собираетесь смотреть на
Ваш корневой узел, и вы

970
00:49:23,400 --> 00:49:26,940
увидите 66 больше
или меньше, чем 55.

971
00:49:26,940 --> 00:49:30,360
И если это больше, чем, ну, это
больше, чем, где мы хотим, чтобы посмотреть?

972
00:49:30,360 --> 00:49:32,000
Куда мы хотим искать сейчас, правда?

973
00:49:32,000 --> 00:49:34,340
Мы хотим, чтобы поиск в
Правая половина этого дерева.

974
00:49:34,340 --> 00:49:38,390
>> Итак, мы имеем, удобно, А
указатель, который указывает на право.

975
00:49:38,390 --> 00:49:44,325
И так, то мы можем установить
наш новый корень, чтобы быть 77.

976
00:49:44,325 --> 00:49:46,450
Мы можем просто пойти туда, где
указатель указывает.

977
00:49:46,450 --> 00:49:49,100
Ну, ну, здесь мы начинаем
на 77, и мы можем только

978
00:49:49,100 --> 00:49:51,172
сделать это рекурсивно снова и снова.

979
00:49:51,172 --> 00:49:52,880
Таким образом, вы вроде
от того, имеют функцию.

980
00:49:52,880 --> 00:49:57,430
У вас есть способ поиска, что вы
можно просто повторять снова и снова и снова,

981
00:49:57,430 --> 00:50:02,720
в зависимости от того, где вы хотите, чтобы посмотреть
пока вы в конечном итоге не получить к значению

982
00:50:02,720 --> 00:50:04,730
что вы ищете.

983
00:50:04,730 --> 00:50:05,230
Сделайте чувство?

984
00:50:05,230 --> 00:50:07,800
>> Я собираюсь показать Вам фактический
Код, и это много кода.

985
00:50:07,800 --> 00:50:08,674
Нет необходимости волноваться.

986
00:50:08,674 --> 00:50:09,910
Мы будем говорить через него.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Вообще-то, нет.

989
00:50:14,020 --> 00:50:15,061
Это было просто псевдокод.

990
00:50:15,061 --> 00:50:17,860
ОК, это было просто псевдокод,
который является немного сложным,

991
00:50:17,860 --> 00:50:19,751
но это совершенно нормально.

992
00:50:19,751 --> 00:50:21,000
Каждый следующий по здесь?

993
00:50:21,000 --> 00:50:24,260
Если корень нуль, возвращение
ложь, потому что это означает, что

994
00:50:24,260 --> 00:50:26,850
Вы даже не имеют ничего там.

995
00:50:26,850 --> 00:50:31,376
>> Если корень п значение, поэтому, если он
случается, тот, который вы смотрите,

996
00:50:31,376 --> 00:50:34,000
то вы будете возвращаться правда
потому что вы знаете вы его нашли.

997
00:50:34,000 --> 00:50:36,250
Но если значение меньше
чем корень п, вы

998
00:50:36,250 --> 00:50:38,332
будет искать левого
ребенок или левая лист,

999
00:50:38,332 --> 00:50:39,540
все, что вы хотите назвать это.

1000
00:50:39,540 --> 00:50:41,750
И если значение больше, чем корень,
Вы собираетесь искать нужное дерево,

1001
00:50:41,750 --> 00:50:44,610
Затем просто запустите функцию
через поиск снова.

1002
00:50:44,610 --> 00:50:48,037
>> А если корень пустой, что это
означает, что вы дошли до конца?

1003
00:50:48,037 --> 00:50:50,120
Это означает, что у вас есть не
более больше листьев для поиска,

1004
00:50:50,120 --> 00:50:52,230
то вы знаете, о, я
думаю, это не здесь

1005
00:50:52,230 --> 00:50:55,063
потому что после того как я посмотрел через
все это, и это не здесь,

1006
00:50:55,063 --> 00:50:56,930
он просто не может быть здесь.

1007
00:50:56,930 --> 00:50:58,350
>> Имеет ли это смысл для всех?

1008
00:50:58,350 --> 00:51:03,230
Так как бинарный поиск, сохраняющих
Возможности связанных списков.

1009
00:51:03,230 --> 00:51:09,200
Холодный, и так второй тип
структуры данных вы, ребята

1010
00:51:09,200 --> 00:51:13,180
может попробовать реализовать на PSET,
у вас есть только один способ выбрать.

1011
00:51:13,180 --> 00:51:19,430
Но, возможно, альтернативный метод
хэш-таблица является то, что мы называем синтаксического дерева.

1012
00:51:19,430 --> 00:51:24,080
>> Все, Trie это является
Конкретный тип дерева,

1013
00:51:24,080 --> 00:51:28,600
имеет значения, которые выходят на другие значения.

1014
00:51:28,600 --> 00:51:31,450
Таким образом, вместо того, двоичный
дерево в том смысле, что только один

1015
00:51:31,450 --> 00:51:35,940
что может указывать на двоих, вы можете иметь
Одно дело точка многих, многих вещей.

1016
00:51:35,940 --> 00:51:39,450
Вы по существу есть массивы
внутри которого вы храните

1017
00:51:39,450 --> 00:51:41,790
указатели, которые указывают на другие массивы.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Таким образом, узел, как мы
будет определять синтаксического дерева

1020
00:51:49,460 --> 00:51:52,590
что мы хотим, чтобы иметь
Логическое, с слово, верно?

1021
00:51:52,590 --> 00:51:54,920
Таким образом, узел Логический
как истинное или ложное,

1022
00:51:54,920 --> 00:51:58,490
в первую очередь в голову
что массив, это слово?

1023
00:51:58,490 --> 00:52:03,620
Во-вторых, вы хотите, чтобы указатели
к тому, что остальные из них.

1024
00:52:03,620 --> 00:52:07,470
Немного сложный, немного абстрактно, но
Я объясню, что это все средства.

1025
00:52:07,470 --> 00:52:13,800
>> Так вот, в верхней, если вы
есть массив, объявленный уже

1026
00:52:13,800 --> 00:52:17,040
узел, где у вас есть логическое
Значение, сохраненное в передней

1027
00:52:17,040 --> 00:52:19,490
что говорит вам это слово?

1028
00:52:19,490 --> 00:52:20,520
Разве это не слово?

1029
00:52:20,520 --> 00:52:23,240
И тогда у вас есть
Остальные массиве, что

1030
00:52:23,240 --> 00:52:26,040
на самом деле хранит все
Возможности, что это может быть.

1031
00:52:26,040 --> 00:52:28,660
Так, например, как
в верхней вас есть

1032
00:52:28,660 --> 00:52:32,140
Первое, что говорит правда или
ложь, да или нет, это слово.

1033
00:52:32,140 --> 00:52:38,130
>> И тогда у вас есть от 0 до 26
письма, которые вы можете хранить.

1034
00:52:38,130 --> 00:52:42,790
Если бы я хотел, чтобы поиск
для летучей мыши, я иду к вершине

1035
00:52:42,790 --> 00:52:49,200
и я смотрю на В. Я нахожу в моем B
массив, так что я знаю, хорошо, это B слово?

1036
00:52:49,200 --> 00:52:53,010
В это не то слово, так, таким образом,
Я должен продолжать поиски.

1037
00:52:53,010 --> 00:52:56,410
Я иду от B, и я с нетерпением к
указатель, который указывает на B

1038
00:52:56,410 --> 00:53:00,900
и я вижу еще один массив информации,
та же структура, что у нас было раньше.

1039
00:53:00,900 --> 00:53:05,240
>> И here-- ой, следующий
Письмо в [неразборчиво] это А.

1040
00:53:05,240 --> 00:53:07,210
Таким образом, мы с нетерпением в этом массиве.

1041
00:53:07,210 --> 00:53:10,860
Мы находим восьмой значение,
и тогда мы посмотрите, ох,

1042
00:53:10,860 --> 00:53:12,840
эй, это то, что словом, это В-А слово?

1043
00:53:12,840 --> 00:53:13,807
Это не слова.

1044
00:53:13,807 --> 00:53:14,890
Мы должны продолжать поиски.

1045
00:53:14,890 --> 00:53:17,850
>> И так, то мы смотрим, где
указатель А точек,

1046
00:53:17,850 --> 00:53:21,130
и это указывает на один способ,
которые у нас есть больше значения сохраняются.

1047
00:53:21,130 --> 00:53:24,150
И в конце концов, мы получаем
В-А-Т, которая является слово.

1048
00:53:24,150 --> 00:53:25,970
И поэтому в следующий раз
Вы посмотрите, что вы собираетесь

1049
00:53:25,970 --> 00:53:30,850
иметь, что проверку, да,
это булева функция является правдой.

1050
00:53:30,850 --> 00:53:35,450
И так в том смысле, мы вроде
наличия дерево с массивами.

1051
00:53:35,450 --> 00:53:39,890
>> Так, то вы можете рода поиск вниз.

1052
00:53:39,890 --> 00:53:43,650
Вместо того, чтобы хэширования функцию и
присвоение значения, связанного списка,

1053
00:53:43,650 --> 00:53:49,190
вы можете просто реализовать
Trie, что поиск downwords.

1054
00:53:49,190 --> 00:53:50,850
Действительно, действительно сложной вещи.

1055
00:53:50,850 --> 00:53:54,060
Не легко думать о, потому что я, как
плевки так много структур данных из

1056
00:53:54,060 --> 00:53:58,710
у вас, но делает все рода
понять, как логика это работает?

1057
00:53:58,710 --> 00:54:01,920
>> Ладно, круто.

1058
00:54:01,920 --> 00:54:05,600
Так B-A-T, а затем
Вы собираетесь искать.

1059
00:54:05,600 --> 00:54:07,940
В следующий раз вы собираетесь
чтобы видеть, о, эй, это правда,

1060
00:54:07,940 --> 00:54:09,273
Таким образом, я знаю, что это должно быть слово.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> То же самое для зоопарка.

1063
00:54:13,770 --> 00:54:17,960
Так вот в чем дело прямо сейчас, если мы
хотел искать зоопарке, прямо сейчас,

1064
00:54:17,960 --> 00:54:20,780
В настоящее время зоопарк не
слово в нашем словаре

1065
00:54:20,780 --> 00:54:25,300
потому что, как вы, ребята, можете видеть,
Первое место, что мы имеем логическое

1066
00:54:25,300 --> 00:54:28,590
возвращает истину в конце масштабирования.

1067
00:54:28,590 --> 00:54:30,430
У нас есть Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> И вот, мы на самом деле не имеют
слово, зоопарк, в нашем словаре

1069
00:54:33,900 --> 00:54:36,070
потому что этот флажок не установлен.

1070
00:54:36,070 --> 00:54:39,540
Таким образом, компьютер не
знаю, что зоопарк это слово

1071
00:54:39,540 --> 00:54:42,430
потому что путь, который мы
хранить его, только зум здесь

1072
00:54:42,430 --> 00:54:44,920
на самом деле имеет логическое значение
который был превращен правда.

1073
00:54:44,920 --> 00:54:49,380
Так что, если мы хотим, чтобы вставить
Слово, зоопарк, в нашем словаре,

1074
00:54:49,380 --> 00:54:51,770
как бы мы идти о том, что делать?

1075
00:54:51,770 --> 00:54:55,960
Что мы должны сделать, чтобы убедиться, что наши
компьютер знает, что Z-О-О слово

1076
00:54:55,960 --> 00:54:58,130
а не первое слово Z-О-О-М?

1077
00:54:58,130 --> 00:54:59,360
>> АУДИТОРИЯ: [неразборчиво]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Пэн: Ровно, мы
хотите, чтобы убедиться, что это

1079
00:55:01,450 --> 00:55:07,890
вот, что Логическое значение
галочка, что это правда.

1080
00:55:07,890 --> 00:55:13,297
Z-О-О, то мы собираемся проверить, что
так мы точно знаем, эй, зоопарк является слово.

1081
00:55:13,297 --> 00:55:15,380
Я собираюсь рассказать
компьютер, что это слово так

1082
00:55:15,380 --> 00:55:18,000
что, когда компьютер проверяет,
он знает, что зоопарк это слово.

1083
00:55:18,000 --> 00:55:21,269
>> Потому что помню все эти данные
структуры, это очень легко для нас

1084
00:55:21,269 --> 00:55:22,310
сказать, ой, летучая мышь это слово.

1085
00:55:22,310 --> 00:55:22,851
Зоопарк это слово.

1086
00:55:22,851 --> 00:55:23,611
Увеличить это слово.

1087
00:55:23,611 --> 00:55:25,860
Но когда вы строите его,
компьютер не имеет понятия.

1088
00:55:25,860 --> 00:55:28,619
>> Таким образом, вы должны сказать это точно
в какой момент это слово?

1089
00:55:28,619 --> 00:55:29,910
В какой момент это не слово?

1090
00:55:29,910 --> 00:55:31,784
И в какой момент я
нужно искать вещи,

1091
00:55:31,784 --> 00:55:34,000
и в какой момент мне нужно идти дальше?

1092
00:55:34,000 --> 00:55:37,010
Все ясно, из этого?

1093
00:55:37,010 --> 00:55:39,540
Круто.

1094
00:55:39,540 --> 00:55:42,530
>> И так потом приходит
Проблема как бы мы

1095
00:55:42,530 --> 00:55:45,560
идти о вставке то
что на самом деле нет?

1096
00:55:45,560 --> 00:55:49,090
Так что давайте просто сказать, что мы хотим, чтобы вставить
слово, ванна, в нашей синтаксического дерева.

1097
00:55:49,090 --> 00:55:53,589
Как вы, ребята, можете увидеть, как в настоящее время
все, что мы имеем сейчас, это В-А-Т,

1098
00:55:53,589 --> 00:55:55,630
и эта новая структура данных
есть имел пинту, что

1099
00:55:55,630 --> 00:55:59,740
указал на нуль, потому что мы считаем,
что, ох, нет никаких слов, после B-A-T,

1100
00:55:59,740 --> 00:56:02,530
почему мы должны держать
имея вещи после этого Т.

1101
00:56:02,530 --> 00:56:06,581
>> Но проблема возникает, если мы делаем вам
хотите иметь слово, которое приходит после

1102
00:56:06,581 --> 00:56:07,080
Т-х.

1103
00:56:07,080 --> 00:56:09,500
Если у вас есть ванна, вы
собирается хотите H права.

1104
00:56:09,500 --> 00:56:13,290
И так как мы собираемся сделать это
мы собираемся создать отдельный узел.

1105
00:56:13,290 --> 00:56:16,840
Мы не выделить любую сумму
памяти для этой новой массива,

1106
00:56:16,840 --> 00:56:20,720
и мы собираемся переназначить указатели.

1107
00:56:20,720 --> 00:56:22,947
>> Мы собираемся назначить
Н, В первую очередь, это нулевой,

1108
00:56:22,947 --> 00:56:24,030
мы собираемся избавиться.

1109
00:56:24,030 --> 00:56:26,590
Мы собираемся, чтобы иметь
Н точка вниз.

1110
00:56:26,590 --> 00:56:30,600
Если мы видим H, мы хотим его
идти куда-то еще.

1111
00:56:30,600 --> 00:56:33,910
>> Здесь, мы можем проверить с да.

1112
00:56:33,910 --> 00:56:38,170
Если мы попали в H после Т, о,
то мы знаем, что это слово.

1113
00:56:38,170 --> 00:56:41,110
Логическое собирается вернуться правда.

1114
00:56:41,110 --> 00:56:42,950
Все ясно, как это произошло?

1115
00:56:42,950 --> 00:56:45,110
ХОРОШО.

1116
00:56:45,110 --> 00:56:47,214
>> Так, по существу, все
эти структуры данных

1117
00:56:47,214 --> 00:56:50,130
что мы перешли сегодня, у меня
пошел на них очень, очень быстро

1118
00:56:50,130 --> 00:56:52,192
а не в гораздо
подробно, и это нормально.

1119
00:56:52,192 --> 00:56:53,900
Как только вы начинаете возиться
с ним, вы будете

1120
00:56:53,900 --> 00:56:55,733
отслеживать, где
все указатели,

1121
00:56:55,733 --> 00:56:58,060
что происходит в вашей
структуры данных, и так далее.

1122
00:56:58,060 --> 00:56:59,810
Они будут очень полезны,
и это до вас,

1123
00:56:59,810 --> 00:57:03,890
ребята, чтобы полностью понять, как
вы хотите реализовать вещи.

1124
00:57:03,890 --> 00:57:07,650
>> И так pset4, из 5-- ой, что это неправильно.

1125
00:57:07,650 --> 00:57:10,140
Pset5 является опечатками.

1126
00:57:10,140 --> 00:57:13,710
Как я уже говорил раньше, вы будете, когда-то
снова, скачать исходный код из нас.

1127
00:57:13,710 --> 00:57:16,210
Там будет три основных
вещи, которые вы будете загружать.

1128
00:57:16,210 --> 00:57:18,470
Вы скачать словари,
KERS, и тексты.

1129
00:57:18,470 --> 00:57:21,660
>> Все эти вещи являются
либо словари слов

1130
00:57:21,660 --> 00:57:25,190
что мы хотим, чтобы вы проверить
или испытание информации

1131
00:57:25,190 --> 00:57:26,930
что мы хотим, чтобы вы проверка орфографии.

1132
00:57:26,930 --> 00:57:29,670
И так словари
мы даем вам собираемся

1133
00:57:29,670 --> 00:57:34,870
чтобы дать вам конкретные слова, которые мы хотим
хранить как-то в способе, которым это

1134
00:57:34,870 --> 00:57:36,530
более эффективным, чем массив.

1135
00:57:36,530 --> 00:57:38,470
И тогда тексты
будет то, что мы

1136
00:57:38,470 --> 00:57:43,900
прошу вас проверить правописание, чтобы убедиться,
все слова есть реальные слова.

1137
00:57:43,900 --> 00:57:47,970
>> И так три блока
программы, которые мы дадим вам

1138
00:57:47,970 --> 00:57:51,130
называются dictionary.c,
dictionary.h и speller.c.

1139
00:57:51,130 --> 00:57:56,500
А так все делает, dictionary.c
то, что вы просили реализовать.

1140
00:57:56,500 --> 00:57:57,880
Он загружает слова.

1141
00:57:57,880 --> 00:58:02,000
Это заклинание проверяет их, и это гарантирует,
что все правильно вставлен.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h это просто файл библиотеки
который объявляет все эти функции.

1143
00:58:05,180 --> 00:58:07,650
И speller.c, мы собираемся дать вам.

1144
00:58:07,650 --> 00:58:09,290
Вам не нужно изменять любой из него.

1145
00:58:09,290 --> 00:58:14,290
Все speller.c делает это принять, что
загружает его, проверяет скорость его,

1146
00:58:14,290 --> 00:58:19,190
тестирует отметку в вроде как
быстро вы сможете сделать вещи.

1147
00:58:19,190 --> 00:58:20,410
>> Это пишущий.

1148
00:58:20,410 --> 00:58:23,920
Только не связывайтесь с ним, но сделать
что вы понимаете, что он делает.

1149
00:58:23,920 --> 00:58:28,090
Мы используем функцию под названием getrusage, что
тестирует производительность вашего заклинания

1150
00:58:28,090 --> 00:58:28,590
проверки.

1151
00:58:28,590 --> 00:58:32,200
Все это делает в основном протестировать
Время все в словаре,

1152
00:58:32,200 --> 00:58:33,680
поэтому убедитесь, что вы понимаете, что.

1153
00:58:33,680 --> 00:58:36,660
Будьте осторожны, чтобы не связываться с ним или
остальное все не будет работать должным образом.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> И большая часть этой проблемы является для
вы, ребята, действительно изменить dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Мы собираемся дать вам
140000 слов в словаре.

1157
00:58:48,526 --> 00:58:50,900
Мы собираемся дать вам текст
файл, который имеет те слова,

1158
00:58:50,900 --> 00:58:54,840
и мы хотим, чтобы вы могли организовать
их в хэш-таблице или синтаксического дерева

1159
00:58:54,840 --> 00:58:58,140
потому что, когда мы просим вас заклинание
check-- представьте себе, если вы заклинание

1160
00:58:58,140 --> 00:59:00,690
проверки, как Одиссея Гомера.

1161
00:59:00,690 --> 00:59:03,010
Это как этого огромной, огромной теста.

1162
00:59:03,010 --> 00:59:05,190
>> Представьте себе, если каждый
Слово, которое вы должны были искать

1163
00:59:05,190 --> 00:59:08,100
через массив 140000 значений.

1164
00:59:08,100 --> 00:59:10,350
Это будет длиться вечно
для вашей машины, чтобы бежать.

1165
00:59:10,350 --> 00:59:14,490
Именно поэтому мы хотим, чтобы организовать наши
данные в более эффективных структур данных

1166
00:59:14,490 --> 00:59:17,270
таких как хэш-таблицы или синтаксического дерева.

1167
00:59:17,270 --> 00:59:20,700
И тогда вы, ребята, можете вид
когда вы искать доступ

1168
00:59:20,700 --> 00:59:22,570
вещи более легко и более быстро.

1169
00:59:22,570 --> 00:59:24,934
>> И поэтому будьте осторожны, чтобы решить столкновений.

1170
00:59:24,934 --> 00:59:27,350
Вы собираетесь получить кучу
слов, которые начинаются с А.

1171
00:59:27,350 --> 00:59:29,957
Вы собираетесь получить кучу слов
которые начинаются с В. до вас

1172
00:59:29,957 --> 00:59:31,290
ребята, как вы хотите, чтобы решить ее.

1173
00:59:31,290 --> 00:59:34,144
Может быть, есть более
эффективность хэш-функция

1174
00:59:34,144 --> 00:59:36,810
чем просто первой букве
и то, и так, что до вас

1175
00:59:36,810 --> 00:59:38,190
ребята вроде делать все, что вы хотите.

1176
00:59:38,190 --> 00:59:40,148
>> Может быть, вы хотите, чтобы добавить
все буквы вместе.

1177
00:59:40,148 --> 00:59:43,410
Может быть, вы хотите, чтобы сделать нравится странные вещи
к ответственности ряд писем,

1178
00:59:43,410 --> 00:59:43,970
без разницы.

1179
00:59:43,970 --> 00:59:45,386
До вас, ребята, как вы хотите сделать.

1180
00:59:45,386 --> 00:59:49,262
Если вы хотите сделать хэш-таблицу, если вы
хочу попробовать синтаксического дерева, полностью зависит от вас.

1181
00:59:49,262 --> 00:59:52,470
Я предупреждаю вас заранее, что
Trie, как правило, немного сложнее

1182
00:59:52,470 --> 00:59:54,520
только потому, что есть много
больше указатели отслеживать.

1183
00:59:54,520 --> 00:59:55,645
Но полностью до вас, ребята.

1184
00:59:55,645 --> 00:59:58,742
Это гораздо более эффективно,
в большинстве случаев.

1185
00:59:58,742 --> 01:00:01,450
Вы хотите, чтобы действительно быть в состоянии держать
трек всех ваших указателей.

1186
01:00:01,450 --> 01:00:03,850
Как сделать то же самое
что я здесь делаю.

1187
01:00:03,850 --> 01:00:06,871
Когда вы пытаетесь вставить
значения в хэш-таблицу или удалить,

1188
01:00:06,871 --> 01:00:08,620
убедитесь, что вы
действительно отслеживания

1189
01:00:08,620 --> 01:00:11,860
где все, потому что
это действительно легко, если я

1190
01:00:11,860 --> 01:00:14,727
пытаюсь вставить, как слово, Энди.

1191
01:00:14,727 --> 01:00:16,810
Давайте просто скажем, что это
реальное слово, слово, Энди,

1192
01:00:16,810 --> 01:00:19,640
в гигантский список из слов.

1193
01:00:19,640 --> 01:00:22,450
>> Если я просто случайно переназначить
указатель так, ой,

1194
01:00:22,450 --> 01:00:24,940
там идет полноту
остальные моего связанного списка.

1195
01:00:24,940 --> 01:00:26,897
Теперь единственное слово я
есть Энди, и в настоящее время

1196
01:00:26,897 --> 01:00:29,230
все Другими словами в
Словари были потеряны.

1197
01:00:29,230 --> 01:00:31,370
И поэтому вы хотите, чтобы убедиться, что вы
отслеживать все ваши указатели

1198
01:00:31,370 --> 01:00:33,661
иначе вы собираетесь получить
огромные проблемы в коде.

1199
01:00:33,661 --> 01:00:35,840
Нарисуйте вещи тщательно, шаг за шагом.

1200
01:00:35,840 --> 01:00:37,870
Это делает его гораздо легче думать.

1201
01:00:37,870 --> 01:00:40,910
>> И, наконец, вы хотите, чтобы иметь возможность
проверить производительность вашей программы

1202
01:00:40,910 --> 01:00:41,618
на большой доске.

1203
01:00:41,618 --> 01:00:43,710
Если вы, ребята, взять
посмотреть на CS50 прямо сейчас,

1204
01:00:43,710 --> 01:00:45,210
у нас есть то, что называется большой совет.

1205
01:00:45,210 --> 01:00:50,200
Это оценка лист самый быстрый
Проверка орфографии раз по всем CS50

1206
01:00:50,200 --> 01:00:55,720
Прямо сейчас, я думаю, что верх как 10
Я думаю, что раз восемь из них являются сотрудниками.

1207
01:00:55,720 --> 01:00:57,960
Мы действительно хочу вас, ребята, чтобы бить нас.

1208
01:00:57,960 --> 01:01:00,870
>> Все из нас пытались реализовать
быстрый код, насколько это возможно.

1209
01:01:00,870 --> 01:01:04,880
Мы хотим, чтобы вы, ребята, чтобы попытаться оспорить
нам и осуществить быстрее, чем всех нас

1210
01:01:04,880 --> 01:01:05,550
Можно.

1211
01:01:05,550 --> 01:01:07,970
И так это действительно
первый раз, что мы

1212
01:01:07,970 --> 01:01:12,680
прошу вас, ребята, чтобы сделать PSET, что
Вы действительно можете сделать в любой метод

1213
01:01:12,680 --> 01:01:13,760
вы хотите.

1214
01:01:13,760 --> 01:01:17,730
>> Я всегда говорю, что это больше похоже
к решению реальных, верно?

1215
01:01:17,730 --> 01:01:19,550
Я говорю, эй, ты мне нужен, чтобы сделать это.

1216
01:01:19,550 --> 01:01:21,380
Построить программу, которая делает это для меня.

1217
01:01:21,380 --> 01:01:22,630
Сделайте это, как вы.

1218
01:01:22,630 --> 01:01:24,271
Я просто знаю, что я хочу, чтобы поститься.

1219
01:01:24,271 --> 01:01:25,770
Это ваша задача на этой неделе.

1220
01:01:25,770 --> 01:01:27,531
Вы, ребята, мы идем
чтобы дать вам задание.

1221
01:01:27,531 --> 01:01:29,030
Мы собираемся дать вам вызов.

1222
01:01:29,030 --> 01:01:31,559
И тогда это до вас, ребята
полностью только выяснить

1223
01:01:31,559 --> 01:01:34,100
что самый быстрый и самый
эффективный способ осуществить это.

1224
01:01:34,100 --> 01:01:34,600
Да?

1225
01:01:34,600 --> 01:01:37,476
>> АУДИТОРИЯ: Мы позволили, если
хотел исследовать быстрые способы

1226
01:01:37,476 --> 01:01:40,821
сделать хеш-таблицы на сайте, мы можем сделать
что и цитировать код чужое?

1227
01:01:40,821 --> 01:01:42,070
ANDI Пэн: Да, совершенно нормально.

1228
01:01:42,070 --> 01:01:44,320
Так что, если вы, ребята, читать
спецификации, есть линия

1229
01:01:44,320 --> 01:01:48,310
в спецификации сказано, что вы, ребята
полностью свободны исследовать хэш

1230
01:01:48,310 --> 01:01:51,070
функции на то, что некоторые
из быстрых хэш-функций

1231
01:01:51,070 --> 01:01:54,720
вести дела через в
Пока вы привести этот код.

1232
01:01:54,720 --> 01:01:57,220
Таким образом, некоторые люди уже
выяснили быстрых способов

1233
01:01:57,220 --> 01:02:00,250
делать проверку орфографии, быстрого
способы хранения информации.

1234
01:02:00,250 --> 01:02:02,750
Всего до вас, ребята, если вам
хочу просто взять, да?

1235
01:02:02,750 --> 01:02:04,045
Убедитесь, что вы цитирования.

1236
01:02:04,045 --> 01:02:06,170
Задача здесь действительно
что мы пытаемся проверить

1237
01:02:06,170 --> 01:02:09,750
убедившись, что вы знаете,
Ваш путь вокруг указатели.

1238
01:02:09,750 --> 01:02:12,700
Как далеко, как вы реализации
фактический хэш-функция

1239
01:02:12,700 --> 01:02:15,070
и, подойдя с подобным
математика, чтобы сделать это,

1240
01:02:15,070 --> 01:02:17,570
вы, ребята, можете исследовать все
методы онлайн вы, ребята, хотите.

1241
01:02:17,570 --> 01:02:17,996
Да?

1242
01:02:17,996 --> 01:02:19,700
>> АУДИТОРИЯ: Можем ли мы Приведу лишь
с помощью [неразборчиво]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Пэн: Да.

1244
01:02:20,120 --> 01:02:22,328
Вы можете просто в свой комментарий,
Вы можете цитировать, как, ну,

1245
01:02:22,328 --> 01:02:26,127
взяты из болтовня, болтовня,
йада, хэш-функция.

1246
01:02:26,127 --> 01:02:27,210
Кто-нибудь есть какие-либо вопросы?

1247
01:02:27,210 --> 01:02:29,694
Мы на самом деле веял
через раздел и сегодня.

1248
01:02:29,694 --> 01:02:31,610
Я буду сюда, чтобы
ответить на вопросы, а также.

1249
01:02:31,610 --> 01:02:36,570
>> Кроме того, как я сказал, офис
часов сегодня вечером и завтра.

1250
01:02:36,570 --> 01:02:40,307
Спецификация этой неделе на самом деле
супер просто и супер короткие читать.

1251
01:02:40,307 --> 01:02:43,140
Я хотел бы предложить взглянуть, просто
прочитать полностью от него.

1252
01:02:43,140 --> 01:02:45,730
>> И на самом деле Zamyla проведет вас
через каждую из функций

1253
01:02:45,730 --> 01:02:49,796
необходимо реализовать, и поэтому
очень, очень ясно, как все.

1254
01:02:49,796 --> 01:02:51,920
Просто убедитесь, что вы
отслеживание указателей.

1255
01:02:51,920 --> 01:02:53,650
Это очень сложная PSET.

1256
01:02:53,650 --> 01:02:56,744
>> Это не вызов, потому что, как,
о, понятия гораздо больше

1257
01:02:56,744 --> 01:02:59,160
трудно, или у вас есть, чтобы узнать,
столько нового синтаксиса путь

1258
01:02:59,160 --> 01:03:00,650
что вы сделали за последний PSET.

1259
01:03:00,650 --> 01:03:03,320
Это PSET трудно, потому что
Есть так много указателей,

1260
01:03:03,320 --> 01:03:06,980
и то это очень, очень легко сразу
у вас есть ошибка в коде не сможет

1261
01:03:06,980 --> 01:03:08,315
чтобы найти, где что ошибка есть.

1262
01:03:08,315 --> 01:03:13,200
>> И так полное и абсолютное вера в вас
ребята, чтобы иметь возможность победить нашу [неразборчиво]

1263
01:03:13,200 --> 01:03:13,700
Написание.

1264
01:03:13,700 --> 01:03:16,640
Я на самом деле не какой-либо письменное шахту
пока нет, но я собираюсь написать мой.

1265
01:03:16,640 --> 01:03:19,070
Поэтому, когда вы пишете
твое, я буду писать мои.

1266
01:03:19,070 --> 01:03:21,070
Я собираюсь попытаться сделать
мой быстрее, чем ваша.

1267
01:03:21,070 --> 01:03:23,940
Мы увидим, кто имеет самый быстрый один.

1268
01:03:23,940 --> 01:03:27,340
>> И да, я буду видеть все
вы, ребята, здесь во вторник.

1269
01:03:27,340 --> 01:03:29,510
Я побегу вид вроде мастерской Pset.

1270
01:03:29,510 --> 01:03:32,640
Все это разделах
неделе, Pset семинары,

1271
01:03:32,640 --> 01:03:36,690
так что вы, ребята, есть много возможностей
за помощью, часы работы, как всегда,

1272
01:03:36,690 --> 01:03:41,330
и я действительно с нетерпением жду
читать весь код ваши ребята.

1273
01:03:41,330 --> 01:03:44,160
У меня есть тесты здесь если вы
ребята, хотите приехать получить те.

1274
01:03:44,160 --> 01:03:45,880
Вот и все.

1275
01:03:45,880 --> 01:03:48,180