1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[МУЗЫКА ИГРАЕТ]

3
00:00:11,137 --> 00:00:12,220
David J. МАЛАН: Хорошо.

4
00:00:12,220 --> 00:00:13,950
Это CS50.

5
00:00:13,950 --> 00:00:18,560
Это пять неделе продолжал, и мы
есть хорошие новости и плохие новости.

6
00:00:18,560 --> 00:00:21,140
Так Хорошей новостью является то, что CS50
запускает в эту пятницу.

7
00:00:21,140 --> 00:00:24,430
Если вы хотели бы присоединиться к нам,
направиться в обычной URL здесь.

8
00:00:24,430 --> 00:00:28,670
не Даже лучшие новости, не лекция
предстоящий понедельник 13-го.

9
00:00:28,670 --> 00:00:31,970
Чуть менее лучшего новости,
викторина нуля в следующую среду.

10
00:00:31,970 --> 00:00:33,840
Подробнее можно
нашел по этому адресу здесь.

11
00:00:33,840 --> 00:00:36,340
И в ближайшие пару дней
мы будем заполняя пробелы

12
00:00:36,340 --> 00:00:39,234
с относительно номеров
что мы зарезервировали.

13
00:00:39,234 --> 00:00:41,400
Лучше новость заключается в том, что буду
быть курс всей отзыв

14
00:00:41,400 --> 00:00:43,570
сессия в ближайшую
Понедельник вечером.

15
00:00:43,570 --> 00:00:46,270
Оставайтесь с нами, чтобы Курса
сайт для размещения и деталей.

16
00:00:46,270 --> 00:00:49,290
Разделы, даже если он является
праздник, также встретится также.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Лучший новости, лекции в следующую пятницу.

19
00:00:52,940 --> 00:00:56,220
Так что это традиция, которую мы
есть, в соответствии с учебной программе.

20
00:00:56,220 --> 00:00:58,100
Просто-- это будет удивительно.

21
00:00:58,100 --> 00:01:02,510
Вы увидите вещи, как
структуры данных постоянной времени

22
00:01:02,510 --> 00:01:04,730
и хэш-таблицы, деревья и пытается.

23
00:01:04,730 --> 00:01:07,150
И мы будем говорить о проблемах дня рождения.

24
00:01:07,150 --> 00:01:09,440
Целая куча вещей
ждет в следующую пятницу.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Хорошо.

27
00:01:12,200 --> 00:01:13,190
Во всяком случае.

28
00:01:13,190 --> 00:01:17,080
>> Так напомним, что мы были
упором на этой картине то, что

29
00:01:17,080 --> 00:01:18,980
внутри памяти нашего компьютера.

30
00:01:18,980 --> 00:01:22,875
Так памяти или оперативной памяти, где программы
существуют в то время как вы работаете их.

31
00:01:22,875 --> 00:01:25,215
Если вы дважды щелкните
значок, чтобы запустить некоторые программы

32
00:01:25,215 --> 00:01:27,520
или дважды щелкните
значок, чтобы открыть файл,

33
00:01:27,520 --> 00:01:30,430
он загружен с жесткого
диск или твердотельный накопитель

34
00:01:30,430 --> 00:01:34,190
в оперативной памяти, памяти произвольного доступа, где
он живет, пока питание не отключится,

35
00:01:34,190 --> 00:01:36,700
крышка ноутбука закрывается,
или выходе из программы.

36
00:01:36,700 --> 00:01:38,960
>> Теперь, когда память, из
которые вы, вероятно,

37
00:01:38,960 --> 00:01:41,950
1 гигабайт в эти дни, 2
гигабайт, или даже намного больше,

38
00:01:41,950 --> 00:01:44,420
как правило, выложены
по заданной программе

39
00:01:44,420 --> 00:01:47,170
в этом виде прямоугольной
Концептуальная модель

40
00:01:47,170 --> 00:01:50,860
в результате чего мы имеем стек на дне
и кучу других вещей на самом верху.

41
00:01:50,860 --> 00:01:53,140
Дело на самом верху
мы видели на этой картинке

42
00:01:53,140 --> 00:01:55,670
раньше, но не говорил о
это так называемый текстовый сегмент.

43
00:01:55,670 --> 00:01:58,419
Сегмент текста просто причудливый способ
сказать нули и те, которые

44
00:01:58,419 --> 00:02:01,150
составить свой фактический скомпилированную программу.

45
00:02:01,150 --> 00:02:03,910
>> Итак, когда вы дважды щелкните
Microsoft Word на Mac или ПК,

46
00:02:03,910 --> 00:02:08,030
или при запуске точку слэш Марио на
Linux компьютер в вашем окне терминала,

47
00:02:08,030 --> 00:02:12,460
нули и единицы, которые составляют
Слово или Марио временно хранятся

48
00:02:12,460 --> 00:02:16,610
в оперативной памяти компьютера в так называемый
текстовый сегмент для конкретной программы.

49
00:02:16,610 --> 00:02:19,080
Ниже, что идет инициализация
и неинициализированные данные.

50
00:02:19,080 --> 00:02:22,655
Это такие вещи, как глобальные переменные,
что мы не использовали многие,

51
00:02:22,655 --> 00:02:24,910
но иногда мы в
имел глобальные переменные

52
00:02:24,910 --> 00:02:28,819
или статически определен строки,
закодирована такие слова, как "привет"

53
00:02:28,819 --> 00:02:31,860
, которые не приняты в от пользователя
которые жестко в вашу программу.

54
00:02:31,860 --> 00:02:34,230
>> Теперь, на дне мы
есть так называемый стеком.

55
00:02:34,230 --> 00:02:37,665
И стек, до сих пор, мы были
используя для каких видов целей?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Что стек используется для?

58
00:02:40,997 --> 00:02:41,160
Да?

59
00:02:41,160 --> 00:02:42,070
>> Аудитория: Функции.

60
00:02:42,070 --> 00:02:43,320
>> David J. МАЛАН: Для функций?

61
00:02:43,320 --> 00:02:44,980
В каком смысле для функций?

62
00:02:44,980 --> 00:02:48,660
>> АУДИТОРИЯ: Когда вы вызываете функцию,
Аргументы копируются в стек.

63
00:02:48,660 --> 00:02:49,660
>> David J. МАЛАН: Точно.

64
00:02:49,660 --> 00:02:52,650
При вызове функции, ее
Аргументы копируются в стек.

65
00:02:52,650 --> 00:02:56,330
Поэтому любые иксы или Y сайт или сайт или B,
что вы передаете в функцию

66
00:02:56,330 --> 00:02:58,680
временно поставить на
так называемый стеком,

67
00:02:58,680 --> 00:03:02,000
как одного из Анненберг
Столовая лотки, а также вещи,

68
00:03:02,000 --> 00:03:03,190
как локальных переменных.

69
00:03:03,190 --> 00:03:06,290
Если ваша функция Foo или подкачки
Функция иметь локальные переменные,

70
00:03:06,290 --> 00:03:08,602
как темп, те два
в конечном итоге в стеке.

71
00:03:08,602 --> 00:03:11,560
Теперь, мы не будем слишком много говорить о
им, но эти переменные окружения

72
00:03:11,560 --> 00:03:15,690
внизу мы увидели некоторое время назад, когда
Я был возиться с клавиатуры один день

73
00:03:15,690 --> 00:03:20,050
и я начал доступа вещи
как агду 100 или агду 1000,

74
00:03:20,050 --> 00:03:22,320
просто elements-- я забываю
numbers-- но что

75
00:03:22,320 --> 00:03:24,330
не должны были быть доступны мне.

76
00:03:24,330 --> 00:03:26,581
Мы начали видеть некоторые
фанки символы на экране.

77
00:03:26,581 --> 00:03:28,330
Это были так называемые
переменные окружения

78
00:03:28,330 --> 00:03:32,390
как глобальных параметров для личных
Программа или для моего компьютера, а не

79
00:03:32,390 --> 00:03:37,090
связаны с недавней
ошибка, что мы обсуждали,

80
00:03:37,090 --> 00:03:39,670
Контузия, что было
житья довольно много компьютеров.

81
00:03:39,670 --> 00:03:42,960
>> Теперь, наконец, в современном центре внимания
мы в конечном счете быть в куче.

82
00:03:42,960 --> 00:03:44,864
Это еще один кусок памяти.

83
00:03:44,864 --> 00:03:47,030
И принципиально все это
память тот же самый материал.

84
00:03:47,030 --> 00:03:48,040
Это то же самое оборудование.

85
00:03:48,040 --> 00:03:49,956
Мы только вид
лечения различных кластеров

86
00:03:49,956 --> 00:03:51,460
байтов для различных целей.

87
00:03:51,460 --> 00:03:56,540
Куча также будет где
переменные и памяти, что вы спрашиваете

88
00:03:56,540 --> 00:03:58,810
от операционной системы
временно сохраняется.

89
00:03:58,810 --> 00:04:01,890
>> Но есть своего рода проблемы
здесь, как и картина предполагает.

90
00:04:01,890 --> 00:04:05,261
Мы-то есть два
корабли около сталкиваться.

91
00:04:05,261 --> 00:04:08,010
Потому что, как вы используете все больше и больше
стека, и, как мы видим сегодня,

92
00:04:08,010 --> 00:04:11,800
вперед, как вы используете все больше и больше
куча, безусловно, плохие вещи могут случиться.

93
00:04:11,800 --> 00:04:15,054
И в самом деле, мы можем вызвать, что
намеренно или ненамеренно.

94
00:04:15,054 --> 00:04:16,970
Так в кульминации последнего
раз был эта программа,

95
00:04:16,970 --> 00:04:20,570
которые не служат любая функциональная
Цель кроме продемонстрировать

96
00:04:20,570 --> 00:04:24,750
как вам, как плохой парень действительно может принять
Преимущество ошибок в чужой программе

97
00:04:24,750 --> 00:04:28,460
и взять на себя программу или даже
Весь компьютерная система или сервер.

98
00:04:28,460 --> 00:04:31,660
Так что просто заглянуть ненадолго, вам
заметить, что основные внизу

99
00:04:31,660 --> 00:04:34,510
принимает в командной строке
Аргументы, как за ARGV.

100
00:04:34,510 --> 00:04:38,480
И это имеет вызов функции F,
существенно безымянный функция называется

101
00:04:38,480 --> 00:04:40,250
е, и это прохождение в ARGV [1].

102
00:04:40,250 --> 00:04:43,960
>> Поэтому, что бы слово пользователь вводит в на
выводится после имени этой программы,

103
00:04:43,960 --> 00:04:49,310
а затем эта произвольная функция до
сверху, е, занимает в строке, AKA символ *,

104
00:04:49,310 --> 00:04:51,720
как мы начали обсуждать,
и он просто называет его "бар".

105
00:04:51,720 --> 00:04:53,310
Но мы могли бы называть его иначе.

106
00:04:53,310 --> 00:04:57,470
А потом он заявляет, внутри
из F, массив символов

107
00:04:57,470 --> 00:04:59,930
называется c-- 12 таких символов.

108
00:04:59,930 --> 00:05:03,580
>> Теперь, по истории, которую я рассказывал
минуту назад, когда в памяти

109
00:05:03,580 --> 00:05:06,720
является с, или те, 12
символы будет в конечном итоге?

110
00:05:06,720 --> 00:05:07,570
Просто чтобы быть ясно.

111
00:05:07,570 --> 00:05:08,070
Да?

112
00:05:08,070 --> 00:05:08,590
>> АУДИТОРИЯ: На стеке.

113
00:05:08,590 --> 00:05:09,420
>> David J. МАЛАН: На стеке.

114
00:05:09,420 --> 00:05:10,720
Так с является локальной переменной.

115
00:05:10,720 --> 00:05:14,079
Мы просим 12 символов или 12 байт.

116
00:05:14,079 --> 00:05:16,120
Те собираются в конечном итоге
на так называемом стеке.

117
00:05:16,120 --> 00:05:18,530
Теперь, наконец, это другая функция
что на самом деле очень полезно,

118
00:05:18,530 --> 00:05:20,571
но мы на самом деле не используется
это сами, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Это означает строку копию, но
только русские буквы, п символов.

121
00:05:25,200 --> 00:05:31,990
Так п символов будет
копируется из бара в с.

122
00:05:31,990 --> 00:05:32,980
А сколько?

123
00:05:32,980 --> 00:05:34,110
Длина панели.

124
00:05:34,110 --> 00:05:36,330
Таким образом, другими словами, что
одна линия, strncopy,

125
00:05:36,330 --> 00:05:39,500
собирается копировать
официально запретить и в.

126
00:05:39,500 --> 00:05:42,340
>> Теперь, просто вид предвидеть
Мораль этой истории,

127
00:05:42,340 --> 00:05:44,750
что потенциально проблематично здесь?

128
00:05:44,750 --> 00:05:49,710
Даже при том, что мы проверяем длину
из бара, и передавая ее в strncopy,

129
00:05:49,710 --> 00:05:53,145
что ваши кишки говорю вам это
еще сломано об этой программе?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Да?

132
00:05:55,220 --> 00:05:57,491
>> АУДИТОРИЯ: Не включает
комната для нулевого символа.

133
00:05:57,491 --> 00:05:59,990
David J. МАЛАН: Не включает
комната для нулевого символа.

134
00:05:59,990 --> 00:06:02,073
Потенциально, в отличие от
Прежняя практика, мы даже не

135
00:06:02,073 --> 00:06:04,810
есть так много как плюс 1 к
разместить эту нулевой символ.

136
00:06:04,810 --> 00:06:06,649
Но это еще хуже, чем это.

137
00:06:06,649 --> 00:06:07,940
Что еще мы не в состоянии сделать?

138
00:06:07,940 --> 00:06:08,432
Да?

139
00:06:08,432 --> 00:06:09,307
>> АУДИТОРИЯ: [неразборчиво]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
David J. МАЛАН: Прекрасно.

142
00:06:16,440 --> 00:06:18,490
Мы жестко 12 довольно произвольно.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Это не так много
проблема, но тот факт,

145
00:06:21,330 --> 00:06:25,630
что мы даже не проверяя, если
длина панели меньше 12,

146
00:06:25,630 --> 00:06:28,530
в этом случае он будет
безопасно положить его в памяти

147
00:06:28,530 --> 00:06:30,260
называется с, что мы выделено.

148
00:06:30,260 --> 00:06:32,960
Действительно, если бар как
20 символов,

149
00:06:32,960 --> 00:06:39,010
Эта функция по-видимому, копирование
20 символов из бара в С, тем самым

150
00:06:39,010 --> 00:06:41,310
принимать, по меньшей мере 8 байтов
что это не должно быть.

151
00:06:41,310 --> 00:06:42,690
Вот подтекст здесь.

152
00:06:42,690 --> 00:06:44,347
>> Таким образом, в краткосрочной, сломанной программы.

153
00:06:44,347 --> 00:06:45,180
Не такое уж большое дело.

154
00:06:45,180 --> 00:06:46,360
Может быть, вы получите ошибку сегментации.

155
00:06:46,360 --> 00:06:47,651
Мы все были ошибки в программах.

156
00:06:47,651 --> 00:06:50,196
Мы все могли бы иметь ошибки
в программах прямо сейчас.

157
00:06:50,196 --> 00:06:51,320
Но то, что подразумевается?

158
00:06:51,320 --> 00:06:54,390
Ну, вот в масштабе в версии
что картина памяти моего компьютера.

159
00:06:54,390 --> 00:06:56,230
Это дно моей стека.

160
00:06:56,230 --> 00:06:59,644
И действительно, в самом низу это то, что
называется родителем рутина стек, причудливый способ

161
00:06:59,644 --> 00:07:00,560
сказать, что это основной.

162
00:07:00,560 --> 00:07:03,772
Так что тот, кто называется функцией
е, что мы говорим о.

163
00:07:03,772 --> 00:07:05,230
Таким образом, это в нижней части стопки.

164
00:07:05,230 --> 00:07:06,640
Обратный адрес нечто новое.

165
00:07:06,640 --> 00:07:08,810
Это всегда было там,
всегда был в этой картине.

166
00:07:08,810 --> 00:07:10,440
Мы просто никогда не обращал внимание на нее.

167
00:07:10,440 --> 00:07:15,290
Потому что получается, то, как с работы является
что, когда одна функция вызывает другую,

168
00:07:15,290 --> 00:07:18,780
не только сделать, чтобы аргументы, что
Функция получить в стек,

169
00:07:18,780 --> 00:07:22,470
не только сделать местные функция сайт
Переменные получить в стек,

170
00:07:22,470 --> 00:07:26,820
то, что называется обратный адрес
также получает положить в стек.

171
00:07:26,820 --> 00:07:33,330
В частности, если основные вызовы Фу, основные сайт
собственный адрес в памяти, бык-то,

172
00:07:33,330 --> 00:07:38,240
эффективно получает положить в стек
так что, когда е делается выполнение которого

173
00:07:38,240 --> 00:07:43,630
знает, где переходить туда, в тексте
сегмент для того, чтобы продолжить выполнение.

174
00:07:43,630 --> 00:07:47,760
>> Так что, если мы здесь концептуально,
в основной, то F вызывается.

175
00:07:47,760 --> 00:07:50,200
Как е знаю, кто
в ручной контроль задней?

176
00:07:50,200 --> 00:07:52,020
Ну, это немного
крошка в красном здесь,

177
00:07:52,020 --> 00:07:54,978
называется обратный адрес, он просто
проверяет, что это за адрес возврата?

178
00:07:54,978 --> 00:07:57,039
О, позвольте мне перейти обратно на главную здесь.

179
00:07:57,039 --> 00:07:59,080
И это немного
из упрощением,

180
00:07:59,080 --> 00:08:00,750
потому нулей и единиц
для магистрали технически

181
00:08:00,750 --> 00:08:01,967
здесь в техническом сегменте.

182
00:08:01,967 --> 00:08:03,800
Но это идея. е
просто должен знать, что

183
00:08:03,800 --> 00:08:06,680
туда, где контроль в конечном счете восходит.

184
00:08:06,680 --> 00:08:09,790
>> Но то, как компьютеры
уже давно выложены вещи

185
00:08:09,790 --> 00:08:12,320
как локальных переменных и
Аргументы, как это.

186
00:08:12,320 --> 00:08:17,180
Таким образом, в верхней части этой картины в
синий кадр стека для F, так что все

187
00:08:17,180 --> 00:08:19,630
из памяти, что F
специально использует.

188
00:08:19,630 --> 00:08:22,990
Так, соответственно, заметить, что
Бар в этой картине.

189
00:08:22,990 --> 00:08:23,980
Бар был его аргумент.

190
00:08:23,980 --> 00:08:27,240
И мы утверждали, что аргументы
Функции получить в стек.

191
00:08:27,240 --> 00:08:29,910
И с, конечно,
Также в этой картине.

192
00:08:29,910 --> 00:08:33,520
>> И только для обозначений целей,
заметить в верхнем левом углу

193
00:08:33,520 --> 00:08:37,020
то, что было бы с кронштейном 0 и
затем слегка вниз, вправо

194
00:08:37,020 --> 00:08:38,220
является с кронштейна 11.

195
00:08:38,220 --> 00:08:41,240
Итак, другими словами, вы можете себе представить
что есть сетка байт

196
00:08:41,240 --> 00:08:44,380
есть, первый из которых
верхний левый, нижний из которых

197
00:08:44,380 --> 00:08:48,360
последний из этих 12 байт.

198
00:08:48,360 --> 00:08:49,930
>> Но теперь попробуйте для быстрой перемотки вперед.

199
00:08:49,930 --> 00:08:55,580
Что должно произойти, если мы передадим
в струнной баре, это больше, чем с?

200
00:08:55,580 --> 00:08:59,130
И мы не проверка, если
это действительно больше, чем 12.

201
00:08:59,130 --> 00:09:03,146
Какая часть этой картины собирается
потерян байт 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
точка точка точка, 11, а затем
плохо, 12, 13 через 19?

203
00:09:07,890 --> 00:09:11,820
Что произойдет здесь,
если вы вывести из заказа

204
00:09:11,820 --> 00:09:14,790
что с кронштейн 0 находится на вершине
и с кронштейн 11 является своего рода вниз

205
00:09:14,790 --> 00:09:15,812
в порядке?

206
00:09:15,812 --> 00:09:16,796
Да?

207
00:09:16,796 --> 00:09:19,260
>> АУДИТОРИЯ: Ну, это будет
перезаписать символ * бар.

208
00:09:19,260 --> 00:09:22,260
>> David J. МАЛАН: Да, это выглядит как
Вы собираетесь перезаписать символ * бар.

209
00:09:22,260 --> 00:09:26,245
И что еще хуже, если вы отправляете в самом деле долго
Строка, вы могли бы даже переписать то, что?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
В качестве обратного адреса.

212
00:09:28,570 --> 00:09:31,380
Что еще раз, так же, как
крошка сказать программе, где

213
00:09:31,380 --> 00:09:34,060
вернуться к тому, когда F
делается при вызове.

214
00:09:34,060 --> 00:09:37,140
>> Так что плохие парни, как правило, делают
, если они приходят через программы

215
00:09:37,140 --> 00:09:41,290
что они любопытно ли
для использования, багги таким образом

216
00:09:41,290 --> 00:09:43,550
что он или она может принимать
Преимущество этой ошибки,

217
00:09:43,550 --> 00:09:45,720
как правило, они не получают
это правильно с первого раза.

218
00:09:45,720 --> 00:09:48,590
Они просто начать передачу, например,
случайные строки в вашей программе,

219
00:09:48,590 --> 00:09:50,260
ли на клавиатуре,
или откровенно они, вероятно,

220
00:09:50,260 --> 00:09:52,740
написать небольшую программу для всего
автоматически генерировать строки,

221
00:09:52,740 --> 00:09:55,430
и начать стучать по вашей программы,
отправка в большом количестве различных входов

222
00:09:55,430 --> 00:09:56,340
на разных длинах.

223
00:09:56,340 --> 00:09:58,990
>> Как только ваши сбои программ,
что удивительная вещь.

224
00:09:58,990 --> 00:10:01,020
Потому что это означает, что он
или она обнаружила

225
00:10:01,020 --> 00:10:02,660
, что, вероятно, действительно ошибка.

226
00:10:02,660 --> 00:10:05,830
И тогда они могут получить более умный
и начать фокусировку более узко

227
00:10:05,830 --> 00:10:07,420
о том, как использовать эту ошибку.

228
00:10:07,420 --> 00:10:11,480
В частности, то, что он или она могли бы
сделать, это отправить, в лучшем случае, привет.

229
00:10:11,480 --> 00:10:12,210
Ничего страшного.

230
00:10:12,210 --> 00:10:14,750
Это строка, это достаточно коротким.

231
00:10:14,750 --> 00:10:18,100
Но что, если он или она посылает,
и мы будем обобщать его как,

232
00:10:18,100 --> 00:10:20,890
Нападение code-- так нулей
и те, которые делают вещи

233
00:10:20,890 --> 00:10:25,150
как RM-РФ, что удалить все
с жесткого диска или рассылки спама

234
00:10:25,150 --> 00:10:27,000
или иначе атаковать машину?

235
00:10:27,000 --> 00:10:29,570
>> Таким образом, если каждый из них
Письма просто представляет,

236
00:10:29,570 --> 00:10:32,380
концептуально, атака, атака,
атака, атака, некоторые плохие код

237
00:10:32,380 --> 00:10:36,410
что кто-то написал, но
если это лицо достаточно умен,

238
00:10:36,410 --> 00:10:40,790
чтобы не только включать в себя все
из тех RM-RFS, но и

239
00:10:40,790 --> 00:10:46,100
есть свои последние несколько байт
быть число, которое соответствует

240
00:10:46,100 --> 00:10:50,540
в адрес его
или ее собственный код атака

241
00:10:50,540 --> 00:10:53,820
что он или она прошла в только
путем предоставления ему в командной строке,

242
00:10:53,820 --> 00:10:58,760
Вы можете эффективно обмануть компьютер
в замечая при е делается выполнения,

243
00:10:58,760 --> 00:11:02,400
о, это время для меня, чтобы перейти
назад к красному обратного адреса.

244
00:11:02,400 --> 00:11:06,070
Но так как он или она имеет так или иначе
перекрываются, что обратный адрес

245
00:11:06,070 --> 00:11:09,602
с их собственным числом,
и они достаточно умны,

246
00:11:09,602 --> 00:11:11,560
чтобы настроили, что
число для обозначения, как вы

247
00:11:11,560 --> 00:11:13,740
см в супер верхней
левый угол там,

248
00:11:13,740 --> 00:11:18,020
Фактический адрес в компьютерной годов
Память о некоторых из их вредоносный код,

249
00:11:18,020 --> 00:11:21,740
плохой парень может обмануть компьютер
в выполнении его или ее собственный код.

250
00:11:21,740 --> 00:11:23,700
>> И, что код, опять же, может быть что угодно.

251
00:11:23,700 --> 00:11:26,120
Это обычно называется
Оболочка код, который является только

252
00:11:26,120 --> 00:11:29,030
способ сказать, что это не
как правило, такая простая вещь, как RM-РФ.

253
00:11:29,030 --> 00:11:32,340
Это на самом деле-то как Bash,
или фактическое программа, которая дает ему

254
00:11:32,340 --> 00:11:37,230
или ее программный контроль, чтобы выполнить
все остальное, что они хотят.

255
00:11:37,230 --> 00:11:40,210
Короче говоря, все это
происходит от того простого факта,

256
00:11:40,210 --> 00:11:44,490
что эта ошибка участие не проверяя
границы вашего массива.

257
00:11:44,490 --> 00:11:47,250
И потому, что пути
Компьютеры работа в том, что они

258
00:11:47,250 --> 00:11:49,430
используют стек от
эффективно, концептуально,

259
00:11:49,430 --> 00:11:54,830
Нижняя дальше вверх, но то элементы
Вы нажимаете на стек расти сверху вниз,

260
00:11:54,830 --> 00:11:56,624
это невероятно проблематично.

261
00:11:56,624 --> 00:11:58,290
Теперь, есть способы обойти это.

262
00:11:58,290 --> 00:12:00,800
И, честно говоря, есть языки
с которой обойти это.

263
00:12:00,800 --> 00:12:03,100
Java имеет иммунитет, например,
к этому конкретному вопросу.

264
00:12:03,100 --> 00:12:04,110
Потому что они не дают вам указатели.

265
00:12:04,110 --> 00:12:05,943
Они не дают вам
прямые адреса памяти.

266
00:12:05,943 --> 00:12:08,560
Так что с этой властью, что у нас
к чему прикасаться в памяти

267
00:12:08,560 --> 00:12:11,580
мы хотим приходит, по общему признанию, большой риск.

268
00:12:11,580 --> 00:12:12,430
>> Так что следите.

269
00:12:12,430 --> 00:12:14,596
Если, честно говоря, в течение нескольких месяцев
или лет, чтобы прийти в любое время

270
00:12:14,596 --> 00:12:17,740
Вы читаете о некоторых эксплуатации
программы или сервера,

271
00:12:17,740 --> 00:12:22,370
если вы никогда не увидит намек-то
как атаки переполнения буфера,

272
00:12:22,370 --> 00:12:25,390
или переполнение стека и другой тип
атаки, близкого по духу,

273
00:12:25,390 --> 00:12:28,770
сколько внушает сайта
назвать, если вы его знаете,

274
00:12:28,770 --> 00:12:33,170
это все говорю о просто
переполнены размер некоторым характером

275
00:12:33,170 --> 00:12:36,200
массив или некоторый массив в целом.

276
00:12:36,200 --> 00:12:38,822
Любые вопросы, то, по этому поводу?

277
00:12:38,822 --> 00:12:39,780
Не пытайтесь повторить это дома.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Хорошо.

280
00:12:42,300 --> 00:12:47,270
Так таНос до сих пор был наш новый
Друг в том, что мы можем выделить память

281
00:12:47,270 --> 00:12:50,540
что мы не обязательно знать, в
заранее, что мы хотим, чтобы мы не должны

282
00:12:50,540 --> 00:12:52,920
на жесткий код в нашу
номера программ, как 12.

283
00:12:52,920 --> 00:12:55,550
Как только пользователь говорит нам, сколько
Данные он или она хочет, чтобы вход,

284
00:12:55,550 --> 00:12:58,000
мы можем Malloc что много памяти.

285
00:12:58,000 --> 00:13:01,484
>> Так таНос оказывается, чтобы
Степень мы использовали его,

286
00:13:01,484 --> 00:13:03,900
явно последний раз, а затем
вы, ребята уже используют его

287
00:13:03,900 --> 00:13:08,160
для GetString неосознанно для
несколько недель, все памяти Malloc в

288
00:13:08,160 --> 00:13:09,820
исходит из так называемой динамической памяти.

289
00:13:09,820 --> 00:13:13,852
И вот почему GetString, например,
может выделить память динамически

290
00:13:13,852 --> 00:13:16,060
не зная, что вы
собирается ввести заранее,

291
00:13:16,060 --> 00:13:21,520
вручить Вам указатель на эту память,
и что память еще ваш держать,

292
00:13:21,520 --> 00:13:24,080
даже после GetString отдачу.

293
00:13:24,080 --> 00:13:27,450
Потому напомним, в конце концов, что
стек постоянно идет вверх и вниз,

294
00:13:27,450 --> 00:13:27,950
вверх и вниз.

295
00:13:27,950 --> 00:13:30,230
И как только она идет
вниз, что означает любую память

296
00:13:30,230 --> 00:13:33,030
эта функция используется должны
не быть использован в других местах.

297
00:13:33,030 --> 00:13:34,570
Это значения мусорные сейчас.

298
00:13:34,570 --> 00:13:36,120
>> Но куча здесь.

299
00:13:36,120 --> 00:13:39,360
И, что приятно об таНос является то, что
когда таНос выделяет память здесь,

300
00:13:39,360 --> 00:13:42,070
это не повлияло, для
Большая часть, стеком.

301
00:13:42,070 --> 00:13:46,000
И поэтому любая функция может получить доступ
памяти, которая была malloc'd,

302
00:13:46,000 --> 00:13:49,120
даже на функцию как GetString,
даже после того, как он будет возвращен.

303
00:13:49,120 --> 00:13:51,700
>> Теперь, обратное таНос бесплатно.

304
00:13:51,700 --> 00:13:53,900
И в самом деле, это правило вам
нужно, чтобы начать принятия

305
00:13:53,900 --> 00:13:58,950
это любой, любой, в любое время вы используете таНос
вы сами должны использовать бесплатно, в конце концов,

306
00:13:58,950 --> 00:14:00,280
в тот же указатель.

307
00:14:00,280 --> 00:14:03,289
Все это время мы писали
багги, код ошибки, по многим причинам.

308
00:14:03,289 --> 00:14:05,580
Но один из которых был
с использованием библиотеки CS50, который

309
00:14:05,580 --> 00:14:09,010
Сам намеренно
багги, это утечек памяти.

310
00:14:09,010 --> 00:14:11,410
Каждый раз, когда вы назвали GetString
в течение последних нескольких недель

311
00:14:11,410 --> 00:14:13,870
мы просим операционные
Система, Linux, на память.

312
00:14:13,870 --> 00:14:15,780
И вы ни разу не дали его обратно.

313
00:14:15,780 --> 00:14:17,730
И это не в
практиковать, хорошая вещь.

314
00:14:17,730 --> 00:14:20,330
>> И Valgrind, один из
инструменты, введенные в Pset 4,

315
00:14:20,330 --> 00:14:22,900
это все о помогая вам
Теперь найти ошибки, как, что.

316
00:14:22,900 --> 00:14:27,060
Но, к счастью для Pset 4 вам не нужно
использовать библиотеку CS50 или GetString.

317
00:14:27,060 --> 00:14:31,220
Поэтому любые ошибки, связанные с памятью являются
в конечном счете, будет свой собственный.

318
00:14:31,220 --> 00:14:34,060
>> Так таНос больше, чем просто
удобна для этой цели.

319
00:14:34,060 --> 00:14:37,420
Мы можем на самом деле сейчас решить
принципиально разные проблемы,

320
00:14:37,420 --> 00:14:41,640
и принципиально решить проблемы более
эффективно, как за неделю нуля обещание.

321
00:14:41,640 --> 00:14:44,720
До сих пор это самая сексуальная
Структура данных у нас были.

322
00:14:44,720 --> 00:14:47,804
И по структуре данных я просто имею в виду
способ концептуализации памяти

323
00:14:47,804 --> 00:14:50,720
таким образом, что выходит за рамки просто говорю,
Это Int, это символ.

324
00:14:50,720 --> 00:14:52,930
Мы можем начать кластера вещей вместе.

325
00:14:52,930 --> 00:14:54,460
>> Так массив выглядит следующим образом.

326
00:14:54,460 --> 00:14:57,270
И то, что было ключевым в о
Массив является то, что она дает вам

327
00:14:57,270 --> 00:14:59,724
спина к спине куски
памяти, каждый из которых

328
00:14:59,724 --> 00:15:02,765
будет того же типа, Int,
Int, Int, Int, или символ, символ, символ,

329
00:15:02,765 --> 00:15:03,330
символ.

330
00:15:03,330 --> 00:15:04,496
Но есть несколько недостатков.

331
00:15:04,496 --> 00:15:06,570
Это, например, это
массив размером шесть.

332
00:15:06,570 --> 00:15:10,650
Предположим, что вы заполните этот массив с шестью
числа и затем, по тем или иным причинам,

333
00:15:10,650 --> 00:15:13,187
ваш пользователь хочет дать
Вы седьмой номер.

334
00:15:13,187 --> 00:15:14,020
Где вы положили его?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Какой же выход, если у вас есть
создали массив в стеке,

337
00:15:18,990 --> 00:15:22,030
например, только с неделю
два обозначения, что мы ввели,

338
00:15:22,030 --> 00:15:23,730
квадратных скобок с рядом внутри?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Ну, у вас есть шесть
Цифры в этих коробках.

341
00:15:27,260 --> 00:15:28,530
Что бы ваши инстинкты быть?

342
00:15:28,530 --> 00:15:29,973
Где бы вы хотели сказать?

343
00:15:29,973 --> 00:15:30,860
>> АУДИТОРИЯ: [неразборчиво]

344
00:15:30,860 --> 00:15:31,315
>> David J. МАЛАН: Извините?

345
00:15:31,315 --> 00:15:32,380
>> АУДИТОРИЯ: Положите его на конце.

346
00:15:32,380 --> 00:15:33,796
>> David J. МАЛАН: Положите его на конце.

347
00:15:33,796 --> 00:15:35,880
Так что просто на правый,
вне этой рамки.

348
00:15:35,880 --> 00:15:38,710
Какой бы хорошо, но это
Оказывается, вы не можете сделать это.

349
00:15:38,710 --> 00:15:41,350
Потому что, если вы не спросили
Для этого блока памяти,

350
00:15:41,350 --> 00:15:44,490
это может быть совпадением тот это
в настоящее время используется некоторой другой переменной

351
00:15:44,490 --> 00:15:45,030
в целом.

352
00:15:45,030 --> 00:15:49,210
Вспомните неделю или около того, когда мы заложили
из имен Zamyla и Дэвин и Гейба

353
00:15:49,210 --> 00:15:49,930
в памяти.

354
00:15:49,930 --> 00:15:51,638
Они были буквально
спина к спине к спине.

355
00:15:51,638 --> 00:15:53,550
Таким образом, мы не можем обязательно
доверять, что бы ни было

356
00:15:53,550 --> 00:15:55,800
здесь доступна для меня, чтобы использовать.

357
00:15:55,800 --> 00:15:56,990
>> Так, что еще вы могли бы сделать?

358
00:15:56,990 --> 00:16:00,282
Ну, раз понимая вас
нужен массив размером семь,

359
00:16:00,282 --> 00:16:02,490
вы могли бы просто создать
массив размером семь затем использовать

360
00:16:02,490 --> 00:16:05,950
цикл или время цикла,
скопировать его в новый массив,

361
00:16:05,950 --> 00:16:09,680
и потом как-то просто избавиться от
этот массив или просто отказаться от его использования.

362
00:16:09,680 --> 00:16:12,130
Но это не очень эффективно.

363
00:16:12,130 --> 00:16:15,340
Короче говоря, массивы не позволяют
динамически изменять размер.

364
00:16:15,340 --> 00:16:17,900
>> Итак, с одной стороны, вы получаете
произвольного доступа, что удивительно.

365
00:16:17,900 --> 00:16:20,108
Потому что это позволяет нам делать то,
как разделяй и властвуй,

366
00:16:20,108 --> 00:16:23,100
бинарный поиск, все из которых мы в
говорили о на экране здесь.

367
00:16:23,100 --> 00:16:24,950
Но вы рисуете себя в угол.

368
00:16:24,950 --> 00:16:27,810
Как только вы нажмете
конец вашего массива,

369
00:16:27,810 --> 00:16:29,980
что вам нужно сделать очень
дорогая операция

370
00:16:29,980 --> 00:16:33,910
или написать целую кучу кода
чтобы теперь иметь дело с этой проблемой.

371
00:16:33,910 --> 00:16:36,680
>> Так что, если вместо того, чтобы у нас были
то, что называется список,

372
00:16:36,680 --> 00:16:38,820
или связан список, в частности,?

373
00:16:38,820 --> 00:16:41,930
Что делать, если вместо того,
прямоугольники спина к спине к спине,

374
00:16:41,930 --> 00:16:45,730
у нас есть прямоугольники, которые оставляют немного
немного маневра между ними?

375
00:16:45,730 --> 00:16:49,670
И хотя я нарисовал это
изображение или адаптировать эту картинку

376
00:16:49,670 --> 00:16:54,696
от одного из текстов здесь, чтобы вернуться к
спина к спине очень организованно, на самом деле,

377
00:16:54,696 --> 00:16:56,820
один из этих прямоугольников
может быть здесь в памяти.

378
00:16:56,820 --> 00:16:58,028
Один из них может быть здесь.

379
00:16:58,028 --> 00:17:00,420
Один из них может быть здесь,
здесь и так далее.

380
00:17:00,420 --> 00:17:02,910
>> Но что, если мы рисовали,
в этом случае, стрелки

381
00:17:02,910 --> 00:17:05,650
что так или иначе связать их
прямоугольники вместе?

382
00:17:05,650 --> 00:17:08,170
Действительно, мы видели техническая
воплощение стрелкой.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Что мы использовали в последнее время
дней, что, под капотом,

385
00:17:13,710 --> 00:17:15,210
является представителем стрелкой?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Указатель, не так ли?

388
00:17:17,349 --> 00:17:19,780
>> Так что, если вместо
просто хранить номера,

389
00:17:19,780 --> 00:17:23,130
как 9, 17, 22, 26, 34,
что, если мы не сохраняется

390
00:17:23,130 --> 00:17:27,079
только номер, но указатель
рядом с каждой такой числа?

391
00:17:27,079 --> 00:17:30,690
Так что так же, как вы бы нить
иглу через целую кучу ткани,

392
00:17:30,690 --> 00:17:32,950
так или иначе связывая вещи
вместе, так же может

393
00:17:32,950 --> 00:17:35,550
мы с указателями, как
воплотился стрелками здесь,

394
00:17:35,550 --> 00:17:38,550
вид ткать вместе
эти отдельные прямоугольники

395
00:17:38,550 --> 00:17:41,780
путем эффективного использования указателя
Рядом с каждым номером, который

396
00:17:41,780 --> 00:17:46,065
указывает на некоторое следующего числа, что
указывает на, в свою очередь, некоторые следующий номер?

397
00:17:46,065 --> 00:17:47,940
Итак, другими словами, то, что
если мы на самом деле хотели

398
00:17:47,940 --> 00:17:49,820
реализовать нечто подобное?

399
00:17:49,820 --> 00:17:53,610
Ну, к сожалению, эти прямоугольники,
По крайней мере, один с 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
не и так далее, они больше не
хорошие квадраты с отдельных номеров.

401
00:17:57,040 --> 00:17:59,960
Дно, прямоугольник
Ниже 9, например,

402
00:17:59,960 --> 00:18:04,330
представляет, что должно
быть указателем, 32 бита.

403
00:18:04,330 --> 00:18:09,460
Теперь, я еще не в курсе любого типа данных
в С, что дает не только Int

404
00:18:09,460 --> 00:18:11,630
но указатель в целом.

405
00:18:11,630 --> 00:18:15,020
>> Так в чем же решение, если мы хотим
чтобы изобретать собственный ответ на этот?

406
00:18:15,020 --> 00:18:15,760
Да?

407
00:18:15,760 --> 00:18:16,640
>> АУДИТОРИЯ: [неразборчиво]

408
00:18:16,640 --> 00:18:17,360
>> David J. МАЛАН: Что это?

409
00:18:17,360 --> 00:18:17,880
>> АУДИТОРИЯ: Новая структура.

410
00:18:17,880 --> 00:18:19,590
>> David J. МАЛАН: Да, так почему
не мы создаем новую структуру,

411
00:18:19,590 --> 00:18:20,920
или в С, структуры?

412
00:18:20,920 --> 00:18:25,990
Мы видели структур и раньше, если кратко,
где мы имели дело со студенческой структуры

413
00:18:25,990 --> 00:18:27,780
как это, кто имел имя и дом.

414
00:18:27,780 --> 00:18:31,980
В Pset 3 прорыв вы использовали целый
куча structs-- GRect и GOvals

415
00:18:31,980 --> 00:18:34,810
, что Стэнфорд создал в
Кластер информация вместе.

416
00:18:34,810 --> 00:18:38,580
Так что, если мы возьмем эту же идею
ключевые слова "объявлений типов" и "структурой,"

417
00:18:38,580 --> 00:18:42,890
а затем некоторые студент-конкретные вещи,
и развиваться это в следующем:

418
00:18:42,890 --> 00:18:46,210
ЬурейеЕ структуры node-- и узел
только очень общее информатика

419
00:18:46,210 --> 00:18:49,980
Термин-то в структуре данных,
Контейнер в структуре данных.

420
00:18:49,980 --> 00:18:53,900
Узел я утверждаю, будет иметь
Int N, очень простой,,

421
00:18:53,900 --> 00:18:58,810
а затем еще немного загадочно,
это вторая линия, структура узла * следующий.

422
00:18:58,810 --> 00:19:01,300
Но в менее технических терминов,
что это за вторая линия

423
00:19:01,300 --> 00:19:02,980
кода в фигурных скобках?

424
00:19:02,980 --> 00:19:03,737
Да?

425
00:19:03,737 --> 00:19:04,851
>> АУДИТОРИЯ: [неразборчиво]

426
00:19:04,851 --> 00:19:06,600
David J. МАЛАН:
указатель на другой узел.

427
00:19:06,600 --> 00:19:09,910
Так по общему признанию, синтаксис немного загадочным.

428
00:19:09,910 --> 00:19:13,250
Но если вы читаете это буквально,
Следующий это имя переменной.

429
00:19:13,250 --> 00:19:14,410
Что такое тип данных?

430
00:19:14,410 --> 00:19:18,206
Это немного многословен на этот раз,
но это тип структура узла *.

431
00:19:18,206 --> 00:19:22,960
Каждый раз, когда мы видели нечто звезду, что
означает, что это указатель на этого типа данных.

432
00:19:22,960 --> 00:19:26,810
Так что в следующий, по-видимому
указатель в структуре узла.

433
00:19:26,810 --> 00:19:28,310
>> Теперь, что это структура узла?

434
00:19:28,310 --> 00:19:31,044
Ну, заметили вы видите тех,
те же слова в правом верхнем углу.

435
00:19:31,044 --> 00:19:33,960
И в самом деле, вы также видите слово
"Узел" сюда в левом нижнем углу.

436
00:19:33,960 --> 00:19:35,640
И это на самом деле просто удобство.

437
00:19:35,640 --> 00:19:39,930
Обратите внимание, что в нашем определении студенческой
есть слово "студент" только один раз.

438
00:19:39,930 --> 00:19:42,510
И это потому, что студент
объект не был самоссылающиеся.

439
00:19:42,510 --> 00:19:45,340
Там нет ничего внутри студента
что нужно, чтобы указать на другого студента,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Это было бы своего рода
странно в реальном мире.

442
00:19:47,630 --> 00:19:50,880
>> Но с узлом в связан
Список, мы делаем хотите узел

443
00:19:50,880 --> 00:19:53,970
быть ссылочной к подобного объекта.

444
00:19:53,970 --> 00:19:57,900
И так заметить изменение здесь не
только то, что внутри фигурных скобок.

445
00:19:57,900 --> 00:20:00,800
Но мы добавляем слово «узел»
вверху, а также

446
00:20:00,800 --> 00:20:02,930
добавив его на дно
вместо "студента".

447
00:20:02,930 --> 00:20:06,000
И это только техническая деталь
таким образом, что, опять же, ваша структура данных,

448
00:20:06,000 --> 00:20:11,380
может быть самоссылающиеся, так что
Узел может указывать на другой такой узел.

449
00:20:11,380 --> 00:20:13,840
>> Так что же это, в конечном счете
будет означать для нас?

450
00:20:13,840 --> 00:20:17,560
Ну, один, этот материал внутри
это содержание нашего узла.

451
00:20:17,560 --> 00:20:19,360
Эта вещь здесь,
вверху справа, это просто так

452
00:20:19,360 --> 00:20:20,860
что, опять же, мы можем обратиться к себе.

453
00:20:20,860 --> 00:20:23,401
А потом внешний материал,
даже при том, что узел является новый термин,

454
00:20:23,401 --> 00:20:25,500
возможно, это все еще
же, как студент и что

455
00:20:25,500 --> 00:20:27,520
был под капотом в SPL.

456
00:20:27,520 --> 00:20:31,095
>> Так что, если мы сейчас хотели начать
реализации этого связанный список,

457
00:20:31,095 --> 00:20:33,220
как мы могли бы перевести
как то так, чтобы кодировать?

458
00:20:33,220 --> 00:20:35,350
Ну, давайте просто посмотрим,
Примером программы, которые

459
00:20:35,350 --> 00:20:36,840
фактически использует связанный список.

460
00:20:36,840 --> 00:20:40,870
Среди сегодняшних кода распределения
является программа под названием Список нулевой.

461
00:20:40,870 --> 00:20:44,980
И если я запускаю это я создал супер
простой графический интерфейс, графический интерфейс пользователя,

462
00:20:44,980 --> 00:20:46,460
но это действительно просто PRINTF.

463
00:20:46,460 --> 00:20:50,930
И теперь я дал себе несколько меню
options-- Удалить, Вставить, Поиск,

464
00:20:50,930 --> 00:20:51,750
и Traverse.

465
00:20:51,750 --> 00:20:52,630
И Quit.

466
00:20:52,630 --> 00:20:55,970
Таковы лишь общие операции по
Структура данных известны как список ссылок.

467
00:20:55,970 --> 00:20:58,409
>> Теперь, Удалить собирается
удалить номер из списка.

468
00:20:58,409 --> 00:21:00,200
Вставьте собирается добавить
число в список.

469
00:21:00,200 --> 00:21:02,181
Поиск будет выглядеть
числа в списке.

470
00:21:02,181 --> 00:21:04,930
И траверс только причудливый способ
сказать, ходить по списку,

471
00:21:04,930 --> 00:21:06,245
распечатать его, но это так.

472
00:21:06,245 --> 00:21:07,720
Не меняйте его в любом случае.

473
00:21:07,720 --> 00:21:08,570
>> Так давайте попробуем это.

474
00:21:08,570 --> 00:21:10,160
Давайте пойдем дальше и ввести 2.

475
00:21:10,160 --> 00:21:12,710
А потом я собираюсь
введите номер, говорят 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
И теперь моя программа просто
запрограммирован сказать, список теперь 9.

478
00:21:17,480 --> 00:21:20,190
Теперь, если я пойду вперед и
у Вставьте снова, пусть

479
00:21:20,190 --> 00:21:23,680
мне идти вперед и уменьшения масштаба и введите в 17.

480
00:21:23,680 --> 00:21:25,770
Теперь мой список 9, затем 17.

481
00:21:25,770 --> 00:21:27,750
Если я вставить снова, давайте пропустим один.

482
00:21:27,750 --> 00:21:32,400
Вместо 22, как за картины мы в
смотрел на здесь, позвольте мне перейти вперед

483
00:21:32,400 --> 00:21:34,630
и вставить 26 следующая.

484
00:21:34,630 --> 00:21:36,230
Так что я собираюсь набрать 26.

485
00:21:36,230 --> 00:21:37,755
Этот список, как я ожидаю.

486
00:21:37,755 --> 00:21:40,630
Но сейчас, просто чтобы посмотреть, если этого кода
собирается быть гибким, позвольте мне теперь

487
00:21:40,630 --> 00:21:43,520
Тип 22, которая, по меньшей мере
концептуально, если мы

488
00:21:43,520 --> 00:21:46,520
Имея это сортируются, которые действительно
будет другая цель прямо сейчас,

489
00:21:46,520 --> 00:21:48,690
должны пойти в период с 17 по 26.

490
00:21:48,690 --> 00:21:50,270
Так я попал Enter.

491
00:21:50,270 --> 00:21:51,380
В самом деле, что работает.

492
00:21:51,380 --> 00:21:54,950
И вот теперь позвольте мне вставить
наконец, за картины, 34.

493
00:21:54,950 --> 00:21:55,450
>> Хорошо.

494
00:21:55,450 --> 00:21:58,980
Так что на данный позвольте мне предусматривают, что
Удалить и Traverse и поиск сделать,

495
00:21:58,980 --> 00:21:59,760
В самом деле, работать.

496
00:21:59,760 --> 00:22:04,180
На самом деле, если я запустить поиск, давайте
поиск по номеру 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Было установлено, 22.

498
00:22:05,010 --> 00:22:07,580
Так что то, что это
Программа Список Ноль делает.

499
00:22:07,580 --> 00:22:10,230
>> Но что на самом деле происходит
на который реализует это?

500
00:22:10,230 --> 00:22:14,530
Ну, сначала я, возможно, придется, и в самом деле
У меня есть, файл с именем list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
И где-то там это
линия, ЬурейеЕ, структура узла,

503
00:22:20,690 --> 00:22:24,850
то у меня есть фигурные скобки, Int N, и
затем struct-- что было определение?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Структура, узел рядом.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Так что мы должны звезду.

508
00:22:31,045 --> 00:22:33,420
Теперь технически мы попадаем в
привычка рисунок его здесь.

509
00:22:33,420 --> 00:22:35,670
Вы можете увидеть учебники и
онлайн ссылки сделать это там.

510
00:22:35,670 --> 00:22:36,660
Это функционально эквивалентны.

511
00:22:36,660 --> 00:22:37,980
На самом деле, это немного более типичным.

512
00:22:37,980 --> 00:22:40,563
Но я буду последователен с чем
мы сделали в прошлый раз и сделать это.

513
00:22:40,563 --> 00:22:42,350
И тогда, наконец, я собираюсь сделать это.

514
00:22:42,350 --> 00:22:45,550
>> Так в файле заголовка
где, в list0.h

515
00:22:45,550 --> 00:22:49,200
сегодня это определение структуры,
и, возможно, некоторые другие вещи.

516
00:22:49,200 --> 00:22:52,580
Между тем в list0c есть
будет несколько вещей.

517
00:22:52,580 --> 00:22:54,740
Но мы собираемся просто
начать и не закончить это.

518
00:22:54,740 --> 00:22:59,690
List0.h это файл я хочу
включить в моей C файл.

519
00:22:59,690 --> 00:23:03,910
А потом в определенный момент я
придется Int, главная, аннулированию.

520
00:23:03,910 --> 00:23:06,530
А потом я собираюсь
есть некоторые к делу здесь.

521
00:23:06,530 --> 00:23:10,620
Я также собираюсь иметь
Прототип, как пустот, поиск, INT,

522
00:23:10,620 --> 00:23:13,610
н, чья цель в жизни
искать элемента.

523
00:23:13,610 --> 00:23:18,310
А потом сюда я утверждаю в
сегодняшняя код, недействительными, поиск, Int, н,

524
00:23:18,310 --> 00:23:21,020
нет запятой, но открытые фигурные скобки.

525
00:23:21,020 --> 00:23:25,049
А теперь я хочу, чтобы так или иначе искать
для элемента в этом списке.

526
00:23:25,049 --> 00:23:27,340
Но мы не имеем достаточно
информация на экране еще.

527
00:23:27,340 --> 00:23:29,800
У меня на самом деле не
представлял сам список.

528
00:23:29,800 --> 00:23:33,070
Так один из способов мы могли бы реализовать
связанный список в программе

529
00:23:33,070 --> 00:23:37,520
будет я вроде хочу делать то,
как декларируют связано список здесь.

530
00:23:37,520 --> 00:23:40,520
Для простоты я собираюсь сделать
эта глобальная, хотя в целом мы

531
00:23:40,520 --> 00:23:41,645
не должны делать этого слишком много.

532
00:23:41,645 --> 00:23:43,260
Но это упростит этот пример.

533
00:23:43,260 --> 00:23:45,890
Поэтому я хочу заявить
связанный список здесь.

534
00:23:45,890 --> 00:23:47,010
Теперь, как я мог бы это сделать?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Вот картина связанного списка.

537
00:23:50,750 --> 00:23:53,030
И я действительно не
известно на данный момент хау

538
00:23:53,030 --> 00:23:56,710
Я собираюсь идти о представляющих
так много вещей, только с одним

539
00:23:56,710 --> 00:23:58,040
переменная в памяти.

540
00:23:58,040 --> 00:23:59,160
Но вспомните момент.

541
00:23:59,160 --> 00:24:00,830
Все это время у нас было
строки, которые затем

542
00:24:00,830 --> 00:24:02,913
показал, что массивы
символов, которые мы затем

543
00:24:02,913 --> 00:24:05,740
показали, чтобы быть просто указатель
на первый символ

544
00:24:05,740 --> 00:24:08,890
в массив символов
который нулем.

545
00:24:08,890 --> 00:24:13,530
Так по этой логике, и с этим
фото вид посева ваши мысли,

546
00:24:13,530 --> 00:24:17,964
на что еще нам на самом деле писать в наш
Код для представления связанный список?

547
00:24:17,964 --> 00:24:21,130
Сколько из этой информации нам нужно
захватить в C код, вы можете сказать?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Да?

550
00:24:23,154 --> 00:24:24,738
>> АУДИТОРИЯ: Нам нужен указатель на узел.

551
00:24:24,738 --> 00:24:26,237
David J. МАЛАН: указатель на узел.

552
00:24:26,237 --> 00:24:29,320
В частности, какой узел бы ваша
инстинкты бы хранить указатель на?

553
00:24:29,320 --> 00:24:30,026
>> АУДИТОРИЯ: Первый узел.

554
00:24:30,026 --> 00:24:31,942
>> David J. МАЛАН: Да,
вероятно, только первый.

555
00:24:31,942 --> 00:24:34,030
И обратите внимание, первый
узел другую форму.

556
00:24:34,030 --> 00:24:37,690
Это только половина размер структуры,
потому что это действительно только указатель.

557
00:24:37,690 --> 00:24:44,650
Так что вы действительно можете сделать, это объявить
связанный список, чтобы иметь тип узла *.

558
00:24:44,650 --> 00:24:47,780
И давайте просто называть его первым
и инициализировать его до нуля.

559
00:24:47,780 --> 00:24:49,910
Так нуль, опять же, идет
в картину здесь.

560
00:24:49,910 --> 00:24:53,620
Мало того, что используется в качестве нуль, как специальная
Возвращаемое значение для того, как GetString

561
00:24:53,620 --> 00:24:57,770
и таНос, нуль также нулевая
указатель, отсутствие указателя,

562
00:24:57,770 --> 00:24:58,430
если вы будете.

563
00:24:58,430 --> 00:25:00,309
Это просто означает, ничто не упомянут тут.

564
00:25:00,309 --> 00:25:02,100
Теперь первый, я мог бы
назвал это ничего.

565
00:25:02,100 --> 00:25:04,200
Я мог бы назвать его "список"
или любое количество других вещей.

566
00:25:04,200 --> 00:25:06,960
Но я звоню его "первым", так что
он выстраивается в линию с этой картины.

567
00:25:06,960 --> 00:25:10,280
Так же, как струны может быть представлено
с адресом его первого байта,

568
00:25:10,280 --> 00:25:11,280
так может связанный список.

569
00:25:11,280 --> 00:25:13,480
И мы увидим другие данные
структуры можно представить

570
00:25:13,480 --> 00:25:16,700
только с одним указателем,
32-разрядная стрелка, указывая

571
00:25:16,700 --> 00:25:18,740
на первом узле в структуре.

572
00:25:18,740 --> 00:25:20,340
>> Но теперь давайте предвидеть проблему.

573
00:25:20,340 --> 00:25:23,230
Если я только вспомнив
в моей программе адресной

574
00:25:23,230 --> 00:25:27,220
из первого узла, первый
прямоугольник в этой структуре данных,

575
00:25:27,220 --> 00:25:31,760
что лучше быть дело о
Реализация остальных моем списке?

576
00:25:31,760 --> 00:25:35,820
Что ключевой деталью, что происходит
обеспечить это на самом деле работает?

577
00:25:35,820 --> 00:25:39,250
И "на самом деле работает" я
значит, так же, как строки,

578
00:25:39,250 --> 00:25:42,180
позволяет нам перейти от первого символа
в имени Давина ко второму,

579
00:25:42,180 --> 00:25:44,755
в третьих,
четвертый, до самого конца,

580
00:25:44,755 --> 00:25:47,880
как мы знаем, когда мы находимся в конце
связанного списка, который выглядит следующим?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Когда это нуль.

583
00:25:50,660 --> 00:25:53,640
И я представлял этот вид как
как инженер-электрик мощи,

584
00:25:53,640 --> 00:25:56,420
с маленьким заземления
символ, своего рода.

585
00:25:56,420 --> 00:25:58,246
Но это просто означает, нуль в этом случае.

586
00:25:58,246 --> 00:26:00,370
Вы можете нарисовать его любое количество
способов, но этот автор

587
00:26:00,370 --> 00:26:02,800
произошло использовать этот символ здесь.

588
00:26:02,800 --> 00:26:06,260
>> Пока мы нанизывая
все эти узлы вместе,

589
00:26:06,260 --> 00:26:08,600
только вспоминая, где
Первый, до тех пор,

590
00:26:08,600 --> 00:26:11,760
как мы ставим специальный символ на
самый последний узел в списке,

591
00:26:11,760 --> 00:26:15,130
и мы будем использовать нуль, потому что это
то, что мы имеем в распоряжении, чтобы нас,

592
00:26:15,130 --> 00:26:16,480
этот список будет завершена.

593
00:26:16,480 --> 00:26:20,190
И даже если бы я только дать вам указатель
первый элемент, вы, программист,

594
00:26:20,190 --> 00:26:22,486
безусловно, может получить доступ к остальным его.

595
00:26:22,486 --> 00:26:24,360
Но давайте пусть ваши умы
побродить немного,

596
00:26:24,360 --> 00:26:26,140
если они не уже
довольно wandered-- что

597
00:26:26,140 --> 00:26:28,723
будет время работы
найдя ничего в этом списке?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Черт возьми, это большая O н,
что не плохо, справедливости ради.

600
00:26:33,470 --> 00:26:34,800
Но это является линейным.

601
00:26:34,800 --> 00:26:37,980
Мы отказались от того, что функция
массивов путем перемещения более

602
00:26:37,980 --> 00:26:43,130
к этой картине динамически
переплетаются или связаны узлы?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Мы отказались от случайного доступа.

605
00:26:46,687 --> 00:26:48,770
Массив приятно, потому что
математически все

606
00:26:48,770 --> 00:26:50,340
является спина к спине к спине к спине.

607
00:26:50,340 --> 00:26:52,370
Даже при том, что этой картине
выглядит красиво, и даже

608
00:26:52,370 --> 00:26:55,830
хотя это выглядит как этих узлов
красиво разнесены, в реальности

609
00:26:55,830 --> 00:26:56,830
они могут быть где угодно.

610
00:26:56,830 --> 00:27:01,590
Ox1, Ox50, Ox123, Ox99, эти
узлы могут быть где угодно.

611
00:27:01,590 --> 00:27:05,960
Потому таНос делает выделить память
из кучи, но в любом месте в куче.

612
00:27:05,960 --> 00:27:09,080
Вам не обязательно знать, что это
будет спина к спине к спине.

613
00:27:09,080 --> 00:27:12,460
И так эта картина в Реальности
не собирается быть столь значительной.

614
00:27:12,460 --> 00:27:16,140
>> Так он собирается занять немного
работать над реализацией этой функции.

615
00:27:16,140 --> 00:27:17,880
Так давайте реализуем поиск сейчас.

616
00:27:17,880 --> 00:27:20,250
И мы увидим рода
умный способ сделать это.

617
00:27:20,250 --> 00:27:24,660
Так что, если я функция поиска и
Я дал переменной, число п

618
00:27:24,660 --> 00:27:28,490
искать, мне нужно знать,
Новый синтаксис для поиска внутри

619
00:27:28,490 --> 00:27:32,400
структуры, это
указал на, чтобы найти н.

620
00:27:32,400 --> 00:27:33,210
Так давайте сделаем это.

621
00:27:33,210 --> 00:27:36,030
>> Итак, сначала я пойду
вперед и объявить узел *.

622
00:27:36,030 --> 00:27:39,400
И я буду называть его
указатель, только по соглашению.

623
00:27:39,400 --> 00:27:41,710
И я собираюсь, чтобы подготовить его к первому.

624
00:27:41,710 --> 00:27:43,770
И теперь я могу это сделать
В несколькими способами.

625
00:27:43,770 --> 00:27:45,436
Но я собираюсь принять общий подход.

626
00:27:45,436 --> 00:27:50,180
В то время как указатель не равен
нуль, и это допустимый синтаксис.

627
00:27:50,180 --> 00:27:54,550
И это как раз означает, выполните следующие действия, так
Пока вы не указывая ни перед чем.

628
00:27:54,550 --> 00:27:55,800
Что я хочу сделать?

629
00:27:55,800 --> 00:28:01,939
>> Если указатель точка п, позвольте мне вернуться
в том, что, equals-- равно что?

630
00:28:01,939 --> 00:28:03,105
Какое значение я ищу?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Фактическая п, который был принят в.

633
00:28:06,590 --> 00:28:09,020
Так вот еще одна особенность
С и многие языки.

634
00:28:09,020 --> 00:28:13,705
Даже при том, что структуры называется узлом
имеет значение п, полностью законной

635
00:28:13,705 --> 00:28:17,530
также есть местный аргумент
или переменная называется н.

636
00:28:17,530 --> 00:28:20,085
Потому что даже мы, с
человеческие глаза, можно выделить

637
00:28:20,085 --> 00:28:22,087
что это п-видимому
отличается от этого п.

638
00:28:22,087 --> 00:28:23,420
Поскольку синтаксис отличается.

639
00:28:23,420 --> 00:28:26,211
У вас есть точка и указатель,
в то время как этот не имеет ничего подобного.

640
00:28:26,211 --> 00:28:27,290
Так что это в порядке.

641
00:28:27,290 --> 00:28:29,120
Это нормально, чтобы называть их те же самые вещи.

642
00:28:29,120 --> 00:28:32,380
>> Если я вам найти это, я
захочет сделать что-то

643
00:28:32,380 --> 00:28:35,000
как сообщить, что мы нашли н.

644
00:28:35,000 --> 00:28:37,930
И мы оставим это как
комментировать или псевдокод код.

645
00:28:37,930 --> 00:28:40,190
Остальное, и вот
интересная часть, что

646
00:28:40,190 --> 00:28:47,320
я хочу делать, если текущий узел
не содержащий п, что я забочусь о?

647
00:28:47,320 --> 00:28:50,700
Как мне добиться следующее?

648
00:28:50,700 --> 00:28:53,710
Если мой палец на
момент PTR, и это

649
00:28:53,710 --> 00:28:55,920
указывая на то, что
Первый указывая на,

650
00:28:55,920 --> 00:28:59,290
как я могу пошевелить пальцем
на следующий узел в коде?

651
00:28:59,290 --> 00:29:01,915
Ну, что крошка мы
собирается следовать в этом случае?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
АУДИТОРИЯ: [неразборчиво].

654
00:29:04,380 --> 00:29:05,630
David J. МАЛАН: Да, так что в следующий.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Так что, если я вернусь в мой
Код здесь, действительно, я

657
00:29:09,824 --> 00:29:12,990
собираюсь идти вперед и сказать, указатель, который
это лишь временное переменная-- это

658
00:29:12,990 --> 00:29:15,320
странное имя, PTR, но
это просто как temp--

659
00:29:15,320 --> 00:29:19,234
Я собираюсь установить указатель
равно какой указателя is--

660
00:29:19,234 --> 00:29:22,150
и опять же, это будет
небольшая детская коляска для moment-- точкой следующего.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Другими словами, я собираюсь принять мои
палец, который, указывая на этом узле

663
00:29:26,550 --> 00:29:31,247
здесь, и я собираюсь сказать, вы знаете,
что, взгляните на следующее поле

664
00:29:31,247 --> 00:29:33,330
и переместить палец в
там оно указывая на.

665
00:29:33,330 --> 00:29:35,163
И это будет
Повторяю, повторять, повторять.

666
00:29:35,163 --> 00:29:37,630
Но когда делает свой палец
прекратить делать вообще ничего?

667
00:29:37,630 --> 00:29:40,095
Как только что строка кода ударов в?

668
00:29:40,095 --> 00:29:40,970
АУДИТОРИЯ: [неразборчиво]

669
00:29:40,970 --> 00:29:43,060
David J. МАЛАН: Если точка а
указатель не равен нулю.

670
00:29:43,060 --> 00:29:44,900
В какой-то момент мой пальца
будет указывая на нуль

671
00:29:44,900 --> 00:29:47,070
и я собираюсь реализовать
это конец этого списка.

672
00:29:47,070 --> 00:29:48,910
Теперь, это немного
ложь для простоты.

673
00:29:48,910 --> 00:29:51,580
Получается, что даже при том, что мы
только что узнал эту точечную нотацию

674
00:29:51,580 --> 00:29:55,220
для структур, указатель не структура.

675
00:29:55,220 --> 00:29:56,580
PTR есть что?

676
00:29:56,580 --> 00:29:58,350
Просто, чтобы быть более nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Это указатель на узел.

679
00:30:01,360 --> 00:30:03,120
Это не сам узел.

680
00:30:03,120 --> 00:30:06,650
Если у меня не было звездой здесь, указатель
absolutely-- это узел.

681
00:30:06,650 --> 00:30:08,650
Это как недели один
Декларация переменной,

682
00:30:08,650 --> 00:30:10,120
хотя слово «узел» является новым.

683
00:30:10,120 --> 00:30:13,860
>> Но как только мы вводим
звезда, то теперь это указатель на узел.

684
00:30:13,860 --> 00:30:17,960
И, к сожалению, вы не можете использовать
точечной нотации для указателя.

685
00:30:17,960 --> 00:30:21,070
Вы должны использовать стрелку
обозначения, которые, поразительно,

686
00:30:21,070 --> 00:30:23,470
Впервые любой кусок
синтаксиса выглядит интуитивно понятным.

687
00:30:23,470 --> 00:30:25,245
Это буквально выглядит как стрела.

688
00:30:25,245 --> 00:30:26,370
И так, что это хорошая вещь.

689
00:30:26,370 --> 00:30:28,995
И здесь буквально
выглядит, как стрела.

690
00:30:28,995 --> 00:30:31,870
Так что я думаю, что это la-- я не
думаю, что я более-совершение здесь-- Я

691
00:30:31,870 --> 00:30:34,120
думаю, что это последний новый кусок
синтаксиса мы собираемся, чтобы увидеть.

692
00:30:34,120 --> 00:30:36,500
И к счастью, это действительно
немного более интуитивным.

693
00:30:36,500 --> 00:30:40,090
>> Теперь, для тех из вас, кто
возможно, предпочтут по-старому,

694
00:30:40,090 --> 00:30:42,550
Вы все еще можете использовать точечной нотации.

695
00:30:42,550 --> 00:30:45,380
Но в соответствии с понедельника
Разговор, мы сначала

696
00:30:45,380 --> 00:30:50,530
должны пойти туда, идти к тому, что
решения, а затем перейти в поле.

697
00:30:50,530 --> 00:30:51,897
Так что это тоже правильно.

698
00:30:51,897 --> 00:30:53,730
И, честно говоря, это
немного больше педантичным.

699
00:30:53,730 --> 00:30:56,530
Ты буквально говоря, разыменовать
указатель и пойти туда.

700
00:30:56,530 --> 00:30:59,320
Затем берем .n, поле называется н.

701
00:30:59,320 --> 00:31:01,370
Но, откровенно говоря, никто не хочет
ввести или прочитать это.

702
00:31:01,370 --> 00:31:03,620
И поэтому мир придумал
обозначение стрелка, которая

703
00:31:03,620 --> 00:31:06,980
эквивалентно, идентичны,
это просто синтаксический сахар.

704
00:31:06,980 --> 00:31:10,570
Так причудливый способ сказать это
выглядит лучше, или выглядит проще.

705
00:31:10,570 --> 00:31:12,296
>> Так что теперь я собираюсь сделать еще одну вещь.

706
00:31:12,296 --> 00:31:15,420
Я собираюсь сказать "перерыв" Как только я
обнаружили, что это так, я не продолжать искать для него.

707
00:31:15,420 --> 00:31:17,620
Но это суть
функции поиска.

708
00:31:17,620 --> 00:31:21,710
Но это намного легче, в
конец, не ходить через код.

709
00:31:21,710 --> 00:31:25,570
Это действительно формальное выполнение
поиска в сегодняшнем коде распределения.

710
00:31:25,570 --> 00:31:30,530
Осмелюсь сказать, что вставка не
особенно интересно идти через

711
00:31:30,530 --> 00:31:33,180
визуально, ни удалить, даже
при том, что в конце дня

712
00:31:33,180 --> 00:31:35,460
они сводятся к довольно
простые эвристики.

713
00:31:35,460 --> 00:31:36,330
>> Так давайте сделаем это.

714
00:31:36,330 --> 00:31:39,250
Если вы будете юмор меня здесь, я сделал
принести кучу стрессовых шаров.

715
00:31:39,250 --> 00:31:40,620
Я принес кучу цифр.

716
00:31:40,620 --> 00:31:46,562
И мы могли бы получить только несколько добровольцев
представлять 9, 17, 20, 22, 29 и 34?

717
00:31:46,562 --> 00:31:48,270
Так по существу все
кто здесь сегодня.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Это был один, два, три,
четыре, пять, шесть человек.

720
00:31:52,760 --> 00:31:55,740
И я попросил go-- увидеть, нет
один в спину поднимает свои руки.

721
00:31:55,740 --> 00:32:01,910
ОК, раз, два, три, четыре,
five-- позвольте мне загрузить balance-- шесть.

722
00:32:01,910 --> 00:32:03,051
ОК, вы шесть давай до.

723
00:32:03,051 --> 00:32:04,050
Мы нужны другие люди.

724
00:32:04,050 --> 00:32:05,460
Мы принесли дополнительные шары стресс.

725
00:32:05,460 --> 00:32:08,200
И если бы вы могли, для
только на мгновение, линия

726
00:32:08,200 --> 00:32:10,490
сами до всего
любите эту фотографию здесь.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Хорошо.

729
00:32:15,959 --> 00:32:17,125
Давайте посмотрим, как тебя зовут?

730
00:32:17,125 --> 00:32:17,550
>> АУДИТОРИЯ: Андрей.

731
00:32:17,550 --> 00:32:18,800
>> David J. МАЛАН: Андрей,
вы номер 9.

732
00:32:18,800 --> 00:32:19,540
Приятно познакомиться.

733
00:32:19,540 --> 00:32:20,400
Держи.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
АУДИТОРИЯ: Джен.

736
00:32:22,176 --> 00:32:22,662
David J. МАЛАН: Джен.

737
00:32:22,662 --> 00:32:23,162
Дэвид.

738
00:32:23,162 --> 00:32:23,765
Номер 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Да?

741
00:32:25,450 --> 00:32:26,400
>> АУДИТОРИЯ: Я Юля.

742
00:32:26,400 --> 00:32:26,980
>> David J. МАЛАН: Юлия, Дэвид.

743
00:32:26,980 --> 00:32:27,545
Количество 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
АУДИТОРИЯ: Кристиан.

746
00:32:29,340 --> 00:32:30,715
David J. МАЛАН: Кристиан, Дэвид.

747
00:32:30,715 --> 00:32:31,541
Количество 22.

748
00:32:31,541 --> 00:32:32,040
И?

749
00:32:32,040 --> 00:32:32,649
>> АУДИТОРИЯ: JP.

750
00:32:32,649 --> 00:32:33,440
David J. МАЛАН: JP.

751
00:32:33,440 --> 00:32:34,880
Количество 29.

752
00:32:34,880 --> 00:32:37,080
Так идти вперед и получить в-- Ой-ой.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Ой-ой.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
В режиме ожидания.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Кто-нибудь есть маркер?

760
00:32:43,682 --> 00:32:44,890
АУДИТОРИЯ: У меня есть Шулера.

761
00:32:44,890 --> 00:32:45,660
David J. МАЛАН: Вы получили шулера?

762
00:32:45,660 --> 00:32:46,159
Хорошо.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
И кто-нибудь есть листок бумаги?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Сохраните лекцию.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Подойди.

769
00:32:55,362 --> 00:32:56,320
АУДИТОРИЯ: У нас есть его.

770
00:32:56,320 --> 00:32:57,600
David J. МАЛАН: Мы получили его?

771
00:32:57,600 --> 00:32:58,577
Хорошо, спасибо.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Здесь мы идем.

774
00:33:02,520 --> 00:33:03,582
Был ли этот от вас?

775
00:33:03,582 --> 00:33:04,540
Вы просто спасли день.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Так 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Хорошо.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Я неправильно 29, но хорошо.

782
00:33:14,890 --> 00:33:15,720
Продолжай.

783
00:33:15,720 --> 00:33:18,114
Хорошо, я дам вам
Ваш перо обратно на мгновение.

784
00:33:18,114 --> 00:33:19,280
Поэтому у нас есть эти люди здесь.

785
00:33:19,280 --> 00:33:20,330
Давайте один другой.

786
00:33:20,330 --> 00:33:23,750
Гейб, ты хочешь играть
Первый элемент здесь?

787
00:33:23,750 --> 00:33:25,705
Мы нуждаемся в вас, чтобы указать
на этих прекрасных людей.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Так 9, 17, 20, 22, отсортируйте
из 29, а затем 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Разве мы теряем кого?

792
00:33:33,325 --> 00:33:33,950
У меня есть 34.

793
00:33:33,950 --> 00:33:36,730
Где did-- ОК, кто хочет быть 34?

794
00:33:36,730 --> 00:33:37,605
ОК, давай до, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Ладно, это будет
стоит кульминация.

797
00:33:41,220 --> 00:33:41,550
Как тебя зовут?

798
00:33:41,550 --> 00:33:42,040
>> АУДИТОРИЯ: Питер.

799
00:33:42,040 --> 00:33:43,456
>> David J. МАЛАН: Питер, давай до.

800
00:33:43,456 --> 00:33:46,810
Хорошо, так вот
целая куча узлов.

801
00:33:46,810 --> 00:33:49,060
Каждый из вас, ребята, представляет
один из этих прямоугольников.

802
00:33:49,060 --> 00:33:51,930
И Гейб, немного странный
человек из, представляет первый.

803
00:33:51,930 --> 00:33:54,850
Таким образом, его указатель немного меньше
на экране, чем все остальные.

804
00:33:54,850 --> 00:33:58,120
И в этом случае, каждый из вашей левой
руки собирается либо направлены вниз,

805
00:33:58,120 --> 00:34:01,085
тем самым представляя нуль, так
только отсутствие указателя,

806
00:34:01,085 --> 00:34:03,210
или это собирается быть указывая
в узле рядом с вами.

807
00:34:03,210 --> 00:34:05,440
>> Так что сейчас, если вы украшают
будьте подобны картинке

808
00:34:05,440 --> 00:34:07,585
здесь, идти вперед и точка
друг на друга, с Gabe

809
00:34:07,585 --> 00:34:11,030
в частности, указывая на
номер 9 для представления списка.

810
00:34:11,030 --> 00:34:14,050
ОК, и число 34, левая рука
надо просто указывая на полу.

811
00:34:14,050 --> 00:34:15,750
>> ОК, так что это связанный список.

812
00:34:15,750 --> 00:34:17,580
Так что это сценарий под вопросом.

813
00:34:17,580 --> 00:34:20,210
И в самом деле, это представитель
из одного класса задач

814
00:34:20,210 --> 00:34:21,929
что вы могли бы попытаться решить с кодом.

815
00:34:21,929 --> 00:34:25,020
Вы хотите, чтобы в конечном счете вставить
новый элемент в список.

816
00:34:25,020 --> 00:34:27,494
В этом случае, мы собираемся
попробуйте вставить число 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Но есть будет
различные случаи рассмотреть.

819
00:34:30,860 --> 00:34:34,409
И в самом деле, это будет один
из большой картины еды на дом здесь, является,

820
00:34:34,409 --> 00:34:35,659
каковы различные случаи.

821
00:34:35,659 --> 00:34:39,120
Какие существуют ли условия или
филиалы, что ваша программа может быть?

822
00:34:39,120 --> 00:34:42,024
>> Ну, номер, который вы пытаетесь
вставка, который мы теперь знаем, 55,

823
00:34:42,024 --> 00:34:44,650
но если вы не знаете,
заранее, я осмелюсь сказать,

824
00:34:44,650 --> 00:34:47,840
попадает в по крайней мере трех
возможные ситуации.

825
00:34:47,840 --> 00:34:49,717
Где может новый элемент быть?

826
00:34:49,717 --> 00:34:51,050
АУДИТОРИЯ: И конец или середину.

827
00:34:51,050 --> 00:34:54,150
David J. МАЛАН: В конце, в
средний, или в начале.

828
00:34:54,150 --> 00:34:56,650
Так я утверждаю, что есть по крайней мере
три проблемы, которые мы должны решить.

829
00:34:56,650 --> 00:34:58,691
Давайте выбирать, что, возможно,
возможно простейший

830
00:34:58,691 --> 00:35:01,090
один, где новый элемент
принадлежит в начале.

831
00:35:01,090 --> 00:35:04,040
Так что я буду иметь код довольно
как искать, что я только что написал.

832
00:35:04,040 --> 00:35:07,670
И я буду иметь PTR, которые
Я представляю пальцем,

833
00:35:07,670 --> 00:35:08,370
как обычно.

834
00:35:08,370 --> 00:35:12,430
>> И помните, какое значение
же мы инициализировать указатель на?

835
00:35:12,430 --> 00:35:15,300
Таким образом, мы инициализировать его обнулить изначально.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Но тогда что же мы делаем, как только мы
были в нашем функции поиска?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Положим его равным первому,
что не означает делать это.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Если я устанавливаю PTR равную первой, что
должны моя рука действительно указывая на?

842
00:35:30,570 --> 00:35:31,070
Право.

843
00:35:31,070 --> 00:35:33,290
Так что, если Гейб и я собираемся
быть равные значения здесь,

844
00:35:33,290 --> 00:35:34,760
мы должны как точки, в число 9.

845
00:35:34,760 --> 00:35:36,420
>> Так что это было начало нашей истории.

846
00:35:36,420 --> 00:35:38,700
А теперь это просто прямой,
несмотря на то, что синтаксис является новым.

847
00:35:38,700 --> 00:35:40,580
Концептуально это только линейный поиск.

848
00:35:40,580 --> 00:35:42,750
Является 55 равен 9?

849
00:35:42,750 --> 00:35:45,559
Вернее, скажем менее 9.

850
00:35:45,559 --> 00:35:47,600
Потому что я пытаюсь
выяснить, где поставить 55.

851
00:35:47,600 --> 00:35:51,270
Менее 9, меньше 17, меньше
чем 20, менее 22, менее 29,

852
00:35:51,270 --> 00:35:52,510
менее 34, нет.

853
00:35:52,510 --> 00:35:55,080
Так что теперь мы в случае
один из по меньшей мере трех.

854
00:35:55,080 --> 00:35:59,910
>> Если я хочу, чтобы вставить 55 над здесь, что
строк кода необходимости получить выполнен?

855
00:35:59,910 --> 00:36:01,890
Как это картину
люди должны изменить?

856
00:36:01,890 --> 00:36:03,181
Что мне делать с моей левой рукой?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Это должно быть нулевым, первоначально,
потому что я в конце списка.

859
00:36:07,360 --> 00:36:09,318
А что должно произойти,
здесь с Петром, это было?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Он, очевидно, собирается указывать на меня.

862
00:36:12,430 --> 00:36:15,580
Так я утверждаю, что есть по крайней мере две линии
кода в примере кода с сегодняшнего дня

863
00:36:15,580 --> 00:36:18,570
что собирается осуществить это
Сценарий добавления 55 в хвосте.

864
00:36:18,570 --> 00:36:20,950
И может меня кто-то-хоп
и просто представляют 55?

865
00:36:20,950 --> 00:36:22,200
Ладно, вы новый 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Так что теперь, если следующая
сценарий приходит,

868
00:36:27,054 --> 00:36:29,720
и мы хотим, чтобы вставить в
начиная или руководитель этого списка?

869
00:36:29,720 --> 00:36:31,100
И то, что ваше имя, номер 55?

870
00:36:31,100 --> 00:36:31,420
>> АУДИТОРИЯ: Джек.

871
00:36:31,420 --> 00:36:32,295
>> David J. МАЛАН: Джек?

872
00:36:32,295 --> 00:36:33,585
ОК, приятно познакомиться.

873
00:36:33,585 --> 00:36:34,210
Добро пожаловать на борт.

874
00:36:34,210 --> 00:36:36,640
Так что теперь мы собираемся
вставить, скажем, число 5.

875
00:36:36,640 --> 00:36:39,840
Вот второй случай
три мы придумали раньше.

876
00:36:39,840 --> 00:36:43,050
Так что если 5 принадлежит в начале,
давайте посмотрим, как мы видим, что из.

877
00:36:43,050 --> 00:36:46,310
Я инициализировать мой PTR
указатель на номер 9 снова.

878
00:36:46,310 --> 00:36:49,140
И я понял,, о, 5 меньше 9.

879
00:36:49,140 --> 00:36:50,880
Так исправить эту картинку для нас.

880
00:36:50,880 --> 00:36:54,820
Чьи руки, Гейба или Давида
или-- что номер 9 в название?

881
00:36:54,820 --> 00:36:55,740
>> АУДИТОРИЯ: Джен.

882
00:36:55,740 --> 00:36:58,406
>> David J. МАЛАН: hands-- Джен
какие из наших рук нужно изменить?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
Итак, Гейб указывает на что теперь?

885
00:37:00,970 --> 00:37:01,640
У меня.

886
00:37:01,640 --> 00:37:02,750
Я новый узел.

887
00:37:02,750 --> 00:37:04,870
Так что я просто вид ходу
здесь, чтобы посмотреть его визуально.

888
00:37:04,870 --> 00:37:06,435
А между тем, что я указать, что?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Тем не менее, когда я указываю.

891
00:37:09,020 --> 00:37:10,000
Так вот оно что.

892
00:37:10,000 --> 00:37:13,717
Так что просто действительно одна строка кода исправления
это конкретный вопрос, казалось бы.

893
00:37:13,717 --> 00:37:14,800
Ладно, так что это хорошо.

894
00:37:14,800 --> 00:37:17,580
А может кто бы это место для 5?

895
00:37:17,580 --> 00:37:18,080
Поднимайтесь.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Мы тебя в следующий раз.

898
00:37:21,320 --> 00:37:24,280
>> Ладно, так now-- и
Как в стороне, имена

899
00:37:24,280 --> 00:37:28,510
Я не делаю прямого упоминания права
Теперь, před указатель, указатель предшественник

900
00:37:28,510 --> 00:37:31,260
и новый указатель, это
только имена дали

901
00:37:31,260 --> 00:37:35,280
в примере кода к указателей или
мои руки, это отчасти указывающие вокруг.

902
00:37:35,280 --> 00:37:36,060
Как тебя зовут?

903
00:37:36,060 --> 00:37:36,700
>> АУДИТОРИЯ: Кристина.

904
00:37:36,700 --> 00:37:37,100
>> David J. МАЛАН: Кристина.

905
00:37:37,100 --> 00:37:38,090
Добро пожаловать на борт.

906
00:37:38,090 --> 00:37:42,180
Ладно, так что давайте рассмотрим сейчас
немного больше раздражает сценарий,

907
00:37:42,180 --> 00:37:46,350
в результате чего я хочу, чтобы вставить
что-то вроде 26 в этом.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Что?

910
00:37:47,590 --> 00:37:50,510
Эти are-- хорошая вещь у нас есть эту ручку.

911
00:37:50,510 --> 00:37:51,955
Ладно, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Если кто-то может получить еще один кусок
бумага готова, только в case-- все в порядке.

914
00:37:57,570 --> 00:37:58,370
О, интересно.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Ну это пример
лекционного ошибки.

917
00:38:02,390 --> 00:38:03,894
Хорошо, таким образом, что тебя зовут?

918
00:38:03,894 --> 00:38:04,560
АУДИТОРИЯ: Юлия.

919
00:38:04,560 --> 00:38:07,559
David J. МАЛАН: Юлия, вы можете поп
, и притворитесь, что вы никогда не были там?

920
00:38:07,559 --> 00:38:09,040
ОК, это никогда не происходило.

921
00:38:09,040 --> 00:38:09,680
Спасибо.

922
00:38:09,680 --> 00:38:12,180
Так что мы хотим вставить
Юлия в этот связанного списка.

923
00:38:12,180 --> 00:38:13,780
Она является число 20.

924
00:38:13,780 --> 00:38:15,530
И, конечно, она
собирается принадлежат на

925
00:38:15,530 --> 00:38:17,521
begin-- не указывают ни на что еще.

926
00:38:17,521 --> 00:38:20,020
Так что ваша рука может отчасти быть
вниз нуль или некоторое значение мусора.

927
00:38:20,020 --> 00:38:21,210
Давайте говорить короткую историю.

928
00:38:21,210 --> 00:38:22,980
Я указываю на 5 на этот раз.

929
00:38:22,980 --> 00:38:23,880
Тогда я проверяю 9.

930
00:38:23,880 --> 00:38:25,130
Тогда я проверяю 17.

931
00:38:25,130 --> 00:38:26,247
Тогда я проверяю 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
И я понимаю,, ох, Юля
должен идти до 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Так что должно произойти?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Чьи руки нужно изменить?

938
00:38:36,910 --> 00:38:38,360
Джулия, шахта, или--
как тебя зовут?

939
00:38:38,360 --> 00:38:39,230
>> АУДИТОРИЯ: Кристиан.

940
00:38:39,230 --> 00:38:40,060
>> David J. МАЛАН: христианин или?

941
00:38:40,060 --> 00:38:40,560
>> АУДИТОРИЯ: Энди.

942
00:38:40,560 --> 00:38:40,905
>> David J. МАЛАН: Энди.

943
00:38:40,905 --> 00:38:41,654
Кристиан или Энди?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Энди должен указать на?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Юлия.

948
00:38:47,341 --> 00:38:47,840
Хорошо.

949
00:38:47,840 --> 00:38:48,960
Так Энди, ты хочешь, чтобы указать на Джулию?

950
00:38:48,960 --> 00:38:50,120
Но подождите минуту.

951
00:38:50,120 --> 00:38:53,260
В истории до сих пор,
Я-то один

952
00:38:53,260 --> 00:38:56,800
отвечает, в том смысле, что
указатель является вещь, которая

953
00:38:56,800 --> 00:38:57,850
перемещение по списку.

954
00:38:57,850 --> 00:39:00,800
Мы можем иметь имя для Энди, но
нет переменная называется Энди.

955
00:39:00,800 --> 00:39:04,320
Единственный другой переменной у нас есть,
первый, кто представлен Гейба.

956
00:39:04,320 --> 00:39:07,690
>> Так что это на самом деле, почему таким образом
Пока мы не нуждались в этом.

957
00:39:07,690 --> 00:39:10,846
Но теперь на экране есть
еще раз отметить, из před указателя.

958
00:39:10,846 --> 00:39:11,970
Итак, позвольте мне быть более явным.

959
00:39:11,970 --> 00:39:14,820
Если это указатель, я должен был лучше
получить немного умнее

960
00:39:14,820 --> 00:39:15,950
о моем итерации.

961
00:39:15,950 --> 00:39:19,580
Если вы не против, что я собираюсь через здесь
снова, указывая здесь, указывая здесь.

962
00:39:19,580 --> 00:39:22,500
Но позвольте мне есть před указатель,
указатель предшественник, это

963
00:39:22,500 --> 00:39:24,740
вид указывая на
элемент я был просто в.

964
00:39:24,740 --> 00:39:27,330
Поэтому, когда я иду сюда, сейчас
Моя левая рука обновления.

965
00:39:27,330 --> 00:39:29,370
Когда я иду здесь мои левые обновления вручную.

966
00:39:29,370 --> 00:39:33,090
И теперь у меня есть не только указатель
элемент, который идет после Джулии,

967
00:39:33,090 --> 00:39:36,300
Я до сих пор есть указатель на
Энди, элемент раньше.

968
00:39:36,300 --> 00:39:39,430
Так у вас есть доступ, по существу,
панировочных сухарей, если хотите,

969
00:39:39,430 --> 00:39:41,500
для всех необходимых указателей.

970
00:39:41,500 --> 00:39:43,710
>> Так что, если я, указывая на
Энди и я также указывая

971
00:39:43,710 --> 00:39:47,105
на Кристиана, чьи руки
должны теперь отметить в другом месте?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Так Энди теперь могут указать на Джулию.

974
00:39:51,960 --> 00:39:54,460
Теперь Юлия может указывать на христианина.

975
00:39:54,460 --> 00:39:56,950
Потому что она может скопировать мой
указатель правой руки.

976
00:39:56,950 --> 00:40:00,044
И, что эффективно ставит вас
обратно в этом месте здесь.

977
00:40:00,044 --> 00:40:02,460
Таким образом, в общем, хотя это
ведет нас вроде навсегда

978
00:40:02,460 --> 00:40:04,510
на самом деле обновления
связан список, реализовать

979
00:40:04,510 --> 00:40:06,580
что операции
относительно просты.

980
00:40:06,580 --> 00:40:10,030
Это из одного, двух, трех
строк кода, в конечном счете.

981
00:40:10,030 --> 00:40:12,780
Но обернуты вокруг тех,
строк кода предположительно

982
00:40:12,780 --> 00:40:16,350
немного логики, которые эффективно
задает вопрос, где мы находимся?

983
00:40:16,350 --> 00:40:18,970
Неужели мы в самом начале,
средний, или конец?

984
00:40:18,970 --> 00:40:21,890
>> Теперь, есть, конечно, некоторые другие
Операции, которые мы могли бы реализовать.

985
00:40:21,890 --> 00:40:24,880
И эти фотографии здесь просто изобразить
то, что мы только что сделали с людьми.

986
00:40:24,880 --> 00:40:26,080
А как насчет удаления?

987
00:40:26,080 --> 00:40:30,650
Если я хочу, например,
удалить номер 34 или 55,

988
00:40:30,650 --> 00:40:34,680
Я мог бы иметь такой же код,
но я буду нуждаться в один или два этапа.

989
00:40:34,680 --> 00:40:36,110
Потому что нового?

990
00:40:36,110 --> 00:40:40,460
Если я удалю кого в конце,
как числа 55, а затем 34,

991
00:40:40,460 --> 00:40:42,995
что также должно измениться, как мне это сделать?

992
00:40:42,995 --> 00:40:44,870
Я должен не evict--
как тебя зовут?

993
00:40:44,870 --> 00:40:45,380
>> АУДИТОРИЯ: Джек.

994
00:40:45,380 --> 00:40:46,255
>> David J. МАЛАН: Джек.

995
00:40:46,255 --> 00:40:49,770
Я должен не только evict-- бесплатно Джек,
так буквально назвать бесплатный Джек, или, по крайней мере,

996
00:40:49,770 --> 00:40:53,530
указатель там же, но теперь
что необходимо изменить с Петром?

997
00:40:53,530 --> 00:40:55,510
Его рука лучше начать вниз.

998
00:40:55,510 --> 00:40:59,300
Потому что, как только я звонить бесплатно на
Джек, если еще указывает Петра на Джека

999
00:40:59,300 --> 00:41:02,530
и я поэтому держите обходе
список и доступ этот указатель,

1000
00:41:02,530 --> 00:41:05,650
вот когда наш старый друг сегментация
обвинить действительно может умереть.

1001
00:41:05,650 --> 00:41:07,860
Потому что мы дали
памяти обратно к Джеку.

1002
00:41:07,860 --> 00:41:10,760
>> Вы можете остаться там
неловко на мгновение.

1003
00:41:10,760 --> 00:41:13,410
Потому что у нас всего пару
заключительные операции рассмотреть.

1004
00:41:13,410 --> 00:41:15,600
Снятие голову списка,
или beginning-- и этот сайт

1005
00:41:15,600 --> 00:41:16,349
немного раздражает.

1006
00:41:16,349 --> 00:41:19,640
Потому что мы должны знать, что Гейб
это своего рода специальное в этой программе.

1007
00:41:19,640 --> 00:41:21,440
Потому что на самом деле, у него есть своя указатель.

1008
00:41:21,440 --> 00:41:24,860
Он не просто на которую ссылаются,,
как почти все остальные здесь.

1009
00:41:24,860 --> 00:41:28,112
>> Поэтому, когда глава списка
удалены, чьи руки должны изменить сейчас?

1010
00:41:28,112 --> 00:41:29,070
Как тебя зовут снова?

1011
00:41:29,070 --> 00:41:29,450
>> АУДИТОРИЯ: Кристина.

1012
00:41:29,450 --> 00:41:31,408
>> David J. МАЛАН: Я ужасно
на имена, по-видимому.

1013
00:41:31,408 --> 00:41:34,011
Так Кристина и Гейб,
чьи руки необходимо изменить

1014
00:41:34,011 --> 00:41:36,510
когда мы пытаемся удалить Кристину,
число 5, от картины?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Итак, давайте сделаем Гейб.

1017
00:41:38,820 --> 00:41:40,950
Гейб собирается указать,
предположительно, в доме номер 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Но что следующий должен произойти?

1020
00:41:44,642 --> 00:41:46,600
АУДИТОРИЯ: Кристина должна
быть пустым [неразборчиво].

1021
00:41:46,600 --> 00:41:50,244
David J. МАЛАН: Хорошо, мы должны, вероятно,
make-- я услышал "нулевой" где.

1022
00:41:50,244 --> 00:41:51,410
АУДИТОРИЯ: Null и освободить ее.

1023
00:41:51,410 --> 00:41:51,855
David J. МАЛАН: Null что?

1024
00:41:51,855 --> 00:41:53,074
АУДИТОРИЯ: Null и освободить ее.

1025
00:41:53,074 --> 00:41:54,490
David J. МАЛАН: Null и освободить ее.

1026
00:41:54,490 --> 00:41:55,422
Так что это очень легко.

1027
00:41:55,422 --> 00:41:58,380
И это прекрасно, что ты сейчас рода
стоять там, не принадлежащие.

1028
00:41:58,380 --> 00:42:00,430
Потому что вы были
отделен от списка.

1029
00:42:00,430 --> 00:42:02,820
Вы эффективно было
сиротами из списка.

1030
00:42:02,820 --> 00:42:07,770
И таким образом, мы лучше позвонить бесплатно сейчас на
Кристин, чтобы дать эту память назад.

1031
00:42:07,770 --> 00:42:10,240
В противном случае каждый раз, когда мы
удалить узел из списка

1032
00:42:10,240 --> 00:42:14,230
мы могли бы делать список
короче, но на самом деле не уменьшается

1033
00:42:14,230 --> 00:42:15,096
размер в памяти.

1034
00:42:15,096 --> 00:42:17,720
И поэтому, если мы продолжаем добавлять и
добавив, добавление элементов в списке,

1035
00:42:17,720 --> 00:42:19,280
мой компьютер становится менее эффективным
и все медленнее и медленнее,

1036
00:42:19,280 --> 00:42:21,740
потому что я бегу из
памяти, даже если я на самом деле не

1037
00:42:21,740 --> 00:42:25,580
используя байт Кристины
памяти больше.

1038
00:42:25,580 --> 00:42:28,500
>> Так, в конце есть и другие
сценарии, из course-- удаления

1039
00:42:28,500 --> 00:42:30,640
в средней, удаления
в конце, как мы видели.

1040
00:42:30,640 --> 00:42:32,348
Но тем интереснее
Сейчас задача заключается в

1041
00:42:32,348 --> 00:42:34,770
будет рассматривать именно
что время работы является.

1042
00:42:34,770 --> 00:42:36,640
Так что не только вы можете сохранить ваш
бумажек, если, Гейб,

1043
00:42:36,640 --> 00:42:38,640
вы не возражаете давая
каждый мяч стресс.

1044
00:42:38,640 --> 00:42:42,100
Огромное спасибо нашему связанного списка
добровольцев здесь, если бы вы могли.

1045
00:42:42,100 --> 00:42:45,320
>> [Аплодисменты]

1046
00:42:45,320 --> 00:42:46,700
>> David J. МАЛАН: Хорошо.

1047
00:42:46,700 --> 00:42:51,110
Так пару аналитическая
вопросы потом, если я мог.

1048
00:42:51,110 --> 00:42:59,670
Мы видели это обозначение раньше,
Big O и омега, верхние границы

1049
00:42:59,670 --> 00:43:02,520
и нижние границы
время работы от некоторого алгоритма.

1050
00:43:02,520 --> 00:43:04,950
Итак, давайте рассмотрим только
пару вопросов.

1051
00:43:04,950 --> 00:43:07,090
>> Один, и мы сказали, это
прежде, чем же работает

1052
00:43:07,090 --> 00:43:10,647
время поиска
Список по большой O?

1053
00:43:10,647 --> 00:43:13,480
Что верхнюю границу работающем
Время поиска связанный список

1054
00:43:13,480 --> 00:43:16,340
как осуществляется нашими волонтерами здесь?

1055
00:43:16,340 --> 00:43:17,820
Это большой O н, линейный.

1056
00:43:17,820 --> 00:43:20,630
Потому что в худшем случае,
элемент, как 55,

1057
00:43:20,630 --> 00:43:23,830
мы могли бы искать может быть там, где
Джек был, всю дорогу в конце.

1058
00:43:23,830 --> 00:43:28,250
И, к сожалению, в отличие от массива
мы не можем получить фантазии на этот раз.

1059
00:43:28,250 --> 00:43:31,820
Даже при том, что все наши люди были
отсортированы от небольших элементов, 5,

1060
00:43:31,820 --> 00:43:35,900
все, вплоть до большего элемента,
55, что, как правило, хорошая вещь.

1061
00:43:35,900 --> 00:43:38,815
Но то, что делает это предположение
больше не позволяют нам делать?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
АУДИТОРИЯ: [неразборчиво]

1064
00:43:40,650 --> 00:43:40,920
David J. МАЛАН: снова сказать?

1065
00:43:40,920 --> 00:43:41,800
АУДИТОРИЯ: Произвольный доступ.

1066
00:43:41,800 --> 00:43:43,049
David J. МАЛАН: Произвольный доступ.

1067
00:43:43,049 --> 00:43:46,330
И в свою очередь это означает, что мы можем не
больше использовать слабый нули, интуицию,

1068
00:43:46,330 --> 00:43:49,365
и очевидность используя двоичный
поиск и разделяй и властвуй.

1069
00:43:49,365 --> 00:43:51,240
Потому что даже при том, что мы
люди могли, очевидно,

1070
00:43:51,240 --> 00:43:54,610
видеть, что Энди или христианин были
примерно в середине списка,

1071
00:43:54,610 --> 00:43:57,670
известно лишь, что, как
компьютер путем снятия верхнего слоя список

1072
00:43:57,670 --> 00:43:59,029
с самого начала.

1073
00:43:59,029 --> 00:44:00,570
Таким образом, мы отказались, что произвольный доступ.

1074
00:44:00,570 --> 00:44:04,380
>> Настолько большой O п теперь это верхняя
граница нашего времени поиска.

1075
00:44:04,380 --> 00:44:07,920
Как насчет омега нашего поиска?

1076
00:44:07,920 --> 00:44:11,535
Что нижняя граница по поиску
в течение некоторого числа в этом списке?

1077
00:44:11,535 --> 00:44:12,410
АУДИТОРИЯ: [неразборчиво]

1078
00:44:12,410 --> 00:44:13,040
David J. МАЛАН: снова сказать?

1079
00:44:13,040 --> 00:44:13,420
АУДИТОРИЯ: Один.

1080
00:44:13,420 --> 00:44:13,800
David J. МАЛАН: Один.

1081
00:44:13,800 --> 00:44:14,760
Так постоянная времени.

1082
00:44:14,760 --> 00:44:17,020
В лучшем случае, Кристина
В самом деле в начале списка.

1083
00:44:17,020 --> 00:44:19,020
И мы ищем
число 5, так что мы нашли ее.

1084
00:44:19,020 --> 00:44:19,787
Так нет ничего сложного.

1085
00:44:19,787 --> 00:44:22,370
Но у нее есть, чтобы быть в
начало списка в этом случае.

1086
00:44:22,370 --> 00:44:23,745
Что о чем-то как Удалить?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Что делать, если вы хотите удалить элемент?

1089
00:44:26,300 --> 00:44:29,200
Что верхняя граница и нижняя граница
на удалении чего от связаны

1090
00:44:29,200 --> 00:44:29,699
перечислить?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
АУДИТОРИЯ: [неразборчиво]

1093
00:44:36,070 --> 00:44:36,420
David J. МАЛАН: снова сказать?

1094
00:44:36,420 --> 00:44:37,067
АУДИТОРИЯ: н.

1095
00:44:37,067 --> 00:44:38,900
David J. МАЛАН: п
действительно верхняя граница.

1096
00:44:38,900 --> 00:44:41,700
Потому что в худшем случае мы стараемся
удалить Джек, как мы только что сделали.

1097
00:44:41,700 --> 00:44:43,050
Он всю дорогу в конце.

1098
00:44:43,050 --> 00:44:45,419
Принимает от нас навсегда, или
п шагов, чтобы найти его.

1099
00:44:45,419 --> 00:44:46,460
Так вот верхняя граница.

1100
00:44:46,460 --> 00:44:47,430
Это линейная, уверен.

1101
00:44:47,430 --> 00:44:50,970
И в лучшем случае время работы, или
нижние границы в лучшем случае

1102
00:44:50,970 --> 00:44:51,975
будет постоянная времени.

1103
00:44:51,975 --> 00:44:54,600
Потому что, может быть, мы пытаемся удалить
Кристин, и мы просто повезти

1104
00:44:54,600 --> 00:44:55,558
она в начале.

1105
00:44:55,558 --> 00:44:56,350
Теперь подождите минуту.

1106
00:44:56,350 --> 00:44:59,370
Гейб также в начале,
и мы также должны были обновить Гейб.

1107
00:44:59,370 --> 00:45:01,150
Так что не было еще один этап.

1108
00:45:01,150 --> 00:45:04,210
Так это действительно постоянной
Время, в лучшем случае,

1109
00:45:04,210 --> 00:45:06,345
удалить наименьший элемент?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Это, несмотря на то, что может быть два,
три или даже 100 строк кода,

1112
00:45:10,960 --> 00:45:14,000
если это то же самое количество
линии, не в некоторой петли,

1113
00:45:14,000 --> 00:45:16,577
и не зависит от размера
из списка, абсолютно.

1114
00:45:16,577 --> 00:45:18,660
Удаление элемента в
начало списка,

1115
00:45:18,660 --> 00:45:21,940
даже если мы имеем дело с
Гейб, еще постоянная времени.

1116
00:45:21,940 --> 00:45:24,220
>> Так это кажется
массивный шаг назад.

1117
00:45:24,220 --> 00:45:27,000
И то, что это пустая трата времени
если, в неделю один и недели

1118
00:45:27,000 --> 00:45:30,250
нулю, мы должны были не только
Код псевдокод но фактический код

1119
00:45:30,250 --> 00:45:35,780
реализовать то, что это журнал
база н, или войдите, скорее, из п, база 2,

1120
00:45:35,780 --> 00:45:37,150
с точки зрения его времени работы.

1121
00:45:37,150 --> 00:45:40,710
Так почему, черт возьми, мы хотели бы начать
используя нечто вроде связанного списка?

1122
00:45:40,710 --> 00:45:41,517
Да.

1123
00:45:41,517 --> 00:45:44,022
>> АУДИТОРИЯ: Таким образом, вы можете добавить
элементы в массив.

1124
00:45:44,022 --> 00:45:46,230
David J. МАЛАН: Таким образом, вы можете
добавлять элементы в массив.

1125
00:45:46,230 --> 00:45:47,550
И это тоже является тематическим.

1126
00:45:47,550 --> 00:45:49,740
И мы будем продолжать видеть
это, это компромисс, гораздо

1127
00:45:49,740 --> 00:45:51,573
как мы видели
Компромисс с сортировки слиянием.

1128
00:45:51,573 --> 00:45:54,606
Мы могли бы реально ускорить
поиск или сортировки, а,

1129
00:45:54,606 --> 00:45:57,480
если мы тратим немного больше места и
иметь дополнительный кусок памяти

1130
00:45:57,480 --> 00:45:58,760
или массив для сортировки слиянием.

1131
00:45:58,760 --> 00:46:01,270
Но мы проводим больше
пространство, но мы экономим время.

1132
00:46:01,270 --> 00:46:04,820
В этом случае, мы
отказавшись от времени, но мы

1133
00:46:04,820 --> 00:46:08,170
обеспечение гибкости,
Динамизм, если хотите,

1134
00:46:08,170 --> 00:46:10,280
которые, возможно, положительная черта.

1135
00:46:10,280 --> 00:46:11,520
>> Мы также проводить пространство.

1136
00:46:11,520 --> 00:46:13,710
В каком смысле связаны
перечислить дороже

1137
00:46:13,710 --> 00:46:15,700
с точки зрения пространства, чем массив?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Где дополнительное пространство приходят?

1140
00:46:19,920 --> 00:46:20,460
Да?

1141
00:46:20,460 --> 00:46:21,800
>> АУДИТОРИЯ: [неразборчиво] указатель.

1142
00:46:21,800 --> 00:46:23,310
>> David J. МАЛАН: Да, мы
также есть указатель.

1143
00:46:23,310 --> 00:46:25,560
Так что это minorly раздражает
в том, что больше не являюсь

1144
00:46:25,560 --> 00:46:27,780
Я хранения просто Int
для представления Int.

1145
00:46:27,780 --> 00:46:30,990
Я запоминания Int и а
указатель, который также 32 бит.

1146
00:46:30,990 --> 00:46:33,470
Так что я буквально удваивая
участие объем пространства.

1147
00:46:33,470 --> 00:46:36,040
Так вот компромисс, но
вот в случае междунар.

1148
00:46:36,040 --> 00:46:39,580
Предположим, что вы не хранения Int,
но предположим, что каждый из этих прямоугольников

1149
00:46:39,580 --> 00:46:43,290
или каждый из этих людей представлял
слово, английское слово, которое

1150
00:46:43,290 --> 00:46:46,430
может содержать пять знаков, 10
символы, может быть, даже больше.

1151
00:46:46,430 --> 00:46:49,940
Тогда добавив всего 32 больше битов
может быть менее крупной сделки.

1152
00:46:49,940 --> 00:46:52,160
>> Что делать, если каждый из студентов
в демонстрации

1153
00:46:52,160 --> 00:46:55,107
были буквально студенческие Структуры, которые
имеют имена и домов и, возможно,

1154
00:46:55,107 --> 00:46:57,065
телефонов и Twitter
ручки и тому подобное.

1155
00:46:57,065 --> 00:46:59,564
Так все поля мы начали
говорим о другой день,

1156
00:46:59,564 --> 00:47:02,410
гораздо менее крупной сделки, как
наши узлы становятся более интересными

1157
00:47:02,410 --> 00:47:05,972
и большой, чтобы провести, а, дополнительный
указатель просто связать их вместе.

1158
00:47:05,972 --> 00:47:07,180
Но на самом деле, это компромисс.

1159
00:47:07,180 --> 00:47:09,560
И в самом деле, код
сложнее, как вы будете

1160
00:47:09,560 --> 00:47:11,770
см по бегло
что конкретный пример.

1161
00:47:11,770 --> 00:47:14,302
Но что, если было
некоторые Святой Грааль здесь.

1162
00:47:14,302 --> 00:47:17,010
Что делать, если мы не сделаем шаг
назад, но массивный шаг вперед

1163
00:47:17,010 --> 00:47:19,180
и внедрить данные
Структура, через который мы

1164
00:47:19,180 --> 00:47:22,870
может найти элементы, такие как Джек или
Christine или любые другие элементы

1165
00:47:22,870 --> 00:47:25,870
в этом массиве в истинно постоянного времени?

1166
00:47:25,870 --> 00:47:26,920
Поиск постоянна.

1167
00:47:26,920 --> 00:47:28,320
Удалить постоянна.

1168
00:47:28,320 --> 00:47:29,570
Вставка постоянна.

1169
00:47:29,570 --> 00:47:32,260
Все эти операции являются постоянными.

1170
00:47:32,260 --> 00:47:33,750
Это было бы нашим святым Граалем.

1171
00:47:33,750 --> 00:47:36,690
И что это, где мы
подберут следующий раз.

1172
00:47:36,690 --> 00:47:38,600
Увидимся.

1173
00:47:38,600 --> 00:47:39,371