1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Тиждень 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Малан] [Harvard University]

3
00:00:04,000 --> 00:00:08,000
[Це CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Це CS50, і це початок тижня 6,

5
00:00:12,000 --> 00:00:16,000
так що пару нових інструментів тепер доступні для вас, щоб скористатися перевагами,

6
00:00:16,000 --> 00:00:19,000
перша з яких називається CS50 стилю.

7
00:00:19,000 --> 00:00:22,000
Швидше за все, якщо ви схожі на мене чи будь-якого вчення хлопці,

8
00:00:22,000 --> 00:00:26,000
Ви, напевно, бачили програму, чий стиль виглядає трохи щось на зразок цього.

9
00:00:26,000 --> 00:00:30,000
Може бути, ви почнете різання деякі кути пізно вночі, або ви будете мати справу з ним пізніше,

10
00:00:30,000 --> 00:00:32,000
, А потім TF або CA приходить в робочий час.

11
00:00:32,000 --> 00:00:34,000
Тоді це важко для нас, щоб читати.

12
00:00:34,000 --> 00:00:38,000
Ну, цей код синтаксично правильні, і він буде компілювати, і вона буде реально працювати.

13
00:00:38,000 --> 00:00:40,000
Але це безумовно не 5 за стиль.

14
00:00:40,000 --> 00:00:45,000
>> Але тепер, якщо ми підемо в цей каталог тут-

15
00:00:45,000 --> 00:00:48,000
і зауважив, що у мене є conditions2.c-

16
00:00:48,000 --> 00:00:55,000
і я біжу цю нову команду, style50, на цей файл conditions2.c, Enter

17
00:00:55,000 --> 00:00:57,000
помітите, що він повідомив мені, що він був стилізований.

18
00:00:57,000 --> 00:01:00,000
Gedit зауважив, що файл був змінений на диску,

19
00:01:00,000 --> 00:01:08,000
і якщо я натискаю кнопку перезавантаження, всі ваші проблеми в даний час автоматизовані.

20
00:01:08,000 --> 00:01:15,000
[Оплески]

21
00:01:15,000 --> 00:01:17,000
Це одна з речей, які ми зробили в ці вихідні.

22
00:01:17,000 --> 00:01:20,000
Зрозумійте, що вона недосконала, тому що є певний код

23
00:01:20,000 --> 00:01:23,000
що він просто не зможе стилізувати відмінно,

24
00:01:23,000 --> 00:01:26,000
але розумію, що це зараз інструменту ви можете скористатися

25
00:01:26,000 --> 00:01:33,000
якщо тільки привести в порядок деякі з більш errantly розміщені фігурні дужки тощо.

26
00:01:33,000 --> 00:01:36,000
>> Але більш переконливим зараз CS50 перевірки.

27
00:01:36,000 --> 00:01:39,000
З CS50 перевірки, ви можете виконувати ті ж випробування коректності

28
00:01:39,000 --> 00:01:42,000
на свій власний код, що вчення хлопці здатні.

29
00:01:42,000 --> 00:01:44,000
Це утиліта командного рядка, яка йде зараз в прилад

30
00:01:44,000 --> 00:01:46,000
Як тільки ви update50 відповідно до

31
00:01:46,000 --> 00:01:49,000
PSET 4 специфікацій, а також використовувати його по суті, як це.

32
00:01:49,000 --> 00:01:51,000
Ви виконаєте команду check50.

33
00:01:51,000 --> 00:01:56,000
Потім ви передаєте в якості аргументу командного рядка, або більш відомий як комутатор або прапор.

34
00:01:56,000 --> 00:01:58,000
Як правило, речі, які мають дефіс називається перемикачем

35
00:01:58,000 --> 00:02:02,000
на програму командного рядка, так з вказуюче

36
00:02:02,000 --> 00:02:04,000
перевіряє, що ви хочете запустити.

37
00:02:04,000 --> 00:02:07,000
>> Тести, які ви хочете запустити визначені однозначно цей рядок,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Іншими словами, це просто довільне, але унікальна рядок

40
00:02:13,000 --> 00:02:18,000
, Які ми використовуємо, щоб однозначно ідентифікувати правильності PSET 4 в тестах.

41
00:02:18,000 --> 00:02:21,000
А потім ви задаєте пробіл список файлів, які ви хочете завантажити

42
00:02:21,000 --> 00:02:24,000
Перевірити, щоб CS50 для аналізу.

43
00:02:24,000 --> 00:02:29,000
Наприклад, якщо я йду на моє рішення тут Зміна розміру-

44
00:02:29,000 --> 00:02:31,000
Дозвольте мені відкрити великі вікна терміналу-

45
00:02:31,000 --> 00:02:42,000
і я йду вперед і запустити скажімо check50-з 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
а потім йти вперед і вказати імена файлів,

47
00:02:46,000 --> 00:02:49,000
Зміна розміру, а потім натисніть Enter, він стискає,

48
00:02:49,000 --> 00:02:53,000
Він завантажує, він перевіряє, і я просто не зміг цілу купу тестів.

49
00:02:53,000 --> 00:02:59,000
Той в червоному в лівому верхньому куті говорить, що Зміна розміру і BMP існує.

50
00:02:59,000 --> 00:03:01,000
Це був тест. Таке питання ми поставили.

51
00:03:01,000 --> 00:03:04,000
І це нещасні, тому що відповідь була помилковою.

52
00:03:04,000 --> 00:03:08,000
Білий текст нижче він говорить очікується bmp.h існувати, і це просто моя вина.

53
00:03:08,000 --> 00:03:11,000
Я забув, щоб завантажити його, так що мені потрібно завантажувати як файли,

54
00:03:11,000 --> 00:03:14,000
Зміна розміру і bmp.h.

55
00:03:14,000 --> 00:03:17,000
Але тепер помічаю всі інші тести в жовтий, тому що вони не працюють,

56
00:03:17,000 --> 00:03:21,000
і так смайлик вертикально, тому що він не є ні щасливим, ні сумно,

57
00:03:21,000 --> 00:03:25,000
але у нас є для усунення цього питання в червоному перед тими, інших перевірок буде працювати.

58
00:03:25,000 --> 00:03:27,000
>> Дозвольте мені виправити це.

59
00:03:27,000 --> 00:03:30,000
Дозвольте мені масштаб і повторіть це, на цей раз з bmp.h також

60
00:03:30,000 --> 00:03:34,000
в командному рядку, Enter, і тепер, якщо все піде добре,

61
00:03:34,000 --> 00:03:38,000
він збирається перевірити, а потім повертають результат, затримайте дихання-

62
00:03:38,000 --> 00:03:42,000
Все зелене, а це значить, що я роблю дуже добре на PSET 4 до цих пір.

63
00:03:42,000 --> 00:03:44,000
Ви можете бачити і вивести з описового тексту тут

64
00:03:44,000 --> 00:03:47,000
точно, що це ми перевірили.

65
00:03:47,000 --> 00:03:49,000
Ми протестували перший же файли існують?

66
00:03:49,000 --> 00:03:51,000
Ми тоді протестовані робить Зміна розміру компіляції?

67
00:03:51,000 --> 00:03:58,000
Потім ми перевірили це не розмір 1x1 піксель BMP, коли п, зміна розміру фактор, 1.

68
00:03:58,000 --> 00:04:01,000
Тепер, якщо ви не знаєте, що п, ви будете тільки ви зануритися в PSET 4,

69
00:04:01,000 --> 00:04:04,000
але це просто розсудливість перевірити, щоб переконатися, що ви не зміна розміру

70
00:04:04,000 --> 00:04:08,000
Зображення взагалі, якщо зміна розміру коефіцієнт дорівнює 1.

71
00:04:08,000 --> 00:04:14,000
Якщо ж, навпаки, він змінює 1x1 піксель в піксель 1x1 2x2 BMP, щоб правильно

72
00:04:14,000 --> 00:04:19,000
при п = 2, то аналогічно, мій формує відповідно.

73
00:04:19,000 --> 00:04:22,000
>> Коротше кажучи, це означало, один, приймати перетину пальців

74
00:04:22,000 --> 00:04:25,000
з рівняння право, перш ніж подати PSET.

75
00:04:25,000 --> 00:04:28,000
Ви будете точно знати, що ваш TF скоро дізнаємося

76
00:04:28,000 --> 00:04:30,000
коли ви йдете про відправку деяких з цих наборів проблеми,

77
00:04:30,000 --> 00:04:34,000
а також педагогічні мотивація дійсно поставити

78
00:04:34,000 --> 00:04:37,000
можливість перед вами, так що, коли ви знаєте, апріорно

79
00:04:37,000 --> 00:04:39,000
що є помилки в коді і тестах, які не пройшли,

80
00:04:39,000 --> 00:04:43,000
Ви можете помістити в більш ефективні часу попереду, щоб вирішити ці проблеми

81
00:04:43,000 --> 00:04:45,000
, А не втрачати очки, отримати зворотній зв'язок від ваших TF,

82
00:04:45,000 --> 00:04:48,000
, А потім йти, "Ах", як я зрозумів це.

83
00:04:48,000 --> 00:04:50,000
Тепер принаймні є інструмент, щоб допомогти вам знайти це.

84
00:04:50,000 --> 00:04:52,000
Це не збирається вказати, де помилка, але вона скаже вам,

85
00:04:52,000 --> 00:04:54,000
, Що є симптомом його.

86
00:04:54,000 --> 00:04:57,000
>> Тепер розумію, тести не є вичерпним.

87
00:04:57,000 --> 00:04:59,000
Просто тому, що ви отримуєте екран, повний зелених смайликів

88
00:04:59,000 --> 00:05:02,000
не означає, що ваш код є досконалою, але це не означає,

89
00:05:02,000 --> 00:05:06,000
що вона пройшла певні випробування, передбачені в специфікації.

90
00:05:06,000 --> 00:05:08,000
Іноді ми не випустимо перевірок.

91
00:05:08,000 --> 00:05:10,000
Наприклад, детективний роман, одним з аспектів PSET 4,

92
00:05:10,000 --> 00:05:15,000
це свого роду розчарування, якщо ми даємо вам

93
00:05:15,000 --> 00:05:18,000
відповідь на питання, що це таке, і є кілька способів, щоб показати

94
00:05:18,000 --> 00:05:21,000
хто ця людина в тому, що червоні шуму.

95
00:05:21,000 --> 00:05:24,000
У специфікації будуть завжди вказувати в майбутньому для PSET 5 уперед

96
00:05:24,000 --> 00:05:26,000
Які види контролю існують для вас.

97
00:05:26,000 --> 00:05:28,000
Ви помітите, що це за білі URL в нижній частині.

98
00:05:28,000 --> 00:05:30,000
На даний момент це всього лише діагностичний вихід.

99
00:05:30,000 --> 00:05:33,000
Якщо ви відвідаєте цю адресу, ви отримаєте цілу купу божевільних, загадкові повідомлення

100
00:05:33,000 --> 00:05:36,000
що ви можете переглядати, але це в основному для співробітників

101
00:05:36,000 --> 00:05:41,000
так що ми можемо діагностувати і налагоджувати помилки в check50 себе.

102
00:05:41,000 --> 00:05:46,000
>> Без церемоній, давайте перейдемо туди, де ми зупинилися.

103
00:05:46,000 --> 00:05:48,000
CS50 бібліотеці ми вважали само собою зрозумілим протягом декількох тижнів,

104
00:05:48,000 --> 00:05:52,000
але потім на минулому тижні, ми почали пілінг тому один з шарів його.

105
00:05:52,000 --> 00:05:55,000
Ми почали відклавши рядок на користь того, що замість цього?

106
00:05:55,000 --> 00:05:57,000
[Студенти] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, який був символ * весь цей час,

108
00:05:59,000 --> 00:06:03,000
але тепер ми не повинні вдавати, що це фактичний тип даних рядок.

109
00:06:03,000 --> 00:06:06,000
Швидше, це був синонім роду для символів *,

110
00:06:06,000 --> 00:06:09,000
і рядок являє собою послідовність символів,

111
00:06:09,000 --> 00:06:14,000
Так чому це має сенс представляти рядки як символ * з?

112
00:06:14,000 --> 00:06:20,000
Що означає символ * представляє в контексті цієї концепції рядки?

113
00:06:20,000 --> 00:06:23,000
Так. >> [Студент] перший символ.

114
00:06:23,000 --> 00:06:25,000
Добре, перший символ, але не зовсім перший символ.

115
00:06:25,000 --> 00:06:27,000
Це-[Студенти] адресу.

116
00:06:27,000 --> 00:06:29,000
Добре, адреса першого символу.

117
00:06:29,000 --> 00:06:33,000
Все, що необхідно для подання рядків в пам'яті комп'ютера

118
00:06:33,000 --> 00:06:36,000
це просто унікальний адресу самого першого байта.

119
00:06:36,000 --> 00:06:38,000
Вам навіть не потрібно знати, як довго це

120
00:06:38,000 --> 00:06:42,000
тому що, як ви можете зрозуміти, що з динамічно?

121
00:06:42,000 --> 00:06:44,000
[Студент] довжина рядка.

122
00:06:44,000 --> 00:06:48,000
Ви можете зателефонувати довжина рядка, відмінно, але як робота довжину рядка?

123
00:06:48,000 --> 00:06:50,000
Що він робить? Так.

124
00:06:50,000 --> 00:06:52,000
[Студент] Продовжуйте, поки не отримаєте нульовий символ.

125
00:06:52,000 --> 00:06:54,000
Так, точно, він просто виконує ітерації з циклу, в той час як цикл,

126
00:06:54,000 --> 00:06:57,000
незалежно від * до кінця, і в кінці представлено

127
00:06:57,000 --> 00:07:01,000
на \ 0, так званої нульової символ, н,

128
00:07:01,000 --> 00:07:05,000
Не плутати з нульовим, який є дороговказом,

129
00:07:05,000 --> 00:07:07,000
який вступить в розмову знову сьогодні.

130
00:07:07,000 --> 00:07:11,000
>> Ми очищені назад шаром GetInt, і тоді ми поглянули на GetString,

131
00:07:11,000 --> 00:07:14,000
і нагадаємо, що обидві ці функції, або дійсно,

132
00:07:14,000 --> 00:07:18,000
GetString, було використання певних функцій

133
00:07:18,000 --> 00:07:21,000
насправді розібрати, тобто, читати і аналізувати, введених користувачем.

134
00:07:21,000 --> 00:07:25,000
І що це за нова функція?

135
00:07:25,000 --> 00:07:27,000
Scanf або Sscanf. Це насправді відбувається в кілька різних ароматів.

136
00:07:27,000 --> 00:07:31,000
Там в SCANF, є Sscanf, є fscanf.

137
00:07:31,000 --> 00:07:35,000
Зараз, однак, давайте зосередимося на один найбільш легко проілюструвати,

138
00:07:35,000 --> 00:07:38,000
і дозвольте мені йти вперед і відкрити в приладі

139
00:07:38,000 --> 00:07:41,000
Файл, як це, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Це супер проста програма,

141
00:07:43,000 --> 00:07:46,000
але що робить щось, що ми ніколи не робили

142
00:07:46,000 --> 00:07:48,000
без допомоги CS50 бібліотеки.

143
00:07:48,000 --> 00:07:51,000
Це стає Int від користувача. Як це працює?

144
00:07:51,000 --> 00:07:53,000
Ну, а в рядку 16 є,

145
00:07:53,000 --> 00:07:56,000
помітите, що ми заявляємо Int називається х, і в цей момент в історії,

146
00:07:56,000 --> 00:07:58,000
що таке значення х?

147
00:07:58,000 --> 00:08:00,000
[Нерозбірливо відповідь студента]

148
00:08:00,000 --> 00:08:02,000
[David M.] Право, хто знає, сміття значення потенційно, так і в 17, ми просто повідомити користувачеві

149
00:08:02,000 --> 00:08:06,000
дайте мені номер, будь ласка, і крок 18, де це стає цікавим.

150
00:08:06,000 --> 00:08:11,000
Scanf здається запозичувати ідеї з Printf в тому, що він використовує формат кодів в лапки.

151
00:08:11,000 --> 00:08:13,000
% D, звичайно, десяткове число.

152
00:08:13,000 --> 00:08:21,000
Але чому я проходить в & х, а не просто х?

153
00:08:21,000 --> 00:08:24,000
Колишній правильно. Так.

154
00:08:24,000 --> 00:08:26,000
[Нерозбірливо відповідь студента]

155
00:08:26,000 --> 00:08:31,000
Саме, якщо мета цієї програми, як і функція GetInt себе,

156
00:08:31,000 --> 00:08:34,000
, Щоб отримати ціле число від користувачів я можу передати функції

157
00:08:34,000 --> 00:08:38,000
всі змінні, я хочу, але якщо я не передавати їх по посиланню

158
00:08:38,000 --> 00:08:41,000
або за адресою або за вказівником, все синонімом для цілей сьогоднішньої,

159
00:08:41,000 --> 00:08:46,000
то ця функція не має можливості змінювати вміст цієї змінної.

160
00:08:46,000 --> 00:08:49,000
Це повинно передати в копії, як баггі версії своп

161
00:08:49,000 --> 00:08:51,000
що ми говорили про кілька разів тепер.

162
00:08:51,000 --> 00:08:54,000
>> Але замість цього, роблячи & х, я буквально проходить в чому?

163
00:08:54,000 --> 00:08:57,000
[Студент] адресу. >> Адресу х.

164
00:08:57,000 --> 00:09:01,000
Це схоже на малювання карти для функції називається SCANF і говорять тут,

165
00:09:01,000 --> 00:09:04,000
ці напрямки шматок пам'яті в комп'ютері

166
00:09:04,000 --> 00:09:07,000
що ви можете піти зберігати деяке ціле дюйма

167
00:09:07,000 --> 00:09:10,000
Для того, щоб Sscanf досі зробити це

168
00:09:10,000 --> 00:09:13,000
який оператор, що частина синтаксису цього доведеться використовувати

169
00:09:13,000 --> 00:09:19,000
навіть якщо ми не можемо бачити, тому що хтось інший написав цю функцію?

170
00:09:19,000 --> 00:09:21,000
Іншими словами - що це таке?

171
00:09:21,000 --> 00:09:23,000
[Студент] X читати.

172
00:09:23,000 --> 00:09:27,000
Там збирається бути деякий читання, але тільки у відношенні х тут.

173
00:09:27,000 --> 00:09:30,000
Якщо SCANF в даний час передається адреса х,

174
00:09:30,000 --> 00:09:35,000
Синтаксично, що оператор зобов'язаний існувати десь

175
00:09:35,000 --> 00:09:38,000
Усередині реалізації SCANF так, що SCANF

176
00:09:38,000 --> 00:09:42,000
дійсно може написати номер 2 за цією адресою?

177
00:09:42,000 --> 00:09:44,000
Так, так *.

178
00:09:44,000 --> 00:09:47,000
Нагадаємо, що * це наш оператор разименованія, яка по суті означає піти туди.

179
00:09:47,000 --> 00:09:50,000
>> Після того як ви передали адреси, як в даному випадку,

180
00:09:50,000 --> 00:09:53,000
SCANF, ймовірно, якщо ми насправді оглянув його вихідний код-

181
00:09:53,000 --> 00:09:59,000
робить * х або еквівалент насправді піти за цією адресою і покласти деяке значення там.

182
00:09:59,000 --> 00:10:02,000
Тепер, як і про те, як SCANF отримує введення з клавіатури,

183
00:10:02,000 --> 00:10:04,000
ми махаємо руками за сьогодні.

184
00:10:04,000 --> 00:10:07,000
Просто припустимо, що операційна система дозволяє Sscanf говорити

185
00:10:07,000 --> 00:10:11,000
з клавіатури користувачем, але на даний момент зараз в рядку 19,

186
00:10:11,000 --> 00:10:14,000
Коли ми просто роздрукувати х, це, здається, випадок

187
00:10:14,000 --> 00:10:17,000
що SCANF поставив Int х.

188
00:10:17,000 --> 00:10:19,000
Це точно, як SCANF працює, і згадати останній тиждень

189
00:10:19,000 --> 00:10:25,000
це точно, як GetString і GetInt та інших його сімейство функцій

190
00:10:25,000 --> 00:10:28,000
в кінцевому підсумку працює, хоча і з невеликим дисперсії, як Sscanf,

191
00:10:28,000 --> 00:10:31,000
що означає сканування рядків замість клавіатури.

192
00:10:31,000 --> 00:10:33,000
Але давайте поглянемо на невеликої різниці в цьому.

193
00:10:33,000 --> 00:10:37,000
У scanf2, я дійсно облажався.

194
00:10:37,000 --> 00:10:42,000
Що не так, і я сховаю коментар, що пояснює, як багато-

195
00:10:42,000 --> 00:10:47,000
що не так з цією програмою, версія 2?

196
00:10:47,000 --> 00:10:55,000
Будьте як технічні можливості на цей раз.

197
00:10:55,000 --> 00:10:57,000
Це виглядає досить добре.

198
00:10:57,000 --> 00:11:03,000
Це приємно відступу, але-

199
00:11:03,000 --> 00:11:07,000
Добре, а як щодо давайте скорочувати його до коротких запитань?

200
00:11:07,000 --> 00:11:17,000
Лінія 16. Що робити лінії 16 в точною, але технічний англійську мову?

201
00:11:17,000 --> 00:11:20,000
Отримання трохи ніяково. Так, Майкл.

202
00:11:20,000 --> 00:11:25,000
[Студент] Це вказує на перші літери рядків.

203
00:11:25,000 --> 00:11:27,000
>> Добре, близько. Дозвольте мені налаштувати, що небагато.

204
00:11:27,000 --> 00:11:33,000
Вказуючи на першу букву рядка, ви оголошуєте змінну буфера

205
00:11:33,000 --> 00:11:36,000
, Що буде вказувати на перший адреса рядка,

206
00:11:36,000 --> 00:11:39,000
або, скоріше, буде вказувати більш конкретно символ.

207
00:11:39,000 --> 00:11:42,000
Зверніть увагу, що це насправді не вказуючи де завгодно, тому що немає оператора присвоювання.

208
00:11:42,000 --> 00:11:46,000
Там немає знаку рівності, тому все, що ми робимо, виділення змінної званого буфера.

209
00:11:46,000 --> 00:11:49,000
Це трапляється, 32 біт, тому що це покажчик,

210
00:11:49,000 --> 00:11:52,000
і вміст буфера імовірно в кінці кінців

211
00:11:52,000 --> 00:11:57,000
буде містити адресу символ, але зараз, що ж буфері містити?

212
00:11:57,000 --> 00:11:59,000
Просто деякі фіктивні, хто знає, сміття значення,

213
00:11:59,000 --> 00:12:03,000
тому, що ми явно не ініціалізований, так що ми не повинні припускати, що завгодно.

214
00:12:03,000 --> 00:12:06,000
Отже, тепер лінія 17,-що ж лінії 17 робити?

215
00:12:06,000 --> 00:12:08,000
Може бути, зігріє це.

216
00:12:08,000 --> 00:12:10,000
Вона виводить рядок, чи не так?

217
00:12:10,000 --> 00:12:12,000
Він друкує струнного ласка.

218
00:12:12,000 --> 00:12:15,000
>> Рядок 18 є своєрідною знайомий тепер в тому, що ми тільки що бачили дисперсія цього

219
00:12:15,000 --> 00:12:18,000
але з іншим кодом формату, так і в рядку 18,

220
00:12:18,000 --> 00:12:23,000
ми говоримо SCANF тут є адресою блоку пам'яті.

221
00:12:23,000 --> 00:12:27,000
Я хочу, щоб ти дзвонив в рядок, як це мається на увазі% З,

222
00:12:27,000 --> 00:12:32,000
але проблема в тому, що ми не зробили пару речей.

223
00:12:32,000 --> 00:12:35,000
Що одна з проблем?

224
00:12:35,000 --> 00:12:38,000
[Студент] Це спроба разименованія нульового покажчика.

225
00:12:38,000 --> 00:12:41,000
Добре, нульові або просто в іншому випадку невідомі покажчиків.

226
00:12:41,000 --> 00:12:45,000
Ви вручення SCANF адресу, але ви тільки що сказали хвилину тому

227
00:12:45,000 --> 00:12:49,000
, Що адреса сміття значення, тому що ми насправді не присвоїти йому ні до чого,

228
00:12:49,000 --> 00:12:53,000
і тому ви говорите SCANF ефективно йти покласти рядки тут,

229
00:12:53,000 --> 00:12:56,000
але ми не знаємо, де тут ще є,

230
00:12:56,000 --> 00:12:59,000
так що ми, власне, не виділеної пам'яті для буфера.

231
00:12:59,000 --> 00:13:03,000
Крім того, що ви теж навіть не кажу SCANF?

232
00:13:03,000 --> 00:13:06,000
Припустимо, що це був шматок пам'яті, і це не було сміття значення,

233
00:13:06,000 --> 00:13:09,000
але ви все ще не говорив SCANF щось важливе.

234
00:13:09,000 --> 00:13:12,000
[Студент] Де насправді, амперсанд.

235
00:13:12,000 --> 00:13:15,000
Амперсанд, тому в даному випадку, це нормально.

236
00:13:15,000 --> 00:13:18,000
Тому що буфер уже оголошений як покажчик

237
00:13:18,000 --> 00:13:22,000
з * частину синтаксису, ми не повинні використовувати амперсанд

238
00:13:22,000 --> 00:13:25,000
тому що це вже адресу, але я думаю, що я чув, це тут.

239
00:13:25,000 --> 00:13:27,000
[Студент] Як він великий?

240
00:13:27,000 --> 00:13:29,000
Добре, що ми не говоримо SCANF, наскільки великий цей буфер,

241
00:13:29,000 --> 00:13:32,000
який означає, що навіть якщо буфер був покажчик,

242
00:13:32,000 --> 00:13:35,000
Ми говоримо SCANF, покласти тут рядок,

243
00:13:35,000 --> 00:13:38,000
Але тут може бути 2 байти, це може бути 10 байт, він може бути мегабайт.

244
00:13:38,000 --> 00:13:41,000
Scanf поняття не має, а тому, що це шматок пам'яті

245
00:13:41,000 --> 00:13:43,000
Імовірно, це не рядок, поки немає.

246
00:13:43,000 --> 00:13:48,000
Це всього лише рядок, як тільки ви писати символи і \ 0 до цього шматок пам'яті.

247
00:13:48,000 --> 00:13:51,000
Тепер це лише деякі шматок пам'яті.

248
00:13:51,000 --> 00:13:55,000
Scanf не буде знати, коли перестати писати за цією адресою.

249
00:13:55,000 --> 00:13:59,000
>> Якщо згадати деякі приклади в минулому, коли я випадково набрав на клавіатурі

250
00:13:59,000 --> 00:14:03,000
намагається переповнення буферу, і ми говорили в п'ятницю про саме це.

251
00:14:03,000 --> 00:14:07,000
Якщо супротивник якимсь чином вводить в свій програмі набагато більше слів

252
00:14:07,000 --> 00:14:10,000
або речення або фразу, то ви очікували, ви можете перевитрати

253
00:14:10,000 --> 00:14:13,000
частину пам'яті, яка може мати погані наслідки,

254
00:14:13,000 --> 00:14:15,000
як приймати по всій програмі.

255
00:14:15,000 --> 00:14:17,000
Ми повинні виправити це якось.

256
00:14:17,000 --> 00:14:20,000
Дозвольте мені масштаб і йдіть в 3-й версії цієї програми.

257
00:14:20,000 --> 00:14:22,000
Це трохи краще.

258
00:14:22,000 --> 00:14:24,000
У цій версії, помітите різницю.

259
00:14:24,000 --> 00:14:27,000
У рядку 16, я ще раз оголосити змінну буфера,

260
00:14:27,000 --> 00:14:29,000
але те, що вона зараз?

261
00:14:29,000 --> 00:14:33,000
Це масив з 16 символів.

262
00:14:33,000 --> 00:14:36,000
Це добре, тому що це означає, я можу тепер сказати SCANF

263
00:14:36,000 --> 00:14:39,000
Тут фактично шматок пам'яті.

264
00:14:39,000 --> 00:14:42,000
Ви можете подумати, масиви покажчиків як зараз,

265
00:14:42,000 --> 00:14:44,000
навіть якщо вони насправді не еквівалентні.

266
00:14:44,000 --> 00:14:47,000
Вони ведуть себе по-різному в різних контекстах.

267
00:14:47,000 --> 00:14:50,000
Але це, звичайно, справа, що буфер посилання

268
00:14:50,000 --> 00:14:53,000
16 послідовних символів, тому що це те, що масив

269
00:14:53,000 --> 00:14:55,000
і був протягом декількох тижнів.

270
00:14:55,000 --> 00:14:59,000
>> Ось, я кажу SCANF ось шматок пам'яті.

271
00:14:59,000 --> 00:15:01,000
На цей раз, це насправді частина пам'яті,

272
00:15:01,000 --> 00:15:07,000
Але чому цієї програми досі вразливостям?

273
00:15:07,000 --> 00:15:11,000
Що сталося ще?

274
00:15:11,000 --> 00:15:14,000
Я вже говорив, дайте мені 16 байт, але-

275
00:15:14,000 --> 00:15:16,000
[Студент] Що робити, якщо вони друкують більш ніж в 16?

276
00:15:16,000 --> 00:15:20,000
Ось саме, що якщо користувач вводить 17 символів або 1700 символів?

277
00:15:20,000 --> 00:15:23,000
У самому справі, давайте подивимося, якщо ми не можемо спіткнутися цю помилку зараз.

278
00:15:23,000 --> 00:15:25,000
Це краще, але не ідеально.

279
00:15:25,000 --> 00:15:28,000
Дозвольте мені йти вперед і працювати scanf3 зробити для компіляції цієї програми.

280
00:15:28,000 --> 00:15:34,000
Дозвольте мені виконати scanf3, String ласка: привіт, і ми, здається, в порядку.

281
00:15:34,000 --> 00:15:37,000
Дозвольте мені спробувати трохи більше одного, привіт.

282
00:15:37,000 --> 00:15:42,000
Добре, давайте зробимо привіт, як справи, Enter.

283
00:15:42,000 --> 00:15:54,000
Отримання виду пощастило тут, скажімо, привіт як справи.

284
00:15:54,000 --> 00:15:56,000
Чорт візьми.

285
00:15:56,000 --> 00:16:03,000
Отже, нам пощастило. Давайте подивимося, якщо ми не можемо це виправити.

286
00:16:03,000 --> 00:16:06,000
Ні, вона не збирається дозволити мені скопіювати.

287
00:16:06,000 --> 00:16:09,000
Давайте спробуємо це знову.

288
00:16:09,000 --> 00:16:12,000
Гаразд, стояти осторонь.

289
00:16:12,000 --> 00:16:20,000
Ми побачимо, як довго я можу прикидатися, щоб зосередитися в той же час зробити це.

290
00:16:20,000 --> 00:16:23,000
Чорт візьми. Це досить необхідності, насправді.

291
00:16:23,000 --> 00:16:26,000
Там ми йдемо.

292
00:16:26,000 --> 00:16:30,000
Точка зробив.

293
00:16:30,000 --> 00:16:34,000
>> Це, ніяково, хоча воно і є, він також є одним з джерел більшу плутанину

294
00:16:34,000 --> 00:16:38,000
При написанні програм, які мають помилки, тому що вони проявляються

295
00:16:38,000 --> 00:16:40,000
Тільки раз в той час іноді.

296
00:16:40,000 --> 00:16:43,000
Реальність така, що навіть якщо ваш код повністю зламана,

297
00:16:43,000 --> 00:16:46,000
це може бути повністю зруйнована раз в той час

298
00:16:46,000 --> 00:16:49,000
тому що іноді, по суті, відбувається те, виділяє операційної системи

299
00:16:49,000 --> 00:16:52,000
трохи більше пам'яті, ніж вам дійсно потрібно по будь-якої причини,

300
00:16:52,000 --> 00:16:57,000
і так ніхто не використовує пам'ять відразу після шматок з 16 символів,

301
00:16:57,000 --> 00:17:01,000
так що якщо ви йдете в 17, 18, 19, незалежно, це не така велика проблема.

302
00:17:01,000 --> 00:17:04,000
Тепер, комп'ютер, навіть якщо вона не звалиться в той момент,

303
00:17:04,000 --> 00:17:09,000
в кінцевому підсумку може використовувати Байт номер 17 або 18, або 19 на щось інше,

304
00:17:09,000 --> 00:17:14,000
У цей момент ваші дані, які ви створили, хоча і надмірно довгими,

305
00:17:14,000 --> 00:17:18,000
буде втрачено потенційно деякі інші функції.

306
00:17:18,000 --> 00:17:21,000
Це не обов'язково залишиться недоторканим,

307
00:17:21,000 --> 00:17:23,000
але це не обов'язково викликати сегменті вина.

308
00:17:23,000 --> 00:17:26,000
Але в даному випадку, я, нарешті, надали достатньо символів

309
00:17:26,000 --> 00:17:29,000
що я суттєво перевищив мої сегмент пам'яті, і бац,

310
00:17:29,000 --> 00:17:33,000
Операційна система сказала: "Вибач, це не добре, помилки сегментації."

311
00:17:33,000 --> 00:17:38,000
>> І давайте подивимося тепер, якщо те, що залишається тут, в моєму каталогу

312
00:17:38,000 --> 00:17:40,000
помітив, що у мене є цей файл тут, ядро.

313
00:17:40,000 --> 00:17:42,000
Зверніть увагу, що це знову закликав дамп пам'яті.

314
00:17:42,000 --> 00:17:46,000
По суті, це файл, який містить вміст пам'яті програми

315
00:17:46,000 --> 00:17:48,000
в точці, в якій він розбився,

316
00:17:48,000 --> 00:17:51,000
і просто спробувати маленький приклад тут відпустити мене тут

317
00:17:51,000 --> 00:17:57,000
і запустити GDB на scanf3 а потім вказати третій аргумент називається ядром,

318
00:17:57,000 --> 00:18:01,000
і помітити тут, що якщо я перераховую код,

319
00:18:01,000 --> 00:18:06,000
ми зможемо, як звичайно, з GDB, щоб почати ходити через цю програму,

320
00:18:06,000 --> 00:18:10,000
і я можу запустити його, і як тільки я потрапив-як з кроком команди в GDB-

321
00:18:10,000 --> 00:18:13,000
Як тільки я потрапив в потенційно баггі лінії після введення в величезній рядку,

322
00:18:13,000 --> 00:18:16,000
Я зможу насправді визначити його тут.

323
00:18:16,000 --> 00:18:19,000
Детальніше про це, хоча, в розділі з точки зору дампи

324
00:18:19,000 --> 00:18:22,000
і т.п., так що ви можете копатися всередині дампа

325
00:18:22,000 --> 00:18:27,000
і подивитися, на якому рядку програми не ви.

326
00:18:27,000 --> 00:18:32,000
Будь-які питання, то на покажчики й на адреси?

327
00:18:32,000 --> 00:18:36,000
Тому що сьогодні, ми збираємося почати приймати як належне, що ці речі існують

328
00:18:36,000 --> 00:18:40,000
і ми точно знаємо, що вони є.

329
00:18:40,000 --> 00:18:42,000
Так.

330
00:18:42,000 --> 00:18:46,000
>> [Студент] Чому ви не повинні поставити амперсанд поруч з частини-

331
00:18:46,000 --> 00:18:48,000
Хороше питання.

332
00:18:48,000 --> 00:18:51,000
Чому у мене не було поставити амперсанд поруч з масив символів, як я зробив раніше

333
00:18:51,000 --> 00:18:53,000
з більшістю наших прикладах?

334
00:18:53,000 --> 00:18:55,000
Коротка відповідь полягає в масивах трохи особливим.

335
00:18:55,000 --> 00:18:59,000
Ви можете подумати, буфер, що насправді є адресою,

336
00:18:59,000 --> 00:19:03,000
і так уже сталося, щоб бути так, що площа позначення кронштейна

337
00:19:03,000 --> 00:19:06,000
є зручним, так що ми можемо піти в кронштейн 0, кронштейн 1,

338
00:19:06,000 --> 00:19:10,000
Кронштейн 2, не вдаючись до використання * позначень.

339
00:19:10,000 --> 00:19:13,000
Це трохи білого брехня, тому що масиви і покажчики

340
00:19:13,000 --> 00:19:17,000
, Насправді, трохи по-іншому, але вони можуть часто, але не завжди використовуються як взаємозамінні.

341
00:19:17,000 --> 00:19:21,000
Коротше кажучи, коли функція очікує покажчик на ділянку пам'яті,

342
00:19:21,000 --> 00:19:24,000
Ви можете або передати його адресу, який був повернутий Танос,

343
00:19:24,000 --> 00:19:29,000
і ми побачимо, Танос знову незабаром, або ви можете передати його ім'я масиву.

344
00:19:29,000 --> 00:19:32,000
Ви не повинні робити амперсанд з масивами, тому що вони вже

345
00:19:32,000 --> 00:19:34,000
істотно хотів адрес.

346
00:19:34,000 --> 00:19:36,000
Це один виняток.

347
00:19:36,000 --> 00:19:39,000
У квадратних дужках зробити їх особливими.

348
00:19:39,000 --> 00:19:41,000
>> Не могли б ви покласти амперсанд поруч з буфером?

349
00:19:41,000 --> 00:19:43,000
Не в цьому справа.

350
00:19:43,000 --> 00:19:46,000
Це не буде працювати, тому що, знову ж таки, цього куточка випадку

351
00:19:46,000 --> 00:19:49,000
де масиви насправді не зовсім адреси.

352
00:19:49,000 --> 00:19:54,000
Але ми, можливо, повернемося до цього незабаром з іншими прикладами.

353
00:19:54,000 --> 00:19:56,000
Давайте спробуємо вирішити проблему тут.

354
00:19:56,000 --> 00:20:00,000
У нас є структури даних, які ми використовували протягом деякого часу відомо як масив.

355
00:20:00,000 --> 00:20:02,000
Справа в точку, це те, що ми просто не було.

356
00:20:02,000 --> 00:20:04,000
Але масиви мають деякі плюси і мінуси.

357
00:20:04,000 --> 00:20:06,000
Масиви є хорошим чому?

358
00:20:06,000 --> 00:20:11,000
Що одна річ, яка вам подобається, в тій мірі, вам подобається масиви про масивах?

359
00:20:11,000 --> 00:20:13,000
Що зручно про них? Що переконливим?

360
00:20:13,000 --> 00:20:18,000
Чому ми введемо їх в першу чергу?

361
00:20:18,000 --> 00:20:20,000
Так.

362
00:20:20,000 --> 00:20:27,000
[Студент] Вони можуть зберігати великий обсяг даних, і вам не доведеться використовувати всю річ.

363
00:20:27,000 --> 00:20:29,000
Ви можете використовувати розділ.

364
00:20:29,000 --> 00:20:32,000
Добре, з масивом можна зберігати велику кількість даних,

365
00:20:32,000 --> 00:20:35,000
і вам не обов'язково використовувати все це, так що ви можете overallocate,

366
00:20:35,000 --> 00:20:39,000
що може бути зручно, якщо ви не знаєте заздалегідь, скільки чогось чекати.

367
00:20:39,000 --> 00:20:41,000
>> GetString є прекрасним прикладом.

368
00:20:41,000 --> 00:20:44,000
GetString, написані нами, поняття не має, скільки символів очікувати,

369
00:20:44,000 --> 00:20:48,000
Тому той факт, що ми можемо виділити шматки безперервної пам'яті це добре.

370
00:20:48,000 --> 00:20:51,000
Масиви також вирішити проблему, ми побачили пару тижнів тому, тепер

371
00:20:51,000 --> 00:20:54,000
, Де ваш код починає перетвориться на щось дуже погано розроблена.

372
00:20:54,000 --> 00:20:57,000
Нагадаємо, що Я створив студент на ім'я Девід структури,

373
00:20:57,000 --> 00:21:00,000
а потім, що було насправді альтернатива, хоча,

374
00:21:00,000 --> 00:21:04,000
до того змінної ім'я та іншу змінну, я думаю, будинки,

375
00:21:04,000 --> 00:21:08,000
і інша змінна ID, тому що в цій історії я тоді хотів представити щось інше

376
00:21:08,000 --> 00:21:11,000
Роб подобається в програмі, так що потім я вирішив почекати хвилину,

377
00:21:11,000 --> 00:21:13,000
Мені потрібно перейменувати ці змінні.

378
00:21:13,000 --> 00:21:16,000
Давайте називати моє name1, ID1, House1.

379
00:21:16,000 --> 00:21:20,000
Давайте назвемо Роба name2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Але почекайте хвилинку, що про Томмі?

381
00:21:22,000 --> 00:21:24,000
Тоді у нас було ще три змінні.

382
00:21:24,000 --> 00:21:27,000
Ми ввели когось іншого, чотири набори змінних.

383
00:21:27,000 --> 00:21:30,000
Світ почав заплутатися дуже швидко,

384
00:21:30,000 --> 00:21:33,000
таким чином, ми ввели структури, і те, що переконливих про структуру?

385
00:21:33,000 --> 00:21:39,000
Що структуру C дозволити вам зробити?

386
00:21:39,000 --> 00:21:42,000
Це дуже незручно сьогодні.

387
00:21:42,000 --> 00:21:44,000
Що? >> [Нерозбірливо відповідь студента]

388
00:21:44,000 --> 00:21:47,000
Так, зокрема, ЬурейеЕ дозволяє створити новий тип даних,

389
00:21:47,000 --> 00:21:51,000
і структури, структури ключових слів, дозволяє інкапсулювати

390
00:21:51,000 --> 00:21:54,000
концептуально пов'язані елементи даних разом

391
00:21:54,000 --> 00:21:56,000
і після цього називати їх чимось на зразок студента.

392
00:21:56,000 --> 00:21:58,000
>> Це було добре, тому що тепер ми можемо змоделювати

393
00:21:58,000 --> 00:22:03,000
набагато більше роду концептуально відповідає поняттю студента в змінну

394
00:22:03,000 --> 00:22:07,000
, А не довільно мають один для рядка, по одному для ID, і так далі.

395
00:22:07,000 --> 00:22:10,000
Масиви приємно, тому що вони дозволяють почати прибирання нашого коду.

396
00:22:10,000 --> 00:22:13,000
Але те, що є і зворотна сторона тепер масиву?

397
00:22:13,000 --> 00:22:15,000
Що ви можете не робити? Так.

398
00:22:15,000 --> 00:22:17,000
[Студент] Ви повинні знати, наскільки вона велика.

399
00:22:17,000 --> 00:22:19,000
Ви повинні знати, наскільки він великий, так що це вид болю.

400
00:22:19,000 --> 00:22:21,000
Ті з вас, з досвідом програмування знаємо, що в багатьох мовах,

401
00:22:21,000 --> 00:22:24,000
як Java, ви можете попросити шматок пам'яті, зокрема масиву,

402
00:22:24,000 --> 00:22:28,000
наскільки великий ти, з довжиною, власність, так би мовити, і це дійсно зручно.

403
00:22:28,000 --> 00:22:32,000
У C, ви не можете навіть назвати StrLen на загальному масиві

404
00:22:32,000 --> 00:22:35,000
тому що StrLen, як слово має на увазі, тільки для рядків,

405
00:22:35,000 --> 00:22:39,000
і ви можете з'ясувати довжину рядка, тому що цю людину конвенції

406
00:22:39,000 --> 00:22:43,000
наявності \ 0, але масиві, в більш загальному, це просто шматок пам'яті.

407
00:22:43,000 --> 00:22:46,000
Якщо це масив цілих чисел, там не буде якийсь особливий характер

408
00:22:46,000 --> 00:22:48,000
В кінці вас чекає.

409
00:22:48,000 --> 00:22:50,000
Ви повинні пам'ятати, довжина масиву.

410
00:22:50,000 --> 00:22:54,000
Ще одним недоліком масиву підняв свою голову в GetString себе.

411
00:22:54,000 --> 00:22:59,000
Що ще одним недоліком масиву?

412
00:22:59,000 --> 00:23:01,000
Сер, тільки ти і я сьогодні.

413
00:23:01,000 --> 00:23:04,000
[Нерозбірливо відповідь студента] >> Це що?

414
00:23:04,000 --> 00:23:06,000
Він оголошений у стеці.

415
00:23:06,000 --> 00:23:09,000
Добре, заявив в стеці. Чому б вам не подобається?

416
00:23:09,000 --> 00:23:13,000
[Студент] Тому що він буде використовувати повторно.

417
00:23:13,000 --> 00:23:15,000
Він отримує повторно.

418
00:23:15,000 --> 00:23:18,000
Добре, якщо ви використовуєте масив для виділення пам'яті,

419
00:23:18,000 --> 00:23:21,000
Ви не можете, наприклад, повернутися, тому що це в стеці.

420
00:23:21,000 --> 00:23:23,000
Добре, що це недолік.

421
00:23:23,000 --> 00:23:25,000
А як щодо ще одного з масивом?

422
00:23:25,000 --> 00:23:28,000
Після того як ви виділите її, ти ніби п'яний, якщо вам потрібно більше місця

423
00:23:28,000 --> 00:23:30,000
, Ніж у масиву.

424
00:23:30,000 --> 00:23:34,000
>> Тоді ми ввели, нагадаємо, Танос, який дав нам можливість динамічного виділення пам'яті.

425
00:23:34,000 --> 00:23:37,000
Але що, якщо ми спробували інший світ?

426
00:23:37,000 --> 00:23:40,000
Що якщо ми хочемо, щоб вирішити пару з тих проблем,

427
00:23:40,000 --> 00:23:45,000
так що ми замість-моє перо заснув тут-

428
00:23:45,000 --> 00:23:51,000
Що робити, якщо ми замість цього хотіли суті створити світ, який уже не так?

429
00:23:51,000 --> 00:23:56,000
Це масив, і, звичайно ж, цей вид погіршується, як тільки ми потрапили в кінець масиву,

430
00:23:56,000 --> 00:24:00,000
і я вже не вистачає місця для іншого цілого або іншого персонажа.

431
00:24:00,000 --> 00:24:03,000
Що робити, якщо ми начебто превентивно говорите, чому б нам не відпочити

432
00:24:03,000 --> 00:24:07,000
це вимога, що всі ці ділянки пам'яті повинні бути суміжними спина до спини,

433
00:24:07,000 --> 00:24:10,000
і чому цього не зробити, коли мені потрібно Int або символ,

434
00:24:10,000 --> 00:24:12,000
просто дайте мені простір для одного з них?

435
00:24:12,000 --> 00:24:14,000
І коли мені потрібно ще, дай мені іншого простору,

436
00:24:14,000 --> 00:24:16,000
і коли мені потрібно ще, дай мені іншого простору.

437
00:24:16,000 --> 00:24:19,000
Перевага який в даний час є те, що, якщо хтось ще

438
00:24:19,000 --> 00:24:21,000
займає пам'ять тут, немає нічого складного.

439
00:24:21,000 --> 00:24:25,000
Я візьму цей додатковий блок пам'яті тут і то це одне.

440
00:24:25,000 --> 00:24:28,000
>> Тепер, тільки заковика в тому, що це майже відчуває, як у мене

441
00:24:28,000 --> 00:24:30,000
цілий букет різних змінних.

442
00:24:30,000 --> 00:24:33,000
Це відчуває себе п'ять різних змінних потенційно.

443
00:24:33,000 --> 00:24:36,000
Але що, якщо ми вкрасти ідею з рядків

444
00:24:36,000 --> 00:24:41,000
яким ми якось пов'язати ці речі разом концептуально, а що, якщо я це зробив?

445
00:24:41,000 --> 00:24:44,000
Це мій дуже погано звертається стрілки.

446
00:24:44,000 --> 00:24:46,000
Але припустимо, що кожна з цих ділянок пам'яті

447
00:24:46,000 --> 00:24:52,000
вказав на одного, і цей хлопець, у якого немає брата, щоб його права,

448
00:24:52,000 --> 00:24:54,000
не має такого стрільця.

449
00:24:54,000 --> 00:24:56,000
Це насправді те, що називається пов'язаного списку.

450
00:24:56,000 --> 00:25:00,000
Це нова структура даних, яка дозволяє виділити шматок пам'яті,

451
00:25:00,000 --> 00:25:03,000
потім інша, потім ще, потім ще, в будь-який час ми хочемо

452
00:25:03,000 --> 00:25:07,000
під час виконання програми, і ми пам'ятаємо, що всі вони так чи інакше пов'язаних

453
00:25:07,000 --> 00:25:11,000
буквально ланцюжок їх разом, і ми зробили це наочно тут зі стрілкою.

454
00:25:11,000 --> 00:25:15,000
Але в коді, яким буде механізм, через який ви могли б якимось чином підключити,

455
00:25:15,000 --> 00:25:20,000
майже як Scratch, один шматок на інший шматок?

456
00:25:20,000 --> 00:25:22,000
Ми могли б використовувати покажчик, чи не так?

457
00:25:22,000 --> 00:25:25,000
Тому що насправді стрілка, яка походить з верхнього лівого квадрата,

458
00:25:25,000 --> 00:25:31,000
цей хлопець тут, щоб цю, може міститися всередині цього квадрата

459
00:25:31,000 --> 00:25:34,000
Не тільки деякі цілі, а не тільки деяких символів, але що, якщо я насправді виділив

460
00:25:34,000 --> 00:25:37,000
трохи додаткового простору, так що тепер,

461
00:25:37,000 --> 00:25:41,000
Кожен з моїх ділянок пам'яті, навіть якщо це коштуватиме мені,

462
00:25:41,000 --> 00:25:45,000
зараз виглядає трохи більш прямокутної, де одна з ділянок пам'яті

463
00:25:45,000 --> 00:25:47,000
Використовується для номер, як номер 1,

464
00:25:47,000 --> 00:25:50,000
а потім, якщо цей хлопець зберігає номер 2,

465
00:25:50,000 --> 00:25:52,000
ця інша частина пам'яті використовується для стрільця,

466
00:25:52,000 --> 00:25:54,000
або більш конкретно, покажчик.

467
00:25:54,000 --> 00:25:59,000
І нехай я зберігаю № 3 тут в той час як я використовую це, щоб вказати на того хлопця,

468
00:25:59,000 --> 00:26:02,000
і тепер цей хлопець, припустимо, я хочу тільки три таких ділянок пам'яті.

469
00:26:02,000 --> 00:26:05,000
Я намалюю лінію через які, із зазначенням нульовий.

470
00:26:05,000 --> 00:26:07,000
Існує ніякого додаткового характеру.

471
00:26:07,000 --> 00:26:10,000
>> Дійсно, це, як ми можемо йти про реалізацію

472
00:26:10,000 --> 00:26:12,000
те, що називається зв'язний список.

473
00:26:12,000 --> 00:26:18,000
Зв'язаний список нову структуру даних, і це сходинка до

474
00:26:18,000 --> 00:26:21,000
багато любителів структур даних, які починають вирішувати проблеми

475
00:26:21,000 --> 00:26:23,000
уздовж лінії Facebook тип проблеми і Google тип проблеми

476
00:26:23,000 --> 00:26:26,000
де у вас є величезні набори даних, і він більше не ріже

477
00:26:26,000 --> 00:26:29,000
зберігати всі безперервно і використовувати щось подібне лінійний пошук

478
00:26:29,000 --> 00:26:31,000
або навіть щось подібне до бінарного пошуку.

479
00:26:31,000 --> 00:26:33,000
Ви хочете ще краще працює рази.

480
00:26:33,000 --> 00:26:37,000
У самому справі, одна з Святої Grails ми поговоримо пізніше на цьому тижні або в наступному

481
00:26:37,000 --> 00:26:41,000
алгоритм, час виконання якої постійно.

482
00:26:41,000 --> 00:26:44,000
Іншими словами, вона завжди приймає стільки ж часу, незалежно від того,

483
00:26:44,000 --> 00:26:47,000
наскільки великий вхід, і дійсно було б переконливим,

484
00:26:47,000 --> 00:26:49,000
навіть більше, ніж те, логарифмічна.

485
00:26:49,000 --> 00:26:51,000
Що це на екрані тут?

486
00:26:51,000 --> 00:26:55,000
Кожен з прямокутників саме те, що я тільки що намалювали від руки.

487
00:26:55,000 --> 00:26:59,000
Але справа все шляху зліва спеціальної змінної.

488
00:26:59,000 --> 00:27:02,000
Це збирається бути одним покажчиком, тому що той Гоча

489
00:27:02,000 --> 00:27:04,000
з пов'язаного списку, так як ці речі називаються,

490
00:27:04,000 --> 00:27:09,000
є те, що у вас є, щоб повісити на один кінець пов'язаного списку.

491
00:27:09,000 --> 00:27:13,000
>> Так само, як з рядком, ви повинні знати адресу першого символу.

492
00:27:13,000 --> 00:27:15,000
Те ж угода для пов'язаних списків.

493
00:27:15,000 --> 00:27:19,000
Ви повинні знати адресу першого блоку пам'яті

494
00:27:19,000 --> 00:27:25,000
тому що звідти можна добратися до будь-якого іншого.

495
00:27:25,000 --> 00:27:27,000
Даунсайд.

496
00:27:27,000 --> 00:27:30,000
Яку ціну ми платимо за цю універсальність мають динамічне

497
00:27:30,000 --> 00:27:34,000
значну структуру даних, що якщо ми коли-небудь знадобиться більше пам'яті, штраф,

498
00:27:34,000 --> 00:27:37,000
просто виділити ще один шматок і намалюйте стрілки від

499
00:27:37,000 --> 00:27:39,000
старого до нового хвості списку?

500
00:27:39,000 --> 00:27:41,000
Так.

501
00:27:41,000 --> 00:27:43,000
[Студент] Це займає приблизно вдвічі більше простору.

502
00:27:43,000 --> 00:27:45,000
Вона займає вдвічі більше місця, так що це виразно недолік, і ми бачили це

503
00:27:45,000 --> 00:27:48,000
Компроміс, перш ніж між часом і простором і гнучкість

504
00:27:48,000 --> 00:27:51,000
де в даний час, нам не потрібно 32 біт для кожного з цих чисел.

505
00:27:51,000 --> 00:27:57,000
Нам дійсно потрібно 64, 32 числа і 32 для покажчика.

506
00:27:57,000 --> 00:27:59,000
Але почекайте, у мене є 2 гігабайти оперативної пам'яті.

507
00:27:59,000 --> 00:28:02,000
Додавання ще 32 біта тут і тут не здається, що великі угоди.

508
00:28:02,000 --> 00:28:05,000
Але для великих наборів даних, це безперечно додає буквально в два рази більше.

509
00:28:05,000 --> 00:28:09,000
Що ще одним недоліком зараз, або те, що функції ми здаватися,

510
00:28:09,000 --> 00:28:12,000
якщо ми уявимо списки речей з пов'язаного списку, а не масив?

511
00:28:12,000 --> 00:28:14,000
[Студент] Ви не можете пройти у зворотному напрямку.

512
00:28:14,000 --> 00:28:16,000
Ви не можете пройти у зворотному напрямку, так що ви вид різьбових якщо ви йдете

513
00:28:16,000 --> 00:28:19,000
зліва на право використання циклу або час циклу

514
00:28:19,000 --> 00:28:21,000
а потім розумієш: «О, я хочу повернутися в початок списку".

515
00:28:21,000 --> 00:28:26,000
Ви не можете, тому що ці покажчики йти тільки зліва направо, як стрілки показують.

516
00:28:26,000 --> 00:28:29,000
>> Тепер, ви могли згадати початок списку з іншої змінної,

517
00:28:29,000 --> 00:28:31,000
але це складність мати на увазі.

518
00:28:31,000 --> 00:28:35,000
Масивів, незалежно від того, як далеко ви підете, ви завжди можете зробити мінус, мінус, мінус, мінус

519
00:28:35,000 --> 00:28:37,000
і повернутися, звідки ви прийшли.

520
00:28:37,000 --> 00:28:40,000
Що ще одним недоліком тут? Так.

521
00:28:40,000 --> 00:28:43,000
[Нерозбірливо запитання студента]

522
00:28:43,000 --> 00:28:47,000
Можна, таким чином, ви дійсно тільки що запропонував структуру даних, звану двічі зв'язаний список,

523
00:28:47,000 --> 00:28:50,000
І дійсно, можна додати ще один покажчик на кожен з цих прямокутників

524
00:28:50,000 --> 00:28:53,000
, Який іде в іншому напрямку, потенціал зростання яких

525
00:28:53,000 --> 00:28:55,000
Тепер ви можете пройти туди і назад,

526
00:28:55,000 --> 00:28:59,000
Недоліком який в даний час ви використовуєте в три рази більше пам'яті, ніж ми звикли

527
00:28:59,000 --> 00:29:04,000
а також ускладнення з точки зору коду, ви повинні написати, щоб отримати це право.

528
00:29:04,000 --> 00:29:08,000
Але все це, можливо, дуже розумні компроміси, якщо звернення є більш важливим.

529
00:29:08,000 --> 00:29:10,000
Так.

530
00:29:10,000 --> 00:29:12,000
[Студент] Ви також не можете мати 2D пов'язаного списку.

531
00:29:12,000 --> 00:29:16,000
Добре, ви не можете дійсно є 2D зв'язаний список.

532
00:29:16,000 --> 00:29:18,000
Ви могли б. Це не так просто, як масив.

533
00:29:18,000 --> 00:29:21,000
Як і масив, ви відкриваюча дужка, закрита дужка, відкриваюча дужка, закрита дужка,

534
00:29:21,000 --> 00:29:23,000
, І ви отримаєте деякий 2-мірну структуру.

535
00:29:23,000 --> 00:29:26,000
Ви можете реалізувати 2-мірних зв'язаний список

536
00:29:26,000 --> 00:29:29,000
якщо ви робите доповнення, як ви запропонували, 1/3 покажчика на кожну з цих речей,

537
00:29:29,000 --> 00:29:34,000
і якщо ви думаєте про іншому списку приходить на вас 3D стиль

538
00:29:34,000 --> 00:29:40,000
з екрану всім нам, що це просто ще один ланцюжок якийсь.

539
00:29:40,000 --> 00:29:45,000
Ми могли б це зробити, але це не так просто, як друкувати відкритої дужки, квадратні дужки. Так.

540
00:29:45,000 --> 00:29:48,000
[Нерозбірливо запитання студента]

541
00:29:48,000 --> 00:29:50,000
Добре, так що це реальний футболіст.

542
00:29:50,000 --> 00:29:54,000
>> Ці алгоритми, які ми сумували за, як про, бінарний пошук,

543
00:29:54,000 --> 00:29:57,000
Ви можете шукати масив чисел на дошці

544
00:29:57,000 --> 00:30:01,000
або телефонну книгу так набагато швидше, якщо ви використовуєте розділяй і володарюй

545
00:30:01,000 --> 00:30:05,000
і алгоритм двійкового пошуку, але бінарний пошук необхідних два припущення.

546
00:30:05,000 --> 00:30:09,000
Один з них, що дані були відсортовані.

547
00:30:09,000 --> 00:30:11,000
Тепер ми можемо по-видимому тримати цю сортуються,

548
00:30:11,000 --> 00:30:14,000
так що, можливо, це не має значення, але бінарний пошук Передбачається також,

549
00:30:14,000 --> 00:30:18,000
що ви мали випадковий доступ до списку чисел,

550
00:30:18,000 --> 00:30:21,000
і масив дозволяє мати довільний доступ, і випадкового доступу,

551
00:30:21,000 --> 00:30:24,000
Я маю на увазі, якщо ви даного масиву, скільки часу це займе у вас

552
00:30:24,000 --> 00:30:26,000
щоб дістатися до кронштейна 0?

553
00:30:26,000 --> 00:30:29,000
Одна операція, ви просто використовуєте [0], і ви тут же.

554
00:30:29,000 --> 00:30:33,000
Скільки кроків потрібно для того, щоб дістатися до розташування 10?

555
00:30:33,000 --> 00:30:36,000
Один крок, ви просто йдете в [10], і ви там.

556
00:30:36,000 --> 00:30:40,000
На відміну від цього, як ви отримуєте по 10 число у зв'язаному списку?

557
00:30:40,000 --> 00:30:42,000
Ви повинні почати з самого початку, тому що ви тільки пам'ятаючи

558
00:30:42,000 --> 00:30:45,000
початок пов'язаного списку, як і рядок в даний час пам'ятала

559
00:30:45,000 --> 00:30:48,000
за адресою її перший символ, і виявили, що десята Int

560
00:30:48,000 --> 00:30:53,000
або що десята символів в рядку, ви повинні шукати всю цю чортову річ.

561
00:30:53,000 --> 00:30:55,000
>> Знову ж таки, ми не вирішення всіх наших проблем.

562
00:30:55,000 --> 00:31:00,000
Ми представляємо нові, але це залежить від того, що ви намагаєтеся проектувати для.

563
00:31:00,000 --> 00:31:04,000
У плані реалізації цього, ми можемо запозичувати ідеї з цього студента структури.

564
00:31:04,000 --> 00:31:07,000
Синтаксис дуже схожий, тільки тепер, ідея трохи більш абстрактних

565
00:31:07,000 --> 00:31:09,000
ніж удома, назва і ID.

566
00:31:09,000 --> 00:31:13,000
Але я пропоную, щоб ми могли мати структуру даних в C

567
00:31:13,000 --> 00:31:17,000
що називається вузлом, так як останнє слово на слайд пропозиції,

568
00:31:17,000 --> 00:31:21,000
Усередині вузла і вузол просто загальний контейнер в комп'ютерній науці.

569
00:31:21,000 --> 00:31:25,000
Це звичайно зображується у вигляді кола або квадрата або прямокутника, як ми зробили.

570
00:31:25,000 --> 00:31:27,000
І в цій структурі даних, у нас є ціле число, N,

571
00:31:27,000 --> 00:31:29,000
так що це число я хочу зберегти.

572
00:31:29,000 --> 00:31:36,000
Але що це друга лінія, структура вузла * далі?

573
00:31:36,000 --> 00:31:40,000
Чому це правильно, або яку роль ця річ гри,

574
00:31:40,000 --> 00:31:42,000
хоча це трохи загадкове на перший погляд?

575
00:31:42,000 --> 00:31:44,000
Так.

576
00:31:44,000 --> 00:31:46,000
[Нерозбірливо відповідь студента]

577
00:31:46,000 --> 00:31:50,000
Саме, тому * роду трофеї, що це покажчик якийсь.

578
00:31:50,000 --> 00:31:53,000
Назва цього покажчика як завгодно інший,

579
00:31:53,000 --> 00:32:00,000
але ми могли б назвав це все, що ми хочемо, але те, що робить цей покажчик вказує на?

580
00:32:00,000 --> 00:32:03,000
[Студент] Інший вузол. >> Точно, він вказує на інший такий вузол.

581
00:32:03,000 --> 00:32:05,000
>> Тепер, це свого роду цікавість C.

582
00:32:05,000 --> 00:32:09,000
Нагадаємо, що C читається компілятором зверху вниз, зліва направо,

583
00:32:09,000 --> 00:32:13,000
що означає, якщо-це трохи відрізняється від того, що ми робили з учнем.

584
00:32:13,000 --> 00:32:16,000
Коли ми визначили студент, ми насправді не ставив слово там.

585
00:32:16,000 --> 00:32:18,000
Він просто сказав ЬурейеЕ.

586
00:32:18,000 --> 00:32:20,000
Тоді у нас була Int Ідентифікатор, ім'я рядки, рядки будинок,

587
00:32:20,000 --> 00:32:23,000
, А потім студентом в нижній частині структури.

588
00:32:23,000 --> 00:32:26,000
Ця заява трохи відрізняється, тому що,

589
00:32:26,000 --> 00:32:28,000
знову ж таки, компілятор це трохи безглуздо.

590
00:32:28,000 --> 00:32:30,000
Це тільки збирається читати зверху вниз,

591
00:32:30,000 --> 00:32:33,000
Таким чином, якщо воно досягає 2-ї лінії тут

592
00:32:33,000 --> 00:32:37,000
де поруч оголошений, і він бачить, ой, ось змінна наступному.

593
00:32:37,000 --> 00:32:39,000
Це покажчик на структуру вузла.

594
00:32:39,000 --> 00:32:42,000
Компілятор буде розуміти, що це структура вузла?

595
00:32:42,000 --> 00:32:44,000
Я ніколи не чув про цю річ раніше,

596
00:32:44,000 --> 00:32:47,000
тому що слово вузол не могли б з'явитися

597
00:32:47,000 --> 00:32:49,000
до дна, так що ця надмірність.

598
00:32:49,000 --> 00:32:53,000
Ви повинні сказати структури вузлів тут, які потім можна скоротити надалі

599
00:32:53,000 --> 00:32:56,000
Завдяки ЬурейеЕ тут, але це тому, що

600
00:32:56,000 --> 00:33:02,000
Ми посиланням на саму структуру всередині структури.

601
00:33:02,000 --> 00:33:05,000
Це той, Гоча там.

602
00:33:05,000 --> 00:33:07,000
>> Деякі цікаві проблеми будуть виникати.

603
00:33:07,000 --> 00:33:09,000
У нас є список номерів. Як ми вставляємо в нього?

604
00:33:09,000 --> 00:33:11,000
Як ми можемо шукати його? Як ми можемо видалити з нього?

605
00:33:11,000 --> 00:33:13,000
Особливо зараз, коли ми повинні управляти всіма цими покажчиками.

606
00:33:13,000 --> 00:33:15,000
Ви думали, покажчики були свого роду галюциногенний

607
00:33:15,000 --> 00:33:17,000
коли ви були одним з них просто намагаюся читати Int до нього.

608
00:33:17,000 --> 00:33:20,000
Тепер ми повинні маніпулювати вартістю всього списку.

609
00:33:20,000 --> 00:33:22,000
Чому б нам не взяти нашу 5-хвилинну перерву тут, а потім ми принесемо

610
00:33:22,000 --> 00:33:34,000
деякі люди на сцену, щоб зробити саме це.

611
00:33:34,000 --> 00:33:36,000
>> З набагато більше задоволення, коли вона розігрується.

612
00:33:36,000 --> 00:33:39,000
Хто б буквально хотів бути першим?

613
00:33:39,000 --> 00:33:41,000
Гаразд, давай вгору. Ви знаходитесь в першу чергу.

614
00:33:41,000 --> 00:33:44,000
Хто хотів би бути 9? Гаразд, 9.

615
00:33:44,000 --> 00:33:46,000
Як щодо 9? 17?

616
00:33:46,000 --> 00:33:51,000
Трохи кліка тут. 22 і 26 в цьому ряду.

617
00:33:51,000 --> 00:33:53,000
І потім, як про когось там, на яку посилаються.

618
00:33:53,000 --> 00:33:57,000
Ви 34. Ладно, 34, давай вгору.

619
00:33:57,000 --> 00:33:59,000
По-перше, це там. Гаразд, всі чотири з вас, хлопці.

620
00:33:59,000 --> 00:34:01,000
А хто ж ми говоримо на 9?

621
00:34:01,000 --> 00:34:04,000
Хто наш 9?

622
00:34:04,000 --> 00:34:07,000
Хто дійсно хоче бути 9? Гаразд, давай, бути 9.

623
00:34:07,000 --> 00:34:10,000
Тут ми йдемо.

624
00:34:10,000 --> 00:34:13,000
34, ми зустрінемося з вами там.

625
00:34:13,000 --> 00:34:17,000
Перша частина являє собою зробити собі виглядати.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, добре.

627
00:34:21,000 --> 00:34:25,000
Якщо ви можете стояти осторонь, тому що ми збираємося Malloc вас в даний момент.

628
00:34:25,000 --> 00:34:29,000
>> Добре, добре.

629
00:34:29,000 --> 00:34:32,000
Добре, відмінно, так що давайте задати пару питань тут.

630
00:34:32,000 --> 00:34:34,000
А насправді, як тебе звати? >> Аніта.

631
00:34:34,000 --> 00:34:37,000
Аніта, ладно, йди сюди.

632
00:34:37,000 --> 00:34:41,000
Аніта збирається допомогти нам начебто вирішити одне досить просте питання в першому,

633
00:34:41,000 --> 00:34:44,000
який, як ви вважаєте, чи є значення знаходиться в списку?

634
00:34:44,000 --> 00:34:48,000
Тепер зверніть увагу, що, по-перше, представлені тут Лукас,

635
00:34:48,000 --> 00:34:52,000
трохи відрізняється, і тому його папірець свідомо боком

636
00:34:52,000 --> 00:34:55,000
тому що це не так високий і не займає стільки бітів,

637
00:34:55,000 --> 00:34:58,000
хоча технічно він має такий же розмір паперу, просто повертається.

638
00:34:58,000 --> 00:35:01,000
Але він трохи відрізняється тим, що він всього лише 32 біт для покажчика,

639
00:35:01,000 --> 00:35:05,000
і всі ці хлопці є 64-бітними, половина з яких це число, половина з яких є покажчиком.

640
00:35:05,000 --> 00:35:08,000
Але покажчик не зображено, так що якщо ви, хлопці, могли б дещо незграбно

641
00:35:08,000 --> 00:35:12,000
використовувати ліву руку, щоб вказати на людину поруч з вами.

642
00:35:12,000 --> 00:35:14,000
І ти номер 34. Як тебе звуть?

643
00:35:14,000 --> 00:35:16,000
Арі.

644
00:35:16,000 --> 00:35:19,000
Арі, так що насправді, тримати папір в праву руку, а ліва рука йде вниз.

645
00:35:19,000 --> 00:35:21,000
Ви уявляєте нульовою зліва.

646
00:35:21,000 --> 00:35:24,000
>> Тепер наша людська картина дуже послідовні.

647
00:35:24,000 --> 00:35:26,000
Насправді це як покажчики працюють.

648
00:35:26,000 --> 00:35:29,000
І якщо ви спробуєте може трохи Таким чином, так що я не на вашому шляху.

649
00:35:29,000 --> 00:35:34,000
Аніта тут, знайти мені номер 22,

650
00:35:34,000 --> 00:35:40,000
але припустити, обмеження не люди, піднявши папірці,

651
00:35:40,000 --> 00:35:43,000
Але це список, і у вас є тільки Лукас з самого початку

652
00:35:43,000 --> 00:35:46,000
тому що він буквально перший покажчик.

653
00:35:46,000 --> 00:35:51,000
Припустимо, що ви самі покажчик, так що ви теж маєте можливість вказати на щось.

654
00:35:51,000 --> 00:35:56,000
Чому б вам не почати, вказуючи на те, що Лукас вказує на?

655
00:35:56,000 --> 00:35:58,000
Добре, і дозвольте мені взяти на це тут.

656
00:35:58,000 --> 00:36:04,000
Тільки заради обговорення, дозвольте мені підтягти порожню сторінку тут.

657
00:36:04,000 --> 00:36:06,000
Як пишеться ваше ім'я? >> Аніта.

658
00:36:06,000 --> 00:36:08,000
Гаразд, Аніта.

659
00:36:08,000 --> 00:36:18,000
Припустимо, вузол * Аніта = Лукас.

660
00:36:18,000 --> 00:36:22,000
Ну, ми не повинні називати вас Лукас. Ми повинні зателефонувати вам в першу чергу.

661
00:36:22,000 --> 00:36:25,000
Чому це насправді відповідає дійсності тут?

662
00:36:25,000 --> 00:36:27,000
Один, перший вже існує.

663
00:36:27,000 --> 00:36:30,000
Перше було виділено імовірно десь тут.

664
00:36:30,000 --> 00:36:35,000
Node * По-перше, і це було виділено списку якось.

665
00:36:35,000 --> 00:36:37,000
Я не знаю, як це сталося. Це сталося до початку класу.

666
00:36:37,000 --> 00:36:40,000
Це пов'язано список людей була створена.

667
00:36:40,000 --> 00:36:44,000
А тепер у цей момент в історії-це все відбувається на Facebook видимо пізніше

668
00:36:44,000 --> 00:36:49,000
на даний момент у цій історії, Аніта була ініціалізований рівній першої,

669
00:36:49,000 --> 00:36:51,000
але це не означає, що Аніта вказує на Лукаса.

670
00:36:51,000 --> 00:36:53,000
Швидше за все, вона вказує на те, що він вказує на

671
00:36:53,000 --> 00:36:57,000
тому що ту ж адресу, що знаходиться всередині 32 біт Лукас - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
Тепер і всередині 32 біт Аніта - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Тепер знайдіть 22. Як би ви про це?

674
00:37:05,000 --> 00:37:07,000
Що це? >> Точка завгодно.

675
00:37:07,000 --> 00:37:11,000
Навівши курсор на будь-який інший, так що йти вперед і діяти його як найкраще, що ви можете тут.

676
00:37:11,000 --> 00:37:15,000
Добре, добре, і тепер ви, вказуючи на те, що, як тебе звати з 22?

677
00:37:15,000 --> 00:37:18,000
Рамон. >> Рамон, так Рамон тримається 22.

678
00:37:18,000 --> 00:37:20,000
Ви вже зробили чек.

679
00:37:20,000 --> 00:37:24,000
Хіба Рамон == 22, і якщо так, наприклад, ми можемо повернутися вірно.

680
00:37:24,000 --> 00:37:26,000
Дозвольте мені, в той час як ці хлопці стоять тут трохи незграбно-

681
00:37:26,000 --> 00:37:32,000
Дозвольте мені зробити щось швидко, як BOOL знайти.

682
00:37:32,000 --> 00:37:37,000
Я збираюся йти вперед і говорити (список вузлів *, Int N).

683
00:37:37,000 --> 00:37:39,000
Я скоро повернуся з вами, хлопці. Мені просто потрібно написати код.

684
00:37:39,000 --> 00:37:45,000
А тепер я збираюся йти вперед і робити це, вузол * Аніта = списку.

685
00:37:45,000 --> 00:37:51,000
І я буду йти вперед і говорити в той час як (Аніта! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> Метафора тут стає трохи розтягнуто, але в той час (Аніта! = NULL), що я хочу робити?

687
00:37:57,000 --> 00:38:03,000
Мені потрібно якимось чином посилання

688
00:38:03,000 --> 00:38:05,000
ціле число, Аніта вказує на.

689
00:38:05,000 --> 00:38:08,000
У минулому, коли ми мали структур, які вузла,

690
00:38:08,000 --> 00:38:11,000
Ми використовували позначення точки, і ми хотіли б сказати щось на кшталт:

691
00:38:11,000 --> 00:38:15,000
anita.n, але проблема в тому, що Аніта не є структурою як такої.

692
00:38:15,000 --> 00:38:17,000
Що вона?

693
00:38:17,000 --> 00:38:21,000
Вона покажчик, так що дійсно, якщо ми хочемо використати цю точкову нотацію-

694
00:38:21,000 --> 00:38:23,000
і це буде виглядати нарочито трохи загадково-

695
00:38:23,000 --> 00:38:28,000
Ми повинні зробити щось подібне переходу на лівій руці все, що Аніта вказує на

696
00:38:28,000 --> 00:38:31,000
, А потім отримати полю називається п.

697
00:38:31,000 --> 00:38:35,000
Аніта є покажчиком, але те, що * Аніта?

698
00:38:35,000 --> 00:38:38,000
Що ви знаходите, коли ви йдете до того, що Аніта вказує на?

699
00:38:38,000 --> 00:38:42,000
Структури, вузлів і вузлів, нагадаємо, має поле з назвою п

700
00:38:42,000 --> 00:38:47,000
тому що вона, нагадаємо, ці 2 поля, в наступному і п,

701
00:38:47,000 --> 00:38:50,000
, Який ми бачили кілька хвилин тому прямо тут.

702
00:38:50,000 --> 00:38:53,000
>> Щоб насправді імітувати це в коді,

703
00:38:53,000 --> 00:39:02,000
ми могли б зробити це і говорять, що якщо ((* Anita). == п п), п, що я шукав.

704
00:39:02,000 --> 00:39:04,000
Зверніть увагу, що функція була передана в кількості я дбаю.

705
00:39:04,000 --> 00:39:10,000
Тоді я можу йти вперед і робити щось подібне повернення правда.

706
00:39:10,000 --> 00:39:12,000
В іншому випадку, якщо це не так, що я хочу робити?

707
00:39:12,000 --> 00:39:19,000
Як перевести в код, що Аніта зробила це інтуїтивно, йдучи за списком?

708
00:39:19,000 --> 00:39:26,000
Що я повинен робити тут, щоб імітувати Аніта цього кроку вліво, що крок вліво?

709
00:39:26,000 --> 00:39:28,000
[Нерозбірливо відповідь студента] >> Що це таке?

710
00:39:28,000 --> 00:39:30,000
[Нерозбірливо відповідь студента]

711
00:39:30,000 --> 00:39:34,000
Добре, не погана ідея, але в минулому, коли ми зробили це, ми зробили Аніта + +

712
00:39:34,000 --> 00:39:37,000
тому що це було додати число від 1 до Аніти,

713
00:39:37,000 --> 00:39:40,000
які, як правило, вказують на наступний людина, як Рамон,

714
00:39:40,000 --> 00:39:44,000
або особою, поряд з ним або поруч із ним особою вниз лінію.

715
00:39:44,000 --> 00:39:49,000
Але це не зовсім добре тут, тому що це річ виглядати в пам'яті?

716
00:39:49,000 --> 00:39:54,000
Не те, щоб. Ми повинні відключити це.

717
00:39:54,000 --> 00:40:00,000
Схоже, що це в пам'яті, і, хоча я намалював 1 і 2 і 3 близькі один до одного,

718
00:40:00,000 --> 00:40:03,000
якщо ми дійсно імітації цього, ви, хлопці, в той же час вказуючи на ті ж люди,

719
00:40:03,000 --> 00:40:07,000
може, деякі з вас беруть випадкові крок назад, деякі з вас випадковий крок вперед?

720
00:40:07,000 --> 00:40:10,000
>> Ця чехарда і раніше пов'язаного списку,

721
00:40:10,000 --> 00:40:13,000
але ці хлопці можуть бути де завгодно в пам'яті,

722
00:40:13,000 --> 00:40:15,000
так що Аніта + + не буде працювати, чому?

723
00:40:15,000 --> 00:40:19,000
Що на місці Аніта + +?

724
00:40:19,000 --> 00:40:21,000
Хто його знає.

725
00:40:21,000 --> 00:40:24,000
Це деякі інші значення, просто так трапляється бути вставлений

726
00:40:24,000 --> 00:40:28,000
серед всіх цих вузлів випадково, тому що ми не використовуємо масив.

727
00:40:28,000 --> 00:40:30,000
Ми виділили кожному з цих вузлів окремо.

728
00:40:30,000 --> 00:40:32,000
Добре, якщо ви, хлопці, можете очистити себе назад.

729
00:40:32,000 --> 00:40:37,000
Дозвольте мені запропонувати, що замість Аніти + +, ми замість цього отримує Аніта-

730
00:40:37,000 --> 00:40:42,000
Ну, чому б нам не піти на будь Аніта вказує на те і робимо. Наступний?

731
00:40:42,000 --> 00:40:45,000
Іншими словами, ми йдемо до Рамон, який тримає номер 22,

732
00:40:45,000 --> 00:40:51,000
і потім. наступна неначе Аніта буде копіювати його лівий покажчик руку.

733
00:40:51,000 --> 00:40:54,000
Але вона не хотіла йти далі, ніж Ramon тому що ми знайшли 22.

734
00:40:54,000 --> 00:40:56,000
Але це була б ідея. Тепер, це бог-жахливий безлад.

735
00:40:56,000 --> 00:40:59,000
Чесно кажучи, ніхто ніколи не буде пам'ятати цей синтаксис, і тому, на щастя,

736
00:40:59,000 --> 00:41:04,000
це насправді небагато навмисному-ой, ви насправді не розумієте, що я написав.

737
00:41:04,000 --> 00:41:08,000
Це було б більш переконливим, якби могли. Voila!

738
00:41:08,000 --> 00:41:10,000
>> За лаштунками, я був вирішити проблему таким чином.

739
00:41:10,000 --> 00:41:14,000
Аніта, піти на цей крок вліво,

740
00:41:14,000 --> 00:41:18,000
По-перше, ми дійсно йдуть на адресу, яку Аніта вказує на

741
00:41:18,000 --> 00:41:23,000
і де вона знайде не тільки росіян, які ми тільки що перевірив для порівняння,

742
00:41:23,000 --> 00:41:25,000
але ви також знайдете наступну - у цьому випадку,

743
00:41:25,000 --> 00:41:28,000
Лівою рукою Рамона, вказуючи на наступний вузол в списку.

744
00:41:28,000 --> 00:41:32,000
Але це бог-жахливий безлад про які я говорив раніше,

745
00:41:32,000 --> 00:41:34,000
але виявляється, C дозволяє нам спростити це.

746
00:41:34,000 --> 00:41:40,000
Замість листа (* Anita), ми можемо замість цього просто написати Аніта-> п,

747
00:41:40,000 --> 00:41:45,000
і це одне і те ж функціонально, але це набагато більш зрозумілим,

748
00:41:45,000 --> 00:41:48,000
і це набагато більше узгоджується з картиною, яку ми залучали

749
00:41:48,000 --> 00:41:50,000
Весь цей час за допомогою стрілок.

750
00:41:50,000 --> 00:41:57,000
>> Нарешті, що ми повинні зробити в кінці цій програмі?

751
00:41:57,000 --> 00:42:00,000
Там в одному рядку коду залишилося.

752
00:42:00,000 --> 00:42:02,000
Повернення що?

753
00:42:02,000 --> 00:42:05,000
Брехня, бо якщо ми отримаємо через весь час циклу

754
00:42:05,000 --> 00:42:10,000
і Аніта є, по суті, нульовий, значить, вона пройшла шлях до кінця списку

755
00:42:10,000 --> 00:42:12,000
де вона, вказуючи на те, що, тебе звуть?

756
00:42:12,000 --> 00:42:15,000
Ліва Арі. >> Арі сторони, яка є недійсним.

757
00:42:15,000 --> 00:42:18,000
Аніта зараз нульовий, і я розумію, ви просто стоїте тут ніяково в підвішеному стані

758
00:42:18,000 --> 00:42:21,000
тому що я збираюся відправитися в монолозі тут,

759
00:42:21,000 --> 00:42:23,000
але ми будемо залучати вас знову через хвилину.

760
00:42:23,000 --> 00:42:27,000
Аніта є недійсним в той момент в історії, так що в той час як цикл завершується,

761
00:42:27,000 --> 00:42:30,000
і ми повинні повернутися помилковим, тому що якщо вона отримала всю дорогу до нульового покажчика Арі

762
00:42:30,000 --> 00:42:34,000
тоді не було числа, що вона шукала в списку.

763
00:42:34,000 --> 00:42:39,000
Ми можемо очистити це занадто, але це досить хороша реалізація, то

764
00:42:39,000 --> 00:42:43,000
функції обходу, знайти функції для пов'язаного списку.

765
00:42:43,000 --> 00:42:48,000
Він як і раніше лінійний пошук, але це не так просто, як + + покажчик

766
00:42:48,000 --> 00:42:52,000
або + + змінна я, тому що тепер ми не можемо вгадати

767
00:42:52,000 --> 00:42:54,000
де кожен з цих вузлів в пам'яті.

768
00:42:54,000 --> 00:42:57,000
Ми повинні буквально слідувати по слідах сухарями або, більш конкретно,

769
00:42:57,000 --> 00:43:00,000
покажчиків, щоб добратися від одного вузла до іншого.

770
00:43:00,000 --> 00:43:02,000
>> Тепер давайте спробуємо ще один. Аніта, ви хочете, щоб повернутися сюди?

771
00:43:02,000 --> 00:43:06,000
Чому б нам не піти далі і виділити одну людину з аудиторії?

772
00:43:06,000 --> 00:43:08,000
Malloc-як тебе звати? >> Ребекка.

773
00:43:08,000 --> 00:43:10,000
Ребекка. Ребекка була malloced від аудиторії,

774
00:43:10,000 --> 00:43:13,000
і тепер вона зберігається номер 55.

775
00:43:13,000 --> 00:43:17,000
І мета під рукою зараз для Аніти, щоб вставити

776
00:43:17,000 --> 00:43:22,000
Ребекка в зв'язаний список тут у відповідному місці.

777
00:43:22,000 --> 00:43:24,000
Давай сюди на хвилинку.

778
00:43:24,000 --> 00:43:28,000
Я зробив щось на зразок цього.

779
00:43:28,000 --> 00:43:32,000
Я зробив вузол *. А що тебе звуть?

780
00:43:32,000 --> 00:43:34,000
Ребекка. >> Ребекка, все в порядку.

781
00:43:34,000 --> 00:43:41,000
Ребекка отримує Танос (SizeOf (вузла)).

782
00:43:41,000 --> 00:43:44,000
Так само, як ми виділили такі речі, як студенти і ще багато чого в минулому,

783
00:43:44,000 --> 00:43:46,000
Ми потребуємо в розмірі вузла, так що тепер Ребекка

784
00:43:46,000 --> 00:43:49,000
вказує на те, що?

785
00:43:49,000 --> 00:43:52,000
Ребекка має два поля всередині неї, одним з яких є 55.

786
00:43:52,000 --> 00:43:55,000
Давайте робити те, що, Ребекка-> = 55.

787
00:43:55,000 --> 00:44:00,000
Але тоді Ребеку-> наступна повинна бути, як зараз, її рука це свого роду хто знає?

788
00:44:00,000 --> 00:44:03,000
Це вказує на деякий сміття значення, так чому б не для хорошої заходом

789
00:44:03,000 --> 00:44:07,000
Ми принаймні, зробити так, щоб ліва рука тепер на її боці.

790
00:44:07,000 --> 00:44:09,000
Тепер Аніта, візьми його звідси.

791
00:44:09,000 --> 00:44:11,000
Ви повинні Ребекка того, були виділені.

792
00:44:11,000 --> 00:44:20,000
Йдемо далі і знайти, де ми повинні поставити Ребекка.

793
00:44:20,000 --> 00:44:25,000
Добре, дуже добре.

794
00:44:25,000 --> 00:44:28,000
Гаразд, добре, і тепер ми потребуємо вас, щоб забезпечити трохи напрямок,

795
00:44:28,000 --> 00:44:30,000
так що ви досягли Арі.

796
00:44:30,000 --> 00:44:33,000
Його ліва рука є дійсним, але Ребекка, очевидно, належить право,

797
00:44:33,000 --> 00:44:36,000
Так як же ми повинні змінити це зв'язаний список

798
00:44:36,000 --> 00:44:38,000
для того, щоб вставити Ребекка у відповідному місці?

799
00:44:38,000 --> 00:44:42,000
Якщо б ви могли буквально рухати лівої руки людей по всьому міру необхідності,

800
00:44:42,000 --> 00:44:48,000
ми вирішити цю проблему таким чином.

801
00:44:48,000 --> 00:44:52,000
Гаразд, добре, а тим часом ліва рука Ребекка тепер на її боці.

802
00:44:52,000 --> 00:44:54,000
>> Це було занадто просто.

803
00:44:54,000 --> 00:44:57,000
Давайте спробуємо виділення-Ми майже закінчили, 20.

804
00:44:57,000 --> 00:44:59,000
Гаразд, давай вгору.

805
00:44:59,000 --> 00:45:04,000
20 були виділені, так що дозвольте мені йти вперед і сказати знову тут

806
00:45:04,000 --> 00:45:07,000
ми тільки що зробили Саад вузол *.

807
00:45:07,000 --> 00:45:11,000
У нас є Танос (SizeOf (вузла)).

808
00:45:11,000 --> 00:45:16,000
Потім ми робимо точно такий же синтаксис, як ми робили раніше на 20,

809
00:45:16,000 --> 00:45:20,000
і я буду робити далі = NULL, і тепер справа за Анітою

810
00:45:20,000 --> 00:45:23,000
вставити вас у зв'язаному списку, якщо б ви могли грати, що точно таку ж роль.

811
00:45:23,000 --> 00:45:30,000
Виконати.

812
00:45:30,000 --> 00:45:32,000
Гаразд, добре.

813
00:45:32,000 --> 00:45:38,000
Тепер подумайте, перш ніж почати рух лівої руки навколо.

814
00:45:38,000 --> 00:45:46,000
Ви на сьогоднішній день отримали найбільш незручний роль сьогодні.

815
00:45:46,000 --> 00:45:59,000
Чия рука повинна бути перенесена в першу чергу?

816
00:45:59,000 --> 00:46:02,000
Гаразд, почекай, я чую деяких немає в.

817
00:46:02,000 --> 00:46:07,000
Якщо деякі люди хотіли б ввічливо, щоб допомогти вирішити незручну ситуацію тут.

818
00:46:07,000 --> 00:46:11,000
Чия лівою рукою необхідно спочатку оновити можливо? Так.

819
00:46:11,000 --> 00:46:13,000
[Студент] Саад автора.

820
00:46:13,000 --> 00:46:15,000
Добре, Саад, чому, правда?

821
00:46:15,000 --> 00:46:17,000
[Нерозбірливо відповідь студента]

822
00:46:17,000 --> 00:46:19,000
Добре, тому що якщо ми будемо рухатися, як тебе звати? >> Маршалл.

823
00:46:19,000 --> 00:46:22,000
Marshall, якщо ми будемо рухатися руку спочатку вниз до нуля,

824
00:46:22,000 --> 00:46:25,000
Тепер ми в буквальному сенсі сиротами чотирьох чоловік в цьому списку

825
00:46:25,000 --> 00:46:29,000
тому що він був єдиним, вказуючи на Рамона, і все вліво,

826
00:46:29,000 --> 00:46:31,000
так що оновлення вказівників перший був поганий.

827
00:46:31,000 --> 00:46:33,000
Давайте скасувати це.

828
00:46:33,000 --> 00:46:37,000
Добре, а тепер ідіть уперед і перемістити відповідні лівою рукою, вказуючи на Рамона.

829
00:46:37,000 --> 00:46:39,000
Це відчуває себе трохи зайвим.

830
00:46:39,000 --> 00:46:41,000
Тепер є дві людини, вказуючи на Рамона, але це нормально

831
00:46:41,000 --> 00:46:43,000
тому що тепер, як ще ми можемо оновити список?

832
00:46:43,000 --> 00:46:48,000
Що з іншого боку повинен рухатися?

833
00:46:48,000 --> 00:46:53,000
Чудово, тепер ми втратили пам'ять?

834
00:46:53,000 --> 00:46:57,000
Ні, так добре, давайте подивимося, якщо ми не можемо розірвати цей раз.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing в останній раз, номер 5.

836
00:47:00,000 --> 00:47:04,000
Всю дорогу в спину, давай вниз.

837
00:47:04,000 --> 00:47:08,000
Це дуже цікаво.

838
00:47:08,000 --> 00:47:15,000
[Оплески]

839
00:47:15,000 --> 00:47:17,000
Як тебе звуть? >> Рон.

840
00:47:17,000 --> 00:47:19,000
Рон, ладно, ви malloced як номер 5.

841
00:47:19,000 --> 00:47:23,000
Ми тільки виконуваний код, який майже ідентичні ці

842
00:47:23,000 --> 00:47:26,000
тільки з іншою назвою.

843
00:47:26,000 --> 00:47:28,000
Відмінно.

844
00:47:28,000 --> 00:47:38,000
Тепер, Аніта, удачі вставки № 5 у списку наразі.

845
00:47:38,000 --> 00:47:43,000
Добре, а?

846
00:47:43,000 --> 00:47:47,000
Відмінно, так що це дійсно третій з трьох загального числа випадків.

847
00:47:47,000 --> 00:47:49,000
Спочатку був хтось, врешті-решт, Ребекка.

848
00:47:49,000 --> 00:47:51,000
У нас тоді був хтось в середині.

849
00:47:51,000 --> 00:47:53,000
Тепер у нас є хтось на самому початку, і в цьому прикладі,

850
00:47:53,000 --> 00:47:56,000
у нас тепер оновити Лукас вперше

851
00:47:56,000 --> 00:48:00,000
тому що перший елемент у списку наразі має вказувати на новий вузол,

852
00:48:00,000 --> 00:48:03,000
які, в свою чергу, вказує на номер вузла 9.

853
00:48:03,000 --> 00:48:06,000
>> Це було дуже ніяково демонстрації, я впевнений,

854
00:48:06,000 --> 00:48:08,000
таким чином, велике оплески для цих хлопців, якби могли.

855
00:48:08,000 --> 00:48:11,000
Красиво зроблено.

856
00:48:11,000 --> 00:48:17,000
Ось і все. Ви можете зберегти ваші папірці, як мало пам'яті.

857
00:48:17,000 --> 00:48:22,000
Виявляється, що робить це в коді

858
00:48:22,000 --> 00:48:26,000
це не так просто, як просто рух руками

859
00:48:26,000 --> 00:48:28,000
і, вказуючи покажчики на різні речі.

860
00:48:28,000 --> 00:48:31,000
Але розумію, що, коли приходить час, щоб реалізувати щось подібне

861
00:48:31,000 --> 00:48:34,000
зв'язаний список або варіант, якщо ви зосередитеся насправді

862
00:48:34,000 --> 00:48:38,000
ці базові основи, крихітні проблем у мене немає, щоб з'ясувати,

863
00:48:38,000 --> 00:48:43,000
він цю руку або цього боку, розумію, що те, що в іншому випадку досить складна програма

864
00:48:43,000 --> 00:48:47,000
може, по суті, зводиться до досить простим будівельних блоків, як це.

865
00:48:47,000 --> 00:48:51,000
>> Давайте речі в більш складних напрямку досі.

866
00:48:51,000 --> 00:48:53,000
Тепер у нас є поняття пов'язаного списку.

867
00:48:53,000 --> 00:48:57,000
У нас також є, завдяки пропозиції туди-двусвязний список,

868
00:48:57,000 --> 00:49:01,000
, Який виглядає майже так само, але тепер у нас є два покажчика всередині структури

869
00:49:01,000 --> 00:49:05,000
замість одного, і ми могли б, ймовірно, назвати ці покажчики попередньої і наступної

870
00:49:05,000 --> 00:49:08,000
або вліво або вправо, але ми, справді, потрібні два з них.

871
00:49:08,000 --> 00:49:10,000
Код буде трохи складніше.

872
00:49:10,000 --> 00:49:12,000
Аните довелося б робити більше роботи тут, на сцені.

873
00:49:12,000 --> 00:49:15,000
Але ми, безумовно, може здійснювати таку структуру.

874
00:49:15,000 --> 00:49:19,000
З точки зору часу роботи, однак, що було б час роботи

875
00:49:19,000 --> 00:49:24,000
Аніта для знаходження числа п у зв'язаному списку зараз?

876
00:49:24,000 --> 00:49:27,000
Тим не менш велика O п, так що це не краще, ніж лінійний пошук.

877
00:49:27,000 --> 00:49:29,000
Ми не можемо зробити бінарний пошук, хоча, знову ж.

878
00:49:29,000 --> 00:49:34,000
Чому це було так? Ви не можете стрибати.

879
00:49:34,000 --> 00:49:36,000
Хоча ми, очевидно, всі люди на сцені,

880
00:49:36,000 --> 00:49:39,000
і Аніта могла б eyeballed його і сказав: "Ось середині списку"

881
00:49:39,000 --> 00:49:42,000
вона не буде знати, що якщо вона комп'ютерної програми

882
00:49:42,000 --> 00:49:47,000
оскільки єдине, що їй довелося замкнутися на на початку сценарію

883
00:49:47,000 --> 00:49:50,000
був Лукас, який був першим покажчиком.

884
00:49:50,000 --> 00:49:53,000
Вона обов'язково повинна слідувати за тими посиланнями,

885
00:49:53,000 --> 00:49:56,000
вважаючи її шляху, поки не знайшла приблизно посередині,

886
00:49:56,000 --> 00:49:58,000
і навіть тоді, вона не буде знати, коли вона досягла середини

887
00:49:58,000 --> 00:50:01,000
якщо вона проходить весь шлях до кінця, щоб з'ясувати, скільки є,

888
00:50:01,000 --> 00:50:05,000
потім відступає, і, що теж було б важко, якщо ви не були

889
00:50:05,000 --> 00:50:07,000
двусвязний список якийсь.

890
00:50:07,000 --> 00:50:10,000
>> Рішення деяких проблем сьогодні, але введення інших.

891
00:50:10,000 --> 00:50:12,000
А як щодо різних структур даних в цілому?

892
00:50:12,000 --> 00:50:15,000
Це фотографія з лотків у Mather House,

893
00:50:15,000 --> 00:50:19,000
і в цьому випадку, у нас є структура даних, ми також вид вже говорили.

894
00:50:19,000 --> 00:50:22,000
Ми говорили про стеку в контексті пам'яті,

895
00:50:22,000 --> 00:50:26,000
і це як би навмисно назвали тому, що стек в термінах пам'яті

896
00:50:26,000 --> 00:50:31,000
фактично є структурою даних, яка все більше і більше речей шар поверх неї.

897
00:50:31,000 --> 00:50:35,000
Але найцікавіше про стек, як це має місце в дійсності,

898
00:50:35,000 --> 00:50:38,000
те, що це особливий вид структури даних.

899
00:50:38,000 --> 00:50:42,000
Це структура даних, причому перший елемент

900
00:50:42,000 --> 00:50:46,000
це останній елемент з.

901
00:50:46,000 --> 00:50:50,000
Якщо ви перший лоток ставити в стек,

902
00:50:50,000 --> 00:50:53,000
Ви збираєтеся бути, на жаль, останній лотка повинні бути прийняті стека,

903
00:50:53,000 --> 00:50:55,000
і це не завжди добре.

904
00:50:55,000 --> 00:50:58,000
І навпаки, ви можете думати про нього навпаки,

905
00:50:58,000 --> 00:51:02,000
В останнє є першим з.

906
00:51:02,000 --> 00:51:05,000
>> Тепер, будь-які сценарії приходять на розум, де, маючи стек

907
00:51:05,000 --> 00:51:08,000
структура даних, де у вас є, що власність

908
00:51:08,000 --> 00:51:13,000
останні увійшов, першим вийшов, насправді переконливим?

909
00:51:13,000 --> 00:51:16,000
Хіба це добре? Хіба це погано?

910
00:51:16,000 --> 00:51:19,000
Це, безумовно, погано, якщо лотків не були всі однакові

911
00:51:19,000 --> 00:51:21,000
і всі вони були спеціальним різних кольорів і ще багато чого,

912
00:51:21,000 --> 00:51:24,000
і колір ви хочете, всю дорогу внизу.

913
00:51:24,000 --> 00:51:26,000
Звичайно, ви не можете отримати, що без великих зусиль.

914
00:51:26,000 --> 00:51:28,000
Ви повинні почати з верхньої і працювати ваш шлях вниз.

915
00:51:28,000 --> 00:51:31,000
Точно так само, як якщо б ви були одним з цих вентиляторів хлопчиків

916
00:51:31,000 --> 00:51:34,000
хто чекає всю ніч, намагаючись отримати iPhone і ліній до

917
00:51:34,000 --> 00:51:36,000
в такому місці, як це?

918
00:51:36,000 --> 00:51:40,000
Хіба не було б здорово, якби в Apple Store

919
00:51:40,000 --> 00:51:42,000
були структуру стека даних?

920
00:51:42,000 --> 00:51:44,000
Ура? Мало того?

921
00:51:44,000 --> 00:51:47,000
Це тільки для людей, які з'являються в останньої хвилини

922
00:51:47,000 --> 00:51:50,000
, А потім отримати зірвав черзі.

923
00:51:50,000 --> 00:51:52,000
І справді, той факт, що я був так схильний говорити чергу

924
00:51:52,000 --> 00:51:56,000
насправді відповідає тому, що ми б назвали таку структуру даних,

925
00:51:56,000 --> 00:51:59,000
один в реальності, де порядок має значення,

926
00:51:59,000 --> 00:52:02,000
і ви хочете перший, щоб бути першою з

927
00:52:02,000 --> 00:52:04,000
якщо тільки заради людської справедливості.

928
00:52:04,000 --> 00:52:07,000
Ми зазвичай називаємо це структура даних черзі.

929
00:52:07,000 --> 00:52:11,000
>> Виявляється, крім пов'язаних списків, ми можемо почати використовувати ці ж основні ідеї

930
00:52:11,000 --> 00:52:15,000
і почати створювати нове і різні типи рішень проблем.

931
00:52:15,000 --> 00:52:19,000
Наприклад, у випадку стека, ми могли б являти собою стек

932
00:52:19,000 --> 00:52:22,000
, Використовуючи структуру даних, як це, я хотів би запропонувати.

933
00:52:22,000 --> 00:52:26,000
У цьому випадку, я оголосив структури, і я вже говорив всередині цієї структури

934
00:52:26,000 --> 00:52:30,000
являє собою масив чисел, а потім змінна розміром,

935
00:52:30,000 --> 00:52:33,000
і Я буду називати цю річ стека.

936
00:52:33,000 --> 00:52:35,000
Тепер, чому це дійсно працює?

937
00:52:35,000 --> 00:52:43,000
У разі стек, я міг би зробити це ефективно на екрані у вигляді масиву.

938
00:52:43,000 --> 00:52:47,000
Ось мій стек. Такі мої номери.

939
00:52:47,000 --> 00:52:50,000
І ми будемо малювати їх, як це, це, це, це, це.

940
00:52:50,000 --> 00:52:53,000
А то у мене деякі інші члени даних тут,

941
00:52:53,000 --> 00:52:58,000
яка називається розмір, так це розмір, і це числа,

942
00:52:58,000 --> 00:53:02,000
і колективно, всією Ipad тут являє собою один стек структури.

943
00:53:02,000 --> 00:53:07,000
Зараз, за ​​замовчуванням, розмір імовірно повинен бути ініціалізований до 0,

944
00:53:07,000 --> 00:53:11,000
і те, що всередині масиву чисел спочатку

945
00:53:11,000 --> 00:53:14,000
Коли я вперше виділити масив?

946
00:53:14,000 --> 00:53:16,000
Garbage. Хто знає? І це насправді не має значення.

947
00:53:16,000 --> 00:53:20,000
Це не має значення, якщо це 1, 2, 3, 4, 5, зовсім випадково

948
00:53:20,000 --> 00:53:25,000
на невезіння, що зберігаються в моїй структурі, тому що поки я знаю, що розмір стека

949
00:53:25,000 --> 00:53:29,000
дорівнює 0, то я знаю, програмним, не дивися на будь-який з елементів у масиві.

950
00:53:29,000 --> 00:53:31,000
Це не має значення, що там.

951
00:53:31,000 --> 00:53:34,000
Не дивися на них, як би наслідок розмірі 0.

952
00:53:34,000 --> 00:53:38,000
>> Але припустимо, що тепер я йду вперед і вставити щось у стек.

953
00:53:38,000 --> 00:53:42,000
Я хочу, щоб вставити номер 5, так що я поклав № 5 тут,

954
00:53:42,000 --> 00:53:45,000
і то що я можу поставити сюди?

955
00:53:45,000 --> 00:53:48,000
Зараз я б насправді поклав 1 для розміру,

956
00:53:48,000 --> 00:53:50,000
і в даний час стек має розмір 1.

957
00:53:50,000 --> 00:53:53,000
Що робити, якщо я йду вперед і вставити число, скажімо, 7 наст?

958
00:53:53,000 --> 00:53:57,000
Це те оновлюється до 2, а потім ми будемо робити 9,

959
00:53:57,000 --> 00:54:02,000
а потім ця оновлюється до 3.

960
00:54:02,000 --> 00:54:05,000
Але цікава особливість тепер цей стек є те, що

961
00:54:05,000 --> 00:54:09,000
Я повинен видалити елемент якого, якщо я хочу спливав

962
00:54:09,000 --> 00:54:12,000
щось з стека, так би мовити?

963
00:54:12,000 --> 00:54:14,000
9 була б перше, що потрібно йти.

964
00:54:14,000 --> 00:54:18,000
Як випливає картина зміниться, якщо я хочу поп елемент з стека,

965
00:54:18,000 --> 00:54:20,000
хотілося лоток Mather?

966
00:54:20,000 --> 00:54:22,000
Так. >> [Студент] Встановити розмір до 2.

967
00:54:22,000 --> 00:54:27,000
Точно, все, що я зробити, це встановити розмір 2, і що мені робити з масивом?

968
00:54:27,000 --> 00:54:29,000
Я не маю нічого робити.

969
00:54:29,000 --> 00:54:32,000
Я міг би, просто щоб бути анальний, покласти 0 існує або -1 або щось означають,

970
00:54:32,000 --> 00:54:34,000
що це не законно значення, але це не має значення, тому що

971
00:54:34,000 --> 00:54:37,000
Я можу записувати за межами самого масиву, як довго це

972
00:54:37,000 --> 00:54:41,000
так що я знаю тільки подивіться на перші два елементи в цьому масиві.

973
00:54:41,000 --> 00:54:47,000
Тепер, якщо я піду і додайте номер 8 до цього масиву, яким чином картина зміниться наступним?

974
00:54:47,000 --> 00:54:50,000
Це стає 8, і це стає 3.

975
00:54:50,000 --> 00:54:52,000
Я різання декілька кутів тут.

976
00:54:52,000 --> 00:54:56,000
Тепер у нас є 5, 7, 8, і ми повернулися до розміру 3.

977
00:54:56,000 --> 00:54:58,000
Це досить простий в реалізації,

978
00:54:58,000 --> 00:55:06,000
Але коли ми будемо шкодувати про це дизайнерське рішення?

979
00:55:06,000 --> 00:55:09,000
Коли речі починають йти дуже, дуже неправильно? Так.

980
00:55:09,000 --> 00:55:11,000
[Нерозбірливо відповідь студента]

981
00:55:11,000 --> 00:55:13,000
Якщо ви хочете, щоб повернутися і отримати перший елемент, який вставив

982
00:55:13,000 --> 00:55:18,000
>> При цьому виявляється, навіть якщо стек являє собою масив під капотом,

983
00:55:18,000 --> 00:55:21,000
ці структури даних, ми почали говорити про також відомий як

984
00:55:21,000 --> 00:55:25,000
абстрактних структур даних, яким, як вони реалізуються

985
00:55:25,000 --> 00:55:27,000
повністю, крім точки.

986
00:55:27,000 --> 00:55:31,000
Структура даних, як стек передбачається додати підтримку

987
00:55:31,000 --> 00:55:35,000
операцій, таких як поштовх, який штовхає лоток в стек,

988
00:55:35,000 --> 00:55:39,000
і поп-музики, яка видаляє елемент з стека, і це все.

989
00:55:39,000 --> 00:55:43,000
Якби ви завантажите чужий код, який вже реалізований

990
00:55:43,000 --> 00:55:46,000
те, що називається стеком, що людина написала б

991
00:55:46,000 --> 00:55:49,000
тільки дві функції для вас, штовхати і поп-музики, чия єдина мета в житті

992
00:55:49,000 --> 00:55:51,000
було б зробити саме це.

993
00:55:51,000 --> 00:55:54,000
Ви або його або її, хто здійснював цю програму

994
00:55:54,000 --> 00:55:58,000
був би зовсім один, щоб вирішити, як реалізувати

995
00:55:58,000 --> 00:56:00,000
Семантика натискання і з'являються під капотом

996
00:56:00,000 --> 00:56:03,000
або функціональність натискання і з'являються.

997
00:56:03,000 --> 00:56:07,000
І я зробив кілька короткозорим рішенням тут

998
00:56:07,000 --> 00:56:10,000
шляхом реалізації свого стека з цією простою структурою даних, то чому?

999
00:56:10,000 --> 00:56:12,000
Коли ж цей розрив структури даних?

1000
00:56:12,000 --> 00:56:18,000
У який момент я повинен повертати помилку, коли користувач викликає поштовх, наприклад?

1001
00:56:18,000 --> 00:56:20,000
[Студент] Якщо немає більше місця.

1002
00:56:20,000 --> 00:56:23,000
Саме, якщо немає більше місця, якщо я перевищив ємність,

1003
00:56:23,000 --> 00:56:27,000
який усі великі літери, оскільки вона припускає, що це свого роду глобальна константа.

1004
00:56:27,000 --> 00:56:30,000
Ну, тоді я просто хочу, щоб сказати: «Вибачте, я не можу висунути ще одне значення

1005
00:56:30,000 --> 00:56:32,000
в стек ", як в Mather.

1006
00:56:32,000 --> 00:56:36,000
>> У якийсь момент вони збираються потрапити у верхню частину цього маленького кабінету.

1007
00:56:36,000 --> 00:56:39,000
Там немає більше місця або потужності в стеку, і в цей момент там якась помилка.

1008
00:56:39,000 --> 00:56:42,000
Вони повинні поставити елемент десь в іншому місці, лоток десь в іншому місці,

1009
00:56:42,000 --> 00:56:44,000
або взагалі нікуди.

1010
00:56:44,000 --> 00:56:47,000
Тепер, з чергою, ми могли б реалізувати це трохи по-іншому.

1011
00:56:47,000 --> 00:56:50,000
Черга трохи відрізняється тим, що під капотом, він може бути реалізований

1012
00:56:50,000 --> 00:56:54,000
як масив, але чому, в такому випадку, я пропоную

1013
00:56:54,000 --> 00:56:59,000
також є голова елемент, який представляє главу списку,

1014
00:56:59,000 --> 00:57:06,000
Перед списку, перша людина в черзі в магазин Apple, на додаток до розміру?

1015
00:57:06,000 --> 00:57:14,000
Навіщо потрібна додаткова порція даних тут?

1016
00:57:14,000 --> 00:57:16,000
Згадайте, які номери є

1017
00:57:16,000 --> 00:57:18,000
якщо я намалював його таким чином.

1018
00:57:18,000 --> 00:57:21,000
Нехай це зараз черги замість того, щоб стік,

1019
00:57:21,000 --> 00:57:24,000
різниця в тому, як Apple Store в черзі справедливо.

1020
00:57:24,000 --> 00:57:27,000
Перша людина в черзі в початок списку, номер 5 в цьому випадку,

1021
00:57:27,000 --> 00:57:30,000
він або вона буде давати в магазині в першу чергу.

1022
00:57:30,000 --> 00:57:32,000
Давайте зробимо це.

1023
00:57:32,000 --> 00:57:35,000
Припустимо, що це стан моєї черги в даний момент часу, і тепер в Apple Store

1024
00:57:35,000 --> 00:57:39,000
відкривається, і перша особа, номер 5, направляється в магазин.

1025
00:57:39,000 --> 00:57:43,000
Як я можу змінити картину тепер, коли я де-черзі першої особи

1026
00:57:43,000 --> 00:57:47,000
на передній лінії?

1027
00:57:47,000 --> 00:57:50,000
Що це? >> [Студент] Зміни в черзі.

1028
00:57:50,000 --> 00:57:52,000
Зміна головою, так що 5 зникає.

1029
00:57:52,000 --> 00:57:56,000
Насправді, це, ніби, як краще це зробити?

1030
00:57:56,000 --> 00:58:00,000
Насправді, це як ніби цей хлопець зникає.

1031
00:58:00,000 --> 00:58:03,000
Що б номер 7 робимо в реальному магазині?

1032
00:58:03,000 --> 00:58:05,000
Вони б зробити великий крок вперед.

1033
00:58:05,000 --> 00:58:08,000
>> Але що ми прийшли до розуміння, коли мова йде про масивах

1034
00:58:08,000 --> 00:58:10,000
і переміщення речей навколо?

1035
00:58:10,000 --> 00:58:12,000
Це свого роду марна трата часу, так?

1036
00:58:12,000 --> 00:58:16,000
Чому ви повинні бути настільки анальний, щоб мати першої особи

1037
00:58:16,000 --> 00:58:21,000
На початку лінії на фізичному початок блоку пам'яті?

1038
00:58:21,000 --> 00:58:23,000
Це абсолютно не потрібно. Чому?

1039
00:58:23,000 --> 00:58:26,000
Що може я просто пам'ятаю, а? >> [Нерозбірливо відповідь студента]

1040
00:58:26,000 --> 00:58:30,000
Точно, я міг би просто пам'ятаю, з цієї додаткової головкою члена даних

1041
00:58:30,000 --> 00:58:34,000
що тепер глава список не 0, що це було хвилину тому.

1042
00:58:34,000 --> 00:58:39,000
Зараз це насправді номер 1. Таким чином, я отримую невелику оптимізацію.

1043
00:58:39,000 --> 00:58:44,000
Просто тому, що я де-черзі хтось з лінії на початку лінії в Apple Store

1044
00:58:44,000 --> 00:58:47,000
не означає, що кожен повинен зміщуватися, що нагадаємо, є лінійною операцією.

1045
00:58:47,000 --> 00:58:50,000
Я можу замість цього проводити постійну часу тільки

1046
00:58:50,000 --> 00:58:53,000
і досягнення, то набагато швидше відповідь.

1047
00:58:53,000 --> 00:58:56,000
Але ціна, яку я плачу це те, що щоб отримати, що додаткова продуктивність

1048
00:58:56,000 --> 00:58:58,000
і не мають перекласти всі?

1049
00:58:58,000 --> 00:59:01,000
Так. >> [Нерозбірливо відповідь студента]

1050
00:59:01,000 --> 00:59:04,000
Можна додати більше людей, добре, що проблема ортогональної

1051
00:59:04,000 --> 00:59:07,000
з тим, що ми не перекладаючи людей навколо.

1052
00:59:07,000 --> 00:59:11,000
Він як і раніше масиву, чи так ми перекласти всі або не-

1053
00:59:11,000 --> 00:59:13,000
О, я бачу, що ви маєте на увазі, ладно.

1054
00:59:13,000 --> 00:59:16,000
Насправді, я згоден з тим, що ви говорите, що він майже як якби

1055
00:59:16,000 --> 00:59:19,000
Ми тепер ніколи не буде використовувати початку цього масиву більше

1056
00:59:19,000 --> 00:59:22,000
тому що, якщо я видалю 5, то я можу видалити 7.

1057
00:59:22,000 --> 00:59:24,000
Але я тільки поставити людей з правого боку.

1058
00:59:24,000 --> 00:59:28,000
>> Він відчуває, як я витрачати простір, і в підсумку моя черга розпадається взагалі нічого,

1059
00:59:28,000 --> 00:59:31,000
таким чином, ми могли б просто є люди, запахом,

1060
00:59:31,000 --> 00:59:35,000
і ми могли думати про це масив дійсно як свого роду кругова структура,

1061
00:59:35,000 --> 00:59:38,000
але ми використовуємо те, що оператор C, щоб робити такого роду запахом?

1062
00:59:38,000 --> 00:59:40,000
[Нерозбірливо відповідь студента] >> оператора по модулю.

1063
00:59:40,000 --> 00:59:43,000
Було б трохи дратує продумати, як ви будете робити з запахом,

1064
00:59:43,000 --> 00:59:46,000
але ми могли б це зробити, і ми могли почати збирати людей на те, що раніше передній лінії,

1065
00:59:46,000 --> 00:59:52,000
але ми просто пам'ятаємо з цією головою змінна які фактичного керівника лінія насправді.

1066
00:59:52,000 --> 00:59:57,000
Що, якщо, замість цього, наша мета в кінцевому підсумку, однак,

1067
00:59:57,000 --> 01:00:00,000
було шукати числа, як ми зробили тут, на сцені з Анітою,

1068
01:00:00,000 --> 01:00:02,000
але ми дійсно хочемо найкращою з усіх цих світах?

1069
01:00:02,000 --> 01:00:05,000
Ми хочемо більше складності, ніж масив дозволяє

1070
01:00:05,000 --> 01:00:09,000
тому що ми хочемо можливість динамічно зростати структури даних.

1071
01:00:09,000 --> 01:00:12,000
Але ми не хочемо вдаватися до того, що ми вказали,

1072
01:00:12,000 --> 01:00:15,000
У першій лекції не був оптимальним алгоритмом,

1073
01:00:15,000 --> 01:00:17,000
, Що лінійного пошуку.

1074
01:00:17,000 --> 01:00:21,000
Виявляється, що можна, справді, досягнення

1075
01:00:21,000 --> 01:00:24,000
або принаймні близько до постійної часу, в результаті чого хтось, як Аніта,

1076
01:00:24,000 --> 01:00:27,000
якщо вона налаштовує її структуру даних, щоб не бути пов'язаним списком,

1077
01:00:27,000 --> 01:00:30,000
щоб не бути стек, щоб не бути черг, може, справді,

1078
01:00:30,000 --> 01:00:33,000
придумати структуру даних, яка дозволяє їй шукати речі,

1079
01:00:33,000 --> 01:00:37,000
навіть слова, а не просто цифри, в тому, що ми будемо називати постійною часу.

1080
01:00:37,000 --> 01:00:40,000
>> І справді, забігаючи вперед, одна з psets в цьому класі майже завжди

1081
01:00:40,000 --> 01:00:43,000
здійснення перевірки правопису, в результаті чого

1082
01:00:43,000 --> 01:00:46,000
ми даємо вам знову близько 150000 англійських слів і мета

1083
01:00:46,000 --> 01:00:51,000
завантажити в пам'ять тих, і швидко зможе відповісти на питання про форму

1084
01:00:51,000 --> 01:00:54,000
це слово написано правильно?

1085
01:00:54,000 --> 01:00:58,000
І це було б дійсно смоктати, якщо вам довелося перебрати всі 150000 слів, щоб відповісти на це питання.

1086
01:00:58,000 --> 01:01:02,000
Але, насправді, ми побачимо, що ми можемо зробити це в дуже, дуже швидкий час.

1087
01:01:02,000 --> 01:01:06,000
І це буде включати здійснення так званих хеш-таблиці,

1088
01:01:06,000 --> 01:01:09,000
І хоча на перший погляд це те, що називається хеш-таблиці буде

1089
01:01:09,000 --> 01:01:12,000
Давайте досягнення цих супер швидкого реагування,

1090
01:01:12,000 --> 01:01:18,000
Виявляється, що є насправді проблема.

1091
01:01:18,000 --> 01:01:23,000
Коли приходить час для здійснення цього, що називається, знову ж таки, я роблю це знову.

1092
01:01:23,000 --> 01:01:25,000
Я тільки тут.

1093
01:01:25,000 --> 01:01:28,000
Коли приходить час для здійснення цієї речі, званої хеш-таблиці,

1094
01:01:28,000 --> 01:01:30,000
ми будемо мати, щоб прийняти рішення.

1095
01:01:30,000 --> 01:01:32,000
Яким повинен цю річ насправді бути?

1096
01:01:32,000 --> 01:01:36,000
І коли ми починаємо вставки цифр в цій хеш-таблиці,

1097
01:01:36,000 --> 01:01:38,000
як ми будемо зберігати їх таким чином,

1098
01:01:38,000 --> 01:01:42,000
що ми можемо отримати їх назад так швидко, як ми отримали їх?

1099
01:01:42,000 --> 01:01:45,000
Але ми побачимо незабаром, що це питання

1100
01:01:45,000 --> 01:01:48,000
коли день народження кожної людини в класі буде цілком доречним.

1101
01:01:48,000 --> 01:01:51,000
Виявляється, що в цій кімнаті, у нас є кілька сотень людей,

1102
01:01:51,000 --> 01:01:56,000
так що ймовірність того, що два з нас є той же день народження, ймовірно, досить висока.

1103
01:01:56,000 --> 01:01:58,000
Що, якщо там були тільки 40 з нас в цій кімнаті?

1104
01:01:58,000 --> 01:02:02,000
Які шанси двох людей, які мають той же день народження?

1105
01:02:02,000 --> 01:02:04,000
[Студенти] Понад 50%.

1106
01:02:04,000 --> 01:02:06,000
Так, більш ніж на 50%. Насправді, я навіть приніс графік.

1107
01:02:06,000 --> 01:02:08,000
Виявляється, і це насправді просто попередній перегляд-

1108
01:02:08,000 --> 01:02:12,000
якщо є тільки 58 із нас у цьому залі, імовірність того, 2 з нас

1109
01:02:12,000 --> 01:02:16,000
що має той же день народження є надзвичайно високим, майже 100%,

1110
01:02:16,000 --> 01:02:20,000
і що збирається викликати цілий букет боляче для нас в середу.

1111
01:02:20,000 --> 01:02:24,000
>> З урахуванням сказаного, давайте відкладемо тут. Ми будемо бачити Вас в середу.

1112
01:02:24,000 --> 01:02:28,000
[Оплески]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]