1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> Выступающий 1: Все в порядке, так что мы вернулись.

3
00:00:13,120 --> 00:00:14,480
Добро пожаловать в CS50.

4
00:00:14,480 --> 00:00:16,510
Это конец недели семь.

5
00:00:16,510 --> 00:00:20,200
Поэтому напомним, что в прошлый раз, мы начали
глядя на несколько более сложно

6
00:00:20,200 --> 00:00:21,100
структур данных.

7
00:00:21,100 --> 00:00:25,110
Так как до сих пор, все, что мы были действительно
В нашем распоряжении было этого, массив.

8
00:00:25,110 --> 00:00:29,340
>> Но прежде чем отбросить массив как не
все, что интересно, что это действительно так

9
00:00:29,340 --> 00:00:33,570
на самом деле, то, что некоторые из
Плюсы этого простого данных

10
00:00:33,570 --> 00:00:34,560
структуры до сих пор?

11
00:00:34,560 --> 00:00:36,110
Каково это хорошо?

12
00:00:36,110 --> 00:00:39,450
До сих пор, как мы видели?

13
00:00:39,450 --> 00:00:42,540
Что у тебя?

14
00:00:42,540 --> 00:00:44,028
Ничего.

15
00:00:44,028 --> 00:00:45,020
>> СТУДЕНТ: [неразборчиво].

16
00:00:45,020 --> 00:00:45,395
>> Выступающий 1: Что это?

17
00:00:45,395 --> 00:00:46,410
>> СТУДЕНТ: [неразборчиво].

18
00:00:46,410 --> 00:00:47,000
>> Выступающий 1: фиксированный размер.

19
00:00:47,000 --> 00:00:51,260
Итак, почему фиксированный размер хороший, хотя?

20
00:00:51,260 --> 00:00:53,180
>> СТУДЕНТ: [неразборчиво].

21
00:00:53,180 --> 00:00:56,240
>> Выступающий 1: Хорошо, так что это эффективно в
том смысле, что вы можете выделить

22
00:00:56,240 --> 00:01:00,070
Фиксированная сумма в пространстве, которое, мы надеемся,
Именно столько

23
00:01:00,070 --> 00:01:01,180
пространства, как вы хотите.

24
00:01:01,180 --> 00:01:02,720
Так что может быть абсолютно плюс.

25
00:01:02,720 --> 00:01:06,530
>> Что еще по одной стороне массива?

26
00:01:06,530 --> 00:01:07,610
Да?

27
00:01:07,610 --> 00:01:08,750
>> СТУДЕНТ: [неразборчиво].

28
00:01:08,750 --> 00:01:09,550
>> Выступающий 1: Все - Простите?

29
00:01:09,550 --> 00:01:11,270
>> СТУДЕНТ: [неразборчиво].

30
00:01:11,270 --> 00:01:13,620
>> Выступающий 1: Все коробки в памяти
или рядом друг с другом.

31
00:01:13,620 --> 00:01:15,220
И это полезно - почему?

32
00:01:15,220 --> 00:01:15,970
Совершенно верно.

33
00:01:15,970 --> 00:01:18,611
Но как мы можем использовать это правда?

34
00:01:18,611 --> 00:01:21,500
>> СТУДЕНТ: [неразборчиво].

35
00:01:21,500 --> 00:01:24,490
>> Выступающий 1: Точно, мы можем отслеживать
, где все просто, зная,

36
00:01:24,490 --> 00:01:28,560
один адрес, а именно, адреса
Первый байт, что блок памяти.

37
00:01:28,560 --> 00:01:30,420
Или в случае строки,
адрес первого

38
00:01:30,420 --> 00:01:31,460
символ в этой строке.

39
00:01:31,460 --> 00:01:33,330
А оттуда, мы можем найти
конца строки.

40
00:01:33,330 --> 00:01:35,710
Мы можем найти второй элемент,
третий элемент, и так далее.

41
00:01:35,710 --> 00:01:38,740
>> И таким причудливым способом описания, что
особенность в том, что массивы дают нам

42
00:01:38,740 --> 00:01:40,020
произвольным доступом.

43
00:01:40,020 --> 00:01:44,330
Просто с помощью квадратных скобок
обозначения и номера, вы можете перейти к

44
00:01:44,330 --> 00:01:48,070
конкретного элемента в массиве
за постоянное время, Big O

45
00:01:48,070 --> 00:01:49,810
одного, так сказать.

46
00:01:49,810 --> 00:01:51,080
>> Но есть некоторые минусы.

47
00:01:51,080 --> 00:01:53,110
Что массив не делать очень легко?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Что это не очень хорошо?

50
00:01:57,170 --> 00:01:58,810
>> СТУДЕНТ: [неразборчиво].

51
00:01:58,810 --> 00:01:59,860
>> Выступающий 1: Что это?

52
00:01:59,860 --> 00:02:00,530
>> СТУДЕНТ: [неразборчиво].

53
00:02:00,530 --> 00:02:01,460
>> Выступающий 1: Расширение в размерах.

54
00:02:01,460 --> 00:02:04,800
Таким образом, недостатки массива
точно противоположное тому, что

55
00:02:04,800 --> 00:02:05,540
расквитаться есть.

56
00:02:05,540 --> 00:02:07,610
Поэтому одним из недостатков является
что это фиксированный размер.

57
00:02:07,610 --> 00:02:09,400
Таким образом, вы не можете реально вырастить его.

58
00:02:09,400 --> 00:02:13,510
Вы можете перераспределить больший кусок
памяти, а затем переместите старый элементы

59
00:02:13,510 --> 00:02:14,460
в новый массив.

60
00:02:14,460 --> 00:02:18,060
, А затем освободить старого массива, для
Например, при использовании таНос или аналогичного

61
00:02:18,060 --> 00:02:21,180
Функция называется Realloc, которая
перераспределяет память.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, как в сторону, пытается дать вам
памяти, что это рядом с массивом

63
00:02:25,490 --> 00:02:26,610
что вы уже имеете.

64
00:02:26,610 --> 00:02:28,740
Но это может перемещать предметы
вокруг в целом.

65
00:02:28,740 --> 00:02:30,710
Но в общем, что дорого, не так ли?

66
00:02:30,710 --> 00:02:33,440
Потому что, если у вас есть кусок памяти
такого размера, но вы действительно хотите один

67
00:02:33,440 --> 00:02:36,710
такого размера, и вы хотите сохранить
оригинальные элементы, у вас есть

68
00:02:36,710 --> 00:02:40,510
примерно линейный процесс копирования время
что должно произойти от

69
00:02:40,510 --> 00:02:41,900
старого массива на новый.

70
00:02:41,900 --> 00:02:44,630
А реальность такова просят операционной
Система снова и снова и

71
00:02:44,630 --> 00:02:48,340
снова на большие куски памяти может начаться
стоить вам некоторое время, а также.

72
00:02:48,340 --> 00:02:52,250
Так что это как благословение и проклятие в
замаскировать тот факт, что эти массивы

73
00:02:52,250 --> 00:02:53,860
имеют фиксированный размер.

74
00:02:53,860 --> 00:02:56,790
Но если ввести вместо что-то
как это, которое мы назвали связанного

75
00:02:56,790 --> 00:03:00,580
список, мы получаем несколько плюсы и
несколько недостатков и здесь.

76
00:03:00,580 --> 00:03:05,780
>> Так связанный список просто данные
структура, состоящая из структур C в этом

77
00:03:05,780 --> 00:03:09,850
случае, когда структура, напомним, является просто
контейнер для одного или более конкретных

78
00:03:09,850 --> 00:03:11,100
типы переменных.

79
00:03:11,100 --> 00:03:16,110
В этом случае, что же типы данных
видимому, внутри структуры, который

80
00:03:16,110 --> 00:03:17,600
Последний раз мы называется узлом?

81
00:03:17,600 --> 00:03:19,380
Каждый из этих прямоугольников узла.

82
00:03:19,380 --> 00:03:22,660
И каждый из меньших прямоугольников
Внутри это тип данных.

83
00:03:22,660 --> 00:03:25,300
Какие же тогда мы говорили
они были в понедельник?

84
00:03:25,300 --> 00:03:26,478
Да?

85
00:03:26,478 --> 00:03:27,870
>> СТУДЕНТ: [неразборчиво].

86
00:03:27,870 --> 00:03:30,721
>> Выступающий 1: переменные и указатель, или
точнее, целое для N,

87
00:03:30,721 --> 00:03:32,180
и указатель на дне.

88
00:03:32,180 --> 00:03:35,360
Оба эти, оказывается, 32 бита, по крайней
мере на компьютере, как это CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, и поэтому они
обращается одинаково в размере.

90
00:03:37,980 --> 00:03:42,260
>> Так что с помощью указателя
хотя для по-видимому?

91
00:03:42,260 --> 00:03:47,690
Зачем добавлять эту стрелку теперь, когда массивы, были
так хорошо и чисто и просто?

92
00:03:47,690 --> 00:03:50,460
Что делаете для указателя
нами в каждом из этих узлов?

93
00:03:50,460 --> 00:03:52,160
>> СТУДЕНТ: [неразборчиво].

94
00:03:52,160 --> 00:03:52,465
>> Выступающий 1: Совершенно верно.

95
00:03:52,465 --> 00:03:54,120
Это говорит вам, где
далее идет.

96
00:03:54,120 --> 00:03:57,350
Так что я, конечно, использовать аналогию
использованием потока к виду

97
00:03:57,350 --> 00:03:59,180
нить эти узлы вместе.

98
00:03:59,180 --> 00:04:01,760
И это именно то, что мы делаем с
указателей, поскольку каждый из этих

99
00:04:01,760 --> 00:04:06,360
участков памяти может или не может быть
смежные, спина к спине к спине

100
00:04:06,360 --> 00:04:09,500
внутри оперативной памяти, потому что каждый раз, когда вы
позвоните Malloc говорят: дай мне достаточно

101
00:04:09,500 --> 00:04:12,510
байтов для нового узла, он может
быть здесь, или он может быть здесь.

102
00:04:12,510 --> 00:04:13,120
Это могло бы быть здесь.

103
00:04:13,120 --> 00:04:13,730
Это могло бы быть здесь.

104
00:04:13,730 --> 00:04:14,640
Вы просто не знаю.

105
00:04:14,640 --> 00:04:17,880
>> Но с помощью указателей в адресах
эти узлы, вы можете сшить их

106
00:04:17,880 --> 00:04:22,370
вместе таким образом, что визуально выглядит
как список, даже если эти вещи

107
00:04:22,370 --> 00:04:26,770
все распространены на протяжении всего одного или
Ваши два или ваши четыре гигабайта оперативной памяти

108
00:04:26,770 --> 00:04:28,760
внутри вашего собственного компьютера.

109
00:04:28,760 --> 00:04:33,230
>> Таким образом, недостаток, то,
Связанный список есть что?

110
00:04:33,230 --> 00:04:34,670
Что такое цена, что мы
видимо платить?

111
00:04:34,670 --> 00:04:36,010
>> СТУДЕНТ: [неразборчиво].

112
00:04:36,010 --> 00:04:36,920
>> Выступающий 1: Больше места, не так ли?

113
00:04:36,920 --> 00:04:39,340
Мы, в данном случае, удвоил сумму
пространства, потому что мы прошли

114
00:04:39,340 --> 00:04:43,500
с 32 бит для каждого узла, для каждого
Интеллект, так что теперь 64 бита, потому что мы должны

115
00:04:43,500 --> 00:04:45,050
держать вокруг указателя, а также.

116
00:04:45,050 --> 00:04:48,860
Вы получаете больше эффективности, если вашей структуры
больше, чем эта простая вещь.

117
00:04:48,860 --> 00:04:52,020
Если у вас действительно есть внутри студента
из которых представляет собой пару строк для

118
00:04:52,020 --> 00:04:55,430
имя и дом, может быть, номер удостоверения личности,
возможно, некоторые другие области в целом.

119
00:04:55,430 --> 00:04:59,000
>> Так что если у вас есть достаточно большая структура,
то, возможно, стоимость указатель

120
00:04:59,000 --> 00:05:00,010
Не такое уж большое дело.

121
00:05:00,010 --> 00:05:03,570
Это немного из угла в этом случае
мы сохраняем такие простые примитивные

122
00:05:03,570 --> 00:05:04,760
внутрь связанного списка.

123
00:05:04,760 --> 00:05:05,790
Но суть та же.

124
00:05:05,790 --> 00:05:08,230
Вы определенно тратить больше
памяти, но вы получаете

125
00:05:08,230 --> 00:05:08,990
гибкость.

126
00:05:08,990 --> 00:05:12,280
Потому что теперь, если я хочу добавить элемент
В начале этого списка,

127
00:05:12,280 --> 00:05:14,340
Я должен выделить новый узел.

128
00:05:14,340 --> 00:05:17,180
И я должен просто обновить эти
Стрелки как-то просто перемещение

129
00:05:17,180 --> 00:05:17,980
некоторые указатели вокруг.

130
00:05:17,980 --> 00:05:20,580
>> Если я хочу, чтобы вставить что-то в
середине списка, я не придется

131
00:05:20,580 --> 00:05:24,410
толкать в сторону все, что мы сделали в
недель прошлое с нашим добровольцам, которые

132
00:05:24,410 --> 00:05:25,700
представлена ​​массивом.

133
00:05:25,700 --> 00:05:29,470
Я могу просто выделить новый узел и
Затем просто указать стрелками на

134
00:05:29,470 --> 00:05:32,290
разных направлениях, поскольку она не
должны оставаться в фактическом

135
00:05:32,290 --> 00:05:35,670
памяти истинных линии, как я нарисовал
его здесь на экране.

136
00:05:35,670 --> 00:05:38,400
>> А потом, наконец, если вы хотите вставить
то в конце списка, это

137
00:05:38,400 --> 00:05:39,210
еще проще.

138
00:05:39,210 --> 00:05:43,320
Это своего рода произвольные обозначения,
но в 34 указателей, сделать предположение.

139
00:05:43,320 --> 00:05:46,710
Что такое значение его указателя наиболее
вероятно, обращается вроде как старые

140
00:05:46,710 --> 00:05:47,700
школе есть антенна?

141
00:05:47,700 --> 00:05:48,920
>> СТУДЕНТ: [неразборчиво].

142
00:05:48,920 --> 00:05:49,900
>> Выступающий 1: Это, вероятно, нулевым.

143
00:05:49,900 --> 00:05:52,710
И в самом деле, что является одним автора
представление нулевой.

144
00:05:52,710 --> 00:05:56,310
И это нуль, потому что вы абсолютно
нужно знать, где к концу связанного

145
00:05:56,310 --> 00:06:00,050
список, чтобы вы продолжаете после и
после и после этих стрелок

146
00:06:00,050 --> 00:06:01,170
некоторым мусором значения.

147
00:06:01,170 --> 00:06:06,230
Так нулевых не будет означать, что нет никакой
более узлов справа от числа 34,

148
00:06:06,230 --> 00:06:07,200
в этом случае.

149
00:06:07,200 --> 00:06:10,270
>> Поэтому мы полагаем, что мы можем реализовать
этот узел в коде.

150
00:06:10,270 --> 00:06:12,130
И мы видели такую
синтаксиса раньше.

151
00:06:12,130 --> 00:06:15,090
Typedef просто определяет новый тип для
нас, дает нам как синоним

152
00:06:15,090 --> 00:06:17,100
Строка была для символ *.

153
00:06:17,100 --> 00:06:21,030
В этом случае, он собирается дать нам
сокращенную запись, так что структура узла

154
00:06:21,030 --> 00:06:24,010
Вместо этого можно просто быть записана в виде
узел, который является намного более чистой.

155
00:06:24,010 --> 00:06:25,360
Это гораздо менее многословным.

156
00:06:25,360 --> 00:06:30,080
>> Внутри узла видимому Целочисленное
называется п, а затем структуры узла *

157
00:06:30,080 --> 00:06:34,670
что означает именно то, что мы хотели
Стрелки в виду, указатель на другой

158
00:06:34,670 --> 00:06:36,940
узел точно такой же тип данных.

159
00:06:36,940 --> 00:06:40,300
И я предлагаю, чтобы мы могли реализовать
Функция поиска, как это, которое в

160
00:06:40,300 --> 00:06:41,890
первый взгляд может показаться,
немного сложным.

161
00:06:41,890 --> 00:06:43,330
Но давайте посмотрим его в контексте.

162
00:06:43,330 --> 00:06:45,480
>> Позвольте мне перейти к прибору здесь.

163
00:06:45,480 --> 00:06:48,460
Позвольте мне открыть файл с именем
Список нулю точка ч.

164
00:06:48,460 --> 00:06:53,950
И что только содержит определение мы
только что видели минуту назад для этих данных

165
00:06:53,950 --> 00:06:55,390
тип называется узлом.

166
00:06:55,390 --> 00:06:57,350
Поэтому мы ввели, что в файл точка ч.

167
00:06:57,350 --> 00:07:01,430
>> И, как в стороне, хотя это
программа, которую вы собираетесь, чтобы увидеть это

168
00:07:01,430 --> 00:07:05,410
не все, что комплекс, это действительно
Конвенции при написании программы

169
00:07:05,410 --> 00:07:10,270
положить вещи, как типы данных, тянуть
Константы иногда, внутри вашего

170
00:07:10,270 --> 00:07:13,210
заголовок файла, а не обязательно в
С вашего файла, конечно же, когда ваш

171
00:07:13,210 --> 00:07:17,370
программ получить больше и больше, так что
Вы знаете, где искать, как для

172
00:07:17,370 --> 00:07:20,840
документации в некоторых случаях или
для основы, как это,

173
00:07:20,840 --> 00:07:22,360
определение некоторого типа.

174
00:07:22,360 --> 00:07:25,680
>> Если бы я сейчас открыть список нулю точка
C, заметить несколько вещей.

175
00:07:25,680 --> 00:07:29,090
Она включает в себя несколько файлов заголовка, большинство
которого мы видели раньше.

176
00:07:29,090 --> 00:07:31,980
Она включает в себя свой собственный файл заголовка.

177
00:07:31,980 --> 00:07:35,200
>> И, как в стороне, почему это двойная
котировки здесь, в отличие от угла

178
00:07:35,200 --> 00:07:38,340
кронштейны на линии, которая
Я выделил там?

179
00:07:38,340 --> 00:07:39,180
>> СТУДЕНТ: [неразборчиво].

180
00:07:39,180 --> 00:07:40,460
>> Выступающий 1: Да, так что это локальный файл.

181
00:07:40,460 --> 00:07:44,300
Так что, если это локальный файл собственного здесь
на линии 15, например, вы используете

182
00:07:44,300 --> 00:07:46,570
двойные кавычки вместо
в угловые скобки.

183
00:07:46,570 --> 00:07:48,270
>> Теперь это отчасти интересно.

184
00:07:48,270 --> 00:07:51,830
Обратите внимание, что я объявил глобальную
переменной в этой программе в строке 18

185
00:07:51,830 --> 00:07:55,910
называется первой, идея в том, что это
будет указатель на первый

186
00:07:55,910 --> 00:07:59,190
узел в моем связанный список, а я
инициализировать его к нулю, потому, что я

187
00:07:59,190 --> 00:08:02,310
не выделяется каких-либо фактических
узлы только пока.

188
00:08:02,310 --> 00:08:07,570
>> Так что это представляет, графически, то, что мы
увидел минуту назад на картинке как

189
00:08:07,570 --> 00:08:10,090
что указатель на Дальнем
с левой стороны.

190
00:08:10,090 --> 00:08:12,260
Так что сейчас, что указатель
не имеет стрелки.

191
00:08:12,260 --> 00:08:14,590
Вместо этого он просто нулевой.

192
00:08:14,590 --> 00:08:17,880
Но он представляет, какой будет
адрес первого фактического

193
00:08:17,880 --> 00:08:19,480
узла в этом списке.

194
00:08:19,480 --> 00:08:22,120
Так я реализовал это глобальная
потому что, как вы увидите, все это

195
00:08:22,120 --> 00:08:25,310
Программа делает в жизни, это реализовать
связанный список для меня.

196
00:08:25,310 --> 00:08:27,050
>> Теперь у меня есть несколько прототипов здесь.

197
00:08:27,050 --> 00:08:31,190
Я решил реализовать функции, такие как
делеции, вставки, поиска и

198
00:08:31,190 --> 00:08:31,740
обхода -

199
00:08:31,740 --> 00:08:35,210
Последний просто быть прогулка через
Список, распечатав ее элементов.

200
00:08:35,210 --> 00:08:36,750
А теперь вот мой основной программе.

201
00:08:36,750 --> 00:08:39,890
И мы не будем тратить слишком много времени на
это, так как это является своего рода, мы надеемся,

202
00:08:39,890 --> 00:08:41,780
старая шляпа к настоящему времени.

203
00:08:41,780 --> 00:08:45,370
>> Я собираюсь сделать следующее,
в то время как пользователь взаимодействует.

204
00:08:45,370 --> 00:08:47,300
Так что, я собираюсь печатать
из этого меню.

205
00:08:47,300 --> 00:08:49,420
И я отформатировал его в качестве
чисто, как я мог.

206
00:08:49,420 --> 00:08:52,240
Если пользователь вводит в одном, то есть
они хотят, чтобы удалить что-нибудь.

207
00:08:52,240 --> 00:08:54,560
Если пользователь введет в двух, это означает, что
они хотят, чтобы вставить что-то.

208
00:08:54,560 --> 00:08:55,930
И так далее.

209
00:08:55,930 --> 00:08:58,270
Я собираюсь потом подскажут
Тогда для команды.

210
00:08:58,270 --> 00:08:59,300
А потом я собираюсь использовать GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Так что это действительно просто menuing
интерфейс, где вы просто должны ввести

212
00:09:02,790 --> 00:09:05,270
число отображение одного
из этих команд.

213
00:09:05,270 --> 00:09:08,730
И теперь у меня есть хорошая чистая переключатель
заявление, что собирается включить

214
00:09:08,730 --> 00:09:10,090
любой пользователь ввели дюйма

215
00:09:10,090 --> 00:09:12,180
И если они набрали одно, я буду
вызове удаления и ломаться.

216
00:09:12,180 --> 00:09:14,380
Если они ввели два, я буду
позвоните вставить и ломаться.

217
00:09:14,380 --> 00:09:16,490
>> А теперь обратите внимание я поместил каждого
из них на той же линии.

218
00:09:16,490 --> 00:09:18,360
Это всего лишь стилистическое решение.

219
00:09:18,360 --> 00:09:20,210
Обычно мы видели что-то
как это.

220
00:09:20,210 --> 00:09:23,260
Но я просто решил, честно говоря, моя программа
выглядел более для чтения, так

221
00:09:23,260 --> 00:09:25,980
это было только четыре случая
просто перечислить это так.

222
00:09:25,980 --> 00:09:28,360
Полностью законное использование стиля.

223
00:09:28,360 --> 00:09:31,480
И я буду делать это так долго, как
Пользователь не набрала нулю, что я

224
00:09:31,480 --> 00:09:33,910
решено будет означать, что они хотят бросить курить.

225
00:09:33,910 --> 00:09:36,630
>> Так что теперь замечаю, что я
будем делать здесь.

226
00:09:36,630 --> 00:09:38,650
Я собираюсь освободить списке по-видимому.

227
00:09:38,650 --> 00:09:40,230
Но об этом через минуту.

228
00:09:40,230 --> 00:09:41,640
Давайте сначала запустить эту программу.

229
00:09:41,640 --> 00:09:45,250
Итак, позвольте мне сделать больший терминал
окна, точка слэш список 0.

230
00:09:45,250 --> 00:09:49,510
Я собираюсь идти вперед и вставляйте их
набрав два, как число 50, а теперь

231
00:09:49,510 --> 00:09:51,590
Вы увидите список теперь на 50.

232
00:09:51,590 --> 00:09:53,380
И мой текст, просто прокручивается немного.

233
00:09:53,380 --> 00:09:55,940
Так что теперь Обратите внимание на список содержит
число 50.

234
00:09:55,940 --> 00:09:58,220
>> Давайте еще вставкой, взяв два.

235
00:09:58,220 --> 00:10:01,630
Давайте введите номер, как один.

236
00:10:01,630 --> 00:10:03,940
Список является одной, а затем 50.

237
00:10:03,940 --> 00:10:06,020
Так что это просто текстовое представление
списка.

238
00:10:06,020 --> 00:10:10,550
И давайте вставим еще один номер, как
номер 42, который с надеждой

239
00:10:10,550 --> 00:10:14,620
будет в конечном итоге в середине, потому что
этой программы, в частности, сортирует его

240
00:10:14,620 --> 00:10:16,320
элементы, как он вставляет их.

241
00:10:16,320 --> 00:10:17,220
Так что у нас это есть.

242
00:10:17,220 --> 00:10:20,730
Супер просто программу, которая может
Абсолютно использовали множество, но я

243
00:10:20,730 --> 00:10:23,280
, случается, используют связанный список
именно так я могу динамически

244
00:10:23,280 --> 00:10:24,610
увеличиваются и уменьшаются его.

245
00:10:24,610 --> 00:10:28,470
>> Итак, давайте взглянем на поиски, если я
запустить команду три, я хочу поиску

246
00:10:28,470 --> 00:10:31,040
, скажем, числа 43.

247
00:10:31,040 --> 00:10:34,190
И ничего не было найдено по-видимому,
потому что я не вернулся без ответа.

248
00:10:34,190 --> 00:10:35,010
Итак, давайте сделаем это снова.

249
00:10:35,010 --> 00:10:35,690
Поиск.

250
00:10:35,690 --> 00:10:39,520
Давайте искать для 50, или, скорее, поиск
для 42, у которого есть хорошая

251
00:10:39,520 --> 00:10:40,850
почти неуловимая смысл.

252
00:10:40,850 --> 00:10:42,610
И я нашел смысл жизни там.

253
00:10:42,610 --> 00:10:44,990
Число 42, если вы не знаете,
ссылки Поиск в Интернете.

254
00:10:44,990 --> 00:10:45,350
Хорошо.

255
00:10:45,350 --> 00:10:47,130
Так, что эта программа для меня сделал?

256
00:10:47,130 --> 00:10:50,660
Это просто позволил мне вставить таким образом,
далеко и поиск элементов.

257
00:10:50,660 --> 00:10:53,650
>> Давай вперед, то, чтобы
функции, мы взглянул на

258
00:10:53,650 --> 00:10:55,360
в понедельник, как дразнилка.

259
00:10:55,360 --> 00:10:59,620
Так что эта функция, я утверждаю, ищет
элемента в списке по первым

260
00:10:59,620 --> 00:11:03,830
одна, предлагая пользователю с последующим вызовом
GetInt, чтобы получить фактические десятичного

261
00:11:03,830 --> 00:11:05,060
что вы хотите найти.

262
00:11:05,060 --> 00:11:06,460
>> Потом заметил этого.

263
00:11:06,460 --> 00:11:10,690
Я собираюсь создать временную переменную
В линии 188 называется указателем -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
мог бы назвать ее как угодно.

266
00:11:12,440 --> 00:11:16,140
И это указатель на узле
потому что Я сказал узла * там.

267
00:11:16,140 --> 00:11:19,900
И я инициализации равным
первый, так что я эффективно мое

268
00:11:19,900 --> 00:11:22,860
пальца, так сказать, на самом
Первый элемент списка.

269
00:11:22,860 --> 00:11:27,460
Так что, если моя правая рука здесь PTR Я
указывая на то же самое, что первый

270
00:11:27,460 --> 00:11:28,670
указывает на.

271
00:11:28,670 --> 00:11:31,430
>> Так что теперь еще в коде,
что будет дальше -

272
00:11:31,430 --> 00:11:35,070
это общая парадигма при переборе
по структуре, как

273
00:11:35,070 --> 00:11:35,970
связанный список.

274
00:11:35,970 --> 00:11:40,410
Я собираюсь сделать следующее в то время как
указатель не равен нулю Таким образом, хотя

275
00:11:40,410 --> 00:11:47,530
мой палец не указывает на некоторые нулевым
стоимости, если стрелка указателя N равно N.

276
00:11:47,530 --> 00:11:52,290
Мы заметили, что первые N является то, что
пользователь вводит в GetInts называю здесь.

277
00:11:52,290 --> 00:11:54,280
>> И стрелка указателя N означает, что?

278
00:11:54,280 --> 00:11:59,020
Ну, если мы вернемся к картины здесь,
есть ли у меня пальцем, указывая на

279
00:11:59,020 --> 00:12:02,960
что первый узел, содержащий девять,
стрелки по существу означает, что перейти к

280
00:12:02,960 --> 00:12:08,860
узла и захватить значение в точке N,
В этом случае, поле данных называется н.

281
00:12:08,860 --> 00:12:14,120
>> Как в сторону - и мы увидели эту пару
недель назад, когда кто-то спросил -

282
00:12:14,120 --> 00:12:18,840
этот синтаксис является новой, но это не так
дать нам силы, которые мы

283
00:12:18,840 --> 00:12:20,040
уже не было.

284
00:12:20,040 --> 00:12:25,325
Что это за фраза эквивалентно использованию
точечной нотации и звезда пара

285
00:12:25,325 --> 00:12:29,490
недель назад, когда мы очищенные назад
этот слой немного преждевременно?

286
00:12:29,490 --> 00:12:31,780
>> СТУДЕНТ: [неразборчиво].

287
00:12:31,780 --> 00:12:38,880
>> Выступающий 1: Точно, это была звезда, и
тогда это была звезда точкой N, с

288
00:12:38,880 --> 00:12:41,930
Здесь скобки, который выглядит,
честно говоря, я думаю, что много

289
00:12:41,930 --> 00:12:43,320
более загадочные читать.

290
00:12:43,320 --> 00:12:46,270
Но указатель звезды, как всегда,
средства идут туда.

291
00:12:46,270 --> 00:12:49,090
И как только вы там, какие данные
поля вы хотите получить доступ?

292
00:12:49,090 --> 00:12:52,730
Ну вы используют точку доступа к
поля структур данных, и я

293
00:12:52,730 --> 00:12:54,140
специально хотят н.

294
00:12:54,140 --> 00:12:56,240
>> Честно говоря, я бы сказал, это
просто трудно читать.

295
00:12:56,240 --> 00:12:58,080
Это сложнее вспомнить, где
сделать скобках идти,

296
00:12:58,080 --> 00:12:59,030
звезда и все такое.

297
00:12:59,030 --> 00:13:02,150
Таким образом, мир принял некоторые синтаксические
сахар, так сказать.

298
00:13:02,150 --> 00:13:04,740
Просто сексуально способ сказать,
это эквивалентно, а также

299
00:13:04,740 --> 00:13:05,970
возможно, более интуитивным.

300
00:13:05,970 --> 00:13:09,600
Если указатель действительно является указателем,
средств стрелки обозначения пойти туда и найти

301
00:13:09,600 --> 00:13:11,890
поля в этом случае называются N.

302
00:13:11,890 --> 00:13:13,660
>> Так что, если я нахожу это, заметьте, что я делаю.

303
00:13:13,660 --> 00:13:17,430
Я просто распечатать, я обнаружил, я процентов,
подключение значение для этого Int.

304
00:13:17,430 --> 00:13:20,730
Я называю спать в течение одной секунды просто вид
паузы вещи на экране, чтобы

305
00:13:20,730 --> 00:13:22,900
дать пользователю второй поглощать
что только что произошло.

306
00:13:22,900 --> 00:13:24,290
И тогда я нарушу.

307
00:13:24,290 --> 00:13:26,330
В противном случае, что мне делать?

308
00:13:26,330 --> 00:13:30,960
Обновить указатель на равных
указателя стрелки рядом.

309
00:13:30,960 --> 00:13:35,840
>> Так что просто чтобы быть ясным, это означает пойти
там, с помощью моей старой школы обозначений.

310
00:13:35,840 --> 00:13:39,580
Так что это просто означает, идти к тому, что
Вы указываете на, который в самом

311
00:13:39,580 --> 00:13:43,660
Первый случай я указывая на
Структура с девятью в нем.

312
00:13:43,660 --> 00:13:44,510
Так что я пошел туда.

313
00:13:44,510 --> 00:13:47,880
И тогда точечной нотации означает,
получить значение в следующем.

314
00:13:47,880 --> 00:13:50,470
>> Но ценность, хотя он рисуется
как узкие, просто номер.

315
00:13:50,470 --> 00:13:51,720
Это адрес в числовой.

316
00:13:51,720 --> 00:13:55,670
Так что это одна строка кода, будь то
написано, как это, более скрытом

317
00:13:55,670 --> 00:14:00,190
пути, или, как это, несколько более
интуитивно понятным способом, просто означает, пошевелить рукой

318
00:14:00,190 --> 00:14:03,460
от первого узла к следующему,
а затем следующий, а затем

319
00:14:03,460 --> 00:14:05,320
следующей, и так далее.

320
00:14:05,320 --> 00:14:09,920
>> Таким образом, мы не будем останавливаться на других
реализаций вставлять и удалять

321
00:14:09,920 --> 00:14:14,030
и обхода, первые два из
которые являются достаточно сложной.

322
00:14:14,030 --> 00:14:17,010
И я думаю, что это довольно легко получить
потерял, когда делают это в устной форме.

323
00:14:17,010 --> 00:14:19,890
Но что мы можем сделать здесь
Попробуйте определить, как

324
00:14:19,890 --> 00:14:21,640
Лучше делать это визуально.

325
00:14:21,640 --> 00:14:24,800
Потому что я хотел бы предложить, что если мы
хотите вставить элементы в этой

326
00:14:24,800 --> 00:14:26,680
существующий список, который
состоит из пяти элементов -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26 и 33 -

328
00:14:29,530 --> 00:14:33,300
Если бы я собирался осуществить это в
код, мне нужно подумать, как идти

329
00:14:33,300 --> 00:14:34,160
об этом.

330
00:14:34,160 --> 00:14:37,720
>> И я хотел бы предложить шаги ребенка
которой, в данном случае я имею в виду, каковы

331
00:14:37,720 --> 00:14:41,090
возможных сценариев, которые мы
могут возникнуть в целом?

332
00:14:41,090 --> 00:14:44,120
При реализации вставки для связанного
списке, это только, случается,

333
00:14:44,120 --> 00:14:46,090
Конкретным примером размер пять.

334
00:14:46,090 --> 00:14:50,420
Ну, если вы хотите вставить цифру,
как, скажем, номер один, и

335
00:14:50,420 --> 00:14:53,380
поддержание порядке сортировки, где
, очевидно, номер один нужно

336
00:14:53,380 --> 00:14:55,686
идти в этом конкретном примере?

337
00:14:55,686 --> 00:14:56,840
Например, в начале.

338
00:14:56,840 --> 00:15:00,030
>> Но что интересно, есть то, что
Если Вы хотите вставить одну в эту

339
00:15:00,030 --> 00:15:04,100
список, что нужно специальный указатель
обновить очевидно?

340
00:15:04,100 --> 00:15:04,610
Первая.

341
00:15:04,610 --> 00:15:07,830
Так что я бы сказал, что это первый случай
что мы могли бы хотеть рассмотреть,

342
00:15:07,830 --> 00:15:11,140
сценарий, включающий введение, по
начале списка.

343
00:15:11,140 --> 00:15:15,400
>> Давайте обрывать, может быть, так легко, или даже
простой случай, условно говоря.

344
00:15:15,400 --> 00:15:18,110
Предположим, я хочу, чтобы вставить
35 числа в порядке сортировки.

345
00:15:18,110 --> 00:15:20,600
Это, очевидно, принадлежит там.

346
00:15:20,600 --> 00:15:25,320
Так что, очевидно, указатель будет
должны быть обновлены в этом сценарии?

347
00:15:25,320 --> 00:15:30,060
34 в указатель становится NOT NULL
но адрес структуры

348
00:15:30,060 --> 00:15:31,800
содержащий номер 35.

349
00:15:31,800 --> 00:15:32,750
Так вот случай два.

350
00:15:32,750 --> 00:15:36,190
Так что уже, я вроде квантования
сколько работы я должен сделать здесь.

351
00:15:36,190 --> 00:15:39,880
>> И, наконец, очевидный случай середина
Действительно, в середине, если я хочу

352
00:15:39,880 --> 00:15:45,870
вставлять нечто вроде говорят 23, который идет
между 23 и 26, но

353
00:15:45,870 --> 00:15:48,680
Теперь все становится немного более
участвует, потому что

354
00:15:48,680 --> 00:15:52,800
указатели должны быть изменены?

355
00:15:52,800 --> 00:15:56,680
22 Так, безусловно, должна быть изменена
потому что он не может указать на 26 больше.

356
00:15:56,680 --> 00:16:00,320
Ему нужно, чтобы он указывал на новый узел,
Мне придется выделить по телефону

357
00:16:00,320 --> 00:16:01,770
Malloc или некоторый эквивалент.

358
00:16:01,770 --> 00:16:05,990
>> Но потом я также нужно, чтобы новый узел, 23
В этом случае, чтобы иметь свой указатель

359
00:16:05,990 --> 00:16:07,870
указывая на кого?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
И там будет
Порядок операций здесь.

362
00:16:10,380 --> 00:16:13,410
Потому что если я сделаю это глупо и я
Например начала в начале

363
00:16:13,410 --> 00:16:16,040
списке, и моя цель, чтобы вставить 23.

364
00:16:16,040 --> 00:16:18,610
И я проверял, оно принадлежит
здесь, около девяти?

365
00:16:18,610 --> 00:16:18,950
Нет.

366
00:16:18,950 --> 00:16:20,670
Имеет ли место здесь, рядом с 17?

367
00:16:20,670 --> 00:16:20,940
Нет.

368
00:16:20,940 --> 00:16:22,530
Имеет ли она принадлежит здесь рядом с 22?

369
00:16:22,530 --> 00:16:23,300
Да.

370
00:16:23,300 --> 00:16:26,400
>> Теперь, если я глуп здесь, и не
думая, что это до конца, я мог бы

371
00:16:26,400 --> 00:16:28,320
выделить мой новый узел 23.

372
00:16:28,320 --> 00:16:32,080
Я мог бы обновить указатель из
узел, который называется 22, указывая

373
00:16:32,080 --> 00:16:33,080
его на новый узел.

374
00:16:33,080 --> 00:16:36,140
И что тогда мне придется обновлять
указатель на новый узел, чтобы быть?

375
00:16:36,140 --> 00:16:38,120
>> СТУДЕНТ: [неразборчиво].

376
00:16:38,120 --> 00:16:38,385
>> Выступающий 1: Совершенно верно.

377
00:16:38,385 --> 00:16:39,710
Указывая на 26.

378
00:16:39,710 --> 00:16:45,590
Но, черт возьми, если бы я уже не обновлять
Указатель 22, чтобы она указывала на этого парня, и

379
00:16:45,590 --> 00:16:48,260
теперь у меня есть сироты, остальные
списка, так сказать.

380
00:16:48,260 --> 00:16:52,140
Так что порядок операций здесь
будет важно.

381
00:16:52,140 --> 00:16:55,100
>> Для этого я мог украсть,
скажем, шесть добровольцев.

382
00:16:55,100 --> 00:16:57,650
И давайте посмотрим, если мы не можем сделать этого
визуально вместо кода-мудрым.

383
00:16:57,650 --> 00:16:59,330
И у нас есть некоторые прекрасные стресса
шары для вас сегодня.

384
00:16:59,330 --> 00:17:02,510
Хорошо, а как об одном, двух, в
Назад - в конце там.

385
00:17:02,510 --> 00:17:04,530
три, четыре, вы оба
Парни на конце.

386
00:17:04,530 --> 00:17:05,579
И пять, шесть.

387
00:17:05,579 --> 00:17:05,839
Конечно.

388
00:17:05,839 --> 00:17:06,450
Пять и шесть.

389
00:17:06,450 --> 00:17:08,390
Ладно, и мы приедем
чтобы вы, ребята, в следующий раз.

390
00:17:08,390 --> 00:17:09,640
Ладно, поднимайся.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Ладно, раз уж ты здесь, во-первых,
Вы хотели бы быть тем, неловко

393
00:17:14,819 --> 00:17:16,119
Стекло в Google здесь?

394
00:17:16,119 --> 00:17:19,075
Ладно, ладно, стекло,
Запись видео.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
Хорошо, вы хорошо идти.

397
00:17:24,589 --> 00:17:27,950
>> Ладно, так что если вы, ребята, можете приехать
Здесь, я подготовил заранее

398
00:17:27,950 --> 00:17:30,110
некоторые цифры.

399
00:17:30,110 --> 00:17:31,240
Ладно, иди сюда.

400
00:17:31,240 --> 00:17:33,440
А почему бы вам не пойти немного
далее, что путь.

401
00:17:33,440 --> 00:17:35,520
И посмотрим, как тебя зовут,
Стекло с Google?

402
00:17:35,520 --> 00:17:35,910
>> СТУДЕНТ: Бен.

403
00:17:35,910 --> 00:17:36,230
>> Выступающий 1: Бен?

404
00:17:36,230 --> 00:17:38,380
ОК, Бен, ты будешь первым, буквально.

405
00:17:38,380 --> 00:17:40,580
Итак, мы собираемся отправить вам
в конце стадии.

406
00:17:40,580 --> 00:17:41,670
Ладно, и ваше имя?

407
00:17:41,670 --> 00:17:41,990
>> СТУДЕНТ: Джейсон.

408
00:17:41,990 --> 00:17:44,530
>> Выступающий 1: Джейсон, OK вы будете
быть номером девять.

409
00:17:44,530 --> 00:17:46,700
Так что, если вы хотите следовать Бен таким образом.

410
00:17:46,700 --> 00:17:47,010
>> СТУДЕНТ: Джилл.

411
00:17:47,010 --> 00:17:49,630
>> Выступающий 1: Джилл, вы собираетесь быть
17, который, если бы я сделал это более

412
00:17:49,630 --> 00:17:51,260
разумно, я бы
началось на другом конце.

413
00:17:51,260 --> 00:17:52,370
Вы идти по этому пути.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
А вы кто?

416
00:17:53,670 --> 00:17:53,980
>> СТУДЕНТ: Марии.

417
00:17:53,980 --> 00:17:56,130
>> Выступающий 1: Мария, вы будете 22.

418
00:17:56,130 --> 00:17:58,420
А ваше имя?

419
00:17:58,420 --> 00:17:58,810
>> СТУДЕНТ: Крис.

420
00:17:58,810 --> 00:18:00,100
>> Выступающий 1: Крис, вы будете 26.

421
00:18:00,100 --> 00:18:00,740
А потом, наконец.

422
00:18:00,740 --> 00:18:01,400
>> СТУДЕНТ: Дианы.

423
00:18:01,400 --> 00:18:02,670
>> Выступающий 1: Диана, вы будете 34.

424
00:18:02,670 --> 00:18:03,920
Таким образом, вы иди сюда.

425
00:18:03,920 --> 00:18:06,360
>> Ладно, настолько совершенен отсортированный
Заказать уже.

426
00:18:06,360 --> 00:18:09,600
И давайте идти вперед и делать это
так что мы можем на самом деле -

427
00:18:09,600 --> 00:18:11,720
Бен, ты просто вид глядя
из в никуда там.

428
00:18:11,720 --> 00:18:15,670
Итак, давайте пойдем дальше и изображают эту
применением оружия, так же, как я был, собственно,

429
00:18:15,670 --> 00:18:16,250
что происходит.

430
00:18:16,250 --> 00:18:19,540
Так что идти вперед и дать себе
фут или два между собой.

431
00:18:19,540 --> 00:18:22,900
И идти вперед и отметить с одной стороны,
кто бы ты должен быть направлен на

432
00:18:22,900 --> 00:18:23,470
на основе этого.

433
00:18:23,470 --> 00:18:25,890
И если вы просто указать нулевой
прямо вниз к полу.

434
00:18:25,890 --> 00:18:27,690
Хорошо, так хорошо.

435
00:18:27,690 --> 00:18:32,290
>> Так что теперь у нас есть связанный список, и позвольте мне
предлагаю, что я буду играть роль

436
00:18:32,290 --> 00:18:35,110
PTR, так что я не буду беспокоиться
проведение этого вокруг.

437
00:18:35,110 --> 00:18:37,830
А потом - кто-то глуп Конвенции -
Вы можете называть это все, что угодно -

438
00:18:37,830 --> 00:18:39,800
предшественника указатель, указатель PRED -

439
00:18:39,800 --> 00:18:43,930
это просто прозвище мы дали в
наш образец кода для моей левой руке.

440
00:18:43,930 --> 00:18:47,240
С другой стороны, что будет сохранение
отслеживать, кто есть кто в

441
00:18:47,240 --> 00:18:48,400
Следующие сценарии.

442
00:18:48,400 --> 00:18:52,390
>> Итак, пусть, во-первых, я хочу обрывать
что первый пример вставки, скажем

443
00:18:52,390 --> 00:18:54,330
20 в списке.

444
00:18:54,330 --> 00:18:57,160
Так что я собираюсь нужно, чтобы кто-то
воплощают в себе число 20 для нас.

445
00:18:57,160 --> 00:18:58,950
Так что мне нужно кого-то Malloc
от аудитории.

446
00:18:58,950 --> 00:18:59,380
Поднимайся.

447
00:18:59,380 --> 00:19:00,340
Как тебя зовут?

448
00:19:00,340 --> 00:19:01,300
>> СТУДЕНТ: Брайан.

449
00:19:01,300 --> 00:19:05,270
>> Выступающий 1: Брайан, все в порядке, так что вы
должен быть узел, содержащий 20.

450
00:19:05,270 --> 00:19:06,810
Ладно, иди сюда.

451
00:19:06,810 --> 00:19:10,025
И очевидно, что, где
Брайан действительно принадлежите?

452
00:19:10,025 --> 00:19:12,190
Таким образом, в середине - собственно,
подожди минутку.

453
00:19:12,190 --> 00:19:13,420
Мы делаем это не в порядке.

454
00:19:13,420 --> 00:19:17,170
Мы делаем это намного сложнее
, чем она должна быть в первую очередь.

455
00:19:17,170 --> 00:19:21,210
Хорошо, мы собираемся бесплатно Брайан
Брайан и Realloc как пять.

456
00:19:21,210 --> 00:19:23,680
>> Итак, теперь мы хотим, чтобы вставить
Брайан, как пять.

457
00:19:23,680 --> 00:19:25,960
Так иди сюда рядом с
Бен на мгновение.

458
00:19:25,960 --> 00:19:28,250
И вы, вероятно, может сказать
где эта история идет.

459
00:19:28,250 --> 00:19:30,500
Но давайте тщательно обдумайте
порядок выполнения операций.

460
00:19:30,500 --> 00:19:32,880
И это именно это визуальное
что происходит, чтобы выстроиться

461
00:19:32,880 --> 00:19:34,080
с этот образец кода.

462
00:19:34,080 --> 00:19:40,120
Так вот я PTR первоначально указывая
Не на Бена, как таковой, но на любом

463
00:19:40,120 --> 00:19:43,245
оценивают он содержит, который в данном случае
- что тебя зовут?

464
00:19:43,245 --> 00:19:43,670
>> СТУДЕНТ: Джейсон.

465
00:19:43,670 --> 00:19:47,350
>> Выступающий 1: Джейсон, так как Бен и я
указывая на Джейсона в этот момент.

466
00:19:47,350 --> 00:19:49,700
Так что теперь у меня есть, чтобы определить,
где же Брайан принадлежите?

467
00:19:49,700 --> 00:19:53,500
Поэтому единственное, что я имею доступ к
Прямо сейчас его N элемента данных.

468
00:19:53,500 --> 00:19:58,280
Так что я собираюсь проверить, является
Брайан меньше Джейсон?

469
00:19:58,280 --> 00:19:59,770
Ответ на этот вопрос так.

470
00:19:59,770 --> 00:20:03,680
>> Так что сейчас должно произойти,
в правильном порядке?

471
00:20:03,680 --> 00:20:07,120
Мне нужно уточнить, сколько указателей
Всего в этой истории?

472
00:20:07,120 --> 00:20:10,720
Где моя рука все еще указывая на
Джейсон, и ваша рука - если вы хотите

473
00:20:10,720 --> 00:20:12,930
положить руку, как, вроде, я
Не знаю, знаком вопроса.

474
00:20:12,930 --> 00:20:14,070
Хорошо, хорошо.

475
00:20:14,070 --> 00:20:15,670
>> Ладно, так что вы должны
несколько кандидатов.

476
00:20:15,670 --> 00:20:20,500
Либо Бен или я или Джейсон Брайан или
или все остальные, которые

477
00:20:20,500 --> 00:20:21,370
указатели нужно изменить?

478
00:20:21,370 --> 00:20:23,260
Сколько всего?

479
00:20:23,260 --> 00:20:24,080
>> Итак, два.

480
00:20:24,080 --> 00:20:27,090
Мой указатель на самом деле не имеет никакого значения
потому что я только временно.

481
00:20:27,090 --> 00:20:31,370
Так что эти два парня, по-видимому,
как Бен и Брайана.

482
00:20:31,370 --> 00:20:34,410
Итак, позвольте мне предложить, что мы обновляем
Бен, так как он в первую очередь.

483
00:20:34,410 --> 00:20:36,350
Первым элементом этого списка
Теперь будет Брайан.

484
00:20:36,350 --> 00:20:38,070
Так Бен точки на Брайана.

485
00:20:38,070 --> 00:20:39,320
Хорошо, что теперь?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Кто получает указал на кого?

488
00:20:43,460 --> 00:20:44,710
>> СТУДЕНТ: [неразборчиво].

489
00:20:44,710 --> 00:20:46,180
>> Выступающий 1: Хорошо, таким образом Брайан
чтобы указать на Джейсона.

490
00:20:46,180 --> 00:20:48,360
Но я потерял этот указатель?

491
00:20:48,360 --> 00:20:49,980
Знаю ли я, где Джейсон?

492
00:20:49,980 --> 00:20:50,790
>> СТУДЕНТ: [неразборчиво].

493
00:20:50,790 --> 00:20:52,620
>> Выступающий 1: я делаю, так как я
временный указатель.

494
00:20:52,620 --> 00:20:55,110
И по-видимому, я не изменил
, чтобы указать на новый узел.

495
00:20:55,110 --> 00:20:58,300
Так что мы можем просто Брайан точки
тот, кто на меня указывая на.

496
00:20:58,300 --> 00:20:59,000
И мы сделали.

497
00:20:59,000 --> 00:21:01,890
Таким случаем, вставка на
начало списка.

498
00:21:01,890 --> 00:21:02,950
Были два ключевых шага.

499
00:21:02,950 --> 00:21:06,750
Во-первых, мы должны обновить Бена, а затем
Мы также должны обновить Брайан.

500
00:21:06,750 --> 00:21:09,230
И тогда я не придется беспокоиться
тащась через остальную

501
00:21:09,230 --> 00:21:12,680
список, потому что мы уже нашли его
расположение, потому что он принадлежал к

502
00:21:12,680 --> 00:21:14,080
слева от первого элемента.

503
00:21:14,080 --> 00:21:15,400
>> Ладно, довольно проста.

504
00:21:15,400 --> 00:21:18,110
В самом деле, кажется, что мы уже почти
делает это слишком сложно.

505
00:21:18,110 --> 00:21:20,240
Итак, давайте обрывать конца
списка, и увидеть, где

506
00:21:20,240 --> 00:21:21,380
Сложность начинается.

507
00:21:21,380 --> 00:21:24,560
Так что если сейчас, я Alloc от аудитории.

508
00:21:24,560 --> 00:21:25,540
Любой хочет играть 55?

509
00:21:25,540 --> 00:21:26,700
Ладно, я видел вашу руку первым.

510
00:21:26,700 --> 00:21:29,620
Поднимайся.

511
00:21:29,620 --> 00:21:30,030
Да.

512
00:21:30,030 --> 00:21:31,177
Как тебя зовут?

513
00:21:31,177 --> 00:21:32,310
>> СТУДЕНТ: [неразборчиво].

514
00:21:32,310 --> 00:21:33,240
>> Выступающий 1: Habata.

515
00:21:33,240 --> 00:21:33,890
ОК, давай вверх.

516
00:21:33,890 --> 00:21:35,730
Вы будете номером 55.

517
00:21:35,730 --> 00:21:37,820
Таким образом, вы, конечно, принадлежат
в конце списка.

518
00:21:37,820 --> 00:21:41,850
Так что давайте переиграть моделирования со мной
будучи PTR на мгновение.

519
00:21:41,850 --> 00:21:44,050
Так что я собираюсь первым, чтобы указать на
все, что Бена указывая на.

520
00:21:44,050 --> 00:21:45,900
Мы оба теперь, указывая на Брайана.

521
00:21:45,900 --> 00:21:48,420
Так 55 не меньше, чем пять.

522
00:21:48,420 --> 00:21:52,510
Так что я собираюсь обновить себя,
указывая на следующий указатель Брайана, который

523
00:21:52,510 --> 00:21:54,450
Сейчас, конечно, Джейсон.

524
00:21:54,450 --> 00:21:57,310
55 составляет не менее девяти, так
Я собираюсь обновить PTR.

525
00:21:57,310 --> 00:21:58,890
Я собираюсь обновить PTR.

526
00:21:58,890 --> 00:22:02,290
Я собираюсь обновить PTR
Я собираюсь обновить PTR.

527
00:22:02,290 --> 00:22:05,060
И я собираюсь - Хм, что это
тебя зовут?

528
00:22:05,060 --> 00:22:05,560
>> СТУДЕНТ: Дианы.

529
00:22:05,560 --> 00:22:09,190
>> Выступающий 1: Диана указывает, конечно,
при нулевом левой рукой.

530
00:22:09,190 --> 00:22:13,030
Так где же на самом деле Habata
принадлежат ясно?

531
00:22:13,030 --> 00:22:15,050
С левой стороны, здесь.

532
00:22:15,050 --> 00:22:19,460
Так как я знаю, поставить ее здесь
Я думаю, что я облажался.

533
00:22:19,460 --> 00:22:22,420
Ведь что такое искусство PTR
данный момент времени?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Так что, хотя, визуально, мы можем
Очевидно, все эти

536
00:22:25,580 --> 00:22:26,610
ребята здесь на сцене.

537
00:22:26,610 --> 00:22:29,680
Я не следил за предыдущими
человек в списке.

538
00:22:29,680 --> 00:22:33,210
У меня нет пальцем указывая,
В этом случае номер узла 34.

539
00:22:33,210 --> 00:22:34,760
>> Так что давайте на самом деле начать над этим.

540
00:22:34,760 --> 00:22:37,560
Так что теперь я на самом деле нужно
Вторая локальной переменной.

541
00:22:37,560 --> 00:22:40,980
И это то, что вы увидите в
Сам образец кода C, где, как я иду,

542
00:22:40,980 --> 00:22:45,860
когда я обновляю мою правую руку, чтобы указать
Джейсон, тем самым оставляя Брайана позади, я

543
00:22:45,860 --> 00:22:51,440
лучше начать использовать мою левую руку, чтобы
обновления, где я был, так что, как я иду

544
00:22:51,440 --> 00:22:52,700
через этот список -

545
00:22:52,700 --> 00:22:55,040
более неловко, чем хотел
Теперь вот визуально -

546
00:22:55,040 --> 00:22:56,740
Я иду, чтобы добраться до
конце списка.

547
00:22:56,740 --> 00:23:00,020
>> Эта рука по-прежнему нулевой, который является довольно
бесполезным, кроме указывать

548
00:23:00,020 --> 00:23:02,980
Я ясно в конце списка
но теперь по крайней мере, у меня есть эта

549
00:23:02,980 --> 00:23:08,270
предшественника указатель, указывающий здесь, так что
Теперь то, что руки и то, что нужно указатели

550
00:23:08,270 --> 00:23:10,150
в обновлении?

551
00:23:10,150 --> 00:23:13,214
Чья рука вы хотите
перенастроить в первую очередь?

552
00:23:13,214 --> 00:23:15,190
>> СТУДЕНТ: [неразборчиво].

553
00:23:15,190 --> 00:23:16,220
>> Выступающий 1: Итак, Дианы.

554
00:23:16,220 --> 00:23:21,110
Где Вы хотите, чтобы указать
Левая Дианы указатель в?

555
00:23:21,110 --> 00:23:23,620
На 55, по-видимому, с тем чтобы
мы вставили туда.

556
00:23:23,620 --> 00:23:25,560
А где должны 55 указателя идти?

557
00:23:25,560 --> 00:23:27,000
Вниз, представляющая нулевой.

558
00:23:27,000 --> 00:23:28,890
И мои руки, на данный момент, не
значения, потому что они были просто

559
00:23:28,890 --> 00:23:30,070
временных переменных.

560
00:23:30,070 --> 00:23:31,030
Так что теперь мы закончим.

561
00:23:31,030 --> 00:23:34,650
>> Таким образом, дополнительные сложности там - и
это не так сложно реализовать,

562
00:23:34,650 --> 00:23:38,660
но нам нужна вторая переменная, чтобы сделать
уверен, что прежде, чем я могу двигать правой

563
00:23:38,660 --> 00:23:42,140
стороны, я обновить значение моей левой
стороны, ПРЕД указатель в этом случае, так

564
00:23:42,140 --> 00:23:45,860
что у меня есть задний указатель
отслеживать, где я был.

565
00:23:45,860 --> 00:23:49,360
Теперь, как в стороне, если вы думаете, что это
через это чувство, что это

566
00:23:49,360 --> 00:23:51,490
немного раздражает, чтобы сохранить
след этого левой рукой.

567
00:23:51,490 --> 00:23:54,015
>> Что бы другое решение
этой проблемы были?

568
00:23:54,015 --> 00:23:56,500
Если у вас есть, чтобы перепроектировать данных
структуры мы говорим

569
00:23:56,500 --> 00:23:59,630
через прямо сейчас?

570
00:23:59,630 --> 00:24:02,690
Если это только отчасти чувствует себя немного
раздражающим, вроде бы, два указателя

571
00:24:02,690 --> 00:24:08,430
собирается по списку, кто еще мог
были, в идеальном мире, поддерживается

572
00:24:08,430 --> 00:24:10,160
информацию, которая нам нужна?

573
00:24:10,160 --> 00:24:11,360
Да?

574
00:24:11,360 --> 00:24:12,610
>> СТУДЕНТ: [неразборчиво].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> Выступающий 1: Совершенно верно.

577
00:24:16,150 --> 00:24:19,130
Право так есть на самом деле интересное
зародыш идеи.

578
00:24:19,130 --> 00:24:22,470
И эта идея предыдущего указателя,
указывая на предыдущий элемент.

579
00:24:22,470 --> 00:24:25,580
Что делать, если я просто воплощением этого
внутри самого списка?

580
00:24:25,580 --> 00:24:27,810
И это будет трудно визуализировать
Все это без бумаги

581
00:24:27,810 --> 00:24:28,830
падения на пол.

582
00:24:28,830 --> 00:24:31,860
Но предположим, что эти парни использоваться как
их руки, чтобы иметь предыдущие

583
00:24:31,860 --> 00:24:35,950
указатель, и следующий указатель, тем самым
реализовать то, что мы назовем вдвойне

584
00:24:35,950 --> 00:24:36,830
связанный список.

585
00:24:36,830 --> 00:24:41,090
Которая позволила бы мне, чтобы разобраться перемотки,
гораздо легче без меня,

586
00:24:41,090 --> 00:24:43,800
программист, необходимости держать
отслеживать вручную -

587
00:24:43,800 --> 00:24:44,980
действительно вручную -

588
00:24:44,980 --> 00:24:47,280
от того, где я был ранее
в списке.

589
00:24:47,280 --> 00:24:48,110
Поэтому мы не будем этого делать.

590
00:24:48,110 --> 00:24:50,950
Мы будем держать его просто, потому что это
собирается прийти в цене, в два раза

591
00:24:50,950 --> 00:24:53,450
много места для указателей,
если вы хотите вторую.

592
00:24:53,450 --> 00:24:55,760
Но это действительно общий
Структура данных известных как

593
00:24:55,760 --> 00:24:57,410
дважды связанный список.

594
00:24:57,410 --> 00:25:01,310
>> Давайте сделаем последний пример здесь и положить
эти ребята из их страдания.

595
00:25:01,310 --> 00:25:03,270
Так Malloc 20.

596
00:25:03,270 --> 00:25:05,320
Поднимайтесь из прохода там.

597
00:25:05,320 --> 00:25:06,280
Ладно, как тебя зовут?

598
00:25:06,280 --> 00:25:07,440
>> СТУДЕНТ: [неразборчиво].

599
00:25:07,440 --> 00:25:07,855
>> Выступающий 1: Простите?

600
00:25:07,855 --> 00:25:08,480
>> СТУДЕНТ: [неразборчиво].

601
00:25:08,480 --> 00:25:09,410
>> Выступающий 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
ОК поднимайся.

603
00:25:10,230 --> 00:25:11,910
Вы должны быть 20.

604
00:25:11,910 --> 00:25:14,720
Вы, очевидно, собираются
принадлежат от 17 до 22.

605
00:25:14,720 --> 00:25:16,150
Итак, позвольте мне узнать свой урок.

606
00:25:16,150 --> 00:25:18,150
Я собираюсь начать указатель
указывая на Брайана.

607
00:25:18,150 --> 00:25:21,190
И я буду иметь мою левую руку
обновлять только с Брайаном, как я переехать в

608
00:25:21,190 --> 00:25:23,600
Джейсон, 20 проверка делает менее девяти?

609
00:25:23,600 --> 00:25:24,060
Нет.

610
00:25:24,060 --> 00:25:25,430
На 20 меньше, чем 17?

611
00:25:25,430 --> 00:25:25,880
Нет.

612
00:25:25,880 --> 00:25:27,450
На 20 меньше, чем 22?

613
00:25:27,450 --> 00:25:28,440
Да.

614
00:25:28,440 --> 00:25:34,070
Так что указатели или рук нужно изменить
где они указывая сейчас?

615
00:25:34,070 --> 00:25:37,070
>> Так что мы можем сделать, указывая на 17 20.

616
00:25:37,070 --> 00:25:37,860
Так что это нормально.

617
00:25:37,860 --> 00:25:40,080
Куда мы хотим, чтобы указать
указатель сейчас?

618
00:25:40,080 --> 00:25:41,330
В 22.

619
00:25:41,330 --> 00:25:45,410
И мы знаем, где 22, опять же благодаря
на мой временный указатель.

620
00:25:45,410 --> 00:25:46,760
Таким образом, мы все в порядке там.

621
00:25:46,760 --> 00:25:49,440
Так из-за этого временного хранения
Я следил, где все.

622
00:25:49,440 --> 00:25:55,055
И теперь вы можете визуально вдаваться в котором
Вы принадлежите, и теперь нам нужно 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 шаров стресс,
и аплодисменты для

624
00:25:58,410 --> 00:25:59,770
эти ребята, если мы могли.

625
00:25:59,770 --> 00:26:00,410
Красиво сделано.

626
00:26:00,410 --> 00:26:05,320
>> [Аплодисменты]

627
00:26:05,320 --> 00:26:06,330
>> Выступающий 1: Хорошо.

628
00:26:06,330 --> 00:26:09,860
И вы можете держать части
бумаги на память.

629
00:26:09,860 --> 00:26:15,930
>> Ладно, так что, поверьте мне, это намного
легче идти через это с

630
00:26:15,930 --> 00:26:17,680
людей, чем с фактическим кодом.

631
00:26:17,680 --> 00:26:22,690
Но то, что вы найдете в мгновение
Теперь, то, что же - о, спасибо.

632
00:26:22,690 --> 00:26:23,630
Спасибо -

633
00:26:23,630 --> 00:26:29,360
является то, что вы увидите, что те же данные
структуры, связанный список, может на самом деле

634
00:26:29,360 --> 00:26:33,200
использоваться в качестве строительного блока, чтобы еще больше
сложных структур данных.

635
00:26:33,200 --> 00:26:37,620
>> И поймите, слишком тема здесь является то, что
мы абсолютно ввели более

636
00:26:37,620 --> 00:26:40,060
Сложность в реализации
этого алгоритма.

637
00:26:40,060 --> 00:26:43,940
Вставки, и если мы прошли через это,
удаление и поиск, немного

638
00:26:43,940 --> 00:26:46,660
сложнее, чем
был с массивом.

639
00:26:46,660 --> 00:26:48,040
Но мы получить некоторую динамику.

640
00:26:48,040 --> 00:26:50,180
Мы получаем адаптивную структуру данных.

641
00:26:50,180 --> 00:26:54,010
>> Но опять же, мы платим цену наличием некоторых
дополнительные сложности, как в

642
00:26:54,010 --> 00:26:54,910
его осуществлении.

643
00:26:54,910 --> 00:26:56,750
И мы отказались от случайного доступа.

644
00:26:56,750 --> 00:27:00,450
И, честно говоря, нет некоторых хороших
чистое предметное я могу дать вам, что

645
00:27:00,450 --> 00:27:03,120
говорит вот почему связанный список
лучше, чем массив.

646
00:27:03,120 --> 00:27:04,100
И оставить все как есть.

647
00:27:04,100 --> 00:27:07,520
Потому что тема повторения теперь, даже
более, что в ближайшие недели, является

648
00:27:07,520 --> 00:27:10,200
что есть не обязательно
правильный ответ.

649
00:27:10,200 --> 00:27:13,830
>> Вот почему у нас есть отдельные оси
дизайна для домашних заданий.

650
00:27:13,830 --> 00:27:17,700
Это будет очень контекстно-зависимых
хотите ли вы использовать эти данные

651
00:27:17,700 --> 00:27:21,750
структуру или, что одно и оно будет
зависит от того, что для вас важно в плане

652
00:27:21,750 --> 00:27:24,620
ресурсов и сложности.

653
00:27:24,620 --> 00:27:28,830
>> Но позвольте мне предложить, что идеальные данные
Структура, Святой Грааль, были бы

654
00:27:28,830 --> 00:27:32,200
то, что постоянная времени,
независимо от того, сколько материал

655
00:27:32,200 --> 00:27:36,940
внутри нее, не было бы удивительно, если
структура данных, возвращаемая ответы

656
00:27:36,940 --> 00:27:37,920
постоянное время.

657
00:27:37,920 --> 00:27:38,330
Да.

658
00:27:38,330 --> 00:27:40,110
Это слово в вашем огромном словаре.

659
00:27:40,110 --> 00:27:41,550
Или нет, это слово не является.

660
00:27:41,550 --> 00:27:43,270
Или любая такая проблема.

661
00:27:43,270 --> 00:27:46,360
Ну давайте посмотрим, если мы не можем по крайней мере,
сделать шаг на этом пути.

662
00:27:46,360 --> 00:27:50,190
>> Позвольте мне предложить новую структуру данных, которая
могут быть использованы для разных целей,

663
00:27:50,190 --> 00:27:52,260
В этом случае называют хэш-таблице.

664
00:27:52,260 --> 00:27:55,590
И вот мы на самом деле вернуться к взглянув
в массиве, и в этом случае, а также

665
00:27:55,590 --> 00:28:00,550
несколько произвольно, я нарисовал эту
хэш-таблицы в виде массива рода

666
00:28:00,550 --> 00:28:02,810
двумерный массив -

667
00:28:02,810 --> 00:28:05,410
или, скорее, он изображен здесь как два
одномерный массив - но это только

668
00:28:05,410 --> 00:28:10,770
массив размером 26, так что, если мы
называют массивом, настольный кронштейн

669
00:28:10,770 --> 00:28:12,440
нуля прямоугольника в верхней части.

670
00:28:12,440 --> 00:28:15,090
Таблица 25 кронштейн представляет собой прямоугольник
в нижней части.

671
00:28:15,090 --> 00:28:18,620
И это, как я мог бы нарисовать данные
структура, в которой я хочу сохранить

672
00:28:18,620 --> 00:28:19,790
имена людей.

673
00:28:19,790 --> 00:28:24,370
>> Так, например, и я не буду рисовать
Все это здесь, на накладные расходы, если я

674
00:28:24,370 --> 00:28:29,160
было это массив, который я сейчас собираюсь
называют хэш-таблицу, и это опять же

675
00:28:29,160 --> 00:28:31,360
Расположение нулю.

676
00:28:31,360 --> 00:28:34,840
Это вот расположение
, и так далее.

677
00:28:34,840 --> 00:28:37,880
Я утверждаю, что я хочу использовать эти данные
Структура, ради обсуждения,

678
00:28:37,880 --> 00:28:42,600
сохранять имена людей, Алиса и Боб
и Чарли и другие подобные имена.

679
00:28:42,600 --> 00:28:46,110
Так что думать об этом сейчас, когда начал
, скажем, словарь

680
00:28:46,110 --> 00:28:47,520
с большим количеством слов.

681
00:28:47,520 --> 00:28:49,435
Они, оказывается, имена
В нашем примере.

682
00:28:49,435 --> 00:28:52,560
И все это слишком уместны, пожалуй,
осуществление проверки орфографии, как мы

683
00:28:52,560 --> 00:28:54,400
может для проблемных установить шесть.

684
00:28:54,400 --> 00:28:59,300
>> Так что, если у нас есть массив от общего размера 26
так что это 25-й расположение

685
00:28:59,300 --> 00:29:03,390
в нижней части, и я утверждаю, что Алиса
Первое слово в словаре

686
00:29:03,390 --> 00:29:07,260
имена, которые я хочу вставить в оперативную память,
в эту структуру данных, где

687
00:29:07,260 --> 00:29:12,480
инстинкты говорят вам, что Алисы
имя должно идти в этом массиве?

688
00:29:12,480 --> 00:29:13,510
>> У нас есть 26 вариантов.

689
00:29:13,510 --> 00:29:14,990
Где мы хотим поставить ее?

690
00:29:14,990 --> 00:29:16,200
Мы хотим ее в кронштейн нулю, не так ли?

691
00:29:16,200 --> 00:29:18,280
Для Алисы, давайте назовем что нулю.

692
00:29:18,280 --> 00:29:20,110
И B будет одной и С будут два.

693
00:29:20,110 --> 00:29:22,600
Итак, мы собираемся писать
Алиса имя здесь.

694
00:29:22,600 --> 00:29:24,890
Если мы затем вставьте Боб, его
Название пойду сюда.

695
00:29:24,890 --> 00:29:27,280
Чарли пойду сюда.

696
00:29:27,280 --> 00:29:30,500
И так далее вниз через
этой структуры данных.

697
00:29:30,500 --> 00:29:32,090
>> Это прекрасная структуры данных.

698
00:29:32,090 --> 00:29:32,730
Почему?

699
00:29:32,730 --> 00:29:37,460
Ну то, что время работы
вставка имя человека в эту

700
00:29:37,460 --> 00:29:39,850
Структура данных прямо сейчас?

701
00:29:39,850 --> 00:29:43,702
Учитывая, что эта таблица будет реализован,
действительно, как массив.

702
00:29:43,702 --> 00:29:44,940
Ну, это постоянное время.

703
00:29:44,940 --> 00:29:45,800
Это порядка единицы.

704
00:29:45,800 --> 00:29:46,360
Почему?

705
00:29:46,360 --> 00:29:48,630
>> Ну как вы определяете,
Где Alice принадлежит?

706
00:29:48,630 --> 00:29:51,000
Ты смотришь на какую букву ее имени?

707
00:29:51,000 --> 00:29:51,490
Первое.

708
00:29:51,490 --> 00:29:54,350
И вы можете получить там, если это строка,
просто глядя на строку

709
00:29:54,350 --> 00:29:55,200
Кронштейн нулю.

710
00:29:55,200 --> 00:29:57,110
Таким образом, нулевой символ строки.

711
00:29:57,110 --> 00:29:57,610
Это легко.

712
00:29:57,610 --> 00:30:00,350
Мы сделали это в Crypto
Назначение недели назад.

713
00:30:00,350 --> 00:30:05,310
И то, как только вы знаете, что Алисы
Письмо капитала, мы можем вычесть

714
00:30:05,310 --> 00:30:08,160
от 65 лет и сам капитал,
, что дает нам нулю.

715
00:30:08,160 --> 00:30:10,940
Таким образом, мы теперь знаем, что Алиса принадлежит
по месту нахождения нуля.

716
00:30:10,940 --> 00:30:14,240
>> А если учесть, указатель на эти данные
структуры, какой-то, как долго

717
00:30:14,240 --> 00:30:18,840
мне потребуется, чтобы найти расположение
нулю в массив?

718
00:30:18,840 --> 00:30:22,080
Всего лишь один шаг, правая Это постоянное время
из-за случайного доступа мы

719
00:30:22,080 --> 00:30:23,780
Предлагаемый было особенностью массива.

720
00:30:23,780 --> 00:30:28,570
Короче говоря, выяснить, что индекс
имени Алисы, которая, по

721
00:30:28,570 --> 00:30:32,610
этом случае, или давайте просто решать
что к нулю, где B является одним и С

722
00:30:32,610 --> 00:30:34,900
два, полагая, что из
постоянная времени.

723
00:30:34,900 --> 00:30:38,510
Я просто смотреть на нее первое письмо,
выясняя, где ноль

724
00:30:38,510 --> 00:30:40,460
массив также постоянное время.

725
00:30:40,460 --> 00:30:42,140
Так что технически это
как теперь два шага.

726
00:30:42,140 --> 00:30:43,330
Но это все равно постоянно.

727
00:30:43,330 --> 00:30:46,880
Так мы называем это Big O одного Таким образом мы
вставлены Алиса в эту таблицу в

728
00:30:46,880 --> 00:30:48,440
постоянное время.

729
00:30:48,440 --> 00:30:50,960
>> Но, конечно, я веду себя
наивная, да?

730
00:30:50,960 --> 00:30:53,240
Что делать, если есть Аарона в классе?

731
00:30:53,240 --> 00:30:53,990
Или Алисия?

732
00:30:53,990 --> 00:30:57,230
Или любые другие имена, начинающиеся с
А. Куда мы собираемся поставить

733
00:30:57,230 --> 00:31:00,800
что человек, не так ли?

734
00:31:00,800 --> 00:31:03,420
Я имею в виду, прямо сейчас есть только три
люди на стол, поэтому возможно, мы

735
00:31:03,420 --> 00:31:07,490
Аарон должен положить по месту нахождения
ноль один два три.

736
00:31:07,490 --> 00:31:09,480
>> Право, я мог бы поставить здесь.

737
00:31:09,480 --> 00:31:13,350
Но тогда, если мы пытаемся вставить Давиду в
этого списка, где же Давид идти?

738
00:31:13,350 --> 00:31:15,170
Теперь наша система начинает нарушения
вниз, вправо?

739
00:31:15,170 --> 00:31:19,210
Потому что теперь Дэвид заканчивает здесь
Если на самом деле Аарон здесь.

740
00:31:19,210 --> 00:31:23,060
И вот теперь вся эта идея с
чистая структура данных, которая дает нам

741
00:31:23,060 --> 00:31:28,010
вставок постоянного времени уже не
постоянное время, потому что я должен

742
00:31:28,010 --> 00:31:31,240
проверить, о, черт возьми, кто-то уже
по месту нахождения Алисы.

743
00:31:31,240 --> 00:31:35,320
>> Позвольте мне исследовать остальную часть этого данные
Структура, ища место, чтобы положить

744
00:31:35,320 --> 00:31:37,130
кто-то, как имя Аарона.

745
00:31:37,130 --> 00:31:39,390
И так, что тоже начинает
принять линейное время.

746
00:31:39,390 --> 00:31:42,710
Более того, если вы сейчас хотите найти
Аарон в этой структуре данных, и вы

747
00:31:42,710 --> 00:31:45,430
проверить и имя Аарона здесь нет.

748
00:31:45,430 --> 00:31:47,960
В идеале, вы просто сказали бы Аарона
не в структуре данных.

749
00:31:47,960 --> 00:31:51,530
Но если вы начинаете освобождая место для
Аарон, где должно было быть D

750
00:31:51,530 --> 00:31:55,600
или E, вы, худшем случае, придется проверить
Вся структура данных, в

751
00:31:55,600 --> 00:31:59,480
этом случае она переходит в нечто
линейный в размер таблицы.

752
00:31:59,480 --> 00:32:00,920
>> Так что все в порядке, я буду это исправить.

753
00:32:00,920 --> 00:32:04,200
Проблема здесь в том, что у меня было
26 элементов в этом массиве.

754
00:32:04,200 --> 00:32:05,000
Позвольте мне изменить.

755
00:32:05,000 --> 00:32:06,010
К сожалению.

756
00:32:06,010 --> 00:32:10,600
Позвольте мне изменить его так, что вместо бытия
размер 26 в общей сложности, обратите внимание на нижнюю

757
00:32:10,600 --> 00:32:12,720
Индекс будет меняться к N минус 1.

758
00:32:12,720 --> 00:32:16,610
Если 26 явно слишком мал для людей "
имена, потому что есть тысячи

759
00:32:16,610 --> 00:32:20,830
имена мира, давайте просто делать
в 100 или 1000 или 10000.

760
00:32:20,830 --> 00:32:22,960
Давайте просто выделить намного больше места.

761
00:32:22,960 --> 00:32:27,230
>> Ну, что вовсе не обязательно снижает
вероятность того, что мы не будем иметь два

762
00:32:27,230 --> 00:32:31,510
люди с именами, начинающимися с, и
Итак, вы собираетесь, чтобы попытаться положить

763
00:32:31,510 --> 00:32:33,120
имена по месту нахождения нуля до сих пор.

764
00:32:33,120 --> 00:32:36,850
Они все еще собираемся сталкиваются, которая
означает, что мы все еще нужно решение, чтобы положить

765
00:32:36,850 --> 00:32:41,020
Алиса и Аарона и Алисия и другие
имена, начинающиеся с в другом месте.

766
00:32:41,020 --> 00:32:43,460
Но как большая проблема это?

767
00:32:43,460 --> 00:32:46,870
Какая вероятность того, что вы
могут возникать конфликты в данных

768
00:32:46,870 --> 00:32:48,240
структуры, как это?

769
00:32:48,240 --> 00:32:52,570
>> Ну, позвольте мне - мы вернемся
На этот вопрос здесь.

770
00:32:52,570 --> 00:32:55,530
И посмотрите, как мы могли бы
решить в первую очередь.

771
00:32:55,530 --> 00:32:58,480
Позвольте мне подтянуть это предложение здесь.

772
00:32:58,480 --> 00:33:02,020
То, что мы только что описали алгоритм,
эвристические называются линейными

773
00:33:02,020 --> 00:33:05,030
зондирования которой, если бы вы попытались вставить
что-то здесь, в этом данные

774
00:33:05,030 --> 00:33:08,920
Структура, которая называется хэш-таблицу,
и там нет места там, вы

775
00:33:08,920 --> 00:33:12,000
действительно исследовать структуры данных
проверки, это доступно?

776
00:33:12,000 --> 00:33:13,430
Является ли это доступно это доступно?

777
00:33:13,430 --> 00:33:13,980
Является ли это доступно?

778
00:33:13,980 --> 00:33:17,550
И когда он, наконец, вы вставьте
имя, которое вы изначально

779
00:33:17,550 --> 00:33:19,370
в других местах в этом месте.

780
00:33:19,370 --> 00:33:23,360
Но в худшем случае, единственное место,
может быть в самом низу данных

781
00:33:23,360 --> 00:33:25,090
Структура, в самом конце массива.

782
00:33:25,090 --> 00:33:30,130
>> Так линейного зондирования, в худшем случае,
превратится в линейный алгоритм, где

783
00:33:30,130 --> 00:33:34,500
Аарона, если он произойдет, будет вставлен последний
В этой структуре данных, он может

784
00:33:34,500 --> 00:33:39,540
сталкиваться с этой первой месте, но
Затем закончиться неудачей в самом конце.

785
00:33:39,540 --> 00:33:43,940
Так что это не постоянная
время святой Грааль для нас.

786
00:33:43,940 --> 00:33:47,650
Этот подход вставки элементов в
структуру данных, называемую хэш

787
00:33:47,650 --> 00:33:52,050
Таблица не кажется, постоянное время
по крайней мере, в общем случае.

788
00:33:52,050 --> 00:33:54,000
Это может превратится в нечто линейной.

789
00:33:54,000 --> 00:33:56,970
>> Так что, если мы разрешения коллизий
несколько по-другому?

790
00:33:56,970 --> 00:34:00,740
Итак, вот более сложные
подходить к тому, что до сих пор

791
00:34:00,740 --> 00:34:02,800
называемый хэш-таблицу.

792
00:34:02,800 --> 00:34:05,890
И хэш, а в сторону, что
Я имею в виду, что индекс

793
00:34:05,890 --> 00:34:07,070
Котором я говорил раньше.

794
00:34:07,070 --> 00:34:09,810
Для хэш что-то может быть
рассматривать как глагол.

795
00:34:09,810 --> 00:34:13,690
>> Так что если вы хэш Алисы имя,
хеш-функции, так сказать,

796
00:34:13,690 --> 00:34:14,710
должна возвращать число.

797
00:34:14,710 --> 00:34:18,199
В этом случае равно нулю, если она принадлежит на
нулевом месте, один, если она принадлежит на

798
00:34:18,199 --> 00:34:20,000
местоположение, и так далее.

799
00:34:20,000 --> 00:34:24,360
Так что мой хэш-функции до сих пор было
супер просто, только глядя на

800
00:34:24,360 --> 00:34:26,159
Первая буква в чье-то имя.

801
00:34:26,159 --> 00:34:29,090
Но хэш-функция принимает в качестве
ввести некоторые части данных,

802
00:34:29,090 --> 00:34:30,210
строка, целое все.

803
00:34:30,210 --> 00:34:32,239
И он выплевывает обычно число.

804
00:34:32,239 --> 00:34:35,739
И это число, где, что данные
элемент принадлежит в структуре данных

805
00:34:35,739 --> 00:34:37,800
известный здесь как хэш-таблицу.

806
00:34:37,800 --> 00:34:41,400
>> Так что просто интуитивно, это
несколько ином контексте.

807
00:34:41,400 --> 00:34:44,170
Это фактически имеет в виду пример
с участием дни рождения, где

808
00:34:44,170 --> 00:34:46,850
там может быть столько, сколько
31 дней в месяце.

809
00:34:46,850 --> 00:34:52,239
Но то, что этому человеку решить
делать в случае столкновения?

810
00:34:52,239 --> 00:34:55,304
Контекст в настоящее время, а не столкновение
имена, но столкновение дни рождения,

811
00:34:55,304 --> 00:35:00,760
если два человека имеют одинаковый день рождения
2-го октября, например.

812
00:35:00,760 --> 00:35:02,120
>> СТУДЕНТ: [неразборчиво].

813
00:35:02,120 --> 00:35:05,010
>> Выступающий 1: Да, так что здесь мы имеем
более эффективного использования связанных списков.

814
00:35:05,010 --> 00:35:07,830
Так это выглядит немного по-другому
чем мы обратили его ранее.

815
00:35:07,830 --> 00:35:10,790
Но мы, кажется, есть в массив
на левой стороне.

816
00:35:10,790 --> 00:35:13,230
В этом нет одного индекса, для не
особой причины.

817
00:35:13,230 --> 00:35:14,630
Но это все еще массиве.

818
00:35:14,630 --> 00:35:16,160
Это массив указателей.

819
00:35:16,160 --> 00:35:20,670
И каждый из тех элементов, каждый из
эти круги или косая черта - слэш

820
00:35:20,670 --> 00:35:23,970
представляющий нулевой - каждая из этих
указателей по-видимому, указывающие на

821
00:35:23,970 --> 00:35:25,730
какие данные структуры?

822
00:35:25,730 --> 00:35:26,890
Связанный список.

823
00:35:26,890 --> 00:35:30,530
>> Так что теперь у нас есть возможность
жесткий код в нашей программе

824
00:35:30,530 --> 00:35:32,010
Размер таблицы.

825
00:35:32,010 --> 00:35:35,360
В этом случае, мы знаем, никогда нет
более 31 дней в месяц.

826
00:35:35,360 --> 00:35:38,480
Так жесткое кодирование значения, как 31
разумное в этом контексте.

827
00:35:38,480 --> 00:35:42,700
В контексте имен, жесткого кодирования
26 не является необоснованным его людей

828
00:35:42,700 --> 00:35:46,340
только имена начинаются с, например,
алфавита с участием до Z.

829
00:35:46,340 --> 00:35:50,180
>> Мы можем втиснуть их все в этих данных
Структура пока, когда мы получаем

830
00:35:50,180 --> 00:35:55,330
столкновения, мы не ставим здесь имена,
мы вместо этого думать об этих клетках

831
00:35:55,330 --> 00:36:00,270
а не как строки себя, но в качестве
указателей, например, Элис.

832
00:36:00,270 --> 00:36:03,660
И тогда Алиса может иметь другой указатель
в другое имя, начинающееся с

833
00:36:03,660 --> 00:36:06,150
А. и Боб на самом деле идет сюда.

834
00:36:06,150 --> 00:36:10,850
>> И, если есть другой имя, начинающееся
с В, он заканчивается здесь.

835
00:36:10,850 --> 00:36:15,070
И поэтому каждый из элементов этой
Таблица два, если мы разработали эту

836
00:36:15,070 --> 00:36:17,350
немного умнее -

837
00:36:17,350 --> 00:36:18,125
Давай, -

838
00:36:18,125 --> 00:36:22,950
если мы разработали это немного больше
умнее, теперь становится адаптивами

839
00:36:22,950 --> 00:36:27,720
структура, в которой нет жесткого ограничения
от того, сколько элементов вы можете вставить

840
00:36:27,720 --> 00:36:30,700
в это, потому что если у вас есть
столкновения, это нормально.

841
00:36:30,700 --> 00:36:34,690
Просто идти вперед и добавить его в
что мы видели немного назад было

842
00:36:34,690 --> 00:36:38,290
известный как связанный список.

843
00:36:38,290 --> 00:36:39,690
>> Ну давайте паузу на мгновение.

844
00:36:39,690 --> 00:36:42,570
Какова вероятность столкновения
в первую очередь?

845
00:36:42,570 --> 00:36:45,480
Право, может быть, я по думал, может быть,
Я на инженерных эту проблему,

846
00:36:45,480 --> 00:36:46,370
потому что вы знаете, что?

847
00:36:46,370 --> 00:36:49,070
Да, я могу придумать произвольное
Примеры с верхней части моей головы, как

848
00:36:49,070 --> 00:36:52,870
Allison и Аарона, но в действительности,
задано равномерное распределение

849
00:36:52,870 --> 00:36:56,990
входов, то есть некоторые случайные вставки
в структуру данных, что на самом деле

850
00:36:56,990 --> 00:36:58,580
Вероятность столкновения?

851
00:36:58,580 --> 00:37:01,670
Хорошо получается, это на самом деле
супер высокой.

852
00:37:01,670 --> 00:37:03,850
Позвольте мне обобщить эту
Проблема, как этот.

853
00:37:03,850 --> 00:37:08,890
>> Таким образом, в комнате N CS50 студентов, что
вероятность того, что по крайней мере

854
00:37:08,890 --> 00:37:11,010
Два студента в комнате
имеют одинаковый день рождения?

855
00:37:11,010 --> 00:37:13,346
Так что есть что. Несколько Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 людей здесь и несколько
сотни людей у ​​себя дома сегодня.

857
00:37:16,790 --> 00:37:20,670
Так что если вы хотели спросить себя, что это
вероятность два человека

858
00:37:20,670 --> 00:37:23,930
В этом номере, имеющем тот же день рождения,
мы можем понять это.

859
00:37:23,930 --> 00:37:26,250
И я утверждаю, на самом деле есть два
людей с такими же день рождения.

860
00:37:26,250 --> 00:37:29,560
>> Например, кто-нибудь
имеют сегодня день рождения?

861
00:37:29,560 --> 00:37:31,340
Вчера?

862
00:37:31,340 --> 00:37:32,590
Завтра?

863
00:37:32,590 --> 00:37:35,980
Все в порядке, поэтому он чувствует себя, как я собираюсь
чтобы сделать это 363 или около того больше

864
00:37:35,980 --> 00:37:39,500
раз на самом деле выяснить,
Если у нас есть столкновения.

865
00:37:39,500 --> 00:37:42,350
Или мы могли бы просто сделать это математически
а не утомительно

866
00:37:42,350 --> 00:37:43,200
делать это.

867
00:37:43,200 --> 00:37:44,500
И предлагаю следующее.

868
00:37:44,500 --> 00:37:48,740
>> Поэтому я предлагаю, чтобы мы могли моделировать
Вероятность двух людей с

869
00:37:48,740 --> 00:37:55,320
же день рождения, как и вероятность 1
минус вероятность не имеющий

870
00:37:55,320 --> 00:37:56,290
тот же день рождения.

871
00:37:56,290 --> 00:37:59,960
Таким образом, чтобы получить это, и это только
причудливый способ написания этого, для

872
00:37:59,960 --> 00:38:03,090
Первый человек в комнате, он или она
может иметь любую одну из возможных

873
00:38:03,090 --> 00:38:07,370
Дни рождения предполагая, 365 дней в году,
с извинениями для лиц с

874
00:38:07,370 --> 00:38:08,760
Февральская 29 лет.

875
00:38:08,760 --> 00:38:13,470
>> Таким образом, первый человек в этом номере бесплатный
иметь любое количество рождений

876
00:38:13,470 --> 00:38:18,280
из 365 возможностей так, чтобы
мы сделаем это 365 разделить на 365,

877
00:38:18,280 --> 00:38:18,990
который является одним.

878
00:38:18,990 --> 00:38:22,700
Следующий человек в комнате, если цель
, чтобы избежать столкновения, можно только

879
00:38:22,700 --> 00:38:26,460
его или ее день рождения о том, как
много различных возможных дней?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Таким образом, второе слагаемое в этом выражении
по существу делают, что математика для нас

882
00:38:31,430 --> 00:38:33,460
путем вычитания от одного возможный день.

883
00:38:33,460 --> 00:38:36,390
А потом на следующий день, на следующий день,
на следующий день до общего количества

884
00:38:36,390 --> 00:38:38,100
людей в комнате.

885
00:38:38,100 --> 00:38:41,290
>> И если мы, то рассмотрим, что же тогда есть
вероятность не каждый имеющий

886
00:38:41,290 --> 00:38:45,265
уникальные дни рождения, но опять же минус 1
что, что мы получаем выражение

887
00:38:45,265 --> 00:38:47,810
, что может очень причудливо
выглядеть следующим образом.

888
00:38:47,810 --> 00:38:50,330
Но это более интересно
смотреть на визуально.

889
00:38:50,330 --> 00:38:55,120
Это график, где по оси абсцисс представляет
Количество человек в комнате,

890
00:38:55,120 --> 00:38:56,180
количество рождений.

891
00:38:56,180 --> 00:38:59,840
На оси ординат вероятность
столкновения, два человека

892
00:38:59,840 --> 00:39:01,230
имеющие тот же день рождения.

893
00:39:01,230 --> 00:39:05,020
>> И еду на дом от этой кривой
что, как только вы получите как 40

894
00:39:05,020 --> 00:39:11,110
студенты, твоя очередь на 90% вероятности
комбинаторно двух

895
00:39:11,110 --> 00:39:13,550
человек или больше имеющей
тот же день рождения.

896
00:39:13,550 --> 00:39:18,600
И как только вы получите 58 человек нравится это
почти 100% шанс двух

897
00:39:18,600 --> 00:39:21,310
людей в комнате собираются иметь
же день рождения, хотя есть

898
00:39:21,310 --> 00:39:26,650
365 или 366 возможных ведра, и
Только 58 человек в комнате.

899
00:39:26,650 --> 00:39:29,900
Просто статистически вы, вероятно,
получить столкновений, которая в короткие

900
00:39:29,900 --> 00:39:31,810
мотивирует это обсуждение.

901
00:39:31,810 --> 00:39:35,890
Что даже если мы получить фантазии здесь, и
начать с этих цепей, мы все еще

902
00:39:35,890 --> 00:39:36,950
придется столкновений.

903
00:39:36,950 --> 00:39:42,710
>> Так что возникает вопрос, что такое
затраты на ведение операции вставки и удаления

904
00:39:42,710 --> 00:39:44,850
в структуру данных, как это?

905
00:39:44,850 --> 00:39:46,630
Ну позвольте мне предложить -

906
00:39:46,630 --> 00:39:51,570
и позвольте мне вернуться к экрану над
здесь - если мы п элементов в

907
00:39:51,570 --> 00:39:56,330
список, так что если мы пытаемся вставить
N элементов, и у нас есть

908
00:39:56,330 --> 00:39:58,050
сколько всего ведра?

909
00:39:58,050 --> 00:40:03,450
Скажем, 31 всего ведра
в случае рождения.

910
00:40:03,450 --> 00:40:09,240
Какая максимальная длина одного
этих цепей потенциально?

911
00:40:09,240 --> 00:40:12,670
>> Если снова есть 31 возможных
Дни рождения в данном месяце.

912
00:40:12,670 --> 00:40:14,580
А ведь это только слипания всех -

913
00:40:14,580 --> 00:40:15,580
на самом деле это глупый пример.

914
00:40:15,580 --> 00:40:16,960
Давайте делать, а не 26.

915
00:40:16,960 --> 00:40:20,890
Так что, если на самом деле есть люди, чьи имена
Начните с через Z, тем самым давая

916
00:40:20,890 --> 00:40:22,780
нам 26 возможностей.

917
00:40:22,780 --> 00:40:25,920
И мы, используя структуру данных, как
тот, который мы только что видели, в результате чего мы имеем

918
00:40:25,920 --> 00:40:30,210
массив указателей, каждый из которых
указывает на связанный список, где

919
00:40:30,210 --> 00:40:32,360
Первый список все
с именем Элис.

920
00:40:32,360 --> 00:40:35,770
Второй список с каждым
имя, начинающееся с, начиная

921
00:40:35,770 --> 00:40:36,980
с В, и так далее.

922
00:40:36,980 --> 00:40:41,020
>> Какая вероятность длина каждого из
эти списки, если предположить, хороший чистый

923
00:40:41,020 --> 00:40:45,410
Распределение имен через Z
по всей структуре данных?

924
00:40:45,410 --> 00:40:50,210
Там в русских людей в структуре данных
деленное на 26, если они красиво

925
00:40:50,210 --> 00:40:52,110
распространиться по всей
структуре данных.

926
00:40:52,110 --> 00:40:54,970
Таким образом, длина каждого из этих
цепей п деленное на 26.

927
00:40:54,970 --> 00:40:57,380
Но в больших обозначение О, что это?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Что это на самом деле?

930
00:41:02,440 --> 00:41:04,150
Так что это действительно просто п, не так ли?

931
00:41:04,150 --> 00:41:06,620
Потому что мы говорили в прошлом,
тьфу, что вы разделите на 26.

932
00:41:06,620 --> 00:41:08,710
Да, на самом деле это быстрее.

933
00:41:08,710 --> 00:41:12,720
Но в теории, это не принципиально
все, что быстрее.

934
00:41:12,720 --> 00:41:16,040
>> Таким образом, мы, кажется, не так уж много
ближе к этой Святой Грааль.

935
00:41:16,040 --> 00:41:17,750
На самом деле, это всего лишь линейное время.

936
00:41:17,750 --> 00:41:20,790
Черт возьми, в этот момент, почему бы нам не
Разместите один огромный связанный список?

937
00:41:20,790 --> 00:41:23,510
Почему бы нам не использовать только один огромный
массив для хранения имен

938
00:41:23,510 --> 00:41:25,010
все в комнате?

939
00:41:25,010 --> 00:41:28,280
Ну, есть еще что-то
убедительным о хэш-таблицы?

940
00:41:28,280 --> 00:41:30,810
Есть ли еще что-то убедительных
о структуре данных

941
00:41:30,810 --> 00:41:33,940
, который выглядит, как это?

942
00:41:33,940 --> 00:41:35,182
Это.

943
00:41:35,182 --> 00:41:37,050
>> СТУДЕНТ: [неразборчиво].

944
00:41:37,050 --> 00:41:39,840
>> Выступающий 1: Да, и еще раз, если это просто
линейный алгоритм времени и

945
00:41:39,840 --> 00:41:42,780
линейное время структура данных, почему бы мне не
просто хранить имя каждого в большой

946
00:41:42,780 --> 00:41:44,210
массиве или в большом связанный список?

947
00:41:44,210 --> 00:41:47,010
И прекратите делать CS намного труднее
, чем она должна быть?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Что является убедительным по этому поводу, даже
хотя я поцарапал его?

950
00:41:53,190 --> 00:41:54,930
>> СТУДЕНТ: [неразборчиво].

951
00:41:54,930 --> 00:41:57,040
>> Выступающий 1: заказчику не?

952
00:41:57,040 --> 00:41:58,140
Дорогие больше.

953
00:41:58,140 --> 00:42:03,390
Так вставками потенциально могли еще
постоянной времени, даже если ваши данные

954
00:42:03,390 --> 00:42:07,910
структура выглядит следующим образом, массив
указателей, каждый из которых указывает на

955
00:42:07,910 --> 00:42:09,550
потенциально связанный список.

956
00:42:09,550 --> 00:42:15,220
Как вы могли бы достичь постоянной
Время введения имена?

957
00:42:15,220 --> 00:42:16,280
Приклейте наклейку на фронте, не так ли?

958
00:42:16,280 --> 00:42:19,290
>> Если мы жертвуем дизайн гол
ранее, где мы хотели сохранить

959
00:42:19,290 --> 00:42:22,650
всех по именам, например, сортируют,
или все цифры на этапе отсортированы,

960
00:42:22,650 --> 00:42:25,020
Предположим, что у нас есть
несортированный связанный список.

961
00:42:25,020 --> 00:42:29,960
Это только стоит нам один или два этапа,
Как и в случае с Беном и Брайан

962
00:42:29,960 --> 00:42:32,750
ранее, вставить элемент в
начале списка.

963
00:42:32,750 --> 00:42:36,090
Так что, если мы не заботимся о сортировке все
из имен, начиная с или все

964
00:42:36,090 --> 00:42:39,660
имена, начинающиеся с B, мы все еще можем
достижения постоянной время вставки.

965
00:42:39,660 --> 00:42:43,900
Теперь глядя Алисы или Боба или любое имя
в целом все еще что?

966
00:42:43,900 --> 00:42:48,100
Это большое О от N деленное на 26, в
идеальном случае, когда все это равномерно

967
00:42:48,100 --> 00:42:51,190
распределены, где есть столько автора
как есть Z, который, вероятно,

968
00:42:51,190 --> 00:42:52,220
нереально.

969
00:42:52,220 --> 00:42:53,880
Но это по-прежнему линейно.

970
00:42:53,880 --> 00:42:57,120
>> Но и здесь мы возвращаемся к точке
асимптотической обозначения бытия

971
00:42:57,120 --> 00:42:58,600
Теоретически верно.

972
00:42:58,600 --> 00:43:02,960
Но в реальном мире, если я утверждаю, что
моя программа может сделать что-то 26 раз

973
00:43:02,960 --> 00:43:06,210
быстрее, чем ваша, чья программа
Вы собираетесь предпочитаете использовать?

974
00:43:06,210 --> 00:43:09,660
Ваша или моя, которая
в 26 раз быстрее?

975
00:43:09,660 --> 00:43:14,320
Реально, лица, составляет 26
раза быстрее, даже если теоретически

976
00:43:14,320 --> 00:43:18,790
наши алгоритмы работают в том же
асимптотическое время.

977
00:43:18,790 --> 00:43:20,940
>> Позвольте мне предложить другую
Решение в целом.

978
00:43:20,940 --> 00:43:24,380
И если этого не сразит вас наповал,
мы из структур данных.

979
00:43:24,380 --> 00:43:27,420
Так это он, синтаксического дерева -

980
00:43:27,420 --> 00:43:28,520
вид глупое имя.

981
00:43:28,520 --> 00:43:32,880
Оно происходит от извлечений, и слово
пишется синтаксического дерева, т-р-и-е, из-за

982
00:43:32,880 --> 00:43:34,450
Конечно поиска звучит как синтаксического дерева.

983
00:43:34,450 --> 00:43:36,580
Но это история
слова синтаксического дерева.

984
00:43:36,580 --> 00:43:40,980
>> Так синтаксического дерева действительно своего рода дерево,
и это также игра на это слово.

985
00:43:40,980 --> 00:43:46,330
И хотя вы не можете достаточно увидеть его
с этой визуализации, синтаксического дерева является

986
00:43:46,330 --> 00:43:50,790
дерева структурированы, как семья дерево с
одним предком наверху и много

987
00:43:50,790 --> 00:43:54,530
из внуков и правнуков
как оставляет на дне.

988
00:43:54,530 --> 00:43:58,100
Но каждому узлу в виде дерева является массивом.

989
00:43:58,100 --> 00:44:00,680
И это в массиве - и давай
упрощать на мгновение - это

990
00:44:00,680 --> 00:44:04,600
массив, в этом случае, размер 26, где
каждый узел снова массив размера

991
00:44:04,600 --> 00:44:09,000
26, где нулевой элемент в этом
Массив представляет, а последний

992
00:44:09,000 --> 00:44:11,810
элемент в каждом таком
Массив представляет Z.

993
00:44:11,810 --> 00:44:15,520
>> Так что я предлагаю, то, что эти данные
структуре, известной как виде дерева, может быть

994
00:44:15,520 --> 00:44:17,600
использоваться также для хранения слов.

995
00:44:17,600 --> 00:44:21,740
Мы видели, как минуту назад, мы могли сохранить
словами, или в данном случае имена, и мы

996
00:44:21,740 --> 00:44:25,440
видели ранее, как мы можем хранить числа,
но если мы ориентируемся на имена или строки

997
00:44:25,440 --> 00:44:27,460
заметьте, что интересно.

998
00:44:27,460 --> 00:44:32,210
Я утверждаю, что имя Максвелла
Внутри этой структуры данных.

999
00:44:32,210 --> 00:44:33,730
Где вы видите Максвелла?

1000
00:44:33,730 --> 00:44:35,140
>> СТУДЕНТ: [неразборчиво].

1001
00:44:35,140 --> 00:44:36,240
>> Выступающий 1: на левой стороне.

1002
00:44:36,240 --> 00:44:39,910
Так что интересно, с этими данными
структура, а не магазин

1003
00:44:39,910 --> 00:44:46,200
Строка M-A-X-W-E-L-L обратной косой черты нулю, все
непрерывно, а не то, что вы делаете

1004
00:44:46,200 --> 00:44:46,890
состоит в следующем.

1005
00:44:46,890 --> 00:44:50,510
Если это так синтаксического дерева структуры данных,
каждый из которых узлов снова массива

1006
00:44:50,510 --> 00:44:54,650
и вы хотите сохранить Максвелла, сначала
индекс и так корня узла, так что

1007
00:44:54,650 --> 00:44:57,810
сказать, верхний узел,
в положении М, вправо, так

1008
00:44:57,810 --> 00:44:59,160
примерно в середине.

1009
00:44:59,160 --> 00:45:03,740
, А затем оттуда, вы будете следовать
указателя на дочерние узлы, так сказать.

1010
00:45:03,740 --> 00:45:06,150
Таким образом, в том смысле, дерево семьи,
вы будете следовать его вниз.

1011
00:45:06,150 --> 00:45:09,030
И это приведет вас к другому узлу
На левой стороне, которая является

1012
00:45:09,030 --> 00:45:10,540
просто еще один массив.

1013
00:45:10,540 --> 00:45:14,710
>> И потом, если вы хотите сохранить Максвелл,
вы найдете указатель, который представляет

1014
00:45:14,710 --> 00:45:16,430
, Которая является этот здесь.

1015
00:45:16,430 --> 00:45:17,840
Тогда вы идете к следующему узлу.

1016
00:45:17,840 --> 00:45:20,100
И обратите внимание - именно поэтому картины
немного обманывает -

1017
00:45:20,100 --> 00:45:21,990
этот узел выглядеть супер крошечные.

1018
00:45:21,990 --> 00:45:26,050
Но право это Y и Z.
Это просто автор усеченной

1019
00:45:26,050 --> 00:45:27,630
снимок так, чтобы вы на самом деле
видеть вещи.

1020
00:45:27,630 --> 00:45:30,400
В противном случае это фото
бы чрезвычайно широк.

1021
00:45:30,400 --> 00:45:36,180
Итак, теперь вы индекса в ячейку X, то
W, то Е, то L, то L. Тогда в чем

1022
00:45:36,180 --> 00:45:37,380
это любопытство?

1023
00:45:37,380 --> 00:45:41,250
>> Ну, если мы используем этот вид новых
взять на себя, как хранить строку в

1024
00:45:41,250 --> 00:45:44,500
структуры данных, вам все равно придется
существенно галочку в данных

1025
00:45:44,500 --> 00:45:47,250
структуры, что слово заканчивается.

1026
00:45:47,250 --> 00:45:50,830
Другими словами, каждый из этих узлов
так или иначе нужно помнить, что мы

1027
00:45:50,830 --> 00:45:53,500
фактически выполнили все эти указатели
и уезжают немного

1028
00:45:53,500 --> 00:45:58,370
хлебных крошек на дне здесь этого
Структура, чтобы указать, M-A-X-W-E-L-L представляет

1029
00:45:58,370 --> 00:46:00,230
действительно, в этой структуре данных.

1030
00:46:00,230 --> 00:46:02,040
>> Таким образом, можно сделать следующим образом.

1031
00:46:02,040 --> 00:46:06,810
Каждый из узлов на картинке мы просто
пила имеет один, массив размером 27.

1032
00:46:06,810 --> 00:46:10,550
И это сейчас 27, так как в P установить шесть,
мы фактически дают вам апостроф,

1033
00:46:10,550 --> 00:46:13,590
чтобы мы могли иметь имена, как O'Reilly
и другие с апострофа.

1034
00:46:13,590 --> 00:46:14,820
Но та же идея.

1035
00:46:14,820 --> 00:46:17,710
Каждый из этих элементов в
массива указывает на структуру

1036
00:46:17,710 --> 00:46:19,320
узел, так что просто узлом.

1037
00:46:19,320 --> 00:46:21,430
Так что это очень напоминает
нашей связанного списка.

1038
00:46:21,430 --> 00:46:24,550
>> А то у меня логическое, который я
называю слово, которое просто будет

1039
00:46:24,550 --> 00:46:29,120
верно, если слово заканчивается на этом
узел в дереве.

1040
00:46:29,120 --> 00:46:32,870
Это по сути, есть немного
треугольника мы видели несколько минут назад.

1041
00:46:32,870 --> 00:46:37,190
Так что, если слово заканчивается в этом узле в
Дерево, это слово поле будет правдой,

1042
00:46:37,190 --> 00:46:41,990
который концептуально галочки, или
мы рисуем этот треугольник, да там

1043
00:46:41,990 --> 00:46:44,080
это слово здесь.

1044
00:46:44,080 --> 00:46:45,120
>> Так что это синтаксического дерева.

1045
00:46:45,120 --> 00:46:48,540
А теперь вопрос в том, что
является время его работы?

1046
00:46:48,540 --> 00:46:49,930
Он большой O п?

1047
00:46:49,930 --> 00:46:51,410
Это что-то еще?

1048
00:46:51,410 --> 00:46:57,330
Ну, если вы п имена в этих данных
Структура, Максвелл всего лишь один из

1049
00:46:57,330 --> 00:47:02,330
них, что время работы
вставки или найти Максвелла?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Что время работы
вставки Максвелла?

1052
00:47:09,050 --> 00:47:11,740
Если есть другие названия N
уже в таблице?

1053
00:47:11,740 --> 00:47:12,507
Да?

1054
00:47:12,507 --> 00:47:15,429
>> СТУДЕНТ: [неразборчиво].

1055
00:47:15,429 --> 00:47:17,550
>> Выступающий 1: Да, это длина
имени, не так ли?

1056
00:47:17,550 --> 00:47:24,420
Так М-а-х-З-е-л-л поэтому он чувствует себя, как это
Алгоритм Big O семи.

1057
00:47:24,420 --> 00:47:26,580
Теперь, конечно, имя
будет варьироваться в длину.

1058
00:47:26,580 --> 00:47:27,380
Может быть, это краткое имя.

1059
00:47:27,380 --> 00:47:28,600
Может быть, это длинное имя.

1060
00:47:28,600 --> 00:47:33,390
Но то, что ключевым здесь является то, что
это постоянное число.

1061
00:47:33,390 --> 00:47:36,810
А может быть, это не совсем постоянное,
но Бог, если реально, в

1062
00:47:36,810 --> 00:47:41,570
словарь, там, наверное, некоторый предел
на количество букв в

1063
00:47:41,570 --> 00:47:43,820
имя человека в конкретной стране.

1064
00:47:43,820 --> 00:47:46,940
>> И таким образом, мы можем предположить, что
значение является постоянным.

1065
00:47:46,940 --> 00:47:47,750
Я не знаю, что это такое.

1066
00:47:47,750 --> 00:47:50,440
Это, наверное, больше, чем
мы думаем, что это такое.

1067
00:47:50,440 --> 00:47:52,720
Потому что всегда есть какой-нибудь угол
случае с сумасшедшим длинное имя.

1068
00:47:52,720 --> 00:47:56,360
Так что давайте называть это К, но она по-прежнему
постоянная предположительно, потому что каждый

1069
00:47:56,360 --> 00:48:00,190
назвать в мире, по крайней мере
конкретной страны, является то, что длина или

1070
00:48:00,190 --> 00:48:01,780
короче, так что это постоянно.

1071
00:48:01,780 --> 00:48:04,490
Но когда мы сказали что-то большое
O постоянного значения, что это такое

1072
00:48:04,490 --> 00:48:07,760
действительно эквивалентны?

1073
00:48:07,760 --> 00:48:10,420
Это действительно одно и то же
как говорят постоянное время.

1074
00:48:10,420 --> 00:48:11,530
>> Сейчас мы вроде обмана, верно?

1075
00:48:11,530 --> 00:48:15,340
Мы вроде используя некоторые теории
здесь, чтобы сказать, что хорошо, порядка К

1076
00:48:15,340 --> 00:48:17,450
действительно только порядка одной,
и это постоянное время.

1077
00:48:17,450 --> 00:48:18,200
Но это на самом деле.

1078
00:48:18,200 --> 00:48:22,550
Поскольку ключевое понимание в том, что
если мы имеем п имена уже в этом

1079
00:48:22,550 --> 00:48:26,010
структуру данных, и мы вставляем Максвелл,
это количество времени, которое требуется нам

1080
00:48:26,010 --> 00:48:29,530
вставить Максвелла на всех пострадавших
по тому, как много других людей

1081
00:48:29,530 --> 00:48:31,100
в структуре данных?

1082
00:48:31,100 --> 00:48:31,670
Не похоже, чтобы быть.

1083
00:48:31,670 --> 00:48:36,280
Если бы я был миллиард больше элементов в этой
дерева, а затем вставить Максвеллом

1084
00:48:36,280 --> 00:48:38,650
Он на всех пострадавших?

1085
00:48:38,650 --> 00:48:39,050
Нет.

1086
00:48:39,050 --> 00:48:42,950
И это в отличие от любого дня данные
структур, которые мы видели до сих пор, где

1087
00:48:42,950 --> 00:48:46,820
время работы вашего алгоритма
совершенно не зависит от того, сколько

1088
00:48:46,820 --> 00:48:51,430
материал или еще не был
В этой структуре данных.

1089
00:48:51,430 --> 00:48:54,650
>> И так с этим дает вам сейчас
возможность установить шесть р, которая будет

1090
00:48:54,650 --> 00:48:58,310
снова связано с осуществлением собственного
проверка орфографии, чтения в 150 000

1091
00:48:58,310 --> 00:49:01,050
словами, как лучше сохранить эту
не обязательно является очевидным.

1092
00:49:01,050 --> 00:49:04,030
И хотя я стремился найти
Святой Грааль, я не

1093
00:49:04,030 --> 00:49:05,330
утверждают, что это синтаксического дерева.

1094
00:49:05,330 --> 00:49:09,810
В самом деле, Хеш-таблицу можно очень хорошо
оказаться гораздо более эффективным.

1095
00:49:09,810 --> 00:49:10,830
Но это только -

1096
00:49:10,830 --> 00:49:14,620
это только одна из проектных решений
Вы должны сделать.

1097
00:49:14,620 --> 00:49:18,920
>> Но в заключение давайте 50 или около того
секунды, чтобы взглянуть на то, что лежит

1098
00:49:18,920 --> 00:49:22,190
впереди на следующей неделе и далее мы переходим
из этой командной строки

1099
00:49:22,190 --> 00:49:26,220
С миром, если на веб-программы вещей
основан и языков, как PHP и

1100
00:49:26,220 --> 00:49:30,350
JavaScript и сам Интернет,
протоколов, таких как HTTP, которые у вас есть

1101
00:49:30,350 --> 00:49:32,870
само собой разумеющимся, в течение многих лет
сейчас, и каждый набрал больше

1102
00:49:32,870 --> 00:49:34,440
день, пожалуй, и не видел.

1103
00:49:34,440 --> 00:49:37,420
И мы начнем отогните
слоях Что такое Интернет.

1104
00:49:37,420 --> 00:49:40,650
А что это за код, который
лежит в основе сегодняшней инструментов.

1105
00:49:40,650 --> 00:49:43,230
Так 50 секунд этот тизер здесь.

1106
00:49:43,230 --> 00:49:46,570
Я даю вам Воины Сети.

1107
00:49:46,570 --> 00:49:51,370
>> [ВОСПРОИЗВЕДЕНИЕ ВИДЕО]

1108
00:49:51,370 --> 00:49:56,764
>> -Он пришел с сообщением.

1109
00:49:56,764 --> 00:50:00,687
С протоколом все свое.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Он пришел в мир жестоких брандмауэров,
безразличными маршрутизаторы, и опасности далеко

1112
00:50:19,780 --> 00:50:22,600
хуже, чем смерть.

1113
00:50:22,600 --> 00:50:23,590
Он быстр.

1114
00:50:23,590 --> 00:50:25,300
Он сильный.

1115
00:50:25,300 --> 00:50:27,700
Он TCPIP.

1116
00:50:27,700 --> 00:50:30,420
И у него есть ваш адрес.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Воины в Сети.

1119
00:50:34,590 --> 00:50:35,290
>> [КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ]

1120
00:50:35,290 --> 00:50:38,070
>> Выступающий 1: То есть, как в интернете
будем работать на следующей неделе.

1121
00:50:38,070 --> 00:50:40,406