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

2
00:00:00,500 --> 00:00:05,120
[Музика, яка грає]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
СПІКЕР 1: Гаразд.

5
00:00:12,900 --> 00:00:14,600
Все добро пожаловать в розділ.

6
00:00:14,600 --> 00:00:18,660
Я сподіваюся, що ви все успішно
оговтався від вашої вікторини

7
00:00:18,660 --> 00:00:19,510
з минулого тижня.

8
00:00:19,510 --> 00:00:22,564
Я знаю, що це трохи божевільні в рази.

9
00:00:22,564 --> 00:00:25,230
Як я вже говорив раніше, якщо ви
в межах стандартного відхилення,

10
00:00:25,230 --> 00:00:28,188
насправді не турбуватися про це, особливо
для менш комфортною розділі.

11
00:00:28,188 --> 00:00:30,230
Ось про те, де ви повинні бути.

12
00:00:30,230 --> 00:00:32,850
>> Якщо ви зробили великий, то дивним.

13
00:00:32,850 --> 00:00:33,650
Слава вам.

14
00:00:33,650 --> 00:00:36,149
І якщо ви відчуваєте, як вам потрібно
трохи більше допомоги, будь ласка,

15
00:00:36,149 --> 00:00:38,140
не соромтеся, щоб досягти
до будь-якої з TFS.

16
00:00:38,140 --> 00:00:40,030
Ми всі тут, щоб допомогти.

17
00:00:40,030 --> 00:00:40,960
>> Ось чому ми вчимо.

18
00:00:40,960 --> 00:00:44,550
Ось чому я тут кожен понеділок для вас
Хлопці і в офісі годин по четвергах.

19
00:00:44,550 --> 00:00:48,130
Тому, будь ласка, не соромтеся, дайте мені знати,
якщо ви турбуєтеся про що-небудь

20
00:00:48,130 --> 00:00:52,450
або якщо що-небудь на вікторині
що ви дійсно хотіли б звернутися.

21
00:00:52,450 --> 00:00:56,940
>> Так повістка дня на сьогодні
все про структури даних.

22
00:00:56,940 --> 00:01:01,520
Деякі з них просто буде просто
щоб ви ознайомилися з ними.

23
00:01:01,520 --> 00:01:04,870
Ви ніколи не можете реалізувати
їм у цьому класі.

24
00:01:04,870 --> 00:01:08,690
Деякі з них ви,
як для вашого SPELLER PSET.

25
00:01:08,690 --> 00:01:11,380
>> Ви будете мати вибір
між хеш-таблиць і спроб.

26
00:01:11,380 --> 00:01:13,680
Таким чином, ми будемо безумовно над тими.

27
00:01:13,680 --> 00:01:18,690
Це буде точно більше виду
з розділу високий рівень сьогодні, хоча,

28
00:01:18,690 --> 00:01:22,630
бо є багато з них, і якщо
ми пішли в деталі реалізації

29
00:01:22,630 --> 00:01:26,490
на всі з них, ми не були б
навіть пройти через пов'язані списки

30
00:01:26,490 --> 00:01:28,520
і, може бути, трохи хеш-таблиці.

31
00:01:28,520 --> 00:01:31,200
>> Так, ведмідь зі мною.

32
00:01:31,200 --> 00:01:33,530
Ми не збираємося робити
стільки кодування на цей раз.

33
00:01:33,530 --> 00:01:36,870
Якщо у вас є які-небудь питання з цього приводу
або ви хочете побачити це реалізується

34
00:01:36,870 --> 00:01:39,260
або спробувати його на собі,
Я безумовно рекомендую

35
00:01:39,260 --> 00:01:44,250
збирається study.cs50.net, які
є приклади всіх з них.

36
00:01:44,250 --> 00:01:46,400
Це матиме свої PowerPoints
з примітками, які ми

37
00:01:46,400 --> 00:01:50,860
як правило, використовують, а також деякі програмування
вправи, особливо для речей

38
00:01:50,860 --> 00:01:55,250
як пов'язані списки і бінарні
дерева стеки і підказки.

39
00:01:55,250 --> 00:01:59,590
Так трохи більше високий рівень, який
могло б бути добре для вас, хлопці.

40
00:01:59,590 --> 00:02:01,320
>> Так з цим, ми почнемо.

41
00:02:01,320 --> 00:02:03,060
А також, yes-- вікторини.

42
00:02:03,060 --> 00:02:06,550
Я думаю, що більшість з вас, хто в
мій розділ є свої вікторини,

43
00:02:06,550 --> 00:02:12,060
але хто приходить в або якоїсь причини ви
ні, вони прямо тут, в передній.

44
00:02:12,060 --> 00:02:12,740
>> Так зв'язкові списки.

45
00:02:12,740 --> 00:02:15,650
Я знаю цей вид йде
для резервного перед вашою вікторини.

46
00:02:15,650 --> 00:02:17,940
Це було за тиждень до
що ми дізналися про це.

47
00:02:17,940 --> 00:02:21,040
Але в цьому випадку, ми просто
піти трохи більш докладно.

48
00:02:21,040 --> 00:02:25,900
>> Так чому ми могли б вибрати
пов'язаний список по масиву?

49
00:02:25,900 --> 00:02:27,130
Що відрізняє їх?

50
00:02:27,130 --> 00:02:27,630
Да?

51
00:02:27,630 --> 00:02:30,464
>> АУДИТОРІЯ: Ви можете розширити пов'язані
список порівняно з фіксованим розміром масиву в.

52
00:02:30,464 --> 00:02:31,171
СПІКЕР 1: Право.

53
00:02:31,171 --> 00:02:33,970
Масив має фіксований розмір в той час як
Зв'язаний список має змінний розмір.

54
00:02:33,970 --> 00:02:36,970
Так що, якщо ми не знаємо, як
багато ми хочемо зберегти,

55
00:02:36,970 --> 00:02:39,880
Зв'язаний список дає нам відмінний
спосіб зробити це, тому що ми можемо просто

56
00:02:39,880 --> 00:02:43,730
додати на іншому вузлі, і додати на
другий вузол і додати на іншому вузлі.

57
00:02:43,730 --> 00:02:45,750
Але що може бути компроміс?

58
00:02:45,750 --> 00:02:49,521
Хтось пам'ятає компроміс
між масивами і пов'язані списки?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> АУДИТОРІЯ: Ви повинні
пройти через всі шляхи

61
00:02:51,460 --> 00:02:53,738
через зв'язаний список
знайти елемент у списку.

62
00:02:53,738 --> 00:02:55,570
В масиві, ви можете
просто знайти елемент.

63
00:02:55,570 --> 00:02:56,278
>> СПІКЕР 1: Право.

64
00:02:56,278 --> 00:02:57,120
Так з arrays--

65
00:02:57,120 --> 00:02:58,500
>> АУДИТОРІЯ: [нерозбірливо].

66
00:02:58,500 --> 00:03:01,090
>> СПІКЕР 1: С масивами, у нас є
те, що називається довільним доступом.

67
00:03:01,090 --> 00:03:04,820
Означає, що якщо ми хочемо що
або п'ята точка зі списку

68
00:03:04,820 --> 00:03:07,230
або п'ята точка нашого
Масив, ми можемо просто взяти його.

69
00:03:07,230 --> 00:03:10,440
Якщо це зв'язаний список, у нас є
для перебору, чи не так?

70
00:03:10,440 --> 00:03:14,020
Так доступ до елементу в
Масив є постійна часу,

71
00:03:14,020 --> 00:03:19,530
в той час як зі зв'язаним списком було б
швидше за все, буде лінійний час, тому що, може бути,

72
00:03:19,530 --> 00:03:21,370
наш елемент повністю в кінці.

73
00:03:21,370 --> 00:03:23,446
Ми повинні шукати через все.

74
00:03:23,446 --> 00:03:25,320
Так з усіма цими даними
структури, які ми збираємося

75
00:03:25,320 --> 00:03:29,330
щоб витрачати трохи більше часу на,
які плюси і мінуси.

76
00:03:29,330 --> 00:03:31,480
Коли може ми хочемо
використовувати один над іншим?

77
00:03:31,480 --> 00:03:34,970
І це почасти
більше, що потрібно забрати.

78
00:03:34,970 --> 00:03:40,140
>> Таким чином, ми маємо тут
Визначення вузла.

79
00:03:40,140 --> 00:03:43,040
Це як один з елементів
наш зв'язаний список, чи не так?

80
00:03:43,040 --> 00:03:46,180
Таким чином, ми всі знайомі
з нашими ЬурейеЕ структур,

81
00:03:46,180 --> 00:03:47,980
які ми розглянули в огляді востаннє.

82
00:03:47,980 --> 00:03:53,180
Це була в основному просто створення
другий тип даних, які ми могли б використовувати.

83
00:03:53,180 --> 00:03:57,930
>> І в цьому випадку, це якась вузол
що проведе деякий ціле число в.

84
00:03:57,930 --> 00:04:00,210
І тоді те, що друга частина тут?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Будь?

87
00:04:05,677 --> 00:04:06,680
>> АУДИТОРІЯ: [нерозбірливо].

88
00:04:06,680 --> 00:04:07,020
>> СПІКЕР 1: Так.

89
00:04:07,020 --> 00:04:08,400
Це покажчик на наступний вузол.

90
00:04:08,400 --> 00:04:12,610
Таким чином, це має бути насправді тут.

91
00:04:12,610 --> 00:04:18,790
Це покажчик типу
вузол до наступної речі.

92
00:04:18,790 --> 00:04:22,410
І ось що вони
охоплює нашу вузол.

93
00:04:22,410 --> 00:04:24,060
Прохолодний.

94
00:04:24,060 --> 00:04:29,390
>> Гаразд, так з пошуком, як ми були
просто говорю, перш ніж руки, якщо ви

95
00:04:29,390 --> 00:04:31,840
буде шукати через,
у вас є насправді ітерації

96
00:04:31,840 --> 00:04:33,660
через зв'язаний список.

97
00:04:33,660 --> 00:04:38,530
Так що, якщо ми шукаємо числа
9, ми б почати в нашій голові

98
00:04:38,530 --> 00:04:41,520
і що вказує нам на початку
нашої пов'язаного списку, чи не так?

99
00:04:41,520 --> 00:04:44,600
І ми говоримо: добре, робить це
вузол містить число 9?

100
00:04:44,600 --> 00:04:45,690
Ні?

101
00:04:45,690 --> 00:04:47,500
>> Гаразд, іди до наступного.

102
00:04:47,500 --> 00:04:48,312
Дотримуйтесь його.

103
00:04:48,312 --> 00:04:49,520
Містить вона число 9?

104
00:04:49,520 --> 00:04:50,570
Ні.

105
00:04:50,570 --> 00:04:51,550
Слідуйте наступний.

106
00:04:51,550 --> 00:04:55,490
>> Так що ми повинні насправді ітерації
через нашу пов'язаного списку.

107
00:04:55,490 --> 00:05:00,070
Ми не можемо просто піти прямо туди, де 9.

108
00:05:00,070 --> 00:05:05,860
І якщо ви, хлопці, насправді хочете, щоб
побачити деякі псевдо-код там.

109
00:05:05,860 --> 00:05:10,420
У нас є функція пошуку тут
що бере in-- що ж потрібно в?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Що ти думаєш?

112
00:05:14,320 --> 00:05:15,960
Так легким.

113
00:05:15,960 --> 00:05:17,784
Що це?

114
00:05:17,784 --> 00:05:18,700
АУДИТОРІЯ: [нерозбірливо].

115
00:05:18,700 --> 00:05:20,366
СПІКЕР 1: ми шукаємо число.

116
00:05:20,366 --> 00:05:20,980
Чи не так?

117
00:05:20,980 --> 00:05:22,875
І що б це відповідати?

118
00:05:22,875 --> 00:05:25,020
Це покажчик на?

119
00:05:25,020 --> 00:05:26,000
>> АУДИТОРІЯ: вузол.

120
00:05:26,000 --> 00:05:28,980
>> СПІКЕР 1: вузол в список
що ми дивимося на, чи не так?

121
00:05:28,980 --> 00:05:33,700
Тому у нас є деякі вузли покажчик тут.

122
00:05:33,700 --> 00:05:37,240
Це точка, що збирається
насправді перебору нашому списку.

123
00:05:37,240 --> 00:05:39,630
Ми встановлюємо його рівним список
бо це просто

124
00:05:39,630 --> 00:05:44,380
вважаючи його рівним
почати нашого пов'язаного списку.

125
00:05:44,380 --> 00:05:50,660
>> І в той час як це не NULL, тоді як
у нас ще є речі в нашому списку,

126
00:05:50,660 --> 00:05:55,580
перевірте, якщо цей вузол має
число ми шукаємо.

127
00:05:55,580 --> 00:05:57,740
Повернутися правда.

128
00:05:57,740 --> 00:06:01,070
В іншому випадку, відновите його, чи не так?

129
00:06:01,070 --> 00:06:04,870
>> Якщо це NULL, ми виходимо з нашого
в той час як цикл і повернутися хибним

130
00:06:04,870 --> 00:06:08,340
тому що це означає, що ми не знайшли його.

131
00:06:08,340 --> 00:06:11,048
Чи всі отримати, як це працює?

132
00:06:11,048 --> 00:06:11,548
Добре.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Так з вставки, ви
є три різні способи.

135
00:06:20,260 --> 00:06:25,250
Ви можете випереджати, ви можете додати
і ви можете вставити в асорті.

136
00:06:25,250 --> 00:06:28,215
В цьому випадку, ми
збираюся робити препендом.

137
00:06:28,215 --> 00:06:33,380
Хто-небудь знає, як ті,
три випадки можуть відрізнятися?

138
00:06:33,380 --> 00:06:36,920
>> Так перед ім'ям означає, що ви поклали
це в передній частині вашого списку.

139
00:06:36,920 --> 00:06:39,770
Так що це означатиме, що незалежно від того,
що ваш вузол, незалежно від того,

140
00:06:39,770 --> 00:06:43,160
що значення, що ви збираєтеся
поставити його прямо тут, перед, ОК?

141
00:06:43,160 --> 00:06:45,160
Це буде перший
елемент у списку.

142
00:06:45,160 --> 00:06:49,510
>> Якщо ви додаєте його, це буде
йти до задньої частини списку.

143
00:06:49,510 --> 00:06:54,010
І вставити в асорті означає, що ви
збирається поставити насправді в те місце,

144
00:06:54,010 --> 00:06:57,700
де він тримає ваш зв'язаний список відсортований.

145
00:06:57,700 --> 00:07:00,810
Знову ж, як ви використовуєте
ті, і коли ви використовуєте

146
00:07:00,810 --> 00:07:02,530
їм буде варіюватися в залежності від вашого випадку.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Якщо це не потрібно
сортувати, перед ім'ям, як правило,

149
00:07:07,750 --> 00:07:10,460
бути тим, що більшість людей
використовувати, тому що ви не

150
00:07:10,460 --> 00:07:15,680
повинні пройти через весь список
щоб знайти кінець, щоб додати його на, чи не так?

151
00:07:15,680 --> 00:07:17,720
Ви можете просто дотримуватися його прямо в.

152
00:07:17,720 --> 00:07:21,930
>> Так що ми будемо проходити через
вставка 1 прямо зараз.

153
00:07:21,930 --> 00:07:26,360
Так що те, що я збираюся
дуже рекомендую на цьому PSET

154
00:07:26,360 --> 00:07:29,820
є залучення речі, як завжди.

155
00:07:29,820 --> 00:07:35,130
Це дуже важливо, що ви оновлюєте
Ваші вказівники в правильному порядку

156
00:07:35,130 --> 00:07:38,620
тому що, якщо ви оновлюєте їх
трохи не в порядку,

157
00:07:38,620 --> 00:07:42,210
Ви будете в кінцевому підсумку
втрати частини вашого списку.

158
00:07:42,210 --> 00:07:49,680
>> Так, наприклад, в даному випадку, ми
каже керівник просто навести на 1.

159
00:07:49,680 --> 00:07:56,070
Якщо ми просто робимо, що
без збереження цього 1,

160
00:07:56,070 --> 00:07:58,570
ми поняття не маємо, що
1 слід вказати на зараз

161
00:07:58,570 --> 00:08:02,490
бо ми втратили те, що
Глава вказав на.

162
00:08:02,490 --> 00:08:05,530
Так одна справа пам'ятати
коли ви робите препендом

163
00:08:05,530 --> 00:08:09,630
це, щоб врятувати те, що
голова вказує на перший,

164
00:08:09,630 --> 00:08:15,210
потім перепризначити його, а потім обновити
що ваш новий вузол повинен вказувати на.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
В цьому випадку, це один із способів зробити це.

167
00:08:22,560 --> 00:08:25,440
>> Так що, якби ми зробили це таким чином
де ми просто перепризначено голову,

168
00:08:25,440 --> 00:08:30,320
ми втрачаємо в основному наша
Весь список, чи не так?

169
00:08:30,320 --> 00:08:38,000
Один зі способів зробити це, щоб мати 1 пункт до
Далі, а потім головки точку 1.

170
00:08:38,000 --> 00:08:42,650
Або ви можете зробити вигляд, як
тимчасового зберігання, які я казав о.

171
00:08:42,650 --> 00:08:45,670
>> Але перепризначення програми Your
покажчики в правильному порядку

172
00:08:45,670 --> 00:08:48,750
буде дуже, дуже
важливо для цієї PSET.

173
00:08:48,750 --> 00:08:53,140
В іншому випадку, ви будете мати хеш
таблиці або спробувати що просто буде

174
00:08:53,140 --> 00:08:56,014
тільки частина слова, які ви
хочу і то you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
АУДИТОРІЯ: Що було тимчасове
зберігання, що ви говорили?

176
00:08:58,930 --> 00:09:00,305
СПІКЕР 1: тимчасове зберігання.

177
00:09:00,305 --> 00:09:02,760
Тому в основному другий
як ви могли б зробити це

178
00:09:02,760 --> 00:09:07,650
зберігатиме главу то, як
зберігати йому тимчасову змінну.

179
00:09:07,650 --> 00:09:11,250
Призначають його по 1 і
потім обновити 1 до точки

180
00:09:11,250 --> 00:09:13,830
до того, що глава використовується, щоб вказати на.

181
00:09:13,830 --> 00:09:16,920
Таким чином, очевидно,
елегантнішим, бо вас

182
00:09:16,920 --> 00:09:20,770
не потрібно тимчасове значення, але
просто пропонуючи ще один спосіб зробити це.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
І ми, дійсно є
деякий код для цього.

185
00:09:25,790 --> 00:09:28,080
Так що для зв'язаного списку, ми
насправді є деякий код.

186
00:09:28,080 --> 00:09:31,930
Так, перенесіть сюди, це випереджаючи.

187
00:09:31,930 --> 00:09:34,290
Так що це входить в його в голові.

188
00:09:34,290 --> 00:09:38,820
>> Так перша річ, ви повинні
створити новий вузол, звичайно,

189
00:09:38,820 --> 00:09:40,790
і перевірити на NULL.

190
00:09:40,790 --> 00:09:43,250
Завжди добре.

191
00:09:43,250 --> 00:09:47,840
І тоді вам потрібно присвоїти значення.

192
00:09:47,840 --> 00:09:51,260
Всякий раз, коли ви створюєте новий вузол, вам
не знаю, що це, вказуючи на наступний,

193
00:09:51,260 --> 00:09:54,560
так що ви хочете, щоб ініціалізувати його, щоб NULL.

194
00:09:54,560 --> 00:09:58,760
Якщо це зрештою вказуючи на щось
ще, він отримує перепризначений, і це прекрасно.

195
00:09:58,760 --> 00:10:00,740
Якщо це перше, що
в списку, він повинен

196
00:10:00,740 --> 00:10:04,270
вказувати на NULL, тому що
що це кінець списку.

197
00:10:04,270 --> 00:10:12,410
>> Отже, щоб вставити його, ми бачимо тут ми
присвоюємо наступний цінність нашого вузла

198
00:10:12,410 --> 00:10:17,380
бути все, що голова,
яка є те, що ми мали тут.

199
00:10:17,380 --> 00:10:19,930
Це те, що ми тільки що зробили.

200
00:10:19,930 --> 00:10:25,820
І тоді ми присвоюємо голову до точки
на наш новий вузол, бо пам'ятаю,

201
00:10:25,820 --> 00:10:31,090
Новий деякий покажчик на вузол,
і це саме те, що голова.

202
00:10:31,090 --> 00:10:34,370
Саме тому ми
Тобто ця стрілка аксессор.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Прохолодний?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> АУДИТОРІЯ: Чи є у нас в
инициализировать новий Далі, щоб NULL-перше,

207
00:10:41,100 --> 00:10:44,240
або ми можемо просто инициализировать його очолити?

208
00:10:44,240 --> 00:10:48,210
>> СПІКЕР 1: Нова наступний
повинен бути NULL, щоб почати

209
00:10:48,210 --> 00:10:53,760
тому що ви не знаєте,
де він буде.

210
00:10:53,760 --> 00:10:56,100
Крім того, це свого роду
точно так само як парадигму.

211
00:10:56,100 --> 00:10:59,900
Ви можете встановити його рівним NULL просто зробити
Переконайтеся, що всі ваші бази покриті

212
00:10:59,900 --> 00:11:04,070
перш ніж робити які-небудь перепризначення так, що
Ви завжди гарантується, що це буде

213
00:11:04,070 --> 00:11:08,880
вказувати на певне значення
проти, як цінності сміття.

214
00:11:08,880 --> 00:11:12,210
Тому що, так, ми присвоюємо
Нова наступний автоматично,

215
00:11:12,210 --> 00:11:15,420
але це більше, як
хороша практика, щоб ініціалізувати його

216
00:11:15,420 --> 00:11:19,270
таким чином, і потім передати.

217
00:11:19,270 --> 00:11:23,420
>> Отже, двусвязного списки зараз.

218
00:11:23,420 --> 00:11:24,601
Що ми думаємо?

219
00:11:24,601 --> 00:11:26,350
Що змінилося з
двусвязного списки?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Таким чином, в наших пов'язаних списків, ми можемо
рухатися тільки в одному напрямку, чи не так?

222
00:11:34,300 --> 00:11:35,270
У нас є тільки поруч.

223
00:11:35,270 --> 00:11:36,760
Ми можемо йти тільки вперед.

224
00:11:36,760 --> 00:11:40,300
>> З двонаправлений список,
ми можемо також рухатися у зворотному напрямку.

225
00:11:40,300 --> 00:11:44,810
Таким чином, ми маємо не тільки
число, яке ми хочемо зберегти,

226
00:11:44,810 --> 00:11:50,110
у нас є, де він вказує на наступний
і де ми тільки прийшли.

227
00:11:50,110 --> 00:11:52,865
Таким чином, це дозволяє
деякі краще обходу.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Так подвійно пов'язані вузли,
дуже схожі, чи не так?

230
00:12:01,240 --> 00:12:05,000
Тільки різниця в тому, тепер ми
є поруч і попередня.

231
00:12:05,000 --> 00:12:06,235
Це єдина відмінність.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Так що, якби ми мали випереджати або append-- ми
не мають ніякого коду для цього до here--

234
00:12:14,790 --> 00:12:17,830
але якби ви були, щоб спробувати
вставте його, важливу річ

235
00:12:17,830 --> 00:12:19,980
це ви повинні зробити
що ви присвоєння

236
00:12:19,980 --> 00:12:23,360
як ваш попередній і ваші
наступний покажчик правильно.

237
00:12:23,360 --> 00:12:29,010
Таким чином, в цьому випадку, ви б
не тільки инициализировать поруч,

238
00:12:29,010 --> 00:12:31,820
ініціалізації попередня.

239
00:12:31,820 --> 00:12:36,960
Якщо ми знаходимося на початку списку, ми
буде не тільки зробити глава одно новий,

240
00:12:36,960 --> 00:12:41,750
але наш новий попередня повинні
вказують на голові, чи не так?

241
00:12:41,750 --> 00:12:43,380
>> От і вся різниця.

242
00:12:43,380 --> 00:12:47,200
І якщо ви хочете більше практики з
вони зі зв'язаними списками, з вставки,

243
00:12:47,200 --> 00:12:49,900
з видаленням, зі вставкою
в збірних списку,

244
00:12:49,900 --> 00:12:52,670
будь ласка, ознайомтеся з study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Там купа великих навчань.

246
00:12:54,870 --> 00:12:55,870
Я дуже рекомендую їх.

247
00:12:55,870 --> 00:12:59,210
Я бажаю, щоб ми встигли пройти через них
але є багато структур даних

248
00:12:59,210 --> 00:13:01,530
щоб пройти.

249
00:13:01,530 --> 00:13:02,650
>> Отже, хеш-таблиці.

250
00:13:02,650 --> 00:13:07,070
Це, мабуть, найбільш
корисно трохи для PSET

251
00:13:07,070 --> 00:13:11,090
тут, тому що ви збираєтеся бути
реалізації одного з них, або спробу.

252
00:13:11,090 --> 00:13:12,200
Мені дуже подобається, хеш-таблиці.

253
00:13:12,200 --> 00:13:13,110
Вони досить прохолодно.

254
00:13:13,110 --> 00:13:17,080
>> Тому в основному те, що
відбувається це хеш-таблиця

255
00:13:17,080 --> 00:13:22,050
коли нам дійсно потрібно швидке
вставка, видалення, і пошук.

256
00:13:22,050 --> 00:13:25,010
Ті речі, які ми
пріоритетності в хеш-таблиці.

257
00:13:25,010 --> 00:13:29,500
Вони можуть отримати досить великий,
але, як ми побачимо з спроб,

258
00:13:29,500 --> 00:13:33,040
Є речі, які набагато більше.

259
00:13:33,040 --> 00:13:38,330
>> Але в принципі, все хеш
таблиця хеш-функція

260
00:13:38,330 --> 00:13:47,215
що говорить вам, які відро покласти друг
Ваших даних, кожен з ваших елементів в.

261
00:13:47,215 --> 00:13:51,140
Простий спосіб думати про хеш-таблиці
є те, що це всього лише відра речей,

262
00:13:51,140 --> 00:13:51,770
чи не так?

263
00:13:51,770 --> 00:13:59,720
Отже, коли ви сортування речі
як першу букву свого імені,

264
00:13:59,720 --> 00:14:01,820
що ніби як хеш-таблицю.

265
00:14:01,820 --> 00:14:06,180
>> Так що, якби я був в групі, ви, хлопці, це
в групах, хто починає імені

266
00:14:06,180 --> 00:14:11,670
з тут, або той, хто день народження
в січні, лютому, березні,

267
00:14:11,670 --> 00:14:15,220
незалежно, тобто ефективно
створення хеш-таблицю.

268
00:14:15,220 --> 00:14:18,120
Це просто створення відра, що
Ви сортування елементів в

269
00:14:18,120 --> 00:14:19,520
так що ви можете знайти їх легше.

270
00:14:19,520 --> 00:14:22,300
Так Таким чином, коли мені потрібно
щоб знайти один з вас,

271
00:14:22,300 --> 00:14:24,680
У мене немає до пошуку
через кожен з ваших імен.

272
00:14:24,680 --> 00:14:29,490
Я можу бути, як, ну, я знаю, що
День народження Даніель є in--

273
00:14:29,490 --> 00:14:30,240
АУДИТОРІЯ: --April.

274
00:14:30,240 --> 00:14:30,948
СПІКЕР 1: Апрель.

275
00:14:30,948 --> 00:14:33,120
Так я дивлюся на мій квітня
відро, і якщо пощастить,

276
00:14:33,120 --> 00:14:38,270
вона буде єдиним в там і
мій час був постійним в цьому сенсі,

277
00:14:38,270 --> 00:14:41,230
в той час як, якщо я повинен дивитися
через цілу купу людей,

278
00:14:41,230 --> 00:14:43,090
це займе набагато більше часу.

279
00:14:43,090 --> 00:14:45,830
Так хеш-таблиці дійсно всього відра.

280
00:14:45,830 --> 00:14:48,630
Легкий спосіб думати про них.

281
00:14:48,630 --> 00:14:52,930
>> Так дуже важлива річ про
Хеш-таблиця є хеш-функція.

282
00:14:52,930 --> 00:14:58,140
Так про що я щойно говорив про, як
Ваш перший лист від вашого імені

283
00:14:58,140 --> 00:15:01,450
або твій день народження місяць,
це ідеї, які

284
00:15:01,450 --> 00:15:03,070
дійсно корелює з хеш-функції.

285
00:15:03,070 --> 00:15:08,900
Це просто спосіб вирішити, які
відро Ти елемент потрапляє в, ОК?

286
00:15:08,900 --> 00:15:14,850
Таким чином, для цієї PSET, ви можете подивитися
майже будь хеш-функція ви хочете.

287
00:15:14,850 --> 00:15:16,030
>> Не треба бути вашим власним.

288
00:15:16,030 --> 00:15:21,140
Є деякі дійсно класні ті з
є що робити всякі божевільні математиці.

289
00:15:21,140 --> 00:15:25,170
І якщо ви хочете, щоб ваш
перевірка орфографії супер швидкий,

290
00:15:25,170 --> 00:15:27,620
Я б точно
шукати в одному з тех.

291
00:15:27,620 --> 00:15:32,390
>> Але існують і
прості, як обчислювальних

292
00:15:32,390 --> 00:15:39,010
сума словами, як
кожна буква має свій номер.

293
00:15:39,010 --> 00:15:39,940
Обчислити суму.

294
00:15:39,940 --> 00:15:42,230
Це визначає відро.

295
00:15:42,230 --> 00:15:45,430
Вони також мають легше, що
такі ж, як усі тут,

296
00:15:45,430 --> 00:15:47,050
все B тут.

297
00:15:47,050 --> 00:15:48,920
Будь-який з них.

298
00:15:48,920 --> 00:15:55,770
>> В основному, це просто говорить вам, які
Індекс масиву ваш елемент повинен перейти в.

299
00:15:55,770 --> 00:15:58,690
Просто вирішуючи bucket--
це все хеш-функція.

300
00:15:58,690 --> 00:16:04,180
Так от у нас є приклад, який
просто перша буква рядка

301
00:16:04,180 --> 00:16:05,900
що я тільки що говорив о.

302
00:16:05,900 --> 00:16:11,900
>> Так у вас є хеш, це тільки
Перша буква вашого струнного мінус,

303
00:16:11,900 --> 00:16:16,090
який дасть вам деякі
число від 0 до 25.

304
00:16:16,090 --> 00:16:20,790
І те, що ви хочете зробити, це
переконайтеся, що це являє

305
00:16:20,790 --> 00:16:24,110
розмір вашої хеш table--
скільки є відра.

306
00:16:24,110 --> 00:16:25,860
З багатьма з них
хеш-функції, вони

307
00:16:25,860 --> 00:16:31,630
збирається повертатися значення, які могли б
бути набагато вище числа ковшів

308
00:16:31,630 --> 00:16:33,610
що ви насправді є
в хеш-таблиці,

309
00:16:33,610 --> 00:16:37,240
так що вам потрібно зробити
упевнений і мода на них.

310
00:16:37,240 --> 00:16:42,190
В іншому випадку, він збирається сказати,
ой, вона повинна бути в відрі 5000

311
00:16:42,190 --> 00:16:46,040
але у вас є тільки 30
відра в ваш хеш-таблиці.

312
00:16:46,040 --> 00:16:49,360
І, звичайно, ми всі знаємо, що це
збирається привести в деяких божевільних помилок.

313
00:16:49,360 --> 00:16:52,870
Тому переконайтеся, що мода на
Розмір вашого хеш-таблиці.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Прохолодний.

316
00:16:58,930 --> 00:17:00,506
Так зіткнень.

317
00:17:00,506 --> 00:17:02,620
Чи всі добре дотепер?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> АУДИТОРІЯ: З чого б це
повернути таку масивну значення?

320
00:17:05,900 --> 00:17:09,210
>> СПІКЕР 1: Залежно від алгоритму
що ваш хеш-функція використовує.

321
00:17:09,210 --> 00:17:12,270
Деякі з них будуть робити
божевільний множення.

322
00:17:12,270 --> 00:17:16,270
І це все про отримання
рівномірний розподіл,

323
00:17:16,270 --> 00:17:18,490
так вони роблять деякі дійсно
божевільні речі іноді.

324
00:17:18,490 --> 00:17:20,960
Це все.

325
00:17:20,960 --> 00:17:22,140
Що-небудь ще?

326
00:17:22,140 --> 00:17:22,829
Добре.

327
00:17:22,829 --> 00:17:24,480
>> Так зіткнень.

328
00:17:24,480 --> 00:17:29,270
В основному, як я вже казав,
в кращому випадку,

329
00:17:29,270 --> 00:17:32,040
будь-яке відро я дивлюся в це
матиме одне,

330
00:17:32,040 --> 00:17:34,160
так що я не повинен дивитися на все, чи не так?

331
00:17:34,160 --> 00:17:37,040
Я або знаю, що там або це
ні, і це те, що ми дійсно хочемо.

332
00:17:37,040 --> 00:17:43,960
Але якщо у нас є десятки тисяч
точки даних і менше цього числа

333
00:17:43,960 --> 00:17:48,700
ковшів, ми збираємося мати
Зіткнення де зрештою щось

334
00:17:48,700 --> 00:17:54,210
матиме в кінцевому підсумку в
Відро, що вже є елемент.

335
00:17:54,210 --> 00:17:57,390
>> Таким чином, питання, що
ми робимо в цьому випадку?

336
00:17:57,390 --> 00:17:58,480
Що ми робимо?

337
00:17:58,480 --> 00:17:59,300
У нас вже є щось там?

338
00:17:59,300 --> 00:18:00,060
Чи є у нас просто викинути його?

339
00:18:00,060 --> 00:18:00,700
>> Ні.

340
00:18:00,700 --> 00:18:01,980
Ми повинні тримати їх обох.

341
00:18:01,980 --> 00:18:06,400
Тому шлях, який ми
як правило, зробити це буде що?

342
00:18:06,400 --> 00:18:08,400
Яка структура даних
ми щойно говорили про?

343
00:18:08,400 --> 00:18:09,316
АУДИТОРІЯ: пов'язаний список.

344
00:18:09,316 --> 00:18:10,500
СПІКЕР 1: пов'язаний список.

345
00:18:10,500 --> 00:18:16,640
Так що тепер, замість того, щоб кожен з них
Відра тільки маючи один елемент,

346
00:18:16,640 --> 00:18:24,020
він збирається утримувати зв'язаний список
елементи, які були HASHED в нього.

347
00:18:24,020 --> 00:18:27,588
ОК, чи все вид це взяли?

348
00:18:27,588 --> 00:18:30,546
Тому що ми не могли мати масив
бо ми не знаємо, як багато речей

349
00:18:30,546 --> 00:18:31,730
збираються бути там.

350
00:18:31,730 --> 00:18:36,540
Зв'язаний список дозволяє
є тільки точне число, що

351
00:18:36,540 --> 00:18:38,465
хешіруются в цьому відрі, чи не так?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Так лінійного зондування є
в основному це idea--

354
00:18:50,500 --> 00:18:52,300
це один із способів боротьби з зіткненні.

355
00:18:52,300 --> 00:18:58,010
Що ви можете зробити, це якщо в цей
Справа, ягода була хешіруется в 1

356
00:18:58,010 --> 00:19:01,130
і у нас вже є
щось там, ви просто

357
00:19:01,130 --> 00:19:04,840
продовжувати йти вниз доти,
Ви знайти вільний слот.

358
00:19:04,840 --> 00:19:06,370
Це один із способів впоратися з цим.

359
00:19:06,370 --> 00:19:09,020
Інший спосіб справитися
це з тим, що ми просто

360
00:19:09,020 --> 00:19:12,280
called-- пов'язані
список називається ланцюжка.

361
00:19:12,280 --> 00:19:20,510
>> Так ця ідея працює, якщо
Ваш хеш-таблиці ви думаєте

362
00:19:20,510 --> 00:19:24,150
значно більше, ніж
встановити ваші дані, або якщо вам

363
00:19:24,150 --> 00:19:28,870
хочу спробувати і мінімізувати ланцюжка
поки це не абсолютно необхідно.

364
00:19:28,870 --> 00:19:34,050
Так одне лінійне
зондування, очевидно, означає,

365
00:19:34,050 --> 00:19:37,290
що ваш хеш-функції
це не зовсім так корисно

366
00:19:37,290 --> 00:19:42,200
тому що ви будете в кінцевому підсумку за допомогою
Ваш хеш-функція, потрапляючи в точку,

367
00:19:42,200 --> 00:19:46,400
Ви лінійний датчик до
якесь місце, що доступно.

368
00:19:46,400 --> 00:19:49,670
Але зараз, звичайно, що-небудь
ще, що закінчується там,

369
00:19:49,670 --> 00:19:52,050
Ви будете мати, щоб
пошук ще далі вниз.

370
00:19:52,050 --> 00:19:55,650
>> І є набагато більше
Пошук витрати, які

371
00:19:55,650 --> 00:19:59,820
переходить в вводі елемент
в хеш-таблиці зараз, чи не так?

372
00:19:59,820 --> 00:20:05,640
І тепер, коли ви йдете, і спробувати знайти
ягідка знову, ви збираєтеся, щоб прояснити його,

373
00:20:05,640 --> 00:20:07,742
і він збирається сказати,
ой, дивіться у відро 1,

374
00:20:07,742 --> 00:20:09,700
і це не буде
у відро 1, так що ви

375
00:20:09,700 --> 00:20:11,970
доведеться пройти
через решта з них.

376
00:20:11,970 --> 00:20:17,720
Так що іноді корисно,
але в більшості випадків,

377
00:20:17,720 --> 00:20:22,660
ми збираємося сказати, що
ланцюжка є те, що ви хочете зробити.

378
00:20:22,660 --> 00:20:25,520
>> Таким чином, ми говорили про це раніше.

379
00:20:25,520 --> 00:20:27,812
Я трохи забігаю вперед.

380
00:20:27,812 --> 00:20:33,560
Але ланцюжка в основному, що
кожен відро в хеш-таблиці

381
00:20:33,560 --> 00:20:36,120
це просто зв'язаний список.

382
00:20:36,120 --> 00:20:39,660
>> Так ще один спосіб, або більш технічний
спосіб, щоб думати про хеш-таблиці

383
00:20:39,660 --> 00:20:44,490
є те, що це просто масив
пов'язаних списків, які

384
00:20:44,490 --> 00:20:49,330
коли ви пишете свій словник
і ви намагаєтеся завантажити його,

385
00:20:49,330 --> 00:20:52,070
думати про нього, як
масив пов'язаних списків

386
00:20:52,070 --> 00:20:54,390
буде зробити це набагато простіше
для вас, щоб ініціалізувати.

387
00:20:54,390 --> 00:20:57,680
>> АУДИТОРІЯ: Так хеш-таблиці
має заздалегідь визначений розмір,

388
00:20:57,680 --> 00:20:58,980
як [нерозбірливо] відер?

389
00:20:58,980 --> 00:20:59,220
>> СПІКЕР 1: Право.

390
00:20:59,220 --> 00:21:01,655
Отже має певну кількість
Ковші, що ви determine--

391
00:21:01,655 --> 00:21:03,530
які ви, хлопці, повинні
не соромтеся грати с.

392
00:21:03,530 --> 00:21:05,269
Це може бути досить прохолодно
щоб подивитися, що відбувається

393
00:21:05,269 --> 00:21:06,810
як ви зміните свою кількість сегментів.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Але так, це має
встановити кількість ковшів.

396
00:21:11,510 --> 00:21:15,360
Що дозволяє відповідати як
багато елементів, як вам потрібно

397
00:21:15,360 --> 00:21:19,350
це окремий ланцюжка, де вас
зв'язали списки в кожному відрі.

398
00:21:19,350 --> 00:21:22,850
Це означає, що ваш хеш-таблицю
буде точно розмір

399
00:21:22,850 --> 00:21:25,440
що вам це потрібно, щоб бути, чи не так?

400
00:21:25,440 --> 00:21:27,358
Ось і вся точка пов'язаних списків.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Прохолодний.

403
00:21:32,480 --> 00:21:38,780
>> Так що все там в порядку?

404
00:21:38,780 --> 00:21:39,801
Добре.

405
00:21:39,801 --> 00:21:40,300
Ах.

406
00:21:40,300 --> 00:21:41,860
Що тільки що відбулося?

407
00:21:41,860 --> 00:21:42,960
Дійсно зараз.

408
00:21:42,960 --> 00:21:45,250
Вгадайте, хтось вбиває мене.

409
00:21:45,250 --> 00:21:52,060
>> ОК, ми збираємося піти в
нах, які трохи божевільним.

410
00:21:52,060 --> 00:21:53,140
Мені подобається хеш-таблиці.

411
00:21:53,140 --> 00:21:54,460
Я думаю, що вони дійсно здорово.

412
00:21:54,460 --> 00:21:56,710
Намагається це круто, занадто.

413
00:21:56,710 --> 00:21:59,590
>> Так хто-небудь пам'ятає, що спроба це?

414
00:21:59,590 --> 00:22:01,740
Ви повинні перейшли
це коротко в лекції?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Пам'ятаєш роду, як це працює?

417
00:22:06,377 --> 00:22:08,460
АУДИТОРІЯ: Я просто киваючи
що ми справді йшли по ній.

418
00:22:08,460 --> 00:22:09,626
СПІКЕР 1: Ми дійсно йдуть по ньому.

419
00:22:09,626 --> 00:22:13,100
Добре, ми дійсно збираємося йти
за це тепер є те, що ми говоримо.

420
00:22:13,100 --> 00:22:14,860
>> АУДИТОРІЯ: Ось для пошуку дерева.

421
00:22:14,860 --> 00:22:15,280
>> СПІКЕР 1: Так.

422
00:22:15,280 --> 00:22:16,196
Це пошукова дерево.

423
00:22:16,196 --> 00:22:16,960
Дивовижний.

424
00:22:16,960 --> 00:22:23,610
Так що, одне зауважити тут, що ми
дивимося на окремих персонажів

425
00:22:23,610 --> 00:22:24,480
тут, чи не так?

426
00:22:24,480 --> 00:22:29,710
>> Тому, перш ніж з нашим хеш-функції, ми
дивилися на словах, як в цілому,

427
00:22:29,710 --> 00:22:32,270
і тепер ми дивимося більш
на персонажів, чи не так?

428
00:22:32,270 --> 00:22:38,380
Тому у нас є Максвелла сюди і Мендель.

429
00:22:38,380 --> 00:22:47,840
Тому в основному try-- спосіб думати
про те, що кожен рівень тут

430
00:22:47,840 --> 00:22:49,000
являє собою масив з букв.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Так що це ваш кореневої вузол тут, чи не так?

433
00:22:55,790 --> 00:23:01,980
Це все символи
алфавіт для початку кожного слова.

434
00:23:01,980 --> 00:23:06,480
>> І те, що ви хочете зробити, це
скажімо, в порядку, у нас є деякі M слово.

435
00:23:06,480 --> 00:23:10,590
Ми збираємося шукати Максвелла, так
ми йдемо до М. і М точок в цілому

436
00:23:10,590 --> 00:23:14,800
інший масив, в якому кожен
Слово, поки існує

437
00:23:14,800 --> 00:23:17,044
це слово, яке має
в якості другого листа,

438
00:23:17,044 --> 00:23:19,460
за умови, що є слово, яке
є B в якості другого листа,

439
00:23:19,460 --> 00:23:24,630
він матиме покажчик
відбувається в якійсь наступний масив.

440
00:23:24,630 --> 00:23:29,290
>> Там, напевно, не
Слово, яке MP-то,

441
00:23:29,290 --> 00:23:32,980
так в P позиції в цьому
Масив, що це просто буде NULL.

442
00:23:32,980 --> 00:23:38,840
Це б сказав, добре, там немає ні слова
що M подальшим P, ОК?

443
00:23:38,840 --> 00:23:43,100
Так що, якщо ми думаємо про неї, кожен
один з цих більш дрібних речей

444
00:23:43,100 --> 00:23:47,990
насправді один з них
великі масиви з A до Z.

445
00:23:47,990 --> 00:23:55,064
Так що може бути однією з речей,
що це свого роду недоліком спробувати?

446
00:23:55,064 --> 00:23:56,500
>> АУДИТОРІЯ: Багато пам'яті.

447
00:23:56,500 --> 00:23:59,940
>> СПІКЕР 1: Це тонна пам'яті, чи не так?

448
00:23:59,940 --> 00:24:08,750
Кожен з цих блоків тут
представляє 26 місця, 26 масив елементів.

449
00:24:08,750 --> 00:24:13,680
Так намагається отримати неймовірно простір важким.

450
00:24:13,680 --> 00:24:17,100
>> Але вони дуже швидко.

451
00:24:17,100 --> 00:24:22,540
Так неймовірно швидко, але
дійсно простір неефективно.

452
00:24:22,540 --> 00:24:24,810
Вид повинен з'ясувати
з якої ви хочете.

453
00:24:24,810 --> 00:24:29,470
Це дійсно здорово для вашого PSET,
але вони займають багато пам'яті,

454
00:24:29,470 --> 00:24:30,290
так що ви компроміс.

455
00:24:30,290 --> 00:24:31,480
Да?

456
00:24:31,480 --> 00:24:34,300
>> АУДИТОРІЯ: Чи можна буде
налаштувати спробу, а потім

457
00:24:34,300 --> 00:24:37,967
коли у вас є всі
Дані в ньому, що ви need--

458
00:24:37,967 --> 00:24:39,550
Я не знаю, якщо це матиме сенс.

459
00:24:39,550 --> 00:24:42,200
Я був позбутися всіх
NULL символи, але потім

460
00:24:42,200 --> 00:24:42,910
Ви не змогли б індекс them--

461
00:24:42,910 --> 00:24:43,275
>> СПІКЕР 1: Ви як і раніше в них потребує.

462
00:24:43,275 --> 00:24:44,854
>> АУДИТОРІЯ: - точно так же кожен раз.

463
00:24:44,854 --> 00:24:45,520
СПІКЕР 1: Так.

464
00:24:45,520 --> 00:24:50,460
Ви потрібні нульові символи, щоб
Ви знаєте, якщо їсти не слово є.

465
00:24:50,460 --> 00:24:52,040
Бен у вас було щось ви хочете?

466
00:24:52,040 --> 00:24:52,540
Добре.

467
00:24:52,540 --> 00:24:54,581
Гаразд, так що ми збираємося
йти трохи більш

468
00:24:54,581 --> 00:24:58,920
в технічних деталях позаду
спробувати працювати через приклад.

469
00:24:58,920 --> 00:25:01,490
>> ОК, так що це одне і те ж.

470
00:25:01,490 --> 00:25:06,290
Тоді як у зв'язаному списку, наш головний
вид of-- що слово, яке я хочу? -

471
00:25:06,290 --> 00:25:08,350
як будувати блок був вузол.

472
00:25:08,350 --> 00:25:12,280
У спробі, у нас також є вузол,
але це визначається по-різному.

473
00:25:12,280 --> 00:25:17,000
>> Таким чином, ми маємо деяку Ьоо що
чи представляє слово в дійсності

474
00:25:17,000 --> 00:25:23,530
існує в цьому місці, а потім
у нас є деякі масив here-- вірніше,

475
00:25:23,530 --> 00:25:27,840
це покажчик на
Масив складається з 27 символів.

476
00:25:27,840 --> 00:25:33,339
А це для, в даному випадку, це
27-- Я впевнений, що всі ви, як, чекати,

477
00:25:33,339 --> 00:25:34,880
є 26 літери алфавіту.

478
00:25:34,880 --> 00:25:36,010
Чому у нас 27?

479
00:25:36,010 --> 00:25:37,870
>> Тому залежно від
як ви це реалізувати,

480
00:25:37,870 --> 00:25:43,240
це від PSET, що
дозволено для апострофи.

481
00:25:43,240 --> 00:25:46,010
Так ось чому додатковий один.

482
00:25:46,010 --> 00:25:50,500
Ви також будете мати до деяких
випадки нульової термінатор

483
00:25:50,500 --> 00:25:53,230
включений в якості одного з
персонажі, що це дозволено бути,

484
00:25:53,230 --> 00:25:56,120
і ось як вони перевіряють, щоб
побачити, якщо це кінець слова.

485
00:25:56,120 --> 00:26:01,340
Якщо ви зацікавлені, перевірити
Відео Кевіна на study.cs50,

486
00:26:01,340 --> 00:26:04,790
а також Вікіпедії є
деякі хороші ресурси там.

487
00:26:04,790 --> 00:26:09,000
>> Але ми збираємося пройти через тільки почасти
про те, як ви могли б працювати через спроби

488
00:26:09,000 --> 00:26:11,010
якщо ви дали один.

489
00:26:11,010 --> 00:26:16,230
Тому у нас є супер простий один тут, що
немає слів "летюча миша" і "зум" в них.

490
00:26:16,230 --> 00:26:18,920
І, як ми бачимо тут,
це мало місця тут

491
00:26:18,920 --> 00:26:22,560
представляє нашу Ьоо що
каже, так, це слово.

492
00:26:22,560 --> 00:26:27,060
А потім це користується нашим
масиви символів, чи не так?

493
00:26:27,060 --> 00:26:33,480
>> Отже, ми збираємося пройти через
знайти "битою" в цьому спроби.

494
00:26:33,480 --> 00:26:38,340
Так починаються у верхній частині, чи не так?

495
00:26:38,340 --> 00:26:46,290
І ми знаємо, що б відповідає
другий індекс, другий елемент

496
00:26:46,290 --> 00:26:47,840
в цьому масиві, тому що і б.

497
00:26:47,840 --> 00:26:51,340
Так приблизно друга.

498
00:26:51,340 --> 00:26:58,820
>> І це говорить, у порядку, круто, випливає, що в
наступний масив, тому що, якщо ми пам'ятаємо,

499
00:26:58,820 --> 00:27:02,160
це не що кожна з них
фактично містить елемент.

500
00:27:02,160 --> 00:27:07,110
Кожен з цих масивів
містить покажчик, чи не так?

501
00:27:07,110 --> 00:27:10,030
Це важлива відмінність, щоб зробити.

502
00:27:10,030 --> 00:27:13,450
>> Я знаю, що це буде be-- намагається є
дуже важко отримати на перший раз,

503
00:27:13,450 --> 00:27:15,241
тому, навіть якщо це
другий чи третій раз

504
00:27:15,241 --> 00:27:18,370
і він як і раніше вид
удаваній важко,

505
00:27:18,370 --> 00:27:21,199
Я обіцяю, якщо ви йдете годинник
Коротше завтра,

506
00:27:21,199 --> 00:27:22,740
це, напевно, зробити набагато більше сенсу.

507
00:27:22,740 --> 00:27:23,890
Це займає дуже багато, щоб переварити.

508
00:27:23,890 --> 00:27:27,800
Я до сих пір іноді я
як, чекати, що це спроба?

509
00:27:27,800 --> 00:27:29,080
Як я можу використовувати це?

510
00:27:29,080 --> 00:27:33,880
>> Таким чином, ми б і в цьому випадку,
яка є нашим другим показником.

511
00:27:33,880 --> 00:27:40,240
Якби ми мали, скажімо, з або
d або будь-який інший буквою,

512
00:27:40,240 --> 00:27:45,810
ми повинні відобразити цю спиною до індексу
нашого масиву, який відповідає.

513
00:27:45,810 --> 00:27:56,930
Таким чином, ми б як rchar, і ми просто
відняти від зіставити його в 0 до 25.

514
00:27:56,930 --> 00:27:58,728
Все добре, як ми
Карта наших героїв?

515
00:27:58,728 --> 00:28:00,440
Добре.

516
00:28:00,440 --> 00:28:05,980
>> Так ми йдемо до другого і ми
бачити, що, так, це не NULL.

517
00:28:05,980 --> 00:28:07,780
Ми можемо перейти до наступного масиві.

518
00:28:07,780 --> 00:28:12,300
Таким чином, ми перейдемо до цієї наступній масиву тут.

519
00:28:12,300 --> 00:28:15,500
>> І ми говоримо: добре, тепер ми
чи потрібно це тут.

520
00:28:15,500 --> 00:28:18,590
Є нульовим або робить це
насправді рухатися вперед?

521
00:28:18,590 --> 00:28:21,880
Так насправді рухається
вперед в цьому масиві.

522
00:28:21,880 --> 00:28:24,570
І ми говоримо: добре, т наша остання буква.

523
00:28:24,570 --> 00:28:27,580
Так ми йдемо в т в індексі.

524
00:28:27,580 --> 00:28:30,120
А потім ми рухаємося вперед
бо є ще один.

525
00:28:30,120 --> 00:28:38,340
І це говорять в основному, що, так,
він каже, що є слово here--

526
00:28:38,340 --> 00:28:41,750
що якщо ви будете слідувати цим
Шлях, ви приїхали

527
00:28:41,750 --> 00:28:43,210
при слові, яке ми знаємо, "Летюча миша".

528
00:28:43,210 --> 00:28:43,800
Да?

529
00:28:43,800 --> 00:28:46,770
>> АУДИТОРІЯ: Це стандартна мати що
як індекс 0, а потім є свого роду в 1

530
00:28:46,770 --> 00:28:47,660
або мати в кінці?

531
00:28:47,660 --> 00:28:48,243
>> СПІКЕР 1: Ні.

532
00:28:48,243 --> 00:28:55,360
Так що, якщо ми оглянемося на наш
Декларація тут, це логічний,

533
00:28:55,360 --> 00:28:59,490
так що це його власний елемент в вузлі.

534
00:28:59,490 --> 00:29:03,331
Так що це не частина масиву.

535
00:29:03,331 --> 00:29:03,830
Прохолодний.

536
00:29:03,830 --> 00:29:08,370
Так що, коли ми закінчимо наше слово, і ми
в цьому масиві, то, що ми хочемо зробити

537
00:29:08,370 --> 00:29:12,807
це зробити чек на це слово.

538
00:29:12,807 --> 00:29:14,390
І в цьому випадку, він повернеться так.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Так на цій ноті, ми знаємо, що "зоопарк" -
ми знаємо, як люди, які "зоопарк" це слово,

541
00:29:24,090 --> 00:29:24,820
чи не так?

542
00:29:24,820 --> 00:29:28,990
Але намагатимуться тут буде
кажуть, ні, це не так.

543
00:29:28,990 --> 00:29:33,980
І було б сказати, що, тому що ми
не позначені як слова тут.

544
00:29:33,980 --> 00:29:40,440
Навіть при тому, що ми можемо пройти
до цього масиву,

545
00:29:40,440 --> 00:29:43,890
це спроба могла сказати, що, ні,
зоопарк не в словнику

546
00:29:43,890 --> 00:29:47,070
тому що у нас не
позначивши його як такий.

547
00:29:47,070 --> 00:29:52,870
>> Так один із способів зробити that--
ой, вибачте, це один.

548
00:29:52,870 --> 00:29:59,450
Таким чином, в даному випадку, "зоопарк» не
Слово, але це в нашій спроби.

549
00:29:59,450 --> 00:30:05,690
Але в цьому, сказати, що ми хочемо його
ввести слово "баня", те, що відбувається

550
00:30:05,690 --> 00:30:08,260
це ми слідуємо through-- B, A, т.

551
00:30:08,260 --> 00:30:11,820
Ми в цьому масиві, і
ми йдемо шукати ч.

552
00:30:11,820 --> 00:30:15,220
>> В цьому випадку, коли ми
подивіться на покажчик на годину,

553
00:30:15,220 --> 00:30:17,890
це вказує на NULL, ОК?

554
00:30:17,890 --> 00:30:20,780
Так, якщо це не явно
вказуючи на іншого масиву,

555
00:30:20,780 --> 00:30:25,000
Ви припускаєте, що всі покажчики
в цьому масиві вказуючи на нуль.

556
00:30:25,000 --> 00:30:28,270
Таким чином, в цьому випадку, ч вказує
обнулити тому ми нічого не можемо зробити,

557
00:30:28,270 --> 00:30:31,540
так воно і повернеться
хибним, "баня" не тут.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Так що тепер ми насправді
збираюся пройти через

560
00:30:35,810 --> 00:30:39,790
як би ми насправді сказати,
що "зоопарк" знаходиться в нашій спроби.

561
00:30:39,790 --> 00:30:42,920
Як ми вставляємо "зоопарк" в нашій спроби?

562
00:30:42,920 --> 00:30:47,810
Таким чином, в одній і тій же способом, що ми почали з
наш зв'язаний список, ми стартуємо з кореня.

563
00:30:47,810 --> 00:30:50,600
Якщо ви сумніваєтеся, почніть з
корінь цих речей.

564
00:30:50,600 --> 00:30:53,330
>> І ми будемо говорити, добре, м

565
00:30:53,330 --> 00:30:55,650
г існує в цьому, і він робить.

566
00:30:55,650 --> 00:30:58,370
Таким чином, ви, як перейти до
Ваш наступний масив, ОК?

567
00:30:58,370 --> 00:31:01,482
А потім на наступний,
ми говоримо, добре, дійсно про існують?

568
00:31:01,482 --> 00:31:03,000
Він робить.

569
00:31:03,000 --> 00:31:04,330
Це ще раз.

570
00:31:04,330 --> 00:31:08,670
>> І так на нашому наступному, ми вже говорили,
ОК, "зоопарк" вже існує тут.

571
00:31:08,670 --> 00:31:12,440
Все, що потрібно зробити, це встановити це дорівнює
істинно, що є слово там.

572
00:31:12,440 --> 00:31:15,260
Якщо ви слідували все
до перед тією точкою,

573
00:31:15,260 --> 00:31:17,030
це слово, так що просто
встановити його рівним такі.

574
00:31:17,030 --> 00:31:17,530
Да?

575
00:31:17,530 --> 00:31:22,550
>> АУДИТОРІЯ: Отже робить, що
означає, що "ба" це слово також?

576
00:31:22,550 --> 00:31:24,120
>> СПІКЕР 1: Ні.

577
00:31:24,120 --> 00:31:28,870
Таким чином, в даному випадку, "ба", ми отримаємо
тут, ми б сказали, це слово,

578
00:31:28,870 --> 00:31:31,590
ні, і це все одно буде не.

579
00:31:31,590 --> 00:31:32,822
Добре?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> АУДИТОРІЯ: Тому, як тільки ви це
Слово і ви говорите, да, то це

582
00:31:36,360 --> 00:31:38,380
міститиме піти в м?

583
00:31:38,380 --> 00:31:42,260
>> СПІКЕР 1: Так що це має відношення до
with-- ви завантажуєте це.

584
00:31:42,260 --> 00:31:43,640
Ви говорите, "зоопарк" це слово.

585
00:31:43,640 --> 00:31:47,020
Коли ви йдете в check--
як, скажімо, ви хочете сказати ,,

586
00:31:47,020 --> 00:31:49,400
значить "зоопарк" існують в цьому словнику?

587
00:31:49,400 --> 00:31:54,200
Ви тільки збираєтеся шукати "зоопарк"
а потім перевірити, якщо це слово.

588
00:31:54,200 --> 00:31:57,291
Ви ніколи не збираєтеся переїхати
до м, бо це не

589
00:31:57,291 --> 00:31:58,290
то, що ви шукаєте.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Так що, якщо ми насправді хотіли
додати "ванну" в цій спробі,

592
00:32:08,070 --> 00:32:11,390
ми будемо робити те ж саме
як ми це робили з "зоопарком"

593
00:32:11,390 --> 00:32:15,380
крім ми побачимо, що, коли ми
спробувати добратися до ч, його не існує.

594
00:32:15,380 --> 00:32:20,090
Таким чином, ви можете думати про це як намагаються
щоб додати новий вузол у зв'язаному списку,

595
00:32:20,090 --> 00:32:27,210
таким чином, ми повинні були б додати ще один
один з цих масивів, як і.

596
00:32:27,210 --> 00:32:35,670
І тоді те, що ми робимо, ми просто встановити годину
елемент цього масиву, що вказують на це.

597
00:32:35,670 --> 00:32:39,430
>> І тоді те, що ми хотіли б зробити тут?

598
00:32:39,430 --> 00:32:43,110
Додати це дорівнює справедливо
бо це слово.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Прохолодний.

601
00:32:48,150 --> 00:32:48,700
Я знаю.

602
00:32:48,700 --> 00:32:51,170
Намагається не сама захоплююча.

603
00:32:51,170 --> 00:32:54,250
Повірте мені, я знаю.

604
00:32:54,250 --> 00:32:58,040
>> Так одна справа розуміти, з спроб,
Я сказав, що вони дуже ефективні.

605
00:32:58,040 --> 00:33:00,080
Таким чином, ми бачили вони
зайняти до тонну простору.

606
00:33:00,080 --> 00:33:01,370
Вони начебто заплутаною.

607
00:33:01,370 --> 00:33:03,367
Так чому б нам коли-небудь використовувати їх?

608
00:33:03,367 --> 00:33:05,450
Ми використовуємо їх, тому що вони
неймовірно ефективний.

609
00:33:05,450 --> 00:33:08,130
>> Так що якщо ви коли-небудь шукаєте
до Словом, ви тільки

610
00:33:08,130 --> 00:33:10,450
обмежені по довжині слова.

611
00:33:10,450 --> 00:33:15,210
Так що якщо ви шукаєте
Слово, яке має довжину п'ять,

612
00:33:15,210 --> 00:33:20,940
Ви тільки коли-небудь доведеться
зробити в більшості п'ять порівнянь, ОК?

613
00:33:20,940 --> 00:33:25,780
Таким чином, це робить його в основному постійною.

614
00:33:25,780 --> 00:33:29,150
Як вставки і пошуку
в основному постійна часу.

615
00:33:29,150 --> 00:33:33,750
>> Так що якщо ви можете коли-небудь отримати
щось в постійному часі,

616
00:33:33,750 --> 00:33:35,150
це так само добре, як він отримує.

617
00:33:35,150 --> 00:33:37,990
Ви не можете поправитися, ніж
Постійна часу для цих речей.

618
00:33:37,990 --> 00:33:43,150
Так, що є одним з
Величезні плюси спроб.

619
00:33:43,150 --> 00:33:46,780
>> Але це багато місця.

620
00:33:46,780 --> 00:33:50,380
Таким чином, ви начебто повинні вирішити,
що для вас важливіше.

621
00:33:50,380 --> 00:33:54,700
І на сучасних комп'ютерах,
простір, що спроба може зайняти до

622
00:33:54,700 --> 00:33:57,740
можливо, не впливає
Ви так багато, але, може бути,

623
00:33:57,740 --> 00:34:01,350
Ви маєте справу з чимось
що має набагато, набагато більше речей,

624
00:34:01,350 --> 00:34:02,810
і спробувати просто не розумно.

625
00:34:02,810 --> 00:34:03,000
Да?

626
00:34:03,000 --> 00:34:05,610
>> АУДИТОРІЯ: Почекайте, так у вас є 26
Букви в кожному один?

627
00:34:05,610 --> 00:34:07,440
>> СПІКЕР 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Так, у вас є 26.

629
00:34:08,570 --> 00:34:16,984
У вас є якийсь є слово маркер, а потім
у вас є 26 покажчиків в кожному з.

630
00:34:16,984 --> 00:34:17,775
І вони point--

631
00:34:17,775 --> 00:34:20,280
>> АУДИТОРІЯ: І кожен 26,
вони один у 26?

632
00:34:20,280 --> 00:34:21,500
>> СПІКЕР 1: Так.

633
00:34:21,500 --> 00:34:27,460
І ось чому, як ви можете
см, вона розширюється досить швидко.

634
00:34:27,460 --> 00:34:28,130
Добре.

635
00:34:28,130 --> 00:34:32,524
Таким чином, ми збираємося, щоб отримати в дерева, які
Я відчуваю, що це простіше і, ймовірно,

636
00:34:32,524 --> 00:34:36,150
бути миленький відстрочка
від спроб є.

637
00:34:36,150 --> 00:34:39,620
Будемо сподіватися, що більшість з вас
бачили дерево раніше.

638
00:34:39,620 --> 00:34:41,820
Не так, як досить
ті, за межами, які я

639
00:34:41,820 --> 00:34:44,340
не знаю, якщо хто-
пішов на відкритому повітрі в останній час.

640
00:34:44,340 --> 00:34:49,230
Я пішов збір яблук в ці вихідні,
і о, чорт візьми, це було красиво.

641
00:34:49,230 --> 00:34:52,250
Я не знав, листя
може виглядати, що досить.

642
00:34:52,250 --> 00:34:53,610
>> Так що це просто дерево, чи не так?

643
00:34:53,610 --> 00:34:56,790
Це лише деякі вузол, і він
вказує на купу інших вузлів.

644
00:34:56,790 --> 00:34:59,570
Як ви бачите тут, це
вид повторюється темою.

645
00:34:59,570 --> 00:35:03,720
Вузли, який вказує на вузлах є свого роду
Сутність багатьох структур даних.

646
00:35:03,720 --> 00:35:06,670
Все залежить від того, як ми
щоб вони вказують один з одним

647
00:35:06,670 --> 00:35:08,600
і як ми перетинаємо
через них і, як ми

648
00:35:08,600 --> 00:35:14,500
вставити те, що визначає
їх різні характеристики.

649
00:35:14,500 --> 00:35:17,600
>> Так що деякі терміни,
які я використовував раніше.

650
00:35:17,600 --> 00:35:20,010
Так корінь все, що знаходиться на самому верху.

651
00:35:20,010 --> 00:35:21,200
це де ми завжди починаємо.

652
00:35:21,200 --> 00:35:23,610
Ви можете думати про це як глава також.

653
00:35:23,610 --> 00:35:28,750
Але для дерев, ми, як правило,
ставляться до нього як корінь.

654
00:35:28,750 --> 00:35:32,820
>> Все в нижній here--
в дуже, дуже bottom--

655
00:35:32,820 --> 00:35:34,500
вважаються листя.

656
00:35:34,500 --> 00:35:37,210
Так що йде разом з
все дерево, що, не так?

657
00:35:37,210 --> 00:35:39,860
Листя по краях дереві.

658
00:35:39,860 --> 00:35:45,820
>> І тоді у нас також є кілька
Умови говорити про вузлах зв'язку

659
00:35:45,820 --> 00:35:46,680
один до одного.

660
00:35:46,680 --> 00:35:49,700
Тому у нас є батько,
діти, брати і сестри.

661
00:35:49,700 --> 00:35:56,260
Таким чином, в даному випадку, є 3
Батько 5, 6, і 7.

662
00:35:56,260 --> 00:36:00,370
Так батько все, що
один крок вище, що ви перебуваєте

663
00:36:00,370 --> 00:36:02,940
з посиланням на, так що просто
як родоводу.

664
00:36:02,940 --> 00:36:07,090
Будемо сподіватися, що це все трохи
трохи більш зрозумілим, ніж спроб.

665
00:36:07,090 --> 00:36:10,970
>> Брати і сестри є будь, які мають
те ж саме батько, чи не так?

666
00:36:10,970 --> 00:36:13,470
Вони на тому ж рівні, тут.

667
00:36:13,470 --> 00:36:16,960
А потім, як я був
кажучи, діти просто

668
00:36:16,960 --> 00:36:22,630
все, що на один крок нижче
даний вузол, ОК?

669
00:36:22,630 --> 00:36:23,470
Прохолодний.

670
00:36:23,470 --> 00:36:25,610
Так бінарне дерево.

671
00:36:25,610 --> 00:36:31,450
Може хто-небудь здогад на одному з
характеристики бінарного дерева?

672
00:36:31,450 --> 00:36:32,770
>> АУДИТОРІЯ: Макс два листа.

673
00:36:32,770 --> 00:36:33,478
>> СПІКЕР 1: Право.

674
00:36:33,478 --> 00:36:34,640
Так макс двох листків.

675
00:36:34,640 --> 00:36:39,730
Таким чином, в цей перш, у нас був цей один
що було три, але в бінарному дереві,

676
00:36:39,730 --> 00:36:45,000
у вас є макс двох
дітей на батьків, чи не так?

677
00:36:45,000 --> 00:36:46,970
Там інша
Цікавою особливістю.

678
00:36:46,970 --> 00:36:51,550
Хто-небудь знає, що?

679
00:36:51,550 --> 00:36:52,620
Бінарне дерево.

680
00:36:52,620 --> 00:37:00,350
>> Так бінарне дерево матиме всі
на the-- цей не sorted--

681
00:37:00,350 --> 00:37:05,320
але у відсортований бінарного дерева,
все праворуч

682
00:37:05,320 --> 00:37:08,530
більше, ніж батьків,
і все зліва

683
00:37:08,530 --> 00:37:10,035
менше, ніж батьків.

684
00:37:10,035 --> 00:37:15,690
І що було вікторина
Питання колись, так добре знати.

685
00:37:15,690 --> 00:37:19,500
Так як ми визначаємо це,
знову, у нас є ще один вузол.

686
00:37:19,500 --> 00:37:21,880
Це виглядає дуже схоже на що?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Подвійно

689
00:37:28,836 --> 00:37:29,320
>> Аудиторія: Пов'язані списки

690
00:37:29,320 --> 00:37:31,100
>> СПІКЕР 1: подвійний зв'язаний список, чи не так?

691
00:37:31,100 --> 00:37:33,690
Так що, якщо ми замінимо цей
з попереднім і наступним,

692
00:37:33,690 --> 00:37:35,670
це було б подвійно зв'язаний список.

693
00:37:35,670 --> 00:37:40,125
Але в даному випадку, ми насправді
є лівий і правий, і цим все сказано.

694
00:37:40,125 --> 00:37:41,500
В іншому випадку, це точно так же.

695
00:37:41,500 --> 00:37:43,374
У нас ще є елемент
Ви шукаєте,

696
00:37:43,374 --> 00:37:45,988
і ви просто повинні два покажчика
збирається все, що буде далі.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Так, так бінарне дерево.

699
00:37:51,870 --> 00:37:57,665
Якщо ми помічаємо, все на
тут більше than--

700
00:37:57,665 --> 00:37:59,850
або все відразу
щоб прямо тут

701
00:37:59,850 --> 00:38:02,840
більше, ніж всі,
тут менше.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Так що, якби ми мали шукати через, його
повинен виглядати дуже близько до бінарного пошуку

704
00:38:14,000 --> 00:38:14,910
тут, чи не так?

705
00:38:14,910 --> 00:38:17,640
Крім замість того щоб шукати
на половині масиву,

706
00:38:17,640 --> 00:38:21,720
ми просто дивлячись на будь-якому зліва
сторона або права сторона дерева.

707
00:38:21,720 --> 00:38:24,850
Так він отримує трохи простіше, я думаю.

708
00:38:24,850 --> 00:38:29,300
>> Так що якщо ваш корінь NULL,
Очевидно, що це просто брехня.

709
00:38:29,300 --> 00:38:33,470
І якщо це є, очевидно, що це правда.

710
00:38:33,470 --> 00:38:35,320
Якщо це менше, ніж, ми шукаємо лівого.

711
00:38:35,320 --> 00:38:37,070
Якщо це більше, ніж,
ми шукаємо право.

712
00:38:37,070 --> 00:38:39,890
Це так само, як бінарний пошук,
просто інша структура даних

713
00:38:39,890 --> 00:38:40,600
що ми використовуємо.

714
00:38:40,600 --> 00:38:42,790
Замість масиву,
це просто бінарне дерево.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> ОК, стеки.

717
00:38:48,090 --> 00:38:51,550
А також, схоже, що ми
може мати трохи часу.

718
00:38:51,550 --> 00:38:54,460
Якщо ми це зробимо, я щасливий піти
за все це знову.

719
00:38:54,460 --> 00:38:56,856
Отже, стеки.

720
00:38:56,856 --> 00:39:02,695
Хтось пам'ятає, що stacks--
будь-які характеристики стека?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> Отже, більшість з нас, я думаю, що,
їдять в їдальні halls--

723
00:39:10,400 --> 00:39:13,100
стільки, скільки ми, можливо, не подобається.

724
00:39:13,100 --> 00:39:16,900
Але очевидно, що ви можете думати про стек
буквально тільки у вигляді стопки лотків

725
00:39:16,900 --> 00:39:18,460
або стопка речей.

726
00:39:18,460 --> 00:39:21,820
І, що важливо
щоб зрозуміти, що це

727
00:39:21,820 --> 00:39:26,850
something-- характеристика
що ми називаємо це по-- є ЛІФО.

728
00:39:26,850 --> 00:39:28,450
Хто-небудь знає, що це означає?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> АУДИТОРІЯ: останнім прийшов, першим з.

731
00:39:30,650 --> 00:39:32,250
>> СПІКЕР 1: праворуч, останнім прийшов, першим з.

732
00:39:32,250 --> 00:39:36,585
Так що, якщо ми знаємо, якщо ми укладка речей
до, найпростіше захопити off--

733
00:39:36,585 --> 00:39:39,570
і, можливо, єдине, що ми можемо захопити
, Якби наш стек великий enough--

734
00:39:39,570 --> 00:39:40,850
є те, що верхній елемент.

735
00:39:40,850 --> 00:39:43,460
Тому, що б було поставити на
last-- як ми бачимо тут,

736
00:39:43,460 --> 00:39:46,370
що було штовхнув
на найбільш recently-- є

737
00:39:46,370 --> 00:39:51,160
буде першим
річ, яку ми палити, ОК?

738
00:39:51,160 --> 00:39:56,324
>> Отже, що ми маємо тут справу
другий ЬурейеЕ структура.

739
00:39:56,324 --> 00:39:58,740
Це насправді просто хотів
Crash Course в структурі даних,

740
00:39:58,740 --> 00:40:01,650
так що є багато кинуті на вас, хлопці.

741
00:40:01,650 --> 00:40:02,540
Я знаю.

742
00:40:02,540 --> 00:40:04,970
Так ще один структура.

743
00:40:04,970 --> 00:40:06,740
Ура для структур.

744
00:40:06,740 --> 00:40:16,660
>> І в цьому випадку, це якась покажчик
в масив, який має певний потенціал.

745
00:40:16,660 --> 00:40:20,830
Таким чином, це представляє наш стек
тут, як і наш фактичний масив

746
00:40:20,830 --> 00:40:22,520
що тримає наші елементи.

747
00:40:22,520 --> 00:40:24,850
А потім тут у нас є деякі розміри.

748
00:40:24,850 --> 00:40:31,170
>> І, як правило, ви хочете, щоб зберегти
трек, наскільки великий ваш стек

749
00:40:31,170 --> 00:40:36,180
тому, що він збирається, щоб дозволити
Ви зробити це, якщо ви знаєте розмір,

750
00:40:36,180 --> 00:40:39,170
це дозволяє сказати,
ОК, я на повну потужність?

751
00:40:39,170 --> 00:40:40,570
Чи можу я додати нічого більше?

752
00:40:40,570 --> 00:40:44,650
І це також говорить вам,
де у верхній частині вашого стека

753
00:40:44,650 --> 00:40:48,180
так ви знаєте, що ви
може насправді зняти.

754
00:40:48,180 --> 00:40:51,760
І що насправді відбувається в
бути трохи більш ясно.

755
00:40:51,760 --> 00:40:57,350
>> Таким чином, для поштовху, З одного боку, якщо вас
були коли-небудь реалізувати поштовх,

756
00:40:57,350 --> 00:41:01,330
як я щойно говорив, ваша
Стек має обмежений розмір, чи не так?

757
00:41:01,330 --> 00:41:03,990
Наш масив був деякий потенціал.

758
00:41:03,990 --> 00:41:04,910
Це масив.

759
00:41:04,910 --> 00:41:08,930
Це фіксований розмір, так що нам потрібно
переконатися, що ми не ставили більше

760
00:41:08,930 --> 00:41:11,950
в нашому масиві, ніж ми
насправді є місце для.

761
00:41:11,950 --> 00:41:16,900
>> Так що, коли ви створюєте поштовх
Функція, перше, що вам зробити, це скажемо, в порядку,

762
00:41:16,900 --> 00:41:18,570
у мене є місце в моїй стека?

763
00:41:18,570 --> 00:41:23,330
Тому що, якщо я не роблю, вибачте,
Я не можу зберігати елемент.

764
00:41:23,330 --> 00:41:28,980
Якщо я, то ви хочете зберегти
це на вершині стека, чи не так?

765
00:41:28,980 --> 00:41:31,325
>> І саме тому у нас є
відслідковувати нашого розміру.

766
00:41:31,325 --> 00:41:35,290
Якщо ми не відслідковувати нашого розміру,
ми не знаємо, куди його покласти.

767
00:41:35,290 --> 00:41:39,035
Ми не знаємо, як багато речей
в нашому масиві вже.

768
00:41:39,035 --> 00:41:41,410
Як очевидно, є способи
що, може бути, ви могли б зробити це.

769
00:41:41,410 --> 00:41:44,610
Ви можете ініціалізувати все, щоб NULL
а потім перевірити наявність останньої NULL,

770
00:41:44,610 --> 00:41:47,950
але набагато простіше річ просто
сказати, в порядку, відстежувати розмір.

771
00:41:47,950 --> 00:41:51,840
Як я знаю, у мене є чотири елементи
в моєму масиві, так наступна річ

772
00:41:51,840 --> 00:41:55,930
що ми ставимо на, ми
збираєтеся зберігати в індексі 4.

773
00:41:55,930 --> 00:42:00,940
І тоді, звичайно, це означає, що
Ви успішно штовхнув щось

774
00:42:00,940 --> 00:42:03,320
на свій стек, ви
хочу збільшити розмір

775
00:42:03,320 --> 00:42:08,880
так що ви знаєте, де ви знаходитесь, так
що ви можете натиснути більше речей на.

776
00:42:08,880 --> 00:42:12,730
>> Так що, якщо ми намагаємося поп
щось з стека,

777
00:42:12,730 --> 00:42:16,072
що може бути в першу чергу
що ми хочемо, щоб перевірити?

778
00:42:16,072 --> 00:42:18,030
Ти намагаєшся взяти
щось від вашого стека.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Ви впевнені, що є
щось в вашому стеці?

781
00:42:24,781 --> 00:42:25,280
Ні.

782
00:42:25,280 --> 00:42:26,894
Так що, можливо, ми хочемо перевірити?

783
00:42:26,894 --> 00:42:27,810
>> АУДИТОРІЯ: [нерозбірливо].

784
00:42:27,810 --> 00:42:29,880
СПІКЕР 1: Перевірте розмір?

785
00:42:29,880 --> 00:42:31,840
Розмір.

786
00:42:31,840 --> 00:42:38,520
Тому ми хочемо, щоб перевірити, якщо
наш розмір більше 0, ОК?

787
00:42:38,520 --> 00:42:44,970
І якщо це так, то ми хочемо, щоб зменшити
наш розмір 0 і повернути це.

788
00:42:44,970 --> 00:42:45,840
Чому?

789
00:42:45,840 --> 00:42:49,950
>> У першому з них ми були
штовхаючи, ми висунули його

790
00:42:49,950 --> 00:42:52,460
на розмір і потім оновленої розміру.

791
00:42:52,460 --> 00:42:57,850
В цьому випадку, ми зменшуючи розмір
і то, приймаючи його, вищипування його

792
00:42:57,850 --> 00:42:58,952
з нашого масиву.

793
00:42:58,952 --> 00:42:59,826
Чому ми можемо це зробити?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Так що, якщо у мене є одна річ, на мій стек,
що б мій розмір на той момент?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> А де елемент 1 зберігається?

798
00:43:15,180 --> 00:43:17,621
На те, що індекс?

799
00:43:17,621 --> 00:43:18,120
АУДИТОРІЯ: 0.

800
00:43:18,120 --> 00:43:19,060
СПІКЕР 1: 0.

801
00:43:19,060 --> 00:43:22,800
Таким чином, в даному випадку, ми
завжди потрібно робити sure--

802
00:43:22,800 --> 00:43:27,630
замість того щоб повернутися
розмір мінус 1, тому що ми

803
00:43:27,630 --> 00:43:31,730
знаємо, що наш елемент
зберігатимуться на 1 менше

804
00:43:31,730 --> 00:43:34,705
все наш розмір, це
просто піклується про нього.

805
00:43:34,705 --> 00:43:36,080
Це трохи більш елегантний спосіб.

806
00:43:36,080 --> 00:43:41,220
І ми просто зменшити OUR
Розмір, а потім повернути розмір.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> Аудиторія: Я думаю, просто в цілому,
навіщо ця структура даних

809
00:43:45,300 --> 00:43:47,800
бути корисним?

810
00:43:47,800 --> 00:43:50,660
>> СПІКЕР 1: Це залежить від контексту.

811
00:43:50,660 --> 00:43:57,420
Таким чином, для деяких з теорії,
якщо ви працюєте with-- ОК,

812
00:43:57,420 --> 00:44:02,750
дайте мені подивитися, чи є вигідно один
що є корисним для більш, ніж зовні

813
00:44:02,750 --> 00:44:05,420
з CS.

814
00:44:05,420 --> 00:44:15,780
З стеків, в будь-який час вам потрібно
відслідковувати те, що

815
00:44:15,780 --> 00:44:20,456
є найбільш недавно доданого, коли
Ви збираєтеся хочете використовувати стек.

816
00:44:20,456 --> 00:44:24,770
>> І я не можу думати про хороше
приклад, що зараз.

817
00:44:24,770 --> 00:44:29,955
Але всякий раз, коли найостанніша
Справа в тому, найбільш важливі для вас,

818
00:44:29,955 --> 00:44:31,705
от коли стек
буде корисно.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Я намагаюся думати, якщо
є хороший варіантом.

821
00:44:39,330 --> 00:44:43,720
Якщо я думаю про хороше, наприклад, в наступному
20 хвилин, я, безумовно, скажу вам.

822
00:44:43,720 --> 00:44:49,455
>> Але в цілому, якщо є що-небудь,
як я сказав, що більшість, де остання

823
00:44:49,455 --> 00:44:52,470
найголовніше, що це
де стопка вступає в гру.

824
00:44:52,470 --> 00:44:58,860
Тоді як черги є свого роду протилежність.

825
00:44:58,860 --> 00:44:59,870
І всі маленькі собаки.

826
00:44:59,870 --> 00:45:00,890
Хіба це не здорово, чи не так?

827
00:45:00,890 --> 00:45:03,299
Я відчуваю, що повинен
просто є кролик відео

828
00:45:03,299 --> 00:45:05,090
прямо в середині
розділ для вас, хлопці

829
00:45:05,090 --> 00:45:08,870
бо це є інтенсивним розділ.

830
00:45:08,870 --> 00:45:10,480
>> Так черги.

831
00:45:10,480 --> 00:45:12,710
В основному черги як лінія.

832
00:45:12,710 --> 00:45:15,780
Ви, хлопці, я впевнений, що використання цього кожен день,
точно так само як в наших їдальнях.

833
00:45:15,780 --> 00:45:18,160
Таким чином, ми повинні піти в
і отримати в свої лотки, я

834
00:45:18,160 --> 00:45:21,260
що у вас є, щоб стояти в черзі
серветки або отримати вашу їжу.

835
00:45:21,260 --> 00:45:24,650
>> Таким чином, різниця тут
в тому, що це FIFO.

836
00:45:24,650 --> 00:45:30,090
Так що, якщо ЛІФО востаннє був в першу
поза, FIFO є першим прийшов, першим пішов.

837
00:45:30,090 --> 00:45:33,400
Так що це, де все, що ви поклали
на перший ваш найважливіший.

838
00:45:33,400 --> 00:45:35,540
Так що, якщо ви чекали
в line-- можу вас

839
00:45:35,540 --> 00:45:39,130
Уявіть собі, якщо ви пішли в
піти отримати новий iPhone

840
00:45:39,130 --> 00:45:42,800
і це був стек, де
остання людина в лінії отримав його першим,

841
00:45:42,800 --> 00:45:44,160
люди будуть вбивати один одного.

842
00:45:44,160 --> 00:45:49,800
>> Так FIFO, ми всі добре знайомі
с в реальному світі тут,

843
00:45:49,800 --> 00:45:54,930
і все це має відношення до дійсності
вид відтворення всю цю лінію

844
00:45:54,930 --> 00:45:56,900
і черг структуру.

845
00:45:56,900 --> 00:46:02,390
Так у той час як зі стеком,
у нас є поштовх і поп-музики.

846
00:46:02,390 --> 00:46:06,440
З чергу, ми маємо
поставити в чергу і видалення з черги.

847
00:46:06,440 --> 00:46:10,910
Так поставити в чергу в основному означає,
покласти його на спину,

848
00:46:10,910 --> 00:46:13,680
і виведення з коштів взяти
від с фронта.

849
00:46:13,680 --> 00:46:18,680
Таким чином, наша структура даних
трохи складніше.

850
00:46:18,680 --> 00:46:21,060
У нас є друге, для відстеження.

851
00:46:21,060 --> 00:46:25,950
>> Так що без голови, це
саме стек, чи не так?

852
00:46:25,950 --> 00:46:27,900
Це те ж саме будову, як стек.

853
00:46:27,900 --> 00:46:32,480
Єдина відмінність в даний час є у нас
Тобто ця голова, яка, що ви думаєте

854
00:46:32,480 --> 00:46:34,272
збирається відстежувати?

855
00:46:34,272 --> 00:46:35,510
>> АУДИТОРІЯ: Перший.

856
00:46:35,510 --> 00:46:38,685
>> СПІКЕР 1: праворуч,
Перше, що ми вкладаємо в.

857
00:46:38,685 --> 00:46:41,130
Глава нашої черги.

858
00:46:41,130 --> 00:46:42,240
Той, хто це перший в черзі.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Гаразд, так що якщо ми робимо в чергу.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Знову ж, з будь-яким з
ці структури даних,

863
00:46:55,920 --> 00:46:59,760
так як ми маємо справу з масивом,
ми повинні перевірити, якщо у нас є простір.

864
00:46:59,760 --> 00:47:03,290
>> Це ніби як мені розповідав
хлопці, якщо ви відкриваєте файл,

865
00:47:03,290 --> 00:47:04,760
Ви повинні перевірити на нуль.

866
00:47:04,760 --> 00:47:08,330
З будь-якої з цих стеків
і черги, вам потрібно

867
00:47:08,330 --> 00:47:13,420
щоб побачити, якщо є вільне місце, тому що ми
справу з масивом фіксованого розміру,

868
00:47:13,420 --> 00:47:16,030
як ми бачимо, here-- 0, 1 всього до 5.

869
00:47:16,030 --> 00:47:20,690
Так, що ми робимо в цьому випадку є перевірка
щоб побачити, якщо у нас ще є простір.

870
00:47:20,690 --> 00:47:23,110
Чи є наша розмір менше потужності?

871
00:47:23,110 --> 00:47:28,480
>> Якщо це так, ми повинні зберігати його в
хвіст, і ми оновимо наш розмір.

872
00:47:28,480 --> 00:47:30,250
Так що, можливо, хвіст буде в цьому випадку?

873
00:47:30,250 --> 00:47:32,360
Це явно не виписані.

874
00:47:32,360 --> 00:47:33,380
Як би ми зберігаємо це?

875
00:47:33,380 --> 00:47:34,928
Що б хвіст бути?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Так що давайте йти через цей приклад.

878
00:47:40,190 --> 00:47:44,590
Так що це масив розміром 6, чи не так?

879
00:47:44,590 --> 00:47:49,220
І у нас є зараз, наш розмір 5.

880
00:47:49,220 --> 00:47:55,240
І коли ми ставимо його в, він збирається
йти в п'ятому індексу, чи не так?

881
00:47:55,240 --> 00:47:57,030
Так зберігати в хвості.

882
00:47:57,030 --> 00:48:05,600
>> Ще один спосіб написати хвіст б просто
бути наш масив з індексом розміру, чи не так?

883
00:48:05,600 --> 00:48:07,560
Це розмір 5.

884
00:48:07,560 --> 00:48:11,490
Наступна річ, яку збирається піти в 5.

885
00:48:11,490 --> 00:48:12,296
Прохолодний?

886
00:48:12,296 --> 00:48:13,290
Добре.

887
00:48:13,290 --> 00:48:16,350
Це стає трохи складніше,
коли ми починаємо балуватися з головою.

888
00:48:16,350 --> 00:48:17,060
Да?

889
00:48:17,060 --> 00:48:20,090
>> АУДИТОРІЯ: Чи означає це, що ми
оголосив би масив,

890
00:48:20,090 --> 00:48:23,880
було давно п'ять елементів і
Потім ми додаємо на нього?

891
00:48:23,880 --> 00:48:24,730
>> СПІКЕР 1: Ні.

892
00:48:24,730 --> 00:48:27,560
Таким чином, в даному випадку, це стек.

893
00:48:27,560 --> 00:48:31,760
Це буде оголошений
у вигляді масиву розміром 6.

894
00:48:31,760 --> 00:48:37,120
І в цьому випадку ми
є тільки один космічний вліво.

895
00:48:37,120 --> 00:48:42,720
>> Отже, одна справа знаходиться в цьому
так, якщо наша голова на 0,

896
00:48:42,720 --> 00:48:45,270
Потім ми просто можете додати його в розмірах.

897
00:48:45,270 --> 00:48:51,020
Але це стає трохи складніше
бо насправді, вони

898
00:48:51,020 --> 00:48:52,840
немає слайд
для цього, так що я збираюся

899
00:48:52,840 --> 00:48:56,670
щоб зробити один, бо це не
так просто, як тільки ви

900
00:48:56,670 --> 00:48:59,230
почати позбавлення від речей.

901
00:48:59,230 --> 00:49:03,920
Так у той час як зі стеком
Ви тільки коли-небудь

902
00:49:03,920 --> 00:49:08,920
турбуватися про те, що розмір
коли ви додаєте щось на,

903
00:49:08,920 --> 00:49:15,710
з чергою ви також повинні переконатися,
Переконайтеся, що ваша голова доводилося,

904
00:49:15,710 --> 00:49:20,760
бо здорово, що про черги
є те, що, якщо ви не на повну потужність,

905
00:49:20,760 --> 00:49:23,040
ви можете зробити це обернути навколо.

906
00:49:23,040 --> 00:49:28,810
>> Отже, один thing-- о,
це жахливо крейда.

907
00:49:28,810 --> 00:49:31,815
Одна річ, щоб розглянути цю справу.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Ми просто робимо п'ять.

910
00:49:37,140 --> 00:49:41,810
Отже, ми збираємося
кажуть голова тут.

911
00:49:41,810 --> 00:49:46,140
Це означає 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Глава там, і
будь ласка, що в них.

913
00:49:54,210 --> 00:49:58,340
І ми хочемо, щоб додати щось в, чи не так?

914
00:49:58,340 --> 00:50:01,170
Так, що ми повинні
знаю, що голова завжди

915
00:50:01,170 --> 00:50:05,620
рухатиметься цим шляхом і
Потім цикл назад навколо, ОК?

916
00:50:05,620 --> 00:50:10,190
>> Так ця черга має місце, чи не так?

917
00:50:10,190 --> 00:50:13,950
У ньому є місце на самому початку,
вид протилежності це.

918
00:50:13,950 --> 00:50:17,920
Так що нам потрібно зробити, це ми
потрібно розрахувати хвіст.

919
00:50:17,920 --> 00:50:20,530
Якщо ви знаєте, що ваш
голова не переїхав, хвіст

920
00:50:20,530 --> 00:50:24,630
просто ваш масив в
Індекс розміру.

921
00:50:24,630 --> 00:50:30,000
>> Але насправді, якщо ви використовуєте чергу,
Ваша голова, ймовірно, оновлюється.

922
00:50:30,000 --> 00:50:33,890
Так що вам потрібно зробити, це
насправді обчислити хвіст.

923
00:50:33,890 --> 00:50:39,990
Так що ми робимо, це формула
тут, які я збираюся дати вам

924
00:50:39,990 --> 00:50:42,680
хлопці, думаєте про, і
тоді ми будемо говорити про це.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Так що це потужність.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Так що це буде насправді
дати вам спосіб зробити це.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Тому що в цьому випадку, то, що?

931
00:51:04,330 --> 00:51:09,205
Наша голова на 1, наш розмір 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Якщо ми мод, що на 5, отримуємо 0,
який є, де ми повинні ввести його.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Так то в наступному випадку,
якщо ми мали зробити це,

936
00:51:26,080 --> 00:51:33,390
ми говоримо, добре, давайте з черги щось.

937
00:51:33,390 --> 00:51:34,390
Ми з черги це.

938
00:51:34,390 --> 00:51:37,740
Виймаємо цей елемент, чи не так?

939
00:51:37,740 --> 00:51:47,930
>> І тепер наша голова вказуючи тут,
і ми хочемо додати в іншому.

940
00:51:47,930 --> 00:51:52,470
Це, в основному
назад від нашої лінії, чи не так?

941
00:51:52,470 --> 00:51:55,450
Черги можуть обернути навколо масиву.

942
00:51:55,450 --> 00:51:57,310
Це одна з основних відмінностей.

943
00:51:57,310 --> 00:51:58,780
Стопки, ви не можете зробити це.

944
00:51:58,780 --> 00:52:01,140
>> З чергами, ви можете
бо все, що має значення

945
00:52:01,140 --> 00:52:03,940
є те, що ви знаєте, що
зовсім недавно був доданий.

946
00:52:03,940 --> 00:52:10,650
Бо все буде додано до
цей напрямок вліво, в цьому випадку,

947
00:52:10,650 --> 00:52:16,480
а потім обернути навколо, ви можете
продовжити введення нових елементів

948
00:52:16,480 --> 00:52:18,830
в передній частині масиву
бо це не дійсно

949
00:52:18,830 --> 00:52:20,640
передня частина масиву більше.

950
00:52:20,640 --> 00:52:26,320
Ви можете думати про початок
Масив як де ваша голова насправді.

951
00:52:26,320 --> 00:52:29,710
>> Так ця формула, як
Ви розрахувати свій хвіст.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Чи означає це, має сенс?

954
00:52:35,610 --> 00:52:36,110
Добре.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
ОК, з черги, а потім
ви, хлопці, є 10 хвилин

957
00:52:44,040 --> 00:52:48,840
ставити мені будь уточнюючі питання
Ви хочете, бо я знаю, що це божевільний.

958
00:52:48,840 --> 00:52:51,980
>> Гаразд, так в тому ж way--
Я не знаю, якщо ви, хлопці помітили,

959
00:52:51,980 --> 00:52:53,450
але CS це все про візерунками.

960
00:52:53,450 --> 00:52:57,370
Речі досить багато
же, тільки з крихітними хитрувань.

961
00:52:57,370 --> 00:52:58,950
Так само і тут.

962
00:52:58,950 --> 00:53:04,040
Нам потрібно перевірити, щоб побачити, якщо ми насправді
є щось в нашій черзі, вірно?

963
00:53:04,040 --> 00:53:05,960
Скажімо, в порядку, наша розмір більше 0?

964
00:53:05,960 --> 00:53:06,730
Прохолодний.

965
00:53:06,730 --> 00:53:10,690
>> Якщо ми це зробимо, то ми перенесемо наше голову, яка
це те, що я тільки що продемонстрував тут.

966
00:53:10,690 --> 00:53:13,870
Ми оновлюємо нашу голову ще одна.

967
00:53:13,870 --> 00:53:18,390
А потім ми зменшуємо наші
Розмір і повертає елемент.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Існує набагато більше бетону
Код на study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
і я дуже рекомендую рух
через нього, якщо у вас є час,

971
00:53:29,440 --> 00:53:30,980
навіть якщо це всього лише псевдо-код.

972
00:53:30,980 --> 00:53:35,980
І якщо ви, хлопці, хочете поговорити через
що зі мною один на один, будь ласка, повідомте мені,

973
00:53:35,980 --> 00:53:37,500
знаю.

974
00:53:37,500 --> 00:53:38,770
Я був би щасливий.

975
00:53:38,770 --> 00:53:42,720
Структури даних, якщо
ви берете CS 124, ви будете

976
00:53:42,720 --> 00:53:47,830
знаю, що структури даних отримати дуже
весело і це тільки початок.

977
00:53:47,830 --> 00:53:50,350
>> Так що я знаю, це важко.

978
00:53:50,350 --> 00:53:51,300
Це нормально.

979
00:53:51,300 --> 00:53:52,410
Ми боремося.

980
00:53:52,410 --> 00:53:53,630
Я до сих пір.

981
00:53:53,630 --> 00:53:56,660
Отже не турбуйтеся про це занадто багато.

982
00:53:56,660 --> 00:54:02,390
>> Але це в основному програми Your
Crash Course в структурах даних.

983
00:54:02,390 --> 00:54:03,400
Я знаю, що це багато.

984
00:54:03,400 --> 00:54:06,860
Є що-небудь, що ми
хотів би піти знову?

985
00:54:06,860 --> 00:54:09,400
Все, що ми хочемо поговорити через?

986
00:54:09,400 --> 00:54:10,060
Да?

987
00:54:10,060 --> 00:54:16,525
>> АУДИТОРІЯ: Для цього, наприклад, так
новий хвіст на 0 над цим?

988
00:54:16,525 --> 00:54:17,150
СПІКЕР 1: Так.

989
00:54:17,150 --> 00:54:18,230
АУДИТОРІЯ: ОК.

990
00:54:18,230 --> 00:54:24,220
Отже переживає,
Ви повинні були б 1 плюс 4 ілі--

991
00:54:24,220 --> 00:54:27,671
>> СПІКЕР 1: Отже, ви говорили,
коли ми хочемо піти і зробити це знову?

992
00:54:27,671 --> 00:54:28,296
АУДИТОРІЯ: Так.

993
00:54:28,296 --> 00:54:38,290
Так що, якщо ви були з'ясувати out-- де
Ви розрахунку хвіст з в тому, що?

994
00:54:38,290 --> 00:54:44,260
>> СПІКЕР 1: Так хвіст
був in-- я змінив це.

995
00:54:44,260 --> 00:54:52,010
Таким чином, в цьому прикладі тут, це було
масив, ми дивимося на, ОК?

996
00:54:52,010 --> 00:54:54,670
Тому у нас є речі, в 1, 2, 3, і 4.

997
00:54:54,670 --> 00:55:05,850
Тому у нас є наша голова дорівнює 1 на
ця точка, і наш розмір дорівнює 4

998
00:55:05,850 --> 00:55:07,050
на даний момент, чи не так?

999
00:55:07,050 --> 00:55:08,960
>> Ви всі згодні, що це так?

1000
00:55:08,960 --> 00:55:14,620
Так ми робимо голову плюс розмір, який
дає нам 5, а потім ми мод на 5.

1001
00:55:14,620 --> 00:55:20,690
Ми отримуємо 0, яка говорить нам, що 0 є
де наша хвіст, де у нас є простір.

1002
00:55:20,690 --> 00:55:22,010
>> АУДИТОРІЯ: Що шапка?

1003
00:55:22,010 --> 00:55:23,520
>> СПІКЕР 1: Ємність.

1004
00:55:23,520 --> 00:55:24,020
Вибачте.

1005
00:55:24,020 --> 00:55:29,640
Так що це розмір вашого масиву.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Да?

1008
00:55:36,047 --> 00:55:39,210
>> АУДИТОРІЯ: [нерозбірливо], перш ніж
ми повертає елемент?

1009
00:55:39,210 --> 00:55:46,270
>> СПІКЕР 1: Так ми рухаємося
очолити або повернути час?

1010
00:55:46,270 --> 00:55:52,680
Так що, якщо ми перейдемо один, зменшити розмір?

1011
00:55:52,680 --> 00:55:54,150
Утримувати.

1012
00:55:54,150 --> 00:55:55,770
Я безумовно забув ще один.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Нічого.

1015
00:56:01,990 --> 00:56:04,980
Існує не одна формула.

1016
00:56:04,980 --> 00:56:09,980
Так, ви хотіли б, щоб повернутися
глава, а потім повернути його назад.

1017
00:56:09,980 --> 00:56:13,270
>> АУДИТОРІЯ: ОК, тому що в цей
Точка, голова була на 0,

1018
00:56:13,270 --> 00:56:18,452
а потім ви хочете, щоб повернутися
Індекс 0, а потім зробити головний 1?

1019
00:56:18,452 --> 00:56:19,870
>> СПІКЕР 1: Право.

1020
00:56:19,870 --> 00:56:22,820
Я думаю, що є ще один
Формула ніби як це.

1021
00:56:22,820 --> 00:56:26,970
У мене немає його на верхній голову, як
Я не хочу, щоб дати вам не той.

1022
00:56:26,970 --> 00:56:35,470
Але я думаю, що це цілком допустимо, щоб
скажімо, в порядку, зберігати цю element-- все

1023
00:56:35,470 --> 00:56:40,759
елемент голова is-- зменшити ваш
розмір, переміщати голову над, і повернення

1024
00:56:40,759 --> 00:56:41,800
все, що елемент.

1025
00:56:41,800 --> 00:56:44,760
Це абсолютно справедливо.

1026
00:56:44,760 --> 00:56:45,260
Добре.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Я відчуваю, що це не
як most-- ви не

1029
00:56:53,560 --> 00:56:55,740
збирається вийти звідси
як, да, я знаю спроб.

1030
00:56:55,740 --> 00:56:56,880
Я отримав все це.

1031
00:56:56,880 --> 00:56:57,670
Це добре.

1032
00:56:57,670 --> 00:57:00,200
Я обіцяю.

1033
00:57:00,200 --> 00:57:05,240
Але структури даних є чимось, що
вона займає багато часу, щоб звикнути.

1034
00:57:05,240 --> 00:57:10,010
Ймовірно, це один з найскладніших
речі, я думаю, що, в курсі.

1035
00:57:10,010 --> 00:57:15,330
>> Так що, безумовно, займає
Повторення і дивлячись at-- I

1036
00:57:15,330 --> 00:57:20,050
насправді не знаю, зв'язкові списки
поки я не зробив занадто багато з ними,

1037
00:57:20,050 --> 00:57:22,550
таким же чином, що не зробив
дійсно зрозуміти покажчики

1038
00:57:22,550 --> 00:57:27,040
поки у мене не було, щоб навчити його на двох
років і зробити свої власні psets з ним.

1039
00:57:27,040 --> 00:57:28,990
Це займає багато повторення і час.

1040
00:57:28,990 --> 00:57:32,600
І в кінці кінців, це буде свого роду натисніть.

1041
00:57:32,600 --> 00:57:36,320
>> Але в той же час, якщо у вас є вид
з глибокого знайомства з того, що

1042
00:57:36,320 --> 00:57:39,321
це зробити, їх плюси
і cons-- що і

1043
00:57:39,321 --> 00:57:41,820
ми дійсно, як правило, підкреслюють,
особливо в інтро звичайно.

1044
00:57:41,820 --> 00:57:45,511
Мовляв, навіщо нам використовувати
спробуйте над масивом?

1045
00:57:45,511 --> 00:57:48,010
Мовляв, те, що позитивні сторони
і негативи кожного з них?

1046
00:57:48,010 --> 00:57:51,610
>> І розуміння компромісів
між кожною з цих структур

1047
00:57:51,610 --> 00:57:54,910
є те, що набагато більш важливо зараз.

1048
00:57:54,910 --> 00:57:58,140
Там може бути один божевільний
Питання або два це

1049
00:57:58,140 --> 00:58:03,710
попрошу вас, щоб реалізувати поштовх або
здійснити поп або поставити в чергу і видалення з черги.

1050
00:58:03,710 --> 00:58:07,340
Але здебільшого, мають, що
вище розуміння рівня та більш

1051
00:58:07,340 --> 00:58:09,710
з інтуїтивне розуміння є
важливіше, ніж насправді

1052
00:58:09,710 --> 00:58:11,250
будучи в стані його реалізувати.

1053
00:58:11,250 --> 00:58:14,880
>> Це було б дійсно здорово, якщо ви все
могли вийти і піти реалізувати спробу,

1054
00:58:14,880 --> 00:58:19,720
але ми розуміємо, що це не обов'язково
найрозумніше зараз.

1055
00:58:19,720 --> 00:58:23,370
Але ви можете в PSET, якщо ви хочете
на, а потім ви отримаєте практику,

1056
00:58:23,370 --> 00:58:27,200
і тоді, можливо, ви будете
дійсно розумію.

1057
00:58:27,200 --> 00:58:27,940
Да?

1058
00:58:27,940 --> 00:58:30,440
>> АУДИТОРІЯ: ОК, так, які з них
ми хотіли використати в PSET?

1059
00:58:30,440 --> 00:58:31,916
Чи потрібно використовувати одну з них?

1060
00:58:31,916 --> 00:58:32,540
СПІКЕР 1: Так.

1061
00:58:32,540 --> 00:58:34,199
Так у вас є вибір.

1062
00:58:34,199 --> 00:58:36,740
Я думаю, в цьому випадку, ми можемо
говорити про PSET трохи

1063
00:58:36,740 --> 00:58:40,480
бо я пробіг ці.

1064
00:58:40,480 --> 00:58:47,779
Так що у вашому PSET, у вас є свій
Вибір спроб або хеш-таблиці.

1065
00:58:47,779 --> 00:58:49,570
Деякі люди будуть намагатися
і використовувати цвітіння фільтри,

1066
00:58:49,570 --> 00:58:51,840
але ті, технічно не правильно.

1067
00:58:51,840 --> 00:58:55,804
Через їх імовірнісний характер,
вони дають помилкові спрацьовування іноді.

1068
00:58:55,804 --> 00:58:57,095
Вони холодний погляд в, хоча.

1069
00:58:57,095 --> 00:58:59,030
Дуже рекомендую дивлячись
на них, принаймні.

1070
00:58:59,030 --> 00:59:03,260
Але у вас є вибір
між хеш-таблицю і спробувати.

1071
00:59:03,260 --> 00:59:06,660
І що буде, коли
Ви завантажуєте в словнику.

1072
00:59:06,660 --> 00:59:09,230
>> І ви повинні будете вибрати
Ваш хеш-функція,

1073
00:59:09,230 --> 00:59:13,420
Ви повинні будете вибрати, скільки
Відра у вас є, і вона буде змінюватися.

1074
00:59:13,420 --> 00:59:17,440
Як якщо у вас є більше відра,
може бути, він буде працювати швидше.

1075
00:59:17,440 --> 00:59:22,790
Але, можливо, ви даремно
багато місця, що шлях, хоча.

1076
00:59:22,790 --> 00:59:26,320
Ви повинні зрозуміти це.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> АУДИТОРІЯ: Ви говорили, що
ми можемо використовувати інші хеш-функцій,

1079
00:59:29,875 --> 00:59:31,750
що ми не повинні
створити хеш-функції?

1080
00:59:31,750 --> 00:59:32,666
>> СПІКЕР 1: Так, вірно.

1081
00:59:32,666 --> 00:59:38,150
Так буквально за хеш-функції,
Як і Google "хеш функція"

1082
00:59:38,150 --> 00:59:40,770
і шукати якісь нових і прикольних.

1083
00:59:40,770 --> 00:59:43,250
Ви не передбачається побудувати
Ваші власні хеш-функції.

1084
00:59:43,250 --> 00:59:46,100
Люди витрачають їх
тези про ці речі.

1085
00:59:46,100 --> 00:59:50,250
>> Отже не турбуйтеся про будівництво самостійно.

1086
00:59:50,250 --> 00:59:53,350
Знайти одне онлайн, щоб почати с.

1087
00:59:53,350 --> 00:59:56,120
Деякі з них ви повинні
маніпулювати трохи

1088
00:59:56,120 --> 00:59:59,430
щоб переконатися, що повертаються типи збігаються
і ще багато чого, так що на початку,

1089
00:59:59,430 --> 01:00:02,420
Я б рекомендував використовувати щось
дуже легко, що, може бути, просто

1090
01:00:02,420 --> 01:00:04,680
хеші по першій букві.

1091
01:00:04,680 --> 01:00:08,760
А потім, як тільки у вас є, що роботу,
включення кулер хеш-функції.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> АУДИТОРІЯ: б спробувати бути або
ефективним, але тільки складніше, like--

1094
01:00:13,020 --> 01:00:15,880
>> СПІКЕР 1: Так спробувати, я думаю,
Інтуїтивно важко реалізувати

1095
01:00:15,880 --> 01:00:18,310
але дуже швидко.

1096
01:00:18,310 --> 01:00:20,620
Проте, займає більше місця.

1097
01:00:20,620 --> 01:00:25,270
Знову ж таки, ви можете оптимізувати і тих, хто в
різні способи і є способи to--

1098
01:00:25,270 --> 01:00:26,770
АУДИТОРІЯ: Як ми оцінюються з цього приводу?

1099
01:00:26,770 --> 01:00:27,540
Чи означає це matter--

1100
01:00:27,540 --> 01:00:29,164
>> СПІКЕР 1: Отже, ви оцінюються звичайним способом.

1101
01:00:29,164 --> 01:00:31,330
Ви збираєтеся оцінюються по дизайну.

1102
01:00:31,330 --> 01:00:36,020
Який би шлях ви не робили, ви хочете, щоб
переконайтеся, що це так елегантно, як це може бути

1103
01:00:36,020 --> 01:00:38,610
і так ефективно, як це може бути.

1104
01:00:38,610 --> 01:00:41,950
Але якщо ви вибираєте спробу або хеш
Таблиця тих пір, поки він працює,

1105
01:00:41,950 --> 01:00:45,350
ми задоволені, що.

1106
01:00:45,350 --> 01:00:48,370
А якщо ви використовуєте щось, що хеші
по першій букві, це нормально,

1107
01:00:48,370 --> 01:00:51,410
як, можливо, як дизайн-мудрим.

1108
01:00:51,410 --> 01:00:53,410
Ми також досягнення
Точка в цьому semester--

1109
01:00:53,410 --> 01:00:55,340
Я не знаю, якщо ви
Хлопці noticed-- якщо ви

1110
01:00:55,340 --> 01:00:58,780
Pset сорти знижуватися трохи
через дизайн і ще багато чого,

1111
01:00:58,780 --> 01:00:59,900
це прекрасно.

1112
01:00:59,900 --> 01:01:02,960
Це стає в точку, де ваш
Програми стають все більш складними.

1113
01:01:02,960 --> 01:01:04,830
Є ще місця
Ви можете поліпшити.

1114
01:01:04,830 --> 01:01:06,370
>> Тож це цілком нормально.

1115
01:01:06,370 --> 01:01:08,810
Це не те, що ви
робить гірше на PSET.

1116
01:01:08,810 --> 01:01:11,885
Це просто ми бути сильніше на вас зараз.

1117
01:01:11,885 --> 01:01:13,732
Таким чином, кожен відчуває це.

1118
01:01:13,732 --> 01:01:14,940
Я просто оцінюються всі ваші psets.

1119
01:01:14,940 --> 01:01:16,490
Я знаю, що всі відчувають це.

1120
01:01:16,490 --> 01:01:19,600
>> Отже не турбуйтеся про це.

1121
01:01:19,600 --> 01:01:23,580
І якщо у вас є які-небудь питання
Попередні psets або способів, ви можете поліпшити,

1122
01:01:23,580 --> 01:01:27,760
Я намагаюся і коментувати конкретні
місця, але іноді це пізно

1123
01:01:27,760 --> 01:01:30,840
і я втомлююся.

1124
01:01:30,840 --> 01:01:34,885
Чи є інші речі
близько структури даних?

1125
01:01:34,885 --> 01:01:37,510
Я впевнений, що ви, хлопці, не дуже
хочу поговорити про них більше,

1126
01:01:37,510 --> 01:01:42,650
але якщо є, я щасливий
йти по ним, а також що-небудь

1127
01:01:42,650 --> 01:01:45,580
З лекції минулої
тиждень або на минулому тижні.

1128
01:01:45,580 --> 01:01:51,580
>> Я знаю, минулого тижня було все огляд, так
ми, можливо, пропустили протягом деякого перегляду

1129
01:01:51,580 --> 01:01:54,190
від лекції.

1130
01:01:54,190 --> 01:01:58,230
Будь-які інші питання я можу відповісти?

1131
01:01:58,230 --> 01:01:59,350
ОК, все в порядку.

1132
01:01:59,350 --> 01:02:02,400
Ну, ви, хлопці, виходьте 15 хвилин раніше.

1133
01:02:02,400 --> 01:02:08,370
>> Я сподіваюся, що це був напів-корисними, принаймні,
і я буду бачити вас, хлопці на наступному тижні,

1134
01:02:08,370 --> 01:02:12,150
або четвер робочі години.

1135
01:02:12,150 --> 01:02:15,285
Є просить для закусок
на наступному тижні, це-то й річ?

1136
01:02:15,285 --> 01:02:17,459
Тому що я забув цукерки сьогодні.

1137
01:02:17,459 --> 01:02:19,750
І я приніс цукерки останній
тиждень, але це був День Колумба,

1138
01:02:19,750 --> 01:02:25,400
таким чином, було як шість чоловік, які
було чотири мішки цукерок до себе.

1139
01:02:25,400 --> 01:02:28,820
Я можу привести Starbursts
знову, якщо вам подобається.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
Добре, добре звучить.

1142
01:02:32,250 --> 01:02:35,050
Майте великий день, хлопці.

1143
01:02:35,050 --> 01:02:39,510