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

2
00:00:11,860 --> 00:00:13,120
>> Виступаючий 1: Все в порядку, так що ми повернулися.

3
00:00:13,120 --> 00:00:14,480
Ласкаво просимо до CS50.

4
00:00:14,480 --> 00:00:16,510
Це кінець тижня сім.

5
00:00:16,510 --> 00:00:20,200
Тому нагадаємо, що минулого разу, ми почали
дивлячись на декілька більш складно

6
00:00:20,200 --> 00:00:21,100
структур даних.

7
00:00:21,100 --> 00:00:25,110
Так як досі, все, що ми були дійсно
У нашому розпорядженні було цього, масив.

8
00:00:25,110 --> 00:00:29,340
>> Але перш ніж відкинути масив що не
все, що цікаво, що це дійсно так

9
00:00:29,340 --> 00:00:33,570
насправді, те, що деякі з
Плюси цього простого даних

10
00:00:33,570 --> 00:00:34,560
структури досі?

11
00:00:34,560 --> 00:00:36,110
Яке це добре?

12
00:00:36,110 --> 00:00:39,450
До цих пір, як ми бачили?

13
00:00:39,450 --> 00:00:42,540
Що у тебе?

14
00:00:42,540 --> 00:00:44,028
Нічого.

15
00:00:44,028 --> 00:00:45,020
>> СТУДЕНТ: [нерозбірливо].

16
00:00:45,020 --> 00:00:45,395
>> Виступаючий 1: Що це?

17
00:00:45,395 --> 00:00:46,410
>> СТУДЕНТ: [нерозбірливо].

18
00:00:46,410 --> 00:00:47,000
>> Виступаючий 1: фіксований розмір.

19
00:00:47,000 --> 00:00:51,260
Отже, чому фіксований розмір хороший, хоча?

20
00:00:51,260 --> 00:00:53,180
>> СТУДЕНТ: [нерозбірливо].

21
00:00:53,180 --> 00:00:56,240
>> Виступаючий 1: Добре, так що це ефективно в
тому сенсі, що ви можете виділити

22
00:00:56,240 --> 00:01:00,070
Фіксована сума в просторі, який, ми сподіваємося,
Саме стільки

23
00:01:00,070 --> 00:01:01,180
простору, як ви хочете.

24
00:01:01,180 --> 00:01:02,720
Так що може бути абсолютно плюс.

25
00:01:02,720 --> 00:01:06,530
>> Що ще по одній стороні масиву?

26
00:01:06,530 --> 00:01:07,610
Так?

27
00:01:07,610 --> 00:01:08,750
>> СТУДЕНТ: [нерозбірливо].

28
00:01:08,750 --> 00:01:09,550
>> Виступаючий 1: Все - Пробачте?

29
00:01:09,550 --> 00:01:11,270
>> СТУДЕНТ: [нерозбірливо].

30
00:01:11,270 --> 00:01:13,620
>> Виступаючий 1: Всі коробки в пам'яті
або поруч один з одним.

31
00:01:13,620 --> 00:01:15,220
І це корисно - чому?

32
00:01:15,220 --> 00:01:15,970
Абсолютно вірно.

33
00:01:15,970 --> 00:01:18,611
Але як ми можемо використовувати це правда?

34
00:01:18,611 --> 00:01:21,500
>> СТУДЕНТ: [нерозбірливо].

35
00:01:21,500 --> 00:01:24,490
>> Виступаючий 1: Точно, ми можемо відстежувати
, Де все просто, знаючи,

36
00:01:24,490 --> 00:01:28,560
одна адреса, а саме, адреси
Перший байт, що блок пам'яті.

37
00:01:28,560 --> 00:01:30,420
Або у випадку рядки,
адресу першого

38
00:01:30,420 --> 00:01:31,460
символ в цьому рядку.

39
00:01:31,460 --> 00:01:33,330
А звідти, ми можемо знайти
кінця рядка.

40
00:01:33,330 --> 00:01:35,710
Ми можемо знайти другий елемент,
третій елемент, і так далі.

41
00:01:35,710 --> 00:01:38,740
>> І таким химерним способом опису, що
особливість в тому, що масиви дають нам

42
00:01:38,740 --> 00:01:40,020
довільним доступом.

43
00:01:40,020 --> 00:01:44,330
Просто за допомогою квадратних дужок
позначення і номери, ви можете перейти до

44
00:01:44,330 --> 00:01:48,070
конкретного елемента в масиві
за постійний час, Big O

45
00:01:48,070 --> 00:01:49,810
одного, так би мовити.

46
00:01:49,810 --> 00:01:51,080
>> Але є деякі мінуси.

47
00:01:51,080 --> 00:01:53,110
Що масив не робити дуже легко?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Що це не дуже добре?

50
00:01:57,170 --> 00:01:58,810
>> СТУДЕНТ: [нерозбірливо].

51
00:01:58,810 --> 00:01:59,860
>> Виступаючий 1: Що це?

52
00:01:59,860 --> 00:02:00,530
>> СТУДЕНТ: [нерозбірливо].

53
00:02:00,530 --> 00:02:01,460
>> Виступаючий 1: Розширення в розмірах.

54
00:02:01,460 --> 00:02:04,800
Таким чином, недоліки масиву
точно протилежне тому, що

55
00:02:04,800 --> 00:02:05,540
розквитатися є.

56
00:02:05,540 --> 00:02:07,610
Тому одним з недоліків є
що це фіксований розмір.

57
00:02:07,610 --> 00:02:09,400
Таким чином, ви не можете реально виростити його.

58
00:02:09,400 --> 00:02:13,510
Ви можете перерозподілити більший шматок
пам'яті, а потім перемістіть старий елементи

59
00:02:13,510 --> 00:02:14,460
в новий масив.

60
00:02:14,460 --> 00:02:18,060
, А потім звільнити старого масиву, для
Наприклад, при використанні Танос або аналогічного

61
00:02:18,060 --> 00:02:21,180
Функція називається Realloc, яка
перерозподіляє пам'ять.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, як у бік, намагається дати вам
пам'яті, що це поруч з масивом

63
00:02:25,490 --> 00:02:26,610
що ви вже маєте.

64
00:02:26,610 --> 00:02:28,740
Але це може переміщати предмети
навколо в цілому.

65
00:02:28,740 --> 00:02:30,710
Але загалом, що дорого, чи не так?

66
00:02:30,710 --> 00:02:33,440
Тому що, якщо у вас є шматок пам'яті
такого розміру, але ви дійсно хочете один

67
00:02:33,440 --> 00:02:36,710
такого розміру, і ви хочете зберегти
оригінальні елементи, у вас є

68
00:02:36,710 --> 00:02:40,510
приблизно лінійний процес копіювання час
що має статися від

69
00:02:40,510 --> 00:02:41,900
старого масиву на новий.

70
00:02:41,900 --> 00:02:44,630
А реальність така просять операційної
Система знову і знову і

71
00:02:44,630 --> 00:02:48,340
знову на великі шматки пам'яті може початися
коштувати вам деякий час, а також.

72
00:02:48,340 --> 00:02:52,250
Так що це як благословення і прокляття в
замаскувати той факт, що ці масиви

73
00:02:52,250 --> 00:02:53,860
мають фіксований розмір.

74
00:02:53,860 --> 00:02:56,790
Але якщо ввести замість щось
як це, яке ми назвали пов'язаного

75
00:02:56,790 --> 00:03:00,580
список, ми отримуємо кілька плюси і
кілька недоліків і тут.

76
00:03:00,580 --> 00:03:05,780
>> Так зв'язаний список просто дані
структура, що складається зі структур C в цьому

77
00:03:05,780 --> 00:03:09,850
випадку, коли структура, нагадаємо, є просто
контейнер для одного або більше конкретних

78
00:03:09,850 --> 00:03:11,100
типи змінних.

79
00:03:11,100 --> 00:03:16,110
У цьому випадку, що ж типи даних
Мабуть, всередині структури, який

80
00:03:16,110 --> 00:03:17,600
Останній раз ми називається вузлом?

81
00:03:17,600 --> 00:03:19,380
Кожен з цих прямокутників вузла.

82
00:03:19,380 --> 00:03:22,660
І кожен з менших прямокутників
Всередині це тип даних.

83
00:03:22,660 --> 00:03:25,300
Які ж тоді ми говорили
вони були в понеділок?

84
00:03:25,300 --> 00:03:26,478
Так?

85
00:03:26,478 --> 00:03:27,870
>> СТУДЕНТ: [нерозбірливо].

86
00:03:27,870 --> 00:03:30,721
>> Виступаючий 1: змінні і покажчик, або
точніше, ціле для N,

87
00:03:30,721 --> 00:03:32,180
і покажчик на дні.

88
00:03:32,180 --> 00:03:35,360
Обидва ці, виявляється, 32 біта, по крайней
міру на комп'ютері, як це CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, і тому вони
звертається однаково в розмірі.

90
00:03:37,980 --> 00:03:42,260
>> Так що з допомогою покажчика
хоча для мабуть?

91
00:03:42,260 --> 00:03:47,690
Навіщо додавати цю стрілку тепер, коли масиви, були
так добре і чисто і просто?

92
00:03:47,690 --> 00:03:50,460
Що робите для покажчика
нами в кожному з цих вузлів?

93
00:03:50,460 --> 00:03:52,160
>> СТУДЕНТ: [нерозбірливо].

94
00:03:52,160 --> 00:03:52,465
>> Виступаючий 1: Абсолютно вірно.

95
00:03:52,465 --> 00:03:54,120
Це вам каже, де
далі йде.

96
00:03:54,120 --> 00:03:57,350
Так що я, звичайно, використовувати аналогію
використанням потоку до виду

97
00:03:57,350 --> 00:03:59,180
нитка ці вузли разом.

98
00:03:59,180 --> 00:04:01,760
І це саме те, що ми робимо з
покажчиків, оскільки кожен з цих

99
00:04:01,760 --> 00:04:06,360
ділянок пам'яті може або не може бути
суміжні, спина до спини до спини

100
00:04:06,360 --> 00:04:09,500
всередині оперативної пам'яті, тому що кожного разу, коли ви
зателефонуйте Malloc кажуть: дай мені достатньо

101
00:04:09,500 --> 00:04:12,510
байтів для нового вузла, він може
бути тут, або він може бути тут.

102
00:04:12,510 --> 00:04:13,120
Це могло б бути тут.

103
00:04:13,120 --> 00:04:13,730
Це могло б бути тут.

104
00:04:13,730 --> 00:04:14,640
Ви просто не знаю.

105
00:04:14,640 --> 00:04:17,880
>> Але за допомогою покажчиків в адресах
ці вузли, ви можете зшити їх

106
00:04:17,880 --> 00:04:22,370
разом таким чином, що візуально виглядає
як список, навіть якщо ці речі

107
00:04:22,370 --> 00:04:26,770
всі поширені протягом всього одного або
Ваші два або ваші чотири гігабайти оперативної пам'яті

108
00:04:26,770 --> 00:04:28,760
всередині вашого власного комп'ютера.

109
00:04:28,760 --> 00:04:33,230
>> Таким чином, недолік, то,
Зв'язаний список є що?

110
00:04:33,230 --> 00:04:34,670
Що таке ціна, що ми
мабуть платити?

111
00:04:34,670 --> 00:04:36,010
>> СТУДЕНТ: [нерозбірливо].

112
00:04:36,010 --> 00:04:36,920
>> Виступаючий 1: Більше місця, чи не так?

113
00:04:36,920 --> 00:04:39,340
Ми, в даному випадку, подвоїв суму
простору, тому що ми пройшли

114
00:04:39,340 --> 00:04:43,500
з 32 біт для кожного вузла, для кожного
Інтелект, так що тепер 64 біта, тому що ми повинні

115
00:04:43,500 --> 00:04:45,050
тримати навколо покажчика, а також.

116
00:04:45,050 --> 00:04:48,860
Ви отримуєте більше ефективності, якщо вашої структури
більше, ніж ця проста річ.

117
00:04:48,860 --> 00:04:52,020
Якщо у вас дійсно є всередині студента
з яких представляє собою пару рядків для

118
00:04:52,020 --> 00:04:55,430
ім'я і будинок, може бути, номер посвідчення особи,
можливо, деякі інші області в цілому.

119
00:04:55,430 --> 00:04:59,000
>> Так що якщо у вас є достатньо велика структура,
то, можливо, вартість покажчик

120
00:04:59,000 --> 00:05:00,010
Чи не така вже велика справа.

121
00:05:00,010 --> 00:05:03,570
Це трохи з кутка в цьому випадку
ми зберігаємо такі прості примітивні

122
00:05:03,570 --> 00:05:04,760
всередину пов'язаного списку.

123
00:05:04,760 --> 00:05:05,790
Але суть та ж.

124
00:05:05,790 --> 00:05:08,230
Ви безумовно витрачати більше
пам'яті, але ви отримуєте

125
00:05:08,230 --> 00:05:08,990
гнучкість.

126
00:05:08,990 --> 00:05:12,280
Тому що тепер, якщо я хочу додати елемент
На початку цього списку,

127
00:05:12,280 --> 00:05:14,340
Я повинен виділити новий вузол.

128
00:05:14,340 --> 00:05:17,180
І я повинен просто оновити ці
Стрілки якось просто переміщення

129
00:05:17,180 --> 00:05:17,980
деякі покажчики навколо.

130
00:05:17,980 --> 00:05:20,580
>> Якщо я хочу, щоб вставити щось у
середині списку, я не доведеться

131
00:05:20,580 --> 00:05:24,410
штовхати в бік все, що ми зробили в
тижнів минуле з нашим добровольцям, які

132
00:05:24,410 --> 00:05:25,700
представлена ​​масивом.

133
00:05:25,700 --> 00:05:29,470
Я можу просто виділити новий вузол і
Потім просто вказати стрілками на

134
00:05:29,470 --> 00:05:32,290
різних напрямках, оскільки вона не
повинні залишатися у фактичному

135
00:05:32,290 --> 00:05:35,670
пам'яті істинних лінії, як я намалював
його тут на екрані.

136
00:05:35,670 --> 00:05:38,400
>> А потім, нарешті, якщо ви хочете вставити
то в кінці списку, це

137
00:05:38,400 --> 00:05:39,210
ще простіше.

138
00:05:39,210 --> 00:05:43,320
Це свого роду довільні позначення,
але в 34 покажчиків, зробити припущення.

139
00:05:43,320 --> 00:05:46,710
Що таке значення його покажчика найбільш
ймовірно, звертається ніби як старі

140
00:05:46,710 --> 00:05:47,700
школі є антенна?

141
00:05:47,700 --> 00:05:48,920
>> СТУДЕНТ: [нерозбірливо].

142
00:05:48,920 --> 00:05:49,900
>> Виступаючий 1: Це, ймовірно, нульовим.

143
00:05:49,900 --> 00:05:52,710
І справді, що є одним учасника
подання нульовий.

144
00:05:52,710 --> 00:05:56,310
І це нуль, тому що ви абсолютно
потрібно знати, де до кінця пов'язаного

145
00:05:56,310 --> 00:06:00,050
список, щоб ви продовжуєте після і
після і після цих стрілок

146
00:06:00,050 --> 00:06:01,170
деяким сміттям значення.

147
00:06:01,170 --> 00:06:06,230
Так нульових не означатиме, що немає ніякої
більш вузлів праворуч від числа 34,

148
00:06:06,230 --> 00:06:07,200
в цьому випадку.

149
00:06:07,200 --> 00:06:10,270
>> Тому ми вважаємо, що ми можемо реалізувати
цей вузол в коді.

150
00:06:10,270 --> 00:06:12,130
І ми бачили таку
синтаксису раніше.

151
00:06:12,130 --> 00:06:15,090
Typedef просто визначає новий тип для
нас, дає нам як синонім

152
00:06:15,090 --> 00:06:17,100
Рядок була для символ *.

153
00:06:17,100 --> 00:06:21,030
У цьому випадку, він збирається дати нам
скорочений запис, так що структура вузла

154
00:06:21,030 --> 00:06:24,010
Натомість можна просто бути записана у вигляді
вузол, який є набагато більш чистою.

155
00:06:24,010 --> 00:06:25,360
Це набагато менш багатослівним.

156
00:06:25,360 --> 00:06:30,080
>> Усередині вузла мабуть Цілочисельне
називається п, а потім структури вузла *

157
00:06:30,080 --> 00:06:34,670
що означає саме те, що ми хотіли
Стрілки на увазі, покажчик на інший

158
00:06:34,670 --> 00:06:36,940
вузол точно такий же тип даних.

159
00:06:36,940 --> 00:06:40,300
І я пропоную, щоб ми могли реалізувати
Функція пошуку, як це, яке в

160
00:06:40,300 --> 00:06:41,890
перший погляд може здатися,
трохи складним.

161
00:06:41,890 --> 00:06:43,330
Але давайте подивимося його в контексті.

162
00:06:43,330 --> 00:06:45,480
>> Дозвольте мені перейти до приладу тут.

163
00:06:45,480 --> 00:06:48,460
Дозвольте мені відкрити файл з ім'ям
Список нулю точка ч.

164
00:06:48,460 --> 00:06:53,950
І що тільки містить визначення ми
тільки що бачили хвилину тому для цих даних

165
00:06:53,950 --> 00:06:55,390
тип називається вузлом.

166
00:06:55,390 --> 00:06:57,350
Тому ми ввели, що у файл точка ч.

167
00:06:57,350 --> 00:07:01,430
>> І, як осторонь, хоча це
програма, яку ви збираєтеся, щоб побачити це

168
00:07:01,430 --> 00:07:05,410
не все, що комплекс, це дійсно
Конвенції при написанні програми

169
00:07:05,410 --> 00:07:10,270
покласти речі, як типи даних, тягнути
Константи іноді, всередині вашого

170
00:07:10,270 --> 00:07:13,210
заголовок файлу, а не обов'язково в
З вашого файлу, звичайно ж, коли ваш

171
00:07:13,210 --> 00:07:17,370
програм отримати більше і більше, так що
Ви знаєте, де шукати, як для

172
00:07:17,370 --> 00:07:20,840
документації в деяких випадках або
для основи, як це,

173
00:07:20,840 --> 00:07:22,360
визначення деякого типу.

174
00:07:22,360 --> 00:07:25,680
>> Якби я зараз відкрити список нулю точка
C, помітити кілька речей.

175
00:07:25,680 --> 00:07:29,090
Вона включає в себе кілька файлів заголовка, більшість
якого ми бачили раніше.

176
00:07:29,090 --> 00:07:31,980
Вона включає в себе свій власний файл заголовка.

177
00:07:31,980 --> 00:07:35,200
>> І, як осторонь, чому це подвійна
котирування тут, в відміну від кута

178
00:07:35,200 --> 00:07:38,340
кронштейни на лінії, яка
Я виділив там?

179
00:07:38,340 --> 00:07:39,180
>> СТУДЕНТ: [нерозбірливо].

180
00:07:39,180 --> 00:07:40,460
>> Виступаючий 1: Так, так що це локальний файл.

181
00:07:40,460 --> 00:07:44,300
Так що, якщо це локальний файл власного тут
на лінії 15, наприклад, ви використовуєте

182
00:07:44,300 --> 00:07:46,570
подвійні лапки замість
в кутові дужки.

183
00:07:46,570 --> 00:07:48,270
>> Тепер це частково цікаво.

184
00:07:48,270 --> 00:07:51,830
Зверніть увагу, що я оголосив глобальну
змінної в цій програмі в рядку 18

185
00:07:51,830 --> 00:07:55,910
називається першою, ідея в тому, що це
буде покажчик на перший

186
00:07:55,910 --> 00:07:59,190
вузол в моєму зв'язаний список, а я
ініціалізувати його до нуля, тому, що я

187
00:07:59,190 --> 00:08:02,310
не виділяється яких фактичних
вузли тільки поки.

188
00:08:02,310 --> 00:08:07,570
>> Так що це представляє, графічно, те, що ми
побачив хвилину тому на зображенні як

189
00:08:07,570 --> 00:08:10,090
що покажчик на Далекому
з лівого боку.

190
00:08:10,090 --> 00:08:12,260
Так що зараз, що покажчик
не має стрілки.

191
00:08:12,260 --> 00:08:14,590
Замість цього він просто нульовий.

192
00:08:14,590 --> 00:08:17,880
Але він представляє, якою буде
адресу першого фактичного

193
00:08:17,880 --> 00:08:19,480
вузла в цьому списку.

194
00:08:19,480 --> 00:08:22,120
Так я реалізував це глобальна
тому що, як ви побачите, все це

195
00:08:22,120 --> 00:08:25,310
Програма робить у житті, це реалізувати
зв'язаний список для мене.

196
00:08:25,310 --> 00:08:27,050
>> Тепер у мене є кілька прототипів тут.

197
00:08:27,050 --> 00:08:31,190
Я вирішив реалізувати функції, такі як
делеции, вставки, пошуку та

198
00:08:31,190 --> 00:08:31,740
обходу -

199
00:08:31,740 --> 00:08:35,210
Останній просто бути прогулянка через
Список, роздрукувавши її елементів.

200
00:08:35,210 --> 00:08:36,750
А тепер ось мій основній програмі.

201
00:08:36,750 --> 00:08:39,890
І ми не будемо витрачати надто багато часу на
це, так як це є свого роду, ми сподіваємося,

202
00:08:39,890 --> 00:08:41,780
стара капелюх до теперішнього часу.

203
00:08:41,780 --> 00:08:45,370
>> Я збираюся зробити наступне,
в той час як користувач взаємодіє.

204
00:08:45,370 --> 00:08:47,300
Так що, я збираюся друкувати
з цього меню.

205
00:08:47,300 --> 00:08:49,420
І я відформатував його в якості
чисто, як я міг.

206
00:08:49,420 --> 00:08:52,240
Якщо користувач вводить в одному, тобто
вони хочуть, щоб видалити що-небудь.

207
00:08:52,240 --> 00:08:54,560
Якщо користувач введе в двох, це означає, що
вони хочуть, щоб вставити щось.

208
00:08:54,560 --> 00:08:55,930
І так далі.

209
00:08:55,930 --> 00:08:58,270
Я збираюся потім підкажуть
Тоді для команди.

210
00:08:58,270 --> 00:08:59,300
А потім я збираюся використовувати GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Так що це дійсно просто menuing
інтерфейс, де ви просто повинні ввести

212
00:09:02,790 --> 00:09:05,270
число відображення одного
з цих команд.

213
00:09:05,270 --> 00:09:08,730
І тепер у мене є хороша чиста перемикач
заяву, що збирається включити

214
00:09:08,730 --> 00:09:10,090
будь-який користувач ввели дюйма

215
00:09:10,090 --> 00:09:12,180
І якщо вони набрали одне, я буду
виклику видалення і ламатися.

216
00:09:12,180 --> 00:09:14,380
Якщо вони ввели два, я буду
зателефонуйте вставити і ламатися.

217
00:09:14,380 --> 00:09:16,490
>> А тепер зверніть увагу я помістив кожного
з них на тій же лінії.

218
00:09:16,490 --> 00:09:18,360
Це всього лише стилістичне рішення.

219
00:09:18,360 --> 00:09:20,210
Зазвичай ми бачили щось
як це.

220
00:09:20,210 --> 00:09:23,260
Але я просто вирішив, чесно кажучи, моя програма
виглядав більш для читання, так

221
00:09:23,260 --> 00:09:25,980
це було тільки чотири випадки
просто перерахувати це так.

222
00:09:25,980 --> 00:09:28,360
Повністю законне використання стилю.

223
00:09:28,360 --> 00:09:31,480
І я буду робити це так довго, як
Користувач не набрала нулю, що я

224
00:09:31,480 --> 00:09:33,910
вирішено означатиме, що вони хочуть кинути палити.

225
00:09:33,910 --> 00:09:36,630
>> Так що тепер помічаю, що я
робитимемо тут.

226
00:09:36,630 --> 00:09:38,650
Я збираюся звільнити списку мабуть.

227
00:09:38,650 --> 00:09:40,230
Але про це через хвилину.

228
00:09:40,230 --> 00:09:41,640
Давайте спочатку запустити цю програму.

229
00:09:41,640 --> 00:09:45,250
Отже, дозвольте мені зробити більший термінал
вікна, точка слеш список 0.

230
00:09:45,250 --> 00:09:49,510
Я збираюся йти вперед і вставляйте їх
набравши два, як число 50, а тепер

231
00:09:49,510 --> 00:09:51,590
Ви побачите список тепер на 50.

232
00:09:51,590 --> 00:09:53,380
І мій текст, просто прокручується небагато.

233
00:09:53,380 --> 00:09:55,940
Так що тепер Зверніть увагу на список містить
число 50.

234
00:09:55,940 --> 00:09:58,220
>> Давайте ще вставкою, взявши два.

235
00:09:58,220 --> 00:10:01,630
Давайте введіть номер, як один.

236
00:10:01,630 --> 00:10:03,940
Список є однією, а потім 50.

237
00:10:03,940 --> 00:10:06,020
Так що це просто текстове представлення
списку.

238
00:10:06,020 --> 00:10:10,550
І давайте вставимо ще один номер, як
номер 42, який з надією

239
00:10:10,550 --> 00:10:14,620
буде в кінцевому підсумку в середині, тому що
цієї програми, зокрема, сортує його

240
00:10:14,620 --> 00:10:16,320
елементи, як він вставляє їх.

241
00:10:16,320 --> 00:10:17,220
Так що у нас це є.

242
00:10:17,220 --> 00:10:20,730
Супер просто програму, яка може
Абсолютно використовували безліч, але я

243
00:10:20,730 --> 00:10:23,280
, Трапляється, використовують зв'язаний список
саме так я можу динамічно

244
00:10:23,280 --> 00:10:24,610
збільшуються і зменшуються його.

245
00:10:24,610 --> 00:10:28,470
>> Отже, давайте поглянемо на пошуки, якщо я
запустити команду три, я хочу пошуку

246
00:10:28,470 --> 00:10:31,040
, Скажімо, числа 43.

247
00:10:31,040 --> 00:10:34,190
І нічого не було знайдено мабуть,
тому що я не повернувся без відповіді.

248
00:10:34,190 --> 00:10:35,010
Отже, давайте зробимо це знову.

249
00:10:35,010 --> 00:10:35,690
Пошук.

250
00:10:35,690 --> 00:10:39,520
Давайте шукати для 50, або, скоріше, пошук
для 42, у якого є гарна

251
00:10:39,520 --> 00:10:40,850
майже невловима зміст.

252
00:10:40,850 --> 00:10:42,610
І я знайшов сенс життя там.

253
00:10:42,610 --> 00:10:44,990
Число 42, якщо ви не знаєте,
посилання Пошук в Інтернеті.

254
00:10:44,990 --> 00:10:45,350
Добре.

255
00:10:45,350 --> 00:10:47,130
Так, що ця програма для мене зробив?

256
00:10:47,130 --> 00:10:50,660
Це просто дозволив мені вставити таким чином,
далеко і пошук елементів.

257
00:10:50,660 --> 00:10:53,650
>> Давай вперед, то, щоб
функції, ми глянув на

258
00:10:53,650 --> 00:10:55,360
в понеділок, як дразнилка.

259
00:10:55,360 --> 00:10:59,620
Так що ця функція, я стверджую, шукає
елемента в списку по перших

260
00:10:59,620 --> 00:11:03,830
одна, пропонуючи користувачеві з наступним викликом
GetInt, щоб отримати фактичні десяткового

261
00:11:03,830 --> 00:11:05,060
що ви хочете знайти.

262
00:11:05,060 --> 00:11:06,460
>> Потім помітив цього.

263
00:11:06,460 --> 00:11:10,690
Я збираюся створити тимчасову змінну
У лінії 188 називається покажчиком -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
міг би назвати її як завгодно.

266
00:11:12,440 --> 00:11:16,140
І це вказівник на вузлі
бо Я сказав вузла * там.

267
00:11:16,140 --> 00:11:19,900
І я ініціалізації рівним
перший, так що я ефективно моє

268
00:11:19,900 --> 00:11:22,860
пальця, так би мовити, на самому
Перший елемент списку.

269
00:11:22,860 --> 00:11:27,460
Так що, якщо моя права рука тут PTR Я
вказуючи на те ж саме, що перший

270
00:11:27,460 --> 00:11:28,670
вказує на.

271
00:11:28,670 --> 00:11:31,430
>> Так що тепер ще в коді,
що буде далі -

272
00:11:31,430 --> 00:11:35,070
це загальна парадигма при переборі
за структурою, як

273
00:11:35,070 --> 00:11:35,970
зв'язаний список.

274
00:11:35,970 --> 00:11:40,410
Я збираюся зробити наступне в той час як
покажчик не дорівнює нулю Таким чином, хоча

275
00:11:40,410 --> 00:11:47,530
мій палець не вказує на деякі нульовим
вартості, якщо стрілка покажчика N дорівнює N.

276
00:11:47,530 --> 00:11:52,290
Ми помітили, що перші N є те, що
користувач вводить в GetInts називаю тут.

277
00:11:52,290 --> 00:11:54,280
>> І стрілка покажчика N означає, що?

278
00:11:54,280 --> 00:11:59,020
Ну, якщо ми повернемося до картини тут,
чи є у мене пальцем, вказуючи на

279
00:11:59,020 --> 00:12:02,960
що перший вузол, що містить дев'ять,
стрілки по суті означає, що перейти до

280
00:12:02,960 --> 00:12:08,860
вузла і захопити значення в точці N,
У цьому випадку, поле даних називається н.

281
00:12:08,860 --> 00:12:14,120
>> Як у бік - і ми побачили цю пару
тижнів тому, коли хтось запитав -

282
00:12:14,120 --> 00:12:18,840
цей синтаксис є новою, але це не так
дати нам сили, які ми

283
00:12:18,840 --> 00:12:20,040
вже не було.

284
00:12:20,040 --> 00:12:25,325
Що це за фраза еквівалентно використанню
точкової нотації і зірка пара

285
00:12:25,325 --> 00:12:29,490
тижнів тому, коли ми очищені тому
ця верства трохи передчасно?

286
00:12:29,490 --> 00:12:31,780
>> СТУДЕНТ: [нерозбірливо].

287
00:12:31,780 --> 00:12:38,880
>> Виступаючий 1: Точно, це була зірка, і
тоді це була зірка точкою N, з

288
00:12:38,880 --> 00:12:41,930
Тут дужки, який виглядає,
чесно кажучи, я думаю, що багато

289
00:12:41,930 --> 00:12:43,320
більш загадкові читати.

290
00:12:43,320 --> 00:12:46,270
Але покажчик зірки, як завжди,
кошти йдуть туди.

291
00:12:46,270 --> 00:12:49,090
І як тільки ви там, які дані
поля ви хочете отримати доступ?

292
00:12:49,090 --> 00:12:52,730
Ну ви використовують точку доступу до
поля структур даних, і я

293
00:12:52,730 --> 00:12:54,140
спеціально хочуть н.

294
00:12:54,140 --> 00:12:56,240
>> Чесно кажучи, я б сказав, це
просто важко читати.

295
00:12:56,240 --> 00:12:58,080
Це складніше пригадати, де
зробити дужках йти,

296
00:12:58,080 --> 00:12:59,030
зірка і все таке.

297
00:12:59,030 --> 00:13:02,150
Таким чином, світ прийняв деякі синтаксичні
цукор, так би мовити.

298
00:13:02,150 --> 00:13:04,740
Просто сексуально спосіб сказати,
це еквівалентно, а також

299
00:13:04,740 --> 00:13:05,970
можливо, більш інтуїтивним.

300
00:13:05,970 --> 00:13:09,600
Якщо покажчик дійсно є покажчиком,
коштів стрілки позначення піти туди і знайти

301
00:13:09,600 --> 00:13:11,890
поля в цьому випадку називаються N.

302
00:13:11,890 --> 00:13:13,660
>> Так що, якщо я знаходжу це, зауважте, що я роблю.

303
00:13:13,660 --> 00:13:17,430
Я просто роздрукувати, я виявив, я відсотків,
підключення значення для цього Int.

304
00:13:17,430 --> 00:13:20,730
Я називаю спати протягом однієї секунди просто вид
паузи речі на екрані, щоб

305
00:13:20,730 --> 00:13:22,900
дати користувачеві другий поглинати
що тільки що відбулося.

306
00:13:22,900 --> 00:13:24,290
І тоді я порушу.

307
00:13:24,290 --> 00:13:26,330
В іншому випадку, що мені робити?

308
00:13:26,330 --> 00:13:30,960
Оновити покажчик на рівних
покажчика стрілки поруч.

309
00:13:30,960 --> 00:13:35,840
>> Так що просто щоб бути ясним, це означає піти
там, за допомогою моєї старої школи позначень.

310
00:13:35,840 --> 00:13:39,580
Так що це просто означає, йти до того, що
Ви вказуєте на, який на самому

311
00:13:39,580 --> 00:13:43,660
Перший випадок я вказуючи на
Структура з дев'ятьма в ньому.

312
00:13:43,660 --> 00:13:44,510
Так що я пішов туди.

313
00:13:44,510 --> 00:13:47,880
І тоді точкової нотації означає,
отримати значення в наступному.

314
00:13:47,880 --> 00:13:50,470
>> Але цінність, хоча він малюється
як вузькі, просто номер.

315
00:13:50,470 --> 00:13:51,720
Це адреса в числовий.

316
00:13:51,720 --> 00:13:55,670
Так що це один рядок коду, будь то
написано, як це, більш прихованому

317
00:13:55,670 --> 00:14:00,190
шляху, або, як це, кілька більш
інтуїтивно зрозумілим способом, просто означає, поворушити рукою

318
00:14:00,190 --> 00:14:03,460
від першого вузла до наступного,
а потім наступний, а потім

319
00:14:03,460 --> 00:14:05,320
наступної, і так далі.

320
00:14:05,320 --> 00:14:09,920
>> Таким чином, ми не будемо зупинятися на інших
реалізацій вставляти і видаляти

321
00:14:09,920 --> 00:14:14,030
і обходу, перші два з
які є достатньо складною.

322
00:14:14,030 --> 00:14:17,010
І я думаю, що це досить легко отримати
втратив, коли роблять це в усній формі.

323
00:14:17,010 --> 00:14:19,890
Але що ми можемо зробити тут
Спробуйте визначити, як

324
00:14:19,890 --> 00:14:21,640
Краще робити це візуально.

325
00:14:21,640 --> 00:14:24,800
Тому що я хотів би запропонувати, що якщо ми
хочете вставити елементи в цій

326
00:14:24,800 --> 00:14:26,680
існуючий список, який
складається з п'яти елементів -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26 і 33 -

328
00:14:29,530 --> 00:14:33,300
Якби я збирався здійснити це в
код, мені потрібно подумати, як йти

329
00:14:33,300 --> 00:14:34,160
про це.

330
00:14:34,160 --> 00:14:37,720
>> І я хотів би запропонувати кроки дитини
якої, в даному випадку я маю на увазі, які

331
00:14:37,720 --> 00:14:41,090
можливих сценаріїв, які ми
можуть виникнути в цілому?

332
00:14:41,090 --> 00:14:44,120
При реалізації вставки для пов'язаного
списку, це тільки, трапляється,

333
00:14:44,120 --> 00:14:46,090
Конкретним прикладом розмір п'ять.

334
00:14:46,090 --> 00:14:50,420
Ну, якщо ви хочете вставити цифру,
як, скажімо, номер один, і

335
00:14:50,420 --> 00:14:53,380
підтримання порядку сортування, де
, Очевидно, номер один потрібно

336
00:14:53,380 --> 00:14:55,686
йти в цьому конкретному прикладі?

337
00:14:55,686 --> 00:14:56,840
Наприклад, на початку.

338
00:14:56,840 --> 00:15:00,030
>> Але що цікаво, є те, що
Якщо Ви хочете вставити одну в цю

339
00:15:00,030 --> 00:15:04,100
список, що потрібно спеціальний покажчик
оновити очевидно?

340
00:15:04,100 --> 00:15:04,610
Перша.

341
00:15:04,610 --> 00:15:07,830
Так що я б сказав, що це перший випадок
що ми могли б хотіти розглянути,

342
00:15:07,830 --> 00:15:11,140
сценарій, що включає введення, по
початку списку.

343
00:15:11,140 --> 00:15:15,400
>> Давайте обривати, може бути, так легко, або навіть
простий випадок, умовно кажучи.

344
00:15:15,400 --> 00:15:18,110
Припустимо, я хочу, щоб вставити
35 числа в порядку сортування.

345
00:15:18,110 --> 00:15:20,600
Це, очевидно, належить там.

346
00:15:20,600 --> 00:15:25,320
Так що, очевидно, покажчик буде
повинні бути оновлені в цьому сценарії?

347
00:15:25,320 --> 00:15:30,060
34 в покажчик стає NOT NULL
але адреса структури

348
00:15:30,060 --> 00:15:31,800
містить номер 35.

349
00:15:31,800 --> 00:15:32,750
Так от випадок два.

350
00:15:32,750 --> 00:15:36,190
Так що вже, я начебто квантування
скільки роботи я повинен зробити тут.

351
00:15:36,190 --> 00:15:39,880
>> І, нарешті, очевидний випадок середина
Дійсно, в середині, якщо я хочу

352
00:15:39,880 --> 00:15:45,870
вставляти щось на кшталт говорять 23, який йде
між 23 і 26, але

353
00:15:45,870 --> 00:15:48,680
Тепер все стає трохи більш
бере участь, тому що

354
00:15:48,680 --> 00:15:52,800
покажчики мають бути змінені?

355
00:15:52,800 --> 00:15:56,680
22 Так, безумовно, має бути змінена
тому що він не може вказати на 26 більше.

356
00:15:56,680 --> 00:16:00,320
Йому потрібно, щоб він вказував на новий вузол,
Мені доведеться виділити по телефону

357
00:16:00,320 --> 00:16:01,770
Malloc або деякий еквівалент.

358
00:16:01,770 --> 00:16:05,990
>> Але потім я також потрібно, щоб новий вузол, 23
У цьому випадку, щоб мати свій покажчик

359
00:16:05,990 --> 00:16:07,870
вказуючи на кого?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
І там буде
Порядок операцій тут.

362
00:16:10,380 --> 00:16:13,410
Тому що якщо я зроблю це нерозумно і я
Наприклад початку на початку

363
00:16:13,410 --> 00:16:16,040
списку, і моя мета, щоб вставити 23.

364
00:16:16,040 --> 00:16:18,610
І я перевіряв, воно належить
тут, близько дев'яти?

365
00:16:18,610 --> 00:16:18,950
Ні.

366
00:16:18,950 --> 00:16:20,670
Чи має місце тут, поруч з 17?

367
00:16:20,670 --> 00:16:20,940
Ні.

368
00:16:20,940 --> 00:16:22,530
Чи має вона належить тут поруч з 22?

369
00:16:22,530 --> 00:16:23,300
Так.

370
00:16:23,300 --> 00:16:26,400
>> Тепер, якщо я дурний тут, і не
думаючи, що це до кінця, я міг би

371
00:16:26,400 --> 00:16:28,320
виділити мій новий вузол 23.

372
00:16:28,320 --> 00:16:32,080
Я міг би оновити покажчик з
вузол, який називається 22, вказуючи

373
00:16:32,080 --> 00:16:33,080
його на новий вузол.

374
00:16:33,080 --> 00:16:36,140
І що тоді мені доведеться оновлювати
покажчик на новий вузол, щоб бути?

375
00:16:36,140 --> 00:16:38,120
>> СТУДЕНТ: [нерозбірливо].

376
00:16:38,120 --> 00:16:38,385
>> Виступаючий 1: Абсолютно вірно.

377
00:16:38,385 --> 00:16:39,710
Вказуючи на 26.

378
00:16:39,710 --> 00:16:45,590
Але, чорт візьми, якщо б я вже не оновлювати
Покажчик 22, щоб вона вказувала на цього хлопця, і

379
00:16:45,590 --> 00:16:48,260
тепер у мене є сироти, решта
списку, так сказати.

380
00:16:48,260 --> 00:16:52,140
Так що порядок операцій тут
буде важливо.

381
00:16:52,140 --> 00:16:55,100
>> Для цього я міг вкрасти,
скажімо, шість добровольців.

382
00:16:55,100 --> 00:16:57,650
І давайте подивимося, якщо ми не можемо зробити цього
візуально замість коду-мудрим.

383
00:16:57,650 --> 00:16:59,330
І у нас є деякі прекрасні стресу
кулі для вас сьогодні.

384
00:16:59,330 --> 00:17:02,510
Добре, а як про один, двох, в
Тому - наприкінці там.

385
00:17:02,510 --> 00:17:04,530
три, чотири, ви обидва
Хлопці на кінці.

386
00:17:04,530 --> 00:17:05,579
І п'ять, шість.

387
00:17:05,579 --> 00:17:05,839
Звичайно.

388
00:17:05,839 --> 00:17:06,450
П'ять і шість.

389
00:17:06,450 --> 00:17:08,390
Гаразд, і ми приїдемо
щоб ви, хлопці, в наступний раз.

390
00:17:08,390 --> 00:17:09,640
Гаразд, піднімайся.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Гаразд, якщо вже ти тут, по-перше,
Ви хотіли б бути тим, ніяково

393
00:17:14,819 --> 00:17:16,119
Скло в Google тут?

394
00:17:16,119 --> 00:17:19,075
Гаразд, гаразд, скло,
Запис відео.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
Добре, ви добре йти.

397
00:17:24,589 --> 00:17:27,950
>> Гаразд, так що якщо ви, хлопці, можете приїхати
Тут, я підготував заздалегідь

398
00:17:27,950 --> 00:17:30,110
деякі цифри.

399
00:17:30,110 --> 00:17:31,240
Гаразд, іди сюди.

400
00:17:31,240 --> 00:17:33,440
А чому б вам не піти трохи
далі, що шлях.

401
00:17:33,440 --> 00:17:35,520
І подивимося, як тебе звати,
Скло з Google?

402
00:17:35,520 --> 00:17:35,910
>> СТУДЕНТ: Бен.

403
00:17:35,910 --> 00:17:36,230
>> Виступаючий 1: Бен?

404
00:17:36,230 --> 00:17:38,380
ОК, Бен, ти будеш першим, буквально.

405
00:17:38,380 --> 00:17:40,580
Отже, ми збираємося відправити вам
в кінці стадії.

406
00:17:40,580 --> 00:17:41,670
Гаразд, і ваше ім'я?

407
00:17:41,670 --> 00:17:41,990
>> СТУДЕНТ: Джейсон.

408
00:17:41,990 --> 00:17:44,530
>> Виступаючий 1: Джейсон, OK ви будете
бути номером дев'ять.

409
00:17:44,530 --> 00:17:46,700
Так що, якщо ви хочете слідувати Бен таким чином.

410
00:17:46,700 --> 00:17:47,010
>> СТУДЕНТ: Джилл.

411
00:17:47,010 --> 00:17:49,630
>> Виступаючий 1: Джилл, ви збираєтеся бути
17, який, якщо б я зробив це більш

412
00:17:49,630 --> 00:17:51,260
розумно, я б
почалося на іншому кінці.

413
00:17:51,260 --> 00:17:52,370
Ви йти цим шляхом.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
А ви хто?

416
00:17:53,670 --> 00:17:53,980
>> СТУДЕНТ: Марії.

417
00:17:53,980 --> 00:17:56,130
>> Виступаючий 1: Марія, ви будете 22.

418
00:17:56,130 --> 00:17:58,420
А ваше ім'я?

419
00:17:58,420 --> 00:17:58,810
>> СТУДЕНТ: Кріс.

420
00:17:58,810 --> 00:18:00,100
>> Виступаючий 1: Кріс, ви будете 26.

421
00:18:00,100 --> 00:18:00,740
А потім, нарешті.

422
00:18:00,740 --> 00:18:01,400
>> СТУДЕНТ: Діани.

423
00:18:01,400 --> 00:18:02,670
>> Виступаючий 1: Діана, ви будете 34.

424
00:18:02,670 --> 00:18:03,920
Таким чином, ви іди сюди.

425
00:18:03,920 --> 00:18:06,360
>> Гаразд, настільки досконалий відсортований
Замовити вже.

426
00:18:06,360 --> 00:18:09,600
І давайте йти вперед і робити це
так що ми можемо насправді -

427
00:18:09,600 --> 00:18:11,720
Бен, ти просто вид дивлячись
з в нікуди там.

428
00:18:11,720 --> 00:18:15,670
Отже, давайте підемо далі і зображують цю
застосуванням зброї, так само, як я був, власне,

429
00:18:15,670 --> 00:18:16,250
що відбувається.

430
00:18:16,250 --> 00:18:19,540
Так що йти вперед і дати собі
фут чи два між собою.

431
00:18:19,540 --> 00:18:22,900
І йти вперед і відзначити з одного боку,
хто б ти повинен бути спрямований на

432
00:18:22,900 --> 00:18:23,470
на основі цього.

433
00:18:23,470 --> 00:18:25,890
І якщо ви просто вказати нульовий
прямо вниз до підлоги.

434
00:18:25,890 --> 00:18:27,690
Добре, так добре.

435
00:18:27,690 --> 00:18:32,290
>> Так що тепер у нас є зв'язаний список, і дозвольте мені
пропоную, що я буду грати роль

436
00:18:32,290 --> 00:18:35,110
PTR, так що я не буду турбуватися
проведення цього навколо.

437
00:18:35,110 --> 00:18:37,830
А потім - хтось дурний Конвенції -
Ви можете називати це все, що завгодно -

438
00:18:37,830 --> 00:18:39,800
попередника покажчик, покажчик PRED -

439
00:18:39,800 --> 00:18:43,930
це просто прізвисько ми дали в
наш зразок коду для моєї лівій руці.

440
00:18:43,930 --> 00:18:47,240
З іншого боку, що буде збереження
відслідковувати, хто є хто в

441
00:18:47,240 --> 00:18:48,400
Наступні сценарії.

442
00:18:48,400 --> 00:18:52,390
>> Отже, нехай, по-перше, я хочу обривати
що перший приклад вставки, скажімо

443
00:18:52,390 --> 00:18:54,330
20 в списку.

444
00:18:54,330 --> 00:18:57,160
Так що я збираюся потрібно, щоб хтось
втілюють у собі число 20 для нас.

445
00:18:57,160 --> 00:18:58,950
Так що мені потрібно когось Malloc
від аудиторії.

446
00:18:58,950 --> 00:18:59,380
Піднімайся.

447
00:18:59,380 --> 00:19:00,340
Як тебе звуть?

448
00:19:00,340 --> 00:19:01,300
>> СТУДЕНТ: Брайан.

449
00:19:01,300 --> 00:19:05,270
>> Виступаючий 1: Брайан, все гаразд, так що ви
повинен бути вузол, що містить 20.

450
00:19:05,270 --> 00:19:06,810
Гаразд, іди сюди.

451
00:19:06,810 --> 00:19:10,025
І очевидно, що, де
Брайан дійсно належите?

452
00:19:10,025 --> 00:19:12,190
Таким чином, в середині - власне,
почекай хвилинку.

453
00:19:12,190 --> 00:19:13,420
Ми робимо це не в порядку.

454
00:19:13,420 --> 00:19:17,170
Ми робимо це набагато складніше
, Чим вона повинна бути в першу чергу.

455
00:19:17,170 --> 00:19:21,210
Добре, ми збираємося безкоштовно Брайан
Брайан і Realloc як п'ять.

456
00:19:21,210 --> 00:19:23,680
>> Отже, тепер ми хочемо, щоб вставити
Брайан, як п'ять.

457
00:19:23,680 --> 00:19:25,960
Так іди сюди поруч з
Бен на мить.

458
00:19:25,960 --> 00:19:28,250
І ви, мабуть, може сказати
де ця історія йде.

459
00:19:28,250 --> 00:19:30,500
Але давайте ретельно обміркуйте
порядок виконання операцій.

460
00:19:30,500 --> 00:19:32,880
І це саме це візуальне
що відбувається, щоб вишикуватися

461
00:19:32,880 --> 00:19:34,080
з цей зразок коду.

462
00:19:34,080 --> 00:19:40,120
Так от я PTR спочатку вказуючи
Відповіді Бена, як такої, але на будь-якому

463
00:19:40,120 --> 00:19:43,245
оцінюють він містить, який в даному випадку
- Що тебе звуть?

464
00:19:43,245 --> 00:19:43,670
>> СТУДЕНТ: Джейсон.

465
00:19:43,670 --> 00:19:47,350
>> Виступаючий 1: Джейсон, так як Бен і я
вказуючи на Джейсона в цей момент.

466
00:19:47,350 --> 00:19:49,700
Так що тепер у мене є, щоб визначити,
де ж Брайан належите?

467
00:19:49,700 --> 00:19:53,500
Тому єдине, що я маю доступ до
Прямо зараз його N елемента даних.

468
00:19:53,500 --> 00:19:58,280
Так що я збираюся перевірити, є
Брайан менше Джейсон?

469
00:19:58,280 --> 00:19:59,770
Відповідь на це питання так.

470
00:19:59,770 --> 00:20:03,680
>> Так що зараз має статися,
в правильному порядку?

471
00:20:03,680 --> 00:20:07,120
Мені потрібно уточнити, скільки покажчиків
Всього в цій історії?

472
00:20:07,120 --> 00:20:10,720
Де моя рука все ще вказуючи на
Джейсон, і ваша рука - якщо ви хочете

473
00:20:10,720 --> 00:20:12,930
покласти руку, як, начебто, я
Не знаю, знаком питання.

474
00:20:12,930 --> 00:20:14,070
Добре, добре.

475
00:20:14,070 --> 00:20:15,670
>> Гаразд, так що ви повинні
кілька кандидатів.

476
00:20:15,670 --> 00:20:20,500
Або Бен або я або Джейсон Брайан або
або всі інші, які

477
00:20:20,500 --> 00:20:21,370
покажчики потрібно змінити?

478
00:20:21,370 --> 00:20:23,260
Скільки всього?

479
00:20:23,260 --> 00:20:24,080
>> Отже, два.

480
00:20:24,080 --> 00:20:27,090
Мій покажчик насправді не має ніякого значення
тому що я тільки тимчасово.

481
00:20:27,090 --> 00:20:31,370
Так що ці два хлопці, мабуть,
як Бен і Брайана.

482
00:20:31,370 --> 00:20:34,410
Отже, дозвольте мені запропонувати, що ми оновлюємо
Бен, так як він в першу чергу.

483
00:20:34,410 --> 00:20:36,350
Першим елементом цього списку
Тепер буде Брайан.

484
00:20:36,350 --> 00:20:38,070
Так Бен точки на Брайана.

485
00:20:38,070 --> 00:20:39,320
Добре, що тепер?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Хто отримує вказав на кого?

488
00:20:43,460 --> 00:20:44,710
>> СТУДЕНТ: [нерозбірливо].

489
00:20:44,710 --> 00:20:46,180
>> Виступаючий 1: Добре, таким чином Брайан
щоб вказати на Джейсона.

490
00:20:46,180 --> 00:20:48,360
Але я втратив цей покажчик?

491
00:20:48,360 --> 00:20:49,980
Чи знаю я, де Джейсон?

492
00:20:49,980 --> 00:20:50,790
>> СТУДЕНТ: [нерозбірливо].

493
00:20:50,790 --> 00:20:52,620
>> Виступаючий 1: я роблю, так як я
тимчасовий покажчик.

494
00:20:52,620 --> 00:20:55,110
І мабуть, я не змінив
, Щоб вказати на новий вузол.

495
00:20:55,110 --> 00:20:58,300
Так що ми можемо просто Брайан точки
той, хто на мене вказуючи на.

496
00:20:58,300 --> 00:20:59,000
І ми зробили.

497
00:20:59,000 --> 00:21:01,890
Таким випадком, вставка на
початок списку.

498
00:21:01,890 --> 00:21:02,950
Були два ключових кроки.

499
00:21:02,950 --> 00:21:06,750
По-перше, ми повинні оновити Бена, а потім
Ми також повинні оновити Брайан.

500
00:21:06,750 --> 00:21:09,230
І тоді я не доведеться турбуватися
тащась через решту

501
00:21:09,230 --> 00:21:12,680
список, тому що ми вже знайшли його
розташування, тому що він належав до

502
00:21:12,680 --> 00:21:14,080
ліворуч від першого елемента.

503
00:21:14,080 --> 00:21:15,400
>> Гаразд, досить проста.

504
00:21:15,400 --> 00:21:18,110
Справді, здається, що ми вже майже
робить це занадто складно.

505
00:21:18,110 --> 00:21:20,240
Отже, давайте обривати кінця
списку, і побачити, де

506
00:21:20,240 --> 00:21:21,380
Складність починається.

507
00:21:21,380 --> 00:21:24,560
Отже якщо зараз, я Alloc від аудиторії.

508
00:21:24,560 --> 00:21:25,540
Будь хоче грати 55?

509
00:21:25,540 --> 00:21:26,700
Гаразд, я бачив вашу руку першим.

510
00:21:26,700 --> 00:21:29,620
Піднімайся.

511
00:21:29,620 --> 00:21:30,030
Так.

512
00:21:30,030 --> 00:21:31,177
Як тебе звуть?

513
00:21:31,177 --> 00:21:32,310
>> СТУДЕНТ: [нерозбірливо].

514
00:21:32,310 --> 00:21:33,240
>> Виступаючий 1: Habata.

515
00:21:33,240 --> 00:21:33,890
ОК, давай вгору.

516
00:21:33,890 --> 00:21:35,730
Ви будете номером 55.

517
00:21:35,730 --> 00:21:37,820
Таким чином, ви, звичайно, належать
в кінці списку.

518
00:21:37,820 --> 00:21:41,850
Так що давайте переграти моделювання зі мною
будучи PTR на мить.

519
00:21:41,850 --> 00:21:44,050
Так що я збираюся першим, щоб вказати на
все, що Бена вказуючи на.

520
00:21:44,050 --> 00:21:45,900
Ми обидва тепер, вказуючи на Брайана.

521
00:21:45,900 --> 00:21:48,420
Так 55 не менше, аніж п'ять.

522
00:21:48,420 --> 00:21:52,510
Так що я збираюся оновити себе,
вказуючи на наступний покажчик Брайана, який

523
00:21:52,510 --> 00:21:54,450
Зараз, звичайно, Джейсон.

524
00:21:54,450 --> 00:21:57,310
55 становить не менше дев'яти, так
Я збираюся оновити PTR.

525
00:21:57,310 --> 00:21:58,890
Я збираюся оновити PTR.

526
00:21:58,890 --> 00:22:02,290
Я збираюся оновити PTR
Я збираюся оновити PTR.

527
00:22:02,290 --> 00:22:05,060
І я збираюся - Хм, що це
тебе звати?

528
00:22:05,060 --> 00:22:05,560
>> СТУДЕНТ: Діани.

529
00:22:05,560 --> 00:22:09,190
>> Виступаючий 1: Діана вказує, звичайно,
при нульовому лівою рукою.

530
00:22:09,190 --> 00:22:13,030
То де ж насправді Habata
належать ясно?

531
00:22:13,030 --> 00:22:15,050
З лівого боку, тут.

532
00:22:15,050 --> 00:22:19,460
Так як я знаю, поставити її тут
Я думаю, що я облажався.

533
00:22:19,460 --> 00:22:22,420
Адже що таке мистецтво PTR
даний момент часу?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Так що, хоча, візуально, ми можемо
Очевидно, всі ці

536
00:22:25,580 --> 00:22:26,610
хлопці тут на сцені.

537
00:22:26,610 --> 00:22:29,680
Я не стежив за попередніми
людина в списку.

538
00:22:29,680 --> 00:22:33,210
У мене немає пальцем вказуючи,
У цьому випадку номер вузла 34.

539
00:22:33,210 --> 00:22:34,760
>> Так що давайте насправді почати над цим.

540
00:22:34,760 --> 00:22:37,560
Так що тепер я насправді потрібно
Друга локальної змінної.

541
00:22:37,560 --> 00:22:40,980
І це те, що ви побачите в
Сам зразок коду C, де, як я йду,

542
00:22:40,980 --> 00:22:45,860
коли я оновлюю мою праву руку, щоб вказати
Джейсон, тим самим залишаючи Брайана позаду, я

543
00:22:45,860 --> 00:22:51,440
краще почати використовувати мою ліву руку, щоб
оновлення, де я був, так що, як я йду

544
00:22:51,440 --> 00:22:52,700
через цей список -

545
00:22:52,700 --> 00:22:55,040
більш ніяково, ніж хотів
Тепер ось візуально -

546
00:22:55,040 --> 00:22:56,740
Я йду, щоб дістатися до
кінці списку.

547
00:22:56,740 --> 00:23:00,020
>> Ця рука і раніше нульової, який є досить
марним, крім вказувати

548
00:23:00,020 --> 00:23:02,980
Я ясно в кінці списку
але тепер принаймні, у мене є ця

549
00:23:02,980 --> 00:23:08,270
попередника покажчик, який вказує тут, так що
Тепер те, що руки і те, що потрібно покажчики

550
00:23:08,270 --> 00:23:10,150
в оновленні?

551
00:23:10,150 --> 00:23:13,214
Чия рука ви хочете
переналаштувати в першу чергу?

552
00:23:13,214 --> 00:23:15,190
>> СТУДЕНТ: [нерозбірливо].

553
00:23:15,190 --> 00:23:16,220
>> Виступаючий 1: Отже, Діани.

554
00:23:16,220 --> 00:23:21,110
Де Ви хочете, щоб вказати
Ліва Діани покажчик у?

555
00:23:21,110 --> 00:23:23,620
На 55, мабуть, з тим щоб
ми вставили туди.

556
00:23:23,620 --> 00:23:25,560
А де повинні 55 покажчика йти?

557
00:23:25,560 --> 00:23:27,000
Вниз, що представляє нульовий.

558
00:23:27,000 --> 00:23:28,890
І мої руки, на даний момент, не
значення, тому що вони були просто

559
00:23:28,890 --> 00:23:30,070
тимчасових змінних.

560
00:23:30,070 --> 00:23:31,030
Так що тепер ми закінчимо.

561
00:23:31,030 --> 00:23:34,650
>> Таким чином, додаткові складності там - і
це не так складно реалізувати,

562
00:23:34,650 --> 00:23:38,660
але нам потрібна друга змінна, щоб зробити
упевнений, що перш, ніж я можу рухати правою

563
00:23:38,660 --> 00:23:42,140
боку, я оновити значення моєї лівої
боку, ПОПЕРЕД покажчик у цьому випадку, так

564
00:23:42,140 --> 00:23:45,860
що у мене є задній покажчик
відслідковувати, де я був.

565
00:23:45,860 --> 00:23:49,360
Тепер, як осторонь, якщо ви думаєте, що це
через це почуття, що це

566
00:23:49,360 --> 00:23:51,490
трохи дратує, щоб зберегти
слід цього лівою рукою.

567
00:23:51,490 --> 00:23:54,015
>> Що б інше рішення
цієї проблеми були?

568
00:23:54,015 --> 00:23:56,500
Якщо у вас є, щоб перепроектувати даних
структури ми говоримо

569
00:23:56,500 --> 00:23:59,630
через прямо зараз?

570
00:23:59,630 --> 00:24:02,690
Якщо це тільки частково відчуває себе трохи
дратівливим, начебто, два покажчика

571
00:24:02,690 --> 00:24:08,430
збирається за списком, хто ще міг
були, в ідеальному світі, підтримується

572
00:24:08,430 --> 00:24:10,160
інформацію, яка нам потрібна?

573
00:24:10,160 --> 00:24:11,360
Так?

574
00:24:11,360 --> 00:24:12,610
>> СТУДЕНТ: [нерозбірливо].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> Виступаючий 1: Абсолютно вірно.

577
00:24:16,150 --> 00:24:19,130
Право так є насправді цікаве
зародок ідеї.

578
00:24:19,130 --> 00:24:22,470
І ця ідея попереднього покажчика,
вказуючи на попередній елемент.

579
00:24:22,470 --> 00:24:25,580
Що робити, якщо я просто втіленням цього
всередині самого списку?

580
00:24:25,580 --> 00:24:27,810
І це буде важко візуалізувати
Все це без паперу

581
00:24:27,810 --> 00:24:28,830
падіння на підлогу.

582
00:24:28,830 --> 00:24:31,860
Але припустимо, що ці хлопці використовуватися як
їх руки, щоб мати попередні

583
00:24:31,860 --> 00:24:35,950
покажчик, і наступний покажчик, тим самим
реалізувати те, що ми назвемо подвійно

584
00:24:35,950 --> 00:24:36,830
зв'язаний список.

585
00:24:36,830 --> 00:24:41,090
Яка дозволила б мені, щоб розібратися перемотування,
набагато легше без мене,

586
00:24:41,090 --> 00:24:43,800
програміст, необхідності тримати
відслідковувати вручну -

587
00:24:43,800 --> 00:24:44,980
дійсно вручну -

588
00:24:44,980 --> 00:24:47,280
від того, де я був раніше
у списку.

589
00:24:47,280 --> 00:24:48,110
Тому ми не будемо цього робити.

590
00:24:48,110 --> 00:24:50,950
Ми будемо тримати його просто, тому що це
збирається прийти в ціні, в два рази

591
00:24:50,950 --> 00:24:53,450
багато місця для покажчиків,
якщо ви хочете другу.

592
00:24:53,450 --> 00:24:55,760
Але це дійсно загальний
Структура даних відомих як

593
00:24:55,760 --> 00:24:57,410
двічі зв'язаний список.

594
00:24:57,410 --> 00:25:01,310
>> Давайте зробимо останній приклад тут і покласти
ці хлопці з їх страждання.

595
00:25:01,310 --> 00:25:03,270
Так Malloc 20.

596
00:25:03,270 --> 00:25:05,320
Піднімайтеся з проходу там.

597
00:25:05,320 --> 00:25:06,280
Гаразд, як тебе звати?

598
00:25:06,280 --> 00:25:07,440
>> СТУДЕНТ: [нерозбірливо].

599
00:25:07,440 --> 00:25:07,855
>> Виступаючий 1: Пробачте?

600
00:25:07,855 --> 00:25:08,480
>> СТУДЕНТ: [нерозбірливо].

601
00:25:08,480 --> 00:25:09,410
>> Виступаючий 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
ОК піднімайся.

603
00:25:10,230 --> 00:25:11,910
Ви повинні бути 20.

604
00:25:11,910 --> 00:25:14,720
Ви, очевидно, збираються
належать від 17 до 22.

605
00:25:14,720 --> 00:25:16,150
Отже, дозвольте мені дізнатися свій урок.

606
00:25:16,150 --> 00:25:18,150
Я збираюся почати покажчик
вказуючи на Брайана.

607
00:25:18,150 --> 00:25:21,190
І я буду мати мою ліву руку
оновлювати тільки з Брайаном, як я переїхати в

608
00:25:21,190 --> 00:25:23,600
Джейсон, 20 перевірка робить менше дев'яти?

609
00:25:23,600 --> 00:25:24,060
Ні.

610
00:25:24,060 --> 00:25:25,430
На 20 менше, ніж 17?

611
00:25:25,430 --> 00:25:25,880
Ні.

612
00:25:25,880 --> 00:25:27,450
На 20 менше, ніж 22?

613
00:25:27,450 --> 00:25:28,440
Так.

614
00:25:28,440 --> 00:25:34,070
Так що покажчики або рук потрібно змінити
де вони вказуючи зараз?

615
00:25:34,070 --> 00:25:37,070
>> Так що ми можемо зробити, вказуючи на 17 20.

616
00:25:37,070 --> 00:25:37,860
Так що це нормально.

617
00:25:37,860 --> 00:25:40,080
Куди ми хочемо, щоб вказати
покажчик зараз?

618
00:25:40,080 --> 00:25:41,330
У 22.

619
00:25:41,330 --> 00:25:45,410
І ми знаємо, де 22, знову ж таки завдяки
на мій тимчасовий покажчик.

620
00:25:45,410 --> 00:25:46,760
Таким чином, ми все гаразд там.

621
00:25:46,760 --> 00:25:49,440
Так через це тимчасового зберігання
Я стежив, де всі.

622
00:25:49,440 --> 00:25:55,055
І тепер ви можете візуально вдаватися в якому
Ви належите, і тепер нам потрібно 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 куль стрес,
і оплески для

624
00:25:58,410 --> 00:25:59,770
ці хлопці, якщо ми могли.

625
00:25:59,770 --> 00:26:00,410
Красиво зроблено.

626
00:26:00,410 --> 00:26:05,320
>> [Оплески]

627
00:26:05,320 --> 00:26:06,330
>> Виступаючий 1: Добре.

628
00:26:06,330 --> 00:26:09,860
І ви можете тримати частини
папери на пам'ять.

629
00:26:09,860 --> 00:26:15,930
>> Гаразд, так що, повірте мені, це набагато
легше йти через це з

630
00:26:15,930 --> 00:26:17,680
людей, ніж з фактичним кодом.

631
00:26:17,680 --> 00:26:22,690
Але те, що ви знайдете в мить
Тепер, те, що ж - о, спасибо.

632
00:26:22,690 --> 00:26:23,630
Спасибі -

633
00:26:23,630 --> 00:26:29,360
є те, що ви побачите, що ті ж дані
структури, зв'язаний список, може насправді

634
00:26:29,360 --> 00:26:33,200
використовуватися в якості будівельного блоку, щоб ще більше
складних структур даних.

635
00:26:33,200 --> 00:26:37,620
>> І зрозумійте, занадто тема тут є те, що
ми абсолютно ввели більш

636
00:26:37,620 --> 00:26:40,060
Складність у реалізації
цього алгоритму.

637
00:26:40,060 --> 00:26:43,940
Вставки, і якщо ми пройшли через це,
видалення і пошук, трохи

638
00:26:43,940 --> 00:26:46,660
складніше, ніж
був з масивом.

639
00:26:46,660 --> 00:26:48,040
Але ми отримати деяку динаміку.

640
00:26:48,040 --> 00:26:50,180
Ми отримуємо адаптивну структуру даних.

641
00:26:50,180 --> 00:26:54,010
>> Але знову ж, ми платимо ціну наявністю деяких
додаткові складності, як у

642
00:26:54,010 --> 00:26:54,910
його здійсненні.

643
00:26:54,910 --> 00:26:56,750
І ми відмовилися від випадкового доступу.

644
00:26:56,750 --> 00:27:00,450
І, чесно кажучи, немає деяких хороших
чисте предметне я можу дати вам, що

645
00:27:00,450 --> 00:27:03,120
говорить ось чому зв'язаний список
краще, ніж масив.

646
00:27:03,120 --> 00:27:04,100
І залишити все як є.

647
00:27:04,100 --> 00:27:07,520
Тому що тема повторення тепер, навіть
більше, що в найближчі тижні, є

648
00:27:07,520 --> 00:27:10,200
що є не обов'язково
правильну відповідь.

649
00:27:10,200 --> 00:27:13,830
>> Ось чому у нас є окремі осі
дизайну для домашніх завдань.

650
00:27:13,830 --> 00:27:17,700
Це буде дуже контекстно-залежних
чи хочете ви використовувати ці дані

651
00:27:17,700 --> 00:27:21,750
структуру або, що одне і воно буде
залежить від того, що для вас важливо в плані

652
00:27:21,750 --> 00:27:24,620
ресурсів і складності.

653
00:27:24,620 --> 00:27:28,830
>> Але дозвольте мені запропонувати, що ідеальні дані
Структура, Святий Грааль, були б

654
00:27:28,830 --> 00:27:32,200
те, що постійна часу,
незалежно від того, скільки матеріал

655
00:27:32,200 --> 00:27:36,940
всередині неї, не було б дивно, якщо
структура даних, яка повертається відповіді

656
00:27:36,940 --> 00:27:37,920
постійний час.

657
00:27:37,920 --> 00:27:38,330
Так.

658
00:27:38,330 --> 00:27:40,110
Це слово у вашому величезному словнику.

659
00:27:40,110 --> 00:27:41,550
Або ні, це слово не є.

660
00:27:41,550 --> 00:27:43,270
Або будь-яка така проблема.

661
00:27:43,270 --> 00:27:46,360
Ну давайте подивимося, якщо ми не можемо принаймні,
зробити крок на цьому шляху.

662
00:27:46,360 --> 00:27:50,190
>> Дозвольте мені запропонувати нову структуру даних, яка
можуть бути використані для різних цілей,

663
00:27:50,190 --> 00:27:52,260
У цьому випадку називають хеш-таблиці.

664
00:27:52,260 --> 00:27:55,590
І ось ми насправді повернутися до глянувши
в масиві, і в цьому випадку, а також

665
00:27:55,590 --> 00:28:00,550
кілька довільно, я намалював цю
хеш-таблиці у вигляді масиву роду

666
00:28:00,550 --> 00:28:02,810
двовимірний масив -

667
00:28:02,810 --> 00:28:05,410
або, скоріше, він зображений тут як два
одновимірний масив - але це тільки

668
00:28:05,410 --> 00:28:10,770
масив розміром 26, так що, якщо ми
називають масивом, настільний кронштейн

669
00:28:10,770 --> 00:28:12,440
нуля прямокутника у верхній частині.

670
00:28:12,440 --> 00:28:15,090
Таблиця 25 кронштейн є прямокутником
в нижній частині.

671
00:28:15,090 --> 00:28:18,620
І це, як я міг би намалювати дані
структура, в якій я хочу зберегти

672
00:28:18,620 --> 00:28:19,790
імена людей.

673
00:28:19,790 --> 00:28:24,370
>> Так, наприклад, і я не буду малювати
Все це тут, на накладні витрати, якщо я

674
00:28:24,370 --> 00:28:29,160
було це масив, який я зараз збираюся
називають хеш-таблицю, і це знову ж

675
00:28:29,160 --> 00:28:31,360
Розміщення нулю.

676
00:28:31,360 --> 00:28:34,840
Це ось розташування
, І так далі.

677
00:28:34,840 --> 00:28:37,880
Я стверджую, що я хочу використовувати ці дані
Структура, заради обговорення,

678
00:28:37,880 --> 00:28:42,600
зберігати імена людей, Аліса і Боб
і Чарлі та інші подібні імена.

679
00:28:42,600 --> 00:28:46,110
Так що думати про це зараз, коли почав
, Скажімо, словник

680
00:28:46,110 --> 00:28:47,520
з великою кількістю слів.

681
00:28:47,520 --> 00:28:49,435
Вони, виявляється, імена
У нашому прикладі.

682
00:28:49,435 --> 00:28:52,560
І все це занадто доречні, мабуть,
здійснення перевірки орфографії, як ми

683
00:28:52,560 --> 00:28:54,400
може для проблемних встановити шість.

684
00:28:54,400 --> 00:28:59,300
>> Так що, якщо у нас є масив від загального розміру 26
так що це 25-й розташування

685
00:28:59,300 --> 00:29:03,390
в нижній частині, і я стверджую, що Аліса
Перше слово в словнику

686
00:29:03,390 --> 00:29:07,260
імена, які я хочу вкласти в оперативну пам'ять,
в цю структуру даних, де

687
00:29:07,260 --> 00:29:12,480
інстинкти говорять вам, що Аліси
ім'я має йти в цьому масиві?

688
00:29:12,480 --> 00:29:13,510
>> У нас є 26 варіантів.

689
00:29:13,510 --> 00:29:14,990
Де ми хочемо поставити її?

690
00:29:14,990 --> 00:29:16,200
Ми хочемо її в кронштейн нулю, чи не так?

691
00:29:16,200 --> 00:29:18,280
Для Аліси, давайте назвемо що нулю.

692
00:29:18,280 --> 00:29:20,110
І B буде однією і С будуть два.

693
00:29:20,110 --> 00:29:22,600
Отже, ми збираємося писати
Аліса ім'я тут.

694
00:29:22,600 --> 00:29:24,890
Якщо ми потім вставте Боб, його
Назва піду сюди.

695
00:29:24,890 --> 00:29:27,280
Чарлі піду сюди.

696
00:29:27,280 --> 00:29:30,500
І так далі вниз через
цієї структури даних.

697
00:29:30,500 --> 00:29:32,090
>> Це прекрасна структури даних.

698
00:29:32,090 --> 00:29:32,730
Чому?

699
00:29:32,730 --> 00:29:37,460
Ну те, що час роботи
вставка ім'я людини в цю

700
00:29:37,460 --> 00:29:39,850
Структура даних прямо зараз?

701
00:29:39,850 --> 00:29:43,702
Враховуючи, що ця таблиця буде реалізований,
дійсно, як масив.

702
00:29:43,702 --> 00:29:44,940
Ну, це постійний час.

703
00:29:44,940 --> 00:29:45,800
Це порядку одиниці.

704
00:29:45,800 --> 00:29:46,360
Чому?

705
00:29:46,360 --> 00:29:48,630
>> Ну як ви визначаєте,
Де Alice належить?

706
00:29:48,630 --> 00:29:51,000
Ти дивишся на яку букву її імені?

707
00:29:51,000 --> 00:29:51,490
Перше.

708
00:29:51,490 --> 00:29:54,350
І ви можете отримати там, якщо це рядок,
просто дивлячись на рядок

709
00:29:54,350 --> 00:29:55,200
Кронштейн нулю.

710
00:29:55,200 --> 00:29:57,110
Таким чином, нульовий символ рядка.

711
00:29:57,110 --> 00:29:57,610
Це легко.

712
00:29:57,610 --> 00:30:00,350
Ми зробили це в Crypto
Призначення тижні тому.

713
00:30:00,350 --> 00:30:05,310
І те, як тільки ви знаєте, що Аліси
Лист капіталу, ми можемо відняти

714
00:30:05,310 --> 00:30:08,160
від 65 років і сам капітал,
, Що дає нам нулю.

715
00:30:08,160 --> 00:30:10,940
Таким чином, ми тепер знаємо, що Аліса належить
за місцем знаходження нуля.

716
00:30:10,940 --> 00:30:14,240
>> А якщо врахувати, покажчик на ці дані
структури, якийсь, як довго

717
00:30:14,240 --> 00:30:18,840
мені буде потрібно, щоб знайти розташування
нулю у масив?

718
00:30:18,840 --> 00:30:22,080
Всього лише один крок, права Це постійний час
за випадкового доступу ми

719
00:30:22,080 --> 00:30:23,780
Пропонований було особливістю масиву.

720
00:30:23,780 --> 00:30:28,570
Коротше кажучи, з'ясувати, що індекс
імені Аліси, яка, за

721
00:30:28,570 --> 00:30:32,610
цьому випадку, або давайте просто вирішувати
що до нуля, де B є одним і С

722
00:30:32,610 --> 00:30:34,900
два, вважаючи, що з
постійна часу.

723
00:30:34,900 --> 00:30:38,510
Я просто дивитися на неї перший лист,
з'ясовуючи, де нуль

724
00:30:38,510 --> 00:30:40,460
масив також постійний час.

725
00:30:40,460 --> 00:30:42,140
Так що технічно це
як тепер два кроки.

726
00:30:42,140 --> 00:30:43,330
Але це все одно постійно.

727
00:30:43,330 --> 00:30:46,880
Так ми називаємо це Big O одного Таким чином ми
вставлені Аліса в цю таблицю у

728
00:30:46,880 --> 00:30:48,440
постійний час.

729
00:30:48,440 --> 00:30:50,960
>> Але, звичайно, я поводжуся
наївна, так?

730
00:30:50,960 --> 00:30:53,240
Що робити, якщо є Аарона в класі?

731
00:30:53,240 --> 00:30:53,990
Або Алісія?

732
00:30:53,990 --> 00:30:57,230
Або будь-які інші імена, що починаються з
А. Куди ми збираємося поставити

733
00:30:57,230 --> 00:31:00,800
що людина, чи не так?

734
00:31:00,800 --> 00:31:03,420
Я маю на увазі, просто зараз є тільки три
люди на стіл, тому можливо, ми

735
00:31:03,420 --> 00:31:07,490
Аарон повинен покласти за місцем знаходження
нуль один два три.

736
00:31:07,490 --> 00:31:09,480
>> Право, я міг би поставити тут.

737
00:31:09,480 --> 00:31:13,350
Але тоді, якщо ми намагаємося вкласти Давида в
цього списку, де ж Давид йти?

738
00:31:13,350 --> 00:31:15,170
Тепер наша система починає порушення
вниз, вправо?

739
00:31:15,170 --> 00:31:19,210
Тому що тепер Девід закінчує тут
Якщо насправді Аарон тут.

740
00:31:19,210 --> 00:31:23,060
І ось тепер вся ця ідея з
чиста структура даних, яка дає нам

741
00:31:23,060 --> 00:31:28,010
вставок постійного часу вже не
постійний час, тому що я повинен

742
00:31:28,010 --> 00:31:31,240
перевірити, про, чорт візьми, хтось вже
за місцем знаходження Аліси.

743
00:31:31,240 --> 00:31:35,320
>> Дозвольте мені досліджувати решту цього дані
Структура, шукаючи місце, щоб покласти

744
00:31:35,320 --> 00:31:37,130
хтось, як ім'я Аарона.

745
00:31:37,130 --> 00:31:39,390
І так, що теж починає
прийняти лінійний час.

746
00:31:39,390 --> 00:31:42,710
Більше того, якщо ви зараз хочете знайти
Аарон в цій структурі даних, і ви

747
00:31:42,710 --> 00:31:45,430
перевірити і ім'я Аарона тут немає.

748
00:31:45,430 --> 00:31:47,960
В ідеалі, ви просто сказали б Аарона
не в структурі даних.

749
00:31:47,960 --> 00:31:51,530
Але якщо ви починаєте звільняючи місце для
Аарон, де мало бути D

750
00:31:51,530 --> 00:31:55,600
або E, ви, гіршому випадку, доведеться перевірити
Вся структура даних, у

751
00:31:55,600 --> 00:31:59,480
цьому випадку вона переходить у щось
лінійний в розмір таблиці.

752
00:31:59,480 --> 00:32:00,920
>> Так що все в порядку, я буду це виправити.

753
00:32:00,920 --> 00:32:04,200
Проблема тут у тому, що у мене було
26 елементів в цьому масиві.

754
00:32:04,200 --> 00:32:05,000
Дозвольте мені змінити.

755
00:32:05,000 --> 00:32:06,010
На жаль.

756
00:32:06,010 --> 00:32:10,600
Дозвольте мені змінити його так, що замість буття
розмір 26 в цілому, зверніть увагу на нижню

757
00:32:10,600 --> 00:32:12,720
Індекс змінюватиметься на N мінус 1.

758
00:32:12,720 --> 00:32:16,610
Якщо 26 явно замалий для людей "
імена, тому що є тисячі

759
00:32:16,610 --> 00:32:20,830
імена світу, давайте просто робити
в 100 або 1000 або 10000.

760
00:32:20,830 --> 00:32:22,960
Давайте просто виділити набагато більше місця.

761
00:32:22,960 --> 00:32:27,230
>> Ну, що зовсім не обов'язково знижує
ймовірність того, що ми не будемо мати два

762
00:32:27,230 --> 00:32:31,510
люди з іменами, що починаються з, і
Отже, ви збираєтеся, щоб спробувати покласти

763
00:32:31,510 --> 00:32:33,120
імена за місцем знаходження нуля до цих пір.

764
00:32:33,120 --> 00:32:36,850
Вони все ще збираємося стикаються, яка
означає, що ми все ще потрібно рішення, щоб покласти

765
00:32:36,850 --> 00:32:41,020
Аліса і Аарона та Алісія та інші
імена, що починаються з в іншому місці.

766
00:32:41,020 --> 00:32:43,460
Але як велика проблема це?

767
00:32:43,460 --> 00:32:46,870
Яка ймовірність того, що ви
можуть виникати конфлікти в даних

768
00:32:46,870 --> 00:32:48,240
структури, як це?

769
00:32:48,240 --> 00:32:52,570
>> Ну, дозвольте мені - ми повернемося
На це питання тут.

770
00:32:52,570 --> 00:32:55,530
І подивіться, як ми могли б
вирішити в першу чергу.

771
00:32:55,530 --> 00:32:58,480
Дозвольте мені підтягнути цю пропозицію тут.

772
00:32:58,480 --> 00:33:02,020
Те, що ми тільки що описали алгоритм,
евристичні називаються лінійними

773
00:33:02,020 --> 00:33:05,030
зондування якої, якби ви спробували вставити
щось тут, у цьому дані

774
00:33:05,030 --> 00:33:08,920
Структура, яка називається хеш-таблицю,
і там немає місця там, ви

775
00:33:08,920 --> 00:33:12,000
дійсно дослідити структури даних
перевірки, це доступно?

776
00:33:12,000 --> 00:33:13,430
Чи є це доступно це доступно?

777
00:33:13,430 --> 00:33:13,980
Чи є це доступно?

778
00:33:13,980 --> 00:33:17,550
І коли він, нарешті, ви вставте
ім'я, яке ви спочатку

779
00:33:17,550 --> 00:33:19,370
в інших місцях в цьому місці.

780
00:33:19,370 --> 00:33:23,360
Але в гіршому випадку, єдине місце,
може бути в самому низу даних

781
00:33:23,360 --> 00:33:25,090
Структура, в самому кінці масиву.

782
00:33:25,090 --> 00:33:30,130
>> Так лінійного зондування, в гіршому випадку,
перетвориться в лінійний алгоритм, де

783
00:33:30,130 --> 00:33:34,500
Аарона, якщо він відбудеться, буде вставлений останній
У цій структурі даних, він може

784
00:33:34,500 --> 00:33:39,540
стикатися з цієї першої місці, але
Потім закінчитися невдачею в самому кінці.

785
00:33:39,540 --> 00:33:43,940
Так що це не постійна
час святий Грааль для нас.

786
00:33:43,940 --> 00:33:47,650
Цей підхід вставки елементів у
структуру даних, звану хеш

787
00:33:47,650 --> 00:33:52,050
Таблиця не видається, постійне час
принаймні, в загальному випадку.

788
00:33:52,050 --> 00:33:54,000
Це може перетвориться на щось лінійної.

789
00:33:54,000 --> 00:33:56,970
>> Так що, якщо ми вирішення колізій
дещо по-іншому?

790
00:33:56,970 --> 00:34:00,740
Отже, ось більш складні
підходити до того, що до цих пір

791
00:34:00,740 --> 00:34:02,800
званий хеш-таблицю.

792
00:34:02,800 --> 00:34:05,890
І хеш, а в сторону, що
Я маю на увазі, що індекс

793
00:34:05,890 --> 00:34:07,070
Який я говорив раніше.

794
00:34:07,070 --> 00:34:09,810
Для хеш щось може бути
розглядати як дієслово.

795
00:34:09,810 --> 00:34:13,690
>> Так що якщо ви хеш Аліси ім'я,
хеш-функції, так би мовити,

796
00:34:13,690 --> 00:34:14,710
повинна повертати число.

797
00:34:14,710 --> 00:34:18,199
У цьому випадку дорівнює нулю, якщо вона належить на
нульовому місці, один, якщо вона належить на

798
00:34:18,199 --> 00:34:20,000
місце розташування, і так далі.

799
00:34:20,000 --> 00:34:24,360
Так що мій хеш-функції до цих пір було
супер просто, тільки дивлячись на

800
00:34:24,360 --> 00:34:26,159
Перша буква в чиєсь ім'я.

801
00:34:26,159 --> 00:34:29,090
Але хеш-функція приймає в якості
ввести деякі частини даних,

802
00:34:29,090 --> 00:34:30,210
рядок, ціле всі.

803
00:34:30,210 --> 00:34:32,239
І він випльовує звичайно число.

804
00:34:32,239 --> 00:34:35,739
І це число, де, що дані
елемент належить в структурі даних

805
00:34:35,739 --> 00:34:37,800
відомий тут як хеш-таблицю.

806
00:34:37,800 --> 00:34:41,400
>> Так що просто інтуїтивно, це
дещо іншому контексті.

807
00:34:41,400 --> 00:34:44,170
Це фактично має на увазі приклад
за участю дні народження, де

808
00:34:44,170 --> 00:34:46,850
там може бути стільки, скільки
31 днів у місяці.

809
00:34:46,850 --> 00:34:52,239
Але те, що цій людині вирішити
робити в разі зіткнення?

810
00:34:52,239 --> 00:34:55,304
Контекст в даний час, а не зіткнення
імена, але зіткнення дні народження,

811
00:34:55,304 --> 00:35:00,760
якщо дві людини мають однаковий день народження
2-го жовтня, наприклад.

812
00:35:00,760 --> 00:35:02,120
>> СТУДЕНТ: [нерозбірливо].

813
00:35:02,120 --> 00:35:05,010
>> Виступаючий 1: Так, так що тут ми маємо
більш ефективного використання пов'язаних списків.

814
00:35:05,010 --> 00:35:07,830
Так це виглядає трохи по-іншому
ніж ми звернули її раніше.

815
00:35:07,830 --> 00:35:10,790
Але ми, здається, є в масив
на лівій стороні.

816
00:35:10,790 --> 00:35:13,230
У цьому немає одного індексу, для НЕ
особливої ​​причини.

817
00:35:13,230 --> 00:35:14,630
Але це все ще масиві.

818
00:35:14,630 --> 00:35:16,160
Це масив покажчиків.

819
00:35:16,160 --> 00:35:20,670
І кожен з тих елементів, кожен з
ці кола або коса риса - слеш

820
00:35:20,670 --> 00:35:23,970
представляє нульовий - кожна з цих
покажчиків мабуть, вказують на

821
00:35:23,970 --> 00:35:25,730
які дані структури?

822
00:35:25,730 --> 00:35:26,890
Зв'язаний список.

823
00:35:26,890 --> 00:35:30,530
>> Так що тепер у нас є можливість
жорсткий код у нашій програмі

824
00:35:30,530 --> 00:35:32,010
Розмір таблиці.

825
00:35:32,010 --> 00:35:35,360
У цьому разі, ми знаємо, ніколи немає
більше 31 днів на місяць.

826
00:35:35,360 --> 00:35:38,480
Так жорстке кодування значення, як 31
розумне в цьому контексті.

827
00:35:38,480 --> 00:35:42,700
У контексті імен, жорсткого кодування
26 не є необгрунтованим його людей

828
00:35:42,700 --> 00:35:46,340
тільки імена починаються з, наприклад,
алфавіту з участю до Z.

829
00:35:46,340 --> 00:35:50,180
>> Ми можемо втиснути їх усі в цих даних
Структура поки, коли ми отримуємо

830
00:35:50,180 --> 00:35:55,330
зіткнення, ми не ставимо тут імена,
ми замість цього думати про цих клітинах

831
00:35:55,330 --> 00:36:00,270
а не як рядки себе, але в якості
покажчиків, наприклад, Еліс.

832
00:36:00,270 --> 00:36:03,660
І тоді Аліса може мати інший покажчик
в інше ім'я, що починається з

833
00:36:03,660 --> 00:36:06,150
А. і Боб насправді йде сюди.

834
00:36:06,150 --> 00:36:10,850
>> І, якщо є інший ім'я, що починається
з В, він закінчується тут.

835
00:36:10,850 --> 00:36:15,070
І тому кожен з елементів цієї
Таблиця два, якщо ми розробили цю

836
00:36:15,070 --> 00:36:17,350
трохи розумніший -

837
00:36:17,350 --> 00:36:18,125
Давай, -

838
00:36:18,125 --> 00:36:22,950
якщо ми розробили це трохи більше
розумніші, тепер стає адаптивен

839
00:36:22,950 --> 00:36:27,720
структура, в якій немає жорсткого обмеження
від того, скільки елементів ви можете вставити

840
00:36:27,720 --> 00:36:30,700
в це, тому що якщо у вас є
зіткнення, це нормально.

841
00:36:30,700 --> 00:36:34,690
Просто йти вперед і додати його в
що ми бачили трохи назад було

842
00:36:34,690 --> 00:36:38,290
відомий як зв'язаний список.

843
00:36:38,290 --> 00:36:39,690
>> Ну давайте паузу на мить.

844
00:36:39,690 --> 00:36:42,570
Яка ймовірність зіткнення
в першу чергу?

845
00:36:42,570 --> 00:36:45,480
Право, може бути, я по думав, може бути,
Я на інженерних цю проблему,

846
00:36:45,480 --> 00:36:46,370
тому що ви знаєте, що?

847
00:36:46,370 --> 00:36:49,070
Так, я можу придумати довільне
Приклади з верхньої частини моєї голови, як

848
00:36:49,070 --> 00:36:52,870
Allison і Аарона, але насправді,
задано рівномірний розподіл

849
00:36:52,870 --> 00:36:56,990
входів, тобто деякі випадкові вставки
в структуру даних, що насправді

850
00:36:56,990 --> 00:36:58,580
Ймовірність зіткнення?

851
00:36:58,580 --> 00:37:01,670
Добре виходить, це насправді
супер високою.

852
00:37:01,670 --> 00:37:03,850
Дозвольте мені узагальнити цю
Проблема, як цей.

853
00:37:03,850 --> 00:37:08,890
>> Таким чином, в кімнаті N CS50 студентів, що
ймовірність того, що принаймні

854
00:37:08,890 --> 00:37:11,010
Два студенти в кімнаті
мають однаковий день народження?

855
00:37:11,010 --> 00:37:13,346
Так що є що. Кілька Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 людей тут і кілька
сотні людей у ​​себе вдома сьогодні.

857
00:37:16,790 --> 00:37:20,670
Так що якщо ви хотіли запитати себе, що це
ймовірність дві людини

858
00:37:20,670 --> 00:37:23,930
У цьому номері, що має той же день народження,
ми можемо зрозуміти це.

859
00:37:23,930 --> 00:37:26,250
І я стверджую, насправді є два
людей з такими ж день народження.

860
00:37:26,250 --> 00:37:29,560
>> Наприклад, хто-небудь
мають сьогодні день народження?

861
00:37:29,560 --> 00:37:31,340
Вчора?

862
00:37:31,340 --> 00:37:32,590
Завтра?

863
00:37:32,590 --> 00:37:35,980
Все в порядку, тому він відчуває себе, як я збираюся
щоб зробити це 363 або близько того більше

864
00:37:35,980 --> 00:37:39,500
раз насправді з'ясувати,
Якщо у нас є зіткнення.

865
00:37:39,500 --> 00:37:42,350
Або ми могли б просто зробити це математично
а не втомлює

866
00:37:42,350 --> 00:37:43,200
робити це.

867
00:37:43,200 --> 00:37:44,500
І пропоную наступне.

868
00:37:44,500 --> 00:37:48,740
>> Тому я пропоную, щоб ми могли моделювати
Ймовірність двох людей з

869
00:37:48,740 --> 00:37:55,320
ж день народження, як і ймовірність 1
мінус ймовірність не має

870
00:37:55,320 --> 00:37:56,290
Того ж дня народження.

871
00:37:56,290 --> 00:37:59,960
Таким чином, щоб отримати це, і це тільки
химерний спосіб написання цього, для

872
00:37:59,960 --> 00:38:03,090
Перший чоловік у кімнаті, він або вона
може мати будь-яку одну з можливих

873
00:38:03,090 --> 00:38:07,370
Дні народження припускаючи, 365 днів у році,
з вибаченнями для осіб з

874
00:38:07,370 --> 00:38:08,760
Лютнева 29 років.

875
00:38:08,760 --> 00:38:13,470
>> Таким чином, перша людина в цьому номері безкоштовний
мати будь-яку кількість народжень

876
00:38:13,470 --> 00:38:18,280
з 365 можливостей так, щоб
ми зробимо це 365 розділити на 365,

877
00:38:18,280 --> 00:38:18,990
який є одним.

878
00:38:18,990 --> 00:38:22,700
Наступний чоловік у кімнаті, якщо мета
, Щоб уникнути зіткнення, можна тільки

879
00:38:22,700 --> 00:38:26,460
його або її день народження про те, як
багато різних можливих днів?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Таким чином, другий доданок в цьому виразі
по суті роблять, що математика для нас

882
00:38:31,430 --> 00:38:33,460
шляхом вирахування від одного можливий день.

883
00:38:33,460 --> 00:38:36,390
А потім на наступний день, на наступний день,
на наступний день до загальної кількості

884
00:38:36,390 --> 00:38:38,100
людей у ​​кімнаті.

885
00:38:38,100 --> 00:38:41,290
>> І якщо ми, то розглянемо, що ж тоді є
ймовірність не кожен має

886
00:38:41,290 --> 00:38:45,265
унікальні дні народження, але знову ж мінус 1
що, що ми отримуємо вираз

887
00:38:45,265 --> 00:38:47,810
, Що може дуже химерно
виглядати наступним чином.

888
00:38:47,810 --> 00:38:50,330
Але це більш цікаво
дивитися на візуально.

889
00:38:50,330 --> 00:38:55,120
Це графік, де по осі абсцис являє
Кількість осіб в кімнаті,

890
00:38:55,120 --> 00:38:56,180
кількість народжень.

891
00:38:56,180 --> 00:38:59,840
На осі ординат ймовірність
зіткнення, дві людини

892
00:38:59,840 --> 00:39:01,230
що мають той же день народження.

893
00:39:01,230 --> 00:39:05,020
>> І їжу додому від цієї кривої
що, як тільки ви отримаєте як 40

894
00:39:05,020 --> 00:39:11,110
студенти, твоя черга на 90% ймовірності
комбінаторно двох

895
00:39:11,110 --> 00:39:13,550
чоловік або більше має
Того ж день народження.

896
00:39:13,550 --> 00:39:18,600
І як тільки ви отримаєте 58 людина подобається це
майже 100% шанс двох

897
00:39:18,600 --> 00:39:21,310
людей у ​​кімнаті збираються мати
ж дня народження, хоча є

898
00:39:21,310 --> 00:39:26,650
365 або 366 можливих відра, і
Тільки 58 осіб у кімнаті.

899
00:39:26,650 --> 00:39:29,900
Просто статистично ви, ймовірно,
отримати зіткнень, яка в короткі

900
00:39:29,900 --> 00:39:31,810
мотивує це обговорення.

901
00:39:31,810 --> 00:39:35,890
Що навіть якщо ми отримати фантазії тут, і
почати з цих ланцюгів, ми все ще

902
00:39:35,890 --> 00:39:36,950
доведеться зіткнень.

903
00:39:36,950 --> 00:39:42,710
>> Тож виникає питання, що таке
витрати на ведення операції вставки і видалення

904
00:39:42,710 --> 00:39:44,850
в структуру даних, як це?

905
00:39:44,850 --> 00:39:46,630
Ну дозвольте мені запропонувати -

906
00:39:46,630 --> 00:39:51,570
і дозвольте мені повернутися до екрану над
тут - якщо ми п елементів у

907
00:39:51,570 --> 00:39:56,330
список, так що якщо ми намагаємося вкласти
N елементів, і у нас є

908
00:39:56,330 --> 00:39:58,050
скільки всього відра?

909
00:39:58,050 --> 00:40:03,450
Скажімо, 31 всього відра
у разі народження.

910
00:40:03,450 --> 00:40:09,240
Яка максимальна довжина одного
цих ланцюгів потенційно?

911
00:40:09,240 --> 00:40:12,670
>> Якщо знову є 31 можливих
Дні народження в цьому місяці.

912
00:40:12,670 --> 00:40:14,580
Але ж це тільки злипання всіх -

913
00:40:14,580 --> 00:40:15,580
насправді це дурний приклад.

914
00:40:15,580 --> 00:40:16,960
Давайте робити, а не 26.

915
00:40:16,960 --> 00:40:20,890
Так що, якщо насправді є люди, чиї імена
Почніть з через Z, тим самим даючи

916
00:40:20,890 --> 00:40:22,780
нам 26 можливостей.

917
00:40:22,780 --> 00:40:25,920
І ми, використовуючи структуру даних, як
той, який ми тільки що бачили, в результаті чого ми маємо

918
00:40:25,920 --> 00:40:30,210
масив покажчиків, кожен з яких
вказує на зв'язаний список, де

919
00:40:30,210 --> 00:40:32,360
Перший список всі
з ім'ям Еліс.

920
00:40:32,360 --> 00:40:35,770
Другий список з кожним
ім'я, що починається з, починаючи

921
00:40:35,770 --> 00:40:36,980
з В, і так далі.

922
00:40:36,980 --> 00:40:41,020
>> Яка імовірність довжина кожного з
ці списки, якщо припустити, хороший чистий

923
00:40:41,020 --> 00:40:45,410
Розподіл імен через Z
по всій структурі даних?

924
00:40:45,410 --> 00:40:50,210
Там у російських людей в структурі даних
поділене на 26, якщо вони красиво

925
00:40:50,210 --> 00:40:52,110
поширитися по всій
структурі даних.

926
00:40:52,110 --> 00:40:54,970
Таким чином, довжина кожного з цих
ланцюгів п поділене на +26.

927
00:40:54,970 --> 00:40:57,380
Але у великих позначення О, що це?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Що це насправді?

930
00:41:02,440 --> 00:41:04,150
Так що це дійсно просто п, чи не так?

931
00:41:04,150 --> 00:41:06,620
Тому що ми говорили в минулому,
тьфу, що ви розділите на 26.

932
00:41:06,620 --> 00:41:08,710
Та, насправді це швидше.

933
00:41:08,710 --> 00:41:12,720
Але в теорії, це не принципово
все, що швидше.

934
00:41:12,720 --> 00:41:16,040
>> Таким чином, ми, здається, не так вже й багато
ближче до цієї Святий Грааль.

935
00:41:16,040 --> 00:41:17,750
Насправді, це всього лише лінійний час.

936
00:41:17,750 --> 00:41:20,790
Чорт візьми, в цей момент, чому б нам не
Додайте один величезний зв'язаний список?

937
00:41:20,790 --> 00:41:23,510
Чому б нам не використовувати тільки один величезний
масив для зберігання імен

938
00:41:23,510 --> 00:41:25,010
все в кімнаті?

939
00:41:25,010 --> 00:41:28,280
Ну, є ще щось
переконливим про хеш-таблиці?

940
00:41:28,280 --> 00:41:30,810
Чи є ще щось переконливих
про структуру даних

941
00:41:30,810 --> 00:41:33,940
, Який виглядає, як це?

942
00:41:33,940 --> 00:41:35,182
Це.

943
00:41:35,182 --> 00:41:37,050
>> СТУДЕНТ: [нерозбірливо].

944
00:41:37,050 --> 00:41:39,840
>> Виступаючий 1: Так, і ще раз, якщо це просто
лінійний алгоритм часу і

945
00:41:39,840 --> 00:41:42,780
лінійний час структура даних, чому б мені не
просто зберігати ім'я кожного у великій

946
00:41:42,780 --> 00:41:44,210
масиві або у великому зв'язаний список?

947
00:41:44,210 --> 00:41:47,010
І припиніть робити CS набагато важче
, Чим вона повинна бути?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Що є переконливим з цього приводу, навіть
хоча я подряпав його?

950
00:41:53,190 --> 00:41:54,930
>> СТУДЕНТ: [нерозбірливо].

951
00:41:54,930 --> 00:41:57,040
>> Виступаючий 1: замовникові не?

952
00:41:57,040 --> 00:41:58,140
Дорогі більша.

953
00:41:58,140 --> 00:42:03,390
Так вставками потенційно могли ще
постійної часу, навіть якщо ваші дані

954
00:42:03,390 --> 00:42:07,910
структура виглядає таким чином, масив
покажчиків, кожен з яких вказує на

955
00:42:07,910 --> 00:42:09,550
потенційно зв'язаний список.

956
00:42:09,550 --> 00:42:15,220
Як ви могли б досягти постійної
Час введення імена?

957
00:42:15,220 --> 00:42:16,280
Приклейте наклейку на фронті, чи не так?

958
00:42:16,280 --> 00:42:19,290
>> Якщо ми жертвуємо дизайн гол
раніше, де ми хотіли зберегти

959
00:42:19,290 --> 00:42:22,650
всіх по іменах, наприклад, сортують,
або всі цифри на етапі відсортовані,

960
00:42:22,650 --> 00:42:25,020
Припустимо, що у нас є
несортоване зв'язаний список.

961
00:42:25,020 --> 00:42:29,960
Це тільки варто нам один або два етапи,
Як і у випадку з Беном і Брайан

962
00:42:29,960 --> 00:42:32,750
раніше, вставити елемент у
початку списку.

963
00:42:32,750 --> 00:42:36,090
Так що, якщо ми не дбаємо про сортування всі
з імен, починаючи з або всі

964
00:42:36,090 --> 00:42:39,660
імена, що починаються з B, ми все ще можемо
досягнення постійної час вставки.

965
00:42:39,660 --> 00:42:43,900
Тепер дивлячись Аліси або Боба чи будь-яке ім'я
в цілому все ще що?

966
00:42:43,900 --> 00:42:48,100
Це велике О від N поділене на 26, в
ідеальному випадку, коли все це рівномірно

967
00:42:48,100 --> 00:42:51,190
розподілені, де є стільки учасника
як є Z, який, ймовірно,

968
00:42:51,190 --> 00:42:52,220
нереально.

969
00:42:52,220 --> 00:42:53,880
Але це як і раніше лінійно.

970
00:42:53,880 --> 00:42:57,120
>> Але і тут ми повертаємося до точки
асимптотичної позначення буття

971
00:42:57,120 --> 00:42:58,600
Теоретично вірно.

972
00:42:58,600 --> 00:43:02,960
Але в реальному світі, якщо я стверджую, що
моя програма може зробити щось 26 разів

973
00:43:02,960 --> 00:43:06,210
швидше, ніж ваша, чия програма
Ви збираєтеся віддаєте перевагу використовувати?

974
00:43:06,210 --> 00:43:09,660
Ваша або моя, яка
в 26 разів швидше?

975
00:43:09,660 --> 00:43:14,320
Реально, особи, становить 26
рази швидше, навіть якщо теоретично

976
00:43:14,320 --> 00:43:18,790
наші алгоритми працюють у тому ж
асимптотическое час.

977
00:43:18,790 --> 00:43:20,940
>> Дозвольте мені запропонувати іншу
Рішення в цілому.

978
00:43:20,940 --> 00:43:24,380
І якщо цього не уб'є вас наповал,
ми зі структур даних.

979
00:43:24,380 --> 00:43:27,420
Так це він, синтаксичного дерева -

980
00:43:27,420 --> 00:43:28,520
вид дурне ім'я.

981
00:43:28,520 --> 00:43:32,880
Воно походить від витягів і слово
пишеться синтаксичного дерева, т-р-і-е, через

982
00:43:32,880 --> 00:43:34,450
Звичайно пошуку звучить як синтаксичного дерева.

983
00:43:34,450 --> 00:43:36,580
Але це історія
слова синтаксичного дерева.

984
00:43:36,580 --> 00:43:40,980
>> Так синтаксичного дерева дійсно свого роду дерево,
і це також гра на це слово.

985
00:43:40,980 --> 00:43:46,330
І хоча ви не можете досить побачити його
з цією візуалізації, синтаксичного дерева є

986
00:43:46,330 --> 00:43:50,790
дерева структуровані, як сім'я дерево з
одним предком нагорі і багато

987
00:43:50,790 --> 00:43:54,530
з онуків і правнуків
як залишає на дні.

988
00:43:54,530 --> 00:43:58,100
Але кожному вузлу у вигляді дерева є масивом.

989
00:43:58,100 --> 00:44:00,680
І це в масиві - і давай
спрощувати на мить - це

990
00:44:00,680 --> 00:44:04,600
масив, в цьому випадку, розмір 26, де
кожен вузол знову масив розміру

991
00:44:04,600 --> 00:44:09,000
26, де нульовий елемент в цьому
Масив являє, а останній

992
00:44:09,000 --> 00:44:11,810
елемент в кожному такому
Масив являє Z.

993
00:44:11,810 --> 00:44:15,520
>> Так що я пропоную, те, що ці дані
структурі, відомої як вигляді дерева, може бути

994
00:44:15,520 --> 00:44:17,600
використовуватися також для зберігання слів.

995
00:44:17,600 --> 00:44:21,740
Ми бачили, як хвилину тому, ми могли зберегти
словами, або в даному випадку імена, і ми

996
00:44:21,740 --> 00:44:25,440
бачили раніше, як ми можемо зберігати числа,
але якщо ми орієнтуємося на імена або рядка

997
00:44:25,440 --> 00:44:27,460
зауважте, що цікаво.

998
00:44:27,460 --> 00:44:32,210
Я стверджую, що ім'я Максвелла
Всередині цієї структури даних.

999
00:44:32,210 --> 00:44:33,730
Де ви бачите Максвелла?

1000
00:44:33,730 --> 00:44:35,140
>> СТУДЕНТ: [нерозбірливо].

1001
00:44:35,140 --> 00:44:36,240
>> Виступаючий 1: на лівій стороні.

1002
00:44:36,240 --> 00:44:39,910
Так що цікаво, з цими даними
структура, а не магазин

1003
00:44:39,910 --> 00:44:46,200
Рядок M-A-X-W-E-L-L зворотного косою риси нулю, всі
безперервно, а не те, що ви робите

1004
00:44:46,200 --> 00:44:46,890
полягає в наступному.

1005
00:44:46,890 --> 00:44:50,510
Якщо це так синтаксичного дерева структури даних,
кожен з яких вузлів знову масиву

1006
00:44:50,510 --> 00:44:54,650
і ви хочете зберегти Максвелла, спочатку
індекс і так кореня вузла, так що

1007
00:44:54,650 --> 00:44:57,810
сказати, верхній вузол,
в положенні М, вправо, так

1008
00:44:57,810 --> 00:44:59,160
приблизно в середині.

1009
00:44:59,160 --> 00:45:03,740
, А потім звідти, ви будете слідувати
покажчика на дочірні вузли, так би мовити.

1010
00:45:03,740 --> 00:45:06,150
Таким чином, в тому сенсі, дерево родини,
ви будете слідувати його вниз.

1011
00:45:06,150 --> 00:45:09,030
І це приведе вас до іншого вузла
На лівій стороні, яка є

1012
00:45:09,030 --> 00:45:10,540
просто ще один масив.

1013
00:45:10,540 --> 00:45:14,710
>> І потім, якщо ви хочете зберегти Максвелл,
ви знайдете вказівник, який представляє

1014
00:45:14,710 --> 00:45:16,430
, Яка є цей тут.

1015
00:45:16,430 --> 00:45:17,840
Тоді ви йдете до наступного вузла.

1016
00:45:17,840 --> 00:45:20,100
І зверніть увагу - саме тому картини
трохи обманює -

1017
00:45:20,100 --> 00:45:21,990
цей вузол виглядати супер крихітні.

1018
00:45:21,990 --> 00:45:26,050
Але право це Y і Z.
Це просто автор усіченої

1019
00:45:26,050 --> 00:45:27,630
знімок так, щоб ви насправді
бачити речі.

1020
00:45:27,630 --> 00:45:30,400
В іншому випадку це фото
б надзвичайно широкий.

1021
00:45:30,400 --> 00:45:36,180
Отже, тепер ви індексу в клітинку X, то
W, то Е, то L, то L. Тоді в чому

1022
00:45:36,180 --> 00:45:37,380
це цікавість?

1023
00:45:37,380 --> 00:45:41,250
>> Ну, якщо ми використовуємо цей вид нових
взяти на себе, як зберігати рядок у

1024
00:45:41,250 --> 00:45:44,500
структури даних, вам все одно доведеться
істотно галочку в даних

1025
00:45:44,500 --> 00:45:47,250
структури, що слово закінчується.

1026
00:45:47,250 --> 00:45:50,830
Іншими словами, кожен з цих вузлів
однак потрібно пам'ятати, що ми

1027
00:45:50,830 --> 00:45:53,500
фактично виконали всі ці покажчики
і виїжджають трохи

1028
00:45:53,500 --> 00:45:58,370
хлібних крихт на дні тут цього
Структура, щоб вказати, M-A-X-W-E-L-L являє

1029
00:45:58,370 --> 00:46:00,230
дійсно, в цій структурі даних.

1030
00:46:00,230 --> 00:46:02,040
>> Таким чином, можна зробити наступним чином.

1031
00:46:02,040 --> 00:46:06,810
Кожен з вузлів на зображенні ми просто
пила має один, масив розміром 27.

1032
00:46:06,810 --> 00:46:10,550
І це зараз 27, тому що в P встановити шість,
ми фактично дають вам апостроф,

1033
00:46:10,550 --> 00:46:13,590
щоб ми могли матиме імена, як O'Reilly
та інші з апострофа.

1034
00:46:13,590 --> 00:46:14,820
Але та ж ідея.

1035
00:46:14,820 --> 00:46:17,710
Кожен з цих елементів у
масиву вказує на структуру

1036
00:46:17,710 --> 00:46:19,320
вузол, так що просто вузлом.

1037
00:46:19,320 --> 00:46:21,430
Так що це дуже нагадує
нашої пов'язаного списку.

1038
00:46:21,430 --> 00:46:24,550
>> А то у мене логічне, який я
називаю слово, яке просто буде

1039
00:46:24,550 --> 00:46:29,120
вірно, якщо слово закінчується на цьому
вузол в дереві.

1040
00:46:29,120 --> 00:46:32,870
Це по суті, є трохи
трикутника ми бачили кілька хвилин тому.

1041
00:46:32,870 --> 00:46:37,190
Так що, якщо слово закінчується в цьому вузлі в
Дерево, це слово поле буде правдою,

1042
00:46:37,190 --> 00:46:41,990
який концептуально галочки, або
ми малюємо цей трикутник, та там

1043
00:46:41,990 --> 00:46:44,080
це слово тут.

1044
00:46:44,080 --> 00:46:45,120
>> Так що це синтаксичного дерева.

1045
00:46:45,120 --> 00:46:48,540
А тепер питання в тому, що
є час його роботи?

1046
00:46:48,540 --> 00:46:49,930
Він великий O п?

1047
00:46:49,930 --> 00:46:51,410
Це щось ще?

1048
00:46:51,410 --> 00:46:57,330
Ну, якщо ви п імена в цих даних
Структура, Максвелл всього лише один з

1049
00:46:57,330 --> 00:47:02,330
них, що час роботи
вставки або знайти Максвелла?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Що час роботи
вставки Максвелла?

1052
00:47:09,050 --> 00:47:11,740
Якщо є інші назви N
вже в таблиці?

1053
00:47:11,740 --> 00:47:12,507
Так?

1054
00:47:12,507 --> 00:47:15,429
>> СТУДЕНТ: [нерозбірливо].

1055
00:47:15,429 --> 00:47:17,550
>> Виступаючий 1: Так, це довжина
імені, чи не так?

1056
00:47:17,550 --> 00:47:24,420
Так М-а-х-З-е-л-л тому він відчуває себе, як це
Алгоритм Big O семи.

1057
00:47:24,420 --> 00:47:26,580
Тепер, звичайно, ім'я
буде змінюватись в довжину.

1058
00:47:26,580 --> 00:47:27,380
Може бути, це коротке ім'я.

1059
00:47:27,380 --> 00:47:28,600
Може бути, це довге ім'я.

1060
00:47:28,600 --> 00:47:33,390
Але те, що ключовим тут є те, що
це постійне число.

1061
00:47:33,390 --> 00:47:36,810
А може бути, це не зовсім постійну,
але Бог, якщо реально, в

1062
00:47:36,810 --> 00:47:41,570
словник, там, напевно, певний межа
на кількість літер у

1063
00:47:41,570 --> 00:47:43,820
ім'я людини в конкретній країні.

1064
00:47:43,820 --> 00:47:46,940
>> І таким чином, ми можемо припустити, що
значення є постійним.

1065
00:47:46,940 --> 00:47:47,750
Я не знаю, що це таке.

1066
00:47:47,750 --> 00:47:50,440
Це, напевно, більше, ніж
ми думаємо, що це таке.

1067
00:47:50,440 --> 00:47:52,720
Тому що завжди є який-небудь кут
випадку з божевільним довге ім'я.

1068
00:47:52,720 --> 00:47:56,360
Так що давайте називати це К, але вона як і раніше
постійна імовірно, тому що кожен

1069
00:47:56,360 --> 00:48:00,190
назвати у світі, принаймні
конкретної країни, є те, що довжина або

1070
00:48:00,190 --> 00:48:01,780
коротше, так що це постійно.

1071
00:48:01,780 --> 00:48:04,490
Але коли ми сказали щось велике
O постійного значення, що це таке

1072
00:48:04,490 --> 00:48:07,760
дійсно еквівалентні?

1073
00:48:07,760 --> 00:48:10,420
Це дійсно один і той же
як кажуть постійний час.

1074
00:48:10,420 --> 00:48:11,530
>> Зараз ми начебто обману, вірно?

1075
00:48:11,530 --> 00:48:15,340
Ми начебто використовуючи деякі теорії
тут, щоб сказати, що добре, порядку До

1076
00:48:15,340 --> 00:48:17,450
дійсно тільки близько однієї,
і це постійний час.

1077
00:48:17,450 --> 00:48:18,200
Але це насправді.

1078
00:48:18,200 --> 00:48:22,550
Оскільки ключове розуміння в тому, що
якщо ми маємо п імена вже в цьому

1079
00:48:22,550 --> 00:48:26,010
структуру даних, і ми вставляємо Максвелл,
це кількість часу, який потрібен нам

1080
00:48:26,010 --> 00:48:29,530
вставити Максвелла на всіх постраждалих
по тому, як багато інших людей

1081
00:48:29,530 --> 00:48:31,100
в структурі даних?

1082
00:48:31,100 --> 00:48:31,670
Чи не схоже, щоб бути.

1083
00:48:31,670 --> 00:48:36,280
Якби я був мільярд більше елементів в цій
дерева, а потім вставити Максвеллом

1084
00:48:36,280 --> 00:48:38,650
Він на всіх постраждалих?

1085
00:48:38,650 --> 00:48:39,050
Ні.

1086
00:48:39,050 --> 00:48:42,950
І це на відміну від будь-якого дня дані
структур, які ми бачили дотепер, де

1087
00:48:42,950 --> 00:48:46,820
час роботи вашого алгоритму
абсолютно не залежить від того, скільки

1088
00:48:46,820 --> 00:48:51,430
матеріал або ще не був
У цій структурі даних.

1089
00:48:51,430 --> 00:48:54,650
>> І так з цим дає вам зараз
можливість встановити шість р, яка буде

1090
00:48:54,650 --> 00:48:58,310
знову пов'язано із здійсненням власного
перевірка орфографії, читання в 150 000

1091
00:48:58,310 --> 00:49:01,050
словами, як краще зберегти цю
не обов'язково є очевидним.

1092
00:49:01,050 --> 00:49:04,030
І хоча я прагнув знайти
Святий Грааль, я не

1093
00:49:04,030 --> 00:49:05,330
стверджують, що це синтаксичного дерева.

1094
00:49:05,330 --> 00:49:09,810
Справді, Хеш-таблицю можна дуже добре
виявитися набагато більш ефективним.

1095
00:49:09,810 --> 00:49:10,830
Але це тільки -

1096
00:49:10,830 --> 00:49:14,620
це тільки одна з проектних рішень
Ви повинні зробити.

1097
00:49:14,620 --> 00:49:18,920
>> Але на закінчення давайте 50 або близько того
секунди, щоб поглянути на те, що лежить

1098
00:49:18,920 --> 00:49:22,190
попереду на наступному тижні і далі ми переходимо
з цієї командного рядка

1099
00:49:22,190 --> 00:49:26,220
З миром, якщо на веб-програми речей
заснований і мов, як PHP і

1100
00:49:26,220 --> 00:49:30,350
JavaScript і сам Інтернет,
протоколів, таких як HTTP, які у вас є

1101
00:49:30,350 --> 00:49:32,870
само собою зрозумілим, протягом багатьох років
зараз, і кожен набрав більше

1102
00:49:32,870 --> 00:49:34,440
день, мабуть, і не бачив.

1103
00:49:34,440 --> 00:49:37,420
І ми почнемо відігніть
шарах Що таке Інтернет.

1104
00:49:37,420 --> 00:49:40,650
А що це за код, який
лежить в основі сьогоднішньої інструментів.

1105
00:49:40,650 --> 00:49:43,230
Так 50 секунд Цього тизер тут.

1106
00:49:43,230 --> 00:49:46,570
Я даю вам Воїни Мережі.

1107
00:49:46,570 --> 00:49:51,370
>> [ВІДТВОРЕННЯ ВІДЕО]

1108
00:49:51,370 --> 00:49:56,764
>> -Він прийшов із повідомленням.

1109
00:49:56,764 --> 00:50:00,687
З протоколом все своє.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Він прийшов у світ жорстоких брандмауерів,
байдужими маршрутизатори, і небезпеки далеко

1112
00:50:19,780 --> 00:50:22,600
гірше, ніж смерть.

1113
00:50:22,600 --> 00:50:23,590
Він швидкий.

1114
00:50:23,590 --> 00:50:25,300
Він сильний.

1115
00:50:25,300 --> 00:50:27,700
Він TCPIP.

1116
00:50:27,700 --> 00:50:30,420
І у нього є вашу адресу.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Воїни в Мережі.

1119
00:50:34,590 --> 00:50:35,290
>> [КІНЕЦЬ відеовідтворення]

1120
00:50:35,290 --> 00:50:38,070
>> Виступаючий 1: Тобто, як в інтернеті
будемо працювати наступного тижня.

1121
00:50:38,070 --> 00:50:40,406