1
00:00:00,000 --> 00:00:03,423
>> [Грає музика]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Пен: Ласкаво просимо в тиждень 6 розділу.

4
00:00:08,210 --> 00:00:11,620
Ми відхилилися від нашого стандарту
розділ час у вівторок

5
00:00:11,620 --> 00:00:14,130
днем, щоб цей прекрасний неділю вранці.

6
00:00:14,130 --> 00:00:17,330
Спасибі за всім, що
приєднався до мене сьогодні, але серйозно,

7
00:00:17,330 --> 00:00:18,170
оплески.

8
00:00:18,170 --> 00:00:20,600
>> Це досить велике зусилля.

9
00:00:20,600 --> 00:00:23,600
Я майже не навіть зробити його
в той час, але це було в порядку.

10
00:00:23,600 --> 00:00:27,520
Так що я знаю, що всі ви
тільки що зробили його у вікторині.

11
00:00:27,520 --> 00:00:30,370
Перш за все, ласкаво просимо в
оборотна сторона цього.

12
00:00:30,370 --> 00:00:32,917
>> По-друге, ми поговоримо про це.

13
00:00:32,917 --> 00:00:34,000
Ми поговоримо про вікторину.

14
00:00:34,000 --> 00:00:35,700
Ми поговоримо про те, як
Ви робите в класі.

15
00:00:35,700 --> 00:00:36,550
Ви будете в порядку.

16
00:00:36,550 --> 00:00:39,080
У мене є свої вікторини для
Ви в кінці тут,

17
00:00:39,080 --> 00:00:42,120
так що якщо ви, хлопці, хочете, щоб прийняти
Погляд на неї, абсолютно нормально.

18
00:00:42,120 --> 00:00:46,590
>> Так швидко перш ніж ми почнемо, то
Порядок денний на сьогодні виглядає наступним чином.

19
00:00:46,590 --> 00:00:48,430
Як ви можете бачити, ми
в основному швидке звільнення

20
00:00:48,430 --> 00:00:52,120
через цілу купу структур даних
дійсно, дійсно, дійсно швидко.

21
00:00:52,120 --> 00:00:54,380
Так як таке воно не буде
супер інтерактивна сьогодні.

22
00:00:54,380 --> 00:00:59,620
Це буде просто мені ніби кричати
речі, які ви, і якщо я плутаю вас,

23
00:00:59,620 --> 00:01:02,680
якщо я йду занадто швидко, дайте мені знати.

24
00:01:02,680 --> 00:01:05,200
Вони просто різні дані
структури, а також в рамках

25
00:01:05,200 --> 00:01:07,070
Вашої PSET для цього
Майбутня тиждень, ви будете

26
00:01:07,070 --> 00:01:10,340
буде запропоновано реалізувати один з них,
можливо, два з them-- два з них

27
00:01:10,340 --> 00:01:12,319
в PSET.

28
00:01:12,319 --> 00:01:14,610
ОК, так що я просто хочу, щоб
почати з деяких оголошень.

29
00:01:14,610 --> 00:01:19,070
Ми підемо по стеків і черг в більш
Глибина, ніж те, що ми робили раніше вікторини.

30
00:01:19,070 --> 00:01:20,990
Ми підемо по пов'язані
список знову, знову,

31
00:01:20,990 --> 00:01:23,899
більш докладно, ніж те, що
ми мали до вікторини.

32
00:01:23,899 --> 00:01:26,440
І тоді ми будемо говорити про хеш
столи, дерева і намагається, які

33
00:01:26,440 --> 00:01:28,890
все досить необхідно для вашого PSET.

34
00:01:28,890 --> 00:01:32,925
І тоді ми будемо йти над деякими
Корисні поради для pset5.

35
00:01:32,925 --> 00:01:37,360
>> Отже, вікторина 0.

36
00:01:37,360 --> 00:01:41,090
Середня був 58%.

37
00:01:41,090 --> 00:01:45,370
Це була дуже низькою, і так ви, хлопці, все
зробив дуже, дуже добре відповідно

38
00:01:45,370 --> 00:01:46,510
З цим.

39
00:01:46,510 --> 00:01:49,970
>> Досить багато, правило, якщо ви
в стандартному відхиленні від середнього

40
00:01:49,970 --> 00:01:52,990
особливо, оскільки ми знаходимося в менш
зручні розділ, ви абсолютно нормально.

41
00:01:52,990 --> 00:01:54,120
Ви на вірному шляху.

42
00:01:54,120 --> 00:01:55,190
Життя чудове.

43
00:01:55,190 --> 00:01:58,952
>> Я знаю, що це страшно думати, що
Я отримав, як 40% на цьому конкурсі.

44
00:01:58,952 --> 00:02:00,160
Я збираюся на провал цього класу.

45
00:02:00,160 --> 00:02:02,243
Я обіцяю вам, ви не
відбувається збій клас.

46
00:02:02,243 --> 00:02:03,680
Ти абсолютно нормально.

47
00:02:03,680 --> 00:02:06,850
>> Для тих з вас, хто отримав більше
середнє, вражає, вражає,

48
00:02:06,850 --> 00:02:08,780
як серйозно добре зроблено.

49
00:02:08,780 --> 00:02:09,689
Я їх зі мною.

50
00:02:09,689 --> 00:02:11,730
Не соромтеся, отримати їх
Наприкінці розділу.

51
00:02:11,730 --> 00:02:14,520
Дозвольте мені знати, якщо у вас є
питання, питання з ними.

52
00:02:14,520 --> 00:02:17,204
Якщо ми додамо ваш рахунок
так, дайте нам знати.

53
00:02:17,204 --> 00:02:21,240
>> Отже, pset5, це дійсно
дивно тиждень Єльському університеті в сенсі

54
00:02:21,240 --> 00:02:24,240
що наша PSET пов'язано
У середу опівдні в тому числі

55
00:02:24,240 --> 00:02:27,317
кінці дня, так що насправді
Теоретично через вівторок опівдні.

56
00:02:27,317 --> 00:02:29,150
Напевно, ніхто не закінчив
на вівторок опівдні.

57
00:02:29,150 --> 00:02:30,830
Це абсолютно нормально.

58
00:02:30,830 --> 00:02:33,700
Ми збираємося, щоб мати прийомні години
сьогодні, а також в понеділок ввечері.

59
00:02:33,700 --> 00:02:36,810
І всі розділи цьому тижні буде
фактично перетворився в майстернях,

60
00:02:36,810 --> 00:02:38,800
так що не соромтеся поп
будь-який перетин хочете,

61
00:02:38,800 --> 00:02:42,810
і вони будуть свого роду міні-PSET
семінари для допомоги в цьому.

62
00:02:42,810 --> 00:02:45,620
Так як таке, це єдиний розділ,
де ми навчальний матеріал.

63
00:02:45,620 --> 00:02:49,220
Всі інші розділи будуть фокусування
виключно на допомогу для PSET.

64
00:02:49,220 --> 00:02:50,146
Так?

65
00:02:50,146 --> 00:02:52,000
>> АУДИТОРІЯ: Де робочі години?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Пен: Годинники
tonight-- о, гарне питання.

67
00:02:56,120 --> 00:03:00,580
Я думаю, що сьогодні ввечері офіс годин
в Teal або громад.

68
00:03:00,580 --> 00:03:02,984
Якщо ви подивитеся онлайн CS50
і ви йдете до офісної годин,

69
00:03:02,984 --> 00:03:05,650
повинен бути графік, що
говорить вам, де всі з них.

70
00:03:05,650 --> 00:03:07,954
>> Я знаю, як сьогодні
або завтра чирок,

71
00:03:07,954 --> 00:03:10,120
і я думаю, що ми, можливо,
фонду для іншої ночі.

72
00:03:10,120 --> 00:03:11,020
Я не впевнений.

73
00:03:11,020 --> 00:03:11,700
Гарне питання.

74
00:03:11,700 --> 00:03:14,430
Перевірте CS50.

75
00:03:14,430 --> 00:03:18,780
>> Прохолодні, будь-які питання, що стосуються
Графік на наступний, як три дні?

76
00:03:18,780 --> 00:03:21,690
Я обіцяю вам, хлопці, як Давида
сказав, що це вершина пагорба.

77
00:03:21,690 --> 00:03:23,050
Ви, хлопці, майже немає.

78
00:03:23,050 --> 00:03:24,644
Всього три більше днів.

79
00:03:24,644 --> 00:03:26,310
Отримати там, а потім ми все зійде.

80
00:03:26,310 --> 00:03:28,114
Ми матимемо гарний CS-безкоштовний перерву.

81
00:03:28,114 --> 00:03:28,780
Ласкаво просимо назад.

82
00:03:28,780 --> 00:03:30,779
Ми в мережі пірнати
програмування та розробка,

83
00:03:30,779 --> 00:03:35,150
речі, які дуже весело порівнянні
в деяких інших psets.

84
00:03:35,150 --> 00:03:37,974
І це буде холод і
ми будемо мати багато веселощів.

85
00:03:37,974 --> 00:03:38,890
Ми будемо мати більше цукерок.

86
00:03:38,890 --> 00:03:39,730
На жаль для цукерок.

87
00:03:39,730 --> 00:03:40,945
Я забув цукерки.

88
00:03:40,945 --> 00:03:43,310
Це був грубий вранці.

89
00:03:43,310 --> 00:03:46,340
Таким чином, ви, хлопці, майже там,
і я дуже пишаюся вами, хлопці.

90
00:03:46,340 --> 00:03:49,570
>> ОК, так що стеки.

91
00:03:49,570 --> 00:03:53,331
Хто любив питання про Джека
і його одяг на вікторині?

92
00:03:53,331 --> 00:03:53,830
Ніхто?

93
00:03:53,830 --> 00:03:56,500
ОК, це нормально.

94
00:03:56,500 --> 00:04:00,200
>> Так по суті, як ви можете
фото Джек, цей хлопець тут,

95
00:04:00,200 --> 00:04:03,350
любить приймати одяг
з верхньої частини стека,

96
00:04:03,350 --> 00:04:05,750
і він кладе його назад на
стек після того як він зробив.

97
00:04:05,750 --> 00:04:07,600
Так що в цьому шляху, він ніколи
здається, стає

98
00:04:07,600 --> 00:04:10,090
в нижній частині
укладають у його одязі.

99
00:04:10,090 --> 00:04:12,600
Так що це свого роду описує
основна структура даних

100
00:04:12,600 --> 00:04:16,610
як стек реалізований.

101
00:04:16,610 --> 00:04:20,060
>> По суті, думати про
стек, як будь стек об'єктів

102
00:04:20,060 --> 00:04:24,900
де ви поклали речі на вершині, і
то ви поп їх зверху.

103
00:04:24,900 --> 00:04:28,600
Так ЛІФО є абревіатурою нам подобається
щоб use-- Останнє увійшов, першим вийшов.

104
00:04:28,600 --> 00:04:32,480
І так, щоб тривати у верхній частині
стек першим, який виходить.

105
00:04:32,480 --> 00:04:34,260
І так два члени
ми хотіли б пов'язати

106
00:04:34,260 --> 00:04:36,190
с, що називається поштовх і поп-музики.

107
00:04:36,190 --> 00:04:39,790
Коли ви натискаєте на те
стек, і ви поп його назад.

108
00:04:39,790 --> 00:04:43,422
>> І тому я думаю, це свого роду
абстрактне поняття для тих з вас,

109
00:04:43,422 --> 00:04:45,630
хто хоче бачити, як
практична реалізація

110
00:04:45,630 --> 00:04:46,740
в реальному світі.

111
00:04:46,740 --> 00:04:50,170
Як багато з вас написали есе
може бути, як годину, перш ніж він був через,

112
00:04:50,170 --> 00:04:54,510
і ви випадково видалили величезний
шматок ній, як випадково?

113
00:04:54,510 --> 00:04:58,560
І тоді те, що управління роблю
ми використовуємо, щоб покласти його назад?

114
00:04:58,560 --> 00:05:00,030
Control-Z, так?

115
00:05:00,030 --> 00:05:03,640
Control-Z, так що кількість часу
що Control-Z врятував моє життя,

116
00:05:03,640 --> 00:05:08,820
врятував мою дупу, кожен раз,
який реалізується через стек.

117
00:05:08,820 --> 00:05:13,020
>> По суті вся інформація
що на вашому документі Word,

118
00:05:13,020 --> 00:05:15,080
він отримує штовхнув і вискочив на волю.

119
00:05:15,080 --> 00:05:19,460
І так щоразу, коли вам істотно
видалити що-небудь, ви поп його назад.

120
00:05:19,460 --> 00:05:22,820
І потім, якщо вам це потрібно знову, вам
штовхати його, що це те, що Ctrl + C робить.

121
00:05:22,820 --> 00:05:26,770
І так реальний світ функція
про те, як простий структури даних

122
00:05:26,770 --> 00:05:28,690
може допомогти з вашого повсякденного життя.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Таким чином, структура є способом, яким
ми насправді створити стек.

125
00:05:40,150 --> 00:05:44,720
Набираємо визначити-структуру, а потім
ми називаємо це стек на дні.

126
00:05:44,720 --> 00:05:47,440
І в стеку,
у нас є два параметри

127
00:05:47,440 --> 00:05:51,580
що ми можемо по суті маніпулювати,
так що ми повинні сЬаг зірки рядків потужності.

128
00:05:51,580 --> 00:05:55,150
>> Все, що він робить
створює масив

129
00:05:55,150 --> 00:05:58,835
що ми можемо зберігати все, що ви хочете
які ми можемо визначити його ємність.

130
00:05:58,835 --> 00:06:01,990
Ємність знаходиться всього макс кількість
предмети можна покласти в цьому масиві.

131
00:06:01,990 --> 00:06:05,660
Розмір INT це лічильник, який тримає
відслідковувати, скільки елементів в даний час

132
00:06:05,660 --> 00:06:07,850
в стеку.

133
00:06:07,850 --> 00:06:11,860
Отже, ми можемо відстежувати, А,
і, як велика фактична стек,

134
00:06:11,860 --> 00:06:14,850
і, В, скільки цього стека
ми заповнили, тому що ми не хочемо,

135
00:06:14,850 --> 00:06:18,800
переповнення над тим, що наші можливості.

136
00:06:18,800 --> 00:06:24,340
>> Так, наприклад, цей прекрасний
Питання було на вікторині.

137
00:06:24,340 --> 00:06:28,160
По суті, як ми штовхати
на верх стека.

138
00:06:28,160 --> 00:06:28,830
Досить просто.

139
00:06:28,830 --> 00:06:30,621
Якщо ви подивитеся на нього,
ми будемо йти через це.

140
00:06:30,621 --> 00:06:32,640
Якщо [нерозбірливо] размер--
пам'ятаєте, коли ви

141
00:06:32,640 --> 00:06:35,300
хочете отримати доступ до будь
Параметр в структури,

142
00:06:35,300 --> 00:06:40,320
ви ім'я struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> У цьому випадку, з поза
ім'я нашого стека.

144
00:06:42,720 --> 00:06:46,230
Ми хочемо, щоб відкрити розмір
це, тому ми робимо s.size.

145
00:06:46,230 --> 00:06:50,280
Так що, поки розмір не
дорівнює потужності або до тих пір,

146
00:06:50,280 --> 00:06:52,940
а це менше, ніж ємність,
або буде працювати тут.

147
00:06:52,940 --> 00:06:57,180
>> Ви хочете отримати доступ до внутрішньої
вашого стека, так s.strings,

148
00:06:57,180 --> 00:07:00,790
і ви збираєтеся покласти, що новий номер
що ви хочете вставити в там.

149
00:07:00,790 --> 00:07:05,030
Давайте просто скажемо, ми хочемо, щоб
вставте Int N в стек,

150
00:07:05,030 --> 00:07:08,905
ми могли б зробити s.strings,
кронштейни, s.size дорівнює п.

151
00:07:08,905 --> 00:07:11,030
Тому що розмір де ми
в даний час в стеку

152
00:07:11,030 --> 00:07:14,590
якщо ми збираємося, щоб підштовхнути
це, ми просто доступ

153
00:07:14,590 --> 00:07:17,370
там, де розмір, тим
ток повнота стека,

154
00:07:17,370 --> 00:07:21,729
і ми натискаємо Int N на нього.

155
00:07:21,729 --> 00:07:24,770
А потім ми хочемо, щоб переконатися, що
ми також збільшуючи розмір п,

156
00:07:24,770 --> 00:07:27,436
так що ми можемо відстежувати ми в
додали додатковий предмет в стек.

157
00:07:27,436 --> 00:07:29,660
Тепер у нас є більший розмір.

158
00:07:29,660 --> 00:07:33,196
Чи означає це, тут сенс
все, як логічно це працює?

159
00:07:33,196 --> 00:07:34,160
Це був свого роду швидко.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
АУДИТОРІЯ: Чи можете ви перейти
в s.stringss.strings [s.size] ще раз?

162
00:07:42,160 --> 00:07:45,808
ANDI Пен: Звичайно, так, що робить
s.size даний час нам дає?

163
00:07:45,808 --> 00:07:47,440
АУДИТОРІЯ: Це поточний розмір.

164
00:07:47,440 --> 00:07:50,890
ANDI Пен: Рівне, тому
поточний індекс, що наш розмір на,

165
00:07:50,890 --> 00:07:57,780
і тому ми хочемо, щоб поставити новий ціле число
що ми хочемо, щоб вставити в s.size.

166
00:07:57,780 --> 00:07:58,760
Чи має це сенс?

167
00:07:58,760 --> 00:08:01,110
Тому s.strings, все, що
це є ім'я масиву.

168
00:08:01,110 --> 00:08:03,510
Все це звертається до
Масив в нашої структури,

169
00:08:03,510 --> 00:08:06,030
і тому, якщо ми хочемо, щоб
розмістити п в цьому індексі,

170
00:08:06,030 --> 00:08:09,651
ми можемо просто відкрити його
за допомогою кронштейнів s.size.

171
00:08:09,651 --> 00:08:10,150
Прохолодний.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Гаразд, поп, я псевдокод його
для вас, хлопці, але аналогічної концепції.

174
00:08:18,916 --> 00:08:19,790
Чи має це сенс?

175
00:08:19,790 --> 00:08:22,310
Якщо розмір більше,
нуля, то ви

176
00:08:22,310 --> 00:08:25,350
знаю, що ви хочете взяти щось
через, якщо розмір не

177
00:08:25,350 --> 00:08:27,620
більше нуля, то ви
не мають нічого в стеку.

178
00:08:27,620 --> 00:08:29,840
>> Отже, ви хочете тільки виконувати
цей код, він може тільки

179
00:08:29,840 --> 00:08:32,320
поп, якщо є щось, щоб поп-музики.

180
00:08:32,320 --> 00:08:35,830
Таким чином, якщо розмір більше
ніж 0, то мінус розмір.

181
00:08:35,830 --> 00:08:40,020
Ми зменшуємо розмір, а потім повернутися
все, що всередині нього, тому що

182
00:08:40,020 --> 00:08:42,710
сунути, ми хочемо, щоб
Доступ все, що зберігається

183
00:08:42,710 --> 00:08:45,694
в індексі вершини стека.

184
00:08:45,694 --> 00:08:46,610
Всі сенс?

185
00:08:46,610 --> 00:08:49,693
Якби я зробив, ви, хлопці написати це,
ви, хлопці, буде мати можливість записати його?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
ОК, ви, хлопці, можете пограти з ним.

188
00:08:53,570 --> 00:08:55,252
Не турбуйтеся, якщо ви не отримаєте його.

189
00:08:55,252 --> 00:08:57,460
Ми не встигли закодувати
це сьогодні, тому що ми

190
00:08:57,460 --> 00:08:59,959
є багато цих структур
щоб пройти, але по суті

191
00:08:59,959 --> 00:09:02,214
псевдокод, дуже, дуже схожі, щоб підштовхнути.

192
00:09:02,214 --> 00:09:03,380
Просто дотримуйтесь уздовж логіки.

193
00:09:03,380 --> 00:09:06,092
Переконайтеся, що ви звертаєтеся все
особливості вашої структури правильно.

194
00:09:06,092 --> 00:09:06,574
Так?

195
00:09:06,574 --> 00:09:09,282
>> АУДИТОРІЯ: Чи будуть ці слайди і
Вся ця річ буде до сьогодні-іш?

196
00:09:09,282 --> 00:09:11,586
ANDI Пен: Завжди, так.

197
00:09:11,586 --> 00:09:13,710
Я збираюся спробувати поставити
це до, як через годину після.

198
00:09:13,710 --> 00:09:16,626
Я електронній пошті Давида, Девід буде намагатися
покласти його, як через годину після цього.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> ОК, так що потім ми перейдемо в цей інший
прекрасний структура даних, звана чергу.

201
00:09:25,470 --> 00:09:30,140
Як ви, хлопці, можете подивитися тут, А
Чергу, для англійців серед нас,

202
00:09:30,140 --> 00:09:32,010
Все це являє собою лінію.

203
00:09:32,010 --> 00:09:34,680
Так всупереч тому, що
Ви думаєте, що стек,

204
00:09:34,680 --> 00:09:37,750
чергу саме те, що
логічно ви думаєте.

205
00:09:37,750 --> 00:09:41,914
Він проводиться за правилами FIFO,
який є першим увійшов, першим вийшов.

206
00:09:41,914 --> 00:09:43,705
Якщо ви перший
один у лінії, ви

207
00:09:43,705 --> 00:09:46,230
перше, що
виходить з лінії.

208
00:09:46,230 --> 00:09:49,680
>> Отже, що ми хотіли б назвати це
у звільненні пакету з черги і enqueueing.

209
00:09:49,680 --> 00:09:52,380
Якщо ми хочемо щось додати
в нашій черзі, ми в чергу.

210
00:09:52,380 --> 00:09:55,690
Якщо ми хочемо, щоб з черги, або взяти
то геть, ми з черги.

211
00:09:55,690 --> 00:10:03,350
>> Так же зміст, що ми начебто
створення елементів фіксованого розміру, що ми

212
00:10:03,350 --> 00:10:06,500
може зберігати певний
речі, але ми можемо також

213
00:10:06,500 --> 00:10:10,100
змінити, де ми розміщення
Параметри всередині них

214
00:10:10,100 --> 00:10:13,140
на основі того, який тип
Функціональність ми хочемо.

215
00:10:13,140 --> 00:10:16,700
Так стеків, ми хотіли останній
Один з них, N, щоб бути першим з.

216
00:10:16,700 --> 00:10:19,800
Чергу ми хочемо перший
і бути перше, що.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Так в структури типу
визначити, як ви можете бачити,

219
00:10:26,710 --> 00:10:29,470
це трохи відрізняється
від того, що стек

220
00:10:29,470 --> 00:10:33,120
тому що ми не тільки повинні мати
трек, де в даний час розмір,

221
00:10:33,120 --> 00:10:37,420
ми також хочемо, щоб відстежувати голову
як і де ми в даний час.

222
00:10:37,420 --> 00:10:39,580
Так що я думаю, що це простіше
якщо я малюю це.

223
00:10:39,580 --> 00:10:53,270
Отже, давайте уявимо, що у нас є черга,
так скажемо, голова прямо тут.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Глава лінії, давайте
просто сказати, що це в даний час,

226
00:10:58,310 --> 00:11:01,809
і ми хочемо, щоб вставити
то в черзі.

227
00:11:01,809 --> 00:11:04,350
Я збираюсь подзвонити розмір істотно
це те ж саме, як хвіст,

228
00:11:04,350 --> 00:11:06,314
кінець, де ваш черги.

229
00:11:06,314 --> 00:11:07,730
Давайте просто скажемо, розмір прямо тут.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Так як же реально
вставити щось в черзі?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Що індекс ми хочемо розмістити
де ми хочемо вставити в.

234
00:11:24,130 --> 00:11:29,320
Якщо це початок вашої
черги, і це в кінці його

235
00:11:29,320 --> 00:11:31,860
або розмір його, де ми
Щоб додати наступний об'єкт?

236
00:11:31,860 --> 00:11:32,920
>> АУДИТОРІЯ: [нерозбірливо]

237
00:11:32,920 --> 00:11:35,920
ANDI Пен: Рівне, ви хочете, щоб додати
це в залежності від ви написали це.

238
00:11:35,920 --> 00:11:37,840
Або це порожній або порожній.

239
00:11:37,840 --> 00:11:42,630
Отже, ви хочете, щоб додати його, ймовірно,
тут, тому що, якщо розмір is--

240
00:11:42,630 --> 00:11:50,540
якщо вони все сповнені, ви хочете
щоб додати його прямо тут, прямо?

241
00:11:50,540 --> 00:11:57,150
>> І так от, в той час як дуже, дуже
просто, не зовсім завжди правильно

242
00:11:57,150 --> 00:12:00,690
тому що основна відмінність
між черги і стека

243
00:12:00,690 --> 00:12:04,350
є те, що черга може
насправді маніпулювати

244
00:12:04,350 --> 00:12:06,980
так що зміни головні
в залежності від того, де ви хочете

245
00:12:06,980 --> 00:12:08,650
початок вашого кия, щоб почати.

246
00:12:08,650 --> 00:12:11,900
І в результаті, твій хвіст
Також зміниться.

247
00:12:11,900 --> 00:12:14,770
І так поглянути на
цей код прямо зараз.

248
00:12:14,770 --> 00:12:18,620
Як ви, хлопці, було також запропоновано
написати на вікторині, поставити в чергу.

249
00:12:18,620 --> 00:12:22,580
Може бути, ми поговоримо через чому
відповідь була, що це було.

250
00:12:22,580 --> 00:12:26,790
>> Я не міг відповідати цій лінії на один,
але по суті це шматок коду

251
00:12:26,790 --> 00:12:29,030
повинні знаходитися на одній лінії.

252
00:12:29,030 --> 00:12:30,140
Проведіть як 30 секунд.

253
00:12:30,140 --> 00:12:33,000
Погляньте, і зрозуміти, чому
це шлях, що це.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Дуже, дуже схожі структура, дуже, дуже
Подібна структура, як і попередній

256
00:12:55,420 --> 00:12:58,090
стек для, можливо, за винятком того,
одного рядка коду.

257
00:12:58,090 --> 00:13:01,190
І, що одного рядка коду
визначає функціональність.

258
00:13:01,190 --> 00:13:03,900
І це дійсно відрізняє
черга з стопки.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Хто-небудь хоче прийняти удар
на пояснення, чому ви

261
00:13:22,010 --> 00:13:24,980
отримав цю складну річ в тут?

262
00:13:24,980 --> 00:13:27,845
Ми бачимо повернення нашого
чудовий друг модуль.

263
00:13:27,845 --> 00:13:31,020
Як ви, хлопці, скоро прийде
визнати в програмуванні,

264
00:13:31,020 --> 00:13:34,910
майже в будь-який час потрібно щось
обернути навколо нічого,

265
00:13:34,910 --> 00:13:36,850
модуль буде шлях, щоб зробити це.

266
00:13:36,850 --> 00:13:40,510
Так, знаючи, що, хто-небудь хоче
спробувати пояснюючи, що рядки коду?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Так, всі відповіді
приймаються і схвалюються.

269
00:13:47,507 --> 00:13:48,840
АУДИТОРІЯ: Ви говорите мені?

270
00:13:48,840 --> 00:13:49,506
ANDI Пен: Так.

271
00:13:49,506 --> 00:13:56,200
АУДИТОРІЯ: О, ні вибачте.

272
00:13:56,200 --> 00:14:00,250
ANDI Пен: ОК, так що давайте
ходити через цей код.

273
00:14:00,250 --> 00:14:03,642
Тому, коли ви намагаєтеся
щось додати на черзі,

274
00:14:03,642 --> 00:14:08,510
в прекрасному випадку, що глава трапляється
щоб бути тут, це дуже легко для нас

275
00:14:08,510 --> 00:14:10,960
просто йти до кінця
вставити щось, вірно?

276
00:14:10,960 --> 00:14:14,690
Але вся суть у черзі
що глава може насправді динамічно

277
00:14:14,690 --> 00:14:17,280
змінюватися в залежності від де
хочете початок нашого ц бути,

278
00:14:17,280 --> 00:14:19,880
і, як такий, хвіст
Також зміниться.

279
00:14:19,880 --> 00:14:31,100
>> І так уявити, що це не було
черги, а це було черги.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Скажімо, голова прямо тут.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Скажімо, наша черга подивився, як це.

284
00:14:56,980 --> 00:15:00,190
Якби ми хотіли, щоб перекласти, де
початок лінії,

285
00:15:00,190 --> 00:15:03,400
давайте говорити, що ми перейшли голову
таким чином, і тут розміри.

286
00:15:03,400 --> 00:15:07,100
>> Тепер ми хочемо, щоб додати щось
ця черга, але, як ви, хлопці, можете бачити,

287
00:15:07,100 --> 00:15:11,150
це не так просто, як просто
додати все, що після розміру

288
00:15:11,150 --> 00:15:13,630
бо тоді ми біжимо з
Межі нашого фактичного масиву.

289
00:15:13,630 --> 00:15:16,190
Де ми хочемо, щоб дійсно додати тут.

290
00:15:16,190 --> 00:15:18,610
Це краса черзі
є те, що для нас, візуально

291
00:15:18,610 --> 00:15:22,380
Схоже, що лінія йде, як це,
але при зберіганні в структурі даних,

292
00:15:22,380 --> 00:15:29,370
вони дають його в якості як цикл.

293
00:15:29,370 --> 00:15:32,360
Це свого роду обтікає
до фронту таким же чином

294
00:15:32,360 --> 00:15:34,780
що лінія може також обернути
навколо залежно від скрізь, де вас

295
00:15:34,780 --> 00:15:36,279
хочу початку рядка, щоб бути.

296
00:15:36,279 --> 00:15:38,630
І тому, якщо ми беремо
шукати тут, давайте

297
00:15:38,630 --> 00:15:40,880
що ми хочемо, щоб створити
Функція називається Додає.

298
00:15:40,880 --> 00:15:43,980
Ми хотіли, щоб додати Int N в цій д.

299
00:15:43,980 --> 00:15:49,250
Якщо q.size q-- ми називаємо це наші дані
structure-- якщо наша queue.size НЕ

300
00:15:49,250 --> 00:15:52,520
дорівнює потужності або якщо
це менше, ніж ємність,

301
00:15:52,520 --> 00:15:55,120
q.strings це масив в нашій ц.

302
00:15:55,120 --> 00:15:58,380
Ми збираємося встановити
що одно q.heads,

303
00:15:58,380 --> 00:16:02,730
що прямо тут, плюс q.size
Модуль ємністю, яка

304
00:16:02,730 --> 00:16:04,290
обернути нас тут.

305
00:16:04,290 --> 00:16:08,040
>> Таким чином, у цьому прикладі, індекс
глави 1, вірно?

306
00:16:08,040 --> 00:16:11,480
Індекс розміру 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Таким чином, ми можемо зробити 1 плюс 4 модуля
нашої здатності, яка 5.

308
00:16:19,500 --> 00:16:20,920
Що це нам дає?

309
00:16:20,920 --> 00:16:23,270
Що таке індекс, який
виходить з цього?

310
00:16:23,270 --> 00:16:24,080
>> АУДИТОРІЯ: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Пен: 0,
буває тут,

312
00:16:27,870 --> 00:16:30,640
і тому ми хочемо, щоб мати можливість
вставити в прямо тут.

313
00:16:30,640 --> 00:16:34,730
І так це рівняння тут вид
просто працює з будь-якими номерами

314
00:16:34,730 --> 00:16:36,750
в залежності від того, де ваш
голова і ваш розмір є.

315
00:16:36,750 --> 00:16:38,541
Якщо ви знаєте, що ті,
речі, ви знаєте,

316
00:16:38,541 --> 00:16:43,170
саме там, де ви хочете вставити
все, що після черги.

317
00:16:43,170 --> 00:16:44,640
Чи має це сенс для всіх?

318
00:16:44,640 --> 00:16:48,560
>> Я знаю, начебто мозку
тизер особливо, так як це

319
00:16:48,560 --> 00:16:50,512
прийшли в після вашого тесту.

320
00:16:50,512 --> 00:16:52,220
Але, сподіваюся, все
Тепер можна зрозуміти

321
00:16:52,220 --> 00:16:57,800
Тому це рішення чи це
функція так, що це таке.

322
00:16:57,800 --> 00:16:59,840
Будь трохи неясно з цього приводу?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ДОБРЕ.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> І ось тепер, якщо ви
хотів з черги, це

327
00:17:09,970 --> 00:17:15,240
де наша голова буде перехід
тому що, якщо ми повинні були з черги,

328
00:17:15,240 --> 00:17:17,030
ми не зняти кінець д.

329
00:17:17,030 --> 00:17:19,130
Ми хочемо, щоб з голови, вірно?

330
00:17:19,130 --> 00:17:24,260
Так що в підсумку, голова зміниться,
і тому, коли ви в чергу,

331
00:17:24,260 --> 00:17:26,800
Ви повинні стежити за
де ваша голова і ваш розмір

332
00:17:26,800 --> 00:17:29,450
повинні мати можливість вставити
в правильне положення.

333
00:17:29,450 --> 00:17:32,740
>> І тому, коли ви з черги,
Я також псевдокод його.

334
00:17:32,740 --> 00:17:35,480
Не соромтеся, якщо ви хочете
спробувати кодування це.

335
00:17:35,480 --> 00:17:36,980
Ви хочете, щоб перемістити голову, вірно?

336
00:17:36,980 --> 00:17:39,320
Якби я хотів, щоб з черги, я
буде рухатися голову над.

337
00:17:39,320 --> 00:17:40,800
Це буде голова.

338
00:17:40,800 --> 00:17:45,617
>> І наша поточний розмір буде
відняти, тому що ми більше не

339
00:17:45,617 --> 00:17:46,950
чотири елементи в матриці.

340
00:17:46,950 --> 00:17:51,370
У нас є тільки три, а потім ми хочемо
повернутися все було зберігати всередині

341
00:17:51,370 --> 00:17:56,260
глави, тому що ми хочемо, щоб це
Значення так, дуже схожа на стек.

342
00:17:56,260 --> 00:17:58,010
Просто ви приймаєте
з іншого місця,

343
00:17:58,010 --> 00:18:01,770
і у вас є, щоб передати свою покажчик
в іншому місці в якості результату.

344
00:18:01,770 --> 00:18:03,890
Логічно, кожен слідувати?

345
00:18:03,890 --> 00:18:05,690
Відмінно.

346
00:18:05,690 --> 00:18:10,156
>> ОК, так що ми збираємося трохи поговорити
більш докладно про пов'язаних списків

347
00:18:10,156 --> 00:18:13,280
тому що вони дуже, дуже цінний
для вас в ході цьому тижні

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Пов'язані списки, як ви, хлопці,
пам'ятаю, вони все

350
00:18:17,130 --> 00:18:22,570
є вузлами, які вузли впевнений
значення як значення і покажчик

351
00:18:22,570 --> 00:18:26,290
які пов'язані один з одним
за цими вказівниками.

352
00:18:26,290 --> 00:18:29,880
І тому від того, як структура
ми створюємо вузол тут ми

353
00:18:29,880 --> 00:18:33,569
є Int N, який є те, що
значення в магазині або струнного п

354
00:18:33,569 --> 00:18:35,610
або що ви хочете, щоб
це називають, напівкокс зірка н.

355
00:18:35,610 --> 00:18:41,482
Структура, вузол зірка, яка є покажчиком
що ви хочете, щоб у кожному вузлі,

356
00:18:41,482 --> 00:18:43,690
Ви будете мати, що
точка покажчик до наступного.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Ви будете мати голову
із зв'язаного списку, що це

359
00:18:50,040 --> 00:18:53,140
збирається вказують на решті
значення так далі, і так далі

360
00:18:53,140 --> 00:18:55,290
поки ви в кінцевому підсумку не дійдете до кінця.

361
00:18:55,290 --> 00:18:58,040
І це останній вузол просто
відбувається, щоб не мати покажчик.

362
00:18:58,040 --> 00:18:59,952
Це буде вказувати на
NULL, і що, коли

363
00:18:59,952 --> 00:19:01,910
ви знаєте, що вдарив
кінець вашої пов'язаного списку

364
00:19:01,910 --> 00:19:04,076
коли ваш останній покажчик
не вказує ні на що.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Так що ми збираємося йти трохи більше в
Глибина про те, як одне, можливо,

367
00:19:10,990 --> 00:19:12,400
пошук зв'язаний список.

368
00:19:12,400 --> 00:19:15,460
Пам'ятайте, що деякі з
Недоліками пов'язаних списків

369
00:19:15,460 --> 00:19:19,340
вірші масив щодо пошуків.

370
00:19:19,340 --> 00:19:22,565
Масив можна бінарний пошук, але
чому ви не можете зробити це у зв'язаному списку?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> АУДИТОРІЯ: Тому що вони всі пов'язані,
але ви зовсім не знаю, де

373
00:19:30,320 --> 00:19:31,330
[Нерозбірливо].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Пен: Так, саме так пам'ятаю
що блиск масиву

375
00:19:34,600 --> 00:19:37,190
було те, що у нас було
оперативний пристрій, де

376
00:19:37,190 --> 00:19:41,580
якби я хотів значення з індексу
шостій, я міг просто сказати індекс шостій,

377
00:19:41,580 --> 00:19:42,407
дайте мені це значення.

378
00:19:42,407 --> 00:19:45,240
І це тому, що масиви упорядковано
в безперервному просторі пам'яті

379
00:19:45,240 --> 00:19:48,020
в одному місці, в той час як
вид пов'язаних списків

380
00:19:48,020 --> 00:19:52,820
випадково перемежовуються усього,
і єдиний спосіб ви можете знайти одне

381
00:19:52,820 --> 00:19:56,890
через покажчик, який говорить вам,
адресу, де, що наступного вузол.

382
00:19:56,890 --> 00:20:00,290
>> І так, в результаті, єдиний спосіб
шукати у зв'язаному списку

383
00:20:00,290 --> 00:20:01,560
це лінійний пошук.

384
00:20:01,560 --> 00:20:05,890
Бо я точно не знаю, де
12-й значення у зв'язаному списку,

385
00:20:05,890 --> 00:20:08,780
Я повинен пройти повноту
цього зв'язаний список одного

386
00:20:08,780 --> 00:20:12,450
одна від голови до першого вузла,
до другого вузла, третьому вузлу,

387
00:20:12,450 --> 00:20:17,690
весь шлях вниз, поки я, нарешті, не отримують
де цей вузол, я дивлюся на це.

388
00:20:17,690 --> 00:20:22,110
І тому в цьому сенсі, пошук
на зв'язаний список завжди п.

389
00:20:22,110 --> 00:20:23,040
Це завжди п.

390
00:20:23,040 --> 00:20:25,690
Це завжди в лінійному часу.

391
00:20:25,690 --> 00:20:28,470
>> І тому код, в якому
ми реалізуємо це, і це

392
00:20:28,470 --> 00:20:32,620
трохи нового для вас, хлопці, так як ви
Хлопці насправді не говорив про або коли-небудь

393
00:20:32,620 --> 00:20:35,000
переглянуто покажчики в тому, як
пошук за допомогою покажчиків,

394
00:20:35,000 --> 00:20:37,670
таким чином, ми будемо йти через
це дуже, дуже повільно.

395
00:20:37,670 --> 00:20:40,200
Так пошук логічний, право,
давайте уявимо, що ми хочемо

396
00:20:40,200 --> 00:20:42,820
створити функцію з ім'ям
Пошук, який повертає істинне

397
00:20:42,820 --> 00:20:46,820
якщо ви знайшли значення всередині пов'язаний
список, і повертає помилкове в іншому випадку.

398
00:20:46,820 --> 00:20:50,030
Вузол зірка список
В даний час тільки покажчик

399
00:20:50,030 --> 00:20:52,960
до першого пункту у вашому пов'язаного списку.

400
00:20:52,960 --> 00:20:56,700
INT п значення, що ви
пошук в цьому списку.

401
00:20:56,700 --> 00:20:58,770
>> Так вузол зірка покажчик дорівнює список.

402
00:20:58,770 --> 00:21:00,970
Це означає, що ми встановлюємо
і створення покажчик

403
00:21:00,970 --> 00:21:03,592
до цього першого вузлу всередині списку.

404
00:21:03,592 --> 00:21:04,300
Всі зі мною?

405
00:21:04,300 --> 00:21:06,530
Так що, якщо ми повинні були піти
сюди, я б

406
00:21:06,530 --> 00:21:13,850
ініціалізації покажчик, який вказує на
глава незалежно, що список.

407
00:21:13,850 --> 00:21:18,600
>> І те, як тільки ви отримаєте тут,
в той час як покажчик не дорівнює нулю,

408
00:21:18,600 --> 00:21:22,160
так що це петля, в якій ми
буде згодом проходження

409
00:21:22,160 --> 00:21:25,940
решта нашому списку, тому що те, що
відбувається, коли покажчик дорівнює NULL?

410
00:21:25,940 --> 00:21:27,550
Ми знаємо, що have--

411
00:21:27,550 --> 00:21:28,450
>> АУДИТОРІЯ: [нерозбірливо]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Пен: Рівне, тому ми знаємо, що
ми досягли кінця списку, вірно?

413
00:21:31,491 --> 00:21:34,470
Якщо ви йдете сюди, кожен вузол
повинен бути спрямований на інший вузол

414
00:21:34,470 --> 00:21:36,550
і так далі, і так далі
доки натиснете зрештою

415
00:21:36,550 --> 00:21:41,589
хвіст вашого пов'язаного списку,
який має покажчик, який просто

416
00:21:41,589 --> 00:21:43,130
не вказують, ніж у будь-якому іншому немає.

417
00:21:43,130 --> 00:21:47,510
І так ви знаєте, що в основному
Ваш список є ще до

418
00:21:47,510 --> 00:21:50,900
до покажчика не чинить не рівні
нуль, тому що колись він дорівнює нулю,

419
00:21:50,900 --> 00:21:53,310
Ви знаєте, що немає більше матеріалу.

420
00:21:53,310 --> 00:21:56,930
>> Так що це петля, в якій ми
матиме реальну пошуку.

421
00:21:56,930 --> 00:22:01,690
І якщо pointer-- ви бачите
що вид функції стрілка там?

422
00:22:01,690 --> 00:22:06,930
Так що, якщо покажчик вказує п, якщо
покажчик на п дорівнює дорівнює п,

423
00:22:06,930 --> 00:22:09,180
так, що означає, що якщо
покажчик, що ви

424
00:22:09,180 --> 00:22:13,420
пошуку на кінці кожного
вузол фактично дорівнює значенню

425
00:22:13,420 --> 00:22:15,990
Ви шукаєте, то
Ви хочете, щоб повернутися правда.

426
00:22:15,990 --> 00:22:19,280
Так в основному, якщо ви знаходитесь на вузлі, який
має значення, що ви шукаєте,

427
00:22:19,280 --> 00:22:23,550
Ви знаєте, що ви були
в змозі успішно шукати.

428
00:22:23,550 --> 00:22:27,150
>> В іншому випадку, ви хочете встановити
покажчик на наступний вузол.

429
00:22:27,150 --> 00:22:28,850
Це те, що ця лінія тут робить.

430
00:22:28,850 --> 00:22:31,750
Покажчик дорівнює покажчик поруч.

431
00:22:31,750 --> 00:22:33,360
Всі бачити, як це працює?

432
00:22:33,360 --> 00:22:36,580
>> І по суті, ви збираєтеся просто
пройти повноту списку,

433
00:22:36,580 --> 00:22:41,920
скидання покажчик кожного разу до
Ви в кінцевому рахунку потрапив в кінці списку.

434
00:22:41,920 --> 00:22:45,030
І ви не знаєте, що їсти не
більше вузлів для пошуку по,

435
00:22:45,030 --> 00:22:47,999
а потім ви можете повернутися помилковим
тому що ви знаєте, що, ну, добре,

436
00:22:47,999 --> 00:22:50,540
якщо я був в змозі шукати
через повністю списку.

437
00:22:50,540 --> 00:22:54,530
Якщо в цьому прикладі, якщо б я хотів
шукати значення 10,

438
00:22:54,530 --> 00:22:57,250
і я починаю в голові, і
Я шукаю всю дорогу вниз,

439
00:22:57,250 --> 00:23:00,550
і я в кінці кінців отримав на це, що
покажчик, який вказує на NULL,

440
00:23:00,550 --> 00:23:04,415
Я знаю, що, лайно, я думаю, 10 не перебуває у
цей список, тому що я не міг знайти його.

441
00:23:04,415 --> 00:23:06,520
І я в кінці списку.

442
00:23:06,520 --> 00:23:11,040
І в цьому випадку ви знаєте,
Я збираюся повернутися помилковим.

443
00:23:11,040 --> 00:23:12,900
>> Нехай це замочити в для трохи.

444
00:23:12,900 --> 00:23:17,350
Це буде досить
важливо для вашого PSET.

445
00:23:17,350 --> 00:23:21,140
Логіка дуже проста, можливо
синтаксично тільки його реалізації.

446
00:23:21,140 --> 00:23:23,365
Ви, хлопці, хочете, щоб
Переконайтеся, що ви розумієте.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Прохолодний.

449
00:23:27,650 --> 00:23:32,560
>> Отже, як ми б
вставки вузлів, право,

450
00:23:32,560 --> 00:23:35,380
в списку, бо пам'ятаю,
які те, що переваги

451
00:23:35,380 --> 00:23:39,230
мати зв'язаний список проти
масив з погляду зберігання?

452
00:23:39,230 --> 00:23:41,110
>> АУДИТОРІЯ: Це динамічний,
так легше, метою яких

453
00:23:41,110 --> 00:23:43,180
>> ANDI Пен: Рівне,
так що це динамічний, який

454
00:23:43,180 --> 00:23:46,880
означає, що він може розширюватися і стискатися
в залежності від потреб користувача.

455
00:23:46,880 --> 00:23:56,570
І так, в цьому сенсі, ми не повинні
витрачати непотрібного пам'ять, тому що я

456
00:23:56,570 --> 00:24:00,850
якщо я не знаю, скільки я хочу значення
в магазині, це не має сенсу для мене

457
00:24:00,850 --> 00:24:04,310
створити масив, тому що
якщо я хочу, щоб зберігати 10 значень

458
00:24:04,310 --> 00:24:08,380
і створити масив +1000, це
багато даремно пам'ять, виділено.

459
00:24:08,380 --> 00:24:11,180
Ось чому ми хочемо використовувати пов'язаний
Список, щоб мати можливість динамічно

460
00:24:11,180 --> 00:24:13,860
змінити або зменшити розмір нашої.

461
00:24:13,860 --> 00:24:17,040
>> І так, що робить вставку
трохи більш складним.

462
00:24:17,040 --> 00:24:20,810
Оскільки ми не можемо довільно звертатися до елементів
так, що ми масиву.

463
00:24:20,810 --> 00:24:24,270
Якщо я хочу, щоб вставити елемент
в сьомий індексу,

464
00:24:24,270 --> 00:24:26,930
Я просто не можу вставити
в сьомий індексу.

465
00:24:26,930 --> 00:24:30,020
На пов'язаному списку, це не
досить легко працювати, як,

466
00:24:30,020 --> 00:24:34,947
і тому, якщо ми хотіли, щоб вставити
один тут, у зв'язаному списку,

467
00:24:34,947 --> 00:24:36,280
візуально, це дуже легко побачити.

468
00:24:36,280 --> 00:24:39,363
Ми просто хочемо, щоб вставити його прямо там,
на самому початку списку,

469
00:24:39,363 --> 00:24:40,840
відразу після голови.

470
00:24:40,840 --> 00:24:44,579
>> Але те, яким чином ми повинні перепризначити
покажчики це трохи заплутаним

471
00:24:44,579 --> 00:24:47,620
або, за логікою, це має сенс, але
Ви хочете, щоб переконатися, що у вас є

472
00:24:47,620 --> 00:24:50,250
повністю вниз, тому що
останнє, що ви хочете

473
00:24:50,250 --> 00:24:52,990
це перепризначити указки
так, що ми тут робимо.

474
00:24:52,990 --> 00:24:58,170
Якщо ви разименовать
покажчик з голови до 1,

475
00:24:58,170 --> 00:25:01,086
то все раптом
інша частина вашого пов'язаного списку

476
00:25:01,086 --> 00:25:04,680
втрачається, тому що у вас є насправді не
створено тимчасовий нічого.

477
00:25:04,680 --> 00:25:06,220
Ось вказав на 2.

478
00:25:06,220 --> 00:25:10,080
При передачі покажчика, то
Решта свій список повністю втрачені.

479
00:25:10,080 --> 00:25:13,310
Отже, ви хочете бути
дуже, дуже обережні

480
00:25:13,310 --> 00:25:17,010
спочатку призначити
Покажчик з якою вам

481
00:25:17,010 --> 00:25:20,150
вставити в там, де
Ви хочете, і тоді ви

482
00:25:20,150 --> 00:25:22,710
може разименовать решті список.

483
00:25:22,710 --> 00:25:25,250
>> Таким чином, це відноситься і до скрізь, де
Ви намагаєтеся вставити в.

484
00:25:25,250 --> 00:25:27,520
Якщо ви хочете, щоб вставити на
голова, якщо ви хочете, щоб відповісти тут,

485
00:25:27,520 --> 00:25:29,455
якщо ви хочете вставити в
кінець, ну, кінець я

486
00:25:29,455 --> 00:25:30,910
думаю, ви б просто
немає покажчик, але ви

487
00:25:30,910 --> 00:25:33,830
хочете, щоб переконатися, що ви не
втратити решта вашого списку.

488
00:25:33,830 --> 00:25:36,640
Ви завжди хочете, щоб переконатися,
Ваш новий вузол вказуючи

489
00:25:36,640 --> 00:25:39,330
до все, що ви
вставити в,

490
00:25:39,330 --> 00:25:42,170
а потім ви можете додати ланцюжок далі.

491
00:25:42,170 --> 00:25:43,330
Все ясно?

492
00:25:43,330 --> 00:25:45,427
>> Це буде
один з реальних проблем.

493
00:25:45,427 --> 00:25:48,010
Один з найголовніших питань
Ви будете мати на вашому PSET

494
00:25:48,010 --> 00:25:51,340
є те, що ви збираєтеся, щоб спробувати створити
зв'язаний список і додати речі,

495
00:25:51,340 --> 00:25:53,340
але потім просто втратити
інша частина вашого пов'язаного списку.

496
00:25:53,340 --> 00:25:54,900
І ви будете, як я
Не знаю, чому це відбувається?

497
00:25:54,900 --> 00:25:58,040
І це біль, щоб пройти через
і шукати всі ваші покажчики.

498
00:25:58,040 --> 00:26:02,100
>> І я гарантую вам на цьому PSET,
писати і малювати ці вузли з

499
00:26:02,100 --> 00:26:03,344
буде дуже, дуже корисно.

500
00:26:03,344 --> 00:26:06,010
Таким чином, ви можете повністю відстежувати
де всі ваші покажчики,

501
00:26:06,010 --> 00:26:08,540
що відбувається не так,
де всі ваші вузли,

502
00:26:08,540 --> 00:26:12,660
те, що ви повинні зробити, щоб отримати доступ до або
вставити або видалити або будь-якого з них.

503
00:26:12,660 --> 00:26:14,550
Все добре з цим?

504
00:26:14,550 --> 00:26:15,050
Прохолодний.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Так що, якщо ми хотіли подивитися на код?

507
00:26:22,600 --> 00:26:24,470
О, я не знаю, якщо ми
можна побачити the-- OK, так

508
00:26:24,470 --> 00:26:27,940
у верхній все це є функцією
імені вставка, де ми хочемо

509
00:26:27,940 --> 00:26:31,365
вставити Int N у зв'язаному списку.

510
00:26:31,365 --> 00:26:32,740
Ми збираємося пройти через це.

511
00:26:32,740 --> 00:26:34,770
Це багато коду, багато нового синтаксису.

512
00:26:34,770 --> 00:26:36,220
Ми в порядку.

513
00:26:36,220 --> 00:26:39,120
>> Так на вершині, коли
ми хочемо, щоб створити що-небудь

514
00:26:39,120 --> 00:26:42,380
що нам потрібно зробити, особливо якщо ви
Хочете його не можна зберігати в стеці

515
00:26:42,380 --> 00:26:43,920
але в купі?

516
00:26:43,920 --> 00:26:45,460
Ми йдемо в Танос, вірно?

517
00:26:45,460 --> 00:26:48,240
Отже, ми збираємося створити покажчик.

518
00:26:48,240 --> 00:26:52,074
Вузол, покажчик, нові одно
Танос розмір вузла

519
00:26:52,074 --> 00:26:53,740
тому що ми хочемо, що вузол буде створений.

520
00:26:53,740 --> 00:26:56,720
Ми хочемо, щоб кількість
пам'яті, що вузол займає

521
00:26:56,720 --> 00:26:59,300
щоб бути відведено для
Створення нового вузла.

522
00:26:59,300 --> 00:27:02,270
>> А потім ми збираємося, щоб перевірити,
побачити, якщо нові одно дорівнює нулю.

523
00:27:02,270 --> 00:27:03,370
Пам'ятайте, що ми говорили?

524
00:27:03,370 --> 00:27:06,470
Що б ви не Танос,
Що необхідно завжди робити?

525
00:27:06,470 --> 00:27:09,490
Ви завжди повинні перевірити, щоб побачити
чи ні, що це NULL.

526
00:27:09,490 --> 00:27:13,620
>> Наприклад, якщо ваша операційна
система була повністю заповнена,

527
00:27:13,620 --> 00:27:17,060
якщо ви не мали більше пам'яті на
все, і ви намагаєтеся Танос,

528
00:27:17,060 --> 00:27:18,410
це повернеться NULL для вас.

529
00:27:18,410 --> 00:27:21,094
І тому, якщо ви намагаєтеся використовувати його
коли він був направлений на нуль,

530
00:27:21,094 --> 00:27:23,260
ви не збираєтеся, щоб в стані
для доступу до цієї інформації.

531
00:27:23,260 --> 00:27:27,010
І так, як, наприклад, ми хотіли зробити
Переконайтеся, що всякий раз, коли ви mallocing,

532
00:27:27,010 --> 00:27:30,500
Ви завжди перевіряти, якщо
що пам'ять дано вам є недійсним.

533
00:27:30,500 --> 00:27:33,670
А якщо це не так, то ми можемо рухатися
на з іншою частиною нашого коду.

534
00:27:33,670 --> 00:27:36,140
>> Отже, ми збираємося, щоб
ініціалізувати новий вузол.

535
00:27:36,140 --> 00:27:39,050
Ми збираємося зробити новий п дорівнює п.

536
00:27:39,050 --> 00:27:42,390
І тоді ми будемо робити
встановити новий покажчик на новий

537
00:27:42,390 --> 00:27:46,900
в нуль, тому що зараз ми не
хочу що-небудь для того, щоб вказати на.

538
00:27:46,900 --> 00:27:48,755
Ми не маємо ні найменшого поняття де
він збирається поставити вас,

539
00:27:48,755 --> 00:27:50,630
а потім, якщо ми хочемо, щоб
вставте його в голові,

540
00:27:50,630 --> 00:27:53,820
то ми можемо передати
покажчик на голову.

541
00:27:53,820 --> 00:27:58,530
Всі слідувати логіці чи
де, що відбувається?

542
00:27:58,530 --> 00:28:02,502
>> Все, що ми робимо, створюючи новий
вузол, встановивши покажчик на NULL,

543
00:28:02,502 --> 00:28:04,210
а потім перепризначення
це в голові, якщо ми

544
00:28:04,210 --> 00:28:06,320
знаю, що ми хочемо, щоб вставити його в голову.

545
00:28:06,320 --> 00:28:09,420
А потім голова буде
вказують на те нового вузла.

546
00:28:09,420 --> 00:28:11,060
Все в порядку з цим?

547
00:28:11,060 --> 00:28:12,380
>> Так що це двоступінчастий процес.

548
00:28:12,380 --> 00:28:14,760
Ви повинні спочатку призначити
все, що ви створюєте.

549
00:28:14,760 --> 00:28:18,260
Встановлено, що покажчик на
довідка, а потім вам

550
00:28:18,260 --> 00:28:21,400
може роду разименованія
перший покажчик

551
00:28:21,400 --> 00:28:22,972
і вказати його до новому вузлу.

552
00:28:22,972 --> 00:28:25,680
Де ви хочете, щоб вставити його,
що логіка збирається провести вірно.

553
00:28:25,680 --> 00:28:27,530
>> Це ніби як привласнення
тимчасові змінні.

554
00:28:27,530 --> 00:28:28,700
Пам'ятайте, у вас є
щоб переконатися, що вас

555
00:28:28,700 --> 00:28:30,346
не втрачати, якщо ви підкачки.

556
00:28:30,346 --> 00:28:33,470
Ви хочете, щоб переконатися, що у вас є
тимчасова змінна, що вид зберігає

557
00:28:33,470 --> 00:28:35,620
трек де цієї речі
зберігається, так що ви

558
00:28:35,620 --> 00:28:41,190
не втрачають будь-яке значення в ході
з, як возитися з ним.

559
00:28:41,190 --> 00:28:42,710
>> ОК, так що код буде тут.

560
00:28:42,710 --> 00:28:45,020
Ви, хлопці, погляньте після розділу.

561
00:28:45,020 --> 00:28:48,060
Це буде там.

562
00:28:48,060 --> 00:28:50,280
>> Так що я думаю, як робить
це відрізняється, якщо ми хотіли

563
00:28:50,280 --> 00:28:52,300
вставити в середині або в кінці?

564
00:28:52,300 --> 00:28:57,892
Хто-небудь є ідея про те, що це
псевдокод, як логічне посиланням

565
00:28:57,892 --> 00:29:00,350
що ми б хотіли, якщо ми
щоб вставити його в середині?

566
00:29:00,350 --> 00:29:03,391
Так що, якщо ми хотіли, щоб вставити її на
голова, все, що ми зробити, це створити новий вузол.

567
00:29:03,391 --> 00:29:06,311
Ми встановлюємо покажчик, що
Новий вузол який голові,

568
00:29:06,311 --> 00:29:08,310
а потім ми встановлюємо голову
з новим вузлом, правильно?

569
00:29:08,310 --> 00:29:11,560
Якби ми хотіли, щоб вставити його в середині
зі списку, що б ми повинні робити?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> АУДИТОРІЯ: Це буде як і раніше
бути аналогічний процес

572
00:29:16,110 --> 00:29:19,114
з, як присвоєння і покажчик
то призначення цього покажчика,

573
00:29:19,114 --> 00:29:20,530
але ми повинні знайти там.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Пен: Рівне, так точно
той же самий процес, крім вас

575
00:29:23,560 --> 00:29:27,820
повинні знайти, де саме ви
хочу, щоб новий покажчик, щоб піти в,

576
00:29:27,820 --> 00:29:44,790
так що якщо я хочу, щоб вставити в
середина пов'язані list-- ОК,

577
00:29:44,790 --> 00:29:46,370
давайте говорити, що наш зв'язаний список.

578
00:29:46,370 --> 00:29:49,500
Якщо ми хочемо, щоб вставити її прямо тут,
ми збираємося створити новий вузол.

579
00:29:49,500 --> 00:29:50,520
Ми збираємося Танос.

580
00:29:50,520 --> 00:29:52,220
Ми збираємося створити новий вузол.

581
00:29:52,220 --> 00:29:55,940
Ми збираємося призначити
покажчик цього вузла тут.

582
00:29:55,940 --> 00:29:58,335
>> Але проблема, яка відрізняється
звідки голова

583
00:29:58,335 --> 00:30:00,490
є те, що ми точно знали,
де голова.

584
00:30:00,490 --> 00:30:01,930
Це було прямо на першій, чи не так?

585
00:30:01,930 --> 00:30:04,870
Але тут ми повинні відслідковувати
де ми вставивши його в.

586
00:30:04,870 --> 00:30:07,930
Якщо ми вставляємо наш
вузол тут, у нас є

587
00:30:07,930 --> 00:30:12,270
щоб переконатися, що
одним попередня до цього вузла

588
00:30:12,270 --> 00:30:14,172
це той, який присвоює покажчик.

589
00:30:14,172 --> 00:30:16,380
Отже, ви повинні вид
відслідковувати дві речі.

590
00:30:16,380 --> 00:30:19,420
Якщо вам відстежувати, де це
вузол в даний час вставки в.

591
00:30:19,420 --> 00:30:23,280
Ви також повинні відстежувати, де
попередній вузол, який ви дивитеся на

592
00:30:23,280 --> 00:30:24,340
Також там.

593
00:30:24,340 --> 00:30:25,830
Все добре з цим?

594
00:30:25,830 --> 00:30:26,500
ДОБРЕ.

595
00:30:26,500 --> 00:30:28,000
>> Як щодо вставки врешті-решт?

596
00:30:28,000 --> 00:30:34,220
Якби я хотів, щоб додати його here-- якщо я хотів
щоб додати новий вузол в кінець списку,

597
00:30:34,220 --> 00:30:37,009
як я міг би йти про те, що робити?

598
00:30:37,009 --> 00:30:39,300
АУДИТОРІЯ: Так собі, то
останній вказали на нуль.

599
00:30:39,300 --> 00:30:40,960
ANDI Пен: Так.

600
00:30:40,960 --> 00:30:43,560
Точно, так що це одне
В даний час відзначається знати,

601
00:30:43,560 --> 00:30:46,720
і тому я думаю, в цьому сенсі, це
дуже легко додати до кінця списку.

602
00:30:46,720 --> 00:30:51,810
Все, що вам потрібно зробити, це встановити його
дорівнює нулю, а потім бум.

603
00:30:51,810 --> 00:30:53,070
Прямо там, дуже легко.

604
00:30:53,070 --> 00:30:53,960
Дуже просто.

605
00:30:53,960 --> 00:30:56,430
>> Дуже схожий на
голову, але логічно вас

606
00:30:56,430 --> 00:30:59,690
хочете, щоб переконатися, що кроки,
ви берете до робити все це,

607
00:30:59,690 --> 00:31:01,500
ви прямуєте.

608
00:31:01,500 --> 00:31:04,420
Це дуже легко, в середині
ваш код, загрузнути в,

609
00:31:04,420 --> 00:31:05,671
ой, у мене так багато покажчиків.

610
00:31:05,671 --> 00:31:07,461
Я не знаю, де
що-небудь, вказуючи на.

611
00:31:07,461 --> 00:31:09,170
Я навіть не знаю, який вузол я на.

612
00:31:09,170 --> 00:31:11,490
Що відбувається?

613
00:31:11,490 --> 00:31:13,620
>> Розслабтеся, заспокойтеся, зробіть глибокий вдих.

614
00:31:13,620 --> 00:31:15,530
Намалюйте свій зв'язаний список.

615
00:31:15,530 --> 00:31:18,800
Якщо ви говорите, я знати, де саме
Мені потрібно вставити це в

616
00:31:18,800 --> 00:31:22,970
і я точно знаю, як передати мій
покажчики, набагато, набагато легше уявити

617
00:31:22,970 --> 00:31:27,200
out-- набагато простіше не
заблукати в багів в коді.

618
00:31:27,200 --> 00:31:29,410
Все в порядку з цим?

619
00:31:29,410 --> 00:31:31,380
ДОБРЕ.

620
00:31:31,380 --> 00:31:35,120
>> Тому я думаю, поняття, що ми не
дійсно говорили про досі,

621
00:31:35,120 --> 00:31:38,131
і я думаю, ви, ймовірно,
не зустрінете багато yet--

622
00:31:38,131 --> 00:31:40,880
це свого роду передової concept--
є те, що ми насправді є дані

623
00:31:40,880 --> 00:31:43,900
Структура називається подвійно зв'язаний список.

624
00:31:43,900 --> 00:31:46,390
Отже, як ви, хлопці, можете бачити,
все, що ми робимо, створюючи

625
00:31:46,390 --> 00:31:50,400
фактичне значення, додатковий
покажчик на кожен з наших вузлів

626
00:31:50,400 --> 00:31:52,660
що також вказує на попередній вузол.

627
00:31:52,660 --> 00:31:58,170
Так ми не тільки маємо нашу
вузли вказують на наступний.

628
00:31:58,170 --> 00:32:01,430
Вони також вказують на попередній.

629
00:32:01,430 --> 00:32:04,310
Я збираюся ігнорувати ці два прямо зараз.

630
00:32:04,310 --> 00:32:06,740
>> Отже у вас є ланцюжок
що може рухатися в обох напрямках,

631
00:32:06,740 --> 00:32:09,630
і тоді це трохи легше
логічно слідувати.

632
00:32:09,630 --> 00:32:11,896
Як тут, а
відстеження, о, я

633
00:32:11,896 --> 00:32:14,520
повинні знати, що цей вузол
той, який я повинен передати,

634
00:32:14,520 --> 00:32:17,532
Я можу просто піти тут і
просто витягти попередній.

635
00:32:17,532 --> 00:32:19,490
Тоді я точно знаю, де
тобто, а потім вас

636
00:32:19,490 --> 00:32:21,130
не повинні перетинати
Сукупність пов'язаного списку.

637
00:32:21,130 --> 00:32:22,180
Це трохи легше.

638
00:32:22,180 --> 00:32:24,960
>> Але таким чином, ви повинні подвійно
кількість вказівників,

639
00:32:24,960 --> 00:32:26,960
це в два рази більше пам'яті.

640
00:32:26,960 --> 00:32:28,950
Це багато вказівників, щоб відстежувати.

641
00:32:28,950 --> 00:32:32,140
Це трохи більш складним, але це
трохи більш дружнім до користувача залежно

642
00:32:32,140 --> 00:32:34,080
про те, що ви намагаєтеся досягти.

643
00:32:34,080 --> 00:32:36,910
>> Таким чином, це тип даних,
Структура повністю існує,

644
00:32:36,910 --> 00:32:40,280
і структура для дуже, дуже
просто, за винятком все, що ви маючи це,

645
00:32:40,280 --> 00:32:43,850
а не просто покажчик на наступний,
у вас також є покажчик на попередній.

646
00:32:43,850 --> 00:32:45,940
От і вся різниця була.

647
00:32:45,940 --> 00:32:47,740
Все добре з цим?

648
00:32:47,740 --> 00:32:48,240
Прохолодний.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Гаразд, так що тепер я
дійсно витратити, напевно,

651
00:32:53,280 --> 00:32:56,870
як від 15 до 20 хвилин або навалом
в решту часу в розділі

652
00:32:56,870 --> 00:32:58,360
говорити про хеш-таблицях.

653
00:32:58,360 --> 00:33:02,590
Як багато з вас, хлопці,
прочитав pset5 специфікації?

654
00:33:02,590 --> 00:33:03,620
Гаразд, добре.

655
00:33:03,620 --> 00:33:06,160
Це вище, ніж 50%, як правило.

656
00:33:06,160 --> 00:33:07,560
Все добре.

657
00:33:07,560 --> 00:33:10,345
>> Отже, як ви, хлопці, побачите,
Ви задача в pset5

658
00:33:10,345 --> 00:33:16,790
буде реалізувати словник
де ви завантажити більше 140000 слів

659
00:33:16,790 --> 00:33:20,610
що ми даємо вам і перевірка орфографії
це проти всього тексту.

660
00:33:20,610 --> 00:33:22,580
Ми дамо вам випадкових
шт літератури.

661
00:33:22,580 --> 00:33:23,520
Ми дамо вам Одіссея.

662
00:33:23,520 --> 00:33:24,561
Ми дамо вам Іліаду.

663
00:33:24,561 --> 00:33:26,350
Ми дамо вам Остін Пауерс.

664
00:33:26,350 --> 00:33:28,220
>> І ваше завдання
буде перевірка орфографії

665
00:33:28,220 --> 00:33:31,760
кожне слово всього
з тих словників

666
00:33:31,760 --> 00:33:34,960
по суті, з нашої орфографії.

667
00:33:34,960 --> 00:33:38,620
І так є кілька частин
створення цієї PSET,

668
00:33:38,620 --> 00:33:41,970
Спочатку ви хочете бути
в стані фактично завантажити

669
00:33:41,970 --> 00:33:43,970
всі слова в ваш
словник, а потім вам

670
00:33:43,970 --> 00:33:45,530
хочу, щоб мати можливість
орфографії і всі з них.

671
00:33:45,530 --> 00:33:48,780
І так, як, наприклад, ви збираєтеся вимагати
структура даних, яка може зробити це швидко

672
00:33:48,780 --> 00:33:50,790
і ефективно і динамічно.

673
00:33:50,790 --> 00:33:52,900
>> Тому я вважаю, найпростіший
спосіб зробити це, вам

674
00:33:52,900 --> 00:33:55,010
ймовірно створити масив, вірно?

675
00:33:55,010 --> 00:33:58,910
Найпростіший спосіб зберігання вас
можна створити масив 140000 слів

676
00:33:58,910 --> 00:34:03,400
і просто розмістити їх там, і всі
потім пройти їх бінарного пошуку

677
00:34:03,400 --> 00:34:06,780
або виборів або не--
шкода, що це сортування.

678
00:34:06,780 --> 00:34:10,729
Ви можете сортувати їх, а потім пройти їх
двійковий пошук або просто лінійний пошук

679
00:34:10,729 --> 00:34:13,730
і тільки остаточні слова, але
займає величезну кількість пам'яті,

680
00:34:13,730 --> 00:34:15,190
і це не дуже ефективно.

681
00:34:15,190 --> 00:34:18,350
>> І таким чином ми збираємося почати
говорити про способи виготовлення

682
00:34:18,350 --> 00:34:20,110
наша тривалість більш ефективним.

683
00:34:20,110 --> 00:34:23,190
І наша мета, щоб отримати
постійна часу, де

684
00:34:23,190 --> 00:34:25,810
це майже як масиви, де
у вас є миттєвий доступ.

685
00:34:25,810 --> 00:34:28,560
Якби я хотів, щоб шукати що-небудь,
Я хочу, щоб мати можливість просто,

686
00:34:28,560 --> 00:34:30,810
бум, знайти його точно, і витягнути його.

687
00:34:30,810 --> 00:34:34,100
І так структура, в якій
ми будемо стає дуже близько

688
00:34:34,100 --> 00:34:37,569
щоб бути в змозі отримати доступ до постійних
Час, це Святий Грааль

689
00:34:37,569 --> 00:34:41,370
в програмуванні постійного
час називається хеш-таблиці.

690
00:34:41,370 --> 00:34:45,370
І так Девід згадувалося раніше
[Нерозбірливо] трохи в лекції,

691
00:34:45,370 --> 00:34:49,100
але ми збираємося, щоб дійсно
занурення в глибокий цьому тижні

692
00:34:49,100 --> 00:34:51,780
на шматок, який відносно
як хеш-таблиця працює.

693
00:34:51,780 --> 00:34:53,949
>> Так чином, що хеш
таблиця роботи, наприклад,

694
00:34:53,949 --> 00:35:00,230
якби я хотів, щоб зберегти купу словами,
купа слів в англійській мові,

695
00:35:00,230 --> 00:35:02,940
Я теоретично може помістити
банан, яблуко, ківі, манго, пара,

696
00:35:02,940 --> 00:35:04,980
і диня все тільки на масиві.

697
00:35:04,980 --> 00:35:07,044
Всі вони могли вписатися і бути знайти.

698
00:35:07,044 --> 00:35:09,210
Це було б свого роду болю
пошук і доступ через,

699
00:35:09,210 --> 00:35:12,920
але простий спосіб зробити це полягає в
що ми можемо створити насправді структура

700
00:35:12,920 --> 00:35:15,680
називається хеш-таблиця, де ми хеш.

701
00:35:15,680 --> 00:35:19,880
Ми біжимо всі наші ключі через
хеш-функція, рівняння,

702
00:35:19,880 --> 00:35:22,600
Виходить, що їх усі в
якась цінність

703
00:35:22,600 --> 00:35:28,740
що тоді ми можемо зберігати на
суті масив пов'язаного списку.

704
00:35:28,740 --> 00:35:32,570
>> І ось, якщо ми хочемо
для зберігання англійські слова,

705
00:35:32,570 --> 00:35:37,250
ми могли потенційно просто, я не
знаєте, перетворити всі перші букви

706
00:35:37,250 --> 00:35:39,630
в якийсь номер.

707
00:35:39,630 --> 00:35:43,140
І тому, наприклад, якби я хотів
А бути синонімом apple--

708
00:35:43,140 --> 00:35:47,460
або з індексом 0, а
У синонімом 1,

709
00:35:47,460 --> 00:35:51,030
ми можемо мати 26 записів
що може просто зберігати

710
00:35:51,030 --> 00:35:53,610
всі букви
алфавіт, що ми почнемо с.

711
00:35:53,610 --> 00:35:56,130
І тоді ми можемо мати
яблуко на індексом 0.

712
00:35:56,130 --> 00:35:59,160
Ми можемо мати банан індексу
1, диня в індексі 2,

713
00:35:59,160 --> 00:36:00,540
і так далі, і так далі.

714
00:36:00,540 --> 00:36:04,460
І таким чином, якщо я хотів, щоб пошук
мій хеш-таблиця і доступ яблуко,

715
00:36:04,460 --> 00:36:07,560
Я знаю, яблуко починається з
Л-і я точно знаю,

716
00:36:07,560 --> 00:36:10,860
що вона повинна бути і хеш
Таблиця з індексом 0, тому що

717
00:36:10,860 --> 00:36:13,620
функції, присвоєні.

718
00:36:13,620 --> 00:36:16,572
>> Так що я не знаю, ми
програма користувача, де

719
00:36:16,572 --> 00:36:18,780
Ви будете платити з
arbitrarily-- не довільно,

720
00:36:18,780 --> 00:36:22,530
в спробі задумливо
думати про хороше рівнянь

721
00:36:22,530 --> 00:36:25,460
щоб мати можливість поширюватися
всі ваші значень

722
00:36:25,460 --> 00:36:29,370
таким чином, вони можуть легко отримати доступ до
це пізніше з як рівняння

723
00:36:29,370 --> 00:36:31,130
що ви, самі, знаєте.

724
00:36:31,130 --> 00:36:35,210
Таким чином, в сенсі, якщо я хотів, щоб перейти до
манго, я знаю, о, це починається з м.

725
00:36:35,210 --> 00:36:37,134
Вона повинна бути в індексі 12.

726
00:36:37,134 --> 00:36:38,800
Я не доведеться шукати у всьому.

727
00:36:38,800 --> 00:36:42,080
Я знаю, exactly-- я міг би просто піти в
індекс 12 і тягнути це.

728
00:36:42,080 --> 00:36:45,520
>> Все ясно, як
Функція Hash Table працює?

729
00:36:45,520 --> 00:36:48,380
Це свого роду просто більш складний масив.

730
00:36:48,380 --> 00:36:50,010
Це все, що є.

731
00:36:50,010 --> 00:36:51,630
ДОБРЕ.

732
00:36:51,630 --> 00:36:57,690
>> Так що я думаю, що ми зіткнулися з
це питання, що

733
00:36:57,690 --> 00:37:06,390
відбудеться, якщо у вас є кілька речей,
які дають вам той же індекс?

734
00:37:06,390 --> 00:37:10,570
Так би мовити, нашу функцію, все це
зробив вважати, що перший лист

735
00:37:10,570 --> 00:37:14,490
і перетворити це в
Відповідний 0 до 25 Індекс.

736
00:37:14,490 --> 00:37:17,137
Це абсолютно нормально, якщо
є тільки один з кожного.

737
00:37:17,137 --> 00:37:18,970
Але другий ви починаєте
мають більше, ви

738
00:37:18,970 --> 00:37:20,910
буде мати те, що називається зіткнення.

739
00:37:20,910 --> 00:37:25,580
>> Так що, якщо я намагаюся вставити поховати в хеш
таблиця, вже банан на ньому,

740
00:37:25,580 --> 00:37:27,870
що станеться, коли
Ви намагаєтеся вставити, що?

741
00:37:27,870 --> 00:37:30,930
Погані речі, бо банан
вже існує в індексі

742
00:37:30,930 --> 00:37:33,800
що ви хочете, щоб зберігати його в.

743
00:37:33,800 --> 00:37:35,560
Беррі роду, як, ах, що ж мені робити?

744
00:37:35,560 --> 00:37:37,080
Я не знаю, куди йти.

745
00:37:37,080 --> 00:37:38,410
Як вирішити цю проблему?

746
00:37:38,410 --> 00:37:41,150
>> І так ви, хлопці, буде свого роду
бачити, що ми робимо це складна річ

747
00:37:41,150 --> 00:37:44,810
де ми можемо насправді вид
створити зв'язаний список в наших масивів.

748
00:37:44,810 --> 00:37:46,840
І так найпростіший спосіб
думати про це,

749
00:37:46,840 --> 00:37:50,830
всі хеш-таблиці є
масив пов'язаних списків.

750
00:37:50,830 --> 00:37:55,670
І так, в цьому сенсі, у вас є
Цей красивий масив покажчиків,

751
00:37:55,670 --> 00:37:58,740
а потім кожен покажчик в
що значення, в цьому індексі,

752
00:37:58,740 --> 00:38:00,740
може насправді вказувати на інші речі.

753
00:38:00,740 --> 00:38:05,720
І так у вас є всі ці окремі
ланцюга сходить одному великому масиві.

754
00:38:05,720 --> 00:38:07,960
>> І ось, якщо я
хотів вставити ягоду,

755
00:38:07,960 --> 00:38:11,220
Я знаю, гаразд, я збираюся ввести
це через мій хеш-функції.

756
00:38:11,220 --> 00:38:15,070
Я збираюся закінчити з індексом
1, а потім я збираюся бути в змозі мати

757
00:38:15,070 --> 00:38:20,410
просто менше підмножина цього
гігант словник 140,000 слово.

758
00:38:20,410 --> 00:38:24,220
І тоді я можу просто подивитися
через 1/26, що.

759
00:38:24,220 --> 00:38:27,910
>> І так, то я можу просто вставити
ягоди або до, або після того, як банан

760
00:38:27,910 --> 00:38:28,820
в цьому випадку?

761
00:38:28,820 --> 00:38:29,700
Після, правда?

762
00:38:29,700 --> 00:38:33,920
І так ви будете хотіти, щоб
вставити цей вузол після банана,

763
00:38:33,920 --> 00:38:36,667
і таким чином Ви збираєтеся вставити
в хвості цієї пов'язаного списку.

764
00:38:36,667 --> 00:38:38,500
Я збираюся повернутися
в цьому попередньому слайді,

765
00:38:38,500 --> 00:38:40,680
так що ви, хлопці, можете побачити, як
Хеш функція працює.

766
00:38:40,680 --> 00:38:43,980
>> Так хеш функція це рівняння
що ви працюєте вигляд вашого входу

767
00:38:43,980 --> 00:38:46,940
через, щоб отримати всі індекс
Ви хочете, щоб призначити його к.

768
00:38:46,940 --> 00:38:51,130
І так, в цьому прикладі, всі ми хотіли
потрібно було взяти першу букву,

769
00:38:51,130 --> 00:38:55,890
свою чергу, що в індекс, то
може зберігати, що в нашій хеш-функції.

770
00:38:55,890 --> 00:39:00,160
Все, що ми робимо тут ми
перетворенні перший букву.

771
00:39:00,160 --> 00:39:04,770
Так KeyKey [0] тільки перша буква
все, що рядок ми с,

772
00:39:04,770 --> 00:39:05,720
ми передаємо в.

773
00:39:05,720 --> 00:39:09,740
Ми перетворення, що верхній і
ми віднімаючи великими А,

774
00:39:09,740 --> 00:39:11,740
тому все, що робить
дає нам ряд

775
00:39:11,740 --> 00:39:13,670
в яких ми можемо хеш наші цінності на.

776
00:39:13,670 --> 00:39:16,550
>> А потім ми збираємося
повернутися хеш модуль РОЗМІР.

777
00:39:16,550 --> 00:39:19,340
Будьте дуже, дуже обережні,
тому, теоретично, тут

778
00:39:19,340 --> 00:39:21,870
Ваш хеш-значення може бути нескінченним.

779
00:39:21,870 --> 00:39:23,660
Це може бути просто піти далі і далі і далі.

780
00:39:23,660 --> 00:39:26,080
Це може бути деякі дійсно,
дійсно велике значення,

781
00:39:26,080 --> 00:39:29,849
а тому, що ваш хеш-таблиці, що
Ви створили тільки має 26 індексів,

782
00:39:29,849 --> 00:39:31,890
Ви хочете, щоб переконатися, що ваш
modulusing, так що ви

783
00:39:31,890 --> 00:39:33,848
НЕ run-- це те ж саме
що в якості queue--

784
00:39:33,848 --> 00:39:36,320
так що ви не зійшли з
Дно Вашої хеш-функції.

785
00:39:36,320 --> 00:39:39,210
>> Ви хочете, щоб обернути його назад навколо
так само, як в [нерозбірливо], коли

786
00:39:39,210 --> 00:39:41,750
у вас, як дуже,
дуже велика буква, ви

787
00:39:41,750 --> 00:39:43,740
не хочу, щоб
просто бігти кінець.

788
00:39:43,740 --> 00:39:46,948
Те ж саме тут, ви хочете, щоб переконатися, що
він не працює з кінця, накладаючись

789
00:39:46,948 --> 00:39:48,330
навколо верхньої частини таблиці.

790
00:39:48,330 --> 00:39:50,530
Так що це просто дуже
просто хеш функція.

791
00:39:50,530 --> 00:39:56,570
Все, що зробив перший взяти
Лист який нашому вході був

792
00:39:56,570 --> 00:40:01,660
і перетворити це в індекс,
ми могли б поставити в нашу хеш-таблиці.

793
00:40:01,660 --> 00:40:05,450
>> Так, і так, як я сказав раніше,
так, що ми вирішення колізій

794
00:40:05,450 --> 00:40:09,330
в нашій хеш таблиці, що мають,
що ми називаємо, ланцюжки.

795
00:40:09,330 --> 00:40:13,860
Так що, якщо ви намагаєтеся вставити кілька
слова, які починаються з тієї ж речі,

796
00:40:13,860 --> 00:40:16,145
Ви будете мати один хеш-значення.

797
00:40:16,145 --> 00:40:18,770
Авокадо і яблуко, якщо у Вас є
запустити його через нашу хеш-функції,

798
00:40:18,770 --> 00:40:21,450
збираються, щоб дати вам
така ж кількість, кількість 0.

799
00:40:21,450 --> 00:40:24,550
І так як ми вирішити це
що ми можемо насправді вид зв'язати їх

800
00:40:24,550 --> 00:40:27,010
разом з допомогою пов'язаних списків.

801
00:40:27,010 --> 00:40:29,600
>> І тому в цьому сенсі,
ви, хлопці, можете побачити вид

802
00:40:29,600 --> 00:40:32,640
як структури даних,
ми були налаштування, раніше

803
00:40:32,640 --> 00:40:35,870
як родзинки пов'язані список роду
з можете прийти разом в один.

804
00:40:35,870 --> 00:40:38,860
І тоді ви можете створити ще
більш ефективні структури даних

805
00:40:38,860 --> 00:40:43,350
які можуть обробляти великі обсяги
Дані, які динамічно змінювати розмір в залежності

806
00:40:43,350 --> 00:40:44,870
від ваших потреб.

807
00:40:44,870 --> 00:40:45,620
Все ясно?

808
00:40:45,620 --> 00:40:47,580
Все ніби ясно,
на те, що відбувається тут?

809
00:40:47,580 --> 00:40:52,110
>> Якби я хотів, щоб insert--, що це
фрукти, який починається з, я не знаю

810
00:40:52,110 --> 00:40:54,726
B, крім ягід, банан.

811
00:40:54,726 --> 00:40:55,710
>> АУДИТОРІЯ: Ожина.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Пен: Blackberry, ожина.

813
00:40:57,910 --> 00:41:00,530
Де ожини йти сюди?

814
00:41:00,530 --> 00:41:04,251
Ну, ми насправді не сортуються
це ще, але теоретично

815
00:41:04,251 --> 00:41:06,250
якби ми хотіли, щоб це
в алфавітному порядку,

816
00:41:06,250 --> 00:41:07,944
де повинні BlackBerry йти?

817
00:41:07,944 --> 00:41:09,210
>> АУДИТОРІЯ: [нерозбірливо]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Пен: Рівне, після тут, вірно?

819
00:41:11,100 --> 00:41:14,950
Але так як це дуже складно
reorder-- Я думаю, це до вас, хлопці.

820
00:41:14,950 --> 00:41:17,920
Ви, хлопці, можете повністю
здійснити все, що ви хочете.

821
00:41:17,920 --> 00:41:20,730
Чим більше ефективний спосіб
робити це, можливо,

822
00:41:20,730 --> 00:41:24,570
буде сортувати ваш пов'язаний
список в алфавітному порядку,

823
00:41:24,570 --> 00:41:26,520
і тому, коли ви
вставки речі, ви хочете

824
00:41:26,520 --> 00:41:28,632
щоб переконатися, що вставити їх
в алфавітному порядку

825
00:41:28,632 --> 00:41:30,590
так що потім, коли ви
намагаються шукати їх,

826
00:41:30,590 --> 00:41:32,410
Ви не повинні пройти всі.

827
00:41:32,410 --> 00:41:35,290
Ви точно знаєте, де
вона є, і це простіше.

828
00:41:35,290 --> 00:41:39,100
>> Але якщо ви начебто є
речі перемежовуються випадково,

829
00:41:39,100 --> 00:41:41,420
Ви як і раніше будете мати
пройти його в жодному разі.

830
00:41:41,420 --> 00:41:44,990
І тому, якщо я хотів, щоб просто
вставте ожини тут

831
00:41:44,990 --> 00:41:47,470
і я хотів, щоб шукати
це, знаю, ох, ожина

832
00:41:47,470 --> 00:41:52,012
повинні почати з індексом 1, так що я
знаю, миттєво просто шукати на 1.

833
00:41:52,012 --> 00:41:53,970
І тоді я можу роду
пройти зв'язаний список

834
00:41:53,970 --> 00:41:56,120
поки я не отримати до BlackBerry,
і then-- да?

835
00:41:56,120 --> 00:41:59,550
>> АУДИТОРІЯ: Якщо ви намагаєтеся create--
Я думаю, як це дуже простий хеш

836
00:41:59,550 --> 00:42:00,050
функція.

837
00:42:00,050 --> 00:42:02,835
І якщо ми хочемо, щоб зробити
декілька шарів, що, як,

838
00:42:02,835 --> 00:42:05,870
ОК, ми хочемо, щоб відокремити в
як і всі алфавітно

839
00:42:05,870 --> 00:42:09,040
а потім знову хотів інший набір
з букв алфавіту протягом, що,

840
00:42:09,040 --> 00:42:11,715
ми покласти як хеш
таблиця в хеш-таблиці,

841
00:42:11,715 --> 00:42:13,256
або як функції всередині функції?

842
00:42:13,256 --> 00:42:14,880
Або that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Пен: Так ваш хеш
function-- свій хеш-таблицю

844
00:42:17,510 --> 00:42:19,360
може бути як великою, як ви хочете.

845
00:42:19,360 --> 00:42:21,930
Таким чином, в цьому сенсі, я думав,
це було дуже легко, дуже

846
00:42:21,930 --> 00:42:25,320
просто для мене, щоб просто зразок основі
на літери першого слова.

847
00:42:25,320 --> 00:42:28,690
І так є тільки 26 варіантів.

848
00:42:28,690 --> 00:42:32,650
Я можу отримати тільки 26 варіантів з
0 до 25, тому що вони можуть тільки

849
00:42:32,650 --> 00:42:36,510
почати від А до Z. Але якщо ви хочете
додати, мабуть, більше складності

850
00:42:36,510 --> 00:42:39,260
або швидше бігти до вашого часу
хеш-таблиця, ви абсолютно

851
00:42:39,260 --> 00:42:40,760
може зробити всі види речей.

852
00:42:40,760 --> 00:42:43,330
Ви можете зробити свій власний
Рівняння, яке дає вам

853
00:42:43,330 --> 00:42:48,000
більш розсилки в
слів, то при пошуку,

854
00:42:48,000 --> 00:42:49,300
це буде швидше.

855
00:42:49,300 --> 00:42:52,100
>> Це повністю залежить від вас, хлопці
як ви хочете, щоб здійснити це.

856
00:42:52,100 --> 00:42:55,140
Думайте про це як тільки відрами.

857
00:42:55,140 --> 00:42:57,376
Якби я хотів, щоб мати
26 відра, я збираюся

858
00:42:57,376 --> 00:42:59,420
сортувати речі в цих відрах.

859
00:42:59,420 --> 00:43:02,980
Але я збираюся мати купу
речі в кожному відрі,

860
00:43:02,980 --> 00:43:05,890
так що якщо ви хочете, щоб зробити його
швидше і ефективніше,

861
00:43:05,890 --> 00:43:07,190
дайте мені сто відер.

862
00:43:07,190 --> 00:43:09,290
>> Але тоді ви повинні з'ясувати
спосіб сортування речі так, щоб вони

863
00:43:09,290 --> 00:43:11,040
в належному відро вони повинні бути в.

864
00:43:11,040 --> 00:43:13,331
Але потім, коли ви насправді
хочу подивитися на цього відра,

865
00:43:13,331 --> 00:43:16,410
це набагато швидше, тому що є
менше речі в кожному відрі.

866
00:43:16,410 --> 00:43:20,250
І так, так, це насправді
трюк для вас, хлопці в pset5

867
00:43:20,250 --> 00:43:22,360
є те, що ви будете
виклик просто створити

868
00:43:22,360 --> 00:43:26,170
все, що є найбільш ефективним
Функція Ви можете думати, щоб бути

869
00:43:26,170 --> 00:43:28,520
можливість зберігання та перевірки цих значень.

870
00:43:28,520 --> 00:43:30,840
>> Всього до вас, хлопці
Однак ви хочете, щоб це зробити,

871
00:43:30,840 --> 00:43:32,229
але це дійсно хороша точка.

872
00:43:32,229 --> 00:43:34,520
Те, що така логіка ви
хочу, щоб почати думати про

873
00:43:34,520 --> 00:43:37,236
, Ну, чому я не зробити більше відра.

874
00:43:37,236 --> 00:43:39,527
І тоді я повинен шукати
менше речей, і тоді, можливо, я

875
00:43:39,527 --> 00:43:41,640
мають різну хеш-функцію.

876
00:43:41,640 --> 00:43:45,500
>> Так, є багато способів зробити це
PSET, деякі швидше, ніж інші.

877
00:43:45,500 --> 00:43:50,630
Я повністю збираюся просто подивитися, як
швидко став найшвидшим ви, хлопці,

878
00:43:50,630 --> 00:43:55,170
бути в змозі отримати ваші функції на роботу.

879
00:43:55,170 --> 00:43:58,176
ОК, все добре на
Ієрархії серверів і хеш-таблиці?

880
00:43:58,176 --> 00:44:00,800
Це насправді, як дуже простий
поняття, якщо ви думаєте про це.

881
00:44:00,800 --> 00:44:05,160
Все це є поділ все
Ваші входи в відра,

882
00:44:05,160 --> 00:44:10,670
сортуючи їх, а потім шукають в
список, що там пов'язано з.

883
00:44:10,670 --> 00:44:11,852
>> Прохолодний.

884
00:44:11,852 --> 00:44:18,160
Гаразд, тепер у нас є різного роду
структури даних, яка називається деревом.

885
00:44:18,160 --> 00:44:20,850
Давайте йти далі і говорити про спроби
які суттєво відрізняються,

886
00:44:20,850 --> 00:44:22,330
але в тій же категорії.

887
00:44:22,330 --> 00:44:29,010
По суті, все дерево замість цього
організації даних в лінійному чином

888
00:44:29,010 --> 00:44:32,560
що хеш-таблиця does-- вас
Знаєте, він отримав верх і низ

889
00:44:32,560 --> 00:44:37,900
а потім ви начебто посилаються геть it-- в
Дерево має верхній, що ви називаєте корінь,

890
00:44:37,900 --> 00:44:40,220
і то він має листя все навколо нього.

891
00:44:40,220 --> 00:44:42,390
>> А так все у вас тут
це тільки верхній вузол

892
00:44:42,390 --> 00:44:45,980
який вказує на інші вузли, що точки
щоб більше вузлів, і так далі і тому подібне.

893
00:44:45,980 --> 00:44:48,130
І так ви просто розщеплення гілок.

894
00:44:48,130 --> 00:44:53,255
Це просто інший спосіб організації
Дані, і тому що ми називаємо це дерево,

895
00:44:53,255 --> 00:44:56,270
ви, хлопці, просто-- це просто
моделюється, щоб дивитися, як дерево.

896
00:44:56,270 --> 00:44:57,670
Ось чому ми називаємо його дерева.

897
00:44:57,670 --> 00:44:59,370
>> Хеш таблиця виглядає як таблиця.

898
00:44:59,370 --> 00:45:01,310
Дерево виглядає як дерево.

899
00:45:01,310 --> 00:45:03,300
Все це є окремим
спосіб організації вузлів

900
00:45:03,300 --> 00:45:06,020
залежно від того, що ваші потреби.

901
00:45:06,020 --> 00:45:11,810
>> Так у вас є коріння і
то у вас є листя.

902
00:45:11,810 --> 00:45:15,380
Таким чином, що ми можемо особливо
думаю про нього бінарне дерево,

903
00:45:15,380 --> 00:45:18,150
бінарне дерево просто
Конкретний тип дерева

904
00:45:18,150 --> 00:45:22,450
де кожен вузол тільки точки
щоб, при макс, два інших вузлів.

905
00:45:22,450 --> 00:45:25,434
І ось у вас є відмінний
Симетрія в дереві

906
00:45:25,434 --> 00:45:28,600
що робить його легше свого роду виглядати
на які цінності ви, тому що тоді ви

907
00:45:28,600 --> 00:45:30,150
завжди зліва чи право.

908
00:45:30,150 --> 00:45:33,150
Там ніколи не як лівої третини від
ліва або четвертий зліва.

909
00:45:33,150 --> 00:45:36,358
Це просто у вас є лівий і правий
і ви можете шукати небудь з цих двох.

910
00:45:36,358 --> 00:45:38,980
І так, чому це корисно?

911
00:45:38,980 --> 00:45:40,980
Таким чином, що це
корисна, якщо ви шукаєте

912
00:45:40,980 --> 00:45:42,890
шукати через значення, вірно?

913
00:45:42,890 --> 00:45:45,640
Замість реалізації двійковий
пошук в масиві помилок,

914
00:45:45,640 --> 00:45:49,260
якщо ви хочете, щоб мати можливість вставити вузли
і забрати вузли за бажанням, а також

915
00:45:49,260 --> 00:45:52,185
зберегти пошук
потужності довічного пошуку.

916
00:45:52,185 --> 00:45:54,560
Таким чином, в цьому випадку, ми начебто
tricking-- пам'ятаю, коли ми

917
00:45:54,560 --> 00:45:56,530
сказав зв'язані списки не можуть бінарний пошук?

918
00:45:56,530 --> 00:46:01,700
Ми кшталт створення структури даних
що прийоми, які в робочий.

919
00:46:01,700 --> 00:46:05,034
>> І це тому, що зв'язані списки є лінійними,
вони тільки посилаються один за іншим.

920
00:46:05,034 --> 00:46:06,950
Ми можемо мати вигляд
різного роду покажчиків

921
00:46:06,950 --> 00:46:09,408
які вказують на різних вузлах
що може допомогти нам у пошуку.

922
00:46:09,408 --> 00:46:12,590
І ось, якби я хотів, щоб
є дерево двійкового пошуку,

923
00:46:12,590 --> 00:46:14,090
Я знаю, що мого середині, якщо 55 років.

924
00:46:14,090 --> 00:46:18,280
Я просто хочу, щоб створити що
як мій середині, як мій корінь,

925
00:46:18,280 --> 00:46:20,770
і тоді я буду мати
Значення виділення з нього.

926
00:46:20,770 --> 00:46:25,610
>> Так от, якщо я збираюся шукати
значення 66, я можу почати в 55 років.

927
00:46:25,610 --> 00:46:27,310
Це більше, ніж 66 55?

928
00:46:27,310 --> 00:46:30,970
Так, це, так що я знаю, що я муз пошук
я н право покажчик цього дерева.

929
00:46:30,970 --> 00:46:32,440
Я йду до 77.

930
00:46:32,440 --> 00:46:35,367
ОК, це менше, ніж 66 або більше, ніж 77?

931
00:46:35,367 --> 00:46:37,950
Це менше, ніж, так що ви знаєте, про,
який повинен бути зліва вузол.

932
00:46:37,950 --> 00:46:41,410
>> І ось ми начебто збереження
всі великі речі про масивах,

933
00:46:41,410 --> 00:46:44,420
оскільки динамічне зміна розміру
об'єктів, будучи

934
00:46:44,420 --> 00:46:49,530
можливість вставляти і видаляти за бажанням,
без того, щоб турбуватися про фіксовану

935
00:46:49,530 --> 00:46:50,370
обсяг простору.

936
00:46:50,370 --> 00:46:52,820
Ми як і раніше зберігають всі
ці чудові речі

937
00:46:52,820 --> 00:46:57,140
в той же час бути в змозі зберегти
увійти і пошук час бінарного пошуку

938
00:46:57,140 --> 00:47:00,450
що ми були тільки раніше
можливість отримати фразу.

939
00:47:00,450 --> 00:47:06,310
>> Прохолодний структура даних, начебто
Комплекс для реалізації, вузол.

940
00:47:06,310 --> 00:47:08,311
Як ви можете бачити, все це
це структура вузла

941
00:47:08,311 --> 00:47:10,143
є те, що у вас є лівий
і право покажчиком.

942
00:47:10,143 --> 00:47:11,044
Це все, що є.

943
00:47:11,044 --> 00:47:12,960
Таким чином, замість просто
має х або попередній.

944
00:47:12,960 --> 00:47:15,920
Ви повинні наліво або направо, а потім
Ви можете вид зв'язати їх разом

945
00:47:15,920 --> 00:47:16,836
Однак ви того побажаєте.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> Добре, ми насправді відбувається
просто взяти кілька хвилин.

948
00:47:24,270 --> 00:47:25,790
Отже, ми збираємося, щоб повернутися сюди.

949
00:47:25,790 --> 00:47:28,270
Як я вже говорив,
Я начебто пояснив

950
00:47:28,270 --> 00:47:31,520
логіка, як ми
буде шукати через це.

951
00:47:31,520 --> 00:47:33,860
Ми збираємося, щоб спробувати
pseudocoding цей, щоб побачити

952
00:47:33,860 --> 00:47:38,000
якщо ми можемо роду застосувати
Та ж логіка бінарного пошуку

953
00:47:38,000 --> 00:47:40,055
на інший тип структури даних.

954
00:47:40,055 --> 00:47:45,049
Якщо ви, хлопці, хочете, щоб прийняти як пара
хвилин, щоб просто думати про це.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ДОБРЕ.

957
00:48:46,925 --> 00:48:51,407
Гаразд, я збираюся
насправді просто не дасть вам the-- немає,

958
00:48:51,407 --> 00:48:52,990
ми будемо говорити про псевдокоді перший.

959
00:48:52,990 --> 00:48:56,580
Так хто-небудь хоче
дати удар на те, що

960
00:48:56,580 --> 00:49:02,100
перше, що ви хочете робити, коли
Ви починаєте пошук по?

961
00:49:02,100 --> 00:49:04,460
Якщо ми шукаємо
значення 66, що

962
00:49:04,460 --> 00:49:07,940
Перше, що ми хочемо робити, якщо
ми хочемо, щоб цей бінарний пошук дерево?

963
00:49:07,940 --> 00:49:10,760
>> АУДИТОРІЯ: Ви хочете, щоб дивитися прямо
і подивіться наліво і побачите [нерозбірливо]

964
00:49:10,760 --> 00:49:11,230
більше число.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Пен: Так, саме так.

966
00:49:12,271 --> 00:49:15,350
Таким чином, ви будете дивитися на корені.

967
00:49:15,350 --> 00:49:18,180
Там багато способів ви можете зателефонувати
це, ваші батько вузла люди говорять.

968
00:49:18,180 --> 00:49:21,317
Я хотів би сказати, тому що корінь
це як корінь дерева.

969
00:49:21,317 --> 00:49:23,400
Ви збираєтеся дивитися на
Ваш кореневий вузол, і ви

970
00:49:23,400 --> 00:49:26,940
побачите 66 більше
або менше, ніж 55.

971
00:49:26,940 --> 00:49:30,360
І якщо це більше, ніж, ну, це
більше, ніж, де ми хочемо, щоб подивитися?

972
00:49:30,360 --> 00:49:32,000
Куди ми хочемо шукати зараз, правда?

973
00:49:32,000 --> 00:49:34,340
Ми хочемо, щоб пошук в
Права половина цього дерева.

974
00:49:34,340 --> 00:49:38,390
>> Отже, ми маємо, зручно, А
покажчик, який вказує на право.

975
00:49:38,390 --> 00:49:44,325
І так, то ми можемо встановити
наш новий корінь, щоб бути 77.

976
00:49:44,325 --> 00:49:46,450
Ми можемо просто піти туди, де
покажчик вказує.

977
00:49:46,450 --> 00:49:49,100
Ну, ну, тут ми починаємо
на 77, і ми можемо тільки

978
00:49:49,100 --> 00:49:51,172
зробити це рекурсивно знову і знову.

979
00:49:51,172 --> 00:49:52,880
Таким чином, ви начебто
від того, мають функцію.

980
00:49:52,880 --> 00:49:57,430
У вас є спосіб пошуку, що ви
можна просто повторювати знову і знову і знову,

981
00:49:57,430 --> 00:50:02,720
в залежності від того, де ви хочете, щоб подивитися
поки ви в кінцевому результаті не отримати до значення

982
00:50:02,720 --> 00:50:04,730
що ви шукаєте.

983
00:50:04,730 --> 00:50:05,230
Мати сенс?

984
00:50:05,230 --> 00:50:07,800
>> Я збираюся показати Вам фактичний
Код, і це багато коду.

985
00:50:07,800 --> 00:50:08,674
Немає необхідності хвилюватися.

986
00:50:08,674 --> 00:50:09,910
Ми будемо говорити через нього.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Насправді, немає.

989
00:50:14,020 --> 00:50:15,061
Це було просто псевдокод.

990
00:50:15,061 --> 00:50:17,860
ОК, це було просто псевдокод,
який є трохи складним,

991
00:50:17,860 --> 00:50:19,751
але це абсолютно нормально.

992
00:50:19,751 --> 00:50:21,000
Кожен наступний по тут?

993
00:50:21,000 --> 00:50:24,260
Якщо корінь нуль, повернення
брехня, тому що це означає, що

994
00:50:24,260 --> 00:50:26,850
Ви навіть не мають нічого там.

995
00:50:26,850 --> 00:50:31,376
>> Якщо корінь п значення, тому, якщо він
трапляється, той, який ви дивитеся,

996
00:50:31,376 --> 00:50:34,000
то ви будете повертатися правда
тому що ви знаєте ви його знайшли.

997
00:50:34,000 --> 00:50:36,250
Але якщо значення менше
чому корінь п, ви

998
00:50:36,250 --> 00:50:38,332
буде шукати лівого
дитина чи ліва лист,

999
00:50:38,332 --> 00:50:39,540
все, що ви хочете назвати це.

1000
00:50:39,540 --> 00:50:41,750
І якщо значення більше, ніж корінь,
Ви збираєтеся шукати потрібне дерево,

1001
00:50:41,750 --> 00:50:44,610
Потім просто запустіть функцію
через пошук знову.

1002
00:50:44,610 --> 00:50:48,037
>> А якщо корінь порожній, що це
означає, що ви дійшли до кінця?

1003
00:50:48,037 --> 00:50:50,120
Це означає, що у вас їсти не
більш більше листя для пошуку,

1004
00:50:50,120 --> 00:50:52,230
то ви знаєте, о, я
думаю, це не тут

1005
00:50:52,230 --> 00:50:55,063
тому що після того як я подивився через
все це, і це не тут,

1006
00:50:55,063 --> 00:50:56,930
він просто не може бути тут.

1007
00:50:56,930 --> 00:50:58,350
>> Чи має це сенс для всіх?

1008
00:50:58,350 --> 00:51:03,230
Так як бінарний пошук, що зберігають
Можливості пов'язаних списків.

1009
00:51:03,230 --> 00:51:09,200
Холодний, і так другий тип
структури даних ви, хлопці

1010
00:51:09,200 --> 00:51:13,180
може спробувати реалізувати на PSET,
у вас є тільки один спосіб вибрати.

1011
00:51:13,180 --> 00:51:19,430
Але, можливо, альтернативний метод
хеш-таблиця є те, що ми називаємо синтаксичного дерева.

1012
00:51:19,430 --> 00:51:24,080
>> Все, Trie це є
Конкретний тип дерева,

1013
00:51:24,080 --> 00:51:28,600
має значення, які виходять на інші значення.

1014
00:51:28,600 --> 00:51:31,450
Таким чином, замість того, двійковий
дерево в тому сенсі, що тільки один

1015
00:51:31,450 --> 00:51:35,940
що може вказувати на двох, ви можете мати
Одна справа точка багатьох, багатьох речей.

1016
00:51:35,940 --> 00:51:39,450
Ви по суті є масиви
усередині якого ви зберігаєте

1017
00:51:39,450 --> 00:51:41,790
покажчики, які вказують на інші масиви.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Таким чином, вузол, як ми
визначатиме синтаксичного дерева

1020
00:51:49,460 --> 00:51:52,590
що ми хочемо, щоб мати
Логічне, з слово, вірно?

1021
00:51:52,590 --> 00:51:54,920
Таким чином, вузол Логічний
як істинне або помилкове,

1022
00:51:54,920 --> 00:51:58,490
в першу чергу в голову
що масив, це слово?

1023
00:51:58,490 --> 00:52:03,620
По-друге, ви хочете, щоб покажчики
до того, що решта з них.

1024
00:52:03,620 --> 00:52:07,470
Трохи складний, трохи абстрактно, але
Я поясню, що це всі засоби.

1025
00:52:07,470 --> 00:52:13,800
>> Так от, у верхній, якщо ви
є масив, оголошений вже

1026
00:52:13,800 --> 00:52:17,040
вузол, де у вас є логічне
Значення, збережене в передній

1027
00:52:17,040 --> 00:52:19,490
що говорить вам це слово?

1028
00:52:19,490 --> 00:52:20,520
Хіба це не слово?

1029
00:52:20,520 --> 00:52:23,240
І тоді у вас є
Решта масиві, що

1030
00:52:23,240 --> 00:52:26,040
насправді зберігає всі
Можливості, що це може бути.

1031
00:52:26,040 --> 00:52:28,660
Так, наприклад, як
у верхній вас є

1032
00:52:28,660 --> 00:52:32,140
Перше, що говорить правда чи
брехня, так чи ні, це слово.

1033
00:52:32,140 --> 00:52:38,130
>> І тоді у вас є від 0 до 26
листи, які ви можете зберігати.

1034
00:52:38,130 --> 00:52:42,790
Якби я хотів, щоб пошук
для кажана, я йду до вершини

1035
00:52:42,790 --> 00:52:49,200
і я дивлюся на В. Я знаходжу в моєму B
масив, так що я знаю, добре, це B слово?

1036
00:52:49,200 --> 00:52:53,010
У це не те слово, так, таким чином,
Я повинен продовжувати пошуки.

1037
00:52:53,010 --> 00:52:56,410
Я йду від B, і я з нетерпінням до
покажчик, який вказує на B

1038
00:52:56,410 --> 00:53:00,900
і я бачу ще один масив інформації,
та ж структура, що у нас було раніше.

1039
00:53:00,900 --> 00:53:05,240
>> І here-- ой, наступний
Лист в [нерозбірливо] це А.

1040
00:53:05,240 --> 00:53:07,210
Таким чином, ми з нетерпінням в цьому масиві.

1041
00:53:07,210 --> 00:53:10,860
Ми знаходимо восьмий значення,
і тоді ми подивіться, ох,

1042
00:53:10,860 --> 00:53:12,840
агов, це те, що словом, це В-А слово?

1043
00:53:12,840 --> 00:53:13,807
Це не слова.

1044
00:53:13,807 --> 00:53:14,890
Ми повинні продовжувати пошуки.

1045
00:53:14,890 --> 00:53:17,850
>> І так, то ми дивимося, де
покажчик А точок,

1046
00:53:17,850 --> 00:53:21,130
і це вказує на один спосіб,
які у нас є більше значення зберігаються.

1047
00:53:21,130 --> 00:53:24,150
І врешті-решт, ми отримуємо
В-А-Т, яка є слово.

1048
00:53:24,150 --> 00:53:25,970
І тому наступного разу
Ви подивіться, що ви збираєтеся

1049
00:53:25,970 --> 00:53:30,850
мати, що перевірку, так,
це булева функція є правдою.

1050
00:53:30,850 --> 00:53:35,450
І так в тому сенсі, ми начебто
наявності дерево з масивами.

1051
00:53:35,450 --> 00:53:39,890
>> Так, то ви можете роду пошук вниз.

1052
00:53:39,890 --> 00:53:43,650
Замість того, щоб хешування функцію і
привласнення значення, пов'язаного списку,

1053
00:53:43,650 --> 00:53:49,190
ви можете просто реалізувати
Trie, що пошук downwords.

1054
00:53:49,190 --> 00:53:50,850
Дійсно, дійсно складній речі.

1055
00:53:50,850 --> 00:53:54,060
Нелегко думати про, тому що я, як
плювки так багато структур даних з

1056
00:53:54,060 --> 00:53:58,710
у вас, але робить все роду
зрозуміти, як логіка це працює?

1057
00:53:58,710 --> 00:54:01,920
>> ОК здорово.

1058
00:54:01,920 --> 00:54:05,600
Так B-A-T, а потім
Ви збираєтеся шукати.

1059
00:54:05,600 --> 00:54:07,940
Наступного разу ви збираєтеся
щоб бачити, о, агов, це правда,

1060
00:54:07,940 --> 00:54:09,273
Таким чином, я знаю, що це має бути слово.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Те ж саме для зоопарку.

1063
00:54:13,770 --> 00:54:17,960
Так ось у чому справа прямо зараз, якщо ми
хотів шукати зоопарку, прямо зараз,

1064
00:54:17,960 --> 00:54:20,780
В даний час зоопарк не
слово в нашому словнику

1065
00:54:20,780 --> 00:54:25,300
тому що, як ви, хлопці, можете бачити,
Перше місце, що ми маємо логічне

1066
00:54:25,300 --> 00:54:28,590
повертає істину в кінці масштабування.

1067
00:54:28,590 --> 00:54:30,430
У нас є Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> І ось, ми насправді не мають
слово, зоопарк, в нашому словнику

1069
00:54:33,900 --> 00:54:36,070
тому що цей прапорець не встановлений.

1070
00:54:36,070 --> 00:54:39,540
Таким чином, комп'ютер не
знаю, що зоопарк це слово

1071
00:54:39,540 --> 00:54:42,430
бо шлях, який ми
зберігати його, тільки зум тут

1072
00:54:42,430 --> 00:54:44,920
насправді має логічне значення
який був перетворений правда.

1073
00:54:44,920 --> 00:54:49,380
Так що, якщо ми хочемо, щоб вставити
Слово, зоопарк, в нашому словнику,

1074
00:54:49,380 --> 00:54:51,770
як би ми йти про те, що робити?

1075
00:54:51,770 --> 00:54:55,960
Що ми повинні зробити, щоб переконатися, що наші
комп'ютер знає, що Z-О-О слово

1076
00:54:55,960 --> 00:54:58,130
а не перше слово Z-О-О-М?

1077
00:54:58,130 --> 00:54:59,360
>> АУДИТОРІЯ: [нерозбірливо]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Пен: Рівне, ми
хочете, щоб переконатися, що це

1079
00:55:01,450 --> 00:55:07,890
ось, що Логічне значення
галочка, що це правда.

1080
00:55:07,890 --> 00:55:13,297
Z-О-О, то ми збираємося перевірити, що
так ми точно знаємо, гей, зоопарк є слово.

1081
00:55:13,297 --> 00:55:15,380
Я збираюся розповісти
комп'ютер, що це слово так

1082
00:55:15,380 --> 00:55:18,000
що, коли комп'ютер перевіряє,
він знає, що зоопарк це слово.

1083
00:55:18,000 --> 00:55:21,269
>> Тому що пам'ятаю всі ці дані
структури, це дуже легко для нас

1084
00:55:21,269 --> 00:55:22,310
сказати, ой, кажан це слово.

1085
00:55:22,310 --> 00:55:22,851
Зоопарк це слово.

1086
00:55:22,851 --> 00:55:23,611
Збільшити це слово.

1087
00:55:23,611 --> 00:55:25,860
Але коли ви будуєте його,
комп'ютер не має поняття.

1088
00:55:25,860 --> 00:55:28,619
>> Таким чином, ви повинні сказати це точно
в який момент це слово?

1089
00:55:28,619 --> 00:55:29,910
У який момент це не слово?

1090
00:55:29,910 --> 00:55:31,784
І в якийсь момент я
потрібно шукати речі,

1091
00:55:31,784 --> 00:55:34,000
і в який момент мені потрібно йти далі?

1092
00:55:34,000 --> 00:55:37,010
Все ясно, з цього?

1093
00:55:37,010 --> 00:55:39,540
Прохолодний.

1094
00:55:39,540 --> 00:55:42,530
>> І так потім приходить
Проблема як би ми

1095
00:55:42,530 --> 00:55:45,560
йти про вставці то
що насправді немає?

1096
00:55:45,560 --> 00:55:49,090
Так що давайте просто сказати, що ми хочемо, щоб вставити
слово, ванна, в нашій синтаксичного дерева.

1097
00:55:49,090 --> 00:55:53,589
Як ви, хлопці, можете побачити, як в даний час
все, що ми маємо зараз, це В-А-Т,

1098
00:55:53,589 --> 00:55:55,630
і ця нова структура даних
Тобто мав пінту, що

1099
00:55:55,630 --> 00:55:59,740
вказав на нуль, тому що ми вважаємо,
що, ох, немає ніяких слів, після B-A-T,

1100
00:55:59,740 --> 00:56:02,530
чому ми повинні тримати
маючи речі після цього Т.

1101
00:56:02,530 --> 00:56:06,581
>> Але проблема виникає, якщо ми робимо вам
хочете мати слово, яке приходить після

1102
00:56:06,581 --> 00:56:07,080
Т-х.

1103
00:56:07,080 --> 00:56:09,500
Якщо у вас є ванна, ви
збирається хочете H права.

1104
00:56:09,500 --> 00:56:13,290
І так як ми збираємося зробити це
ми збираємося створити окремий вузол.

1105
00:56:13,290 --> 00:56:16,840
Ми не виділити будь-яку суму
пам'яті для цієї нової масиву,

1106
00:56:16,840 --> 00:56:20,720
і ми збираємося перепризначити покажчики.

1107
00:56:20,720 --> 00:56:22,947
>> Ми збираємося призначити
Н, В першу чергу, це нульовий,

1108
00:56:22,947 --> 00:56:24,030
ми збираємося позбутися.

1109
00:56:24,030 --> 00:56:26,590
Ми збираємося, щоб мати
Н точка вниз.

1110
00:56:26,590 --> 00:56:30,600
Якщо ми бачимо H, ми хочемо його
йти кудись ще.

1111
00:56:30,600 --> 00:56:33,910
>> Тут, ми можемо перевірити з да.

1112
00:56:33,910 --> 00:56:38,170
Якщо ми потрапили в H після Т, о,
то ми знаємо, що це слово.

1113
00:56:38,170 --> 00:56:41,110
Логічне збирається повернутися правда.

1114
00:56:41,110 --> 00:56:42,950
Все ясно, як це сталося?

1115
00:56:42,950 --> 00:56:45,110
ДОБРЕ.

1116
00:56:45,110 --> 00:56:47,214
>> Так, по суті, все
ці структури даних

1117
00:56:47,214 --> 00:56:50,130
що ми перейшли сьогодні, у мене
пішов на них дуже, дуже швидко

1118
00:56:50,130 --> 00:56:52,192
а не в набагато
докладно, і це нормально.

1119
00:56:52,192 --> 00:56:53,900
Як тільки ви починаєте возитися
з ним, ви будете

1120
00:56:53,900 --> 00:56:55,733
відстежувати, де
всі покажчики,

1121
00:56:55,733 --> 00:56:58,060
що відбувається у вашій
структури даних, і так далі.

1122
00:56:58,060 --> 00:56:59,810
Вони будуть дуже корисні,
і це до вас,

1123
00:56:59,810 --> 00:57:03,890
хлопці, щоб повністю зрозуміти, як
ви хочете реалізувати речі.

1124
00:57:03,890 --> 00:57:07,650
>> І так pset4, з 5-- ой, що це неправильно.

1125
00:57:07,650 --> 00:57:10,140
Pset5 є друкарськими помилками.

1126
00:57:10,140 --> 00:57:13,710
Як я вже говорив раніше, ви будете, колись
знову, скачати вихідний код з нас.

1127
00:57:13,710 --> 00:57:16,210
Там буде три основних
речі, які ви будете завантажувати.

1128
00:57:16,210 --> 00:57:18,470
Ви скачати словники,
KERS, і тексти.

1129
00:57:18,470 --> 00:57:21,660
>> Всі ці речі є
або словники слів

1130
00:57:21,660 --> 00:57:25,190
що ми хочемо, щоб ви перевірити
або випробування інформації

1131
00:57:25,190 --> 00:57:26,930
що ми хочемо, щоб ви перевірка орфографії.

1132
00:57:26,930 --> 00:57:29,670
І так словники
ми даємо вам збираємося

1133
00:57:29,670 --> 00:57:34,870
щоб дати вам конкретні слова, які ми хочемо
зберігати якось в способі, яким це

1134
00:57:34,870 --> 00:57:36,530
більш ефективним, ніж масив.

1135
00:57:36,530 --> 00:57:38,470
І тоді тексти
буде те, що ми

1136
00:57:38,470 --> 00:57:43,900
прошу вас перевірити правопис, щоб переконатися,
всі слова є реальні слова.

1137
00:57:43,900 --> 00:57:47,970
>> І так три блоки
програми, які ми дамо вам

1138
00:57:47,970 --> 00:57:51,130
називаються dictionary.c,
dictionary.h і speller.c.

1139
00:57:51,130 --> 00:57:56,500
А так все робить, dictionary.c
те, що ви просили реалізувати.

1140
00:57:56,500 --> 00:57:57,880
Він завантажує слова.

1141
00:57:57,880 --> 00:58:02,000
Це заклинання перевіряє їх, і це гарантує,
що все правильно вставлений.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h це просто файл бібліотеки
який оголошує всі ці функції.

1143
00:58:05,180 --> 00:58:07,650
І speller.c, ми збираємося дати вам.

1144
00:58:07,650 --> 00:58:09,290
Вам не потрібно змінювати кожній із нього.

1145
00:58:09,290 --> 00:58:14,290
Всі speller.c робить це прийняти, що
завантажує його, перевіряє швидкість його,

1146
00:58:14,290 --> 00:58:19,190
тестує позначку в ніби як
швидко ви зможете зробити речі.

1147
00:58:19,190 --> 00:58:20,410
>> Це що пише.

1148
00:58:20,410 --> 00:58:23,920
Тільки не зв'язуйтеся з ним, але зробити
що ви розумієте, що він робить.

1149
00:58:23,920 --> 00:58:28,090
Ми використовуємо функцію під назвою getrusage, що
тестує продуктивність вашого заклинання

1150
00:58:28,090 --> 00:58:28,590
перевірки.

1151
00:58:28,590 --> 00:58:32,200
Все це робить в основному протестувати
Час все в словнику,

1152
00:58:32,200 --> 00:58:33,680
тому переконайтеся, що ви розумієте, що.

1153
00:58:33,680 --> 00:58:36,660
Будьте обережні, щоб не зв'язуватися з ним або
решта все не буде працювати належним чином.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> І велика частина цієї проблеми є для
ви, хлопці, дійсно змінити dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Ми збираємося дати вам
140000 слів у словнику.

1157
00:58:48,526 --> 00:58:50,900
Ми збираємося дати вам текст
файл, який має ті слова,

1158
00:58:50,900 --> 00:58:54,840
і ми хочемо, щоб ви могли організувати
їх у хеш-таблиці або синтаксичного дерева

1159
00:58:54,840 --> 00:58:58,140
тому що, коли ми просимо вас заклинання
check-- уявіть собі, якщо ви заклинання

1160
00:58:58,140 --> 00:59:00,690
перевірки, як Одіссея Гомера.

1161
00:59:00,690 --> 00:59:03,010
Це як цього величезною, величезною тесту.

1162
00:59:03,010 --> 00:59:05,190
>> Уявіть собі, якщо кожен
Слово, яке ви повинні були шукати

1163
00:59:05,190 --> 00:59:08,100
через масив 140000 значень.

1164
00:59:08,100 --> 00:59:10,350
Це буде тривати вічно
для вашої машини, щоб бігти.

1165
00:59:10,350 --> 00:59:14,490
Саме тому ми хочемо, щоб організувати наші
дані в більш ефективних структур даних

1166
00:59:14,490 --> 00:59:17,270
таких як хеш-таблиці або синтаксичного дерева.

1167
00:59:17,270 --> 00:59:20,700
І тоді ви, хлопці, можете вид
коли ви шукати доступ

1168
00:59:20,700 --> 00:59:22,570
речі більш легко і більш швидко.

1169
00:59:22,570 --> 00:59:24,934
>> І тому будьте обережні, щоб вирішити зіткнень.

1170
00:59:24,934 --> 00:59:27,350
Ви збираєтеся отримати купу
слів, які починаються з А.

1171
00:59:27,350 --> 00:59:29,957
Ви збираєтеся отримати купу слів
які починаються з В. до вас

1172
00:59:29,957 --> 00:59:31,290
хлопці, як ви хочете, щоб вирішити її.

1173
00:59:31,290 --> 00:59:34,144
Може бути, є більш
ефективність хеш-функція

1174
00:59:34,144 --> 00:59:36,810
ніж просто першій букві
і те, і так, що до вас

1175
00:59:36,810 --> 00:59:38,190
хлопці на зразок робити все, що ви хочете.

1176
00:59:38,190 --> 00:59:40,148
>> Може бути, ви хочете, щоб додати
всі букви разом.

1177
00:59:40,148 --> 00:59:43,410
Може бути, ви хочете, щоб зробити подобається дивні речі
до відповідальності ряд листів,

1178
00:59:43,410 --> 00:59:43,970
все.

1179
00:59:43,970 --> 00:59:45,386
До вас, хлопці, як ви хочете зробити.

1180
00:59:45,386 --> 00:59:49,262
Якщо ви хочете зробити хеш-таблицю, якщо ви
хочу спробувати синтаксичного дерева, повністю залежить від вас.

1181
00:59:49,262 --> 00:59:52,470
Я попереджаю вас заздалегідь, що
Trie, як правило, трохи складніше

1182
00:59:52,470 --> 00:59:54,520
тільки тому, що є багато
більше покажчики відстежувати.

1183
00:59:54,520 --> 00:59:55,645
Але повністю до вас, хлопці.

1184
00:59:55,645 --> 00:59:58,742
Це набагато більш ефективно,
в більшості випадків.

1185
00:59:58,742 --> 01:00:01,450
Ви хочете, щоб дійсно бути в змозі тримати
трек всіх ваших покажчиків.

1186
01:00:01,450 --> 01:00:03,850
Як зробити те ж саме
що я тут роблю.

1187
01:00:03,850 --> 01:00:06,871
Коли ви намагаєтеся вставити
значення в хеш-таблицю або видалити,

1188
01:00:06,871 --> 01:00:08,620
переконайтеся, що ви
дійсно відстеження

1189
01:00:08,620 --> 01:00:11,860
де всі, тому що
це дійсно легко, якщо я

1190
01:00:11,860 --> 01:00:14,727
намагаюся вставити, як слово, Енді.

1191
01:00:14,727 --> 01:00:16,810
Давайте просто скажемо, що це
реальне слово, слово, Енді,

1192
01:00:16,810 --> 01:00:19,640
в гігантський список зі слів.

1193
01:00:19,640 --> 01:00:22,450
>> Якщо я просто випадково перепризначити
покажчик так, ой,

1194
01:00:22,450 --> 01:00:24,940
там йде повноту
решта мого пов'язаного списку.

1195
01:00:24,940 --> 01:00:26,897
Тепер єдине слово я
є Енді, і в даний час

1196
01:00:26,897 --> 01:00:29,230
всі Іншими словами в
Словники були втрачені.

1197
01:00:29,230 --> 01:00:31,370
І тому ви хочете, щоб переконатися, що ви
відслідковувати всі ваші покажчики

1198
01:00:31,370 --> 01:00:33,661
інакше ви збираєтеся отримати
величезні проблеми в коді.

1199
01:00:33,661 --> 01:00:35,840
Намалюйте речі ретельно, крок за кроком.

1200
01:00:35,840 --> 01:00:37,870
Це робить його набагато легше думати.

1201
01:00:37,870 --> 01:00:40,910
>> І, нарешті, ви хочете, щоб мати можливість
перевірити продуктивність вашої програми

1202
01:00:40,910 --> 01:00:41,618
на великій дошці.

1203
01:00:41,618 --> 01:00:43,710
Якщо ви, хлопці, взяти
подивитися на CS50 прямо зараз,

1204
01:00:43,710 --> 01:00:45,210
у нас є те, що називається велику раду.

1205
01:00:45,210 --> 01:00:50,200
Це оцінка лист найшвидший
Перевірка орфографії раз по всіх CS50

1206
01:00:50,200 --> 01:00:55,720
Прямо зараз, я думаю, що верх як 10
Я думаю, що раз вісім з них є співробітниками.

1207
01:00:55,720 --> 01:00:57,960
Ми дійсно хочу вас, хлопці, щоб бити нас.

1208
01:00:57,960 --> 01:01:00,870
>> Всі з нас намагалися реалізувати
швидкий код, наскільки це можливо.

1209
01:01:00,870 --> 01:01:04,880
Ми хочемо, щоб ви, хлопці, щоб спробувати заперечити
нам і здійснити швидше, ніж всіх нас

1210
01:01:04,880 --> 01:01:05,550
може.

1211
01:01:05,550 --> 01:01:07,970
І так це дійсно
перший раз, що ми

1212
01:01:07,970 --> 01:01:12,680
прошу вас, хлопці, щоб зробити PSET, що
Ви дійсно можете зробити в будь-який метод

1213
01:01:12,680 --> 01:01:13,760
ти хочеш.

1214
01:01:13,760 --> 01:01:17,730
>> Я завжди кажу, що це більше схоже
до вирішення реальних, вірно?

1215
01:01:17,730 --> 01:01:19,550
Я говорю, гей, ти мені потрібен, щоб зробити це.

1216
01:01:19,550 --> 01:01:21,380
Побудувати програму, яка робить це для мене.

1217
01:01:21,380 --> 01:01:22,630
Зробіть це, як ви.

1218
01:01:22,630 --> 01:01:24,271
Я просто знаю, що я хочу, щоб постити.

1219
01:01:24,271 --> 01:01:25,770
Це ваше завдання на цьому тижні.

1220
01:01:25,770 --> 01:01:27,531
Ви, хлопці, ми йдемо
щоб дати вам завдання.

1221
01:01:27,531 --> 01:01:29,030
Ми збираємося дати вам виклик.

1222
01:01:29,030 --> 01:01:31,559
І тоді це до вас, хлопці
повністю тільки з'ясувати

1223
01:01:31,559 --> 01:01:34,100
що найшвидший і
ефективний спосіб здійснити це.

1224
01:01:34,100 --> 01:01:34,600
Так?

1225
01:01:34,600 --> 01:01:37,476
>> АУДИТОРІЯ: Ми дозволили, якщо
хотів досліджувати швидкі способи

1226
01:01:37,476 --> 01:01:40,821
зробити хеш-таблиці на сайті, ми можемо зробити
що і цитувати код чуже?

1227
01:01:40,821 --> 01:01:42,070
ANDI Пен: Так, абсолютно нормально.

1228
01:01:42,070 --> 01:01:44,320
Так що, якщо ви, хлопці, читати
специфікації, є лінія

1229
01:01:44,320 --> 01:01:48,310
в специфікації сказано, що ви, хлопці
повністю вільні досліджувати хеш

1230
01:01:48,310 --> 01:01:51,070
функції на те, що деякі
з швидких хеш-функцій

1231
01:01:51,070 --> 01:01:54,720
вести справи через в
Поки ви привести цей код.

1232
01:01:54,720 --> 01:01:57,220
Таким чином, деякі люди вже
з'ясували швидких способів

1233
01:01:57,220 --> 01:02:00,250
робити перевірку орфографії, швидкого
способи зберігання інформації.

1234
01:02:00,250 --> 01:02:02,750
Всього до вас, хлопці, якщо вам
хочу просто взяти, так?

1235
01:02:02,750 --> 01:02:04,045
Переконайтеся, що ви цитування.

1236
01:02:04,045 --> 01:02:06,170
Завдання тут дійсно
що ми намагаємося перевірити

1237
01:02:06,170 --> 01:02:09,750
переконавшись, що ви знаєте,
Ваш шлях навколо покажчики.

1238
01:02:09,750 --> 01:02:12,700
Як далеко, як ви реалізації
фактичний хеш-функція

1239
01:02:12,700 --> 01:02:15,070
і, підійшовши з подібним
математика, щоб зробити це,

1240
01:02:15,070 --> 01:02:17,570
ви, хлопці, можете досліджувати всі
методи онлайн ви, хлопці, хочете.

1241
01:02:17,570 --> 01:02:17,996
Так?

1242
01:02:17,996 --> 01:02:19,700
>> АУДИТОРІЯ: Чи можемо ми Наведу лише
за допомогою [нерозбірливо]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Пен: Так.

1244
01:02:20,120 --> 01:02:22,328
Ви можете просто в свій коментар,
Ви можете цитувати, як, ну,

1245
01:02:22,328 --> 01:02:26,127
взяті з балаканина, балаканина,
Йадав, хеш-функція.

1246
01:02:26,127 --> 01:02:27,210
Хто-небудь є які-небудь питання?

1247
01:02:27,210 --> 01:02:29,694
Ми насправді віяв
через розділ і сьогодні.

1248
01:02:29,694 --> 01:02:31,610
Я буду сюди, щоб
відповісти на питання, а також.

1249
01:02:31,610 --> 01:02:36,570
>> Крім того, як я сказав, офіс
годин сьогодні ввечері і завтра.

1250
01:02:36,570 --> 01:02:40,307
Специфікація цьому тижні насправді
супер просто і супер короткі читати.

1251
01:02:40,307 --> 01:02:43,140
Я хотів би запропонувати поглянути, просто
прочитати повністю від нього.

1252
01:02:43,140 --> 01:02:45,730
>> І насправді Zamyla проведе вас
через кожну з функцій

1253
01:02:45,730 --> 01:02:49,796
необхідно реалізувати, і тому
дуже, дуже ясно, як усі.

1254
01:02:49,796 --> 01:02:51,920
Просто переконайтеся, що ви
відстеження покажчиків.

1255
01:02:51,920 --> 01:02:53,650
Це дуже складна PSET.

1256
01:02:53,650 --> 01:02:56,744
>> Це не виклик, тому що, як,
о, поняття набагато більше

1257
01:02:56,744 --> 01:02:59,160
важко, або у вас є, щоб дізнатися,
стільки нового синтаксису шлях

1258
01:02:59,160 --> 01:03:00,650
що ви зробили за останній PSET.

1259
01:03:00,650 --> 01:03:03,320
Це PSET важко, тому що
Є так багато покажчиків,

1260
01:03:03,320 --> 01:03:06,980
і то це дуже, дуже легко відразу
у вас є помилка в коді не зможе

1261
01:03:06,980 --> 01:03:08,315
щоб знайти, де що помилка є.

1262
01:03:08,315 --> 01:03:13,200
>> І так повне і абсолютне віра в вас
хлопці, щоб мати можливість перемогти нашу [нерозбірливо]

1263
01:03:13,200 --> 01:03:13,700
Написання.

1264
01:03:13,700 --> 01:03:16,640
Я насправді не який-небудь письмове шахту
поки немає, але я збираюся написати мій.

1265
01:03:16,640 --> 01:03:19,070
Тому, коли ви пишете
твоє, я буду писати мої.

1266
01:03:19,070 --> 01:03:21,070
Я збираюся спробувати зробити
мій швидше, ніж ваша.

1267
01:03:21,070 --> 01:03:23,940
Ми побачимо, хто має найшвидший один.

1268
01:03:23,940 --> 01:03:27,340
>> І так, я буду бачити все
ви, хлопці, тут у вівторок.

1269
01:03:27,340 --> 01:03:29,510
Я побіжу вигляд ніби майстерні Pset.

1270
01:03:29,510 --> 01:03:32,640
Все це розділах
тижня, Pset семінари,

1271
01:03:32,640 --> 01:03:36,690
так що ви, хлопці, є багато можливостей
за допомогою, години роботи, як завжди,

1272
01:03:36,690 --> 01:03:41,330
і я дійсно з нетерпінням чекаю
читати весь код ваші хлопці.

1273
01:03:41,330 --> 01:03:44,160
У мене є тести тут якщо ви
хлопці, хочете приїхати отримати ті.

1274
01:03:44,160 --> 01:03:45,880
Це все.

1275
01:03:45,880 --> 01:03:48,180