1
00:00:00,000 --> 00:00:08,250

2
00:00:08,250 --> 00:00:12,680
>> Джейсон Хіршхорна: Вітаю всіх
в розділі Seven.

3
00:00:12,680 --> 00:00:15,040
Ми знаходимося в тиждень сім курсу.

4
00:00:15,040 --> 00:00:18,440
І майбутній четвер
Хеллоуїн, так що я

5
00:00:18,440 --> 00:00:21,420
одягнені як гарбуз.

6
00:00:21,420 --> 00:00:23,460
Я не міг нахилитися і покласти на
мої черевики, так ось чому я

7
00:00:23,460 --> 00:00:25,660
просто носити шкарпетки.

8
00:00:25,660 --> 00:00:29,220
Я також нічого не носити під
це, тому я не можу зняти його, якщо це

9
00:00:29,220 --> 00:00:29,950
відволікаючи до вас.

10
00:00:29,950 --> 00:00:31,860
Заздалегідь прошу вибачення за це.

11
00:00:31,860 --> 00:00:33,170
Вам не потрібно представити
що відбувається.

12
00:00:33,170 --> 00:00:34,240
Я ношу боксерів.

13
00:00:34,240 --> 00:00:36,170
Так що все добре.

14
00:00:36,170 --> 00:00:41,120
>> У мене є довгий розповідь про те, чому я
одягнений як гарбуза, але я збираюся

15
00:00:41,120 --> 00:00:45,110
крім того, що пізніше в цьому розділі
тому що я хочу, щоб почати роботу.

16
00:00:45,110 --> 00:00:47,720
У нас є багато цікавих речей,
перейти на цьому тижні.

17
00:00:47,720 --> 00:00:51,810
Більшість з них мають безпосереднє відношення до цього
тижня проблема набір, друкарськими помилками.

18
00:00:51,810 --> 00:00:54,680
Ми збираємося йти по пов'язані
списки та хеш-таблиці

19
00:00:54,680 --> 00:00:57,160
для всієї секції.

20
00:00:57,160 --> 00:01:02,490
Я поклав цей список щотижня, список
ресурси для вас, щоб допомогти вам

21
00:01:02,490 --> 00:01:04,120
матеріал на цьому курсі.

22
00:01:04,120 --> 00:01:07,600
Якщо у збиток або якщо заводжуся
більше інформації, перевірити один з

23
00:01:07,600 --> 00:01:09,930
ці ресурси.

24
00:01:09,930 --> 00:01:14,530
>> Знову ж, pset6 є друкарськими помилками,
PSET на цьому тижні.

25
00:01:14,530 --> 00:01:17,690
І це також закликає вас, і я
рекомендуємо вам, щоб використовувати деякі інші

26
00:01:17,690 --> 00:01:20,320
ресурси спеціально для цієї PSet.

27
00:01:20,320 --> 00:01:23,390
Зокрема, три у мене є
перераховані на екрані -

28
00:01:23,390 --> 00:01:27,160
GDB, який ми були знайомі з
і використовували на деякий час тепер, є

29
00:01:27,160 --> 00:01:29,270
буде дуже корисно на цьому тижні.

30
00:01:29,270 --> 00:01:30,190
Так що я поклав, що тут.

31
00:01:30,190 --> 00:01:32,910
Але всякий раз, коли ви працюєте з C,
ви завжди повинні використовувати GDB для

32
00:01:32,910 --> 00:01:34,430
налагодження програм.

33
00:01:34,430 --> 00:01:36,660
На цьому тижні також Valgrind.

34
00:01:36,660 --> 00:01:38,535
Хто-небудь знає, що Valgrind робить?

35
00:01:38,535 --> 00:01:42,184

36
00:01:42,184 --> 00:01:43,890
>> АУДИТОРІЯ: Він перевіряє витоків пам'яті?

37
00:01:43,890 --> 00:01:45,950
>> Джейсон Хіршхорна: Valgrind
перевіряє витоку пам'яті.

38
00:01:45,950 --> 00:01:49,970
Так що якщо ви Танос щось у вашому
Програма, ви просите пам'яті.

39
00:01:49,970 --> 00:01:52,920
Наприкінці програми, у вас є
написати безкоштовно на все, що ви

40
00:01:52,920 --> 00:01:54,800
malloced дати пам'ять назад.

41
00:01:54,800 --> 00:01:58,420
Якщо ви не пишете безкоштовно в кінці і
ваша програма приходить до висновку,

42
00:01:58,420 --> 00:02:00,000
все автоматично
бути звільнені.

43
00:02:00,000 --> 00:02:02,340
А для невеликих програм, це
не так вже страшно.

44
00:02:02,340 --> 00:02:05,250
Але якщо ви пишете довгий хід
програма, що не вийде,

45
00:02:05,250 --> 00:02:09,180
обов'язково, протягом декількох хвилин або
пару секунд, потім витоку пам'яті

46
00:02:09,180 --> 00:02:10,710
може стати величезна угода.

47
00:02:10,710 --> 00:02:14,940
>> Таким чином, для pset6, очікується, що
ви будете мати витоків нульові пам'яті з

48
00:02:14,940 --> 00:02:15,910
ваша програма.

49
00:02:15,910 --> 00:02:18,690
Для перевірки витоку пам'яті, запустіть Valgrind
і вона буде давати вам деякі цікаві

50
00:02:18,690 --> 00:02:21,190
Вихід даючи вам знати чи
або не все було безкоштовно.

51
00:02:21,190 --> 00:02:23,940
Ми будемо практикувати з цим пізніше
сьогодні, з надією.

52
00:02:23,940 --> 00:02:25,790
>> Нарешті, команда різн ..

53
00:02:25,790 --> 00:02:28,900
Ви щось схоже на нього використовується
в pset5 з інструментом швидкого погляду.

54
00:02:28,900 --> 00:02:30,780
Дозволено вам заглянути всередину.

55
00:02:30,780 --> 00:02:33,400
Ви також використовується диференціал теж за
проблема встановити спец.

56
00:02:33,400 --> 00:02:35,950
Але в дозволив вам
порівняння двох файлів.

57
00:02:35,950 --> 00:02:39,180
Ви можете порівняти файл растрового зображення і
Інформація заголовки розчину персоналу та

58
00:02:39,180 --> 00:02:42,200
Ваше рішення в pset5 якщо
ви вирішили використовувати його.

59
00:02:42,200 --> 00:02:44,030
Різниця дозволить вам
зробити це, а також.

60
00:02:44,030 --> 00:02:48,620
Ви можете порівняти правильну відповідь для
Проблема цьому тижні встановити на свій відповідь

61
00:02:48,620 --> 00:02:52,210
і подивитися, якщо він вибудовується в лінію або см.
де помилки.

62
00:02:52,210 --> 00:02:55,870
>> Отже, це три хороших інструментів, які
Ви повинні використовувати протягом цього тижня, і

63
00:02:55,870 --> 00:02:58,130
обов'язково перевірити вашу програму
з цими трьома інструментами

64
00:02:58,130 --> 00:03:00,520
перед включенням його дюйма

65
00:03:00,520 --> 00:03:04,650
Знову ж, як я вже згадував щотижня,
якщо у вас є зворотній зв'язок для мене - як

66
00:03:04,650 --> 00:03:06,470
позитивним і конструктивним -

67
00:03:06,470 --> 00:03:09,930
не соромтеся, щоб очолити на сайт
в нижній частині цього слайда

68
00:03:09,930 --> 00:03:11,270
і ввести його там.

69
00:03:11,270 --> 00:03:13,440
Я дуже ціную будь
і все із зворотним зв'язком.

70
00:03:13,440 --> 00:03:17,360
І якщо ви дасте мені конкретні речі, які
Що я можу зробити, щоб поліпшити або, що я

71
00:03:17,360 --> 00:03:21,350
все добре, що ви хотіли, щоб я
продовжити, я беру це близько до серця і

72
00:03:21,350 --> 00:03:24,040
дійсно дуже стараються слухати
ваші відгуки.

73
00:03:24,040 --> 00:03:27,720
Я не можу пообіцяти, що я збираюся зробити
все, хоча, як носити

74
00:03:27,720 --> 00:03:30,700
гарбуз костюм щотижня.

75
00:03:30,700 --> 00:03:34,020
>> Отже, ми збираємося провести більшу частину
розділ, як я вже говорив, йдеться про

76
00:03:34,020 --> 00:03:37,240
зв'язані списки і хеш-таблиці, які
буде безпосередньо застосовні до

77
00:03:37,240 --> 00:03:38,780
Проблема встановити на цьому тижні.

78
00:03:38,780 --> 00:03:42,580
Пов'язані списки ми підемо на відносно
швидко, тому що ми витратили справедливий біт

79
00:03:42,580 --> 00:03:44,930
часу збирається над нею в розділі.

80
00:03:44,930 --> 00:03:48,680
І тому ми отримати прямо в
кодування проблеми для пов'язаних списків.

81
00:03:48,680 --> 00:03:52,740
А потім в кінці ми поговоримо про
хеши і як вони застосовуються до цього

82
00:03:52,740 --> 00:03:55,280
Проблема тижні встановити.

83
00:03:55,280 --> 00:03:57,560
>> Ви бачили цей код раніше.

84
00:03:57,560 --> 00:04:02,730
Це структура, і це визначення
щось нове називається вузлом.

85
00:04:02,730 --> 00:04:10,660
А усередині вузла існує ціле
прямо тут і є вказівник на

86
00:04:10,660 --> 00:04:11,830
інший вузол.

87
00:04:11,830 --> 00:04:12,790
Ми бачили це раніше.

88
00:04:12,790 --> 00:04:14,830
Це було придумувати для
пару тижнів зараз.

89
00:04:14,830 --> 00:04:18,680
Вона поєднує в собі покажчики, які ми відвідували
роботи з, і структури, які дозволяють

90
00:04:18,680 --> 00:04:22,079
нам об'єднати два різних
речі в один тип даних.

91
00:04:22,079 --> 00:04:24,830

92
00:04:24,830 --> 00:04:26,490
>> Там дуже багато відбувається на екрані.

93
00:04:26,490 --> 00:04:30,220
Але все це має бути відносно
знайомі з вами.

94
00:04:30,220 --> 00:04:33,810
На першій лінії, ми
оголосити новий вузол.

95
00:04:33,810 --> 00:04:41,650
А потім всередині цієї нового вузла, я поставив
ціле число в цьому вузлі до одного.

96
00:04:41,650 --> 00:04:44,950
Ми бачимо, на наступному рядку я роблю
Е команда, але я сірим кольором

97
00:04:44,950 --> 00:04:48,080
команда Е, тому що насправді
Важливою частиною є ця лінія тут -

98
00:04:48,080 --> 00:04:50,020
new_node.n.

99
00:04:50,020 --> 00:04:51,270
Що точка на увазі?

100
00:04:51,270 --> 00:04:53,810

101
00:04:53,810 --> 00:04:57,240
>> АУДИТОРІЯ: Перейдіть у вузол і
оцінити вартість н для нього.

102
00:04:57,240 --> 00:04:58,370
>> Джейсон Хіршхорна: Це
Абсолютно вірно.

103
00:04:58,370 --> 00:05:03,300
Dot означає переходу до північна частина
цього нового вузла.

104
00:05:03,300 --> 00:05:05,690
У наступному рядку що робить?

105
00:05:05,690 --> 00:05:16,140

106
00:05:16,140 --> 00:05:17,050
Майкл.

107
00:05:17,050 --> 00:05:21,910
>> АУДИТОРІЯ: Створюється ще один вузол
що буде вказувати на новий вузол.

108
00:05:21,910 --> 00:05:24,870
>> Джейсон Хіршхорна: Так це не
створити новий вузол.

109
00:05:24,870 --> 00:05:26,120
Він створює те, що?

110
00:05:26,120 --> 00:05:28,300

111
00:05:28,300 --> 00:05:29,300
>> АУДИТОРІЯ: Покажчик.

112
00:05:29,300 --> 00:05:33,460
>> Джейсон Хіршхорна: покажчик на вузол,
як зазначено цьому вузол * тут.

113
00:05:33,460 --> 00:05:34,800
Таким чином, це створює покажчик на вузол.

114
00:05:34,800 --> 00:05:37,490
І який вузол він вказуючи
щоб, Майкл?

115
00:05:37,490 --> 00:05:38,440
>> АУДИТОРІЯ: Новий вузол?

116
00:05:38,440 --> 00:05:39,240
>> Джейсон Хіршхорна: Новий вузол.

117
00:05:39,240 --> 00:05:43,020
І це вказує там, тому що ми
дав йому адресу нового вузла.

118
00:05:43,020 --> 00:05:45,820
І тепер в цій лінії ми бачимо
два різні способи

119
00:05:45,820 --> 00:05:46,910
висловлюючи те ж саме.

120
00:05:46,910 --> 00:05:49,650
І я хотів би відзначити, як ці
дві речі однакові.

121
00:05:49,650 --> 00:05:54,740
У першому рядку ми разименовать
покажчик.

122
00:05:54,740 --> 00:05:55,830
Так ми йдемо до вузла.

123
00:05:55,830 --> 00:05:56,830
Це те, що ця зірка означає.

124
00:05:56,830 --> 00:05:57,930
Ми бачили, що перед з покажчиками.

125
00:05:57,930 --> 00:05:59,280
До цього вузла.

126
00:05:59,280 --> 00:06:00,370
Ось в дужках.

127
00:06:00,370 --> 00:06:04,610
А потім доступ через оператора точки
н елементом цього вузла.

128
00:06:04,610 --> 00:06:08,430
>> Так що бере синтаксис
ми побачили прямо тут і зараз

129
00:06:08,430 --> 00:06:09,670
використовувати його з покажчиком.

130
00:06:09,670 --> 00:06:13,730
Звичайно, він отримує трохи зайнятий, якщо
ви пишете ці дужки -

131
00:06:13,730 --> 00:06:14,940
що зірка і що крапка.

132
00:06:14,940 --> 00:06:16,220
Це стає трохи зайнятий.

133
00:06:16,220 --> 00:06:18,500
Тому у нас є деякі синтаксичний цукор.

134
00:06:18,500 --> 00:06:19,920
І ця лінія прямо тут -

135
00:06:19,920 --> 00:06:21,170
ptr_node-> п.

136
00:06:21,170 --> 00:06:25,400

137
00:06:25,400 --> 00:06:28,000
Це робить точно такий же речі.

138
00:06:28,000 --> 00:06:30,840
Так що ті два рядки коду
еквівалентні і буде робити

139
00:06:30,840 --> 00:06:31,650
та ж сама річ.

140
00:06:31,650 --> 00:06:34,210
>> Але я хотів би відзначити тих, перед
ми підемо далі, щоб ви розумієте

141
00:06:34,210 --> 00:06:39,000
що дійсно ця річ прямо тут є
просто синтаксичний цукор для разименованія

142
00:06:39,000 --> 00:06:44,200
покажчик, а потім збирається
н частиною цієї структури.

143
00:06:44,200 --> 00:06:45,525
Будь-які питання про цьому слайді?

144
00:06:45,525 --> 00:06:53,020

145
00:06:53,020 --> 00:06:54,390
ОК.

146
00:06:54,390 --> 00:06:58,510
>> Так що ми збираємося пройти через пару
операцій, які ви можете зробити на

147
00:06:58,510 --> 00:06:59,730
зв'язані списки.

148
00:06:59,730 --> 00:07:05,770
Зв'язаний список, нагадаємо, являє собою серію
вузлів, які вказують на іншому.

149
00:07:05,770 --> 00:07:12,470
І ми зазвичай починають з покажчиком
називається глава, як правило,, що вказує на

150
00:07:12,470 --> 00:07:14,040
перше, що в списку.

151
00:07:14,040 --> 00:07:18,900
Так на першій лінії тут, ми
є наш початковий L в першу чергу.

152
00:07:18,900 --> 00:07:21,370
Так що, що ви можете думати - це
текст прямо тут ви можете думати про якість

153
00:07:21,370 --> 00:07:23,560
просто покажчик ми зберегли
десь, що точки

154
00:07:23,560 --> 00:07:24,670
на перший елемент.

155
00:07:24,670 --> 00:07:27,500
І в цьому пов'язаного списку
у нас є чотири вузла.

156
00:07:27,500 --> 00:07:29,530
Кожен вузол являє собою великий ящик.

157
00:07:29,530 --> 00:07:33,430
Чим більше коробка всередині великої
коробка ціла частина.

158
00:07:33,430 --> 00:07:37,400
І тоді у нас є вказівник участь.

159
00:07:37,400 --> 00:07:39,630
>> Ці коробки не тягне
шкала тому, наскільки велика

160
00:07:39,630 --> 00:07:42,320
собою ціле число в байтах?

161
00:07:42,320 --> 00:07:43,290
Наскільки велика зараз?

162
00:07:43,290 --> 00:07:43,710
Чотири.

163
00:07:43,710 --> 00:07:45,470
І, наскільки великий це покажчик?

164
00:07:45,470 --> 00:07:45,940
Чотири.

165
00:07:45,940 --> 00:07:48,180
Так насправді, якщо ми повинні були зробити
це в масштабі обидві коробки

166
00:07:48,180 --> 00:07:49,690
буде такий же розмір.

167
00:07:49,690 --> 00:07:52,870
У цьому випадку, ми хочемо, щоб вставити
щось у зв'язаному списку.

168
00:07:52,870 --> 00:07:57,190
Таким чином, ви можете бачити тут ми вставки
п'ять Ми пройти через

169
00:07:57,190 --> 00:08:01,310
зв'язаний список, знайти, де п'ять
йде, а потім вставте його.

170
00:08:01,310 --> 00:08:03,560
>> Давайте розберемо, що вниз і йти
трохи повільніше.

171
00:08:03,560 --> 00:08:05,510
Я збираюся вказати на борту.

172
00:08:05,510 --> 00:08:09,930
Так у нас є вузол п'ять, що
ми створили в mallocs.

173
00:08:09,930 --> 00:08:11,190
Чому всі сміються?

174
00:08:11,190 --> 00:08:12,130
Жартую.

175
00:08:12,130 --> 00:08:13,310
ОК.

176
00:08:13,310 --> 00:08:14,820
Таким чином, ми malloced п'ять.

177
00:08:14,820 --> 00:08:16,310
Ми створили цей вузол
десь в іншому місці.

178
00:08:16,310 --> 00:08:17,740
У нас є це готові піти.

179
00:08:17,740 --> 00:08:20,130
Ми починаємо в передній частині
наш список з двома.

180
00:08:20,130 --> 00:08:22,380
І ми хочемо, щоб вставити
в відсортованому моди.

181
00:08:22,380 --> 00:08:27,550
>> Так що, якщо ми бачимо два, і ми хочемо, щоб покласти
в п'ять, що ж нам робити, коли ми бачимо,

182
00:08:27,550 --> 00:08:28,800
щось менше, ніж ми?

183
00:08:28,800 --> 00:08:31,850

184
00:08:31,850 --> 00:08:33,520
Що?

185
00:08:33,520 --> 00:08:36,750
Ми хочемо, щоб вставити п'ять у це
зв'язаний список, зберігаючи його сортувати.

186
00:08:36,750 --> 00:08:37,520
Ми бачимо, номер два.

187
00:08:37,520 --> 00:08:38,769
Так що ж нам робити?

188
00:08:38,769 --> 00:08:39,179
Маркус?

189
00:08:39,179 --> 00:08:40,679
>> АУДИТОРІЯ: Зателефонуйте покажчик
до наступного вузла.

190
00:08:40,679 --> 00:08:42,530
>> Джейсон Хіршхорна: І чому
ми йдемо до наступного?

191
00:08:42,530 --> 00:08:45,970
>> АУДИТОРІЯ: Тому що це
Наступний вузол у списку.

192
00:08:45,970 --> 00:08:48,310
І ми знаємо тільки, що інше місце.

193
00:08:48,310 --> 00:08:50,410
>> Джейсон Хіршхорна: І п'ять більше,
ніж два, зокрема.

194
00:08:50,410 --> 00:08:51,600
Тому що ми хочемо, щоб тримати його відсортований.

195
00:08:51,600 --> 00:08:52,730
Так п'ять більше двох.

196
00:08:52,730 --> 00:08:54,460
Таким чином, ми перейдемо до наступного.

197
00:08:54,460 --> 00:08:55,240
І тепер ми досягнемо чотири.

198
00:08:55,240 --> 00:08:56,490
І що відбувається, коли ми досягаємо чотири?

199
00:08:56,490 --> 00:08:58,920

200
00:08:58,920 --> 00:09:00,310
>> П'ять більше чотирьох.

201
00:09:00,310 --> 00:09:01,460
Так ми продовжуємо.

202
00:09:01,460 --> 00:09:03,110
І тепер ми в шість.

203
00:09:03,110 --> 00:09:04,360
І що ж ми бачимо в шість?

204
00:09:04,360 --> 00:09:08,672

205
00:09:08,672 --> 00:09:09,608
Так, Карлос?

206
00:09:09,608 --> 00:09:10,544
>> АУДИТОРІЯ: Шість більше п'яти.

207
00:09:10,544 --> 00:09:11,480
>> Джейсон Хіршхорна: Шість є
більше п'яти.

208
00:09:11,480 --> 00:09:13,660
Так от де ми хочемо
вставити п'ять.

209
00:09:13,660 --> 00:09:17,320
Однак, майте на увазі, що якщо ми
є тільки один покажчик тут -

210
00:09:17,320 --> 00:09:19,840
це наша додаткова покажчик ось
обході за списком.

211
00:09:19,840 --> 00:09:21,860
І ми вказуємо до шести.

212
00:09:21,860 --> 00:09:25,010
Ми втратили слід того, що
приходить раніше шести.

213
00:09:25,010 --> 00:09:29,130
Так що, якщо ми хочемо, щоб вставити щось у
цей список тримати його сортують, ми

214
00:09:29,130 --> 00:09:31,630
ймовірно, потрібно, як багато покажчиків?

215
00:09:31,630 --> 00:09:32,280
>> АУДИТОРІЯ: Два.

216
00:09:32,280 --> 00:09:32,920
>> Джейсон Хіршхорна: Два.

217
00:09:32,920 --> 00:09:35,720
Один відстежувати струму
один і один, щоб відстежувати

218
00:09:35,720 --> 00:09:37,050
попередній.

219
00:09:37,050 --> 00:09:38,450
Це тільки односпрямований список.

220
00:09:38,450 --> 00:09:39,670
Це тільки йде в одному напрямку.

221
00:09:39,670 --> 00:09:43,220
Якби ми мали двусвязний список, де
все було вказуючи на речі

222
00:09:43,220 --> 00:09:46,240
після нього і речі до нього, то
ми не повинні були б зробити це.

223
00:09:46,240 --> 00:09:49,350
Але в даному випадку ми не хочемо втратити
трек, що було до нас, у разі

224
00:09:49,350 --> 00:09:53,350
ми повинні вставити п'ять десь
в середині.

225
00:09:53,350 --> 00:09:55,610
Скажімо, у нас були вставки дев'ять.

226
00:09:55,610 --> 00:09:57,260
Що станеться, коли
ми дісталися до восьми?

227
00:09:57,260 --> 00:10:01,860

228
00:10:01,860 --> 00:10:04,880
>> АУДИТОРІЯ: Ви повинні були б
отримати, що порожню точку.

229
00:10:04,880 --> 00:10:07,820
Замість того, нульову точку, яку ви повинні були б
додати елемент, а потім є

230
00:10:07,820 --> 00:10:09,216
він вказував на дев'яти.

231
00:10:09,216 --> 00:10:09,700
>> Джейсон Хіршхорна: Абсолютно вірно.

232
00:10:09,700 --> 00:10:10,600
Отже, ми отримуємо вісім.

233
00:10:10,600 --> 00:10:13,140
Ми дійдете до кінця списку, тому що
це вказує на нуль.

234
00:10:13,140 --> 00:10:16,330
І тепер, замість того, він вказував на
нуль у нас він вказував на наш новий вузол.

235
00:10:16,330 --> 00:10:19,870
І ми встановити покажчик в
наш новий вузол на нуль.

236
00:10:19,870 --> 00:10:21,445
Хто-небудь є які-небудь питання
про вставці?

237
00:10:21,445 --> 00:10:25,620

238
00:10:25,620 --> 00:10:28,100
Що, якщо я не піклуються про
зберігаючи список упорядковано?

239
00:10:28,100 --> 00:10:31,701

240
00:10:31,701 --> 00:10:34,350
>> АУДИТОРІЯ: Дотримуйтеся його на
початку або в кінці.

241
00:10:34,350 --> 00:10:35,510
>> Джейсон Хіршхорна: Дотримуйтеся його на
початок або кінець.

242
00:10:35,510 --> 00:10:37,276
Який ми повинні робити?

243
00:10:37,276 --> 00:10:38,770
Боббі?

244
00:10:38,770 --> 00:10:41,020
Чому кінець?

245
00:10:41,020 --> 00:10:43,250
>> АУДИТОРІЯ: Тому що початок
вже заповнений.

246
00:10:43,250 --> 00:10:43,575
>> Джейсон Хіршхорна: ОК.

247
00:10:43,575 --> 00:10:44,360
Початок вже заповнена.

248
00:10:44,360 --> 00:10:46,090
Хто хоче сперечатися з Боббі.

249
00:10:46,090 --> 00:10:47,290
Маркус.

250
00:10:47,290 --> 00:10:48,910
>> АУДИТОРІЯ: Ну ви, ймовірно, хочете
дотримуватися його на початку, тому що

251
00:10:48,910 --> 00:10:50,140
в іншому випадку, якщо ви кладете його на
кінець вам доведеться

252
00:10:50,140 --> 00:10:51,835
пройти весь список.

253
00:10:51,835 --> 00:10:52,990
>> Джейсон Хіршхорна: Абсолютно вірно.

254
00:10:52,990 --> 00:10:57,970
Так що, якщо ми думаємо про виконання,
Час роботи, включивши в кінці

255
00:10:57,970 --> 00:11:00,110
б н, розмір цього.

256
00:11:00,110 --> 00:11:03,080
Що таке велика O виконання вставки
на початку?

257
00:11:03,080 --> 00:11:04,170
Постійний час.

258
00:11:04,170 --> 00:11:07,075
Так що, якщо ви не дбаєте про збереження
щось сортуються, набагато краще просто

259
00:11:07,075 --> 00:11:08,420
вставити на початку цього списку.

260
00:11:08,420 --> 00:11:10,320
І це може бути зроблено за постійний час.

261
00:11:10,320 --> 00:11:13,900

262
00:11:13,900 --> 00:11:14,690
>> ОК.

263
00:11:14,690 --> 00:11:18,870
Наступна операція знайти, що інший -
ми формулюванні це як категорії.

264
00:11:18,870 --> 00:11:22,470
Але ми будемо дивитися через
зв'язаний список протягом деякого об'єкта.

265
00:11:22,470 --> 00:11:26,000
Ви, хлопці, бачили код для
пошук перш в лекції.

266
00:11:26,000 --> 00:11:29,490
Але ми начебто тільки що зробив це з
вставити, або принаймні вставки

267
00:11:29,490 --> 00:11:30,580
щось відсортовані.

268
00:11:30,580 --> 00:11:36,350
Ви переглядаєте, збирається вузла до вузла,
поки ви не знайдете номер, що ви

269
00:11:36,350 --> 00:11:37,780
шукаю.

270
00:11:37,780 --> 00:11:39,670
Що станеться, якщо ви досягнете
кінець списку?

271
00:11:39,670 --> 00:11:43,020
Скажи я шукаю дев'яти і I
дійдете до кінця списку.

272
00:11:43,020 --> 00:11:44,270
Що нам робити?

273
00:11:44,270 --> 00:11:47,147

274
00:11:47,147 --> 00:11:48,110
>> АУДИТОРІЯ: Повернутися брехня?

275
00:11:48,110 --> 00:11:48,690
>> Джейсон Хіршхорна: Повернутися хибним.

276
00:11:48,690 --> 00:11:49,960
Ми не знайшли його.

277
00:11:49,960 --> 00:11:52,010
Якщо ви дійдете до кінця списку і
Ви не знайшли номер, який ви знаходитесь

278
00:11:52,010 --> 00:11:54,170
шукаю, це не там.

279
00:11:54,170 --> 00:11:55,420
Будь-які питання про знайти?

280
00:11:55,420 --> 00:11:59,530

281
00:11:59,530 --> 00:12:04,615
Якби це було відсортований список, що б
бути різними для нашого пошуку?

282
00:12:04,615 --> 00:12:07,370

283
00:12:07,370 --> 00:12:08,103
Так.

284
00:12:08,103 --> 00:12:10,600
>> АУДИТОРІЯ: Було б знайти перше значення
от більше того,

285
00:12:10,600 --> 00:12:12,390
ви шукаєте і
потім повернутися помилковим.

286
00:12:12,390 --> 00:12:13,190
>> Джейсон Хіршхорна: Абсолютно вірно.

287
00:12:13,190 --> 00:12:17,310
Так що, якщо це відсортований список, якщо ми доберемося до
щось, що це більше, ніж те, що

288
00:12:17,310 --> 00:12:20,180
ми шукаємо, ми не повинні
продовжувати йти в кінець списку.

289
00:12:20,180 --> 00:12:24,060
Ми можемо в цій точці повернутися помилковим
тому що ми не збираємося, щоб знайти його.

290
00:12:24,060 --> 00:12:27,340
Питання тепер, ми говорили про
зберігаючи пов'язані списки сортуються,

291
00:12:27,340 --> 00:12:28,180
тримати їх без сортування.

292
00:12:28,180 --> 00:12:30,050
Це буде те, що ви перебуваєте
, Ймовірно, доведеться думати про

293
00:12:30,050 --> 00:12:34,240
коли проблема кодування встановити п'ять, якщо ви
вибрати хеш-таблицю з окремою

294
00:12:34,240 --> 00:12:36,360
ланцюжка підхід, який
ми поговоримо трохи пізніше.

295
00:12:36,360 --> 00:12:41,400
>> Але чи варто це того, щоб зберегти список
відсортований і потім мати можливість, може бути, є

296
00:12:41,400 --> 00:12:42,310
швидше результати?

297
00:12:42,310 --> 00:12:47,220
Або краще, щоб швидко вставити
щось в постійному виконання, але тоді

298
00:12:47,220 --> 00:12:48,430
є більше пошуку?

299
00:12:48,430 --> 00:12:52,250
Це компроміс тут же, що вам
самим вирішувати, що є більш доцільним

300
00:12:52,250 --> 00:12:53,590
для вашої конкретної проблеми.

301
00:12:53,590 --> 00:12:56,680
І є не обов'язково один
абсолютно правильну відповідь.

302
00:12:56,680 --> 00:12:59,520
Але це, безумовно, рішення, яке ви отримуєте
зробити, і, ймовірно, добре, щоб захистити

303
00:12:59,520 --> 00:13:05,270
що, скажімо, коментар або два, чому
ви вибрали один над іншим.

304
00:13:05,270 --> 00:13:06,490
>> Нарешті, видалення.

305
00:13:06,490 --> 00:13:08,100
Ми бачили видалення.

306
00:13:08,100 --> 00:13:09,180
Це схоже на пошук.

307
00:13:09,180 --> 00:13:11,020
Ми шукаємо елемента.

308
00:13:11,020 --> 00:13:12,390
Скажіть, що ми намагаємося видалити шість.

309
00:13:12,390 --> 00:13:14,450
Так ми знаходимо шість прямо тут.

310
00:13:14,450 --> 00:13:18,860
Справа в тому, що ми повинні переконатися, що ми
робити те, що все, що вказує на

311
00:13:18,860 --> 00:13:21,220
шість - як ми бачимо в дії
два вниз тут -

312
00:13:21,220 --> 00:13:26,500
що б не вказуючи на шести потреб в
пропустити шість зараз і бути змінений на

313
00:13:26,500 --> 00:13:28,160
всі шість вказує на.

314
00:13:28,160 --> 00:13:31,410
Ми не хочемо, щоб коли-небудь сиротам решту
наш список, забувши встановити, що

315
00:13:31,410 --> 00:13:32,960
попередня покажчик.

316
00:13:32,960 --> 00:13:35,960
А потім іноді, залежно
за програмою, вони просто

317
00:13:35,960 --> 00:13:37,380
видалити цей вузол цілком.

318
00:13:37,380 --> 00:13:40,135
Іноді ви хочете, щоб повернутися
значення, яке знаходиться в цьому вузлі.

319
00:13:40,135 --> 00:13:42,490
Так от, як видалення робіт.

320
00:13:42,490 --> 00:13:44,610
Будь-які питання по видалити?

321
00:13:44,610 --> 00:13:51,280

322
00:13:51,280 --> 00:13:53,850
>> АУДИТОРІЯ: Так що, якщо ви збираєтеся видалити
це, ви б просто використовувати безкоштовно, тому що

323
00:13:53,850 --> 00:13:55,655
імовірно було malloced?

324
00:13:55,655 --> 00:13:57,976
>> Джейсон Хіршхорна: Якщо ви хочете, щоб звільнити
те, що цілком правильно, і ви

325
00:13:57,976 --> 00:13:58,540
malloced його.

326
00:13:58,540 --> 00:14:00,410
Скажімо ми хотіли повернутися це значення.

327
00:14:00,410 --> 00:14:04,010
Ми могли б повернутися шість, а потім безкоштовно
цей вузол і виклик безкоштовно на нього.

328
00:14:04,010 --> 00:14:06,180
Або ми, ймовірно, дзвонити безкоштовно перший
, А потім повернутися шість.

329
00:14:06,180 --> 00:14:11,210

330
00:14:11,210 --> 00:14:11,580
>> ОК.

331
00:14:11,580 --> 00:14:14,010
Так давайте перейдемо до практики кодування.

332
00:14:14,010 --> 00:14:16,090
Ми збираємося, щоб закодувати три функції.

333
00:14:16,090 --> 00:14:18,260
Перший з них називається insert_node.

334
00:14:18,260 --> 00:14:22,170
Так у вас є код, який я послав по електронній пошті вам, і
якщо ви дивитеся це пізніше

335
00:14:22,170 --> 00:14:28,020
Ви можете отримати доступ до коду в linked.c
на сайті CS50.

336
00:14:28,020 --> 00:14:30,880
Але в linked.c, є деякі
скелет код, який вже

337
00:14:30,880 --> 00:14:32,280
була написана для вас.

338
00:14:32,280 --> 00:14:34,560
А тут ще пару ФУНКЦІЇ
вам потрібно написати.

339
00:14:34,560 --> 00:14:36,380
>> Спочатку ми збираємося
написати insert_node.

340
00:14:36,380 --> 00:14:39,800
А що insert_node робить
є вставляє ціле.

341
00:14:39,800 --> 00:14:42,440
І ви даєте ціле число
в зв'язний список.

342
00:14:42,440 --> 00:14:45,470
І зокрема, необхідно
зберегти список, відсортований

343
00:14:45,470 --> 00:14:47,650
від меншого до більшого.

344
00:14:47,650 --> 00:14:51,360
Крім того, ви не хочете, щоб
вставити всі дублікати.

345
00:14:51,360 --> 00:14:54,600
Нарешті, як ви можете бачити insert_node
повертає логічне значення.

346
00:14:54,600 --> 00:14:57,140
Таким чином, ви, як передбачається, щоб користувач знав,
чи ні вставка була

347
00:14:57,140 --> 00:15:00,800
успішним, повертаючи істинним або хибним.

348
00:15:00,800 --> 00:15:02,580
Наприкінці цієї програми -

349
00:15:02,580 --> 00:15:05,750
і для цієї стадії вам не потрібно
турбуватися про звільнення нічого.

350
00:15:05,750 --> 00:15:11,790
Так що все, що ви робите це взяття цілої
і вставки його в список.

351
00:15:11,790 --> 00:15:13,890
>> Це те, що я прошу вас зробити зараз.

352
00:15:13,890 --> 00:15:17,620
Знову ж, в linked.c, які ви
у всіх є, це код скелет.

353
00:15:17,620 --> 00:15:20,980
І ви повинні побачити в нижній
Оголошення функції зразка.

354
00:15:20,980 --> 00:15:27,390
Проте, перш ніж в його кодування
в С, я настійно рекомендую вам піти

355
00:15:27,390 --> 00:15:29,330
через ряд кроків, ми були
практикуючих щотижня.

356
00:15:29,330 --> 00:15:31,100
Ми вже пройшли через
картина цього.

357
00:15:31,100 --> 00:15:33,380
Таким чином, ви повинні мати певне уявлення
, Як це працює.

358
00:15:33,380 --> 00:15:36,590
Але я хотів би закликати вас, щоб написати
деякі псевдокод, перш ніж поринути дюйма

359
00:15:36,590 --> 00:15:38,640
І ми збираємося перейти на
псевдокод як група.

360
00:15:38,640 --> 00:15:41,470
А потім, як тільки ви написали
псевдокод, і як тільки ми написали наш

361
00:15:41,470 --> 00:15:45,850
псевдокод як група, ви можете
йти в кодування його в С.

362
00:15:45,850 --> 00:15:49,980
>> Як один на один, функція insert_node
Ймовірно, найскладніша з

363
00:15:49,980 --> 00:15:53,550
три ми збираємося написати, тому що я
додані деякі додаткові обмеження на

364
00:15:53,550 --> 00:15:57,190
Ваш програмування, зокрема, що
ви не збираєтеся вставити будь

365
00:15:57,190 --> 00:15:59,880
дублікатів та, що список
повинні залишатися відсортований.

366
00:15:59,880 --> 00:16:02,660
Так що це нетривіальна програма
що ви повинні кодувати.

367
00:16:02,660 --> 00:16:06,470
І чому б вам не взяти 6:55
хвилин тільки, щоб отримати роботу на

368
00:16:06,470 --> 00:16:07,640
псевдокод і код.

369
00:16:07,640 --> 00:16:09,460
А потім ми почнемо
збирається в якості групи.

370
00:16:09,460 --> 00:16:11,680
Знову ж, якщо у вас є які-небудь питання, просто
підніміть руку, і я прийду навколо.

371
00:16:11,680 --> 00:16:15,258

372
00:16:15,258 --> 00:16:16,508
.

373
00:16:16,508 --> 00:18:28,370

374
00:18:28,370 --> 00:18:30,120
>> Ми також в цілому зробити це -

375
00:18:30,120 --> 00:18:32,070
або я не явно говорять вам
може працювати з людьми.

376
00:18:32,070 --> 00:18:36,500
Але очевидно, що я настійно рекомендую Вам,
якщо у вас є питання, запитати

377
00:18:36,500 --> 00:18:39,840
сусід сидить поруч з вами
або навіть працювати з кимось

378
00:18:39,840 --> 00:18:40,510
ще, якщо ви хочете.

379
00:18:40,510 --> 00:18:42,600
Це не повинно бути індивідуальним
мовчання діяльності.

380
00:18:42,600 --> 00:20:11,770

381
00:20:11,770 --> 00:20:16,330
>> Давайте почнемо з написання деяких
псевдокод на дошці.

382
00:20:16,330 --> 00:20:19,395
Хто може дати мені першу лінію
псевдокод для цієї програми?

383
00:20:19,395 --> 00:20:22,240

384
00:20:22,240 --> 00:20:23,640
Для цієї функції, а -
insert_node.

385
00:20:23,640 --> 00:20:29,960

386
00:20:29,960 --> 00:20:31,830
Олден?

387
00:20:31,830 --> 00:20:36,560
>> АУДИТОРІЯ: Тому перше, що я зробив, було
створити новий покажчик на вузол і I

388
00:20:36,560 --> 00:20:41,320
ініціалізації він вказуючи на те ж саме
річ, яка список вказує на.

389
00:20:41,320 --> 00:20:41,550
>> Джейсон Хіршхорна: ОК.

390
00:20:41,550 --> 00:20:45,190
Так ви створюєте новий покажчик
в список, а не до вузла.

391
00:20:45,190 --> 00:20:45,420
>> АУДИТОРІЯ: Вірно.

392
00:20:45,420 --> 00:20:46,150
Так.

393
00:20:46,150 --> 00:20:46,540
>> Джейсон Хіршхорна: ОК.

394
00:20:46,540 --> 00:20:48,221
А потім що ми хочемо зробити?

395
00:20:48,221 --> 00:20:49,163
Що після цього?

396
00:20:49,163 --> 00:20:50,105
А як щодо вузла?

397
00:20:50,105 --> 00:20:51,050
У нас немає вузла.

398
00:20:51,050 --> 00:20:52,300
Ми просто мати значення.

399
00:20:52,300 --> 00:20:55,918

400
00:20:55,918 --> 00:20:58,890
Якщо ми хочемо, щоб вставити вузол, що ми
потрібно зробити, перш ніж ми можемо навіть

401
00:20:58,890 --> 00:20:59,980
думати про вставивши його?

402
00:20:59,980 --> 00:21:00,820
>> АУДИТОРІЯ: Ой, вибачте.

403
00:21:00,820 --> 00:21:02,160
ми повинні Malloc простір для вузла.

404
00:21:02,160 --> 00:21:02,455
>> Джейсон Хіршхорна: Відмінно.

405
00:21:02,455 --> 00:21:03,210
Давайте зробимо -

406
00:21:03,210 --> 00:21:04,628
ОК.

407
00:21:04,628 --> 00:21:06,065
Не можете досягти цього максимуму.

408
00:21:06,065 --> 00:21:08,939

409
00:21:08,939 --> 00:21:09,897
ОК.

410
00:21:09,897 --> 00:21:13,236
Ми збираємося йти вниз, а потім
ми використовуємо два стовпці.

411
00:21:13,236 --> 00:21:13,732
Я не можу піти, що -

412
00:21:13,732 --> 00:21:14,982
ОК.

413
00:21:14,982 --> 00:21:23,660

414
00:21:23,660 --> 00:21:25,130
Створіть новий вузол.

415
00:21:25,130 --> 00:21:29,380
Ви можете створити ще один покажчик на список
або ви можете просто використовувати список, як вона існує.

416
00:21:29,380 --> 00:21:30,720
Ви дійсно не потрібно цього робити.

417
00:21:30,720 --> 00:21:31,750
>> Так ми створюємо новий вузол.

418
00:21:31,750 --> 00:21:32,010
Великий.

419
00:21:32,010 --> 00:21:32,840
Це те, що ми робимо в першу чергу.

420
00:21:32,840 --> 00:21:34,870
Що далі?

421
00:21:34,870 --> 00:21:35,080
>> АУДИТОРІЯ: Зачекайте.

422
00:21:35,080 --> 00:21:38,330
Чи повинні ми створити новий вузол зараз або
ми повинні чекати, щоб переконатися, що

423
00:21:38,330 --> 00:21:42,260
немає ніяких дублікатів вузла
в списку, перш ніж ми його створити?

424
00:21:42,260 --> 00:21:43,100
>> Джейсон Хіршхорна: Хороше питання.

425
00:21:43,100 --> 00:21:47,770
Давайте проведемо це на потім, бо
Велику частину часу ми будемо створювати

426
00:21:47,770 --> 00:21:48,220
новий вузол.

427
00:21:48,220 --> 00:21:49,110
Так ми будемо тримати це тут.

428
00:21:49,110 --> 00:21:51,006
Але це хороше запитання.

429
00:21:51,006 --> 00:21:53,250
Якщо ми створюємо його, і ми знаходимо
дублікат, що повинно

430
00:21:53,250 --> 00:21:54,490
ми робимо, перш ніж повернутися?

431
00:21:54,490 --> 00:21:55,190
>> АУДИТОРІЯ: Звільніть його.

432
00:21:55,190 --> 00:21:55,470
>> Джейсон Хіршхорна: Так.

433
00:21:55,470 --> 00:21:56,500
Напевно звільнити його.

434
00:21:56,500 --> 00:21:56,760
ОК.

435
00:21:56,760 --> 00:21:59,850
Що ми робимо після того як ми
створити новий вузол?

436
00:21:59,850 --> 00:22:02,260
Енні?

437
00:22:02,260 --> 00:22:04,780
>> АУДИТОРІЯ: Ставимо
число у вузлі?

438
00:22:04,780 --> 00:22:05,140
>> Джейсон Хіршхорна: Абсолютно вірно.

439
00:22:05,140 --> 00:22:07,190
Ми, число - ми Malloc простір.

440
00:22:07,190 --> 00:22:08,160
Я збираюся залишити це
всі як одна рядок.

441
00:22:08,160 --> 00:22:08,720
Але ви праві.

442
00:22:08,720 --> 00:22:10,305
Ми Malloc пробіл, а потім
ми ставимо номер дюйма

443
00:22:10,305 --> 00:22:12,585
Ми можемо навіть встановити покажчик
частина її до нуля.

444
00:22:12,585 --> 00:22:13,720
Ось саме.

445
00:22:13,720 --> 00:22:17,400
І то що говорити про після цього?

446
00:22:17,400 --> 00:22:18,490
Ми намалював цю картину на дошці.

447
00:22:18,490 --> 00:22:21,190
Так що ж нам робити?

448
00:22:21,190 --> 00:22:22,680
>> АУДИТОРІЯ: Ми йдемо за списком.

449
00:22:22,680 --> 00:22:23,930
>> Джейсон Хіршхорна: Пройтися по списку.

450
00:22:23,930 --> 00:22:30,620

451
00:22:30,620 --> 00:22:31,100
ОК.

452
00:22:31,100 --> 00:22:34,280
І що ж ми перевіряємо для кожного вузла.

453
00:22:34,280 --> 00:22:35,955
Курт, що ж ми перевіряємо
для кожного вузла?

454
00:22:35,955 --> 00:22:41,640
>> АУДИТОРІЯ: Чи дивитеся н значення
що вузол більше, ніж п значенням

455
00:22:41,640 --> 00:22:43,070
нашого вузла.

456
00:22:43,070 --> 00:22:43,340
>> Джейсон Хіршхорна: ОК.

457
00:22:43,340 --> 00:22:44,280
Я збираюся зробити -

458
00:22:44,280 --> 00:22:45,855
так, добре.

459
00:22:45,855 --> 00:22:48,160
Так що це п -

460
00:22:48,160 --> 00:22:59,040
Я збираюся сказати, якщо значення більше
ніж цей вузол, то що ж нам робити?

461
00:22:59,040 --> 00:23:07,290
>> АУДИТОРІЯ: Ну, тоді ми вставляємо
річ прямо перед цим.

462
00:23:07,290 --> 00:23:07,970
>> Джейсон Хіршхорна: ОК.

463
00:23:07,970 --> 00:23:09,410
Таким чином, якщо це більше, ніж ця,
то ми хочемо вставити.

464
00:23:09,410 --> 00:23:14,010
Але ми хочемо, щоб вставити його прямо перед
тому що ми також повинні були б бути

465
00:23:14,010 --> 00:23:16,070
відстеження, то,
з того, що було раніше.

466
00:23:16,070 --> 00:23:22,690
Так вставити раніше.

467
00:23:22,690 --> 00:23:25,120
Таким чином, ми, ймовірно, щось пропустив
раніше.

468
00:23:25,120 --> 00:23:27,770
Ми, ймовірно, повинні бути зберігаючи
трек, що відбувається.

469
00:23:27,770 --> 00:23:28,460
Але ми повернемося туди.

470
00:23:28,460 --> 00:23:30,160
Так що значення менше?

471
00:23:30,160 --> 00:23:38,030

472
00:23:38,030 --> 00:23:39,710
Курт, що ми будемо робити, якщо
значення менше?

473
00:23:39,710 --> 00:23:43,000
>> АУДИТОРІЯ: Тоді вам просто продовжувати йти
якщо це не останній.

474
00:23:43,000 --> 00:23:43,550
>> Джейсон Хіршхорна: Мені це подобається.

475
00:23:43,550 --> 00:23:44,800
Так що до наступного вузла.

476
00:23:44,800 --> 00:23:47,410

477
00:23:47,410 --> 00:23:48,930
Якщо це не останній -

478
00:23:48,930 --> 00:23:51,100
ми, ймовірно, перевіряючи, що
в термінах стану.

479
00:23:51,100 --> 00:23:54,870
Але так, наступний вузол.

480
00:23:54,870 --> 00:23:58,680
І це стає занадто низьким,
так що ми будемо рухатися тут.

481
00:23:58,680 --> 00:24:02,030
Але якщо -

482
00:24:02,030 --> 00:24:03,280
може все це бачиш?

483
00:24:03,280 --> 00:24:07,230

484
00:24:07,230 --> 00:24:11,610
Якщо ми рівні, що ми робимо?

485
00:24:11,610 --> 00:24:15,740
Якщо значення ми намагаємося вставити
дорівнює вартості цього вузла?

486
00:24:15,740 --> 00:24:16,320
Так?

487
00:24:16,320 --> 00:24:18,400
>> АУДИТОРІЯ: [нерозбірливо].

488
00:24:18,400 --> 00:24:18,850
>> Джейсон Хіршхорна: Так.

489
00:24:18,850 --> 00:24:19,290
Враховуючи це -

490
00:24:19,290 --> 00:24:20,090
Маркус прав.

491
00:24:20,090 --> 00:24:21,330
Ми могли б, можливо, зроблено
щось інше.

492
00:24:21,330 --> 00:24:25,360
Але, враховуючи, що ми створили його, тут
ми повинні звільнити, а потім повернутися.

493
00:24:25,360 --> 00:24:26,774
Про хлопчик.

494
00:24:26,774 --> 00:24:30,080
Так краще?

495
00:24:30,080 --> 00:24:31,850
Як це?

496
00:24:31,850 --> 00:24:33,100
ОК.

497
00:24:33,100 --> 00:24:35,360

498
00:24:35,360 --> 00:24:37,640
Безкоштовний і те що ми
повернутися, [нерозбірливо]?

499
00:24:37,640 --> 00:24:41,330

500
00:24:41,330 --> 00:24:44,110
ОК.

501
00:24:44,110 --> 00:24:45,360
Ми не написали нічого?

502
00:24:45,360 --> 00:24:53,500

503
00:24:53,500 --> 00:24:59,650
Так куди ми відстеження
попереднього вузла?

504
00:24:59,650 --> 00:25:02,370
>> Зали: Я думаю, що це піде
після створення нового вузла.

505
00:25:02,370 --> 00:25:02,600
>> Джейсон Хіршхорна: ОК.

506
00:25:02,600 --> 00:25:03,940
Тому на початку ми, напевно, -

507
00:25:03,940 --> 00:25:07,175
так, ми можемо створити покажчик на новий
вузол, як попередній покажчик вузла і

508
00:25:07,175 --> 00:25:09,600
поточний покажчик вузла.

509
00:25:09,600 --> 00:25:12,640
Так що давайте вставити, що тут.

510
00:25:12,640 --> 00:25:15,610

511
00:25:15,610 --> 00:25:26,900
Створення поточний і попередній
покажчики на вузлах.

512
00:25:26,900 --> 00:25:28,955
Але коли ми налаштувати ці покажчики?

513
00:25:28,955 --> 00:25:30,205
Де ж нам робити, що в коді?

514
00:25:30,205 --> 00:25:33,830

515
00:25:33,830 --> 00:25:34,160
Джефф?

516
00:25:34,160 --> 00:25:35,170
>> АУДИТОРІЯ: - умови значення?

517
00:25:35,170 --> 00:25:36,420
>> Джейсон Хіршхорна: Які
один, зокрема?

518
00:25:36,420 --> 00:25:39,862

519
00:25:39,862 --> 00:25:40,720
>> АУДИТОРІЯ: Я просто в замішанні.

520
00:25:40,720 --> 00:25:44,200
Якщо значення більше цього вузла,
чи не означає це, що ви хочете піти

521
00:25:44,200 --> 00:25:45,320
на наступний вузол?

522
00:25:45,320 --> 00:25:49,515
>> Джейсон Хіршхорна: Так що, якщо наша значення
більше, ніж значення цього вузла.

523
00:25:49,515 --> 00:25:52,130
>> АУДИТОРІЯ: Так, то ви хотіли б
йти далі по лінії, чи не так?

524
00:25:52,130 --> 00:25:52,590
>> Джейсон Хіршхорна: Вірно.

525
00:25:52,590 --> 00:25:53,840
Таким чином, ми не вставляйте його тут.

526
00:25:53,840 --> 00:25:58,430

527
00:25:58,430 --> 00:26:03,240
Якщо значення менше цього вузла, то
ми йдемо до наступного вузла - або тоді ми

528
00:26:03,240 --> 00:26:03,835
вставити раніше.

529
00:26:03,835 --> 00:26:05,966
>> АУДИТОРІЯ: Зачекайте, що це
вузол і що значення?

530
00:26:05,966 --> 00:26:08,510

531
00:26:08,510 --> 00:26:09,280
>> Джейсон Хіршхорна: Хороше питання.

532
00:26:09,280 --> 00:26:13,260
Значення за цим визначенням функції
це те, що нам дають.

533
00:26:13,260 --> 00:26:16,910
Так значення є числом нам дають.

534
00:26:16,910 --> 00:26:21,120
Таким чином, якщо значення менше, ніж це
вузол, нам потрібен час, щоб вставити.

535
00:26:21,120 --> 00:26:24,575
Якщо значення більше цього вузла,
ми йдемо до наступного вузла.

536
00:26:24,575 --> 00:26:26,790
І повернутися до початкового питання,
хоча, де -

537
00:26:26,790 --> 00:26:29,060
>> АУДИТОРІЯ: Якщо значення більше
ніж цього вузла.

538
00:26:29,060 --> 00:26:30,310
>> Джейсон Хіршхорна: І так
що нам робити тут?

539
00:26:30,310 --> 00:26:36,790

540
00:26:36,790 --> 00:26:38,160
Солодкий.

541
00:26:38,160 --> 00:26:38,860
Це вірно.

542
00:26:38,860 --> 00:26:41,370
Я просто збираюся написати
зміна покажчики.

543
00:26:41,370 --> 00:26:44,010
Але так, з поточною
ви б оновити її до

544
00:26:44,010 --> 00:26:46,080
вказують на наступній.

545
00:26:46,080 --> 00:26:47,330
Все інше ми пропустили?

546
00:26:47,330 --> 00:26:52,710

547
00:26:52,710 --> 00:26:54,940
Так що я збираюся ввести цей
код в Gedit.

548
00:26:54,940 --> 00:26:58,375
І в той час я роблю це, ви можете мати
Ще пара хвилин, щоб працювати з кодування

549
00:26:58,375 --> 00:28:19,240
це в С.

550
00:28:19,240 --> 00:28:20,940
>> Так що я свій внесок псевдокод.

551
00:28:20,940 --> 00:28:22,940
Невелика примітка перш ніж ми почнемо.

552
00:28:22,940 --> 00:28:25,560
Ми не можемо бути в змозі повністю
закінчити це всього

553
00:28:25,560 --> 00:28:27,300
три з цих функцій.

554
00:28:27,300 --> 00:28:30,630
Існує правильні шляхи їх вирішення
що я буду по електронній пошті до вас, хлопці

555
00:28:30,630 --> 00:28:33,730
після розділу, і він буде
будуть розміщені на CS50.net.

556
00:28:33,730 --> 00:28:35,640
Так що я не закликаю вас
піти подивитися на секціях.

557
00:28:35,640 --> 00:28:40,550
Я закликаю вас, щоб спробувати їх на ваш
володіти, а потім використовувати практику

558
00:28:40,550 --> 00:28:41,760
проблеми, щоб перевірити свої відповіді.

559
00:28:41,760 --> 00:28:47,070
Всі вони були розроблені, щоб тісно
відносяться до і дотримуватися того, що

560
00:28:47,070 --> 00:28:48,400
що вам потрібно зробити на безлічі проблем.

561
00:28:48,400 --> 00:28:53,820
Так що я закликаю вас до практики це
за своїм розсудом, а потім використовувати код для

562
00:28:53,820 --> 00:28:54,660
перевірити свої відповіді.

563
00:28:54,660 --> 00:28:57,060
Тому що я хочу, щоб рухатися далі, щоб прояснити
столи в якийсь момент у розділі.

564
00:28:57,060 --> 00:28:58,150
Таким чином, ми не могли б отримати через все це.

565
00:28:58,150 --> 00:28:59,960
Але ми зробимо стільки, скільки ми можемо зараз.

566
00:28:59,960 --> 00:29:00,370
>> ОК.

567
00:29:00,370 --> 00:29:01,960
Почнемо.

568
00:29:01,960 --> 00:29:04,770
Асам, як ми створюємо новий вузол?

569
00:29:04,770 --> 00:29:06,810
>> АУДИТОРІЯ: Ви структури *.

570
00:29:06,810 --> 00:29:09,640
>> Джейсон Хіршхорна: Таким чином, ми
є, що тут.

571
00:29:09,640 --> 00:29:10,040
Ой, вибачте.

572
00:29:10,040 --> 00:29:13,530
Ви говорили структуру *.

573
00:29:13,530 --> 00:29:17,260
>> АУДИТОРІЯ: А потім [? вид?]
вузол або з вузлом.

574
00:29:17,260 --> 00:29:17,780
>> Джейсон Хіршхорна: ОК.

575
00:29:17,780 --> 00:29:19,740
Я буду називати його new_node
так що ми можемо залишатися послідовним.

576
00:29:19,740 --> 00:29:22,646

577
00:29:22,646 --> 00:29:33,180
>> АУДИТОРІЯ: І ви хочете встановити, що
очолити, перший вузол.

578
00:29:33,180 --> 00:29:33,580
>> Джейсон Хіршхорна: ОК.

579
00:29:33,580 --> 00:29:37,290
Так що тепер це, вказує на - так це
не створив новий вузол ще.

580
00:29:37,290 --> 00:29:41,380
Це просто вказуючи на
Перший вузол у списку.

581
00:29:41,380 --> 00:29:42,630
Як створити новий вузол?

582
00:29:42,630 --> 00:29:45,490

583
00:29:45,490 --> 00:29:48,070
Якщо мені потрібно простір, щоб створити новий вузол.

584
00:29:48,070 --> 00:29:49,230
Malloc.

585
00:29:49,230 --> 00:29:51,710
І наскільки великий?

586
00:29:51,710 --> 00:30:00,390
>> АУДИТОРІЯ: Розмір структури.

587
00:30:00,390 --> 00:30:01,150
>> Джейсон Хіршхорна:
розмір структури.

588
00:30:01,150 --> 00:30:02,400
І що структура називається?

589
00:30:02,400 --> 00:30:09,670

590
00:30:09,670 --> 00:30:09,840
>> АУДИТОРІЯ: Вузол?

591
00:30:09,840 --> 00:30:11,640
>> Джейсон Хіршхорна: Вузол.

592
00:30:11,640 --> 00:30:17,640
Так Танос (SizeOf (вузол));
дає нам простір.

593
00:30:17,640 --> 00:30:19,740
І ця лінія -

594
00:30:19,740 --> 00:30:21,740
один неправильний на цій лінії.

595
00:30:21,740 --> 00:30:24,430
Є new_node покажчик на структуру?

596
00:30:24,430 --> 00:30:25,650
Це загальна назва.

597
00:30:25,650 --> 00:30:26,520
Що це -

598
00:30:26,520 --> 00:30:27,450
вузол, точно.

599
00:30:27,450 --> 00:30:29,340
Це вузол *.

600
00:30:29,340 --> 00:30:33,010
І що ж нам робити відразу після
ми Malloc щось, Асан?

601
00:30:33,010 --> 00:30:34,476
Що перше, що ми робимо?

602
00:30:34,476 --> 00:30:38,850

603
00:30:38,850 --> 00:30:40,320
Що робити, якщо він не працює?

604
00:30:40,320 --> 00:30:42,430
>> АУДИТОРІЯ: О, перевірити, якщо він
вказує на вузлі?

605
00:30:42,430 --> 00:30:43,310
>> Джейсон Хіршхорна: Абсолютно вірно.

606
00:30:43,310 --> 00:30:46,750
Так що якщо ви new_node дорівнює рівних
нуль, що ж нам робити?

607
00:30:46,750 --> 00:30:51,650

608
00:30:51,650 --> 00:30:54,820
Це повертає логічне значення, цю функцію.

609
00:30:54,820 --> 00:30:57,760
Саме так.

610
00:30:57,760 --> 00:30:58,450
Виглядає добре.

611
00:30:58,450 --> 00:30:59,680
Все, що додати туди?

612
00:30:59,680 --> 00:31:00,670
Ми додамо речі в кінці.

613
00:31:00,670 --> 00:31:03,160
Але що до цих пір виглядає добре.

614
00:31:03,160 --> 00:31:06,170
Створення поточні і попередні покажчики.

615
00:31:06,170 --> 00:31:08,650
Майкл, як я можу це зробити?

616
00:31:08,650 --> 00:31:12,810
>> АУДИТОРІЯ: Ви повинні були б
зробити вузол *.

617
00:31:12,810 --> 00:31:21,800

618
00:31:21,800 --> 00:31:25,502
Ви повинні були б зробити один не
для new_node але для

619
00:31:25,502 --> 00:31:26,905
вузли у нас вже є.

620
00:31:26,905 --> 00:31:27,230
>> Джейсон Хіршхорна: ОК.

621
00:31:27,230 --> 00:31:29,255
Таким чином, поточний вузол ми на.

622
00:31:29,255 --> 00:31:30,505
Я подзвоню, що ин.

623
00:31:30,505 --> 00:31:39,650

624
00:31:39,650 --> 00:31:39,770
Добре.

625
00:31:39,770 --> 00:31:41,620
Ми вирішили, що ми хочемо зберегти
два, тому що ми повинні знати

626
00:31:41,620 --> 00:31:42,870
що перед ним.

627
00:31:42,870 --> 00:31:45,770

628
00:31:45,770 --> 00:31:47,020
Що вони инициализируются?

629
00:31:47,020 --> 00:31:49,874

630
00:31:49,874 --> 00:31:54,180
>> АУДИТОРІЯ: Їх цінність в нашому списку.

631
00:31:54,180 --> 00:31:58,090
>> Джейсон Хіршхорна: Так в чому ж
Перше, що в нашому списку?

632
00:31:58,090 --> 00:32:04,050
Або як ми знаємо, де
початок нашому списку є?

633
00:32:04,050 --> 00:32:08,015
>> АУДИТОРІЯ: Хіба це не пройшло
у функцію?

634
00:32:08,015 --> 00:32:08,466
>> Джейсон Хіршхорна: Вірно.

635
00:32:08,466 --> 00:32:09,716
Він був прийнятий в прямо тут.

636
00:32:09,716 --> 00:32:15,910

637
00:32:15,910 --> 00:32:18,980
Так що, якщо він передається у функцію,
початок списку, що ми повинні

638
00:32:18,980 --> 00:32:21,270
встановити струм, рівний?

639
00:32:21,270 --> 00:32:22,110
>> АУДИТОРІЯ: Список.

640
00:32:22,110 --> 00:32:22,900
>> Джейсон Хіршхорна: Список.

641
00:32:22,900 --> 00:32:24,090
Ось саме.

642
00:32:24,090 --> 00:32:26,290
Тепер він має адресу
початок нашого списку.

643
00:32:26,290 --> 00:32:28,450
А як щодо попередній?

644
00:32:28,450 --> 00:32:31,920
>> АУДИТОРІЯ: Список мінус одна?

645
00:32:31,920 --> 00:32:32,690
>> Джейсон Хіршхорна: Там в
нічого перед ним.

646
00:32:32,690 --> 00:32:34,580
Так що ми можемо зробити, щоб показати, нічого?

647
00:32:34,580 --> 00:32:35,050
>> АУДИТОРІЯ: Null.

648
00:32:35,050 --> 00:32:35,450
>> Джейсон Хіршхорна: Так.

649
00:32:35,450 --> 00:32:37,950
Це звучить як хороша ідея.

650
00:32:37,950 --> 00:32:38,360
Прекрасно.

651
00:32:38,360 --> 00:32:39,630
Спасибо.

652
00:32:39,630 --> 00:32:42,850
Пройтися по списку.

653
00:32:42,850 --> 00:32:45,490
Костянтин, як довго ми будемо
йти за списком?

654
00:32:45,490 --> 00:32:49,010
>> АУДИТОРІЯ: поки ми не досягнемо нульової.

655
00:32:49,010 --> 00:32:49,390
>> Джейсон Хіршхорна: ОК.

656
00:32:49,390 --> 00:32:50,430
Так що якщо, в той час, протягом циклу.

657
00:32:50,430 --> 00:32:52,200
Що ми робимо?

658
00:32:52,200 --> 00:32:53,320
>> АУДИТОРІЯ: Може бути, для циклу?

659
00:32:53,320 --> 00:32:53,910
>> Джейсон Хіршхорна: Давайте зробимо цикл.

660
00:32:53,910 --> 00:32:55,870
ОК.

661
00:32:55,870 --> 00:33:02,465
>> АУДИТОРІЯ: І ми говоримо на -

662
00:33:02,465 --> 00:33:09,764

663
00:33:09,764 --> 00:33:13,390
до поточного покажчика
НЕ дорівнює NULL.

664
00:33:13,390 --> 00:33:19,160
>> Джейсон Хіршхорна: Так що, якщо ми знаємо, що
стан, як ми можемо написати цикл

665
00:33:19,160 --> 00:33:21,740
засновані від цього умови.

666
00:33:21,740 --> 00:33:24,380
Які циклі ми повинні використовувати?

667
00:33:24,380 --> 00:33:25,260
>> АУДИТОРІЯ: У той час як.

668
00:33:25,260 --> 00:33:25,590
>> Джейсон Хіршхорна: Так.

669
00:33:25,590 --> 00:33:27,130
Це має більше сенсу, засновану
від того, що ви сказали.

670
00:33:27,130 --> 00:33:29,430
Якщо ми просто хочемо, щоб увійти в ми це було б
просто знаю, що річ, було б

671
00:33:29,430 --> 00:33:31,680
сенс робити якийсь час циклу.

672
00:33:31,680 --> 00:33:39,880
У той час як струм не дорівнює NULL,
якщо значення менше цього вузла.

673
00:33:39,880 --> 00:33:41,650
Akshar, дай мені цю лінію.

674
00:33:41,650 --> 00:33:48,810

675
00:33:48,810 --> 00:33:56,955
>> АУДИТОРІЯ: Якщо ток-> п
н менш вартості.

676
00:33:56,955 --> 00:34:00,170

677
00:34:00,170 --> 00:34:03,260
Або зворотна що.

678
00:34:03,260 --> 00:34:06,140
Перемикач що кронштейн.

679
00:34:06,140 --> 00:34:06,620
>> Джейсон Хіршхорна: Вибачте.

680
00:34:06,620 --> 00:34:08,760
>> АУДИТОРІЯ: Змініть кронштейн.

681
00:34:08,760 --> 00:34:10,914
>> Джейсон Хіршхорна: Так що, якщо це
більше, ніж значення.

682
00:34:10,914 --> 00:34:18,719

683
00:34:18,719 --> 00:34:22,120
Тому що це помилка з
вище коментар, я збираюся це зробити.

684
00:34:22,120 --> 00:34:22,480
Але так.

685
00:34:22,480 --> 00:34:25,125
Якщо наша цінність менше, ніж це
вузол, що ж нам робити?

686
00:34:25,125 --> 00:34:25,540
О.

687
00:34:25,540 --> 00:34:26,710
У мене є його прямо тут.

688
00:34:26,710 --> 00:34:27,960
Вставте раніше.

689
00:34:27,960 --> 00:34:32,080

690
00:34:32,080 --> 00:34:32,370
ОК.

691
00:34:32,370 --> 00:34:33,933
Як ми це робимо?

692
00:34:33,933 --> 00:34:34,900
>> АУДИТОРІЯ: Це все ще я?

693
00:34:34,900 --> 00:34:36,150
>> Джейсон Хіршхорна: Так.

694
00:34:36,150 --> 00:34:38,520

695
00:34:38,520 --> 00:34:39,770
>> АУДИТОРІЯ: Ви -

696
00:34:39,770 --> 00:34:42,909

697
00:34:42,909 --> 00:34:44,159
new_node-> наступна.

698
00:34:44,159 --> 00:34:46,770

699
00:34:46,770 --> 00:34:50,163
>> Джейсон Хіршхорна: Так в чому
що збирається рівнятися?

700
00:34:50,163 --> 00:34:52,070
>> АУДИТОРІЯ: Це буде рівний струму.

701
00:34:52,070 --> 00:34:53,889
>> Джейсон Хіршхорна: Абсолютно вірно.

702
00:34:53,889 --> 00:34:55,730
І так з іншого -

703
00:34:55,730 --> 00:34:56,730
що ще потрібно для оновлення?

704
00:34:56,730 --> 00:34:59,982
>> АУДИТОРІЯ: Переконайтеся, що повз дорівнює нулю.

705
00:34:59,982 --> 00:35:01,870
>> Джейсон Хіршхорна: Якщо попередня -

706
00:35:01,870 --> 00:35:03,730
так що якщо перед дорівнює нулю.

707
00:35:03,730 --> 00:35:05,990
>> АУДИТОРІЯ: Це означає, що він збирається
стати главою.

708
00:35:05,990 --> 00:35:06,780
>> Джейсон Хіршхорна: Це означає
це стати главою.

709
00:35:06,780 --> 00:35:07,620
Отже, що ж нам робити?

710
00:35:07,620 --> 00:35:12,510
>> АУДИТОРІЯ: Ми робимо голову одно new_node.

711
00:35:12,510 --> 00:35:16,690
>> Джейсон Хіршхорна: Керівник
дорівнює new_node.

712
00:35:16,690 --> 00:35:20,540
І чому очолити тут, не перелічити?

713
00:35:20,540 --> 00:35:24,940
>> АУДИТОРІЯ: Тому що голова є світовим
змінна, яка є відправною точкою.

714
00:35:24,940 --> 00:35:26,190
>> Джейсон Хіршхорна: Солодкий.

715
00:35:26,190 --> 00:35:33,750

716
00:35:33,750 --> 00:35:34,170
ОК.

717
00:35:34,170 --> 00:35:36,150
І -

718
00:35:36,150 --> 00:35:53,796
>> АУДИТОРІЯ: Тоді ви ще перед->
Наступний одно new_node.

719
00:35:53,796 --> 00:35:55,080
А потім ви повернетеся правда.

720
00:35:55,080 --> 00:35:59,560

721
00:35:59,560 --> 00:36:02,700
>> Джейсон Хіршхорна: Куди
ми встановлюємо new_node кінець?

722
00:36:02,700 --> 00:36:04,850
>> Зали: Я -

723
00:36:04,850 --> 00:36:06,180
Я встановив, що на початку.

724
00:36:06,180 --> 00:36:07,430
>> Джейсон Хіршхорна: Так що лінія?

725
00:36:07,430 --> 00:36:10,000

726
00:36:10,000 --> 00:36:12,598
>> АУДИТОРІЯ: Після того, як якщо заява
перевірки, якщо він відомий.

727
00:36:12,598 --> 00:36:13,057
>> Джейсон Хіршхорна: Прямо тут?

728
00:36:13,057 --> 00:36:18,335
>> АУДИТОРІЯ: я зроблю new_node-> п
дорівнює вартості.

729
00:36:18,335 --> 00:36:19,585
>> Джейсон Хіршхорна: Звучить добре.

730
00:36:19,585 --> 00:36:21,740

731
00:36:21,740 --> 00:36:25,090
Напевно, має сенс - ми не робимо
повинні знати, що список ми на

732
00:36:25,090 --> 00:36:26,280
тому що ми маємо справу тільки
з одного списку.

733
00:36:26,280 --> 00:36:29,560
Так краще оголошення функції для
це просто, щоб позбутися цього

734
00:36:29,560 --> 00:36:34,360
цілком і просто вставити
значення в голову.

735
00:36:34,360 --> 00:36:35,930
Ми навіть не повинні знати,
що список ми дюйма

736
00:36:35,930 --> 00:36:39,140
Але я буду тримати його на даний момент і
потім змінити його з модернізації

737
00:36:39,140 --> 00:36:42,590
слайди і код.

738
00:36:42,590 --> 00:36:44,980
Так що добре виглядає на даний момент.

739
00:36:44,980 --> 00:36:46,560
Якщо значення - хто може зробити цю лінію?

740
00:36:46,560 --> 00:36:47,810
Якщо -

741
00:36:47,810 --> 00:36:52,240

742
00:36:52,240 --> 00:36:53,840
що нам робити тут, Ной.

743
00:36:53,840 --> 00:36:57,890

744
00:36:57,890 --> 00:37:07,100
>> АУДИТОРІЯ: Якщо значення більше
ніж вал-> п -

745
00:37:07,100 --> 00:37:16,830

746
00:37:16,830 --> 00:37:18,240
>> Джейсон Хіршхорна: Як зробити
ми йдемо до наступного вузла?

747
00:37:18,240 --> 00:37:27,760

748
00:37:27,760 --> 00:37:30,530
>> АУДИТОРІЯ: Керр-> п
дорівнює new_node.

749
00:37:30,530 --> 00:37:37,630

750
00:37:37,630 --> 00:37:39,195
>> Джейсон Хіршхорна: Так п
яка частина структури?

751
00:37:39,195 --> 00:37:43,065

752
00:37:43,065 --> 00:37:46,020
Ціле.

753
00:37:46,020 --> 00:37:50,420
І new_node є покажчиком на вузол.

754
00:37:50,420 --> 00:37:51,880
Так що частина тек ми повинні оновити?

755
00:37:51,880 --> 00:38:03,900

756
00:38:03,900 --> 00:38:05,400
Якщо не я, то що інша частина?

757
00:38:05,400 --> 00:38:21,680

758
00:38:21,680 --> 00:38:22,810
Ной, що інша частина.

759
00:38:22,810 --> 00:38:23,570
>> АУДИТОРІЯ: О, в наступний.

760
00:38:23,570 --> 00:38:25,645
>> Джейсон Хіршхорна: Далі, точно.

761
00:38:25,645 --> 00:38:26,410
Саме так.

762
00:38:26,410 --> 00:38:28,770
Наступна є правильним.

763
00:38:28,770 --> 00:38:31,540
А що ще потрібно
оновити, Ной?

764
00:38:31,540 --> 00:38:32,840
>> АУДИТОРІЯ: Покажчики.

765
00:38:32,840 --> 00:38:34,840
>> Джейсон Хіршхорна: Так
ми оновили струм.

766
00:38:34,840 --> 00:38:36,090
>> АУДИТОРІЯ: Попередня-> наступна.

767
00:38:36,090 --> 00:38:48,160

768
00:38:48,160 --> 00:38:49,410
>> Джейсон Хіршхорна: Так.

769
00:38:49,410 --> 00:38:57,465

770
00:38:57,465 --> 00:38:58,370
Добре, ми паузу.

771
00:38:58,370 --> 00:39:02,200
Хто може допомогти нам тут?

772
00:39:02,200 --> 00:39:03,385
Ману, що ми повинні робити?

773
00:39:03,385 --> 00:39:05,615
>> АУДИТОРІЯ: Ви повинні встановити
його рівним тек-> наступний.

774
00:39:05,615 --> 00:39:09,110

775
00:39:09,110 --> 00:39:11,630
Але зробити це раніше, ніж в попередньому рядку.

776
00:39:11,630 --> 00:39:12,880
>> Джейсон Хіршхорна: ОК.

777
00:39:12,880 --> 00:39:16,590

778
00:39:16,590 --> 00:39:18,260
Що-небудь ще?

779
00:39:18,260 --> 00:39:19,170
Akshar.

780
00:39:19,170 --> 00:39:22,680
>> АУДИТОРІЯ: Я не думаю, що ти
означало змінити Curr-> наступний.

781
00:39:22,680 --> 00:39:29,270
Я думаю, ви на увазі, щоб зробити вал рівних
вал-> Далі для переходу до наступного вузла.

782
00:39:29,270 --> 00:39:30,500
>> Джейсон Хіршхорна: Так жаль, де?

783
00:39:30,500 --> 00:39:32,680
На якій лінії?

784
00:39:32,680 --> 00:39:33,420
Ця лінія?

785
00:39:33,420 --> 00:39:33,750
>> АУДИТОРІЯ: Так.

786
00:39:33,750 --> 00:39:35,745
Зробити вал дорівнює вал-> наступна.

787
00:39:35,745 --> 00:39:39,690

788
00:39:39,690 --> 00:39:43,360
>> Джейсон Хіршхорна: Так от правильно
оскільки в даний час є

789
00:39:43,360 --> 00:39:45,220
покажчик до вузла.

790
00:39:45,220 --> 00:39:48,550
І ми хочемо, щоб вона вказувала на наступний
вузол, що стає в даний час

791
00:39:48,550 --> 00:39:49,930
вказав на.

792
00:39:49,930 --> 00:39:54,410
Сам Керр має наступний.

793
00:39:54,410 --> 00:39:58,620
Але якби ми мали оновити curr.next, ми
буде оновлювати фактичні відома

794
00:39:58,620 --> 00:40:01,430
сама не там, де це
покажчик вказував.

795
00:40:01,430 --> 00:40:02,680
А як щодо цієї лінії, хоча.

796
00:40:02,680 --> 00:40:05,160

797
00:40:05,160 --> 00:40:07,330
Аві?

798
00:40:07,330 --> 00:40:09,590
>> АУДИТОРІЯ: Попередня-> наступна дорівнює ін.

799
00:40:09,590 --> 00:40:12,500

800
00:40:12,500 --> 00:40:19,440
>> Джейсон Хіршхорна: Отже, ще раз, якщо перед є
покажчик на вузол, перед-> наступний є

801
00:40:19,440 --> 00:40:23,020
Фактичний покажчик у вузлі.

802
00:40:23,020 --> 00:40:27,190
Так що це буде оновлення
покажчик у вузлі до Curr.

803
00:40:27,190 --> 00:40:28,570
Ми не хочемо, щоб оновити
покажчик на вузол.

804
00:40:28,570 --> 00:40:30,570
Ми хочемо, щоб оновити попередній.

805
00:40:30,570 --> 00:40:31,850
Так як же нам це зробити?

806
00:40:31,850 --> 00:40:34,250
>> АУДИТОРІЯ: Було б просто бути пред.

807
00:40:34,250 --> 00:40:34,565
>> Джейсон Хіршхорна: Вірно.

808
00:40:34,565 --> 00:40:35,560
Попередня є покажчиком на вузол.

809
00:40:35,560 --> 00:40:38,750
Тепер ми міняємо його на
Новий покажчик на вузол.

810
00:40:38,750 --> 00:40:40,830
ОК Давайте рухатися вниз.

811
00:40:40,830 --> 00:40:41,940
Нарешті, остання умова.

812
00:40:41,940 --> 00:40:44,896
Джефф, що ми робимо тут?

813
00:40:44,896 --> 00:40:47,515
>> АУДИТОРІЯ: Якщо значення
дорівнює вал-> п.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> Джейсон Хіршхорна: Вибачте.

816
00:40:51,300 --> 00:40:52,372
О боже мій.

817
00:40:52,372 --> 00:40:54,330
Що?

818
00:40:54,330 --> 00:40:55,580
Значення == вал-> п.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Що нам робити?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> АУДИТОРІЯ: Ви б звільнити нашу new_node,
і тоді ви б повернутися помилковим.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> Джейсон Хіршхорна: Це те, що
ми написали досі.

825
00:41:23,460 --> 00:41:25,710
Хто-небудь є нічого
додати, перш ніж зробити?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
ОК.

828
00:41:35,710 --> 00:41:36,960
Давайте спробуємо.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Контроль може дійти до кінця
з не-порожнеча функції.

831
00:41:46,110 --> 00:41:48,310
Аві, що відбувається?

832
00:41:48,310 --> 00:41:51,380
>> АУДИТОРІЯ: Ви повинні поставити повернення
правда за межами час циклу?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> Джейсон Хіршхорна: Я не знаю.

835
00:41:54,400 --> 00:41:54,780
Ви хочете, щоб я?

836
00:41:54,780 --> 00:41:55,520
>> АУДИТОРІЯ: Не беріть в голову.

837
00:41:55,520 --> 00:41:56,350
Ні.

838
00:41:56,350 --> 00:41:57,180
>> Джейсон Хіршхорна: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> Зали: Я думаю, що ви призначені для
покласти повернення помилковим наприкінці

840
00:41:59,460 --> 00:42:02,230
з той час циклу.

841
00:42:02,230 --> 00:42:03,270
>> Джейсон Хіршхорна: То де
Ви хочете, щоб це пішло?

842
00:42:03,270 --> 00:42:05,270
>> АУДИТОРІЯ: Як за той час циклу.

843
00:42:05,270 --> 00:42:08,800
Так що, якщо ви виходите з той час як цикл Це означає, що
що ви дійшли до кінця і

844
00:42:08,800 --> 00:42:09,980
нічого не трапилося.

845
00:42:09,980 --> 00:42:10,410
>> Джейсон Хіршхорна: ОК.

846
00:42:10,410 --> 00:42:12,340
Так що ж нам робити тут?

847
00:42:12,340 --> 00:42:13,702
>> АУДИТОРІЯ: Ви повернутися помилковим
там же.

848
00:42:13,702 --> 00:42:15,040
>> Джейсон Хіршхорна: О, ми
зробити це в обох місцях?

849
00:42:15,040 --> 00:42:15,650
>> АУДИТОРІЯ: Так.

850
00:42:15,650 --> 00:42:16,900
>> Джейсон Хіршхорна: ОК.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Якщо ми йдемо?

853
00:42:26,160 --> 00:42:26,980
О боже мій.

854
00:42:26,980 --> 00:42:27,290
Мені дуже шкода.

855
00:42:27,290 --> 00:42:28,480
Я прошу вибачення за екрану.

856
00:42:28,480 --> 00:42:30,530
Це свого роду безконтрольного поведінки на нас.

857
00:42:30,530 --> 00:42:31,520
Так що вибирайте опцію.

858
00:42:31,520 --> 00:42:35,260
Нуль, відповідно до кодом, виходить з програми.

859
00:42:35,260 --> 00:42:36,700
Один вставляє щось.

860
00:42:36,700 --> 00:42:37,990
Давайте вставити три.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
Вставка була успішною.

863
00:42:45,380 --> 00:42:46,500
Я збираюся роздрукувати.

864
00:42:46,500 --> 00:42:48,050
Я не маю нічого.

865
00:42:48,050 --> 00:42:48,450
ОК.

866
00:42:48,450 --> 00:42:50,250
Може бути, це була просто випадковість.

867
00:42:50,250 --> 00:42:52,810
Вставте один.

868
00:42:52,810 --> 00:42:55,770
Чи не успішним.

869
00:42:55,770 --> 00:42:57,470
ОК.

870
00:42:57,470 --> 00:43:02,400
Давайте розглянемо GDB дуже швидко
щоб перевірити, що відбувається.

871
00:43:02,400 --> 00:43:06,055
>> Запам'ятати GDB. / Ім'я вашого
Програма отримує нас в GDB.

872
00:43:06,055 --> 00:43:07,610
Багато це чи мало, щоб впоратися?

873
00:43:07,610 --> 00:43:08,560
Блимає?

874
00:43:08,560 --> 00:43:10,400
Напевно.

875
00:43:10,400 --> 00:43:12,760
Закрийте очі і зробіть кілька глибоких
дихає, якщо ви втомлюєтеся

876
00:43:12,760 --> 00:43:13,580
дивитися на це.

877
00:43:13,580 --> 00:43:14,200
Я в GDB.

878
00:43:14,200 --> 00:43:15,830
Що перше, що я роблю в GDB?

879
00:43:15,830 --> 00:43:17,050
Ми повинні з'ясувати,
що відбувається тут.

880
00:43:17,050 --> 00:43:17,310
Давайте подивимося.

881
00:43:17,310 --> 00:43:21,650
У нас є шість хвилин, щоб зрозуміти
, Що відбувається.

882
00:43:21,650 --> 00:43:22,900
Перерва основною.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
А потім що мені робити?

885
00:43:28,130 --> 00:43:29,180
Карлос?

886
00:43:29,180 --> 00:43:31,060
Запустіть.

887
00:43:31,060 --> 00:43:32,250
ОК.

888
00:43:32,250 --> 00:43:34,160
Давайте виберемо опцію.

889
00:43:34,160 --> 00:43:36,330
І що N робити?

890
00:43:36,330 --> 00:43:38,480
Наступна.

891
00:43:38,480 --> 00:43:38,950
Так.

892
00:43:38,950 --> 00:43:39,740
>> АУДИТОРІЯ: Ви не згадали -

893
00:43:39,740 --> 00:43:45,230
ти не сказав, що глава, це було
инициализируется нулем на початку.

894
00:43:45,230 --> 00:43:47,140
Але я думав, ви сказали, що було в порядку.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> Джейсон Хіршхорна: Поїхали - давайте подивимося
в GDB, а потім ми повернемося.

897
00:43:52,640 --> 00:43:54,910
Але це звучить як у вас вже є
деякі ідеї про те, що відбувається.

898
00:43:54,910 --> 00:43:58,340
Тому ми хочемо, щоб вставити щось.

899
00:43:58,340 --> 00:43:59,390
ОК.

900
00:43:59,390 --> 00:44:00,150
Ми вставити.

901
00:44:00,150 --> 00:44:00,770
Будь ласка, введіть Int.

902
00:44:00,770 --> 00:44:01,990
Ми вставити три.

903
00:44:01,990 --> 00:44:03,000
А потім я на цій лінії.

904
00:44:03,000 --> 00:44:07,030
Як я можу йти почати налагодження
вставка відомо функцію?

905
00:44:07,030 --> 00:44:08,280
О боже мій.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Це багато.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Хіба що хвилююся багато?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> АУДИТОРІЯ: О, це помер.

912
00:44:21,680 --> 00:44:22,930
>> Джейсон Хіршхорна: Я просто
витягнув його.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
ОК.

915
00:44:28,310 --> 00:44:29,560
>> АУДИТОРІЯ: Може бути, це
Інший кінець дроту.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> Джейсон Хіршхорна: Нічого собі.

918
00:44:39,470 --> 00:44:42,330
Так суть -

919
00:44:42,330 --> 00:44:43,470
що ти сказав?

920
00:44:43,470 --> 00:44:46,040
>> Зали: Я сказав, що іронія технічна
Труднощі в цьому класі.

921
00:44:46,040 --> 00:44:46,410
>> Джейсон Хіршхорна: Я знаю.

922
00:44:46,410 --> 00:44:48,660
Якби тільки я мав контроль над цією частиною.

923
00:44:48,660 --> 00:44:49,910
[Нерозбірливості]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Це звучить здорово.

926
00:44:55,400 --> 00:44:58,680
Чому б вам не почати думати про
те, що ми могли б зробити так,

927
00:44:58,680 --> 00:45:01,140
і ми повернемося в 90 секунд.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, я збираюся запитати вас, як йти
всередині insert_node налагодити його.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Так що це, де ми востаннє зупинилися.

932
00:46:31,460 --> 00:46:35,110
Як я можу йти всередині insert_node, Avica,
вивчити, що відбувається?

933
00:46:35,110 --> 00:46:36,360
Яка команда GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Перерва не візьме мене всередині.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Чи знає маркіза?

938
00:46:47,130 --> 00:46:48,240
>> АУДИТОРІЯ: Що?

939
00:46:48,240 --> 00:46:51,780
>> Джейсон Хіршхорна: Яка команда GDB
Я використовую, щоб зайти всередину цієї функції?

940
00:46:51,780 --> 00:46:52,070
>> АУДИТОРІЯ: Крок?

941
00:46:52,070 --> 00:46:55,140
>> Джейсон Хіршхорна: Крок через
С. Це бере мене всередині.

942
00:46:55,140 --> 00:46:55,476
ОК.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing деякий простір.

944
00:46:58,040 --> 00:46:59,120
Це все виглядає як його збираються.

945
00:46:59,120 --> 00:47:00,370
Давайте розглянемо new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
Він отримав деяку адресу пам'яті.

948
00:47:05,410 --> 00:47:07,440
Давайте перевіримо -

949
00:47:07,440 --> 00:47:08,500
це все правильно.

950
00:47:08,500 --> 00:47:12,220
Так що все тут, здається,
працює правильно.

951
00:47:12,220 --> 00:47:14,530
>> АУДИТОРІЯ: У чому різниця
між Р і дисплея?

952
00:47:14,530 --> 00:47:16,160
>> Джейсон Хіршхорна: Р позначає для друку.

953
00:47:16,160 --> 00:47:19,310
І так ви питаєте у чому
Різниця між цим і цим?

954
00:47:19,310 --> 00:47:22,330
У цьому випадку, нічого.

955
00:47:22,330 --> 00:47:26,960
Але в цілому є
деякі відмінності.

956
00:47:26,960 --> 00:47:28,220
І ви повинні дивитися в керівництві GDB.

957
00:47:28,220 --> 00:47:29,560
Але в даному випадку, нічого.

958
00:47:29,560 --> 00:47:31,460
Ми схильні використовувати печатку, хоча, тому що
нам не потрібно робити набагато більше, ніж

959
00:47:31,460 --> 00:47:33,960
роздрукувати одне значення.

960
00:47:33,960 --> 00:47:34,640
>> ОК.

961
00:47:34,640 --> 00:47:40,300
Таким чином, ми знаходимося на лінії 80 нашого коду,
установка вузла * Curr рівну списку.

962
00:47:40,300 --> 00:47:42,500
Давайте роздрукувати ін.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
Вона дорівнює список.

965
00:47:46,840 --> 00:47:48,850
Солодкий.

966
00:47:48,850 --> 00:47:49,340
Зачекайте.

967
00:47:49,340 --> 00:47:50,590
Вона дорівнює щось.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Це не здається правильним.

970
00:47:56,190 --> 00:47:56,840
Там ми йдемо.

971
00:47:56,840 --> 00:47:59,470
Це тому, що в GDB, праворуч, якщо
це лінія ти на ньому

972
00:47:59,470 --> 00:48:00,330
ще не виконане.

973
00:48:00,330 --> 00:48:03,100
Так що вам потрібно насправді тип
Наступний виконати лінію

974
00:48:03,100 --> 00:48:05,230
перш, ніж бачити його результати.

975
00:48:05,230 --> 00:48:06,680
І ось ми.

976
00:48:06,680 --> 00:48:09,490
Ми тільки що виконали цю лінію,
попередня дорівнює нулю.

977
00:48:09,490 --> 00:48:13,590
Отже, ще раз, якщо ми друкуємо попередня
ми не побачимо нічого дивного.

978
00:48:13,590 --> 00:48:18,680
Але якщо ми насправді виконати, що
лінія, то ми побачимо,

979
00:48:18,680 --> 00:48:20,380
що ця лінія працювала.

980
00:48:20,380 --> 00:48:21,060
>> Тому у нас є ін.

981
00:48:21,060 --> 00:48:23,180
Ті, обидва хороші.

982
00:48:23,180 --> 00:48:24,010
Чи не так?

983
00:48:24,010 --> 00:48:28,130
Зараз ми знаходимося на цій лінії прямо тут.

984
00:48:28,130 --> 00:48:29,310
У той час як вал НЕ дорівнює NULL.

985
00:48:29,310 --> 00:48:31,110
Ну, що робить вал рівні?

986
00:48:31,110 --> 00:48:32,450
Ми тільки що бачили він дорівнював нулю.

987
00:48:32,450 --> 00:48:33,210
Ми надрукували його.

988
00:48:33,210 --> 00:48:35,110
Я роздрукувати його знову.

989
00:48:35,110 --> 00:48:36,720
Так що поки петля
буде виконувати?

990
00:48:36,720 --> 00:48:37,270
>> АУДИТОРІЯ: Ні.

991
00:48:37,270 --> 00:48:39,790
>> Джейсон Хіршхорна: Так що, коли я набрав, що
лінія, ви бачите, ми вскочили на всьому шляху

992
00:48:39,790 --> 00:48:41,390
вниз до основи, повернутися помилковим.

993
00:48:41,390 --> 00:48:44,520
А потім ми збираємося повернутися помилковим
і повернутися до нашої програми і

994
00:48:44,520 --> 00:48:48,020
зрештою роздрукувати, як ми бачили,
вставка була успішною.

995
00:48:48,020 --> 00:48:51,010
Так, у когось є якісь ідеї про те, що
ми повинні зробити, щоб це виправити?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Я збираюся чекати, поки я не бачу
пару рук вгору.

998
00:48:57,570 --> 00:48:58,830
Ми не виконати це.

999
00:48:58,830 --> 00:49:01,660
Майте на увазі, це був перший
що ми робили.

1000
00:49:01,660 --> 00:49:02,430
Я не збираюся зробити пару.

1001
00:49:02,430 --> 00:49:03,670
Я збираюся зробити декілька.

1002
00:49:03,670 --> 00:49:04,830
Тому що пару означає два.

1003
00:49:04,830 --> 00:49:07,620
Я буду чекати більше двох.

1004
00:49:07,620 --> 00:49:10,690
>> Перший вставка, вал,
за замовчуванням дорівнює нулю.

1005
00:49:10,690 --> 00:49:14,050
І цей цикл виконується тільки
якщо вал не є нульовим.

1006
00:49:14,050 --> 00:49:18,740
Так як я можу обійти це?

1007
00:49:18,740 --> 00:49:19,990
Я бачу три руки.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Я буду чекати більше трьох.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Маркус, що ти думаєш?

1012
00:49:35,940 --> 00:49:37,730
>> АУДИТОРІЯ: Ну, якщо вам це потрібно, щоб
виконати більше одного разу, ви просто

1013
00:49:37,730 --> 00:49:39,948
змінити його на зроби час циклу.

1014
00:49:39,948 --> 00:49:41,250
>> Джейсон Хіршхорна: ОК.

1015
00:49:41,250 --> 00:49:44,240
Чи буде це вирішити нашу проблему, хоча?

1016
00:49:44,240 --> 00:49:47,750
>> НЕ AUDIENCE: У цьому випадку немає через
той факт, що список порожній.

1017
00:49:47,750 --> 00:49:52,150
Так то ви, мабуть, просто потрібно додати
заяву, що якщо цикл завершується

1018
00:49:52,150 --> 00:49:55,312
то ви повинні бути в кінці
список, після чого вас

1019
00:49:55,312 --> 00:49:56,562
можна просто вставити її.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> Джейсон Хіршхорна: Мені це подобається.

1022
00:49:59,680 --> 00:50:00,500
Це має сенс.

1023
00:50:00,500 --> 00:50:03,390
Якщо цикл виходить -

1024
00:50:03,390 --> 00:50:04,800
тому що це буде повернення помилковим тут.

1025
00:50:04,800 --> 00:50:08,220
Так що, якщо цикл завершується, то ми на
кінець списку, або, може бути

1026
00:50:08,220 --> 00:50:10,690
початок списку, якщо немає нічого в
це, яке є таким же, як в кінці.

1027
00:50:10,690 --> 00:50:12,770
Так що тепер ми хочемо, щоб вставити
щось тут.

1028
00:50:12,770 --> 00:50:17,380
Так як же цей код шукати, Маркус?

1029
00:50:17,380 --> 00:50:21,600
>> АУДИТОРІЯ: Якщо у вас вже є вузол
malloced, ви могли б просто сказати,

1030
00:50:21,600 --> 00:50:25,400
new_node-> наступна дорівнює нуль, тому що
він повинен бути в кінці.

1031
00:50:25,400 --> 00:50:27,510
Або new_node-> наступна дорівнює нулю.

1032
00:50:27,510 --> 00:50:27,765
>> Джейсон Хіршхорна: ОК.

1033
00:50:27,765 --> 00:50:28,190
Вибачте.

1034
00:50:28,190 --> 00:50:35,760
New_node-> наступна одно нуль
, Тому що ми знаходимося в кінці.

1035
00:50:35,760 --> 00:50:36,460
Це не покласти його дюйма

1036
00:50:36,460 --> 00:50:37,710
Як ми покласти його у списку?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Вірно.

1039
00:50:46,460 --> 00:50:47,750
Ось тільки поклавши її рівною.

1040
00:50:47,750 --> 00:50:50,940
Ні, як же ми насправді
покласти його у списку?

1041
00:50:50,940 --> 00:50:54,170
Що вказуючи на
кінець списку?

1042
00:50:54,170 --> 00:50:56,090
>> АУДИТОРІЯ: зав.

1043
00:50:56,090 --> 00:50:57,566
>> Джейсон Хіршхорна: Вибачте?

1044
00:50:57,566 --> 00:50:59,440
>> АУДИТОРІЯ: керівник вказує
в кінці списку.

1045
00:50:59,440 --> 00:51:01,480
>> Джейсон Хіршхорна: Якщо немає нічого в
список, голова вказуючи на

1046
00:51:01,480 --> 00:51:04,170
кінець списку.

1047
00:51:04,170 --> 00:51:06,920
Так що буду працювати на
Перший вставки.

1048
00:51:06,920 --> 00:51:09,810
Що, якщо є кілька
речі в списку?

1049
00:51:09,810 --> 00:51:12,470
Чим ми не хочемо, щоб встановити
очолити одно new_node.

1050
00:51:12,470 --> 00:51:13,790
Що ми хочемо, щоб там робити?

1051
00:51:13,790 --> 00:51:15,610
Так?

1052
00:51:15,610 --> 00:51:16,860
Напевно попередній.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Чи буде це працювати?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Нагадаємо, що попередня просто
покажчик на вузол.

1057
00:51:33,050 --> 00:51:34,770
І попередня є локальної змінної.

1058
00:51:34,770 --> 00:51:38,080
Так ця лінія буде встановлена ​​локальна змінна,
попередній, рівною або

1059
00:51:38,080 --> 00:51:39,380
вказуючи на цьому новому вузлі.

1060
00:51:39,380 --> 00:51:41,500
Це не буде насправді поклав його
в нашому списку, хоча.

1061
00:51:41,500 --> 00:51:44,330
Як ми покласти його в нашому списку?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> Зали: Я думаю, що ви
зробити поточний-> Next.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> Джейсон Хіршхорна: ОК.

1066
00:51:52,550 --> 00:51:54,010
вал-> наступна.

1067
00:51:54,010 --> 00:51:58,768
Отже, ще раз, єдина причина, ми вниз
ось, що значить струм, рівний?

1068
00:51:58,768 --> 00:51:59,760
>> АУДИТОРІЯ: Дорівнює нулю.

1069
00:51:59,760 --> 00:52:01,790
>> Джейсон Хіршхорна: І так, що
відбудеться, якщо ми робимо нуль-> далі?

1070
00:52:01,790 --> 00:52:02,810
Що ми збираємося отримати?

1071
00:52:02,810 --> 00:52:04,060
Ми отримаємо помилку сегментації.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> АУДИТОРІЯ: Do вал дорівнює нулю.

1074
00:52:08,880 --> 00:52:10,760
>> Джейсон Хіршхорна: Це те ж саме,
як попередня, хоча, тому що є

1075
00:52:10,760 --> 00:52:12,820
локальна змінна ми встановлюємо
рівним цьому новому вузлу.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Давайте повернемося до нашої картині
вставки щось.

1078
00:52:20,920 --> 00:52:25,500
Скажіть, що ми, включивши в кінці
зі списку, так прямо тут.

1079
00:52:25,500 --> 00:52:30,010
У нас є поточний покажчик Це
вказуючи на нуль і попередній пункт

1080
00:52:30,010 --> 00:52:32,800
який, вказуючи на 8.

1081
00:52:32,800 --> 00:52:35,330
Так що ж нам потрібно оновити, Аві?

1082
00:52:35,330 --> 00:52:36,680
>> АУДИТОРІЯ: Попередній-> далі?

1083
00:52:36,680 --> 00:52:41,980
>> Джейсон Хіршхорна: Попередній-> наступна є те, що
ми хочемо оновити, бо

1084
00:52:41,980 --> 00:52:44,960
насправді вставити його в
кінець списку.

1085
00:52:44,960 --> 00:52:47,220
У нас ще є одна помилка, проте,
що ми збираємося запустити в.

1086
00:52:47,220 --> 00:52:50,090
Що це помилка?

1087
00:52:50,090 --> 00:52:50,790
Так?

1088
00:52:50,790 --> 00:52:53,860
>> АУДИТОРІЯ: Це збирається повернутися
брехня в цьому випадку?

1089
00:52:53,860 --> 00:52:56,380
>> Джейсон Хіршхорна: О, це буде
збирається повернутися помилковим.

1090
00:52:56,380 --> 00:52:57,430
Але є й інша помилка.

1091
00:52:57,430 --> 00:52:58,930
Тому ми повинні поставити замість істинного.

1092
00:52:58,930 --> 00:53:01,370
>> АУДИТОРІЯ: Чи є попередня раніше, дорівнює
нуль у верхній частині списку?

1093
00:53:01,370 --> 00:53:03,645
>> Джейсон Хіршхорна: Так попередня ще
дорівнює нуль на самому початку.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Так як ми можемо подолати це?

1096
00:53:10,440 --> 00:53:10,950
Так?

1097
00:53:10,950 --> 00:53:15,280
>> Зали: Я думаю, що ви можете зробити чек
до в той час як цикл, щоб переконатися, що це

1098
00:53:15,280 --> 00:53:16,610
порожній список.

1099
00:53:16,610 --> 00:53:17,000
>> Джейсон Хіршхорна: ОК.

1100
00:53:17,000 --> 00:53:17,710
Так що давайте йти сюди.

1101
00:53:17,710 --> 00:53:18,530
У чек.

1102
00:53:18,530 --> 00:53:19,380
Якщо -

1103
00:53:19,380 --> 00:53:20,770
>> АУДИТОРІЯ: Так що, якщо керівник
дорівнює дорівнює нулю.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> Джейсон Хіршхорна: Якщо голова
дорівнює дорівнює нуль -

1106
00:53:26,320 --> 00:53:27,790
що нам скаже, якщо це порожній список.

1107
00:53:27,790 --> 00:53:31,090
>> АУДИТОРІЯ: І тоді ви
зробити глава одно нова.

1108
00:53:31,090 --> 00:53:34,740
>> Джейсон Хіршхорна: Керівник
дорівнює new_node?

1109
00:53:34,740 --> 00:53:35,730
А що ще потрібно зробити?

1110
00:53:35,730 --> 00:53:37,020
>> АУДИТОРІЯ: А потім ви повернетеся правда.

1111
00:53:37,020 --> 00:53:37,535
>> Джейсон Хіршхорна: Не зовсім.

1112
00:53:37,535 --> 00:53:38,785
Ми не вистачає на один крок.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> АУДИТОРІЯ: new_node поруч
повинен вказувати на нуль.

1115
00:53:43,710 --> 00:53:44,570
>> Джейсон Хіршхорна: Точно, Олден.

1116
00:53:44,570 --> 00:53:46,600
І тоді ми зможемо повернутися вірно.

1117
00:53:46,600 --> 00:53:47,560
ОК.

1118
00:53:47,560 --> 00:53:51,630
Але це все ще хороша ідея, щоб робити речі,
в кінці списку, чи не так?

1119
00:53:51,630 --> 00:53:51,950
Добре.

1120
00:53:51,950 --> 00:53:54,450
Ми як і раніше може насправді отримати
в кінці списку.

1121
00:53:54,450 --> 00:53:57,870
Так це код прекрасно, якщо ми на
кінець списку і є деякі

1122
00:53:57,870 --> 00:53:59,120
речі в списку?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Чи не так?

1125
00:54:02,040 --> 00:54:03,540
Тому що у нас ще є ідея Маркуса.

1126
00:54:03,540 --> 00:54:06,870
Ми могли б вийти з цього циклу, тому що
ми в кінці списку.

1127
00:54:06,870 --> 00:54:09,308
Так що ми як і раніше хочемо, щоб цей
код тут?

1128
00:54:09,308 --> 00:54:10,520
>> АУДИТОРІЯ: Так.

1129
00:54:10,520 --> 00:54:11,000
>> Джейсон Хіршхорна: Так.

1130
00:54:11,000 --> 00:54:14,190
І те, що нам потрібно змінити це?

1131
00:54:14,190 --> 00:54:15,440
Правда.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Це звучить добре
всім досі?

1134
00:54:21,640 --> 00:54:22,420
Хто-небудь є будь-яка -

1135
00:54:22,420 --> 00:54:23,480
Аві, у вас є, що додати?

1136
00:54:23,480 --> 00:54:23,920
>> АУДИТОРІЯ: Ні.

1137
00:54:23,920 --> 00:54:25,276
>> Джейсон Хіршхорна: ОК.

1138
00:54:25,276 --> 00:54:27,010
Таким чином, ми зробили кілька змін.

1139
00:54:27,010 --> 00:54:29,540
Ми зробили цю перевірку перш, ніж ми
займався порожній список.

1140
00:54:29,540 --> 00:54:31,790
Таким чином, ми подбали про порожній список.

1141
00:54:31,790 --> 00:54:35,500
І ось ми подбали про вставці
щось в кінці списку.

1142
00:54:35,500 --> 00:54:38,930
Так що, схоже, як це в той час як петлі взяття
догляд за речами між ними,

1143
00:54:38,930 --> 00:54:41,920
десь в списку, якщо є
речі в списку.

1144
00:54:41,920 --> 00:54:42,280
>> ОК.

1145
00:54:42,280 --> 00:54:44,310
Давайте запустити цю програму ще раз.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Чи не успішним.

1148
00:54:50,755 --> 00:54:52,190
>> АУДИТОРІЯ: Ви не зробили це.

1149
00:54:52,190 --> 00:54:53,940
>> Джейсон Хіршхорна: О,
Я не робив це.

1150
00:54:53,940 --> 00:54:56,250
Хороше запитання, Майкл.

1151
00:54:56,250 --> 00:54:57,500
Давайте додамо марку пов'язані між собою.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Лінія 87 є помилка.

1154
00:55:04,830 --> 00:55:05,420
Лінія 87.

1155
00:55:05,420 --> 00:55:06,600
Олден, це була лінія ви мені дали.

1156
00:55:06,600 --> 00:55:08,962
Що не так?

1157
00:55:08,962 --> 00:55:10,710
>> АУДИТОРІЯ: Вона повинна бути на нуль.

1158
00:55:10,710 --> 00:55:11,000
>> Джейсон Хіршхорна: Відмінно.

1159
00:55:11,000 --> 00:55:11,630
Абсолютно вірно.

1160
00:55:11,630 --> 00:55:13,290
Він повинен бути нульовим.

1161
00:55:13,290 --> 00:55:15,210
Давайте зробимо знову.

1162
00:55:15,210 --> 00:55:17,220
Компіляція.

1163
00:55:17,220 --> 00:55:17,890
ОК.

1164
00:55:17,890 --> 00:55:19,400
Давайте вставити три.

1165
00:55:19,400 --> 00:55:20,570
Вставка була успішною.

1166
00:55:20,570 --> 00:55:21,660
Давайте роздрукувати його.

1167
00:55:21,660 --> 00:55:23,590
О, якби ми могли перевірити.

1168
00:55:23,590 --> 00:55:25,500
Але ми ще не зробили
роздрукувати функцію ще.

1169
00:55:25,500 --> 00:55:27,840
Давайте введемо щось ще.

1170
00:55:27,840 --> 00:55:29,090
Що ми повинні ввести?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> АУДИТОРІЯ: Сім.

1173
00:55:31,940 --> 00:55:33,340
>> Джейсон Хіршхорна: Сім?

1174
00:55:33,340 --> 00:55:34,590
>> АУДИТОРІЯ: Так.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> Джейсон Хіршхорна: У нас є несправність сегм.

1177
00:55:39,780 --> 00:55:43,760
Таким чином, ми отримали один, але ми чітко
не може отримати два.

1178
00:55:43,760 --> 00:55:45,690
Це 5:07.

1179
00:55:45,690 --> 00:55:48,370
Таким чином, ми могли налагодити цей
протягом трьох хвилин.

1180
00:55:48,370 --> 00:55:51,240
Але я збираюся залишити нас тут
і рухатися далі на хеши.

1181
00:55:51,240 --> 00:55:54,290
Але, знову ж, відповіді на цей код
Я буду відправити його до вас у небагато.

1182
00:55:54,290 --> 00:55:55,440
Ми дуже близькі до нього.

1183
00:55:55,440 --> 00:55:58,300
Я настійно рекомендую вам, щоб з'ясувати,
що відбувається тут і виправити її.

1184
00:55:58,300 --> 00:56:02,400
Так що я буду вам по електронній пошті цей код, як
добре плюс рішення -

1185
00:56:02,400 --> 00:56:03,670
ймовірно, рішення пізніше.

1186
00:56:03,670 --> 00:56:05,110
Вперше цей код.

1187
00:56:05,110 --> 00:56:08,290
>> Інша річ, що я хочу зробити, перш ніж ми
обробка ми не звільнили нічого.

1188
00:56:08,290 --> 00:56:10,370
Так що я хочу показати вам, що
Valgrind виглядає.

1189
00:56:10,370 --> 00:56:14,310
Якщо ми запустимо кордону Valgrind
на нашій програмі,. / пов'язані між собою.

1190
00:56:14,310 --> 00:56:22,540
Знову ж, відповідно з цим слайді, ми
повинен працювати Valgrind з деяким типом

1191
00:56:22,540 --> 00:56:26,410
варіант, в даному випадку
- Витік перевірка = повний.

1192
00:56:26,410 --> 00:56:27,660
Так давайте напишемо Valgrind
- Витік перевірка = повний.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Так що це буде працювати Valgrind
на нашій програмі.

1195
00:56:35,080 --> 00:56:37,000
А тепер програма насправді працює.

1196
00:56:37,000 --> 00:56:40,190
Так що ми збираємося запустити його так само, як
перш, покласти щось дюйма

1197
00:56:40,190 --> 00:56:40,830
Я збираюся поставити в трьох.

1198
00:56:40,830 --> 00:56:41,790
Це працює.

1199
00:56:41,790 --> 00:56:43,202
Я не збираюся, щоб спробувати покласти в чомусь
ще, тому що ми збираємося

1200
00:56:43,202 --> 00:56:44,710
отримати сегм хибним в цьому випадку.

1201
00:56:44,710 --> 00:56:46,700
Так що я просто хочу, щоб кинути палити.

1202
00:56:46,700 --> 00:56:50,160
>> І тепер ви бачите тут
витоку і резюме купа.

1203
00:56:50,160 --> 00:56:52,310
Це хороші речі, які
Ви хочете, щоб перевірити.

1204
00:56:52,310 --> 00:56:56,780
Таким чином, резюме купа - це говорить, у використанні
на виході - вісім байт в одному блоці.

1205
00:56:56,780 --> 00:56:58,370
Це один блок є
вузол ми malloced.

1206
00:56:58,370 --> 00:57:02,230
Майкл, ти вже говорив вузол вісім
укуси, оскільки він має ціле

1207
00:57:02,230 --> 00:57:02,680
і покажчик.

1208
00:57:02,680 --> 00:57:04,550
Так ось наш вузол.

1209
00:57:04,550 --> 00:57:08,170
А потім каже, що ми використовували Танос
сім разів, і ми звільнили

1210
00:57:08,170 --> 00:57:08,940
щось в шість разів.

1211
00:57:08,940 --> 00:57:13,680
Але ми ніколи не називається вільним, так що я не
Ідея, що це говорить.

1212
00:57:13,680 --> 00:57:18,490
>> Але досить сказати, що, коли ваш
програма запускається, Танос в даний час називається

1213
00:57:18,490 --> 00:57:20,330
в деяких інших місцях, які ми
не потрібно турбуватися.

1214
00:57:20,330 --> 00:57:22,460
Так Танос, ймовірно, називається
в деяких місцях.

1215
00:57:22,460 --> 00:57:24,480
Нам не потрібно турбуватися, де.

1216
00:57:24,480 --> 00:57:26,240
Але це дійсно нам.

1217
00:57:26,240 --> 00:57:27,380
Це перша лінія це ми.

1218
00:57:27,380 --> 00:57:28,320
Ми залишили цей блок.

1219
00:57:28,320 --> 00:57:30,330
І ви бачите, що тут
в резюме витоку.

1220
00:57:30,330 --> 00:57:31,950
Проте дістатися -

1221
00:57:31,950 --> 00:57:32,930
вісім байт в одному блоці.

1222
00:57:32,930 --> 00:57:34,100
Це означає, що пам'ять -

1223
00:57:34,100 --> 00:57:35,730
ми просочилися, що пам'ять.

1224
00:57:35,730 --> 00:57:37,570
Виразно втратив -

1225
00:57:37,570 --> 00:57:38,770
щось втрачається назавжди.

1226
00:57:38,770 --> 00:57:40,590
Як правило, ви не будете
бачу нічого там.

1227
00:57:40,590 --> 00:57:44,780
Проте дістатися, як правило, де
ви побачите речі, де ви хочете,

1228
00:57:44,780 --> 00:57:48,900
дивитися, щоб побачити, який код повинен Ви
звільнили, але Ви забули звільнити.

1229
00:57:48,900 --> 00:57:53,170
>> І потім, якщо це було не так,
якби ми зробили безкоштовний все,

1230
00:57:53,170 --> 00:57:54,360
ми можемо перевірити, що.

1231
00:57:54,360 --> 00:57:57,330
Давайте просто запустити програму
ставлячи ні в що.

1232
00:57:57,330 --> 00:57:59,800
Ви побачите тут, у використанні на виході -

1233
00:57:59,800 --> 00:58:01,310
нульові байти в нульових блоків.

1234
00:58:01,310 --> 00:58:06,310
Це означає, що ми нічого не залишилося
коли вийшов ця програма.

1235
00:58:06,310 --> 00:58:12,090
Так, перш ніж включати в pset6, запустіть Valgrind
і переконайтеся, що у вас немає

1236
00:58:12,090 --> 00:58:15,310
просочується будь-яка пам'ять у вашій програмі.

1237
00:58:15,310 --> 00:58:17,910
Якщо у вас є будь-які питання з Valgrind,
не соромтеся звернутися.

1238
00:58:17,910 --> 00:58:18,700
Але це, як ви його використовуєте.

1239
00:58:18,700 --> 00:58:20,890
Дуже просто - подивитися, якщо ви
є у використанні на виході -

1240
00:58:20,890 --> 00:58:22,270
будь байт будь-яких блоків.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Так ми працювали над вставки вузла.

1243
00:58:29,580 --> 00:58:33,840
У мене було два інших функцій тут -
роздрукувати вузлів і безкоштовні вузли.

1244
00:58:33,840 --> 00:58:37,780
Знову ж, ці функції, які
буде добре для вас на практиці

1245
00:58:37,780 --> 00:58:40,990
тому що вони допоможуть вам не тільки з
ці приклади вправ, а й

1246
00:58:40,990 --> 00:58:42,180
з проблеми встановити.

1247
00:58:42,180 --> 00:58:44,230
Вони карту на досить близько до речей
ви збираєтеся потрібно зробити в

1248
00:58:44,230 --> 00:58:45,010
Проблема встановити.

1249
00:58:45,010 --> 00:58:47,640
Але я хочу, щоб переконатися,
ми торкнемося всього.

1250
00:58:47,640 --> 00:58:50,400
І хеш-таблиці також мають вирішальне значення для
що ми робимо в розділі цієї

1251
00:58:50,400 --> 00:58:51,980
тиждень - або в наборі проблеми.

1252
00:58:51,980 --> 00:58:55,200
>> Так що ми збираємося закінчити розділ
говорити про хеш-таблиці.

1253
00:58:55,200 --> 00:58:58,140
Якщо ви помітите, що я зробив
трохи хеш-таблиці.

1254
00:58:58,140 --> 00:59:00,020
Тобто не те, що ми говоримо
о, однако.

1255
00:59:00,020 --> 00:59:03,540
Ми говоримо про другий
тип хеш-таблиці.

1256
00:59:03,540 --> 00:59:07,300
І за своєю суттю, хеш-таблицю
не що інше,

1257
00:59:07,300 --> 00:59:08,860
Масив плюс хеш-функція.

1258
00:59:08,860 --> 00:59:11,150
Ми збираємося говорити на трохи просто
переконайтеся, що всі розуміють, що таке

1259
00:59:11,150 --> 00:59:12,110
хеш-функція є.

1260
00:59:12,110 --> 00:59:15,420
І я кажу вам зараз, що це
не більше, ніж двох речей -

1261
00:59:15,420 --> 00:59:18,590
масив і хеш-функція.

1262
00:59:18,590 --> 00:59:20,716
І ось кроки по
який цього працює.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Там в наш масив.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Там наша функція.

1267
00:59:39,460 --> 00:59:43,180
Зокрема, хеш-функції повинні
зробити кілька речей з цим.

1268
00:59:43,180 --> 00:59:45,040
Я збираюся говорити конкретно
про ця проблема встановити.

1269
00:59:45,040 --> 00:59:46,450
Це, ймовірно, буде
прийняти в рядку.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
І те, що він збирається повернутися?

1272
00:59:51,770 --> 00:59:52,640
Який тип даних?

1273
00:59:52,640 --> 00:59:54,260
Олден?

1274
00:59:54,260 --> 00:59:55,760
Ваш хеш-функція повернення?

1275
00:59:55,760 --> 00:59:58,760
Ціле.

1276
00:59:58,760 --> 01:00:01,700
Так що це те, що хеш
Таблиця складається з -

1277
01:00:01,700 --> 01:00:05,430
таблиця у вигляді масиву
та хеш-функція.

1278
01:00:05,430 --> 01:00:06,010
Як це працює?

1279
01:00:06,010 --> 01:00:07,300
Він працює в три етапи.

1280
01:00:07,300 --> 01:00:08,740
Ми даємо йому ключ.

1281
01:00:08,740 --> 01:00:11,470
У цьому випадку, ми дамо йому рядок.

1282
01:00:11,470 --> 01:00:18,140
Ми називаємо хеш-функцію на першому етапі
на ключі, і ми отримуємо значення.

1283
01:00:18,140 --> 01:00:20,310
>> Зокрема, ми будемо говорити
ми отримуємо ціле.

1284
01:00:20,310 --> 01:00:25,630
Це ціле число, є дуже специфічна
межі того, що, що ціле може бути.

1285
01:00:25,630 --> 01:00:28,880
У цьому прикладі, наш масив
має розмір три.

1286
01:00:28,880 --> 01:00:32,330
Так що цифри можуть, що ціле бути.

1287
01:00:32,330 --> 01:00:35,970
Який діапазон допустимих значень для
що ціле, повертається тип це

1288
01:00:35,970 --> 01:00:37,220
хеш-функція?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Нуль, один і два.

1291
01:00:42,110 --> 01:00:46,060
Справа в хеш-функції є
з'ясувати місце в масиві

1292
01:00:46,060 --> 01:00:47,790
де наш ключ буде.

1293
01:00:47,790 --> 01:00:51,290
Є тільки три можливих
місця тут -

1294
01:00:51,290 --> 01:00:52,130
нуль, один або два.

1295
01:00:52,130 --> 01:00:55,360
Так ця функція більш високий дохід
нуль, один або два.

1296
01:00:55,360 --> 01:00:58,740
Деякі діє Indice в цьому масиві.

1297
01:00:58,740 --> 01:01:02,770
>> А потім залежно від того, де він повертає,
Ви можете побачити там безліч відкритий

1298
01:01:02,770 --> 01:01:03,730
дужки значення.

1299
01:01:03,730 --> 01:01:05,800
Ось де ми розмістили ключ.

1300
01:01:05,800 --> 01:01:11,280
Так ми кидаємо в гарбузі,
ми виходимо нулю.

1301
01:01:11,280 --> 01:01:15,540
У масиві кронштейна 0, покладемо гарбуз.

1302
01:01:15,540 --> 01:01:21,070
Кидаємо в кішок, ми отримуємо одну.

1303
01:01:21,070 --> 01:01:24,110
Ставимо кішку в одному.

1304
01:01:24,110 --> 01:01:25,480
Ставимо в павука.

1305
01:01:25,480 --> 01:01:26,710
Ми виходимо два.

1306
01:01:26,710 --> 01:01:30,200
Ставимо павука на масив кронштейна два.

1307
01:01:30,200 --> 01:01:32,300
Це було б так добре, якщо
він працював у цьому роді.

1308
01:01:32,300 --> 01:01:35,570
Але, на жаль, як ми побачимо,
це трохи складніше.

1309
01:01:35,570 --> 01:01:37,570
>> Перш ніж ми перейдемо туди, на будь-які питання
про це базова

1310
01:01:37,570 --> 01:01:38,820
наладка хеш-таблиці?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Це зображення точно
те, що ми звернули на дошці.

1313
01:01:51,940 --> 01:01:55,420
Але так як ми звернули його на дошці, я
я не збираюся йти в неї далі.

1314
01:01:55,420 --> 01:02:00,430
По суті ключі, магія чорного ящика -
або в даному випадку, чирок коробка - з

1315
01:02:00,430 --> 01:02:02,410
хеш-функція поміщає їх у відра.

1316
01:02:02,410 --> 01:02:04,690
І в цьому прикладі ми
не поінформувавши ім'я.

1317
01:02:04,690 --> 01:02:07,880
Ми покласти відповідний телефон
число імені у відрі.

1318
01:02:07,880 --> 01:02:10,430
Але ви могли б дуже добре просто
поставити ім'я у відрі.

1319
01:02:10,430 --> 01:02:12,950
>> Це всього лише картина того, що
ми звернули на дошці.

1320
01:02:12,950 --> 01:02:14,460
У нас є потенційні пастки, однако.

1321
01:02:14,460 --> 01:02:17,470
І є два зокрема
ковзає, що я хочу, щоб перейти.

1322
01:02:17,470 --> 01:02:20,230
Перший про
хеш-функція.

1323
01:02:20,230 --> 01:02:22,620
Тому я поставив питання, що
робить хороша хеш-функція?

1324
01:02:22,620 --> 01:02:24,220
Я даю дві відповіді.

1325
01:02:24,220 --> 01:02:26,630
По-перше, це детерміноване.

1326
01:02:26,630 --> 01:02:29,660
У контексті хеш-функцій,
що це означає?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Так?

1329
01:02:39,282 --> 01:02:42,850
>> АУДИТОРІЯ: Він може знайти
індекс за постійний час?

1330
01:02:42,850 --> 01:02:43,810
>> Джейсон Хіршхорна: Це
не те, що це означає.

1331
01:02:43,810 --> 01:02:44,725
Але це хороше припущення.

1332
01:02:44,725 --> 01:02:46,100
Хто-небудь ще є припущення
до того, що це означає?

1333
01:02:46,100 --> 01:02:47,780
Це гарна хеш-функція
детермінована?

1334
01:02:47,780 --> 01:02:48,280
Енні?

1335
01:02:48,280 --> 01:02:51,680
>> АУДИТОРІЯ: Це ключовий можна зіставити тільки
в одному місці в хеш-таблиці.

1336
01:02:51,680 --> 01:02:53,070
>> Джейсон Хіршхорна: Це
Абсолютно вірно.

1337
01:02:53,070 --> 01:02:57,430
Кожен раз, коли ви кладете в гарбуза,
вона завжди повертає нуль.

1338
01:02:57,430 --> 01:03:01,660
Якщо ви покладете на гарбуз і вашої хеш
Функція повертає нуль, але має

1339
01:03:01,660 --> 01:03:06,060
ймовірність повернення щось
ще більше нуля -

1340
01:03:06,060 --> 01:03:09,280
тому можливо, це може повернути одне іноді
або два інших рази -

1341
01:03:09,280 --> 01:03:11,100
що це не дуже гарна хеш-функція.

1342
01:03:11,100 --> 01:03:11,800
Ви абсолютно праві.

1343
01:03:11,800 --> 01:03:15,680
Ваш хеш-функція повинна повертати
точно такий же ціле число, в даному випадку, для

1344
01:03:15,680 --> 01:03:17,780
точно такий же рядком.

1345
01:03:17,780 --> 01:03:22,210
>> Може бути, вона повертає ту ж саму точну ціле
з тієї ж точною рядка

1346
01:03:22,210 --> 01:03:24,430
незалежно від капіталізації.

1347
01:03:24,430 --> 01:03:27,980
Але в такому випадку він як і раніше
детермінованою, так як кілька речей

1348
01:03:27,980 --> 01:03:29,350
відображаються на те ж значення.

1349
01:03:29,350 --> 01:03:30,170
Це нормально.

1350
01:03:30,170 --> 01:03:32,615
Поки є тільки один
вихід для даного входу.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> ОК.

1353
01:03:36,350 --> 01:03:38,340
Друге, що те, що це
повертає дійсні показники.

1354
01:03:38,340 --> 01:03:40,220
Ми виховані, що раніше.

1355
01:03:40,220 --> 01:03:41,860
Це хеш-функція -

1356
01:03:41,860 --> 01:03:43,710
про хлопчик -

1357
01:03:43,710 --> 01:03:46,840
хеш-функція повинна
повернутися допустимі показники.

1358
01:03:46,840 --> 01:03:47,740
Так би мовити -

1359
01:03:47,740 --> 01:03:48,990
давайте повернемося до цього прикладу.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
Мій хеш-функція підраховує
букви в слові.

1362
01:03:57,540 --> 01:03:58,380
Це хеш-функція.

1363
01:03:58,380 --> 01:03:59,740
І повертає, що ціле число.

1364
01:03:59,740 --> 01:04:04,280
Так що, якщо у мене є слово А, це
збирається повернутися один.

1365
01:04:04,280 --> 01:04:06,900
І це буде поставити прямо тут.

1366
01:04:06,900 --> 01:04:09,430
Що робити, якщо я ставлю в слові битою?

1367
01:04:09,430 --> 01:04:11,310
Це збирається повернутися три.

1368
01:04:11,310 --> 01:04:12,560
Де кажан йти?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> Це не підходить.

1371
01:04:19,750 --> 01:04:21,000
Але для цього потрібно піти куди-небудь.

1372
01:04:21,000 --> 01:04:23,340
Це мій хеш-таблиці зрештою, і
все має піти куди-небудь.

1373
01:04:23,340 --> 01:04:24,590
Так де повинні кажан йти?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Будь-які думки?

1376
01:04:28,710 --> 01:04:29,450
Вгадуємо?

1377
01:04:29,450 --> 01:04:30,280
Хороші припущення?

1378
01:04:30,280 --> 01:04:31,220
>> АУДИТОРІЯ: Нуль.

1379
01:04:31,220 --> 01:04:32,120
>> Джейсон Хіршхорна: Чому нулю?

1380
01:04:32,120 --> 01:04:35,990
>> АУДИТОРІЯ: Тому що три
модулю три дорівнює нулю?

1381
01:04:35,990 --> 01:04:38,620
>> Джейсон Хіршхорна: Три
модулю три дорівнює нулю.

1382
01:04:38,620 --> 01:04:40,810
Це велика здогадка,
і це правильно.

1383
01:04:40,810 --> 01:04:43,870
Таким чином, в цьому випадку він повинен
ймовірно, піти на нулі.

1384
01:04:43,870 --> 01:04:51,080
Так що хороший спосіб гарантувати, що цей хеш
Функція повертає тільки допустимі показники в

1385
01:04:51,080 --> 01:04:54,580
до модуля його розмірів таблиці.

1386
01:04:54,580 --> 01:04:57,360
Якщо ви по модулю Що б це ні прибутку за рахунок
три, ви завжди збираєтеся отримати

1387
01:04:57,360 --> 01:05:00,930
щось середнє між нуль, один і два.

1388
01:05:00,930 --> 01:05:05,160
І якщо це завжди повертає сім, і
ви завжди модулю на три, ви

1389
01:05:05,160 --> 01:05:06,030
завжди збираєтеся отримати те ж саме.

1390
01:05:06,030 --> 01:05:09,270
>> Так що це ще детермінованим
якщо ви по модулю.

1391
01:05:09,270 --> 01:05:11,420
Але, що буде гарантувати, що вам
ніколи не отримати щось -

1392
01:05:11,420 --> 01:05:12,940
інвалід промисловості.

1393
01:05:12,940 --> 01:05:16,840
Як правило, що за модулем має статися
всередині хеш-функції.

1394
01:05:16,840 --> 01:05:18,240
Так що вам не потрібно турбуватися про це.

1395
01:05:18,240 --> 01:05:20,555
Ви просто можете гарантувати, що
це правильний Indice.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Є питання по цьому
потенційна пастка?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> ОК.

1400
01:05:39,060 --> 01:05:40,290
І там ми йдемо.

1401
01:05:40,290 --> 01:05:42,890
Наступна потенційна пастка, і
це великий.

1402
01:05:42,890 --> 01:05:46,880
Що робити, якщо дві клавіші карту
в те ж значення?

1403
01:05:46,880 --> 01:05:49,350
Таким чином, є два способи впоратися з цим.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Перший називається лінійним
зондування, який я

1406
01:05:56,020 --> 01:05:57,300
не збираюся перейти на.

1407
01:05:57,300 --> 01:06:01,120
Але ви повинні бути знайомі з тим, як
що працює, а що це таке.

1408
01:06:01,120 --> 01:06:05,610
>> Другий я збираюся перейти на
тому що це той, який багато

1409
01:06:05,610 --> 01:06:08,290
люди, ймовірно, в кінцевому підсумку вирішити,
використовувати у своїй проблемі набору.

1410
01:06:08,290 --> 01:06:09,820
Звичайно, ви не повинні.

1411
01:06:09,820 --> 01:06:15,280
Але для безлічі проблем, багатьох людей
як правило, вибирають для створення хеш-таблицю

1412
01:06:15,280 --> 01:06:17,950
з роздільного зв'язування реалізації
їх словник.

1413
01:06:17,950 --> 01:06:21,390
Так що ми збираємося перейти на те, що це означає,
створити хеш-таблицю з

1414
01:06:21,390 --> 01:06:23,890
окремий ланцюжка.

1415
01:06:23,890 --> 01:06:26,260
>> Так що я поклав на гарбуз.

1416
01:06:26,260 --> 01:06:29,560
Це повертає нуль.

1417
01:06:29,560 --> 01:06:31,410
І я поклав гарбуз тут.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Тоді я поклав у -

1420
01:06:37,930 --> 01:06:39,922
що ще один Хеллоуїн-тематичний річ?

1421
01:06:39,922 --> 01:06:42,200
>> АУДИТОРІЯ: Цукерки.

1422
01:06:42,200 --> 01:06:42,770
>> Джейсон Хіршхорна: Цукерки!

1423
01:06:42,770 --> 01:06:43,910
Це відмінне.

1424
01:06:43,910 --> 01:06:47,760
Я поклав в цукерки, і цукерки
також дає мені нулю.

1425
01:06:47,760 --> 01:06:49,350
Що мені робити?

1426
01:06:49,350 --> 01:06:51,940
Є ідеї?

1427
01:06:51,940 --> 01:06:53,940
Тому що все, що ви начебто знаю
що окремі ланцюжка є.

1428
01:06:53,940 --> 01:06:55,190
Так будь-які ідеї, що робити?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Так.

1431
01:06:59,110 --> 01:07:03,810
>> АУДИТОРІЯ: Введення рядок
насправді в хеш-таблиці.

1432
01:07:03,810 --> 01:07:08,910
>> Джейсон Хіршхорна: Таким чином, ми збираємося
залучити хорошу ідею тут.

1433
01:07:08,910 --> 01:07:09,340
ОК.

1434
01:07:09,340 --> 01:07:12,290
>> АУДИТОРІЯ: Є хеш-таблиці
[Нерозбірливості]

1435
01:07:12,290 --> 01:07:16,640
покажчик, який вказує на
початок списку.

1436
01:07:16,640 --> 01:07:20,930
А потім гарбуз бути перше значення
в цьому пов'язаному списку і цукерки бути

1437
01:07:20,930 --> 01:07:22,800
друге значення в цій пов'язаного списку.

1438
01:07:22,800 --> 01:07:23,420
>> Джейсон Хіршхорна: ОК.

1439
01:07:23,420 --> 01:07:24,670
Маркус, який був чудовим.

1440
01:07:24,670 --> 01:07:26,160
Я збираюся зруйнувати це.

1441
01:07:26,160 --> 01:07:28,890
Маркус кажу, що не
перезаписати гарбуз.

1442
01:07:28,890 --> 01:07:30,660
Це було б погано.

1443
01:07:30,660 --> 01:07:33,640
Не ставте цукерки десь в іншому місці.

1444
01:07:33,640 --> 01:07:35,390
Ми збираємося поставити їх обох на нулі.

1445
01:07:35,390 --> 01:07:37,770
Але ми збираємося мати справу з
покласти їх в нулі

1446
01:07:37,770 --> 01:07:39,395
створення списку на нулі.

1447
01:07:39,395 --> 01:07:42,430
І ми збираємося створити список
все, що відображається на нуль.

1448
01:07:42,430 --> 01:07:47,960
І найкращий спосіб ми навчилися створювати
список, який може збільшуватися і зменшуватися

1449
01:07:47,960 --> 01:07:49,840
динамічно чи не знаходиться в межах
інший масив.

1450
01:07:49,840 --> 01:07:51,510
Так не багатовимірний масив.

1451
01:07:51,510 --> 01:07:54,080
Але просто створити зв'язаний список.

1452
01:07:54,080 --> 01:07:55,330
>> Так що він запропонував -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Я збираюся отримання нової -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
це створити масив з покажчиками,
масив покажчиків.

1457
01:08:19,689 --> 01:08:20,580
ОК.

1458
01:08:20,580 --> 01:08:24,180
Будь-яка ідея чи натяк, що тип
цього покажчиків має бути?

1459
01:08:24,180 --> 01:08:26,290
Маркус?

1460
01:08:26,290 --> 01:08:27,250
>> АУДИТОРІЯ: Покажчики на -

1461
01:08:27,250 --> 01:08:28,609
>> Джейсон Хіршхорна: Тому що вам
сказав зв'язаний список, а значить -

1462
01:08:28,609 --> 01:08:29,520
>> АУДИТОРІЯ: Node покажчики?

1463
01:08:29,520 --> 01:08:30,670
>> Джейсон Хіршхорна: Node покажчики.

1464
01:08:30,670 --> 01:08:32,830
Якщо речі в наш пов'язані
Список вузли, то вони

1465
01:08:32,830 --> 01:08:34,370
повинні бути покажчики вузлів.

1466
01:08:34,370 --> 01:08:35,939
І що ж вони рівні спочатку?

1467
01:08:35,939 --> 01:08:36,990
>> АУДИТОРІЯ: Null.

1468
01:08:36,990 --> 01:08:38,240
>> Джейсон Хіршхорна: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Так що наш порожній річчю.

1471
01:08:46,080 --> 01:08:47,170
Гарбузове повертає нуль.

1472
01:08:47,170 --> 01:08:48,569
Що нам робити?

1473
01:08:48,569 --> 01:08:49,609
Прогулянка мене через нього?

1474
01:08:49,609 --> 01:08:50,810
Насправді, Маркус вже дав мені.

1475
01:08:50,810 --> 01:08:52,439
Хтось ще погуляти я через нього.

1476
01:08:52,439 --> 01:08:54,760
Що ми робимо, коли ми -

1477
01:08:54,760 --> 01:08:56,609
це виглядає дуже схоже на
те, що ми просто робили.

1478
01:08:56,609 --> 01:08:57,396
Аві.

1479
01:08:57,396 --> 01:08:59,090
>> АУДИТОРІЯ: Я збираюся зробити припущення.

1480
01:08:59,090 --> 01:09:01,250
Тому, коли ви отримуєте цукерки.

1481
01:09:01,250 --> 01:09:01,640
>> Джейсон Хіршхорна: Так.

1482
01:09:01,640 --> 01:09:03,120
Ну, ми отримали гарбуз.

1483
01:09:03,120 --> 01:09:03,870
Давайте наш перший.

1484
01:09:03,870 --> 01:09:04,324
Ми отримали гарбуз.

1485
01:09:04,324 --> 01:09:04,779
>> АУДИТОРІЯ: ОК.

1486
01:09:04,779 --> 01:09:05,880
Гарбузове повертає нуль.

1487
01:09:05,880 --> 01:09:08,770
Таким чином, ви покладете його в тому, що.

1488
01:09:08,770 --> 01:09:10,810
Або насправді, ви поклали його
у зв'язаному списку.

1489
01:09:10,810 --> 01:09:13,550
>> Джейсон Хіршхорна: Як ми
покласти його у зв'язаному списку?

1490
01:09:13,550 --> 01:09:15,479
>> АУДИТОРІЯ: О, фактичний синтаксис?

1491
01:09:15,479 --> 01:09:16,240
>> Джейсон Хіршхорна: Просто ходити -

1492
01:09:16,240 --> 01:09:16,740
сказати більше.

1493
01:09:16,740 --> 01:09:19,310
Що нам робити?

1494
01:09:19,310 --> 01:09:22,100
>> АУДИТОРІЯ: Ви просто вставити
це як перший вузол.

1495
01:09:22,100 --> 01:09:22,675
>> Джейсон Хіршхорна: ОК.

1496
01:09:22,675 --> 01:09:29,069
Таким чином, ми маємо нашу вузла, гарбуз.

1497
01:09:29,069 --> 01:09:31,560
А тепер, як я вводжу його?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> АУДИТОРІЯ: Ви призначаєте
це до покажчика.

1500
01:09:37,090 --> 01:09:37,970
>> Джейсон Хіршхорна: Які покажчик?

1501
01:09:37,970 --> 01:09:39,620
>> АУДИТОРІЯ: Покажчик на нулі.

1502
01:09:39,620 --> 01:09:41,420
>> Джейсон Хіршхорна: То де
робить це сенс?

1503
01:09:41,420 --> 01:09:42,810
>> АУДИТОРІЯ: Щоб обнулити прямо зараз.

1504
01:09:42,810 --> 01:09:43,529
>> Джейсон Хіршхорна: Ну,
це вказує на нуль.

1505
01:09:43,529 --> 01:09:44,499
Але я ставлю на гарбуз.

1506
01:09:44,499 --> 01:09:46,053
Так де він повинен вказувати?

1507
01:09:46,053 --> 01:09:46,880
>> АУДИТОРІЯ: Щоб гарбуз.

1508
01:09:46,880 --> 01:09:47,399
>> Джейсон Хіршхорна: Для гарбуза.

1509
01:09:47,399 --> 01:09:48,760
Саме так.

1510
01:09:48,760 --> 01:09:50,010
Так що це вказує на гарбуз.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
А причому тут цей покажчик
в гарбуза точки?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
До

1515
01:09:58,340 --> 01:09:58,590
>> АУДИТОРІЯ: Null.

1516
01:09:58,590 --> 01:09:59,210
>> Джейсон Хіршхорна: Щоб обнулити.

1517
01:09:59,210 --> 01:10:00,460
Саме так.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Так що ми просто вставляється щось
у зв'язаному списку.

1520
01:10:05,140 --> 01:10:07,210
Ми тільки що написав цей код, щоб зробити це.

1521
01:10:07,210 --> 01:10:09,520
Майже ми майже вийшло
повністю тріщини.

1522
01:10:09,520 --> 01:10:10,790
Тепер ми вставляємо цукерки.

1523
01:10:10,790 --> 01:10:13,480
Наша цукерки також прагне до нуля.

1524
01:10:13,480 --> 01:10:16,100
Так що ж нам робити з цукерками?

1525
01:10:16,100 --> 01:10:18,790
>> АУДИТОРІЯ: Це залежить від того,
не ми намагаємося залагодити його.

1526
01:10:18,790 --> 01:10:19,640
>> Джейсон Хіршхорна: Це
Абсолютно вірно.

1527
01:10:19,640 --> 01:10:21,070
Це залежить від наявності або відсутності
ми намагаємося залагодити його.

1528
01:10:21,070 --> 01:10:22,660
Давайте припустимо, що ми не
збирається залагодити його.

1529
01:10:22,660 --> 01:10:24,880
>> АУДИТОРІЯ: Ну що ж, як ми обговорювали
раніше, то простіше просто поставити його

1530
01:10:24,880 --> 01:10:28,590
на самому початку так покажчик
від нуля вказує на цукерки.

1531
01:10:28,590 --> 01:10:29,020
>> Джейсон Хіршхорна: ОК.

1532
01:10:29,020 --> 01:10:29,380
Тримайся.

1533
01:10:29,380 --> 01:10:30,630
Дозвольте мені створити цукерки прямо тут.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Так цей покажчик -

1536
01:10:35,150 --> 01:10:37,590
>> АУДИТОРІЯ: Так, треба зараз
бути вказуючи на цукерки.

1537
01:10:37,590 --> 01:10:40,580
Тоді є вказівник від
цукерки вказують на гарбуз.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> Джейсон Хіршхорна: Як що?

1540
01:10:44,560 --> 01:10:47,380
І сказати, що ми отримали ще один
що потрібно зіставити з нуля?

1541
01:10:47,380 --> 01:10:48,660
>> АУДИТОРІЯ: Ну, ви просто
зробити те ж саме?

1542
01:10:48,660 --> 01:10:50,290
>> Джейсон Хіршхорна: Зробіть те ж саме.

1543
01:10:50,290 --> 01:10:53,700
Таким чином, в цьому випадку, якщо ми не будемо
хочете зберегти це владнав його

1544
01:10:53,700 --> 01:10:55,270
Звучить досить просто.

1545
01:10:55,270 --> 01:10:59,920
Візьмемо покажчик в Indice
дається нашої хеш-функції.

1546
01:10:59,920 --> 01:11:03,830
У нас є, що крапка в наш новий вузол.

1547
01:11:03,830 --> 01:11:07,830
І тоді все, що було вказуючи
раніше -

1548
01:11:07,830 --> 01:11:10,620
у разі нуль, в
Другий випадок гарбуза -

1549
01:11:10,620 --> 01:11:15,310
що, як там воно вказуючи на
раніше, ми додаємо в найближчих

1550
01:11:15,310 --> 01:11:17,810
наш новий вузол.

1551
01:11:17,810 --> 01:11:19,650
Ми вставки щось
на самому початку.

1552
01:11:19,650 --> 01:11:22,900
Насправді це набагато простіше, ніж
намагаючись зберегти список, відсортований.

1553
01:11:22,900 --> 01:11:25,340
Але, знову ж, пошук буде
Чим складніше тут.

1554
01:11:25,340 --> 01:11:28,300
Ми завжди доведеться йти до кінця.

1555
01:11:28,300 --> 01:11:29,650
>> ОК.

1556
01:11:29,650 --> 01:11:32,750
Будь-які питання про роздільного зв'язування?

1557
01:11:32,750 --> 01:11:34,690
Як це працює?

1558
01:11:34,690 --> 01:11:35,820
Будь ласка, попросіть їх зараз.

1559
01:11:35,820 --> 01:11:39,260
Я дуже хочу, щоб переконатися, що ви все
зрозуміти це перш, ніж ми качан.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> Зал: А чому ви поставити гарбуз
і цукерки в те ж саме

1562
01:11:52,060 --> 01:11:54,108
частина хеш-таблиці?

1563
01:11:54,108 --> 01:11:55,860
>> Джейсон Хіршхорна: Хороше питання.

1564
01:11:55,860 --> 01:11:59,140
Чому ми ставимо їх у те ж саме
частина хеш-таблиці?

1565
01:11:59,140 --> 01:12:03,200
Ну, в цьому випадку наша хеш-функція
повертає нуль для них обох.

1566
01:12:03,200 --> 01:12:05,310
Таким чином, вони повинні піти на нулі Indice
тому що там ми збираємося

1567
01:12:05,310 --> 01:12:07,420
дивитися на них, якщо ми коли-небудь
хочу подивитися їх.

1568
01:12:07,420 --> 01:12:11,750
Знову ж, з лінійною зондування підхід
ми б не покласти їх обох в нулі.

1569
01:12:11,750 --> 01:12:13,900
Але в окремому підході ланцюга,
ми збираємося поставити їх обох в нулі

1570
01:12:13,900 --> 01:12:16,620
а потім створити список з нуля.

1571
01:12:16,620 --> 01:12:20,140
>> І ми не хочемо, щоб перезаписати гарбуз
просто для цього, тому що тоді ми будемо

1572
01:12:20,140 --> 01:12:21,860
Припустимо, що гарбуз була
ніколи не вставляється.

1573
01:12:21,860 --> 01:12:25,230
Якщо ми просто тримати одну річ в
місце, яке було б погано.

1574
01:12:25,230 --> 01:12:28,590
Тоді не було б
шанс з нас коли-небудь -

1575
01:12:28,590 --> 01:12:31,660
якщо ми колись мали дублікат, то ми
просто стерти нашу початкове значення.

1576
01:12:31,660 --> 01:12:34,090
Так от чому ми робимо цей підхід.

1577
01:12:34,090 --> 01:12:36,580
Або ось чому ми вибрали - але знову ж, ми
вибрав окремий підхід ланцюгових,

1578
01:12:36,580 --> 01:12:39,670
яких є багато інших підходів
можна було вибрати.

1579
01:12:39,670 --> 01:12:41,185
Я відповів на ваше запитання?

1580
01:12:41,185 --> 01:12:41,660
>> ОК.

1581
01:12:41,660 --> 01:12:42,910
Карлос.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Лінійний зондування включатиме -

1584
01:12:47,720 --> 01:12:51,913
Якщо ми знайшли зіткнення в нулі,
виглядатиме в наступному місці, щоб побачити, якщо

1585
01:12:51,913 --> 01:12:54,310
вона була відкрита і поклав його там.

1586
01:12:54,310 --> 01:12:57,320
А потім ми подивимося в наступному спорту і
подивитися, якщо це було відкрито, і поклав його туди.

1587
01:12:57,320 --> 01:12:59,780
Таким чином, ми знаходимо наступний доступний
відкрите місце і поклав його там.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Будь-які інші питання?

1590
01:13:03,890 --> 01:13:05,370
Так, Аві.

1591
01:13:05,370 --> 01:13:07,490
>> АУДИТОРІЯ: У продовження до цього,
що ви маєте на увазі наступне місце?

1592
01:13:07,490 --> 01:13:10,250
У хеш-таблиці або у зв'язаному списку.

1593
01:13:10,250 --> 01:13:12,100
>> Джейсон Хіршхорна: Для лінійних
програмування, не пов'язані списки.

1594
01:13:12,100 --> 01:13:13,400
Наступного пляма на хеш-таблиці.

1595
01:13:13,400 --> 01:13:13,820
>> АУДИТОРІЯ: ОК.

1596
01:13:13,820 --> 01:13:17,570
Таким чином, хеш-таблиця буде
инициализирован розміром -

1597
01:13:17,570 --> 01:13:19,560
як число рядків
що ви були вставки?

1598
01:13:19,560 --> 01:13:22,170
>> Джейсон Хіршхорна: Ви б
хочу, щоб це дійсно великий.

1599
01:13:22,170 --> 01:13:23,910
Так.

1600
01:13:23,910 --> 01:13:27,900
Ось картина того, що ми
просто звернув на дошці.

1601
01:13:27,900 --> 01:13:29,470
Знову ж, у нас є зіткнення прямо тут.

1602
01:13:29,470 --> 01:13:30,710
на 152.

1603
01:13:30,710 --> 01:13:33,570
І ви побачите, ми створили
зв'язаний список з нього.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Знову ж, хеш-таблиці окремий ланцюжка
підхід не той, який ви

1606
01:13:41,850 --> 01:13:45,590
повинні прийняти для проблеми встановіть
шість, але це той, який багато

1607
01:13:45,590 --> 01:13:47,100
студенти, як правило, щоб взяти.

1608
01:13:47,100 --> 01:13:51,140
Так на цій ноті, давайте коротко поговоримо
перш, ніж ми качан про проблему шість,

1609
01:13:51,140 --> 01:13:52,160
а потім я поділюся з вами історією.

1610
01:13:52,160 --> 01:13:55,120
У нас є три хвилини.

1611
01:13:55,120 --> 01:13:55,750
>> Архів завдань шість.

1612
01:13:55,750 --> 01:13:57,790
У вас є чотири функції -

1613
01:13:57,790 --> 01:14:02,430
навантаження, перевірте, розмір і вивантаження.

1614
01:14:02,430 --> 01:14:03,380
Навантаження -

1615
01:14:03,380 --> 01:14:07,120
добре, ми йшли
над навантаженням тільки зараз.

1616
01:14:07,120 --> 01:14:09,330
Ми звернули навантаження на дошці.

1617
01:14:09,330 --> 01:14:13,230
І ми навіть почали кодування багато
вставки у зв'язаному списку.

1618
01:14:13,230 --> 01:14:18,020
Так навантаження не набагато більше, ніж
що ми тільки що робили.

1619
01:14:18,020 --> 01:14:21,070
>> Перевірити це, як тільки ви
щось завантажений.

1620
01:14:21,070 --> 01:14:22,580
Це той же самий процес, як цей.

1621
01:14:22,580 --> 01:14:26,845
Ті ж перші дві частини, де ви кидаєте
щось в хеш-функції

1622
01:14:26,845 --> 01:14:29,190
і отримати його значення.

1623
01:14:29,190 --> 01:14:30,700
Але зараз ми не вставляючи його.

1624
01:14:30,700 --> 01:14:33,350
Зараз ми шукаємо для нього.

1625
01:14:33,350 --> 01:14:37,130
Я зразок коду, написаного для знаходження
щось у зв'язаному списку.

1626
01:14:37,130 --> 01:14:38,250
Я закликаю вас, щоб практикувати це.

1627
01:14:38,250 --> 01:14:43,000
Але інтуїтивно знайти щось буде
досить схоже на вставку щось.

1628
01:14:43,000 --> 01:14:46,540
Справді, ми намалювали картину знаходження
щось у зв'язаному списку, рухаючись

1629
01:14:46,540 --> 01:14:48,910
через, поки не дісталися до кінця.

1630
01:14:48,910 --> 01:14:52,430
І якщо ви дісталися до кінця так і не змогли
знайти його, то це не є.

1631
01:14:52,430 --> 01:14:55,400
Так от перевірка, по суті.

1632
01:14:55,400 --> 01:14:57,030
>> Далі йде розмір.

1633
01:14:57,030 --> 01:14:57,910
Давай пропустимо розмір.

1634
01:14:57,910 --> 01:15:00,040
Нарешті ви вивантажити.

1635
01:15:00,040 --> 01:15:02,890
Розвантаження є одним ми не тягне
на дошці або закодовані ще.

1636
01:15:02,890 --> 01:15:05,990
Але я закликаю вас, щоб спробувати його кодування
в нашому прикладі, пов'язаного, наприклад списку.

1637
01:15:05,990 --> 01:15:11,440
Але вивантажити інтуїтивно
схожий на замовлення -

1638
01:15:11,440 --> 01:15:14,010
або я маю на увазі схожий на перевірити.

1639
01:15:14,010 --> 01:15:17,350
Для тепер кожен раз, коли ви збираєтеся винятком
через, ви не просто перевіряти,

1640
01:15:17,350 --> 01:15:19,090
побачити, якщо у вас є свій значення там.

1641
01:15:19,090 --> 01:15:22,490
Але ви приймаєте цей вузол і
звільняючи його, по суті.

1642
01:15:22,490 --> 01:15:23,610
Це те, що вивантаження просить вас зробити.

1643
01:15:23,610 --> 01:15:24,670
Безкоштовний все, що ви malloced.

1644
01:15:24,670 --> 01:15:27,480
Так що ви збираєтеся через весь список
знову, проходячи через весь хеш

1645
01:15:27,480 --> 01:15:27,760
Таблиця знову.

1646
01:15:27,760 --> 01:15:29,240
На цей раз не перевіряти
щоб подивитися, що там.

1647
01:15:29,240 --> 01:15:31,080
Просто скачати, що там.

1648
01:15:31,080 --> 01:15:33,260
>> І, нарешті розмір.

1649
01:15:33,260 --> 01:15:34,350
Розмір повинен бути реалізований.

1650
01:15:34,350 --> 01:15:35,590
Якщо ви не реалізуєте розмір -

1651
01:15:35,590 --> 01:15:36,250
Я скажу це, як це.

1652
01:15:36,250 --> 01:15:39,740
Якщо ви не реалізуєте розмір в точності
одного рядка коду в тому числі

1653
01:15:39,740 --> 01:15:43,760
повернутися заяву, ви
робить розмір неправильно.

1654
01:15:43,760 --> 01:15:47,170
Тому переконайтеся розмір, для повного дизайну
точки, ви робите це в точності один

1655
01:15:47,170 --> 01:15:49,970
рядок коду, в тому числі
оператор повернення.

1656
01:15:49,970 --> 01:15:52,450
>> І не зібратися ще, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Прагнучи бобра.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Я хотів сказати спасибі вам, хлопці
за те, щоб розділі.

1660
01:16:01,300 --> 01:16:02,550
Майте Happy Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Це мій костюм.

1663
01:16:05,960 --> 01:16:08,850
Я буду носити це в четвер
якщо я бачу вас в робочий час.

1664
01:16:08,850 --> 01:16:14,640
І якщо вам цікаво, про деякі більш
фон, щоб цього костюма, відчуваю

1665
01:16:14,640 --> 01:16:19,135
можете перевірити 2011 розділ
для історії про те, чому я

1666
01:16:19,135 --> 01:16:20,900
носити гарбуза костюм.

1667
01:16:20,900 --> 01:16:23,680
І це сумна історія.

1668
01:16:23,680 --> 01:16:27,050
Тому переконайтеся, що у вас є
деякі тканини поблизу.

1669
01:16:27,050 --> 01:16:28,680
Але на цьому, якщо у вас є які-небудь
питання, я буду дотримуватися навколо

1670
01:16:28,680 --> 01:16:29,960
зовні після розділу.

1671
01:16:29,960 --> 01:16:31,510
Удачи на проблеми встановити шість.

1672
01:16:31,510 --> 01:16:33,540
І як завжди, якщо у вас є які-небудь
питання, дайте мені знати.

1673
01:16:33,540 --> 01:16:35,584