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