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

2
00:00:11,460 --> 00:00:12,250
>> DAVID мала: Добре.

3
00:00:12,250 --> 00:00:13,860
Ласкаво просимо назад в CS50.

4
00:00:13,860 --> 00:00:16,190
Це початок 8-го тижня.

5
00:00:16,190 --> 00:00:21,320
І нагадати, що проблема набору 5 закінчився
з трохи складним завданням.

6
00:00:21,320 --> 00:00:25,210
Так що якщо ви відновити всі ваші
навчання стипендіатів і фотографії СА

7
00:00:25,210 --> 00:00:30,480
у файлі card.raw, Ви маєте право
Тепер, щоб знайти всі ці люди, і

8
00:00:30,480 --> 00:00:34,510
один щасливий переможець буде ходити додому з одним
з цих речей, стрибок руху

9
00:00:34,510 --> 00:00:37,450
пристрій, який можна використовувати для остаточної
проектів, наприклад.

10
00:00:37,450 --> 00:00:39,860
>> Це, щороку призводить до
трохи моторошний.

11
00:00:39,860 --> 00:00:43,480
І так, що я думав, що зробити, це поділитися
з вами деякими з нот, які мають

12
00:00:43,480 --> 00:00:47,370
туди і назад протягом
штатний розклад пізно.

13
00:00:47,370 --> 00:00:51,110
Наприклад, тільки вчора ввечері, цитати
кінець цитати, від одного з персоналу

14
00:00:51,110 --> 00:00:55,000
Члени "Я просто був студент стукіт
в мої двері, щоб зробити знімок зі мною.

15
00:00:55,000 --> 00:00:59,020
Сталкери, скажу я вам. "Почався
достатнім описом, а потім ми переїхали

16
00:00:59,020 --> 00:01:02,830
на, годину або трохи пізніше, "У мене було
студент чекає мене після розділу

17
00:01:02,830 --> 00:01:06,080
і у нього були всі наші імена і фотографії
на кілька аркушів паперу. "Добре.

18
00:01:06,080 --> 00:01:09,230
Так організовано, але не
все, що моторошне ще.

19
00:01:09,230 --> 00:01:12,520
>> Потім: "Я був за містом, в ці вихідні,
і коли я повернувся, було один в

20
00:01:12,520 --> 00:01:12,630
моє

21
00:01:12,630 --> 00:01:16,740
спальню. "[сміється]

22
00:01:16,740 --> 00:01:20,410
DAVID мала: Наступна цитата з персоналу
користувача ", студент прийшов до мене додому на

23
00:01:20,410 --> 00:01:25,330
Сомервілль в 4 ранку сьогодні вранці. "Далі
персоналу ", я добрався до готелі в Сан-

24
00:01:25,330 --> 00:01:30,016
Франциско і студент чекав
мене в лобі з трьома дзеркалок ".

25
00:01:30,016 --> 00:01:31,510
Тип камери.

26
00:01:31,510 --> 00:01:34,980
"Я навіть не на персонал в цьому семестрі,
але студент увірвався в мій будинок це

27
00:01:34,980 --> 00:01:40,480
вранці і записав все це
зі склом Google. "І тоді, нарешті,

28
00:01:40,480 --> 00:01:43,650
"Принаймні 12 людей були з нетерпінням
чекає мене, коли я вийшов зі свого

29
00:01:43,650 --> 00:01:44,800
лімузина, а потім я

30
00:01:44,800 --> 00:01:46,970
прокинувся. "Добре.

31
00:01:46,970 --> 00:01:57,690
Так що серед фотографій, як ви
Нагадаємо, що в цей хлопець тут, хто ви

32
00:01:57,690 --> 00:02:01,850
могли б знати, як Міло банан, який живе
з Лорен Карвалью, наші голови

33
00:02:01,850 --> 00:02:02,905
викладанні Fellow.

34
00:02:02,905 --> 00:02:05,170
Міло, Міло, іди сюди хлопчик.

35
00:02:05,170 --> 00:02:06,320
Майло.

36
00:02:06,320 --> 00:02:08,650
Майло.

37
00:02:08,650 --> 00:02:12,230
Майте на увазі, що він носить Google скла, так що
ми покажемо вам все це після.

38
00:02:12,230 --> 00:02:16,190
Так що це Міло, якщо ви хотіли б
сфотографуватися з ним пізніше.

39
00:02:16,190 --> 00:02:18,240
Якщо ви хочете, щоб виглядати
на аудиторію там.

40
00:02:18,240 --> 00:02:19,430
ОК.

41
00:02:19,430 --> 00:02:20,200
Це хороші кадри.

42
00:02:20,200 --> 00:02:22,556
Ну, Міло банан.

43
00:02:22,556 --> 00:02:23,941
О, не робіть цього.

44
00:02:23,941 --> 00:02:29,020
>> [Сміється]

45
00:02:29,020 --> 00:02:29,470
>> ОК.

46
00:02:29,470 --> 00:02:34,550
Так слово, то про те, що чекає попереду,
тому що, як ми починаємо перехід,

47
00:02:34,550 --> 00:02:38,410
На цьому тижні Зокрема, з С в
командного рядка середовища і PHP

48
00:02:38,410 --> 00:02:42,720
JavaScript і SQL і HTML і CSS в
веб-середовищі, ми будемо

49
00:02:42,720 --> 00:02:44,490
оснащення вам все
більше знань для

50
00:02:44,490 --> 00:02:46,010
потенційних остаточного проектів.

51
00:02:46,010 --> 00:02:49,240
З цією метою, звичайно, має
Традиція проведення семінарів, які

52
00:02:49,240 --> 00:02:50,950
знаходяться на тангенціальному теми
до курсу.

53
00:02:50,950 --> 00:02:54,330
Дуже, пов'язаних з програмуванням і
розробки додатків і так далі, але

54
00:02:54,330 --> 00:02:57,010
не обов'язково вивчені
власного курсу навчальній програмі.

55
00:02:57,010 --> 00:03:00,250
>> Так що якщо ви могли б бути зацікавлені в одному
або кілька семінарів в цьому році,

56
00:03:00,250 --> 00:03:02,530
зареєструватися на cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Є старший семінари
на cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
І в реєстр до цих пір в цьому році
Чудовий веб-додатків з Рубіном на

59
00:03:10,620 --> 00:03:13,580
Рейки, який є альтернативою
мови PHP.

60
00:03:13,580 --> 00:03:14,900
Комп'ютерна лінгвістика.

61
00:03:14,900 --> 00:03:18,710
Введення в IOS, яка є
платформі, яка використовується для iPhone і

62
00:03:18,710 --> 00:03:19,850
Ipad розвитку.

63
00:03:19,850 --> 00:03:22,890
JavaScript для веб-додатків, ми розглянемо
, Але в цьому семінарі, ви перейдете

64
00:03:22,890 --> 00:03:24,070
більш докладно.

65
00:03:24,070 --> 00:03:27,390
>> Стрибок руху, так що ми насправді є
наших друзів з Leap руху,

66
00:03:27,390 --> 00:03:29,160
самої компанії, приєднуйтесь до нас.

67
00:03:29,160 --> 00:03:31,800
Завтра, по суті, забезпечити
практичний семінар, якщо

68
00:03:31,800 --> 00:03:33,320
представляти інтерес для Вас.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, альтернативний прийом
Використання JavaScript не в браузері,

70
00:03:38,770 --> 00:03:39,970
а на сервері.

71
00:03:39,970 --> 00:03:42,110
Node.js, який дуже
в тому ж дусі, а також.

72
00:03:42,110 --> 00:03:43,650
Гладкий дизайн Android.

73
00:03:43,650 --> 00:03:46,990
Android Будучи дуже популярним альтернативним
Телефон для IOS і Windows

74
00:03:46,990 --> 00:03:48,790
та інших мобільних платформ.

75
00:03:48,790 --> 00:03:51,180
І веб активної оборони.

76
00:03:51,180 --> 00:03:54,590
>> Таким чином, справді, якщо ви хочете
взяти участь у цьому, дозвольте мені

77
00:03:54,590 --> 00:03:55,840
зробити це до відома.

78
00:03:55,840 --> 00:03:57,790
Ми дуже раді повідомити, що
наші друзі в Leap

79
00:03:57,790 --> 00:03:59,140
Рух, який є запуск -

80
00:03:59,140 --> 00:04:01,300
це пристрій дійсно просто прийшов
з кілька місяців тому -

81
00:04:01,300 --> 00:04:05,960
люб'язно пожертвував 30 таких пристроїв
класу стільки студентів, якщо

82
00:04:05,960 --> 00:04:08,670
Ви хотіли б запозичити апаратних
до кінця семестру і використовувати його для

83
00:04:08,670 --> 00:04:10,390
фактичного кінцевого проекту.

84
00:04:10,390 --> 00:04:11,890
Вони підтримують декілька мов.

85
00:04:11,890 --> 00:04:16,040
Ніхто з них не C, жоден з них PHP, так
реалізувати один або декілька з цих семінари

86
00:04:16,040 --> 00:04:16,899
може виявитися інтересів.

87
00:04:16,899 --> 00:04:19,730
І всі вони будуть зняті у
тому випадку, якщо ви не в змозі

88
00:04:19,730 --> 00:04:21,380
особисто бути присутнім на засіданні.

89
00:04:21,380 --> 00:04:25,000
Розклад буде оголошено через
електронної пошти, як ми зміцнити номерів.

90
00:04:25,000 --> 00:04:28,460
>> І, нарешті, якщо ви йдете в
projects.cs.50.net, це веб-сайт

91
00:04:28,460 --> 00:04:31,450
ми підтримуємо щороку, що ми запрошуємо
Люди зі спільноти, викладачів

92
00:04:31,450 --> 00:04:36,420
відомств, персоналу, і обидві
в межах CS50 до

93
00:04:36,420 --> 00:04:37,730
запропонувати проектні ідеї.

94
00:04:37,730 --> 00:04:39,050
Речі, що представляють інтерес для студентських груп.

95
00:04:39,050 --> 00:04:40,600
Речі, що представляють інтерес для відділів.

96
00:04:40,600 --> 00:04:43,990
Так що свою чергу, є, якщо ви боретеся
з невизначеністю щодо того, що ви

97
00:04:43,990 --> 00:04:46,700
самі хотіли б зайнятися.

98
00:04:46,700 --> 00:04:51,760
>> Так останній раз ми ввели можливо
складнішу структуру даних, ніж ми

99
00:04:51,760 --> 00:04:53,300
бачили в минулі тижні.

100
00:04:53,300 --> 00:04:56,550
Ми були досить використанні масивів
щасливо, як корисно, якщо

101
00:04:56,550 --> 00:04:58,160
спрощені структури даних.

102
00:04:58,160 --> 00:05:00,570
Тоді ми ввели ці, які
Звичайно це зв'язкові списки.

103
00:05:00,570 --> 00:05:05,470
І те, що було одним із мотивів для
введення цієї структури даних?

104
00:05:05,470 --> 00:05:06,930
Так?

105
00:05:06,930 --> 00:05:07,250
Що це?

106
00:05:07,250 --> 00:05:08,080
>> АУДИТОРІЯ: динамічні розміри.

107
00:05:08,080 --> 00:05:09,040
>> DAVID мала: динамічні розміри.

108
00:05:09,040 --> 00:05:11,890
Так у той час як в масиві, ви повинні
знаю його розмір заздалегідь, коли

109
00:05:11,890 --> 00:05:12,740
Ви передати його.

110
00:05:12,740 --> 00:05:14,380
У зв'язаному списку, ви не
повинні знати, що.

111
00:05:14,380 --> 00:05:17,610
Ви можете просто Malloc або, більш загально,
виділити додатково

112
00:05:17,610 --> 00:05:20,720
вузла, так би мовити, в будь-який час ви
вставити додаткові дані.

113
00:05:20,720 --> 00:05:22,670
І не вузол без попередньо сенс.

114
00:05:22,670 --> 00:05:25,580
Це всього лише загальний термін, що описує
свого роду контейнер, який ми

115
00:05:25,580 --> 00:05:29,610
використання в нашій структура даних для зберігання
деякий пункт інтересу, який цього

116
00:05:29,610 --> 00:05:31,750
випадку, виявляється, цілих чисел.

117
00:05:31,750 --> 00:05:33,160
>> Але завжди є компроміс.

118
00:05:33,160 --> 00:05:38,070
Отже, ми отримуємо динамічні розміри даних
структури, але яку ціну ми платимо?

119
00:05:38,070 --> 00:05:40,040
Чим недолік пов'язаних списків?

120
00:05:40,040 --> 00:05:41,006
Так?

121
00:05:41,006 --> 00:05:41,980
>> АУДИТОРІЯ: потрібно більше пам'яті.

122
00:05:41,980 --> 00:05:44,240
>> DAVID мала: вона вимагає більше
пам'яті, як саме?

123
00:05:44,240 --> 00:05:46,440
>> АУДИТОРІЯ: [нерозбірливо].

124
00:05:46,440 --> 00:05:47,050
>> DAVID мала: Абсолютно вірно.

125
00:05:47,050 --> 00:05:50,460
Так що тепер ми покажчиків займаючи
додаткову пам'ять, що ми раніше

126
00:05:50,460 --> 00:05:53,040
не потрібні, тому що перевага
масиву, звичайно, є те, що

127
00:05:53,040 --> 00:05:54,860
все в суміжних, спини
щоб спина до спини, яка

128
00:05:54,860 --> 00:05:56,380
дає довільним доступом.

129
00:05:56,380 --> 00:06:00,710
Тому що тільки за допомогою квадратних дужок
позначення, або більш технічно покажчик

130
00:06:00,710 --> 00:06:03,580
арифметика, дуже проста того,
Ви можете отримати доступ до будь-якого

131
00:06:03,580 --> 00:06:05,700
елементів у постійне час.

132
00:06:05,700 --> 00:06:08,975
І справді, це свого роду натяк на
інша ціна, яку ми платимо з

133
00:06:08,975 --> 00:06:09,760
зв'язаний список.

134
00:06:09,760 --> 00:06:13,890
>> Що відбувається з часом роботи
щось на зразок пошуку, якщо я хочу

135
00:06:13,890 --> 00:06:17,270
Наведіть приклад і всередині
зв'язаного списку?

136
00:06:17,270 --> 00:06:20,290
Що значить мій час роботи став?

137
00:06:20,290 --> 00:06:21,560
Big O н.

138
00:06:21,560 --> 00:06:24,060
Якщо він сортується?

139
00:06:24,060 --> 00:06:25,440
Що робити, якщо структура даних розбираються?

140
00:06:25,440 --> 00:06:28,640
Чи можу я зробити краще, ніж великі
О п для пошуку?

141
00:06:28,640 --> 00:06:31,700
Ні, тому що в гіршому випадку він може
дуже добре бути відсортовані, але кількість

142
00:06:31,700 --> 00:06:32,950
Ви шукаєте може бути більшим.

143
00:06:32,950 --> 00:06:35,370
Це може бути номер 100, яка
може статися, що всі

144
00:06:35,370 --> 00:06:36,410
шляху в кінці.

145
00:06:36,410 --> 00:06:39,950
І тому що ви можете отримати доступ тільки до пов'язаних
Список цього здійсненням

146
00:06:39,950 --> 00:06:42,690
шляхи її перший вузол, ти
все ще почасти не пощастило.

147
00:06:42,690 --> 00:06:47,450
Ви повинні пройти все це
від першого до останнього, щоб знайти

148
00:06:47,450 --> 00:06:49,150
що велике значення, як 100.

149
00:06:49,150 --> 00:06:51,350
Або визначити, якщо це
навіть не було.

150
00:06:51,350 --> 00:06:55,960
>> Тому ми не можемо робити те, що алгоритм в даних
структуру, яка виглядає наступним?

151
00:06:55,960 --> 00:06:59,460
Ми не можемо зробити бінарний пошук, тому що
бінарний пошук вимагає, щоб у нас були

152
00:06:59,460 --> 00:07:00,740
довільним доступом.

153
00:07:00,740 --> 00:07:04,500
Ми могли б просто стрибнути з місця на
місці без подальшої

154
00:07:04,500 --> 00:07:07,080
ці хлібні крихти у вигляді
всіх цих покажчиків.

155
00:07:07,080 --> 00:07:08,300
>> Тепер, як ми здійснити це?

156
00:07:08,300 --> 00:07:12,830
Ну, якщо ми йдемо на екран при цьому, якщо
ми можемо швидко перевизначити ці дані

157
00:07:12,830 --> 00:07:13,440
Структура -

158
00:07:13,440 --> 00:07:15,670
мій почерк не все, що
відмінна тут, але ми постараємося.

159
00:07:15,670 --> 00:07:22,030
Так ЬурейеЕ структури, і що я
хочу, щоб ця річ тут?

160
00:07:22,030 --> 00:07:22,960
Node.

161
00:07:22,960 --> 00:07:24,580
Так що я буду приступити до нас.

162
00:07:24,580 --> 00:07:27,860
А тепер, те, що повинно бути всередині
Структура даних для цього окремо

163
00:07:27,860 --> 00:07:28,430
зв'язаний список?

164
00:07:28,430 --> 00:07:29,950
Скільки полів?

165
00:07:29,950 --> 00:07:30,450
>> Так два.

166
00:07:30,450 --> 00:07:31,570
Один з них досить легко.

167
00:07:31,570 --> 00:07:33,050
Так Int N.

168
00:07:33,050 --> 00:07:35,930
І ми могли б назвати N, що ми хочемо,
але вона повинна бути Цілочисельне якщо ми

169
00:07:35,930 --> 00:07:37,660
реалізації зв'язаного списку для цілих чисел.

170
00:07:37,660 --> 00:07:41,920
А тепер що ж другий
поля мають бути?

171
00:07:41,920 --> 00:07:43,460
Struct вузла *.

172
00:07:43,460 --> 00:07:50,570
Тому, якщо я структуру вузла *, а потім я
можна назвати це також те, що хочу,

173
00:07:50,570 --> 00:07:53,510
але тільки бути ясно, що я буду називати
його поруч, як ми робили.

174
00:07:53,510 --> 00:07:55,270
І тоді я закрию фігурні дужки.

175
00:07:55,270 --> 00:08:00,700
>> І тепер, як минулого разу,
Я поклав вузол тут.

176
00:08:00,700 --> 00:08:03,830
Але якщо я оголошую це як
вузла, чому я турбувати бути таким

177
00:08:03,830 --> 00:08:07,320
детальний тут в оголошенні структури
* Наступний вузол, на відміну

178
00:08:07,320 --> 00:08:09,210
просто вузол * наступний?

179
00:08:09,210 --> 00:08:09,904
Так?

180
00:08:09,904 --> 00:08:12,810
>> АУДИТОРІЯ: [нерозбірливо].

181
00:08:12,810 --> 00:08:14,050
>> DAVID мала: Абсолютно вірно.

182
00:08:14,050 --> 00:08:14,530
Саме так.

183
00:08:14,530 --> 00:08:18,320
Оскільки C дійсно приведе вас в прямому і
бачить тільки визначення вузла

184
00:08:18,320 --> 00:08:21,230
дорозі сюди, ви не можете
посилатися на нього тут.

185
00:08:21,230 --> 00:08:24,760
Таким чином, ми маємо таку переважного
Оголошення тут, які за загальним визнанням

186
00:08:24,760 --> 00:08:25,390
більш докладний.

187
00:08:25,390 --> 00:08:27,810
Struct вузол, тобто
тепер ми можемо отримати доступ до нього

188
00:08:27,810 --> 00:08:29,760
внутрішньої структури даних.

189
00:08:29,760 --> 00:08:33,370
>> І, як осторонь, тому що це
стає трохи більше суб'єктивний зараз,

190
00:08:33,370 --> 00:08:36,230
зірки технічно може піти сюди,
він може піти тут, він може

191
00:08:36,230 --> 00:08:37,179
навіть піти в середині.

192
00:08:37,179 --> 00:08:39,890
Ми прийняли, в стилі керівництва для
Звичайно, Конвенція здачі

193
00:08:39,890 --> 00:08:42,299
зірки поруч з даними
тип, який в даному випадку

194
00:08:42,299 --> 00:08:43,460
буде структура вузла.

195
00:08:43,460 --> 00:08:46,620
Але зрозумійте, в багатьох підручниках і
онлайн посилання, ви, можливо, дійсно

196
00:08:46,620 --> 00:08:48,450
побачити його на іншій стороні.

197
00:08:48,450 --> 00:08:52,200
Але так само, як розуміють, що буде насправді
працювати, і ви повинні бути просто

198
00:08:52,200 --> 00:08:52,970
послідовним.

199
00:08:52,970 --> 00:08:53,580
>> Добре.

200
00:08:53,580 --> 00:08:55,630
Так, щоб було нашу заяву
зі структури вузла.

201
00:08:55,630 --> 00:08:59,430
Потім ми почали робити більше
складні речі.

202
00:08:59,430 --> 00:09:03,410
Наприклад, ми вирішили ввести
щось на зразок хеш-таблиці.

203
00:09:03,410 --> 00:09:08,160
Так от хеш-таблицю розміром N,
індексується від 0 у лівому верхньому куті, щоб н

204
00:09:08,160 --> 00:09:09,690
мінус 1 в лівому нижньому кутку.

205
00:09:09,690 --> 00:09:11,640
Це може бути хеш
таблиця на все.

206
00:09:11,640 --> 00:09:15,340
Але які речі ми розмовляли
про використання хеш-таблицю для?

207
00:09:15,340 --> 00:09:18,370
Зберігання Що?

208
00:09:18,370 --> 00:09:18,800
>> Імена.

209
00:09:18,800 --> 00:09:20,870
Ми могли б зробити імена, як
ми зробили минулого разу.

210
00:09:20,870 --> 00:09:22,200
І справді, ви можете зберігати все що завгодно.

211
00:09:22,200 --> 00:09:24,640
І ми побачимо це знову
PHP і JavaScript.

212
00:09:24,640 --> 00:09:28,550
Хеш-таблиці є хорошим роду швейцарських
Армійський ніж, що дозволяє зберігати

213
00:09:28,550 --> 00:09:33,690
майже все, що ви хочете всередині
, Пов'язуючи його зі значеннями ключів.

214
00:09:33,690 --> 00:09:34,770
Ключі з цінностями.

215
00:09:34,770 --> 00:09:37,800
>> Зараз у цьому простому випадку, наші
Ключі просто цифри.

216
00:09:37,800 --> 00:09:40,380
Ми реалізації хеш
таблиці у вигляді масиву.

217
00:09:40,380 --> 00:09:43,500
І так ключі 0,
1, 2, і так далі.

218
00:09:43,500 --> 00:09:47,200
І тому ми, як люди, вирішив у минулому
тижня, що ви знаєте, що, якщо ми

219
00:09:47,200 --> 00:09:50,410
збираєтеся зберігати імена, давайте просто
довільно, але досить розумно,

220
00:09:50,410 --> 00:09:54,680
Припустимо, що Аліса, ім'я,
просто бути проіндексовані на 0.

221
00:09:54,680 --> 00:09:58,030
І Боб, ім'я B, будуть індексуватися
в 1, і так далі.

222
00:09:58,030 --> 00:10:02,490
Так у нас була відповідність між входами,
які є рядками, та хеш

223
00:10:02,490 --> 00:10:04,560
місцях, які є числами.

224
00:10:04,560 --> 00:10:07,740
>> Таким чином, цей процес зазвичай називають
хеш-функції, і ви дійсно можете

225
00:10:07,740 --> 00:10:09,130
реалізувати його в коді.

226
00:10:09,130 --> 00:10:12,080
Якби я хотів реалізувати хеш-функції
, Який робить саме те, що ми

227
00:10:12,080 --> 00:10:17,070
щойно описав в минулий раз, я міг би
оголосити функцію, яка приймає як

228
00:10:17,070 --> 00:10:18,330
вхідного наприклад -

229
00:10:18,330 --> 00:10:22,190
і давайте зробимо це на цьому
Екран тут.

230
00:10:22,190 --> 00:10:26,180
Якби я хотів реалізувати хеш
Функція, я міг би сказати

231
00:10:26,180 --> 00:10:27,410
щось на зразок цього.

232
00:10:27,410 --> 00:10:29,030
>> Це збирається повернутися Int.

233
00:10:29,030 --> 00:10:33,600
Це буде називатися хеш, і це
збирається прийняти в якості аргументу

234
00:10:33,600 --> 00:10:38,920
рядок, або ми можемо бути більш належного зараз,
і сказати, символ *, ми будемо називати його с.

235
00:10:38,920 --> 00:10:43,840
І тоді вся ця функція повинна робити,
У кінцевому рахунку, це повернути Int.

236
00:10:43,840 --> 00:10:45,990
Тепер, як він це робить, що може
Не будь так ясно.

237
00:10:45,990 --> 00:10:49,510
Я збираюся реалізувати це без будь-якого
форма перевірки помилок прямо зараз.

238
00:10:49,510 --> 00:10:55,740
Я просто збираюся сліпо сказати, повернутися
що є під кронштейн з 0, мінус,

239
00:10:55,740 --> 00:10:58,850
скажімо, в столиці коми.

240
00:10:58,850 --> 00:10:59,960
>> Повністю порушена.

241
00:10:59,960 --> 00:11:02,620
Це не ідеально, тому що
Один з них, що, якщо з є недійсним?

242
00:11:02,620 --> 00:11:04,000
Погані речі будуть відбуватися.

243
00:11:04,000 --> 00:11:07,940
Два, що, якщо перша буква в цьому
ім'я не букви?

244
00:11:07,940 --> 00:11:09,860
Це не збирається перетворити
з добре також.

245
00:11:09,860 --> 00:11:11,970
Це може бути малої літери
чи ні лист взагалі.

246
00:11:11,970 --> 00:11:15,520
Так повністю можливості для поліпшення,
але це основна ідея.

247
00:11:15,520 --> 00:11:19,010
>> Те, що ми минулого тижня описав усній формі
просто процес картування Аліса

248
00:11:19,010 --> 00:11:23,360
0 і Боба 1 можуть бути виражені
звичайно, більш formulaically як C

249
00:11:23,360 --> 00:11:24,320
Тут діють.

250
00:11:24,320 --> 00:11:28,630
Зайшов ще хеш, сприймає рядок як
введення, а потім якимось чином робить щось

251
00:11:28,630 --> 00:11:31,020
з цього входу для отримання вихідного.

252
00:11:31,020 --> 00:11:34,130
Не в відміну від нашого чорного полі Опис
що ми давно зробили.

253
00:11:34,130 --> 00:11:36,550
Я не знаю, як це могло б бути
робіт під капотом.

254
00:11:36,550 --> 00:11:40,120
>> Для задачі набір 6, одна з проблем,
для вас, щоб вирішити, що

255
00:11:40,120 --> 00:11:41,920
Чи буде ваш хеш-функція може бути?

256
00:11:41,920 --> 00:11:45,760
Що буде всередині цього чорного
рамки, і, імовірно, це буде

257
00:11:45,760 --> 00:11:50,380
трохи більш цікаво, ніж це, і
безумовно, більш схильні до помилок

258
00:11:50,380 --> 00:11:53,180
перевірок, ніж даний
здійснення.

259
00:11:53,180 --> 00:11:54,580
>> Але можуть виникнути проблеми, чи не так?

260
00:11:54,580 --> 00:11:57,760
Якщо є структура даних, таких як це
Один з них, що одна з проблем

261
00:11:57,760 --> 00:12:01,600
ви можете зіткнутися з плином часу, як ви вставляєте
все більше і більше імен в

262
00:12:01,600 --> 00:12:02,880
хеш-таблиці?

263
00:12:02,880 --> 00:12:04,630
Ви отримуєте зіткнень, чи не так?

264
00:12:04,630 --> 00:12:07,560
Що робити, якщо у вас є Аліса і Аарон,
дві людини, імена яких відбулося

265
00:12:07,560 --> 00:12:08,190
почати з?

266
00:12:08,190 --> 00:12:11,660
То виникає питання, де ви
покласти другий таку назву?

267
00:12:11,660 --> 00:12:15,050
>> Ну, ви можете наївно просто покласти його
де Боб належить, але потім Боб

268
00:12:15,050 --> 00:12:17,300
види різьбових, якщо ви спробуєте
вставити його ім'я поруч і

269
00:12:17,300 --> 00:12:18,240
там немає місця для нього.

270
00:12:18,240 --> 00:12:21,400
Так що ви можете покласти Боб де Чарлі,
і ви можете собі уявити, це дуже швидко

271
00:12:21,400 --> 00:12:23,020
покладених в трохи безлад.

272
00:12:23,020 --> 00:12:25,600
Щось лінійної зрештою, де ви
просто доведеться шукати все це

273
00:12:25,600 --> 00:12:28,190
шукає Алісу або Боба
або Аарона або Чарлі.

274
00:12:28,190 --> 00:12:33,230
>> Так замість цього ми запропонували, а не просто
лінійно зондування для відкритих просторів

275
00:12:33,230 --> 00:12:36,450
і шльоп імена там, ми
запропонував незвичайний підхід.

276
00:12:36,450 --> 00:12:41,740
Хеш-таблиці як і раніше здійснюватиметься з
масив індексів, але тип даних

277
00:12:41,740 --> 00:12:44,500
Зараз ці показники були покажчики.

278
00:12:44,500 --> 00:12:47,360
Покажчики на що?

279
00:12:47,360 --> 00:12:48,730
Покажчики на зв'язані списки.

280
00:12:48,730 --> 00:12:53,330
>> Тому нагадаємо, що зв'язаний список
дійсно тільки покажчик на вузол і

281
00:12:53,330 --> 00:12:57,110
вузол має наступне поле, і вузол
має наступне поле, і так далі.

282
00:12:57,110 --> 00:13:00,690
Так що ви можете думати про це масиві на
лівій стороні хеш-таблицю в якості

283
00:13:00,690 --> 00:13:01,820
провідні на зв'язаний список.

284
00:13:01,820 --> 00:13:07,000
Перевага який, якщо ви отримаєте
зіткнення між Алісою та Аарон,

285
00:13:07,000 --> 00:13:09,300
що ви будете робити з
другої такої людини?

286
00:13:09,300 --> 00:13:14,150
Ви просто прикріпити його або її
Наприкінці, або навіть початок

287
00:13:14,150 --> 00:13:15,490
цього зв'язаний список.

288
00:13:15,490 --> 00:13:17,340
>> А насправді, давайте просто локшини через
, Що лише на одну секунду.

289
00:13:17,340 --> 00:13:18,640
Де б найкраще підходять?

290
00:13:18,640 --> 00:13:22,060
Якщо я вставляю Аліса і вона закінчується на
першого місця, то я намагаюся

291
00:13:22,060 --> 00:13:25,310
вставити ім'я Аарона, і є
Очевидно, зіткнення, я повинен покласти

292
00:13:25,310 --> 00:13:27,400
його на початку
зв'язаного списку?

293
00:13:27,400 --> 00:13:30,944
Ось на цьому першому місці,
або в кінці?

294
00:13:30,944 --> 00:13:31,440
>> АУДИТОРІЯ: [нерозбірливо].

295
00:13:31,440 --> 00:13:31,990
>> DAVID мала: OK.

296
00:13:31,990 --> 00:13:32,490
Я чув починається.

297
00:13:32,490 --> 00:13:33,903
Чому на самому початку?

298
00:13:33,903 --> 00:13:34,750
>> АУДИТОРІЯ: [нерозбірливо].

299
00:13:34,750 --> 00:13:34,940
>> DAVID мала: OK.

300
00:13:34,940 --> 00:13:36,520
Це алфавітний, так що це добре.

301
00:13:36,520 --> 00:13:37,330
Це хороший власності.

302
00:13:37,330 --> 00:13:39,335
Це заощадить мені деякий час потенційно.

303
00:13:39,335 --> 00:13:43,290
Вона не дозволить мені зробити бінарний пошук, але я
може принаймні бути в змозі вирватися з

304
00:13:43,290 --> 00:13:47,340
з циклу, якщо я розумію, ну, я до речі
Аарон минулому були б у такому

305
00:13:47,340 --> 00:13:48,310
відсортований зв'язаний список.

306
00:13:48,310 --> 00:13:50,360
Я не доведеться витрачати свій час, дивлячись
весь шлях до кінця.

307
00:13:50,360 --> 00:13:51,530
Так, що це розумно.

308
00:13:51,530 --> 00:13:54,710
Чому ще може ви хочете вставити
зіштовхуються ім'я в

309
00:13:54,710 --> 00:13:56,660
початок списку?

310
00:13:56,660 --> 00:13:57,397
Що це?

311
00:13:57,397 --> 00:13:58,680
>> АУДИТОРІЯ: [нерозбірливо].

312
00:13:58,680 --> 00:14:00,820
>> DAVID мала: Це може зайняти багато часу,
щоб отримати в кінці списку.

313
00:14:00,820 --> 00:14:02,490
І справді, більше і більше.

314
00:14:02,490 --> 00:14:04,920
Чим більше імен, що ви вставляєте
почати з, тим більше, що

315
00:14:04,920 --> 00:14:06,280
Ланцюг збираєтеся отримати.

316
00:14:06,280 --> 00:14:07,890
Чим довше, що пов'язано
Список збираєтеся отримати.

317
00:14:07,890 --> 00:14:09,420
Значить, ви дійсно просто
витрачаєте свій час.

318
00:14:09,420 --> 00:14:14,070
Може бути, вам краще підтримання
постійний час вставки, Big O 1,

319
00:14:14,070 --> 00:14:18,470
, Завжди поклавши зіштовхуються на ім'я
початку зв'язаного списку,

320
00:14:18,470 --> 00:14:21,230
а не турбуватися стільки
про сортування.

321
00:14:21,230 --> 00:14:22,600
>> Який найкращий відповідь?

322
00:14:22,600 --> 00:14:23,320
Незрозуміло.

323
00:14:23,320 --> 00:14:26,140
Це частково залежить від того,
розподіл, що картина

324
00:14:26,140 --> 00:14:27,850
з імен ви вставляєте.

325
00:14:27,850 --> 00:14:29,430
Це не обов'язково
Очевидна відповідь.

326
00:14:29,430 --> 00:14:33,100
Але ось, знову ж таки,
Дизайн можливість.

327
00:14:33,100 --> 00:14:37,220
>> Таким чином, ми тоді дивилися на цю річ, яка
дійсно інші великі можливості

328
00:14:37,220 --> 00:14:38,180
для р-набір 6.

329
00:14:38,180 --> 00:14:41,770
І зрозумійте, якщо ви ще не зробили,
Zamyla пірнає в обидві ці, хеш

330
00:14:41,770 --> 00:14:43,260
таблиць і спроб, більш докладно.

331
00:14:43,260 --> 00:14:45,630
І відео покрокове керівництво
вбудовані в р-набір спец.

332
00:14:45,630 --> 00:14:46,590
Це було синтаксичного дерева -

333
00:14:46,590 --> 00:14:51,670
Т-Р-І-Е. І те, що було цікаво
це було, що час роботи

334
00:14:51,670 --> 00:14:59,510
пошуку ім'я, як Максвелл
в минулий раз, було великим O чого?

335
00:14:59,510 --> 00:15:01,040
Що це?

336
00:15:01,040 --> 00:15:01,920
>> Аудиторії: кількість букв.

337
00:15:01,920 --> 00:15:02,550
>> DAVID мала: Кількість букв.

338
00:15:02,550 --> 00:15:03,210
Я чув про дві речі.

339
00:15:03,210 --> 00:15:04,630
Кількість листів та постійний час.

340
00:15:04,630 --> 00:15:05,540
Так що давайте йти з цим в першу чергу.

341
00:15:05,540 --> 00:15:06,410
Кількість букв.

342
00:15:06,410 --> 00:15:10,195
Ну, ця структура даних, нагадаємо, є
як дерево, генеалогічне дерево, кожна з

343
00:15:10,195 --> 00:15:12,860
вузли якого складаються з масивів.

344
00:15:12,860 --> 00:15:16,300
А ті масиви покажчиків на
інших подібних вузлів або інших подібних

345
00:15:16,300 --> 00:15:17,670
масивів у дереві.

346
00:15:17,670 --> 00:15:22,890
>> Так що, якщо ми хотіли потім визначити
Чи Максвелл знаходиться тут, я міг би піти

347
00:15:22,890 --> 00:15:26,890
у першому масиві, на самому верху
дерева, так званий корінь, верхній частині

348
00:15:26,890 --> 00:15:30,521
дерева, а потім слідувати за покажчиком м,
Потім покажчик, то х,

349
00:15:30,521 --> 00:15:31,710
W, E, L, L.

350
00:15:31,710 --> 00:15:34,910
А потім, коли я бачу деякі спеціальні символи,
позначається тут як трикутник.

351
00:15:34,910 --> 00:15:38,480
У коді ви побачите, що ми пропонуємо Вам
реалізований як логічний, просто кажу, що так

352
00:15:38,480 --> 00:15:40,540
чи ні, слово закінчується.

353
00:15:40,540 --> 00:15:45,270
>> Ну, раз ми пішли в M-A-X-W-E-L-L,
відчуває, як сім, може бути,

354
00:15:45,270 --> 00:15:48,910
вісім, якщо ми зробимо ще один повз нього, вісім
кроки, щоб знайти Максвелла.

355
00:15:48,910 --> 00:15:53,050
Або назвемо його К. Але згадаймо останній
час, я стверджував, що, якщо є

356
00:15:53,050 --> 00:15:57,540
реально максимальною довжиною по
Словом, як 40 з гаком персонажів,

357
00:15:57,540 --> 00:16:00,810
Максимальна довжина увазі
постійне значення.

358
00:16:00,810 --> 00:16:05,770
Так насправді, так, це технічно Big O
8 або 7, або дійсно великий O К. Але

359
00:16:05,770 --> 00:16:09,420
якщо є кінцева кришка на те, що
K може бути, це константа.

360
00:16:09,420 --> 00:16:12,080
І так це велика О від 1 на
кінці дня.

361
00:16:12,080 --> 00:16:13,040
>> Не в реальному світі.

362
00:16:13,040 --> 00:16:15,960
Не тоді, коли ви насправді почати дивитися
ваш годинник, як працює ваша програми.

363
00:16:15,960 --> 00:16:20,690
Це абсолютно буде трохи
повільніше, ніж дійсно постійної

364
00:16:20,690 --> 00:16:21,840
Час з одного кроку.

365
00:16:21,840 --> 00:16:25,540
Це буде сім або вісім кроків,
але все ж це набагато, набагато краще

366
00:16:25,540 --> 00:16:30,080
, Ніж алгоритм, як Big O п, що
залежить від розміру того, що в

367
00:16:30,080 --> 00:16:31,220
структурі даних.

368
00:16:31,220 --> 00:16:34,970
>> Зверніть увагу на вгору тут ми можемо вставити
ще мільйон імен у цій

369
00:16:34,970 --> 00:16:38,170
Структура даних, але скільки ще кроків
він збирається взяти нас знайти

370
00:16:38,170 --> 00:16:40,480
Максвелл в такому випадку?

371
00:16:40,480 --> 00:16:40,780
Жоден.

372
00:16:40,780 --> 00:16:41,820
Він не впливає.

373
00:16:41,820 --> 00:16:45,480
І на сьогоднішній день, я не думаю, що ми бачили
Приклад структури даних, або

374
00:16:45,480 --> 00:16:48,560
Алгоритм, який був повністю
не залежить від зовнішніх

375
00:16:48,560 --> 00:16:50,040
поведінки, як, що.

376
00:16:50,040 --> 00:16:51,160
Але це не може бути дивним.

377
00:16:51,160 --> 00:16:52,900
Це не може бути єдиним рішенням
для р-набір

378
00:16:52,900 --> 00:16:53,570
>> І це не так.

379
00:16:53,570 --> 00:16:55,980
Це не обов'язково дані
структуру ви повинні тяжіти до,

380
00:16:55,980 --> 00:16:58,220
тому що, як хеш-таблиці, компроміс.

381
00:16:58,220 --> 00:17:00,500
Якою ціною ви платите тут?

382
00:17:00,500 --> 00:17:00,940
Пам'яті.

383
00:17:00,940 --> 00:17:02,890
Я маю на увазі, це звіряче
обсяг пам'яті.

384
00:17:02,890 --> 00:17:05,569
І ви не можете досить побачити його тут, бо
Автор цього знімка

385
00:17:05,569 --> 00:17:09,420
Очевидно, усічений всіх масивів
і ми не бачимо багато і

386
00:17:09,420 --> 00:17:12,700
B і C і Q і Y в
і Z в цих масивах.

387
00:17:12,700 --> 00:17:13,630
Але вони там.

388
00:17:13,630 --> 00:17:17,660
>> Кожен з цих вузлів цілий ряд
від близько 26 або більше байтів, кожен з

389
00:17:17,660 --> 00:17:19,170
яка являє собою літеру.

390
00:17:19,170 --> 00:17:22,920
27 у нашому випадку, так що ми можемо підтримати
апострофа в задачі набору.

391
00:17:22,920 --> 00:17:27,030
Так що ця структура даних дійсно,
дійсно щільна і широка.

392
00:17:27,030 --> 00:17:30,880
І вже одне це може в кінцевому підсумку уповільнення
речі вниз, або принаймні коштувати вам

393
00:17:30,880 --> 00:17:32,240
набагато більше місця.

394
00:17:32,240 --> 00:17:34,020
Але, знову ж, можна зробити
порівняння тут.

395
00:17:34,020 --> 00:17:39,190
>> Нагадаємо, якийсь час назад, ми домоглися багато чого
більш захоплююче час роботи в сортуванні

396
00:17:39,190 --> 00:17:42,880
коли ми використовуємо сортування злиттям, але ціна
ми заплатили, щоб досягти N § п про злиття

397
00:17:42,880 --> 00:17:46,930
Сортувати вимагає, щоб ми витрачаємо
більше, що ресурс?

398
00:17:46,930 --> 00:17:47,690
Більше місця.

399
00:17:47,690 --> 00:17:50,530
Ми потребували масив вторинних
скопіювати людей у, так само, як

400
00:17:50,530 --> 00:17:51,620
ми зробили тут на сцені.

401
00:17:51,620 --> 00:17:55,880
Отже, ще раз, немає явних переможців,
але просто суб'єктивні дизайну

402
00:17:55,880 --> 00:17:57,710
приймати рішення.

403
00:17:57,710 --> 00:17:58,060
>> Добре.

404
00:17:58,060 --> 00:17:59,130
Так як щодо цього?

405
00:17:59,130 --> 00:18:02,050
Будь визнає яких D-Hall?

406
00:18:02,050 --> 00:18:02,440
ОК.

407
00:18:02,440 --> 00:18:03,170
Так три з нас.

408
00:18:03,170 --> 00:18:03,750
Mather будинок.

409
00:18:03,750 --> 00:18:05,070
Так що це для їдальні Мазера.

410
00:18:05,070 --> 00:18:09,650
Б'юся об заклад, всі зали їдальні є
стеки лотки, як це.

411
00:18:09,650 --> 00:18:11,950
І це насправді представник
в те, що ми

412
00:18:11,950 --> 00:18:13,050
очевидно, вже бачили.

413
00:18:13,050 --> 00:18:14,850
Ми назвали її буквально стек.

414
00:18:14,850 --> 00:18:18,970
І в стек, з точки зору вашого
пам'яті комп'ютера, де дані йдуть

415
00:18:18,970 --> 00:18:20,460
в той час як функції при виклику.

416
00:18:20,460 --> 00:18:23,410
>> Наприклад, які речі йдуть
в стеку по відношенню до

417
00:18:23,410 --> 00:18:27,420
Розмітка пам'яті ми обговорювали
тижнів у минулому?

418
00:18:27,420 --> 00:18:28,736
Що це?

419
00:18:28,736 --> 00:18:29,670
>> АУДИТОРІЯ: виклики функцій.

420
00:18:29,670 --> 00:18:30,260
>> DAVID мала: Мені дуже шкода.

421
00:18:30,260 --> 00:18:31,210
>> АУДИТОРІЯ: виклики функцій.

422
00:18:31,210 --> 00:18:33,590
>> DAVID мала: виклики функцій, але
Зокрема, те, що всередині кожного

423
00:18:33,590 --> 00:18:35,340
ці кадри?

424
00:18:35,340 --> 00:18:37,220
Які речі?

425
00:18:37,220 --> 00:18:37,460
Так.

426
00:18:37,460 --> 00:18:38,500
Так що локальні змінні.

427
00:18:38,500 --> 00:18:43,080
У будь-який час ми потребували деякому локальному сховищі,
як аргумент, або INT I, або десяткового

428
00:18:43,080 --> 00:18:45,940
Temp, або будь-який інший місцевий
змінна, ми були

429
00:18:45,940 --> 00:18:47,210
покласти, що в стек.

430
00:18:47,210 --> 00:18:49,610
І ми називаємо це стек, тому що
цього нашарування ідея.

431
00:18:49,610 --> 00:18:52,940
Просто вид матчів з реальністю,
Концепція їх.

432
00:18:52,940 --> 00:18:56,650
>> Але виявляється, що стек може також
розглядатися як структура даних,

433
00:18:56,650 --> 00:19:00,110
Альтернативою масиві, альтернативні
на зв'язаний список.

434
00:19:00,110 --> 00:19:02,770
Щось концептуально більш цікавим
що все ще може бути

435
00:19:02,770 --> 00:19:06,030
реалізовані з використанням будь-якої з цих
речі, але це інший тип

436
00:19:06,030 --> 00:19:09,140
Дані структури підтримки, насправді,
тільки дві операції.

437
00:19:09,140 --> 00:19:11,000
Але ви можете додати на любителя
можливостей, ніж ці.

438
00:19:11,000 --> 00:19:12,180
Але ці основи -

439
00:19:12,180 --> 00:19:13,510
штовхати і поп-музики.

440
00:19:13,510 --> 00:19:19,240
>> А ідея зі стеком в тому, що якщо
маємо тут, з або без Анненберг

441
00:19:19,240 --> 00:19:22,880
знаючи, піднос з сусіднього будинку
з номером 9 на ньому.

442
00:19:22,880 --> 00:19:23,870
Так що просто Int.

443
00:19:23,870 --> 00:19:26,990
І я хочу, щоб натиснути на цю даними
Структура, яка в даний час є порожнім.

444
00:19:26,990 --> 00:19:28,790
Розглянемо в нижній частині стопки.

445
00:19:28,790 --> 00:19:33,150
Я б підштовхнути цей номер 9 на
стек, а тепер це прямо там.

446
00:19:33,150 --> 00:19:36,040
>> Але найцікавіше про стек
тому, що якщо зараз я хочу, щоб підштовхнути

447
00:19:36,040 --> 00:19:40,210
інше значення, як і 17, і я штовхаю
цього в стек, я збираюся зробити

448
00:19:40,210 --> 00:19:43,290
тільки інтуїтивно річ, я просто хочу,
поставити його саме там, де ми, люди,

449
00:19:43,290 --> 00:19:45,180
був би схильний висловився, на вершині.

450
00:19:45,180 --> 00:19:48,850
Але що цікаво зараз
в тому, як я можу отримати в 9?

451
00:19:48,850 --> 00:19:50,670
Ви знаєте, я не без деякого зусилля.

452
00:19:50,670 --> 00:19:54,070
>> Так що цікаво
стек в тому, що дизайн,

453
00:19:54,070 --> 00:19:56,330
це структура даних ЛІФО.

454
00:19:56,330 --> 00:19:59,680
Дурний спосіб опису
останній увійшов, перший вийшов.

455
00:19:59,680 --> 00:20:03,280
Таким чином, останнє число в
в цей час було 17 років.

456
00:20:03,280 --> 00:20:07,540
Так що, якщо я хочу щось від поп
стопки, він може бути тільки 17.

457
00:20:07,540 --> 00:20:11,890
Таким чином, є обов'язковий порядок
операцій тут, де останній елемент

458
00:20:11,890 --> 00:20:14,260
В повинен бути першим одного з них.

459
00:20:14,260 --> 00:20:16,440
Отже акронім, ЛІФО.

460
00:20:16,440 --> 00:20:19,160
>> Так чому це могло б бути корисним?

461
00:20:19,160 --> 00:20:22,690
Чи є їх контексту, в якому потрібно
хочуть структуру даних, як це?

462
00:20:22,690 --> 00:20:24,810
Ну, це, безумовно, корисно
всередині комп'ютера.

463
00:20:24,810 --> 00:20:29,050
Так операційних систем чітко використовувати цю
вид структури даних для стеків.

464
00:20:29,050 --> 00:20:32,800
Ми також побачимо ту ж ідею
коли справа доходить до веб-сторінок.

465
00:20:32,800 --> 00:20:35,890
Так на цьому тижні і на наступному тижні і за її межами,
і, як ви приступити до реалізації веб-

466
00:20:35,890 --> 00:20:39,490
сторінок на мові, званому HTML, Ви можете
фактично використовувати структуру даних, як

467
00:20:39,490 --> 00:20:42,690
це визначити, чи є сторінка
правильно відформатований.

468
00:20:42,690 --> 00:20:47,170
Тому що ми побачимо всі веб-сторінки слід
свого роду ієрархію, відступи

469
00:20:47,170 --> 00:20:52,030
який, врешті-решт, бути
деревовидної структури під капотом.

470
00:20:52,030 --> 00:20:53,620
Так про це трохи пізніше.

471
00:20:53,620 --> 00:20:56,560
>> Але зараз, давайте пропонувати для
моменту, як ми могли б йти про

472
00:20:56,560 --> 00:20:58,830
представляють, що стек?

473
00:20:58,830 --> 00:21:03,370
Дозвольте мені запропонувати, щоб ми здійснили
стек з такою код.

474
00:21:03,370 --> 00:21:07,990
Так стек буде мати всередині нього
дві речі, масив, званий піддони

475
00:21:07,990 --> 00:21:09,510
просто щоб бути у відповідності з демо.

476
00:21:09,510 --> 00:21:12,660
І кожен з елементів у цьому масиві
буде типу Int.

477
00:21:12,660 --> 00:21:14,740
І потужності, мабуть, що?

478
00:21:14,740 --> 00:21:18,796
Тому що я не написав
Повне визначення тут.

479
00:21:18,796 --> 00:21:21,535
>> Це, мабуть, максимально
розмір масиву.

480
00:21:21,535 --> 00:21:25,150
І це, ймовірно, оголошений як різке
визначають у верхній частині файлу, деякі

481
00:21:25,150 --> 00:21:28,450
вид постійної, як випливає з
просто капіталізації.

482
00:21:28,450 --> 00:21:32,250
Таким чином, десь потужність визначається
в якості максимального розміру.

483
00:21:32,250 --> 00:21:35,590
Тим часом, всередині структури даних
відомого як стек там буде

484
00:21:35,590 --> 00:21:38,630
бути цілим числом тільки відомі
просто як розмір.

485
00:21:38,630 --> 00:21:43,400
>> Так що, якщо б я мав представити це зараз
графічно, давайте припустимо, що це

486
00:21:43,400 --> 00:21:48,070
весь чорний прямокутник представляє свій стек.

487
00:21:48,070 --> 00:21:50,070
Всередині це двома змінними.

488
00:21:50,070 --> 00:21:54,780
Так що я збираюся зробити
Перший, як розмір.

489
00:21:54,780 --> 00:21:57,420
А другий я збираюся
залучити у вигляді масиву.

490
00:21:57,420 --> 00:22:01,060
>> Але тільки, щоб тримати речі впорядковано,
Зазвичай я хотів би звернути масив як

491
00:22:01,060 --> 00:22:04,910
це, але це частково добре
якщо ми відповідає дійсності, або

492
00:22:04,910 --> 00:22:06,230
відповідає ментальної моделі.

493
00:22:06,230 --> 00:22:12,880
Отже, дозвольте мені зробити замість масиву
вертикально, який знаходиться всього, знову ж таки,

494
00:22:12,880 --> 00:22:13,840
художника виконання.

495
00:22:13,840 --> 00:22:16,610
Насправді не важливо, що це
знаходиться під капотом.

496
00:22:16,610 --> 00:22:20,350
І ми будемо говорити, що, за замовчуванням,
потужність буде три.

497
00:22:20,350 --> 00:22:23,480
Так що це буде розташування 0, то це
буде номером 1, це

498
00:22:23,480 --> 00:22:25,740
буде розташований в 2.

499
00:22:25,740 --> 00:22:29,330
>> Якби я з підкупити стрес м'яч, не так
хтось хотів, щоб придумати і запустити

500
00:22:29,330 --> 00:22:30,870
борту тут на мить?

501
00:22:30,870 --> 00:22:31,960
Добре, бачив вашу руку першим.

502
00:22:31,960 --> 00:22:33,950
Піднімайся.

503
00:22:33,950 --> 00:22:36,500
Добре.

504
00:22:36,500 --> 00:22:38,760
Так що я вважаю, що це Стівен.

505
00:22:38,760 --> 00:22:40,035
Піднімайся.

506
00:22:40,035 --> 00:22:40,770
Добре.

507
00:22:40,770 --> 00:22:46,760
>> Але припустимо, що тепер ми перемотати на початковому
стан світу, де я

508
00:22:46,760 --> 00:22:52,180
щойно оголосив стека, і це
буде потужністю три.

509
00:22:52,180 --> 00:22:54,470
Однак розмір ще не визначений.

510
00:22:54,470 --> 00:22:56,100
Лотки ще не був визначений.

511
00:22:56,100 --> 00:22:57,300
Таким чином, кілька питань у першу чергу.

512
00:22:57,300 --> 00:23:01,310
І дозвольте мені дати вам мікрофон, щоб ви могли
активнішу участь в цьому.

513
00:23:01,310 --> 00:23:05,190
>> Так що ж знаходиться усередині розмір в даний момент
в строк, якщо все, що я зробив,

514
00:23:05,190 --> 00:23:09,340
заявив стек з
одного рядка коду?

515
00:23:09,340 --> 00:23:10,100
>> Стівен: Не так багато.

516
00:23:10,100 --> 00:23:12,080
>> DAVID мала: Добре, не так багато.

517
00:23:12,080 --> 00:23:14,410
Чи знаємо ми, що всередині розмір,
ми знаємо, що всередині

518
00:23:14,410 --> 00:23:16,330
цього масиву тут?

519
00:23:16,330 --> 00:23:18,630
>> Стівен: Просто випадковий код, вірно?

520
00:23:18,630 --> 00:23:20,220
Просто -

521
00:23:20,220 --> 00:23:23,230
>> DAVID мала: Так, я збираюся
називають це код, але випадкових -

522
00:23:23,230 --> 00:23:23,820
>> Стівен: Речей.

523
00:23:23,820 --> 00:23:28,290
>> DAVID мала: Такі речі, як випадкова

524
00:23:28,290 --> 00:23:28,870
>> Стівен: біт.

525
00:23:28,870 --> 00:23:29,530
>> DAVID мала: біти, так?

526
00:23:29,530 --> 00:23:31,190
Так сміття значення, вірно?

527
00:23:31,190 --> 00:23:33,470
Так перестановки з 0 і 1 в.

528
00:23:33,470 --> 00:23:35,920
Залишки попередніх випадках використання
цієї пам'яті.

529
00:23:35,920 --> 00:23:38,150
І ми дійсно не знаємо, які саме значення
які, таким чином, ми, як правило залучити їх

530
00:23:38,150 --> 00:23:38,930
у вигляді знаків питання.

531
00:23:38,930 --> 00:23:41,990
>> Тому перше, що ми мабуть
збирається хочете зробити тут -

532
00:23:41,990 --> 00:23:46,630
і дозвольте мені дати це поле всередині
звідти назва - лотки.

533
00:23:46,630 --> 00:23:49,540
Що ми повинні імовірно ініціалізації
розмір, якщо ми хочемо

534
00:23:49,540 --> 00:23:51,040
почати використовувати цей стек?

535
00:23:51,040 --> 00:23:53,070
>> Стівен: Лоток 3 до півдня.

536
00:23:53,070 --> 00:23:53,910
>> DAVID мала: Так, добре.

537
00:23:53,910 --> 00:23:56,710
Щоб було ясно, потужністю оголошений
в іншому місці, як три.

538
00:23:56,710 --> 00:23:58,570
І ось що я використовував
виділити масиву.

539
00:23:58,570 --> 00:24:03,535
Розмір збирається звернутися до скільки
Лотки даний момент в стек.

540
00:24:03,535 --> 00:24:03,880
>> Стівен: Нуль.

541
00:24:03,880 --> 00:24:04,460
>> DAVID мала: Так воно і має дорівнювати нулю.

542
00:24:04,460 --> 00:24:07,760
Так що вперед, і з будь-яким пальцем,
намалювати нуля в розмірах.

543
00:24:07,760 --> 00:24:08,440
Добре.

544
00:24:08,440 --> 00:24:10,920
Так що тепер, що всередині цього
тут, ми не знаємо.

545
00:24:10,920 --> 00:24:12,160
Це дійсно просто значення сміття.

546
00:24:12,160 --> 00:24:14,800
Так ми змогли залучити знаки питання, але
Давайте тримати раду чистими поки

547
00:24:14,800 --> 00:24:16,300
тому що це не має значення
що там.

548
00:24:16,300 --> 00:24:19,130
Нам не потрібно для ініціалізації масиву
ні до чого, тому що, якщо ми знаємо, що

549
00:24:19,130 --> 00:24:23,100
розмір стека дорівнює нулю, а ми
Не слід дивитися на що-небудь в

550
00:24:23,100 --> 00:24:25,590
цей масив в усякому разі у
даний момент часу.

551
00:24:25,590 --> 00:24:29,970
>> Тепер припустимо, що я натискаю
9 числа в стек.

552
00:24:29,970 --> 00:24:33,750
Як ми повинні оновити структуру даних
всередині цього чорного ящика?

553
00:24:33,750 --> 00:24:35,540
Які цінності потрібно змінити?

554
00:24:35,540 --> 00:24:36,200
>> Стівен: В -

555
00:24:36,200 --> 00:24:37,400
розмір?

556
00:24:37,400 --> 00:24:37,650
>> DAVID мала: OK.

557
00:24:37,650 --> 00:24:38,770
Розмір має стати те, що?

558
00:24:38,770 --> 00:24:39,580
>> Стівен: розмір має бути один.

559
00:24:39,580 --> 00:24:39,870
>> DAVID мала: OK.

560
00:24:39,870 --> 00:24:41,110
Отже розмір повинен стати одним.

561
00:24:41,110 --> 00:24:42,540
Таким чином, ви можете зробити це в кілька способів.

562
00:24:42,540 --> 00:24:46,920
Дозвольте мені дати вам, тепер ваша
палець ластик.

563
00:24:46,920 --> 00:24:47,260
Добре.

564
00:24:47,260 --> 00:24:49,960
Тоді зараз пальця кисті.

565
00:24:49,960 --> 00:24:50,330
Добре.

566
00:24:50,330 --> 00:24:52,820
А тепер, що ще має змінитися,
очевидно, що в структурі даних?

567
00:24:52,820 --> 00:24:57,060
>> Стівен: Ми збираємося від
знизу вгору до 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID мала: 9.

569
00:24:57,760 --> 00:24:58,420
ОК, добре.

570
00:24:58,420 --> 00:25:01,550
Так до сих пір не має значення, що поставлено на
місце розташування одного або двох, тому що вони

571
00:25:01,550 --> 00:25:04,520
сміття значення, але ми не повинні турбуватися
шукає там, тому що розмір

572
00:25:04,520 --> 00:25:07,540
говорить нам, що тільки перший елемент
насправді законно.

573
00:25:07,540 --> 00:25:10,400
Так що тепер я натискаю на 17 списку.

574
00:25:10,400 --> 00:25:11,830
Що відбувається з цією картиною?

575
00:25:11,830 --> 00:25:14,720
>> Стівен: Так розмір буде йти до двох.

576
00:25:14,720 --> 00:25:15,300
>> DAVID мала: OK.

577
00:25:15,300 --> 00:25:16,070
Ти ластик -

578
00:25:16,070 --> 00:25:16,810
Ой.

579
00:25:16,810 --> 00:25:18,026
Ти ластик.

580
00:25:18,026 --> 00:25:18,840
>> Стівен: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID мала: Ти кисті.

582
00:25:19,720 --> 00:25:20,560
>> Стівен: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID мала: OK.

584
00:25:20,920 --> 00:25:21,600
А що ще?

585
00:25:21,600 --> 00:25:22,600
>> Стівен: І тоді ми -

586
00:25:22,600 --> 00:25:22,915
>> DAVID мала: Ми висунули 17.

587
00:25:22,915 --> 00:25:24,760
>> Стівен: Ми дотримуємося 17 зверху, а значить -

588
00:25:24,760 --> 00:25:25,710
>> DAVID мала: Добре, добре.

589
00:25:25,710 --> 00:25:27,040
>> Стівен: - помістіть його вниз.

590
00:25:27,040 --> 00:25:27,530
>> DAVID мала: Добре.

591
00:25:27,530 --> 00:25:27,940
Це стає легко.

592
00:25:27,940 --> 00:25:29,300
Я не збираюся, щоб допомогти вам у цей раз.

593
00:25:29,300 --> 00:25:30,510
Натисніть 22.

594
00:25:30,510 --> 00:25:31,720
>> Стівен: Готово.

595
00:25:31,720 --> 00:25:34,870
Стати ластик.

596
00:25:34,870 --> 00:25:37,340
Я стаю кисті.

597
00:25:37,340 --> 00:25:39,340
І тоді я ставлю 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID мала: 22.

599
00:25:40,100 --> 00:25:40,620
Відмінно.

600
00:25:40,620 --> 00:25:41,380
Так що ще раз.

601
00:25:41,380 --> 00:25:44,280
Я тепер збираюся натиснути
стек 26.

602
00:25:44,280 --> 00:25:46,350
>> Стівен: Ох.

603
00:25:46,350 --> 00:25:50,278
О, чорт візьми.

604
00:25:50,278 --> 00:25:52,520
Ви дійсно застало мене зненацька.

605
00:25:52,520 --> 00:25:53,703
>> DAVID мала: Ви не зробили
це передбачити?

606
00:25:53,703 --> 00:25:55,930
>> Стівен: Я не бачив цього чекати.

607
00:25:55,930 --> 00:25:58,756
Чи можемо ми повторно Первинна потужність?

608
00:25:58,756 --> 00:25:59,790
>> DAVID мала: Це хороше запитання.

609
00:25:59,790 --> 00:26:02,360
Отже, у нас вид пофарбовані себе
в кутку тут.

610
00:26:02,360 --> 00:26:06,740
Там дійсно нічого хорошого за Стівен
тому що у нас виділено в цьому масиві

611
00:26:06,740 --> 00:26:09,130
статично, так би мовити, всередині
структури даних.

612
00:26:09,130 --> 00:26:12,170
І ми по суті жорстко
це буде розміром три.

613
00:26:12,170 --> 00:26:14,170
Так що ми не можемо звільнити його.

614
00:26:14,170 --> 00:26:20,020
>> Ми могли б, якби ми повернулися, ми
переглянув лотки бути покажчик, який

615
00:26:20,020 --> 00:26:22,300
потім ми використовуємо Malloc в руки пам'яті.

616
00:26:22,300 --> 00:26:25,050
Тому що, якщо ми отримали від пам'яті
через купу Malloc, ми

617
00:26:25,050 --> 00:26:26,430
могли б звільнити його.

618
00:26:26,430 --> 00:26:29,630
Але перед звільненням, ми могли б
перерозподілити більший шматок пам'яті,

619
00:26:29,630 --> 00:26:31,330
оновити покажчик, і так далі.

620
00:26:31,330 --> 00:26:33,500
Але на сьогоднішній день, це дійсно
що ми можемо зробити.

621
00:26:33,500 --> 00:26:36,360
Натисніть і поп, імовірно, збирався
мати, щоб сигналізувати деякі помилки.

622
00:26:36,360 --> 00:26:40,270
>> Так, наприклад, наша реалізація
поштовх може повернутися BOOL які

623
00:26:40,270 --> 00:26:42,390
повернутий раніше правда, правда, правда.

624
00:26:42,390 --> 00:26:48,390
Але в четвертий раз, він буде мати
повернутися помилковим, наприклад.

625
00:26:48,390 --> 00:26:48,540
Добре.

626
00:26:48,540 --> 00:26:49,540
Дуже добре зроблено.

627
00:26:49,540 --> 00:26:50,060
Поздравляю.

628
00:26:50,060 --> 00:26:52,160
Ви заробили свій стрес м'яч сьогодні.

629
00:26:52,160 --> 00:26:53,110
>> [Оплески]

630
00:26:53,110 --> 00:26:54,382
>> Стівен: Спасибо.

631
00:26:54,382 --> 00:26:55,680
>> DAVID мала: Спасибо.

632
00:26:55,680 --> 00:26:59,740
Отже, це, здається, не так багато
з крок вперед, чи не так?

633
00:26:59,740 --> 00:27:01,410
Ми описали цю структуру даних.

634
00:27:01,410 --> 00:27:02,320
Це було переконливим, чи не так?

635
00:27:02,320 --> 00:27:03,200
Операційні системи подобається.

636
00:27:03,200 --> 00:27:06,360
Мабуть в Інтернеті може скористатися цим,
та інших програм на місці.

637
00:27:06,360 --> 00:27:10,870
Але те, що дурні обмеження, що ми
повернутися до роду тижня дві межі

638
00:27:10,870 --> 00:27:12,880
де ми зафіксували розмір масивів.

639
00:27:12,880 --> 00:27:15,010
>> Таким чином, є справді пара
способи, якими ми могли б вирішити цю.

640
00:27:15,010 --> 00:27:18,750
Ми могли динамічно виділяти масив,
не жорстка кодування це, як я

641
00:27:18,750 --> 00:27:22,600
зроблено тут, але замість повторного оголошення
це, просто щоб було ясно, як

642
00:27:22,600 --> 00:27:23,830
щось на зразок цього.

643
00:27:23,830 --> 00:27:29,040
Лотки Int *, не наважуючись
на працездатність ще.

644
00:27:29,040 --> 00:27:35,460
Але коли я заявляю стека в іншому місці
в моєму коді, я міг би назвати Malloc,

645
00:27:35,460 --> 00:27:38,250
отримати адресу шматок
пам'яті, і я міг призначити

646
00:27:38,250 --> 00:27:39,980
ця адреса лотків.

647
00:27:39,980 --> 00:27:43,340
>> І потім, тому що це просто шматок
пам'яті, я міг би продовжувати використовувати квадратні

648
00:27:43,340 --> 00:27:45,450
дужок у звичайному порядку.

649
00:27:45,450 --> 00:27:49,020
Бо знову ж, на зразок цього
функціональний еквівалент масиви і

650
00:27:49,020 --> 00:27:50,820
ділянки пам'яті, які приходять
назад від Malloc.

651
00:27:50,820 --> 00:27:53,090
Ми можемо ставитися один, як і інші
використанням арифметики покажчиків або

652
00:27:53,090 --> 00:27:54,440
квадратних позначення кронштейна.

653
00:27:54,440 --> 00:27:55,660
Так що це один підхід.

654
00:27:55,660 --> 00:28:00,120
>> Але як ще ми можемо реалізувати цю
ту ж структуру даних, потенційно?

655
00:28:00,120 --> 00:28:00,280
Вірно?

656
00:28:00,280 --> 00:28:04,530
Я відчуваю, що ми просто вирішили цю
проблеми, як тиждень тому.

657
00:28:04,530 --> 00:28:08,860
Те, що було рішення цієї проблеми
що Стівен зіткнувся?

658
00:28:08,860 --> 00:28:10,370
Так зв'язані списки, мають рацію.

659
00:28:10,370 --> 00:28:13,410
>> Якщо проблема в тому, що ми фарбуємо
себе в кут, виділивши

660
00:28:13,410 --> 00:28:17,580
Заздалегідь занадто мало пам'яті, що ми
тоді доведеться якось мати справу з, ну,

661
00:28:17,580 --> 00:28:19,880
Чому б просто не уникнути
питання взагалі?

662
00:28:19,880 --> 00:28:26,170
Чому б просто не оголосити лотки бути
покажчик на вузол, ERGO зв'язаний список,

663
00:28:26,170 --> 00:28:30,740
і потім виділити нові вузли
кожен раз, коли Стівен необхідні, щоб відповідати

664
00:28:30,740 --> 00:28:32,400
число в структуру даних.

665
00:28:32,400 --> 00:28:34,200
>> Таким чином, картина повинна змінитися.

666
00:28:34,200 --> 00:28:38,220
Це не буде так чисто і, як
просто, як тільки масив з трьох цілих чисел.

667
00:28:38,220 --> 00:28:42,970
Тепер це буде вказівник на
структури, і що структура збирається

668
00:28:42,970 --> 00:28:44,830
є Цілочисельне і наступний покажчик.

669
00:28:44,830 --> 00:28:47,670
Це буде вести через цей покажчик
в іншу таку структуру, щоб

670
00:28:47,670 --> 00:28:48,600
іншої такої структури.

671
00:28:48,600 --> 00:28:50,560
Таким чином, картина була б насправді
отримати трохи брудніше.

672
00:28:50,560 --> 00:28:52,950
І ми б стрілки пов'язуючи
всі разом.

673
00:28:52,950 --> 00:28:55,280
>> Але це нормально, правильно, тому що
ми бачили, як це зробити.

674
00:28:55,280 --> 00:28:58,180
І як тільки ви звикнете
створюєте щось на зразок пов'язаного

675
00:28:58,180 --> 00:29:01,450
список, який ви повинні будете зробити, якщо Ви
вибрати для реалізації хеш-таблицю з

676
00:29:01,450 --> 00:29:05,120
роздільне зв'язування для р-набір 6, ви можете
використовувати його в якості будівельного блоку, або

677
00:29:05,120 --> 00:29:08,870
інгредієнта або в подряпин говорять,
процедури, то, що ви поклали, ви

678
00:29:08,870 --> 00:29:12,560
створили свій власний шматочок пазла
, Який потім можна використовувати повторно.

679
00:29:12,560 --> 00:29:17,090
Так компроміси, але потенційні рішення
що ми насправді бачив раніше.

680
00:29:17,090 --> 00:29:20,560
>> Так досить часто, ви бачите це кожен
рік або два, коли Apple випустила

681
00:29:20,560 --> 00:29:23,060
щось нове, і всі божевільні люди
лінія за межами Apple,

682
00:29:23,060 --> 00:29:27,050
магазин, щоб купити їх граничні
оновити на обладнанні.

683
00:29:27,050 --> 00:29:30,420
Я говорю про це, це нормально, тому що
Я один з тих людей.

684
00:29:30,420 --> 00:29:35,140
Так які структури даних
може представляти цю реальність?

685
00:29:35,140 --> 00:29:36,980
>> Ну, давайте назвемо це черги, лінія.

686
00:29:36,980 --> 00:29:40,270
Так англійці називають це зазвичай
Черга в кожному разі, так що це хороше ім'я.

687
00:29:40,270 --> 00:29:44,960
І дві операції, які чергу
повинна підтримувати ми будемо називати Enqueue

688
00:29:44,960 --> 00:29:48,900
операції та операції з черги,
які схожі за

689
00:29:48,900 --> 00:29:50,120
духу натиснути і поп-музики.

690
00:29:50,120 --> 00:29:54,060
Це просто як би в різних
Конвенції, те, що ми називаємо цим.

691
00:29:54,060 --> 00:29:57,680
Але для постановки в чергу щось означає, додати
або вставити його в структурі даних.

692
00:29:57,680 --> 00:29:59,570
Щоб з черги означає, щоб видалити його.

693
00:29:59,570 --> 00:30:05,170
Але в той час був стек даних LIFO
структурі черги в першій,

694
00:30:05,170 --> 00:30:06,740
перший із структури даних.

695
00:30:06,740 --> 00:30:10,050
>> Якщо ви перший чоловік у черзі,
Ви будете першою людиною, щоб отримати

696
00:30:10,050 --> 00:30:12,420
з лінії і купити новий пристрій.

697
00:30:12,420 --> 00:30:18,070
Уявіть собі, як розлад ці люди були б
Якщо Apple, замість цього використовували стек, для

698
00:30:18,070 --> 00:30:21,250
Наприклад, для здійснення вибору
до вашої нової іграшкою.

699
00:30:21,250 --> 00:30:24,310
Так черг сенсу, звичайно, і
ми можемо думати про всякі

700
00:30:24,310 --> 00:30:27,480
додатків, мабуть, для черг,
особливо якщо ви хочете справедливості.

701
00:30:27,480 --> 00:30:30,040
Отже, як ми могли б реалізувати ці
в якості структури даних?

702
00:30:30,040 --> 00:30:33,680
>> Ну, я пропоную, щоб ми могли
потрібно зробити це таким чином.

703
00:30:33,680 --> 00:30:35,225
Так що я збираюся зараз мають номери.

704
00:30:35,225 --> 00:30:38,190
Таким чином, ми будемо тримати його простим і не
обов'язково говорити з точки зору лотків.

705
00:30:38,190 --> 00:30:40,220
Просто числа, які народ отримав.

706
00:30:40,220 --> 00:30:43,760
Ємність збирається, знову ж, виправити
загальна кількість людей, які можуть бути в

707
00:30:43,760 --> 00:30:46,900
цієї лінії, а три або
будь-які інші значення.

708
00:30:46,900 --> 00:30:50,760
>> Але я пропоную, що мені потрібно, щоб відстежувати
не тільки розмір

709
00:30:50,760 --> 00:30:52,370
Черга, як багато речей у ньому.

710
00:30:52,370 --> 00:30:56,310
Тому розмір поточного розміру, потужності
це максимальний розмір.

711
00:30:56,310 --> 00:30:58,540
Просто ще раз, номенклатура
Відповідно до угоди.

712
00:30:58,540 --> 00:31:03,680
Навіщо мені потрібен додатковий десяткового всередині
черзі, щоб відстежувати, хто знаходиться в

713
00:31:03,680 --> 00:31:05,365
передній лінії?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Чому я повинен це робити в цьому випадку?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Ну, як ця картина
збираюся міняти?

718
00:31:16,190 --> 00:31:19,280
Я, ймовірно, може повторно найбільш
цієї картини.

719
00:31:19,280 --> 00:31:21,480
Дозвольте мені йти вперед і стерти те, що тут.

720
00:31:21,480 --> 00:31:24,580
Ми дамо цим трохи
інше ім'я тут.

721
00:31:24,580 --> 00:31:28,930
Давайте позбутися 17, давайте позбудемося
з 9, давайте позбавлятися від 3.

722
00:31:28,930 --> 00:31:30,410
І давайте додамо ще одну річ.

723
00:31:30,410 --> 00:31:34,710
Я вважаю, що мені потрібно стежити за
передньої частини списку, який є тільки

724
00:31:34,710 --> 00:31:35,570
буде ІНТАС добре.

725
00:31:35,570 --> 00:31:36,550
І ми збираємося зробити його простим.

726
00:31:36,550 --> 00:31:37,740
Немає пов'язаного списку на даний момент.

727
00:31:37,740 --> 00:31:40,900
>> Ми визнаємо, що ми збираємося
натикаються на це обмеження.

728
00:31:40,900 --> 00:31:43,720
Але те, що я хочу бачити
на цей раз?

729
00:31:43,720 --> 00:31:47,240
Отже, нехай я йду вперед і першим
Людина приходить в лінію, а

730
00:31:47,240 --> 00:31:48,560
це число 9.

731
00:31:48,560 --> 00:31:49,680
У нас є стрес куль.

732
00:31:49,680 --> 00:31:51,330
Чи можу я вкрасти, скажімо, два або три людини?

733
00:31:51,330 --> 00:31:52,690
Один, два, три?

734
00:31:52,690 --> 00:31:53,120
Піднімайся.

735
00:31:53,120 --> 00:31:56,022
Прямо з фронту, тому що
ми будемо робити це одним швидким.

736
00:31:56,022 --> 00:31:59,415
>> Кожен з вас тепер буде
Вентилятор хлопчика в черзі в Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Ви не будете отримувати Apple Hardware
В кінці цього ж.

739
00:32:06,210 --> 00:32:06,500
Добре.

740
00:32:06,500 --> 00:32:09,430
Значить, ти номер 9, ви
№ 17, № 22.

741
00:32:09,430 --> 00:32:12,130
Ці довільні числа, наприклад,
Студент ідентифікатори і ще багато чого.

742
00:32:12,130 --> 00:32:14,550
І через хвилину, давайте почнемо
, Щоб почати додавати речей.

743
00:32:14,550 --> 00:32:16,000
І я побіжу борту тут на цей раз.

744
00:32:16,000 --> 00:32:19,570
>> Так що в цьому випадку я ініціалізувати
передньої бути -

745
00:32:19,570 --> 00:32:22,380
Я насправді не все одно, що
фронт, так як розмір дорівнює нулю.

746
00:32:22,380 --> 00:32:24,480
Так що це може також просто
бути знаком питання.

747
00:32:24,480 --> 00:32:26,170
Всі ці знаки питання.

748
00:32:26,170 --> 00:32:29,880
Так що тепер ми почнемо реально побачити деякі
люди шикуються в чергу в магазині.

749
00:32:29,880 --> 00:32:33,320
>> Таким чином, якщо число 9, ти перша
там в 5 ранку, йти вперед і шикуються в чергу,

750
00:32:33,320 --> 00:32:34,210
або напередодні ввечері.

751
00:32:34,210 --> 00:32:34,580
ОК.

752
00:32:34,580 --> 00:32:35,940
Так що тепер тут 9.

753
00:32:35,940 --> 00:32:37,940
Так 9 знаходиться на початку списку.

754
00:32:37,940 --> 00:32:41,440
Так що я збираюся йти вперед і поновлення
Розмір цього поточні дані

755
00:32:41,440 --> 00:32:44,740
структури, щоб не бути більше 0,
але рівним 1.

756
00:32:44,740 --> 00:32:47,630
Я збираюся поставити на 9
перед списком.

757
00:32:47,630 --> 00:32:51,020
Дозвольте мені йти вперед і перемикання екрану
так що ми можемо бачити минуле з нами тут.

758
00:32:51,020 --> 00:32:53,220
>> А тепер що я хочу
поставити на фронт?

759
00:32:53,220 --> 00:32:56,240
Я буду відслідковувати, що
початку черги зараз

760
00:32:56,240 --> 00:32:58,570
знаходиться в місці розташування 0.

761
00:32:58,570 --> 00:33:00,510
Бо далі буде?

762
00:33:00,510 --> 00:33:03,000
Ну, припустимо, що тепер я поставити в чергу
17, а.

763
00:33:03,000 --> 00:33:04,510
Так що стрибати в лінію там.

764
00:33:04,510 --> 00:33:07,060
І знову ж, начебто двері
Магазин буде тут.

765
00:33:07,060 --> 00:33:08,700
Так що тепер я додав 17.

766
00:33:08,700 --> 00:33:10,810
І хоча ці хлопці блокують
екрану, це нормально,

767
00:33:10,810 --> 00:33:12,300
тому що ми бачимо це тут.

768
00:33:12,300 --> 00:33:12,910
Вибачте.

769
00:33:12,910 --> 00:33:13,810
>> АУДИТОРІЯ: Ми можемо рухатися -

770
00:33:13,810 --> 00:33:14,660
>> DAVID мала: Ні, це нормально.

771
00:33:14,660 --> 00:33:16,000
Це величезний там.

772
00:33:16,000 --> 00:33:18,580
Так 17 тепер всередині черги.

773
00:33:18,580 --> 00:33:21,332
Мені потрібно оновлення, яке
полів зараз, хоча?

774
00:33:21,332 --> 00:33:23,210
Добре, безумовно розміру.

775
00:33:23,210 --> 00:33:26,430
А як щодо фронту?

776
00:33:26,430 --> 00:33:27,040
ОК, немає.

777
00:33:27,040 --> 00:33:30,200
Передня не повинна змінитися, оскільки
На відміну від стека, ми

778
00:33:30,200 --> 00:33:31,370
хочуть зберегти справедливість.

779
00:33:31,370 --> 00:33:35,150
Так що якщо 9 вийшов на перше, ми хочемо, 9
бути першою з лінії

780
00:33:35,150 --> 00:33:36,420
і в магазин.

781
00:33:36,420 --> 00:33:37,220
>> Справді, давайте подивимося, що.

782
00:33:37,220 --> 00:33:42,235
Перед тим, як вставити 22, давайте
йти вперед і Dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Як тебе звуть?

784
00:33:42,970 --> 00:33:43,680
>> АУДИТОРІЯ: Джейк.

785
00:33:43,680 --> 00:33:45,440
>> DAVID мала: Джейк збирається
бути видалена з черги зараз.

786
00:33:45,440 --> 00:33:48,050
Таким чином, ви добираєтеся, щоб йти в магазин.

787
00:33:48,050 --> 00:33:49,880
І робити вигляд, що в магазині
он там.

788
00:33:49,880 --> 00:33:51,970
Так що тепер потрібно, - ДІТ-ДІТ-дит!

789
00:33:51,970 --> 00:33:53,400
Що має статися зараз?

790
00:33:53,400 --> 00:33:54,490
Дизайн рішення.

791
00:33:54,490 --> 00:33:56,825
Так не поганий інстинкт, але -
як тебе звати?

792
00:33:56,825 --> 00:33:57,090
>> АУДИТОРІЯ: Девід.

793
00:33:57,090 --> 00:33:57,500
>> DAVID мала: Девід.

794
00:33:57,500 --> 00:33:58,810
Отже, що зробив Давид?

795
00:33:58,810 --> 00:34:02,590
Він намагався виправити сортувати дані
Структура і перейти від його розташування

796
00:34:02,590 --> 00:34:04,100
в колишньому місці Джейка.

797
00:34:04,100 --> 00:34:06,740
І це прекрасно, якщо ми готові
визнати, що, як

798
00:34:06,740 --> 00:34:08,199
деталь реалізації.

799
00:34:08,199 --> 00:34:11,100
Але спочатку, давайте оновимо дані
структури, перш ніж робити це.

800
00:34:11,100 --> 00:34:14,139
Тому що я не подобається ідея всіх
люди зрушення в цій лінії.

801
00:34:14,139 --> 00:34:17,360
>> Це не страшно, якщо Девід робить це з
один крок, але знову ж, згадайте

802
00:34:17,360 --> 00:34:20,360
, Коли у нас було вісім добровольців по
етапі, і ми зробили, як вставки

803
00:34:20,360 --> 00:34:22,600
Сортування, де ми повинні були почати
переміщення всіх навколо.

804
00:34:22,600 --> 00:34:23,790
Тобто дороги, чи не так?

805
00:34:23,790 --> 00:34:28,330
Це змушує мене зіщулитися про Big O
п, Big O п квадрат знову.

806
00:34:28,330 --> 00:34:30,650
Це не почуття, як
ідеальний результат.

807
00:34:30,650 --> 00:34:32,080
>> Так що давайте просто оновлювати це.

808
00:34:32,080 --> 00:34:35,120
Таким чином, розмір черги
більше не є 2.

809
00:34:35,120 --> 00:34:37,090
Це тепер просто 1.

810
00:34:37,090 --> 00:34:40,360
Але тепер я можу щось оновити
Я не оновлювалася раніше,

811
00:34:40,360 --> 00:34:41,130
перед списком.

812
00:34:41,130 --> 00:34:45,420
Я міг би просто сказати, що розташування 1?

813
00:34:45,420 --> 00:34:49,770
Так що тепер у нас є сміття цінність тут,
сміття значення тут, і Девід в

814
00:34:49,770 --> 00:34:51,469
середині цього сміття.

815
00:34:51,469 --> 00:34:54,980
Проте структура даних
як і раніше недоторканими.

816
00:34:54,980 --> 00:34:58,540
>> І справді, я навіть не потрібно
змінити колишній номер Джейка

817
00:34:58,540 --> 00:35:00,460
9, тому що, хто піклується.

818
00:35:00,460 --> 00:35:04,470
У мене є достатньо інформації, в даний час в
розміру, що я знаю, що є одна людина в

819
00:35:04,470 --> 00:35:05,030
цієї черги.

820
00:35:05,030 --> 00:35:08,340
І я знаю, що ця людина
знаходиться в місці розташування 1, а не 0.

821
00:35:08,340 --> 00:35:09,760
Я не розраховую.

822
00:35:09,760 --> 00:35:11,300
Таким чином, 1, а також.

823
00:35:11,300 --> 00:35:13,410
Так що дані структури все ще добре.

824
00:35:13,410 --> 00:35:14,330
>> Ну, а що буде далі?

825
00:35:14,330 --> 00:35:15,010
Давайте Enqueue -

826
00:35:15,010 --> 00:35:15,370
Як тебе звуть?

827
00:35:15,370 --> 00:35:16,160
>> АУДИТОРІЯ: Каллен.

828
00:35:16,160 --> 00:35:16,580
>> DAVID мала: Каллен.

829
00:35:16,580 --> 00:35:20,770
Давайте постановки в чергу Каллен, і
22 в даний час в черзі.

830
00:35:20,770 --> 00:35:22,300
Так що тепер повинен змінити тут?

831
00:35:22,300 --> 00:35:24,380
Передня не збирається
змінити, це очевидно.

832
00:35:24,380 --> 00:35:27,160
Розмір буде змінюватися, щоб бути 2 знову.

833
00:35:27,160 --> 00:35:31,590
І 22 закінчується тут, 9 і раніше присутня,
але це ефективно

834
00:35:31,590 --> 00:35:32,600
сміття значення зараз.

835
00:35:32,600 --> 00:35:35,910
Це просто пережиток минулого Джейком.

836
00:35:35,910 --> 00:35:39,200
>> Так що тепер, що станеться, якщо
Я з черги Девід?

837
00:35:39,200 --> 00:35:41,560
Одна остання операція, Dequeue Давида.

838
00:35:41,560 --> 00:35:46,070
Ми могли б перейти, але я пропоную давайте
зробити так мало роботи, скільки можливо.

839
00:35:46,070 --> 00:35:50,280
Тепер моя структура даних йде
Резервне в розмірі від 2 до 1.

840
00:35:50,280 --> 00:35:53,730
Але попереду черги
тепер стає 2.

841
00:35:53,730 --> 00:35:56,640
Мені не потрібно, щоб змінити це число
Поки ще немає, тому що вони

842
00:35:56,640 --> 00:35:58,230
просто значення сміття.

843
00:35:58,230 --> 00:35:59,720
>> Але тепер те, що відбувається?

844
00:35:59,720 --> 00:36:03,280
Припустимо, що я себе поставити в чергу, 26?

845
00:36:03,280 --> 00:36:05,890
Я відчуваю, що я належу тут.

846
00:36:05,890 --> 00:36:06,890
Так що я бути встановлені в чергу.

847
00:36:06,890 --> 00:36:08,760
Так що я як би до нас приєднатися.

848
00:36:08,760 --> 00:36:11,300
І навіть якщо ви не зовсім
візуально оцінити це на сцені,

849
00:36:11,300 --> 00:36:15,075
тому що у нас багато місця, я повинен
Не стояти тут, то чому?

850
00:36:15,075 --> 00:36:16,290
>> Зали: Ви перебуваєте за межами поля.

851
00:36:16,290 --> 00:36:16,370
>> DAVID мала: Вірно.

852
00:36:16,370 --> 00:36:16,940
Я поза законом.

853
00:36:16,940 --> 00:36:19,330
Я проіндексовано за
рамках даного масиву.

854
00:36:19,330 --> 00:36:23,420
Я дійсно повинен бути в одному з
три можливих місцях.

855
00:36:23,420 --> 00:36:25,150
Отже, де найбільш природним піти?

856
00:36:25,150 --> 00:36:27,760
Я пропоную позикових коштів
тижня один трюк.

857
00:36:27,760 --> 00:36:30,150
Оператор Mod, у відсотках.

858
00:36:30,150 --> 00:36:36,850
Тому що я стояв на технічно
Розміщення 3, але у мене 3 мод потужності,

859
00:36:36,850 --> 00:36:40,250
SO 3, знак відсотка, 3 -

860
00:36:40,250 --> 00:36:40,970
ємність 3.

861
00:36:40,970 --> 00:36:41,720
Що це?

862
00:36:41,720 --> 00:36:43,700
Який залишок при
Ви ділите 3 на 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Так що це ставить мене були Джейк був,
який насправді добре.

865
00:36:48,140 --> 00:36:50,370
Так що в даний час здійснення
цієї речі збирається

866
00:36:50,370 --> 00:36:51,250
бути трохи головного болю.

867
00:36:51,250 --> 00:36:53,740
Це дійсно просто один рядок
головного болю, коду.

868
00:36:53,740 --> 00:36:56,580
Але принаймні тепер є сміття
Значення тут, але є два

869
00:36:56,580 --> 00:36:57,910
законних цілими тут.

870
00:36:57,910 --> 00:37:04,160
І я стверджую, що зараз ми зробили
саме те, що нам потрібно зробити, так довго, як

871
00:37:04,160 --> 00:37:08,600
змінити те, що ми Джейка
Значення мало бути 26.

872
00:37:08,600 --> 00:37:12,110
>> Тепер у нас є достатньо інформації як і раніше
для підтримки цілісності

873
00:37:12,110 --> 00:37:13,060
цієї структури даних.

874
00:37:13,060 --> 00:37:17,160
Ми все ще почасти не пощастило, коли ми
вставити чотири або більш загальної

875
00:37:17,160 --> 00:37:20,740
елементи, але я можу принаймні зробити досить
ефективне використання цієї константи

876
00:37:20,740 --> 00:37:21,740
час, насправді.

877
00:37:21,740 --> 00:37:27,150
Я не доведеться турбуватися про перенесення
Кожна людина, як нахил Давида була.

878
00:37:27,150 --> 00:37:30,816
>> Будь-які питання по стеки,
або ця черга?

879
00:37:30,816 --> 00:37:32,184
>> Зали: причина, чому
Вам потрібен розмір, щоб ви знали

880
00:37:32,184 --> 00:37:34,010
Де є людина?

881
00:37:34,010 --> 00:37:34,770
>> DAVID мала: Абсолютно вірно.

882
00:37:34,770 --> 00:37:38,230
Мені потрібно знати розмір масиву
тому що мені потрібно точно знати, як

883
00:37:38,230 --> 00:37:41,940
багато з цих значень є законними,
і так, що я можу знайти, де поставити

884
00:37:41,940 --> 00:37:42,800
наступна людина.

885
00:37:42,800 --> 00:37:43,300
Саме так.

886
00:37:43,300 --> 00:37:44,580
Розмір -

887
00:37:44,580 --> 00:37:46,360
Насправді, ми не оновлювали це поки що.

888
00:37:46,360 --> 00:37:48,380
Я додав себе в 26.

889
00:37:48,380 --> 00:37:51,760
Розмір в даний час, а не один, а два.

890
00:37:51,760 --> 00:37:57,780
Так що тепер це дійсно допомагає мені знайти
чолі списку, яка не дорівнює 0, чи не

891
00:37:57,780 --> 00:37:59,250
1, але 2.

892
00:37:59,250 --> 00:38:01,665
Перед списком
насправді число 22.

893
00:38:01,665 --> 00:38:05,120
Тому що він прийшов першим, тому він повинен
пустять у магазині переді мною,

894
00:38:05,120 --> 00:38:08,780
хоча візуально я стою
ближче до магазину.

895
00:38:08,780 --> 00:38:09,220
>> Все в порядку?

896
00:38:09,220 --> 00:38:12,410
Оплесків для цих хлопців
, І ми повідомимо їх звідти.

897
00:38:12,410 --> 00:38:17,090
>> [Оплески]

898
00:38:17,090 --> 00:38:18,150
>> DAVID мала: Я міг дозволити
Ви тримаєте лоток.

899
00:38:18,150 --> 00:38:20,760
Ми могли бачити, що відбувається, якщо
Ви хочете, але може і ні.

900
00:38:20,760 --> 00:38:21,590
Добре.

901
00:38:21,590 --> 00:38:25,380
І що тепер що нам залишається?

902
00:38:25,380 --> 00:38:28,900
Ну, дозвольте мені запропонувати, що є
Кілька інші структури даних, ми могли

903
00:38:28,900 --> 00:38:33,810
почати додавати до нашого набір інструментів, який буде
дійсно може бути дуже, дуже актуальна, як

904
00:38:33,810 --> 00:38:35,270
ми поринемо в матеріал Інтернету.

905
00:38:35,270 --> 00:38:38,150
Що знову ж таки, є якийсь зв'язок
до дерев у вигляді

906
00:38:38,150 --> 00:38:40,550
те, що називається DOM, документ
об'єктної моделі.

907
00:38:40,550 --> 00:38:42,370
Але ми побачимо більше
що незабаром.

908
00:38:42,370 --> 00:38:46,260
>> Дозвольте мені запропонувати, що ми definitionally
дерево викликів тепер те, що ви знаєте, як

909
00:38:46,260 --> 00:38:48,820
більше сімейного дерева, де ви
є предком

910
00:38:48,820 --> 00:38:49,790
Коріння дерева.

911
00:38:49,790 --> 00:38:54,480
Патріархальної або матріархат в
самій вершині дерева.

912
00:38:54,480 --> 00:38:56,700
Без їх подружжя, в цьому випадку.

913
00:38:56,700 --> 00:39:00,940
Але тепер ми маємо те, що ми будемо називати
дітей, які є вузлами, які висять

914
00:39:00,940 --> 00:39:05,480
за лівим дитиною або право дитини,
стрілки, як показано тут.

915
00:39:05,480 --> 00:39:10,490
>> Іншими словами, в структурі даних дерева
в комп'ютер, дерево має нульову

916
00:39:10,490 --> 00:39:11,480
або більше вузлів.

917
00:39:11,480 --> 00:39:13,500
Якщо у нього є хоча б один вузол,
Це називається коренем.

918
00:39:13,500 --> 00:39:15,700
Це речі, що візуально
ми звертаємо на самому верху.

919
00:39:15,700 --> 00:39:20,280
І цей вузол, як і будь-який інший вузол, може
мати нуль, один або два, або три,

920
00:39:20,280 --> 00:39:23,600
або скільки дітей
Структура даних підтримує.

921
00:39:23,600 --> 00:39:29,150
У цьому випадку, корінь, зберігання
Значення одного, має двох дітей, 2 і 3,

922
00:39:29,150 --> 00:39:33,020
тому ми зазвичай називаємо 2 лівих
дитини і 3 правом дитини.

923
00:39:33,020 --> 00:39:36,940
>> А потім, коли ми приступимо до 5, 6, і
7, 6 можна назвати середнім дитиною.

924
00:39:36,940 --> 00:39:38,940
Якщо у вас є четверо дітей,
це збиває з пантелику.

925
00:39:38,940 --> 00:39:42,260
Таким чином, ми припинити використання такого
поєднань в усній формі.

926
00:39:42,260 --> 00:39:44,580
Але це дійсно тільки генеалогічне дерево.

927
00:39:44,580 --> 00:39:48,880
І листя тут вузли, які
самі по собі не мають дітей.

928
00:39:48,880 --> 00:39:52,540
Вони висять від нижньої частини дерева.

929
00:39:52,540 --> 00:39:56,940
>> Так як ми можемо реалізувати дерево,
має тільки дві дітям максимально?

930
00:39:56,940 --> 00:39:58,410
Ми назвемо це бінарне дерево.

931
00:39:58,410 --> 00:40:00,960
Бі знову означає два, в цьому
випадку, як і з бінарними.

932
00:40:00,960 --> 00:40:04,830
І тому він може мати нуль, один,
або двох дітей максимально.

933
00:40:04,830 --> 00:40:08,650
>> Я пропоную, щоб ми здійснили вузла
для цієї структури з Int N,

934
00:40:08,650 --> 00:40:11,910
а потім два покажчика, одна називається
залишили, одна називається правом.

935
00:40:11,910 --> 00:40:14,830
Але це просто приємно
довільні угоди.

936
00:40:14,830 --> 00:40:18,170
І те, що приємно зараз, особливо, якщо ви
вид боровся концептуально

937
00:40:18,170 --> 00:40:21,300
рекурсії, або думав, що це не було
Рішення дійсно ні до чого,

938
00:40:21,300 --> 00:40:23,120
Особливо якщо б ви могли
запустити з пам'яті.

939
00:40:23,120 --> 00:40:26,600
Тепер, коли ми говоримо про дані
структури і алгоритми, які дозволяють

940
00:40:26,600 --> 00:40:31,030
нам, щоб пройти їх і маніпулювати ними,
Виявляється, що рекурсія повертається в

941
00:40:31,030 --> 00:40:34,240
набагато більш переконливою
якщо не красивим способом.

942
00:40:34,240 --> 00:40:38,670
>> Так що я пропоную, є реалізація
з функції пошуку.

943
00:40:38,670 --> 00:40:39,870
Враховуючи два входи -

944
00:40:39,870 --> 00:40:41,570
тому думайте про це як чорний ящик.

945
00:40:41,570 --> 00:40:46,560
Враховуючи два входи, N, ціле і
покажчик на дереві, покажчик на

946
00:40:46,560 --> 00:40:50,020
вузла, або дійсно корінь дерева, я
стверджують, що ця функція може повертати

947
00:40:50,020 --> 00:40:53,530
істинним або хибним, що значення N
всередині цього дерева.

948
00:40:53,530 --> 00:40:55,210
>> Що всередині цього чорного ящика?

949
00:40:55,210 --> 00:40:57,440
Ну, чотири гілки.

950
00:40:57,440 --> 00:40:58,385
Спочатку просто перевіряє.

951
00:40:58,385 --> 00:41:00,490
Якщо дерево є порожнім, просто повернути помилкове.

952
00:41:00,490 --> 00:41:04,580
Якщо ні вузла, немає N,
немає числа, якраз повертає помилкове.

953
00:41:04,580 --> 00:41:12,330
Якщо хоч, N, значення, яке ви шукаєте
для, менше дерева стрілку N, і

954
00:41:12,330 --> 00:41:15,180
просто щоб було ясно, що це означає, коли
Я пишу дерева, а потім стрілка

955
00:41:15,180 --> 00:41:18,150
позначення, п?

956
00:41:18,150 --> 00:41:18,690
Саме так.

957
00:41:18,690 --> 00:41:21,970
Це означає, що разименованія
Покажчик називається деревом.

958
00:41:21,970 --> 00:41:26,750
Відправляйтеся туди, а потім потрапити всередину, що
вузла і отримати його полі, назване N.

959
00:41:26,750 --> 00:41:30,810
А потім порівняти фактичні N, яка була
перейшла в пошук проти нього.

960
00:41:30,810 --> 00:41:35,390
>> Таким чином, якщо N менше, значення N
у вузлі дерева сам, ну,

961
00:41:35,390 --> 00:41:36,720
Що це означає?

962
00:41:36,720 --> 00:41:40,690
Це нічого не значить на перший погляд.

963
00:41:40,690 --> 00:41:40,900
Вірно?

964
00:41:40,900 --> 00:41:45,560
Як і коли ви є масив
Значення, які Ви хотіли б застосувати двійковий

965
00:41:45,560 --> 00:41:48,290
шукати як форма розриву
і володарюй.

966
00:41:48,290 --> 00:41:51,790
Але те, що зробив припущення ми повинні зробити
для бінарного пошуку працює взагалі

967
00:41:51,790 --> 00:41:54,510
в телефонній книзі і
більш ранні приклади?

968
00:41:54,510 --> 00:41:55,530
>> Як бути відсортовані.

969
00:41:55,530 --> 00:41:59,490
Так що давайте уточнити визначення дерева
Тут, щоб не бути просто дерево, яке може

970
00:41:59,490 --> 00:42:00,880
мати будь-яку кількість дітей.

971
00:42:00,880 --> 00:42:04,700
Не тільки бінарне дерево, яке може
мати 0, 1 або 2 максимально.

972
00:42:04,700 --> 00:42:09,700
Але, як бінарне дерево пошуку або BST,
, Яка є просто химерний спосіб сказати

973
00:42:09,700 --> 00:42:15,430
бінарне дерево так, що кожен вузла
лівий дитини, якщо він присутній,

974
00:42:15,430 --> 00:42:16,830
менш вузла.

975
00:42:16,830 --> 00:42:20,170
І право кожного вузла дитиною,
якщо вони присутні, більше

976
00:42:20,170 --> 00:42:21,740
крім самого вузла.

977
00:42:21,740 --> 00:42:25,200
>> Отже, іншими словами, якщо ви повинні були зробити
дерева з всі цифри

978
00:42:25,200 --> 00:42:30,620
ретельно збалансовані, як це так, що якщо
у вас є 55 в якості кореневого, 33 може піти

979
00:42:30,620 --> 00:42:33,090
ліворуч від нього, тому що це менше, ніж 55.

980
00:42:33,090 --> 00:42:36,430
77 може піти у своєму праві, тому що
це більше, ніж 55.

981
00:42:36,430 --> 00:42:40,750
Але тепер помітили, те ж визначення,
це рекурсивне визначення в усній формі,

982
00:42:40,750 --> 00:42:42,600
повинен направити заявку на 33.

983
00:42:42,600 --> 00:42:47,610
33 в лівій дитина повинна бути менше його,
права дитини і в 33, 44, повинні бути

984
00:42:47,610 --> 00:42:48,580
більше, ніж він.

985
00:42:48,580 --> 00:42:51,670
>> Так що це бінарне дерево пошуку, а
Я пропоную, використовуючи трохи

986
00:42:51,670 --> 00:42:53,910
рекурсію, зараз ми можемо знайти N.

987
00:42:53,910 --> 00:42:59,160
Таким чином, якщо N менше, ніж значення N це
поточного вузла, я піду

988
00:42:59,160 --> 00:43:04,090
вперед і вибивати з рук, так би мовити, і просто
повертаючи те, що відповідь на це питання з

989
00:43:04,090 --> 00:43:08,470
пошук п від
лівого дерева дитини.

990
00:43:08,470 --> 00:43:11,370
Ще раз зверніть увагу, ця функція просто
очікує вузла зірки,

991
00:43:11,370 --> 00:43:12,780
покажчик на вузол.

992
00:43:12,780 --> 00:43:17,360
Так що, звичайно, я просто можу зробити дерево
стрілка вліво, що призводить

993
00:43:17,360 --> 00:43:18,400
мені на інший вузол.

994
00:43:18,400 --> 00:43:19,480
Але що це за вузол?

995
00:43:19,480 --> 00:43:22,820
>> Ну, відповідно до цієї декларацією,
Зліва тільки покажчик, так що тільки

996
00:43:22,820 --> 00:43:27,090
означає, що я переходячи до функції пошуку
різних покажчиків, а саме

997
00:43:27,090 --> 00:43:30,750
один, який представляє
моя ліва дитини дерева.

998
00:43:30,750 --> 00:43:36,040
Таким чином, в цьому випадку покажчик 33, якщо
це наш приклад введення Тим часом, якщо

999
00:43:36,040 --> 00:43:40,740
п більше значення п при
поточного вузла в дереві, то я

1000
00:43:40,740 --> 00:43:43,370
збираюся йти вперед і вибивати з рук в інші
Напрямок та просто сказати, я не

1001
00:43:43,370 --> 00:43:47,280
знаю, якщо це значення п в дереві,
але я знаю, якщо це так, це на мою

1002
00:43:47,280 --> 00:43:49,090
Права гілка, так би мовити.

1003
00:43:49,090 --> 00:43:53,120
Отже, дозвольте мені рекурсивно шукати,
проходить N раз, але переходить у

1004
00:43:53,120 --> 00:43:54,580
покажчик на моєму правому дитини.

1005
00:43:54,580 --> 00:44:00,020
>> Іншими словами, якщо я в даний час перебуваю на 55
і я шукаю 99, я знаю, що 99

1006
00:44:00,020 --> 00:44:04,270
більше 55, так само, як я розірвав
тижнів телефонну книгу тому, і ми

1007
00:44:04,270 --> 00:44:07,140
пішов прямо, як і ми
збираюся йти прямо тут.

1008
00:44:07,140 --> 00:44:11,960
І я не знаю, чи буде це на моє право
дитини, а це не так, 77 є, але

1009
00:44:11,960 --> 00:44:13,210
Я знаю, що в цьому напрямку.

1010
00:44:13,210 --> 00:44:18,770
Тому я називаю пошуку праворуч від мене дитину,
77, і нехай пошук фігури з

1011
00:44:18,770 --> 00:44:24,950
там, якщо 99 в цьому довільному
Прикладом є насправді.

1012
00:44:24,950 --> 00:44:26,900
>> В іншому випадку, те, що останній випадок?

1013
00:44:26,900 --> 00:44:28,620
Якщо дерево є недійсним один випадок.

1014
00:44:28,620 --> 00:44:31,890
Якщо п менше поточного вузла
значення ще один випадок.

1015
00:44:31,890 --> 00:44:35,120
Якщо п більше, ніж поточний
Значення вузла третій випадок.

1016
00:44:35,120 --> 00:44:38,250
Що четвертому і останньому випадку?

1017
00:44:38,250 --> 00:44:39,480
Я думаю, що ми з випадків, чи не так?

1018
00:44:39,480 --> 00:44:44,690
Повинно бути, п о
поточного вузла, що я на.

1019
00:44:44,690 --> 00:44:49,640
>> Так що, якщо Я шукаю 55 на даний момент
в цій історії, що філія

1020
00:44:49,640 --> 00:44:51,780
Дерево буде повернута істина.

1021
00:44:51,780 --> 00:44:55,380
Так що тут цікаво те, що ми
насправді, на відміну від минулих тижнів, ми якось

1022
00:44:55,380 --> 00:44:56,740
з двох випадків є підстави.

1023
00:44:56,740 --> 00:44:58,300
І вони не повинні
все буде на самому верху.

1024
00:44:58,300 --> 00:45:01,390
Верхня частина базового варіанту, тому що якщо
Дерево є недійсним, немає нічого спільного.

1025
00:45:01,390 --> 00:45:03,410
Просто повернути жорстко задані
Значення хибним.

1026
00:45:03,410 --> 00:45:07,400
>> Нижня гілка роду
за замовчуванням, згідно з яким, якщо ми перевірили для

1027
00:45:07,400 --> 00:45:11,550
нульовим, ми перевірили, якщо вона має бути
залишилося, але воно не повинно бути, у нас

1028
00:45:11,550 --> 00:45:14,640
перевіряється, якщо це має бути правильно, але це
не повинно бути, очевидно, що воно має бути

1029
00:45:14,640 --> 00:45:15,870
там, де ми є.

1030
00:45:15,870 --> 00:45:16,780
Це базовий варіант.

1031
00:45:16,780 --> 00:45:19,920
Таким чином, є два рекурсивних випадків
затиснута там в середині.

1032
00:45:19,920 --> 00:45:21,630
Але я міг би написати
це в будь-якому порядку.

1033
00:45:21,630 --> 00:45:24,520
Я просто думав, що це як би відчував, природні
спочатку перевірити на можливу помилку,

1034
00:45:24,520 --> 00:45:28,340
потім перевірити наліво, потім перевірити прямо, то
Припустимо, що ви перебуваєте у вузлі

1035
00:45:28,340 --> 00:45:30,630
насправді ви шукаєте.

1036
00:45:30,630 --> 00:45:36,240
>> Так чому це могло б бути корисним?

1037
00:45:36,240 --> 00:45:37,910
Ось і виходить -

1038
00:45:37,910 --> 00:45:42,110
і дозвольте мені перейти до тизер
тут, це в Мережі.

1039
00:45:42,110 --> 00:45:44,920
Ми збираємося, щоб почати використовувати не
мова програмування на перший, але

1040
00:45:44,920 --> 00:45:46,030
мова розмітки.

1041
00:45:46,030 --> 00:45:48,740
Мова розмітки є одним це
близькі за духом до програмування

1042
00:45:48,740 --> 00:45:51,715
мови, але це не дає вам
Можливість виразити себе логічно.

1043
00:45:51,715 --> 00:45:55,070
Це тільки дає вам можливість
виразити себе структурно.

1044
00:45:55,070 --> 00:45:57,960
>> Де Ви хочете, щоб покласти щось
на сторінці, веб-сторінка?

1045
00:45:57,960 --> 00:45:59,200
Який колір ви хочете це зробити?

1046
00:45:59,200 --> 00:46:00,950
Який розмір шрифту ви хочете це зробити?

1047
00:46:00,950 --> 00:46:02,970
Які слова ви насправді
хочете на веб-сторінку?

1048
00:46:02,970 --> 00:46:04,060
Так що це мова розмітки.

1049
00:46:04,060 --> 00:46:07,690
Але тоді ми дуже швидко ввести
JavaScript, який є повноцінним

1050
00:46:07,690 --> 00:46:08,560
мови програмування.

1051
00:46:08,560 --> 00:46:12,530
Дуже схожий за зовнішнім виглядом синтаксично
С, але це буде мати деякі

1052
00:46:12,530 --> 00:46:15,200
добре, більш потужна, більш
зручних для користувача характеристик.

1053
00:46:15,200 --> 00:46:18,050
>> І одним з розчарувань у це
точка в семестр, що ми будемо

1054
00:46:18,050 --> 00:46:22,065
скоро в реалізації спеллер набагато менше
рядків коду з використанням інших мовах

1055
00:46:22,065 --> 00:46:25,580
C ніж сама дозволяє, але для розуму
ми скоро зрозуміли.

1056
00:46:25,580 --> 00:46:27,750
Це буде перший такий веб-сторінки.

1057
00:46:27,750 --> 00:46:30,120
Він буде повністю в захват,
Перше ми робимо.

1058
00:46:30,120 --> 00:46:31,400
Він просто скаже: привіт світ.

1059
00:46:31,400 --> 00:46:34,010
Але якщо ви ніколи не бачили його
раніше, це HTML,

1060
00:46:34,010 --> 00:46:35,670
Мова розмітки гіпертексту.

1061
00:46:35,670 --> 00:46:39,310
>> Якщо ви йдете в певний пункт меню в
Найбільш будь-якому браузері, на будь-який веб-сторінці

1062
00:46:39,310 --> 00:46:43,160
Інтернет, ви можете побачити HTML
що деякі люди написали

1063
00:46:43,160 --> 00:46:44,400
створити цю веб-сторінку.

1064
00:46:44,400 --> 00:46:47,850
І це, ймовірно, виглядає не так
коротка або ж акуратно, як цей.

1065
00:46:47,850 --> 00:46:51,400
Але це буде за тією ж схемою цих
відкриті дужки і коса риска і

1066
00:46:51,400 --> 00:46:53,660
Листи та потенційно чисел.

1067
00:46:53,660 --> 00:46:56,770
>> Я думав, що дам вам тизер
того, що ви будете в змозі зробити

1068
00:46:56,770 --> 00:46:57,950
після прийому CS50.

1069
00:46:57,950 --> 00:47:02,620
Пустіть мене до cs.harvard.edu / грабувати,
Домашня сторінка нашої власної Роб Боудена.

1070
00:47:02,620 --> 00:47:06,080
Він зробив це для нас.

1071
00:47:06,080 --> 00:47:07,490
Таким чином, ви скоро будете в змозі зробити це.

1072
00:47:07,490 --> 00:47:10,660
А також, що ви чули
Сьогодні вранці -

1073
00:47:10,660 --> 00:47:12,480
те, що ви чули сьогодні вранці -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER Танцювальна музика]

1075
00:47:13,780 --> 00:47:15,702
>> - Ви будете мати можливість зробити це.

1076
00:47:15,702 --> 00:47:16,790
Що чекає нас у середу.

1077
00:47:16,790 --> 00:47:17,791
Ми будемо бачити вас тоді.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER Танцювальна музика]

1079
00:47:22,950 --> 00:47:24,300
DAVID Малай: Наступного CS50 -

1080
00:47:24,300 --> 00:47:31,670